马尔科夫模型3

2017-07-20

前向算法（Forward Algorithm）

计算观察序列的概率（Finding the probability of an observed sequence）

1.计算t=1时的局部概率α‘S

按如下公式计算t=1的局部概率：

$$
\alpha_{t}{(j)} = Pr(观察状态|隐藏状态) ∗ Pr(t时刻所有指向j状态的路径)
$$

t=1的时，没有任何指向当前状态的路径。所以t=1时位于当前状态的概率是初始概率。

$$
\alpha_{1}{(j)} = \pi(j) ∗ b_{jk_{1}}
$$

@ pram k[]: 表示所获得的观察状态的序列，那么k1就是第一个观察状态的结果，因为第一个状态没有前面的依赖关系，我们总是将其先做好处理。
@ pram 𝛑[]: 表示初始到达隐藏状态的概率序列
@ pram α[][]: 其中的t表示在t时刻指向j这个隐藏状态的概率
@ pram b[][]: 表示从隐藏状态指向观察状态的概率矩阵

2.计算t>1时的局部概率

我们可以假设（递归地），乘号左边项“Pr( 观察状态 | 隐藏状态j )”已经有了，现在考虑其右边项“Pr(t时刻所有指向j状态的路径）”。
为了计算到达某个状态的所有路径的概率，我们可以计算到达此状态的每条路径的概率并对他们求和。否则用穷举的思想是指数级别上升的。

计算α所需要的路径数目随着观察序列的增加而指数级递增，但是t-1时刻!α’s给出了所有到达此状态的前一路径概率，因此，我们可以通过t-1时刻的局部概率定义t时刻的α’s，即:

$$
\alpha_{t+1}{(j)} = b_{jk_{t+1}} \sum_{i=1}^{n} {\alpha_{t}(i) \alpha_{ij}}
$$

对于这一步，可以结合着前一篇文章马尔科夫模型2后面对前向算法的简单例子来看。

3.降低计算复杂度

假设观察序列O的长度为T以及一个含有n个隐藏状态的隐马尔科夫模型 I = (pi,A,B)。

穷举搜索的时间复杂度是2TN^T,前向算法的时间复杂度是T*N^2。

根据上述可以把前向算法的公式进行简化（但实际复杂度是没有改变的）

$$
\sum_{X}{\pi(i_{1})b_{i_{1}k_{1}}}\prod_{j=2}^{T}{\alpha_{i_{j-1}i_j}b_{i_{j}k_j}}
$$

4.前向算法代码的简单实现

import java.util.Vector;
/**
 * Created by ganjun on 2017/7/22.
 */
/*
马尔科夫模型前向算法实现
1、隐藏状态 (天气)：Sunny，Cloudy，Rainy；
　　2、观察状态（海藻湿度）：Dry，Dryish，Damp，Soggy；
　　3、初始状态概率： Sunny（0.63）， Cloudy（0.17）， Rainy（0.20）；
　　4、状态转移矩阵：
　　　　　　　　　　　　 weather today
　　　　　　　　　　　　 Sunny Cloudy Rainy
　　　 　weather　Sunny 0.500 0.375 0.125
　　　　yesterday Cloudy 0.250 0.125 0.625
　　　　　　　　　 Rainy 　0.250 0.375 0.375
　　5、混淆矩阵：
　　　　　　　　　　　　observed states
　　　　　　　　　　　Dry Dryish Damp Soggy
　　　　　　　　　Sunny 0.60 0.20 0.15 0.05
　　　　hidden　 Cloudy 0.25 0.25 0.25 0.25
　　　　states　　Rainy 0.05 0.10 0.35 0.50
 */
public class Forward {
    public static final String [] hideStates = {"Sunny" , "Cloudy" , "Rainy"};
    public static final String [] observations = {"Dry" , "Dryish" , "Damp" ,  "Soggy"};
    public static final double startProbability[] = {0.63, 0.17 , 0.20};
    public static final double [][] emission_probability =
            {
                    {0.60 , 0.20 , 0.15 , 0.05} ,
                    {0.25 , 0.25 , 0.25 , 0.25} ,
                    {0.05 , 0.10 , 0.35 , 0.50}
            };
    public static final double [][] transition_probability =
            {
                    {0.500 , 0.375 , 0.125} ,
                    {0.250 , 0.125 , 0.625} ,
                    {0.250 , 0.375 , 0.375}
            };
    public double calResultPro(Vector<Integer> observeStates ,
                               String [] hideStates ,
                               String [] observations ,
                               double [] startProbability ,
                               double [][] transition_probability ,
                               double [][] emission_probability
                               ){
        double res = 0;
        double pro [][] = new double [observeStates.size()][hideStates.length];
        //第一步没有之前的依赖,借助于startPro,单独进行计算
        for(int i=0 ; i<hideStates.length ; i++){
            pro[0][i] = startProbability[i] * emission_probability[i][observeStates.get(0)];
        }
        //接下来的observeStates.size()-1个观察状态都是借助前一次的概率来进行判断的
        for(int i=1 ; i<observeStates.size() ; i++){
            //当前这次选中的j状态，它从前一次多种可能的k状态转移过来的
            for(int j=0 ; j<hideStates.length ; j++){
                pro[i][j] = 0;
                for(int k=0  ;k<hideStates.length ; k++){
                    pro[i][j] += pro[i-1][k] * transition_probability[k][j]
                            * emission_probability[j][observeStates.get(i)];
                }
            }
        }
        //将所有到达最结尾的可能状态都相加求和
        for(int i=0 ; i<hideStates.length ; i++){
            res += pro[observeStates.size()-1][i];
        }
        return res;
    }
    public static void main(String [] args){
        Forward sol = new Forward();
        Vector<Integer> vec = new Vector<Integer>();
        //这里以观察状态为Dry , Damp , Soggy来计算产生这个观察序列的概率
        vec.add(0); vec.add(2); vec.add(3);
        System.out.println(sol.calResultPro(vec , hideStates , observations ,
                startProbability , transition_probability , emission_probability));
    }
}

5.总结

前向算法的目标是计算给定隐马尔科夫模型HMM下的观察序列的概率—Pr(observations | ℷ)。

我们首先通过计算局部概率降低计算整个概率的复杂度，局部概率表示的是t时刻到达某个状态s的概率。

t=1时候，可以利用初始概率（来自于P向量）和观察概率Pr(observation | state)(来自于混淆矩阵)计算局部概率；而t>1时的局部概率可以利用t-1时的局部概率进行计算。

因此，这个问题是递归定义的，观察序列的概率就是通过依次计算t=1,2,…,T时的局部概率，并且对于t=T时所有局部概率。