論文の概要: Practice with Graph-based ANN Algorithms on Sparse Data: Chi-square
Two-tower model, HNSW, Sign Cauchy Projections
- arxiv url: http://arxiv.org/abs/2306.07607v1
- Date: Tue, 13 Jun 2023 08:05:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-14 14:41:50.125487
- Title: Practice with Graph-based ANN Algorithms on Sparse Data: Chi-square
Two-tower model, HNSW, Sign Cauchy Projections
- Title（参考訳）: スパースデータに基づくグラフベースANNアルゴリズムの実践:チ二乗二解モデル, HNSW, サインコーシー投影
- Authors: Ping Li, Weijie Zhao, Chao Wang, Qi Xia, Alice Wu, Lijun Peng
- Abstract要約: グラフベースのANNアルゴリズムを用いてスパースデータの効率的な探索を探索する。
広告ターゲティングでは、標準のコサイン2-tower'モデルで埋め込みを訓練する。
また,Chi-square two-tower' モデルも開発している。
- 参考スコア（独自算出の注目度）: 17.542394573133777
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Sparse data are common. The traditional ``handcrafted'' features are often
sparse. Embedding vectors from trained models can also be very sparse, for
example, embeddings trained via the ``ReLu'' activation function. In this
paper, we report our exploration of efficient search in sparse data with
graph-based ANN algorithms (e.g., HNSW, or SONG which is the GPU version of
HNSW), which are popular in industrial practice, e.g., search and ads
(advertising).
We experiment with the proprietary ads targeting application, as well as
benchmark public datasets. For ads targeting, we train embeddings with the
standard ``cosine two-tower'' model and we also develop the ``chi-square
two-tower'' model. Both models produce (highly) sparse embeddings when they are
integrated with the ``ReLu'' activation function. In EBR (embedding-based
retrieval) applications, after we the embeddings are trained, the next crucial
task is the approximate near neighbor (ANN) search for serving. While there are
many ANN algorithms we can choose from, in this study, we focus on the
graph-based ANN algorithm (e.g., HNSW-type).
Sparse embeddings should help improve the efficiency of EBR. One benefit is
the reduced memory cost for the embeddings. The other obvious benefit is the
reduced computational time for evaluating similarities, because, for
graph-based ANN algorithms such as HNSW, computing similarities is often the
dominating cost. In addition to the effort on leveraging data sparsity for
storage and computation, we also integrate ``sign cauchy random projections''
(SignCRP) to hash vectors to bits, to further reduce the memory cost and speed
up the ANN search. In NIPS'13, SignCRP was proposed to hash the chi-square
similarity, which is a well-adopted nonlinear kernel in NLP and computer
vision. Therefore, the chi-square two-tower model, SignCRP, and HNSW are now
tightly integrated.
- Abstract（参考訳）: スパースデータは一般的です。
伝統的な ``handcrafted'' の特徴はしばしばスパースである。
例えば ``relu''' アクティベーション関数を通じてトレーニングされた組込みは、トレーニングされたモデルからの組込みも非常にスパースである。
本稿では,検索や広告(広告)などの産業分野で広く使われている,グラフベースのanアルゴリズム(hnsw,あるいはhnswのgpu版であるsong)を用いた,スパースデータにおける効率的な検索の探索について報告する。
私たちは、プロプライエタリな広告ターゲティングアプリケーションと、公開データセットのベンチマークを実験します。
広告ターゲティングでは、標準の ‘cosine two-tower' モデルで埋め込みを訓練し、 ‘chi-square two-tower' モデルも開発する。
どちらのモデルも ``ReLu'' アクティベーション関数と統合されたときに(非常に)スパース埋め込みを生成する。
EBR (embedding-based search) アプリケーションでは、埋め込みをトレーニングした後、次に重要なタスクは、サービスに対する近接探索(ANN)である。
選択できるANNアルゴリズムはたくさんありますが、本研究では、グラフベースのANNアルゴリズム(例えば、HNSW型)に焦点を当てます。
スパース埋め込みはebrの効率を改善するのに役立つ。
1つの利点は、埋め込みのメモリコストの削減である。
hnsw のようなグラフベースの ann アルゴリズムでは、類似度を計算することがしばしば優位なコストとなるため、類似度を評価する計算時間が短縮されるのも明らかである。
ストレージや計算にデータスペーサの活用に加えて,ベクトルをビットにハッシュするために 'sign cauchy random projections' (SignCRP)' を統合し,メモリコストをさらに削減し,ANN検索を高速化する。
NIPS'13 において、SignCRP は NLP とコンピュータビジョンにおいてよく適応された非線形カーネルである Chi-square の類似性をハッシュするために提案された。
したがって、2-乗モデルであるSignCRPとHNSWは緊密に統合されている。
関連論文リスト
- LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search [4.194768796374315]
本稿では,内積近似が多出力回帰問題であることを示す観測に基づく新しい教師付きスコア計算法を提案する。
実験の結果,提案手法はクエリ待ち時間とメモリ使用量の両方においてPQよりも優れていることがわかった。
また,クラスタリングに基づくANNライブラリであるLoRANNを導入する。
論文 参考訳（メタデータ） (2024-10-24T17:13:39Z) - 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) - Learning Regularized Graphon Mean-Field Games with Unknown Graphons [155.38727464526923]
グラフィック平均フィールドゲーム(GMFG)のための強化学習アルゴリズムを設計する。
我々は、正規化されたGMFGのナッシュ平衡(NE)を、グラフンが未知のときに学習することを目指している。
これらのアルゴリズムは、サンプルエージェントからグラモンを学習するために設計された最初のものである。
論文 参考訳（メタデータ） (2023-10-26T16:19:24Z) - Neural-prior stochastic block model [0.0]
我々は,コミュニティを,逆ではなくノード属性によって決定されるものとしてモデル化することを提案する。
本稿では,信念伝播と近似メッセージパッシングを組み合わせた統計物理に基づくアルゴリズムを提案する。
提案したモデルとアルゴリズムは理論とアルゴリズムのベンチマークとして利用できる。
論文 参考訳（メタデータ） (2023-03-17T14:14:54Z) - Provably Efficient Neural Offline Reinforcement Learning via Perturbed
Rewards [33.88533898709351]
VIPeRは、ランダム化された値関数のアイデアと悲観主義の原理を一致させる。
オフラインデータを複数回摂動することで、暗黙的に悲観性を得る。
ニューラルネットワーク関数近似を用いた一般的なマルコフ決定過程(MDP)において、証明可能かつ計算的に効率的である。
論文 参考訳（メタデータ） (2023-02-24T17:52:12Z) - A Theory of I/O-Efficient Sparse Neural Network Inference [17.862408781750126]
機械学習モデルは、その精度を速い速度で向上させるため、エネルギーと計算資源の需要は増大する。
低レベルでは、これらのリソースの大部分は異なるメモリユニット間でのデータ移動によって消費されます。
我々は、スパースフィードフォワードニューラルネットワーク(FFNN)推論に必要なI/Oを厳密に理論的に分析する。
論文 参考訳（メタデータ） (2023-01-03T11:23:46Z) - Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。
我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。
RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文 参考訳（メタデータ） (2022-10-21T15:56:13Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。
KRRのストリーミング版であるStreaMRAKを提案する。
本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
論文 参考訳（メタデータ） (2021-08-23T21:03:09Z) - Faster Secure Data Mining via Distributed Homomorphic Encryption [108.77460689459247]
ホモモルフィック暗号化(HE)は、最近、暗号化されたフィールド上で計算を行う能力により、ますます注目を集めている。
本稿では,スケーリング問題の解決に向けて,新しい分散HEベースのデータマイニングフレームワークを提案する。
各種データマイニングアルゴリズムとベンチマークデータセットを用いて,新しいフレームワークの有効性と有効性を検証する。
論文 参考訳（メタデータ） (2020-06-17T18:14:30Z) - Learning to Hash with Graph Neural Networks for Recommender Systems [103.82479899868191]
グラフ表現学習は、大規模に高品質な候補探索をサポートすることに多くの注目を集めている。
ユーザ・イテム相互作用ネットワークにおけるオブジェクトの埋め込みベクトルの学習の有効性にもかかわらず、連続的な埋め込み空間におけるユーザの好みを推測する計算コストは膨大である。
連続的かつ離散的なコードとを協調的に学習するための,単純かつ効果的な離散表現学習フレームワークを提案する。
論文 参考訳（メタデータ） (2020-03-04T06:59:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。