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

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

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

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è)基本問(wèn)題1、一個(gè)語(yǔ)句W=w1w2….wn的P(W|G),也就是產(chǎn)生語(yǔ)句W的概率？

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

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

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

獨(dú)立性假設(shè)獨(dú)立性假設(shè)祖先無(wú)關(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問(wèn)題2在語(yǔ)句W的句法結(jié)構(gòu)有歧義的情況下,如何快速選擇最佳的語(yǔ)法分析(parse)?問(wèn)題2在語(yǔ)句W的句法結(jié)構(gòu)有歧義的情況下,如何快速選擇最佳的語(yǔ)18Viterbi算法輸入：G=(S,N,∑,R,P),字符串輸出：t*(W在G下最可能的分析樹(shù))算法：1、初始化2、動(dòng)態(tài)規(guī)劃：j從1到n,i從1到n-j,重復(fù)如下步驟3、結(jié)束t*的根節(jié)點(diǎn)為S（文法開(kāi)始符號(hào)）；從開(kāi)始回溯，得到S的最優(yōu)樹(shù)結(jié)構(gòu)記錄了非終結(jié)符及其統(tǒng)攝的起止位置Viterbi算法輸入：G=(S,N,∑,R,P),字符19Viterbi算法示例Viterbi算法示例20問(wèn)題3參數(shù)訓(xùn)練問(wèn)題從樹(shù)庫(kù)直接統(tǒng)計(jì)——TreebankGrammar最大似然估計(jì)依賴于艱巨的工程：樹(shù)庫(kù)建設(shè)向內(nèi)向外算法迭代過(guò)程與初始參數(shù)相關(guān)問(wèn)題3參數(shù)訓(xùn)練問(wèn)題從樹(shù)庫(kù)直接統(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.由此得到語(yǔ)法G0.i<-0.EM步驟：E步驟：計(jì)算期望值C(A->BC)和C(A->a)M步驟：用E-步驟所得的期望值,利用:重新估計(jì)P(A->μ),得到語(yǔ)法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)沒(méi)有考慮詞對(duì)結(jié)構(gòu)分析的影響沒(méi)有考慮上下文對(duì)結(jié)構(gòu)分析的影響許多當(dāng)前的獲得較高精度的句法分析系統(tǒng)以PCFG為基礎(chǔ)PCFG的優(yōu)缺點(diǎn)優(yōu)點(diǎn)30淺層句法分析技術(shù)從完全句法分析（completeparsing）到淺層句法分析（shallowparsing）真實(shí)語(yǔ)料的復(fù)雜性語(yǔ)言知識(shí)的不足提高分析的效率應(yīng)用目標(biāo)驅(qū)動(dòng)淺層分析的其他名稱：部分分析（partialparsing），組塊分析（chunking）淺層句法分析技術(shù)從完全句法分析（completeparsi31部分分析示例部分分析示例32基于HMM的淺層分析技術(shù)識(shí)別目標(biāo)：非遞歸的NP組塊分析：在線性序列中插入括號(hào)，來(lái)標(biāo)示組塊邊界[The/DTprosecutor/NN]said/VBin/IN[closing/NN]that/CS…基于HMM的淺層分析技術(shù)識(shí)別目標(biāo)：非遞歸的NP33短語(yǔ)邊界一對(duì)詞性標(biāo)記[ 表示一個(gè)NP組塊的開(kāi)始] 表示一個(gè)NP組塊的結(jié)束][ 表示兩個(gè)NP組塊相鄰I 表示不是NP組塊邊界，且處于NP內(nèi)部O 表示不是NP組塊邊界，且處于NP外部短語(yǔ)邊界一對(duì)詞性標(biāo)記34基于HMM的NP組塊邊界標(biāo)注帶有詞性標(biāo)記、組塊邊界標(biāo)記的語(yǔ)料庫(kù)可觀察符號(hào)序列：詞性標(biāo)記對(duì)序列隱狀態(tài)：5個(gè)可能的NP組塊邊界標(biāo)記通過(guò)對(duì)語(yǔ)料庫(kù)統(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)記的語(yǔ)料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)句法分析過(guò)程（1）從左向右掃描輸入字符串，按照Li層級(jí)上的正則表達(dá)式模式進(jìn)行歸約，得到新的模式序列，對(duì)于輸入串中無(wú)法歸約的符號(hào)，直接輸出；（2）i=i+1，在新的Li層級(jí)上，用正則表達(dá)式模式進(jìn)行歸約（3）不斷進(jìn)行上述步驟，直到無(wú)法歸約為止；（4）如果歸約過(guò)程中有多種選擇，以覆蓋范圍最大的歸約子串為輸入結(jié)果級(jí)