論文の概要: Discovering Data Structures: Nearest Neighbor Search and Beyond

• arxiv url: http://arxiv.org/abs/2411.03253v1
• Date: Tue, 05 Nov 2024 16:50:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-06 15:00:30.712767
• Title: Discovering Data Structures: Nearest Neighbor Search and Beyond
• Title（参考訳）: データ構造を発見する - 最近傍の検索とそれを超えるもの
• Authors: Omar Salemohamed, Laurent Charlin, Shivam Garg, Vatsal Sharan, Gregory Valiant,
• Abstract要約: データ構造をエンド・ツー・エンドで学習するための一般的なフレームワークを提案する。 我々のフレームワークは、基礎となるデータ分布に適応し、クエリと空間の複雑さをきめ細やかな制御を提供する。 まず、この枠組みを近接探索問題に適用する。
• 参考スコア（独自算出の注目度）: 18.774836778996544
• License:
• Abstract: We propose a general framework for end-to-end learning of data structures. Our framework adapts to the underlying data distribution and provides fine-grained control over query and space complexity. Crucially, the data structure is learned from scratch, and does not require careful initialization or seeding with candidate data structures/algorithms. We first apply this framework to the problem of nearest neighbor search. In several settings, we are able to reverse-engineer the learned data structures and query algorithms. For 1D nearest neighbor search, the model discovers optimal distribution (in)dependent algorithms such as binary search and variants of interpolation search. In higher dimensions, the model learns solutions that resemble k-d trees in some regimes, while in others, they have elements of locality-sensitive hashing. The model can also learn useful representations of high-dimensional data and exploit them to design effective data structures. We also adapt our framework to the problem of estimating frequencies over a data stream, and believe it could also be a powerful discovery tool for new problems.
• Abstract（参考訳）: データ構造をエンド・ツー・エンドで学習するための一般的なフレームワークを提案する。 我々のフレームワークは、基礎となるデータ分布に適応し、クエリと空間の複雑さをきめ細やかな制御を提供する。 重要なことは、データ構造はスクラッチから学習され、候補データ構造やアルゴリズムで慎重に初期化やシードを行う必要はない。 まず、この枠組みを近接探索問題に適用する。 いくつかの設定で、学習したデータ構造とクエリアルゴリズムをリバースエンジニアリングすることができます。 近接した1次元探索に対して、このモデルは二進探索や補間探索の変種のような最適分布(in)依存アルゴリズムを発見する。 より高次元では、モデルはいくつかのレジームにおいてk-d木に似た解を学ぶが、他の場合では局所性に敏感なハッシュの要素を持つ。 このモデルはまた、高次元データの有用な表現を学習し、それらを有効データ構造の設計に利用することができる。 また、私たちのフレームワークは、データストリーム上の周波数を推定する問題にも適応しています。

関連論文リスト

• Coordinated Multi-Neighborhood Learning on a Directed Acyclic Graph [6.727984016678534]
  因果非巡回グラフ(DAG)の構造を学習することは、機械学習や人工知能の多くの分野で有用である。 強い、しばしば制限的な仮定なしに優れた経験的、理論的結果を得ることは困難である。 本論文では,複数のユーザ特定ターゲットノードの周囲の局所構造を推定する制約に基づく新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-05-24T08:49:43Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。 クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。 このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
  論文  参考訳（メタデータ） (2023-05-24T11:05:12Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  因果構造を学習することは、通常、スコアまたは独立テストを使用して構造を評価することを伴う探索問題を引き起こす。 本研究では,観測・干渉データから因果構造を予測するため,変分推論モデルを訓練する。 我々のモデルは、実質的な分布シフトの下で頑健な一般化能力を示す。
  論文  参考訳（メタデータ） (2022-05-25T17:37:08Z)
• Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
  Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。 代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。 データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
  論文  参考訳（メタデータ） (2021-12-06T20:34:55Z)
• Mathematical Models for Local Sensing Hashes [7.400475825464313]
  近似インデックス構造は,クラスタリングと外乱検出の近傍探索を高速化する好機であることを示す。 局所センシングハッシュの特性を数学的にモデル化する方向を示す。
  論文  参考訳（メタデータ） (2021-11-16T10:40:55Z)
• Learning to Hash Robustly, with Guarantees [79.68057056103014]
  本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。 理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。 我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
  論文  参考訳（メタデータ） (2021-08-11T20:21:30Z)
• Evaluating Online and Offline Accuracy Traversal Algorithms for k-Complete Neural Network Architectures [6.123324869194195]
  本稿では,バイナリ分類のためのコンパクトニューラルネットワークアーキテクチャについて検討する。 過完全なアーキテクチャ候補を好む場合、スピードと精度の向上を調査します。
  論文  参考訳（メタデータ） (2021-01-16T20:37:29Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Deep Retrieval: Learning A Retrievable Structure for Large-Scale Recommendations [21.68175843347951]
  本稿では,ユーザとイテムのインタラクションデータを用いて,検索可能な構造を直接学習するために,Deep Retrieval(DR)を提案する。 DRは、産業レコメンデーションシステムのために数億のアイテムをスケールで展開した最初の非ANNアルゴリズムの1つである。
  論文  参考訳（メタデータ） (2020-07-12T06:23:51Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。 クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
  論文  参考訳（メタデータ） (2020-05-22T23:07:42Z)
• Data Structures & Algorithms for Exact Inference in Hierarchical Clustering [41.24805506595378]
  本稿では,新しいトレリスデータ構造に基づく階層クラスタリングにおける表現型推論のための動的プログラミングアルゴリズムを提案する。 我々のアルゴリズムは時間と空間に比例してN$要素のパワーセットをスケールし、これは(2N-3)! 可能な階層のそれぞれを明示的に考慮するよりも指数関数的に効率的である。
  論文  参考訳（メタデータ） (2020-02-26T17:43:53Z)

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

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