論文の概要: Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes

• arxiv url: http://arxiv.org/abs/2006.09862v2
• Date: Tue, 13 Apr 2021 15:16:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-19 19:43:34.921377
• Title: Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes
• Title（参考訳）: 非対称決定点過程に対するスケーラブル学習とMAP推論
• Authors: Mike Gartrell, Insu Han, Elvis Dohmatob, Jennifer Gillenwater, Victor-Emmanuel Brunel
• Abstract要約: 我々は新しいNDPPカーネル分解を導入することで,空間と時間要件を線形に$M$で学習するアルゴリズムを開発した。 また, 線形複雑度NDPP最大値推定アルゴリズムを新たに開発したカーネルだけでなく, 先行処理にも適用する。
• 参考スコア（独自算出の注目度）: 29.56615511158156
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Determinantal point processes (DPPs) have attracted significant attention in machine learning for their ability to model subsets drawn from a large item collection. Recent work shows that nonsymmetric DPP (NDPP) kernels have significant advantages over symmetric kernels in terms of modeling power and predictive performance. However, for an item collection of size $M$, existing NDPP learning and inference algorithms require memory quadratic in $M$ and runtime cubic (for learning) or quadratic (for inference) in $M$, making them impractical for many typical subset selection tasks. In this work, we develop a learning algorithm with space and time requirements linear in $M$ by introducing a new NDPP kernel decomposition. We also derive a linear-complexity NDPP maximum a posteriori (MAP) inference algorithm that applies not only to our new kernel but also to that of prior work. Through evaluation on real-world datasets, we show that our algorithms scale significantly better, and can match the predictive performance of prior work.
• Abstract（参考訳）: 決定点過程 (Determinantal point process, DPP) は、大規模なアイテムコレクションから引き出されたサブセットをモデル化できる機械学習において大きな注目を集めている。 最近の研究は、非対称DPP(NDPP)カーネルがモデリング能力と予測性能の点で対称カーネルに対して大きな優位性を持っていることを示している。 しかし、$M$のアイテムコレクションでは、既存のNDPP学習と推論アルゴリズムは$M$のメモリ2乗と、$M$のランタイム立方体(学習)と$M$の2乗を必要とするため、多くの典型的なサブセット選択タスクでは非現実的である。 本研究では,新しいNDPPカーネル分解を導入することで,空間と時間要件を線形に$M$で学習するアルゴリズムを開発した。 また、線形複雑度ndppを最大化することで、新しいカーネルだけでなく、以前の作業にも適用される後続(map)推論アルゴリズムを導出する。 実世界のデータセットを評価することで,アルゴリズムのスケールが大幅に向上し,先行作業の予測性能に匹敵することを示す。

関連論文リスト

• Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles [39.10180309328293]
  本稿では,特徴選択の観点から線形MDPを再考する。 我々の主な成果は、この問題に対する最初のアルゴリズムである。 コンベックスプログラミングによって効率よく計算できることを示す。
  論文  参考訳（メタデータ） (2023-09-18T03:35:48Z)
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  部分的に観測可能なマルコフ決定過程(POMDP)における表現学習の研究 まず,不確実性(OFU)に直面した最大推定(MLE)と楽観性を組み合わせた復調性POMDPのアルゴリズムを提案する。 次に、このアルゴリズムをより広範な$gamma$-observable POMDPのクラスで機能させる方法を示す。
  論文  参考訳（メタデータ） (2023-06-21T16:04:03Z)
• Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes [45.40646054226403]
  決定点プロセス(DPP)は、$n$アイテムの全てのサブセットに確率を割り当てる。 最近の研究は、NDPPに対する近似連鎖モンテカルロサンプリングアルゴリズムを、サイズ-k$サブセットに限定して研究している。 低ランクカーネルを持つ$k$-NDPPに対するスケーラブルなMCMCサンプリングアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-07-01T15:22:12Z)
• Scalable Sampling for Nonsymmetric Determinantal Point Processes [47.18450267217498]
  M$アイテムの集合上の決定点過程(DPP)は、対称的なカーネル行列によってパラメータ化されるモデルである。 最近の研究は、非対称DPP(NDPPs)を生じるカーネル対称性の制約を取り除くことで、機械学習アプリケーションにおいて大幅な性能向上が期待できることを示している。 コールスキー分解に基づくDPPサンプリングアルゴリズムは1つしか知られておらず、NDPPにも直接適用できる。 NDPPカーネルに特定の構造的制約を課すことで、カーネルのランクに依存する方法で拒絶率を制限できることが示される。
  論文  参考訳（メタデータ） (2022-01-20T19:21:59Z)
• Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
  我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。 我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。 また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
  論文  参考訳（メタデータ） (2021-02-17T18:54:08Z)
• Simple and Near-Optimal MAP Inference for Nonsymmetric DPPs [3.3504365823045044]
  非対称なカーネル行列によって定義される決定点過程に対する最大後続推定(MAP)問題について検討する。 局所探索を用いてこの問題に対する最初の乗法近似保証を得る。 近似係数が$kO(k)$ に近いので、理論上、実験的に、この問題に対する最先端の手法と好適に比較できることが示される。
  論文  参考訳（メタデータ） (2021-02-10T09:34:44Z)
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
  本稿では,割引決定(MDP)のための強化学習について検討する。 本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。 以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-23T17:08:54Z)
• Determinantal Point Processes in Randomized Numerical Linear Algebra [80.27102478796613]
  数値線形代数(RandNLA)は、科学計算、データサイエンス、機械学習などで発生する行列問題に対する改良されたアルゴリズムを開発するためにランダム性を使用する。 最近の研究により、DPPとRandNLAの間の深い実りある関係が明らかになり、新たな保証とアルゴリズムの改善につながった。
  論文  参考訳（メタデータ） (2020-05-07T00:39:52Z)

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

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