感知机分类器 理论推导

感知机其实也是一个线性分类模型，但是同逻辑回归不同，主要是损失函数建立的思路同时不从概率角度出发。

（一）假设函数

数据集(样本)：
X ⊑ R N f ( x ; ω , b ) = ω 1 x 1 + ω 2 x 2 + . . . + ω N x N + b X\sqsubseteq\mathbb{R}^N\\f(\boldsymbol x;\omega,b)=\omega_1x_1+\omega_2x_2+...+\omega_Nx_N+b X⊑RNf(x;ω,b)=ω1​x1​+ω2​x2​+...+ωN​xN​+b增广形式： f ( x ; ω ) = ω 0 x 0 + ω 1 x 1 + ω 2 x 2 + . . . + ω N x N        ( x 0 = 1 ) f(\boldsymbol x;\omega)=\omega_0x_0+\omega_1x_1+\omega_2x_2+...+\omega_Nx_N\;\;\;(x_0=1) f(x;ω)=ω0​x0​+ω1​x1​+ω2​x2​+...+ωN​xN​(x0​=1)
解释一下，f这个函数是典型线性模型函数。其中 ω = [ ω 1 , ω 2 , . . . ω N ] T \omega={\lbrack\omega_{1,}\omega_2,...\omega_N\rbrack}^T ω=[ω1,​ω2​,...ωN​]T是N维的权重向量，b是偏置。当解决线性回归问题时，我们直接用 f ( x ; ω ) f(x;\omega) f(x;ω)即可预测输出目标。
但是在感知机中，我们使用符号函数 s i g n ( ) sign() sign()作为激活函数。对于二分类问题：
y ∈ { − 1 ， 1 } y\in\{-1，1\} y∈{−1，1}
则我们的假设函数函数定义如下：
h ( x ; ω ) = s i g n ( ω T x + b ) = { + 1              i f    ω T x + b > 0 − 1              i f    ω T x + b < 0 h(x;\omega)=sign(\omega^Tx+b)=\left\{\begin{array}{l}+1\;\;\;\;\;\;if\;\omega^Tx+b>0\\-1\;\;\;\;\;\;if\;\omega^Tx+b<0\end{array}\right. h(x;ω)=sign(ωTx+b)={+1ifωTx+b>0−1ifωTx+b<0​

线性可分的概念

对于两类线性可分模型中有：
对 R n \mathbb{R}^n Rn中任意一个样本都满足
y ( i ) × ( ω T x ( i ) + b ) > 0 y^{(i)}\times(\omega^T\boldsymbol x^{\boldsymbol(\mathbf i\boldsymbol)}+b)>0 y(i)×(ωTx(i)+b)>0
即说明是线性可分的 。其实蛮好理解的，h(x;w)就是(wTx+b)是我们的预测函数，如果它大于0，我们输出y=1，表示一种分类。如果小于0，说明是另一种分类。那么一个在数据集中的样本 x ( i ) x^{(i)} x(i)对于的 y ( i ) y^{(i)} y(i)要么是1要么是-1，则要是与假设函数乘积大于0，说明是同号的，即是一个分类。
则感知机的最终目标就是要找到一个n维参数 ω \omega ω，使得对于样本中每一个样本都有：
y ( i ) × ( ω T x ( i ) + b ) > 0 y^{(i)}\times(\omega^T\boldsymbol x^{\boldsymbol(\mathbf i\boldsymbol)}+b)>0 y(i)×(ωTx(i)+b)>0

（二）损失函数

策略一：
现在我们以出错的角度出发，去建立一个损失函数。
说白了就是用分类分错的个数作为损失函数。损失函数的目的就是损失函数越小对于我们的假设函数模型越好。那对于一个线性分类模型，是不是分得越准越好。那么我们以分类分错的个数作为损失函数从目的上来说是没毛病的。
l o s s ( x ; ω ) = ∑ i = 1 N I { y ( i ) ( ω T x + b ) < 0 } loss(\boldsymbol x;\omega)=\sum_{i=1}^NI\{y^{(i)}(\omega^T\boldsymbol x+b)<0\} loss(x;ω)=i=1∑N​I{y(i)(ωTx+b)<0}
就是说，我们把样本 x ( i ) x^{(i)} x(i)带入假设函数中，算出的值要是和原来数据集对应的分类 y ( i ) y^{(i)} y(i)异号，则说明不是同类。
I（·）是指示函数，如果括号中的表达式成立，则函数值为1，反之为0。配合求和符号能很方便的表示个数。

我们期望的是loss函数越小越好，最好是能求出它的极值情况。但是请注意，按照常规操作应该是要求导，但是这个函数啊，它不能求导。因为它是离散的，不是连续函数这咋导。所以这个方法不行。

策略二：

引入超平面距离：

在n维空间中，超平面表示n-1维的一个空间模型。比如在二维坐标系(平面)中，超平面就是一维的一根直线。在3维空间中，超平面就可以用一个曲面方程来表示。超平面可以有效分类高一个维度的模型。

超平面在分类问题中，也称为决策边界。那在现在感知机模型中，超平面是什么呢。

其实就是两个类别之间的那个分界线。现在回归一下假设函数： h ( x ; ω ) = s i g n ( ω T x + b ) = { + 1              i f    ω T x + b > 0 − 1              i f    ω T x + b < 0 h(x;\omega)=sign(\omega^Tx+b)=\left\{\begin{array}{l}+1\;\;\;\;\;\;if\;\omega^Tx+b>0\\-1\;\;\;\;\;\;if\;\omega^Tx+b<0\end{array}\right. h(x;ω)=sign(ωTx+b)={+1ifωTx+b>0−1ifωTx+b<0​
那，分类之间的边界不就是 ω T x + b = 0 \omega^Tx+b=0 ωTx+b=0这条直线么。但是在高维就不是直线了，可能是一个二维平面等等。

现在回归主题，我们怎么选择一个更优质，连续可导的函数。这里可以用距离！！如果我分类分错了，那么这个点到决策边界的距离（超平面的距离）我先假设为 d d d 那么是不是 d d d 越小越好呢。就是说我分错了，但是越离我的分类界限越近越好。
举个例子，我现在要从牛奶和咖啡中分类一杯咖啡，但是现在拿到了一杯特浓高钙牛奶。这个损失就很大，也就是说它距离我分类平面的距离越远 d d d越大，然后拿到了一杯淡淡的牛奶，现在相比之前的特浓牛奶，我的 d d d 变小了。之后又拿到了一杯含有咖啡因的牛奶， d d d 更小了。然后拿到了一杯混有一点点咖啡的牛奶，那这个样本非常接近决策边界了，所以 d d d 无限接近0。

针对于每个分错类的点：
y ( i ) × ( ω T x ( i ) + b ) < 0 y^{(i)}\times(\omega^T\boldsymbol x^{\boldsymbol(\mathbf i\boldsymbol)}+b)<0 y(i)×(ωTx(i)+b)<0
它到决策边界（超平面）的距离 d d d为：
d = ∣ ω T x + b ∣ ∥ ω ∥ d=\frac{\vert\omega^T\boldsymbol x+b\vert}{\parallel\omega\parallel} d=∥ω∥∣ωTx+b∣​
联合分错点的不等式，有：
d = − ( ω T x + b ) y ( i ) ∥ ω ∥ d=-\frac{(\omega^T\boldsymbol x+b)y^{(i)}}{\parallel\omega\parallel} d=−∥ω∥(ωTx+b)y(i)​
能去掉绝对值乘一个-y，是因为y不是取1就是-1，而且它与假设函数的乘积是一个负值，在补上一个负号就可以了。

那现在我们求的是一个分错点的，总的来看，这个模型要好。肯定是对于每一个出错的样本点，它距离决策边界越近越好，那就是 d 1 d_1 d1​、 d 2 d_2 d2​… d N d_N dN​的总和越小越好。则有：
d s u m = − 1 ∥ ω ∥ ∑ i = 1 n ( ω T x ( i ) + b ) y ( i ) d_{sum}=-\frac1{\parallel\omega\parallel}\sum_{i=1}^n(\omega^T\boldsymbol x^{\boldsymbol(\mathbf i\boldsymbol)}+b)y^{(i)} dsum​=−∥ω∥1​i=1∑n​(ωTx(i)+b)y(i)
注意，这里的n是出错的样本个数。
这个函数是一个连续的可导。它可以作为我们的损失函数:
l o s s ( x ; ω , b ) = − ∑ i = 1 n ( ω T x ( i ) + b ) y ( i ) loss(x;\omega,b)=-\sum_{i=1}^n(\omega^T\boldsymbol x^{\boldsymbol(\mathbf i\boldsymbol)}+b)y^{(i)} loss(x;ω,b)=−i=1∑n​(ωTx(i)+b)y(i)
分别对 ω \omega ω、 b b b求偏微分：
（如果是增广形式，默认 x 0 x_0 x0​=1， ω 0 \omega_0 ω0​=b 参数b可以省略）
{ ∂ l o s s ( x ; ω , b ) ∂ ω = − ∑ x ( i ) i = 1 n y ( i ) ∂ l o s s ( x ; ω , b ) ∂ b = − ∑ i = 1 n y ( i ) \left\{\begin{array}{l}\frac{\partial loss(x;\omega,b)}{\partial\omega}=-\overset n{\underset{i=1}{\sum\boldsymbol x^{\boldsymbol(\mathbf i\boldsymbol)}}}y^{(i)}\\\\\\\frac{\partial loss(x;\omega,b)}{\partial b}=-\sum_{i=1}^ny^{(i)}\end{array}\right. ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​∂ω∂loss(x;ω,b)​=−i=1∑x(i)​n​y(i)∂b∂loss(x;ω,b)​=−∑i=1n​y(i)​

（三）优化算法

1.梯度下降法 GD

梯度下降法详细推导

ω t + 1 = ω t − α ∂ l o s s ( x ; ω , b ) ∂ ω ( α 是 学 习 率 ) \omega_{t+1}=\omega_t-\alpha\frac{\partial loss(x;\omega,b)}{\partial\omega} (\alpha是学习率) ωt+1​=ωt​−α∂ω∂loss(x;ω,b)​(α是学习率)
ω t + 1 = ω t + α ∑ x ( i ) i = 1 n y ( i ) \omega_{t+1}=\omega_t+\alpha\overset n{\underset{i=1}{\sum\boldsymbol x^{\boldsymbol(\mathbf i\boldsymbol)}}}y^{(i)} ωt+1​=ωt​+αi=1∑x(i)​n​y(i)
同理
b t + 1 = b t + α ∑ i = 1 n y ( i ) b_{t+1}=b_t+\alpha\sum_{i=1}^ny^{(i)} bt+1​=bt​+αi=1∑n​y(i)
2.随机梯度下降法 SGD
ω t + 1 = ω t + α x ( i ) y ( i ) \omega_{t+1}=\omega_t+\alpha x^{\boldsymbol(\mathbf i\boldsymbol)}y^{(i)} ωt+1​=ωt​+αx(i)y(i)
b t + 1 = b t + α y ( i ) b_{t+1}=b_t+\alpha y^{(i)} bt+1​=bt​+αy(i)
只用当前点来更新

3.牛顿法
ω t + 1 = ω t − α H − 1 ( ω ) ∂ l o s s ( x ; ω , b ) ∂ ω \omega_{t+1}=\omega_t-\alpha H^{-1}(\omega)\frac{\partial loss(x;\omega,b)}{\partial\omega} ωt+1​=ωt​−αH−1(ω)∂ω∂loss(x;ω,b)​
H − 1 H^{-1} H−1是Hessian矩阵的逆

3.拟牛顿法
后续再更新拟牛顿ba
− - −

（四）感知机收敛性证明

1.由于数据集线性可分有：
y ( i ) ω T x > 0 y^{(i)}\omega^Tx>0 y(i)ωTx>0
∃ γ > 0      s . t .    γ = m i n { y ( i ) ω T x } \exists\gamma>0\;\;s.t.\;\gamma=min\{y^{(i)}\omega^T\boldsymbol x\} ∃γ>0s.t.γ=min{y(i)ωTx}
γ \gamma γ是一个很小的正数。设 ω ∧ \overset\wedge\omega ω∧是最终最优的参数。是一个能很准确分类的参数。
y ( i ) ω ∧ T x ( i ) ≥ γ > 0 y^{(i)}\overset\wedge\omega^Tx^{(i)}\geq\gamma>0 y(i)ω∧Tx(i)≥γ>0
2.第k次误分类时：
ω k = ω k − 1 + α y ( i ) x ( i ) \omega_{k}=\omega_{k-1}+\alpha y^{(i)}x^{(i)} ωk​=ωk−1​+αy(i)x(i)
ω k ⋅ ω ∧ = ω k − 1 ⋅ ω ∧ + α y ( i ) x ( i ) ⋅ ω ∧ \omega_{k}\cdot\overset\wedge\omega=\omega_{k-1}\cdot\overset\wedge\omega+\alpha y^{(i)}x^{(i)}\cdot\overset\wedge\omega ωk​⋅ω∧=ωk−1​⋅ω∧+αy(i)x(i)⋅ω∧
ω k ⋅ ω ∧ ≥ ω k − 1 ⋅ ω ∧ + α γ \omega_{k}\cdot\overset\wedge\omega\geq\omega_{k-1}\cdot\overset\wedge\omega+\alpha\gamma ωk​⋅ω∧≥ωk−1​⋅ω∧+αγ
ω k ⋅ ω ∧ ≥ ω k − 2 ⋅ ω ∧ + 2 α γ \omega_{k}\cdot\overset\wedge\omega\geq\omega_{k-2}\cdot\overset\wedge\omega+2\alpha\gamma ωk​⋅ω∧≥ωk−2​⋅ω∧+2αγ
. . . . .... ....
ω k ⋅ ω ∧ ≥ k α γ \omega_{k}\cdot\overset\wedge\omega\geq k\alpha\gamma ωk​⋅ω∧≥kαγ
3.令R为最大的样本值：

R = m a x 1 ≤ i ≤ N ∥ x ( i ) ∥ R=\underset{1\leq i\leq N}{max}\parallel x^{(i)}\parallel R=1≤i≤Nmax​∥x(i)∥
由SGD：
∥ ω k ∥ 2 = ∥ ω k − 1 ∥ 2 + 2 α ω T x ( i ) y ( i ) + α 2 ( x ( i ) ) 2      \parallel\omega_k\parallel^2=\parallel\omega_{k-1}\parallel^2+2\alpha\omega^Tx^{(i)}y^{(i)}+\alpha^2{(x^{(i)})}^2\;\; ∥ωk​∥2=∥ωk−1​∥2+2αωTx(i)y(i)+α2(x(i))2
2 α ω T x ( i ) y ( i ) 2\alpha\omega^Tx^{(i)}y^{(i)} 2αωTx(i)y(i)这一项是小于0的，因为是误分点，详情看之前的推导。故有：
∥ ω k ∥ 2 ≤ ∥ ω k − 1 ∥ 2 + α 2 ( x ( i ) ) 2      \parallel\omega_k\parallel^2\leq\parallel\omega_{k-1}\parallel^2+\alpha^2{(x^{(i)})}^2\;\; ∥ωk​∥2≤∥ωk−1​∥2+α2(x(i))2
现在把刚刚 R R R的定义拿过来用
∥ ω k ∥ 2 ≤ ∥ ω k − 1 ∥ 2 + α 2 R 2 \parallel\omega_k\parallel^2\leq\parallel\omega_{k-1}\parallel^2+\alpha^2R^2 ∥ωk​∥2≤∥ωk−1​∥2+α2R2
∥ ω k ∥ 2 ≤ ∥ ω k − 2 ∥ 2 + 2 α 2 R 2 \parallel\omega_k\parallel^2\leq\parallel\omega_{k-2}\parallel^2+2\alpha^2R^2 ∥ωk​∥2≤∥ωk−2​∥2+2α2R2
. . . . .... ....
∥ ω k ∥ 2 ≤ k α 2 R 2 \parallel\omega_k\parallel^2\leq k\alpha^2R^2 ∥ωk​∥2≤kα2R2

综上所述：

由上面三个结果可以得到：
由2可知：
k α γ ≤ ω k ω ∧ k\alpha\gamma\leq\omega_k\overset\wedge\omega kαγ≤ωk​ω∧
这里有个很难理解的地方,我们假设 ω ∧ = 1 \overset\wedge\omega=1 ω∧=1。为什么可以这样操作呢，我的理解是， ω ∧ \overset\wedge\omega ω∧是最终优化的权重参数，它是会完全正确把所有样本分开的。 ω ∧ \overset\wedge\omega ω∧作为平面的法向量，是可以任意指定模长的，所以在证明之初，就可以假设它的模长=1方便计算。

故得到：
k α γ ≤ ω k k\alpha\gamma\leq\omega_k kαγ≤ωk​
由3可得:
k α γ ≤ k α R k\alpha\gamma\leq\sqrt k\alpha R kαγ≤k ​αR
k ≤ R 2 γ 2 k\leq\frac{R^2}{\gamma^2} k≤γ2R2​
这就说明了，k不是发散的，它总会小于某个值。我们的感知机算法在迭代k次后会收敛。收敛的次数和 R = m a x 1 ≤ i ≤ N ∥ x ( i ) ∥ R=\underset{1\leq i\leq N}{max}\parallel x^{(i)}\parallel R=1≤i≤Nmax​∥x(i)∥ 有关，样本x最大值有关，还和一个参数 γ \gamma γ有关。
反正总之我们是证明了它的收敛性了。