# Gradient Descent and Gradient Boosting

ML里的很多问题都可以简化为求解优化问题，让loss function最小的 $$\hat{\theta}=\underset{\theta}{\arg \min } L(\theta)$$ 。

简单的model中L可以直接求解得到，但是对于参数多的L，求解过程困难。因为实际的loss function多是连续、可导的，那就有了gradient descent求解的思路。

Step 1: Take the derivative (gradient) of the loss function for each parameter in it. \
Step 2: Pick random values for the parameters.\
Step 3: Plug the parameter values into the derivatives(gradient)\
Step 4: Calculate the step sizes, step size = slope\*learning\_rate\
Step 5: Calculate the new parameter: new parameter = old parameter-step size\
Back to Step 3 until Step\_Size=small, or reach the maximum number of steps

$$
\begin{array}{l}{\text { 1: } \theta \leftarrow \theta\_{0}} \ {\text { 2: while } \nabla L(\theta)>\epsilon \text { do }} \ {\text { 3: } \quad \theta \leftarrow \theta-\alpha \cdot \nabla L(\theta)} \ {\text { 4: return } \theta}\end{array}
$$

$$\epsilon$$ 是tolerance，很小的数值（1e-6）， $$\alpha$$ 是learning rate。

use gradient to descent to the lowest point in the loss function (sum of the squared residuals); gradient descent can be very sensitive to the learning rate 

{% hint style="info" %}
基于导数的优化问题（不只是gradient descent）都要求提前做好standardization 
{% endhint %}

## 实现Gradient Descent

```python
import numpy as np

#gradient descent
def gd(theta0, L, D, alpha, epsilon):
    theta = theta0
    it=0
    while True:
        it+=1
        l=L(theta)
        d=D(theta)
        if np.linalg.norm(d) < epsilon: #eucladian distance
            return theta
        theta-=alpha*d
        if (it%100)==0:
            print(f'{it}, theta: {theta}, l:{l}')

#Test Case L(x,y) = (x-3)**2 + (y-9)**2
ret = gd(
theta0=np.array([10.0, 20.0]),
L = lambda a:(a[0]-3)**2+(a[1]-9)**2,
D = lambda x: np.array([2*(x[0]-3), 2*(x[1]-9)]),
alpha = 1e-2,
epsilon = 1e-7
)

print(ret)
```

## Stochastic Gradient Descent &#x20;

从上面的过程可以看出，如果要实现一次gradient descent，需要load进去所有的x。如果我们只load部分的dataset，每次换不同的batch去算derivative，这个时候我们叫它out of core learning 在sklearn就是partial\_fit&#x20;

## Gradient Boosting&#x20;

### 从general的boosting vs bagging说起

![](https://492391472-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LiBoWdc5sh0EFrazIOe%2F-Lo7Rl4Oyp64-8sp621G%2F-Lo7YNpPIDca5a-hRyhO%2Fimage.png?alt=media\&token=467bb8fb-08ea-4e8f-bdf6-3e3fe1be3bfe)

Bagging: independent classifier并行运算，一群high variance, low bias的model，用一些avg的技巧得到最后的结果（因为low bias，所以大家犯不同的错误取平均后应该得到一个真实值），比如weighted average, majority vote, normal average  最后的结果是reduce variance，variance变成了原来的1/N。

Boosting: sequential classifiers串行运算，可以理解成 精英教育，不停培养同一个model，让这个model的error最小。每一个model都在学习在此之前每一个model的mistake。Boosting的问题在于我们需要设置一个stop time or iteration time，因为它有overfitting的问题。

### Gradient Boosting

我们此前的想法都是given x，predict y。y本身有一个predicted value, 也有一个true value. 现在转变一下想法，我们还有一个叫做residual的参数 $$r\_{j, i}$$ ， residual of $$f\_{j}$$ on data i.

$$r\_{0, i} \leftarrow y\_{i}-f\_{0}\left(x\_{i}\right)$$&#x20;

已知 $$x\_{i}$$ ，预测每个$$r\_{j, i}$$ , $$f 1 : x\_{i} \rightarrow r\_{0, i}$$ , 用预测结果改进 $$f\_{0}$$.

$$
\begin{array}{l}{\text { }} \ {\text{ 1: } f\_{0} : x \rightarrow 0 } \ {\text { 2: } f \leftarrow f\_{0}} \ {\text { 3: } i \leftarrow 1}  \ {\text { 4: while } i\<T \text { do }} \ {\text { 5: } e\_{i} \leftarrow y\_{i}-f\left(x\_{i}\right)} \ {\text { 6: } \text { fit } f\_{i} \text { using }\left{\<x\_{i}, e\_{i}>\right}} \ {\text { 7: } f(x) \leftarrow f(x)+f\_{i}(x)} \ {\text { 8: } \text { i } \leftarrow i+1} \ {\text { 9: return } f}\end{array}
$$

其实，MSE是 $$L=\sum\_{i}\left(y\_{i}-\hat{y\_{i}}\right)^{2}$$ , 而 $$\frac{d L}{d \hat{y\_{i}}}=2\left(y\_{i}-\hat{y\_{i}}\right) = 2\times residual$$&#x20;

$$
\begin{array}{l}{\text { 1: } f \leftarrow f\_{0}} \ {\text { 2: } i \leftarrow 1} \ {\text { 3: while } i\<T \text { do }} \ {\text { 4: }  e\_{i} \leftarrow \nabla L(f)} \ {\text { 5: } \text { fit } f\_{i} \text { using }\left{\<x\_{i}, e\_{i}>\right}} \ {\text { 6: } f(x) \leftarrow f(x)-\alpha\_{i} \cdot f\_{i}(x)} \ {\text { 7: } i \leftarrow i+1} \ {\text { 8: return } f}\end{array}
$$

所以 Boosting 有三个要素：

A loss function to be optimized

A weak learner to make predictions. eg. Tree model

An additive model： 将多个弱学习器累加起来组成强学习器，进而使目标损失函数达到极小。&#x20;

之所以称为 Gradient，是因为在添加新模型时使用了梯度下降算法来最小化的损失

## Adaboost&#x20;

用exponential loss的gradient boosting

1. 让所有的weight都一样，可以是1/N或者是1
2. 让dependent variable变成Y={-1,1} 因为在后期公式里是看正负号判断data的positive/negative
3. 增加错误部分的weights

{% embed url="<http://www.robots.ox.ac.uk/~az/lectures/cv/adaboost_matas.pdf>" %}

## 其它

{% embed url="<https://zhuanlan.zhihu.com/p/43506482>" %}