详细分析Baum–Welch algorithm

臭名昭著的犯罪团伙落脚在一个小镇上,负隅顽抗着。此犯罪团伙的反侦查意识极强,武警部长再也坐不下去了,每让这个犯罪团伙多存在一天,就多一份对公民的威胁。于是你以特派专家的身份,被武警部长邀请去计划搜捕行动。

讨论

武警部长告诉你,犯罪团伙的每天的防卫状态,只可能是“防卫严密”或“防卫松懈”两种状态一种,而且今天的防卫状态只和昨天的防卫状态相关。即如果今天“防卫严密”的话,明天有一定的概率“防卫松懈”。

武警部长对你说:”组织抓捕,当然是要在防卫松懈时去抓捕了,但问题在于,并不容易知道他们究竟什么时候会防卫松懈。也不知道今天防卫严密后,明天防卫松懈的概率。如果知道了将容易很多”,说完,拿出来一份文件。

作为特派专家,你似乎意识到什么,于是询问部长:“你们虽然不能直接知道他们的防卫状态,但你们每天都会密切观察他们的举动,有什么别的信息呢?”

武警部长答道:“这倒是有一些。比如我已经排了专人去监视那个犯罪团体的活跃状况。大致可以分为“活跃”和“不活跃”。活跃的时候人来人往,车流量很大,不活跃则几乎没人进出他们的老巢。我们发现他们的活跃状态和防卫状态有一定关系,但又没法确定。”

你狡黠地一笑:“这就好办了。”

分析

你找来一张纸,写下了如下的关系

  • 我们知道犯罪团伙每天的活跃的状态,即可见层
  • 我们知道犯罪团伙每天的防卫状态一共有哪些
  • 我们不知道今天的防卫状态与昨天的防卫状态关系是怎样的。即不知道隐藏层的转移关系
  • 我们不知道每天的防卫状态是怎样的,即不知道隐藏层
  • 我们也不知道每天的防卫状态,与活跃状态之间的关系,即由隐藏层某个元素可以推出可见层某个元素的概率,即表现(emission)概率。

你说:“现在不知道,并不代表以后也不可能知道,所以我们现在要大胆尝试。”

武警部长说:“说人话。”

你道:“好啦,就是不知道的猜一遍。虽然猜的并不准确,但有办法让它逐渐符合实际。”

假设昨天的防卫状态与今天的防卫状态的关系是,即表格A

假设的隐藏层状态状态转移 今天 防卫 严密 今天 防卫 松懈
昨天 防卫 严密 0.5 0.5
昨天 防卫 松懈 0.3 0.7

或者是

设某一天为初始状态,假设那天犯罪团体防卫严密的概率是0.2,防卫松懈的概率是0.8即表格π

初始状态概率
防卫 严密0.2
防卫 松懈0.8

或者

再假设防卫的状态到活跃状态的表现关系,比如今天 防卫 严密,则活跃的概率是0.3。得到表格B

假设的表现关系活跃不活跃
防卫 严密0.30.7
防卫 松懈0.80.2

至此,准备工作已经完成了。然后你把这三张表放在一起,并装入一个文件袋θ里

武警部长道:“我还是看不出你接下来会怎么做。”

你不慌不忙地起身热了两壶茶,又坐下对部长说道:“部长,最近观察到的那犯罪团伙的活跃状态是怎么样的?”

部长又拿出一份报告,这是上个星期对那个犯罪团伙的观察情况。

于是你说:“这是真实观察到的结果,我们就叫他“结果X”好了。不同的犯罪团伙的防卫状态和转移概率以及表现矩阵,也就是有不同的表格A,B,π,也就是不同的文件档案θ。不同的文件档案θ,代表着可能观测到的不同结果。”

“我们现在确实不知道文件档案里的内容和数据应该是什么。但肯定有某个我们期待得到的文件档案θ,记录了那犯罪团伙的准确信息,并且会导致“结果X”的出现概率最大,让我们有很大机会碰上“结果X”。这样就符合了我们所观察的实际情况。毕竟在我们看来,我们确实观察到的“结果X””

部长若有所思,说“嗯,这个方法太精彩了。只是我以前好像在哪儿见到过类似的东西?”

你道:“部长应该了解过概率论,这个思想和似然(likelihood)是一样的,都是不知道概率,只知道结果,而要从结果反推出概率。”

部长把茶给你和他斟上,接着问道:“那么接下来应该怎么办呢?”

用两天的数据更新表格A

你道:“例如想更新表格A上的内容,比如知第一天为“防卫严密”到第二天为“ 防卫 松懈”的转移概率,并且要符合实际观察到的情况,即第一天活跃,第二天活跃。我们来计算这种情况的出现概率。

你拿出文件袋θ,计算到:

  1. 根据表格π,第一天为“防卫严密”的概率为0.2
  2. 根据表格B,第一天为“ 防卫严密”,则第一天为“活跃”的概率为0.3
  3. 根据表格A,第一天为“ 防卫 严密”,第二天为“ 防卫松懈”的概率为0.5
  4. 根据表格B,第二天为“防卫松懈”,第二天为“ 活跃”的概率为0.8
  5. 相乘得到新的,第一天为“ 活跃”并且第二天为“ 活跃”这种情况的概率是0.024

根据原猜测结果,计算符合实际(第一天活跃,第二天活跃)的转移概率,即计算

同样可得

部长道:“按照我们观察到的真实结果X,和猜测的文件档案θ,对于这四种情况,显然第四种情况,即第一天“防卫松懈“第二天也”防卫松懈”的概率最高,最有可能发生啊。”

你道:“对,但那并不代表另外三种情况不可能发生。若是让第一种情况除以第四种情况,就得到了从第一天“防卫严密”到第二天“防卫松懈”的新转移概率,

0.0240/0.3584 = 0.6696

。在归一化后,要比我们之前的推测更加符合我们的观察。

新的隐藏层状态转移
(未归一化)
今天 防卫 严密 今天 防卫 松懈
昨天 防卫 严密 0.17850.0446
昨天 防卫 松懈 0.1607 1

归一化后,就是根据我们所观察到的结果X的一部分,即第一天活跃,第二天活跃所计算出的,比之前推测更加靠谱的表格A。也就是说,在更新表格A后,文件档案θ所代表的的犯罪团伙的信息,会让“第一天活跃第二天活跃”这种情况出现的概率更加增大。

新的隐藏层状态转移
(归一化后)
今天 防卫 严密 今天 防卫 松懈
昨天 防卫 严密 0.80000.2000
昨天 防卫 松懈 0.1385 0.8615

根据最有可能的隐藏层,计算隐藏层元素间转移概率比例就是计算下面的式子:

更新表格A的过程,就是计算下面的式子,即隐藏层状态转移关系

部长拿起纸笔验算了一番:

“神了”,部长非常惊喜,“相比于我们之前的猜测,更新后的猜测更加符合实际,也就是说那些犯罪团伙的信息更加符合更新后的。”

你非常自豪,说道:“这还只是仅使用了两天的数据,如果把7天观测数据全部用上又如何呢?

完整的一遍更新流程

首先仍然是更新表格A

活跃状态最可能的防卫状态概率
第一二天活跃-活跃松懈-松懈0.3584
第二三天 活跃-活跃松懈-松懈0.3584
第三四天 活跃-不活跃松懈-严密0.1344
第四五天 不活跃-不活跃严密-严密0.0490
第五六天 不活跃-不活跃松懈-松懈0.0896
第六七天 活跃-活跃松懈-松懈0.3584
总计1.3482

然后根据原来的表格更新防卫状态的转换概率,下面是从“防卫严密”到“防卫松懈”的计算

活跃状态 恰好是“防卫严密”到“防卫松懈” 概率
第一二天活跃-活跃0.024
第二三天 活跃-活跃 0.024
第三四天 活跃-不活跃 0.006
第四五天 不活跃-不活跃0.014
第五六天 不活跃-活跃0.056
第六七天 活跃-活跃 0.024
总计0.148
  • 新的 从“防卫严密”到“防卫松懈”的转移概率0.148/1.3482 = 0.1098。
  • 新的 从“防卫严密”到“防卫严密”的转移概率0.118/1.3482 = 0.0875。
  • 新的 从“防卫松懈”到“防卫严密”的转移概率0.3552/1.3482 = 0.2612。
  • 新的 从“防卫松懈”到“防卫松懈”的转移概率1.2768/1.3482 = 0.9470。

归一化后得到新的表格A

新的隐藏层状态转移 今天 防卫 严密 今天 防卫 松懈
昨天 防卫 严密 0.44350.5565
昨天 防卫 松懈 0.2162 0.7838

接下来更新,表格B,首先更新由“防卫严密”表现出“不活跃”的概率

假设不活跃是由于严密
即防卫状态转移
出现左侧
防卫情况的概率
第三四天活跃-不活跃松懈-严密 0.1344
第四五天不活跃-不活跃严密-严密0.0490
第五六天不活跃-活跃严密-松懈0.0560
总计0.2394
  • 新的 从“防卫严密”到“活跃”的表现概率0.177/1.2992 = 0.1098。
  • 新的 从“防卫严密”到“不活跃”的表现概率0.2394/0.2730 = 0.8749。
  • 新的 从“防卫松懈”到“活跃”的表现概率1.2240/1.2992 = 0.9421。
  • 新的 从“防卫松懈”到“不活跃”的表现概率0.376/0.2730 = 0.1370。

归一化后得到更新后的表格B:

活跃 不活跃
防卫 严密 0.11150.8885
防卫 松懈 0.8130 0.1270

同理,更新表格B即更新隐藏层到可见层的表现矩阵,即

其中

即,假设“不活跃”这个状态全部是由“防卫严密”导致的,那么我们在计算时只需要考虑那些包含着“不活跃”的两天连续观察,例如第三四天。而不包含的全部去掉,例如第一二天。

活跃状态最可能
初始状态
最可能初
始状态概率
初始状态
为“严密”的概率
初始状态
为“松懈”的概率
第一二天活跃-活跃松懈0.41600.03300.4160
第二三天 活跃-活跃松懈0.41600.03300.4160
第三四天 活跃-不活跃松懈0.22400.02700.2240
第四五天 不活跃-不活跃严密0.06300.06300.0560
第五六天 不活跃-活跃松懈0.10400.07700.1040
第六七天 活跃-活跃松懈0.41600.03300.4160
总计
1.6930
总计0.2600总计1.6860

归一化后得:

更新后的初始状态概率
防卫 严密0.1336
防卫 松懈0.8664

更新表格π,即更新第一天隐藏层的初始状态,即

我们更新完了第一波表格A,B,π,但这还不够,我们可能仍然有更合适的文件档案θ等待我们去计算。于是我们就以这一次更新后的表格,作为下一次的起始表格,再更新一遍。如此循环下去,直到表格中的数据稳定下来,就得到了我们想要得到的文件档案θ,这样的文件档案能够保证出现“结果X”的概率最大。

表格

为了方便各位计算,我把根据最开始所猜测的θ对应的转换表格贴出,对应了所有可能的情况。表中数字加起来即为总概率1。第一行第一列意思为,如果第一天防守严密,第二天防守严密,那么第一天活跃且第二天活跃的概率

活跃-活跃活跃-不活跃不活跃-活跃不活跃-不活跃
严密-严密0.00900.02100.02100.0490
严密-松懈0.02400.00600.05600.0140
松懈-严密0.05760.13440.01440.0336
松懈-松懈0.35840.08960.08960.0336

结语

武警部长依据你的方法,召集手下人员,很快就得出了那犯罪团伙的防卫状况以及其他信息。在几天后的精密策划的抓捕行动中,犯罪团伙成员悉数落网。大家听了你的故事后,都对你很是敬佩,武警部长更是高兴,对你连声称赞。几天后一个晚上,武警部长悄悄找到你,对你说:“Baum–Welch algorithm这么神奇。但,你还有什么别的预测算法,可以帮我算算我的另一半在哪里吗?”

你意味深长地一笑,没有说话。

参考:

  1. https://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm

Leave a Reply