感知機（PLA）

02-27

前記：準備動筆之前看了下之前寫了筆記（PLA和線性回歸），寫的時候自我感覺良好，可是現在一看，這寫的神馬玩意啊這是...本篇開始，結合《統計學習方法》《機器學習》等書，來論述總結機器學習中的N個重要模型。

廢話少說，直接上步驟：

n維空間的超平面 $S_0$ ： $vec w^Tvec x+b=0$
任一點 $(x_0,y_0)$ 到 $S_0$ 的距離： $frac{1}{|w|}|vec wx_0+b|$
代入 $y_0$ 去掉絕對值： $-frac{1}{|w|}y_0(vec wx_0+b)$
誤分類點距離S0的總距離： $sum_{x_iin M}^{}{-frac{1}{|w|}y_i(vec wx_i+b)}$
簡化上述公式： $minL(w,b)=-sum_{x_iin M}^{}{y_i(vec wx_i+b)}$
分量梯度： $abla _wL(w,b)=-sum_{x_iin M}^{}y_ix_i$ ， $abla _bL(w,b)=-sum_{x_iin M}^{}y_i$
找誤分類點並更新： $w_{t+1}leftarrow w_t+eta y_ix_i$ ， $b_{t+1}leftarrow b_t+eta y_i$ （隨機梯度下降）
直到沒有誤分類點

演算法直觀上的解釋：當一個點被誤分類，即位於超平面的錯誤一側時，調整w和b的值，使得超平面向該點移動，減少超平面與該點的距離，直到超平面越過該點，該點即被正確分類。

先問幾個問題：

回答：

對偶形式

我們把對偶形式先公式化的描述出來，具體深層次的理解和推導請見svm篇。

上面我們已經推導出有： $w_{t+1}leftarrow w_t+eta y_ix_i$ ， $b_{t+1}leftarrow b_t+eta y_i$

在所有的w和b的更新中，假設 $x_i$ 點貢獻了 $n_i$ 次，令 $alpha_i=n_ieta$ ，則w，b可表示為： $w=sum_{i=1}^{N}{alpha_iy_ix_i}\ b=sum_{i=1}^{N}{alpha_iy_i}$

所以，感知機的模型又可以表示成： $f(x)=sign(sum_{j=1}^{N}{alpha_jy_jx_jcdot x+b})$ ，輸出 $alpha$ 和b

初始化 $alphaleftarrow 0,bleftarrow 0$
選取數據 $(x_i,y_i)$
如果 $y_i(sum_{j=1}^{N}{alpha_jy_jx_jcdot x+b})leq 0$ ，更新 $alpha_i leftarrow alpha_i+eta,bleftarrow b+eta$
轉到2直到沒有錯誤

對偶形式的特點是可以預先計算出實例間的內積並以矩陣（GRAM矩陣）形式存儲。

既然都看到這兒了，少年點個贊可好？感謝！

done 2017年11月20日16:26:31