「ベイズ最適化」を読む　～第5章制約付きベイズ最適化 ①問題設定～

はじめに

データを使って仮説の生成と検証を行なうための方法であるベイズ最適化を学ぶために，今村秀明・松井孝太著「ベイズ最適化　ー適応的実験計画の基礎と実践ー」を読むことにした。

本記事は，「第5章制約付きベイズ最適化」における問題設定に関する読書メモである。

本書の紹介ページ

www.kindaikagaku.co.jp

第5章制約付きベイズ最適化

この章からは，ブラックボックス最適化のより応用的な問題設定を扱っている。本章では，最適化したい目的関数とは別に「制約」が存在する「制約付き最適化」について説明している。

5.1 制約付き最適化とは

制約付き最適化(constrained optimization)とは，最適化したい目的関数 $f$ 以外に，探索点 $x \in \mathcal{X}$ が満たすべき制約が存在する問題設定である。

制約の例として，以下のようなものが挙げられる。

探索点 $\boldsymbol{x}$ の各次元が特定の範囲にある : $a_i \leq x_i \leq b_i$
探索点 $\boldsymbol{x}$ が特定の不等式を満たす : $\boldsymbol{c}^T \boldsymbol{x} \leq \boldsymbol{0}$
目的関数の評価値が一定の値以下 : $f(\boldsymbol{x}) \leq c$
目的関数の評価にかかった時間が一定の値以下 : $\mathrm{Time}(\boldsymbol{x}) \leq c$
目的関数の評価に要したメモリ使用量が一定の値以下 : $\mathrm{UsedMemory}(\boldsymbol{x}) \leq c$

制約付き最適化の多様性

上記の制約の例だけでも，制約付き最適化が多様であるということが分かる。本書で紹介されている制約付き最適化問題の分類には以下のようなものが挙げられる。

探索点自体の評価 vs 探索点の関数の評価

1. および 2. の問題設定では，探索点 $\boldsymbol{x}$ が決まれば制約が満たされているかどうかが直ちに判定できる。
一方，3.，4.および5では，探索点 $\boldsymbol{x}$ の関数( $f(\boldsymbol{x})$ など)を評価しているので，制約が満たされているか直ちに判断することができない。

制約をhardに扱う vs 制約をsoftに扱う

制約が満たされない探索点は評価しないことを，制約をhardに扱うと表現する。
この場合，3. 以降のように探索点の関数( $f(\boldsymbol{x})$ など)を評価する必要がある場合は，hardに扱う場合は難しいと言える。

一方制約が満たされない探索点の評価を許容する扱いのことを，制約をsoftに扱うと表現する。
この場合，制約が満たされる領域と満たされない領域の境界をよく推定できるため，最適化の性能が上がる可能性がある。一方で，制約を満たさない無駄な探索点ばかりを評価する可能性もある。

本書で扱う制約付きベイズ最適化の問題設定

本書で扱う制約付きベイズ最適化の問題設定は以下の通りである。

不等式の形をした制約を対象とする。
制約が満たされているかどうかが容易に判定できないブラックボックスな制約を扱うものとする。
制約が満たされる領域と満たされない領域の境界を上手く推定するために，制約をsoftに扱うものとする。

5.2 制約付きベイズ最適化

前章までで紹介していたブラックボックス最適化の問題設定における，最適化の手順は以下の通りであった。

$n$ トライアル目において，それまでえら得ているデータ $\mathcal{D}_n= \{ (\boldsymbol{x}_i, y_i) \}_{i=1}^n$ をもとにして次に試す探索点 $\boldsymbol{x}_{n+1}$ を決定する。
$\boldsymbol{x}_{n+1}$ を目的関数 $f$ に渡し，ノイズを含む評価値 $y_{n+1} = f(\boldsymbol{x}_{n+1}) + \varepsilon$ を得る。
$\mathcal{D}_{n+1}= \mathcal{D}_n \cup \{ (\boldsymbol{x}_{n+1}, y_{n+1}) \}$ として次のトライアルに移行する。

制約付き最適化では，各トライアルにおいて， $\boldsymbol{x}_{n+1}$ が満たすべき制約を課す。
制約は主に不等式 $\boldsymbol{c} ( \boldsymbol{x}_{n+1} ) \leq 0$ の形で与えられるものとする。

$\begin{align} \min_{x \in \mathcal{X}} f(\boldsymbol{x}) \quad \mathrm{s.t.} \quad \boldsymbol{c}( \boldsymbol{x} ) \leq 0 \\ \end{align}$

問題設定の詳細

不等式制約

不等式制約は $\boldsymbol{c}(\boldsymbol{x}) \leq 0$ という形である。不等式が逆の場合や，右辺が $0$ 出ない場合は，式変形をすることでこの形に持っていく。

等式制約 $\boldsymbol{c} ( \boldsymbol{x} ) = 0$ の場合は， $\boldsymbol{c} ( \boldsymbol{x} ) \leq 0$ および $-\boldsymbol{c} (\boldsymbol{x}) \leq 0$ の形に変形する。
実用上は，このように分解すると制約を満たす解を見つけることがとても困難になるので，閾値 $\delta$ を設定して， $\boldsymbol{c} ( \boldsymbol{x} ) \leq \delta$ および $-\boldsymbol{c} (\boldsymbol{x}) \leq \delta$ のように制約を緩和することが多い。

$\boldsymbol{c} (\boldsymbol{x}) = x$ とすると，等式制約 $\boldsymbol{c} (\boldsymbol{x}) = 0$ は，等式制約 $x = 0$ となる。
また，制約が緩和された問題は，( $x \leq \delta$ および $-x \leq \delta$ ) $\Leftrightarrow$ ( $x \leq \delta$ および $-\delta \leq x$ )となる。

制約をみたすかどうかの判定タイミング

各トライアルにおいて選んだ探索点 $\boldsymbol{x}_{n+1}$ に対する制約関数の値 $\boldsymbol{c} ( \boldsymbol{x}_{n+1} )$ は，目的関数の計算前に分かるとは限らないと仮定する。

制約関数の扱い

制約関数 $\boldsymbol{c}$ はブラックボックス関数であり，評価には目的関数の評価と同様にコストがかかると仮定する。
これは連続最適化や凸最適化における制約付き最適化とは大きく異なる。 $\boldsymbol{c}$ をブラックボックス関数として扱うことにより，多様で複雑な制約を扱うことができるようになる。

観測ノイズ

各トライアルにおいて，目的関数と制約関数の両方を考慮して探索点 $\boldsymbol{x}_{n+1}$ を選び，

$\begin{align} y_{n+1} &= f(\boldsymbol{x}_{n+1}) + \varepsilon, \quad \varepsilon \sim \mathcal{N}(0, \sigma^2) \\ \\ \boldsymbol{z}_{n+1} &= c(\boldsymbol{x}_{n+1}) + \varepsilon', \quad \varepsilon' \sim \mathcal{N}(\boldsymbol{0}, {\sigma'}^2 \boldsymbol{I}_K) \\ \\ \mathcal{D}_n &= \{ (\boldsymbol{x}_i, y_i, \boldsymbol{z}_i) \}_{i=1}^n \\ \\ \sigma^2, {\sigma'}^2 &: \mathrm{Const. }\\ \end{align}$

とする。

まとめと感想

今回は，「第5章制約付きベイズ最適化」のうち，問題設定について学んだ。

連続最適化や凸最適化と異なり，制約関数 $\boldsymbol{c}$ 自体がブラックボックス関数である，ということが特徴であった。これは問題を難しくしてしまう要因かもしれないが，一方で計算時間制約やメモリ制約といった，実用上で扱わないといけない制約を取り込めるので，柔軟性はあると感じた。

また，等式制約 $\boldsymbol{c} (\boldsymbol{x}) = 0$ の扱い方についても参考になった。実運用上では，等式制約はかなり厳しいものであるが， $0$ ではなく， $-\delta \sim \delta$ の間の小さい数ならばOKとするテクニックは，他の最適化問題を解くうえでも参考になると感じた。