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：
- 模型状态集S。状态集记为
$S=\{S_1, S_2, ..., S_N\}$，设有N种可能状态。 - 观测结果种类集V。观测结果种类集合记
$V=\{v_1, v_2, ..., v_M\}$，设有M种可能类别，观测序列的元素即从该集合中取样。 - 状态转移概率 (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类问题：
- 估计指定观测序列的概率（Likelihood）。已知模型
$\lambda$，希望估计出指定观测序列$O=<O_1, O_2, ..., O_T>$的概率，即$p(O|\lambda)$。 - 找出状态序列
$Q$（Decoding）。已知模型$\lambda$以及一个观测序列O，希望找出状态序列$Q=<O_1,O_2,...,O_T>$，可能的解会有若干个，但我们只关心其中具有最大概率产生观测序列O的那个状态序列$Q^*$，即
Q^* = \arg\max_Q p(O| Q,\lambda)
- 找出模型参数
$\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
.