《机器学习系列-强填EM算法在理论与工程之间的鸿沟(上)》
小夕曾經問一位做機器學習理論的學姐:“學姐學姐,EM算法是什么呢?”
?
學姐回答:“EM算法啊,就是解決包含隱變量的參數估計問題。”
?
小夕:
?
然后小夕去問一位做工程的學長:“學長學長,EM算法是什么呢?”
?
學長回答:“EM算法就那樣啊,就是先用有標簽的樣本訓練個分類器,再給未知標簽的樣本貼標簽,然后再拿全部樣本再訓練分類器,就這樣來回倒騰~”
?
小夕:
?
?于是小夕自己一個人看了一整天的EM算法QAQ
前言
首先說,其實學長和學姐說的都很對。但是對于一個路人來說,很難將學長與學姐的說法聯系到同一個東西上。而最終小夕總結出來的就是,做工程的學長的回答其實是做理論的學姐的回答下的一個簡化的特例。
?
首先,我們來看一下理論上的期望最大化算法,也就是EM算法(不要想了,對于這個算法,小夕打死也繞不開數學公式了,所以有公式恐懼癥的同學請自行用手指蓋住它們...
?
另外,嚴正聲明一下,對于沒有微積分與概率統計基礎的同學,請直接等下一篇中得出的結論!非要看這一篇的話,請時刻保持理智,請時刻保持理智,請時刻保持理智。
理論家眼中的EM
?
開門見山,EM算法的目標是使包含隱變量的數據集的后驗概率或似然函數最大化,進而得到最優的參數估計。
?
我們知道,通過貝葉斯公式,可以發現后驗概率中包含了似然函數和先驗概率(忽略分母的那個evidence項),因此求最大后驗概率的過程中包含了求極大似然估計的過程。因此雖然EM算法的目標是最大化后驗概率或似然函數,而本質上就可以認為是最大化似然函數。因此下面我們直接討論最大化似然函數。
?
似然函數設為l(θ),描述樣本可以用多維隨機變量(對應于機器學習的多維特征),每一維的隨機變量都可以認為服從某種概率分布。因此要描述每一維的樣本情況,我們只需要估計出這一維度的概率分布模型的參數就可以啦。而將所有維度的分布模型的參數放在一起,就是似然函數的參數,即θ。因此根據定義,
?
即似然函數代表著該包含m個樣本的樣本集存在的合理性(似然函數值越大,該樣本集的存在就越合理,即意味著參數取的越正確),描述每個樣本的多維隨機變量的分布模型的參數即上面的θ,p(x; θ)代表著固定θ的值,求p(x)的概率。
?
第二行的z則代表隱變量,確切的說是隱含的隨機變量。哈?看不懂第二步怎么來的?請回去復習微積分...算了,小夕太過善良,還是講講吧。
?
顯然,這里似然函數討論的是離散情況(畢竟都是∑符號而不是∫符號呀),因此,在p(x; θ)中加上z這個隨機變量后,只能將這個隨機變量積分掉才能保證加上z以后的式子依然等于p(x;θ),當然,z是離散的,所以積分掉的意思是“求和”掉。
(回顧一下,對于任何一個連續隨機變量x,∫p(x)dx=1;對于任何一個離散隨機變量x,∑p(x)=1)
?
好,懂了第二步,在繼續往下推之前,想一想我們可不可以直接計算第二步呢?當然不行啦,不僅有θ,還有隱變量啊。因此繼續往下推。
??
誒?又出來個Qi。這個Qi是什么呢?這個Qi是隱變量z的概率分布函數啦。為什么要加上它呢?再好好觀察一下最后這一步中的這一部分!
?
有沒有發現什么!?對!這就是數學期望呀~別說數學期望都忘了啊,小夕還是再啰嗦一下吧...對于某離散隨機變量X來說,其數學期望
看吧~加上Qi這個概率分布函數后,是不是就出來了一個數學期望啦!但好像還是不能計算,懂數值計算的讀者應該知道log(∑…)的計算量是十分恐怖的,而且我們還被我們加上了一個不知道怎么計算的Qi!!!因此要繼續變!!!怎么變呢?Jensen不等式來啦!
?
直接摳了個定義(看不懂沒關系):
?
通過這個Jensen不等式,我們發現可以進一步往下推了。
?
誒?雖然是往下推了一步,但是我們必須要讓等號恒成立才行啊,否則這個推理是不成立的呀。。。那么怎么讓等號恒成立呢?
?
根據Jensen不等式的等號成立條件,E[f(X)]≥f(E[X])中的隨機變量X必須恒等于常數!!也就是說:
?
≡c(c為常數)
?
于是重點來了,將分母的Qi移到右邊,將右邊的c移到左邊!我們發現:
好,再利用(概率分布函數的基本性質),發現我們可以繼續這樣推!
?
推到最后竟然是這個?????
這個不就是每個樣本的隱變量z的后驗概率嗎!!!
也就是說我們只要求出來了每個樣本的隱變量的每個取值的后驗概率,就能得到這個樣本的Qi!!!
就能讓Jensen不等式的等號成立!!!
就能讓log(∑…)的不可計算成功變成可計算!!!
就能計算我們的目標——似然函數啦!!!
?
所以,咳咳,總之,我們首先固定一個θ(也就是隨便給θ取個初始值),然后我們計算出隱變量z的取值的后驗概率,就能讓這個包含隱變量的似然函數變成傳統意義上的似然函數~也就是只考慮參數θ的似然函數~(這個過程稱為E步)
?
而最大化傳統意義上的似然函數就不用啰嗦啦~那就用傳統的方法最大化呀~最大化了以后就得到了當前的最優θ。(這個過程稱為M步)
?
而得到了當前的最優θ以后,我們又可以重新計算出隱變量z的取值的后驗概率,就能……~~~總之就又可以E步,然后又M步,然后又E,又M……
?
就這樣一直重復,一直重復,直到似然函數的值不再變化,此時每個樣本的Qi就是每個樣本的標簽~而此時的θ就是最終那個最優的θ啦~
?
至此,理論上的EM算法完成了,最終得到的就是我們要估計的最優參數θ,順便得到了每個樣本的隱變量的取值。
那么工程上看似是跟分類器打交道,小夕則說其實是理論的特例又是怎么回事呢?敬請期待《機器學習系列-強填EM算法在理論與工程之間的鴻溝(下)》,待小夕華麗麗的填上理論與工程的鴻溝。(下一篇沒有這一篇這么恐怖,2333)
雖然您可能沒有看懂,但是看在生敲公式后發現微信編輯器不識別然后又一個個截圖的份上_(:з」∠)_
?
總結
以上是生活随笔為你收集整理的《机器学习系列-强填EM算法在理论与工程之间的鸿沟(上)》的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 史上最简单的隐马尔可夫模型讲解
- 下一篇: WSDM Cup 2020检索排序评测任