概念學(xué)習(xí)完整版本

概念學(xué)習(xí)和一般到特殊序

ConceptLearningAndTheGeneral-To-SpecificOrdering

---主要內(nèi)容歸納學(xué)習(xí)概念學(xué)習(xí)定義及其符號(hào)化歸納學(xué)習(xí)假設(shè)假設(shè)的一般到特殊序FIND-S：尋找極大特殊假設(shè)主要內(nèi)容變型空間（VersionSpace）候選刪除學(xué)習(xí)算法

Candidate-EliminationAlgorithm歸納偏置

InductiveBias總結(jié)機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí)致力于研究建立能夠根據(jù)經(jīng)驗(yàn)自我提高處理性能的計(jì)算機(jī)程序。機(jī)器學(xué)習(xí)的中心問(wèn)題:從特殊的訓(xùn)練樣例中歸納出一般函數(shù)。歸納學(xué)習(xí)：從給定訓(xùn)練樣例中歸納出一般函數(shù)的學(xué)習(xí)方法歸納學(xué)習(xí)歸納學(xué)習(xí)根據(jù)有無(wú)教師指導(dǎo)，可分為：示例學(xué)習(xí)（有導(dǎo)師學(xué)習(xí)）觀察與發(fā)現(xiàn)學(xué)習(xí)（無(wú)導(dǎo)師學(xué)習(xí)）概念學(xué)習(xí)：屬于一種有導(dǎo)師的歸納學(xué)習(xí)方法。概念學(xué)習(xí)定義及其符號(hào)化什么叫做概念（Concept）？論域

“紅點(diǎn)”“綠點(diǎn)”概念：某個(gè)大的集合中選取的子集。（如從動(dòng)物集合中選取鳥(niǎo)類）或者是在這個(gè)大的集合（論域）中定義的布爾函數(shù)。概念學(xué)習(xí)定義及其符號(hào)化什么叫做概念學(xué)習(xí)（ConceptLearning）？問(wèn)題：

給定一樣例集合以及每個(gè)樣例是否屬于某一概念的標(biāo)注，怎樣自動(dòng)推斷出概念的一般定義。你能給出“鳥(niǎo)類”的一般定義嗎？麻雀、燕子、烏鴉......概念學(xué)習(xí)：從有關(guān)某個(gè)布爾函數(shù)的輸入輸出訓(xùn)練樣例中推斷出該布爾函數(shù)。概念學(xué)習(xí)舉例目標(biāo)概念：Aldo進(jìn)行水上運(yùn)動(dòng)的日子ExampleSkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes任務(wù)目的：基于某天的各屬性，以預(yù)測(cè)出該天EnjoySport的值。訓(xùn)練樣例：<x,c(x)>,正例，反例，訓(xùn)練集D術(shù)語(yǔ)定義ExampleSkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2RainyColdHighStrongWarmChangeNo實(shí)例(Instance)x、實(shí)例集(InstanceSpace)X目標(biāo)概念c：定義在實(shí)例集X上的布爾函數(shù)c:X{0,1}Sunny,Cloudy,RainyStrong,Weak3*2^5=96個(gè)c(x)=1c(x)=0H={h|h:X{0,1}}假設(shè)空間,假設(shè)h機(jī)器學(xué)習(xí)的目標(biāo)：

尋找一假設(shè)h,使的對(duì)于X中所有的x，都有h(x)=c(x).概念學(xué)習(xí)舉例假設(shè)采取什么樣的形式呢？<value1,value2,value3,value4,value5,value6><Sky,AirTemp,Humidity,Wind,Water,Forecast>’?’表示任意本屬性可接受的值明確指定的屬性值(如Warm)‘’表示不接受任何值<?,Cold,High,?,?,?><?,?,?,?,?,?><,,,,,>Aldo只在寒冷和潮濕的日子里進(jìn)行水上運(yùn)動(dòng)每一天都是正例每一天都是反例概念學(xué)習(xí)舉例EnjoySport概念學(xué)習(xí)的任務(wù)---學(xué)習(xí)使EnjoySport=yes的日子---屬性約束的合取式EnjoySport學(xué)習(xí)的輸出任意概念學(xué)習(xí)任務(wù)的表示---實(shí)例的集合、實(shí)例集合上的目標(biāo)函數(shù)、候選假設(shè)的集合以及訓(xùn)練樣例的集合。概念學(xué)習(xí)的圖示XcD通過(guò)訓(xùn)練集D學(xué)習(xí)得到的h能保證在整個(gè)實(shí)例集合X上與目標(biāo)概念c有相同的輸出嗎？歸納學(xué)習(xí)的假設(shè)歸納學(xué)習(xí)算法最多只能保證輸出的假設(shè)能與訓(xùn)練樣例相擬合。歸納學(xué)習(xí)假設(shè)任一假設(shè)如果在足夠大的訓(xùn)練樣例集合中很好地逼近目標(biāo)函數(shù)，它也能在未見(jiàn)實(shí)例中很好地逼近目標(biāo)函數(shù)。作為搜索的概念學(xué)習(xí)EnjoySport概念學(xué)習(xí)學(xué)習(xí)任務(wù)：從H中尋找一h，使得對(duì)于X中的所有x，有

h(x)=c(x).H有多少個(gè)假設(shè)構(gòu)成呢？5*4*4*4*4*4=5120個(gè)1+4*3*3*3*3*3=973個(gè)出現(xiàn)“不接受任何值”的情況？多數(shù)實(shí)際的學(xué)習(xí)任務(wù)包含更大的、有時(shí)是無(wú)限大的假設(shè)空間。對(duì)假設(shè)空間進(jìn)行搜索的策略假設(shè)的一般到特殊序假設(shè)的一般到特殊序關(guān)系h1=<Sunny,?,?,Strong,?,?>h2=<Sunny,?,?,?,?,?>任何被h1劃分為正例的實(shí)例都會(huì)被h2劃分為正例。被h1和h2劃分為正例的實(shí)例個(gè)數(shù)有什么關(guān)系呢？結(jié)論：h2比h1更一般假設(shè)的一般到特殊序定義:x滿足h的含義

令hj和hk為在X上定義的布爾函數(shù)。稱hjmore_general_than_or_equal_tohk

，當(dāng)且僅當(dāng)h(x)=1假設(shè)的一般到特殊序hj嚴(yán)格地比hk更一般hk比hj更特殊假設(shè)的一般到特殊序圖例實(shí)例集X假設(shè)集HH1=<Sunny,?,?,Strong,?,?>H2=<Sunny,?,?,?,?,?>H3=<Sunny,?,?,?,Cool,?>x1=<Sunny,Warm,High,Strong,Cool,Same>x2=<Sunny,Warm,High,Light,Warm,Same>x1x2h1h3h2特殊一般假設(shè)的一般到特殊序假設(shè)空間H上的一個(gè)偏序“比…更一般”關(guān)系滿足自反、反對(duì)稱和傳遞。如何利用該偏序結(jié)構(gòu)有效地搜索假設(shè)空間如：FIND-S算法

CANDIDATE-ELIMINATION算法FIND-S:尋找極大特殊假設(shè)FIND-S算法1.將h初始化為H中最特殊假設(shè)2.對(duì)每個(gè)正例x對(duì)h的每個(gè)屬性約束ai如果x滿足ai,那么不做任何處理否則將h中ai替換為x滿足的另一個(gè)更一般約束3.輸出假設(shè)hFIND-S算法舉例ExampleSkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYes1.h

<,,,,,>2.h<Sunny,Warm,Normal,Strong,Warm,Same>3.h<Sunny,Warm,?,Strong,Warm,Same>4.h<Sunny,Warm,?,Strong,Warm,Same>5.h<Sunny,Warm,?,Strong,?,?>為什么忽略反例？假設(shè)：假設(shè)空間H包含目標(biāo)概念c

訓(xùn)練樣例不包含錯(cuò)誤

當(dāng)且假設(shè)h是H中與所觀察到正例相一致的最特殊的假設(shè)

c一定與所有正例相一致

c一定比h更一般

c中不會(huì)覆蓋一個(gè)反例因此h也不會(huì)FIND-S算法圖示x3x1x2x4實(shí)例集X假設(shè)集Hh0h1h4h2,3x1,x2,x4為正例（紅點(diǎn)）x3為反例（綠點(diǎn)）h1=<Sunny,Warm,Normal,Strong,Warm,Same>h2=<Sunny,Warm,?,Strong,Warm,Same>h3=<Sunny,Warm,?,Strong,Warm,Same>h4=<Sunny,Warm,?,Strong,?,?>特殊一般Find-S算法特點(diǎn)與問(wèn)題特點(diǎn)：對(duì)以屬性約束的合取式描述的假設(shè)空間，F(xiàn)ind-S保證輸出為H中與正例一致的最特殊的假設(shè)。目標(biāo)概念包含在H中，且訓(xùn)練數(shù)據(jù)無(wú)錯(cuò)誤，最終假設(shè)h也與所有反例一致。問(wèn)題：1.學(xué)習(xí)過(guò)程是否收斂到了正確的目標(biāo)概念？2.為什么要用最特殊的假設(shè)？3.訓(xùn)練樣例是否相互一致？4.如果有多個(gè)極大特殊假設(shè)怎么辦？ch最一般的假設(shè)不好嗎？或者說(shuō)介于二者之間的如何？變形空間和候選刪除算法候選刪除算法輸出與訓(xùn)練樣例一致的所有假設(shè)的集合并且不需要明確列舉其所有成員缺點(diǎn)：訓(xùn)練數(shù)據(jù)含有噪聲時(shí)，性能較差為了引入若干機(jī)器學(xué)習(xí)問(wèn)題，提供良好的框架。變形空間定義假設(shè)h與一組樣例D是一致的定義：一個(gè)假設(shè)h與訓(xùn)練樣例集合D一致，當(dāng)且僅當(dāng)對(duì)D中每一個(gè)樣例<x,c(x)>，都有h(x)=c(x)。注意：一致與滿足的區(qū)別！變形空間VersionSpace定義：關(guān)于假設(shè)空間H和訓(xùn)練樣例集D的變形空間，標(biāo)記為VSH,D,是H中與訓(xùn)練樣例D一致的所有假設(shè)構(gòu)成的子集。列表后消除算法列表后消除算法a.變形空間VersionSpace

包含H中所有假設(shè)的列表b.對(duì)每個(gè)訓(xùn)練樣例<x,c(x)>從變型空間中移除所有h(x)!=c(x)的假設(shè)c.輸出VersionSpace中的假設(shè)列表包含的假設(shè)的個(gè)數(shù)？H有限！優(yōu)點(diǎn)：保證得到所有與訓(xùn)練數(shù)據(jù)一致的假設(shè)。H無(wú)限？H包含假設(shè)很多時(shí)？變型空間的更簡(jiǎn)潔表示VersionSpace的邊界{<Sunny,Warm,?,Strong,?,?>}{<Sunny,?,?,?,?,?>,<?,Warm,?,?,?,?>}<Sunny,?,?,Strong,?,?><Sunny,Warm,?,?,?,?><?,Warm,?,Strong,?,?>SkyAirTempHumidityWindWaterForecastEnjoySportSunnyWarmNormalStrongWarmSameYesSunnyWarmHighStrongWarmSameYesRainyColdHighStrongWarmChangeNoSunnyWarmHighStrongCoolChangeYes極大特殊成員集合極大特殊成員集合S：G：一般邊界和特殊邊界一般邊界(GeneralBoundary)G特殊邊界(SpecificBoundary)SG和S被良好的定義，它們就完全規(guī)定了變型空間！變型空間的確切組成：G中所包含的假設(shè)，S中包含假設(shè)以及G和S之間偏序結(jié)構(gòu)所規(guī)定的假設(shè)！候選刪除學(xué)習(xí)算法將G集合初始化為H中極大一般假設(shè)將S集合初始化為H中極大特殊假設(shè)對(duì)每個(gè)訓(xùn)練樣例d，進(jìn)行下面操作如果d是正例從G中移去所有與d不一致的假設(shè)對(duì)S中每個(gè)與d不一致的假設(shè)s從S中移去s把s的所有極小泛化式h加入到S中，其中h滿足h與d一致，而且G的某個(gè)成員比h更一般從S移去所有這樣的假設(shè)：它比S中另一假設(shè)更一般如果d是反例從S中移去所有與d不一致的假設(shè)對(duì)G中每個(gè)與d不一致的假設(shè)g從G中移去g把g的所有極小特殊化式h加入到G中，其中h滿足h與d一致，而且S的某個(gè)成員比h更特殊從G移去所有這樣的假設(shè)：它比G中另一假設(shè)更特殊只要操作被良好的定義了，該算法可應(yīng)用于任意概念學(xué)習(xí)和任意假設(shè)空間。那個(gè)假設(shè)？這個(gè)假設(shè)呢？CandidateEliminationAlgorithm舉例(1)S0={<?,?,?,?,?,?>}ExampleSkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongWarmSameYes2SunnyWarmHighStrongWarmSameYes3RainyColdHighStrongWarmChangeNo4SunnyWarmHighStrongCoolChangeYesG0={<?,?,?,?,?,?>}S1={<Sunny,Warm,Normal,Strong,Warm,Same>}G1=G0S2={<Sunny,Warm,?,Strong,Warm,Same>}G2=G1=G0S2={<Sunny,Warm,?,Strong,Warm,Same>}G2={<?,?,?,?,?,?>}S3=S2G3={<Sunny,?,?,?,?,?>,<?,Warm,?,?,?,?>,<?,?,?,?,?,Same>}G4={<Sunny,?,?,?,?,?>,<?,Warm,?,?,?,?>}S4={<Sunny,Warm,?,Strong,?,?>}CandidateEliminationAlgorithm舉例(2)S4={<Sunny,Warm,?,Strong,?,?>}G4={<Sunny,?,?,?,?,?>,<?,Warm,?,?,?,?>}<Sunny,?,?,Strong,?,?><Sunny,Warm,?,?,?,?><?,Warm,?,Strong,?,?>一般邊界G特殊邊界Sx1Remarkson

Candidate-EliminationAlgorithm(1)是否會(huì)收斂到正確的假設(shè)Xc假設(shè):1.在訓(xùn)練樣例中沒(méi)有錯(cuò)誤。2.H中確實(shí)包含目標(biāo)概念的正確假設(shè)。假設(shè)滿足時(shí)，什么情況目標(biāo)概念才真正獲得呢？

S和G邊界集合收斂到單個(gè)的可確定的假設(shè)！下一步需要什么樣的訓(xùn)練樣例概念學(xué)習(xí)中的最優(yōu)策略查詢：產(chǎn)生實(shí)例以滿足當(dāng)前變型空間中大約半數(shù)的假設(shè)。Remarkson

Candidate-EliminationAlgorithm(2)怎樣使用不完全學(xué)習(xí)的概念S4={<Sunny,Warm,?,Strong,?,?>}G4={<Sunny,?,?,?,?,?>,<?,Warm,?,?,?,?>}<Sunny,?,?,Strong,?,?><Sunny,Warm,?,?,?,?><?,Warm,?,Strong,?,?>InstanceSkyAirTempHumidityWindWaterForecastEnjoySportASunnyWarmNormalStrongCoolChange?BRainyColdNormalLightWarmSame?CSunnyWarmNormalLightWarmSame?DSunnyColdNormalStrongWarmSame?實(shí)例A被VS中的全部假設(shè)劃分為正例?。尚哦茸畲螅?shí)例B被VS中的全部假設(shè)劃分為反例?。尚哦茸畲螅?shí)例C被VS中的一半假設(shè)劃分為正例，一半為反例！（如不提供更多信息，無(wú)法分類）分類歧義性最大！

實(shí)例C與前面最優(yōu)查詢相同！實(shí)例D被VS中的2假設(shè)劃分為正例，4個(gè)為反例！（可信度比A、B要?。w納偏執(zhí)InductiveBias歸納推理中的一些基本問(wèn)題一個(gè)有偏的假設(shè)空間（EnjoySport）考慮目標(biāo)概念“Sky=Sunny或Sky=Cloudy”InstanceSkyAirTempHumidityWindWaterForecastEnjoySport1SunnyWarmNormalStrongCoolChangeYes2CloudyWarmNormalStrongCoolChangeYes3RainyWarmNormalStrongCoolChangeYesVSH,D={},為什么呢？與前兩個(gè)樣例一致，并且能在給定H中表示的最特殊假設(shè)是S2:<?,Warm,Normal,Strong,Cool,Change>需要表示能力更強(qiáng)的假設(shè)空間H歸納偏執(zhí)InductiveBias無(wú)偏的學(xué)習(xí)器?

能否定義一個(gè)H,它能表達(dá)所有的可教授概念?等價(jià)于它能夠表達(dá)實(shí)例集X的所有可能的子集X的冪集PowerSetEnjoySport學(xué)習(xí)任務(wù)中，6屬性實(shí)例空間X的大小為96可以定義的概念數(shù)目：2^