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∑nwixi
w 0 , w i w_{0},w_{i} w0,wi 是参数， n n 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∑nwixi+i=1∑nj=i+1∑nwijxixj
一次项有 n + 1 n+1 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 xixj̸=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∑dwixi+i=1∑dj=i+1∑d(vi⋅vj)xixj
其中 v i v_{i} vi是第 i i i维特征的隐向量,其长度为 k ( k < < n ) k(k<<n) 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=1kvi,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 xixj̸=0&i̸=j的所有样本都能用来学习 v i v_i vi，很大程度上避免了数据稀疏性的影响。
时间复杂度O( k d 2 kd^2 kd2)—>O( k d kd 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)−21B.A=∑i=1n∑j=i+1n⟨vi,vj⟩xixj;B=21∑i=1n⟨vi,vi⟩xixi
∑ 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∑nj=i+1∑n<vi,vj>xixj21i=1∑nj=1∑n<vi,vj>xixj−21i=1∑n<vi,vi>xixi21⎝⎛i=1∑nj=1∑nf=1∑kvifvjfxixj−i=1∑nf=1∑kvifvifxixi⎠⎞21⎝⎛f=1∑ki=1∑nvifxij=1∑nvjfxj−i=1∑nf=1∑kvifvifxixi⎠⎞
因为 ∑ i = 1 n v i f x i \sum_{i=1}^{n} v_{i f} x_{i} ∑i=1nvifxi 跟 j j j 没有关系， ∑ j = 1 n v j f x j \sum_{j=1}^{n} v_{j f} x_{j} ∑j=1nvjfxj 跟 i i 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=1nvifxi∑j=1nvjfxj=(∑i=1nvifxi)(∑j=1nvjfxj)
公式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∑nj=i+1∑n<vi,vj>xixj21i=1∑nj=1∑n<vi,vj>xixj−21i=1∑n<vi,vi>xixi)21⎝⎛i=1∑kj=1∑nvifxij=1∑nvjfxj−i=1∑nf=1∑kvifvifxixi⎠⎞21⎝⎛f=1∑ki=1∑nvifxij=1∑nvjfxj−i=1∑nf=1∑kvifvifxixi⎠⎞
如此一来根据 x x x 求 y ^ \hat{y} y^ 的时间复杂度就降为 O ( k n ) O(k n) 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∑nwixi+21f=1∑k⎝⎛(i=1∑nvi,fxi)2−i=1∑nvi,f2xi2⎠⎞
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=1dvj,fxj−vi,fxi2, 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=1dvj,fxj 只与 f f f 有关而与 i i i 无关，在每次迭代过程中，可以预先对所有 f f f 的 ∑ j = 1 d v j , f x j \sum_{j=1}^{d} v_{j, f} x_{j} ∑j=1dvj,fxj 进行计算，复杂度 O ( k d ) O(k d) O(kd),就能在常数时间 O ( 1 ) O(1) O(1)内得到 v i , f v_{i, f} vi,f 的梯度。而对于其它参数 w 0 w_{0} w0 和 w i w_{i} wi，显然也是在常数时间内计算梯度。此外，更新参数只需要 O ( 1 ) O(1) O(1) ，一共有 1 + d + k d 1+d+k d 1+d+kd 个参数，因此FM参数训练的复杂度也是 O ( k d ) O(k d) O(kd).
所以说，FM模型是一种高效的模型，是线性时间复杂度的，可以在线性的时间做出训练和预测。
##具体例子
特征组合
| ---- | x1年龄 | x2北京 | x3上海 | x4s深圳 | x5男 | x6女 |
|---|---|---|---|---|---|---|
| 用户1 | 23 | 1 | 1 | |||
| 用户2 | 31 | 1 | 1 |
如上例特征 x x 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=1nwixi
实际中“北京的男性用户”，“上海的女性用户”这种组合特征可能是有用的，即 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 xixj 就成一个新的特征。
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=1nwixi+∑i=1n∑j=i+1nvi⋅vjxixj
. . . 表示向量的内积。样本 x x x 是 n n n 维向量， x i x_i xi 是第 i i i 个维度上的值。 v i v_i vi是 x i x_i xi 对应的长度为 K K K的隐向量， V V V 是模型参数，所以所有样本都使用同一个 V 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×kVn×kT，即 w i , j = < v i , v j > w_{i,j}=<v_i,v_j> wi,j=<vi,vj>。其中 k ≪ n k≪n k≪n，本来需要训练的 n × n n×n n×n 个参数，现在只需要训练 n × k n×k n×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>xixj 构成一个完整的对称矩阵， ∑ 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>xixj 是这个对称矩阵的上三角部分（不包含对角线）,所以 ∑ 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>xixj 等于 ∑ 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>xixj 减去对角线再除以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是一对多的关系。
- 对于连续特征，一个特征就对应一个Field。或者对连续特征离散化，一个分箱成为一个特征。
- 对于离散特征，采用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∑nj=i+1∑nvi,fj⋅vj,fixixj
总的体会：FFM相比于FM，多了一个filed的概念，相当于进一步细化了数据。体现在公式上，相当于由一个特征对应一个隐向量---->一个t特征对应K个隐向量，K表示K个域。也就是说，FFM认为隐向量不仅与特征有关还与filed有关。
具体的例子解释：在FFM（Field-aware Factorization Machines ）中每一维特征（feature）都归属于一个特定的field，field和feature是一对多的关系。比如下图：
| field | field1年龄 | field2城市 | field3性别 | |||
| feature | x1年龄 | x2北京 | x3上海 | x4深圳 | x5男 | x6女 |
| 用户1 | 23 | 1 | 1 | |||
| 用户2 | 31 | 1 | 1 |
每个field有且只有一个值为1，其他均为0。 其实field的概念类似于一个集合。
结束：
- 这只是从数学公式上大致了解什么是FM以及FFM。FM的参数量已经是可控范围内了（ O ( k n ) O(kn) O(kn)）,FFM的参数量是 O ( n k 2 ) O(nk^2) O(nk2),这是很大的参数量了。
- 其实在这里，我一开始并不理解FM到底是怎样得到embedding，那么下一节将记录到底怎么得到的embedding。
![《Microsoft Sql server 2008 Internals》读书笔记--第七章Special Storage(2)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)