Computational Advertising 笔记(五)

这部分我们讨论一些 click modeling 的东西。

首先想说的是一个最简单的 model,基于 click 和 impression 次数的统计,常规所谓 CTR(click through rate)就是 click 数与 impression 数的比,但是很明显 CTR 单单不能反应数据的有效性,我们可以额外的引入 impression 次数刻画这个 CTR 估计的稳定程度。

CoEC

这个 model 忽视了由于 item 在页面上放置位置的不同造成的差异性:根据研究,搜索页面的用户注意力一般集中在左上,因此每次 impression 能导致的 click 可能性是与位置相关的,因此 impression 并不“可加”。一种 discount 有效 impression 的方式是通过每个位置的平均 CTR,又称 reference CTR 来处理,这样将每次 impression 乘以对应位置的 reference CTR 就获得了所谓的 EC(expected click),这样消除了 position bias 的 EC 就变成可加的了。观测到的 click 数目从统计上来看应该是分布在 EC 附近,也就是说 CoEC(clicks over expected clicks)的期望应该是 1。

看起来使用 CoEC 而不是 CTR 作为每个 item 的 relevance 的反应是一个不错的选择,但是实际操作中与 CTR 类似都面临着 data sparsity 的问题。Laplace smoothing 可以作为一种选择,如 10 个 position 可以在分子上加 1,分母上加 10,这样没有数据的时候正好均匀分布。另一种策略使用的是所谓 Poisson-Gamma distribution 对这个过程进行建模。我们知道 model counts 最常用的统计模型是指数族里面的 Poisson 分布,其参数 \lambda 反应了“速率”,这也就是我们所谓的 CoEC,那么给定了 click 和 EC 之后 CoEC 的 MLE 就是两者的比。一般我们也会使用 Laplace smoothing 解决 0 观测。

如果使用 Bayesian modelling,我们还可以假定每个 CoEC 本身是取自一个 Gamma 分布,这样我们希望能

\displaystyle \max_{\alpha, \beta} \int_0^\infty \prod_{i = 1}^N \text{Poisson}(\text{\# click}_i \mid \lambda \text{EC}_i) \text{Gamma}(\lambda \mid \alpha, \beta) \mathrm{d} \lambda

这用经典的 empirical Bayesian 就能获得超参数了。然后用每个对应的后验 MAP 做 inference,这种做法的好处是可以为 Laplace smoothing 提供更合理的加数,CoEC 也足够简单,实现比较容易。

Cascade Hypothesis

这篇 paper 里面给了四个假设,

  • baseline 是用户将所有的 position 都仔细看过,点击的概率等于 relevance,即 c_{d, i} = c_{d, j}= r_d,这种假设其实是说点击概率与 position 无关;
  • mixture hypothesis 认为,一部分人是 baseline 里面的做法,一部分人是随机点的,分布仅与位置有关,所以观测到的点击概率是 relevance 与某个背景概率的混合,即 c_{d, i} = \lambda r_d + (1 - \lambda) b_i,因此恢复出 r_d 我们只需要获得背景概率 b_i 即可;
  • examine hypothesis 认为要点击必须先 examine,每个位置被 examine 的概率不同,因此观测到的点击是相关与 examination 两件事情同时发生的概率,即 c_{d, i} = x_i r_d
  • cascade hypothesis 认为点击后面的 item 表示前面已经被 examine 过,而点击前面的 item 则后面的 item 是没有 examine 过的,那么第 i 个位置被点击相当于前面 i - 1 个位置都被 skip 了,并且已经被 examine 了,因此这时点击的概率是 c_{d, i} = r_d \prod_{j = 1}^{i - 1} (1 - r_{d_j}),这里是 1 - r_{d_j} 而不是 1 - c_{d_j, j} 的原因是 examination 已经发生了。

paper 里面的比较实验避免了直接对 cascade hypothesis 里面各个参数的显式计算(通过 cross entropy evaluation)。

User Browsing Model

UBM 这篇文章感觉是通过所谓的 attractiveness 这个 document 内在的信息修改了 cascade hypothesis(或者说没有 follow 这个假设,提出的是自己的的方案),最后获得的 model 形式很像,但是解释到 user 的 browsing 上就会显得很不一样,它引入了两种 user:

  • single browsing model,用户决定是否 examine 需要先通过决定是否这个 item 是 attractive 的,这样判定 attractiveness 是根据 item 本身 \alpha_{u, q} = \Pr(a = 1 \mid u, q),其中 u 为 snippet,q 为 query;是否 examine 被位置和距离 click 的距离所决定,\gamma_{r, d} = \Pr(e = 1\mid r, d ),其中 d 是距上次 click 的距离(如果没有 click 则假想有个 0,这样距离大小至少为 1),而 r 是当前位置。
  • multiple browsing model,这其实是以上模型的 mixture,引入多种可能行为的混合,但是似乎实验上并没发现额外的参数能够改善评估准则;

这篇文章使用的是 perplexity 来做衡量,看看在 training set 上获得的参数是否能更好的生成训练集。生成模型最大化

\displaystyle \Pr(\text{obs} \mid \alpha, \gamma) = \prod_{r = 1}^R \prod_{d = 1}^D \prod_{\text{click}} \gamma_{r,d} \alpha_{u, q} \prod_{\text{non-click}} (1 - \gamma_{r, d} \alpha{u, q})

这个似然。看起来似乎也挺简单的 =.= 只是不知道这个不 model relevance,难道仅用 attractiveness 作为 ranking?

Bayesian Browsing Model

这个算是比较近的文章了,据说 Bing 可能也在用类似的 feature。作者认为另外一个 DCM(dependent click model)是 follow 了 cascade hypothesis,但支持多次点击,即如果点击则仍有一定的概率 examine 下一个 document。BBM 搞了一个如下的 model,

Graphical Model for BBM

这里 S_i 是需要被 recover 出来用作 ranking 的随机变量,它是 Bernoulli,参数为 r_i,对应的就是 relevance;E_i 表示 examine 行为,而 C_i 是我们看到的 click 与否的行为。这个 graphical model 想说的是:如果没有 examination 就不会 click,examine 了 click 的概率是 S_i1 的概率,上面所有的 click 都会影响后面 examination 的可能,而这个可能性为 \beta_{r_i, d_i} 和 UBM 中一样。从这点来说,BBM 似乎就是将 examine hypothesis 和 user browsing 两个 idea 弄在一起了,也算是 cascade hypothesis (或者 DCM)的增强。需要注意的是文中将 r_i 的先验设为 uniform 分布,而后验由于独立性求解是相对容易的。

这个 model 做 inference(已知 click 反推 S_i 的概率)直接用 Bayesian theorem,主要利用独立性可以获得,有解析解,但 normalizing factor 需要数值解求出来;而 training 获得 \beta_{r, d} 的过程可以在此之前求解,因为给定先验后,将 S_i 积掉,关于 \beta_{r, d} 的方程解耦,这意味着每项可以单独求解(通过一次 map/reduce)。那么在做 inference 的时候 inference 只需要多做一次即可(只需要 map)。paper 上似乎说用了个更复杂的 map/reduce 一次将两步完成。

评测上似乎也是用的类似 perplexity 的东西,只是不清楚这玩意实际用上去能好多少。感觉微软这个工作还是很不错的,不少地方还可以继续研究一下,有功夫需要推到一些上面的关系。

——————
And I will bless them that bless you, and curse him that curses you: and in you shall all families of the earth be blessed.

Advertisements
Computational Advertising 笔记(五)

一个有关“Computational Advertising 笔记(五)”的想法

发表评论

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

WordPress.com 徽标

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

Google+ photo

You are commenting using your Google+ 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 /  更改 )

Connecting to %s