前面的章節(jié)重點關(guān)注詞：如何識別它們凡桥，分析它們的結(jié)構(gòu)户辞，分配給他們詞匯類別，以及獲得它們的含義卧抗。我們還看到了如何識別詞序列或n-grams中的模式藤滥。然而，這些方法只觸碰到支配句子的復(fù)雜約束的表面社裆。我們需要一種方法處理自然語言中顯著的歧義拙绊。我們還需要能夠應(yīng)對這樣一個事實，句子有無限的可能泳秀，而我們只能寫有限的程序來分析其結(jié)構(gòu)和發(fā)現(xiàn)它們的含義标沪。
本章的目的是要回答下列問題：
我們?nèi)绾问褂眯问交Z法來描述無限的句子集合的結(jié)構(gòu)？
我們?nèi)绾问褂镁浞鋪肀硎揪渥咏Y(jié)構(gòu)嗜傅？
語法分析器如何分析一個句子并自動構(gòu)建句法樹金句？
一路上，我們將覆蓋英語句法的基礎(chǔ)吕嘀，并看到句子含義有系統(tǒng)化的一面违寞，只要我們確定了句子結(jié)構(gòu)贞瞒，將更容易捕捉。
PS：書中的講解順序個人感覺比較難以理解趁曼，下面我會以自己的理解順序來重新調(diào)整
一军浆、文法簡述
文法(語法)是用于描述語言的語法結(jié)構(gòu)的形式規(guī)則。任何一種語言都有它自己的文法挡闰，我們最常接觸的文法自然語言里有主謂賓這樣的文法一樣乒融。（文法好像還分為句法和詞法，不去糾結(jié)這個尿这，我們正常來說都是在處理句法）
使用文法有很多顯而易見的好處(畢竟大家都是有9年義務(wù)教育的人簇抵，都懂的)，但在計算機中進行文法分析還需要解決兩個主要的問題射众，其一是文法在計算機中的表達與存儲方法碟摆，以及語料數(shù)據(jù)集；其二是文法解析的算法叨橱。
1. 文法在計算機中的表達與存儲方法
在計算機中典蜕，我們可以用樹狀結(jié)構(gòu)圖來表示，如下圖所示罗洗，S表示句子愉舔；NP、VP伙菜、PP是名詞轩缤、動詞、介詞短語（短語級別）贩绕；N火的、V、P分別是名詞淑倾、動詞馏鹤、介詞。
實際存儲的時候上述的樹可以表示為(S (NP (N Boeing)) (VP (V is) (VP (V located) (PP (P in) (NP (N Seattle))))))娇哆。
同時湃累，互聯(lián)網(wǎng)上已經(jīng)有成熟的、手工標注的語料數(shù)據(jù)集碍讨，例如The Penn Treebank Project （Penn Treebank II Constituent Tags）治力。
2. 文法解析的算法
如何描述文法，有兩種主流觀點勃黍，其中一種是短語結(jié)構(gòu)文法琴许，英文術(shù)語是：Constituency = phrase structure grammar = context-free grammars (CFGs)。
這種短語語法用固定數(shù)量的rule分解句子為短語和單詞溉躲、分解短語為更短的短語或單詞等更小的單元榜田。一個是取自WSJ語料庫的短語結(jié)構(gòu)樹示例：
另一種是依存結(jié)構(gòu)益兄，用單詞之間的依存關(guān)系來表達語法。如果一個單詞修飾另一個單詞箭券，則稱該單詞依賴于另一個單詞：
這一部分是接下來的重點
二净捅、上下文無關(guān)文法（Context-Free Grammer）
CFG是一個四元組：G =（N，T辩块，P蛔六，S），其中
- N是非終結(jié)符（Nonterminals）的有限集合
- T是終結(jié)符（Terminals）的有限集合废亭，且N∩T=Φ
- P是產(chǎn)生式（Productions）的有限集合国章，形如：A→α，其中A∈N（左部）豆村，α∈(N∪T)*（右部）液兽，若α=ε，則稱A→ε為空產(chǎn)生式（也可以記為A →）
- S是非終結(jié)符掌动，稱為文法的開始符號（Start symbol）
使用CFG可以很快速準確地定義簡單的算術(shù)表達式四啰，例如N = {E} T = {+，*粗恢，(柑晒，)，-眷射，id} S = E四元組匙赞，S = E表明文法從E開始，也就是WSJ語料庫的短語結(jié)構(gòu)樹中的S妖碉，那么產(chǎn)生式有這幾種：E → E + E; E → E * E; E →（E); E → -E; E → id罚屋。
抽象地數(shù)學(xué)表示是這樣的，簡單來說嗅绸，其實N就是就是NP、VP撕彤、PP和N等的集合鱼鸠，T就是我們的單詞。
定義這樣的四元組羹铅，主要是為了使用分析樹表示文法蚀狰，也就是我們上面所看到的樹的結(jié)構(gòu)。
分析樹的定義：
- 根由開始符號所標記
- 每個葉子由一個終結(jié)符职员、非終結(jié)符麻蹋、或ε標記
- 每個內(nèi)部結(jié)點由一個非終結(jié)符標記
- 若A是某內(nèi)部節(jié)點的標記，且X1焊切，X2扮授，…芳室，Xn是該節(jié)點從左到右所有孩子的標記，則A→X1X2…Xn是一個產(chǎn)生式刹勃。若A→ε堪侯，則標記為A的結(jié)點可以僅有一個標記為ε的孩子
其實拋開這些文縐縐的定義，我覺得最重要的一點就是：要求產(chǎn)生式的左部有且僅有一個非終結(jié)符
1. 遞歸下降解析器
一種最簡單的分析器將一個文法作為如何將一個高層次的目標分解成幾個低層次的子目標的規(guī)范來解釋荔仁。頂層的目標是找到一個 S伍宦。S→NP VP 產(chǎn)生式允許分析器替換這個目標為兩個子目標：找到一個 NP，然后找到一個 VP乏梁。每個這些子目標都可以再次被子目標的子目標替代次洼，使用左側(cè)有 NP 和 VP 的產(chǎn)生式。最終遇骑，這種擴張過程達到子目標卖毁，如找到詞 telescope。這樣的子目標可以直接與輸入序列比較质蕉，如果下一個單詞匹配就取得成功势篡。如 果沒有匹配，分析器必須備份模暗，并嘗試其它選擇：
import nltk
from nltk import CFG
grammar1 = nltk.CFG.fromstring("""
S -> NP VP
VP -> V NP | V NP PP
PP -> P NP
V -> "saw" | "ate" | "walked"
NP -> "John" | "Mary" | "Bob" | Det N | Det N PP
Det -> "a" | "an" | "the" | "my"
N -> "man" | "dog" | "cat" | "telescope" | "park"
P -> "in" | "on" | "by" | "with"
""")
rd_parser = nltk.RecursiveDescentParser(grammar1)
sent = 'Mary saw a dog'.split()
for t in rd_parser.parse(sent):
print(t)
可以調(diào)用nltk.app.rdparser()來查看分析過程：
遞歸下降分析是一種自上而下分析禁悠。自上而下分析器在檢查輸入之前先使用文法預(yù)測輸 入將是什么。
三個主要缺點：
- 左遞歸產(chǎn)生式：NP-> NP PP 會陷入死循環(huán)
- 處理不符合句子的詞和結(jié)構(gòu)時候浪費時間
- 回溯過程過重會丟掉計算過的分析兑宇，重新計算
2. 移進-歸約解析器
移進-歸約分析器是一種自下而上分析器碍侦，它嘗試找到對應(yīng)文法產(chǎn)生式右側(cè)的詞和短語的序列，用左側(cè)的替換它們隶糕，直到整個句子歸約為一個 S瓷产。
移位-規(guī)約分析器反復(fù)將下一個輸入詞推到堆棧，如果堆棧上的前 n 項枚驻，匹配一些產(chǎn)生式的右側(cè)的 n 個項目濒旦，那么就把它們彈出棧，并把產(chǎn)生式左邊的項目壓入棧再登。這種替換前 n 項為一項的操作就是規(guī)約操作尔邓。此操作只適用于堆棧的頂部；規(guī)約棧中的項目必須在后面的項目被壓入棧之前做锉矢。當所有的輸入都使用過梯嗽，堆棧中只剩余一個項目，也就是一顆分析樹作為它的根的 S 節(jié)點時沽损，分析器完成灯节。移位-規(guī)約分析器通過上述過程建立一顆分析樹。每次彈出堆棧 n 個項目，它就將它們組合成部分的分析樹炎疆，然后將這壓回推棧：
sr_parse = nltk.ShiftReduceParser(grammar1)
for t in sr_parse.parse(sent):
print(t)
兩個缺點：
- 由于堆棧的特殊性卡骂，只能找到一種解析
- 不能保證一定能找到解析
3. 左角落分析器
遞歸下降分析器的問題之一是當它遇到一個左遞歸產(chǎn)生式時，會進入無限循環(huán)磷雇。這是因為它盲目應(yīng)用文法產(chǎn)生式而不考慮實際輸入的句子偿警。左角落分析器是自下而 上與自上而下方法的混合體。
左角落分析器是一個帶自下而上過濾的自上而下的分析器唯笙。不像普通的遞歸下降分析器螟蒸，它不會陷入左遞歸產(chǎn)生式的陷阱。在開始工作之前崩掘，左角落分析器預(yù)處理上下文無關(guān)文法建立一個表七嫌，其中每行包含兩個單元，第一個存放非終結(jié)符苞慢，第二個存放那個非終結(jié)符可 能的左角落的集合
分析器每次考慮產(chǎn)生式時诵原，它會檢查下一個輸入詞是否與左角落表格中至少一種非終結(jié)符的類別相容。
三挽放、依存關(guān)系和依存文法
依存文法存在一個共同的基本假設(shè)：文法結(jié)構(gòu)本質(zhì)上包含詞和詞之間的依存（修飾）關(guān)系绍赛。一個依存關(guān)系連接兩個詞，分別是核心詞（ head）和依存詞（ dependent）辑畦。依存關(guān)系可以細分為不同的類型吗蚌，表示兩個詞之間的具體句法關(guān)系。
依存關(guān)系是一個核心詞與它的依賴之間的二元對稱關(guān)系纯出。一個句子的核心詞通常是動詞蚯妇，所有其他詞要么依賴于核心詞，要么依賴路徑與它聯(lián)通暂筝。
依存關(guān)系表示是一個加標簽的有向圖箩言，其中節(jié)點是詞匯項，加標簽的弧表示依賴關(guān)系焕襟， 從中心詞到依賴陨收。
依存文法分析標注關(guān)系 (共14種) 及含義如下：
90年代的文法分析論文99%都是短語結(jié)構(gòu)樹，但后來人們發(fā)現(xiàn)依存文法樹標注簡單鸵赖，parser準確率高务漩，所以后來（特別是最近十年）基本上就是依存文法樹的天下了（至少80%）。
目前研究主要集中在數(shù)據(jù)驅(qū)動的依存文法分析方法卫漫，即在訓(xùn)練實例集合上學(xué)習得到依存文法分析器，而不涉及依存語法理論的研究肾砂。數(shù)據(jù)驅(qū)動的方法的主要優(yōu)勢在于給定較大規(guī)模的訓(xùn)練數(shù)據(jù)列赎，不需要過多的人工干預(yù)，就可以得到比較好的模型。因此包吝，這類方法很容易應(yīng)用到新領(lǐng)域和新語言環(huán)境饼煞。數(shù)據(jù)驅(qū)動的依存文法分析方法主要有兩種主流方法：基于圖（ graph-based）的分析方法和基于轉(zhuǎn)移（ transition-based）的分析方法
1. 基于圖的依存句法分析方法
基于圖的方法將依存句法分析問題看成從完全有向圖中尋找最大生成樹的問題。一棵依存樹的分值由構(gòu)成依存樹的幾種子樹的分值累加得到诗越。根據(jù)依存樹分值中包含的子樹的復(fù)雜度砖瞧，基于圖的依存分析模型可以簡單區(qū)分為一階和高階模型。 高階模型可以使用更加復(fù)雜的子樹特征嚷狞，因此分析準確率更高块促，但是解碼算法的效率也會下降〈参矗基于圖的方法通常采用基于動態(tài)規(guī)劃的解碼算法竭翠，也有一些學(xué)者采用柱搜索(beam search)來提高效率。學(xué)習特征權(quán)重時薇搁，通常采用在線訓(xùn)練算法斋扰，如平均感知器（ average dperceptron）。
目前基于圖的方法的句法分析算法主要有自頂向下（Top Down）啃洋，自底向上（Bottom Up）传货，最大生成樹（Spanning Tree）的方法。
例如在使用最大熵算法進行依存句法分析時就是生成一系列句法樹宏娄，使用最大熵等模型去計算單條依存邊的概率问裕，從里面挑選出概率最大的那一棵作為輸出。
具體可以參考：基于最大熵的依存句法分析
2. 基于轉(zhuǎn)移的依存句法分析方法
基于轉(zhuǎn)移的方法將依存樹的構(gòu)成過程建模為一個動作序列绝编，將依存分析問題轉(zhuǎn)化為尋找最優(yōu)動作序列的問題僻澎。 早期，研究者們使用局部分類器（如支持向量機等）決定下一個動作十饥。近年來窟勃，研究者們采用全局線性模型來決定下一個動作，一個依存樹的分值由其對應(yīng)的動作序列中每一個動作的分值累加得到逗堵。特征表示方面秉氧，基于轉(zhuǎn)移的方法可以充分利用已形成的子樹信息，從而形成豐富的特征蜒秤，以指導(dǎo)模型決策下一個動作汁咏。模型通過貪心搜索或者柱搜索等解碼算法找到近似最優(yōu)的依存樹。和基于圖的方法類似作媚，基于轉(zhuǎn)移的方法通常也采用在線訓(xùn)練算法學(xué)習特征權(quán)重
總的來說攘滩，基于轉(zhuǎn)移的依存句法分析方法是基于動作（或稱轉(zhuǎn)移）和一個分類器實現(xiàn)的，仿照人類從左到右的閱讀順序纸泡，其不斷地讀入單詞漂问，根據(jù)該單詞和已構(gòu)建的句法子樹等信息建立分類模型，分類模型輸出當前狀態(tài)下的最佳動作，然后分析器根據(jù)最佳動作“拼裝”句法樹
目前基于轉(zhuǎn)移的依存句法分析方法主要分為基于棧（Stack Based）和基于列表（List Based）兩類蚤假，其中基于棧的又分為arc-standard算法和arc-eager算法栏饮。
補充知識點：投射和非投射
投射性：如果詞p依存于詞q，那么p和q之間的任意詞r就不能依存到p和q所構(gòu)成的跨度之外
簡單來說就是任意構(gòu)成依存的兩個單詞構(gòu)成一個籠子磷仰，把它們之間的所有單詞囚禁在這個籠子里袍嬉，內(nèi)部的詞的依存關(guān)系只能在這個籠子里，也就是說不存在交叉的依存弧灶平，如下圖所示：
3. 多模型融合的依存句法分析方法
基于圖和基于轉(zhuǎn)移的方法從不同的角度解決問題伺通，各有優(yōu)勢∶癖疲基于圖的模型進行全局搜索但只能利用有限的子樹特征泵殴，而基于轉(zhuǎn)移的模型搜索空間有限但可以充分利用已構(gòu)成的子樹信息構(gòu)成豐富的特征。詳細比較發(fā)現(xiàn)拼苍，這兩種方法存在不同的錯誤分布笑诅。因此，研究者們使用不同的方法融合兩種模型的優(yōu)勢疮鲫，常見的方法有：stacked learning吆你；對多個模型的結(jié)果加權(quán)后重新解碼(re-parsing)；從訓(xùn)練語料中多次抽樣訓(xùn)練多個模型(bagging)俊犯。
四妇多、額外的筆記——語義依存分析
語義依存分析 (Semantic Dependency Parsing, SDP)，分析句子各個語言單位之間的語義關(guān)聯(lián)燕侠，并將語義關(guān)聯(lián)以依存結(jié)構(gòu)呈現(xiàn)者祖。 使用語義依存刻畫句子語義，好處在于不需要去抽象詞匯本身绢彤，而是通過詞匯所承受的語義框架來描述該詞匯七问，而論元的數(shù)目相對詞匯來說數(shù)量總是少了很多的。語義依存分析目標是跨越句子表層句法結(jié)構(gòu)的束縛茫舶，直接獲取深層的語義信息械巡。 例如以下三個句子，用不同的表達方式表達了同一個語義信息饶氏，即張三實施了一個吃的動作讥耗，吃的動作是對蘋果實施的。
語義依存分析不受文法結(jié)構(gòu)的影響疹启，將具有直接語義關(guān)聯(lián)的語言單元直接連接依存弧并標記上相應(yīng)的語義關(guān)系古程。這也是語義依存分析與文法依存分析的重要區(qū)別。
再看一下三個句子的句法依存分析和語義依存分析的對比:
從上邊的對比可以看出,雖然三個句子擁有不同的句子結(jié)構(gòu), 產(chǎn)生了不同的句法分析結(jié)果, 但是三個句子中語言單元之間的語義關(guān)系并沒有發(fā)生變化, 從"吃"這個詞來看, 它的主體, 客體...都沒有發(fā)生變化喊崖。
再看一個例子：
如上例對比了句法依存和語義分析的結(jié)果挣磨，可以看到兩者存在兩個顯著差別：
句法依存某種程度上更重視非實詞（如介詞）在句子結(jié)構(gòu)分析中的作用菲宴，而語義依存更傾向在具有直接語義關(guān)聯(lián)的實詞之間建立直接依存弧，非實詞作為輔助標記存在
兩者依存弧上標記的語義關(guān)系完全不同趋急，語義依存關(guān)系是由論元關(guān)系引申歸納而來，可以用于回答問題势誊，如我在哪里喝湯呜达，我在用什么喝湯，誰在喝湯粟耻，我在喝什么查近。但是句法依存卻沒有這個能力
語義依存與語義角色標注之間也存在關(guān)聯(lián)，語義角色標注只關(guān)注句子主要謂詞的論元及謂詞與論元之間的關(guān)系挤忙，而語義依存不僅關(guān)注謂詞與論元的關(guān)系霜威，還關(guān)注謂詞與謂詞之間、論元與論元之間册烈、論元內(nèi)部的語義關(guān)系戈泼。語義依存對句子語義信息的刻畫更加完整全面。
語義依存關(guān)系分為三類赏僧，分別是主要語義角色大猛，每一種語義角色對應(yīng)存在一個嵌套關(guān)系和反關(guān)系；事件關(guān)系淀零，描述兩個事件間的關(guān)系挽绩；語義依附標記，標記說話者語氣等依附性信息驾中。
五唉堪、歧義
一個眾所周知的關(guān)于歧義例子如下所示，來自 Groucho Marx 的電影肩民，Animal Crac kers (1930):
While hunting in Africa, I shot an elephant in my pajamas. How an elephant got into my pajamas I’ll never know.
雖然我一直get不到這個歧義唠亚，不過歧義也很好理解，就是一句話有不同的理解此改，用我們之前的特征方法很難解決歧義的問題趾撵，但文法分析可以很好地解決：
