Factorization Machines算法

Factorization Machines算法

Posted by yougth on March 13, 2019

之前讲过一个SVD算法,它能够通过一个U-I矩阵分解,然后把User和Item分别变成想要的向量表示,然后通过向量相似度的计算做关联推荐或者user2item的推荐。

这个算法有一个局限性,就是它没有办法用到一些重要的特征,如果推荐的优化目标是点击率的话,那么本身Item的点击率是一个很重要的特征,我们有没有办法把这些特征也建模到这个算法中呢,这就是Factorization Machines算法了,中文叫向量分解机,一般直接简称Fm算法。

定义问题

在逻辑回归算法中,我们定义了一个线性模型,基本上是一个最简单的二分类模型,如果问题稍微复杂一点,我们可能要在特征工程上做很多事情,简单来说就是处理特征或者特征组合,那么有没有可能直接把特征组合建模到模型中呢,我们这样定义

特征向量

问题定义好了,但是如果我们直接去求解这个问题的话,有两方面的问题

  1. 这里的是对特征进行one-hot后的,比如itemId或者ItemTag之类本身one-hot后就很稀疏,而我们后面做特征交叉用了,那么就必须保证两个都必须不为0,这对于稀疏矩阵来说很难,这样学习出来模型效果和稳定性无法保证。
  2. 直接去学习的话复杂度是的复杂度,因为n本身就很大,一般都是千万到亿级别的,这个复杂度直接学习比较困难。

问题变换

那么我们借鉴之前SVD的思路,把这个参数矩阵去做分解,变成一个nk的矩阵和一个kn的矩阵的乘积,这样做的好处是对于所有的特征,我们都能够用一个向量(vec)来表示,向量表示后就可以很灵活的计算各种相似度了,这也是现在很火的各种embeding表示的思想。那么我们可以变换为

这里分别是两个向量,表示i,j特征的embeding,但是这样做会发现有一个很大的问题,复杂度变得更高了,变成,别着急,我们变换一下

这里第一步变换中本来两层循环,第二层从i+1开始,但是我们让两个都从1开始,那么相当于算了两次,所以除以二,另外还要去掉对角线上的值。 第二步变换是对矩阵做展开,因为我们前面说了是两个向量,而这个向量是k维的,直接展开之后就多了一层k的循环。 第三步矩阵分解的k维向量提出来放到最外层,最后一步因为都是计算n维向量和x的乘积,所以可以直接合并变成平方。

特征向量

这样下来复杂度变成了,而k « n,计算起来就很容易了。

优势

  • 计算效率高,因为k是一个常数,所以复杂度和lr差不多,训练速度也差不多。
  • 解决矩阵稀疏性问题,通过矩阵分解,让每一个参数通过特征隐含向量的内积表示,能够使得学习更加充分。
  • 提高了模型预估能力,比如用户特征是性别,物品特征是类型,分为汽车和化妆品,而训练数据中没有男性喜欢化妆品,但是假设让我们预估某个男性对化妆品的喜好程度,我们可以直接通过计算男性的embeding向量和化妆品的embeding向量的相似度,同样可以预估。
  • 相比较其他模型,矩阵分解类算法是他的一个特殊情况,之前讲过的SVD,相当于是只有userid和itemid这两类特征的fm。当然另一方面,也可以从这个角度去理解fm算法,比如对于一个nm的U-I矩阵,我们通过矩阵分解为两个矩阵nk和km的乘积,另一方面我们有一个np的item和年龄的矩阵,我们可以分解为两个矩阵nk和kp的矩阵,那么对于这两个物品embeding矩阵n*k显然是不一样的,但是如果我们在fm中userId和年龄特征放进去训练,出来结果会是综合了年龄和userId的,它会把年龄的特征权重也吸收到模型中。
  • 实用性强,可以通过分解后的向量计算向量相似度做u2i或者i2i召回,也可以通过训练做精排模型打分。

求解方法

最简单的就是梯度下降法,模型的各个参数梯度如下。