EM 算法

  1. 如果概率模型的变量都是观测变量,则给定数据之后,可以直接用极大似然估计法或者贝叶斯估计法来估计模型参数。

    但是当模型含有隐变量时,就不能简单的使用这些估计方法。此时需要使用EM 算法。

    • EM 算法是一种迭代算法。
    • EM 算法专门用于含有隐变量的概率模型参数的极大似然估计,或者极大后验概率估计。
  2. EM算法的每次迭代由两步组成:

    • E步求期望。
    • M步求极大。

    所以EM算法也称为期望极大算法。

一、示例

1.1 身高抽样问题

  1. 假设学校所有学生中,男生身高服从正态分布 , 女生身高服从正态分布

    现在随机抽取200名学生,得到这些学生的身高 ,求参数 的估计。

  2. 定义隐变量为 ,其取值为 ,分别表示男生、女生

    • 如果隐变量是已知的,即已知每个学生是男生还是女生 ,则问题很好解决:

      • 统计所有男生的身高的均值和方差,得到

        其中 表示满足 构成的集合。 分别表示平均值和方差。

      • 统计所有女生的身高的均值和方差,得到

        其中 表示满足 构成的集合。 分别表示平均值和方差。

    • 如果已知参数 ,则任意给出一个学生的身高 ,可以知道该学生分别为男生/女生的概率。

      则有: 。因此也就知道该学生更可能为男生,还是更可能为女生。

    因此:参数 学生是男生/女生,这两个问题是相互依赖,相互纠缠的。

  3. 为解决该问题,通常采取下面步骤:

    • 先假定参数的初始值:

    • 迭代 :

      • 根据 来计算每个学生更可能是属于男生,还是属于女生。

        这一步为E 步(Expectation),用于计算隐变量的后验分布

      • 根据上一步的划分,统计所有男生的身高的均值和方差,得到 ;统计所有女生的身高的均值和方差,得到

        这一步为 M 步(Maximization ),用于通过最大似然函数求解正态分布的参数。

      • 当前后两次迭代的参数变化不大时,迭代终止。

1.2 三硬币模型

  1. 已知三枚硬币 ABC ,这些硬币正面出现的概率分别为 。进行如下试验:

    • 先投掷硬币 A,若是正面则选硬币 B;若是反面则选硬币 C
    • 然后投掷被选出来的硬币,投掷的结果如果是正面则记作 1;投掷的结果如果是反面则记作0
    • 独立重复地 次试验,观测结果为: 1,1,0,1,0,...0,1

    现在只能观测到投掷硬币的结果,无法观测投掷硬币的过程,求估计三硬币正面出现的概率。

  2. 设:

    • 随机变量 是观测变量,表示一次试验观察到的结果,取值为 1 或者0
    • 随机变量 是隐变量,表示未观测到的投掷A硬币的结果,取值为 1 或者 0
    • 是模型参数

    则:

    注意:随机变量 的数据可以观测,随机变量 的数据不可观测

  3. 将观测数据表示为 ,未观测数据表示为

    由于每次试验之间都是独立的,则有:

  4. 考虑求模型参数 的极大似然估计,即:

    这个问题没有解析解,只有通过迭代的方法求解,EM算法就是可以用于求解该问题的一种迭代算法。

  5. EM算法求解:

    首先选取参数的初值,记作 ,然后通过下面的步骤迭代计算参数的估计值,直到收敛为止:

    设第 次迭代参数的估计值为: , 则EM算法的第 次迭代如下:

    • E步:计算模型在参数 下,观测数据 来自于投掷硬币 B 的概率:

      它其实就是 ,即:已知观测变量 的条件下,观测数据 来自于投掷硬币 B 的概率。

    • M 步:计算模型参数的新估计值:

      • 第一个式子:通过后验概率 估计值的均值作为先验概率 的估计。
      • 第二个式子:通过条件概率 的估计来求解先验概率 的估计。
      • 第三个式子:通过条件概率 的估计来求解先验概率 的估计。
  6. EM 算法的解释:

    • 初始化:随机选择三枚硬币 ABC 正面出现的概率 的初始值

    • E 步:在已知概率 的情况下,求出每个观测数据 是来自于投掷硬币 B 的概率。即:

      于是对于 次实验,就知道哪些观测数据是由硬币 B 产生,哪些是由硬币 C 产生。

    • M 步:在已知哪些观测数据是由硬币 B 产生,哪些是由硬币 C 产生的情况下:

      • 就等于硬币 B 产生的次数的频率。
      • 就等于硬币B 产生的数据中,正面向上的频率。
      • 就等于硬币 C 产生的数据中,正面向上的频率。

二、EM算法原理

2.1 观测变量和隐变量

  1. 表示观测随机变量, 表示对应的数据序列;令 表示隐随机变量, 表示对应的数据序列。

    连在一起称作完全数据,观测数据 又称作不完全数据。

  2. 假设给定观测随机变量 ,其概率分布为 ,其中 是需要估计的模型参数,则不完全数据 的似然函数是 , 对数似然函数为

    假定 的联合概率分布是 ,完全数据的对数似然函数是 ,则根据每次观测之间相互独立,有:

  3. 由于 发生,根据最大似然估计,则需要求解对数似然函数:

    的极大值。其中 表示对所有可能的 求和,因为边缘分布

    该问题的困难在于:该目标函数包含了未观测数据的的分布的积分和对数。

2.2 EM算法

2.2.1 原理

  1. EM 算法通过迭代逐步近似极大化

    假设在第 次迭代后, 的估计值为: 。则希望 新的估计值能够使得 增加,即:

    为此考虑两者的差:

    这里 已知,所以 可以直接计算得出。

  2. Jensen 不等式:如果 是凸函数, 为随机变量,则有:

    • 如果 是严格凸函数,当且仅当 是常量时,等号成立。

      jensen

    • 满足 时,将 视作概率分布。

      设随机变量 满足概率分布 ,则有:

  3. 考虑到条件概率的性质,则有 。因此有:

    等号成立时,需要满足条件:

    其中 为随机变量 的取值个数。

  4. 令 :

    则有: ,因此 的一个下界。

    • 根据定义有: 。因为此时有:

    • 任何可以使得 增大的 ,也可以使 增大。

      为了使得 尽可能增大,则选择使得 取极大值的

  5. 求极大值:

    其中: 无关,因此省略。

2.2.2 算法

  1. EM 算法:

    • 输入:

      • 观测变量数据
      • 联合分布 ,以及条件分布

      联合分布和条件分布的形式已知(比如说高斯分布等),但是参数未知(比如均值、方差)

    • 输出:模型参数

    • 算法步骤:

      • 选择参数的初值 ,开始迭代。

      • E步:记 为第 次迭代参数 的估计值,在第 步迭代的 E 步,计算:

        其中 表示:对于观测点 关于后验概率 的期望。

      • M步:求使得 最大化的 ,确定 次迭代的参数的估计值

      • 重复上面两步,直到收敛。

  2. 通常收敛的条件是:给定较小的正数 ,满足: 或者

  3. 是算法的核心,称作 函数。其中:

    • 第一个符号表示要极大化的参数(未知量)。
    • 第二个符号表示参数的当前估计值(已知量)。
  4. EM算法的直观理解:EM算法的目标是最大化对数似然函数

    • 直接求解这个目标是有问题的。因为要求解该目标,首先要得到未观测数据的分布 。如:身高抽样问题中,已知身高,需要知道该身高对应的是男生还是女生。

      但是未观测数据的分布就是待求目标参数 的解的函数。这是一个“鸡生蛋-蛋生鸡” 的问题。

    • EM算法试图多次猜测这个未观测数据的分布

      每一轮迭代都猜测一个参数值 ,该参数值都对应着一个未观测数据的分布 。如:已知身高分布的条件下,男生/女生的分布。

    • 然后通过最大化某个变量来求解参数值。这个变量就是 变量,它是真实的似然函数的下界 。

      • 如果猜测正确,则 就是真实的似然函数。
      • 如果猜测不正确,则 就是真实似然函数的一个下界。
  5. 隐变量估计问题也可以通过梯度下降法等算法求解,但由于求和的项数随着隐变量的数目以指数级上升,因此代价太大。

    • EM算法可以视作一个非梯度优化算法。
    • 无论是梯度下降法,还是EM 算法,都容易陷入局部极小值。

2.2.3 收敛性定理

  1. 定理一:设 为观测数据的似然函数,EM算法得到的参数估计序列, 为对应的似然函数序列,其中

    则: 是单调递增的,即:

  2. 定理二:设 为观测数据的对数似然函数, EM算法得到的参数估计序列, 为对应的对数似然函数序列,其中

    • 如果 有上界,则 会收敛到某一个值

    • 在函数 满足一定条件下,由 EM 算法得到的参数估计序列 的收敛值 的稳定点。

      关于“满足一定条件”:大多数条件下其实都是满足的。

  3. 定理二只能保证参数估计序列收敛到对数似然函数序列的稳定点 ,不能保证收敛到极大值点。

  4. EM算法的收敛性包含两重意义:

    • 关于对数似然函数序列 的收敛。
    • 关于参数估计序列 的收敛。

    前者并不蕴含后者。

  5. 实际应用中,EM 算法的参数的初值选择非常重要。

    • 参数的初始值可以任意选择,但是 EM 算法对初值是敏感的,选择不同的初始值可能得到不同的参数估计值。
    • 常用的办法是从几个不同的初值中进行迭代,然后对得到的各个估计值加以比较,从中选择最好的(对数似然函数最大的那个)。
  6. EM 算法可以保证收敛到一个稳定点,不能保证得到全局最优点。其优点在于:简单性、普适性。

三、EM算法与高斯混合模型

3.1 高斯混合模型

  1. 高斯混合模型(Gaussian mixture model,GMM):指的是具有下列形式的概率分布模型:

    其中 是系数,满足 :

    • 是高斯分布密度函数,称作第 个分模型,
  2. 如果用其他的概率分布密度函数代替上式中的高斯分布密度函数,则称为一般混合模型。

3.2 参数估计

  1. 假设观察数据 由高斯混合模型 生成,其中

    可以通过EM算法估计高斯混合模型的参数

  2. 可以设想观察数据 是这样产生的:

    • 首先以概率 选择第 个分模型
    • 然后以第 个分模型的概率分布 生成观察数据

    这样,观察数据 是已知的,观测数据 来自哪个分模型是未知的。

    对观察变量 ,定义隐变量 ,其中

  3. 完全数据的对数似然函数为:

    其对数为:

    后验概率为:

    即:

    函数为:

    求极大值:

    根据偏导数为 0,以及 得到:

    • 其中: ,其物理意义为:所有的观测数据 中,产生自第 个分模型的观测数据的数量。

    • 其中: ,其物理意义为:所有的观测数据 中,产生自第 个分模型的观测数据的总和。

    • 其中: ,其物理意义为:所有的观测数据 中,产生自第 个分模型的观测数据,偏离第 个模型的均值( )的平方和。

  4. 高斯混合模型参数估计的EM算法:

    • 输入:

      • 观察数据
      • 高斯混合模型的分量数
    • 输出:高斯混合模型参数

    • 算法步骤:

      • 随机初始化参数

      • 根据 迭代求解 ,停止条件为:对数似然函数值或者参数估计值收敛。

        其中:

        • 其物理意义为:所有的观测数据 中,产生自第 个分模型的观测数据的数量。

        • 其物理意义为:所有的观测数据 中,产生自第 个分模型的观测数据的总和。

        • 其物理意义为:所有的观测数据 中,产生自第 个分模型的观测数据,偏离第 个模型的均值( )的平方和。

四、EM 算法与 kmeans 模型

  1. kmeans算法:给定样本集 , 针对聚类所得簇划分 , 最小化平方误差:

    其中 是簇 的均值向量。

  2. 定义观测随机变量为 ,观测数据为 。定义隐变量为 ,它表示 所属的簇的编号。设参数 , 则考虑如下的生成模型:

    其中 表示距离 最近的中心点所在的簇编号。即:

    • 最近的簇就是 代表的簇,则生成概率为
    • 最近的簇不是 代表的簇,则生成概率等于 0 。
  3. 计算后验概率:

    即:

    • 最近的簇就是 代表的簇,则后验概率为 1 。
    • 最近的簇不是 代表的簇,则后验概率为 0 。
  4. 计算 函数:

    设距离 最近的聚类中心为 ,即它属于簇 ,则有:

    则有:

    定义集合 ,它表示属于簇 的样本的下标集合。则有:

    则有:

    这刚好就是 k-means 算法的目标:最小化平方误差。

  5. 由于求和的每一项都是非负的,则当每一个内层求和 都最小时,总和最小。即:

    得到:,其中 表示集合 的大小。

    这就是求平均值来更新簇中心。

五、EM 算法的推广

5.1 F 函数

  1. F函数:假设隐变量 的概率分布为 ,定义分布 与参数 的函数 为:

    其中 是分布 的熵。

    通常假定 的连续函数,因此 的连续函数。

  2. 函数 有下列重要性质:

    • 对固定的 ,存在唯一的分布 使得极大化 。此时 ,并且 随着 连续变化。
    • , 则
  3. 定理一:设 为观测数据的对数似然函数, EM 算法得到的参数估计序列,函数 ,则:

    • 如果 有局部极大值,那么 也在 有局部极大值。
    • 如果 有全局极大值,那么 也在 有全局极大值。
  4. 定理二:EM算法的一次迭代可由 F 函数的极大-极大算法实现:设 为第 次迭代参数 的估计, 为第 次迭代函数 的估计。在第 次迭代的两步为:

    • 对固定的 ,求 使得 极大化。
    • 对固定的 ,求 使得 极大化。

5.2 GEM算法1

  1. GEM算法1(EM算法的推广形式):

    • 输入:

      • 观测数据
      • 函数
    • 输出:模型参数

    • 算法步骤:

      • 初始化参数 ,开始迭代。

      • 次迭代:

        • 为参数 的估计值, 为函数 的估计值。求 使得 极大化。
        • 使得 极大化。
        • 重复上面两步直到收敛。
  2. 该算法的问题是,有时候求 极大化很困难。

5.3 GEM算法2

  1. GEM算法2(EM算法的推广形式):

    • 输入:

      • 观测数据
      • 函数
    • 输出:模型参数

    • 算法步骤:

      • 初始化参数 ,开始迭代。

      • 次迭代:

        • 为参数 的估计值, 计算

        • 使得

        • 重复上面两步,直到收敛。

  2. 此算法不需要求 的极大值,只需要求解使它增加的 即可。

5.4 GEM算法3

  1. GEM算法3(EM算法的推广形式):

    • 输入:

      • 观测数据
      • 函数
    • 输出:模型参数

    • 算法步骤:

      • 初始化参数 ,开始迭代

      • 次迭代:

        • 为参数 的估计值, 计算

        • 进行 次条件极大化:

          • 首先在 保持不变的条件下求使得 达到极大的
          • 然后在 的条件下求使得 达到极大的
          • 如此继续,经过 次条件极大化,得到 ,使得
        • 重复上面两步,直到收敛。

  2. 该算法将 EM 算法的 M 步分解为 次条件极大化,每次只需要改变参数向量的一个分量,其余分量不改变。