Tips：未進行解釋的符號主要參照lec1睦裳，部分需要參照其他lec～
前面幾個Lecture介紹了why can ML赫悄？并介紹了一個簡單的model：PLA 披坏。有了理論保障态坦，如何設計algorithm？下面進入How can ML 階段 ^ - ^
Lec 9 ：Linear Regression
前面提到的基本是binary classification棒拂，如 銀行根據(jù)顧客信息決定是否發(fā)放信用卡……如果換成銀行想得到的是顧客的信用額度伞梯，這時就是regression問題了～
這章介紹一個新的model：Linear Regression～
1、Hypothesis & Error Measure
regression 的輸出空間y = R帚屉，什么樣的H可以輸出實數(shù)谜诫？
已有顧客的data：x = （x0，x1攻旦，x2喻旷，……，xd）牢屋，每一維的數(shù)據(jù)有不同的含義且预，如收入、年齡烙无、性別锋谐、工作等等。自然地截酷，顧客的信用額度可以用一個加權分數(shù)來衡量：
所以線性回歸模型的Hypothesis可以表示為：
嗯……你會發(fā)現(xiàn)這個h（x）和perceptron的h（x）很像涮拗，只是少了取sigh。
那linear regression的H長什么樣子呢？x是一維向量和二維向量時如圖
這時的關注點不再是 正負 三热，而是 距離鼓择。g（x）和f（x）的距離，即紅線部分就漾。一般把紅線叫做 誤差 或 residuals（余數(shù)呐能，在技法課程中還會看到這個概念）。
這個H的衡量標準是什么从藤？regression通常都會使用squared error 催跪，err（y^,y）= (y^ - y)的平方锁蠕，則Ein和Eout表示為：
注：經(jīng)過上一節(jié)討論夷野，現(xiàn)在的setting是有noise的，x服從一個分布P（x）荣倾，y也會服從一個分布P（y|x）悯搔，x、y是聯(lián)合分布舌仍。
所以接下來的問題就是 minimize Ein（w）妒貌，求的w也就求得g。
2铸豁、minimize Ein（w）
已經(jīng)有了Ein（w）的表達式灌曙，將其轉化為矩陣形式，方便后續(xù)計算：
現(xiàn)在優(yōu)化目標是：
這個式子更簡潔节芥，w是唯一變量在刺。Ein（w）是連續(xù)函數(shù)continuous，且可微differentiable头镊，凸函數(shù)convex 蚣驼。形象點兒就是下圖這樣的：
學過微積分的應該知道，這時候存在最低點相艇，且最低點梯度為0.所以找到使梯度為0的w就是結果颖杏。（這個思路很重要）
那就算算梯度咯……
展開Ein（w）：
用A、b坛芽、c替換已知項：
得到：
令梯度等于0留储，可以求得w。
大部分情況下 （XTX）都是可逆的（因為N>>d+1咙轩，本人并沒有理解）欲鹏。如上圖所示，將一部分定義為pseudo-inverse X+,虛假的逆矩陣臭墨。在（XTX）不可逆時赔嚎，線代里面有很多求 pseudo-inverse 的方法，實際應用中，也會有很多實現(xiàn)好的工具可以用來求X+尤误，建議直接計算X+求得w侠畔。
至此，我們就得到一個完整的Linear Regression 模型损晤，完整的algorithm：
這是一個simple & efficient的算法软棺，我們只需要計算X+。
3尤勋、LR真是一個學習算法嗎喘落？？最冰？瘦棋！
似乎我們只是計算了一個X+就得到了結果，既沒有通過迭代優(yōu)化Ein也沒有優(yōu)化Eout暖哨，這真的是一個學習算法嗎赌朋？其實答案必然是，why篇裁？我們已經(jīng)使得Ein最小沛慢，dvc有限時則Eout接近Ein。實際上达布，迭代優(yōu)化的過程隱藏在X+的計算過程中了………只要最后Eout是good团甲，也就可以說 learning happened！
VC理論可以保障Eout會很小黍聂，對于LR還有另外一種解釋躺苦，這種解釋得益于analytic solution（就是可以輕易分析出結果的意思）：
先從Ein 的平均出發(fā)，Eout推導與之類似分冈。Ein的平均與VC關注的不一樣圾另，VC關注的是個別的Ein。這里的平均是指多次抽取雕沉，計算多個Ein集乔，再取平均。最終得到的結果是Ein的平均與“noise level”坡椒、“d + 1”扰路、“N”有關……
計算Ein時，Ein表示形式轉化為上圖倔叼，稱XX+為 hat matrix H汗唱，為什么？因為y乘上這個矩陣后被戴上了一個帽子 ^……哈哈哈哈哈哈哈哈丈攒，這是千真萬確哩罪。
hat matrix做了什么事情授霸？用圖解釋。
粉色部分可以看成是各個x組成的一個空間际插，span of X碘耳，X散在一個空間里面。y^ = X W框弛，其實y^就是各個x的線性組合辛辨，所以y^會在這個X 的span里面（這里就理解為一個平面就好了，輸入的x都在這個平面上瑟枫，所以線性組合出的y^也會在這個平面上）斗搞。
紫色部分是Y向量，n維慷妙。綠色部分則是y-y^的值僻焚，我們希望y - y^越小越好，最小的情況就是垂直的時候景殷，即圖中綠色的線溅呢。所以其實hat matrix就是把y投影到span of X澡屡，得到y(tǒng)^猿挚。（I - H）y就是y - y^，算得residual驶鹉。
直接給出一個結論：trace（I - H） = N - （d + 1）绩蜻，trace是對角線和。why室埋？沒給出办绝。但是其哲學含義為：原本自由度為N，投影到一個 d+1維的平面姚淆，自由度減少d + 1.
下面再看一張圖孕蝉，理解noise做了什么事情？
紅色f（X）是理想中的那個遙不可及的夢腌逢，紫色y是加入了noise 的f（X）降淮，y = noise + f(X) 。從圖上可以看出搏讶，對noise做（I - H）投影同樣是得到 y - y^這條綠色的線＜驯睢！媒惕！沒錯系吩，residual都是noise惹得禍啊……
至此，我們就可以重寫Ein這個式子：
恩妒蔚，這樣我們就得到了這節(jié)開始給出的結論：
Eout與Ein類似穿挨，只是Eout是“加上”月弛。如何理解呢？哲學上科盛，Ein是我們拿在手上的data尊搬，得到的結果自然會偏心使得Ein小一些，而Eout如果也偏向于小一些土涝，就會偏兩次佛寿！所以，Eout加但壮，再偏回來……哈哈哈哈哈哈冀泻，這節(jié)的哲學都很有趣！
Ein和Eout的平均作圖蜡饵，稱為 Learning Curve （后續(xù)章節(jié)會再提到這里）：
σ平方 就是 noise level 弹渔。
這里Ein和Eout的平均差異是 2（d+1）/N 。而之前VC是考慮的最壞情況下差多少……
到這里溯祸，應該不得不相信LinReg真的是一個學習算法……
（個人小結一下：
前面的PLA已經(jīng)感受到即便很直觀很直接的簡單模型也都有著豐富的數(shù)學理論在里面肢专，后面會提到更多更復雜的模型，每一個都有數(shù)學的哲思在里面焦辅，但是至于是先有蛋還是先有雞這件事博杖，我也搞不清楚。不得不感慨筷登，數(shù)學萬歲剃根！
另外，這章的整體思路其實和后面介紹model的章節(jié)的思路都是類似的前方，大概就是 先有一個Hypothesis狈醉，然后找到一個error measure，然后你就通過各種數(shù)學手段去最優(yōu)化惠险，就得到了一個學習算法……恩苗傅，基本都是這樣的。當然都是說起來容易做起來難啊……
哭）
4班巩、LinReg VS LinClassification
線性回歸和線性分類比較下吧……
直接上圖渣慕，不解釋：
上面說明了它們之間的區(qū)別，但這不是重點趣竣，重點是它們之間微妙的聯(lián)系摇庙！
其實{-1，+1} ∈ R遥缕，而線性回歸又很好解卫袒，那么是不是可以用線性回歸來做分類呢？单匣！可以夕凝！
算出regression的分數(shù)后取sign就好了……嘿嘿嘿宝穗，理論上怎么解釋呢？上圖码秉！
這個圖是什么意思呢逮矛？線性回歸和線性分類的主要區(qū)別就是錯誤衡量標準，這張圖顯示了 err（sqr）是err（0/1）的上限转砖，所以须鼎，如果err（sqr）在我們接受的范圍內，那err（0/1）必然也可以接受府蔗。（這個思路很重要）晋控。嗯哼~我們又找到了一個err（0/1）的上限，比VC bound更loose的上限姓赤。做回歸效率更高赡译，把err（0/1）換成err（sqr），相當于用上限的loose換取了efficiency不铆！
通常用回歸進行分類表現(xiàn)不會太差蝌焚，但是一般情況下，是用線性回歸算得的w作為線性分類（PLA or Pocket）的w0 誓斥，這樣可以加速分類的速度只洒。（ 這個思路很重要）
