Empiricial Risk Minimization

統(tǒng)計(jì)學(xué)習(xí)理論是整個(gè)機(jī)器學(xué)習(xí)到框架。試想我們學(xué)習(xí)的目的是什么呢？當(dāng)然是為了具備用合理的方式處理問(wèn)題的能力。統(tǒng)計(jì)學(xué)習(xí)理論要解決的問(wèn)題就是基于數(shù)據(jù)找到一個(gè)預(yù)測(cè)函數(shù)。經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化(Empiricial Risk Minimization,ERM)[2]是統(tǒng)計(jì)學(xué)習(xí)理論中準(zhǔn)則之一，常用于給出學(xué)習(xí)算法(learning algorithms)性能的理論邊界。 假定給定兩個(gè)數(shù)據(jù)空間\(X\)和\(Y\), 我們想學(xué)習(xí)到一個(gè)假設(shè)函數(shù)(hypothesis function)\(h:X\rightarrow Y\)。對(duì)于任意的\(x\in X\), 我們可用假設(shè)函數(shù)求得\(x\)在空間\(Y\)中對(duì)應(yīng)的映射\(y\in Y\)，即\(y=h(x)\)。假設(shè)\(X\)和\(Y\)之間存在聯(lián)合概率分布\(P(x,y)\)，注意在聯(lián)合概率的假設(shè)下，\(x\)和\(y\)之間不存在單一映射關(guān)系。具體而言，即使給定\(x\)，\(y\)依然是個(gè)隨機(jī)變量，最合理的\(y\)就是使不確定性最小的：\(y=arg\underset{y\in Y}{\max}\;P(y|x)\)。如何衡量我們預(yù)測(cè)的結(jié)果好不好呢？損失函數(shù)(loss function)登場(chǎng)了，損失函數(shù)\(L(y,\hat{y})\)度量預(yù)測(cè)值\(\hat{y}\)與真實(shí)值\(y\)之間的差距，兩者越相近，對(duì)應(yīng)的損失也就越小。在二分類問(wèn)題中，損失函數(shù)常定義為\(L(y,\hat{y})=I(y\neq\hat{y})\)；在回歸問(wèn)題中，損失函數(shù)更傾向于\(L(y,\hat{y})=(y-\hat{y})^2\)。假設(shè)函數(shù)\(h(x)\)的風(fēng)險(xiǎn)(泛化誤差)定義為損失函數(shù)的期望： \begin{equation} R(h)=\mathbb{E}\left[L(h(x),y)\right]=\int L(h(x),y)d P(x,y) \end{equation} 學(xué)習(xí)算法的終極目標(biāo)是在假設(shè)集合\(\mathcal{H}\)中找到最優(yōu)的假設(shè)函數(shù)\(h^{\star}\)，使得風(fēng)險(xiǎn)\(R(h)\)最小： \begin{equation} h^{\star}=arg \underset{h\in\mathcal{H}}{\min}\;R(h) \end{equation} 絕大多數(shù)情形下，我們不知道概率分布\(P(x,y)\)，使得學(xué)習(xí)算法無(wú)法計(jì)算\(R(h)\)。但是我們可以通過(guò)在\(P(x,y)\)上采樣的方式來(lái)計(jì)算\(R(h)\)的近似值。假設(shè)我們從\(P(x,y)\)采樣得到的\(m\)個(gè)獨(dú)立同分布的樣本組成訓(xùn)練集\(\mathcal{S}=\{(x^{(i)},y^{(i)})\}_{i=1}^m\)，那么風(fēng)險(xiǎn)\(R(h)\)對(duì)應(yīng)的近似值\(\hat{R}(h)\)只需在訓(xùn)練集上計(jì)算損失函數(shù)的均值即可： \begin{equation} \hat{R}(h)=\frac{1}{m}\sum_{i=1}^mL(h(x^{(i)},y^{(i)}) \end{equation} 其中\(zhòng)(\hat{R}(h)\)即為經(jīng)驗(yàn)風(fēng)險(xiǎn)(empirical risk)。經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化準(zhǔn)則闡述的規(guī)律就是使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小的假設(shè)函數(shù)對(duì)應(yīng)實(shí)際的最優(yōu)假設(shè)函數(shù)\(h^{\star}\)的近似值\(\hat{h}^{\star}\): \begin{equation} \hat{h}^{\star}=arg\underset{h\in\mathcal{H}}{\min}\;\hat{R}(h) \end{equation} 根據(jù)大數(shù)定理可知，在訓(xùn)練數(shù)據(jù)足夠多的情況下(\(n\rightarrow\infty\))，經(jīng)驗(yàn)風(fēng)險(xiǎn)是可以收斂到真實(shí)的泛化誤差的。但在大多實(shí)際應(yīng)用中，可用于訓(xùn)練模型的樣本卻往往非常有限。因此，在有限的訓(xùn)練數(shù)據(jù)情形下，使經(jīng)驗(yàn)風(fēng)險(xiǎn)最小的假設(shè)函數(shù)，其對(duì)應(yīng)的泛化誤差不一定是最小的，即可能不是泛化能力最強(qiáng)的假設(shè)函數(shù)，如圖1所示。?

Probabilistic Inequalities

在展開學(xué)習(xí)理論之前，非常有必要簡(jiǎn)單回顧并證明一下相關(guān)的概率不等式，這是進(jìn)一步討論學(xué)習(xí)理論的基礎(chǔ)。

定理一(Jensen's Inequality)[4]

假設(shè)\(X\)為隨機(jī)變量，\(f:X\rightarrow\mathbb{R}\)為凸函數(shù)(convex)，有 \begin{equation} f\left(\mathbb{E}[X]\right)\leq \mathbb{E}\left[f(x)\right] \end{equation} 如果\(f\)為凹函數(shù)(concave)則有相反的結(jié)論 \begin{equation} f\left(\mathbb{E}[X]\right)\geq \mathbb{E}\left[f(x)\right] \end{equation}

定理二(Markov's Inequality)[5]

假設(shè)\(X\)為非負(fù)的隨機(jī)變量，對(duì)任意的\(t>0\)，有 \begin{equation} P(X>t)\leq\frac{\mathbb{E}[X]}{t} \end{equation}

證明： \begin{equation} \begin{array}{rl} \mathbb{E}[X]&=\int_{0}^{+\infty}xp(x)dx=\int_{0}^{t}xp(x)dx+\int_{t}^{+\infty}xp(x)dx\\ &\geq \int_{t}^{+\infty}xp(x)dx \geq t\int_{t}^{+\infty}p(x)dx=tP(X>t) \end{array} \end{equation}

定理三(Chernoff Bound)[1]

假設(shè)\(X\)為隨機(jī)變量,有 \begin{equation} P(X>\epsilon)\leq\underset{t\geq 0}{\inf}\exp(-t\epsilon)\mathbb{E}[\exp(tX)] \end{equation} 其中\(zhòng)(inf\)表示函數(shù)的最大下界。

證明： \begin{equation} \begin{array}{rl} P(X>\epsilon)&=P\left(\exp(X)>\exp(\epsilon)\right)\\ &=\underbrace{P\left(\exp(tX)>\exp(t\epsilon)\right)\leq\exp(-t\epsilon)\mathbb{E}[\exp(tX)]}_{Markov's \; inequality} \end{array} \end{equation}

定理四

假設(shè)隨機(jī)變量\(X\in[a,b]\)，\(\mathbb{E}[X]=0\)，有 \begin{equation} \mathbb{E}[\exp(tX)]\leq\exp\left(\frac{t^2(b-a)^2}{8}\right) \end{equation}

證明： 在\(a\neq 0,b\neq 0\)時(shí)，我們可以將\(X\)表示成\(a\)和\(b\)的線性組合\(X=\alpha b+(1-\alpha)a\)，其中\(zhòng)(\alpha=(X-a)/(b-a)\in[0,1]\)。對(duì)于凸函數(shù)\(f(x)=\exp(tx)\)，如果我們將\(X\)視為一個(gè)Bernoulli分布的隨機(jī)變量(即\(P(X=b)=\alpha,P(X=a)=1-\alpha\))，那么根據(jù)Jensen不等式，有 \begin{equation} f(X)=f(\alpha x+(1-\alpha)b)\leq\alpha f(x)+(1-\alpha)f(b) \end{equation} 將\(X=\alpha b+(1-\alpha)a\)帶入上述不等式中，得 \begin{equation} \exp(tX)\leq\frac{X-a}{b-a}\exp(tb)+\frac{b-X}{b-a}\exp(ta) \end{equation} 在上式左右兩邊求期望值，結(jié)合\(\mathbb{E}[X]=0\)，有 \begin{equation} \mathbb{E}[\exp(tX)]\leq-\frac{a}{b-a}\exp(tb)+\frac{b}{b-a}\exp(ta)=\exp(g(u)) \end{equation} 其中\(zhòng)(u=t(b-a)\),\(g(u)=-\theta u+\log(1-\theta+\theta\exp(u))\),\(\theta=-a/(b-a)\in(0,1)\)。 根據(jù)二階Taylor展開公式，存在\(v\in(0,u)\)使得下式成立： \begin{equation} g(u)=g(0)+ug'(0)+\frac{u^2}{2}g''(v) \end{equation} 接下來(lái)，對(duì)\(g(u)\)求一階倒數(shù)和二階倒數(shù) \begin{equation} g'(0)=-\theta+\frac{\theta\exp(u)}{1-\theta+\theta\exp(u)}\vert_{u=0}=0 \end{equation} \begin{equation} g''(v)=\frac{\theta\exp(v)}{1-\theta+\theta\exp(v)}\left(1-\frac{\theta\exp(v)}{1-\theta+\theta\exp(v)}\right)\leq\frac{1}{4} \end{equation} 該不等式成立，因?yàn)閷?duì)任意\(s\in[0,1]\)，有函數(shù)\(s(1-s)\leq\frac{1}{4}\)。將\(g(0)=0\),\(g'(0)=0\),\(g''(v)\leq 1/4\)和\(u\)帶入Taylor展開式中，得到以下不等式： \begin{equation} g(u)=\frac{u^2}{2}g''(v)\leq\frac{u^2}{8}=\frac{t^2(b-a)^2}{8} \end{equation} 由上式可得 \begin{equation} \mathbb{E}[\exp(tX)]\leq\exp\left(\frac{t^2(b-a)^2}{8}\right) \end{equation} 我們可以驗(yàn)證，在\(a=b=0\)時(shí)，上述不等式仍然是成立的。

定理五(Hoeffding's Inequality)[3]

假設(shè)\(X_1,\cdots,X_n\)為\(n\)個(gè)相互獨(dú)立的隨機(jī)變量,且\(X_i\in[a_i,b_i]\)，\(\bar{X}=\sum_{i=1}^nX_i/n\)，則對(duì)任意的\(\epsilon>0\)有 \begin{equation} P\left(|\bar{X}-\mathbb{E}[\bar{X}]|>\epsilon\right)\leq 2\exp\left(\frac{2n^2\epsilon^2}{\sum_{i=1}^n(b_i-a_i)^2}\right) \end{equation}

證明：根據(jù)對(duì)稱性、Chernoff邊界定理、定理四以及隨機(jī)變量間的相互獨(dú)立性質(zhì)，可推導(dǎo)出下式 \begin{equation} \begin{array}{rl} &P\left(|\bar{X}-\mathbb{E}[\bar{X}]|>\epsilon\right)\\ =&2P\left(\bar{X}-\mathbb{E}[\bar{X}]>\epsilon\right)\\ \leq& 2\underset{t\geq 0}{\inf}\exp(-t\epsilon)\mathbb{E}[\exp(t\bar{X})]\\ =& 2\underset{t\geq 0}{\inf}\exp(-t\epsilon)\mathbb{E}[\exp(t\sum_{i=1}^nX_i/n)]\\ =& 2\underset{t\geq 0}{\inf}\exp(-t\epsilon)\mathbb{E}[\prod_{i=1}^n\exp(tX_i/n)]\\ =& 2\underset{t\geq 0}{\inf}\exp(-t\epsilon)\prod_{i=1}^n\mathbb{E}[\exp(tX_i/n)]\\ \leq & 2\underset{t\geq 0}{\inf}\exp(-t\epsilon)\prod_{i=1}^n\exp(t^2(b_i-a_i)^2/(8n^2))\\ =& 2\underset{t\geq 0}{\inf}\exp(-t\epsilon+\sum_{i=1}^nt^2(b_i-a_i)^2/(8n^2)) \end{array} \end{equation} 為了得到盡可能接近真實(shí)值的上階，我們還剩最后一步，即求出上式最右側(cè)函數(shù)的最大下界。定義函數(shù)\(p:\mathbb{R}\rightarrow\mathbb{R}\)為 \begin{equation} p(t)=-t\epsilon+\sum_{i=1}^n\frac{t^2(b_i-a_i)^2}{8n^2} \end{equation} 很顯然\(p(t)\)是一個(gè)二次函數(shù)，其最大下界可在極值點(diǎn)出取得： \begin{equation} p'(t)=-\epsilon+\frac{t\sum_{i=1}^n(b_i-a_i)^2}{4n^2}=0 \end{equation} 解上式可得 \begin{equation} t=\frac{4n^2\epsilon}{\sum_{i=1}^n(b_i-a_i)^2} \end{equation} 將\(t\)帶入\(p(t)\)即可得Hoeffding不等式： \begin{equation} P\left(|\bar{X}-\mathbb{E}[\bar{X}]|>\epsilon\right)\leq 2\exp\left(-\frac{2n^2\epsilon^2}{\sum_{i=1}^n(b_i-a_i)^2}\right) \end{equation}

定理六(Union Bound)[8]

對(duì)于有限個(gè)事件\(A_1,A_2,\cdots,A_n\)，有 \begin{equation} P\left(\bigcup_{i=1}^nA_i\right)\leq\sum_{i=1}^nP(A_i) \end{equation}

證明： 我們用歸納法來(lái)證明該定理。在\(n=1\)時(shí)，顯然\(P(A_1)\leq P(A_1)\)；假設(shè)在\(n=k\)時(shí)，\(P\left(\bigcup_i^kA_i\right)\leq\sum_{i=1}^nP(A_i)\)成立；那么在\(n=k+1\)時(shí)，結(jié)合\(P(A\cup B)=P(A)+P(B)-P(A\cap B)\)，有 \begin{equation} \begin{array}{rl} P\left(\bigcup_{i=1}^{k+1}A_i\right)&=P\left(\bigcup_{i=1}^{k}A_i\right)+P(A_{k+1})-P\left(\bigcup_{i=1}^{k}A_i\cap A_{k+1}\right)\\ &\leq\sum_{i=1}^kP(A_i)+P(A_{k+1})=\sum_{i=1}^{k+1}P(A_i) \end{array} \end{equation} 綜上所述，可知該定理成立。

Model complexity and Generalization Error

機(jī)器學(xué)習(xí)求解的假設(shè)函數(shù)不是單純?yōu)榱藬M合已有的數(shù)據(jù)，其最終目標(biāo)是準(zhǔn)確預(yù)測(cè)未知數(shù)據(jù)的輸出。經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化存在過(guò)擬合的風(fēng)險(xiǎn)，其目的在于找到一個(gè)可以很好與訓(xùn)練數(shù)據(jù)匹配的假設(shè)函數(shù)，而該假設(shè)函數(shù)不一定能預(yù)測(cè)未知數(shù)據(jù)的輸出。如圖2所示，訓(xùn)練數(shù)據(jù)的規(guī)模\(m\)、模型復(fù)雜度和泛化誤差\(R(h)\)三者間存在一定的關(guān)系。我們?nèi)绾伪苊膺^(guò)擬合？我們可以從兩方面應(yīng)對(duì)這個(gè)問(wèn)題。 從圖2(a)中可知，增加訓(xùn)練數(shù)據(jù)的規(guī)模有利于降低泛化誤差。但也不是訓(xùn)練數(shù)據(jù)越多越好，因?yàn)楫?dāng)訓(xùn)練數(shù)據(jù)達(dá)到一定規(guī)模后，泛化誤差的變化趨于平緩。那么一定的規(guī)模到底是個(gè)什么概念呢？這對(duì)應(yīng)我們后面即將說(shuō)明的算法的樣本復(fù)雜度。觀察圖2(b)，可知模型復(fù)雜度太大或者太小都會(huì)導(dǎo)致泛化誤差過(guò)大。因此，另一個(gè)避免模型過(guò)擬合的方法就是控制模型復(fù)雜度。 機(jī)器學(xué)習(xí)領(lǐng)域有個(gè)警句，"Sometimes it's not who has the best algorithm that wins;it's who has the most data"。現(xiàn)在大數(shù)據(jù)也吵得火熱，圖2也可以幫助我們理解為什么大量的訓(xùn)練數(shù)據(jù)加上一般的模型產(chǎn)生的威力可能要強(qiáng)于少量的訓(xùn)練數(shù)據(jù)加上優(yōu)秀的模型。但是呢，縱然現(xiàn)在有分布式計(jì)算作為支撐，過(guò)多的訓(xùn)練數(shù)據(jù)還是會(huì)帶來(lái)很大的存儲(chǔ)、通信和計(jì)算開銷，但在有些情形下盲目增大訓(xùn)練數(shù)據(jù)的規(guī)模意義不大；另一方面，在某些領(lǐng)域想要獲取足夠多的訓(xùn)練數(shù)據(jù)不是那么容易的。在研究機(jī)器學(xué)習(xí)算法時(shí)，模型的復(fù)雜度是我們更為關(guān)心的問(wèn)題。

The case of finite \(\mathcal{H}\)

我們用\(|\mathcal{H}|\)表示假設(shè)集合\(\mathcal{H}\)中包含的假設(shè)函數(shù)的數(shù)目，有限個(gè)假設(shè)函數(shù)組成假設(shè)集合\(\mathcal{H}=\{h_1,h_2,\cdots,h_{|\mathcal{H}|}\}\)，根據(jù)經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化的原則，從假設(shè)集合\(\mathcal{H}\)中估計(jì)出的最優(yōu)假設(shè)函數(shù)滿足訓(xùn)練誤差最小的條件： \begin{equation} \hat{h}=arg\underset{h_i\in\mathcal{H}}{\min}\hat{R}(h_i) \end{equation} 下面要證明的是使訓(xùn)練誤差較小的假設(shè)函數(shù)\(\hat{h}\)，其泛化誤差也不至于太大。我們分兩步完成這個(gè)證明：首先，對(duì)任意假設(shè)函數(shù)\(h\)而言，\(\hat{R}(h)\)都是\(R(h)\)的一個(gè)可靠的近似值；其次，給出\(\hat{h}\)的泛化誤差\(R(\hat{h})\)的上界。 我們?cè)跇颖究臻g內(nèi)根據(jù)樣本的概率分布\(\mathcal{D}\)進(jìn)行采樣，得到訓(xùn)練集\(\mathcal{S}=\{(x^{(i)},y^{(i)})\}_{i=1}^m\)。給定任意假設(shè)函數(shù)\(h_i\in\mathcal{H}\)，定義服從Bernoulli分布的隨機(jī)變量\(Z_j=I\{h_i(x^{(j)})\neq y^{(j)}\}\in\{0,1\}\)，則\(Z_j\)表示\(h_i\)是否將樣本\((x^{(j)},y^{(j)})\)誤分類了，\(h_i\)的泛化誤差\(R(h_i)=P(z_j=1)\)。因?yàn)樗袠颖径际菑耐粋€(gè)概率分布中獨(dú)立采樣的，所以\(\{Z_j\}_{j=1}^m\)中的都是滿足獨(dú)立同分布的Bernoulli隨機(jī)變量。\(h_i\)的訓(xùn)練誤差形式為： \begin{equation} \hat{R}(h_i)=\frac{1}{m}\sum_{j=1}^mI\{h_i(x^{(j)})\neq y^{(j)}\}=\frac{1}{m}\sum_{j=1}^mz_j \end{equation} 顯然\(\hat{R}(h_i)\)為\(m\)個(gè)獨(dú)立同分布的Bernoulli隨機(jī)變量的均值，且這些隨機(jī)變量的期望值都為\(R(h_i)\)。根據(jù)Hoeffding不等式，得到如下規(guī)律： \begin{equation} P\left(|R(h_i)-\hat{R}(h_i)|>\gamma\right)\leq 2\exp(-2\gamma^2m) \end{equation} 上述規(guī)律說(shuō)明：對(duì)特定假設(shè)函數(shù)\(h_i\)而言，在樣本數(shù)目\(m\)足夠大時(shí)，訓(xùn)練誤差和泛化誤差近似相等的概率可以非常大，這也證明了\(\hat{R}(h)\)都是\(R(h)\)的一個(gè)可靠的近似值。 但我們想要保證的不僅僅是這種近似的可靠性只對(duì)特定的假設(shè)函數(shù)成立，而是對(duì)假設(shè)集合\(\mathcal{H}\)中的所有假設(shè)函數(shù)都成立。現(xiàn)將事件\(A_i\)定義為\(|R(h_i)-\hat{R}(h_i)|>\gamma\)，則由上一個(gè)結(jié)論可得\(P(A_i)\leq 2\exp(-2\gamma^2m)\)。 \begin{equation} \begin{array}{rl} &P\left(\exists h\in\mathcal{H}.|R(h_i)-\hat{R}(h_i)|>\gamma\right)\\ =&P(\bigcup_{i=1}^{|\mathcal{H}|}A_i)\\ \leq & \sum_{i=1}^{|\mathcal{H}|}P(A_i)\\ \leq & 2\sum_{i=1}^{|\mathcal{H}|}\exp(-2\gamma^2m)\\ =& 2|\mathcal{H}|\exp(-2\gamma^2m) \end{array} \end{equation} 上述事件的對(duì)立事件對(duì)應(yīng)的概率為： \begin{equation} \begin{array}{rl} &P\left(\neg\exists h\in\mathcal{H}.|R(h_i)-\hat{R}(h_i)|>\gamma\right)\\ =&P\left(\forall h\in\mathcal{H}.|R(h_i)-\hat{R}(h_i)|\leq\gamma\right)\\ \geq & 1-2|\mathcal{H}|\exp(-2\gamma^2m) \end{array} \end{equation} 上式被成為一致性收斂(uniform convergence)，因?yàn)檫@個(gè)邊界值對(duì)\(\mathcal{H}\)中的所有假設(shè)函數(shù)都成立。由此可知，\(\mathcal{H}\)中的所有假設(shè)函數(shù)的訓(xùn)練誤差與泛化誤差偏離范圍在\(\gamma\)以內(nèi)的概率至少為\(1-2|\mathcal{H}|\exp(-2\gamma^2m)\)。 現(xiàn)在，我們已經(jīng)得到了訓(xùn)練樣本數(shù)目\(m\)、訓(xùn)練誤差與泛化誤差間的偏離上限\(\gamma\)及其發(fā)生最大偏差時(shí)的的概率下限\(1-2|\mathcal{H}|\exp(-2\gamma^2m)\)三者間的關(guān)系，在給定其中兩個(gè)值的情況下我們可以推出第三個(gè)變量需要滿足的條件。比如說(shuō)，為了確保所有假設(shè)函數(shù)的訓(xùn)練誤差和泛化誤差間的偏差范圍都在\(\gamma\)以內(nèi)的概率至少為\(1-\delta\)，至少需要多少個(gè)訓(xùn)練樣本？這個(gè)問(wèn)題對(duì)應(yīng)的數(shù)學(xué)表述為： \begin{equation} P\left(\forall h\in\mathcal{H}.|R(h_j)-\hat{R}(h_j)|\leq\gamma\right)\geq 1-2|\mathcal{H}|\exp(-2\gamma^2m)\geq 1-\delta \end{equation} 求解上述不等式，可得訓(xùn)練樣本數(shù)目\(m\)的下界： \begin{equation} m\geq\frac{1}{2\gamma^2}\log\frac{2|\mathcal{H}|}{\delta}=O\left(\frac{1}{\gamma^2}\log\frac{|\mathcal{H}|}{\delta}\right) \end{equation} 這條規(guī)律對(duì)我們是非常有用的，由此我們可以推測(cè)算法性能要達(dá)到某種水平，至少需要多少個(gè)樣本就足夠了，這也稱為算法的樣本復(fù)雜度(sample complexity)。一般而言，\(\log |\mathcal{H}|\)增長(zhǎng)很慢，據(jù)CMU的Andrew Moore所說(shuō)，\(\log |\mathcal{H}|\leq 30\)。樣本數(shù)目太少不能保證訓(xùn)練出來(lái)的模型有較優(yōu)的性能，樣本數(shù)目也沒(méi)必要太多太多，尤其在樣本的收集比較困難的情況下，只要能在模型性能達(dá)到期望的效果，樣本越少越好。 同樣地，假設(shè)樣本數(shù)目\(m\)和\(\delta\)都確定了，我們想知道假設(shè)集合\(\mathcal{H}\)中所有假設(shè)函數(shù)的訓(xùn)練誤差和泛化誤差間偏離程度\(\gamma\)： \begin{equation} |R(h_j)-\hat{R}(h_j)|\leq\gamma\leq\sqrt{\frac{1}{2m}\log\frac{2|\mathcal{H}|}{\delta}} \end{equation} 接下來(lái)，我們即將給出\(\hat{h}\)的泛化誤差上界。定義假設(shè)集合\(\mathcal{H}\)中的最優(yōu)假設(shè)函數(shù)為： \begin{equation} h^{\star}=arg\underset{h\in\mathcal{H}}{\min}\;R(h) \end{equation} 由于\(h^{\star}\)訓(xùn)練誤差小于\(\hat{h}\)，結(jié)合\(|R(h)-\hat{R}{h}|\leq\gamma\)，可得到\(\hat{h}\)的泛化誤差上界： \begin{equation} R(\hat{h})\leq\hat{R}(\hat{h})+\gamma\leq\hat{R}(h^{\star})+\gamma\leq R(h^{\star})+2\gamma \end{equation} 上式說(shuō)明，訓(xùn)練誤差最小的假設(shè)函數(shù)\(\hat{h}\)的泛化誤差頂多比假設(shè)集合中最優(yōu)的假設(shè)函數(shù)\(h^{\star}\)高\(yùn)(2\gamma\)，即： \begin{equation} R(\hat{h})\leq\left(\underset{h\in\mathcal{H}}{\min}\;R(h)\right)+2\sqrt{\frac{1}{2m}\log\frac{2|\mathcal{H}|}{\delta}} \end{equation} 如果擴(kuò)大模型的復(fù)雜度，即假設(shè)空間增大為\(\mathcal{H}'\supset\mathcal{H}\)。在\(\mathcal{H}'\)中，我們可能找到泛化誤差更小的假設(shè)函數(shù)，因此第一項(xiàng)不可能增大；\(\mathcal{H}'\)中假設(shè)函數(shù)的數(shù)目\(k\)增大，必然使得第二項(xiàng)增大。 根據(jù)如下關(guān)系： \begin{equation} R(\hat{h})\leq \hat{R}(\hat{h})+\sqrt{\frac{1}{2m}\log\frac{2|\mathcal{H}|}{\delta}} \end{equation} 我們可以總結(jié)出如下規(guī)律：在\(|\mathcal{H}|\)有限的情況下，只要樣本數(shù)目\(m\)足夠大，就有\(zhòng)(R(\hat{h})\approx \hat{R}(h)\)；此時(shí)若有\(zhòng)(\hat{R}(\hat{h})\approx 0\)，必然有\(zhòng)(R(\hat{h})\approx 0\)，即通過(guò)經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化得到的最優(yōu)假設(shè)函數(shù)是可靠的。但實(shí)際情況并非如此簡(jiǎn)單：如果\(|\mathcal{H}|\)有限，在大多數(shù)情況下我們無(wú)法保證從\(\mathcal{H}\)中選擇出來(lái)的假設(shè)函數(shù)的經(jīng)驗(yàn)風(fēng)險(xiǎn)趨近于0(少數(shù)時(shí)候可以碰巧找到經(jīng)驗(yàn)風(fēng)險(xiǎn)為0的假設(shè)函數(shù))，此時(shí)\(\hat{h}\)的泛化誤差可能無(wú)法令人滿意；如果\(|\mathcal{H}|\)趨于無(wú)限，我們雖可以保證\(\hat{R}(\hat{h})\approx 0\)，但根據(jù)上式又無(wú)法得到\(R(\hat{h})\approx \hat{R}(h)\)，使得無(wú)法確保\(\hat{h}\)的泛化誤差足夠小。在\(|\mathcal{H}|\)趨于無(wú)限時(shí)，是否真的無(wú)法保證\(R(\hat{h})\approx \hat{R}(h)\)呢？請(qǐng)看下面\(|\mathcal{H}|=\infty\)的情況。

The case of infinite \(\mathcal{H}\)

為什么前面推導(dǎo)出的\(R(\hat{h})\)的泛化誤差的上界在\(|\mathcal{H}|=\infty\)時(shí)沒(méi)多少用呢？因?yàn)樵谕茖?dǎo)過(guò)錯(cuò)中用到了union bound的性質(zhì)，而且union bound定理中給出的上界是在假設(shè)所有假設(shè)函數(shù)\(h_i\)之間都相互獨(dú)立的前提下給出的。在實(shí)際情況中，\(\mathcal{H}\)有不少假設(shè)函數(shù)都是相似的。任意相似的兩個(gè)假設(shè)函數(shù)\(h_i\approx h_j\)，兩者有很多地方都是重疊的，也就說(shuō)\(\hat{R}(h_i)=\hat{R}(h_j)\)的概率很大。顯然，\(h_i\)和\(h_j\)不可能相互獨(dú)立，此時(shí)還用相互獨(dú)立的假設(shè)計(jì)算union bound會(huì)把重疊部分重復(fù)計(jì)算多次，致使給出的上界太過(guò)松弛。舉個(gè)簡(jiǎn)單的例子，假設(shè)\(\mathcal{H}\)為二維平面上所有直線的集合，顯然\(|\mathcal{H}|=\infty\)。如圖3中的\(x_i\)看來(lái)，二維平面中所有假設(shè)直線只有兩種，在\(x_1\)上面或下面的直線。

既然如此，我們能否找到一種策略，將所有相似的假設(shè)函數(shù)歸為有限的若干組呢？為了說(shuō)明這個(gè)問(wèn)題，下面我們簡(jiǎn)要介紹VC維。

VC Dimension

VC維(Vapnik-Chervonenkis dimension)[9]用于度量分類算法的復(fù)雜度。介紹VC維之前，先引入shatter(分散)這個(gè)概念。給定\(n\)個(gè)數(shù)據(jù)組成的集合\(\mathcal{X}=\{x^{(1)},x^{(2)},\cdots,x^{(d)}\}\)，若對(duì)任意的標(biāo)簽集合\(\mathcal{Y}=\{y^{(1)},y^{(2)},\cdots,y^{(d)}\}\)，都存在假設(shè)函數(shù)\(h\in\mathcal{H}\)可以完全正確分類，即\(h(x^{(i)})=y^{(i)}\)對(duì)\(\mathcal{X}\)中的所有數(shù)據(jù)都成立，則稱\(\mathcal{H}\)可以分散\(\mathcal{X}\)。假設(shè)集合\(\mathcal{H}\)的VC維\(VC(\mathcal{H})\)定義為\(\mathcal{H}\)可以分散的集合的能包含的數(shù)據(jù)的最大數(shù)目；若\(\mathcal{H}\)足以分散任意大的集合，則\(VC(\mathcal{H})=\infty\)。需要注意的是，為了證明\(VC(\mathcal{H})\)至少為\(d\)，我們只需要找到一個(gè)包含\(d\)個(gè)數(shù)據(jù)的集合能被\(\mathcal{H}\)分散即可；為了證明\(VC(\mathcal{H})\)最多為\(d\)，我們要證明不存在包含\(d+1\)個(gè)數(shù)據(jù)的集合能被\(\mathcal{H}\)分散。 為了更為直觀解釋VC維的概念，我們以只包含線性分類器(即感知機(jī)，Perceptron)的\(\mathcal{H}\)在二維平面中的情況為例進(jìn)行說(shuō)明。在圖4中，無(wú)論三個(gè)數(shù)據(jù)的標(biāo)簽如何變化，總能找到線性分類器實(shí)現(xiàn)無(wú)誤差的分類。但在圖5中，三點(diǎn)共線，線性分類器無(wú)法完全正確處理任意的分類任務(wù)。除此之外，對(duì)于包含至少4個(gè)數(shù)據(jù)的集合，再也無(wú)法在\(\mathcal{H}\)中找到可以完美分類的線性分類器。由此可見，\(\mathcal{H}\)能分散的集合最多只能包含三個(gè)數(shù)據(jù)，因此\(VC(\mathcal{H})=3\)。實(shí)際上，在\(d\)維空間里，線性分類器的VC維是\(d+1\)。看到這里，我們可能會(huì)非常氣憤，好不容易抽出時(shí)間學(xué)習(xí)VC維，竟然被告知\(d\)維空間中的線性分類器頂多可以完全正確對(duì)\(d+1\)個(gè)數(shù)據(jù)正確分類，要它有何用？值得慶幸的是，現(xiàn)實(shí)世界的變化還是趨于平滑的，相鄰的數(shù)據(jù)大多時(shí)候都屬于相同類別，并不需要處理所有數(shù)據(jù)都是任意類別的情形。所以即使是VC維較小的分類器也是有用武之地的。?

? ?

在統(tǒng)計(jì)學(xué)習(xí)理論中，VC維可用于給出分類模型的泛化誤差的概率性的上界，并且該上界獨(dú)立于樣本的分布情況。如果分類模型集合\(\mathcal{H}\)對(duì)應(yīng)的VC維為\(d\)，以經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化為最優(yōu)準(zhǔn)則，經(jīng)過(guò)\(m\)個(gè)服從獨(dú)立同分布的數(shù)據(jù)訓(xùn)練后得到分類模型的\(\hat{h}\in\mathcal{H}\)，\(\hat{h}\)的訓(xùn)練誤差和泛化誤差間的關(guān)系為： \begin{equation} P\left(R(\hat{h})\leq \hat{R}(\hat{h})+\sqrt{\fractjgufvlx2j{m}\left(\log\frac{2m}tjgufvlx2j+1\right)+\frac{1}{m}\log\frac{4}{\delta}}\right)\geq 1-\delta \end{equation} 其中，帶根號(hào)的那一項(xiàng)我們?cè)诖朔Q之為VC置信度(也可視為模型復(fù)雜度對(duì)應(yīng)的懲罰項(xiàng))。具體的證明過(guò)程本想親自推導(dǎo)一遍的，只是看了Vapnik的大作后頓時(shí)有了力不從心的感覺(jué)，目前肯起來(lái)太吃力，所有有興趣的人士請(qǐng)參見[12,13]。 VC維可被有效應(yīng)用于為線性分類器的泛化誤差確定一個(gè)上界，SVM就是一個(gè)成功的應(yīng)用典范。但其他場(chǎng)合下也許行不通，我們可以用以下三中情形來(lái)簡(jiǎn)單說(shuō)明：

• 對(duì)于諸如神經(jīng)網(wǎng)絡(luò)等非線性模型，無(wú)法較為準(zhǔn)確估計(jì)對(duì)應(yīng)的VC維；
• 對(duì)于KNN(k=1)和采用高斯核函數(shù)的SVM模型等，VC維是無(wú)窮的；
• 上界有時(shí)不能提供任何指導(dǎo)意義，比如分類錯(cuò)誤率的上界大于1時(shí)。

假設(shè)函數(shù)的VC維越大，表明其模型越復(fù)雜，對(duì)應(yīng)的表達(dá)能力也越強(qiáng)！復(fù)雜模型的經(jīng)驗(yàn)風(fēng)險(xiǎn)很小，同時(shí)也會(huì)因過(guò)于復(fù)雜帶來(lái)較大的懲罰成分。如果最后泛化誤差的上界增大，意味著泛化誤差很小的概率越來(lái)越小，模型不穩(wěn)定的幾率會(huì)大大增加。奧卡姆剃刀（Occam's razor）原理提倡在多個(gè)具有處于競(jìng)爭(zhēng)地位的可得出相同結(jié)論的理論中選擇最簡(jiǎn)單的那個(gè)。換到我們這個(gè)語(yǔ)境中，可以理解成，在經(jīng)驗(yàn)風(fēng)險(xiǎn)最小的若干個(gè)假設(shè)函數(shù)中，優(yōu)先選擇復(fù)雜度最低的模型。順帶提一下，為什么SVM要選擇間隔最大的超平面？其實(shí)這背后也是和VC維有關(guān)系的。如圖6所示，在\(n\)維空間里，如果所有數(shù)據(jù)點(diǎn)都可用一個(gè)半徑至少為\(R\)的球面包圍，超平面間的幾何間隔為\(2M\)，那么SVM的VC維的上界為[12]： \begin{equation} VC(\mathcal{H})\leq\min\left\lbrace\lceil\frac{R^2}{M^2},n\rceil\right\rbrace+1 \end{equation} 由上式可知，最大化幾何間隔實(shí)際上實(shí)在降低SVM的VC維；此外，對(duì)線性可分的數(shù)據(jù)而言，這些超平面對(duì)應(yīng)的經(jīng)驗(yàn)風(fēng)險(xiǎn)為0，所以最大化幾何間隔也是在直接降低泛化誤差的上界。我以前經(jīng)常在想，SVM的泛化性能和支持向量的數(shù)目是否有關(guān)系呢？這次我終于得到答案了。如果我們用留一法對(duì)SVM進(jìn)行交叉驗(yàn)證，那么還有一個(gè)實(shí)際風(fēng)險(xiǎn)的上界[10]： \begin{equation} \mathbb{E}[P(error)]\leq\frac{\mathbb{E}[Number\;of\;support\;vectors]}{Number\;of\;training\;samples} \end{equation} 其中\(zhòng)(\mathbb{E}[P(error)]\)是在\(m-1\)個(gè)樣本上訓(xùn)練后用剩下的一個(gè)樣本測(cè)試得到的風(fēng)險(xiǎn)期望，\(\mathbb{E}[Number\;of\;support\;vectors]\)是支持向量的期望值。這個(gè)上界的產(chǎn)生是出于這樣的一個(gè)思想：僅僅支持向量的變化才會(huì)引起超平面的變動(dòng)，致使在最壞的情況下所有的支持向量都被誤分類。但是據(jù)[10]指出：很多情形下即使支持向量數(shù)目減少了，實(shí)際的誤差也還是會(huì)增大。所以，該上界不能提供準(zhǔn)確的錯(cuò)誤信息。即便如此，我們卻可以根據(jù)這個(gè)現(xiàn)象得出一個(gè)結(jié)論： 支持向量的數(shù)目不能作為衡量SVM泛化性能的指標(biāo) 。?

那么在實(shí)際應(yīng)用中，我們又如何選擇合適的模型？模型選擇[6]方法很多，大家最為熟悉的交叉驗(yàn)證(Cross Validation)就是其中之一。下面只簡(jiǎn)要介紹結(jié)構(gòu)風(fēng)險(xiǎn)最小化的內(nèi)容。

Structure Risk Minimization

在機(jī)器學(xué)習(xí)中，我們必須根據(jù)有限的訓(xùn)練數(shù)據(jù)選擇一個(gè)泛化模型(假設(shè)函數(shù))來(lái)完成后續(xù)的預(yù)測(cè)任務(wù)，而選出來(lái)的這個(gè)泛化模型很有可能存在過(guò)擬合問(wèn)題，即在訓(xùn)練數(shù)據(jù)上能很好擬合數(shù)據(jù)，但是在新數(shù)據(jù)上的預(yù)測(cè)結(jié)果卻非常糟糕。結(jié)構(gòu)風(fēng)險(xiǎn)定義為經(jīng)驗(yàn)風(fēng)險(xiǎn)與VC置信度之和，構(gòu)成了泛化誤差的上界。結(jié)構(gòu)風(fēng)險(xiǎn)最小化(Structure Risk Minimization, SRM)[7]通過(guò)在模型復(fù)雜度和訓(xùn)練數(shù)據(jù)上的擬合程度之間尋找一個(gè)平衡點(diǎn)，以解決過(guò)擬合問(wèn)題，這也是VC維的一個(gè)應(yīng)用場(chǎng)合。 結(jié)合圖7，我們將結(jié)構(gòu)風(fēng)險(xiǎn)最小化的步驟簡(jiǎn)要描述為如下四步:

1. 根據(jù)先驗(yàn)知識(shí)選擇一種類型的假設(shè)函數(shù)形成假設(shè)集合\(\mathcal{H}\)，比如\(n\)次多項(xiàng)式或者有\(zhòng)(n\)個(gè)隱含結(jié)點(diǎn)的三層神經(jīng)網(wǎng)絡(luò)；
2. 根據(jù)模型復(fù)雜度(VC維)遞增的順序?qū)(\mathcal{H}\)劃分成若干逐層嵌套的假設(shè)集合\(\mathcal{H}_1\subseteq\mathcal{H}_2\subseteq\mathcal{H}_3\subseteq\cdots\subseteq\mathcal{H}\)，比如\(\mathcal{H}_t\)可以是對(duì)應(yīng)\(t\)次多項(xiàng)式的假設(shè)函數(shù)集合；
3. 依次在每個(gè)\(\mathcal{H}_t\)上以經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化為原則選擇假設(shè)函數(shù)\(\hat{h}_t\in\mathcal{H}_t\);
4. 選擇使泛化誤差上界(經(jīng)驗(yàn)風(fēng)險(xiǎn)+VC置信度)最小的模型為最優(yōu)模型，在上界相同的情形下優(yōu)先選擇復(fù)雜度最低的模型。

References

[1] Chernoff bound. http://en.wikipedia.org/wiki/Chernoff_bound .

[2] Empirical risk minimization. http://en.wikipedia.org/wiki/Empirical_risk_minimization .

[3] Hoeffding’s inequality. http://en.wikipedia.org/wiki/Hoeffding’s_inequality .

[4] Jensen’s inequality. http://en.wikipedia.org/wiki/Jensen’s_inequality .

[5] Markov’s inequality. http://en.wikipedia.org/wiki/Markov_inequality .

[6] Model selection. http://en.wikipedia.org/wiki/Model_selection .

[7] Structural risk minimization. http://www.svms.org/srm/ .

[8] Union bound. http://en.wikipedia.org/wiki/Boole’s_inequality .

[9] VC dimension. http://www.svms.org/vc-dimension/ .

[10] Christopher JC Burges. A tutorial on support vector machines for pattern recognition. Data mining and knowledge discovery, 2(2):121–167, 1998.

[11] Vapnik-chervonenkis learning theory. http://cmp.felk.cvut.cz/~hlavac/TeachPresEn/31PattRecog/27VapnikChervonenkis.pdf

Learning Theory