8、概率句法分析ppt課件

1、概率句法分析,徐志明 哈工大語言技術(shù)中心,語言的描述,語言的描述 統(tǒng)計(jì)學(xué)的方法： 語言是個(gè)概率分布。 構(gòu)造概率模型，描述語言句子的概率分布。 例如：n-gram模型、HMM。 代數(shù)學(xué)的方法 語言是一個(gè)句子集合。 定義一種文法，它可推導(dǎo)出該語言的所有句子。 通過能否推導(dǎo)出完整的句法分析樹，判斷句子的合法性。 上述兩種方法結(jié)合 概率文法：將概率引入到語言文法中，分析句子的句法結(jié)構(gòu)。 用概率指導(dǎo)句法結(jié)構(gòu)歧義的消解。,語言文法,語言文法： 四元組：G=(VN ,VT ,R,S) VN：非終結(jié)符的集合，表示句子結(jié)構(gòu)分析的中間成分 VT ：終結(jié)符的集合，相當(dāng)于詞匯表。 R ：規(guī)則集 ：基本形式：。其中：

2、， 。 S ：初始符號，代表語言的句子。 例如：句子：The man ate the apple.,文法的類型,0型 短語文法 1型 上下文有關(guān)文法 2型 上下文無關(guān)文法 3型 正則文法,文 法 類 型,逐 漸 增 加 限 制,如果文法是正規(guī)文法 一定也是上下文無關(guān)文法,語言學(xué)家Chomsky把文法分成以下四種類型：,逐 次兼容,文法的類型,0-型（無約束文法） 無限制 1-型（上下文相關(guān)文法） A 2-型（上下文無關(guān)文法） A 3-型（正則文法） A aB A a,上下文無關(guān)文法,上下文無關(guān)文法 (Context Free Grammar，CFG) 四元組：G=(VN ,VT ,R,S) V

3、N：非終結(jié)符的集合 VT ：終結(jié)符的集合。 R ：規(guī)則集。基本形式： 。其中： ， 。 S ：初始符號。 概率上下文無關(guān)文法(Probabilistic Context Free Grammar，PCFG) 將概率引入到CFG文法中。 每條規(guī)則 ，附帶一個(gè)概率值 。 約束：,PCFG：例子,句法分析,句法分析(Parsing) 和句法分析器(Parser) 任務(wù)： 詞序列 句法分析樹。 本質(zhì)：線性序列 非線性序列。 動機(jī)：自然語言是一種非線性的符號序列。句子結(jié)構(gòu)表現(xiàn)為復(fù)雜的嵌套性，而N-gram和HMM只能處理線性序列。 句法分析例子： 輸入句子：I saw the dog with the

4、telescope. 輸出該句子的句法分析樹,I saw the dog with the telescope. ,Parsing,CFG：句法分析樹表示,(S (NP (Pro I) (VP (VP (V saw) (NP (Det the) (N dog) (PP (P with) (NP (Det the) (N telescope),句法分析模型,Parser Model 計(jì)算句法分析樹概率： 。 計(jì)算句子概率： 句法歧義消解：選擇概率最大的句法分析樹：,句子概率=各種句法分析樹的概率之和,句法分析樹概率計(jì)算,句法分析樹概率=該分析樹上的所有規(guī)則概率之積。 句子概率=該句子的各種句法分

5、析樹的概率之和。,句法分析樹：假設(shè),位置無關(guān) 子樹的概率與構(gòu)成子樹所在的位置無關(guān)。 類似于HMM中的時(shí)間無關(guān)。 上下文無關(guān) 子樹的概率與子樹以外的詞無關(guān)。 祖先無關(guān) 子樹的概率與子樹以外的節(jié)點(diǎn)無關(guān)。,PCFG規(guī)則概率估計(jì),語言學(xué)文法 構(gòu)造CFG。編寫語言規(guī)則。 語料庫建設(shè) 建立基于CFG的句法樹庫(Tree Bank)： 帶有句法標(biāo)注的語料庫。 句法分析樹的集合。如Pen Tree Bank 文法訓(xùn)練：規(guī)則概率 對于規(guī)則 ，在樹庫上統(tǒng)計(jì)該規(guī)則及其非終結(jié)符A的頻度。 然后可估計(jì)規(guī)則概率 應(yīng)用： 應(yīng)用概率Parser進(jìn)行句法分析。,PCFG規(guī)則概率估計(jì)例子,S NP VP,3,2,6,1,3,1,

6、2,NP Pro,NP Det N,NP NP PP,VP V NP VP VP PP PP P NP,PCFG：規(guī)則的頻度統(tǒng)計(jì),S NP VP,3,2,6,1,3,1,2,NP Pro,NP Det N,NP NP PP,VP V NP VP VP PP PP P NP,/ 3 = 1.0,/ 9 = 0.22,/ 9 = 0.67,/ 9 = 0.11,/ 4 = 0.75,/ 4 = 0.25,/ 2 = 1.0,PCFG：規(guī)則的概率估計(jì),句法分析的難點(diǎn),句法分析的難點(diǎn)： 句法歧義：一個(gè)句子對應(yīng)著幾種可能的句法分析結(jié)果（多顆句法分析樹） 句法分析的核心任務(wù)是消解句子在句法結(jié)構(gòu)上的歧義。,

7、符號注釋,一些符號的注釋 句子 句法分析樹：T 文法G =(VN ,VT ,R,S) 假設(shè)文法G的規(guī)則 形式只有兩種形式： 可以通過范式化處理，使CFG 規(guī)則滿足上述形式。,PCFG的三個(gè)基本問題,與HMM相似，PCFG也有三個(gè)基本問題。 問題1： 給定文法G，計(jì)算由G生成句子S 的概率 ？ 問題2： 尋找句子S最優(yōu)句法分析樹? 問題3： 如何從語料庫W中訓(xùn)練G的概率參數(shù),使得P(W|G)最大 模型參數(shù)訓(xùn)練問題,問題1&2,思路 采用動態(tài)規(guī)劃算法，將句法分析樹的概率計(jì)算轉(zhuǎn)換成句法分析樹的子樹的概率計(jì)算。,問題1：向內(nèi)算法,向內(nèi)變量 非終結(jié)符A的內(nèi)部概率（Inside probability）（

8、可理解成子樹概率）。根據(jù)文法G從A推出詞串 的概率。,問題1：向內(nèi)概率公式,獨(dú)立性假設(shè),P(A,B|C) = P(A|B,C)P(B|C),問題1：向內(nèi)算法（自下向上）,輸入： 文法G，句子 輸出： 算法： 1、初始化： 2、歸納計(jì)算：j從1到n，i從1到n-j，重復(fù)下面計(jì)算 3、結(jié)束：,詞性概率,句法子樹概率,句子生成概率,問題1：向內(nèi)算法計(jì)算示例,SNP VP 1.0NPNP PP 0.4 PPP NP 1.0NPJohn 0.1 VPV NP 0.7NPbone 0.18 VPVP PP 0.3NPstar 0.04 Pwith 1.0NPfish 0.18 Vate 1.0NPtele

9、scope 0.1,問題1：向內(nèi)算法計(jì)算示例,1,2,3,4,5,6,7,初始化,8,9,10,11,i,j,問題2： Viterbi 算法,輸入：文法G，句子 輸出：t* (S在G下最優(yōu)句法分析樹) 算法： 1、初始化 2、動態(tài)規(guī)劃：j從1到n,i從1到n-j,重復(fù)如下步驟 3、結(jié)束 t*的根節(jié)點(diǎn)為S（文法開始符號）；從 開始回溯，得到S的最優(yōu)樹結(jié)構(gòu) 記錄了非終結(jié)符及其統(tǒng)攝的起止位置,Viterbi算法示例,問題3： 參數(shù)訓(xùn)練問題,從樹庫直接統(tǒng)計(jì)Treebank Grammar 最大似然估計(jì) 依賴于艱巨的工程：樹庫建設(shè) 向內(nèi)向外算法 無監(jiān)督學(xué)習(xí) 迭代過程 與初始參數(shù)相關(guān),問題3：向外算法,向

10、外變量 非終結(jié)符A的外部概率（Outside probability） 根據(jù)文法G從A推出詞串 的上下文的概率，記為：,問題3：向外算法（自下向上）,輸入： 文法G，句子 輸出： 算法： 1、初始化： 2、歸納計(jì)算：j從n -1到0，i從1到n-j，重復(fù)下面計(jì)算,計(jì)算外部概率示例（自頂向下）,問題3：向內(nèi)向外算法規(guī)則使用次數(shù)的數(shù)學(xué)期望,統(tǒng)計(jì)經(jīng)過三點(diǎn),規(guī)則概率重估公式,向內(nèi)向外算法,EM算法運(yùn)用于PCFG的參數(shù)估計(jì)的具體算法。 初始化：隨機(jī)給P(A-) 賦值，使得P(A- ) =1.由此得到語法G0. iBC) 和C(A-a) M步驟：用E-步驟所得的期望值,利用: 重新估計(jì)P(A-) ,得到語

11、法Gi+1 循環(huán)計(jì)算:i+,重復(fù)EM步驟,直至P(A-)收斂.,PCFG的優(yōu)缺點(diǎn),優(yōu)點(diǎn) 可以對句法分析的歧義結(jié)果進(jìn)行概率排序 提高文法的容錯(cuò)能力（robustness） 缺點(diǎn) 沒有考慮詞對結(jié)構(gòu)分析的影響 沒有考慮上下文對結(jié)構(gòu)分析的影響 許多當(dāng)前的獲得較高精度的句法分析系統(tǒng)以PCFG為基礎(chǔ),基于CFG規(guī)則的分析方法,基于CFG規(guī)則的分析方法： 1.CYK算法； 2.移進(jìn)歸約算法； 3.Marcus確定性分析算法； 4.Earley算法； 5.Tomita算法（GLR算法、富田算法）； 6.Chart算法（圖分析算法、線圖分析算法）；,句法分析策略,句法分析通常采用的策略有： 自頂向下分析法； 自

12、底向上分析法； 左角分析法； 其他策略。,1 線圖分析算法,(1) S NP VP (2) NP N (3) NP CS 的 (4) VP V NP (5) CS NP V (6) V V V,我是縣長派來的 蒼蠅是瞎子打死的 主意是董永想出來的 N V N V V 的,線圖結(jié)構(gòu)圖示,1,2,3,4,5,6,0,N,N,V,V,V,的,我 是 縣長 派 來 的 蒼蠅 是 瞎子 打 死 的 主意 是 董永 想 出來 的,V,CS,NP,VP,S,線圖 Chart,NP,NP,基本概念：線圖/chart,線圖是一組節(jié)點(diǎn)(node)和邊(edge)的集合 節(jié)點(diǎn)：對應(yīng)著輸入字符串中的字符間隔 邊： 其

13、中標(biāo)記為非終結(jié)符或終結(jié)符 問題： 如何從輸入串開始，一步步形成chart，使得存在一條邊可以覆蓋全部節(jié)點(diǎn)，并且邊上標(biāo)記為S？,Chart的另一種表示形式,“邊”的起始位置,邊的終止位置,“邊”上的標(biāo)記,Chart算法的基本數(shù)據(jù)結(jié)構(gòu),1) chart edgei i=1,2, edge := 2) agenda 棧（stack）結(jié)構(gòu)，存放等待加入到chart中的邊（edge） 3) active arc 存放當(dāng)前分析狀態(tài)，狀態(tài)由三部分組成,Chart算法的過程描述,將待分析字符串w置入輸入緩沖區(qū)，agenda清為空棧； 循環(huán)，反復(fù)執(zhí)行下面步驟，直至輸入緩沖區(qū)和agenda均為空 若agenda為

14、空，則從輸入緩沖區(qū)取一個(gè)字符，并把該字符及其起止位置(P1, P2)推入agenda棧； 從agenda中彈出棧頂?shù)倪?，該邊的起止位置?P1, P2), 邊上標(biāo)記為L； 檢查規(guī)則集中的規(guī)則，對所有形如AL 這樣的規(guī)則，在active arc集合中增加一條起止位置為P1, P2，弧上為AL 這樣的點(diǎn)規(guī)則； 把從agenda中彈出的標(biāo)記為L的邊，加入到chart中的P1, P2之間； 檢查所有active arc，如果存在起止位置為P0, P1，且弧上點(diǎn)規(guī)則為A L 的active arc，就增加一條新的active arc，起止位置為P0, P2，弧上點(diǎn)規(guī)則為A L 如果一條active ar

15、c（起止位置為P0, P2）上點(diǎn)規(guī)則形如A L （點(diǎn)號在規(guī)則最右端），就將起止位置為P0, P2，邊上標(biāo)記為A的邊壓入agenda棧。,Chart算法分析示例,1,2,3,4,5,6,0,chart active arc,輸入緩沖區(qū),agenda,Chart算法分析示例（續(xù)）,agenda,輸入緩沖區(qū),chart,active arc,(0,1) NP,Chart算法分析示例（續(xù)）,agenda,輸入緩沖區(qū),N,NP N ,CSNP V ,S NP VP,NP,Chart算法分析示例（續(xù)）,agenda,輸入緩沖區(qū),N,NP N ,S NP VP,NP,V,VP V NP,V V V,CSNP

16、 V ,(1,3) VP,Chart算法分析示例（續(xù)）,agenda,輸入緩沖區(qū),(0,3) S,N,NP N ,S NP VP,NP,V,VP V NP,V V V,N,NP N ,S NP VP,NP,VP,VP V NP ,S NP VP ,S,CSNP V ,CSNP V ,Chart算法分析示例（續(xù)）,agenda,輸入緩沖區(qū),(3,4) V,N,NP N ,S NP VP,NP,V,VP V NP,V V V,N,NP N ,S NP VP,NP,VP,VP V NP ,S NP VP ,S,V,VP V NP,V V V,CSNP V ,CSNP V ,Chart算法分析示例（續(xù)

17、）,agenda,輸入緩沖區(qū),(4,5) V,N,NP N ,S NP VP,NP,V,VP V NP,V V V,N,NP N ,S NP VP,NP,VP,VP V NP ,S NP VP ,S,V,VP V NP,V V V,V,VP V NP,V V V,V V V ,CSNP V ,CSNP V ,Chart算法分析示例（續(xù)）,agenda,輸入緩沖區(qū),(3,5) V,N,NP N ,CSNP V ,S NP VP,NP,V,VP V NP,V V V,N,NP N ,CSNP V ,S NP VP,NP,VP,VP V NP ,S NP VP ,S,V,VP V NP,V V V,

18、V,VP V NP,V V V,V V V ,V ,CSNP V ,Chart算法分析示例（續(xù)）,agenda,輸入緩沖區(qū),(2,5) CS,N,NP N ,CSNP V ,S NP VP,NP,V,VP V NP,V V V,N,NP N ,CSNP V ,S NP VP,NP,VP,VP V NP ,S NP VP ,S,V,VP V NP,V V V,V,VP V NP,V V V,V V V ,V ,CSNP V ,CS,NPCS 的,Chart算法分析示例（續(xù)）,agenda,輸入緩沖區(qū),(5,6) 的,N,NP N ,CSNP V ,S NP VP,NP,V,VP V NP,V V

19、 V,N,NP N ,CSNP V ,S NP VP,NP,VP,VP V NP ,S NP VP ,S,V,VP V NP,V V V,V,VP V NP,V V V,V V V ,V ,CSNP V ,CS,NPCS 的,的,NPCS 的 ,Chart算法分析示例（續(xù)）,agenda,輸入緩沖區(qū),N,NP N ,CSNP V ,S NP VP,NP,V,VP V NP,V V V,N,NP N ,CSNP V ,S NP VP,NP,VP,VP V NP ,S NP VP ,S,V,VP V NP,V V V,V,VP V NP,V V V,V V V ,V ,CSNP V ,CS,NPCS 的,的,NPCS 的 ,NP,VP,S,Chart算法分析示例（續(xù)）,agenda,輸入緩沖區(qū),N,NP N ,CSNP V ,S NP VP,NP,V,VP V NP,V V V,N,NP N ,CSNP V ,S NP VP,NP,VP V NP ,S NP VP ,V,VP V NP,V V V,V,VP V NP,V V V,V V V ,V ,CSNP V ,CS,NPCS 的,的,NPCS 的 ,NP,VP,S,淺層