一些零碎的知識(shí)點(diǎn)

1、歸納與演繹

2、歸納學(xué)習(xí)：廣義的歸納學(xué)習(xí)是指從樣例中學(xué)習(xí)；狹義的歸納學(xué)習(xí)是指從樣例數(shù)據(jù)中習(xí)得概念，因此也稱概念學(xué)習(xí)。

3、布爾概念學(xué)習(xí)：也是一種歸納學(xué)習(xí)，即從所有訓(xùn)練數(shù)據(jù)的輸入和布爾輸出結(jié)果之間的關(guān)系中，推斷出布爾函數(shù)的所有可能。（黑箱模型）

什么是假設(shè)空間

? ? ? ? 假設(shè)空間就是從樣本空間中歸納所有樣本構(gòu)成的假設(shè)集合。通過樣本數(shù)據(jù)中每個(gè)特征的屬性值個(gè)數(shù)，可以構(gòu)造出假設(shè)空間的大小和規(guī)模。

? ? ? ? 在歸納學(xué)習(xí)中，學(xué)習(xí)的過程可以看做在一個(gè)所有假設(shè)組成的空間進(jìn)行探索的過程，找到所有可以將訓(xùn)練集中的數(shù)據(jù)正確判斷的假設(shè)的集合。最終獲得一個(gè)和訓(xùn)練值一直的假設(shè)的集合，即成為該數(shù)據(jù)集的版本空間。

歸納偏好

? ? ? ?根據(jù)訓(xùn)練集可以從假設(shè)空間中最終得到一個(gè)適合訓(xùn)練集的多個(gè)假設(shè)，但是當(dāng)一個(gè)新的數(shù)據(jù)需要進(jìn)行預(yù)測(cè)時(shí)，選擇不同的假設(shè)進(jìn)行預(yù)測(cè)得到的結(jié)果會(huì)是不一樣的(此處獲得的不同假設(shè)可以看做不同的模型)。那么歸納偏好則會(huì)決定，我們?cè)诎姹究臻g中應(yīng)該選擇哪一個(gè)假設(shè)。

? ? ? ?歸納偏好可以認(rèn)為學(xué)習(xí)算法自身在一個(gè)非常龐大的假設(shè)空間中對(duì)假設(shè)進(jìn)行選擇的啟發(fā)式價(jià)值觀。歸納偏好的最終結(jié)果，就是算法自身找到一個(gè)可以滿足所有訓(xùn)練集的假設(shè)，并且對(duì)于訓(xùn)練集之外的數(shù)據(jù)，也可以做到較好的預(yù)測(cè)。

偏好選擇原則

? ? ? ? 需要有理論上的指導(dǎo)，來指導(dǎo)算法從龐大的假設(shè)空間之中找到最適合的偏好。? ?

奧卡姆剃刀原則

? ? ? ? ?奧卡姆剃刀定義

? ? ? ? ?在機(jī)器學(xué)習(xí)領(lǐng)域，奧卡姆剃刀原則就是在多個(gè)滿足訓(xùn)練集的假設(shè)空間中，找到最簡(jiǎn)單的那一個(gè)，對(duì)于一些簡(jiǎn)單的場(chǎng)景，奧卡姆剃刀原則可以找到相應(yīng)的假設(shè)，對(duì)于比較復(fù)雜的場(chǎng)景，則會(huì)面臨另外一個(gè)問題：在多個(gè)假設(shè)之間，如何判定哪一個(gè)假設(shè)更簡(jiǎn)單。

NFL（No Free Lunch）定理

? ? ? ?可以通過訓(xùn)練集外的樣本在不同假設(shè)上的誤差，來決定兩個(gè)假設(shè)之間的性能好壞，那么在同一個(gè)樣本空間χ和一個(gè)假設(shè)空間H，P(h|X,ζa)代表算法ζa在樣本空間X中，產(chǎn)生假設(shè)h的概率。令f(x)代表真實(shí)的目標(biāo)函數(shù)，那么算法ζa在訓(xùn)練集外（χ-X）的誤差的誤差的期望值為：

算法ζa在訓(xùn)練集外（χ-X）的誤差的誤差的期望值

? ? ? ? 其中，Ⅱ(h(x)≠f(x))為指示函數(shù)，當(dāng)對(duì)樣本x預(yù)測(cè)失敗時(shí)，值為1。P(x)為遇到樣本x的概率。以上為使用同一種假設(shè)造成的誤差期望，對(duì)于假設(shè)空間中所有可能的假設(shè)，都有可能選中，概率為P(h|X,ζa)，那么對(duì)于所有的假設(shè)空間，誤差的期望值為：

（1,1即為在所有假設(shè)上算法的誤差期望）

? ? ? 這里假設(shè)在整個(gè)函數(shù)空間中，所有可能的目標(biāo)函數(shù)f是均勻分布的（即所有真實(shí)的問題是均勻出現(xiàn)的），對(duì)所有可能的f(x)，按照均勻分布對(duì)誤差求和：

對(duì)于所有f進(jìn)行誤差求和

? ? ?推導(dǎo)得出：

中間結(jié)果

? ? ?對(duì)于

? ? ?由于f是均勻分布的，同一個(gè)數(shù)據(jù)可能滿足f(x)也可能不滿足。而且數(shù)據(jù)也是獨(dú)立同分布的，因此h(x)≠f(x)的概率為1/2，在整個(gè)樣本空間中的預(yù)測(cè)結(jié)果即為：

? ? ?所以，對(duì)于均勻分布對(duì)誤差求和的結(jié)果：

容易得出：

誤差的期望與算法本身無關(guān)

但是，得出這一結(jié)論的前提，是所有的樣本數(shù)據(jù)遵從獨(dú)立同分布原則，所有問題出現(xiàn)的概率相同。并且在實(shí)際中f(x)也是同等概率出現(xiàn)的。但是實(shí)際并不是這樣，我們只關(guān)系我們所要解決的問題，只是為了解決明確的需求來獲得最佳的方案

NFL定理只是讓我們認(rèn)識(shí)到：脫離具體問題來討論算法的優(yōu)劣，是沒有意義的。學(xué)習(xí)算法的歸納偏好是否與需求匹配，是最重要的。