机器学习基础(5)-二分类问题与感知机模型
感知机模型
感知机（perceptron）是一种二分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取值为\(\{+1, -1\}\)。感知机学习旨在求出将训练数据进行线性划分的分离超平面，它也是神经网络与支持向量机的基础。
感知机的模型如下。输入空间为\(X\subseteq R^n\)，输入空间和特征空间相同；输出空间为\(Y=\{+1,-1\}\)。感知机的输入\(x\)是表示实例的特征向量，输出\(y\)表示实例的类别，感知机即为如下的函数： \[ f(x) = sign(w\cdot x+b) \] 其中\(w\)和\(b\)是感知机模型的参数，\(w\)被称为权重weight，\(b\)被称为偏置bias，sign为符号函数，\(w\cdot x\)为内积计算。
从几何上考虑，输入的\(x\)是特征空间中的一个点，感知机模型的假设空间则是定义在特征空间中的所有线性分类器，每个线性分类器对应特征空间中的一个超平面S，而参数向量\(w\)是超平面S的法向量，\(b\)是超平面S的截距。该超平面将特征空间划分为两个部分，位于两个部分的点分别对应不同的输出，+1和-1，即正类和负类。
考虑机器学习的分类，感知机所属的类别为：
- 监督学习
- 非概率模型，线性模型
- 在线学习
感知机学习策略
确定了模型之后，需要确定策略，即定义（经验）损失函数并将损失函数最小化。
感知机的损失函数被定义为误分类点到超平面S的距离，任一点\(x_i\)到超平面的距离为： \[ \frac{1}{||w||}|w\cdot x_i + b| \] 在我们有的数据集\((x_i,y_i)\)中，\(y_i\in Y = \{+1,-1\}\)。考虑数据集中误分类的数据\((x_i, y_i)\)，有下面的推导成立： \[ 当w\cdot x_i + b>0时：y_i = -1 \\ 当w\cdot x_i + b<0时：y_i = +1 \] 从而对于误分类的数据\((x_i,y_i)\)，它到超平面S的距离为： \[ -y_i\frac{1}{||w||}(w\cdot x_i + b) \] 不考虑系数\(1/||w||\)，我们可以得到感知机的经验风险函数： \[ L(w,b) = -\sum_{x_i\in M}y_i(w\cdot x_i + b) \] 其中M表示误分类点的集合。因此感知机的学习策略是经验风险最小化，也就是让上面经验风险函数最小。
感知机学习算法
感知机学习算法（Perceptron Learning Algorithm，PLA）具体包括原始形式和对偶形式。
原始形式
感知机学习算法是误分类驱动的，具体采用随机梯度下降法。首先仍选一个超平面，对应参数为\(w_0,b_0\)。然后用梯度下降法不断地极小化目标函数。极小化过程中不是一次使得M中所有误分类点的梯度下降，而是随机选取一个误分类点，使其梯度下降。考虑损失函数的梯度，有： \[ \bigtriangledown _wL(w,b) = -\sum_{x_i\in M}y_ix_i \\ \bigtriangledown _bL(w,b) = -\sum_{x_i\in M}y_i \] 每次随机选取一个误分类点\((x_i,y_i)\)，对参数\(w,b\)进行更新： \[ w\leftarrow w - \eta(-y_ix_i) = w+\eta y_ix_i \\ b\leftarrow b - \eta(-y_i) = b+\eta y_i \] 因此，感知机学习算法的原始形式如下：
- 输入：训练数据集\(T = {(x_1,y_1),...,(x_N,y_N)}\)；学习率\(\eta\ (0 < \eta \le 1)\)
- 输出：参数\(w,b\)，结果感知机模型\(f(x) = sign(w\cdot x+b)\)
首先选取初值\(w_0,b_0\)
在训练集中选取数据\((x_i,y_i)\)
如果有\(y_i(w\cdot x_i+b)\le 0\)，则表示这个点是一个误分类的点，则进行如下的参数更新： \[ w\leftarrow w+\eta y_ix_i \\ b\leftarrow b+\eta y_i \]
重复执行步骤2，3，直到训练集中没有误分类的点
从直观上理解上面的算法，每次找到一个误分类的点，则调整参数\(w,b\)的值，使得超平面向误分类点进行移动，以减少该误分类点与平面之间的距离。每次都这样调整，直到所有的点都能够被正确分类。不过需要注意的是，感知机学习算法受初值影响，也受过程影响。由于采用不同的初值或者选用不同的误分类点，得到的解也会不同。
对偶形式
对偶形式的基本思想：将\(w,b\)表示为\(x_i,y_i\)的线性组合，通过求解对应的系数来求得\(w,b\)。下面来介绍这种思想的合理性。
首先我们可以考虑假设初值均为0，即\(w_0=0,b_0=0\)。之后，对于误分类的点，同样有如下的更新方式： \[ w\leftarrow w+\eta y_ix_i \\ b\leftarrow b+\eta y_i \] 假设整个过程一共修改了n次参数，那么这n次修改会对应到不同的点上，具体对应关系与实际过程中误分类的情况以及选取误分类点的情况有关。整个过程迭代结束后，我们可以得到下面的等式： \[ w = \sum_{i=1}^{N}\alpha_iy_ix_i\\ b = \sum_{i=1}^{N}\alpha_iy_i \] 其中，对应系数\(\alpha_i = n_i\eta\)，\(n_i\)表示点\((x_i,y_i)\)在整个过程中被误分类的次数。这也就说，我们最终学习得到的参数可以被表示成\(x_i,y_i\)的线性组合，对应的系数就是\(\alpha_i\)，且系数的值一定是非负数。从这里也可以看出，最终参数结果与实例点的更新次数有关。如果一个实例点的更新次数越多，意味着它距离分离超平面越近，从而越难被分类正确，从而对学习结果影响越大。
因此，对偶形式的感知机学习算法如下：
- 输入：训练数据集\(T = {(x_1,y_1),...,(x_N,y_N)}\)；学习率\(\eta\ (0 < \eta \le 1)\)
- 输出：参数\(\alpha,b\)，结果感知机模型\(f(x) = sign(\sum_{j=1}^{N}\alpha_jy_jx_j\cdot x+b)\)
首先选取初值\(\alpha_0=0,b_0=0\)
在训练集中选取数据\((x_i,y_i)\)
如果有\(y_i(\sum_{j=1}^{N}\alpha_jy_jx_j\cdot x_i+b)\le 0\)，则表示这个点是一个误分类的点，则进行如下的参数更新： \[ \alpha \leftarrow \alpha +\eta \\ b\leftarrow b+\eta y_i \]
重复执行步骤2，3，直到训练集中没有误分类的点
在上面的过程中，实例之间进行的操作仅有内积，因此可以预先将训练集中实例之间的内积计算出来并以矩阵的形式进行存储，我们可以通过index直接取值得到对应的内积结果。而这个矩阵就是所谓的Gram矩阵： \[ G = [x_i \cdot x_j]_{N \times N} \]
算法可行性
感知机算法能够发挥作用的前提是数据集线性可分。我们很容易知道，如果是线性不可分的数据集，我们是无法通过一个超平面进行划分的，从而感知机算法也无法发挥作用。不过感知机算法在线性可分的数据集上一定能够起效吗，下面就来正面感知机算法的可行性，即通过有限次的迭代，算法一定能够收敛。
这里为了方便叙述，可以将偏执\(b\)并入权重\(w\)，对应同时将输入向量进行扩充，加入常数1。此时有\(\hat{w}=(w^T,b)^T,\hat{x}=(x^T,1)^T\)，增加上标hat表示对向量的扩充。则感知机的模型就变为了\(f(x)=sign(\hat{w}\cdot \hat{x})\)。
假设感知机在训练集上的误分类次数为k，那么我们需要证明的是k上界存在。
首先由于数据集线性可分，所以一定存在一个超平面\(\hat{w_{opt}}\)能够将训练集完全正确地分开，其中\(||\hat{w_{opt}} = 1||\)且训练集中的点都恰好不在这个面上。根据距离计算公式以及正负类的输出，可以得到如下的结果： \[ y_i(\hat{w_{opt}}\cdot \hat{x_{i}}) = y_i(w_{opt}\cdot x_i+b_{opt}) > 0 \] 取\(\gamma = \min_i\{ y_i(w_{opt}\cdot x_i+b_{opt}) \} > 0\)，则有： \[ y_i(\hat{w_{opt}}\cdot \hat{x_{i}}) = y_i(w_{opt}\cdot x_i+b_{opt})\ge \gamma > 0 \tag{1} \] 假设在第k-1次更新过后，参数向量为\(\hat{w_{k-1}}\)，而第k次更新参数向量，采用的误分类点为\((x_i,y_i)\)，那么对于这个误分类点，它应该满足： \[ y_i(\hat{w_{k-1}} \cdot \hat{x_i}) = y_i(w_{k-1}\cdot x_i + b_{k-1}) \le 0 \tag{2} \] 而第k次更新如下： \[ \hat{w_k} = \hat{w_{k-1}} + \eta y_i\hat{x_i} \] 这样，我们就可以进行如下推导： \[ \begin{aligned} \hat{w_{opt}} \cdot \hat{w_{k}} &= \hat{w_{opt}} \cdot(\hat{w_{k-1}} + \eta y_i\hat{x_i}) \\ &=\hat{w_{opt}}\cdot \hat{w_{k-1}} + \eta y_i(\hat{w_{opt}}\cdot \hat{x_{i}}) \\ &\ge \hat{w_{opt}}\cdot \hat{w_{k-1}} + \eta \gamma \quad using (1) \\ &\ge \hat{w_{opt}}\cdot \hat{w_{k-2}} + 2\eta \gamma \\ &\ge ...\ge k\eta \gamma \end{aligned} \tag{3} \] 同时我们取\(R=\max_{1\le i\le N} ||\hat{x_i}||\)，则有如下推导
\[ \begin{aligned} ||\hat{w_{k}}||^2 &= ||\hat{w_{k-1}} +\eta y_i\hat{x_i}||^2 \\ &=||\hat{w_{k-1}}||^2 + 2\eta y_i (\hat{w_{k-1}}\cdot \hat{x_i}) + \eta^2y_i^2||\hat{x_i}||^2 \\ &\le ||\hat{w_{k-1}}||^2 + \eta^2||\hat{x_i}||^2 \quad using (2) \\ &\le ||\hat{w_{k-1}}||^2 + \eta^2R^2 \\ &\le ||\hat{w_{k-2}}||^2 + 2\eta^2R^2 \\ &\le ... \le k\eta^2R^2 \end{aligned} \tag{4} \]
综合上面两个不等式(3)和(4)，则有：
\[ \begin{aligned} k\eta\gamma \le \hat{w_{opt}} \cdot \hat{w_{k}} & \le ||\hat{w_{opt}}||\ || \hat{w_{k}}|| \le || \hat{w_{k}}|| \le \sqrt{k}\eta R \\ k\eta\gamma &\le \sqrt{k}\eta R \\ k &\le (\frac{R}{\gamma})^2 \end{aligned} \]
综上所述，感知机的误分类次数k是存在上界的，且上界为\((R/\gamma)^2\)，且其中\(R=\max_{1\le i\le N} ||\hat{x_i}||\)，\(\gamma = \min_i\{ y_i(w_{opt}\cdot x_i+b_{opt}) \} > 0\)。这也就说，经过有限次搜索，一定可以找到将训练数据完全正确划分开的分离超平面。
感知机算法对于线性可分的数据集是有效的，但是如果想要在线性不可分的数据集上应用感知机算法，则需要对要求进行放宽。我们不强求对所有的实例点都满足正确分类，而是容忍有错误点，最终的模型应该让错误点的个数最少。不过这个问题是一个NP难问题。
我们将原始的感知机学习算法进行修改，称为Packet Algorithm。它的流程与PLA类似，每次对错误点进行修正。只不过在进行更新的时候，会计算当前分类错误点的个数，并与之前的结果进行比较，取效果更好的超平面作为当前选择。经过n次迭代之后，得到最终结果，这应该是一个相对较好的分离超平面。
Packet Algorithm是感知机算法应用在非线性可分数据集上的一种修改。但是如果两种算法都应用在线性可分的数据集上，Packet Algorithm的效率会低一些，因为它在每次迭代中都需要计算当前情况下所有的误分类点的个数，而原始感知机算法在每次迭代中只关注一个误分类点。