2017年9月27日 星期三

The Growth Functions of the Four Hypothesis Sets

台大的線上課程,Machine Learning Foundations,對於以下4種Hypothesis Sets,尋找他們的Growth Functions及Break Points。


對於Postitive Rays、Postitive Intervals、及Convex Sets而言,都可以找到它們的Growth Function,mH(N)。但對於2D Perceptrons而言,就不容易找到mH(N),但可以找到它的上限:

mH(N) < 24, N >= 4

這裡的N = 4,就是此Growth Function的Break Point。

我用Python,將Positive Rays、Postitive Intervals、及Convex Sets,這3種Growth Function畫出折線圖出來。對於2D Perceptrons,因為找不到它的Growth Function,但手繪紅色那條線段,它是介於2D Perceptrons和Convex Set的中間。


橫軸N代表平面上的N個點。縱軸代表最大Dichotomies的數量。每一條折線,代表每一種Hypothesis Set的Growth Function,分別說明如下:
  • Convex Set。不管N有多大,找不到Break Point。
  • Positive Rays。當N = 2時,出現Break Point。
  • Positive Intervals。當N = 3時,出現Break Point。
  • 至於2D Perceptron呢?會在N = 4時,在紅色線上的那一綠色的點,就是BreakPoint。
Python程式如下


-Count

2017年9月26日 星期二

Definition of Dichotomy

上一篇,Max Number of Dichotomies,解釋了什麼是Dichotomy。本篇,再來看看台大的線上課程,Machine Learning Foundations,對於Dichotomy的定義


大家對此定義,是否感到困惑?式子左邊有h,為何右邊也有h?

這有點像是我們在唸文言文,有許多字是一字多義。尤其是「于」這個字,「煢煢僕夫,于彼冀方」這裡的「于」是「往」的意思。「婿立于門外」這裡的「于」是「於」的意思。當然,本人學問沒這麼大,這些例子是從網路上抓下來的。

又想到最近台灣的教育當局,要刪減文言文的比例,個人覺得不算是壞事,原因為何?待我另立篇說明之。學文言文有一個好處就是,不會執著於一個字只能有一個解釋,可以發揮想像力及推演能力,去理解一篇文章。

回到正題。這裡要說的是,左邊的h,指的是Dichotomy。而右邊的h,就是Hypothesis。而Dichotomy是一種很特別的Hypothesis。

先看式子的右邊,這是什麼意思?



這是N個 {X, O} 的笛卡爾積。請參考WIKI的Cartesian Product (笛卡爾積)

N = 2去想這件事 (+1為O,-1為X):



N = 3時:



所以,當N=3時,Dichotomy的個數最多有8個 |h(x1, x2, x3)|

Hypothesis的定義

找到一個hypothesis,h,能區分平面上的3個點為 (+1為O,-1為X)

h(x1) = +1
h(x2) = +1
h(x3) = -1

換一個方式問,能區分平面上的3個點為 +1、+1、-1,的Hypothesis,有幾個?上一篇說明,有無限多個。

我們把所有能區分平面上的3個點為 +1、+1、-1,的Hypothesis,歸為一類,稱為Dichotomy,用符號h',表示之,以區分h。

h'(x1, x2, x3) = (h(x1), h(x2), h(x3)) = (+1, +1, -1)

於是,我們把無限多個Hypothesis,歸為一類,用一個Dichotomy表示。課程裡所提的,式子左邊的h,其實就是h'。因為課程用相同的符號h表達Dichotomy和Hypothesis,造成我們的困擾,有可能是因為我們文言文讀的不夠多的關係。而為何用相同的h代表Dichotomy和Hypothesis?這是因為Dichotomy是一種特殊的Hypothesis。從此以後,課文提到的Hypothesis,其實就是Dichotomy。這樣想,就明白了。

-Count

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