Об использовании алгоритма цепи Маркова для генерации текста

Question

Я читаю книгу «Практика программирования» Брайана У. Кернигана и Роб Пайка. Глава 3 содержит алгоритм цепного подхода Маркова, который считывает исходный текст и использует его для создания случайного текста, который «читает хорошо» (что означает выход ближе к собственно звучащий по-английски, чем бред):

set w1 and w2 to the first two words in the source text 
print w1 and w2 
loop: 
    randomly choose w3, one of the successors of prefix w1 and w2 in the source text 
    print w3 
    replace w1 and w2 by w2 and w3 
    repeat loop 

Моих вопрос: каков стандартный способ справиться с ситуацией, когда новые значения для w2 и w3 не имеют преемника в исходном тексте?

Большое спасибо заранее!

Answer 1

Вот ваши варианты:

1. Выберите слово случайным образом? (Всегда работает)
2. Выберите новый W2 в случайном порядке? (Возможно, все еще петля)
3. Назад к предыдущим W1 и W2? (Может быть, все еще петля)

Я бы, вероятно, пошел с попыткой № 2 или № 3 один раз, а затем вернуться к # 1 - который всегда будет работать.

Answer 2

Я считаю, что это серьезная проблема в НЛП, без прямого решения. Один из подходов состоит в том, чтобы пометить части речи в дополнение к фактическим словам, чтобы обобщить отображения. Используя части речи, программа может, по крайней мере, предсказать, какая часть речи должна следовать за словами W2 и W3, если нет прецедента для последовательности слов. «После того, как это сопоставление было выполнено на примерах обучения, мы можем обучить модель меток на этих примерах обучения. С учетом нового тестового предложения мы можем восстановить последовательность тегов из модели, и нетрудно идентифицировать объекты, идентифицированные модель." Из Колумбии notes.

Answer 3

Ситуация, которую вы описываете, учитывает 3-grams, то есть статистическую частоту 3-х кортежей в данном наборе данных. Чтобы создать матрицу Маркова без adsorbing states, это не точки, где f_2(w1,w2) -> w3 и f_2(w2,w3) = 0, вам придется расширить возможности. Обобщенный расширение @ ThomasW ответов будет:

1. Если множество предсказатель f_2(w1,w2) != 0 извлечь из этого
2. Если множество предсказатель f_1(w2) != 0 извлечь из этого
3. Если множество предсказателя f_0() != 0 извлечь из этого

То есть нарисуйте, как обычно, из 3-граммового набора, чем 2-граммовый набор, чем набор из 1 грамма. На последнем шаге вы просто будете рисовать слово в случайном порядке, взвешенное его статистической частотой.