《機器學(xué)習(xí)（周志華）》學(xué)習(xí)筆記（一）

Q：什么是機器學(xué)習(xí)？

機器學(xué)習(xí)最初被定義為“不顯式編程地賦予計算機能力的研究領(lǐng)域”。很明顯，這里的“機器”是指計算機。通常我們給計算機編程都會使用if-else這些流程控制：

if(今天是周末）{
  在家睡覺
}
else{
  好好工作
}

這就是直接地、明顯地（顯式地）告訴了計算機什么時候應(yīng)該做什么。

機器學(xué)習(xí)則不是直接告訴計算機什么時候做什么，而是提供一些案例（訓(xùn)練數(shù)據(jù)），讓計算機通過案例自己學(xué)習(xí)，自己摸索什么時候應(yīng)該做什么。一個著名的例子是給計算機輸入一大堆“房價-房屋面積”數(shù)據(jù)，讓計算機自己發(fā)現(xiàn)房價和房屋面積的規(guī)律，然后我們輸入一個新的房屋面積數(shù)據(jù)，計算機就可以根據(jù)學(xué)習(xí)到的規(guī)律輸出相應(yīng)的房價。

機器學(xué)習(xí)的根本任務(wù)是預(yù)測。

“機器學(xué)習(xí)”同時也是一門學(xué)科，研究怎樣使得計算機更好地學(xué)習(xí)，亦即，是一門研究“學(xué)習(xí)算法”的學(xué)科，主要任務(wù)是評估“學(xué)習(xí)算法”的好壞以及開發(fā)新的“學(xué)習(xí)算法”。這里的“學(xué)習(xí)算法”是計算機的學(xué)習(xí)方法，本質(zhì)上是一種基于現(xiàn)有的數(shù)據(jù)產(chǎn)生預(yù)測模型的算法。

Q：學(xué)習(xí)一門學(xué)科需要先掌握其基本概念，“機器學(xué)習(xí)”領(lǐng)域有哪些需要掌握的重要概念？

人類觀察事物時，是通過觀察事物的本質(zhì)特征來認(rèn)識事物的。比如觀察西瓜，會觀察西瓜的色澤、根蒂、敲聲等特征。假設(shè)我們收集了一批關(guān)于西瓜的數(shù)據(jù)：

(色澤=青綠；根蒂=蜷縮；敲聲=濁響）
(色澤=墨綠；根蒂=稍蜷；敲聲=沉悶）
(色澤=淺白；根蒂=硬挺；敲聲=清脆）
······

假設(shè)我們希望用這一批數(shù)據(jù)來讓計算機學(xué)習(xí)
1、樣本、示例、記錄——這批數(shù)據(jù)里的每對括號。
2、數(shù)據(jù)集——這組樣本（示例、記錄）的集合。
3、特征、屬性——色澤、根蒂、敲聲等反映一個事物的本質(zhì)的可觀察方面。
4、屬性值——青旅、墨綠、蜷縮、濁響等，是屬性的取值。
5、屬性空間、樣本空間、輸入空間——屬性張成的空間。這似乎是線性代數(shù)的語言，亦即把屬性當(dāng)作坐標(biāo)軸，形成一個空間，那么樣本就是這個空間中一個個的點。例如，吧“色澤”、“根蒂”、“敲聲”作為坐標(biāo)軸，則長生了一個三維空間，每個西瓜都是這個空間里的一個點。
6、維數(shù)——樣本空間的坐標(biāo)軸數(shù)，也就是數(shù)據(jù)集的特征數(shù)量。本例中的維數(shù)是3。
7、假設(shè)——也稱假設(shè)函數(shù)，指計算機通過學(xué)習(xí)后得到的一個函數(shù)（預(yù)測模型）。
8、標(biāo)記——關(guān)于樣本結(jié)果的信息，比如一個(色澤=青綠；根蒂=蜷縮；敲聲=濁響）的西瓜是好瓜，那么“好瓜”就是(色澤=青綠；根蒂=蜷縮；敲聲=濁響）這個樣本的標(biāo)記。
9、樣例——帶有標(biāo)記的樣本，比如（(色澤=青綠；根蒂=蜷縮；敲聲=濁響），好瓜）
10、標(biāo)記空間、輸出空間——所有標(biāo)記的集合。本例中就是指｛好瓜、壞瓜｝。
11、泛化——如果用某個數(shù)據(jù)集的樣本訓(xùn)練出的一個模型（假設(shè)函數(shù)），能夠適用于新的樣本數(shù)據(jù)，就說這個模型具有泛化能力。模型能適用于越多的新數(shù)據(jù)，則說明其泛化能力越強。

Q：《機器學(xué)習(xí)》為“假設(shè)空間”這個概念另起一節(jié)說明，那么什么是“假設(shè)空間”？

“假設(shè)空間”里的“假設(shè)”指的是假設(shè)函數(shù)，也就是機器學(xué)習(xí)的成果。例如我們做分類學(xué)習(xí)，那么通過數(shù)據(jù)訓(xùn)練后得到的分類模型就是我們得到的假設(shè)。

假設(shè)空間是指所有可能假設(shè)組成的空間。也可以說是所有在表達(dá)形式上符合任務(wù)要求的假設(shè)函數(shù)的集合。

對于西瓜分類任務(wù)，我們要獲得的假設(shè)函數(shù)的形式是

好瓜→（色澤=*）^（根蒂=*）^（敲聲=*）

假設(shè)“色澤”、“根蒂”、“敲聲”3個特征都有3種可能取值，那就有444+1=65種可能假設(shè)，亦即假設(shè)空間的大小為65。
對于根據(jù)房屋大小預(yù)測房價的問題，我們要后的的假設(shè)函數(shù)的形式則是

y = a*x + b

這個問題的假設(shè)空間是無窮大。

因此，學(xué)習(xí)過程可以看作在假設(shè)空間中尋找符合訓(xùn)練數(shù)據(jù)集的假設(shè)的過程。

Q：什么是“歸納偏好”？

A：
在西瓜分類問題中，可能由于數(shù)據(jù)集的原因，我們會得到多個符合數(shù)據(jù)集的假設(shè)函數(shù)，比如：

好瓜→（色澤=墨綠）^（根蒂=蜷縮）^（敲聲=沉悶）
好瓜→（色澤=青綠）^（根蒂=*）^（敲聲=沉悶）

這所有訓(xùn)練后得到的假設(shè)組成的空間稱為“版本空間”。

那么版本空間中哪一個假設(shè) 比較好？
如果我們認(rèn)為越精細(xì)越好，則選擇

好瓜→（色澤=墨綠）^（根蒂=蜷縮）^（敲聲=沉悶）

如果我們認(rèn)為越粗略越好，則選擇

好瓜→（色澤=青綠）^（根蒂=*）^（敲聲=沉悶）

像上面那樣，計算機的學(xué)習(xí)算法基于某種偏好認(rèn)為某個假設(shè)比其他假設(shè)好，那么我們說這個學(xué)習(xí)算法有“歸納偏好”。事實上所有“學(xué)習(xí)算法”都有歸納偏好，而且一般來說會偏好那些形式簡單的假設(shè)。

Q：什么是NFL定理？其推導(dǎo)如何？

A：
NFL（No Free Lunch）定理，翻譯過來就是“沒有免費午餐”定理，收的是在機器學(xué)習(xí)中，沒有給定具體問題的情況下，或者說面對的是所有問題的情況下，沒有一種算法能說得上比另一種算法好。換成我們的俗話講，就是“不存在放之四海而皆準(zhǔn)的方法”。只有在給定某一問題，比如說給“用特定的數(shù)據(jù)集給西瓜進(jìn)行分類”，才能分析并指出某一算法比另一算法好。這就要求我們具體問題具體分析，而不能指望找到某個算法后，就一直指望著這個“萬能”的算法。這大概也是no free lunch名字的由來吧。

這個定理怎么得出的？西瓜書里有這樣一段文字：


似乎說的是我？

好吧，仔細(xì)讀一下推導(dǎo)過程，其實不難，連我這種數(shù)學(xué)渣渣都能讀懂絕大部分。只要別被一長串推導(dǎo)嚇到就行。

首先，定理推導(dǎo)的思路是證明對于某個算法a，它在訓(xùn)練集以外的所有樣本的誤差，與a本身無關(guān)。

讓我們一步一步來探索。

首先，誤差是怎樣表示，或者說怎樣計算出來的？簡單起見，只考慮二分類問題。那么誤差就是分類器錯判的個數(shù)與樣本總數(shù)的比

E=誤判數(shù)/總數(shù)。

其次我們要明確，一個算法，會產(chǎn)生很多不同的假設(shè)。更詳細(xì)得說，一個算法的結(jié)果就是一個函數(shù)h，但是h的參數(shù)不同，那么就會有h1，h2等不同的假設(shè)函數(shù)。最典型的是h=kx+b。只要參數(shù)k、b不同，那么函數(shù)h就不同了。

那么，對于某個算法a，它在訓(xùn)練集以外的所有樣本的誤差，就是它所能產(chǎn)生的所有假設(shè)h，在訓(xùn)練集以外的所有樣本上的誤判率的和。

對于某個假設(shè)h，“h在某個數(shù)據(jù)集上的誤差”與“在某個數(shù)據(jù)集中抽取一個能讓h誤判的樣本的概率”是等價的問題。設(shè)P(x)為“在某個數(shù)據(jù)集中抽取一個能讓h誤判的樣本的概率”，那就可以用P(x)來替代h的誤差。

綜上所述，對于某個算法a，它在訓(xùn)練集以外的所有樣本的誤差就可以這樣表示：


某個算法a，它在訓(xùn)練集以外的所有樣本的誤差

對于二分類問題，設(shè)f為真正的分類函數(shù)，可能f有多個。假設(shè)其均勻分布，那么對于某個算法a，它在訓(xùn)練集以外的所有樣本的誤差就可以表示成：


二分類問題中算法a在訓(xùn)練集外所有樣本的誤差

由乘法分配率可以化為
Paste_Image.png

又由于


Paste_Image.png

上式中最后意象可以被化簡：
Paste_Image.png

又由全概率公式，或者說概率的可列可加性，下面這一項（上式中間那一項）其實等于1
這一塊其實等于1，所有h的概率加起來嘛

如此一來，a就在公式中消失了，于是最后的結(jié)果就是
與a無關(guān)

所以說無論是什么算法，它在訓(xùn)練集以外所有樣本上的誤差都是上式表示的結(jié)果。

這就是NFL定理的推導(dǎo)。

這篇文章發(fā)表的五年里，大多數(shù)的評論都是圍繞NFL的。五年前我對機器學(xué)習(xí)和NFL都知之甚少?，F(xiàn)在我有了更多理解，便嘗試一下再解釋解釋周志華老師這個簡單版的論證。

我們對于數(shù)學(xué)的恐懼，在理解數(shù)學(xué)內(nèi)容時感到困難，原因大多是我們沒有搞清楚數(shù)學(xué)符號對應(yīng)的意思。我們往往都是匆匆掃一眼對于符號的定義，然后就忙不迭地透入公式之中。但是，連基本地單詞都沒掌握，怎么能指望理解一句話地內(nèi)容呢？所以首先我們解釋清楚上面所用到的數(shù)學(xué)符號的含義。

  • \mathcal{X}是樣本空間，指的就是所有可能的樣本組成的集合。比如說我們要判斷一批西瓜中的好瓜壞瓜，那么這一批西瓜就是樣本空間。假設(shè)這一批西瓜有1000個，那么|\mathcal{X}|就是樣本空間的規(guī)模，也就是所有可能西瓜的數(shù)量，1000。
  • X則是我們所有用的訓(xùn)練集，x代表其中的一個訓(xùn)練樣本。比如我們從這批1000個西瓜中采樣50個來做分析，那這50個西瓜就是訓(xùn)練集。
  • h代表使用學(xué)習(xí)算法在訓(xùn)練集中學(xué)習(xí)出來的假設(shè)。在我們這個例子中也就是一個判別函數(shù)，用來判斷一個樣本的類別h: \mathcal{X} \rightarrow \{0,1\}。使用這個判別函數(shù)h，輸入某個西瓜的特征信息，就這個函數(shù)就會告訴我們這個瓜是好是壞。我們用f來代表真正的判別函數(shù)。
  • \mathfrak{L}代表一個訓(xùn)練算法，比如\mathfrak{L}_{a}可能代表邏輯回歸，\mathfrak{L}_可能代表決策樹。我們可以把\mathfrak{L}也看作一個函數(shù)，輸入是一個訓(xùn)練集，輸出是一個判別函數(shù)\mathfrak{L}: \mathcal{X} \rightarrow H。這里H是指假設(shè)空間，也就是所有可能的判別函數(shù)的集合。
  • 前文已經(jīng)說過，在假設(shè)空間H中，可以有多個假設(shè)h_1, h_2,..符合同一個訓(xùn)練集X，那么學(xué)習(xí)算法\mathfrak{L}應(yīng)該挑選哪一個假設(shè)呢？我們目前不知道，但可以假設(shè)某個算法\mathfrak{L}和某個數(shù)據(jù)集X，它挑選某個假設(shè)h的概率是P(h|X,\mathfrak{L}).

對于某個算法\mathfrak{L}_a，設(shè)它在訓(xùn)練集以外的所有樣本，也就是剩下的950個瓜x \in \mathcal{X} - X 的期望誤差(Expected Out of Training Error)為E_{ote}(\mathfrak{L}_a|X, f)。按照數(shù)學(xué)期望的定義，它可以表達(dá)成：
E_{ote}(\mathfrak{L}_a|X, f) = \sum_{h\in \mathfrak{L}(X)} P(h|X, \mathfrak{L}_a)E_{ote}(h|X, \mathfrak{L}_a)

其中P(h|X, \mathfrak{L}_a)是指學(xué)習(xí)算法\mathfrak{L}_a根據(jù)給定的訓(xùn)練集X，選擇了假設(shè)h的概率；而E_{ote}(h|X, \mathfrak{L}_a)是指假設(shè)h在訓(xùn)練集以外的所有樣本的期望誤差。再次按照數(shù)學(xué)期望的定義，它可以表達(dá)成：
E_{ote}(h|X, \mathfrak{L}_a) = \sum_{x \in \mathcal{X} - X}P(x)\mathbb{I}\big(f(x) \neq h(x)\big)

其中\mathbb{I}(b) 是一個輔助函數(shù)，用來表示x是不是被誤判了，定義為
\mathbb{I}(b) \left\{ \begin{aligned} &0 \quad b=True \\ &1 \quad b=False \\ \end{aligned} \right .

那么整個E_{ote}(\mathfrak{L}_a|X, f)的定義就可以寫成
E_{ote}(\mathfrak{L}_a|X, f) = \sum_{h\in \mathfrak{L}(X)} P(h|X, \mathfrak{L}_a) \sum_{x \in \mathcal{X} - X}P(x)\mathbb{I}\big(f(x) \neq h(x)\big)

學(xué)習(xí)算法生成的假設(shè)h可能有多個，真判別函數(shù)f也可能有多個。于是我們對所有可能的f的誤差求和：
\sum_f E_{ote}(\mathfrak{L}_a|X, f) = \sum_f \sum_{h\in \mathfrak{L}(X)} P(h|X, \mathfrak{L}_a) \sum_{x \in \mathcal{X} - X}P(x)\mathbb{I}\big(f(x) \neq h(x)\big)

由乘法分配率可以化為
\sum_f E_{ote}(\mathfrak{L}_a|X, f) = \sum_{h\in \mathfrak{L}(X)} P(h|X, \mathfrak{L}_a) \sum_{x \in \mathcal{X} - X} P(x) \sum_f \mathbb{I}\big(f(x) \neq h(x)\big)

怎樣化簡上式的最后一項\sum_f \mathbb{I}\big(f(x) \neq h(x)\big)呢？我們不知道真正的判別函數(shù)f是怎樣的，只知道它存在于假設(shè)空間H中，那我們姑且認(rèn)為每一個假設(shè)h是真判別函數(shù)f的概率相等，也就是假設(shè)f在空間H中的概率是均勻分布。若f在H中均勻分布，則有一半f對x的預(yù)測是0，另一半的預(yù)測是1。無論如何，對于一個給定的h，總有一半f對x的預(yù)測與h不一致，也就是說\sum_f \mathbb{I}\big(f(x) \neq h(x)\big)=\frac{|H|}{2}，也就是說：
\begin{aligned} \sum_f E_{ote}(\mathfrak{L}_a|X, f) &= \sum_{h\in \mathfrak{L}(X)} P(h|X, \mathfrak{L}_a) \sum_{x \in \mathcal{X} - X} P(x) \frac{1}{2}|H| \\ &=\frac{1}{2}|H| \sum_{h\in \mathfrak{L}(X)} P(h|X, \mathfrak{L}_a) \sum_{x \in \mathcal{X} - X} P(x) \\ &=\frac{1}{2}|H| \sum_{x \in \mathcal{X} - X} P(x) \sum_{h\in \mathfrak{L}(X)} P(h|X, \mathfrak{L}_a) \\ &=\frac{1}{2}|H| \sum_{x \in \mathcal{X} - X} P(x) \end{aligned}
到了這一步，我們已經(jīng)可以看出，學(xué)習(xí)算法(\mathfrak{L}_a在訓(xùn)練集外的總誤差與(\mathfrak{L}_a自身無關(guān)，無論它是邏輯回歸，還是決策樹，還是別的什么，理論上其訓(xùn)練集外的總誤差都是\frac{1}{2} |H| \sum_{x \in \mathcal{X} - X} P(x).

最后提一嘴，|H|是指假設(shè)空間的規(guī)模，也就是所有可能的判別函數(shù)h的數(shù)量。那么，一共可能有多少個h呢？一個h要做的事情是給樣本空間里的樣本打上0或1的標(biāo)簽，有多少種打標(biāo)簽的組合，相當(dāng)于問1000個西瓜中每個西瓜都可能是好瓜壞瓜，那么1000個西瓜一共有多少種可能的好壞組合？答案是2^{1000}種。所以理論上其訓(xùn)練集外的總誤差都是
\sum_f E_{ote}(\mathfrak{L}_a|X, f) = 2^{|\mathcal{X}|-1} \sum_{x \in \mathcal{X} - X} P(x)

好家伙，我自己寫完，看到這么多符號，也下了一跳。擔(dān)心細(xì)一看每一步都不難，其實都是高中數(shù)學(xué)而已。

本作品首發(fā)于簡書 和 博客園平臺，采用知識共享署名 4.0 國際許可協(xié)議進(jìn)行許可。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容