人工智能算法效果评估：人工智能之维特比

人工智能算法效果评估：人工智能之维特比4、计算的详细过程据分析可知，Day1的天气取决于初始状态序列；Day2的天气仅取决于Day1；Day3的天气又只取决于Day2的天气。SunnyCloudyRainy0.630.170.20⑤状态转移矩阵：⑥发射矩阵：3、逻辑分析

概述

Viterbi算法其实是用动态规划算法求解最短路径。在《数学之美》这本书中是这样描述的，“维特比算法是一个特殊但应用最广的动态规划算法，利用动态规划，可以解决任何一个图中的最短路径问题。维特比算法是针对一个特殊的图--篱笆网络的有向图的最短路径问题而提出的。它之所以重要，是因为凡是使用隐含马尔科夫模型描述的问题都可以用它来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。”说白了，维特比算法就是求解最短路径的一种算法，求后一个时间点的最短路径，依赖于前一个时间点的路径。

一个详细实例

1、问题的描述

问题：假设连续观察3天的海藻湿度分别为{Dry Damp Soggy}，求这三天最可能出现的天气情况。

2、已知的信息

SunnyCloudyRainy0.630.170.20

⑤状态转移矩阵：

	Sunny	Cloudy	Rainy
Sunny	0.5	0.375	0.125
Cloudy	0.25	0.125	0.625
Rainy	0.25	0.375	0.375

⑥发射矩阵：

	Dry	Dryish	Damp	Soggy
Sunny	0.6	0.2	0.15	0.05
Cloudy	0.25	0.25	0.25	0.25
Rainy	0.05	0.10	0.35	0.5

3、逻辑分析

据分析可知，Day1的天气取决于初始状态序列；Day2的天气仅取决于Day1；Day3的天气又只取决于Day2的天气。

4、计算的详细过程

（1）Day1由于是初始状态，我们分别求

P(Day1-Sunny)=0.63*0.6;

P(Day1-Cloudy)=0.17*0.25;

P(Day1-Rain)=0.20*0.05;

Choose max{ P(Day1-Sunny) P(Day1-Cloudy) P(Day1-Rainy)} 得到P(Day1-Sunny)最大，得出第1天Sunny的概率最大。

（2）Day2的天气又取决于Day1的天气状况，同时也受Day2观察的海藻情况影响。

P(Day2-Sunny)= max{ P(Day1-Sunny)*0.5 P(Day1-Cloudy)*0.25 P(Day1-Rainy)*0.25} *0.15;

P(Day2-Cloudy)= max{ P(Day1-Sunny)*0.375 P(Day1-Cloudy)*0.125 P(Day1-Rainy)*0.625} *0.25;

P(Day2-Rainy)= max{ P(Day1-Sunny)*0.125 P(Day1-Cloudy)*0.625 P(Day1-Rainy)*0.375} *0.35;

Choosemax{ P(Day2-Sunny) P(Day2-Cloudy) P(Day2-Rainy)} 得到P(Day2-Cloudy)最大，得出第2天Cloudy的概率最大。

故{Sunny Cloudy}是前两天最大可能的天气序列。

（3）Day3的天气又取决于Day2的天气状况，同时也受Day3观察的海藻情况影响。

P(Day3-Sunny)= max{ P(Day2-Sunny)*0.5 P(Day2-Cloudy)*0.25 P(Day2-Rainy)*0.25} *0.05;

P(Day3-Cloudy)= max{ P(Day2-Sunny)*0.375 P(Day2-Cloudy)*0.125 P(Day2-Rainy)*0.625} *0.25;

P(Day3-Rainy)= max{ P(Day2-Sunny)*0.125 P(Day2-Cloudy)*0.625 P(Day2-Rainy)*0.375} *0. 05;

Choosemax{ P(Day3-Sunny) P(Day3-Cloudy) P(Day3-Rainy)} 得到P(Day3-Rainy)最大，得出第3天Rainy的概率最大。故{Sunny Cloudy Rainy}是这三天最可能的天气序列。

5、流程图

6、Python实现代码

输出结果如下：

[{'sunny': 0.378} {'cloudy': 0.0354375} {'rainy': 0.01107421875}]

总结

其实维特比(Viterbi)算法跟向前(Forward)算法很相似(向前(Forward)算法也是一种求解最短路径的算法)，求解过程基本相同，维特比(Viterbi)算法与向前(Forward)算法最大的区别是将前一个时间点路径求和(∑)改成求最大值(max)。