集合関数のベイズ最適化

概要

この記事では、有限集合$X$と関数$f : 2^X \to \mathbb{R}$^[1]に対するブラックボックス最適化問題をベイズ最適化を用いて解く方法を紹介します。つまり、関数$f$の具体的な形はわからず、評価値$f(S) \ (S \in 2^X)$のみが得られる状況で$f$を最適化するという問題設定です。このような問題設定には、例えば空間上に少数のセンサーを設置する位置の最適化などの応用があります。

集合関数のブラックボックス最適化にはいくつかの研究がありますが、この記事では以下の論文で提案されている手法を紹介します。

Kernels over Sets of Finite Sets using RKHS Embeddings, with Application to Bayesian (Combinatorial) Optimization
Poompol Buathong, David Ginsbourger, Tipaluck Krityakierne Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:2731-2741, 2020.

また、この論文の手法は集合のサイズが一定の場合を対象としていますが、この記事では集合のサイズも可変とした場合の最適化方法についても検討します。

なお、この記事ではガウス過程・ベイズ最適化の基本的な知識を前提としています。

集合のサイズが一定の場合

まずは集合のサイズが一定の場合を考えます。この場合は以下のように定式化できます。

$$\begin{align} \text{minimize} \quad & f(S) \\ \text{subject to} \quad & S \subseteq X \\ & |S| = p \end{align}$$

集合のカーネル関数

ベイズ最適化では目的関数をガウス過程でモデル化することが一般的です。今回の問題でも関数$f$をガウス過程でモデル化できればベイズ最適化の手法が使えます。

ガウス過程でモデル化する際にはカーネル関数が必要です。集合関数をガウス過程で表現するためには、集合を対象とするカーネル関数が必要です。

集合のカーネル関数の必要性

集合のカーネル関数が必要な理由を考えてみます。もしRBFカーネルのような一般的なカーネルで十分であれば、わざわざ集合用のカーネルを考える必要はありません。

ガウス過程ではカーネル関数を用いて入力間の類似度を測り、類似度に基づいて予測します。類似度の高い入力は予測値も似た値になるという考え方です。そのためカーネル関数が入力間の類似度を適切に表現できる必要があります。

例えば$X = \{a, b, c, d\}$の部分集合$S = \{a, b\}$と$T = \{c, d\}$があったとき、$S$と$T$の類似度をどう定義するかが問題です。RBFカーネルなどは入力間の距離を用いて類似度を定義しますが、集合間の距離の定め方は自明ではありません。

そのため集合の類似度を適切に表現するためのカーネル関数が必要です。

Deep Embeddingカーネル

上記論文では集合のカーネル関数としてDeep Embeddingカーネルを提案しています。

集合の要素に対する正定値カーネル$k_X(x, y) \ (x, y \in X)$が与えられているとして、Deep Embeddingカーネル$k_{DE}(S, T) \ (S, T \in 2^X)$は以下のように定義されます。

$$\begin{align} k_{DS}(S, T) &= \frac{1}{|S||T|}\sum_{x \in S, y \in T} k_X(x, y) \\ d_{\mathcal{E}}(S, T) &= \sqrt{k_{DS}(S, S) + k_{DS}(T, T) - 2k_{DS}(S, T)} \\ k_{DE}(S, T) &= k_H(d_{\mathcal{E}}(S, T)) \end{align}$$

ここで、$k_H$は任意のヒルベルト空間$\mathcal{H}$に対して、関数$(h, h') \mapsto k_H(\|h - h'\|_\mathcal{H})$が正定値カーネルとなるような関数です。例えば、$k_H(d) = \sigma^2 \exp(-d^2 / \theta)$といった関数が考えられます。$\sigma, \theta$はハイパーパラメータです。

例: 施設配置問題 (p-メディアン問題)

p-メディアン問題を例にとり上記のカーネルを用いたベイズ最適化を適用してみます。

コードはこちらのノートブックにあります。

問題設定

p-メディアン問題とは以下のような問題です。

• 施設を配置する候補地点の集合$X$と、サービスを受ける顧客の集合$C$が与えられます。
• 各顧客$c \in C$から各候補地点$f \in X$までの距離$d_{cf}$が与えられています。
• $X$から$p$個の地点を選び、選んだ地点に施設を開設します。
• 各顧客は最も近い施設にサービスを受けに行きます。
• サービスを受けるために顧客が移動する距離の総和が最小になるような施設の開設地点を求めたいです。

この問題は以下のように定式化できます。

$$\begin{align} \text{minimize} \quad & \sum_{c \in C} \min_{f \in S} d_{cf} \\ \text{subject to} \quad & S \subseteq X \\ & |S| = p \end{align}$$

今回は以下のようなランダムな入力を用意しました。

• $C$は$[0, 1]^2$から一様ランダムに100点サンプリングして作成します。
• $X = C$とします^[2]。
• $d_{ij}$はユークリッド距離とします。
• $p = 5$とします。

顧客集合$C$と施設配置候補集合$F$の位置

アルゴリズムの設定

ベイズ最適化アルゴリズムの設定は以下の通りです。

アルゴリズムの設定

• カーネルの設定
  • 上で説明したDeep Embeddingカーネルを使用。
  • $k_X$はMatérnカーネルを使用。
  • $k_H(d)=\sigma^2\exp(d^2/\theta)$とする。
  • カーネルのハイパーパラメータは周辺尤度最大化で決定。
• 初期訓練データ
  • ランダムにサンプリングした5点のデータを使用。
• 最適化のステップ数
  • 100ステップ。
• 獲得関数
  • 対数期待改善量（LogEI）を使用。
  • 空集合から要素を追加するビームサーチで獲得関数を最適化。ビーム幅は5。

結果

以下はベイズ最適化の進行状況を示すグラフです。各ステップでの目的関数値の変化を最適値に対する比率で表示しています。また、比較のためにランダム探索の結果も示しています。

最適化の過程。横軸はステップ数、縦軸は目的関数値の最適値に対する比率。青点はベイズ最適化の各ステップで評価された目的関数値、青線は各ステップまでの最良の目的関数値。オレンジ点はランダム探索の結果、オレンジ線はランダム探索の最良値。

ベイズ最適化の過程のアニメーション。青点は各ステップで試行された施設の位置、赤点は最良の施設配置。

ベイズ最適化はランダム探索よりも早く良い解に収束していますが、最適解とは数%の差があります。

以下はベイズ最適化で得られた最良の施設配置と、最適解の施設配置です。ベイズ最適化の結果は適度に散らばっており妥当な結果に見えます。ただ、最適解と比べると若干の差があります。

最終的な施設配置。青点はベイズ最適化の最終的な施設配置。赤点は最適解。

集合のサイズが可変の場合

上では集合のサイズが固定の場合を考えましたが、次に集合のサイズが可変の場合を考えます。

Deep Embedding カーネルの問題点

Deep Embeddingカーネルは集合の要素に関して平均を取るため、サイズが大きく異なる集合同士でも類似度が高くなる可能性があります。これは施設配置問題のように施設数（=集合のサイズ）が多いほど目的関数値が小さくなる場合などには問題です。施設数（=集合のサイズ）の違いを考慮する必要があります。

Deep Embedding カーネルの拡張

この問題に対処するため、以下のようにカーネル$k_{DE}'$を定義します。

$$k_{DE}'(S, T) = k_{\text{size}}(|S|, |T|) \cdot k_{DE}(S, T)$$

ここで、$k_{\text{size}}(x, y)$は１次元のカーネル関数（例えばRBFカーネルやMatérnカーネル）です。

$k_{\text{size}}$を掛けることで集合のサイズが異なる場合にはカーネルの値が小さくなるようにしています^[3]。

このカーネル$k'_{DE}$を用いることで、集合のサイズが異なる場合でも適切に最適化が行えます。

集合のサイズと目的関数値の多目的ベイズ最適化

集合のサイズを可変にして単純に目的関数が良くなる集合を見つけるのであれば上のカーネル$k$を用いてベイズ最適化を行えばよいです。

しかし、単純に目的関数が良い集合を見つけたいのではなく、様々なサイズの場合に対して良い集合を見つけたい場合があります。

例えば上で扱った施設配置問題（p-メディアン問題）では施設数を増やすほど目的関数値は小さくなります。また、目的関数では考慮していませんが通常は施設数は増やすほど開設のコストが増えるため、施設数は少ない方が良いです。そのため施設数と目的関数値のトレードオフを考慮した最適化を行いたいことがあります。

このように目的関数と集合のサイズのトレードオフ関係を考慮して最適化する方法として多目的最適化が考えられます。別の方法として$p$ごとに最適化することを繰り返す方法もありますが、多目的最適化手法を使えばすべての$p$に対してより効率的に最適化を行えることが期待できます。

ベイズ最適化で多目的最適化を行うアルゴリズムは様々ありますが、例えば期待超改善量を最大化するように次に試行する集合を選択する方法などがあります。

例: 施設配置問題 (p-メディアン問題)

上で扱った施設配置問題（p-メディアン問題）を再び例に取り上げます。問題設定は同じですが、今回は目的関数値と施設数の両方を考慮して最適化を行います。具体的な違いは以下の通りです。

• 施設数$p$は固定ではなく$3, 4, 5, 6, 7$のいずれかとする。
• 期待超改善量を獲得関数として使用する。

ソースコードはこちらのノートブックにあります。

結果

以下はベイズ最適化の進行状況を示すグラフです。各施設数において目的関数が減少しており最適化が進んでいることがわかります。

ベイズ最適化の過程。最上段は各ステップで試行された施設数を示しています。２段目以降は各施設数ごとの最適化の進行状況です。２段目以降の縦軸は目的関数値の最適値に対する比率です。点が各ステップにおける結果で、点線はそのステップまでの最良の結果です。

ベイズ最適化の過程のアニメーション。青点は各ステップで試行された施設の位置。

以下は施設数に対する目的関数値のグラフです。施設数が多くなるほど目的関数値が小さくなることが確認できます。

施設数と目的関数値の散布図

以下は施設数ごとのベイズ最適化の最終的な施設配置と最適解の配置です。ベイズ最適化の解は適度に散らばっており妥当な解に見えますが、最適解とは差があることもわかります。

施設数ごとの最終的な施設配置。青点はベイズ最適化の最終的な施設配置。赤点は最適解。

他の方法との比較

簡単ですが他の手法との比較も行います。以下の手法を比較してみます。

名称	カーネル	説明
Random		ランダムに集合のサイズ$p$を選んだのち、集合の要素もランダムに選ぶ。
EI (indep)	$k_{DE}$	$p$ごとに個別にベイズ最適化を行う。ただし全体のステップ数を他と揃えるために１つの$p$に対するステップ数は等分する。アルゴリズムの設定は集合のサイズが固定の場合と同じ。
EI (rotate)	$k'_{DE}$	$p=3, 4, 5, 6, 7, 3, 4, ...$というように集合のサイズは順番に変えていく。集合の要素は期待改善量を最大にするように選ぶ。
EI	$k'_{DE}$	各pごとに期待改善量が最大となる集合を探索したのちに、最も期待改善量が大きな $p$ とその集合を選択する。
EHVI	$k'_{DE}$	上に述べた多目的ベイズ最適化による方法。

問題設定は上と同様ですが乱数の種を変えてそれぞれ10回繰り返して比較します。

以下のグラフでは 100 ステップが終了した時点の最良の目的関数値の最適値に対する比率を施設数ごとに比較しています。上に述べた多目的ベイズ最適化（EHVI）が最も良い結果を出していることがわかります。

他の手法との比較の箱ひげ図

コードはこちらのノートブックにあります。

まとめ

この記事では、集合関数のベイズ最適化について、集合のサイズが一定の場合と可変の場合の最適化手法を紹介しました。

集合のサイズが一定の場合には、Deep Embeddingカーネルを用いたベイズ最適化手法を紹介し、施設配置問題を例に実験して良好な結果を得ました。

また、集合のサイズが可変の場合のためにサイズの違いを考慮したカーネル関数を導入しました。また、集合のサイズと目的関数との間にトレードオフ関係がある場合に対して多目的ベイズ最適化による方法を紹介しました。こちらも施設配置問題を例に実験して良好な結果が得られました。

脚注

1. $2^X$は$X$の部分集合全体の集合を表します。

2. このような設定なのでk-medoidクラスタリングの問題ともいえます。

3. 集合のサイズが異なる場合を別のタスクと考えたマルチタスクカーネルといえます。