大絮

# 期望最大化

期望最大化算法（EM）是机器学习中用来求解参数的一种迭代式方法，能收敛到局部最优，不保证全局最优。EM算法是MM算法（Minorize-Maximization algorithm）的特例之一。可以解决的典型的参数估计问题有高斯混合模型、隐马尔科夫模型等。

# 1. 最大似然视角

# 1.1 Jensen不等式

Jensen不等式描述如下：

若 f(x)f(x) 是区间 (a,b)(a,b) 上的凸函数，则对任意的 x1,x2,x3,...,xn∈(a,b)x_1,x_2,x_3,...,x_n \in (a,b) ，有不等式:

f(x1+x2+x3+...+xnn)≥f(x1)+f(x2)+f(x3)+...+f(xn)n(1.1)f({ {x_1+x_2+x_3+...+x_n} \over n}) \ge {f(x_1)+f(x_2)+f(x_3)+...+f(x_n) \over n} \tag {1.1}

当且仅当 x1=x2=x3=...=xnx_1=x_2=x_3=...=x_n 时，等号成立。如果 f(x)f(x) 为凹函数，则 ≥\ge 号取反。

也可以表示为：

f(E(X))≥E(f(X))(1.2)f(E(X)) \ge E(f(X)) \tag {1.2}

# 1.2 最大似然估计

最大似然估计（Maximum Likelihood Estimation, MLE）属于概率论中点估计，也是机器学习中参数估计的重要方法。

假设数据为 X=(x1,x2,x3,...,xN)X=(x_1,x_2,x_3,...,x_N)，数据在某个概率模型下出现的概率为

P(X∣θ)=p(x1∣θ)p(x2∣θ)p(x3∣θ)...p(xN∣θ)(1.3)P(X|\theta)=p(x_1|\theta)p(x_2|\theta)p(x_3|\theta)...p(x_N|\theta) \tag {1.3}

要估计一个合适的参数 θ\theta，确保 P(X∣θ)P(X|\theta) 取得最大值。因为 p(xi)∈[0,1]p(x_i) \in [0,1]，P(X)P(X) 连乘的性质会导致其值接近无穷小，难以计算，所以在 P(X∣θ)P(X|\theta) 之前加一个对数操作，把连乘转化成连加，再通过求导数求极值的方法进行参数估计。

L(X∣θ)=log⁡P(X∣θ)=∑iNlog⁡p(xi∣θ)(1.4)L(X|\theta) = \log P(X|\theta) = \sum_{i}^N \log p(x_i|\theta) \tag {1.4}

期望最大化中引入了无法观测的隐变量 ZZ， ZZ 的作用是在某种程度上影响了生成可观测数据 XX 的概率模型。EM算法推导如下：

L(X∣θ)=log⁡P(X∣θ)=∑iNlog⁡∑zP(xi,zj∣θ)=∑iNlog⁡∑zQ(zj)P(xi,zj∣θ)Q(zj) \begin{aligned} L(X|\theta) = \log P(X|\theta) \\ = \sum_{i}^N \log \sum_{z}P(x_i,z_j|\theta) \\ = \sum_{i}^N \log \sum_{z} Q(z_j) {P(x_i,z_j|\theta) \over Q(z_j)} \end{aligned}
≥∑iN∑zQ(zj)log⁡P(xi,zj∣θ)Q(zj)(1.5) \begin{aligned} \ge \sum_{i}^N \sum_{z} Q(z_j) \log {P(x_i,z_j|\theta) \over Q(z_j)} \tag{1.5} \end{aligned}

其中 (1.5)(1.5) 是由Jensen不等式推导而来，为了使等号成立，得到一个更加紧凑的边界，假设：

P(xi,zj∣θ)Q(zj)=C(1.6) {P(x_i,z_j|\theta) \over Q(z_j)} = C \tag{1.6}

推导公式得：

P(xi,zj∣θ)Q(zj)=C⇒P(xi,zj∣θ)=C⋅Q(zj)⇒∑zP(xi,zj∣θ)=∑zC⋅Q(zj)⇒P(xi∣θ)=C=P(xi,zj∣θ)Q(zj)⇒Q(zj)=P(xi,zj∣θ)P(xi∣θ) \begin{aligned} {P(x_i,z_j|\theta) \over Q(z_j)} = C \\[3ex] \Rightarrow P(x_i,z_j|\theta) = C \cdot Q(z_j) \\[3ex] \Rightarrow \sum_{z} P(x_i,z_j|\theta) = \sum_{z} C \cdot Q(z_j) \\[3ex] \Rightarrow P(x_i|\theta) = C = {P(x_i,z_j|\theta) \over Q(z_j)} \\[3ex] \Rightarrow Q(z_j) = {P(x_i,z_j|\theta) \over P(x_i|\theta)} \end{aligned}
Q(zj)=P(zj∣xi,θ)(1.7) \begin{aligned} Q(z_j) = P(z_j|x_i,\theta) \tag{1.7} \end{aligned}

由此可得期望最大化的E-Step和M-Step。EM算法的迭代过程也是不断提高 L(X∣θ)L(X|\theta) 函数下界的过程，直到函数收敛，但是不保证收敛到全局最优解。

E-Step:

Q(zj)=p(zj∣xi,θ)Q(z_j) = p(z_j|x_i,\theta)

M-Step:

θ=argmax⁡θ∑iN∑zQ(zj)log⁡P(xi,zj∣θ)Q(zj)\theta = arg\,\max_{\theta} \sum_{i}^N \sum_{z} Q(z_j) \log {P(x_i,z_j|\theta) \over Q(z_j)}

期望最大化算法的收敛性的证明为：

L(θt+1)≥Qit(zj)log⁡p(xi,zj∣θt+1)Qit(zj)(1.8) L(\theta^{t+1}) \ge Q_{i}^{t}(z_j) \log {p(x_i,z_j|\theta^{t+1}) \over Q_i^{t}(z_j)} \tag{1.8}
≥Qit(zj)log⁡p(xi,zj∣θt)Qit(zj)(1.9) \ge Q_{i}^{t}(z_j) \log {p(x_i,z_j|\theta^{t}) \over Q_i^{t}(z_j)} \tag{1.9}

其中公式 (1.8)(1.8) 由Jensen不等式得证，公式 (1.9)(1.9) 由M步的极大值求解得证。

可以把EM算法迭代求解的过程看过是坐标上升算法，E步固定 θ\theta 求 QQ ，M步固定 QQ 求 θ\theta。

# 2. 相对熵视角

# 2.1 相对熵

相对熵（relative entropy），又称为Kullback-Leibler散度，用来衡量两个概率分布之间的差异程度，非对称。

设 P(x)P(x)，Q(x)Q(x) 是随机变量 XX 上的两个概率分布，则在离散和随机变量情形下，定义如下

KL(P∣∣Q)=∑P(x)log⁡P(x)Q(x)(2.1) KL(P||Q) = \sum P(x) \log {P(x) \over Q(x)} \tag{2.1}
KL(P∣∣Q)=∫P(x)log⁡P(x)Q(x)(2.2) KL(P||Q) = \int P(x) \log {P(x) \over Q(x)} \tag{2.2}

且 KL(P∣∣Q)≥0KL(P||Q) \ge 0。

相对熵详细的讲解，请看变分推断 (opens new window)。

# 2.2 变分推断

变分推断中，依然最大化似然估计 L(X∣θ)L(X|\theta)。

L(X∣θ)=log⁡P(X∣θ)=log⁡P(X,Z∣θ)P(Z∣X,θ)=log⁡P(X,Z∣θ)−log⁡P(Z∣X,θ)+log⁡Q(Z)−log⁡Q(Z) \begin{aligned} L(X|\theta) = \log P(X|\theta) = \log {P(X,Z|\theta) \over P(Z|X,\theta)} \\[3ex] = \log P(X,Z|\theta) - \log P(Z|X,\theta) + \log Q(Z) - \log Q(Z) \end{aligned}
=log⁡P(X,Z∣θ)−log⁡Q(Z)−log⁡P(Z∣X,θ)Q(Z)(2.3) = \log P(X,Z|\theta) - \log Q(Z) - \log {P(Z|X,\theta) \over Q(Z)} \tag{2.3}

得到 (2.3)(2.3) 式之后，对两边同时针对 Q(Z)Q(Z) 取期望。

∫Q(z)log⁡P(X∣θ)=∫Q(z)log⁡P(X,Z∣θ)−∫Q(z)log⁡Q(Z)−∫Q(z)log⁡P(Z∣X,θ)Q(Z)⇒log⁡P(X∣θ)=∫Q(z)log⁡P(X,Z∣θ)−∫Q(z)log⁡Q(Z)+∫Q(z)log⁡Q(Z)P(Z∣X,θ) \begin{aligned} \int_{Q(z)} \log P(X|\theta) = \int_{Q(z)} \log P(X,Z|\theta) - \int_{Q(z)} \log Q(Z) - \int_{Q(z)} \log {P(Z|X,\theta) \over Q(Z)} \\[3ex] \Rightarrow \log P(X|\theta) = \int_{Q(z)} \log P(X,Z|\theta) - \int_{Q(z)} \log Q(Z) + \int_{Q(z)} \log {Q(Z) \over P(Z|X,\theta)} \\[3ex] \end{aligned}
⇒log⁡P(X∣θ)=ELBO+KL(Q∣∣P)(2.4) \Rightarrow \log P(X|\theta) = ELBO + KL(Q||P) \tag{2.4}

其中:

ELBO=∫Q(z)log⁡P(X,Z∣θ)−∫Q(z)log⁡Q(Z)KL(Q∣∣P)=∫Q(z)log⁡Q(Z)P(Z∣X,θ), \begin{aligned} ELBO = \int_{Q(z)} \log P(X,Z|\theta) - \int_{Q(z)} \log Q(Z) \\[3ex] KL(Q||P) = \int_{Q(z)} \log {Q(Z) \over P(Z|X,\theta)}, \\[3ex] \end{aligned}

Evidence Lower Bound是 log⁡P(X∣θ)\log P(X|\theta) 的下界，简称为ELBO。可以通过不断的提高下界的方式来最大化似然估计。

假设：

Q(Z)=C⋅P(Z∣X,θ)(2.5) Q(Z) = C \cdot P(Z|X,\theta) \tag{2.5}

这个假设的含义是用一个概率分布 Q(Z)Q(Z) 来表示 P(Z∣X,θ)P(Z|X,\theta) ，当两者相等时， KL(Q∣∣P)KL(Q||P) 是一个常数。优化的目标变成了最大化ELBO。这个假设与上一节的Jensen不等式一样。（KL距离和Jensen不等式内在一定具有某种联系）

则有：

log⁡P(X∣θ)=ELBO+constantlog⁡P(X∣θ)=∫Q(z)log⁡P(X,Z∣θ)−∫Q(z)log⁡Q(Z)+constantlog⁡P(X∣θ)=∫zQ(z)log⁡p(X,z∣θ)−∫zQ(z)log⁡Q(z)log⁡P(X∣θ)=∫zQ(z)log⁡p(X,z∣θ)log⁡Q(z) \begin{aligned} \log P(X|\theta) = ELBO + constant \\[3ex] \log P(X|\theta) = \int_{Q(z)} \log P(X,Z|\theta) - \int_{Q(z)} \log Q(Z) + constant \\[3ex] \log P(X|\theta) = \int_z {Q(z) \log p(X,z|\theta)} - \int_{z} Q(z) \log Q(z) \\[3ex] \log P(X|\theta) = \int_z Q(z) { \log p(X,z|\theta) \over \log Q(z) } \\[3ex] \end{aligned}
=∫x∫zQ(z)log⁡p(x,z∣θ)log⁡Q(z)(2.6) = \int_{x} \int_{z} Q(z) { \log p(x,z|\theta) \over \log Q(z) } \tag{2.6}

到此，从相对熵角度的推导就和最大似然角度的推导取得相同结论。（Jensen不等式和相对熵必定具有联系，使得两者有等价性）。

最近更新: 3/23/2022, 22:50:49

← Varitional Inference →