【NLP】句法分析
赞
踩
研究过程
最初，只是将词构成序列，研究词与词之间的概率分布：n-gram
接着引入词的句法red：属性，在句子中的不同位置：词性标注
现在考察词之间句法red：关系
句法规则涵盖的信息
句子的语法
词的顺序
短语成分
句子的层次结构
句法关系
两种不同的句法结构
依存结构
说明词与词之间的依赖关系，可以表示为一个依存树
在依存树中，被其他词语所依赖的单词并非处在依存树的根节点，而是叶节点
「图片」
短语结构
将词组成对应的短语结构，然后将各种嵌套的短语结构混合在一起就变成了句子
句法分析
输入一个句子，输出一个短语结构形式的语法树
「图片」
句法树中包含的信息：词性类别（N/V/DT）/短语（名词短语/动词短语）/句子（根结点）
两个目的
- 判断输入的句子是否符合语法
- 识别句子各部分语法元素，同时生成句法树
两个准备
- 语言的形式化描述
- 句法分析技术
形式语言（详细内容在编译原理中）
三种途径描述语言：（1）穷举（2）语法描述（3）自动机
形式语言是用来直观且精准地描述语言的手段
最原始的形式语言：
α
→
β
\alpha \to \beta
α→β，alpha 可以被改写为 beta，通过不断的运用该规则，就可以得到一个叫做语言的集合
形式语言的定义
G
=
(
N
,
∑
,
P
,
S
)
G = (N,\sum,P,S)
G=(N,∑,P,S)，其中 N 是非终结符集合，sum 是终结符集合，P 是规则集合
P
=
(
α
→
β
)
P = (\alpha \to \beta)
P=(α→β)，alpha 中至少包含一个非终结符，S 为起始符
推导的定义
如果
α
β
γ
\alpha\beta\gamma
αβγ是总词汇表克林闭包中的符号串，且
(
β
→
ϵ
)
∈
P
(\beta \to \epsilon) \in P
(β→ϵ)∈P，故
α
β
γ
=
>
G
α
ϵ
γ
\alpha\beta\gamma =>_G \alpha\epsilon\gamma
αβγ=>Gαϵγ
$=>^+
表示传递闭包，也就是
表示传递闭包，也就是
表示传递闭包，也就是X_n
到
到
到X_{n+1}$经过 n（n>=1）步推导
$=>^*
表示自反和传递闭包，也就是
表示自反和传递闭包，也就是
表示自反和传递闭包，也就是X_n
到
到
到X_{n+1}$经过 n（n>=0）步推导
最左，最右和规范推导
没步推导只改写最左边的非终结符，称为最左推导，同理有最右推导，最右推导称为规范推导
句型与句子
α β γ \alpha\beta\gamma αβγ是一个句型，若该句型中不包含非终结符，则称为句子，所有句子构成的集合就被称为语言，记为 L（G），形式化描述为： L ( G ) = { x ∣ x ∈ ∑ , S = > G + x } L(G) = \{x|x \in \sum, S =>^+_Gx \} L(G)={x∣x∈∑,S=>G+x}
正则文法
A
→
B
x
A \to B x
A→Bx左线性正则文法，A/B 为非终结符，x 为终结符
A
→
x
B
A \to xB
A→xB右线性正则文法
上下文无关文法（2 型文法）
A → α A \to \alpha A→α，其中 A 为非终结符，alpha 为单词表的克林闭包
上下文有关文法（1 型）
α A β → α γ β \alpha A \beta \to \alpha \gamma \beta αAβ→αγβ，其中 A 为非终结符，其他几项都属于单词表的克林闭包，gamma 至少包含了一个字符
无约束文法
最基础的 α → β \alpha \to \beta α→β
上下文无关文法的二义性
一个文法如果存在多个语法分析树与其对应，那么这个文法就是二义的
形式语法
用来规定语言中允许出现的结构的形式化说明，这里我们重点介绍 CFG 上下文无关文法
上下文无关文法的语法 G
G = （T，N，S，R）
T：终结符，叶节点
N：非终结符，中间节点
S：开始符号，根结点
R：产生式，用来构建树的枝干
CFG 的特性
上下文无关：生成式不依赖于所处环境
由 CFG 生成的语言可能拥有不止一个短语结构（结构歧义）
Chomsky 范式
一个受 chomsky 范式约束的 CFG 具有和一般 CFG 一样的终结符，非终结符，开始符号定义，对于产生式进行了两条约束：
N
i
→
N
j
N
k
a
l
l
∈
N
N^i \to N^jN^k all \in N
Ni→NjNkall∈N
N
i
→
w
,
w
∈
T
N^i \to w, w \in T
Ni→w,w∈T
应用句法规则构建语法树
搜索依据：语法规则
搜索过程：检查各种语法规则所有可能的组合方式
搜索目的：最终找到一种组合可以生成对应的句法树
方向：自上向下，自下而上
Cocke-Kasami-Younger Parsing
自底向上，利用线表/识别矩阵
CYK 的识别矩阵
方阵对角线以下全部为 0
主对角线上的元素全部由终结符构成
主对角线上方的元素全部由非终结符组成
构造步骤
首先将
t
0
,
0
=
0
t_{0,0} = 0
t0,0=0，然后往主对角线填上所有单词（非终结符）
然后考虑
t
i
,
i
+
1
,
i
=
0
,
.
.
.
,
n
−
1
t_{i,i+1},i = 0,...,n-1
ti,i+1,i=0,...,n−1这一对角线，对于输入句子
x
=
w
1
w
2
.
.
.
w
n
x = w_1w_2...w_n
x=w1w2...wn开始分析
如果有
A
→
w
i
+
1
,
则
t
i
,
i
+
1
=
A
A \to w_{i+1}, 则 t_{i,i+1} = A
A→wi+1,则ti,i+1=A,即，对于主对角线上每一个终结符，所有可能推导出他的非终结符写在右边主对角线的上方
然后一层一层向上叠加，
A
→
B
C
,
B
∈
t
i
,
k
,
C
∈
t
k
,
j
=
>
A
∈
t
i
,
j
A \to BC, B \in t_{i,k}, C \in t_{k,j} => A \in t_{i,j}
A→BC,B∈ti,k,C∈tk,j=>A∈ti,j
判断句子 x 是由文法 G 产生的充要条件就是 t（0，n）=S
优缺点
简单
但是必须对文本进行范式化处理，并且无法区分red：（是区分不是避免）歧义
几种常见的歧义
词性歧义/名词修饰歧义（形容词修饰的究竟是哪个名词）/介词短语修饰歧义（动作的状态修饰的对象不明）/边界歧义（Jim and Jane from LA）
PCFG 概率上下文无关文法
除了原本的四个指标，新增了每一个产生式可能出现的概率 P
设句法树使用了 n 条产生式，则生成该句法树的概率为
∏
i
=
1
n
p
(
α
i
→
β
i
)
\prod^n_{i=1}p(\alpha_i \to \beta_i)
∏i=1np(αi→βi)
如 此我们认为句法树集合为
τ
(
s
)
\tau(s)
τ(s)，每棵树概率 p（t），最可能的语法树
T
=
arg
max
t
∈
τ
(
s
)
p
(
t
)
T = \arg \max\limits_{t \in \tau(s)}p(t)
T=argt∈τ(s)maxp(t)
如何得到 PCFG 中的各种树，光靠枚举是肯定不够的：可以从 treebank 中学习
treebank
给定句法树样本，然后从训练语料中统计产生式并且估计每个产生式的概率
包含多种语言
参数
G：语法
L：G 生成的语言
t：语法树
N
=
(
N
1
,
.
.
.
,
N
N
)
N = (N^1,...,N^N)
N=(N1,...,NN)非终结符集合
W
=
(
w
1
,
.
.
w
n
)
W = (w^1,..w^n)
W=(w1,..wn)终结符集合
(
w
1
,
w
2
,
.
.
.
,
w
n
)
(w_1,w_2,...,w_n)
(w1,w2,...,wn)要处理的句子
N
p
q
j
N^j_{pq}
Npqj管辖位置 p 到 q 的非终结符 NJ
α
(
p
,
q
,
N
j
)
\alpha(p,q,N^j)
α(p,q,Nj)外向概率
β
(
p
,
q
,
N
j
)
\beta(p,q,N^j)
β(p,q,Nj)内向概率
假设
上下文无关：
P
(
N
k
l
j
→
γ
∣
w
o
r
d
s
o
u
t
s
i
d
e
(
w
k
,
w
i
)
)
=
P
(
N
k
l
j
→
γ
)
P(N^j_{kl} \to \gamma|wordsoutside(w_k,w_i)) = P(N^j_{kl} \to \gamma)
P(Nklj→γ∣wordsoutside(wk,wi))=P(Nklj→γ)
祖先节点无关：
P
(
N
k
l
j
→
γ
∣
a
n
c
e
s
t
o
r
N
o
d
e
)
=
P
(
N
k
l
j
→
γ
)
P(N^j_{kl} \to \gamma|ancestorNode) = P(N^j_{kl} \to \gamma)
P(Nklj→γ∣ancestorNode)=P(Nklj→γ)
HMM 与 PCFG 的比较
HMM 中定义了前向，后向概率；PCFG 定义了向外，向内概率
与 HMM 相同，PCFG 的三个基本问题：
（1）计算句子的概率
（2）给一个句子找到最优的语法树
（3）参数学习：求解使句子概率最大的句法 G
定义动态规划表
π
(
i
,
j
.
,
X
)
\pi(i,j.,X)
π(i,j.,X)由非终结符 X 推导出子串的最大概率
目标是计算：
max
t
∈
τ
(
s
)
p
(
t
)
=
π
(
1
,
n
,
S
)
\max\limits_{t \in \tau(s)}p(t) = \pi(1,n,S)
t∈τ(s)maxp(t)=π(1,n,S)
取 max，可以得到是 V P → V P , P P VP \to VP,PP VP→VP,PP
句法分析的程序化表达
句法分析的评价
依存语法分析
在依存语法理论中，处于支配地位的成分称为支配者，而处于被支配地位的称为从属者；用有向边来表示依存关系，支配者处于发出端，从属者处于接收端
依存树
子节点依存于父节点
依存投射树
位置低依存于位置高的成分，实线表示依存关系，虚线表示投射
依存语法要求
（1）一个句子只能有一个独立的成分：单一父节点
（2）句子的其他成分都从属于某一个成分：连通
（3）任何一成分都不能依存于多个成分：无环
（4）成分 A 直接从属于 B，而 C 在句子中的物理位置在 A 和 B 之间，那么 C 一定从属于包含[A，B]某一部分：可投射
依存句法分析器
（1）依存句法结构描述：有向图/依存树（上文中提及）
（2）分析算法的设计与实现
（3）文法规则&参数学习
分析算法
生成式的分析方法
采用联合概率模型
S
c
o
r
e
(
x
,
y
∣
θ
)
Score(x,y|\theta)
Score(x,y∣θ)，生成一系列依存句法树，并且对每一个进行概率打分，最后选择分数最高的分析结果作为输出
e.g.二元词汇亲和模型&选择偏好模型
递归生成模型：每个词的左子节点和右子节点由各自的马尔可夫模型产生，左子节点从右向左产生，直到无法继续获得子节点；右子节点从左向右产生，直到无法获得子节点。这一方法是自顶向下的递归方法。
判别式的分析方法
采用条件概率模型
S
c
o
r
e
(
x
∣
y
,
θ
)
Score(x|y,\theta)
Score(x∣y,θ)，使目标函数
∏
i
=
1
n
S
c
o
r
e
(
x
i
∣
y
i
,
θ
)
\prod\limits^n_{i=1}Score(x_i|y_i,\theta)
i=1∏nScore(xi∣yi,θ)最大的 theta 作为模型的参数
e.g.最大生成树模型：整棵句法树的打分是树中各条边打分的加权和
S
(
x
,
y
)
=
∑
w
⋅
f
(
i
,
j
)
S(x,y) = \sum w \cdot f(i,j)
S(x,y)=∑w⋅f(i,j)，f(i,j)表示 y 中的依存关系，如果树中 xi 与 xj 有依存关系则为 1，没有为 0. w 为使用样本训练出来的权值
决策式分析方法
每次在原本的基础上处理一个词，一旦做出认定则不再改变。
e.g.移进规约算法，arc-eager 算法
具体例子请移步这里：https://blog.csdn.net/weixin_46876169/article/details/139042946?spm=1001.2014.3001.5501
优点：如果判断准确，时间复杂度可以远远低于全局最优算法
问题：无法处理非投射现象，而且一旦陷入局部最优就可能导致错误信息的传递
基于约束满足的分析方法
根据约束对于依存树进行剪枝操作，直到得到合法的依存树且满足所有条件
问题：可能有多个树都满足条件此时无法判断选择哪个
依存句法分析器的评价指标
无标记依存正确率（unlabeled attachment score）：所有词中找到了其正确支配词的词所占的百分比（包含根结点所以不可能为 0）
带标记依存正确率（labeled attachment score）：找到了正确支配词且依存关系类型也标注正确
依存正确率（dependency accuracy）：非根结点词找到正确支配词所占的百分比
根正确率：有两种定义
（1）正确根结点的个数与句子个数的比值
（2）所有句子中找到正确根结点的句子所占的百分比
完全匹配率（complete match）：所有句子中无标记依存结构完全正确的句子所占的百分比
e.g.
UA = 6/7
LA= 5/7
DA=5/6
短语结构与依存结构的转换
实现方法：
（1）定义中心词抽取规则，产生中心词表
（2）根据中心词表，为句法树中每个节点选择中心子节点
（3）将非中心子节点的中心词依存到中心子节点的中心词上
汉英句法结构对比
（1）汉语比英语更少使用功能词，同时没有形态变化
（2）英语绝大多数短语以左部为中心，而汉语大多数以右部为中心
（3）汉语中往往忽略先行代词：
He thinks it is good to play games
他认为（）玩游戏很好
语义分析
语义计算的任务：解释自然语言句子或文章各部分的含义
面临的困难：语义的判断具有主观的因素；自然语言中存在着大量的歧义/俗语/指代/隐喻
语义的分类
（1）词的指称
（2）人的主观判断
（3）过程语义
（4）词汇分解学派
（5）条件真理模型
（6）情景语义学
（7）模态逻辑
格语法
格的定义
格语法中的格是“深层格”，它是指句子中体词(名词、代词等)和谓词(动词、形容词等)之间的及物性关系(transitivity)，如:动作和施事者的关系、动作和受事者的关系等，这些关系是语义关系，它是一切语言中普遍存在的现象。
三条基本规则
S
→
M
o
d
a
l
i
t
y
+
P
r
o
p
o
s
i
t
i
o
n
S \to Modality+Proposition
S→Modality+Proposition
P
→
V
+
C
1
+
.
.
.
+
C
n
P \to V+C_1+...+C_n
P→V+C1+...+Cn
C
→
K
+
N
P
C \to K +NP
C→K+NP
格表
施事格/工具格/承受格/使乘格/方位格/客体格…
分析步骤
判断主要动词，并找出该词的格框架，识别句子中对应的格成分，在确定句子的情态
e.g.
语义网络
有向图：图的节点表示概念，图的边表示概念之间的关系
事件的语义关系：
（1）分类关系
（2）聚焦关系：多个下级概念构成一个上级概念
（3）推论关系：由一个概念推出另一个概念
（4）时间，位置关系：事实发生或存在的时间，位置。
概念依存理论
词义消歧
e.g.bank 银行/河岸
（1）基于规则
（2）统计机器学习-有监督/无监督
基本思路：词的不同语义与上下文往往有关联性
（3）基于词典信息的消歧
有监督的词义消歧方法
通过建立分类器，利用划分多义词的上下文的类别来区分多义词的词义
（1）基于上下文的定义，根据其他位置所处的单词来确认当前多义词的意思，这样子的条件可以认为是“语义指示器”，消歧问题就实际上转换为了指示器-语义分类问题
（2）Flip-flop 算法：
假设
T
1
,
T
2
T_1,T_2
T1,T2为多义词的两种语义，
V
1
,
.
.
.
,
V
n
V_1,...,V_n
V1,...,Vn为指示器可能的取值
执行循环：找到 V1，V2，Vn 的一种划分[Q1，Q2]，使 Ti 与 Qi 之间的互信息最大
除此以外还有：
（3）基于贝叶斯分类器的词义消歧
（4）基于最大熵的词义消歧方法
无监督的词义消歧
在本处不做解释，例子有上下文分组辨识，可以寻找其他文章查看
基于词典信息的消歧
（1）基于语义定义的消歧：词条中词本身的定义与上下文结合作为对应的定义
（2）基于义类词典的消歧：对应的语义所处的环境决定了其的意思，类似于使用别的词来描述该词
（3）基于双语词典的消歧
（4）Yarowsky 消歧算法：
基于词典的消歧算法都对歧义词有限制：每篇文本只有一个意义&每个搭配只有一个意义
对于第一个约束，如果一个给定的多义词在第一次使用某个语义，那么在后面也很有可能使用这个语义
对于第二个约束，采用自举的学习技术。搭配特征依据如下比率排序：
p
(
s
k
1
∣
f
)
p
(
s
k
2
∣
f
)
\frac{p(s_{k_1}|f)}{p(s_{k_2}|f)}
p(sk2∣f)p(sk1∣f)
其中 s 为词义，f 为搭配特征
语义角色标注
以句子中的谓词为核心，分析句子中的其他成分与谓词之间的关系
主要用途：信息抽取、自动文摘、机器翻译
两类语义角色：与具体谓词直接相关的，使用 ARG0-ARG5 表示，通常 ARG0 表示动作的施事，ARG1 表示动作的影响，其他的则根据谓语动词不同有不同的含义
起修饰性的作用，使用 ARGM-XXX 进行表示
句法分析器-候选论元剪除-论元识别-论元标注-后处理
候选论元剪除
将谓词作为当前节点，考察兄弟节点，如果不是并列结构，则将其作为候选项；若兄弟节点是 PP，则其所有子节点也是候选项
