特征交叉系列模型

FM 因子分解机

相比 Logistic回归模型只考虑单个特征对 $y$ 的影响, FM 因子分解机考虑了二阶组合特征:

\hat{y} (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} .

在推荐系统中, 特征值非常稀疏, 因此会对每一类特征学习一个隐变量, 也即 $x_{i} \to v_{i}$ , 进而替换 $w_{i, j} = ⟨ v_{i}, v_{j} ⟩ .$
事实上我们可以进一步降低复杂度: 从 $O (k n^{2})$ 到 $O (k n)$ , 这里 $k$ 是 $⟨ v_{i}, v_{j} ⟩$ 的复杂度. $\sum_{i = 1}^{n} \sum_{j = i + 1}^{n} ⟨ v_{i}, v_{j} ⟩ x_{i} x_{j} = \frac{1}{2} \sum_{f = 1}^{k} [{(\sum_{i = 1}^{n} v_{i, f} x_{i})}^{2} - \sum_{i = 1}^{n} v_{i, f}^{2} x_{i}^{2}] .$

推导

$\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} - \sum_{i = 1}^{n} ⟨ v_{i}, v_{i} ⟩ x_{i}^{2}) \\ = \frac{1}{2} (\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}^{2} x_{i}^{2}) \\ = \frac{1}{2} \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} v_{i, f}^{2} x_{i}^{2}) \\ = \frac{1}{2} \sum_{f = 1}^{k} ({(\sum_{i = 1}^{n} v_{i, f} x_{i})}^{2} - \sum_{i = 1}^{n} v_{i, f}^{2} x_{i}^{2}) . \end{aligned}$

回代一下得到:

FFM

多的 F 是域 (Field). 它会对特征进行分组, 例如性别 one-hot encoding 之后分成 x_female, x_male, 它们都属于性别. 定义域映射函数

f

f_{i}

为

x_{i}

对应的域编号, 它是一个额外的特征.

y = w_{0} + \sum_{i = 1}^{n} w_{i} x_{i} + \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} ⟨ V_{i, f_{j}}, V_{j, f_{i}} ⟩ x_{i} x_{j} .

如果共有 $F$ 个域, 每个 $x_{i}$ 拥有 $F$ 个隐向量, 当他们两两交叉, 二阶交叉项参数共有 $n k F$ .