論文の概要: Learnability of Parameter-Bounded Bayes Nets

• arxiv url: http://arxiv.org/abs/2407.00927v2
• Date: Sun, 4 Aug 2024 18:04:50 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-06 20:28:55.198899
• Title: Learnability of Parameter-Bounded Bayes Nets
• Title（参考訳）: パラメータ境界ベイズネットの学習可能性
• Authors: Arnab Bhattacharyya, Davin Choo, Sutanu Gayen, Dimitrios Myrisiotis,
• Abstract要約: LEARNの$mathsfNP$-hardnessの結果を証明し、LEARNのpromise search variantの$mathsfNP$-hardnessを証明する。 パラメータ有界ベイズネットを回復するのに十分なサンプルの複雑さに関する正の結果で、硬さの結果を補完する。
• 参考スコア（独自算出の注目度）: 14.01376675905243
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bayes nets are extensively used in practice to efficiently represent joint probability distributions over a set of random variables and capture dependency relations. In a seminal paper, Chickering et al. (JMLR 2004) showed that given a distribution $\mathbb{P}$, that is defined as the marginal distribution of a Bayes net, it is $\mathsf{NP}$-hard to decide whether there is a parameter-bounded Bayes net that represents $\mathbb{P}$. They called this problem LEARN. In this work, we extend the $\mathsf{NP}$-hardness result of LEARN and prove the $\mathsf{NP}$-hardness of a promise search variant of LEARN, whereby the Bayes net in question is guaranteed to exist and one is asked to find such a Bayes net. We complement our hardness result with a positive result about the sample complexity that is sufficient to recover a parameter-bounded Bayes net that is close (in TV distance) to a given distribution $\mathbb{P}$, that is represented by some parameter-bounded Bayes net, generalizing a degree-bounded sample complexity result of Brustle et al. (EC 2020).
• Abstract（参考訳）: ベイズネットは実際には、ランダム変数の集合上の結合確率分布を効率的に表現し、依存関係を捉えるために広く使われている。 Chickering et al (JMLR 2004) は、ベイズネットの辺分布として定義される分布 $\mathbb{P}$ が与えられたとき、$\mathbb{P}$ を表すパラメータ有界ベイズネットが存在するかどうかを決定するために$\mathsf{NP}$-hard であることを示した。 彼らはこの問題をLEARNと呼んだ。 本研究では、LEARN の $\mathsf{NP}$-hardness 結果を拡張し、LEARN のpromise search variant の $\mathsf{NP}$-hardness を証明する。 我々は、パラメータ有界ベイズネットをパラメータ有界ベイズネット(EC 2020)で表される所定の分布に(テレビ距離で)近いパラメータ有界ベイズネットを復元するのに十分であるサンプル複雑性に関する正の結果を補足する。

関連論文リスト

• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Near-Optimal Degree Testing for Bayes Nets [6.814860712547177]
  問題の複雑さのサンプルは$tildeTheta (2n/2/varepsilon2)$である。 我々のアルゴリズムは、これまでサンプル最適化テスターの獲得に用いられてきたテスト・バイ・ラーニング・フレームワークに依存している。
  論文  参考訳（メタデータ） (2023-04-13T03:48:31Z)
• On counterfactual inference with unobserved confounding [36.18241676876348]
  独立だが不均一な単位を持つ観測的研究を前提として、各単位の反実分布を学習することが目的である。 我々は、すべての$n$サンプルをプールして、すべての$n$パラメータベクトルを共同で学習する凸目的を導入する。 対数的ソボレフ不等式を満たすためにコンパクトに支持された分布に対して十分な条件を導出する。
  論文  参考訳（メタデータ） (2022-11-14T04:14:37Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• Robust Estimation for Nonparametric Families via Generative Adversarial Networks [92.64483100338724]
  我々は,高次元ロバストな統計問題を解くためにGAN(Generative Adversarial Networks)を設計するためのフレームワークを提供する。 我々の研究は、これらをロバスト平均推定、第二モーメント推定、ロバスト線形回帰に拡張する。 技術面では、提案したGAN損失は、スムーズで一般化されたコルモゴロフ-スミルノフ距離と見なすことができる。
  論文  参考訳（メタデータ） (2022-02-02T20:11:33Z)
• Non-Gaussian Component Analysis via Lattice Basis Reduction [56.98280399449707]
  非ガウス成分分析(NGCA)は分布学習問題である。 我々は,NGCA に対して,$A$ が離散的あるいはほぼ離散的であるような効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-12-16T18:38:02Z)
• Sparse online variational Bayesian regression [0.0]
  完全ベイズアプローチに代わる安価でスケーラブルな代替手段としてのバリエーションベイズ推論。 線形モデルの場合、この方法は決定論的最小二乗問題の反復解のみを必要とする。 大きな p の場合、近似は計算とメモリの両方において o(p) のコストの有望な結果が得られる。
  論文  参考訳（メタデータ） (2021-02-24T12:49:42Z)
• Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$ [5.457150493905064]
  ガウス下収束を考慮した新しい推定器を提案する。 我々の推定器はその分散に関する事前の知識を必要としない。 我々の推定器の構成と分析は、他の問題に一般化可能なフレームワークを提供する。
  論文  参考訳（メタデータ） (2020-11-17T02:47:24Z)
• Neural Bayes: A Generic Parameterization Method for Unsupervised Representation Learning [175.34232468746245]
  本稿ではニューラルベイズと呼ばれるパラメータ化手法を提案する。 これは一般に計算が難しい統計量の計算を可能にする。 このパラメータ化のための2つの独立したユースケースを示す。
  論文  参考訳（メタデータ） (2020-02-20T22:28:53Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  確率分布が未知な分布の不確実性の下でBQOについて検討する。 標準的なBQOアプローチは、固定されたサンプル集合が与えられたときの真の期待目標のモンテカルロ推定を最大化する。 この目的のために,新しい後方サンプリングに基づくアルゴリズム,すなわち分布的に堅牢なBQO(DRBQO)を提案する。
  論文  参考訳（メタデータ） (2020-01-19T12:00:33Z)

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

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