動機
字詞序列比詞數多帶資訊。成分結構描述句子如何由小片語組合,隱狀態模型描述未觀察類別如何產生詞元。兩者都把無限制的理解問題化成明確任務:解析器問文法允許哪些推導,HMM 問指定參數下的概率或最佳狀態路徑。任何一種答案都不自動等於完整意思。
歧義令這個區分重要。同一句可有多棵解析樹,多條狀態路徑也可解釋同一觀察。算法必須先決定是保留所有可能、把概率相加,還是只選最大者。交換這些運算會改變問題。動態規劃的用處,是許多候選解釋共享相同子問題,不必重算。
本節給有限模型,完整證明受限文法的 CKY,以及 HMM 前向與維特比(Viterbi)推理。
定義
定義 7.1.1
(上下文無關文法、解析樹與歧義)
上下文無關文法含有限非終結符 、終結詞彙 、起始符 及產生式。解析樹內節點按產生式展開,葉由左至右給詞元序列。語言中同一句若有兩棵以起始符 為根的不同解析樹,文法便有歧義;這關於結構解釋,不只是句子是否被接受。
定義 7.1.2
(Chomsky 範式與 CKY 圖表)
CKY 假設無空產生式、無單位產生式的 Chomsky 範式,每條是 或 。輸入非空 。空句或單位鏈要另擴充,不能直接套本遞推。令 包含恰可推導 的非終結符,兩端索引均包括在內。
定義 7.1.3
(隱馬爾可夫(Markov)模型、似然與維特比解碼)
HMM 有有限隱狀態 、初始概率 、轉移 ,以及有限詞彙上的發射概率 。、 每行和為一,且 。狀態轉移是一階 Markov,給定狀態後各發射條件獨立。路徑與觀察的聯合概率為:
這些獨立假設定義模型,並不是動態規劃推導出的現實性質。觀察似然把所有隱路徑的聯合概率相加;維特比則取最大。若觀察似然正,最大後驗路徑與最大聯合路徑相同,因各候選共享同一分母。
定理/命題
定理 7.1.4
(CKY 識別與解析重建)
先把所有有規則 的 放進 。按片段長遞增,若某切點 及規則 滿足 、,便把 加入 。最後 在格內,當且僅當它可推導該片段;句子合法當且僅當 。保存每個見證規則與切點,可用有限共享圖表表示全部解析樹。
定理 7.1.5
(前向相加與維特比取最大)
非空觀察序列的初值為 ,之後:
; 是長度 、末態 的路徑中最大聯合概率。故似然為 ,最佳路徑聯合值為 。記最大前驅即可重建一條最佳路;要全部同分路徑,須保留並列見證。
命題 7.1.6
(由標記計數得最大似然行)
固定狀態 ,設 為由 出發的轉移計數,總數 。在所有概率行 中,函數 (約定 )有唯一最大點 。發射行及初始分布用各自的計數,同樣方法最大化。
證明思路
證明
(對片段長度歸納)
CKY 對片段長歸納。單詞推導只能用詞彙規則,正是初值。較長樹的根必用 ,左子樹覆蓋一個非空前段,決定唯一切點,右子樹覆蓋餘段。歸納給兩子符號已在相應格,故插入 ,證完整。反過來,每次插入都有兩份較短合法推導,可接成根規則,證可靠。保存見證能重建樹,只保成員則只知存在。
證明透視
範式與片段次序用在哪裏
範式用了兩次。長度一的片段只能由詞彙規則推導,因為沒有空規則或單位規則;較長的片段必由二元規則推導,兩個子節點都非空,因此都嚴格較短。正是這種嚴格縮短,使對片段長度的歸納成立:每一格只依賴較短片段的格。
關鍵一步是切點 屬於見證的一部分。同一條根規則的不同切點給出不同的樹,所以遞推要遍歷所有 ;若只問存在,一個成功的切點已足夠。論證從兩個方向收尾:由推導經歸納得到圖表項目,由圖表項目又取得兩份較短推導並接合。
單位規則 會破壞這個次序,因為格 會依賴自己;若有 、 這樣的循環,同一片段更有無窮多棵樹。空產生式則允許子節點覆蓋零個詞元。兩者都需要明確擴充,如上文所說。
直接循環各二元規則、片段及切點,時間為 ,成員空間為 。回指數據可更大,逐棵列出所有樹的輸出甚至可指數多。多項式時間識別不表示解析棵數也是多項式。
證明
(按上一狀態分割路徑)
前向遞推把所有末態 的路徑按上一狀態 分成互斥情況。模型分解給前綴值乘轉移及本次發射,互斥情況再相加。對 歸納得每格意義,最後相加末態便恰數每路徑一次。
證明
(以較佳前綴取代前綴)
維特比固定最後兩態 ,各候選路徑共享同一非負末段因子,所以用末態 的最佳前綴取代較差前綴不會降低值。對 取最大,再對末態取最大,即得最優。記錄達到最大值的前驅,便能反向追索。此證明依賴末段只看 及當前詞,不能不加修改套到任意長程依賴模型。
概念視角算法
同一依賴圖回答兩個問題
前向與維特比都沿時間—狀態圖傳訊,乘法都用來延伸路徑。加法總計互斥解釋,最大值選一個解釋。因此把加法換成最大值,是把似然改成最佳路徑概率,不只是較快地計算同一答案。
稠密轉移下兩法運算量均為 。似然只要兩個長度 陣列;重建路徑須儲存指標或重算。長乘積會數值下溢,維特比可用對數並把零記為負無窮;前向則需縮放或 log-sum-exp,不能只取對數最大值,否則改變原來求和。
訓練若觀察到隱狀態,參數估計可直接推導。 是分開各序列計數的 到 轉移次數, 是 發射 的次數。完整數據似然分成多項分布因子,每行一個,所以每行可各自最大化。
證明
(最大化多項分布行)
記 ,並設 為任意概率行。 的項對目標貢獻為零,所以只有集合 有影響,而且要得到有限值,須在 上 。於是
這裏用了 ,且僅在 時取等號。全程取等號迫使 上 且 ,因此 以外 。故 是唯一最大點,零計數項在無平滑最優值為零。
整行零計數則不能由該似然識別,須另選政策,不能除零。狀態未見的學習需要後驗加權計數等另一程序,本節不聲稱已推導它。
證明透視
約束條件如何完結多項分布論證
除以 之後,兩個目標值之差成為 乘以以 為權的 之和,並逐項使用 。這是唯一用到的分析性質。它把上界化為 ,而這個量不大於 ,恰恰因為 是一行概率:完結論證的是這個約束,而不是拉格朗日(Lagrange)乘數法。計數為零的項不出現在目標中,所以求和只限於 ;若 在 之外放了質量,便有 ,不等式嚴格成立。 的等號條件於是迫使 ,即得唯一性。
例題詳解
例題 7.1.7
(小文法有兩種結構解釋)
規則 、,輸入 aaa。三個單詞格都有 S,兩個長二格也由唯一切點得 S。長三格有兩個見證:第一詞後切得 ,第二詞後切得 。同一格的成員 S 可代表兩棵樹。若要計數,把集合插入改為子樹計數乘積的總和,結果為二,而非把兩理由當一個。
例題 7.1.8
(似然與最佳路徑不同)
狀態 R,D,初值 ,轉移行 、。a 的發射率為 ,b 為 。觀察 ab,首步為 ;前向次步 ,似然 。維特比次步 ,最佳路 R,D,聯合值 ,後驗只有 。最佳單一解釋仍未必接近確定。
例題 7.1.9
(標記序列學習要保留邊界)
狀態 R,R,D,D,R,詞元 a,a,b,b,a。R 出發各有一次到 R、D,D 出發也各一次,所以轉移兩行均 。R 所見發射全為 a,D 全為 b,無平滑估計便為一或零。單序列初態全放 R。加入另一獨立序列要新增初態計數,不能在前序列末態與後序列首態間虛構轉移。
常見錯誤
反例模式
句子可識別,不代表解析唯一
接受 aaa,卻有前述兩種括法。格中只有一個 S 記存在,不記唯一。要分析歧義就保存見證或計數,不能把識別成功說成已選出正確意思。
常見錯誤
(把編號的 HMM 狀態當作文法類別)
HMM 狀態不必是人能解讀的文法類別,除非建模時明確如此設定。狀態只是模型中的索引,事後加上的名稱是詮釋,不是參數本身的性質。
常見錯誤
(逐時刻分別取最大)
逐時各選最大後驗狀態,也不是選整條最大聯合路徑;局部最喜歡的狀態之間甚至可能有零概率轉移。動態規劃保留跨時約束,局部選擇會丟掉它。
常見錯誤
(把成員資格當作概率,並忽略斷詞)
文法合法性與概率亦不同。多條推導不等於已有概率;加入規則概率須另定概率文法及任務。斷詞也是模型一部分,未見詞、標點、多詞表達不能假裝已在固定詞彙內。平滑可給未見事件正概率,但假設須與無平滑最大似然分開。
總結
CKY 按片段共享推導,以樹結構歸納證識別。HMM 按時間與末態共享前綴,加總得似然,取最大得最佳路徑。標記計數給明確多項分布估計,但零次數及序列邊界要另處理。這些方法精確解決有限指定任務,語義理解及更豐富模型仍未完成。
練習
練習 7.1.10
(對文法 ,用三個根切點計算 的解析數,並說明單一成員格為何不足以儲存這個數。)
核心
解答(3)
- 1
計算較短片段的解析數
設 為 的解析數,則 ,,。
- 2
對三個根切點求和
關鍵一步
。
依據: 根規則 把片段切在第一、二或三個詞元之後,而兩棵子樹可獨立選取。
- 3
與成員格比較
成員格只記 在格內,把五棵樹合成一個符號;計數或共享回指才能保留額外資訊。
練習 7.1.11
(列出兩狀態例題中觀察 的四條隱路徑聯合概率,並驗證似然及維特比的答案。)
核心
解答(3)
- 1
計算四個聯合概率
初值 ,轉移行 與 ,發射概率 、、、:
- 2
驗證似然與最佳路徑
總和為 ,最大值 在 。末態為 的路徑相加得 ,末態為 的得 ,與前向各項吻合。
- 3
解讀這兩個數
似然是所有解釋的總和,而最佳路徑的後驗為 。所以似然不能當作最佳單一解釋的概率。
練習 7.1.12
(某已標記語料中,由狀態 出發的轉移計數為 。求無平滑最大似然行。另一狀態的轉移計數為 時,可得甚麼結論?)
基礎
解答(3)
- 1
把已見計數正規化
總數為 ,所以最大似然行是 。
- 2
檢查零項
給未見的第三個轉移正概率,會削弱已見轉移可用的質量,降低無平滑似然。
依據: 把正概率給未見轉移,就要從已見轉移取走質量。
- 3
處理沒有觀察的行
全零行的似然因子對每個概率行都相同,數據不識別唯一值;先驗或平滑能選一個,但沒有任何特定的行可以單由這些計數推出。
練習 7.1.13
(某兩狀態模型的初始概率為 ,轉移矩陣為單位矩陣,兩個狀態都以概率一發射唯一的詞元 。對觀察 ,求似然、最佳聯合概率及最佳路徑數,並說明破同分指標保留甚麼。)
綜合
解答(3)
- 1
找出概率為正的路徑
路徑 與 各為 。交叉路徑 、 需要概率為零的轉移,所以概率為零。
- 2
計算三個量
似然為 ,最佳聯合值為 ,最大者有兩條。
- 3
說明指標
確定的破同分指標只返回其中一條合法最佳路徑;若不明確存下並列,另一個解釋就會丟失。