Марковские цепи - это (почти стандартный) способ генерации random gibberish, который выглядит разумным для неподготовленного глаза. Как бы вы хотели определить марковский текст из написанного человеком текста.Алгоритмы для идентификации созданного марковским контентом?
Было бы здорово, если бы ресурсы, на которые вы указываете, являются дружественными Python.
Вы можете использовать подход «грубой силы», посредством которого вы сравниваете сгенерированный язык с данными, собранными на n-граммах более высокого уровня чем модель Маркова, которая его породила.
Т.е., если язык был сгенерирован марковской моделью 2-го порядка, то до 3 грамм будут иметь правильные частоты, но 4 грамма, вероятно, не будут.
Вы можете получить до частот 5-граммовых от компании Google общественного n-gram dataset. Это огромное, хотя - 24G сжимается - вы должны получить его по почте на DVD-дисках от LDC.
EDIT: Добавлены некоторые детали реализации
N-граммы уже подсчитаны, так что вам просто нужно хранить счетчики (или частоты), таким образом, чтобы быстро найти. Должна работать правильно проиндексированная база данных или, возможно, индекс Lucene.
Учитывая текст, сканируйте его и посмотрите на частоту каждого 5-граммов в своей базе данных и посмотрите, где он по сравнению с другими 5-граммами, начинающимися с тех же 4 слов.
Практически более серьезным препятствием может быть лицензионное соглашение с набором данных. Использование его для коммерческого приложения может быть запрещено.
Если у вас было несколько больших текстов, созданных Марковым, вы могли бы определить, что они были такими, сравнивая частоты слов между каждыми образцами. Поскольку цепи Маркова зависят от постоянных вероятностей слов, пропорции любого данного слова должны быть примерно равны от образца к образцу.
Возможно, также стоит посмотреть на набор инструментов для естественного языка на основе python: http://nltk.sourceforge.net/ - сказал, что это может быть немного чрезмерно, если вас интересуют только частоты слов. – Markus
Если словосочетания генерируются так, чтобы они выглядели как настоящий текст, у вас могут возникнуть проблемы, если вы работаете с частотами слов, таких как ... – Janusz
Проблема с этим подходом заключается в том, что если созданный человеком текст и текст, генерируемый марковской цепочкой, сделаны из текста с аналогичными частотами перехода слов и слов, текст, созданный цепочкой Марков, будет похож на текст, созданный человеком. –
Один простой подход состоял бы в том, чтобы большая группа людей прочитала текст ввода для вас и посмотрела, имеет ли смысл текст. Я просто шучу, это сложная проблема.
Я считаю, что это сложная проблема, потому что текст сгенерированной цепочкой Марков будет иметь много одинаковых свойств реального человеческого текста с точки зрения частоты слов и простых отношений между упорядочением слов.
Различия между реальным текстом и текстом, генерируемым цепью Маркова, находятся в правилах грамматики более высокого уровня и в семантическом значении, которые сложно кодировать программно. Другая проблема заключается в том, что цепи Маркова достаточно хороши для генерации текста, который иногда возникает с грамматически и семантически корректными утверждениями.
В качестве примера, вот aphorism from the kantmachine:
Сегодня он чувствовал бы убежден, что человеческая воля свободна; завтра, , считая неразрывную цепь природы, он будет смотреть на свободу как на просто иллюзию и объявить природу все-в-одном.
Хотя эта строка была написана компьютерной программой, трудно сказать, что человек никогда не скажет об этом.
Я думаю, что, если вы не можете дать нам более конкретные сведения о компьютере и человеческом тексте, которые выявят более очевидные различия, будет сложно решить это с помощью компьютерного программирования.
Это довольно тревожно. Я прочитал «Критику чистого разума» (единственная работа Канта, которую я мог бы заставить себя прочитать/понять), и я бы никогда не сказал, что афоризм генерируется машиной. – shylent
@shylent - это был четвертый хит на странице, и я согласен, это очень похоже на стиль Канта. Это было бы очень хорошим примером для курса, который включает цепи Маркова! –
Краудсорсинг. Используйте Механический Турок и попросите нескольких людей проголосовать за это. Есть даже некоторые библиотеки, которые помогут вам снять это. Например:
Вот блог от O'Reilly Radar на советы по использованию Mechanical Turk, чтобы получить работу:
Я предлагаю обобщение ответа Эвана: сделайте собственную марковскую модель и обучите ее большим куском (очень большой) образец, который вы дадите, оставив остальную часть образца как «тестовые данные». Теперь посмотрим, насколько хорошо модель, которую вы обучили, выполняет на тестовых данных, например.с критерием квадратного квадрата, который предложит ситуацию, в которой «fit is TOO good» (предполагая, что тестовые данные действительно генерируются этой моделью), а также те, в которых соответствие очень плохое (предполагая ошибку в структуре модели - более -приведенная модель с неправильной структурой делает в этих случаях заведомо плохую работу).
Конечно, есть еще много вопросов для калибровки, таких как структура модели - вы подозреваете простую модель, основанную на Ntuples слов и немного больше, или более сложную с грамматическими состояниями и тому подобное. К счастью, вы можете довольно хорошо откалибровать вещи, используя большие корпуса из обычного текста, а также те, которые вы создаете с помощью моделей различных структур.
Другой подход заключается в использовании nltk для анализа предложений, которые вам даны. Небольшое количество ошибочных вычислений следует ожидать даже в естественном тексте (поскольку люди несовершенны, а также парсер - он может не знаю, что слово X можно использовать в качестве глагола и только классифицировать его как существительное и т. д. и т. д.), но большинство моделей Маркова (если они не моделируют по существу ту же структуру грамматики, которую использует ваш парсер, и вы можете используйте несколько парсеров, чтобы попытаться противодействовать этому! -) приведет к тому, что VASTLY будет более ошибочным, чем даже дислексическим людям. Опять же, откалибруйте это на естественных и синтетических текстах, и вы увидите, что я имею в виду!)
Если вы пишете программу, которая генерирует вероятности перехода от марковского перехода из любой последовательности символов, а затем вычисляет скорость энтропии марковской матрицы. (см. http://en.wikipedia.org/wiki/Entropy_rate#Entropy_rates_for_Markov_chains). Это в основном оценка того, насколько легко можно предсказать текст, используя только цепь марков (более высокая энтропия означает труднее для прогнозирования). Поэтому я думаю, что чем ниже энтропия марковской матрицы, тем вероятнее, что образец текста контролируется марковской матрицей. Если у вас есть вопросы о том, как писать этот код, у меня, случается, есть программа на python, которая делает именно это на моем компьютере, поэтому я могу помочь вам
Мне нравится этот подход, но я думаю, что это было бы неоправданно вычислимым? – agiliq
Не видите, как, добавили некоторые детали ответа. – pufferfish