Skip to content

Lesson-3 句法分析

成分句法树

成分句法树是一种基于短语结构的句法表示方法，用于表示句子的句法结构。成分句法树将句子分解为迭代嵌套的句法成分，通过树形结构展示这些成分之间的层次关系。

基本概念：

（1）句法成分：

  • 名词短语（NP）：如 “The cat”
  • 动词短语（VP）：如 “is sleeping on the mat“
  • 介词短语（PP）：如 “on the mat”

（2）树形结构：

  • 节点表示句法类别或词语
  • 边表示句法成分之间的包含或修饰关系

（3）递归性：句法成分可以嵌套。

具体例子如下：

"The cat sleeps on the mat."的句法树为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
S
├── NP
│   ├── Det: "The"
│   └── N: "cat"
├── VP
│   ├── V: "sleeps"
│   └── PP
│       ├── P: "on"
│       └── NP
│           ├── Det: "the"
│           └── N: "mat"

为什么需要句法结构呢？

  • 我们通常要将单词组成更大的单位（短语）来表达复杂的意思
  • 理解语言需要弄清楚哪些词或者短语修饰另外一些词或者短语

句法结构树的作用：

  • 解释句子的句法组成 ，并验证语法规则
  • 消解歧义：在句法歧义问题中，成分句法树通过展示不同的结构可能性帮助解决歧义。

消解歧义的具体内容：

  • 修饰语的歧义：例："I saw the man with a telescope."

存在两种结构：

1
2
3
4
S
├── NP (I)
├── VP (saw)
    ├── NP (the man with a telescope)

1
2
3
4
5
S
├── NP (I)
├── VP (saw)
    ├── NP (the man)
    ├── PP (with a telescope)
  • 词性带来的歧义：同一个单词可能属于不同的词性
  • 短语边界的歧义：不同的短语边界划分会影响句子的解析
依存句法树

依存句法树（Dependency Parse Tree）是另一种用于表示句子结构的形式。与成分句法树不同，依存句法树专注于描述句子中词与词之间的语法依赖关系。它以树的形式表示每个单词（节点）之间的依赖关系，其中根节点是句子的核心词（通常是谓语动词）。

特点：

  • 单词为节点
  • 边（箭头）表示两个单词之间的语法依赖关系，如主谓关系、修饰关系、宾语关系等
  • 依存句法树是一个有向无环图

具体例子：

"The cat sleeps on the mat."对应的依存句法树：

1
2
3
4
5
6
   sleeps
   ├── cat (nsubj)
   │   └── The (det)
   ├── on (prep)
   │   └── mat (pobj)
   │       └── the (det)

具体的依存含义为：nsubj 是主语依赖关系；det 是限定词依赖关系；prep 是介词依赖关系；pobj 是介词宾语依赖关系。

成分句法树 VS 依存句法树

成分句法树：（1）节点是词、短语和句子；（2）边表示从属关系；（3）嵌套结构的树

依存句法树：（1）节点是词；（2）边是依存关系；（3）是多叉树

上下文无关文法

上下文无关文法包含以下部分：

  • 终结符：句子的基本单元（如单词）
  • 非终结符：短语类别（如句子 S、名词短语 NP、动词短语 VP）
  • 起始符：整个句法分析的根节点，通常是 S
  • 规则集合：将非终结符分解为终结符或其他非终结符的规则

上下文无关文法 VS 上下文有关文法：

上下文无关文法就是说这个文法中所有的产生式中左边只有一个非终结符，比如：

1
2
S -> aSb，
S -> ab

而上下文有关文化的第一个产生式的左边不止有一个符号，所以你在匹配这个符号的时候，还要确保其有正确的上下文，即“a”和“b”。比如：

1
2
aSb -> aaSbb
S -> ab

在具有以上先验知识后，我们开始介绍 PCFG（概率上下文无关文法）：在 PCFG 中，每条规则会被赋予一个概率值 \(P\)，表示该规则在当前上下文中被选择的可能性。

比如：

1
2
3
4
S → NP VP   [P=0.9]
S → VP      [P=0.1]
NP → Det N  [P=0.8]
NP → N      [P=0.2]
我们需要：对于一个非终结符：\(\sum P =1\)

PCFG 的特性：

  • 根据概率选择最优解析，比如，对于存在句法歧义的句子，PCFG 可以根据规则概率生成多棵解析树，并选择概率最高的树作为最优解析。
  • 怎么得到规则的概率的呢？PCFG 的规则概率通常基于大规模语料库，通过统计频率计算得到。
\[P(A\rightarrow \alpha) = \frac{\text{规则}A\rightarrow \alpha\text{出现的次数}}{\text{以}A\text{开始的所有规则的出现的个数}}\]
  • 训练：使用最大似然估计（MLE）或贝叶斯方法对规则概率进行训练。

应用示例：

设定以下文法规则及概率：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
S → NP VP    [P=1.0]
NP → Det N   [P=0.6]
NP → N       [P=0.4]
VP → V NP    [P=0.7]
VP → V       [P=0.3]
Det → "the"  [P=1.0]
N → "cat"    [P=0.5]
N → "dog"    [P=0.5]
V → "chased" [P=0.6]
V → "slept"  [P=0.4]

输入句子："The cat chased the dog."

可以得到下面的解析树1：

1
2
3
4
5
6
7
8
9
S
├── NP
│   ├── Det ("the")
│   └── N ("cat")
└── VP
    ├── V ("chased")
    └── NP
        ├── Det ("the")
        └── N ("dog")

其概率的计算为：\(P = 1.0 \times 0.6 \times 0.7 \times 1.0 \times 0.5 \times 0.6 \times 0.6 \times 1.0 \times 0.5\)

综上，PCFG 会面临三个问题：

（1）给定一个句子\(W=w_1…w_n\)和文法\(G\)，如何快速计算概率\(P(W|G)\)：这个句子有多种可能性，我们需要计算出符合文法的所有可能性；

（2）给定一个句子\(W=w_1…w_n\)和文法\(G\)，选择出概率最大的句法树（类似解码）；

（3）给定一个句子\(W=w_1…w_n\)和文法\(G\)，如何调整文法使句子的概率最大（训练出\(G\)的过程）。

内向算法

针对上面 PCFG 的问题（2），我们使用内向算法。

伪代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
输入：句子W = w_1...w_n，文法G
输出：a_ij(A)
初始化：a_ii = P(A->w_i)

动态规划计算：
for j = 1,2,...,n:
   for i = 1,2,...,n-j:
      a_i(i+j)(A) = \sum_{BC}\sum_{k=1}^{i+j-1}P(A->BC)*a_ik(B)*a_(k+1)(i+j)(C)

最终，我们得到：a_1n(S)即为P(W|G)
下面举一个具体计算的例子：

文法规则如下：

1
2
3
4
5
6
7
8
9
S → NP VP    [P=1.0]
NP → Det N   [P=0.5]
NP → N       [P=0.5]
VP → V NP    [P=0.6]
VP → V       [P=0.4]
Det → "the"  [P=1.0]
N → "cat"    [P=0.5]
N → "dog"    [P=0.5]
V → "chased" [P=0.6]

句子如下；

1
W = "the cat chased the dog"

首先，我们开始初始化：\(a_{11}=P(Det → "the")=1.0\)，\(a_{22}=P(N → "cat")=0.5\)，\(a_{33}=P(V → "chased")=0.6\)，\(a_{44}=P(Det → "the")=1.0\)，\(a_{55}=P(N → "dog")=0.5\)

然后，我们开始计算\(a_{12} = P(NP → Det N)a_{11}a_{22} =0.5 \times 1.0 \times 0.5=0.25\)，同理可得：\(a_{4,5} = 0.25\)。接下来：\(a_{3,5} = P(VP → V NP) a_{33}a_{45} = 0.6 \times 0.6 \times 0.25 = 0.09\)，最后，我们计算出：\(a_{1,5} = P(S → NP VP) a_{1,2}a_{3,5} = 1.0 \times 0.25 \times 0.09=0.0225\)。因此，我们最后得到\(P(W|G) = 0.0225\)

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 协议之条款下提供，附加条款亦可能应用