为啥要聊FM呢，因为它设计很优雅～而且工程实现上有简化技巧，实现起来也很优雅，之后在FNN/DeepFM/xDeepFM都扮演者重要的角色。
Logistic Regression(LR)模型只能学习特征的线性表达，线性部分：
$$\hat{y} = w_0 + \sum_{i=1}^{n}w_i x_i$$
为了能让他具有非线性能力，工程师会根据自己对业务的理解手动进行特征组合，比如$x_{city} \cdot x_{age}$这样模型就能学习年龄和城市的组合情况，比如（城市=北京，年龄=12），在学习过程中就能学习“北京地区12岁的小孩”会怎么怎么着，这样手动的特征组合还是太消耗精力了，一个可以想到的思路是:
$$\sum_{i=1}^{n}\sum_{x=1+1}^{n}w_{ij}x_i x_j$$
不管3721就直接把每个维度的特征都给它组合起来，这样也不是不行，但是这样有一个致命的缺陷——稀疏，大概是制约模型的最大因素吧。我们有很多categorical feature，这些特征一般会经过onehot处理，比如城市有600多个，那么仅仅城市一个特征就要用600维的向量来表达，其中只有一个1，其他599个都是0，着599维根其他特征组合之后又是0，所以引入特征组合之后，使原本稀疏的特征更加稀疏～大概比30岁程序员的头发还稀疏～
FM(Factorization Machines)就是来解决这个问题的，FM不是用一个常数$w_{ij}$来表达$x_i$和$x_j$的权重，它用一群常数来表达～每一维的特征$x_i$都分配一个权重向量$\textbf{v}_i$，这样两维特征要组合的时候用他们各自的权重向量的内积作为他们俩的权重，所以$x_i$和$x_j$组合后是$\left \langle \textbf{v}_i, \textbf{v}_j \right \rangle x_i x_j$
尖括号是算内积
$$\left \langle \textbf{v}_i, \textbf{v}_j \right \rangle= \sum_{f=1}^{k}v_{i,f}v_{j,f}$$
有多少维特征就会有多少个向量$\textbf{v}$，我们把这些向量组成一个矩阵$V \in R^{n \times k}$，其中$n$就是特征向量，$k$表示一个向量有多少分量（维度），梯度下降求解向量$\textbf{v}_i$的过程中，会对向量中的每个分量$\textbf{v}_{if}进行更新$，于是FM模型的终极形态:
$$\hat{y}:=w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n}\sum_{j=i+1}^{n}\left \langle \textbf{v}_i, \textbf{v}_j \right \rangle x_i x_j$$
FM的直觉解释
文中的例子，用户对电影打分。
用户集合：
$$U = \left \{ Alice(A), Bob(B), Charlie(C),… \right \}$$
电影集合：
$$I=\left \{ Titanic(TI), NottingHill(NH), StartWars(SW), StarTrek(ST),… \right \}$$
打分数据集：
- (A, TI, 2010-1, 5),
- (A, NH, 2010-2, 3),
- (A, SW, 2010-4, 1),
- (B, SW, 2009-5, 4),
- (B, ST, 2009-8, 5),
- (C, TI, 2009-9, 1),
- (C, SW, 2009-12, 5)
处理完之后的特征如下：
这张图大家大概都快看吐了～再多看这一次也无妨了～彩色方框框起来的可以理解成一个域(field),一个域表示一个特征向量话之后的多个纬度，比如上面说的城市会变成600维的特征，那600维就是一个域，城市域～这个概念在之后的FFM中被提出。
- 1. 蓝色方框表示用户域，框起来的纬度是用户onehot之后的向量
- 2. 橘色是电影名字onehot之后的向量
- 3. 黄色是用户打过分的其他电影，大过分的电影系数加和等于1
- 4. 绿色是离散有序特征，表示用户给这个电影打分的时间 自2009年1月之后几个月了
- 5. 暗红色表示用户上一部打分的电影
- 6. 目标是用户对电影的打分1-5
拿一行解释一下吧，第一行，用户Alice对电影《泰坦尼克》的评分是5分，她还对《诺丁山(NH)》、《星球大战(SW)》也打过分，给《泰坦尼克(TI)》打分距离2009年1月13个月后，之前没给任何电影打过分。下面两条分别是Alice对《诺丁山》的打分是3分，对《星球大战》的打分是1分～
Alice应该是典型的女性观众群体，《泰坦尼克》和《诺丁山》都是非常有名的爱情电影，她对这两部对打分都很高，《泰坦尼克》就不废话了，《诺丁山》里的休·格兰特帅的一塌糊涂～但是《星球大战》这种太空史诗电影就只给了1分。
现在我们希望预测Alice对电影《星际迷航(ST)》的打分，很显然在数据集中Alice对电影《星际迷航》没有直接打分，在LR里面手动做特征组合的话 $w_{A,ST}=0$，这个系数就得不到更新。但是在FM里面每个特征都有自己的向量$\left \langle \textbf{v}_{A}, \textbf{v}_{ST} \right \rangle$就能干这个活。
- 首先，Bob和Charlie他们俩都对《星球大战》打出了比较高的分4分和5分，$\left \langle \textbf{v}_{A}, \textbf{v}_{SW} \right \rangle$和$\left \langle \textbf{v}_{C}, \textbf{v}_{SW} \right \rangle$这俩应该是差不多的，那么$\textbf{B}$和$\textbf{C}$也就差不多。
- Alice和Charlie对电影《泰坦尼克》和《星球大战》的打分是正好相反的，所以他们俩的向量$\textbf{A}$和$\textbf{C}$会非常不相等。
- 因为Bob给《星球大战》和《星际迷航》的打分都很高，所以$\textbf{SW}$和$\textbf{ST}$会很相似～
- 于是～～～Alice对《星际迷航》的打分应该跟她对《星球大战》的打分差不多。
FM计算
FM前半本的就是Linear的部分，不管他，我们看后面$\sum_{i=1}^{n}\sum_{j=i+1}^{n}\left \langle \textbf{v}_i, \textbf{v}_j \right \rangle x_i x_j$，如果直接结算的话复杂度是$O(kn^2)$，这个是可以优化的，需要回忆下小学数学
$$(x_1 + x_2 + x_3)^2 = x_1^2 + x_1x_2 + x_1x_3 + x_2x_1 + x_2^2 + x_2x_3 + x_3x_1 + x_3x_2 + x_3^2$$
类似矩阵运算
$$\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}\begin{bmatrix} x_1 & x_2 & x_3\end{bmatrix} = \begin{bmatrix} x_1^2 & x_1x_2 & x_1x_3\\ x_2x_1 & x_2^2 & x_2x_3\\ x_3x_1 & x_3x_2 & x_3^2 \end{bmatrix}$$
我们仅需要上三角部分，所以直觉的公式就是
$$\frac{1}{2}\left [ (x_1 + x_2 + x_3)^2 – (x_1^2 + x_2^2 + x_3^2) \right ]$$
论文给出了推到过程：
如果按最后的计算公示，算法复杂度就到了$O(kn)$ 了，因为实际操作中大家都是进行矩阵运算的，我们把上面的公式写成矩阵形式：权重矩阵$V \in R^{n \times k}$， 特征有$n$维，每维特征自带的权重分量是$k$维的，即矩阵的每一行代表一个特征向量$\textbf{v}_i$。输入矩阵$X\in R^{m\times n}$，有$m$个样本，每个样本有$n$维特征，于是FM的计算过程是
$$\text{SUM}((XV)^2, \text{DIM}=1) – \left [ \text{SUM}(V^2, DIM=1) \cdot X^2 \right ]$$
DIM=1表示按列求和，这里给出一个PyTorch的实现
class FMModel(torch.nn.Module):
def __init__(self, d, k):
super(FMModel, self).__init__()
self.linear_layer = torch.nn.Linear(in_features=526, out_features=1, bias=True)
self.V = torch.nn.Parameter(torch.rand(d, k))
def forward(self, x):
linear_out = self.linear_layer(x)
fm_part_1 = torch.sum(torch.square(torch.matmul(x, self.V)), dim = 1, keepdim = True)
fm_part_2 = torch.sum(torch.sum(torch.square(self.V), dim = 1) * torch.square(x), dim = 1, keepdim = True)
out = linear_out + 0.5 * (fm_part_1 - fm_part_2)
return out