消失候選算法

Question

考慮下面的訓練數據集..

+-------+-------+----------+-------------+ 
| Size | Color | Shape | Class/Label | 
+=======+=======+==========+=============+ 
| big | red | circle | No   | 
| small | red | triangle | No   | 
| small | red | circle | Yes   | 
| big | blue | circle | No   | 
| small | blue | circle | Yes   | 
+-------+-------+----------+-------------+ 

我想明白是怎麼算法進行，當它與一個反面的例子開始，當兩個反面的例子走到了一起。

順便說一句，這不是一個轉讓問題。

與其他數據集的例子也歡迎！這是爲了理解算法的負面部分。

Answer 1

爲了您的假設空間（H），你開始你的套極大一般的（G）和最大特定的（S）假設：

G0 = {<?, ?, ?>} 
S0 = {<0, 0, 0>} 

當你提出了一個反面例子，你需要從S中刪除與當前觀察不一致的任何假設，並用其與觀察一致的最小特化代替G中任何不一致的假設，但仍比一些S的成員更一般。因此，對於你的第一個（否定）例子，最小的專業化將會產生新的假設空間

G1 = {<small, ? , ?>, <?, blue, ?>, <?, ?, triangle>} 
S1 = S0 = {<0, 0, 0>} 

請注意，S沒有變化。對於你的下一個例子，(small, red, triangle)，這也是否定的，你需要進一步專門化G.注意，G1中的第二個假設與新的觀察不匹配，因此只有G1中的第一個和第三個假設需要專門化。這將產生

G2 = {<small, blue, ?>, <small, ?, circle>, <?, blue, ?>, <big, ?, triangle>, <?, blue, triangle>} 

然而，由於上述G2的第一和最後一個假設是中間假說（<?, blue, ?>），我們放棄這兩個的專長，使

G2 = {<small, ?, circle>, <?, blue, ?>, <big, ?, triangle>} 
S2 = S1 = S0 = {<0, 0, 0>} 

對於正(small, red, circle)觀察，你必須概括S和刪除G中任何不一致，這給

G3 = {<small, ?, circle>} 
S3 = {<small, red, circle>} 

(big, blue, circle)是下一個反齒刃例如。但是，由於它不以G一致，沒有什麼可以做

G4 = G3 = {<small, ?, circle>} 
S4 = S3 = {<small, red, circle>} 

最後，你有(small, blue, circle)的正面例子，這就需要你來概括s到使它與一致。例如，給

G5 = {<small, ?, circle>} 
S5 = {<small, ?, circle>} 

由於G和S是平等的，所以你已經學會了「小圈子」的概念。