Boosting(XGBoost、LightGBM)

XGBoost和LightGBM都属于GBDT的变种，见上篇；读本篇需要先熟练理解和掌握CART回归树和GBDT算法。

XGBoost

原论文： https://arxiv.org/abs/1603.02754

基于CART回归树的生成方法：依然是先确定最优树的结构，然后通过最小化损失函数确定叶子结点的输出值，XGBoost在GBDT上做了一定改进

引入正则化项来控制树的复杂度

表记$T(x;\Theta_{m})=w_{q(x)}$，$x$为一个样本，$q(x)$表示该样本所在的叶子结点，$w_q$为叶子节点$q$的回归输出；于是$w_{q(x)}$即表示每个样本的回归输出，即决策树的输出。定义集合$I_j=\{i|q(x^{(i)})=j\}$表示划分到叶结点$j$的所有训练样本的集合即上一篇的表示法：$\{x|x∈R_{j}\}$。$T$为叶子节点个数（即划分个数）$m$为步/轮数，$N$为样本个数。

定义每一步生成新决策树的损失函数的正则项：

$$\Omega(T(x;\Theta_m))=\gamma T+\frac{1}{2}\lambda||w||^2$$

可以看出惩罚考虑了两项：$T$为叶子节点个数，$w$为每个样本的输出值

（也可以用$c$表示：$\Omega(T(x;\Theta_m))=\gamma T+\frac{1}{2}\lambda||c||^2$，$c$即每个划分的输出值，也就对应了每个样本的输出）

XGBoost向损失函数加入此正则项($L’$为不含正则项的原损失函数)变为（样本总体损失函数）：

$$L(y_{i+1},f_{m+1}(x_i))=\sum_iL'(y_{i+1},f_{m+1}(x_i))+\Omega(T(x;\Theta_{m+1}))$$

修改拟合目标

在AdaBoost中我们是拟合残差

在GBDT中我们是去拟合负梯度（一阶导数，泰勒公式一阶展开求导得出）来替代拟合残差

而XGBoost中， 直接用泰勒展开式将损失函数二阶展开，求其一阶梯度和二阶梯度，正因为使用损失函数的二阶泰勒展开，因此与损失函数更接近，比只使用了一阶展开的GBDT收敛速度更快（前提是函数一阶、二阶都连续可导，而且在这里计算一阶导和二阶导时可以并行计算）

$$g_i=\frac{\partial L'(y_i,f(x_i))}{\partial f(x_i)},h_i=\frac{\partial^2 L '(y_i,f(x_i))}{\partial f(x_i)}$$

于是用和GBDT一样的方法，对无正则的原损失函数（单个样本）$L’(y_{i+1},f_{m+1}(x_i))$在$\hat f_m(x_i)$处进行泰勒二阶展开，这里简要推导：

$L’(y_{i+1},f_{m+1}(x_i))=L’(y_{i+1},f_m(x_i)+T(x,\Theta_{m+1}))$

对右式在$\hat f_m(x_i)$二阶泰勒展开，并令$x’=\hat f_m(x_i)+T(x,\Theta_{m+1})$，$y$为无关常量

$\therefore 原式≈L’(y_{i+1},f_m(x_i))+g_i(x’-\hat f_m(x_i))+\frac{1}{2}h_i(x’-\hat f_m(x_i))^2$

$=L’(y_{i+1},f_m(x_i))+g_iT(x,\Theta_{m+1})+\frac{1}{2}h_iT^2(x,\Theta_{m+1})$

由于对本轮优化来说，$L’(y_{i+1},f_m(x_i))$是个常数，不会影响损失函数，于是：

$L’(y_{i+1},f_{m+1}(x_i))≈g_iT(x,\Theta_{m+1})+\frac{1}{2}h_iT^2(x,\Theta_{m+1})$

于是计算整个样本集的损失函数（前面的损失函数都是单个样本的）加上前面的正则构成目标损失函数：

$Obj_{m+1}=\sum_{i=1}^N[g_iT(x,\Theta_{m+1})+\frac{1}{2}h_iT^2(x,\Theta_{m+1})]+\gamma T+\frac{1}{2}\lambda||w||^2$，转换表示，见开头的表记方法

$=\sum_{i=1}^N[g_iw_{q(x_i)}+\frac{1}{2}h_iw^2_{q(x_i)}]+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^Tw_j^2$ ，将对样本求和改为对划分求和，同一个叶子节点/划分$j$的输出值是相同的，即$w_{q(x_i)}=w_j\quad if\quad i∈I_j$，于是改写为：

$Obj_{m+1}=\sum_{j=1}^T[(\sum_{i∈I_j} g_i)w_j+\frac{1}{2}(\sum_{i∈I_j}h_i+\lambda)w_j^2]+\gamma T$

$$令G_j=\sum_{i∈I_j} g_i \quad ,H_j=\sum_{i∈I_j}h_i\quad,则：$$ $$Obj_{m+1}=\sum_{j=1}^T[G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2]+\gamma T$$

①于是【根据此损失函数先确定$(j,s)$划分，确定决策树的结构】

但是注意到实际上在确定决策树结构（选择最优特征和分割点）的时候，决策树结构数量是无穷的，所以实际上并不能穷举所有可能的决策树结构。什么样的决策树结构是最优的呢？通常使用贪心策略来生成决策树的每个结点。——因为对某个结点采取的是二分策略，分别对应左子结点和右子结点，除了当前待处理的结点，其他结点对应的$Obj_{m+1}$值都不变，所以对于收益的计算只需要考虑当前结点的$Obj_{m+1}$值即可。

（其它DT和基于DT的boosting通常也用贪心策略）

1. 从深度为0的树开始对每个叶子结点穷举所有的可用特征；
2. 针对每一个特征，把属于该结点的训练样本的该特征升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并采用最佳分裂点时的收益；
3. 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，把该结点生成出左右两个新的叶子结点，并为每个新结点关联新的样本集；
4. 退回到第一步，继续递归操作直到满足特定条件。

不过原作者没有直接这样暴力枚举，因为即使贪心策略只考虑当前结点，该结点内可能的分裂点也很多。于是原作者通过加权分位数的算法选出了一些可能的分裂点（见后文）。

下面我们就要通过一个增益函数/打分函数来判断谁是最佳特征和分裂点了：

分裂前针对该结点的最优目标函数(这个最优目标函数是假设结构已经固定的情况下在第②步中先求出来的）为：

$$Obj_{m+1}^{(before)}=-\frac{1}{2}\frac{G^2}{H+\lambda}+\gamma=-\frac{1}{2}\frac{(G_L+G_R)^2}{(H_L+H_R)+\lambda}+\gamma$$

分裂后的最优目标函数为：（$G分为左G_L和右G_R,H同理$）

$$Obj_{m+1}^{(later)}=-\frac{1}{2}[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}]+2\gamma$$

于是对于目标函数$Obj_m$，分裂后的收益为$Gain=Obj_{m+1}^{(before)}-Obj_{m+1}^{(later)}$：

$$Gain=\frac{1}{2}[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{(H_L+H_R)+\lambda}]-\gamma$$

为了限制树的生长，我们可以加入阈值，当增益大于阈值时才让节点分裂，上式中的$\gamma$即阈值，它是正则项里叶子节点数$T$的系数，所以XGBoost在优化目标函数的同时相当于做了预剪枝。 同时可以看出该式子中$\lambda$起了对叶结点score做平滑的作用。（这俩参数定义见最前面的正则化公式）这两个参数在这里求分裂的时候也都起了正则化作用

故可用此公式决定最优分裂特征和分裂点，贪心地选择收益最大的作为分裂点

②【根据损失函数确定每个结点的最优回归输出】

由于决策树的结构已经固定了，那么就知道了$q(),I_j$。（这里的①与GBDT的第③步一样的，先求出划分，结构就固定了，然后在GDBT中下一步③求出残差的替代让新决策树去拟合之（即缩小与残差的损失函数），求得每个结点的最优输出值；不过在XGBoost中这里推导出了一个由一阶导，二阶导构成的损失函数，于是XGBoost就是要去缩小这个损失函数，选取每个结点的最优输出值）；

又由于$g_i,h_i$是对当前已知模型(上一步/轮求出来的)$f_m(x_i)$的导数，那么$G_j,H_j$也是已知常数，于是让目标损失函数$Obj_{m+1}$对$w_j$求0导（我们原来是要对$T(x;\Theta_{m})$求导的，而$T(x;\Theta_{m})=w_{q(x)}$）可得

$$w^o=-\frac{G_j}{H_j+\lambda}$$ $$最优损失函数:Obj_{m+1}=-\frac{1}{2}\sum_{j=1}^T\frac{G^2_j}{H_j+\lambda}+\gamma T$$

$w^o=-\frac{G_j}{H_j+\lambda}$即为叶子节点的最优输出，相当于GDBT的第④步

引入学习率/缩减（Shrinkage）

在更新前向分步模型的时候，在新树的输出引入学习率，以防止过拟合

$$f_{m+1}(x)=f_{m}(x)+\epsilon T^o(x;\Theta_{m+1})$$

引入分布式加权分位数略图算法

在决策树分裂的时候引入的减小计算量的方法：weighted quantile sketch。本质是基于权重的采样

决策树的分裂基本都是基于贪心的，也就是只考虑当前结点的最优特征和划分而不考虑全局最优，但这样依然需要穷举该结点内每个可能的分裂点。当数据没法全部加载到内存中时，这种方法会比较慢，XGBoost提出了一种近似的方法去高效的生成候选分割点——分布式加权分位数略图算法

先看加权分位数略图算法

对原目标式：$Obj_{m+1}=\sum_{i=1}^N[g_iT(x,\Theta_{m+1})+\frac{1}{2}h_iT^2(x,\Theta_{m+1})]+\Omega(T(x;\Theta_m))$变形，在里面添加一个常数：

$=\sum_{i=1}^N[g_iT(x,\Theta_{m+1})+\frac{1}{2}h_iT^2(x,\Theta_{m+1})+\frac{1}{2}\frac{g_i^2}{h_i}]+\Omega(T(x;\Theta_m))+constant$

$=\sum_{i=1}^n\frac{1}{2}h_i[T(x,\Theta_{m+1})-(-\frac{g_i}{h_i})^2]+\Omega(T(x;\Theta_m))+constant$

可以看出，最后的目标代价函数就是一个$h_i$的加权平均损失函数

于是进一步我们想要如何以分位数的方式划分区域来取候选点。

思想：我们将特征样本排序，划分成不同区域，对样本取分位数点，每个分位数点落在区域内，但由于样本权重越高的区域，预测结果越是不确定的样本区域，切分的粒度就应该越密集。

那么具体怎么实现呢：

对于数据集$D_k=\{(x_{1k},h_1),(x_{2k},h_2),\cdots,(x_{nk},h_n)\}$，$k$表示某特征，$h$即为损失函数在该样本在$k$特征对应的二阶梯度

s在加权分位缩略图算法中，取值是按照Rank来取的：

$$r_k(z)=\frac{\sum_{(x,h)∈D_k,x<z}h}{\sum_{(x,h)∈D_k}h}$$

输入为某个特征的值$z$,计算的是该特征所有可取值中小于$z$的特征值的总权重占总的所有可取值的总权重和的比例，输出为一个比例值。 这个Rank计算出来就相当于将原特征值用$h$加了权映射到$(0,1)$上

于是按照此公式选取候选分割点$\{s_{k1},s_{k2},\cdots,s_{kl}\}$：

$$|r_k(s_{k,j})-r_k(s_{k,j+1})|<\epsilon\quad,s_{k1}=\min_ix_{ik},s_{kl}=\max_ix_{ik}$$

$\epsilon$ 是一个近似比例，或叫扫描步幅，就是说在加权后的特征取值区间上，按照步幅$\epsilon$取值，得到$\frac{1}{\epsilon}$个候选点

取值分两种：

①global proposal ：也就是在最开始树还没分裂的时候就选好一组$\{s_{k1},s_{k2},\cdots,s_{kl}\}$，在总体样本里选择，每次树切分的时候都不变 。

②local proposal：它是在每次树分割成子树之后再选择出一组$\{s_{k1},s_{k2},\cdots,s_{kl}\}$，来自子树的样本集！

两种都要，共同组成分割候选点集合。对于子树中存在的global proposal选取的分割点，需要加入子树local proposal选取的分割点集合中，组成子树候选点

于是可以找到整合和的所有候选点$\{s_{k1},s_{k2},\cdots,s_{kl}\}$

对于分布式加权分位数略图算法，多了两个操作合并merge和修剪prune，可以看这篇文章xgboost之分位点算法

引入直方图算法

找到了候选点$\{s_{k1},s_{k2},\cdots,s_{kl}\}$，就要开始遍历候选点选最大收益的最优分割点，直方图算法是在遍历候选点寻找最大增益的最优分割时候所进行的优化

使用直方图算法，即生成直方图。候选点将样本集合划分为了很多区间，每个区间叫分桶。在每个分桶上对样本统计值$g$、$h$进行累加统计求$Gain$，这样就生成了一个直方图，每个桶的值就是桶内二阶梯度之和，即累加统计的$Gain$。这时候我们要计算最优划分，就遍历候选点将其左边所有桶和右边所有桶分别作为左右子树求比不分裂前的增益，求使这个增益最大那个划分即可。

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

[总结上2]如何分割成子树

（分布式加权分位数略图算法+直方图算法）：

1. [找候选点：分布式加权分位数略图算法]求global proposal和local proposal，得到一系列候选分裂点集合$\{s_{k1},s_{k2},\cdots,s_{kl}\}$（加权分位数略图算法）

2. [在候选点中找最优点：直方图算法]候选点将样本集合划分为了很多区间，每个区间叫分桶。在每个分桶上对样本统计值$g$、$h$进行累加统计求$Gain$，最后在这些累计的统计量上寻找最佳分裂点。（这步其实就是使用增益公式遍历选最佳分裂点的步骤，只是反映都直方图上）

结合贪心，替代上面“修改拟合目标”中的1234暴力枚举法

允许缺失值存在

XGBoost模型允许缺失值的存在。对于特征值缺失的样本，XGBoost可以学习这些缺失值的分裂方向。

具体地，XGBoost把缺失值当做稀疏矩阵来对待，即本身的在节点[遍历寻找某特征的最优分裂点时不考虑缺失值的数值，只对非缺失值进行遍历]<=允许缺失值存在的核心。所以缺失值对树生成不会有影响，缺失值数据会继续被其他特征进行最优划分，最终学习到分类（如果用下面的①可以最优但增加计算负担，用②也可以，实际上影响不大）。

于是两种处理方法：

①将缺失值分到左子树和右子树分别计算损失，选择较优的那个。

②也可以直接设定缺失值默认分类方向。实际处理时，比如可以将缺失值设置成missing=-999等，大大提高运算速度。

如果训练中没有数据缺失，预测时出现了数据缺失，那么默认被分类到右子树。

（在原始的GBDT策略中是要手动对缺失值进行处理的）

计算机系统优化

这部分略，可以阅读原论文

XGBoost算法总结

1. 初始化

2. 迭代计算每一步：

   ①计算损失函数在当前模型的一阶梯度和二阶梯度：

   $$g_i=\frac{\partial L'(y_i,f(x_i))}{\partial f(x_i)},h_i=\frac{\partial^2 L '(y_i,f(x_i))}{\partial f(x_i)}$$ $$G_j=\sum_{i∈I_j} g_i \quad ,H_j=\sum_{i∈I_j}h_i\quad$$

   ② 通过加权分位数算法选出了一些可能的分裂点。

   根据增益公式计算可能的特征和分裂点，选择最大化该公式的最优特征和最优分裂点，确定新树结构：

   $$Gain=\frac{1}{2}[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{(H_L+H_R)+\lambda}]-\gamma$$

   $\lambda$有正则效果，$\gamma$作为分裂阈值，也起了正则化效果

   ③根据损失函数极小化确定每个子结点的回归输出

$$T^o(x;\Theta_{m+1})=-\frac{G_j}{H_j+\lambda}$$

​ ④新树乘以学习率，前向分步模型更新

$$f_{m+1}(x)=f_{m}(x)+\epsilon T^o(x;\Theta_{m+1})$$

​ 3. 迭代直到满足停止条件

相比GBDT的优点

1. 由于XGBoost使用了损失函数的泰勒二阶展开，因此与损失函数更接近，对其进行拟合，收敛速度更快。

   而GBDT只进行了一阶展开。

2. 加入了正则项，控制模型复杂度，避免过拟合。正则项$\gamma$一方面在分割的时候相当于做了预剪枝，正则项$\lambda$相当于对leaf score做了平滑作用，这俩都等效于正则化；另一方面在损失函数中起到了正则化

3. 采用[近似的]最优特征与最优分割点选择方法（加权中位数方法+贪心算法 ）。

   a.贪心即只考虑当前结点最优特征和最优划分。（贪心算法一般决策树分裂都用，否则找全局最优，决策树枚举完计算量是非常大的）

   b.同时决策树结点在分裂时需要穷举每个可能的分裂点，当数据没法全部加载到内存中时，这种方法会比较慢，XGBoost提出了一种近似的方法去高效的生成候选分割点——加权分位数的方法寻找可能的分裂点。

   ①可以加速和减小内存消耗

   ②支持并行，在对每棵决策树进行结点分裂时，需要每个特征的增益，选择最大的那个特征作为分裂特征，各个特征的增益计算可以多线程进行（GBDT其实也可以在求增益的时候做并行，但它没有做；XGBoost专门设置了一个block结构来储存并行计算的增益特征）

   ③支持对缺失值的处理，对于特征值缺失的样本，XGBoost可以学习这些缺失值的分裂方向。见上

   （在原始的GBDT策略中是手动对缺失值进行处理的）

4. 在每一轮更新前向分步模型的时候引入了学习率，防止过拟合。学习率可以降低每颗学到的新树的影响。在实际操作的时候可以将学习率设置低一点，迭代次数设置更大。（GBDT也有学习率）

5. 引进了特征子采样/列抽样 ，像Random Forest那样，既能降低过拟合，还能减少计算。

LightGBM

原论文： https://www.microsoft.com/en-us/research/publication/lightgbm-a-highly-efficient-gradient-boosting-decision-tree/

LightGBM是微软去年才发表并开源的新算法，也是一种基于GBDT的算法。其能达到速度比XGBoost快，但精度却一样。

其核心是在GBDT的每个CART分裂子树，选取最优分裂点的方法上进行了改进。原始GBDT中，即使使用了贪心，要对每个分裂点进行枚举，计算量也非常大。在XGBoost中，使用了加权分位数略图算法来解决这个问题。

但对于GBDT，是没有权重的（没有像XGBoost采用二阶梯度），于是在LightGBM中为了基于GBDT改进，提出了Gradient-based One-Side Sampling (GOSS)和Exclusive Feature Bundling (EFB)算法来解决最优分割点选取问题

直方图算法与差加速

LightGBM采用了直方图算法，与XGBoost一样（但没有权重）。可以看XGBoost的直方图算法标题。

直方图差加速：一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图，需要遍历该叶子上的所有数据，使用差算法来做仅需遍历直方图的$k$个分桶

Gradient-based One-Side Sampling(GOSS)

基于梯度的单边采样。GOSS是一种在减少数据量和保证精度上平衡的算法。

来源于基础思想：对于残差（一阶梯度）较小的样本，直接舍去不学习（因为其已经学得很好了）。但这样改变了数据分布，必然会影响模型的精度，于是提出GOSS，在这个思想上进行改进。

[思想]：GOSS保留残差（梯度）较大的样本，在梯度较小的样本上使用随机采样；并且给小样本采样的时候给一个更大的权重以免过多改变数据分布。

[具体地]：

1. 先计算每个样本的残差（梯度）

2. 对残差的绝对值排序产生一个新序列

3. 选取比例$a$的样本作为残差较大的样本，全部遍历求增益；

   在剩余的数据（比例$1-a$，为残差较小的样本）中以采样率$b$进行随机采样出一批样本，遍历求增益

4. 在计算信息增益的时候，为采样出的残差小的数据乘以$\frac{1-a}{b}$（ 即：小梯度样本总数/随机采样出的小梯度样本数量，把采样值扩大到相当于采取了原始个数的样本）

附上原论文的算法：

原论文还继续分析了GOSS的性能和泛化性（分析过程见原论文，略），得到结论：

①[性能分析]：随机采样是GOSS在$a=0$的一种情况。多数情况下，GOSS性能优于随机采样；GOSS并不会丢失太多精度，但速度大大加快

②[泛化性能分析]：在GOSS准确的情况下，GOSS泛化误差近似于全量的真实数据。另一方面，采样将增加基学习器的多样性（因为每次采样获得的数据可能会不同），这将提高泛化性。

Exclusive Feature Bundling(EFB)

互斥的特征捆绑。 EFB可以有效减少特征的数量。

[思想]：高维数据通常是稀疏的，且许多特征是互斥的（range不同），于是我们可以绑定这样的每一组互斥特征为单一特征，通过仔细设计特征扫描算法，我们从特征捆绑中构建了与单个特征相同的特征直方图。这种方式是无损的。我们只需要遍历捆绑后的大特征就可以获取到所有特征的直方图，降低了需要遍历的特征量，加快了计算速度。

[寻找哪些特征可以绑定]： 将最优捆绑问题归结为图着色问题，用边连接非互斥特征，于是未有连接的特征团就是互斥特征，然后用近似的贪婪算法来做特征捆绑。

发现特征不是100%互斥但大部分情况是互斥的。于是设定一个参数$\gamma$，表示每个绑定的最大冲突比率，只要不高于这个阈值就可以绑定。

[怎么绑定/互斥特征如何合并]：我们需要将一组被捆绑的特征能够单独分离出来。于是可以通过为特征值添加偏移量，将特征放在不同的箱中来构建一个捆绑。也就是说将各个特征的range通过添加偏移量的方法，合并后扩展到一个大range。

附上原论文的算法，算法3为贪心寻找绑定，算法4为合并互斥特征：

Leaf-wise (Best-first) Tree Growth

采用Leaf-wise策略建树（下图）

图片来源：LightGBM原理分析

用Leaf-wise可以做到每次从当前所有叶子中，找到分裂增益最大的一个叶子，也就能选取最优增益的建树方法；而level-wise同对待同层所有叶子就可能增益很低。但容易过拟合。Leaf-wise每次分裂可以降低更多偏差，精度更高，但容易过拟合。但可以通过限制树高来防止过拟合。

而且由于GOSS和EFB算法本身就有正则化的效果，所以可以使用Leaf-wise来提升精度

直接支持类别特征

GDBT，XGBoost不直接支持类别特征， 需要把类别特征转化到多维的0/1特征。

而LightGBM直接支持了类别特征，在决策树算法上增加了类别特征的决策规则，具体略

后记

1. 实际上绝大多数树模型在划分结点的时候都是采用贪心算法，只计算当前结点的最优特征和最优划分，否则树模型的可能实在太多，枚举完的代价是巨大的

2. Bagging与Boosting

   用XGBoost/GBDT在在调参的时候把树的最大深度调成6就有很高的精度了。但是用DecisionTree或RandomForest的时候需要把树的深度调到15或更高，why？

   ①随机森林属于Bagging方法，主要降低方差， 使用训练数据的不同子集来训练多个模型。因此它在不剪枝的决策树、神经网络等学习器上效用更为明显。 （dropout就可以视为神经网络的一种bagging）

   ②XGB/GBDT属于Boosting方法，主要降低偏差，是一种迭代方法。因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成；

   Bagging和Boosting都属于集成学习

3. 分割=分裂=划分，这三个词都是描述决策树变成子树的过程，我是混着用的

4. LightGBM只是略读，以后可以更深入了解其理论和复杂度