转：DP和HDP
Dirichlet Process and Hierarchical Dirichlet Process
原文：http://hi.baidu.com/zentopus/item/46a622f5ef13e4c5a835a28e
?
Dirichlet Process and Hierarchical Dirichlet Process
?????? 在這篇文章里，我會初步地介紹Dirichlet Process以及Hierarchical Dirichlet Process，不過僅僅局限于模型本身，并不涉及其inference和具體的application。
?????? 首先，我將簡單地介紹Dirichlet分布。Dirichlet分布可以看做是分布之上的分布。其定義為對于一個K維的probability simplex:
???
?????? 我們說這組是Dirichlet distributed， 參數為如果其滿足:
???
?
?????? 如何理解這個定義呢？我們可以舉個例子：假設我們有一個從魔術店買來的骰子，我們不知道這是不是一個和普通骰子一樣均勻的骰子，即每面出現的概率都是1/6。那么我們現在就可以用一個分布來描述我們對于這個骰子的uncertainty，也就是說，我們想知道這個骰子是一個公平的骰子的概率是多少。那么這個分布，就可以是一個Dirichlet Distribution，只要我們可以將這個分布描述為上述的數學形式。我們再看一眼這個例子，投擲一次骰子，必然會有一面出現（這是一個好骰子），那么六面出現的概率總和必然為1，換句話說，我們可以用這樣一個分布來描述骰子出現的概率。而后我們又想知道，這樣一個分布出現的概率是多少，那么我們就可以用Dirichlet分布來描述它。從而我們可以說，Dirichlet分布是一個分布之上的分布。
?? ?
Dirichlet Process
??? 接下來，我們將從Dirichlet分布過渡到Dirichlet Process。
?? ?首先，我們先來看一下probability measure的概念：我們定義G為可度量空間X上的一個probability measure，如果其滿足：
???????
?????? 我們還是從剛才的骰子的例子開始，我們現在認為整個骰子所描述的事件空間為一個可度量的空間。一個骰子投擲出去之后，六面必然有一面出現，那么我們可以自然地將整個空間分成為6個部分，我們稱每一個部分為一個劃分。那么針對這種六個劃分的情況，我們可以有一個對應于這個劃分的Dirichlet分布。現在我們想做一些調整，我們將骰子投擲出去的結果分成了2種，一種是大{4,5,6}，另外是小，對應于{1,2,3}。那么我們可以認為整個空間，被分割成為了2個劃分，那么相應的，我們可以對這樣一種劃分有一個對應的Dirichlet分布。現在我們將其進行一個一般性的描述。假設我們現在有一個可度量的空間X，其上的任意一個有限(finite)劃分(partition)滿足：
?
?????? 我們說一個probability measure G服從都Dirichlet Process，如果其滿足：對于這個可度量空間上的任意一個有限劃分，以及一個實數一個probability measure G0：
?????? 這里G0稱作base measure,有些類似于這個DP的均值(mean)，稱作Strength parameter， 有些類似于這個DP的inverse-variance，在描述一個DP的時候，我們寫作：
?????? 接下來，我將簡單介紹一下其對應的幾種常見的表現形式
The Chinese Restaurant Process
?????? 把Chinese Restaurant Process(CRP)放在最前，是我認為這是最容易理解的一種表現形式。其對應的并不是G本身，而是對應一個從G進行sampling的過程。
?????? 假設現在有一家中餐館，里面有無限多的桌子，當然，不是所有桌子上都坐了人。首先進來第一個顧客，第一個顧客只能坐在一號桌子。他坐下之后點了一個菜（這個菜的分量足夠大）。然后進來了第二個顧客，他看了一眼一號桌的菜，如果他喜歡吃的話，就坐到一號桌去，如果不喜歡的話，就另外再開一桌，自己點菜。假設這個過程一直下去，當第i個顧客進店的時候，假設這時候已經有了k桌菜，這個顧客巡視了一圈，然后尋找自己喜歡的菜。我們認為他是一個具有大眾口味的人，他選擇某一桌的概率，完全正比于這桌上坐了多少個顧客。如果他實在沒有找到喜歡的菜，他也可以新開一桌，新開一桌的概率正比于某個初始的數值。
?????? 現在我們數學一點來看待這個過程：假設每一個sample，對應于一個顧客。那么我們可以認為第i個sample選擇桌子k的概率為的概率，代表了這桌的菜。這個概率正比于已經坐在這桌的顧客數量，而這個顧客開一個新桌的概率則正比于初始化的參數.
?????? 從剛才的描述中，我們已經看出了Dirichlet Process所獲得的樣本是離散的，并且其抽樣過程中體現出了一種聚類的特性。而這些特性不受Base Measure是離散或者連續的影響。
?????? 出了CRP之外，還有一個非常類似的方式，稱之為Polya urn scheme(Blackwell 1973)。這個過程和CRP非常相似。假設我們現在有一組samples:
?????? 這組樣本是i.i.d的，并且其滿足：
?????? 我們可以這樣理解抽樣的過程：我們現在口袋里有很多很多球，都是不同顏色的。我們從中取出一個球，鑒別了它的顏色，然后拿一個和這個球一樣顏色的球和這個球一塊兒放回去。如此往復，得到了我們現有的一組樣本。
?????? 我們和CRP統一一下，則這個過程可以表現為：
?????? 如果G的sample可以滿足上述的分布，我們就認為從G符合DP。
Stick-breaking Construction
?????? 除了CRP之外，我們還可以通過別的方式來構造一個DP，這就是Stick-breaking construction。整個構造過程如下：
?????? 我們觀察上面的這個過程，可以發現sample的過程，就相當于CRP中給每個桌子賦予一個值，而獲取的過程，則是確定每個桌子上的顧客數量。
?????? 我們注意到:
?????? 所以，我們可以將解釋為一個random probability measure。并且，如果是以這樣的方式產生的，我們可以將其寫為：
?????? GEM代表三個人名，分別為：Griffith，Engen和McCloskey
Dirichlet Process Mixture
?????? 另一個理解DP的角度，就是從一個混合模型來看。假設在一個混合模型中，我們不知道component的明確數量，這時候我們應該怎么處理呢？常規的方法是，重復做多次試驗，每次試驗中假設不同的數量的component，而后利用AIC，BIC等判別方式來進行選擇。但是這樣的方式又耗時又費力，有沒有輕松一些的方式呢？DP mixture model給了我們一個新的選擇，其關鍵點在于，認為空間中是有無限多的mixtrue component的，但是根據我們的數據，只有其中有限個的component被激活了，并且，這些激活的component的proportion滿足一個Dirichlet Distribution。下面我們就從一個有限的mixture model出發，來推廣到一個DP mixtrue model。
?????? 我們假設這個mixtrue model有L個component，我們用來表示每個component的proportion，并且，我們給這個proportion加上一個對稱的Dirichlet先驗，則我們有：
?????? 我們用z代表每個sample的component assignment，即選中了哪一個component，用代表每個component的參數，而這組參數符合一個分布G0，則我們有：
?????? 我們此時可以得到一個分布
?????? 而如果我們將L推向infinite，則這個模型便成為了DP mixture， 如同下圖
?????? 我們再完整地看一次DP mixture的生成過程：
Why Dirichlet Process
?????? 我們用了這么復雜的數學手段，搞出來一個DP，是為什么呢？我們觀察DP，發現其有一個非常重要的特性，即在抽樣的過程中，可以獲取到值相等的2個樣本。這有什么重要意義呢？這意味著這一過程本身在重復抽樣的過程中，就完成了一個聚類的過程。并且我們注意到，DP對于其Base Measure并無要求，也就是說其Base Measure可以為連續的分布。而我們知道，對于一個連續的分布，其抽樣的過程中，兩個樣本完全相同的概率為絕對的0，而DP則可以在這個分布的基礎上，將樣本離散化，使得2個樣本的值相同的概率不為0。
?
Hierarchical Dirichlet Process
???????
?????? 我們發現DP具有很好的聚類的特性，并且我們也不用事先設定好類別的數量，使得整個過程變得更為智能。
?
?????? 那么我們現在考慮另一個問題，假設我們已經有了很多數據，并且數據自身是按照組別出現的，每一組數據都可以看做一個mixture model。除了組別內部是mixture model之外，我們還希望這些mixture component是可以share的。我們換一個角度來看這個問題：假設我們現在有一個巨大的空間，整個空間中包含了無數的mixture component，我們每次選擇其中的幾個，然后利用這幾個component生成一組數據。我們把一組一組的數據放在一起，就得到了我們現在所擁有的數據。我們現在希望可以用mixture model來描述這樣一種數據，DP可以幫上什么忙么？
?
?????? 我們注意到，在每一組數據中，我們需要進行一次clustering，這意味著我們可以選擇DP來描述某一組數據。但是我們又希望在整個數據中share component，一個很原始的原始的想法，就是限制DP的Base Measure為離散的，從而讓我們有固定的component可以進行選擇。但是這樣就使得問題失去了一般性，并且我們還需要面對一個問題，如何選擇這樣一個Base Measure以及其component數量。這時候，我們發現這個問題其實和針對每一個組內的問題是一致的，那么我們很自然地就想到了，在這一層上我們再利用一次DP來描述，從而使得我們可以克服這些麻煩的問題。那么在DP之上再引入一層DP的模型，就是Hierarchical Dirichlet Process(HDP)。其圖模型可以參看下圖
?????? 現在我們從生成模型的角度，來看一下這整個的過程：
Chinese Restaurant Franchise
?????? 和DP一樣，我們也可以用中餐館這樣一個描述方式來加強對于這個問題的理解。
?????? 這次，我們不是有一個中餐館，我們有一家中餐連鎖店，每一家都有一樣的一份菜單。對于第j家餐館，我們考慮其第i個顧客。和之前一樣，這個顧客走進這家餐館之后，選擇坐在已有的一桌，或者是新開辟一桌。不過這里有一點特別的是，我們允許不同的餐館中的不同的桌子點相同的菜，因為這些顧客是從同一份菜單里點菜的，當然，每桌還是只有一個菜。那么從一個餐館的層面來說，我們有：
?????? 那么，在選擇每桌的菜的層面上，我們有：
?????? 我們注意到，在整個過程中，各種菜是可以在組間和組內共享的，這是HDP的關鍵特性。
Stick-breaking Construction
?????? 現在，我們再從Stick-breaking Construction的角度來看一看HDP。
?????? 從圖中我們可以看出，G0是符合DP的，根據之前我們對于DP的描述，我們有：
?????? 其中：
?????? 既然G0有support，那么自然的，以G0為Base Measure的Gj也有相同的support，則：
?????? 其中，滿足:
?????? 在給定的情況下，之間是相互獨立的。那么和之間的關系又是如何呢？
?????? 我們知道，根據DP的定義，對于可度量空間上的任意一種有限劃分{A1,A2,...,Ar}，我們有：
?????? 那么，這也就意味著：
?????? 從這個式子中，我們就不難看出：
?????? 而和，我們則認為其均為probability measure。
?????? 那么對于圖中所描述的混合模型，我們的完整的生成模型為：
?????? 其中
Discussion
?????? 相同的問題，我們為什么要使用HDP？最基本的理由是，如果我們遇到這樣的數據集的時候，即一個component會不斷變化的mixture model，并且在subgroup中，component是可以共享的這樣一個數據集，我們就可以利用HDP來進行建模。實際中，HDP也已經被廣泛的使用，應用包括topic modeling，cognitive science等等。
?????? HDP本身是Dependent Dirichlet Process(DDP)的一種具體的形式，它能夠有效地描述這種垂直的層級關系。但是HDP也有局限性，其并不能描述即時變化，不能夠描述component的生成與消亡。而在解決這個問題上，目前我們可以依靠Poisson Process Based Dependent Dirichlet Process來給出一個方案，這其中利用了Poisson Process，Gamma Process以及DP的內在關系，具體可以看Dahua Lin的NIPS 2010文章。有時間的話，我也會把對那個模型做一個簡單的描述。
?????? HDP可以利用Variational Inference和Gibbs Sampling來進行"求解"，Wang Chong也提出了一種Online的算法，其中利用了一種不同的Stick-breaking的構造方式，來使得上下兩層關系之間進行解耦，從而能夠進行Online的求解過程。
轉載于:https://www.cnblogs.com/lifegoesonitself/p/3423363.html
總結
- 上一篇： 404页面自动跳转javascript
- 下一篇： JQUERY AJAX无刷新异步上传文件