為甚麼要為文法加上概率?
同一個句子可能有多個合法的句法分析。前面的 CKY 表格能判斷分析是否存在,也能記錄不同的切分,但它本身不能衡量各個分析的相對權重。概率上下文無關文法(PCFG)給每條產生式賦予概率,進而給完整的分析樹賦權。這提供了明確的排序方法,卻不能保證得分最高的樹就是說話者原本的意思。
對同一個句子,我們將計算兩個不同的量:內部概率把所有分析樹的權重相加;維特比(Viterbi)概率取其中單棵最優樹的權重。前者衡量模型賦予整個觀測句子的概率,後者幫助我們選出一個分析。把求和換成取最大值,回答的問題就變了。
模型和條件
定義 32.1.1
(二元概率文法與樹的權重)
設非終結符集 、詞彙集 和帶標籤的產生式集合 都有限,起始符為 。推導樹在每個節點記錄所選規則的標籤:即使書寫的左右兩側相同,不同規則標籤仍算不同推導。每條規則形如 或 ,其中 ,。同一左側的規則概率非負且總和為一。在標記為 的每個節點,按照這些概率選擇規則;各節點使用獨立隨機抽取,抽取分布由該節點標記決定。有限分析樹的概率,亦即權重,是樹上所有規則概率的乘積。
局部概率歸一化並不保證生成過程最終停止。例如若 的概率為一,就永遠無法生成終結符句子。額外假設從 出發的過程幾乎必然終止,此時有限終結樹的總概率才是一。即使缺少此假設,下述有限表格仍給出指定有限句子的無條件概率;但只要存在正概率不終止,所有有限句子的概率之和就小於一。零權重規則可以省略。
定義 32.1.2
(內部值與維特比值)
對非空句子 、非終結符 及 ,令 為根為 、葉子恰好是 的所有有限樹的權重和,並令 為這類樹中單棵樹的最大權重;沒有這樣的樹時為零。句子的內部概率是 ,維特比概率是 。
記規則概率為 或 。內部值滿足
如果文法將同拼寫的詞彙規則用不同標籤表示,第一項就把它們的權重加起來。若區分節點符號與分支結構,但不區分書寫完全相同的規則標籤,可先把這些選項的概率相加,再用一條規則表示。終止模型賦予整個句子的概率為 ,不需要除以句長或分析數。
為甚麼遞推是正確的
定理 32.1.3
(內部概率遞推)
對於上述二元/詞彙規則文法和固定的非空句子,這個遞推恰好計算每個 所有對應分析樹的權重和。如果從起始符開始幾乎必然終止, 就是生成該句子的概率。
證明
(對跨度歸納)
對跨度歸納。跨度為一時,樹根必須使用一條詞彙規則;把所有匹配規則的概率相加便得到正確結果。對較長跨度,根必用某條二元規則 。兩個子樹都產生非空片段,因此左片段有唯一的結束位置 。反過來,一條根規則、一個切分以及左右子樹唯一確定一棵父樹。這樣的組合既不遺漏,也不重複。
根據歸納假設,左右子樹權重和已經正確。把兩者相乘,分配律便產生每一對左右子樹的權重乘積;再乘根規則概率,得到父樹的權重。對所有規則和切分求和,便得到全部父樹的權重和。固定 時,一棵二叉樹有 個葉節點和 個二元節點,因而只有有限個帶規則標記的推導,不涉及無窮求和交換。
證明透視
獨立性用在甚麼地方
證明用到三項事實,各用在一處。樹與它的組成(根規則、切分、左子樹、右子樹)之間的一一對應是關鍵一步;它要求每條規則都是二元或詞彙規則,使父節點恰有一個切分點。分配律再把兩個和的乘積化為對全部左右子樹配對的求和。生成模型只用在「樹的權重等於其規則概率之積」這一句,由各節點獨立選規則來保證。若規則選擇依賴整句之前的上下文,需要改變狀態或遞推;結論不能自動用於所有語言模型。若容許 與 這類一元規則,同一跨度就有無窮多棵樹,按跨度歸納便到不了基例。
最優樹與總概率
維特比值服從同一個遞推,只是把每個求和換成取最大值。詞彙基例對匹配規則取最大值,二元遞推為
空集合上的最大值按約定記為零。
定理 32.1.4
(帶回溯指標的維特比遞推)
對固定的非空句子,上述遞推計算 ,即根為 、覆蓋 的樹的最大權重(沒有樹時為零)。若 ,取達到最大值的規則與切分,並在左右子樹中遞歸地照做,便重建出權重為 的一棵樹。
證明
(獨立因子之積的最大值)
對跨度歸納。一個詞元的樹只含一條詞彙規則,所以最大權重就是匹配規則概率的最大值。對較長跨度,每棵樹都有根規則 、切分 、覆蓋 的左子樹 與覆蓋 的右子樹 ,其權重為 。固定規則與切分後, 與 的選擇互相獨立,且所有權重非負,所以 的最大值就是兩個最大值之積;由歸納假設,兩者分別是 與 。再對規則和切分取最大值,便得所述遞推。
若最大值為正,達到最大值的規則與切分滿足 且 。由歸納假設,兩個子片段各有達到相應權重的最優樹,在根規則下把它們合併,就得到權重為 的樹。
概念視角結構
同一個表格形狀,不同的運算
兩個表格的形狀都是 。內部表格在非負數上取 、;維特比表格取 、。上面兩個證明的差別,只在於乘法為何可以穿過 :對和有 ,對最大值,當 時有 。若把每條規則概率換成「真」, 換成「或」、 換成「且」,便得到 CKY 的識別表格,只記錄是否存在某棵樹。三個表格針對同一批樹回答三個不同的問題:總權重、最重的一棵,以及有沒有樹。
沿回溯指標可以恢復一棵最優樹。若有並列,可能有數棵同樣好的樹;保存所有最優見證才能恢復所有並列最優樹。數值零既可能表示無分析,也可能表示存在權重為零的合法分析;若要區分,應另存布林(Boole)表。
命題 32.1.5
(兩個表格的代價)
設句子有 個詞元, 與 分別為二元規則與詞彙規則,並假設算術運算成本為常數。直接遍歷規則時,至多計算 個「規則加切分」項與 個詞彙項,所以時間為 。數值表格有 個格子,即 。
證明
(數算跨度與切分)
格子 ()有 個可能的切分 ,每條二元規則對每個切分給出一項。令 ,長度為 的格子有 個,故「規則加切分」項的個數為 。 個單詞元格子各把每條詞彙規則檢查一次。表格對每個非終結符和每個跨度 各有一個格子,跨度共有 個。保存全部回溯指標可能比數值表格需要更多空間。
例題
例題 32.1.6
(三個詞元的兩個分析)
設 概率為 , 概率為 。此分支過程幾乎必然終止:終止概率 是 中方程 的最小解,即 。解釋最小根:設 為所有分支在深度 前停止的概率,從 出發,遞推 遞增並趨於終止概率;它始終不超過任何非負不動點。aaa 的兩種括號結構是 和 。每棵樹都使用兩條二元規則、三條詞彙規則,權重為 。故 ,而 ;兩棵樹都是維特比解。總概率更大,是因為兩種推導是不同事件。
例題 32.1.7
(為兩個權重不等的分析填寫兩個表格)
取產生式 (概率 )、(概率 ),以及 、、、、(概率均為 )。對句子 abc,單詞元格子為 ,其他非終結符均為零。長度為二時,,;維特比值相同。其餘長度為二的格子全為零。特別地, 在 ab 上的格子為零: 需要單獨一個 a 構成 , 需要單獨一個 b 構成 ,兩者都不可能。所以 ab 是一個 ,卻不是 ;這個零來自缺少分析,而不是規則權重為零。
對整個句子,規則 在切分 處貢獻 , 在切分 處貢獻 。因此 ,,回溯指標為 ,對應的樹是 。給定句子時這棵樹的條件概率為 。內部值 與模型一致:abc 是唯一概率為正的句子。
例題 32.1.8
(下溢與 log-sum-exp 一步)
設一個長句子恰有兩個分析,權重分別為 與 。兩個數都小於雙精度可表示的最小正數,直接連乘會下溢成零,表格便無法區分它們。取對數後,第一個權重是 ,第二個是 。維特比值取較大者,即 。內部值需要求和:。若以最大值代替 log-sum-exp,會報告 ,把內部概率低估了 倍。
常見錯誤與細微之處
反例模式
最重的樹不一定屬於概率最大的句子
論斷:最優分析樹較重的句子,就是概率較大的句子。取 與 (概率各 )、(概率 ),以及 、、、、、(概率均為 )。同一左側的規則概率和為一,每個推導兩層改寫後即停止,所以有限樹的總權重為 。句子 ab 有兩棵樹 與 ,權重各為 ,故 ,。句子 cd 只有一棵樹 ,權重 ,故 。維特比值把 cd 排在前面,但兩句的概率是 與 ,概率較大的是 ab。比較句子必須用內部概率;維特比只用來為給定句子選一棵樹。
在已經觀察到句子的條件下,某棵樹的後驗概率等於該樹權重除以 ,前提是分母為正。它不同於維特比表給出的聯合權重。在上面的反例中,ab 的兩棵樹條件概率各為 ;若句子概率為零,這個條件式無定義。實際計算中,許多小概率相乘可能下溢;取對數可把乘法變成加法,但求和時需要穩定的 log-sum-exp,而不是簡單取最大值。
常見錯誤
(數算詞語,而不是數算推導)
對文法 (概率 )、(概率 )中的 aaa,括號結構 與 給出同一個詞串,容易把它們算作一個分析,報告 。它們是兩棵不同的樹,所以內部概率是 。求和是對推導進行,不是對不同的詞串進行。
常見錯誤
(局部歸一化不等於會終止)
取 概率 、 概率 。左側為 的規則概率和為一,但有限樹的總權重只有 (即 的較小根),所以由表格得到的各句子概率之和是 ,不是 。把每組規則各自歸一化,並不能使整個生成過程成為有限句子上的概率分布。
練習
快速檢查
(對文法 (概率 )、(概率 ),求 和 aaaa 的總概率,並解釋後者根節點的三種切分。)
記 個 a 的內部值為 ,並對各切分長度求和。
解答 · 答案
兩個詞元只有一棵樹,其權重為 。四個詞元的根切分長度分別是 ,所以
也可數出五棵二叉樹,每棵有三條二元規則和四條詞彙規則,權重各為 。
快速檢查
(一個句子恰有兩棵正權重分析樹,權重為 和 ,沒有其他分析。求內部值、維特比值,以及給定句子後第二棵樹的後驗概率。)
一個用求和,一個用取最大值,再以樹權重除以內部值。
解答 · 答案
內部值為 ,維特比值為 。給定句子,第二棵樹的概率為 。最大值與總和回答不同問題。
快速檢查
(若 概率為 , 概率為 ,求 在 中的最小解。為甚麼局部歸一化不能保證幾乎必然終止?)
整理成二次方程,找出不等於 的根。
解答 · 答案
方程的兩個解為 和 ,因此終止概率是較小的 。雖然每個節點的選項概率加起來是一,仍有 的概率產生無限推導。局部歸一化只規定每一步的選擇,不能證明整個過程停止。
快速檢查
(在 abc 例題的文法中,把 與 的概率改為 與 。求頂層格子的內部值、維特比值與回溯指標。)
只有頂層的兩項改變;長度為二的各項不變。
解答 · 答案
在切分 的項為 , 在切分 的項為 。內部值為 ,維特比值為 ,回溯指標為 ,對應的樹是 。最優樹的條件概率為 。