给定一个状态集 S={s1,s2,s3,...,s|s|} ，一个由时间产生的观察向量 z⃗ ∈ST 。比如，一个天气系统的状态有 S={sun,cloud,rain} ， |S|=3 ，观察 |T|=5 天的天气状态为 z⃗ ={z1=ssun,z2=scloud,z3=scloud,z4=srain,z5=scloud} 。
如果没有任何假设，在t时刻的状态 sj 将会是状态集中的任意值。因此做出以下两个假设：
LIMITED HORIZON ASSUMPTION： P(zt|zt−1,zt−2,...,z1)=P(zt|zt−1) 意思是在t时的状态的可能性仅取决于t-1时的状态。
STATIONARY PROCESS ASSUMPTION： P(zt|zt−1=P(z2|z1);t∈2...T 意思是状态传递的条件概率不会随时间改变。
为了方便，假设一个初始状态和初始观测点 z0=s0 ， s0 代表在0时刻的初始概率分布。因此可以定义转移矩阵 A ，Aij定义了在任意时刻t，从状态i变换到状态j时的概率。
比如上面那个天气系统的转换矩阵为：
A= s0ssunscloudsrains00000ssun.33.8.2.1scloud.33.1.6.2srain.33.1.2.7对于一个特定的状态序列 z⃗ ，其概率为：
P（z⃗ )=∏t=1TAzt−1zt 比如，由上面那个转移矩阵 A ，可以得到：P(z1=ssun,z2=scloud,z3=srain,z4=srain,z5=scloud)=P(ssun|s0)P(scloud|ssun)P(srain|scloud)P(srain|srain)P(scloud|srain)=.33×.1×.2×.7×.2由极大似然法+拉格朗日乘子法可以推导出：
Aij=∑Tt=11{zt−1=siandzt=sj}∑Tt=11{zt−1=si}当我们不能观察到一系列状态，而只能观察到这一系列状态的一些可能的函数，可能就用到HMM了。
一个形象的例子是由夏天里每天吃的冰淇淋数来推断每天的天气。我们并没有观察到实际的状态序列（每天的天气），可我们能观察到由实际状态序列所产生的结果（每天吃的冰淇淋数）。
用数学语言来表达：在之前的马尔科夫模型中，我们有一个状态集 S={s1,s2,s3,...,s|s|} ，一个由时间产生的观察向量 z={z1,z2,...zT},zt∈S ，但在此情况下 z⃗ 与 S 是未知的；而我们已知的是与其相关的状态集V={v1,v2,v3,...,v|v|}，和观察输出向量 x={x1,x2,...xT},xt∈V 。 从状态i转换到状态j依旧定义为转移矩阵 Aij 。 我们将已知的观察向量 v⃗ 的概率视作隐含状态的函数，做出OUTPUT INDEPENDENCE ASSUMPTION并定义 P(xt=vk|zt=sj)=P(xt=vk|x1,...,xT,z1,...,zT)=Bjk ，矩阵 B 的意义是，在对应时刻t，隐状态为sj时生成输出 vk 的概率。
比如在上面的冰淇凌例子中，我们可以得到一个观察输出向量（每天吃的冰淇淋数） x⃗ ={x1=v3,x2=v2,x3=v1,x4=v2} ，以及一个已知的状态集（冰淇淋数量） V={v1=1,v2=2,v3=3}
在HMM中， z⃗ 是由马尔科夫模型生成，其转移矩阵为 A ，并且为时间长度的序列。在每个时刻t，我们选择一个xt作为状态 zt 的一个函数输出，因此，在计算其概率时，要把每个可能产生 z⃗ 的 x⃗ 都加起来：
P(x⃗ ;A,B)=P(x⃗ )=∑z⃗ P(x⃗ ,z⃗ ;A,B)=...=∑z⃗ (∏t=1T(Bztxt)∏t=1T(Azt−1zt)) 这个式子优点是简单，但缺点是要把每个可能的 z⃗ 都加起来。因为 zt 有 |S| 种可能的取值，导致在每个时刻计算的复杂度为 O(|S|T) 。 因此提出了一个叫GORWARD PROCEDURE的DP算法来削减时间复杂度。这个算法首先定义了 αi(t)=P(x1,x2,...,xt,zt=si;A,B) ，表示在时刻 t ，状态为si时，关于所有观察的总概率。因此 P(x⃗ ;A,B)=∑|S|i=1αi(T) 。Forward Procedure算法伪代码： 1. Base case: αi(0)=A0i,i=1...|S| 2. Recursion: αj(t)=∑|S|i=1αi(t−1)AijBjxi,j=1...|S|,t=1...T
此算法在每个时刻计算概率 P(x⃗ ) 的复杂度仅为 O(|S|) 。 BACKWORD RECEDURE算法用来计算相似的概率：
βi(t)=P(xT,xT−1,...,xt+1,zt=si;A,B)已知一个观察输出序列 x⃗ ∈VT ，则隐含序列 z⃗ ∈ST 最可能的取值怎么计算？ 用数学语言表达，我们要求：
argMaxz⃗ P(z⃗ |x⃗ ;A,B)=argMaxz⃗ P(x⃗ ,z⃗ ;A,B)∑z⃗ P(x⃗ ,z⃗ ;A,B)=argMaxz⃗ P(x⃗ ,z⃗ ;A,B) 。 依然，遍历一个可能序列的时间复杂度就到达了 O(|S|T) 。HMM的EM朴素解法伪代码： Repeat until convergence { (E-Step) For every possible labeling z⃗ ∈ST , set
Q(z⃗ ):=p(z⃗ |x⃗ ;A,B) (M-Step) Set A,B:=argMaxA,B∑z⃗ Q(z⃗ )logP(x⃗ ,z⃗ ;A,B)Q(z⃗ ) s.t.∑j=1|S|Aij=1,i=1...|S|;Aij>=0,i,j=1...|S| s.t.∑k=1|V|Bik=1,i=1...|S|;Bik>=0,i=1...|S|,k=1...|K| }继续还是由拉格朗日乘子法，可以得到以下算法：
Forward-Backward algorithm for HMM parameter learning 伪代码:
Initialization: Set A and B as random valid probability matrices
where Ai0=0 and B0k=0 for i = 1..|S| and k = 1..|V|.
Repeat until convergence{
(E-step) Run the Forward and Backward algorithm to compute αi and βj for i = 1..|S|.
Then set: γt(i,j):=αi(t)AijBjxtβj(t+1) (M-step)Re-estimate the maximum like lihood parameters as: Aij:=∑Tt=1γt(i,j)∑|S|j=1∑Tt=1γt(i,j) Bjk:=∑|S|i=1∑Tt=11{xt=vk}γt(i,j)∑|S|i=1∑Tt=1γt(i,j) }
资料以及详细证明过程：Hidden Markov Models
