從特殊的訓(xùn)練樣例中提取出一般的特征是機(jī)器學(xué)習(xí)的中心問題，這一問題被稱為概念學(xué)習(xí)（concept learning)，或稱從樣例中逼近布爾值函數(shù)。定義： 概念學(xué)習(xí)是指從有關(guān)某個(gè)布爾函數(shù)的輸入輸出訓(xùn)練樣例中推斷出該布爾函數(shù)。

術(shù)語(yǔ)定義

概念定義在一個(gè)實(shí)例（instance）集合之上，表示為X。
　　目標(biāo)概念（target concept）： 待學(xué)習(xí)的概念或函數(shù)，記作c。一般來說，c是可以定義在實(shí)例集X上的任意布爾函數(shù)，即c:X→{0,1}。
　　訓(xùn)練樣例（training examples）：每個(gè)樣例為X中的一個(gè)實(shí)例x以及它的目標(biāo)概念值c(x)。對(duì)于c(x)=1的實(shí)例被稱為正例（positive example)，對(duì)于c(x)=0的實(shí)例為反例（negative example）。經(jīng)?？梢杂眯蚺?lt;x,c(x)>來描述訓(xùn)練樣例。
　　假設(shè)（hypothese)：對(duì)目標(biāo)概念的估計(jì)，所有可能假設(shè)的集合為H。H中的每個(gè)假設(shè)h表示X上的定義的布爾函數(shù)即h:X→{0,1}。機(jī)器學(xué)習(xí)的目標(biāo)就是尋找一個(gè)假設(shè)，使對(duì)于X中的所有x,h(x) = c(x)。
　　歸納學(xué)習(xí)假設(shè):任一假設(shè)如果在足夠大的訓(xùn)練樣例集中很好的逼近目標(biāo)函數(shù)，它也能在未見實(shí)例中很好的逼近目標(biāo)函數(shù)。

假設(shè)的一般到特殊序

如果任何被h1劃分為正例的實(shí)例都會(huì)被h2劃分為正例，那么我就說h2比h1更一般。

FIND-S：尋找極大特殊假設(shè)

FIND-S算法使用一般到特殊序，在偏序結(jié)構(gòu)的一個(gè)分支上執(zhí)行一般到特殊搜索，以尋找與樣例一致的最特殊假設(shè)。從H中最特殊假設(shè)開始，然后再該假設(shè)覆蓋正例失敗時(shí)將其一般化（當(dāng)一假設(shè)能正確地劃分一個(gè)正例時(shí)，稱該假設(shè)“覆蓋”該正例），算法如下：

　　FIND-S算法的重要特點(diǎn)是：對(duì)以屬性約束的合取式描述的假設(shè)空間，F(xiàn)IND-S保證輸出為H中與正例一致的最特殊的假設(shè)。然而，這一學(xué)習(xí)算法仍存在一些未解決的問題：

• 學(xué)習(xí)過程是否收斂到了正確的目標(biāo)概念，也就是沒法確定它是否找到了唯一合適的假設(shè)。
• 為什么要用最特殊的假設(shè)。
• 訓(xùn)練樣例是否相互一致。訓(xùn)練數(shù)據(jù)中的某些錯(cuò)誤或噪聲會(huì)嚴(yán)重破壞FIND-S算法，因?yàn)樗雎粤怂蟹蠢?/li>
• 如何處理有多個(gè)極大特殊假設(shè)的情況

變型空間和候選消除算法

候選消除（candidate-elimination）算法能解決FIND-S中的若干不足之處。FIND-S輸出的假設(shè)只是H種能夠擬合訓(xùn)練樣例的多個(gè)假設(shè)中的一個(gè)，而候選消除算法輸出的是如訓(xùn)練樣例一致的所有假設(shè)的集合。候選消除算法利用一般到特殊序，通過漸進(jìn)地計(jì)算極大特殊假設(shè)集合S和極大一般假設(shè)集合G計(jì)算變型空間。

表示

當(dāng)一個(gè)假設(shè)能正確分類一組樣例時(shí)，我們稱這個(gè)假設(shè)是與這些樣例一致的（consistent）。

　　候選消除算法能夠表示與訓(xùn)練樣例一致的所有假設(shè)，在假設(shè)空間中這一子集被稱為關(guān)于假設(shè)空間H和訓(xùn)練樣例D的變型空間（version space），因?yàn)樗四繕?biāo)概念的所有合理變型。

列表后消除算法

列表后消除算法列出所有成員來表示變型空間。

　　這一算法能保證得到所有與訓(xùn)練數(shù)據(jù)一致的假設(shè)，但是要繁瑣的列出H中所有假設(shè)，這對(duì)于大多數(shù)實(shí)際的假設(shè)空間是并不現(xiàn)實(shí)。

變型空間的更簡(jiǎn)潔表示

候選消除算法與列表后消除算法遵循同樣的原則，但它使用一種更簡(jiǎn)潔的變型空間表示法。變型空間被表示為它的極大一般和極大特殊的成員。這些成員形成了一般和特殊邊界的集合，這些邊界在整個(gè)偏序結(jié)構(gòu)中劃分出變型空間。

候選消除學(xué)習(xí)算法

關(guān)于變型空間和候選消除的說明

候選消除算法是否會(huì)收斂到正確的假設(shè)

由候選消除算法得到的變型空間能夠收斂到正確假設(shè)的條件是：

• 在訓(xùn)練樣例中沒有錯(cuò)誤
• H中確實(shí)包含描述目標(biāo)概念的正確假設(shè)

下一步需要什么樣的訓(xùn)練樣例

一般來說，概念學(xué)習(xí)的最優(yōu)查詢策略，是產(chǎn)生實(shí)例以滿足當(dāng)前變型空間中大約半數(shù)的假設(shè)。這樣，變型空間的大小可以在遇到每個(gè)新樣例時(shí)減半，正確的目標(biāo)概念就可在只用?㏒?|VS|?次實(shí)驗(yàn)后得到。

歸納偏置

現(xiàn)在還有一些問題，比如目標(biāo)概念不在假設(shè)空間中怎么辦？假設(shè)空間的大小對(duì)算法推廣到未見實(shí)例的能力有什么影響？假設(shè)空間的大小對(duì)所需訓(xùn)練樣例的數(shù)量有什么影響？這些都是歸納推理中的一些基本問題。

有偏的學(xué)習(xí)器

如果擴(kuò)大假設(shè)空間來使每個(gè)可能的假設(shè)都被包含在內(nèi)，則有偏的假設(shè)空間可定義的目標(biāo)概念數(shù)量會(huì)過于巨大。

無偏的學(xué)習(xí)器

為了保證目標(biāo)概念在假設(shè)空間中，我們需要一個(gè)能表達(dá)所有的可教授概念（every teachable concept）（即能夠表達(dá)實(shí)例集X的所有可能的子集）的假設(shè)空間。一般我們把集合X的所有子集的集合稱為X的冪集（power set）。
　　如果我們使用無偏的形式，將假設(shè)空間定義為允許使用前面假設(shè)的任意析取、合取或否定式，這樣我們可以安全的使用候選消除算法而不必?fù)?dān)心無法表達(dá)目標(biāo)概念。然而新的問題是：概念學(xué)習(xí)算法將完全無法從訓(xùn)練樣例中泛化。

無偏學(xué)習(xí)的無用性

以上的討論說明了歸納推理的一個(gè)基本屬性：學(xué)習(xí)器如果不對(duì)目標(biāo)概念的形式做預(yù)先的假定 ，它從根本上無法對(duì)未見實(shí)例進(jìn)行分類。由于歸納學(xué)習(xí)需要某種形式的預(yù)先假定，或稱為歸納偏置（inductive bias），我們可以用歸納偏置來描述不同學(xué)習(xí)方法的特征。

　　候選消除算法的歸納偏置：目標(biāo)概念c包含在給定的假設(shè)空間H中。
　　一種算法如果有偏性越強(qiáng)，那它的歸納能力越強(qiáng)，可以分類更多的未見實(shí)例。