論文の概要: RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2405.12497v1
• Date: Tue, 21 May 2024 04:55:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-11 00:01:52.464235
• Title: RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search
• Title（参考訳）: RaBitQ:近似近傍探索のための理論的誤差境界を持つ高次元ベクトルの量子化
• Authors: Jianyang Gao, Cheng Long,
• Abstract要約: 本稿では,RabQ という新しいランダム化量子化手法を提案し,D$次元ベクトルを$D$ビット文字列に量子化する。 RaBitQは、シャープな理論的エラー境界を保証し、同時に優れた経験的精度を提供する。 さらに,ビットワイズ演算やSIMDに基づく演算での距離を推定するRaBitQの効率的な実装についても紹介する。
• 参考スコア（独自算出の注目度）: 16.389851096504277
• License:
• Abstract: Searching for approximate nearest neighbors (ANN) in the high-dimensional Euclidean space is a pivotal problem. Recently, with the help of fast SIMD-based implementations, Product Quantization (PQ) and its variants can often efficiently and accurately estimate the distances between the vectors and have achieved great success in the in-memory ANN search. Despite their empirical success, we note that these methods do not have a theoretical error bound and are observed to fail disastrously on some real-world datasets. Motivated by this, we propose a new randomized quantization method named RaBitQ, which quantizes $D$-dimensional vectors into $D$-bit strings. RaBitQ guarantees a sharp theoretical error bound and provides good empirical accuracy at the same time. In addition, we introduce efficient implementations of RaBitQ, supporting to estimate the distances with bitwise operations or SIMD-based operations. Extensive experiments on real-world datasets confirm that (1) our method outperforms PQ and its variants in terms of accuracy-efficiency trade-off by a clear margin and (2) its empirical performance is well-aligned with our theoretical analysis.
• Abstract（参考訳）: 高次元ユークリッド空間における近傍近傍(ANN)の探索は重要な問題である。 近年、高速SIMDベースの実装により、PQ(Product Quantization)とその変種はベクトル間の距離を効率的に正確に推定することができ、インメモリANN検索において大きな成功を収めている。 実験的な成功にもかかわらず、これらの手法は理論的誤り境界を持たず、現実のデータセットで破滅的に失敗することが観察されていることに留意する。 そこで本研究では,$D$次元ベクトルを$D$ビット文字列に量子化するRaBitQというランダム化量子化手法を提案する。 RaBitQは、シャープな理論的エラー境界を保証し、同時に優れた経験的精度を提供する。 さらに,ビットワイズ演算やSIMDに基づく演算での距離を推定するRaBitQの効率的な実装についても紹介する。 実世界のデータセットに対する大規模な実験により,(1)精度・効率トレードオフの観点からPQとその変種をクリアマージンで上回り,(2)実験性能は理論解析とよく一致していることが確認された。

関連論文リスト

• HAVER: Instance-Dependent Error Bounds for Maximum Mean Estimation and Applications to Q-Learning [11.026588768210601]
  そこで本研究では,K$分布中の最大平均値の固有値をサンプルを用いて推定する問題について検討する。 HAVERと呼ばれる新しいアルゴリズムを提案し,その平均二乗誤差を解析する。
  論文  参考訳（メタデータ） (2024-11-01T07:05:11Z)
• Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing [47.32366699399839]
  近似第二エピシロン依存(SOSP)の発見は、よく研究され基礎的な問題である。 本稿では,低次元センサマシン最適化問題に適用する。
  論文  参考訳（メタデータ） (2024-03-12T01:27:44Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。 SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
  論文  参考訳（メタデータ） (2023-10-21T18:48:45Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Quantum Sparse Coding [5.130440339897477]
  我々はスパース符号化のための量子インスピレーション付きアルゴリズムを開発した。 量子コンピュータとイジングマシンの出現は、より正確な推定につながる可能性がある。 我々はLightrの量子インスパイアされたデジタルプラットフォーム上でシミュレーションデータを用いて数値実験を行う。
  論文  参考訳（メタデータ） (2022-09-08T13:00:30Z)
• DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs [54.08445874064361]
  本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。 Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。 提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
  論文  参考訳（メタデータ） (2022-08-29T18:01:42Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• AQD: Towards Accurate Fully-Quantized Object Detection [94.06347866374927]
  本稿では,浮動小数点演算を除去するために,AQDと呼ばれる高精度な量子化オブジェクト検出ソリューションを提案する。 我々のAQDは、非常に低ビットのスキームの下での完全精度と比較して、同等またはそれ以上の性能を実現しています。
  論文  参考訳（メタデータ） (2020-07-14T09:07:29Z)
• One-Bit Compressed Sensing via One-Shot Hard Thresholding [7.594050968868919]
  1ビット圧縮センシングの問題は、いくつかのバイナリ測定からスパース信号を推定することである。 広範に使われている非制約の幅の概念から遠ざかる、斬新で簡潔な分析法を提案する。
  論文  参考訳（メタデータ） (2020-07-07T17:28:03Z)
• Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
  データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。 本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
  論文  参考訳（メタデータ） (2020-04-09T01:45:05Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。