這裡是監督學習第三課，長期更新，求關注！
前兩課分别講了監督學習最簡單（普遍）的算法，線性回歸，以及knn和常見的問題以及解決方式。
對于線性回歸的計算複雜度優化由mn兩個參數決定。根據他們的相對大小選擇更好的求解公式（預測）
這一課跟前面不一樣，前面我們是給出X 輸入，求Y，通過預先計算X和Y的關系，這一課我們沒有X，隻有Y。
由Y預測Y。
這就是線上學習。下面詳細展開！
假設現在有一個分類問題，我們8個模型（分類器），這8個分類器如何我們不知道，我們假設其中有一個分類器是完美的。那麼怎麼找出這個分類器呢？
最簡單的方法就是折半算法 halving algorithm，假設我們有了ground truth，通過和ground truth對比，我們每次可以排除錯誤答案對應的錯誤分類器，假設隻有一個分類器完美，那麼最後肯定隻剩下一個分類器。
但是實際上，我們不知道是否隻有一個分類器完美，也不知道在所有預測上都正确的分類器到底是不是完美，因為我們無法窮舉所有的輸入。舉個例子，如果是圖像分類的話，判斷一個圖檔是貓還是狗，這樣的圖檔有無限張。我們不可能窮舉每張圖檔。
這種情況下，我們的目标變為降低錯誤的次數。
Weight Majority
現在考慮另一種辦法，通過給每個專家附上權重，每輪prediction為權重和較大的label。
直覺的來說就是給每個專家投票權，而投票權有大有小，權重大的專家有更大的決定權，而投票結果較多的label就是預測值。
若一個專家犯了錯，把這個專家的權重乘上一個懲罰因子β ，（<1）。
可以求得最後的錯誤上限為：
過程：
當majority 犯錯的時候，majority 乘上β ，因為多數派要大于0.5Wt，是以右邊式子是最大值。
是以W權重的更新大小為
一開始的W1值為n，通過M次的懲罰，第t輪的時候權重和縮小的不少，但依然比每個專家單獨權重要大。Mi就是任意專家。
當需要預測的值不是類别而是實數值的時候，我們不使用投票法，而使用内積的方式求預測值。
預測器：
情景思考：如果沒有一個專家能永遠正确決策，但通過觀察，發現有兩個專家或多個達成一緻（多個專家的組合）的時候決策正确率能提高不少，這個時候我們如何修改原來的算法？
這屬于典型的布爾表達式問題。我們先來看最簡單的幾種情況。通過添加或修改新的feature我們可以重新設計和訓練預測器
根據不等式可以得到新的錯誤界限。假設需要k個專家，他們共同的決策結果能産生最少的累積誤差，很容易想到新的專家有
位。将組合數的上界帶入原錯誤界中，得到，
perceptron感覺機
感覺機這個東西有很多年頭了，有時候被當作神經網絡的單個節點。在這一課中，perceptron代表的是一種簡單算法的決策模型。跟svm比較相似。
在一個空間中，有很多很多的點，（資料點），假如這些資料對應的label 是兩個類别，也就是說，在空間上這些點可以被一個平面分開。
在這個圖上，這個平面是中間加粗的線，+ -是兩個不同的類别。γ是兩個類别距離超平面的最短距離。
（讀者：我去，這不就是svm嗎？）哈哈，和svm不一樣的是這個算法比較簡單。
注意這個也是線上算法，也就是說，我們每次拿到一個資料就進行一次計算。
我們有m個資料，是以可以用for循環。
直覺的說，我們先預設一個w 值，w是一個向量，決定平面的方向。然後通過w和x資料預測結果。
将預測結果與實際結果比較，如果不一樣，就更新w值。這裡跟梯度下降差不多，相信圖檔可以看林軒田的視訊。
也就是說根據預測情況，選擇要不要微調w。如果w改變了，平面就會旋轉之類的。
還是一樣給出bound，哎這就是數學課！
。
現在，一個新的算法華麗登場！
Winnow algorithm
跟剛才一樣，這個算法也适用于同樣的場景。winnow也是更新w，隻不過是乘法更新，不是加法更新！
觀察到這裡的x 取值為0或者1，0意味着不相關，1意味着相關。
注意6的更新方式，隻有在預測出錯的時候權重才會更新，也就是說隻有兩種情況。
1. yt =0 ，yt hat = 1,, w * 1/2
2 yt = 1, yt hat = 0 w * 2
也就是說，當預測值過大，權重減半，當預測值過小，權重雙倍，而且隻有當對應專家值為1 的時候對應w才會更新。
也就是說最後學習結果是一個disjunction。
省略cover set。。。