CTR预估

点击率(Click through rate) = 点击次数 / 展示次数

推荐系统中，是否进行推荐，需要根据预估的 CTR 来进行。在 CTR 预估中，常用的算法有 FM、FFM 和 DeepFM。

FM模型

FM(Factorization Machine)主要是为了解决数据稀疏的情况下，特征怎样组合的问题。已一个广告分类的问题为例，根据用户与广告位的一些特征，来预测用户是否会点击广告。数据如下：

image

clicked是分类值，表明用户有没有点击该广告。1表示点击，0表示未点击。而country,day,ad_type则是对应的特征。对于这种categorical特征，一般都是进行one-hot编码处理。将上面的数据进行one-hot编码以后，就变成了下面这样 :

image

one-hot之后，数据会变得非常稀疏，特征空间会变得很大（产生百万千万维的特征）。比如对item进行one-hot，如果有100w个item，就会产生100w个维度，而每个item只在其中一维的值为1。

此外，普通的线性模型各个特征是单独的：

image

但实际中很多特征之间有关联，比如电商广告中，男性用户更喜欢球类，女性用户更喜欢化妆品类等。需要发掘这些有关联的特征。

在FM模型中，考虑了特征之间的关联，所以相比线性模型，多了后面特征组合的部分：

image

由上面式子可以看出，一共有 n(n-1)/2 个组合特征，对应有这么多个权重wij。但在数据非常稀疏的情况下，满足xi,xj都不为0的情况很少，这就很难训练得到wij。

所以引入辅助向量V，通过V来计算得到权重w。

image

这就相当于将W矩阵分解为V和VT。而对k值的限定，则反映了FM模型的表达能力。

通过辅助的V，将关联特征原本需要训练的特征权重参数，减少到了 nk 个。

直观上看，FM的复杂度是O(k * n^2)，但是，在实际计算后面的组合特征时，可有如下推导：

image

其中，第一步的变换，可以用下面的示意图来说明：（注意仔细看下标的范围，就能理解第一步是怎么推的了）。基本思路就相当于 2ab = (a+b)^2 - (a^2+b2)。

image

使用SGD来更新参数：

image

变换之后的复杂度为O(k * n)，所以FM可在线性时间内做出预测，效率高。

使用tensorflow来做一个FM模型的小实践，代码及详细说明，请参见 https://github.com/dox1994/recommend_system/blob/master/FM/fm.ipynb