前言

原创不易，转载请注明出处

机器学习中关于解决回归问题的总结

注：以下线性回归中，均可采用梯度下降、最小二乘(交替)、牛顿法(拟牛顿)、坐标轴下降、正规方程解析解、最小角回归法 求得。下面整理只给出每个算法最常用的解法。

关于机器学习&深度学习中，损失、代价、目标、成本含义解释

• 损失函数：真实值与预测值的差距
• 代价函数：所有样本损失值加总 / 样本数
• 目标函数：损失函数加了正则项
• 成本函数：成本函数和代价函数是等价的

注：如以下涉及到的用词错误，敬请谅解

一元线性回归

百度百科

​ 一元线性回归是分析只有一个自变量（自变量x和因变量y）线性相关关系的方法。一个经济指标的数值往往受许多因素影响，若其中只有一个因素是主要的，起决定性作用，则可用一元线性回归进行预测分析。

白话原理

​ 形如： 。只有一个自变量和一个因变量的直线方程，目的是找到最优的回归系数w和偏置b，使得预测值 和真实值 的损失最小。

代价函数

​ 均方误差：

​ 很多教材上给出的是误差平方和，其实都可以，无非就是分母不一样。这里均方根多除一个2是方便梯度下降求偏导。

求解方式

​ 梯度下降，直观理解就是代价函数曲线上的“下山过程”，其实就是对代价函数求偏导。又分为批量梯度下降BGD、小批量梯度下降MBGD、随机梯度下降SGD。

​ 批量梯度下降法是最原始的形式，它是指在每一次迭代时使用所有样本来进行梯度的更新。优点是一次迭代是对所有样本进行计算，可以利用矩阵并行计算。缺点是当样本数量级很大时，整个训练过程会非常慢。

​ 小批量梯度下降是机器学习和深度学习最为常用的优化方法。是对BGD和SGD的一个折中。其思想是每次迭代使用batch_size个样本来对参数进行更新。优点是通过矩阵运算，每次在一个batch上优化参数并不会比单个数据慢太多。其次是每使用一个batch可以大大减小收敛所需要的迭代次数，同时可以使收敛到的结果更加接近梯度下降的效果。缺点就是batch_size阈值的选择。

​ 随机梯度下降是每次迭代使用一个样本来对参数进行更新。使得训练速度加快。优点是由于不是在全部训练数据上的损失函数，而是在每轮迭代中，随机优化某一条训练数据上的损失函数，这样每一轮参数的更新速度大大加快。缺点是准确度下降，由于单个样本并不能代表全体样本的趋势，所以很可能会局部最优甚至无法做到线性收敛。

优缺点 & 适用场景

• 一元线性方程比较简单，欠拟合风险较大，所以一般不用。

多元线性回归

百度百科

​ 在回归分析中，如果有两个或两个以上的自变量，就称为多元回归。事实上，一种现象常常是与多个因素相联系的，由多个自变量的最优组合共同来预测或估计因变量，比只用一个自变量进行预测或估计更有效，更符合实际。因此多元线性回归比一元线性回归的实用意义更大。

白话原理

​ 形如： 。相比于一元线性回归，多元线性回归(即多变量回归)更加符合实际，因为我们实际需求大多都是多个特征的。同样的我们需要求解一组参数 和 偏置 ，来使得预测值和真实值的误差最小。当w转成向量后可得预测函数如下：

注：很多文献上都喜欢用 表示权重向量，即上述的

代价函数

​ 均方误差

求解方式

​ 梯度下降、最小二乘

​ 最小二乘的思想就是求多元函数极值，说白了就是对各个求偏导然后使偏导为0。这样P个参数就对应P个方程需要求解，可以说计算量比较大。而梯度下降可以看做是更简单的一种求最小二乘法最后一步解方程 的方法。

关于最小二乘、梯度下降、牛顿法的总结：

https://cloud.tencent.com/developer/article/1433814

优缺点 & 适用场景

• 优点是不需要对数据进行归一化处理，原始数据进行计算参数，不存在量纲的问题。

• 缺点是计算复杂度较高，在特征比较多的时候，计算量很大。

局部加权线性回归

百度百科

​ 局部加权线性回归（Local Weights Linear Regression）也是一种线性回归。不同的是，普通线性回归是全局线性回归，使用全部的样本计算回归系数。而局部加权线性回归，通过引入权值（核函数），在预测的时候，只使用与测试点相近的部分样本来计算回归系数。

白话原理

​ 线性回归的一个问题是有可能出现欠拟合，因为它求的是具有最小均方误差的无偏估计，欠拟合是无法达到我们想要的预测效果，所以有些方法允许在估计中引入一些偏差，从而降低预测的均方误差。局部线性加权的思想是对待预测点附近的每个点赋予一个权重，然后在带权的样本上基于最小均方误差来进行回归。

​ 换句话说，在局部加权线性回归中，我们在预测前对于每个点都赋予一个权重，离需要预测点越近的点权重越大，反之权重越小。其它思想和多元线性回归基本一致，加权体现在代价函数上。

代价函数

是我们的预测值，即：

就是权重，我们一般使用高斯核函数：

• 其中，x是我们的要预测的点，k是我们需要指定的参数，他控制了权值随距离变化的速率。从公式可以看到，加权函数只有一个系数，那就是分母上的K，当K取很小时， 得到的很多值均趋于0，此时只有很少一部分样本用于训练，而当K取很大时， 的值不会很快趋于0，从而会有一大部分点用于训练，我们可以通过调整K的值，决定这个局部的大小究竟是多大。
  • k值越大，权重随距离变化的速率越小，预测某个点时用到的数据点就更多。
  • k值越小，权重随距离变化的速率越大，预测某个点时用到的数据点就更少。
  • k值的选择是很重要的，k值选择过大，可能出现过拟合问题，k值选择过小，可能出现欠拟合问题。
  • 经验来说可调范围区间为：k ∈ [0.01, .01]，K=1可以说加权对样本没什么影响。

求解方式

​ 梯度下降、正规方程

优缺点 & 适用场景

​ 优点就是通过核函数加权来预防欠拟合，缺点也很明显K需要调试。当多元线性回归过拟合的时候，可以尝试高斯核局部加权来预防过拟合。

多项式回归

百度百科

​ 多项式回归，回归函数是回归变量多项式的回归。多项式回归模型是线性回归模型的一种，此时回归函数关于回归系数是线性的。由于任一函数都可以用多项式逼近，因此多项式回归有着广泛应用

​ 研究一个因变量与一个或多个自变量间多项式的回归分析方法，称为多项式回归（Polynomial Regression）。如果自变量只有一个时，称为一元多项式回归；如果自变量有多个时，称为多元多项式回归。在一元回归分析中，如果依变量y与自变量x的关系为非线性的，但是又找不到适当的函数曲线来拟合，则可以采用一元多项式回归。

白话原理

​ 多项式回归是一元线性回归及多元线性回归的扩展。在原有线性方程的基础上增加了自变量x的几次项，可以说是变相的增加了特征。譬如一元多项式回归，当多项式项数为n时，相当于多了n个特征。多元多项式也是这个道理，所以就有种特征交叉的意思了。

​ 一元m次多项式回归方程如下：

​ 二元二次多项式回归方程如下：

代价函数

​ 均方误差

求解方式

​ 梯度下降、最小二乘

优缺点 & 适用场景

​ 当我们要拟合的是曲线而不是直线时，就可以用多项式回归。通过控制项数来用线性模型拟合非线性数据。相比于线性回归应用更加广泛，因为我们实际场景中的数据大多呈现非线性关系。因为项数的存在所以原始数据维度得到提高，使得方程更好的拟合高维的数据，提高模型的泛化能力。缺点就是多项式的项数是需要调试的。

Lasso回归 & Ridge回归

Lasso回归

百度百科

​ LASSO是由1996年Robert Tibshirani首次提出，全称Least absolute shrinkage and selection operator。该方法是一种压缩估计。它通过构造一个惩罚函数得到一个较为精炼的模型，使得它压缩一些回归系数，即强制系数绝对值之和小于某个固定值；同时设定一些回归系数为零。因此保留了子集收缩的优点，是一种处理具有复共线性数据的有偏估计。

白话原理

​ 就是在线性回归的基础上，代价函数里加了L1正则。

代价函数

求解方式

​ 坐标轴下降法、最小角回归法

​ 为什么lasso回归的求解方式不再是梯度下降、最小二乘？因为lasso回归对损失函数加了L1惩罚。L1范数用的是绝对值之和，导致损失函数有不可导的点，所以最小二乘、梯度下降、牛顿和拟牛顿就统统失效了。

因为实际应用中，不管是回归还是变量选择还是降维，lasso回归应用并不多，所以这里对坐标轴下降和最小角回归不做解释。

优缺点 & 适用场景

​ L1正则化可以使得一些特征的系数变小,甚至还使一些绝对值较小的系数直接变为0，所以对于高纬的特征数据，尤其是线性关系是稀疏的，就可以用lasso回归，也是起到一定的降维作用。

Ridge回归

百度百科

​ 岭回归(英文名：ridge regression, Tikhonov regularization)是一种专用于共线性数据分析的有偏估计回归方法，实质上是一种改良的最小二乘估计法，通过放弃最小二乘法的无偏性，以损失部分信息、降低精度为代价获得回归系数更为符合实际、更可靠的回归方法，对病态数据的拟合要强于最小二乘法。

白话原理

​ 就是在线性回归的基础上，代价函数里加了L2正则。

代价函数

求解方式

​ 最小二乘、梯度下降

岭回归和lasso回归的区别

• 相同：
  • 都可以用来解决线性回归的过拟合问题。
• 不同：
  • lasso 可以用来做特征选择，而 ridge 不行。或者说，lasso 更容易使得权重变为 0，而 ridge 更容易使得权重接近 0。
  • 从贝叶斯角度看，L1 正则等价于参数 𝑤 的先验概率分布满足拉普拉斯分布，而 L2 正则 等价于参数 𝑤 的先验概率分布满足高斯分布。

关于lasso回归可以做降维的说法，请看下图：

​ 等高线和约束域的切点就是目标函数的最优价。岭回归对应方法的约束是圆，其切点只会存在于圆周上，不会与坐标轴相切，则在任一维度上的取值都不为0，因此没有稀疏。

​ 对于lasso回归，其约束域是正方形，会存在坐标轴的切点，使得部分维度特征权重为0，因此很容易产生稀疏解。

​ 所以lasso回归可以达到变量选择的效果，将不显著的变量系数直接压缩至0，而岭回归对原本的系数进行了一定程度的压缩，但是任一系数都不会压缩至0。

L1正则 & L2正则

L1和L2是正则化项，是为了限制模型的参数，防止模型过拟合而加在损失函数后面的一项。

• L1是模型各参数绝对值之和，L1更趋向于少量特征，其它特征为0，因为最优参数很大概率容易出现在坐标轴上，从而导致产生系数矩阵，从而可以进行庞大特征数量下的特征选择。
• L2为各个参数的平方和的开方。L2会选择更多矩阵，但这些矩阵趋向于0。L2正则能够有效的防止模型过拟合，解决非满秩下求逆困难的问题。

为什么只正则化参数𝑤，不再加上参数 𝑏 呢？

​ 因为𝑤通常是一个高维参数矢量，已经可以表达高偏差问题，𝑤可能包含有很多参数，我们不可能拟合所有参数，而𝑏只是单个数字，所以𝑤几乎涵盖所有参数，而不是𝑏，如果加了参数𝑏，其实也没太大影响，因为𝑏只是众多参数中的一个，所以通常可以省略不计，如果想加上这个参数，也是完全没问题的。

弹性网络回归

白话原理

​ 弹性网络回归ElasticNet回归的思想就是L1正则和L2正则结合来对参数进行更新。在线性回归的基础上，代价函数加了L1正则和L2正则，即lasso回归和岭回归的结合。

代价函数

求解方式

​ 最小二乘、梯度下降

优缺点 & 适用场景

​ 当我们发现用Lasso回归太过(太多特征被稀疏为0)，而岭回归也正则化的不够(回归系数衰减太慢)的时候，可以考虑使用ElasticNet回归来综合，得到比较好的结果。

贝叶斯岭回归

百度百科

​ 贝叶斯线性回归（Bayesian linear regression）是使用统计学中贝叶斯推断（Bayesian inference）方法求解的线性回归（linear regression）模型 [1-2] 。

​ 贝叶斯线性回归将线性模型的参数视为随机变量（random variable），并通过模型参数（权重系数）的先验（prior）计算其后验（posterior）。贝叶斯线性回归可以使用数值方法求解，在一定条件下，也可得到解析型式的后验或其有关统计量。

​ 贝叶斯线性回归具有贝叶斯统计模型的基本性质，可以求解权重系数的概率密度函数，进行在线学习以及基于贝叶斯因子（Bayes factor）的模型假设检验。

先来回顾涉及到的相关概念：

概率乘法公式

全概率公式

设 ~ 是 Ω 的一个划分

贝叶斯公式

贝叶斯定理

它的意思就是：在事件B发生的情况下，事件A发生的概率。

其中，P(A)叫做先验概率，P(B|A)叫做似然，P(B)叫做证据因子，P(A|B)叫做后验概率。

朴素贝叶斯

一般情况下 ，若 则称A与B相互独立，即 相互独立时成立。

朴素贝叶斯的”朴素“就在于它假设特征间是独立的，从而变成了“低配版的贝叶斯”。相较于贝叶斯来说，优点就是可以减少需要估计的参数，缺点就是会牺牲一定的准确率。

注：关于朴素贝叶斯这里不再详细阐述，有兴趣可以查一下，包括其中知识点如 拉普拉斯平滑、多项式朴素贝叶斯、伯努利朴素贝叶斯、高斯朴素贝叶斯等。

极大似然估计

• 似然估计：给定结果的情况下发生的概率

• 极大似然：事情已经发生了，当未知参数等于多少时，能让这个事情发生的概率最大，本质意义上是我们在很多参数中选择一个能使数据出现概率最大的参数。

共轭先验

• 如果先验分布与后验分布属于同一类型的分布，那么我们将先验分布称为似然函数的共轭先验。比如，高斯分布对于高斯类型的似然函数是其自身的共轭先验，也就是说如果先验是高斯，似然函数也是高斯，那么后验也会是高斯。

贝叶斯线性回归公式引入

• 由线性回归可得，数据定义如下：

• 所以我们令 ，求得 即可。

由于求解过程太麻烦，所以笔者就略过。详细求后验推导请见：

https://www.bilibili.com/video/BV1St411m7XJ?p=3

详细Prediction推导请见：

https://www.bilibili.com/video/BV1St411m7XJ?p=4

优缺点 & 适用场景

​ 贝叶斯回归的优点就是对数据有自适应能力，可以重复利用数据并防止过拟合，因为我们在估计的过程中可以引入正则项，比如在贝叶斯线性回归的基础上引入L2正则就是贝叶斯岭回归。缺点就是学习过程开销太大。当特征数在10个以为，可以尝试贝叶斯回归。

Huber回归

白话原理

​ 对于回归问题一般采用MSE作为代价函数，但是如果我们数据中异常值比较严重，导致训练后模型给出的 和真实的 偏差较大，这样在用平方作为loss，模型很容易过拟合，并带偏最后指标。

​ 所以为了增加平方损失对噪声点的鲁棒性，Huber损失应运而生。Huber回归就是在线性回归的基础上，将损失函数替换为Huber损失。

代价函数

先来回顾一下L1损失和L2损失：

2损失处处可导，计算方便，但是对噪声敏感。

L1损失虽然对噪声不敏感，但是在0处不可导，计算不方便。

综合L1和L2的优点，得到Huber损失：

求解方式

​ 梯度下降、最小二乘

优缺点 & 适用场景

​ 结合了L1损失和L2损失的优点，适用于异常点比较严重的数据集。同时缺点就是超参δ是需要调整的，当δ趋向于0时，Huber损失会趋向于MSE；当δ趋向于无穷时，Huber损失会趋向于MAE。

KNN

百度百科

​ 邻近算法，或者说K最近邻（KNN，K-NearestNeighbor）分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是K个最近的邻居的意思，说的是每个样本都可以用它最接近的K个邻近值来代表。近邻算法就是将数据集合中每一个记录进行分类的方法。KNN算法的核心思想是，如果一个样本在特征空间中的K个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法在类别决策时，只与极少量的相邻样本有关。

白话原理

​ 本着物以类聚人以群分的思想，KNN的原理也非常简单。要判断一个新样本的类别，就要看它的邻居是谁。K个邻居即为新样本在样本空间中距离最近的K个点。KNN有三个基本要素：距离度量、K值选择、决策规则。算法步骤就是首先计算已知类别数据集中的点与当前点之间的聚类，然后对距离进行升序排序，返回K个邻近点的下标。如果是分类问题那就是少数服从多数原则。如果是回归问题，直接对K个近邻的y取均值即可，所以KNN不需要训练，只要对于一个新样本点利用距离最近的K个点的标签就可以得出结果。

距离度量

假设有两个样本点 ，它们两者间的闵可夫斯基距离 定义为：

当 时，称为曼哈顿距离(坐标轴距离的绝对值和)

当 时，称为欧式距离(两点间直线距离)

K值选择

• 如果K值过小，会降低精度
• 如果K值过大，会增加噪声
• K一般低于训练样本数的平方根

决策规则

• 分类：多数表决
• 回归：均值、加权平均

优缺点 & 适用场景

​ K值的调试是需要花费时间的。普通的KNN计算时间较长，因为要线性扫描样本空间来计算新样本与所有样本的距离，所以数据越多效率越低。当然改进的方法如KD树、球树等。对于普通的预测场景建议放弃KNN。对于需要一个特别容易解释的模型的时候，可以尝试一下。比如需要向用户解释原因的推荐算法、比如将文本分词，统计词频后判断文章类型、比如电商 视频网站找到与你类似的用户，根据它们的选择推荐你可能感兴趣的物品(类似于协同过滤)。

SVM

百度百科

​ 支持向量机（Support Vector Machine, SVM）是一类按监督学习（supervised learning）方式对数据进行二元分类的广义线性分类器（generalized linear classifier），其决策边界是对学习样本求解的最大边距超平面（maximum-margin hyperplane）。

​ SVM使用铰链损失函数（hinge loss）计算经验风险（empirical risk）并在求解系统中加入了正则化项以优化结构风险（structural risk），是一个具有稀疏性和稳健性的分类器 [2] 。SVM可以通过核方法（kernel method）进行非线性分类，是常见的核学习（kernel learning）方法之一 [4] 。

SVR：即支持向量机回归。我们通常所说的SVM，它其实就是在特征空间中找间隔最大的超平面的广义线性分类器。对于线性可分和线性不可分问题都有着求硬间隔最大和软间隔最大的方法。SVM在这里不再过多阐述，有兴趣的读者可以查阅相关书籍。

先来回顾一下SVM相关知识

SVM

最大间隔

​ 上面也提到了，SVM是在特征空间中找间隔最大的超平面，以此来进行分类的。对于线性可分问题，我们需要求硬间隔最大即可。对于非线性可分问题，我们需要通过核函数映射到高维空间，计算软间隔最大即可。下面以线性可分为例，我们来看一下SVM的形式化表示。

支持向量 & 支持向量平面

​ 支持向量定义为：距超平面距离最近的那些点。如上图所示到超平面距离为、的点。支持向量平面就是恰好过这些点的平面。二分类有两个支持向量平面，这两个平面是平行的。超平面是位于这两个平面中间的。如下图所示，、 即为支持向量平面， 为超平面。我们只需要使 、 的间隔最大，那么超平面的分隔效果就越好。

寻找最大间隔

• 首先我们定义我们要求解的超平面，其实就是我们的线性方程：

为超平面 的法向量，即垂直于超平面的向量，它能决定超平面的方向。b就是截距，能确定超平面的位置。

• 为方便运算我们设支持向量平面为：

• 算最大间隔

  • 假设上有一点，上有一点，如下图所示分别做原点到、的向量。那么我们可以求得两向量的差：。所以我们的间隔就可以表示成：。

  • 我们需要求得距离 最大。

SVR

​ 和回归问题一样，我们都是通过训练样本 ，想要学到我们的回归模型 ，使得 与 近可能接近。

​ 和SVM原理基本一致，SVR也是要找出一个超平面，使得所有数据到这个超平面的距离最小。对样本 ，传统回归模型通常是直接基于模型输出 与 真实 之间的差别来计算损失。当且仅当 的时候损失才为0。SVR与此不同，它假设我们能容忍 与 之间最多有 的偏差。当且仅当 与 之间的差别绝对值大于 时才计算损失。如下图所示，这相当于以超平面 为中心，构建了一个宽度为 的间隔带，若训练样本落入此间隔带，则认为是被预测正确的。

CART树

CART树介绍

​ 在决策树的几个算法中，只有CART树既能做回归又能做分类，并且既能处理连续值又能处理离散值。其核心思想与ID3和C4.5相同，主要的不同处在于CART在每一个节点上都采用二分法，即每个节点都只能有两个子节点，最后构成的是二叉树，所以CART树通常是集成学习树模型的默认基分类器。回归问题中，目标值是连续的，所以CART树最后输出的是划分到叶子节点的训练样本的标签的均值。

回归树的数学表示

一个回归树对应着一个特征空间的一个划分及在划分单元上的是输出值，说白了就是对应着一个左右子树的划分和在叶子结点的预测值。假设已输入特征空间划分为 个单元 ，并且在每个单元 上有一个固定的输出类别 ，这就是以上回归树的数学表示。

• 属于叶子节点是1，不属于叶子结点是0
• 向量和 向量 做内积，权当是一个映射

损失函数

很多书上的公式都给的是SSE，实际sklearn的底层用的是MSE，因为实际上是要除m的，否则会我们计算的会很大。

• 根据误差平方和最小的原则来寻找最优分裂特征和最优分裂点

优化函数(分裂过程)

• 和 分别表示最优切分变量和最优切分点。
• 上述公式表示：样本第 个特征，根据切分点 ，划分为左右子树。分别求左右子树的SSE，加总就是第 个特征的第 分割点的SSE。求最小的SSE，这个特征和分割点就是我们要找的最优特征和最优分割点。

白话分裂过程

​ 我们对于每个特征，将特征值排序，计算特征值两两间的均值作为分割点。小于分割点的去左子树，大于分割点的去右子树。即m个特征，m-1个分隔点。遍历每个特征，再遍历每个分割点。计算以每个分隔点划分的左右子树的SSE。SSE最小的特征和分割点作为最优特征和最优分裂点。

伪代码表示如下：

for j in 特征:
    for s in 分隔点：
        Loss = 左子树SSE + 右子树SSE
        dict[(j,s)] = Loss

• 假设预测值为 并取定值
• 给定
• 计算
  

剪枝

​ 经过算法构建的决策树非常详细，并且分叉可能会多，深度也可能很深，也就是说对于每个特征都被详细的加以考虑，最终叶子节点的训练样本都是纯的，很容易过拟合。并且树模型越复杂，过拟合程度会越高，为了提高决策树的泛化能力，我们采用剪枝来防止过拟合。

• 预剪枝
  • 预剪枝本质就是早停止。
  • 在每一次实际对结点进行进一步划分之前，先采用验证集的数据来验证如果划分是否能提高划分的准确性。如果不能，就把结点标记为叶结点并退出进一步划分。如果可以就继续递归生成节点。
• 后剪枝
  • 本质就是通过衡量剪枝后损失函数变化来决定是否剪枝。
  • 后剪枝是先从训练集生成一颗完整的决策树。然后自底向上地对非叶子结点进行考察，若将该结点对应的子树替换为叶结点能带来泛化性能提升，则将该子树替换为叶结点。
• 两种剪枝的对比
  • 后剪枝决策树通常比预剪枝决策树保留了更多的分支。
  • 后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝。
  • 后剪枝训练时间开销比未剪枝和预剪枝的都要大。
  • 常用后剪枝。

随机森林

百度百科

​ 在机器学习中，随机森林是一个包含多个决策树的分类器， 并且其输出的类别是由个别树输出的类别的众数而定。随机森林指的是利用多棵树对样本进行训练并预测的一种分类器。

bagging思想

​ 随机森林是基分类器为决策树的bagging算法，bagging是集成学习的思想之一。bagging思想首先是采用M轮的bootstrap自助采样，每轮采样对应训练一个弱分类器，并且训练的时候是并行计算的，最后将这M个弱分类器进行组合来实现预测的。由于自助采样，所以bagging是通过样本扰动的方式来增加基分类器的差异性，差异性越大，集成效果越好。因此bagging的基学习器应为对训练样本扰动敏感的算法，这就是bagging思想。

受样本扰动敏感：LR、NN、决策树

白话原理

​ 随机森林在bagging样本随机的基础上，增加了特征随机。默认的基分类器就是CART树。它相比于单颗决策树，RF的预测结果更加准确，并且可以输出特征的重要性排序。因为要保证若分类器之间的差异性，所以随机森林的每个弱分类器都不需要剪枝。由于两个随机的思想，即使不剪枝也不容易发生过拟合。由于并行训练和特征随机所以RF的训练速度要比决策树快。RF的构建流程大致分为这几步：

• 1.根据自助采样抽取M个样本集。每个样本集从原来的N个训练样本中有放回的随机抽取N个样本。未被抽取到的36.8%的样本组成袋外数据用于测试。

• 2.从候选特征中随机的无放回的抽取K个特征。

• 3.用每个样本集和特征集并行的构建弱分类器。

• 4.这样M个样本集一共训练出M课决策树，组成随机森林。

  • 如果是分类问题，则各个弱分类器以投票的方式决定预测结果，最终输出类别就是得票最多的。
  • 如果是回归问题，则最终预测值就是各个弱分类器输出值的算术平均。

RF比较适用于可解释性要求不高，准去率要求较高的场合。其实当森林中决策树很多时，虽然是并行训练，它的训练时间也挺大。

为什么随机抽样？

• 保证基分类器的多样性，若每棵树的样本集都一样，那训练的每棵决策树都是一样的。

为什么要有放回的抽样？

• 保证样本集间有重叠，若不放回，每个训练样本集及其分布都不一样，可能导致训练的各决策树差异性很大，最终多数表决无法 “求同”。

为什么不用全样本训练？

• 全样本忽视了局部样本的规律，不利于模型泛化能力。

为什么要随机特征？

• 随机特征保证基分类器的多样性（差异性），最终集成的泛化性能可通过个体学习器之间的差异度而进一步提升，从而提高泛化能力和抗噪能力。

RF为什么比bagging效率高？

• bagging无随机特征，使得训练决策树时效率更低。

为什么自助采样会有36.8%的概率没有被采样到？

GBDT

boosting思想

​ Boosting一族是可将弱学习器提升为强学习器的算法，它的思想就是每一个基分类器纠正前一个基分类器的错误，至于纠正的方式不同所以有不同的boosting算法。算法思想如下：

1. 先从训练集训练出一个基学习器。
2. 再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续得到较大的关注。
3. 然后基于调整后的样本分布来训练下一个基学习器。
4. 如此重复进行，直到基学习器数目达到指定的阈值T位置。
5. 再将这T个基学习器进行加权结合得到强集成学习器。

AdaBoost思想

在boosting思想的基础上，adaboost思想如下：

1. 初始化训练集权重，从初始训练集里训练得到一个基学习器
2. 增加错分样本的权重，减少分对样本的权重
3. 增加错误率小的基学习器的权重，减少错误率大的基学习器的权重
4. 用调整后的(样本权重归一化)样本训练下一个基学习器
5. 直到基学习器的数目达到实现指定的值
6. 然后将这几个基学习器加权进行投票

提升树 & 梯度提升

​ 提升树其实就是加法模型，它每一步产生一个弱学习器，并加权累加到总模型中。如果每一步的弱学习器生成都是依据损失函数的负梯度方向，则称之为梯度提升。在GBDT中，提升树在构建树的每一步过程中，都去拟合上一步获得模型在训练集的残差，这个残差正好是损失函数的负梯度方向。也就是提升算法通过迭代的选择一个负梯度方向上的基函数来逐渐逼近局部极小值。分类问题时，提升树其实就是基学习器为CART分类树的adaboost。回归问题时，提升树是基学习器为CART回归树的adaboost。

GBDT

严格意义来讲，做回归时称为GBRT，做分类时称为GBDT。以下统称为GBDT。

白话原理

​ GBDT全称是梯度提升决策树，是boosting家族的一员，它的叫法有很多，如TreeLink、GBRT、TreeNet。其实本质就是加法模型，通过多棵树的累加和不断的减小训练过程产生的残差来达到预测的目的。

拆开来看，它分为GB和DT。

• GB(Grandient Boosting):梯度提升的意思：梯度提升是指对损失函数求导，损失函数的负梯度方向就是近似残差，每轮的CART树拟合上一次的残差，通过梯度下降使残差越来越小。
• DT(Decision tree)：决策树：默认的基分类器是CART回归树。因为每次迭代要拟合的是梯度值，也就是连续值，而且最后累加所有树的预测结果作为最终结果，分类树的结果没有办法累加，所有要用回归树。

GBDT是建立在提升树的思想基础上，即每次迭代都学习一棵CART树来拟合前t-1棵树在训练集上的残差。

拟合残差就是逐步逼近的过程，数学角度来讲本质就是对损失函数一阶泰勒展开。泰勒公式逼近任何一个多项式，求它的近似值。

对于GBDT而言，这个残差正好是损失函数的负梯度，要让损失函数(均方误差)最小，就要在负梯度的方向上进行梯度下降。说的再直白一点，GBDT的每个基分类器都是对残差进行预测，每一次的计算都是为了减少上一次的残差，所以为了消除残差，在残差减小的梯度方向上建立模型进行梯度下降，这与传统的Boosting中关注样本和基分类器的权重有着很大的区别。所以GBDT的构建步骤可以分为两步，首先就是根据损失函数计算残差，然后就是训练回归树拟合残差。

GBDT里也用了学习率，是Shrinkage的一个思想，如果每棵树的结果直接全部加起来很容易一步学到位导致过拟合，所以基于Shrinkage的思想，为每棵树设置了一个权重，累加的时候要乘上这个权重，主要是为了削弱每棵树的影响，让后面有更大的学习空间。所以将每棵回归树对应的结果乘学习率(第一棵树不乘)，加总就是最终预测值。

关键点就是利用损失函数的负梯度去拟合残差，对于损失函数求一阶导数

GBDT对弱分类器的要求一般是低方差和高偏差的，因为训练过程是通过不断降低偏差(残差)来提高分类器的精度

举个例子

面试题整理

优缺点 & 适用场景

• 优点：GBDT基于树模型，继承了树模型的优点 [对异常点鲁棒、不相关的特征（即非线性特征）干扰性低（LR需要加正则）、可以很好地处理缺失值，处理高维数据] ，同时又避免了决策树易出现过拟合的现象。
• 缺点：基分类器间相互依赖，难以并行训练。
• 如果其它线性模型拟合的效果不好，可以用GBDT，对于回归而言，可以尝试Huber损失的GBDT。

梯度提升，梯度体现在哪？

• 每次预测的是上一次的残差，在损失函数的梯度方向，残差要越来越小。

GBDT过拟合了怎么办？

• 限制树的最大深度
• 限制叶子节点的最少样本数量
• 借鉴RF的两个随机思想
• 正则项
• 迭代次数(早停止)
• 随机梯度下降

树的复杂度由哪方面体现？
树的层数
叶子节点个数
L1、L2

GBDT输出

• 当一个样本进入GBDT之中后，会在每一个基学习器(CART树)上得到一个output，通过对各个基学习器的output求和(除第一棵树外，其他的树要乘以学习率)，得到最终的输出。

GBDT与RF之间的区别

• 相同点
  • 都是由多棵树组成，最终的结果都是由多棵树一起决定
• 不同点
  • 从集成学习的角度来讲：RF属于bagging思想，而GBDT是boosting思想
  • 从权衡方差偏差角度来讲：RF不断的降低模型的方差，而GBDT不断的降低模型的偏差
  • 从训练样本角度来讲：RF每次迭代的样本是从全部训练集中有放回抽样形成的，而GBDT每次使用全部样本
  • 从树的生成角度来讲：RF的树是并行生成，而GBDT只能顺序生成(需要等上一棵树完全生成)
  • 从结果角度来讲：分类问题随机森林的结果是多棵树投票表决，回归问题是多棵树算术平均。而GBDT是加权融合
  • 从数据敏感性角度来讲：``随机森林对异常值不敏感。GBDT对异常值比较敏感
  • 从泛化能力来看：RF不易过拟合，而GBDT容易过拟合
  • 随机森林不需要进行特征归一化。GBDT最好进行特征归一化，梯度下降收敛快一些

GBDT和Adaboost的区别

• 1.GBDT每次迭代沿梯度下降最快方向学习去弥补模型的不足; Adaboost每次迭代提升错误样本权重来弥补模型的不足；
• 2.GBDT可选多种目标函数，当为均方误差时，正好为残差；Adaboost目标函数为指数损失函数
• 3.GBDT无更新样本分布，无分类器权重；Adaboost都有
• 4.GBDT输出为累加；Adaboost分类为多数表决，回归为取平均值
• 5.GBDT分类器只能是CART回归树；Adaboost可有其他类型分类器

GBDT和LR的区别

• 1.LR是线性模型，可解释性强，很容易并行化，但学习能力有限，需要大量的人工特征工程
• 2.GBDT是非线性模型，具有天然的特征组合优势，特征表达能力强，但是树与树之间无法并行训练，而且树模型很容易过拟合
• 当在高维稀疏特征的场景下，LR的效果一般会比GBDT好

GBDT为什么要拟合前面几轮的残差？

• 损失函数的负梯度方向在当前模型的值近似残差，每一轮迭代尽量去拟合残差，使得最终累加结果趋近真实值

GBDT通过什么方式减少误差？

• 不断迭代去拟合残差

为什么只能用CART回归树？

• 源于GBDT的核心思想中需要将所有树的预测值累计，而分类树的结果显然是没办法累加的，比如男+男+女=到底是男是女，所以GBDT中的树都是回归树，不是分类树

GBDT为什么要用梯度下降？

• 负梯度是损失函数下降最快的方向，即为快速找到最小损失函数

GBDT如何做特征选择？

• 计算每棵树非叶子节点分裂后平方损失的减少，减少得越多说明特征越重要

为什么GBDT的树深度较RF浅？

• GBDT利用残差逼近不断拟合原数据，每一轮都需要保证一定的偏差，所以每棵决策树更浅
• RF并行训练不同的分类器+输出为多数表决—> 因此需要每棵决策树尽可能去拟合样本—>基本不剪枝

GBDT如何加速训练？

• 预排序,预排序可以加速查找最佳分裂点;

GBDT哪些部分可以并行？

• 1.计算每个样本的负梯度；
• 2.选取最佳分割点时；
• 3.预测时将每个样本之前的值累加时

GBDT为什么要归一化？

• 1.加快梯度下降收敛速度，避免震荡现象
• 2.提高精度

XGBOOST

​ XGBOOST是在GBDT的基础上做的改进和优化，GBDT对损失函数梯度下降，XGB对损失函数二阶泰勒展开，运算速度和准确度都相对高一些。

XGBOOST的boosting策略和GBDT基本一样，都是通过加法模型，不断拟合残差来达到预测效果的。不同点在于：

• 传统的GBDT以CART回归树做基分类器，XGBOOST的基学习器除了可以是CART外，还支持线性分类器。
• 传统GBDT在优化时只用到一阶导数信息。XGBOOST则对代价函数进行了二阶泰勒展开(牛顿法)，同时用到了一阶和二阶导数。可以更为精准的逼近真实的损失函数。XGBOOST还支持自定义代价函数，只要代价函数一阶和二阶可导就可以。
• XGBOOST在代价函数中加入了正则项，用于控制模型复杂度。相当于预剪枝。从权衡方差偏差角度来看，降低了模型的方差，这也是优于传统GBDT的一个特性。
• XGBOOST还借鉴了随机森林的特征抽样，就是所谓的列采样，对每棵树随机选择特征子集，不仅能防止过拟合，还能减少计算。
• XGBOOST还支持并行化，这里的并行化并不是树与树之间的并行，XGB本质还是boosting训练串行的思想。它是指特征维度的并行，由于CART树最耗时的步骤是对特征值进行排序（因为要计算最佳分裂点），XGBOOST在训练之前，预先对每一列进行排序，存储为block块结构，在后面查找特征分割点时可以重复使用，而且特征已经被存储为一个个block结构，那么在寻找每个特征的最佳分割点时，可以利用多线程并行的对每个block并行计算查找每个特征的最佳分割点，极大地提升训练速度。这也就是所谓的预排序。
• 另外我印象中XGBOOST对缺失值的处理是分别假设这些样本属于左子树和右子树，然后比较两者的分裂增益，选择增益较大的那一边作为该样本的分裂方向。

XGBOOST差不多就对GBDT做了这些优化，它在可扩展性和训练速度和精度上都有了巨大的提升，但是核心思想是没有发生太大变化的。

面试题整理

XGBoost为什么使用泰勒二阶展开？

• 相对于GBDT的一阶泰勒展开，XGBoost采用二阶泰勒展开，可以更为精准的逼近真实的损失函数。
• 可扩展性提高，损失函数支持自定义，只需要新的损失函数二阶可导。

XGBoost为什么快？

• 分块并行：训练前每个特征按特征值进行排序并存储为Block结构，后面查找特征分割点时重复使用，并且支持并行查找每个特征的分割点。

XGBoost防止过拟合的方法？

• 目标函数添加正则项：叶子节点个数+叶子节点权重的L2正则化
• 列抽样：训练的时候只用一部分特征（不考虑剩余的block块即可）
• 子采样：每轮计算可以不使用全部样本，使算法更加保守
• shrinkage: 可以叫学习率或步长，为了给后面的训练留出更多的学习空间

GBDT、XGBoost中的一棵树的停止生长条件？

• 当新引入的一次分裂所带来的增益Gain<0时，放弃当前的分裂
• 当树达到最大深度时，停止建树，因为树的深度太深容易出现过拟合，这里需要设置一个超参数max_depth
• 当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值，也会放弃此次分裂。这涉及到一个超参数: 最小样本权重和，是指如果一个叶子节点包含的样本数量太少也会放弃分裂，防止树分的太细。

XGBoost如何处理不平衡数据？

• 对于不平衡的数据集，例如用户的购买行为，肯定是极其不平衡的，这对XGBoost的训练有很大的影响，XGBoost有两种自带的方法来解决：

  • 第一种，如果你在意AUC，采用AUC来评估模型的性能，那你可以通过设置scale_pos_weight来平衡正样本和负样本的权重。例如，当正负样本比例为1:10时， scale_pos_weight可以取10；

  • 第二种，如果你在意概率(预测得分的合理性)，你不能重新平衡数据集(会破坏数据的真实分布)，应该设置max_delta_step为一个有限数字来帮助收敛（基模型为LR时有效）。

  • 除此之外，还可以通过上采样、下采样、SMOTE算法或者自定义代价函数的方式解决正负样本不平衡的问题。

XGBoost中如何对树进行剪枝？

• 在目标函数中增加了正则项，控制树的复杂度。
• 在结点分裂时，定义了一个阈值，如果分裂后目标函数的增益小于该阈值，则不分裂。
• 当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值（最小样本权重和），也会放弃此次分裂。

XGBoost如何寻找最优特征(最佳分裂点)？

• XGBoost在训练的过程中给出各个特征的增益评分，最大增益的特征会被选出来作为分裂依据，从而记忆了每个特征对模型训练时的重要性。从内部节点中涉及某特征的次数作为该特征的重要性排序。
  • weight：该特征在所有树中被用作分割样本的特征的总次数。
    • gain：该特征在其出现过的所有
    • 树中产生的平均增益。

XGBooost参数调优的一般步骤？

• 首先可以考虑learning rate学习率，一般初识为0.1就可以
• 还可以调整max_depth每棵子树的最大深度 和 min_child_weight子节点的权重阈值，一般来说最大深度可以从3-10里迭代的修正。权重阈值的话可以在1-6。
• 还可以调整gamma，也叫最小划分损失min_split_loss，一般是0.1-0.5
• 还可以加L1或L2，降低学习率(0.01-0.1)等等

代码角度讲，XGBooost过拟合了怎么办？

• 第一类参数：用于直接控制模型的复杂度。包括max_depth,min_child_weight,gamma 等参数
• 第二类参数：用于增加随机性，从而使得模型在训练时对于噪音不敏感。包括subsample,colsample_bytree还有就是直接减小learning rate，但需要同时增 加estimator 参数。

为什么XGBoost相比某些模型对缺失值不敏感？

• 一棵树中每个结点在分裂时，寻找的是某个特征的最佳分裂点（特征值），完全可以不考虑存在特征值缺失的样本，也就是说，如果某些样本缺失的特征值缺失，对寻找最 佳分割点的影响不是很大。

XGB的原理是什么，学习的目标是什么，每个学习器学习的是什么？

• 原理和GBDT一样，都是加法模型，串行的生成树。学习的目标也和GBDT一样，拟合上一棵树的残差让残差最小，无非就是它是对代价函数进行二阶泰勒展开。

优缺点 & 适用场景

• 优点：基于二阶泰勒展开，所以能精确的找到分割点。精度往往比GBDT高一些。
• 缺点：空间消耗大，算法需要保存数据的特征值，还要保存特征排序的结果。在遍历每一个分割点的时候，都需要进行分裂增益的计算。
• 在GBDT效果不理想的时候，可以用XGB试试。集成家族性能往往由于传统线性模型。

LightGBM

​ 常用的机器学习算法，例如线性回归、神经网络等，都可以以mini-batch的方式训练，训练数据的大小不会受到内存限制。而GBDT家族在每一次迭代的时候，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。尤其面对工业级海量的数据，GBDT、XGBOOST是不能满足其需求的。所以LightGBM应运而生。原理上它和GBDT及XGBoost类似，都采用损失函数的负梯度作为当前决策树的残差近似值，去拟合新的决策树。

XGBoost的缺点

​ 上面也提到过XGB是基于预排序方法的决策树算法。这种构建决策树的算法基本思想是：首先，对所有特征都按照特征的数值进行预排序。其次，在遍历分割点的时候用的代价找到一个特征上的最好分割点。最后，在找到一个特征的最好分割点后，将数据分裂成左右子节点。这样的预排序算法的优点是能精确地找到分割点。但是缺点也很明显：

• 首先，空间消耗大。这样的算法需要保存数据的特征值，还保存了特征排序的结果（例如，为了后续快速的计算分割点，保存了排序后的索引），这就需要消耗训练数据两倍的内存。
• 其次，时间上也有较大的开销，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。
• 最后，对cache优化不友好。在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的cache miss。

LightGBM的优化

​ 为了避免上述XGBoost的缺陷，并且能够在不降低准确率的条件下加快XGB模型的训练速度，lightGBM在XGB算法上进行了如下优化：

• 基于Histogram的决策树算法。
• 单边梯度采样 Gradient-based One-Side Sampling(GOSS)：使用GOSS可以减少大量只具有小梯度的数据实例，这样在计算信息增益的时候只利用剩下的具有高梯度的数据就可以了，相比XGBoost遍历所有特征值节省了不少时间和空间上的开销。
• 互斥特征捆绑 Exclusive Feature Bundling(EFB)：使用EFB可以将许多互斥的特征绑定为一个特征，这样达到了降维的目的。
• 带深度限制的Leaf-wise的叶子生长策略：大多数GBDT工具使用低效的按层生长 (level-wise) 的决策树生长策略，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销。实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。LightGBM使用了带有深度限制的按叶子生长 (leaf-wise) 算法。
• 直接支持类别特征(Categorical Feature)
• 支持高效并行
• Cache命中率优化

基于Histogram的决策树算法

直方图算法

​ Histogram algorithm应该翻译为直方图算法，直方图算法的基本思想是：先把连续的浮点特征值离散化成 个整数，同时构造一个宽度为 的直方图。在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。

​ 我们知道特征离散化具有很多优点，如存储方便、运算更快、鲁棒性强、模型更加稳定等。对于直方图算法来说最直接的有以下两个优点：

• 内存占用更小：直方图算法不仅不需要额外存储预排序的结果，而且可以只保存特征离散化后的值，而这个值一般用8位整型存储就足够了，内存消耗可以降低为原来的。也就是说XGBoost需要用位32的浮点数去存储特征值，并用位32的整形去存储索引，而 LightGBM只需要用8位去存储直方图，内存相当于减少为；
• 计算代价更小：预排序算法XGBoost每遍历一个特征值就需要计算一次分裂的增益，而直方图算法LightGBM只需要计算 次（ 可以认为是常数)，直接将时间复杂度从 降到，且。

当然，Histogram算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在不同的数据集上的结果表明，离散化的分割点对最终的精度影响并不是很大，甚至有时候会更好一点。原因是单个决策树在这是弱模型，分割点是不是精确并不是太重要；较粗的分割点也有正则化的效果，可以有效地防止过拟合；即使单棵树的训练误差比精确分割的算法稍大，但在梯度提升的框架下没有太大的影响。

直方图做差加速

​ LightGBM另一个优化是Histogram（直方图）做差加速。一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到，在速度上可以提升一倍。通常构造直方图时，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的k个桶。在实际构建树的过程中，LightGBM还可以先计算直方图小的叶子节点，然后利用直方图做差来获得直方图大的叶子节点，这样就可以用非常微小的代价得到它兄弟叶子的直方图。

XGBoost 在进行预排序时只考虑非零值进行加速，而 LightGBM 也采用类似策略：只用非零特征构建直方图。

带深度限制的 Leaf-wise 算法

​ 在Histogram算法之上，LightGBM进行进一步的优化。首先它抛弃了大多数GBDT工具使用的按层生长(level-wise) 的决策树生长策略，而使用了带有深度限制的按叶子生长(leaf-wise)算法。

​ XGBoost 采用Level-wise的增长策略，该策略遍历一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，实际上很多叶子的分裂增益较低，没必要进行搜索和分裂，因此带来了很多没必要的计算开销。

​ LightGBM采用Leaf-wise的增长策略，该策略每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。因此同Level-wise相比，Leaf-wise的优点是：在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度；Leaf-wise的缺点是：可能会长出比较深的决策树，产生过拟合。因此LightGBM会在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。

单边梯度采样算法

​ Gradient-based One-Side Sampling 应该被翻译为单边梯度采样（GOSS）。GOSS算法从减少样本的角度出发，排除大部分小梯度的样本，仅用剩下的样本计算信息增益，它是一种在减少数据量和保证精度上平衡的算法。

​ AdaBoost中，样本权重是数据重要性的指标。然而在GBDT中没有原始样本权重，不能应用权重采样。幸运的是，我们观察到GBDT中每个数据都有不同的梯度值，对采样十分有用。即梯度小的样本，训练误差也比较小，说明数据已经被模型学习得很好了，直接想法就是丢掉这部分梯度小的数据。然而这样做会改变数据的分布，将会影响训练模型的精确度，为了避免此问题，提出了GOSS算法。

​ GOSS是一个样本的采样算法，目的是丢弃一些对计算信息增益没有帮助的样本留下有帮助的。根据计算信息增益的定义，梯度大的样本对信息增益有更大的影响。因此，GOSS在进行数据采样的时候只保留了梯度较大的数据，但是如果直接将所有梯度较小的数据都丢弃掉势必会影响数据的总体分布。所以，GOSS首先将要进行分裂的特征的所有取值按照绝对值大小降序排序`（XGBoost一样也进行了排序，但是LightGBM不用保存排序后的结果）。选取绝对值最大的 个数据。然后在剩下的较小梯度数据中随机选择 $b * 100% $个数据。接着将这 $ b * 100% $ 个数据乘以一个常数 ，这样算法就会更关注训练不足的样本，而不会过多改变原数据集的分布。最后使用这 个数据来计算信息增益。

互斥特征捆绑算法

​ 高维度的数据往往是稀疏的，这种稀疏性启发我们设计一种无损的方法来减少特征的维度。通常被捆绑的特征都是互斥的（即特征不会同时为非零值，像one-hot），这样两个特征捆绑起来才不会丢失信息。如果两个特征并不是完全互斥（部分情况下两个特征都是非零值），可以用一个指标对特征不互斥程度进行衡量，称之为冲突比率，当这个值较小时，我们可以选择把不完全互斥的两个特征捆绑，而不影响最后的精度。互斥特征捆绑算法（Exclusive Feature Bundling, EFB）指出如果将一些特征进行融合绑定，则可以降低特征数量。这样在构建直方图时的时间复杂度从 变为 ，这里 指特征融合绑定后特征包的个数，且 。

针对这种想法，我们会遇到两个问题：

• 怎么判定哪些特征应该绑在一起？
• 怎么把特征绑为一个？

解决哪些特征应该绑在一起

​ 将相互独立的特征进行绑定是一个 NP难题，LightGBM的EFB算法将这个问题转化为图着色的问题来求解，将所有的特征视为图的各个顶点，将不是相互独立的特征用一条边连接起来，边的权重就是两个相连接的特征的总冲突值，这样需要绑定的特征就是在图着色问题中要涂上同一种颜色的那些点（特征）。此外，我们注意到通常有很多特征，尽管不是100％相互排斥，但也很少同时取非零值。 如果我们的算法可以允许一小部分的冲突，我们可以得到更少的特征包，进一步提高计算效率。具体步骤可以总结如下：

1. 构造一个加权无向图，顶点是特征，边有权重，其权重与两个特征间冲突相关；
2. 根据节点的度进行降序排序，度越大，与其它特征的冲突越大；
3. 遍历每个特征，将它分配给现有特征包，或者新建一个特征包，使得总体冲突最小。

解决怎么把特征绑为一捆

​ 特征合并算法，其关键在于原始特征能从合并的特征中分离出来。绑定几个特征在同一个bundle里需要保证绑定前的原始特征的值可以在bundle中识别，考虑到histogram-based算法将连续的值保存为离散的bins，我们可以使得不同特征的值分到bundle中的不同bin（箱子）中，这可以通过在特征值中加一个偏置常量来解决。比如，我们在bundle中绑定了两个特征A和B，A特征的原始取值为区间[0,10)，B特征的原始取值为区间[0,20），我们可以在B特征的取值上加一个偏置常量10，将其取值范围变为[10,30），绑定后的特征取值范围为 [0, 30），这样就可以放心的融合特征A和B了。

直接支持类别特征

​ 实际上大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征，通过 one-hot 编码，转化到多维的0/1特征，降低了空间和时间的效率。但我们知道对于决策树来说并不推荐使用 one-hot 编码，尤其当类别特征中类别个数很多的情况下，会存在以下问题：

1. 会产生样本切分不平衡问题，导致切分增益非常小（即浪费了这个特征）。使用 one-hot编码，意味着在每一个决策节点上只能使用one vs rest（例如是不是狗，是不是猫等）的切分方式。例如，动物类别切分后，会产生是否狗，是否猫等一系列特征，这一系列特征上只有少量样本为 1，大量样本为 0，这时候切分样本会产生不平衡，这意味着切分增益也会很小。较小的那个切分样本集，它占总样本的比例太小，无论增益多大，乘以该比例之后几乎可以忽略；较大的那个拆分样本集，它几乎就是原始的样本集，增益几乎为零。比较直观的理解就是不平衡的切分和不切分没有区别。
2. 会影响决策树的学习。因为就算可以对这个类别特征进行切分，独热编码也会把数据切分到很多零散的小空间上，如下图左边所示。而决策树学习时利用的是统计信息，在这些数据量小的空间上，统计信息不准确，学习效果会变差。但如果使用下图右边的切分方法，数据会被切分到两个比较大的空间，进一步的学习也会更好。下图右边叶子节点的含义是X=A或者X=C放到左孩子，其余放到右孩子。

支持高效并行

特征并行

​ 特征并行的主要思想是不同机器在不同的特征集合上分别寻找最优的分割点，然后在机器间同步最优的分割点。XGBoost使用的就是这种特征并行方法。这种特征并行方法有个很大的缺点：就是对数据进行垂直划分，每台机器所含数据不同，然后使用不同机器找到不同特征的最优分裂点，划分结果需要通过通信告知每台机器，增加了额外的复杂度。

​ LightGBM 则不进行数据垂直划分，而是在每台机器上保存全部训练数据，在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。具体过程如下图所示。

传统的数据并行策略主要为水平划分数据，让不同的机器先在本地构造直方图，然后进行全局的合并，最后在合并的直方图上面寻找最优分割点。这种数据划分有一个很大的缺点：通讯开销过大。如果使用点对点通信，一台机器的通讯开销大约为 ，如果使用集成的通信，则通讯开销为 。LightGBM在数据并行中使用分散规约(Reduce scatter) 把直方图合并的任务分摊到不同的机器，降低通信和计算，并利用直方图做差，进一步减少了一半的通信量。具体过程如下图所示。

投票并行

基于投票的数据并行则进一步优化数据并行中的通信代价，使通信代价变成常数级别。在数据量很大的时候，使用投票并行的方式只合并部分特征的直方图从而达到降低通信量的目的，可以得到非常好的加速效果。具体过程如下图所示。

大致步骤为两步：

1. 本地找出 Top K 特征，并基于投票筛选出可能是最优分割点的特征；
2. 合并时只合并每个机器选出来的特征。

Cache命中率优化

​ XGBoost对cache优化不友好，如下图所示。在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的cache miss。为了解决缓存命中率低的问题，XGBoost 提出了缓存访问算法进行改进。

优缺点

优点

（1）速度更快

• LightGBM 采用了直方图算法将遍历样本转变为遍历直方图，极大的降低了时间复杂度；
• LightGBM 在训练过程中采用单边梯度算法过滤掉梯度小的样本，减少了大量的计算；
• LightGBM 采用了基于 Leaf-wise 算法的增长策略构建树，减少了很多不必要的计算量；
• LightGBM 采用优化后的特征并行、数据并行方法加速计算，当数据量非常大的时候还可以采用投票并行的策略；
• LightGBM 对缓存也进行了优化，增加了缓存命中率；

（2）内存更小

• XGBoost使用预排序后需要记录特征值及其对应样本的统计值的索引，而 LightGBM 使用了直方图算法将特征值转变为 bin 值，且不需要记录特征到样本的索引，将空间复杂度从 降低为 ，极大的减少了内存消耗；
• LightGBM 采用了直方图算法将存储特征值转变为存储 bin 值，降低了内存消耗；
• LightGBM 在训练过程中采用互斥特征捆绑算法减少了特征数量，降低了内存消耗。

缺点

• 可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度限制，在保证高效率的同时防止过拟合；
• Boosting族是迭代算法，每一次迭代都根据上一次迭代的预测结果对样本进行权重调整，所以随着迭代不断进行，误差会越来越小，模型的偏差（bias）会不断降低。由于LightGBM是基于偏差的算法，所以会对噪点较为敏感；
• 在寻找最优解时，依据的是最优切分变量，没有将最优解是全部特征的综合这一理念考虑进去；

LightGBM与XGBoost的联系和区别

（1）LightGBM使用了基于histogram的决策树算法，这一点不同于XGBoost中的贪心算法和近似算法，histogram算法在内存和计算代价上都有不小优势。

• 1）内存上优势：很明显，直方图算法的内存消耗为 (因为对特征分桶后只需保存特征离散化之后的值)，而XGBoost的贪心算法内存消耗为： ，因为XGBoost既要保存原始feature的值，也要保存这个值的顺序索引，这些值需要32位的浮点数来保存。
• 2）计算上的优势：预排序算法在选择好分裂特征计算分裂收益时需要遍历所有样本的特征值，时间为 , 而直方图算法只需要遍历桶就行了，时间为 。

（2）XGBoost采用的是level-wise的分裂策略，而LightGBM采用了leaf-wise的策略，区别是XGBoost对每一层所有节点做无差别分裂，可能有些节点的增益非常小，对结果影响不大，但是XGBoost也进行了分裂，带来了不必要的开销。leaft-wise的做法是在当前所有叶子节点中选择分裂收益最大的节点进行分裂，如此递归进行，很明显leaf-wise这种做法容易过拟合，因为容易陷入比较高的深度中，因此需要对最大深度做限制，从而避免过拟合。

（3）XGBoost在每一层都动态构建直方图，因为XGBoost的直方图算法不是针对某个特定的特征，而是所有特征共享一个直方图(每个样本的权重是二阶导)，所以每一层都要重新构建直方图，而LightGBM中对每个特征都有一个直方图，所以构建一次直方图就够了。

（4）LightGBM使用直方图做差加速，一个子节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到，从而加速计算。

（5）LightGBM支持类别特征，不需要进行独热编码处理。

（6）LightGBM优化了特征并行和数据并行算法，除此之外还添加了投票并行方案。

（7）LightGBM采用基于梯度的单边采样来减少训练样本并保持数据分布不变，减少模型因数据分布发生变化而造成的模型精度下降。

（8）特征捆绑转化为图着色问题，减少特征数量。

时间序列-ARIMA

关于时间序列及时间序列分析，这里只围绕ARIMA介绍，有兴趣的朋友可以看王艳的应用时间序列分析这本书。

百度百科

​ 时间序列（或称动态数列）是指将同一统计指标的数值按其发生的时间先后顺序排列而成的数列。时间序列分析的主要目的是根据已有的历史数据对未来进行预测。经济数据中大多数以时间序列的形式给出。根据观察时间的不同，时间序列中的时间可以是年份、季度、月份或其他任何时间形式。

时间序列数据

​ 时序数据就是在时间上分布的一系列数值。生活中常见的时序数据包括，股票价格、广告数据、气温变化、网站的PV/UV、个人健康数据、工业传感器数据、服务器系统监控数据（比如CPU和内存占用率）、车联网等。

数据平稳性

​ 平稳性就是要求经由样本时间序列所得到的拟合曲线在未来的一段期间内仍能顺着现有的形态“惯性”地延续下去。平稳性要求序列的均值和方差不发生明显变化。我们的时序数据可以分为以下三个种类：

• 白噪声序列：白噪声的意思是指它是纯随机性的序列，它是没有预测的价值的。当我们遇到白噪声序列(纯随机序列)的时候我们就可以停止我们的分析。
• 平稳的非白噪声序列：最常见的序列，它的均值、方差都是常数。我们有很多成熟的模型去拟合，比如AR、MA、ARMA。
• 非平稳序列：当我们遇到非平稳序列的时候，我们需要通过差分等方法把它转化为平稳序列，再用平稳序列的方法去拟合。比如通过差分变换，再用ARIMA去拟合。

ARIMA

AR（自回归模型）

• 描述当前值与历史值之间的关系，用变量自身的历史时间数据对自身进行预测，所以只适用于预测与自身前期相关的现象

• 自回归模型必须满足平稳性的要求，且必须有自相关性

• 阶自回归过程的公式定义：
  

  • 表示当前值
  • 是常数项，和回归方程中的意义一样
  • 是阶数，表示时间间隔，比如，可以理解为间隔1天(今天和昨天)，表示当前值和前个值是有关系的
  • 是自相关系数，和回归方程的意义一样，是待求解参数，比如老生常谈的最小二乘、梯度下降等
  • 是误差
  • 当前值和前1天有关、和前2天有关，累加表示当前要预测的值表示和前1天、前2天、前天都有关

MA（移动平均模型）

• 它关注的是自回归模型中的误差项的累加

• 目的是消除预测中的随即波动，让误差越均衡越好

• 阶自回归过程的公式定义：
  

  • 我们需要求解的是参数和误差项组合是更合适的，能够较好的消除随机波动的

ARMA（自回归移动平均模型）

• 自回归与移动平均的结合

• 公式定义：
  

  • 是需要指定的超参
  • 是需要求解的参数

ARIMA(p，d，q)（差分自回归移动平均模型）

• 将非平稳时间序列转化为平稳时间序列，然后将因变量仅对它的滞后值(阶数)以及随机误差项的现值和滞后值进行回归所建立的模型
• AR是自回归，是自回归项，也成为滞后值，表示滞后2阶
• MA为移动平均，为移动平均数
• 为时间序列成为平稳时所做的差分次数

ACF&PACF

ACF和PACF是帮助我们选择超参的。

ACF（自相关函数）

• 有序的随机变量序列与其自身相比较，自相关函数反映了同一序列在不同时序的取值之间的相关性。

PACF（偏自相关函数）

• 对于一个平稳AR§模型，求出滞后k自相关系数时，实际上得到并不是与之间单纯的相关关系
• 同时还会受到中间k-1个随机变量的影响。而这k-1个随机变量又都和具有相关关系。所以自相关系数p(k)里实际掺杂了其它变量对与的影响。
• PACF是剔除了中间k-1个随机变量的干扰后，对影响的相关程度。
• ACF还包含了其它变量的影响，而偏自相关系数是严格这两个变量之间的相关性。

ACI&BIC

经常地，对一堆数据进行建模的时候，特别是分类和回归模型，我们有很多的变量可供使用，选择不同的变量组合可以得到不同的模型，例如我们有5个变量，2的5次方，我们将有32个变量组合，可以训练出32个模型。但是哪个模型更加的好呢？目前常用有如下方法：

• ：赤池信息量
• ：贝叶斯信息量
• L是在该模型下的最大似然，n是数据数量，k是模型的变量个数
• AIC、BIC 越小模型越好

三个模型A, B, C，在通过这些规则计算后，我们知道B模型是三个模型中最好的，但是不能保证B这个模型就能够很好地刻画数据，因为很有可能这三个模型都是非常糟糕的，B只是烂苹果中的相对好的苹果而已。
这些规则理论上是比较漂亮的，但是实际在模型选择中应用起来还是有些困难的，我们不可能对所有这些模型进行一一验证AIC, BIC，HQ规则来选择模型，工作量太大。

关于AIC、BIC详细阐述见：https://zhuanlan.zhihu.com/p/142489599

• BIC的惩罚项比AIC大，考虑了样本个数，样本数量多，可以防止模型精度过高造成的模型复杂度过高。
• AIC和BIC前半部分是一样的，BIC考虑了样本数量，样本数量过多时，可有效防止模型精度过高造成的模型复杂度过高。

时间序列分析步骤

• 拿到待分析时序数据
• 平稳性检验
• 白噪声检验
• 定阶
• 建模预测

平稳性检验

​ 平稳性检验是整个时间序列分析的第一步，也就是说当我们拿到时序数据后的第一件事就是做平稳性检验。通常平稳性检验的方法有：单位根检验，来检验我们的序列是否符合平稳性。对于不符合平稳性的，我们需要将其转为平稳的数据，最常用的方法就是差分。对于已经符合平稳性检验的时序数据，那就可以跳过差分直接寻找最合适的模型参数即可。

• 单位根检验
  • 单位根检验统计检验方法有ADF检验、PP检验、NP检验。最常用的是ADF检验。
  • ADF检验就是判断序列是否存在单位根：如果序列平稳，就不存在单位根；否则，就会存在单位根。
  • ADF检验的 H0 假设就是存在单位根，如果得到的显著性检验统计量小于三个置信度（10%，5%，1%），则对应有（90%，95，99%）的把握来拒绝原假设。
  • ADF值小于0.05，说明满足平稳性要求。

通过平稳性检验后，发现它不满足平稳性要求，那就要通过差分变换来转平。

差分变换

• 时间序列在t与t-1时刻的差值
• 差分 ：现在数列=现时刻数值-前一时刻数值
• 也就是本时刻与前一时刻的差值作为新的数列，可以让数列更加平稳

一阶差分，即一次差分完后，再进行平稳性检验，如还不满足平稳性要求，在一阶差分的基础上进行二阶差分，以此类推知道满足平稳性要求。

当满足平稳性要求后，我们就需要进行白噪声检验。

白噪声检验

​ 实际上就是纯随机性检验，比如通过Box-Pierce检验来判断我们的序列是否为白噪声：如果一个时间序列是纯随机的，得到一个观察期数为n的观察序列，那么该序列的延迟非零期的样本自相关系数将近似服从均值为0，方差为序列观察期数倒数的正态分布。

定阶

​ 通过平稳性、白噪声检验之后，我们就可以确定ARIMA模型的参数，即通过ACF和PACF确定。当肉眼观察ACF、PACF图时，多数情况下会有多组值满足几阶后的点都趋向于0。可以使用ACI、BIC，来求得使模型更好的参数。

建模预测

​ 在参数有了之后，我们就可以训练ARIMA模型进行预测了。

优缺点&使用场景

• 优点：模型简单，既可以只用内生变量，也可以融合外生变量。
• 缺点：要求时序数据是稳定的，或者通过差分化之后是稳定的；本质上只能捕捉线性关系，不能捕捉非线性关系。
• 对于足够历史数据且数据规律的情况下，可以尝试ARIMA进行回归拟合。

分享一篇好文章：https://ask.hellobi.com/blog/Tonysong2013/10964

隐马尔科夫

马尔科夫链

​ 马尔科夫链定义本身比较简单，它假设某一时刻状态转移的概率只依赖于它的前一个状态。举个形象的比喻，假如每天的天气是一个状态的话，那个今天是不是晴天只依赖于昨天的天气，而和前天的天气没有任何关系。当然这么说可能有些武断，但是这样做可以大大简化模型的复杂度，因此马尔科夫链在很多时间序列模型中得到广泛的应用，比如循环神经网络RNN，隐式马尔科夫模型HMM等。

​ 如果用精确的数学定义来描述，则假设我们的序列状态是：，那么我们在时刻的状态的条件概率仅仅依赖于时刻，即：

​ 既然某一时刻状态转移的概率只依赖于它的前一个状态，那么我们只要能求出系统中任意两个状态之间的转换概率，这个马尔科夫链的模型就定了。我们来看看下图这个马尔科夫链模型的具体的例子(来源于维基百科)。

隐马尔科夫(HMM)

什么样的问题需要HMM

首先我们来看看什么样的问题解决可以用HMM模型。使用HMM模型时我们的问题一般有这两个特征：

• １）我们的问题是基于序列的，比如时间序列，或者状态序列。

• ２）我们的问题中有两类数据，一类序列数据是可以观测到的，即观测序列；而另一类数据是不能观察到的，即隐藏状态序列，简称状态序列。

有了这两个特征，那么这个问题一般可以用HMM模型来尝试解决。这样的问题在实际生活中是很多的。比如：我现在在打字写博客，我在键盘上敲出来的一系列字符就是观测序列，而我实际想写的一段话就是隐藏序列，输入法的任务就是从敲入的一系列字符尽可能的猜测我要写的一段话，并把最可能的词语放在最前面让我选择，这就可以看做一个HMM模型了。再举一个，我在和你说话，我发出的一串连续的声音就是观测序列，而我实际要表达的一段话就是状态序列，你大脑的任务，就是从这一串连续的声音中判断出我最可能要表达的话的内容。

HMM模型的定义

对于HMM模型，首先我们假设是所有可能的隐藏状态的集合，是所有可能的观测状态的集合，即：

• 是可能的隐藏状态数
• 是所有可能的观察状态数

对于一个长度为的序列，是对应的状态序列，是对应的观察序列，即：

• 任意一个隐藏状态
• 任意一个观察状态

HMM模型做了两个很重要的假设：

1. 齐次马尔科夫链假设。即任意时刻的隐藏状态只依赖于它前一个隐藏状态。当然这样假设有点极端，因为很多时候我们的某一个隐藏状态不仅仅只依赖于前一个隐藏状态，可能是前两个或者前三个。但是这样假设的好处是模型简单，便于求解。如果在时刻的隐藏状态，在时刻的隐藏状态是，则从时刻到时刻的HMM状态转移概率可以表示为：

​ 这样可以组成马尔科夫链的状态转移矩阵A：

2. 观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态，这也是为了简化模型的假设。如果时刻的隐藏状态是而对应的观察状态为，则该时刻观察状态在隐藏状态下生成的概率为，满足：

这样可以组成观测状态生成的概率矩阵B：

​ 除此之外，我们需要一组在时刻的隐藏状态概率分布:

一个HMM模型，可以由隐藏状态初始概率分布，状态转移概率矩阵A，观测状态概率矩阵B决定。、A决定状态序列，B决定观测序列。因此HMM模型可以由一个三元组表示：

一个HMM模型实例

下面我们用一个简单的实例来描述上面抽象出的HMM模型。这是一个盒子与球的模型，例子来源于李航的《统计学习方法》。假设我们有3个盒子，每个盒子里都有红色和白色两种球，这三个盒子里球的数量分别是：

按照下面的方法从盒子里抽球，开始的时候，从第一个盒子抽球的概率是0.2，从第二个盒子抽球的概率是0.4，从第三个盒子抽球的概率是0.4。以这个概率抽一次球后，将球放回。然后从当前盒子转移到下一个盒子进行抽球。规则是：如果当前抽球的盒子是第一个盒子，则以0.5的概率仍然留在第一个盒子继续抽球，以0.2的概率去第二个盒子抽球，以0.3的概率去第三个盒子抽球。如果当前抽球的盒子是第二个盒子，则以0.5的概率仍然留在第二个盒子继续抽球，以0.3的概率去第一个盒子抽球，以0.2的概率去第三个盒子抽球。如果当前抽球的盒子是第三个盒子，则以0.5的概率仍然留在第三个盒子继续抽球，以0.2的概率去第一个盒子抽球，以0.3的概率去第二个盒子抽球。如此下去，直到重复三次，得到一个球的颜色的观测序列:

注意在这个过程中，观察者只能看到球的颜色序列，却不能看到球是从那个盒子里取出的。

那么我们按照上面HMM模型的定义，我们的观测集合是：

我们的状态集合是：

而观测序列和状态序列的长度为3

初始状态分布为：

状态转移概率分布矩阵为：

观测状态概率矩阵为：

从这个例子中，我们也可以抽象出HMM观测序列生成的过程。

• 输入的是：HMM模型 、观测序列长度
• 输出的是：观测序列
• 生成过程如下：
  • 根据状态概率分布生成隐藏状态
  • for t from 1 to T
    • 按照隐藏状态的观测状态分布生成观测状态
    • 按照隐藏状态的状态转移概率分布产生隐藏状态
  • 所有一起形成观测序列

HMM模型的三个基本问题

1. 评估观测序列的概率。

   即给定模型和观测序列，计算在模型下观测序列出现的概率。这个问题的求解需要用到前向后向算法。

   有关前向后向算法推荐文章：https://www.cnblogs.com/pinard/p/6955871.html

2. 模型参数学习问题。

   即给定观测序列，估计模型的参数，使该模型下观测序列的条件概率最大。这个问题的求解需要用到基于EM的鲍姆-韦尔奇算法。

   有关基于EM的鲍姆-韦尔奇算法推荐文章：https://www.cnblogs.com/pinard/p/6972299.html

3. 预测问题，也成解码问题。

   即给定模型和观测序列，求给定观测序列条件下，最可能出现的对应的状态序列。这个问题求解需要用到基于动态规划的维比特算法

   有关基于动态规划的维比特算法推荐：https://www.cnblogs.com/pinard/p/6991852.html

推荐复旦有关隐马尔科夫的白板推导：https://www.bilibili.com/video/BV1qC4y1H7RA?from=search&seid=8633811429380460161&spm_id_from=333.337.0.0

原创不易，转载请注明出处