FM算法详解（因子分解机）

什么是FM？

FM即Factor Machine，因子分解机。

任意的N×N 实对称矩阵]都有 N 个线性无关的特征向量。并且这些特征向量都可以正交单位化而得到一组正交且模为 1 的向量。故实对称矩阵 A 可被分解成：

对称矩阵分解

其中Q为正交矩阵，Λ为实对角矩阵。

类似地，所有二次项参数ω_ij可以组成一个对称阵W

（为了方便说明FM的由来，对角元素可以设置为正实数），那么这个矩阵就可以分解为

image.png
V的第j列v_j便是第j维特征x_j的隐向量。换句话说，特征分量 x_i和x_j

的交叉项系数就等于 x_i对应的隐向量与和x_j对应的隐向量的内积，即每个参数
ω_ij=<v_i,v_j>，这就是FM模型的核心思想。

为了求出ω_ij，我们需要求出特征分量x_i的辅助向量v_i=(v_i1,v_i2,v_i3,...,v_ik),

x_j的辅助向量v_j=(v_j1,v_j2,v_j3,...,v_jk)
k表示隐向量长度(k<<n)，转换过程如下图所示：

image.png image.png

W^*矩阵对角线上面的元素即为交叉项的参数。

如何组合？

多项式模型是包含特征组合的最直观的模型。在多项式模型中，特征 x_i和 x_j

的组合采用 x_i x_j表示，即 x_i和 x_j都非零时，组合特征 x_i x_j才有意义。从对比的角度，本文只讨论二阶多项式模型。模型的表达式如下：

二阶多项式模型1

其中，n代表样本的特征数量， x_i是第i个特征的值，ω₀,ω_i,ω_ij是模型参数。

从公式来看，模型前半部分就是普通的LR线性组合，后半部分的交叉项即：特征的组合。单从模型表达能力上来看，FM的表达能力是强于LR的，至少不会比LR弱，当交叉项参数全为0时退化为普通的LR模型。

从公式(1)可以看出，组合特征的参数一共有(n*(n-1))/2个，任意两个参数都是独立的。

举例说明

通俗点来讲就是把自己乘自己的那部分减掉，只留下交叉项
假设有3个特征x₁ x₂ x₃，每一个特征的隐变量分别为v₁=(1 1)、v2=(4 2)、v3=(1 3)，即：

V = [
        [1, 1],
        [4, 2],
        [1, 3]
    ]

所以
W=V*V^t

[
  [ 2  6  4]
  [ 6 20 10]
  [ 4 10 10]
]

Σ³_i=1 Σ³_j=1w_ij x_i x_j=
2x₁x₁+6x₁x₂+4x₁x₃

+6x₂x₁+20x₂x₂+10x₂x₃

+4x₁x₁+10x₃x₂+10x₂x₃

实际上，我们应该考虑的交叉项应该是排除自身组合的项，即对于x₁x₁、x₂x₂、x₃x₃不认为是交叉项，那么真正的交叉项为x₁x₂、x₁x₃、x₂x₁、x₂x₃、x₃x₁、x₃x₂。
去重后，交叉项即x₁x₂、x₁x₃、x₂x₃。这也是公式中1/2出现的原因。
W矩阵的上半部分为w_ij的取值范围，所以个数为(n*(n-1))/2=(3*(3-1))/2=3

隐向量v就是embedding vector?

我们口中的隐向量vi实际上是一个向量组，其形状为（输入特征One-hot后的长度，自定义长度k）；
隐向量vi代表的并不是embedding vector，而是在对输入进行embedding vector的向量组，也可理解为是一个权矩阵；
由输入样本x_ivi得到的向量才是真正的embedding vector。
由输入样本x_iv（矩阵）得到的向量才是真正的embedding vector。

参见https://www.zhihu.com/question/48107602