機(jī)器學(xué)習(xí)課件

2003.12.181機(jī)器學(xué)習(xí)第1章引言2003.12.182什麼是機(jī)器學(xué)習(xí)什麼是機(jī)器學(xué)習(xí)電腦程式如何隨著經(jīng)驗(yàn)積累自動(dòng)提高性能系統(tǒng)自我改進(jìn)的過程歷史成功應(yīng)用學(xué)習(xí)識(shí)別人類講話學(xué)習(xí)駕駛車輛學(xué)習(xí)分類新的天文結(jié)構(gòu)學(xué)習(xí)對(duì)弈西洋雙陸棋2003.12.183相關(guān)學(xué)科人工智慧計(jì)算複雜性理論控制論資訊理論統(tǒng)計(jì)學(xué)2003.12.184學(xué)習(xí)問題的標(biāo)準(zhǔn)描述定義如果一個(gè)電腦針對(duì)某類任務(wù)T的用P衡量的性能根據(jù)經(jīng)驗(yàn)E來自我完善，那麼我們稱這個(gè)電腦程式在從經(jīng)驗(yàn)E中學(xué)習(xí)，針對(duì)某類任務(wù)T，它的性能用P來衡量。西洋跳棋學(xué)習(xí)問題的解釋E，和自己下棋T，參與比賽P，比賽成績（或贏棋能力，擊敗對(duì)手的百分比）手寫識(shí)別學(xué)習(xí)問題機(jī)器人駕駛學(xué)習(xí)問題2003.12.185學(xué)習(xí)問題的標(biāo)準(zhǔn)描述（2）定義太寬泛甚至包括了以非常直接的方式通過經(jīng)驗(yàn)自我提高的電腦程式實(shí)際的機(jī)器學(xué)習(xí)問題往往比較複雜定義一類問題探索解決這類問題的方法理解學(xué)習(xí)問題的基本結(jié)構(gòu)和過程2003.12.186設(shè)計(jì)一個(gè)學(xué)習(xí)系統(tǒng)基本設(shè)計(jì)方法和學(xué)習(xí)途徑（以西洋跳棋為例）選擇訓(xùn)練經(jīng)驗(yàn)選擇目標(biāo)函數(shù)選擇目標(biāo)函數(shù)的表示選擇函數(shù)逼近演算法最終設(shè)計(jì)2003.12.187設(shè)計(jì)一個(gè)學(xué)習(xí)系統(tǒng)西洋跳棋學(xué)習(xí)問題任務(wù)T，下西洋跳棋性能標(biāo)準(zhǔn)P，擊敗對(duì)手的百分比訓(xùn)練經(jīng)驗(yàn)E，和自己進(jìn)行訓(xùn)練對(duì)弈學(xué)習(xí)系統(tǒng)需要選擇要學(xué)習(xí)的知識(shí)的確切類型對(duì)於這個(gè)目標(biāo)知識(shí)的表示一種學(xué)習(xí)機(jī)制2003.12.188選擇訓(xùn)練經(jīng)驗(yàn)第一個(gè)關(guān)鍵屬性，訓(xùn)練經(jīng)驗(yàn)?zāi)芊駷橄到y(tǒng)的決策提供直接或間接的回饋第二個(gè)重要屬性，學(xué)習(xí)器在多大程度上控制樣例序列第三個(gè)重要屬性，訓(xùn)練樣例的分佈能多好地表示實(shí)例分佈，通過樣例來衡量最終系統(tǒng)的性能2003.12.189選擇目標(biāo)函數(shù)目標(biāo)函數(shù)ChooseMoveChooseMove:BM，接受合法棋局集合中的棋盤狀態(tài)作為輸入，並從合法走子集合中選擇某個(gè)走子作為輸出問題轉(zhuǎn)化我們把提高任務(wù)T的性能P的問題轉(zhuǎn)化（或簡化）為學(xué)習(xí)像ChooseMove這樣某個(gè)特定的目標(biāo)函數(shù)2003.12.1810選擇目標(biāo)函數(shù)（2）ChooseMove的評(píng)價(jià)學(xué)習(xí)問題很直觀地轉(zhuǎn)化成這個(gè)函數(shù)這個(gè)函數(shù)的學(xué)習(xí)很困難，因?yàn)樘峁┙o系統(tǒng)的是間接訓(xùn)練經(jīng)驗(yàn)另一個(gè)目標(biāo)函數(shù)V一個(gè)評(píng)估函數(shù)，V:BR，它為任何給定棋局賦予一個(gè)數(shù)值評(píng)分，給好的棋局賦予較高的評(píng)分優(yōu)點(diǎn)，學(xué)習(xí)簡單V的應(yīng)用根據(jù)V能夠輕鬆地找到當(dāng)前棋局的最佳走法。2003.12.1811選擇目標(biāo)函數(shù)（3）V的設(shè)計(jì)，對(duì)於集合B中的任意棋局b，V(b)定義如下如果b是一最終的勝局，那麼V(b)=100如果b是一最終的負(fù)局，那麼V(b)=-100如果b是一最終的和局，那麼V(b)=0如果b不是最終棋局，那麼V(b)=V(b’)，其中b’是從b開始雙方都採取最優(yōu)對(duì)弈後可達(dá)到的終局2003.12.1812選擇目標(biāo)函數(shù)（4）上面設(shè)計(jì)的缺陷遞歸定義運(yùn)算效率低不可操作簡評(píng)學(xué)習(xí)任務(wù)簡化成發(fā)現(xiàn)一個(gè)理想目標(biāo)函數(shù)V的可操作描述。通常要完美地學(xué)習(xí)這樣一個(gè)V的可操作的形式是非常困難的。一般地，我們僅希望學(xué)習(xí)演算法得到近似的目標(biāo)函數(shù)V’，因此學(xué)習(xí)目標(biāo)函數(shù)的過程常稱為函數(shù)逼近。2003.12.1813選擇目標(biāo)函數(shù)的表示函數(shù)的表示一張大表，對(duì)於每個(gè)唯一的棋盤狀態(tài)，表中有唯一的表項(xiàng)來確定它的狀態(tài)值規(guī)則集合二項(xiàng)式函數(shù)人工神經(jīng)網(wǎng)路2003.12.1814選擇目標(biāo)函數(shù)的表示（2）重要的權(quán)衡過程一方面，我們總希望選區(qū)一個(gè)非常有表現(xiàn)力的描述，以最大可能地逼近理想的目標(biāo)函數(shù)另一方面，越有表現(xiàn)力的描述需要越多的訓(xùn)練數(shù)據(jù)，使程式能從它表示的多種假設(shè)中選擇2003.12.1815選擇目標(biāo)函數(shù)的表示（3）一個(gè)簡單的表示法，對(duì)於任何給定的棋盤狀態(tài)，函數(shù)V可以通過以下棋盤參數(shù)的線性組合來計(jì)算。x1，黑子的數(shù)量x2，紅子的數(shù)量x3，黑王的數(shù)量x4，紅王的數(shù)量x5，被紅子威脅的黑子數(shù)量x6，被黑子威脅的紅子數(shù)量2003.12.1816選擇目標(biāo)函數(shù)的表示（4）目標(biāo)函數(shù)V(b)=w0+w1x1+w2x2+…+w6x6其中，w0…w6是權(quán)值，表示不同棋局特徵的相對(duì)重要性至此，問題轉(zhuǎn)化為學(xué)習(xí)目標(biāo)函數(shù)中的係數(shù)（即權(quán)值）2003.12.1817選擇函數(shù)逼近演算法每個(gè)訓(xùn)練樣例表示成二元對(duì)<b，Vtrain(b)>b是棋盤狀態(tài)，Vtrain(b)是訓(xùn)練值比如，<<x1=0,x2=0,x3=1,x4=0,x5=0,x6=0>,100>訓(xùn)練過程從學(xué)習(xí)器可得到的間接訓(xùn)練經(jīng)驗(yàn)中導(dǎo)出上面的訓(xùn)練樣例調(diào)整係數(shù)wi，最佳擬合這些訓(xùn)練樣例2003.12.1818選擇函數(shù)逼近演算法（2）估計(jì)訓(xùn)練值困難處一個(gè)簡單的方法，Vtrain(b)=V’(Successor(b))調(diào)整權(quán)值最佳擬合的定義，比如誤差平方和最小尋找演算法，比如最小均方法，LMSLeastMeanSquares2003.12.1819最終設(shè)計(jì)實(shí)驗(yàn)生成器執(zhí)行系統(tǒng)泛化器鑒定器新問題解答路線假設(shè)訓(xùn)練樣例2003.12.1820最終設(shè)計(jì)（2）執(zhí)行系統(tǒng)用學(xué)會(huì)的目標(biāo)函數(shù)來解決給定的任務(wù)鑒定器以對(duì)弈的路線或歷史記錄作為輸入，輸出目標(biāo)函數(shù)的一系列訓(xùn)練樣例。泛化器以訓(xùn)練樣例為輸入，產(chǎn)生一個(gè)輸出假設(shè)，作為它對(duì)目標(biāo)函數(shù)的估計(jì)。實(shí)驗(yàn)生成器以當(dāng)前的假設(shè)作為輸入，輸出一個(gè)新的問題，供執(zhí)行系統(tǒng)去探索。2003.12.1821西洋跳棋學(xué)習(xí)的更多討論圖1-2第13章理論上的保證這種學(xué)習(xí)技術(shù)是否確保發(fā)現(xiàn)一個(gè)非常接近的近似。更複雜的目標(biāo)函數(shù)其他學(xué)習(xí)演算法最近鄰演算法，存儲(chǔ)訓(xùn)練樣例，尋找保存的最接近的情形來匹配新的情況遺傳演算法，產(chǎn)生大量候選的西洋跳棋程式，讓它們相互比賽，保留最成功的程式並進(jìn)一步用模擬進(jìn)化的方式來培育或變異它們基於解釋的學(xué)習(xí)，分析每次成敗的原因2003.12.1822機(jī)器學(xué)習(xí)的一個(gè)觀點(diǎn)一個(gè)有效的觀點(diǎn)機(jī)器學(xué)習(xí)問題歸結(jié)於搜索問題本書給出了對(duì)一些基本表示定義的假設(shè)空間的搜索演算法通過搜索策略和搜索空間的內(nèi)在結(jié)構(gòu)來刻畫學(xué)習(xí)方法2003.12.1823機(jī)器學(xué)習(xí)的問題存在什麼樣的演算法能從特定的訓(xùn)練數(shù)據(jù)學(xué)習(xí)一般的目標(biāo)函數(shù)呢？如果提供了充足的訓(xùn)練數(shù)據(jù)，什麼樣的條件下，會(huì)使特定的演算法收斂到期望的函數(shù)？哪個(gè)演算法對(duì)哪些問題和表示的性能最好？多少訓(xùn)練數(shù)據(jù)是充足的？怎樣找到學(xué)習(xí)到假設(shè)的置信度與訓(xùn)練數(shù)據(jù)的數(shù)量及提供給學(xué)習(xí)器的假設(shè)空間特性之間的一般關(guān)係？學(xué)習(xí)器擁有的先驗(yàn)知識(shí)是怎樣引導(dǎo)從樣例進(jìn)行泛化的過程的？當(dāng)先驗(yàn)知識(shí)僅僅是近似正確時(shí)，它們會(huì)有幫助嗎？關(guān)於選擇有效的後驗(yàn)訓(xùn)練經(jīng)驗(yàn)，什麼樣的策略最好？這個(gè)策略的選擇會(huì)如何影響學(xué)習(xí)問題的複雜性。怎樣把學(xué)習(xí)任務(wù)簡化為一個(gè)或多個(gè)函數(shù)逼近問題？換一種方式，系統(tǒng)該試圖學(xué)習(xí)哪些函數(shù)？這個(gè)過程本身能自動(dòng)化嗎？學(xué)習(xí)器怎樣自動(dòng)地改變表示法來提高表示和學(xué)習(xí)目標(biāo)函數(shù)的能力？2003.12.1824全書內(nèi)容簡介第2章，基於符號(hào)和邏輯表示的概念學(xué)習(xí)第3章，決策樹第4章，人工神經(jīng)網(wǎng)路第5章，統(tǒng)計(jì)和估計(jì)理論的基礎(chǔ)概念第6章，貝葉斯理論第7章，計(jì)算學(xué)習(xí)第8章，基於實(shí)例的學(xué)習(xí)第9章，遺傳演算法第10章，規(guī)則學(xué)習(xí)第11章，基於解釋的學(xué)習(xí)第12章，近似知識(shí)與現(xiàn)有數(shù)據(jù)的結(jié)合第13章，增強(qiáng)學(xué)習(xí)2003.12.1825簡介許多機(jī)器學(xué)習(xí)涉及到從特殊訓(xùn)練樣例中得到一般概念。概念，可被看作一個(gè)對(duì)象或事件集合，它是從更大的集合中選取的子集，或在這個(gè)較大集合中定義的布爾函數(shù)。概念學(xué)習(xí)問題的定義給定一個(gè)樣例集合以及每個(gè)樣例是否屬於某個(gè)概念的標(biāo)注，怎樣推斷出該概念的一般定義。又稱從樣例中逼近布爾函數(shù)。概念學(xué)習(xí)是指從有關(guān)某個(gè)布爾函數(shù)的輸入輸出訓(xùn)練樣例中推斷出該布爾函數(shù)。2003.12.1826概念學(xué)習(xí)任務(wù)一個(gè)例子目標(biāo)概念，Aldo進(jìn)行水上運(yùn)動(dòng)的日子，表示為布爾函數(shù)EnjoySport任務(wù)目的，基於某天的各屬性，預(yù)測EnjoySport的值一個(gè)樣例集，每個(gè)樣例表示為屬性的集合2003.12.1827概念學(xué)習(xí)任務(wù)（2）YesChangeCoolStrongHighWarmSunny4YesChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample表2-1目標(biāo)概念EnjoySport的訓(xùn)練樣例2003.12.1828概念學(xué)習(xí)任務(wù)（3）表示假設(shè)的形式一個(gè)簡單的形式，實(shí)例的各屬性約束的合取式令每個(gè)假設(shè)為6個(gè)約束（或變數(shù)）的向量，每個(gè)約束對(duì)應(yīng)一個(gè)屬性可取值範(fàn)圍，為？任意本屬性可接受的值明確指定的屬性值

不接受任何值假設(shè)的例子<?,Cold,High,?,?,?><?,?,?,?,?,?> //所有的樣例都是正例<,,,,,> //所有的樣例都是反例2003.12.1829概念學(xué)習(xí)任務(wù)（4）EnjoySport概念學(xué)習(xí)任務(wù)已知實(shí)例集X每個(gè)實(shí)例x由6個(gè)屬性描述，每個(gè)屬性的取值範(fàn)圍已確定假設(shè)集H每個(gè)假設(shè)h描述為6個(gè)屬性的取值約束的合取目標(biāo)概念c一個(gè)布爾函數(shù)，變數(shù)為實(shí)例訓(xùn)練樣例集D目標(biāo)函數(shù)（或目標(biāo)概念）的正例和反例求解H中的一假設(shè)h，使對(duì)於X中任意x，h(x)=c(x)2003.12.1830術(shù)語定義實(shí)例x實(shí)例集X概念目標(biāo)概念c訓(xùn)練樣例x訓(xùn)練樣例集D正例，目標(biāo)概念成員反例，非目標(biāo)概念成員假設(shè)h假設(shè)集H機(jī)器學(xué)習(xí)的目標(biāo)就是尋找一個(gè)假設(shè)h，使得對(duì)所有的h，都有h(x)=c(x)2003.12.1831歸納學(xué)習(xí)假設(shè)什麼是歸納學(xué)習(xí)？從特殊的樣例得到普遍的規(guī)律歸納只能保證輸出的假設(shè)能與訓(xùn)練樣例相擬合歸納假設(shè)的一個(gè)基本假定對(duì)於未見實(shí)例最好的假設(shè)就是與訓(xùn)練數(shù)據(jù)最佳擬合的假設(shè)歸納學(xué)習(xí)假設(shè)任一假設(shè)如果在足夠大的訓(xùn)練樣例集中很好地逼近目標(biāo)函數(shù)，它也能在未見實(shí)例中很好地逼近目標(biāo)函數(shù)。2003.12.1832作為搜索的概念學(xué)習(xí)概念學(xué)習(xí)可以看作一個(gè)搜索的過程搜索範(fàn)圍：假設(shè)的表示所隱含定義的整個(gè)空間搜索目標(biāo)：能夠最好地?cái)M合訓(xùn)練樣例的假設(shè)當(dāng)假設(shè)的表示形式選定後，那麼就隱含地為學(xué)習(xí)演算法確定了所有假設(shè)的空間例子EnjoySport的假設(shè)空間2003.12.1833假設(shè)的一般到特殊序假設(shè)的一般到特殊序關(guān)係考慮下麵兩個(gè)假設(shè)h1=<sunny,?,?,Strong,?,?>h2=<Sunny,?,?,?,?,?>任何被h1劃分為正例的實(shí)例都會(huì)被h2劃分為正例，因此h2比h1更一般。利用這個(gè)關(guān)係，無需列舉所有假設(shè)，就能在無限的假設(shè)空間中進(jìn)行徹底的搜索2003.12.1834假設(shè)的一般到特殊序（2）關(guān)係“更一般”的精確定義任給實(shí)例x和假設(shè)h，說x滿足h，當(dāng)且僅當(dāng)h(x)=1令hj和hk是在X上定義的布爾函數(shù)，稱hj比hk更一般，當(dāng)且僅當(dāng)(xX)[(hk(x)=1)

(hj(x)=1)]記為hjmore_general_than_or_equal_tohk，或hj

ghk2003.12.1835假設(shè)的一般到特殊序（3）“更一般”的嚴(yán)格情形hj>ghk，當(dāng)且僅當(dāng)，(hj

ghk)

(hk

ghj)“更特殊”關(guān)係的定義hj

ghk，當(dāng)且僅當(dāng)，hk

ghj以EnjoySport為例說明上面的定義偏序的特點(diǎn)（區(qū)別於全序），全序上的搜索可以是二分法，偏序的搜索比無序簡單，比全序複雜。這個(gè)偏序關(guān)係的定義與目標(biāo)概念無關(guān)2003.12.1836Find-S：尋找極大特殊假設(shè)使用more_general_than偏序的搜索演算法從H中最特殊假設(shè)開始，然後在假設(shè)覆蓋正例失敗時(shí)將其一般化表2-3Find-S演算法將h初始化為H中最特殊假設(shè)對(duì)每個(gè)正例x對(duì)h的每個(gè)屬性約束ai如果x滿足ai那麼不做任何處理否則將h中ai替換為x滿足的另一個(gè)更一般約束輸出假設(shè)h2003.12.1837Find-S：尋找極大特殊假設(shè)（2）Find-S演算法在例子EnjoySport上的應(yīng)用h<,,,,,>h<Sunny,Warm,Normal,Strong,Warm,Same>h<Sunny,Warm,?,Strong,Warm,Same>遇到反例，h不變（因?yàn)閔已經(jīng)能夠正確地識(shí)別反例）h<Sunny,Warm,?,Strong,?,?>2003.12.1838Find-S：尋找極大特殊假設(shè)（3）Find-S演算法演示了一種利用more_general_than偏序來搜索假設(shè)空間的方法，沿著偏序鏈，從較特殊的假設(shè)逐漸轉(zhuǎn)移到較一般的假設(shè)。因此，每一步得到的假設(shè)都是在那一點(diǎn)上與訓(xùn)練樣例一致的最特殊的假設(shè)。Find-S的重要特點(diǎn)：對(duì)以屬性約束的合取式描述的假設(shè)空間H，保證輸出為H中與正例一致的最特殊的假設(shè)。存在的問題是否收斂到了正確的目標(biāo)概念？為什麼要用最特殊的假設(shè)？訓(xùn)練樣例是否相互一致？如果有多個(gè)極大特殊假設(shè)怎麼辦？2003.12.1839變型空間和候選消除演算法候選消除演算法概說概念學(xué)習(xí)的另一種方法，候選消除演算法（candidate-elimination）Find-S演算法的不足，輸出的假設(shè)只是H中能夠擬合訓(xùn)練樣例的多個(gè)假設(shè)中的一個(gè)候選消除演算法輸出與訓(xùn)練樣例一致的所有假設(shè)的集合候選消除演算法在描述這一集合時(shí)不需要明確列舉所有成員利用more_general_than偏序結(jié)構(gòu)，可以維護(hù)一個(gè)一致假設(shè)集合的簡潔表示候選消除演算法的應(yīng)用，化學(xué)質(zhì)譜分析、啟發(fā)式搜索的控制規(guī)則候選消除演算法的缺點(diǎn)，容錯(cuò)性能差2003.12.1840變型空間和候選消除演算法（2）“一致”的定義一個(gè)假設(shè)h與訓(xùn)練樣例集合D一致，當(dāng)且僅當(dāng)對(duì)D中每一個(gè)樣例<x,c(x)>都有h(x)=c(x)，即Consistent(h,D)(<x,c(x)>D)h(x)=c(x)“一致”與“滿足”的關(guān)係變型空間（versionspace）與訓(xùn)練樣例一致的所有假設(shè)組成的集合表示了目標(biāo)概念的所有合理的變型關(guān)於H和D的變型空間，記為VSH,D，是H中與訓(xùn)練樣例D一致的所有假設(shè)構(gòu)成的子集VSH,D={hH|Consistent(h,D)}2003.12.1841變型空間和候選消除演算法（3）列表後消除演算法表示變型空間的一種方法是列出其所有成員變型空間

包含H中所有假設(shè)的列表對(duì)每個(gè)訓(xùn)練樣例<x,c(x)>，從變型空間中移除所有h(x)

c(x)的假設(shè)輸出VersionSpace中的假設(shè)列表優(yōu)點(diǎn)保證得到所有與訓(xùn)練數(shù)據(jù)一致的假設(shè)缺點(diǎn)非常繁瑣地列出H中的所有假設(shè)，大多數(shù)實(shí)際的假設(shè)空間無法做到2003.12.1842變型空間和候選消除演算法（4）變型空間的更簡潔表示變型空間被表示為它的極大一般和極大特殊的成員這些成員形成了一般和特殊邊界的集合，這些邊界在整個(gè)偏序結(jié)構(gòu)中劃分出變型空間以EnjoySport為例2003.12.1843變型空間和候選消除演算法（5）形式化定義極大一般極大特殊關(guān)於假設(shè)空間H和訓(xùn)練數(shù)據(jù)D的一般邊界G，是在H中與D相一致的極大一般成員的集合關(guān)於假設(shè)空間H和訓(xùn)練數(shù)據(jù)D的特殊邊界S，是在H中與D相一致的極大特殊成員的集合2003.12.1844變型空間和候選消除演算法（6）變型空間表示定理，令X為一任意的實(shí)例集合，H為X上定義的布爾假設(shè)的集合。令c:X

{0,1}為X上定義的任一目標(biāo)概念，並令D為任一訓(xùn)練樣例集合{<x,c(x)>}。對(duì)所有的X,H,c,D以及良好定義的S和G：

VSH,D={h

H|(

s

S)(

g

G)(g

gh

gs)}證明：只需證明：1）每一個(gè)滿足上式右邊的h都在VSH,D中，2）VSH,D的每個(gè)成員都滿足都滿足等式右邊?！?003.12.1845變型空間和候選消除演算法（7）候選消除演算法初始化G和S如果d是一個(gè)正例從G中移去所有與d不一致的假設(shè)對(duì)S中每個(gè)與d不一致的假設(shè)s從S中移去s把s的所有的極小泛化式h加入到S中，其中h滿足h與d一致，而且G的某個(gè)成員比h更一般如果d是一個(gè)反例從S中移去所有與d不一致的假設(shè)對(duì)G中每個(gè)與d不一致的假設(shè)g從G中移去g把g的所有的極小特殊化式h加入到G中，其中h滿足h與d一致，而且S的某個(gè)成員比h更特殊從G中移去所有這樣的假設(shè)：它比G中另一個(gè)假設(shè)更特殊2003.12.1846變型空間和候選消除演算法（8）演算法舉例2003.12.1847變型空間和候選消除的說明候選消除演算法收斂到正確的假設(shè)訓(xùn)練樣例中沒有錯(cuò)誤H中確實(shí)包含描述目標(biāo)概念的正確假設(shè)如果樣例中存在錯(cuò)誤如果給定足夠的訓(xùn)練數(shù)據(jù)，我們會(huì)發(fā)現(xiàn)S和G邊界收斂得到一個(gè)空的變型空間如果目標(biāo)概念不能由假設(shè)表示方式所描述相似情況出現(xiàn)2003.12.1848變型空間和候選消除（2）下一步需要什麼樣的訓(xùn)練樣例一般來說，概念學(xué)習(xí)的最優(yōu)查詢策略，是產(chǎn)生實(shí)例以滿足當(dāng)前變型空間中大約半數(shù)的假設(shè)。這樣，變型空間的大小可以在遇到每個(gè)新樣例時(shí)減半，正確的目標(biāo)概念就可在只用log2|VS|次實(shí)驗(yàn)後得到。2003.12.1849變型空間和候選消除（3）怎樣使用不完全學(xué)習(xí)概念雖然圖2-3的變型空間中仍包含多個(gè)假設(shè)，即目標(biāo)概念還未學(xué)習(xí)到，但是仍然有可能對(duì)新樣例進(jìn)行一定可信度的分類。表2-6的例子2003.12.1850歸納偏置有關(guān)候選消除演算法的幾個(gè)問題如果目標(biāo)概念不在假設(shè)空間中怎麼辦？是否可設(shè)計(jì)一個(gè)包含所有假設(shè)的空間來解決這一困難？假設(shè)空間的大小對(duì)於演算法推廣到未見實(shí)例的能力有什麼影響？假設(shè)空間的大小對(duì)所需訓(xùn)練樣例的數(shù)量有什麼影響？2003.12.1851歸納偏置（2）一個(gè)有偏的假設(shè)空間在EnjoySport這個(gè)例子中，假設(shè)空間限制為只包含屬性值的合取。（有偏）這一限制，導(dǎo)致假設(shè)空間不能夠表示最簡單的析取形式的目標(biāo)概念。2003.12.1852歸納偏置（3）無偏的學(xué)習(xí)器為了保證目標(biāo)概念在假設(shè)空間中，需要提供一個(gè)假設(shè)空間，它能表達(dá)所有的可教授概念。換言之，它能表達(dá)實(shí)例集X的所有子集。問題：為什麼2.3節(jié)中合取假設(shè)空間只能表示973個(gè)假設(shè)？2003.12.1853歸納偏置（4）EnjoySport的無偏形式帶來的問題：概念學(xué)習(xí)演算法無法從訓(xùn)練樣例中泛化。要想獲得單個(gè)目標(biāo)概念，就必須提供X中所有實(shí)例作為訓(xùn)練樣例使用2.6.3節(jié)討論的部分學(xué)習(xí)的無效2003.12.1854歸納偏置（5）無偏學(xué)習(xí)的無用性歸納學(xué)習(xí)的一個(gè)基本屬性：學(xué)習(xí)器如果不對(duì)目標(biāo)概念的形式做預(yù)先的假定，它從根本上無法對(duì)未見實(shí)例進(jìn)行分類歸納學(xué)習(xí)需要的預(yù)先假定，稱為歸納偏置2003.12.1855歸納偏置（6）歸納偏置的精確定義(Dc

xi)

L(xi,Dc)需要在Dc

xi上附加怎樣的前提，以使L(xi,Dc)能夠演繹派生。L的歸納偏置定義為前提集合B，使所有的新實(shí)例滿足：

(B

Dc

xi)

L(xi,Dc)考慮對(duì)於實(shí)例集合X的概念學(xué)習(xí)演算法L。令c為X上定義的任一概念，並令Dc為c的任意訓(xùn)練樣例集合，L(xi,Dc)表示經(jīng)過Dc訓(xùn)練後L賦予實(shí)例xi的分類。L的歸納偏置是最小斷言集合B，它使任意目標(biāo)概念c和相應(yīng)的訓(xùn)練樣例Dc滿足：

xi

X[(B

Dc

xi)

L(xi,Dc)]2003.12.1856歸納偏置（6）候選消除演算法的歸納偏置{c

H}3個(gè)有偏程度不同的歸納學(xué)習(xí)演算法機(jī)械式候選消除演算法Find-S一種演算法的有偏性越強(qiáng)，它的歸納能力越強(qiáng)，可以分類更多的未見實(shí)例。某些歸納偏置隱含在學(xué)習(xí)器中，有些表示為斷言集合，可由學(xué)習(xí)器操作。2003.12.1857小結(jié)主要內(nèi)容概念學(xué)習(xí)可看作搜索預(yù)定義潛在假設(shè)空間的過程假設(shè)的一般到特殊偏序結(jié)構(gòu)可以定義在任何概念學(xué)習(xí)問題中，這種結(jié)構(gòu)便於假設(shè)空間的搜索Find-S演算法使用一般到特殊序，在偏序結(jié)構(gòu)的一個(gè)分支上執(zhí)行一般到特殊搜索，尋找一個(gè)與樣例一致的最特殊假設(shè)候選消除演算法利用一般到特殊序，通過漸進(jìn)地計(jì)算極大特殊假設(shè)集合和極大一般假設(shè)集合發(fā)現(xiàn)變型空間候選消除演算法缺少健壯性，第10章描述了幾種基於一般到特殊序關(guān)係的概念學(xué)習(xí)演算法，它們能夠處理有雜訊的數(shù)據(jù)和目標(biāo)概念無法在假設(shè)空間中表示的情況歸納學(xué)習(xí)演算法隱含了歸納偏置，候選消除演算法的偏置是：目標(biāo)概念可以在假設(shè)空間中找到。輸出的假設(shè)和對(duì)新實(shí)例的分類可由歸納偏置和訓(xùn)練樣例演繹推出2003.11.1858概論決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理演算法之一是一種逼近離散值函數(shù)的方法很好的健壯性能夠?qū)W習(xí)析取運(yùn)算式ID3,Assistant,C4.5搜索一個(gè)完整表示的假設(shè)空間歸納偏置是優(yōu)先選擇較小的樹決策樹表示了多個(gè)if-then規(guī)則2003.11.1859提綱決策樹定義適用問題特徵基本ID3演算法決策樹學(xué)習(xí)的歸納偏置訓(xùn)練數(shù)據(jù)的過度擬合更深入的話題2003.11.1860決策樹表示法決策樹通過把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來分類實(shí)例。葉子節(jié)點(diǎn)即為實(shí)例所屬的分類樹上每個(gè)節(jié)點(diǎn)說明了對(duì)實(shí)例的某個(gè)屬性的測試節(jié)點(diǎn)的每個(gè)後繼分支對(duì)應(yīng)於該屬性的一個(gè)可能值圖3-1決策樹代表實(shí)例屬性值約束的合取的析取式。從樹根到樹葉的每一條路徑對(duì)應(yīng)一組屬性測試的合取，樹本身對(duì)應(yīng)這些合取的析取。2003.11.1861決策樹學(xué)習(xí)的適用問題適用問題的特徵實(shí)例由“屬性-值”對(duì)表示目標(biāo)函數(shù)具有離散的輸出值可能需要析取的描述訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例問題舉例根據(jù)疾病分類患者根據(jù)起因分類設(shè)備故障根據(jù)拖欠支付的可能性分類貸款申請(qǐng)分類問題核心任務(wù)是把樣例分類到各可能的離散值對(duì)應(yīng)的類別2003.11.1862基本的決策樹學(xué)習(xí)演算法大多數(shù)決策樹學(xué)習(xí)演算法是一種核心演算法的變體採用自頂向下的貪婪搜索遍曆可能的決策樹空間ID3是這種演算法的代表2003.11.1863基本的決策樹學(xué)習(xí)演算法（2）ID3的思想自頂向下構(gòu)造決策樹從“哪一個(gè)屬性將在樹的根節(jié)點(diǎn)被測試”開始使用統(tǒng)計(jì)測試來確定每一個(gè)實(shí)例屬性單獨(dú)分類訓(xùn)練樣例的能力ID3的過程分類能力最好的屬性被選作樹的根節(jié)點(diǎn)根節(jié)點(diǎn)的每個(gè)可能值產(chǎn)生一個(gè)分支訓(xùn)練樣例排列到適當(dāng)?shù)姆种е匮}上面的過程2003.11.1864表3-1用於學(xué)習(xí)布爾函數(shù)的ID3演算法概要ID3(Examples,Target_attribute,Attributes)創(chuàng)建樹的root節(jié)點(diǎn)如果Examples都為正,返回label=+的單節(jié)點(diǎn)樹root如果Examples都為反,返回label=-的單節(jié)點(diǎn)樹root如果Attributes為空，那麼返回單節(jié)點(diǎn)root，label=Examples中最普遍的Target_attribute值否則開始A

Attributes中分類examples能力最好的屬性root的決策屬性A對(duì)於A的每個(gè)可能值vi在root下加一個(gè)新的分支對(duì)應(yīng)測試A=vi令Examplesvi為Examples中滿足A屬性值為vi的子集如果Examplesvi為空在這個(gè)新分支下加一個(gè)葉子節(jié)點(diǎn)，節(jié)點(diǎn)的label=Examples中最普遍的Target_attribute值否則在新分支下加一個(gè)子樹ID3（Examplesvi,Target_attribute,Attributes-{A}）結(jié)束返回root2003.11.1865最佳分類屬性資訊增益用來衡量給定的屬性區(qū)分訓(xùn)練樣例的能力ID3演算法在增長樹的每一步使用資訊增益從候選屬性中選擇屬性用熵度量樣例的均一性熵刻畫了任意樣例集的純度給定包含關(guān)於某個(gè)目標(biāo)概念的正反樣例的樣例集S，那麼S相對(duì)這個(gè)布爾型分類的熵為

Entropy(S)=-p+log2p+-p-log2p-資訊理論中對(duì)熵的一種解釋，熵確定了要編碼集合S中任意成員的分類所需要的最少二進(jìn)位位數(shù)更一般地，如果目標(biāo)屬性具有c個(gè)不同的值，那麼S相對(duì)於c個(gè)狀態(tài)的分類的熵定義為

Entropy(S)=2003.11.1866最佳分類屬性（2）用資訊增益度量期望的熵降低屬性的資訊增益，由於使用這個(gè)屬性分割樣例而導(dǎo)致的期望熵降低

Gain(S,A)是在知道屬性A的值後可以節(jié)省的二進(jìn)位位數(shù)例子2003.11.1867ID3演算法舉例表3-2…繼續(xù)這個(gè)過程，直到滿足以下兩個(gè)條件中的一個(gè)所有的屬性已經(jīng)被這條路經(jīng)包括與這個(gè)節(jié)點(diǎn)關(guān)聯(lián)的所有訓(xùn)練樣例都具有相同的目標(biāo)屬性值2003.11.1868決策樹學(xué)習(xí)中的假設(shè)空間搜索觀察ID3的搜索空間和搜索策略，認(rèn)識(shí)到這個(gè)演算法的優(yōu)勢和不足假設(shè)空間包含所有的決策樹，它是關(guān)於現(xiàn)有屬性的有限離散值函數(shù)的一個(gè)完整空間維護(hù)單一的當(dāng)前假設(shè)（不同於第二章的變型空間候選消除演算法）不進(jìn)行回溯，可能收斂到局部最優(yōu)每一步使用所有的訓(xùn)練樣例，不同於基於單獨(dú)的訓(xùn)練樣例遞增作出決定，容錯(cuò)性增強(qiáng)2003.11.1869決策樹學(xué)習(xí)的歸納偏置ID3的搜索策略優(yōu)先選擇較短的樹選擇那些資訊增益高的屬性離根節(jié)點(diǎn)較近的樹很難準(zhǔn)確刻畫ID3的歸納偏置近似的ID3的歸納偏置較短的樹比較長的樹優(yōu)先近似在於ID3得到局部最優(yōu)，而不一定是全局最優(yōu)一個(gè)精確具有這個(gè)歸納偏置的演算法，BFS-ID3更貼切近似的歸納偏置較短的樹比較長的樹優(yōu)先，資訊增益高的屬性更靠近根節(jié)點(diǎn)的樹優(yōu)先2003.11.1870限定偏置和優(yōu)選偏置ID3和候選消除演算法的比較ID3的搜索範(fàn)圍是一個(gè)完整的假設(shè)空間，但不徹底地搜索這個(gè)空間候選消除演算法的搜索範(fàn)圍是不完整的假設(shè)空間，但徹底地搜索這個(gè)空間ID3的歸納偏置完全是搜索策略排序假設(shè)的結(jié)果，來自搜索策略候選消除演算法完全是假設(shè)表示的表達(dá)能力的結(jié)果，來自對(duì)搜索空間的定義2003.11.1871限定偏置和優(yōu)選偏置優(yōu)選偏置ID3的歸納偏置是對(duì)某種假設(shè)勝過其他假設(shè)的一種優(yōu)選，對(duì)最終可列舉的假設(shè)沒有硬性限制限定偏置候選消除演算法的偏置是對(duì)待考慮假設(shè)的一種限定通常優(yōu)選偏置比限定偏置更符合歸納學(xué)習(xí)的需要優(yōu)選偏置和限定偏置的結(jié)合考慮第1章的例子2003.11.1872為什麼短的假設(shè)優(yōu)先ID3的歸納偏置的哲學(xué)基礎(chǔ)奧坎姆剃刀優(yōu)先選擇擬合數(shù)據(jù)的最簡單的假設(shè)科學(xué)上的例子物理學(xué)家優(yōu)先選擇行星運(yùn)動(dòng)的簡單假設(shè)簡單假設(shè)的數(shù)量遠(yuǎn)比複雜假設(shè)的數(shù)量少簡單假設(shè)對(duì)訓(xùn)練樣例的針對(duì)性更小，更像是泛化的規(guī)律，而不是訓(xùn)練樣例的另一種描述2003.11.1873為什麼短的假設(shè)優(yōu)先奧坎姆剃刀的困難我們反問，使用上頁的推理，應(yīng)該優(yōu)先選擇包含恰好17個(gè)葉子節(jié)點(diǎn)和11個(gè)非葉子節(jié)點(diǎn)的決策樹？假設(shè)的規(guī)模由學(xué)習(xí)器內(nèi)部使用的特定表示決定從生物進(jìn)化的觀點(diǎn)看內(nèi)部表示和奧坎姆剃刀原則2003.11.1874決策樹學(xué)習(xí)的常見問題決策樹學(xué)習(xí)的實(shí)際問題確定決策樹增長的深度處理連續(xù)值的屬性選擇一個(gè)適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)處理屬性值不完整的訓(xùn)練數(shù)據(jù)處理不同代價(jià)的屬性提高計(jì)算效率針對(duì)這些問題，ID3被擴(kuò)展成C4.52003.11.1875避免過度擬合數(shù)據(jù)過度擬合對(duì)於一個(gè)假設(shè)，當(dāng)存在其他的假設(shè)對(duì)訓(xùn)練樣例的擬合比它差，但事實(shí)上在實(shí)例的整個(gè)分佈上表現(xiàn)得卻更好時(shí)，我們說這個(gè)假設(shè)過度擬合訓(xùn)練樣例定義：給定一個(gè)假設(shè)空間H，一個(gè)假設(shè)h

H，如果存在其他的假設(shè)h’

H，使得在訓(xùn)練樣例上h的錯(cuò)誤率比h’小，但在整個(gè)實(shí)例分佈上h’的錯(cuò)誤率比h小，那麼就說假設(shè)h過度擬合訓(xùn)練數(shù)據(jù)。圖3-6的例子2003.11.1876避免過度擬合數(shù)據(jù)（2）導(dǎo)致過度擬合的原因一種可能原因是訓(xùn)練樣例含有隨機(jī)錯(cuò)誤或雜訊當(dāng)訓(xùn)練數(shù)據(jù)沒有雜訊時(shí)，過度擬合也有可能發(fā)生，特別是當(dāng)少量的樣例被關(guān)聯(lián)到葉子節(jié)點(diǎn)時(shí)，很可能出現(xiàn)巧合的規(guī)律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實(shí)際的目標(biāo)函數(shù)並無關(guān)系。2003.11.1877避免過度擬合數(shù)據(jù)（3）避免過度擬合的方法及早停止樹增長後修剪法兩種方法的特點(diǎn)第一種方法更直觀第一種方法中，精確地估計(jì)何時(shí)停止樹增長很困難第二種方法被證明在實(shí)踐中更成功2003.11.1878避免過度擬合數(shù)據(jù)（4）避免過度擬合的關(guān)鍵使用什麼樣的準(zhǔn)則來確定最終正確樹的規(guī)模解決方法使用與訓(xùn)練樣例截然不同的一套分離的樣例，來評(píng)估通過後修剪方法從樹上修建節(jié)點(diǎn)的效用。使用所有可用數(shù)據(jù)進(jìn)行訓(xùn)練，但進(jìn)行統(tǒng)計(jì)測試來估計(jì)擴(kuò)展（或修剪）一個(gè)特定的節(jié)點(diǎn)是否有可能改善在訓(xùn)練集合外的實(shí)例上的性能。使用一個(gè)明確的標(biāo)準(zhǔn)來衡量訓(xùn)練樣例和決策樹的複雜度，當(dāng)這個(gè)編碼的長度最小時(shí)停止樹增長。2003.11.1879避免過度擬合數(shù)據(jù)（5）方法評(píng)述第一種方法是最普通的，常被稱為訓(xùn)練和驗(yàn)證集法。可用數(shù)據(jù)分成兩個(gè)樣例集合：訓(xùn)練集合，形成學(xué)習(xí)到的假設(shè)驗(yàn)證集合，評(píng)估這個(gè)假設(shè)在後續(xù)數(shù)據(jù)上的精度方法的動(dòng)機(jī)：即使學(xué)習(xí)器可能會(huì)被訓(xùn)練集合誤導(dǎo)，但驗(yàn)證集合不大可能表現(xiàn)出同樣的隨機(jī)波動(dòng)驗(yàn)證集合應(yīng)該足夠大，以便它本身可提供具有統(tǒng)計(jì)意義的實(shí)例樣本。常見的做法是，樣例的三分之二作訓(xùn)練集合，三分之一作驗(yàn)證集合。2003.11.1880錯(cuò)誤率降低修剪將樹上的每一個(gè)節(jié)點(diǎn)作為修剪得候選對(duì)象修剪步驟刪除以此節(jié)點(diǎn)為根的子樹，使它成為葉結(jié)點(diǎn)把和該節(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例的最常見分類賦給它反復(fù)修剪節(jié)點(diǎn)，每次總是選取那些刪除後可以最大提高決策樹在驗(yàn)證集合上的精度的節(jié)點(diǎn)繼續(xù)修剪，直到進(jìn)一步的修剪是有害的為止數(shù)據(jù)分成3個(gè)子集訓(xùn)練樣例，形成決策樹驗(yàn)證樣例，修剪決策樹測試樣例，精度的無偏估計(jì)如果有大量的數(shù)據(jù)可供使用，那麼使用分離的數(shù)據(jù)集合來引導(dǎo)修剪2003.11.1881規(guī)則後修剪從訓(xùn)練集合推導(dǎo)出決策樹，增長決策樹直到盡可能好地?cái)M合訓(xùn)練數(shù)據(jù)，允許過度擬合發(fā)生將決策樹轉(zhuǎn)化為等價(jià)的規(guī)則集合，方法是為從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑創(chuàng)建一條規(guī)則通過刪除任何能導(dǎo)致估計(jì)精度提高的前件來修剪每一條規(guī)則按照修剪過的規(guī)則的估計(jì)精度對(duì)它們進(jìn)行排序，並按這樣的順序應(yīng)用這些規(guī)則來分類後來的實(shí)例2003.11.1882規(guī)則後修剪（2）例子圖3-1的最左一條路徑if(outlook=sunny)

(Humidity=High)thenPlayTennis=No考慮刪除先行詞(outlook=sunny)和(Humidity=High)選擇使估計(jì)精度有最大提升的步驟考慮修剪第二個(gè)前件2003.11.1883規(guī)則後修剪（3）規(guī)則精度估計(jì)方法使用與訓(xùn)練集不相交的驗(yàn)證集基於訓(xùn)練集合本身被C4.5使用，使用一種保守估計(jì)來彌補(bǔ)訓(xùn)練數(shù)據(jù)有利於當(dāng)前規(guī)則的估計(jì)偏置過程先計(jì)算規(guī)則在它應(yīng)用的訓(xùn)練樣例上的精度然後假定此估計(jì)精度為二項(xiàng)式分佈，並計(jì)算它的標(biāo)準(zhǔn)差對(duì)於一個(gè)給定的置信區(qū)間，採用下界估計(jì)作為規(guī)則性能的度量評(píng)論對(duì)於大的數(shù)據(jù)集，保守預(yù)測非常接近觀察精度，隨著數(shù)據(jù)集合的減小，離觀察精度越來越遠(yuǎn)不是統(tǒng)計(jì)有效（此概念第5章介紹），但是實(shí)踐中發(fā)現(xiàn)有效2003.11.1884規(guī)則後修剪（4）把決策樹轉(zhuǎn)化成規(guī)則集的好處可以區(qū)分決策節(jié)點(diǎn)使用的不同上下文消除了根節(jié)點(diǎn)附近的屬性測試和葉節(jié)點(diǎn)附近的屬性測試的區(qū)別提高了可讀性2003.11.1885合併連續(xù)值屬性ID3被限制為取離散值的屬性學(xué)習(xí)到的決策樹要預(yù)測的目標(biāo)屬性必須是離散的樹的決策節(jié)點(diǎn)的屬性也必須是離散的簡單刪除上面第2個(gè)限制的方法通過動(dòng)態(tài)地定義新的離散值屬性來實(shí)現(xiàn)，即先把連續(xù)值屬性的值域分割為離散的區(qū)間集合2003.11.1886合併連續(xù)值屬性（2）例子，Temperature應(yīng)該定義什麼樣的基於閾值的布爾屬性選擇產(chǎn)生最大資訊增益的閾值按照連續(xù)屬性排列樣例，確定目標(biāo)分類不同的相鄰實(shí)例產(chǎn)生一組候選閾值，它們的值是相應(yīng)的A值之間的中間值可以證明產(chǎn)生最大資訊增益的c值位於這樣的邊界中（Fayyad1991）通過計(jì)算與每個(gè)候選閾值關(guān)聯(lián)的資訊增益評(píng)估這些候選值方法的擴(kuò)展連續(xù)的屬性分割成多個(gè)區(qū)間，而不是單一閾值的兩個(gè)空間2003.11.1887屬性選擇的其他度量標(biāo)準(zhǔn)資訊增益度量存在一個(gè)內(nèi)在偏置，偏向具有較多值的屬性避免方法，其他度量，比如增益比率增益比率通過加入一個(gè)被稱作分裂資訊的項(xiàng)來懲罰多值屬性，分裂資訊用來衡量屬性分裂數(shù)據(jù)的廣度和均勻性

SplitInformation(S,A)= GainRatio(S,A)=分裂資訊項(xiàng)阻礙選擇值為均勻分佈的屬性問題，當(dāng)某個(gè)Si

S。解決方法：採用一些啟發(fā)式規(guī)則，比如僅對(duì)增益高過平均值的屬性應(yīng)用增益比率測試2003.11.1888屬性選擇的其他度量標(biāo)準(zhǔn)（2）基於距離的度量定義了數(shù)據(jù)劃分間的一種距離尺度計(jì)算每個(gè)屬性產(chǎn)生的劃分與理想劃分間的距離選擇最接近完美劃分的屬性LopezdeMantaras定義了這個(gè)距離度量，證明了它不偏向有大量值的屬性此外Mingers實(shí)驗(yàn)，不同的屬性選擇度量對(duì)最終精度的影響小於後修剪得程度和方法的影響2003.11.1889缺少屬性值的訓(xùn)練樣例例子，醫(yī)學(xué)領(lǐng)域經(jīng)常需要根據(jù)此屬性值已知的實(shí)例來估計(jì)這個(gè)缺少的屬性值為了評(píng)估屬性A是否是決策節(jié)點(diǎn)n的最佳測試屬性，要計(jì)算決策樹在該節(jié)點(diǎn)的資訊增益Gain(S,A)。假定<x,c(x)>是S中的一個(gè)訓(xùn)練樣例，並且其屬性A的值A(chǔ)(x)未知2003.11.1890缺少屬性值的訓(xùn)練樣例（2）處理缺少屬性值的一種策略是賦給它節(jié)點(diǎn)n的訓(xùn)練樣例中該屬性的最常見值另一種策略是賦給它節(jié)點(diǎn)n的被分類為c(x)的訓(xùn)練樣例中該屬性的最常見值更複雜的策略，為A的每個(gè)可能值賦予一個(gè)概率，而不是簡單地將最常見的值賦給A(x)2003.11.1891處理不同代價(jià)的屬性實(shí)例的屬性可能與代價(jià)相關(guān)優(yōu)先選擇盡可能使用低代價(jià)屬性的決策樹，僅當(dāng)需要產(chǎn)生可靠的分類時(shí)才依賴高代價(jià)屬性通過引入一個(gè)代價(jià)項(xiàng)到屬性選擇度量中，可以使ID3演算法考慮屬性代價(jià)Tan和Schlimmer的例子2003.11.1892小結(jié)和補(bǔ)充讀物決策樹學(xué)習(xí)為概念學(xué)習(xí)和學(xué)習(xí)其他離散值的函數(shù)提供了一個(gè)實(shí)用的方法ID3演算法貪婪演算法從根向下推斷決策樹搜索完整的假設(shè)空間歸納偏置，較小的樹過度擬合問題ID3演算法的擴(kuò)展2003.11.1893小結(jié)和補(bǔ)充讀物（2）HuntQuinlanMingers2003.12.1894概述人工神經(jīng)網(wǎng)路提供了一種普遍且實(shí)用的方法從樣例中學(xué)習(xí)值為實(shí)數(shù)、離散值或向量的函數(shù)反向傳播演算法，使用梯度下降來調(diào)節(jié)網(wǎng)路參數(shù)以最佳擬合由輸入-輸出對(duì)組成的訓(xùn)練集合人工神經(jīng)網(wǎng)路對(duì)於訓(xùn)練數(shù)據(jù)中的錯(cuò)誤健壯性很好人工神經(jīng)網(wǎng)路已被成功應(yīng)用到很多領(lǐng)域，例如視覺場景分析，語音識(shí)別，機(jī)器人控制2003.12.1895簡介神經(jīng)網(wǎng)路學(xué)習(xí)對(duì)於逼近實(shí)數(shù)值、離散值或向量值的目標(biāo)函數(shù)提供了一種健壯性很強(qiáng)的方法對(duì)於某些類型的問題，如學(xué)習(xí)解釋複雜的現(xiàn)實(shí)世界中的感測器數(shù)據(jù)，人工神經(jīng)網(wǎng)路是目前知道的最有效的學(xué)習(xí)方法反向傳播演算法成功例子，學(xué)習(xí)識(shí)別手寫字元，學(xué)習(xí)識(shí)別口語，學(xué)習(xí)識(shí)別人臉2003.12.1896生物學(xué)動(dòng)機(jī)ANN受到生物學(xué)的啟發(fā)，生物的學(xué)習(xí)系統(tǒng)是由相互連接的神經(jīng)元組成的異常複雜的網(wǎng)路。ANN由一系列簡單的單元相互密集連接構(gòu)成的，其中每一個(gè)單元有一定數(shù)量的實(shí)值輸入，並產(chǎn)生單一的實(shí)數(shù)值輸出人腦的構(gòu)成，大約有1011個(gè)神經(jīng)元，平均每一個(gè)與其他104個(gè)相連神經(jīng)元的活性通常被通向其他神經(jīng)元的連接啟動(dòng)或抑制最快的神經(jīng)元轉(zhuǎn)換時(shí)間比電腦慢很多，然而人腦能夠以驚人的速度做出複雜度驚人的決策很多人推測，生物神經(jīng)系統(tǒng)的資訊處理能力一定得益於對(duì)分佈在大量神經(jīng)元上的資訊表示的高度並行處理2003.12.1897生物學(xué)動(dòng)機(jī)（2）ANN系統(tǒng)的一個(gè)動(dòng)機(jī)就是獲得這種基於分佈表示的高度並行演算法ANN並未模擬生物神經(jīng)系統(tǒng)中的很多複雜特徵ANN的研究分為兩個(gè)團(tuán)體使用ANN研究和模擬生物學(xué)習(xí)過程獲得高效的機(jī)器學(xué)習(xí)演算法，不管這種演算法是否反映了生物過程本書屬於後一個(gè)研究團(tuán)體2003.12.1898神經(jīng)網(wǎng)路表示ALVINN系統(tǒng)Pomerleau1993使用一個(gè)學(xué)習(xí)到的ANN以正常的速度在高速公路上駕駛汽車ANN的輸入是一個(gè)30x32像素的網(wǎng)格，輸出是車輛行進(jìn)的方向每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)網(wǎng)路單元的輸出，而從下方進(jìn)入節(jié)點(diǎn)的實(shí)線為其輸入隱藏單元，輸出僅在網(wǎng)路內(nèi)部，不是整個(gè)網(wǎng)路輸出的一部分每個(gè)輸出單元對(duì)應(yīng)一個(gè)特定的駕駛方向，這些單元的輸出決定哪一個(gè)方向是被最強(qiáng)烈推薦的2003.12.1899神經(jīng)網(wǎng)路表示（2）ALVINN是很多ANN的典型結(jié)構(gòu)，所有單元分層互連形成一個(gè)有向無環(huán)圖通常，ANN圖結(jié)構(gòu)可以有很多種類型無環(huán)或有環(huán)有向或無向本章討論以反向傳播演算法為基礎(chǔ)的ANN方法反向傳播演算法假定網(wǎng)路是一個(gè)固定結(jié)構(gòu)，對(duì)應(yīng)一個(gè)有向圖，可能包含環(huán)ANN學(xué)習(xí)就是為圖中每一條邊選取權(quán)值大多數(shù)實(shí)際應(yīng)用與ALVINN相似2003.12.18100適合神經(jīng)網(wǎng)路學(xué)習(xí)的問題訓(xùn)練集合為含有雜訊的複雜感測器數(shù)據(jù)，例如來自攝像機(jī)和麥克風(fēng)需要較多符號(hào)表示的問題，例如決策樹學(xué)習(xí)的任務(wù)，能夠取得和決策樹學(xué)習(xí)大體相當(dāng)?shù)慕Y(jié)果反向傳播演算法是最常用的ANN學(xué)習(xí)技術(shù)2003.12.18101反向傳播演算法適合問題的特徵實(shí)例是用很多“屬性-值”對(duì)表示的目標(biāo)函數(shù)的輸出可能是離散值、實(shí)數(shù)值或者由若干實(shí)數(shù)屬性或離散屬性組成的向量訓(xùn)練數(shù)據(jù)可能包含錯(cuò)誤可容忍長時(shí)間的訓(xùn)練可能需要快速求出目標(biāo)函數(shù)值人類能否理解學(xué)到的目標(biāo)函數(shù)是不重要的2003.12.18102本章餘後部分提綱討論訓(xùn)練單個(gè)單元的學(xué)習(xí)演算法介紹組成神經(jīng)網(wǎng)路的幾種主要單元感知器（perceptron）線性單元（linerunit）sigmoid單元（sigmoidunit）給出訓(xùn)練多層網(wǎng)路的反向傳播演算法考慮幾個(gè)一般性問題ANN的表徵能力假設(shè)空間搜索的本質(zhì)特徵過度擬合問題反向傳播演算法的變體例子，利用反向傳播演算法訓(xùn)練識(shí)別人臉的ANN2003.12.18103感知器一種類型的ANN系統(tǒng)是以感知器為基礎(chǔ)感知器以一個(gè)實(shí)數(shù)值向量作為輸入，計(jì)算這些輸入的線性組合，如果結(jié)果大於某個(gè)閾值，就輸出1，否則輸出-1

其中每個(gè)wi是一個(gè)實(shí)數(shù)常量，或叫做權(quán)值，用來決定輸入xi對(duì)感知器輸出的貢獻(xiàn)率。特別地，-w0是閾值。2003.12.18104感知器（2）兩種簡化形式，附加一個(gè)常量輸入x0=1，前面的不等式寫成

或?qū)懗上蛄啃问?/p>

為了簡短起見，把感知器函數(shù)寫為 其中，2003.12.18105感知器（3）學(xué)習(xí)一個(gè)感知器意味著選擇權(quán)w0,…,wn的值。所以感知器學(xué)習(xí)要考慮的候選假設(shè)空間H就是所有可能的實(shí)數(shù)值權(quán)向量的集合

2003.12.18106感知器的表徵能力可以把感知器看作是n維實(shí)例空間（即點(diǎn)空間）中的超平面決策面對(duì)於超平面一側(cè)的實(shí)例，感知器輸出1，對(duì)於另一側(cè)的實(shí)例，輸出-1這個(gè)決策超平面方程是可以被某個(gè)超平面分割的樣例集合，稱為線性可分樣例集合2003.12.18107感知器的表徵能力（2）單獨(dú)的感知器可以用來表示很多布爾函數(shù)表示m-of-n函數(shù)感知器可以表示所有的原子布爾函數(shù)：與、或、與非、或非然而，一些布爾函數(shù)無法用單一的感知器表示，例如異或2003.12.18108感知器的表徵能力（3）因?yàn)樗械牟紶柡瘮?shù)都可表示為基於原子函數(shù)的互連單元的某個(gè)網(wǎng)路，因此感知器網(wǎng)路可以表示所有的布爾函數(shù)。事實(shí)上，只需要兩層深度的網(wǎng)路，比如表示析取範(fàn)式注意，要把一個(gè)AND感知器的輸入求反只要簡單地改變相應(yīng)輸入權(quán)的符號(hào)因?yàn)楦兄骶W(wǎng)路可以表示大量的函數(shù)，而單獨(dú)的單元不能做到這一點(diǎn)，所以我們感興趣的是學(xué)習(xí)感知器組成的多層網(wǎng)路2003.12.18109感知器訓(xùn)練法則雖然我們的目的是學(xué)習(xí)由多個(gè)單元互連的網(wǎng)路，但我們還是要從如何學(xué)習(xí)單個(gè)感知器的權(quán)值開始單個(gè)感知器的學(xué)習(xí)任務(wù)，決定一個(gè)權(quán)向量，它可以使感知器對(duì)於給定的訓(xùn)練樣例輸出正確的1或-1我們主要考慮兩種演算法感知器法則delta法則這兩種演算法保證收斂到可接受的假設(shè)，在不同的條件下收斂到的假設(shè)略有不同這兩種演算法提供了學(xué)習(xí)多個(gè)單元構(gòu)成的網(wǎng)路的基礎(chǔ)2003.12.18110感知器法則演算法過程從隨機(jī)的權(quán)值開始反復(fù)應(yīng)用這個(gè)感知器到每個(gè)訓(xùn)練樣例，只要它誤分類樣例就修改感知器的權(quán)值重複這個(gè)過程，直到感知器正確分類所有的訓(xùn)練樣例感知器訓(xùn)練法則

其中

2003.12.18111感知器法則（2）為什麼這個(gè)更新法則會(huì)成功收斂到正確的權(quán)值呢？一些例子可以證明（Minskey&Papert1969）如果訓(xùn)練樣例線性可分，並且使用了充分小的

否則，不能保證2003.12.18112梯度下降和delta法則delta法則克服感應(yīng)器法則的不足，線上性不可分的訓(xùn)練樣本上，收斂到目標(biāo)概念的最佳近似delta法則的關(guān)鍵思想是，使用梯度下降來搜索可能的權(quán)向量的假設(shè)空間，以找到最佳擬合訓(xùn)練樣例的權(quán)向量delta法則為反向傳播演算法提供了基礎(chǔ)，而反向傳播演算法能夠?qū)W習(xí)多個(gè)單元的互連網(wǎng)絡(luò)對(duì)於包含多種不同類型的連續(xù)參數(shù)化假設(shè)的假設(shè)空間，梯度下降是必須遍曆這樣的空間的所有演算法的基礎(chǔ)2003.12.18113梯度下降和delta法則（2）把delta訓(xùn)練法則理解為訓(xùn)練一個(gè)無閾值的感知器

指定一個(gè)度量標(biāo)準(zhǔn)來衡量假設(shè)相對(duì)於訓(xùn)練樣例的訓(xùn)練誤差

第6章給出了選擇這種E定義的一種貝葉斯論證，在一定條件下，使E最小化的假設(shè)就是H中最可能的假設(shè)2003.12.18114可視化假設(shè)空間圖4-4根據(jù)E的定義，誤差曲面是一個(gè)拋物面，存在一個(gè)單一全局最小值梯度下降搜索從一個(gè)任意的初始權(quán)向量開始，然後沿誤差曲面最陡峭下降的方向，以很小的步伐反復(fù)修改這個(gè)向量，直到得到全局的最小誤差點(diǎn)2003.12.18115梯度下降法則的推導(dǎo)如何發(fā)現(xiàn)沿誤差曲面最陡峭下降的方向？通過計(jì)算E相對(duì)向量的每個(gè)分量的導(dǎo)數(shù)，這個(gè)向量導(dǎo)數(shù)被稱為E對(duì)於的梯度，記作當(dāng)梯度被解釋為權(quán)空間的一個(gè)向量時(shí)，它確定了使E最陡峭上升的方向，所以這個(gè)向量的反方向給出了最陡峭下降的方向梯度訓(xùn)練法則

其中，

2003.12.18116梯度下降法則的推導(dǎo)（2）需要一個(gè)高效的方法在每一步都計(jì)算這個(gè)梯度

梯度下降權(quán)值更新法則

2003.12.18117梯度下降法則的推導(dǎo)（3）表4-1，訓(xùn)練線性單元的梯度下降演算法Gradient-Descent(training_examples,)training_examples中每個(gè)訓(xùn)練樣例形式為序偶<,t>，是輸入值向量，t是目標(biāo)輸出值，

是學(xué)習(xí)速率初始化每個(gè)wi為某個(gè)小的隨機(jī)值遇到終止條件之前，做以下操作初始化每個(gè)

wi為0對(duì)於訓(xùn)練樣例training_examples中的每個(gè)<,t>，做把實(shí)例輸入到此單元，計(jì)算輸出o對(duì)於線性單元的每個(gè)權(quán)增量

wi，做

wi

wi+(t-o)xi對(duì)於線性單元的每個(gè)權(quán)wi，做

wiwi+wi2003.12.18118梯度下降法則的推導(dǎo)（4）梯度下降演算法如下選取一個(gè)初始的隨機(jī)權(quán)向量應(yīng)用線性單元到所有的訓(xùn)練樣例，根據(jù)公式4.7計(jì)算每個(gè)權(quán)值的更新權(quán)值因?yàn)檎`差曲面僅包含一個(gè)全局的最小值，所以無論訓(xùn)練樣例是否線性可分，演算法都會(huì)收斂到具有最小誤差的權(quán)向量，條件是使用足夠小的學(xué)習(xí)速率演算法的一種常用改進(jìn)方法是隨著梯度下降步數(shù)的增加逐漸減小學(xué)習(xí)速率2003.12.18119梯度下降的隨機(jī)近似梯度下降是一種重要的通用學(xué)習(xí)範(fàn)型，它是搜索龐大假設(shè)空間或無限假設(shè)空間一種策略梯度下降應(yīng)用於滿足以下條件的任何情況假設(shè)空間包含連續(xù)參數(shù)化的假設(shè)誤差對(duì)於這些假設(shè)參數(shù)可微梯度下降的主要實(shí)踐問題有時(shí)收斂過程可能非常慢如果在誤差曲面上有多個(gè)局部極小值，那麼不能保證找到全局最小值2003.12.18120梯度下降的隨機(jī)近似（2）隨機(jī)梯度下降（或稱增量梯度下降）根據(jù)某個(gè)單獨(dú)樣例的誤差增量計(jì)算權(quán)值更新，得到近似的梯度下降搜索（隨機(jī)取一個(gè)樣例）對(duì)表4-1演算法的修改可以看作為每個(gè)單獨(dú)的訓(xùn)練樣例定義不同的誤差函數(shù)在迭代所有訓(xùn)練樣例時(shí)，這些權(quán)值更新的序列給出了對(duì)於原來誤差函數(shù)的梯度下降的一個(gè)合理近似通過使下降速率的值足夠小，可以使隨機(jī)梯度下降以任意程度接近於真實(shí)梯度下降2003.12.18121梯度下降的隨機(jī)近似（2）標(biāo)準(zhǔn)梯度下降和隨機(jī)梯度下降之間的關(guān)鍵區(qū)別標(biāo)準(zhǔn)梯度下降是在權(quán)值更新前對(duì)所有樣例匯總誤差，而隨機(jī)梯度下降的權(quán)值是通過考查每個(gè)訓(xùn)練樣例來更新的在標(biāo)準(zhǔn)梯度下降中，權(quán)值更新的每一步對(duì)多個(gè)樣例求和，需要更多的計(jì)算（？）標(biāo)準(zhǔn)梯度下降，由於使用真正的梯度，標(biāo)準(zhǔn)梯度下降對(duì)於每一次權(quán)值更新經(jīng)常使用比隨機(jī)梯度下降大的步長如果標(biāo)準(zhǔn)誤差曲面有多個(gè)局部極小值，隨機(jī)梯度下降有時(shí)可能避免陷入這些局部極小值中實(shí)踐中，標(biāo)準(zhǔn)和隨機(jī)梯度下降方法都被廣泛應(yīng)用2003.12.18122梯度下降的隨機(jī)近似（3）delta法則（增量法則），又稱LMS法則、Adaline法則、Windrow-Hoff法則公式4.10與4.4.2節(jié)的感知器法則的相似和區(qū)別delta法則可以學(xué)習(xí)非閾值線性單元的權(quán)，也可以用來訓(xùn)練有閾值的感知器單元。如果非閾值輸出能夠被訓(xùn)練到完美擬合這些值，那麼閾值輸出也會(huì)完美擬合它們即使不能完美地?cái)M合目標(biāo)值，只要線性單元的輸出具有正確的符號(hào)，閾值輸出就會(huì)正確擬合目標(biāo)值儘管這個(gè)過程會(huì)得到使線性單元輸出的誤差最小化的權(quán)值，但這些權(quán)值不能保證閾值輸出的誤差最小化（？）2003.12.18123感知器學(xué)習(xí)小結(jié)感知器法則和delta法則的關(guān)鍵差異前者根據(jù)閾值化的感知器輸出的誤差更新權(quán)值後者根據(jù)輸入的非閾值化線性組合的誤差來更新權(quán)值這個(gè)差異帶來不同的收斂特性前者經(jīng)過有限次的迭代收斂到一個(gè)能理想分類訓(xùn)練數(shù)據(jù)的假設(shè)，條件是訓(xùn)練樣例線性可分後者可能經(jīng)過極長的時(shí)間，漸近收斂到最小誤差假設(shè)，但無論訓(xùn)練樣例是否線性可分都會(huì)收斂2003.12.18124感知器學(xué)習(xí)小結(jié)（2）學(xué)習(xí)權(quán)向量的第3種方法是線性規(guī)劃線性規(guī)劃是解線性不等式方程組的一種通用的有效方法這種方法僅當(dāng)訓(xùn)練樣例線性可分時(shí)有解Duda和Hart給出了一種更巧妙的適合非線性可分的情況的方法更大的問題是，無法擴(kuò)展到訓(xùn)練多層網(wǎng)路，而delta法則可以很容易擴(kuò)展到多層網(wǎng)路2003.12.18125多層網(wǎng)路和反向傳播演算法多層網(wǎng)路能夠表示種類繁多的非線性曲面圖4-5描述了一個(gè)典型的多層網(wǎng)路和它的決策曲面2003.12.18126可微閾值單元使用什麼類型的單元來構(gòu)建多層網(wǎng)路？多個(gè)線性單元的連接仍產(chǎn)生線性函數(shù)，而我們希望構(gòu)建表徵非線性函數(shù)的網(wǎng)路感知器單元可以構(gòu)建非線性函數(shù)，但它的不連續(xù)閾值使它不可微，不適合梯度下降演算法我們需要的單元滿足的條件輸出是輸入的非線性函數(shù)輸出是輸入的可微函數(shù)Sigmoid單元，類似於感知器單元，但基於一個(gè)平滑的可微閾值函數(shù)2003.12.18127可微閾值單元（2）圖4-6sigmoid單元先計(jì)算它的輸入的線性組合，然後應(yīng)用到一個(gè)閾值上，閾值輸出是輸入的連續(xù)函數(shù)

其中

2003.12.18128可微閾值單元（3）sigmoid函數(shù)也稱logistic函數(shù)擠壓函數(shù)輸出範(fàn)圍是0到1單調(diào)遞增導(dǎo)數(shù)很容易用函數(shù)本身表示sigmoid函數(shù)的變型其他易計(jì)算導(dǎo)數(shù)的可微函數(shù)增加陡峭性雙曲正切函數(shù)2003.12.18129反向傳播演算法用來學(xué)習(xí)多層網(wǎng)路的權(quán)值採用梯度下降方法試圖最小化網(wǎng)路輸出值和目標(biāo)值之間的誤差平方網(wǎng)路的誤差定義公式，對(duì)所有網(wǎng)路輸出的誤差求和

2003.12.18130反向傳播演算法（2）反向傳播演算法面臨的學(xué)習(xí)任務(wù)搜索一個(gè)巨大的假設(shè)空間，這個(gè)空間由網(wǎng)路中所有的單元的所有可能的權(quán)值定義，得到類似圖4-4的誤差曲面在多層網(wǎng)路中，誤差曲面可能有多個(gè)局部極小值，梯度下降僅能保證收斂到局部極小值儘管有這個(gè)障礙，已經(jīng)發(fā)現(xiàn)對(duì)於實(shí)踐中很多應(yīng)用，反向傳播演算法都產(chǎn)生了出色的結(jié)果2003.12.18131反向傳播演算法（3）表4-2包含兩層sigmoid單元的前饋網(wǎng)路的反向傳播演算法BackPropagation(training_examples,,nin,nout,nhidden)training_examples是序偶<,>的集合，是網(wǎng)路輸入值向量，是目標(biāo)輸出值。

是學(xué)習(xí)速率，nin是網(wǎng)路輸入的數(shù)量，nhidden是隱藏層單元數(shù)，nout是輸出單元數(shù)，從單元i到單元j的輸入表示為xji，單元i到單元j的權(quán)值表示為wji。創(chuàng)建具有nin個(gè)輸入，nhidden個(gè)隱藏，nout個(gè)輸出單元的網(wǎng)路初始化所有的網(wǎng)路權(quán)值為小的隨機(jī)值在遇到終止條件前對(duì)於訓(xùn)練樣例training_examples中的每個(gè)<,>：把輸入沿網(wǎng)路前向傳播把實(shí)例輸入網(wǎng)路，並計(jì)算網(wǎng)路中每個(gè)單元u的輸出ou使誤差沿網(wǎng)路反向傳播對(duì)於網(wǎng)路的每個(gè)輸出單元k，計(jì)算它的誤差項(xiàng)

kok(1-ok)(tk-ok)對(duì)於網(wǎng)路的每個(gè)隱藏單元h，計(jì)算它的誤差項(xiàng)

hoh(1-oh)更新每個(gè)網(wǎng)路權(quán)值wjiwji+wji，其中wji=jxji2003.12.18132反向傳播演算法（4）表4-2給出的反向傳播演算法適用於包含兩層sigmoid單元的分層前饋網(wǎng)路，並且每一層的單元與前一層的所有單元相連。表4-2是反向傳播演算法的增量梯度下降（或隨機(jī)梯度下降）版本使用的符號(hào)做了如下擴(kuò)展網(wǎng)路中每個(gè)節(jié)點(diǎn)被賦予一個(gè)序號(hào)，這裏的節(jié)點(diǎn)要麼是網(wǎng)路的輸入，要麼是網(wǎng)路中某個(gè)單元的輸出xji表示節(jié)點(diǎn)i到單元j的輸入，wji表示對(duì)應(yīng)的權(quán)值

n表示與單元n相關(guān)聯(lián)的誤差項(xiàng)。2003.12.18133表4-2的演算法解釋從建立一個(gè)具有期望數(shù)量的隱藏單元和輸出單元的網(wǎng)路並初始化所有的網(wǎng)路的權(quán)值為小的亂數(shù)開始給定一個(gè)固定的網(wǎng)路結(jié)構(gòu)，演算法的主迴圈就對(duì)訓(xùn)練樣例進(jìn)行反復(fù)的迭代對(duì)於每一個(gè)訓(xùn)練樣例，它應(yīng)用目前的網(wǎng)路到這個(gè)樣例，計(jì)算出對(duì)這個(gè)樣例網(wǎng)路輸出的誤差，然後更新網(wǎng)路中所有的權(quán)值對(duì)這樣的梯度下降步驟進(jìn)行迭代，直到網(wǎng)路的性能達(dá)到可接受的精度為止2003.12.18134反向傳播演算法的梯度下降法則表4-2的梯度下降權(quán)更新法則與delta訓(xùn)練法則相似類似delta法則，依照以下三者來更新每一個(gè)權(quán)學(xué)習(xí)速率

該權(quán)值涉及的輸入值xji該單元的輸出誤差不同於delta法則的地方delta法則中的誤差項(xiàng)被替換成一個(gè)更複雜的誤差項(xiàng)

j2003.12.18135反向傳播演算法的誤差項(xiàng)輸出單元k的誤差項(xiàng)

k與delta法則中的(tk-ok)相似，但乘上了sigmoid擠壓函數(shù)的導(dǎo)數(shù)ok(1-ok)。隱藏單元h的誤差項(xiàng)因?yàn)橛?xùn)練樣例僅對(duì)網(wǎng)路的輸出提供了目標(biāo)值tk，所以缺少直接的目標(biāo)值來計(jì)算隱藏單元的誤差值採取以下的間接方法計(jì)算隱藏單元的誤差項(xiàng)：對(duì)受隱藏單元h影響的每一個(gè)單元的誤差

k進(jìn)行加權(quán)求和，每個(gè)誤差

k權(quán)值為wkh，wkh就是從隱藏單元h到輸出單元k的權(quán)值。這個(gè)權(quán)值刻畫了隱藏單元h對(duì)於輸出單元k的誤差應(yīng)負(fù)責(zé)的程度。2003.12.18136表4-2的演算法解釋（2）表4-2的演算法隨著每個(gè)訓(xùn)練樣例的出現(xiàn)而遞增地更新權(quán)，這一點(diǎn)與梯度下降的隨機(jī)近似演算法一致要取得誤差E的真實(shí)梯度，需要在修改權(quán)值之前對(duì)所有訓(xùn)練樣例的

jxji值求和在典型的應(yīng)用中，權(quán)值的更新迭代會(huì)被重複上千次有很多終止條件可以用來停止這個(gè)過程迭代的次數(shù)到了一個(gè)固定值時(shí)停止當(dāng)在訓(xùn)練樣例上的誤差降到某個(gè)閾值以下在分離的驗(yàn)證樣例集合上的誤差符合某個(gè)標(biāo)準(zhǔn)終止條件很重要，太少的迭代無法有效地降低誤差，太多的迭代會(huì)導(dǎo)致對(duì)訓(xùn)練數(shù)據(jù)的過度擬合2003.12.18137增加衝量項(xiàng)因?yàn)榉聪騻鞑パ菟惴ǖ膽?yīng)用如此廣泛，所以已經(jīng)開發(fā)出了很多反向傳播演算法的變體修改權(quán)值更新法則，使第n次迭代時(shí)的權(quán)值的更新部分地依賴於發(fā)生在第n-1次迭代時(shí)的更新，比如wji(n)=jxji+wji(n-1)右側(cè)第一項(xiàng)就是表4-2中的權(quán)值更新法則，第二項(xiàng)被稱為衝量項(xiàng)梯度下降的搜索軌跡就像一個(gè)球沿誤差曲面滾下，衝量使球從一次迭代到下一次迭代時(shí)以同樣的方向滾動(dòng)衝量有時(shí)會(huì)使這個(gè)球滾過誤差曲面的局部極小值或平坦區(qū)域衝量也具有在梯度不變的區(qū)域逐漸增大搜索步長的效果，從而加快收斂2003.12.18138學(xué)習(xí)任意的無環(huán)網(wǎng)路表4-2的演算法可以簡單地推廣到任意深度的前饋網(wǎng)路第m層的單元r的

r值由更深的第m+1層

值根據(jù)下式計(jì)算將這個(gè)演算法推廣到任何有向無環(huán)結(jié)構(gòu)也同樣簡單，而不論網(wǎng)路中的單元是否被排列在統(tǒng)一的層上，計(jì)算任意內(nèi)部單元的

的法則是：，Downstream(r)是在網(wǎng)路中單元r的直接下游單元的集合，即輸入中包括r的輸出的所有單元2003.12.18139反向傳播法則的推導(dǎo)隨機(jī)梯度下降演算法迭代處理訓(xùn)練樣例，每次處理一個(gè)，對(duì)於每個(gè)訓(xùn)練樣例d，利用關(guān)於這個(gè)樣例的誤差Ed的梯度修改權(quán)值2003.12.18140符號(hào)說明xji，單元j的第i個(gè)輸入wji，與xji相關(guān)聯(lián)的權(quán)值netj，單元j的輸入的加權(quán)和oj，單元j計(jì)算出的輸出tj，單元j的目標(biāo)輸出

，sigmoid函數(shù)outputs，網(wǎng)路最後一層的輸出單元的集合Downstream(j)，單元j的輸出到達(dá)的單元的集合2003.12.18141隨機(jī)梯度下降法則的推導(dǎo)，分情況討論的推導(dǎo)輸出單元2003.12.18142隨機(jī)梯度下降法則的推導(dǎo)（２）隱藏單元2003.12.18143收斂性和局部極小值對(duì)於多層網(wǎng)路，誤差曲面可能含有多個(gè)不同的局部極小值，梯度下降可能陷入這些局部極小值中的任何一個(gè)對(duì)於多層網(wǎng)路，反向傳播演算法僅能保證收斂到誤差E的某個(gè)局部極小值，不一定收斂到全局最小誤差儘管缺乏對(duì)收斂到全局最小誤差的保證，反向傳播演算法在實(shí)踐中仍是非常有效的函數(shù)逼近演算法2003.12.18144收斂性和局部極小值（２）網(wǎng)路的權(quán)越多，誤差曲面的維數(shù)越多，也就越可能為梯度下降提供更多的逃逸路線考慮隨著訓(xùn)練中迭代次數(shù)的增加網(wǎng)路權(quán)值的演化方式如果把網(wǎng)路的權(quán)值初始化為接近於0的值，那麼在早期的梯度下降步驟中，網(wǎng)路將表現(xiàn)為一個(gè)非常平滑的函數(shù)，近似為輸入的線性函數(shù)，這是因?yàn)閟igmoid函數(shù)本身在權(quán)值靠近0時(shí)接近線性僅當(dāng)權(quán)值增長一定時(shí)間後，它們才會(huì)到達(dá)可以表示高度非線性網(wǎng)路函數(shù)的程度，可以預(yù)期在這個(gè)能表示更複雜函數(shù)的權(quán)空間區(qū)域存在更多的局部極小值但是當(dāng)權(quán)到達(dá)這一點(diǎn)時(shí)，它們已經(jīng)足夠靠近全局最小值，即便它是這個(gè)區(qū)域的局部最小值也是可以接受的2003.12.18145收斂性和局部極小值（3）用來緩解局部極小值問題的啟發(fā)式規(guī)則為梯度更新法則加一個(gè)衝量，可以帶動(dòng)梯度下降過程，沖過狹窄的局部極小值（原則上，也可能沖過狹窄的全局最小值）使用隨機(jī)的梯度下降而不是真正的梯度下降。隨機(jī)近似對(duì)於每個(gè)訓(xùn)練樣例沿一個(gè)不同的誤差曲面有效下降，這些不同的誤差曲面通常有不同的局部極小值，這使得下降過程不太可能陷入一個(gè)局部極小值使用同樣的數(shù)據(jù)訓(xùn)練多個(gè)網(wǎng)路，但用不同的隨機(jī)權(quán)值初始化每個(gè)網(wǎng)路。如果不同的訓(xùn)練產(chǎn)生不同的局部極小值，那麼對(duì)分離的驗(yàn)證集合性能最好的那個(gè)網(wǎng)路將被選中，或者保留所有的網(wǎng)路，輸出是所有網(wǎng)路輸出的平均值2003.12.18146前饋網(wǎng)路的表徵能力布爾函數(shù)：任何布爾函數(shù)可以被具有兩層單元的網(wǎng)路準(zhǔn)確表示，儘管在最壞情況下所需隱藏單元的數(shù)量隨著網(wǎng)路輸入數(shù)量的增加成指數(shù)級(jí)增長?？紤]下麵的通用方案：對(duì)於每一個(gè)可能的輸入向量，創(chuàng)建不同的隱藏單元，並設(shè)置它的權(quán)值使當(dāng)且僅當(dāng)這個(gè)特定的向量輸入到網(wǎng)路時(shí)該單元被啟動(dòng)，這樣就產(chǎn)生了一個(gè)對(duì)於任意輸入僅有一個(gè)單元被啟動(dòng)的隱藏層，然後把輸出單元實(shí)現(xiàn)為一個(gè)僅由所希望的輸入模式啟動(dòng)的或門。2003.12.18147前饋網(wǎng)路的表徵能力（2）連續(xù)函數(shù)：每個(gè)有界的連續(xù)函數(shù)可以由一個(gè)兩層的網(wǎng)路以任意小的誤差逼近。這個(gè)結(jié)論適用於在隱藏層使用sigmoid單元、在輸出層使用（非閾值）線性單元的網(wǎng)路。所需的隱藏單元數(shù)量依賴於要逼近的函數(shù)。任意函數(shù)：任意函數(shù)可以被一個(gè)有三層單元的網(wǎng)路以任意精度逼近。兩個(gè)隱藏層使用sigmoid單元，輸出層使用線性單元，每層所需單元數(shù)不確定。證明方法：首先說明任意函數(shù)可以被許多局部化函數(shù)的線性組合逼近，這些局部化函數(shù)的值除了某個(gè)小範(fàn)圍外都為0；然後說明兩層的sigmoid單元足以產(chǎn)生良好的局部逼近注意：梯度下降從一個(gè)初始值開始，因此搜索範(fàn)圍裏的網(wǎng)路權(quán)向量可能不包含所有的權(quán)向量2003.12.18148假設(shè)空間搜索和歸納偏置反向傳播演算法的假設(shè)空間是n個(gè)網(wǎng)路權(quán)值形成的n維歐氏空間。這個(gè)空間是連續(xù)的，與決策樹學(xué)習(xí)和其他基於離散表示的方法的假設(shè)空間不同假設(shè)空間的連續(xù)性以及誤差E關(guān)於假設(shè)的連續(xù)參數(shù)可微，導(dǎo)致了一個(gè)定義良好的誤差梯度，為最佳假設(shè)的搜索提供了一個(gè)非常有用的結(jié)構(gòu)。精確地刻畫出反向傳播學(xué)習(xí)的歸納偏置是有難度的，它依賴於梯度下降搜索和權(quán)空間覆蓋可表徵函數(shù)空間的方式的相互作用性把這一偏置粗略地刻畫為在數(shù)據(jù)點(diǎn)之間平滑插值。如果給定兩個(gè)正例，它們之間沒有反例，反向傳播演算法會(huì)傾向於把這兩點(diǎn)之間的點(diǎn)也標(biāo)記為正例2003.12.18149隱藏層表示反向傳播演算法的一個(gè)迷人特性是：它能夠在網(wǎng)路內(nèi)部的隱藏層發(fā)現(xiàn)有用的中間表示訓(xùn)練樣例僅包含網(wǎng)路輸入和輸出，權(quán)值調(diào)節(jié)的過程可以自由地設(shè)置權(quán)值，來定義任何隱藏單元表示，這些隱藏單元表示在使誤差E達(dá)到最小時(shí)最有效。引導(dǎo)反向傳播演算法定義新的隱藏層特徵，這些特徵在輸入中沒有明確表示出來，但能捕捉輸入實(shí)例中與學(xué)習(xí)目標(biāo)函數(shù)最相關(guān)的特徵多層網(wǎng)路在隱藏層自動(dòng)發(fā)現(xiàn)有用表示的能力是ANN學(xué)習(xí)的一個(gè)關(guān)鍵特性。允許學(xué)習(xí)器創(chuàng)造出設(shè)計(jì)者沒有明確引入的特徵。網(wǎng)路中使用的單元層越多，就可以創(chuàng)造出越複雜的特徵2003.12.18150泛化、過度擬合和停止判據(jù)權(quán)值更新演算法的終止條件一種選擇是，對(duì)訓(xùn)練樣例的誤差降低至某個(gè)預(yù)先定義的閾值之下這不是一個(gè)好的策略，因?yàn)榉聪騻鞑パ菟惴ㄈ菀走^度擬合訓(xùn)練樣例，降低對(duì)於其他未見實(shí)例的泛化精度泛化精度：網(wǎng)路擬合訓(xùn)練數(shù)據(jù)外的實(shí)例的精度圖4-9，儘管在訓(xùn)練樣例上的誤差持續(xù)下降，但在驗(yàn)證樣例上測量到的誤差先下降，後上升。因?yàn)檫@些權(quán)值擬合了訓(xùn)練樣例的“特異性”，而這個(gè)特異性對(duì)於樣例的一般分佈沒有代表性。ANN中大量的權(quán)值參數(shù)為擬合這樣的“特異性”提供了很大的自由度2003.12.18151過度擬合為什麼過度擬合發(fā)生在迭代的後期，而不是早期？設(shè)想網(wǎng)路的權(quán)值是被初始化為小隨機(jī)值的，使用這些幾乎一樣的權(quán)值僅能描述非常平滑的決策面隨著訓(xùn)練的進(jìn)行，一些權(quán)值開始增長，以降低在訓(xùn)練數(shù)據(jù)上的誤差，同時(shí)學(xué)習(xí)到的決策面的複雜度也在增加如果權(quán)值調(diào)整迭代次數(shù)足夠多，反向傳播演算法可能會(huì)產(chǎn)生過度複雜的決策面，擬合了訓(xùn)練數(shù)據(jù)中的雜訊和訓(xùn)練樣例中沒有代表性的特徵2003.12.18152過度擬合解決方法權(quán)值衰減它在每次迭代過程中以某個(gè)小因數(shù)降低每個(gè)權(quán)值，這等效於修改E的定義，加入一個(gè)與網(wǎng)路權(quán)值的總量相應(yīng)的懲罰項(xiàng)，此方法的動(dòng)機(jī)是保持權(quán)值較小，從而使學(xué)習(xí)過程向著複雜決策面的反方向偏置驗(yàn)證數(shù)據(jù)一個(gè)最成功的方法是在訓(xùn)練數(shù)據(jù)外再為演算法提供一套驗(yàn)證數(shù)據(jù)，應(yīng)該使用在驗(yàn)證集合上產(chǎn)生最小誤差的迭代次數(shù)，不是總能明顯地確定驗(yàn)證集合何時(shí)達(dá)到最小誤差2003.12.18153過度擬合解決方法（2）一般而言，過度擬合是一個(gè)棘手的問題交叉驗(yàn)證方法在可獲得額外的數(shù)據(jù)提供驗(yàn)證集合時(shí)工作得很好，但是小訓(xùn)練集合的過度擬合問題更為嚴(yán)重k-fold交叉方法把訓(xùn)練樣例分成k份，然後進(jìn)行k次交叉驗(yàn)證過程，每次使用不同的一份作為驗(yàn)證集合，其餘k-1份合併作為訓(xùn)練集合。每個(gè)樣例會(huì)在一次實(shí)驗(yàn)中被用作驗(yàn)證樣例，在k-1次實(shí)驗(yàn)中被用作訓(xùn)練樣例每次實(shí)驗(yàn)中，使用上面討論的交叉驗(yàn)證過程來決定在驗(yàn)證集合上取得最佳性能的迭代次數(shù)，然後計(jì)算這些迭代次數(shù)的均值最後，運(yùn)行一次反向傳播演算法，訓(xùn)練所有m個(gè)實(shí)例並迭代次2003.12.18154舉例：人臉識(shí)別訓(xùn)練樣例20個(gè)不同人的攝影圖像每個(gè)人大約32張圖像不同的表情快樂、沮