Drake's

上次介紹了linear regression，這一堂課會說到logistic regression，主要會將linear regression使用sigmoid轉換來算出不同類別的機率。

之前有學過在二元分類中會判斷病人「有」或是「沒有」心臟疾病，並可以使用0/1的分類錯誤來判斷分類的結果好壞

但如果今天並非想要知道病人「有」或是「沒有」心臟疾病，而是想知道未來一段時間後，心臟疾病發生的機率是多少。和二元分類有點不同，我們想要知道的是發生某個狀況的機率，這會是一個介於0到1的數值。當然後續可以對這個數值定義出一個臨界值來達成二元分類，所以又可以稱為soft binary classification。

如果我們可以知道在給定一組x，他的結果y是一個機率值的話那就可以很容易的找到這樣的結果，但是實務上我們只會拿到有抽樣誤差雜訊的結果，只能知道0/1的結果(即有沒有心臟病發)。再來會學到的是，如果只能知道0/1的情況下，要如何求出想要的機率值。

要如何找到這個機率值呢？一樣可以像之前的線性問題，將每個特徵乘上特徵權重，就會找到分數，但是這次想要的不是這個分數，而且要把分數轉換為0到1的機率值，分數越大機率越大，反之分數越小機率就越對，這裡會透過logistic function會把這個分數值轉換成0到1的機率值。

一般會使用sigmoid來把分數轉換成0到1的機率值，當分數越大會越接近1，分數越小會越接近0。再來就可以使用這個logistic hypothesis來達到我們的目標函式f(x)

究竟logistic和之前學到的有什麼差別呢？
在linear classification算完分數會以0為臨界點來區分0/1類別，並使用0/1 err來判斷結果，在linear regression則會直接輸出分數，再使用squared err來評估結果；logistic regression會將算完的分數透過logistic function轉換，但該用什麼err來衡量呢？

首先可以先算出f(x)是怎麼產生一組資料D的，再來因為要使用hypothesis H來逼近f(x)，所以可以把f取代成h，因為最好的狀況下，我們學習到的h和原本的f是會非常接近。而且如果資料D是由f產生的，那麼f算出來的機率值應該是很大的，所以若是可以在多個h裡面找到一個最大機率的h，就能找到一個最適合的hypothesis

在計算likeliood時，重點會放在hypothesis上，因為hypothesis決定了最後的機率，再來因為logistic function具有對稱性，所以最後可以整理成h(YnXn)的連乘

因為這個hypothesis是線性的，在線性裡面我們關注的是其中的權重w，所以再重新整理將h取代成w，把y取代成線性組合yn*w

之前最常處理的就是連加的問題，所以我們取log將連乘取代成連加，再來為了轉成求Ein，所以加上負號來取最小值。最後再將logistic function代進去，就可以得到最後要求的Ein，這裡的Ein又可以稱為cross-entropy error。

在推導出Ein後，再來就要找到一個權重w可以讓Ein最小，因為Ein最小就可以知道Eout也很小。前面的linear regression因為是convex所以可以透過梯度找到最小低，而logistic regression這個函式也是convex，所以也可以透過梯度來找到梯度為0的地方算出最好的權重w。

我們可以使用微分和鏈鎖率來找到梯度，如果今天要讓梯度等於0可以有一個假設，就是假設θ出來的值是0，但要讓θ出來的值是負無限大，就要讓y乘上w乘上x這一項是正的。其中w^T．x這個分數在以前可以被拿來作兩元分類，而乘上y如果大於0的話，代表是同號，即所有資料都可以分對，意義就是線性可分。之前在linear regression可以直接算出一個close-form的答案，但是現在logistic regression並非線性的，困難在於沒辦法直接算出close-form的解，那該怎麼辦呢？

這個時候就可以應用到之前的PLA方法，PLA在每次拜訪到的點如果分錯的話，就會逐步作調整來更新權重。

在整理後可以歸納出兩個部分，如果需要更新權重的話，第一個η是指走多大一步，之前在PLA可以視為1，後面第二部份則是算出要走的方向。像這種逐步循序的調整學習又稱為iterative optimization approach逐步最佳化方法。

那麼再來要如何找到logistic regression的最好權重值w呢？其實就是隨便找一個方向v，然後慢慢透過往下走到谷底就可以了，其中要走的步伐η會決定往下走的速度。

但是要怎麼找這個方向v呢？因為這個問題還是非線性，但是如果我們每次都看一小小段，就是一次只看一個線性問題，就可以比較容易而且轉成接近線性問題。其實這就是常使用的梯度下降法(Gradient Descent)，即每一次走梯度逐步找到最佳，或是近似最佳解。

那麼η該怎麼決定呢？如果η太小的話，雖然遲早可以找到最佳值，但是速度會很慢；如果η太大的話，反而可以會跳過最小值，搞不好會跳來跳去找不到最佳值。有一個最好的方法，就是隨著坡度的大小來決定η要走的大小。

因為η會改變，所以可以採用一個不一樣的η來代表這個會變動的η，即他每一次的學習都是會變化的η乘上梯度，這就稱為fixed learning rate gradient descent。

最後我們可以逐步的作梯度下降，一直到找到最好的谷點，但是實際上可以找到接近谷底的值就可以了，所以最常用的就是設定一個iteration的次數，到達就停止。這個方法其實就很像之前學到的pocket方法，pocket方法是每次抓一個最好的值，得到更好的值就會更新。

因為之前有上過Andrew的Machine Learning課程，其實Andrew在教linear regression找最佳權重w時，就是直接教fixed learning rate的梯度下降法，我覺得在學習線性時用梯度下降還滿好理解的，對於後面到logistic regression很有幫助，建議沒有上過Andrew的Machine Learning課程可以考慮上看看！

參考資料:
Machine Learning Foundation 10
Andrew Ng - Machine Learning

上堂課講到err的衡量方法有兩種，其中一種squared err就是這這堂課Regression就會用到的err衡量方法。

regression會拿來解連續型資料的問題，以前面提過的信用卡案例來說，regression就不是拿來用在判斷要不要發給信用卡，而且會決定發卡的額度上限是多少，依然是一個機器學習問題。

前面的例子也有說到，不同的資料特徵值可能會有不同的重要性，所以會有一個權重w來表示每個x的重要性加權。這有點累似之前的perceptron，但差別是perceptron是用來作二元分類，所以會再取sign判斷正負號，而這裡的regression是不用的。

linear regression的hypothesis主要會找到一條線(或超平面)來盡量滿足所有的資料點，而資料點和線或是平面的距離就稱為residuals(餘數)，或是可以稱為誤差，我們會希望這個餘數越小越好，因為越小就代表hypothesis越正確。

一開始有講到，linear regression最常使用的錯誤衡量方法就是sqiared err。

在regression求Ein時，可以把運算過程轉換成向量矩陣運算

在求Ein最小值的過程只有W是未知的，而這個Ein(w)會是一個convex函式，在反覆修正W最終會得到一個最低點，也就可以找到Ein最小值，可以找透過找梯度為0來找到這個最低點。

中間會將梯度函式重新整理，在梯度等於0的情況下，最終會找到最好的W。在求W的過程中會帶出pseudo-inverse的概感，使用pseudo-inverse和y就可以求出最好的W。

這樣看起來直接計算出W好像有一步登天的感覺不像機器學習，但事實上linear regression可以說是機器學習方法，因為確實可以找到Ein，當你認同VC維那麼好的Ein就會有好的Eout，而且在計算過程中，其實背後也有很多的步驟進行並非一步就達成。

要怎麼確定linear regression真的可以學的好呢？可以透過對多的Ein的平均來衡量，而這個Ein的平均大概會等於noise level(資料的雜訊)×(1-d+1/N)，所以如果資料量越多得到的結果就會越好。

以幾何上來說來說明，y是一個N維的向量，X是在N維上的一個小空間，而y(hat)會落在這個小空間裡。linear regression的目的就是讓y和y(hat)可以最小，最小的距離就是y到y(hat)的線性投影，所以linear regression的hypothesis的目的就是把任何一個向量投影到x空間中。因為H作了投影，而I-H等同就是在求餘數，即y-y(hat)。這之中會存在一個特性trace(I-H) = N-(d+1)。

y為f(x)加上noise，Ein其實就是把I-H用在noise向量上，最後推導出來Ein平均為noise level×(1-d+1/N)，Eout平均推導出來剛好相反，為noise level×(1-d+1/N)。

從Ein和Eout可以畫出leraning curve，當資料量N越大時可以看到Ein和Eout的變化，Eout會越加越少，Ein會越減越少，兩者都會收斂。VC求的是最壞的情形，而我們現在是求平均的情形，但兩者會得到類似的結果，所以可以說linear regression在N夠大時，並在noise不是太多的情況下，確實是可以學習的。

和之前的線性分類相比，分類的y是兩元類別，迴歸是一個連續型實數；分類會取sign轉成二元類別而迴歸不用；在錯誤衡量方法，分類是用0/1 error而迴歸是用squared error。因為迴歸的運算可以很有效的得到解答，那麼是不是可以把linear regression拿來解分類問題嗎？

其實兩者最大的不同就是在錯誤的衡量，可以發現迴歸的平方錯誤會比分類0/1的錯誤還大。

接著把VC放進來分類問題，因為regression的squared錯誤會比0/1錯誤還大，分類會被regression bound住。所以如果可以把regression作的很好，就可以把分類作的很好，甚至可能把Eout也作好。所以確實可以用regression來取代作分類問題，會比較好解，但是效果確不一定比較好，因為其錯誤為分類的上界。

有個好的辦法是，先透過regression來算出一個W初始值，再將這個W拿去PLA進行學習，可能可以增加PLA學習的效率。

總結來說，這一堂課介紹了linear regression，其在求解時而要求出pseudo-inverse，而且可以確保Eout和Ein平均的差距為2(d+1)/N，最後linear regression是可以用在分類問題上的。

參考資料:
Machine Learning Foundation 09

雖然python已經有很好用的測試框架可以使用，不過對於剛開始想要自己寫測試的人，這些框架該怎麼使用還是需要花點時間學習一番。在真正進入使用測試框架之後，不彷先來作個簡單的測試感覺一下，其實我們可以很簡單的使用python的assert來實作看看。

假設今天要設計提款功能，其中有兩個函式，一個會回傳存款減去提款剩下的金額，一個會檢查提款金額只能以1000為單位。所以這台atm很簡單，就是只讓你提1000為單位的金額，而且不能提超過你餘額的錢。

1
2
3
4
5

def withdraw(deposit, money):    
    return deposit - money
    
def check_withdraw(money):    
    return 'accept' if money % 1000 == 0 else 'refuse'

接著就是來寫一個測試用的function class，把要測試的不同條件寫進去，如果全pass就給個PASS訊息。function class只是一個簡單的方法把函式都集中起來，當然可以再作不同的變化。

1
2
3
4
5
6
7
8
9
10

class TaskTest(object):    
    def test_withdraw(self, func):        
        assert func(1200, 2000) < 0, '存款小於提款不能允許提出'        
        assert func(3000, 2000) > 0, '存款大於提款需允許提出'        
        print('ALL withdraw PASS!')    
        
    def test_check_withdraw(self, func):        
        assert func(1300) == 'refuse', '提款金額非以1000為單位必須拒絕'        
        assert func(1000) == 'accept', '提款金額以1000為單位必須接受'        
        print('All check_withdraw test PASS!')

接著就開始執行測試囉!

1
2
3
4
5

>>> tester = TaskTest()
>>> tester.test_withdraw(withdraw)
ALL withdraw PASS!
>>> tester.test_check_withdraw(check_withdraw)
All check_withdraw test PASS!

那如果今天有人不小心動到函式內容，1000被改成1300會發生什麼事情呢？

1
2

def check_withdraw(money):    
    return 'accept' if money % 1300 == 0 else 'refuse'

一樣執行看看，就會發現在作檢查提款的測試時被assert中斷了!當測試沒測過就可以趕快回去檢查一下程式碼究竟發生什麼問題了

1
2
3
4
5
6
7
8
9
10

>>> tester = TaskTest()
>>> tester.test_withdraw(withdraw)
ALL withdraw PASS!
>>> tester.test_check_withdraw(check_withdraw)
Traceback (most recent call last):
  File "assert.py", line 23, in <module>
    tester.test_check_withdraw(check_withdraw)
  File "assert.py", line 15, in test_check_withdraw
    assert func(1300) == 'refuse', '提款金額非以1000為單位必須拒絕'
AssertionError: 提款金額非以1000為單位必須拒絕

第一次寫測試其實可以從python的assert開始玩起，自己就可以簡單寫單元測試囉！針對已經是大型的系統就可以考慮使用一些python的測試框架作單元測試或是整合測試。如果像這樣的單元測試要一進步的話，可以先從使用python的unittest開始！

先來複習一下前面課程，從前面的課程可以得知，在有限的VC維度下，且有大的樣本N並且Ein是夠小的，滿足三個條件我們就可以讓機器可以學習。

那如果今天在整個學習流程中，未知的目標函式在產生x時有雜訊發生，會發生什麼事呢？這堂課主要就是在說明，如果資料有雜訊，到底會不會對學習造成影響。

事實上雜訊是有可能發生的，比如說在審核信用卡的例子，可能在y產生雜訊，即發不發信用卡被錯誤標記；也可能在x產生雜訊，這就發生在蒐集資料時產生的錯誤。那麼究竟有雜訊會不會對VC維產生影響呢？

我們一樣從前面的抽彈珠例子來看，本來如果f(x)和h(x)相等時是綠色，不相等是橘色，今天如果有雜訊發生，代表y和f(x)會不相等(明明要核卡但沒有)。雜訊就可以假設成一種會變顏色的彈珠，有時是綠色有時是橘色，雖然會有這種雜訊的彈珠出現，但是因為雜訊變色彈珠是少數，我們仍然可以透過抽樣的方式來計算橘色和綠色彈珠的比率，所以VC維還是會work的。

這邊會帶出目標分配P(y|x)，以二元分類o和x的例子來看，如果我們已知P(o|x)是70%，P(x|x)是30%，在這個情況下我們會選擇o，但是剩下的30%可以看成雜訊。即最好的預測是o，而雜訊發生的機率是30%。所以在這裡機器學習要作到的，就是在點x找到最理想的mini-target。

最後再把雜訊加進去後，可以把目標函式f(x)改變成mini-target P(y|x)加上雜訊，而這個y會用來在最後評估g和f是否接近。

之前談到的錯誤衡量方式為分類錯誤(又稱為0/1錯誤)，就是直覺的判斷g(x)和f(x)是否相等，不管是Ein或是Eout都可以對每一個點各自作判斷(稱為pointwise)是否發生錯誤。

這種0/1錯誤衡量會用在分類問題上，除了分類錯誤外，另外常用的錯誤衡量方式為Squred Err，判斷每一個y到理想的y的距離，這種則常用在數值型的機器學習問題，像是迴歸分析。在不同的機器學習問題，會使用最適合的錯誤衡量方法。

當我們把錯誤衡量加上去，這個選擇的錯誤衡量會用來評估g(x)和f(x)是否相等。

在0/1分類時，可能會有兩種分錯的情況，以指紋判斷正不正確來說明，一種為false reject，就是指原本是正確的，但是被判成錯誤；另一種為false accept，是指原本是錯誤的，但是被判成正確。看起來都是錯誤，但是這兩種錯誤會在不同的應用上有不同的重要性。

以超市的應用為例，如果超市透過指紋來判斷是不是要給折扣，今天判斷錯誤造成該給折扣卻沒給(false reject)讓顧客不開心，損失了這個客戶可能造成超市的損失；相比之下，如果是不該給折扣卻給了(false accept)，頂多只是超市有一點損失而已沒什麼大不了。所以以超市來看，false reject的成本會比false accept高。

以CIA應用為例，今天如果有人沒有權限但是卻被判斷有權限可以看資料(false accept)，這將是個很嚴重的錯誤；那如果是有權限但是被判斷成沒有權限(false reject)，其實只的造成員工的不開心而已。和超市相比，他的false accept成本可能就會遠遠大於false reject。

那麼到底該怎麼樣去衡量雜訊造成的實際應用錯誤呢？我們會透過設計友善的演算法來找到還可以接受的錯誤衡量方法。所以相比於實際的錯誤err，在設計演算法會透過計算一個另一個err hat，來試圖讓錯誤衡量可以更多的方便。

前面講到的又稱為有權重的分類問題(weight classification)，不同的例子會有不同的重要性。因為已經證明在有雜訊的情況下VC維仍然是可行的，所以我們只要確保Ein是最小的，就可以保證Eout是最小的。我們總共學過兩個讓Ein最小化的方法，第一個是PLA，PLA就會等所有的資料都分對就結束，即Ein為0；如果PLA跑不完的話，可以用另外的Pocket演算法，Pocket演算法可以把加權錯誤比較好的放入pocket。

如果我們要把0/1分類問題加上權重，其實可以簡單的把-1的資料複製成1000次，就會很像他有帶權重1000。實際並不的真的複製，原本的pocket會輪流拜訪每一個點，當我們這種-1的點讓他有1000倍的機率更容易被拜訪到，其實就可以達到類似的效果。

總結來說，這堂課首先說明了有雜訊的情況下，會使用一個機率函式P(y|x)來取代f(x)，再來會使用適合的錯誤衡量方法來作評估，但是錯誤衡量方法有時並不容易給，所以會透過比較友善的演算法設計來達成。最後說到兩種不同的錯誤會有不同的權重，且這個權重可以透過虛擬複製的方法達成。

參考資料:
Machine Learning Foundation 08

在上一講中證明了如果存在break point，而且輸入點N夠大的情況下，Ein和Eout是會接近的。這一講會延續VC bound帶出VC Dimension。

前面有證明到，成長函式mH(N)會被上限函式B(N, k) bound住，然後上限函式又會被一個多項式N^k-1給bound住。所以我們可以直接使用N的k-1次方來表示成長函式。

再來把N的k-1次方取代原本的成長函式mH(N)並代回原本的Hoeffding不等式中，他告訴我們1. 只要成長函式存在break point，即表示是個好的hypothesis且2. 輸入的N夠大，即表示是個好的D的情況下，再來配合3. 一個好的演算法，那麼就可以保證機器可以有學習的效果。

VC dimension被定義為最大的非break point維度，所以當我們說在k點不能被shatter，那麼VC dimension就是k-1。

依據VC dimension的定義，在PLA是在4點不能shatter，所以VC dimension為3。以前我們說成長函式mH(N)是有限的就是好的，現在我們可以說如果VC dimension是有限也就是好的。

有了VC dimension再回來看2D的PLA該怎麼學習，PLA可以在線性可分的資料D中找到g讓Ein為0，而VC dimension為3且N夠大的情況下，能推論Ein和Eout會很接近，即Ein和Eout差距很大的機率會很小，又因為Ein為0，所以可以知道Eout也會很接近0，就代表機器真的可以學習了。

前面可以看到1維perceptron的VC dimension為2，2維的perceptron的VC dimension為3，這樣看起來似乎可以推論出d維度的VC dimension為d+1。當然這是正確的，因為後續可以證明出dVC >= d+1和dVC <= d+1

VC dimension的物理意義大致上可以說是hypothesis集合在要作二元分類的狀況下，到底有多少的自由度。前面提到的VC dimension的定義是說，VC dimension在k-1的時候可以產生最多的dichotomy，所以這個自由度也就告訴我們hypothesis集合到底可以產生多少的dicotomy組合。以positive ray的例子來看，其有1個可以調整的參數，positive interval的例子則有2個可以調整的參數

我們可以將VC bound的式子作一些調整轉換，其中把右邊壞事情發生的機率代換成δ，那麼好事情發生的機率就是1-δ，也就是Ein(g) - Eout(g) <= ε，再用右邊的部份可以導出ε。

好事情發生的機率，即Ein(g)和Eout(g)有多靠近，又可以稱為generalization eror，就是指舉一反三的效果好不好。衡量一個model的複雜度可以用Ω符號來表示，而VC dimension告訴我們的是，當model的複雜度越高的時候，就會產生penalty效應，有很高的機率Eout(g)會小於等於Ein(g)加上model的複雜度。

以圖示來看這個現象，其中model複雜度會隨著VC dimension越大而變大；而VC dimension越大時，排列組合也會比較多，就比較有可能找到一個更小的Ein，所以Ein會降低。但是因為model複雜度的penalty效應，Eout並不會隨著Ein持續下降，而且到達一個臨界點時轉折變成一個山谷型，所以最好的VC dimension就是中間轉折的地方。這在機器學習上的意義就是，當我們使用很強大的hypothesis或是model，也會伴隨著model複雜度提高帶來的壞處，也就是把Ein作到最好，但也可能因為model複雜度的penalty讓Eout沒辦法作到最好，在使用機器學習上都需要進行取捨的地方。

那麼到底需要多少的樣本資料，才能讓Ein和Eout很接近呢？假設今天要讓Ein和Eou相距ε為0.1而且δ壞事發生的機率為10%，如果是2D的perceptron其VC dimension為3，那需要有多少的資料才足夠呢？理論上可以推出29300筆可以滿足，大至上為10000 x dVC，但是實務上只需要10 x dVC的樣本數就足夠了。

總結這一講的內容，主要在介紹VC dimension定義為最大的non-break point，且percepron的VC dimension為d+1，VC dimension其實際意義為可自由調整的參數，且VC dimension會影響到模型和樣本的複雜度

參考資料:
Machine Learning Foundation 07

前面講到M如果會變成無限大，就無法滿足能夠學習的理論，所以我們希望能透過成長函式mH(N)來取代M，這一講主要在推論mH(N)是不是真的成長的比較慢，且能夠夠取代掉M

複習一下成長函數的定義是指Hyperthesis集合在N個點上最多能夠產生多少個Dichotomies(即O或是X兩分的排列組合)。上一講提到了四種成長函數，且每一種都可能有出現break point現象，就是指當輸入點數大於某個臨界值後，會產生沒有辦法滿足的Dicotomies組合。

假設今天有一個Hyperthesis在N為1時mH(N)為2種，N為2時mH(N)最多只有3種(3 < 2^2)，那麼我們要找在3點輸入時，而且最小的break point K為2(即任2點不能有shatter)，究竟mH(N)為多少呢？可以發現加上第5種組合，無論前面4種用什麼組合，在第5種任2點都會shatter，所以最多只會有4種可能

到這邊可以發現當N越大時，break point K會對最大可能的mH(N)產生限制(因為K為break point，K+1開始都會shatter)，使得當N越大時，N和mH(N)之間的差距會越來越大。所以如果可以證明mH(N)是一個多項式，就可以在原本的Hoeffiding不等式中，把可能無限大的M取代成有限制且為多項式的mH(N)，使得學習是有可能的。

再來先別管成長函式了，我們透過bounding function來表示在break point為K的情況下，mH(N)的最大可能性，就是在K個點不能出現shatter。這樣我們就可以不用管問題是屬於positive intervals或是1D perceptrons要用不同的方法分析，我們可以統一使用B(N, 3)來表代所有不同的問題。

N和K建立的bounding function可以用表格來呈現，基本上可以分成4種。第一種是如果K為1，即B(N, 1)代表1個點不能出現shatter，那麼只會有1種情況；第二種是右上斜角部份，今天如果K大於N，那麼K等於沒有限制，所以最多會有2^N種情況；第三種是在斜角上，當N和k的值一樣時，因為不能是2^N種，所以減1最多會有2^N-1種。

那麼最重要的斜角下方部份該怎麼填了，假設要填的值是B(4, 3)，我們猜測他可能和前一排的B(3, ?)有關係。這裡可以看到所有的組合總共是11種，看起來B(4, 3)好像是B(3, 3)和B(3, 2)相加，但是該怎麼去證明說是有關係的呢？

把B(4, 3)的11種解可以分成α和β兩種類型，橘色的類型為X1-X3相同，但是X4會不一樣(即2α)，紫色的類型為皆不相同(即β)。B(4, 3)指其中3個點不能shatter，那X1-X3也是其中的3個點，所以也不能shatter，意思就是說如果今天不看X4的話，因為X1-X3不能shatter，所以α加β會小於等於B(3, 3)。

再繼續往下只看α部份的話，如果X1-X3其中有2個點shatter了，那麼再加上X4的話就會造成3點shatter，這也是B(4, 3)不允許的，所以X1-X3其中2個點也不能shatter。於是α會小於等於B(3, 2)

再來就可以把中間證明的過程連結在一起了，B(4, 3) ≤ B(3, 3) + B(3, 2)，又可以轉變成B(N, K) ≤ B(N-1, K) + B(N-1, K-1)，這樣就可以把斜角下方都值都可以填上一個上限值。我們最早從會有無限多組解的大M開始，再到其實大M是有限的，透過成長函數可找到dichotomy數量mH(N)，再推展到上限函式B(K, N)來統一計算N和K的上限值(不用依不同的情況計算mH(N))，最後證明到這裡的值其實就是上限的上限值(很繞口)。

所以推展到這邊可以得到的重點是，mH(N)會被上限函式bounded住，然後這個上限函式又會被上限的上限bounded住，而且這個上限的上限是一個多項式；因此只要確保有出現break point，就可以說mH(N)是個多項式。

再來回到原本的帶有union bound的Hoeffding不等式，我們經過上面的推導後，是不是可以把這個成長函式mH(N)丟進Hoeffding裡面，就可以了呢？再來會開始推導成投影片中的新的式子，是一個長的差不多的式子，他可以證明在N夠大的情況下，就可以根據Hoeffding不等式來說學習是可以達成的。

第一步遇到的問題是Eout會是無限多的值，所以會先把Eout取代成有限的Ein’，這裡的概念是如果Ein和Eout差距很大時(即壞事發生時)，那麼有很大的機會(>1/2)，Ein和Ein’也隔的很遠。

接著第一步的結果，因為多了Ein’所以會多了N個樣本，所以成長函式裡面的N會變成2N。第二步會把Union Bounded中發生各種壞事的情況，找到共同發生的部份，所以把前面說到有限組合的mH(N)代進式子中。

再來因為我們是有限多個值了，所以想像概念就像是現在瓶子裡面有2N個樣本，今天抽出N個樣本，我們就可以把這N個樣本和原本的2N個樣本作比較。這就像是用了一個比較小的瓶子和比較小的誤差，使用了抽後不放回的Hoeffding，他其實還是Hoeffding。

證明到這邊，可以簡單的證明出apnik-Chervonenkis (VC) bound了! 所以在break point為4的2D perceptrons中，如果N夠大的情況下，是真的可以透過PLA達到學習效果的。

總結來說，這一課證明了只要存在break point，就會對未來的成長函數加上很大的限制，因為有了break poin也才能證明mH(N)會被一個多項式的上限函式bounded住，並且mH(N)可以取代Hoeffding原本是無限多的大M

參考資料:
Machine Learning Foundation 06

這一講主要在延續前一講的推導，說明無限多個hypothesis到底發生什麼事情。

前面有是到如果要讓訓練是可行的，則必需要加上一些假設，首先原本訓練的資料和測試hypothesis的資料都是來自於相同的分配(Distribution)，那麼當hypothesis集合是有限的，且資料數量N夠大的情況下，不論演算法A挑出哪一個函式g，Ein和Eout都會是接近的。在這個情況下，只要挑出趨近於0的Ein，就可以保證Eout也趨近於0，即代表學習是可能的。

再複習一下到目前的學習內容。證明機器學習的過程中，首先會希望得到一個函式g而且和f會很接近，也就是希望Eout(g)會接近於0。但是我們不知道該怎麼去證明Eout會接近於0，於是我們從取樣下手來證明Ein如果趨近於0的話，且Ein和Eout會很接近，那麼Eout也會趨近於0。那麼要讓機器學習可能，其中一個很大的重點是有限的hypothesis集合M，究竟這個M扮演了什麼角色？

這時我們會談到M的trade-off，所謂選擇M的trade-off就是當我們選了比較小的M才能符合Hoeffiding不等式讓壞事發生的機率降低，但這代表可以選擇的hypothesis比較少，也許這樣可能就無法選到一個好的hypothesis來讓Ein可以趨近於0。相反的，如果M越大，雖然選擇的hypothesis變多，但是壞事發生的機率也會上升。所以選擇一個正確而且適當的M對於學習問題是很重要的。

前面提到如果M是有限的集合，那麼學習才有可能發生，如果是M是無限大的話，壞事發生的機率也就是無限大，機器就沒辦法學到一個好的結果，因為其中的壞事發生的機率，就是M種發生壞事的機率相加。雖然看起來M會無限大，但事實上發生不同壞事資料D可能是一樣的。以PLA為例說明，假設選了兩條非常接近的線(即兩個hypothesis)，其實這兩條線可能對於同一組資料D分出來的結果是一樣的，所以不同的壞事發生可能會有重疊的情況，所以看起來M應該是有限的。

假設平面上只有一個點，每條線都是一個hypothesis，看起來你確實可以在平面上切出無限多條線，可是事實上不管怎麼切都只會有兩種情況，即這個點不是O就是X，所以只要任何長的像H1的切線都是O，任何長的像H2的切線都是X

如果是兩個輸入的話，總共會有4種切線，

如果是3個輸入呢？看起來總共會有8種總合，但是事實上其中會有2種組合沒辦法使用直線切出來(OXO和XOX)，所以實際上只會有6種切線。

這又稱為Effect Number of Lines，從表格可以發現每個輸入最多只會有2^N種組合，但是能夠有效的切出兩種分類會從3個輸入開始變少，所以我們可以把M取代成effect(N)。也就是說無論今天的M再多大，都可以找到一個有限的切線數量effect(N)，而且這個effect(N)可以比2^N小很多，這樣就能夠保證學習能夠發生。

這裡講到Dichotomy的概念，所謂Dichotomy就是兩分的意思(分成O和X為一例)，Dichotomy和原本的hypothesis的差別在於Dichotomy是有限的組合，而Hypothesis是平面上無限條線的任一條，接下來會把原本的M取代成有限的Dichotomy數量。

接著會透過計算成長函式(Growth Function)來找到有限的Dichotomy上限數量，取代M讓學習可以發生。

以一個最簡單的Postive Ray來說明，資料點N分佈在一維線上，當我們取一個threshold可以找到不同的Postive Ray，那麼所有可能的Dichotomy組合總共會是N+1個(就是能在點之間切線的數量)，在這個問題下Dichotomy的組合大大的小於2^N種。

課程舉了四種不同的成長函數，其中PLA的Dichotomy數量mH(N)會小於2^N，但是對於Hoeffding不等式中，如果mH(N)是指數型成長，則無法確保不等式成立，所以我們需要證明mH(N)是一個多項式的成長。

這個部份提到了Break Point的概念，所謂的Break Point就是當某一個輸入開始，Dichotomy數量不再是指數成長(即2^N)，像是positive ray在2個輸入時發生，postive interval在3個輸入時發生，2D perceptrons在4個輸入時發生。在這裡看到神奇的地方在於本來的沒有break point的情況下mH(N)會是指數成長，但是當有了break point後，mH(N)會是一個多項式，下一講就會開始證明是如何轉變成多項式的。

參考資料:
Machine Learning Foundation 05

這一講的學習重點主要是在如何討論學習到底是不是可行的，並進一步推導證明機器是真的可以「學習」的。

機器會不會其實是沒辦法學習的？我們可以先看講義上的圖形，上半部的圖形屬於-1，下半部的圖形屬於+1，那麼給了f上方右邊的圖，他究竟是屬於+1還是-1呢？如果我們用黑色區域是不是對稱來判斷，那麼這張圖會是+1；但如果我們用左上角的格子是否為黑色，那邊這張圖會是-1。這裡會發現如果我們用不同的規則就可能得到不同的答案，看起來好像真的沒辦法讓機器真的「學習」一個正確的答案。

用一個比較數學的例子來看，假設今天有一個函式f，輸入是3個bit，輸出是o或是x。再來我們透過機器學習演算法學到g函式，並確保這個g函式在5筆資料D都能和f得到一樣的答案(即f和g結果相同)。所以我們確保了g和f(甚至是講義上的8個f)在D得到相同答案，但是除了D之外剩下的3種答案，g只會有一種結果。這會有什麼的影響呢？比如說當g在剩下3筆得到XOX，那麼他會和f6相同，可是我們今天是要告訴你正確的f其實是除了f6以外的函式，那麼似乎g和f答案又錯了，看起來機器好像真的沒辦法「學習」到一個正確答案。這又稱為no free lunch，如果沒有對機器學習問題加上一些限制，即我們只是單純給機器資料學習，事實上是沒辦法讓機器學出一個正確的答案的。

這裡舉一個推論未知的方法，比如說在一個瓶子中有綠色彈珠和橘色彈珠，如果今天沒有辦法完全數完瓶內所有的彈珠，那麼該如何去推論橘色彈珠的比例呢？我們可以透過統計手法利用取樣(樣本)的比例來推論瓶內橘色彈珠(母體)的比例。假設瓶內橘色彈珠的比例是μ，綠色是1-μ，取樣出橘色彈珠的比例是ν，綠色是1-ν，是否可以用這個ν來推論μ呢？照理說ν可能沒辦法完全的推論μ(明明有橘色彈珠，但是每一次運氣不好都抽到綠色)，但是在一定的機率下，ν應該是有辦法推論μ的，在數學上可用Hoeffding’s Inequality來解釋

透過Hoeffding’s Inequality可以解釋，如果今天抽出彈珠(N)的數量越大的話，ν和μ之間差很遠的機率(ε)就會很小，也就是說如果可以取出數量夠大的樣本的話，就可以讓「壞事」(ν和μ差很多)發生的機率變小，我們可以說ν和μ大概差不多會是對的(即probably approximately correct, PAC)

那用這個抽彈珠的例子到底和學習會有什麼關係？當把抽彈珠轉成學習的問題，未知橘色彈珠的機率μ可視為未知的f，所有抽出來的彈珠就是每筆的資料，其中橘色彈珠可視為h(x)≠f(x)，即hypothesis h是錯的，綠色彈珠可視為h(x)=f(x)，即hypothesis h是對的。所以如果我們在獨立的抽出彈珠時，就可知道來誰論h和f不一樣的機率到底是多少。

所以把前面錯誤推估的部份加入進去機器學習的流程中。首先我有一個機率在瓶子中取樣產生了資料D，在判斷h和f是不是一樣時，其中這個h就是Hypothesis集合中的其中一個

再來就可以透過手上確實知道的資料D來說h和f是否相同，也就是透過Ein(取樣的資料Error)來推論Eout(實際的瓶子的資料Error)，使用Hoeffding’s Inequality就可以證明當N夠大時，Ein和Eout就會差不多是相同的。

但這樣的證明充其量其能說是驗證而已，就是這個h目前還沒有辦法像是PLA一樣丟不同資料產生不同的h，但是我們可以證明這個h是不是使用資料D能夠有有用的推論f，即驗證選出h的表現是好的還是不好的。

目前已經可以驗證相同h之下的表現好還是不好，但是今天當我們有了選擇時(即在多個h裡面作選擇)，我們可能就會有偏見的選出一個瓶子都是綠色彈珠的結果，但事實上可能只是剛好這個瓶子都「碰巧」的抽出了綠色彈珠，就像擲銅板一樣，不論這枚銅板多麼公正，都會有可能出現每次都正面的情況。前面講到Hoeffding告訴我們的是ν和μ之間差異很大的這種「不好」的事情機率應該是很小的，但是當我們有選擇的時候，這種「不好」的取樣卻會造成Ein和Eout差距變大。

如果演算法遇到不好的資料(Ein和Eout差很遠)，就會得到不好的結果。Hoeffding告訴我們的是每一個h不好的情況是很小的，但是在演算法有自由選擇h的情況下，那麼不好資料發生的機率是多少呢？

假設有M總不同的h，那麼不好資料發生的機率，就會等於每一個h發生不好機率的總合(Union Bound)。所以如果演算法有辦法選出一個最小的Ein(壞事發生的機率是最小的)，就可以表示選出來的Eout會是最小的

總結來說機器該如何能夠學習呢？只要滿足Hypothesis集合是有限的集合M，且樣本資料N是夠大的，對於任何被演算法選出來的g(其中一個假設h)，就可以推論Eout和Ein是差不多相同的。就是剛提到的，演算法只要選出一個Ein是最小的，就可以保證Eout也是最小的。

參考資料:
Machine Learning Foundation 04

第三講主要在說明機器學習有哪些種類，以及在訓練過程中會用到哪些不同的特徵(Feature)種類。在針對輸出空間y的不同可以有以下幾種不同的學習種類：

在上一講有看到在平面上透過直線切割出兩種類別，這種二元分類(Binary Classification)是機器學習裡面最常見的問題。但現實上的應用有時並不會侷限在二元分類，常常會遇到多種類別的問題，即多元分類(Multiclass Classification)問題。比如說，可以透過硬幣的大小和重量來區分出美元硬幣，這時候的輸出就是4種類別，如果把類別數量用K來代稱，那麼二元分類可以被視為多元分類的一種特例。這種多元分類問題常用在許多不同的應用，比如說手寫字跡的辨識、圖片中的物件辨識或是email的種類或是重要性辨識。

如果今天要預測的不是兩元類別或是多元類別，而是一個數字型態的資料，例如透過公司的資料或是新聞的風向來預測股價，或是透過氣候的資料來預測未來的氣溫，這樣的學習也是在統計中常被使用到的迴歸分析。通常透過迴歸分析來預測數值結果也是一種具有label的監督式(Supervised)的學習，因為在學習過程中，會告訴演算法資料x的特徵，和其對應的y數值結果。

再進一步更複雜的應用中，像是自然語言辨識的領域中，如何對每個字作詞性標注(Part-of-Speech Tag)，他看起似乎像是種多類別的問題(一個詞被分到其中一種詞性)，但是這種詞性標注的問題往往不是把每個詞拆開來輸入，而是會把整個句子輸入來學習分析，因為詞性可能會根據語句而有變化，這個問題尤其是在中文詞性標注更加的明顯。傳統上處理詞性標注可以逶過隱馬可夫模型(Hidden Markov Model, HMM))將詞當作觀察現象，詞性當作隱藏狀態，並結合維特比(Viterbi)演算法來作詞性標注。

在學習的過程中有沒有給予y(輸出標籤)，可以區分成監督式和非監督式學習。

之前討論到的學習方法是，我們把每個硬幣x的大小和重量，以及這個硬幣的種類y，來學習判斷硬幣的哪個種類，這種有給予y的稱為監督式學習。如果今天不告訴機器每個硬幣的種類y，在只知道硬幣的大小和重量的情況下，把硬幣區分成不同群，稱為非監督式學習。非監督式學習困難的問題常常在於分群的結果不容易被衡量，監督式學習效果的衡量可以簡單的比對機器判斷的g(x)和y是否一致，因此非監督式常習會再透過一些方法像是Elbow Method或是silhouette analysis來判斷分群的品質。非監督式學習除了群聚分析外，像是密度分析(Density Estimation)和臨群偵測(Outlier Detection)也都是非監督式學習的範疇。

介於監督式和非監督式學習中間稱為半監督式(Semi-supervised)，半監督式會先使用一部份已經有標注好標籤的資料作監督式學習，再使用沒有標注的資料來讓機器可以學的更好。其中常用在大量的資料無法將所有的資料都給予標籤，因為標注資料的成本是很高的，所以像是影像辯識就會透過半監督式方法來完成學習。

增強學習(Reinforcement Learning)會透過獎勵的方式告訴機器什麼樣的情況是好或是不好，例如在廣告的投放上當使用者點擊某種類的廣告會影響廣告系統推薦給使用者的廣告內容。

參考資料:
Machine Learning Foundation 03

第二講的內容主要在說明如何透過機器學習來回答兩元問題。上一講有提到機器學習會透過一個演算法A，並透過資料D和假說Hyposis H集合，透過選擇一個假說來學習到函式g。以上一講的案例來說，我們會透過函式g來決定要不要發信用卡。

我們可以簡單的透過計算分數的方式來建立一個簡單的機器學習方法。首先可以把每位使用者的資料建立一筆特徵向量當作輸入資料，而每個維度還會有重要性的權重(例如年薪的權重可能會比性別的權重還來的高)，最後把每個使用者依據加總的分數，和設定的門檻值(threshold)比較，如果高過門檻值就發卡，沒高過就不發卡，這樣的模型h就是一個簡單的Perceptron(感知器)。

其實在情感分析(Sentiment Analysis)上，以前也常用這種計算分數的方式來判斷文本屬於正面(Postive)或是(Nagtive)。當我們手上有一個情感詞典(定義哪些字是正面，哪些字是負面)，在拿到一篇文章的時候，就可以加總正面詞(+1)和負面詞(-1)來算出文章的情感分數，再搭配門檻值來判斷文章是屬於正面還是負面，甚至是正負面的程度。(不同字詞可以有不同程度的權重，沒有被情感詞典定義的詞當作0分)

這個用來判斷要不要發信用卡的模型h，在二維的平面上會呈現為一條直線(平面上的每一點就是一筆資料x，每一筆資料的形狀則是指的label)，在高維度的空間會是一個平面。這條直接的一邊是其中一種label(O)，跨過線的另一邊則是另一種label(X)，這樣的線性分類器即可以用來分類兩元問題。

那究竟平面上面的這條線該怎麼切才是最好的呢？可以透過Perceptron Learning Algorithm(PLA)來學習出最好的線性分類器。當平面上的線如果切的不夠好時，透過會旋轉這條線來讓切線更完美。當正的label被分到負的label時，代表w和x的角度太大，可以透過向量相加來讓角度變小；當負的label被分到正的label時，代表w和x的角度太小，可以透過向量相減來讓角度變大。就這樣一直轉到所有的正的label和負的label都分到正確的類別沒有任何分錯，就可以得到一個最佳的切線，這個演算法稱為PLA。

PLA既然要在平面上找到一條切線，那勢必他就必須要是線性可分的問題，像是上圖最左邊就是一個線性可分的問題，右邊兩張則是線性不可分，即不管怎麼旋轉這條切線都沒辦法把兩種類別各自分到對的地方。如果稍有瞭解支援向量機(Support Vector Machine, SVM)的人大概會想到，如果使用SVM的話就可以解決線性不可分的問題，因為SVM主要是也在空間裡找到線性可分的超平面來切分空間，如果遇到第二種線性不可分的情況，最簡單可以透過調整懲罰參數C來忽略一些無法分到正確類別的資料(也許是雜訊)。至於遇到第三種情況的話，則可以調整核函式Kernel Function來將於N維線性不可分的資料於較高的維度M找到線性可分的超平面。

回到PLA，現實上絕對沒有這麼好的情況可以讓你都有線性可分，也許只有稍微有點雜訊，就會讓問題變成線性不可分。這邊會用到演算法稱為口袋演算法(pocket algorithm)，即是在PLA的修正學習過程中，如果找到一個比較好的線(即分錯最少)，我們就把這條線放到口袋裡面，當遇到下一條比我們口袋裡這條線更好的線，就再換成新的線，一直到執到覺得應該差不多就停下來。所以當我們是線性可分，PLA可以幫助找到好的解答；但如果不是線性可分，透過變形的PLA確實可以找到一個還不錯的解答。

參考資料: Machine Learning Foundation 02