趣说Viterbi 维特比算法

缘由

今天天朗气清,惠风和畅,我与一群认识不认识的人出去郊外好好玩了一天,我也把家里配置很不错的专业照相机带去,记录了我们在一起抓小鱼,野炊,登山顶的美好的时光,并分享给大家。我们一直玩到傍晚,才启程回去,我正在欣赏我拍的照片的时候,突然有个异性对我说:”你的照片拍的不错啊。明天有空吗,我们一起去吃个饭吧?”

我听到这句话后,立马意识到这句话绝对没看上去那么简单,肯定还有深层次的意思。于是我的脑袋立马就以每小时80迈的速度飞速旋转着:

首先,Ta说了这么一句话,可以分为三个小句(隐马尔可夫模型中的可见层):

至于深层次的意思(隐马尔可夫模型中的隐藏层),比如“你的照片拍得不错”,可能是说我用来拍照的照相机很专业,也可能是说我拍照技术很高超,但也有可能是在反讽我,说我拍得太low。总结起来,如下图所示

虽然每个小句都有三种可能的深层意思,但真正的深层意思只可能是一个。Ta说我照片拍得好,究竟是列出的三种深层意思中的哪一个呢?Ta的完整深层意思究竟是什么呢?是想反讽我,让我明天凌晨教Ta拍照,发现我的照相机夜视功能不行好好嘲笑我?还是看上我的照相机,明天下午约我出来,却顺手牵羊拿走我的照相机,好弥补自己不足的生活费呢?就算不能100%确定,也要确定其中概率最大的是哪个?

我意识到,如果这么直接猜很难猜到,如果还有一些信息可以帮助我就好了。很快,我就想到了一些东西。

准备

我要先假设,Ta的第二个小句的深层意思,只与第一个小句的深层意思有关,在思考号第一个小句的深层意思后,才开始思考第二个小句的深层意思。第三个小句的深层意思,只与第二个小句的深层意思有关。也就是,隐藏层某一个状态只与前一个状态有关,这样才能用马尔可夫状态转移求解。

我首先要考虑的就是,从深层意思到说出来的概率(即从隐藏层到表现层的表现(emission)概率)

也就是,如果Ta的深层意思是我的照相机非常专业,Ta会有多大的概率说出“你的照片拍得不错呢?”根据我以往拍别人的经验,这个概率大概是“0.3”。或者Ta第二个小句的深层意思是“明天凌晨有空吗?”,Ta会有多大概率说出“明天有空吗”?诶,Ta怎么知道我的照相机还有夜视功能?Ta的观察力太厉害啊!同理,其他的也能总结出来。

其次,我要考虑的是,每个小句的每个深层意思,可以引起下一个小句某个深层意思的概率(即隐藏层元素之间的状态转移矩阵)是多少。

例如,Ta如果是想到“我的拍照技术非常高超”,Ta有多大的概率会在下一个小句想到“你明天下午有空吗?”,又有多大的概率会在下一步想到:“你明天凌晨有空吗?”。不过说实话,应该没人会在凌晨约别人出来,但下午我又要和朋友开黑,实在两难。于是我制作了两张表,分别表明不同小句不同元素间的转移概率:

最后,我需要知道的是,Ta为什么要

分析(Viterbi算法)

之前说过,我不知道Ta的完整深层意思是什么,我需要找出概率最大的,最可能的那条路径。虽然我已经计算好各种概率,如果我要把所有可能都算一遍,我要计算3+3×3+3x3x3 = 39遍,太慢了,从刚才Ta说出那句话到现在已经了0.8秒。为了更快弄清楚Ta的深层意思,我的大脑已经以超光速运转着了呢!

(图:对于不同的路径,究竟哪条概率最大,最有可能呢?并且如何计算才能让总计算次数最少?)

首先,仍然是这张图。对于第一个小句的三个深层意思,让初始概率乘上表现概率,得到这三个深层意思可能出现的概率。我们并不能立马断定究竟哪个所在的路径概率最大。所以这三个都有可能。那么这三个都暂时先留着吧。这样我们就得到了三条可能的路径。

然后计算到第二个小句的三个深层意思的转移概率。首先计算对第一个深层意思的转移概率。

路径a的总概率 = (初始状态到“专业照相机“的概率” 乘上”“专业照相机”到“早上有空”的转移概率 乘上 “早上有空”到“明天有空吗?”的表现概率) = 0.12*0.2*0.4 = 0.0096。

同理,路径b的的总概率 = 0.24*0.5*0.4 = 0.0480。路径c的总概率 = 0.02*0.6*0.4 = 0.0060。

然后,viterbi算法的核心来了,如果完整的深层思想里,包含“明天早上你有空吗”这一项,那么这一项究竟应该由路径a,路径b还是路径c产生?答案很明显,由于我们之前说过要找概率最大的路径,所以也应该选择目前概率最大的一项,即路径b。虽然在暴力方法里,我们之后还是需要计算路径a和路径c,但现在在viterbi算法里,路径a和路径c再也不可能出现了。

同理,对于第二个小句的第二个深层意思,计算得到路径d概率最大为0.0288

对于第二个小句的第三个深层意思,计算得到路径h概率最大为0.0144

于是我们又得到了三条可能的路径,与之前一样,无法确定哪条路径最有可能,于是在计算第二个小句的深层意思到第三个小句的深层意思,把把这三天路径代入计算。这样就大大减少了计算次数。

结果

经过我缜密的分析,我最终得出“拍照技术非常高超”-“明天早上你有空吗”-“Ta想向我拜师学习拍照技术”这条路径最高,概率为0.014400。这也是根据我的猜测,Ta此时内心里正在想的。

之前说过,按照暴力方法,需要计算3+3×3+3x3x3 = 39次,而此时,我只计算了3 + 3×3 + 3×3 = 21次。这还只是小规模数据,数据规模大起来后,节省的时间将更多。

总而言之,在Ta说话后的1.6秒内,我猜测到了Ta的真实意图。我想到,我的拍照技术确实很高这一点没错,但明天早上我不一定起得来, 如果教别人我可能时间也不够。于是我一边看着自己手上照相机,一边认真说道:“照相不像看上去那么简单,你看这光圈,如果我不这么设置的话,阴影就会覆盖住这一块区域…..”

等我抬起头,Ta已经不见了。

【此处欠一张应景的搞笑图,谁知道的,请私信我哈哈哈】

Leave a Reply