標籤：

EdX-Columbia機器學習課第8講筆記：線性分類器與感知機

05-11

線性分類器

這裡我們只討論二元分類的情況，即 $mathcal{Y} in {-1, +1}$ 或 $mathcal{Y} in {0, 1}$ 。在這種情況下，假設我們使用貝葉斯分類器，而且對某個新數據判定其類別為1，則肯定有

$egin{aligned}&p(x|y=1)P(y=1) > p(x|y=0)P(y=0) \Rightarrow & lnfrac{p(x|y=1)P(y=1)}{p(x|y=0)P(y=0)} > 0end{aligned}$

假設對 $y=0 { m or} 1$ 其期望密度共享同一個協方差矩陣，即 $p(x|y) = N(x|mu, Sigma)$ ，那麼代入前一講的概率密度函數，有

$lnfrac{p(x|y=1)P(y=1)}{p(x|y=0)P(y=0)} = ln frac{pi_1}{pi_0} - frac{1}{2} (mu_1 + mu_0)^TSigma^{-1}(mu_1 - mu_0) + x^TSigma^{-1}(mu_1 = mu_0)$

其中不帶 $x$ 的是一個常數項，可以寫作 $w_0$ ， $x^T$ 的係數可以寫作 $w$ 。得到的這個線性式子也稱作線性判別分析（LDA）

因此該貝葉斯分類器的決策規律可以寫為一個線性函數，即

$f(x) = { m sign}(x^Tw + w_0)$

如果我們放寬之前的假設（即兩個類別各自是高斯分布，且共享協方差矩陣），可以得到一個更廣義的（二元）線性分類器

$f(x) = { m sign}(x^Tw + w_0)$

其中 $w in mathbb{R}^d, w_0 in mathbb{R}$ 。這個分類器要求樣本 $x$ 是（大致）線性可分的。 $mathbb{R}^d$ 的兩個子集 $A,B$ 被稱為是線性可分的，如果滿足以下條件

$x^Tw + w_0egin{cases}>0 & { m if }x in A \<0 & { m if }x in Bend{cases}$

這裡 $(w,w_0)$ 定義了一個仿射超平面

為了理解仿射超平面的概念，先看一下超平面的概念。 $mathbb{R}^d$ 中的超平面是其 $d-1$ 維的線性子空間。作為線性子空間，超平面肯定會包含原點。任意超平面 $H$ 可以用向量 $w$ 來表示，即

$H = {x in mathbb{R}^d | x^Tw = 0}$

從幾何上講，在最簡單的情況下（二維空間），對於給定的向量 $oldsymbol{w}$ ，其超平面是有所有與其正交的點（從該點到原點能連出一個向量，這個向量與 $w$ 正交）所組成的一條過原點的直線 $ax$

對於任一向量 $oldsymbol{x}$ ，可以計算它與 $oldsymbol{w}$ 的夾角。可知三角形的另外一邊為 $oldsymbol{x} - oldsymbol{w}$ ，那麼由余弦定理，有

$egin{aligned}|!|x-w|!|^2 &= |!|x|!|^2 + |!|w|!|^2 - 2|!|x|!||!|w|!|cos heta \(x-w)^T(x-w) &= |!|x|!|^2 + |!|w|!|^2 - 2|!|x|!||!|w|!|cos heta \|!|x|!| - x^Tw - w^Tx + |!|x|!|^2 &= |!|x|!|^2 + |!|w|!|^2 - 2|!|x|!||!|w|!|cos heta \2x^Tw &= 2|!|x|!||!|w|!|cos heta \ herefore |!|x|!||cos heta| &= frac{|x^Tw|}{|!|w|!|}end{aligned}$

即從 $x$ 到 $w$ 的距離是 $|x^Tw|$ 。而且只有當 $heta in (-frac{pi}{2}, frac{pi}{2})$ 時，才有 $cos heta > 0$ 。因此 $x$ 在 $w$ 的哪邊是由其夾角餘弦值決定，即有

${ m sign}(cos heta) = { m sign}(x^Tw)$

將超平面平移標量 $w_0$ ，就得到了仿射超平面，決策平面也變成了 $H=x^Tw+w_0 = 0$ 。當 $w_0>0$ 時，將超平面往逆向 $w$ 的方向移動；當 $w_0<0$ 時，將超平面往向著 $w$ 的方向移動。

與線性回歸類似，也可以通過將特徵組合成高維特徵的方法，將低維的線性不可分樣本集變為高維線性可分樣本集。另外，如果對兩個類別，其期望密度各自對應一個協方差矩陣，即 $p(x|y) = N(x|mu_y, Sigma_y)$ ，那麼與前面不同的是，有

$lnfrac{p(x|y=1)P(y=1)}{p(x|y=0)P(y=0)} = C + x^T(Sigma_1^{-1}mu_1 - Sigma_0^{-1}mu_0) + x^Tleft(frac{Sigma_0^{-1} - Sigma_1^{-1}}{2} ight)x$

這裡第三項是一個關於 $x$ 的二次項，因此也稱作二次判別分析（不過權重是線性的）

${-1, +1}$ 上的最小二乘

如何對諸如

$f(x) = { m sign}(x^Tw+w_0)$

這樣形式的問題學到一個更通用的分類器？一個簡單的方法是把分類問題看做是回歸問題，分四步

令 $y=(y_1, ldots, y_n)^T$ ，其中 $y_i in {-1,+1}$ 是 $x_i$ 的類別標籤
往 $x_i$ 中加入一個全為1的特徵，構造矩陣 $X=[x_1, ldots, x_n]^T$
使用最小二乘法學出權重向量 $w = (X^TX)^{-1}X^Ty$
對新的點 $x_0$ ，其標籤標記為 $y_0 = { m sign}(x_0^Tw)$

當然可以使用 $ell_p$ 回歸來代替最小二乘，進行正則化或者特徵選擇

這種方法最大的問題是容易受到離群點的影響，而且影響會很大

感知機

對線性分類器

$y = f(x) = { m sign}(x^Tw)$

感知機演算法試圖最小化的損失函數為

$mathcal{L} = -sum_{i=1}^n(y_i cdot x_i^Tw)1{y_i ot= { m sign}(x_i^Tw)}$

因為對 $y in {-1, +1}$ ，有

$egin{aligned}y_i cdot x_i^Twegin{cases}>0 & { m if }y_i = { m sign}(x_i^Tw) \<0 & { m if }y_i ot= { m sign}(x_i^Tw)end{cases}end{aligned}$

通過最小化 $mathcal{L}$ ，我們試著總去預測出正確的標籤

但是 $abla_w mathcal{L} = 0$ 對 $w$ 沒有解析解，所以只能迭代求解。不過 $abla_wmathcal{L}$ 指出了 $w$ 沿著哪個方向可以增大 $mathcal{L}$ 。因此，對足夠小的 $eta$ ，如果按照

$w leftarrow w - eta abla_w mathcal{L}$

來更新 $w$ ，則有 $mathcal{L}(w) < mathcal{L}(w)$ ，即我們得到了更好的 $w$

這種方法稱為梯度下降法，感知機用了隨機梯度下降的方法進行學習，步驟為

1. 初始化權重向量 $w^{(1)} = 0$

2. 對 $t=1,2,ldots$

a. 找到所有錯分的樣本，即所有 $(x_i, y_i) in mathcal{D}$ 使得 $y_i ot= { m sign}(x_i^Tw^{(t)})$

b. 如果這樣的樣本存在，隨機選擇一個 $(x_i, y_i)$ 進行更新

$w^{(t+1)} = w^{(t)} + eta y_ix_i$

否則返回 $w^{(t)}$ （即此時所有樣本均已被正確分類）

感知機的缺點有兩點

對於線性可分的情況，演算法在找到滿足條件的 $w$ 以後就會停止，不會找到最優分類器
對於線性不可分的情況，演算法不會收斂

推薦閱讀：

※Cousera deeplearning.ai筆記 — 淺層神經網路（Shallow neural network）
※比賽心路駕駛行為預測駕駛風險（二）
※有關NLP的比賽
※機器學習基本套路
※機器學習-線性回歸

TAG:機器學習 |