論文の概要: Determinantal Point Processes in Randomized Numerical Linear Algebra

• arxiv url: http://arxiv.org/abs/2005.03185v1
• Date: Thu, 7 May 2020 00:39:52 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-06 00:10:59.852061
• Title: Determinantal Point Processes in Randomized Numerical Linear Algebra
• Title（参考訳）: ランダム化数値線形代数における決定点過程
• Authors: Micha{\l} Derezi\'nski and Michael W. Mahoney
• Abstract要約: 数値線形代数(RandNLA)は、科学計算、データサイエンス、機械学習などで発生する行列問題に対する改良されたアルゴリズムを開発するためにランダム性を使用する。 最近の研究により、DPPとRandNLAの間の深い実りある関係が明らかになり、新たな保証とアルゴリズムの改善につながった。
• 参考スコア（独自算出の注目度）: 80.27102478796613
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Randomized Numerical Linear Algebra (RandNLA) uses randomness to develop improved algorithms for matrix problems that arise in scientific computing, data science, machine learning, etc. Determinantal Point Processes (DPPs), a seemingly unrelated topic in pure and applied mathematics, is a class of stochastic point processes with probability distribution characterized by sub-determinants of a kernel matrix. Recent work has uncovered deep and fruitful connections between DPPs and RandNLA which lead to new guarantees and improved algorithms that are of interest to both areas. We provide an overview of this exciting new line of research, including brief introductions to RandNLA and DPPs, as well as applications of DPPs to classical linear algebra tasks such as least squares regression, low-rank approximation and the Nystr\"om method. For example, random sampling with a DPP leads to new kinds of unbiased estimators for least squares, enabling more refined statistical and inferential understanding of these algorithms; a DPP is, in some sense, an optimal randomized algorithm for the Nystr\"om method; and a RandNLA technique called leverage score sampling can be derived as the marginal distribution of a DPP. We also discuss recent algorithmic developments, illustrating that, while not quite as efficient as standard RandNLA techniques, DPP-based algorithms are only moderately more expensive.
• Abstract（参考訳）: ランダム化された数値線形代数(RandNLA)は、科学計算、データサイエンス、機械学習などで生じる行列問題に対する改良されたアルゴリズムを開発するためにランダム性を利用する。 決定点過程 (Determinantal Point Processes, DPPs) は、純粋および応用数学において、カーネル行列のサブ行列式によって特徴づけられる確率分布を持つ確率点過程のクラスである。 最近の研究により、DPPとRandNLAの間の深い実りある関係が明らかになり、両方の分野に関心を持つ新たな保証とアルゴリズムの改善につながった。 我々は、RandNLAとDPPの簡単な紹介や、最小二乗回帰、低ランク近似、Nystr\"om法といった古典線形代数問題へのDPPの適用を含む、このエキサイティングな新しい研究ラインの概要を述べる。 例えば、DPPを用いたランダムサンプリングは、最小二乗に対する新しい種類の非バイアス推定を導き、これらのアルゴリズムのより洗練された統計的および推論的理解を可能にし、ある意味では、Nystr\"om法のための最適なランダム化アルゴリズムであり、レバレッジスコアサンプリングと呼ばれるRandNLA手法は、DPPの限界分布として導出することができる。 また、最近のアルゴリズム開発についても論じ、標準RandNLA技術ほど効率的ではないが、DPPベースのアルゴリズムは適度に高価である。

関連論文リスト

• Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning [49.0767291348921]
  RandNLA (Randomized Numerical Linear Algebra) は、ランダムネスを用いてユビキタス行列問題に対する改良アルゴリズムを開発する分野である。 この記事では、これらの開発状況を踏まえた自己完結したRandNLAの概要を紹介する。
  論文  参考訳（メタデータ） (2024-06-17T02:30:55Z)
• Online Learning Under A Separable Stochastic Approximation Framework [20.26530917721778]
  分離可能な近似フレームワークを用いて,機械学習モデルのクラスに対するオンライン学習アルゴリズムを提案する。 提案アルゴリズムは,他の一般的な学習アルゴリズムと比較して,より堅牢でテスト性能が高いことを示す。
  論文  参考訳（メタデータ） (2023-05-12T13:53:03Z)
• Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes [45.40646054226403]
  決定点プロセス(DPP)は、$n$アイテムの全てのサブセットに確率を割り当てる。 最近の研究は、NDPPに対する近似連鎖モンテカルロサンプリングアルゴリズムを、サイズ-k$サブセットに限定して研究している。 低ランクカーネルを持つ$k$-NDPPに対するスケーラブルなMCMCサンプリングアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-07-01T15:22:12Z)
• Generalization Bounds for Data-Driven Numerical Linear Algebra [24.961270871124217]
  データ駆動アルゴリズムは、トレーニングされた入力サンプルから学習することで、未知のアプリケーション固有の分布からの入力に内部構造やパラメータを適用することができる。 いくつかの最近の研究は、数値線形代数における問題にこのアプローチを適用し、性能において顕著な経験的利得を得た。 本研究では、Gupta と Roughgarden が提案するデータ駆動アルゴリズム選択のためのPAC学習フレームワークにおいて、これらのアルゴリズムの一般化境界を証明する。
  論文  参考訳（メタデータ） (2022-06-16T02:23:45Z)
• Photonic co-processors in HPC: using LightOn OPUs for Randomized Numerical Linear Algebra [53.13961454500934]
  従来のハードウェアでは,次元削減のためのランダム化ステップ自体が計算ボトルネックとなる可能性がある。 ランダム化は,様々な重要なrandnlaアルゴリズムにおいて,精度損失が無視できないほど大幅に高速化できることを示す。
  論文  参考訳（メタデータ） (2021-04-29T15:48:52Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes [29.56615511158156]
  我々は新しいNDPPカーネル分解を導入することで,空間と時間要件を線形に$M$で学習するアルゴリズムを開発した。 また, 線形複雑度NDPP最大値推定アルゴリズムを新たに開発したカーネルだけでなく, 先行処理にも適用する。
  論文  参考訳（メタデータ） (2020-06-17T13:42:09Z)

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

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