背景知识

实对称矩阵分解

$\mathbf{W}$ 为实对称矩阵，那么该矩阵可按如下公式进行分解：

\begin{matrix} (1) & W_{n \times n} = V_{n \times k} V_{k \times n}^{T} \end{matrix}

FM（Factor Machine）又称为因子分解机，主要用于电商推荐场景。

$d$ $\mathbf{x} = (x_1, x_2, \cdots, x_d)$ ，那么，对于线性模型定义如下：

\begin{matrix} (2) & \begin{matrix} \hat{y} (x) = u_{0} + \sum_{i = 1}^{d} u_{i} x_{i} \\ 其 中 ， u_{0} 为 偏 置 项 \\ u = {u_{1}, u_{2}, \dots, u_{d}} 为 参 数 \end{matrix} \end{matrix}

该模型较为简单，没有考虑特征交叉的情况。为了提高模型的预测能力，现加入两两特征交叉：

\begin{matrix} (3) & \begin{matrix} \hat{y} (x) = u_{0} + \sum_{i = 1}^{d} u_{i} x_{i} + \sum_{i = 1}^{d} \sum_{j = i + 1}^{d} w_{i j} x_{i} x_{j} \\ 其 中 ， W = {| \begin{matrix} w_{11} & \dots & w_{1 d} \\ ⋮ & \dots & ⋮ \\ w_{d 1} & \dots & w_{d d} \end{matrix} |}_{d \times d} 为 参 数 ， 该 矩 阵 为 实 对 称 矩 阵 \end{matrix} \end{matrix}

$\mathrm{o}(d^2)$ ，复杂度较高。

$\mathbf{W} = \mathbf{V} \mathbf{V}^{\mathrm{T}}$ ，可以对模型进行如下优化：

\begin{matrix} (4) & \begin{array}{r} \begin{aligned} \hat{y} (x) & = u_{0} + \sum_{i = 1}^{d} u_{i} x_{i} + \sum_{i = 1}^{d} \sum_{j = i + 1}^{d} w_{i j} x_{i} x_{j} \\ = u_{0} + \sum_{i = 1}^{d} u_{i} x_{i} + \sum_{i = 1}^{d} \sum_{j = i + 1}^{d} ⟨ v_{i}, v_{j} ⟩ x_{i} x_{j} \\ = u_{0} + \sum_{i = 1}^{d} u_{i} x_{i} + \frac{1}{2} \sum_{i = 1}^{d} \sum_{j = 1}^{d} ⟨ v_{i}, v_{j} ⟩ x_{i} x_{j} - \frac{1}{2} \sum_{i = 1}^{d} ⟨ v_{i}, v_{i} ⟩ x_{i} x_{i} \\ = u_{0} + \sum_{i = 1}^{d} u_{i} x_{i} + \frac{1}{2} (\sum_{i = 1}^{d} \sum_{j = 1}^{d} \sum_{q = 1}^{k} v_{i q} v_{j q} x_{i} x_{j} - \sum_{i = 1}^{d} \sum_{q = 1}^{k} v_{i q} v_{i q} x_{i} x_{i}) \\ = u_{0} + \sum_{i = 1}^{d} u_{i} x_{i} + \frac{1}{2} \sum_{q = 1}^{k} (\sum_{i = 1}^{d} \sum_{j = 1}^{d} v_{i q} v_{j q} x_{i} x_{j} - \sum_{i = 1}^{d} v_{i q}^{2} x_{i}^{2}) \\ = u_{0} + \sum_{i = 1}^{d} u_{i} x_{i} + \frac{1}{2} \sum_{q = 1}^{k} [(\sum_{i = 1}^{d} v_{i q} x_{i}) (\sum_{j = 1}^{d} v_{j q} x_{j}) - \sum_{i = 1}^{d} v_{i q}^{2} x_{i}^{2}] \\ = u_{0} + \sum_{i = 1}^{d} u_{i} x_{i} + \frac{1}{2} \sum_{q = 1}^{k} [(\sum_{i = 1}^{d} v_{i q} x_{i})^{2} - \sum_{i = 1}^{d} v_{i q}^{2} x_{i}^{2})] \\ 其 中 ， v_{i}, v_{j} 为 矩 阵 V 的 列 向 量 \end{aligned} \end{array} \end{matrix}

$\mathrm{o}(kd)$ 。

一般使用MSE：

\begin{matrix} (5) & \begin{matrix} loss (\hat{y}, y) = \frac{1}{2} \sum_{i = 1}^{m} ({\hat{y}}^{(i)} - y^{(i)})^{2} \\ 其 中 ， m 为 样 本 个 数 \\ {\hat{y}}^{(i)} 为 第 i 个 样 本 的 预 测 值 \\ y^{(i)} 为 第 i 个 样 本 的 真 实 值 \end{matrix} \end{matrix}

对参数求导为：

\begin{matrix} (6) & \begin{matrix} \frac{\partial Loss (\hat{y}, y)}{\partial θ} = \sum_{i = 1}^{m} ({\hat{y}}^{(i)} - y^{(i)}) \frac{\partial {\hat{y}}^{(i)}}{\partial θ} \\ 其 中 ， θ 为 模 型 参 数 \end{matrix} \end{matrix}

一般使用交叉熵损失函数：

\begin{matrix} (7) & \begin{matrix} Loss (\hat{y}, y) = - [\sum_{i = 1}^{m} y^{(i)} \log σ ({\hat{y}}^{(i)}) + (1 - y^{(i)}) \log (1 - σ ({\hat{y}}^{(i)})] \\ 其 中 ， σ 为 Sigmoid 函 数 \end{matrix} \end{matrix}

对参数求导为：

\begin{matrix} (8) & \begin{aligned} \frac{\partial Loss (\hat{y}, y)}{\partial θ} & = - [\sum_{i = 1}^{m} y^{(i)} \frac{1}{σ ({\hat{y}}^{(i)})} \frac{\partial σ ({\hat{y}}^{(i)})}{\partial {\hat{y}}^{(i)}} \frac{\partial {\hat{y}}^{(i)}}{\partial θ} + (1 - y^{(i)}) \frac{1}{(1 - σ ({\hat{y}}^{(i)})} \frac{- \partial σ ({\hat{y}}^{(i)})}{\partial {\hat{y}}^{(i)}} \frac{\partial {\hat{y}}^{(i)}}{\partial θ}] \\ = - [\sum_{i = 1}^{m} y^{(i)} \frac{1}{σ ({\hat{y}}^{(i)})} σ ({\hat{y}}^{(i)}) (1 - σ ({\hat{y}}^{(i)})) \frac{\partial {\hat{y}}^{(i)}}{\partial θ} + (y^{(i)} - 1) \frac{1}{(1 - σ ({\hat{y}}^{(i)})} σ ({\hat{y}}^{(i)}) (1 - σ ({\hat{y}}^{(i)})) \frac{\partial {\hat{y}}^{(i)}}{\partial θ}] \\ = - [\sum_{i = 1}^{m} y^{(i)} (1 - σ ({\hat{y}}^{(i)})) \frac{\partial {\hat{y}}^{(i)}}{\partial θ} + (y^{(i)} - 1) σ ({\hat{y}}^{(i)}) \frac{\partial {\hat{y}}^{(i)}}{\partial θ}] \\ = - [\sum_{i = 1}^{m} \frac{\partial {\hat{y}}^{(i)}}{\partial θ} (y^{(i)} - σ ({\hat{y}}^{(i)}))] \end{aligned} \end{matrix}

$\hat{y}$ 对参数的偏导数，如下：

\begin{matrix} (9) & \frac{\partial \hat{y}}{\partial θ} = {\begin{cases} 1, & if θ = u_{0} \\ x_{i}, & if θ = u_{i} \\ (x_{i} \sum_{j = 1}^{d} v_{j q} x_{j}) - v_{i q} x_{i}^{2}, & if θ = v_{i q} \end{cases} \end{matrix}