論文の概要: Scalable Sampling for Nonsymmetric Determinantal Point Processes

• arxiv url: http://arxiv.org/abs/2201.08417v1
• Date: Thu, 20 Jan 2022 19:21:59 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-24 13:33:32.400296
• Title: Scalable Sampling for Nonsymmetric Determinantal Point Processes
• Title（参考訳）: 非対称決定点過程のスケーラブルサンプリング
• Authors: Insu Han, Mike Gartrell, Jennifer Gillenwater, Elvis Dohmatob, Amin Karbasi
• Abstract要約: M$アイテムの集合上の決定点過程(DPP)は、対称的なカーネル行列によってパラメータ化されるモデルである。 最近の研究は、非対称DPP(NDPPs)を生じるカーネル対称性の制約を取り除くことで、機械学習アプリケーションにおいて大幅な性能向上が期待できることを示している。 コールスキー分解に基づくDPPサンプリングアルゴリズムは1つしか知られておらず、NDPPにも直接適用できる。 NDPPカーネルに特定の構造的制約を課すことで、カーネルのランクに依存する方法で拒絶率を制限できることが示される。
• 参考スコア（独自算出の注目度）: 47.18450267217498
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A determinantal point process (DPP) on a collection of $M$ items is a model, parameterized by a symmetric kernel matrix, that assigns a probability to every subset of those items. Recent work shows that removing the kernel symmetry constraint, yielding nonsymmetric DPPs (NDPPs), can lead to significant predictive performance gains for machine learning applications. However, existing work leaves open the question of scalable NDPP sampling. There is only one known DPP sampling algorithm, based on Cholesky decomposition, that can directly apply to NDPPs as well. Unfortunately, its runtime is cubic in $M$, and thus does not scale to large item collections. In this work, we first note that this algorithm can be transformed into a linear-time one for kernels with low-rank structure. Furthermore, we develop a scalable sublinear-time rejection sampling algorithm by constructing a novel proposal distribution. Additionally, we show that imposing certain structural constraints on the NDPP kernel enables us to bound the rejection rate in a way that depends only on the kernel rank. In our experiments we compare the speed of all of these samplers for a variety of real-world tasks.
• Abstract（参考訳）: M$アイテムの集合上の決定点プロセス(DPP)は、対称的なカーネル行列によってパラメータ化され、それらの項目の全てのサブセットに確率を割り当てるモデルである。 最近の研究は、非対称DPP(NDPPs)を生じるカーネル対称性の制約を取り除くことで、機械学習アプリケーションにおいて大幅な性能向上が期待できることを示している。 しかし、既存の作業では、スケーラブルなNDPPサンプリングの問題が残されている。 コールスキー分解に基づくDPPサンプリングアルゴリズムは1つしか知られておらず、NDPPにも直接適用できる。 残念ながら、ランタイムは$M$で、従って大規模なアイテムコレクションにはスケールしない。 本稿ではまず, このアルゴリズムを, 低ランク構造を持つカーネルに対して線形時間に変換できることを示す。 さらに,新しい提案分布を構築し,スケーラブルな部分線形時間拒否サンプリングアルゴリズムを開発した。 さらに、NDPPカーネルに特定の構造的制約を課すことで、カーネルのランクに依存する方法で拒絶率を制限できることが示される。 実験では、これらのサンプルの速度を実世界の様々なタスクと比較した。

関連論文リスト

• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes [45.40646054226403]
  決定点プロセス(DPP)は、$n$アイテムの全てのサブセットに確率を割り当てる。 最近の研究は、NDPPに対する近似連鎖モンテカルロサンプリングアルゴリズムを、サイズ-k$サブセットに限定して研究している。 低ランクカーネルを持つ$k$-NDPPに対するスケーラブルなMCMCサンプリングアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-07-01T15:22:12Z)
• Simple and Near-Optimal MAP Inference for Nonsymmetric DPPs [3.3504365823045044]
  非対称なカーネル行列によって定義される決定点過程に対する最大後続推定(MAP)問題について検討する。 局所探索を用いてこの問題に対する最初の乗法近似保証を得る。 近似係数が$kO(k)$ に近いので、理論上、実験的に、この問題に対する最先端の手法と好適に比較できることが示される。
  論文  参考訳（メタデータ） (2021-02-10T09:34:44Z)
• Learning from DPPs via Sampling: Beyond HKPV and symmetry [2.0305676256390934]
  行列点過程(DPP)の線形統計量の分布関数を近似する方法を示す。 我々のアプローチはスケーラブルであり、従来の対称カーネルを超えて非常に一般的なDPPに適用できる。
  論文  参考訳（メタデータ） (2020-07-08T17:33:45Z)
• Sampling from a $k$-DPP without looking at all items [58.30573872035083]
  カーネル関数とサブセットサイズ$k$が与えられた場合、我々のゴールは、サブセットによって誘導されるカーネル行列の行列式に比例する確率を持つ$n$アイテムから$k$をサンプリングすることである(つまり$k$-DPP)。 既存の$k$-DPPサンプリングアルゴリズムは、すべての$n$アイテムを複数回パスする高価な前処理ステップを必要とするため、大規模なデータセットでは利用できない。 そこで我々は, 十分大きなデータの均一なサンプルを適応的に構築し, より小さな$k$のアイテムを効率よく生成するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-06-30T16:40:44Z)
• Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes [29.56615511158156]
  我々は新しいNDPPカーネル分解を導入することで,空間と時間要件を線形に$M$で学習するアルゴリズムを開発した。 また, 線形複雑度NDPP最大値推定アルゴリズムを新たに開発したカーネルだけでなく, 先行処理にも適用する。
  論文  参考訳（メタデータ） (2020-06-17T13:42:09Z)
• Determinantal Point Processes in Randomized Numerical Linear Algebra [80.27102478796613]
  数値線形代数(RandNLA)は、科学計算、データサイエンス、機械学習などで発生する行列問題に対する改良されたアルゴリズムを開発するためにランダム性を使用する。 最近の研究により、DPPとRandNLAの間の深い実りある関係が明らかになり、新たな保証とアルゴリズムの改善につながった。
  論文  参考訳（メタデータ） (2020-05-07T00:39:52Z)

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

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