2019-05-27

FM实践

背景

Fm是工业界比较常用的机器学习算法，在点击预估场景下都能有很好的效果。

FM

FM(Factorization Machine)通过向量交叉学习的方式来挖掘特征之间的相关性,实现组合特征，能够很好的挖掘数据特征间的相关性，可以做分类，排序，回归。适应于高度稀疏的特征矩阵，目标函数及优化学习时候都可以在线性时间完成从而也适合在线学习。适用于ctr点击预估，推荐。

优点

线性复杂度
特征组合
可以处理高度稀疏数据

原理

二阶FM公式：

时间复杂度O($k$$n^2$)，

参数个数为1+n+$\frac{n*k}{2}$

公式可以进一步化简，时间复杂度降低到O($k*$n)，从而适用于工业生产环境及大规模数据

WX20190325-104644@2x

特征交叉

	年龄	北京	上海	广州	男	女
用户1	25	1	0	0	1	0
用户2	17	0	0	1	0	1

普通的线性模型，我们都是将各个特征独立考虑的，并没有考虑到特征与特征之间的相互关系。但实际上，特征之间可能具有一定的关联。

图表中，“北京的男性用户”、“上海的女性用户”这种组合特征可能是有意义并且有用的。

高度稀疏数据

FM在高度稀疏的情况下特征之间的交叉仍然能够估计，而且可以泛化到未被观察的交叉

FM构造特征向量和标签的示例：

WX20190325-104551@2x

每行表示目标 $y^i$ 与其对应的特征向量 $x^i$ ，蓝色框表征当前评分用户，橘色框表征当前被评分电影信息，黄色框表征当前评分用户评分过得所有电影信息，绿色框表征投票时间信息，褐红框表征当前用户最近评分过的一部电影。，最右边的区域是评分。

如上面的例子，可以在上面例子基础上增加新的特征。比如性别，年龄，学历，主题，tag，位置，时间。还可以尝试一些trick。

同时大量类别特征引入，会使得矩阵更加的稀疏。然而FM仍然可以估计特征交叉，同时通过调整k还可以调整模型的泛化能力。

原因如下(原文paper)：

Assume we want to estimate the interaction between Alice (A) and Star Trek (ST) for predicting the target y (here the rating). Obviously, there is no case x in the training data where both variables xA and xST are non-zero and thus a direct estimate would lead to no interaction (wA,ST = 0). But with the factorized interaction parameters ⟨vA,vST⟩ we can estimate the interaction even in this case. First of all, Bob and Charlie will have similar factor vectors vB and vC because both have similar interactions with Star Wars (vSW) for predicting ratings – i.e. ⟨vB,vSW⟩ and ⟨vC,vSW⟩ have to be similar. Alice (vA) will have a different factor vector from Charlie (vC) because she has different interactions with the factors of Titanic and Star Wars for predicting ratings. Next, the factor vectors of Star Trek are likely to be similar to the one of Star Wars because Bob has similar interactions for both movies for predicting y. In total, this means that the dot product (i.e. the interaction) of the factor vectors of Alice and Star Trek will be similar to the one of Alice and Star Wars

优化算法

选用了FTRL。FTRL算法的设计思想是每次找到让之前所有目标函数（损失函数加正则项）之和最小的参数。该算法在处理诸如逻辑回归之类的带非光滑正则化项（如L1正则项）的凸优化问题上表现出色

FTRL是FOBOS和RDA算法的综合

FOBOS。更新w时候对每个维度进行判断，当一个样本的梯度不足以令对应维度上的权重反正较大变化，认为不重要，截断置零。阀值随t减小。
RDA。在sgd基础上。在w更新策略包含一个梯度对w的积分平均值，正则项和辅助的强凸函数。截断阀值不变

FTRL优点：

每次找到让之前所有目标函数（损失函数加正则项）之和最小的参数
算法在提高模型解的稀疏性方面比其他(gd,sgd,momentum)等，效果显著
对每一维分开训练更新，每一维度使用的是不同的学习率。优点是考虑了样本本身在不同特征分布上的不均衡性。

多阶FM

上文提到的FM是2-way(二阶)FM，FM也有多阶的形式。

FM与其他算法对比

FM与协同过滤

协同过滤是FM的一个特例，矩阵分解特征只有用户和商品，而FM可以采用其他特征，学习更多特征组合，更加具有普适性。

FM与决策树

决策树同样可以做特征组合，而且很方便的对特征做高阶组合。但是这种高阶组合需要在数据集里存在。因为这种高阶的特征模式数据不存在的话，或者数据特别少。那么决策树对一个特征分裂后就不会用另一个特征分裂了。所以在高度稀疏的数据中，决策树很难学习到高阶的特征组合

FM与神经网络

神经网络可以对embedding后的稀疏离散特征做更复杂的非线性变换

实践

通过离线模型训练获得模型参数

fm_model = xl.create_fm()
fm_model.setTrain("./Train.txt")
fm_model.setValidate("./Validate.txt")
fm_model.setValidate("./Test.txt")
fm_model.setTXTModel("model.txt")
fm_model.fit(param,"model_output.out")

online使用spark streaming，对实时数据做预测并输出

val warehouse_location = ""
val log: Logger = LoggerFactory.getLogger(this.getClass)
val sparkSession: SparkSession = SparkSession.builder()
     .appName("FM Onling Perdict")
     .config("spark.sql.warehouse.dir", warehouse_location)
     .config("spark.serializer", "org.apache.spark.serializer.KryoSerializer")
     .config("spark.streaming.backpressure.enabled", "true")
     .config("spark.streaming.backpressure.initialRate", 20L).getOrCreate()

val messages = KafkaUtils.createDirectStream[String, String, StringDecoder, StringDecoder](
     ssc, kafkaParameters, topicSet).mapPartitions
val fmode: FMModel = FMWithFTRL.load(**,offlinePara, numFeatures)
fmode.predict()