Linear Discriminants 線性判別式

線性判別式公式
$$f(\mathbf{x};\mathbf{w})=w_1{x}^{(1)}+w_2{x}^{(2)}+?+w_d{x}^{(d)}+b=0$$

兩種表示方法


$w^{\prime }$是更加數學化的公式

我們所要做的，就是求$w$和$b$，獲得線性判別式。

Loss Function 損失函數

misclassification 誤分類

誤分類是一種錯誤
如果一個訓練樣本的標簽為𝑦 = +1，那么它的判別函數得分$f(x)$應該 > 0
如果一個訓練樣本的標簽為𝑦 = ?1，那么它的判別函數得分$f(x)$應該 < 0
因此，當出現 $yf(x)<0$，說明分類錯誤。

0-1 Loss/Error function 0-1損失函數

$$l(f(x),y)=\{\begin{array}{ll}0,& yf(x)>0\\ 1,& yf(x)\le 0\end{array}$$

The whole error整體誤差：用于判斷全部examples
$$\sum _{i=1}^{N}l(f(x_i),y_i)$$

0-1損失函數有兩個問題：

• 顯而易見，這是一個階躍函數，在0點具有不連續性，沒有很好的定義可以求導；
• 它不是凸的，這意味著當我們試圖用梯度下降算法來最小化整體損失，它是無法給出這個特定損失函數的最優解

所以我們建議做的或者最初的創造者，或者現在所謂的感知器所做的是，他們想出了這個零一損失函數的凸近似值——the hinge loss 鉸鏈損失函數

Hinge Loss Function 鉸鏈損失函數

Hinge Loss Function is a convex over-approximation of the 0-1 loss. 鉸鏈損失函數是 0-1 損失函數的凸過度近似。

$$l(f(x),y)=\{\begin{array}{ll}0,& yf(x)>1\\ 1?yf(x),& yf(x)\le 1\end{array}=\{\begin{array}{ll}0,& 1?yf(x)<0\\ 1?yf(x),& 1?yf(x)\ge 0\end{array}$$

OR
$$l(f(x),y)=\max (0,1?yf(x))$$

簡單的理解

$$\mathbf{l}(\mathbf{z})=\{\begin{array}{ll}0,& z>1\\ 1?z,& z\le 1\end{array}$$
我們所做的就是構建0-1損失函數的凸近似函數，它是凸的，我們也可以對它進行微分（求導）。

Optimization 優化

min?wL(X,Y;w)=∑i=1Nmax?{0,1?yif(xi;w)}\min_{\mathbf{w}} \; L(\mathbf{X}, \mathbf{Y}; \mathbf{w}) = \sum_{i=1}^{N} \max\{0,\, 1 - y_i f(x_i; \mathbf{w})\} wmin?L(X,Y;w)=i=1∑N?max{0,1?yi?f(xi?;w)}

在這個具體實例中，將4個節點代入模型公式 $f(\mathbf{x};\mathbf{w})=w_1{x}^{(1)}+w_2{x}^{(2)}+b=0$。我們已知道他們的標簽 $y_i$，由此得到每個節點的損失函數值 max?{0,1?yif(xi;w)}\max\{0,\, 1 - y_i f(x_i;\mathbf{w})\}max{0,1?yi?f(xi?;w)}。整個數據集，總體損失是 ∑i=14max?{0,1?yif(xi;w)}\sum_{i=1}^{4} \max\{0,\, 1 - y_i f(x_i; \mathbf{w})\}∑i=14?max{0,1?yi?f(xi?;w)}。
由此，我們采用梯度下降算法來求最小損失函數，這就是我們面對的優化問題。

所有的機器學習都可以表示為優化問題，一旦我們有了機器學習問題的表示方式（模型），我們表示了特征features，我們表示了判別式disccriminant，并且量化定義了什么是誤差。我們開始使用0-1損失函數，但因為它不可微，使用這個數據會導致復雜的后續處理過程。因此我們簡化了它，或者說以此為目的構建了一個復雜的鉸鏈損失過度近似。然后下一步，我們將以優化問題的形式進行問題訓練。這是整個機器學習和數據挖掘的一致主題。

現在我們將使用梯度下降算法進行優化。使用這個算法所求的便是這個模型，參數為向量$w$。

這里是有點難以理解的，這個圖的損失函數，分界點在$x=1$，不是0點。雖然實際上 $yf(x)=[0,1]$是正確分類了，本應該沒有損失值的，但這是近似損失函數，不是完全符合實際的，所以我們會計算它的損失值。所以當 $yf(x)<1$ 時候，我們會假定視為這是分類錯誤了。

算法

已知： 訓練樣本：{(xi,yi)∣i=1…N},yi∈{?1,+1}\{(x_i, y_i) \mid i = 1 \dots N\}, \quad y_i \in \{-1, +1\}{(xi?,yi?)∣i=1…N},yi?∈{?1,+1}
隨機初始化 $w^{(0)}$
循環直到收斂（Until Convergence）

• 對于 $i=1\dots N$：
  • 選擇樣本 $x_i$，其標簽為 $y_i$
  • 計算
    $$f(x_i)={\mathbf{w}}^{(k)T}\mathbf{x}+b$$
  • 如果 $y_{i}f(x_i)<1$，則使用梯度下降更新權重向量：
    $${\mathbf{w}}^{(k)}={\mathbf{w}}^{(k?1)}?\alpha ?l({\mathbf{w}}^{(k)})={\mathbf{w}}^{(k?1)}?\alpha (?y_i{x}_i)={\mathbf{w}}^{(k?1)}+\alpha y_i{x}_i$$

如果循環收斂一直是0，說明這是被完全分類正確的模型。
這個算法是在20世紀60年代開發1960s，是最早的神經網絡之一，被稱為perceptron 感知器。