#介绍
感知器算法由Rosenblatt于1957年提出，它是一种监督式学习算法。它是一种相当好的二分类在线算法。比如说Y有d个特征:
X = x 1 , x 2 , x 3 , . . . , x d X = x_1,x_2,x_3,...,x_d X=x1,x2,x3,...,xd
如果给这个d个特征每个加上一个权值，并进行线性组合。那么就可以得到下式：
y = ∑ i = 1 d ( w i x i + b i ) y=\sum_{i=1}^d(w_ix_i+b_i) y=i=1∑d(wixi+bi)
这里求和出的结果就是用这些特征计算出来的总分，如果我们假定y>threshold时，最终结果为1。否则y <threshold时，最终结果为-1。则最终的表达式可以表示为：
h ( x ) = s i g n ( ( ∑ i = 1 d ( w i x i ) ) − t h r e s h o l d ) h(x)=sign((\sum_{i=1}^d(w_ix_i))-threshold) h(x)=sign((i=1∑d(wixi))−threshold)
这个公式称为perceptron hypothesis。
（1）可以对上面的公式进行简化。其中可以把threshold作为w0,x0作为1，这样子的话就可以把上面的公式简化为：
h ( x ) = s i g n ( ( ∑ i = 1 d ( w i x i ) ) − t h r e s h o l d ) h(x)=sign((\sum_{i=1}^d(w_ix_i))-threshold) h(x)=sign((∑i=1d(wixi))−threshold)
= s i g n ( ( ∑ i = 0 d ( w i x i ) ) + ( − t h r e s h o l d ) ⏟ w 0 ∗ ( + 1 ) ⏟ x 0 \quad\quad\;=sign((\sum_{i=0}^d(w_ix_i))+\underbrace{(-threshold)}_{w_0}*\underbrace{(+1)}_{x_0} =sign((∑i=0d(wixi))+w0 (−threshold)∗x0 (+1)
= s i g n ( ∑ i = 0 d ( w i x i ) ) \quad\quad\;=sign(\sum_{i=0}^d(w_ix_i)) =sign(∑i=0d(wixi))
= s i g n ( w T x ) \quad\quad\;=sign(w^Tx) =sign(wTx)
（2）如果把上面的特征（二维）对应到空间中，则h(x)就是空间中的直线。如果是在多维空间中，则h(x)对应超平面。
#PLA算法（perceptron learning algorithm）
##（1）伪代码描述
##（2）基本思想
我们假定一个初始的w向量来对数据进行判定，一直到遇到一个判断错误的数据，这个时候，我们就是使用这个判断错误的数据，对w进行修改。
**如果 w x < 0 wx<0 wx<0, y > 0 y>0 y>0，w(k+1) = w(k) + pxk
**如果 w x > 0 wx>0 wx>0, y < 0 y<0 y<0，w(k+1) = w(k) - pxk
**如果 y w x > 0 ywx>0 ywx>0，w(k+1) = w(k)
##（3）向量描述
这里我们可以知道w，x在空间中是两个向量，对于第一种情况， w x < 0 wx<0 wx<0，就相当于两个向量夹角大于90度:
此时，W+X会把新的W向X靠近，这样的话就达到了学习的效果。
同理对于第二种情况， w x > 0 wx>0 wx>0，就相当于两个向量夹角小于90度:
#算法验证
##（1）验证算法是会收敛的
当出现错误时：
∣ ∣ w t + 1 ∣ ∣ 2 = ∣ ∣ w t + y t x t ∣ ∣ 2 = ∣ ∣ w t ∣ ∣ 2 + 2 y t w t T x t + ∣ ∣ y t x t ∣ ∣ 2 ||w_{t+1}||^2=||w_t + y_tx_t||^2=||w_t||^2 + 2y_tw_t^Tx_t + ||y_tx_t||^2 ∣∣wt+1∣∣2=∣∣wt+ytxt∣∣2=∣∣wt∣∣2+2ytwtTxt+∣∣ytxt∣∣2
≤ ∣ ∣ w t ∣ ∣ 2 + ∣ ∣ y t x t ∣ ∣ 2 ≤ ∣ ∣ w t ∣ ∣ 2 + m a x ∣ ∣ y n x n ∣ ∣ 2 ≤ ∣ ∣ w 0 ∣ ∣ 2 + T m a x ∣ ∣ y n x n ∣ ∣ 2 = T m a x ∣ ∣ x n ∣ ∣ 2 \leq||w_t||^2 + ||y_tx_t||^2\leq||w_t||^2 + max||y_nx_n||^2\leq||w_0||^2 + Tmax||y_nx_n||^2=Tmax||x_n||^2 ≤∣∣wt∣∣2+∣∣ytxt∣∣2≤∣∣wt∣∣2+max∣∣ynxn∣∣2≤∣∣w0∣∣2+Tmax∣∣ynxn∣∣2=Tmax∣∣xn∣∣2
由上面的公式可知： ∣ ∣ w t + 1 ∣ ∣ 2 ∣ ∣ w t ∣ ∣ 2 ≤ 1 + m a x ∣ ∣ x n ∣ ∣ 2 ∣ ∣ w t ∣ ∣ 2 \frac{||w_{t+1}||^2}{||w_t||^2} \leq 1 + \frac{max||x_n||^2}{||w_t||^2} ∣∣wt∣∣2∣∣wt+1∣∣2≤1+∣∣wt∣∣2max∣∣xn∣∣2,其中，另 R 2 = m a x ∣ ∣ x n ∣ ∣ 2 R^2=max||x_n||^2 R2=max∣∣xn∣∣2,所以，上面的式子可以变为:
∣ ∣ w t + 1 ∣ ∣ 2 ∣ ∣ w t ∣ ∣ 2 ≤ 1 + R 2 ∣ ∣ w t ∣ ∣ 2 \frac{||w_{t+1}||^2}{||w_t||^2} \leq 1 + \frac{R^2}{||w_t||^2} ∣∣wt∣∣2∣∣wt+1∣∣2≤1+∣∣wt∣∣2R2
因此，可以知道算法最终是收敛的。算法学习是可以终止的。
##（2）求算法学习步数
因为
w f T ∗ w t + 1 = w f T ( w t + y t x t ) = w f T w t + y t w f T x t ≥ w f T w t + m i n y n w f T x n ≥ . . . ≥ w f T w 0 + T m i n ( y n w f T x n ) = T m i n y n w f T x n w_f^T*w_{t+1}=w_f^T(w_t +y_tx_t)=w_f^Tw_t + y_tw_f^Tx_t\geq w_f^Tw_t +miny_nw_f^Tx_n\geq...\geq w_f^Tw_0 + Tmin(y_nw_f^Tx_n)=Tminy_nw_f^Tx_n wfT∗wt+1=wfT(wt+ytxt)=wfTwt+ytwfTxt≥wfTwt+minynwfTxn≥...≥wfTw0+Tmin(ynwfTxn)=TminynwfTxn
所以：
w f T w t ∣ ∣ w f ∣ ∣ ∣ ∣ w t ∣ ∣ ≥ T m i n y n w f T x n ∣ ∣ w f ∣ ∣ T m a x ∣ ∣ x n ∣ ∣ 2 \frac{w_f^Tw_t}{||w_f||||w_t||}\geq\frac{Tminy_nw_f^Tx_n}{||w_f||\sqrt{Tmax||x_n||^2}} ∣∣wf∣∣∣∣wt∣∣wfTwt≥∣∣wf∣∣Tmax∣∣xn∣∣2 TminynwfTxn
又因为 w f T w t ∣ ∣ w f ∣ ∣ ∣ ∣ w t ∣ ∣ ≤ 1 \frac{w_f^Tw_t}{||w_f||||w_t||} \leq1 ∣∣wf∣∣∣∣wt∣∣wfTwt≤1
又另： ρ = m i n y n w f T ∣ ∣ w f ∣ ∣ x n \rho=miny_n\frac{w_f^T}{||w_f||}x_n ρ=minyn∣∣wf∣∣wfTxn
计算可得：
T ≤ R 2 ρ 2 T\leq\frac{R^2}{\rho^2} T≤ρ2R2
如果大家对相关话题感兴趣的话，可以关注yiyele-xxq(程序猿技术交流)公众号。
