機器學習_學習筆記系列(02)：怎麼知道機器有在學習?
在機器學習當中，我們也提到了，我的目標是想從輸入資料x和輸出資料y中，找出一個規則f。
但當我們的數據有限，而且我們真的不知道這個規則f的時候，我們怎麼知道這個f是對的。
舉個例子，假如小名，禮拜一和四，晚上待在家裡打電動，禮拜二和五，晚上去健身，禮拜三和六，晚上去逛街，那他禮拜天到底會在家打電動還是去健身還是去逛街呢？
那我們現在就要來告訴大家，要怎麼讓機器真正學習到，能推敲出其中的一些規則，還有推敲規則時，有哪些條件限制。
以下內容引用來源在[1]
首先我們要先引入一個統計實驗為例子，假設有一袋彈珠，裡面只有黑和白兩種顏色，黑色彈珠在袋子裡面的比例為u，白色為1-u，但是我們現在不知道實際比例，所以我們從彈珠裡面拿N個彈珠，算算看黑色幾個，白色幾個，所以我們算出
估計值v=黑色彈珠數量/所有抽出彈珠數量N。
我們也知道當我們抽得越多次，v就會越接近真實比例u，但我們永遠還是不知道u是多少。
所以我們在這裡引入一個式子叫做霍夫丁不等式(Hoeffding's inequality)
這裡的ϵ是我們自己的定義的值。
那這個式子的意義是什麼？首先看到左邊，這裡的意思就是我們實驗的值v和實際值u，相差的大小大於我們所定義的值ϵ的機率。
具體來說，可以把ϵ當成實驗的品質，如果今天ϵ很大，假如|v-u|>ϵ成立，那代表我們的實驗v超級不準，但是超級不準的情況機率很低，所以可以看到當ϵ越大，右邊的值也會越小。當然如果我們將抽彈珠的次數增加，發生超級不準情況的機率就會降低，所以可以看到N增加右邊數值也會減少。
霍夫丁不等式 VS機器學習
那這個不等式和機器能不能學習有什麼關係??
在彈珠的例子套用在機器學習上，我們可以把我們不知道真正的黑色彈珠比例u類比成我們不知道的規則f。
我們現在有一個資料庫D，從裡面挑N個資料，就像我們從袋子抽出N個彈珠一樣，如果抽出的輸入資料x套入假設公式h(x)=f(x)，代表其為白色彈珠，反之不等於，代表黑色彈珠，那機率v代表我們抽出的資料，會有多少比例當我們套入x到假設公式h和實際公式f後他們不相等。
這裡解惑一下，雖然不知道f，但是我們知道f(x)，想起來了嗎f(x)=y，就是輸出資料。
而套入霍夫丁不等式裡，如果ϵ很大，|v-u|>ϵ成立，代表v和u差很多，意思就是我們從資料庫裡面抽出來的這N個資料，得出h(x)不等於f(x)的比例，和實際上h(x)不等於f(x)的比例差很多。
那這裡大家就會想，假如v非常接近0，那不就代表我們的假設h(x)=f(x)的比例很大，我們的假設非常成功嗎?
但是這裡還有一個問題就是實際狀況是這麼一回事嗎？雖然v很接近0，但是實際上這個假設h可能很失敗，也就是u很接近1。
回到剛剛霍夫丁不等式，|v-u|>ϵ
假如我們選的N筆資料看起來很成功，讓v=0.01，但是實際上u=0.9，那他超過ϵ的機率就很大，意義上不就是我們取的數量N太少，才會讓v跟u差那麼多嗎?
換個例子，假如v=0.01，u=0.02，那麼他超過ϵ的機率就會很小，這代表我們選的N筆資料夠多，而且我們的假設h很好非常接近f。
另一個極端的例子就是v=0.9，u=0.91，雖然這代表我們取的資料非常接近實際狀況，但是他的v很大，表示我們的假設h很差。
而在這邊我們定義一些符號，把他寫得更直接一點。我們把我們取樣的錯誤率v定義為
這裡要注意雙線中括號定義為，如果裡面的式子成立(h(xn)不等於f(xn))值會等於1，若不成立(h(xn)等於f(xn))則等於0。
另外我們把全部數據的錯誤率u定義為
這裡的意思就是所有資料，會有多少機率使得h(xn)不等於f(xn)。那我們現在就可以正大光明的讓v=E_in和u=E_out。套入霍夫丁不等式得到
但是這裡要非常小心一件事情。當我們得到最後的最佳方程式g，是可以直接把h換成g，帶入上述的霍夫丁不等式嗎？答案是不可以！！！
我們在之前提到在機器學習的過程，電腦是在每一步中，從假設集H挑一個h出來，所以這些h在我們取樣N個數據以前，全部都是固定好的，而g是根據我們取樣的資料然後從許多個h，靠一步一步學習選出的最佳方程式，所以g是不固定的。
所以我們不能把這個不固定的方程式g直接帶到霍夫丁不等式，因為這就違反霍夫丁不等式的前情提要假設。
如果要把g納入我們的霍夫丁不等式，就要用一種間接且暴力的方式套入，
這裡箭頭的意思就是只蘊含，例如A蘊含B就如下圖所示
可以這樣寫的原因是因為，我們設我們的假設集H有M個假設方程式h
H={h1,h2,h3,….,hm} for m=1,2,3,…,M
而最佳方程式g一定是m個假設方程式h裡面其中一個。另外我們知道，如果A蘊含B，則P(A)<P(B)，又因為
P[B1 or B2 or B3 or … or BM]≤P[B1]+P[B2]+P[B3]+…+P[BM]
所以我們可以利用這些特性得出
最後我就可以利用這個不等式，把g帶進去得到
所以大家這裡應該有注意到了，如果我們的假設集H裡面有無限多個假設，也就是M等於無限大，但是我們又希望P越小越好，所以我得必須加一些條件使得我們的M是有限的，這樣機器學習才是有意義的。
總結
總結一下，這個套用到平常的機器學習中，
我們選的N筆資料就是所謂的訓練集(Training set)，沒被選到的就是測試集(Testing set)，而v代表了我們訓練出來model的錯誤率。
如此一來我們可以利用霍夫丁不等式，告訴我們機器真的有沒有學到東西，如果v很小，就可以讓機器知道這個假設h在這N筆資料裡是很好，而透過u和v的差別，可以告訴機器真的有沒有學到東西。
Reference
[1] Abu-Mostafa, Y. S., Magdon-Ismail, M., & Lin, H. T. (2012). Learning from data (Vol. 4). New York, NY, USA:: AMLBook.
[2] 台大資工 林軒田 教授, 機器學習基石(上), Coursera
[3] Mohri, M., Rostamizadeh, A., & Talwalkar, A. (2018). Foundations of machine learning. MIT press.
***本系列完全沒有開任何營利***
作者：劉智皓
LinkedIn：CHIH-HAO LIU
