論文の概要: Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu

• arxiv url: http://arxiv.org/abs/2011.04144v2
• Date: Thu, 22 Jul 2021 06:37:12 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-28 02:40:10.144089
• Title: Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu
• Title（参考訳）: Chow-Liuによる木構造分布の準最適学習
• Authors: Arnab Bhattacharyya, Sutanu Gayen, Eric Price, N. V. Vinodchandran
• Abstract要約: 古典的ChowLiuアルゴリズム(IEEE Trans.Inform.Theory, 1968)に対する有限サンプル保証を提供する。 特定の木の$T$に対して、$widetildeO (|Sigma|2nvarepsilon-1)$の分布からのサンプルを$P$ over $Sigman$とすると、最も近いKL分岐を効率的に学習できる。
• 参考スコア（独自算出の注目度）: 14.298220510927695
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We provide finite sample guarantees for the classical Chow-Liu algorithm (IEEE Trans.~Inform.~Theory, 1968) to learn a tree-structured graphical model of a distribution. For a distribution $P$ on $\Sigma^n$ and a tree $T$ on $n$ nodes, we say $T$ is an $\varepsilon$-approximate tree for $P$ if there is a $T$-structured distribution $Q$ such that $D(P\;||\;Q)$ is at most $\varepsilon$ more than the best possible tree-structured distribution for $P$. We show that if $P$ itself is tree-structured, then the Chow-Liu algorithm with the plug-in estimator for mutual information with $\widetilde{O}(|\Sigma|^3 n\varepsilon^{-1})$ i.i.d.~samples outputs an $\varepsilon$-approximate tree for $P$ with constant probability. In contrast, for a general $P$ (which may not be tree-structured), $\Omega(n^2\varepsilon^{-2})$ samples are necessary to find an $\varepsilon$-approximate tree. Our upper bound is based on a new conditional independence tester that addresses an open problem posed by Canonne, Diakonikolas, Kane, and Stewart~(STOC, 2018): we prove that for three random variables $X,Y,Z$ each over $\Sigma$, testing if $I(X; Y \mid Z)$ is $0$ or $\geq \varepsilon$ is possible with $\widetilde{O}(|\Sigma|^3/\varepsilon)$ samples. Finally, we show that for a specific tree $T$, with $\widetilde{O} (|\Sigma|^2n\varepsilon^{-1})$ samples from a distribution $P$ over $\Sigma^n$, one can efficiently learn the closest $T$-structured distribution in KL divergence by applying the add-1 estimator at each node.
• Abstract（参考訳）: 古典的なchow-liuアルゴリズム(ieee trans.~inform.~theory, 1968)に対する有限なサンプル保証を提供し、分布のツリー構造を持つグラフィカルモデルを学ぶ。 for a distribution $P$ on $\Sigma^n$ and a tree $T$ on $n$ node, we say $T$ is a $\varepsilon$-approximate tree for $P$ if a $T$-structured distribution $Q$ such that $D(P\;||\;Q)$ is at most $\varepsilon$ than the best possible tree-structured distribution for $P$。 p$ 自体がツリー構造であるなら、chow-liu アルゴリズムは$\widetilde{o}(|\sigma|^3 n\varepsilon^{-1})$ i.i.d.~samples で相互情報のためのプラグイン推定子を持ち、一定の確率で $p$ で $\varepsilon$-approximate tree を出力する。 対照的に、一般的な$P$(木構造ではないかもしれない)の場合、$\Omega(n^2\varepsilon^{-2})$サンプルは$\varepsilon$-approximate treeを見つけるために必要である。 我々の上限は、Canonne, Diakonikolas, Kane, and Stewart~(STOC, 2018): 3つの確率変数に対して、$X,Y,Z$ each over $\Sigma$, testing if $I(X; Y \mid Z)$ is $0$ or $\geq \varepsilon$ is possible with $\widetilde{O}(|\Sigma|^3/\varepsilon)$サンプルを証明している。 最後に、特定のツリー$T$に対して、分布$P$ over $\Sigma^n$のサンプルを$\widetilde{O} (|\Sigma|^2n\varepsilon^{-1}) とすると、各ノードに add-1 推定器を適用することで、KL の分岐において最も近い$T$-構造分布を効率的に学習できることを示す。

関連論文リスト

• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。 PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
  論文  参考訳（メタデータ） (2024-10-10T06:15:42Z)
• A spectral least-squares-type method for heavy-tailed corrupted regression with unknown covariance \& heterogeneous noise [2.019622939313173]
  重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。 本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
  論文  参考訳（メタデータ） (2022-09-06T23:37:31Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Tree density estimation [12.831051269764115]
  確率密度 $f(boldsymbol x)$ を持つランダムベクトル $boldsymbol X$ in $mathbb Rd$ の密度推定。 有界なサポートを持つリプシッツ連続 $f$ に対して、$mathbb E int |f_n(boldsymbol x)-fT*(boldsymbol x)|dboldsymbol x=0$ a.s である。 有界なサポートを持つリプシッツ連続$f$に対して、$mathbb E int |f_n(boldsymbol x)-f
  論文  参考訳（メタデータ） (2021-11-23T16:05:59Z)
• Coresets for Decision Trees of Signals [19.537354146654845]
  仮にそのような行列に対して$(k,varepsilon)$-coresetを出力する最初のアルゴリズムを提供する。 これは、決定木と -- 機械学習から -- 計算幾何学における分割木の間のリンクをフォージすることで実現している。
  論文  参考訳（メタデータ） (2021-10-07T05:49:55Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• Self-training Converts Weak Learners to Strong Learners in Mixture Models [86.7137362125503]
  擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。 さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:59:16Z)
• Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
  ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。 我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
  論文  参考訳（メタデータ） (2020-06-23T20:21:27Z)
• Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
  i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。 疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
  論文  参考訳（メタデータ） (2020-06-17T09:21:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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