1.3 假設空間

歸納（induction）與演繹（deduction）是科學推理的兩大基本手段。前者是從特殊到一般的“泛化”（generalization）過程，即從具體的事實歸結出一般性規律；后者則是從一般到特殊的“特化”（specialization）過程，即從基礎原理推演出具體狀況。例如，在數學公理系統中，基于一組公理和推理規則推導出與之相洽的定理，這是演繹；而“從樣例中學習”顯然是一個歸納的過程，因此亦稱“歸納學習”（inductive learning）。

歸納學習有狹義與廣義之分，廣義的歸納學習大體相當于從樣例中學習，而狹義的歸納學習則要求從訓練數據中學得概念（concept），因此亦稱為“概念學習”或“概念形成”。概念學習技術目前研究、應用都比較少，因為要學得泛化性能好且語義明確的概念實在太困難了，現實常用的技術大多是產生“黑箱”模型。然而，對概念學習有所了解，有助于理解機器學習的一些基礎思想。

概念學習中最基本的是布爾概念學習，即對“是”“不是”這樣的可表示為0/1布爾值的目標概念的學習。舉一個簡單的例子，假定我們獲得了這樣一個訓練數據集：

更一般的情況是考慮形如（A∧B）∨（C∧D）的析合范式。

這里要學習的目標是“好瓜”。暫且假設“好瓜”可由“色澤”“根蒂”“敲聲”這三個因素完全確定，換言之，只要某個瓜的這三個屬性取值明確了，我們就能判斷出它是不是好瓜。于是，我們學得的將是“好瓜是某種色澤、某種根蒂、某種敲聲的瓜”這樣的概念，用布爾表達式寫出來則是“好瓜。（色澤=？）∧（根蒂=？）∧（敲聲=？）”，這里“？”表示尚未確定的取值，而我們的任務就是通過對表1.1的訓練集進行學習，把“？”確定下來。

“記住”訓練樣本，就能力。如果僅僅把訓練集中的瓜“記住”，是所謂的“機械學習”[Cohen and Feigenbaum,1983]，或稱“死記硬背式學習”，參見（1.5 發展歷程）。

讀者可能馬上發現，表1.1第一行：“（色澤=青綠）∧（根蒂=蜷縮）∧（敲聲=濁響）”不就是好瓜嗎？是的，但這是一個已見過的瓜，別忘了我們學習的目的是“泛化”，即通過對訓練集中瓜的學習以獲得對沒見過的瓜進行判斷的能力。如果僅僅把訓練集中的瓜“記住”，今后再見到一模一樣的瓜當然可判斷，但是，對沒見過的瓜，例如“（色澤=淺白）∧（根蒂=蜷縮）∧（敲聲=濁響）”怎么辦呢？

這里我們假定訓練樣本不含噪聲，并且不考慮“非青綠”這樣的操作。由于訓練集包含正例，因此假設自然不出現。

我們可以把學習過程看作一個在所有假設（hypothesis）組成的空間中進行搜索的過程，搜索目標是找到與訓練集“匹配”（fit）的假設，即能夠將訓練集中的瓜判斷正確的假設。假設的表示一旦確定，假設空間及其規模大小就確定了。這里我們的假設空間由形如“（色澤=？）∧（根蒂=？）∧（敲聲=？）”的可能取值所形成的假設組成。例如色澤有“青綠”“烏黑”“淺白”這三種可能取值；還需考慮到，也許“色澤”無論取什么值都合適，我們用通配符“*”來表示，例如“好瓜。（色澤=*）∧（根蒂=蜷縮）∧（敲聲=濁響）”，即“好瓜是根蒂蜷縮、敲聲濁響的瓜，什么色澤都行”。此外，還需考慮極端情況：有可能“好瓜”這個概念根本就不成立，世界上沒有“好瓜”這種東西；我們用表示這個假設。這樣，若“色澤”“根蒂”“敲聲”分別有3、3、3種可能取值，則我們面臨的假設空間規模大小為4×4×4+1=65。圖1.1直觀地顯示出了這個西瓜問題假設空間。

有許多可能的選擇，如在路徑上自頂向下與自底向上同時進行，在操作上只刪除與正例不一致的假設等。

可以有許多策略對這個假設空間進行搜索，例如自頂向下、從一般到特殊，或是自底向上、從特殊到一般，搜索過程中可以不斷刪除與正例不一致的假設、和（或）與反例一致的假設。最終將會獲得與訓練集一致（即對所有訓練樣本能夠進行正確判斷）的假設，這就是我們學得的結果。

需注意的是，現實問題中我們常面臨很大的假設空間，但學習過程是基于有限樣本訓練集進行的，因此，可能有多個假設與訓練集一致，即存在著一個與訓練集一致的“假設集合”，我們稱之為“版本空間”（version space）。例如，在西瓜問題中，與表1.1訓練集所對應的版本空間如圖1.2所示。