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

• arxiv url: http://arxiv.org/abs/2207.00486v1
• Date: Fri, 1 Jul 2022 15:22:12 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-04 13:05:57.270492
• Title: Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes
• Title（参考訳）: 非対称決定点過程に対するスケーラブルMCMCサンプリング
• Authors: Insu Han, Mike Gartrell, Elvis Dohmatob, Amin Karbasi
• Abstract要約: 決定点プロセス(DPP)は、$n$アイテムの全てのサブセットに確率を割り当てる。 最近の研究は、NDPPに対する近似連鎖モンテカルロサンプリングアルゴリズムを、サイズ-k$サブセットに限定して研究している。 低ランクカーネルを持つ$k$-NDPPに対するスケーラブルなMCMCサンプリングアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 45.40646054226403
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A determinantal point process (DPP) is an elegant model that assigns a probability to every subset of a collection of $n$ items. While conventionally a DPP is parameterized by a symmetric kernel matrix, removing this symmetry constraint, resulting in nonsymmetric DPPs (NDPPs), leads to significant improvements in modeling power and predictive performance. Recent work has studied an approximate Markov chain Monte Carlo (MCMC) sampling algorithm for NDPPs restricted to size-$k$ subsets (called $k$-NDPPs). However, the runtime of this approach is quadratic in $n$, making it infeasible for large-scale settings. In this work, we develop a scalable MCMC sampling algorithm for $k$-NDPPs with low-rank kernels, thus enabling runtime that is sublinear in $n$. Our method is based on a state-of-the-art NDPP rejection sampling algorithm, which we enhance with a novel approach for efficiently constructing the proposal distribution. Furthermore, we extend our scalable $k$-NDPP sampling algorithm to NDPPs without size constraints. Our resulting sampling method has polynomial time complexity in the rank of the kernel, while the existing approach has runtime that is exponential in the rank. With both a theoretical analysis and experiments on real-world datasets, we verify that our scalable approximate sampling algorithms are orders of magnitude faster than existing sampling approaches for $k$-NDPPs and NDPPs.
• Abstract（参考訳）: 決定点過程 (Determinantal point process, DPP) は、$n$アイテムの集合の全ての部分集合に確率を割り当てるエレガントなモデルである。 従来、dppは対称カーネル行列によってパラメータ化されるが、この対称性の制約を取り除いて非対称dpps(nonsymmetric dpps)となり、モデリング能力と予測性能が大幅に向上する。 最近の研究は、NDPPのサイズ-$k$サブセット($k$-NDPPs)に制限されたNDPPに対する近似マルコフ連鎖モンテカルロ(MCMC)サンプリングアルゴリズムを研究している。 しかし、このアプローチのランタイムは$n$で2倍になり、大規模な設定では実現不可能である。 本研究では,低ランクカーネルを持つ$k$-NDPPに対するスケーラブルなMCMCサンプリングアルゴリズムを開発し,$n$でサブリニアなランタイムを実現する。 提案手法は最先端ndppリジェクションサンプリングアルゴリズムに基づいており,提案手法を効率的に構築するための新しい手法により拡張する。 さらに,拡張可能な$k$-NDPPサンプリングアルゴリズムを,サイズ制約のないNDPPに拡張する。 得られたサンプリング手法はカーネルのランクにおいて多項式時間の複雑さを持ち,既存の手法では指数関数的な実行時間を持つ。 実世界のデータセットに関する理論的解析と実験により、我々のスケーラブルな近似サンプリングアルゴリズムは、$k$-NDPPsとNDPPsの既存のサンプリング手法よりも桁違いに高速であることを確認した。

関連論文リスト

• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-01-26T22:09:59Z)
• Scalable Sampling for Nonsymmetric Determinantal Point Processes [47.18450267217498]
  M$アイテムの集合上の決定点過程(DPP)は、対称的なカーネル行列によってパラメータ化されるモデルである。 最近の研究は、非対称DPP(NDPPs)を生じるカーネル対称性の制約を取り除くことで、機械学習アプリケーションにおいて大幅な性能向上が期待できることを示している。 コールスキー分解に基づくDPPサンプリングアルゴリズムは1つしか知られておらず、NDPPにも直接適用できる。 NDPPカーネルに特定の構造的制約を課すことで、カーネルのランクに依存する方法で拒絶率を制限できることが示される。
  論文  参考訳（メタデータ） (2022-01-20T19:21:59Z)
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs [39.01663172393174]
  生成モデルにアクセス可能な無限水平平均回帰マルコフ決定過程の最適方針を求める。 状態-作用対あたりのサンプルを$widetildeO(t_mathrmmix epsilon-3)$ (oblivious) で解決するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-13T17:18:11Z)
• Simple and Near-Optimal MAP Inference for Nonsymmetric DPPs [3.3504365823045044]
  非対称なカーネル行列によって定義される決定点過程に対する最大後続推定(MAP)問題について検討する。 局所探索を用いてこの問題に対する最初の乗法近似保証を得る。 近似係数が$kO(k)$ に近いので、理論上、実験的に、この問題に対する最先端の手法と好適に比較できることが示される。
  論文  参考訳（メタデータ） (2021-02-10T09:34:44Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• 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)

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

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