绿色健康小清新

耐得住寂寞,守得住繁华

Viterbi-Algorithm(维特比算法)

Viterbi-Algorithm

维特比算法是一个特殊但应用最广的动态规划算法。利用动态规划,可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图-篱笆网了(Lattice)的有向图最短路径问题而提出来的。它之所以重要,是因为凡是使用隐马尔科夫模型描述的问题都可以用它解码,包括当前的数字通信、语音识别、机器翻译、拼音转汉字、分词等。

背景

假定用户(盲打时)输入的拼音时y1,y2,,yNy_1,y_2,\cdots ,y_N,对应的汉字是x1,x2,,xNx_1,x_2,\cdots,x_N(虽然真正的输入法产品都是以词作为输入单位的,为了便于说明问题及简单起见,以字为单位来解释维特比算法),那么根据当前介绍的工具:

x1,x2,...,xN=argmaxxPP(x1,x2,,xNy1,y2,,yN)=argmaxxXi=1NP(yixi)P(xixi1)(1)x_1,x_2,...,x_N=\arg\max\limits_{x∈P}P(x_1,x_2,\cdots,x_N|y_1,y_2,\cdots,y_N)=\arg\max\limits_{x∈X}\prod^N_{i=1}P(y_i|x_i)P(x_i|x_{i-1}) \tag{1}

输入的可见序列为y1,y2,,yNy_1,y_2,\cdots ,y_N,而产生他们的隐含序列是x1,x2,,xNx_1,x_2,\cdots,x_N。可以用下图描述这样一个过程:

这是一个相对简单的隐马尔科夫链,没用状态跳跃,也没有自环。P(xixi1)P(x_i|x_{i−1})是状态之间的转移概率,P(yixi)P(y_i|x_i)是每个状态的产生概率。现在,这个马尔科夫链的每个状态的输出是固定,但是每个状态的值可以变化。比如输出读音”zhong”的字可以是”中”、”种“等多个字。我们不妨抽象一点,用符号xijx_{ij}表示状态xix_i的第jj个可能的值。如果把每个状态按照不同的值展开,就得到下面这个篱笆网络(Lattice)

在上图中,每个状态有3个或4个值,当然时间中它们可以有任意个值。

那么从第一个状态到最后一个状态的任何一条路径(Path)都可能产生我们观察到的输出序列Y。当然这些路径的可能性不一样,而我们要做的就是找到最可能的这条路径,并不是很难。但麻烦的是这样的路径组合数非常多,会让序列状态数的增长呈指数式增长。汉语中每个无声调的拼音对应13个左右的国标汉字,假定句子长为10个字,那么这个组合数为13105×101413^{10} \sim 5 × 10^{14},这个计算量就相当的大了。因此,需要一个最好能和状态数目成正比的算法,而这个算法在1967年首次提出,即维特比算法。


维特比算法基础

维特比利用动态规划的思想来求解概率最大路径(可理解为求图最短路径),使得复杂度正比于序列长度,复杂度O(ND2)O(N\cdot D^2),N为长度,D为宽度,从而很好地解决了问题的求解。

维特比算法的基础可以概括为下面三点:

  1. 如果概率最大的路径P(或者说是最短路径)经过某个点,比如下图中的x22x_{22},那么这条路径上从起始点S到x22x_{22}的这一段路径Q,一定是S到x22x_{22}之间的最短路径。否则,用S到x22x_{22}的最短路径R代替Q,便构成了一条比P更短的路径,这就和之前的假设矛盾了。
  2. 从S到E路径必定经过第i时刻的某个状态,假定第i时刻有k个状态,那么如果记录了从S到i个状态的所有k个节点(所有时刻的所有状态)的最短路径,最终的最短路径必经过其中的一条。这样,在任何时刻,只要考虑非常有限条候选路径即可。
  3. 结合以上两点,假定当我们从状态i进入到i+1时,从S到i上各个节点的最短路径已经找到,并且记录到这些节点上,那么在计算出从起点S到第i+1状态的某个结点的最短路径时,只要考虑从S到前一个状态i所有的k个节点的最短路径,以及从这k个节点到xi+1,jx_{i+1},j的距离即可。

为了记录中间变量,引入变量δ\deltaψ\psi。定义t时刻到状态为i的所有结点最大概率值(最短路径):

δt(i)=maxP(it=i,it1,,i1,ot,,o1λ),  i=1,2,,N\delta_t{(i)} = \max P(i_t=i,i_{t-1},\cdots,i_1,o_t,\cdots,o_1|\lambda),\ \ i=1,2,\cdots,N

其中, iti_t表示最短路径, oto_t表示观测符号, λ\lambda表示模型参数。依据上式可以得出变量 δ\delta的递推式:

δt+1(i)=max[δt(j)aji]bi(ot+1),  i=1,2,,N;t=1,2,,T1\delta_{t+1}(i)=max[\delta_t(j)\cdot a_{ji}]\cdot b_i(o_{t+1}), \ \ i=1,2,\cdots,N;t=1,2,\cdots,T-1

表示t时刻处于状态jj,t+1时刻转移到状态 ii 且观测到符号 ot+1o_{t+1}的最大概率。

定义 ψt(i)\psi_t(i) 为时刻t到状态为i的概率最大路径的前一个时刻经过的结点,即它保存了最短路径所经过的结点:

ψt(i)=argmax1jN[δt1(j)aji]\psi_t(i) = \arg\max\limits_{1\le j\le N}[\delta_{t-1}(j)\cdot a_{ji}]

可以看到,其实ψ\psi的值就是我们之前算的δ\delta的前一项max的值所对应的状态!


举例

这里给出一个盒子和球的例子,跟我们之前在HMM中所讲的例子是一样的!只不过使用了维特比算法!

👉 HMM(隐马尔科夫模型)

假设我们有3个盒子,每个盒子里都有红色和白色两种球,这三个盒子里球的数量分别是:

盒子123
红球数547
白球数563

按照下面的方法从盒子里抽球,开始的时候,从第一个盒子抽球的概率是0.2,从第二个盒子抽球的概率是0.4,从第三个盒子抽球的概率是0.4。以这个概率抽一次球后,将球放回。然后从当前盒子转移到下一个盒子进行抽球。规则是:如果当前抽球的盒子是第一个盒子,则以0.5的概率仍然留在第一个盒子继续抽球,以0.2的概率去第二个盒子抽球,以0.3的概率去第三个盒子抽球。如果当前抽球的盒子是第二个盒子,则以0.5的概率仍然留在第二个盒子继续抽球,以0.3的概率去第一个盒子抽球,以0.2的概率去第三个盒子抽球。如果当前抽球的盒子是第三个盒子,则以0.5的概率仍然留在第三个盒子继续抽球,以0.2的概率去第一个盒子抽球,以0.3的概率去第二个盒子抽球。如此下去,直到重复三次,得到一个球的颜色的观测序列:

O={}O = \{红,白,红\}

注意在这个过程中,观察者只能看到球的颜色序列,却不能看到球是从哪个盒子里取出的。

我们的观察集合是:

V={,}, M=2V=\{红,白\}, \ M=2

我们的状态集合是:

Q={123} N=3Q = \{盒子1,盒子2,盒子3\}, \ N=3

而观察序列和状态序列的长度为3.

初始状态分布为:

=(0.2,0.4,0.4)T\prod = (0.2,0.4,0.4)^T

状态转移概率分布矩阵为:

A={0.50.20.30.30.50.20.20.30.5}A = \left\{\begin{matrix} 0.5 & 0.2 & 0.3\\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.3 & 0.5 \end{matrix}\right\}

观测状态概率矩阵为:

B={0.50.50.40.60.70.3}B = \left\{ \begin{matrix} 0.5 & 0.5 \\ 0.4 & 0.6 \\ 0.7 & 0.3 \end{matrix}\right\}

我们已知球的颜色观测序列:

O={}O = \{红,白,红\}

试求最优状态序列。

求解:

首先需要得到三个隐藏状态在时刻1时对应的各自两个局部状态,此时观测状态为1:

δ1(1)=π1b1(o1)=0.2×0.5=0.1δ1(2)=π2b2(o1)=0.4×0.4=0.16δ1(3)=π3b3(o1)=0.4×0.7=0.28\delta_1(1) = \pi_1b_1(o_1) = 0.2\times0.5 = 0.1 \\ \delta_1(2) = \pi_2b_2(o_1) = 0.4\times0.4 = 0.16 \\ \delta_1(3) = \pi_3b_3(o_1) = 0.4\times0.7 = 0.28 \\

ψ1(1)=ψ1(2)=ψ1(3)=0\psi_1(1) = \psi_1(2) = \psi_1(3) = 0

现在开始递推三个隐藏状态在时刻2时对应的各自两个局部状态,此时观测状态为2:

δ2(1)=max1j3[δ1(j)aj1]b1(o2)=max1j3[0.1×0.5,0.16×0.3,0.28×0.2]×0.5=0.028max1j3[δ1(j)aj1]=0.28×0.2  ψ2(1)=3\delta_2(1) = \max\limits_{1\le j\le3}[\delta_1(j)a_{j1}]b_1(o_2) = \max\limits_{1\le j\le3}[0.1\times0.5,0.16\times0.3,0.28\times0.2]\times0.5=0.028 \\ \max\limits_{1\le j \le 3}[\delta_{1}(j)\cdot a_{j1}] = 0.28 \times 0.2 \ \rightarrow \ \psi_2(1) = 3 \\

δ2(2)=max1j3[δ1(j)aj2]b2(o2)=max1j3[0.1×0.2,0.16×0.5,0.28×0.3]×0.6=0.0504max1j3[δ1(j)aj2]=0.28×0.3  ψ2(2)=3\delta_2(2) = \max\limits_{1\le j\le3}[\delta_1(j)a_{j2}]b_2(o_2) = \max\limits_{1\le j\le3}[0.1\times0.2,0.16\times0.5,0.28\times0.3]\times0.6=0.0504 \\ \max\limits_{1\le j \le 3}[\delta_{1}(j)\cdot a_{j2}] = 0.28 \times 0.3 \ \rightarrow \ \psi_2(2) = 3 \\

δ2(3)=max1j3[δ1(j)aj3]b3(o2)=max1j3[0.1×0.3,0.16×0.2,0.28×0.5]×0.3=0.042max1j3[δ1(j)aj3]=0.28×0.5  ψ2(3)=3\delta_2(3) = \max\limits_{1\le j\le3}[\delta_1(j)a_{j3}]b_3(o_2) = \max\limits_{1\le j\le3}[0.1\times0.3,0.16\times0.2,0.28\times0.5]\times0.3=0.042 \\ \max\limits_{1\le j \le 3}[\delta_{1}(j)\cdot a_{j3}] = 0.28 \times 0.5 \ \rightarrow \ \psi_2(3) = 3 \\

继续递推三个隐藏状态在时刻3时对应的各自两个局部状态,此时观测状态为1:

δ3(1)=max1j3[δ2(j)aj1]b1(o3)=max1j3[0.028×0.5,0.0504×0.3,0.042×0.2]×0.5=0.00756max1j3[δ2(j)aj1]=0.0504×0.3  ψ3(1)=2\delta_3(1) = \max\limits_{1\le j\le3}[\delta_2(j)a_{j1}]b_1(o_3) = \max\limits_{1\le j\le3}[0.028\times0.5,0.0504\times0.3,0.042\times0.2]\times0.5=0.00756 \\ \max\limits_{1\le j \le 3}[\delta_{2}(j)\cdot a_{j1}] = 0.0504\times 0.3 \ \rightarrow \ \psi_3(1) = 2 \\

δ3(2)=max1j3[δ2(j)aj2]b2(o3)=max1j3[0.028×0.2,0.0504×0.5,0.042×0.3]×0.4=0.01008max1j3[δ2(j)aj2]=0.0504×0.5  ψ3(2)=2\delta_3(2) = \max\limits_{1\le j\le3}[\delta_2(j)a_{j2}]b_2(o_3) = \max\limits_{1\le j\le3}[0.028\times0.2,0.0504\times0.5,0.042\times0.3]\times0.4=0.01008 \\ \max\limits_{1\le j \le 3}[\delta_{2}(j)\cdot a_{j2}] = 0.0504\times 0.5 \ \rightarrow \ \psi_3(2) = 2 \\

δ3(3)=max1j3[δ2(j)aj3]b3(o3)=max1j3[0.028×0.3,0.0504×0.2,0.042×0.5]×0.7=0.0147max1j3[δ2(j)aj3]=0.042×0.5  ψ3(3)=3\delta_3(3) = \max\limits_{1\le j\le3}[\delta_2(j)a_{j3}]b_3(o_3) = \max\limits_{1\le j\le3}[0.028\times0.3,0.0504\times0.2,0.042\times0.5]\times0.7=0.0147 \\ \max\limits_{1\le j \le 3}[\delta_{2}(j)\cdot a_{j3}] = 0.042\times 0.5 \ \rightarrow \ \psi_3(3) = 3 \\

此时已经到最后的时刻,我们开始准备回溯:

  • 此时最大概率为δ3(3)\delta_3(3),从而得到i3=3i_3^*=3
  • 由于ψ3(3)=3\psi_3(3)=3,所以i2=3i^*_2=3
  • 又由于ψ2(3)=3\psi_2(3)=3,所以i1=3i^*_1=3

从而可得到当观测序列为(红,白,红)时得到最终的最可能的隐藏状态序列为:

(i1,i2,i3)=(3,3,3)(i^*_1,i^*_2,i^*_3) = (3,3,3)


总结

维特比算法也是寻找序列最短路径的一个通用方法,和dijkstra算法有些类似,但是dijkstra算法并没有使用动态规划,而是贪心算法。同时维特比算法仅仅局限于求序列最短路径,而dijkstra算法是通用的求最短路径的方法。

总的来说,无论在语音识别、输入法打字中,输入都是按照流(Stream)的方式进行的,只要处理每个状态的时间比讲话,或者打字速度,那么无论输入有多长,解码过程永远就是实时的。

-------------本文结束感谢您的阅读-------------
六经蕴籍胸中久,一剑十年磨在手

欢迎关注我的其它发布渠道