理论知识 机器学习理论 V1

“对部分机器学习相关理论进行整理"

Posted by SunQH on September 2, 2021

机器学习理论

常问问题

线性回归

  • 原理

    • 给定n维特征的样本$x$,线性模型的形式为:$f(x)=wx+b$

      其中w为每个特征对应的权重生成的权重向量。

    • 线性模型的优点是:

      1. 模型简单
      2. 可解释性强,权重向量w直观的表达了各个特征在预测中的重要性。
    • 很多功能强大的非线性模型可以在线性模型的基础上通过引入层级结构或者非线性映射得到。

==逻辑回归(LR)==

考察点:把LR从头到脚都给讲一遍。建模,现场数学推导,每种解法的原理,正则化,LR和maxent模型啥关系,LR为啥比线性回归好。有不少会背答案的人,问逻辑细节就糊涂了。原理都会? 那就问工程,并行化怎么做,有几种并行化方式,读过哪些开源的实现。还会,那就准备收了吧,顺便逼问LR模型发展历史。

原理

  • 逻辑回归虽然名字叫做回归,但实际上却是一种分类学习方法
  • 逻辑回归本质上是线性回归,只是在特征到结果的映射中加入了一层逻辑函数g(z),即:
    1. 先把特征线性求和
    2. 然后使用函数g(z)作为假设函数来预测(使用sigmoid函数作为逻辑函数),将连续值映射到0 和1
    3. 这样输出的为一个概率值

cost function(极大似然函数)推导

img

如何做分类

逻辑回归作为一个回归函数,如何用于分类问题。 逻辑回归中,对于每个 x,其条件概率 y 的确是一个连续的变量。而逻辑回归中可以设定一个阈值,y 值大于这个阈值的是一类,y 值小于这个阈值的是另外一类。至于阈值的选择,通常是根据实际情况来确定,一般情况下选取 0.5 作为阈值来划分。

🚩为什么可以用似然函数做损失函数

因为目标是要让预测为正的的概率最大,且预测为负的概率也最大,即每一个样本预测都要得到最大的概率,将所有的样本预测后的概率进行相乘都最大,这就能到似然函数了。

求 $w$ 使得 $lnL(w)$ 最大,用梯度下降或者牛顿法求解都行。

🚩LR的cost function和梯度下降参数迭代公式

img

==LR参数求解的优化方法==

梯度下降法,随机梯度下降法,牛顿法,LBFGS,BFGS,OWLQN

极大似然函数无法直接求解,一般是通过对该函数进行梯度下降来不断逼近其最优解。这里需要注意的点是要对梯度下降有一定的了解,就梯度下降本身来看的话就有随机梯度下降,批梯度下降,small batch 梯度下降三种方式,面试官可能会问这三种方式的优劣以及如何选择最合适的梯度下降方式。

  • 批梯度下降会获得全局最优解,缺点是在更新每个参数的时候需要遍历所有的数据,计算量会很大,并且会有很多的冗余计算,导致的结果是当数据量大的时候,每个参数的更新都会很慢。
  • 随机梯度下降是以高方差频繁更新,优点是使得 sgd 会跳到新的和潜在更好的局部最优解,缺点是使得收敛到局部最优解的过程更加的复杂。
  • 小批量梯度下降结合了批梯度下降和随机梯度下降的优点,每次更新的时候使用 n 个样本。减少了参数更新的次数,可以达到更加稳定收敛结果,一般在深度学习当中我们采用这种方法。

LR和线性回归的区别

  1. 线性回归用来做预测, LR用来做分类。

  2. 线性回归的拟合函数本质上是对 输出变量 y 的拟合, 而==逻辑回归的拟合函数是对 label 为1的样本的概率的拟合。==

  3. [公式]

  4. 线性回归用最小二乘法来计算参数,LR用最大似然估计来计算参数。

  5. 🚩 ==线性回归更容易受到异常值的影响,而LR对异常值有较好的稳定性。==

LR 如何实现多分类?

  1. 方式1: 修改逻辑回归的损失函数,使用softmax函数构造模型解决多分类问题

    softmax分类模型会有相同于类别数的输出,输出的值为对于样本属于各个类别的概率,最后对于样本进行预测的类型为概率值最高的那个类别。

  2. 方式2根据每个类别都建立一个二分类器,本类别的样本标签定义为0,其它分类样本标签定义为1

    则有多少个类别就构造多少个逻辑回归分类器。

  3. 若所有类别之间有明显的互斥则使用softmax分类器,若所有类别不互斥有交叉的情况则构造相应类别个数的逻辑回归分类器。

逻辑回归为什么一般性能差?

LR是线性的,不能得到非线性关系,实际问题并不完全能用线性关系就能拟合。

如何用LR解决非线性问题?

将特征离散成高维的01特征可以解决分类模型的非线性问题

🚩 LR 为何要对特征进行离散化

  1. 引入非线性。 逻辑回归属于广义线性模型,表达能力受限;单变量离散化为N个后,每个变量有单独的权重,相当于为模型引入了非线性,能够提升模型表达能力,加大拟合; 离散特征的增加和减少都很容易,易于模型的快速迭代;

  2. 运算速度快。 稀疏向量内积乘法运算速度快,计算结果方便存储,容易扩展

  3. 增加鲁棒性。 离散化后的特征对异常数据有很强的鲁棒性:

比如一个特征是年龄>30是1,否则0。如果特征没有离散化,一个异常数据“年龄300岁”会给模型造成很大的干扰;

  1. 方便交叉与特征组合: 离散化后可以进行特征交叉,

由M+N个变量变为M*N个变量,进一步引入非线性,提升表达能力。

  1. 增加稳定性: 特征离散化后,模型会更稳定,

比如如果对用户年龄离散化,20-30作为一个区间,不会因为一个用户年龄长了一岁就变成一个完全不同的人。当然处于区间相邻处的样本会刚好相反,所以怎么划分区间是门学问。

  1. 简化模型,降低过拟合风险: 特征离散化以后,起到了简化了逻辑回归模型的作用,降低了模型过拟合的风险。

为什么逻辑回归比线性回归要好?

逻辑回归和线性回归首先都是广义的线性回归,但是:

  1. 经典线性模型的优化目标函数是最小二乘,而逻辑回归则是似然函数,

  2. 另外线性回归在整个实数域范围内进行预测,敏感度一致,而分类范围,需要在[0,1]。逻辑回归就是一种减小预测范围,将预测值限定为[0,1]间的一种回归模型,因而对于这类问题来说,逻辑回归的鲁棒性比线性回归的要好

逻辑回归与最大熵模型MaxEnt的关系?

逻辑回归跟最大熵模型没有本质区别。逻辑回归是最大熵对应类别为二类时的特殊情况,也就是当逻辑回归类别扩展到多类别时,就是最大熵模型

逻辑回归的优缺点

优点:

  • 形式简单,模型的可解释性非常好。从特征的权重可以看到不同的特征对最后结果的影响,某个特征的权重值比较高,那么这个特征最后对结果的影响会比较大。
  • 模型效果不错。在工程上是可以接受的(作为 baseline),如果特征工程做的好,效果不会太差,并且特征工程可以并行开发,大大加快开发的速度。
  • 训练速度较快。分类的时候,计算量仅仅只和特征的数目相关。并且逻辑回归的分布式优化 SGD 发展比较成熟。
  • 方便调整输出结果,通过调整阈值的方式。

缺点:

  • 准确率欠佳。因为形式非常的简单,而现实中的数据非常复杂,因此,很难达到很高的准确性。
  • 很难处理数据不平衡的问题。举个例子:如果我们对于一个正负样本非常不平衡的问题比如正负样本比 10000:1。我们把所有样本都预测为正也能使损失函数的值比较小。但是作为一个分类器,它对正负样本的区分能力不会很好。
  • 无法自动的进行特征筛选。
  • 只能处理二分类问题。

🚩工程上,怎么实现LR的并行化?有哪些并行化的工具

  • 逻辑回归的并行化最主要的就是对目标函数梯度计算的并行化
  • 算法的并行化有两种:
    1. 无损的并行化:
      1. 算法天然可以并行,并行只是提高了计算的速度和解决问题的规模,但和正常执行的结果是一样的。
      2. 基于Batch的算法(Batch-GD, LBFGS, OWLQN)都是可以进行无损的并行化的。
    2. 有损的并行化:
      1. 算法本身不是天然并行的,需要对算法做一些近似来实现并行化,这样并行化之后的双方和正常执行的结果并不一致,但是相似的。
      2. 基于SGD的算法(Ad Predictor, FTRL-Proximal)都只能进行有损的并行化。
  • 并行化的工具:
    • MPI
    • OpenMP

🚩LR和SVM的联系与区别?

  • 联系
    • LR和SVM都可以处理分类问题,且一般都用于处理线性二分类问题(在改进的情况下可以处理多分类问题)
    • 两个方法都可以增加不同的正则化项,如L1、L2等等。所以在很多实验中,两种算法的结果是很接近的。
  • 区别
    • LR是参数模型,SVM是非参数模型。
    • 从目标函数来看,区别在于逻辑回归采用的是Logistical Loss,SVM采用的是hinge loss.这两个损失函数的目的都是增加对分类影响较大的数据点的权重,减少与分类关系较小的数据点的权重。
    • SVM的处理方法是只考虑Support Vectors,也就是和分类最相关的少数点,去学习分类器。而逻辑回归通过非线性映射,大大减小了离分类平面较远的点的权重,相对提升了与分类最相关的数据点的权重。
    • 逻辑回归相对来说模型更简单,好理解,特别是大规模线性分类时比较方便。而SVM的理解和优化相对来说复杂一些,SVM转化为对偶问题后,分类只需要计算与少数几个支持向量的距离,这个在进行复杂核函数计算时优势很明显,能够大大简化模型和计算。
    • Logic 能做的 SVM能做,但可能在准确率上有问题,SVM能做的Logic有的做不了。

SVM

【机器学习】支持向量机 SVM(非常详细)

【机器学习】支持向量机 SVM(非常详细)

  • 原理: SVM,全称是support vector machine,中文名叫支持向量机。SVM是一个面向数据的分类算法,它的目标是为确定一个分类超平面,从而将不同的数据分隔开。

    • 支持向量机(support vector machines, SVM)是一种二分类模型,
    • 它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机;
    • SVM还包括核技巧,这使它成为实质上的非线性分类器。
    • SVM的的学习策略就是间隔最大化,可形式化为一个求解凸二次规划的问题,也等价于正则化的合页损失函数的最小化问题
    • SVM的的学习算法就是求解凸二次规划的最优化算法。
  • 最大间隔超平面。

    • 为了使这个超平面更具鲁棒性,我们会去找最佳超平面,以最大间隔把两类样本分开的超平面,也称之为最大间隔超平面。
  • 支持向量 img

    • 样本中距离超平面最近的一些点,这些点叫做支持向量。
  • SVM的核函数

    • 核函数的本质可以概括为如下三点:

      • 实际应用中,常常遇到线性不可分的情况。针对这种情况,常用做法是把样例特征映射到高维空间中,转化为线性可分问题

      • 将样例特征映射到高维空间,可能会遇到维度过高的问题。

      • 针对可能的维数灾难,可以利用核函数。核函数也是将特征从低维到高维的转换,但避免了直接进行高维空间中的复杂计算,可以在低维上进行计算,却能在实质上将分类效果表现在高维上。

        当然,SVM也能处理线性可分问题,这时使用的就是线性核了。

  • 常用的核函数包括如下几个

    • 线性核函数
    • 多项式核函数
    • RBF核函数(高斯核)
    • Sigmoid核函数
  • 松弛变量的理解

    1. 线性可分的理解
      1. 线性可分,即能找到超平面,对应硬间隔支持向量机
      2. 部分不可分,为近似线性可分问题,需要松弛变量,对应软间隔支持向量机
      3. 线性不可分,需要用到核函数
    2. 硬间隔支持向量机对噪声敏感,软间隔支持向量机要加个松弛变量ξ。我们都知道,硬间隔满足,yi * ( wi * x + b )≥1,这是函数间隔,是几何间隔的   w   倍。由于一些点出现在两条线的间隔内部,函数间隔的约束条件不满足,所以引入松弛变量ξ,使yi * ( wi * x + b ) + ξ ≥1,即:yi * ( wi * x + b ) ≥1 - ξ。对于这些离群点有对应的松弛变量,其他的点是没有松弛变量ξ的。

K最近邻(KNN)分类算法

  • 算法的过程:来了一个新的输入实例,我们算出该实例与每一个训练点的距离(这里的复杂度为0(n)比较大,所以引出了下文的kd树等结构),然后找到前k个,这k个哪个类别数最多,我们就判断新的输入实例就是哪类
    1. 计算测试数据与各个训练数据之间的距离;(耗时)
    2. 选取距离最小的K个点;
    3. 确定这K个点所在类别的出现频率
    4. 这K个点中出现频率最高的类别作为测试数据的预测分类
  • 距离函数:与该实例最近邻的k个实例,这个最近邻的定义是通过不同距离函数来定义,我们最常用的是欧式距离。
  • 归一化:为了保证每个特征同等重要性,我们这里对每个特征进行归一化
  • 参数选择:k值的选取,既不能太大,也不能太小,何值为最好,需要实验调整参数确定!
    • k取值的影响:
      • k小:模型复杂,容易过拟合
      • k大:模型简单,忽略数据中的有用信息
    • 如何确定k的取值
      • 那么我们一般怎么选取呢?李航博士书上讲到,我们一般选取一个较小的数值,通常采取 交叉验证法来选取最优的k值。
      • 也就是说,选取k值很重要的关键是实验调参,类似于神经网络选取多少层这种,通过调整超参数来得到一个较好的结果
  • 减少搜索时间-kd树:按照每个特征的维度的中位数建立kd树,之后根据预测样本的特征搜索,如果大于,则右枝;如果小于,则左枝。

k-means聚类算法(无监督)

  • 算法步骤:

    1. 随机选取k个点,作为聚类中心;
    2. 计算每个点分别到k个聚类中心的欧式距离,然后将该点分到最近的聚类中心,这样就行成了k个集合;
    3. 再重新计算每个集合的质心(各向量特征取均值)
    4. 重复以上2~4步,直到质心的位置不再发生变化或者达到设定的迭代次数。
  • 在k-means或kNN,为什么用欧氏距离来计算最近邻之间的距离而不用曼哈顿距离?

    • 曼哈顿距离只计算水平或垂直距离,有维度的限制

    • 另一方面,欧氏距离可用于任何空间的距离计算问题

      因为,数据点可以存在于任何空间,欧氏距离是更可行的选择。例如:想象一下国际象棋棋盘,象或车所做的移动是由曼哈顿距离计算的,因为它们是在各自的水平和垂直方向做的运动。

岭回归模型(Ridge)

  • 就是对于一个线性模型,在原来的损失函数加入参数的l2范数的惩罚项, 限制参数

决策树(DT)

决策树的生成过程就是使用满足划分准则的特征不断的将数据集划分为纯度更高,不确定性更小的子集 的过程。对于当前数据集D的每一次的划分,都希望根据某特征划分之后的各个子集的纯度更高,不确定性更小。

  • 决策树的类型
    • 分类树分析是指预测结果是数据所属的类(比如某个电影去看还是不看)
    • 回归树分析是指预测结果可以被认为是实数(例如房屋的价格,或患者在医院中的逗留时间)
    • 分类回归树(CART,Classification And Regression Tree)分析是用于指代上述两种树的总称
    • 分类的目标是根据已知样本的某些特征,判断一个新的样本属于哪种已知的样本类,它的结果是离散值。而回归的结果是连续的值。当然,本质是一样的,都是特征(feature)到结果/标签(label)之间的映射。
  • 特征选择准则
    • 用来度量划分前后的数据集的纯度及不确定性(量化分类效果)
    • 比如:信息增益,信息增益率,基尼指数

信息增益( ID3算法 )

  • 核心思想:以信息增益度量属性选择,选择分裂后信息增益最大的属性进行分裂。
  • 定义: 以某特征划分数据集前后的熵的差值
  • 公式: 划分前集合熵 - 划分后集合熵image-20210801183450773

在熵的理解那部分提到了,熵可以表示样本集合的不确定性,熵越大,样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏

做法:计算使用所有特征划分数据集D,得到多个特征划分数据集D的信息增益,从这些信息增益中选 择最大的,因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。

熵的理解:为了精确地定义信息增益,我们先定义信息论中广泛使用的一个度量标准称为熵(entropy)

  • 它刻画了任意样例集的纯度(purity)。

  • 给定包含关于某个目标概念的正反样例的样例集S,那么S相对这个布尔型分类的熵为:

    image-20210109214727229

    image-20210109224025591

    其中,p+为正样本概率,p-为负样本概率。

  • 缺点:信息增益偏向取值较多的特征
    • 原因:当特征的取值较多时,根据此特征划分更容易得到纯度更高的子集,因此划分之后的熵更低,由于划分前的熵是一定的,因此信息增益更大,因此信息增益比较偏向取值较多的特征。
    • 解决方法 : 信息增益比( C4.5算法 )

信息增益比( C4.5算法 )

  • 本质: 是在信息增益的基础之上乘上一个惩罚参数。

  • 公式:信息增益比 = 惩罚参数 * 信息增益image-20210801184028880

  • 特征个数较多时,惩罚参数较小;特征个数较少时,惩罚参数较大。

  • 缺点:信息增益比偏向取值较少的特征

  • 原因: 当特征取值较少时HA(D)的值较小,因此其倒数较大,因而信息增益比较大。因而偏向取值较少 的特征。

  • 信息增益比的使用:基于以上缺点,并不是直接选择信息增益率最大的特征,而是

    1. 先在候选特征中找出信 息增益高于平均水平的特征,
    2. 然后在这些特征中再选择信息增益率最高的特征。

基尼指数( CART算法 -分类树)

定义:基尼指数(基尼不纯度):表示在样本集合中一个随机选中的样本被分错的概率

公式:基尼指数(基尼不纯度)= 样本被选中的概率 * 样本被分错的概率

image-20210801213355246

注意: Gini指数越小表示集合中被选中的样本被分错的概率越小,也就是说集合的纯度越高,反之,集合越不纯。

  1. 🚩 pk表示选中的样本属于k类别的概率,则这个样本被分错的概率是(1-pk)
  2. 样本集合中有K个类别,一个随机选中的样本可以属于这k个类别中的任意一个,因而对类别就加和
  3. 当为二分类是,Gini(P) = 2p(1-p)

集成学习

  • 原理:
    • 集成学习是指用某种策略将多个分类器预测的结果集成起来,作为最终的预测结
    • 主要有2种形式:boosting和bagging。
  • Boosting方法
    • 基本思想
      • 串行,分类器互相依赖
      • 训练时,将基分类器层层叠加,每一层训练时对前一层错分样本给予更高的权重,分类错误率低的基分类器给予更高的权重
      • 测试时,根据各层分类器的结果加权得到最终结果。
    • 主要作用
      • 减少集成分类器的偏差(基分类器层层叠加)

Boosting方法的例子

  • AdaBoost(自适应增强)
    • 基本思想
      • 前一个分类器分错/分对的样本的权值会得到加强/降低,加权后的全体样本再次被用来训练下一个基本分类器
  • GBDT(梯度提升决策树)
    • 基本思想

      • GBDT的每一次计算都为了减少上一次的残差,进而在负梯度的方向上建立一个新的模型
      • 根据当前模型损失函数的负梯度信息来训练新加入的弱分类器,然后把训练好的弱分类器以累加的形式结合到现有模型里
  • XGBoost

    • 目标函数

      • 目标函数分为两个部分:误差函数(logistic损失函数、平方损失函数)和正则化项(定义模型的复杂度)
      • 将目标函数化简之后,目标函数只依赖于一阶导数g和二阶导数h
      • 将目标函数和正则化项结合化简,对w进行求导,求出最优w,代入目标函数中

bagging方法

  • 基本思想
    • 可并行,分类器无依赖
    • 将训练集分为若干子集,分别训练各个基分类器
    • 测试时,每个基分类器单独做出判断,通过投票方式做出最终决策
  • 作用
    • 减少集成分类器的方差(基分类器并行,根据统计学)

bagging方法的例子

  • 随机森林 https://zhuanlan.zhihu.com/p/91395504

GBDT

  • 梯度提升决策树,使用CART回归树作为基学习器,是一种boosting算法,用于分类或者回归问题。GBDT通过不断学习前一个基学习器的残差做优化,最终得到结果。

RF和GBDT

  • 随机森林, 使用决策树作为基学习器,是一种bagging算法,用于分类或者回归问题。RF通过各个基生成器投票或取平均的方式得到结果基模型其实就是ID3、C4.5、CART这几种决策树。
  • 梯度提升决策树,使用CART回归树作为基学习器,是一种boosting算法,用于分类或者回归问题。GBDT通过不断学习前一个基学习器的残差做优化,最终得到结果。
  1. 首先gbdt 是通过采用加法模型(即基函数的线性组合),以及不断减小训练过程产生的残差来达到将数据分类或者回归的算法。
  2. gbdt通过多轮迭代, 每轮迭代产生一个弱分类器,每个分类器在上一轮分类器的梯度(如果损失函数是平方损失函数,则梯度就是残差值)基础上进行训练。
  3. 🚩 对弱分类器的要求一般是足够简单,并且是低方差和高偏差的。因为训练的过程是通过降低偏差来不断提高最终分类器的精度(此处是可以证明的)。
  4. 弱分类器一般会选择为==CART TREE==(也就是分类回归树)。
  5. 由于上述高偏差和简单的要求,每个分类回归树的深度不会很深。最终的总分类器是将每轮训练得到的弱分类器加权求和得到的(也就是加法模型)。
  • 处理缺失值

    • RF:

      1. 对应类别的中位数代替

        快速简单但是效果差:

      2. 引入权重,先做相似度预测,相似度高的权重大

        费时费力但效果好:

    • 🚩GBDT

      • 构建CART树时通过 特征中无缺失值数据比例*这些数据的的信息增益 选取特征分裂节点。
  • 特征重要性判断

    • RF

      1. 通过Gini系数的减少量,越大越重要
      2. 🚩对于一个树,先使用OOB(Out of bag)样本计算测试误差a,再随机打乱OOB样本中第i个特征 (上下打乱特征矩阵第i列的顺序)后计算测试误差b,a与b差距越大特征i越重要。
    • GBDT:

      计算 所有回归决策树中通过特征i分裂后平方损失或基尼指数的减少值的和 / 回归树数量 得到特征重 要性。

  • 异同点

    • 相同点
      • 都是多棵树
      • 都由多棵树决定结果
    • 不同点
      • RF为bagging思想,又放回的采样数据;GBDT为boosting思想
      • RF不限制书深度、不剪枝;GBDT需要限制书的深度(容易过拟合)
      • RF可以并行;GBDT为串行
      • RF为多数投票法,方差小;GBDT将结果累加,或者加权累加,偏差小
      • RF对异常值不敏感;GBDT敏感

RF和GBDT的区别?

相同点

  • 都是由多棵树组成,最终的结果都是由多棵树一起决定。

不同点

  • 集成学习:RF属于bagging思想,而GBDT是boosting思想
  • 偏差-方差权衡:RF不断的降低模型的方差,而GBDT不断的降低模型的偏差
  • 训练样本:RF每次迭代的样本是从全部训练集中有放回抽样形成的,而GBDT每次使用全部样本
  • 并行性:RF的树可以并行生成,而GBDT只能串行顺序生成(需要等上一棵树完全生成)
  • 最终结果:RF最终是多棵树进行多数表决(回归问题是取平均),方差小;而GBDT是将所有结果累加或者加权累加,偏差小
  • 数据敏感性:RF对异常值不敏感,而GBDT对异常值比较敏感
  • 泛化能力:RF不易过拟合(有放回的采样数据,而且可以对特征列采样,不用全部特征),而GBDT容易过拟合
  • RF不需要限制树的深度,不用剪枝;GBDT为了防止过拟合,需要限制树深

比较LR和GBDT

先说说LR和GBDT的区别

  • LR是线性模型,可解释性强,很容易并行化,但学习能力有限,需要大量的人工特征工程
  • GBDT是非线性模型,具有天然的特征组合优势,特征表达能力强,但是树与树之间无法并行训练,而且树模型很容易过拟合;

说说什么情景下GBDT不如LR?

当在高维稀疏特征的场景下,LR的效果一般会比GBDT好

原因如下:

先看一个例子: 假设一个二分类问题,label为0和1,特征有100维,如果有1w个样本,但其中只要10个正样本1,而这些样本的特征 f1的值全为1,而其余9990条样本的f1特征都为0(在高维稀疏的情况下这种情况很常见)。

我们都知道在这种情况下,树模型很容易优化出一个使用fyu’yuya’s’d’f’j’ka特征作为重要分裂节点的树,因为这个结点直接能够将训练数据划分的很好,但是当测试的时候,却会发现效果很差,因为这个特征f1只是刚好偶然间跟y拟合到了这个规律,这也是我们常说的过拟合。

那么这种情况下,如果采用LR的话,应该也会出现类似过拟合的情况呀:y = W1 x f1 + Wi x fi+….,其中 W1特别大以拟合这10个样本。为什么此时树模型就过拟合的更严重呢?

仔细想想发现,因为现在的模型普遍都会带着正则项,而 LR 等线性模型的正则项是对权重的惩罚,也就是 W1一旦过大,惩罚就会很大,进一步压缩 W1的值,使他不至于过大。但是,树模型则不一样,树模型的惩罚项通常为叶子节点数和深度等,而我们都知道,对于上面这种 case,树只需要一个节点就可以完美分割9990和10个样本,一个结点,最终产生的惩罚项极其之小

这也就是为什么在高维稀疏特征的时候,线性模型会比非线性模型好的原因了:带正则化的线性模型比较不容易对稀疏特征过拟合。

XGBoost

简单介绍一下XGBoost。

  • 基本原理

    • 首先需要说一说GBDT,它是一种基于boosting增强策略的加法模型,训练的时候采用前向分布算法进行贪婪的学习,每次迭代都学习一棵CART树来拟合之前 t-1 棵树的预测结果与训练样本真实值的残差(使用损失函数的负梯度来近似模拟残差)。

    • XGBoost对GBDT进行了一系列优化,如果不考虑工程实现、解决问题上的一些差异,xgboost与gbdt比较大的不同就是目标函数的定义: 比如损失函数进行了二阶泰勒展开、目标函数加入正则项、支持并行和默认缺失值处理(稀疏感知法)等,在可扩展性训练速度上有了巨大的提升,但其核心思想没有大的变化

      image-202108040001531951. 相比GBDT,XGBoost添加了正则项,对每颗树的复杂度进行了惩罚,包括叶子节点个数和叶节点权重: image-20210804000410508

      1. 对目标函数进行了二阶泰勒展开,得到节点分裂增益公式:

      image-20210804002204563

  • 主要过程是:一层一层的完成建树过程, xgboost训练的时候,是通过加法的方式进行训练,也就是每一次通过聚焦残差训练一棵树出来, 最后的预测结果是所有树的加和表示

    1. 在训练过程中是聚焦残差
    2. 在目标函数中使用了二阶泰勒展开并加入了正则
    3. 在决策树的生成过程中采用了精确贪心的思路,
    4. 寻找最佳分裂点的时候,使用了预排序算法

    对所有特征都按照特征的数值进行预排序, 然后遍历所有特征上的所有分裂点位,计算按照这些候选分裂点位分裂后 的全部样本的目标函数增益,找到最大的那个增益对应的特征和候选分裂点位,从而进行分裂。

  • xgboost优化

    1. 预排序:对特征进行预排序,并以column block的结构保存在内存中,按照特征的由小到大保存 样本的索引(索引指向内存中的具体数据)。这种结构只需要在构建树之前先排序一次,之后节点分裂就可以直接根据索引得到梯度信息。
    2. Cache优化:预排序在索引层面上特征值是有序的,但在内存中还是不连续的,会造成内存的不 连续访问,降低Cache命中。故对其优化:为每个线程分配一个连续的缓存区,将需要的梯度信息 存放在缓冲区中,这样就是实现了非连续空间到连续空间的转换,提高了算法效率,解决缓存命中 率低的问题
  • xgboost缺点

    1. 虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量,但在节点分裂过程中仍需要遍历数据集

    2. 预排序过程的空间复杂度过高,不仅需要存储特征值,还需要存储特征对应样本的梯度统计值的索引,相当于消耗了两倍的内存。

XGBoost与GBDT的不同?

XGBoost类似于GBDT的优化版,不论是精度还是效率上都有了提升。都是聚焦残差,不过与GBDT相比,具体的优点有:

  • 基分类器:XGBoost的基分类器不仅支持CART决策树,还支持线性分类器,此时XGBoost相当于带L1和L2正则化项的Logistic回归(分类问题)或者线性回归(回归问题)。而GBDT仅支持CART树作为基学习器。

    🚩 节点分裂的方式不同,GBDT是用的基尼系数,XGBoost是经过优化推导后的。

  • 损失函数:XGBoost对损失函数做了二阶泰勒展开,用二阶梯度可以更好地拟合损失下降的曲线。并且XGBoost还支持自定义损失函数(可以是最小平方差、logistic loss function、hinge loss function或者人为定义的loss function),只要损失函数一阶、二阶可导便可进行boosting,其进一步增大了模型的泛化能力; GBDT旨在通过不断加入新的树最快速度降低残差,只用了一阶导数信息

  • 正则项:XGBoost的损失函数(目标函数)加了正则项,对叶子节点个数叶子结点的权重分别进行L1、L2正则化, 相当于预剪枝,使得学习出来的模型更加不容易过拟合。

  • 列抽样:XGBoost支持列采样,与随机森林类似,不仅可以减少计算,还可以用于防止过拟合,而GBDT使用全部特征。

  • 缺失值处理:对树中的每个非叶子结点,XGBoost可以自动学习出它的默认分裂方向。如果某个样本该特征值缺失,会将其划入默认分支。

  • 并行化:注意不是tree维度的并行,而是特征维度的并行。XGBoost预先将每个特征按特征值排好序,存储为块结构,(按特征值由小到大排序,不仅要存储样本的特征值,还需要保存样本的索引,索引指向内存中的具体数据,即样本的一阶、二阶梯度信息),分裂结点时,根据索引可以得到相应的梯度信息(一阶、二阶),可以采用多线程并行查找每个特征的最佳分割点,极大提升训练速度。

  • 收缩率:XGBoost加入了收缩率系数,在每次迭代完决策树fi后将叶子节点的权重乘上该系数,来削弱每棵树的影响,让后面的树有更大的学习空间。实际应用中,一般把eta设置为较小的数,把迭代次数设置为较大值。

XGBoost的优点

  1. 精度高:GBDT 只用到一阶泰勒展开,而 XGBoost 对损失函数进行了二阶泰勒展开。引入二阶导一方面是为了增加精度,另一方面也是为了能够自定义损失函数。
  2. 灵活性更强:传统GBDT以CART作为基分类器,xgboost还支持线性分类器,这时xgboost相当于带L1和L2正则化项的逻辑斯蒂回归(分类问题)或者线性回归(回归问题)。
  3. 正则化:在目标函数中加入了正则项,用于控制模型的复杂度。正则项里包含了树的叶子节点个数、叶子节点权重的 L2 范式。正则项降低了模型的方差,使学习出来的模型更加简单,有助于防止过拟合。
  4. Shrinkage:相当于学习速率。XGBoost 在进行完一次迭代后,会将叶子节点的权重乘上该系数,主要是为了削弱每棵树的影响,让后面有更大的学习空间
  5. 列抽样:借鉴了随机森林的做法,支持列抽样,不仅能降低过拟合,还能减少计算;
  6. 缺失值处理:对于特征的值有缺失的样本,xgboost可以自动学习出它的分裂方向。
  7. 可以并行化操作:块结构可以很好的支持并行计算。
  8. 可并行的近似直方图算法:树节点在进行分裂时,我们需要计算每个特征的每个分割点对应的增益,即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下,贪心算法效率就会变得很低,所以xgboost还提出了一种可并行的近似直方图算法,用于高效地生成候选的分割点。
  9. 相当于预剪枝:当增益大于阈值时才让节点分裂,上式中的gamma即阈值,它是正则项里叶子节点数T的系数,所以xgboost在优化目标函数的同时相当于做了预剪枝。

XGBoost的缺点

  1. 节点分类需要遍历数据集:虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量,但在节点分裂过程中仍需要遍历数据集;
  2. 预排序空间复杂度高:预排序过程的空间复杂度过高,不仅需要存储特征值,还需要存储特征对应样本的梯度统计值的索引,相当于消耗了两倍的内存。
  3. 找到特别精确的分割点,可能存在过拟合。

为什么使用泰勒二阶展开?

  • 精准性:相对于GBDT的一阶泰勒展开,XGBoost采用二阶泰勒展开,可以更为精准的逼近真实的损失函数。对损失函数应用泰勒二阶展开可以得到节点的分裂增益公式,为后面选取最佳变量的最佳分割点,提供增益指标。
  • 可扩展性:损失函数支持自定义,只需要新的损失函数二阶可导。这种去耦合增加了XGBoost的适用性。

为什么可以并行训练?

  • XGBoost的并行,并不是说每棵树可以并行训练,XGB本质上仍然采用boosting思想,每棵树训练前需要等前面的树训练完成才能开始训练。
  • XGBoost的并行,指的是特征维度的并行:在训练之前,对每个特征按特征值有小到大对样本进行预排序,(不仅要存储样本的特征值,还需要保存样本的索引,索引指向内存中的具体数据,即样本的一阶、二阶梯度信息)并存储为Block结构,在后面查找特征分割点时可以重复使用,而且特征已经被存储为一个个block结构,那么在寻找每个特征的最佳分割点时,可以利用多线程对每个block并行计算。

为什么快?

  • 分块并行:训练前每个特征按特征值进行排序并存储为Block结构,后面查找特征分割点时重复使用,并且支持并行查找每个特征的分割点。
  • 候选分位点:每个特征采用常数个分位点作为候选分割点,在找最佳分裂点的时候,只需要在候选分割点中做选择,不用遍历所有可能的分裂位置。(全局扫描法将所有特征的特征按照从小到大排序,将所有可能的分裂位置都遍历一遍,找到其中增益最大的那个分裂点,其计算复杂度和叶子节点上样本的特征取值个数成正比。)
  • CPU cache(高速缓冲存储器) 命中优化: 使用缓存预取的方法,为每个线程分配一个连续的buffer(缓存区),读取每个block中样本的梯度信息并存入连续的Buffer中。(预排序在索引层面上特征值是有序的,但是在内存中还是不连续的,会造成内存的不连续访问,降低cache命中。故对其优化:为每个线程分配一个连续的缓存区,将需要的样本梯度信息存放到缓存区中,这样就实现了非连续空间到连续空间的转换,提高了算法效率,解决缓存命中率低的问题。)
  • Block 处理优化:Block预先放入内存;Block按列进行解压缩;将Block划分到不同硬盘来提高吞吐。

防止过拟合的方法?

XGBoost在设计时,为了防止过拟合做了很多优化,具体如下:

  • 目标函数添加正则项:叶子节点个数L1正则化+叶子节点权重的L2正则化。
  • 列抽样:训练的时候只用一部分特征(不考虑剩余的block块即可)。
  • 子采样:每轮计算可以不使用全部样本,使算法更加保守。
  • shrinkage: 得到决策树后,将叶子节点权重乘上收缩系数(可以叫学习率或步长),削弱每棵树的影响,为了给后面的训练留出更多的学习空间。

如何处理缺失值?

XGBoost模型的一个优点就是允许特征存在缺失值。对缺失值的处理方式如下:(稀疏感知算法)

  • 训练时,根据叶子结点分裂增益公式,将该特征值missing的样本分别分配到左叶子结点和右叶子结点,两种情形都计算一遍后,选择放到分裂后增益最大的那个方向(左分支或是右分支),作为预测时特征值缺失样本的默认分支方向(右子节点)。
  • 如果在训练中没有缺失值而在预测中出现缺失,那么会自动将缺失值的划分方向放到右子结点

🚩叶子结点的权重计算?

XGBoost目标函数最终推导形式如下:

图片

利用一元二次函数求最值的知识,当目标函数达到最小值Obj星时,每个叶子结点的权重为wj*。

具体公式如下:

图片

Gj代表在叶子节点j上,所有样本的一阶导数值之和;Hj代表在叶子节点j上,所有样本的二阶导数值之和。最终的obj叫做结构分数,结构分数越小,代表生成的树的结构就越好(让残差尽可能的小)。

一棵树的停止生长条件?

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

如何处理不平衡数据?

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

  • 第一种,如果你在意预测的排名顺序(AUC),采用AUC来评估模型的性能,那你可以通过设置scale_pos_weight(设置正样本的权重)来平衡正样本和负样本的权重。例如,当正负样本比例为1:10时,scale_pos_weight可以取10;
  • 第二种,如果你在意预测正确的概率,你不能重新平衡数据集(会破坏数据的真实分布),应该设置max_delta_step为一个有限数字来帮助收敛(基模型为LR时有效)。
  • 除此之外,还可以通过上采样、下采样、SMOTE算法或者自定义代价函数的方式解决正负样本不平衡的问题

如何对树进行剪枝?

  • ①在目标函数中增加了正则项:使用叶子结点的数目和叶子结点权重的L2模的平方,控制树的复杂度。
  • ②在结点分裂时,定义了一个阈值,如果分裂后目标函数的增益(分裂增益)小于该阈值,则不分裂。
  • ③当引入一次分裂后,重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值(最小样本权重和),也会放弃此次分裂。
  • XGBoost 先从顶到底建立树直到最大深度,再从底到顶反向检查是否有不满足分裂条件的结点,进行剪枝。

如何选择最佳分裂点?

  • 分裂策略
    • xgboost采用二叉树,开始的时候,全部样本都在一个叶子节点上。然后叶子节点不断通过二分裂,逐 渐生成一棵树。 xgboost使用levelwise的生成策略,即每次对同一层级的全部叶子节点尝试进行分裂。 对叶子节点分裂生成树的过程有几个基本的问题:是否要进行分裂?选择哪个特征进行分裂?在特征的 什么点位进行分裂?以及分裂后新的叶子上取什么值?
    • 是否要进行分裂?
      • xgboost采用预剪枝策略,只有分裂后的增益大于0才会进行分裂
    • 选择什么特征进行分裂?
      • xgboost采用特征并行的方法进行计算选择要分裂的特征,即用多个线程,尝试把各个特征都作为分裂 的特征,找到各个特征的最优分割点,计算根据它们分裂后产生的增益,选择增益最大的那个特征作为 分裂的特征。
    • 选择什么分裂点位?
      • xgboost选择某个特征的分裂点位的方法有两种,一种是全局扫描法,另一种是候选分位点法。 全局扫描法将所有样本该特征的取值按从小到大排列,将所有可能的分裂位置都试一遍,找到其中增益最大的那个分裂点,其计算复杂度和叶子节点上的样本特征不同的取值个数成正比。 而候选分位点法是一种近似算法,仅选择常数个(如256个)候选分裂位置,然后从候选分裂位置中找 出最优的那个。 分裂点的提出:加权分位数算法

XGBoost在训练前预先将特征按照特征值进行了排序,并存储为block结构,以后在结点分裂时可以重复使用该结构。

选择最佳分裂点的方法有两种:全局扫描法和加权分位数算法。

全局扫描法:可以采用特征并行的方法利用多个线程分别计算每个特征的最佳分割点(对每个特征的每个可能的分割点都计算其分裂增益),根据每次分裂后产生的增益,最终选择增益最大的那个特征的特征值作为最佳分裂点。

加权分位数算法:如果在计算每个特征的最佳分割点时,对每个样本都进行遍历,计算复杂度会很大,这种全局扫描的方法并不适用大数据和样本特征的取值较多的场景。XGBoost还提供了一种加权分位数算法(直方图近似算法),对特征排序后仅选择常数个候选分裂位置作为候选分裂点,选择最佳分裂点时,仅仅需要在候选分裂点中进行选择,极大提升了结点分裂时的计算效率。

(相当于对分裂点进行了分桶,尽量让左右子树的loss分布均匀(利用二阶导数值hi根据每一个样本对拟合残差的贡献程度进行加权),这样先选出了候选分割点,我们只需要保存每个桶中样本的一阶导数值的和、二阶导数值的和,然后对于每个候选分割点,计算分裂增益时,只需要将分割点左边的桶的值进行求和与右边的桶的值求和进行比较即可。因为桶的个数肯定小于样本的数量,所以得以加速)

可扩展性如何体现?

  • 基分类器的scalability:弱分类器可以支持CART决策树,也可以支持LR和Linear(线性分类器)。
  • 目标函数的scalability:支持自定义loss function,只需要其一阶、二阶可导。有这个特性是因为泰勒二阶展开,得到通用的目标函数形式。

  • 学习方法的scalability:Block结构支持并行化,支持 Out-of-core计算。

如何评价特征的重要性?

  • weight :该特征在所有树中被用作分割样本的特征的总次数。
  • gain :该特征在其出现过的所有树中产生的平均增益。
  • cover :该特征在其出现过的所有树中的平均覆盖范围。

gain: 计算使用 特征i分裂节点的分裂增益之和/所有特征分裂节点的分裂增益之和 ,得到重要性。

注意:覆盖范围这里指的是一个特征用作分割点后,其影响的样本数量,即有多少样本经过该特征分割到两个子节点。

为什么对缺失值不敏感?

对存在缺失值的特征,一般的解决方法是:

  • 离散型变量:用出现次数最多的特征值填充;
  • 连续型变量:用中位数或均值填充;

一些模型如SVM和KNN,其模型原理中涉及到了对样本距离的度量,如果缺失值处理不当,最终会导致模型预测效果很差。

而树模型对缺失值的敏感度低,大部分时候可以在数据缺失时时使用。原因就是,一棵树中每个结点在分裂时,寻找的是某个特征的最佳分裂点(特征值),完全可以不考虑存在特征值缺失的样本,也就是说,如果某些样本缺失的特征值缺失,对寻找最佳分割点的影响不是很大。

XGBoost对缺失数据有特定的处理方法:训练时,根据叶子结点分裂增益公式,将该特征值missing的样本分别分配到左叶子结点和右叶子结点,两种情形都计算一遍后,选择放到分裂后增益最大的那个方向(左分支或是右分支),作为预测时特征值缺失样本的默认分支方向(右子节点)。

因此,对于有缺失值的数据在经过缺失处理后:

  • 当数据量很小时,优先用朴素贝叶斯
  • 数据量适中或者较大,用树模型,优先XGBoost
  • 数据量较大,也可以用神经网络
  • 避免使用距离度量相关的模型,如KNN和SVM

参数调优的一般步骤?

首先需要初始化一些基本变量,例如:

  • learning_rate = 0.1
  • max_depth = 5
  • min_child_weight = 1
  • gamma = 0
  • subsample = 0.8
  • colsample_bytree = 0.8
  • scale_pos_weight = 1

learning_rate:学习率(收缩系数)

n_estimators:树的个数 一般会设置early_stopping_rounds=200,如果新增加200棵树都不降低损失,那么就停止建树, verbose=50,每50次输出一次结果。

max_depth:构建树的深度,越大越容易过拟合;

min_child_weight:孩子节点中最小的样本权重和。当引入一次分裂后,重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值,会放弃此次分裂。这涉及到一个超参数:最小样本权重和,是指如果一个叶子节点包含的样本数量太少也会放弃分裂,防止树分的太细。

gamma:损失下降多少才进行分裂(控制叶子节点的个数,分裂后节点就增加了),也称作最小划分损失min_split_loss,只有当划分后的损失函数损失下降值大于此阈值,当前叶子节点才继续划分。

subsample:对训练样本的随机采样比例

colsample_bytree:对特征的采样比例

scale_pos_weight:正样本在数据集中占得权重(可以解决正负样本比例不均衡的问题)

alpha :L1正则化系数,try 1e-5, 1e-2, 0.1, 1, 100

lambda :L2正则化系数

(1) 确定learning rate和estimator的数量

learning rate可以先用0.1,用cv来寻找最优的estimators

(2) max_depth和 min_child_weight

我们调整这两个参数是因为,这两个参数对输出结果的影响很大。我们首先将这两个参数设置为较大的数,然后通过迭代的方式不断修正,缩小范围。

max_depth,每棵子树的最大深度,check from range(3,10,2)。

min_child_weight,子节点的权重阈值,check from range(1,6,2)。

如果一个结点分裂后,它的所有子节点的权重之和都大于该阈值,该叶子节点才可以划分。

(3) gamma

也称作最小划分损失min_split_loss,check from 0.1 to 0.5,指的是,对于一个叶子节点,当对它采取划分之后,损失函数的降低值的阈值。

  • 如果大于该阈值,则该叶子节点值得继续划分
  • 如果小于该阈值,则该叶子节点不值得继续划分

(4) subsample, colsample_bytree

subsample是对训练的采样比例

colsample_bytree是对特征的采样比例

both check from 0.6 to 0.9

(5) 正则化参数

alpha 是L1正则化系数,try 1e-5, 1e-2, 0.1, 1, 100

lambda 是L2正则化系数

(6) 降低学习率

降低学习率的同时增加树的数量,通常最后设置学习率为0.01~0.1

如果过拟合了怎么解决?

当出现过拟合时,有两类参数可以缓解:

第一类参数:用于直接控制模型的复杂度。包括max_depth,min_child_weight,gamma 等参数(即控制树的深度和叶子节点的个数);

第二类参数:用于增加随机性,从而使得模型在训练时对于噪音不敏感。包括subsample,colsample_bytree(即对样本集采样、对特征采样);

还有就是直接减小learning rate,但需要同时增加estimator 参数。(即减小收缩系数,让叶子节点的权重更小,让后面的树有更大的学习空间)。

XGBoost和LightGBM的区别?

图片

(1)树生长策略:XGB采用level-wise的分裂策略,LGB采用leaf-wise的分裂策略。XGB对每一层所有节点做无差别分裂,(该策略遍历一次数据可以同时分裂同一层的叶子,容易进行多线程优化,也好控制模型的复杂度,不容易过拟合)但是可能有些节点增益非常小,对结果影响不大,带来不必要的开销(一层一层的走,不管它效果好不好)。Leaf-wise是在所有叶子节点中选取分裂收益最大的节点进行的,(该策略可以降低更多的误差,得到更好的精度),但是很容易出现过拟合问题,所以需要对最大深度做限制 。

(2)分割点查找算法:XGB使用特征预排序算法,LGB使用基于直方图的切分点算法,其优势如下:

(XGB寻找最优分裂点的复杂度=特征数量 X 分裂节点数量 X 样本的数量,LGB分别从这三个方面进行了优化)

  • 减少内存占用,比如离散为256个bin时,只需要用8位整形就可以保存一个样本被映射为哪个bin(这个bin可以说就是转换后的特征),对比预排序的exact greedy(精准贪婪算法)算法来说(用int_32来存储索引+ 用float_32保存特征值),可以节省7/8的空间。(64-8)/64=7/8。(XGB需要保存特征值和样本索引值(指向样本的梯度信息),而LGB只需要保存每一个离散值对应的梯度累加和即可。)
  • 计算效率提高,预排序的Exact greedy(贪婪算法(全局扫描法))对每个特征都需要遍历一遍数据,并计算增益,复杂度为𝑂(#𝑓𝑒𝑎𝑡𝑢𝑟𝑒×#𝑑𝑎𝑡𝑎)。而直方图算法在建立完直方图后,只需要对每个特征遍历直方图即可,复杂度为𝑂(#𝑓𝑒𝑎𝑡𝑢𝑟𝑒×#𝑏𝑖𝑛𝑠)。
  • LGB还可以使用直方图做差加速,一个节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到,从而加速计算

但实际上xgboost的近似直方图算法(加权分位数算法)也类似于lightgbm这里的直方图算法,为什么xgboost的近似算法比lightgbm还是慢很多呢?

xgboost在每一层都动态构建直方图, 因为xgboost的直方图算法不是针对某个特定的feature,而是所有feature共享一个直方图(每个样本的权重是二阶导),所以每一层都要重新构建直方图,而lightgbm中对每个特征都有一个直方图,所以构建一次直方图就够了。(XGB在每一层的分裂过程中,都需要对所有的特征重新选择候选分割点(即重新构建直方图),因为XGB在选取候选分割点的时候,考虑的是想让loss在左右子树上分布均匀,(二阶导数代表样本对降低loss的贡献程度,所以可以根据二阶导数值累加来选取候选分割点),每次分裂之后,节点中的样本数量发生变化,每个节点的二阶导数和也是变化的,所以需要重新构建直方图。)

  • LGB还使用了单边梯度采样算法GOSS来减少样本的个数和互斥特征捆绑算法EFB来减少特征的个数。

(3)支持离散变量:XGB无法直接输入类别型变量,因此需要事先对类别型变量进行编码(例如独热编码),而LightGBM可以直接处理类别型变量(采用many-vs-many的切分方式,将类别特征分为两个子集,实现类别特征的最优切分。基本思想为每次分组时,都会根据训练目标对类别特征进行分类:在枚举分割点之前,先把直方图按照每个类别对应的label均值进行排序,然后按照排序的结果依次枚举最优分割点)。

(4)缓存命中率:XGB使用Block结构的一个缺点是取梯度的时候,是通过索引来获取的,而这些梯度的获取顺序是按照特征的大小顺序的,(并且不同特征的访问顺序也不同),这将导致非连续的内存访问,可能使得CPU cache缓存命中率低,从而影响算法效率。而LGB是基于直方图分裂特征的,梯度信息都存储在一个个bin(桶:离散值索引?)中,所以访问梯度是连续的,缓存命中率高。

(5)LightGBM 与 XGboost 的并行策略不同:

  • 特征并行 :LGB特征并行的前提是每个worker留有一份完整的数据集,但是每个worker仅在特征子集上进行最佳切分点的寻找;worker之间需要相互通信,通过比对损失来确定最佳切分点;然后将这个最佳切分点的位置进行全局广播,每个worker进行切分即可。XGB的特征并行与LGB的最大不同在于XGB每个worker节点中仅有部分的列数据,也就是垂直切分,每个worker寻找局部最佳切分点,worker之间相互通信,然后在具有最佳切分点的worker上进行节点分裂,再由这个节点广播一下被切分到左右节点的样本索引号,其他worker才能开始分裂。二者的区别就导致了LGB中worker间通信成本明显降低,只需通信一个特征分裂点即可,而XGB中要广播样本索引。
  • 数据并行 :当数据量很大,特征相对较少时,可采用数据并行策略。LGB中先对数据水平切分,每个worker上的数据先建立起局部的直方图,然后合并成全局的直方图,采用直方图相减的方式,先计算样本量少的节点的样本索引,然后直接相减得到另一子节点的样本索引,这个直方图算法使得worker间的通信成本降低一倍,因为只用通信以此样本量少的节点。XGB中的数据并行也是水平切分,然后单个worker建立局部直方图,再合并为全局,不同在于根据全局直方图进行各个worker上的节点分裂时会单独计算子节点的样本索引,因此效率贼慢,每个worker间的通信量也就变得很大。
  • 投票并行(LGB):当数据量和维度都很大时,选用投票并行,该方法是数据并行的一个改进。数据并行中的合并直方图的代价相对较大,尤其是当特征维度很大时。大致思想是:每个worker首先会找到本地的一些优秀的特征,然后进行全局投票,根据投票结果,选择top的特征进行直方图的合并,再寻求全局的最优分割点。

LightGBM的调参过程?

learning_rate:学习率,预先设定一个较高的值,如0.1

boosting_type: 默认选择gbdt

n_estimators/num_boost_round:迭代次数(残差树的个数)

max_depth:树的深度

num_leaves:叶子个数,一般小于2**max_depth

min_data_in_leaf:节点中样本点最小个数

max_bin:最大分桶的个数(离散化时取值的最大值)

feature_fraction: 特征的采样率

bagging_fraction: 样本的采样率

bagging_freq: k,意味每k次迭代(每生成k棵树)执行bagging

lambda_l1: L1正则化参数

lambda_l2: L2正则化参数

min_split_gain: 分裂最小增益阈值,分裂增益小于阈值则终止分裂

  • 针对leaf-wise树的参数优化

    • num_leaves:控制了叶节点的数目。它是控制树模型复杂度的主要参数。如果是level-wise,则该参数为2**depth,其中depth为树的深度。但是当叶子数量相同时,leaf-wise的树要远远深过level-wise树,非常容易导致过拟合。因此应该让num_leaves小于2^depth。在leaf-wise树中,并不存在depth的概念。因为不存在一个从leaves到depth的合理映射。
    • min_data_in_leaf: 每个叶节点的最少样本数量。它是处理leaf-wise树的过拟合的重要参数。将它设为较大的值,可以避免生成一个过深的树。但是也可能导致欠拟合。
    • max_depth:控制了树的最大深度。该参数可以显式的限制树的深度。
  • 针对更快的训练速度

    • 通过设置 bagging_fraction 和 bagging_freq 参数来使用 bagging 方法
    • 通过设置 feature_fraction 参数来使用特征的子抽样
    • 使用较小的 max_bin(离散化值:分割节点)
    • 使用 save_binary 在未来的学习过程对数据加载进行加速
  • 获得更好的准确率

    • 使用较大的 max_bin (学习速度可能变慢)
    • 使用较小的 learning_rate 和较大的 num_iterations
    • 使用较大的 num_leaves (可能导致过拟合)
    • 使用更大的训练数据
    • 尝试DART
  • 缓解过拟合

    • 使用较小的 max_bin, 分桶粗一些
    • 使用较小的 num_leaves 不要在单棵树分的太细
    • 使用 lambda_l1, lambda_l2 和 min_gain_to_split 来使用正则
    • 尝试 max_depth 来避免生成过深的树
    • 使用 min_data_in_leaf 和 min_sum_hessian_in_leaf, 确保叶子节点有足够多的数据

LightGBM的调参步骤

第一步:学习率和迭代次数我们先把学习率先定一个较高的值,这里取 learning_rate = 0.1,其次确定估计器boosting/boost/boosting_type的类型,不过默认都会选gbdt。

1
2
3
4
5
6
7
8
9
'boosting_type'/'boosting': 'gbdt'
'objective': 'binary'
'metric': 'auc'
 
# 以下是选择的初始值
'max_depth': 5     # 由于数据集不是很大,所以选择了一个适中的值,其实4-10都无所谓。
'num_leaves': 30   # 由于lightGBM是leaves_wise生长,官方说法是要小于2^max_depth
'subsample'/'bagging_fraction':0.8           # 数据采样
'colsample_bytree'/'feature_fraction': 0.8   # 特征采样

迭代的次数,也可以说是残差树的数目,参数名为n_estimators/num_iterations/num_round/num_boost_round。我们可以先将该参数设成一个较大的数,然后在cv结果中查看最优的迭代次数lgb.cv(params, data_train, num_boost_round=1000, nfold=5, stratified=False, shuffle=True, metrics='auc',early_stopping_rounds=50,seed=0)

我们根据以上结果,就可以取n_estimators=188

第二步:确定max_depth和num_leaves这是提高精确度的最重要的参数。这里我们引入sklearn里的GridSearchCV()函数进行搜索。

1
2
3
4
5
6
7
8
from sklearn.grid_search import GridSearchCV

params_test1={'max_depth': range(3,8,1), 'num_leaves':range(5, 100, 5)}
              
gsearch1 = GridSearchCV(estimator = lgb.LGBMClassifier(boosting_type='gbdt',objective='binary',metrics='auc',learning_rate=0.1, n_estimators=188, max_depth=6, bagging_fraction = 0.8,feature_fraction = 0.8), 
                       param_grid = params_test1, scoring='roc_auc',cv=5,n_jobs=-1)
gsearch1.fit(X_train,y_train)
gsearch1.grid_scores_, gsearch1.best_params_, gsearch1.best_score_

根据结果,我们取max_depth=4, num_leaves=10

第三步:确定min_data_in_leaf和max_bin

1
2
3
4
5
6
params_test2={'max_bin': range(5,256,10), 'min_data_in_leaf':range(1,102,10)}
              
gsearch2 = GridSearchCV(estimator = lgb.LGBMClassifier(boosting_type='gbdt',objective='binary',metrics='auc',learning_rate=0.1, n_estimators=188, max_depth=4, num_leaves=10,bagging_fraction = 0.8,feature_fraction = 0.8), 
                       param_grid = params_test2, scoring='roc_auc',cv=5,n_jobs=-1)
gsearch2.fit(X_train,y_train)
gsearch2.grid_scores_, gsearch2.best_params_, gsearch2.best_score_

这个结果就不显示了,根据结果,我们取min_data_in_leaf=51,max_bin in=15。

第四步:确定feature_fraction、bagging_fraction、bagging_freq

第五步:确定lambda_l1和lambda_l2

第六步:确定 min_split_gain

第七步:降低学习率,增加迭代次数,验证模型

1
2
3
4
5
6
model=lgb.LGBMClassifier(boosting_type='gbdt',objective='binary',metrics='auc',learning_rate=0.01, n_estimators=1000, max_depth=4, num_leaves=10,max_bin=15,min_data_in_leaf=51,bagging_fraction=0.6,bagging_freq= 0, feature_fraction= 0.8,
lambda_l1=1e-05,lambda_l2=1e-05,min_split_gain=0)
model.fit(X_train,y_train)
y_pre=model.predict(X_test)
print("acc:",metrics.accuracy_score(y_test,y_pre))
print("auc:",metrics.roc_auc_score(y_test,y_pre))

这样会发现, 调完参之后, 比使用默认参数的acc,auc都会有所提高。还有一种是LightGBM的cv函数调参, 这个比较省事,写好代码自动寻优,但是需要调参经验,如何设置一个好的参数范围, 这个不写了,篇幅太长,具体的看最后面那个链接吧。

sklearn里的GridSearchCV()函数

XGBoost其他问题(极端梯度提升)

  • 与GBDT不同之处?

    • 用泰勒展开近似目标函数
  • XGBoost为什么使用泰勒二阶展开?为什么用二阶信息不用一阶?
  • XGBoost在什么地方做的剪枝,怎么做的?
  • XGBoost如何分布式?特征分布式和数据分布式? 各有什么存在的问题?
  • XGBoost里处理缺失值的方法?
  • XGBoost有那些优化?
  • xgboost对预测模型特征重要性排序的原理?
  • XGBoost如何寻找最优特征?是又放回还是无放回的呢?
  • GBDT和XGBoost的区别是什么?
  • lightgbm和xgboost有什么区别?他们的loss一样么? 算法层面有什么区别?

XGBoost怎么调参

(1) XGBoost重要参数

xgboost主要分为三类参数:

1.通用参数 general parameter

booster: 每次迭代的模型选择,gbtree或者gbliner

silent: 控制打印信息,(过时,被verbosity代替)

nthread:并行的线程数,默认使用最大的核数

2.Booster参数:Parameters for Tree Booster

eta: shinkage防止过拟合,默认0.3

gamma:公式中叶子节点个数的参数,也就是分类后损失函数的增益,增益大于这个阈值,才会对节点进行分裂。

max_depth:默认为0,树的最大深度,用来避免过拟合

min_child_weight: 最小的叶子节点样本权重和,如果节点分裂造成一个叶子节点的样本权重和小于该值,则放弃分裂。

max_delta_step: 该参数仙子每棵树权重改变的最大步长。一般用不到,但是在数据样本极度不平衡时,可能对逻辑回归有帮助。

subsample:训练样本随机采样的比例。

colsample_bytree, colsample_bylevel, colsample_bynode: 列采样的参数设置。bytree表示在构建每棵树的时候使用。bylevel表示构建每层节点的时候使用,bynode在每次分裂的时候使用。

lambda: L2正则化项。默认为1.

alpha:L1的正则化项.

scale_pos_weight: 控制正负样本的平衡用于不平衡数据

3.学习任务参数:控制训练目标的表现

objective:定义损失函数。常用值有binary:logistic; multi:softmax; multi:softprob

eval_metic: 验证集的评估指标。rmse, mae, logloss, error, merror, mlogloss, auc

seed:随机数的种子,设置它可以复现随机数的结果,也可以用于调整参数。

(2) XGBoost调参技巧

a.当出现过拟合时,有两类参数可以缓解:

  • 第一类参数:用于直接控制模型的复杂度。包括max_depth, min_child_weight, gamma等参数
  • 第二类参数:用于增加随机性,从而使得模型在训练时对于噪声不敏感,包括subsample, colsample_bytree.

也可以直接检查步长eta,此时需要增加num_round参数.

b.当遇到数据不平衡时(如广告点击率预测任务),有两种方式提高模型的预测性能:

  • 如果关心的是预测的AUC.

可以通过scale_pos_weight参数来平衡正负样本的权重; 使用AUC来评估。

  • 如果关心的是预测的正确率

不能重新平衡正负样本**;设置max_delta_step为一个有限的值(如1),从而有助于收敛

LightGBM

原理

LightGBM (Light Gradient Boosting Machine)是一个实现GBDT算法的框架,支持高效率的并行训练。

LigthGBM也是一种boosting算法,它由微软开源,是XGB的一种轻量级实现,用于分类或者回归问题。在准确率与XGB相近的情况下,大大减少运行时长和内存占用

LightGBM提出的主要原因就是为了解决GBDT在海量数据遇到的问题,让GBDT可以更好更快地用于工业实践。

优点

  • 更快的训练速度
  • 更低的内存消耗
  • 更好的准确率
  • 分布式支持,可以快速处理海量数据

🚩与XGB相比的优化

  • 基于Histogram算法的决策树算法 - 将遍历样本转变为遍历直方图,极大的降低了时间复杂度;
  • 带深度限制的Leaf-wise的叶子生长策略 - 减少了很多不必要的计算量
  • 直方图做差加速 - 将遍历样本转变为遍历直方图,极大的降低了时间复杂度;
  • 直接支持类别特征(Categorical Feature)
  • Cache命中率优化
  • 基于直方图的稀疏特征优化多线程优化。
  1. 单边梯度抽样算法 - 过滤掉梯度小的样本,减少了大量的计算;
  2. 直方图算法 - 将遍历样本转变为遍历直方图,极大的降低了时间复杂度;
  3. 互斥特征捆绑算法(EFB)
  4. 带深度限制的 Leaf-wise 算法 - 减少了很多不必要的计算量

img

Histogram算法

直方图算法的基本思想是先把连续的浮点特征值离散化成k个整数(其实又是分桶的思想,而这些桶称为bin,比如[0,0.1)→0, [0.1,0.3)→1),同时构造一个宽度为k的直方图。

在遍历数据的时候,根据离散化后的值作为索引在直方图中累积统计量,当遍历一次数据后,直方图累积了需要的统计量,然后根据直方图的离散值,遍历寻找最优的分割点。

img

使用直方图算法有很多优点。首先,最明显就是内存消耗的降低,直方图算法不仅不需要额外存储预排序的结果,而且可以只保存特征离散化后的值,而这个值一般用8位整型存储就足够了,内存消耗可以降低为原来的1/8。然后在计算上的代价也大幅降低,预排序算法每遍历一个特征值就需要计算一次分裂的增益,而直方图算法只需要计算k次(k可以认为是常数),时间复杂度从O(#data#feature)优化到O(k#features)。

带深度限制的Leaf-wise的叶子生长策略

在XGBoost中,树是按层生长的,称为Level-wise tree growth,同一层的所有节点都做分裂,最后剪枝,如下图所示:

img

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

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

img

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

直方图差加速

LightGBM另一个优化是Histogram(直方图)做差加速。一个容易观察到的现象:一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图,需要遍历该叶子上的所有数据,但直方图做差仅需遍历直方图的k个桶。

利用这个方法,LightGBM可以在构造一个叶子的直方图后,可以用非常微小的代价得到它兄弟叶子的直方图,在速度上可以提升一倍。

直接支持类别特征

实际上大多数机器学习工具都无法直接支持类别特征,一般需要把类别特征,转化到多维的0/1特征,降低了空间和时间的效率。而类别特征的使用是在实践中很常用的。基于这个考虑,LightGBM优化了对类别特征的支持,可以直接输入类别特征,不需要额外的0/1展开。并在决策树算法上增加了类别特征的决策规则。在Expo数据集上的实验,相比0/1展开的方法,训练速度可以加速8倍,并且精度一致。据我们所知,LightGBM是第一个直接支持类别特征的GBDT工具。

CatBoost

极简示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import numpy as np
import catboost as cb

# 读数据
train_data = np.random.randint(0, 100, size=(100, 10))
train_label = np.random.randint(0, 2, size=(100))
test_data = np.random.randint(0,100, size=(50,10))
print(train_data,train_label,test_data)

# 建立模型
model = cb.CatBoostClassifier(iterations=2, depth=2, learning_rate=0.5, loss_function='Logloss',
                              logging_level='Verbose')
# 模型拟合
model.fit(train_data, train_label, cat_features=[0,2,5])
# 预测
preds_class = model.predict(test_data)
preds_probs = model.predict_proba(test_data)
print('class = ',preds_class)
print('proba = ',preds_probs)

机器学习中的距离计算方法

设空间中两个点为(x1,y1),(x2,y2):

欧式距离:

img

曼哈顿距离(城区距离):

​ d(i,j)= X1-X2 + Y1-Y2

余弦距离:

img

**欧式距离与余弦距离的对比? **

1.欧式距离的数值受到维度的影响,余弦相似度不受维度影响, 在高维的情况下也依然保持低维完全相同时相似度为1等性质。

2.欧式距离体现的是距离上的绝对差异,余弦距离体现的是方向上的相对差异。

**切比雪夫距离(横向纵向最大距离): **

​ dis=max(abs(x1-x2),abs(y1-y2))

其他问题

如何做特征组合

特征组合的思想很简单,通过将单独的特征进行组合(相乘或求笛卡尔积)而形成的合成特征。比如属性A有三个特征,属性B有两个特征,笛卡尔积后就有六个组合特征,然后用one hot 或其他embedding方式给新的特征编码

为什么朴素贝叶斯如此“朴素”?

因为它假定所有的特征在数据集中的作用是同样重要和独立的。正如我们所知,这个假设在现实世界中是很不真实的,因此,说朴素贝叶斯真的很“朴素”。

启发式搜索算法总结

启发式搜索算法蕴含着许多人生哲学,它虽不是数学方法,其思想更类似于人类解决问题的思想和一些人生中总结的道理,值得好好体会。最后用网上一段描述各种搜索算法的例子来作为总结:

为了找出地球上最高的山,一群有志气的兔子们开始想办法。 (1)兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山法,它不能保证局部最优值就是全局最优值。 (2)兔子喝醉了。他随机地跳了很长时间。这期间,它可能走向高处,也可能踏入平地。但是,他渐渐清醒了并朝他踏过的最高方向跳去。这就是模拟退火。 (3)兔子们知道一个兔的力量是渺小的。他们互相转告着,哪里的山已经找过,并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。 (4)兔子们吃了失忆药片,并被发射到太空,然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是,如果你过几年就杀死一部分海拔低的兔子,多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。

如何用根据特征重要性筛选特征

利用模型的 feature_importances_方法。

阈值的选择会进行遍历并选择最佳的阈值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from numpy import sort
from sklearn.feature_selection import SelectFromModel # Fit model using each importance as a threshold
thresholds = sort(model_XGB.feature_importances_)
for thresh in thresholds:
  # select features using threshold
  selection = SelectFromModel(model_XGB, threshold=thresh, prefit=True)
  select_X_train = selection.transform(X_train)
  # train model
  selection_model = XGBClassifier()
  selection_model.fit(select_X_train, y_train)
# eval model
  select_X_test = selection.transform(X_test)
  y_pred = selection_model.predict(select_X_test)
  predictions = [round(value) for value in y_pred]
  accuracy = accuracy_score(y_test, predictions)
  print("Thresh=%.3f, n=%d, Accuracy: %.2f%%" % (thresh, select_X_train.shape[1],
      accuracy*100.0))

谈谈判别式模型和生成式模型?

判别方法:由数据直接学习决策函数 Y = f(X),或者由条件分布概率 P(Y X)作为预测模型,即判别模型。
生成方法:由数据学习联合概率密度分布函数 P(X,Y),然后求出条件概率分布P(Y X)作为预测的模型,即生成模型。

由生成模型可以得到判别模型,但由判别模型得不到生成模型。

常见的判别模型有:K近邻、SVM、决策树、感知机、线性判别分析(LDA)、线性回归、传统的神经网络、逻辑斯蒂回归、boosting、条件随机场

常见的生成模型有:朴素贝叶斯、隐马尔可夫模型、高斯混合模型、文档主题生成模型(LDA)、限制玻尔兹曼机