推荐系统 - FM模型

1. 模型演进 LR -> POLY2 -> FM -> FFM

1.1 LR模型 - 融合多种特征的推荐模型

线性回归模型数学表达式如下：
$\begin{align} \hat{y}(x) &= w_0 + \sum_{i=1}^{n} w_ix_i \\ &= \sum_{i=0}^{n} w_ix_i \end{align}$
逻辑回归数学表达式如下：
$\hat{y}(x) = \frac{1}{1 + e^{-w^Tx}}$
逻辑回归模型的优缺点：（1）相比协同过滤模型仅利用用户与物品的相互行为信息进行推荐，逻辑回归模型能够综合利用用户、物品、上下文等多种不同的特征，生成较为全面的推荐结果；（2）逻辑回归的另外一种表现形式的感知机作为神经网络中最基础的单一神经元，是深度学习的基础性结构；（3）可解释性强：逻辑回归的数学形式是各特征的加权合，再施以sigmoid函数。逻辑回归的简单数学形式非常符合人类对预估过程的直观认知。（4）逻辑回归模型的局限性：表达能力不强，无法进行特征交叉；需要人工进行特征交叉。

逻辑回归模型参数估计参考：https://www.jianshu.com/p/f7b6cd2f8567

1.2 POLY2模型 - 特征交叉的开始

针对特征交叉问题，算法工程师经常采用先手动组合特征，再通过各种分析手段帅选特征的方法，但该方法是比较低效率的；因此采用POLY2模型进行特征的“暴力”组合成了可行的选择。
$\hat{y}(x) = w_0 + \sum_{i=1}^{n} w_ix_i + \color{blue}{\sum_{i=1}^{n} \sum_{j=i+1}^{n} w_{i,j} x_i x_j}$
从上述公式可以看到，POLY2（多项式核SVM）对所有特征进行了两两交叉（ $x_i, x_j$ ），并对所有的特征组合赋予权重 $w_{i,j}$ [标量]。POLY2通过暴力组合特征的方式，在一定程度上解决了特征组合的问题。POLY2模型本质上仍是线性模型，其训练方法与逻辑回归并无区别，因此便于工程上的兼容。
POLY2模型存在两个较大的缺陷： （1）在处理互联网数据时，经常采用one-hot编码的方式处理类别数据，致使特征向量极度稀疏，POLY2进行无选择的特征交叉。原本就稀疏的特征向量更加稀疏，导致大部分交叉特征的权重缺乏有效的数据进行训练，无法收敛。（2）权重参数的数量由 $n$ 直接上升至 $n^2$ ，极大地增加了训练复杂度。

1.3 FM模型 - 隐向量特征交叉

为了解决POLY2模型的缺陷，2010年Rendle提出了FM模型；与POLY2相比，其主要的区别是用两个向量的内积（ $<v_i, v_j>$ [向量]）取代了单一的权重系数 $w_{i,j}$ 。具体来说，FM为每个特征学习了一个隐权重向量（latent vector），在特征交叉时，使用两个特征隐向量的内积作为交叉特征的权重。

$\hat{y}(x) = w_0 + \sum_{i=1}^{n} w_ix_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \color{blue}{<v_i, v_j>} x_i x_j$

向量内积运算.png

本质上，FM引入隐向量的做法，与矩阵分解用隐向量代表用户和物品的做法异曲同工。可以说，FM是将矩阵分解隐向量的思想进行了进一步扩展，从单纯的用户、物品隐向量扩展到所有特征上。 FM通过引入特征隐向量的方式，直接把POLY2模型 $n^2$ 级别的权重参数数量减少到了 $nk$ （ $k$ 为隐向量维度， $n>>k$ ）
隐向量的引入使得FM能够更好地解决数据稀疏性问题。 例如，在某商品推荐的场景下，样本有两个特征，分别是channel和brand。某训练样本的特征组合是(ESPN, Adidas)。在POLY2中，只有当ESPN和Adidas同时出现在一个训练样本时，模型才能学到这个组合特征对应的权重。而在FM中，ESPN的隐向量也可以通过(ESPN, Gucci) 样本进行更新，Adidas的隐向量也可以通过(NBC, Adidas)样本进行更新，这大幅度降低了模型对数据稀疏性的要求。甚至对于一个从未出现过的特征组合(NBC, Gucci)，由于模型之前已经分别学习过NBC和Gucci的隐向量，具备了计算该特征组合权重的能力，这是POLY2无法实现的。

1.4 FFM模型 - 引入特征域的概念

相比FM模型，FFM模型引入了特征域感知（field-aware）这一概念，使模型的表达能力更强。假设样本的 $n$ 个特征属于 $f$ 个field，那么FFM的二次项有 $nf$ 个隐向量。而在FM模型中，每一维特征的隐向量只有一个。FM可以看做FFM的特例，是把所有特征都归属到一个field的FFM模型。FFM模型公式如下：
$\hat{y}(x) = w_0 + \sum_{i=1}^{n} w_ix_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \color{blue}{<v_{i, f_j}, v_{j, f_i}>} x_i x_j$
上式中， $f_j$ 是第 $j$ 个特征所属的field；当 $x_i$ 与 $x_j$ 进行特征交叉时， $x_i$ 从其 $f$ 个隐向量中挑选出 $v_{i, f_j}$ 与特征 $x_j$ 进行交叉。如果隐向量长度为 $k$ ，那么FFM的二次参数有 $\color{red}{n*f*k}$ 个，远远多于FM模型的 $nk$ 个。此外，由于隐向量与field相关，FFM二次项并不能够化简，其计算复杂度是 $\color{red}{O(k*n^2)}$ 。
【特征域的概念解释】 简单地讲，“域”代表特征域，域内的特征一般采用one-hot编码形成的一段one-hot特征向量。例如，用户的性别分为：男，女，未知三类。那么对于一个女性用户来说，采用one-hot方式编码的特征向量为[0,1,0]，这个三维的特征向量就是一个“性别”特征域。将所有特征域拼接起来，就组成了样本的整体特征向量。
FFM原理举例说明，假设在训练推荐模型过程中接收到的训练样本如下。其中Publisher、Advertiser、Gender就是三个特征域，ESPN、NIKE、Male分别是这三个特征域的特征值（需要转化成one-hot特征）； 如果按照FM的原理，特征ESPN、NIKE和Male都有对应的隐向量 $w_{ESPN}, w_{NIKE}, w_{Male}$ ，那么ESPN特征与NIKE特征、ESPN特征与Male特征做交叉的权重应该是 $<w_{ESPN}, w_{NIKE}>$ 和 $<w_{ESPN}, w_{Male}>$ ，其中ESPN对应的隐向量 $w_{ESPN}$ 在两次特征交叉过程中是不变的。而在FFM中，ESPN与NIKE、ESPN与Male交叉时候特征是不一样的，分别是 $<w_{ESPN, A}, w_{NIKE, P}>$ 和 $<w_{ESPN, G}, w_{Male, P}>$ ；这就是FM和FFM主要的差别。

image.png

2. 如何提升FM计算效率？

对于FM模型二阶项（ $\sum_{i=1}^{n} \sum_{j=i+1}^{n} <v_i, v_j> x_i x_j$ ）的时间复杂度为: $\color{red}{O(k*n^2)}$ ，对二阶项进行改写后的时间复杂度为： $\color{red}{O(k*n)}$ ，其中 $n$ 是特征数量， $k$ 表示隐向量维度。

$\begin{align} & \sum_{i=1}^{n} \sum_{j=i+1}^{n} \color{blue}{<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 \tag{step1}\\ & =\frac{1}{2} \left( \sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{f=1}^{k} v_{i,f} v_{j,f} x_i x_j - \sum_{i=1}^{n} \sum_{f=1}^{k} v_{i,f} v_{i,f} x_i x_i \right) \tag{step2}\\ & =\frac{1}{2} \sum_{f=1}^{k} \left( \left(\sum_{i=1}^{n} v_{i,f}x_i \right) \left( \sum_{j=1}^{n} v_{j,f}x_j \right) - \sum_{i=1}^{n} v_{i,f}^2 x_i^2 \right) \tag{step3}\\ & =\frac{1}{2} \sum_{f=1}^{k} \left( \left(\sum_{i=1}^{n} v_{i,f}x_i \right)^2 - \sum_{i=1}^{n} v_{i,f}^2 x_i^2 \right) \tag{step4} \\ \end{align}$

【step1】计算说明如下：FM二阶项计算的是下面所有黄色正方形相加之和；

step1计算说明.png
【step2】比较好理解，就是把 $<v_i, v_j>$ 的计算展开： $\sum_{f=1}^{k} v_{i,f} v_{j,f}$
【step3】计算说明如下：可以假设 $n=4, k=2$ ；

step3计算说明.png
【step4】说明： $\left(\sum_{i=1}^{n} v_{i,f}x_i \right)$ 和 $\left( \sum_{j=1}^{n} v_{j,f}x_j \right)$ 是相等的，因为是在隐向量的第 $f$ 维，对所有特征求和；

step4计算说明.png

3. MF与FM模型的关系？

MF（Matrix Factorization，矩阵分解）模型是在推荐系统领域资深的协同过滤模型。核心思想是通过两个低维小矩阵（一个代表用户embedding矩阵，一个代表物品embedding矩阵）的乘积计算，来模拟真实用户点击或评分产生的大的协同信息稀疏矩阵。当训练完成，每个用户和物品得到对应的低维embedding表达后，如果要预测某个用户 $User_i$ 对 $Item_j$ 的评分的时候，只要它们做个内积运算 $<User_i, Item_j>$ ，这个得分就是预测得分。

矩阵分解模型.png
本质上，MF模型是FM模型的特例，MF可以认为是只有User ID和Item ID这两个特征Fields的FM模型；MF将这两类特征通过矩阵分解，来达到将这两类特征embedding化表达的目的。 而 FM可以看做是MF模型的进一步扩展，除了User ID和Item ID这两类特征外，很多其它类型的特征，都可以进一步融入FM模型里，它将所有这些特征转化为embedding低维向量表达，并计算任意两个特征embedding的内积，就是特征组合的权重。

MF与FM的关系.png

参考资料

FM论文：Factorization Machines https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf
FFM论文：Field-aware Factorization Machines for CTR Prediction https://www.csie.ntu.edu.tw/~cjlin/papers/ffm.pdf
《深度学习推荐系统》 - 王喆
推荐系统召回四模型之：全能的FM模型 https://zhuanlan.zhihu.com/p/58160982
深入FFM原理与实践 https://tech.meituan.com/2016/03/03/deep-understanding-of-ffm-principles-and-practices.html

最后编辑于：2021.06.20 17:38:51

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,772评论 6赞 477
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,458评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,610评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,640评论 1赞 276
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,657评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,590评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,962评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,631评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,870评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,611评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,704评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,386评论 4赞 319
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,969评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,944评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,179评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 44,742评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,440评论 2赞 342