EM算法及其应用

EM算法简介

首先上一段EM算法的wiki定义:

expectation–maximization (EM) algorithm is an iterative method to find maximum likelihood(MLE) or maximum a posteriori (MAP) estimates of parameters in statistical models, where the model depends on unobserved latent variables.

就是EM算法是: 一种迭代式的算法,用于含有隐变量的概率参数模型的最大似然估计或极大后验概率估计.

网上已经有很多很优秀的博客讲EM算法的了,再次就不赘述了,只复述一些关键性的步骤,相关链接见本文参考部分.

(1) 起因: 给定一系列样本,求解含有隐变量的极大似然估计(MLE)

其中z表示隐变量. 由于隐变量的存在,无法直接使用MLE去求解theta,EM的策略是先建立极大似然函数的下界(E-Step),然后去优化下界逼近原始的极大解(M-Step),不停迭代直到收敛到局部最优解.

(2) 求解: 算法推导

Qi表示隐变量z的分布,需要满足条件:

,比如要将班上学生聚类,假设隐藏变量z是身高,那么Qi就是连续的高斯分布,如果按照隐藏变量是男女,那么就是伯努利分布.

主要是公式2到公式3比较难懂,使用的是Jensen不等式,具体可以看这篇博客有详细的数学解释,此处不赘述.

(3) 结论: 算法总结

公式3表示是对极大似然函数求下界,此时我们假定theta已近给定,通过调整Qi的值使得下界不断的上升去逼近真实值. 当不等式变成等式的时候表示已经调整到和真实值一样的水平了,由Jensen不等式知道此时的随机变量是常数C,即:

进一步推导得到:

得到第一个重要的结论: theta已知的情况下,使得下界提升的Qi就是后验概率,解决了Qi如何选择的问题,其实这就是E-Step.

在找到使得下界提升的Qi之后,固定住Qi,M-Step就是使用MLE极大化此时的下界.

总结下就是:

套路就是: 首先猜下隐类别变量z,之后更新其它参数(theta)

图解就是:

当收敛到theta*时或者||theta(t+1)-theta(t)|| < thresh就可以迭代停止了. 从算法的过程来看,EM算法对初始值敏感同时不能保证收敛到全局最优解. 至于后续的证明EM算法的收敛性,大家看我参考处的相关博客链接或者李航博士的<<统计学习方法>>一书第9章有详细的证明.

EM算法的应用

GMM

GMM(Gaussian Mixture Model)就是指对样本的概率密度(density estimation)分布进行估计,而估计采用的模型是多个高斯模型的加权和,其中的每个高斯模型就代表了一个类(Cluster). 实际分布中可以把模型定义为任何分布的mixture model,为何是高斯混合模型呢? 原因如下两点:

  • 计算比较方便
  • 理论任意多的高斯分布可以近似任意概率分布

问题简化为:

随机变量X是由K个高斯分布混合而成,各个高斯分布的权重(概率)是Φi, 各个高斯分布的均值和方差为μi, ∑i. 观测到随机变量X的一系列样本,估计参数Φ, μ, ∑.

和EM算法之前的引入一样,隐含类别标签用Zi表示,表示样本属于类别Zi,可以假定Zi服从多项式分布,即:

换句话来说就是第j个cluster的权重是Φj.

假设有K个类别(cluster). 假定在给定Zi后,Xi服从高斯分布,即:

联合概率分布是:

故此时的极大似然函数是:

参考EM算法的套路,首先猜测隐类别变量z,然后更新其它参数(Φ, μ, ∑).

Wji表示第i个数据点属于第j个cluster的概率. 具体的Wji的计算可以使用贝叶斯公式:

sklearn中的GMM

API地址在这:GuassianMixture_API 官方的guide是这么介绍的:

The GaussianMixture object implements the expectation-maximization (EM) algorithm for fitting mixture-of-Gaussian models.

可以看出是用EM算法求解的GMM. 官方有个示例, 示例地址是使用EM算法来进行density estimation的.

代码直接粘贴来,如下:

import matplotlib as mpl
import matplotlib.pyplot as plt

import numpy as np

from sklearn import datasets
from sklearn.mixture import GaussianMixture
from sklearn.model_selection import StratifiedKFold

print(__doc__)

colors = ['navy', 'turquoise', 'darkorange']


def make_ellipses(gmm, ax):
    for n, color in enumerate(colors):
        if gmm.covariance_type == 'full':
            covariances = gmm.covariances_[n][:2, :2]
        elif gmm.covariance_type == 'tied':
            covariances = gmm.covariances_[:2, :2]
        elif gmm.covariance_type == 'diag':
            covariances = np.diag(gmm.covariances_[n][:2])
        elif gmm.covariance_type == 'spherical':
            covariances = np.eye(gmm.means_.shape[1]) * gmm.covariances_[n]
        v, w = np.linalg.eigh(covariances)
        u = w[0] / np.linalg.norm(w[0])
        angle = np.arctan2(u[1], u[0])
        angle = 180 * angle / np.pi  # convert to degrees
        v = 2. * np.sqrt(2.) * np.sqrt(v)
        ell = mpl.patches.Ellipse(gmm.means_[n, :2], v[0], v[1],
                                  180 + angle, color=color)
        ell.set_clip_box(ax.bbox)
        ell.set_alpha(0.5)
        ax.add_artist(ell)

iris = datasets.load_iris()

# Break up the dataset into non-overlapping training (75%) and testing
# (25%) sets.
skf = StratifiedKFold(n_splits=4)
# Only take the first fold.
train_index, test_index = next(iter(skf.split(iris.data, iris.target)))


X_train = iris.data[train_index]
y_train = iris.target[train_index]
X_test = iris.data[test_index]
y_test = iris.target[test_index]

n_classes = len(np.unique(y_train))

# Try GMMs using different types of covariances.
estimators = dict((cov_type, GaussianMixture(n_components=n_classes,
                   covariance_type=cov_type, max_iter=20, random_state=0))
                  for cov_type in ['spherical', 'diag', 'tied', 'full'])

n_estimators = len(estimators)

plt.figure(figsize=(3 * n_estimators // 2, 6))
plt.subplots_adjust(bottom=.01, top=0.95, hspace=.15, wspace=.05,
                    left=.01, right=.99)


for index, (name, estimator) in enumerate(estimators.items()):
    # Since we have class labels for the training data, we can
    # initialize the GMM parameters in a supervised manner.
    estimator.means_init = np.array([X_train[y_train == i].mean(axis=0)
                                    for i in range(n_classes)])

    # Train the other parameters using the EM algorithm.
    estimator.fit(X_train)

    h = plt.subplot(2, n_estimators // 2, index + 1)
    make_ellipses(estimator, h)

    for n, color in enumerate(colors):
        data = iris.data[iris.target == n]
        plt.scatter(data[:, 0], data[:, 1], s=0.8, color=color,
                    label=iris.target_names[n])
    # Plot the test data with crosses
    for n, color in enumerate(colors):
        data = X_test[y_test == n]
        plt.scatter(data[:, 0], data[:, 1], marker='x', color=color)

    y_train_pred = estimator.predict(X_train)
    train_accuracy = np.mean(y_train_pred.ravel() == y_train.ravel()) * 100
    plt.text(0.05, 0.9, 'Train accuracy: %.1f' % train_accuracy,
             transform=h.transAxes)

    y_test_pred = estimator.predict(X_test)
    test_accuracy = np.mean(y_test_pred.ravel() == y_test.ravel()) * 100
    plt.text(0.05, 0.8, 'Test accuracy: %.1f' % test_accuracy,
             transform=h.transAxes)

    plt.xticks(())
    plt.yticks(())
    plt.title(name)

plt.legend(scatterpoints=1, loc='lower right', prop=dict(size=12))


plt.show()

代码大意是使用不同的covariance类型({‘full’, ‘tied’, ‘diag’, ‘spherical’}),来观察GMM对iris数据集的聚类效果. iris数据集由150个样本组成,每个样本的特征是4维,3个类别(setosa,versicolor,virginica).

结果如下:

EM还有用在DGM(Bayesian network)中的,这些就比较高深了,暂时还没做了解,以后再补.

参考 1. EM算法在wiki上的解释 2. Jerry Lead的博客 3. zouxy09的博客 4. 一个EM算法的总结 5. GMM模型 6. sina博客介绍的GMM 7. scikit-learn中的GMM

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Phoenix的Android之旅

Java 集合 Vector

List有三种实现,ArrayList, LinkedList, Vector, 它们的区别在于, ArrayList是非线程安全的, Vector则是线程安全...

692
来自专栏开发与安全

算法:AOV网(Activity on Vextex Network)与拓扑排序

在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称之为AOV网(Activity on Vextex ...

3977
来自专栏赵俊的Java专栏

从源码上分析 ArrayList

1211
来自专栏拭心的安卓进阶之路

Java 集合深入理解(12):古老的 Vector

今天刮台风,躲屋里看看 Vector ! 都说 Vector 是线程安全的 ArrayList,今天来根据源码看看是不是这么相...

2537
来自专栏xingoo, 一个梦想做发明家的程序员

20120918-向量实现《数据结构与算法分析》

#include <iostream> #include <list> #include <string> #include <vector> #include...

1836
来自专栏Hongten

ArrayList VS Vector(ArrayList和Vector的区别)_面试的时候经常出现

2182
来自专栏alexqdjay

HashMap 多线程下死循环分析及JDK8修复

1.1K4
来自专栏聊聊技术

原 初学图论-Kahn拓扑排序算法(Kah

2988
来自专栏desperate633

LeetCode Invert Binary Tree题目分析

Invert a binary tree. 4 / \ 2 7 / \ / \1 3 6 9 to4 / \ 7 2 / \ / \9 6 3 1 Tri...

981
来自专栏xingoo, 一个梦想做发明家的程序员

Spark踩坑——java.lang.AbstractMethodError

百度了一下说是版本不一致导致的。于是重新检查各个jar包,发现spark-sql-kafka的版本是2.2,而spark的版本是2.3,修改spark-sql-...

1260

扫码关注云+社区