Computational Advertising 读书笔记(九)

这一讲主要讨论的是推荐系统,当然就 recommendation 这一个问题来说就足够搞一本厚厚的专著(此后我们将仔细看看 Recommender System Handbook)了,一堂课显然只是覆盖了一些 general 的东西。大部分内容也来自 Yehuda Koren 原来的讲稿。

targeting 是区分 impression,extracting value 里面一个重要的步骤,常见的 targeting 的目标是 demography、geo 和 behavior,这样引出的问题是如何获得用户的数据,以及如何利用这些数据进行推断。因此很大程度上 targeting 的输出结果是 user profile,它刻画了 user 的各种 interest,常用的手段是一些 generative model(将 unigram 这类 sparse feature 转换成为 topic 这类更为 dense 的 feature),根据时间进行加权(区分 long term interest 以及 short term interest,甚至 publishing interest 和 reading interest),聚类等等。

对 recommendation system 来说,它输入的是用户对 item 的 rating(有时候也会有 user profile 或者 item profile),这种 rating 可以是 explicit 的,也可以是 implicit 的(如 page view、click 这些行为)。一个重要的技术称为 collaborative filtering(根据历史上许多用户的 transaction 数据),这种技术可以是关注于 user-item(rating),也可以是关注 item-item(co-clicked,co-bought)或者 user-user 的关系,具体的应用不同,能拿到的数据类型/关系是不一样的,这决定了 recommendation system 的算法和模型。

这个一般的 representation 都是使用有 missing value 的 rating matrix,所谓有 missing value 的意思是说没有观测的 rating 上的区别性不能计入目标函数(或者说区别程度未知)。问题是影响 rating 的因素很多,就算我们考虑某些 feature,也很可能 miss 了不少信息(嗯,一个很重要的问题是那么是否可以用 semi-parametric model 来表述这个事情呢?),同时拿到的数据可能是有严重的 imbalance 的:rating matrix 非常稀疏,对于一个特定用户,给出的 rating 占全部的比例很低,对一个 item 给出 rating 的用户也很少。如果记 r_{u, i} 为用户 u 对第 i 个 item 的 rating,记 \hat{r}_{u, i} 为预测值,我们可以很容易利用 MSE 类似的准则进行评估(仅仅在有 value 的地方,这是与传统估计不一样的地方)。

对广告系统来说,往往这种类似的矩阵更为稀疏,另外广告系统使用 ranking model 的 evaluation 可能更合适。

neighborhood CF

常用的 CF 的策略有基于 neighborhood:如对 item 的 rating 评估可以使用“相似”的 item,对 user 对 item 的评估使用相似的 user,这一般是将相似 item被同一个 user 的 rating 加权或者相似的 user 对同一个 item 的 rating 进行加权。这种方式直观,对新用户和新 item 能处理。问题是往往某些 item/user 他们的 rating 存在明显的 bias,为了让不同的之间能够相互比较,必须引入 normalization。一般可以认为观测到的 rating 是来自三个部分:global mean,user bias 和 item bias。这类似于一个 rank 1 的 decomposition,

\displaystyle\min_{\mu, b_i, b_u} \sum_{(u, i) \in K} (r_{u, i} - \mu - b_u - b_i)^2 + \lambda \left( \sum_u |b_u|^2 + \sum_i |b_i|^2 \right)

利用这个 model,我们可以计算每个用户对应的残差 b_{u, i},帮助我们计算最终的 rating,

\displaystyle\hat{r}_{u, i} = b_{u, i} + \frac{1}{Z}\left( \sum_{j \in \mathcal{N}(i)}s_{i, j} (r_{u, j} - b_{u, j})\right)

其中的 Z = \sum_{j \in \mathcal{N}(i)} s_{i, j}

这里涉及到计算 item-item 的相似关系,我们可以用 rate 过两者的 user 列表作为比较的 feature vector,一种策略是使用 correlation,这需要取两者公共部分,对于 binary 的 rating 可以用 Jaccard similarity。以上方法也存在对偶的利用 user 进行的策略。这两种策略对不同的问题有不同的应用场合,比如 item 较少时前者容易计算,而如果 item 时效性比较强,则适合使用后者进行计算。

matrix factorization

另一种策略是使用矩阵分解,获得 item 和 user 的低维表示:从矩阵重构的角度来说,我们此时只关心有 rating 的部分产生的 loss,常见使用 MSE 作为 evaluation,这等价于假定了某个 Gaussian distribution 下的类似 MLE 的问题,

\min_{U, V} \sum_{(i, j) \in K} (r_{i, j} - u_i^\top v_j)^2 + \lambda_1 \sum_i \|u_i\|^2 + \lambda_2 \sum_j \| v_j \|^2

这里的正则项可以解释称为 Gaussian 的 prior,这是一个 non-parametric 模型。似乎我们很容易就抛弃了 parametric model(后面也有一些工作,但是似乎又完全转换到 parametric model 下了)。这类问题典型的 optimization technique 是 stochastic optimization,但是似乎很难弄成 parallel 的(比较容易的是 alternative least square)。同时,这个 model 也可以引入对应的 bias,考虑 rating 本身的分布(见这里),引入 probabilistic graphical model,考虑 rating missing 的原因等等。这个我们也将在稍后的系列文章里面仔细讨论。

时序对推荐结果的影响

当时 Yehuda 访问我们的时候讲过一个很有意思的发现,就是某些推荐数据(如电影)上随着时间的推移,平均 rating 会慢慢增高。产生这个事情的原因很可能是电影这种商品,越到后来来看的人,越可能是“慕名而来”,因此给的评价反而相对上映当时要高不少。

这告诉我们不论是 item 还是 user 可能随着时间的推移都会有一些变化,为此,我们可能需要对以上某些 factor 加入对应的时间,作为时间的函数,而不再是一个静态的东西。

推荐与搜索

有的求解推荐的策略是利用 content similarity,这就把推荐转换成为了 retrieval 的问题。更有将 item 的推荐当做用对应 rating vector 的 retrieval 的做法。感觉上这些方法仍然是比较 heuristic 的 idea。我现在的一种 idea 是将这些 known feature 作为 parametric model,而将某些未知因素作为 non-parametric model 来处理。不知道这样是否能拥有可解释性,同时能提高精度呢?

——————
In the same day the LORD made a covenant with Abram, saying, To your seed have I given this land, from the river of Egypt to the great river, the river Euphrates:

Advertisements
Computational Advertising 读书笔记(九)

一个有关“Computational Advertising 读书笔记(九)”的想法

发表评论

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