跳轉到

02.1 感知器與線性分類#

本章導讀#

1957 年，Rosenblatt 把 Hebb 的學習規則改造成一個可以「從標籤學習」的演算法——感知器（Perceptron）。 它不只會記憶，還會根據對錯調整自己。更驚人的是，它有一個數學保證：只要答案存在，它必定找得到。

淺顯說明#

感知器的學習循環像考試訂正：

  1. 作答：用目前的權重 \(\mathbf{w}\) 預測 \(\hat y\) 。
  2. 對答案： \(\hat y\) 和正解 \(y\) 一樣嗎？
  3. 訂正：錯了才改——「預測太小就加權重，太大就減權重」，而且只動有影響的輸入。

重複直到全對。Rosenblatt 證明：如果資料可以用一條直線分開，這個循環保證收斂。

正規理論#

感知器模型#

輸入 \(\mathbf{x} \in \mathbb{R}^n\) ，標籤 \(y \in \{+1, -1\}\) ，權重 \(\mathbf{w}\) ，偏置 \(b\) ：

\[ \hat y = \mathrm{sgn}(\mathbf{w}^\top \mathbf{x} + b) \]

感知器學習演算法#

\[ \mathbf{w} \leftarrow \mathbf{w} + \eta\, y\, \mathbf{x}, \qquad b \leftarrow b + \eta\, y \qquad \text{（僅當 } \hat y \ne y \text{ 時）} \]

統一寫法（把 \(b\) 併入 \(\mathbf{w}\) ， \(\mathbf{x}\) 補一個 1）：

\[ \mathbf{w} \leftarrow \mathbf{w} + \eta\, y\,\mathbf{x} \quad \text{iff} \quad y(\mathbf{w}^\top\mathbf{x}) \le 0 \]

感知器收斂定理（Novikoff, 1962）#

定理：若存在單位向量 \(\mathbf{w}^*\) 與邊距 \(\gamma > 0\) 使得所有訓練資料滿足 \(y_i(\mathbf{w}^{*\top}\mathbf{x}_i) \ge \gamma\) （線性可分且有邊距）， 則感知器演算法的更新次數 \(k\) 滿足：

\[ k \;\le\; \frac{R^2}{\gamma^2}, \qquad R = \max_i \|\mathbf{x}_i\| \]

證明梗概：設 \(\mathbf{w}^{(k)}\) 為第 \(k\) 次更新後的權重（ \(\mathbf{w}^{(0)} = \mathbf{0}\) ）。

  1. 每次 update 用了被分錯的 \((\mathbf{x}_i, y_i)\) ：
\[ \mathbf{w}^{(k)\top}\mathbf{w}^* = \mathbf{w}^{(k-1)\top}\mathbf{w}^* + \eta\, y_i\, \mathbf{x}_i^\top \mathbf{w}^* \;\ge\; \mathbf{w}^{(k-1)\top}\mathbf{w}^* + \eta\gamma \;\Rightarrow\; \mathbf{w}^{(k)\top}\mathbf{w}^* \ge k\eta\gamma \]
  1. 但每次 update 只加一個大小有界的項：
\[ \|\mathbf{w}^{(k)}\|^2 = \|\mathbf{w}^{(k-1)}\|^2 + 2\eta\, y_i\,\mathbf{w}^{(k-1)\top}\mathbf{x}_i + \eta^2\|\mathbf{x}_i\|^2 \;\le\; \|\mathbf{w}^{(k-1)}\|^2 + \eta^2 R^2 \;\Rightarrow\; \|\mathbf{w}^{(k)}\|^2 \le k\eta^2 R^2 \]

（因為分錯時 \(y_i\,\mathbf{w}^{(k-1)\top}\mathbf{x}_i \le 0\) ，中間項非正。）

  1. 由 Cauchy–Schwarz：
\[ k\eta\gamma \;\le\; \mathbf{w}^{(k)\top}\mathbf{w}^* \;\le\; \|\mathbf{w}^{(k)}\|\,\|\mathbf{w}^*\| \;\le\; \sqrt{k}\,\eta R \]

兩邊除以 \(\sqrt{k}\,\eta\) ： \(\sqrt{k}\,\gamma \le R\) ，即 \(k \le R^2/\gamma^2\) 。 \(\blacksquare\)

意義：更新次數只依賴「邊距與資料範圍的比值」，與維度無關——資料越「分得開」，學得越快。

ADALINE：從「對錯」到「誤差大小」#

1960 年 Widrow 的 ADALINE 改用連續誤差：不只在分錯時更新，而是最小化平方誤差 \(L = (y - \mathbf{w}^\top\mathbf{x})^2\) 。這讓「學習」從離散的對錯，變成連續的優化——為梯度下降鋪路（下一節）。

簡易範例：兩點分類#

資料： \(\mathbf{x}_1 = (1,1), y_1 = +1\) ； \(\mathbf{x}_2 = (-1,-1), y_2 = -1\) 。 \(\eta = 1\) ， \(\mathbf{w}^{(0)} = \mathbf{0}\) 。

  1. \((\mathbf{x}_1, +1)\) ： \(\mathbf{w}^\top\mathbf{x}_1 = 0 \le 0\) ，分錯 → \(\mathbf{w}^{(1)} = (1,1)\) 。
  2. \((\mathbf{x}_2, -1)\) ： \(y\,\mathbf{w}^\top\mathbf{x} = (-1)\times(-2) = 2 > 0\) ，分對，不更新。
  3. 回到 \((\mathbf{x}_1)\) ： \(y\,\mathbf{w}^\top\mathbf{x} = 2 > 0\) ，分對。收斂： \(\mathbf{w} = (1,1), b = 0\) 。

驗證理論： \(R = \sqrt{2}\) ， \(\gamma = \mathbf{w}^{*\top}\mathbf{x}_i = \sqrt{2}\) ，上界 \(R^2/\gamma^2 = 1\) ——實際更新次數恰為 1。

歷史典故#

習題#

  1. 用感知器演算法分類 \(\{(2,1),+1\}, \{(-2,-1),-1\}\) ，從 \(\mathbf{w}^{(0)}=\mathbf{0}\) 開始，列出每步更新。
  2. 證明：對收斂定理中的 \(\mathbf{w}^{(k)}\) ，有 \(\cos\angle(\mathbf{w}^{(k)}, \mathbf{w}^*) \ge \sqrt{k}\,\gamma / (\sqrt{k} R)\) ，並討論其極限。
  3. 資料不是線性可分時，感知器會怎樣？（提示：更新次數無上界，權重會震盪。）這與 01.1 的 XOR 矛盾有何關係？

補充#

1. 數學推導證明#

證明（習題 2，修正版）：夾角餘弦的下界。

沿用收斂定理的記號（ \(\mathbf{w}^{(0)} = \mathbf{0}\) ， \(\|\mathbf{w}^*\| = 1\) ，每次更新用被分錯的樣本）：

\[ \mathbf{w}^{(k)\top}\mathbf{w}^* \ge k\eta\gamma, \qquad \|\mathbf{w}^{(k)}\|^2 \le k\eta^2 R^2 \]

故夾角餘弦

\[ \cos\angle(\mathbf{w}^{(k)}, \mathbf{w}^*) = \frac{\mathbf{w}^{(k)\top}\mathbf{w}^*}{\|\mathbf{w}^{(k)}\|\,\|\mathbf{w}^*\|} \ge \frac{k\eta\gamma}{\sqrt{k}\,\eta R} = \frac{\sqrt{k}\,\gamma}{R} \]

（註：習題原敘述分母多寫了一個 \(\sqrt{k}\) ，約掉後即得上式。）右端隨 \(\sqrt{k}\) 增長，但餘弦 \(\le 1\) ，故必有 \(\sqrt{k}\,\gamma/R \le 1\) ，即 \(k \le R^2/\gamma^2\) ——收斂定理的另一種看法：權重方向與理想分離方向的夾角越縮越小，直到分對為止。 \(\blacksquare\)

證明（習題 1 的手算）： 資料 \((2,1),+1\) 與 \((-2,-1),-1\) ， \(\eta = 1\) ， \(\mathbf{w}^{(0)} = \mathbf{0}\) ， \(b_0 = 0\) 。第一步在 \((2,1)\) 上 \(y\,\mathbf{w}^\top\mathbf{x} = 0 \le 0\) （分錯），更新得 \(\mathbf{w}^{(1)} = (2,1)\) ， \(b_1 = 1\) 。檢查： \(y_1(\mathbf{w}^{(1)\top}\mathbf{x}_1 + b_1) = 5 + 1 > 0\) ， \(y_2(\mathbf{w}^{(1)\top}\mathbf{x}_2 + b_1) = 5 - 1 > 0\) ——一次更新即收斂，與程式輸出 \(\mathbf{w} = (2,1)\) 、 \(b = 1\) 、 \(k = 1\) 一致。 \(\blacksquare\)

說明（習題 3）：線性不可分時。 若無 \(\mathbf{w}^*\) 使 \(y_i(\mathbf{w}^{*\top}\mathbf{x}_i) \ge \gamma > 0\) ，上述證明的第 1 步不成立， \(k \le R^2/\gamma^2\) 的上界消失——演算法在被分錯的樣本間循環更新、永不停止（如 XOR 四點：任何超平面必分錯至少一點，權重來回震盪）。這正是 01.1 節「單一 LTU 切不開 XOR」的演算法版本。

2. 簡易範例#

範例一：兩點分類的手算＋程式對照。 本章例子 \(\mathbf{x}_1 = (1,1),+1\) 、 \(\mathbf{x}_2 = (-1,-1),-1\) ：程式 _code/02.1-perceptron-training.py 輸出更新次數 \(k = 1\) 、上界 \(R^2/\gamma^2 = 1\) ——實際等於理論上界（資料沿對角線、邊距最大）。

範例二：較大資料集。 程式另做 15 個隨機可分點（真實分離向量 \((2,-1)\) ）：收斂更新 \(k = 12\) ，上界約 \(9086.8\) ——上界很鬆（最壞情形估計），實務遠快於理論保證；重點是保證存在：只要線性可分， \(k\) 有限，演算法必停。