HMM

PRML: Chapter 13

对于序列数据，数据的分布往往不是独立同分布的，而当前数据点往往和之前的数据点序列有关,对于这种数据的概率分布建模,有两种：stationary 和 nonstationary, 我们这里关注前者, 也就是序列数据和时间有关,生成分布和时间无关
M阶Markov链 ：条件概率分布只依赖与前M个变量
但是如果我们直接对 $p(x_n \mid x_{n-M},\ldots ,x_{n-1})$ 建模,假设离散变量,那么参数的数量随M指数增长
假设数据由对应的隐变量,满足马尔科夫链结构,得到state space model如下

其中 $z_{n+1} \perp z_{n-1} \mid z_n$, 并且从D分离得, $x_n$ 依赖于所以之前 $x_i(i<n)$
对于以上得图结构，如果隐变量是离散,我们获得了隐式马尔可夫模型(HMM),如果隐变量和观测变量都符合高斯分布,我们获得linear dynamical system

Hidden Markov Model

可以看成Naive Bayes的sequence version，都是生成式模型
有N个观测数据,隐变量有K种值编码1到K
我们定义HMM参数如下

$\pi \; \pi_k = p(z_{1k} = 1)$ 其中 $z_{nk}$ 代表 $z_n$ 处在第k个状态是否为真(初始概率向量)
(transition probabilities) $\mathbf{A} \; A_{jk} = p(z_{nk} = 1 \mid z_{n-1,j} = 1)$ suject to $0 \le A_{jk} \le 1 \sum_{k}A_{jk} = 1$ （状态转移矩阵)
(emission probabilities) $\phi$ 是一组控制 $p(\mathbf{x}_n \mid \mathbf{z}_n, \phi)$ 的参数(混淆矩阵)

那么

$p(z_1 \mid \pi) = \prod_{k=1}^K \pi_{k}^{z_{1k}}$ $p(z_n \mid z_{n-1}) = \prod_{k=1}^K \prod_{j=1}^K A_{jk}^{z_{nk}z_{n-1,j}}$ $p(x_n \mid z_n) = \prod_{k=1}^K p(x_n \mid \phi_k)^{z_{nk}}$

HMM假设

齐次马尔科夫性假设：假设隐藏的马尔科夫链在任意时刻的状态只依赖前一时刻的状态,与其他时刻状态以及观测无关,也和当前时刻t无关
$p(z_i \mid z_{i-1}, \ldots, z_1) = p(z_i \mid z_{i-1})$
$p(z_{i+1} \mid z_{i}) = p(z_{j+1} \mid z_j)$
观察独立性假设：假设任意时刻观测只依赖于该时刻马尔科夫链的状态,和其他观测状态无关
$p(x_1,\ldots,x_N \mid z_1, \ldots, z_N) = \prod p(x_i \mid z_i)$

$p(\mathbf{X},\mathbf{Z}\mid \theta) = p(\mathbf{z}_1 \mid \pi)\left[ \prod_{n=2}^N p(\mathbf{z}_n \mid \mathbf{z}_{n-1}, \mathbf{A}) \right] \prod_{m=1}^N p(\mathbf{x}_m \mid \mathbf{z}_m, \phi)$

其中 $\mathbf{X} = \{\mathbf{x_1, \ldots, x_N}\}$ , $\mathbf{Z} = \{\mathbf{z_1, \ldots, z_N}\}$ , $\theta = \{\mathbf{\pi,A,\phi}\}$
上面是标准的HMM模型,很多HMM的变形，比如left-to-right HMM,它限制 $A_{jk} = 0 (k < j)$

Maximum likelihood for the HMM

$p(X \mid \theta) = \sum_{Z}p(X,Z \mid \theta)$

直接最大化导致没有闭式解,采用EM算法

选择 $Q(Z) = p(Z \mid X, \theta)$
选择 $\theta := \underset{\theta}{argmax}\;\sum_{Z}Q(Z)\mathrm{ln}\; \frac{p(X,Z \mid \theta)}{Q(Z)} = \underset{\theta}{argmax}\sum_{Z}p(X, Z \mid \theta^{old})\mathrm{ln}p(X,Z \mid \theta)$
迭代到收敛

$\gamma(z_n) = p(z_n \mid X, \theta^{old})$ $\xi(z_{n-1}, z_n) = p(z_{n-1},z_n \mid X, \theta^{old})$

$\gamma(z_{nk})$ 是 $\gamma(z_n = k)$, $\xi(z_{n-1,j},z_{nk})$ 是 $\xi_(z_{n-1} = j, z_n = k)$

$\gamma(z_{nk}) = p(z_{nk} = 1 \mid X, \theta^{old}) = E_{z_{n} \sim \gamma}[z_{nk}] \\ = \sum_{k=1}^K \gamma(z_n = k)z_{nk} = \sum_{z}\gamma(z)z_{nk}$ $\xi(z_{n-1,j},z_{nk}) = p(z_{n-1,j}z_{nk} = 1 \mid X, \theta^{old}) = E_{z_{n-1},z_{n} \sim \xi}[z_{n-1,j}z_{nk}] \\ = \sum_{z_{n-1},z_{n}}\xi(z_{n-1},z_n)z_{n-1,j}z_{nk}$

(这里PRML写的是 $\sum_{z}\gamma(z)z_{n-1,j}z_{nk}$ ????)

$\sum_{Z}p(Z\mid X, \theta^{old})\mathrm{ln}p(X,Z \mid \theta) \\ =\sum_{Z} p(Z \mid X, \theta^{old}) [\mathrm{ln} p(z_1 \mid \pi) + \sum \mathrm{ln} p(z_n \mid z_{n-1}, A) + \sum \mathrm{ln}p(x_m \mid z_m, \phi)] \\ = \sum_{Z} ??[\sum_{k=1}^K z_{1k}\mathrm{ln}\pi_k + \sum_{n=2}^N\sum_{k=1}^K\sum_{j=1}^K z_{nk}z_{n-1,j}\mathrm{ln}A_{jk} + \sum_{n=1}^N\sum_{k=1}^K z_{nk}\mathrm{ln}(x_n \mid \phi_k)] \\ =\sum_{k=1}^K \gamma(z_{1k})\mathrm{ln}\pi_k + \sum_{n=2}^N\sum_{j=1}^K\sum_{k=1}^K \xi(z_{n-1,j},z_{nk})\mathrm{ln}A_{jk} + \sum_{n=1}^N \sum_{k=1}^K \gamma(z_{nk})\mathrm{ln}p(x_n \mid \phi_k)$

(gg ??的地方推导失败那他怎么得到下面的式子啊我凉了)

用拉格朗日乘子法

$\pi_k = \frac{\gamma(z_{1k})}{\sum_{j=1}^K \gamma(z_{1j})}$ $A_{jk} = \frac{\sum_{n=2}^N \xi(z_{n-1,j},z_{nk})}{\sum_{l=1}^K\sum_{n=2}^N\xi(z_{n-1,j},z_{nl})}$

注意 $\pi\;A$ 中的元素初始化为0那么会一直保持0,一般随机初始化suject to 和为1和正数限制
关于 $\phi_k$ 最大化时,最后一项类似混合高斯分布的形式
如果 $p(x_n \mid \phi_k) = N(x_n\mid \mu_k, \Sigma_k)$

$\mu_k = \frac{\sum_{n=1}^N \gamma(z_{nk})x_n}{\sum_{n=1}^N \gamma(z_{nk})}$ $\Sigma_k = \frac{\gamma(z_{nk})(x_n - \mu_k)(x_n - \mu_k)^T}{\sum_{n=1}^N \gamma(z_{nk})}$

EM算法还需要初始化 $\phi$ , 一种方式是先假设数据是iid,然后估计出来的参数作为初始值

forward-backward algorithm(Baum-Welch)

有效估计 $\gamma(z_{nk})$ 和 $\xi(z_{n-1,j},z_{nk})$ 的方法

由D分离性质，我们有

$p(X \mid z_n) = p(x1,\ldots,x_n\mid z_n)p(x_{n+1},\ldots,x_N \mid z_n)$ $\gamma(z_n) = p(z_n \mid X) = \frac{p(X \mid z_n)p(z_n)}{p(X)} \\ = \frac{p(x_1,\ldots,x_n, z_n)p(x_{n+1},\ldots,x_{N}\mid z_n)}{p(X)} \\ = \frac{\alpha(z_n)\beta(z_n)}{p(X)}$

定义

$\alpha(z_n) = p(x_1,\ldots,x_n,z_n) = p(x_1,\ldots,x_n \mid z_n)p(z_n) \\ = p(x_n\mid z_n)p(x_1,\ldots,x_{n-1}\mid z_n)p(z_n) \\ = p(x_n \mid z_n)\sum_{z_{n-1}}p(x1,\ldots,x_{n-1},z_{n-1},z_n) \\ = p(x_n \mid z_n)\sum_{z_{n-1}}p(x1,\ldots,x_{n-1},z_n\mid z_{n-1})p(z_{n-1}) \\ = p(x_n \mid z_n)\sum_{z_{n-1}}p(x1,\ldots,x_{n-1} \mid z_{n-1})p(z_n \mid z_{n-1})p(z_{n-1}) \\ = p(x_n \mid z_n)\sum_{z_{n-1}}p(x1,\ldots,x_{n-1},z_{n-1})p(z_n \mid z_{n-1})$

也就是

$\alpha(z_n) = p(x_n \mid z_n) \sum_{z_{n-1}}\alpha(z_{n-1})p(z_n \mid z_{n-1})$

初始时

$\alpha(z_1) = p(x_1,z_1) = p(z_1)p(x_1 \mid z_1) = \prod_{k=1}^K \{\pi_k p(x_1 \mid \phi_k)\}^{z_{1k}}$

计算整个链的时间复杂度为 $O(NK^2)$

同理

$\beta(z_n) = p(x_{n+1},\ldots,x_N \mid z_n) = \sum_{z_{n+1}}p(x_{n+1},\ldots,x_N,z_{n+1}\mid z_{n}) \\ = \sum_{z_{n+1}}p(x_{n+1},\ldots,x_N \mid z_{n+1},z_{n})p(z_n \mid z_{n+1}) \\ = \sum_{z_{n+1}}p(x_{n+1},\ldots,x_N \mid z_{n+1})p(z_n \mid z_{n+1}) \\ = \sum_{z_{n+1}}p(x_{n+2},\ldots,x_N \mid z_{n+1})p(x_{n+1} \mid z_{n+1})p(z_n \mid z_{n+1})$

也就是

$\beta(z_n) = \sum_{z_{n+1}}\beta(z_{n+1})p(x_{n+1} \mid z_{n+1})p(z_{n+1} \mid z_{n})$

初始时

$p(X \mid z_N) = \frac{\alpha(z_N)\beta(z_N)}{p(X)} \Rightarrow \beta(z_N) = 1$

对于 $p(X)$ 的计算,在参数估计时可以约分掉,如果我们想要知道 $p(X)$ 值那么

$p(X) = \sum_{n}\alpha(z_n)\beta(z_n) = \sum_{z_N}\alpha(z_N)$

接下来我们估计 $\xi$ 函数,利用函数定义和D分离性质有

$\xi(z_{n-1},z_n) = p(z_{n-1},z_n \mid X) = \frac{p(X \mid z_{n-1},z_{n})p(z_{n-1},z_n)}{p(X)} \\ = \frac{p(x_1,\ldots,x_{n-1} \mid z_{n-1})p(x_{n+1},\ldots,x_N \mid z_{n})p(x_n \mid z_n)p(z_{n-1})p(z_n \mid z_{n-1})}{p(X)} \\ = \frac{\alpha(z_{n-1})p(x_n \mid z_n)p(z_n \mid z_{n-1})\beta(z_n)}{p(X)}$

其中 $p(x_n \mid z_n)$ 因为 $x_n$ 是已经观察到的变量,在EM算法之前可以把其表示为 $z_n$ 的函数, 并且保持不变(形式？)

如果观察到 X ,希望预测 N+1时刻的x值

$p(x_{N+1} \mid X) = \sum_{z_{N+1}}p(x_{N+1},z_{N+1} \mid X) \\ = \sum_{z_{N+1}}p(x_{N+1}\mid z_{N+1})p(z_{N+1}\mid X) \\ = \sum_{z_{N+1}}p(x_{N+1}\mid z_{N+1})\sum_{z_N}p(z_{N+1},z_N \mid X) \\ = \sum_{z_{N+1}}p(x_{N+1}\mid z_{N+1})\sum_{z_N}p(z_N \mid X)p(z_{N+1}\mid z_{N}, X)\\ = \sum_{z_{N+1}}p(x_{N+1}\mid z_{N+1})\sum_{z_N}p(z_N \mid X)p(z_{N+1}\mid z_{N}) \\ = \frac{1}{p(X)}\sum_{z_{N+1}}p(x_{N+1}\mid z_{N+1}) \sum_{z_N}p(z_N, X)p(z_{N+1} \mid z_{N}) \\ = \frac{1}{p(X)}\sum_{z_{N+1}}p(x_{N+1}\mid z_{N+1}) \sum_{z_N}p(z_{N+1} \mid z_{N})\alpha(z_N)$

The sum-product algorithm for HMM

提供简便推导 $\alpha - \beta$ 递归的方法
HMM的简化的因子图可以表示为

其中

$h(z_1) = p(z_1)p(x_1 \mid z_1)$ $f_n(z_{n-1},z_n) = p(z_n \mid z_{n-1})p(x_n \mid z_n)$

把 $z_N$ 当作根,用sum-product算法推导如下

$\mu_{z_{n-1} \rightarrow f_n}(z_{n-1}) = \mu_{f_{n-1} \rightarrow z_{n-1}}(z_{n-1})$ $\mu_{f_n \rightarrow z_n}(z_n) = \sum_{z_{n-1}}f_n(z_{n-1},z_n) \mu_{z_{n-1} \rightarrow f_n}(z_{n-1}) \\ = \sum_{z_{n-1}}f_n(z_{n-1},z_n)\mu_{f_{n-1} \rightarrow z_{n-1}}(z_{n-1})$

如果我们定义 $\alpha(z_n) = \mu_{f_n \rightarrow z_n}(z_n)$ 由于 $\mu_{h \rightarrow z_1} = h(z_1)$ 和 $\alpha(z_1)$ 的公式一样，两者的迭代公式一样，所以两者 $\alpha$ 是相同的

考虑从根的回传信息，根据sum-product算法有

$\mu_{z_{n+1} \rightarrow f_{n+1}}(z_{n+1}) = \mu_{f_{n+2} \rightarrow z_{n+1}}(z_{n+1})$ $\mu_{f_{n+1} \rightarrow z_n}(z_n) = \sum_{z_{n}}f_{n+1}(z_{n}, z_{n+1})\mu_{z_{n+1} \rightarrow f_{n+1}(z_{n+1})} = \sum_{z_{n}}f_{n+1}(z_n,z_{n+1})\mu_{f_{n+2} \rightarrow z_{n+1}}(z_{n+1})$

定义 $\beta(z_n) = \mu_{f_{n+1} \rightarrow z_n}(z_n)$ 同理可证,两者的 $\beta$ 函数也是等价的

scale the factor

Viterbi

given x and M how to find y given y and X, how to find parameters of M to max p(y\midx, M)

sequential data

Hidden Markov Model

Maximum likelihood for the HMM

forward-backward algorithm(Baum-Welch)

The sum-product algorithm for HMM

scale the factor

Viterbi

CATALOG

FEATURED TAGS

FRIENDS