EM Algorithm
- 格式：pptx
- 大小：668.33 KB
- 文档页数：35
下载文档原格式
合集下载
matlab练习程序（EM算法）
matlab练习程序（EM算法）最⼤期望算法（Expectation-maximization algorithm，⼜译为期望最⼤化算法），是在概率模型中寻找参数最⼤似然估计或者最⼤后验估计的算法，其中概率模型依赖于⽆法观测的隐性变量。
最⼤期望算法经过两个步骤交替进⾏计算：第⼀步是计算期望（E），利⽤对隐藏变量的现有估计值，计算其最⼤似然估计值；第⼆步是最⼤化（M），最⼤化在E步上求得的最⼤似然值来计算参数的值。
M步上找到的参数估计值被⽤于下⼀个E步计算中，这个过程不断交替进⾏。
下⾯⽤EM算法对⾼斯混合模型进⾏聚类，该算法不仅能够给出聚类后数据的均值，还能够给出协⽅差。
代码如下：clear all;close all;clc;mu1=[00];S1=[0.80.1];data1=mvnrnd(mu1,S1,1000);plot(data1(:,1),data1(:,2),'r.');hold on;mu2=[24];S2=[0.41.3];data2=mvnrnd(mu2,S2,1000);plot(data2(:,1),data2(:,2),'g.');mu3=[-23];S3=[2.41.3];data3=mvnrnd(mu3,S3,1000);plot(data3(:,1),data3(:,2),'b.');%利⽤EM算法对⾼斯混合模型聚类data=[data1;data2;data3];mu{1} = rand(1,2);mu{2} = rand(1,2);mu{3} = rand(1,2);sigma{1} = rand(1,2);sigma{2} = rand(1,2);sigma{3} = rand(1,2);p = [0.30.40.4];w=zeros(length(data),3);for i=1:1000%E-stepfor j=1:3w(:,j) = p(j)*mvnpdf(data,mu{j},sigma{j});endw = w./repmat(sum(w,2),[13]);%M-stepfor j=1:3mu{j} = w(:,j)'* data / sum(w(:,j));sigma{j} = sqrt(w(:,j)'*((data-mu{j}).*(data-mu{j})) / sum(w(:,j)));endp = sum(w) / length(data);endfigure;w = uint8(w);data1 = data(w(:,1)==1,:);data2 = data(w(:,2)==1,:);data3 = data(w(:,3)==1,:);plot(data1(:,1),data1(:,2),'r.');hold on;plot(data2(:,1),data2(:,2),'g.');plot(data3(:,1),data3(:,2),'b.');结果：原始⾼斯数据：聚类后：。
基于EM算法的多种训练方式的比较分析
基于EM算法的多种训练方式的比较分析EM算法，全称Expectation-Maximization Algorithm，是一种常用的似然函数最大化的迭代算法。
EM算法广泛应用于机器学习、数据挖掘等领域中的参数估计问题。
在许多应用中，使用EM算法得到的结果往往优于其他常见的参数估计方法，例如最大似然估计和贝叶斯估计。
EM算法的核心思想是通过迭代更新参数，不断提高观测数据的似然度。
算法分为两个步骤：E步骤和M步骤。
在E步骤中，通过已知参数计算每个观测数据属于每个隐变量的概率值。
在M步骤中，通过已知数据的权重和隐变量的概率值，更新参数，求出新的参数估计值。
整个算法通过不断重复这两个步骤，从而得到最终的参数估计值。
在EM算法的应用中，我们常常需要使用多种不同的训练方式。
这些训练方式基于不同的假设和理论基础，可以为我们提供更多的模型选择和优化的机会。
在接下来的文章中，我们将介绍几种不同的基于EM算法的训练方式，并对它们的优缺点进行比较分析。
第一种训练方式：Batch EM训练Batch EM训练是一种传统的EM训练方式，也是许多应用中最常用的训练方式。
在Batch EM训练中，算法在每一次迭代中使用所有的训练数据。
这种训练方式在数据量较小或者计算资源充足的情况下表现良好，但是在数据量较大，计算资源有限的情况下，迭代收敛速度较慢且容易出现过拟合。
第二种训练方式：Stochastic EM训练Stochastic EM训练是一种改进版的EM训练方式。
在Stochastic EM训练中，算法在每一次迭代中只随机选取一小部分数据进行计算，从而加速算法的收敛速度。
这种训练方式在大规模数据集和计算资源不充足的情况下表现良好，但是由于每次随机选择的数据不同，因此可能导致算法的收敛方向不稳定，容易陷入局部最优解。
第三种训练方式：Minibatch EM训练Minibatch EM训练是Stochastic EM训练的进一步改进。
多元正态分布的em算法推导
多元正态分布的EM算法推导引言EM (Expectation-Maximization) 算法是一种常用的统计学习算法，用于在存在隐变量的情况下估计参数。
在本文中，我们将重点讨论多元正态分布的EM算法推导。
多元正态分布是一种常用的概率模型，广泛应用于数据分析和机器学习中。
多元正态分布多元正态分布是指具有多个连续随机变量的概率分布。
对于一个d维的多元正态分布，其概率密度函数可以表示为：=(-(x-)T{-1}(x-)))其中，x是一个d维向量，表示观测值；μ是一个d维向量，表示均值向量；Σ是一个d×d的协方差矩阵。
EM算法推导EM算法是一种通过迭代优化似然函数来估计参数的方法。
对于多元正态分布的EM算法，我们需要首先给出观测数据的生成模型。
假设我们有n个观测样本x1, x2, …, xn，每个样本都是一个d维向量。
我们的目标是估计多元正态分布的参数，即均值向量μ和协方差矩阵Σ。
E步骤在E步骤中，我们需要计算隐变量的后验概率。
对于多元正态分布，我们引入隐变量z表示每个观测样本的类别。
假设有k个类别，那么z可以取值为1, 2, …, k。
我们定义隐变量z的后验概率为γij，表示第i个观测样本属于第j个类别的概率。
根据贝叶斯定理，我们有：}{_{l=1}^k_lp(x_i;_l,_l)})其中，πj表示第j个类别的先验概率，满足∑j=1kπj=1。
我们可以通过计算后验概率γij来得到隐变量的期望。
具体地，对于第i个观测样本，我们可以计算其属于第j个类别的期望为：={j=1}^k{ij})M步骤在M步骤中，我们需要通过最大化隐变量的期望来更新参数。
具体地，我们需要最大化似然函数关于参数的期望：})={i=1}^nQ_i({ij}))其中，θ表示参数，θ(t)表示第t次迭代的参数。
对于多元正态分布的参数估计，我们需要分别对均值向量μ和协方差矩阵Σ进行更新。
首先，对于均值向量μ的更新，我们可以通过最大化似然函数期望来得到：}=)接下来，对于协方差矩阵Σ的更新，我们可以通过最大化似然函数期望来得到：}=)最后，对于先验概率π的更新，我们可以通过最大化似然函数期望来得到：}=)迭代更新通过不断迭代E步骤和M步骤，我们可以逐步优化似然函数，直到收敛。
(完整word版)EM算法matlab程序
X=zeros（600，2);X(1：200,：）= normrnd（0,1，200,2）；X(201:400,:）= normrnd(0，2,200，2);X（401:600，:）= normrnd（0,3,200,2）；[W，M,V，L] = EM_GM(X，3,［]，[],1，[］）下面是程序源码:打印帮助function[W，M,V，L］= EM_GM（X，k,ltol,maxiter,pflag,Init)％[W，M,V,L］= EM_GM(X，k，ltol,maxiter，pflag,Init）％% EM algorithm for k multidimensional Gaussian mixture estimation％％Inputs：％X(n，d）- input data，n=number of observations，d=dimension of variable % k - maximum number of Gaussian components allowed％ltol - percentage of the log likelihood difference between 2 iterations ([] for none) % maxiter — maximum number of iteration allowed (［] for none）％pflag — 1 for plotting GM for 1D or 2D cases only，0 otherwise （[］for none) % Init — structure of initial W，M, V: Init。
W，Init。
M, Init。
V （［] for none）％％Ouputs：% W(1,k）— estimated weights of GM% M（d，k) — estimated mean vectors of GM％V（d,d,k) — estimated covariance matrices of GM％L — log likelihood of estimates％％Written by％Patrick P。
EM算法详细例子+推导
首先来明确一下我们的目标：我们的目标是在观察变量 X 和给定观察 样本 x1, x2, ..., xn 的情况下，极大化对数似然函数
∑n
l(θ) = ln P (Xi = xi)
(5)
i=1
其中只包含观察变量的概率密度函数
∑
P (Xi = xi) = P (Xi = xi, Z = zj)
(6)
j
1这里因为参数 θ 的写法与条件概率的写法相同，因此将参数 θ 写到下标以更明确的表 述
如果我们这个时候有某种方法（比如，正确的猜到每次投掷硬币是 A 还是 B），这样的话我们就可以将这个不完整的数据估计变为完整数据估 计。
当然我们如果没有方法来获得更多的数据的话，那么下面提供了一种在
这种不完整数据的情况下来估计参数 θ 的方法。我们用迭代的方式来进行：
(1) 我们先赋给 θ 一个初始值，这个值不管是经验也好猜的也好，反正我 们给它一个初始值。在实际使用中往往这个初始值是有其他算法的结 果给出的，当然随机给他分配一个符合定义域的值也可以。这里我们 就给定 θA = 0.7, θB = 0.4
1
1 简介
期望最大化 (Expectation Maximization) 算法最初是由 Ceppellini[2] 等 人 1950 年在讨论基因频率的估计的时候提出的。后来又被 Hartley[3] 和 Baum[4] 等人发展的更加广泛。目前引用的较多的是 1977 年 Dempster[5] 等人的工作。它主要用于从不完整的数据中计算最大似然估计。后来经过 其他学者的发展，这个算法也被用于聚类等应用。
2 一个例子 [6]
本章节希望通过一个例子来解释期望最大化算法的来由以及合理性。
考虑一个投掷硬币的实验：现在我们有两枚硬币 A 和 B，这两枚硬币和 普通的硬币不一样，他们投掷出正面的概率和投掷出反面的概率不一定相
em算法
em算法是指期望最大化算法（期望最大化算法，也翻译为期望最大化算法），是一种迭代算法，用于包含潜在变量概率估计的概率参数模型的最大似然估计或最大后验。
在统计计算中，最大期望(EM)算法是在概率(probabilistic)模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量(Latent Variable)。
最大期望经常用在机器学习和计算机视觉的数据聚类(Data Clustering)领域。
最大期望算法经过两个步骤交替进行计算:第一步是计算期望(E)，利用概率模型参数的现有估计值，计算隐藏变量的期望;第二步是最大化(M)，利用E 步上求得的隐藏变量的期望，对参数模型进行最大似然估计。
M 步上找到的参数估计值被用于下一个E 步计算中，这个过程不断交替进行。
总体来说，EM的算法流程如下:1.初始化分布参数2.重复直到收敛:E步骤:估计未知参数的期望值，给出当前的参数估计。
M步骤:重新估计分布参数，以使得数据的似然性最大，给出未知变量的期望估计。
迭代使用EM步骤，直至收敛。
可以有一些比较形象的比喻说法把这个算法讲清楚。
比如说食堂的大师傅炒了一份菜，要等分成两份给两个人吃，显然没有必要拿来天平一点一点的精确的去称分量，最简单的办法是先随意的把菜分到两个碗中，然后观察是否一样多，把比较多的那一份取出一点放到另一个碗中，这个过程一直迭代地执行下去，直到大家看不出两个碗所容纳的菜有什么分量上的不同为止。
EM算法就是这样，假设我们估计知道A和B两个参数，在开始状态下二者都是未知的，并且知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。
可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。
EM 算法是Dempster，Laind，Rubin 于1977 年提出的求参数极大似然估计的一种方法，它可以从非完整数据集中对参数进行MLE 估计，是一种非常简单实用的学习算法。
基于EM算法的模型聚类的研究及应用的开题报告
基于EM算法的模型聚类的研究及应用的开题报告一、研究背景及意义在实际应用中，模型聚类是一种十分重要的数据分析方法，它可以帮助我们将同类数据分组，进而对这些数据进行更深入的分析。
而基于EM算法的模型聚类是一种较为经典的数据聚类方法。
EM算法（Expectation Maximization Algorithm）是一种迭代算法，可用于通过已知的数据样本来估算一个概率模型的参数。
随着数据规模的增大和多样性的提高，现有的聚类算法已经无法处理高维、大规模、多样性数据的聚类问题。
因此，使用基于EM算法的模型聚类算法，对于解决这类问题会更具优势。
基于EM算法的模型聚类算法可以应用于很多领域，如图像分割、自然语言处理、生物信息学等，并且已经取得了一定的成果。
因此，本文将对基于EM算法的模型聚类算法进行深入研究，以期为相关学科和行业提供更精准和高效的数据分析方法。
二、研究内容及方法1. 研究内容（1）EM算法原理及流程（2）基于EM算法的模型聚类算法的优化（3）基于EM算法的模型聚类算法在实际应用中的性能评价2. 研究方法（1）文献综述——通过查找相关文献，对基于EM算法的模型聚类算法进行深入了解，并复盘其发展历程。
（2）算法设计——基于EM算法的模型聚类算法，需要对算法流程进行详细设计，并针对具体应用场景进行优化。
（3）实验验证——需要在实际数据集上进行算法实验，评价基于EM算法的模型聚类算法的准确性、可靠性和有效性。
三、预期成果1. 设计出一种优化的基于EM算法的模型聚类算法。
2. 在多个数据集上进行实验验证，证明该算法在性能和精度上的优足够好。
3. 提出具体应用场景下的项目案例，将该算法应用到实际项目中进行验证，以证明其实用性及可行性。
四、研究计划时间节点及计划如下：第一阶段：文献综述，对基于EM算法的模型聚类算法进行了解及复盘时间：2周第二阶段：算法设计，对基于EM算法的模型聚类算法进行详细优化设计时间：4周第三阶段：实验验证，对算法在多个数据集上进行实验验证时间：4周第四阶段：应用和总结，应用算法到实际项目中进行验证，并对算法进行总结和展望。
变量选择 em算法
变量选择em算法全文共四篇示例，供读者参考第一篇示例：变量选择是机器学习中非常重要的一个步骤，它影响着模型的准确性、效率和可解释性。
在实际应用中，我们往往面临着大量的特征变量，而并非每一个变量都对模型的预测能力有所贡献。
我们需要对变量进行选择，以提高模型的预测准确性和解释性。
其中EM算法是一种常用的变量选择方法。
EM算法是一种迭代优化算法，通常用于解决包含潜变量的统计模型的参数估计问题。
EM算法的基本思想是通过迭代的方式来估计模型参数，分为两步进行：E步（Expectation）和M步（Maximization）。
在E步中，我们计算潜变量的期望值，即给定观测数据条件下潜变量的概率分布；在M步中，我们最大化似然函数，估计模型参数。
通过不断迭代这两步，我们可以逐步逼近模型的最优参数。
在变量选择问题中，EM算法可以被用来估计每个变量对于模型的重要性。
具体来说，我们可以通过以下步骤来实现变量选择：1. 初始化：我们需要初始化模型参数，并设定一个阈值作为收敛条件。
2. E步：对于每一个变量，我们计算其对应的模型权重。
这里可以根据特定的模型选择不同的权重计算方式，如逻辑回归中的系数、决策树中的信息增益等。
3. M步：在这一步，我们利用EM算法更新模型参数。
我们可以通过梯度下降等优化算法来最大化似然函数，得到最优参数。
4. 变量选择：根据每个变量的模型权重，我们可以对变量进行排序，选择重要性较高的变量作为模型的输入特征。
5. 收敛判断：在每次迭代中，我们比较模型参数的变化是否小于设定的阈值，如果满足收敛条件，则停止迭代，否则继续进行E步和M步。
通过以上步骤，我们可以利用EM算法来选择模型的变量，从而提高模型的准确性和解释性。
在实际应用中，EM算法可以应用于各种机器学习模型中，如逻辑回归、决策树、支持向量机等。
它不仅能够帮助我们选择重要的变量，还可以减少模型的复杂性和提高模型的泛化能力。
第二篇示例：变量选择em 算法在数据挖掘领域中扮演了重要的角色，它通过迭代的方法选择出最具有代表性的变量，帮助我们更好地理解数据的特征和规律。
多元高斯混合模型 em算法 工况-概述说明以及解释
多元高斯混合模型em算法工况-概述说明以及解释1.引言1.1 概述在编写文章的概述部分时，需要对主题进行简要介绍，并提供相关背景信息。
这里是关于多元高斯混合模型（Gaussian Mixture Model, GMM）及其在工况（engineering conditions）中的应用的概述。
多元高斯混合模型是一种常见的统计模型，它是由多个高斯分布组成的概率密度函数的线性组合。
在实际问题中，很多数据的分布无法被单个高斯分布完全描述，而是由多个高斯分布混合而成。
多元高斯混合模型通过将这些高斯分布加权组合，能够更好地近似复杂数据的分布情况。
EM算法是一种常用于估计多元高斯混合模型参数的迭代算法。
通过EM算法，我们可以根据观测数据来估计出模型中每个高斯分布的均值、协方差和权重等参数，从而得到最优的模型拟合结果。
EM算法的基本思想是通过交替迭代的方式，通过E步骤计算隐变量（即数据来自于哪个高斯分布），再通过M步骤更新模型参数，不断优化模型，直到收敛到最优解。
在工况中，多元高斯混合模型及EM算法的应用非常广泛。
工况通常涉及到多个不同的条件和变量，而且这些条件和变量之间往往存在复杂的关联关系。
通过使用多元高斯混合模型，可以更好地对这些变量的分布进行建模和描述，进而提供更准确的分析和预测结果。
无论是在工程领域的故障诊断、质量控制还是金融领域的风险分析等应用场景中，多元高斯混合模型都发挥着重要的作用。
总而言之，本文将针对多元高斯混合模型及其在工况中的应用展开详细探讨。
通过介绍多元高斯混合模型的基本原理和EM算法的实现方式，以及探讨其在工况中的应用案例，旨在提供一种全面的分析方法和工具，以帮助读者更好地理解和应用该模型解决实际问题。
1.2文章结构文章结构部分的内容可以包括以下内容：本文将从以下几个方面进行论述：多元高斯混合模型、EM算法以及它们在工况中的应用。
首先，我们将介绍多元高斯混合模型的基本概念和原理。
通过对多元高斯分布和混合模型的介绍，读者将了解到多元高斯混合模型在数据建模和聚类分析中的重要性及应用场景。
EM算法及其应用实例
Gaussian Mixture Model -Generative Model
Gaussian Mixture Model-Generative Model
Gaussian Mixture Model-Generative Model
Gaussian Mixture Model-Generative Model
Probabilistic Latent Semantic Analysis Model -Generative Model • 问题提出 • 如果时间回到2006年，马云和杨致远的手还会握在一起吗/阿里巴巴集团和 雅虎就股权回购一事签署了最终协议
• 讲解：两个文本的完全不相关，但是事实上，马云和阿里巴巴集团，杨致远和雅虎有着密 切的联系，从语义上看，两者都和“阿里巴巴"有关系。
几个EM应用实例
• Gaussian Mixture Model • Probabilistic Latent Semantic Analysis Model • Latent Dirichlet Allocation Model
Gaussian Mixture Model-Generative Model
The LC Cluster Models
• Includes a K-category latent variable, each category representing a cluster. • Each cluster contains a homogeneous group of persons(cases) who share common interests, values, characteristics, and/or behavior(i.e. share common model parameters). • Note: Advantages over more traditional ad-hoc types of cluster analysis methods include selection criteria and probability-based classification. Posterior membership probabilities are estimated directly from the model parameters and used to assign cases to the modal class – the class for which the posterior probability is highest.
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2
vz u, v v, v
2
u u
2
v z
2
2
2
u, v v
2
2
z
2
u, v v
2
2
v u, v
n
Here we consider the variant form in Euclidean Space
n 2 n 2 xi yi xi yi i 1 i 1 i 1
• How to construct a convex function?
If f(x) is twice differentiable on [a,b] and f ''( x) 0 on [a,b] then f(x) is convex on [a,b]. ln( x) is strictly convex on (0, ) .Hence optimized object is to maximize log-likelihood function.
2
Mathematical Foundations(cont.)
n 1 holds n 1
n n 1 x y x y x y i i i i n 1 n 1 i 1 i 1 2 2
x y x y
2 2 n 1 n 1
n 2 2 n 2 n 2 n 2 x y x yi yn 1 xi xi yi i 1 i 1 i 1 i 1 n n 2 2 2 xi xn 1 yi2 yn 1 i 1 i 1 n 1 2 n 1 2 xi yi i 1 i 1
Example
• True distribution vs What we see
• Problem: How to estimate the parameter of distribution from the right picture?
Dilemma of Estimation
We can only get the information of distribution if we are sure which sample belongs to which class. We can only get the information of sample belonging if we are sure what shape the distribution is. All are resulted from the existing of hidden variable.
u, v u, v z, v u v, v u, v v, v 0 v, v v, v
Mathematical Foundations(cont.)
z is a vector orthogonal to the vector v
u u, v v, v
x1 y1 xn yn x1 xn
2
2
2
y
2
1
yn
2
Mathematical Foundations(cont.)
• Proof procedure of Cauchy–Schwarz inequality
Let u,v be arbitrary vectors in vector space V over F, where F is the field of real or complex numbers 1. v=0 clearly hold the inequality u , v u v 2. Assume u , v 0 u, v Let z u v v, v
Mathematical Foundations(cont.)
• Let f be a real valued function defined on an interval I=[a,b]. f is said to be convex on I if x1, x2 I , [0,1] f ( x1 (1 ) x2 ) f ( x1 ) (1 ) f ( x2 )
2 2 n 1 n 1
EM mechanism
• Problem Formulation
Given a set of independent observed sample x x1, x2 ,, xn with the dimension of d which observe the P-distribution with i i i i the parameter to be estimated in the vector p p1 , p2 , ps . 1 i k representing there are k similar distribution. Determine the values of i group with the maximized probability by introducing |z| hidden values ( z z1, z2 ,, zk ). ,0,1,0,0, ,0] The meaning of zi can be denoted as [0,0, i 1 k i Let p( zk 1) k
Mathematical Foundations(cont.)
• Proof procedure of Jensen equality
n=1: trivial case; n=2: correspond to the definition of convexity; n≥3: f n1 x f x n x f x (1 )
EM mechanism(cont.)
• The basic structure of EM is as follows:
Initialization: randomly set the component E-step: Determine the conditional expectation EZ X , ln P( X , z ) M-step: Maximize EZ X , ln P( X , z ) w.r.t t 1 stable l ( ) D , Do until convergence: Q , t 1 : E c
n 1 f xn 1 (1 n 1 ) n 1 f xn 1 i f ( xi )
i 1 n
i f ( xi ) 1 i 1 n 1
n
i f xi
i 1
n 1
Mathematical Foundations(cont.)
Mathematical Foundations(cont.)
• Cauchy–Schwarz inequality
x, y
2
x, x y , y
Two sides are equal if and only if they are linearly dependent (in geometry space, they are parallel) Expanding
Example(cont.)
• For Maximize Likelihood (ML), we have:
l ( ) log p( xi ) where 1 , 2 ,, k
N i 1
and the is the only parameter to be estimated, with the known type of pdf, the can be directly computed. However, for the previous case, the computing L is impossible since i l ( ) are expressed as follows:
*A.P.
Dempster, N.M. Laird, and D.B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, J. Royal Statiscal Soc., Ser. R, vol. 39, no.1, pp.1-38, 1977.
n 2 xn 1 yn 1 xi yi xi yi i 1 i 1
n
2
2 2 n 1 n 1
2 xn 1 yn 1
2 n 1
n 2 n 2 n 2 n 2 xi yi xi yi i 1 i 1 i 1 i 1
EM Algorithm
Directory
• Theory • Simulation • Summary
Part I: Theory
Expectation Maximization
• Proposed by (A. P. Dempster, 1977)* • Motivation
Incomplete data hidden variable: in statistics, an extraneous variable in a statistical model that correlates (directly or inversely) with both the dependent variable and the independent variable The existing of hidden variable means solve problem directly based on formula is infeasible.
vz u, v v, v
2
u u
2
v z
2
2
2
u, v v
2
2
z
2
u, v v
2
2
v u, v
n
Here we consider the variant form in Euclidean Space
n 2 n 2 xi yi xi yi i 1 i 1 i 1
• How to construct a convex function?
If f(x) is twice differentiable on [a,b] and f ''( x) 0 on [a,b] then f(x) is convex on [a,b]. ln( x) is strictly convex on (0, ) .Hence optimized object is to maximize log-likelihood function.
2
Mathematical Foundations(cont.)
n 1 holds n 1
n n 1 x y x y x y i i i i n 1 n 1 i 1 i 1 2 2
x y x y
2 2 n 1 n 1
n 2 2 n 2 n 2 n 2 x y x yi yn 1 xi xi yi i 1 i 1 i 1 i 1 n n 2 2 2 xi xn 1 yi2 yn 1 i 1 i 1 n 1 2 n 1 2 xi yi i 1 i 1
Example
• True distribution vs What we see
• Problem: How to estimate the parameter of distribution from the right picture?
Dilemma of Estimation
We can only get the information of distribution if we are sure which sample belongs to which class. We can only get the information of sample belonging if we are sure what shape the distribution is. All are resulted from the existing of hidden variable.
u, v u, v z, v u v, v u, v v, v 0 v, v v, v
Mathematical Foundations(cont.)
z is a vector orthogonal to the vector v
u u, v v, v
x1 y1 xn yn x1 xn
2
2
2
y
2
1
yn
2
Mathematical Foundations(cont.)
• Proof procedure of Cauchy–Schwarz inequality
Let u,v be arbitrary vectors in vector space V over F, where F is the field of real or complex numbers 1. v=0 clearly hold the inequality u , v u v 2. Assume u , v 0 u, v Let z u v v, v
Mathematical Foundations(cont.)
• Let f be a real valued function defined on an interval I=[a,b]. f is said to be convex on I if x1, x2 I , [0,1] f ( x1 (1 ) x2 ) f ( x1 ) (1 ) f ( x2 )
2 2 n 1 n 1
EM mechanism
• Problem Formulation
Given a set of independent observed sample x x1, x2 ,, xn with the dimension of d which observe the P-distribution with i i i i the parameter to be estimated in the vector p p1 , p2 , ps . 1 i k representing there are k similar distribution. Determine the values of i group with the maximized probability by introducing |z| hidden values ( z z1, z2 ,, zk ). ,0,1,0,0, ,0] The meaning of zi can be denoted as [0,0, i 1 k i Let p( zk 1) k
Mathematical Foundations(cont.)
• Proof procedure of Jensen equality
n=1: trivial case; n=2: correspond to the definition of convexity; n≥3: f n1 x f x n x f x (1 )
EM mechanism(cont.)
• The basic structure of EM is as follows:
Initialization: randomly set the component E-step: Determine the conditional expectation EZ X , ln P( X , z ) M-step: Maximize EZ X , ln P( X , z ) w.r.t t 1 stable l ( ) D , Do until convergence: Q , t 1 : E c
n 1 f xn 1 (1 n 1 ) n 1 f xn 1 i f ( xi )
i 1 n
i f ( xi ) 1 i 1 n 1
n
i f xi
i 1
n 1
Mathematical Foundations(cont.)
Mathematical Foundations(cont.)
• Cauchy–Schwarz inequality
x, y
2
x, x y , y
Two sides are equal if and only if they are linearly dependent (in geometry space, they are parallel) Expanding
Example(cont.)
• For Maximize Likelihood (ML), we have:
l ( ) log p( xi ) where 1 , 2 ,, k
N i 1
and the is the only parameter to be estimated, with the known type of pdf, the can be directly computed. However, for the previous case, the computing L is impossible since i l ( ) are expressed as follows:
*A.P.
Dempster, N.M. Laird, and D.B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, J. Royal Statiscal Soc., Ser. R, vol. 39, no.1, pp.1-38, 1977.
n 2 xn 1 yn 1 xi yi xi yi i 1 i 1
n
2
2 2 n 1 n 1
2 xn 1 yn 1
2 n 1
n 2 n 2 n 2 n 2 xi yi xi yi i 1 i 1 i 1 i 1
EM Algorithm
Directory
• Theory • Simulation • Summary
Part I: Theory
Expectation Maximization
• Proposed by (A. P. Dempster, 1977)* • Motivation
Incomplete data hidden variable: in statistics, an extraneous variable in a statistical model that correlates (directly or inversely) with both the dependent variable and the independent variable The existing of hidden variable means solve problem directly based on formula is infeasible.