机器学习 | 三分钟带你了解最流行的在线学习算法

引言：本文由梯度科技高级大数据开发工程师黄泽邦撰写，针对目前非常流行的机器学习场景，主要介绍在线学习相较于离线学习的优势和必要性、在线学习相关算法、FTRL算法以及该算法在flink实时流计算上的应用。

离线的机器学习开发流程基本是以下步骤： 

(1)批量数据融合，特征工程。

(2)构建训练模型（LR、GBDT等），评估模型效果。

(3)保存模型并部署线上使用。

但是离线学习仍存在不少缺陷：

批量离线算法中每次迭代对全体训练数据集进行计算（例如计算全局梯度）， 虽然有分布式大规模的机器学习平台如spark，精度和收敛还可以，但是在某种程度上批处理方法对训练样本的数量还是有限制的，无法有效处理超高维度的大数据集（此时全局梯度计算代价太大），且没法应用于数据流做在线学习。

在线学习则是指，每次来一个样本，利用一个迭代方法更新模型变量，使得当前期望损失最小。

相对于离线学习来说，在线学习会根据线上的预测结果动态调整模型，加入模型预测错误，从而及时做出修正，将最新的数据反馈至模型中，减少了模型的延时性。这些优势使其在工业界有较多应用，例如风险评分、CTR和推荐系统等。

它不需要加载所有数据进内存，以流式的处理方式可以处理任意数量的样本，因此可以处理大维度数据训练。

不是所有的批计算算法都适合做流式算法，只有那些损失函数易于计算的算法才比较适合做成流式计算。这里有两种，贝叶斯概率回归、梯度下降法。

给定参数先验，根据反馈计算后验，将其作为下一次预测的先验，然后再根据反馈计算后验，如此进行下去，就是一个在线学习的过程。但是这种方法有个不足之处，就是贝叶斯模型参数无法稀疏化，所需资源较大。

最经典的损失函数计算方法是梯度下降法了。

用梯度下降法来求解损失函数的算法有：逻辑斯蒂回归（LR）、感知机、线性回归等。

这类模型天然适合在线学习业务，可通过流数据，一边预测，一边进行模型参数的自更新迭代。

对流数据中的每一条数据，使用梯度下降法来迭代模型参数，由于目标函数的梯度向量计算中只需要进行向量间的点乘和相加，可以很容易将每个迭代过程拆分成相互独立的计算步骤，由不同的节点进行独立计算，然后归并计算结果。

按数据行来进行并行训练解决了模型训练中的样本数量问题，但是实际情况中会出现超高维特征的情况（如上千万的离散维度），仅仅按行进行并行处理，无法满足该类场景，因此还需按列将高维特征向量拆分成若干小的向量进行求解。将样本矩阵按行划分，将样本特征向量分布到不同的计算节点，由各计算节点完成自己所负责样本的点乘与求和计算，然后将计算结果进行归并。

以LR为例，通过LR的随机梯度（SGD）下降并不能很好的解决超大规模数据集在线数据流时的问题，随机梯度下降每次参数的更新并不是沿着全局梯度进行下降的，而是沿着某个样本产生的梯度方向下降，很可能陷入局部最优解。SGD算法已经不适用，必须提出新的优化算法。

那么这里就又引出了一个专门针对在线学习思想做优化的算法：FTRL（Follow The Regularized Leader）。

FTRL（Follow The Regularized Leader）就是google在这样的背景下研发出来的，当时Google在2013年KDD上发表了FTRL算法后，在业界引起了巨大的反响，国内外各大IT公司纷纷上线该算法，在推荐系统，CTR等业务中，具有广泛的应用。

FTRL算法的损失函数，一般也不是能够很快求解的，这种情况下，一般需要找一个代理的损失函数。

代理损失函数需要满足几个要求：1. 代理损失函数比较容易求解，最好是有解析解 2. 优化代理损失函数求的解，和优化原函数得到的解差距不能太大，所以算法引入了regret的概念。

其中 t 表示总共 T 轮中的第 t 轮迭代，l_t表示损失函数，w 表示要学习的参数。Regret 字面意思是 “后悔度”，即更新完不后悔，表示 "代理函数求出来的解" 离 "真正损失函数求出来的解" 的损失差距。

当然这个损失必须满足一定的条件，在线学习才可以有效，则：

随着训练样本的增多，这两个优化目标优化出的参数的实际损失值差距越来越小，即随着训练样本的增加，代理损失函数和原损失函数求出来的参数的实际损失值差距越来越小。

Per-Coordinate 意思是FTRL是对w每一维分开训练更新的，每一维使用的是不同的学习速率，也是上面代码中λ_2之前的那一项。与w所有特征维度使用统一的学习速率相比，这种方法考虑了训练样本本身在不同特征上分布的不均匀性，如果包含w某一个维度特征的训练样本很少，每一个样本都很珍贵，那么该特征维度对应的训练速率可以独自保持比较大的值，每来一个包含该特征的样本，就可以在该样本的梯度上前进一大步，而不需要与其他特征维度的前进步调强行保持一致。

输入的α、β是用来调节学习率的超参数。

再看下一时刻的特征权重的更新公式，增加理解。

现实场景中对于模型的稀疏性也很看重。上亿的特征并不鲜见，模型越复杂，需要的存储、时间资源也随之升高，而稀疏的模型会大大减少预测时的内存和复杂度。另外稀疏的模型相对可解释性也较好，这也正是通常所说的 L1 正则化的优点。而为了得到平滑解，则可加入L2正则项。

1. Probabilistic Feature Inclusion：丢弃训练数据中很少出现的特征。离线训练可以通过预处理过滤，这里给出了两个在线训练的方法。

2. Encoding Values with Fewer Bits：由于需要保存的数据一般处于[-2,2]之间所以使用64位浮点数存储浪费了空间。它使用小数点前2位小数点后13位正负号的数值型编码保存浮点数。这样可以节省75%的内存，并且准确度基本没有损失。

3. Training Many Similar Models：当需要训练多个模型的变种时，每个模型都单独训练会浪费很多资源；如果把一个固定的模型作为先验学习残差，无法处理移除或替换特征的情况。经过观察发现：每一维的特征都跟特定的数据有关，每个模型的变种都有自己独特的数据。因而，可以用一张hash表来存储所有变种的模型参数，以及该特征是哪个变种模型。

4. A single Value Structure：当模型需要增加或者减少一批特征时，此时共享的特征只保留一份，用一个位数组来记录某个特征被哪些模型变种共享。对于一个样本，计算所有模型的更新值并取平均值更新共享参数。

5. Computing Learning Rates with Counts：使用正负样本的比例来近似计算梯度的和。

6.  Subsampling Training Data：实际训练中，正样本相对负样本（如CTR中未被点击的样本数据）的总数是非常小的，负样本按r的概率采样在训练时乘一个1/r的权重来弥补正样本的缺失。

Flink是当前流行的分布式流处理框架，其能实现高吞吐低延时，轻量级容错机制，且在同一时间允许系统维持高吞吐率和提供exactly-once的一致性保证。但是其原有的mllib库并不完善，Alink 是阿里巴巴基于实时计算引擎 Flink 研发的新一代机器学习算法平台，是业界首个同时支持批式算法、流式算法的机器学习平台。下面就针对Alink里的FTRL算法实例进行解析。

由于Alink实现的是LR+FTRL，那么首先需要训练出一个逻辑回归模型作为FTRL算法的初始模型，满足系统冷启动的需要。同时在特征处理数据的时候，可以将负样本乘以一个1/r的权重，或正样本乘以一个r的权重来弥补正样本的缺失造成的欠拟合。

BatchOperator initData = new RandomTableSourceBatchOp()                .setNumCols(5)                .setNumRows(100L)                .setOutputCols(new String[]{"f0", "f1", "f2", "f3", "label"})                .setOutputColConfs("label:weight_set(1.0,1.0,2.0,5.0)"); BatchOperator initModel = new LogisticRegressionTrainBatchOp()                .setFeatureCols(new String[]{"f0", "f1", "f2", "f3"})                .setLabelCol("label")                .setMaxIter(10).linkFrom(initData);

接下来设置Ftrl在线学习模型，可以看到，根据上面介绍的原理，设置alpha、beta学习参数，L1、L2正则化参数提高模型参数稀疏性、获得平滑解，以及设置特征向量长度，实现维度切分分布式训练。

StreamOperator  smodel = new FtrlTrainStreamOp(initModel)                .setFeatureCols(new String[]{"f0", "f1", "f2", "f3"})                .setLabelCol("label")                .setTimeInterval(10)                .setAlpha(0.1)                .setBeta(0.1)                .setL1(0.1)                .setL2(0.1)                .setVectorSize(1000)                .setWithIntercept(true)                .linkFrom(dataWithLabel);

然后在FTRL的基础上，连接预测数据进行预测。

StreamOperator predict = new FtrlPredictStreamOp(initModel)                .setPredictionCol("pred")                .setReservedCols(new String[]{"label"})                .setPredictionDetailCol("details")                .linkFrom(smodel, data);

筛选auc和精确度高于阈值的模型，并保存好。

StreamOperator  sfmodel = new FtrlModelFilterStreamOp()                .setAucThreshold(0.5)                .setAccuracyThreshold(0.5)                .setPositiveLabelValueString("1.0")                .setLabelCol("label").linkFrom(smodel, dataWithLabel);
 sfmodel.linkFrom(dataWithLabel).link(                new AppendModelStreamFileSinkStreamOp()                        .setFilePath("/tmp/lr_model_stream")                        .setNumKeepModel(10) // 保存模型上限        );

这里不针对Alink源码做主要解析，只对其中的工作流做一个基本描述，详情解析请查看源码或其他相关文档。

1）加载初始化模型，可提前训练好一个模型，或者获取上一次断开实时流服务前所保留的最后模型，作为初始化输入。

2）获取FTRL相关参数，初始化数据做了特征哈希，会产生高维向量，进行高维向量切割。

3）Alink里会构建两个数据流：训练流和反馈流，训练流会分布式计算FTRL迭代所需的预测部分，反馈流则分布式处理（时间未过期、向量有意义）的反馈数据，并更新参数。

4）归并这些预测计算结果，如果满足条件则归并模型 ，并向下游算子输出模型。

5）符合标准（时间过期了）的数据将跳出迭代，转发给下游operator（也就是在线预测阶段），即定时把模型更新给在线预测阶段。

6）为了避免异常情况出现，也可以将流模型保存到内存数据库、hdfs中，以便下次重启动的时候，可以加载上次停止之前的模型。

FTRL从算法逻辑上来讲跟批算法没有太大改变，只不过FTRL算法在流式的模型训练过程中对于稀疏数据以及大维度模型训练方面有比较好的效果。

在线学习的场景，其广泛应用于推荐系统，异常检测等业务中。这些场景都有一个相似点：需要获取预测目标近期的行为数据来判断预期行为。

以CTR预测为例（Click-Through-Rate）在推荐系统中，当你通过协同过滤算法得出一批物品、商品后，需要针对这些东西进行一个再排序，来确定先推荐哪些最可能被点击到的商品。那怎么确定谁最可能被点击呢，就用到CTR预测了。

即是预测该商品是否会被点击、购买，预测得分最高者，则被最先推荐给用户。

一般来说，用户针对物品的特征行为，有以下这几大类：评分、投票、转发、标记、评论、点击类别、页面停留时间等。为了不流失太多用户的特征信息，在构造分类特征的时候会使用大量的one-hot编码，而针对这些大类构造出来的特征，往往会有上万甚至上百万维。

那么，这时候使用在线学习FTRL算法，则是一个很好的选择。它可以分布式计算超高维特征，以及快速迭代模型以适应用户最近的行为，提高预测准确率。

参考资料