littlebeandog/EL

## EL

# 集成学习


- 将若干仅仅略好于随机模型的**弱模型**结合为**强模型**

- 集成学习的思想最早是在**1980**年被提出的


-----

## 三种思想

- bagging

> 从原始训练集抽样形成**子训练集**合，基于子训练集产生基模型（base model）并进行集成

![enter image description here](https://lh3.googleusercontent.com/9nNu6rp2V6ZOkLPeSxkih2XbfeXuihtzt35o7d3eRYL-sEwKK87auKNM7DuJWXDJbgcwAGY=s0 "bagging_code.png")


- stacking

> 一级模型的预测值作为新的训练集.元模型（meta data）将上述一基模型组合起来。`第j个基模型对第i个样本的训练结果作为新训练集中第i个样本的第j个特征`

![enter image description here](https://lh3.googleusercontent.com/5Fpq7uaHUz_7wz8ILZjy59G-LqBvtD2n2Vt9KQuHKKRTTVIlOTrK36whffXMp8_8ARkbU5U=s0 "stacking_code.png")

- boosting

> 基于上一轮训练结果对下一轮的训练策略进行调整
> 以Adaboost为例

![enter image description here](https://lh3.googleusercontent.com/qBw597dLtBMlPFfwEb3gVNVuCIvtde81ZnJ4r2WxlsZ7lIIe8mo_MCvxSk4lhjJVhhfcXPI=s0 "adaboost.png")

- 提升树(Boosting Tree):以决策树为基函数,每一轮对上一轮迭代的**残差**进行训练
$$r_m=y_i-f_{m-1}(x_i)$$
- 梯度提升树(GBDT):损失函数的**负梯度**作为提升树中残差的近似值
$$-[\frac{\partial L(y,f(x_i)}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$$

-------

## 偏差与方差

- 偏差（bias）：预测值的期望和真实值之间的差距。
- 方差：预测值的离散程度

![enter image description here](https://lh3.googleusercontent.com/zRfL6eIX874DTyNca-j-LjoTQ-wTOH3gwPaZf2Jqi9UsJeLC3wVd0jO7ocm1gYrqL08E5Nk=s0 "bias1.png")

#### 在机器学习中的意义

- Error = Bias + Variance
- 偏差：偏差越大，越偏离真实数据。
- 方差：[表征过拟合的风险][2]

```
一次打靶实验，目标是为了打到10环，但是实际上只打到了7环，那么这里面的Error就是3。具体分析打到7环的原因，可能有两方面：一是瞄准出了问题，比如实际上射击瞄准的是9环而不是10环；二是枪本身的稳定性有问题，虽然瞄准的是9环，但是只打到了7环。那么在上面一次射击实验中，Bias就是1,反应的是模型期望与真实目标的差距，而在这次试验中，由于Variance所带来的误差就是2，即虽然瞄准的是9环，但由于本身模型缺乏稳定性，造成了实际结果与模型期望之间的差距。

弱模型：偏差高（精度低）方差小（过拟合风险小）
```


![enter image description here](https://lh3.googleusercontent.com/eIF5z8HbBJ3WPoAdzf-4-DU7Dx_vjbgVgrcVSBbHSnVTa90EX5910CeyK7Hyo0Pxe7Nk8D0=s0 "trade-off.png")

#### boosting 与 bagging 的区别

- bagging：不降低偏差，降低方差
> 各个模型样本近似同分布，所以不会显著降低bias
> 若各个模型完全独立:
> $$Var(\sum X_i/n)=Var(X_i)/n$$
> 若各个模型完全相同
> $$Var(\sum X_i/n)=Var(X_i)$$
> 实际的子模型基于上述极端的中间态

- boosting：降低偏差，不降低方差
> boosting每一步都是基于上一步，迭代的最小化损失函数，每一轮迭代的模型之间强相关。

--------

## XGBoost的原理

#### 目标函数优化

用$\theta$代表模型参数，XGboost目标函数如下：
$$Obj(\Theta)=L(\theta) + \Omega(\Theta)$$
其中$L(\theta)$为损失函数，**$\Omega(\Theta)$为正则项**.
定义第$t$次迭代后的预测值为$\hat y_i^{(t)}$,预测函数为$f_t(x)$:
$$\hat y_i^{(0)}=0\\
\hat y_i^{(1)}=f_1(x_i)=\hat y_i^{(0)}+f_1(x_i)\\
\hat y_i^{(2)}=f_1(x_i)+f_2(x_i)=\hat y_i^{(1)}+f_2(x_i)\\
...\\
\hat y_i^{(t)}=\sum_{k=1}^tf_k(x_i)=\hat y_i^{(t-1)}+f_t(x_i)$$
对于第t次迭代生成的树，目标函数为：
$$\begin{eqnarray*}
obj^{(t)}&=&\sum_{i=1}^nl(y_i,\hat y_i)+\sum_{i=1}^t\Omega(f_i)\\
& = &\sum_{i=1}^nl(y_i,\hat y_i^{(t-1)}+f_t(x_i))+\Omega(f_t)+constant
\end{eqnarray*}$$
以MSE损失函数为例，上述目标函数转化为：
$$\begin{eqnarray*}
obj^{(t)}&=&\sum_{i=1}^n(y_i-(\hat y_i^{(t-1)}+f_t(x_i)))^2+\sum_{i=1}^t\Omega(f_i)\\
& = &\sum_{i=1}^n[2(\hat y_i^{(t-1)}-y_i)f_t(x_i)+f_t(x_i)^2]+\Omega(f_t)+constant
\end{eqnarray*}$$
根据二次泰勒级数：
$$f(x)=f(x_0)+f'(x)(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2$$
将上述目标函数近似为：
$$obj^{(t)}=\sum_{i=1}^n[l(y_i,\hat y_i^{(t-1)})+g_if_t(x_i)+\frac12h_if_t^2(x_i)]+\Omega(f_t)+constant$$
其中$g_i$和$h_i$分别为：
$$g_i=\partial_{\hat y_i^{(t-1)}}l(y_i,y_i^{(t-1)})\\
h_i=\partial^2_{\hat y_i^{(t-1)}}l(y_i,y_i^{(t-1)})$$
移除常数项，则在第t轮迭代的目标函数为：
$$\sum_{i=1}^ng_if_t(x_i)+\frac12h_if_t^2(x_i)]+\Omega(f_t)$$

**因此,XGboost支持自定义任何可以二阶导的损失函数**

#### 模型复杂度

boosting算法中的variance问题

以另一种形式来定义第t次迭代所得到的树
$$f_t(x)=\omega_{q(x)},\omega\in R^T,q:R^d \rightarrow \{1,2,...,T\}$$
$\omega$代表叶子分数的向量，$q$代表代表树结构，$T$代表叶子的数量。
在XGBoost中，模型复杂度定义为：
$$\Omega(f)=\gamma T + \frac12\lambda\sum_{j=1}^T\omega_j^2$$
**这是一个经验公式**，具体计算的例子如下：

![enter image description here](https://lh3.googleusercontent.com/t37Dwgie6GqZTaahLNj43e36CNuS4K6RwnAGvxpQAcoidNvWO5Fq75Dq51CYZ3TezTpml8Y=s0 "complexity.png")

#### 结构分数（Structure Score）
根据**目标函数**和**模型复杂度**中的推导，第t棵树的目标函数可以写为如下形式：
$$\begin{eqnarray*}
obj^{(t)}&=&\sum_{i=1}^n[g_i\omega_{q(x_i)}+\frac12h_i\omega_{q(x_i)}]+\Omega(f_t)]+\gamma T + \frac12\lambda\sum_{j=1}^T\omega_j^2\\
&=&\sum_{j=1}^T[(\sum_{i\in I_j}g_i)w_j+\frac12(\sum_{i\in l_j}h_i+\lambda)\omega^2_j]+\gamma T
\end{eqnarray*}$$
其中$I_j=\{i|q(x_i)=j\}$，定义$G_j=\sum_{i\in I_j}g_i$,$H_j=\sum_{i\in I_j}h_i$:
上式化简为：
$$obj^{(t)}=\sum_{j=1}^T[G_j\omega_j+\frac12(H_j+\lambda)\omega_j^2] + \gamma T$$
上式中的$\omega_j$是相互独立的，对于给定的树结构`即确定的q(x)`,对$\omega_j$求导得：
$$\omega_j^*=-G_j/(H_j+\lambda)\\
obj^*=-\frac12\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda} + \gamma T$$
这个分数**越小**，代表这个树的结构**越好**。

![enter image description here](https://lh3.googleusercontent.com/VhAxvrorn9ChMzU483y3drV195rrAJccSamd_VoaNqP7mQmtw7lfCy-ihrItrRyN0cZpYb8=s0 "structure_score.png")

#### 树的分割

当分割一个叶子节点时，增加的分数为
$$Gain=\frac12[\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}]$$

上式包含4个部分：

- 左叶子得分
- 右叶子得分
- 原始叶子得分
- 加入新节点的复杂度代价

相比于枚举所有的分割，将所有样本排序并从左至右扫描就可以得到所有可能的分割的结构分数。

**解决决策树中开销最大的特征分隔**
**特征粒度的并行**

![enter image description here](https://lh3.googleusercontent.com/Mf_5aA9yithhGBe02P5mqOomV-1QIAHjbH7VGyvxNrqf9qHy6mLzE0M4yc9-xhs3nHQsw4M=s0 "tree_structure.png")


--------

[2]:http://scott.fortmann-roe.com/docs/BiasVariance.html

	# 集成学习


	- 将若干仅仅略好于随机模型的弱模型结合为强模型

	- 集成学习的思想最早是在1980年被提出的


	-----

	## 三种思想

	- bagging

	> 从原始训练集抽样形成子训练集合，基于子训练集产生基模型（base model）并进行集成

	![enter image description here](https://lh3.googleusercontent.com/9nNu6rp2V6ZOkLPeSxkih2XbfeXuihtzt35o7d3eRYL-sEwKK87auKNM7DuJWXDJbgcwAGY=s0 "bagging_code.png")


	- stacking

	> 一级模型的预测值作为新的训练集.元模型（meta data）将上述一基模型组合起来。`第j个基模型对第i个样本的训练结果作为新训练集中第i个样本的第j个特征`

	![enter image description here](https://lh3.googleusercontent.com/5Fpq7uaHUz_7wz8ILZjy59G-LqBvtD2n2Vt9KQuHKKRTTVIlOTrK36whffXMp8_8ARkbU5U=s0 "stacking_code.png")

	- boosting

	> 基于上一轮训练结果对下一轮的训练策略进行调整
	> 以Adaboost为例

	![enter image description here](https://lh3.googleusercontent.com/qBw597dLtBMlPFfwEb3gVNVuCIvtde81ZnJ4r2WxlsZ7lIIe8mo_MCvxSk4lhjJVhhfcXPI=s0 "adaboost.png")

	- 提升树(Boosting Tree):以决策树为基函数,每一轮对上一轮迭代的残差进行训练
	$$r_m=y_i-f_{m-1}(x_i)$$
	- 梯度提升树(GBDT):损失函数的负梯度作为提升树中残差的近似值
	$$-[\frac{\partial L(y,f(x_i)}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$$

	-------

	## 偏差与方差

	- 偏差（bias）：预测值的期望和真实值之间的差距。
	- 方差：预测值的离散程度

	![enter image description here](https://lh3.googleusercontent.com/zRfL6eIX874DTyNca-j-LjoTQ-wTOH3gwPaZf2Jqi9UsJeLC3wVd0jO7ocm1gYrqL08E5Nk=s0 "bias1.png")

	#### 在机器学习中的意义

	- Error = Bias + Variance
	- 偏差：偏差越大，越偏离真实数据。
	- 方差：[表征过拟合的风险][2]

	```
	一次打靶实验，目标是为了打到10环，但是实际上只打到了7环，那么这里面的Error就是3。具体分析打到7环的原因，可能有两方面：一是瞄准出了问题，比如实际上射击瞄准的是9环而不是10环；二是枪本身的稳定性有问题，虽然瞄准的是9环，但是只打到了7环。那么在上面一次射击实验中，Bias就是1,反应的是模型期望与真实目标的差距，而在这次试验中，由于Variance所带来的误差就是2，即虽然瞄准的是9环，但由于本身模型缺乏稳定性，造成了实际结果与模型期望之间的差距。

	弱模型：偏差高（精度低）方差小（过拟合风险小）
	```


	![enter image description here](https://lh3.googleusercontent.com/eIF5z8HbBJ3WPoAdzf-4-DU7Dx_vjbgVgrcVSBbHSnVTa90EX5910CeyK7Hyo0Pxe7Nk8D0=s0 "trade-off.png")

	#### boosting 与 bagging 的区别

	- bagging：不降低偏差，降低方差
	> 各个模型样本近似同分布，所以不会显著降低bias
	> 若各个模型完全独立:
	> $$Var(\sum X_i/n)=Var(X_i)/n$$
	> 若各个模型完全相同
	> $$Var(\sum X_i/n)=Var(X_i)$$
	> 实际的子模型基于上述极端的中间态

	- boosting：降低偏差，不降低方差
	> boosting每一步都是基于上一步，迭代的最小化损失函数，每一轮迭代的模型之间强相关。

	--------

	## XGBoost的原理

	#### 目标函数优化

	用$\theta$代表模型参数，XGboost目标函数如下：
	$$Obj(\Theta)=L(\theta) + \Omega(\Theta)$$
	其中$L(\theta)$为损失函数，$\Omega(\Theta)$为正则项.
	定义第$t$次迭代后的预测值为$\hat y_i^{(t)}$,预测函数为$f_t(x)$:
	$$\hat y_i^{(0)}=0\\
	\hat y_i^{(1)}=f_1(x_i)=\hat y_i^{(0)}+f_1(x_i)\\
	\hat y_i^{(2)}=f_1(x_i)+f_2(x_i)=\hat y_i^{(1)}+f_2(x_i)\\
	...\\
	\hat y_i^{(t)}=\sum_{k=1}^tf_k(x_i)=\hat y_i^{(t-1)}+f_t(x_i)$$
	对于第t次迭代生成的树，目标函数为：
	$$\begin{eqnarray*}
	obj^{(t)}&=&\sum_{i=1}^nl(y_i,\hat y_i)+\sum_{i=1}^t\Omega(f_i)\\
	& = &\sum_{i=1}^nl(y_i,\hat y_i^{(t-1)}+f_t(x_i))+\Omega(f_t)+constant
	\end{eqnarray*}$$
	以MSE损失函数为例，上述目标函数转化为：
	$$\begin{eqnarray*}
	obj^{(t)}&=&\sum_{i=1}^n(y_i-(\hat y_i^{(t-1)}+f_t(x_i)))^2+\sum_{i=1}^t\Omega(f_i)\\
	& = &\sum_{i=1}^n[2(\hat y_i^{(t-1)}-y_i)f_t(x_i)+f_t(x_i)^2]+\Omega(f_t)+constant
	\end{eqnarray*}$$
	根据二次泰勒级数：
	$$f(x)=f(x_0)+f'(x)(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2$$
	将上述目标函数近似为：
	$$obj^{(t)}=\sum_{i=1}^n[l(y_i,\hat y_i^{(t-1)})+g_if_t(x_i)+\frac12h_if_t^2(x_i)]+\Omega(f_t)+constant$$
	其中$g_i$和$h_i$分别为：
	$$g_i=\partial_{\hat y_i^{(t-1)}}l(y_i,y_i^{(t-1)})\\
	h_i=\partial^2_{\hat y_i^{(t-1)}}l(y_i,y_i^{(t-1)})$$
	移除常数项，则在第t轮迭代的目标函数为：
	$$\sum_{i=1}^ng_if_t(x_i)+\frac12h_if_t^2(x_i)]+\Omega(f_t)$$

	因此,XGboost支持自定义任何可以二阶导的损失函数

	#### 模型复杂度

	boosting算法中的variance问题

	以另一种形式来定义第t次迭代所得到的树
	$$f_t(x)=\omega_{q(x)},\omega\in R^T,q:R^d \rightarrow \{1,2,...,T\}$$
	$\omega$代表叶子分数的向量，$q$代表代表树结构，$T$代表叶子的数量。
	在XGBoost中，模型复杂度定义为：
	$$\Omega(f)=\gamma T + \frac12\lambda\sum_{j=1}^T\omega_j^2$$
	这是一个经验公式，具体计算的例子如下：

	![enter image description here](https://lh3.googleusercontent.com/t37Dwgie6GqZTaahLNj43e36CNuS4K6RwnAGvxpQAcoidNvWO5Fq75Dq51CYZ3TezTpml8Y=s0 "complexity.png")

	#### 结构分数（Structure Score）
	根据目标函数和模型复杂度中的推导，第t棵树的目标函数可以写为如下形式：
	$$\begin{eqnarray*}
	obj^{(t)}&=&\sum_{i=1}^n[g_i\omega_{q(x_i)}+\frac12h_i\omega_{q(x_i)}]+\Omega(f_t)]+\gamma T + \frac12\lambda\sum_{j=1}^T\omega_j^2\\
	&=&\sum_{j=1}^T[(\sum_{i\in I_j}g_i)w_j+\frac12(\sum_{i\in l_j}h_i+\lambda)\omega^2_j]+\gamma T
	\end{eqnarray*}$$
	其中$I_j=\{i\|q(x_i)=j\}$，定义$G_j=\sum_{i\in I_j}g_i$,$H_j=\sum_{i\in I_j}h_i$:
	上式化简为：
	$$obj^{(t)}=\sum_{j=1}^T[G_j\omega_j+\frac12(H_j+\lambda)\omega_j^2] + \gamma T$$
	上式中的$\omega_j$是相互独立的，对于给定的树结构`即确定的q(x)`,对$\omega_j$求导得：
	$$\omega_j^*=-G_j/(H_j+\lambda)\\
	obj^*=-\frac12\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda} + \gamma T$$
	这个分数越小，代表这个树的结构越好。

	![enter image description here](https://lh3.googleusercontent.com/VhAxvrorn9ChMzU483y3drV195rrAJccSamd_VoaNqP7mQmtw7lfCy-ihrItrRyN0cZpYb8=s0 "structure_score.png")

	#### 树的分割

	当分割一个叶子节点时，增加的分数为
	$$Gain=\frac12[\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}]$$

	上式包含4个部分：

	- 左叶子得分
	- 右叶子得分
	- 原始叶子得分
	- 加入新节点的复杂度代价

	相比于枚举所有的分割，将所有样本排序并从左至右扫描就可以得到所有可能的分割的结构分数。

	解决决策树中开销最大的特征分隔
	特征粒度的并行

	![enter image description here](https://lh3.googleusercontent.com/Mf_5aA9yithhGBe02P5mqOomV-1QIAHjbH7VGyvxNrqf9qHy6mLzE0M4yc9-xhs3nHQsw4M=s0 "tree_structure.png")


	--------

	[2]:http://scott.fortmann-roe.com/docs/BiasVariance.html