台大線上課程的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
