推荐系统(五)

这里我们集中讨论一下 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_iQ_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_iv_j,实际上这相当于把上面两式联立起来,在一次 iteration 里面来做。

实现 ALS 的 map/reduce 策略比较容易,我们给一个比较傻的版本,每条 record 包含五项,user,item,R_{i, j}u_iv_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_iv_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.

Advertisements
推荐系统(五)

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s