1機器學習

—概念學習

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

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

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

No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport13基本概念訓練樣例d:每個樣例為X中的一個實例x以及他的目標概念值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基本概念訓練樣例集D:訓練樣例的集合No.SkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes例子–enjoysport17例子–enjoysport基本概念假設h:

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

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

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

如果x滿足ai

那么不做任何處理否則將h中ai替換為x滿足的下一個更一般 約束輸出假設h32Find-s中的假設空間搜索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假設集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偏序來搜索假設空間的方法，沿著偏序鏈，從較特殊的假設逐漸轉移到較一般的假設。因此，每一步得到的假設都是在那一點上與訓練樣例一致的最特殊的假設。Find-S的重要特點：對以屬性約束的合取式描述的假設空間H，保證輸出為H中與正例一致的最特殊的假設。34Find-s存在問題存在的問題是否收斂到了正確的目標概念？Find-s找到了與訓練樣例一致的假設，但無法確定它是否找到了唯一合適的假設（即目標概念本身）。或者說是否還有其它的假設為什么要用最特殊的假設？如果有多個與D一致的假設，它只找到最特殊的假設訓練樣例是否相互一致？D中出現(xiàn)錯誤將嚴重破壞Find-s算法如果有多個極大特殊假設怎么辦？35歸納學習概念概念學習定義作為搜索的概念學習（搜索策略：偏序）Find-S：尋找極大特殊假設變形空間和候選消除算法歸納偏置OUTLINE36變形空間和候選消除算法候選消除算法概述概念學習的另一種方法，候選消除算法（candidate-elimination）Find-S算法的不足，輸出的假設只是H中能夠擬合訓練樣例的多個假設中的一個候選消除算法輸出與訓練樣例一致的所有假設的集合候選消除算法在描述這一集合時不需要明確列舉所有成員，利用more_general_than偏序結構，可以維護一個一致假設集合的簡潔表示37變形空間和候選消除算法候選消除算法的應用，化學質譜分析、啟發(fā)式搜索的控制規(guī)則候選消除算法的缺點，容錯性能差38變形空間和候選消除算法輸出與訓練樣例一致的所有假設的集合“一致”的定義一個假設h與訓練樣例集合D一致，當且僅當對D中每一個樣例<x,c(x)>都有h(x)=c(x)，即Consistent(h,D)(<x,c(x)>D)h(x)=c(x)39變形空間和候選消除算法變形空間VSH,D關于H和D的變型空間，記為VSH,D，是假設空間H中與訓練樣例D一致的所有假設構成的子集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中所有假設的列表對每個訓練樣例<x,c(x)>從變型空間中移除所有h(x)c(x)的假設輸出VSH,D中的假設列表42列表后消除算法優(yōu)點保證得到所有與訓練數(shù)據(jù)一致的假設缺點非常繁瑣地列出H中的所有假設，大多數(shù)實際的假設空間無法做到43候選消除算法變型空間的更簡潔表示變型空間被表示為它的極大一般和極大特殊的成員這些成員形成了一般和特殊邊界的集合，這些邊界在整個偏序結構中劃分出變型空間。關于假設空間H和訓練數(shù)據(jù)D的一般邊界G，是在H中與D相一致的極大一般成員的集合關于假設空間H和訓練數(shù)據(jù)D的特殊邊界S，是在H中與D相一致的極大特殊成員的集合44候選消除算法——算法描述初始化G和S如果d是一個正例從G中移去所有與d不一致的假設對S中每個與d不一致的假設s從S中移去s把s的所有的極小泛化式h加入到S中，其中h滿足h與d一致，而且G的某個成員比h更一般從S中移去所有這樣的假設：它比S中另一個假設更一般如果d是一個反例從S中移去所有與d不一致的假設對G中每個與d不一致的假設g從G中移去g把g的所有的極小特殊化式h加入到G中，其中h滿足h與d一致，而且S的某個成員比h更特殊從G中移去所有這樣的假設：它比G中另一個假設更特殊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

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

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

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

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

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

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