FTRL&FM

smartcat2010

已于 2022-02-05 20:05:33 修改

阅读量3.4k

点赞数

分类专栏：机器学习推荐系统算法工程文章标签：机器学习深度学习算法

于 2016-11-16 15:06:38 首次发布

本文链接：https://blog.csdn.net/smartcat2010/article/details/53186746

版权

推荐系统同时被 3 个专栏收录

44 篇文章

订阅专栏

算法工程

27 篇文章

订阅专栏

机器学习

21 篇文章

订阅专栏

1. Feature Retire: 防止随着训练持续进行，模型越来越大；将较长时间不修改的feature，从模型中删去；

2. Dump模型，w,q,z必须Dump出来，用来断点恢复；w单独dump出来，用来给Prediction-Cluster进行预测；

3. 在线最优化求解冯扬

FTRL最优化问题的公式里，包含3个部分：迎合过往梯度，正则化增加稀疏性，别离以往的W偏离过远；

4.Ad Click Prediction: a View from the Trenches(2013)

【工程实现中的memory saving策略】

　　这里对google所提的一些节省内存的实现细节做一个介绍

Predict时的memory saving：

　　　　–L1范数加策略，训练结果w很稀疏，在用w做predict的时候节省了内存，很直观，不细说了

我的理解：FTRL的原始公式，当L1正则项系数为0时，等价于普通的SGD，从最终w求解的公式里可以看到。如果上线之后不再更新特征参数，则FTRL的L1正则可以在不影响AUC的情况下削减很多参数值到0，从而减少参数量（online learning是下面的介绍：）；可以只存储n和z，w在计算的时候现用n和z来计算得到；

Training时的memory saving：

在线丢弃训练数据中很少出现的特征(probabilistic feature inclusion)，但是对于online set，对全数据进行pre-process查看哪些特征出现地很少、或者哪些特征无用，是代价很大的事情，所以要想训练的时候就做稀疏化，就要想一些在线的方法（FTRL分开更新的w各维度，每一维不同的步长，per-coordinate）

　　　　1）Poisson Inclusion：对某一维度特征所来的训练样本，以p的概率接受加入模型；（被模型接受时，出现次数的数学期望 = p*1+(1-p)*p*2+(1-p)^2*p*3+... ==>拆分成[p*1+(1-p)*p*1+(1-p)^2*p*1+...]+[(1-p)*p*1+(1-p)^2*p*1+...]+...这样的多组等比数列=1/p

　　　　2）Bloom Filter Inclusion：用bloom filter做某一特征出现k次才加入模型; （因为bloom filter有可能出现冲突，所以有可能让少于k次的特征提前加入模型）(此法在和1相同特征节省率时，AUC表现更好，可能是因为1会更多的误杀频繁特征）

　　2. 浮点数重新编码

　　　　1)　　特征权重不需要用32bit或64bit的浮点数存储，存储浪费空间（因为大部分权值都在(-2,2)范围内)

　　　　2)　　16bit encoding(定点编码：1个符号位，2个整数位，13个小数位），但是要注意处理rounding技术对regret带来的影响（不懂。。。）

　　3. 训练若干相似model

　　　　1）对同一份训练数据序列，同时训练多个相似的model

　　　　2）这些model有各自独享的一些feature，也有一些共享的feature

　　　　3）出发点：有的特征维度可以是各个模型独享的，而有的各个模型共享的特征，可以用同样的数据训练。

我的理解：A/B测试时，把多份模型部署到一个分布式哈希表里，同1个Key下面存储1～N个模型的统计量（没有该feature的模型，就用全0特别是学习率为0来表示，这样紧凑数组格式）；优点：1. 节省Key的存储空间；2. 如果同时训练，可以只读一次训练数据（节省网络或磁盘IO），只生成一次特征（节省CPU），只传输一遍w和g（节省网络），只更新一遍w(节省哈希查找次数）；如果不能做多不同模型之间的同时同步训练，至少可以A/B两个模型共用一份参数服务器；

　　4. Single Value Structure（据说有公司已经在实际中这么搞，大数据量下也能够保证不错的auc）

　　　 1）多个model公用一个feature存储（例如放到cbase或redis中），各个model都更新这个共有的feature结构

　　　 2）对于某一个model，对于他所训练的特征向量的某一维，直接计算一个迭代结果并与旧值做一个平均

真的是把所有模型在同一个特征值上的统计量做了平均处理；google说这样大胆的近似不影响效果，但我感觉用这个来做A/B测试似乎不太好，不太严谨；

5. 使用正负样本的数目来计算梯度的和（所有的model具有同样的N和P）

p就是本次sigmoid(x)的值，假设模型已经训练的很准确了，那么p就近似等于P/(P+N)，P是该特征上见过的正样本数目，N是该特征上见过的负样本数目；如果使用方法3的多模型共享哈希表，则所有模型，在同一个特征上，P和N是相同的，所以可以只存储一份，开销被均摊了；

　　6. Subsampling Training Data

　　　　1）在实际中，CTR远小于50%，所以正样本更加有价值。通过对训练数据集进行subsampling，可以大大减小训练数据集的大小

　　　　2）正样本全部采（至少有一个广告被点击的query数据），负样本使用一个比例r采样（完全没有广告被点击的query数据）。但是直接在这种采样上进行训练，会导致比较大的biased prediction

　　　　3）解决办法：训练的时候，对样本再乘一个权重。权重直接乘到loss上面，从而梯度也会乘以这个权重。

　　　　　我的理解：先采样减少负样本数目（即减少训练时间），在训练的时候再用权重加大来弥补负样本数目的变少，使得在最终损失函数上是等价的。（只是为了减少训练时间，不是为了处理样本不均衡的问题）

人家用可视化方式，查看不同slice data上的指标升降情况；slice可以按照query-topic划分，可以按照国家划分，...；格子宽度可以表示样本数或者点击数；因为指标的变动可能在某些样本上提升有些样本上下降，这样细致分析，就可以看出新模型对哪些人群样本有提升哪些有下降；有些精细化运营的意味；

5. xgBoost有连续特征；FTRL要对连续特征进行分桶；

xgBoost大约1万个特征效果饱和；FTRL可以更多的特征，减轻特征工程的工作量；

二. FM

http://geek.csdn.net/news/detail/112231

每一个特征xi，有自己的“词向量”vi

在数据稀疏性普遍存在的实际应用场景中，二次项参数的训练是很困难的。原因是，每个参数 wij的训练需要大量 xi 和 xj 都非零的样本；由于样本数据本来就比较稀疏，满足“xi 和 xj 都非零”的样本将会非常少。训练样本的不足，很容易导致参数wij 不准确，最终将严重影响模型的性能。

如何解决二次项参数的训练问题呢？矩阵分解提供了一种解决思路。model-based的协同过滤中，一个rating矩阵可以分解为user矩阵和item矩阵，每个user和item都可以采用一个隐向量表示。两个向量的点积就是矩阵中user对item的打分。

具体来说，xhxi 和 xixj 的系数分别为〈vh,vi〉和〈vi,vj〉，它们之间有共同项 vi。也就是说，所有包含“xi 的非零组合特征”（存在某个 j≠i，使得 xixj≠0）的样本都可以用来学习隐向量 vi，这很大程度上避免了数据稀疏性造成的影响。而在多项式模型中，whi 和 wij 是相互独立的。