应用机器学习算法总结

Machine Learning

前言

三四月曾计划投递算法实习，可春招直接一片红海，各厂连开发HC都没有，更不必说卷到天上算法岗
近来突然病倒，我不得提前结束所有出国的计划。
这段时间一切的学习变得有心无力，况且我也不是一个喜欢学习的人，可HR不断的电话轰炸提醒我无论如何还是要面临秋招的挑战
这两天状态好些重新捡起了Leetcode，发现停了一个多月甚至写代码已有所生疏，还有其他大量的基础知识。我意识到我没有能力在秋招前再好高骛远的追求算法或是DS岗了
择业方向将调整为开发，大数据和量化方向，机器学习大概率是鲜有用到了

三四月做的一些机器学习的面试准备将整理于此处，便于日后阅读
mathjax在部分浏览器表现不佳，当看到公式不显示时请刷新浏览器
markdown不同编辑器的格式不同，排版有些混乱，日后将会逐步完善

指标与模型评估

评价两个特征相似度的指标：
- 协方差: $Cov(X,Y)=E[(X-ux)(Y-uy)]$
- 相关系数：$p=\frac{Cov(X,Y)}{\sigma_x\sigma_y}$
如果在模型中加入一个特征，怎样判断这个特征的好与坏
- 皮尔逊相关系数，互信息系数，距离相关系数
- 互信息：$I(X;Y)=H(Y)-H(Y|X)$ (熵与条件熵的差)
- 信息增益比：$I(X;Y)/H(X)$ (互信息/特征x的熵)
  - 信息增益比倾向于分类特征数较小的特征
选择特征的方法：
- 方差选择法
- 相关系数法
- 互信息法
- 卡方检验 $x^2=Sum[((A-E)^2)/E]$

特征工程

标准化（Normalization）
- 线性归一化：$X_n=(X-X_{min})/(X_{max}-X_{min})$
- Z-Score: $z=\frac{(x-u)}{\sigma}$
BN的作用
- 就是在深度神经网络训练过程中使得每一层神经网络的输入保持相同分布的
- 加快网络的训练和收敛速度
  - 如果每层的数据分布都不一样的话，将会导致网络非常难收敛和训练，而如果把每层的数据都在转换在均值为零，方差为1的状态下，这样每层数据的分布都是一样的训练会比较容易收敛
- 控制梯度爆炸，防止梯度消失
  - 梯度消失：在深度神经网络中，如果网络的激活输出很大，其对应的梯度就会很小，导致网络的学习速率就会很慢，假设网络中每层的学习梯度都小于最大值0.25，网络中有n层，因为链式求导的原因，第一层的梯度将会小于0.25的n次方，所以学习速率相对来说会变的很慢，而对于网络的最后一层只需要对自身求导一次，梯度就大，学习速率就会比较快，这就会造成在一个很深的网络中，浅层基本不学习，权值变化小，而后面几层网络一直学习，后面的网络基本可以表征整个网络，这样失去了深度的意义。（使用BN层归一化后，网络的输出就不会很大，梯度就不会很小）
  - 梯度爆炸：同理，使用BN后权值的更新也不会很大
- 防止过拟合
  - 在网络的训练中，BN的使用使得一个minibatch中所有样本都被关联在了一起，因此网络不会从某一个训练样本中生成确定的结果，即同样一个样本的输出不再仅仅取决于样本的本身，也取决于跟这个样本同属一个batch的其他样本，而每次网络都是随机取batch，这样就会使得整个网络不会朝这一个方向使劲学习。一定程度上避免了过拟合。

决策树

ID3
- 信息增益
C4.5
- 信息增益比
CART
- 分类问题：基于基尼系数划分特征
  - 基尼系数：$Gini(p) = \sum\limits_{k=1}^{K}p_k (1-p_k)=1-\sum\limits_{k=1}^{K}(p_k)^2$
    - 这里$p_k=\frac{|C_k|}{|D|}$，$C_k$是$D$中属于第k类的样本子集，$K$是类的个数
- 分类问题：平方误差
  - 对于每个特征，遍历每个取值s将数据集分成两份，计算切分后的误差
    - 选择误差最小的特征作为树的分裂点，切分节点形成左右分支
    - 递归以上操作

损失函数

回归问题
- MSE，MAE
分类问题
- Log loss
- Focal Loss
- Hinge Loss
- Exponential Loss
MSE
Cross Entropy
- $H(p,q) = H(p)+D_{KL}(p||q)$
- $H(p,q) = -\sum_{i=1}^{n}p(x_i)log(q(x_i))$
为什么分类问题不能使用MSE作为损失函数
- MSE的意义是计算预测值与目标值的欧式距离，交叉熵则是表征概率分布和预测概率分布差异，与欧氏距离无关

梯度消失和梯度爆炸

产生梯度不稳定的原因：前面曾的梯度乘上后面梯度的乘积，当存在过多的层时，就会出现梯度不稳定的场景，比如梯度消失和梯度爆炸
梯度消失的原因：
- 隐藏层的层数过多
- 采用了不合适的激活函数
梯度爆炸：
- 层数过多
- 权重的初始值过大
解决方案：
- 使用ReLu，Leaky-ReLu代替sigmoid函数
- 使用BN
- 合适的初始化

权重初始化

全部设为0
随机初始化
Xavier initialization
- 为了使得网络中的信息更好的流动，每一层输出的方差尽可能相等。即尽可能让输入和输出服从相同的分布，这样就能避免后面层的激活函数的输出值趋近于0
- 正态分布：$N(0,\frac{2}{(n1+n2})$
- 均匀分布：$[-\sqrt{\frac{6}{n1+n2}}, +\sqrt{\frac{6}{n1+n2}}]$
Kaiming initialization
- 本质上就是经过relu激活函数后，方差变为原先的1/2
- 正态分布：$N(0,2/n)$
- 均匀分布: $[-\sqrt(6/u), \sqrt(6/u)]$

优化算法

牛顿法
- 本质上就是泰勒展开取前两项然后求导
- Taylor 展开:
  $f(x) = f(x_0)+f’(x_0)(x-x_0)+\frac{1}{2}f’’(x_0)(x-x_0)^2+\dots+\frac{1}{n!}f^{(n)}(x_0)(x-x_0)^n$
  - 取前三项，忽略二次后的项
  - $f(x) = f(x_0)+f’(x_0)(x-x_0)+\frac{1}{2}f’’(x_0)(x-x_0)^2$
  - 求导 $f’(x) = f’(x_0)+f’’(x_0)(x-x_0)=0$
    - 得$x^*=x_0-\frac{f’(x_0)}{f’’(x_0)}$
  - 迭代公式: $x_{t+1}=x_t-\frac{f’(x_t)}{f’’(x_t)}$
- 推广到矩阵形式：$x_{k+1}=x_k-H_k^{-1}g_k$
  - 其中$H$为Hassian矩阵, $H = \nabla^2f(x_0)$
拉格朗日乘数法
- KKT条件
动量项
- 动量项累积了之前迭代时的梯度值，使得本次迭代时沿着之前的惯性方向向前走
- 之前的梯度下降法的更新公式为
  - $w_{k+1}=w_k - \alpha \nabla f(w)$
    - $\alpha$ 是学习率
    - 动量项则是修改了后面的梯度项，积累了之前的梯度
    - $w_{k+1} = w_k+\alpha *V_k$
      - $V_{k+1}=-\alpha \nabla f(w)+(1-\alpha)V_{k}$
RMSProp
- 全称Root Mean Square Prop，是AdaGrad的一种改进方法
- 更新公式：
  - $s_{dw}(t+1)=\beta s_{dw}(t)+ (1-\beta) dW^2$（注这里不是二阶导，而是一阶导的平方）
  - $W=W-\alpha \frac{db}{\sqrt{s_{dw}}+\epsilon}$
- $s_{dw}$是损失函数在前t−1轮迭代过程中累积的梯度动量
- RMSProp的特点是对梯度计算了微分平方加权平均数，如果摆动方向过于大的话，我们在更新权重或者偏置的时候除以它之前累积的梯度的平方根，这样就可以使得更新幅度变小
Adam
- 全称Adaptive Moment Estimation，其实就是结合了前面的Momentum和RMSProp算法
- $v_{dw} = \beta_1 v_{dw}+ (1-\beta_1)dw$
- $s_{dw} = \beta_2 s_{dw}+ (1-\beta_2)dw^2$
由于移动指数在迭代开始初期会导致和开始的值有较大的差异，因此对上式进行修正
- $v_{dw}^c = \frac{v_{dw}}{1-\beta_1^t}$
- $s_{dw}^c = \frac{s_{dw}}{1-\beta_2^t}$
- 注意这里$\beta$上面的t是t次方。
对权重和偏置进行更新
- $w=w-\alpha \frac{v_{dw}^c}{\sqrt{s_{dw}^c}+\epsilon}$
上式中，$\beta1$对应的是Momentum的$\beta$值，$\beta2$对应的是RMSProp算法中的$\beta$值

逻辑回归

本质上就是想用线性回归来做分类问题，引入了Sigmoid函数作为拟合函数
Sigmoid 函数: $f(z)=\frac{1}{1+e^{-z}}$
- 值域为[0,1]，能够把值都映射到[0,1]上
- 将物品类别分类为1的概率：$P(Y=1)=\frac{1}{1+e^{-X\beta}}$
损失函数：
- Log Loss： $J(\beta)=-logL(\beta)=-\sum\limits_{i=1}^{n}[y_i logP(y_i)+(1-y_i)log(1-P(y_i))]$
  - 这个是用极大似然估计+log取负号得来的，$L(\beta)$表示观测到的y发生概率的乘积

SVM及SMO算法

SVM Support Vector Machine
- 目的是找到最大间隔超平面$w^T x+b=0$
- 点$x(x_1,x_2… x_n)$到超平面的距离为：$d=\frac{|w^T x+b|}{||w||}$
- 因此分类的结果如果大于$d$，$y_{predict}=1$,否则 $y_{predict}=-1$
  - 经过变化，两个方程合并，可以得到$y(w^T x + b)\geq1$
- 回到最初的目的，即最大化间隔 $d=\frac{|w^T x+b|}{||w||}$
  - 由上式，去掉绝对值 $d=\frac{y(w^T x + b)}{||w||}$
  - 目标函数$ f(w)=\max\limits_{w,b}2*\frac{y(w^T x + b)}{||w||}$ 前面乘上一个2是为了方便后面推导，不影响目标结果
    - 在支持向量上(支持向量是离分割平面最近的样本点, 即满足$y(w^T x + b)=1$)，所以目标函数可表示为:$f(w)=\max\limits_{w} \frac{2}{||w||}=\min\limits_{w}\frac{1}{2}||w||=\min\limits_{w}\frac{1}{2}{||w||}^2$(为了表示方便，去掉$||w||$的根号)
      *得到SVM的初步优化问题:
  - $f(w)=\min\limits_{w} \frac{1}{2}{||w||}^2\ \ s.t. \ \ y_i(w^Tx_i+b) \geq 1$
- 当前的问题是一个不等式优化问题，针对这种情况常用的思想是将不等式约束条件转变为等式约束条件，引入松弛变量
  - 不等式约束（引入松弛变量）-> 等式约束（lagrange函数）-> 无约束优化
Lagrange 函数
- 当前的问题为：$f(w)=\min\limits_{w} \frac{1}{2}{||w||}^2\ \ s.t. \ \ g_i(w)=1-y_i(w^Tx_i+b) \leq 0$
  - 引入松弛变量 $a_i^2$得到 $h_i(w,a_i)=g_i(w)+a_i^2=0$ 由此我们将此式转化为等式约束，下一步生成Lagrange函数:
  - $L(w,\lambda,a)=f(w)+\sum\limits_{i=1}^{n}\lambda_i[g_i(w)+a_i^2] \ \ \lambda_i \geq 0$
  - 根据约束优化问题极值的必要条件对其求解，联立方程，拉格朗日方程对$a,w,\lambda$的偏微分=0，得到KKT条件： $\begin{cases} \frac{\partial L}{\partial w_i}=\frac{\partial f}{\partial w_i}+\sum\limits_{j=1}^n\lambda_j\frac{\partial g_j}{\partial w_i}=0\\ \lambda_i g_i(w)=0\\ g_i(w)<=0\\ \lambda_i>=0 \end{cases}$ $\lambda_i$称为KKT乘子

KKT条件及理解
- 支持向量$g(w_i)=0$，所以$\lambda_i>0$即可
  - 而其它向量$g(w_i)<0, \lambda_i=0$
- 原问题是$f(w)=\min\limits_w \frac{1}{2}{||w||}^2$, 现在转化为求解问题 $\min\limits_{w,\lambda,a} L()$
  - 假设找到了最佳参数的目标函数的最小值为p, 因为$g_i(w)<0$则 $L(w,\lambda) < p$,因此为了找到最优的参数$\lambda$使得$L(w,\lambda)$尽可能接近于p，故问题转换为$\max\limits_{\lambda}(w,\lambda)$
  - 因此我们可以将原问题转化为: $\min\limits_w\max\limits_{\lambda}L(w,\lambda) \ \ s.t. \ \lambda_i \geq 0$
强对偶性
- 加入函数$f$有,$\min \max f \geq \max \min f$ 可以理解为凤尾大于鸡头，此为弱对偶关系
- 而强对偶关系的意思是指等号成立, $\min \max f = \max \min f$
- 如果$f$是凸优化问题，则强对偶关系成立，而前面的KKT条件，就是强对偶关系的充分必要条件
SVM 优化
- SVM 优化的主要问题是：$\min\limits_{w}\frac{1}{w} {||w||}^2,\ \ s.t \ \ g_i(w,b)=1 - y_i(w^T x_i + b) \leq 0$
- 构造拉格朗日函数：$\min\limits_{w,b}\max\limits_{\lambda}L(w,b,\lambda)=\frac{1}{2}{||w||}^2+\sum\limits_{i=1}^{n}\lambda_i[1-y_i(w^Tx_i+b)]\ \ s.t. \ \ \lambda_i \geq 0$
- 利用强对偶性转化：$\max\limits_{\lambda}\min\limits_{w,b}L(w,b,\lambda)$
  - 对$w,b$求偏导，并使其等于0，得：
    - $\sum\limits_{i=1}^{n}\lambda_i x_i y_i = w$
    - $\sum\limits_{i=1}^{n}\lambda_i y_i=0$
  - 将上式结果代回到原方程得：
- SMO算法
  - 可以看出上式问题是一个二次规划问题，问题规模正比于训练样本数，常用SMO(Sequential Minimal Optimization) 算法求解。
    - SMO核心思想非常简单：每次只优化一个参数，其他参数先固定住，仅求当前这个优化参数的极值。
    - 但是优化目标有约束条件：$\sum\limits_{i-1}^{n}\lambda_i y_j = 0$
      - 因此没有办法一次只变动一个参数，所以选择一次变动两个参数，固定其他约束，于是有以下约束：
        
        $\lambda_iy_i+\lambda_jy_j=c \ \ \ s.t. \ \ \lambda_i \geq 0 \ \lambda_j \geq 0$
        
        其中$c=-\sum\limits_{k \neq i,j}\lambda_ky_k$, 由此可以得出$\lambda_j=\frac{c-\lambda_iy_i}{y_j}$,也就是说我们可以利用$\lambda_i$的表达式来代替$\lambda_j$，这样就相当于把目标问题转化成了仅有一个约束条件的最优化问题，仅有的约束是$\lambda_i\geq0$。
    - 对于仅有一个约束条件的最优化问题，我们完全可以在 $\lambda_i$上对优化目标求偏导，令导数为零，从而求出变量值 $\lambda_{i_{new}}$ ，然后根据$\lambda_{i_{new}}$求出$\lambda_{j_{new}}$ 。
    - 通过多次迭代求得最优解$\lambda^*$
- 前面求偏导可知，$w=\sum\limits_{i=1}^{m}\lambda_iy_ix_i$
- 可以求得w
- 我们知道所有的$\lambda_i>0$对应的点都是支持向量，我们可以随便找到一个支持向量，然后代入:
  - $y_s(wx_s+b)=1$, 即可求得b
- 为更具鲁棒性，可以求得支持向量的均值: $b=\frac{1}{|S|}\sum\limits_{s\in S}(y_s-wx_s)$
- $w$和$b$都得到了，即可构建超平面了$f(x)=sign(w^Tx+b)$
Soft Margin问题
- 前面讨论的都是硬间隔(Hard Margin问题)，但实际情况是，数据经常会有一些坏点，导致样本线性不可分。Soft Margin就是为了解决这个问题，相比硬间隔的苛刻条件，允许个别样本点出现在间隔带里面，至于度量软间隔的程度。可以用$\xi_i$来表示距离间隔带的长度
- 增加软间隔后优化目标变成了:

$\min\limits_{w}\frac{1}{2}{||w||}^2+C\sum\limits_{i=1}^{m}\xi_i \\ s.t. \ \ g_i(w,b)=1-y_i(w^Tx_i+b)-\xi_i\leq0, \ \xi_i \geq0,\ i=1,2,3,4 \cdots$

其中 C 是一个大于 0 的常数，可以理解为错误样本的惩罚程度，若 C 为无穷大， $\xi$必然无穷小，如此一来线性 SVM 就又变成了线性可分 SVM；当 C 为有限值的时候，才会允许部分样本不遵循约束条件。随后构造Lagrange函数：

$\min\limits_{w,b,\xi}\max\limits_{\lambda,\mu}L(w,b,\xi,\lambda,\mu)=\frac{1}{2}{||w||}^2+C\sum\limits_{i=1}^{m}\xi_i+\sum\limits_{i=1}^{n}\lambda_i[1-\xi_i-y_i(w^Tx_i+b)]-\sum\limits_{i=1}^{n}\mu_i\xi_i\\ s.t.\ \ \ \lambda_i\geq0\ \ \mu_i\geq 0$

其中$\lambda_i$和$\mu_i$是拉格朗日乘子, $w,b$ 和$\xi_i$是主问题参数。
根据强对偶性，将对偶问题转换为：

$\max\limits_{\lambda,\mu}\min\limits_{w,b,\xi}L(w,b,\xi,\lambda,\mu)$

分别对主问题参数 $w,b$ 和$\xi_i$求偏导，并另偏导数为0，得：

$w = \sum\limits_{i=1}^{m} \lambda_iy_ix_i \\ 0 = \sum\limits_{i=1}^{m}\lambda_iy_i \\ C = \lambda_i + \mu_i$

将这些关系带入上式得Lagrange函数中，可得：

$\min\limits_{w,b,\xi}L(w,b,\xi,\lambda,\mu)=\sum\limits_{j=1}^{n}\lambda_i-\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\lambda_i\lambda_jy_iy_j(x_i\cdot x_j)$

最小化结果只有$\lambda$而没有$\mu$，所以现在只需要最大化$\lambda$就好：

$\max\limits_{\lambda}[\sum\limits_{j=1}^{n}\lambda_i-\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\lambda_i\lambda_jy_iy_j(x_i\cdot x_j)]\\ s.t. \ \ \ \sum_{i=1}^{n}\lambda_iy_i = 0, \ \ \lambda_i \geq0, \ \ C-\lambda_i - \mu_i=0$

可以发现软间隔和硬间隔其实是一样的，只是多了个约束条件
然后同理用SMO算法求解得到拉格朗日乘子$\lambda^*$
求出超平面：

$w=\sum\limits_{i=1}^{m}\lambda_iy_ix_i \\ b=\frac{1}{|S|}\sum\limits_{s\in S}(y_s-wx_s)$

在间隔区内的部分样本点是不是支持向量？
- 我们可以由求参数 w 的那个式子可看出，只要$\lambda_i>0$ 的点都能够影响我们的超平面，因此都是支持向量。
Kernel 核函数
- 当问题线性不可分的时候，可以用核函数把样本映射到高维空间，让样本点在高维空间线性可分
- 常见核函数：
  - 线性核函数 $k(x_i.x_i)=x_i^T x_j$
  - 多项式核函数 $k(x_i,x_j)=(x_i^T x_j)^d$
  - 高斯核函数 $k(x_i,x_i)=exp(-\frac{||x_i-x_j||}{2\delta^2})$
- 核函数的选择技巧：一般选择线性核函数，效果如果不好可以上高斯核函数
SVM 的优缺点：
- 优点
  - 可解释性强，不依靠统计方法，从而简化了通常的分类和回归问题
  - 能找出对任务至关重要的关键样本（支持向量）
  - 最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”
- 缺点
  - 训练时间长。当采用 SMO 算法时，由于每次都需要挑选一对参数，因此时间复杂度为$O(N^2)$ ，其中 $N$ 为训练样本的数量
  - 当采用核技巧时，如果需要存储核矩阵，则空间复杂度为 $O(N^2)$
  - 模型预测时，预测时间与支持向量的个数成正比。当支持向量的数量较大时，预测计算复杂度较高。
  - 因此支持向量机目前只适合小批量样本的任务，无法适应百万甚至上亿样本的任务。

聚类算法

Pytorch实现案例

实现mlp网络结构

# 建立一个四层感知机网络
class MLP(torch.nn.Module):   # 继承 torch 的 Module
    def __init__(self):
        super(MLP,self).__init__()    #
        # 初始化三层神经网络 两个全连接的隐藏层，一个输出层
        self.fc1 = torch.nn.Linear(784,512)  # 第一个隐含层  
        self.fc2 = torch.nn.Linear(512,128)  # 第二个隐含层
        self.fc3 = torch.nn.Linear(128,10)   # 输出层
        
    def forward(self,din):
        dout = F.relu(self.fc1(din))  
        dout = F.relu(self.fc2(dout))
        dout = F.softmax(self.fc3(dout), dim=1)
        return dout

    def train(self, X):
        loss_func = torch.nn.CrossEntropyLoss()
        optimizer = torch.optim.SGD(params = model.parameters(),lr=0.001)
        for epoch in range(n_epochs):
            optimizer.zero_grad()
            output = model(data)
            loss = loss_func(output,target)
            loss.backward()
            optimizer.step()
            train_loss += loss.item()*data.size(0)

实现LR

强化学习

先说一下DQN网络
- 本质上来说就是用神经网络来估计Q
- 原本Q-Learning的更新规则是这样的：
  - $Q(s,a)=Q(s,a)+\alpha[r+\gamma maxQ(s’,a’)-Q(s,a)]$
  - $就是尽量使 [r+\gamma maxQ(s’,a’)-Q(s,a)] 逼近于0$
- 于是Q网络可以转换成为
  - $w*=argmin_w{r+\gamma maxQ(s’,a’)-Q(s,a)}$
- 经验回放，可以把以前的数据$(s(t),a(t),s(t+1),rt)$取出来然后批量训练
说一下dueling DQN
- 引入了优势函数变量=动作价值函数-状态价值函数
- 即 Q(s,a)=V(s)+A(s,a)
- 分别建立两个网络，然后把V和A加起来
- 为什么Dueling DQN会更好？
  - 因为每一次更新，V函数都会被更新到，这也会影响其它动作的Q值，而传统的DQN只会更新某个动作的Q值，其它动作的Q值就不会被更新
  - 可以学到不同动作的差异性，在动作空间较大的环境下非常有效
- 网络结构的实现

class VAnet(torch.nn.Module):
    def __init__(self, state_dim, hidden_dim, action_dim):
        super(VAnet, self).__init__()
        self.fc1 = torch.nn.Linear(state_dim, hidden_dim) # 共享网络部分
        self.fc_A = torch.nn.Linear(hidden_dim, action_dim)
        self.fc_V = torch.nn.Linear(hidden_dim, 1)
    def forward(self, x):
        A = self.fc_A(F.relu(self.fc1(x)))
        V = self.fc_V(F.relu(self.fc1(x)))
        Q = V + A - A.mean(1).view(-1, 1) # Q值由V值和A值计算得到
        return Q

贝尔曼方程 $V(s)=r(s)+\gamma \sum\limits_{s'\in S}p(s'|s)V(s')$
在线策略和离线策略 (on-policy和off-policy)
- 在线策略：行为策略和目标策略是一个策略：Sarsa
  - Sarsa的评估策略和行动策略都是 $\epsilon-greedy$
  - Q-learning 的评估策略是贪婪的，而行动策略是$\epsilon-greedy$
- 离线策略：行为策略和目标策略不是一个策略：Q-Learning
  - 离线策略能够更好的利用历史数据，因此具有更小的样本复杂度
model-based 和model-free
- model-free是agent和environment进行实时的交互，单纯通过样本来学习
- model-based则是先学一个model

PSO算法

粒子群算法 particle swarm optimization
速度更新
- 其中w是惯性因子，一般动态的w会比静态的w有更好的的寻优结果
- $w=(w_{ini}-w_{end})(G_k-g)/G_k + w_{end}$
  - $G_{k}$：最大迭代次数
  - $ g$：当前迭代次数
  - $w_{ini}, w_{end}：w$的范围
- $c1,c2$是学习因子
  - 如果$c1$为0，说明粒子没有自身的认知能力，变成一个社会学模型，收敛速度快，更容易陷入局部最优
  - 如果$c2$为0，说明粒子没有社会信息，整个群体相当于多个粒子进行盲目的搜索，收敛速度慢
位置更新 $x=x+v$

Embedding Learning 集成机器学习

集成学习就是组合多个若监督模型以期得到一个更好更全面的强监督模型，其潜在思想就是某一个弱分类器得到了错误的预测，其他的弱分类器也能将错误纠正过来。

数据集过大：划分成多个小数据集，学习多个模型进行组合
数据集过小：利用Bootstrap方法进行抽样，得到多个数据集，分别训练多个模型再进行组合

集成学习分类

Bagging
- Bagging是bootstrap aggregating的简写
  - bootstrap：bootstrap也称为自助法，它是一种有放回的抽样方法，目的为了得到统计量的分布以及置信区间
- Bagging 利用bootstrap方法从整体数据集中采取有放回抽样得到N个数据集，在每个数据集上学习出一个模型，最后的预测结果利用N个模型的输出得到，具体地：分类问题采用N个模型预测投票的方式，回归问题采用N个模型预测平均的方式。
- 如随机森林，就是用Bagging的思想，有两个采样的过程，对输入数据的行（数据的数量）与列（数据的特征）都进行采样
Boosting
- Boosting可以直接理解为additive training
- Boosting是一种可以用来减小监督学习中偏差的机器学习算法。主要也是学习一系列弱分类器，并将其组合为一个强分类器。Boosting中有代表性的是
  - AdaBoost（Adaptive boosting）Ref
    - AdaBoost 的自适应在于：前一个基本分类器被错误分类的样本的权值会增大，而正确分类的样本的权值会减小，并再次用来训练下一个基本分类器。同时，在每一轮迭代中，加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数才确定最终的强分类器。
    - 算法流程：
      1.首先基于训练数据的权值分布，对每一个训练样本最开始都基于相同的权值$w_i=\frac{1}{N}$
      
      2.选择一个当前误差率最低的弱分类器$H_t$，并计算在当前数据分布之下，弱分类器的误差：
      
      这个式子可以理解为错误的预测的权值之和。
      
      3.计算该分类器在最终分类器所占的比重：
      
      4.更新训练的权值分布$D_{t+1}$
      
      其中$Z_t$为归一化常数$Z_t=2\sqrt{e_t(1-e_t)}$
      具体到每个样本的更新：
      - 错误样本(将被分配更高的权重)：$D_{t+1}(i)=\frac{D_t(i)}{2e_t}$
      - 正确样本(将被分配更低的权重): $D_{t+1}(i)=\frac{D_t(i)}{2(1-e_t)}$
        
        5.不断迭代（2）-（4）得到T个分类器的权重。
        
        6.最终，按照分类器的权重$a_t$组合分类器，得到集成函数：
        $f(x)=\sum\limits_{t=1}^T \alpha_tH_t(x)$
        再通过符号函数，得到一个强分类器：
        $H_{final}=sign(f(x))=sign(\sum\limits_{t=1}^T \alpha_tH_t(x))$
    - Adaboosting的优点：
      - 不用对特征进行筛选，也不存在过拟合的现象。
      - 不需要预先知道弱分类器的错误率上限，可以根据弱分类器的反馈，自适应地调整假定的错误率，执行的效率高。
    - Adaboosting的缺点：
      - 会使得难于分类样本的权值呈指数增长，训练将会过于偏向这类困难的样本，导致易受噪声干扰
  - GBDT（Gradient Boost Decision Tree) 和 XGBoost Ref
    - 也是一种Boosting的方法，与AdaBoost不同，GBDT每一次的计算是为了减少上一次的残差，GBDT在残差减少（负梯度）的方向上建立一个新的模型
    - XGBoost 是gbdt的一种工程算法实现，和GBDT只有少量的区别，可以把两者一起看待，然后记住少量区别就够了
    - GBDT原理
      - 首先Boosting算法都可以看作是K课树组成的加法模型 $\hat{y}=\sum\limits_{k=1}^{K}f_k(x_i)$
      - 目标函数： $Obj^{(t)} = \sum\limits_{i=1}^{n}l(y_i,\hat{y}_i^t)+\sum\limits_{i=1}^t\Omega(f_i) =\sum\limits_{i=1}^{n}l(y_i,\hat{y}_i^{t-1}+f_t(x_i))+\Omega(f_t)+constant$ 此时$f_t(x_i)$是我们要加入的新模型
      - 引入泰勒展开： $f(x+\Delta x)\approx f(x)+f'(x)\Delta x+\frac{1}{2}f''(x)\Delta x^2$ 把$\hat{y}_i^{t-1}$看成是上式的$x$，$f_t(x_i)$看作是$\Delta x$, 因此目标函数可以写成： $Obj^{(t)}\approx \sum\limits_{i=1}^{n}[l(y_i,\hat{y}_i^{t-1})+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)+constant$ 其中$g_i$是损失函数的一阶导，$h_i$是损失函数的二阶导
        只关注$f_t(x_i)$有关项，目标函数可以写成: $Obj^{(t)}\approx \sum\limits_{i=1}^{n}[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\Omega(f_t)+constant$ 所以只需要求得每一步的一阶导数和二阶导数的值，然后最优化目标函数，就可以得到每一步的$f(x)$
    - 如何找到叶子的最优分裂点
      - 贪心算法
        
        参考cart，对每个值进行升序排序，对每个值都作为当前的分裂点，然后计算分裂收益
      - 近似算法
        
        贪心算法可以得到最优解，但是数据量太大时则无法读入内存进行计算，因此可以考虑使用近似算法
        
        近似算法的思想是对特征进行分桶，即找到l个划分点，把相邻分位点之间的样本分在一个桶中。在遍历该特征的时候，只需要遍历各个分位点，从而计算最优划分。算法实现中该流程还可以分为两种
        
        全局近似是在新生成一棵树之前就对各个特征计算分位点并划分样本，之后在每次分裂过程中都采用近似划分，
        
        局部近似就是在具体的某一次分裂节点的过程中采用近似算法。
    - XGBoost 处理稀疏值
      - 当样本的第i个特征值缺失时，无法利用该特征进行划分时，XGBoost的想法是将该样本分别划分到左节点和右节点，然后计算其增益，那边大就划分到哪边
    - XGBoost 的优点
      - 使用许多策略去防止过拟合，如：正则化项、Shrinkage and Column Subsampling等
      - 支持并行化，这是XGBoost的闪光点，虽然树与树之间是串行关系，但是同层级节点可并行。具体的对于某个节点，节点内选择最佳分裂点，候选分裂点计算增益用多线程并行。训练速度快。
      - 对稀疏条件的处理
      - 交叉验证，early stop
  - GBDT, XGBoost, LightGBM 的区别
    1. XGBoost使用基于预排序的决策树算法，每遍历一个特征就需要计算一次特征的增益，时间复杂度为O(datafeature)而LightGBM使用基于直方图的决策树算法，直方图的优化算法只需要计算K次，时间复杂度为O(Kfeature)
    2. XGBoost使用按层生长(level-wise)的决策树生长策略，LightGBM则采用带有深度限制的按叶子节点(leaf-wise)算法。在分裂次数相同的情况下，leaf-wise可以降低更多的误差，得到更好的精度。leaf-wise的缺点在于会产生较深的决策树，产生过拟合。
    3. 支持类别特征，不需要进行独热编码处理
    4. 优化了特征并行和数据并行算法，除此之外还添加了投票并行方案
    5. 采用基于梯度的单边采样来保持数据分布，减少模型因数据分布发生变化而造成的模型精度下降
    6. 特征捆绑转化为图着色问题，减少特征数量

Bagging 和Boosting对比
- Bagging中每个训练集互不相关，也就是每个基分类器互不相关，而Boosting中训练集要在上一轮的结果上进行调整，也使得其不能并行计算
- Bagging中预测函数是均匀平等的，但在Boosting中预测函数是加权的
- Bagging已经保证降低了方差，但是偏差无法保证，所以每个模型需要负责一些以降低偏差（比如每一颗决策树都很深）；Boosting采用的策略是在每一次学习中都减少上一轮的偏差，因而在保证了偏差的基础上就要将每一个基分类器简化使得方差更小

Stacking
- Stacking方法是指训练一个模型用于组合其他各个模型。首先我们先训练多个不同的模型，然后把之前训练的各个模型的输出为输入来训练一个模型，以得到一个最终的输出。理论上，Stacking可以表示上面提到的两种Ensemble方法，只要我们采用合适的模型组合策略即可。但在实际中，我们通常使用logistic回归作为组合策略。

Stacking和Blending的区别
- Blending比较简单，用不相交的数据集训练多个不同的基模型，并将其输出取加权平均
- Stacking是将数据集划分为两个不相交的集合，在第一个集合的数据集中训练多个模型,在第二个数据集中测试这些模型,将预测结果作为输入,将正确的标签作为输出,再训练一个高层的模型
  - Stacking 理解起来有许多谬误，网上的说法偏差太多。这个链接目前是我自认为最清晰的Ref
- stacking是k-fold交叉验证，元模型的训练数据等同于基于模型的训练数据，该方法为每个样本都生成了元特征，每生成元特征的模型不一样（k是多少，每个模型的数量就是多少）；测试集生成元特征时，需要用到k（k fold不是模型）个加权平均；
  blending是holdout方法，直接将训练集切割成两个部分，仅10%用于元模型的训练；
- Blending相比Stacking的优点
  - 比stacking简单（因为不用进行k次的交叉验证来获得stacker feature）
  - 避开了一个信息泄露问题：generlizers和stacker使用了不一样的数据集
  - 在团队建模过程中，不需要给队友分享自己的随机种子
- Blending相比Stacking的缺点
  - 数据使用的不充分，可能会带来过拟合
  - stacking使用多次的CV会比较稳健

Transformer

VC维

RNN 循环神经网络

网络组成部分和理论推导在这里不赘述了，主要阐述问题和局限性
梯度消失和梯度爆炸
- RNN不能很好的处理长序列，因为RNN很容易在训练过程中发生梯度消失和梯度爆炸，导致训练梯度不能在较长序列中一直传递下去，从而使RNN无法捕捉到长距离的影响
- 梯度爆炸：比较好处理，直接设置一个阈值即可
- 梯度消失：
  - 合理的初始化权重
  - 使用Relu代替Sigmoid和tanh作为激活函数
  - 使用其他结构的RNNs，比如LSTM和GRU

LSTM

一种优化的RNN模型，但是复杂了很多
引入了长短期记忆，使用了三种门控，分别为$z^f$（遗忘门控），$z^i$（选择门控），$z^o$（输出门控），这三个门控都是拼接向量乘以权重矩阵之后，再通过一个$sigmoid$激活函数转换成0到1之间的数值
LSTM 主要有三个阶段：
- 忘记阶段： 具体来说是通过计算得到的$z^f$（f表示forget）来作为忘记门控，来控制上一个状态的$c^{t-1}$哪些需要留哪些需要忘。
- 选择记忆阶段： 这个阶段将这个阶段的输入有选择性地进行“记忆”。主要是会对输入$x^t$进行选择记忆。哪些重要则着重记录下来，哪些不重要则少记一些，当前的输入内容由前面计算得到的$z$表示。而选择的门控信号则是由$z^i$来进行控制
- 输出阶段： 输出阶段。这个阶段将决定哪些将会被当成当前状态的输出。主要是通过$z^o$来进行控制的。并且还对上一阶段得到的$c^o$进行放缩($tanh$ 函数)