【西瓜書】周志華《機器學習》學習筆記與習題探討（一）

【第1章 緒論】

〖一、知識點歸納〗

1.1 引言

學習演算法：機器學習所研究的主要內容，是關於在計算機上從數據中產生「模型」的演算法，即「學習演算法」。

學習演算法的作用：1.基於提供的經驗數據產生模型；

2.面對新情況時，模型可提供相應的判斷。

模型：泛指從數據中學得的結果。

學習器：學習演算法在給定數據和參數空間上的實例化。

1.2 基本術語

要進行機器學習，先要有數據。

數據集：一組記錄的集合。

示例/樣本/特徵向量：每條記錄（關於一個事件或對象的描述）或空間中的每一個點（對應一個坐標向量）。

屬性/特徵：反應事件或對象在某方面的表現或性質的事項。

屬性值：屬性上的取值。

屬性空間/樣本空間/輸入空間：屬性張成的空間。

維數：屬性的個數。

模型需要從數據中學得。

學習/訓練：從數據中學得模型的過程。

訓練數據：訓練過程中使用的數據。

訓練樣本：每個樣本。

訓練集：訓練樣本組成的集合。

假設：學習模型對應了關於數據的某種潛在的規律。

真相/真實：這種潛在規律自身。

學習過程就是為了找出或逼近真相。

獲得訓練樣本的結果信息，才能建立「預測」的模型。

標記：關於示例結果的信息。

樣例：擁有了標記信息的示例。

標記空間：所有標記的集合。

測試：學得模型後，使用其進行預測的過程。

測試樣本：被預測的樣本。

聚類：將訓練集中的訓練樣本分成若干組。

簇：每組稱為一個「簇」，這些自動形成的「簇」可能對應一些潛在的概念劃分。

根據訓練數據是否擁有標記信息，學習任務可大致劃分為兩類。

機器學習的目標是使學得的模型能更好地適用於「新樣本」。

泛化：學得模型適用於新樣本的能力。

1.3 假設空間

學習過程看作一個在所有假設組成的空間中進行的搜索的過程，搜索目標是找到與訓練集「匹配」的假設。

假設空間：機器學習中可能的函數構成的空間稱為「假設空間」。

版本空間：一個與訓練集一致的「假設集合」。

1.4 歸納偏好

歸納偏好：機器學習演算法在學習過程中對某種類型假設的偏好。

任何一個有效的機器學習演算法必有其歸納偏好。

「奧卡姆剃刀」原則：「若有多個假設與觀察一致，則選最簡單的那個。」

注意： 奧卡姆剃刀並非唯一可行的原則；

奧克姆剃刀本身存在不同的詮釋。

「沒有免費的午餐」定理（NFL定理）：總誤差與學習演算法無關。

注意： 脫離具體問題，空泛的談論「什麼學習演算法更好」，毫無意義。

〖二、難點分析〗

P5 假設空間的規模問題

1. 某一屬性值無論取什麼都合適，我們用通配符「*」來表示。

2. 世界上沒有，我們用「?」來表示。

書中例子為西瓜，為判斷西瓜的好壞，其屬性有三種，即：色澤、根蒂、敲聲。

這三種屬性分別有3、3、3種可能取值，但假設空間的規模卻是4×4×4+1=65。

這是因為，在假設空間中，屬性的「無論取什麼屬性值都合適」也是一種屬性值，而不是作為單一屬性的3種可能取值的集合存在。

因為假設空間是機器學習中可能的函數構成的空間，「無論取什麼屬性值都合適」意味著這個函數與這一屬性無關。

例如，如果西瓜的三個屬性取值都是「無論取什麼屬性值都合適」，那麼無論什麼瓜，都是好瓜。而不是3×3×3=27個種類的瓜的集合，並不需要依次判斷，需要的判斷僅僅是——它是瓜。

所以其假設空間為：

{青綠，烏黑，淺白，*}×{蜷縮，稍蜷，硬挺，*}×{濁響，清脆，沉悶，*}+1（沒有「好瓜」的定義）=65

〖三、習題探討〗

1.1 表1.1中若只包含編號為1和4的兩個樣例，試給出相應的版本空間。

解：

如表1.1所示，好瓜和非好瓜的三個屬性的屬性值均不相同，故與訓練集一致的假設集合即版本空間如下圖所示：

圖1.1 版本空間

其取值則共有七種，其合取式為：

（色澤＝青綠）∧（根蒂＝ ? ）∧（敲聲＝ ? ）

（色澤＝ ? ）∧（根蒂＝蜷縮）∧（敲聲＝ ? ）

（色澤＝ ? ）∧（根蒂＝ ? ）∧（敲聲＝濁響）

（色澤＝青綠）∧（根蒂＝蜷縮）∧（敲聲＝ ? ）

（色澤＝青綠）∧（根蒂＝ ? ）∧（敲聲＝濁響）

（色澤＝ ? ）∧（根蒂＝蜷縮）∧（敲聲＝濁響）

（色澤＝青綠）∧（根蒂＝蜷縮）∧（敲聲＝濁響）

1.2 與使用單個合取式來進行假設表示相比，使用「析合範式」將使得假設空間具有更強的表示能力。例如：

好瓜←→（(色澤=*)∧(根蒂=蜷縮)∧(敲聲=*)）∨（(色澤=烏黑)∧(根蒂=*)∧(敲聲=沉悶)）

會把「（(色澤=青綠)∧(根蒂=蜷縮)∧(敲聲=清脆)）」以及「（(色澤=烏黑)∧(根蒂=硬挺)∧(敲聲=沉悶)）」都分類為「好瓜」。

若使用最多包含k個合取式的析合範式來表達表1.1西瓜分類問題的假設空間，試估算共有多少種可能的假設。

解：

計算此題，先要計算假設空間的規模，之前筆者一直被P5 中三種屬性的3種屬性值迷惑，以為此表也應如此計算。

但實際上，此表的色澤屬性只有：1.青綠、2.烏黑 兩種屬性值，故其規模大小為： 3×4×4+1=49種。

k的最大值為49。

使用最多包含k個合取式的析合範式有如下多種可能：

p.s.很多博主都分別討論了是否存在冗餘的兩種情況，筆者則認為冗餘由於分析的步驟不同而不存在。

1.3 若數據包含雜訊，則假設空間中有可能不存在與所有訓練樣本都一致的假設。在此情形下，試設計一種歸納偏好用於假設選擇。

解：

歸納偏好：在訓練過程中選擇滿足最多樣本的假設。

1.4 本章1.4節在論述「沒有免費的午餐」定理時，默認使用了「分類錯誤率」作為性能度量來對分類器進行評估。若換用其他性能度量l,試證明沒有免費的午餐」定理仍成立。

解：

考慮二分類問題，NFL首先要保證真是目標函數f均勻分布，對於有X個樣本的二分類問題，顯然f共有2X種情況。其中一半是與假設一致的，也就 P(f(x)=h(x))=0.5。 此時， ∑fl(h(x),f(x))=0.5?2X?(l(h(x)=f(x))+l(h(x)≠f(x))) l(h(x)=f(x))+l(h(x)≠f(x))應該是個常數，隱含的條件就該是(一個比較合理的充分條件) l(0,0)=l(1,1),l(1,0)=l(0,1)。如果不滿足， NFL 應該就不成立了(或者不那麼容易證明)。

西瓜書系列合集：

【西瓜書】周志華《機器學習》學習筆記與習題探討（一）

【西瓜書】周志華《機器學習》學習筆記與習題探討（一）續

【西瓜書】周志華《機器學習》學習筆記與習題探討（二）①

【西瓜書】周志華《機器學習》學習筆記與習題探討（二）②

推薦閱讀：