本文介绍了模式识别的线性分类器，包括线性分类器的基础概念、垂直平分准则以及垂直平分分类器、Fisher 投影准则、感知准则、最小错分样本准则、最小平方误差准则、最小二乘估计。
1. 引言
模式识别的目的是在特征空间中设法找到两类（或多类）之间的分界面。一方面，我们可以通过估计样本的概率模型，然后采用贝叶斯决策（最大后验估计）或者最大似然估计的策略来实现分类。但是很多情况下，建立样本的概率模型和准确估计样本的概率密度函数及其他模型参数并不是一件容易的事情。
实际上，估计概率密度函数也不是我们的目的。贝叶斯决策的策略分为两步，首先根据样本进行概率密度函数估计，然后再根据估计的概率密度函数求分类面。如果能直接根据样本求分类面，就可以省略对概率密度函数的估计。我们知道，当样本为正态分布且各类协方差矩阵相等的条件下，贝叶斯决策的最优分类面是线性的，二分类问题的判别函数形式为 $g(x) = \boldsymbol{w}^\top\boldsymbol{x} + w_0$。那么如果我们知道判别函数的形式，可以设法从数据中直接估计这种判别函数的参数，这就是基于样本直接进行分类器设计的思想。进一步，即使不知道最优的判别函数是什么形式，仍然可以根据需要或对问题的理解设定判别函数类型，从数据直接求解判别函数。
线性分类器是一种基于样本直接设计的分类器。采用不同的准则及不同的寻优算法就得到不同的线性判别方法。
2. 线性分类器基础
2.1. 线性判别函数
模式识别的目的就是在样本特征空间中寻找两类或多类之间的分界面（决策边界），从而实现对不同模式的分类。
- 【决策面】在样本特征空间中，将不同种类样本区分开的决策边界也叫决策面或分类面。
- 【判别函数】用数学形式描述决策面的函数就是判别函数。
- 【超平面】使用线性判别函数描述的决策面是线性的，在低维空间中表现为点、线、面的形式，在高维空间中则称为超平面。
- 【线性分类器】这样的线性决策面构成的分类器称作线性分类器。
注意到，特征空间种的决策面可以是线性的，可以是非线性的。只有采用线性决策面的分类器称作线性分类器。
在 $n$ 维特征空间种，特征向量表示为 $\boldsymbol{x} = [x_1, x_2, \cdots, x_n]^{\text{T}}$，则线性判别函数一般形式为
\[g(\boldsymbol{x}) = \boldsymbol{w}^{\text{T}}\boldsymbol{x} + w_0 = w_1x_1 + w_2x_2 + \cdots + w_nx_n + w_0\]其中 $w_0$ 为阈值权，$w_1, w_2, \cdots, w_n$ 为加权因子。
在二分类问题中，分别用 $\omega_1$ 和 $\omega_2$ 表示两类，采用上述线性判别函数进行分类，对应的判别规则为
\[\begin{cases} \boldsymbol{x}\in\omega_1 & g(\boldsymbol{x}) > 0 \\ \boldsymbol{x}\in\omega_2 & g(\boldsymbol{x}) < 0 \end{cases}\]决策面方程为
\(\boldsymbol{w}^{\text{T}}\boldsymbol{x} + w_0 = 0\)
线性判别函数有如下几个几何性质：
- 法向量方向为 $\boldsymbol{w}$ 设决策面上任意两个点 $\boldsymbol{x}_1$ 和 $\boldsymbol{x}_2$，它们满足 $g(\boldsymbol{x}_1) = g(\boldsymbol{x}_2) = 0$，两式相减得 $\boldsymbol{w}^{\text{T}}(\boldsymbol{x}_1 - \boldsymbol{x}_2) = 0$，而$\boldsymbol{x}_1 - \boldsymbol{x}_2$ 构成了决策面上的任意向量，因此决策面与 $\boldsymbol{w}$ 垂直
- 样本 $\boldsymbol{x}$ 到决策面的欧氏距离为 \(e=\frac{\vert\boldsymbol{w}^{\text{T}}\boldsymbol{x} + w_0\vert}{\sqrt{w_1^2 + w_2^2 + \cdots + w_n^2}}=\frac{\vert\boldsymbol{w}^{\text{T}}\boldsymbol{x} + w_0\vert}{\Vert \boldsymbol{w} \Vert}\)
- 原点（一个坐标全 0 的特殊样本点）到决策面的欧氏距离为 \(d=\frac{\vert w_0\vert}{\sqrt{w_1^2 + w_2^2 + \cdots + w_n^2}}=\frac{\vert w_0\vert}{\Vert \boldsymbol{w} \Vert}\)
2.2. 广义线性判别函数
上述线性判别函数是一个一般的点/线/超平面，为了简化设计和计算，我们可以将其平移至原点，从而得到广义线性判别函数。
首先定义如下增广样本向量 $\boldsymbol{y}$ 和增广权向量 $\boldsymbol{a}$
\[\begin{aligned} \boldsymbol{y} &= [1, x_1, x_2, \cdots, x_n]^{\text{T}}\\ \boldsymbol{a} &= [w_0, w_1, w_2, \cdots, w_n]^{\text{T}} \end{aligned}\]则广义线性判别函数为
\[g(\boldsymbol{y}) = \boldsymbol{a}^{\text{T}}\boldsymbol{y} = w_0 + w_1x_1 + w_2x_2 + \cdots + w_nx_n\]对应的决策面为
\[\boldsymbol{a}^{\text{T}}\boldsymbol{y} = 0\]$g(\boldsymbol{y})$ 在增广特征向量所在的增广特征空间 $\boldsymbol{Y}$ 确定了一个过原点的超平面，在设计某些线性分类器时，过原点的超平面便于求解和计算。增广的 $\boldsymbol{Y}$ 特征空间比原始的 $x\boldsymbol{X}$ 特征空间维数增加了一维，但样本间的欧氏距离保持不变，且不影响分类器的优化设计。
2.3. 二分类与多分类
分类问题是模式识别的基本问题。多类分类问题可以通过两种典型做法分解成若干个二分类问题，这样就可以通过组合多个二分类器、采用多个线性判别函数进行分类：
- 一对其余，在训练时依次把某个类别的样本归为一类，其他剩余的样本归为另一类，也就是把多类样本转化为类与“类的非”这两类。
- 一对一，对多个类别中每两个类别进行分类。
2.4. 线性分类器设计的基本思路
- 给定类别已知的样本——训练样本集
- 选择一个准则函数 $J$，其值反映分类器性能（分类结果优劣）
- 采用求最优解的数学方法求准则函数 $J$ 的极值解，从而求得权向量 $w$ 和阈值权 $w_0$ ，或增广权向量 $a$
3. 垂直平分准则
3.1. 设计思路
如图，在二维特征向量的二分类问题（$C=2，D=2$）中，垂直平分分类器设计思路是基于两类样本均值点作垂直平分线。根据垂直平分的特性求解其权向量和阈值权的方法如下：
-
利用垂直关系，即分类面与两类均值连线垂直，可计算得到权向量 $\boldsymbol{w}$（参考前面线性判别函数的几何性质）
\[\boldsymbol{w} = \boldsymbol{m}_1 - \boldsymbol{m}_2\]则线性判别函数为
\[g(\boldsymbol{x}) = \boldsymbol{w}^{\text{T}}\boldsymbol{x} + w_0 = (\boldsymbol{m}_1 - \boldsymbol{m}_2)^{\text{T}}\boldsymbol{x} + w_0\] -
利用分类面垂直平分两类均值连线，即两类均值的连线的中点在分类面上，可计算得到阈值权 $w_0$
均值连线的中点为
\[\boldsymbol{x}_0 = \frac{\boldsymbol{m}_1 + \boldsymbol{m}_2}{2}\]代入决策面方程 $g(\boldsymbol{x})=0$ 可求得
\[w_0 = -\frac{1}{2}(\boldsymbol{m}_1 - \boldsymbol{m}_2)^{\text{T}}(\boldsymbol{m}_1 + \boldsymbol{m}_2)\]
最终得到线性判别函数为
\[g(\boldsymbol{x}) = (\boldsymbol{m}_1 - \boldsymbol{m}_2)^{\text{T}}\boldsymbol{x} - \frac{1}{2}(\boldsymbol{m}_1 - \boldsymbol{m}_2)^{\text{T}}(\boldsymbol{m}_1 + \boldsymbol{m}_2)\]决策面方程为
\[g(\boldsymbol{x}) = 0\]垂直平分决策规则为
\[\begin{cases} \boldsymbol{x}\in\omega_1 & g(\boldsymbol{x}) > 0 \\ \boldsymbol{x}\in\omega_2 & g(\boldsymbol{x}) < 0 \end{cases}\]推广到多维特征向量的二分类问题（$C=2，D>2$）时上述形式保持不变。
3.2. 最小距离等价决策
上述的垂直平分决策规则，等价于最小距离等价决策（最小距离分类法），即每个样本到两类均值连线的距离最小的类被判定为该样本所属的类。
定义判别函数为欧氏距离，即
\[\begin{aligned} g_1(\boldsymbol{x}) &= d_1(x) = \Vert \boldsymbol{x} - \boldsymbol{m}_1 \Vert = \sqrt{(\boldsymbol{m}_1 - \boldsymbol{x})^{\text{T}}(\boldsymbol{m}_1 - \boldsymbol{x})} \\ g_2(\boldsymbol{x}) &= d_2(x) = \Vert \boldsymbol{x} - \boldsymbol{m}_2 \Vert = \sqrt{(\boldsymbol{m}_2 - \boldsymbol{x})^{\text{T}}(\boldsymbol{m}_2 - \boldsymbol{x})} \end{aligned}\]那么垂直平分分类器等价的最小距离决策规则为
\[\begin{cases} \boldsymbol{x}\in\omega_1 & g_1(\boldsymbol{x}) < g_2(\boldsymbol{x}) \\ \boldsymbol{x}\in\omega_2 & g_1(\boldsymbol{x}) > g_2(\boldsymbol{x}) \end{cases}\]3.3. 特点总结
垂直平分分类器（最小距离分类器）的主要特点如下：
- 解决二分类问题的线性分类器
- 原则上对样本集无特殊要求
- 未采用准则函数求极值解（非最佳决策）
- 算法最简单，分类器设计最容易
4. Fisher 投影准则
Fisher 投影准则的提出有以下两方面的原因：
- 垂直平分分类器在面对一些样本分布情况时效果不佳（其本身是一个非最佳分类器），如下图左所示；更好的分类器如下图右所示；
![fisher-advantage]()
- 如果分类时所用的特征个数太多，将形成高维特征空间，高维空间不论对分类器的理论设计还是分类器的实际运用，都会带来“灾难性”后果。特征个数越多，计算量就越大，导致分类器设计困难和分类困难。
因此我们可以考虑把所有样本都投影到一个方向上，然后在这个一维空间中确定一个分类的阈值。过这个阈值点且与投影方向垂直的超平面就是两类的分类面。原始的高维空间上的分类问题被转换为一维空间上的分类问题。
在不同方向上投影后，样本在一维坐标轴上的分布不同，有的适合分类，有的不适合分类。因此一维坐标轴的方向不是随意的，需进行优化求解。我们可以从下图中看出，不同的投影方向会使得两类样本的影响该方向的分类结果，左图的投影方向可以使得两类样本较好分开，而按照右图的方向投影后则两类样本混在一起。
Fisher投影准则所要解决的问题就是，如何根据样本集情况，求解最佳的（最易于分类的）投影线方向。Fisher 线性判别的思想就是，选择合适的投影方向，使得投影后两类的间隔尽可能远，同时每一类内部的样本又尽可能聚集。如下图所示。
4.1. 投影
假设二维空间的一个特征向量 $\boldsymbol{x}$，某个投影方向向量为 $\boldsymbol{w}$。假设 $\vert \boldsymbol{w} \vert = 1$（因为只关心投影的方向，不关心长度），那么投影向量为
\[\frac{\boldsymbol{w}^\top\cdot \boldsymbol{x}}{\vert \boldsymbol{w} \vert} = \boldsymbol{w}^\top\boldsymbol{x}\]4.2. Fisher 投影
假设两类样本集，其中第 $w_i$ 类样本集为
\[\mathcal{X}_i=[\boldsymbol{x}_1^i,\cdots, x_{N_i}^i]\in \mathbb{R}^{d\times N_i}\]即特征维度为 $d$，样本个数为 $N_i$。
投影前，原始特征空间中第 $w_i$ 类样本的均值为
\[\boldsymbol{m}_i=\frac{1}{N_i}\sum_{\boldsymbol{x}_j\in \mathcal{X}_i}\boldsymbol{x}_j, \quad i=1,2\]为了度量两类的间隔和每一类内部的聚集程度，可以定义各类的类内离散度矩阵（within-class scatter matrix）为
\[\boldsymbol{S}_i=\sum_{\boldsymbol{x}_j\in \mathcal{X}_i}(\boldsymbol{x}_j-\boldsymbol{m}_i)(\boldsymbol{x}_j-\boldsymbol{m}_i)^\top \in \mathbb{R}^{d\times d},\quad i=1,2\]那么总类内离散度矩阵（pooled within-class scatter matrix）为
\[\boldsymbol{S}_w = \boldsymbol{S}_1+\boldsymbol{S}_2\]类间离散度矩阵（between-class scatter matrix）为
\[\boldsymbol{S}_b = (\boldsymbol{m}_1-\boldsymbol{m}_2)(\boldsymbol{m}_1-\boldsymbol{m}_2)^\top \in \mathbb{R}^{d\times d}\]将所有样本投影到一维空间，根据前一节的投影公式，投影后的特征向量为
\[y = \boldsymbol{w}^\top\boldsymbol{x}\]投影后两类的均值（标量）分别为
\[\tilde{m}_i = \frac{1}{N_i}\sum_{y_j\in \mathcal{Y}_i}y_j=\frac{1}{N_i}\sum_{x_j\in \mathcal{X}_i}\boldsymbol{w}^\top\boldsymbol{x}_i = \boldsymbol{w}^\top\boldsymbol{m}_i, \quad i=1,2\]投影后的类内离散度和总类内离散度分别为
\[\begin{aligned} \tilde{S}_i &= \sum_{y_j\in \mathcal{Y}_i}(y_j-\tilde{m}_i)^2\\ \tilde{S}_w &= \tilde{S}_1+\tilde{S}_2\\ \end{aligned}\]投影后的类间离散度为
\[\tilde{S}_b = (\tilde{m}_1-\tilde{m}_2)^2\]根据前述 Fisher 投影准则的优化目标（即选择合适的投影方向，使得投影后类间离散度 $S_b$ 尽可能大，同时总类内离散度 $S_w$ 尽可能小）可以写出如下分式形式的优化目标函数：
\[J(\boldsymbol{w}) = \frac{\tilde{S}_b}{\tilde{S}_w}=\frac{(\tilde{m}_1-\tilde{m}_2)^2}{\tilde{S}_1+\tilde{S}_2}\]为了寻找最优投影方向 $\boldsymbol{w}$，需要将优化目标函数进行改写。由于
\[\begin{aligned} \tilde{S}_b &= (\tilde{m}_1-\tilde{m}_2)^2 \\ &= (\boldsymbol{w}^\top\boldsymbol{m}_1-\boldsymbol{w}^\top\boldsymbol{m}_2)(\boldsymbol{w}^\top\boldsymbol{m}_1-\boldsymbol{w}^\top\boldsymbol{m}_2)^\top\\ &= \boldsymbol{w}^\top(\boldsymbol{m}_1-\boldsymbol{m}_2)(\boldsymbol{m}_1-\boldsymbol{m}_2)^\top\boldsymbol{w}\\ &= \boldsymbol{w}^\top\boldsymbol{S}_b\boldsymbol{w} \end{aligned}\]而
\[\begin{aligned} \tilde{S}_w &= \tilde{S}_1+\tilde{S}_2\\ &=\sum_{y_1\in \mathcal{Y}_1}(y_1-\tilde{m}_1)^2+\sum_{y_2\in \mathcal{Y}_2}(y_2-\tilde{m}_2)^2\\ &=\sum_{x_1\in \mathcal{X}_1}(\boldsymbol{w}^\top\boldsymbol{x}_1-\boldsymbol{w}^\top\boldsymbol{m}_1)^2+\sum_{x_2\in \mathcal{X}_2}(\boldsymbol{w}^\top\boldsymbol{x}_2-\boldsymbol{w}^\top\boldsymbol{m}_2)^2\\ &=\boldsymbol{w}^\top[\sum_{x_1\in \mathcal{X}_1}(\boldsymbol{x}_1-\boldsymbol{m}_1)(\boldsymbol{x}_1-\boldsymbol{m}_1)^\top+\sum_{x_2\in \mathcal{X}_2}(\boldsymbol{x}_2-\boldsymbol{m}_2)(\boldsymbol{x}_2-\boldsymbol{m}_2)^\top]\boldsymbol{w}\\ &= \boldsymbol{w}^\top(\boldsymbol{S}_1+\boldsymbol{S}_2)\boldsymbol{w}\\ &= \boldsymbol{w}^\top\boldsymbol{S}_w\boldsymbol{w} \end{aligned}\]那么优化目标函数可以写成
\[J(\boldsymbol{w}) = \frac{\boldsymbol{w}^\top\boldsymbol{S}_b\boldsymbol{w}}{\boldsymbol{w}^\top\boldsymbol{S}_w\boldsymbol{w}}\]上式被称为广义瑞利（Rayleigh）商。
从优化目标来看，如果直接对上式（分子分母都是二次型）进行优化，有无穷个满足要求的解。为了解决多解问题，我们需要额外增加一个约束条件，限制解的个数。由于我们只关心投影的方向，对投影方向向量的模长不关心，并且上式分子分母的向量 $\boldsymbol{w}$ 数乘缩放不影响比值。
在我们求导之前，需要对分母进行归一化，因为不做归一的话，$\boldsymbol{w}$ 扩大任何倍，都成立，我们就无法确定 $\boldsymbol{w}$。这里 $\boldsymbol{w}$ 并不是唯一的，倘若 $\boldsymbol{w}$ 对应 $J(\boldsymbol{w})$ 的极大值点，则 $a\cdot \boldsymbol{w}$ 仍旧可以达到 $J(\boldsymbol{w})$ 的极大值点。
因此将优化问题更改如下
\[\begin{aligned} \max &\; \boldsymbol{w}^\top\boldsymbol{S}_b\boldsymbol{w}\\ s.t. &\; \boldsymbol{w}^\top\boldsymbol{S}_w\boldsymbol{w}=c\neq 0 \end{aligned}\]通过额外引入一个使得分子等于常数的等式约束来限制 $\boldsymbol{w}$ 的取值，然后通过拉格朗日乘子法求解极大值，定义拉格朗日函数如下
\[\begin{aligned} L(\boldsymbol{w},\lambda) &= \boldsymbol{w}^\top\boldsymbol{S}_b\boldsymbol{w} - \lambda (\boldsymbol{w}^\top\boldsymbol{S}_w\boldsymbol{w}-c)\\ \Rightarrow \frac{\partial L(\boldsymbol{w},\lambda)}{\partial \boldsymbol{w}} &= 2\boldsymbol{S}_b\boldsymbol{w} - 2\lambda \boldsymbol{S}_w\boldsymbol{w}\\ \end{aligned}\]《the Matrix Cookbook》二次型的导数
\[\frac{\partial \boldsymbol{x}^\top\boldsymbol{B\boldsymbol{x}}}{\partial \boldsymbol{x}} = (\boldsymbol{B}+\boldsymbol{B}^\top)\boldsymbol{x} \tag{81}\]而类间方差矩阵根据其定义，满足 $\boldsymbol{S}_b = \boldsymbol{S}_b^\top$，此时有
\[\frac{\partial \boldsymbol{x}^\top\boldsymbol{B\boldsymbol{x}}}{\partial \boldsymbol{x}} = 2\boldsymbol{B}\boldsymbol{x}\]
令上式等于零，取到极大值 $\boldsymbol{w}^{\star}$，即
\[\boldsymbol{S}_b\boldsymbol{w}^{\star} = \lambda \boldsymbol{S}_w\boldsymbol{w}^{\star}\]当样本数大于特征维度时，$\boldsymbol{S}_w$ 通常是非奇异矩阵，可求逆，因此有
\[\lambda \boldsymbol{w}^{\star} = \boldsymbol{S}_w^{-1}\boldsymbol{S}_b\boldsymbol{w}^{\star}\]即上述最优化问题倍转化为求矩阵 $\boldsymbol{S}_w^{-1}\boldsymbol{S}_b$ 的特征值 $\lambda$ 和特征向量 $\boldsymbol{w}^{\star}$。
将 $\boldsymbol{S}_b$ 的定义式代入有
\[\lambda \boldsymbol{w}^{\star} = \boldsymbol{S}_w^{-1}(\boldsymbol{m}_1-\boldsymbol{m}_2)(\boldsymbol{m}_1-\boldsymbol{m}_2)^\top\boldsymbol{w}^{\star}\]注意到，$(\boldsymbol{m}_1-\boldsymbol{m}_2)^{T}\cdot\boldsymbol{w}^\star$ 是标量，不会改变 $\boldsymbol{w}^ \star$ 的方向，因此可以得到 $\boldsymbol{w}^{\star} $ 是由 $\boldsymbol{S}_w^{-1}(\boldsymbol{m}_1-\boldsymbol{m}_2)$ 决定的，因此 Fisher 投影准则的最优投影方向为
\[\boldsymbol{w}^{\star} = \boldsymbol{S}_w^{-1}(\boldsymbol{m}_1-\boldsymbol{m}_2)\]至此，我们只需要求出原始样本的均值和方差（协方差矩阵？）就可以求出最佳的方向。
需要注意的是，Fisher 投影的最优解本身只给出了一个投影方向，并没有给出我们需要的分类面。要得到分类面，需要再投影后的方向（一维空间）上确定一个分类阈值 $w_0$ 并采取决策规则
\[\begin{aligned} g(\boldsymbol{x})=\boldsymbol{w}^\top\boldsymbol{x} + w_0 > 0 \Rightarrow \boldsymbol{x}\in y_1 \\ g(\boldsymbol{x})=\boldsymbol{w}^\top\boldsymbol{x} + w_0 < 0 \Rightarrow \boldsymbol{x}\in y_2 \end{aligned}\]这里给出另外一种推导思路，上述目标函数正好是广义瑞利商的形式，因此其最大值为 $\boldsymbol{S}_w^{-1}\boldsymbol{S}_b$ 的最大特征值，那么投影方向 $\boldsymbol{w}$ 即为 $\boldsymbol{S}_w^{-1}\boldsymbol{S}_b$ 对应最大特征值 $\lambda$ 的特征向量。
5. 感知准则
5.1. 线性可分性
前面介绍垂直平分准则和 Fisher 投影准则中，我们并没有对样本集进行任何要求。实际上，样本集是否线性可分是一个有必要讨论的问题，因此有了感知准则。样本集的线性可分性指的是，至少存在一个权向量（即决策面），能将样本集中的每个样本都正确分类，否则就是线性不可分的。
- 规范化
可设想，在二分类问题中，假设样本线性可分，将属于 $\omega_2$ 类的样本各分量同时乘以 $-1$，这个过程称为线性可分样本集的规范化。规范化以后，样本集所有样本均满足 $\boldsymbol{a}^{\text{T}}\boldsymbol{y}>0$，这本质上是一个有约束的优化问题，可采取一些方法求出最优的解向量 $\boldsymbol{a}^*$。
- 解区
更进一步，在增广样本空间的基础上，我们定义如下：
- 解向量：能将线性可分样本集中的每个样本都正确分类的权向量 $\boldsymbol{a}$。
- 解区：解向量往往不是一个，而是由无穷多个解向量组成的（角度）区域，称为解区。
在二维二分类问题中，解区（$\boldsymbol{a}^{\text{T}}\boldsymbol{y}>0$）如下图蓝色部分所示。
- 余量
解区中任意一个向量都是解向量，都能把样本正确分开。但如果一个解向量靠近解区的边缘，某些样本的判别函数可能刚刚大于零。考虑到噪声、计算误差等，靠近解区中间的解向量更加可靠。
因此，提出余量概念，即把解区向中间缩小，不取靠近边缘的解，引入余量b，解向量满足
\[\boldsymbol{a}^{\text{T}}\boldsymbol{y}_i>b, \quad i=1,2,\cdots,n\]如下图所示。
5.2. 感知准则函数
对于规范化的增广样本集，感知准则函数可以选取为：
\[J_p(\boldsymbol{a}) = \sum_{y\in{Y_e}}(-\boldsymbol{a}^{\text{T}}y)\]其中
\[Y_e: \{\boldsymbol{y}\in Y_e | \boldsymbol{a}^{\text{T}}\boldsymbol{y}<0\}\]表示样本集中被权向量 $\boldsymbol{a}$ 错分的样本集合。
对于规范化增广样本集，若权向量 $a$ 使样本集中的样本 $\boldsymbol{y}$ 错误分类，则 $\boldsymbol{a}^{\text{T}}\boldsymbol{y}<0$ 或 $-\boldsymbol{a}^{\text{T}}\boldsymbol{y}\geq 0$。所以 $J_p(\boldsymbol{a}) \geq 0$。
对于感知准则函数 $J_p(\boldsymbol{a})$，其最小值对应着最优解 $\boldsymbol{a}^*$。由此可以得到梯度下降法迭代公式
\[\begin{aligned} \Delta J_p(\boldsymbol{a}) &= \frac{\partial J_p(\boldsymbol{a})}{\partial\boldsymbol{a}} = -\sum_{\boldsymbol{y}\in{Y_e}}\boldsymbol{y}\\ \Rightarrow \boldsymbol{a} &= \boldsymbol{a} - \alpha\Delta J_p(\boldsymbol{a})=\boldsymbol{a}+\beta\sum_{\boldsymbol{y}\in{Y_e}}\boldsymbol{y} \end{aligned}\]5.3. 感知器模型
感知器是一个具有单层计算单元的神经元模型，感知器具有多输入和单输出。（如上图和下式所示）
\[y = f(\boldsymbol{w}^{\text{T}}\boldsymbol{x} - \theta)\]如果该神经元没有内部状态的转变，且 $f$ 为一个阶跃函数，其输出表达式为
\[y = f(\boldsymbol{w}^{\text{T}}\boldsymbol{x} - \theta) = \begin{cases} 1, & \boldsymbol{w}^{\text{T}}\boldsymbol{x} - \theta > 0 \\ -1, & \text{otherwise} \end{cases}\]权值向量 $\boldsymbol{w}$ 和阈值 $\theta$ 为感知器的参数，可以通过梯度下降法进行训练。当感知器用于两类模式的分类时，相当于在高维样本的特征空间中，用一个超平面把两类样本区分开，如果两类模式是线性可分的，则算法一定收敛。
6. 最小错分样本准则
感知准则函数只适用于线性可分的情况。对于样本集线性不可分的情况，算法不收敛，即 $\boldsymbol{a}^{\text{T}}\boldsymbol{y}>0\;(i=1,2,\cdots, n)$ 是矛盾不等式组，只能求满足不等式个数最多的解，或者最小错分样本数的解。
对于线性不可分情况，定义一个准则函数，其极值解对应两类样本集中错分数最少的权向量 $𝑎^*$，这种准则称为最小错分样本数准则。最后，采用梯度下降法等优化算法可完成求解。
6.1. 最小错分样本准则一
将 $n$ 个不等式 $\boldsymbol{a}^{\text{T}}\boldsymbol{y}>0\;(i=1,2,\cdots, n)$ 联立，并引入余量 $\boldsymbol{b}=[b_1,b_2,\cdots,b_n]^{\text{T}}$，可得
\[\boldsymbol{Y}\boldsymbol{a}-\boldsymbol{b} > 0\]其中余量可取值为 $\boldsymbol{b}=[1,1,\cdots,1]^{\text{T}}$。
设计如下最小错分样本准则
\[J_{q_1}(\boldsymbol{a}) = \Vert (\boldsymbol{Y}\boldsymbol{a}-\boldsymbol{b})-\vert (\boldsymbol{Y}\boldsymbol{a}-\boldsymbol{b}) \vert \Vert^2\]- 如果样本被正确分类，则 $(\boldsymbol{Y}\boldsymbol{a}-\boldsymbol{b})$ 与 $\vert (\boldsymbol{Y}\boldsymbol{a}-\boldsymbol{b}) \vert$ 同号，有 $J_{q_1}(\boldsymbol{a})=0$。
- 反之，如果样本被错误分类，则异号，有 $J_{q_1}(\boldsymbol{a})>0$。
不满足的样本（即错分的样本）越多，$J_{q_1}(\boldsymbol{a})$ 越大。$J_{q_1}(\boldsymbol{a})$ 取极小值时的权向量 $\boldsymbol{a}$ 就为最优解 $\boldsymbol{a}^*$ 。
6.2. 最小错分样本准则二
\[J_{q_1}(\boldsymbol{a})=\sum_{i=1}^n\frac{1+\text{sign}(y_i^\top \boldsymbol{a})}{2}\]- 如果样本被正确分类，则 $\text{sign}(y_i^\top \boldsymbol{a})=+1$，对应的项为正。
- 反之，如果样本被错误分类，$\text{sign}(y_i^\top \boldsymbol{a})=-1$，对应的项为 0。
因此，正确分类越多，$J_{q_1}(\boldsymbol{a})$ 越大，$J_{q_1}(\boldsymbol{a})$ 取极大值求得最优解。
6.3. 特点总结
- 解决两类问题的线性分类器
- 样本集不限，可以是线性不可分的
- 求满足不等式个数最多的权向量（最优）
- 分类器设计过程复杂
7. 最小平方误差准则
7.1. 准则定义
对于线性不可分情况，定义一个准则函数，其极值解对应两类样本集中错分误差平方和最小的权向量 $\boldsymbol{a}^*$，这种准则称为最小平方误差准则。
最小平方误差准则与最小错分样本准则相同，都可以用于样本线性可分和线性不可分的情况。但最小平方误差准则的极值解对应两类样本集中错分误差平方和最小的权向量 $\boldsymbol{a}^*$，是工程中常用的优化准则。
将 $n$ 个不等式 $\boldsymbol{a}^{\text{T}}\boldsymbol{y}>0\;(i=1,2,\cdots, n)$ 联立，并引入余量 $\boldsymbol{b}=[b_1,b_2,\cdots,b_n]^{\text{T}}$，可得
\[\boldsymbol{Y}\boldsymbol{a}-\boldsymbol{b} > 0\]联立线性方程组，并简写为矩阵形式
\[\begin{aligned} \boldsymbol{Y}\boldsymbol{a}&=\boldsymbol{b}\\ \text{where} \quad \boldsymbol{Y}&=\left(\begin{array}{c} y_{1}^{\mathrm{T}} \\ y_{2}^{\mathrm{T}} \\ \vdots \\ y_{n}^{\mathrm{T}} \end{array}\right) =\left(\begin{array}{cccc} y_{11} & y_{12} & \cdots & y_{1 d} \\ \vdots & & & \\ y_{n 1} & y_{n 2} & \cdots & y_{n d} \end{array}\right) \end{aligned}\]前述已知上式是矛盾方程组，这里采用最小二乘法求解。
首先定义误差 $\boldsymbol{e} = \boldsymbol{Y}\boldsymbol{a}-\boldsymbol{b}$，则平方误差准则函数为
\[J_s(\boldsymbol{a}) = \Vert \boldsymbol{e} \Vert^2 = \Vert \boldsymbol{Y}\boldsymbol{a} - \boldsymbol{b} \Vert^2\\\]根据最小二乘法，最优权向量为
\[\boldsymbol{a}^{\star} = (\boldsymbol{Y}^\top\boldsymbol{Y})^{-1}\boldsymbol{Y}^\top\boldsymbol{b}\]注意，最优权向量的求取与余量 $\boldsymbol{b}$ 的选择有关。
7.2. 线性回归与最小二乘估计
多元线性回归是通过 $(\boldsymbol{x},y), \boldsymbol{x}\in \mathbb{R}^d, y\in \mathbb{R}$ 的一系列观测样本，估计他们之间的线性关系
\[y=w_0+w_1x_1+w_2x_2+\cdots+w_dx_d = \sum_{i=0}^d w_ix_i = \boldsymbol{w}^\top\boldsymbol{x}\]其中， $\boldsymbol{w} = [w_0, w_1, \cdots, w_d]^\top$ 是待定参数。
从机器学习第角度分析线性回归估计，就是用训练样本集估计模型中第参数，使得模型在最小平方误差意义下能够最好地拟合训练样本。即
\[\begin{aligned} \text{sample batch:}\quad & {(\boldsymbol{x}_1, y_1),\cdots, (\boldsymbol{x}_N, y_N)}\\ \text{regression model:}\quad & f(\boldsymbol{x}) = w_0+w_1x_1+w_2x_2+\cdots+w_dx_d = \sum_{i=0}^d w_ix_i = \boldsymbol{w}^\top\boldsymbol{x}\\ \text{MSE loss function:}\quad & \min_{\boldsymbol{w}} L = \frac{1}{N}\sum_{j=1}^N(f(\boldsymbol{x}_j)-y_j)^2 \end{aligned}\]目标函数可以写成以下矩阵形式（忽略系数因为其不影响最优方向）
\[\begin{aligned} L(\boldsymbol{w}) &= \sum_{j=1}^N(f(\boldsymbol{x}_j)-y_j)^2\\ &=\Vert \boldsymbol{X}\boldsymbol{w}-\boldsymbol{y} \Vert^2\\ &=( \boldsymbol{X}\boldsymbol{w}-\boldsymbol{y} )^\top ( \boldsymbol{X}\boldsymbol{w}-\boldsymbol{y} ) \end{aligned}\]其中 $\boldsymbol{X}=[\boldsymbol{x}_1^\top, \cdots, \boldsymbol{x}_N^\top]^\top\in \mathbb{R}^{d\times N}$ 是全部训练样本的特征变量组成的矩阵，$\boldsymbol{y}=[y_1, \cdots, y_N]^\top$ 是全部训练样本的观测变量（分类标签）组成的向量。
展开后得到二次型
\[L(\boldsymbol{w}) = \boldsymbol{y}^\top \boldsymbol{y} - 2 \boldsymbol{y}^\top \boldsymbol{X} \boldsymbol{w} + \boldsymbol{w}^\top \boldsymbol{X}^\top \boldsymbol{X} \boldsymbol{w}\]使得上述目标函数最小化的参数 $\boldsymbol{w}$ 应满足
\[\frac{\partial{L(\boldsymbol{w})}}{\partial{\boldsymbol{w}}} = 0\]第一项：与 $\boldsymbol{w}$ 无关，求导后为 $0$； 第二项：
\[\frac{\partial}{\partial{\boldsymbol{w}}}(- 2 \boldsymbol{y}^\top \boldsymbol{X} \boldsymbol{w}) = - 2 \boldsymbol{X}^\top \boldsymbol{y}\\\]第三项：令 $\boldsymbol{B} = \boldsymbol{X}^\top\boldsymbol{X}$，参考《the Matrix Cookbook》二次型的导数
\[\frac{\partial \boldsymbol{x}^\top\boldsymbol{B\boldsymbol{x}}}{\partial \boldsymbol{x}} = (\boldsymbol{B}+\boldsymbol{B}^\top)\boldsymbol{x} \tag{81}\]若 $\boldsymbol{B}$ 满足 $\boldsymbol{B} = \boldsymbol{B}^\top$，此时有
\[\frac{\partial \boldsymbol{x}^\top\boldsymbol{B\boldsymbol{x}}}{\partial \boldsymbol{x}} = 2\boldsymbol{B}\boldsymbol{x}\]
那么有
\[\begin{aligned} &-2 \boldsymbol{X}^\top\boldsymbol{y} + 2 \boldsymbol{X}^\top \boldsymbol{X} \boldsymbol{w}=0\\ &\boldsymbol{X}^\top\boldsymbol{X}\boldsymbol{w}=\boldsymbol{X}^\top\boldsymbol{y} \end{aligned}\]当 $\boldsymbol{X}^\top\boldsymbol{X}$ 可逆时（这在大多数实际应用中是成立的），最优参数的解为
\[\boldsymbol{w}^{\star}=(\boldsymbol{X}^\top\boldsymbol{X})^{-1}\boldsymbol{X}^\top\boldsymbol{y}\]该方法就是经典的 〖最小二乘法〗 线性回归，其中的矩阵 $(\boldsymbol{X}^\top\boldsymbol{X})^{-1}\boldsymbol{X}^\top$ 被称作 $\boldsymbol{X}$ 的伪逆矩阵（加号逆），记作 $\boldsymbol{X}^+$。
采用上述算法，加入真实的样本是服从之前给出的线性关系的物理规律产生的，只是在观测中带有噪声或误差，则最小二乘线性回归就通过数据学习到了系统本来的模型，而在我们对数据背后的物理模型并不了解的情况下，线性回归给出了在最小平方误差意义下对解释变量与观测变量之间线性关系的最好估计。
7.3. 特点总结
- 解决两类问题的线性分类器
- 样本集不限，可以是线性不可分的
- 求最小平方误差的权向量（最优）
- 分类器设计过程相对简单