論文の概要: Efficiently Learning Markov Random Fields from Dynamics

• arxiv url: http://arxiv.org/abs/2409.05284v1
• Date: Mon, 9 Sep 2024 02:32:45 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-10 16:00:52.357024
• Title: Efficiently Learning Markov Random Fields from Dynamics
• Title（参考訳）: 力学からマルコフランダム場を効果的に学習する
• Authors: Jason Gaitonde, Ankur Moitra, Elchanan Mossel,
• Abstract要約: マルコフ確率場(MRF)の学習パラメータは高次元統計学において重要な課題である。 この問題に関する以前の研究の多くは、MSF分布からのi.d.サンプルへのアクセスを前提としている。 有界なMRFでは、依存構造とパラメータは長さ$O(n log n)$とランタイム$O(n2 log n)$のグラウバー力学の軌跡を用いて復元できることを示す。
• 参考スコア（独自算出の注目度）: 21.976109703401114
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: An important task in high-dimensional statistics is learning the parameters or dependency structure of an undirected graphical model, or Markov random field (MRF). Much of the prior work on this problem assumes access to i.i.d. samples from the MRF distribution and state-of-the-art algorithms succeed using $n^{\Theta(k)}$ runtime, where $n$ is the dimension and $k$ is the order of the interactions. However, well-known reductions from the sparse parity with noise problem imply that given i.i.d. samples from a sparse, order-$k$ MRF, any learning algorithm likely requires $n^{\Omega(k)}$ time, impeding the potential for significant computational improvements. In this work, we demonstrate that these fundamental barriers for learning MRFs can surprisingly be completely circumvented when learning from natural, dynamical samples. We show that in bounded-degree MRFs, the dependency structure and parameters can be recovered using a trajectory of Glauber dynamics of length $O(n \log n)$ with runtime $O(n^2 \log n)$. The implicit constants depend only on the degree and non-degeneracy parameters of the model, but not the dimension $n$. In particular, learning MRFs from dynamics is $\textit{provably computationally easier}$ than learning from i.i.d. samples under standard hardness assumptions.
• Abstract（参考訳）: 高次元統計学における重要な課題は、無向グラフィカルモデルのパラメータや依存構造、すなわちマルコフランダム場(MRF)を学ぶことである。 この問題に関する以前の研究の多くは、MSF分布からのサンプル、すなわち最先端のアルゴリズムへのアクセスを$n^{\Theta(k)}$ランタイムで成功させ、$n$は次元、$k$は相互作用の順序である。 しかし、ノイズ問題によるスパースパリティからのよく知られた還元は、スパース、オーダー-$k$ MRFからのサンプルが与えられた場合、任意の学習アルゴリズムは、おそらくは$n^{\Omega(k)}$時間を必要とすることを示し、大きな計算改善の可能性を妨げている。 本研究では、自然の動的サンプルから学ぶ際に、これらのMRFを学習するための基本的な障壁が驚くほど完全に回避可能であることを実証する。 有界なMRFでは、依存構造とパラメータは、長さ$O(n \log n)$とランタイム$O(n^2 \log n)$のグラウバー力学の軌跡を用いて復元できることを示す。 暗黙定数はモデルの次数と非退化パラメータにのみ依存するが、次元は$n$ではない。 特に、力学から MRF を学ぶことは、標準硬度仮定の下でのサンプルから学ぶよりも、$\textit{provably computerlyly easier}$である。

関連論文リスト

• Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models [49.81937966106691]
  我々は拡散モデルのデータ生成過程を理解するための非漸近理論のスイートを開発する。 従来の研究とは対照的に,本理論は基本的だが多目的な非漸近的アプローチに基づいて開発されている。
  論文  参考訳（メタデータ） (2023-06-15T16:30:08Z)
• Multisample Flow Matching: Straightening Flows with Minibatch Couplings [38.82598694134521]
  連続時間生成モデルを訓練するためのシミュレーション不要な手法は、ノイズ分布と個々のデータサンプルの間の確率経路を構築する。 データとノイズサンプル間の非自明な結合を利用するより一般的なフレームワークであるMultisample Flow Matchingを提案する。 提案手法は,イメージネットデータセットのサンプル一貫性を向上し,低コストなサンプル生成に繋がることを示す。
  論文  参考訳（メタデータ） (2023-04-28T11:33:08Z)
• Smoothly Giving up: Robustness for Simple Models [30.56684535186692]
  このようなモデルをトレーニングするアルゴリズムの例としては、ロジスティック回帰とブースティングがある。 我々は、標準凸損失関数間のチューニングを行う、$Served-Servedジョイント凸損失関数を用いて、そのようなモデルを堅牢に訓練する。 また、ロジスティック回帰のためのCOVID-19データセットを強化し、複数の関連ドメインにまたがる効果のアプローチを強調します。
  論文  参考訳（メタデータ） (2023-02-17T19:48:11Z)
• Learning from aggregated data with a maximum entropy model [73.63512438583375]
  我々は,観測されていない特徴分布を最大エントロピー仮説で近似することにより,ロジスティック回帰と類似した新しいモデルが,集約データからのみ学習されることを示す。 我々は、この方法で学習したモデルが、完全な非凝集データでトレーニングされたロジスティックモデルに匹敵するパフォーマンスを達成することができるという、いくつかの公開データセットに関する実証的な証拠を提示する。
  論文  参考訳（メタデータ） (2022-10-05T09:17:27Z)
• The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
  この仮定から逸脱すると、実際により良い統計的推定結果が得られることが示される。 特に、最適な雑音分布は、データと異なり、また、別の家族からさえも異なる。
  論文  参考訳（メタデータ） (2022-03-02T13:59:20Z)
• An MRF-UNet Product of Experts for Image Segmentation [1.7897459398362972]
  Markovのランダムフィールド(MRF)は、オーバーフィットしやすいラベルよりもシンプルにエンコードします。 UNet と MRF の分布積を計算することにより、両方の戦略を融合させることを提案する。 MRF-UNetはバックプロパゲーションによって共同で訓練される。
  論文  参考訳（メタデータ） (2021-04-12T14:25:32Z)
• Scalable Inference of Sparsely-changing Markov Random Fields with Strong Statistical Guarantees [10.127456032874978]
  スパース変換型MRFの推論に制約付き最適化問題を新たに導入する。 1時間未満で5億以上の変数を持つ疎交換グラフィカルモデルを正確に推定することができる。
  論文  参考訳（メタデータ） (2021-02-06T13:53:00Z)
• Learning based signal detection for MIMO systems with unknown noise statistics [84.02122699723536]
  本論文では,未知のノイズ統計による信号を堅牢に検出する一般化最大確率(ML)推定器を考案する。 実際には、システムノイズに関する統計的な知識はほとんどなく、場合によっては非ガウス的であり、衝動的であり、分析不可能である。 我々のフレームワークは、ノイズサンプルのみを必要とする教師なしの学習アプローチによって駆動される。
  論文  参考訳（メタデータ） (2021-01-21T04:48:15Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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