机器学习中的核心算法: 分类器算法
训练模型并使用它对数据进行分类是机器学习需要解决的问题之一. 为了训练出这样的模型, 基于样本数量的多寡和数据的类型是否为文本, 我们需要使用不同的算法模型才能相应地得到最优结果.
简单地来说, 在数据集足够庞大 $(\geqslant 100\text{K})$ 的情况下, 我们可以尝试使用随机梯度分类器: SGD Classifier.
若不然的话, 可以尝试 线性支持向量机分类器 Linear SVC, 若效果不佳且数据类型是文本的话我们可以尝试使用 朴素贝叶斯 Naive Bayes, 如果并不是文本数据的话我们可以尝试使用 K近邻算法分类器 KNeighbors Classifier.
下面我们简单地对上文中提到的四种算法进行介绍:
1. 随机梯度分类器
最简单的分类器实际上解决的是 “是” 和 “否” 的二元判断问题. 虽然随机梯度分类器可以比较自然的处理多分类问题, 实际上它不过是将相对复杂的多分类拆分成若干个二分类问题:
比如一个对 $10$ 个数字的识别问题就可以使用OVO (一对一) 策略拆分成 $\binom{10}{9} = 45$ 个不同的二分类问题, 或者使用 OVR (一对其余) 策略拆分成 $10$ 个二分类问题.
而要解释这一算法中的 随机梯度 究竟是什么, 我们首先需要解释 梯度下降 的含义. 在这里, 我们的基本思路是假设二分类问题中的分类规则是由某一个 判别函数 所表示的.
在训练模型的过程中, 样本数据可以作为判别函数的输入参数, 并且使用一个 损失函数 用于评价当前模型对数据的预测值相比其真实值的偏差程度, 而训练的目的是调整 判别函数 , 使它对训练数据集的判断对应的 损失函数 值 极小化, 也就是说我们要把训练数据集作为 判别函数 的输入, 通过逐渐调整 判别函数 自身的相关参数使得 损失函数 最优化(求其近似极小值), 而 梯度下降 就是求函数极值的一个有效方法.
对连续函数而言, 其在某一点的一阶 (偏) 导数值的大小代表了该输入参数的变化将会对函数值的大小所造成的影响, 因此我们可以基于导数值判断输入参数应该如何变化才能使函数值更接近极值. 这就像爬山: 如果我们从山上的某一点出发一直沿着更陡峭的方向前行, 往往相比毫无目的地行进到达山顶的可能性更大. 当然, 一味地沿着眼下最陡峭的方向行进也很有可能不能到达最高峰而是被困在小山头上 (局部最优点), 为了避免这个问题而设计出来的各种梯度下降法的衍生品以后有机会再作讨论.
在理解了梯度下降法的作用和基本原理后, 我们就可以对 梯度分类器 的含义作出解释:
定义 (梯度分类器)
梯度分类器就是其 判别函数 在训练过程中使用了梯度下降法进行最优化的分类器.
下面再来解释 随机. 随机梯度下降法 在每一次对函数的最优化迭代过程中, 只从训练数据集中 随机抽取一个 作为函数输入的样本, 因此计算速度很快, 在样本量足够大的情况下就可以很快地得到一个精度还不错的模型. 而其缺点就是使用抽取的单个样本所计算出的迭代方向并不完全准确, 因此也有可能迭代方向并不是整体最优方向.
与之相对的还有 批量梯度下降法 和 小批量梯度下降法:
定义 (批量梯度下降法)
批量梯度下降法在每一次迭代中都会使用整个训练数据集作为其样本, 要计算数据集中所有样本的训练误差, 因此在数据集庞大时训练速度明显不如人意, 但可以确保在每次迭代中都顾及全体样本, 迭代方向一定和整体最优一致.
定义 (小批量梯度下降法)
小批量梯度下降法的迭代策略是前二者的混合, 其训练速度和模型精度介于二者之间. 它将整个训练数据集分为数组, 在每一次迭代时 随机抽取一组, 并计算这一组中所有样本的训练误差. 这样虽然无法确保迭代方向一定和整体最优一致, 但在大幅缩短训练耗时的同时也明显减小了迭代方向偏离整体最优的概率.
因此, 我们的总结如下:
定义 (随机梯度分类器)
随机梯度分类器就是其 判别函数 在训练过程中使用了随机梯度下降法进行最优化的分类器.
2. 线性支持向量机分类器
线性支持向量机 是 支持向量机 的一个子类. 将数据集中的参数投影到某一个平面或空间 (这取决于参数的维度) 上, 若只需要使用一条直线, 平面或超平面即可将属于两种类别的参数完全隔离开, 我们就称这样的数据集是 线性可分 的, 而用于区分 线性可分 数据集的支持向量机分类器就被称为 线性支持向量机分类器.
要解释支持向量机, 就要先解释感知器 (Perceptron).
感知器要解决的问题和支持向量机的基本一致, 同样是要找到一个可以将某个线性可分的数据集分开的超平面:
\[w \cdot x + b = 0\]其中 $x$ 为数据集中的任意一个 $n$ 维向量, $w$ 为需要通过训练而确定的 $n$ 维向量, $b$ 为常数. 对于数据集中任意给定的一个参数 $x_i$, 感知器的决策函数为
\[f(x_i) = \text{sign}(w \cdot x_i + b)\]显然地, $z = w \cdot x + b$ 就是对整个数据集的 线性回归. 和通过最小化均方误差求得权值 $w$ 不同, 感知器的处理方式是几何意义上的:
我们知道, 对 $n$ 维空间中的平面 ($x$ 是一个 $n$ 维空间中的点, 此处用一个 $n$ 维向量表示)
\(w \cdot x + b = 0\) 其中 $w : (_1, w_2, \cdots, w_n)$, 空间上某点 $x: (x_1, x_2, \cdots, x_n)$ 到该平面的 几何距离 为
\[d = \frac{w_1 \cdot x_1 + w_2 \cdot x_2 + \cdots + w_n \cdot x_n + b}{\sqrt{w_1^2 + w_2^2 + \cdots + w_n^2}} = \frac{\vert w \cdot x + b\vert}{\vert \vert w \vert \vert}.\]考虑训练中的超平面, 我们在每一个测试数据集中的参数 $x_i$ 到超平面的距离前加上符号 $y_i$ 以表示它被分到的类别, 并从现在开始我们记每一个样本点为 $(x_i, y_i)$ 的形式:
若 $x_i$ 被分类到超平面上方 (即 $w \cdot x_i + b > 0$), 记其到超平面的 函数距离 为
\[\frac{\vert w \cdot x + b\vert}{\vert \vert w \vert \vert}\]若被分类到下方, 则 函数距离 被记为
\[-\frac{\vert w \cdot x + b\vert}{\vert \vert w \vert \vert}\]即: 若该点被正确分类, 其到超平面的 函数距离 表示为
\[y_i \cdot \frac{\vert w \cdot x + b\vert}{\vert \vert w \vert \vert}\]若被误分, 则表示为
\[-y_i \cdot \frac{\vert w \cdot x + b\vert}{\vert \vert w \vert \vert}\]将训练中所有被误分的参数到超平面的函数距离求和并乘上 $\vert \vert w \vert \vert$ 忽略分母对误分值造成的影响, 我们就得到了感知器的损失函数:
\[\text{L}(w, b) = - \sum_{i=1}^{n} y_i \cdot (w \cdot x_i + b)\]求解这个无约束条件的最优化问题 $\text{min}(\text{L}(w, b))$
就可以得到所需要的超平面
\[w * x + b = 0.\]求解无约束最优化问题可以得到无穷多个解, 解得的平面可能在当前的训练数据集下性能良好, 但应用于新的数据集时效果就会明显不佳, 因为这样训练出的超平面很可能并不是最优的. 线性支持向量机 就是在感知机的基础上被设计出来以找出最优的超平面对应的线性方程的.
下面, 我们解释什么是 支持向量机.
为了寻找最优的超平面, 我们需要引入 边距 (Margin) 的概念以度量平面方程的优劣.
边距 就是指训练数据集中所有参数到超平面距离的绝对值中的最小值. 而 支持向量机 的目标就是在感知器的基础上, 找到边距最大的那个超平面. 这样的超平面更不太可能出现明显的过拟合性, 也就是说它在应用于未知样本时具有更小的泛化误差.
而在训练数据集中, 自身到超平面的几何距离恰为这个超平面在当前的数据集下的边距的所有向量, 就被统称为 支持向量.
](https://i.loli.net/2021/08/10/7AYoNkB4UuxIgX5.png)
根据上述的讨论我们得知, 样本点 $(x_i, y_i)$ 和分类超平面 $w \cdot x + b = 0$ 的 几何距离 为
\[d_i = \frac{\vert w \cdot x_i + b\vert}{\vert \vert w \vert \vert}\]而训练数据集的 几何距离 自然是所有样本点到分类超平面的 几何距离 中的最小值:
\[D = \text{min}(d_i), i \in [n]\]而基于 边距 的定义和支持向量机的目标, 我们就可以得到它的目标函数:
\[\begin{cases} \text{max}(D) \\ \frac{\vert w \cdot x_i + b\vert}{\vert \vert w \vert \vert} \geqslant D, i \in [n] \end{cases}\]求解这个有约束最优化问题, 就可以得到所需要的超平面, 而这个所求得的超平面, 就称为 线性支持向量机分类器 .
3. 朴素贝叶斯分类器
朴素贝叶斯分类的核心思想是基于现有的经验和现象 (在我们的问题中也就是指训练数据集所蕴含的信息) 构造用于分类的映射规则. 朴素贝叶斯分类是贝叶斯分类, 也就是基于贝叶斯定理的分类算法组成的集合, 中的一个算法. 要讨论朴素贝叶斯分类, 我们首先需要了解贝叶斯定理.
定理 (贝叶斯定理)
设 $B$ 为所观测到的结果, $A$ 为导致这一结果发生的可能事件之一. 则在我们观测到 $B$ 发生的前提下, $B$ 确实是由 $A$ 引发的概率是: \(P(B \vert A) = \frac{P(A \vert B) \cdot P(B)}{P(A)}.\)
而朴素贝叶斯算法的基本思想则是: 对于一个给定的待分类项, 依次求解在假设此项出现的情况下, 该项属于各个不同类别的概率分别多大. 计算结果揭示它属于哪一个类别的概率最大, 就将其分类到哪一类中去. 也就是说, 在可用信息仅限于训练数据集的情况下, 我们使用训练数据集中预分类好的数据对每一个不同的参数计算它最有可能属于哪一类的条件概率, 生成一张 “判别表”. 并且在判断完全不同的新数据集里的参数时, 如果该参数位于表中, 我们就沿用训练结果对其直接分类.
下面, 我们给出朴素贝叶斯分类的正式流程:
设$x = {a_1, a_2, \cdots, a_m}$ 为一个待分类项, $a_1, a_2, \cdots, a_m$ 分别为 $x$ 的不同特征属性, 并且有类型集合 $C = {y_1, y_2, \cdots, y_n}$.
对于集合 $C$ 中的每一种类型 $y_i$, 计算 $P( y_i \vert x)$, 比对取得使条件概率最大的 $y_i$, 这即为所求的, $x$ 所属于的类型.
不难看出, 训练朴素贝叶斯分类器中最重要的环节是根据训练数据集求出每一个条件概率 $P( y_i \vert x)$. 在训练过程中, 对条件概率的计算流程如下:
- 将训练数据集视作一个分类的类别和总数已知的待分类项集合.
- 分别计算统计训练数据集中元素的特征属性 $a_1, a_2, \cdots, a_m$ 在各类别 $y_1, y_2, \cdots, y_n$ 下的 $m \cdot n$ 个条件概率估计 \(P(a_i \vert y_j), ~~ i \in [m], ~ j \in [n].\)
- 基于特征属性条件独立的假设, 计算 \(P(y_i \vert x) = \frac{P(y_i) \prod_{j=1}^{m}P(a_j \vert y_i)}{P(x)} = \frac{P(x \vert y_i)P(y_i)}{P(x)}.\)
如果数据集中的特征属性为连续值, 我们则通常假定其值服从 正态分布.
而在某个类别下, 如果并没有出现某个特征项划分, 也就是 $P(a \vert y) = 0$ 这一现象出现的情形下, 我们可以使用 Laplace 校准, 对每个类别下所有划分的计数均 $+1$ 确保其不为 $0$.
因此, 我们同样可以使用朴素贝叶斯算法训练一个基于贝叶斯定理的分类器, 这样的分类器就是 朴素贝叶斯分类器.
4. K 近邻分类器
K 近邻算法又称 K Nearest Neighbors, 顾名思义就是一个 “和临近数据值” 有关的算法.
具体来说, 其原理就是, 在给定参数 $x: (x_1, x_2, \cdots, x_n)$ 并判定其类型时, 统计离它最近的 $k$ 个邻接点的类型, 哪一种点数量最多, 就将其分类为哪一种.
在细节上, 我们首先需要考虑计算 “邻接点的距离”, 也就是考虑对高维空间内点之间距离的度量. 一般而言, 我们常在 KNN 中使用 欧式距离 进行点之间距离的计算.
其次, $k$ 的取值也相当重要. 在实践中, $k$ 的取值是通过从小到大取值试验, 然后进行交叉验证: 按照一定比例拆分出训练数据集和验证数据集, 对每一个可能的 $k$ 值计算验证数据集判定结果的方差 (错误率), 选出效率更高的临界点作为 $k$ 的取值.
KNN 是一个 惰性算法, 这意味着它的全部计算过程只在对新的数据点进行分类时发生. 而基于此特征和其工作原理我们显然可以得知, KNN 在被应用到较大的数据集时需要更多的计算时间, 因为在分类新数据点时程序需要计算出新数据点到训练数据集中每一个数据点的距离, 将其排序并取前 K 个最小的, 这意味着对存储资源和计算资源的双重消耗.
最后, 我们总结如下:
KNN是一个无需参数, 无需假设, 不需要事先对数据进行大量训练明显消耗时间的算法模型.KNN原理简单, 便于实现和使用, 但是不适用于规模庞大的数据集.K值会显著影响算法的分类表现, 在实践中我们常使用 交叉分类 获取最佳的K值.- 使用
KNN算法所构造的分类器就被称为K近邻分类器.
