本系列是臺灣大學資訊工程系林軒田（Hsuan-Tien Lin）教授開設的《機器學習基石》課程的梳理，重在梳理，而非詳細的筆記，因此可能會略去一些細節，
該課程共16講，分為4個部分：
- 機器什么時候能夠學習？（When Can Machines Learn？）
- 機器為什么能夠學習？（Why Can Machines Learn？）
- 機器怎樣學習？（How Can Machines Learn？）
- 機器怎樣可以學得更好？（How Can Machines Learn Better？）
本文是第2部分，對應原課程中的4-8講，
本部分的主要內容：
- 用案例引出學習可行性的疑問；
- 詳細介紹VC維理論，它給出了機器學習的可靠性保證；
- 介紹誤差的度量，以及對誤差權重不同的情況的處理方法，
1 學習可行性的疑問
先來一個小學奧數題/公務員考試題：
其實這個題沒有標準答案，以下兩種解答都是對的：
- 對稱為\(+1\)，非對稱為\(-1\)，因此答案是\(+1\)；
- 最左上角的格子白色為\(+1\)，黑色為\(-1\)，因此答案是\(-1\)；
因此，選擇不同的規則，你會獲得不同的答案，那么，如果給你一些歷史資料，機器學習出某種規則，是否也會遇到這樣的情況呢？
2 機器學習的可靠性保證
2.1 Hoeffding不等式
來看另一個問題：有一個罐子，里面裝有許許多多黃色和綠色的小球，該如何估計黃球的比例？
很簡單，抽樣就行了，抽出一部分樣本，計算得到樣本中的黃球比例\(\nu\)，用這個比例作為罐子中的黃球比例\(\mu\)的估計即可，這樣的估計準不準呢？在統計學中，有Hoeffding不等式給出準確率的界限：
\[\mathbb{P}[\vert\nu-\mu\vert>\epsilon]\le 2\exp{(-2\epsilon^2 N)} \]其中\(N\)為抽樣的樣本個數，這個式子的意思是，\(\nu\)和\(\mu\)相差較遠的概率會有一個上限，在大樣本下，這個上限會比較小，因此\(\nu=\mu\)可以叫做概率近似正確（PAC，probably approximately correct），
2.2 機器學習中的Hoeffding不等式
現在將這個程序類比到機器學習中，罐子中的小球對應于\(\mathcal{X}\)中的單個資料\(\mathbf{x}\)，給定假設集中的一個假設\(h\)，罐子中黃球的比例就對應于\(\mathcal{X}\)中使得\(h(\mathbf{x})=f(\mathbf{x})\)的\(\mathbf{x}\)的比例，現在抽取出一部分樣本，這個樣本對應于現有的資料集\(\mathcal{D}\)，我們可以很容易地知道對\(\mathcal{D}\)中每一個資料\((\mathbf{x}_n,y_n)\)是否有\(h(\mathbf{x}_n)=y_n\)，若相等，對應的小球為黃色，反之為綠色，我們的目的，是要知道在整個\(\mathcal{X}\)中滿足\(h(\mathbf{x})=f(\mathbf{x})\)的\(\mathbf{x}\)的比例有多少，
若\(N\)足夠大，且\(\mathbf{x}_n\)為i.i.d.，對于某個固定的\(h\)來說，就可以用已知的\(E_{\text{in}}(h)=\dfrac{1}{N}\sum\limits_{n=1}^{N} \mathbf{1}_{[h(\mathbf{x}_n)\ne y_n]}\)去推斷\(E_{\text{out}}(h)=\mathop{\mathcal{E}}\limits_{\mathbf{x}\sim P}\mathbf{1}_{[h(\mathbf{x})\ne f(\mathbf{x})]}\)，從而判斷該\(h\)的表現如何，如下圖：
根據Hoeffding不等式，就是
\[\mathbb{P}[\vert E_{\text{in}}(h)-E_{\text{out}}(h)\vert>\epsilon]\le 2\exp{(-2\epsilon^2 N)} \]如果\(E_{\text{in}}(h)\)和\(E_{\text{out}}(h)\)足夠接近，并且\(E_{\text{in}}(h)\)足夠小，這就能保證\(E_{\text{out}}(h)\)足夠小，也就能判斷出對于抽樣程序\(P\)，有\(h\approx f\)，
但是，這只能用來判斷某個\(h\)是否足夠好，如果現在是用演算法\(\mathcal{A}\)從假設集\(\mathcal{H}\)中選出一個\(h\)，再套用上面的不等式，就會有問題，試想一下，假設有150個人，每人丟5次硬幣，就有超過99%的概率會出現有某個丟5次硬幣都是正面的人，這能說明他的丟硬幣技術比其他人高嗎？如果選擇他作為我們的“\(g\)”，能保證他以后再去丟硬幣，得到正面的概率也比其他人更大嗎？
同理，如果是從\(\mathcal{H}\)中選出一個在樣本\(\mathcal{D}\)內誤差最小的\(g\)，能保證它在\(\mathcal{D}\)外也是更好的嗎？想要得到這樣的保證，還需對不等式做一些修正，
對每個\(h\)，都可能會有一些\(\mathcal{D}\)，使得\(h\)在它上面的\(E_{\text{in}}(h)\)和真正的\(E_{\text{out}}(h)\)相差很大，把這種\(\mathcal{D}\)稱作“壞的”，Hoeffding不等式本質上是保證抽到壞的\(\mathcal{D}\)的概率有一個上限，記\(\vert\mathcal{H}\vert=M\)，即共有\(M\)個\(h\)，我們想要保證的是不管最后\(\mathcal{A}\)選出了哪個，\(\mathcal{D}\)是“壞的”的概率都有較小的上限，因此，要計算的應該是對至少一個\(h\)來說\(\mathcal{D}\)是“壞的”的概率：
\[\begin{aligned} &\mathbb{P}_{\mathcal{D}}[(\textbf{BAD } \mathcal{D} \text{ for } h_1) \textbf{ or } (\textbf{BAD } \mathcal{D} \text{ for } h_2) \textbf{ or } \ldots \textbf{ or } (\textbf{BAD } \mathcal{D} \text{ for } h_M) ]\\ \le& \mathbb{P}_{\mathcal{D}}[\textbf{BAD } \mathcal{D} \text{ for } h_1] + \mathbb{P}_{\mathcal{D}}[\textbf{BAD } \mathcal{D} \text{ for } h_2] +\ldots+\mathbb{P}_{\mathcal{D}}[\textbf{BAD } \mathcal{D} \text{ for } h_M]\\ \le& 2\exp{(-2\epsilon^2 N)}+2\exp{(-2\epsilon^2 N)}+\ldots+2\exp{(-2\epsilon^2 N)}\\ =& 2M\exp{(-2\epsilon^2 N)} \end{aligned} \]這才是\(\mathcal{A}\)選出來的\(h\)的\(E_{\text{in}}(h)\)和\(E_{\text{out}}(h)\)距離的上限，但在上面的程序中，因為對事件的并集直接用了加的運算，這個上限被放得太大了，由于不同的\(h\)對應的“壞的”\(\mathcal{D}\)很可能有很大重疊，因此真實的上限應該要小得多，如圖：
另外，\(M\)如果是有限的，根據上式，我們還是可以通過增大\(N\)來保證\(E_{\text{in}}(h)\)和\(E_{\text{out}}(h)\)足夠接近，但如果\(M\)是無限的呢？如在PLA中，系數的取值就可以是無限多個，因此PLA的\(M\)是無窮大的，
2.3 VC維
\(M\)為無窮大時，還是有辦法的，盡管PLA的\(M\)是無窮大，但其實，我們可以對它的\(\mathcal{H}\)中的元素進行分類，只要樣本個數是有限的，它的類別就是有限的，比如在只有一個樣本的情況中，二維PLA的\(\mathcal{H}\)中的元素（就是二維平面上的所有直線）可以簡單分為兩類，一類是把該樣本點分為正的，一類是把該樣本點分為負的：
而在兩個樣本的情況中，\(\mathcal{H}\)中的元素可以分為4類：
三個樣本時可分為8類：
但若3個點共線，那么只有6類：
而當有4個樣本時，\(\mathcal{H}\)中的元素最多只能分成14類：
這說明，在PLA中，有\(N\)個樣本時，有效的\(M\)會小于等于\(2^N\)，
接下來，引入幾個概念：
- 二分（Dichotomies）：對\(N\)個樣本，每個樣本都有正負兩種可能，將所有樣本組成的每一種可能稱為一個dichotomy，dichotomies的集合可記為\(\mathcal{H}(\mathbf{x}_1, \mathbf{x}_2, \ldots,\mathbf{x}_N)\)，顯然，集合中元素個數的上限是\(2^N\)；
- 成長函式（Growth Function）：定義成長函式\(m_{\mathcal{H}}(N)=\max\limits_{\mathbf{x}_1, \mathbf{x}_2, \ldots,\mathbf{x}_N \in \mathcal{X}} \vert \mathcal{H}(\mathbf{x}_1, \mathbf{x}_2, \ldots,\mathbf{x}_N) \vert\)，它的上限是\(2^N\)，對于大多數模型（如二維感知機）的\(\mathcal{H}\)來說，\(m_{\mathcal{H}}(N)\)比\(2^N\)小，僅為多項式大小；
- 打散（Shatter）：如果\(\mathcal{H}\)可以完全實作\(N\)個樣本的\(2^N\)種dichotomies，則稱\(N\)個點可被\(\mathcal{H}\)打散；
- 突破點（Break Point）：若\(k\)個點無論如何也無法被\(\mathcal{H}\)打散，則稱\(k\)為\(\mathcal{H}\)的break point，根據定義，所有比\(k\)大的整數也都會成為break points，對于二維感知機來說，從4開始就是它的break point，
接下來就是要找到，break point和\(m_{\mathcal{H}}(N)\)的關系，
我們繼續引入界限函式（Bounding Function）的概念：\(B(N,k)\)，它是當最小的break point為\(k\)時的最大可能\(m_{\mathcal{H}}(N)\)，那么，該如何計算它或者它的上限？
首先，當\(k=2\)時，表示任意兩個點都不能被打散，因此當\(N=2\)時有\(B(2,2)=3\)，即最多能列舉出3種dichotomies（4種就是這兩個點被打散了），當\(N=3\)時有\(B(3,2)=4\)（窮舉法可知），而當\(k=1\)時，由于任何一個點都不能被打散，因此只能有一種dichotomy，即\(B(N,1)=1\)，另外，如果\(k>N\)，由于小于\(k\)個樣本點都能被打散，因此會有\(B(N,k)=2^N\)，而如果\(N=k\)，那么只需在\(2^N\)個被打散的點中拿掉一種dichotomy，就能滿足這\(N\)個點不被打散的概念了，因此有\(B(N,k)=2^N-1\)，
到目前為止，在下面這張函式表中還有一部分沒有計算：
不妨先來看\(B(4,3)\)該如何計算，如果用窮舉法，可以得出\(B(4,3)=11\)：
觀察這11種dichotomies發現，它們可以分成兩組，其中一組的前3個點是有重復的，它們成為不同的dichotomies僅僅是因為\(\mathbf{x}_4\)不同，而另一組的前3個點沒有重復，
如果把前3個點有重復的8種dichotomies記為\(2\alpha\)（只看前3個點就是\(\alpha\)種），后3種記為\(\beta\)，那么就有\(2\alpha+\beta=11\)，而其實，\(B(4,3)\)無非就是比\(B(3,\cdot)\)多了一個點，假設現在把最后一個點去掉，那么前3個點只可能有\(\alpha+\beta\)種dichotomies（因為第一組\(2\alpha\)種是前面3個點各重復兩次，因此需要剔除一半），由于\(B(4,3)\)中任意3個點都不能被打散，因此前3個點也必須不能被打散，所以有\(\alpha+\beta\le B(3,3)\)，
另一方面，由于\(2\alpha\)組中的4個點中，任意3個點都不能被打散，而第4個點是在每一組前3個點固定的情況下取正/負，因此前3個點中的任意2個點都不能被打散（否則在加入第4個點后就會有3個點被打散），因此，必須要保證\(\alpha\le B(3,2)\)，
由此可知，\(B(4,3)=2\alpha+\beta \le B(3,3)+B(3,2)\)，以此類推，有\(B(N,k)\le B(N-1,k)+B(N-1,k-1)\)，最終結果如圖：
用數學歸納法即可證明：\(B(N,k)\le \sum\limits_{i=0}^{k-1}\binom{N}{i}\)，具體程序在此略過，事實上，可以證明得\(B(N,k)=\sum\limits_{i=0}^{k-1}\binom{N}{i}\)，具體的數學程序較復雜，課程中也略過了，該式說明，\(B(N,k)\)中成長最快的一項最多就是\(N^{k-1}\)的成長速度，
由\(B(N,k)\)的定義，只要break point \(k\)存在，那么\(m_{\mathcal{H}}(N)\)的上限就是\(B(N,k)\)，也因此，\(m_{\mathcal{H}}(N)\)中成長最快的一項最多就是\(N^{k-1}\)的成長速度，
在有了\(m_{\mathcal{H}}(N)\)后，想用它取代\(M\)，還需要做一些處理，具體在此略過，最后可以得到的是Vapnik-Chervonenkis（VC） bound：
\[\mathbb{P}[\exists h \in \mathcal{H} \text{ s.t. }\vert E_{\text{in}}(h)-E_{\text{out}}(h)\vert>\epsilon]\le 4 m_{\mathcal{H}}(2N)\exp{(-\dfrac{1}{8}\epsilon^2 N)} \]定義VC維（VC dimension）\(d_{\text{vc}}(\mathcal{H})\)為滿足\(m_{\mathcal{H}}(N)=2^N\)的最大的\(N\)，也即\(\mathcal{H}\)能打散的最大的點的個數，或最小的break point減1，當\(N\ge2\)且\(d_{\text{vc}}\ge 2\)時，有\(m_{\mathcal{H}}(N)\le N^{d_{\text{vc}}}\)，
對于\(d\)維感知機模型來說，有\(d_{\text{vc}}=d+1\)（證明略），只要\(d_{\text{vc}}\)是有限的，就可以完成泛化，\(d_{\text{vc}}(\mathcal{H})\)就相當于是\(\mathcal{H}\)的powerfulness，
2.4 VC Bound與模型復雜度懲罰
對于\(g=\mathcal{A}(\mathcal{D})\in \mathcal{H}\)，如果\(\mathcal{D}\)在統計上足夠大，有
\[\mathbb{P}[\vert E_{\text{in}}(g)-E_{\text{out}}(g)\vert>\epsilon]\le 4 (2N)^{d_{\text{vc}}} \exp{(-\dfrac{1}{8}\epsilon^2 N)} \]不等式左側表示“壞的”的幾率，若將不等式右邊記為\(\delta\)，可將\(\epsilon\)反表示為\(\epsilon=\sqrt{\dfrac{8}{N}\ln{\dfrac{4(2N)^{d_{\text{vc}}}}{\delta}}}=\Omega(N,\mathcal{H},\delta)\)，\(\Omega(N,\mathcal{H},\delta)\)就代表了對模型復雜度的懲罰，
可以看出，至少有\(1-\delta\)的概率，能滿足
\[E_{\text{out}}(g)\le E_{\text{in}}(g)+\Omega(N,\mathcal{H},\delta) \]\(d_{\text{vc}}\)和error的關系如下圖：
要找到最優的\(d_{\text{vc}}\)，才能使error最小，
VC Bound只是一個非常寬松的理論界限，比如設定\(\epsilon=0.1\)，\(\delta=0.1\)，\(d_{\text{vc}}=3\)，那么根據前式，可得到\(N\approx 10,000 d_{\text{vc}}\)，但在實踐中，往往只需要\(N\approx 10 d_{\text{vc}}\)的資料量就夠了，
2.5 有噪聲時的VC Bound
如果標簽被打錯了，或是同一個人被打了不同標簽，又或是\(\mathbf{x}\)的資訊不準確，都會引入噪聲，在有噪聲時，VC Bound依舊有效嗎？
回到之前小球的例子，之前的小球，每個小球的顏色都是確定的，這種情況叫做是“deterministic”的，在有噪聲的情況中，可以認為每個小球的顏色服從某種概率，即\(y\sim P(y|\mathbf{x})\)，這叫做是“probabilistic”的，可以證明如果\((\mathbf{x},y)\mathop{\sim}^{i.i.d.}P(\mathbf{x},y)\)，那么VC理論依舊是有效的，
有噪聲時，學習的目標是在常見的樣本\(P(\mathbf{x})\)上，學習\(P(y|\mathbf{x})\)，新的學習流程如下：
VC理論依舊有效，pocket演算法就是個很好的例子，
3 誤差度量
在這里介紹一種逐點的誤差度量（pointwise error measure），可以表達成\(\text{err}(g(\mathbf{x}), f(\mathbf{x}))\)，\(g(\mathbf{x})\)可記為\(\tilde{y}\)，\(f(\mathbf{x})\)可記為y，
有兩種比較重要的pointwise error measure：
- \(\text{err}(\tilde{y}, y)=\mathbb{1}_{[\tilde{y} \ne y]}\)，這一般用在分類問題中；
- \(\text{err}(\tilde{y}, y)=(\tilde{y} - y)^2\)，這一般用在回歸問題中，
在有了誤差度量后，學習流程如下：
在分類問題中，錯誤可分為兩類，如下圖所示：
根據這兩類錯誤的重要性不同，可以對它們賦予不同的權重，因此，不同的應用可以有不同的\(\text{err}\)，在演算法中考慮誤差度量時（記用在演算法中的錯誤度量為\(\widehat{\text{err}}\)），最好的情況當然是直接令\(\widehat{\text{err}}=\text{err}\)，但這可能會導致很難計算，比如會帶來NP-hard問題等，一般來說，最好要設計一個對于\(\mathcal{A}\)來說能比較容易進行最優化的\(\widehat{\text{err}}\)，最好要有閉式解（closed-form solution）或有凸的目標函式，
在\(\mathcal{A}\)中加入誤差度量的設計后，學習流程如下：
對于兩類錯誤權重不同的情況，可以用“virtual copying”的策略去學習，以pocket演算法為例，假設false reject錯誤的權重為1，false accept錯誤的權重為1000，在計算時不必真的對每個樣本點賦予權重，可以“虛擬地”將\(y=-1\)的點復制1000份，在實踐中，也不必真的復制，可以在隨機選擇樣本點時，讓演算法隨機選出\(y=-1\)的點的概率增大1000倍即可，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/194795.html
標籤：其他
上一篇：在深度學習中對正則化的直觀認識