马尔可夫链
一个系统有N个状态 S1，S2，···，Sn，随着时间推移，系统从某一状态转移到另一状态，设qt为时间t的状态，系统在时间t处于状态Sj 的概率取决于其在时间 1 ，2，···，t-1 的状态，该概率为：
如果系统在t时间的状态只与其在时间 t -1的状态相关，则该系统构成一个离散的一阶马尔可夫链(马尔可夫过程)：
马尔可夫模型
如果只考虑独立于时间t的随机过程：
其中状态转移概率 aij 必须满足 aij>=0 , 且
，则该随机过程称为马尔可夫模型。
假定一段时间的气象可由一个三状态的马尔可夫模型M描述，S1：雨，S2：多云，S3：晴，状态转移概率矩阵为：
如果第一天为晴天，根据这一模型，在今后七天中天气为O=“晴晴雨雨晴云晴”的概率为：
隐马尔可夫模型
对于一个随机事件，有一观察值序列： O=O1,O2,…OT
该事件隐含着一个状态序列： Q = q1,q2,…qT。
假设：马尔可夫性假设（状态构成一阶马尔可夫链）
P(qi|qi-…q1) = P(qi|qi-)
假设：不动性假设（状态与具体时间无关）
P(qi+|qi) = P(qj+|qj)，对任意i，j成立
假设：输出独立性假设（输出仅与当前状态有关）
p(O1,...,OT | q1,...,qT) = Πp(Ot | qt)
HMM定义
一个隐马尔可夫模型 (HMM) 是由一个五元组描述的：
λ ＝（ N，M ，A，B， π ）
其中：
N = {q1,…qN}：状态的有限集合
M = {v1,…,vM}：观察值的有限集合
A = {aij}，aij = P(qt = Sj |qt-1 = Si)：状态转移概率矩阵
B = {bjk}， bjk = P(Ot = vk | qt = Sj)：观察值概率分布矩阵
π = {πi}，πi = P(q1 = Si)：初始状态概率分布
观察状态是已知的，隐状态是未知的。
三个基本问题
令 λ = {π，A，B} 为给定HMM的参数，
令 O = O1,…,OT 为观察值序列，则有关于
隐马尔可夫模型（HMM）的三个基本问题：
1.评估问题：对于给定模型，求某个观察值序列的概率P(O|λ) ；
• 计算骰子点数序列的确由“作弊”模型生成的可能性
2.解码问题：对于给定模型和观察值序列，求可能性最大的状态序列maxQ{P(Q|O,λ)}；
• 在骰子点数序列中, 判断哪些点数是用骰子B掷出的
3.学习问题：对于给定的一个观察值序列O，调整参数λ，使得观察值出现的概率P(O|λ)最大。
• 如何从大量的点数序列样本中学习得出“作弊模型”的参数
三个基本问题解法
评估问题：前向算法
定义前向变量
采用动态规划算法，复杂度O(N2T)
解码问题：韦特比（Viterbi）算法
采用动态规划算法，复杂度O(N2T)
学习问题：向前向后算法
EM算法的一个特例，带隐变量的最大似然估计
HMM将两个序列相联系起来：
- 由离散隐状态组成的状态序列(路径)，Q = (q1,…,qT), 每个qt∈S均是一个状态，由初始状态概率及状态转移概率(π, A)所决定
- 由明字符组成的观察序列，O = (o1,…,oT), 每个ot∈V均为一个离散明字符，由状态序列及各状态的明字符生成概率(Q,B)所决定。
package org.digdata.hmm;
/**
* HMM对象类
*/
public class HMM implements Cloneable {
/**
* 隐藏状态数目
*/
public int N;
/**
* 观察状态数目
*/
public int M;
/**
* 状态转移矩阵 一个隐状态到另一个隐状态的概率
*/
public double[][] A;
/**
* 混淆矩阵 一个隐状态到观察状态的概率
*/
public double[][] B;
/**
* 初始向量
*/
public double[] pi;
@Override
public Object clone() {
HMM hmm = null;
try {
hmm = (HMM) super.clone();
hmm.A = A.clone();
for (int i = ; i < A.length; i++) {
hmm.A[i] = A[i].clone();
}
hmm.B = B.clone();
for (int i = ; i < B.length; i++) {
hmm.B[i] = B[i].clone();
}
hmm.pi = pi.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
return hmm;
}
public HMM() {
super();
}
/**
* @param n
* 隐藏状态数目
* @param m
* 观察状态数目
* @param a
* 状态转移矩阵
* @param b
* 混淆矩阵
* @param pi
* 初始向量
*/
public HMM(int n, int m, double[][] a, double[][] b, double[] pi) {
super();
N = n;
M = m;
A = a.clone();
for (int i = ; i < a.length; i++) {
A[i] = a[i].clone();
}
B = b.clone();
for (int i = ; i < b.length; i++) {
B[i] = b[i].clone();
}
this.pi = pi.clone();
}
/**
* 用于参数估计
*
* @param n
* 隐藏状态数目
* @param m
* 观察状态数目
*/
public HMM(int n, int m) {
super();
N = n;
M = m;
A = new double[N][N];
B = new double[N][M];
pi = new double[N];
}
/**
* 用于测试已知模型
*
* @param a
* 状态转移矩阵
* @param b
* 符号输出矩阵
* @param pi
* 初始向量
*/
public HMM(double[][] a, double[][] b, double[] pi) {
super();
N = a.length;
M = b[].length;
A = a.clone();
for (int i = ; i < a.length; i++) {
A[i] = a[i].clone();
}
B = b;
for (int i = ; i < b.length; i++) {
B[i] = b[i].clone();
}
this.pi = pi.clone();
}
}
HMM 实际问题：
数值计算中的防溢出处理
在前向算法、Viterbi算法以及Baum-Welch算法中，概率值的连续乘法运算很容易导致下溢现象。
解决办法：
1.前向算法中：每一个时间步的运算中都乘以一 个比例因子
2.Viterbi算法中：对概率值取对数后计算