感知器在数据集划分超平面做分类，模型参数包含权值向量 \(w\) 和偏移 \(b\) ;模型的损失函数定义了错分点到超平面的距离和；模型的更新机制是基于错误驱动的SGD方法。最后，感知器是一种线性分类方法，是判别模型。

0. 基本思想

我们把数据表示为向量空间中的点（使用一个向量表示）。分类问题就是要将数据划分到相应类别，对应到向量空间，就是要划分数据点——如果是二元分类，我们就说将点划分为正例(POSITIVE)与负例(NEGATIVE)；如果是多元分类，我们输出一个标签(LABEL)。

感知器是在向量空间中构建一个或多个超平面，对数据点进行划分。如果是二元分类，只需要一个超平面即可。如果是多元分类 ,设类别数为N(\(N > 2\))，则需要N个超平面。

感知器的超平面思想，更一般的可以称为线性分类面、线性决策边界等。这种思想是SVM（支持向量机），NN（神经网络）的基础。

1. 超平面定义

在向量空间（欧式空间）\(\mathbb{R}^n\)中，定义 平面法向量\(W \in \mathbb{R}^n\) , 定义平面偏移 \(b \in \mathbb{R}^1\) , 定义空间中的点（实例）\(X \in \mathbb{R}^n\) ， 则超平面可表示为：

\[y = W * X + b\]

欧式空间： 又称为欧几里得空间（Euclidean Space）。用\(\mathbb{R}\)表示实数域，对任意一个正整数n，实数的n元组的全体构成了\(\mathbb{R}\)上的一个n维向量空间，用\(\mathbb{R}^n\)表示，有时称之为实数坐标空间(来自维基百科).通俗的来说，初高中学习的二维坐标空间、三维立体空间都是欧式空间。

###1.1 关于平面的一些强调

  1. \(y = W * X + b\)中，W就是平面的法向量。

  2. 任意点到平面的距离：设点为\(x \in \mathbb{R}^n\) , 则点到平面\(y = W * X + b\)的距离为 \(D = \frac {\vert W*x + b \vert}{\Vert W \Vert_2}\) （即把x带入平面方程中求出的值取绝对值，除以平面法向量W的模（二范数）） 。这也被称为几何间隔 。

2.模型

2.1 什么是模型

在监督学习过程中，模型就是要学习的概率分布或者决策函数。感知器所属的判别模型，通常是确定一个决策函数，来将输入映射到输出。

2.2 感知器模型

2.2.1 决策函数：

对于二元分类，

\[y = sign(W*X + b)\]

其中sign函数定义为：

\[sign(t) = \cases{ +1 \quad (t \gt 0) \\ -1 \quad (t \leq 0) }\]

W是权值向量，即平面法向量 \(W \in \mathbb{R}^n\)，b是偏移 , \(b \in \mathbb{R}\)； X是输入向量，\(X \in \mathbb{R}^n\) , y是输出label，\(y \in \{-1,+1\}\)

对于多元分类,

\[y_i = \arg_{i \in I} \max(W_i * X + b_i)\]

设输出类别数为\(n\) , 下标集合\(I = \{ 0 , 1 , ... , n-1\} , i \in I\) ，输出标签 \(y_i \in \{y_0 , y_1 , ... , y_{n-1}\}\) . 前面提到，n个类别，需要n个超平面。则对应的权值向量集合为\(\{ W_0 , W_1 , ... , W_{n-1} \}\) ，对应的b为\(b \in \{ b_1 , b_2 , ... , b_{n-1} \}\)。

2.2.2 直观定义

二元分类，把点带入平面，结果为正即为正例，否则为负例。

多元分类，取点到所有超平面中距离（严格来说，指带入平面方程的值，有正负）最大的超平面对应的标签作为输出。

##3.优化目标(损失函数)

这里仅考虑二元分类的情况。

感知器的损失函数，定义为错分的点到超平面的距离之和（即认为正确分类的点到超平面距离为0）。

前面提到点到超平面的距离为\(D = \frac{1}{\Vert W \Vert_2} \vert W*X + b \vert\) , 我们知道，所谓错分的点，即\(y_{predict} = sign(W*X+b)\)与点的正确标签不同，即\(y_{predict} != y\) , 换句话说，即是

\[\begin{align*} y *& y_{predict} \leq 0\\ y *& (W*X +b) \leq 0\\ -y *& (W*X +b) \geq 0 ~且~ \vert y \vert = 1 \end{align*}\]

故我们可以将平面距离去掉绝对值，\(D = - \frac{1}{\Vert W \Vert_2 } y ( W*X + b )\) 。

令错分点的集合为\(M\) , 则错分点到超平面距离之和可以定义为： \(D_M = - \frac{1}{\Vert W \Vert_2} \sum_{m \in M}{y_m(W*X_m + b)}\)

通常，我们将\(\frac{1}{\Vert W \Vert_2}\)去掉，就得到了感知器的损失函数L：

\[L(w , b) = - \sum_{m \in M}{W*X_m + b}\]

其中\(M\)是错分点的集合。

将几何间隔\(D = \frac{1}{\Vert W \Vert_2} \vert W*X + b \vert\) 去掉\(\frac{1}{\Vert W \Vert_2}\) ，得到\({D}' = \vert W*X + b \vert\)， 这也可以被称做函数间隔。

4. 学习算法

所谓学习，就是为模型的参数找到一个合适的值，使得优化目标得到数据集上的最优（或局部最优）解（如果以损失函数作为优化，则是使损失函数值达到最小或局部最小）。

如果优化目标函数是一个凸函数或凹函数，即可以有全局最优；如果不是，则仅能保证有局部最优。

凸函数，形状类似二元函数且开口向上，有最小值；凹函数则类似二元函数开口向下，有最大值。

感知器使用随机梯度下降(SGD , Stochastic Gradient Descent )的方式来学习得到使得损失函数最小的W和b。当数据集可分时，学习到的参数能够使得损失为0（称为学习算法收敛）；如果不可分，则损失值在一定范围内波动。

当然还有其他的学习算法，如基于数学的最小二乘法（矩阵运算），还有其他的如BFGS , LBFGS等等。（PS：并不知道这些方法实际内容）

梯度下降法，是通过迭代，每次沿着梯度下降的方向移动一段距离，最终达到一个极值点的方法。梯度，就是导数；梯度下降的方向，数值上表示就是就是导数的相反数。常常再为导数相反数乘上一个 \(\eta\) , 这也被称作学习因子(Learning Rate)。学习因子对于梯度下降而言还是比较重要的，因为这在一定程度上决定了每次梯度下降的距离。我们定义每次梯度下降的距离为\(\Delta = - \nabla * \eta\) 。如果\(\eta\)过大，则可能导致优化函数的值在极值点附近来回动荡；过小则会使迭代次数增加。故一般来说，未知情况下可以把\(\eta\)设置稍小一些。一般说来，将\(\eta\)设置为一个定值即可，因为导数是随参数变化而变化的，在极值点附近会自然比较小，在其他区域会比较大。当然，也有一些Ada方法，会根据最近导数变化的情况设置学习因子的值（一般在一个范围内变化），这在神经网络这种每次迭代开销很大的环境下使用还是很有增益的。梯度下降根据更新频次的不同，可以分为三种。第一种就是普通梯度下降,或者叫批量梯度下降（batch GD），在整个数据集上做梯度下降——以感知器为例，如果是普通梯度下降，那么便是将训练集中所有错分点全部过一遍后，将得到的损失函数求梯度做更新。这是从数学意义上最直观、最可信的做法。但是更新一次开销很大。第二种被称为小批量梯度下降(mini-batch GD , 中文名不准确)，就是把数据集分成N份，每份做完后就做一次梯度下降更新。最后就是随机梯度下降（SGD），每个对优化函数有影响的实例（在感知器中，是每个错分的实例）都会引起随机梯度下降的更新。这无疑更新频率提高了，但是针对一个实例的更新，是否对全局的优化函数更新有利？据张岳老师说某位大师穷其一生证明了其与普通GD等价。但是查资料却没有找到是具体哪位，有些唏嘘。

感知器的损失函数 \(L(W,b) = -\sum_{m \in M}{y_m (W*X_m + b )}\) , 使用SGD，只考虑一个实例，设\(i \in M\) , 则\(X_i\)是错分实例，需要进行梯度下降更新。按照以下步骤：

  1. 求$ W $ , $ b $ 在实例\(x_i\)下的损失函数梯度（即对$ W $、$ b $求导）。

    对$ X_i $的损失函数为：\(L(W,b,i) = -y_i (W * X_i + b)\) ,

    对$ W $求导，有\(\frac{\partial L}{\partial W} = -y_i * X_i\)

    对$ b $求导，有\(\frac{\partial L}{\partial b} = -y_i\)

  2. 更新

    设学习因子为$ \eta $ , 则：

    对$ W $ 更新：\(W' = W - \eta * \frac{\partial L}{\partial W} = W + y_i \eta X_i\)

    对$ b $ 更新: \(b' = b - \eta * \frac{\partial L}{\partial b} = b + y_i \eta\)

以上，就完成了一次SGD过程。在训练集上迭代，直到收敛（L = 0）或者在某个阈值内波动即可停止迭代，完成参数学习过程。

4.1 学习算法的直观理解及对多元分类的扩展

以$ W $为例， $ W’ = W + y_i \cdot \eta \cdot X_i $ , 可以理解为：对于正例，如果我们将其错分为负例，则我们将$ W $加上$ \eta \cdot X_i $ , $ \eta \cdot X_i $向量中元素值均非负，这使得下次再划分该实例时，$ WX_i + b $的值会更偏向正一些，即向正确结果更靠近。对于负例的分析同理。

由此我们可以扩展出使用感知器进行多元分类的更新算法：

首先，对于多元分类，每个类别都有权值向量，而输出类别的确定方式为$ y_{predict} = \arg \max_y (W_y \cdot X + b ) $ ， 故如果错分，我们可以增加正确类别对应的权值，同时减少输出类别对应的权值项。经过这样地处理，下次进行$ \arg \max$运算时，感知器就能够向正确的结果靠近。这与二元分类更新算法的直观理解相同。

感知器将一个实例分类错误后，经过更新算法的更新，并不能保证修正后的参数能够立刻正确分类该实例，而仅仅能保证会向该正确结果靠近。这说明更新算法是保守的而非主动的[1]。

###4.2 学习算法伪代码

定义权值向量$ \vec W $ , 偏移 $ b $ (或$\vec b$ ) , 迭代次数$ N $ , 数据集\({\rm T} = \{(\vec X_i , y_i) \}_{1}^M\) , 学习率 $ \eta $

  1. 二元分类

    $\vec W \in \mathbb{R}^{1 \times n} $ , $ b \in \mathbb{R}^1 $(sigular , 常量) , $ \vec X_i \in \mathbb{R}^{n \times 1} $ , \(y \in \{ -1 , +1 \}\)

     binaryClassificationPerceptronTrain( $ \vec W_0 , b_0 , N , {\rm T} , \eta $ ) :
     $\vec W = \vec W_0$
     $b = b_0$
     repeat N times :
         for $( \vec X_i , y_i )$ in $ {\rm T} $ :
             $ y_{predict}  =  sign( \vec W \cdot \vec X_i + b ) $
             if $ y_{predict} \cdot y_i < 0 $ :
                 $ \vec W = \vec W + y_i \cdot \eta \cdot \vec X_i^T $ # 转置
                 $ b = b + y_i \cdot \eta $
     return $ \vec W $ , $ b $

  2. 多元分类

    $\vec W \in \mathbb{R}^{k \times n} $ , $ \vec b \in \mathbb{R}^{k \times 1} $ , $ \vec X_i \in \mathbb{R}^{n \times 1} $ , \(y \in L = \{l_0 , l_1 , \dots , l_k \}\)

    定义矩阵变换函数 G = get_corresponding_row(Matrix/Vector m , label l ) , 将矩阵（向量）对应label行取出

    定义矩阵变换函数 E = extend_variable(Vector/sigular v , label l) , 将向量（常数）向上扩展一维（可以认为是函数G的相反运算），对应label行为值为v，其余全部为0.

     multiClassificationPerceptronTrain($ W_0 , \vec b_0 , N , {\rm T} , \eta $) :
     $ W = W_0 $
     $ \vec b = \vec b_0 $
     repeat N times :
         for $( \vec X_i , y_i )$ in $ {\rm T}$ :
             $ y_{predict} = \arg \max_{y \in L}(G(W,y) \cdot \vec X_i + G(\vec b , y) ) $
             if $y_{predict} $ in not equal to $ y_i $ :
                 $ W = W + \eta \cdot (E(\vec X_i , y_i) - E( \vec X_i , y_{predict})) $
                 $ \vec b = \vec b + \eta \cdot ( E(1 , y_i ) - E(1 , y_{predict}) )$

     return $ \vec W $ , $ \vec b$

二元分类理论上也可以使用多元分类的处理方式。我觉得二元分类方法更多是用于理论的说明，实际效果与使用多元的方式是一样的。并没有实际结果或严格理论作为支撑，仅仅个人推断

关于代码中偏置b的处理

大部分情况下，b都被放入到W向量中或者被忽略。

如果我们需要保证分类面有偏移，即保证b不能被省略，那么我们可以将b嵌入到W中，即$ W’ = [W_0 W_1 W_2 \dots W_n b]$ ， 此时，相应的输入向量X也需要做处理，即加入一维常量1 ， $X’^T = [X_0 X_1 \dots X_n 1] $ 。 这与$WX+b$是完全等价的。

通常情况下，忽略偏移并不会有太大的影响。（此结论是由毕设调整SVM参数得出的，并没有理论依据）

以后的描述为了方便，都将省略$b$.

5. 预测算法

  1. 二元分类

    $ y_p = sign (W \cdot X + b) $

  2. 多元分类

    $ y_p = argmax_y(W_y \cdot X + b) $

6. 感知器变种

###6.1 平均感知器(Average Perceptron , AP)

普通感知器最终返回的权值向量，是针对最近所见实例的一个更新。直观上来看，这存在对最近所见实例一个过拟合现象，对之前的实例效果可能并不好。[2]

平均感知器的思想，是将每次循环（更加准确的说，是每次大迭代中对每个实例的操作，无论是否更新）得到的权值向量作为一个单独的感知器，每个感知器都可以看作是对最近看到数据的拟合。将所有的权值向量平均，或许会有不错的效果。

设迭代次数为 $ N $ , 训练集实例数为 $ \vert {\rm T} \vert $ , 则我们共需要将$ N \times \vert {\rm T} \vert $个权值向量平均，即

\[\bar{W} = \frac{W_1 + W_2 + \dots + W_{N \times \vert {\rm T} \vert}} {N \times \vert {\rm T} \vert}\]

AP伪代码

以多元分类为例

averagePerceptronTrainNaive($ W_0 $ , $ N $ , $ {\rm T} $ ) :
    t = 0
    repeat N times :
        for $( X_i , y_i )$ in $ {\rm T} $ :
            $y_p = argmax_y(W_t \cdot f(X_i , y))$
            if $y_p$ is not equal to $y_i$ :
                $ W_{t+1} = W_t + f(X_i , y_i) - f(X_i , y_p) $
            else :
                $ W_{t+1} = W_t $
            $ t = t+1 $
    return $\frac {W_1 + W_2 + \dots + W_{N \times \vert {\rm T} \vert }} {N \times \vert {\rm T} \vert }$ # $ t = N \times \vert {\rm T} \vert $

上述方法是一种朴素的对平均感知器算法的描述，在实际实现中是不可取的。因为保存$N \times \vert {\rm T} \vert $个$ W $并不现实。

在[2]中提到了一种解决方法：

首先，我们定义每次循环都有一个增量为$ \Delta $，记第 $i$ 次为$\Delta_i$ 。 增量根据是否更新，可以为0或者为$f(X_i , y_i) - f(X_i , y_p)$

则每个权值向量可以表示为:

\[\begin{align*} W_1 &= W_0 + \Delta_1 \\ W_2 &= W_1 + \Delta_2 = W_0 + \Delta_1 + \Delta_2 \\ \dots \\ W_n &= W_{n-1} + \Delta_n = W_0 + \Delta_1 + \Delta_2 + \dots + \Delta_n \end{align*}\]

则

\[\begin{align*} \frac {W_1 + W_2 + \dots + W_n} {n} &= \frac{W_0 + \Delta_1 + W_0 + \Delta_1 + \Delta_2 + \dots + W_0 + \Delta_1 + \Delta_2 + \dots + \Delta_n} {n} \\ &= \frac{n \cdot W_0 + n\cdot\Delta_1 + (n-1)\cdot\Delta_2 + \dots + \Delta_n}{n} \\ &= W_0 + \Delta_1 + \frac{n-1}{n}\cdot\Delta_2 + \dots + \frac{1}{n}\cdot\Delta_n \end{align*}\]

伪代码表示为

averagePerceptronTrain($W_0$ , $N$ , ${\rm T}$) :
    $ n = N \cdot \vert {\rm T} \vert$ 
    $ leftSteps = n $
    $ \bar{W} = W_0 $
    $ W = W_0 $
    repeat N times :
        for $(X_i , y_i)$ in ${\rm T}$ :
            $ y_p = argmax_y(W \cdot f(X_i,y) + b)$
            if $y_p$ in not equal to $y_i$
                $W = W + f(X_i , y_i) - f(X_i , y_p)$
                $\bar{W} = \bar{W} + \frac {leftSteps}{n} \cdot ( f(X_i , y_i)$ - f(X_i , y_p) ) $
            leftSteps = leftSteps -1 
    return $\bar{W}$

还有一种思路（根据LTP中的逻辑），每次仅记录本次更新的具体信息，该信息具体到向量中的每一维。

由于每次更新实际上对权值向量来说只有很少的维被更新，故仅记录（更新的维，增量的大小，循环次数）这3个数据即能表示一次更新。最后再用该数据表现在数据上就行了。非常偏实现的方法，目前没有实现，不能多说。

更新

已经完成从使用Python实现LTPCWS的功能。

关于平均感知器，最简单直观且实际的实现为：

增加一个W_sum权值向量，每次循环后 W_sum += W ，即把当前的权值向量加到W_sum中，最后返回W_sum/n(n为总迭代次数)即可。

LTPCWS中的实现如上所言，定义了W_time ， W_sum 和 current_time ， W_time记录向量每一维最后更新的时间last_update_time，而W_sum中对应维数的值表示在该最后更新时刻的和origin_sum_val。当在current_time该维需要更新时，在（current_time - last_update_time - 1 ）的时间里（循环次数里）该维的值均为W对应的值val ， 记更新增量为$ \Delta $ , 则到当前时刻W_sum中该维的值为 \(\begin{align*} sum\_val &= \underbrace{origin\_sum\_val}_{原始和} + \underbrace{(current\_time - last\_update\_time -1 ) \cdot val}_{过去时间应该加上的值} + \underbrace{( val + \Delta )}_{本次的权值} \\ &= origin\_sum\_val + (current\_time - last\_update\_time) \cdot val + \Delta \end{align*}\)

6.2 感知器的对偶形式

之前说的感知器学习算法称为原始形式，即维护一个权值向量W（和b） ， 而对偶形式则试图将W表示为输入X和标签y的线性组合方式，通过求解线性方程的系数来求得W。

感知器的原始形式、对偶形式与支持向量机的原始形式、对偶形式相对应。

在原始形式中，我们的权值更新方式为：

\[\vec W = \bar{W} + \eta \cdot y_i \cdot \vec X_i\]

初始时W = 0 , 为更清晰的理解，我们为学习算法的原始形式增加不更新时的情况：

    if $ y_{predict} \cdot y_i < 0 $ :
        $ \vec W = \vec W + 1 \cdot \eta \cdot y_i \cdot \vec X_i^T $ 
    else :
        $ \vec W = \vec W + 0 \cdot \eta \cdot y_i \cdot \vec X_i^T $

从上面可以比较清晰的看出，我们的W可以表示为X_i 与 y_i 的乘积的线性函数，且其系数为 $ n \cdot \eta $ , 其中n为该实例引起的更新次数。由此得到对偶形式的权值表示：

\[W = \sum_{i=1}^T { n_i \cdot \eta \cdot y_i \cdot X_i }\]

其中$ n_i $为实例$ X_i $引起的更新次数，T为实例数。

由此我们的预测函数变为：

\[\begin{align*} y &= W\cdot X \\ &= ( \sum_{j=1}^T {n_j \cdot \eta \cdot y_j \cdot X_j } ) \cdot X_i \\ &= \sum_{j=1}^T { ( n_j \cdot \eta \cdot y_j \cdot X_j \cdot X_i )} \end{align*}\]

我们可以先把$ X_j \cdot X_i $($ \eta \cdot X_j \cdot X_i $) 的结果存储起来，避免重复运算。存储结果为$ T \times T $的矩阵，称为Gram 矩阵（Gram Matrix）

[1] 感知器学习研究 ， 刘建伟

[2] The averaged perceptron , PPT from Richard Johansson , University of Gothenburg

哥德堡大学（Göteborgs universitet，GU），是瑞典哥德堡的一所综合性大学。拥有在斯堪的纳维亚地区最多学生，在读学生5万人以上，是斯堪的纳维亚最大的大学之一。哥德堡大学也是瑞典大学里开设专业最广的大学之一一共有8个学院57个学科，8各学院分别是：创新艺术，社会科学，自然科学，人文，教育，信息技术，商业经济与法律以及健康科学。哥德堡大学号称是欧洲主要的大学之一，根据2009年泰晤士高等教育-QS世界大学排名来看，哥德堡大学世界排名185位。 (维基百科)