Factorization Machines算法

Factorization Machines算法

Posted by yougth on March 13, 2019

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

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

定义问题

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

特征向量

\[y(x) = w_0 + \sum_{i=1}^n{w_i x_i} = \sum_{i=1}^{n} \sum_{j=i+1}^n w_{i,j} x_i x_j \tag 1\]

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

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

问题变换

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

\[y(x) = w_0 + \sum_{i=1}^n{w_i x_i} = \sum_{i=1}^{n} \sum_{j=i+1}^n <v_i,v_j> x_i x_j \tag 2\]

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

\[\begin{eqnarray*} combine & = & \sum_{i=1}^n \sum_{j=i+1}^n <v_i, v_j> x_i x_j \\ & = & \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n <v_i,v_j>x_i x_j - \frac{1}{2} \sum_{i=1}^n <v_i,v_i> x_i x_i \\ & = & \frac{1}{2} (\sum_{i=1}^n \sum_{j=1}^n \sum_{f=1}^k v_{i,f} v_{f,j} x_i x_j - \sum_{i=1}^n \sum_{f=1}^k v_{i,f} v_{i,f} x_i x_i ) \\ & = & \frac{1}{2} \sum_{f=1}^k[(\sum_{i=1}^n v_{i,f} x_i)*(\sum_{j=1}^n v_{j,f x_j}) - \sum_{i=1}^n x_{i,f}^2 x_i^2 ] \\ & = & \frac{1}{2} \sum_{f=1}^k[(\sum_{i=1}^n v_{i,f} x_i)^2 - \sum_{i=1}^n v_{i,f}^2 x_i^2] \end{eqnarray*} \tag 3\]

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

特征向量

这样下来复杂度变成了\(O(kn)\),而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召回,也可以通过训练做精排模型打分。

求解方法

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

\[\frac{\partial}{\partial \theta} = \left\{ \begin{aligned} 1 & , & \ \ \ \ if \ \theta \ is \ w_0 \\ x_i & , & \ \ \ if \ \theta \ is \ w_i \\ x_i \sum_{j=1}^n v_{j,f} x_j - v_{i,f} x_i^2 & , & \ \ \ \ if \ \theta \ is \ v_{i,f} \end{aligned} \right.\]

ffm

ffm顾名思义,引入filed -aware概念,之前fm每个特征做交叉的时候为两个向量的乘积,比如上面的女性对化妆品偏好,北京人群对化妆品的偏好,按照fm,化妆品对女性和对base北京计算权重用的是相同的向量,但是很显然这两个差异很大,计算为一个会引入很大的噪声。

所以ffm就是来解决这个问题的,对于不同类型的特征使用不停的field,比如上面,化妆品会计算多个向量,之后给性别用一套向量,给所在地城市用一套向量。

\[y(x) = \sum_{i=1}^{n} \sum_{j=i+1}^n <v_{i,f1},v_{j,f2}> x_i x_j \tag 4\]

引入feild之后,模型首先更精确符合实际情况了,但是但来一个问题是复杂度变大,变成f * k * n。