推荐系统（五）

zt， ， ，

这里我们集中讨论一下 collaborative filtering 中矩阵分解相关的工作。这部分工作的核心就是如何进行矩阵的分解，能够尽可能的逼近原有 rating matrix 中含有 rating 的部分。为了一致性，我们假定 R \in \mathbb{R}^{N \times M} 是一个 rating 矩阵，对应 N 个用户和 M 个 item。我们需要进行如下分解 R \approx U^\top V，其中 U \in \mathbb{R}^{d \times N}, V \in \mathbb{R}^{d\times M}，引入一个评估损失的函数 \ell(R_{i, j}, f(u_i, v_j))，这里我们常见的估计 rating 的方式是 f(u_i, v_i) = u_i^\top v_j。由于存在用户/item 上的 bias，我们一般会将其写成 f(u_i, v_j) = u_i^\top v_j + \alpha_i + \beta_j。

下面就是建立一个合理 loss function，这可以从“噪声模型”来下手，比如常见的就是使用 Gaussian noise，这时的 MLE 等价于（简单起见，先考虑一个没有 bias 的模型）

\min_{u_i, v_i} \displaystyle \sum_{(i, j) \in \mathcal{I}} (R_{i, j} - u_i^\top v_j)^2

所谓的 ALS（alternating least square）就是先固定一边，优化另一边的策略，求导之后容易获得下面的策略：

  • 固 定 V，更新 u_i = (V_iV_i^\top)^{-1} V_i R_i，其中 V_i 是第 i 个用户打过分的 item 对应在 V 里面的子矩阵，类似的定义 R_i，后者是一个列向量。
  • 固定 U，更新 v_j = (U_j U_j^\top)^{-1} U_j R_j，这里是对偶的关系；

为了把这些东西写得更清楚一些，我们使用两个辅助的符号 p_i \in \mathbb{R}^{M, 1} 和 q_j \in \mathbb{R}^{N, 1}，这是两个 0-1 向量，作用是标记出第 i 个用户评分过的 item 和第 j 个 item 被哪些用户评过，对应有 P_i 与 Q_i，这样依据前面的定义，我们有，

  • V_i = V P_i, U_j = U Q_j
  • R_i = e_i^\top R P_i, R_j = e_j^\top R^\top Q_j

这样可以“简化”更新规则，

  • u_i = (V P_i P_i^\top V^\top)^{-1} V P_i P_iR e_i
  • v_i = (U Q_j Q_j^\top U^\top)^{-1} U Q_j Q_j R^\top e_j

很不幸的是似乎每个 user/item 的低维表示可以解耦（即 u_{i_1} 与 u_{i_2} 的计算互相没有关系），但是似乎不能怎么统一计算出来。如果使用 stochastic gradient descent，我们可以每次选择某个 user 或者某个 item 进行 optimization，这时我们仅仅按照梯度方向进行少量移动，

  • u_i += \epsilon \sum_{j \sim i} (R_{i, j} - u_i^\top v_j) v_j
  • v_j += \epsilon \sum_{i \sim j} (R_{i, j} - u_i^\top v_j) u_i

但是这样做是和 ALS 类似的。为了更好的优化，实际我们应该针对“耦合”来做，每次选择一个 rating 进行 optimization，这时我们需要更新的是 u_i 和 v_j，实际上这相当于把上面两式联立起来，在一次 iteration 里面来做。

实现 ALS 的 map/reduce 策略比较容易，我们给一个比较傻的版本，每条 record 包含五项，user，item，R_{i, j}，u_i 与 v_j，每次 iteration 包含两次 map/reduce，每次 map 只是选择 user 或者 item 为 key 发送到 reducer：

  • 如果 user 为 key，reducer 拿到每个 user 对应的 item 列表，这样就能更新各自的 u_i 并将结果写回原先的样子；
  • 如果 item 为 key，reducer 拿到每个 item 对应的 user 列表，这样就能更新各自的 v_j 并将结果写回原先的样子；

如果实现的 SGD 则比较麻烦，但是有一点比较有意思，如果前后两次更新的两个 rating，R_{i, j}, R_{i', j'}，如果 user 没有对对方的 item 进行 rating 也是可以并行的（j\not\sim i', j' \not\sim i）。这意味着，如果我们能从数据里面预先将 user 根据 rate 过 item 进行聚类分块，保证两个块里面的 user 的 item 互相没有重复，这样就能一次多做一些优化（通过并行）。但是这个似乎比较 tricky 啊！

对一个更复杂一些的带有 bias 的 model 来说，我们一般会计算所有 rating 的均值 \bar{r}，优化目标为

\displaystyle\min_{a_i, b_j, u_i, v_j} \sum_{(i, j) \in \mathcal{I}} (R_{i, j} - \bar{r} - a_i - b_j - u_i^\top v_j)^2

这时我们更新的策略会稍有不同（主要是增加的项）

  • a_i += \epsilon \sum_{j \sim i} (R_{i, j} - \bar{r} - a_i - b_j - u_i^\top v_j)
  • b_j += \epsilon \sum_{i \sim j} (R_{i, j} - \bar{r} - a_i - b_j - u_i^\top v_j)

值得注意的是为了避免造成过拟合，往往我们会为 u_i 和 v_j 以及 bias 添加对应的 L^2 的 regularizer。如果引入 link function，\mu (\cdot) 与 loss function \ell(\cdot, \hat{\cdot})，我们可以将以上模型改写成为

\displaystyle\min_{a_i, b_j, u_i, v_j} \sum_{(i, j) \in \mathcal{I}} \ell(R_{i, j}, \mu(\bar{r} - a_i - b_j - u_i^\top v_j))

特别的使用 probabilistic model 的时候往往 link function 与 loss function 有一定的 connection，整个更新的步骤有望进一步化简。最常见的一种方式就是使用 exponential family，比如以上例子我们可以认为选取的模型是 \Pr(R_{i, j} \mid \eta_{i, j}, \sigma^2) 是均值为 \eta_{i, j} 方差为 \sigma^2 的正态分布，这里的 \eta_{i, j} = \bar{r} + a_i + b_j + u_i^\top v_j，这样对应的 MLE 正好是以上的优化目标函数，对应的 link function 为线性函数，loss 为 MSE。类似的，如果 rating 矩阵仅仅含有 rate 和 non-rate，例如对新闻阅读进行推荐的时候只有用户看或者没看这种信息，我们可以使用 logistic regression 类似的方式，假定 \Pr(R_{i, j} \mid \mu_{i, j}) 是均值为 \mu_{i, j} 的 Bernoulli 分布，此时对应的 link function 就是 logistic function 而 loss function 是 cross entropy。这样对于 GLIMs 我们就能给出一个统一的更新形式。

使用这类 probabilistic model 我们就能很容易的换个角度理解 regularization，对以上 frequentist’s model，我们为参数选择 Gaussian 的先验，那么对应的 prior 新增上去对新的模型的 MAP 估计就正好是前面给出的带 L^2 regularizer 的模型了。引入先验以后，我们也可以很自然的考虑使用 Bayesian 的一套方式来选择 hyperparameter（如regularizer 的系数）。甚至使用 Gaussian processes 之类的 non-parametric model。

有了这样一些宏观上的认识之后我们来看看一些文献上的处理方式。

我看到的第一篇这方面的 paper 是所谓的 M3F（最早发在 NIPS 04），直观上来说这个 model 的想法就是避免使用 MSE 而是使用 SVM 的 Hinge loss 来刻画差异性，直观上来说就是小错不算错，错大了就不好（这是对 binary 的情形做的），对应的求解却使用了 SDP（巨慢吧…）。之后的一个改进发表在 ICML 上，我们这里简单的介绍其 idea，假定 R_{i, j} = \pm 1，则我们希望 \hat{R}_{i, j} 与其同号，这样我们只需要 R_{i, j} \hat{R}_{i, j} \geq 1 即可，使用了 Hinge loss 之后我们等价要求 R_{i, j} \hat{R}_{i, j} \geq 1 - \xi_{i, j}，而 slack varaible 就是我们的 loss 了，这样一来我们可以优化

\displaystyle \min_{U, V} \| \hat{R}\|_\text{fro}^2 + \sum_{(i, j) \in \mathcal{I}} \xi_{i, j}

除了通过某种邪恶的方式（SDP）求解以外，我们可以考虑将 Hinge loss 用 smoothed Hinge loss 替代（比如使用前面的 logistic regression 对应的形式，这就是 ICML 那篇文章的主要思路），这样就可以使用 SGD 类似的方式（比如文中采用了 CG）进行求解了。这部分的工作主要是来自 Nathan Srebro 等人，Nathan 似乎是 Hinton 那里出来的。

Hinton 的另一个学生 Ruslan 的一部分工作在于使用 probabilistic model 对 matrix factorization 建模，最早的文章可能是发表在 NIPS 2008 上，除了以上我们讨论过的概率模型以外，他们还讨论了一个所谓的 constrained probabilistic matrix factorization，我们知道出现问题较大的用户主要是 rating 给予的较少，根据我们的 Bayesian 解决方案会回退到接近先验的情形，但是不管什么用户都会回退到一个先验，这很可能是不大正确的，一种可能就是我们把先验换成从 k 个 prototype 选择出来的一种（比如先做用户的 segmentation，根据  rating 简单做一下），当然对 learning 的人来说只需要将这部分也放在 model 里面去 optimize 即可。很自然的接下来在 ICML 08 上的工作就是将一个完全的 Bayesian PMF 搞出来了。当然，这里说的是个 fully Bayesian 哦，很遗憾的是在后验下积分可不是那么好做的，基于 Neals 在这个领域的工作这篇文章直接使用了 MCMC 对后验进行采样（或者就是说使用了 Gibbs sampler 吧），这得益于文章中的 setting 是 conjugate prior（Gaussian 对 Gaussian-Wishart）。

当然 Ruslan 作为 Hinton 的学生更是对 deep belief nets 的组成元件 RBM 深有心得，更早的一份发表在 ICML 07 上工作就是希望通过 RBM 实现类似的工作。RBM 是一个 PoE，也是一个 Markov random field，还是一个 generative model。他们认为 RBM 的 visible layer 就是用户的 rating，而这些 rating 是由 hidden layer 生成出来的，问题是现在的观测（visible）还是 incomplete 的。比如说我们的 rating 是 1-5 离散的，我们就可以在 visible layer 使用 multinomial distribution，而在 hidden layer 使用 Bernoulli，这样对应的 energy function 我们可以写出来，从而能够获得对应的条件概率以及 free energy，此后就是 contrastive divergence 这个套路了。不过这个模型比较奇怪的是具有 k\times M \times d 个参数，其中 d 是低维空间的维数（hidden layer 神经元个数），k 种可选的 rating。似乎只能对给出了部分 rating 的 user 预测其他 item 上的 rating（求那些未观测 neuron 的期望）。

Nathan 和 Ruslan 后来还合作发表了一篇 NIPS 11 的文章，但是似乎是对非均匀采样情况下 Nathan 同志原先模型的一种修正。这里就算了。

下面谈谈工业界的一些 paper。比较有名的可能就是 Yahoo! Research/Labs 的一种试图解决 cold start 问题的方法（见 SIGKDD 09）。我们知道 matrix factorization 是一个 non-parametric model，它的主要问题是 code start，在没有任何 feature 出现的情况下我们无法给 user/item 进行任何推荐。相对的，我们可以使用 logistic regression/ordinal logistic regression 获得一个完全 parametric 的 model，如果我们拥有 user/item 和 user\timesitem 的 feature，这样我们就可以引入一个 parametric model 对 rating 进行建模。这时我们的参数是 user/item 共享的。但是这种 feature 提供的解释终究是有限的，换言之我们还有一些没有能通过这个 capture 的信号，这些我们可以用 matrix factorization 的策略进行解释，这样我们就得到了一个 semi-parametric model。这个所谓 RLFM（regression-based latent factor model）因此通过 feature 解决了 cold start 的问题，同时在具有 rating 观测后又能将 collaborative filtering 的一些性质引入到模型中，但是坏处也是显著的，这个 model 应该非常难以 fitting，作者给出的策略是通过 MCEM 来做。另外有一些策略是希望能将 social 的 signal 引入到推荐中，比如 Yahoo! 的这篇 paper，其实它的核心思想是 user 侧存在一个 social network，从某种程度上能反应 user profile 之间的关系，实际上做得其实是利用类似 Laplacian smoother 增加一个 regularizer 要求朋友之间的 profile 比较相似。另外一点就是该文章要求这些 latent presentation 是 feature 的线性组合产生的。

——————
And I will fetch a morsel of bread, and comfort you your hearts; after that you shall pass on: for therefore are you come to your servant. And they said, So do, as you have said.

推荐系统（五）

留下评论