【EM算法简介】
EM算法,全称为期望最大化算法(Expectation-Maximization Algorithm),是一种迭代优化算法,主要用于含有隐变量的概率模型参数的估计。EM算法的基本思想是:如果给定模型的参数,那么可以根据模型计算出隐变量的期望值;反过来,如果给定隐变量的值,那么可以通过最大化似然函数来估计模型的参数。EM算法就是通过交替进行这两步来找到参数的最大似然估计。
EM算法的基本步骤如下:
1. 初始化模型参数
2. E步:计算隐变量的期望值
3. M步:最大化似然函数,更新模型参数
4. 重复步骤2和3,直到模型参数收敛
【EM算法举例】
K-means算法可以被看作是一种特殊的EM算法。在K-means算法中,我们试图找到一种方式将数据点分配到K个集群中,使得每个数据点到其所在集群中心的距离之和最小。
如果我们将集群分配看作是隐变量,那么K-means算法就可以看作是EM算法:
1. E步:期望步骤。给定当前的集群中心(模型参数),我们可以计算每个数据点最近的集群中心,也就是将每个数据点分配到一个集群中。这个步骤就是计算隐变量的期望值。
2. M步:最大化步骤。给定当前的集群分配(隐变量的值),我们可以计算新的集群中心,也就是每个集群中所有数据点的均值。这个步骤就是最大化似然函数,更新模型参数。
通过交替进行E步和M步,K-means算法可以找到一种集群分配和集群中心,使得每个数据点到其所在集群中心的距离之和最小。这就是K-means算法使用EM算法的地方。
【再举一个例子】
见:https://zhuanlan.zhihu.com/p/78311644 写得非常好,关键摘录如下:
【python编程实现】
import math
import random
def coin_em(rolls, theta_A=None, theta_B=None, maxiter=10000, tol=1e-6):
# 初始化参数
theta_A = theta_A or random.random()
theta_B = theta_B or random.random()
loglike_old = 0
for i in range(maxiter):
# E步
heads_A, tails_A, heads_B, tails_B = e_step(rolls, theta_A, theta_B)
# M步
theta_A, theta_B = m_step(heads_A, tails_A, heads_B, tails_B)
# 计算对数似然
loglike_new = loglikelihood(rolls, theta_A, theta_B)
# 检查收敛
if abs(loglike_new - loglike_old) < tol:
break
else:
loglike_old = loglike_new
return theta_A, theta_B
def e_step(rolls, theta_A, theta_B):
heads_A, tails_A, heads_B, tails_B = 0, 0, 0, 0
for trial in rolls:
likelihood_A = likelihood(trial, theta_A)
likelihood_B = likelihood(trial, theta_B)
p_A = likelihood_A / (likelihood_A + likelihood_B)
p_B = 1 - p_A
heads_A += p_A * trial.count("H")
tails_A += p_A * trial.count("T")
heads_B += p_B * trial.count("H")
tails_B += p_B * trial.count("T")
return heads_A, tails_A, heads_B, tails_B
def m_step(heads_A, tails_A, heads_B, tails_B):
theta_A = heads_A / (heads_A + tails_A)
theta_B = heads_B / (heads_B + tails_B)
return theta_A, theta_B
def likelihood(roll, theta):
numHeads = roll.count("H")
flips = len(roll)
return (theta**numHeads) * ((1-theta)**(flips-numHeads))
def loglikelihood(rolls, theta_A, theta_B):
total = 0
for roll in rolls:
heads = roll.count("H")
tails = roll.count("T")
total += math.log(0.5 * likelihood(roll, theta_A) + 0.5 * likelihood(roll, theta_B))
return total
# 测试
rolls = ["HTTTHHTHTH", "HHHHTHHHHH", "HTHHHHHTHH", "HTHTTTHHTT", "THHHTHHHTH"]
print(coin_em(rolls))
输出:
(0.7967659656145668, 0.5195829299707858)
和原始答案比较接近。