本論文は、順列空間におけるブラックボックス最適化問題に対するベイジアン最適化（BO）アルゴリズムを扱う。従来の最先端BO技術は、すべての双対比較を明示的に列挙する$\Omega(n^2)$複雑度のMallowsカーネルに依存している。本稿では、ソートアルゴリズムに基づいて置換空間にカーネル関数を生成する新しいフレームワークを提案します。このフレームワーク内では、Mallowsカーネルはバブルソートから派生した特別なケースと見なすことができます。さらに、マージアラインメントから構成されたMergeカーネルを提示し、二次複雑度を$ \ Theta（n \ log n）$に下げて最低複雑度を達成します。結果として得られる特徴ベクトルははるかに短くなり、線形対数時間で計算することができるが、依然として意味のある順列距離を効率的に捕捉する。堅牢性と右辺の不変性を向上させながら圧縮性を維持するために、3つの軽量の作業独立技術者（shift histogram、split-pair line、sliding-window motifs）をさらに統合します。実験の結果、提案されたカーネルが様々な順列最適化ベンチマークで既存の最先端のMallowsカーネルを一貫して凌駕することを示した。 Mergeカーネルが順列空間でのベイジアン最適化に対してより圧縮的で効果的なソリューションを提供することを確認してください。
