Question

1. 个性化服务在 web 上变得越来越不可或缺，从提供搜索结果到商品推荐。这类系统的例子包括 Amazon.com 上的商品推荐、Netflix 上的 DVD 推荐、Google 上的新闻推荐等等。这些系统中使用的核心技术是协同过滤 collaborative filtering: CF，它旨在根据所有用户历史评分的 item 预测特定用户的 item 偏好。在许多的这类系统中，用户可以显式给出以不同分数（例如 Netflix 中的 1 ~ 5 分）表示的评分。但是，更多的情况下，也可以通过用户点击或不点击、bookmark 或者 not-bookmark 等用户行为来隐式地表达。这些形式的隐式评分更常见，也更容易获得。

   虽然隐式评分的优势很明显，但是它的缺点（尤其是在数据稀疏的情况下）是很难识别有代表性的负样本。所有的负样本和缺失的正样本混合在一起，无法区分。我们将仅具有正样本的协同过滤称作 One-Class Collaborative Filtering: OCCF。OCCF 发生在不同的场景中，下面给出两个示例：

   • Social Bookmark：Social Bookmark 在 del.icio.us 等 Web 2.0 服务中非常流行。在这样的系统中，每个用户都为一组网页添加书签，这些网页可以被视为用户兴趣的正样本。但是，用户没有为网页添加书签的行为存在两种可能的解释：

     • 第一种解释：该网页是用户感兴趣的，但是用户未能看到这个网页。
     • 第二种解释：用户看到过这个网页，但是用户不感兴趣。

     我们不能假设所有不在用户书签中的网页都是负样本。

   • Clickthrough History：点击数据被广泛应用于个性化搜索和搜索结果改进。通常三元组 $ $ 表示用户 $ u $ 提交了 query $ q $ 并点击了网页 $ p $ 。通常而言，未被点击的网页不被收集。与书签示例类似，我们无法判断网页未被点击是因为内容与 query 无关、还是因为用户未看到。

   有几种直观的策略可以解决这个问题。

   • 一种方法是标记负样本，从而将数据转换为经典的 CF 问题。但是，这需要用户的密切配合来标记数据，代价太大甚至难以进行，因为用户通常不愿意承担这种成本。

     实际项目中，用户很少能够提供算法所需要的标记数据。而且根据一些用户研究表明：如果要求用户在使用系统之前提供很多正面或负面的反馈，那么用户对该系统就有很不好的印象，甚至可能会拒绝使用该系统。

   • 另一种策略是将所有缺失数据视为负样本，称作 All Missing As Negative:AMAN 。经验表明，这种策略的效果很好。但是，由于某些缺失数据可能是正样本，因此推荐的结果是有偏的。

     还有一种策略是将所有缺失值视为未知的，即忽略所有缺失的样本而仅使用正样本，称作 All Missing As Unkown:AMAU 。在使用过程中，我们将这些非缺失值灌入针对非缺失值建模的协同过滤算法。但是该方法存在一个平凡解trivial solution：将所有缺失值预估为正样本。因此，所有缺失值为负 AMAN 和所有缺失值未知 AMAU 是 OCCF 中的两种极端策略。

   论文 《One-Class Collaborative Filtering》 提出了两种方案来解决 OCCF 问题。这两种方案考虑了将缺失值视为负样本的程度，导致了整体上性能得到提升：

   • 第一种方案是基于加权的低秩近似，基本思想是为目标函数中的正样本误差和负样本误差赋予不同的权重。
   • 第二种方案是基于负样本的采样，基本思想是利用某些采样策略对一些缺失值进行采样从而得到负样本。

   它们都充分利用了缺失值中包含的信息，并纠正了将其视为负样本的 bias 。第一种方案可以得到理论上的最优解，第二种方案拥有更好的scalability （计算成本低得多）从而扩展到大型稀疏数据集。

   论文主要贡献：

   • 首先，论文为 OCCF 问题提出了两种可能的框架，并提供了它们的实现。

   • 其次，论文使用几个真实世界的数据集实验研究了各种加权、采样方法。论文提出的解决方案在 OCCF 问题中明显优于两个极端策略（AMAN 和 AMAU）。在实验中，论文的方法相比最佳 baseline 至少提高了 8%。

     此外，实验表明：这两个针对 OCCF 提出的解决方案（基于加权、基于负采样）具有几乎相同的性能。

2. 相关工作：

   • 协同过滤：过去，很多学者从不同方面探索了协同过滤collaborative filtering: CF，从提高算法性能到从异质数据源中整合更多资源。然而，这些关于协同过滤的研究仍然假设我们有正样本（高评分）和负样本（低评分）。

     在非二元评分的情况下，每个 item 被赋予一个评分。大多数先前的工作都集中在这个问题 setting 上。在所有的 CF 问题中，有很多样本的评分缺失。在 《Spectral analysis of data》 和 《Collaborative filtering and the missing at random assumption》 中，作者讨论了在协同过滤问题中对缺失值分布进行建模的问题。但是，他们都无法处理没有负样本的情况。

     在二元评分的情况下，每个样本要么是正样本、要么是负样本。

     • 《Google news personalization: scalable online collaborative filtering》 研究了新闻推荐，点击新闻为正样本、未点击新闻为负样本。作者在这个大规模二元 CF 问题上比较了一些实用的方法。
     • KDD Cup 2007 举办了 Who rated What 推荐任务，其训练数据与 Netflix prize 数据集（带评分）相同。获胜团队（《Who rated what: a combination of SVD, correlation and frequent sequence mining》）提出了一种使用二元训练数据集合 SVD 和流行度的混合方法。

   • One-class Classification: OCC：已经针对二分类问题提出了仅从正样本中学习的算法。

     • 《Estimating the support of a high-dimensional distribution》 提出了 one-class SVM解决了只有正样本可用的问题，即单类分类问题。而 《Learning with positive and unlabeled examples using weighted logistic regression》 不仅使用正样本，也使用未标记的样本。

       对于one-class SVM ，该模型描述了单类single class ，并且仅从正样本中学习。这种方法类似于密度估计。当未标记的数据可用时，解决单类分类问题的一种策略是使用类似于 EM 算法来迭代预测负样本，并学习分类器。

     • 在 《learning from positive statistical queries》 中，作者表明，如果每个正样本以恒定概率 unlabeled，那么在统计 query 模型下可学习的函数族也可以从正样本和未标记样本中学习。

     我们的研究和这些关于单类数据中学习的研究之间的不同之处在于：他们的目的是学习关于正样本的单个概念 one single concept ，而我们探索和学习社交网络中的许多概念。

   • 类别不平衡问题 Class Imbalance Problem ：我们的工作还和类别不平衡问题有关，该问题通常发生在某些类别的样本远多于其它类别的分类任务中。one-class 问题可以视为类别不平衡的一种极端情况。有两种策略来解决类别不平衡问题。

     • 一种是在数据层面，其思想是使用采样来重新平衡数据。
     • 另一种是在算法层面，使用 cost-sensitive 算法（即，对稀疏类别的样本对应的损失提高权重）。

     两种策略的比较可以在 《Extreme re-balancing for svms: a case study》 中找到。

11.1 模型

1. 假设有 $ m $ 个用户和 $ n $ 个 item， $ \mathbf R $ 表示user-item 评分矩阵。假设用户 $ i $ 对 item $ j $ 的评分为 $ r_{i,j} $ ，当 $ r_{i,j} = 1 $ 时表示正样本，当 $ r_{i,j} = ? $ 时表示缺失值。我们的任务是从 $ \mathbf R $ 的缺失数据中找到潜在的正样本，我们称该任务为单类协同过滤 One-Class Collaborative Filtering:OCCF 。

   注意：这里除了评分矩阵 $ \mathbf R $ 之外，没有任何关于用户和item 的其它信息。

11.1.1 wALS

1. 给定一个评分矩阵 $ \mathbf R \in \{0,1\}^{m\times n} $ 以及对应的非负权重矩阵 $ \mathbf W \in \mathbb R_{+}^{m\times n} $ ，加权低秩近似 weighted low-rank approximation 的目标是：使用一个低秩矩阵 $ \mathbf X\in \mathbb R^{m\times n} $ 来近似 $ \mathbf R $ ，使得加权误差最小：

   $ \mathcal L(\mathbf X) = \sum_{i,j} W_{i,j}(r_{i,j} - x_{i,j})^2 $

   其中： $ (\cdot)^2 $ 为平方损失； $ w_{i,j} $ 为权重：

   • 对于正样本 $ r_{i,j} = 1 $ ，由于它是显式给定的，因此置信度为 100%，因此我们设置 $ w_{i,j} = 1 $ 。
   • 对于缺失值，我们认为其中大多数都是负样本，因此设置缺失值的 $ r_{i,j} = 0 $ 。但是缺失值为负样本的置信度并不是 100%，因此我们设置 $ 0\le w_{i,j}\le 1 $ 。

2. 考虑用户的 $ i $ 的 representation 向量为 $ \mathbf{\vec u}_i\in \mathbb R^d $ ，item $ j $ 的 representation 向量为 $ \mathbf{\vec v}_j $ ，则用户 $ i $ 在 item $ j $ 上的预估评分为：

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

   令：

   $ \mathbf U = \begin{bmatrix} \mathbf{\vec u}_1^\top\\ \mathbf{\vec u}_2^\top\\ \vdots\\ \mathbf{\vec u}_m^\top \end{bmatrix}\in \mathbb R^{m\times d},\quad \mathbf V = \begin{bmatrix} \mathbf{\vec v}_1^\top\\ \mathbf{\vec v}_2^\top\\ \vdots\\ \mathbf{\vec v}_n^\top \end{bmatrix}\in \mathbb R^{n\times d} $

   则预估的评分矩阵为： $ \hat{\mathbf R} = \mathbf U \mathbf V^\top $ 。其中 $ d\ll m, d\ll n $ ， $ \hat{\mathbf R} $ 的秩为 $ d $ 。

   令 $ \mathbf X = \hat{\mathbf R} $ ，则这个低秩矩阵就是我们需要得到的低秩近似。

   考虑正则化项之后，我们的目标函数为：

   $ \mathcal L(\mathbf U,\mathbf V) = \sum_{i,j} w_{i,j}(r_{i,j} - \mathbf{\vec u}_i\cdot \mathbf{\vec v}_j)^2 + \lambda(||\mathbf U||_F^2+ ||\mathbf V||_F^2) $

   其中 $ \lambda $ 为正则化系数。

3. 上述最优化过程可以通过交替最小二乘法 alternating least squares:ALS 方法来有效求解。

   根据：

   $ \frac{\partial \mathcal L}{\partial u_{i,k}} = 2\sum_j w_{i,j}(\mathbf{\vec u}_i\cdot \mathbf{\vec v}_j-r_{i,j})v_{j,k} + 2\lambda\sum_j w_{i,j} u_{i,k}\\ \frac{\partial \mathcal L}{\partial v_{j,k}} = 2\sum_i w_{i,j}(\mathbf{\vec u}_i\cdot \mathbf{\vec v}_j-r_{i,j})u_{i,k} + 2\lambda\sum_i w_{i,j} v_{j,k} $

   则有：

   $ \nabla_{\mathbf{\vec u}_i} \mathcal L = \left(\frac{\partial \mathcal L}{\partial u_{i,1}},\cdots,\frac{\partial \mathcal L}{\partial u_{i,d}}\right)^T,\quad \nabla_{\mathbf{\vec v}_j} \mathcal L = \left(\frac{\partial \mathcal L}{\partial v_{j,1}},\cdots,\frac{\partial \mathcal L}{\partial v_{j,d}}\right)^T $

   ALS 方法首先固定 $ \mathbf V $ ，根据 $ \nabla_{\mathbf{\vec u}_i} \mathcal L = \mathbf{\vec 0} $ 我们可以得到 $ \mathbf{\vec u}_i $ 的解析解；然后固定 $ \mathbf U $ ，根据 $ \nabla_{\mathbf{\vec v}_j} \mathcal L = \mathbf{\vec 0} $ 我们可以得到 $ \mathbf{\vec v}_j $ 的解析解。

   我们重复交替优化 $ \mathbf U $ 和 $ \mathbf V $ 直至算法收敛，这种方法称之为加权交替最小二乘法 Weighted Alternating Least Squares:wALS 。

4. 权重矩阵 $ \mathbf W $ 对 wALS 方法的效果至关重要。我们的基本思想是：令 $ w_{i,j} $ 包含置信度信息。如：当 $ r_{i,j} = 1 $ 时令 $ w_{i,j} = 1 $ ，表示置信度很高。但是对于缺失值，它为负样本的置信度并没有 100%，因此我们需要将负样本的权重降低。

   负样本权重有三种配置：

   • Uniform 配置：假设所有用户或所有 item 上的缺失值为负样本的概率都是等可能的。即：

     $ w_{i,j} = \begin{cases} 1&,r_{i,j} = 1\\ \delta&,r_{i,j} = 0 \end{cases} $

     其中 $ \delta\in [0,1] $ 。

   • User-Oriented 配置：如果用户有更多正样本，则假设用户的缺失值为负样本的概率更高。即如果一个用户对大多数item 都给与好评，则用户对缺失的 item 没有产生行为的原因是不感兴趣的可能性越大。

     即：

     $ w_{i,j} = \begin{cases} 1&,r_{i,j} = 1\\ \propto \sum_{j^\prime} r_{i,j^\prime}&,r_{i,j} = 0 \end{cases} $

   • Item-Oriented 配置：如果item 被大多数用户喜欢，则该item 的缺失值为负样本的概率越小。即如果一个 item 是热门的，则用户对它感兴趣的概率越高。

     即：

     $ w_{i,j} = \begin{cases} 1&,r_{i,j} = 1\\ \propto m- \sum_{i^\prime} r_{i^\prime,j}&,r_{i,j} = 0 \end{cases} $

5. 当 $ \mathbf W = \mathbf I $ 时， wALS 方法等价于 AMAN （所有缺失值都是负样本）。

11.1.2 sALS-ENS

1. wALS 方法有两个缺点：

   • 当矩阵 $ \mathbf R $ 太大时，计算代价太大。
   • 负样本数量占绝大多数，因此存在类别不平衡。

   为解决这两个问题，我们提出了基于随机采样的方法。

   • 第一步，从缺失值中根据假设的概率分布随机采样一组负样本，然后我们根据所有的正样本、采样的负样本得到一个新的评分矩阵 $ \tilde{\mathbf R}^{(k)} $ 。
   • 第二步，根据 wALS 算法低秩重构评分矩阵 $ \tilde{\mathbf R}^{(k)} $ ，其中近似矩阵为 $ \hat{\mathbf R}^{(k)} $ 。
   • 最后，对所有的近似矩阵 $ \hat{\mathbf R}^{(k)},1\le k \le K $ 取均值，得到 $ \mathbf R $ 的低秩近似矩阵 $ \hat{\mathbf R} $ 。其中 $ K $ 为随机采样的总次数。

   该方法我们称为 sampling ALS Ensemble:sALS-ENS 。

   

2. 给定原始评分矩阵 $ \mathbf R $ 、采样概率矩阵 $ \hat{\mathbf P} $ 以及负样本大小 $ q $ ，我们可以使用一种快速的 $ O(q) $ 复杂度的随机采样算法（《Faster methods for random sampling 》）来生成新的评分矩阵 $ \tilde {\mathbf R}^{(k)} $ 。

   我们提出了三种采样概率:

   • 均匀随机采样 Uniform： $ \hat p_{i,j}\propto 1 $ 。即所有缺失值为负样本的概率都是等可能的。
   • User-Oriented 采样： $ \hat p_{i,j}\propto \sum_{j^\prime} r_{i,j^\prime} $ 。即用户对应的正样本越多，则缺失值为负样本的概率越大。
   • Item-Oriented 采样： $ \hat p_{i,j}\propto \frac{1}{\sum_{i^\prime} r_{i^\prime,j}} $ 。即item 越热门，则缺失值为负样本的概率越小。

3. 由于从 $ \mathbf R $ 中采样的矩阵 $ \tilde{\mathbf R} $ 是随机的，因此逼近 $ \tilde{\mathbf R} $ 的矩阵 $ \hat{\mathbf R} $ 是有偏的 biased、不稳定的 unstable 。

   一种经验的解决方案是利用集成学习 ensemble。这里我们使用 bagging 的思路：随机采样多次得到 $ \tilde{\mathbf R}^{(k)} $ ，然后利用低秩矩阵 $ \hat{\mathbf R}^{(k)} $ 来逼近 $ \tilde{\mathbf R}^{(k)} $ 。最后通过对所有 $ \hat{\mathbf R}^{(k)} $ 取平均来得到 $ \mathbf R $ 的低秩近似 $ \hat{\mathbf R} $ 。

   $ \mathbf R $ 是观察矩阵， $ \tilde{\mathbf R} $ 是从观察矩阵中采样得到的矩阵， $ \hat{\mathbf R} $ 是针对 $ \tilde{\mathbf R} $ 的重构矩阵。

11.1.3 算法复杂度

1. 假设 $ \mathbf U\in \mathbb R^{m\times d},\mathbf V\in \mathbb R^{n\times d} $ ：

   • 对于 wALS，每一步更新 $ \mathbf U $ 或 $ \mathbf V $ 的时间复杂度为 $ O(d^2nm) $ ，因此wALS 的时间复杂度为 $ O(d^2n_tmn) $ ，其中 $ n_t $ 为迭代的 step 数。

   • 对于 sLAS-ENS，假设NES 集成的模型有 $ l $ 个，正样本数量为 $ n_r $ ，负样本和正样本比例为 $ \alpha $ ，则总的时间复杂度为：

     $ O(d^2ln_t(n_r(1+\alpha)+(m+n)d)) $

   实际过程中 $ n_t,l,\alpha $ 都是很小的常数，典型的值为： $ n_t $ 从 20 到 30、 $ l\le 20 $ 、 $ \alpha\le 5 $ 。并且有 $ (n+m) d\le n_r(1+\alpha) $ 。

   因此 wALS 的算法复杂度为 $ O(mn) $ ，sALS-ENS 的算法复杂度为 $ O(n_r) $ 。因此 wLAS-ENS 对于大型稀疏数据的scalability 更强。

11.2 实验

1. 数据集：

   • Yahoo 新闻数据集：每条记录都是一个 user-news 的pair 对，其中包含用户 ID 和新闻 ID 。数据集包含 3158 个用户和 1536 条新闻。
   • 社交书签数据集：来自 http://del.icio.us 网站的数据，包含 3000 个用户和 2000 个tag 标签。

2. 实验配置：数据集以 80%-20% 的比例拆分为训练集、测试集，其中训练集包含 80% 的已知正样本，剩余都是缺失值；测试集包含另外20% 的已知正样本，以及剩下的所有缺失值。

   凭直觉我们认为：一个优秀的算法应该具有更高的概率将已知正样本排序在未知样本之前。因此我们使用 MAP 和 half-life utility 来评估测试集的性能。

   对于每种配置我们随机重复执行 20 次，并报告指标的均值和标准差。

   另外，所有模型的超参数都是通过交叉验证来确定。

3. 评估指标：

   • Mean Average Precision:MAP：用于信息检索领域评估一组 query 召回的 doc 的排名情况。

     • 我们首先计算用户的 AP ，其中 AP 是在所有位置上计算到的precision 的均值：

       $ \text{AP}(\text{user}_i) = \frac{\sum_{k=1}^K \text{precision}(k)\times I_k}{n_i} $

       其中：

       • $ n_i $ 为用户 $ i $ 喜欢的 item 数量。
       • $ K $ 为排序好的推荐列表的长度。
       • $ I_k $ 表示推荐列表中第 $ k $ 个item 是否用户喜欢的，如果是喜欢的则为 1 ，否则为 0 。
       • $ \text{precision}(k) $ 表示位置 $ k $ 的精度，即推荐列表前 $ k $ 个 item 中，用户 $ i $ 真正喜欢的比例。

     • 然后我们计算所有用户的 AP 均值：

       $ \text{AP} = \frac{1}{m}\sum_{i} \text{AP}(\text{user}_i) $

   • Half-lie Utility:HLU：假设推荐列表中item 的效用 utility 随着位置的增加而指数下降，则定义用户 $ i $ 的推荐列表的效用为：

     $ R_i = \sum_{k=1}^K \frac{I_k}{2^{(k-1)\times (\beta-1)}} $

     这里 $ \beta $ 为参数，实验中设置为 5 。

     测试集所有用户的 HLU 定义为：

     $ R = \frac{\sum_i R_i }{\sum_iR_i ^{\max} } $

     其中 $ R_i^\max $ 表示用户 $ i $ 的推荐列表中，用户所有喜欢的item 都位于推荐列表的头部，因此也是最大的效用。

4. 对比模型：

   • AMAN：我们将几种著名的协同过滤算法和 AMAN 策略结合，包括交替最小二乘 ALS-AMAN、奇异值分解 SVD、以及基于邻域的方法（包括UserBased CF 和 ItemBased CF ）。

   • AMAU：在 AMAU 策略下，我们很难使用传统的协同过滤算法得到 non-trivial 解。此时，根据item 的热门程度进行排序，然后推荐热门item 是一种简单且广泛使用的方法。

     另一种方法是将 OCCF 问题转换为 one-class 分类问题。这里我们采用 one-class SVM 来求解该 one-class 分类问题。我们为每个 item 创建一个 one-class SVM 分类器，该分类器将除了该 item 以外的其它 item 评分作为输入特征，然后预测用户对目标 item 是正向还是负向。

5. 我们首先评估维度 $ d $ 的影响。可以看到：

   • 对于 SVD，随着 $ d $ 的增加性能首先提高然后下降。
   • 对于 wALS，性能更为稳定并且逐渐提高，最后收敛于大约 $ d=50 $ 。

   因此在后续的实验中，我们设置维度 $ d $ 为：

   • 对于 wALS，在所有数据集上 $ d=50 $ 。
   • 对于 SVD，在雅虎新闻数据集上 $ d=10 $ ，在社交书签数据集上 $ d=16 $ 。

   

6. 我们比较了 wALS、 sASL-ENS 这两种方法，对于每一种方法我们提出了三种策略：uniform 均匀的、user-oriented 面向用户的、item-oriented 面向item 的。下表给出了这些方案的结果。

   在wALS 方法中，user-oriented 效果最好、item-oriented 效果最差。这可能是由于用户数量和 item 数量之间不平衡导致。对于当前数据集，用户数量 $ m $ 远大于 item 数量 $ n $ 。

   

7. 我们比较了 AMAU （基于热门程度的推荐、单类SVM）、AMAN （SVD、ALS-AMAN ）以及我们的方法（wALS、sALS-ENS）的效果。

   其中 x 轴为负样本数量和正样本数量的加权比例：

   $ \alpha = \frac{\sum_{(i,j)\in r_{i,j}=0}w_{i,j}}{\sum_{(i,j)\in r_{i,j}=1}w_{i,j}} $

   $ \alpha $ 控制着负样本的规模。当 $ \alpha \rightarrow 0 $ 时，我们的方法接近 AMAU；当 $ \alpha \rightarrow \infty $ 时我们的方法接近 AMAN 。

   为了方便比较，给定 $ \alpha $ 的条件下负采样参数设定为 $ q= \alpha \times n_r $ 。由于热门程度策略、SVD、ALS-AMAN 等方法的效果不会随着 $ \alpha $ 改变，因此它们在图中以水平线展示。

   可以看出：我们的方法要优于 AMAU 和 AMAN 。

   

8. 不同方法在雅虎训练集上的训练时间（单位秒）如下所示。可以看到，当 $ \alpha $ 较小时，sALS 的方法训练效率更高。

   

9. 从实验结果可以看到：和 AMAU 策略相比，AMAN 的效果更好。这是因为：尽管缺失值的标记是未知的，但是我们仍然具有先验知识，即大部分缺失样本都是负样本。

   这和类别不平衡问题中的结论有所不同。在类别不平衡问题中，假设负样本占据主导地位，那么丢夫部分负样本往往会产生更好的效果。但是在 OCCF 问题中，丢弃 “负样本” 反而效果下降。