機器學(xué)習(xí)研究進展-西安電子科技大學(xué)電子工程學(xué)院

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

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

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

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

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

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

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

8、以感知機為基礎(chǔ)，研究統(tǒng)計機器學(xué)習(xí)問題。,15,困難—特征空間基的選擇,選擇特征空間的基特征空間的基可以采用多項式基或三角函數(shù)基尋找一般的方法描述特征空間存在根本性困難(維數(shù)災(zāi))與神經(jīng)網(wǎng)絡(luò)相比，核函數(shù)的選擇可以借助領(lǐng)域知識，這是一個優(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、算法設(shè)計奠定基礎(chǔ)。,20,研究趨勢,算法的理論研究基本已經(jīng)完成，根據(jù)特定需求的研究可能是必要的目前主要集中在下述兩個問題上：泛化不等式需要樣本集滿足獨立同分布，這個條件太嚴厲，可以放寬這個條件？如何根據(jù)領(lǐng)域需求選擇核函數(shù)，有基本原則嗎？,,21,集成機器學(xué)習(xí)的來源,神經(jīng)科學(xué)：Hebb神經(jīng)細胞工作方式數(shù)學(xué)方法：非線性問題的分段化(類似)計算技術(shù)：Widrow的Madaline模型統(tǒng)計理論：PAC的弱可學(xué)習(xí)理論,22,Ensem

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

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

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

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

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

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,符號機器學(xué)習(xí)的最新進展,Rough sets中的reduct理論是近幾年符號機器學(xué)習(xí)最重要的研究結(jié)果之一這個理論理論可以作為符號機器學(xué)習(xí)的數(shù)學(xué)基礎(chǔ)這個理論可以作為符號數(shù)據(jù)分

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

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

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

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

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

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