自然语言处理——6.1 马尔可夫模型

2018-10-04 本文已影响64人 SpareNoEfforts

马尔可夫模型描述

存在一类重要的随机过程：如果一个系统有 $N$ 个状态 $S_1, S_2,…, S_N$ , 随着时间的推移，该系统从某一状态转移到另一状态。如果用 $q_t$ 表示系统在时间 $t$ 的状态变量，那么， $t$ 时刻的状态取值为 $S_j(1 \leqslant j \leqslant N)$ 的概率取决于前 $t-1$ 个时刻 $(1, 2, …, t-1)$ 的状态，该概率为：

$p({q_t} = {S_j}|{q_{t - 1}} = {S_i},{q_{t - 2}} = {S_k},...)$

假设1

如果在特定情况下，系统在时间 $t$ 的状态只与其在时间 $t-1$ 的状态相关，则该系统构成一个离散的一阶马尔可夫链：
公式6.1 $p({q_t} = {S_j}|{q_{t - 1}} = {S_i},{q_{t - 2}} = {S_k},...) = p({q_t} = {S_j}|{q_{t - 1}} = {S_i})$

假设2

如果只考虑公式(6.1)独立于时间 $t$ 的随机过程，即所谓的不动性假设，状态与时间无关，那么： $p({q_t} = {S_j}|{q_{t - 1}} = {S_i}) = {a_{ij}}{\text{ 1}} \leqslant {\text{i,j}} \leqslant {\text{N}}$ ……公式6.2

该随机过程称为马尔可夫模型(Markov Model)。

在马尔可夫模型中，状态转移概率 $a_{ij}$ 必须满足下列条件：
$a_{ij} \geqslant 0$ ……公式6.3

$\sum\limits_{j = 1}^N {{a_{ij}} = 1}$ ……公式6.4

马尔可夫模型又可视为随机的有限状态自动机，该有限状态自动机的每一个状态转换过程都有一个相应的概率，该概率表示自动机采用这一状态转换的可能性。

马尔可夫链可以表示成状态图（转移弧上有概率的非确定的有限状态自动机）

零概率的转移弧省略。
每个节点上所有发出弧的概率之和等于1。

状态序列 $S_1, …, S_T$ 的概率：
$\begin{gathered} p({{\text{S}}_{\text{1}}}{\text{,}}...{\text{, }}{{\text{S}}_T}) = p({{\text{S}}_{\text{1}}}) \times p({S_2}{\text{|}}{{\text{S}}_{\text{1}}}) \times p({S_3}{\text{|}}{{\text{S}}_{\text{1}}},{S_2}) \times ... \times p({S_T}{\text{|}}{{\text{S}}_{\text{1}}},...,{S_{T - 1}}) \hfill \\ = p({{\text{S}}_{\text{1}}}) \times p({S_2}{\text{|}}{{\text{S}}_{\text{1}}}) \times p({S_3}{\text{|}}{S_2}) \times ... \times p({S_T}{\text{|}}{S_{T - 1}}) \hfill = \pi \mathop \Pi \limits_{t = 1}^{T - 1} {a_{{S_t}{S_{t + 1}}}} \hfill \\ \end{gathered}$

其中， ${\pi _i} = p({q_1} = {S_i})$ ，为初始状态的概率。

因此，可求得： $p(t, i, p) = p(S_1| t) \times p(S_2 = i | S_1 = t) \times p(S_3 = p | S_2 = i) = 1.0×0.3×0.6 = 0.18$

自然语言处理——6.1 马尔可夫模型

马尔可夫模型描述

假设1

假设2

该随机过程称为马尔可夫模型(Markov Model)。

马尔可夫链可以表示成状态图（转移弧上有概率的非确定的有限状态自动机）

猜你喜欢

热点阅读