Алгоритмы идентификации контента, сгенерированного Марковым?
https://stackoverflow.com/questions/1185369
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Цепи Маркова - это (почти стандартный) способ генерации случайная тарабарщина который выглядит умным на нетренированный взгляд.Как бы вы отнеслись к идентификации текста, сгенерированного Марковым, по написанному человеком тексту?
Было бы здорово, если бы ресурсы, на которые вы указываете, были дружественны к Python.
Решение
Вы можете использовать подход «грубой силы», при котором вы сравниваете сгенерированный язык с данными, собранными на n-граммах более высокого порядка, чем модель Маркова, которая его сгенерировала.
то естьЕсли язык был создан с использованием марковской модели 2-го порядка, то до 3-х граммов будут иметь правильные частоты, но 4-граммы, вероятно, не будут.
Вы можете получить до 5-граммовых частот от паблика Google набор данных n-грамм. Хотя он огромен - 24G. сжатый - его нужно получить по почте на DVD от НРС.
РЕДАКТИРОВАТЬ:Добавлены некоторые подробности реализации
N-граммы уже подсчитаны, поэтому вам просто нужно сохранить количество (или частоты) таким образом, чтобы их можно было быстро найти.Правильно проиндексированная база данных или, возможно, индекс Lucene должна работать.
Взяв фрагмент текста, просканируйте его и найдите частоту встречаемости каждой 5-граммы в вашей базе данных и посмотрите, какое место она занимает по сравнению с другими 5-граммами, начинающимися с тех же четырех слов.
На практике более серьезным препятствием могут стать условия лицензирования набора данных.Использование его для коммерческого приложения может быть запрещено.
Другие советы
Одним из простых подходов было бы попросить большую группу людей прочитать за вас вводимый текст и посмотреть, имеет ли этот текст смысл.Я только наполовину шучу, это сложная проблема.
Я считаю, что это сложная проблема, потому что текст, сгенерированный цепочкой Маркова, будет обладать многими теми же свойствами, что и реальный человеческий текст, с точки зрения частоты слов и простых взаимосвязей между порядком слов.
Различия между реальным текстом и текстом, генерируемым цепочкой Маркова, заключаются в высокоуровневых правилах грамматики и в семантическом значении, которые трудно закодировать программно.Другая проблема заключается в том, что цепочки Маркова достаточно хороши в генерации текста, чтобы иногда выдавать грамматически и семантически правильные утверждения.
В качестве примера, вот афоризм из машины канта:
Сегодня он был бы убежден, что человеческая воля свободна;завтра, учитывая неразрывную цепь природы, он будет смотреть на свободу как на простую иллюзию и объявит природу всем во всем.
Хотя эта строка была написана компьютерной программой, трудно сказать, что человек никогда бы этого не сказал.
Я думаю, что если вы не сможете предоставить нам более конкретные детали о тексте, созданном компьютером и человеком, которые выявляют более очевидные различия, будет трудно решить эту проблему с помощью компьютерного программирования.
Я предлагаю обобщение ответа Эвана:создайте собственную марковскую модель и обучите ее на большом фрагменте (очень большой) предоставленной вам выборки, оставив остальную часть выборки как «тестовые данные».Теперь посмотрите, насколько хорошо обученная вами модель работает на тестовых данных, напримерс помощью критерия хи-квадрат, который подсказывает ситуацию, в которой «подбор СЛИШКОМ хорош» (предполагая, что тестовые данные действительно сгенерированы этой моделью), а также ситуации, в которых соответствие очень плохое (предполагающее ошибку в структуре модели — превышение -обученная модель с неправильной структурой в таких случаях заведомо плохо справляется).
Конечно, есть еще много проблем для калибровки, таких как структура модели - вы подозреваете, что это простая модель, основанная на Ntupleх слов и немного больше, или более сложная модель с грамматическими состояниями и тому подобное.К счастью, вы можете довольно хорошо откалибровать ситуацию, используя большие корпуса заведомо естественного текста, а также те, которые вы создаете сами с помощью моделей различной структуры.
Другой подход заключается в использовании нлтк для анализа предложенных вам предложений - даже в естественном тексте следует ожидать небольшого количества неправильных анализов (поскольку люди несовершенны, и синтаксический анализатор тоже - он может не знать, что слово X может использоваться как глагол и классифицировать его только как существительное и т. д. и т. п.), но большинство моделей Маркова (если только они не моделируют по существу ту же самую грамматическую структуру, которую использует ваш синтаксический анализатор - и вы можете использовать несколько парсеров, чтобы попытаться противодействовать этому!-) вызовет НАМНОГО больше ошибок при синтаксическом анализе, чем даже у людей с дислексией.Опять же, сравните это с естественными и синтетическими текстами, и вы поймете, что я имею в виду!-)
Если бы у вас было несколько больших текстов, сгенерированных Марковым, вы могли бы определить, что это так, сравнив частоту слов в каждом из образцов.Поскольку цепи Маркова зависят от постоянных вероятностей слов, пропорции любого слова должны быть примерно равны от образца к образцу.
Краудсорсинг.Используйте «Механического турка» и попросите несколько человек проголосовать за это.Есть даже несколько библиотек, которые помогут вам в этом.Например:
Вот сообщение в блоге O'Reilly Radar с советами по использованию Mechanical Turk для выполнения вашей работы:
Если вы напишете программу, которая генерирует вероятности марковского перехода из любой последовательности символов, а затем вычисляет уровень энтропии марковской матрицы.(видеть http://en.wikipedia.org/wiki/Entropy_rate#Entropy_rates_for_Markov_chains) По сути, это оценка того, насколько легко можно предсказать текст, используя только цепь Маркова (более высокая энтропия означает Сильнее предсказывать).Поэтому я думаю, что чем ниже энтропия марковской матрицы, тем более вероятно, что образец текста контролируется марковской матрицей.Если у вас есть вопросы о том, как написать этот код, у меня есть программа на Python, которая делает именно это на моем компьютере, поэтому я могу вам помочь.
