Machine Learning : Perceptron, Linear Regression

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#

線性回歸也可套用到二元分類, 利用公式去推算初始的線, 加快算法的收斂速度

Blog

Pwning my life

Machine Learning : Perceptron, Linear Regression

Perceptron#

Intro#

Perceptron Learning Algorithm#

基本定義#

基本算法 : 修正錯誤#

實作方式#

處理高維度資料#

關於迭代次數與參數正確性成正相關的證明#

雜訊容忍#

Pocket Algorithm#

Linear Regression#

Intro#

Error measure#

Algorithm#

Applications#

Table of Contents