推荐系统(四)

这里讨论 neighborhood-based RS(可以看成是这篇 blog 的扩展版)与 sequence recommendation。

首先还是谈谈邻域方法的好处:简洁(不需要迭代,参数少),方便 justify(可解释,能对用户 argue 比如说跟你有类似癖好的用户 rating 比较 high,所以推荐给你),efficiency(不需要 training,事实上对 large scale 问题还是需要预处理的,也就是预先将类似 taste 的用户计算好,并且最好能 incremental 的维护这个 structure),稳定性好(在系统中新增加 item/user 都不大会影响整体,一般只需要额外计算一些 item/item 的相似关系即可)。

前面介绍过通过相似用户贡献的 rating 进行加权就能获得当前用户对某个 item 的 rating 的估计,如果是当做“分类问题”来处理的 binary 推荐,我们也可以通过一个(加权的)投票的机制(问题是如果用户尚未 rate 并不表示不喜欢)来进行评判。这个过程可以对偶的应用到利用相似 item 的 user rating 对给定的 item 为某个 user 打分。那么如何选择某一侧的来进行计算呢?一般有 5 个方面可以考虑,

  • accuracy,一般说来影响 accuracy 的是使用“少量很确定相似关系的近邻”而不使用大量但不很确定相似关系的近邻,因此如果用户数目相较更为庞大,而 item 变化并不很大,那么进行 item 侧的相对容易(每个 item 获得的 rate 都会比较多)。
  • efficiency,由于需要计算两两相互关系,那么少的那个更加容易计算;
  • stability,选择变化小的来进行计算两两相似度更加稳定;
  • justifiablity,其实觉得两种都能 justify…
  • serendipity,item 侧做会推荐一些“内容相似”的,而 user 侧做会推荐兴趣类似的人看的,感觉后者更好…

一个很重要的处理是做 normalization,也就是说考虑相似 item/user 的贡献应该考虑的是他们的 rating 偏离于 average 的值的贡献对当前用户 average 分的影响,这才是真正 observe 的 value 的估计。另外也有同时还去除掉方差影响的(即除以标准差,让每个user/item 的 rating 方差一致)。不过感觉每个标准差的估计也是不准确的,可能还需要引入某个先验来保证不被某些极端情形误导。对相似度函数,一般常见的就是 correlation(如利用两者公用 rating 的 correlation coefficient),也可以通过其他的渠道如 content 相似度,其他行为的相似度等等。另外可以用 rank 的相似关系(Spearson rank correlation),weighting 的时候相似度是一个方面,还有一个就是相似度的“确信程度”,同时还需要 address 的问题是某些被“习惯性 high rated”的而又非常 popular 的 item 会导致对与其相似 item 的高估,这可以引入类似 tf-idf 的 feature,这里是 iuf 了。选择邻域最常见的还是 k NN 或者 \varepsilon ball。对 rating 如果就很高的 negative correlation 也应该 filter 掉。

这类方法比较有局限的是这么两个:

  • limited coverage,即两个 user/item share 的 rating 比较少,导致相似度很低
  • sensitivity to sparsity,这也是 cold start 的一部分了

两种可能的解决方案是通过 dimensionality reduction,或者对 rating 矩阵进行分解,或者对相似度矩阵进行分解。常见的分解策略就是基于 alternating least square 或者 stochastic gradient descent。另一种对相似度矩阵进行“incomplete”特征值分解。

另一种观点是将 rating 关系转换成为 weighted bipartite graph,对未知 user/item 的 rating 估计可以利用 graph 的某些特性,比如将 high rate 理解成为低电阻,那么可以将 user/item 之间计算出来的电阻作为 rating 的估计,又或者使用路径条数、最短路径、随机游走、类似 PageRank 的 ItemRank 等。

所谓的 sequential recommendation 首要解决的问题是如何让推荐变得“可持续的盈利”,这意味着在某个时刻我们放弃推荐一个可能带来当时盈利较高的 item,而选择较低的 item,以利于后面可以推荐与之相关的其他商品。那么我们需要哪些信息呢?

  • 每个 item 一开始被购买的概率;
  • 购买每个 item 后产生的利润;
  • 如果 item A 被购买,此时 item B 被购买的概率(co-buy);

这样简单的来看,如果我们考虑长度为 2 的 sequence,我们似乎一开始 maximize 的是 \Pr(A) r(A) + \Pr(B \mid A) r(B)?如果没买一个推荐的我们就得找 \max \Pr(A) r(A) 的了。我们这里按照 An MDP-based Recommender System 一文的思路来。核心的 MDP 模型如下,我们 evaluate 的目标是类似于 Markov 过程的 stationary distribution,

\displaystyle V^\pi (s) = R(s, \pi(s)) + \gamma \sum_{s_j \in S} \Pr(s_j \mid s, a) V^\top (s_j)

我们选择的策略 \pi 就是能最大化以上 V(s) 的 action。求解这个问题常用的一个思路是 policy iteration(感觉是不是证明大概就是幂法),每次用上次计算出来的 V 求解 \pi 迭代至收敛。实际应用该模型时需要统计 transition probability,往往也用稍微更高阶的关系(这里用的是一阶)。推荐系统的 action 是决定推荐什么,而 state 是用户购买的 item 序列。这个模型 online 更新也比较容易。做 evaluation 一般可以与最优序列(已经观测到了)进行比较。

——————
And I will give to you, and to your seed after you, the land wherein you are a stranger, all the land of Canaan, for an everlasting possession; and I will be their God.

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