2024机器学习

type

status

date

slug

summary

绪论

经典定义：利用经验改善系统自身的性能。

所谓经验，通常表现为计算机中的数据。

DMP，即D（Training Data）+ M（Model）+ P（Prediction）。

ML 的主要任务，就是从数据中学习出一个模型，然后利用这个模型对未知数据进行预测.

假设我们有x和y两个变量，其中y是我们想要预测的变量（或者说标签 label），x是用来预测y的变量。那么，我们可以将x和y的关系表示为y=f(x)，其中f是一个函数。我们的目标就是找到这个函数f

ML 可以分为：

监督学习（Supervised Learning）：训练数据包含了标签 label，即我们知道x和y的关系，我们的目标就是找到这个关系f。

分类（Classification）：y是离散的
回归（Regression）：y是连续的

无监督学习（Unsupervised Learning）：训练数据不包含标签 label。

聚类（Clustering）：将数据分成若干类。
异常检测（Anomaly Detection）：检测数据中的异常。

模型选择与评估

模型选择（Model Selection）是：

从一组候选模型中选择统计模型的任务（比如选择 SVM、Logistic 回归等等）

或者为同一机器学习模型选择不同的超参数（比如选择 k-means 中的 k）

经验误差和过拟合

误差（Error）：样本的实际输出与预测输出之间的差异。

经验误差（Training / Empirical Error）：模型在训练集上的误差。

泛化误差（Generalization Error）：模型在未见过的样本上的误差。

我们的目标是：一个泛化误差最小的模型。

经验误差并非越小越好，因为会过拟合（overfitting）。

过拟合（Overfitting）：模型在训练集上表现很好，但是在测试集上表现很差。其本质是，模型描述了误差或噪声，而不是潜在的关系。

当模型过于复杂时，例如相对于观测值数量而言参数过多，就会发生过拟合。

解决方法：正则化；早点停下来。

正则化（Regularization）：在训练过程中向损失函数添加惩罚项。这种惩罚会阻止模型变得过于复杂或具有大的参数值，有助于控制模型对训练数据中噪声的拟合能力。
这能够防止过拟合，并提高模型泛化性能。
正则化方法包括L1和L2正则化、drop out、数据增强、提前停止等。通过应用正则化，模型变得更加健壮，并能更准确地预测未见过的数据。
L1和L2正则化是最常见的正则化类型。它们通过添加另一个 term（即正则化项）来更新一般的成本函数。L2正则化通过迫使权重向零衰减来降低权重矩阵的值，从而减少过拟合。L1正则化通过对权重的绝对值进行惩罚，可以将权重减少到零，适用于模型压缩。
Dropout是一种有趣的正则化技术，通过在每次迭代中随机选择一些节点并删除它们及其所有的输入和输出连接来引入更多的随机性。

早点停下来（Early Stopping）：主要思想是在模型开始过拟合之前停止训练，从而防止模型在训练数据上表现良好但在新数据上表现不佳。
三种主要方法：
在预设的训练轮数后停止训练。
当损失函数更新变得很小时停止训练。
当验证损失函数开始增加时停止训练。

相对的，有欠拟合（Underfitting）的概念，即：当统计模型或机器学习算法无法捕获数据的潜在趋势时，就会发生欠拟合。

例如，当将线性模型拟合到非线性数据时，就会发生欠拟合。（简单来说就是直线怎么拟合得了曲线那么复杂的情况）这样的模型预测性能较差。

解决方法：增加模型复杂度；增加特征数量等。

对于决策树：扩展分支。

对于神经网络：更多次的训练。

评估方法

在实践中，我们会考虑模型的泛化能力、耗时、存储消耗、可解释性，最后做出决定。

By the way，我们将测试误差（Test Error）定义为模型在测试集上的误差，将测试误差视作泛化误差的近似。因为测试集（Test Set）是模型未见过的数据，和训练集（Training Set）互斥，所以测试误差可以近似地表示模型在未见过的数据上的误差。

获取测试集

留出法（hold-out）

比如数据集，取80%训练，20%测试
要求：

保证数据分布一致性（例如，分层采样）
多次重复划分（例如100次随机划分）
测试集不宜过大、过小（一般可能说 1/5 到 1/3 为宜）

交叉验证法（cross validation）

or rather, k-fold cross validation（k-折交叉验证法）
将数据集分为k个子集，做k轮，每轮取一个子集作为测试集，k−1个训练集
为了避免切分子集的影响，随机切分 m 种
留一法（leave-one-out, LOO）：为了逼近，就切分k个子集，取1个做测试集

LOO 不受分区方法的影响，也更加准确。但是当数据集较大时，计算量会很大。

自助法（bootstrap）

基于“自助采样”（bootstrap sampling），又称“有放回采样”“可重复采样”

性能度量

性能度量（performance measure）是衡量模型泛化能力的评价标准，反映了任务需求。

对于回归（regression）任务，常用均方误差（mean-square error, MSE）：

其中，f是模型，D是数据集，m是样本数量，是第i个样本，是第i个样本的标签。

对于分类任务（classification），常用错误率（error rate）和精度（accuracy）。

错误率：

其中，I是指示函数（indicator function），当 f(xi)≠yi时，I的值为1，否则为0。

精度：

在信息检索和网络搜索领域，我们经常需要 Precision（查准率）和 Recall（查全率）。

查准率（Precision）：预测为正的样本中，真正为正的样本的比例。

查全率（Recall）：真正为正的样本中，预测为正的样本的比例。

分类结果混淆矩阵：

(T:true F:fake P:positive N:negative)

那么查准率：

查全率:

当P=R时，称这样的点为平衡点.

开销敏感的错误率

二分类代价矩阵如下:

Cost-Sensitive Error Rate（成本敏感错误率）是一种用于衡量机器学习模型在不同类别上的错误率的指标。比如对于上表，我们在预测正确的情况下显然没有代价，而对于两种预测错误的情况赋予了两个代价权重

有如下公式:

在不平衡分类问题中，对于不同类别的错误分类，我们可能会赋予不同的成本。这个公式中cost01和cost10就代表了模型在不同类别上的错误分类所带来的成本

其中,表示模型f在数据集D上,根据成本cost计算出的错误率,m表示数据集D的样本数量

表示对于数据集D中属于正类别的样本,如果模型f对样本的预测结果与真实标签不一致,就将这个错误分类的成本计入中总成本中

同样的,表示对于数据集D中属于负类别的样本,如果模型f对样本的预测结果与真实标签不一致,就将这个错误分类的成本计入总成本中

这样，有:

其中,表示在成本敏感的情况下,预测为正的样本中,真正为正的样本比例.表示在成本敏感的情况下,模型的错误率

FNR表示假反例率（False Negative Rate），FPR表示假正例率（False Positive Rate）。

所谓的假反例率，就是在所有真正为正(TP+FN)的样本中，被错误地预测为负的样本的比例。

所谓的假正例率，就是在所有真正为负(FP+TN)的样本中，被错误地预测为正的样本的比例；

即；而假正例率，就是在所有真正为负的样本中，被错误地预测为正的样本的比例。

显然，。这就是说，错误分成两组，一组是错误估计成了正例，一组是错误估计成了反例，因此加起来就是全部的错误.

比较检验

当我们回到性能比较的问题上来时，我们知道：

测试性能≠泛化性能

测试性能会随着测试集的不同而不同

许多的 ML 算法都有一定的随机因子

这就是为什么，在上文中，我们只说“测试性能是泛化性能的近似”。

如果在测试集上观察到学习器A优于学习器B，我们如何保证A的泛化性能在统计意义上优于B?

假设检验

假设检验（hypothesis testing）是统计学中的一个重要过程。假设检验评估关于总体的两个互斥的陈述，以确定样本数据最能支持哪个陈述。

所谓的假设（hypothesis），就是对 learner 泛化错误率分布的一些判断/猜测。

说人话就是：

首先我们取为学习器在测试集上的错误率,也就是说，如果有m个测试样本，那么就有个样本被错误分类了。

然后，我们假定学习器的泛化错误率为，那么这个学习器将m′个样本错误分类，而将剩下的m−m′个样本正确分类的概率就是

那么，在包含了m个测试样本的测试集上，泛化错误率为ϵ的学习器被测得泛化错误率为的概率为:

于是，使用二项检验（binomial test）的方法，假设:

因此我们需要讨论单边检验的拒绝域形式。当H1成立时，即时，测试错误率往往偏大，拒绝域形式为，其中k是一个正整数。

这里，是显著性水平（significance level），通常取0.01或0.05或0.1。是置信度（confidence level）。通过这个公式，我们可以计算出k的值，即临界点。

进一步求出该检验的拒绝域，当测试错误率时，拒绝H0，接受H1

t检验

t 检验（t-test）是一种用于检验两组数据平均值差异是否显著的假设检验方法。它是一种单变量分析方法，用于比较两组平均值是否显著不同.t检验的核心思想是，通过比较组间差异与组内差异来判断两组数据的差异是否显著。

很多时候我们会进行多次重复训练，得到多个错误率。假设有k个错误率：。

有平均测试错误率：

平均方差:

写出t-分布的公式:

其中，ϵ0是假设的泛化错误率，该公式服从自由度为k−1的t-分布。

t-分布用于根据小样本来估计呈正态分布且方差未知的总体的均值。t-分布的形状和自由度有关。自由度越大，t-分布越接近正态分布

t-检验是针对分布期望的检验。假设一组服从正态分布的测试误差如下:

正态分布的期望。要判断这种说法的正确性，我们可以使用 t-检验

首先，建立零假设H0和备择假设H1:

限定显著性水平

计算T统计量:

其中，s是样本标准差。样本中有n=6个样本，所以自由度为n−1=5.通过查表知道，。那么，接受假设H0，即认为是正确的

交叉验证 t 检验

对一组样本D，进行k折交叉验证，得到k个测试错误率；将两个 learner(A,B) 都分别在每对数据子集上进行训练和测试，会分别产生两组测试错误率:

对每组结果求差值:,如果两个 learner 的泛化性能相同，那么这些差值应该接近于 0。因此，可以用差值,来对假设“两个 learner 的泛化性能相同”进行 t-检验(假设均值为0)

假设检验：计算出差值样本的均值与方差 ,在显著度下，若变量大于 t 分布的临界值,则拒绝假设，即认为两个 learner 的泛化性能不同，并且选择平均错误率较小的learner。

Bias(偏差)和方差

这两个值可以描述模型的泛化性能。

然后:

Bayes(贝叶斯)分类器

问就是 Bayes 条件概率理论。

不同形式的 Bayes Rules:

对于公式,我们可以将其理解为：

:在事件B发生的条件下，事件A发生的概率；称之为A的"条件概率”或”事后概率”。

:事件A发生的概率；称之为A的“先验概率”或”边缘概率”。

:在事件A发生的条件下，事件B发生的概率；称之为B的”条件概率”或”后验概率”,某些文献又称其为在特定B时，A的似然性，因为

按这些术语，贝叶斯定理可表述为：后验概率 = (似然性*先验概率)/标准化常量

另外，比例也有时被称作标准似然度（standardised likelihood），贝叶斯定理可表述为：后验概率 = 标准似然度*先验概率

基于最小错误率的Bayes决策

在pattern classification 问题中，根据概率论中的 Bayes 公式最小化分类的误差，可以得到使错误率最小的分类规则，称为基于最小错误率的 Bayes 决策.

假设我们有一个简单的二元分类问题，我们希望根据某个样本的特征将其分为两个类别：A 和 B。我们使用一个特征x来进行分类，而x的取值范围是实数。

首先，我们需要计算在给定特征 x 的条件下，样本属于类别 A 和 B 的后验概率。根据 Bayes 定理，后验概率可以表示为:

其中，和分别是在类别 A 和 B 下特征x的条件概率，和分别是类别 A 和 B 的先验概率，是特征x的边缘概率

接下来，我们需要选择一个决策规则，使得分类错误率达到最小。通常情况下，我们会选择后验概率最大的类别作为最终的分类结果。即

如果，则将样本分类为 A 类；

如果，则将样本分类为 B 类

具体到计算方式，那就是:

PPT上如是说的

显然，Bayes 模型是一种理论模型。现实中很难获得先验概率和类别条件概率，因此需要估计它们的值.

最大似然估计

最大似然估计（Maximum Likelihood Estimation, MLE）是一种参数估计方法，用于估计模型的参数。它的基本思想是：选择使得已知数据出现的概率最大的模型参数.

在公式中,分子就是要被估计的

首先写出似然函数：

其中，D是带标签的数据集，是模型参数。是在类别的条件下，样本出现的概率。

第二步，整体取对数:

第三步，求导:

然后令导数为0，解出。这样求得的也可以写成，表示是估计值，它观察到的数据的概率最大化

朴素 Bayes 分类器

朴素 Bayes 分类器（Naive Bayes Classifier）是一种基于 Bayes 理论的简单分类器，它假设特征之间相互独立.

其中，n是类别的数量，是在给定特征x的条件下，样本属于类别的概率。

对于先验概率，如果特征是连续的，那么可以使用高斯分布来估计；如果特征是离散的，那么可以使用多项式分布来估计。

直接举例:

编号	色泽	根蒂	敲声	纹理	脐部	触感	密度	含糖率	好瓜
1	青绿	蜷缩	浊响	清晰	凹陷	硬滑	0.697	0.460	是
2	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	0.774	0.376	是
3	乌黑	蜷缩	浊响	清晰	凹陷	硬滑	0.634	0.264	是
4	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	0.608	0.318	是
5	浅白	蜷缩	浊响	清晰	凹陷	硬滑	0.556	0.215	是
6	青绿	稍蜷	浊响	清晰	稍凹	软粘	0.403	0.237	是
7	乌黑	稍蜷	浊响	稍糊	稍凹	软粘	0.481	0.149	是
8	乌黑	稍蜷	浊响	清晰	稍凹	硬滑	0.437	0.211	是
9	乌黑	稍蜷	沉闷	稍糊	稍凹	硬滑	0.666	0.091	否
10	青绿	硬挺	清脆	清晰	平坦	软粘	0.243	0.267	否
11	浅白	硬挺	清脆	模糊	平坦	硬滑	0.245	0.057	否
12	浅白	蜷缩	浊响	模糊	平坦	软粘	0.343	0.099	否
13	青绿	稍蜷	浊响	稍糊	凹陷	硬滑	0.639	0.161	否
14	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	0.657	0.198	否
15	乌黑	稍蜷	浊响	清晰	稍凹	软粘	0.360	0.370	否
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	0.593	0.042	否
17	青绿	蜷缩	沉闷	稍糊	稍凹	硬滑	0.719	0.103	否

一个测试用例:

编号	色泽	根蒂	敲声	纹理	脐部	触感	密度	含糖率	好瓜
测1	青绿	蜷缩	浊响	清晰	凹陷	硬滑	0.697	0.460	？

因此可以算出

并且有离散值的条件概率(多项式)：

而连续值的条件概率(高斯)：

那么，对于这个测试用例，我们可以得到：

正是因为，所以这个测试用例被分类为“是好瓜”

Laplace 修正

对于上面的数据集，我们观察这个例子:

编号	色泽	根蒂	敲声	纹理	脐部	触感	密度	含糖率	好瓜
测2	青绿	蜷缩	清脆	清晰	凹陷	硬滑	0.697	0.460	？

结果，数据集里面根本就没有敲声“清脆”还能是好瓜的，即:

那我们算条件概率的时候，乘了个零，不就啥也没有了吗？虽然这事挺符合数据集的（没这种例子，可能性当然为零），但是不太符合现实。因此，我们需要对这种情况进行修正。

这种修正被称为“平滑”（Smoothing），而 Laplace 修正（Laplacian Correction）就是一种经典方法。

拉普拉斯平滑的核心思想是在概率估计中引入一个小的修正值，以确保后验概率永远不会为零。这样，即使在训练数据中没有观察到某个特征，其概率也不会被计算为零，从而避免了零概率问题。

这其中，N就是特征的取值个数，Ni是第i个特征的取值个数,对于测试用例测2，就有:

这里，我们可以看到，虽然数据集里面没有敲声“清脆”还能是好瓜的，但是我们的修正之后，这个概率不再是零了。下面分母所加的2就是N，即瓜在“是否为好瓜”上有两种取值

这里呢，我们看到的3，譬如说罢，对于敲声，一共有三种，即“浊响”、“沉闷”、“清脆”。我们用 Laplace 修正后的概率去计算，就不会出现零概率的情况了.

基于最小风险的 Bayes 决策

基于最小风险的 Bayes 决策（Bayes Decision with Minimum Risk）是一种基于 Bayes 理论的分类方法，它将分类错误的损失考虑在内，选择具有最小风险的类别作为最终的分类结果。

我们假设一个有 N 个标签状态的集合：

我们还考虑了风险，即。它意味着因将误认为而造成的损失

决策树

ID3

ID3 算法是一种决策树算法，用于从一组实例中构建决策树。它基于信息增益的概念，选择信息增益（Information Gain）最大的属性来构建决策树.

所谓信息增益，就是指在得知某个条件后，信息的不确定性减少的程度。信息增益越大，意味着得知这个条件后，信息的不确定性减少的程度越大，也就是说，这个条件对于我们来说越有用。（非常像熵）

对于有n个分类的label,代表第i个类别所占比例,信息熵:

因此对于二分类来讲就是:

信息增益

总体信息熵(原始信息熵)-特征子集加权信息熵

eg:

购买	天气
是	晴天
是	晴天
否	多云
是	多云
否	雨天
否	雨天
是	雨天
是	多云
否	晴天
否	多云

计算类别分布：

购买（是）: 5
购买（否）: 5
总样本数: 10

计算概率：

P(是)=5/10=0.5
P(否)=5/10=0.5

计算信息熵：

2. 计算信息增益

信息增益（Information Gain）用于衡量通过某个特征划分数据集后，信息熵的减少程度。其计算公式为：

其中，S是原始数据集，A是特征，Sv是特征A的某个取值v的子集。

计算步骤：

我们以“天气”作为特征进行划分。

天气取值：

晴天: 4个样本（2是，2否）
多云: 4个样本（3是，1否）
雨天: 2个样本（2是，0否）

计算每个子集的信息熵：

晴天：

P(是)=2/4=0.5

P(否)=2/4=0.5

多云：

P(是)=3/4=0.75

P(否)=1/4=0.25

雨天：

P(是)=2/2=1 P(是)=2/2=1

P(否)=0/2=0 P(否)=0/2=0

计算加权平均信息熵：

计算信息增益：

总结

信息熵：原始数据集的信息熵为 1。

信息增益：通过“天气”特征划分后，信息增益为 0.276。

在这个例子里,特征子集就是”天气”这个集合,以天气的属性分成三个子集,每个子集有一个信息熵,最后加权

C4.5

引入 Gain Ratio 来度量一个 partition 是不是真的好

Gain Ratio

IV(D,a)也可以表示成,其中P(v)代表特征子集的某个特征属性占总体的比例.

如果还是以上面的例子来说.则有

Bi-partition

离散的特征值进行划分是比较简单的,但是连续的特征值不太容易划分,但是可以将连续的离散化.

C4.5 采用 Bi-partition 的方法来处理连续值的划分,也就是:

也就是说,连续值没超过某个阈值,那就给设定一个离散值,类似于二值化.

但是如何选择这个阈值呢?选不好自然会导致这个特征值出现或大或小的误差.明确目标是:选择与信息增益最高的分区相对应的阈值

比如,给定训练集,可能的分区有：

手握这个可能的阈值集合，我们希望：

其中，.简单的说,就是按照你预设的T_a计算方法,带入信息增益公式然后求解最大化问题(求函数解)

剪枝

分支过多会导致过拟合.

剪枝分为:

预剪枝(Pre-Pruning)

后剪枝(Post-Pruning)

简单来说，pre-pruning 就是在构建决策树的过程中停止添加属性；post-pruning 就是在构建决策树之后，对决策树进行剪枝。两者各有优劣，主要看剪枝后泛化性能如何.

这是直接从训练集生成的决策树.

后剪枝会看剪除某分支前后的泛化性能（其实就是看测试集上准确度如何），来决定是否要剪枝

所以，同 pre-pruning 相比，post-pruning 的优点是:

欠拟合风险较小

泛化能力通常更优

但也有缺点:后剪枝的计算开销较大(遍历每个节点还要重新测试)

缺失值

就是在训练过程中,某个实例的某个特征值(属性)为空,那怎么处理?

有两个问题:

当某些值缺失时如何选择属性

给定分区属性，如何对这些缺少属性值的示例进行分区

首先约定三个符号：

表示训练集D中，拥有属性a的样本集合

表示中，属性a的值为的样本集合

表示中label为K的样本集合

现在，我们对每个样本x赋予一个权重。

属性a上有值的样本的权重，我们设置为：

中label为K的样本的权重，我们设置为：

其中, 表示 label 的种类数。

中属性a具有值为的样本的权重，我们设置为：

其中，,V表示属性a的取值数目。然后：

简单来说就是把拥有属性a的样本集合当总集合,计算了信息增益.为了反映总体,还需要乘上有值子集的权重.这对于第一个问题的回答就是:该选还是要选,但是要乘权重用部分反映总体了

对于第二个问题，我们是这样解决的:

对于在属性 a 上有值的样本 x，我们将 x 放入其对应的子节点中，并且其权重不变（）。

对于属性 a 缺失值的样本 x，我们将其放入所有子节点中，其权重变为

直接看ppt

对有对应属性的子集计算信息熵

然后计算信息增益

然后计算有值子集的权重占比(14/17)

算出来当前节点按照纹理属性分类增益最高

这个就和上面对于问题二的描述相吻合,在不同子节点中没有值的样本权重不同

可解释性

决策树的可解释性非常好，因为它的每个节点都对应一个属性，每个分支都对应一个属性值，所以我们可以很容易地解释决策树的每个节点的含义.

不过，用决策树做 classification 的边界是与轴平行的.

因此，对于比较复杂的场景，这样的小片段（或者说小盒子）就会有很多.

决策树的优点：

可以生成可理解的规则

无需太多计算即可执行分类

清楚地表明哪些属性对于预测或分类最重要

（天然能）处理好矩形区域

缺点：

决策树可能会遭受错误传播（Error Propagation）的影响

自然，对于非矩形区域的分类效果不好

SVM

SVM（Support Vector Machine）支持向量机是一种监督学习算法，可以用于分类和回归问题。SVM 的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使得 SVM 对噪声的鲁棒性更好

线性可分SVM

原则：为了正确地对更靠近直线的新数据进行分类，直线与训练样本之间的最小距离应尽可能远

如图，将线性分类器的间隔（Margin）定义为在到达数据点之前边界可以增加的宽度。那两边的边界就是支持向量（Support Vector）。

显然，每个分类器都对应着一组 Margin 和支持向量，我们希望找到 Margin 最大的分类器。

但是SVM多数都是多维度的,因此需要定义超平面(hyperplane):.

其中w是法向量,b是偏置.对于一个样本,如果,那么属于正类

我们设Margin为,分类器为,目标是让最大化

我们将plus plane写作,将minus plane写作.

定义为minus plane上的点,则为plus plane上距离最近的点.反过来亦然

则有成立,验证如下

考虑 plus plane 上的点,那么：

同理，minus plane 上的点,有：

我们希望找到一个向量,使得在 plus plane上，也就是说，我们希望有：

展开，得到：

带入,得到：

解得：

因此给定c和w则总能找到一个,使在plus plane上

自然,要找的Margin就是:

我们注意到，参数c可以是任意的，因为我们总是能通过归一化把c从式子中消去。因此，我们的目标就变成了最大化

我们注意到：

这样，我们就可以写出：

我们原来的优化问题是：

它就转化成了：

这里之所以是,是因为边界的大小与超平面的法向量w的大小成反比,因此，最大化边界等价于最小化的平方

Lagrange 对偶

我们的优化问题是一个凸二次规划问题，可以用 Lagrange 乘子法求解.通过引入拉格朗日乘子，可以将约束条件合并到目标函数中，形成拉格朗日函数:

其中，是 Lagrange 乘数

所谓“凸二次规划问题”，就是指目标函数是凸函数，约束条件是线性的。这样的问题，可以用 Lagrange 乘子法求解.

我们希望L(w,b,α)对α最大化，对w和b最小化。因此，我们的目标可以写成:

首先，我们最大化,那么：

当时，函数中的为正。减去一个正值，意味着如果我想对最大化，那么就应该为0。

当时，函数中的为负。减去一个负值就是加上一个正值，意味着如果我想对最大化，那么就应该趋近于无穷大。

注意到，如果趋向于无穷大，那么我也别最小化了，重开吧；所以说，我们永远不能让。我们发现，这恰好满足了我们的约束条件。

对偶问题

对于任何一个 Lagrange 函数，我们都可以写出对偶函数，只带有 Lagrange 乘数作为唯一的变量。倘若的最优解存在并且可以表示为，那么的最优解也存在并且可以表示为.

于是有对偶差异:

如果,那么则说强对偶成立.此时,可以通过求解对偶问题来解决原问题.

KKT条件

对于一个凸优化问题，如果存在最优解（或者干脆说强对偶关系存在），那么这个 Lagrange 函数一定满足 KKT 条件，即：

这就是说：

所有参数的一阶导数为 0

约束条件中的函数本身要小于等于 0

Lagrange 乘数要大于等于 0

Lagrange 乘数和约束条件的函数的乘积为 0，也就是说，不论取什么值，我总要保证两者中至少有一个为 0

当这些条件被满足时，Lagrange 函数L(x,a) 的最优解与其对偶函数g(α)的最优解相等。这样，我们就可以通过求解对偶问题来求解原问题

根据KKT条件对L(w,b,α)求导，得到:

所以:

并且，我们通过先求最大值再求最小值的方式，使得函数天然就满足:

所以只需要再满足：

满足的就是支持向量,所有不在支持向量上的点,αi=0

化简过程如下:

带入上面得到的

可以得到

再代入w，转换为内积形式，得到对偶式

因此:

由于满足所有 KKT 条件，所以:

这样，我们只需要求解对偶函数的最大值即可。最终，目标函数变为:

然后么，不管是梯度下降，还是 SMO 算法，还是什么 QP（Quadratic Programming，二次规划）都可以求解α。求得了α，我们就可以求得w和b，然后就可以求得分类器了

SMO算法

SMO（Sequential Minimal Optimization）算法是一种启发式算法，用于求解二次规划问题。

SMO 算法的思想是：每次循环选择两个变量（比如 αi 和 αj），固定其他变量，针对这两个变量构建一个二次规划问题，这个二次规划问题的解应该更接近原始二次规划问题的解。这样，通过多次循环，就可以得到原始二次规划问题的解

核函数

我们之前的讨论都是在线性可分的情况下进行的，但是实际上，很多时候数据是线性不可分的。这时，我们就需要引入核函数（Kernel Function），将数据映射到高维空间中，使得数据线性可分。

这时候，对偶优化问题就变成了:

其中，ϕ(xi) 是将 xi 映射到高维空间的函数。

计算特征空间中特征向量的内积可能成本很高，因为它是高维的。所以:

我们把k(xi,xj)称为核函数（Kernel Function），如此一来，我们只要在原始空间中计算核函数的值就可以了.

例如下图

总之呢，只要我们能够计算特征空间中的内积，我们就不需要显式地进行映射.

Mercer 定理：如果一个函数 k(xi,xj)是一个对称函数，那么它就是一个（Mercer）核函数，当且仅当对于任意的 n 和 x1,x2,…,xn，矩阵 K 是对称半正定的。

其中矩阵 K 是

常用的核函数有:

线性核函数:

多项式和函数:,其中c是常数用于调整核函数的影响(通常非负),d是多项式的度数,决定了映射到特征空间的复杂度

高斯核函数:

Sigmoid核函数:

软间隔

数据带有噪声，我们往往要允许一些数据点被误分类。这时，我们就需要引入软间隔（Soft Margin）.

本质上，是说这些点不满足约束条件

引入 loss 函数:

最优化目标：

其中，C是一个超参数，用于控制误分类点的惩罚程度。这使得，前半部分仍然是最大化 Margin，而后半部分则是最小化误分类点的个数。当 C>0 时，它是一个 tradeoff 参数；当时，它是一个 hard margin SVM。

然而，是一个不凸、不连续的函数，不利于求解。因此，我们引入 hinge loss 函数

施加 hinge loss 函数后，我们的最优化目标变为：

引入松弛变量,使得:

这样，我们的最优化目标就变为：

每个都对应着一个数据点，它的值表示这个数据点的分类是否正确。如果分类正确，那么；如果分类错误，那么。换言之，表示第 i个数据点的分类错误的程度。

写出 Lagrange 函数:

其中和是拉格朗日乘子.

分别求导，使之为零，得到:

在新约束条件下的对偶问题为:

这与线性可分离情况下的优化问题非常相似，只是现在上有一个上限 C。然后也没啥，接着 SMO 求解就完了。

它的 KKT 条件是：

我们发现，对于每一个数据点 (xi,yi)，都有或者。

如果，那么该点对于 w 和 b 没有任何影响。

如果，那么该点一定是一个支持向量。这种情况下，讨论的取值范围：

，那么，该点就在 Margin 上

，那么。倘若，那么该点就在 Margin 内部；倘若，那么该点就是一个误分类点

SVR

支持向量回归（Support Vector Regression，SVR）是一种使用支持向量机（SVM）进行回归任务的方法。与传统的回归方法不同，SVR通过在训练数据中找到一个边界（支持向量），来建立一个能够尽可能包含大部分训练样本的函数。

SVR的目标是找到一个函数，使得训练样本与函数的预测值之间的差异最小化。与分类问题中的SVM不同，SVR的目标不是完全分离样本，而是在一定的容忍度内尽量拟合样本。

SVR的基本思想是将回归问题转化为一个优化问题。给定训练样本 (xi,yi)，其中是输入特征，是对应的目标值。SVR的优化目标是最小化预测值与实际值之间的误差，并尽量使得误差在一个容忍度内。

具体来说，SVR的优化问题可以表示为：

其中，w是回归函数的权重向量，b是偏置项，和松弛变量，C是正则化参数。这个优化问题的目标是最小化权重向量的范数和误差项，并通过松弛变量来容忍一定的误差。

SVR的约束条件可以表示为：

其中，是容忍度，用于控制预测值与实际值之间的最大误差

通过求解这个优化问题，可以得到最优的权重向量w和偏置项b，从而得到SVR模型。在预测阶段，SVR使用学习到的模型来预测新样本的目标值

KNN

KNN 根据数据集与邻居的相似性对数据集进行分类。

KNN 算法的基本思想是：如果一个样本在特征空间中的 k 个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。

与其他监督学习算法不同，KNN 不会从训练数据中学习显式映射，而是直接利用训练数据进行预测.

给定训练集其中,,k是类别的个数,对于新的样本,KNN的目标是找到与X最近的k个样本,然后根据这k个样本的类别来预测y的值

对于 classification 任务，KNN 的输出形式是一个离散变量，表示样本的类别。对于 regression 任务，KNN 的输出形式是一个连续变量，表示样本的数值。

KNN 需要：参数 K，以及距离度量方法（其实就是 Distance Function）

距离度量

KNN 算法中最常用的距离度量方法是欧氏距离（Euclidean Distance），它是样本特征向量的欧氏距离.即,对于和,他们之间的欧氏距离为:

除了欧氏距离，KNN 还可以使用其他距离度量方法，比如 Manhattan(曼哈顿) 距离.

Minkowski(闵考斯基) 距离是欧氏距离和 Manhattan 距离的一般化

这个公式是 m 阶 Minkowski 距离的计算式。当 m=1 时，Minkowski 距离等价于 Manhattan 距离；当 m=2 时，Minkowski 距离等价于欧氏距离。

当时，Minkowski 距离等价于 Chebyshev 距离

余弦相似度

余弦相似度是内积空间的两个非零向量之间相似度的度量，用于测量它们之间角度的余弦

Hamming 距离

Hamming 距离度量了两个 features 之间的差异。直接看例子就懂了

可见差异为2，所以 Hamming 距离为2.

可见差异为 3，所以 Hamming 距离为 3.

换而言之，Hamming 距离等价于将一个 feature 变换成另一个 feature 所需要替换的字符个数.

归一化

对于 KNN 而言，features 之间必须要进行归一化.

一种方法是：将用替换，其中是第 m 个 feature 的均值，是第 m 个 feature 的标准差。

使得每个 feature 的均值为0，标准差为1。

带权

由于 feature 间并不同等重要，因此我们可以对 feature 进行加权缩放。

其中，是第 i 个 feature 的权重。这个权重可以作为先验知识直接给出，也可以通过交叉验证（cross-validation）学习得到.

K的选择

理论上，如果可用样本数量无限，K 越大，分类效果越好，因为用上了更多的信息.当 K=1 时，KNN 可以看作是一个最近邻分类器（Nearest Neighbor Classifier）。这时，KNN 的分类结果对噪声非常敏感，因为它只考虑了一个最近邻.

较小的 K：

为每个类别创建许多小区域

噪声敏感

决策边界可能不够平滑

可能造成过拟合

较大的 K：

为每个类别创建较少的大区域

通常可以得到更平滑的决策边界

可以减少 class 间的 label 噪声

可能造成欠拟合（这就是由太过平滑的决策边界造成的）

一般来说，K是奇数，这样就可以避免平票的情况

留出法

留出法（Hold-Out）将数据集 D 划分为两个互斥的集合，一个作为训练集 S，一个作为测试集 T。在 S 上训练出模型后，用 T 来评估其测试误差，作为对泛化误差的估计

可以使用 Hold-Out 方法来选择最优的 K。一旦模型确定，我们就可以在测试集上评估模型的泛化误差

Hold-Out 方法的缺点是：只使用了一部分数据来训练模型，这样会造成模型的训练效果不够好。而且，可能会造成数据的分布变化，因此为了保证数据分布的一致性，还是分层采样比较好

K-Fold 交叉验证

K-Fold 交叉验证是将数据集 D 划分为 k 个大小相似的互斥子集，每个子集都尽可能保持数据分布的一致性。然后，每次用 k-1 个子集的并集作为训练集，余下的那个子集作为测试集，这样就可以获得 k 组训练/测试集对，从而可以进行 k 次训练和测试，最终返回的是 k 个测试结果的均值

留一法

留一法（Leave-One-Out）是 K-Fold 交叉验证的特殊情况，即k=n。这时，每个子集都只包含一个样本，这样就得到了n组训练/测试集对，从而可以进行n次训练和测试，最终返回的是n个测试结果的均值

输出的是:

维度灾难

维度灾难（Curse of Dimensionality）是指在高维空间中，数据变得非常稀疏，这会导致距离度量失效，从而影响 KNN 的分类效果。

高维时会有平时在低维空间中不会出现的问题，如：

存储复杂度

计算复杂度

采样困难

最近邻的搜索

非参数估计

etc.

复杂度优化

有用于降低复杂性的各种精确和近似方法。

对于计算复杂度，可以使用更好的数据结构，比如 KD-Tree；此外，还可以使用近似最近邻（Approximate Nearest Neighbor，ANN）算法、局部敏感哈希（Locality Sensitive Hashing，LSH）等。

KD-Tree

KD-Tree（K-Dimensional Tree）是一种用于高效存储和检索k维数据的数据结构。它是一种二叉树，每个节点代表一个k维数据点，并根据数据点在每个维度上的值将空间划分为两个子空间。KD-Tree的构建过程基于递归地选择一个维度和一个切分值，将数据点分配到左右子树中

下面是KD-Tree的构建过程的简要描述：

选择一个维度：从k个维度中选择一个维度作为切分维度。通常是按照某种规则选择，比如轮流选择或选择方差最大的维度。

选择一个切分值：在选择的切分维度上，选择一个切分值，将数据点划分到左右子树中。切分值可以是中位数、平均值或其他选择方法。

划分数据点：将数据点根据切分值划分到左右子树中。所有小于等于切分值的数据点分配到左子树，大于切分值的数据点分配到右子树。

递归构建子树：对左右子树递归地执行以上步骤，直到每个叶节点只包含一个数据点或没有数据点。

最近邻搜索是KD-Tree中最常见的操作之一。给定一个查询点，KD-Tree可以快速找到与查询点最近的数据点。搜索过程从根节点开始，根据查询点在当前维度上与切分值的关系，选择进入左子树或右子树。然后，递归地在选择的子树中执行相同的搜索过程，直到找到最近的数据点或搜索完整个树。

范围搜索是另一个常见的操作，用于找到在给定范围内的所有数据点。搜索过程类似于最近邻搜索，但在每个节点上需要考虑查询范围与切分超平面的关系，以确定是否需要进入左子树或右子树。

KNN总结:

优点：

简单直观，训练非常快，易于实施

特别适合多分类问题

凭借无限的训练数据和足够大的 K，KNN 方法效果很好

缺点：

对噪声特征敏感

即使在测试时也将所有训练数据存储在内存中

查询时速度慢：每个测试点的计算量为 O(nd)

高维时会有维度灾难

回归学习

回归任务的输出的连续的,而分类是离散的:

Regression	Classification
房价预测	性别分类
作物产量预测	电影种类
身高预测	好瓜坏瓜

回归学习的目标是学习一个预测函数f，使得尽可能接近y；同时，对于新的输入，可以预测出相应的输出y。至于这个函数，可以是线性的，也可以是非线性的。

回归是一个监督学习问题。之所以这么说，是因为我们需要有标签 yy 来指导我们的学习过程。

根据输入值的个数，回归学习可以分为一元回归（Univariate Regression）和多元回归（Multivariate Regression）；根据预测函数的形式，回归学习可以分为线性回归（Linear Regression）和非线性回归（Nonlinear Regression）。

因此可以统一写作:

其中是权重向量,b是偏置项.因此回归任务的本质就是求出最优的w和b,使预测值f(x)尽可能接近真实值y

最小二乘法

在回归任务中，经常使用最小二乘法（Least Square Method）.

定义误差：

这其中，是数据集的大小，是第i个样本的真实值，是第i个样本的预测值。那么，最小二乘法的目标就是：

注意，我们的model为,Loss function 为:

问题是如何求解最优w和b使得Loss最小呢?我们可以对w和b分别求偏导，然后令其为0，从而得到最优解。

解得:

其中，。

对于多元回归，我们可以将看作是一个向量，也是一个向量，那么就有：

模型:

其中，X是一个m×n的矩阵.因此多元回归Loss是:

其中，；

y是一个m*1的向量.对求偏导令偏导等于0,解得:

向量求偏导公式:

不过，最小二乘法的损失函数有可能会造成模型过拟合;

缺点:

解析解中的有可能不是满秩的，这时就无法求逆了，即不存在。这就是说，样本的特征数大于样本的个数，这样，就会有多个解。

所以说，想要应用最小二乘法，要求已有样本中的值比较准确，且样本的特征数小于样本的个数.

Ridge 回归与 Lasso 回归

岭回归（Ridge Regression）和Lasso 回归（Lasso Regression）都是为了解决最小二乘法的缺点而提出的，它们都属于线性回归

模型的函数是不变的(上文中给出的模型函数是普适的),loss的形式略有区别

中：

y是目标变量（或因变量）的向量，包含了观测到的实际值。

X是自变量（或特征）的矩阵，包含了观测到的特征值。

是模型的参数向量，用于拟合自变量和目标变量之间的关系。

是正则化参数，用于控制正则化项的强度。

对于上面的公式:

朴素线性回归（Ordinary Least Squares, OLS）：朴素线性回归使用最小二乘法来拟合数据。损失函数是目标变量与预测变量之间的差异的平方和。公式中的表示目标变量与预测变量之间的残差平方和。

Ridge 回归：Ridge 回归是一种带有L2正则化的线性回归方法。它在最小二乘损失函数的基础上添加了正则化项，以限制参数的大小。正则化项是参数向量的L2范数的平方。通过引入正则化项，Ridge 回归可以减小参数的方差，从而降低过拟合的风险。正则化参数控制正则化项的强度，较大的值会增加正则化的影响。

Lasso 回归：Lasso 回归是一种带有L1正则化的线性回归方法。与Ridge回归类似，Lasso回归也在最小二乘损失函数的基础上添加了正则化项。不同之处在于，Lasso回归使用参数向量的L1范数作为正则化项，即。L1正则化倾向于产生稀疏解，即将某些参数置为零，从而实现特征选择的效果。正则化参数控制正则化项的强度，较大的值会增加正则化的影响。

Ridge 回归和 Lasso 回归可以防止模型过拟合，也可以解决样本的特征数远超过样本数的问题。

对 Ridge 回归的 Loss function 求偏导，令其为0:

解得:

有了的加持,自然整个矩阵就是满秩的

对于Lasso回归,L1正则是

则是中的每个权重值(L1范数，定义为参数向量中各个元素绝对值的和),因此这是个常数没有导数,所以使用近端梯度下降法（Proximal Gradient Descent Method），来最小化 Lasso 回归的 Loss function.因此解析解为:

其中，L是 Lipschitz 常数，是Loss function。所谓 Lipschitz 常数，可以简单认为是一个大于零的常数。

Lasso 回归可以解决特征数大于样本数的问题。

然而，Lasso 回归容易产生稀疏解（Sparse Solution）。稀疏解指的是模型参数向量中的某些元素被压缩为零，从而实现特征选择（Feature Selection）的效果.

L1正则化项的特点是在优化过程中促使某些参数变为零。这是因为L1正则化项在参数空间中的等值线是由菱形构成的，而不是圆形（L2正则化项的等值线是圆形）。因此，当优化算法在最小化损失函数的同时，受到L1正则化项的影响，它会倾向于将某些参数压缩为零，从而实现特征选择。

通过产生稀疏解，Lasso回归可以帮助我们识别和选择对目标变量具有显著影响的特征。这对于处理高维数据和特征选择非常有用。通过将某些特征的系数置为零，Lasso回归可以简化模型，减少过拟合的风险，并提高模型的解释性

深度学习

模仿生物神经元的结构,生物上的神经元就是一个计算单元，通过输入线获取大量输入并进行一些计算，然后通过轴突将输出输出到其他节点或大脑中的其他神经元.

M-P 神经元模型就是这样的一个模型，它接收n个输入信号，每个输入信号通过带权重的连接线传递给神经元，神经元将所有输入信号的加权和作为输入，通过激活函数f计算输出y=f(z)

激活函数

激活函数（Activation Function）是神经网络中的一个重要组成部分，它决定了神经元的输出是否被激活。激活函数的输入是神经元的加权和 z，输出是神经元的输出 y。

激活函数的作用是引入非线性因素，使得神经网络可以拟合非线性函数。如果没有激活函数，神经网络的输出将是输入的线性组合，无法拟合非线性函数。

激活函数的种类有很多，常见的有 Sigmoid 函数、Tanh 函数、ReLU 函数等。

sigmoid 函数和 tanh 函数在深度学习中已经不常用了，因为它们的梯度在接近饱和区域时会变得非常小，从而导致梯度消失的问题。而且，sigmoid 输出不是以零为中心的.

与 sigmoid/tanh 函数相比,ReLU极大地加速了随机梯度下降的收敛,且与涉及昂贵运算（指数等）的 tanh/sigmoid 神经元相比，ReLU 可以通过简单地将激活矩阵阈值设置为零来实现.

感知器

感知器（Perceptron）是一种简单的神经网络模型，它是由两层神经元组成的单层前馈神经网络。感知器的输入层接收输入信号，输出层产生输出信号。感知器的输出信号是由输入信号加权和经过激活函数计算得到的

这是一种线性分类器。如果训练集是线性可分的，那么感知器就保证收敛。

Perceptron 的缺陷：单层 Perceptron 只能学习线性可分离模式。

多层感知器MLP

顾名思义,是多个感知器组合,是一种前馈神经网络,可以解决非线性分离问题.

在全连接层中，每个神经元都连接到前一层中的每个神经元，并且每个连接都有自己的权重。

所谓前馈（Feedforward），就是指神经网络的信息流只能从输入层流向输出层，而不能从输出层流向输入层。在此网络中，信息仅沿一个方向移动，即向前移动，从输入节点经过隐藏节点（如果有）并到达输出节点。网络中不存在循环或环路。

MLP 的缺点：就内存（权重）和计算（连接）而言非常昂贵

反向传播

反向传播，即 Back Propagation。

1986年，提出了多层感知器（MLP）的BP算法（反向传播算法），利用 Sigmoid 激活函数进行非线性映射，有效解决了非线性分类和学习的问题.

虽然多层感知器也可以一定程度上解决非线性问题,但多层结构是通过组合简单的非线性函数来构建更复杂的非线性决策边界(类似于样条曲线是组合多个多项式插值曲线),泛化能力并不很好,因此需要引入激活函数

再者说,上文中提到”前馈”的概念,也就是没有回头路,而反向传播就是提供了可以从输出层到输入层的递进:从输出层开始,将误差信号逐层向前传播,利用链式法则计算每一层的权重和偏置的梯度,使用梯度下降法更新网络的权重和偏置参数.

训练过程

神经网络的学习过程是根据训练数据来调整神经元的连接权值以及每个功能神经元的阈值。

在训练神经网络时，一个 epoch 意味着完整训练集的一次传递。通常它可能包含一些迭代。

通常我们将训练集分成 batches，每个 epoch 都会遍历整个训练集。每次 iteration 都会跑个 batch。

每一个 epoch 后，我们都会在 validation set 上测试一下模型的性能。

随机梯度下降（Stochastic Gradient Descent，SGD）意味着，基本上，我们使用 1 个样本的损失来更新每次迭代的参数。

批量梯度下降（Batch Gradient Descent，BGD）意味着，我们在每次迭代时使用训练集中所有示例的损失平均值。

小批量梯度下降（Mini-Batch Gradient Descent，MBGD）意味着，我们在每次迭代时使用训练集中的 n 个样本（而不是 SGD 中的 1 个样本）

梯度下降

核心要义是更新参数,为了让loss最小化.

梯度的方向是函数f在当前点的最大方向导数的方向，而梯度的模是方向导数的最大值

简单的说,上文中最优化w和b两个参数的时候使用的是求偏导的计算,但是大多数情况下损失函数都是一个复杂的非线性函数,直接求偏导有可能根本求不出来(回归问题的非满秩情况),以及有局部最优解问题.一次不如在每次训练的过程中向损失函数降低的方向走,走着走着就到最小值了.

而使用梯度是为了让函数快速收敛,梯度是f在当前点的最大方向导数的方向,那么梯度的反向就是最快下降方向了,顺着梯度的反方向移动一小步。这个移动的步长由学习率控制

步长过大可能会导致算法在最小值附近来回跳跃,无法收敛到最优解,甚至可能会导致算法发散,损失函数不断增大

步长过小会使得算法收敛速度非常慢,需要大量的迭代才能达到最优解,在高维空间中,小步长更新可能会陷入局部最优解,无法逃脱.

softmax

Softmax 函数是一种归一化指数函数，它将n维实数向量z映射到n维实数向量σ(z)，其中每个元素的范围是(0,1)，并且所有元素的和为1.

Softmax 函数常用于多分类问题的输出层，用于将神经网络的输出转换为概率分布.可以使用概率分布优化训练过程

Softmax 函数也用作神经网络的输出层激活函数

CNN

卷积神经网络（Convolutional Neural Network，CNN）是一种前馈神经网络，它的人工神经元可以响应一部分覆盖范围内的周围单元，对于大型图像处理有出色表现。

主要有三个关键概念：

Receptive Field（感受野）：神经元对输入数据的局部区域。

Parameter Sharing（权值共享）：在一个特征图中，所有神经元都使用相同的权重和偏置。

Pooling（池化）：通过减少特征图的尺寸来减少参数数量。

对于 Receptive Field，每个隐层节点只连接到图像某个局部的像素区域，从而大大减少需要训练的权值参数。（和 MLP 不同）而对于 Parameter Sharing，每个隐层节点都使用相同的权值和偏置，这样可以大大减少需要训练的权值参数。

对于 Pooling，它可以减少特征图的尺寸，从而减少参数数量。虽然尺寸减少，但是主要特征仍然保留。Pooling 本质上是一种 subsampling。

CNN 的主要结构是：

卷积层

这张图详细描述了卷积层的工作原理。主要包含以下几个关键点:

输入图像大小: 输入图像大小为 N x N。

卷积核(滤波器): 卷积核大小为 F x F，包含可训练的权重参数。

卷积操作: 卷积核在输入图像上滑动(stride=1)进行卷积运算,得到输出特征图。

输出特征图大小计算:

输出特征图大小 = (N - F) / S + 1

当 N=10, F=3, S=2 时, 输出特征图大小 = (10 - 3) / 2 + 1 = 4.5

可训练参数:

卷积核中的权重参数是可训练的, 即"Trainable Parameters"。

集成学习

集成学习（Ensemble Learning）是一种机器学习范式，它通过将多个学习器进行组合来解决单一预测问题。集成学习的目标是将多个学习器组合成一个预测模型，以获得比单个学习器更好的泛化能力。

集成的方式，总体来说可以分为：

Boosting

Bagging

集成学习：

同质集成（homogeneous ensemble）：集成中的所有学习器都是同一模型生成的。

异质集成（heterogeneous ensemble）：集成中的学习器可以是不同的模型生成的。

弱学习器（weak learner）：在学习过程中，学习器的性能比随机猜测略好的学习器。

基础学习器越准确、越多样化，集成就越好。（即好而不同）然而，基础学习器的“准确性”和“多样性”是相互矛盾的。

也就是说,准确性高的基础学习器往往具有相似的学习模式,缺乏多样性,而多样化的基础学习器可能会牺牲一定的准确性.因此集成学习的优势和目的就在于集成多个准确且互补的基础学习器,可以提高整体的预测性能.

并行方法

与电路一样可以有并行和串行.并行方法（Parallel Methods）是一种集成学习方法，它通过训练多个基础学习器来构建集成模型。并行方法的基本思想是，训练多个基础学习器，然后将它们组合成一个集成模型。并行方法的优点是易于实现，但它的缺点是基础学习器之间的依赖性。

Bagging

Bagging（Bootstrap Aggregating）是一种并行的集成方法，旨在通过构建多个基学习器并对它们的预测进行组合来改善模型的性能。Bagging的基本思想是通过自助采样（Bootstrap Sampling）和聚合（Aggregation）来减少模型的方差

Bagging 的基础是通过使用一种名为 bootstrap 的统计技术获得与原始训练集 L 大小相同的不同训练集

所谓 bootstrap，就是从原始训练集 L 中随机采样m个样本，然后将这m个样本放回，再从中随机采样m个样本，重复这个过程m次，最终得到m个大小为m的训练集。这个过程就是 bootstrap。它使得训练集Li每一个都带有和原数据集L相比略有不同的特征。

很明显的,很有可能原始数据集中的一些样本会被重复抽取,那么有以下公式:

这个公式是用来计算在Bootstrap采样过程中,每个样本被选中的概率.也就是说,在大量的Bootstrap采样过程中,每个原始样本被选中的概率趋于 63.2%。这就是所谓的"Out-of-Bag"样本比例.因此每个训练子集都能有原数据集2/3作训练集,1/3的数据做测试集,则不需要再划分.

另外，Bagging 可以减小模型的方差。

随机森林

随机森林（Random Forest）是一种集成学习方法，它通过构建多个决策树并对它们的预测进行组合来改善模型的性能。随机森林的基本思想是通过随机选择特征子集来减少模型的方差。

随机森林是对 Bagging 的改进，它的 base learner 是决策树。

随机森林有放回构造训练集(bootstrap)；随机选取m个特征构建决策树。同朴素的决策树不同，随机森林引入随机属性扰动，使得每棵树的训练集不同，从而使得每棵树的结构不同；并且，随机森林的每棵树都是完全生长的，不进行剪枝。

朴素决策树在每个节点上选择最优的特征进行划分。

随机森林在每个节点上随机选择一部分特征,然后从中选择最优的特征进行划分。这就是"随机属性扰动"的含义。

随机属性扰动增加了决策树之间的多样性,提高了集成的准确性,而且即使某些特征不重要,随机森林也能从中挖掘出有价值的信息

串行方法

串行方法依赖于基学习器之间的顺序关系。串行方法的基本思想是通过顺序训练多个基学习器，每个基学习器都专注于先前迭代中预测错误的样本。串行方法的优点是基础学习器之间的依赖性较低，但它的缺点是易于过拟合（当然，这意味着串行方法可以减小模型的偏差）。

Boosting

在集成学习中，串行方法是一种通过顺序训练多个基学习器的方法。其中，Boosting是一种常见的串行集成学习方法。

Boosting的基本思想是通过迭代训练多个弱学习器，每次迭代都根据前一轮的预测结果来调整样本的权重，使得基学习器更关注先前迭代中预测错误的样本。通过这种方式，Boosting可以逐步减小模型的偏差，并提高模型的准确性。

下面是Boosting的基本步骤：

初始化样本权重：将每个样本的权重初始化为相等值，通常为1/N，其中 N 是样本数量。

迭代训练基学习器：在每一轮迭代中，根据当前样本权重训练一个基学习器。训练过程中，样本的权重会根据前一轮的预测结果进行调整，即被错误预测的样本会被赋予更高的权重。

更新样本权重：根据当前基学习器的预测结果，更新每个样本的权重。被正确预测的样本权重会减小，而被错误预测的样本权重会增加。

组合基学习器：将每个基学习器的预测结果按照一定的权重进行组合，通常是通过加权投票或加权平均的方式。

重复迭代：重复步骤2至步骤4，直到达到预定的迭代次数或满足停止条件。

最终，Boosting通过组合多个基学习器的预测结果，将它们的优势进行整合，得到一个更强大的集成模型。由于每个基学习器都专注于先前迭代中预测错误的样本，Boosting可以逐步减小模型的偏差，并提高整体模型的准确性。

常见的Boosting算法包括AdaBoost（Adaptive Boosting）、Gradient Boosting和XGBoost（eXtreme Gradient Boosting）等。它们在迭代过程中采用不同的策略来调整样本权重和基学习器的权重，以进一步提高模型的性能。

AdaBoost

在上文描述的五步boosting中,adaboost完成第四步的方法是根据每个弱分类器的分类准确率,计算它在最终强分类器中的权重(自然准确率高的弱分类器会被赋予更高的权重),组合的方式是加权求和

adaBoost的基学习器是决策树桩(只有一个节点的决策树),下图展现了如何调整权重以及如何加权求和的过程

Fusion 策略

也就是如何将几个基学习器的结果组合起来.

平均

也就是加和平均

加权平均：

其中：

一般而言，在个体学习器性能相差较大时宜使用加权平均法，个体学习器性能相近时宜使用简单平均法。

投票

简单的说,就是少数服从多数,众多学习器给出的结果里面哪个呼声最高就按哪个走.

学习器的预测结果是类别标签集合中的一个，投票法的基本思想是选择预测结果最多的类别标签作为集成模型的预测结果。

我们先约定在样本上的预测结果是，其中 是在样本x上预测为类别标签的输出。

那就应该是二进制的只有0和1,因为上面的描述方式中”样本x上预测为类别标签的输出”应该只有是或不是的结果吧

绝对多数投票法

即 Majority Voting，它的基本思想是选择预测结果最多的类别标签作为集成模型的预测结果:

其中，l是类别标签的数量

相对多数投票法

即 Plurality Voting，它的基本思想是选择预测结果最多的类别标签作为集成模型的预测结果.

相对多数投票法(Plurality Voting)只要获得最多票数就能胜出,不需要过半数票; 绝对多数投票法(Majority Voting)要求获得超过半数(50%+1)的票数才能胜出;

加权投票法

即 Weighted Voting，它其实就是 Plurality Voting 的加权版本

其中，是学习器的权重。

多样性度量

显然，如果个体学习器的准确率越高，多样性越大，则集成越好。

误差-分歧分解（Error-Diversity Decomposition）是一种用于分析集成学习器性能的方法，它将集成学习器的误差分解为偏差、方差和分歧三个部分。

其中，E 就是集成误差;

是个体学习器泛化误差的加权均值。

是个体学习器的加权差异性。

多样性增强

在集成学习中需有效的生成多样性大的个体学习器，一般思路是在学习过程中引入随机性。

数据样本扰动

输入属性扰动

输出表示扰动

算法参数扰动

数据样本扰动

给定初始数据集，可从中产生出不同的数据子集，再利用不同的数据子集训练出不同的个体学习器。数据样本扰动通常是基于采样法：Boosting、Bagging。

这对于不稳定基学习器（决策树、神经网络...）很有效。

输入属性扰动

对于稳定基学习器（LDA、SVM、KNN...），从初始属性集中抽取出若干个属性子集，基于每个属性子集训练一个基学习器。

对包含大量冗余属性的数据，在子空间中训练个体学习器不仅能产生多样性大的个体，还会因属性数的减少而节省时间开销。

输出表示扰动

将原任务拆解为多个可同时求解的子任务或者是将分类输出转化为回归输出后构建个体学习器。

算法参数扰动

基学习算法一般都有参数需要设置，例如神经网络的神经元数，初始连接权值等，通过随机设置不同的参数。往往可产生差别较大的个体学习器

题目

Q：试分析随机森林为什么比决策树bagging集成的训练速度更快？

A：随机森林是一种集成学习方法，它由多个决策树组成。相比于单个决策树的bagging集成，随机森林在训练速度上通常更快，这主要归因于以下几个方面：

并行化处理：随机森林中的决策树可以并行生成，每个决策树都是独立训练的。这意味着在拥有多个处理器或多个计算节点的情况下，可以同时训练多个决策树，从而加快训练速度。相比之下，决策树的bagging集成通常是串行生成的，每个决策树都依赖于前一个决策树的结果，无法并行化处理。

特征子集采样：随机森林在生成每个决策树时，对于每个节点的特征进行随机子集采样。这意味着每个决策树只使用了部分特征进行训练，而不是使用全部特征。这种特征子集采样可以减少每个决策树的计算量，进而提高训练速度。相比之下，决策树的bagging集成通常使用全部特征进行训练。

数据子集采样：随机森林在生成每个决策树时，对于每个节点的训练样本进行随机子集采样。这意味着每个决策树只使用了部分训练样本进行训练，而不是使用全部训练样本。这种数据子集采样可以减少每个决策树的计算量，进而提高训练速度。相比之下，决策树的bagging集成通常使用全部训练样本进行训练。

综上所述，随机森林通过并行化处理、特征子集采样和数据子集采样等技术手段，能够在训练过程中减少计算量，从而提高训练速度。

Q：了解 GBDT、XGBoost 原理

A：GBDT（Gradient Boosting Decision Trees）是一种集成学习算法，它通过组合多个决策树来构建一个强大的预测模型。XGBoost（eXtreme Gradient Boosting）是GBDT的一种优化实现，它在GBDT的基础上进行了改进，提供了更高的性能和可扩展性。

GBDT的原理如下：

初始化模型：将所有样本的预测值初始化为一个常数，通常为目标变量的均值。

迭代训练：每次迭代中，GBDT通过拟合一个新的决策树来减少当前模型的残差。它通过计算当前模型对每个样本的预测值与实际值之间的残差，然后用这些残差作为新的目标值来训练一个新的决策树。

更新模型：将新生成的决策树与当前模型进行加权组合，得到一个更新后的模型。为了避免过拟合，每棵树的贡献通过一个学习率进行缩放，通常小于1。

重复迭代：重复步骤2和步骤3，直到达到预定的迭代次数或满足停止条件。

GBDT的优点包括：

能够处理各种类型的特征，包括连续特征和离散特征。

能够自动捕捉特征之间的非线性关系。

在处理缺失值时具有鲁棒性。

可以灵活处理不同类型的损失函数。

XGBoost是对GBDT的改进，它在GBDT的基础上引入了一些新的技术和优化：

正则化：XGBoost引入了正则化项，包括L1正则化和L2正则化，用于控制模型的复杂度，防止过拟合。

列抽样：XGBoost支持对特征进行列抽样，这样每次训练决策树时只使用部分特征，可以提高模型的泛化能力和效率。

并行计算：XGBoost使用多线程进行并行计算，加快了模型的训练速度。

缺失值处理：XGBoost能够自动处理缺失值，无需对缺失值进行特殊处理。

特征权重：XGBoost可以计算特征的重要性，帮助理解模型的预测过程。

聚类算法

聚类（Clustering）是一种无监督学习方法，它将数据集中的样本划分为若干个互不相交的子集，每个子集称为一个簇（Cluster）。聚类的目标是使得簇内的样本尽量相似，而簇间的样本尽量不同。

所谓无监督，就是说聚类任务的训练数据没有标签，也就是说，我们不知道训练数据的真实类别。我们在聚类任务中，只需要将训练数据划分为若干个簇，而不需要知道每个簇的真实类别。度量样本的差异性，就用距离描述.

K-Means

初始化簇质心:

首先随机选择K个样本点作为初始的簇质心。

分配样本到簇:

对于每个样本点，计算它到各个簇质心的距离，将其分配到距离最近的簇。

更新簇质心:

对于每个簇，计算该簇内所有样本点的平均值，作为新的簇质心。

检查收敛条件:

比较新旧两轮簇质心的变化情况，如果变化小于某个阈值，则认为算法收敛。

否则回到步骤2继续迭代

这个迭代过程会不断调整簇质心的位置,使得每个样本点到其所属簇质心的距离和最小化。当算法收敛时,簇质心就稳定下来,代表了K个聚类的中心位置。

需要注意的是,K-Means算法对初始化簇质心的位置比较敏感,不同的初始化可能会得到不同的聚类结果。因此在实际应用中,通常会运行多次算法,选择得到最优聚类效果的结果。

找到最佳结果的措施是最小化平方误差E（SSE，平方误差之和）

k 表示簇的数量

表示第 i 个簇包含的样本点集合

x 表示样本点

表示第 i 个簇的质心

表示样本点 x 与其所属簇质心之间的欧氏距离的平方

这个目标函数的含义是:对于每个簇i, 将该簇内所有样本点到簇质心的平方距离进行求和,然后将所有簇的这个平方距离和进行累加

不过，最小化E是 NP-Hard 的。K-Means 使用交互式最优算法。每次迭代的每一步都是优化E的过程。我们可以选择多次初始化来得到最好的结果（不过这个措施是否有效取决于k).

如何选择k呢?有一个方法叫做”肘部法”

这张图解释了肘部法,具体来说:

横轴表示聚类数 K 的取值范围,从 1 到 7。

纵轴表示 K-Means 算法的目标函数值,即样本点到其所属簇质心的平方距离和。

随着 K 的增加,目标函数值会逐渐降低。但当 K 达到某个值时,目标函数值的下降趋势会发生"拐点"或"肘部"。

这个"肘部"对应的 K 值就是最佳的聚类数。在图中,这个"肘部"出现在 K=4 左右。

也就是说,通过观察目标函数值随 K 变化的曲线图,找到"肘部"所对应的 K 值,就可以确定最佳的聚类数。这种方法直观且易于理解,被称为"肘部法"。

以上QA为什么会是如此呢?根据K-Means的性质,聚类数 K 增加时,目标函数值 SSE 应该是单调递减的。也就是说,K=5 时的 SSE 应该小于或等于 K=3 时的 SSE.

错误的原因就有如下:

初始化问题:

K-Means 算法对初始化簇中心的位置比较敏感。如果初始化不当,可能会陷入局部最优解。

在 K=5 的情况下,算法可能陷入了一个较差的局部最优解,导致 SSE 较高。

数据特性问题:

如果数据集本身不适合划分为 5 个簇,即使增加聚类数也无法得到更好的结果。

这种情况下,K=3 可能更能反映数据的自然聚类结构。

代码实现问题:

也有可能是代码本身存在 bug,导致 K-Means 算法无法正确运行.

DBSCAN

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种常用的密度聚类算法。

DBSCAN算法通过基于样本之间的密度来发现聚类结构。它不需要预先指定聚类的数量，并且可以有效地处理具有不同密度和噪声的数据集。

DBSCAN算法的核心思想是定义一个样本的邻域，并根据邻域内样本的密度来判断样本的类型。具体来说，DBSCAN算法将样本分为三种类型：核心点（core point）、边界点（border point）和噪声点（noise point）。

邻域：对于数据集D中的任意点p，其邻域包含数据集D中与p的距离不大于的点。

核心点是某点的邻域内具有足够数量的样本的点。邻域内的样本数量超过了预先指定的阈值（MinPts）

边界点是在一个指定的邻域内的样本数量不足以成为核心点，但是它位于核心点的邻域内。

噪声点是既不是核心点也不是边界点的样本。

还有如下概念:

直接密度可达（Directly Density-Reached）：如果点q在点p的 -邻域中，且点p是核心点，则称点q相对于点p是直接密度可达的。

密度可达（Density-Reached）：对于点p和q，如果存在一个点序列，其中，，且相对于是直接密度可达的，则称点 q 相对于点 p 是密度可达的。

也就是一连串直接密度可达的点串联起的两个点至少是密度可达的

密度相连（Density-Connected）：对于点p和q，如果存在一个核心点o，使得点p和点q都相对于点o是密度可达的，则称点 $p$ 和点 $q$ 是密度相连的。

比密度可达的要求更低一层

DBSCAN将簇定义为密度连通性最强的样本集

DBSCAN算法的步骤如下：

选择一个未被访问的样本点。

计算该样本点的邻域内的样本数量，如果大于等于MinPts，则将该样本点标记为核心点，并将其邻域内的样本加入同一个簇。

对于核心点邻域内的每个样本，如果它也是核心点，则将其邻域内的样本加入同一个簇。

重复步骤2和步骤3，直到所有的核心点及其可达的样本都被访问过。

选择一个未被访问的样本点，重复步骤2到步骤4，直到所有的样本点都被访问过。

将剩余的未被分配到任何簇的样本点标记为噪声点。

换一种说法,可以这样描述过程:

首先找到所有的核心点,然后根据密度可达关系将核心点及其可达点归为同一个簇。

最后,将所有密度相连的簇合并成为最终的聚类结果。

两个描述过程是结果等价的,第一种描述是对单个核心点,密度相连的步骤先作出了(第2步),但是第二个描述方式是先对所有核心点单独归类,在最后对每个核心点判断密度相连

DBSCAN算法的优点是能够发现任意形状的聚类，并且对噪声点具有鲁棒性。然而，它对于具有不同密度的聚类可能会遇到困难，并且对于高维数据集可能会受到维度灾难的影响。此外，DBSCAN算法的性能也受到邻域半径和MinPts参数的选择影响。

性能度量

好的聚类应该：

簇内相似度高

簇间相似度低

以及还有内部指数和外部指数评判:内部指数，就是说不使用参考模型直接评估聚类结果；外部指数，将聚类结果与参考模型进行比较，例如领域专家给出的划分结果.

Davies-Boukdin 指数

越小越好。

Dunn 指数

越大越好。