HMM 隐马尔科夫模型

Hidden Markov Model (HMM) 隐马尔可夫模型

离散马尔可夫过程:一个系统,其在任意时刻会处于且只能处于N个状态中的一个。记状态集为$S=\{S_1, S_2, ..., S_N\}$,系统在时刻t时的状态为$q_t$,意味着$q_t=S_i\in S, 1\leqslant i \leqslant N$。这里的时刻的内涵在于其是某种序列上的一点,该方法可对任意序列都有效,如时序、空间轨迹等。

系统在离散的时刻根据以前的状态以既定的概率转到下一个状态:

p(q_{t+1}| q_t, q_{t-1}, ...)

对于一阶马尔可夫模型,系统在下一个时刻的状态仅依赖于当前时刻的状态,而与更早的状态无关:

p(q_{t+1} | q_t, q_{t-1}, ...) = p(q_{t+1} | q_t)

转移概率:系统从一个状态转移到另一个状态的概率。可以简化模型,假设状态间的转移概率与系统发展过程无关(即与时间无关),亦即$p(q_{t+1}|q_t)\equiv p(q_{t'+1}|q_{t'}), \forall t, t'$。转移概率矩阵$\bm A_{N\times N}$,其中元素$A_{ij}$表示从状态i转移到状态j的概率,由于一个状态i到所有可能的状态(包括相同的状态i)的转移概率之和应该为1,故$A_{ij}\ge 0 \wedge \sum_j A_{ij}=1$

在一个可观测的马尔可夫模型(observable Markov model)中,状态是可被观测的,在任意时刻t,我们都可知道其对应的状态$q_t$,并随着过程的发展,系统不断地从一个状态转移到另一个状态。

隐马尔可夫模型
Hidden Markov Model, HMM。在隐马尔可夫模型中,系统的状态是不可被观测的,但是系统到达一个状态时,可以记录一个观测,这个观测是此时系统状态的一个概率函数。

HMM中假设状态转移概率不依赖于时间t,即在任何时候,从状态$q_i$转移到状态$q_j$的概率均相同。

模型可能的状态的集合记S,可能的观测结果种类的集合记V。模型状态序列记Q,观测序列记O。时间t时,模型状态为$q_t$,观测(结果)为$O_t$。初始时刻的状态记$q_1$

对于一个既定模型,一个同样的观测序列可以由多个不同的状态序列产生而来,但我们一般只关心具有最大概率产生观测序列的那个状态序列。

形式化HMM:

  1. 模型状态集S。状态集记为$S=\{S_1, S_2, ..., S_N\}$,设有N种可能状态。
  2. 观测结果种类集V。观测结果种类集合记$V=\{v_1, v_2, ..., v_M\}$,设有M种可能类别,观测序列的元素即从该集合中取样。
  3. 状态转移概率 (transition probability matrix):
\bm A = [a_{ij}]\in\R^{N\times N}, \text{ 其中 } a_{ij}\equiv p(q_{t+1}=S_j | q_t=S_i), \forall t

其中的“恒等且对所有t”($...\equiv ... \forall t$)即表示转移概率与时间无关,HMM假设转移概率与时间(系统状态转移历史)无关。
4. 观测概率 (emission probability matrix, observation likelihoods)

\bm B=[b_{jm}]\in\R^{N\times M}, \text{ 其中 } b_{jm}\equiv p(O_t=v_m | q_t=S_j), \forall t

即模型状态为$S_j$时,观测结果的种类为$v_m$的概率,HMM中假设其与时间无关。
5. 观测序列O。$O=[o_1, o_2,\cdots, o_T]$,一个观测值$o_t$从集合V中取样,其还隐含一个不可观测的状态q_t(即HMM中的hidden variable)。
6. 初始时刻各状态概率:

\bm\Pi = [\pi_i]\in\R^N, \text{ 其中 } \pi_i = p(q_1=S_i), 1\le i \le N, \sum_{i}^N \pi_i = 1

$\lambda=\left(\bm A, \bm B, \bm \Pi\right)$被称作HMM的参数集(其中蕴含了N,M)。

HMM关心的3类问题:

  1. 估计指定观测序列的概率(Likelihood)。已知模型$\lambda$,希望估计出指定观测序列$O=<O_1, O_2, ..., O_T>$的概率,即$p(O|\lambda)$
  2. 找出状态序列$Q$ (Decoding)。已知模型$\lambda$以及一个观测序列O,希望找出状态序列$Q=<O_1,O_2,...,O_T>$,可能的解会有若干个,但我们只关心其中具有最大概率产生观测序列O的那个状态序列$Q^*$,即
Q^* = \arg\max_Q p(O| Q,\lambda)
  1. 找出模型参数$\lambda$ (Learning)。已知以观测序列组成的训练集$\mathcal X={O^{(k)}}$(即其中一个样本k是一个观测序列$O^{(k)}=<O_1^{(k)},O_2^{(k)},...>$),希望学习到具有最大概率产生$\mathcal X$的模型参数$\lambda^*$,即
\lambda^* = \arg\max_\lambda p(\lambda | \mathcal X)

Markov Random Fields 马尔科夫随机场

A Markov random field is a set of random variables having the Markov property described by an undirected graph.

A Markov random field is known as a Markov network or undirected graph model. (无向图概率模型)

Differences between Markov networks and Bayesian networks: Bayesian networks are directed and acylic, and Markov networks are undirected and may be cylic.

A multivariate normal distribution forms a Markov random field $G=(V,E)$ if the pair nodes of a zero entry inside the inverse covariance matrix corresponds to the unreachability between the pair nodes. i.e.:

\bm X=[\bm X_v]_{v\in V} \sim \mathcal{N}(\bm \mu, \bm \Sigma)

such that

[\bm \Sigma^{-1}]_{uv} = 0 \iff <u,v>\not\in E

.

上一篇:linux平台下的6818开发板(ARM)显示屏的字体显示


下一篇:Scalable Rule-Based Representation Learning for Interpretable Classification