4 Linear Models for classification
這一章開始介紹分類問題的線性模型。在具體介紹之前，先介紹幾個概念。
為什麼說是線性模型，因為在這一類模型中，決策面是輸入向量x的線性函數，這個線性不同于回歸模型中的線性，線性回歸模型指的是模型是參數的線性函數。什麼是“線性可分”？資料集可以被我們前面說的x的線性決策面分開，則稱資料集是“線性可分的”。
在第一章中，曾經介紹過有三種方法可以解決分類問題：1.判别函數 2.直接對p(ck|x)模組化(判别模型) 3.對p(x|ck),p(x)分别模組化，再利用貝葉斯理論，計算後驗機率p(ck|x)。
這一章前三節分别講了這三種方法，下面首先進入判别函數的介紹。
4.1 Discriminant Functions
4.1.1 Two classes
先來考慮比較簡單的x的分類目标K=2，即隻有兩類的情況。
最簡單的判别函數當然是取x的線性函數：
當y(x)>=0的時候，把x歸為C1類，當y(x)<0的時候，把x歸為C2類，是以這裡的決策面就是wx+w0=0。作者之後又對此進行了一些幾何角度的解釋，w0控制的是決策面的位置，w控制的是決策面的方向(注意後面的Fisher Linear Discriminant要用到這個結論)。
4.1.2 Multiple classes
當K>=2,即x的分類目标大于兩類的時候，無論我們用K-1個(not in that class)或者是K(K-1)/2(every possible pair of classes)個4.1.1節講到的"two classes classifier"，都會引出一個ambiguous region。是以面對K類問題時，采用如下方法：
考慮一個包含K個線性判别函數的K分類器：
隻有當對于任何j！=k，都有yk(x)>yj(x)時，把x歸于第K類。之前的“兩類”問題，我們既可以用4.1.1中的一個y(x)解決，也可以用類似于這裡的y1(x),y2(x)來解決。
讨論過判别函數的具體形式之後，該讨論一下如何來拟合判别函數中的參數w了。書上大緻講了三種方法，least squares，FLD，perceptron algorithm。
4.1.3 Least squares for classification
在第三章中，Least squares是常用的Loss函數，是以很自然的，就會想到在這裡最小平方适不适用。但在這最小平方沒有任何機率解釋，唯一的解釋是當Loss函數是最小平方的時候，對E[L]求最小值，會得到y(x)取E[t|x]時E[L]最小的結論，而在“兩類”問題中，E[t|x]是後驗機率的向量？(這個點上不太懂，就是E[t|x]是怎麼由後驗機率給出的)。
當面對K類問題時，我們有K組w向量，x，t也相同(這裡的t是1-of-K coding scheme)，是以把這三組量都表示為矩陣形式的時候，我們得到了error function：
這裡為什麼求的是矩陣的迹？
這樣我們就可以通過最小化error function來解出W：
作者接下來講了一些least squares的弊端，首先，無法保證y(x)的取值在0到1之間。其次對于噪聲點的魯棒性也比較差，書上兩幅圖4.4和4.5對此做了解釋。最後，作者大緻講了一下最小平方法效果不太好的原因，因為在回歸問題中，我們是在對目标值做了高斯分布的假設之後得出least square的，而在分類問題中，目标值隻有兩種取值，顯然和高斯分布相去甚遠。
4.1.4 Fisher's Linear Discriminant
關于FLD : 将高維的樣本投影到較少的次元，以達到抽取分類資訊和壓縮特征空間維數的效果。投影後保證樣本在新的子空間有最大類間距離和最小類内距離，即樣本點在該空間有最近可分離性。
利用下式将輸入向量投影到一維空間：
y>=w0時x歸為C1類，y<w0時x歸為C2類，這樣就得到了如前所述的标準線性分類器。但注意到将多元輸入變量投影到一維的過程中可能會損失很多資訊，而之前說到過，w是決定決策面的方向，是以這就回到主題上來了，如何拟合w。
作者定義的幾個量都不難了解，類内距，類間距，最後我們使用這幾個建立起一個最大化目标：
因為隻在乎輸入變量投影的方向，是以在舍棄掉一些标量後，得到了關于w方向的式子：
我們可以利用投影後的資料做一些分類工作，将會簡單很多。
4.1.5 Relation to least squares
作者通過指定t1與t2的值，對least squares進行了一些推導得出了與fisher 判别相同的w方向，即說明了fisher是least square的一個特例。
4.1.6 Fisher‘s discriminat for multiple classes
這一節把Fisher判别擴充到了K類問題上，原理與4.1.4基本相同，不贅述了。
4.1.7 The perceptron algorithm
定義perceptron algorithm：
當y(x)=-1的時候，将x歸為C2類，當y(x)=1的時候，将x歸為C1類。
有了預測函數，下面該找error function了，注意到當tn=1的時候，我們希望a>0,而當tn=-1時，我們希望a<0,這樣便發現，我們始終希望a*tn>0,對于那些分類錯誤的點，我們希望-a*tn越小越好，是以便得到了error function：
對error function使用随機梯度下降，得到：
作者用圖4.7很好的對此處的梯度下降進行了幾何解釋。對于perceptron algorithm，如果資料線性可分，那麼根據上面的方法w一定可以在有限步驟内收斂，假設資料線性可分，最後的解有多個，那麼取到哪一個要根據參數的初始化和樣本點的出現順序而定了。perceptron的限制在于，它不能輸出預測的機率值，也無法擴充到K>2類的問題中，最重要的是，它是基于固定的basis function的。