Question

5.1 定义

1. 感知机是二分类的线性分类模型，属于判别模型。

   • 模型的输入为实例的特征向量，模型的输出为实例的类别：正类取值 +1, 负类取值 -1 。
   • 感知机的物理意义：将输入空间（特征空间）划分为正、负两类的分离超平面。

2. 设输入空间（特征空间）为 $ MathJax-Element-224 $ ；输出空间为 $ MathJax-Element-225 $ ；输入 $ MathJax-Element-226 $ 为特征空间的点；输出 $ MathJax-Element-227 $ 为实例的类别。

   定义函数 $ MathJax-Element-228 $ 为感知机。其中：

   • $ MathJax-Element-229 $ 为权值向量， $ MathJax-Element-230 $ 为偏置。它们为感知机的参数。
   • sign 为符号函数：
   $ sign(x)=\begin{cases} +1, & x \ge 0 \\ -1, & x \lt 0 \end{cases} $

3. 感知机的几何解释： $ MathJax-Element-243 $ 对应特征空间 $ MathJax-Element-232 $ 上的一个超平面 $ MathJax-Element-287 $ ，称作分离超平面。

   • $ MathJax-Element-234 $ 是超平面 $ MathJax-Element-287 $ 的法向量， $ MathJax-Element-236 $ 是超平面的截距。

   • 超平面 $ MathJax-Element-287 $ 将特征空间划分为两个部分：

     • 超平面 $ MathJax-Element-287 $ 上方的点判别为正类。
     • 超平面 $ MathJax-Element-287 $ 下方的点判别为负类。

5.2 损失函数

1. 给定数据集 $ MathJax-Element-240 $ ，其中 $ MathJax-Element-241 $ 。

   若存在某个超平面 $ MathJax-Element-287 $ ： $ MathJax-Element-243 $ ， 使得将数据集中的正实例点与负实例点完全正确地划分到超平面的两侧，则称数据集 $ MathJax-Element-317 $ 为线性可分数据集；否则称数据集 $ MathJax-Element-317 $ 线性不可分。

   划分到超平面两侧，用数学语言描述为： $ MathJax-Element-246 $
   

2. 根据感知机的定义：

   • 对正确分类的点 $ MathJax-Element-314 $ ，有 $ MathJax-Element-248 $
     
   • 对误分类的点 $ MathJax-Element-314 $ ，有 $ MathJax-Element-250 $

3. 如果将感知机的损失函数定义成误分类点的中总数，则它不是 $ MathJax-Element-251 $ 的连续可导函数，不容易优化。

   因此，定义感知机的损失函数为误分类点到超平面 $ MathJax-Element-287 $ 的总距离。

   对误分类的点 $ MathJax-Element-314 $ ，则 $ MathJax-Element-254 $ 距离超平面的距离为：

   $ \frac{1}{||\mathbf {\vec w}||_2}|\mathbf {\vec w} \cdot\mathbf {\vec x}_i +b| $

   由于 $ MathJax-Element-255 $ ，以及 $ MathJax-Element-256 $ ，因此上式等于

   $ \frac{- \tilde y_i(\mathbf {\vec w} \cdot\mathbf {\vec x}_i +b)}{||\mathbf {\vec w}||_2} $

   不考虑 $ MathJax-Element-262 $ ，则得到感知机学习的损失函数：

   $ L(\mathbf {\vec w},b)=-\sum_{\mathbf {\vec x}_i \in \mathbb M}\tilde y_i(\mathbf {\vec w} \cdot\mathbf {\vec x}_i +b) $

   其中：

   • $ MathJax-Element-272 $ 为误分类点的集合。它隐式的与 $ MathJax-Element-307 $ 相关，因为 $ MathJax-Element-307 $ 优化导致误分类点减少从而使得 $ MathJax-Element-261 $ 收缩。
   • 之所以不考虑 $ MathJax-Element-262 $ ，因为感知机要求训练集线性可分，最终误分类点数量为零，此时损失函数为零。即使考虑分母，也是零。若训练集线性不可分，则感知机算法无法收敛。
   • 误分类点越少或者误分类点距离超平面 $ MathJax-Element-287 $ 越近， 则损失函数 $ MathJax-Element-264 $ 越小。

4. 对于特定的样本点，其损失为：

   • 若正确分类，则损失为 0 。
   • 若误分类，则损失为 $ MathJax-Element-307 $ 的线性函数。

   因此给定训练集 $ MathJax-Element-317 $ ，损失函数 $ MathJax-Element-267 $ 是 $ MathJax-Element-307 $ 的连续可导函数。

5.3 学习算法

1. 给定训练集 $ MathJax-Element-295 $ ，求参数 $ MathJax-Element-307 $ ：

   $ MathJax-Element-271 $ 。

5.3.1 原始形式

1. 假设误分类点集合 $ MathJax-Element-272 $ 是固定的，则损失函数 $ MathJax-Element-277 $ 的梯度为：

   $ \nabla_\mathbf {\vec w} L(\mathbf {\vec w},b)=- \sum_{\mathbf {\vec x}_i \in \mathbb M}\tilde y_i \mathbf {\vec x}_i \\ \nabla_b L(\mathbf {\vec w},b)=-\sum_{\mathbf {\vec x}_i \in\mathbb M}\tilde y_i $

2. 通过梯度下降法，随机选取一个误分类点 $ MathJax-Element-314 $ ，对 $ MathJax-Element-307 $ 进行更新：

   $ \mathbf {\vec w} \leftarrow \mathbf {\vec w}+\eta\tilde y_i\mathbf {\vec x}_i \\ b \leftarrow b+\eta\tilde y_i $

   其中 $ MathJax-Element-309 $ 是步长，即学习率。

   通过迭代可以使得损失函数 $ MathJax-Element-277 $ 不断减小直到 0 。

3. 感知机学习算法的原始形式：

   • 输入：

     • 线性可分训练集 $ MathJax-Element-308 $
     • 学习率 $ MathJax-Element-309 $
       

   • 输出：

     • $ MathJax-Element-280 $
       
     • 感知机模型： $ MathJax-Element-281 $

   • 步骤：

     • 选取初始值 $ MathJax-Element-306 $ 。

     • 在训练集中选取数据 $ MathJax-Element-286 $ 。若 $ MathJax-Element-284 $ 则：

       $ \mathbf {\vec w} \leftarrow \mathbf {\vec w}+\eta\tilde y_i\mathbf {\vec x}_i \\ b \leftarrow b+\eta \tilde y_i $

     • 在训练集中重复选取数据来更新 $ MathJax-Element-307 $ 直到训练集中没有误分类点。

5.3.2 性质

1. 对于某个误分类点 $ MathJax-Element-286 $ ，假设它被选中用于更新参数。

   • 假设迭代之前，分类超平面为 $ MathJax-Element-287 $ ，该误分类点距超平面的距离为 $ MathJax-Element-288 $ 。
   • 假设迭代之后，分类超平面为 $ MathJax-Element-289 $ ，该误分类点距超平面的距离为 $ MathJax-Element-290 $ 。

   则：

   $ \Delta d=d'-d=\frac{1}{||\mathbf {\vec w}^{\prime}||_2}|\mathbf {\vec w}^{\prime} \cdot\mathbf {\vec x}_i+b'|-\frac{1}{||\mathbf {\vec w}||_2}|\mathbf {\vec w} \cdot\mathbf {\vec x}_i+b| \\ =-\frac{1}{||\mathbf {\vec w}^{\prime}||_2}\tilde y_i(\mathbf {\vec w}^{\prime} \cdot\mathbf {\vec x}_i+b')+\frac{1}{||\mathbf {\vec w}||_2}\tilde y_i(\mathbf {\vec w} \cdot\mathbf {\vec x}_i+b)\\ \simeq -\frac{\tilde y_i}{||\mathbf {\vec w}||_2}[(\mathbf {\vec w}^{\prime}-\mathbf {\vec w})\cdot \mathbf {\vec x}_i +(b'-b)]\\ =-\frac{\tilde y_i}{||\mathbf {\vec w}||}[\eta \tilde y_i \mathbf {\vec x}_i\cdot \mathbf {\vec x}_i +\eta \tilde y_i]\\ =-\frac{\tilde y_i^{2}}{||\mathbf {\vec w}||_2}(\eta \mathbf {\vec x}_i \cdot \mathbf {\vec x}_i +1) \lt 0 $

   因此有 $ MathJax-Element-291 $ 。

   这里要求 $ MathJax-Element-292 $ ，因此步长 $ MathJax-Element-293 $ 要相当小。

2. 几何解释 ：当一个实例点被误分类时，调整 $ MathJax-Element-307 $ 使得分离平面向该误分类点的一侧移动，以减少该误分类点与超平面间的距离，直至超平面越过所有的误分类点以正确分类。

3. 感知机学习算法由于采用不同的初值或者误分类点选取顺序的不同，最终解可以不同。

5.3.3 收敛性

1. 感知机收敛性定理：设线性可分训练集 $ MathJax-Element-295 $ 。

   • 存在满足 $ MathJax-Element-296 $ 的超平面： $ MathJax-Element-297 $ ，该超平面将 $ MathJax-Element-304 $ 完全正确分开。

     且存在 $ MathJax-Element-299 $ ，对所有的 $ MathJax-Element-300 $ 有： $ MathJax-Element-301 $ 。

     其中 $ MathJax-Element-302 $ 。

   • 令 $ MathJax-Element-303 $ ，则感知机学习算法原始形式在 $ MathJax-Element-304 $ 上的误分类次数 $ MathJax-Element-305 $ 满足：

     $ k \le (\frac {R}{r})^{2} $

2. 感知机收敛性定理说明了：

   • 当训练集线性可分时，感知机学习算法原始形式迭代是收敛的。

     • 此时算法存在许多解，既依赖于初值，又依赖于误分类点的选择顺序。
     • 为了得出唯一超平面，需要对分离超平面增加约束条件。

   • 当训练集线性不可分时，感知机学习算法不收敛，迭代结果会发生震荡。

5.3.4 对偶形式

1. 根据原始迭代形式 ：

   $ \mathbf {\vec w} \leftarrow \mathbf {\vec w}+\eta\tilde y_i\mathbf {\vec x}_i \\ b \leftarrow b+\eta\tilde y_i $

   取初始值 $ MathJax-Element-306 $ 均为 0。则 $ MathJax-Element-307 $ 可以改写为：

   $ \mathbf {\vec w}=\sum_{i=1}^{N} \alpha_i \tilde y_i \mathbf {\vec x}_i\\ b=\sum_{i=1}^{N} \alpha_i \tilde y_i $

   这就是感知机学习算法的对偶形式。

2. 感知机学习算法的对偶形式：

   • 输入：

     • 线性可分训练集 $ MathJax-Element-308 $
     • 学习率 $ MathJax-Element-309 $
       

   • 输出：

     • $ MathJax-Element-310 $ ，其中 $ MathJax-Element-311 $ 。
     • 感知机模型 $ MathJax-Element-312 $ 。

   • 步骤：

     • 初始化： $ MathJax-Element-313 $ 。
     • 在训练集中随机选取数据 $ MathJax-Element-314 $ ，若 $ MathJax-Element-315 $ 则更新：
     $ \alpha_i \leftarrow \alpha_i+\eta\\ b \leftarrow b+\eta \tilde y_i $
     • 在训练集中重复选取数据来更新 $ MathJax-Element-316 $ 直到训练集中没有误分类点。

3. 在对偶形式中， 训练集 $ MathJax-Element-317 $ 仅仅以内积的形式出现，因为算法只需要内积信息。

   可以预先将 $ MathJax-Element-318 $ 中的实例间的内积计算出来，并以矩阵形式存储。即 Gram矩阵： $ MathJax-Element-319 $

4. 与原始形式一样，感知机学习算法的对偶形式也是收敛的，且存在多个解。