1. 首頁
  2. 問答
  3. Word預測算法

Word預測算法

2013-09-10 60 views
16

我確定有一篇關於此的文章，但我找不到一個問這個確切的問題。考慮以下幾點：Word預測算法

  1. 我們有可用的
  2. 單詞詞典，我們被送到的話很多段落，我希望能夠預測中給出該輸入句子的一個單詞。假設我們有幾句話，比如「你好，我的名字是湯姆」，「他的名字是傑瑞」，「他去沒有水的地方」。如果存在單詞，我們檢查一個哈希表。如果沒有，我們爲它分配一個唯一的ID並將其放入散列表中。通過這種方式，我們不必將單詞的「鏈」存儲爲一串字符串，而只需要一個uniqueID列表。以上，我們將有例如（0,1,2,3,4），（5,2,3,6）和（7,8,9,10,3,11,12）。請注意，3是「是」，我們在發現新單詞時添加了新的唯一標識。所以說我們被給了一句「她的名字是」，這將是（13，2，3）。鑑於這種情況，我們想知道下一個詞應該是什麼。這是我想到的算法，但我不認爲它是有效的：我不知道它的有效性： 3,6,2,7,8。
  3. 每條鏈的平均大小爲M，其中M爲平均句子長度
  4. 我們給出了一個新的鏈S， 13，2，3，我們希望知道最可能的下一個詞是什麼？

算法：

  1. 首先掃描鏈對於那些誰包含完整的S輸入的整個列表（13,2,3，在這個例子中）。由於我們必須掃描N個鏈，每個長度爲M，並且一次比較S個字母，因此它的O（N * M * S）。

  2. 如果在我們的掃描中沒有鏈具有完整的S，那麼通過刪除最不重要的單詞（即第一個，所以刪除13）進行下一次掃描。現在，在最壞的情況O（N * M * S）中掃描（2，3）爲1，這實際上是S-1。

  3. 繼續以這種方式掃描，直到我們得到的結果> 0（如果有的話）。

  4. 收集我們收集的所有剩餘鏈中的下一個單詞。我們可以使用一個哈希表，每次添加時都會計數，並跟蹤最多的單詞。 O（N）最差的情況下，O（1）找到最大的單詞。

  5. 找到的最大單詞是最有可能的，所以請將其退回。

每次掃描都需要O（M * N * S）最壞的情況。這是因爲有N個鏈，每個鏈有M個號碼，我們必須檢查S號來覆蓋匹配。我們掃描S次最壞的情況（13,2,3，然後2,3，然後3 3次掃描= S）。因此，總的複雜度是O（S^2 * M * N）。

所以，如果我們有10萬條鏈，平均句子長度爲10個單詞，我們正在尋找1,000,000 * S^2來獲得最佳單詞。顯然，N >> M，由於句子長度並不總是隨觀察句子數量成比例，所以M可以是一個常數。然後我們可以將複雜度降低到O（S^2 * N）。 O（S^2 * M * N）可能更有助於分析，因爲M可能是一個相當大的「常量」。

這可能是完全錯誤的方法來採取這種類型的問題，但我想分享我的想法，而不是公然要求幫助。掃描我的方式的原因是因爲我只想掃描儘可能多的東西。如果什麼都沒有完整的S，只是保持修剪S，直到一些鏈條匹配。如果他們從來不匹配，我們不知道下一個字是什麼預測！關於較少時間/空間複雜解決方案的任何建議？謝謝！

來源

2013-09-10 user2045279

+0

想到什麼閱讀您的問題後發現的是一個字短語/段落的基於後綴的數組。例如http://projectile.sv.cmu.edu/research/public/tools/salm/tutorial.pdf – hatchet

+0

我沒有直接的解決方案，但有一些很棒的閱讀：http：// en .wikipedia.org/wiki/N-gram http://www.codeproject.com/Articles/20423/N-gram-and-Fast-Pattern-Extraction-Algorithm http://aclweb.org/anthology-new/Q /Q13/Q13-1010.pdf –

回答

17

這是language modeling的問題。對於基線方法，唯一需要的是哈希表映射固定長度的單詞鏈，例如長度爲k，以最可能的後續單詞。（*）

在培訓時間，您打破使用滑動窗口輸入(k+1)-grams。所以，如果你遇到

The wrath sing, goddess, of Peleus' son, Achilles

你產生，爲ķ = 2，

START START the 
START the wrath 
the wrath sing 
wrath sing goddess 
goddess of peleus 
of peleus son 
peleus son achilles

這可以在線性時間內完成。對於每個3-gram，計數（在一個散列表中）第三個單詞跟隨前兩個單詞的頻率。

最後，循環遍歷散列表和每個鍵（2-gram）只保留最常出現的第三個單詞。線性時間。

在預測時間，只看（012）9（2）最後單詞並預測下一個單詞。這只是一個恆定的時間，因爲它只是一個哈希表查找。

如果你想知道爲什麼你應該只保留短鏈而不是完整的鏈，那麼看看Markov windows的理論。如果你的模型要記住它在輸入中看到的所有單詞鏈，那麼它的訓練數據就會非常糟糕，並且只能在預測時重現它的輸入。如何嚴重依賴於訓練集（更多數據更好），但對於k> 4，您確實需要在您的模型中使用smoothing。

（*）或概率分佈，但這不是您的簡單示例用例所必需的。

來源

2013-09-10 20:45:54

+0

啊，是的，我會過度訓練。因此，重申你所說的話，在3克的輸入上訓練，並找到最常見的下一個單詞。對於我們發現的每個密鑰（密鑰是2克），將散列值存儲爲最常見的第三個字。持續訓練能夠保存所遇到的所有單詞嗎？然後，每個2-gram可以包含2-gram之後的頂部T字的列表。我只是試圖想辦法不必重新訓練已經看到的輸入，並記住我們在2克後看到了多少前面的單詞。我想它是一個 – user2045279

+0

培訓時間與您想要使用多少存儲的問題。例如，你說10次觀察到「名字是約翰」，9次是「名字是彼得」。如果你用「彼得」再訓練兩句，現在彼得應該是最常見的。我們不知道這個，除非我們再訓練整套，因爲我們只儲存最常見的東西。你怎麼看？ – user2045279

+0

@ user2045279：對於在線培訓，您確實需要保留更多的信息，因此所有可能的結果都與他們的頻率相關，而不僅僅是最常見的結果。 –

相關問題

 相關問題