機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘-大眼睛實(shí)驗(yàn)室

1、機(jī)器學(xué)習(xí)的困惑與歷史的啟示,王玨,第九屆機(jī)器學(xué)習(xí)及其應(yīng)用研討會(huì)2011年11月，清華大學(xué),自然模型,,[采樣],樣本集,,模型,[算法],,,[交叉驗(yàn)證],假設(shè)iid,統(tǒng)計(jì)機(jī)器學(xué)習(xí)的麻煩,？？？？？,,,[設(shè)計(jì)實(shí)驗(yàn)],,,問(wèn)題：模型是自然模型嗎？,統(tǒng)計(jì)機(jī)器學(xué)習(xí),如果數(shù)據(jù)不充分，在大變量集合下，如何設(shè)計(jì)實(shí)驗(yàn)，獲得新數(shù)據(jù)。,統(tǒng)計(jì)機(jī)器學(xué)習(xí)的困難：實(shí)驗(yàn)設(shè)計(jì)存在組合問(wèn)題。iid成為與自然模型無(wú)關(guān)的假設(shè)！,特殊函數(shù)的逼近,社會(huì)的需

2、求,生物、網(wǎng)絡(luò)、金融、經(jīng)濟(jì)和安全等眾多領(lǐng)域，大變量集合的海量數(shù)據(jù)不斷涌出，社會(huì)迫切需要分析與處理這些數(shù)據(jù)的有效理論、方法與技術(shù)。,尋找分析與處理大變量集合海量數(shù)據(jù)的新理念、理論、方法與技術(shù)成為當(dāng)前迫切的任務(wù)。,歷史的故事,線性感知機(jī),基于最小二乘的Rosenblatt的感知機(jī)(1956)，其本質(zhì)是多變量空間上的平均(回歸)。,1902年，James的神經(jīng)元相互連接1943年，McCulloch和Pitts的神經(jīng)元工作方式1949年，

3、Hebb的學(xué)習(xí)律。,,貢獻(xiàn)是：多變量回歸的計(jì)算方法(神經(jīng)網(wǎng)絡(luò))。,基函數(shù)：L = ?1D + ?2I + ?3G + ?4S設(shè)計(jì)算法，確定?，獲得模型,疑問(wèn)是：只能解決線性問(wèn)題，不能滿(mǎn)足實(shí)際的需要。埋下被批評(píng)的口實(shí)。,20世紀(jì)70年代面臨的選擇,統(tǒng)計(jì)優(yōu)化(平均)：線性感知機(jī)統(tǒng)計(jì)模式識(shí)別,復(fù)雜信息系統(tǒng)(結(jié)構(gòu))：專(zhuān)家系統(tǒng)句法模式識(shí)別,選擇,非線性問(wèn)題計(jì)算效率,,,專(zhuān)家系統(tǒng)合理復(fù)雜問(wèn)題求解實(shí)現(xiàn)智能系統(tǒng)的理想,,,Duda a

4、nd Hart[73],從Bayes判別(分類(lèi))，引入損失函數(shù)，變?yōu)檎齽t化問(wèn)題,If [D=0]?[G=A] then[L=0]If [I=0]?[G=A] then[L=0]If [D=1]?[I=1]?[G=A] then [L=1],AI,1969年，M.Minsky發(fā)表顛覆性的報(bào)告， “Perceptron”。表象是以XOR問(wèn)題向以平均為基礎(chǔ)的感知機(jī)發(fā)難，本質(zhì)是試圖以結(jié)構(gòu)方法代替平均。全書(shū)使用拓?fù)渥鳛楣ぞ摺?1956年，

5、以復(fù)雜信息處理為契機(jī)，提出AI。其動(dòng)機(jī)有二：其一，發(fā)展處理符號(hào)的方法，其二，處理非線性問(wèn)題。,,過(guò)分強(qiáng)調(diào)獨(dú)立性，使得描述任何一個(gè)問(wèn)題，需要窮舉出所有可能。80年代，耗資巨大的CYC“失敗”了。,需要統(tǒng)計(jì)方法成為共識(shí)。,20世紀(jì)80年代面臨的選擇,概率圖模型(Bayes學(xué)派):Markov隨機(jī)場(chǎng)Bayes網(wǎng),人工神經(jīng)網(wǎng)絡(luò)(頻率學(xué)派):BP統(tǒng)計(jì)機(jī)器學(xué)習(xí),選擇,結(jié)構(gòu)學(xué)習(xí)的困難先驗(yàn)的結(jié)構(gòu)先驗(yàn)概率分布推斷是NPC,,,字符識(shí)別，網(wǎng)絡(luò)

6、數(shù)據(jù)建模誤差界指導(dǎo)算法設(shè)計(jì)算法基于線性感知機(jī)無(wú)需先驗(yàn)知識(shí)，無(wú)推斷考慮泛化為核心,,,Gibbs[1902], Wright[1935]Clifford[1971]Pearl[1988，89],統(tǒng)計(jì)機(jī)器學(xué)習(xí),1991年，Vapnik借用在AI中的PAC，給出基于iid的誤差界，基于PAC的統(tǒng)計(jì)開(kāi)始成為主流,1986年， Remulhart發(fā)表PDP報(bào)告，包含非線性BP算法，解決XOR,逼近非線性函數(shù)。學(xué)術(shù)價(jià)值不大，人們開(kāi)始重新

7、嘗試“平均”方法。,從ANN到SML，發(fā)展得力于對(duì)字符識(shí)別的成功,神經(jīng)網(wǎng)絡(luò)?基于PAC的機(jī)器學(xué)習(xí)?基于統(tǒng)計(jì)學(xué)的機(jī)器學(xué)習(xí),貢獻(xiàn): (1)基于iid的誤差界指導(dǎo)算法設(shè)計(jì)，(2)算法設(shè)計(jì)返回感知機(jī)，線性算法，尋找線性空間(核映射)。,基于PAC理論，誤差界以1-?概率成立。這個(gè)參數(shù)在泛化意義下的解釋?zhuān)豪硐耄?應(yīng)該趨于0，但是，誤差界將趨于無(wú)窮，成為平凡界。,新世紀(jì)開(kāi)始，統(tǒng)計(jì)學(xué)家加入SML，完全放棄PAC(Hastie)。,維數(shù)災(zāi)難,高維空間上

8、的統(tǒng)計(jì)理論，多重積分是麻煩，補(bǔ)充“合適”樣本是麻煩?！巴植肌敝荒芡Ａ粼诩僭O(shè)上，無(wú)法實(shí)施。,在高維空間(成百上千)建模，最大的危險(xiǎn)就是空間大的程度使得再多的樣本，在這個(gè)空間上也是稀疏的。,,由于困難具有本質(zhì)性，平均遇到大麻煩！,概率圖模型,將平均放在局部，避免了維數(shù)災(zāi)問(wèn)題，同時(shí)保證了泛化和模型的可解釋性，關(guān)鍵是結(jié)構(gòu)，將局部的平均構(gòu)造起來(lái)。,基于平均的研究已經(jīng)過(guò)去20余年，2009年，Koller出版巨著(近1200頁(yè))，概率圖模型。,,

9、結(jié)構(gòu)(全局) + 平均(局部),,將問(wèn)題考慮為求解Bayes問(wèn)題,一、表示 二、推斷 三、學(xué)習(xí),概率圖模型的三個(gè)要素,表示---I-map,P(I,D,G,L,S)=,P(I),P(D | I),P(G | I, D),P(L | I, D, G),P(S | I, D, G, L),P(D, I)=P(D)P(I),P(L|G),P(S|I),,,,,,,P(D),P(L, I|G)

10、=P(L|G)P(I|G),I與D相互獨(dú)立,L只與G有關(guān)，與其他獨(dú)立,S只與I有關(guān)，與其他獨(dú)立,P(I),P(G|I,D),D?I,L ? I,L ? D,S ? D,S ? G,S ? L,I-map={,},P(L, D|G)=P(L|G)P(D|G),求解Bayes問(wèn)題的策略,使用Markov網(wǎng)表示Bayes問(wèn)題。,(1)連接的節(jié)點(diǎn)保持連接。(2)X與Y有共同子孫，X與Y連接。,由于Bayes網(wǎng)可以簡(jiǎn)單地轉(zhuǎn)化為Markov網(wǎng)，因此

11、，在統(tǒng)計(jì)上，這個(gè)方法可以歸入Bayes范疇，Markov網(wǎng)成為求解Bayes問(wèn)題的一個(gè)方法。,求解Bayes問(wèn)題有兩個(gè)途徑：(1)直接求解，困難；(2)變換為Markov網(wǎng)，使用優(yōu)化方法求解。(與Duda & Hart的思考一致)。,推斷---Bayes問(wèn)題,推斷，概率查詢(xún)(Y邊緣)：根據(jù)給定圖，計(jì)算P(Y | E = e)。在證據(jù)E=e條件下，Y出現(xiàn)的概率(邊緣概率)。,(1)根據(jù)給定BN，計(jì)算聯(lián)合分布：P(?) = ? P(

12、Xi | PaXi),(2)計(jì)算在E下變量Y的邊緣分布：P(Y | E) = ?X??-{Y}-EP(?),??計(jì)算是NPC問(wèn)題(或多重積分，Bayes問(wèn)題)。,求解Bayes問(wèn)題的兩條路線(Duda(1973), Koller(2009))：,(1)直接求解：動(dòng)態(tài)規(guī)劃、Clique樹(shù)，蒙特卡洛等。,(2)變分求解：設(shè)定目標(biāo)函數(shù)(損失)，化為正則化問(wèn)題。,學(xué)習(xí),假設(shè)：給定結(jié)構(gòu)且樣本完整(所有變量被賦值)。任務(wù)：學(xué)習(xí)參數(shù)，參數(shù)估計(jì)。CP

13、D方法：(1)最大似然估計(jì), (2)Bayes預(yù)測(cè),假設(shè)：結(jié)構(gòu)未知，但是，樣本完整。任務(wù)：學(xué)習(xí)結(jié)構(gòu)和參數(shù)?？紤]一個(gè)可能結(jié)構(gòu)的假設(shè)空間，結(jié)構(gòu)選擇變?yōu)閮?yōu)化問(wèn)題。,假設(shè)：樣本不完整，或某些變量未知。任務(wù)：發(fā)現(xiàn)非顯現(xiàn)表現(xiàn)的變量，知識(shí)發(fā)現(xiàn)。,學(xué)習(xí)結(jié)構(gòu)的兩種策略,D,A,C,B,E,假設(shè)空間：對(duì)結(jié)構(gòu)，就是變量連接的全組合。,學(xué)習(xí)結(jié)構(gòu)：根據(jù)某種準(zhǔn)則，求出I-map,準(zhǔn)則：對(duì)某個(gè)結(jié)構(gòu)的評(píng)價(jià)---評(píng)分。,I(G)={A ? B},I(G)={A

14、? C},I(G)={A ? E},I(G)={A ? E，B ? E， C ? D， A ? C},目標(biāo):從假設(shè)空間中選擇似然最大的模型(結(jié)構(gòu)和參數(shù)),更為重要的是：通過(guò)知識(shí)庫(kù)建立結(jié)構(gòu)(或減小假設(shè)空間)。,歷史進(jìn)程---20年河?xùn)|，20年河西？,1986-今天平均(數(shù)值計(jì)算)統(tǒng)計(jì)機(jī)器學(xué)習(xí),1943-1969平均(數(shù)值計(jì)算)感知機(jī),2000-今后平均+結(jié)構(gòu)?概率圖模型？,1956-1986結(jié)構(gòu)(符號(hào)計(jì)算)人工智能,,M.

15、 Minsky等 Perceptrons: An introduction to computational geometry. 1969,D. Rumelhart等, Parallel Distributed Processing, 1986 V. Vapnik, The nature of statistical learning theory, 1995T.Hastie等, The Elements of Statistic

16、al Learning, 2003,D. Koller等Probabilistic Graphical Models: Principles and Techniques, 2009,,,總結(jié)：我們的糾結(jié),統(tǒng)計(jì)機(jī)器學(xué)習(xí)以“泛化”為核心。,泛化：大量不確定觀察的平均是確定的，排中。iid,難以割舍:,(1)大量實(shí)際問(wèn)題需要建立的模型是可泛化的；,(2)泛化使得建立的模型是實(shí)際問(wèn)題有依據(jù)的近似；,(3)不知什么新的標(biāo)準(zhǔn)可以代替泛化。,Ko

17、ller這本書(shū)并沒(méi)有以泛化為核心，她的宗旨與AI相似。,前途：“預(yù)測(cè)”與“描述”,預(yù)測(cè)與描述是數(shù)據(jù)挖掘提出的兩個(gè)任務(wù)，但是，數(shù)據(jù)挖掘的描述任務(wù)一直開(kāi)展不好(啤酒和尿布)。被嘲笑！,圖模型既可以消除噪音且表示緊湊(相對(duì)AI的窮舉)，還可以對(duì)模型的各個(gè)部分可解釋。前者是預(yù)測(cè)(泛化)，后者是描述(發(fā)現(xiàn))。,金融和生物等領(lǐng)域，計(jì)算機(jī)科學(xué)有兩個(gè)策略：其一，代替領(lǐng)域?qū)＜?從數(shù)據(jù)建立可靠(泛化)的模型)，其二，為領(lǐng)域提供工具，簡(jiǎn)化專(zhuān)家的工作(知識(shí)發(fā)現(xiàn)