动机
字词序列比词数多带信息。成分结构描述句子如何由小片语组合,隐状态模型描述未观察类别如何产生词元。两者都把无限制的理解问题化成明确任务:解析器问文法允许哪些推导,HMM 问指定参数下的概率或最佳状态路径。任何一种答案都不自动等于完整意思。
歧义令这个区分重要。同一句可有多棵解析树,多条状态路径也可解释同一观察。算法必须先决定是保留所有可能、把概率相加,还是只选最大者。交换这些运算会改变问题。动态规划的用处,是许多候选解释共享相同子问题,不必重算。
本节给有限模型,完整证明受限文法的 CKY,以及 HMM 前向与维特比(Viterbi)推理。
定义
定义 7.1.1
(上下文无关文法、解析树与歧义)
上下文无关文法含有限非终结符 、终结词汇 、起始符 及产生式。解析树内节点按产生式展开,叶由左至右给词元序列。语言中同一句若有两棵以起始符 为根的不同解析树,文法便有歧义;这关于结构解释,不只是句子是否被接受。
定义 7.1.2
(Chomsky 范式与 CKY 图表)
CKY 假设无空产生式、无单位产生式的 Chomsky 范式,每条是 或 。输入非空 。空句或单位链要另扩充,不能直接套本递推。令 包含恰可推导 的非终结符,两端索引均包括在内。
定义 7.1.3
(隐马尔可夫(Markov)模型、似然与维特比解码)
HMM 有有限隐状态 、初始概率 、转移 ,以及有限词汇上的发射概率 。、 每行和为一,且 。状态转移是一阶 Markov,给定状态后各发射条件独立。路径与观察的联合概率为:
这些独立假设定义模型,并不是动态规划推导出的现实性质。观察似然把所有隐路径的联合概率相加;维特比则取最大。若观察似然正,最大后验路径与最大联合路径相同,因各候选共享同一分母。
定理/命题
定理 7.1.4
(CKY 识别与解析重建)
先把所有有规则 的 放进 。按片段长递增,若某切点 及规则 满足 、,便把 加入 。最后 在格内,当且仅当它可推导该片段;句子合法当且仅当 。保存每个见证规则与切点,可用有限共享图表表示全部解析树。
定理 7.1.5
(前向相加与维特比取最大)
非空观察序列的初值为 ,之后:
; 是长度 、末态 的路径中最大联合概率。故似然为 ,最佳路径联合值为 。记最大前驱即可重建一条最佳路;要全部同分路径,须保留并列见证。
命题 7.1.6
(由标记计数得最大似然行)
固定状态 ,设 为由 出发的转移计数,总数 。在所有概率行 中,函数 (约定 )有唯一最大点 。发射行及初始分布用各自的计数,同样方法最大化。
证明思路
证明
(对片段长度归纳)
CKY 对片段长归纳。单词推导只能用词汇规则,正是初值。较长树的根必用 ,左子树覆盖一个非空前段,决定唯一切点,右子树覆盖余段。归纳给两子符号已在相应格,故插入 ,证完整。反过来,每次插入都有两份较短合法推导,可接成根规则,证可靠。保存见证能重建树,只保成员则只知存在。
证明透视
范式与片段次序用在哪里
范式用了两次。长度一的片段只能由词汇规则推导,因为没有空规则或单位规则;较长的片段必由二元规则推导,两个子节点都非空,因此都严格较短。正是这种严格缩短,使对片段长度的归纳成立:每一格只依赖较短片段的格。
关键一步是切点 属于见证的一部分。同一条根规则的不同切点给出不同的树,所以递推要遍历所有 ;若只问存在,一个成功的切点已足够。论证从两个方向收尾:由推导经归纳得到图表项目,由图表项目又取得两份较短推导并接合。
单位规则 会破坏这个次序,因为格 会依赖自己;若有 、 这样的循环,同一片段更有无穷多棵树。空产生式则允许子节点覆盖零个词元。两者都需要明确扩充,如上文所说。
直接循环各二元规则、片段及切点,时间为 ,成员空间为 。回指数据可更大,逐棵列出所有树的输出甚至可指数多。多项式时间识别不表示解析棵数也是多项式。
证明
(按上一状态分割路径)
前向递推把所有末态 的路径按上一状态 分成互斥情况。模型分解给前缀值乘转移及本次发射,互斥情况再相加。对 归纳得每格意义,最后相加末态便恰数每路径一次。
证明
(以较佳前缀取代前缀)
维特比固定最后两态 ,各候选路径共享同一非负末段因子,所以用末态 的最佳前缀取代较差前缀不会降低值。对 取最大,再对末态取最大,即得最优。记录达到最大值的前驱,便能反向追索。此证明依赖末段只看 及当前词,不能不加修改套到任意长程依赖模型。
概念视角算法
同一依赖图回答两个问题
前向与维特比都沿时间—状态图传讯,乘法都用来延伸路径。加法总计互斥解释,最大值选一个解释。因此把加法换成最大值,是把似然改成最佳路径概率,不只是较快地计算同一答案。
稠密转移下两法运算量均为 。似然只要两个长度 数组;重建路径须存储指针或重算。长乘积会数值下溢,维特比可用对数并把零记为负无穷;前向则需缩放或 log-sum-exp,不能只取对数最大值,否则改变原来求和。
训练若观察到隐状态,参数估计可直接推导。 是分开各序列计数的 到 转移次数, 是 发射 的次数。完整数据似然分成多项分布因子,每行一个,所以每行可各自最大化。
证明
(最大化多项分布行)
记 ,并设 为任意概率行。 的项对目标贡献为零,所以只有集合 有影响,而且要得到有限值,须在 上 。于是
这里用了 ,且仅在 时取等号。全程取等号迫使 上 且 ,因此 以外 。故 是唯一最大点,零计数项在无平滑最优值为零。
整行零计数则不能由该似然识别,须另选策略,不能除零。状态未见的学习需要后验加权计数等另一程序,本节不声称已推导它。
证明透视
约束条件如何完成多项分布论证
除以 之后,两个目标值之差成为 乘以以 为权的 之和,并逐项使用 。这是唯一用到的分析性质。它把上界化为 ,而这个量不大于 ,恰恰因为 是一行概率:完成论证的是这个约束,而不是拉格朗日(Lagrange)乘数法。计数为零的项不出现在目标中,所以求和只限于 ;若 在 之外放了质量,便有 ,不等式严格成立。 的取等条件于是迫使 ,即得唯一性。
例题详解
例题 7.1.7
(小文法有两种结构解释)
规则 、,输入 aaa。三个单词格都有 S,两个长二格也由唯一切点得 S。长三格有两个见证:第一词后切得 ,第二词后切得 。同一格的成员 S 可代表两棵树。若要计数,把集合插入改为子树计数乘积的总和,结果为二,而非把两理由当一个。
例题 7.1.8
(似然与最佳路径不同)
状态 R,D,初值 ,转移行 、。a 的发射率为 ,b 为 。观察 ab,首步为 ;前向次步 ,似然 。维特比次步 ,最佳路 R,D,联合值 ,后验只有 。最佳单一解释仍未必接近确定。
例题 7.1.9
(标记序列学习要保留边界)
状态 R,R,D,D,R,词元 a,a,b,b,a。R 出发各有一次到 R、D,D 出发也各一次,所以转移两行均 。R 所见发射全为 a,D 全为 b,无平滑估计便为一或零。单序列初态全放 R。加入另一独立序列要新增初态计数,不能在前序列末态与后序列首态间虚构转移。
常见错误
反例模式
句子可识别,不代表解析唯一
接受 aaa,却有前述两种括法。格中只有一个 S 记存在,不记唯一。要分析歧义就保存见证或计数,不能把识别成功说成已选出正确意思。
常见错误
(把编号的 HMM 状态当作文法类别)
HMM 状态不必是人能解读的文法类别,除非建模时明确如此设定。状态只是模型中的索引,事后加上的名称是诠释,不是参数本身的性质。
常见错误
(逐时刻分别取最大)
逐时各选最大后验状态,也不是选整条最大联合路径;局部最喜欢的状态之间甚至可能有零概率转移。动态规划保留跨时约束,局部选择会丢掉它。
常见错误
(把成员资格当作概率,并忽略分词)
文法合法性与概率亦不同。多条推导不等于已有概率;加入规则概率须另定概率文法及任务。分词也是模型一部分,未见词、标点、多词表达不能假装已在固定词汇内。平滑可给未见事件正概率,但假设须与无平滑最大似然分开。
总结
CKY 按片段共享推导,以树结构归纳证识别。HMM 按时间与末态共享前缀,加总得似然,取最大得最佳路径。标记计数给明确多项分布估计,但零次数及序列边界要另处理。这些方法精确解决有限指定任务,语义理解及更丰富模型仍未完成。
练习
练习 7.1.10
(对文法 ,用三个根切点计算 的解析数,并说明单一成员格为何不足以存储这个数。)
核心
解答(3)
- 1
计算较短片段的解析数
设 为 的解析数,则 ,,。
- 2
对三个根切点求和
关键一步
。
依据: 根规则 把片段切在第一、二或三个词元之后,而两棵子树可独立选取。
- 3
与成员格比较
成员格只记 在格内,把五棵树合成一个符号;计数或共享回指才能保留额外信息。
练习 7.1.11
(列出两状态例题中观察 的四条隐路径联合概率,并验证似然及维特比的答案。)
核心
解答(3)
- 1
计算四个联合概率
初值 ,转移行 与 ,发射概率 、、、:
- 2
验证似然与最佳路径
总和为 ,最大值 在 。末态为 的路径相加得 ,末态为 的得 ,与前向各项吻合。
- 3
解读这两个数
似然是所有解释的总和,而最佳路径的后验为 。所以似然不能当作最佳单一解释的概率。
练习 7.1.12
(某已标记语料中,由状态 出发的转移计数为 。求无平滑最大似然行。另一状态的转移计数为 时,可得什么结论?)
基础
解答(3)
- 1
把已见计数规范化
总数为 ,所以最大似然行是 。
- 2
检查零项
给未见的第三个转移正概率,会削弱已见转移可用的质量,降低无平滑似然。
依据: 把正概率给未见转移,就要从已见转移取走质量。
- 3
处理没有观察的行
全零行的似然因子对每个概率行都相同,数据不识别唯一值;先验或平滑能选一个,但没有任何特定的行可以单由这些计数推出。
练习 7.1.13
(某两状态模型的初始概率为 ,转移矩阵为单位矩阵,两个状态都以概率一发射唯一的词元 。对观察 ,求似然、最佳联合概率及最佳路径数,并说明破同分指针保留什么。)
综合
解答(3)
- 1
找出概率为正的路径
路径 与 各为 。交叉路径 、 需要概率为零的转移,所以概率为零。
- 2
计算三个量
似然为 ,最佳联合值为 ,最大者有两条。
- 3
说明指针
确定的破同分指针只返回其中一条合法最佳路径;若不明确存下并列,另一个解释就会丢失。