李航老师的《统计学习方法》感知机部分的读书笔记（xyy 要努力做一个日更博主！！）

0. Intro

感知机可以理解 为将实例划分为正负两类的分离超平面，是二分类的线性分类模型。

用一个很简单的二维的例子来形容就是，在一个分布着红色实例和绿色实例的二维空间里，其中两种颜色的实例线性可分（可以用一条直线将两类实例完全区分开）。在这种情况下，蓝色线（二维空间的超平面是一维的直线）就是感知机。

image-20210427163206496

  • 输入为特征向量，输出为实例的类别（取 +1 和 -1 二值）。

  • 具有简单、易于实现的优点

  • 分为原始形式、对偶形式。


1. 感知机模型简介

定义（感知机）：假设输入空间是 $\chi \in R^n$，输出空间是 $y = {+1, -1}$。输入 $x \in \chi$ 表示实例的特征向量，对应于输入空间。

则感知机的由输入空间到输出空间的映射函数为：$f(x) = sign(w*x+b)$

其中，$w$ 和 $b$ 为感知机参数，$w \in R^n$ 叫做权值向量，$b \in R$ 叫做偏置。

$sign$ 为符号函数，即：$sign = \begin{cases} +1 &\text{x >=0} \\-1 &\text{x<0} \end{cases}$

感知机的几何解释：

线性方程 $w*x+b=0$ 对应于特征空间 $R^n$ 中的一个超平面 S，其中 w 是超平面的法向量，b 是超平面的截距。


2. 感知机的学习策略

2.1 线性可分介绍

定义（数据集的线性可分性）：给定一个数据集 $T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$，其中 $x_i \in R^n$，$y_i \in {+1, -1}$，$i=1,2…,N$。如果存在某个超平面 $S$ 能将数据集的正实例点和负实例点完全正确地划分到超平面地两侧，则称数据集具有线性可分性。（即对所有 $y_i = +1$ 的实例 $i$，有 $wx_i+b>0$；对所有 $y_i=-1$ 的实例 $i$，有 $wx_i+b<0$）

假设训练数据集是线性可分的，感知机学习的目标是求得一个能够将训练集正实例点和负实例点完全正确分开的分离超平面。为此需要确定一个学习策略（损失函数）来确定优秀的感知机模型参数 $w$ 和 $b$。
`

2.2 感知机的损失函数推导：

感知机采用的损失函数原理为： 误分类点到超平面 $S$ 的总距离。

  1. 先写出输入空间 $R^n$ 中任一点 $x_0$ 到超平面 $S$ 的距离：$\frac{1}{||w||} |w*x_0+b|$ （此处 $||w||$ 为 $w$ 的 $L_2$ 范数）

  2. 其次，对于误分类的点来说，$-y_i(w*x+b)>=0$

  3. 所以，误分类点 $x_i$ 到超平面 $S$ 的距离是：$-\frac{1}{||w||}y_i(w*x_i+b)$

  4. 因此，感知机的损失函数为所有误分类点到超平面 $S$ 的总距离：$-\frac{1}{||w||}\sum_{x_i \in M} y_i(w*x_i+b)$

不考虑 $\frac{1}{||w||}$，结果为 $L(w,b)=-\sum_{x_i \in M}y_i(w*x_i+b)$

补充介绍 函数间距 和 几何间距 ：

可能大家对 $|w*x_0+b|$ （函数间距）比较熟悉，但是函数间距存在一定的问题。我们引入损失函数的目的是唯一地衡量超平面的划分性能，因此，固定的超平面应该拥有唯一的 Loss。但是聪明的感知机发现，如果等比例地缩小 $w$ 和 $b$，可以轻而易举地降低 Loss。但是，超平面却没有改变！

因此引入了$\frac{1}{||w||} |w*x_0+b|$（几何间距），拥有等比例的感知机参数将拥有相同的 Loss


3. 感知机学习算法（原始形式）

原始形式的感知机学习过程可以分为三步：

  1. 随机选取感知机模型参数初值 $w_0$，$b_0$

  2. 采用梯度下降法极小化目标函数

$L(w,b)=-\sum_{x_i \in M}y_i(w*x_i+b)$

$\nabla_w L(w,b)=-\sum_{x_i \in M} y_ix_i$

$\nabla_b L(w,b)=-\sum_{x_i \in M} y_i$

  1. 更新 $w$，$b$ （此处 $\eta$ 为步长，也称学习率）

$w \leftarrow w + \eta y_i x_i$

$b \leftarrow b + \eta y_i$


4. 感知机学习算法（对偶形式）

4.1 对偶形式介绍

我们知道在原始形式中，感知机模型参数 $w$ 和 $b$ 的每一次迭代为：$w \leftarrow w + \eta y_i x_i$ 和 $b \leftarrow b + \eta y_i$。

那我们整合 n 次迭代，可以得到 $w$ 和 $b$ 关于 $(x_i, y_i)$ 的增量分别是 $\alpha_i y_i x_i$ 和 $\alpha_i y_i$ （为了简洁 $\alpha$ 在这里视作一个新的常量，为 $n_i \eta$）

所以最后学习到的就是：$w = \sum_{i=1}^{N} \alpha_i y_i x_i$ 和 $b = \sum_{i=1}^{N} \alpha_i y_i$

然后将上式代入感知机的输入空间至输出空间的映射关系 $f(x)=sign(w*x+b)$ 得到 $f(x)=sign(\sum_{j=1}^{N} \alpha_jy_jx_j * x + b)$

至此我们得到了感知机学习的对偶模式的学习算法。

4.2 对偶模式学习步骤

对偶模式学习步骤总体和传统模型相近：

  1. 选取感知机模型参数初值 $\alpha_0 = 0$，$b_0 = 0$

    【注意对比传统模式】传统模式的参数初值是随机选取。这里因为 $\alpha$ 具有涵义 $n_i \eta$，而初始情况下是不知道有无误分类点，因此取 0

  2. 在训练集选取数据 $(x_i, y_i)$

  3. 如果（误分类）$y_i (\sum_{j=1}^{N} \alpha_j y_j x_j* x_i + b) \leq 0$

    更新 $w$，$b$ ：$\alpha_i \leftarrow \alpha_i + \eta$ 和 $b \leftarrow b + \eta y_i$

  4. 转至 2 直到没有误分类点

4.3 WHY 对偶模式？

我们先将两种模式的参数更新表达式单独列出：

模式 参数1 参数2 映射关系
传统模式 $w \leftarrow w + \eta y_i x_i$ $b \leftarrow b + \eta y_i$ $f(x)=sign(w*x+b)$
对偶模式 $\alpha_i \leftarrow \alpha_i + \eta$ $b \leftarrow b + \eta y_i$ $f(x)=sign(\sum_{j=1}^{N} \alpha_jy_jx_j * x + b)$

我们可以比较容易地看出在传统模式下，每次迭代参数 $w$ 都需计算一遍内积 $y_i x_i$，在计算映射关系时同样也需要计算内积 $w*x$

但是在对偶模式下，参数的迭代只是简单的加法运算，映射关系虽然需要计算内积 $x_j * x_i$ ，但是我们利用 Gram矩阵 可以较好地解决。因此大大减少了计算量。

【Gram矩阵】定义式为：$G = [x_i * x_j]_{N*N}$，在此处的用途是，可以将一系列的内积 $x_i * x_j$ 提前计算好，在执行映射关系计算的时候，仅需要查表，将时间复杂度降到 O(1)


5. 算法的收敛性

为了便于叙述和推导，将偏置 $b$ 并入权重向量 $w$，记作 $\hat w = (w^T,b)^T$ 。同样也将输入向量加以扩充，加入常数1，记作 $\hat x = (x^T, 1)^T$

我们讨论收敛性的目的是为了证明在训练集线性可分的情况下，误分类次数 $k$ 是由上限的。换句话说就是经过有限次搜索，可以找到将训练集完全正确分开的分离超平面。当训练集线性不可分的时候，感知机学习算法不收敛，迭代结果会发生震荡。

5.1 两个不等式证明

  • 不等式1：$\hat w_k * \hat w_{opt} \geq k \eta \gamma$

    $\hat w_k * \hat w_{opt} = \hat w_{k-1} * \hat w_{opt} + \eta y_i \hat w_{opt} * \hat x_i \geq \hat w_{k-1} * \hat w_{opt} + \eta \gamma$

    由此递推可得 $\hat w_k * \hat w_{opt} \geq \hat w_{k-1}* \hat w_{opt} + \eta \gamma \geq \hat w_{k-2}* \hat w_{opt} + 2\eta \gamma \geq … \geq k \eta \gamma$

  • 不等式2：$||\hat w_k||^2 \leq k \eta^2R^2$

    $||\hat w_k||^2 = ||\hat w_{k-1}||^2 + 2\eta y_i \hat w_{k-1} * \hat x_i + \eta^2||\hat x_i||^2$

    $\leq ||\hat w_{k-1}||^2 + \eta^2||\hat x_i||^2$

    $\leq ||\hat w_{k-1}||^2 + \eta^2R^2$

    $\leq ||\hat w_{k-2}||^2 + 2\eta^2R^2$

    $\leq k \eta^2R^2$

5.2 Novikoff 定理

定理（Novikoff）：设训练数据集 $T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$ 是线性可分的，其中 $x_i \in \chi = R^n$，$y_i \in {+1, -1}$，$i=1,2,…,N$，则：

  1. 存在满足条件 $||\hat w_{opt}||=1$ 的超平面 $\hat w_{opt} \hat x = w_{opt} x + b_{opt} = 0$ 将训练数据集完全分开；
    且存在 $\gamma > 0$，对所有 $i=1,2,…,N$ 有 $y_i(\hat w_{opt} \hat x_i) = y_i (w_{opt} x_i + b_{opt}) >= \gamma$
  2. 令 $R = max_{1 \leq i \leq N} ||\hat x_i||$，则感知机算法在训练数据集上的误分类次数 $k$ 满足不等式 $k \leq (\frac{R}{\gamma})^2$

Novikoff 定理主要为感知机在理论上的可行性做了证明，误分类次数具有优先上限，意味着在训练集线性可分的情况下，感知机通过有限次迭代参数，最终可以完全分类。

接下来进行证明：

  1. 由于假定了前提条件训练集是线性可分的

    因此，设将训练数据集完全正确分开的超平面为 $\hat w_{opt} \hat x = w_{opt} x + b_{opt} = 0$，使 $||\hat w_{opt}|| = 1$

    由于对 $i = 1,2,..,N$ 均有 $y_i (\hat w_{opt} \hat x_i) = y_i (w_{opt} x_i + b_{opt}) > 0$

    所以必定存在 $\gamma = min_i {y_i (w_{opt} x_i + b_{opt})}$ 使 $y_i (\hat w_{opt} \hat x_i) = y_i(w_{opt} x_i + b_{opt}) \geq \gamma$

  2. 令 $\hat w_{k-1}$ 是第 $k$ 个误分类实例之前的扩充权重向量，即 $\hat w_{k-1} = (w_{k-1}^{T}, b_{k-1})^T$

    则第 $k$ 个误分类实例的条件是 $y_i (\hat w_{k-1} \hat x_i) = y_i (w_{k-1} x_i + b_{k-1}) \leq 0$

    $w$ 和 $b$ 的更新为 $w_k \leftarrow w_{k-1} + \eta y_i x_i$ 和 $b_k \leftarrow b_{k-1}+\eta y_i$

    借助上节推导的两个不等式可得：

    $k \eta \gamma \leq \hat w_k * \hat w_{opt} \leq ||\hat w_k||||\hat w_{opt}|| \leq \sqrt{k}\eta R$

    等价于$k^2 \gamma^2 \leq kR^2$

    所以可得 $k \leq (\frac{R}{\gamma})^2$


总结

感知机通过构造超平面对实例点进行分类（二分类），其中构造的超平面依赖于感知机参数 $w$ 和 $b$，两者在每一个误分类点处使用梯度下降的方法进行迭代更新。

但是，感知机起作用有一个很强的前提：训练集是线性可分的（或者说，判别边界是线性的），只有在这个前提下才能训练出完全划分的感知机，不然在迭代参数的时候会震荡。