传统的集中式个性化推荐

矩阵分解

矩阵分解（MF），是最常用的推荐算法之一。我们将用户对物品的反馈用矩阵 $r$ 表示，这个矩阵也被称为评分矩阵。将原始评分矩阵 $r$ 分解为 $p$ 和 $q$ ，使得：

$r=p\times q$ .

其中， $r$ 为 $m\times n$ ， $p$ （用户隐向量矩阵）的维度为 $m\times k$ ， $q$ （物品隐向量矩阵）的维度为 $k\times n$ ， $k$ 是一个较小的数。

MF的优化函数如下：

$\min_{p,q} \Sigma_{(i,j)}\left(r_{ij}- \langle p_i,q_j \rangle\right )+\lambda\|p\|^2_2+\mu\|q\|^2_2.$

MF算法通过优化式（1）来填充和预测缺失的评分值，其中 $r_{ij}$ 代表原始评分矩阵中用户 $i$ 对物品 $j$ 的非0评分，而 $p_i$ 代表用户 $i$ 的隐向量， $q_j$ 代表物品 $j$ 的隐向量。该函数的优化目标是：使得用户 $i$ 的隐向量 $p_i$ 与物品 $j$ 的隐向量 $q_j$ 之间的点积值，与评分矩阵中用户 $i$ 对物品 $j$ 的实际评分值 $r_{ij}$ 尽可能接近。

因子分解机

推荐系统的另一种常用算法是因子分解机（FM），它将推荐问题归结为回归问题。传统的线性模型只能捕捉到线性信息，不能捕获非线性信息，也就是特征与与特征之间的相互作用。

这种特征与与特征之间的相互作用，就是特征工程中常用的交叉特征（也称为组合特征）。FM模型如下式所示，

$y=\omega_0+\sum_{i=1}^{n}\omega_ix_i+\sum_{0<i<j \leqslant n}\langle v_i,v_j \rangle x_ix_j.$

联邦个性化推荐

矩阵分解

假设公司A是以书籍为内容进行推荐，而公司B是以电影为内容进行推荐。根据协同过滤的思想，具有相同观影兴趣的用户很可能有相同的阅读兴趣。

这个场景下，每一家公司分别有用户对物品的评分矩阵，但由于隐私保护的原因，公司不能共享这些评分数据。按照上面介绍的MF算法，它将评分矩阵分解为用户隐特征向量和物品隐特征向量。由于两家公司的用户群体相同，它们共享用户的隐向量信息 $p$ 。接下来，这个算法的流程描述如下：

步骤1：由可信第三方服务端初始化用户隐向量矩阵 $p$ ，并使用公钥对其进行加密 $\left [ \left [ p \right ]\right ]$ 。同时，各家参与公司分别初始化自己的物品隐向量矩阵 $q$ 。
步骤2：服务端将加密的用户隐向量矩阵 $\left [ \left [ p \right ]\right ]$ 分别发送给所有参与联合建模的公司。
步骤3：各参与方利用私钥解密用户隐向量矩阵。先利用梯度下降更新自己的本地物品隐向量矩阵。同时，计算用户隐向量矩阵 $p$ 的梯度，加密后发送给服务器。
步骤4：服务器汇总接收到的加密用户隐向量梯度，更新矩阵 $p$ 。
步骤5：重复步骤2~4，直到收敛。

个人理解这个方法的核心思想是： $p$ 的更新用到了联邦学习的优势，并且由于 $q$ 是保密的，因此可以保护隐私安全。

联邦因子分解机

假设公司A是一家在线的书籍销售商，公司B是一家社交网络公司，公司B不直接销售商品，但是它有每个用户的画像数据。如果能够利用这部分数据，则对公司A的销售额同样有很好的提升。

假设现在公司A有用户的反馈分数和部分特征信息，设为 $\left ( X_1,Y \right )$ ，而公司B拥有额外的特征数据，设为 $X_2$ ，其FM模型可以表示为

$\hat{y}=\omega_0^A+\sum_{i=1}^n \omega_i^Ax_i^A+\sum_{0<i<j \leqslant n}\langle v_i^A,v_j^A \rangle x_i^Ax_j^A+\omega_0^B+\sum_{i=1}^n \omega_i^Bx_i^B+\sum_{0<i<j \leqslant n}\langle v_i^B,v_j^B \rangle x_i^Bx_j^B+\sum_{0<i\leqslant n, 0<j\leqslant m}\langle v_i^A,v_j^B \rangle x_i^Ax_j^B$

下面给出联邦学习因子分解机的详细算法流程：

步骤1：公司A和公司B各自初始化本地模型，即对于公司A，初始化参数 $\omega_i^A$ 和 $v_i^A$ ；对于公司B，初始化参数 $\omega_i^B$ 和 $v_i^B$ 。
步骤2：公司B将中间结果 $\omega_0^B+\Sigma_{j=1}^m \omega_i^Bx_i^B$ 和 $v_i^Bx_i^B$ 加密，传输给公司A。
步骤3：公司A接收到公司B传输的加密中间结果，计算加密残差 $\left [ \left [ d \right ] \right ]=\left [ \left [ \hat{y}-y \right ] \right ]$ ，公司A将 $\left [ \left [ d \right ] \right ]$ 和 $\left [ \left [ v_i^Ax_i^A \right ] \right ]$ 发送回公司B。
步骤4：公司A和公司B分解求解加密梯度。
步骤5：将这些加密的参数梯度上传到第三方服务端解密，结果分别重新返回公司A和公司B，利用梯度下降更新参数。
重复步骤2~6，直到算法收敛