与最佳路径不同的问题
现有语言模型课文推导前向似然及维特比(Viterbi)最佳路径。这里使用整段观测,询问某一时刻状态的后验分布。这是平滑:它不同于只用目前为止观测的过滤,也不同于选择一条最可能的完整路径。
使用有限隐藏状态集合 、长度 的非空观测序列 、初始概率 、转移概率 及发射概率 。与现有课文一样,模型指定一阶状态链,以及给定状态后条件独立的发射。初始概率构成概率分布;每个状态对应的转移及发射概率也各自构成概率分布。
前缀与后缀量
定义 11.1.1
(前向值与后向值)
状态 在时刻 的前向值,是观测前缀与该状态同时出现的概率:
后向值 把从时刻 的状态 之后开始的所有可能后缀状态序列之模型转移与发射乘积相加:
空后缀(即 )的权重为一。两者都满足一步递推:
记 为整段序列的似然。
当 时, 是给定该状态后较晚观测的条件概率。后缀乘积的定义也为零概率状态指定数值,而不必对零概率事件取条件。
定理 11.1.2
(平滑恒等式)
对每个 及状态 ,
对 及状态 ,
若 ,平滑后验为
而且它们互相一致:,。
证明
(在时刻 t 分割每条路径)
固定 。在联合模型中,每条相容完整路径可分为一段以 结束的前缀,以及由 转移出去的后缀。把乘积对两组选择求和得到 。当 时这就是 ,对 求和便得 。
对 ,按相邻状态 、 分割。路径权重分解为到 为止的前缀、单一步 ,以及 之后的后缀,由此得到所述联合概率。除以 便得 及 。
关于一致性,后向递推给出 ,前向递推给出 。除以 即得两条边际化等式。
证明透视
分解在哪里被使用
模型假设只在一处进入:完整路径的权重是一个初始因子,加上每一步的一个转移因子和一个发射因子的乘积。在时刻 把这个乘积切开,涉及 的因子构成前缀,涉及 的因子构成后缀。两组因子恰好共用一个变量 。这就是必须先固定 的原因,也是前缀与后缀的双重求和能分离为两个和之乘积的唯一理由。
所以关键一步是分配律:对前缀与后缀各自独立求和,把指数多条路径换成两个长度为 的向量。论证能够收尾,是因为 使 的情形正好就是 的定义,而每条递推只是把同一刀移动一步。
有两点并未声称。第一,论证没有说给定观测后隐藏状态彼此独立:等式只对每个固定的 逐一成立,多个时刻的联合后验并不等于各 的乘积。第二,除了模型本身,唯一需要额外假设的是最后的除法,它要求 。
若 ,这些条件后验不能由该比率定义。例如所有状态都给观测到的词零概率时,每条完整路径的观测概率都是零。把 换成均匀向量是额外约定,并非上述后验。
两状态计算
例题 11.1.3
(两状态模型中的平滑)
取状态 、初始向量 、转移矩阵
以及发射概率 、、、。对观测 ,前向及后向值为
因此
作比较,时刻一的过滤只用 ,得到 ;较晚观测令其平滑概率变成 。
反例模式
逐时刻众数未必是最佳路径
这里时刻一最可能状态是 ,时刻二是 ,所以逐个选边际众数得到 ,其后验概率为 。完整路径 的后验概率为 ,更为可能。因此逐个最大化边际分布并非维特比解码,即使此例四种转移都可能。
例题 11.1.4
(单一观测:平滑等于过滤)
沿用同一模型,但观测序列只有一个符号 ()。此时 、,所以 ,而
没有较晚的观测,所以平滑与过滤一致;又因为不存在 ,所以没有相邻状态后验 。这是递推的边界情形。
例题 11.1.5
(被证据排除的状态)
保留初始向量及 ,但把状态 的发射改为 、,并保留 、。对观测 :
后向值为 ,以及 、。于是
观测 在状态 不可能出现,所以状态 在时刻二的平滑概率为零,尽管它的先验概率为正。作核对:,,两者之和为 。
常见错误
常见错误
(把平滑边际分布当作互相独立)
在两状态计算中,,但路径 的后验概率是 。 只描述单一时刻;要得到多个时刻的联合后验,需要相邻状态项 (更长路径则要用完整的链分解)。
常见错误
(用前缀总和作规范化)
在 时, 是过滤用的常数,并非 。在两状态计算中 ,而 。若以 去除 ,所得数值之和不等于一。平滑的分母永远是整段序列的似然 。
成本与习题
对稠密转移及常数时间算术,计算全部前向及后向值需 时间。存储全部前向值并滚动使用一个后向向量,可用 个存储值按时间倒序输出状态后验;输出每个 本身便有 个值。长乘积在浮点运算中可能下溢;缩放或 log-sum-exp 实现必须一致地保留规范化。
快速检查
( 是多少?)
想一想时刻 之后有哪些观测。
解答 · 答案
:后缀为空,没有较晚的观测需要生成,空乘积等于一。
快速检查
(在观测为 的两状态例子中, 是多少?)
读出 矩阵第 行第 列的元素。
解答 · 答案
。
快速检查
(在两状态例子中,把 的第一列相加,应等于哪个平滑后验?)
对较早的状态 求和。
解答 · 答案
:对 求和 得到时刻二状态 的后验。
快速检查
(若 ,能计算 的公式吗?)
留意分母。
解答 · 答案
不能。公式是以 为分母的比率, 没有数值;对概率为零的观测事件取条件,不能由此比率给出。