論文の概要: 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}$である。
関連論文リスト
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。
SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
論文 参考訳(メタデータ) (2024-06-03T17:56:58Z) - Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。
我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
論文 参考訳(メタデータ) (2024-02-21T19:55:01Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳(メタデータ) (2022-03-18T18:50:52Z) - Multimeasurement Generative Models [7.502947376736449]
我々は、密度$p_X$ in $mathbbRd$を未知分布からサンプリングする問題を学習とサンプリングの問題を$p_mathbfY$ in $mathbbRMd$とする。
論文 参考訳(メタデータ) (2021-12-18T02:11:36Z) - Robust Model Selection and Nearly-Proper Learning for GMMs [26.388358539260473]
学習理論では、データは有限混合モデルから生成されるという標準的な仮定がある。しかし、コンポーネントの数が事前に分かっていないときに何が起こるのか。
対数係数内の分布に適合するために必要な最小コンポーネント数を、およそ決定することができる。
論文 参考訳(メタデータ) (2021-06-05T01:58:40Z) - Learning to extrapolate using continued fractions: Predicting the
critical temperature of superconductor materials [5.905364646955811]
人工知能(AI)と機械学習(ML)の分野では、未知のターゲット関数 $y=f(mathbfx)$ の近似が共通の目的である。
トレーニングセットとして$S$を参照し、新しいインスタンス$mathbfx$に対して、このターゲット関数を効果的に近似できる低複雑さの数学的モデルを特定することを目的としている。
論文 参考訳(メタデータ) (2020-11-27T04:57:40Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳(メタデータ) (2020-11-19T17:21:37Z) - Learning Restricted Boltzmann Machines with Sparse Latent Variables [23.521950334858566]
制限ボルツマンマシン(RBM)は、潜在変数を持つ非指向型グラフィカルモデルである。
そこで本研究では,RBMが生成したサンプルを学習する作業について考察する。
時間複雑性を$tildeO(n2s+1)$で学習するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-07T14:42:50Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳(メタデータ) (2020-06-02T16:38:36Z) - Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。
最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-04-30T10:42:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。