定義

概念學習是指從有關某個布爾函數(shù)的輸入輸出訓練樣例中，推斷出該布爾函數(shù)

任務描述

• 實例集合（X）
• 實例集合上的目標函數(shù)（C）
• 候選假設的集合（H）
• 訓練樣例集合（D）

機器學習任的任務是在整個實例集合X上確定與目標概念c相同的假設h

術語定義

1. 概念定義在一個實例集合之上，該集合表示為X。
2. 待學習的概念或函數(shù)稱為目標概念。
3. 在學習目標概念時， 必須提供一套訓練樣例， 每個樣例為X中的一個實例x以及它的目標概念值c(x)，對c(x)=1的實例被稱之為正例或目標概念成員，相反對于c(x)=0的實例稱為反例或非目標概念成員。通常用序偶<x, c(x)>來描述訓練樣例，表示包含了實例x和目標概念值c(x)。
4. 一旦給定目標概念c的訓練樣例集， 學習器面臨的問題就是假設或者估計c。H表示所有可能假設的集合，H確定目標概念考慮的范圍。通常H依設計者所選擇的假設表示而定。H中假設h表示X上定義的布爾函數(shù),即h:X->{0， 1}。機器學習的目標就是尋找一個假設h，使對于X中的所有x, h(x)=c(x)。

歸納學習假設

機器學習任的任務是在整個實例集合X上確定與目標概念c相同的假設h，然而我們對于c僅有的信息只是它在訓練樣例上的值，因此，歸納學習算法最多只能保證輸出的假設能與訓練樣例相擬合。如果沒有更多的信息，我們只能假定，對未見實例最好的假設就是與訓練數(shù)據(jù)最佳你和的假設，這是歸納學習的一個基本假定。

任一假設如果在足夠大的訓練樣例集中很好的逼近目標函數(shù)，它也能在未見實例中很好的逼近目標函數(shù)

作為搜索的概念學習

概念學習可以看做是一個搜索的過程，范圍是假設的表示所隱含定義的整個空間

如果把學習看作是一個搜索為題，那么自然，對于學習算法的研究需要考查假設空間搜索的不同策略，特別引起我們興趣的算法應該能有效地搜索非常大或無限的假設空間，以找到最佳擬合訓練數(shù)據(jù)的假設。

假設的一般到特殊序

對X中任意實例x和H中任意假設h， 我們說x滿足h當且僅當h(x)=1

任何被h₁劃分為正例的實例都會被h₂劃分為正例，我們就說h₂比h₁更一般

** more-general-than-or-equal-to的定義如下：**
令h_j和h_k為在X上定義的布爾函數(shù)。定義more-general-than-or-equal-to關系(≥_g )。h_j ≥ _gh_k當且僅當：
（?x ∈ X）[(h_k(x)=1)->(h_j(x)=1)]

備注：嚴格一般為上面定義去除等于

Find-S: 尋找極大特殊假設

1. 將h初始化為H中最特數(shù)的假設
2. 對每個正例x

• 對h的每個屬性約束a_i, 如果x滿足a_i，那么不做任何事，否則，將h中a_i替換為x滿足的近鄰的更一般約束

3. 輸出假設h

Find-S算法存在的一些未解決的問題

• 學習過程是否手鏈到了正確的目標概念？雖然Find-S找到了與訓練數(shù)據(jù)一致的假設，但沒辦法確定它否找到了唯一合適的假設，或是否還有其他可能的假設。我們希望算法知道它是否收斂到了目標概念，如果不能，至少要描述出這種不確定性。
• 為什么要用最特殊的假設。如果有多個與訓練樣例一致的假設，F(xiàn)ind-S只能找出最特殊的。為什么我們偏好最特殊的假設，而不選最一般的假設，或者一般程度位于兩者之間的某個假設。
• 訓練樣例是否相互一致？在多數(shù)實際的學習問題中，訓練數(shù)據(jù)中常會出現(xiàn)某些錯誤或者噪聲，這樣的不一致的訓練集會嚴重破壞Find-S算法，因為它忽略了所有的反例。我們期望的算法至少能檢測出訓練數(shù)據(jù)的不一致性，并且最好能容納這樣的錯誤。
• 如果有多個極大特數(shù)假設怎么辦？在一些假設空間可能有多個極大特數(shù)假設。這種情況下，F(xiàn)ind-S必須被擴展以允許其在選擇怎樣泛華假設的路徑上回溯，以容納目標假設位于偏序結構的另一分支上的可能性。更進一步，我們可以定義一個不存在極大特殊假設的假設空間，然而這是一個更理論性的問題而非實踐問題。

變形空間和候選消除算法

候選消除算法中，輸出的是與訓練樣例一致的所有假設的集合。且候選消除算法在描述這一集合時不需要明確列舉其所有成員，這主要歸功于more-general-than偏序結構，在這里需要維護一個一致假設集合的簡潔表示，然后在遇到新的訓練樣例時逐步精化這一表示。

定義:一個假設h與訓練樣例集合D一致（consistent），當且僅當對D中的每個樣例<x,c(x)>, h(x)=c(x)

** Consistent(h,D) Ξ (? <x, c(x)> ∈ D ) h(x) = c(x)**
一致與滿足的區(qū)別：一個樣例x在h(x)=1時稱為滿足假設h，不論x是目標概念的正例還是反例。然而，這一樣例是否與h一致與目標概念有關，即是否h(x) = c(x)

定義：關于假設空間H與訓練樣例集D的變型空間(version space)，標記為VS_H,D,是H中與訓練樣例D一致的所有假設構成的子集。

列表后消除算法

1. 變型空間VersionSpace<-包含H中所有的假設列表

2. 對每個訓練樣例<x, c(x)>，從變型空間中移除所有h(x) ≠ c(x)的假設h
3. 輸出VersionSpace中的假設列表

候選消除算法

候選消除算法與上面的列表后消除算法遵循同樣的原則。然而，它