G.6 CCG 句法分析

组合语法中的规则都是二元或一元规则，因此，基于 CKY 算法的自底向上表格方法看起来可以直接用于 CCG 句法分析。遗憾的是，每个词都有大量可用词汇范畴，加上 CCG 组合规则适用范围极广，导致加入句法分析表的成分数量激增，其中大多毫无用处。控制这些“僵尸成分”爆炸的关键，是准确评估并利用每个词最可能的词汇范畴；这一过程称为超标注（supertagging）。

以下各小节介绍一种使用超标签的 CCG 分析方法：借助 $A^*$ 算法，把分析过程组织成启发式搜索。

G.6.1 超标注¶

第 18 章介绍了词性标注，即给句中每个词指派正确的词汇类别。超标注是在高度词汇化语法框架中与之对应的任务；指派的标签通常决定了句子推导的大部分结构（Bangalore and Joshi, 1999）。

CCG 超标注器依靠 CCGbank 等树库提供总体的词汇范畴集合，以及词典中每个词允许指派的范畴。CCGbank 包含 1,000 多种词汇范畴；实践中，大多数超标注器会把标签集限制为训练语料中至少出现 10 次的标签，于是词典中大约有 425 种可用词汇范畴。即使这一较小数字，与 Penn Treebank 标签集的 45 种词性相比仍然很大。

与传统词性标注相同，构建 CCG 超标注器的标准方法，是用监督式机器学习从人工标注训练数据中构建序列标注器。给定句子后，通常使用 RNN 或 Transformer 神经序列模型寻找最大概率标签序列。

也可以使用第 18 章介绍的 CRF 标注模型，并采用类似特征：当前词 $w_i$、其前后 $l$ 个词范围内的上下文词、局部词性标签、字符后缀，以及前一时间步的超标签。模型通过最大化训练语料的对数似然来训练，再按第 18 章所述使用 Viterbi 算法解码。

然而，大量可能的超标签加上每个词的高歧义度，会使朴素 CRF 的错误率高到无法实际用于句法分析器。单一最佳标签序列 $\hat T$ 通常包含太多错误标签，无法进行有效分析。为解决该问题，模型不再只返回最佳序列，而是为输入中的每个词返回可能超标签上的概率分布。下面给出简单句子的分布示例；每列表示在输入句子的上下文中，给定词采用各超标签的概率，省略号表示该词其余可能的超标签。

为了得到每种“词—标签”组合的概率，需要对所有在相应位置包含该标签的超标签序列之概率求和。可使用附录 A 介绍、也用于训练 CRF 的前向—后向算法完成这一计算。

G.6.2 使用 $A^*$ 算法进行 CCG 句法分析¶

$A^*$ 算法是一种启发式搜索方法，它用议程（agenda）寻找最优解。表示部分解的搜索状态根据代价函数加入议程；每次迭代都选择代价最小的选项继续探索。当表示完整解的状态第一次从议程中被选出时，该状态保证是最优解，搜索随即终止。

$A^*$ 的代价函数 $f(n)$ 用于高效引导搜索到达解。$f$ 代价包含两部分：$g(n)$ 是状态 $n$ 所表示部分解的精确代价，$h(n)$ 是利用 $n$ 构造完整解时所需代价的启发式近似。若 $h(n)$ 满足“不高估实际代价”的条件，$A^*$ 就能找到最优解。不出所料，启发式值越接近实际代价，$A^*$ 越能在不探索大部分解空间的情况下高效找到解。

用于句法分析时，搜索状态对应表示完整成分的边。每条边指明成分的起止位置、语法范畴和 $f$ 代价。这里，$g$ 分量表示边的当前代价，$h$ 分量则估计完成一项包含该边的推导所需代价。Klein and Manning（2003）最早把 $A^*$ 用于短语结构分析；这里介绍的 CCG 方法以 Lewis and Steedman（2014）的工作为基础。

算法利用超标注器提供的信息，用表示输入中每个词全部可能词汇范畴及相应 $f$ 代价的状态，初始化议程和句法分析表。主循环从议程中移除代价最低的边，并检查它是否形成完整推导。若是，就把它选为最佳解并终止循环；否则，根据适用的 CCG 规则生成新状态，为它们分配代价，并加入议程等待处理。循环持续到发现完整推导；若议程耗尽仍无结果，则分析失败。

function CCG-ASTAR-PARSE(words) returns table or failure
    supertags ← SUPERTAGGER(words)
    for i ← 1..LENGTH(words)
        for all (words[i], A, score) in supertags
            edge ← MAKEEDGE(i-1, i, A, score)
            table ← INSERTEDGE(table, edge)
            agenda ← INSERTEDGE(agenda, edge)
    loop
        if EMPTY?(agenda) return failure
        current ← POP(agenda)
        if COMPLETEDPARSE?(current) return table
        table ← INSERTEDGE(table, current)
        for each rule in APPLICABLERULES(current)
            successor ← APPLY(rule, current)
            if successor not in agenda or table
                agenda ← INSERTEDGE(agenda, successor)
            else if successor is in agenda with higher cost
                agenda ← REPLACEEDGE(agenda, successor)

图 G.1　基于 $A^*$ 的 CCG 句法分析。

G.6.3 启发式函数¶

定义 $A^*$ 搜索的启发式函数前，需要确定如何评价 CCG 推导的质量。作一个简化假设：CCG 推导的概率就是该推导中各词所指派超标签概率的乘积，忽略推导所用的规则。形式上，给定句子 $S$ 和包含超标签序列 $T$ 的推导 $D$：

传统 $A^*$ 方法用“越低越好”的代价函数为状态评分，即最小化推导代价。为此，用负对数概率为推导评分，得到完整 CCG 推导的评分公式：

据此可以定义 $f$ 代价。边的 $f$ 代价是两项之和：$g(n)$ 是该边所表示跨度的代价，$h(n)$ 是完成一项包含该边的推导所需代价的估计；二者也常称为内部代价和外部代价。利用公式 G.13 定义一条边的 $g(n)$，即对构成该跨度的各超标签代价求和。

对 $h(n)$，需要一个近似、但绝不高估最终推导实际代价的分数。一种满足该要求的简单启发式是假定：跨度外的每个词都会被指派其最大概率超标签。若最终推导确实使用这些标签，其分数就等于启发式值；若最终推导使用任何其他标签，新标签的代价必定更高，因此保证启发式不会高估。

综合以上内容，一条边的合适 $f$ 代价定义为：

例如，在句子

(G.15) United serves Denver.

中，考虑一条表示词 serves、超标签为 $N$ 的边。其 $g$ 代价就是该标签的负对数概率 $-\log_{10}(0.1)=1$。外部 $h$ 代价采用对 United 和 Denver 最乐观的超标签指派，分别是 $N/N$ 和 $NP$。因此，该边最终的 $f$ 代价为 1.443。

G.6.4 示例¶

图 G.2 展示本例的初始议程和完整句法分析过程。利用超标注器信息初始化议程和句法分析表后，算法从议程中选出最佳边：United、标签 $N/N$、$f$ 代价 0.591。这条边不是完整分析，因此应用所有相关语法规则生成新状态。在本例中，对 United: N/N 和 serves: N 应用前向函数应用，会把边 United serves: N[0,2], 1.795 加入议程。

略过若干步骤，在第三轮迭代中，表示完整推导的边 United serves Denver, S[0,3], 0.716 被加入议程。但算法此时不会终止，因为该边的代价 0.716 尚未使它位于议程顶端；弹出的反而是范畴为 $NP$ 的 Denver 边。这会向议程加入另一条边，即对 Denver 进行类型提升。处理完该边之后，先前表示完整推导的状态才升至议程顶端，被弹出、接受目标检验并作为解返回。

$A^*$ 方法的效果体现在图 G.2 的状态着色和最终句法分析表中。蓝色边——包括所有没有明确画出的初始词汇范畴指派——表示搜索空间中从未到达议程顶端的状态，因而也从未向最终分析表贡献任何边。这与 PCKY 方法形成对比：后者系统地为输入中所有可能跨度填入全部可能成分，使分析表充斥着大量不会贡献最终分析的成分。

图 G.2　对 “United serves Denver” 进行 $A^*$ 搜索的示例。蓝色方框中的带圈数字表示状态从议程弹出的顺序。各状态的代价是使用负 $\log_{10}$ 概率计算的 $f$ 代价。