限られた試行回数でのベイズ最適化
ベイズ最適化(Bayesian Optimization, BO)は、評価に多大なコスト(時間、計算資源、費用など)がかかる「ブラックボックス関数」を最適化するための強力な手法です。特に、利用可能な既存データが少ない、あるいは関数評価の回数(予算)が限られている状況において、他の最適化手法と比較して優れた性能を発揮することで知られています。
ブラックボックス関数とは、内部構造が不明で、入力値を与えると出力値が得られるものの、その関係性が数式などで明示的に表現されていない関数を指します。例えば、複雑なシミュレーション、化学合成や材料開発における実験などがこれに該当します。ベイズ最適化は、代理モデル(Surrogate Model)と獲得関数(Acquisition Function)という2つの要素を巧みに利用し、「予測→評価→モデル更新」のサイクルを繰り返すことで、少ない評価回数で効率的に最適解を探索します。
しかしながら、従来のベイズ最適化であっても、評価予算が極端に少ない制約下では課題に直面します。このような状況では、探索空間全体を正確にモデル化するための十分なサンプル(評価点)を得ることが困難になります。代理モデルの精度が低いと、有望な領域を見逃したり、逆に有望でない領域を集中的に探索してしまったりする可能性があり、結果として最適とは言えない性能(準最適解)に留まってしまうことがあります。
この課題に対処するため、限られた試行回数下でベイズ最適化のアプローチが探求されています。本記事では、まず「Limited-budget ベイズ最適化」の概念を定義し、次にこの課題に取り組むための既存アプローチに関連する主要なアイデアを概説します。さらに、これらのアプローチがもたらす利点と、それに伴う課題についても解説していきます。
Limited-budget ベイズ最適化の定義
最適化の文脈において、Limited-budget ベイズ最適化とは、関数評価の実行可能な回数が極めて厳しく制限されている状況を指します。このような状況は、データ点(特定の入力パラメータ設定)を評価することが極端に時間を要する場合や、多大な計算資源または費用を必要とする環境で発生します。
例えば、多結晶材料の分野では、材料特性に大きな影響を与える結晶粒界の構造を最適化することが重要です。この問題に対して、ベイズ最適化は材料特性を評価するために密度汎関数理論(Density Functional Theory, DFT)に基づくシミュレーションと組み合わせて適用されてきました。DFT計算は精度が高い一方で、一つの構造に対する計算に多大な時間がかかります。したがって、通常の開発プロジェクト期間でこのような計算コストの高い評価を何百何千回も行うことは現実的ではなく、限られた評価回数の中で可能な限り最適な性能(例えば、安定性や特定の物性値)を達成するための効率的な最適化戦略が不可欠となります。実験者は、ごくわずかな関数評価で最大の成果を得たいと考えるでしょう。
Limited-budget ベイズ最適化とコスト考慮型ベイズ最適化
ベイズ最適化の文献において「予算」や「コスト」という言葉が使われる際、それは単に関数評価の回数制限だけでなく、実験やシミュレーションを実行するための実際のコスト(時間、費用、リソース消費など)を指す場合もあります。
多くの実世界のシナリオでは、このコストが均一ではない(heterogeneous)可能性があります。つまり、探索空間内の場所(パラメータ設定)によって、評価にかかるコストが異なる場合があるのです。例えば、ある実験条件では短時間で結果が出るが、別の条件では長時間かかる、あるいは特定のパラメータ領域では高価な試薬が必要になる、といった状況が考えられます。
このような場合、ユーザーは主要な目的(例えば、材料の性能最大化)を達成すると同時に、総コストを最小限に抑えたいと考えることがよくあります。この目的を達成するためには、最適化アルゴリズムは、場所によってコストが変動することを認識し、コストパフォーマンスの高い実験設定を推奨する必要があります。このような問題設定は、「コスト認識型ベイズ最適化(Cost-aware BO)」や「コスト感受性ベイズ最適化(Cost-sensitive BO)」などと呼ばれ、予算制約のあるベイズ最適化の研究分野で重要なトピックとなっています。
しかし、本記事ではこのコスト考慮型BOについては扱いません。本記事では、評価1回あたりのコストは均一(homogeneous)であると仮定し、評価の総回数(有限な評価予算)が厳しく制限されている状況に焦点を当て、そのための技術について解説します。
従来のベイズ最適化が低予算下で抱える課題
従来のベイズ最適化アルゴリズムは、評価予算が極めて限られている場合、いくつかの点で困難に直面します。
(1) 不十分なサンプリングによる代理モデルの精度低下
限られた関数評価回数では、アルゴリズムは探索空間全体を適切にモデル化するための十分なデータを収集できません。サンプル数が不足すると、代理モデルは真の関数の挙動を捉えきれず、過学習(既知の点に過剰に適合し、未知の領域での予測精度が低い)や未学習(有望な領域がモデル化されないまま残る)といった問題を引き起こす可能性があります。結果として、最適解から程遠い推奨を行ってしまい、最適化の性能が低下します。
(2) 不十分な探索と活用
ベイズ最適化の核心は、探索空間の未知の領域を探索すること(Exploration)と、これまでに見つかった有望な領域をさらに深く活用すること(Exploitation)のバランスを取ることにあります。しかし、評価回数が少ない場合、このバランスを取ることがより一層難しくなります。探索に偏りすぎると、限られた予算を有望でない領域の評価に浪費してしまう可能性があります。逆に活用に偏りすぎると、より良い解が存在するかもしれない未探索の領域を見逃し、局所最適解に陥ってしまうリスクが高まります。少ない評価回数でこのジレンマを解消するのは非常に困難です。
(3) 次元の呪い
ベイズ最適化(における代理モデル)を含め、機械学習モデルはしばしば「次元の呪い」の影響を受けます。探索空間の次元数(入力パラメータの数)が増加するにつれて、空間の体積は指数関数的に増大し、ブラックボックス関数をモデル化するために必要なサンプル数も急増します。高次元空間では、限られたサンプルが非常に疎(スパース)に分布するため、代理モデルの構築が本質的に困難になります。評価予算が少ない状況では、この問題はさらに顕著になり、高次元問題に対する従来のベイズ最適化の適用性を著しく制限します。
これらの課題が存在するため、研究者たちは、限定予算という厳しい条件下でもベイズ最適化が最適な性能を発揮できるように、Limited-Budgetに特化した様々な戦略を提案しています。これらの戦略は、従来のBOの枠組みを拡張・修正し、限られた評価機会を最大限に活用することを目指します。
Limited-budget ベイズ最適化のアプローチ
限定予算または有限予算のベイズ最適化に関連する研究を調査すると、主に2つの大きな方向性が見られます。
- 探索空間の絞り込み(Search space refinement): 限られた予算をより有望な領域に集中させることで、探索効率を高めるアプローチです。全体を満遍なく探索するのではなく、有望そうな部分領域に焦点を当ててモデル化と探索を行うことを目指します。
- 先読みアプローチ(Look-ahead approach)または非近視眼的BO(Non-myopic BO): 各評価ステップで、その選択が将来の探索に与える影響を考慮に入れるアプローチです。目先の利益(獲得関数値)だけでなく、複数ステップ先までの長期的な効果を最大化するように次の評価点を決定します。
以下では、これら2つのアプローチの本質を簡潔に説明し、それぞれに関連する具体的な戦略を紹介します。
探索空間の絞り込み:有望な領域への集中
探索空間の絞り込みは、評価予算が限られている場合に、探索対象をより小さな領域に限定することで探索効率を高める戦略です。このアプローチの根底にある仮定は、比較的有望でありそうな、より小さな領域を集中的に探索すれば、限られた予算内でも精度の高い代理モデルを構築でき、結果としてより良い推奨(最適解に近い点)が得られるだろう、というものです。
Nomura & Abeによる論文 "A Simple Heuristic for Bayesian Optimization with A Low Budget" では、残りの評価回数を最大限に活用するために探索空間を操作する戦略が提案されています。このヒューリスティックな手法は、以下の手順で有望な部分空間を特定します。
- 初期分割と評価: まず、探索空間全体をいずれかの一つの次元に沿って k 個の等しい部分領域に分割します。そして、各部分領域の中心点を評価します。(下図1の左側、x1軸に沿って3分割し、各中心を評価)
- 有望領域の選択と再分割: 最も良い評価値(目的に応じて最大値または最小値)を示した中心点を持つ部分領域を選択します。次に、この選択された領域を、別の次元に沿って再び k 個の等しい部分領域に分割し、同様に各中心点を評価します。(下図1の中央、選択された領域をx2軸に沿って3分割し、各中心を評価)
- 繰り返しの適用: このプロセスを、全ての次元が考慮されるまで繰り返します。
- 絞り込み後のBO: 全評価予算 B の一部(絞り込み用予算Bref)をこの絞り込みプロセスに使用します。これにより、元の探索空間よりも小さく、かつ有望と期待される部分領域が得られます。その後、残りの予算を使って、この絞り込まれた領域内で従来のベイズ最適化を実行します。
図1. 探索空間の絞り込みアプローチ (miLab編集部作成)
【利点】
- 限られた評価予算の最適利用: 小さく有望な領域に探索を集中させることで、限られたリソースを効率的に使用できます。広大な空間を満遍なく探索するよりも、短期間で有望な解を見つけられる可能性があります。
- 事前知識不要: この探索空間絞り込みのヒューリスティックは比較的単純であり、実装が容易です。探索空間に関する事前の知識(例えば、最適解が存在しそうな大まかな領域など)を必要としません。
【リスク】
- 初期分割への依存性: この手法の有効性は、探索空間をどのように初期分割するかに大きく依存します。特に、次元を選択する順序や分割数 k の選び方が適切でない場合、真の最適領域を含まない部分空間に絞り込んでしまい、最適解を見つけられない可能性があります。
- ヒューリスティックのチューニング: 探索空間を絞り込むために使用されるヒューリスティック(分割数 k、次元選択順序など)は、問題ごとに最適な設定が異なる可能性があり、追加のチューニングが必要になる場合があります。これにより、アプローチの汎用性が低下する可能性があります。
- スケーラビリティ: 高次元データの場合、絞り込みプロセスの計算コストが増加する可能性があります。また、次元ごとに順番に絞り込んでいくため、高次元になると特定の次元の組み合わせに過度に焦点を当ててしまい、全体的な探索が制限される(他の有望な領域を見逃す)リスクがあります。
先読みアプローチと近視眼的ベイズ最適化
Limited-budgetベイズ最適化の研究におけるもう一つの重要な動向は、「先読みアプローチ(Look-ahead approach)」と呼ばれるものです。従来のベイズ最適化では、アルゴリズムは各ステップでその選択が長期的にどのような影響をもたらすかを考慮せず、目先の即時的な改善(報酬)が最大となる点を選択しようとします。私たちが普段利用する最も一般的な獲得関数(例:Expected Improvement (EI), Probability of Improvement (PI) など)の多くは、ある点を選択するという決定が将来の探索に与える長期的な影響を考慮していません。この問題は、ベイズ最適化の「近視眼性(Myopia)」問題と呼ばれます。近視眼性とは文字通り、遠くを見通す能力がないこと、つまり短期的な視点しか持てないことを指します。
特徴 | 近視眼的獲得関数 (Myopic AF) | 非近視眼的獲得関数 (Non-myopic AF) |
考慮する範囲 | 次の1ステップのみ | 複数ステップ先(r ステップ先)まで |
目的 | 即時的な報酬(改善量)の最大化 | 将来のステップを含む累積報酬(改善量)の最大化 |
計算コスト | 比較的低い | 高い(特に先読みステップ数 r が大きい場合) |
複雑性 | 単純 | 複雑(動的計画法やモンテカルロ近似が必要な場合がある) |
評価予算が極めて制限されている場合、短期的な利益を優先するよりも、一つの評価がもたらす長期的な効果(例えば、将来の不確実性をどれだけ減らせるか、より有望な領域を発見するのにどれだけ役立つか)を考慮することが、より価値を持つようになります。
例えば、EIのような従来の獲得関数は、過去の観測データのみに依存して、即時的な期待報酬(現在の最良値からの改善量の期待値)を最大化することで短期的な利益を優先します。過去のサンプルは、代理モデルの平均値が高い領域(活用すべき領域)と分散(不確実性)が高い領域(探索すべき領域)を特定するのに役立ち、EIはこれら二つの基準のバランスを取りながら次の評価点を推奨します。しかし、この推奨点は、設定された探索と活用のバランスに基づいて決定され、その選択が将来の決定(次の次の評価点、そのまた次の評価点...)にどのような影響を与えるかは考慮されません。これは、チェスのプレイヤーが、その手によって将来の盤面がどうなるかを考慮せず、次の手で取れる駒や有利になる度合いだけを見て指し手を決めるようなものです。
対照的に、非近視眼的獲得関数の戦略は、複数手先まで読み、計画を立てて指し手を決める別のチェスプレイヤーに例えることができます。この場合、現在の手(評価点の選択)が将来の可能な手(将来の評価点)や得られる可能性のある報酬(将来の改善量)に与える影響が考慮されます。例えば、非近視眼的なEIの一つの表現方法は、近視眼的なEI最大化による即時的な利益と、モンテカルロシミュレーションを通じて計算される将来の期待改善量の期待値の合計として定式化できます。このような表現は、通常、複雑な問題をより小さな部分問題に分解する動的計画法(Dynamic Programming)のアプローチを用いて導出されます。
実際には、将来の累積報酬の期待値を計算するプロセスは、考慮すべき将来のシナリオ(評価点の選択とその結果の組み合わせ)が指数関数的に増加するため、計算コストが非常に高くなる可能性があります。例えば、r ステップ先読みの非近視眼的EIでは、各ステップで $$ m $$ 回のシミュレーションを行うと、計算コストは$$ O(m^r) $$のオーダーで増加する可能性があります。この計算負荷を考慮し、理論的にはnステップ先読みのアプローチの表現が存在するものの、多くの実用的な非近視眼的獲得関数では、先読みのステップ数 $$ r $$ の値を通常 2 から 5 程度に制限します。これは文献では「ローリングホライズン(Rolling Horizon)」とも呼ばれます。非近視眼的BOの研究において、このローリングホライズンの適切な値を見つけることは、重要な研究課題の一つです。
以下は、Limited-Budget BOの研究において、ベイズ最適化の「近視眼性」問題に取り組んでいる研究の例です。
- Bayesian Optimization with a Finite Budget: An Approximate Dynamic Programming Approach
- GLASSES: Relieving the myopia of Bayesian optimization.
- Practical Two-Step Lookahead Bayesian Optimization
- The Parallel Knowledge Gradient Method for Batch Bayesian Optimization
次に、非近視眼的BOアプローチを使用することに伴う利点とリスクについて説明します。
【利点】
- 評価効率の向上: 複数ステップ先と限られた予算を考慮することで、これらの手法は利用可能な関数評価をより効率的に使用できます。結果として、より少ない評価回数でより良い解を見つけられる可能性があります。単に目先の改善量が大きい点を選ぶのではなく、「情報を得る価値が高い点」や「将来の最適化に繋がる点」を選べるようになります。
- 探索と活用のより良いバランス: これらのアプローチの非近視眼的な性質は、探索空間の絞り込みアプローチと比較して、探索と活用の間でより洗練されたバランスを取ることを可能にします。これにより、局所最適解に陥る可能性を低減できます。(下図2参照)近視眼的な獲得関数(例:EI)は、有望そうな領域を貪欲に評価し続け、結果として準最適な領域に囚われてしまうことがあります。しかし、非近視眼的な獲得関数は、有望な領域を活用することと、不確実性の高い領域を探索することの間でより良いバランスを取ることで、大域的最適解を見つける可能性を高めます。
- 適応性: 一部の手法では、残りの予算や目的関数に関する現在の知識の状態に基づいて戦略を適応させることができます。例えば、予算が残り少なくなってきたら探索よりも活用を重視する、といった調整が可能です。これにより、より柔軟で頑健な最適化が実現します。
図2. 近視眼的 vs 非近視眼的ベイズ最適化 (miLab編集部作成)
【リスク】
- 計算複雑性: これらの手法の洗練度の向上は、多くの場合、より高い計算複雑性という代償を伴います。複数ステップ先読みのアプローチは、より単純な獲得関数よりも計算に時間がかかることがあります。しかしながら、Limited-budget ベイズ最適化が適用されるシナリオ、すなわち実験やシミュレーションのコストが非常に高い応用においては、この増加した計算(モデリング)コストは、単純な獲得関数と比較して優れた最適化性能が実証されているため、正当化されることが多いです。 つまり、1回の評価にかかるコスト(数時間~数週間)に比べれば、次の評価点を決めるための計算時間(数分~数時間)は許容範囲内と考えられる場合が多いです。
- 近似: 厳密な複数ステップ先読みの計算は非常に複雑であるため、これらの手法の多くは近似やヒューリスティクスに依存しています。これらの近似が常に最適な決定につながるとは限りません。特に、代理モデルが真の関数をうまく捉えられていない(misspecified model)状況で、大きなローリングホライズン(先読みステップ数)を使用すると、近似誤差が深刻になる可能性があります。先読みのステップ数を適切に選択することが、近似誤差を低減する上で重要になります。
実用的なMI応用における考慮事項
ベイズ最適化は、そのブラックボックス最適化能力、少ないサンプルサイズでの効率性、そして微分不要な性質から、広範な分野で利用されています。特にマテリアルズ・インフォマティクス(MI)分野では、実験やシミュレーションにコストがかかることが多いため、BOは有力なツールとして認識されています。
しかしながら、Limited-budget ベイズ最適化という領域は比較的新しく、まだ発展途上にあります。そのため、これらの先進的なアプローチを実際のMIシナリオ(例えば、新材料探索、プロセス最適化など)に適用する際には、いくつかの要因を慎重に考慮する必要があります。
(1) 汎化性能とアプローチ選択
本記事で紹介した「探索空間の絞り込み」と「先読みアプローチ」は、それぞれ独自の長所と短所を持っています。しかし、あらゆる種類のMI問題に対して万能に適用できる単一の最良アプローチを見つけることは非現実的です。どのアプローチを選択すべきかは、以下のような多くの要因に依存します。
- 探索空間の次元: 高次元問題では、探索空間の絞り込みは特定の領域に偏りすぎるリスクがあり、先読みアプローチは計算コストが爆発する可能性があります。
- 残りの評価予算の量: 予算が極端に少ない場合は、わずかな評価で有望領域を特定する必要があり、絞り込み戦略が有効かもしれません。一方、ある程度の予算が残っている場合は、長期的な視点を持つ先読みアプローチが有利になる可能性があります。
- 獲得関数計算のための計算予算: 先読みアプローチ、特にモンテカルロシミュレーションを伴うものは、次の評価点を決定するための計算時間が長くなる可能性があります。これが許容範囲内かどうかを評価する必要があります。
- 近似誤差の許容度: 先読みアプローチにおける近似誤差が、最適化の性能にどの程度影響するか、その許容度を考慮する必要があります。
(2) 高次元へのスケーラビリティ
紹介されたLimited-budget ベイズ最適化アプローチの多くは、比較的低次元の問題での経験的な結果報告が主であり、高次元(例えば、数十以上のパラメータ)の探索空間での有効性は十分に検証されていません。MI分野では高次元のパラメータ空間を扱うことも少なくないため、これらの手法を高次元問題に適用する際には、そのスケーラビリティについて追加の検証や、高次元向けに設計された手法の検討が必要となるでしょう。
(3) 近似誤差とチューニング
先読みアプローチにおいて、先読みステップ数やモンテカルロシミュレーションの回数によっては、近似誤差が非近視眼的なアプローチから得られる利点を打ち消してしまう可能性があります。適切な先読みステップ数(ローリングホライズン)の選択は、問題に依存することが多く、事前のチューニングや、最適化の進行状況に応じた動的な調整が必要になる場合があります。このチューニング自体にもコストがかかる可能性があることに留意が必要です。
(4) MI特有の課題との組み合わせ
さらに、実際のMI応用では、実験ノイズ、再現性の問題、複数の目的(性能、コスト、安定性など)を同時に最適化したい多目的最適化の要求など、限定予算以外にも考慮すべき課題が存在します。これらのLimited-budget ベイズ最適化アプローチを、これらのMI特有の課題とどのように組み合わせて効果的に活用していくかについても、今後の検討が必要です。
結論:限られた試行機会を最大限に活かすために
本記事で議論した Limited-budget ベイズ最適化戦略(探索空間の絞り込み、および先読みアプローチ/非近視眼的ベイズ最適化)は、評価予算が限られているという厳しい制約下のシナリオにおいて、従来のベイズ最適化を凌駕する有望な改善をもたらす可能性を秘めています。これらの手法は、貴重な評価機会をより戦略的に活用し、少ない試行回数でより良い解を発見することを目指しています。
しかしながら、これらのアプローチは同時により高度な複雑さを導入し、実世界の最適化問題に適用する際には慎重に考慮すべき潜在的な課題も伴います。計算コストの増加、近似誤差の影響、問題設定に合わせたチューニングの必要性、そして高次元問題へのスケーラビリティなどは、導入前に十分に検討すべき点です。
Limited-budgetベイズ最適化は、特に材料科学、創薬、高コストシミュレーション、ロボット工学など、評価コストがボトルネックとなる多くの分野において、その重要性を増していくと考えられます。今後、よりスケーラブルで、計算効率が高く、かつロバストな限定予算BO手法の開発が進むことで、これまで困難であった問題に対する最適化の可能性がさらに広がることが期待されます。特定の問題の特性と利用可能なリソースを考慮し、これらの先進的な手法の利点とリスクを比較検討した上で、適切なアプローチを選択することが求められます。
参考文献
- Nomura, M., & Abe, K. (2019). A simple heuristic for Bayesian optimization with a low budget. arXiv preprint arXiv:1911.07790 https://doi.org/10.48550/arXiv.1911.07790
- Lam, R., Willcox, K., & Wolpert, D. H. (2016). Bayesian optimization with a finite budget: An approximate dynamic programming approach. Advances in Neural Information Processing Systems, 29. https://proceedings.neurips.cc/paper/2016/file/5ea1649a31336092c05438df996a3e59-Paper.pdf
- González, J., Osborne, M., & Lawrence, N. (2016, May). GLASSES: Relieving the myopia of Bayesian optimisation. In Artificial Intelligence and Statistics (pp. 790-799). PMLR. https://proceedings.mlr.press/v51/gonzalez16b.pdf
- Wu, J., & Frazier, P. (2019). Practical two-step lookahead Bayesian optimization. Advances in neural information processing systems, 32. https://proceedings.neurips.cc/paper/2019/file/2e6d9c6052e99fcdfa61d9b9da273ca2-Paper.pdf
- Wu, J., & Frazier, P. (2016). The parallel knowledge gradient method for batch Bayesian optimization. Advances in neural information processing systems, 29. https://proceedings.neurips.cc/paper_files/paper/2016/file/18d10dc6e666eab6de9215ae5b3d54df-Paper.pdf
- Lee, E., Eriksson, D., Bindel, D., Cheng, B., & Mccourt, M. (2020, August). Efficient rollout strategies for Bayesian optimization. In Conference on Uncertainty in Artificial Intelligence (pp. 260-269). PMLR. https://www.auai.org/uai2020/proceedings/124_main_paper.pdf