機(jī)器學(xué)習(xí)課件1第一頁，共四十一頁，編輯于2023年，星期六提綱概念學(xué)習(xí)給定某一類別的若干正例和反例，從中獲得該類別的一般定義搜索的觀點在預(yù)定義的假設(shè)空間中搜索假設(shè)，使其與訓(xùn)練樣例有最佳的擬合利用假設(shè)空間的偏序結(jié)構(gòu)算法收斂到正確假設(shè)的條件歸納學(xué)習(xí)的本質(zhì)，從訓(xùn)練數(shù)據(jù)中泛化的理由第二頁，共四十一頁，編輯于2023年，星期六簡介許多機(jī)器學(xué)習(xí)涉及到從特殊訓(xùn)練樣例中得到一般概念。概念，可被看作一個對象或事件集合，它是從更大的集合中選取的子集，或在這個較大集合中定義的布爾函數(shù)。概念學(xué)習(xí)問題的定義問題：給定一個樣例集合以及每個樣例是否屬于某個概念的標(biāo)注，怎樣推斷出該概念的一般定義。又稱從樣例中逼近布爾函數(shù)定義：概念學(xué)習(xí)是指從有關(guān)某個布爾函數(shù)的輸入輸出訓(xùn)練樣例中推斷出該布爾函數(shù)第三頁，共四十一頁，編輯于2023年，星期六概念學(xué)習(xí)任務(wù)一個例子目標(biāo)概念，Aldo進(jìn)行水上運動的日子，表示為布爾函數(shù)EnjoySport任務(wù)目的，基于某天的各屬性，預(yù)測EnjoySport的值一個樣例集，每個樣例表示為屬性的集合第四頁，共四十一頁，編輯于2023年，星期六概念學(xué)習(xí)任務(wù)（2）YesChangeCoolStrongHighWarmSunny4NoChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample表2-1目標(biāo)概念EnjoySport的訓(xùn)練樣例候選消除法變型空間例一般到特殊Find_S第五頁，共四十一頁，編輯于2023年，星期六概念學(xué)習(xí)任務(wù)（3）表示假設(shè)的形式一個簡單的形式，實例的各屬性約束(變量)的合取式令每個假設(shè)為6個約束(變量)的向量，每個約束(變量)對應(yīng)一個屬性可取值范圍，為？任意本屬性可接受的值明確指定的屬性值不接受任何值假設(shè)的例子<?,Cold,High,?,?,?><?,?,?,?,?,?> //所有的樣例都是正例<,,,,,> //所有的樣例都是反例第六頁，共四十一頁，編輯于2023年，星期六EnjoySport概念學(xué)習(xí)任務(wù)

已知實例集X每個實例x由6個屬性描述，每個屬性的取值范圍已確定假設(shè)集H每個假設(shè)h描述為6個屬性的取值約束的合取目標(biāo)概念c一個布爾函數(shù)，變量為實例訓(xùn)練樣例集D目標(biāo)函數(shù)（或目標(biāo)概念）的正例和反例求解H中的一假設(shè)h，使對于X中任意x，h(x)=c(x)第七頁，共四十一頁，編輯于2023年，星期六術(shù)語定義實例x和實例集X概念和目標(biāo)概念c訓(xùn)練樣例x和訓(xùn)練樣例集D正例，目標(biāo)概念成員反例，非目標(biāo)概念成員假設(shè)h和假設(shè)集H機(jī)器學(xué)習(xí)的目標(biāo)就是尋找一個假設(shè)h，使得對所有的h，都有h(x)=c(x)第八頁，共四十一頁，編輯于2023年，星期六歸納學(xué)習(xí)假設(shè)什么是歸納學(xué)習(xí)？從特殊的樣例得到普遍的規(guī)律歸納只能保證輸出的假設(shè)能與訓(xùn)練樣例相擬合歸納假設(shè)的一個基本假定對于未見實例最好的假設(shè)就是與訓(xùn)練數(shù)據(jù)最佳擬合的假設(shè)歸納學(xué)習(xí)假設(shè)任一假設(shè)如果在足夠大的訓(xùn)練樣例集中很好地逼近目標(biāo)函數(shù)，它也能在未見實例中很好地逼近目標(biāo)函數(shù)第九頁，共四十一頁，編輯于2023年，星期六作為搜索的概念學(xué)習(xí)概念學(xué)習(xí)可以看作一個搜索的過程搜索范圍：假設(shè)的表示所隱含定義的整個空間搜索目標(biāo)：能夠最好地擬合訓(xùn)練樣例的假設(shè)當(dāng)假設(shè)的表示形式選定后，那么就隱含地為學(xué)習(xí)算法確定了所有假設(shè)的空間例子EnjoySport的假設(shè)空間第十頁，共四十一頁，編輯于2023年，星期六假設(shè)的一般到特殊序假設(shè)的一般到特殊序關(guān)系考慮下面兩個假設(shè)h1=<sunny,?,?,Strong,?,?>h2=<Sunny,?,?,?,?,?>任何被h1劃分為正例的實例都會被h2劃分為正例，因此h2比h1更一般利用這個關(guān)系，無需列舉所有假設(shè)，就能在無限的假設(shè)空間中進(jìn)行徹底的搜索第十一頁，共四十一頁，編輯于2023年，星期六假設(shè)的一般到特殊序（2）關(guān)系“更一般”的精確定義任給實例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

ghk第十二頁，共四十一頁，編輯于2023年，星期六假設(shè)的一般到特殊序（3）“更一般”的嚴(yán)格情形hj>ghk，當(dāng)且僅當(dāng)，“更特殊”關(guān)系的定義hj

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

ghj以EnjoySport為例說明上面的定義偏序的特點（區(qū)別于全序），全序上的搜索可以是二分法，偏序的搜索比無序簡單，比全序復(fù)雜。這個偏序關(guān)系的定義與目標(biāo)概念無關(guān)第十三頁，共四十一頁，編輯于2023年，星期六Find-S：尋找極大特殊假設(shè)使用more_general_than偏序的搜索算法從H中最特殊假設(shè)開始，然后在假設(shè)覆蓋正例失敗時將其一般化表2-3Find-S算法將h初始化為H中最特殊假設(shè)對每個正例x對h的每個屬性約束ai如果x滿足ai那么不做任何處理否則將h中ai替換為x滿足的另一個更一般約束輸出假設(shè)h第十四頁，共四十一頁，編輯于2023年，星期六Find-S：尋找極大特殊假設(shè)(2)Find-S算法在例子EnjoySport上的應(yīng)用h<,,,,,>h<Sunny,Warm,Normal,Strong,Warm,Same>h<Sunny,Warm,?,Strong,Warm,Same>遇到反例，h不變（因為h已經(jīng)能夠正確地識別反例）h<Sunny,Warm,?,Strong,?,?>訓(xùn)練樣本第十五頁，共四十一頁，編輯于2023年，星期六Find-S：尋找極大特殊假設(shè)(3)Find-S算法沿著偏序鏈搜索，每一步得到的假設(shè)都是在那一點上與訓(xùn)練樣例一致的最特殊的假設(shè)Find-S的重要特點對以屬性約束的合取式描述的假設(shè)空間H，保證輸出為H中與正例一致的最特殊的假設(shè)存在的問題是否收斂到了正確的目標(biāo)概念？為什么要用最特殊的假設(shè)？訓(xùn)練樣例是否相互一致？如果有多個極大特殊假設(shè)怎么辦？第十六頁，共四十一頁，編輯于2023年，星期六變型空間和候選消除算法候選消除算法（candidate-elimination）Find-S算法的不足：輸出的假設(shè)只是H中能夠擬合訓(xùn)練樣例的多個假設(shè)中的一個候選消除算法輸出與訓(xùn)練樣例一致的所有假設(shè)的集合候選消除算法在描述這一集合時不需要明確列舉所有成員候選消除算法的應(yīng)用，化學(xué)質(zhì)譜分析、啟發(fā)式搜索的控制規(guī)則候選消除算法的缺點，容錯性能差第十七頁，共四十一頁，編輯于2023年，星期六變型空間和候選消除算法（2）“一致”的定義一個假設(shè)h與訓(xùn)練樣例集合D一致，當(dāng)且僅當(dāng)對D中每一個樣例<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)}第十八頁，共四十一頁，編輯于2023年，星期六變型空間和候選消除算法（3）列表后消除(Listtheneliminate)算法表示變型空間的一種方法是列出其所有成員變型空間包含H中所有假設(shè)的列表對每個訓(xùn)練樣例<x,c(x)>，從變型空間中移除所有h(x)c(x)的假設(shè)輸出VersionSpace中的假設(shè)列表優(yōu)點保證得到所有與訓(xùn)練數(shù)據(jù)一致的假設(shè)缺點非常繁瑣地列出H中的所有假設(shè)，大多數(shù)實際的假設(shè)空間無法做到第十九頁，共四十一頁，編輯于2023年，星期六變型空間和候選消除算法（4）變型空間的更簡潔表示變型空間被表示為它的極大一般和極大特殊的成員這些成員形成了一般和特殊邊界的集合，這些邊界在整個偏序結(jié)構(gòu)中劃分出變型空間以EnjoySport為例第二十頁，共四十一頁，編輯于2023年，星期六變型空間和候選消除算法（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相一致的極大特殊成員的集合第二十一頁，共四十一頁，編輯于2023年，星期六變型空間和候選消除算法（6）變型空間表示定理：令X為一任意的實例集合，H為X上定義的布爾假設(shè)的集合。令c:X{0,1}為X上定義的任一目標(biāo)概念，并令D為任一訓(xùn)練樣例集合{<x,c(x)>}。對所有的X,H,c,D以及良好定義的S和G：

VSH,D={hH|(sS)(gG)(gghgs)}第二十二頁，共四十一頁，編輯于2023年，星期六候選消除算法初始化G和S如果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中每個與d不一致的假設(shè)g從G中移去g把g的所有的極小特殊化式h加入到G中，其中h滿足h與d一致，而且S的某個成員比h更特殊從G中移去所有這樣的假設(shè)：它比G中另一個假設(shè)更特殊第二十三頁，共四十一頁，編輯于2023年，星期六變型空間和候選消除算法（8）算法舉例（EnjoySport）初始邊界集合S0和G0訓(xùn)練樣本變型空間例第二十四頁，共四十一頁，編輯于2023年，星期六變型空間和候選消除的說明候選消除算法收斂到正確的假設(shè)訓(xùn)練樣例中沒有錯誤H中確實包含描述目標(biāo)概念的正確假設(shè)如果樣例中存在錯誤如果給定足夠的訓(xùn)練數(shù)據(jù)，我們會發(fā)現(xiàn)S和G邊界收斂得到一個空的變型空間如果目標(biāo)概念不能由假設(shè)表示方式所描述相似情況出現(xiàn)第二十五頁，共四十一頁，編輯于2023年，星期六變型空間和候選消除（2）下一步需要什么樣的訓(xùn)練樣例一般來說，概念學(xué)習(xí)的最優(yōu)查詢策略，是產(chǎn)生實例以滿足當(dāng)前變型空間中大約半數(shù)的假設(shè)。這樣，變型空間的大小可以在遇到每個新樣例時減半，正確的目標(biāo)概念就可在只用log2|VS|次實驗后得到查詢實例<sunny,warm,Normal,Light,Warm,Same>變型空間例第二十六頁，共四十一頁，編輯于2023年，星期六變型空間和候選消除（3）怎樣使用不完全學(xué)習(xí)概念雖然圖2-3的變型空間中仍包含多個假設(shè)，即目標(biāo)概念還未學(xué)習(xí)到，但是仍然有可能對新樣例進(jìn)行一定可信度的分類表2-6的例子第二十七頁，共四十一頁，編輯于2023年，星期六表2-6的例子?SameWarmStrongNormalColdSunnyD?SameWarmLightNormalWarmSunnyC?SameWarmLightNormalColdRainyB?ChangeCoolStrongNormalWarmSunnyAEnjoySportForecastWaterWindHumidityAirTempSkyExample表2-6待分新實例變型空間例第二十八頁，共四十一頁，編輯于2023年，星期六歸納偏置有關(guān)候選消除算法的幾個問題如果目標(biāo)概念不在假設(shè)空間中怎么辦？是否可設(shè)計一個包含所有假設(shè)的空間來解決這一困難？假設(shè)空間的大小對于算法推廣到未見實例的能力有什么影響？假設(shè)空間的大小對所需訓(xùn)練樣例的數(shù)量有什么影響？無偏學(xué)習(xí)第二十九頁，共四十一頁，編輯于2023年，星期六歸納偏置（2）一個有偏的假設(shè)空間在EnjoySport這個例子中，假設(shè)空間限制為只包含屬性值的合取。（有偏）這一限制，導(dǎo)致假設(shè)空間不能夠表示最簡單的析取形式的目標(biāo)概念。NoChangeCoolStrongNormalWarmRainy3YesChangeCoolStrongNormalWarmCloudy2YesChangeCoolStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample第三十頁，共四十一頁，編輯于2023年，星期六歸納偏置（3）無偏的學(xué)習(xí)器為了保證目標(biāo)概念在假設(shè)空間中，需要提供一個假設(shè)空間，它能表達(dá)所有的可教授概念（everyteachableconcept）;換言之，它能表達(dá)實例集X的所有子集。冪集：2|X|問題：為什么2.3節(jié)中合取假設(shè)空間只能表示973個假設(shè)？第三十一頁，共四十一頁，編輯于2023年，星期六歸納偏置（4）EnjoySport的無偏形式帶來的問題：概念學(xué)習(xí)算法無法從訓(xùn)練樣例中泛化。要想獲得單個目標(biāo)概念，就必須提供X中所有實例作為訓(xùn)練樣例使用2.6.3節(jié)討論的部分學(xué)習(xí)的無效偏置問題第三十二頁，共四十一頁，編輯于2023年，星期六歸納偏置（5）無偏學(xué)習(xí)的無用性歸納學(xué)習(xí)的一個基本屬性：學(xué)習(xí)器如果不對目標(biāo)概念的形式做預(yù)先的假定，它從根本上無法對未見實例進(jìn)行分類歸納學(xué)習(xí)需要的預(yù)先假定，稱為歸納偏置（inductivebias）第三十三頁，共四十一頁，編輯于2023年，星期六歸納偏置的精確定義

L的歸納偏置定義為前提集合B，使所有的新實例滿足：定義：考慮對于實例集合X的概念學(xué)習(xí)算法L。令c為X上定義的任一概念，并令Dc為c的任意訓(xùn)練樣例集合，表示經(jīng)過Dc訓(xùn)練后L賦予實例xi的分類。L的歸納偏置是最小斷言集合B，它使任意目標(biāo)概念c和相應(yīng)的訓(xùn)練樣例Dc滿足：第三十四頁，共四十一頁，編輯于2023年，星期六歸納偏置（6）候選消除算法的歸納偏置{cH}3個有偏程度不同的歸納學(xué)習(xí)算法機(jī)械式候選消除算法Find-S歸納偏置結(jié)論：有偏性越強(qiáng)，它的歸納能力越強(qiáng)類別假定，對假設(shè)排序隱含在學(xué)習(xí)機(jī)中第三十五頁，共四十一頁，編輯于2023年，星期六小結(jié)概念學(xué)習(xí)可看作在預(yù)定義假設(shè)空間的搜索過程假設(shè)的一般到特殊偏序結(jié)構(gòu)可以定義在任何概念學(xué)習(xí)問題中，這種結(jié)構(gòu)便于假設(shè)空間的搜索Find-S算法使用一般到特殊序，在