Fugu-MT 論文翻訳(概要): Learning bounded-degree polytrees with known skeleton

論文の概要: Learning bounded-degree polytrees with known skeleton

arxiv url: http://arxiv.org/abs/2310.06333v2
Date: Mon, 22 Jan 2024 02:22:12 GMT
ステータス: 処理完了
システム内更新日: 2024-01-23 20:25:42.602089
Title: Learning bounded-degree polytrees with known skeleton
Title（参考訳）: 既知の骨格を持つ有界多樹の学習
Authors: Davin Choo, Joy Qiping Yang, Arnab Bhattacharyya, Cl\'ement L. Canonne
Abstract要約: 有界次数ポリツリーの効率的な適切な学習のための有限サンプル保証を確立する。基礎となる無向グラフが知られているとき、d$-polytreesを時間で学習し、任意の有界$d$のサンプル複雑性を学習する効率的なアルゴリズムを提供する。
参考スコア（独自算出の注目度）: 15.137372516678143
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We establish finite-sample guarantees for efficient proper learning of bounded-degree polytrees, a rich class of high-dimensional probability distributions and a subclass of Bayesian networks, a widely-studied type of graphical model. Recently, Bhattacharyya et al. (2021) obtained finite-sample guarantees for recovering tree-structured Bayesian networks, i.e., 1-polytrees. We extend their results by providing an efficient algorithm which learns $d$-polytrees in polynomial time and sample complexity for any bounded $d$ when the underlying undirected graph (skeleton) is known. We complement our algorithm with an information-theoretic sample complexity lower bound, showing that the dependence on the dimension and target accuracy parameters are nearly tight.
Abstract（参考訳）: 我々は,有界多木,高次元確率分布の豊富なクラス,および広く研究されているグラフィカルモデルであるベイズネットワークのサブクラスを効率的に学習するための有限サンプル保証を確立する。近年、Bhattacharyya et al. (2021) は木構造ベイズネットワーク、すなわち1-ポリツリーを復元するための有限サンプル保証を得た。基礎となる非方向グラフ(スケルトン)が知られているとき、多項式時間で$d$-polytreesを学習し、任意の有界$d$のサンプル複雑性を学習する効率的なアルゴリズムを提供することで、結果を拡張する。このアルゴリズムを,情報理論的なサンプル複雑性下限で補完し,次元や対象の精度パラメータへの依存性がほぼタイトであることを示す。

関連論文リスト

Optimal estimation of Gaussian (poly)trees [25.02920605955238]
分布学習(KL距離)と構造学習(正確な回復)の両問題を考察する。最初のアプローチはChow-Liuアルゴリズムに基づいており、最適な木構造分布を効率的に学習する。第2のアプローチは、制約に基づく構造学習のための条件付き独立試験器として部分相関を用いたポリツリーに対するPCアルゴリズムの修正である。
論文参考訳（メタデータ） (2024-02-09T12:58:36Z)
Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
論文参考訳（メタデータ） (2023-05-24T11:05:12Z)
Learning Linear Non-Gaussian Polytree Models [2.4493299476776778]
ポリツリーであるグラフを効率的に学習するアルゴリズムを提案する。提案手法は,まず無向木構造を学習するChow-Liuアルゴリズムと,エッジを指向する新しいスキームを組み合わせたものである。
論文参考訳（メタデータ） (2022-08-13T18:20:10Z)
Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
論文参考訳（メタデータ） (2021-10-28T14:59:41Z)
Efficient Bayesian network structure learning via local Markov boundary search [17.1764265047364]
本研究では,特定の分布仮定を伴わない観測データから,非循環型図形学習の複雑さを解析する。局所マルコフ境界探索法を用いて、基礎となるグラフィカルモデルに祖先集合を構築する。我々のアプローチは一般に、離散的あるいは連続的な分布を分布の仮定なしで処理し、データから有向グラフモデルの構造を効率的に学習するのに必要となる最小限の仮定に光を当てる。
論文参考訳（メタデータ） (2021-10-12T15:33:59Z)
Learning Linear Polytree Structural Equation Models [4.833417613564028]
我々は、線形構造方程式モデル(SEM)からデータを生成する際に、有向非巡回グラフ(DAG)を学習する問題に興味を持っている。我々は、よく知られたChow-Liuアルゴリズムのサンプルサイズについて十分な条件について検討し、ポリツリーの骨格と等価クラスの両方を正確に復元する。また、各ノードが変数群を表すような群線型ポリツリーモデルの拡張も検討する。
論文参考訳（メタデータ） (2021-07-22T23:22:20Z)
Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
論文参考訳（メタデータ） (2021-06-08T00:57:59Z)
Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。 RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
論文参考訳（メタデータ） (2021-06-02T01:37:52Z)
SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。 Katiyarら。 (2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
論文参考訳（メタデータ） (2021-01-22T01:57:35Z)
Sample-Optimal and Efficient Learning of Tree Ising models [24.201827888085944]
最適な$O(n ln n/epsilon2)$サンプルから,$n$-variable tree-structured Isingモデルが全変動距離$epsilon$の範囲内で計算効率良く学習可能であることを示す。我々の保証は、Chow-Liuアルゴリズムの既知の結果に従わない。
論文参考訳（メタデータ） (2020-10-28T10:17:48Z)
Convex Polytope Trees [57.56078843831244]
コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
論文参考訳（メタデータ） (2020-10-21T19:38:57Z)

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