視頻列表：
43 句法分析技術(shù)（一）
44 句法分析技術(shù)（二）
45 句法分析技術(shù)（三）
46 句法分析技術(shù)（四）
47 句法分析技術(shù)（五）

43 句法分析技術(shù)（一）

第七章 句法分析技術(shù)

什么是句法分析

• 判斷輸入的詞序列能否構(gòu)成一個合乎語法的句子，確定合乎語法句子的句法結(jié)構(gòu)
• 運用句法規(guī)則和其他知識將輸入句子中詞之間的線性次序，變成一個非線性的數(shù)據(jù)結(jié)構(gòu)（例如短語結(jié)構(gòu)樹或有向無環(huán)圖）
• 
  

為什么要進行句法分析

• 例一：音字轉(zhuǎn)換例
  一只小花貓
• 例二：機器翻譯示例
  Jan hit the girl with long hair
  Jan hit the girl with a hammer
• 例三：信息檢索例
  哪個球隊獲得了亞洲杯冠軍？
  日本隊擊敗中國隊獲得亞洲杯冠軍
• 例四：語法歧義：一個句子對應著幾種句法分析結(jié)果
  “咬死了獵人的狗”
  “那只狼咬死了獵人的狗”
  “那只咬死了獵人的狗失蹤了”

漢語句法分析的獨特性

根據(jù)朱德熙《語法答問》《語法講義》

• 漢語沒有形態(tài)
• 語序靈活
• 詞類和句法成分不存在一一對應的關(guān)系
• 漢語句子的構(gòu)造原則與詞組的構(gòu)造原則基本上是一致的
• 漢語語法形式化工作滯后

句法分析系統(tǒng)

一個句法分析系統(tǒng)通常由兩部分組成：

形式語法體系

• 匹配模式
  基于模板的方法
  短語結(jié)構(gòu)語法
• 句法規(guī)則
• 特征制約
• 語義解釋
• 擴充轉(zhuǎn)移網(wǎng)絡
• 樹鄰接語法(TAG)

44 句法分析技術(shù)（二）

• 基于合一運算的語法（廣義短語結(jié)構(gòu)語法、詞匯功能語法、功能合一語法、基于中心詞驅(qū)動的短語結(jié)構(gòu)語法(HPSG)）
• 基于詞的語法（鏈語法、依存語法、配價語法）

分析控制機制

• 模式匹配技術(shù)

• 基于短語結(jié)構(gòu)語法分析算法（厄爾利（ Earley ）分析算法、富田勝（ Tomida ）分析算法、線圖（Chart）分析算法、確定性分析算法等等）

• 基于擴充轉(zhuǎn)移網(wǎng)絡的分析算法

• 鏈分析算法

• 
  $Ｇ=(N,\sum ,P,S)$是一個文法，α→β ∈ P

• 0型文法
  對α→β不作任何限制

• 1型文法
  |α|≤|β|

• 2型文法：上下文無關(guān)文法
  α∈N

• 3型文法：正則文法
  A→aB或A→a: G是右線性文法，L(G)是3型語言
  A→Ba或A→ａ: G是左線性文法，L(G)是3型語言

• 在自然語言處理中研究和應用較多的是2型文法和3型文法

推導

• 一個字串的推導是一系列文法規(guī)則的應用
  S→NP VP →John V NP →John V NP PP →John ate fish P NP →John ate fish with bone
• 這一推導的過程可以用分析樹來表示
  
  根據(jù)某上文下無關(guān)文法從起始非終結(jié)符可能推導出的所有字串的集合稱為由該CFG定義的語言

CFG的形式化定義

一個CFG是一個四元組$Ｇ=<N,\sum ,P,S>$
N是非終結(jié)符的集合
$\sum$是終結(jié)符的集合
P是產(chǎn)生式的集合，其中每個產(chǎn)生式形如:
$A\to \alpha$
A是非終結(jié)符
$\alpha$是由終結(jié)符與非終結(jié)符構(gòu)成的字串
S是一個起始非終結(jié)符

上下文無關(guān)文法示例（context free grammar）

語言的合法性

概率上下文無關(guān)文法（Probabilistic (Stochastic) Context Free Grammar）

隨機上下文無關(guān)語法可以直接統(tǒng)計語言學中詞與詞、詞與詞組以及詞組與詞組的規(guī)約信息，并且可以由語法規(guī)則生成給定句子的概率。

定義

定義：一個隨機上下文無關(guān)語法（PCFG）由以下5部分組成：
（1）一個非終結(jié)符號集N
（2）一個終結(jié)符號集∑
（3）一個開始非終結(jié)符S∈N
（4）一個產(chǎn)生式集R
（5）對于任意產(chǎn)生式r∈R，其概率為P?
產(chǎn)生式具有形式X→Y，其中，X∈ N, Y ∈(N∪ ∑)*
${\sum }_{}^{\lambda }P(X\to \lambda )=1$

PCFG的三個基本假設

• CFG的簡單概率拓廣${\sum }_{}^{\lambda }P(X\to \lambda )=1$
• 基本假設
  位置無關(guān)(Place invariance)
  上下文無關(guān)(Context-free)
  祖先無關(guān)(Ancestor-free)
• 分析樹的概率等于所有施用規(guī)則概率之積
  
  P(tree1)=1/22/32/3=2/9
  P(tree2)=1/21/31/3=1/18
  P(tree3)=1/21/2=1/4
  P(tree4)=1/21/2=1/4

PCFG的三個基本問題

1、一個語句$W=w_1{w}_2\dots .w_n$的P(W|G),也就是產(chǎn)生語句W的概率？
$P(W|G)$
2、在語句W的句法結(jié)構(gòu)有歧義的情況下,如何快速選擇最佳的語法分析(parse) ?
$\underset{tree}{\mathrm{argmax}}P(tree|W,G)$
3、如何從語料庫中訓練G的概率參數(shù),使得P(W|G)最大
$\underset{G}{\mathrm{argmax}}P(tree|W,G)$
-問題1&2解決思路

向內(nèi)（Inside）算法

非終結(jié)符A的內(nèi)部概率（Inside probability）
定義為根據(jù)文法G從A推出詞串$w_i...w_j$ 的概率，
記為${\alpha }_{i,j}(A)$,
$i\le j$
${\alpha }_{i,j}(A)$稱為向內(nèi)變量

45 句法分析技術(shù)（三）

• 向內(nèi)概率公式
  

向內(nèi)算法計算示例:
S→NP VP 1.0 NP→NP PP 0.4
PP→P NP 1.0 NP→John 0.1
VP→V NP 0.7 NP→bone 0.18
VP→VP PP 0.3 NP→star 0.04
P→with 1.0 NP→fish 0.18
V→ate 1.0 NP→telescope 0.1

問題2

Viterbi 算法

輸入： G=(S,N,∑,R,P),字符串$W=w_1{w}_2\dots .w_n$
輸出：t* ( W在G下最可能的分析樹)

Viterbi算法示例(自底向上)

問題3 參數(shù)訓練問題-有指導學習方法

從樹庫直接統(tǒng)計——Treebank Grammar
最大似然估計
依賴于艱巨的工程：樹庫建設

PCFG的優(yōu)缺點

• 優(yōu)點
  可以對句法分析的歧義結(jié)果進行概率排序
  提高文法的容錯能力（robustness）
• 缺點
  沒有考慮詞對結(jié)構(gòu)分析的影響
  沒有考慮上下文對結(jié)構(gòu)分析的影響
  許多當前的獲得較高精度的句法分析系統(tǒng)以PCFG為基礎(chǔ)

46 句法分析技術(shù)（四）

淺層句法分析技術(shù)

從完全句法分析（complete parsing）到淺層句法分析（shallow parsing）

• 真實語料的復雜性
• 語言知識的不足
• 提高分析的效率
• 應用目標驅(qū)動
• 淺層分析的其他名稱：部分分析（partial parsing），組塊分析（ chunking ）
  

基于HMM的淺層分析技術(shù)

識別目標：非遞歸的NP
組塊分析：在線性序列中插入括號，來標示組塊邊界
[The/DT prosecutor/NN] said/VB in/IN [closing/NN] that/CS …

級聯(lián)式有限狀態(tài)句法分析

（1）從左向右掃描輸入字符串，按照Li層級上的正則表達式模式進行歸約，得到新的模式序列，對于輸入串中無法歸約的符號，直接輸出；
（2）i=i+1，在新的Li層級上，用正則表達式模式進行歸約
（3）不斷進行上述步驟，直到無法歸約為止；
（4）如果歸約過程中有多種選擇，以覆蓋范圍最大的歸約子串為輸入結(jié)果

47 句法分析技術(shù)（五）

小結(jié)

• 以PCFG為重點介紹了近年來句法分析技術(shù)的基本原理與方法
• 句法分析是當前語言處理技術(shù)的瓶頸問題之一
• 句法分析是語義分析（更深層次的語言理解）的必由之路
• 句法是形式、語義是內(nèi)容
• 句法的強制性和語義的決定性
• 句法系統(tǒng)和語義系統(tǒng)是兩個不同的系統(tǒng)，它們各自獨立而又相互依存，彼此的對應關(guān)系十分復雜

致謝
關(guān)毅老師，現(xiàn)為哈工大計算機學院語言技術(shù)中心教授，博士生導師。通過認真學習了《自然語言處理（哈工大 關(guān)毅 64集視頻）》¹（來自互聯(lián)網(wǎng)）的課程，受益良多，在此感謝關(guān)毅老師的辛勤工作！為進一步深入理解課程內(nèi)容，對部分內(nèi)容進行了延伸學習^{2 3 456}，在此分享，期待對大家有所幫助，歡迎加我微信（驗證：NLP），一起學習討論，不足之處，歡迎指正。

參考文獻

---

《自然語言處理（哈工大 關(guān)毅 64集視頻）》（來自互聯(lián)網(wǎng)） ??

王曉龍、關(guān)毅 《計算機自然語言處理》 清華大學出版社 2005年 ??

哈工大語言技術(shù)平臺云官網(wǎng)：http://ltp.ai/ ??

Steven Bird,Natural Language Processing with Python,2015 ??

Claude E. Shannon. “Prediction and Entropy of Printed English”, Bell System Technical Journal 30:50-64. 195 ??

An Empirical Study of Smoothing Techniques for Language Modeling, Stanley F. Chen ??

總結(jié)

以上是生活随笔為你收集整理的《自然语言处理（哈工大 关毅 64集视频）》学习笔记：第七章 句法分析技术的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。