論文の概要: Merge Kernel for Bayesian Optimization on Permutation Space
- arxiv url: http://arxiv.org/abs/2507.13263v1
- Date: Thu, 17 Jul 2025 16:12:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-18 20:10:24.573377
- Title: Merge Kernel for Bayesian Optimization on Permutation Space
- Title（参考訳）: 置換空間上のベイズ最適化のためのマージカーネル
- Authors: Zikai Xie, Linjiang Chen,
- Abstract要約: ソートアルゴリズムに基づく置換空間上でのカーネル関数生成のための新しいフレームワークを提案する。
提案したカーネルは、様々な置換最適化ベンチマークで最先端のMallowsカーネルを一貫して上回っている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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（参考訳）: ベイズ最適化(BO)アルゴリズムはブラックボックス最適化問題の標準ツールである。
置換空間に対する現在の最先端のBOアプローチは、任意のペア比較を明示的に列挙するMallows kernel-an $\Omega(n^2)$表現に依存している。
Mallowsカーネルとペア比較の密接な関係に着想を得て、ソートアルゴリズムに基づく置換空間上でカーネル関数を生成する新しいフレームワークを提案する。
このフレームワーク内では、Mallowsカーネルはバブルソートから派生した特別なインスタンスと見なすことができる。
さらに、マージソートから構築された \textbf{Merge Kernel} を導入し、最小の複雑性を達成するために二次複雑性を$\Theta(n\log n)$に置き換える。
結果として得られる特徴ベクトルは著しく短く、線形時間で計算できるが、それでも意味のある置換距離を効率的に捉えることができる。
コンパクト性を犠牲にすることなく、ロバスト性や右不変性を向上するために、(1)絶対要素変位を集約し、大域的なずれ信号を供給するシフトヒストグラム、(2)置換全体の2つのハーフをまたいで要素を並べて選択した長距離比較を符号化するスプリットペアライン、(3)近傍の目的に影響を及ぼす局所的な順序パターンを要約するスライドウインドウモチーフの3つの軽量タスク非依存記述器を組み込んだ。
我々の経験的評価は,提案したカーネルが様々な置換最適化ベンチマークで最先端のMallowsカーネルより一貫して優れていることを示す。
その結果、マージ・ケルネルは置換空間におけるベイズ最適化に対してよりコンパクトで効果的な解を提供することを確認した。
関連論文リスト
- Faster Convergence with Multiway Preferences [99.68922143784306]
本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。
本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
論文 参考訳（メタデータ） (2023-12-19T01:52:13Z) - Self-concordant Smoothing for Large-Scale Convex Composite Optimization [0.0]
2つの凸関数の和を最小化する自己協和スムージングの概念を導入し、そのうちの1つは滑らかであり、もう1つは非滑らかである。
本稿では, 近位ニュートンアルゴリズムであるProx-N-SCOREと近位一般化したガウスニュートンアルゴリズムであるProx-GGN-SCOREの2つのアルゴリズムの収束性を証明する。
論文 参考訳（メタデータ） (2023-09-04T19:47:04Z) - Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。
従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。
本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-15T04:57:37Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Local Sample-weighted Multiple Kernel Clustering with Consensus
Discriminative Graph [73.68184322526338]
マルチカーネルクラスタリング(MKC)は、ベースカーネルの集合から最適な情報融合を実現するためにコミットされる。
本稿では,新しい局所サンプル重み付きマルチカーネルクラスタリングモデルを提案する。
実験により, LSWMKCはより優れた局所多様体表現を有し, 既存のカーネルやグラフベースのクラスタリングアルゴリズムよりも優れていた。
論文 参考訳（メタデータ） (2022-07-05T05:00:38Z) - Tree ensemble kernels for Bayesian optimization with known constraints
over mixed-feature spaces [54.58348769621782]
木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。
ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。
我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
論文 参考訳（メタデータ） (2022-07-02T16:59:37Z) - Scalable First-Order Bayesian Optimization via Structured Automatic
Differentiation [4.061135251278187]
広い範囲のカーネルが構造化行列を生じさせ、勾配観測のための正確な$mathcalO(n2d)$Matrix-vector multiplyとヘッセン観測のための$mathcalO(n2d2)$を可能にした。
提案手法は,ほぼすべての標準カーネルに適用され,ニューラルネットワーク,放射基底関数ネットワーク,スペクトル混合カーネルなどの複雑なカーネルに自動的に拡張される。
論文 参考訳（メタデータ） (2022-06-16T17:59:48Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Kernel Clustering with Sigmoid-based Regularization for Efficient
Segmentation of Sequential Data [3.8326963933937885]
セグメント化は、データシーケンスを非線形で複雑な構造を持つ複数の重複しないセグメントに分割することを目的としている。
この問題を最適に解決するための一般的なカーネルは動的プログラミング(DP)である。
最適セグメンテーションを近似するために多くのアルゴリズムが提案されているが、それらの解の品質は保証されていない。
論文 参考訳（メタデータ） (2021-06-22T04:32:21Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Block majorization-minimization with diminishing radius for constrained nonsmooth nonconvex optimization [8.386501595252]
BMM(Block Majorization-minimativeization)は、制約付き非負のサロゲートに対する単純な反復アルゴリズムである。
BMMは,様々なアルゴリズムに対して,新しい一階最適度尺度を生成する。
また, BMM の収束率を向上させるために, 減衰半径の付加的利用が有効であることを示す。
論文 参考訳（メタデータ） (2020-12-07T07:53:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。