Perceptron
Intro
- 深度學習基礎單元（神經元）
- Linear classifier
Perceptron Learning Algorithm
基本定義
- 資料 : $ (x, y) \Rightarrow (x_1, x_2) $
- 方程式 : $ w_0c + w_1x_1 + w_2x_2 = (w_0, w_1, w_2) \cdot (c, x_1, x_2) = 0 $
- 資料點位於直線右側時, 等式結果為正, 反之則為負
基本算法 : 修正錯誤
- 遇到錯誤的點時將往x方向的法向量加入w, 迫使資料點被放置於直線的另一側
實作方式
- 指定迭代次數, 若參數可正確分類則return
處理高維度資料
- 訂立一個 threshold, 取內積結果與 threshold 相差的正負值
關於迭代次數與參數正確性成正相關的證明
當 $\mathbf w^{(t)}$ 對樣本 $(x_k,y_k)$ 分類錯誤時，PLA會做以下更新 :
$$ \mathbf w^{(t+1)} = \mathbf w^{(t)} + y_k x_k $$
假設現在是第t次 :
$$ \begin{aligned} \mathbf{w}^{(t+1)} \cdot \mathbf{w}^{*} &= (\mathbf{w}^{(t)} + y_k x_k) \cdot \mathbf{w}^{*} \\ &= \mathbf{w}^{(t)} \cdot \mathbf{w}^{*} + y_k (x_k \cdot \mathbf{w}^{*}) \end{aligned} $$
線性可分 $\Rightarrow y_k (x_k!\cdot \mathbf w^{*})\ge\gamma$
$$ \mathbf w^{(t+1)}!\cdot \mathbf w^{*} \ge \mathbf w^{(t)}!\cdot \mathbf w^{*} + \gamma $$
接著計算更新之後的Norm :
$$ \begin{aligned} |\mathbf w^{(t+1)}|^2 &= |\mathbf w^{(t)} + y_k x_k|^2\\ &= |\mathbf w^{(t)}|^2 + 2y_k\mathbf w^{(t)}!\cdot x_k + |x_k|^2\\ &\le |\mathbf w^{(t)}|^2 + 0 + R^2 \quad(\because y_k\mathbf w^{(t)}!\cdot x_k\le0)\\ &= |\mathbf w^{(t)}|^2 + R^2 \end{aligned} $$
M次更新後可得 :
$$ |\mathbf w^{(M)}|^2 \le M R^2 $$
並且可以分別得到dot至少成長 :
$$ \mathbf w^{(M)}!\cdot \mathbf w^{*}\ge M \gamma $$
以及norm至多成長 :
$$ |\mathbf w^{(M)}|\le R\sqrt{M} $$
因此可以得到Cosine的下界 :
$$ \begin{aligned} \cos\theta_M &= \frac{\mathbf w^{(M)}!\cdot \mathbf w^{*}} {|\mathbf w^{(M)}||\mathbf w^{*}|}\\ &\ge \frac{M\gamma}{(R\sqrt{M})|\mathbf w^{*}|} = \frac{\sqrt{M}\gamma}{R|\mathbf w^{*}|} \end{aligned} $$
其中右式為單調增加
雜訊容忍
- 加總錯誤次數
- Minimize
不過由於需要minimize的為indicator, 無法解開(NP-hard), 可改進此演算法
Pocket Algorithm
- 更新模式與PLA相同
- 若新的權重優於原版才更新為新的 $w_t$
Linear Regression
Intro
- 與Perceptron很類似, 不過不是取sign, 是取內積作為函數的output
- 以擬合資料走向為目標, 想辦法最小化殘差量
Error measure
使用的誤差平方
Algorithm
先定義資料集 ${(\mathbf x_i, y_i)}_{i=1}^n,\quad \mathbf x_i\in\mathbb{R}^p$ :
$$ X = \begin{bmatrix} 1 & x_{11} & x_{12} & \cdots & x_{1p} \\ 1 & x_{21} & x_{22} & \cdots & x_{2p} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_{n1} & x_{n2} & \cdots & x_{np} \end{bmatrix} ,\quad \boldsymbol\beta = \begin{bmatrix} \beta_0 \\ \beta_1 \\ \vdots \\ \beta_p \end{bmatrix} ,\quad \mathbf y = \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix} $$
模型就會是 :
$$ \hat{\mathbf y}=X,\boldsymbol\beta $$
接著定義Loss:
$$ J(\boldsymbol\beta) = |\mathbf y - X\boldsymbol\beta|_2^2 = (\mathbf y - X\boldsymbol\beta)^\top(\mathbf y - X\boldsymbol\beta) $$
接著求微分，然後令他為0 (求解正規方程) :
$$ \frac{\partial J}{\partial \boldsymbol\beta} = -2X^\top(\mathbf y - X\boldsymbol\beta) ;\overset{!}{=} \mathbf0 \quad\Longrightarrow\quad X^\top X \boldsymbol\beta = X^\top \mathbf y $$
假設 $X^\top X$ 可逆(大部分情況都是可逆) :
$$ \boldsymbol\beta = (X^\top X)^{-1} X^\top \mathbf y $$
Applications
線性回歸也可套用到二元分類, 利用公式去推算初始的線, 加快算法的收斂速度
