Stage-dependent integer-binary encoding in factorization-machine black-box optimization

技術要約：因子分解マシン・ブラックボックス最適化におけるステージ依存型整数・バイナリ符号化

問題提起
ブラックボックス最適化（BBO）は、目的関数に明示的な解析形式がなく、評価コストが高い問題を扱う。Factorization Machine with Quadratic-optimization Annealing (FMQA) は、因子分解マシン（FM）を用いてサロゲートモデルを構築し、イジングマシンを用いてこれを最適化する、有力なBBO手法である。FMQAの重要な構成要素は、整数または連続変数を、二次無制約バイナリ最適化（QUBO）モデルとして定式化するために、整数・バイナリ符号化（例：ワンホット、ドメインウォール、またはバイナリ符号化）を介してバイナリ変数へと変換することである。

従来のFMQAは、機械学習ステージ（サロゲートモデルの構築）と解探索ステージ（イジングマシンによる最適化）の両方において、単一の整数・バイナリ符号化手法を採用している。しかし、先行研究ではトレードオフが存在することが示唆されている。すなわち、ドメインウォール符号化はイジングマシンにおける解探索性能において優れた結果をもたらすことが多い一方で、ワンホット符号化はFMQAのプロセス全体において、より低い目的関数値を生み出す傾向がある。この相違は、学習に適した符号化と、そのランドスケープの探索に適した符号化が異なる可能性を示唆している。単一の符号化を固定する従来の手法は、FMとイジングマシンのそれぞれが持つ独自の能力を十分に活用できていない可能性がある。

手法
著者らは、学習ステージと解探索ステージで異なる整数・バイナリ符号化を用いる、ステージ依存型のFMQAフレームワークを提案している。本アプローチの核となるのは以下の通りである：

1. デュアル符号化戦略： 本フレームワークは、学習に適した符号化（具体的には、提案手法「OhDw」におけるワンホット符号化）を用いてFMサロゲートモデルを学習させ、その後、最適化を行うイジングマシンのために、探索に適した別の符号化（具体的にはドメインウォール符号化）へと変換する。
2. QUBO行列の変換： この切り替えを可能にするため、著者らはワンホット符号化とドメインウォール符号化の間のQUBO行列の数学的な変換公式を導出した。これらの公式は、加法的定数を除いて、サロゲートの目的関数ランドスケープが実行可能な整数状態において保持されることを保証する。
   • ワンホットからドメインウォールへの変換には、特定の総和関係（式18–20）を用いてQUBO行列 $Q^{(oh)}$ の対角項および非対角項を $Q^{(dw)}$ へ変換する工程が含まれる。
   • 逆変換（ドメインウォールからワンホット）も導出されている（式22–24）。
   • これらの相互変換の計算複雑性は、$O(N^2q^2)$（$N$ は入力次元、$q$ は離散化レベル数）であると確立されている。
3. アルゴリズムのワークフロー：
   • 学習ステージ： ワンホット符号化を用いてエンコードされた入出力データに基づき、FMを学習させる。
   • 変換： 学習されたサロゲートモデル（QUBO行列として表現される）を、ワンホットからドメインウォール符号化へと変換する。
   • 探索ステージ： ドメインウォール符号化の制約が付加された変換後のQUBOを、イジングマシン（Fixstars Amplify Annealing Engine）を用いて最適化し、候補解を見つける。
   • 評価： 解をデコードし、真のブラックボックス関数に対して評価を行い、次のイテレーションのための学習データセットに追加する。

主な貢献

1. フレームワークの提案： プロセス全体を通じて単一の符号化を固定するのではなく、学習ステージと探索ステージの間で符号化の選択を分離するFMQAフレームワークを導入した。
2. 理論的導出： 学習されたモデルの忠実度を損なうことなく、サロゲートの目的関数ランドスケープを保持しながら、ワンホットとドメインウォールのQUBO行列間での相互変換公式を導出した。
3. 経験的分解： 整数・バイナリ符号化の影響を、学習ステージと解探索ステージの寄与へと数値的に分解し、それぞれの性能への影響を個別に評価した。

実験結果
提案手法は、多峰性のベンチマーク問題であるラストリギン関数を用い、入力次元 $N \in \{2, 5\}$ および離散化レベル $q \in \{61, 301\}$ において評価された。提案手法「OhDw」（学習にワンホット、探索にドメインウォール）の性能を、従来の単一符号化バリアント（Oh, Dw, Bi）およびベイズ最適化（BO）と比較した。

• 学習ステージにおける符号化の支配性： すべての条件下において、学習ステージで使用された符号化が、最適化性能を決定付ける支配的な要因であった。ドメインウォールまたはバイナリ符号化を用いて学習を行ったものと比較して、ワンホット符号化を用いて学習を行った手法（OhおよびOhDw）は、一貫して低い残留誤差を達成した。
• ステージ依存の利点： 探索ステージへのドメインウォール符号化への切り替えによる恩恵は、条件に依存していた：
  • $N=5$ かつ $q=301$（より細かい離散化、より大きな探索空間）の場合、OhDw法は、Oh法（ワンホットのみ）と比較して、より低い残留誤差と、グローバル最適解に近い解を達成した。
  • $N=5$ かつ $q=61$ の場合、Oh法がわずかにOhDwを上回った。
  • $N=2$ の場合、OhとOhDwの間で有意な性能差は見られなかった。
• 探索の安定性： 解探索ステージの分析により、ドメインウォール符号化はイジングマシン内での実行可能状態間の安定した遷移を可能にする一方で、ワンホット符号化は制約違反の状態を経由する必要があり、探索の安定性を低下させる可能性があることが示された。

意義と主張
本論文は、整数・バイナリ符号化の選択は単なる表現上の選択ではなく、FMQAの学習ステージと解探索ステージにおいて異なる役割を果たす設計要素であると主張している。主要な知見は、学習ステージにおけるワンホット符号化が、正確なサロゲートモデルを構築する優れた能力に起因して、最適化性能を駆動する主要な要因であることである。しかし、本研究は、ステージ依存型の符号化（具体的には、学習にワンホット、探索にドメインウォールを組み合わせる手法）を採用することで、入力次元が大きく離散化が細かい、より複雑な探索空間を持つシナリオにおいて、さらなる改善が得られることを示している。

著者らは、OhDw法は有望ではあるものの、その汎用性を確認するには、より多様なベンチマーク関数や実世界の設計最適化問題におけるさらなる検証が必要であると結論付けている。また、ペナルティ係数への感度やQUBOの密度差に関する系統的な分析も、今後の課題として挙げられている。