論文の概要: Exact and Approximate Algorithms for Polytree Learning

• arxiv url: http://arxiv.org/abs/2605.03622v1
• Date: Tue, 05 May 2026 10:50:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-06 19:35:43.902307
• Title: Exact and Approximate Algorithms for Polytree Learning
• Title（参考訳）: ポリツリー学習のためのエクササイズアルゴリズムと近似アルゴリズム
• Authors: Juha Harviainen, Frank Sommer, Manuel Sorge,
• Abstract要約: ポリツリーは、有向森林として$n$変数の集合間の条件依存を捉えようとするベイズネットワークのサブクラスである。 最適なポリツリーを学習する問題はNPハードであるため、どの制限がより引きやすいか研究する。 任意に小さい$> 0$と任意の定数の直交境界に対して、時間$O((2+)n)$で最適なポリツリーを求めるアルゴリズムを考案する。
• 参考スコア（独自算出の注目度）: 9.426097667758627
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of $n$ variables as a directed forest and are motivated by their more efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it more tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms. We devise an algorithm that finds the optimal polytree in time $O((2+ε)^n)$ for arbitrarily small $ε> 0$ and any constant in-degree bound $k$, improving over the fastest previously known algorithm of time complexity $O(3^n)$. We further give polynomial-time algorithms for finding a polytree whose score is within a factor of $k$ from the optimal one for arbitrary scores and a factor of $2$ for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.
• Abstract（参考訳）: ポリツリーは、有向森林としての$n$変数の集合間の条件依存性を捉えようとするベイズネットワークのサブクラスであり、より効率的な推論と解釈可能性の向上によって動機付けられる。 最適なポリツリーを学習する問題はNPハードであるため、例えば、直交境界、ポリツリーの品質を計測するスコア関数の特性、近似アルゴリズムなどを考慮して、どの制限がより魅力的かを検討する。 任意に小さな$ε> 0$ と任意の定数の in-degree bound $k$ に対して、最適ポリツリー時間$O((2+ε)^n)$ を求めるアルゴリズムを考案し、より高速に知られている時間複雑性のアルゴリズム$O(3^n)$ より改良する。 さらに、任意のスコアに対する最適値からスコアが$k$以内のポリツリーを見つけるための多項式時間アルゴリズムと、加算値に対して$2$の係数を与える。 結果の多くは、時間複雑性または近似係数のどちらかに対して(ほぼ)厳密な下限によって補完される。

関連論文リスト

• Fast decision tree learning solves hard coding-theoretic problems [7.420043502440765]
  我々は、Ehrenfeucht と Haussler のアルゴリズムの改善により、$k$-NCP に対して$O(log n)$-approximation アルゴリズムが得られることを示す。 これは、$k$-NCPのアルゴリズムを設計するための新しい道、あるいはEhrenfeucht と Haussler のアルゴリズムの最適性を確立するための道と解釈できる。
  論文  参考訳（メタデータ） (2024-09-19T21:40:57Z)
• 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)
• On Computing Optimal Tree Ensembles [7.424944196676223]
  ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。 最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。 2つの新しいアルゴリズムと対応する下位境界を提供する。
  論文  参考訳（メタデータ） (2023-06-07T13:30:43Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• 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)

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

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