FNLP 笔记第七集：句法分析

八、句法分析——成分分析

句法（Syntax）是指词序列的合法性和良构性规则，我们本章分析的是句法中的成分结构（constituency）。它通常较为复杂，所以需要树这种更复杂的数据结构来表示。这也导致前面的所有方法无法分析清楚一个句子的句法。我们的目标就是找到一种新方法。

1. 什么是成分？

成分是一组可以当做单一单元，并且有某些共同行为的词。它一般有这些性质：

• 出现位置较为固定，比如名词短语通常出现在动词之前；
• 可移动；
• 不可切分；
• 可并列。

为什么它值得分析呢，是因为它的成分很复杂，并且可以嵌套，这也是为什么引出了树这个数据结构。举个例子，”The guy who fixed the car carefully packed his tools” 可以表示成下面这个句法树：

句法分析（Parsing）的任务就是：给定一个句子，搜索并打分所有合法的结构，最终给出最可能的句法树。因此我们有下面四个任务：

• 这个结构是正确的吗？
• 这个结构的分数如何？
• 如何找到分数最高的结构？
• 如何找到最好的参数？

我们依旧有两种方法研究这个问题。接下来我们从统计的方法来做。

2. 上下文无关文法

首先我们定义一些概念。形式语言（Formal Language）是在某个字母表上的字符串集合，所谓字母表 $\Sigma$ 就是有限的符号集合，比如一些字母或一些单词；而字符串就是字母表中符号的有序排列。形式语言不包括所有的字符串，而是受到一定规则限制，这个规则就叫形式文法（Formal Grammar）。一个文法 $G$ 包含：

• 终结符 $\Sigma$，包括具体的符号，比如一些具体的单词；
• 非终结符 $N$，包括一些抽象的符号，比如 NP（名词短语），S（句子）等；
• 开始符号 $S$；
• 产生规则 $R$，表示如何生成字符串。它的一般形式是：$(\Sigma\cup N)^+\rightarrow(\Sigma\cup N)^*$

而上下文无关文法（Context-Free Grammars）的唯一限制是产生规则：$A\rightarrow(\Sigma\cup N)^*$，左边必须要是单个非终结符，右边可以是任意字符串。

文法有等价的概念，弱等价只需要使按照这个文法，能生成的字符串相同即可，而强等价需要保证句法结构完全一致。比如，定义两个文法：$G_1:S\rightarrow SS\vert a$，表示一个 $S$ 可以变成两个 $S$，或是变成具体字符 $a$。那么这个文法可以产生的字符串就是一堆 $a$，很好理解吧。另一个文法 $G_2:\rightarrow aS\vert a$，表示一个 $S$ 可以展开成 $aS$，也能变成单独的 $a$，那么这个文法能产生的字符串也是一堆 $a$，说明这两个文法弱等价。但是我们看 $aaa$ 的结构，在 $G_1$ 下的结构长这样：

      S
     / \
    S   S
   / \   |
  S   S  a
  |   |
  a   a

而 $G_2$ 下的结构是这样的：

S
|
aS
 |
 aS
  |
  a

因此这两个文法不是强等价的。

在 CFG 更进一步，对产生规则进一步限制，就成了乔姆斯基范式（Chomsky Normal Form, CNF）。它的规则只有两种：$X\rightarrow YZ$，或者 $X\rightarrow x$。有个定理：任意的 CFG 都可以变成等价的 CNF，虽然 PPT 没讲怎么变，但是我依稀记得一年前的 AI 引论就考了这个问题，直接给我大脑攻击烂了啊，因此我们来详细讲讲。按照下面步骤进行：

1. 添加新的开始符号：$S_0\rightarrow S$
2. 消除空产生式：假如有 $A\rightarrow\epsilon$，那么所有存在 $A$ 的式子都变成删或不删两个情况。比如有 $B\rightarrow AC$，那就变成 $B\rightarrow AC\vert C$。
3. 消除单位产生式：假如有 $A\rightarrow B$，那么所有 $B$ 的产生式全部搬到 $A$ 上。比如有 $B\rightarrow CD\vert a$，那就搬给 $A\rightarrow CD\vert a$。
4. 消除混合终结符：假如有 $A\rightarrow aB$ 这种混合了终结符的，就引入新变量 $X_a\rightarrow a$，然后把这个规则改成 $A\rightarrow X_aB$。
5. 拆分长规则：假如有 $A\rightarrow BCDE$，就拆成多个短的规则：$A\rightarrow BX_1$，$X_1\rightarrow CX_2$，$X_2\rightarrow DE$。

我觉得复习半天，应该不会考这个玩意，看看得了。

那这么些文法有啥用呢，其实就是完成了第一个任务：判断一个结构是否正确。

3. 概率上下文无关文法

现在我们回答第二个问题：怎么判断一个结构的好坏？就需要用概率上下文无关文法（PCFG）。它不仅需要给出上下文无关文法的规则，还需要给每个规则赋概率。比如，规则中 $A$ 既可以拆成 $BC$，也可以拆成 $abCD$，那就需要分配概率，比如前面这个拆分有 $0.8$ 的概率，后面这个有 $0.2$ 的概率，需要保证加起来为 1。有了这些局部的概率，就可以计算一个句子这样拆分的概率了。这个概率是通过统计算出来的，在训练集中，我们找到所有 $A$，然后看有多少的拆分是将 $A$ 拆分成 $BC$ 了，这个比重就是概率。对于我们做题来说，一般会把概率直接给出来。

4. CKY 算法

接着是第三个问题：如何找到分数最高的结构？我们综合分治和动态规划算法，得到了 CKY 算法，我也懒得说明这个算法是怎么想出来的了，就直接看看它的步骤吧。

这个算法的前提是遵循 CNF 文法。

我们定义一个状态 $\pi[i,j,X]$，表示非终结符 $X$ 覆盖 $w_{i+1},\cdots,w_j$ 的最大概率。那么对于 $\pi[i,i+1,X]$，它的值就是 $w_{i+1}$ 是 $X$ 的概率，即：

\[\pi[i,i+1,X]=p(X\rightarrow w_{i+1})\]

而递推方程就是利用 $X\rightarrow YZ$，将 $[i,j]$ 从任何地方切分，看看能不能拆成 $YZ$ 的形式。因此：

\[\pi[i,j,X]=\max_{X\rightarrow YZ,m\in[i,j]} p(X\rightarrow YZ)\pi[i,m,Y]\pi[m,j,Z]\]

也就是找到使得概率最大的切分位置与 $X$ 的规则。

举个例子吧。给定一个 CNF 文法：

然后给定句子：I saw the boy with a telescope. 现在我们来求 DP 表，DP 表长这样：

左边是 $i$，右边是 $j$，这两个数字都是词与词之间间隙的序号，比如句子中 I 之前的编号为 0，I 与 saw 之间是 1。表里面每一个填两个东西：一个是覆盖 $[i,j]$ 的非终止符，另一个是对应的最大概率。其实左下角都不会填任何东西，因为 $i$ 不能比 $j$ 大。我们先填对角线，比如 $[0,1]$ 之间是 I，根据规则肯定是 NP，并且概率是 0.1，以此类推填满对角线：

接着填两个词的，先看 I saw，应该是 NP + V，但是没有这种规则，因此啥也不填。saw the 也没有对应的规则，不填。the boy 是 Det N，有 NP，概率为 0.6，因此填进去。这样一路填，直到填满整个表。直接上答案：

这里最后的概率没算出来，应该是 $0.00054$，这就是最大概率。那怎么倒推结构呢，只需要在计算的同时记录这个最大概率是由哪两个部分得来的就行了。

CYK 算法同样可以用于判定一个句法是否能生成这个句子，只要按照上面这个算法，并且不用算概率，最后能推出 $S$，就说明是可以生成的。

5. 评估 CKY 算法的指标

我们最开始就说过了精确率：你放进句法树的边中，有多少是对的；以及召回率：在所有应当放入句法树的边中，有多少被放进来了。F1 值就是取它们的调和平均。

九、句法分析——依存分析

之前分析的是成分结构，现在我们分析的是另一种结构，叫依存。

1. 什么是依存？

词汇单元之间是依靠二元非对称关系链接的。比如，形容词是修饰名词的，主语和宾语是依附于动词的，等等。一般来说，依存树的根是 ROOT，它只有一个子结点就是这句话的谓语，然后遵循一定的依存关系。

我们通常用依存弧来表示依存关系，由核心词指向附属词。核心的词叫 Superior 支配词，被指向的词叫 Inferior 依赖词，连接的关系叫依存关系。一般的思路是，从谓语开始，寻找它的附属词，至于寻找的原则，确实没讲，纯凭感觉说是。

由依存弧连接产生的数据结构不一定是树，很可能是图，我们称为依存图。理想的依存图满足下述性质：

• 弱连通性：作为无向图是连通的；
• 无环：这要解释吗；
• 单头：每个词只附属于一个词，当然可以有很多词附属它；
• 投射：边不交叉。

实际上很多依存图不满足这些性质，所以考虑这些其实没用。

现在的问题是：怎么设计算法，获取依存图？我们依旧要处理四个问题：

• 这个依存关系是正确的吗？
• 这个依存关系的分数如何？
• 如何找到分数最高的依存关系？
• 如何找到最好的参数？

2. Transition-Based Dependency Parsing

后注： 这部分好像写的有点赶，全是文字，一点图没有，大家可能有点懵，建议大家去网上找点相关资料看。这一个知识点在期中考试单独作为一道题出现，就是给了一个具体的句子，要求按照这种方式画出其依存图，并且要求一共进行了多少次动作。并且还要注意的是，题目中定义的三种动作不是下文的三种动作，而是新定义，所以其实你看这种也没什么用。本质还是不难的。

这个算法的思路是基于正常人的思考逻辑：从左到右阅读，凭感觉判断这是主语、这是谓语、这是宾语，诸如此类。但是这一招有时会失误，比如：I convinced her children … 如果没有看完，会觉得 her children 是宾语，然而后文是：I convinced her children are noisy. 原来是宾语从句，那没事了。其实原始的思路就像贪心，发现出问题了就只能回溯了。

首先，整体的架构包含三个部分：一个栈，储存部分处理的词；缓冲区 buffer，是还没有处理的词，也是个栈，前面的词作栈顶；依存弧集合，收纳已经建立好的依存关系。把栈放左边，栈底朝左；buffer 放右边，栈底朝右。一开始栈里面只有 ROOT，buffer 中是所有的输入词，依存弧是一条没有。

其次，这个算法中有三个基础动作，一个叫 SHIFT，将 buffer 的第一个词入栈；一个叫 LEFTARC，建立左弧，具体而言是从 buffer 的栈顶元素指向栈顶元素，也就是一个向左的箭头，并把依赖词删掉；最后一个叫 RIGHTARC，建立右弧，具体是把栈顶词指向 buffer 词上，把依赖词删掉，再把栈顶词放回 buffer。

最后是算法流程，非常非常简单：只要 buffer 不是空的，或者栈里面至少还有两个元素，就根据当前状态选择三个动作里面的一个，一直迭代就好了。那有人就要问了，我哪知道该做哪个动作啊？对模型来说，这就是训练要练的东西了，它的名字叫 Oracle，本质是一个需要训练的分类器。但是对于人类来说这是简单的啊，我们的判断依据是两个元素到底能不能构建弧，只要能构建弧我们都构建，因此得到了完整的算法。

如何评估构建的依存图呢，我们依旧是按词打分：看有多少词被正确依存了；当然也可以按照句子打分，看看有多少句子完全正确，但是这个非常严格了。当然“正确”也有两个指标，一种是 UAS（Unlabeled Attachment Score）：只要头对了就算对；另一种是 LAS（Labeled Attachment Score），还需要弧的标签对才算对。很明显 LAS 严格一些。

当然还需要注意，这个算法不能处理不满足投射性的算法。

十、作者最后的寄语

这里主要想讲一下期中考试的事。我复习就是把课件过一遍，然后制作成了这个笔记合辑。最后考试的时候，发现大部分的题我都复习到了，所以这份笔记是有充分的可信度的。又据说这门课连着两年的期中都是同一套题，怪不得一点往年题没有呢。我上考场的时候信誓旦旦地要把题目背下来，但是不可能也没必要：不可能是因为题目给了一大堆数据要手算，不可能把数据记下来；没必要是因为本质上就是这些知识点而已。

先讲讲期中考试的具体情况吧，期中考了九个题目，其中大部分就是要手算一些算法，比如上文的 CKY 算法，弧依存算法，再比如之前的困惑度的定义和计算，HMM 算法等等，基本上是统计方法的算法。而神经网络的算法，就容易出概念题，今年好像有个题是问 LSTM 和 GRU 的优缺点，还有一题是给了几个关于 Transformer 和 attention 的描述，问哪项是对的，因此大家要看看概念。还有一道比较特殊的是第一题，给定一种特殊的语法，要求举出词义消歧的例子，比如“Adj N N”，要构建出一个句子，满足这个语法，并且有两种解读方法，反正差不多这情况，大家了解一下。

至于难度，不算难，但绝对恶心，题量够大，计算量也不小。如果掌握地不够熟练，很容易做不完。所以建议认真把这些笔记都看一遍，该动手操作的手算一下，不要感觉自己会了就跳过去。别的叮嘱倒是没有，我觉得看完这份笔记就已经足够应付考试了。不过其实我不知道我期中多少分，反正感觉还行。

再讲讲笔记，因为这门课只有期中没有期末，我期中考完就没听过了。大家看笔记如果有不懂的，可以问 AI 或者查资料。我知道现在很多人喜欢用 AI 解决一切问题，不过查资料的好处是：一方面资料是人写的，讲的更像人话，另一方面资料一般附图，更好理解。至于期中之后的东西，我只能说，既然我都没做笔记，说明压根不用听了（×）