Viterbi算法
学习自
http://blog.ivank.net/viterbi-algorithm-clarified.html#:~:text=%20Viterbi%20Algorithm%20Clarified%20%201%20Defining%20a,problem%20is%20based%20on%20dynamic%20programming.%20More%20
维特比算法，作者举了一个例子来说明其中的原理，或者说是算法过程。
具体例子是关于医生、患者、症状。
假设患者连续三天看医生，患者有两种结论，健康和生病。患者有三种症状，正常、感冒、头晕，连续三天的症状分别是正常、感冒和头晕。
基于之前的样本分析，假定
Start - 初始状态，一个人处于健康的的概率是60%，生病的概率是40%。
Transition - 状态转换，如果一个人第一天是处于健康的状态，那么第二天仍然处于健康状态的概率是70%，生病的概率是30%。
如果一个人第一天是处于生病的状态，那么第二天处于健康状态的概率是40%，仍然处于生病的概率是60%。
Emission - 在健康状态时，患者报告正常的概率是50%，感冒的概率是40%，头晕的概率是10%。
在生病状态时，患者报告正常的概率是10%，感冒的概率是30%，头晕的概率是60%。
现在根据三天上报的症状{正常，感冒，头晕}，判断三天的健康状态分别是什么样的概率最大？
在不考虑症状，只考虑初始状态健康/生病的概率和健康<->生病这个状态机的转换关系，可以计算出8种状态（3天，每天2个状态，2×2×2）的概率大小。
| 生病 |
生病 |
生病 |
0.4×0.6×0.6=0.144 |
| 生病 |
生病 |
健康 |
0.4×0.6×0.4=0.096 |
| 生病 |
健康 |
生病 |
0.4×0.4×0.3=0.048 |
| 生病 |
健康 |
健康 |
0.4×0.4×0.7=0.112 |
| 健康 |
生病 |
生病 |
0.6×0.3×0.6=0.108 |
| 健康 |
生病 |
健康 |
0.6×0.3×0.4=0.072 |
| 健康 |
健康 |
生病 |
0.6×0.7×0.3=0.126 |
| 健康 |
健康 |
健康 |
0.6×0.7×0.7=0.294 |
当需要把症状考虑在内，在三天症状为{正常，感冒，头晕}时候，三天的健康状态的概率分别是多少呢？
以三天分别为{健康，生病，生病}，计算其概率。
第一天健康且上报正常的概率是0.6×0.5=0.3
第二天生病且上报感冒的概率是0.3×0.3=0.09
第二天生病且上报头晕的概率是0.6×0.6=0.36
那么三天判定为{健康，生病，生病}的概率是0.3×0.09×0.36=0.00972
这样可以遍历8种状态的概率，最后可以得出{健康，健康，生病}的概率最大。
但是上述例子观察的仅仅是3天，如果是10天，那么就存在2^10=1024种状态了，如果是100天，那么就是2^100，再使用上面的方法就不是最优了。
维特比算法是在路径中找出概率最大的路径。由下图中使用1代表健康，使用0代表生病，可知，最大的路径遍历是{1, 1, 0}即{健康，健康，生病}。
维特比算法的其他应用，例如用户误将tower输入成了toqer，需要提示用户将其修改为tower。类比于猜测连续5天的患者的健康状态，现在是要计算出5个最有可能的字母是什么。
Start - 初始状态，26个字母的概率，共26个值
Transition - 状态转换，例如字母o后面跟着字母q的概率，共26×26个值
Emission - 这个像是一个条件概率，请教了英语专业的朋友，告知了上下文，也不知道这个“Emission”翻译成什么合适。
实际要输入某个字母，用户实际输入成各个字母的概率，例如用户本身需要输入字母F，实际输入F的概率是90%，G的概率是4%，共26×26个值
初始状态和状态转换可以从大量的现有英语文本中，例如英文书籍等，统计得出，Emission可以通过人工进行设定。
当使用“toqer”作为输入时候，使用维特比算法，可以得出最后的单词是“tower”。
…