台大線上課程的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)
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
沒有留言:
張貼留言