論文の概要: On the Parameterized Complexity of Polytree Learning

• arxiv url: http://arxiv.org/abs/2105.09675v1
• Date: Thu, 20 May 2021 11:29:12 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-21 17:00:10.763982
• Title: On the Parameterized Complexity of Polytree Learning
• Title（参考訳）: 多木学習のパラメータ化複雑性について
• Authors: Niels Gr\"uttemeier, Christian Komusiewicz, Nils Morawietz
• Abstract要約: データサイエンスの基本的な課題は、観測データからベイズネットワークを学ぶことである。 textscPolytree Learningは3n cdot |I|mathcalO(1)$ timeで解けることを示す。
• 参考スコア（独自算出の注目度）: 4.060731229044571
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A Bayesian network is a directed acyclic graph that represents statistical dependencies between variables of a joint probability distribution. A fundamental task in data science is to learn a Bayesian network from observed data. \textsc{Polytree Learning} is the problem of learning an optimal Bayesian network that fulfills the additional property that its underlying undirected graph is a forest. In this work, we revisit the complexity of \textsc{Polytree Learning}. We show that \textsc{Polytree Learning} can be solved in $3^n \cdot |I|^{\mathcal{O}(1)}$ time where $n$ is the number of variables and $|I|$ is the total instance size. Moreover, we consider the influence of the number of variables $d$ that might receive a nonempty parent set in the final DAG on the complexity of \textsc{Polytree Learning}. We show that \textsc{Polytree Learning} has no $f(d)\cdot |I|^{\mathcal{O}(1)}$-time algorithm, unlike Bayesian network learning which can be solved in $2^d \cdot |I|^{\mathcal{O}(1)}$ time. We show that, in contrast, if $d$ and the maximum parent set size are bounded, then we can obtain efficient algorithms.
• Abstract（参考訳）: ベイズネットワークは、共役確率分布の変数間の統計的依存関係を表す有向非巡回グラフである。 データサイエンスの基本的な課題は、観測データからベイズネットワークを学ぶことである。 \textsc{polytree learning} は、基礎となる無向グラフが森である追加プロパティを満たす最適なベイズネットワークを学ぶ問題である。 本研究では,textsc{Polytree Learning}の複雑さを再考する。 我々は、$n$が変数の数、$|I|$が全インスタンスサイズである場合、$3^n \cdot |I|^{\mathcal{O}(1)}$ で \textsc{Polytree Learning} を解くことができることを示した。 さらに、最終DAGの空でない親集合を受信する$d$変数の数が、 \textsc{Polytree Learning} の複雑さに与える影響についても検討する。 2^d \cdot |i|^{\mathcal{o}(1)}$ time で解くベイジアンネットワーク学習とは異なり、 \textsc{polytree learning} は$f(d)\cdot |i|^{\mathcal{o}(1)}$-timeアルゴリズムを持たない。 対照的に、$d$ と最大親集合のサイズが有界であれば、効率的なアルゴリズムを得ることができる。

関連論文リスト

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Most Neural Networks Are Almost Learnable [52.40331776572531]
  固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。 このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。 シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
  論文  参考訳（メタデータ） (2023-05-25T22:27:42Z)
• Learning and Covering Sums of Independent Random Variables with Unbounded Support [4.458210211781738]
  独立整数値確率変数の和 $X = X_1 + cdots + X_n$ を非有界、あるいは無限なサポートでカバーし、学習する問題について検討する。 我々は、$X_i$sの集合的サポートの最大値が、必ずしも$X$を学習する際のサンプルの複雑さに現れることを示した。
  論文  参考訳（メタデータ） (2022-10-24T15:03:55Z)
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing [5.117810469621253]
  ランダム化されたETHの下では、2つの基本的な問題に対して超ポリノミカルな下界が証明される。 その結果, 分散自由なPAC学習と決定木の試験において, 新たな下位境界が示唆された。 学習決定木の境界の低さを$nOmega(log s)$に改善できることを示します。
  論文  参考訳（メタデータ） (2022-10-12T16:25:48Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
  我々は、$rho$が少なくとも0.8$である場合に、エラー指数を少なくとも40%向上させるアルゴリズムを設計し、分析する。 我々の分析は、グラフの一部により多くのデータを割り当てるために、微小だが検出可能なサンプルの統計的変動を巧みに活用することに基づいている。
  論文  参考訳（メタデータ） (2021-10-27T10:45:21Z)
• Testing network correlation efficiently via counting trees [19.165942326142538]
  本稿では,2つのネットワークがエッジ関連であるかどうかを潜時対応によって検証する新しい手法を提案する。 テスト統計は、非同型木族に対する符号付き木の共起を数えることに基づいている。
  論文  参考訳（メタデータ） (2021-10-22T14:47:20Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• An Algorithm for Learning Smaller Representations of Models With Scarce Data [0.0]
  データセットが小さすぎるか、完全に代表的でない状況下で、二項分類問題を解くための欲求的アルゴリズムを提案する。 それは、ゆるやかな精度の制約、反復的なハイパーパラメータプルーニング手順、新しいデータを生成するために使われる関数といった訓練されたモデルに依存している。
  論文  参考訳（メタデータ） (2020-10-15T19:17:51Z)
• Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries [55.28642461328172]
  平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
  論文  参考訳（メタデータ） (2020-06-25T19:59:24Z)

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

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