隐马尔科夫模型（HMM）及事实上现

马尔科夫模型

马尔科夫模型是单重随机过程，是一个2元组：(S,A)。

当中S是状态集合，A是状态转移矩阵。

仅仅用状态转移来描写叙述随机过程。

马尔科夫模型的2个如果

有限历史性如果：t+l时刻系统状态的概率分布仅仅与t时刻的状态有关，与t时刻曾经的状态无关；

齐次性如果：从t时刻到t+l时刻的状态转移与t的值无关。

以天气模型为例

天气变化有3中状态S:{1(阴),2（云）,3（晴）}

图片来自网络

则状态转移矩阵A:

$A = left[ {egin{array}{*{20}{c}}{0.4}&{0.3}&{0.3}\{0.2}&{0.6}&{0.2}\{0.1}&{0.1}&{0.8}end{array}} ight]$

这样，仅仅要知道的初始状态概率向量，就能预測接下来每天的天气了。

隐马尔科夫模型

隐马尔科夫模型是双重随机过程，是一个5元组：

$lambda left( {S,V,A,B,pi } ight)$

V是输出集合。

$B = left{ {{b_j}left( k ight)} ight}$

表示在状态j时输出k的概率。

$pi$ 是初始状态概率。

用状态转移和输出概率一起来描写叙述随机过程。

以扔硬币模型为例

有个小孩手上拿着3个各不同样，也正反不均匀的硬币。他每次随机抽取1个硬币扔，扔了非常多次（比方10次），他并不告诉你他每次抽中的是哪个硬币。可是他会告诉你每次的正反结果：正正反正反正正正……

在这个问题中，我们知道观察序列（硬币的正反），可是小孩手上硬币类型的变换序列被隐藏起来了，我们不知道小孩每次拿的哪个硬币扔，因此是双重随机过程。这就隐马尔科夫过程。

这里如果模型參数已知：

A=[0.90.05 0.05;0.45 0.1 0.45;0.45 0.45 0.1];
B=[0.50.75 0.25;0.5 0.25 0.75];
Pi=[1/31/3 1/3]';

隐马尔科夫模型的3个问题

1.【概率问题】给定上述模型，观察到[正正反]的概率是多少？

O=[11 2];

2.【预測问题】给定上述模型，假设观察到上述结果，最可能的硬币转换序列（状态转换序列）是什么？

3.【学习问题】不告诉你模型參数，怎样依据观察序列得到它们？

【概率问题】

1.向前算法

向前变量：给定模型，在时刻t，状态为i，且之前的观察序列例如以下的概率。

${alpha _t}left( t ight) = Pleft( {{o_1}{o_2}{o_3} ldots {o_t},{q_t} = ileft| lambda ight.} ight)$

显然有

$egin{array}{l}egin{array}{*{20}{c}}{{alpha _1}left( i ight) = {pi _i}{b_i}left( {{o_i}} ight)}&{left( {1 le i le N} ight)}end{array}\egin{array}{*{20}{c}}{{alpha _{t + 1}}left( j ight) = left[ {sumlimits_{i = 1}^N {{alpha _t}left( i ight){a_{ij}}} } ight]{b_j}left( {{o_{t + 1}}} ight)}&{1 le t le T - 1,1 le j le N}end{array}end{array}$

Alpha=zeros(3,N);
Beta=zeros(3,N);
Lambda=zeros(3,N);
 
Alpha(:,1)=B(O(1),:)'.*Pi;
Delta=Alpha;
fori=2:N
    Alpha(:,i)=A'*Alpha(:,i-1).*B(O(i),:)';
end
Q1_1=sum(Alpha(:,N));

输出

Alpha=
0.166666666666667      0.150000000000000      0.0867187500000000
0.250000000000000      0.0531250000000000    0.00683593750000000
0.0833333333333333    0.0322916666666667    0.0259765625000000
 
Q1_1=0.119531250000000

2.向后算法

向后变量：给定模型，在时刻t，状态为i，且之后的观察序列例如以下的概率。

${eta _t}left( i ight) = Pleft( {{o_{t + 1}}{o_{t + 2}} ldots {o_T}left| {{q_t} = i,lambda } ight.} ight)$

显然有

$egin{array}{l}egin{array}{*{20}{c}}{{eta _T}left( i ight) = 1}&{left( {1 le i le N} ight)}end{array}\egin{array}{*{20}{c}}{{eta _t}left( i ight) = sumlimits_{j = 1}^N {{a_{ij}}{b_j}left( {{o_{t + 1}}} ight){eta _{t + 1}}left( j ight)} }&{1 le t le T - 1,1 le j le N}end{array}end{array}$

Beta(:,N)=ones(N,1);
fori=N:-1:2
   Beta(:,i-1)=bsxfun(@times,A,B(O(i),:))*Beta(:,i);
end
Q1_2=sum(Pi.*B(1,:)'.*Beta(:,1));

输出

Beta=
0.252187500000000      0.500000000000000      1
0.202968750000000      0.587500000000000      1
0.321093750000000      0.412500000000000      1
 
Q1_2=0.119531250000000

【预測问题】

Viterbi算法

Viterbi变量：给定模型，在时刻t，状态为i，观察到的最佳转换序列为的概率。

${delta _t}left( i ight) = mathop {max }limits_{{q_1},{q_2}, ldots ,{q_{t - 1}}} Pleft( {{q_1}{q_2} ldots {q_{t - 1}},{q_t} = i,{o_1}{o_2} ldots {o_t}left| lambda ight.} ight)$

显然有

$egin{array}{l}egin{array}{*{20}{c}}{{delta _1}left( i ight) = {pi _i}{b_i}left( {{o_i}} ight)}&{1 le i le N}end{array}\egin{array}{*{20}{c}}{{delta _{t + 1}}left( j ight) = left[ {max {delta _t}left( i ight){a_{ij}}} ight]{b_j}left( {{o_{t + 1}}} ight)}&{1 le i le N}end{array}end{array}$

这里须要把最佳路径记录下来

${Psi _t}left( j ight) = arg mathop {max }limits_{1 le i le N} left[ {{delta _{t - 1}}left( i ight){a_{ij}}} ight$

Q2=zeros(1,N);
fori=2:N
    Delta(:,i)=max(bsxfun(@times,A,Delta(:,i-1)))'.*B(O(i),:)';
   [~,Lambda(:,i)]=max(bsxfun(@times,A,Delta(:,i-1)));
end
[~,Q2(N)]=max(Delta(:,N));
fori=N:-1:2
    Q2(i-1)=Lambda(Q2(i),i);
end

输出

Delta=
0.166666666666667      0.0750000000000000    0.0337500000000000
0.250000000000000      0.0281250000000000    0.00316406250000000
0.0833333333333333    0.0281250000000000    0.00949218750000000

最优序列

1     1     1

【学习问题】

1.有监督模式

在有大量标签数据下，直接用频率近似概率參数就可以。

2.无监督模式

Baum-Welch算法

定义变量：在给定模型和观察序列O，在t时刻状态为i，在t+1时刻状态为j的概率

$egin{array}{l}{xi _t}left( {i,j} ight) = Pleft( {{q_t} = i,{q_{t + 1}} = jleft| {O,lambda } ight.} ight)\ = {{{alpha _t}left( i ight){a_{ij}}{b_j}left( {{o_{t + 1}}} ight){eta _{t + 1}}left( j ight)} mathord{left/ {vphantom {{{alpha _t}left( i ight){a_{ij}}{b_j}left( {{o_{t + 1}}} ight){eta _{t + 1}}left( j ight)} {sumlimits_{i = 1}^N {sumlimits_{j = 1}^N {{alpha _t}left( i ight){a_{ij}}{b_j}left( {{o_{t + 1}}} ight){eta _{t + 1}}left( j ight)} } }}} ight. kern- ulldelimiterspace} {sumlimits_{i = 1}^N {sumlimits_{j = 1}^N {{alpha _t}left( i ight){a_{ij}}{b_j}left( {{o_{t + 1}}} ight){eta _{t + 1}}left( j ight)} } }}end{array}$

令

${gamma _t}left( i ight) = sumlimits_{j = 1}^N {{xi _t}left( {i,j} ight)}$

则关于模型參数的一种预计方法为

$egin{array}{l}overline {{pi _i}} = {gamma _1}left( i ight)\overline {{a_{ij}}} = {{sumlimits_{t = 1}^{T - 1} {{xi _t}left( {i,j} ight)} } mathord{left/ {vphantom {{sumlimits_{t = 1}^{T - 1} {{xi _t}left( {i,j} ight)} } {sumlimits_{t = 1}^{T - 1} {{gamma _t}left( i ight)} }}} ight. kern- ulldelimiterspace} {sumlimits_{t = 1}^{T - 1} {{gamma _t}left( i ight)} }}\overline {{b_j}} left( k ight) = {{sumlimits_{t = 1}^T {left{ {{gamma _t}left( j ight)} ight}left| {_{{o_t} = {v_k}}} ight.} } mathord{left/ {vphantom {{sumlimits_{t = 1}^T {left{ {{gamma _t}left( j ight)} ight}left| {_{{o_t} = {v_k}}} ight.} } {sumlimits_{t = 1}^T {{gamma _t}left( j ight)} }}} ight. kern- ulldelimiterspace} {sumlimits_{t = 1}^T {{gamma _t}left( j ight)} }}end{array}$

欢迎參与讨论并关注本博客和微博以及知乎个人主页兴许内容继续更新哦~

转载请您尊重作者的劳动，完整保留上述文字以及文章链接，谢谢您的支持！