Black-box optimization using factorization and Ising machines

本論文は、大規模なブラックボックス最適化問題を多様な分野で効率的に解決するために因子分解機械を代理モデルとして、およびイジングマシンを活用する因子分解機械量子アニーリング（FMQA）アルゴリズムをレビューし、その即時導入を促進するために必要なツールと応用例を提供する。

要約

完璧なケーキのレシピを見つけようとしていると想像してください。しかし、料理本も、材料のリストも、オーブンの仕組みについての知識もありません。できるのは、ケーキを焼き、味見をし、スコアを得ることだけです。ケーキがパサついていれば低いスコア、美味しくできれば高いスコアが得られます。これが科学者たちが「ブラックボックス最適化」と呼ぶものです。あなたは最良の「入力」（材料）を探して最良の「出力」（味）を得ようとしていますが、その機械（オーブン）は謎に包まれています。

問題は、考えられる材料の組み合わせが数十億通りもあることです。一つずつ試そうとすれば、永遠にかかってしまいます。次の最良の配合を推測しようとしても、ルールがわからないため困難です。

この論文は、この謎を解決するための巧妙な新しい方法を導入します。それは、「スマートな推測マシン」（ファクター化マシンと呼ばれる）と「超高速検索エンジン」（イジングマシンと呼ばれる）という二つの主要なツールを用いるものです。

以下に、その仕組みをステップバイステップで説明します。

1. スマートな推測マシン（サロゲート）

毎回実際のケーキを焼いてレシピを検証する代わりに、オーブンの「デジタルツイン」を構築します。いくつかのケーキを焼き、その結果を記録し、コンピュータプログラム（ファクター化マシン）に、過去のデータに基づいて新しいレシピがどれほど良いかを予測させるように教えます。

• 比喩: これは、100 個のケーキを味見した料理評論家のようなものです。「卵を 2 個使い、砂糖を 3 カップ使う」と伝えれば、実際に焼かなくてもスコアを推測できます。
• 難点: 賢い評論家がいたとしても、数十億もの選択肢の中から絶対的な最良のレシピを見つけるのは、依然として巨大なパズルです。材料が離散的（「卵を 1 個加える」または「卵を 2 個加える」であり、「卵を 1.5 個加える」ではない）である場合、可能性の数は爆発的に増大します。

2. 超高速検索エンジン（イジングマシン）

ここで論文は興味深くなります。著者たちは、「スマートな推測マシン」を、イジングマシンと呼ばれる特殊なタイプのコンピュータが完璧に理解できる言語に変換できることに気づきました。

• 比喩: イジングマシンは、巨大で超高速な迷路解き機だと想像してください。通常、これらのマシンは配送トラックの最短経路を見つけるや、磁石の配置などの複雑なパズルを解くために使われます。
• マジックトリック: 著者たちは、「スマートな推測マシン」の予測問題を、イジングマシンが瞬時に解けるような迷路に変換する方法を見つけました。コンピュータがゆっくりと推測と検証を繰り返す代わりに、イジングマシンは「スマートな評論家」が最良だと考える材料の組み合わせを瞬時に見つけ出します。

3. 「FMQA」アルゴリズム

この一連のプロセスを、論文ではFMQA（Quadratic-optimization Annealing を伴うファクター化マシン）と呼んでいます。

• 流れ:
  1. いくつかのケーキを焼く（データを収集する）。
  2. スマートな評論家（ファクター化マシン）を訓練する。
  3. 超高速検索エンジン（イジングマシン）に、評論家が想像しうる最良のレシピを見つけるよう依頼する。
  4. その特定のレシピを焼き、実際のスコアを得る。
  5. その新しいスコアを評論家にフィードバックし、繰り返す。

なぜこれが重要なのか？

通常、膨大なリストから最良のレシピを見つけるのは非常に時間がかかります。この論文は、「評論家」と「超高速検索エンジン」という特定の組み合わせを使用することで、選択肢のリストが巨大であっても、以前よりもはるかに速く優れた解決策を見つけられることを示しています。

論文からの実世界の例

著者たちは理論について語るだけでなく、科学や工学における実際の「レシピ」でこれをテストしました。

• 超材料の設計: 冷却用途のための「メタ材料」（特殊な性質を持つ人工材料）を設計するために使用しました。彼らは異なる材料の小さな棒を配置する必要がありました。このアルゴリズムは、ランダムな推測よりも優れたパターンを見つけ出しました。
• より良い層の構築: 光は通すが熱は遮断する窓用のフィルム層を設計しました。アルゴリズムは、材料を積む完璧な順序を突き止めました。
• 信号機の改善: 信号機をパズルとして扱いました。目標は、都市を車でより速く移動させることでした。アルゴリズムは赤と緑の信号のタイミングを調整し、標準的な設定よりもはるかにスムーズな流れを見つけ出しました。
• 飛行機の翼の設計: 翼の形状を微調整し、より効率的に飛行させるようにしました（揚力を増やし、抗力を減らす）。
• 新薬（ペプチド）の創出: 細菌を殺すが人間の細胞には害を与えないタンパク質の短い鎖（ペプチド）を設計しました。これは干し草の山から針を見つけるようなものですが、このアルゴリズムは実験室でテストされた際に実際に機能するいくつかのペプチドを見つけ出しました。

結論

この論文は、特定の種類の AI（ファクター化マシン）と専用ハードウェア（イジングマシン）を組み合わせることで、科学者たちが「ブラックボックス」の問題を以前よりもはるかに速く解決できることを主張しています。これは、探偵に、最も有望な手がかりを瞬時に浮き彫りにする超強力な拡大鏡を与えるようなもので、以前は解くことが難しすぎた犯罪（または材料設計）を解決することを可能にします。

著者たちは、他の科学者たちが自分たちの難しいパズルを解決するためにこの「スマートな評論家＋超高速検索エンジン」の組み合わせを使用できるよう、無料のソフトウェアツールも公開しています。

技術概要

タムラらによる論文「Black-box optimization using factorization and Ising machines」の詳細な技術的サマリーを以下に示す。

1. 問題定義

**ブラックボックス最適化（BBO）**は、材料設計や創薬から機械学習のハイパーパラメータ調整に至るまで、幅広い分野における重要な課題である。BBO において、目的関数 $y(x)$ は内部の関数形式や勾配が未知の「ブラックボックス」であり、入力 - 出力ペアのみが利用可能である。

• 課題: ベイズ最適化（BO）などの従来の BBO 手法は、最適な入力を予測するために代理モデル（例えばガウス過程）に依存している。しかし、入力空間が離散的、高次元、または組み合わせ的である場合、次の入力を選択するための基準である獲得関数の最適化は、計算的に困難（非現実的）となる。
• ボトルネック: 候補入力の数が増加するにつれ、網羅的探索は不可能（NP 困難）となり、勾配ベースの手法は離散変数に対して機能しない。既存の手法は、大規模な離散探索空間を効率的に探索して大域的最適解を見つけることに苦慮している。

2. 手法：FMQA アルゴリズム

本論文は、**FMQA（Factorization Machine with Quadratic-optimization Annealing）**アルゴリズムを提案する。このアプローチは、特定の機械学習代理モデルとイジングマシン（IM）を組み合わせ、獲得関数の最適化を効率的に解決する。

A. 代理モデル：ファクトリゼーションマシン（FM）

FMQA は、ガウス過程の代わりに**ファクトリゼーションマシン（FM）**を代理モデルとして使用する。

• 構造: FM は、出力 $\bar{y}(x)$ を線形項とペアごとの相互作用項の和としてモデル化する。
  $$\bar{y}(x) = w_0 + \sum w_i x_i + \sum \sum \langle v_i, v_j \rangle x_i x_j$$
• 利点: FM は直接**二次制約なし二値最適化（QUBO）**モデル（またはイジングハミルトニアン）に変換可能である。これにより、代理モデル自体を IM を用いた最適化問題として解くことができる。
• 学習: FM は、特徴量数 $N$ と潜在次元 $K$ に対して線形複雑度 $O(NK)$ の勾配降下法を用いて効率的に学習される。

B. 最適化エンジン：イジングマシン（IM）

核心的な革新は、FM の獲得関数（または負の予測値の最小化）を最大化する入力 $x$ を発見するために IM を使用することである。

• ハードウェア/ソフトウェア: このアルゴリズムは、使用する特定の IM に依存しない。以下をサポートする。
  • 量子アニーラ: 例：D-Wave システム。
  • デジタルアニーラ: 例：富士通デジタルアニーラ。
  • シミュレーテッドアニーリングエンジン: 例：Fixstars Amplify Annealing Engine（GPU ベース）。
• プロセス: FM を QUBO に変換 $\rightarrow$ IM によって解き、最適な二値ベクトルを特定 $\rightarrow$ 元の入力空間に復号する。

C. 非二値入力の処理（エンコーディング戦略）

IM は二値変数上で動作するため、本論文は一般的な最適化問題に対するエンコーディング手法を詳述している。

1. 二値変数: 直接マッピング（エンコーディング不要）。
2. 整数変数:
   • 二進エンコーディング: 整数を 2 のべき乗の和として表現する。
   • ワンホットエンコーディング: $N$ ビットの中で単一の '1' として整数を表現する（$\sum x_i = 1$ という制約が必要）。
   • ドメインウォールエンコーディング: ワンホットに比べてビット数を削減できる、整数に対するより効率的なエンコーディング。
3. 複雑な構造（グラフ、文字列、画像）:
   • **二値変分オートエンコーダ（bVAE）**を使用する。
   • bVAE は、複雑な入力（例：分子の SMILES 文字列、画像）を二値変数の潜在空間にエンコードする。
   • FM はこの潜在空間上で学習される。IM は潜在二値ベクトルを最適化し、それを元の構造に復号する。

3. 主な貢献

1. アルゴリズム的枠組み: QUBO 互換の FM 代理モデルを介して BBO を組み合わせ最適化ハードウェア（IM）に橋渡しする方法を示し、FMQA アルゴリズムを形式化した。
2. スケーラビリティ: 獲得関数の最適化の難しさにより従来の BO が失敗する大規模な離散最適化問題（数千ビットまで）を FMQA が処理できることを示した。
3. ソフトウェアエコシステム: 技術を民主化するためのオープンソースツールを導入した。
   • オリジナル FMQA パッケージ: 基本的な実装のための Python ライブラリ。
   • Amplify-BBOpt: Fixstars Amplify SDK と統合された専用ライブラリ。ユーザーが手動で QUBO 式を構成することなく、連続変数や制約（例：ワンホット）を定義できる。
4. 包括的なベンチマーク: 単純な二値問題を超えた汎用性を証明するため、多様な分野でアプローチを検証した。

4. 結果と応用例

本論文は、物理学、化学、材料科学、社会科学における成功事例をレビューしている。

• 制約なし二値最適化:

  • メタマテリアル設計: D-Wave 2000Q を用いて放射冷却構造（24〜60 ビット）を最適化し、ランダム探索よりも優れた構造を迅速に見出した。
  • 層状材料: 高性能な透明放射冷却フィルム（最大 48 ビット）と広角スペクトルフィルタを設計し、記録的な性能を持つ 10 層材料の製造に成功した。
  • ポリマー設計: 熱伝導率のためのブロック共重合体を最適化。
  • 特徴量選択: ポリマーの機械的特性を予測するための最適な特徴量サブセットを選択し、LASSO を上回った。

• 制約付き二値最適化:

  • 磁性トンネル接合（MTJ）: 特定のイオンの数に関する厳格な制約（例：Mg と Ge がそれぞれ正確に 5 つ）を伴う原子配列を、QUBO 内のペナルティ項を用いて最適化。
  • 分子配置: 分極率のためのペリレン分子内の原子配置を最適化。
  • 共振回避: 回路基板の取付穴の位置を最適化し、固有周波数を最大化。

• 整数変数問題:

  • フォトニック結晶レーザー: 出力パワーとビーム品質のための連続構造パラメータ（44 ビットに離散化）を最適化し、粒子群最適化（PSO）や遺伝的アルゴリズム（GA）を上回った。
  • 翼形状最適化: 揚抗比を最大化する翼型（100 ビット）を最適化し、ランダム探索に対して 17% の改善を達成。
  • 交通信号制御: 都市シミュレーションにおける平均車速を最大化するため、960 個の二値変数（16 の交差点を表す）を最適化。
  • 車体設計: 18 の制約を持つ車体構造の多目的ベンチマークを解決し、NSGA-II よりも少ない関数評価数（900 対 30,000）で優れたパレート解を達成。

• 複雑な構造（bVAE）:

  • 熱放射体: 500 ビットの潜在空間を用いて、熱光電変換のための 2 次元トポロジカル形状を最適化。
  • 分子設計: 300 ビットの潜在空間を用いて、複数の特性（LogP、QED など）を持つドラッグライクな分子（SMILES 文字列）を最適化。
  • ペプチド設計: 抗菌性と非溶血性のペプチドに対する多目的最適化を行い、2 つの新しいペプチドの合成と検証に成功。

5. 意義と展望

• IM のためのキーテクノロジー: 本論文は、FMQA をイジングマシンの「キラーアプリケーション」として位置づけ、以前は解決不可能だった現実世界の BBO 問題を解決するための実用的なエンドツーエンドのワークフローを提供している。
• 速度と効率: 獲得関数の最適化を専用ハードウェア（IM）にオフロードすることで、FMQA は離散空間における大域的最適解を見つけるために必要な計算時間を大幅に削減する。
• 将来の方向性:
  • 量子優位性: 現在、量子アニーラやデジタルアニーラを使用しているが、この枠組みは量子ビット数が増加するにつれて、ゲートベースの量子コンピュータ（QAOA を使用）の準備が整っている。
  • 自律実験室: 著者らは、材料発見や創薬を加速するため、FMQA を自動化実験システムと統合することを提案している。
  • スケーラビリティ: 今後の研究では、より大きなバッチサイズを処理し、予測精度と IM の性能をさらに向上させる高次代理モデル（HUBO）の開発を目指す。

結論として、本論文は、機械学習の代理モデルと組み合わせ最適化ハードウェアの間のギャップを効果的に埋める、堅牢で汎用性が高く、極めて効率的なブラックボックス最適化の枠組みとして FMQA を確立している。