論文の概要: $\mathbb{R}^{2k}$ is Theoretically Large Enough for Embedding-based Top-$k$ Retrieval
- arxiv url: http://arxiv.org/abs/2601.20844v1
- Date: Wed, 28 Jan 2026 18:45:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-29 15:46:07.100117
- Title: $\mathbb{R}^{2k}$ is Theoretically Large Enough for Embedding-based Top-$k$ Retrieval
- Title（参考訳）: $\mathbb{R}^{2k}$は、埋め込みベースのTop-k$ Retrievalの理論的に大きすぎる
- Authors: Zihao Wang, Hang Yin, Lihui Liu, Hanghang Tong, Yangqiu Song, Ginny Wong, Simon See,
- Abstract要約: 本稿では,最小埋め込み次元 (Minimal Embeddable Dimension, MED) で表されるベクトル空間に部分集合 (m$ element, $mchoose k$ subsets of at least $k$ element) を埋め込むために必要な最小次元について検討する。
MEDの密接な境界は理論的に導出され、$ell$メートル法、内積、コサイン類似性を含む「距離」や「類似性」の様々な概念に対して実証的に支持される。
- 参考スコア（独自算出の注目度）: 99.8640829555514
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: This paper studies the minimal dimension required to embed subset memberships ($m$ elements and ${m\choose k}$ subsets of at most $k$ elements) into vector spaces, denoted as Minimal Embeddable Dimension (MED). The tight bounds of MED are derived theoretically and supported empirically for various notions of "distances" or "similarities," including the $\ell_2$ metric, inner product, and cosine similarity. In addition, we conduct numerical simulation in a more achievable setting, where the ${m\choose k}$ subset embeddings are chosen as the centroid of the embeddings of the contained elements. Our simulation easily realizes a logarithmic dependency between the MED and the number of elements to embed. These findings imply that embedding-based retrieval limitations stem primarily from learnability challenges, not geometric constraints, guiding future algorithm design.
- Abstract（参考訳）: 本稿では, 最小埋め込み次元 (Minimal Embeddable Dimension, MED) と呼ばれるベクトル空間に部分集合 (m$ element) と${m\choose k}$ subsets of at least $k$ element) を埋め込むために必要な最小次元について検討する。
MEDの密接な境界は理論的に導出され、$\ell_2$メートル法、内積、コサイン類似性を含む「距離」や「類似性」の様々な概念に対して実証的に支持される。
さらに、より達成可能な環境で数値シミュレーションを行い、そこでは、${m\choose k}$サブセットの埋め込みを、その要素の埋め込みのセントロイドとして選択する。
シミュレーションにより,MEDと埋め込み要素数との対数依存性を容易に実現できる。
これらの知見は, 組込み型検索の限界は主に, 幾何学的制約ではなく, 学習可能性の問題に起因し, 将来のアルゴリズム設計を導くことを示唆している。
関連論文リスト
- Bounds on Lorentz-violating parameters in magnetically confined 2D systems: A phenomenological approach [0.0]
本稿では、磁区2次元電子系を用いて最小のSME係数を$a_mu$および$b_mu$で制限する枠組みを提案する。
有効質量を持つ非相対論的(Schr"odinger--Pauli)極限で働くと、円筒ジオメトリーのラジアル問題を導出する。
論文 参考訳（メタデータ） (2025-10-28T11:11:59Z) - Fourier Sliced-Wasserstein Embedding for Multisets and Measures [3.396731589928944]
ユークリッド空間に Rd 上の多重集合と測度を埋め込む新しい方法を提案する。
我々は、Rd 上の分布をバイ・リプシッツな方法でユークリッド空間に埋め込むことは不可能であることを証明した。
論文 参考訳（メタデータ） (2024-05-26T11:04:41Z) - Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams [34.7582575446942]
準多項式依存のMDSに対する最初の近似アルゴリズムをDeltaに与える。
本アルゴリズムは,シェラリ・アダムスLPの条件付きラウンドリングの幾何学的認識に基づく新しい解析法である。
論文 参考訳（メタデータ） (2023-11-29T17:42:05Z) - Polynomial Width is Sufficient for Set Representation with
High-dimensional Features [69.65698500919869]
DeepSetsは集合表現のための最も広く使われているニューラルネットワークアーキテクチャである。
a) 線形 + パワーアクティベーション (LP) と (b) 線形 + 指数的アクティベーション (LE) の2つの集合要素埋め込み層を示す。
論文 参考訳（メタデータ） (2023-07-08T16:00:59Z) - Parameterized Approximation Schemes for Clustering with General Norm
Objectives [0.6956677722498498]
本稿では、$(k,epsilon)$-approximationアルゴリズムを$k$-clustering問題に対して設計する、よく研究されている方式について考察する。
私たちの主な貢献は、クリーンでシンプルなEPASで、10以上のクラスタリング問題を解決しています。
論文 参考訳（メタデータ） (2023-04-06T15:31:37Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - De Rham compatible Deep Neural Network FEM [0.0]
DNNでは通常のsimplicial partitions $mathcalT$ of $Omega$の制限は不要である。
我々は、高階互換空間や他の非互換な離散化のクラスへの構成の一般化を示す。
論文 参考訳（メタデータ） (2022-01-14T11:22:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。