感知机（Perceptron）是一种基本的线性二分类模型，输入为实例的特征向量，输出为实例的类别，具体为 +1 或 -1 的二值。该模型在输入空间（特征空间）中构造一个分离超平面来区分正负两类实例，属于判别模型。感知机学习的目标是找到一个能够将训练数据线性划分的超平面，为此，它采用基于误分类的损失函数，并通过梯度下降法来最小化这一损失函数，进而确定感知机模型的参数。感知机学习算法不仅简单而且易于实现，包括原始形式和对偶形式。感知机模型利用所学习的参数对新输入实例进行分类。感知机由Rosenblatt在1957年提出，它为神经网络和支持向量机的发展奠定了基础。
本章节首先阐述感知机模型的基本概念；随后详细描述感知机的学习策略，尤其是损失函数的形式；最后介绍感知机学习算法。
Pod 5.1 感知机模型
感知机模型定义：假定输入空间（特征空间）为 \mathcal{X} \subseteq \mathbb{R}^{n} ，输出空间为 \mathcal{Y}=\{+1,-1\} 。输入 x \in \mathcal{X} 表示实例的特征向量，相应于特征空间中的点；输出 y \in \mathcal{Y} 表示实例的类别。由输入空间到输出空间的映射函数
f(x) = \text{sign}(w \cdot x + b)定义为感知机。这里， w 和 b 是感知机模型的参数， w \in \mathbb{R}^{n} 称为权重（weight）或权重向量（weight vector）， b \in \mathbb{R} 称为偏置（bias）， w \cdot x 代表 w 和 x 的内积。符号函数 \text{sign} 定义如下：
\text{sign}(x) = \begin{cases} +1, & x \geq 0 \\ -1, & x < 0 \end{cases}感知机是线性分类模型的一个典型代表，属于判别模型类别。其模型假设空间包含了所有可能的线性分类器，即所有的 \{f \mid f(x) = w \cdot x + b\} 形式的函数集合。
感知机模型还有一个直观的几何解释：线性方程 w \cdot x + b = 0 对应于 \mathbb{R}^{n} 特征空间中的一个分离超平面 S ，其中向量 w 是该超平面的法向量，而常数 b 为超平面的截距。该超平面将特征空间划分为两个部分，位于超平面两侧的点（特征向量）分别属于正类或负类。因此，这个超平面 S 被称为分离超平面。
感知机学习过程基于一个训练数据集，该数据集包含实例的特征向量及其对应的类别标签：
T = \{(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)\}其中 x_i \in \mathcal{X} = \mathbb{R}^{n} ， y_i \in \mathcal{Y} = \{+1,-1\} ， i = 1, 2, \cdots, N 。通过训练数据，感知机学习的目标是求解模型参数 w, b ，从而得到感知机模型。利用学习到的感知机模型，可以对新的输入实例进行分类，预测其可能的输出类别。
Pod 5.2 感知机学习策略
Pod 5.2.1 数据集的线性可分性
数据集的线性可分性定义：对于给定的数据集
T = \{(x_{1}, y_{1}), (x_{2}, y_{2}), \ldots, (x_{N}, y_{N})\}其中 x_{i} \in \mathcal{X}=\mathbb{R}^{n}, y_{i} \in \mathcal{Y}=\{+1,-1\}, i=1,2,\ldots,N, 如果存在某个超平面 S:
w \cdot x + b = 0能够正确地将数据集中的正实例和负实例归类到超平面的两侧，即所有 y_{i} = +1 的实例 i 满足 w \cdot x_{i} + b > 0，而所有 y_{i} = -1 的实例 i 满足 w \cdot x_{i} + b < 0，则称数据集 T 为线性可分数据集（linearly separable data set）；反之，则称数据集 T 线性不可分。
Pod 5.2.2 感知机学习策略
假定训练数据集是线性可分的，感知机学习的目的是寻找一个分离超平面，它能将训练集中的正负实例完全正确地划分到超平面的两侧。为了实现这一目标，即为了确定感知机模型的参数 w 和 b，需要设定一个学习策略，包括定义一个（经验）损失函数并最小化这一损失。
虽然误分类的总数是一个直观的损失函数选择，但它不是参数 w, b 的连续可导函数，因而不便于优化。感知机采用的是另一种损失函数，即误分类点到分离超平面 S 的总距离。首先，任意点 x_0 到超平面 S 的距离可以表示为：
\frac{1}{\|w\|} |w \cdot x_0 + b|这里，\|w\| 表示 w 的 L_2 范数。
对于误分类数据点 (x_i, y_i)，以下条件始终成立：
-y_i(w \cdot x_i + b) > 0这是因为当 w \cdot x_i + b > 0 时，y_i 应该是 -1，反之，当 w \cdot x_i + b < 0 时，y_i 应该是 +1。因此，一个误分类点 x_i 到超平面 S 的距离为：
-\frac{1}{\|w\|} y_i(w \cdot x_i + b)假设 M 代表所有误分类点的集合，那么所有误分类点到超平面 S 的总距离是：
-\frac{1}{\|w\|} \sum_{x_i \in M} y_i(w \cdot x_i + b)忽略常数 \frac{1}{\|w\|} 后，我们得到感知机的损失函数。
给定训练数据集 T，感知机 \text{sign}(w \cdot x + b) 的学习损失函数定义为：
L(w, b) = -\sum_{x_i \in M} y_i(w \cdot x_i + b)这里的 M 是误分类点的集合，损失函数 L(w, b) 代表了感知机学习的经验风险。
损失函数 L(w, b) 是非负的，当不存在误分类点时其值为零。误分类点越少，且距离超平面越近，损失函数的值就越小。对于任一特定样本点，当其被误分类时损失函数是参数 w, b 的线性函数，在正确分类时损失函数为零。因此，对于给定的训练数据集 T，损失函数 L(w, b) 是 w, b 的连续可导函数。
感知机学习的目标是在假设空间中选取使经验风险 L(w, b) 最小化的模型参数 w, b，即确定感知机模型。
Pod 5.3 感知机学习算法
感知机的学习问题可以转化为求解损失函数的最优化问题，其中最优化方法通常采用随机梯度下降法。
感知机学习算法旨在解决以下优化问题：给定训练数据集
T=\{(x_{1}, y_{1}), (x_{2}, y_{2}), \ldots, (x_{N}, y_{N})\}其中 x_{i} \in \mathcal{X}=\mathbb{R}^{n}, y_{i} \in \mathcal{Y}=\{-1,+1\}, i=1,2,\ldots,N，目标是找到参数 w, b，使得损失函数达到最小：
\min_{w, b} L(w, b) = -\sum_{x_{i} \in M} y_{i}(w \cdot x_{i} + b)这里 M 是误分类点的集合。
感知机学习算法是基于误分类的驱动策略，特别是采用随机梯度下降法（stochastic gradient descent）。从任意选取的初始超平面 w_{0}, b_{0} 开始，算法通过梯度下降法不断地减小目标函数的值。在这个过程中，并不是一次性对所有误分类点进行梯度下降，而是随机选取一个误分类点来更新梯度。
如果误分类点集合 M 是固定的，那么损失函数 L(w, b) 的梯度可以由下式给出：
\begin{aligned} \nabla_{w} L(w, b) &= -\sum_{x_{i} \in M} y_{i} x_{i} \\ \nabla_{b} L(w, b) &= -\sum_{x_{i} \in M} y_{i} \end{aligned}随机选择一个误分类点 (x_{i}, y_{i})，然后更新 w 和 b：
\begin{aligned} w &\leftarrow w + \eta y_{i} x_{i} \\ b &\leftarrow b + \eta y_{i} \end{aligned}其中 \eta (0 < \eta \leq 1) 是步长，也被称作学习率（learning rate）。通过迭代，我们希望损失函数 L(w, b) 不断减少，直到降为零。
综上所述，我们得到以下算法：
输入: 训练数据集 T=\{(x_{1}, y_{1}), (x_{2}, y_{2}), \ldots, (x_{N}, y_{N})\}，其中 x_{i} \in \mathcal{X}=\mathbb{R}^{n}, y_{i} \in \mathcal{Y}=\{-1,+1\}, i=1,2,\ldots,N；学习率 \eta (0 < \eta \leq 1)。
输出: w, b；感知机模型 f(x) = \text{sign}(w \cdot x + b)。
1. 初始化权重 w_{0} 和偏置 b_{0}。
2. 从训练集中选取数据点 (x_{i}, y_{i})。
3. 如果 y_{i}(w \cdot x_{i} + b) \leq 0，则更新 w 和 b：
4. 重复步骤2和3，直到训练集中没有误分类点。
此算法的直观解释是：当一个实例点被误分类，即位于分离超平面的错误一侧时，调整 w 和 b 的值，使分离超平面朝着该误分类点的方向移动，减小该点与超平面之间的距离，直至超平面越过该点，使其被正确分类。
