Max Number of Dichotomies

線上課程，Machine Learning Foundations，提到了 mH(N)：

中文解釋為，在N個點裡，找出最大數量的 Dichotomy。數學式子定義如下，它是一個Dichotomy Set的Growth Function，裡面的H，代表Dichotomy Set。如何解釋它呢？

在解釋它之前，先了解什麼是Dichotomy。但在之前，還得先了解什麼是Hypothesis。所以要過好幾關，才能徹底了解此Growth Function。

先說，什麼是Hypothesis。

依照定義

意思是，給1個點x，輸出為+1 (用O表示) 或 -1 (用X表示)，用來區別。我們可以用平面上，有3個點的2D perceptrons，來解釋。亦即，平面上有3個點，我們可以找到很多條線，來區分這3個點。一條線，就是一個 hypothesis，如下圖所示。

我們可以找到3條線，將x1與x2歸為+1類，x3歸為-1類。

h1(x1) = +1	h2(x1) = +1	h3(x1) = +1
h1(x2) = +1	h2(x2) = +1	h3(x2) = +1
h1(x3) = -1	h2(x3) = -1	h3(x3) = -1

當然不只這3條，會有無線多條。

什麼是Hypothesis Set？用數學式子定義如下

我們用上面的例子，來了解這個定義

H = {h1, h2, h3, …}

所以Hypothesis Set數量為

|H| = 無限多

因為我們不想處理無限多的hypothesis，所以想找一個方法，取代hypothesis，就是dichotomy。從上面的表格得知，用這3個hypothesis：h1、h2、h3，區分3個點的結果都是一樣的。所以我們可以將這3個hypothesis歸為一類，稱為dichotomy，用新的h1代表之，以取代舊的h1、h2、h3、……會有無限多的hypothesis。

h1(x1, x2, x3) = OOX

接下來，我們要探討，最多有幾個Dichotomy？

Dichotomy Set

H (x1, x2, …, xN) = {h1, h2, …}

請注意，這裡的H，指的是Dichotomy Set，而非Hypothesis Set。此Dichotomy Set最大的數量為

|H| <= 2N

我們回到原來用Growth Function表示Max Number of Dichotomies的式子

mH(N)的上限就是2N, 數學表示如下

mH(N) <= 2N

但實際上，對於2D Perceptrons而言，當N>=4，Dichotomies數量不會到達2N。

我們用N=3，也就是3個點為例，用2D Perceptrons來看，會有幾個Dichotomy。我們用兩種情況，Case 1和Case 2，來算Dichotomy的數量。

Case 1是3個點不在同一條直線上，他的Dichotomy數量為8。Case 2是3個點剛好在一條直線上，他的Dichotomy數量為6。為何一個是8，一個是6？圖示如下：

這兩個Case，整理如下：

Case 1	Case 2
h1 (x1, x2, x3) = OOO h2 (x1, x2, x3) = OOX h3 (x1, x2, x3) = OXO h4 (x1, x2, x3) = OXX h5 (x1, x2, x3) = XOO h6 (x1, x2, x3) = XOX h7 (x1, x2, x3) = XXO h8 (x1, x2, x3) = XXX	h1 (x1, x2, x3) = OOO h2 (x1, x2, x3) = OOX h4 (x1, x2, x3) = OXX h5 (x1, x2, x3) = XOO h7 (x1, x2, x3) = XXO h8 (x1, x2, x3) = XXX
H (x1, x2, x3) = {   h1, h2, h3, h4,    h5, h6, h7, h8   }	H (x1, x2, x3) = {   h1, h2, h4,    h5, h7, h8   }
|H (x1, x2, x3)| = 8	|H (x1, x2, x3)| = 6

合併Case 1和Case 2

|H(x1, x2, x3)| = 8 or 6

將N=3的2 D Perceptrons，套用在下面這個式子

mH(3) = max(6, 8) = 8

這樣一來，對於max和H，是否能清楚了解？

至於，式子中的x1, x2, …, xN，代表什麼意思？

以N = 3來看，就是3個點。x1, x2, x3，代表平面上的任意3個點。這3個點的組合會有無限多個，我們僅拿2種代表性的3個點，來看。Case 1是取任意3個不在同一直線上的點，Case 2是取任意3個在同一直線上的點。當然，還有許多特殊的Case，如2個或3個點重疊，這種Case，不需要特別關注。

-Count