2018年1月26日 星期五

Machine Learning Foundations 作業二 Question 10 解法

台大線上課程的Machine Learning Foundations,作業二 Question 10:


這個題目的解答,可以參考網路上這位仁兄所寫的:

我也是先參考這篇文章後,思考了一段時間,才真正了解這道題目的意思。想將自己理解的過程分享大家,故有此文。

在解這道題之前,先了解題目在講什麼?什麼是Simplified Decision Trees?H所代表的是那一種型式的Hypothesis Set?我們很容易被題目裡出現的一大堆不熟悉的數學符號唬住。所以,先了解這些數學符號,才是首要之務。

我們先將d設為2,這樣可以簡化問題,去理解H到底是什麼樣的Hypothesis Set?先看看,這時候,S長什麼樣子?

S a collection of vectors in {0, 1}^2

{0, 1}^2是什麼意思?

請參考WIKI的Cartesian Product (笛卡爾積)


也可以參考 數學指南 實用數學手冊 笛卡爾積 p644, p887, p895

所以:

於是

S a collection of vectors in {0, 1}^2

這句話就是

S a collection of vectors in {(0, 0), (0, 1), (1, 0), (1, 1)}

這又是什麼意思呢?意思是,S的集合裡的元素,是由這4個vector組合而成的:

s1 = (0, 0)
s2 = (0, 1)
s3 = (1, 0)
s4 = (1, 1)

共有幾種這樣的S?這是Power Set的概念,請參考WIKI


所以S共有16種可能。列舉其中幾種可能:

S = empty
S = {s4}
S = {s1, s2}
S = {s1, s3, s4}
S = {s1, s2, s3, s4}

接下來,解釋這個式子:

還是一頭霧水,到底這個式子是在講什麼?有數學式子是這樣寫的嗎?我們把i拆解開來:

因為 d = 2,所以 i = 1, 2。

v1 = [[ x1 > t1 ]]
v2 = [[ x2 > t2 ]]

還好我寫過程式,可以用程式的角度去想,>做的是邏輯運算,若成立,就是1,否則為0。那麼,為何要被 [[ 和 ]] 包圍起來?這是要強調被 [[ 和 ]] 包圍起來,表示裡面是在做邏輯運算,其結果不是1就是0。舉一例:

x = (3, 4)
t = (5, 2)

v1 = [[x1 > t1]] = [[3 > 5]] = 0
v2 = [[x2 > t2]] = [[4 > 2]] = 1

v = (v1, v2) = (0, 1)

所以我們發現,原來

是在做座標轉換。什麼意思?畫圖表示:

接下來,解釋這道式子:

先看看這個意思。

被 [[ 與 ]] 包圍的,就是在做邏輯運算。意思就是,當v屬於S,則為1,否則為0。舉兩個例子:

Case 1:


Case 2:

這樣大家是不是了解H所代表的Hypothesis Set長什麼樣子的吧?其實很簡單,就是當d=2的情況下,以t為中心,將平面切成4個區域:s1, s2, s3, s4

該了解的都了解之後,我們可以開始回答問題本身:

What is the VC-dimension of the "simplified decision trees" hypothesis set?

還是一樣,先看d=2的情況,假設有4個點,p1, p2, p3, p4,是否都可以從H找到h來區分這4個點?


共有16個情況,只列前面8種,是因為將前面的8種,反過來,就是後面的8種。這16種情況,都能從H找到h,區分4個點。如上圖,要滿足第2個情況:(p1, p2, p3, p4) = (+, +, +, -),t要擺在那裡?擺在4個點的中間。S要長什麼樣子?如下:


考慮平面上有5個點:p1, p2, p3, p4, p5

p1 = p2 = p3 = p4 = +1
p5 = -1

因為t只能將平面切成4個部份。所以,第5個點,p5,不管怎麼放,都會和另外1個點處在同一區域。如下圖p2和p5處在同一位置。這樣一下,經過座標轉換,p2和p5就貼在一起,變成(1,0)。可是同一個點,不能同時為+1,與-1,所以這種情況不可能發生。


所以:
d = 2, dvc = 4 = 2^2

t能將三維空間,分為8塊,所以:
d = 3, dvc = 8 = 2^3

然後,d維空間,用數學歸納法,可以得到:  
dvc = 2^d

-Count

沒有留言:

張貼留言