梯度提升机：贪婪函数逼近法

gbdt

需积分: 29 183 浏览量更新于2023-05-24 收藏 950KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

"GREEDY FUNCTION APPROXIMATION: A GRADIENT BOOSTING MACHINE" 这篇文章主要探讨了一种称为“贪婪函数逼近”的机器学习方法——梯度提升机（Gradient Boosting Machine, GBDT）。作者Jerome H. Friedman是斯坦福大学的教授，他在1999年的Reitz讲座中提出了这个概念。文章发表在2001年《统计学年鉴》第29卷第5期，页码为1189–1232。传统的函数估计或近似通常是在参数空间中进行的，而Friedman提出了一种新的视角，即在函数空间中进行数值优化。他将逐次增加的展开方式与最陡下降法（steepest-descent minimization）建立了联系，这是一种在函数空间中的优化策略。文章阐述了一个基于任何拟合标准的通用梯度下降“提升”范式，用于构建累加展开模型。具体来说，Friedman提出了针对最小二乘法、最小绝对偏差和Huber损失函数的回归问题，以及多元逻辑似然函数的分类问题的算法。这些算法能够逐步增强模型的性能。特别是当个体累加组件是决策树（regression trees）时，他发展了特定的增强策略，这种“TreeBoost”模型具有高度的解释性，并且对于不那么干净的数据，其表现尤为出色。梯度提升决策树（Gradient Boosting of Regression Trees, GBRT）结合了预测精度、鲁棒性和可解释性，适用于回归和分类问题。这种方法不仅提供了一种强大的学习机制，还揭示了它与其他机器学习方法，如AdaBoost，之间的联系。通过组合弱预测器（如简单的决策树）并迭代地优化它们的组合，GBDT能够构建出强大的预测模型，尤其在处理有噪声、缺失值或非线性关系的数据时，表现突出。 "GREEDY FUNCTION APPROXIMATION: A GRADIENT BOOSTING MACHINE"是一篇深入研究梯度提升技术的论文，它推动了机器学习领域的发展，尤其是决策树集成方法的广泛应用。这种方法现在已经成为现代机器学习工具箱中不可或缺的一部分，广泛应用于各种实际问题，如信用评分、医学诊断和推荐系统等。

资源详情

资源推荐

1196 J. H. FRIEDMAN

The update (16) can be alternatively expressed as

x=F

m−1

x+



j=1

1x ∈ R

(17)

with γ

= ρ

. One can view (17) as adding J separate basis functions

at each step 1x ∈ R



, instead of a single additive one as in (16). Thus,

in this case one can further improve the quality of the ﬁt by using the opti-

mal coefﬁcients for each of these separate basis functions (17). These optimal

coefﬁcients are the solution to

γ



= arg min

γ





i=1



F

m−1

x

+



j=1

1x ∈ R







Owing to the disjoint nature of the regions produced by regression trees, this

reduces to

= arg min



∈R

Ly

F

m−1

x

+γ(18)

This is just the optimal constant update in each terminal node region, based

on the loss function L, given the current approximation F

m−1

x.

For the case of LAD regression (18) becomes

= median

∈R

y

− F

m−1

x



which is simply the median of the current residuals in the jth terminal node at

the mth iteration. At each iteration a regression tree is built to best predict the

sign of the current residuals y

−F

m−1

x

, based on a least-squares criterion.

Then the approximation is updated by adding the median of the residuals in

each of the derived terminal nodes.

Algorithm 3 (LAD

TreeBoost).

x=mediany



For m = 1toM do:

˜y

= signy

− F

m−1

x

i= 1N

R



= J-terminal node tree ˜y

 x





= median

∈R

y

− F

m−1

x

j= 1J

x=F

m−1

x+



j=1

1x ∈ R



endFor

end Algorithm

This algorithm is highly robust. The trees use only order information on

the individual input variables x

, and the pseudoresponses ˜y

(13) have only

two values, ˜y

∈−1 1. The terminal node updates are based on medians.

GREEDY FUNCTION APPROXIMATION 1197

An alternative approach would be to build a tree to directly minimize the loss

criterion,

tree

x=arg min

J-node tree



i=1

y

− F

m−1

x

−treex



x=F

m−1

x

+tree

x

However, Algorithm 3 is much faster since it uses least-squares to induce the

trees. Squared-error loss is much more rapidly updated than mean absolute

deviation when searching for splits during the tree building process.

4.4. M-Regression. M-regression techniques attempt resistance to long-

tailed error distributions and outliers while maintaining high efﬁciency for

normally distributed errors. We consider the Huber loss function [Huber

(1964)]

Ly F=



y − F

 y − F≤δ

δy − F−δ/2y − F >δ.

(19)

Here the pseudoresponse is

˜y

=−



∂Ly

Fx



∂Fx



Fx=F

m−1

x



− F

m−1

x

 y

− F

m−1

x

 ≤ δ,

δ · signy

− F

m−1

x

 y

− F

m−1

x

 >δ,

and the line search becomes

= arg min



i=1

Ly

F

m−1

x

+ρhx

 a

(20)

with L given by (19). The solution to (19), (20) can be obtained by standard

iterative methods [see Huber (1964)].

The value of the transition point δ deﬁnes those residual values that are

considered to be “outliers,” subject to absolute rather than squared-error loss.

An optimal value will depend on the distribution of y − F

∗

x, where F

∗

the true target function (1). A common practice is to choose the value of δ to

be the α-quantile of the distribution of y − F

∗

x, where 1 − α controls the

breakdown point of the procedure. The “breakdown point” is the fraction of

observations that can be arbitrarily modiﬁed without seriously degrading the

quality of the result. Since F

∗

x is unknown one uses the current estimate

m−1

x as an approximation at the mth iteration. The distribution of y −

m−1

x is estimated by the current residuals, leading to

= quantile

y

− F

m−1

x





With regression trees as base learners we use the strategy of Section 4.3,

that is, a separate update (18) in each terminal node R

. For the Huber loss

剩余43页未读，继续阅读

xjtucyzhb

粉丝: 0
资源: 1

会员权益专享

梯度提升机：贪婪函数逼近法

A Gradient Boosting Machine

Greedy function approximation - A gradient boosting machine (1).pdf

GREEDY FUNCTION APPROXIMATION- A GRADING BOOSTING MACHINE.pdf

Greedy Function Approximation A Gradient Boosting Machine.pdf

A Gentle Introduction to Gradient Boosting

greedy function approximation:a gradient boosting machine

GBDT算法近五年参考文献

基于XGboost的优化算法

wenet测试结果test_attention、test_attention_rescoring、test_ctc_greedy_search、test_ctc_prefix_beam_search分别表示什么

implement the UCB algorithm and plot the expected regret as a function of 𝑇 using 1000 sample path simulations with python and Compare this with the greedy algorithm, Total number of periods 𝑇 = 2000, Price choices 𝑝 = 0,1,2,3, … ,19, reward = 10 − 0.5𝑝 + 𝜖, 𝜖~𝑁(0, 0.04)

用julia写一个，贪心算法

python:greedy_algorithm

ε-greedy策略实现深度强化学习代码

Suppose there are five feature A, B,C, D, E with constraints B , 3,C , 2, A , B, B , C,C < D, A = D, E < A, E < B, E < C, E < D, B , D Define the loss function as val({A = a, . . . , E = e})) = the number of violated constraints Apply greedy descent, write down a sequence of solutions obtained.

matlab中的ε-greedy

会员权益专享

最新资源