論文の概要: Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics

• arxiv url: http://arxiv.org/abs/2409.05284v2
• Date: Mon, 4 Nov 2024 18:37:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-07 22:38:45.432884
• Title: Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
• Title（参考訳）: 雑音の多いパリティバリアをバイパスする:ダイナミクスから高次マルコフランダム場を学習する
• Authors: Jason Gaitonde, Ankur Moitra, Elchanan Mossel,
• Abstract要約: 我々は、時間的相関サンプルからマルコフランダムフィールド(MRF)として知られるグラフィカルモデルを学ぶことの問題を考察する。 特に,Glauberのダイナミックスから,$widetildeO_k(n)$サイトの更新を$k$ MRFで行うと,$widetildeO_k(n2)$時間でグラフとパラメータを復元するアルゴリズムが存在することを示す。 私たちの結果は、MDFのより現実的で直感的に少ないモデルが、実際には効率をはるかに上回っていることを、驚くほど示しています。
• 参考スコア（独自算出の注目度）: 21.976109703401114
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of learning graphical models, also known as Markov random fields (MRFs) from temporally correlated samples. As in many traditional statistical settings, fundamental results in the area all assume independent samples from the distribution. However, these samples generally will not directly correspond to more realistic observations from nature, which instead evolve according to some stochastic process. From the computational lens, even generating a single sample from the true MRF distribution is intractable unless $\mathsf{NP}=\mathsf{RP}$, and moreover, any algorithm to learn from i.i.d. samples requires prohibitive runtime due to hardness reductions to the parity with noise problem. These computational barriers for sampling and learning from the i.i.d. setting severely lessen the utility of these breakthrough results for this important task; however, dropping this assumption typically only introduces further algorithmic and statistical complexities. In this work, we surprisingly demonstrate that the direct trajectory data from a natural evolution of the MRF overcomes the fundamental computational lower bounds to efficient learning. In particular, we show that given a trajectory with $\widetilde{O}_k(n)$ site updates of an order $k$ MRF from the Glauber dynamics, a well-studied, natural stochastic process on graphical models, there is an algorithm that recovers the graph and the parameters in $\widetilde{O}_k(n^2)$ time. By contrast, all prior algorithms for learning order $k$ MRFs inherently suffer from $n^{\Theta(k)}$ runtime even in sparse instances due to the reductions to sparse parity with noise. Our results thus surprisingly show that this more realistic, but intuitively less tractable, model for MRFs actually leads to efficiency far beyond what is known and believed to be true in the traditional i.i.d. case.
• Abstract（参考訳）: 我々は、時間的相関サンプルからマルコフランダムフィールド(MRF)として知られるグラフィカルモデルを学ぶことの問題を考察する。 多くの伝統的な統計設定と同様に、地域の基本的な結果は、分布から独立したサンプルを仮定する。 しかし、これらのサンプルは一般的に自然からのより現実的な観察と直接対応せず、確率的なプロセスに従って進化する。 計算レンズから、真のMRF分布から1つのサンプルを生成することさえも、$\mathsf{NP}=\mathsf{RP}$でなければ難解であり、さらに、サンプルから学ぶアルゴリズムは、ノイズ問題によるパリティによる硬度減少のために禁止的な実行を必要とする。 サンプリングと学習のためのこれらの計算障壁は、この重要なタスクにおいて、これらのブレークスルー結果の有用性を著しく低下させるが、この仮定を廃止することは、通常、さらなるアルゴリズム的および統計的複雑さをもたらすだけである。 本研究では, MRFの自然な進化から得られる直接軌跡データが, 計算的下界を克服し, 効率的な学習を行うことを示す。 特に、グラウバー力学による$\widetilde{O}_k(n)$のサイト更新、グラフィカルモデル上のよく研究された自然な確率過程、および$\widetilde{O}_k(n^2)$時間のグラフとパラメータを復元するアルゴリズムがあることが示されている。 対照的に、学習順序$k$ MRFの前のアルゴリズムは全て、ノイズを伴うスパースパリティの低減によるスパースインスタンスにおいても、本質的には$n^{\Theta(k)}$ランタイムに悩まされている。 我々の結果は、このより現実的だが直感的に、MSFのモデルは、伝統的なi.i.d.の場合において、知られていることや真実であると信じられているものよりもはるかに効率が良いことを示している。

関連論文リスト

• 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)

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

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