机器学习知识点汇总

机器学习模型

感知机

k 近邻

朴素贝叶斯

sklearn中有3种不同类型的朴素贝叶斯：
1.多项式型：用于离散值模型里。比如文本分类问题里面，我们不光看词语是否在文本中出现，也得看出现次数。如果总词数为n，出现词数为m的话，有点像掷骰子n次出现m次这个词的场景。
2.高斯分布型：当特征是连续变量的时候，假定属性/特征服从正态分布的。
3.伯努利型：每个特征的取值只能是1和0(以文本分类为例，某个单词在文档中出现过，则其特征值为1，否则为0)。

原理

贝叶斯公式和特征条件独立假设
条件概率：
$P(A|B)$表示事件B已经发生的前提下，事件A发生的概率，叫做事件B发生下事件A的条件概率。其基本求解公式为：$P(A|B)=\frac{P(AB)}{P(B)}$
贝叶斯定理便是基于条件概率，通过$P(A|B)$来求$P(B|A)$：
$P(B|A)=\frac{P(A|B)P(B)}{P(A)}$
在分类任务中：
$P(类别|特征)=\frac{P(特征|类别)P(类别)}{P(特征)}$

特征条件独立假设的作用

由贝叶斯公式，分子中的$P(yk)$是先验概率，根据训练集就可以简单地计算出来。
而条件概率$P(x|y_k)=P(x_1,x_2,…,x_n|y_k)$，它的参数规模是指数数量级别的，假设第i维特征$x_i$可取值的个数有$S_i$个，类别取值个数为k个，那么参数个数为：$$k\prod{i=1}^{n}S{i}$针对这个问题，朴素贝叶斯算法对条件概率分布作出了独立性的假设，通俗地讲就是说假设各个维度的特征$x_1,x_2,...,x_n$互相独立，在这个假设的前提上，条件概率可以转化为：$P(x|y{k})=P(x{1},x{2},…,x{n}|y{k})=\prod{i=1}^{n}P(x{i}|y{k})$这样，参数规模就降到$k\sum{i=1}^{n}S_{i}$$

平滑

拉普拉斯平滑

优缺点

优点:
(1）算法逻辑简单,易于实现（算法思路很简单，只要使用贝叶斯公式转化即可）
(2) 分类过程中时空开销小（假设特征相互独立，只会涉及到二维存储）
缺点：
朴素贝叶斯假设属性之间相互独立，这种假设在实际过程中往往是不成立的。在属性之间相关性越大，分类误差也就越大。

场景题

如预测今天的天气：根据历史数据，可以知道天气类型的先验分布，以及每种天气类型下的特征数据（如温度、湿度等）的条件分布，然后根据贝叶斯公式求得天气类型的后验分布。

决策树

3种决策树，区别，适用场景

ID3:检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树。
信息增益：
特征A对训练数据集D的信息增益，定义为集合A的经验熵$H(D)$与特征A给定条件下D的经验条件熵$H(D|A)$之差：

$$g(D,A)=H(D)-H(D|A)$$

不足之处：当一个属性的可取值数目较多时，那么可能在这个属性对应的可取值下的样本只有一个或者是很少个，那么这个时候它的信息增益是非常高的，这个时候纯度很高，ID3决策树会认为这个属性很适合划分，但是较多取值的属性来进行划分带来的问题是它的泛化能力比较弱，不能够对新样本进行有效的预测。

C4.5：用信息增益比来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足。
信息增益比：


但是同样的这个增益率对可取值数目较少的属性有所偏好，因此C4.5决策树先从候选划分属性中找出信息增益高于平均水平的属性，在从中选择增益率最高的。
CART:用基尼系数来选择属性，选择划分后基尼系数最小的属性。
基尼系数：
基尼系数值越小，说明二分之后的子样本的“纯净度”越高，即说明选择该属性（值）作为分裂属性（值）的效果越好。
对于样本集S，GINI计算如下：

其中，在样本集S中，$P_k$表示分类结果中第k个类别出现的频率。
  对于含有N个样本的样本集S，根据属性A的第i个属性值，将数据集S划分成两部分，则划分成两部分之后，GINI计算如下：

其中，$n_1$、$n_2$分别为样本子集$S_1$、$S_2$的样本个数。
  对于属性A，分别计算任意属性值将数据集划分成两部分之后的GINI，选取其中的最小值，作为属性A得到的最优二分方案：

对于样本集S，计算所有属性的最优二分方案，选取其中的最小值，作为样本集S的最优二分方案：

所得到的属性A及其第i属性值，即为样本集S的最优分裂属性以及最优分裂属性值。

连续值处理办法

参考周志华《机器学习》
C4.5采用二分法处理连续数值，取每两个相邻属性值的中位点作为候选划分点，计算基于此划分点二分化后的信息增益，选择最大的最为划分点。不同于离散属性，连续属性还可以作为后代结点的划分属性。

缺失值处理办法

问题一：如何在属性值缺失的情况下进行划分属性选择？
计算某个属性时，取在此属性上不缺失的样本子集，计算子集上的信息增益，最后乘以此子集占所有样本的比重，得到最终的信息增益。

问题二：给定划分属性，若该样本在此属性上的值缺失，怎么划分？
给每个样本附一个权重，若该样本在此属性上有值，则加入对应子结点，权重不变。若该样本在此属性上没有值，则加入所有子结点，并将其权重调整为此子结点中无缺失值占所有无缺失样本的比例*原权重。

GBDT 和随机森林区别

哪个具备交叉验证

GBDT 和 xgboost 区别

回归树

随机森林样本数量是否会影响模型复杂度

特征选择方法

信息增益
信息增益比
基尼系数

信息熵和基尼系数关系

信息熵在 x=1处一阶泰勒展开式就是基尼系数，纯度越高，值越小。
参考 https://blog.csdn.net/YE1215172385/article/details/79470926

逻辑回归

损失函数(交叉熵损失函数)

$L=\sum_{i=1}^Ny^{(i)}log\ \hat y^{(i)}+(1-y^{(i)})log\ (1-\hat y^{(i)})$

LR 怎么处理非线性

1.特征离散+特征交叉
2.核函数，不同于SVM，LR中所有样本都会参与运算，计算量过大。
3.LR之前加入神经网络，将神经网络看做特征提取

能否用核函数

加L2正则可以引入核函数。https://www.youtube.com/watch?v=AbaIkcQUQuo&list=PLXVfgk9fNX2IQOYPmqjqWsNUFl2kpk1U2&index=21
推导：

和 NB 的不同

特征离散化的好处

https://blog.csdn.net/yang090510118/article/details/39478033
在工业界，很少直接将连续值作为特征喂给逻辑回归模型，而是将连续特征离散化为一系列0、1特征交给逻辑回归模型，这样做的优势有以下几点：

1. 稀疏向量内积乘法运算速度快，计算结果方便存储，容易scalable（扩展）。
2. 离散化后的特征对异常数据有很强的鲁棒性：比如一个特征是年龄>30是1，否则0。如果特征没有离散化，一个异常数据“年龄300岁”会给模型造成很大的干扰。
3. 逻辑回归属于广义线性模型，表达能力受限；单变量离散化为N个后，每个变量有单独的权重，相当于为模型引入了非线性，能够提升模型表达能力，加大拟合。
4. 离散化后可以进行特征交叉，由M+N个变量变为M*N个变量，进一步引入非线性，提升表达能力。
5. 特征离散化后，模型会更稳定，比如如果对用户年龄离散化，20-30作为一个区间，不会因为一个用户年龄长了一岁就变成一个完全不同的人。当然处于区间相邻处的样本会刚好相反，所以怎么划分区间是门学问。

李沐少帅指出，模型是使用离散特征还是连续特征，其实是一个“海量离散特征+简单模型” 同 “少量连续特征+复杂模型”的权衡。既可以离散化用线性模型，也可以用连续特征加深度学习。就看是喜欢折腾特征还是折腾模型了。通常来说，前者容易，而且可以n个人一起并行做，有成功经验；后者目前看很赞，能走多远还须拭目以待。

大概的理解：
1）计算简单
2）简化模型
3）增强模型的泛化能力，不易受噪声的影响

参数估计推导

伯努利过程 极大似然 损失函数 梯度下降

为什么使用Sigmoid

因为它引入了非线性映射，将线性回归值域映射到0-1之间，有助于直观的做出预测类型的判断：大于等于0.5表示阳性，小于0.5表示阴性。

做 ctr预估

把被点击的样本当成正例，把未点击的样本当成负例，那么样本的ctr实际上就是样本为正例的概率，LR可以输出样本为正例的概率，所以可以用来解决这类问题，另外LR相比于其他模型有求解简单、可解释强的优点，这也是工业界所看重的。

1. LR是线性模型，具有很好的可解释性，分布式计算迭代速度快。
2. LR可以很好的利用正则化解决稀疏性问题，尤其特征维数非常大，大到千亿级别。
3. 输出是0-1的连续值，取值范围天然契合概率，而点击率也是一个0-1的概率值。

   归一化或者取对数

   提高梯度下降法求解最优解的速度
   https://blog.csdn.net/weixin_38111819/article/details/79729444

   与NB区别

   https://blog.csdn.net/cjneo/article/details/45167223
   1.一个是生成式模型，一个是判别式模型
   2.Naive Bayes是建立在条件独立假设基础之上的，设特征X含有n个特征属性（X1，X2，…Xn），那么在给定Y的情况下，X1，X2，…Xn是条件独立的。LR的限制则要宽松很多，如果数据满足条件独立假设，LR能够取得非常好的效果；当数据不满度条件独立假设时，LR仍然能够通过调整参数让模型最大化的符合数据的分布，从而训练得到在现有数据集下的一个最优模型。

   最大熵模型

   当你要猜一个概率分布时，如果你对这个分布一无所知，那就猜熵最大的均匀分布，如果你对这个分布知道一些情况，那么，就猜满足这些情况的熵最大的分布。

与逻辑回归的相似点

从最大熵的思想出发得出的最大熵模型，最后的最大化求解就是在求$P(y|x)$的对数似然最大化。逻辑回归也是在求条件概率分布关于样本数据的对数似然最大化。二者唯一的不同就是条件概率分布的表示形式不同。

SVM

原理

从分类超平面，到求两类间的最大间隔，到转化为求间隔分之一，等优化问题。然后就是优化问题的解决办法，首先是用拉格拉日乘子把约束优化转化为无约束优化，对各个变量求偏导令其为零，得到的式子带入拉格朗日式子从而转化为对偶问题， 最后再利用SMO（序列最小优化）来解决这个对偶问题。

求解方法和推导

转化为对偶形式，极大极小求α，w 和 b

损失函数

合页损失+正则化项
二分类问题的真正损失函数是0/1损失函数，但是因为其不是连续可导的，所以用合页损失函数代替。合页损失函数是0/1损失函数的上界。

学习算法

SMO 序列最小最优化算法

怎么防止过拟合

松弛变量 引入松弛变量使SVM能够容忍异常点的存在
目标函数中的正则化项

核函数原理

将样本从原始空间映射到一个更高维的特征空间，使得样本在这个空间中线性可分。但是计算映射的内积通常是困难的，因此引入核函数。两个样本在特征空间的内积等于他们在原始空间通过核函数计算的结果。

为什么要引入对偶

原问题是凸二次规划问题，转换为对偶问题更加高效。对偶问题只用求解alpha系数，而alpha系数只有支持向量才非0，其他全部为0。

怎么做回归

SVR

怎么做多分类

https://blog.csdn.net/xfChen2/article/details/79621396
多个超平面同时求解
一对多
一对一 投票 Libsvm的实现方法

是否适合大规模数据

PEGASOS

与 LR 区别

https://www.jianshu.com/p/f86de852ee96
https://blog.csdn.net/jieming2002/article/details/79317496

1. 本质区别是损失函数的不同：
   LR 的损失函数：
   
   基于概率理论，假设样本为1的概率可以用sigmoid函数来表示，然后通过极大似然估计的方法估计出参数的值。
   SVM 的目标函数：
   
   基于几何间隔最大化原理，认为存在最大几何间隔的分类面为最优分类面。
2. 支持向量机只考虑局部的边界线附近的点（支持向量），而逻辑回归考虑全局（远离的点对边界线的确定也起作用）。
3. 解决非线性问题时，LR 很少使用核函数。若使用核函数，LR 中每个样本点都必须参与核计算，这带来的计算复杂度是相当高的。
4. SVM 目标函数中自带正则

数据不平衡解决办法

再缩放《西瓜书》P67 实际操作复杂
上采样
下采样
libSVM的解决办法：在惩罚因子上做文章。给样本数量少的类更大的惩罚因子，表示我们重视这部分样本。libSVM就直接使用样本数量的比确定惩罚因子。

k-means

transformer

3个 attention 的作用

编码器和解码器中的attention 学习文本的表示，学习句子内部的词依赖关系，捕获句子的内部结构。
编码器和解码器attention用来翻译对齐。

Attention

对比 Attention 和 CNN RNN

RNN的方案很简单，递归式进行：
$\boldsymbol{y}t = f(\boldsymbol{y}{t-1},\boldsymbol{x}_t)$
无法并行，速度较慢
输入序列不论长短都会被编码成一个固定长度的向量表示，而解码则受限于该固定长度的向量表示。
CNN 则需要通过层叠来扩大感受野

长度需要填充的文本怎么避免填充值影响后续计算

https://blog.csdn.net/stupid_3/article/details/83184691
https://blog.csdn.net/mijiaoxiaosan/article/details/74909076
给在较短的序列后面填充0。因为这些填充的位置，其实是没什么意义的，所以我们的attention机制不应该把注意力放在这些位置上，所以我们需要进行一些处理。
具体的做法是，把这些位置的值加上一个非常大的负数(可以是负无穷)，这样的话，经过softmax，这些位置的概率就会接近0！

机器学习算法

最优化算法

迭代尺度法
梯度下降法
牛顿法或拟牛顿法

附录

评价方法

分类评价方法

准确率
召回率
F值
P-R 曲线
ROC 曲线和 AUC 曲线

回归评价方法

平均绝对误差
均方误差 MSE

过拟合

过拟合

当我们提高在训练数据上的表现时，在测试数据上反而下降。
过拟合发生的本质原因，是由于监督学习问题的不适定：在高中数学我们知道，从n个（线性无关）方程可以解n个变量，解n+1个变量就会解不出。在监督学习中，往往数据（对应了方程）远远少于模型空间（对应了变量）。因此过拟合现象的发生，可以分解成以下三点：

1.有限的训练数据不能完全反映出一个模型的好坏，然而我们却不得不在这有限的数据上挑选模型，因此我们完全有可能挑选到在训练数据上表现很好而在测试数据上表现很差的模型，因为我们完全无法知道模型在测试数据上的表现。
2.如果模型空间很大，也就是有很多很多模型可以给我们挑选，那么挑到对的模型的机会就会很小。
3.与此同时，如果我们要在训练数据上表现良好，最为直接的方法就是要在足够大的模型空间中挑选模型，否则如果模型空间很小，就不存在能够拟合数据很好的模型。

由上3点可见，要拟合训练数据，就要足够大的模型空间；用了足够大的模型空间，挑选到测试性能好的模型的概率就会下降。因此，就会出现训练数据拟合越好，测试性能越差的过拟合现象。

正则化

在经验风险的上加一个正则化项或罚项，是结构风险最小化策略的实现。正则化项一般是模型复杂度的单点递增函数，模型越复杂，正则项就越大。
正则化的作用是选择经验风险与模型复杂度同时较小的模型。

L0和L1

L0范数是指向量中非零元素的个数。
如果用L0规则化一个参数矩阵W，就是希望W中大部分元素是零，实现稀疏。
L0范数的应用：
1）特征选择
​实现特征的自动选择，去除无用特征。稀疏化可以去掉这些无用特征，将特征对应的权重置为零。
2）可解释性（interpretability）​
例如判断某种病的患病率时，最初有1000个特征，建模后参数经过稀疏化，最终只有5个特征的参数是非零的，那么就可以说影响患病率的主要就是这5个特征。
弊端：非连续；非凸；不可导；

L1范数是指向量中各个元素的绝对值之和，也叫”系数规则算子（Lasso regularization）“。
L1范数也可以实现稀疏，通过将无用特征对应的参数W置为零实现。
L0和L1都可以实现稀疏化，不过一般选用L1而不用L0，原因包括：
1）L0范数很难优化求解（NP难）；
2）L1是L0的最优凸近似，比L0更容易优化求解。

L2

L2范数​​是指向量各元素的平方和然后开方，用在回归模型中也称为岭回归（Ridge regression）。
L2避免过拟合的原理是：让L2范数的规则项||W||2 尽可能小，可以使得W每个元素都很小，接近于零，但是与L1不同的是，不会等于0；这样得到的模型抗干扰能力强，参数很小时，即使样本数据x发生很大的变化，模型预测值y的变化也会很有限。

为什么L1系数可以被压缩为0，L2是接近于0

https://www.zhihu.com/question/37096933/answer/475278057
https://liam.page/2017/03/30/L1-and-L2-regularizer/

L1怎么解决求导困难（不可导）

近端梯度下降
https://www.zhihu.com/question/265426774

怎么防止过拟合

https://www.zhihu.com/question/20924039 参考景略集智的回答
1.正则化，可以用 L1或 L2范数，选择经验风险和模型复杂度同时较小的模型。
2.dropout CNN 和 RNN 不同
DropoutWrapper RNN 中Dropout只能是层与层之间（输入层与LSTM1层、LSTM1层与LSTM2层）的Dropout；同一个层里面，T时刻与T+1时刻是不会Dropout的
3.数据增强 利用 GAN 生成更多数据
4.bagging
5.batch normalization CNN
6.layer normalization RNN
7.Early Stopping

Dropout

训练阶段和测试阶段有何不同？ https://blog.csdn.net/program_developer/article/details/80737724
dropout中不同设置的神经元和我们训练几种不同的神经网络很像。因此，dropout处理很像是大量不同网络的平均结果。
训练阶段以 p 的概率置隐层神经元输出值为0。测试阶段要缩放激活函数，(1-p)。
为了一次性定义模型，tf 等选择测试阶段保持不变，在训练阶段对激活函数进行Inverted Dropout，1/(1-p)

BN

Internal Covariate Shift问题，在训练过程中，隐层的输入分布老是变来变去，所以输出的分布也会不断变化，造成梯度需要不断适应新的数据分布。
BN(2015):对于每个隐层神经元，把逐渐向非线性函数映射后向取值区间极限饱和区靠拢的输入分布强制拉回到均值为0方差为1的比较标准的正态分布，使得非线性变换函数的输入值落入对输入比较敏感的区域，这样输入的小变化使得损失函数变化较大，梯度变大，以此避免梯度消失问题，也加快了收敛速度。https://blog.csdn.net/leviopku/article/details/83109422 RNN 不适用（也有 paper 实现 rnn 可用的 BN）BN特别依赖Batch Size；当Batch size很小的适合，BN的效果就非常不理想了。

LN

BN 是“竖着”来的，对于 batch 内的样本各个维度做归一化，与 batch 有关；
LN 是“横着”来的，对于一个样本，同一层的不同神经元间做归一化。

对偶问题（拉格朗日乘子法）

集成学习

boosting(AdaBoost)

参考《统计学习方法》

1. 给定训练样本集S，其中X和Y分别对应于正例样本和负例样本； T为训练的最大循环次数；
2. 初始化样本权重为1/n ，即为训练样本的初始概率分布；
3. 第一次迭代：
   (1) 训练弱分类器；
   (2) 计算弱分类器的错误率；
   (3) 计算弱分类器的权重；
   (4) 更新样本权重；
   经T次循环后，得到T个弱分类器，按更新的权重叠加，最终得到的强分类器。

bagging

1）从原始样本集中抽取训练集.每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）.共进行k轮抽取，得到k个训练集.（k个训练集相互独立）
2）每次使用一个训练集得到一个模型，k个训练集共得到k个模型.（注：根据具体问题采用不同的分类或回归方法，如决策树、神经网络等）
3）对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果.

两者不同

Bagging + 决策树 = 随机森林
AdaBoost + 决策树 = 提升树
Gradient Boosting + 决策树 = GBDT

1）样本选择上：
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的.
Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化.而权值是根据上一轮的分类结果进行调整.

2）样例权重：
Bagging：使用均匀取样，每个样例的权重相等
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大.

3）预测函数：
Bagging：所有预测函数的权重相等.
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重.

4）并行计算：
Bagging：各个预测函数可以并行生成
Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果.

为什么说bagging是减少方差variance，而boosting是减少偏差bias

https://www.zhihu.com/question/45487317
其实就机器学习算法来说，其泛化误差可以分解为两部分，偏差（bias)和方差(variance)。这个可由下图的式子导出（这里用到了概率论公式$D(X)=E(X^2)-[E(X)]^2$。偏差指的是算法的期望预测与真实预测之间的偏差程度，反应了模型本身的拟合能力；方差度量了同等大小的训练集的变动导致学习性能的变化，刻画了数据扰动所导致的影响。

$$Err(h) = E[(h-f)^2]=E[((h-E[h])-(f-E[h]))^2]$$$$=E[(h-E[h])^2]-2E[(h-E[h])(f-E[h])]+E[(f-E[h])^2]$$$$=var-2E[b(h-E[h]) +b^2=var-2b(E[h]-E[E[h]]) +b^2$$$$=var -2b*0+b^2=var+b^2$$

如下图所示，当模型越复杂时，拟合的程度就越高，模型的训练偏差就越小。但此时如果换一组数据可能模型的变化就会很大，即模型的方差很大。所以模型过于复杂的时候会导致过拟合。当模型越简单时，即使我们再换一组数据，最后得出的学习器和之前的学习器的差别就不那么大，模型的方差很小。还是因为模型简单，所以偏差会很大。

也就是说，当我们训练一个模型时，偏差和方差都得照顾到，漏掉一个都不行。对于Bagging算法来说，由于我们会并行地训练很多不同的分类器的目的就是降低这个方差(variance)$E[(h-E[h])]$ ,因为采用了相互独立的基分类器多了以后，h的值自然就会靠近$E[h]$.所以对于每个基分类器来说，目标就是如何降低这个偏差（bias),所以我们会采用深度很深甚至不剪枝的决策树。对于Boosting来说，每一步我们都会在上一轮的基础上更加拟合原数据，所以可以保证偏差（bias）,所以对于每个基分类器来说，问题就在于如何选择variance更小的分类器，即更简单的分类器，所以我们选择了深度很浅的决策树。

Random Forest

随机森林的集成学习方法是bagging ，但是和bagging 不同的是bagging只使用bootstrap有放回的采样样本，但随机森林既随机采样样本，也随机选择特征，因此防止过拟合能力更强，降低方差。
如果有M个输入变量，每个节点都将随机选择m($m<M$)个特定的变量，然后运用这m个变量来确定最佳的分裂点。在决策树的生成过程中，m的值是保持不变的。m一般取$log_2 M$

stacking

https://blog.csdn.net/qq_18916311/article/details/78557722

gbdt

用损失函数的负梯度来拟合本轮损失的近似值，进而拟合出一个CART回归树。

xgboost

lgbm

CatBoost

xgboost和gbdt区别