聊聊因子分解机（FM）

2020-01-08 本文已影响0人 SoSurprise

说到FM先说一个叫交叉特征的事，因为特征都是相互独立的，我们想要找到一些组合特征，只能两两交叉相乘，所以我们在线性模型加一个多项式
$\hat y = f(\vec x) = w_0 + \sum_{i = 1}^{n}w_ix_i + \sum_{0 < i < j <= n}w_{i, j}x_ix_j.$
这是不是看起来就是一个SVM模型：核函数选择为二阶多项式核
看起来很完美，但是我们的特征都是独热编码（OneHot），所以 $x_ix_j$ 的结果大多数情况下就是0，这样的话后面这个多项式就没法学习了，就算可以学习，如果出现不是0的情况就会出现问题，泛化能力很差。
因子分解机（FM）我们的主角就是解决这个问题：
FM 模型的解决办法是为每个维度的特征（ $x_i$ ）学习一个表征向量（ $v_i$ ，其实可以理解为是特征 ID 的 embedding 向量）。而后将 $x_i$ 和 $x_j$ 的乘积的权重设定为各自表征向量的点积。
$\hat y = f(\vec x) = w_0 + \sum_{i = 1}^{n}w_ix_i + \sum_{0 < i < j <= n}\langle \vec v_i, \vec v_j\rangle x_ix_j.$
中间的推倒过程在后面。简化结果：
$\hat y = f(\vec x) = w_0 + \sum_{i = 1}^{n}w_ix_i + \frac{1}{2}\sum_{f= 1}^{k}((\sum_{i=1}^{n} \vec v_{i,f} x_i)^2-\sum_{i=1}^{n}\vec v_{i,f}^2 x_i^2)$
这里很容易看到没有了特征相乘了，接下来说说效率问题；
考虑到 FM 模型会对特征进行二阶组合，在有 $n$ 个原始特征时，交叉特征就会有 $\frac{n ^ 2 - n}{2}$ 个。因此，如果不做任何优化，FM 模型的复杂度会是 $O(n^2)$ ，具体来说是 $O(kn^2)$ （其中 $k$ 是表征向量的长度）。在特征规模非常大的场景中，这是不可接受的。
那么问题来了，是否有办法将复杂度降低到 $O(kn)$ 呢？答案是可以的，我们来看针对特征交叉项的一系列变换。

$\begin{aligned} \sum_{0 < i < j <= n}\langle \vec v_i, \vec v_j\rangle x_ix_j &{} = \sum_{i = 1}^{n - 1}\sum_{j = i + 1}^{n} \langle \vec v_i, \vec v_j\rangle x_ix_j \\ &{} = \frac{1}{2}\sum_{i = 1}^{n}\sum_{j = 1}^{n}\langle \vec v_i, \vec v_j\rangle x_ix_j - \frac{1}{2}\sum_{i = 1}^{n}\langle \vec v_i, \vec v_i\rangle x_ix_i \\ &{} = \frac{1}{2}\biggl(\sum_{i = 1}^{n}\sum_{j = 1}^{n}\sum_{d = 1}^{k}\vec v_{i, d}\vec v_{j, d}x_ix_j - \sum_{i = 1}^{n}\sum_{d = 1}^{k}\vec v_{i, d}^2x_i^2\biggr) \\ &{} = \frac{1}{2}\sum_{d = 1}^{k}\biggl(\sum_{i = 1}^{n}\sum_{j = 1}^{n}\vec v_{i, d}\vec v_{j, d}x_ix_j - \sum_{i = 1}^{n}\vec v_{i, d}^2x_i^2\biggr) \\ &{} = \frac{1}{2}\sum_{d = 1}^{k}\biggl(\Bigl(\sum_{i = 1}^{n}\vec v_{i, d}x_i\Bigr)\Bigl(\sum_{j = 1}^{n}\vec v_{j, d}x_j\Bigr) - \sum_{i = 1}^{n}\vec v_{i, d}^2x_i^2\biggr) \\ &{} = \frac{1}{2}\sum_{d = 1}^{k}\biggl(\Bigl(\sum_{i = 1}^{n}\vec v_{i, d}x_i\Bigr)^2 - \sum_{i = 1}^{n}\vec v_{i, d}^2x_i^2\biggr). \end{aligned}$

等式第一行是一个平凡的变换，很容易理解。

等式第二行修改了求和符号的范围。原本的求和符号中有 $\frac{n ^ 2 - n}{2}$ 项；变换之后第一项中的求和符号有 $n^2$ 项，第二项中的求和符号有 $n$ 项。因此两式恰好相等。

等式第三行是对向量内积的展开，很容易理解。

等式第四行是运用了加法的结合律，将 $\sum_{d = 1}^{k}$ 抽到外面，这步容易理解。

等式第五行是连续两次逆向使用了乘法对加法的分配率（提取公因子），这一步可能稍微难理解一些。简便起见，我们将 $\vec v_{i, d}x_i$ 记作 $a_i$ ；将 $\vec v_{j, d}x_j$ 记作 $a_j$ 。则变换前的公式记作 $\sum_{i = 1}^{n}\sum_{j = 1}^{n}a_ia_j$ 。将它展开是：

$\begin{aligned} \sum_{i = 1}^{n}\sum_{j = 1}^{n}a_ia_j = {}& a_1a_1 + a_1a_2 + \cdots + a_1a_n + \\ {}& a_2a_1 + a_2a_2 + \cdots + a_2a_n + \\ {}& \cdots + \\ {}& a_na_1 + a_na_2 + \cdots + a_na_n \\ = {}& a_1\bigl(a_1 + a_2 + \cdots + a_n\bigr) + \\ {}& a_2\bigl(a_1 + a_2 + \cdots + a_n\bigr) + \\ {}& \cdots + \\ {}& a_n\bigl(a_1 + a_2 + \cdots + a_n\bigr) \\ = {}& a_1\Bigl(\sum_{j = 1}^{n}a_j\Bigr) + a_2\Bigl(\sum_{j = 1}^{n}a_j\Bigr) + \cdots + a_n\Bigl(\sum_{j = 1}^{n}a_j\Bigr) \\ = {}& \sum_{i = 1}^{n}a_i\sum_{j = 1}^{n}a_j \\ = {}& \Bigl(\sum_{i = 1}^{n}\vec v_{i, d}x_i\Bigr)\Bigl(\sum_{j = 1}^{n}\vec v_{j, d}x_j\Bigr). \end{aligned}$
等式第六行也很明显。第五行的结果中的两个求和项仅仅是下标不同，实际上完全是一回事，因此直接平方就好了。

如此一来，FM 的预测公式变成了下面这样

$\begin{aligned} \hat y &{} = f(\vec x) \\ &{} = w_0 + \sum_{i = 1}^{n}w_ix_i + \frac{1}{2}\sum_{d = 1}^{k}\biggl(\Bigl(\sum_{i = 1}^{n}\vec v_{i, d}x_i\Bigr)^2 - \sum_{i = 1}^{n}\vec v_{i, d}^2x_i^2\biggr). \end{aligned}$

显然，它的复杂度是 $O(kn)$ 。考虑到特征的稀疏性，尽管 $n$ 可能很大，但很多 $x_i$ 都是零。因此其实际复杂度应该是 $O(k\bar n)$ ——其中 $\bar n$ 表示样本不为零的特征维度数量的平均值。

聊聊因子分解机（FM）

猜你喜欢

热点阅读