機(jī)器學(xué)習(xí)及進(jìn)化計(jì)算

1、機(jī)器學(xué)習(xí)及進(jìn)化計(jì)算授課：徐琴珍學(xué)時(shí)：36主要教材及參考書目教材：機(jī)器學(xué)習(xí), Tom M. Mitchell著，曾華軍，張銀奎 等譯，機(jī)械工業(yè)出版社。參考書目：貝葉斯方法，Tomas Leonaard, 機(jī)械工業(yè)出版社。進(jìn)化計(jì)算， 王正志，薄濤，國(guó)防科技大學(xué)出版社。神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)，Martin T. Hangan等，機(jī)械工業(yè)出版社?？己朔绞?平時(shí)考核：課堂討論 選題：決策樹、人工神經(jīng)網(wǎng)絡(luò)、評(píng)估假設(shè)、貝葉斯學(xué)習(xí)、計(jì)算學(xué)習(xí)理論(PAC相關(guān)內(nèi)容等)、基于實(shí)例的學(xué)習(xí)(k-近鄰，局部加權(quán)回歸、RBF等)、遺傳算法、學(xué)習(xí)規(guī)則集合(序列覆蓋算法、學(xué)習(xí)一階規(guī)則等)、學(xué)習(xí)分析、歸納和分析學(xué)習(xí)的結(jié)合、增強(qiáng)學(xué)習(xí)(Q 學(xué)

2、習(xí)、時(shí)間差分學(xué)習(xí)等) 期末考核第一講 機(jī)器學(xué)習(xí)的基本概念第1章 引言 什么是機(jī)器學(xué)習(xí)？ 為什么進(jìn)行機(jī)器學(xué)習(xí)？ 如何利用機(jī)器學(xué)習(xí)解決問(wèn)題？什么是機(jī)器學(xué)習(xí)？直觀地理解： 機(jī)器（計(jì)算機(jī)）的自我學(xué)習(xí)。例： 計(jì)算機(jī)能從醫(yī)療記錄中學(xué)習(xí)，獲取治療新疾病的最有效方法； 住宅管理系統(tǒng)分析住戶的用電模式，以降低能源消耗。 為什么進(jìn)行機(jī)器學(xué)習(xí)？ 包括人工智能、概率統(tǒng)計(jì)、信息論、神經(jīng)生物學(xué)等學(xué)科的發(fā)展為機(jī)器學(xué)習(xí)提供了豐富的素材； 不斷增長(zhǎng)的在線（實(shí)時(shí)）數(shù)據(jù)量； 可以有效地利用計(jì)算機(jī)的計(jì)算性能； 產(chǎn)業(yè)發(fā)展的推動(dòng)； 機(jī)器學(xué)習(xí)適用的三大領(lǐng)域:機(jī)器學(xué)習(xí)適用的三大領(lǐng)域數(shù)據(jù)挖掘：用歷史數(shù)據(jù)提高決策能力。例：醫(yī)療數(shù)據(jù)診斷知識(shí)(da

3、ta knowledge)人們無(wú)法手工操作實(shí)現(xiàn)，而應(yīng)用軟件卻可以。例: 自動(dòng)駕駛；語(yǔ)音識(shí)別個(gè)性定制程序。例：掌握用戶興趣的新聞廣播員典型的數(shù)據(jù)挖掘?qū)嵗龜?shù)據(jù)：給定9714個(gè)病歷記錄，每條記錄描述了懷孕及生產(chǎn)的信息每條病歷記錄包含215個(gè)特征數(shù)據(jù)特征Patient103 time=1Age: 23FirstPregnancy: noAnemia: noPreviousPrematureBirth: no Diabetes: noUltrasound: ?Elective CSection: ?Emergency CSection: ?.Patient103 time=2Age: 23FirstPr

4、egnancy: noAnemia: noPreviousPrematureBirth: noDiabetes: YES Ultrasound: abnormalEmergency CSection: ?Elective CSection: no.Patient103 time=nAge: 23FirstPregnancy: noAnemia: noPreviousPrematureBirth: noDiabetes: noElective CSection: noUltrasound: ?Emergency CSection: Yes.要求預(yù)測(cè)：未來(lái)病歷中需要緊急剖腹產(chǎn)的病人如何利用機(jī)器學(xué)習(xí)

5、解決問(wèn)題學(xué)習(xí)問(wèn)題的標(biāo)準(zhǔn)描述（Section 1.1） 設(shè)計(jì)學(xué)習(xí)系統(tǒng)（Section 1.2)什么是學(xué)習(xí)問(wèn)題？定義：對(duì)于某類任務(wù)T 和性能度量P ，如果一個(gè)計(jì)算機(jī)程序在T 上以P 衡量的性能隨著經(jīng)驗(yàn)E 而自我完善，那么我們稱這個(gè)計(jì)算機(jī)程序在從經(jīng)驗(yàn)E 學(xué)習(xí)。（例：水果分類, 手寫字體的識(shí)別，機(jī)器人駕駛）廣義理解：任何計(jì)算機(jī)程序通過(guò)經(jīng)驗(yàn)來(lái)提高某任務(wù)處理性能的行為 。如何設(shè)計(jì)學(xué)習(xí)系統(tǒng)？(1)選擇訓(xùn)練經(jīng)驗(yàn)a) 訓(xùn)練經(jīng)驗(yàn)?zāi)芊駷橄到y(tǒng)的決策提供直接或間接的反饋 ？(特征抽取、選擇？)b) 學(xué)習(xí)器可以在多大程度上控制訓(xùn)練樣例序列 ?(能否在線學(xué)習(xí)？)c) 訓(xùn)練樣例的分布能多好地表示實(shí)例分布? 例：手寫字體的識(shí)別

6、學(xué)習(xí)問(wèn)題要學(xué)習(xí)的知識(shí)的確切類型對(duì)于這個(gè)目標(biāo)知識(shí)的表示一種學(xué)習(xí)機(jī)制如何設(shè)計(jì)學(xué)習(xí)系統(tǒng)？(2)選擇目標(biāo)函數(shù)學(xué)習(xí)任務(wù)目標(biāo)函數(shù)目標(biāo)函數(shù)的逼近V: Feature statictarget output 選擇目標(biāo)函數(shù)的表示與學(xué)習(xí)機(jī)制有關(guān)：加權(quán)方式，推理方式等如何設(shè)計(jì)學(xué)習(xí)系統(tǒng)？(3)選擇函數(shù)逼近算法(學(xué)習(xí)機(jī)制)估計(jì)訓(xùn)練值調(diào)整權(quán)值(或調(diào)整規(guī)則等)學(xué)習(xí)過(guò)程的設(shè)計(jì)流程決定訓(xùn)練經(jīng)驗(yàn)類型決定目標(biāo)函數(shù)的表示完成設(shè)計(jì)決定目標(biāo)函數(shù)選擇學(xué)習(xí)方法第2章 概念學(xué)習(xí)和一般到特殊序機(jī)器學(xué)習(xí)的中心問(wèn)題：從特殊的訓(xùn)練樣例中歸納出一般函數(shù)（一般概念）。在兩分類問(wèn)題中，概念學(xué)習(xí)的定義為： 從有關(guān)某個(gè)布爾函數(shù)的輸入輸出訓(xùn)練樣例中，推斷出該布爾

7、函數(shù) 。2.2.1 術(shù)語(yǔ)定義 實(shí)例(instance) 屬性(attribute) 目標(biāo)概念(target concept) : c(x) 訓(xùn)練樣例(training examples) 正例(positive example) 、反例(negative example): c(x)=1 or 0 所有可能假設(shè)(all possible hypotheses) : H(c的所有可能假設(shè),從中搜索h(x)=c(x)表2-1目標(biāo)概念EnjoySport的正例和反例ExampleSkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormal

8、StrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes術(shù)語(yǔ)定義Find-S例2.2.2 歸納學(xué)習(xí)假設(shè) 歸納學(xué)習(xí)假設(shè): 任一假設(shè)如果在足夠大的訓(xùn)練樣例集中很好地逼近目標(biāo)函數(shù)，它也能在未見(jiàn)實(shí)例中很好地逼近目標(biāo)函數(shù)。2.3作為搜索的概念學(xué)習(xí) 概念學(xué)習(xí)的過(guò)程即搜索的過(guò)程搜索范圍：假設(shè)表示(H)所隱含定義的整個(gè)空間。搜索目標(biāo):尋找能最好地?cái)M合訓(xùn)練樣例的假設(shè)h。學(xué)習(xí)算法不同，假設(shè)空間搜索的策略也不同。 More general than

9、 or equal to定義：令hj 和hk 為在X上定義的布爾函數(shù)。定義一個(gè)more-general-than-or-equal-to關(guān)系，記做g。稱hjg hk當(dāng)且僅當(dāng)(xX) ( hk (x) =1)( hj (x) =1)例：h1= h2=2.4 FIND-S: 尋找極大特殊假設(shè)表2-3 Find-S算法將h初始化為H中最特殊假設(shè);對(duì)每個(gè)正例x;對(duì)h的每個(gè)屬性約束ai 如果 x滿足ai ,那么不做任何事 否則將h中ai替換為x滿足的緊鄰的更一般 約束輸出假設(shè)h.例：學(xué)習(xí)器的一系列訓(xùn)練樣例如表2-1所示， 則FIND-S的學(xué)習(xí)過(guò)程為： Step1.將h初始化為H中最特殊假設(shè)： h Ste

10、p2.與表2-1中第一個(gè)訓(xùn)練樣例對(duì)比，每個(gè)屬性都被替換成能擬合該例的值約束。 h Step3.第2個(gè)訓(xùn)練樣例（仍為正例）使該算法進(jìn)一步將h泛化: hStep4.第3個(gè)訓(xùn)練樣例是一個(gè)反例，h不變依次對(duì)比樣例，直到最后h泛化為： hFIND-S的困惑學(xué)習(xí)過(guò)程是否收斂到了正確的目標(biāo)概念？- 無(wú)法確定收斂到了目標(biāo)概念為什么要用極大特殊假設(shè)？-若有多個(gè)與訓(xùn)練樣例一致的假設(shè)，F(xiàn)ind-S只能找到極大特殊假設(shè)。訓(xùn)練樣例是否相互一致？ -數(shù)據(jù)含噪若有多個(gè)極大特殊假設(shè)呢？-選擇 2.5變型空間和候選消除算法一些術(shù)語(yǔ)及其表示(1)：一致：一個(gè)假設(shè)h與訓(xùn)練樣例集合D一致(consistent)，當(dāng)且僅當(dāng)對(duì)D中每一個(gè)

11、樣例，h(x)=c(x)。 Consistent(h,D)( D) h(x)=c(x)一些術(shù)語(yǔ)及其表示(2)：變型空間: 關(guān)于假設(shè)空間H和訓(xùn)練樣例集D的變型空間(version space)，標(biāo)記為VSH,D，是H中與訓(xùn)練樣例D一致的所有假設(shè)構(gòu)成的子集。 VSH,DhH | Consistent (h,D) 2.5.2列表后消除算法List-Then-Eliminate: 列出變型空間的其所有成員. 特點(diǎn): 繁瑣。表2-4 列表后消除算法變型空間VersionSpace包含H中所有假設(shè)的列表對(duì)每個(gè)訓(xùn)練樣例 從變型空間中移除所有h(x)c(x)的假設(shè)h輸出VersionSpace中的假設(shè)列表2.5.4 候選消除學(xué)習(xí)法候選消除：候選消除算法通過(guò)使用極大一般成員（G）和極大特殊成員（S）來(lái)表示變型空間。 表2-5 使用變型空間的候選消除算法（正例和反例同時(shí)影響S和G）將G集合初始化為H中極大一般假設(shè)將S集合初始化為H中極大特殊假設(shè)對(duì)每個(gè)訓(xùn)練樣例d，進(jìn)行以下操作：如果d是一正例從G中移去所有與d不一致的假設(shè)對(duì)S中每個(gè)與d不一致的假設(shè)s從S中移去s把s的所有的極小泛化式h加入到S中，其中h滿足h與d一致，而且G的某個(gè)成員比h更一般從S中移去所有這樣的假設(shè)：它比S中另一假設(shè)更一般如果d是一個(gè)反例從S中移去所有與d不一致的假設(shè)對(duì)G中