19.1.3 最少約定搜索

當(dāng)前最佳假設(shè)方法即使在數(shù)據(jù)不充分而對選擇沒有把握的時(shí)候，也必須選擇某個(gè)特定假設(shè)作為最佳猜測，因而會(huì)產(chǎn)生回溯。替代地，我們可以只保存與目前已有的所有數(shù)據(jù)保持一致的全部假設(shè)。每個(gè)新的實(shí)例要么不產(chǎn)生任何影響，要么去掉某些假設(shè)?；貞浺幌略技僭O(shè)空間可以被視為一個(gè)析取語句：

H1∨H2∨H3∨…∨Hn

當(dāng)發(fā)現(xiàn)各種假設(shè)與實(shí)例不一致時(shí)，這個(gè)析取式會(huì)收縮，只保留那些沒有被排除的假設(shè)。設(shè)原始假設(shè)空間的確包含那個(gè)正確答案，那么經(jīng)過縮減后的析取式一定仍然包含正確答案——因?yàn)橹挥心切┎徽_的假設(shè)被去除了。保留下來的假設(shè)集合被稱為變型空間（version space），相應(yīng)的學(xué)習(xí)算法（如圖19.3所示）被稱為變型空間學(xué)習(xí)算法（也叫做候選消除算法）。

圖19.3 變型空間學(xué)習(xí)算法。算法找到V的一個(gè)子集，與examples保持一致

這種學(xué)習(xí)方法的一個(gè)重要特性是它是增量學(xué)習(xí)的：從不需要回頭重新檢查那些已處理過的實(shí)例。無論如何，所有保留下來的假設(shè)都保證與這些實(shí)例一致。這也是一個(gè)最少約定算法，因?yàn)樗贿M(jìn)行任意的選擇（與第十一章中的偏序規(guī)劃方法相比較）。但是它也有一個(gè)明顯的問題。我們已經(jīng)說過假設(shè)空間是規(guī)模巨大的，因此我們?nèi)绾文軌虬堰@個(gè)巨大的析取式寫下來？

下面的這個(gè)簡單類比非常有幫助。如何表示1和2之間的所有實(shí)數(shù)？畢竟，它們的數(shù)量是無限的！答案是使用一個(gè)區(qū)間表示法，指明這個(gè)集合的邊界：[1, 2]。這種方法之所以有效是因?yàn)閷?shí)數(shù)上存在一個(gè)序。

我們在假設(shè)空間上也有一個(gè)序，即一般化/特殊化。這是一個(gè)偏序關(guān)系，即每個(gè)邊界不是一個(gè)點(diǎn)而是一個(gè)假設(shè)的集合，稱為邊界集。重要的是我們可以只用兩個(gè)邊界集就表示整個(gè)變型空間：一個(gè)最一般的邊界（G-集）和一個(gè)最特殊的邊界（S-集）。這兩個(gè)邊界之間的所有假設(shè)都保證與實(shí)例一致。在我們證明這一點(diǎn)之前，讓我們重申一下：

? 當(dāng)前的變型空間是與到目前為止所有的實(shí)例都保持一致的假設(shè)的集合。它用 G-集和 S-集表示，每個(gè)邊界集都是一組假設(shè)集。

? S-集中的每個(gè)成員都與目前為止所有的觀察一致，并且不存在更特殊的一致假設(shè)。

? G-集中的每個(gè)成員都與目前為止所有的觀察一致，并且不存在更一般的一致假設(shè)。

我們希望初始的變型空間（在看不到任何實(shí)例之前）能夠表示所有可能的假設(shè)。這時(shí)G-集被設(shè)為包含True（也就是包含所有實(shí)例的假設(shè)），S-集被設(shè)為包含F(xiàn)alse（外延為空的假設(shè)）。

圖19.4顯示了變型空間的邊界集表示法的一般結(jié)構(gòu)。為了說明這個(gè)表示是充分的，我們需要下面兩個(gè)屬性：

圖19.4 包括所有與樣例一致的假設(shè)的變型空間

① 每個(gè)一致假設(shè)（除了邊界集中的假設(shè)以外）都比G-集中的某個(gè)成員更特殊，也比S-集中的某個(gè)成員更一般。（也就是說，沒有“漏網(wǎng)之魚”。）這能夠從S和G的定義中直接得出。如果存在一個(gè)遺漏的h，那么它一定比G中的任何成員都更特殊，在這種情況下它屬于G；或者比S中的任何元素都更一般，在這種情況下它屬于S。

② 每個(gè)比G-集中的某個(gè)成員更特殊并且比S-集合中的某個(gè)成員更一般的假設(shè)都是一個(gè)一致假設(shè)（即在邊界之間沒有“漏洞”）。在S和G之間的任何h一定拒絕那些被G中的每個(gè)成員都拒絕的反例（因?yàn)閔更特殊），也一定接受被S中的任何成員接受的正例（因?yàn)閔更一般）。因此， h一定符合所有的實(shí)例，從而不可能是不一致的。圖19.5表示了這樣的情形：沒有已知實(shí)例在S之外而在G之內(nèi)，因此縫隙中的所有假設(shè)一定都是一致的。

圖19.5 G和S中的成員的外延。在兩個(gè)邊界集之間沒有已知實(shí)例

因此我們已經(jīng)說明了如果能夠保持S和G符合它們的定義，那么它們就提供了一個(gè)變型空間的令人滿意的表示。剩下的唯一問題就是對一個(gè)新實(shí)例，如何更新S和G（函數(shù)VERSION-SPACE-UPDATE的工作）。最初這看起來似乎很復(fù)雜，但是根據(jù)定義，并輔以圖19.4，重新構(gòu)造算法就不是太困難了。

我們需要考慮S-集和G-集中的成員Si和Gi。對于每個(gè)成員，新的實(shí)例可能是一個(gè)錯(cuò)誤正例或者錯(cuò)誤反例。

① Si的錯(cuò)誤正例：意味著Si太一般化了，但是根據(jù)定義不存在Si的一致的特殊化，所以我們把它從S-集中去掉。

② Si的錯(cuò)誤反例：意味著Si太特殊化了，所以我們把它替換成所有對其進(jìn)行的直接一般化，倘若它們比G中的某成員更特殊。

③ Gi的錯(cuò)誤正例：意味著 Gi太一般化了，所以我們把它替換成所有對其進(jìn)行的直接特殊化，倘若它們比S中的某成員更一般。

④ Gi的錯(cuò)誤反例：意味著Gi太特殊化了，但是根據(jù)定義不存在Gi的一致的一般化，所以我們把它從G-集中去掉。

我們持續(xù)對每個(gè)新的實(shí)例執(zhí)行這些操作，直到下列3種情況之一發(fā)生：

① 在變型空間中剛好剩下一個(gè)概念，這種情況下我們將它作為唯一假設(shè)返回；

② 變型空間坍塌——S 或者 G 變?yōu)榭占砻鲗τ?xùn)練集合而言，沒有一致的假設(shè)。這與決策樹算法的簡單版本中的失敗情況相同。

③ 當(dāng)我們用完全部實(shí)例后，在變型空間中還剩下多個(gè)假設(shè)。這意味著變型空間表示了假設(shè)的一個(gè)析取式。對于任何新的實(shí)例，如果所有的析取子句意見都相同，則我們可以返回它們對該實(shí)例的分類；如果不同，則一種可能方法是采用多數(shù)投票。

我們把在餐館問題上應(yīng)用VERSION-SPACE-LEARNING算法留作一道習(xí)題。

變型空間方法有幾個(gè)主要缺點(diǎn)：

? 如果域中含有噪聲或者在精確分類中有不充分的屬性，則變型空間總是要坍塌的。

? 如果我們允許假設(shè)空間的無限析取式，那么S-集將總是包含一個(gè)單一的最特殊假設(shè)，即到目前為止見到過的正例描述的一個(gè)析取式。類似地，G-集將只包含反例描述的析取式的非。

? 對于某些假設(shè)空間來說，即使存在高效的學(xué)習(xí)算法，S-集和G-集中的元素個(gè)數(shù)仍然可能按照屬性個(gè)數(shù)的指數(shù)級(jí)增長。

到目前為止，還沒有找到完全成功的方案解決噪聲問題。析取式的問題可以通過允許有限形式的析取式或者包括使用更一般謂詞的一般化層次結(jié)構(gòu)來解決。例如，取代析取式 WaitEstimate(x, 30-60)∨WaitEstimate(x,＞60)，我們可以使用一個(gè)簡單的文字LongWait(x)。一般化和特殊化操作的集合可以很容易地進(jìn)行擴(kuò)展以處理該問題。

單純的變型空間算法首先被用于Meta-DENDRAL系統(tǒng)中，是為學(xué)習(xí)規(guī)則以預(yù)測質(zhì)譜儀中分子如何分裂成小塊而設(shè)計(jì)的（Buchanan和Mitchell，1978）。Meta-DENDARL能夠生成規(guī)則，它們在分析化學(xué)的一本授權(quán)出版的期刊中是全新的——第一次由一個(gè)計(jì)算機(jī)程序生成的真正的科學(xué)知識(shí)。這一算法還用于優(yōu)雅的 LEX 系統(tǒng)中（Mitchell 等人，1983），該系統(tǒng)能夠通過研究自身的成功和失敗而學(xué)習(xí)求解符號(hào)積分問題。雖然主要由于噪聲問題，使得變型空間方法可能在大多數(shù)現(xiàn)實(shí)世界的學(xué)習(xí)問題中并不實(shí)用，但是它們提供了很多對假設(shè)空間的邏輯結(jié)構(gòu)的深入了解。