論文の概要: Sampling from a $k$-DPP without looking at all items

• arxiv url: http://arxiv.org/abs/2006.16947v1
• Date: Tue, 30 Jun 2020 16:40:44 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-15 05:20:22.839213
• Title: Sampling from a $k$-DPP without looking at all items
• Title（参考訳）: すべてのアイテムを見ることなく$k$-DPPからサンプリングする
• Authors: Daniele Calandriello, Micha{\l} Derezi\'nski, Michal Valko
• Abstract要約: カーネル関数とサブセットサイズ$k$が与えられた場合、我々のゴールは、サブセットによって誘導されるカーネル行列の行列式に比例する確率を持つ$n$アイテムから$k$をサンプリングすることである(つまり$k$-DPP)。 既存の$k$-DPPサンプリングアルゴリズムは、すべての$n$アイテムを複数回パスする高価な前処理ステップを必要とするため、大規模なデータセットでは利用できない。 そこで我々は, 十分大きなデータの均一なサンプルを適応的に構築し, より小さな$k$のアイテムを効率よく生成するアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 58.30573872035083
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Determinantal point processes (DPPs) are a useful probabilistic model for selecting a small diverse subset out of a large collection of items, with applications in summarization, stochastic optimization, active learning and more. Given a kernel function and a subset size $k$, our goal is to sample $k$ out of $n$ items with probability proportional to the determinant of the kernel matrix induced by the subset (a.k.a. $k$-DPP). Existing $k$-DPP sampling algorithms require an expensive preprocessing step which involves multiple passes over all $n$ items, making it infeasible for large datasets. A na\"ive heuristic addressing this problem is to uniformly subsample a fraction of the data and perform $k$-DPP sampling only on those items, however this method offers no guarantee that the produced sample will even approximately resemble the target distribution over the original dataset. In this paper, we develop an algorithm which adaptively builds a sufficiently large uniform sample of data that is then used to efficiently generate a smaller set of $k$ items, while ensuring that this set is drawn exactly from the target distribution defined on all $n$ items. We show empirically that our algorithm produces a $k$-DPP sample after observing only a small fraction of all elements, leading to several orders of magnitude faster performance compared to the state-of-the-art.
• Abstract（参考訳）: 決定的点過程(英: determinantal point process、dpps)は、大量のアイテムから小さな多様なサブセットを選択するための有用な確率モデルであり、要約、確率最適化、アクティブラーニングなどの応用がある。 カーネル関数とサブセットサイズ$k$が与えられた場合、我々のゴールは、サブセットによって誘導されるカーネル行列の行列式に比例する確率を持つ$n$アイテムから$k$をサンプリングすることである(つまり$k$-DPP)。 既存の$k$-DPPサンプリングアルゴリズムは、すべての$n$アイテムを複数回パスする高価な前処理ステップを必要とするため、大規模なデータセットでは利用できない。 この問題に対処するna\"ive heuristicは、データのごく一部を一様にサンプリングし、これらのアイテムのみに$k$-dppサンプリングを実行することであるが、この方法は、生成されたサンプルが元のデータセット上のターゲットディストリビューションにほぼ類似することさえ保証しない。 そこで本研究では,十分な量の均一なデータサンプルを適応的に構築し,より小さな$k$項目のセットを効率的に生成し,このセットが$n$項目すべてで定義されたターゲット分布から正確に描画されることを保証するアルゴリズムを開発した。 私たちのアルゴリズムは、すべての要素のほんの一部しか観察しなかった後に、k$-dppのサンプルを生成することが実証的に示されています。

関連論文リスト

• Replicable Clustering [57.19013971737493]
  我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。 理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
  論文  参考訳（メタデータ） (2023-02-20T23:29:43Z)
• A Faster Sampler for Discrete Determinantal Point Processes [10.355938901584567]
  Discrete Determinantal Point Processs (DPP) は、データセットのサブサンプル化に幅広い可能性を持つ。 最悪の場合、サンプリングコストは$O(n3)$で、nは基底集合の要素の数である。 この禁止コストに対する一般的な回避策は、低ランクカーネルによって定義されたDPPをサンプリングすることである。
  論文  参考訳（メタデータ） (2022-10-31T14:37:54Z)
• Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes [45.40646054226403]
  決定点プロセス(DPP)は、$n$アイテムの全てのサブセットに確率を割り当てる。 最近の研究は、NDPPに対する近似連鎖モンテカルロサンプリングアルゴリズムを、サイズ-k$サブセットに限定して研究している。 低ランクカーネルを持つ$k$-NDPPに対するスケーラブルなMCMCサンプリングアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-07-01T15:22:12Z)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  我々は,$q$-foldカラムワイドテンソル積の$q$行列に対応するグラム行列を近似するための入力空間時間サンプリングアルゴリズムを提案する。 我々のサンプリング技術は、合計時間でデータセット$X$に同時に適用できる$q$部分相関ランダムプロジェクションのコレクションに依存している。
  論文  参考訳（メタデータ） (2022-02-09T15:26:03Z)
• Scalable Sampling for Nonsymmetric Determinantal Point Processes [47.18450267217498]
  M$アイテムの集合上の決定点過程(DPP)は、対称的なカーネル行列によってパラメータ化されるモデルである。 最近の研究は、非対称DPP(NDPPs)を生じるカーネル対称性の制約を取り除くことで、機械学習アプリケーションにおいて大幅な性能向上が期待できることを示している。 コールスキー分解に基づくDPPサンプリングアルゴリズムは1つしか知られておらず、NDPPにも直接適用できる。 NDPPカーネルに特定の構造的制約を課すことで、カーネルのランクに依存する方法で拒絶率を制限できることが示される。
  論文  参考訳（メタデータ） (2022-01-20T19:21:59Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Testing Determinantal Point Processes [0.0]
  配電体の特性試験という新たな視点からDPPについて検討する。 DPPをテストするための最初のアルゴリズムを提案する。 より一般的な対数-部分モジュラ分布のクラスをテストする問題に対して、新しい硬度結果を示す。
  論文  参考訳（メタデータ） (2020-08-09T04:45:16Z)
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning [123.69175280309226]
  オンライン強化学習(RL)における課題の1つは、エージェントがその振る舞いを最適化するために、環境の探索とサンプルの活用をトレードオフする必要があることである。 1) 生成モデル(環境のスパースシミュレータなど)にアクセス可能な状態のサンプル数を規定する「対象別」アルゴリズム,2) 所定のサンプルをできるだけ早く生成する「対象別」サンプル収集。
  論文  参考訳（メタデータ） (2020-07-13T15:17:35Z)
• Best-item Learning in Random Utility Models with Subset Choices [40.17224226373741]
  我々は、$k$アイテムのサブセットの逐次的かつ適応的に選択されたプレイを用いて、$n$アイテムのプールから最も価値のあるアイテムをPACで学習する問題を考察する。 そのようなRUMの新たな性質を最小限の利点と呼び、アイテムのペアを分離する複雑さを特徴づけるのに役立つ。 一般RUMの学習アルゴリズムとして,アイテムの相対的な数と階層的除去と,新しいPACサンプルの複雑性保証を併用した学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-19T03:57:16Z)

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

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