FM

参考链接：

点击率预估算法：FM与FFM

读论文:FFM

FM–2010–论文

FFM–2014–论文

FM在特征组合中的应用

FFM原理及公式推导

是2010年Stedden Rendle提出的，目的是解决稀疏数据的特征组合问题。

逻辑回归

公式1
y = w 0 + ∑ i = 1 n w i x i y=w_{0}+\sum_{i=1}^{n} w_{i} x_{i} y=w0​+i=1∑n​wi​xi​
w 0 , w i w_{0},w_{i} w0​,wi​ 是参数，$n$表示数据总量， x i x_{i} xi​表示某条数据。

二阶多项式模型（Poly2模型）

公式2
y ^ ( x ) = w 0 + ∑ i = 1 n w i x i + ∑ i = 1 n ∑ j = i + 1 n w i j x i x j \hat{y}(\mathbf{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} y^​(x)=w0​+i=1∑n​wi​xi​+i=1∑n​j=i+1∑n​wij​xi​xj​
一次项有$n+1$个，二次项（即组合特征的参数）共有
d ( d − 1 ) 2 \frac{d(d-1)}{2} 2d(d−1)​，而参数与参数之间彼此独立，在稀疏场景下，二次项的训练是很困难的。因为要训练 w i j w_{ij} wij​,需要大量的 x i x_{i} xi​ 和 x j x_{j} xj​都非0的样本（只有非0组合才有意义）。而样本本身是稀疏的，满 x i x j ≠ 0 x_{i} x_{j} \neq 0 xi​xj​̸​=0的样本会非常少，那么样本少就难以估计参数 w i j w_{ij} wij​，训练出来的模型容易过拟合。

为了缓解上述问题，Rendle在2010提出了FM模型，它可以缓解公式2，特定如下：

• FM模型可以在非常稀疏的情况下进行参数估计
• FM模型是线性时间复杂度的，可以直接使用原问题进行求解，而且不用像SVM一样依赖支持向量。
• FM模型是一个通用的模型，其训练数据的特征取值可以是任意实数。
  ###对参数 W i j W_{ij} Wij​进行分解

公式3
y ^ ( x ) = w 0 + ∑ i = 1 d w i x i + ∑ i = 1 d ∑ j = i + 1 d ( v i ⋅ v j ) x i x j \hat{y}(\mathbf{x})=w_{0}+\sum_{i=1}^{d} w_{i} x_{i}+\sum_{i=1}^{d} \sum_{j=i+1}^{d}\left(\mathbf{v}_{i} \cdot \mathbf{v}_{j}\right) x_{i} x_{j} y^​(x)=w0​+i=1∑d​wi​xi​+i=1∑d​j=i+1∑d​(vi​⋅vj​)xi​xj​
其中 v i v_{i} vi​是第$i$维特征的隐向量,其长度为$k(k<<n)$ , ( v i ⋅ v j ) \left(\mathbf{v}_{i} \cdot \mathbf{v}_{j}\right) (vi​⋅vj​) 为内积，其乘积为原来 w i j w_{ij} wij​, 也就是
w ^ i j = ( v i ⋅ v j ) = ∑ f = 1 k v i , f ⋅ v j , f \hat{w}_{i j}=\left(\mathbf{v}_{i} \cdot\mathbf{v}_{j}\right)=\sum_{f=1}^{k} v_{i, f} \cdot v_{j, f} w^ij​=(vi​⋅vj​)=∑f=1k​vi,f​⋅vj,f​。

将 w i j w_{ij} wij​进行分解，使得不同的特征对不再是完全独立的，而它们的关联性可以用隐式因子表示，这将使得有更多的数据可以用于模型参数的学习。比如 x i x_i xi​, x j x_j xj​与 x i x_i xi​, x k x_k xk​ 的参数分别为： ⟨ v i , v j ⟩ ⟨v_i,v_j⟩ ⟨vi​,vj​⟩和 ⟨ v i , v k ⟩ ⟨v_i,v_k⟩ ⟨vi​,vk​⟩，它们都可以用来学习 v i v_i vi​，更一般的，包含 x i x j ≠ 0 & i ≠ j x_{i} x_{j} \neq 0 \& i \neq j xi​xj​̸​=0&i̸​=j的所有样本都能用来学习 v i v_i vi​，很大程度上避免了数据稀疏性的影响。

时间复杂度O( k d 2 kd^2 kd2)—>O($kd$)

A = 1 2 ( 2 A + B ) − 1 2 B . A = ∑ i = 1 n ∑ j = i + 1 n ⟨ v i , v j ⟩ x i x j ; B = 1 2 ∑ i = 1 n ⟨ v i , v i ⟩ x i x i A=\frac{1}{2}(2 A+B)-\frac{1}{2} B . \quad A=\sum_{i=1}^{n} \sum_{j=i+1}^{n}\left\langle\mathbf{v}_{i}, \mathbf{v}_{j}\right\rangle x_{i} x_{j} ; \quad B=\frac{1}{2} \sum_{i=1}^{n}\left\langle\mathbf{v}_{i}, \mathbf{v}_{i}\right\rangle x_{i} x_{i} A=21​(2A+B)−21​B.A=∑i=1n​∑j=i+1n​⟨vi​,vj​⟩xi​xj​;B=21​∑i=1n​⟨vi​,vi​⟩xi​xi​

∑ i = 1 n ∑ j = i + 1 n < v i , v j > x i x j = 1 2 ∑ i = 1 n ∑ j = 1 n < v i , v j > x i x j − 1 2 ∑ i = 1 n < v i , v i > x i x i = 1 2 ( ∑ i = 1 n ∑ j = 1 n ∑ f = 1 k v i f v j f x i x j − ∑ i = 1 n ∑ f = 1 k v i f v i f x i x i ) = 1 2 ( ∑ f = 1 k ∑ i = 1 n v i f x i ∑ j = 1 n v j f x j − ∑ i = 1 n ∑ f = 1 k v i f v i f x i x i ) \begin{aligned} & \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}\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) \\=& \frac{1}{2}\left(\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} \sum_{f=1}^{k} v_{i f} v_{i f} x_{i} x_{i}\right) \end{aligned} ===​i=1∑n​j=i+1∑n​<vi​,vj​>xi​xj​21​i=1∑n​j=1∑n​<vi​,vj​>xi​xj​−21​i=1∑n​<vi​,vi​>xi​xi​21​⎝⎛​i=1∑n​j=1∑n​f=1∑k​vif​vjf​xi​xj​−i=1∑n​f=1∑k​vif​vif​xi​xi​⎠⎞​21​⎝⎛​f=1∑k​i=1∑n​vif​xi​j=1∑n​vjf​xj​−i=1∑n​f=1∑k​vif​vif​xi​xi​⎠⎞​​

因为 ∑ i = 1 n v i f x i \sum_{i=1}^{n} v_{i f} x_{i} ∑i=1n​vif​xi​ 跟 $j$ 没有关系， ∑ j = 1 n v j f x j \sum_{j=1}^{n} v_{j f} x_{j} ∑j=1n​vjf​xj​ 跟 $i$ 没有关系，所以：
∑ i = 1 n v i f x i ∑ j = 1 n v j f x j = ( ∑ i = 1 n v i f x i ) ( ∑ j = 1 n v j f x j ) \sum_{i=1}^{n} v_{i f} x_{i} \sum_{j=1}^{n} v_{j f} x_{j}=\left(\sum_{i=1}^{n} v_{i f} x_{i}\right)\left(\sum_{j=1}^{n} v_{j f} x_{j}\right) ∑i=1n​vif​xi​∑j=1n​vjf​xj​=(∑i=1n​vif​xi​)(∑j=1n​vjf​xj​)

公式4
∑ i = 1 n ∑ j = i + 1 n < v i , v j > x i x j = 1 2 ∑ i = 1 n ∑ j = 1 n < v i , v j > x i x j − 1 2 ∑ i = 1 n < v i , v i > x i x i ) = 1 2 ( ∑ i = 1 k ∑ j = 1 n v i f x i ∑ j = 1 n v j f x j − ∑ i = 1 n ∑ f = 1 k v i f v i f x i x i ) = 1 2 ( ∑ f = 1 k ∑ i = 1 n v i f x i ∑ j = 1 n v j f x j − ∑ i = 1 n ∑ f = 1 k v i f v i f x i x i ) \begin{aligned} & \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}\left(\sum_{i=1}^{k} \sum_{j=1}^{n} v_{i f} x_{i} \sum_{j=1}^{n} v_{j f} x_{j}-\sum_{i=1}^{n} \sum_{f=1}^{k} v_{i f} v_{i f} x_{i} x_{i}\right) \\=& \frac{1}{2}\left(\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} \sum_{f=1}^{k} v_{i f} v_{i f} x_{i} x_{i}\right) \end{aligned} ===​i=1∑n​j=i+1∑n​<vi​,vj​>xi​xj​21​i=1∑n​j=1∑n​<vi​,vj​>xi​xj​−21​i=1∑n​<vi​,vi​>xi​xi​)21​⎝⎛​i=1∑k​j=1∑n​vif​xi​j=1∑n​vjf​xj​−i=1∑n​f=1∑k​vif​vif​xi​xi​⎠⎞​21​⎝⎛​f=1∑k​i=1∑n​vif​xi​j=1∑n​vjf​xj​−i=1∑n​f=1∑k​vif​vif​xi​xi​⎠⎞​​

如此一来根据 $x$ 求 y ^ \hat{y} y^​ 的时间复杂度就降为 $O(kn)$ 可以看出，FM模型可以在线性的时间做出预测。

FM模型学习

公式5
y ^ ( x ) = w 0 + ∑ i = 1 n w i x i + 1 2 ∑ f = 1 k ( ( ∑ i = 1 n v i , f x i ) 2 − ∑ i = 1 n v i , f 2 x i 2 ) \hat{y}(\mathbf{x})=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\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) y^​(x)=w0​+i=1∑n​wi​xi​+21​f=1∑k​⎝⎛​(i=1∑n​vi,f​xi​)2−i=1∑n​vi,f2​xi2​⎠⎞​
FM模型可以使用梯度下降法进行学习，模型的梯度为：
公式6
∂ ∂ θ y ( x ) = { 1 , if  θ is  w 0 x i , if  θ is  w i x i ∑ j = 1 d v j , f x j − v i , f x i 2 , if  θ is  v i , f \frac{\partial}{\partial \theta} y(\mathbf{x})=\left\{\begin{array}{ll}{1,} & {\text { if } \theta \text { is } w_{0}} \\ {x_{i},} & {\text { if } \theta \text { is } w_{i}} \\ {x_{i} \sum_{j=1}^{d} v_{j, f} x_{j}-v_{i, f} x_{i}^{2},} & {\text { if } \theta \text { is } v_{i, f}}\end{array}\right. ∂θ∂​y(x)=⎩⎨⎧​1,xi​,xi​∑j=1d​vj,f​xj​−vi,f​xi2​,​ if θ is w0​ if θ is wi​ if θ is vi,f​​
∑ j = 1 d v j , f x j \sum_{j=1}^{d} v_{j, f} x_{j} ∑j=1d​vj,f​xj​ 只与 $f$ 有关而与 $i$ 无关，在每次迭代过程中，可以预先对所有 $f$ 的 ∑ j = 1 d v j , f x j \sum_{j=1}^{d} v_{j, f} x_{j} ∑j=1d​vj,f​xj​ 进行计算，复杂度 $O(kd)$,就能在常数时间 $O(1)$内得到 v i , f v_{i, f} vi,f​ 的梯度。而对于其它参数 w 0 w_{0} w0​ 和 w i w_{i} wi​，显然也是在常数时间内计算梯度。此外，更新参数只需要 $O(1)$ ，一共有 $1+d+kd$ 个参数，因此FM参数训练的复杂度也是 $O(kd)$.

所以说，FM模型是一种高效的模型，是线性时间复杂度的，可以在线性的时间做出训练和预测。

##具体例子

特征组合

如上例特征 $x$ 有6个维度，年龄是连续值，城市和性别用one-hot表示，假设我们用最简单的线性拟合来预测y值。
y ^ = w 0 + ∑ i = 1 n w i x i \hat{y}=w_{0}+\sum_{i=1}^{n} w_{i} x_{i} y^​=w0​+∑i=1n​wi​xi​
实际中“北京的男性用户”，“上海的女性用户”这种组合特征可能是有用的，即 x i x_i xi​ , x j x_j xj​（ x i x_i xi​ , x j x_j xj​ 都是one-hot特征）同时为1时可能是一个很有用的特征，这种组合特征是 x i x_i xi​ 和 x j x_j xj​ 的线性组合所无法表示的。这样一来乘积 x i x j x_ix_j xi​xj​ 就成一个新的特征。

y ^ = w 0 + ∑ i = 1 n w i x i + ∑ i = 1 n ∑ j = i + 1 n v i ⋅ v j x i x j \hat{y}=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n} \sum_{j=i+1}^{n} v_{i} \cdot v_{j} x_{i} x_{j} y^​=w0​+∑i=1n​wi​xi​+∑i=1n​∑j=i+1n​vi​⋅vj​xi​xj​

$.$ 表示向量的内积。样本 $x$ 是 $n$ 维向量， x i x_i xi​ 是第 $i$ 个维度上的值。 v i v_i vi​是 x i x_i xi​ 对应的长度为 $K$的隐向量， $V$ 是模型参数，所以所有样本都使用同一个 $V$ ，即 x 1 , 1 x_{1,1} x1,1​ 与 x 2 , 1 x_{2,1} x2,1​ 都使用 v 1 v_1 v1​。

由于二次项系数 w i j w_{ij} wij​ ，我们额外引入 n 2 2 \frac{n^{2}}{2} 2n2​ 个参数需要训练。有没有什么办法可以减少参数？再来观察二次项系数矩阵 W n × n W_{n×n} Wn×n​，它是对称的方阵 w i j = w j i w_{ij}=w_{ji} wij​=wji​ ，同时它是稀疏的，因为绝大部分的组合特征都是无用的，所以其系数应该为0。可以对 W n × n W_{n×n} Wn×n​ 进行矩阵分解 W n × n = V n × k V n × k T W_{n×n}=V_{n×k}V_{n×k}^{T} Wn×n​=Vn×k​Vn×kT​，即 w i , j = < v i , v j > w_{i,j}=<v_i,v_j> wi,j​=<vi​,vj​>。其中 $k\ll n$，本来需要训练的 $n\times n$ 个参数，现在只需要训练 $n\times k$ 个。

∑ i = 1 n ∑ j = 1 n < v i , v j > x i x j \sum_{i=1}^{n} \sum_{j=1}^{n}<v_{i}, v_{j}>x_{i} x_{j} ∑i=1n​∑j=1n​<vi​,vj​>xi​xj​ 构成一个完整的对称矩阵， ∑ i = 1 n ∑ j − i + 1 n < v i , v j > x i x j \sum_{i=1}^{n} \sum_{j-i+1}^{n}<v_{i}, v_{j}>x_{i} x_{j} ∑i=1n​∑j−i+1n​<vi​,vj​>xi​xj​ 是这个对称矩阵的上三角部分（不包含对角线）,所以 ∑ i = 1 n ∑ j = i + 1 n < v i , v j > x i x j \sum_{i=1}^{n} \sum_{j=i+1}^{n}<v_{i}, v_{j}>x_{i} x_{j} ∑i=1n​∑j=i+1n​<vi​,vj​>xi​xj​ 等于 ∑ i = 1 n ∑ j = 1 n < v i , v j > x i x j \sum_{i=1}^{n} \sum_{j=1}^{n}<v_{i}, v_{j}>x_{i} x_{j} ∑i=1n​∑j=1n​<vi​,vj​>xi​xj​ 减去对角线再除以2。即公式4

FFM(Field-aware Factorization Machine)

最初的概念来自Yu-Chin Juan （阮毓钦，毕业于中国台湾大学，现在美国Criteo工作）与其比赛队员，提出FM的升级版模型。通过引入field的概念，FFM把相同的性质的特征归于同一个field。

在FM模型中，每一个特征会对应一个隐变量，但在FFM模型中，认为应该将特征分为多个field，每个特征对应每个field分别有一个隐变量。field和feature是一对多的关系。

例子
举个例子，我们的样本有3种类型的字段：publisher, advertiser, gender，分别可以代表媒体，广告主或者是具体的商品，性别。其中publisher有5种数据，advertiser有10种数据，gender有男女2种，经过one-hot编码以后，每个样本有17个特征，其中只有3个特征非空。

• 如果使用FM模型，则17个特征，每个特征对应一个隐变量。
• 如果使用FFM模型，则17个特征，每个特征对应3个隐变量，即每个类型对应一个隐变量，具体而言，就是对应publisher, advertiser, gender三个field各有一个隐变量。

（巨人的肩膀）体会：在FM模型中，每一个特征会对应一个隐变量，但在FFM模型中，认为应该将特征分为多个field，每个特征对应每个field分别有一个隐变量。举个例子，我们的样本有3种类型的字段：publisher, advertiser, gender，分别可以代表媒体，广告主或者是具体的商品，性别。其中publisher有5种数据，advertiser有10种数据，gender有男女2种，经过one-hot编码以后，每个样本有17个特征，其中只有3个特征非空。如果使用FM模型，则17个特征，每个特征对应一个隐变量。如果使用FFM模型，则17个特征，每个特征对应3个隐变量，即每个类型对应一个隐变量，具体而言，就是对应publisher, advertiser, gender三个field各有一个隐变量。

在FFM的训练过程中，有许多细节要注意。

• 第一，样本归一化。FFM默认是进行样本数据的归一化，否则很容易造成数据inf溢出，进而引起梯度计算的nan错误。因此，样本层面的数据是推荐进行归一化的。
• 特征归一化。CTR/CVR模型采用了多种类型的源特征，包括数值型和categorical类型等。但是，categorical类编码后的特征取值只有0或1，较大的数值型特征会造成样本归一化后categorical类生成特征的值非常小，没有区分性。例如，一条用户-商品记录，用户为“男”性，商品的销量是5000个（假设其它特征的值为零），那么归一化后特征“sex=male”（性别为男）的值略小于0.0002，而“volume”（销量）的值近似为1。特征“sex=male”在这个样本中的作用几乎可以忽略不计，这是相当不合理的。因此，将源数值型特征的值归一化到 $[0,1][0,1]$是非常必要的。
• 省略零值特征。从FFM模型的表达式可以看出，零值特征对模型完全没有贡献。包含零值特征的一次项和组合项均为零，对于训练模型参数或者目标值预估是没有作用的。因此，可以省去零值特征，提高FFM模型训练和预测的速度，这也是稀疏样本采用FFM的显著优势。

在FFM（Field-aware Factorization Machines ）中每一维特征（feature）都归属于一个特定的field，field和feature是一对多的关系。

1. 对于连续特征，一个特征就对应一个Field。或者对连续特征离散化，一个分箱成为一个特征。
2. 对于离散特征，采用one-hot编码，同一种属性的归到一个Field。

不论是连续特征还是离散特征，它们都有一个共同点：同一个field下只有一个feature的值不是0，其他feature的值都是0。

FFM模型认为 v i v_i vi​ 不仅跟 x i x_i xi​ 有关系，还跟与 x i x_i xi​ 相乘的 x j x_j xj​ 所属的Field有关系，即 v i v_i vi​ 成了一个二维向量 v F × K v_{F×K} vF×K​，F是Field的总个数。FFM只保留了二次项(特征组合).

公式6
y ^ = ∑ i = 1 n ∑ j = i + 1 n v i , f j ⋅ v j , f i x i x j \hat{y}=\sum_{i=1}^{n} \sum_{j=i+1}^{n} v_{i, f j} \cdot v_{j, f i} x_{i} x_{j} y^​=i=1∑n​j=i+1∑n​vi,fj​⋅vj,fi​xi​xj​

总的体会：FFM相比于FM，多了一个filed的概念，相当于进一步细化了数据。体现在公式上，相当于由一个特征对应一个隐向量---->一个t特征对应K个隐向量，K表示K个域。也就是说，FFM认为隐向量不仅与特征有关还与filed有关。

具体的例子解释：在FFM（Field-aware Factorization Machines ）中每一维特征（feature）都归属于一个特定的field，field和feature是一对多的关系。比如下图：

每个field有且只有一个值为1，其他均为0。 其实field的概念类似于一个集合。

结束：

• 这只是从数学公式上大致了解什么是FM以及FFM。FM的参数量已经是可控范围内了（$O(kn)$）,FFM的参数量是 O ( n k 2 ) O(nk^2) O(nk2),这是很大的参数量了。
• 其实在这里，我一开始并不理解FM到底是怎样得到embedding，那么下一节将记录到底怎么得到的embedding。

​

​

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！