論文の概要: Stitching Inner Product and Euclidean Metrics for Topology-aware Maximum Inner Product Search
- arxiv url: http://arxiv.org/abs/2504.14861v1
- Date: Mon, 21 Apr 2025 05:01:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-29 19:33:31.5416
- Title: Stitching Inner Product and Euclidean Metrics for Topology-aware Maximum Inner Product Search
- Title（参考訳）: トポロジーを考慮した内積探索のための内積とユークリッド計量
- Authors: Tingyang Chen, Cong Fu, Xiangyu Ke, Yunjun Gao, Yabo Ni, Anxiang Zeng,
- Abstract要約: 我々は、Metric-Amphibious Graph(MAG)と呼ばれる新しいグラフベースのインデックスと、それに対応する検索アルゴリズムAdaptive Navigation with Metric Switch(ANMS)を導入する。
これらの知見に基づいて,Metric-Amphibious Graph (MAG) とそれに対応する検索アルゴリズムAdaptive Navigation with Metric Switch (ANMS) を導入した。
- 参考スコア（独自算出の注目度）: 21.295432955733197
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Maximum Inner Product Search (MIPS) is a fundamental challenge in machine learning and information retrieval, particularly in high-dimensional data applications. Existing approaches to MIPS either rely solely on Inner Product (IP) similarity, which faces issues with local optima and redundant computations, or reduce the MIPS problem to the Nearest Neighbor Search under the Euclidean metric via space projection, leading to topology destruction and information loss. Despite the divergence of the two paradigms, we argue that there is no inherent binary opposition between IP and Euclidean metrics. By stitching IP and Euclidean in the design of indexing and search algorithms, we can significantly enhance MIPS performance. Specifically, this paper explores the theoretical and empirical connections between these two metrics from the MIPS perspective. Our investigation, grounded in graph-based search, reveals that different indexing and search strategies offer distinct advantages for MIPS, depending on the underlying data topology. Building on these insights, we introduce a novel graph-based index called Metric-Amphibious Graph (MAG) and a corresponding search algorithm, Adaptive Navigation with Metric Switch (ANMS). To facilitate parameter tuning for optimal performance, we identify three statistical indicators that capture essential data topology properties and correlate strongly with parameter tuning. Extensive experiments on 12 real-world datasets demonstrate that MAG outperforms existing state-of-the-art methods, achieving up to 4x search speedup while maintaining adaptability and scalability.
- Abstract（参考訳）: 最大内部製品探索(MIPS)は、特に高次元データアプリケーションにおいて、機械学習と情報検索において基本的な課題である。
既存のMIPSのアプローチは内積(IP)の類似性のみに依存しており、局所的な最適化や冗長な計算の問題に直面している。
2つのパラダイムの相違にもかかわらず、我々は、IPとユークリッドのメトリクスの間に固有の二項対立は存在しないと論じている。
インデックス化と検索アルゴリズムの設計において,IPとユークリッドを縫合することにより,MIPSの性能を大幅に向上させることができる。
具体的には,この2つの指標間の理論的および経験的関係をMIPSの観点から考察する。
グラフベースの検索を基盤とした調査の結果,データトポロジによって異なるインデックス化と検索戦略がMIPSに明確な優位性をもたらすことが明らかとなった。
これらの知見に基づいて,新しいグラフベースインデックスである Metric-Amphibious Graph (MAG) と,それに対応する検索アルゴリズム Adaptive Navigation with Metric Switch (ANMS) を導入する。
パラメータチューニングを最適化するために,本質的なデータトポロジ特性を捕捉し,パラメータチューニングと強く相関する3つの統計指標を同定する。
12の実世界のデータセットに対する大規模な実験により、MAGは既存の最先端の手法よりも優れており、適応性とスケーラビリティを維持しながら、最大4倍の検索スピードアップを実現している。
関連論文リスト
- Retrieval with Learned Similarities [2.729516456192901]
最先端の検索アルゴリズムは、学習された類似点に移行した。
そこで本研究では,Mixture-of-Logits (MoL) を実証的に実現し,多様な検索シナリオにおいて優れた性能が得られることを示す。
論文 参考訳（メタデータ） (2024-07-22T08:19:34Z) - The Impacts of Data, Ordering, and Intrinsic Dimensionality on Recall in Hierarchical Navigable Small Worlds [0.09208007322096533]
調査は、HNSWがデータセットのスペクトルにわたって有効であることに焦点を当てている。
我々は、KN(K Nearest Neighbours)探索と比較して、近似HNSW探索のリコールが、ベクトル空間の固有次元と結びついていることを発見した。
一般的なベンチマークデータセットをKNNの代わりにHNSWで実行することで、いくつかのモデルではランキングを最大3ポジションシフトすることができる。
論文 参考訳（メタデータ） (2024-05-28T04:16:43Z) - Minimally Supervised Learning using Topological Projections in
Self-Organizing Maps [55.31182147885694]
自己組織化マップ(SOM)におけるトポロジカルプロジェクションに基づく半教師付き学習手法を提案する。
提案手法は,まずラベル付きデータ上でSOMを訓練し,最小限のラベル付きデータポイントをキーベストマッチングユニット(BMU)に割り当てる。
提案した最小教師付きモデルが従来の回帰手法を大幅に上回ることを示す。
論文 参考訳（メタデータ） (2024-01-12T22:51:48Z) - Efficient Architecture Search via Bi-level Data Pruning [70.29970746807882]
この研究は、DARTSの双方向最適化におけるデータセット特性の重要な役割を探求する先駆者となった。
我々は、スーパーネット予測力学を計量として活用する新しいプログレッシブデータプルーニング戦略を導入する。
NAS-Bench-201サーチスペース、DARTSサーチスペース、MobileNetのようなサーチスペースに関する総合的な評価は、BDPがサーチコストを50%以上削減することを検証する。
論文 参考訳（メタデータ） (2023-12-21T02:48:44Z) - Maximize to Explore: One Objective Function Fusing Estimation, Planning,
and Exploration [87.53543137162488]
我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。
textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。
様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
論文 参考訳（メタデータ） (2023-05-29T17:25:26Z) - Towards Meta-learned Algorithm Selection using Implicit Fidelity
Information [13.750624267664156]
IMFASは、計算コストの低い任意のメタ機能によって容易に豊かになる情報的ランドマークを生産する。
テスト期間中に、ほぼ半分の忠実度シーケンスでSuccessive Halvingを破ることができることを示す。
論文 参考訳（メタデータ） (2022-06-07T09:14:24Z) - Pretrained Cost Model for Distributed Constraint Optimization Problems [37.79733538931925]
分散制約最適化問題(DCOP)は、最適化問題の重要なサブクラスである。
本稿では,DCOPのための新しい非巡回グラフスキーマ表現を提案し,グラフ表現を組み込むためにグラフ注意ネットワーク(GAT)を利用する。
我々のモデルであるGAT-PCMは、幅広いDCOPアルゴリズムを向上するために、オフラインで最適なラベル付きデータで事前訓練される。
論文 参考訳（メタデータ） (2021-12-08T09:24:10Z) - Riemannian classification of EEG signals with missing values [67.90148548467762]
本稿では脳波の分類に欠落したデータを扱うための2つの方法を提案する。
第1のアプローチでは、インプットされたデータと$k$-nearestの隣人アルゴリズムとの共分散を推定し、第2のアプローチでは、期待最大化アルゴリズム内で観測データの可能性を活用することにより、観測データに依存する。
その結果, 提案手法は観測データに基づく分類よりも優れており, 欠落したデータ比が増大しても高い精度を維持することができることがわかった。
論文 参考訳（メタデータ） (2021-10-19T14:24:50Z) - ZARTS: On Zero-order Optimization for Neural Architecture Search [94.41017048659664]
微分可能なアーキテクチャサーチ (DARTS) は、NASの高効率性のため、一般的なワンショットパラダイムである。
この作業はゼロオーダーの最適化に変わり、上記の近似を強制せずに探索するための新しいNASスキームであるZARTSを提案する。
特に、12ベンチマークの結果は、DARTSの性能が低下するZARTSの顕著な堅牢性を検証する。
論文 参考訳（メタデータ） (2021-10-10T09:35:15Z) - ROME: Robustifying Memory-Efficient NAS via Topology Disentanglement and
Gradient Accumulation [106.04777600352743]
微分可能なアーキテクチャサーチ(DARTS)は、スーパーネット全体がメモリに格納されているため、メモリコストが大幅に低下する。
シングルパスのDARTSが登場し、各ステップでシングルパスのサブモデルのみを選択する。
メモリフレンドリーだが、計算コストも低い。
RObustifying Memory-Efficient NAS (ROME) と呼ばれる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-11-23T06:34:07Z) - Distributed Optimization, Averaging via ADMM, and Network Topology [0.0]
センサローカライゼーションの現実問題において,ネットワークトポロジと異なるアルゴリズムの収束率の関係について検討する。
また、ADMMと持ち上げマルコフ連鎖の間の興味深い関係を示すとともに、その収束を明示的に特徴づける。
論文 参考訳（メタデータ） (2020-09-05T21:44:39Z) - Rethinking Performance Estimation in Neural Architecture Search [191.08960589460173]
本稿では,資源制約型システムにおける性能推定(PE)の体系的再考を行う。
BPEと強化学習,進化アルゴリズム,ランダム探索,異種アーキテクチャ探索などの様々な探索アルゴリズムを組み合わせることで,NASの1,000倍の高速化を実現した。
論文 参考訳（メタデータ） (2020-05-20T09:01:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。