ML百物语：贝叶斯优化(Bayesian Optimization) 其三_阿米斯丹猫

http://blog.sina.com.cn/u/1993354473

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

ML百物语：贝叶斯优化(Bayesian Optimization) 其三

(2017-08-23 11:44:26)

标签：

ml百物语

贝叶斯优化

分类： ML百物语

其一：http://blog.sina.com.cn/s/blog_76d02ce90102xqqs.html

其二：http://blog.sina.com.cn/s/blog_76d02ce90102xqrh.html

本文是我对于Bayesian Optimization的一些理解和总结

结合python源码的一些分析

无法保证正确，如果有问题，欢迎提出

源码地址：https://github.com/fmfn/BayesianOptimization

提取函数（acquisition function)

上一篇中着重讲了高斯过程，通过使用高斯过程，我们可以得到一个关于目标函数的后验概率描述

或者简单的说，给定采样点x，可以得到f(x)的均值和方差

显然，如果采样点足够多，那么这个后验概率就会越来越拟合真实的f(x)

但是这么做显然是不怎么优雅的，贝叶斯优化的一个主要优点就是可以大幅度减少采样次数，因此才会在超参优化和人机交互方面有比较好的应用

定义提取函数的目标就是为了有目的的去选取采样点，显然，提取的时候有两个方向：

1. explore，尽可能的探索未知的空间，这样对f(x)的后验概率才会更接近f(x)

2. exploit，强化已有的结果，在现有最大值的附近进行探索，保证找到的f(x)会更大

这两个标准是互相矛盾的，如何在这两者之间寻找一个平衡点可以说是提取函数面对的主要挑战。

常见的acquisition function有三种，下面一一介绍这三种：

probability of improvement(POI)

这种方法考虑的是让新的采样能提升最大值的概率最大

假设现在的最大值为f(x+)，那么acquisition函数为：

http://s2/mw690/002aTUyBzy7dFbquXdv41&690Optimization) 其三" TITLE="ML百物语：贝叶斯优化(Bayesian Optimization) 其三" />

Φ(·) 表示的是正态累计分布函数，这个函数也叫做MPI（maximum probability of improvement)，或P算法。

这个函数会更倾向于exploit，而不是explore，因此很有可能会收敛到接近f(x+)附近的位置。为了解决这个问题，可以添加一个trade-off系数。

http://s8/mw690/002aTUyBzy7dFc7mzYj27&690Optimization) 其三" TITLE="ML百物语：贝叶斯优化(Bayesian Optimization) 其三" />

这样就会防止f(x+)附近的，非常细微的提升。

这里的系数ξ可以自己定义，可以通过动态调整这个系数的大小来控制偏向explore还是偏向exploit。

值得注意的是，PI使用的是一种贪心搜索的策略，因此一定程度上说更像是局部搜索。

下面是代码实现：

 Python
Code 

1
2
3
4

    def _poi(x, gp, y_max, xi):
        mean, std = gp.predict(x, return_std=True)
        z = (mean - y_max - xi)/std
        return norm.cdf(z)

Expected improvement(EI)

使用EI作为acquisition function是一个在explore和exploit之间平衡的一个不错选择。explore时，应该选择那些具有比较大方差的点，而在exploit时，则应该优先考虑均值大的点。

要解释EI，还要从POI开始。

POI是一个概率函数，描述的是新的点能比当前最大值大的概率，但是大多少并不关心。

EI则使用的是数学期望，因此"大多少"这个因素也被考虑在内

http://s6/mw690/002aTUyBzy7dFegdgjz95&690Optimization) 其三" TITLE="ML百物语：贝叶斯优化(Bayesian Optimization) 其三" />

将式子展开以后：

http://s2/mw690/002aTUyBzy7dFgvbjNva1&690Optimization) 其三" TITLE="ML百物语：贝叶斯优化(Bayesian Optimization) 其三" />

http://s4/mw690/002aTUyBzy7dFgvdvpN03&690Optimization) 其三" TITLE="ML百物语：贝叶斯优化(Bayesian Optimization) 其三" />

式子中的，参数ξ通常可以固定为0.01

值得注意的是，实验证明动态的参数ξ并不能带来效果的提升，甚至有时会更差

代码实现如下：

 Python Code 

1
2
3
4

    def _ei(x, gp, y_max, xi):
        mean, std = gp.predict(x, return_std=True)
        z = (mean - y_max - xi)/std
        return (mean - y_max - xi) * norm.cdf(z) + std * norm.pdf(z)

Upper confidence bound

除了EI和POI，有一个更简单的想法，直接比较置信空间中的最大值

http://s12/mw690/002aTUyBzy7dFgL9EaD9b&690Optimization) 其三" TITLE="ML百物语：贝叶斯优化(Bayesian Optimization) 其三" />

也就是上图的蓝色区域上边界。

式子如下：

http://s3/mw690/002aTUyBzy7dFgP8xk612&690Optimization) 其三" TITLE="ML百物语：贝叶斯优化(Bayesian Optimization) 其三" />

这种做法比较的是置信区间内的最大值，尽管看起来简单，但是实际效果却意外的好

代码如下：

 Python Code 

1
2
3

    def _ucb(x, gp, kappa):
        mean, std = gp.predict(x, return_std=True)
        return mean + kappa * std

下面是POI,EI,UCB三种方法的比较：

http://s10/mw690/002aTUyBzy7dFh06KHTc9&690Optimization) 其三" TITLE="ML百物语：贝叶斯优化(Bayesian Optimization) 其三" />

POI,EI,UCB的比较，上图是真实分布和后验概率，下图是acquisition function。

可以看出，POI在找到了局部极值后就不继续探索了，EI在t>=5之后acquisition的前半段几乎为0。

在acquisition函数的选择上并没有什么准则，还是看经验吧，Brochu等人试着混合使用几个不同的acquisition函数，（可能类似boost算法？）得到了意外的好的结果。

关于三种常见的acquisition function就讲到这里了。接下来就是和理论无关的纯代码了

贝叶斯优化时每次迭代都会找能让acquisition函数最大的点。而这个函数的形式是已知的，因此可以使用各种想得到的办法，梯度下降/BFGS/牛顿...等等。

python源码中使用的是一种混合的办法，先随机采样100000个点，找其中的最大值作为初始最大值，然后在以250个种子点计算L-BFGS看能不能超越当前的最大值，代码如下：

 Python Code 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

def acq_max(ac, gp, y_max, bounds):
    """
    A function to find the maximum of the acquisition function

    It uses a combination of random sampling (cheap) and the 'L-BFGS-B'
    optimization method. First by sampling 1e5 points at random, and then
    running L-BFGS-B from 250 random starting points.

    Parameters
    ----------
    :param ac:
        The acquisition function object that return its point-wise value.

    :param gp:
        A gaussian process fitted to the relevant data.

    :param y_max:
        The current maximum known value of the target function.

    :param bounds:
        The variables bounds to limit the search of the acq max.

    Returns
    -------
    :return: x_max, The arg max of the acquisition function.
    """

    # Warm up with random points
    x_tries = np.random.uniform(bounds[:, 0], bounds[:, 1],
                                 size=(100000, bounds.shape[0]))
    ys = ac(x_tries, gp=gp, y_max=y_max)
    x_max = x_tries[ys.argmax()]
    max_acq = ys.max()

    # Explore the parameter space more throughly
    x_seeds = np.random.uniform(bounds[:, 0], bounds[:, 1],
                                size=(250, bounds.shape[0]))
    for x_try in x_seeds:
        # Find the minimum of minus the acquisition function
        res = minimize(lambda x: -ac(x.reshape(1, -1), gp=gp, y_max=y_max),
                       x_try.reshape(1, -1),
                       bounds=bounds,
                       method="L-BFGS-B")

        # Store it if better than previous minimum(maximum).
        if max_acq is None or -res.fun[0] >= max_acq:
            x_max = res.x
            max_acq = -res.fun[0]

    # Clip output to make sure it lies within the bounds. Due to floating
    # point technicalities this is not always the case.
    return np.clip(x_max, bounds[:, 0], bounds[:, 1])

30～34行就是随机点找初始最大值的过程。之后在37行定义了250个种子点，然后从每个种子点出发求一次L-BFGS，看结果能不能超过当前的最大值，如果可以，那么用这个值作为当前最大值。

关于acquisition函数就讲到这里吧，如果还有下篇的话，可能会讲讲噪声环境下的优化，还有一些应用的例子吧。

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：ML百物语：贝叶斯优化(Bayesian Optimization) 其二

后一篇：[PBS真的可以为所欲为] Unreal材质模型源码分析其一

新浪BLOG意见反馈留言板　欢迎批评指正