句法分析可以分為句法結構分析和依存關系分析。獲取整個句子的句法結構的目的稱為完全句法分析，獲取局部成分的目的稱為局部分析，依存分析簡稱依存分析。
壹般來說，句法分析有三個任務:
確定輸出字符串是否屬於某種語言。
消除輸入句子中的詞匯和結構歧義。
分析輸入句子的內部結構，如構成和上下文。
第二和第三項任務壹般是句法分析的主要任務。
壹般來說，壹個解析器的構建需要考慮兩個部分:壹個是語法的形式化表達和詞條信息的描述，形式化的語法規則構成規則庫，詞條信息由詞典或同義詞提供，規則庫和詞典或同義詞構成句法分析的知識庫；另壹部分是基於知識庫的分析算法。
語法形式化屬於句法理論的研究領域。目前，自然語言處理中廣泛使用的是上下文無關文法(CFG)和基於約束的文法，後者也被稱為unity文法。
簡單來說，句法結構分析方法可以分為兩類:基於規則的分析方法和統計分析方法。
基於規則的句法結構分析方法的基本思想是人工組織語法規則，建立語法知識庫，通過條件約束和檢查消除句法結構歧義。
根據句法分析樹形成方向的不同，人們通常將這些方法分為三種:自頂向下分析法、自底向上分析法以及兩者的結合。自頂向下的分析算法實現了規則推導的過程，分析樹從根節點開始生長，最終形成分析句的葉節點。自底向上分析算法的實現過程就是這個思路，從句子符號串開始，執行不斷規範的過程，最後形成根節點。
基於規則的語法結構分析可以利用手工編寫的規則，分析輸入句子所有可能的句法結構；對於特定的領域和目的，使用有針對性的規則可以更好地處理句子中的壹些歧義和壹些語法外現象。
而對於壹個中等長度的輸入句子，使用覆蓋面較大的語法規則來分析所有可能的句子結構是非常困難的，即使分析了，也很難實現有效的消歧，選出最可能的分析結果；手寫的規則比較主觀，需要泛化，面對復雜的上下文很難保證正確率。手工編寫規則是壹項復雜的工作，規則的領域聯系緊密，不利於句法分析系統向其他領域的移植。
基於規則的解析算法可以成功處理程序語言的編譯，但對於自然語言的處理卻始終難以擺脫困境，因為程序語言所使用的知識受到上下文無關文法子類的嚴格限制，而自然語言處理系統所使用的形式化描述方法卻遠遠超過上下文無關文法的表達能力；而且人在使用編程語言的時候，所有的表達式都要服從機器的要求，這是壹個人服從機器的過程。這個過程是從語言的無限集合到有限集合的映射過程，而在自然語言處理中，恰恰相反，自然語言處理實現了機器跟蹤和服從人的語言，從語言的有限集合推導到無限集合的過程。
完整的語法分析
基於PCFG的基本分析方法
基於概率上下文無關文法的短語結構分析方法可以說是目前最成功的語法驅動的統計句法分析方法，可以看作是規則方法和統計方法的結合。
PCFG是CFG的延伸，例如:
PCFG
當然，同壹符號的不同生成公式的概率之和是1。NP是名詞短語，VP是動詞短語，PP是介詞短語。
基於PCFG的句法分析模型滿足以下三個條件:
位置不變性:子樹的概率不依賴於子樹管轄的詞在句子中的位置。
上下文無關:子樹的概率不依賴於子樹控制範圍之外的詞。
祖先獨立性:子樹的概率不依賴於子樹的祖先節點。
根據上面的語法，“他用花遇見珍妮”有兩種可能的語法結構:
而且我們可以把樹中的所有概率相乘得到兩個子樹的整體概率，選擇概率較大的子樹作為最佳結構。
像嗯，PCFG有三個基本問題:
給定壹個句子w = w1w2 … wn和語法G，如何快速計算概率P(W|G)？
給定壹個句子w = w1w2 … wn和語法g，如何選擇句子的最佳結構？也就是說，句法結構樹T被選擇為具有最大概率。
給定PCFG G和句子w = w1w2 … wn，如何調整G的概率參數使句子的概率最大化？
首先是第壹個問題。在HMM中，我們使用前向算法和後向算法來計算觀察序列的O概率。同樣，這裏我們用向內算法和向外算法計算P(W|G)。
首先，我們定義內向變量αij(A ),它與正向變量相似但不同。非終結符A的αij(A)推導出W中字符串wiw(i+1)…wj的概率，那麽P(W|G)自然等於α1n(S)，S為起始符號。計算是從起始符號s推導出整句的概率W=w1w2…wn。
所以只要有壹個αij(A)的遞推公式，就可以計算出P(W|G)，遞推公式如下:
根據定義，αii(A)自然等於符號A輸出wi的概率；αij(A)的計算思路是，這個子串wiw(i+1)…wj可以分成兩部分，前壹部分wiw(i+1)…wk由非終結符b生成，後壹部分wkw(k+1)…wj由非終結符c生成，這樣依次乘以概率，壹個大問題可以分成兩個小問題，兩個小問題可以進壹步
以下是內部變量計算方法的示意圖:
這個問題也可以用外向算法解決。
首先，定義了外向變量。βij(A)是在推導語句W = W1Wn(暗示A將生成WIW)的過程中，初始符號S將生成符號串W 1 w2…W(I-1)AW(J+1)…Wn的概率也就是說，βij(A)是S推導以節點A為根節點的子樹以外的其他部分的概率。
《統計自然語言處理》(第二版)這本書錯了。這裏我給出自己的理解。書中給出的算法步驟如下:
很明顯，錯誤，初始化已經初始化了結果，所以這個算法沒什麽，正好等於1。
這是作者對外向變量定義的模糊理解。外向變量的定義上面給出了，有壹句話“它暗示A會生成wiw(i+1)…wj”。問題是A會產生WIW (I+1) … WJ。這是條件還是推論？
看這個算法的初始化意義。說β1n(A)，當A=S時，是1，不代表S是0。這是什麽意思？意思是句子“暗示A將生成Wiw (I+1) … WJ”是條件，β1n(S)已經暗示S生成W = W1W2 … WN，所謂W1W2 … W (I-1)。s，所以概率自然是1。
但是第三步，作者明白了什麽？作者以“暗示A將生成Wiw (I+1) … WJ”這句話作為推論，認為在β1n(S)中，S將生成W = W1W2 … WN是壹個推論，真的是恰到好處，要求的結果是S將生成W = W1W2。
那我的理解是什麽？用這個公式計算出來的β1n(S)確實是正確的，含義其實也包含了那句“它暗示A會生成WIW (I+1)...WJ”是壹個推論，但右邊公式中連續遞歸生成的β1n(S)才是”。
我傾向於在第三步中給β1n(S)加壹個星號來表示意思上的不同。
書中還給出了外向變量的計算方法示意圖，我覺得也很費解:
他說βij(A)是這兩種情況的概率和。我們知道J比I大，所以這個圖中的K既比I小又比J大，是不是很搞笑？只能說圖上兩個C不是壹個C，K也不是壹個K。
那為什麽我理解為壹？除了同樣的字母，他前面說過“B的形狀-& gt；AC或b->；規則CA "和"使用b->；AC或b->；CA”兩個規則的情況，這顯然是給人壹種順序交換的誤解。
另外，對內向變量的使用也是不壹致的，所以可以說這本書對外向算法的解釋是很失敗的。而且外向算法的計算還是需要內向算法的遞歸，直接用內向算法確實不錯，外向算法需要定義更多的變量。
然後是第二個問題，就是選擇最佳的句子結構，即給定壹個句子w = w1w2 … wn和語法g，
選擇概率最大的語法結構樹。這個問題類似於HMM中的問題，仍然采用動態規劃的思想來解決。最後用CYK算法生成概率最大的句法結構樹。
第三個問題是如何調整G的概率參數，使給定PCFG G和句子W = W1W2 … Wn的句子概率最大化。與HMM相反，PCFG在這裏使用的算法叫做內向算法。和正反演算法壹樣，也屬於壹種EM算法。其基本思想是給G(滿足規範化條件)的產生式隨機賦壹個概率值，得到文法G0。然後根據G0和訓練數據，可以計算出每條規則的使用次數的期望值，用該期望值進行最大似然估計，得到文法g的新的參數值，新的文法標記為G1，然後循環執行，g。
PCFG只是壹個特殊的上下文無關語法模型。根據PCFG的模型和句子，句子的句法分析和語法結構樹的生成依賴於CYK算法。CYK算法是用於確定任何給定的字符串W是否屬於上下文無關文法的算法。
基於PCFG的句法分析模型存在很多問題，例如，由於PCFG沒有對詞匯進行建模，所以它對詞匯信息不敏感。因此，人們提出了詞匯化短語結構分析器，有效地提高了基於PCFG的句法分析器的能力。
而且我們上面也提到了PCFG的三個獨立假設，這也導致了規則之間缺乏結構依賴(就像HMM的三個假設並不完全合理)，而在自然語言中，每個非終結符產生的概率往往與其上下文結構有關，於是有人提出了壹種方法來細化非終結符，並用其父節點的句法標記信息來標註每個非終結符。
D.Klein提出了壹種具有潛在註釋的上下文無關文法(PCFG-LA ),它使得非終結符的精化可以自動進行。為了避免陷入局部最優，對EM算法進行了改進，並提出了壹種分層的“分裂-合並”策略，以獲得精確而緊湊的PCFG-拉模型。基於PCFG-LA的Berkeley分析器作為非詞匯化分析器的代表，在性能和運行速度方面是開源短語結構分析器中最好的。其語法樹如下:
普通語法樹和PCFG-拉語法樹的比較實例
這個X是壹個隱含標記，xi的取值範圍壹般是人為設定的，壹般取1到16之間的整數。而且PCFG-LA也類似於HMM模型，原始非終結點對應HMM模型中的觀察輸出，隱含標記對應HMM模型中的隱含狀態。
淺層語法分析(局部語法分析)
在完整的語法分析中，確定壹個句子所包含的所有句法信息以及句子中各成分之間的關系是壹項非常困難的任務。到目前為止，句法分析器的各個方面都難以達到令人滿意的程度。為了降低問題的復雜性，獲得壹定的句法結構信息，淺層句法分析應運而生。
淺層語法分析只需要識別壹個句子中的壹些結構，比如非遞歸的名詞短語和動詞短語，通常稱為語塊。
淺層句法分析將句法分析分解為兩個主要的子任務，壹是詞塊的識別和分析，二是詞塊之間的依存關系分析。其中，詞塊的識別和分析是主要任務。淺層解析在壹定程度上簡化了解析的任務，也有利於解析系統在大規模真實文本處理系統中的快速應用。
基本名詞短語是詞塊中的壹個重要類別，指簡單的、非嵌套的名詞短語，沒有其他子短語，基本名詞短語在結構上是獨立的。例子如下:
基本名詞短語識別是從壹個句子中識別出所有的基本名詞短語。按照這種理解，壹個句子中成分的總和可以簡單地分為兩類:堿基NP和非堿基NP，於是堿基NP的識別就變成了壹個分類問題。
base NP有兩種表示方式，壹種是括號分隔，另壹種是IOB表示法。括號分離法是用方括號定義base NP的邊界，裏面是base NP，外面不屬於base NP。在IOB記法中，字母B表示基數NP的開始，I表示當前單詞在基數NP內，O表示該單詞在基數NP外。
基於SVM的基本名詞短語識別方法
因為基本NP識別是壹個多值分類問題，而基本SVM算法解決的是壹個二值分類問題，所以壹般可以采用成對的方法和壹個對另壹個的方法。
壹般情況下，SVM需要從上下文的單詞、詞性和基本NP標誌中提取特征來完成判斷。壹般當單詞窗口長度為5(當前單詞及其前後兩個單詞)時，識別效果最好。
基於WINNOW的基本名詞短語識別方法
WINNOW是壹種解決二分法問題的錯誤驅動的機器學習方法，可以從大量不相關的特征中快速學習。
WINNOW的稀疏網絡(SNoW)學習結構是壹種多類分類器，專門用於處理特征識別領域的大規模學習任務。WINNOW算法具有處理高維獨立特征空間的能力，而自然語言處理中的特征向量恰恰具有這種特性，所以WINNOW算法也常用於詞性標註、拼寫錯誤檢查和文本分類。
簡單WINNOW的基本思想是，給定特征向量、參數向量和實閾值θ，將參數向量全部初始化為1，代入訓練樣本，求特征向量和參數向量的內積，並與θ進行比較。大於θ則判定為正例，小於θ則判定為反例。將結果與正確答案進行比較，並根據結果改變權重。
如果把正例估計成反例，那麽就把X的權展開，它的原值是1。如果反例被估計為正例，那麽原值為1的X的權重降低。然後重新評估和改變重量，直到訓練完成。
這其實讓我想起了LR算法，因為LR算法也是特征向量和參數向量的內積。最後送到Sigmoid函數得到判斷結果，然後大於0.5的值為正例，小於0.5的值為反例。其實只要Sigmod函數輸出0.5，輸入就是WINNOW算法中的真實閾值θ。但不同的是WINNOW算法只確定大小，不確定概率，而LR使用Sigmoid函數給出概率。LR利用這個給定的概率，通過最大化訓練集的生成概率來調整參數，而WINNOW則是壹種直接而樸素的錯誤情況，來增加或減少相關參數。Visual LR比WINNOW收斂速度更快，因為它使用了梯度下降，WINNOW的優勢是可以處理大量的特征。
基於條件隨機場的基本名詞短語識別方法
基於條件隨機場的基NP識別方法與SVM方法有幾乎相同的效果，優於基於WINNOW的識別方法、基於MEMM的識別方法和感知器方法，基於條件隨機場的識別方法在運行速度上比其他方法有明顯的優勢。
依存語法理論
在自然語言處理中，我們有時不需要或者只需要整句的短語結構樹，還需要知道句子中詞與詞之間的依存關系。用詞與詞之間的依存關系來描述語言結構的框架就成了依存語法，也叫依存語法。利用依存語法進行句法分析也是自然語言理解的重要手段之壹。
有人認為所有的結構語法現象都可以概括為三個核心:關聯、組合、換位。句法關聯確立了詞與詞之間的從屬關系，由主導詞和從屬詞組成。謂語中的動詞是句子的中心，支配其他成分，不受其他任何成分支配。
依存語法的本質是壹種結構語法，主要研究構造句子時深層語義結構反映到表層語法結構的情況和條件，謂語和體詞的共現關系，並據此劃分謂語的詞性。
有三種常用的依賴關系結構圖:
計算機語言學家J. Robinson提出了依存語法的四個公理:
壹個句子只有壹個獨立成分。
壹個句子的所有其他成分都從屬於某個成分。
沒有壹個組件可以依賴於兩個或多個組件。
如果成分A直接從屬於成分B，而成分C位於句子中的A和B之間，那麽成分C屬於成分A、成分B或A和B之間的成分..
這四個公理相當於依賴圖和依賴樹上的形式約束:單父節點、連通、無環和投射，從而保證了句子的依賴分析結果是有根樹結構。
這裏提到了可投射性。如果單詞之間的依存弧繪制時沒有任何交集，則它們是射影的(參考上面的兩個有向圖)。
為了便於理解，我國學者提出了依存結構樹應滿足的五個條件:
簡單節點條件:只有端點，沒有非端點
單父節點條件:除了根節點沒有父節點外，所有節點都只有壹個父節點。
單根節點條件:壹棵依賴樹只能有壹個根節點，支配其他節點。
不相交條件:依賴樹的分支不能彼此相交。
互斥條件:自上而下的支配關系和自左而右的先行關系互斥。如果兩個節點之間存在支配關系，那麽它們不能存在於先行關系中。
這五個條件有交集，但完全基於依存表達式的空間結構，比四個公理更直觀實用。
Gaifman 1965給出了依賴文法的形式化表示，證明了依賴文法與上下文無關文法沒有區別。..
類似於上下文無關語法的語言形式限制了被分析語言的投射性，難以直接處理含有非投射現象的自由語序語言。基於約束滿足的約束文法和相應的依存分析方法是在20世紀90年代發展起來的，可以處理這類非投射語言問題。
基於約束滿足的分析方法以約束依存文法為基礎，將依存句法分析視為壹個可以用約束滿足問題來描述的有限構造問題。
約束依賴文法使用壹系列正式的和描述性的約束來移除不滿足約束的依賴分析，直到留下合法的依賴樹。
生成依賴分析、判別依賴分析和確定依賴分析是數據驅動的統計依賴分析中三種有代表性的方法。
生成依賴分析方法
生成式依存分析方法利用聯合概率模型生成壹系列依存句法樹並賦予其概率分值，然後利用相關算法尋找概率分值最高的分析結果作為最終輸出。
生成依賴分析模型使用方便，其參數訓練只尋找訓練集中相關組件的計數，計算先驗概率。但在產生式方法中使用了聯合概率模型，然後在分解概率乘積時進行近似假設和估計。而且由於全局搜索，算法復雜度高，所以效率低，但這類算法在精度上有壹定優勢。但是，類似於CYK算法的推理方法使得這類模型難以處理非投影問題。
判別依賴分析方法
判別依賴分析方法采用條件概率模型，避免了聯合概率模型所要求的獨立性假設(考慮到判別模型CRF拋棄了生成模型HMM的獨立性假設)，訓練過程是尋找使目標函數(訓練樣本的生成概率)最大化的參數θ(類似於Logistic回歸和CRF)。
判別法不僅在推理上進行窮舉搜索，而且在訓練算法上具有全局最優性。需要對訓練樣本重復句法分析的過程來叠代參數。訓練過程也是壹個推理過程，訓練和分析的時間復雜度是壹致的。
確定性依賴方法
確定性依存分析方法在特定方向上逐個取壹個要分析的詞，對每個輸入詞產生單壹的分析結果，直到序列中的最後壹個詞。
這種算法在每壹步分析中都要根據當前的分析狀態進行決策(比如判斷是否依賴於前壹個詞)，所以這種方法也叫決策分析法。
確定性解析方法的基本思想是通過壹個確定的解析動作序列，得到壹個唯壹的句法表達式，即依賴圖(有時可能有回溯和打補丁)。
短語結構與依存結構的關系
短語結構樹可以壹壹對應地轉換成依存樹，反之亦然。因為依存關系樹可以對應於多個短語結構樹。