注：上接GBDT和XGBOOST算法推导和流程详解(PART-1)

XGBOOST算法原理及相应流程

XGBOOST相比GBDT有以下有点和改进:

1）分布式-特征切分

2）稀疏感知-缺失值直接当做特征处理

3）加权分位点进行-树构建节点分割

4）泰勒二阶导数-Newtons Methods更新方法

5）防止过拟合的方法-正则+shrinkage+subsampling

6）系统设计上更加优化

基本原理

XGBOOST-Extreme Gradient Boosting，从名字就可以看出，它利用了梯度提升的思想，但是做的更加极致，这个是因为它使用了Newton法进行更新每棵树（泰勒二阶展开）。

XGBOOST算法的流程为：

//#XGBOOST算法流程

第一步：确定损失函数，泰勒二阶展开，求解最优树权重，继而求出最优树结构和分裂标准函数。

第二步：按照分裂函数逐步一棵树一棵树去生成，值的注意的是，生成的每棵树是利用Newton法迭代的。

第三步：将每棵树进行累加，作为最终生成的数（损失最小，达到最优）。

算法结束

写在前面

泰勒公式

泰勒公式是一个用函数在某点的信息描述其附近取值的公式。

基本形式为：

$$f(x) = \sum_{n=0}^n\frac{f^n(x_0)}{n!}(x-x_0)^n \tag{1}$$

以上是泰勒公式的基本定义和基本形式。

泰勒的一阶展开为：

$$\begin{align} &导数定义：\frac{f(x)-f(x_0)}{x-x_0}=f^\prime(x) \to f(x) = f(x_0)+f^\prime(x)(x-x_0) \tag{2}\\ &导数定义另一形式： \frac{f(x+\triangle x)-f(x)}{\triangle x} = f^\prime(x) \to f(x+\triangle x) = f(x)+\triangle xf^\prime(x) \tag{3}\\ &一阶泰勒展开：f(x) = f(x_0)+f^\prime(x)(x-x_0) 或 f(x+\triangle x)=f(x)+\triangle xf^\prime(x) \tag{4} \\ &二阶泰勒展开为：f(x)=f(x_0)+f^\prime(x)(x-x_0)+\frac{1}{2}f^{''}(x)(x-x_0)或\nonumber \\ &f(x+\triangle x) = f(x)+\triangle x f^\prime(x)+ \frac{1}{2} \triangle x^2 f^{''}(x) \tag{5} \end{align}$$

以上可知，导数和泰勒公式是有关系的,因此可以从导数的角度去记忆泰勒公式。

不管是是GBDT还是XGBOOST，只要是base learners到strong learners都会用到这个思想，其迭代的形式可为：

$$\begin{align} 假设：x^t &= x^{t-1}+\triangle x \nonumber \\ 则有：L(x^t) &= L(x^{t-1}+\triangle x)\nonumber \\ &=L(x^{t-1})+\triangle x L^\prime(x^{t-1}) + \frac{1}{2}\triangle xL^{''}(x^{t-1}) \tag{6} \end{align}$$

只不过GBDT用的是一阶，XGBOOST为二阶。

LR+GBDT二分类和多分类梯度计算和更新过程

梯度推导

SIGMOID 函数分类(LR+GBDT)

sigmoid函数通常将结果映射到[0,1]之间，先推导通过后向传播求其梯度，假设非映射结果为（$F_m(x)$）：

$$\begin {align} Sigmoid映射：h(x;\theta) &= \frac{1}{1+e^{-F_m(x)}} \tag{1} \\ 损失函数：Loss(y,\hat y) &= -\sum_{i=0}^1y_ilog\hat y_i \nonumber\\ &=-[y_ilog h_i+(1-y_i)log(1-h_i)]\tag{2} \\ \end {align}$$

应该注意的是$\hat y$是预测结果，并且$\hat y = h(x;\theta)$，交叉熵作为损失函数是为了评估实际值（标签）$y_i$与预测值的相似程度。先求其梯度，且暂时不考虑使用什么函数拟合。

$$\begin{align} 一般形式（拟合函数F_m(x)）：g_t &= \frac{\partial Loss(y,\hat y)}{\partial F_m(x)} \nonumber \\ &=(h(x;\theta)-y_i) \tag{3} \end{align}$$

求一阶导数的时候不需要一下把所有的的函数都代入，这样会比较复杂，链式求导一般会较少计算错误率。上式若拟合函数是多元线性组合形式，则为LR的梯度求导过程，只需要代入$F_m(x) = w^Tx$:

$$\begin{align} g_t &= (h(x;\theta)-y_i)\frac{\partial F_m(x)}{\partial w_i} \nonumber\\ & = (\hat y_i-y_i)x_i \tag{4} \end{align}$$

LR采用梯度下降时，更新方法为：

LR更新方法-梯度下降法

第一步：初始化$[w_1,w_2,…,w_n]^T$;

第二步：计算梯度Jacobian矩阵。

$g_t =[g_1,g_2,…,g_i]^T= [(\hat y_1-y_1)x_i,(\hat y_2-y_2)x_2,…,(\hat y_i-y_i)x_i]$;

第三步：$[w_1,w_2,…,w_n]^T:=[w_1,w_2,…,w_n]^T-\alpha g_t$;

第四步：$w^* = arg \min_wLoss $;

第五步：算法结束

1.The derivation of the PCA

1.1 主观理解

​ PCA算法是一种特征降维方法，该方法是一种线性降维方法。加入有两个特征，一个是房价，一个房子面积，先对结果进行降维。

首先进行减均值去中心化，得到：

​ 房价（$X$）和面积（$Y$）的样本协方差为（样本方差）：

$$Var(X) = \frac{1}{n-1}\Sigma_{i=1}^n (X-\mu_{X})\\ Cov(X,Y) = \frac{1}{n-1}\Sigma_{i=1}^n (X-\mu_{X})(Y-\mu_{Y})$$

​

Word2Vec and Corresponding Knowledge

1. Neural Network language model

1.1 CBOW(Continue bag of words)

CBOW最早是Mikolov等大牛在2013年提出的。CBOW要利用若干个上下文词来预测中心词。之所以称为continuous bag-of-word，即连续词袋，是因为在考虑上下文单词时，这些上下文单词的顺序是忽略的。我们先从最简单版本的CBOW开始讲，即上下文词只有1个。

One-word context

先从最简单的CBOW开始讲，即只使用1个上下文单词$w_I$来预测中心词$w_O$。
如图1描述的就是One-word context定义之下的神经网络模型。词典大小为V, 隐藏层的大小为N，相邻层的神经元是全连接的。输入层是一个用one-hot方式编码的单词向量$x=(x_1,…x_k,…,x_V)$，其中只有一个$x_k$为1，其余均为0。

输入层到隐藏层
输入层到隐藏层的连接权重可以表示使用$W_{V \times N}$:

$$\mathbf W= \begin{pmatrix} w_{11}& w_{12}& …& w_{1N}\\ w_{21}& w_{22}& … & w_{2N}\\ …& … & … & …\\ w_{V1}& w_{V2}&. .. &w_{VN} \end{pmatrix}$$

$W_{V \times N}$每行是相应单词的输入词向量表示，即第一行为词典中第一个单词的输入词向量表示，第$k$行为词典中第$k$个词的输入词向量表示，解释如下：

$$\mathbf h= \mathbf W^T \mathbf x=\mathbf W_{(k,\cdot)}^T :=\mathbf v_{\omega_I}^T \tag{1}$$

$x$是某个单词的one-hot向量表示，且该单词在词典中的下标为k，即$x_k$=1, $x^\prime_k=0, k^\prime≠k$。因此只用到$W^T$的第$k$列，也即$W$的第$k$行。因此，$W$的第$k$行即为第k个单词的输入词向量，相当于直接将$W$的第$k$行拷贝到隐藏层单元$h$上。该输入词向量也是我们最终学习到的词向量（后面的输出词向量我们不需要）。

在上述神经网络中，相当于输入层到隐藏层的激活函数为线性激活函数。另外，由于具有上述的性质，因此通常输入层到隐藏层不显示绘制出来，直接通过查表操作(如TensorFlow中embedding_lookup)拿出单词的词向量，然后传入到下一层，只不过这个词向量也需要通过反向传播来优化。