論文の概要: Approximating a Target Distribution using Weight Queries

• arxiv url: http://arxiv.org/abs/2006.13636v2
• Date: Sat, 27 Feb 2021 17:56:58 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-17 09:23:38.106609
• Title: Approximating a Target Distribution using Weight Queries
• Title（参考訳）: ウェイトクエリによるターゲット分布の近似
• Authors: Nadav Barak and Sivan Sabato
• Abstract要約: 本稿では,データセットの例を反復的に選択し,対応する重み付けクエリを実行する対話型アルゴリズムを提案する。 我々は,アルゴリズムが検出した再重み付けと,最も達成可能な再重み付けとの間の全変動距離に依存する近似を導出する。
• 参考スコア（独自算出の注目度）: 25.392248158616862
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a novel challenge: approximating a distribution without the ability to randomly sample from that distribution. We study how such an approximation can be obtained using *weight queries*. Given some data set of examples, a weight query presents one of the examples to an oracle, which returns the probability, according to the target distribution, of observing examples similar to the presented example. This oracle can represent, for instance, counting queries to a database of the target population, or an interface to a search engine which returns the number of results that match a given search. We propose an interactive algorithm that iteratively selects data set examples and performs corresponding weight queries. The algorithm finds a reweighting of the data set that approximates the weights according to the target distribution, using a limited number of weight queries. We derive an approximation bound on the total variation distance between the reweighting found by the algorithm and the best achievable reweighting. Our algorithm takes inspiration from the UCB approach common in multi-armed bandits problems, and combines it with a new discrepancy estimator and a greedy iterative procedure. In addition to our theoretical guarantees, we demonstrate in experiments the advantages of the proposed algorithm over several baselines. A python implementation of the proposed algorithm and of all the experiments can be found at https://github.com/Nadav-Barak/AWP.
• Abstract（参考訳）: 我々は、その分布からランダムにサンプリングする能力のない分布を近似することという、新しい課題を考える。 このような近似が *weight query* を用いてどのように得られるか検討する。 例のデータセットが与えられた場合、重み付きクエリはoracleに例の1つを示し、ターゲットの分布に従って確率を返す。 このオラクルは、例えば、対象とする人口のデータベースへのクエリのカウント、あるいは検索エンジンへのインターフェースを表現して、与えられた検索にマッチする結果の数を返却することができる。 本稿では,データセットの例を反復的に選択し,対応する重み付けクエリを実行する対話型アルゴリズムを提案する。 アルゴリズムは、限られた数の重みクエリを用いて、ターゲット分布に応じて重みを近似するデータセットの再重み付けを求める。 我々は,アルゴリズムが検出した再重み付けと,最も達成可能な再重み付けとの間の全変動距離に依存する近似を導出する。 提案アルゴリズムは,マルチアームバンディット問題に共通するUPB手法からインスピレーションを得て,新たな差分推定器と欲求反復法を組み合わせたものである。 理論的な保証に加えて,いくつかのベースラインに対する提案アルゴリズムの利点を実験で実証する。 提案アルゴリズムのピソン実装と全ての実験はhttps://github.com/Nadav-Barak/AWPで見ることができる。

関連論文リスト

• pEBR: A Probabilistic Approach to Embedding Based Retrieval [4.8338111302871525]
  埋め込み検索は、クエリとアイテムの両方の共有セマンティック表現空間を学習することを目的としている。 現在の産業実践では、検索システムは典型的には、異なるクエリに対して一定数のアイテムを検索する。
  論文  参考訳（メタデータ） (2024-10-25T07:14:12Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Finding Support Examples for In-Context Learning [73.90376920653507]
  本稿では,この課題を2段階に解決するためのfilter-thEN-Search法であるLENSを提案する。 まず、データセットをフィルタリングして、個別に情報的インコンテキストの例を得る。 そこで本研究では,反復的に改良し,選択したサンプル順列を評価可能な多様性誘導型サンプル探索を提案する。
  論文  参考訳（メタデータ） (2023-02-27T06:32:45Z)
• Leveraging Importance Weights in Subset Selection [45.54597544672441]
  本稿では,任意のモデルファミリを実用的なバッチ設定で扱うように設計されたサブセット選択アルゴリズムを提案する。 我々のアルゴリズムであるIWeSは、各サンプルに割り当てられたサンプリング確率が、以前選択されたバッチで訓練されたモデルのエントロピーに基づいて、重要サンプリングによってサンプルを選択する。
  論文  参考訳（メタデータ） (2023-01-28T02:07:31Z)
• A Bayesian Bradley-Terry model to compare multiple ML algorithms on multiple data sets [4.394728504061753]
  本稿では, ベイズモデルを用いて, 複数のデータセット上で, 任意の距離で複数のアルゴリズムを比較する。 このモデルはBradley-Terryモデルに基づいており、1つのアルゴリズムが異なるデータセットで他のアルゴリズムよりも優れている回数を数えている。
  論文  参考訳（メタデータ） (2022-08-09T17:59:06Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。 局所探索のための政策勾配は、しばしばランダムな摂動から得られる。 目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-06-22T16:07:02Z)
• Approximate Query Processing for Group-By Queries based on Conditional Generative Models [3.9837198605506963]
  グループバイクエリには複数の値が含まれるため、すべてのグループに対して十分な正確な推定を行うのは難しい。 階層化サンプリングは、一様サンプリングに比べて精度が向上するが、特定のクエリで選択されたサンプルは他のクエリでは動作しない。 オンラインサンプリングは、クエリ時に与えられたクエリのサンプルを選択するが、長いレイテンシを必要とする。 提案フレームワークは階層化サンプリングとオンラインアグリゲーションを組み合わせることで,グループバイクエリの推定精度を向上させることができる。
  論文  参考訳（メタデータ） (2021-01-08T08:49:21Z)
• Optimal Off-Policy Evaluation from Multiple Logging Policies [77.62012545592233]
  我々は,複数のロギングポリシからオフ政治評価を行い,それぞれが一定のサイズ,すなわち階層化サンプリングのデータセットを生成する。 複数ロガーのOPE推定器は,任意のインスタンス,すなわち効率のよいインスタンスに対して最小分散である。
  論文  参考訳（メタデータ） (2020-10-21T13:43:48Z)
• Optimal Representative Sample Weighting [0.0]
  重み付けを代表的に行うことを目的として,サンプルやデータ記録に重み付けを割り当てる問題を考察する。 代表標本重みを求める問題を最適化問題として, 多くの場合, 凸であり, 効率よく解ける問題である。 本稿では,提案するアイデアのオープンソース実装であるrswについて述べるとともに,CDC BRFSSデータセットのスキューサンプルに適用する。
  論文  参考訳（メタデータ） (2020-05-18T20:29:00Z)

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

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