論文の概要: Faster Maximum Inner Product Search in High Dimensions
- arxiv url: http://arxiv.org/abs/2212.07551v3
- Date: Tue, 27 Jun 2023 03:36:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-28 17:36:12.036326
- Title: Faster Maximum Inner Product Search in High Dimensions
- Title（参考訳）: 高次元における最大内積探索の高速化
- Authors: Mo Tiwari, Ryan Kang, Je-Yong Lee, Donghyun Lee, Chris Piech,
Sebastian Thrun, Ilan Shomorony, Martin Jinye Zhang
- Abstract要約: 最大内部製品探索(MIPS)は、リコメンデーションシステムなどの機械学習アプリケーションにおいて、ユビキタスなタスクである。
複雑度が$d$に依存しない新しいランダム化MIPSアルゴリズムであるBanditMIPSを提案する。
我々は、BanditMIPSが正しい答えを高い確率で返し、$d$を$O(sqrtd)$から$O(1)$に改善する理論的な保証を提供する。
- 参考スコア（独自算出の注目度）: 17.040520467777295
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Maximum Inner Product Search (MIPS) is a ubiquitous task in machine learning
applications such as recommendation systems. Given a query vector and $n$ atom
vectors in $d$-dimensional space, the goal of MIPS is to find the atom that has
the highest inner product with the query vector. Existing MIPS algorithms scale
at least as $O(\sqrt{d})$, which becomes computationally prohibitive in
high-dimensional settings. In this work, we present BanditMIPS, a novel
randomized MIPS algorithm whose complexity is independent of $d$. BanditMIPS
estimates the inner product for each atom by subsampling coordinates and
adaptively evaluates more coordinates for more promising atoms. The specific
adaptive sampling strategy is motivated by multi-armed bandits. We provide
theoretical guarantees that BanditMIPS returns the correct answer with high
probability, while improving the complexity in $d$ from $O(\sqrt{d})$ to
$O(1)$. We also perform experiments on four synthetic and real-world datasets
and demonstrate that BanditMIPS outperforms prior state-of-the-art algorithms.
For example, in the Movie Lens dataset ($n$=4,000, $d$=6,000), BanditMIPS is
20$\times$ faster than the next best algorithm while returning the same answer.
BanditMIPS requires no preprocessing of the data and includes a hyperparameter
that practitioners may use to trade off accuracy and runtime. We also propose a
variant of our algorithm, named BanditMIPS-$\alpha$, which achieves further
speedups by employing non-uniform sampling across coordinates. Finally, we
demonstrate how known preprocessing techniques can be used to further
accelerate BanditMIPS, and discuss applications to Matching Pursuit and Fourier
analysis.
- Abstract（参考訳）: 最大内部製品探索(MIPS)は、リコメンデーションシステムなどの機械学習アプリケーションにおいて、ユビキタスなタスクである。
クエリベクトルと$d$次元空間における$n$原子ベクトルが与えられた場合、MIPSの目標は、クエリベクトルで最高内部積を持つ原子を見つけることである。
既存のMIPSアルゴリズムは少なくとも$O(\sqrt{d})$としてスケールし、高次元設定では計算が禁止される。
本稿では、$d$に依存しない新しいランダム化MIPSアルゴリズムであるBanditMIPSを紹介する。
BanditMIPSは、各原子の内部積を座標をサブサンプリングすることで推定し、より有望な原子に対するより多くの座標を適応的に評価する。
特定の適応サンプリング戦略はマルチアームのバンディットによって動機づけられる。
我々は、banditmipsが正しい答えを高い確率で返すことを理論的に保証する一方で、$d$の複雑さを$o(\sqrt{d})$から$o(1)$に改善する。
また、4つの合成および実世界のデータセットの実験を行い、BanditMIPSが最先端のアルゴリズムよりも優れていることを示す。
例えば、Movie Lensデータセット($$4,000,$d$=6,000)では、BanditMIPSは同じ答えを返す間、次の最適なアルゴリズムよりも20$\times$高速である。
BanditMIPSはデータの事前処理を必要とせず、実践者が正確性と実行をトレードオフするために使用するハイパーパラメータを含んでいる。
また、座標をまたいだ一様サンプリングを用いてさらなる高速化を実現するBanditMIPS-$\alpha$というアルゴリズムの変種を提案する。
最後に,前処理技術がバンディットのさらなる高速化にどのように役立つかを実証し,マッチング追従とフーリエ解析への応用について考察する。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳（メタデータ） (2022-11-28T08:40:12Z) - Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes [45.40646054226403]
決定点プロセス(DPP)は、$n$アイテムの全てのサブセットに確率を割り当てる。
最近の研究は、NDPPに対する近似連鎖モンテカルロサンプリングアルゴリズムを、サイズ-k$サブセットに限定して研究している。
低ランクカーネルを持つ$k$-NDPPに対するスケーラブルなMCMCサンプリングアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-07-01T15:22:12Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳（メタデータ） (2022-06-14T08:14:14Z) - Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process
Regression with Mat\'ern Correlations [23.560067934682294]
マタン相関を用いた1次元ガウス過程回帰のための正確でスケーラブルなアルゴリズムを開発した。
提案アルゴリズムは,計算時間と予測精度の両方において,既存の代替手法よりもはるかに優れている。
論文 参考訳（メタデータ） (2022-03-07T03:30:35Z) - Quantum Algorithms for Reinforcement Learning with a Generative Model [16.168901236223117]
強化学習は、エージェントがその累積報酬を最大化するために環境とどのように相互作用するかを研究する。
最適ポリシー(pi*$)、最適値関数(v*$)、最適値関数(q*$)を近似する量子アルゴリズムを設計する。
一致する量子下界を証明して、q*$を計算するための量子アルゴリズムが最適であることを示す。
論文 参考訳（メタデータ） (2021-12-15T19:51:49Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳（メタデータ） (2020-10-19T16:45:37Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - BanditPAM: Almost Linear Time $k$-Medoids Clustering via Multi-Armed
Bandits [16.1767275655842]
現在の$k$-medoidsクラスタリングアルゴリズム、例えば、PAM(Partitioning Around Medoids)は反復的であり、各イテレーションで$n$のデータセットサイズであり、大規模なデータセットでは極めて高価である。
マルチアームバンディットの技法にインスパイアされたランダム化アルゴリズムであるBanditPAMを提案する。これは、PAMの繰り返しの複雑さを$O(n2)$から$O(n log n)$に減らし、実際に保持されるデータに対する仮定の下で、高い確率で同じ結果を返す。
我々は、コーディングを含むいくつかの大規模な実世界のデータセットで実験的に結果を検証する。
論文 参考訳（メタデータ） (2020-06-11T22:17:16Z) - Low Complexity Sequential Search with Size-Dependent Measurement Noise [19.201555109949677]
本稿では、エージェントが任意の時間にその領域にターゲットが存在するかどうかを問い合わせる領域を選択することができるターゲットローカライゼーション問題について考察する。
アレイ処理における初期ビームアライメント、ネットワークにおける重ヒッタ検出、ロボット工学におけるビジュアルサーチといった実用的応用により、我々は事実上重要な複雑さの制約/指標を考察する。
新規検索戦略として$dyaPM$と$hiePM$が提案されている。
論文 参考訳（メタデータ） (2020-05-15T22:40:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。