C05. 线性判别函数
5.1 引言
在 Ch03 中，假定概率密度函数的参数形式已知，使用训练样本来估计概率密度函数的参数值
在 Ch05 中，假定判别函数的参数形式已知，使用训练样本来估计判别函数的参数值
求解判别函数的参数值的方法：有些是基于统计的方法，有些不是基于统计的方法；这些方法都不需要知道概率密度函数的参数值，因此它们都属于非参数化的方法
线性判别函数分类
- 基于 $\text{x}$ 的各个分量的线性函数
- 基于 $\text{x}$ 的各个分量的线性基函数
寻找线性判别函数的问题被形式化为极小化准则函数的问题，以分类为目的的准则函数：样本风险，也叫训练误差，是对训练样本集进行分类所引起的平均损失
因为计算极小风险线性判别函数是困难的，因此本章将主要讨论处理「极小化准则函数」的「梯度下降法」的计算复杂度和收敛性。
5.2 线性判别函数和判定面
线性判别函数：由 $\text{x}$ 的各个分量的线性组合而成的函数
- $\text{w}$ 是「权向量」
- $w_0$ 是「阈值」或者「偏置」
$$
g ( \text{x} ) =\text{w}^T\text{x}+w_0
$$
5.2.1 二分类情况
判别条件
- 如果 $g ( \text{x} )>0$，则判定 $\omega_1$
- 如果 $g ( \text{x} ) <0$，则判定 $\omega_2$
- 如果 $g ( \text{x} ) =0$，则 $g ( \text{x} )$ 定义一个判定面，用于将属于 $\omega_1$ 的点与属于 $\omega_2$ 的点分开
- 当 $g ( \text{x} )$ 是线性的，则这个判定面被称为「超平面」
权向量 $\text{w}$ 与超平面上的任意向量正交
- 假设 $\text{x}_1$ 和 $\text{x}_2$ 都在判定面上
- $\text{w}^T\text{x}_1+w_0=\text{w}^T\text{x}_2+w_0=0$
- $\text{w}^T ( \text{x}_1-\text{x}_2 ) =0$
- 超平面 $H$ 将特征空间分成两个部分
- 对应于 $\omega_1$ 类的决策区域 $\mathcal{R}_1$，当 $\text{x}\in\mathcal{R}_1$，则 $g ( \text{x} )>0$，所以判定面的法向量 $\text{w}$ 指向 $\mathcal{R}_1$
- 对应于 $\omega_2$ 类的决策区域 $\mathcal{R}_2$，当 $\text{x}\in\mathcal{R}_2$，则 $g ( \text{x} ) <0$，所以判定面的法向量 $\text{w}$ 指向 $\mathcal{R}_2$
判别函数 $g ( \text{x} )$ 是特征空间中某点 $\text{x}$ 到超平面的距离的一种代数度量
- $\text{x}=\text{x}_p+r\frac{\text{w}}{|\text{w}|}$
- $\text{x}_p$ 是 $\text{x}$ 在 $H$ 上的投影向量
- $g ( \text{x}_p ) =0$
- $r$ 是相应的算术距离
- $r>0$：表示 $\text{x}$ 在 $H$ 的正侧
- $r<0$：表示 $\text{x}$ 在 $H$ 的负侧
- $\text{x}_p$ 是 $\text{x}$ 在 $H$ 上的投影向量
- $g ( \text{x} ) =\text{w}^T\text{x}+w_0=r|\text{w}|$
- $r=\frac{g ( \text{x} )}{|\text{w}|}$
- 从原点到 $H$ 的距离为 $w_0/|\text{w}|$
- 如果 $w_0>0$，表明原点在 $H$ 的正侧
- 如果 $w_0<0$，表明原点在 $H$ 的负侧
线性判别函数基于超平面判定面把特征空间分割成两个区域
- 超平面的方向由法向量 $\text{w}$ 确定
- 超平面的位置由阈值 $w_0$ 确定
- 判别函数 $g ( \text{x} )$ 正比于 $\text{x}$ 点到超平面的代数距离
- 当 $\text{x}$ 在 $H$ 的正侧时，$g ( \text{x} )>0$
- 当 $\text{x}$ 在 $H$ 的负侧时，$g ( \text{x} ) <0$
5.2.2 多分类情况
将多分类问题转化成多个二分类问题
- 把 $K$ 分类问题转化为 $K$ 个二分类问题，其中第 $i$ 个二分类问题把属于 $\omega_i$ 的点与不属于 $\omega_i$ 的点区分开
- 把 $K$ 分类问题转化为 $K ( K-1 ) /2$ 个二分类问题，其中第 $c_{ij}$ 个二分类问题把属于 $\omega_i$ 和 $\omega_j$ 的点区分开
- 缺点：以上两种方法都会产生无法确定其类型的区域
使用「线性机」解决多分类问题 ( 也叫 $K$ 类判别函数[^Bishop,2006] Ch04 )
- 定义$K$ 个判别函数：$g_i(\text{x})=\text{w}_i^T\text{x}i+w{i0},i=1,\cdots,K$
- 如果 $g_i(\text{x})>g_j(\text{x}),i\neq j$，则 $\text{x}$ 属于 $\omega_i$
- $\omega_i$ 与 $\omega_j$ 之间的判定面为 $g_i(\text{x})=g_j(\text{x})$，即 $(\text{w}i-\text{w}j)^T\text{x}+(w{i0}-w{j0})=0$，此时的判定面与二分类情况相同
- 如果 $g_i(\text{x})>g_j(\text{x}),i\neq j$，则 $\text{x}$ 属于 $\omega_i$
- 缺点：判决区域是凸的，限制了分类器的适应性和精确性
- 无法判别非凸的区域
5.3 广义线性判别函数
线性判别函数 $g( \text{x})=w_0+\sum_{i=1}^D w_i x_i$
- 系数 $w_i$ 是权向量 $\text{w}$ 的分量
- 系数的个数是 $D$
二次判别函数 $g ( \text{x} )=w_0+\sum_{i=1}^D w_i x_i+\sum_{i=1}^D\sum_{j=1}^D w_{ij}x_i x_j$
- 因为 $x_i x_j = x_j x_i$ ，所以假设 $w_{ij}=w_{ji}$
- 系数的个数是 $D+D(D+1)/2$
- $g(\text{x})=0$ 定义的分隔面是二阶曲面，也叫超二次曲面
多项式判别函数 $g(\text{x} )=\sum_{i=1}^{\hat{D}} a_i y_i(\text{x})=\text{a}^T\text{y}$
- $y_i(\text{x}),i=1,\cdots,\hat{D}$ 是基函数，可以为 $\text{x}$ 的任意函数，这些函数对应的特征提取子系统的结果
- $\text{a}\in\mathbb{R}^{\hat{D}}$ 是基函数权向量
- 优点：通过这种非线性变换，将非线性可分问题转化到线性可分问题
- 缺点：变换导致维度空难问题
5.4 二分类线性可分的情况
假设包含$N$个样本的集合{$\text{y}_1,\cdots,\text{y}_N$}，标记 $\omega\in{\omega_1,\omega_2}$，求解判别函数 $g(\text{x})=\text{a}^T\text{y}$ 的权向量 $\text{a}$，如果权向量存在就表示样本「线性可分」。
- 对于一个样本 $\text{y}_i$，如果 $\text{a}^T\text{y}_i>0$，则标记为 $\omega_1$，规范化为「+1」
- 对于一个样本 $\text{y}_i$，如果 $\text{a}^T\text{y}_i<0$，则标记为 $\omega_2$，规范化为「-1」
- 经过规范化后，只需要寻找对所有样本都有 $\text{a}^T\text{y}_i>0$ 的权向量 $\text{a}$，这个向量称为「分离向量」，也叫「解向量」
5.4.1 几何解释和术语
解区域：区域中的向量都是解向量
- 解区域中单位长度的权向量作为解向量
- 解区域中寻找满足 $\text{a}^T\text{y}_i\geq b>0$ 的具有最小长度的权向量
- $b$ 称为「边沿裕量」，也叫「间隔」
- 解向量尽可能不在边界点上
- 解区域的「中间」位置来寻找解向量，因为这样的解更可能对测试样本进行正确的分类
5.4.2 梯度下降算法
(梯度下降的推导及区别，还可参考 [^Bishop,2006] Ch05 Sec 5.2
寻找满足线性不等式组 $\text{a}^T\text{y}_i>0$ 的解时所采用的方法：定义准则函数 $J(\text{a})$ ，当 $\text{a}$ 是解向量时，$J(\text{a})$ 最小。于是问题就转化为标量函数的极小化问题，通常采用梯度下降法来解决
- $\alpha$ 是正的比例因子，也叫用于设定步长的「学习率」
- 如果 $\alpha$ 太小，则收敛速度慢
- 如果 $\alpha$ 太大，则无法收敛
$$
\text{a}^{(t+1)}=\text{a}^{(t)}-\alpha^{(t)}\nabla J(\text{a}^{(t)})
$$
设定学习率的原则性的方法：准则函数在 $\text{a}^{(t)}$ 附近的二阶泰勒展开式
- $\text{H}=\partial^2 J/\partial a_i\partial a_j$
$$
\begin{aligned}
J(\text{a})&\simeq J(\text{a}^{(t)})+\nabla J^T(\text{a}-\text{a}^{(t)})+\frac12(\text{a}-\text{a}^{(t)})^T \text{H}(\text{a}-\text{a}^{(t)})\
J(\text{a}^{(t+1)})&\simeq J(\text{a}^{(t)})-\alpha^{(t)}|\nabla J|^2+\frac12(\alpha^{(t)})^2\nabla J^T \text{H}\nabla J
\end{aligned}
$$
5.5 感知器准则函数最小化
5.5.1 感知器准则函数
构造解线性不等式 $\text{a}^T\text{y}_i>0$ 的准则函数的问题
- 代价函数：$J(\text{a};\text{y}_1,\cdots,\text{y}_n)$ 是被 $\text{a}$ 错误的样本数
- 这个函数是分段常数函数，无法进行梯度搜索
- 感知器准则函数：$J_p(\text{a})=\sum_{\text{y}\in\mathcal{E}}(-\text{a}^T\text{y})$
- $\mathcal{E}(\text{a})$ 是被 $\text{a}$ 错分的样本集合
- 当 $\text{a}^T\text{y}\leq 0$ 时，$J_p(\text{a})$ 是非负的
- $J_p(\text{a})$ 是与错分样本到判决边界距离之和成正比的
- 梯度下降的迭代公式：$\text{a}^{(t+1)}=\text{a}^{(t)}+\alpha^{(t)}\sum_{\text{y}\in\mathcal{E}_t}\text{y}$
- $\mathcal{E}(\text{a})$ 是被 $\text{a}$ 错分的样本集合
- 批处理：每次修正权向量时都要计算成批的样本
- 改进方法：单样本迭代
5.5.2 单个样本校正的收敛性证明
5.5.3 一些直接的推广
5.6 松弛算法
5.6.1 下降算法
5.6.2 收敛性证明
5.7 线性不可分的情况
当样本是线性可分的时候，感知器算法和松弛算法都能解决向量分类的问题，这些算法统称为「误差校正方法」，因为它们都在遇到错分样本时才对权向量进行校正，都是以完全无错解为目标。
当样本是线性不可分的时候，感知器算法和松弛算法将永远无法收敛，于是采用许多启发式规则用于修改误差校正算法，使得不可分问题得到可以接受的结果，即对可分问题仍能保证大部分正确分类。