機器學(xué)習(xí)2概念學(xué)習(xí)優(yōu)秀公開課件

1機器學(xué)習(xí)

—概念學(xué)習(xí)

2歸納學(xué)習(xí)概念概念學(xué)習(xí)定義作為搜索的概念學(xué)習(xí)（搜索策略：偏序）Find-S：尋找極大特殊假設(shè)變形空間和候選消除算法歸納偏置OUTLINE3歸納學(xué)習(xí)也可以稱作歸納推理或簡稱歸納，其任務(wù)是：給定函數(shù)f(未知)的實例集合，返回一個近似于f的函數(shù)h——h稱為假設(shè)，所有h的集合稱為假設(shè)空間一個好的假設(shè)應(yīng)該能夠預(yù)測未見過的實例——這就是基本的歸納問題問題實例——用一個單變量函數(shù)(近似目標(biāo)函數(shù))來擬合若干數(shù)據(jù)點，選擇最高次數(shù)為k的多項式集合作為假設(shè)h的集合，即假設(shè)空間H歸納學(xué)習(xí)5上圖中顯示了擬合兩兩一組數(shù)據(jù)的不同函數(shù)—與所有數(shù)據(jù)一致的函數(shù)稱為一致假設(shè)如何在多個一致假設(shè)之間進行選擇？答案—奧卡姆剃刀原則(Ockham’srazor)—優(yōu)先選擇與數(shù)據(jù)一致的最簡單假設(shè)原因—比數(shù)據(jù)本身更復(fù)雜的假設(shè)不能從數(shù)據(jù)中提取任何模式此外，對于非確定性函數(shù)，在假設(shè)的復(fù)雜度和數(shù)據(jù)擬合度之間進行折中不可避免Ockham剃刀原則6歸納學(xué)習(xí)概念概念學(xué)習(xí)定義作為搜索的概念學(xué)習(xí)（搜索策略：偏序）Find-S：尋找極大特殊假設(shè)變形空間和候選消除算法歸納偏置OUTLINE7概念學(xué)習(xí)給定某一類別的若干正例和反例，從中獲得該類別的一般定義。搜索的觀點在預(yù)定義的假設(shè)空間中搜索假設(shè)，使其與訓(xùn)練樣例有最佳的擬合。利用假設(shè)空間的偏序結(jié)構(gòu)算法收斂到正確假設(shè)的條件概念學(xué)習(xí)9例子–enjoysport目標(biāo)概念，Aldo進行水上運動的日子，表示為布爾函數(shù)EnjoySport任務(wù)目的，基于某天的各屬性，預(yù)測EnjoySport的值一個樣例集，每個樣例表示為屬性的集合No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes表2-1目標(biāo)概念EnjoySport的訓(xùn)練樣例10基本概念實例x

:每一個實例使用若干屬性表示，相應(yīng)屬性值構(gòu)成一個實例No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport11基本概念實例集X

:概念定義在一個實例集合之上，這個集合表示為X

No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport13基本概念訓(xùn)練樣例d:每個樣例為X中的一個實例x以及他的目標(biāo)概念值c(x)。表示為序偶<x,c(x)>

注意：EnjoySport=yes時c(x)=1 EnjoySport=no時c(x)=0No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport14基本概念正例:c(x)=1的實例被稱為正例反例:c(x)=0的實例被稱為反例No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport15基本概念訓(xùn)練樣例集D:訓(xùn)練樣例的集合No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport17例子–enjoysport基本概念假設(shè)h:

<Sunny,Warm,?,Strong,?,?>No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes明確指定的屬性值任意本屬性可接受的值不接受任何值:18例子–enjoysport基本概念假設(shè)集合H:所有可能假設(shè)的集合No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes19例子–enjoysport已知:實例集–X假設(shè)集–H目標(biāo)概念–c:X{0,1}訓(xùn)練樣例–D求解（學(xué)習(xí)目標(biāo)）:H中的一假設(shè)h，使對于X中任意x，h(x)=c(x)

21歸納學(xué)習(xí)概念概念學(xué)習(xí)定義作為搜索的概念學(xué)習(xí)（搜索策略：偏序）Find-S：尋找極大特殊假設(shè)變形空間和候選消除算法歸納偏置OUTLINE22作為搜索的概念學(xué)習(xí)概念學(xué)習(xí):可以看作一個在假設(shè)空間上搜索的過程學(xué)習(xí):訓(xùn)練樣例假設(shè)空間選取假設(shè)的表示所隱含定義的整個空間目標(biāo)：能夠最好地擬合訓(xùn)練樣例的假設(shè)23作為搜索的概念學(xué)習(xí)當(dāng)假設(shè)的表示形式選定后，那么就隱含地為學(xué)習(xí)算法確定了所有假設(shè)的空間E.g.EnjoySport的實例空間:

3X2X2X2X2X2=96假設(shè)空間H中語法不同的假設(shè):5X4X4X4X4X4=5120假設(shè)空間H中語義不同的假設(shè)：（去掉“空”）4X3X3X3X3X3+1=9733+?+SkyAirTempHumidityWindWaterForecastEnjoySport32222225搜索策略假設(shè)空間中徹底詳盡的搜索需要一個策略（順序）Why?如何對假設(shè)排序?線性排序偏序26假設(shè)的一般到特殊序假設(shè)的一般到特殊序關(guān)系考慮下面兩個假設(shè)h1=<sunny,?,?,Strong,?,?>h2=<Sunny,?,?,?,?,?>任何被h1劃分為正例的實例都會被h2劃分為正例，因此h2比h1更一般。利用這個關(guān)系，無需列舉所有假設(shè)，就能在無限的假設(shè)空間中進行徹底的搜索29歸納學(xué)習(xí)概念概念學(xué)習(xí)定義作為搜索的概念學(xué)習(xí)（搜索策略：偏序）Find-S：尋找極大特殊假設(shè)變形空間和候選消除算法歸納偏置OUTLINE30Find-s：尋找極大特殊假設(shè)算法使用more_general_than偏序的搜索算法從H中最特殊假設(shè)開始，然后在假設(shè)覆蓋正例失敗時將其一般化Specifichypothesis31Find-s算法Find-S算法將h初始化為H中最特殊假設(shè)對每個正例x對h的每個屬性約束ai

如果x滿足ai

那么不做任何處理否則將h中ai替換為x滿足的下一個更一般 約束輸出假設(shè)h32Find-s中的假設(shè)空間搜索x1=<sunny,warm,normal,strong,warm,same>,+x2=<sunny,warm,high,strong,warm,same>,+x3=<rainy,cold,high,strong,warm,change>,-x4=<sunny,warm,high,strong,cool,change>,+實例X假設(shè)集Hx1x2h0h1h2,3h0=<,,,,,>h1=<sunny,warm,normal,strong,warm,same>h2=<sunny,warm,?,strong,warm,same>h3=<sunny,warm,?,strong,warm,same>h4=<sunny,warm,?,strong,?,?>特殊一般x3h4x433Find-s的特點Find-S算法演示了一種利用more_general_than偏序來搜索假設(shè)空間的方法，沿著偏序鏈，從較特殊的假設(shè)逐漸轉(zhuǎn)移到較一般的假設(shè)。因此，每一步得到的假設(shè)都是在那一點上與訓(xùn)練樣例一致的最特殊的假設(shè)。Find-S的重要特點：對以屬性約束的合取式描述的假設(shè)空間H，保證輸出為H中與正例一致的最特殊的假設(shè)。34Find-s存在問題存在的問題是否收斂到了正確的目標(biāo)概念？Find-s找到了與訓(xùn)練樣例一致的假設(shè)，但無法確定它是否找到了唯一合適的假設(shè)（即目標(biāo)概念本身）?；蛘哒f是否還有其它的假設(shè)為什么要用最特殊的假設(shè)？如果有多個與D一致的假設(shè)，它只找到最特殊的假設(shè)訓(xùn)練樣例是否相互一致？D中出現(xiàn)錯誤將嚴(yán)重破壞Find-s算法如果有多個極大特殊假設(shè)怎么辦？35歸納學(xué)習(xí)概念概念學(xué)習(xí)定義作為搜索的概念學(xué)習(xí)（搜索策略：偏序）Find-S：尋找極大特殊假設(shè)變形空間和候選消除算法歸納偏置OUTLINE36變形空間和候選消除算法候選消除算法概述概念學(xué)習(xí)的另一種方法，候選消除算法（candidate-elimination）Find-S算法的不足，輸出的假設(shè)只是H中能夠擬合訓(xùn)練樣例的多個假設(shè)中的一個候選消除算法輸出與訓(xùn)練樣例一致的所有假設(shè)的集合候選消除算法在描述這一集合時不需要明確列舉所有成員，利用more_general_than偏序結(jié)構(gòu)，可以維護一個一致假設(shè)集合的簡潔表示37變形空間和候選消除算法候選消除算法的應(yīng)用，化學(xué)質(zhì)譜分析、啟發(fā)式搜索的控制規(guī)則候選消除算法的缺點，容錯性能差38變形空間和候選消除算法輸出與訓(xùn)練樣例一致的所有假設(shè)的集合“一致”的定義一個假設(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)39變形空間和候選消除算法變形空間VSH,D關(guān)于H和D的變型空間，記為VSH,D，是假設(shè)空間H中與訓(xùn)練樣例D一致的所有假設(shè)構(gòu)成的子集VSH,D

{h

H|Consistent(h,D)}versionspaceSG40變形空間示例{<Sunny,Warm,?,Strong,?,?>}S:{<Sunny,?,?,?,?,?>,<?,Warm,?,?,?,?>}G:<Sunny,?,?,Strong,?,?><Sunny,Warm,?,?,?,?><?,Warm,?,Strong,?,?>41列表后消除算法列表后消除算法：表示變型空間的一種方法是列出其所有成員算法：變型空間VSH,D

包含H中所有假設(shè)的列表對每個訓(xùn)練樣例<x,c(x)>從變型空間中移除所有h(x)c(x)的假設(shè)輸出VSH,D中的假設(shè)列表42列表后消除算法優(yōu)點保證得到所有與訓(xùn)練數(shù)據(jù)一致的假設(shè)缺點非常繁瑣地列出H中的所有假設(shè)，大多數(shù)實際的假設(shè)空間無法做到43候選消除算法變型空間的更簡潔表示變型空間被表示為它的極大一般和極大特殊的成員這些成員形成了一般和特殊邊界的集合，這些邊界在整個偏序結(jié)構(gòu)中劃分出變型空間。關(guān)于假設(shè)空間H和訓(xùn)練數(shù)據(jù)D的一般邊界G，是在H中與D相一致的極大一般成員的集合關(guān)于假設(shè)空間H和訓(xùn)練數(shù)據(jù)D的特殊邊界S，是在H中與D相一致的極大特殊成員的集合44候選消除算法——算法描述初始化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è)更特殊45候選消除算法——示例極大一般極大特殊{<sunny,warm,normal,strong,warm,same>}正例{<sunny,warm,high,strong,warm,same>}正例s1G1s2{<sunny,warm,?,strong,warm,same>}G2{<rainy,cold,high,strong,warm,change>}反例specific46候選消除算法——示例極大一般極大特殊{<sunny,warm,normal,strong,warm,same>}正例{<sunny,warm,high,strong,warm,same>}正例s1G1s2{<sunny,warm,?,strong,warm,same>}G2{<rainy,cold,high,strong,warm,change>}反例specific47極大一般極大特殊{<sunny,warm,normal,strong,warm,same>}正例{<sunny,warm,high,strong,warm,same>}正例s1G1s2,s3{<sunny,warm,?,strong,warm,same>}G2G3{<sunny,?,?,?,?,?><?,warm,?,?,?,?><?,?,?,?,?,same>}{<sunny,warm,high,strong,cool,change>}正例候選消除算法——示例48極大一般極大特殊{<sunny,warm,normal,strong,warm,same>}正例{<sunny,warm,high,strong,warm,same>}正例s1G1s2,s3{<sunny,warm,?,strong,warm,same>}G2G4{<sunny,warm,?,strong,?,?>}S4候選消除算法——示例{<sunny,?,?,?,?,?><?,warm,?,?,?,?>}正例49S

邊界覆蓋了正例相關(guān)的信息，因此正例不需要保留G

邊界覆蓋了反例相關(guān)的信息，因此反例不需要保留訓(xùn)練樣例使用順序不會影響算法結(jié)果（變形空間），但會影響算法效率正例使S邊界一般化，反例使G邊界特殊化.如果S和G覆蓋同樣的假設(shè)，則假設(shè)空間中只有一個與訓(xùn)練數(shù)據(jù)一致的假設(shè).如果S和G

變?yōu)榭?二者有一個為空，另一個必為空)，那么假設(shè)空間中沒有與訓(xùn)練數(shù)據(jù)一致的假設(shè).候選消除算法特點50練習(xí)考慮積木世界的以下屬性和屬性值：顏色={黃色，藍色，綠色}；形狀={圓錐形，球形，長方形}；硬度={硬，軟}

尺寸={大，小}訓(xùn)練樣例如下（“+”表示正例，“-”表示反例）

(黃色，圓錐形，軟，大，+)(藍色，長方形，軟，小，-)(黃色，球形，軟，小，+)(黃色，圓錐形，硬，大，+)(黃色，長方形，軟，大，+)(綠色，球形，硬，大，-)

(藍色，圓錐形，軟，大，-)問題：采用變形空間法，學(xué)習(xí)概念：黃色積木51變型空間和候選消除算法的說明(1)候選消除算法收斂到正確的假設(shè)，當(dāng)且僅當(dāng)訓(xùn)練樣例中沒有錯誤H中確實包含描述目標(biāo)概念的正確假設(shè)如果樣例中存在錯誤如果給定足夠的訓(xùn)練數(shù)據(jù)，我們會發(fā)現(xiàn)S和G邊界收斂得到一個空的變型空間如果目標(biāo)概念不能由假設(shè)表示方式所描述相似情況出現(xiàn)52變型空間和候選消除算法的說明(2)下一步需要什么樣的訓(xùn)練樣例一般來說，概念學(xué)習(xí)的最優(yōu)查詢策略，是產(chǎn)生實例以滿足當(dāng)前變型空間中大約半數(shù)的假設(shè)。這樣，變型空間的大小可以在遇到每個新樣例時減半，正確的目標(biāo)概念就可在只用log2|VS|次實驗后得到。53變型空間和候選消除算法的說明(3)怎樣使用不完全學(xué)習(xí)概念若變型空間中仍包含多個假設(shè)，即目標(biāo)概念還未學(xué)習(xí)到，但是仍然有可能對新樣例進行一定可信度的分類。54示例——對未見實例分類{<Sunny,Warm,?,Strong,?,?>}S:{<Sunny,?,?,?,?,?>,<?,Warm,?,?,?,?>}G:<Sunny,?,?,Strong,?,?><Sunny,Warm,?,?,?,?><?,Warm,?,Strong,?,?><SunnyWarmNormalStrongCoolChange>6+----------------------------------------------------------------<SunnyWarmNormalLightWarmSame>3+3-----------------------------------------------------------------<SunnyColdNormalStrongWarmSame>2+4-55歸納學(xué)習(xí)概念概念學(xué)習(xí)定義作為搜索的概念學(xué)習(xí)（搜索策略：偏序）Find-S：尋找極大特殊假設(shè)變形空間和候選消除算法歸納偏置OUTLINE56歸納偏置有關(guān)候選消除算法的幾個問題如果目標(biāo)概念不在假設(shè)空間中怎么辦？是否可設(shè)計一個包含所有假設(shè)的空間來解決這一困難？假設(shè)空間的大小對于算法推廣到未見實例的能力有什么影響？假設(shè)空間的大小對所需訓(xùn)練樣例的數(shù)量有什么影響？57歸納偏置一個有偏的假設(shè)空間在EnjoySport這個例子中，假設(shè)空間限制為只包含屬性值的合取。（有偏）這一限制，導(dǎo)致假設(shè)空間不能夠表示最簡單的析取形式的目標(biāo)概念。例如下面實例No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmHighStrongWarmSameYes2CloudyWarmHighStrongWarmSameYes3RainyWarmHighStrongWarmSameNo從1、2得<？WarmHighStrongWarmSame>與樣例一致的最特殊的假設(shè)，它仍然過于一般化了58歸納偏置無偏的學(xué)習(xí)器為了保證目標(biāo)概念在假設(shè)空間中，需要提供一個假設(shè)空間，它能表達所有的可教授概念。換言之，它能表達實例集X的所有子集。