Machine Learning Foundations 作業二 Question 4

http://blog.csdn.net/countchu/article/details/79152973

台大線上課程的Machine Learning Foundations，作業二的Question 4

如何解這道題目？我們可以寫一支python解這道題目。

如，求Original VC Bound的epsilon (error) 的上限為多少，我們就會定義一個function：

def errorForOriginalVcBound (N, sigma):

然後將數學式子寫成代碼，放進去就好了。但這時候，遇到一個問題，如何用程式表達mH？還記得VC Dimension嗎？：

我們可以將mH(N)換成N^dvc，如此一來，式子就寫成：

於是，我們的function，多了一個參數，叫dvc：

def errorForOriginalVcBound (dvc, N, sigma):

也可以用Python定義一個function叫mH，覆用之。

def mH (N, dvc):

    return math.pow (N, dvc)

Error for Original VC Bound的實作

def errorForOriginalVcBound (dvc, N, sigma):

    value = 4 * mH (2*N, dvc) / sigma

    value = 8 * np.log (value) / N

    value = math.sqrt (value)

    return value

接下來是 Error for Rademacher Penalty Bound的實作，

def errorForRademacherPenaltyBound (dvc, N, sigma):

    value1 = 2 * N * mH (N, dvc)

    value1 = 2 * np.log (value1) / N

    value1 = math.sqrt (value1)

    value2 = (2/N) * np.log (1/sigma)

    value2 = math.sqrt (value2)

    value3 = 1/N

    return value1 + value2 + value3

再來是Error for Parrondo and Van den Broek的實作。但我們發現一個問題，就是公式的左右邊，都有一個epsilon。有兩種解法，

第1種解法，是用一元二次求x解的公式，x就是epsilon：

ax^2 + bx + c = 0

這樣，就可以推導出，只有左邊有epsilon的式子出來。於是，我們就把式子的右邊，寫成代碼即可。這是數學家的作法。

第2種解法，將epsilon當成一個參數。至於要給什麼樣的值，我們可以先觀察其它的式子算出來的結果，再做決定。我選擇第2種解法，於是，Error for Parrondo and Van den Broek的實作如下：

def errorForParrondoAndVanDenBroek (dvc, N, sigma, epsilon):

    value = 6 * mH (2*N, dvc) / sigma

    value = 2 * epsilon + np.log (value)

    value = math.sqrt ((1/N) * value)

    return value

對於Devroye而言，也是公式的左右兩邊，都有一個epsilon。實作的方法與剛才的Parrondo相同：

def errorForDevroye (dvc, N, sigma, epsilon):

    value = np.log (4) + dvc * np.log (N * N) - np.log (epsilon)

    value = 4 * epsilon * (1 + epsilon) + value

    value = (1/(2*N)) * value

    value = math.sqrt (value)

    return value

這裡有一個問題是，為何function的第一行要這麼寫？那是因為當N=10000時，直接計算，數字太大，電腦無法處理。我們可用以用對數運算，將式子拆解成電腦可以處理的單元，如下：

最後是Variant VC Bound的實作：

def errorVariantVcBound (dvc, N, sigma):

    value = 2 * mH (N, dvc)

    value = value / math.sqrt (sigma)

    value = np.log (value)

    value = (16.0 / N) * value

    value = math.sqrt (value)

    return value

所以，我們現在有5個functions，依據題目的順序排列：

errorForOriginalVcBound

errorForRademacherPenaltyBound

errorForParrondoAndVanDenBroek

errorForDevroye

errorVariantVcBound

其中，errorForParrondoAndVanDenBroek和errorForDevroye因為都需要epsilon參數，而我們不知道該給那一個值，所以暫不管它。先求其它3個：

    dvc = 50

    sigma = 0.05

    N = 10000

    value1 = errorForOriginalVcBound (dvc, N, sigma)

    print ("Error for Original VC Bound          = ", value1)

    

    value2 = errorForRademacherPenaltyBound (dvc, N, sigma)

    print ("Error for Rademacher Penalty Bound   = ", value2)

    

    value3 = errorVariantVcBound (dvc, N, sigma)

    print ("Error for Variant VC Bound           = ", value3)

發現最小的值是0.3313。我們可以用這個最小的值，當作是epsilon的參數，用在errorForParrondoAndVanDenBroek和errorForDevroye

    epsilon = min ([value1, value2, value3])

    print ("epsilon = ", epsilon)

    value4 = errorForParrondoAndVanDenBroek (dvc, N, sigma, epsilon)

    print ("Error for Parrondo and Van den Broek = ", value4)

    value5 = errorForDevroye (dvc, N, sigma, epsilon)

    print ("Error for Devroye                    = ", value5)

所以，Devroye公式算出來的值，是最小的。

-Count