文章目录
- 概
- 主要内容
Lam R, Willcox K, Wolpert D H, et al. Bayesian Optimization with a Finite Budget: An Approximate Dynamic Programming Approach[C]. neural information processing systems, 2016: 883-891.
@article{lam2016bayesian,
title={Bayesian Optimization with a Finite Budget: An Approximate Dynamic Programming Approach},
author={Lam, Remi and Willcox, Karen and Wolpert, David H},
pages={883–891},
year={2016}}
概
贝叶斯优化中的多步优化策略. 像经典的EI方法, 就是只考虑一步, 即希望找到
r
(
S
k
,
x
k
+
1
,
f
k
+
1
)
=
max
{
0
,
f
m
i
n
S
k
−
f
k
+
1
}
r(mathcal{S}_k, x_{k+1},f_{k+1})=max {0, f_{min}^{mathcal{S}_k}-f_{k+1}}
r(Sk,xk+1,fk+1)=max{0,fminSk−fk+1}
的期望收益最大化的点
x
k
+
1
x_{k+1}
xk+1为下一个评估点.
上式中的 f m i n S k f_{min}^{mathcal{S}_k} fminSk是指目标函数在集合 S k mathcal{S}_k Sk上的最小值.
主要内容
考虑如下动态规划, 第k步的
状态:
S
k
mathcal{S}_k
Sk, 即观测到的点;
控制:
u
k
u_k
uk, 且
u
k
(
S
k
)
=
x
k
+
1
u_k(mathcal{S}_k)=x_{k+1}
uk(Sk)=xk+1
扰动:
w
k
:
=
f
k
+
1
∼
p
(
f
(
x
k
+
1
)
∣
S
k
)
w_k:=f_{k+1} sim p(f(x_{k+1})|mathcal{S}_k)
wk:=fk+1∼p(f(xk+1)∣Sk);
设状态转移为:
S
k
+
1
=
F
k
(
S
k
,
x
k
+
1
,
f
k
+
1
)
=
S
k
∪
{
(
x
k
+
1
,
f
k
+
1
)
}
.
mathcal{S}_{k+1} = mathcal{F}_k (mathcal{S}_{k}, x_{k+1}, f_{k+1}) = mathcal{S}_{k}cup {(x_{k+1}, f_{k+1})}.
Sk+1=Fk(Sk,xk+1,fk+1)=Sk∪{(xk+1,fk+1)}.
收益(效用函数):
U
k
(
x
k
+
1
;
S
k
)
=
E
w
k
[
r
k
(
S
k
,
x
k
+
1
,
f
k
+
1
)
+
J
k
+
1
(
F
k
(
S
k
,
x
k
+
1
,
f
k
+
1
)
)
]
,
J
k
(
x
k
+
1
)
=
max
x
k
+
1
U
k
,
J
N
=
r
N
(
x
N
+
1
)
.
U_k(x_{k+1}; mathcal{S} _k) = mathbb{E}_{w_k}[r_k(mathcal{S}_k, x_{k+1}, f_{k+1})+J_{k+1}(mathcal{F}_k (mathcal{S}_{k}, x_{k+1}, f_{k+1}))], \ J_k(x_{k+1}) = max_{x_{k+1}} U_k,\ J_N=r_N(x_{N+1}).
Uk(xk+1;Sk)=Ewk[rk(Sk,xk+1,fk+1)+Jk+1(Fk(Sk,xk+1,fk+1))],Jk(xk+1)=xk+1maxUk,JN=rN(xN+1).
很自然的想法是, 我们最大化 U 1 U_1 U1, 来获得所需的评估点, 但是问题是, 这个是一个嵌套的最大化优化问题， 不易求解.
本文采用rollout 算法来估计 U k U_k Uk, 具体如下:
给定基本的决策控制 π = ( π 1 , … , π N ) pi = (pi_1, ldots, pi_N) π=(π1,…,πN)(比如最大化EI), 为了最优化 U k U_k Uk, 我们先选择用 H k + 1 H_{k+1} Hk+1估计 J k + 1 J_{k+1} Jk+1, 其定义如下:
其中
n
∈
{
k
+
1
,
…
,
N
−
1
}
n in {k+1, ldots, N-1}
n∈{k+1,…,N−1},
γ
∈
[
0
,
1
]
gamma in [0, 1]
γ∈[0,1] 用以调节增量.
H
n
H_n
Hn是一个期望, 可以用Gauss-Hermite正交化估计:
其中 N ~ = min { k + h , N } tilde{N} = min {k+h, N} N~=min{k+h,N}, 用以限制最大的估计步数, α ( q ) alpha^{(q)} α(q)是正交系数, f n + 1 ( q ) f_{n+1}^{(q)} fn+1(q)是Hermite多项式的根(大概).
于是,
U
k
(
x
k
+
1
,
S
k
)
U_k(x_{k+1},mathcal{S}_k)
Uk(xk+1,Sk)便可用下式估计:
算法如下:
Input:
h
,
γ
,
N
,
S
1
h, gamma, N, mathcal{S}_1
h,γ,N,S1;
repeat N:
- 根据(20）近似最大化 U k U_k Uk
- 更新 S k + 1 = S k ∪ { ( x k + 1 , f k + 1 ) } mathcal{S}_{k+1}=mathcal{S}_k cup {(x_{k+1},f_{k+1})} Sk+1=Sk∪{(xk+1,fk+1)}
out: f m i n S N + 1 f_{min}^{S_{N+1}} fminSN+1.
最后
以上就是还单身小刺猬最近收集整理的关于Bayesian Optimization with a Finite Budget: An Approximate Dynamic Programming Approach的全部内容，更多相关Bayesian内容请搜索靠谱客的其他文章。
发表评论 取消回复