之前我們介紹了Logistic回歸以及它的誤差為交叉熵誤差，介紹了梯度下降算法gradient descnt來獲得最好的w。接下來我們將回顧之前的線性模型，將其延伸到更多的分類問題中。

一、二元分類

我們上一節課介紹的三個線性模型

線性分類問題使用了：

1.線性scoring function?

2.h = sign(s)

3.0-1誤差

NP難的，不好解。

線性回歸問題使用了：

1.線性scoring function?

2.h =?s，不需要使用函數 sign(x)

3.平方誤差

有閉式解。

Logistic回歸：

1.線性scoring function?

2.h =?

3.交叉熵誤差

梯度下降法求解。

他們都算了一個分數scoring function?。

我們現在要把上面那三個問題都用于分類（主要是后兩個）。

線性回歸的輸出空間是R，+1，-1是其中兩個特殊值。

logistics回歸的資料和現行分類的資料是一樣的。

線性分類一般有兩步：

現在我們使用誤差函數（將上面換一種寫法）：

（最后一步是為了和其他函數作比較）

線性回歸：

整合成一步：

Logistic回歸：

整合成一步：

可以看到上面的誤差函數中都有ys，那么ys的物理意義是什么？

答：ys就是指分類的正確率得分，我們希望他是正的，而且希望他越大越好。

作出上面三個誤差函數的圖像來比較，其中橫坐標是ys

err0/1

呈階梯狀的，我們要看sign(ys)的正負，如果是正的，err0/1恒取最小值0。否則err取1.

errSQR

呈拋物線形式，我們要看ys與1相比，取平方。errSQR與err0/1不同，比如在ys=3時，err0/1誤差為0，而errSQR的值挺大。在ys=1時，取得最小值。且在ys=1左右很小區域內，err0/1和errSQR近似，這意味著如果今天某個資料在errSQR上得到很小的值的話，它在err0/1也會取得很小的值。

errCE

呈指數下降的單調函數，ys越大，其值越小。ys越來越大，誤差函數趨近于0。整體來說，在ys越大時候，err0/1和errCE近似。我們可以來說errCE上得到很小的值的話，它在err0/1也會取得很小的值。

但是我們發現errCE并不是始終在err0/1之上，所以為了計算討論方便，我們對errCE做一個scale，可以看到在ys=0處，errCE與err0/1切在一起了，如下圖：

此時，scale errCE始終在err0/1之上。

scale errCE成為err0/1的上限。

是幾個資料做平均，是在無數個資料上做平均，所以不等式仍然成立。

從我們知道的理論出發，我們知道err0/1的VC，然后得到：

之前提到是模型復雜度。

從的角度看，

這表示：如果我們把logistics回歸里面的err做好的話，那么某種角度來說也把err0/1做的還不錯。

使用不同方法做分類的優缺點：

PLA：

1.優點

有效+在線性可分的時候有很好的保證

2.缺點

如果線性不可分，就只能用pocket做了，但就沒有上面PLA效果那么好了。

線性回歸：

1.優點

有閉式解，最容易求解

2.缺點

在ys越大或者越小的時候，它和err0/1就差距很大了。

logistics回歸

1.優點

比較好求解

2.缺點

ys越小的時候，它和err0/1就差距會比較大。

注：線性回歸通常的用處是為PLA，pocket，logistics回歸提供一個初值。

二、隨機梯度下降

回憶一下PLA，每次選擇一個資料進行更新，每次迭代的時間復雜度是O(1)。logistics回歸每次要計算所有的資料然后做平均，看起來每一輪會花比較顯著的力氣，每次迭代的時間復雜度是O(N)。我們能不能讓logistics回歸每一輪和PLA一樣快。

之前的logistics回歸的迭代步驟是上面這樣的，現在我們不要計算這么多樣本然后做平均，只要取出一個樣本計算（近似的）下降方向。

這種隨機抽取一個資料的方法叫做隨機梯度方法：

我們可以把所有資料的平均值看做我們每次隨機取出樣本的期望值。即

隨機梯度=真實梯度+noise（這些noise的期望為0）

于是，隨機梯度法為：

想法：把正式的梯度替換為隨機梯度。

好處：簡單、容易計算，容易用于大數據或者在線學習（資料一筆一筆來）。

缺點：不太穩定。特別是步長太大的時候。

之前我們講過的PLA中

與今天的logistics回歸做比較：

可以發現

1.SGD?logistics回歸可以看做是稍“軟”一點的PLA，因為PLA只對分類錯誤的點進行修正，而SGD logistic regression每次迭代都會進行或多或少的修正。

2.當分值很大時候，且η=1時，那么對logistics回歸用SGD求解就相當于PLA。

現存的問題：

如何確定停機準則（怎么知道算法以及做好了？）? ?

分析：梯度下降法會看梯度是否等于0來判斷到谷底了嗎？但是顯然隨機梯度方法不適合這樣判斷，不然再計算全梯度就白做簡化了。一般讓迭代次數足夠多我們就認為它跑到谷底了（但這只是一種大家的認為）。

如何確定學習率η？

分析：之后會具體分析如何選擇它，但是現在我們可以直接令η=0.1（經驗上這是一個很好的數字，0.126）

三、用?logistics回歸進行多分類

之前我們一直講的都是二分類問題，現在我們看看如何把它延伸做多分類問題。通俗來講：從是非題變到選擇題。

有四個類別不好做，那么我們想是否可以先把某個類別分出來？答：可以做一個二元分類器，先把‘’分出來。（同理也可以把任何一種形狀與其他形狀分開來）

→

如下圖，按照上述四個分類器，得到劃分區域，在一些區域（右上角熒光綠區域）全是‘’，在一些區域（黃色）全是‘◇’，在粉色區域全是‘△’，在藍色區域是‘☆’?？墒欠诸惼鲿稿e，如果某個區域（比如黃色綠色緊挨著的區域）有兩個分類器都搶著說是自己的區域怎么辦？以及在一些區域（中心區域）四個分類器都說不是自己的區域怎么辦？

看到{-1，+1}兩個值來標記，分類器只會說是自己的還是不是自己的區域，就會造成上面的問題，我們現在用softy的模型，我不說是不是，我只說可能性，比如

可以看到有一些模糊的邊界，因為模糊的邊界代表在此處的可能性不一定是0或1，可能是在0.5的附近。

四個分類器結果為（都是軟化了原來的分類）：

將他們都組合起來，在那些不確定的區域，我可以選一個可能性最大的。

區域類型：選擇使得幾率P最大的那個K類。（logistics函數是算幾率的，但也是單調的，所以可以直接比較里面的分數，這里灰色是指不重要，可以省略）

這種多分類的處理方式，我們稱為One-Versus-All(OVA) 。我們每次都拿一個和其他所有比。

對每一個類別跑一個logistic函數，其中該類別的資料設置為正，其余資料設置為負，跑完會得到一個權重w，然后用w對該筆資料計算分數。

這種方法的優點是：

1.簡單高效

2.可以使用logistic regression模型來解決，從而以后碰到可以輸出一個概率的模型或者一個可以比大小的數值的模型，都可以套用

缺點是：

1.如果數據類別很多時，那么每次二分類問題中，正類和負類的數量差別就很大（100個類，1類vs99類），數據不平衡unbalanced，這樣會影響分類效果。

以后會講上面問題怎么解決。此外，在這里我們沒有強調幾率加起來必須是1(統計上考慮到了這個問題)。

四、用二元分類進行多分類

上面說到如果數據類別很多時，那么每次二分類問題中，正類和負類的數量差別就很大（100個類，1類vs99類），數據不平衡。那么我們可以用1類vs1類嗎？而不是一對多。

我從所有的類別中選兩個先看看這兩個里面哪個是我們要的答案。（比如哪邊是‘’，哪邊是‘◇’）

同上面一樣，兩兩進行比較，會得到六種（排列組合，3+2+1）結果：

然后再怎么確定呢？比如怎么分出‘’？

我們看與‘’有關的分類器：第1,2,3個圖在訓練時有把‘’包含進去，我們可以得到結論，大概右上角是‘’。

換一種角度：

對于右上角，圖1,2,3分類說他是‘’，圖4說它是‘◇’，圖5，6說它是‘☆’.所以右上角這塊被判定為票數最多的‘’。

每個圖形看一遍，可以得到：

我們可以看做這六個圖是投票器，對每個區域進行投票，票數最多就判定為是什么類別。

這種方法叫做One-Versus-One(OVO)。我們每次都拿一個和另外一個比。

我們把資料拿來，先確定我們要分類那兩個類（一個看做正類，一個看做負類），這樣兩兩分類就可以做出l個分類器，我讓這l個分類器去投票，看看哪一個類別獲得最大的支持。

這種方法的優點是：

1.簡單高效，雖然兩兩分類做的分類次數多了，但是每個分類器用的資料少了。

2.可以使用二元分類模型來解決，從而以后可以套用任何可以做二元分類的模型。

缺點是：

1.由于是兩兩分類，所以分類器會很多（w會多），存儲空間因此變大了，每次預測的時間也變長了，也就是做了更多的訓練。

在類別不太多的時候，OVA和OVO都比較常用。

總結：

?

?

?

?

?

?

?

?

?

?

?

總結

以上是生活随笔為你收集整理的林轩田《机器学习基石》（十一）—— Linear models for classification的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。