機器學習研究進展-西安電子科技大學電子工程學院

1、1,機器學習研究進展,第九屆中國機器學習會議 上海2004年10月,王 玨中國科學院自動化研究所jue.wang@mail.ia.ac.cn,周志華南京大學計算機科學與技術系zhouzh@nju.edu.cn,連接機器學習符號機器學習遺傳機器學習分析機器學習,機器學習研究的變遷,Carbonell(1989)展望,Dietterich(1997)展望,,,,,,？,,統(tǒng)計機器學習集成機器學習符號機器學習增強機

2、器學習,,,,流形機器學習半監(jiān)督機器學習多實例機器學習Ranking機器學習數(shù)據(jù)流機器學習,應用驅(qū)動的機器學習研究,,,目前，以“主義”爭霸的時代已經(jīng)過去，不同方法解決不同問題。,,,3,對統(tǒng)計機器學習的說明,Dietterich將感知機類的連接機器學習分離出來，并根據(jù)劃分機理，將其分為兩種類型：統(tǒng)計機器學習與集成機器學習。這意味著，感知機類機器學習是重點強調(diào)：表示：非線性問題的線性表示泛化：以泛化能力為基礎的算法設計,,

3、4,對增強機器學習的說明,“適應性”是控制理論中最重要的概念之一，以往在計算機科學中考慮較少1975年，Holland首先將這個概念引入計算機科學。1990年左右，MIT的Sutton等青年計算機科學家，結(jié)合動態(tài)規(guī)劃等問題，統(tǒng)稱其為增強機器學習這樣，遺傳學習成為實現(xiàn)增強機器學習的一種方法,,5,對符號機器學習的說明,盡管經(jīng)過十年，符號機器學習被保留，然而，其目標和內(nèi)涵已發(fā)生很大的變化改變泛化目標為符號描述(數(shù)據(jù)挖掘)。這意味著，符

4、號機器學習已不是與統(tǒng)計機器學習競爭的研究，而是一個研究目標與其不同的研究范式,,6,分析機器學習被放棄,分析機器學習所包含的類比、解釋等問題對背景知識有更高的要求，這從表示到學習均需要考慮新的理論基礎，在這些理論未出現(xiàn)之前，其淡出機器學習研究的視野是自然的,,7,近幾年的發(fā)展動向,由于真實世界的問題十分困難，現(xiàn)有的理論、方法，甚至理念已不能滿足需要，由此，大量近代數(shù)學的研究結(jié)果被引入計算機科學，由此，形成新的機器學習范式,8,特點,從C

5、arbonell到Dietterich的特點是：在算法設計理論上，基礎代替隨意的算法設計，具體地說，更為強調(diào)機器學習的數(shù)學基礎應用驅(qū)動代替理論驅(qū)動(認知科學與算法的Open問題)。具體地說，從AI中以“學習”機制驅(qū)動(智能)”的研究方式，改變?yōu)楦鶕?jù)面臨的實際問題發(fā)展新的理論與方法,,9,統(tǒng)計機器學習的要點,目前，統(tǒng)計機器學習的研究主要集中在兩個要點上：,表示問題,泛化問題,非線性問題在線形空間的表示,對給定樣本集合， 通過算法建

6、立模型，對問題世界為真的程度,,,10,線性表示,計算：非線性算法一般是NP完全的。認識世界：只有在某個空間中可以描述為線性的世界，人們才說，這個世界已被認識(將問題變換為另一個問題)數(shù)學方法：尋找一個映射，將非線性問題映射到線性空間，以便其可以線性表述,11,例子---XOR問題,xy0001,例子：XOR問題：,映射：(x,y)?(x,xy,y),線形表示：,12,在機器學習中的方法,尋找具有一般意義的線性空間(方法

7、)目前，機器學習主要采用兩種方法：整體線性，Hilbert空間(核映射)類似分段線性，Madaline或弱分類方法,13,Hilbert空間,Hilbert空間是Von Neumman為量子力學數(shù)學基礎提出的一類具有一般意義的線性內(nèi)積空間在機器學習中借助Hilbert空間構成特征空間,14,線性不可分機器學習問題,將線性不可分問題變?yōu)榫€性可分問題的關鍵是尋找一個映射，將樣本集映射到特征空間，使其在特征空間線性可分這樣，我們只需

8、以感知機為基礎，研究統(tǒng)計機器學習問題。,15,困難—特征空間基的選擇,選擇特征空間的基特征空間的基可以采用多項式基或三角函數(shù)基尋找一般的方法描述特征空間存在根本性困難(維數(shù)災)與神經(jīng)網(wǎng)絡相比，核函數(shù)的選擇可以借助領域知識，這是一個優(yōu)點,16,理論描述,是否可以不顯現(xiàn)地描述特征空間，將特征空間上描述變?yōu)闃颖究臻g上的描述？如果不考慮維數(shù)問題，在泛函分析理論上，這是可行的這就是核函數(shù)方法,,泛化能力描述,Duda(1973),Vap

9、nik(1971),18,“泛化誤差界”研究的演變,PAC界(Valiant[1984])VC維界(Blumer[1989])最大邊緣(Shawe-Taylor[1998]),19,最大邊緣(Shawe-Taylor[1998]),M>0，邊緣不能等于零。這意味著，樣本集合必須是可劃分的。邊緣最大，誤差界最小，泛化能力最強。泛化能力可以使用樣本集合的邊緣刻畫。,這個不等式依賴于邊緣M。貢獻：給出了有幾何直觀的界描述，從而為

10、算法設計奠定基礎。,20,研究趨勢,算法的理論研究基本已經(jīng)完成，根據(jù)特定需求的研究可能是必要的目前主要集中在下述兩個問題上：泛化不等式需要樣本集滿足獨立同分布，這個條件太嚴厲，可以放寬這個條件？如何根據(jù)領域需求選擇核函數(shù)，有基本原則嗎？,,21,集成機器學習的來源,神經(jīng)科學：Hebb神經(jīng)細胞工作方式數(shù)學方法：非線性問題的分段化(類似)計算技術：Widrow的Madaline模型統(tǒng)計理論：PAC的弱可學習理論,22,Ensem

11、ble(集成),1954年，Hebb使用這個單詞來說明視覺神經(jīng)細胞的信息加工方式假設信息加工是由神經(jīng)集合體來完成,23,Madaline模型,Widrow的Madaline模型在數(shù)學上，其本質(zhì)是放棄感知機對樣本空間劃分的超平面需要滿足連續(xù)且光滑的條件，代之分段的超平面,24,Schapire的理論,定理：如果一個概念是弱可學習的，充要條件是它是強可學習的,這個定理證明是構造性的，派生了弱分類器的概念，即，比隨機猜想稍好的分類器,這個

12、定理說明： 多個弱分類器可以集成為一個強分類器,1990年，Schapire證明了一個關鍵定理，由此，奠定了集成機器學習的理論基礎,25,問題,集成機器學習的研究還存在著大量未解決的問題，關于泛化能力的估計(不等式)還存在問題目前，這類機器學習的理論研究主要是觀察與積累，大量的現(xiàn)象還不能解釋,,符號機器學習,最早的符號機器學習：Solomonoff的文法歸納方法(1959),,符號機器學習的主流：Samuel限制機器學習在結(jié)

13、構化符號數(shù)據(jù)集合上(1967)，約簡算法。,Gold證明，這是不可能的實現(xiàn)的(1967)。,值得注意的動向：文法歸納方法引起人們的重視。,,Hebb路線：每個規(guī)則可以理解為一個弱分類器。,27,符號機器學習的數(shù)學基礎,符號機器學習不同于統(tǒng)計機器學習，劃分樣本集合的等價關系是學習所得，符號機器學習是事先定義等價關系，學習只是在這個等價關系下約簡樣本集合等價關系為：{(x, y) : a(x)=a(y), x, y?U},28,符號機

14、器學習的泛化問題,一個無矛盾規(guī)則越短，其覆蓋對象越多，因此，符號機器學習的泛化是以信息長度描述的。這樣，“最小”樹或規(guī)則集合就是其目標函數(shù)兩個因素影響這個目標：其一，從實域到符號域的映射，其二，在符號域上的約簡。對“最小”兩者都是NP完全的。因此，近似算法是必然的但是，只有在符號域上的約簡是符號機器學習特有，因此，其泛化能力受到限制不必與統(tǒng)計機器學習競爭，設立新目標,29,數(shù)據(jù)分析與傳統(tǒng)機器學習區(qū)別,傳統(tǒng)機器學習假設所有用戶有相同

15、的需求，其目標函數(shù)確定，而數(shù)據(jù)分析，不同用戶有不同需求，目標函數(shù)隨用戶需求而定傳統(tǒng)機器學習是“黑箱”，模型無須可解釋，但是，數(shù)據(jù)分析必須考慮對用戶的可讀性傳統(tǒng)機器學習將“例外”考慮為噪音，而數(shù)據(jù)分析則認為“例外”可能是更有意義的知識,30,符號機器學習的特點,由于這類機器學習主要處理符號，因此，如果獲得一個長度較短的數(shù)據(jù)集合的描述，可以將其翻譯為人可以閱讀的文本。人通過閱讀這個文本就可以了解數(shù)據(jù)集合的內(nèi)容這個目標與泛化能力無關，計

16、算結(jié)果只是給定數(shù)據(jù)集合根據(jù)特定需求的一個可以被人閱讀的縮影這與傳統(tǒng)數(shù)據(jù)分析的目標一致,31,符號數(shù)據(jù)分析(數(shù)據(jù)挖掘),數(shù)據(jù)分析的主要工具是統(tǒng)計，“統(tǒng)計顯現(xiàn)”是分析的主要指標符號數(shù)據(jù)分析，盡管統(tǒng)計工具是必要的，但是，主要是通過將符號數(shù)據(jù)集合約簡為簡潔形式,32,符號機器學習的最新進展,Rough sets中的reduct理論是近幾年符號機器學習最重要的研究結(jié)果之一這個理論理論可以作為符號機器學習的數(shù)學基礎這個理論可以作為符號數(shù)據(jù)分

17、析的基礎(數(shù)據(jù)挖掘),33,Reduct與符號數(shù)據(jù)分析,在任務上，association rules派生于統(tǒng)計相關分析，其方法可以使用reduct理論來刻畫Reduct具有很多重要的數(shù)學性質(zhì)，可以保證根據(jù)不同需求識別不同的例外我們建議，將符號數(shù)據(jù)分析建立在reduct理論之上,34,什么是outlier/exception,不能被模型(統(tǒng)計分布、規(guī)則集合等)概括的某些觀察稱為相對這個模型的outlier/ exception注釋

18、： 在統(tǒng)計學中，這類觀察稱為outlier，在認知科學中，有意義的outlier稱為exception,35,方法,R是給定的reduct，使用R構造新信息系統(tǒng)，R是這個信息系統(tǒng)的Core只要刪除一個核屬性，必然產(chǎn)生例外，同時縮短規(guī)則集,36,例外研究的意義,刪除例外，可以使得規(guī)則更為簡潔，從而突出信息的重點。例外是噪音例外是比可以覆蓋大多數(shù)樣本的規(guī)則更為有趣的知識對專家，規(guī)則是“老生常談”，而例外則是應該引起注意的事件或

19、知識例外是新研究與發(fā)現(xiàn)的開始,,37,增強機器學習,增強機器學習最早提出是考慮“從變化環(huán)境中”學習蘊含在環(huán)境中知識，其本質(zhì)是對環(huán)境的適應開始的動機主要是為了解決機器人規(guī)劃、避障與在環(huán)境中適應的學習問題目前，由于網(wǎng)絡用戶是更為復雜的環(huán)境，例如，如何使搜索引擎適應用戶的需求，成為更為重要的應用領域,,38,流形機器學習,很多問題的表示方法，使得信息十分稀疏，如何將信息稠密化是一個困難的問題（“維數(shù)災難”），主成分分析是一種方法，但是，

20、只對線性情況有效流形學習是解決上述問題的非線性方法由于流形的本質(zhì)是分段線性化，因此，流形學習需要解決計算開集、設計同胚映射等問題,39,半監(jiān)督機器學習,在觀測數(shù)據(jù)中，可能有很多觀測不能決定其類別標號。這需要根據(jù)數(shù)據(jù)中已知類別標號的樣本與領域知識來推測這些樣本的類別標號，并建立問題世界的模型，這就是半監(jiān)督學習這類問題直接來自于實際應用：例如，大量醫(yī)學影像，醫(yī)生把每張片子上的每個病灶都標出來再進行學習，是不可能的，能否只標一部分，并且

21、還能利用未標的部分？,40,多示例機器學習,傳統(tǒng)的機器學習中，一個對象有一個描述，而在一些實際問題中，一個對象可能同時有多個描述，到底哪個描述是決定對象性質(zhì)(例如類別)的，卻并不知道。解決這種“對象：描述：類別”之間1:N:1關系的學習就是多示例學習,41,Ranking機器學習,其原始說法是learning for ranking問題主要來自信息檢索，假設用戶的需求不能簡單地表示為“喜歡”或“不喜歡”，而需要將“喜歡”表示為一個順序

22、，問題是如何通過學習，獲得關于這個“喜歡”順序的模型。,42,數(shù)據(jù)流機器學習,在網(wǎng)絡數(shù)據(jù)分析與處理中，有一類問題，從一個用戶節(jié)點上流過的數(shù)據(jù)，大多數(shù)是無意義的，由于數(shù)據(jù)量極大，不能全部存儲，因此，只能簡單判斷流過的文件是否有用，而無法細致分析如何學習一個模型可以完成這個任務，同時可以增量學習，以保證可以從數(shù)據(jù)流中不斷改善(或適應)用戶需求的模型,43,研究現(xiàn)狀,上述的五類機器學習范式還處于實驗觀察階段，沒有堅實的理論基礎！這些范式主