馬爾可夫鍊
一個系統有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算法中：對機率值取對數後計算