FM (Factorization Machine)

一. 应用场景

在计算广告领域,点击率CTR(click-through rate)和转化率CVR(conversion rate)是衡量广告流量的两个关键指标。准确的估计CTR、CVR对于提高流量的价值,增加广告收入有重要的指导作用。预估CTR/CVR,业界常用的方法有人工特征工程 + LR(Logistic Regression)、GBDT(Gradient Boosting Decision Tree) + LR、FM(Factorization Machine)和FFM(Field-aware Factorization Machine)

二.目的

旨在解决稀疏数据下的特征组合问题

三.优点

    • 高度稀疏数据场景;
    • 具有线性的计算复杂度。

四.原理

公示推导

    • 通过组合交叉的特性来学习特征为0样本的权重参数。每个参数 [公式] 的训练需要大量[公式] 和 [公式]都非零的样本;由于样本数据本来就比较稀疏,满足“[公式] 和 [公式]都非零”的样本将会非常少。训练样本的不足,很容易导致参数 [公式] 不准确,最终将严重影响模型的性能;[公式] 和 [公式]的系数分别为 [公式] 和 [公式] ,它们之间有共同项 [公式]即尽管 [公式]为0,但由于[公式]不为0 ,那么就可以通过[公式] 来学习[公式]。也就是说,所有包含“ [公式] 的非零组合特征”(存在某个 [公式] ,使得 [公式] )的样本都可以用来学习隐向量[公式],这很大程度上避免了数据稀疏性造成的影响。而在多项式模型中, [公式] 和 [公式] 是相互独立的。
    • 由于[公式]是对阵矩阵,也即半正定矩阵,这边当作正定矩阵近似求解,这个矩阵就可以分解为 [公式]
    • 由于[公式] 代表向量内积(点乘/数量积),具有对称性,即<a,b>=<b,a>,所以<x_i, x_j>为实对称矩阵,则是对称矩阵,而FM项 是这个对称矩阵的上三角部分(不包含对角线),所以FM项就等于减去对角线再除以2
    • FM的复杂度是 [公式] 。通过计算优化,FM的二次项可以化简,其复杂度可以优化到 [公式]

SGD梯度更新参数

 

其中, [公式] 代表样本的特征数量,[公式]是第 [公式] 个特征的值, [公式] 是模型参数,vi/vj隐向量的长度为 [公式]

五.参考

0