Maximum Likelihood Estimation (MLE)

  • Estimate the parameters of a probability distribution by maximizing a likelihood function.
    • Under the assumed statistical model, the observed data is most probable.

已知：

  • 概率分布\(D\)的概率密度函数（模型），如\(f(\mu,\sigma^2)\)，但是两个参数未知。
  • 采样样本数据\(x_1,x_2,\cdots, x_n\)。

求解：

  • 模型参数\(\mu,\sigma^2\)估计值。

利用\(f(\mu,\sigma^2)\)，计算样本似然函数：

\[L(\mu,\sigma^2\vert x_1,x_2,\cdots,x_n) = f_{\mu,\sigma^2}(x_1,x_2,\cdots,x_n).\]

where \(f_{\mu,\sigma^2}(x_1,x_2,\cdots,x_n) = \prod_{i=1}^n f_{\mu,\sigma^2}(x_i)\)为样本数据联合分布的概率密度函数，表示在模型参数已知的情况下，得到这组样本数据的概率。

求解使似然函数最大的参数值\(\hat{\mu},\hat{\sigma}^2\)，即为最大似然估计值：

\[\hat{\mu},\hat{\sigma}^2 = \arg\max L(\mu,\sigma^2).\]

为了方便计算，对似然函数取对数：

\[l(\mu,\sigma^2) = \log L(\mu,\sigma^2) = \log \prod_{i=1}^n f_{\mu,\sigma^2}(x_i) = \sum_{i=1}^n\log f_{\mu,\sigma^2}(x_i).\]
  • 对其求导，导数为0，得到似然方程；
  • 解似然方程，得到模型参数估计值。

EM Algorithm

  • 通过样本数据，估计样本的模型参数，最常用的是MLE。
  • 但是，当样本数据中有未知的隐含变量时，无法直接用MLE得到模型参数，此时，需要用EM算法。

思路：

  • 猜想隐含变量（EM中的E）。
  • 基于样本数据和猜测的隐含变量，利用MLE，求解模型参数（EM中的M）。
  • 由于隐含变量是猜测的，所以得到的模型参数并不理想。
  • 基于当前得到的模型参数，继续猜测隐含变量（E）。
  • 以此类推，迭代，直到模型参数无变化，算法收敛。

推导

已知样本数据\(X = \{x_1,x_2,\cdots,x_n\}\)，求解样本的模型参数\(\theta\)，极大化对数似然函数：

\[\hat{\theta} = \arg\max_\theta\sum_{i=1}^n\log f(x_i;\theta).\]

假设样本数据中有隐含变量\(Z = \{z_1,z_2,\cdots,z_n\}\)，此时：

\[\begin{aligned} \hat{\theta} & = \arg\max_\theta\sum_{i=1}^n\log f(x_i;\theta) \\ & = \arg\max_\theta\sum_{i=1}^n\log \sum_Z f(x_i,z_i;\theta). \end{aligned}\]

上式无法直接求解\(\theta\)，对其缩放：

\[\begin{aligned} \sum_{i=1}^n\log \sum_Z f(x_i,z_i;\theta) & = \sum_{i=1}^n\log \sum_Z Q_i(z_i) \frac{f(x_i,z_i;\theta)}{Q_i(z_i)} \\ & \ge \sum_{i=1}^n \sum_Z Q_i(z_i)\log \frac{f(x_i,z_i;\theta)}{Q_i(z_i)}. \end{aligned}\]

其中，利用了Jensen Inequality，因为\(\log\)函数为凹函数，因此\(f(\mathbb{E}[x])\ge \mathbb{E}[f(x)]\)，即：

\[\log\sum_j \lambda_j y_j \ge \sum_j \lambda_j \log y_j, \lambda_j\ge 0, \sum_j \lambda_j = 1.\]

当等号成立时：

\[Q_i(z_i) = \frac{f(x_i,z_i;\theta)}{\sum_Z f(x_i,z_i;\theta)} = \frac{f(x_i,z_i;\theta)}{f(x_i;\theta)} = f(z_i\vert x_i;\theta).\]

因此，

\[\arg\max_\theta \sum_{i=1}^n \sum_Z Q_i(z_i)\log \frac{f(x_i,z_i;\theta)}{Q_i(z_i)}.\]

去掉常数部分，则：

\[\arg\max_\theta \sum_{i=1}^n \sum_Z Q_i(z_i)\log f(x_i,z_i;\theta).\]

算法

  1. Input:
    • 样本数据\(X = {x_1,x_2,\cdots,x_n}\)
    • 联合分布\(f(x,z\vert\theta)\)
    • 条件分布\(f(z\vert x;\theta)\)
    • 最大迭代次数\(J\)
    • 随机初始化模型参数\(\theta_0\)
  2. 开始EM迭代(\(j: 1\to J\))：
    • E：计算联合分布的条件概率期望：
      • \(Q_i(z_i) = f(z_i\vert x_i;\theta_j)\).
      • \(L(\theta,\theta_j) = \sum_{i=1}^n \sum_Z Q_i(z_i)\log f(x_i,z_i;\theta)\).
    • M：极大化\(L(\theta,\theta_j)\):
      • \(\theta_{j+1} = \arg\max L(\theta,\theta_j)\).
    • 如果\(\theta_{j+1}\)收敛，算法结束.
  3. Output: 模型参数\(\theta\).

References