CIKM 2018论文精读（一）

2018年 12月 1号

今天我们要来分享一篇题目叫Collaborative Multi-objective Ranking的发表在CIKM 2018上的论文。这篇论文的作者是来自于罗格斯大学（Rutgers University）的Jun Hu和Ping Li。文章的核心内容讲的是，传统的以矩阵分解为基础的“协同排序”（Collaborative Ranking）容易有无法有效学习“用户隐向量”（User Factor）和“物品隐向量”（Item Factor）的问题。这篇论文探究了这种问题的来源以及提出了一种“共同优化”（Joint Optimization）的策略来解决问题。

文章的基本设置

我们先来看一下文章的基本设置。首先，我们假设有一个评分矩阵$ \mathbf{R} \in \mathbb{R}^{M \times N} $，被一个用户矩阵$ \mathbf{U} \in \mathbb{R}^{M \times K} $和一个物品矩阵$ \mathbf{V} \in \mathbb{R}^{N \times K} $所表达$ \mathbf{R} = \mathbf{U} \times \mathbf{V} $。一个“单点”（Pointwise）目标函数常用来学习模型的参数：

\[L_{\mathrm{pointwise}} = \sum_{u=1}^{M} \sum_{v=1}^{N} (r_{ui} - \hat{r_{ui}})^{2} + \sum_{u=1}^{M}\lambda_{U,u}|| \mathbf{U}_{u} ||^{2} + \sum_{v=1}^{N}\lambda_{V,v}|| \mathbf{V}_{v} ||^{2}\]

这个目标函数的目的是希望能够学习到准确的用户隐向量和物品隐向量来逼近原有的评分矩阵。然而在真实的应用中，很多时候我们并不是在意\(\mathbf{U}\)和\(\mathbf{V}\)的绝对数值的准确性，而是它们之间的相对位置，也就是说“排序”。所以，这也就有了“协同排序”的出现。具体说来，“协同排序”就是希望利用“配对法”（Pairwise）的“排序学习”（Learning to Rank）确保物品的相对顺序得以保证。一个常见的针对顺序的损失目标函数是：

\[\varepsilon_{\mathrm{zero-one}} = - \sum_{(u, i_{1}, i_{2}) \in \Omega} \sigma \Bigr( \mathbf{U}_{u} \mathbf{V}_{v_{1}}^{T} - \mathbf{U}_{u} \mathbf{V}_{v_{2}}^{T}\Bigl)\]

其中\(\Omega = \{ (u, i_{1}, i_{2}) : r_{ui_{1}} > r_{ui_{2}} \}\)是一个比较集合，\(\sigma(x)\)是一个$0-1$ 损失函数：当$x > 1$的时候\(\sigma(x) =1\)，其他时候为$0$。这个损失函数无法微分，因此一个替代的方案则是利用Sigmoid函数：

\[\varepsilon_{\mathrm{zero-one-approximate}} = - \sum_{(u, i_{1}, i_{2}) \in \Omega} \frac{1}{1+\exp\Bigr( -\mathbf{U}_{u} (\mathbf{V}_{v_{1}} - \mathbf{V}_{v_{2}})^{T}\Bigl)}\]

我们有了上面的这个损失函数以后，在进行优化的过程中，往往会“保持住”（Fix）所有某个用户$u$所对应的\(\mathbf{V}\)，然后更新\(\mathbf{U}_{u}\)。

文章的核心观点

文章的作者们发现，在某些情况下在更新用户矩阵\(\mathbf{U}_{u}\)的时候，算法不可能保持住所有用户所对应物品的顺序的。举例来说，我们有两组物品的比较顺序\(\{ (u, a, b) : r_{ua} > r_{ub} \} \in \Omega\)和\(\{ (u, c, d) : r_{uc} > r_{ud} \} \in \Omega\)。并且当前情况下，我们有这样的关系：\(\mathbf{V}_{a} - \mathbf{V}_{b} =[0,-1]\)和\(\mathbf{V}_{c} - \mathbf{V}_{d} =[0,1]\)。这也就意味着无论如何更新\(\mathbf{U}_{u}\)，我们都无法同时满足\(\mathbf{U}_{u}(\mathbf{V}_{a} - \mathbf{V}_{b})>0\)和\(\mathbf{U}_{u}(\mathbf{V}_{c} - \mathbf{V}_{d})>0\)，因为这两组乘积必定是一正一负，无法调和。也就是说，在更新了\(\mathbf{U}_{u}\)之后，我们反而无法保证原有的顺序了。

第二个作者们的发现来自于对于Sigmoid函数\(\sigma(x) = \frac{1}{1+ \exp(-ax)}\)的认识。在这个函数中，\(a\)控制了曲线多么接近\(0-1\)损失函数：值越大，越接近。然而，在矩阵分解中，任何对于\(\mathbf{U}_{u}\)的更新（例如把其值增大两倍），都可以利用更改其对应的所有\(\mathbf{V}_{i}\)来达到恢复其之前的状态（例如把其值除以一半）。这样，更新\(\mathbf{U}_{u}\)并不一定逼近\(0-1\)损失函数。换句话说，我们必须要对\(\mathbf{V}\)进行限制，不能无限制得任其发展。

文章提出的模型

有了上面的铺垫，作者们提出了一种新的损失函数，那就是把单点损失函数，基于物品的配对损失函数以及基于用户的配对损失函数结合起来，形成一个三个损失函数的某种平衡。

我们已经定义了单点损失函数，那这里就来看看一下基于物品的配对损失函数。作者们使用了一个叫Bradley-Terry模型来针对某个用户的两个物品进行比较的概率进行建模：

\[P(r_{ui_{1}} > r_{ui_{2}}) = \frac{\exp(\mathbf{U}_{u}\mathbf{V}_{i_{1}}^{T})}{\exp(\mathbf{U}_{u}\mathbf{V}_{i_{1}}^{T}) + \exp(\mathbf{U}_{u}\mathbf{V}_{i_{2}}^{T})}\]

在有了这个概率之后，我们最小化其“负对数似然”（Negative Log Likelihood）:

\[L_{\mathrm{row-wise}} = - \sum_{(u, i_{1}, i_{2}) \in \Omega} \log P(r_{ui_{1}} > r_{ui_{2}}) + \sum_{v} \lambda_{V,v}||\mathbf{V}_{v}||^{2}\]

非常类似的，我们还可以定义基于用户的配对损失函数，得到：

\[L_{\mathrm{column-wise}} = - \sum_{(u_{1} u_{1}, i) \in \Psi} \log P(r_{u_{1}i} > r_{u_{2}i}) + \sum_{u} \lambda_{U,u}||\mathbf{U}_{u}||^{2}\]

于是我们可以定义最终的统一的损失函数为：

\[L = \alpha L_{\mathrm{row-wise}} + \beta L_{\mathrm{column-wise}} + (1-\alpha -\beta) L_{\mathrm{pointwise}}\]

其中，$\alpha \in [0, 1]$和$\beta \in [0, 1]$，并且\(\alpha + \beta <1\)。作者们认为，这个新的损失函数可以解决之前提出的问题。针对这个新的目标函数，文章提出了详细的优化算法，这里就不赘述了。作者们提出的模型在MovieLens、Netflix以及Amazon的数据集上都要优于不使用排序的纯矩阵分解模型以及一般的协同排序算法。