1. 線性判別函數

本章介紹的線性判別函數都歸屬于判別式模型，即對于分類問題，根據判別函數(g(x))的取值進行判斷，比如正數歸為第一類，負數與零歸為第二類。關于判別式模版與生成式模型的區別可以閱讀我以前的博客，最典型的生成式模型是貝葉斯分類器，這個在之前的博客中也有介紹。
在介紹具體算法之前，先了解一下線性判別函數的基本概念。

1.2 線性判別函數基本概念

對于線性可分情況，線性判別函數(g(x))與判別界面(H)如下圖所示：

對于線性不可分情況：

線性判別函數的形式化形式為：

[g ( mathbf { x } ) = mathbf { w } ^ { t } mathbf { x } + w _ { 0 }
]

(mathbf { x } = left( x _ { 1 } , x _ { 2 } , ldots , x _ { d } ight) ^ { t })，是特征矢量，(d)是特征維度的大小。
(mathbf { w } = left( w _ { 1 } , W _ { 2 } , dots , W _ { d } ight) ^ { t })，是權矢量。
(W _ { 0 }) 是偏置。
線性判別函數的增廣形式（便于書寫，便于設計目標函數）：

[g ( mathbf { y } ) = mathbf { a } ^ { t } mathbf { y }
]

(mathbf { y } = left( 1 , x _ { 1 } , x _ { 2 } , ldots , x _ { d } ight) ^ { t })，是增廣的特征矢量，在原始向量前插(1)即可。
(mathbf { a } = left( w _ { 0 } , w _ { 1 } , W _ { 2 } dots , W _ { d } ight) ^ { t })，是增廣的權矢量。

在學習該增廣形式的時候，我曾思考過，既然可以將將線性函數轉化為兩個向量的點乘，那在深度學習中(以pytorch為例)，設計線性層(nn.Linear)時為什么還要令參數bias=True，直接不需要偏置，在輸入向量中拼接一個維度(值為1)豈不是更加方便。答案當然是否定，我仔細思考后發現，如果這么做的話，對于每一個輸入對會有一個獨立的bias，因為新拼接的“1”值會隨著反向傳播進行迭代更新（每個輸入的更新結果不同），此時bias便失去了意義，不再是與線性函數函數綁定，而是變成了輸入的一個特征。

兩類問題的線性判別準則：

[g ( mathbf { x } ) = mathbf { w } ^ { t } mathbf { x } + w _ { 0 } left{ egin{array} { l l } { > 0 , } & { mathbf { x } in omega _ { 1 } } \ { < 0 , } & { mathbf { x } in omega _ { 2 } } \ { = 0 } & {拒識 } end{array} ight.
]

線性分類器的分類界面三維空間可視化：

該界面有幾個特點：
1.線性分類界面(H)是(d)維空間中的一個超平面；
2.分類界面將(d)維空間分成兩部分，(R_1)，(R_2)分別屬于兩個類別；
3.判別函數的權矢量(w)是一個垂直于分類界面(H)的矢量，其方向指向區域(R_1) ；
4.偏置(w_0)與原點到分類界面(H)的距離(r_0)有關：

[r _ { 0 } = frac { w _ { 0 } } { | mathbf { w } | }
]

1.3 線性判別函數的學習

以下內容全部采用增廣形式的寫法進行介紹。
線性判別函數的學習目的，其實就是想通過(n)個訓練樣本(mathbf { y } _ { 1 } , mathbf { y } _ { 2 } , dots , mathbf { y } _ { n })，來確定一個判別函數(g ( mathbf { y } ) = mathbf { a } ^ { t } mathbf { y })的權矢量(a)。其中n個樣本集合來源于兩個不同類別。

在線性可分的情況下，希望得到的判別函數能夠將所有的訓練樣本正確分類。
線性不可分的情況下，判別函數產生錯誤的概率最小。

判別函數的非規范化形式：

[left{ egin{array} { l l } { mathbf { a } ^ { t } mathbf { y } _ { i } > 0 , } & { mathbf { y } _ { i } in omega _ { 1 } } \ { mathbf { a } ^ { t } mathbf { y } _ { i } < 0 , } & { mathbf { y } _ { i } in omega _ { 2 } } end{array} ight.
]

判別函數的規范化i形式：

[left{ egin{array} { c l } { mathbf { a } ^ { t } mathbf { y } _ { i } > 0 , } & { mathbf { y } _ { i } in omega _ { 1 } } \ { - mathbf { a } ^ { t } mathbf { y } _ { i } > 0 , } & { mathbf { y } _ { i } in omega _ { 2 } } end{array} ight.
]

在之后的感知器算法、 LMSE中，均依據規范化的形式進行介紹，規范化后會使得目標函數形式比較簡單。
規范化是在輸入數據上進行，將屬于第二個類別的數據乘上(-1)即可。
需要注意，因為本節內容是在函數的增廣形式下進行介紹，因此在規范化之前需要對于每個類別的數據都拼接一個特征“1”。

2. 二分類問題

這里介紹常用的線性分類函數，感知器、LMSE和SVM，其中SVM本身是線性分類器，但當其加入核函數之后可以達到非線性分類器的效果，實踐中我們經常使用的也是非線性SVM，關于核函數的概念會在后續博客中介紹。

2.1 感知器算法Perception

在介紹感知器算法之前，先了解一下什么是感知器準則。

2.1.1 感知器準則

顯然對于分類問題，最直觀的準則函數定義是最少錯分樣本數準則：

[J _ { N } ( mathbf { a } ) =樣本集合中被錯誤分類的樣本數
]

其函數可視化形式如下：

由于該函數是分段常數函數，不便于采用梯度下降的學習策略進行學習，因此該準則不是一個好的選擇。
更好的感知器準則函數定義如下所示（著名的感知器準則）：

[J _ { P } ( mathbf { a } ) = sum _ { mathbf { y } in mathcal { Y } } left( - mathbf { a } ^ { t } mathbf { y } ight)
]

[
abla J _ { P } = sum _ { mathbf { y } in mathcal { Y } } ( - mathbf { y } )
]

其函數可視化形式如下：

個人認為該準則最大的好處是梯度函數比較直觀，而且容易計算，適用于梯度下降學習策略。
更加細節的感知器訓練方式，會在后續的實驗中進行詳細介紹，并開源實驗代碼。

2.1.2 感知器算法的特點

感知器算法的特點如下：

當樣本線性可分情況下，學習率合適時，算法具有收斂性。
收斂速度較慢。
當樣本線性不可分情況下，算法不收斂，且無法判斷樣本是否線性可分。

2.2 最小平方誤差算法LMSE

如2.1所說，感知器算法對于線性可分問題能夠得到很好的結果，但是對于線性不可分問題往往不能收斂。按照正常人的思考，即使是對于一個線性不可分問題，我們也希望線性判別函數能夠得到一個“錯誤最小”的解，而不應該是算法無法收斂的程度。
基于這種思想，我們得到了一個在線性可分和線性不可分條件下都有很好性能的折衷算法LMSE。
LMSE將求解線性不等式組的問題轉化為求解線性方程組。所謂線性不等式組便是1.3中介紹的規范化后判別函數不等式組。我們希望每個不等式都是大于0的，既然這樣，LMSE設定了任意的正常數(b)，將不等式轉化為等式，只要等式成立，那左邊的多項式一定是大于0的。
LMSE的函數形式如下所示：

[left( egin{array} { c c c c } { y _ { 10 } } & { y _ { 11 } } & { cdots } & { y _ { 1 d } } \ { y _ { 20 } } & { y _ { 21 } } & { cdots } & { y _ { 2 d } } \ { vdots } & { vdots } & { ddots } & { vdots } \ { y _ { n 0 } } & { y _ { n 2 } } & { cdots } & { y _ { n d } } end{array} ight) left( egin{array} { c } { a _ { 0 } } \ { a _ { 1 } } \ { vdots } \ { a _ { d } } end{array} ight) = left( egin{array} { c } { b _ { 1 } } \ { b _ { 2 } } \ { vdots } \ { b _ { n } } end{array} ight)
]

可簡化寫為：

[mathbf { Y } mathbf { a } = mathbf { b } , quad mathbf { b } > 0
]

2.2.1 LMSE的準則函數

定義誤差矢量(e)，用(e)長度的平方作為準則函數：

[egin{array} { c } { mathbf { e } = mathbf { Y } mathbf { a } - mathbf { b } } \ { J _ { S } ( mathbf { a } ) = | mathbf { Y } mathbf { a } - mathbf { b } | ^ { 2 } } end{array}
]

我們想該準則函數越小越好，這樣不等式的值就越接近于正常數(b)的值，也就達到了不等式組恒為正的目的。

2.2.2 LMSE的求解過程

LMSE求解的目的是得到符合要求的權矢量(a)。
求解方法分為兩種：偽逆求解法與迭代求解法。
偽逆求解法：

LMSE準則其實就是誤差平方和最小問題，屬于經典的數學問題。偽逆求解法其實是令準則函數(J _ { S } ( mathbf { a } ))梯度值為0，從而計算得到一個必要條件。
利用數學公式推導，得到權矢量的解析解。

[egin{array} { c } {
abla J _ { S } ( mathbf { a } ) = 2 mathbf { Y } ^ { t } ( mathbf { Y } mathbf { a } - mathbf { b } ) = mathbf { 0 } } \ { mathbf { Y } ^ { t } mathbf { Y } mathbf { a } = mathbf { Y } ^ { t } mathbf { b } } \ { mathbf { a } = left( mathbf { Y } ^ { t } mathbf { Y } ight) ^ { - 1 } mathbf { Y } ^ { t } mathbf { b } = mathbf { Y } ^ { + } mathbf { b } } end{array}
]

(mathbf { Y } ^ { + } = left( mathbf { Y } ^ { t } mathbf { Y } ight) ^ { - 1 } mathbf { Y } ^ { t })稱為偽逆矩陣。
之所以這么做是因為輸入矩陣(Y)往往是奇異矩陣，也就是不可逆的，因此采用上述的偽逆求解方式。
需要注意的是，(mathbf { Y } ^ { t } mathbf { Y })當樣本數多的時候一般是可逆的，當特征數大于樣本數時，基本是不可逆的，也就不能采用這種偽逆求解法。
迭代求解法：

對于準則函數(J _ { S } ( mathbf { a } ))的進一步計算為：

[J _ { s } ( mathbf { a } ) = | mathbf { Y } mathbf { a } - mathbf { b } | ^ { 2 } = sum _ { i = 1 } ^ { n } left( mathbf { a } ^ { prime } mathbf { y } _ { i } - b _ { i } ight) ^ { 2 }
]

準則函數的梯度為：

[oldsymbol {
abla } J _ { s } = sum _ { i = 1 } ^ { n } 2 left( mathbf { a } ^ { prime } mathbf { y } _ { i } - b _ { i } ight) mathbf { y } _ { i }
]

迭代求解法就是采用梯度下降的方式進行實現，具體學習過程在后學的實驗博客中進行介紹。

迭代求解過程中往往省略掉梯度中的系數(2)，因為該數值可以整合進學習率中。

實踐過程中，偽逆求解法的效果不如迭代求解法效果好

2.2.3 LMSE算法的特點

算法的收斂程度依賴于學習率的衰減。
算法對于線性不可分的訓練樣本也能夠收斂于一個均方誤差最小解。
取(b=1)時，當樣本數趨于無窮多時，算法的解以最小均方誤差逼近貝葉斯判別函數。
當訓練樣本線性可分的情況下，算法未必收斂于一個分類超平面。

LMSE在線性可分的問題中，得到的效果不是很好，舉例如下：

2.3 支持向量機SVM

這里是只是簡單介紹SVM的基本概念，并解釋其為什么是最優線性分類器，具體數學推導比較復雜，不做介紹。

首先思考這樣一個問題，為什么要引入支持向量機，他與傳統線性分類器之間的區別是什么？

從這張圖中，可以看見(H_1), (H_2)都是對于現有訓練數據中的最優分類超平面。
但是對于未來要預測的不存在與馴良樣本集合中的數據，顯然(H_1)的效果會更好。因為他距離各個類別的“距離最遠”，魯棒性肯定更強。而(H_2)離紅色樣本太近了，如果某一待預測紅色樣本的輸入特征稍微“向左”偏移一點，(H_2)分類界面便認為其屬于藍色樣本，分類錯誤。
SVM便是出于這種"距離最遠"的想法，希望能夠得到(H_1)類型的分類界面。

2.3.1 SVM數學概念

SVM采用幾何間隔，來描述“距離”這一概念，而幾何間隔的計算需要引入函數間隔。

函數間隔：樣本(x_I)到分類界面(g(x)=0)的函數間隔(b_i)，定義為：

[b _ { i } = left| g left( mathbf { x } _ { i } ight) ight| = left| mathbf { w } ^ { t } mathbf { x } _ { i } + w _ { 0 } ight|
]

幾何間隔；

[gamma _ { i } = frac { b _ { i } } { | mathbf { w } | }
]

如圖所示：

2.3.2 為什么是最優線性分類器

樣本集與分類界面之間的幾何間隔$gamma $定義為樣本與分類界面之間幾何間隔的最小值。
最優分類界面：給定線性可分樣本集，能夠將樣本分開的最大間隔超平面。
SVM就是按照這種思想，希望得到與每個類別的支持矢量距離最大的分類平面。

距離最優分類界面最近的這些訓練樣本稱為支持矢量。
最優分類界面完全由支持矢量決定，然而支持矢量的尋找比較困難。

SVM作為最優線性分類器的介紹如圖所示：

3. 多類問題

本章介紹如何將線性判別函數應用于多類問題。

3.1 處理方式

最常用的處理方式是one versus all的思想，每個類別與其他所有類別進行分類，在sklearn中用“ovr”表示，c類問題變為c個兩類問題，需要c個線性分類界面。

陰影為拒識區域，以下同理。

還有一種方式是one versus one的思想，分別對每兩個類別進行分類，在sklearn中用“ovo”表示，c類問題變為(c(c-1)/2)個兩類問題。

最后一種是采用票箱的方式，用c個線性判別函數處理c類問題，這種做法不存在拒識區域，在實際的數學推導過程中中，這c個票箱其實相當于(c(c-1)/2)個判別函數，因為是選擇c個票箱中的最大值，也就是需要每個兩個票箱進行相減計算，即c(c-1)/2$個判別函數，在排列組合中表示c個里取兩個。

對于感知器算法，可以用Kesler構造法進行設計，也可以稱作擴展的感知器算法。

總結

以上是生活随笔為你收集整理的哈尔滨工业大学计算机学院-模式识别-课程总结（三）-线性判别函数的全部內容，希望文章能夠幫你解決所遇到的問題。

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