|
- UID
- 1029342
- 性别
- 男
|
维特比算法(Viterbi algorithm)是一种动态规划算法，它用于寻找最可能产生观测到的事件的序列，这个序列是隐含状态序列，也叫维特比路径(Viterbi path)。最典型的应用场景是马尔科夫信息源上下文和隐马尔科夫模型(HMM)。
该算法广泛应用于通信技术中的解卷积码，例如：CDMA、GSM数字蜂窝网、拨号调制解调器、卫星、深空通信以及802.11无线网。当前，该算法也经常用于语音识别、语音合成、说话人分割（diarization, 姑且这么翻译，它的意思是将同一段语音中不同人的话语归为一类）[1] 、关键词识别、计算语言学、生物信息学中。例如，在语音转文本中（语音识别），声音信号作为观察到的事件序列，而文本序列作为声音信号的隐含原因。对于给定的声音信号，维特比算法找出最可能的文本序列。
历史(History)维特比算法是以Andrew Viterbi 的名字来命名的，他在1967年提出了这个算法，作为含噪声的数字通信链路中卷积码的解码方法。[2] 不过，该算法具有multiple invention的历史——至少有7个独立的发明者，包括：Viterbi, Needleman and Wunsch, and Wagner and Fischer.[3]
“维特比（路径，算法）”已经成为使用动态规划解决概率最大化问题的标准术语。[3] 例如，在statistical parsing中，对于一个单词序列，动态规划算法能找到最可能上下文无关的语法分析结果，通常称之为“维特比分析”。[4][5][6]
算法(Algorithm)假设在一个隐马尔科模型(HMM)中，状态空间为S, 状态i的初始概率为πi, 状态i到j的转移概率为ai,j。观察到的值为y1, y2, …, yT 。产生观察值的最可能状态序列是x1, x2, …, xT通过下面的迭代关系给出：[7]
 其中Pt,k是以k为最终状态的前t个观察值对应的最可能的状态序列的概率, P(yt|k)是在隐含状态k对应观察值yt的生成概率。维特比路径可以通过保存等式(2)中用到的x的反向指针得到。
根据公式（2），维特比算法计算中需要考察每个状态的|S|个值和前一状态的|S|个值从而计算当前最佳，即每个状态需要O(|S|2)次计算，总共的状态数量为T,所以总的时间复杂度为: O(T × |S|2)。
实例(Example)以乡村中原始的小诊所为例。村民只有两种简单的属性：健康或者发烧。他们只能通过诊所的医生知道自己是否发烧。聪明的医生通过询问病人感觉如何来诊断是否发烧；村民的回答是：正常、头晕、寒冷三者之一。
假设某病人每天都来诊所告诉医生她感觉如何。医生认为病人的健康状况是一个离散的马尔科夫链（Markov chain）。有两种状态“Healthy”和”Fever”，但是医生没法直接观察到，也就是说这两个状态对医生来说是隐藏(hidden)的。每天，病人会基于自身健康状况，以某个几率告诉医生他的感觉：可能是”normal”、”cold”或”dizzy”三者之一，这些事观察值。这里的整个系统可以看做是隐马尔科夫模型（HMM）。
医生了解村民通常的健康状况，以及是否有发热情况下的症状。也就是说，HMM的参数是已知的。这可以表示为下面的Python变成语言：
//初始状态states = ('Healthy', 'Fever')//观察值observations = ('normal', 'cold', 'dizzy') //初始概率start_probability = {'Healthy': 0.6, 'Fever': 0.4} //转移概率transition_probability = { 'Healthy' : {'Healthy': 0.7, 'Fever': 0.3}, 'Fever' : {'Healthy': 0.4, 'Fever': 0.6} }//生成概率emission_probability = { 'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1}, 'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6} }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| //初始状态
states
=
('Healthy',
'Fever')
//观察值
observations
=
('normal',
'cold',
'dizzy')
//初始概率
start_probability
=
{'Healthy':
0.6,
'Fever':
0.4}
//转移概率
transition_probability
=
{
'Healthy'
:
{'Healthy':
0.7,
'Fever':
0.3},
'Fever'
:
{'Healthy':
0.4,
'Fever':
0.6}
}
//生成概率
emission_probability
=
{
'Healthy'
:
{'normal':
0.5,
'cold':
0.4,
'dizzy':
0.1},
'Fever'
:
{'normal':
0.1,
'cold':
0.3,
'dizzy':
0.6}
}
|
这段代码中，start_probability表示病人第一次去诊所时医生认为他属于HMM某个状态的经验知识（医生所知道的只有病人更倾向于健康，0.6的概率为Healthy, 0.4的概率为Fever）。transition_probability表示马尔科夫链中的健康情况转变。在上述例子中，如果病人今天是Healthy那么明天有30%的几率是Fever. emission_probability表示的是在不同的健康状况下不同感觉的可能性，这个可以称为生成概率，也可以叫做状态发射概率。比如：如果他是Healthy的，那么感觉是normal的概率是50%；如果是Fever, 感觉dizzy的概率是60%。 |
|
