<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 GBDT(Gradient Boosting Decision Tree) 原理简介
0. 前言
我最开始了解 GBDT 时，死活不理解决策树这种分段函数，怎么可能算出一阶导数。读了论文 Friedman - Greedy Function Approximation
Step1:  2.1 增量寻优
梯度下降法是利用了导数做为步进参考值，它要求函数是已知且可导的。问题是，现实中，有时这个函数是未知的，比如说对应的是一台机器。我不知道怎么对它建模，唯一的信息就是喂它输入，它就会返回输出。那怎么办呢？
首先，我们回到 $\frac{\partial f(x)}{\partial x}$ 来看，因为步进大小还受 $\lambda$ 调控。这里梯度的作用，其实主要是指示步进方向。
然后，我们换个思路找步进方向。
假设机器的真实模型是 $f(x)$，对我们来说它是未知的。尝试如下：
第一次试探，随机给个初始值 $x_0$，得到 $f(x_0)$。
第二次试探，再随机输入 $x_1$，得到 $f(x_1)$。
这时，有如下三种情况，可以指导第三次试探：
$f(x_1) < f(x_0)$，也就是 $x_0 \to x_1$的方向是对的。
$f(x_1) = f(x_0)$，没有有用信息。
$f(x_1) > f(x_0)$，方向反了。
Step2:  因为我们始终是找极小值点，这个过程就始终如上图所示"U"形。那么每次的步进方向就可用 $f(x_1) - f(x_0)$ 来指示。也就是说，虽然我们无法对机器$f(x)$建模，但我们可以对寻优的过程 $z = f(x_i) - f(x_{i+1})$ 建模 $g(z)$。而 $g(z)$ 只要满足单调且过零点，理论上它可以是任意的，不同函数影响的只是收敛速度，但都会收敛到 $w^*$ 附近。
2.2 逼近
再换个角度，我们不再想寻优。而是假设这个极小值$w^$已经知道了，如何从初始值$w_0 = f(x_0)$一步步逼进到这个极小值$w^$。其实可以完全借用上节的增量寻优建模手法，我们定义 $z = f(x_i) - w^*$，从而对逼近过程建模 $g(z)$。
Step3:  同样地，$g(z)$只要满足一定条件的函数。在这里，就是过零点，正数区间单增，负数区间单减，最常见的代表就是二次函数 $g(z) = z^2$。
我们梳理下整个逼近过程，如下图：
<ASSISTANT_TASK:>
Python Code:
show_image("./res/gradient_descent.jpg", figsize=(12,8))
show_image("./res/iterator.jpg")
Explanation: GBDT(Gradient Boosting Decision Tree) 原理简介
0. 前言
我最开始了解 GBDT 时，死活不理解决策树这种分段函数，怎么可能算出一阶导数。读了论文 Friedman - Greedy Function Approximation: A Gradient Boosting Machine 后，才发现自己完全误解了决策树在GBDT中的作用。论文总是倾向把简单事情描述复杂，博客又常常过于简练地只给具体算法。写这篇文章的想法，就是想用自己的理解，既照顾到数学框架，又落实到具体算法实现，把GBDT说清楚。这里可能有谬误，读者应审慎地阅读。
1. Gradient Boosting 与最优化
ref:
机器学习中的算法(1)-决策树模型组合之随机森林与GBDT
在说GBDT前，我们先说下它的俩前缀Gradient Boosting：
Boosting: 这是一种迭代算法，每一次训练都是在前面已有模型的预测基础上进行。   
  最简单地说，先训练一个初始模型，对比真实值和预测值的残差；用残差再训练一个模型，再计算残差；再训练……。这样，每一个模型都专注于修正前面模型最不给力的效果方面。于是，通过这种方式联合多个弱分类器，就能得到一个强分类器。
Gradient: 梯度。对于单个变量来说，就是一阶导数。   
  前面Boosting要计算残差，方法就很多了，你可以直接相减，也可以定义个函数。这里Gradient就是说用梯度来计算残差。
所以说Gradient Boosting是一种算法框架，它是用Grdient计算残差的Boosting过程，而GBDT只是用决策树来训练的一种具体实现。说到这，学习过最优化的童鞋一定会对Gradient Boosting有种强烈的既视感，是的，那就是我们耳熟能详的最速梯度下降法。
所以，我们先从最速梯度下降法作引，一步步走到Gradeint Boosting框架，然后再落到决策树上，最后如果有精力，介绍下进一步的优化TreeBoost。
2. 最速梯度下降法
我简要说下基本思路，详细可见梯度下降法 - 维基百科。
假设有个有界函数 $| f(x) | < M$，我们需要知道它的最小值。日常的例子中，这个函数可能是一项工程所用的花销，一个项目占用的时间，我们想找到损失最小的方案，即：$\operatorname{arg min}_x \, f(x) $。 找到最小解的过程就叫寻优，函数$f(x)$常被称为损失函数。
2.0 理论
梯度下降法是一种数值寻优算法。什么是数值寻优呢？就是现实中$f(x)$很多时候难以用理论求解出最值，或者$f(x)$就是个黑盒子，我们没有办法直接找到最值，只能去有限的数值解中搜索，所以叫数值寻优。
梯度下降法就是按函数梯度来步进到极值点的过程，其数学表达式形如：
\begin{equation}
    x_{m+1} = x_m - \lambda \frac{\partial f(x)}{\partial x}
\end{equation}
具体过程如下图所示，取自可扩展机器学习——梯度下降(Gradient Descent)：
End of explanation
show_image("./res/incr_opt.png", figsize=(10,5))
Explanation: 2.1 增量寻优
梯度下降法是利用了导数做为步进参考值，它要求函数是已知且可导的。问题是，现实中，有时这个函数是未知的，比如说对应的是一台机器。我不知道怎么对它建模，唯一的信息就是喂它输入，它就会返回输出。那怎么办呢？
首先，我们回到 $\frac{\partial f(x)}{\partial x}$ 来看，因为步进大小还受 $\lambda$ 调控。这里梯度的作用，其实主要是指示步进方向。
然后，我们换个思路找步进方向。
假设机器的真实模型是 $f(x)$，对我们来说它是未知的。尝试如下：
第一次试探，随机给个初始值 $x_0$，得到 $f(x_0)$。
第二次试探，再随机输入 $x_1$，得到 $f(x_1)$。
这时，有如下三种情况，可以指导第三次试探：
$f(x_1) < f(x_0)$，也就是 $x_0 \to x_1$的方向是对的。
$f(x_1) = f(x_0)$，没有有用信息。
$f(x_1) > f(x_0)$，方向反了。
End of explanation
show_image("./res/approx.png", figsize=(10,5))
Explanation: 因为我们始终是找极小值点，这个过程就始终如上图所示"U"形。那么每次的步进方向就可用 $f(x_1) - f(x_0)$ 来指示。也就是说，虽然我们无法对机器$f(x)$建模，但我们可以对寻优的过程 $z = f(x_i) - f(x_{i+1})$ 建模 $g(z)$。而 $g(z)$ 只要满足单调且过零点，理论上它可以是任意的，不同函数影响的只是收敛速度，但都会收敛到 $w^*$ 附近。
2.2 逼近
再换个角度，我们不再想寻优。而是假设这个极小值$w^$已经知道了，如何从初始值$w_0 = f(x_0)$一步步逼进到这个极小值$w^$。其实可以完全借用上节的增量寻优建模手法，我们定义 $z = f(x_i) - w^*$，从而对逼近过程建模 $g(z)$。
End of explanation
show_image("./res/model.png", figsize=(10,5))
Explanation: 同样地，$g(z)$只要满足一定条件的函数。在这里，就是过零点，正数区间单增，负数区间单减，最常见的代表就是二次函数 $g(z) = z^2$。
我们梳理下整个逼近过程，如下图：
End of explanation
<END_TASK>