自然語言處理講座第七章-句法分析技術(shù)課件

第七章句法分析技術(shù)第七章句法分析技術(shù)1什么是句法分析判斷輸入的詞序列能否構(gòu)成一個(gè)合乎語法的句子，確定合乎語法句子的句法結(jié)構(gòu)運(yùn)用句法規(guī)則和其他知識(shí)將輸入句子中詞之間的線性次序，變成一個(gè)非線性的數(shù)據(jù)結(jié)構(gòu)（例如短語結(jié)構(gòu)樹或有向無環(huán)圖）什么是句法分析判斷輸入的詞序列能否構(gòu)成一個(gè)合乎語法的句子，確2為什么要進(jìn)行句法分析例一：音字轉(zhuǎn)換例一只小花貓例二：機(jī)器翻譯例（PrepositionalPhraseAttachment）JanhitthegirlwithlonghairJanhitthegirlwithahammer例三：信息檢索例哪個(gè)球隊(duì)獲得了亞洲杯冠軍？日本隊(duì)擊敗中國隊(duì)獲得亞洲杯冠軍為什么要進(jìn)行句法分析例一：音字轉(zhuǎn)換例3句法分析的難點(diǎn)句法分析的難點(diǎn)：語法歧義：一個(gè)句子對(duì)應(yīng)著幾種句法分析結(jié)果“咬死了獵人的狗”“那只狼咬死了獵人的狗”“那只咬死了獵人的狗失蹤了”漢語句法分析的獨(dú)特性（朱德熙《語法答問》《語法講義》）漢語沒有形態(tài)語序靈活詞類和句法成分不存在一一對(duì)應(yīng)的關(guān)系漢語句子的構(gòu)造原則與詞組的構(gòu)造原則基本上是一致的漢語語法形式化工作滯后深層分析與淺層分析句法分析的難點(diǎn)句法分析的難點(diǎn)：4句法分析系統(tǒng)一個(gè)句法分析系統(tǒng)通常由兩部分組成形式語法體系匹配模式短語結(jié)構(gòu)語法擴(kuò)充轉(zhuǎn)移網(wǎng)絡(luò)樹鄰接語法(TAG)基于合一運(yùn)算的語法（廣義短語結(jié)構(gòu)語法、詞匯功能語法、功能合一語法、基于中心詞驅(qū)動(dòng)的短語結(jié)構(gòu)語法(HPSG)）基于詞的語法（鏈語法、依存語法、配價(jià)語法）分析控制機(jī)制模式匹配技術(shù)基于短語結(jié)構(gòu)語法分析算法（厄爾利（Earley）分析算法、富田勝（Tomida）分析算法、線圖（Chart）分析算法、確定性分析算法等等）基于擴(kuò)充轉(zhuǎn)移網(wǎng)絡(luò)的分析算法鏈分析算法句法分析系統(tǒng)一個(gè)句法分析系統(tǒng)通常由兩部分組成5概率上下文無關(guān)文法（Probabilistic(Stochastic)ContextFreeGrammar）隨機(jī)上下文無關(guān)語法可以直接統(tǒng)計(jì)語言學(xué)中詞與詞、詞與詞組以及詞組與詞組的規(guī)約信息，并且可以由語法規(guī)則生成給定句子的概率。定義：一個(gè)隨機(jī)上下文無關(guān)語法（PCFG）由以下5部分組成：（1）一個(gè)非終結(jié)符號(hào)集N（2）一個(gè)終結(jié)符號(hào)集∑（3）一個(gè)開始非終結(jié)符S∈N（4）一個(gè)產(chǎn)生式集R（5）對(duì)于任意產(chǎn)生式r∈R，其概率為P(r)產(chǎn)生式具有形式X→Y，其中，X∈N,Y∈(N∪∑)*概率上下文無關(guān)文法（Probabilistic(Stoch6PCFG的三個(gè)基本假設(shè)CFG的簡單概率拓廣

基本假設(shè)位置無關(guān)(Placeinvariance)上下文無關(guān)(Context-free)祖先無關(guān)(Ancestor-free)分析樹的概率等于所有施用規(guī)則概率之積PCFG的三個(gè)基本假設(shè)CFG的簡單概率拓廣

7舉例給定如下概率文法G(1)S->AAp1=1/2(2)S->Bp2=1/2(3)A->ap3=2/3(4)A->bp4=1/3(5)B->aap5=1/2(6)B->bbp6=1/2那么：P(tree1)=1/2*2/3*2/3=2/9P(tree2)=1/2*1/3*1/3=1/18P(tree3)=1/2*1/2=1/4P(tree4)=1/2*1/2=1/4舉例給定如下概率文法G8PCFG的三個(gè)基本問題1、一個(gè)語句W=w1w2….wn的P(W|G),也就是產(chǎn)生語句W的概率？

2、在語句W的句法結(jié)構(gòu)有歧義的情況下,如何快速選擇最佳的語法分析(parse)?

3、如何從語料庫中訓(xùn)練G的概率參數(shù),使得P(W|G)最大

PCFG的三個(gè)基本問題1、一個(gè)語句W=w1w2….wn的P(9問題1&2思路運(yùn)用動(dòng)態(tài)規(guī)劃以及剪枝技術(shù)計(jì)算得出一個(gè)語句的多個(gè)句法分析形式的概率，選擇概率最高的結(jié)果作為句法分析的結(jié)果問題1&2思路10向內(nèi)（Inside）算法非終結(jié)符A的內(nèi)部概率（Insideprobability）定義為根據(jù)文法G從A推出詞串的概率，記為稱為向內(nèi)變量向內(nèi)（Inside）算法11問題11、一個(gè)語句W=w1w2….wn的P(W|G),也就是產(chǎn)生語句W的概率？問題11、一個(gè)語句W=w1w2….wn的P(W|G),也就是12向內(nèi)概率公式

獨(dú)立性假設(shè)獨(dú)立性假設(shè)祖先無關(guān)假設(shè)向內(nèi)概率公式13向內(nèi)算法（自底向上）輸入：G=(S,N,∑,R,P),字符串輸出：1、初始化：2、歸納計(jì)算：j從1到n，i從1到n-j，重復(fù)下面計(jì)算3、結(jié)束：向內(nèi)算法（自底向上）輸入：G=(S,N,∑,R,P),字符14向內(nèi)算法計(jì)算示例S→NPVP1.0 NP→NPPP0.4PP→PNP1.0 NP→John0.1VP→VNP0.7 NP→bone0.18VP→VPPP0.3 NP→star0.04P→with1.0 NP→fish0.18V→ate1.0 NP→telescope0.1向內(nèi)算法計(jì)算示例S→NPVP1.0 NP→NPPP015向內(nèi)算法計(jì)算示例1234567初始化891011向內(nèi)算法計(jì)算示例1234567初始化89101116向內(nèi)算法計(jì)算示例初始化1NP→John0.12V→ate1.03NP→fish0.184P→with1.05NP→bone0.18遞歸計(jì)算6VP→VNP0.77PP→PNP1.08S→NPVP1.09NP→NPPP0.410VP→VPPP0.3VP→VNP0.7結(jié)束S→NPVP1.0向內(nèi)算法計(jì)算示例初始化17問題2在語句W的句法結(jié)構(gòu)有歧義的情況下,如何快速選擇最佳的語法分析(parse)?問題2在語句W的句法結(jié)構(gòu)有歧義的情況下,如何快速選擇最佳的語18Viterbi算法輸入：G=(S,N,∑,R,P),字符串輸出：t*(W在G下最可能的分析樹)算法：1、初始化2、動(dòng)態(tài)規(guī)劃：j從1到n,i從1到n-j,重復(fù)如下步驟3、結(jié)束t*的根節(jié)點(diǎn)為S（文法開始符號(hào)）；從開始回溯，得到S的最優(yōu)樹結(jié)構(gòu)記錄了非終結(jié)符及其統(tǒng)攝的起止位置Viterbi算法輸入：G=(S,N,∑,R,P),字符19Viterbi算法示例Viterbi算法示例20問題3參數(shù)訓(xùn)練問題從樹庫直接統(tǒng)計(jì)——TreebankGrammar最大似然估計(jì)依賴于艱巨的工程：樹庫建設(shè)向內(nèi)向外算法迭代過程與初始參數(shù)相關(guān)問題3參數(shù)訓(xùn)練問題從樹庫直接統(tǒng)計(jì)——TreebankGr21向內(nèi)向外算法非終結(jié)符A的外部概率（outsideprobability）定義為：根據(jù)文法G從A推出詞串的上下文的概率，記為：向內(nèi)向外算法22外部概率公式外部概率公式23計(jì)算外部概率示例（自頂向下）計(jì)算外部概率示例（自頂向下）24規(guī)則的概率文法中每條規(guī)則的概率，采用下式估算S->NPVPVP->VNPNP->NNP->NP的NPNP->VP的NP規(guī)則的概率文法中每條規(guī)則的概率，采用下式估算25規(guī)則的概率PennTreebank((S(NP-SBJThemove)(VPfollowed(NP(NParound)(PPof(NP(NPsimilarincreases)(PPby(NPotherlenders))(PPagainst(NPArizonarealestateloans))))),(S-ADV(NP-SBJ*)(VPreflecting(NP(NPacontinuingdecline)(PP-LOCin(NPthatmarket)))))).))規(guī)則的概率PennTreebank26規(guī)則使用次數(shù)的數(shù)學(xué)期望規(guī)則使用次數(shù)的數(shù)學(xué)期望27規(guī)則使用次數(shù)的數(shù)學(xué)期望規(guī)則使用次數(shù)的數(shù)學(xué)期望28向內(nèi)向外算法EM算法運(yùn)用于PCFG的參數(shù)估計(jì)的具體算法。初始化：隨機(jī)地給P(A->μ)賦值，使得ΣμP(A->μ)=1.由此得到語法G0.i<-0.EM步驟：E步驟：計(jì)算期望值C(A->BC)和C(A->a)M步驟：用E-步驟所得的期望值,利用:重新估計(jì)P(A->μ),得到語法Gi+1循環(huán)計(jì)算:i++,重復(fù)EM步驟,直至P(A->μ)收斂.向內(nèi)向外算法EM算法運(yùn)用于PCFG的參數(shù)估計(jì)的具體算法。29PCFG的優(yōu)缺點(diǎn)優(yōu)點(diǎn)可以對(duì)句法分析的歧義結(jié)果進(jìn)行概率排序提高文法的容錯(cuò)能力（robustness）缺點(diǎn)沒有考慮詞對(duì)結(jié)構(gòu)分析的影響沒有考慮上下文對(duì)結(jié)構(gòu)分析的影響許多當(dāng)前的獲得較高精度的句法分析系統(tǒng)以PCFG為基礎(chǔ)PCFG的優(yōu)缺點(diǎn)優(yōu)點(diǎn)30淺層句法分析技術(shù)從完全句法分析（completeparsing）到淺層句法分析（shallowparsing）真實(shí)語料的復(fù)雜性語言知識(shí)的不足提高分析的效率應(yīng)用目標(biāo)驅(qū)動(dòng)淺層分析的其他名稱：部分分析（partialparsing），組塊分析（chunking）淺層句法分析技術(shù)從完全句法分析（completeparsi31部分分析示例部分分析示例32基于HMM的淺層分析技術(shù)識(shí)別目標(biāo)：非遞歸的NP組塊分析：在線性序列中插入括號(hào)，來標(biāo)示組塊邊界[The/DTprosecutor/NN]said/VBin/IN[closing/NN]that/CS…基于HMM的淺層分析技術(shù)識(shí)別目標(biāo)：非遞歸的NP33短語邊界一對(duì)詞性標(biāo)記[ 表示一個(gè)NP組塊的開始] 表示一個(gè)NP組塊的結(jié)束][ 表示兩個(gè)NP組塊相鄰I 表示不是NP組塊邊界，且處于NP內(nèi)部O 表示不是NP組塊邊界，且處于NP外部短語邊界一對(duì)詞性標(biāo)記34基于HMM的NP組塊邊界標(biāo)注帶有詞性標(biāo)記、組塊邊界標(biāo)記的語料庫可觀察符號(hào)序列：詞性標(biāo)記對(duì)序列隱狀態(tài)：5個(gè)可能的NP組塊邊界標(biāo)記通過對(duì)語料庫統(tǒng)計(jì)，得到狀態(tài)轉(zhuǎn)移矩陣每個(gè)狀態(tài)輸出不同詞性標(biāo)記對(duì)的概率$Theprosecutorsaidinclosingthat…<$,DT><DT,NN><NN,VB><VB,IN><IN,NN><NN,CS>[I]O[]基于HMM的NP組塊邊界標(biāo)注帶有詞性標(biāo)記、組塊邊界標(biāo)記的語料35級(jí)聯(lián)式有限狀態(tài)句法分析

級(jí)聯(lián)式有限狀態(tài)分析（CascadedFinite-StateParsing）級(jí)聯(lián)式有限狀態(tài)句法分析

級(jí)聯(lián)式有限狀態(tài)分析（Cascaded36級(jí)聯(lián)式有限狀態(tài)句法分析過程（1）從左向右掃描輸入字符串，按照Li層級(jí)上的正則表達(dá)式模式進(jìn)行歸約，得到新的模式序列，對(duì)于輸入串中無法歸約的符號(hào)，直接輸出；（2）i=i+1，在新的Li層級(jí)上，用正則表達(dá)式模式進(jìn)行歸約（3）不斷進(jìn)行上述步驟，直到無法歸約為止；（4）如果歸約過程中有多種選擇，以覆蓋范圍最大的歸約子串為輸入結(jié)果級(jí)