FM 原理及在召回中的应用(python实现)
1. 综述
为了学习推荐系统的召回模型,首先梳理了一下FM模型,权当是学习笔记,记录一下。
FM(Factor Machine,因子分解机)算法是一种基于矩阵分解的机器学习算法,是为了解决大规模稀疏矩阵中特征组合问题。它是一种通用的预测方法,在即使数据非常稀疏的情况下,依然能估计出可靠的参数进行预测。与传统的简单线性模型不同的是,因子分解机考虑了特征间的交叉,对所有嵌套变量交互进行建模(类似于SVM中的核函数),因此在推荐系统和计算广告领域关注的点击率CTR(click-through rate)和转化率CVR(conversion rate)两项指标上有着良好的表现。此外,FM的模型还具有可以用线性时间来计算,以及能够与许多先进的协同过滤方法(如Bias MF、svd++等)相融合等优点,也被广泛的应用于召回模型中。
本文的主要组织思路如下:
- 为什么提出FM(演进)
- FM具体是什么(原理)
- FM模型在召回中的应用
- 具体怎样应用
2. FM演进
为什么会提出FM模型,下面我从两个角度来简单介绍下FM模型,一个角度是从特征组合模型的进化角度来讲;另外一个角度从协同过滤模型的进化角度来讲。FM模型刚好处于这两类模型进化的交汇口。
- 特征组合角度
这条路径主要的演进路线是从LR到SVM再到FM模型。LR模型是CTR预估领域早期成功的模型,在深度学习大规模应用之前,大多工业推荐排序系统采取LR这种“线性模型+人工特征组合引入非线性”的模式,具体公式表达如图1所示。因为LR模型具有简单方便易解释容易上规模等诸多好处,所以目前仍然有不少实际系统仍然采取这种模式。但是,LR模型最大的缺陷就是人工特征工程,耗时费力,并且浪费人力资源,那么能否将特征组合的能力体现在模型层面呢?
为了解决上述的问题,可以直接在图1中的线性公式中直接加入二阶特征组合即可,具体得到图2 所示公式。任意两个特征进行组合,可以将这个组合出的特征看作一个新特征,融入线性模型中。而组合后的特征权重和一阶特征类似可以直接在训练阶段学习得到。其实这种二阶特征组合的使用方式,和多项式核SVM是等价的。虽然这个模型看上去貌似解决了二阶特征组合问题了,但是它有个潜在的问题:它对组合特征建模,泛化能力比较弱。这里举一个例子加深理解,如果设计一个电影评分系统,现在组合特征是用户U对电影M的评分,在数据集合中如果用户张三$x_{张三}$没有评论电影$x_{大话西游}$的记录,如果想要估计张三和大话西游之间,或者说特征分量$x_{张三}$和$x_{大话西游}$之间的相互关系,显然会得到稀疏$\omega_{张三,大话西游}=0$。即对于观察样本中未出现过交叉的特征分量,不能对相应的参数进行估计。尤其是在大规模稀疏特征存在的场景下,这个毛病尤其突出。比如CTR预估和推荐排序,这些场景的最大特点就是特征的大规模稀疏。所以上述模型并未在工业界广泛采用。那么,有什么办法能够解决这个问题吗?
于是,FM模型此刻可以闪亮登场了。如图3所示,FM模型也直接引入任意两个特征的二阶特征组合,和SVM模型最大的不同,在于特征组合权重的计算方法。FM对于每个特征,学习一个大小为k的一维向量,于是,两个特征 $x_i$和$x_j$的特征组合的权重值,通过特征对应的向量 $v_i$ 和$v_j$的内积$<v_i,v_j>$ 来表示。这本质上是在对特征进行embedding化表征,和目前非常常见的各种实体embedding本质思想是一脉相承的,但是很明显在FM这么做的年代(2010年),还没有现在能看到的各种眼花缭乱的embedding的形式与概念。所以FM作为特征embedding,可以看作当前深度学习里各种embedding方法的老前辈。当然,FM这种模式有它的前辈模型吗?有,等会会谈。其实,和目前的各种深度DNN排序模型比,它仅仅是少了2层或者3层MLP隐层,用来直接对多阶特征非线性组合建模而已,其它方面基本相同。
为什么fm这种通过embedding模式能够解决上述稀疏特征下泛化能力弱的问题?如图3所示,如果$x_i$和$x_j$的特征组合在数据集合中没有出现过,在上述SVM模型的特征组合下,是无法学到这个特征组合的权重的。但是FM模型是学习单个特征的embedding,不依赖某个特定的特征组合是否存在,只要该特征在特征组合中出现过,就可以学习他对应的特征组合的embedding向量,于是,尽管$x_i, x_j$这个特征组合没有看到过,但是在预测的时候,如果看到这个新的特征组合,因为$x_i$和$x_j$都能学会自己对应的embedding,所以可以通过内积算出这个新特征组合的权重。故而FM泛化能力更强。
- 协同过滤
协同过滤(Collaborative Filtering,CF)是推荐算法的鼻祖,至今各个互联网公司中,CF都扮演着不可或缺的角色。协同过滤是根据大家的反馈、评论和意见一起对海量的信息进行过滤,从中筛选出目标用户可能感兴趣的信息的推荐过程。大致过程是,将用户与商品放入一个共现矩阵中,矩阵中的值为某用户对某件商品的点击、评价或者购买行为的度量。我们可以将用户感兴趣的所有商品向量化,记为代表该用户的向量,进而可以计算用户间的相似度。于是,可以将与某待推荐用户相似的用户所感兴趣的商品推荐给该用户。类似的,可以将对商品感兴趣的所有用户向量化,记为代表该商品的向量,进而计算物品之间的相似度。在实际的计算过程中,还应该对爆品、高销品与其他商品的相似度进行一定程度上的衰减。相似度的计算也应该进行归一化,排除数量级的影响。
协同过滤的优点是没有显式的学习过程、可解释性强、简单、速度快。其缺点也很明显:协同过滤只考虑了用户和物品的id信息,而无法将用户的属性、物品的属性、上下文考虑在内,无法挖掘用户和物品之间的隐含关系。对于没有购买或者消费的新用户,协同过滤不知如何推荐,泛化性能差,推荐头部效应比较明显。针对这些问题,MF(Matrix Factorization,矩阵分解)模型被提出来。它的核心思想是通过两个低维小矩阵(一个代表用户embedding矩阵,一个代表物品embedding矩阵)的乘积计算,来模拟真实用户点击或评分产生的大的协同信息稀疏矩阵,本质上是编码了用户和物品协同信息的降维模型。当训练完成,每个用户和物品得到对应的低维embedding表达后,如果要预测某个 $User_i$ 对 $Item_j$的评分的时候,只要它们做个内积计算$<User_i, Item_j>$,这个得分就是预测得分。
本质上,MF模型是FM模型的特例,MF可以被认为是只有User ID 和Item ID这两个特征Fields的FM模型,MF将这两类特征通过矩阵分解,来达到将这两类特征embedding化表达的目的。而FM则可以看作是MF模型的进一步拓展,除了User ID和Item ID这两类特征外,很多其它类型的特征,都可以进一步融入FM模型里,它将所有这些特征转化为embedding低维向量表达,并计算任意两个特征embedding的内积,就是特征组合的权重,如果FM只使用User ID 和Item ID,你套到FM公式里,看看它的预测过程和MF的预测过程一样吗?
在具体的实践过程中,FM模型和MF模型相比,前者继承了后者特征embedding化的特点,同时引入了更多的Side information作为特征,将更多的特征及Side information embedding化融入FM模型中。所以表现的也更加的灵活,能够适应更多的场景。在推荐排序阶段,绝大多数只使用ID信息的模型是不实用的,没有引入Side Information(也就是除了User ID/Item ID外的很多其它可用特征的模型)是不具备实战价值的。原因很简单,大多数真实应用场景中,User/Item有很多信息可用,而协同数据只是其中的一种,引入更多特征明显对于更精准地进行个性化推荐是非常有帮助的。而如果模型不支持更多特征的便捷引入,明显受限严重,很难真正实用,这也是为何矩阵分解类的方法很少看到在排序阶段使用,通常是作为一路召回形式存在的原因。
3. FM原理
FM模型的关键是:特征两两相关。具体的方程式如下:
$ y=w_0 + \sum_{i+n}^n{w_ix_i}+\sum_{i=1}^n\sum_{j=i+1}^n<v_i,v_j>x_ix_j $
其中,$v_i$是第i维特征的隐向量,<-,->代表向量点积,具体表达关系式:
$$ <v_i,v_j>=\sum_{f=1}^k{v_{i,f}v_{j,f}}=\underbrace{\begin{matrix} 1 & 2 & 3 \end{matrix}}_{v_i}{\quad}\left. \begin{matrix} 1 \ 2 \ 3 \end{matrix}\right}{v_i}$$
其中隐向量的长度为k(k<<n), 包含k个描述特征的因子。上述fm公式时间复杂度是$O(k*n^2)$ 实际使用还是比较耗时,这里需要对原始公式做一个化简。针对FM模型二次项的等价化简过程如图4所示。
第一行到第二行的公式理解可以借助图5所示的直观推理,所要计算的部分就是矩阵的上半角。
至于第二行到第三行提取公共部分理解相对较难,可以借助下图展开公式加以理解,先把k维特征内容抽取到最外层,第一项就剩下$\sum_{i=1}^j{\sum_{j=1}^nv_{i,f}{v_{j,f}x_ix_j}}$ ,然后再按照图6逐层展开合并,可以得到最终结果。
最终的计算等价转化为:
$$y=w_0 + \sum_{i+n}^n{w_ix_i}+ \frac{1}{2}\sum_{f=1}^k[(\sum_{i=1}^n{v_{i,f}x_i})^2-\sum_{i=1}^n{v_{i,f}^2x_i^2}]$$
将时间复杂度降低为$o(kn)$,即降到线性复杂度,提高了模型的实用性
4. 召回的应用
在网上介绍最多的就是如果利用fm模型的交叉特征的特性提升网络的性能,更好的做分类或者回归任务。对于推荐系统的召回部分,如何通过fm模型计算user和item的相似度,在线上快速获取topK的item?基于上面的基础,下面来探讨一下如何用FM模型在线上做召回。
构建一个线上的召回模块,主要包含四大部分,训练数据的筛选、特征的选择、模型训练,线上服务搭建。数据样本的确认因场景不同而有很大的差异,细节和注意点较多,这里不做讨论,线上服务也不是讨论重点,这个章节主要集中的特征和模型部分。针对一个线上召回系统,可以将特征简化抽样为user特征,item特征,以及context上下文特征(比如用户点外卖所处地址、时间点等)。
为了简化理解,我们可以先考虑只包含user特征和item特征。对于某个用户,我们可以把属于这个用户子集合的特征,查询离线训练好的FM模型对应的特征embedding向量,然后将n个用户子集合的特征embedding向量累加,形成用户兴趣向量U,这个向量维度和每个特征的维度是相同的。类似的,我们也可以把每个物品,其对应的物品子集合的特征,查询离线训练好的FM模型对应的特征embedding向量,然后将m个物品子集合的特征embedding向量累加,形成物品向量I,这个向量维度和每个特征的维度也是是相同的。对于极简版FM召回模型来说,用户兴趣向量U可以离线算好,,物品兴趣向量I可以类似离线计算或者近在线计算,问题都不大。
然后将上述计算得到的user embedding 存入线上redis中,线上通过id索引对应的embedding。离线计算的item embedding可以存入Faiss(Facebook开源的embedding高效匹配库)数据库中。通过用户的embedding和Faiss中存储的物料embedding做内积计算,按照得分由高到低返回得分Top K的物料作为召回结果。这样就完成了一个极简版本FM召回模型。但是这个版本的FM召回模型存在两个问题。
问题一:首先我们需要问自己,这种累加用户embedding特征向量以及累加物品embedding特征向量,之后做向量内积。这种算法符合FM模型的原则吗?和常规的FM模型是否等价?
我们来分析一下。这种做法其实是在做用户特征集合U和物品特征集合I之间两两特征组合,是符合FM的特征组合原则的,考虑下列公式是否等价就可以明白了:
$<\sum_i{U_i},\sum_j{I_j}>$ 公式(1)
$ \sum_i{\sum_j}{<U_i,I_j>} $ 公式(2)
其实两者是等价的,具体推导过程和上节中第三步的推导类似,但是和完全版本的FM比,我们没有考虑U和I特征集合内部任意两个特征的组合。也可以这么思考问题:在上文我们说过,FM为了提升计算效率,对公式进行了改写,改写后的高效计算公式的第一个平方项其实等价于:把所有特征embedding向量逐位累加成一个求和向量V,然后自己和自己做个内积操作<V,V>。这样等价于根据FM的原则计算了任意两个特征的二阶特征组合了。而上面描述的方法,和标准的FM的做法其实是一样的,区别无非是将特征集合划分为两个子集合U和I,分别代表用户相关特征及物品相关特征。而上述做法其实等价于在用户特征和物品特征之间做两两特征组合,只是少了U内部之间特征,及I内部特征之间的特征组合而已。一般而言,其实我们不需要做U内部特征之间以及I内部特征之间的特征组合,对最终效果影响很小。于是,沿着这个思考路径,我们也可以推导出上述做法基本和FM标准计算过程是等价的。
第二个问题是:这个版本FM是个简化版本模型,因为它没考虑场景上下文特征,那么如果再将上下文特征引入,此时应该怎么做呢?
上下文特征也是很重要的一个特征,它是用户发生行为的场景特征(比如什么时间在什么地方用的什么设备在刷新),这类特征几乎是实时变化的,比如用户上一时刻看了什么电影,下一刻会有历史有很大的相关性,这些动态的特征不太可能离线算好缓存起来。考虑进来上下文特征,如果我们希望构造和标准的FM等价的召回模型,就需要多考虑两个问题:既然部分上下文特征可能是实时变化的,无法离线算好,那么怎么融入上文所述的召回计算框架里?我们需要考虑上下文特征C和用户特征U之间的特征组合,也需要考虑C和物品特征I之间的特征组合。上下文特征有时是非常强的特征。那么,如何做能够将这两对特征组合考虑进来呢?
首先由于上下文特征的动态性,所以给定用户uid后,可以在线查询或者计算某个上下文特征对应的embedding向量,然后所有上下文向量求和得到综合的上下文向量C。这个过程其实和U及I的累加过程是一样的,区别无非是上下文特征需要在线实时计算。而一般而言,场景上下文特征数都不多,所以在线计算,速度方面应可接受。然后,将U和C向量累加求和,利用(U+C)去Faiss通过内积方式取出Top K物品,这个过程和极简版是一样的,无非查询向量由U换成了(U+C)。通过这种方式取出的物品同时考虑到了用户和物品的特征组合<U,I>,以及上下文和物品的特征组合<C,I>。道理和之前讲的内容是类似的。
5. 代码实现
- 使用python做二分类任务。数据和代码下载在AI成长社 中回复FM即可
import numpy as np import random import pandas as pd from numpy import * from random import normalvariate # 正态分布 from datetime import datetime from sklearn.preprocessing import LabelEncoder from sklearn.preprocessing import OneHotEncoder def loadData(base_dir): ''' load ori_data Returns: csv_data ''' movie_columns = ['movie_id', 'title', 'genres'] movies = pd.read_csv(base_dir + "movies.dat", sep='::', header=None, names=movie_columns, engine='python') rating_columns = ['user_id','movie_id','rating','timestamp'] ratings = pd.read_csv(base_dir + "ratings.dat", sep='::', header=None, names=rating_columns, engine='python') user_columns = ['user_id','gender','age','occupation','zip'] users = pd.read_csv(base_dir + "users.dat", sep='::', header=None, names=user_columns, engine='python') data = pd.merge(ratings, movies) data = pd.merge(data, users) return data # 处理数据 def preprocessData(data, ratio): label = data['rating'].map(lambda x: 1 if x > 3 else -1) features = ['genres', 'gender', 'age'] data = data[features] # onehot data = pd.get_dummies(data) num = int(data.shape[0] * ratio) train = data[:num] train_label = label[:num] test = data[num:] test_label = label[num:] return train, train_label, test, test_label def sigmoid(inx): return 1.0 / (1 + np.exp(-inx)) # 训练FM模型 def FM(dataMatrix, classLabels, k, iter, alpha): ''' :param dataMatrix: 特征矩阵 :param classLabels: 标签矩阵 :param k: v的维数 :param iter: 迭代次数 :return: 常数项w_0, 一阶特征系数w, 二阶交叉特征系数v ''' # dataMatrix用的是matrix, classLabels是列表 m, n = shape(dataMatrix) # 矩阵的行列数,即样本数m和特征数n # 初始化参数 w = zeros((n, 1)) # 一阶特征的系数 w_0 = 0 # 常数项 v = normalvariate(0, 0.2) * ones((n, k)) # 即生成辅助向量(n*k),用来训练二阶交叉特征的系数 for it in range(iter): for x in range(m): # 随机优化,每次只使用一个样本 # 二阶项的计算 inter_1 = dataMatrix[x] * v # 每个样本(1*n)x(n*k),得到k维向量(FM化简公式大括号内的第一项) inter_2 = multiply(dataMatrix[x], dataMatrix[x]) * multiply(v, v) # 二阶交叉项计算,得到k维向量(FM化简公式大括号内的第二项) interaction = sum(multiply(inter_1, inter_1) - inter_2) / 2. # 二阶交叉项计算完成(FM化简公式的大括号外累加) p = w_0 + dataMatrix[x] * w + interaction # 计算预测的输出,即FM的全部项之和 tmp = 1 - sigmoid(classLabels[x] * p[0, 0]) # tmp迭代公式的中间变量,便于计算 w_0 = w_0 + alpha * tmp * classLabels[x] for i in range(n): if dataMatrix[x, i] != 0: w[i, 0] = w[i, 0] + alpha * tmp * classLabels[x] * dataMatrix[x, i] for j in range(k): v[i, j] = v[i, j] + alpha * tmp * classLabels[x] * ( dataMatrix[x, i] * inter_1[0, j] - v[i, j] * dataMatrix[x, i] * dataMatrix[x, i]) # 计算损失函数的值 if it % 10 == 0: loss = getLoss(getPrediction(mat(dataMatrix), w_0, w, v), classLabels) print("第{}次迭代后的损失为{}".format(it, loss)) return w_0, w, v # 损失函数 def getLoss(predict, classLabels): m = len(predict) loss = 0.0 for i in range(m): loss -= log(sigmoid(predict[i] * classLabels[i])) return loss # 预测 def getPrediction(dataMatrix, w_0, w, v): m = np.shape(dataMatrix)[0] result = [] for x in range(m): inter_1 = dataMatrix[x] * v inter_2 = multiply(dataMatrix[x], dataMatrix[x]) * multiply(v, v) # multiply对应元素相乘 # 完成交叉项 interaction = np.sum(multiply(inter_1, inter_1) - inter_2) / 2. p = w_0 + dataMatrix[x] * w + interaction # 计算预测的输出 pre = sigmoid(p[0, 0]) result.append(pre) return result # 评估预测的准确性 def getAccuracy(predict, classLabels): m = len(predict) allItem = 0 error = 0 for i in range(m): # 计算每一个样本的误差 allItem += 1 if float(predict[i]) < 0.5 and classLabels[i] == 1.0: error += 1 elif float(predict[i]) >= 0.5 and classLabels[i] == -1.0: error += 1 else: continue return float(error) / allItem if __name__ == '__main__': data_file = "../data/ml-1m/" Data = loadData(data_file) dataTrain, labelTrain, dataTest, labelTest = preprocessData(Data, 0.8) date_startTrain = datetime.now() print("开始训练") w_0, w, v = FM(mat(dataTrain), labelTrain, 4, 100, 0.001) print("w_0:", w_0) print("w:", w) print("v:", v) predict_train_result = getPrediction(mat(dataTrain), w_0, w, v) # 得到训练的准确性 print("训练准确性为:%f" % (1 - getAccuracy(predict_train_result, labelTrain))) date_endTrain = datetime.now() print("训练用时为:%s" % (date_endTrain - date_startTrain)) print("开始测试") predict_test_result = getPrediction(mat(dataTest), w_0, w, v) # 得到训练的准确性 print("测试准确性为:%f" % (1 - getAccuracy(predict_test_result, labelTest)))
最终的训练结果如下图
-
使用tensorflow做召回的代码:链接
6. 参考
2. Factorization Machines 学习笔记
- 我的微信小程序
- 这是我的微信小程序扫一扫
-
- 我的微信公众号
- 我的微信公众号扫一扫
-
评论