On the Structural (Dis)Agreement of Landscape Representations in Black-Box Optimization

技術的概要：ブラックボックス最適化におけるランドスケープ表現の構造的（不一致）合意

問題定義
ブラックボックス最適化における自動アルゴリズム選択（AAS）は、問題インスタンスをアルゴリズムのパフォーマンスにマッピングするために、ランドスケープ特徴表現に大きく依存している。従来の探索的ランドスケープ分析（ELA）特徴から深層学習に基づく埋め込み（DoE2Vec、DeepELA、TransOptAS など）に至るまで、さまざまな表現が存在するが、これらの異なる表現が問題空間の構造的編成についてどのように合意し、あるいは不一致を示すかについての理解は限られている。現在の研究は、一般化を検証するための十分に多様なベンチマークデータセットの不足と、既存の表現が基盤となるランドスケープ特性について補完的な情報を捉えているのか、それとも冗長な情報を捉えているのかという不確実性という、2 つの主要な課題に直面している。具体的には、異なる表現が同一の問題セットを一貫した方法で編成しているのか、それとも幾何学的特性と意味論的特性をそれぞれ強調しているのかは、依然として不明である。

手法
著者らは、4 つの最先端のランドスケープ表現の構造的整合性と補完性を分析するための体系的な教師なし評価パイプラインを提案する：

1. ELA: 従来の低レベル統計特徴（インスタンスあたり 62 特徴）。
2. DoE2Vec: 32 次元の潜在ベクトルを生成する変分オートエンコーダ。
3. TransOptAS: アルゴリズムのパフォーマンス予測のために訓練された 50 次元の埋め込みを生成するトランスフォーマーベースのエンコーダ。
4. DeepELA: 関数変換に対して不変な 48 次元特徴を生成する自己教師ありトランスフォーマー。

データ生成:
標準的なベンチマークを超えた多様性を確保するため、本研究はMA-BBOBスイートを利用する。このデータセットは、552 組の異なる BBOB 問題クラスの線形結合によって生成された 8,280 の変換済み問題インスタンスで構成される。各組み合わせは、次元 $d=10$ のサイズ $50d$ のラテン超立方体サンプリングを用いて評価される。

実験手順:

1. クラスタリング: 各表現について、著者らは 5 つのクラスタリングアルゴリズム（凝集、K-Means、スペクトラル、ガウス混合、BIRCH）とハイパーパラメータ（クラスタ数 $k \in [5, 500]$）に対して広範なグリッド検索を実行した。各表現の最適構成は、シルエットスコアに基づいて選択された。
2. 表現内分析: 著者らは、問題インスタンスがクラスタ間でどのように分布するかを追跡するためのカバレッジ行列を構築した。これらの構造をホモジニティ（H）、完全性（C）、および**V-メジャー（V）**を用いて評価し、クラスタが真の問題クラスとどの程度整合しているかを測定した。
3. 表現間分析: 表現を比較するために、著者らはクラスタのベクトルベースの説明（各ベクトル要素は、特定のクラスタ内の特定の問題の頻度を表す）を導き出し、異なる表現のクラスタ間でコサイン類似度を計算した。これらの類似度スコアに階層的クラスタリングを適用し、構造的な整合性を特定した。
4. パフォーマンス整合性: 最後に、本研究は特徴空間のクラスタとアルゴリズムのパフォーマンスとの間の関係を分析した。差分進化（DE）と粒子群最適化（PSO）の変種からなるポートフォリオを用いて、著者らは各表現によって定義されたクラスタ内で、最良のパフォーマンスを示すアルゴリズム構成がどの程度一貫して選択されたかを測定した。

主要な結果
本研究は、単一の表現が支配的であるのではなく、それぞれが問題空間を根本的に異なる方法で編成し、ランドスケープの補完的な側面を捉えていることを明らかにしている：

• 幾何学的結束性（ELA と TransOptAS）: これらの表現は、コンパクトでよく分離された幾何学的構造を形成する。ELA は最高のシルエットスコア（0.3505）を達成し、TransOptAS がこれに続いた（0.2670）。しかし、両者とも低いホモジニティを示しており、クラスタが幾何学的に緊密である一方で、混合された問題タイプを含む傾向があることを意味している。
• 意味論的忠実度対断片化（DoE2Vec）: DoE2Vec は最高のホモジニティ（0.5612）と V-メジャー（0.5882）を達成し、真の問題の意味論との強い整合性を示した。しかし、多数のクラスタ（355）を生成し、シルエットスコアが最も低かった（0.1722）ため、特徴空間の過剰なセグメンテーションを示唆している。
• バランスの取れた視点（DeepELA）: DeepELA は、幾何学的分離と意味論的整合性のバランスを取った中間的な視点を提供したが、他の表現との類似性は中程度であった。
• 構造的な不一致: 表現間類似性のヒートマップは、TransOptAS が ELA と密接に整合する一方で、DoE2Vec は微細なクラスタリングのために大きく乖離していることを示した。4 つの表現は、同一の問題を著しく異なる方法で編成している。
• パフォーマンスのトレードオフ: アルゴリズムのパフォーマンス（DE と PSO）を分析した際、トレードオフが現れた。DoE2Vec はパフォーマンス選択において最高のホモジニティを示した（同じクラスタ内の問題は最良のアルゴリズムを共有する傾向がある）が、完全性は低かった（異なるクラスタ間で類似のアルゴリズムが選択された）。一方、TransOptAS は高い完全性を示した（類似のパフォーマンスを持つ問題をグループ化する）が、純度は低かった。単一の表現がアルゴリズムのパフォーマンス挙動を完全に捉えることはなかった。

意義と貢献
本論文の主要な貢献は、ランドスケープ表現は交換可能ではなく、同一の問題空間に対して異なる構造的視点をもたらすことを実証した点にある。

• 補完性: 本研究の結果は、ELA/TransOptAS が幾何学的結束を好み、DoE2Vec が意味論的純度を優先することを浮き彫りにしている。これは、単一の表現に依存すると問題ランドスケープの重要な側面を見逃す可能性があるため、堅牢なメタ学習システムを構築するには多視点分析が不可欠であることを示唆している。
• 選択への指針: 結果は、下流タスクへの指針を提供する：もしアルゴリズムの挙動が類似した問題をグループ化することが目的であれば、完全性の高い表現（TransOptAS など）が好ましい可能性がある。一方、特定の問題タイプを分離することが目的であれば、ホモジニティの高い表現（DoE2Vec など）がより適している可能性がある。
• 限界: 著者らは、本研究が単一のベンチマークスイート（MA-BBOB）と特定のアルゴリズムファミリー（DE と PSO）に限定されていることを指摘している。しかし、提案された実証的枠組みは、他のベンチマークや最適化ドメインに拡張できるように設計されている。

結論として、本研究は「普遍的」なランドスケープ表現の存在を否定する。その代わり、自動アルゴリズム選択とメタ学習において、それらの補完的な強みを活用するために、複数の表現を統合することを提唱している。