2023自然語言處理導論 3句法分析

1第三章句法分析自然語言處理導論句法概述3.1成分句法分析3.2依存句法分析3.3目錄Contents2句法分析語料庫3.43.1.1成分語法理論概述3.1.2依存語法理論概述句法概述3.1成分句法分析3.2依存句法分析3.3目錄Contents3句法分析語料庫3.43.1什么是句法？4句法（Syntax）就是研究自然語言中不同成分組成句子的方式以及支配句子結構并決定句子是否成立的規(guī)則。任何人類語言都具備構造無限數(shù)量句子的能力可以通過增加形容詞、副詞、關系小句、介詞短語等方法把任意的句子進一步地創(chuàng)造。無法將一種語言按照詞典的方式把所有句子存儲起來通過語言學研究發(fā)現(xiàn)，句子并非詞語的隨意組合，而是由按照一定規(guī)則結合起來的離散單位組成3.1句法概述5句法是現(xiàn)代語言學研究中的重要課題，有大量的句法理論（SyntacticTheory）相關研究。語法（Grammar）就是指自然語言中句子、短語以及詞等語法單位的語法結構與語法意義的規(guī)律。根據(jù)語法就可以判斷不同成分組成句子的方式以及決定句子是否成立。狹義的語法學研究基本等同于句法學。語言學家自19世紀50年代以來，構建了大量表達明確并且形式化的語法理論，對自然語言句法分析提供了理論支撐。語法理論在構建時，一個重要的問題是該理論是基于成分關系還是基于依存關系。

3.1.1成分語法理論概述6NoamChomsky于1957年發(fā)表的《SyntacticStructures》奠定了成分語法的基礎成分（Constituent）又稱短語結構，是指一個句子內(nèi)部的結構成分。成分可以獨立存在，或者可以用代詞替代，又或者可以在句子中的不同位置移動。例如：他正在寫一本小說。

“一本小說”是一個成分3.1.1成分語法理論概述7根據(jù)不同成分之間是否可以進行相互替代而不會影響句子語法正確性，可以進一步地將成分進行分類，某一類短語就屬于一個句法范疇（SyntacticCategory）。比如“一本小說”、“一所大學”等都屬于一個句法范疇：名詞短語（NonePhrase，NP）。句法范疇不僅僅包含名詞短語（NP）、動詞短語（VP）、介詞短語（PP）等短語范疇，也包含名詞（N）、動詞（V）、形容詞（Adj）等詞匯范疇。除此之外還包含功能范疇（包括冠詞、助動詞等）。3.1.1成分語法理論概述8句法范疇之間不是完全對等的，而是具有層級關系。例如：一個句子可以由一個名詞短語和一個動詞短語組成，一個名詞短語可以由一個限定詞和一個名詞組成，一個動詞短語又可以由一個動詞和一個名詞短語組成。短語結構規(guī)則（PhraseStructureRules）又稱改寫規(guī)則或重寫規(guī)則，對句法范疇間的關系進行形式化描述。通常可以用X

YZW…

表示，其中X表示短語名稱，

表示改寫為，YZW…定義了短語X的結構，如果YZW是短語，則還需要構造出它們的規(guī)則。3.1.1成分語法理論概述9例如： (1)S?>NPVP

(2)NP?>DetN

(3)VP?>VNP成分語法就是由句法范疇以及短語結構規(guī)則定義的語法。由于短語結構規(guī)則具有遞歸性，可以使短語和句子無限循環(huán)組合。這也說明了語言的創(chuàng)造性和無限性。3.1.1成分語法理論概述10由于成分語法局限于表層結構分析，不能徹底解決句法和語義問題，因此存在非連續(xù)成分、結構歧義等問題。3.1.2依存語法理論概述11LucienTesnière

1959年發(fā)表的《Elémentsdesyntaxestructurale》奠定了句法依存關系研究的基礎在基于依存關系的語法中，句子中的每個成分對應句法結構中的唯一一個節(jié)點。兩個成分之間的依存關系是二元的非對稱關系，具有方向性，一個成分是中心語，另一個成分依附于中心語存在，關系從中心語成分指向依存成分。中心成分稱為中心詞或支配者（Governor，Regent，Head）依存成分也稱為修飾詞或從屬者（Modifier，Subordinate，Dependency）3.1.2依存語法理論概述12兩個單詞之間是否存在依存關系？單詞之間誰處于支配地位？誰處于從屬地位？建立這些詞與詞之間關系的依據(jù)是什么？配價（Valency）理論是其中最為經(jīng)典的論著之一，價是詞語的一個屬性，表示某個詞語與其他詞語結合的能力。配價模式(Valency

pattern)則是描述了某一個具有特定意義的詞的出現(xiàn)語境，以及當一個詞出現(xiàn)在一個特定的模式下時，還有哪些詞語會出現(xiàn)在這個模式下及其語義角色。3.1.2依存語法理論概述13詞語間的依存關系還可以根據(jù)語法關系定義為不同的類型，Carroll等人將依存關系細分為了20種，并給出了關系之間的層級結構。Marneffe等人在上述工作的基礎上對依存關系進行了進一步的細化，定義了48種依存關系，主要分為論元依存關系和修飾語依存關系兩大類。3.1.2依存語法理論概述14依存語法中根據(jù)依存成分與中心語或姐妹成分在語序上的關系，可以分為符合投射性原則和違反投射性原則兩類。3.2.1基于上下文無關文法的成分句法分析3.2.2基于概率上下文無關文法的成分句法分析3.2.3成分句法分析評價方法句法概述3.1成分句法分析3.2依存句法分析3.3目錄Contents15句法分析語料庫3.43.2成分句法分析16成分句法分析（ConstituencyParsing）是對給定句子根據(jù)成分語法中制定的規(guī)則構建其所對應的結構樹的過程。通?？梢杂肵

YZW…

表示，

與數(shù)學系統(tǒng)中的上下文無關文法（Context-

FreeGrammar，CFG）組成非常類似3.2成分句法分析17對一個句子進行句法分析的過程可以看做對一個句子搜索所有可能的路徑空間，從中發(fā)現(xiàn)正確的句法樹的過程。搜索過程受到兩個約束限制，一個是句子本身，另外一個是語法。根據(jù)成分句法的定義，葉子節(jié)點一定是句子中的單詞，中間節(jié)點與其子節(jié)點需要符合語法定義。這兩種約束也產(chǎn)生了大多數(shù)分析算法所采用的搜索策略：自底向上（Bottom-up）和自頂向下（Top-down）。3.2成分句法分析18由于句法結構具有歧義，因此句法分析中最重要的工作之一也是如何消除歧義。成分語法中的結構歧義主要有兩種：附著歧義（Attachmentambiguity）以及并列連接歧義（Coordinationambiguity）附著歧義：Theboysawthemanwiththetelescope并列連接歧義：重要政策和措施3.2.1基于上下文無關文法的成分句法分析19在給定上下文無關文法G的情況下，對于給定的句子W={w1,w2,···,wn}，輸出其對應的句法結構，通常有兩大類搜索方法：自頂向下和自底向上。自頂向下搜索試圖從根節(jié)點S出發(fā)，搜索語法中的所有規(guī)則直到葉子節(jié)點，并行構造所有可能的樹自底向上的方法是從輸入的單詞開始，每次都是用語法規(guī)則，直到成功構造了以初始符S為根的樹3.2.1基于上下文無關文法的成分句法分析20CYK算法（CYK是Cocke–Younger–Kasami的縮寫，有時也稱為CKY）是由JohnCocke、DanielYounger以及TadaoKasami分別獨立提出的基于動態(tài)規(guī)劃思想的自底向上語法分析算法CYK算法要求所使用的語法必須符合喬姆斯基范式（ChomskyNormalFrom，CNF），其語法規(guī)則被限制為只具有A→BC或A→w這種形式。根據(jù)CNF語法形式，句法樹的葉子節(jié)點為單詞，單詞的父節(jié)點為詞性符號，在詞性符號層之上每一個非終結符都有兩個子節(jié)點。因此CYK算法采用了二維矩陣對整個樹結構進行編碼。3.2.1基于上下文無關文法的成分句法分析21對于一個長度為n的句子，構造一個(n+1)×(n+1)的二維矩陣T矩陣主對角線以下全部為0，主對角線上的元素由輸入句子的終結符號(單詞)構成主對角線以上的元素Tij包含由文法G的非終結符構成的集合，這個集合表示輸入句子中橫跨在位置i到j之間的單詞的組成成分。輸入句子中索引從0開始，索引位于輸入句子的單詞之間，也可以看成單詞之間的間隔指針例如：0她1喜歡2跳3芭蕾43.2.1基于上下文無關文法的成分句法分析22具體過程如算法3.1所示3.2.1基于上下文無關文法的成分句法分析233.2.1基于上下文無關文法的成分句法分析24移進-歸約成分句法分析算法的基本思想是從左到右掃描輸入的包含單詞詞性對的句子，使用堆棧和一系列的移進（Shift）和歸約（Reduce）操作序列構建句法樹。算法初始時堆棧S為空，隊列Q中包含整個句子所有單詞。在算法結束時堆棧S中包含一個完整的句法樹，隊列Q為空。所采用的操作包含以下四個：移進（Shift）：將非空隊列Q最左端的單詞移入堆棧S中歸約（Reduce）：根據(jù)推導規(guī)則，根據(jù)推導規(guī)則右側所包含非終結符數(shù)量，將堆棧S中的最頂端相應數(shù)量元素移出，然后將利用推導規(guī)則產(chǎn)生的新結構壓入堆棧中接受（Accept）：隊列中所有單詞都已被移到堆棧中，并且堆棧中只剩下一個由非終結符S為根的樹，表示分析成功拒絕（Reject）：隊列中所有單詞都已被移到堆棧中，但是堆棧中并非只有一個以非終結符S為根的樹，并且無法繼續(xù)歸約，表示分析失敗3.2.1基于上下文無關文法的成分句法分析25如何根據(jù)當前堆棧S和隊列Q中的狀態(tài)，選擇下一步的操作是移進-歸約分析算法中最重要的部分。由于移進和歸約操作并不是完全互斥的，在很多狀態(tài)下兩種操作都可以選擇，這就造成了移進歸約沖突（ShiftReduceConflict）。3.2.1基于上下文無關文法的成分句法分析263.2.2基于概率上下文無關文法的成分句法分析27基于概率上下文無關文法（ProbabilisticContext-FreeGrammar，PCFG）的句法分析則可以結合規(guī)則方法和統(tǒng)計方法PCFG是CFG的擴展，因此PCFG的文法也是由終結符集合∑、非終結符集合N、初始符S以及規(guī)則集合R組成。只是在CFG的基礎上對每條規(guī)則增加了概率，其規(guī)則用如下形式表示：A→α,p其中A為非終結符，α∈(∑∪N)?為終結符和非終結符組成的有序序列集合，p為A推導出α的概率，即p=P(A→α)

3.2.2基于概率上下文無關文法的成分句法分析28由于PCFG中每個規(guī)則中包含了概率信息P(A→α)，因此可以根據(jù)一個句子及其句法分析樹計算特定句法分析樹的概率、句子的概率以及句子片段的概率。利用特定分析樹的概率可以用于消除分析樹的歧義。3.2.2基于概率上下文無關文法的成分句法分析29PCFG句法分析樹概率計算句法樹概率計算還要應用以下三個獨立假設：

(1)位置不變性（Placein-variance）：子樹的概率不依賴于該子樹所在的位置；(2)上下文無關性（Context-free）：子樹的概率不依賴于子樹以外的單詞；(3)祖先無關性（Ancestor-free）：子樹的概率不依賴于子樹的祖先節(jié)點。一個特定句法樹T的概率定義為該句法樹T中用來得到句子W所使用的m個規(guī)則的概率乘積：3.2.2基于概率上下文無關文法的成分句法分析303.2.2基于概率上下文無關文法的成分句法分析313.2.2基于概率上下文無關文法的成分句法分析32PCFG的句子概率計算句子概率計算是指在給定PCFG文法G的情況下，計算給定句子W的概率P(W|G)可以采用內(nèi)向算法（InsideAlgorithm）或外向算法（OutsideAlgorithm）采用內(nèi)向算法，首先定義內(nèi)向變量aij(A)為非終結符A推導出W中子串wiwi+1···wj

的概率，即：句子W的概率則相應的標記為a1n(S)通過如下遞推公式計算得到：3.2.2基于概率上下文無關文法的成分句法分析333.2.2基于概率上下文無關文法的成分句法分析34PCFG的最佳樹結構求解最佳樹結構求解是指對于給定句子W={w1,w2,…..

,wn}和PCFG文法G，求解該句子的最佳樹結構，即如何選擇句法結構樹使得其概率最大：可以通過利用基于概率的CYK算法進行3.2.2基于概率上下文無關文法的成分句法分析353.2.2基于概率上下文無關文法的成分句法分析36使用CYK算法求解PCFG的最佳樹結構分析實例3.2.2基于概率上下文無關文法的成分句法分析37PCFG的模型參數(shù)學習基于最大似然估計，統(tǒng)計非終結符的出現(xiàn)次數(shù)進行概率參數(shù)估Count(A→α)是指規(guī)則A→α在整個樹庫中出現(xiàn)的次數(shù)，Count(A)是指在樹庫中非終結符A出現(xiàn)的次數(shù)在僅有大規(guī)模無標記句子的情況下，也可以通過期望最大化算法（ExpectationMaximization，EM）估計規(guī)則的概率參數(shù)。利用當前的文法Gi估算每條規(guī)則出現(xiàn)的期望值是期望步（ExpectationStep，E-步驟），重新估算概率得到Gi+1

的步驟是最大化步（MaximizationStep，M-步驟）3.2.3成分句法分析評價方法38PARSEVAL方法3.3.1基于圖的依存句法分析的成分句法分析3.3.2基于神經(jīng)網(wǎng)絡的圖依存句法分析句法分析3.3.3基于轉(zhuǎn)移的依存句法分析3.3.4基于神經(jīng)網(wǎng)絡的轉(zhuǎn)移依存句法分析3.3.5依存句法分析評價方法句法概述3.1成分句法分析3.2依存句法分析3.3目錄Contents39句法分析語料庫3.43.3依存句法分析40依存句法分析（DependencyParsing）任務目標是依據(jù)依存語法理論分析輸入句子得到其依存句法結構樹。依存句法理論的基本假設是句法結構由單詞和單詞之間的依存關系組成。依存關系具有方向性，從中心語成分指向依存成分。依存關系根據(jù)中心成分和依存成分之間的關系又可以被定義為不同的依存關系類型。依存句法結構使用依存圖（DependencyGraph）進行表示。

3.3依存句法分析41在本節(jié)中，使用S=w0w1···wn

表示輸入的句子，其中w0=root表示虛擬根節(jié)點，w1...wn為輸入句子中的n個單詞。R={r0,r1,...,rm}表示依存關系類型集合，r∈R表示在句子中單詞之間的依存關系，也叫做邊標簽（ArcLabel）。如果依存圖G=(V,A)對于輸入句子S和關系集合R，是一個從w0

出發(fā)的有向樹，并且包含句子中的所有單詞，那么這個依存圖G就成為形式良好的依存圖（Well-formedDependency

Graph），也稱為依存樹（DependencyTree）。3.3.1基于圖的依存句法分析42基于圖的依存句法分析核心是構造評分函數(shù)，對句子S所有依存句法樹G=(V,A)∈GW

進行評分。這個評分代表了一個句法樹作為句子分析正確結果的可能性。不同的基于圖的分析方法采用不同的假設來計算得分?；趫D的依存句法分析算法通常將對依存句法樹的G=(V,A)的評分轉(zhuǎn)化為對其樹上的邊的評分：可以將基于圖的依存句法分析形式化表示為：3.3.1基于圖的依存句法分析43可以證明在依存句法樹不考慮投射性（Projectivity）的情況下，對于輸入句子S的依存句法分析問題等價于基于邊評分λ(wi,r,wj)的圖GS的最大生成樹（MaximumSpanningTree）尋找問題利用最大生成樹算法得到的依存句法樹不具備投射性。針對具有投射性要求的依存句法樹，可以利用其與上下文無關語法之間的強相關性，利用基于CYK算法等上下文無關語法分析算法進行依存句法樹分析。3.3.1基于圖的依存句法分析44非投射性依存句法分析方法朱-劉/埃德蒙茲算法（Chu-Liu/Edmonds）方法是一種常見的帶權有向圖最小/大生成樹尋找算法，因此也常被應用于非投射性依存句法分析。輸入是待分析句子S=w0w1...wn

以及邊之間的權重λ(wi,wj)∈λw0

是句子的虛擬根節(jié)點，依存句法樹中不存在指向w0的邊。3.3.1基于圖的依存句法分析45根據(jù)句子中的單詞和權重組成有向圖GS=(VS,AS)針對圖G中每個頂點選擇入邊權重最大的邊構建子圖G′=(VS,A′)。如果該子圖中沒有環(huán)，那么該子圖就是圖G的最大生成樹。否則，說明圖G′中至少包含一個環(huán)。那么選擇其中任意一個環(huán)C，其邊集合為AC，將環(huán)C用一個節(jié)點wc

來代表，圖GC

中包含所有在圖G中但是不在環(huán)C中的節(jié)點以及wc，GC

的邊通過以下規(guī)則構建：將圖GC作為輸入，遞歸調(diào)用上述算法得到其最大生成樹G=(V,A)。之后根據(jù)所返回的最大生成樹信息對原始圖信息進行修正，移除環(huán)C3.3.1基于圖的依存句法分析46圖3.18朱-劉/埃德蒙茲算法生成依存句法樹樣例3.3.1基于圖的依存句法分析47投射性依存句法分析方法設置虛擬根節(jié)點在句子首位的情況下，投射性依存句法分析樹等價于嵌套依存句法分析樹（NestedDependencyTrees）。因此投射性依存句法分析與上下文無關語法具有非常強的關系，很多用于上下文無關語法分析的算法也可以應用于投射性依存句法分析。首先定義動態(tài)規(guī)劃表C[s][t][i]（s?i?t），表示投射性句法樹以單詞wi為根節(jié)點覆蓋從單詞ws

到單詞wt

的句子片段的最高得分。由此可以得到C[0][n][0]表示輸入句子S=w0,w1,...,wn的依存句法樹的最高得分。3.3.1基于圖的依存句法分析48投射性依存句法分析方法3.3.1基于圖的依存句法分析49投射性依存句法分析方法A[s][t][i]按照如下公式記錄樹結構：3.3.1基于圖的依存句法分析50邊評分模型學習方法邊評分模型可以使用基于高維特征向量的線性函數(shù)進行建模f(·)包含了邊和輸入句子S中各類型相關特征?wi=喜歡

?wi=跳

?wi

的詞性=V

?wj

的詞性=V

?r的依存關系類型=xcomp

?wi-1

的詞性=ADV?wj+1

的詞性=N

?wi

和wj之間距離=1

這些特征還可以組合為更復雜的類型?wi

的詞性=V&wj

的詞性=V&wi=喜歡

?wi=喜歡&wj=跳&wi

和wj

之間距離=1

3.3.1基于圖的依存句法分析51邊評分模型學習方法基于特征向量的線性函數(shù)建模的假設下，對于輸入句子的依存句法分析轉(zhuǎn)換為了如下問題：表示訓練語料集合Sd

表示輸入句子，所對應的正確的依存句法樹用Gd

表示3.3.1基于圖的依存句法分析52邊評分模型學習方法3.3.2基于神經(jīng)網(wǎng)絡的圖依存句法分析53基于圖的依存句法分析主要包含邊評分模型和句法樹生成算法兩個部分組成。其中邊評分模型對于分析效果具有決定性的影響。神經(jīng)網(wǎng)絡方法也可以用于構造邊評分。3.3.2基于神經(jīng)網(wǎng)絡的圖依存句法分析54基于前饋神經(jīng)網(wǎng)絡的方法模型輸入包含兩大部分：原子特征（AtomicFeatures）和短語結構（Phrases）。原子特征部分使用單個詞和單個詞性。通過查找嵌入矩陣M=Rd×|D|

轉(zhuǎn)換為相應的嵌入（Embedding）表示。|D|是特征字典大小，d是特征嵌入表示的維度。為了更好地建模依存關系的上下文信息，根據(jù)所要預測中心詞和修飾詞在句子中的位置，將句子切分為前綴（Prefix）、中綴（Infix）和后綴（Suffix）。3.3.2基于神經(jīng)網(wǎng)絡的圖依存句法分析55基于雙仿射變換的方法DeepBiaffineParser也是采用最大生成樹方法構造依存句法樹，引入了雙向長短時記憶網(wǎng)絡，更好地建模句子上下文信息單詞的詞嵌入和對應的詞性嵌入合并作為雙向長短時記憶網(wǎng)絡的輸入3.3.2基于神經(jīng)網(wǎng)絡的圖依存句法分析56基于雙仿射變換的方法使用多層感知器（MLP）對ri

用于中心詞和修飾詞的不同情況，分別進行兩種不同的降維所有時刻的hi(arc?head)和hi(arc?dep)

分別合并組成矩陣H(arc?head)

和H(arc?dep)

利用不類別雙仿射分類器（Variable-classBiaffineClassifier），得到邊評分矩陣：wi為修飾詞wyi為中心詞的依存類別的分類：3.3.2基于神經(jīng)網(wǎng)絡的圖依存句法分析57基于圖神經(jīng)網(wǎng)絡的方法基于圖神經(jīng)網(wǎng)絡的依存句法分析算法（Graph-basedDependencyParsingwithGraphNeuralNetworks，GNNDP），試圖將更多的結構化信息引入到節(jié)點表示。圖3.22基于圖神經(jīng)網(wǎng)絡的依存句法分析網(wǎng)絡結構圖3.3.2基于神經(jīng)網(wǎng)絡的圖依存句法分析58基于圖神經(jīng)網(wǎng)絡的方法單詞序列表示使用雙向長短時記憶網(wǎng)絡（BiLSTM）編碼單詞序列由于依存邊有方向性，因此采用兩個多層感知器來生成不同的向量從而區(qū)分這兩種角色輸出的得分實際上也是依存邊（wi

支配wj）的概率3.3.2基于神經(jīng)網(wǎng)絡的圖依存句法分析59基于圖神經(jīng)網(wǎng)絡的方法GNNDP將圖神經(jīng)網(wǎng)絡應用到依存句法分析任務，句法分析任務需要在圖G上同時處理支配詞表征hi和從屬詞表示di，而不是為每個節(jié)點編碼一個向量。此外，為了近似精確的高階分析，分析器需要每個GNNs網(wǎng)絡層有關于句子的具體含義。因此，GNNDP采用完全圖（即所有節(jié)點都是連接的），并用依存邊條件概率設置邊權。GNNDP關注三類高階信息，即祖父母、孫子和兄弟關系3.3.2基于神經(jīng)網(wǎng)絡的圖依存句法分析60基于圖神經(jīng)網(wǎng)絡的方法σt(j,i)不僅考慮一跳父子關系(j,i)，還考慮兩跳i的祖父母節(jié)點（用k表示）。同樣，為了在σt(j,i)中對兩跳的j的孫子節(jié)點進行編碼（也用k表示），需要聚合鄰居節(jié)點的從屬詞表示。3.3.2基于神經(jīng)網(wǎng)絡的圖依存句法分析61基于圖神經(jīng)網(wǎng)絡的方法3.3.2基于神經(jīng)網(wǎng)絡的圖依存句法分析62基于圖神經(jīng)網(wǎng)絡的方法3.3.2基于神經(jīng)網(wǎng)絡的圖依存句法分析63基于圖神經(jīng)網(wǎng)絡的方法3.3.3基于轉(zhuǎn)移的依存句法分析64轉(zhuǎn)移系統(tǒng)（TransitionSystem）包含狀態(tài)集合（State或Configuration）以及狀態(tài)之間的轉(zhuǎn)移動作集合（Transition）標準?。ˋrc-Standard）轉(zhuǎn)移系統(tǒng)是其中最常用的投射性依存句法分析轉(zhuǎn)移系統(tǒng)之一3.3.3基于轉(zhuǎn)移的依存句法分析653.3.3基于轉(zhuǎn)移的依存句法分析66假設存在函數(shù)o，可以根據(jù)當前的狀態(tài)c正確地確定下一步的轉(zhuǎn)移動作t，即o(c)=t。那么整個句法分析的過程就可以使用非常簡單的貪心算法完成。針對輸入句子S，首先，構造初始狀態(tài)c0(S)，調(diào)用函數(shù)o得到下一步轉(zhuǎn)移動作t=o(c)。之后，利用根據(jù)轉(zhuǎn)移動