因子分解机(Factorization Machines)

因子分解机(Factorization Machines)

  • 在推荐系统中,CTR(click-through rate)预估是非常重要的环节,其主要是用于判断一个商品是否被用于推荐。谈到CTR预估,有一个算法不得不提一下,LR(logistic regression)逻辑回归。
  • 在推荐系统发展的历史长河中,LR绝对有浓墨重彩的一笔。比如在2020年和微博做算法的同学交流,对方称他们依旧在推荐中使用LR,当然这离不开其非常容易实现大规模实时并行处理的优势。
  • 我们知道LR模型其实是一种线性的学习模型,所以它并不可以获取一些高阶特征(非线性)的信息。但是我们在处理多特征的推荐模型时,除了单特征外,有时候还想对一些特征进行组合。
  • 关于遇到特征组合的问题,目前主流做法主要分为两类:FM系列、DNN系列。本文将着重介绍FM算法。
  • 文章主要从三方面展开对FM算法介绍
    • When – 什么时候需要考虑FM算法
    • What – 究竟什么是FM算法
    • How – FM怎么使用

1. When

什么时候需要考虑FM算法

需要考虑的情况:

  • 情况一:
    • 在建模过程中,除了考虑单个特征,还需要考虑特征与特征之间的关联信息时。比如,企业产品个性化定价中,我们除了想知道收入水平、教育水平对用户购买会员的影响,还想知道这两者组合起来对购买会员的影响。
  • 情况二:
    • 当特征下包含分类比较多的时候,如果通过one-hot处理,就会形成高维的稀疏矩阵,此时直接计算会导致计算量太大,特征权重更新较慢。比如,依旧是企业中个性化定价项目中,特征职业类别会包含很多分类,one-hot编码后,特征空间一下子就会暴增,导致计算量太大,甚至会形成维灾难。

FM算法的优势就是对上面两种情况的处理。

  • 第一,进行特征组合,通过两两特征组合,引入了交叉项得分;
  • 其次,针对维灾难问题,通过引入隐向量,同时对参数矩阵进行矩阵分解,完成对特征的参数估计。

2. What

究竟什么是FM算法

2.1 简单介绍

  • 因子分解机(Factorization Machines,简称为FM)是2010年由Steffen Rendle提出,是一种基于矩阵分解的机器学习算法。
  • 主要用于解决数据稀疏的业务场景下(如推荐业务),特征怎样组合的问题,可以用于求解分类、回归和排序问题。
  • 原文:Factorization Machines

2.2 公式推导

在引出FM算法前,先看一下线性回归表达式:

y=w0+i=1nwixiy = w_0+\sum^{n}_{i=1}{w_ix_i}

其中w0w_0为偏置,wiw_i为每个特征xix_i对应的权重值。

我们在前面讨论过线性回归模型最大的缺点就是只能解决单个特征或者需要人工进行特征组合,那么是否可以把特征组合的能力体现在模型的层面呢,显然OK,如下公式:

y=w0+i=1nwixi+i=1nj=i+1nwijxixjy = w_0+\sum^{n}_{i=1}{w_ix_i}+\sum^{n}_{i=1}{\sum^{n}_{j=i+1}{w_{ij}x_ix_j}}

上面公式,是把两两组合的特征引入模型了,但是又出现了另一个问题,这个组合的特征泛化能力太弱了,因为如果在训练数据中,xixj=0x_ix_j=0,那么wi,j=0w_{i,j}=0。结果就是wi,jw_{i,j}无法通过训练得出。

为了求解wi,jw_{i,j},我们对每个特征分量xix_i引入辅助向量vi=(vi1,vi2,...,vik)v_i=(v_{i1},v_{i2},...,v_{ik})。然后,利用vivjTv_iv_j^Twijw_{ij}进行求解(根据矩阵分解思路:对于正定矩阵W,存在矩阵V,使得W=VVTW=VV^T);

V=[v11v12v1kv21v22v2kvn1vn2vnk]=[V1V2Vn]V= \left[ \begin{matrix} v_{11} & v_{12} & \cdots & v_{1k} \\ v_{21} & v_{22} & \cdots & v_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ v_{n1} & v_{n2} & \cdots & v_{nk} \\ \end{matrix} \right] = \left[ \begin{matrix} V_{1} \\ V_{2} \\ \vdots \\ V_{n} \\ \end{matrix} \right]

那么wijw_{ij}组成的矩阵可以表示成:

W^=VVT=[V1V2Vn][V1TV2TVnT]\hat{W}=VV^T= \left[ \begin{matrix} V_{1} \\ V_{2} \\ \vdots \\ V_{n} \\ \end{matrix} \right] \left[ \begin{matrix} V_{1}^{T} V_{2}^{T} & \cdots & V_{n}^{T} \\ \end{matrix} \right]

此时,我们就可以得到FM的表达式:

y^(x)=w0+i=1nwixi+i=1nj=i+1n<vi,vj>xixj\hat{y}(x) = w_0+\sum^{n}_{i=1}{w_ix_i}+\sum^{n}_{i=1}{\sum^{n}_{j=i+1}{<v_i,v_j>x_ix_j}}

<vi,vj>=f=1kvifvjf<v_i,v_j> =\sum^{k}_{f=1}{v_{if}v_{jf}}

其中,n是特征数量, viv_{i}是第ii维特征的隐向量, <,>代表向量点积。隐向量的长度为k<<nk<<n,包含 kk个描述特征的因子。

同时,直观判断上面表达式的复杂度是O(kn2)O(kn^2)

FM现在被广泛应用的其中一个优点是可以通过数学公式化解,把原来表面上看起来O(kn2)O(kn^2)的复杂度降低为O(kn)O(kn)。具体的化简过程如下:

image-20210304213009034

此时FM的公式就完全搞定。接下来一起看一下如何更新权重值。

2.3 权值求解

可以采用随机梯度下降法SGD求解参数(当然其他类似SGD的方法都是可以的):

\frac{\partial }{\partial \theta}\hat{y}(X)= \begin{cases} 1, &if\ \theta = w_0\\\ x_i, &if\ \theta = w_i\\\ x_i\sum_{j=1}^n{v_j, fx_j-v_i, fx^2_i}, &if\ \theta =v_{i,f}\\ \end{cases}

image-20210304214706223

其中,j=1nVjfxj\sum^{n}_{j=1}{V_{jf}x_j}和i无关,可以事先求出。计算过程中,每个梯度都可以在O(1)时间内求出,整体的参数更新时间为O(kn)。

经过迭代之后就可以求出结果。

3. How

FM怎么使用

写在最后,产出本篇文档其实主要是为了后面DeepFM文章做铺垫,所以本文讲解重原理轻应用。


参考资料

资料一:Factorization Machines

资料二:https://zhuanlan.zhihu.com/p/58160982

资料三:http://wiki.baidu.com/pages/viewpage.action?pageId=181930125


因子分解机(Factorization Machines)
http://sherwinzhang.com/机器学习/ML/因子分解机(Factorization Machines)/
作者
sherwin
发布于
2021年4月8日
许可协议