大数据分析算法-EM算法—最大期望算法课件

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,*,大数据分析算法,EM,算法,最大期望算法,食堂的,大师傅,炒,了一份,菜,，要等,分,成两份,给,两个人吃,2,显然没有必要拿来天平一点一,点,的精,确,的去,称,分量，最简单的办法是先随意的把菜分到,两,个碗,中,，然,后,观察是,否一样多，把比较多的那一份取出,一,点放,到,另一,个,碗中，,这个过程一直迭代地执行下去，直,到,大家,看,不出,两,个碗所 容纳的菜有什么分量上的不同为止,EM,算法就是这样，假设我们,估,计知,道,A,和,B,两,个,参数,，,在 开始状态下二者都是未知的，并且,知,道,了,A,的,信,息就,可,以,得到,B,的信息，反过来知道,了,B,也就得到了,A,。可以考,虑,首,先赋,予,A,某种初值，以此得,到,B,的估计值,，,然后,从,B,的,当,前 值出发，重新估计,A,的取值，这个过程,一,直持,续,到收,敛,为,止,。,1,6:54:,1,0,E,M,算法,3,最,大,期望,算,法,（,Exp,e,c,t,at,i,on-m,a,xi,m,iza,t,ion,algor,i,th,m,，又译期望最大化算,法,）在,统,计中被 用于寻找，依赖于不可,观,察的,隐,性变,量,的概率,模型中，参数的最大似,然,估,计,。,在统计计算中，最,大,期,望,算法,是,在概,率,模型中,寻找参数,最大似然估,计,或,者最,大,后验,估,计的算 法，,其,中概,率,模型,依,赖于,无,法观,测,的隐,藏,变量。最大期望经常用在机器,学,习和,计,算机,视,觉的数,据聚类领域。,1,6:54:,1,1,期望值,（,EXPECTED,V,A,L,UE),在概率和统计学中，一,个,随机,变,量的,期,望 值是变量的输出值乘以,其,机率,的,总和,，,换,句话说，期望值是该变,量,输出,值,的平,均,数,如,果,X,是在概率空间,（,P,）中的一个随机,变量，那么它的期望,值,E,X,的,定,义是,E,X,=,X,d,P,离散：,EX=,连续：,EX,=,4,1,6:54:,1,1,最大似然估计,某位同学与一位猎人一,起,外出,打,猎，,一,只野兔,从前方窜过只听一声,枪,响，,野,兔应,声,到下，如果要你推测，这一发,命,中的,子,弹是,谁,打的？,你就会想，只发一,枪,便打,中,，由,于,猎人命,中的概率一般大于这位,同,学命,中,的概,率,，看来,这一枪是猎人射中的,1,6:54:,1,1,5,最大似然估计,假设我们需要调查我们学校的男生和女生的身高分,布,。你在校园里随便地活捉了,1,0,0,个男生和,1,0,0,个女生。男 左女右，首,先,统计抽样得到的,1,0,0,个男生的身高。假设 他们的身高是服从高斯分布的。但是这个分布的均,值,u,和方差,2,我们不知道，这两个参数就是我们要估计的。,记作,=u,T,。,数学语言：,在学校那么多男生（身高）中，我们独立地按照概率密度,p(,x|,),抽取,1,00,了个（身高），组成样本,集,X,，我们想通过样 本,集,X,来估计出未知参数,。概率密度,p(,x|,),我们知道了是高 斯分,布,N(u,),的形式，其中的未知参数,是,=u,T,。,抽到这,1,0,0,个人的概率：,1,6:54:,1,1,似然函,数,：,L,(,),=,L(x,1,x,2,x,n,|,),=,6,(,|,),=,最大似然估计,7,上,例中，,在学校那么,男生,中，,我,一抽,就,抽到这,1,0,0,个男生（表,示,身高,）,，而,不,是其,他,人，那 是不是表示在整个学校,中,，,这,1,0,0,个,人,（的身,高）出现的概率最大啊,。,那么,这,个概,率,怎么表,示？哦，就是上面那个,似,然函,数,L(,),。所,以,，,我们就只需要找到一个,参,数,，,其对,应,的似然 函数,L(,),最大，也就,是,说抽,到,这,1,0,0,个男生,（的身高）概率最大。,这,个叫,做,的,最,大似然,估计,量,1,6:54:,1,1,最大似然估计,设总体,X,是离散型随机变量,，其概率函数为,(,;,),，其中,是未知参数设,X,1,X,2,X,n,为取自总体,X,的样本,，,X,1,X,2,X,n,的 联合概率函数,为,:,若已知样本取值,为,x,1,x,2,x,n,，则事件,X,1,=,x,1,X,2,=,x,2,X,n,=,x,n,发生的概率为,(,|),=,显然上面的概率,随,改变而改变，从,直,观上,来,讲，,既,然样本,值,x,1,x,2,x,n,出现，即表示其出现的概率相,对,较大,，,而使得,(,;,),取较大的值，不妨看,做,的,函数,=,1,6:54:,1,1,似然函,数,：,L,(,),=,L(x,1,x,2,x,n,|,),=,(,|,),=,8,(,|,),为常量，,X,1,X,2,X,n,为变量,=,最大似然估计,如何求,L(,),最大值？,考虑到有累乘，不妨取对数，这里是因,为,lnL,函数的单 调性和,L,函数的单调性一致，因,此,L(,),的最大值转换为,lnL,(,),的最大值,=,=,=,=,(,|,),=,求最值,可转换为求解下面的方程,(,),=,1,6:54:,1,1,似然方,程,9,EXAMPLE,10,设某工序生产的产品的,不,合格,率,为,p,，,抽,n,个 产品作检验，发,现,有,T,个不,合,格，,试,求,p,的,极大 似然估计,分析：,设,X,是抽查一个产品时的不合,格,个数,，,则,X,服从参数的二点分布,b(1,p).,抽查,n,个产,品,，得,样,本,X,1,X,2,X,3,，其观察值,为,x,1,x,2,.,x,3,，加,入,样本,有,T,个 不合格，表示,x,1,x,2,.,.,.,x,3,中,有,T,个,取值,为,1,，,n-,T,个取,值,为,0,.,按照离散分布场合方,法,，,求,p,的极,大,似然,估,计,1,6:54:,1,1,解：,1,.,写出似然函数,=,(1,),1,=,1,2,.,对,取对数，得对数似,然,函数,：,l,(,p,),x,i,l,n,p,(,1,x,i,),ln,(,1,p,),n,ln,(,1,p,),x,i,ln,p,ln,(,1,p,),i,1,i,1,3,.,写出似然方程,4,.,解似然方程得,：,p,5,.,验证,在,p,x,时,，,d,l,(,p,),0,，这表明,p,x,可使似,然函数达到最大,1,6:54:,1,1,nn,x,0,1,p,p,(,1,p,),i,1,1,),p,1,p,1,n,x,(,1,d,l,(,p,),n,d,p,1,p,i,1,n,i,n,i,x,n,x,i,n,i,1,1,d,p,2,2,11,1,6:54:,1,1,小结,极大似然估计，只是一,种,概率,论,在统,计,学的应,用，它是参数估计的方,法,之一,。,说的,是,已知某 个随机样本满足某种概,率,分布,，,但是,其,中具体 的参,数,不清,楚,，参,数,估计,就,是通,过,若干,次,试验，观察其结果，利用结果,推,出参,数,的大,概,值。最,大似然估计是建立在这,样,的思,想,上,：,已,知某个 参数能使这个样本出现,的,概率,最,大，,我,们当然 不会再去选择其他小概,率,的样,本,，所,以,干脆就,把这个参数作为估计的,真,实值。,12,最大期望算法,13,继续回到身高的例子,，,我,抽到,这,20,0,个,人,中，某些男生和某些女生一,见,钟情,，,已经,好,上,了，怎么着都不愿意分开,，,这,时候,，,你从,这,200,个,人里面随便给我,指一个,人,，,我,都,无法,确,定,这,个 人是男生还是女生。,也就是说,你不知道,抽,取,的,那,20,0,个,人里,面,的每 一个人到底是从男生的,那,个身,高,分布,里,面抽取 的，还是女生的那个身,高,分布,抽,取的,。,用数学 的语言就是,，,抽取得到,的,每个,样,本都,不,知道是 从哪个分布抽取,的,。,1,6:54:,1,8,最大期望算法,14,这个时候，对于每一个样本或者你抽取到的人，,就有两个东西需要猜测或者估计的了,，,一是这个 人是男的还是女的？二是男生和女生对应的身高,的高斯分布的参数是多,少？,只有当我们知道了哪些人属于同一个高斯分布的 时候，我们才能够对这个分布的参数作出靠谱的 预测；反过来，只有当我们对这两个分布的参数 作出了准确的估计的时候，才能知道到底哪些人,属于第一个分布，那些人属于第二个分布,1,6:54:,1,8,先有鸡还,是,先有蛋,1,6:54:,1,8,15,为了解决这个你依赖我,，,我依,赖,你的,循,环依赖 问题，总得有一方,要,先打破僵局，说，,不,管了，我先随便整一个值出来,，,看你,怎,么变,，,然后我,再根据你的变化调整我,的,变化,，,然后,如,此迭代 着不断互相推导，最终,就,会收,敛,到一,个,解,1,6:54:,1,8,亲，还记,得,ppt,开始分菜的厨师么？,16,E,M,：,EXPECT,TA,TION,MAXIMIZ,A,TION,17,依然用身高的例子,Expectatio,n,：我,们,是先随便猜一下男生（身高）的正态 分布的参数：如均值和方差是多少。例如男生的均值是,1,米,7,，方差,是,0,.,1,米，然后计算出每个人更可能属于第,一个还是第二个正态分布中的（例如，这个人的身高是,1,米,8,，那很明显，他最大可能属于男生的那个分,布,）,Maxim,i,zatio,n,：有了每个人的归属，或者说我们已经大,概地按上面的方法将,这,20,0,个人分为男生和女生两部分，我们就可以根据之前说的最大似然那样，通过这些被大,概分为男生,的,n,个人来重新估计第一个分布的参数，女 生的那个分布同样方法重,新,估计,这时候，两个分布的概率改变了,，,那么我们就再需要调,整,E,步,如此往复，直到参数基本不再发生变化为止,1,6:54:,1,8,QUE,S,TIONS,18,你老迭代迭代的，你咋,知,道新,的,参数,的,估计就,比原来的好,啊,？,为什么这种方法行得通,呢,？,有没有失效的时候呢？,什么时候失效呢？,用,到这个方法需要注意,什,么问,题,呢？,1,6:54:,2,2,E,M,算法推导,19,假设我们有一个样本,集,x,(1,),x,(m),，包含,m,个 独立的样本。但每个样,本,i,对应的,类,别,z,(,i,),是未 知的（相当于聚类），,也,即隐,含,变量,。,故我们,需要估计概率模,型,p,(,x,z),的,参,数,，,但是,由,于里 面包,含,隐含,变,量,z,，所,以很,难,用最,大,似然,求,解，,但如果,z,知道了，,那,我,们,就很,容,易求,解,了,。,1,6:54:,2,2,E,M,算法推导,这里把每个人（样本）,的,完整,描,述看,做,是三元,组,y,i,=,x,i,z,i,1,z,i2,，,x,i,是第,i,个样本的观测值,z,i,1,和,z,i,2,表示利用,男女,哪个,高,斯分,布,，隐,含,变量,z,ij,在,x,i,由第,j,个高斯分布,产,生时,值,为,1,，否则,为,0,。,例如一个样本的观测值,为,1,.,8,，,来自,男,生高 斯分布，则样本表示为,1,.8,1,0,。,即若,z,i1,和,z,i2,的值已,知,，也,就,是说,每,个人我,已经标记为男生或者女,生,了,1,6:54:,2,2,20,对于参数估计，我们本质上还是想获得一个使似,然函数最大化的那个参,数,，现在与最大似然不同 的只是似然函数式中多了一个未知的变,量,z,也就是说我们的目标是找到适合,的,和,z,让,L(,),最大,1,6:54:,2,2,21,（,1,）式最大化,，也,就,是,最,