机器学习

Published: 10/1/2023

机器学习指的是计算机不经过显式编程而具有学习能力，是人工智能的一个分支，其算法可以通过数据训练来实现。通常基于概率论，统计学，线性代数等数学知识。

后续所有内容来自《机器学习》，此处仅为总结与归纳。

机器学习基于给定数据集进行学习，数据集中的计量单位称为样本，样本的属性称为特征，样本的属性与特征的对应关系称为标签，同时所有的样本组成了样本空间或者称为特征空间。对于一数据集，所有存在的假设集合被称为假设空间，其中所有符合规律的假设集合组成了版本空间，机器学习的目标是针对某一特定问题，来寻找假设，使得假设对应该问题背后蕴含的规律，这一过程就被称为学习。

如果版本空间中存在多种假设，则考虑偏好函数，偏好函数是对假设的偏好程度的量化，通常使用损失函数来衡量偏好函数。损失函数是对假设的评价函数，通常使用交叉熵，均方误差等函数来衡量损失函数，通过最小化对应的损失函数值来选择最优的假设。

根据数据集有无标签，可将机器学习分为监督学习与无监督学习。无监督学习主要包含聚类，也就是Cluster，用于尝试寻找数据集中暗含的规律；有监督学习主要针对模型输出值是否连续，可分为回归（输出值连续）与分类。分类又分为二分类与多分类。

模型评估与选择

首先了解几个概念：

错误率：分类错误样本数占总样本数的比例
精度：分类正确样本数占总样本数的比例
训练误差：训练集上的误差
泛化误差：模型在新样本上的误差
过拟合：模型在训练集上表现很好，但在测试集上表现很差，可能把训练样本本身特点当作了所有潜在样本的特点
欠拟合：模型在训练集上表现很差，可能模型过于简单，对于训练样本的一般性质尚未学好

通过对候选模型的泛化误差进行评估，选择泛化误差最小的模型。常用的评估方法有留出法，交叉验证法，自助法。

通常使用测试集来测试测试误差作为泛化误差的近似，假设测试集样本从样本真实分布中独立同分布采样，并且不应出现在训练集中。

留出法

将数据集划分为两互斥集合，一个用于训练，一个用于测试。通常训练集占总数据集的2/3~4/5，测试集占10%~30%。分配时需要尽可能保持数据分布一致性，为了实现这一目标在划分数据集时通常使用分层抽样。为了提高评估的稳定性，一般需要采用若干次随机划分，并重复实验取平均值。

交叉验证法

将数据集划分为k个大小相似的互斥子集，每个子集保持数据分布一致性。每次训练时使用k-1个子集的并集作为训练集，余下的子集作为测试集，这样可以进行k次训练，通过计算k次测试结果的平均值来评估模型性能。需要注意该方法的稳定性通常取决于k的取值，所以该方法通常也被称为k折交叉验证。k最常用的取值为10。

和留出法类似，交叉验证法也需要重复实验取最终平均值，以提高评估的稳定性。

在此基础上特殊的有留一法，也就是k=n，n为数据集大小，这样可以最大程度的利用数据集，但是计算量较大。

自助法

以自助采样为基础，对于给定容量为m的数据集D,每次随机从D中挑选一个样本，拷贝放入D1中，并将该样本放回原始数据集，重复m次得到D1。初始数据集中约有36.8%左右的样本未出现在采样数据集中，所以可用D1作为训练集，D-D1作为测试集。自助法的优势在于可以从初始数据集中产生多个不同的训练集，这样可以用于评估模型的稳定性。

当初始数据量足够时，留出法和交叉验证法更常用，因为自助法产生的数据集和初始数据集的分布不同，可能会引入估计偏差，但是当数据量较小时，自助法更常用。

调参与性能度量

常用的性能度量指标主要有：

均方误差 MSE

E (f; D) = \frac{1}{m} i = 1 \sum m (f (x_{i}) - y_{i})^{2}

错误率 ER

E (f; D) = \frac{1}{m} i = 1 \sum m I (f (x_{i}) \neq = y_{i})

精度 ACC

A CC (f; D) = \frac{1}{m} i = 1 \sum m I (f (x_{i}) = y_{i})

线性模型

线性模型是指通过对样本属性的线性组合来作为模型的输出值，线性模型的形式化定义如下：

f (x) = w^{T} x + b

线性回归

对于离散属性，如果存在序关系，则通过连续化将其转化为连续值，对于无序属性，通常使用one-hot编码。根据之前提到的线性模型定义，线性回归的目标是找到一组参数w，b，使得模型的输出值与真实值之间的均方误差最小。通常使用RME作为损失函数，基于该方法来求解的方法被称为最小二乘法，使得所有样本到直线上的欧式距离之和最短。

求解这一过程被称为最小二乘参数估计。分别对RME求关于w,b的偏导求得极值点，进而得到最优解。

基于线性回归，如果模型中存在多个特征，可以使用多元线性回归，如果模型预测值并不为线性组合，则可进一步表示为：

y = g^{- 1} (w^{T} x + b)

该模型被称为 广义线性模型，其中g称为联系函数，通常使用指数函数，对数函数等。

对于分类任务，需要将模型输出值进行映射。通常使用某种单调可微的函数，比如sigmoid函数，将分类时为正类的可能性与作为反类的可能性之比称为几率。将几率取对数得到对数几率，对数几率的分类模型称为对数几率回归。

训练

线性判别分析

LDA也被称为Fisher判别分析。其思想为：将所有样例投影到一条直线上，使得同类样例的投影点尽可能接近，不同类样例的投影点尽可能远离。

多分类

多分类通常采用一对一，一对多或者多对多的方式，一对一通过将每N个类别两两配对产生N(N-1)/2个分类器，最终通过投票产生最终结果。一对多则是将一个类的样例作为正例，其他类别作为反例，总共训练N个分类器，其中每个分类器拥有一个预测置信度，最终结果取得分最高的类别。多对多则是将若干类作为正类，其他类作为反类，然而正反类的构造需要特殊的设计。

总结

决策树

决策树是一种树形结构，其中每个非叶子节点表示一个特征，每个分支代表一个特征的取值，每个叶子节点表示一个类别。决策树的生成是一个递归过程，通过对数据集进行划分，使得每次划分后的数据集尽可能属于同一类别，同时划分后的数据集尽可能的纯净，也就是提高节点的纯度。

信息熵

信息熵可以用于度量样本集合纯度，信息熵越小，样本集合的纯度越高。信息熵的定义如下，设当前样本集合D中第k类样本所占的比例为 $p_{k}$ ，则D的信息熵定义为：

E n t (D) = - k = 1 \sum K p_{k} lo g_{2} p_{k}

考虑不同分支包含的样本数不同，可以给予百分比权重，得到属性对样本集的信息增益：

G ain (D, a) = E n t (D) - v = 1 \sum V \frac{∣ D ^{v} ∣}{∣ D ∣} E n t (D^{v})

信息增益越大，说明使用属性a划分后的纯度提升越大，每次划分分支时可以选择信息增益最大的属性作为划分属性。信息增益对于可取值数目较多的属性有所偏好。

增益率

增益率用于减少信息增益对可取值数目较多的属性的偏好，增益率定义如下：

G ain_r a t i o (D, a) = \frac{G ain ( D , a )}{I V ( a )}

其中IV(a)为属性a的固有值，定义为：

I V (a) = - v = 1 \sum V \frac{∣ D ^{v} ∣}{∣ D ∣} lo g_{2} \frac{∣ D ^{v} ∣}{∣ D ∣}

基尼指数

G ini (D) = 1 - k = 1 \sum K p_{k}^{2} . G ini_in d e x (D, a) = v = 1 \sum V \frac{∣ D ^{v} ∣}{∣ D ∣} G ini (D^{v})

基尼指数越小，样本集合的纯度越高。

剪枝

剪枝用于提升决策树的泛化性能，分为预剪枝与后剪枝两类，预剪枝是在生成过程中，对每个节点进行评估，如果不能带来泛化性能提升，则作为叶节点；后剪枝用于训练完成后，自底向上地对非叶节点评估，如果作为叶节点能提高泛化性能，则进行剪枝，替换为叶节点。

使用验证集与测试集判断是否能够提高泛化性能，

数据处理

如果属性值为连续值，则考虑连续值离散化，最简单的方法是使用二分法。

考虑数据集中数据属性缺失的情况，

多变量决策树

总结

神经网络

神经网络基于M-P神经元模型，将神经元考虑为n元线性函数，为

y = f (i = 1 \sum n w_{i} x_{i} - θ)

这表示神经元接收n个其他神经元传递而来的输入信号，经过带有权重的连接进行传递，最终与阈值theta比较，并通过激活函数产生输出。激活函数负责将给定输入映射为0与1分别表示抑制与激活。常用的函数有Sigmoid函数。神经网络的学习就是参数的确定。

感知机

感知机是一种早期神经网络，由两层神经元组成，也就是输入层-输出层，其训练过程为，对于样本(x,y),如果输出为y1，则有

w_{i} = w_{i} + δ w_{i} δ w_{i} = a (y - y 1) X_{i}

其中a被称为学习率。

感知机只有输出层使用激活函数，这类感知机只能解决线性可分问题。对于非线性可分，则需要添加在输出层与输入层间添加隐藏层，隐藏层同样使用激活函数。

多层前馈神经网络由若干层神经元组成，同层神经元不相互连接，不跨层连接，每两层神经元之间全互联。

误差逆传播算法

BP算法就是误差逆传播算法，可用于多种神经网络，但BP网络通常是指使用BP算法训练的多层前馈神经网络。

BP算法是一种迭代学习算法，每一轮使用广义感知机学习规则对参数进行更新估计，基于梯度下降策略，以目标负梯度对参数进行调整。

实践

使用CPP基于MNIST手写多层前馈神经网络，网络组成结构如下：

（784，784）输入层
（784，256）隐藏层SIDMOID
（256，128）隐藏层SIDMOID
（128，10）输出层SOFTMAX

损失函数为交叉熵，使用BP算法优化参数。

CNN

CNN全称卷积神经网络，专门用于处理网格数据，比如图形。CNN较NN增加了卷积层与池化层。卷积层用于特征提取；池化层用于减少特征维度，降低计算量。作为一种从20年前出现的里程碑类的神经网络（），其中稀疏表示，参数共享，等变表示等思想最为重要。

总结

支持向量机

分类问题的目标是在特征空间中寻找一个超平面，使得所有类别的样本都能被正确分类。该超平面可以表示为：

w^{T} x + b = 0

其中w为法向量，b为截距。对于线性可分问题，存在无穷多个超平面，SVM的目标是找到间隔最大的超平面。

下面是一些SVM的基本概念：

样本距离: 样本到超平面的距离,计算方式为：

r = \frac{∣ w ^{T} x + b ∣}{∣∣ w ∣∣}

支持向量: 距离超平面最近的样本点,并且使得SVM模型成立。
间隔: 两个异类支持向量之间的距离。

为了最大化间隔，SVM的目标函数为：

w, b max \frac{2}{∣∣ w ∣∣}

约束条件为：

y_{i} (w^{T} x_{i} + b) \geq 1

上述为SVM的基本型,对于约束极值问题，可以使用拉格朗日乘子法进行求解，即

L (w, b, α) = \frac{1}{2} ∣∣ w ∣ ∣^{2} - i = 1 \sum m α_{i} (y_{i} (w^{T} x_{i} + b) - 1)

对w,b求偏导，得到：

w = i = 1 \sum m α_{i} y_{i} x_{i} 0 = i = 1 \sum m α_{i} y_{i}

将上述结果代入拉格朗日函数，得到对偶问题：

α max i = 1 \sum m α_{i} - \frac{1}{2} i = 1 \sum m j = 1 \sum m α_{i} α_{j} y_{i} y_{j} x_{i}^{T} x_{j}