成分句法分析 & 依存句法分析 Parsing 知識圖譜

句法分析 (Parsing, Syntactic Analysis) 是自然語言處理（以下都簡稱 NLP）領域最核心的技術之一，旨在分析一個句子的語法結構、成分和詞語之間的依存關係，是語法校驗、語意解釋、對話理解、機器翻譯等應用的基礎。

句法分析一般會分爲成分句法分析 (Constituency Parsing) 與依存句法分析 (Dependency Parsing) ，藉助下圖可以清晰地看出兩者區別：

圖1 成分與依存句法分析產生的語法樹的對比[1]

前者基於詞語結構的文法，後者通過詞語間的語法關係的文法。通俗理解就是，前者是從一個句子、分解爲若幹個詞語組、最後到分解到一個單詞，建立語法結構分析；後者是通過詞語之間的語言學聯繫，建立語法結構分析。

下面 下麪將分別詳述兩種句法分析的經典演算法（第一種內容較多）

一、成分句法分析

1. 上下文無關文法

Context-Free Grammar (以下簡稱 CFG)，是描述計算機程式語言和自然語言非常有效的語法。本質上，CFG 是描述語言語法結構的一組形式規則。對於程式語言，這種語法很適用，但我們都知道，人類使用的自然語言，是上下文有關的。那麼爲什麼要用這種不符合現實的語法呢？

以我的理解，因爲 NLP 本質上還是用計算機語言去處理自然語言，必須基於機器能懂的語法去擴充套件。很多程式語言都是 CFG。當然用上下文有關文法去處理也可以，但這裏面涉及到程式語言設計的複雜度、可延伸性、處理效率等因素，是一個綜合權衡的結果。

那麼，接下來就看看 CFG 在數學上的定義。通常可被定義爲四個要素：

G={N, T, R, S}

1. 非終結符 (Non-terminal) 集合 N。 在 NLP 中一般爲詞性 (Part-of-Speech) 的集合，如名詞、動詞、形容詞等；
2. 終結符 (Terminal) 集合 T。 在 NLP 中一般爲一個詞彙表；
3. 推導規則 (Rules of Productions) 集合 R。 形式爲 A → β，其中 A 必須爲 單獨一個非終結符 ，而 β 可以由非終結符或/與終結符自由組合而成，β ∈ (N ∪ T)*
4. 起始符號 S，S 屬於非終結符。

最終得出的語法結構分析的形式有多種，最常見的是語法樹，下面 下麪舉一個具體的例子：
圖2 CFG 句子分析的簡單例子

當然，在實際情況中，集合 T 會是一個非常龐大的詞彙表。

運用 CFG 做句法分析，其實就是對每個輸入的字串（即句子），搜尋並賦予合適的語法結構，如上圖的語法樹。那麼，CFG 具體是怎麼完成這個任務的呢？

最基礎的 Parsing 搜尋演算法有兩種，自頂向下和自底向上演算法 (Top-down/Bottom-up Parsing)

圖3 自頂向下搜尋的核心流程

如上圖3，自頂向下演算法。

步驟1：從根節點開始，根據文法規則，優先擴充套件當前最左側的非終結符；

步驟2：NP 有兩種擴充套件模式，如果選擇了 Det NP ，那麼無法與第一個終結符（單詞 ‘I’）匹配，回溯至上一層 NP；

步驟3：NP 擴充套件爲 Pron，然後匹配到了終結符（單詞 ‘I’），回溯，從左到右對下一個未進行擴充套件的終結符進行相似的處理。

直至最後，所有的終結符（單詞）都被匹配到了，終止流程。

圖4 自底向上搜尋的核心流程

如上圖4，自底向上演算法。

步驟1：從第一個輸入的終結符開始，根據文法規則，向上匹配非終結符；

步驟2：，因爲有 N → Pron 的規則，所以 Pron 可以直接向上匹配。但再往上就沒有規則匹配了，因此處理下一個輸入符；

步驟3：，第2個輸入符也向上匹配終結符，但 NP 和 V 沒有可組合的文法規則，因此繼續推進下一個輸入符；

直到掃描到最後兩個單詞，對應的 adj 和 N 可以組成 NP，然後 Det 和 NP 組成 NP，以此類推，最後可以組成相同的語法樹。

兩者對比
Top-down 會浪費較多時間在探索不能匹配到輸入句子的情況上，如圖3步驟2；Bottom-up 可能會得出不符合真實語法的語法樹（即錯誤判斷句子的語法結構和部分詞語的詞性）。在這兩點上，兩者互相避免了對方的情況。

此外，Top-down 還有以下缺點：

1. 當出現類似 NP → Det NP 這種文法規則，如果句子較長以及文法規則較多，那麼很有可能會出現無限遞回的情況；

2. 無法處理不合語法規則的句子。

而這兩種基礎的演算法，還有共同的缺陷：

1. 由於不牽涉任何語意層面處理，因此無法處理 句子歧義 問題，即同一個句子會有不止一種合乎文法的結構，如下圖5；

2. 沒有對每個節點各種擴充套件賦予權值，因此無法給出一個最合適的語法樹。

圖5 句子結構層面的歧義[2]]

因此，在這兩者基礎上有很多優化的演算法，下文即將介紹到的 CKY 演算法，就是自底向上的一種。

2. CNF 範式

在詳述 CKY 演算法前，需要先簡單瞭解一下 CNF (Chomsky Normal Form, 喬姆斯基範式)。CNF 是 CFG 文法規則的一種形式，當一個 CFG 只存在以下文法規則，那它就是符合 CNF 的：

A → B C，A → a，S → ε

ABC 皆爲非終結符，a 爲終結符，S 爲起始符，ε 爲空串。

值得一提的是，基於 CNF 得出的語法樹會是一棵 二元樹，其二分性質能有效應用到後面介紹到的很多演算法中。

每條 CFG 的文法規則都能轉化爲等價的 CNF，分爲以下幾種轉換：

1. 當起始符出現在右側時，需要新增規則 S0 → S，使原本的 S 變爲普通非終結符；

2. 非終結符與終結符混合。如：A → b C，可轉換爲兩條規則：A → B C，B → b；

3. 右側多於2個非終結符。如：A → B C D，可轉換爲兩條規則：A → B X，X → C D；

4. 右側爲單個非終結符或空串。如：A → B / A → ε，可直接移除這些規則，如果 B 有相應的推導規則，那麼 A 可以直接指向 B 指向的規則。

另外，可通過 CNF 創造出喬姆斯基鄰接 (Chomsky-adjunction)，縮小語法規模。

如：VP → VBD NP PP*，可分解爲：

VP → VBD NP PP，VP → VBD NP PP PP，…

而使用 CNF 則可以簡單描述爲：

VP → VBD NP，NP → NP PP

3. CKY 演算法

如上文所說，CKY 演算法 (Cocke–Kasami–Younger algorithm，或 CYK) 是一種相對高效的 Bottom-up 演算法，運用了動態規劃的思想。

首先，我們建立一個表格，儲存一個句子的單詞對應的詞性。若句子的單詞數爲 n，則建立一個 (n+1)*(n+1) 的矩陣表格，使用它的上半區三角，如下圖6：

圖6 CKY 識別矩陣表格初始化

此處不列出詳細的文法規則，但要注意的是，一個單詞可能會對應多個詞性，詞性之間也不止一種組合方式。與基礎的 Bottom-up 每次只選取一種匹配/組合的方式不同，CKY 把每種可能都記錄在單元格中。

圖7 完整 CKY 識別矩陣表格

從上圖7中可見，到最後可以匹配出2棵符合文法規則、以 S 爲根節點的語法樹結構（爲了直觀，一些單元格裡的詞性做了重複處理）。與基礎的 Bottom-up 演算法相比， CKY 能有效過濾那些無法形成以 S 爲根節點的 無效語法樹。

但同時，我們也應該發現了，像上面這個句子，CKY 識別後返回的是兩課語法樹，並且都是符合實際語法的：「預訂到 Huston（地名）的航班」 和 「通過 Huston（人名）預訂航班」。可見 CKY 演算法無法解決 句子歧義 問題，無法選出最符合實際的一種語法結構（而按照我們日常用語，可以判斷出前一種句子語意是比較合理的）。

接下來介紹的演算法，可以一定程度上解決這個問題。

4. Probabilistic CFG

概率化上下文無關文法（下面 下麪簡稱 PCFG），基於 CFG 文法，給每條文法規則賦予一個事先確定（通過統計語料庫或其它方法）的先驗概率，如 p(A → β), 0<p<1

其中，對於每個有文法推導式的非終結符，它的所有推導式的概率之和必爲1。

比如 A 有：A → B C，A → D，A → a，這三條規則的概率之和爲1。

基於上一節的 CKY 演算法得出的不同語法樹，直接分別把每棵樹的每條文法規則的概率連乘，最後選出總概率最大的語法樹即可。

爲什麼說是一定程度上解決歧義問題呢？確實，PCFG 可以給出一棵 概率上「最常見」 的語法樹，但還是有缺陷的。

首先，因爲基於上下文無關文法，PCFG 也是很直接粗暴地預設了文法規則之間相互獨立，忽略了句子成分（詞語詞性）之間的依賴關係。比如在英語中，當一個名詞短語 NP 是句子中的賓語時，它是代詞 Pronoun 的機率遠高於它不是代詞（比如專有名詞 Proper noun）的機率。以下是一個語料庫中的分佈情況：

圖8 名詞短語分別爲賓語和主語時，是代詞的概率分佈[3]

但是，PCFG 無法知曉這個短語是賓語還是主語，無法把這些資訊運用到概率計算中，導致計算出來的總概率與實際語法還是有一定程度出入的。

5. 詞彙化 PCFG

詞彙化概率上下文無關文法 (Lexicalized PCFG)，給每條文法規則指定一個 中心詞 (head)，讓文法規則擴充套件爲 詞彙化語法 (Lexicalized grammar)。中心詞可通過語言學知識事先確定，比如一個句子的中心詞一般是動詞詞組 VP，VP 的中心詞是動詞 V 等。

語法樹結構與 CFG 保持一致，增添了每個節點的中心詞，如下圖9：

圖9 L-PCFG 語法樹

其中，有上劃線的代表中心詞。

接下來，需要進行一些統計概率上的計算。

1. 首先將文法規則擴充套件爲爲（以上圖9爲例子）：
   S(questioned)→NP(lawyer) VP(questioned)

2. 每條文法規則的概率可以以下方式轉換爲條件概率：
   p(S(questioned)→NP(lawyer) VP(questioned))
   = p(S →NP VP, lawyer | S, questioned)

   等號右邊的條件概率即：當確定非終結符 S 的中心詞爲 ‘question’ 時，S 擴充套件爲 NP+VP 且非中心詞爲 ‘lawyer’ 的概率。

3. 上述等式比較難理解，但根據條件概率的 鏈式法則 ，可以進一步分解爲：
   p(S →NP VP, lawyer | S, questioned) =
   p(S→NP VP | S, questioned) * p(lawyer | S → NP VP, S, questioned)

   等號右邊第1個概率爲：當確定非終結符 S 的中心詞爲 ‘question’ 時，S 擴充套件爲 NP+VP 的概率；
   第2個概率爲：當確定 S 擴充套件爲 NP+VP 且中心詞爲 ‘question’ 時，非中心詞爲 ‘lawyer’ 的概率。

4. 我們很難直接得出以上的概率，但可以用 極大似然估計 基於語料庫訓練集近似估計概率。但考慮到 數據稀疏 問題（某些詞彙數據在訓練集中正好偏少或沒有，導致概率爲0），所以需要採用平滑方法避免這種情況。如步驟3等號右邊第1個概率可以進一步分拆爲：

圖10 極大似然估計法，直接在訓練集中累計對應詞彙/語法數據的數量

​然後，以一個 平滑參數 λ1 表示上面兩個式子的權重 (0<λ<1)。因此有：

p(S→NP VP | S, questioned)

= λ1e1 + (1-λ1)e2

同理，步驟三等號右邊第2個概率也做這種處理，最後就能求出原本文法規則的概率了。

詞彙化 PCFG 能有效解決上述主語賓語的相關歧義，但在語言分析中，還有很多種類的歧義，下面 下麪列舉幾種常見的：

1. 介詞短語修飾歧義 (PP attachment ambiguity)，如：
   He killed the man with a knife.

   不結合上下文，我們無法得知 with 是修飾 killed 的還是 knife 的。

2. 連詞範圍歧義 (Coordination scope ambiguity)，如：
   Shuttle expert and NASA executive Fred Gregory appointed to board.

   不能確定第1個劃線短語（太空梭專家）是和第二個一起修飾 Fred Gregory 還是指的是另一個人。

3. 形容詞修飾歧義 (Adjectival modifier ambiguity)，如：
   He painted her sitting on the step.
   不能確定劃線部分是在修飾 he 還是 her。

所以，基於以上介紹的分析演算法，至今還有很多研究人員不斷改進演算法或尋找新的演算法去提高效能，接下來簡單介紹幾個評價演算法效能的參數。

6. 演算法效能評價

​Parser evaluation，基於一個已完成對每個句子人工標註（詞性、結構）、被視爲「黃金標準」的語料庫，目標句法分析器對裏面的句子進行分析，得出的結果與「標準」作對比。對比內容爲 非終結符的取值、起始點、結束點（一般針對有多分支的非終結符）。

圖11 句法分析演算法的3個參數

對於上圖11，假設這個句子的「標準」標註如中間表格所示，然後又有有個分析器得出右邊圖表的標註。我們設立以下3個標準：

1. 召回率 (Recall)：以行爲單位，Parser 中標註與 Standard 標註完全吻合的數量：Standard 標註的數量
2. 準確率 (Precision)：以行爲單位，Parser 標註與 Standard 標註完全吻合的數量：Parser 標註的數量
3. F1 參數：F1 = 2PR / (P+R)

如圖11，召回率 R=2/4，準確率 P=2/3，F1=8/14

另附：

圖12 幾種基礎句法分析的得分

最後提一下，所有基於 CFG 的演算法，計算複雜度都是處於 $O(|R|^2*|N|^3)$ 的量級。

二、依存句法分析

1. 依存關係結構

每棵成分語法樹都能轉換爲依存關係樹，原理也是先找出每個成分的中心詞，然後讓另一個非中心詞依賴於此中心詞，轉化方式如下圖13：

圖13 成分語法樹轉化爲依存關係樹

上圖右邊的依存關係樹的每條連線上，還要加上 依賴標籤 ，下圖14是一些標籤的例子：

圖14 部分依賴關係標籤及其描述

相比於 CFG，依存關係語法更關注與詞語間關係、高度詞彙化，能更好的應用於 問答系統 與 關係抽取 等場景。另外，這種語法對就這種詞語的順序要求相對比較低，所以在處理一些語法複雜、次序排列更靈活的語言時，依存關係語法比 CFG 更有優勢。

經過依存關係語法處理後，一個句子的語法結構一般以以下形式展現：

圖15 依存句法分析結構

這樣的數學結構有以下特性：

1. 需要額外新增一個根節點 ROOT，它不會有輸入弧，而且對句子裡每一個單詞（包括標點），它都有唯一一條路徑；

2. 除根節點外，每個單詞都有且只有一條輸入弧；

3. 如果這個結構是從 CFG 結構轉化而來（見上一節），那麼它就會是圖15這樣的形式——沒有交叉的弧線。這是我們稱這種結構是 Projective 的，這也是我們實際處理過程中比較常見的形式。

接下來介紹給一個句子剖析賦予這種結構的一種基礎演算法。

2. Transition-based D-Parsers

基於轉移的依存句法分析，將依存關係結構的構建過程當做一個 動作序列，本質上是以貪婪演算法的思想（總是做出在當前看來是最好的選擇，求得區域性最優解）去確定這個最有動作序列。其中最常被提到的是 MALTparser。

首先是一些數學定義：

1. 一個用於處理詞彙依存關係的 堆疊 σ，從 ROOT 開始；

2. 一個儲存待處理詞彙的 緩衝器 β，初始化時爲整個句子；

3. 產生的依存關係弧的 集合 A，開始時爲空。

整個演算法過程只有以下4種動作：

1. Shift：把緩衝器內的最左邊單詞移動到堆疊中；

2. Left arc：此時堆疊中最右側的單詞與緩衝器最左側的單詞形成依存關係，後者爲中心詞，前者成爲後者的左側子節點；在 A 中新增這個依存關係，並把非中心詞從堆疊中移除；

3. Right arc：如上，兩者形成依存關係，但前者爲中心詞，後者成爲前者的右側子節點；在 A 中新增這個依存關係，保留堆疊中的單詞，將非中心詞也加到堆疊中；

4. Reduce：此時堆疊最右邊的單詞無法與緩衝器中僅剩的最後一個單詞產生依存關係，將堆疊中的最右側的單詞移除。

當 緩衝器爲空 時，終止演算法過程。

具體例子見下圖：

圖16 Transition-based D-Parsers 例子

但是，上面這些動作，選擇哪個並沒有固定的規則，需要用一些判別式分類器，比如 SVM、最大熵分類器、DNNs+LSTM 等，這些涉及到機器學習的技術，每個都是需要很長篇幅去講，後面我會另開一個系列。

此外，也有更多的更有效、效能更高的 Parser，比如基於神經網路的、基於圖的等等，不一一詳述。但最後，依存句法分析演算法的效能評估方法也是要提一提。

其實很簡單，也是基於一個人工標註的語料庫，對比內容是依存關係，有以下兩個參數：

1. Unlabeled attachment score (UAS) , 正確標記關係的比率；

2. Labeled attachment score (LAS), 正確標記關係且關係標籤正確的比率 ;

具體例子見下圖（UAS 只要求前兩項相同，LAS 要求整行相同）：

圖17 評估依存句法分析演算法的參數

參考 References：

[1] https://en.wikipedia.org/wiki/Phrase_structure_grammar

[2][3] Jurafsky, D. and Martin, J.H. Speech and Language Processing

[4] University of Washington, Course Ling-571

[5] Manning, C. Stanford University, Natural Language Processing with
Deep Learning

[6] https://blog.csdn.net/wang_yi_wen/article/details/8906121

[7] https://blog.csdn.net/kunpen8944/article/details/83349880

Thanks for reading ; )