Machine Learning笔记(8)

Jensen’s inequality

Theorem: 令f是凸函数, X是随机变量, 那么有 $E[f(X)] \ge f(EX)$, 并且如果f是严格凸函数, 那么 $E[f(X)] = f(EX) \Leftrightarrow X = EX \; w.p. \;1$(X是常数)

EM algorithm

假设我们有数据集 $S = \{x^1, \ldots, x^m\}$, 似然函数是
$l(\theta) = \sum_{i=1}^m \log p(x;\theta) = \sum_{i=1}^m\log \underset{z}{\sum}p(x,z;\theta)$
直接对 $l(\theta)$求偏导得到参数往往是困难的，而
$l(\theta) = \sum_{i=1}^m \log p(x^i;\theta) \\ = \sum_{i=1}^m\log \underset{z^i}{\sum}p(x^i,z^i;\theta) \\ = \sum_{i=1}^m \log \underset{z^i}{\sum}Q_i(z^i)\frac{p(x^i,z^i;\theta)}{Q_i(z^i)} \\ = \sum_{i=1}^m \log \underset{z^i \sim Q_i}{E}[\frac{p(x^i,z^i;\theta)}{Q_i(z^i)}] \\ \ge \sum_{i=1}^m \underset{z^i \sim Q_i}{E}[\log {\frac{p(x^i,z^i;\theta)}{Q_i(z^i)}}] \\ \ge \sum_{i=1}^m\underset{z^i}{\sum}Q(z^i)\log{\frac{p(x^i,z^i;\theta)}{Q_i(z^i)}}$
其中 $Q_i(z^i) \ge 0$并且 $\sum_{z^i} Q_i(z^i) = 1$是一个概率分布函数
我们希望选取合适的Q函数使得在特定的参数 $\theta$取值点, 等号成立,那么需要
$\frac{p(x^i,z^i;\theta)}{Q_i(z^i)} = c$
c是一个和 $z^i$无关的常数
$Q_i(z^i) \propto p(x^i,z^i;\theta)$
$Q_i(z^i) = \frac{p(x^i,z^i;\theta)}{\sum_{z^i} p(x^i,z^i;\theta)} \\ = \frac{p(x^i,z^i;\theta)}{p(x^i;\theta)} \\ = p(z^i \mid x^i; \theta)$
EM:
Repeat until converge
E-step:
$Q_i(z^i) := p(z^i \mid x^i; \theta)$
M-step:
$\theta := \underset{\theta}{\mathrm{argmax}}\sum_{i=1}^m\underset{z^i}{\sum}Q(z^i)\log{\frac{p(x^i,z^i;\theta)}{Q_i(z^i)}}$
也就是说在E步在 $\theta^t$点我们选取 $Q_i^t$使得它成为 $l(\theta^t)$一个紧的下界( $l(\theta^t) = J(Q^t, \theta^t)$),然后我们固定 $Q_i^t$不变,关于 $\theta$最大化下界得到 $\theta^{t+1}$,由于不等式 $l(\theta) \ge J(Q,\theta)$总是成立,可以证明 $l(\theta^{t+1}) \ge J(Q^t, \theta^{t+1}) \ge J(Q^t, \theta^{t}) = l(\theta^t)$,其中
$J(Q, \theta) = \sum_{i=1}^m\underset{z^i}{\sum}Q(z^i)\log{\frac{p(x^i,z^i;\theta)}{Q_i(z^i)}}$
因此EM算法也可以看在J上的坐标上升
注意EM算法对初始点敏感,可以保证收敛到稳定度但是不能保证收敛到极大值点

EM算法求解混合高斯模型

E-step:
$w_j^i = Q_i(z^i = j) = P(z^i = j \mid x^i; \phi, \mu, \Sigma)$
M-step:
$W(\phi,\mu,\Sigma) = \sum_{i=1}^m\underset{z^i}{\sum}Q(z^i)\log{\frac{p(x^i,z^i;\phi,\mu,\Sigma)}{Q_i(z^i)}} \\ =\sum_{i=1}^m\sum_{j=1}^k Q(z^i = j)\log{\frac{p(x^i \mid z^i = j;\mu, \Sigma)p(z^i = j;\phi)}{Q_i(z^i = j)}} \\ =\sum_{i=1}^m\sum_{j=1}^k w_j^i \log{\frac{\frac{1}{(2\pi)^{n/2}{\lvert \Sigma_j \rvert}^{n/2}}exp(-\frac{1}{2}(x^i - \mu_j)^T \Sigma_j^{-1}(x^i - \mu_j))\phi_j}{w_j^i}}$
$\nabla_{\mu_l}W = -\nabla_{\mu_l}\sum_{i=1}^m\sum_{j=1}^k w_j^i \frac{1}{2} (x^i-\mu_j)^T \Sigma_j^{-1} (x^i - \mu_j) \\ =\sum_{i=1}^m w_l^i(\Sigma_l^{-1}x^i - \Sigma_l^{-1}\mu_l) = 0 \Rightarrow \mu_l := \frac{\sum_{i=1}^m w_l^i x^i}{\sum_{i=1}^m w_l^i}$
关于 $\phi$最大化W
$W = \sum_{i=1}^m\sum_{j=1}^k w_j^i\log{(A\phi_j)} \\ = \sum_{i=1}^m\sum_{j=1}^k w_j^i\log{\phi_j} + \sum_{i=1}^m\sum_{j=1}^k w_j^i \log{A} \\ = \sum_{i=1}^m\sum_{j=1}^k w_j^i\log{\phi_j} + B$
其中A和B是和 $\phi$无关的量,并且 $\sum_{j=1}^k\phi_j = 1$,因此构造拉格朗日函数
$L(\phi) = \sum_{i=1}^m\sum_{j=1}^k w_j^i \log{\phi_j} + \beta (\sum_{j=1}^k \phi_j - 1)$
$\beta$是拉格朗日乘子
$\frac{\partial}{\partial \phi_j}L = \sum_{i=1}^m \frac{w_j^i}{\phi_j} + \beta = 0 \Rightarrow \phi_j = - \frac{\sum_{i=1}^m w_j^i}{\beta}$
又因为 $\sum_{j=1}^k \phi_j = 1$推出
$\phi_j = \frac{\sum_{i=1}^m w_j^i}{\sum_{i=1}^m\sum_{l=1}^k w_l^i} \Rightarrow \phi_j := \frac{\sum_{i=1}^m w_j^i}{m}$

EM for Mixture of naive Bayes

• Previous
  Machine Learning笔记(7)
• Next
  Machine Learning笔记(9)