2017年9月25日 星期一

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

沒有留言:

張貼留言