上次我們完成了感知器的介紹，感知器也有他相對應的學習演算法：perceptron learning algorithm (PLA)。

不過我們今天沒有要講 PLA，我們來講講感知器的缺點。

感知器這個模型有很多的缺點，但是因為他是最簡單的模型，我們就放他一馬（？）。

他的缺點有：

  1. 只能處理線性可分（linear-separable）的資料
  2. 只要能分，大家都是好的分類器（黑貓白貓，能抓老鼠的就是好貓？）

線性可分

我們一項一項來講，什麼是線性可分（linear-separable）？

像這樣是線性可分的，可以用一條直線把不同的點分開。

像這樣根本找不到一條線可以將點分開的，不是線性可分。

差一點點也不行！很尷尬，差一點就可以變成線性可分的了！但是他就不是！

所以整體說起來，感知器在使用上限制頗大。

好的分類器？

接下來，什麼叫作一個好的分類器？

以上三張圖，大家有沒有認為哪一張分的最好？

每個人可能有不同的答案，但是有沒有覺得第一張是比較好的分類器？

為什麼？

資料點都多多少少會有一些誤差，而資料我們都假設他比較相似的會在一起，所以當新的資料點出現的時候，我們通常預期他會在舊的資料點附近。所以說，如果線可以離資料點遠一點比較好，這樣的話就不會不小心分錯。

其實你心裡想的是這個樣子的：

我們可以定一個東西叫作 margin，他就是線到最近的資料點的距離，然後希望 margin 可以越大越好。

Maximum-margin classifier

所以我們希望的是一個讓 margin 最大化的分類器，也就是 Maximum-margin classifier。

那麼他要怎麼以數學表達呢？

注意：以下數學高能！！

$$
\begin{align}
\mathop{\arg\max}{\mathbf{w}, b} &\ \ \ \
\text{margin}(\mathbf{w}, b) \\
\text{subject to} &\ \ \ \
\text{classify } (\mathbf{x_n}, y_n) \text{ correctly} \\
\text{ } &\ \ \ \
\text{margin}(\mathbf{w}, b) = \mathop{\min}{i = 1 \dots n} \text{distance}(\mathbf{x_n}, \mathbf{w}, b)
\end{align}
$$

總的來說，你希望 margin 越大越好，那就是我們的最佳化目標，但是會帶有一些條件，像是我們需要將點都分對，以及 margin 的定義是線到各個點的距離最短的那個。

上方式子中的 argmax 指的是改變某些變數（$\mathbf{w}, b$），讓後方的式子的值最大。subject to 則是限制式，也就是必須要滿足的條件。

但是這樣的式子無法直接套用數學方法計算，所以我們要進一步將式子公式化。

進一步公式化

注意：以下極度數學高能！！

談到距離的話，我們要先講講高中數學裡的點到線距離公式：

$$
\text{distance}(\mathbf{x_i}, \mathbf{w}, b) = \frac{|ax_i + by_i + c|}{\sqrt{a^2 + b^2}}
$$

不記得的話，回去翻翻課本或是 google 一下。可以觀察一下，會發現分子是線的權重向量跟資料點向量的相乘再相加，再加上一個常數項。相乘再相加的動作其實就是兩個向量的 內積運算。分母部份是線的權重向量的 長度。我們可以把這個二維的公式擴充到 n 維，就變成了：

$$
\text{distance}(\mathbf{x_i}, \mathbf{w}, b) = \frac{|\mathbf{w}^T\mathbf{x_i} + b|}{\left\lVert \mathbf{w} \right\rVert}
$$

是不是看起來漂亮許多？

接著，如果要把資料點分對，那就表示說，將資料點 $\mathbf{x_i}$ 代入模型中算出來的值會跟真實答案 $y_i$ 在線的同側，也就是正負號是相同的。利用這點，我們發現如果將資料點代入模型中算出來的值 $(\mathbf{w}^T\mathbf{x_i} + b)$ 與真實答案 $y_i$ 相乘的話，必定為正，所以 $y_i (\mathbf{w}^T\mathbf{x_i} + b) \gt 0$。

整個問題會被進一步變成這樣：

$$
\begin{align}
\mathop{\arg\max}{\mathbf{w}, b} &\ \ \ \
\text{margin}(\mathbf{w}, b) \\
\text{subject to} &\ \ \ \
\forall i, y_i (\mathbf{w}^T\mathbf{x_i} + b) \gt 0 \\
\text{ } &\ \ \ \
\text{margin}(\mathbf{w}, b) = \mathop{\min}{i = 1 \dots n} \frac{|\mathbf{w}^T\mathbf{x_i} + b|}{\left\lVert \mathbf{w} \right\rVert}
\end{align}
$$

$|\mathbf{w}^T\mathbf{x_i} + b|$ 的絕對值部份不是那麼好處理，我們可以把他替換成 $y_i (\mathbf{w}^T\mathbf{x_i} + b)$，反正他一定恆正。

$$
\begin{align}
\mathop{\arg\max}{\mathbf{w}, b} &\ \ \ \
\text{margin}(\mathbf{w}, b) \\
\text{subject to} &\ \ \ \
\forall i, y_i (\mathbf{w}^T\mathbf{x_i} + b) \gt 0 \\
\text{ } &\ \ \ \
\text{margin}(\mathbf{w}, b) = \mathop{\min}{i = 1 \dots n} \frac{y_i (\mathbf{w}^T\mathbf{x_i} + b)}{\left\lVert \mathbf{w} \right\rVert}
\end{align}
$$

Scalling trick

對於以下的部份，我們可以進一步簡化。

$$
\text{margin}(\mathbf{w}, b) = \mathop{\min}_{i = 1 \dots n} \frac{y_i (\mathbf{w}^T\mathbf{x_i} + b)}{\left\lVert \mathbf{w} \right\rVert}
$$

對於一條直線 $\mathbf{w}^T\mathbf{x_i} + b = 0$ 來說，縮放 c 倍基本上是沒有影響的 $c\mathbf{w}^T\mathbf{x_i} + cb = 0$。所以我們就乾脆將這個值縮放成剛好是 1，像下面這樣：

$$
\mathop{\min}_{i = 1 \dots n} y_i (\mathbf{w}^T\mathbf{x_i} + b) = 1
$$

這樣有什麼好處呢？如果你把他代回去我們的最佳化目標的話，margin 的大小是不是變成這樣了呢？

$$
\text{margin}(\mathbf{w}, b) = \frac{1}{\left\lVert \mathbf{w} \right\rVert}
$$

而且我們也省掉了 $y_i (\mathbf{w}^T\mathbf{x_i} + b) \gt 0$ 這個限制，畢竟最小的資料點計算出來至少有 1。整個問題就變成了這樣：

$$
\begin{align}
\mathop{\arg\max} _{\mathbf{w}, b} &\ \ \ \
\frac{1}{\left\lVert \mathbf{w} \right\rVert} \\
\text{subject to} &\ \ \ \
\mathop{\min} _{i = 1 \dots n} y_i (\mathbf{w}^T \mathbf{x_i} + b) = 1
\end{align}
$$

min 還是個不好處理的運算，我們與其求某個資料點代入最小值會是 1，我們不如放寬限制，變成所有資料點帶入公式都會 $\ge 1$。

$$
\mathop{\min}_{i = 1 \dots n} y_i (\mathbf{w}^T\mathbf{x_i} + b) = 1
\Rightarrow
y_i (\mathbf{w}^T\mathbf{x_i} + b) \ge 1
$$

最後，數學家都會有點潔癖，將問題變成他們喜歡的形式。像是求倒數的最大值，不如我們求最小值。要求 $\mathbf{w}$ 的長度太麻煩了，我們把長度中的根號拿掉。再加個二分之一上去。

$$
\begin{align}
\mathop{\arg\min}_{\mathbf{w}, b} &\ \ \ \
\frac{1}{2} \mathbf{w}^T\mathbf{w} \\
\text{subject to} &\ \ \ \
\forall i, y_i (\mathbf{w}^T\mathbf{x_i} + b) \ge 1
\end{align}
$$

maximum-margin classifier 的最終形式就完成了！這也是支持向量機（support vector machine）的雛型。