一、机器学习中的参数估计问题

在前面的博文中，如“简单易学的机器学习算法——Logistic回归”中，采用了极大似然函数对其模型中的参数进行估计，简单来讲即对于一系列样本 $简单易学的机器学习算法——EM算法$ ，Logistic回归问题属于监督型学习问题，样本中含有训练的特征 $简单易学的机器学习算法——EM算法$ 以及标签 $简单易学的机器学习算法——EM算法$ ，在Logistic回归的参数求解中，通过构造样本属于类别 $简单易学的机器学习算法——EM算法$ 和类别 $简单易学的机器学习算法——EM算法$ 的概率：

$简单易学的机器学习算法——EM算法$

这样便能得到Logistic回归的属于不同类别的概率函数：

$简单易学的机器学习算法——EM算法$

此时，使用极大似然估计便能够估计出模型中的参数。但是，如果此时的标签 $简单易学的机器学习算法——EM算法$ 是未知的，称为隐变量，如无监督的学习问题，典型的如K-Means聚类算法，此时不能直接通过极大似然估计估计出模型中的参数。

二、EM算法简介

在上述存在隐变量的问题中，不能直接通过极大似然估计求出模型中的参数，EM算法是一种解决存在隐含变量优化问题的有效方法。EM算法是期望极大(Expectation Maximization)算法的简称，EM算法是一种迭代型的算法，在每一次的迭代过程中，主要分为两步：即求期望(Expectation)步骤和最大化(Maximization)步骤。

三、EM算法推导的准备

1、凸函数

设 $简单易学的机器学习算法——EM算法$ 是定义在实数域上的函数，如果对于任意的实数 $简单易学的机器学习算法——EM算法$ ，都有

$简单易学的机器学习算法——EM算法$

那么 $简单易学的机器学习算法——EM算法$ 是凸函数。若 $简单易学的机器学习算法——EM算法$ 不是单个实数，而是由实数组成的向量，此时，如果函数 $简单易学的机器学习算法——EM算法$ 的Hesse矩阵 $简单易学的机器学习算法——EM算法$ 是半正定的，即

$简单易学的机器学习算法——EM算法$

那么 $简单易学的机器学习算法——EM算法$ 是凸函数。特别地，如果 $简单易学的机器学习算法——EM算法$ 或者 $简单易学的机器学习算法——EM算法$ ，那么称 $简单易学的机器学习算法——EM算法$ 为严格凸函数。

2、Jensen不等式

如果函数 $简单易学的机器学习算法——EM算法$ 是凸函数， $简单易学的机器学习算法——EM算法$ 是随机变量，那么

$简单易学的机器学习算法——EM算法$

特别地，如果函数 $简单易学的机器学习算法——EM算法$ 是严格凸函数，那么 $简单易学的机器学习算法——EM算法$ 当且仅当

$简单易学的机器学习算法——EM算法$

即随机变量 $简单易学的机器学习算法——EM算法$ 是常量。

简单易学的机器学习算法——EM算法

(图片来自参考文章1)

注：若函数 $简单易学的机器学习算法——EM算法$ 是凹函数，上述的符号相反。

3、数学期望

3.1随机变量的期望

设离散型随机变量 $简单易学的机器学习算法——EM算法$ 的概率分布为：

$简单易学的机器学习算法——EM算法$

其中， $简单易学的机器学习算法——EM算法$ ，如果 $简单易学的机器学习算法——EM算法$ 绝对收敛，则称 $简单易学的机器学习算法——EM算法$ 为 $简单易学的机器学习算法——EM算法$ 的数学期望，记为 $简单易学的机器学习算法——EM算法$ ，即：

$简单易学的机器学习算法——EM算法$

若连续型随机变量 $简单易学的机器学习算法——EM算法$ 的概率密度函数为 $简单易学的机器学习算法——EM算法$ ，则数学期望为：

$简单易学的机器学习算法——EM算法$

3.2随机变量函数的数学期望

设 $简单易学的机器学习算法——EM算法$ 是随机变量 $简单易学的机器学习算法——EM算法$ 的函数，即 $简单易学的机器学习算法——EM算法$ ，若 $简单易学的机器学习算法——EM算法$ 是离散型随机变量，概率分布为：

$简单易学的机器学习算法——EM算法$

则：

$简单易学的机器学习算法——EM算法$

若 $简单易学的机器学习算法——EM算法$ 是连续型随机变量，概率密度函数为 $简单易学的机器学习算法——EM算法$ ，则

$简单易学的机器学习算法——EM算法$

四、EM算法的求解过程

假设 $简单易学的机器学习算法——EM算法$ 表示观测变量， $简单易学的机器学习算法——EM算法$ 表示潜变量，则此时 $简单易学的机器学习算法——EM算法$ 即为完全数据， $简单易学的机器学习算法——EM算法$ 的似然函数为 $简单易学的机器学习算法——EM算法$ ，其中， $简单易学的机器学习算法——EM算法$ 为需要估计的参数，那么对于完全数据， $简单易学的机器学习算法——EM算法$ 的似然函数为 $简单易学的机器学习算法——EM算法$ 。

构建好似然函数，对于给定的观测数据，为了估计参数 $简单易学的机器学习算法——EM算法$ ，我们可以使用极大似然估计的方法对其进行估计。因为变量 $简单易学的机器学习算法——EM算法$ 是未知的，我们只能对 $简单易学的机器学习算法——EM算法$ 的似然函数为 $简单易学的机器学习算法——EM算法$ 进行极大似然估计，即需要极大化：

$简单易学的机器学习算法——EM算法$

上述式子中无法直接对 $简单易学的机器学习算法——EM算法$ 求极大值，因为在函数中存在隐变量 $简单易学的机器学习算法——EM算法$ ，即未知变量。若此时，我们能够确定隐变量 $简单易学的机器学习算法——EM算法$ 的值，便能够求出 $简单易学的机器学习算法——EM算法$ 的极大值，可以用过不断的修改隐变量 $简单易学的机器学习算法——EM算法$ 的值，得到新的 $简单易学的机器学习算法——EM算法$ 的极大值。这便是EM算法的思路。通过迭代的方式求出参数 $简单易学的机器学习算法——EM算法$ 。

首先我们需要对参数 $简单易学的机器学习算法——EM算法$ 赋初值，进行迭代运算，假设第 $简单易学的机器学习算法——EM算法$ 次迭代后参数 $简单易学的机器学习算法——EM算法$ 的值为 $简单易学的机器学习算法——EM算法$ ，此时的log似然函数为 $简单易学的机器学习算法——EM算法$ ，即：

$简单易学的机器学习算法——EM算法$

在上式中，第二行到第三行使用到了Jensen不等式，由于log函数是凹函数，由Jensen不等式得到：

$简单易学的机器学习算法——EM算法$

而

$简单易学的机器学习算法——EM算法$

表示的是 $简单易学的机器学习算法——EM算法$ 的期望，其中， $简单易学的机器学习算法——EM算法$ 表示的是隐变量 $简单易学的机器学习算法——EM算法$ 满足的某种分布。这样，上式 $简单易学的机器学习算法——EM算法$ 的值取决于 $简单易学的机器学习算法——EM算法$ 和 $简单易学的机器学习算法——EM算法$ 的概率。在迭代的过程中，调整这两个概率，使得下界不断的上升，这样就能求得 $简单易学的机器学习算法——EM算法$ 的极大值。注意，当等式成立时，说明此时已经等价于 $简单易学的机器学习算法——EM算法$ 。由Jensen不等式可知，等式成立的条件是随机变量是常数，即：

$简单易学的机器学习算法——EM算法$

已知：

$简单易学的机器学习算法——EM算法$

所以：

$简单易学的机器学习算法——EM算法$

则：

$简单易学的机器学习算法——EM算法$

至此，我们得出了隐变量 $简单易学的机器学习算法——EM算法$ 满足的分布的形式 $简单易学的机器学习算法——EM算法$ 。这就是EM算法中的E步。在确定了 $简单易学的机器学习算法——EM算法$ 后，调整参数 $简单易学的机器学习算法——EM算法$ 使得 $简单易学的机器学习算法——EM算法$ 取得极大，这便是M步。EM算法的步骤为：

初始化参数 $简单易学的机器学习算法——EM算法$ ，开始迭代；
E步：假设 $简单易学的机器学习算法——EM算法$ 为第 $简单易学的机器学习算法——EM算法$ 次迭代参数 $简单易学的机器学习算法——EM算法$ 的估计值，则在第 $简单易学的机器学习算法——EM算法$ 次迭代中，计算 $简单易学的机器学习算法——EM算法$ ： $简单易学的机器学习算法——EM算法$
M步：求使 $简单易学的机器学习算法——EM算法$ 极大化的 $简单易学的机器学习算法——EM算法$ ，确定第 $简单易学的机器学习算法——EM算法$ 次的参数的估计值 $简单易学的机器学习算法——EM算法$ ： $简单易学的机器学习算法——EM算法$

五、EM算法的收敛性保证

迭代的过程能否保证最后找到的就是最大的似然函数值呢？即需要证明在整个迭代的过程中，极大似然估计是单调增加的。假定 $简单易学的机器学习算法——EM算法$ 和 $简单易学的机器学习算法——EM算法$ 是EM算法的第 $简单易学的机器学习算法——EM算法$ 次和第 $简单易学的机器学习算法——EM算法$ 次迭代后的结果，选定 $简单易学的机器学习算法——EM算法$ ，进行迭代：

E步： $简单易学的机器学习算法——EM算法$
M步： $简单易学的机器学习算法——EM算法$

固定 $简单易学的机器学习算法——EM算法$ ，将 $简单易学的机器学习算法——EM算法$ 看成变量：

$简单易学的机器学习算法——EM算法$

上式中，第一个大于等于是因为：

$简单易学的机器学习算法——EM算法$

六、利用EM算法参数求解实例

假设有有一批数据 $简单易学的机器学习算法——EM算法$ 分别是由两个正态分布：

$简单易学的机器学习算法——EM算法$

产生，其中， $简单易学的机器学习算法——EM算法$ 和 $简单易学的机器学习算法——EM算法$ 未知， $简单易学的机器学习算法——EM算法$ 。但是不知道具体的 $简单易学的机器学习算法——EM算法$ 是第产生，即可以使用 $简单易学的机器学习算法——EM算法$ 和 $简单易学的机器学习算法——EM算法$ 表示。这是一个典型的涉及到隐藏变量的例子，隐藏变量为 $简单易学的机器学习算法——EM算法$ 和 $简单易学的机器学习算法——EM算法$ 。可以使用EM算法对参数进行估计。

首先是初始化 $简单易学的机器学习算法——EM算法$ 和 $简单易学的机器学习算法——EM算法$ ；
E步： $简单易学的机器学习算法——EM算法$ ，即求数据 $简单易学的机器学习算法——EM算法$ 是由第 $简单易学的机器学习算法——EM算法$ 个分布产生的概率： $简单易学的机器学习算法——EM算法$
M步： $简单易学的机器学习算法——EM算法$ ，即计算最大的期望值。然而我们要求的参数是均值，可以通过如下的方式估计： $简单易学的机器学习算法——EM算法$

Python代码

#coding:UTF-8
'''''
Created on 2015年6月7日
@author: zhaozhiyong
'''
from __future__ import division
from numpy import *
import math as mt
#首先生成一些用于测试的样本
#指定两个高斯分布的参数，这两个高斯分布的方差相同
sigma = 6
miu_1 = 40
miu_2 = 20
#随机均匀选择两个高斯分布，用于生成样本值
N = 1000
X = zeros((1, N))
for i in xrange(N):
if random.random() > 0.5:#使用的是numpy模块中的random
X[0, i] = random.randn() * sigma + miu_1
else:
X[0, i] = random.randn() * sigma + miu_2
#上述步骤已经生成样本
#对生成的样本，使用EM算法计算其均值miu
#取miu的初始值
k = 2
miu = random.random((1, k))
#miu = mat([40.0, 20.0])
Expectations = zeros((N, k))
for step in xrange(1000):#设置迭代次数
#步骤1，计算期望
for i in xrange(N):
#计算分母
denominator = 0
for j in xrange(k):
denominator = denominator + mt.exp(-1 / (2 * sigma ** 2) * (X[0, i] - miu[0, j]) ** 2)
#计算分子
for j in xrange(k):
numerator = mt.exp(-1 / (2 * sigma ** 2) * (X[0, i] - miu[0, j]) ** 2)
Expectations[i, j] = numerator / denominator
#步骤2，求期望的最大
#oldMiu = miu
oldMiu = zeros((1, k))
for j in xrange(k):
oldMiu[0, j] = miu[0, j]
numerator = 0
denominator = 0
for i in xrange(N):
numerator = numerator + Expectations[i, j] * X[0, i]
denominator = denominator + Expectations[i, j]
miu[0, j] = numerator / denominator
#判断是否满足要求
epsilon = 0.0001
if sum(abs(miu - oldMiu)) < epsilon:
break
print step
print miu
print miu

最终结果

[[ 40.49487592 19.96497512]]

参考文章：

1、(EM算法)The EM Algorithm (http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html)

2、数学期望(http://wenku.baidu.com/view/915a9c1ec5da50e2524d7f08.html?re=view)

秒客网

简单易学的机器学习算法——EM算法

一、机器学习中的参数估计问题

二、EM算法简介

三、EM算法推导的准备

1、凸函数

2、Jensen不等式

3、数学期望

3.1随机变量的期望

3.2随机变量函数的数学期望

四、EM算法的求解过程

五、EM算法的收敛性保证

六、利用EM算法参数求解实例

相关文章