關於使用馬爾可夫鏈算法生成文本

Question

我正在閱讀Brian W. Kernighan和Rob Pike編寫的「編程實踐」一書。第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

我相信這是NLP中的一個嚴重問題，沒有一個簡單的解決方案。一種方法是除了實際詞語之外還標記詞類，以概括映射。使用詞性，如果詞序列沒有先例，程序至少可以預測詞類W2和W3後面的詞類。 「一旦對訓練樣例進行了映射，我們就可以在這些訓練樣例上訓練一個標記模型，給定一個新的測試語句，我們就可以從模型中恢復標籤序列，並且可以直接識別由模型。」從哥倫比亞notes。

Answer 3

您所描述的情況考慮了3-grams，即給定數據集中三元組的統計頻率。要創建一個沒有adsorbing states的馬爾可夫矩陣，那麼在f_2(w1,w2) -> w3和f_2(w2,w3) = 0沒有哪個點，你將不得不擴展可能性。廣義擴展@ ThomasW的答案是：

1. 如果從
2. 該組預測f_2(w1,w2) != 0戰平如果從
3. 該組預測f_1(w2) != 0戰平如果從

該組預測 f_0() != 0平局

也就是說，通常從3克集合中抽取，而不是2克集合比1克集合。在最後一步，您只需根據統計頻率隨機抽取一個詞。