基础知识准备

期望最大值(Expectation Maximization, EM)算法, 是一种求解含有隐变量(Latent Variable)的概率模型其参数的极大似然估计(Maximum Likelihood Estimation)方法, 或称为极大后验概率估计. EM算法可以说是一种框架或方法论.

许多算法都以EM算法作为基础, 如:

• 隐马尔科夫算法(HMM)

• LDA主题模型

等. 首先准备EM算法的基础知识

基础知识

1. 凸函数与凹函数

假设函数$f(x)$在区间$I$上连续, 且对于$\forall x_1,x_2 \in I$和$\forall \lambda \in (0, 1)$, 有:

$f(\lambda x_1 + (1 - \lambda)x_2) \le \lambda f(x_1) + (1-\lambda)f(x_2)$

则称$f(x)$为凸函数, 若不等号严格成立, 则称为严格凸函数.

相反, 若:

$f(\lambda x_1 + (1 - \lambda)x_2) \ge \lambda f(x_1) + (1-\lambda)f(x_2)$

则称$f(x)$为凹函数, 若不等号严格成立, 则称为严格凹函数.

凸函数与凹函数的直观图像如下图所示.

2. 詹森不等式

已知$f(x)$为定义域$I$上的连续函数, $x_1,x_2,\cdots,x_n$是区间$[a,b]\sube I$内的任意一组实数, $p_1,p_2,\cdots,p_n$为满足条件$\sum\limits_{k=1}^n p_k=1$的一组非负有理实数, 那么:

• 如果$f(x)$为凸函数, 下面的不等式恒成立:

  $f(\sum\limits_{i=1}^n p_ix_i) \le \sum\limits_{i=1}^n p_if(x_i)$

• 如果$f(x)$为凹函数, 下面的不等式恒成立:

  $f(\sum\limits_{i=1}^n p_ix_i) \ge \sum\limits_{i=1}^n p_if(x_i)$

以上两个不等式均为詹森不等式(Jensen Inequation).

因此如果$X=\{x_1,x_2,\cdots,x_n\}$服从概率分布$P$, 即$P(X=x_i)=p_i$, 则詹森不等式等价于:

• 若$f(x)$为凸函数, 不等式$f(E[X]) \le E[f(X)]$恒成立

• 若$f(x)$为凹函数, 不等式$f(E[X]) \le E[f(X)]$恒成立