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