Abstract
Bayesian Optimization (BO) algorithm is a standard tool for black-box optimization problems. The current state-of-the-art BO approach for permutation spaces relies on the Mallows kernel-an $\Omega(n^2)$ representation that explicitly enumerates every pairwise comparison. Inspired by the close relationship between the Mallows kernel and pairwise comparison, we propose a novel framework for generating kernel functions on permutation space based on sorting algorithms. Within this framework, the Mallows kernel can be viewed as a special instance derived from bubble sort. Further, we introduce the \textbf{Merge Kernel} constructed from merge sort, which replaces the quadratic complexity with $\Theta(n\log n)$ to achieve the lowest possible complexity. The resulting feature vector is significantly shorter, can be computed in linearithmic time, yet still efficiently captures meaningful permutation distances. To boost robustness and right-invariance without sacrificing compactness, we further incorporate three lightweight, task-agnostic descriptors: (1) a shift histogram, which aggregates absolute element displacements and supplies a global misplacement signal; (2) a split-pair line, which encodes selected long-range comparisons by aligning elements across the two halves of the whole permutation; and (3) sliding-window motifs, which summarize local order patterns that influence near-neighbor objectives. Our empirical evaluation demonstrates that the proposed kernel consistently outperforms the state-of-the-art Mallows kernel across various permutation optimization benchmarks. Results confirm that the Merge Kernel provides a more compact yet more effective solution for Bayesian optimization in permutation space.
Abstract (translated)
贝叶斯优化（BO）算法是解决黑箱优化问题的标准工具。当前针对排列空间的最优贝叶斯优化方法依赖于Mallows核，这是一种显式枚举每一对比较关系的$\Omega(n^2)$表示形式。受Mallows核与成对比较之间密切关系的启发，我们提出了一种基于排序算法生成排列空间上核函数的新框架。在此框架内，Mallows核可以被视为一种特殊实例，源自冒泡排序算法。进一步地，我们引入了由归并排序构造的\textbf{Merge Kernel}，它将二次复杂度替换为$\Theta(n \log n)$以实现最低可能的计算复杂度。生成的结果特征向量显著缩短，并可以在对数线性时间内计算完成，同时依然能够高效捕捉有意义的排列距离。 为了增强稳健性和右不变性而不牺牲紧凑性，我们进一步整合了三种轻量级、任务无关的描述符：（1）位移直方图，它聚合绝对元素位移并提供全局错置信号；（2）分裂对线，通过将整个排列的两半部分中的元素对齐来编码选定的长距离比较；以及（3）滑动窗口模式，该模式总结影响最近邻目标的地方顺序模式。我们的实证评估表明，所提出的核函数在各种排列优化基准测试中始终优于当前最先进的Mallows核函数。结果证实Merge Kernel为排列空间中的贝叶斯优化提供了一种更为紧凑且更有效的解决方案。 这一研究不仅展示了如何通过借鉴经典排序算法的特性来设计高效的核函数，而且还提高了我们对如何结合不同类型的描述符以增强机器学习模型在复杂结构化数据上的性能的理解。
URL
https://arxiv.org/abs/2507.13263
