Apache 常见算法-机器学习

线性回归

GLM

广义线性模型基于线性回归模型延展而来，衍生模型很多，如逻辑回归LR。线性“回归”一般是用于预测样本的值，这个值通常是连续的。受限于连续性，导致分类效果不理想。

为了保留线性回归“简单效果有不错”的特点，又想让它能够进行分类，因此需要对预测值再做一次处理。这个多出来的处理过程，就是GLM所做的最主要的事。而处理过程的这个函数，我们把它叫做连接函数。

当一个处理样本的回归模型是线性模型，且连接函数满足一定特性时，我们把模型叫做广义线性模型。用广义模型进行分类、回归都可以，线性回归是广义线性模型的子类，也就是连接函数不做任何处理。

连接函数要求 必须是连续可微，并且可逆的，在高斯线性模型中，链接函数是恒等函数。对于泊松分布，标准的链接函数选择是对数函数。链接函数本质上，就是把实数域范围的 n转换到特定分布合法的u值空间上。比如正态分布、泊松分布、二项分布、负二项分布、伽玛分布、逆高斯分布。形式上仍是线性回归，实质上已是在求取输入空间到输出空间的非线性函数映射。

LR

线性回归的样本的输出，都是连续值，y属于(-∞,+∞)，而逻辑回归中y∈{0, 1}，只能取0和1。

逻辑回归算法是一个分类算法，本质上是广义线性模型的一种。

GBDT

GBDT就是所有弱分类器的结果相加等于预测值，然后下一个弱分类器去拟合误差函数对预测值的残差(这个残差就是预测值与真实值之间的误差)。当然了，它里面的弱分类器的表现形式就是各棵树。

举一个非常简单的例子，比如我今年30岁了，但计算机或者模型GBDT并不知道我今年多少岁，那GBDT咋办呢？

它会在第一个弱分类器（或第一棵树中）随便用一个年龄比如20岁来拟合，然后发现误差有10岁；
接下来在第二棵树中，用6岁去拟合剩下的损失，发现差距还有4岁；
接着在第三棵树中用3岁拟合剩下的差距，发现差距只有1岁了；
最后在第四课树中用1岁拟合剩下的残差，完美。
最终，四棵树的结论加起来，就是真实年龄30岁（实际工程中，gbdt是计算负梯度，用负梯度近似残差）。

优点：

预测阶段的计算速度快，树与树之间可并行化计算。
在分布稠密的数据集上，泛化能力和表达能力都很好，这使得GBDT在Kaggle的众多竞赛中，经常名列榜首。
采用决策树作为弱分类器使得GBDT模型具有较好的解释性和鲁棒性，能够自动发现特征间的高阶关系。

局限性：

GBDT在高维稀疏的数据集上，表现不如支持向量机或者神经网络。
GBDT在处理文本分类特征问题上，相对其他模型的优势不如它在处理数值特征时明显。
训练过程需要串行训练，只能在决策树内部采用一些局部并行的手段提高训练速度。

XGBoost

XGBoost的性能在GBDT上又有一步提升，而其性能也能通过各种比赛管窥一二。坊间对XGBoost最大的认知在于其能够自动地运用CPU的多线程进行并行计算，同时在算法精度上也进行了精度的提高。

Boosting不是一种串行的结构吗?怎么并行的？

注意XGBoost的并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。XGBoost的并行是在特征粒度上的。决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

GBDT和XGBoost区别：

传统的GBDT以CART树作为基学习器，XGBoost还支持线性分类器，这个时候XGBoost相当于L1和L2正则化的逻辑斯蒂回归（分类）或者线性回归（回归）；
传统的GBDT在优化的时候只用到一阶导数信息，XGBoost则对代价函数进行了二阶泰勒展开，得到一阶和二阶导数；
XGBoost在代价函数中加入了正则项，用于控制模型的复杂度。从权衡方差偏差来看，它降低了模型的方差，使学习出来的模型更加简单，防止过拟合，这也是XGBoost优于传统GBDT的一个特性；
shrinkage（缩减），相当于学习速率（XGBoost中的eta）。XGBoost在进行完一次迭代时，会将叶子节点的权值乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。（GBDT也有学习速率）；
列抽样。XGBoost借鉴了随机森林的做法，支持列抽样，不仅防止过拟合，还能减少计算；
对缺失值的处理。对于特征的值有缺失的样本，XGBoost还可以自动学习出它的分裂方向；
XGBoost工具支持并行。

缺点：

虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍需要遍历数据集；
预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引，相当于消耗了两倍的内存

LightGBM

LightGBM是XGBoost的改进版，LightGBM 由微软提出，主要用于解决 GDBT 在海量数据中遇到的问题，以便其可以更好更快地用于工业实践中。LightGBM 提出了以下几点解决方案：

单边梯度抽样算法：利用信息对样本进行抽样，减少了大量梯度小的样本，在接下来的计算过程中只需关注梯度高的样本，极大的减少了计算量
直方图算法：将连续的特征离散化为 k 个离散特征，同时构造一个宽度为 k 的直方图用于统计信息（含有 k 个 bin）。利用直方图算法我们无需遍历数据，只需要遍历 k 个 bin 即可找到最佳分裂点
互斥特征捆绑算法：将一些特征进行融合绑定，则可以降低特征数量 。在LightGBM中，可以直接将每个类别取值和一个bin关联，从而自动地处理它们，也就无需预处理成onehot编码

与XGBoost对比，主要优势是速度和内存：

精度：两个模型相当
训练速度：LightGBM训练速度更快 => 1/10
内存消耗：LightGBM占用内存更小 => 1/6
特征缺失值：两个模型都可以自动处理特征缺失值
分类特征：XGBoost不支持类别特征，需要对其进行OneHot编码，而LightGBM支持分类特征

Random Forest

RF、GBDT和XGBoost都属于集成学习（Ensemble Learning），集成学习的目的是通过结合多个基学习器的预测结果来改善单个学习器的泛化能力和鲁棒性。

目前的集成学习方法大致分为两大类：即个体学习器之间存在强依赖关系、必须串行生成的序列化方法，以及个体学习器间不存在强依赖关系、可同时生成的并行化方法；前者的代表就是Boosting，后者的代表是Bagging和“随机森林”（Random Forest）。

Bagging可以简单的理解为：放回抽样，多数表决（分类）或简单平均（回归）,同时Bagging的基学习器之间属于并列生成，不存在强依赖关系。

Random Forest是Bagging的扩展变体，它在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机特征选择，因此可以概括RF包括四个部分：

随机选择样本（放回抽样）
随机选择特征
构建决策树
随机森林投票（平均）

在构建决策树的时候，RF的每棵决策树都最大可能的进行生长而不进行剪枝；在对预测输出进行结合时，RF通常对分类问题使用简单投票法，回归任务使用简单平均法。

优点：

在数据集上表现良好，相对于其他算法有较大的优势（训练速度、预测准确度）
能够处理很高维的数据，并且不用特征选择，而且在训练完后，给出特征的重要性
容易做成并行化方法

缺点：

在噪声较大的分类或者回归问题上回过拟合。

Factorization Machines

FM的全称是Factorization Machines，就是因子分解机的意思，为什么叫因子分解呢，就是因为他对传统的线性回归模型加了一个因子交叉项，你可以理解为把每一个特征和其他特征相乘后求和。

一般的线性模型压根没有考虑特征间的关联：

从公式可以看出，组合特征的参数一共有 n(n−1)/2个，任意两个参数都是独立的。然而，在数据稀疏性普遍存在的实际应用场景中，二次项参数的训练是很困难的。其原因是，每个参数的训练需要大量都非零的样本；由于样本数据本来就比较稀疏，满足都非零”的样本将会非常少。训练样本的不足，很容易导致参数不准确，最终将严重影响模型的性能。

公式2是一个通用的拟合方程，可以采用不同的损失函数用于解决回归、二元分类等问题，比如可以采用MSE（Mean Square Error）损失函数来求解回归问题，也可以采用Hinge/Cross-Entropy损失来求解分类问题。当然，在进行二元分类时，FM的输出需要经过sigmoid变换，这与Logistic回归是一样的。

其实就是把W分解了，分解成两个矩阵相乘，这样的话其实就剩kn个参数需要我们计算了，降低了算法复杂度。可以发现参数矩阵w是一个*实对称矩阵，可以使用矩阵分解的方法分解，通过引入辅助向量又称为隐向量V来表示。

Wide & Deep

Wide & Deep 模型的核心思想是结合线性模型的记忆能力和 DNN 模型的泛化能力，在训练过程中同时优化 2 个模型的参数，从而达到整体模型的预测能力最优。

线性模型LR简单、快速并且模型具有可解释，有着很好的拟合能力，但是LR模型是线性模型，表达能力有限，泛化能力较弱，需要做好特征工程，尤其需要交叉特征，才能取得一个良好的效果，然而在工业场景中，特征的数量会很多，可能达到成千上万，甚至数十万，这时特征工程就很难做，还不一定能取得更好的效果。 推荐用户之前有过行为的items
DNN几乎不需要特征工程，就可以取得很好的效果，DNN可以自动交叉特征，通过对低纬度的dense embedding进行组合可以学习到更深层次的隐藏特征，尤其是可以学到高阶特征交互，具有很好的泛化能力。另外，DNN通过增加embedding层，可以有效的解决稀疏数据特征的问题，防止特征爆炸。推荐系统中的泛化能力是很重要的，可以提高推荐物品的多样性。但是DNN在拟合数据上相比较LR会较弱，缺点是有点over-generalize（过度泛化）。推荐系统中表现为：会给用户推荐不是那么相关的物品，尤其是user-item矩阵比较稀疏并且是high-rank（高秩矩阵）。趋向于提高推荐系统的多样性。

为了提高推荐系统的拟合性和泛化性，可以将LR和DNN结合起来，同时增强拟合能力和泛化能力，wide&deep就是将LR和DNN组合起来，wide部分就是LR，deep部分就是DNN，将两者的结果组合进行输出。

Wide也是一种特殊的神经网络，他的输入直接和输出相连，属于广义线性模型的范畴。Deep部分就是前馈神经网络模型。对于高维稀疏的分类特征，首先会转化成低维的稠密的向量，然后作为神经网hidden layers的输入进行训练。

Wide部分采用了组合特征的方式，如下所示：

仅仅在输入样本X中的特征gender=female和特征language=en同时为1，新的组合特征AND(gender=female, language=en)才为1。所以只要把两个特征的值相乘就可以了。（这样Cross-product transformation 可以在二值特征中学习到组合特征，并且为模型增加非线性）

模型训练过程中采用联合训练的方式，联合训练 (joint training) 会同时优化所有参数，通过将 wide 组件和 deep 组件在训练时进行加权求和的方式进行，联合训练通过对梯度进行后向传播算法、SGD 优化来完成。

DeepFM

和Wide & Deep的模型类似，DeepFM模型同样由浅层模型和深层模型联合训练得到。不同点主要有以下两点：

wide模型部分由LR替换为FM。FM模型具有自动学习交叉特征的能力，避免了原始Wide & Deep模型中浅层部分人工特征工程的工作

共享原始输入特征。DeepFM模型的原始特征将作为FM和Deep模型部分的共同输入，保证模型特征的准确与一致

DeepFM其中最核心的思想：

没有预训练（no pre-training）

共享 Feature Embedding，没有特征工程（no feature engineering）

同时学习低阶和高阶组合特征（capture both low-high-order interaction features）

CFGAN

生成对抗网络 – GAN 是最近2年很热门的一种无监督算法，它能生成出非常逼真的照片，图像甚至视频。深度学习最特别最厉害的地方就是能够自己学习特征提取。

生成对抗网络（GAN）由2个重要的部分构成：

生成器(Generator)：通过机器生成数据（大部分情况下是图像），目的是“骗过”判别器

判别器(Discriminator)：判断这张图像是真实的还是机器生成的，目的是找出生成器做的“假数据”

训练过程：

第一阶段：固定「判别器D」，训练「生成器G」

第二阶段：固定「生成器G」，训练「判别器D」

第三阶段：循环阶段一和阶段二

通过不断的循环，「生成器G」和「判别器D」的能力都越来越强。

最终我们得到了一个效果非常好的「生成器G」，我们就可以用它来生成我们想要的图片了。

GAN全称对抗生成网络，顾名思义是生成模型的一种，而它的训练则是处于一种对抗博弈状态中的。

CFGAN算法提出了“vector-wise”的方式，对于给定的用户，生成器一次生成其购买向量（Fake Purchase Vectors）；而判别器则用来判别输入的向量是真实的数据还是生成器“伪造”的向量。

在CFGAN中，G生成的是向量称其为购买向量purchase vector。假设我们有基于隐式反馈得到的用户-物品购买矩阵，那么从用户角度来说，购买向量便是矩阵中的一行，若用户与物品有过购买(其实不一定是购买，也可以认为是有过交互），该位置为1，如果没有购买，该位置是空（不是0），从物品角度来说，购买向量便是矩阵中的一列，若物品被用户购买过，该位置为1，如果没有购买过，该位置是空（不是0）。

生成器G的设计
生成器的输入包含两部分，一是用户向量c，另一个是噪声向量z。经过生成器的多层神经网络后，输出用户购买向量。向量中每一个值代表用户与物品交互的概率。这里对输出的购买向量增加了一个mask，mask向量eu中，用户交互过的地方为1，没有交互过的地方为0。用用户购买过的地方去训练，随后预测用户对未购买过的物品的评分。

判别器D的设计
判别器将用户真实的购买向量和G生成的购买向量进行混合，尽可能地将真实向量识别成real，将生成的向量识别成fake。这里同样需要输入用户向量c。

通过负采样的技术，增加一定的负样本。即在每次训练迭代过程中，我们随机选择每个用户的未购买过物品的一部分，将其假设为负样本，然后在训练生成器生成购买向量的时候，使其对应的负样本的值接近0