demonstrate 的 blog

一个是 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）你猜测觉得能让你收益较高的机器多赚一点。

最直观的策略就是设定一个两种策略的比例，这一般称为 greedy，即以 的概率（一般比较小）来探索这些机器（随机抽一个看看能的多少 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，这意味着我们可以将预测的概率变换成为 的形式，这时就成为一个线性模型，而这个线性模型的 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.

Gumbel 分布是一个挺有意思的东西（我很土，没好好学习下 ~~><~~），它的 CDF 如下

求导我们获得其 PDF（记 ），

不难发现，对应的 mode 是 ，对应的中位数是 ，比较难计算的是其 mean，为 ，其中 为欧拉常数。而对应的方差为 。由于 CDF 是可逆的，我们能很容易从均匀分布的随机变量生成 Gumbel 分布的随机变量（取 ，则 为 Gumbel 分布）。下面罗列一些 Gumbel 分布的特性。

线性性 如果 是参数为 的 Gumbel 分布，则 ， 是参数为 的 Gumbel 分布。

Gumbel 分布的差是 Logistic 分布 如果有 分别是参数为 与   Gumbel 分布的独立的随机变量，则两者的差是 Logistic 分布，，其中 Logistic distribution 的 CDF 为 ，其中 是 sigmoid 函数。

Gumbel 分布对 max 的不变性 如果参数为 与   Gumbel 分布的独立的随机变量，则 是 Gumbel 分布，其参数为 。

通常，我们在一些确定性关系后面增加 error 项得到一些统计模型，比如 linear regression 假定了 Gaussian noise；而像分类这类型问题，我们也可以类似的做。比如前面的 random utility 里面假定 ，其中 是我们观测到的 utility，而 是通过 feature 计算出来 systematic utility，我们假定的 error 是 Gumbel 分布时就能获得 multiple logit regression 了（这里有一个具体的例子）：

• 选择 item i 要求 ，
• 这等价于要求 ，
• 利用 Gumbel 分布的性质，几个 Gumbel 分布的 max 仍然是 Gumbel 分布
• 那么最终我们仍然在比较两个 Gumbel 分布，而这个差的分布是 Logistic distribution，这意味着对应的概率可以利用以上性质导出来；
• 这个结果可以与直接使用 multiple logit regression 的模型进行比较，的确是完全一致的。

从某种角度上来说，这种视角告诉我们就算是 additive error 能表达的问题还是挺多的。machine learning 现在不少东西太注重 model 的华丽，似乎不像统计里面更偏重在“解释性”。这也给予我们除了 exponential family 阐述的 logit regression 的另外一种途径。

Gumbel 分布是 generalized extreme value distribution 的一个特例，对应为 shape 参数为 0（趋向于 0 的极限）的情形，常被称为 type I extreme value distribution。同时它也被称为 log-Weibull 分布，这意味着一个 Gumbel 分布的随机变量的对数是 Weibull 分布。

——————-
He that is born in your house, and he that is bought with your money, must needs be circumcised: and my covenant shall be in your flesh for an everlasting covenant.

为了实现一些比较基本的 solver 和具有一定扩展性的基本库，我们试着使用 concept 的方式描述我们的 design：

基本概念

ObjectiveFunction 是一个 functor，

template <class RetType, class VarType>
struct objective_func {
  typedef RetType ret_type ;
  typedef VarType var_type ;

  ret_type
  operator()( const var_type& x) const {
  }
} ;

ObjectiveFunctionWithGradient 是对 ObjectiveFunction 的 refinement，类似的我们可以有 ObjectiveFunctionWithHessian，这是对 ObjectiveFunctionWithGradient 的 refinement。

template <class RetType, class VarType>
struct objective_func_with_gradient : objective_func {
  ret_type
  operator()( const var_type& x, var_type& g) const {
  }
} ;

我们的 Optimizer 的输入是一个 ObjectiveFunction 以及初始值，输出是搜索获得的变量和目标函数值。

template <class ObjFunc>
struct optimizer {
  const ObjFunc& obj ;

  typedef ObjFunc::ret_type ret_type ;
  typedef ObjFunc::var_type var_type ;

  ret_type
  search (const var_type& x0, var_type& x) {
  }
} ;

类似的，我们可以定义 OptimizerWithGradient 和 OptimizerWithHessian。很自然我们可以将某些 optimizer 共有的东西放在这个结构里面，比如最大迭代次数，终止条件等等。不过这些一般比较简单，还是直接 inline 在 solver 里面比较好。

一些具体的实现

基于这些 concept，比如做一个 binary search（尽管这不是一个 optimization，而是一个 solver），这个是 Optimizer 的实现，要求 var_type 可以比较（Comparable）、可赋值（Assignable）。

template <class ObjFunc>
class binary_search {
public:
  typedef ObjFunc::ret_type ret_type ;
  typedef ObjFunc::var_type var_type ;

  binary_search ( constObjFunc& o,
                          const var_type& a, const var_type&b,
                          int m = 100)
    : obj(o), lb (a), ub (b), maxiter (m) {
  }

  ret_type
  search (const var_type& x0, var_type& x) {
    x = x0 ; // Assignable
    assert ( x > lb && a < ub) ;
    ret_type lb_val = obj (lb), ub_val = obj (ub) ;
    assert (ub_val * lb_val < 0) ;
    for (int i = 0 ; i < maxiter ; ++ i) {
      ret_type cur_val = obj (x) ;
      if (cur_val < ? || ub - lb < ??) // use std::numeric_limits<ret_type>::epsilon to judge convergence
        return cur_val ;
      if (cur_val * ub_val > 0) { // lower upper bound
        ub = x ;
        ub_val = cur_val ;
      } else { // raise lower bound
        lb = x ;
        lb_val = cur_val ;
      }
      // renew
      x = (lb + ub) / 2 ;
    }
  }
private:
  var_type lb ;
  var_type ub ;
  const int maxiter ;
  const ObjFunc& obj ;
} ;

又比如说做一个 gradient descent，或者 CG、L-BFGS 什么的都可以类似的实现，这些都会依赖于所谓的 line search。我们可以另外用一个 concept 表示这个算法。

外围

通过这些类，我们另外还应该提供一些常用的 wrapper，比如很多 objective function 可能原来是函数，我们可能可以为其提供 binding，得到一个 functor，并使得其满足 ObjectiveFunction 这些 concept。对于 solver 我们也可以类似的包装一下。

------------------
And all the days of Enoch were three hundred sixty and five years: