[Learning-from-data]無限假設(shè)空間的可學(xué)性以及模型泛化

Theory of Generalization

樣本外誤差 $E_{out}$ 測量了訓(xùn)練集D上學(xué)習(xí)的模型在unseen data上的泛化能力. $E_{out}$ 是基于整個輸入空間X上的表現(xiàn)來測量的.如果使用樣本集來計算模型的 $E_{out}$ ,這些樣本點必須是"unseen",沒有在訓(xùn)練集中出現(xiàn)過.

對應(yīng)的,樣本內(nèi)誤差 $E_{in}$ 是基于訓(xùn)練集中的樣本點,它評估模型在訓(xùn)練集上的表現(xiàn).

Generalization error泛化誤差. 泛化是學(xué)習(xí)中的一個關(guān)鍵問題.Generalization is a key issue in learning.泛化誤差可以定義為 $E_{in}$ 和 $E_{out}$ 兩者之間的差異.Hoeffding不等式提供了一個泛化誤差概率邊界的描述.

$P[| E_{in}(g)-E_{out}(g)| > \epsilon] \leq 2Me^{-2\epsilon^2 N}$ for any $\epsilon > 0$ .

同時可以知道, $|E_{in}(g)-E_{out}(g)| \leq \epsilon$ 的概率為 $1-2Me^{-2N\epsilon^2$ ,也就是說 $E_{out}(g) \leq E_{in}(g) + \epsilon$ ,選定一個tolerance $\delta$ ,所以 $\delta = 2Me^{-2N\epsilon^2}$ , $\epsilon = \sqrt{\frac1{2N} ln\frac{2M}{\delta}}$ ,最終,

$E_{out}(g) \leq E_{in}(g) + \sqrt{\frac1{2N} ln\frac{2M}{\delta}}$ .

這個不等式提供了一個泛化邊界.

$|E_{in}-E_{out}| \leq \epsilon$ ,同時也保證對于所有的 $h \in H$ 來說, $E_{out} \geq E_{in} - \epsilon$ .對于最終的假設(shè)函數(shù)g既想讓它在unseen data上表現(xiàn)良好,又想它是在所有假設(shè)集中做的最好的(H中不存在其他假設(shè)函數(shù).使得 $E_{out}(h)$ 比 $E_{out}(g)$ 要好.). $E_{out}(h) \geq E_{in}(h) + \epsilon$ 這個邊界確保不能做的更好了,因為選擇的其他假設(shè)h對應(yīng) $E_{in}$ 都比g要大,因此對應(yīng)的 $E_{out}$ 也要比g要大,樣本外表現(xiàn)相對變差.

誤差邊界 $\sqrt{\frac1{2N} ln\frac{2M}{\delta}}$ 依賴于假設(shè)空間H的大小M.如果H是無限集合,那么這個邊界就沒有意義了(邊界趨向于無限大).不幸的是,實際情況下大多數(shù)學(xué)習(xí)模型都是無限集合.

為了在無限集合H上繼續(xù)討論模型的泛化能力,我們需要對上面的式子做一些變形,想用有限的數(shù)量去代替M,這樣邊界就有意義了.

之前右邊界M對應(yīng):

[圖片上傳失敗...(image-d114c1-1544952000340)]

確保最終選擇的函數(shù)g: $|E_{in}(g)-E_{out}(g)| > \epsilon$ ,因為g是H中的一個假設(shè).將 $\beta_m$ 代表事件" $|E_{in}(h_m)-E_{out}(h_m)| > \epsilon$ ",因此,對應(yīng)不等式變?yōu)?

[圖片上傳失敗...(image-61202c-1544952000340)]

但是如果各個事件之間相互重疊,那么右邊界就變得比實際上大得多.比如有3個假設(shè),不同事件的面積代表對應(yīng)的事件發(fā)生的概率, $\beta_1,beta_2,beta_3$ 三個事件的聯(lián)合邊界比3個事件對應(yīng)面積小得多,盡管面積和的邊界是正確的.由此推導(dǎo),假設(shè)空間中如果有假設(shè)函數(shù)相差不多,就會造成大量的重疊,導(dǎo)致右邊界比實際值大得多(放得太多!).我們需要想辦法將對應(yīng)的假設(shè)劃分開來(歸類,分成不同的類別),從而將無限的假設(shè)集變成有限的假設(shè)集.

[圖片上傳失敗...(image-8599d6-1544952000340)]

Effective Number of Hypotheses假設(shè)空間的有效數(shù)量

介紹一個概念growth function增長函數(shù)--定義假設(shè)空間的有效數(shù)量.我們用growth function來代替上面不等式中的M,growth function是一個組合量,能度量假設(shè)空間H中假設(shè)函數(shù)之間的差異,也就是圖中不同假設(shè)之間的重疊面積的大小.

對于一個2分類的目標(biāo)函數(shù),每個 $h \in H$ 將輸入空間X映射到{-1,1}上.growth function的定義是基于假設(shè)空間H中不同假設(shè)函數(shù)的數(shù)目,而且是基于有限的樣本點,而不是整個輸入空間X.
一個假設(shè)函數(shù) $h \in H$ 應(yīng)用到有限樣本集上 $x_1,x_2,...,x_N \in X$ ,可以得到一個二分類的N元組 $h(x_1), h(x_2),...,h(x_N)$ .N元組將N個樣本集分為兩類:正類,負(fù)類,這個N元組叫做dichotomy(二分)---對數(shù)據(jù)點一次結(jié)果劃分.每個 $h \in H$ 在N個數(shù)據(jù)點上都會產(chǎn)生一個dichotomy,但是不同的假設(shè)函數(shù)產(chǎn)生的dichotomy可能完全相同.

定義一 $x_1,x_2,...,x_N \in X$ ,在N個數(shù)據(jù)點上,假設(shè)空間H產(chǎn)生的dichotomies定義為:

$H(x_1,x_2,...,x_N) = \{(h(x_1),h(x_2),...,h(x_N))|h \in H\}$ .

H(x_1,x_2,...,x_N)空間是假設(shè)空間H中每個假設(shè)函數(shù)對N個數(shù)據(jù)點劃分產(chǎn)生的dichotomy的集合空間.一個大的H(x_1,x_2,...,x_N)意味著假設(shè)空間更加多種多樣--在N個數(shù)據(jù)點上產(chǎn)生的dichotomy更多.growth function基于dichotomies的數(shù)目.

定義二 假設(shè)空間H上的growth function定義為:

$m_H(N) = max_{x_1,x_2,...,x_N \in X}|H(x_1,x_2,...,x_N)|$

其中|\cdot|表示集合中元素的數(shù)目. $m_H(N)$ 表示在任意N個數(shù)據(jù)點假設(shè)空間H可以生成的不同dichotomies的最大數(shù)目.為了比較 $m_H(N)$ ,我們需要考慮輸入空間X中N個數(shù)據(jù)點的所有可能,然后選擇能產(chǎn)生最多dichotomies的數(shù)據(jù)點集.和M類似, $m_H(N)$ 是假設(shè)空間H中假設(shè)函數(shù)數(shù)目的一種度量,不同之處在于每個假設(shè)是在N個輸入點上進(jìn)行衡量,而不是整個輸入空間X.對于任意假設(shè)空間H,因為 $H(x_1,x_2,...,x_N) \subseteq \{-1,+1\}^N$ , $m_H(N)$ 最大值為:
$m_H(N) \leq 2^N$ .

如果H能夠生成N個數(shù)據(jù)點上所有的可能的類別分布,也就是說 $H(x_1,x_2,...,x_N) = \{-1,+1\}^N$ ,稱假設(shè)空間H能shatter(打碎)N個數(shù)據(jù)點[能覆蓋N個數(shù)據(jù)所有可能的分類集合].

[圖片上傳失敗...(image-b7c812-1544952000340)]

圖中可以看到, $m_H(N)$ 是N個數(shù)據(jù)點產(chǎn)生不同dichotomies的最大值,(a)圖中3點共線時有種情況使用感知機(jī)模型不能劃分,但是(b)圖中3個點可能產(chǎn)生的dichotomies都可以實現(xiàn),所以 $m_H(3)=8$ ,(c)圖中的dichotomy不同通過感知機(jī)生成,所以 $m_H(4)=14$ ,而不是16.同時可以知道隨著假設(shè)空間H變得復(fù)雜, $m_H(N)$ 也逐漸增大--這符合我們的期望.

計算每個假設(shè)空間上的增長函數(shù) $m_H(N)$ 并不實際,而且也沒有必要,因為我們使用增長函數(shù) $m_H(N)$ 來代替不等式中的M,我們可以計算增長函數(shù) $m_H(N)$ 的上界,而不是計算增長函數(shù) $m_H(N)$ 的確定值,使用增長函數(shù)的上界用在不等式中也成立.

定義三 對于假設(shè)空間H,如果k個點組成的輸入集不能被假設(shè)空間shatter(打碎),那么k定義為假設(shè)空間H的break point.

如果k是break point,那么 $m_H(k) < 2^k$ . 通常情況下,計算假設(shè)空間H的break point比計算假設(shè)空間的增長函數(shù)要容易得多.

[圖片上傳失敗...(image-6cd212-1544952000340)]
如果數(shù)據(jù)點超過k,假設(shè)空間更不可能對其shatter,break point更像是對輸入情況的一種界限.

我們使用break point k來導(dǎo)出對任意N的增長函數(shù) $m_H(N)$ 的一個邊界.比如2維感知機(jī)不能把4個點shatter,這個知識對于當(dāng)輸入點是5或更多時,對感知機(jī)能產(chǎn)生的dichotomies能有一個限制.接下來,討論 $m_H(N)$ 的邊界是什么.

Bounding the Growth Function增長函數(shù)的邊界

關(guān)于增長函數(shù)而言,如果 $m_H(N) = 2^N$ 在某個點被打破,那么 $m_H(N)$ 對于任意值N可以通過這個break point用一個簡單的多項式確定邊界.如果不存在break point,對于所有N而言, $m_H(N) = 2^N$ 總是成立的.如果用 $m_H(N)$ 來代替不等式中的Ｍ傅事，那么 $\sqrt{\frac1{2N}ln\frac{2M}{\delta}}$ 泛化誤差邊界無論訓(xùn)練樣本N取多大都不可能趨于零( $m_H(N) = 2^N$ );但是如果 $m_H(N)$ 可以用一個多項式來代替,那么當(dāng)訓(xùn)練樣本數(shù) $N \to \infty$ ,泛化誤差將會趨于零,這意味著在充足樣本集下,模型的泛化結(jié)果可以非常好.

定理如果存在k,使得 $m_H(k) < 2^k$ 成立,那么,

[圖片上傳失敗...(image-3f1597-1544952000340)]

對于所有的N都成立.RHS是一個N的k-1階多項式.如果增長函數(shù)存在break point k,那么就可以使用N的多項式來確定增長函數(shù)的上界,因此可以來替換增長函數(shù).

上面定理的含義是指如果假設(shè)空間H存在一個break point,我們就可以確保模型的泛化效果, $m_H(N)$ 存在一個多項式邊界.

The VC Dimension VC維

上面的定理可以使用break point對整個增長函數(shù)growth function確定邊界.break point越小,邊界越好(越小).

VC維 假設(shè)空間H的VC維 $d_{VC}(H)$ ,簡寫為 $d_{VC}$ ,是指能被H打散的最大的示例集（數(shù)據(jù)集）的大小N,N滿足 $m_H(N)=2^N$ .如果對于所有的N,等式 $m_H(N)=2^N$ 都成立,那么 $d_{VC}= \infty$ .

如果 $d_{VC}$ 是假設(shè)空間H的VC維,那么break point $k = d_{VC}+1$ .因為根據(jù)VC維定義,VC維是假設(shè)空間H能打碎的最大樣本集,所以k就是H的break point,而且不可能存在更小的break point了,因為H可以打碎 $d_{VC}$ 個樣本點,對于更小的樣本點更不在話下.

因為 $m_H$ 的break point k滿足 $k=d_{VC}+1$ ,所以定理可以改寫為:

[圖片上傳失敗...(image-2ace23-1544952000340)]

所以,VC維是增長函數(shù) $m_H(N)$ 的多項式階數(shù).這個多項式邊界可以進(jìn)行簡化.可以用歸納法證明:

$m_H(N) \leq N^{d_{VC}} + 1$ .

這樣,增長函數(shù)growth function可以用VC維來進(jìn)行約束,接下來就是分析使用增長函數(shù) $m_H(N)$ 對M進(jìn)行替換后,泛化邊界的如何變化.使用 $m_H(N)$ 替換M后,

[圖片上傳失敗...(image-2202fc-1544952000340)]

已知增長函數(shù) $m_H(N)$ 可以被一個N的多項式約束,除非假設(shè)空間為VC維無窮大 $d_{VC}(H) = \infty$ .增長函數(shù)取對數(shù)后,呈對數(shù)級增長,然后被 $\frac1{N}$ 減小,因此,如果訓(xùn)練樣本N足夠大,那么 $E_{out}$ 會接近于 $E_{in}$ .(證明了無窮大時,可學(xué)性的第一個問題).

只有當(dāng)VC維趨于無窮大時,假設(shè)才會失效.對于任意有限的VC維來說,誤差收斂到0的速度取決于VC維的大小,因為VC維是多項式的階數(shù).VC維越小,收斂到0的速度越快.

但是僅僅用 $m_H(N)$ 來代替泛化邊界中M是不夠的,還需要進(jìn)一步調(diào)整.不過VC維在其中還扮演了非常重要的角色.可以將假設(shè)空間中假設(shè)分為兩類:good models & bad models.'Good models'指VC維有限,且樣本集N足夠大的模型,這種模型可以保證 $E_{out} \approx E_{in}$ ,樣本集的表現(xiàn)可以泛化到樣本集之外;'bad models'指VC維無窮大,對于bad models無論樣本集N取多大,我們不能基于VC維對 $E_{in}$ 和 $E_{out}$ 進(jìn)行泛化比較.

可以將VC維看做模型的"有用參數(shù)量",模型參數(shù)越多,假設(shè)空間假設(shè)函數(shù)越多,這反應(yīng)了增長函數(shù) $m_H(N)$ 的大小.比如說 $w_0,w_1,...,w_d$ 的感知機(jī)模型,VC維是d+1.對于其他模型而言,有用參數(shù)可能不太明顯.VC維能衡量有用參數(shù)或自由度,這些量可以保證模型數(shù)目的多樣性.但多樣性也不是越多越好,比如 $m_H(N) = 2^N$ 而且 $d_{VC} = \infty$ 的模型,這種情況下不能對模型進(jìn)行泛化.

The VC Generalization Bound VC泛化邊界

如果將增長函數(shù)growth function作為假設(shè)空間有效假設(shè)的一種度量量,那么使用 $m_H(N)$ 代替不等式中M后,可以得到:

[圖片上傳失敗...(image-828b45-1544952000340)]

但這個不等式證明并不是最終的形式.需要修改泛化邊界才能成立.使用下面定理,可以到處正確的邊界,叫做VC維泛化邊界.對于任意二分類目標(biāo)函數(shù)f,任意假設(shè)空間H,任意學(xué)習(xí)算法A,任意的輸入概率分布P都成立:

定理:VC泛化邊界 對于任意tolerance $\delta > 0$ ,

$E_{out}(g) \leq E_{in}(g) + \sqrt{\frac8{N}ln\frac{4m_H(2N)}{\delta}}$

成立的概率是 $1-\delta$ .

如果和上面的不等式進(jìn)行比較,可以發(fā)現(xiàn)下面不等是的邊界更大(move the bound in the weaker direction).只要VC維是有限的,誤差就會收斂于0(盡管速度變慢),因為和 $m_H(N)$ 一樣, $m_H(2N)$ 也是N的 $d_{VC}$ 階多項式.這意味著如果有足夠的數(shù)據(jù),無限假設(shè)空間H中有限VC的每個假設(shè)函數(shù)的 $E_{in}$ 能很好的泛化到 $E_{out}$ 上.其中的關(guān)鍵在于使用定義假設(shè)空間有效假設(shè)的有限增長函數(shù)來替代假設(shè)空間的真正數(shù)目,從而確定邊界.

VC維泛化邊界是機(jī)器學(xué)習(xí)理論中非常重要的一個數(shù)據(jù)結(jié)果.它證明了無限假設(shè)空間的可學(xué)性問題.
The data set D is the source of randomization in the original Hoeffding Inequality.

[圖片上傳失敗...(image-5e3e46-1544952000340)]

Interpreting the Generalization Bound 泛化邊界解釋

上面不等式是一個通用結(jié)果,可以應(yīng)用到所有的假設(shè)集,所有的學(xué)習(xí)算法,輸入空間,概率分布以及二分類目標(biāo)函數(shù)上.同時也可以擴(kuò)展到其他類型的目標(biāo)函數(shù)上.因為不等式結(jié)果的通用性,因此對于有的模型來說邊界可能過于松loose,原因在于這個相同的邊界要覆蓋到多種類型模型上.

VC維可以用作一種評估模型泛化能力的一個指標(biāo),但是相對意義上的,并不具有絕對意義.在實際問題中會采用不同的邊界.

Sample Complexity樣本復(fù)雜度

樣本復(fù)雜度是指模型達(dá)到一定的泛化能力時所需要的訓(xùn)練樣本數(shù)目N.模型的泛化表現(xiàn)可以用兩個參數(shù)衡量: $\epsilon$ 和 $\delta$ .誤差容忍度 $\epsilon$ 表示容忍的泛化誤差量,置信度參數(shù) $\delta$ 表示大于容忍泛化誤差邊界的概率.隨著 $\epsilon$ 和 $\delta$ 變小,訓(xùn)練樣本數(shù)N的變化速度表示了為達(dá)到一定泛化能力所需要的訓(xùn)練樣本數(shù).

對于給定的模型,可以用VC邊界來建立樣本復(fù)雜度.對于固定的 $\delta$ ,假定泛化誤差邊界最多是 $\epsilon$ .從不等式中可以知道,泛化誤差限制在 $\sqrt{\frac8{N}ln\frac{4m_H(2N)}{\delta}}$ ,為了確保不等式 $\sqrt{\frac8{N}ln\frac{4m_H(2N)}{\delta}} \leq \epsilon$ 成立.為了保證泛化誤差最大是 $\epsilon$ ,那么訓(xùn)練集樣本大小N:

$N \geq \frac8{\epsilon^2}ln\frac{4m_H(2N)}{\delta}$

但是這個樣本復(fù)雜度N的邊界不太明顯,因為N出現(xiàn)在不等式的兩端.如果用基于VC維的多項式代替 $m_H(2N)$ ,可以得到:

$N \geq \frac8{\epsilon^2}ln\frac{4((2N)^{d_{VC}}+1)}{\delta}$

但這個不等式同樣也是不確定的.我們可以用簡單的迭代方法計算N的數(shù)值(對N初始化一個值,然后反復(fù)計算不等式,直到N收斂).

Penalty for Model Complexity 模型復(fù)雜度懲罰

樣本復(fù)雜度是在泛化誤差邊界 $\epsilon$ 和置信度 $\delta$ 確定的情況下對訓(xùn)練樣本N的一個估計.但是在大多數(shù)實際情況中,都是給定一個固定大小的訓(xùn)練樣本集D,因此N大小是確定的.在這種情況下,對于給定N,模型在unseen data上表現(xiàn)如何是我們所關(guān)注的問題.

$E_{out}(g) \leq E_{in}(g) + \sqrt{\frac8{N}ln\frac{4m_H(2N)}{\delta}}$

如果用基于VC維的多項式代替 $m_H(2N)$ ,可以得到out-of-sample誤差的另一種邊界表示:

$E_{out}(g) \leq E_{in}(g) + \sqrt{\frac8{N}ln\frac{4((2N)^{d_{VC}}+1)}{\delta}}$

可以將 $E_{out}(g)$ 的邊界看做兩部分,第一部分是 $E_{in}(g)$ ,第二部分是隨著假設(shè)空間H的VC維而變化的量 $\Omega(N,H,\delta)$ ,所以:

$E_{out}(g) \leq E_{in}(g) + \Omega(N,H,\delta)$

其中,

$\Omega(N,H,\delta) = \sqrt{\frac8{N}ln\frac{4m_H(2N)}{\delta}} \leq \sqrt{\frac8{N}ln\frac{4((2N)^{d_{VC}}+1)}{\delta}}$

可以將 $\Omega(N,H,\delta)$ 看做是對模型復(fù)雜度的一種懲罰.當(dāng)使用更加復(fù)雜的假設(shè)空間H時(VC維增加),右邊不等式邊界增加,因此樣本外數(shù)據(jù)上的 $E_{out}(g)$ 表現(xiàn)會惡化.如果用相同的訓(xùn)練樣本去擬合一個相對簡單模型時, $E_{out}(g)$ 變現(xiàn)會更好(右邊界變小).從模型復(fù)雜度懲罰的等式來看,如果用更高的置信度(更小的 $\delta$ ),那么模型會變差;如果用更多樣本N,模型會變好.

如果用更復(fù)雜的假設(shè)空間H(更好的VC維),那么 $\Omega(N,H,\delta)$ 會變大,但用數(shù)據(jù)去擬合模型時,由于有更多的假設(shè)可以選擇, $E_{in}(g)$ 會變小.因此存在一個權(quán)衡(tradeoff):更復(fù)雜的模型可以讓樣本集模型 $E_{in}(g)$ 表現(xiàn)變好,但是 $\Omega(N,H,\delta)$ 會增加(懲罰度變大,因此 $E_{out}(g)$ 變差,泛化效果不好).最佳的模型是兩個量的組合值( $E_{out}(g)$ )能最小.

[圖片上傳失敗...(image-95f429-1544952000340)]

The Test Set 測試集

泛化邊界是基于 $E_{in}$ 的對 $E_{out}$ 的一個寬泛估計.這個估計對于訓(xùn)練過程來說是一個指導(dǎo),但如果目標(biāo)是得到一個關(guān)于 $E_{out}$ 的精準(zhǔn)預(yù)測,這個邊界作用不大.

一種可選方法是使用test set測試集對 $E_{out}$ 進(jìn)行估計,測試集中的數(shù)據(jù)并不應(yīng)用在訓(xùn)練過程中.最終的假設(shè)函數(shù)g是在測試集上進(jìn)行評估,評估結(jié)果作為 $E_{out}$ 的一個估計.

把測試集上的測試結(jié)果稱作 $E_{test}$ .當(dāng)我們用 $E_{test}$ 作為 $E_{out}$ 的一個估計時,事實上假定 $E_{test}$ 泛化效果很好,接近于 $E_{out}$ .但是, $E_{test}$ 和 $E_{in}$ 類似只是一個對樣本結(jié)果估計.我們?nèi)绾未_保 $E_{test}$ 泛化效果如何呢?
$E_{test}$ 泛化效果相關(guān)的假設(shè)的有效數(shù)目是1.因為考慮到測試集,只存在一個假設(shè),就是訓(xùn)練過程中產(chǎn)生的最終假設(shè)函數(shù)g.選擇的測試集不同并不影響最終的假設(shè)函數(shù),但如果選擇不同的訓(xùn)練集,最終的假設(shè)函數(shù)會跟著改變.同時Hoeffding不等式可以應(yīng)用在 $E_{test}$ 的一個假設(shè)上,產(chǎn)生的邊界比VC維邊界更加緊密.測試集越大, $E_{test}$ 對 $E_{out}$ 的估計越準(zhǔn)確.

使用測試集有一定的代價.測試集并不影響學(xué)習(xí)過程的輸出,學(xué)習(xí)過程僅和訓(xùn)練集相關(guān).測試集告訴我們學(xué)習(xí)過程產(chǎn)生的模型表現(xiàn)如何.因此,如果我們將一部分?jǐn)?shù)據(jù)分成測試集,那么用于訓(xùn)練的數(shù)據(jù)就會減少.因為訓(xùn)練數(shù)據(jù)是用來在假設(shè)空間中選擇一個假設(shè),因此訓(xùn)練數(shù)據(jù)對于選擇最終的假設(shè)函數(shù)至關(guān)重要.There is a tradeoff to setting aside test examples.訓(xùn)練集和測試集如何劃分,比例如何需要仔細(xì)權(quán)衡.

在一些文獻(xiàn)中, $E_{test}$ 看做是 $E_{out}$ 的同義詞.

Other Target Types 其他目標(biāo)類型

盡管VC維分析是基于二分類目標(biāo)函數(shù)的,但是也可以擴(kuò)展到實值函數(shù)或其他類型函數(shù)上.介紹一種新的方法偏差-方差分析.

為了符合實值函數(shù),需要調(diào)整 $E_{in}$ 和 $E_{out}$ 的定義.在實值函數(shù)中,需要測量h(x)和f(x)之間的距離,而不是判斷兩個值是否相等.

最常用的誤差測量方法是平方誤差 $e(h(x),f(x)) = (h(x)-f(x))^2$ .可以定義樣本內(nèi)和樣本外的誤差.樣本外誤差是基于整個輸入空間X的,

$E_{out}(h) = E[( h(x)-f(x))^2]$

樣本內(nèi)誤差是基于整個訓(xùn)練集誤差量的平均值:

$E_in(h)=\frac1{N} \sum_{n=1}^N(h(x_n) -f(x_n))^2$

使用樣本誤差均值去評估誤差的期望值.

Approximation-Generalization tradeoff

VC維分析需要選擇在訓(xùn)練數(shù)據(jù)上接近目標(biāo)函數(shù)f和在unseen data上泛化良好這兩個變現(xiàn)之間取得平衡的假設(shè).當(dāng)在假設(shè)空間H中選擇假設(shè)函數(shù)時,需要在兩個矛盾的目標(biāo)之間進(jìn)行權(quán)衡:在假設(shè)空間中選擇可以接近f的假設(shè),同時保證訓(xùn)練數(shù)據(jù)上學(xué)的模型能泛化到整個輸入空間上.VC維泛化邊界就是一種兩者之間權(quán)衡方法.如果H太過于簡單,選擇的假設(shè)可能不能接近f,樣本內(nèi)誤差很大;如果H太過于復(fù)雜,泛化效果變差,因為模型復(fù)雜度太大.存在另外一種方法:近似泛化tradeoff.這種方法適合平方誤差測量,而不是VC分析中使用的二分誤差.這種方法提供了一個新的角度:VC維分析中使用 $E_{in}$ 加上懲罰項 $\Omega$ 來對 $E_{out}$ 進(jìn)行近似;這里將 $E_{out}$ 分成兩部分誤差項.

Bias and Variance偏差和方差

樣本外誤差偏差-方差分解是基于平方誤差測量方法的.Out-of-sample誤差:

$E_{out}(g^{(D)}) = E_x[ (g^{(D)}(x) - f(x))^2]$

其中, $E_{x}$ 表示關(guān)于x的期望值.在最終假設(shè)g上添加顯性的對數(shù)據(jù)集D的依賴關(guān)系.上面等式中樣本外誤差的計算依賴于從選擇數(shù)據(jù)集D中訓(xùn)練出來的最終假設(shè)g,也就是說是依賴于選擇的訓(xùn)練數(shù)據(jù)集的.我們可以在所有可能的訓(xùn)練集上求期望值,移除對選擇的特定數(shù)據(jù)集D的依賴,從而獨立于數(shù)據(jù)集:

$E_D[ E_{out}(g^D)] = E_D[ E_x[(g^{(D)}(x) - f(x))^2]] \\=E_x[ E_D[(g^{(D)}(x) - f(x))^2]] \\=E_x[ E_D[ g^{(D)(x)^2}] -2 E_D[ g^{(D)(x)}]f(x) + f(x)^2]$

其中, $E_D[ g^{(D)}(x)]$ 是一個平均函數(shù),也可以表示為 $\hat{g}(x)$ .可以理解為生成若干個數(shù)據(jù)集 $D_1,D_2,...,D_K$ 然后在每個數(shù)據(jù)集上進(jìn)行訓(xùn)練學(xué)習(xí),生成最終的假設(shè) $g_1,g_2,...,g_K$ .而任意數(shù)據(jù)x在最終的平均假設(shè)上的結(jié)果為 $\hat{g}(x) \approx \frac1{K} \sum_{k=1}^K g_k(x)$ .本質(zhì)上,可以將g(x)看做是一個隨機(jī)變量,在隨機(jī)數(shù)據(jù)集上的隨機(jī)產(chǎn)生的; $\hat{g}(x)$ 是特定值x在隨機(jī)變量上的期望值, $\hat{g}$ 是一個函數(shù),取平均值.同時函數(shù) $\hat{g}$ 有一點違反常識: $\hat{g}$ 不在假設(shè)空間中,但是在假設(shè)空間中函數(shù)的平均值.

可以使用 $\hat{g}$ 對out-of-sample誤差進(jìn)行改寫:
[圖片上傳失敗...(image-4d8aee-1544952000340)]

其中, $\hat{g}(x)$ 是對于D來說是一個常量; $(\hat{g}(x)-f(x))^2$ 測量從數(shù)據(jù)集D中學(xué)到的平均函數(shù)與目標(biāo)函數(shù)f之間的差距,可以把這個量稱為bias偏差:

$bias(x)=(\hat{g}(x)-f(x))^2$

表示學(xué)習(xí)模型偏離目標(biāo)函數(shù)的距離(偏差).因為 $\hat{g}(x)$ 是從不限數(shù)目多個數(shù)據(jù)集中學(xué)習(xí)的,因此它在估計目標(biāo)函數(shù)時僅僅受限于模型自身. $E_D[ (g^{(D)}(x) - \hat{g}(x))^2]$ 是隨機(jī)變量 $g^{(D)}(x)$ 的方差:

$var(x) = E_D[ (g^{(D)}(x) - \hat{g}(x))^2]$

評估依賴于數(shù)據(jù)集的最終假設(shè)的變化情況(方差).最后,out-of-sample誤差的偏差-方差分解為:

$E_D[ E_{out}(g^{(D)})] = E_x[ bias(x) + var(x)] \\=bias + var$

因為, $bias = E_x[ bias(x)], var=E_x[ var(x)]$ . 這里的推導(dǎo)都基于數(shù)據(jù)是無噪音的假設(shè).如果是帶噪音的數(shù)據(jù),在最終的偏差-方差分解中需要加上噪音項.

[圖片上傳失敗...(image-a23a25-1544952000340)]

可以將方差看做學(xué)習(xí)模型的不穩(wěn)定性(也就是方差的意義).

在偏差方差分析中學(xué)習(xí)算法有很大的影響(在VC維分析中卻無關(guān)緊要).

VC維分析只基于假設(shè)空間H,獨立于學(xué)習(xí)算法A;在偏差-方差分析中,學(xué)習(xí)算法A和假設(shè)空間H同樣重要.相同的假設(shè)空間,不同的學(xué)習(xí)算法會產(chǎn)生不同的 $g^{(D)}$ .
盡管偏差-方差分析是基于平方誤差測量方法的,但是學(xué)習(xí)算法并不一定是基于最小化平方誤差.可以使用任何基于D的標(biāo)準(zhǔn)產(chǎn)生最終假設(shè) $g^{(D)}$ .但一旦產(chǎn)生 $g^{(D)}$ 之后,必須基于平方誤差計算偏差和方差.

不幸的是,實際情況下偏差和方差并不能計算出來,因為它們是依賴于目標(biāo)函數(shù)和輸入概率分布,而這兩項都是未知的.但是偏差-方差分析在開發(fā)模型時是一種非常重要的概念性工具.當(dāng)考慮偏差和方差時,需要考慮兩個目標(biāo):在不顯著增加偏差的基礎(chǔ)上嘗試降低方差;在不顯著增加方差的基礎(chǔ)上嘗試降低偏差.

The Learning Curve學(xué)習(xí)曲線

學(xué)習(xí)曲線概括了當(dāng)訓(xùn)練集樣本數(shù)N變化時,樣本內(nèi)誤差和樣本外誤差的變化情況.在大小為N的數(shù)據(jù)集D上學(xué)習(xí)之后,可以得到依賴于D的樣本誤差和樣本外誤差.就像之前在偏差-方差中介紹的一樣,對大小為N的所有可能數(shù)據(jù)集D求期望之后, $E_D[ E_{in}[ g^{(D)}]]$ 和 $E_D[ E_{out}[ g^{(D)}]]$ 是關(guān)于N的函數(shù).比如一個簡單模型和復(fù)雜模型的學(xué)習(xí)曲線如下:
[圖片上傳失敗...(image-cc986-1544952000340)]

可以看出,對于簡單模型來說,收斂速度更快,但是最終表現(xiàn)比復(fù)雜模型要差.對于兩個模型來說,樣本外誤差都隨著N的增大而減小;樣本內(nèi)誤差隨著N增加而增大. 用VC維分析和偏差-方差分析,結(jié)果如何呢?

[圖片上傳失敗...(image-ea00c3-1544952000340)]

在VC維分析中, $E_{out}$ 是 $E_{in}$ 和泛化邊界模型復(fù)雜度懲罰 $\Omega$ 之和.在偏差-方差分析中, $E_{out}$ 被分解為偏差和方差之和.
隨著樣本點增多,泛化誤差和方差都減小.學(xué)習(xí)曲線可表明了關(guān)于 $E_{in}$ 的一個重要特性.隨著N的增加,為了逼近f, $E_{in}$ 接近于學(xué)習(xí)模型的最小誤差.當(dāng)N很小時, $E_{in}$ 與"應(yīng)該的最小誤差"很遠(yuǎn),主要是因為對小數(shù)據(jù)來說,學(xué)習(xí)難度更小.

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末枣宫，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌粪糙，老刑警劉巖艰赞，帶你破解...
沈念sama閱讀 219,490評論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件变隔，死亡現(xiàn)場離奇詭異右遭，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)乖杠，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,581評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門分扎，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人胧洒，你說我怎么就攤上這事畏吓。” “怎么了卫漫？”我有些...
開封第一講書人閱讀 165,830評論 0贊 356
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵菲饼，是天一觀的道長。經(jīng)常有香客問我汛兜，道長巴粪，這世上最難降的妖魔是什么通今？我笑而不...
開封第一講書人閱讀 58,957評論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任粥谬，我火速辦了婚禮肛根，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘漏策。我一直安慰自己派哲，他們只是感情好，可當(dāng)我...
茶點故事閱讀 67,974評論 6贊 393
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布掺喻。她就那樣靜靜地躺著芭届，像睡著了一般。火紅的嫁衣襯著肌膚如雪感耙。梳的紋絲不亂的頭發(fā)上褂乍，一...
開封第一講書人閱讀 51,754評論 1贊 307
城市分裂傳說
那天，我揣著相機(jī)與錄音即硼，去河邊找鬼逃片。笑死，一個胖子當(dāng)著我的面吹牛只酥，可吹牛的內(nèi)容都是我干的褥实。我是一名探鬼主播，決...
沈念sama閱讀 40,464評論 3贊 420
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼裂允，長吁一口氣：“原來是場噩夢啊……” “哼损离！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起绝编，我...
開封第一講書人閱讀 39,357評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤僻澎，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后十饥，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體怎棱，經(jīng)...
沈念sama閱讀 45,847評論 1贊 317
?護(hù)林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,995評論 3贊 338
?白月光啟示錄
正文我和宋清朗相戀三年绷跑，在試婚紗的時候發(fā)現(xiàn)自己被綠了拳恋。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 40,137評論 1贊 351
活死人
序言：一個原本活蹦亂跳的男人離奇死亡砸捏，死狀恐怖谬运，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情垦藏，我是刑警寧澤梆暖，帶...
沈念sama閱讀 35,819評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站掂骏，受9級特大地震影響轰驳，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,482評論 3贊 331
男人毒藥：我在死后第九天來索命
文/蒙蒙一级解、第九天我趴在偏房一處隱蔽的房頂上張望冒黑。院中可真熱鬧，春花似錦勤哗、人聲如沸抡爹。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,023評論 0贊 22
一樁弒父案芒划，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽冬竟。三九已至，卻和暖如春民逼，著一層夾襖步出監(jiān)牢的瞬間泵殴，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,149評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工拼苍，沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留袋狞，地道東北人。一個月前我還...
沈念sama閱讀 48,409評論 3贊 373
代替公主和親
正文我出身青樓映屋，卻偏偏與公主長得像苟鸯，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子棚点，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 45,086評論 2贊 355