如何通俗的理解機器學習中的VC維、shatter和break point？

12-13

學習VC維要先知道的概念有：增長函數（growth function）、對分（dichotomy）、打散（shattering）和斷點（break point）

1.增長函數

增長函數表示假設空間H對m個示例所能賦予標記的最大可能結果數。

比如說現在數據集有兩個數據點，考慮一種二分類的情況，可以將其分類成A或者B，則可能的值有：AA、AB、BA和BB，所以這裡增長函數的值為4.

增長函數值越大則假設空間H的表示能力越強，複雜度也越高，學習任務的適應能力越強。不過儘管H中可以有無窮多的假設h，但是增長函數卻不是無窮大的：對於m個示例的數據集，最多只能有 $2^m$ 個標記結果，而且很多情況下也達不到 $2^m$ 的情況。

2.對分

對於二分類問題來說，H中的假設對D中m個示例賦予標記的每種可能結果稱為對D的一種對分（dichotomy）。對分也是增長函數的一種上限。

3.打散

打散指的是假設空間H能實現數據集D上全部示例的對分，即增長函數= $2^m$ 。但是認識到不打散是什麼則更加重要——

有些情況下H的增長函數不可以達到對應的 $2^m$ 值，比如說在二維實平面上的線性劃分情況中，以下的情況就不可以線性可分（也就是說不能算作賦予標記的結果）：

或者下圖這個

雖然圖畫的非常直擊靈魂，但是你應該可以體會到這種情況下二維平面的線性分類器是不可以給上面的情況分類的（事實上對於任何集合，其 $2^4$ =16種對分中至少有一種不能被線性劃分實現）

4.Vapink-Chervonenkis Dimension

現在可以引出VC維的定義了——

假設空間H的VC維是能被H打散的最大的示例集（數據集）的大小，即有：
$VC(H)=max{m:prod(m)=2^m}$
其中 $prod(m)$ 為假設空間在數據集大小為m時的增長函數。

或者有這種更平實的定義——

對於一個假設空間H，如果存在m個數據樣本能夠被假設空間H中的函數按所有可能的 $2^h$ 種形式分開，則稱假設空間H能夠把m個數據樣本打散（shatter）。假設空間H的VC維就是能打散的最大數據樣本數目m。若對任意數目的數據樣本都有函數能將它們shatter，則假設空間H的VC維為無窮大。

在上面那個4個點的圖中，因為4個點的情況下以及不能做到對分，所以二維實平面上所有線性劃分構成的假設空間H的VC維為3.

5.Break Point

在一些教課書中並沒有提出Break Point的概念，這是林軒田《機器學習基石》公開課里的一種輔助概念。現在簡單說一下break point的意義——我們希望假設空間H的增長函數越小越好（這樣子假設空間比較簡單），或者至少不要增長的太快——如果按照 $2^m$ 這種趨勢增長那簡直是沒天理了。上面說道了，隨著m的增大，一定會出現一個m使假設空間無法shatter。這種不滿足 $2^m$ 的情況說明增長函數從這個點開始變緩了，是一個可喜可賀的重大突破，所以我們把第一個不滿足shatter的m值稱為break point（這裡翻譯成突破點）

給個不啰嗦的定義——

If no k inputs can be shattered by H , call k a break point for H .

從這個定義上看某個假設空間H的VC維數就是最大的非break point值，也就是break point-1.

參考資料

[1]周志華. 機器學習[M]. 清華大學出版社, 2016.

[2]沙伊?沙萊夫-施瓦茨, 沙伊?本-戴維. 深入理解機器學習:從原理到演算法[M]. 機械工業出版社, 2016.

[3]Abumostafa Y S, Magdonismail M, Lin H T. Learning from Data: A Short Course[J]. Amlbook, 2012.

[4]白鵬. 支持向量機理論及工程應用實例[M]. 西安電子科技大學出版社, 2008.

我來大致解釋一下這三個概念吧。從邏輯和知識理解的先後順序上來說，應該是先知道shatter，然後是break point，最後才是VC Dimension。

*為了便於理解，我們在binary target function的範疇內討論

首先，假定我們的Hypothesis Set H是一個Binary function的集合，當我們將一個大小為N的sample data set(記作 $[x_{1},x_{2},...,x_{N-1}]$ )作為H中的一個hypothesis h的輸入的時候，我們就會得到一個長度為N的tuple，形如 $[(h(x_{1}),h(x_{2}),...,h(x_{N}))]$ ，而這個tuple中的每個元素都是+1或者-1，我們把這樣的一個tuple就稱作為一個Dichotomy。

然後，我們定義，對於一個Hypothesis Set H來說， $[H(x_{1},x_{2},...,x_{N})]$ 是 H在sample（ $[x_{1},x_{2},...,x_{N}]$ ）上所有dichotomy的集合。

這樣定義有啥好處呢？簡單地解釋一下。要知道，我們定義並發明這些概念的原因，在於我們以前是無法約束hypothesis的數量的。在Hoeffding"s Inequality中,

$[P[mid E_{in}-E_{out}mid>epsilon]]$ $[leq2Me^{-2epsilon^2N}]$ ，

RHS中的M，也就是Hypothesis Set H的勢，為無窮大。同樣，在Generalization Bound中，

$[E_{out}(g) leq]$ $E_{in}(g)+$ $(frac{1}{2N}ln$ $frac{2M}{delta}$ $)^{frac{1}{2}}$ ，

也出現了同樣的問題，導致我們根本無法判斷 $E_{in}$ 到底能不能夠很好地估計 $E_{out}$ ，也就使得我們無法判斷Learning的feasibility。而這裡的一系列概念，就是要找到一個能夠替代這個大M的有限的一個值，從而說明我們是可以做到Learning，不管能做到多好。

就差最後一個概念了，那就是Growth function。Growth function是什麼呢，請不要執著於這個奇怪的名字，說白了對於一個Hypothesis Set H來說，它的Growth function就是它在任意N個點上所能產生的最多的dichotomy的數量，記作 $m_{H}(N)$ 。那麼這個Growth function和前面所提的H在sample上所有的dichotomy的集合的勢有什麼區別呢？區別就在於這個Growth function是指針對任意N個點的最多的dichotomy數，而前面的集合是指對於特定的一個data set所能產生的dichotomy的集合。也就是說， $m_{H}(N)$ $=$ $max mid$ $[H(x_{1},x_{2},...,x_{N})]$ $mid$ 。

那麼，我們可以知道一個顯而易見的結論，那就是對於任何H， $m_{H}(N)$ $leq 2^{N}$ （輸入每一個 $[x_{1},x_{2},...,x_{N}]$ 都有兩種可能的return值）。這樣一來，我們首先就把原先的Hypothesis Set H的勢，大M，給極大地縮小了範圍（從無窮到有限），儘管 $2^{N}$ 仍舊是一個不現實的upper bound，但是最起碼我們現在再討論Generalization Bound，我們就可以說我們是可以約束RHS的。我覺得把Growth function看成是有效假設(Effective hypotheses)更加容易理解，也就是Growth function代表的是真正能得出不同結果的，有意義的Hypothesis的最大數量。

現在，鋪墊了這麼久，我們終於就可以來講shatter了。如果H能在data set（ $[x_{1},x_{2},...,x_{N}]$ ）上產生所有的dichotomy，那麼我們就說H可以shatter $[x_{1},x_{2},...,x_{N}]$ 。舉兩個例子。

Ex. input data set $X$ 為2D中的三個點，這三個點能夠組成一個等邊三角形；定義H為所有直線，若一個點在直線的一邊，則return +1，否則return -1，請問H能夠shatter這個 $X$ 嗎？（並不規定直線的哪一邊為+1，也就是說兩種情況都可以）

可以。

Ex. input data set $X$ 為2D中的四個點，這四個點能夠組成一個正方先；定義H為所有直線，若一個點在直線的一邊，則return +1，否則return -1，請問H能夠shatter這個 $X$ 嗎？

不可以。多嘗試幾次便可以發現，無論如何，起碼有以下這一種dichotomy是無法得到的：

將四個點從左上角開始順時針命名為 $x_{1},x_{2},x_{3},x_{4}$ ，不難發現， $x_{1},x_{3}$ return +1， $x_{2},x_{4}$ return -1，是不會發生的。對於這個H， $m_{H}(4)=14$

顯然，如果H能夠shatter 一個大小為N的data set，那麼可知 $m_{H}(N)=2^{N}$

換言之，H可以shatter $[x_{1},x_{2},...,x_{N}]$ $Rightarrow$ $m_{H}(N)=2^{N}$

那麼，另一個方向上，是不是 $m_{H}(N)$ $=2^{N}$ $Rightarrow$ H能shatter任意 $[x_{1},x_{2},...,x_{N}]$ 呢？

我們來看一個例子。

Ex. input data set $X$ 為2D中的N個點；定義H為所有convex set，若一個點在一個convex set中，則return +1，否則return -1，請問H能夠shatter這個 $X$ 嗎？（convex set為一個這樣的多邊形：若一個多邊形任意兩個頂點之間的連線完全在這個多邊形內，那麼它就是一個convex set。總之理解起來只要知道這個形狀總是凸出來，不是凹進去的就行了。）

這個例子中， $m_{H}(N)$ $=2^{N}$ 。為什麼呢？假設這N個點都在某個圓的圓周上，那麼是不是對於每一個dichotomy，我只要把我需要return +1的那些點作為頂點，連接起來，構成一個convex set，剩下的點就自然而然在這個convex set以外了，所以任何一個dichotomy我都可以從這個特定的圓上得到。然而，H能shatter任意 $[x_{1},x_{2},...,x_{N}]$ 嗎？顯然是不能的。如果我在這個平面上隨機產生大量的點，現實中是幾乎不可能出現能夠產生所有dichotomy的情況的。而先前在求 $m_{H}(N)$ 時，我們考慮的是理想情況，求的是dichotomy數的最大值，所以即是我們知道一個H的Growth function已經等於其上限 $2^{N}$ ，我們無法判斷對於某個特定的data set，這個H能不能夠shatter。

那麼，我們發現，儘管現在我們把一個無窮的範圍縮小到了有限的 $2^{N}$ ，這個數字仍舊是大得可怕的。而且，讓我們苦惱的是，如果我們觀察Hoeffding"s Inequality，不難發現，RHS中，即使我們將大M替換成了 $2^{N}$ ，我們還是很難判斷， $e^{-2epsilon^2N}$ 到底能夠有效地抵消 $2^{N}$ 增長地速度，從而使bound有效地收斂；換言之，我們仍舊無法判斷Learning是不是feasible的。這時我們就需要break point來進一步幫助我們縮小範圍了。

我們定義，如果任意一個大小為k的data set都不能被H shatter，我們就把k稱作是H的break point。一般我們所指的都是最小的這樣的k，因為顯然如果任意大小為k的data set都不能被H shatter，那麼任意大小為k+1的勢必也不能被H shatter。

我們看先前的兩個例子。

Ex. 定義H為一個平面中的所有直線，若一個點在直線的一邊，則return +1，否則return -1。

先前的例子中我們已經看到，對於N=3時，Growth function的值為8， $m_{H}(N)=2^{N}$ ；N=4時，嘗試一下便可知，Growth function的值為14， $m_{H}(N)$ $<2^{N}$ 。故對於這個H來說，break point k為4。

那麼break point有什麼用呢？其實，不難發現，對於一個H，break point如果存在（此處指break point是一個有限的數而不是無窮），那麼 $m_{H}(N)$ $<2^{N}$ ；然後，經過一系列繁複的數學論證，我們可以得出一個結論，那就是如果break point存在， $m_{H}(N)$ 就是一個polynomial。此處省略數學論證的過程，如果有興趣我可以再提供證明。那麼我們費了半天功夫說明如果break point存在， $m_{H}(N)$ 就是一個polynomial有什麼用呢？很簡單，如果 $m_{H}(N)$ 是一個polynomial，那麼我們就可以很肯定地把大M以某種方式替換成 $m_{H}(N)$ ，這樣一來我們的Hoeffding"s Inequality和Generalizaiton Bound就明顯可以很好地收斂只要N足夠大，因為約束這個polynomial的是一個指數的函數，絕對上比polynomial要有效。換句話說，如果break point存在，我們就可以拍桌子說，Learning是可行的。

那麼，VC Dimension是啥呢？我們定義，對於一個H，它的Vapnik-Chervonenkis Dimension為使得 $m_{H}(N)=2^{N}$ 的最大的N，記作 $d_{vc}(H)$ 。如果Growth function恆等於 $2^{N}$ ，那麼 $d_{vc}(H)$ 為無窮。

其實，H的VC Dimension就是H的k-1，因為根據定義，對於 $N>d_{vc}$ ， $m_{H}(N)$ $<2^{N}$

更有用的是，VC Dimension就是我們先前所提到的那個polynomial的order，這一部分得需要略去的數學論證來得出，所以知道就行。

那麼，實際上，通過數學論證，我們還可以把 $m_{H}(N)$ 進一步縮小，結論是：

$m_{H}(N)$ $leq N^{d_{vc}}+1$ ，這可以通過induction來證明，也需要前面的數學論證為基礎。

現在，再通過相當複雜的論證，我們就可以把先前的Generalization Bound在VC Dimension的基礎上進一步約束，將大M替換為有限並有效的值。這裡只講一下結論，中間數學論證並不會影響邏輯上的理解。VC Generalization Bound:

$E_{out}(g) leq E_{in}(g)$ $+(frac{8}{N}ln$ $frac{4m_{H}(2N)}{delta}$ $)^{frac{1}{2}}$

雖然是一個相當loose的bound，不信的話可以自己隨意構想一個情況然後計算一下bound，但是起碼現在我們就可以肯定，有理有據，證據確鑿地說：Learning is feasible.

參考

Abu-Mostafa, Yaser S., Malik Magdon-Ismail, and Hsuan-Tien Lin. Learning from data: a short course. S. l.: AML, 2012. Print.

-------------------------------------------------------------------------------------------------------------------

4/25

有位朋友對於以上提到的結論「如果break point存在， $m_{H}(N)$ 就是一個polynomial」的數學證明有所興趣，在此特地補充一下證明過程。

要證明這個定理，我們主要用的是遞歸和歸納。

首先，我們定義： $[B(N,k)]$ 為在N個點上，使得這N個點的任意大小為k的子集都不能被shattered的最大的dichotomy的數量。

根據定義，我們可知，如果k是某一個 $H$ 的break point，那麼 $m_{H}(N) leq B(N,k)$ 。

那麼我們求幾個特殊情況下的 $[B(N,k)]$ 。

從k=1或者N=1開始，顯然， $B(N,1)=1$ , $B(1,k)=2$ （k&>1時）

現在我們觀察 $N geq2$ 以及 $k geq 2$ 的情況。

對於這N個點，我們把它們記作( $[x_{1},x_{2},...,x_{N-1}]$ )。現在我們要把所有的dichotomy分類一下。其實，每一個dichotomy就是一個長度為N的tuple，其中每個元素都為+1或-1。那麼，我們現在把這個tuple的位置用1到N來表示，然後把所有dichotomy分成三個組， $S_{1}$ , $S_{2}^{+}$ , $S_{2}^{-}$ 。怎麼分呢？對於每個dichotomy所形成的tuple，我們先不看N號位上的元素。然後我們看前面N-1個位置的元素，如果我們發現有兩個tuple，它們從1到N-1號位上所有的元素都一樣，那麼我們就把這兩個tuple中，N號位上為+1的放在 $S_{2}^{+}$ ，N號位上為-1的放在 $S_{2}^{-}$ 。其餘剩下的，也就是那些1到N-1號位上元素互相都不重複的tuple，放在 $S_{1}$ 。我們把 $S_{1}$ 的大小設為 $alpha$ ，把 $S_{2}^{+}$ 的大小設為 $eta$ ，顯然 $S_{2}^{-}$ 的大小也是 $eta$ ，因為這兩個集合中的元素都是互相成對的，否則它們就會出現在 $S_{1}$ 里。 $alpha+eta$ 就是所有dichotomy的數量。對於每一對N和k，我們都可以把所產生的dichotomy這樣來分類，也都能找到這樣的 $alpha$ 和 $eta$ 使得 $B(N,k)=alpha+2eta$ 。

那麼，在 $[x_{1},x_{2},...,x_{N-1}]$ 上，所能產生的dichotomy的數量就是 $alpha+eta$ 。

然後，因為在 $S_{2}^{+}$ 中， $[x_{1},x_{2},...,x_{N-1}]$ 中任意k-1個點都無法被 $S_{2}^{+}$ 中的dichotomy shatter（否則的話 $S_{2}^{+}$ 和 $S_{2}^{-}$ 就可以shatter一個大小為k的子集了）

所以， $eta leq B(N-1,k-1)$

這樣，我們把上面的這兩個不等式一合併，就有

$B(N,k) leq B(N-1,k)+B(N-1,k-1)$

這個不等式是相當關鍵的。

現在我們要用這個結論來證明一個 lemma

Sauer"s Lemma: $B(N,k) leq sum_{i=0}^{k-1}$ $left(egin{array}{c}N\ iend{array} ight)$

證明過程如下：

首先，通過觀察可知k=1或者N=1時這個lemma是對的。

然後，假定這個定理對於小於 $N_{0}$ 的所有N以及所有k都是正確的。

我們需要證明這個定理對於 $N=N_{0}+1$ 以及所有k也是正確的。

因為我們已知當k=1時，定理對於所有N都是正確的，我們只要關注 $k leq 2$ 的情況。

$B(N_{0}+1,k) leq$ $B(N_{0},k)+B(N_{0},k-1)$ $=sum_{i=0}^{k-1}$ $left(egin{array}{c}N_{0}\ iend{array} ight)$ $+sum_{i=0}^{k-2}$ $left(egin{array}{c}N_{0}\ iend{array} ight)$ $=1+sum_{i=1}^{k-1}$ $left(egin{array}{c}N_{0}\ iend{array} ight)$ $+sum_{i=1}^{k-1}$ $left(egin{array}{c}N_{0}\ i-1end{array} ight)$ $=1+sum_{i=1}^{k-1}$ $left[left(egin{array}{c}N_{0}\ iend{array} ight)+left(egin{array}{c}N_{0}\ i-1end{array} ight)) ight]$ $=1+sum_{i=1}^{k-1}left(egin{array}{c}N_{0}+1\ iend{array} ight) = sum_{i=0}^{k-1}left(egin{array}{c}N_{0}+1\ iend{array} ight)$

Q.E.D

所以，我們可知，如果 $m_{H}(k)<2^k$ ，那麼 $m_{H}(N) leq sum_{i=0}^{k-1} left(egin{array}{c}N\ iend{array} ight)$ ，而且RHS的最高次項的次數為k-1。

通俗來講，舉個例子吧。假如妳想訓練出這樣一個模型：根據人的身高和體重來預測這個人美還是丑。這是一個簡單的二分類問題。

現在想像你面前有一個平面直角坐標系。橫軸（x軸）代表人的身高，縱軸（y軸）代表人的體重。

現在咱們拍腦袋決定：咱們的模型應該是線性的（就是一條直線）。通俗來講，在妳的平面直角坐標系裡，妳畫一條線，這條線就把美人和醜人分開了。這條線就是我們最終的模型。

現在咱們要開始往平面直角坐標系放數據了。

假設咱只有兩組數據（就是說咱們的坐標系裡只有兩個點）。這兩組數據隨機組合，一共有3種情況。
第一種情況：咱們有兩個美人的數據
第二種情況：咱們有兩個醜人的數據
第三種情況：咱們有一美一丑的數據
無論是哪一種情況，咱們都可以通過一條線把美人和醜人分開。這說明：線性的模型是完全可以shatter兩組數據的。

但假如說咱們有四組數據（坐標系裡有四個點）。咱們就無法保證線性模型可以完全解釋所有數據的可能性了。例如咱們的數據是（180cm, 50kg）=美，（10cm, 10kg）=美，（180cm, 10kg）= 丑還有(10cm, 50kg）=丑。對於這組數據，咱無論怎麼畫直線，都沒有辦法把美和丑分開在直線兩側。這說明：線性的模型是沒有辦法Shatter 4組數據的。

假如說咱們有三組數據，還是總可以通過畫線的方式把美/丑分開的。（大家仔細想一想）。

所以，線性模型在這種二維數據的情況下的VC dimension 是3。（因為線性模型最多能Shatter3組數據）

現在，假如說我們突然改變主意了：咱們的模型可以是非線性的。那非線性模型的VC dimension可就高了。想像一下，一條曲線是不是理論上可以把坐標系裡的所有美醜都分開？

所以通俗的理解： VC dimension就是某類模型對數據數量的包容性。VC dimension越高，就說明包容性越強。

說了這麼多，VC dimension到底有什麼用呢？簡單來說，VC dimension可以幫助我們選擇更好的模型。所謂「更好」的模型，可以理解為風險（risk)更低的模型。

如何估計模型的風險呢？咱們有這個公式：
真正的風險 &< 根據已有數據計算出的風險 +f(VC dimension)

f(VC dimension)是一個以VC dimension為變數的函數。咱們要選擇的模型，一定要使f(VC dimension)低，這樣真正的風險就會低。風險低的模型就更好。

Ps: 我上面說的可能不完全準確。只是為了盡量通俗地把概念說明白。

簡單通俗的說。

VC維是模型的複雜程度，模型假設空間越大，VC維越高。
shatter和break point是VC維理論中的概念。shatter是指模型假設把數據打碎了，也就是區分開了。而break point是指當模型複雜度變的足夠高了後，可以把數據打的足夠散的一個數學臨界點。

更重要的是，VC維的實踐意義是給機器學習可學性提供了理論支撐。
1. 測試集合的loss是否和訓練集合的loss接近？VC維越小，理論越接近。
2. 訓練集合的loss是否足夠小？VC維越大，loss理論越小。

一般工業實踐中通過引入正則對模型複雜度(VC維)進行控制，平衡這兩個問題的矛盾。

如果想深入理解，推薦看看騰訊廣點通團隊的這個技術博客：VC維的來龍去脈 | 火光搖曳。個人認為總結的很好。