識別Markov生成內容的算法？

Question

馬爾可夫鏈是一種（幾乎標準的）生成random gibberish的方式，對於未經過訓練的人來說，這看起來很聰明。如何從人類書面文本中識別馬爾科夫生成的文本。

如果你指出的資源是Python友好的，那將是非常棒的。

Answer 1

你可以使用「蠻力」的方法，因此你比較產生語言上收集的n-gram的更高的數據比生成它的馬爾科夫模型更有序。

即如果有一個2階馬爾可夫模型生成的語言，高達3克，將有正確的頻率，但4 - 克可能不會。

您可以從起牀到5克的頻率，谷歌的公共n-gram dataset.這是巨大的，但 - 24G 壓縮 - 你需要通過郵寄得到它在DVD上從LDC。

編輯：增加了一些實施細節

的正克已經被計算在內，所以你只需要計數（或頻率）存儲的方式，可以快速地搜索。一個正確索引的數據庫，或者一個Lucene索引應該可以工作。

給出一段文字，通過它掃描和查找各5克的頻率數據庫，並看到它躋身相比，同爲4個字啓動其他5克。

實際上，更大的障礙可能是數據集的許可條款。將其用於商業應用可能會被禁止。

Answer 2

如果您有幾個大的馬爾科夫生成的文本，您可以通過比較每個樣本之間的詞頻來確定它們是如此。由於馬爾可夫鏈依賴於不變的詞概率，任何給定詞的比例應該大體上等於樣本之間的比例。

Answer 3

一個簡單的方法是讓一大羣人爲你閱讀輸入文本，看看文本是否有意義。我只是半開玩笑，這是一個棘手的問題。

我認爲這是一個難題，因爲馬爾可夫鏈生成的文本在詞頻排序和單詞排序之間的簡單關係方面具有很多與真實人類文本相同的屬性。

由馬爾可夫鏈生成的真實文本和文本之間的差異是語法的高級規則和語義含義，這很難以編程方式進行編碼。另一個問題是馬爾可夫鏈在生成文本時足夠好，以至於他們有時會提供語法和語義上正確的語句。

作爲一個例子，這裏是一個aphorism from the kantmachine：

今天，他會覺得確信 人的意志是自由的;明天，考慮到 性質的不解鏈，他會將自由看作是一種幻想，並宣稱自然是總體上的 。

雖然這個字符串是由計算機程序編寫的，但很難說人不會說這個。

我認爲，除非您能給我們提供關於計算機和人類生成文本的更多具體細節，揭示更明顯的差異，否則使用計算機編程將很難解決此問題。

Answer 4

衆包。使用Mechanical Turk並讓一些人對此進行投票。甚至有一些圖書館可以幫助你解決這個問題。例如：

• TurKit - Iterative Tasks on Mechanical Turk

下面是來自O'Reilly的雷達博客文章上使用訣竅的Mechanical Turk來完成您的工作：

• Mechanical Turk Best Practices

Answer 5

我建議埃文的答案的概括：做一個你自己的馬爾可夫模型，並用大量的訓練（非常大）的樣本，保留樣本的其餘部分作爲「測試數據」。現在，看看您訓練的模型在測試數據上的表現如何，例如用卡方檢驗來表明「適合太好」的情況（表明測試數據確實是由該模型產生的）以及適合度非常差的情況（表明模型結構中存在錯誤 - 超過在這種情況下，錯誤結構的訓練模型會出現糟糕的工作）。

當然，還有很多校準問題，比如模型的結構 - 您懷疑一個基於Ntuples的單詞和更多的簡單模型，還是更復雜的語法狀態等等。幸運的是，您可以通過使用已知自然文本的大型語料庫以及使用各種結構模型自行生成的語料來很好地校準事物。

另一種方法是使用nltk來解析給出的句子 - 甚至在自然文本中也會出現少量錯誤解析（因爲人類並不完美，解析器也是如此 - 它可能會不知道單詞X可以用作動詞，只將它分類爲名詞等等），但是大多數馬爾可夫模型（除非它們本質上建立了語法分析器正在使用的相同語法結構 - 而且可以使用幾個解析器來嘗試和抵消這個問題！）會導致比誦讀困難的人更多的錯誤解析。再次，校準是天然VS合成的文本，你會明白我的意思 - - ！）

Answer 6

如果您編寫一個程序，可以從任意符號序列生成馬爾可夫轉移概率，然後計算馬爾可夫矩陣的熵率。 （參見http://en.wikipedia.org/wiki/Entropy_rate#Entropy_rates_for_Markov_chains）這基本上是使用馬爾可夫鏈可以輕鬆預測文本的估計值（較高的熵意味着較難預測）。因此，我認爲馬爾可夫矩陣的熵越低，文本樣本受馬爾可夫矩陣控制的可能性就越大。如果您有關於如何寫這個代碼的問題，我正好在Python這正是這一點在我的電腦上有一個程序，所以我可以幫你