Question

1. 由于在Amazon 、Apple 、Netflix 等电商网站中的应用，协同过滤在机器学习社区中受到广泛关注。这类网站通常会向用户提供个性化推荐，推荐质量对整体成功overall success 至关重要，因为好的推荐会增加用户购买倾向。然而，推荐正确的 item 是一项非常困难的任务：有很多 item 可供选择，并且用户只愿意考虑少量推荐（通常在十个左右）。

   协同过滤通过从当前用户和其它用户的历史评分中学习当前用户的推荐函数来解决这个问题。已知的数据可以认为是稀疏的评分矩阵 $ \mathbf R\in \mathbb R^{n\times m} $ ，其中 $ n $ 为用户数量、 $ m $ 为 item 数量， $ r_{i,j} $ 表示用户 $ i $ 对 item $ j $ 的评分。通常评分为五星级别，因此 $ r_{i,j}\in \{0,1,\cdots,5\} $ ，0 表示用户尚未对 item 进行评分。从这个意义上讲，0 分比较特殊。

   论文 《Improving maximum margin matrix factorization》 提出了针对 Maximum Margin Matrix Factorization:MMMF 的扩展方法，包括引入偏置项 offset term、自适应正则化、user-item 二部图的 graph kernel 。

2. 相关工作：协同过滤的一种常见方法是将根据数据来训练一个因子模型 factor model。例如，通过为数据集中每个用户和 item 抽取一个因子向量，然后基于 user 因子向量和 item 因子向量的内积来预测评分。这些方法背后的基本思想是：用户偏好和 item 属性都可以通过一组因子来建模。

   矩阵分解方法的基本思想是用低秩矩阵 $ \hat{\mathbf R} $ 来近似原始矩阵 $ \mathbf R $ 。具体而言，矩阵分解方法的目标是找到这样一个近似矩阵 $ \hat{\mathbf R} $ ： $ \mathbf R $ 中观测值和 $ \hat{\mathbf R} $ 中预测值的平方距离之和最小化。一种可行的做法是使用 $ \mathbf R $ 的奇异值分解，并仅使用分解过程中获得的一部分向量。在信息检索社区中，这种数值运算通常被称作潜在语义索引 Latent Semantic Indexing: LSI 。

   然而，奇异值分解的方法并不能正确判断 $ \mathbf R $ 的构成方式。 $ r_{i,j} = 0 $ 表示我们没有观察到 $ (i,j) $ 的 pair ，但是它并不表示用户 $ i $ 不喜欢 item $ j $ 。论文 《Weighted low-rank approximations》 提出了一种替代方法，它是本文所述方法的基础。我们的目标是找到两个矩阵 $ \mathbf U\in \mathbb R^{n\times f} $ 和 $ \mathbf V\in \mathbb R^{m\times f} $ ，使得 $ \hat{\mathbf R} = \mathbf U\mathbf V^\top $ 逼近 $ \mathbf R $ 中的观察值，而不是同时近似所有的项。

   一般而言，找到低秩近似的全局最优解是不现实的：特别是 《Weighted low-rank approximations》 提出的用于计算加权分解的方法需要半定规划 semi-definite programming ，这仅支持数百个最多数千个数据。与最小化秩的目标不同，最大边际矩阵分解 Maximum Margin Matrix Factorization: MMMF 的目标是最小化 $ \mathbf U $ 和 $ \mathbf V $ 的 Froebenius 范数，从而在各自独立的情况下产生一组凸优化问题，因此可以通过当前的优化技术进行处理。《Rank, trace-norm and max-norm》 表明：优化 Froebenius 范数是优化 rank 的一个很好的代理。在 《Probabilistic matrix factorization》 中，作者也提出了基于矩阵分解的类似思想。

   最近，《Cofi rank—maximum margin matrix factorization for collaborative ranking》提出扩展通用 MMMF 框架，从而最小化结构化损失（即 ranking loss ），而不是已知评分的平方误差 sum。关键原因是：协同过滤通常是推荐系统的核心，在用户偏好方面只有未评分 item 的排序才重要。为了有效优化结构化 ranking loss，《Bundle methods for machine learning》 使用了一种新的优化技术来最小化归一化折扣累计增益Normalized Discounted Cumulative Gain: NDCG 损失。

3. 本文贡献：基于上述结果，论文《Improving maximum margin matrix factorization》对这些 MMMF 模型进行了扩展。

   • 在多类保序回归multiclass ordinal regression 中计算梯度的有效方法。
   • 为处理用户和 item 的异质性，提出 user bias 和 item bias。
   • 一种自适应正则化方案，可以处理每个用户不同数量的 item、以及每个 item 不同数量的用户。
   • 类似于 《Probabilistic matrix factorization》 和 《Unifying collaborative and content-based filtering》 的精神，论文提出一个 graph kernel 从而在推荐图中捕获 user-item 相似性。作者证明这两种方法本质上是等价的，并且等于推荐图上的 graph kernel 。

   对于这些扩展中的每一个，论文展示了如何将它们集成到 MMMF 框架中，使得 《Cofi rank—maximum margin matrix factorization for collaborative ranking》 中提出的结构化估计仍然可行。

10.1 MMMF

1. 令 user-item 评分矩阵为 $ \mathbf R=\{r_{i,j}\}\in \mathbb R^{n\times m} $ ，其中 $ n $ 为用户数量、 $ m $ 为 item 数量、 $ r_{i,j} $ 表示用户 $ i $ 为 item $ j $ 的评分。

   假设每个用户 $ i $ 关联一个用户因子向量 $ \mathbf{\vec u}_i\in \mathbb R^f $ ，每个item $ j $ 关联一个item 因子向量 $ \mathbf{\vec v}_j\in \mathbb R^f $ ，则模型预估用户 $ i $ 对 item $ j $ 的评分为： $ \hat r_{i,j} = \mathbf{\vec u}_i\cdot \mathbf{\vec v}_j $ 。

   令所有用户因子向量构成用户因子矩阵 $ \mathbf U\in \mathbb R^{n\times f} $ ，其中第 $ i $ 行表示用户 $ i $ 的用户因子向量。令所有 item 因子向量构成 item 因子矩阵 $ \mathbf V\in \mathbb R^{m\times f} $ ，其中第 $ j $ 行表示 item $ j $ 的 item 因子向量。则有： $ \hat{\mathbf R} = \mathbf U\mathbf V^\top $ 为模型预估的评分矩阵。

2. 我们的目标函数为带正则化的损失函数，其中正则化项为 $ \mathbf U $ 和 $ \mathbf V $ 的 F 范数：

   $ \min_{\mathbf U,\mathbf V} \mathcal L(\mathbf R,\hat{\mathbf R}) + \frac{\lambda_u}{2}||\mathbf U||_F^2+ \frac{\lambda_v}{2}||\mathbf V||_F^2 $

   其中： $ \mathcal L(\cdot,\cdot) $ 为损失函数， $ \lambda_u,\lambda_v $ 为正则化系数。

   该最优化问题可以通过 semi-definite reformulation 精确求解，但是计算复杂度太高。考虑到固定 $ \mathbf U $ 时目标函数是 $ \mathbf V $ 的凸函数、固定 $ \mathbf V $ 时目标函数是 $ \mathbf U $ 的凸函数，因此可以通过固定变量来交替优化 $ \mathbf U $ 和 $ \mathbf V $ 来求解。

3. 原始MMMF 中， $ \mathcal L(\cdot,\cdot) $ 为误差的平方和：

   $ \mathcal L(\mathbf R,\hat{\mathbf R}) = \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^m\delta_{i,j}(r_{i,j} - \hat r_{i,j})^2 $

   其中 $ \delta_{i,j} $ 表示：如果用户 $ i $ 对 item $ j $ 评分则 $ \delta_{i,j} = 1 $ ，否则 $ \delta_{i,j} = 0 $ 。

   这种形式的损失函数无法处理用户粒度的损失。事实上对于单个用户 $ i $ 而言，我们希望能够准确预测用户 $ i $ 感兴趣的 item，对于用户 $ i $ 不感兴趣的 item 我们不太关心。因此对于用户 $ i $ ，我们需要根据 $ (r_{i,1},\cdots,r_{i,m}) $ 和 $ (\hat r_{i,1},\cdots,\hat r_{i,m}) $ 来评估用户粒度的损失。

   定义 $ \mathbf{\vec r}_i = (r_{i,1},\cdots,r_{i,m})^\top $ 为用户 $ i $ 的观测评分 ， $ \hat{\mathbf{\vec r}}_i=(\hat r_{i,1},\cdots,\hat r_{i,m})^\top $ 为用户 $ i $ 的预估评分，论文 Weimer et al. 2008 提出了一种逐用户的损失：

   $ \mathcal L(\mathbf R, \hat{\mathbf R}) = \sum_{i=1}^n l(\mathbf{\vec r}_i,\hat{\mathbf{\vec r}}_i) $

   其中 $ l(\cdot,\cdot) $ 为逐用户的损失。

4. 现在考虑 ranking 损失，它也被称作保序回归分 ordinal regression score 。

   假设用户 $ i $ 的所有评分 $ \mathbf{\vec r}_i $ 中，真实评分为 $ a $ 的item 有 $ m^{(i)}_a $ 个，则有 $ \sum_a m^{(i)}_a = m $ 。

   假设用户 $ i $ 评分的一对item $ (j_1,j_2) $ ，如果满足 $ r_{i,j_1} \gt r_{i,j_2} $ 且 $ \hat r_{i,j_1}\gt \hat r_{i,j_2} $ ，则我们认为预估的排序是正确的，否则我们认为产生了一个单位的损失。

   因此我们定义损失函数为：

   $ l(\mathbf{\vec r}_i,\hat{\mathbf{\vec r}}_i) = \sum_{r_{i,j_1}\gt r_{i,j_2}} C(r_{i,j_1}, r_{i,j_2}) I(\hat r_{i,j_1}\le \hat r_{i,j_2}) $

   其中：

   • $ I(\cdot) $ 为示性函数：当条件为 true 时为 1 ，条件为 false 为 0
   • $ C(r_{i,j_1}, r_{i,j_2}) $ 表示对于用户 $ i $ 而言，混淆了 item $ j_1 $ 和 $ j_2 $ 的顺序的损失。

   考虑到这里有 $ \frac{1}{2}\left[m^2-\sum_a \left(m_a^{(i)}\right)^2\right] $ 项，因此我们需要归一化使得不同用户的损失可以相互比较。另外，为了使得损失函数可导，我们使用一个 soft-margin 损失从而得到一个凸的、可微的损失函数：

   $ l(\mathbf{\vec r}_i,\hat{\mathbf{\vec r}}_i) = \frac{2}{m^2-\sum_a \left(m_a^{(i)}\right)^2}\sum_{r_{i,j_1}\gt r_{i,j_2}} C(r_{i,j_1}, r_{i,j_2}) \max\left(0, 1- \left(\hat r_{i,j_1}-\hat r_{i,j_2}\right)\right) $

   .

10.2 MMMF 扩展

10.2.1 bias

1. 当考虑用户bias 和 item bias 时，我们的模型更新为：

   $ \hat r_{i,j} = \mathbf{\vec u}_i\cdot \mathbf{\vec v}_j + b_i^u + b_j^v $

   其中 ： $ b_i^u $ 为用户 $ i $ 的 bias、 $ b_j^v $ 为item $ j $ 的 bias 。

   在实践过程中，可以简单的将 $ \mathbf U $ 和 $ \mathbf V $ 扩展为：

   $ \mathbf U = \begin{bmatrix} \mathbf{\vec u}_1^\top&b_1^u&1\\ \vdots&\vdots&\vdots\\ \mathbf{\vec u}_n^\top&b_n^u&1 \end{bmatrix} \in \mathbb R^{n\times (f+2) }\quad \mathbf V = \begin{bmatrix} \mathbf{\vec v}_1^\top&1&b_1^v\\ \vdots&\vdots&\vdots\\ \mathbf{\vec v}_m^\top&1&b_m^v \end{bmatrix} \in \mathbb R^{m\times (f+2) } $

   .

10.2.2 自适应正则化

1. 为每个item （或用户）使用单个统一、固定的正则化参数不是一个很好的选择。例如：

   • 对于评分数量很少的用户，我们需要一个较大的正则化系数从而缓解过拟合。
   • 对于评分数量很多的用户，我们需要一个小得多的正则化系数从而期望充分学习。

   同样的，对于评分数量差距很大的 item ，它们的正则化也需要区别对待。

   可以考虑使用基于样本规模的自适应正则化sample-size adaptive regularization 。定义对角矩阵：

   $ \mathbf D^U = \text{diag}\left(\frac{1}{s_{1}^{ \alpha}},\cdots,\frac{1}{s_{n}^{ \alpha}}\right)\\ \mathbf D^V = \text{diag}\left(\frac{1}{t_1^{ \alpha}},\cdots,\frac{1}{t_m^{ \alpha}}\right) $

   其中： $ s_i $ 表示用户 $ i $ 评分的数量， $ t_j $ 为 item $ j $ 评分的数量， $ \alpha $ 为于平滑系数。论文发现当 $ \alpha = 0.5 $ 时效果最好。

   最终我们的目标函数为：

   $ \min_{\mathbf U, \mathbf V} \mathcal L(\mathbf R, \mathbf U\mathbf V^\top) + \frac{\lambda_u}{2}\text{tr}\left(\mathbf U^\top\mathbf D^U \mathbf U\right) + \frac{\lambda_v}{2}\text{tr}\left(\mathbf V^\top\mathbf D^V\mathbf V\right) $

   其中 $ \text{tr}(\cdot) $ 为矩阵的迹，它满足 $ \text{tr}(\mathbf U^\top\mathbf U) = ||\mathbf U||_F $ 。

   实验结果证明：该方法效果是负向的！。

10.2.3 Graph Kernel

1. 目前为止我们忽略了一个非常重要的信息：评分本身不是随机的。如：如果某个用户为 《指环王1》 给了一个很高的评分，那么即使不查看评分矩阵 $ \mathbf R $ ，我们猜到该用户大概率也会对 《指环王2》感兴趣。因此，我们希望除了评分矩阵 $ \mathbf R $ 之外，还能够利用这个结构信息 structural information 。

   定义 $ \mathbf S = \{\delta_{i,j}\}\in \mathbb R^{n\times m} $ ，它定义了关于user-item 二部图的邻接矩阵。我们定义用户 $ i_1 $ 和用户 $ i_2 $ 之间的核函数为：

   $ \mathcal K(i_1,i_2) = \mathbf{\vec s}_{i_1} \cdot \mathbf{\vec s}_{i_2} $

   其中 $ \mathbf{\vec s}_{i} = (\delta_{i,1},\cdots,\delta_{i,m})^\top $ 为邻接矩阵的第 $ i $ 行。

   我们考虑将用户 $ i $ 邻接的item 的线性组合作为用户 $ i $ 的特征，即使用权重矩阵 $ \mathbf W\in \mathbb R^{m\times f} $ 进行线性变换，则用户的特征矩阵变为： $ \mathbf U + \mathbf S\mathbf W $ 。

   考虑到不同用户评分数量不同，则我们也可以对 $ \mathbf S $ 进行按行归一化，得到：

   $ \bar{\mathbf{\vec s}}_{i} = \frac{\mathbf{\vec s}_{i}}{||\mathbf{\vec s}_{i}||},\quad \overline{\mathbf S} = \begin{bmatrix} \bar{\mathbf{\vec s}}_{1}^\top\\ \vdots\\ \bar{\mathbf{\vec s}}_{n}^\top \end{bmatrix}\in \mathbb R^{n\times m} $

   可以证明该方法等价于在用户和 item 之间定义的二部图上应用 graph kernel 。

   最终我们的目标函数为：

   $ \min_{\mathbf U, \mathbf V} \mathcal L(\mathbf R,(\mathbf U + \mathbf S \mathbf W)\mathbf V^\top) + \frac{\lambda_u}{2}\text{tr}\left(\mathbf U^\top\mathbf D^U \mathbf U\right) + \frac{\lambda_v}{2}\text{tr}\left(\mathbf V^\top\mathbf D^V\mathbf V\right) + \frac{\lambda_w}{2}||\mathbf W||^2_F $

   这相当于将用户 $ i $ 的 representation 分解为两部分：

   $ \mathbf{\vec u}_i^\prime = \mathbf{\vec u}_i + \sum_{j=1}^n s_{i,j} \mathbf{\vec w}_j $

   第一部分为原始的 user representation。第二部分为 item representation 的加权，权重为 $ s_{i,j} $ （即用户 $ i $ 对 item $ j $ 的评分，可以考虑归一化）。这里对 item 引入了另一个 representation 矩阵 $ \mathbf W $ 。

10.5 实验

1. 数据集：EachMovie 和 MovieLens 数据集。

   • EachMovie 数据集包含 61265 个用户、1623 部电影、 2811717 个评分。
   • MovieLens 数据集包含 983 个用户、1682 部电影、10 万评分。

2. 评估指标：在所有实验中，我们使用Normalized Discounted Cumulative Gain:NDCG 指标。

   对于用户 $ i $ 的预估值 $ \hat{\mathbf{\vec r}}_i = (\hat r_{i,1},\cdots,\hat r_{i,m}) $ ，定义 $ \pi $ 为这些预估结果的一个排序（排序从1开始）：

   $ \pi = \arg\text{sort}([\hat r_{i,1},\cdots,\hat r_{i,m}]) $

   定义 $ \pi_s $ 为真实评分的一个排序：

   $ \pi_s = \arg\text{sort}([ r_{i,1},\cdots, r_{i,m}]) $

   定义累积增益 Cumulative Gain:CG 为：每个推荐结果排名相关性得分累加值。即：

   $ \text{CG}(\mathbf{\vec r}_i,\pi)@k = \sum_{j=1}^k r_{i,\pi[j]} $

   其中 $ r_{i,\pi[j]} $ 表示预估排在第 $ j $ 个位置的 item 的真实评分。

   $ \text{CG}@k $ 越大表示预估排名top k 的 item 的真实评分越越高。但是， $ \text{CG}@k $ 未考虑位置因素的影响，折扣累积增益Discounted Cumulative Gain:DCG 在 CG 的基础上考虑了位置因素：

   $ \text{DCG}(\mathbf{\vec r}_i,\pi)@k = \sum_{i=1} \frac{2^{r_{i,\pi[j]}}-1}{\log_2(i+1)} $

   可以看到：

   • 预估 top k的 item 的真实评分越高，则 $ \text{DCG}@k $ 越大。
   • 在这 top k 的 item 中，真实评分越高的 item 越靠前，则 $ \text{DCG}@k $ 越大。

   考虑到不同用户的真实评分数量不同，为了方便在不同用户之间进行比较，我们对 DCG@k 进行归一化，得到 NDCG@k 指标：

   $ \text{NDCG}(\mathbf{\vec r}_i,\pi)@k = \frac{\text{DCG}(\mathbf{\vec r}_i,\pi)@k}{\text{DCG}(\mathbf{\vec r}_i,\pi_s)@k} $

   当 NDCG@k = 1.0 时，意味着用户预估的排名和用户真实排名一致。

3. 我们有三种实验配置：

   • 弱泛化 weak generalization：我们从每个用户看过的电影中随机挑选 10/20/50 部电影作为训练集，剩余的 user-item 评分作为测试集，并在测试集上评估模型的 NDCG@10 指标。

   • 强泛化 strong generalization：我们首先丢弃评分数量低于 50 的电影，然后筛选评分数量最高的 100 个用户作为测试集，剩余用户的 user-item 评分作为训练集。

     在测试的时候，我们从这 100 个测试用户中每个用户随机挑选 10/20/50 部电影来更新模型，更新过程中已训练好的 $ \mathbf V $ 固定不动，仅更新 $ \mathbf U $ 。测试这 100 个用户的剩余 user-item 评分作为最后的测试集。

     该配置用于评估模型在训练时不存在的用户上的表现。

   • 反向弱泛化inverted weak generalization：注意到弱泛化、强泛化中，测试用户的训练item 数量是固定的，因此它们无法展示用户bias 的有效性。为了评估用户 bias 的影响，我们交换了弱泛化配置中的训练集和测试集：从每个用户看过的电影中随机挑选 10/20/50 部电影作为测试集，剩余的 user-item 评分作为训练集 。

   所有实验中的参数配置：

   • 正则化参数都是固定的，没有经过调优。
   • $ \mathbf U $ 和 $ \mathbf V $ 维度 $ f $ 固定为 10 。 我们考察了 $ f=30,100 $ 的情况，发现 $ f=10 $ 并未产生明显的性能下降。
   • 采用最小平方误差损失函数。
   • 每组实验均随机进行十轮，并报告评估结果的均值和方差。

4. 弱泛化的实验结果如下，结论：

   • 添加偏移项确实能够提升性能。
   • 单独使用 Graph Kernel 似乎并未提升性能，可能的原因是并未调整 Graph Kernel 的超参数。

   

5. 反向弱泛化的实验结果如下，结论：

   • 添加偏移项确实能够提升性能。
   • 添加偏移项和Graph Kernel 或者自适应正则化配合使用，可以进一步提高性能。

   

6. 强泛化的实验结果如下。我们将结果与Gaussian Process Ordinal Regression:GPOR、Gaussian Process Regression:GPR、 CPR 扩展、CGPOR 扩展以及原始的 MMMF 方法来对比。

   结论：

   • 对于 Movielens 数据集，添加偏移项和Graph Kernel 的表现最佳。

   • 对于 EachMovie 数据集，仅添加偏移项的表现最佳。继续添加 Graph Kernel 反而效果下降，我们认为这是超参数未调优的原因。

   • 在强泛化配置中，我们的方法在这两个数据集上效果都非常好。这是因为：在强泛化阶段，我们的系统为每个新用户解决了一个凸优化问题，从而学习正确的representation $ \mathbf{\vec u}_i $ 。如果系统在弱泛化阶段为 item 学到了合理的特征，那么强评估阶段的良好结果是可以预期的。

     这是我们方法的重要优势：无需重新训练整个模型，就可以为新用户提供快速、准确的模型预估。

   

7. 每种配置随机运行十次时，评估指标方差都非常低，特别是考虑到我们的目标函数是非凸函数。事实上目标函数的方差也非常低。低方差意味着我们总是到达相同的局部最小值，或者该最小值就是全局最小值。

8. 在所有配置中我们并未优化超参数（如正则化系数），如果模型调优则性能可以进一步提升。另外，当我们采用其它损失函数（如保序回归损失或者 ranking 损失），模型性能也能得到提升。但是我们并未在这里评估它们，因为每个损失函数都需要增加 960 个实验。