機器學習基石筆記2：感知器學習演算法(PLA)

02-28

機器學習演算法做是非題（二元分類）

題目：銀行貸款問題，訓練數據是客戶的n維資料和貸款與否，求g

step 1：

$X = (x_1,x_2..x_d)$ ，代表訓練集每一個數據的特徵向量， $x_i$ 代表一個維度（欄位）

$w_i$ 表示 $x_i$ 維度的權重，則 $w_1x_1+w_2x_2...+w_dx_d$ 表示一個客戶的得分值，如果得分值大於閾值（t），則批准貸款，小於則拒絕。於是有如下模型：

$w_1x_1+w_2x_2...+w_dx_d >t \ Rightarrowsum_{i = 1}^{d}(w_ix_i) > t\ Rightarrowsum_{i = 1}^{d}(w_ix_i) -t> 0\ Rightarrowsum_{i = 1}^{d}(w_ix_i) +w_0x_0> 0 quad(w_0=-t,x_0=1)\ Rightarrowsum_{i = 0}^{d}(w_ix_i) > 0\ Rightarrow sum_{i = 0}^{d}(w_ix_i) = w^tx >0quad(w,x為d+1維向量)$

由於目標函數 $f(X) = Y ,Yin left{ +1,-1 ight}$ ，則令 $h(x) = sign(w^tx)$

註：符號函數 $f (x)= sign(x)$ 圖像為：

在二維 $R^2$ 空間上，h可以表示為 $h(x) = sign(w_0cdot1+w_1x_1+w_2x_2)$

step 2：

h(x)是+1還是-1，就是看括弧內的值是>0還是<0。便於邏輯清晰的理解，我們將x1=x，x2=y帶入括弧內，則為 $w_0 +w_1x+w_2y$ ，進一步簡化，令 $ax+by+c =0$ ，則為二維平面上xy坐標系內的一條直線方程。（在n維歐幾里得空間中為超平面）我們知道直線下方的點帶入直線方程結果小於0，上方的點大於0，由於訓練集已出（即訓練集的點在平面上已固定），所以學習的結果是找一條直線（即找到 a、b、c）使得所有訓練集的點正確排在這條直線的上方或下方。如下圖所示：

此圖其實代表了一個二維平面上的訓練樣本點的示例，劃分線是可能的直線。

step 3：

用 $vec {w_0}$ 作為初始直線，不斷迭代使得直線一次比一次更好( $vec {w_0}$ 是向量不是上面向量的分量！此處的0是迭代次數t=0，不是分量下標0)

$vec w_t$ = $egin{pmatrix} w_0 \ w_1 \ w_2 end{pmatrix}$ $vec x$ = $egin{pmatrix} 1 \ x_1 \ x_2 end{pmatrix}$

迭代次數 t = 0,1,2...

假設 $vec w_0$ =(0,0,0)，代入訓練集，找到一個 $(x_{n(t)},y_{n(t)})$ 使得 $sign(vec w_t^Tvec x_{n(t)}) e y_{n(t)}$ ，然後開始修正 $vec w_0$ ，（註：此處用到向量數量積的幾何意義，當w與x的夾角小於90度，則數量積為正，則sign值>0；當w與x的夾角大於90度，則數量積為負，則sign值<0）

即：角度>90 則修正為<90；反之亦然。 $vec w_{t=1} leftarrow vec w_t +y_{n(t)}vec x_{n(t)}$
直到沒有錯誤為止

# todo 為何w向量的法向量是分割直線？幾何很直觀，數學如何證明？忘記了...(補充：技法筆記1的內容里有證明)

總結：

從代數轉到幾何求解，很巧妙
訓練集線性可分才有解

step 4：

# todo 在線性可分的情況下，證明修正次數會有上界

step 5：

對於線性不可分的訓練集的處理

找一條犯錯誤最小的劃分線，一直跑演算法，每次保存最少錯誤的直線，直到指定的次數為止

題圖：2017年11月2日00:01:47

上一篇《1 ML基礎概念》

下一篇《3 機器學習可行性論證》