機器學習概率圖模型(推理采樣算法)

基于采樣的推理算法利用的思想是

概率=大樣本下頻率。故在獲得圖模型以及CPD的基礎上，通過設計采樣算法模擬事件發(fā)生過程，即可獲得一系列事件（聯(lián)合概率質量函數(shù)）的頻率，從而達到inference的目的。1、采樣的做法使用采樣算法對概率圖模型進行隨機變量推理的前提是已經獲得CPD。舉個簡單的例子，如果x=x1,x2,x3,x4的概率分別是a1,a2,a3,a4.則把一條線段分成a1,a2,a3,a4，之后使用Uniform采樣，x落在1處，則隨機變量取值為a1...依次類推，如圖所示。顯然，采樣算法中最重要的量就是采樣的次數(shù)，該量會直接影響到結果的精度。關于采樣次數(shù)有以下定理：以簡單的貝葉斯模型為例，如果最終關心的是聯(lián)合概率，條件概率，單一變量的概率都可以使用采樣算法。下圖共需要設置1+1+4+2+3=11個uniform采樣器，最終得到N個結果組合（d0i1g1s0l1等）。最后計算每個組合出現(xiàn)的頻率即可獲得聯(lián)合概率分布。通過邊緣化則可獲得單一變量概率。如果是條件概率，則去除最終結果并將符合條件的取出，重新歸一化即可?？偨Y可知，采樣算法有以下性質：1.精度越高，結果越可靠，需要的采樣次數(shù)也越多。2.所關心的事件發(fā)生的概率很小，則需要很大的采樣次數(shù)才能得到較為準確的結果。3.如果隨機變量的數(shù)量很多，則采樣算法會非常復雜。故此算法不適用于隨機變量很多的情況。2、馬爾科夫鏈與蒙特卡洛算法馬爾科夫鏈是一種時域動態(tài)模型，其描述的隨機變量隨著時間的推進，在不同狀態(tài)上跳躍。實際上，不同的狀態(tài)是隨機變量所可能的取值，相鄰狀態(tài)之間是相關關系。引入馬爾科夫鏈的目的是為了描述某些情況下，隨機變量的分布無法用數(shù)學公式表達，而可利用馬爾科夫鏈進行建模。把隨機變量的取值視為狀態(tài)，把隨機變量視為跳蚤。馬爾科夫鏈如下圖所示：顯然，對于簡單的馬爾科夫鏈我們大致還可以猜到或者通過方程解出CPD，但是一旦變量非常復雜，則我們很難獲得CPD了。左圖實際上是均勻分布，右圖則可通過3元1次方程組對CPD進行求解。馬爾科夫鏈通過多次迭代后可以達到收斂的效果，如果要馬爾科夫鏈收斂，則有以下兩點要求：1.馬爾科夫鏈不允許有管進不管出的環(huán)2.任何一個狀態(tài)必須有回到自身的回路3、使用馬爾科夫鏈使用馬爾科夫鏈的前提是馬爾科夫鏈已經收斂（mixed）。實際上，判斷馬爾科夫鏈迭代收斂是一件不可能的事情，而判斷其未迭代收斂卻是簡單的。1.對于馬爾科夫鏈而言，蚱蜢落在相鄰窗口的次數(shù)應該是相近的（因為總是在相鄰窗口中跳躍）2.蚱蜢從任意狀態(tài)出發(fā)，最終收斂的結果應該是相近的。一旦馬爾科夫鏈迭代收斂，實際上我們得到了變量

x

的分布。算法：A<迭代收斂>1.選擇不同的狀態(tài)C個作為初始點（故有C條鏈）2.概率迭代T次（C條鏈同時進行）3.對比不同鏈條的相同窗口，觀察次數(shù)是否相近4.假設馬爾科夫鏈已經收斂B<采樣推理>1.選擇一個初始狀態(tài)2.依據(jù)轉移概率計算所得采樣3.將所得采樣放入采樣結果集合中4.利用采樣結果集合計算所需要的量

4、Gibbs采樣之前以貝葉斯模型為例，展示了由葉向根的采樣算法。然而概率圖模型在實際使用中，往往使用馬爾科夫模型或者混合模型。馬爾科夫模型的有環(huán)特性使得其難以使用由葉向根的采樣算法。Gibbs采樣是一種簡單快捷的采樣方式，其可用于馬爾科夫模型推理。其使用方法與貝葉斯模型的采樣相同:1.假設某個隨機變量x1為未知，其他隨機變量均為已知。2.依據(jù)該條件下的概率P(x1|x-1)，對未知隨機變量x1進行采樣3.將采樣結果迭代入下一次采樣過程中如圖所示：如果已知L,S，則可假定D與I的值，對G進行采樣，之后依據(jù)G的值重新對D進行采樣。這個思路聽起來很簡單，但是更致命的是這個算法實現(xiàn)起來也非常簡單。從圖中可以看出，實際上采樣的“核心”——條件概率值，僅僅和相鄰的變量有關，而和圖的整體無關?。。〉玫綏l件概率后丟進均勻分布采樣即可。

5.

MetropolisHastingsAlgorithm從上段可以看出，Gibbs采樣算法是一種異常強大的算法，在構建MRF后，只要進行計算，就能夠解出需要的概率。其缺點是面對難以發(fā)生的小概率事件需要多次迭代才能夠收斂?？紤]到此缺點，計算機科學家們設計了MH算法。這是一種在理論上就能保證收斂的算法。該算法有一較強的約束條件，表現(xiàn)為下式：簡而言之，就是隨機變量轉移到下個狀態(tài)的可能性與其從下個狀態(tài)轉移回當前狀態(tài)的可能性相等。馬爾科夫鏈狀態(tài)代表隨機變量的取值，轉移概率表示在當前狀態(tài)下轉移到下個狀態(tài)的可能性。本算法則提出了更強的約束，在不破壞轉移可能性的前提下，引入了狀態(tài)發(fā)生概率的約束，來強行達到平衡。而這樣約束所換取的好處就是某個隨機變量的狀態(tài)概率分布成了唯一的。（傳統(tǒng)的馬爾科夫鏈只要求T求和后等于1）pi(x)是我們所求的目標。如何選擇合適的T(x->x')就成了當前的主要任務。這里采用了一個很trick的方式來進行解釋。首先，由局部參數(shù)決定x'，然后由"把關概率A"決定是否執(zhí)行轉移。A的設計有以下約束：如果令A(x'->x)=1,則A(x->x')=p.這是把關最松的情況，也就是讓螞蚱跳的盡可能快。Q的設計據(jù)說是一份年薪65W美元的工作。。。Q應該盡可能設計的扁平，也就是x轉向x'的可能性要盡可能大，但是這會導致A變小...導致最終收斂變慢。注：實際上，MH算法是提出了一種較強的約束，每個狀態(tài)相互轉移的可能性相同，而每個狀態(tài)本身發(fā)生的可能性卻可以是不同的。就像是人可以居住在城市不同的地方，如果你住的離學校近，那么你到學校的路就比較堵（轉移的慢），如果你住的比較遠，那么路可能更暢通（轉移的快）人住的遠近是隨機變量沒錯，但是如果做出這種假設，人就有了更多選擇的權利，遠的地方有更大的可能性吸引人去居住。6.基于馬爾科夫隨機鏈蒙特卡洛算法的配對問題求解配對問題本身是一個由MRF建模的問題，解鈴還須系鈴人，MRF引出的問題由MC來進行求解也算是一種循環(huán)吧。。。。。。圖示問題中，紅點與藍點進行匹配，一個紅點有多個藍點可以選擇，其親密程度由指數(shù)函數(shù)與抽象距離函數(shù)來進行描述。最終的目的是使得P（X1=v1,X2=v2....)達到最大。換一個思路來思考，假設紅點和藍點都是特殊的磁鐵，紅點會吸引藍點，磁力和距離有關。如果采用MC的方法來進行求解，則每個紅點是隨機變量（5個磁力小球），藍點是狀態(tài)（8個鐵塊）。蒙特卡羅過程則是所有的磁力球一同落下，看看最終誰和誰吸在了一起。如果用算法來描述一同落下就比較困難了，計算機科學家提出的算法如下：1.隨機變量與狀態(tài)已經一一配準2.某隨機變量重新選擇一個狀態(tài)3.被搶走配偶的隨