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

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

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

ghk2003.12.1835假設的一般到特殊序（3）“更一般”的嚴格情形hj>ghk，當且僅當，(hj

ghk)

(hk

ghj)“更特殊”關系的定義hj

ghk，當且僅當，hk

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

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

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

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

VSH,D={h

H|(

s

S)(

g

G)(g

gh

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

xi)

L(xi,Dc)需要在Dc

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

(B

Dc

xi)

L(xi,Dc)考慮對于實例集合X的概念學習算法L。令c為X上定義的任一概念，并令Dc為c的任意訓練樣例集合，L(xi,Dc)表示經過Dc訓練后L賦予實例xi的分類。L的歸納偏置是最小斷言集合B，它使任意目標概念c和相應的訓練樣例Dc滿足：

xi

X[(B

Dc

xi)

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

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

Attributes中分類examples能力最好的屬性root的決策屬性A對于A的每個可能值vi在root下加一個新的分支對應測試A=vi令Examplesvi為Examples中滿足A屬性值為vi的子集如果Examplesvi為空在這個新分支下加一個葉子節點，節點的label=Examples中最普遍的Target_attribute值否則在新分支下加一個子樹ID3（Examplesvi,Target_attribute,Attributes-{A}）結束返回root2003.11.1865最佳分類屬性信息增益用來衡量給定的屬性區分訓練樣例的能力ID3算法在增長樹的每一步使用信息增益從候選屬性中選擇屬性用熵度量樣例的均一性熵刻畫了任意樣例集的純度給定包含關于某個目標概念的正反樣例的樣例集S，那么S相對這個布爾型分類的熵為

Entropy(S)=-p+log2p+-p-log2p-信息論中對熵的一種解釋，熵確定了要編碼集合S中任意成員的分類所需要的最少二進制位數更一般地，如果目標屬性具有c個不同的值，那么S相對于c個狀態的分類的熵定義為

Entropy(S)=2003.11.1866最佳分類屬性（2）用信息增益度量期望的熵降低屬性的信息增益，由于使用這個屬性分割樣例而導致的期望熵降低

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

H，如果存在其他的假設h’

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

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

SplitInformation(S,A)= GainRatio(S,A)=分裂信息項阻礙選擇值為均勻分布的屬性問題，當某個Si

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

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

或寫成向量形式

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

2003.12.18106感知器的表征能力可以把感知器看作是n維實例空間（即點空間）中的超平面決策面對于超平面一側的實例，感知器輸出1，對于另一側的實例，輸出-1這個決策超平面方程是可以被某個超平面分割的樣例集合，稱為線性可分樣例集合2003.12.18107感知器的表征能力（2）單獨的感知器可以用來表示很多布爾函數表示m-of-n函數感知器可以表示所有的原子布爾函數：與、或、與非、或非然而，一些布爾函數無法用單一的感知器表示，例如異或2003.12.18108感知器的表征能力（3）因為所有的布爾函數都可表示為基于原子函數的互連單元的某個網絡，因此感知器網絡可以表示所有的布爾函數。事實上，只需要兩層深度的網絡，比如表示析取范式注意，要把一個AND感知器的輸入求反只要簡單地改變相應輸入權的符號因為感知器網絡可以表示大量的函數，而單獨的單元不能做到這一點，所以我們感興趣的是學習感知器組成的多層網絡2003.12.18109感知器訓練法則雖然我們的目的是學習由多個單元互連的網絡，但我們還是要從如何學習單個感知器的權值開始單個感知器的學習任務，決定一個權向量，它可以使感知器對于給定的訓練樣例輸出正確的1或-1我們主要考慮兩種算法感知器法則delta法則這兩種算法保證收斂到可接受的假設，在不同的條件下收斂到的假設略有不同這兩種算法提供了學習多個單元構成的網絡的基礎2003.12.18110感知器法則算法過程從隨機的權值開始反復應用這個感知器到每個訓練樣例，只要它誤分類樣例就修改感知器的權值重復這個過程，直到感知器正確分類所有的訓練樣例感知器訓練法則

其中

2003.12.18111感知器法則（2）為什么這個更新法則會成功收斂到正確的權值呢？一些例子可以證明（Minskey&Papert1969）如果訓練樣例線性可分，并且使用了充分小的

否則，不能保證2003.12.18112梯度下降和delta法則delta法則克服感應器法則的不足，在線性不可分的訓練樣本上，收斂到目標概念的最佳近似delta法則的關鍵思想是，使用梯度下降來搜索可能的權向量的假設空間，以找到最佳擬合訓練樣例的權向量delta法則為反向傳播算法提供了基礎，而反向傳播算法能夠學習多個單元的互連網絡對于包含多種不同類型的連續參數化假設的假設空間，梯度下降是必須遍歷這樣的空間的所有算法的基礎2003.12.18113梯度下降和delta法則（2）把delta訓練法則理解為訓練一個無閾值的感知器

指定一個度量標準來衡量假設相對于訓練樣例的訓練誤差

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

其中，

2003.12.18116梯度下降法則的推導（2）需要一個高效的方法在每一步都計算這個梯度

梯度下降權值更新法則

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

是學習速率初始化每個wi為某個小的隨機值遇到終止條件之前，做以下操作初始化每個

wi為0對于訓練樣例training_examples中的每個<,t>，做把實例輸入到此單元，計算輸出o對于線性單元的每個權增量

wi，做

wi

wi+(t-o)xi對于線性單元的每個權wi，做

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

其中

2003.12.18128可微閾值單元（3）sigmoid函數也稱logistic函數擠壓函數輸出范圍是0到1單調遞增導數很容易用函數本身表示sigmoid函數的變型其他易計算導數的可微函數增加陡峭性雙曲正切函數2003.12.18129反向傳播算法用來學習多層網絡的權值采用梯度下降方法試圖最小化網絡輸出值和目標值之間的誤差平方網絡的誤差定義公式，對所有網絡輸出的誤差求和

2003.12.18130反向傳播算法（2）反向傳播算法面臨的學習任務搜索一個巨大的假設空間，這個空間由網絡中所有的單元的所有可能的權值定義，得到類似圖4-4的誤差曲面在多層網絡中，誤差曲面可能有多個局部極小值，梯度下降僅能保證收斂到局部極小值盡管有這個障礙，已經發現對于實踐中很多應用，反向傳播算法都產生了出色的結果2003.12.18131反向傳播算法（3）表4-2包含兩層sigmoid單元的前饋網絡的反向傳播算法BackPropagation(training_examples,,nin,nout,nhidden)training_examples是序偶<,>的集合，是網絡輸入值向量，是目標輸出值。

是學習速率，nin是網絡輸入的數量，nhidden是隱藏層單元數，nout是輸出單元數，從單元i到單元j的輸入表示為xji，單元i到單元j的權值表示為wji。創建具有nin個輸入，nhidden個隱藏，nout個輸出單元的網絡初始化所有的網絡權值為小的隨機值在遇到終止條件前對于訓練樣例training_examples中的每個<,>：把輸入沿網絡前向傳播把實例輸入網絡，并計算網絡中每個單元u的輸出ou使誤差沿網絡反向傳播對于網絡的每個輸出單元k，計算它的誤差項

kok(1-ok)(tk-ok)對于網絡的每個隱藏單元h，計算它的誤差項

hoh(1-oh)更新每個網絡權值wjiwji+wji，其中wji=jxji2003.12.18132反向傳播算法（4）表4-2給出的反向傳播算法適用于包含兩層sigmoid單元的分層前饋網絡，并且每一層的單元與前一層的所有單元相連。表4-2是反向傳播算法的增量梯度下降（或隨機梯度下降）版本使用的符號做了如下擴展網絡中每個節點被賦予一個序號，這里的節點要么是網絡的輸入，要么是網絡中某個單元的輸出xji表示節點i到單元j的輸入，wji表示對應的權值

n表示與單元n相關聯的誤差項。2003.12.18133表4-2的算法解釋從建立一個具有期望數量的隱藏單元和輸出單元的網絡并初始化所有的網絡的權值為小的隨機數開始給定一個固定的網絡結構，算法的主循環就對訓練樣例進行反復的迭代對于每一個訓練樣例，它應用目前的網絡到這個樣例，計算出對這個樣例網絡輸出的誤差，然后更新網絡中所有的權值對這樣的梯度下降步驟進行迭代，直到網絡的性能達到可接受的精度為止2003.12.18134反向傳播算法的梯度下降法則表4-2的梯度下降權更新法則與delta訓練法則相似類似delta法則，依照以下三者來更新每一個權學習速率

該權值涉及的輸入值xji該單元的輸出誤差不同于delta法則的地方delta法則中的誤差項被替換成一個更復雜的誤差項

j2003.12.18135反向傳播算法的誤差項輸出單元k的誤差項

k與delta法則中的(tk-ok)相似，但乘上了sigmoid擠壓函數的導數ok(1-ok)。隱藏單元h的誤差項因為訓練樣例僅對網絡的輸出提供了目標值tk，所以缺少直接的目標值來計算隱藏單元的誤差值采取以下的間接方法計算隱藏單元的誤差項：對受隱藏單元h影響的每一個單元的誤差

k進行加權求和，每個誤差

k權值為wkh，wkh就是從隱藏單元h到輸出單元k的權值。這個權值刻畫了隱藏單元h對于輸出單元k的誤差應負責的程度。2003.12.18136表4-2的算法解釋（2）表4-2的算法隨著每個訓練樣例的出現而遞增地更新權，這一點與梯度下降的隨機近似算法一致要取得誤差E的真實梯度，需要在修改權值之前對所有訓練樣例的

jxji值求和在典型的應用中，權值的更新迭代會被重復上千次有很多終止條件可以用來停止這個過程迭代的次數到了一個固定值時停止當在訓練樣例上的誤差降到某個閾值以下在分離的驗證樣例集合上的誤差符合某個標準終止條件很重要，太少的迭代無法有效地降低誤差，太多的迭代會導致對訓練數據的過度擬合2003.12.18137增加沖量項因為反向傳播算法的應用如此廣泛，所以已經開發出了很多反向傳播算法的變體修改權值更新法則，使第n次迭代時的權值的更新部分地依賴于發生在第n-1次迭代時的更新，比如wji(n)=jxji+wji(n-1)右側第一項就是表4-2中的權值更新法則，第二項被稱為沖量項梯度下降的搜索軌跡就像一個球沿誤差曲面滾下，沖量使球從一次迭代到下一次迭代時以同樣的方向滾動沖量有時會使這個球滾過誤差曲面的局部極小值或平坦區域沖量也具有在梯度不變的區域逐漸增大搜索步長的效果，從而加快收斂2003.12.18138學習任意的無環網絡表4-2的算法可以簡單地推廣到任意深度的前饋網絡第m層的單元r的

r值由更深的第m+1層

值根據下式計算將這個算法推廣到任何有向無環結構也同樣簡單，而不論網絡中的單元是否被排列在統一的層上，計算任意內部單元的

的法則是：，Downstream(r)是在網絡中單元r的直接下游單元的集合，即輸入中包括r的輸出的所有單元2003.12.18139反向傳播法則的推導隨機梯度下降算法迭代處理訓練樣例，每次處理一個，對于每個訓練樣例d，利用關于這個樣例的誤差Ed的梯度修改權值2003.12.18140符號說明xji，單元j的第i個輸入wji，與xji相關聯的權值netj，單元j的輸入的加權和oj，單元j計算出的輸出tj，單元j的目標輸出

，sigmoid函數outputs，網絡最后一層的輸出單元的集合Downstream(j)，單元j的輸出到達的單元的集合2003.12.18141隨機梯度下降法則的推導，分情況討論的推導輸出單元2003.12.18142隨機梯度下降法則的推導（２）隱藏單元2003.12.18143收斂性和局部極小值對于多層網絡，誤差曲面可能含有多個不同的局部極小值，梯度下降可能陷入這些局部極小值中的任何一個對于多層網絡，反向傳播算法僅能保證收斂到誤差E的某個局部極小值，不一定收斂到全局最小誤差盡管缺乏對收斂到全局最小誤差的保證，反向傳播算法在實踐中仍是非常有效的函數逼近算法2003.12.18144收斂性和局部極小值（２）網絡的權越多，誤差曲面的維數越多，也就越可能為梯度下降提供更多的逃逸路線考慮隨著訓練中迭代次數的增加網絡權值的演化方式如果把網絡的權值初始化為接近于0的值，那么在早期的梯度下降步驟中，網絡將表現為一個非常平滑的函數，近似為輸入的線性函數，這是因為sigmoid函數本身在權值靠近0時接近線性僅當權值增長一定時間后，它們才會到達可以表示高度非線性網絡函數的程度，可以預期在這個能表示更復雜函數的權空間區域存在更多的局部極小值但是當權到達這一點時，它們已經足夠靠近全局最小值，即便它是這個區域的局部最小值也是可以接受的2003.12.18145收斂性和局部極小值（3）用來緩解局部極小值問題的啟發式規則為梯度更新法則加一個沖量，可以帶動梯度下降過程，沖過狹窄的局部極小值（原則上，也可能沖過狹窄的全局最小值）使用隨機的梯度下降而不是真正的梯度下降。隨機近似對于每個訓練樣例沿一個不同的誤差曲面有效下降，這些不同的誤差曲面通常有不同的局部極小值，這使得下降過程不太可能陷入一個局部極小值使用同樣的數據訓練多個網絡，但用不同的隨機權值初始化每個網絡。如果不同的訓練產生不同的局部極小值，那么對分離的驗證集合性能最好的那個網絡將被選中，或者保留所有的網絡，輸出是所有網絡輸出的平均值2003.12.18146前饋網絡的表征能力布爾函數：任何布爾函數可以被具有兩層單元的網絡準確表示，盡管在最壞情況下所需隱藏單元的數量隨著網絡輸入數量的增加成指數級增長。考慮下面的通用方案：對于每一個可能的輸入向量，創建不同的隱藏單元，并設置它的權值使當且僅當這個特定的向量輸入到網絡時該單元被激活，這樣就產生了一個對于任意輸入僅有一個單元被激活的隱藏層，然后把輸出單元實現為一個僅由所希望的輸入模式激活的或門。2003.12.18147前饋網絡的表征能力（2）連續函數：每個有界的連續函數可以由一個兩層的網絡以任意小的誤差逼近。這個結論適用于在隱藏層使用sigmoid單元、在輸出層使用（非閾值）線性單元的網絡。所需的隱藏單元數量依賴于要逼近的函數。任意函數：任意函數可以被一個有三層單元的網絡以任意精度逼近。兩個隱藏層使用sigmoid單元，輸出層使用線性單元，每層所需單元數不確定。證明方法：首先說明任意函數可以被許多局部化函數的線性組合逼近，這些局部化函數的值除了某個小范圍外都為0；然后說明兩層的sigmoid單元足以產生良好的局部逼近注意：梯度下降從一個初始值開始，因此搜索范圍里的網絡權向量可能不包含所有的權向量2003.12.18148假設空間搜索和歸納偏置反向傳播算法的假設空間是n個網絡權值形成的n維歐氏空間。這個空間是連續的，與決策樹學習和其他基于離散表示的方法的假設空間不同假設空間的連續性以及誤差E關于假設的連續參數可微，導致了一個定義良好的誤差梯度，為最佳假設的搜索提供了一個非常有用的結構。精確地刻畫出反向傳播學習的歸納偏置是有難度的，它依賴于梯度下降搜索和權空間覆蓋可表征函數空間的方式的相互作用性把這一偏置粗略地刻畫為在數據點之間平滑插值。如果給定兩個正例，它們之間沒有反例，反向傳播算法會傾向于把這兩點之間的點也標記為正例2003.12.18149隱藏層表示反向傳播算法的一個迷人特性是：它能夠在網絡內部的隱藏層發現有用的中間表示訓練樣例僅包含網絡輸入和輸出，權值調節的過程可以自由地設置權值，來定義任何隱藏單元表示，這些隱藏單元表示在使誤差E達到最小時最有效。引導反向傳播算法定義新的隱藏層特征，這些特征在輸入中沒有明確表示出來，但能捕捉輸入實例中與學習目標函數最相關的特征多層網絡在隱藏層自動發現有用表示的能力是ANN學習的一個關鍵特性。允許學習器創造出設計者沒有明確引入的特征。網絡中使用的單元層越多，就可以創造出越復雜的特征2003.12.18150泛化、過度擬合和停止判據權值更新算法的終止條件一種選擇是，對訓練樣例的誤差降低至某個預先定義的閾值之下這不是一個好的策略，因為反向傳播算法容易過度擬合訓練樣例，降低對于其他未見實例的泛化精度泛化精度：網絡擬合訓練數據外的實例的精度圖4-9，盡管在訓練樣例上的誤差持續下降，但在驗證樣例上測量到的誤差先下降，后上升。因為這些權值擬合了訓練樣例的“特異性”，而這個特異性對于樣例的一般分布沒有代表性。ANN中大量的權值參數為擬合這樣的“特異性”提供了很大的自由度2003.12.18151過度擬合為什么過度擬合發生在迭代的后期，而不是早期？設想網絡的權值是被初始化為小隨機值的，使用這些幾乎一樣的權值僅能描述非常平滑的決策面隨著訓練的進行，一些權值開始增長，以降低在訓練數據上的誤差，同時學習到的決策面的復雜度也在增加如果權值調整迭代次數足夠多，反向傳播算法可能會產生過度復雜的決策面，擬合了訓練數據中的噪聲和訓練樣例中沒有代表性的特征2003.12.18152過度擬合解決方法權值衰減它在每次迭代過程中以某個小因子降低每個權值，這等效于修改E的定義，加入一個與網絡權值的總量相應的懲罰項，此方法的動機是保持權值較小，從而使學習過程向著復雜決策面的反方向偏置驗證數據一個最成功的方法是在訓練數據外再為算法提供一套驗證數據，應該使用在驗證集合上產生最小誤差的迭代次數，不是總能明顯地確定驗證集合何時達到最小誤差2003.12.18153過度擬合解決方法（2）一般而言，過度擬合是一個棘手的問題交叉驗證方法在可獲得額外的數據提供驗證集合時工作得很好，但是小訓練集合的過度擬合問題更為嚴重k-fold交叉方法把訓練樣例分成k份，然后進行k次交叉驗證過程，每次使用不同的一份作為驗證集合，其余k-1份合并作為訓練集合。每個樣例會在一次實驗中被用作驗證樣例，在k-1次實驗中被用作訓練樣例每次實驗中，使用上面討論的交叉驗證過程來決定在驗證集合上取得最佳性能的迭代次數，然后計算這些迭代次數的均值最后，運行一次反向傳播算法，訓練所有m個實例并迭代次2003.12.18154舉例：人臉識別訓練樣例20個不同人的攝影圖像每個人大約32張圖像不同的表情快樂、沮喪、憤怒、中性不同的方向左、右、正前、上不同的穿戴是否帶眼鏡共624幅灰度圖像分辨率為120x128，每個像素使用0（黑）到255（白）的灰度值描述任務：學習圖像中人臉的朝向2003.12.18155人臉識別——設計