機器學(xué)習(xí)及進化計算

機器學(xué)習(xí)及進化計算第一頁，共三十二頁，2022年，8月28日主要教材及參考書目教材：《機器學(xué)習(xí)》,TomM.Mitchell著，曾華軍，張銀奎等譯，機械工業(yè)出版社。參考書目：貝葉斯方法，TomasLeonaard,機械工業(yè)出版社。進化計算，王正志，薄濤，國防科技大學(xué)出版社。神經(jīng)網(wǎng)絡(luò)設(shè)計，MartinT.Hangan等，機械工業(yè)出版社。第二頁，共三十二頁，2022年，8月28日考核方式平時考核：課堂討論選題：決策樹、人工神經(jīng)網(wǎng)絡(luò)、評估假設(shè)、貝葉斯學(xué)習(xí)、計算學(xué)習(xí)理論(PAC相關(guān)內(nèi)容等)、基于實例的學(xué)習(xí)(k-近鄰，局部加權(quán)回歸、RBF等)、遺傳算法、學(xué)習(xí)規(guī)則集合(序列覆蓋算法、學(xué)習(xí)一階規(guī)則等)、學(xué)習(xí)分析、歸納和分析學(xué)習(xí)的結(jié)合、增強學(xué)習(xí)(Q學(xué)習(xí)、時間差分學(xué)習(xí)等)

期末考核第三頁，共三十二頁，2022年，8月28日第一講機器學(xué)習(xí)的基本概念

第1章引言什么是機器學(xué)習(xí)？為什么進行機器學(xué)習(xí)？如何利用機器學(xué)習(xí)解決問題？第四頁，共三十二頁，2022年，8月28日什么是機器學(xué)習(xí)？直觀地理解：機器（計算機）的自我學(xué)習(xí)。例：計算機能從醫(yī)療記錄中學(xué)習(xí)，獲取治療新疾病的最有效方法；住宅管理系統(tǒng)分析住戶的用電模式，以降低能源消耗。第五頁，共三十二頁，2022年，8月28日為什么進行機器學(xué)習(xí)？包括人工智能、概率統(tǒng)計、信息論、神經(jīng)生物學(xué)等學(xué)科的發(fā)展為機器學(xué)習(xí)提供了豐富的素材；不斷增長的在線（實時）數(shù)據(jù)量；可以有效地利用計算機的計算性能；產(chǎn)業(yè)發(fā)展的推動；機器學(xué)習(xí)適用的三大領(lǐng)域:第六頁，共三十二頁，2022年，8月28日機器學(xué)習(xí)適用的三大領(lǐng)域數(shù)據(jù)挖掘：用歷史數(shù)據(jù)提高決策能力。 例：醫(yī)療數(shù)據(jù)診斷知識(dataknowledge)人們無法手工操作實現(xiàn)，而應(yīng)用軟件卻可以。 例:自動駕駛；語音識別個性定制程序。 例：掌握用戶興趣的新聞廣播員第七頁，共三十二頁，2022年，8月28日典型的數(shù)據(jù)挖掘?qū)嵗龜?shù)據(jù)：給定9714個病歷記錄，每條記錄描述了懷孕及生產(chǎn)的信息每條病歷記錄包含215個特征第八頁，共三十二頁，2022年，8月28日數(shù)據(jù)特征Patient103time=1Age:23FirstPregnancy:noAnemia:noPreviousPrematureBirth:noDiabetes:noUltrasound:?ElectiveC?Section:?EmergencyC?Section:?...Patient103time=2Age:23FirstPregnancy:noAnemia:noPreviousPrematureBirth:noDiabetes:YESUltrasound:abnormalEmergencyC?Section:?ElectiveC?Section:no......Patient103

time=nAge:23FirstPregnancy:noAnemia:noPreviousPrematureBirth:noDiabetes:noElectiveC?Section:noUltrasound:?EmergencyC?Section:Yes...要求預(yù)測：未來病歷中需要緊急剖腹產(chǎn)的病人第九頁，共三十二頁，2022年，8月28日如何利用機器學(xué)習(xí)解決問題學(xué)習(xí)問題的標(biāo)準(zhǔn)描述（Section1.1）設(shè)計學(xué)習(xí)系統(tǒng)（Section1.2)第十頁，共三十二頁，2022年，8月28日什么是學(xué)習(xí)問題？定義：對于某類任務(wù)T和性能度量P，如果一個計算機程序在T上以P衡量的性能隨著經(jīng)驗E而自我完善，那么我們稱這個計算機程序在從經(jīng)驗E學(xué)習(xí)。（例：水果分類,手寫字體的識別，機器人駕駛）廣義理解：任何計算機程序通過經(jīng)驗來提高某任務(wù)處理性能的行為。第十一頁，共三十二頁，2022年，8月28日如何設(shè)計學(xué)習(xí)系統(tǒng)？(1)選擇訓(xùn)練經(jīng)驗a)訓(xùn)練經(jīng)驗?zāi)芊駷橄到y(tǒng)的決策提供直接或間接的反饋？(特征抽取、選擇？)b)學(xué)習(xí)器可以在多大程度上控制訓(xùn)練樣例序列?(能否在線學(xué)習(xí)？)c)訓(xùn)練樣例的分布能多好地表示實例分布?第十二頁，共三十二頁，2022年，8月28日例：手寫字體的識別學(xué)習(xí)問題要學(xué)習(xí)的知識的確切類型對于這個目標(biāo)知識的表示一種學(xué)習(xí)機制第十三頁，共三十二頁，2022年，8月28日如何設(shè)計學(xué)習(xí)系統(tǒng)？(2)選擇目標(biāo)函數(shù)

學(xué)習(xí)任務(wù)目標(biāo)函數(shù)目標(biāo)函數(shù)的逼近

V:Featurestatictargetoutput選擇目標(biāo)函數(shù)的表示

與學(xué)習(xí)機制有關(guān)：加權(quán)方式，推理方式等第十四頁，共三十二頁，2022年，8月28日如何設(shè)計學(xué)習(xí)系統(tǒng)？(3)選擇函數(shù)逼近算法(學(xué)習(xí)機制)估計訓(xùn)練值調(diào)整權(quán)值(或調(diào)整規(guī)則等)第十五頁，共三十二頁，2022年，8月28日學(xué)習(xí)過程的設(shè)計流程決定訓(xùn)練經(jīng)驗類型決定目標(biāo)函數(shù)的表示完成設(shè)計決定目標(biāo)函數(shù)選擇學(xué)習(xí)方法第十六頁，共三十二頁，2022年，8月28日第2章概念學(xué)習(xí)和一般到特殊序機器學(xué)習(xí)的中心問題：

從特殊的訓(xùn)練樣例中歸納出一般函數(shù)（一般概念）。在兩分類問題中，概念學(xué)習(xí)的定義為：

從有關(guān)某個布爾函數(shù)的輸入輸出訓(xùn)練樣例中，推斷出該布爾函數(shù)。第十七頁，共三十二頁，2022年，8月28日2.2.1術(shù)語定義實例(instance)

屬性(attribute)

目標(biāo)概念(targetconcept):c(x)

訓(xùn)練樣例(trainingexamples)

正例(positiveexample)、反例(negativeexample):c(x)=1or0

所有可能假設(shè)(allpossiblehypotheses):H(c的所有可能假設(shè),從中搜索h(x)=c(x))第十八頁，共三十二頁，2022年，8月28日表2-1目標(biāo)概念EnjoySport的正例和反例ExampleSkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes術(shù)語定義Find-S例第十九頁，共三十二頁，2022年，8月28日2.2.2歸納學(xué)習(xí)假設(shè)

歸納學(xué)習(xí)假設(shè):

任一假設(shè)如果在足夠大的訓(xùn)練樣例集中很好地逼近目標(biāo)函數(shù)，它也能在未見實例中很好地逼近目標(biāo)函數(shù)。第二十頁，共三十二頁，2022年，8月28日2.3作為搜索的概念學(xué)習(xí)概念學(xué)習(xí)的過程即搜索的過程搜索范圍：假設(shè)表示(H)所隱含定義的整個空間。搜索目標(biāo):尋找能最好地擬合訓(xùn)練樣例的假設(shè)h。學(xué)習(xí)算法不同，假設(shè)空間搜索的策略也不同。

第二十一頁，共三十二頁，2022年，8月28日Moregeneralthanorequalto定義：令hj和hk為在X上定義的布爾函數(shù)。定義一個more-general-than-or-equal-to關(guān)系，記做≥g。稱hj≥g

hk當(dāng)且僅當(dāng)(x∈X)[(hk(x)=1)→(hj(x)=1)]例：h1=<Sunny,?,?,Strong,?,?>h2=<Sunny,?,?,?,?,?>第二十二頁，共三十二頁，2022年，8月28日2.4FIND-S:尋找極大特殊假設(shè)表2-3Find-S算法將h初始化為H中最特殊假設(shè);對每個正例x;對h的每個屬性約束ai

如果x滿足ai,那么不做任何事否則將h中ai替換為x滿足的緊鄰的更一般約束輸出假設(shè)h.第二十三頁，共三十二頁，2022年，8月28日例：學(xué)習(xí)器的一系列訓(xùn)練樣例如表2-1所示，則FIND-S的學(xué)習(xí)過程為：Step1.將h初始化為H中最特殊假設(shè)：h←<,,,,,>Step2.與表2-1中第一個訓(xùn)練樣例對比，每個屬性都被替換成能擬合該例的值約束。

h←<Sunny,Warm,Normal,Strong,Warm,Same>第二十四頁，共三十二頁，2022年，8月28日Step3.第2個訓(xùn)練樣例（仍為正例）使該算法進一步將h泛化:h←<Sunny,Warm,?,Strong,Warm,Same>Step4.第3個訓(xùn)練樣例是一個反例，h不變……依次對比樣例，直到最后h泛化為：h←<Sunny,Warm,?,Strong,?,?>第二十五頁，共三十二頁，2022年，8月28日FIND-S的困惑學(xué)習(xí)過程是否收斂到了正確的目標(biāo)概念？--無法確定收斂到了目標(biāo)概念為什么要用極大特殊假設(shè)？--若有多個與訓(xùn)練樣例一致的假設(shè)，F(xiàn)ind-S只能找到極大特殊假設(shè)。訓(xùn)練樣例是否相互一致？--數(shù)據(jù)含噪若有多個極大特殊假設(shè)呢？--選擇第二十六頁，共三十二頁，2022年，8月28日2.5變型空間和候選消除算法一些術(shù)語及其表示(1)：一致：一個假設(shè)h與訓(xùn)練樣例集合D一致(consistent)，當(dāng)且僅當(dāng)對D中每一個樣例<x,c(x)>，h(x)=c(x)。

Consistent(h,D)≡(<x,c(x)>∈D)h(x)=c(x)第二十七頁，共三十二頁，2022年，8月28日一些術(shù)語及其表示(2)：變型空間:關(guān)于假設(shè)空間H和訓(xùn)練樣例集D的變型空間(versionspace)，標(biāo)記為VSH,D，是H中與訓(xùn)練樣例D一致的所有假設(shè)構(gòu)成的子集。

VSH,D≡{h∈H|Consistent(h,D)}第二十八頁，共三十二頁，2022年，8月28日2.5.2列表后消除算法List-Then-Eliminate:列出變型空間的其所有成員.特點:繁瑣。表2-4列表后消除算法變型空間VersionSpace←包含H中所有假設(shè)的列表對每個訓(xùn)練樣例<x,c(x)>

從變型空間中移除所有h(x)≠c(x)的假設(shè)h輸出VersionSpace中的假設(shè)列表第二十九頁，共三十二頁，2022年，8月28日2.5.4候選消除學(xué)習(xí)法候選消除：候選消除算法通過使用極大一般成員（G）和極大特殊成員（S）來表示變型空間。第三十頁，共三十二頁，2022年，8月28日表2-5使用變型空間的候選消除算法（正例和反例同時影響S和G）將G集合初始化為H中極大一般假設(shè)將S集合初始化為H中極大特殊假設(shè)對每個訓(xùn)練樣例d，進行以下操作：如果d是一正例從G中移去所有與d不一致的假設(shè)對S中每個與d不一致的假設(shè)s從S中移去s把s的所有的極小泛化式h加入到S中，其中h滿足h與d一致，而且G的某個成員比h更一般從S中移去所有這樣的假設(shè)：它比S中另一假設(shè)更一般如果d是一個反例從S中移去所有與d不一致的假設(shè)對G