哥伦比亚NLP第二周#5-8
模型的解码-维特比算法
把模型的参数估计完成之后,下一步要做的就是计算出。最顺理成章的想法是算出所有可能的y的条件概率,找到概率最大的那个。但暴力枚举的时间复杂度太大了,因此我们就采用了维特比算法-一个动态规划求最可能路径的算法。
首先描述一下我们的问题:对于一个输入序列,求给定一个输出序列的最可能的输入序列。,而且我们定义函数:
首先我们想到的算法是BFS:
用BFS来遍历所有可能的序列,然后分别计算出各自的可能性。这个方法在数据量不大的时候还有实现的可能,如果面对的是百万级的数据量,那么计算的结果可能要等到天荒地老了。对于BFS,复杂度是指数级的。
所以我们想到了维特比算法:
- 定义为句子长度
- 定义是从起始点到k点的可能序列
- 定义函数:
-定义表示长度为k,并以结尾的所有标注序列中的最大概率:
容易得到递推关系式:(如下图)
下面我们来看一个例子:
首先我们给下面的句子标号,然后按照公式计算出最大值。
最后总结的求取最大值的算法如下:
而完整的维特比算法如下: