(閱前註:

1. 閱讀本文前已全面了解統計機器學習中最大熵模型(MEM),有向圖模型(DAG),無向圖模型(UGM)等相關內容會獲得更好閱讀體驗。2. 本文不是教科書式的介紹,而是借技術分享文自由而不受限的形式,把嚴謹的教材(尤其中式教材)中為了主線的清晰,講清楚「怎麼辦」的內容以外,卻部分難以展現的關於「是什麼」和「為什麼」的一些思考分享出來供大家參考,這些內容考試絕不會考,但筆者認為這一定是能否擁有解決問題能力的關鍵。3. 本文所有概念中文名僅出現一次,下文英文簡稱可與之對照。)

相信大家在做機器學習相關研究中,都或多或少遇到過以下這些概念:最大熵(ME),指數分布族(EFD),貝葉斯網路(BN),馬爾可夫隨機場(MRF),動態圖模型(DBN),隱馬爾可夫模型(HMM),條件隨機場(CRF),最大熵馬爾可夫模型(MEMM),加權有限狀態自動機(WFST),喬姆斯基文法(Chomsky Grammar)等等,這些初次見面看起來頭大,二次見面如同初識的概念可能一定程度上困擾著我們,這些方法到底如何選用?為什麼要搞出這麼多概念來?拋開演算法執行層面的具體細節,他們產生的來龍去脈是什麼?有著怎樣的聯繫?今天,就和大家分享一下我在這部分內容上的一些思考。

1. 一個中心:最大熵準則這是一個原則性的指導思想,實踐中在其他應用指導下才能生效,而平常我們用的極大似然估計方法,是最大熵準則求解步驟中的最後一步。先來看最大熵模型的定義(這裡統一用求和代表離散隨機變數的求和和連續隨機變數的積分,二者公式推導沒有本質區別):

吳軍老師在數學之美里對最大熵模型的通俗解釋是「不要把雞蛋放在一個籃子里」,所以我們需要找一個滿足條件限制的儘可能「均勻」的分布來作為估計分布,熵最大的分布最「均勻」。我想,猜測一個硬幣正反面的概率都是0.5,這是均勻,但當分布有限制的時候,平常理解的平均分配已經無法指導什麼是最優分布了,而最大熵其實只是在無任何其他約束或約束夠簡單的時候(比如ABCDE五種可能結果,限定AB兩結果之和為定值),和平常說的「均勻準則」恰好同解。那麼到底為什麼要求分布的最大熵來作為估計結果呢?這一準則為什麼會屢試不爽,奉為經典?本質到底是什麼?跳出最大熵框架和以往知識的約束,我們來憑直覺設想一下,問題就會迎刃而解。現在要你估計一個隨機變數的分布,滿足若干數字特徵條件後,在分布空間內還有無數可行解,那到底選哪一個呢?理論上,此時選擇任何一個可行解都是沒有問題的,即一個沒有拋過又沒見過,但知道只有兩面而且每次只會從中拋出一面時候,你估計正面概率為0.99,0.5和0.01都有可能是正確答案,因為我們對硬幣拋出正反面分布的先驗一無所知,只能是均勻分布,以上三個猜想命中正解的似然相等!既然相等,為啥一定要猜才0.5看似更合理呢?因為我們估計分布的目的,有時不是為了得到一個完全正確概率最大的分布(反正那也接近0),而是為了得到一個任何情況下,效果都不太差的分布,即,對於最差的情況,我估計的分布和真實分布也要足夠的接近;即,真實分布的樣本在我估計分布上的似然要是最大的;即,交叉熵(CE)最小。寫成公式就是:

繼續推導一下,有驚喜:

可以證明,CE是f的凸泛函數,故只要ri(x)是仿射函數,上述推導成立。看到了吧,所謂最大熵準則呢,既沒有吳軍老師解釋的那麼通俗,也沒有那麼深奧不可理解,利用最大熵準則求出來的分布,其實是在約束條件都成立的條件下,在最差情況下,表現最好的分布,我們只需要理解和承認表現最好等價於似然函數最大,那這樣分布的求解實際上就是求解最大熵分布,甭論熵的物理意義,我認為在統計模型中最好理解的意義一定在此。另外,最大熵分布的求解仍然用到優化問題的對偶性質,可以證明,一般的機器學習問題loss設定成估計分布對經驗分布函數交叉熵(用極大似然求解參數),其實是最大熵模型中選定若干特徵函數ri,並以樣本估計值作為其真值時的最大熵模型的解。證明如下:

故綜上,尋求的是最差情況下的最好解,是我們大多說機器學習問題loss設定成交叉熵(極大似然)的理想答案的性質,只有我們確實需要這樣性質的解的時候,最大熵準則以及表面的損失函數,才是有效的。而我們還有一些如svm背後的hinge loss自成一派;多臂老虎機(MAB)類問題UCB追求收斂速度(若追求期望等也可寫出其他策略);而MSE loss求的是期望值(在正態分布下等價於極大似然),absolute loss求的是中位數,sign loss求的是眾數等,可以看成是把分布空間限定在單點分布時候不同損失函數的求解性質。為啥我覺得最大熵模型是統計建模的中心呢?因為你看看,我們市面上見得到的聯合分布和條件分布表達式基本都是其特例或者其邊緣分布結果。他們都是在給定隨機變數空間和特徵函數的條件下的最大熵模型的解。那麼多複雜的分布和參數性質居然背後有一個統一的思想來統領和指導,我不得不再次驚嘆於數學之美。到此,從最開始無腦迷戀最大熵的美麗形式,到百思不得道的思索,最後窺見其原理的簡明以及局限,真理總是越辯越明。

在這套框架指導下,我們的前輩們還發明了諸多適應於不同數學結構和實際問題的經典模型,仔細研讀會發現他們都是在最大熵的基礎上結合具體問題延展的可行的處理策略以及建模思想,無不結合了領域知識帶來的機理假設使得模型更合理可行。我們雖然通常是做基於統計的機器學習,那隻不過是完全明確的機理不得而知時候採取的建模策略,但是對機理把握越明確,越能同時向模型里注入知識(定性特徵後由樣本表達和定量限定後劃定函數空間等)和數據才能使得機器學習系統能越來越聰明,以便在一件小小的事情上達到自動駕駛,幫助人類開啟新征程的探索。接下來,我們就來看看前輩們給我們留下的,在最大熵的框架下,面對實際問題的行動指南。

(關於最大熵模型的求解公式推導以及學習演算法,以及與其關係密切的指數分布族函數的性質我們另外找專題再討論,本文專註講清楚其來龍去脈和圖模型之間的關係。)2. 兩種世界觀:貝葉斯網路和馬爾可夫隨機場我們對客觀事件發生的可能性大小計算通常轉化為了在給定樣本空間內求解某概率密度函數,第一個要解決也往往是被忽略的問題是,你選取的隨機變數是哪個對象的哪些屬性,描述的是生成過程中的哪個階段?是否有重複和遺漏?他們之間的關係如何呢?如何對變數複雜繁多,生成過程複雜的事件進行最大熵特徵的有效書寫,進而完成建模呢?前輩給我們留下的有向圖(DAG)和無向圖模型(UGM)給了我們答案,他們用兩種完全不同的思考角度完成對物理世界的數學抽象。2.1 DAG2.1.1BN

BN覺得,世間萬物都是依序產生的,我們也可以完全觀測或了解每一道工序下描述對象的全部隨機變數信息,後產生的變數總是按照一定規律受前面若干變數的影響,當其依賴的變數全部產生時,它也應運而生,沒錯,這是個時序模型,我們暫且拋開生成速度,給定固定的變數生成順序,也假設明確知道該系統運行的開始和終止。對於這樣一個生成系統,描述變數和生成過程完全固定,我們應該怎樣去描述和建模呢?其數學結構即DAG,對應有BN的聯合概率密度寫為:

第二個式子是指數族分布表達式,由此得到了最終的聯合概率密度表達式。能這麼寫其實是源於我們已經對此局部做了最大熵建模,並把其轉化為最後一步參數求解了。這裡,theta為固定參數,可能是要從數據中學習估計的,或者待求後驗分布/期望的中間參數(MAP、PME),hi函數對應那些已知固定的參數對分布函數的影響,為外部給定先驗,不參與優化(常常設為常數1),Ai僅為參數的函數和隨機變數無關。且可喜的是,這一看似複雜的形式下有著良好的性質,且對於已知的觀測變數集,對應的CE loss,即最大熵解是有解析解的,簡單的可以直接寫出表達式,或者GD,IIS等求解即可,這裡與本文核心思想無關,暫不更多展開。由此看到,DAG模型的建模思路是,以生成的角度搞清楚研究對象每個事件的生成依賴關係,得到表達依賴的DAG結構以及結構所含的具體特徵表達形式(有序的每個隨機變數的依賴變數集(注意要無環)以及具體方式是其根本數學結構),至此,用條件概率公式即可寫出整個事件的聯合分布,這樣的寫法也一定滿足圖上任意兩個變數集是否相互獨立的結論在公式上的結論,這些都源於因果關係的初始設定。對於任何完全或不完全的觀測可以利用此數據進行參數估計,於是關於此系統的任何條件,邊緣或者聯合概率均可由此得到,建模完成。舉兩個例子簡單說明一下,用類別分布抽出一個某顏色的小球,並選擇按下一個顏色的開關,最後球所顯示的顏色分布;01分布決定是否打雷,打雷作為條件01分布是否下雨,打雷和下雨發生與否決定01分布是否降溫,等等。這些生成機理多由外部知識和大量的人類觀察決定,其好壞決定了模型利用數據的能力和模型上限。但話說回來,這裡的父節點隨機變數集和孩子隨機變數之間的因果關係不必真的存在,我們可以任意給定一族變數的依賴關係並如上建模,只不過,我們相信,利用人腦思維得到的「因果關係」,對應到DAG圖中的關係以後,能夠盡最大可能傳授給機器這一貼近真實的機理,這樣,再用觀測變數集合來消除variance就會有著更好的效果。這個因果關係到DAG有向關係是人機配合的核心介面之一:我負責定性觀察因果關係,你負責把定性算成定量結果。所以BN向我們提供了一種使用最大熵模型建模的策略:分解成若干有序的條件分布,在每個條件分布上用最大熵模型,各部分可獨立處理,合併後即為所求。另外,考慮生成時長的經典模型是Poisson Process和CTMC,和本文主線無關,這裡暫不展開了。2.1.2 DBN很遺憾,能夠用指定個數並含義固定不變的變數來描述的系統是極其簡單而不符合實際的,要麼中間有嚴重的環節缺失,使得因果關係並不牢靠。一個常見的情況是,研究對象是天然的變長序列,即一階張量(高階同理)。比如待檢測變異的基因測序序列,待進行某種標註的給定文本序列。其位置屬性並不重要而一旦對位置建模則處理序列的長度有限且參數數量隨著序列長度線性增長是不可接受的。故綜合數據量和模型複雜度的匹配,假設滿足的一個基本規律是,序列滿足時齊性(homogeneous),其在每一個單元內服從近似相同形式和參數的分布,這樣,在損失很小bias的情況下(可能並不嚴格時齊),把模型參數數量從與序列長度成正比降為與序列長度無關,而僅從基本單元的階數去作為超參調整模型與數據的匹配,以達到最好的學習效果,這就是DBN模型的思路和策略,在暫不要求對開始和結束狀態建模的條件下,為已知序列到序列的映射標註問題提供了通用思路,其基本表達式為:

注意m是每個樣本所特有固定的序列長度,f函數為所有i所共用,不是i的函數,其地位相當於DAG中的一個完整的生成過程。注意添加的S和E,是為了對開頭結尾處可能服從的特殊規律建模,哪怕不對結尾開頭建模,這個符號也使得於是我們在表達式書寫上能夠用統一的形式。

這樣我們對於無須對序列長度建模(往往是給定已知序列的標註)問題,在動態變化的定長序列空間內給出了概率建模思路,即,其生成是基本單元的延展,自然的根據這個動態DAG圖,分布函數是每個共享單元內條件概率的乘積。後面我們會看到,這裡的BN和DBN實際上都是WFST模型的一個特例,更一般的形式我們在後面馬上介紹,另外這裡的共享參數延展特性在後面的CRF模型中同樣應用到,可對照著來理解。2.1.3 WFST無論是靜態圖還是作為其周期延拓的動態圖,繞不開的一點是,在有序產生變數的過程中,對可能的分支狀態的描述無能為力,對所有變長序列統一空間的概率分布函數無法估計。(或言,DAG只是WFST模型中僅有一條沒有任何分支的從開始到結束的狀態鏈的特例,DBN又比BN多的地方在於此鏈構成一個圈)比如,以籃球比賽為例,實際情況可能是,某人以01分布決定傳球還是出手,如果出手則以category 分布決定誰拿到籃板球或者出界,如果有人拿到籃板球決定他要幹嘛,如果出界則決定誰發邊線球;如果傳球,則以01分布決定是否有人搶斷以及如果沒有搶斷誰拿到球後準備幹嘛,如果搶斷,搶斷後準備幹嘛。。。。。。可以看出,每一個隨機行為的結果不僅影響到後續行為的分布參數,還會以分類變數選擇的方式影響到其分布類型,包括變數空間。所以,那種固定的DAG對應固定的變數有序生成的模型已經不適用了,整個系統的狀態連接不能僅僅限定於單鏈的線性,對系統的建模方式應該是狀態空間及在該空間下輸入信號空間作為條件,決定當下輸出及可能的新狀態的分布,這樣能夠描述清楚所有可能行為變數以及其對應可行條件。一次離散隨機過程相當於在從開始到結束的狀態空間內的遊走,每一步都依概率選擇路徑和輸出不影響下一步行為的信號,我們直接觀測的,便是這個信號了。這便是WFST的存在理由,對一個穩定的時序系統,不考慮時長,系統的運行可以看作狀態X輸入=輸出X新狀態的循環,這樣可以完美解決上面的建模問題。表達式如下:

篇幅有限,關於其求解的詳細演算法我們另外介紹,這裡闡述的思想是,通過這一建模框架,我們可以得到任意輸入輸出為序列或可以表達為序列的任務建模,我們定義好輸入空間A,狀態空間Q,以及給定Q,A時發射的B,結果Q,以及發生概率,這可以描述任一穩定系統接收外界信息後的隨機反應方式,概率建模中往往也轉化為求概率最大的那個解的問題。這為我們構建客觀模型提供了更加靈活的框架,不必再受限於線性的狀態轉移結構而是可以任意設置以接近真實情況,也可由此更靈活地設定變數空間,而在這個框架下的每一個局部的狀態轉移分布,即K(Q2,B|Q1,A)=K1(Q2|Q1,A)*K2(B|Q2,Q1,A),其看作條件概率密度函數時仍是用最大熵模型建模和使用DAG基本單元看待,其中若K2(B|Q2,Q1,A)=K2(B|Q1,A),稱之為Moore Machine(HMM就是最簡單的例子),否則稱為Mealy Machine。2.2 UGM=MRF

到此為止,我們介紹完了DAG框架下的條件概率建模思路以及由之產生的諸多拓展方案。UGM的拓展方式同前面完全相同,DBN對應過來就是CRF,WFST每個轉移單元的建模本就可以選擇DAG或UGM兩種方式,這裡就模型堆疊拓展部分不再重述,但對單元內建模思路的獲取的不同予以分析和比較。在DAG的世界裡,一切變數是有因果的而順序產生的,但UGM的世界觀把一個建模單元看作一個整體對象,其隨機變數與屬性函數作用在一個對象上的映射對應,故UGM中的變數都是無序的對象屬性,其相互關聯的原因在於共屬於同一個對象(可以看作是由同一對象產生的,在未知對象時候,理論上應該兩兩相關),那如何構建相互連接的邊呢?我們這樣來想像一下,一個對象的全局描述可能有很多維度,他們稠密地互相連接,相互影響,有些維度是天然已知有固定值,有些未知且不可觀測,有的可以觀測,那這些可以觀測的變數之間有邊相連就等價於,建模者認為在當前已知條件下,二者獨立,互不干擾,或其相關性在當前數據量條件下忽略更有優勢。比如認為一個人的性別和他生的孩子的性別是獨立的,沒有邊相連,而性別和職業卻相關,有邊相連,這裡的連接方式即代表我們人注入計算機的知識結構框架,作為能量幫助計算機理解客觀世界。當圖構建好以後,就完成了物理規律向數學結構的抽象,那任意兩個變數集是否獨立的結論也由圖結構定下來(Markov Property),和前面一樣,DAG通過因果關係得到了依賴關係進而確定獨立關係,這裡通過兩兩相關關係確定圖結構進而確定獨立關係,這兩個方案都給人類提供了足夠友好而可行的介面,這便是圖模型的價值。接下來,Hamilton Clifford Theory告訴我們概率分布可以寫成如下形式:

Ci是圖中所有的max clique,可以證明,這樣的形式是滿足Markov Property的,且是不損失bias條件下形式最簡的。其實這裡應該能理解,我們通過人為給定兩兩變數是否直接相關來獲得UGM結構,而這個結構會自帶對所有兩個變數集是否獨立的判斷(前面DAG則是給定所有變數有序的因果聯繫,而得到這個獨立與否的判斷),讓人去思考最簡單直接的問題,而把這些信號組合起來構成一個模型系統進行複雜計算是計算機的工作。由此我們在每個單元內應用最大熵模型得到的指數族分布解即為第二行的表達結果,故Hamilton Clifford Theory其實就是在由UGM限定變數獨立關係的條件下最大熵模型的具體形式。這裡提一個小點,我們在PRML一書中看到過關於DAG和UGM表達模型能力的表述,舉例了immorality結構UGM無法表達而四邊形結構DAG無法表達的例子,最後說明二者為有交集但互不包含關係且在模型空間中還存在著二者都無法表達的部分(如下圖所示):

其實,這些例子背後的本質是,變數間的獨立與否關係是個變數集上的二元關係,DAG和UGM均只能表達其上有限的一部分(後文還介紹的因子圖可以看作UGM的變種,直接給出互不包含的max clique得到解而省略了找尋步驟,只不過對人腦信息分析提高了難度),另外,在獨立條件滿足時,我們往往也僅把分布搜索空間限定在指數分布族,這也使得我們圖模型可以表達的分布和全體分布的差距,科學研究總是把起點設置得很高使得理論退稿看起來很美,好在這裡的理論基礎對應的本質還是很漂亮和簡單:這些分布形式假設加極大似然估計的結果,一定在最不利的情況下有最好的效果。以上便是DAG和UGM概率建模的全部思想,它期望打通人腦定性知識和結構化數據的聯繫,為最大熵全局模型提供建模變數集合分割的方案,使得分割能簡化每一個子問題的參數空間且由於人腦知識的保證也不至於偏離於真實情況(或在數據有限情況下的折中)。在每個子圖內,我們應用最大熵模型的求解結論,去劃定真實應用的特徵函數(或根據特徵模板以及數據自動選擇),進而求得在人類知識指導下,這樣的樣本條件下,在最差情況下最好的解來。那接下來,我們進一步比較兩種圖模型建模的細節異同,以及在線性鏈上的神奇結論。3. 三條等價鏈:隱馬爾可夫模型,條件隨機場,最大熵馬爾可夫模型在正式探討三類線性鏈圖模型和他們的異同之前,我們先繼續推導一下用DAG和UGM的介面進行建模變數集劃分以後,分布函數極其參數空間的形式:

可以驚喜地發現,無論DAG還是UGM,甚至factor graph都是提供一種變數集合劃分方式,DAG的每個條件概率表達式涉及的條件和目標變數集合正好對應於UGM所得的max clique!而且他們建模的結果中只要每個子圖是最大熵模型得到的指數族分布,那聯合概率也是最大熵模型的指數分布族函數!由上面的公式對照可知,二者模型等價當且僅當:

可以看到,DAG在同等變數集合劃分後的建模中,DAG予實質的特徵函數更多的限定(h函數在一般的建模中往往設置為1,不予考慮),包括條件分布條件變數必須以線性函數得到特徵函數(充分統計量樣本函數)對應參數,此時歸一化函數A也應是變數條件和參數條件和分離的,剩餘不分離部分也是各自特徵函數向量點乘函數得到結果,當UGM的設定函數形式沒有超出這些限定,或可尤其表達的時候,二者建模完全等價。否則,在二者變數劃分方式不同或者DAG函數形式不能表達為UGM對應條件概率表達的時候,二者不可混同,PRML一書中舉的二者不可混同的例子也對應上述表述的情況。當然,我們整個討論問題的範圍都在指數分布族內,其含有分布指數形式以及內部特徵參數點乘得到概率密度值的限定,超出這些限定的分布函數也自然不可表達,而好在,我們的指數分布族函數源於最大熵,最大熵的分布就一定有那個性質,讓我們再來說一遍:充分統計量值測量準確時候,估計出來的分布一定是最差情況下最佳的。好了,有了上面的基礎再看HMM,CRF,MEMM就有一種會當凌絕頂,一覽眾山小的快感了。HMM和MEMM是DAG,區別在於HMM的隱藏鏈Yi生成Xi,MEMM的Yi則由Xi和原有的歷史Yi-1,共同生成,且此關鍵條件分布用UGM建模聯合分布後用條件概率公式得到,而CRF則是徹頭徹尾的UGM(他們的高階形式也類似)。他們三者對應的由圖結構決定的變數集合劃分方式完全相同,從表達能力上看,CRF是最佳最靈活的,而HMM,MEMM分別有所限定,可以看到,在X序列觀測已知推測Y序列的問題上,在我們平常的建模策略里,他們是基本等價的。詳細公式推導如下所示:

可以看到,他們都是指數分布族分布里的函數,只要特徵函數(充分統計量樣本函數)相同,他們都是等價的(其中CRF的第一個單元建模了後兩個模型中前(k-1)個單元,與他們對應後相應的基本單元也可以相互對應了),且表達能力上CRF>HMM and MEMM,後二者則各有千秋。當然他們的共用適用範圍都是不對時長間隔和開始結束建模的序列上元素一一映射問題,共同假設是序列上的時齊性,反映在公式里即是:序列上各位置單元共享函數形式與參數值,其任意長度序列的特徵函數可寫作單元特徵函數和的形式,這樣使得不同長度序列,不同位置之間能夠通過共享參數,互相學習達到從樣本信息中中估計分布的效果,這便是線性鏈模型的終極精髓了。但是,這樣的線性鏈拓展顯然還不能建模像自然語言這樣有著更複雜生成機理的對象,於是狀態機模型,文法理論和因變數的引入,再一次使我們的模型系統貼近真實世界。

4. 四階文法:狀態機模型與隱變數建模

在上文2.1中,提到DAG模型的幾個變種,可依線性鏈擴展處理變長序列,但對變數空間變長以及生成過程存在分類狀態分支的情況無能為力,另外,雖然我們假設對象聯合分布是指數分布族分布是合理的,但是往往觀察的缺失使得我們常常算的是邊緣分布,而這並不再保證指數分布族性質,因此,我們需要引入WFST模型以及由此帶來的對隱變數的考慮和相應處理。這裡的經典理論是Chomsky Grammar,關於它和WFST建模理論,以及和基本圖模型甚至神經網路之間的關係,還有在含有隱變數條件下的EM類演算法的內容較多,這裡暫時點到為止,我們在其他文章中再單獨成文予以詳細闡述。好了,讀罷此文,不希望大家又多會背了一些公式,也不希望連公式也不曾瀏覽,而是對我們教科書上知識產生的來龍去脈形成自己的理解:我們希望求解一個最壞情況下似然性期望最高的分布,於是我們又對偶理論推導出了最大熵目標函數;又由對偶理論得到其函數形式為指數函數,並簡化設定為指數分布族函數;又依據實際問題中可能從變數生成和屬性測量兩個角度指導模型變數關係並化簡模型得到DAG和UGM兩類模型;然後對線性鏈結構予以時齊性假設來拓展基本單元解決得到DBN和CRF兩類模型;最後引出還可能遇到分支的生成過程以及不可觀測變數存在時候需要更加完善的WFST數學結構來解決的情況。這是我理解的統計建模在最大熵的根基下的的全部脈絡,且本文並不涉及演算法操作層面的嚴謹敘述,相關內容可自行查閱教材。這裡我把我基於是什麼和為什麼理解分享出來,讓大家看到教材里寫的怎麼辦時能夠更加有的放矢,頓覺知識財富之美妙和價值,就足夠了。內容不一定完善,供大家參考,希望真理越辯越明。本人自幼熱愛數學建模,後專攻統計建模,近年在生物序列,文本序列等序列建模領域深耕。學習和工作中無數次碰到ME,EFD,BN,MRF,DBN,HMM,CRF,MEMM,WFST,Chomsky Grammar等等,對其中來龍去脈,相互關係頗為疑惑和著迷。遂翻閱資料無數,夜以繼日思考,終得此文,以茲紀念。

更多精彩內容,歡迎關注MatheMagician.


推薦閱讀:
相关文章