两个有意思的东西

一个是 spike and slab prior,一个是 exploration and exploitation(也称 E&E)。

spike and slab prior

这其实是 Bayesian 领域里面的某种奇怪的先验,比如我们常见的 case,Poisson-Gamma 这个 Bayesian model,选用 Poisson distribution 计数,而 Gamma distribution 作为 conjugate prior 是因为后验分布便于计算。很多情况下我们会发现某种情况下(如无观测)我们希望回退到一个 prior 上,这时可以引入一个隐变量,让它决定 prior 是否退化成为一个 delta 分布,这个 delta 函数对应的就是 spike 而原先的 Gamma 就是 slab,这样我们记算后验的时候就会需要判断这个隐变量在哪边对应的是 mode,这就得到一个条件用来选择退化先验还是通过 conjugate prior 获得的先验。非常有趣的一个应用。

Poisson-Gamma 模型使用 Spike and Slab 先验

另外还可以用它来做特征选择,最早的 paper 里面是在 linear regression 这个场景应用这个 idea 到 Gaussian prior 上,退化情况就是在 0 处的一个 delta 函数,选择这个表示该 feature 不会使用。另外似乎 Bengio Yoshua 他们还把这个应用到 RBM 里面去和 Hinton 他们搞的 mcRBM 进行了一些比较。这部分一直不是太明白为啥要搞这么复杂…

E&E

E&E 在 wiki 上关联到的居然是一种商业组织形式(ambidextrous organization),其实对应的数学模型是一个所谓 multi-armed bandit process:大概就是有几台老虎机,每台拉一下某杆就会给你一个 reward(可能是 0 或者负的),每个老虎机的 reward 分布都不一样,而且你是不知道啥分布的。那么为了最大化你的收益,你就得去尝试(explore)每台机器,同时利用(exploit)你猜测觉得能让你收益较高的机器多赚一点。

最直观的策略就是设定一个两种策略的比例,这一般称为 \varepsilon greedy,即以 \varepsilon 的概率(一般比较小)来探索这些机器(随机抽一个看看能的多少 reward),其他的时候都用历史上平均收益最高的机器进行反复尝试。

这个问题出现的地方非常多(比如前面说公司需要把精力集中在自己所长能赚钱的方面,同时也需要探索一些新的领域获得新的收入来源,这个例子比如 google 通过 sponsored search 获利,现在也在 mobile、social network 方面大胆尝试),不少 internet 的应用都是这样一个问题:比如 Yahoo! 伺服的新闻文章,每篇文章的点击率是不同的,但是不展示给用户我们永远不知道其点击率能有多少,为了优化整个网页的点击率,我们一方面需要将这些新闻随机选择给用户看,也需要将我们现在所知道最 popular 的新闻排出来。

当然很多实际的问题和 multi-armed bandit process 的假定可能并不一样,假定最过分的可能是 Auer、Cesa-Bianchi、Fruend 和 Schapire 的那篇文章,基本上就是假定分布未知,甚至总是要跟你对着来的情况下怎么做比较好的策略。实际问题里面一般 arm 数目是会变化的,同时每个 arm 的均值方差可能也是在变化的。另外受到一些 business rule 的影响,实际操作中也可能不能完全做到某些“随机的要求”。

这方面的理论分析非常多,比较简化的一般是假定每个 reward 来源都是某个分布族下面的分布,这个时候一种有效的策略是所谓的 upper confidence bound,也就是通过估计出来的均值附近的一个上界作为选择某个 arm 的准则,这样做非常合理是因为,一方面,如果我们的观测足够多,置信区间就会缩小,这意味着上界偏离均值的程度变小;而如果观测较少,这个区间大,上界偏离均值就大,这样对于观测不够的即便对均值估计较小的 arm 仍然有机会被选择进一步进行探索。

更有意思的是如果我们有一个 model 来判定这个收益,且是一个线性模型的话,这时我们用 Bayesian 方法,将参数的后验均值和方差获得后就能用在 E&E 中间这个 UCB 里面了。最常用的当然是对点击率预测的 Bayesian logistic regression,这意味着我们可以将预测的概率变换成为 \log \frac{p}{1 - p} 的形式,这时就成为一个线性模型,而这个线性模型的 mean 和 variance 我们都是知道的,那么使用 mean + const. x std 这种形式的 UCB 就能做 E&E 了。

UCB 类型方法的好处就是不需要设置一个 random bucket,这样就不会总存在一些用户抱怨自己的用户体验很差了。

E&E 另外一种做法是基于 Gittins index 的,这部分工作比较早,一直也没看大懂。

——————
For I know him, that he will command his children and his household after him, and they shall keep the way of the LORD, to do justice and judgment; that the LORD may bring on Abraham that which he has spoken of him.

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