问题

这个问题还带有一点条件概率，混入了马尔可夫链，最后要选择的是最有可能的句子。输入条件有

• 词典m，是所有可能的输入词语，大小为|m|。
• 词典中的每个词出现在句首的概率B。
• 实数矩阵T，其中T[i,j]表示m[i]出现在m[j]之前的概率；
• 实数矩阵M，其中M[i,j]表示m[i]被误识别成m[j]的概率；
• 问题：OCR识别出来的n个词语的句子q。
  要求输出实际可能的句子。

分析

拿到一个输入q，假设最后生成的结果为p。那么它为p的概率由p句子出现的概率及每一个被识别为的概率。

-理论告警- 所谓朴素贝叶斯定理

这公式是说如果识别出q那么原文是p的概率。我们的问题就是要使得最大化，由于P(q)与p无关，是一个定值（拿B和T一阵地猛乘就得出），所以我们定义，求使它最大的q就是我们要的答案。

求解

先来看公式，后面再来递推最大化

如果将B也融入到T中，即从无到第一个字的概率，可以将公式范化成

把f(q)分解成一个一个单独的词，得到每一部分的几率值为：

PS：按照通用的做法，不会直接算乘法，而是会先取个对数，将乘法转换成加法，这样就比较容易计算。

递推公式

子问题最优解，就是在已经先到i位置的情况下，剩下的概率最大值，由于i位置会影响到后面的几率，所以

那么由此得到递推公式：

这样动态规划中用作缓存的，就是一个大的矩阵，还在可以接受的范围之内。