1.4 歸納偏好

通過學習得到的模型對應了假設空間中的一個假設。于是，圖1.2的西瓜版本空間給我們帶來一個麻煩：現在有三個與訓練集一致的假設，但與它們對應的模型在面臨新樣本的時候，卻會產生不同的輸出。例如，對（色澤=青綠；根蒂=蜷縮；敲聲=沉悶）這個新收來的瓜，如果我們采用的是“好瓜。（色澤=*）∧（根蒂=蜷縮）∧（敲聲=*）”，那么將會把新瓜判斷為好瓜，而如果采用了另外兩個假設，則判斷的結果將不是好瓜。那么，應該采用哪一個模型（或假設）呢？

盡可能特殊即“適用情形盡可能少”；盡可能一般即“適用情形盡可能多”。

對“根蒂”還是對“敲聲”更重視，看起來和屬性選擇，亦稱“特征選擇”（feature selection）有關，但需注意的是，機器學習中的特征選擇仍是基于對訓練樣本的分析進行的，而在此處我們并非基于特征選擇做出對“根蒂”的重視；這里對“根蒂”的信賴可視為基于某種領域知識而產生的歸納偏好。關于特征選擇方面的內容參見（第11章 特征選擇與稀疏學習）。

若僅有表1.1中的訓練樣本，則無法斷定上述三個假設中哪一個“更好”。然而，對于一個具體的學習算法而言，它必須要產生一個模型。這時，學習算法本身的“偏好”就會起到關鍵的作用。例如，若我們的算法喜歡“盡可能特殊”的模型，則它會選擇“好瓜。（色澤=*）∧（根蒂=蜷縮）∧（敲聲=濁響）”；但若我們的算法喜歡“盡可能一般”的模型，并且由于某種原因它更“相信”根蒂，則它會選擇“好瓜。（色澤=*）∧（根蒂=蜷縮）∧（敲聲=*）”。機器學習算法在學習過程中對某種類型假設的偏好，稱為“歸納偏好”（inductivebias），或簡稱為“偏好”。

任何一個有效的機器學習算法必有其歸納偏好，否則它將被假設空間中看似在訓練集上“等效”的假設所迷惑，而無法產生確定的學習結果。可以想象，如果沒有偏好，我們的西瓜學習算法產生的模型每次在進行預測時隨機抽選訓練集上的等效假設，那么對這個新瓜“（色澤=青綠；根蒂=蜷縮；敲聲=沉悶）”，學得模型時而告訴我們它是好的、時而告訴我們它是不好的，這樣的學習結果顯然沒有意義。

歸納偏好的作用在圖1.3這個回歸學習圖示中可能更直觀。這里的每個訓練樣本是圖中的一個點（x，y），要學得一個與訓練集一致的模型，相當于找到一條穿過所有訓練樣本點的曲線。顯然，對有限個樣本點組成的訓練集，存在著很多條曲線與其一致。我們的學習算法必須有某種偏好，才能產出它認為“正確”的模型。例如，若認為相似的樣本應有相似的輸出（例如，在各種屬性上都很相像的西瓜，成熟程度應該比較接近），則對應的學習算法可能偏好圖1.3中比較“平滑”的曲線A而不是比較“崎嶇”的曲線B。

歸納偏好可看作學習算法自身在一個可能很龐大的假設空間中對假設進行選擇的啟發式或“價值觀”。那么，有沒有一般性的原則來引導算法確立“正確的”偏好呢？“奧卡姆剃刀”（Occam's razor）是一種常用的、自然科學研究中最基本的原則，即“若有多個假設與觀察一致，則選最簡單的那個”。如果采用這個原則，并且假設我們認為“更平滑”意味著“更簡單”（例如曲線A更易于描述，其方程式是y=-x2+6x+1,而曲線B則要復雜得多），則在圖1.3中我們會自然地偏好“平滑”的曲線A。

然而，奧卡姆剃刀并非唯一可行的原則。退一步說，即便假定我們是奧卡姆剃刀的鐵桿擁躉，也需注意到，奧卡姆剃刀本身存在不同的詮釋，使用奧卡姆剃刀原則并不平凡。例如對我們已經很熟悉的西瓜問題來說，“假設1：好瓜。（色澤=*）∧（根蒂=蜷縮）∧（敲聲=濁響）”和假設2：“好瓜。（色澤=*）∧（根蒂=蜷縮）∧（敲聲=*）”這兩個假設，哪一個更“簡單”呢？這個問題并不簡單，需借助其他機制才能解決。

事實上，歸納偏好對應了學習算法本身所做出的關于“什么樣的模型更好”的假設。在具體的現實問題中，這個假設是否成立，即算法的歸納偏好是否與問題本身匹配，大多數時候直接決定了算法能否取得好的性能。

讓我們再回頭看看圖1.3.假設學習算法a基于某種歸納偏好產生了對應于曲線A的模型，學習算法b基于另一種歸納偏好產生了對應于曲線B的模型。基于前面討論的平滑曲線的某種“描述簡單性”，我們滿懷信心地期待算法a比b更好。確實，圖1.4（a）顯示出，與B相比，A與訓練集外的樣本更一致；換言之，A的泛化能力比B強。

但是，且慢！雖然我們希望并相信a比b更好，但會不會出現圖1.4（b）的情況：與A相比，B與訓練集外的樣本更一致？

這里只用到一些非常基礎的數學知識，只準備讀第1章且有“數學恐懼”的讀者可以跳過這個部分而不會影響理解，只需相信，上面這個看起來“匪夷所思”的結論確實是成立的。

很遺憾，這種情況完全可能出現。換言之，對于一個學習算法a，若它在某些問題上比學習算法b好，則必然存在另一些問題，在那里b比a好。有趣的是，這個結論對任何算法均成立，哪怕是把本書后面將要介紹的一些聰明算法作為a而將“隨機胡猜”這樣的笨拙算法作為b。驚訝嗎？讓我們看看下面這個簡短的討論：

為簡單起見，假設樣本空間和假設空間都是離散的。令P（h|X,a）代表算法a基于訓練數據X產生假設h的概率， 再令f代表我們希望學習的真實目標函數。a的“訓練集外誤差”，即a在訓練集之外的所有樣本上的誤差為

其中Ⅱ（·）是指示函數，若·為真則取值1，否則取值0。

若f均勻分布，則有一半的f對x的預測與h（x）不一致。

考慮二分類問題，且真實目標函數可以是任何函數?{0，1}，函數空間為{0，1}||。對所有可能的f按均勻分布對誤差求和，有

式（1.2）顯示出，總誤差竟然與學習算法無關！對于任意兩個學習算法a和b，我們都有

嚴格的NFL定理證明比這里的簡化論述繁難得多。

也就是說，無論學習算法a多聰明、學習算法b多笨拙，它們的期望性能竟然相同！這就是“沒有免費的午餐”定理（No Free Lunch Theorem，簡稱NFL定理）[Wolpert, 1996; Wolpert and Macready，1995].

這下子，讀者對機器學習的熱情可能被一盆冷水澆透了：既然所有學習算法的期望性能都跟隨機胡猜差不多，那還有什么好學的？

我們需注意到，NFL定理有一個重要前提：所有“問題”出現的機會相同、或所有問題同等重要。但實際情形并不是這樣。很多時候，我們只關注自己正在試圖解決的問題（例如某個具體應用任務），希望為它找到一個解決方案，至于這個解決方案在別的問題、甚至在相似的問題上是否為好方案，我們并不關心。例如，為了快速從A地到達B地，如果我們正在考慮的A地是南京鼓樓、B地是南京新街口，那么“騎自行車”是很好的解決方案；這個方案對A地是南京鼓樓、B地是北京新街口的情形顯然很糟糕，但我們對此并不關心。

事實上，上面NFL定理的簡短論述過程中假設了的均勻分布，而實際情形并非如此。例如，回到我們熟悉的西瓜問題，考慮{假設1：好瓜。（色澤=*）∧（根蒂=蜷縮）∧（敲聲=濁響）}和{假設2：好瓜。（色澤=*）∧（根蒂=硬挺）∧（敲聲=清脆）}。從NFL定理可知，這兩個假設同樣好。我們立即會想到符合條件的例子，對好瓜（色澤=青綠；根蒂=蜷縮；敲聲=濁響）是假設1更好，而對好瓜（色澤=烏黑；根蒂=硬挺；敲聲=清脆）則是假設2更好。看上去的確是這樣。然而需注意到，“（根蒂=蜷縮；敲聲=濁響）”的好瓜很常見，而“（根蒂=硬挺；敲聲=清脆）”的好瓜罕見，甚至不存在。

所以，NFL定理最重要的寓意，是讓我們清楚地認識到，脫離具體問題，空泛地談論“什么學習算法更好”毫無意義，因為若考慮所有潛在的問題，則所有學習算法都一樣好。要談論算法的相對優劣，必須要針對具體的學習問題；在某些問題上表現好的學習算法，在另一些問題上卻可能不盡如人意，學習算法自身的歸納偏好與問題是否相配，往往會起到決定性的作用。