論文の概要: Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models

• arxiv url: http://arxiv.org/abs/2106.03969v1
• Date: Mon, 7 Jun 2021 21:09:29 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-09 15:32:25.661328
• Title: Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models
• Title（参考訳）: Chow-Liu++: ツリーイジングモデルの最適予測中心学習
• Authors: Enric Boix-Adsera, Guy Bresler, Frederic Koehler
• Abstract要約: 我々は、Chow-Liuアルゴリズムの要素とツリーメートル法を組み合わせた新しいアルゴリズムを提案する。 我々のアルゴリズムは不特定性や敵の腐敗をモデル化するのに堅牢である。
• 参考スコア（独自算出の注目度）: 30.62276301751904
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of learning a tree-structured Ising model from data, such that subsequent predictions computed using the model are accurate. Concretely, we aim to learn a model such that posteriors $P(X_i|X_S)$ for small sets of variables $S$ are accurate. Since its introduction more than 50 years ago, the Chow-Liu algorithm, which efficiently computes the maximum likelihood tree, has been the benchmark algorithm for learning tree-structured graphical models. A bound on the sample complexity of the Chow-Liu algorithm with respect to the prediction-centric local total variation loss was shown in [BK19]. While those results demonstrated that it is possible to learn a useful model even when recovering the true underlying graph is impossible, their bound depends on the maximum strength of interactions and thus does not achieve the information-theoretic optimum. In this paper, we introduce a new algorithm that carefully combines elements of the Chow-Liu algorithm with tree metric reconstruction methods to efficiently and optimally learn tree Ising models under a prediction-centric loss. Our algorithm is robust to model misspecification and adversarial corruptions. In contrast, we show that the celebrated Chow-Liu algorithm can be arbitrarily suboptimal.
• Abstract（参考訳）: 木構造イジングモデルをデータから学習する際の問題点を考察し,そのモデルを用いて計算した後の予測が正確であることを示す。 具体的には、小変数集合に対して$P(X_i|X_S)$が正確であるようなモデルを学ぶことを目指している。 50年以上前に導入されたchow-liuアルゴリズムは、木構造のグラフィカルモデルを学ぶためのベンチマークアルゴリズムである。 予測中心の局所的全変量損失に関するChow-Liuアルゴリズムのサンプル複雑性を[BK19]に表した。 これらの結果は、真の基礎となるグラフの復元が不可能な場合でも有用なモデルを学ぶことができることを示したが、それらの境界は相互作用の最大強度に依存するため、情報理論の最適性は得られない。 本稿では,chow-liuアルゴリズムの要素とツリーメトリック再構成法を慎重に組み合わせ,予測中心損失下でのツリーイジングモデルを効率的かつ最適に学習するアルゴリズムを提案する。 我々のアルゴリズムは不特定性や敵の腐敗をモデル化するのに堅牢である。 対照的に、有名なChow-Liuアルゴリズムは任意に最適であることを示す。

関連論文リスト

• Optimal estimation of Gaussian (poly)trees [25.02920605955238]
  分布学習(KL距離)と構造学習(正確な回復)の両問題を考察する。 最初のアプローチはChow-Liuアルゴリズムに基づいており、最適な木構造分布を効率的に学習する。 第2のアプローチは、制約に基づく構造学習のための条件付き独立試験器として部分相関を用いたポリツリーに対するPCアルゴリズムの修正である。
  論文  参考訳（メタデータ） (2024-02-09T12:58:36Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。 我々の手法は古典的DPベースの推論に広く適用できる。 また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
  論文  参考訳（メタデータ） (2021-12-07T11:26:41Z)
• 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)
• A cautionary tale on fitting decision trees to data from additive models: generalization lower bounds [9.546094657606178]
  本研究では,異なる回帰モデルに対する決定木の一般化性能について検討する。 これにより、アルゴリズムが新しいデータに一般化するために(あるいは作らない)仮定する帰納的バイアスが引き起こされる。 スパース加法モデルに適合する大規模な決定木アルゴリズムに対して、シャープな2乗誤差一般化を低い境界で証明する。
  論文  参考訳（メタデータ） (2021-10-18T21:22:40Z)
• 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)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• 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)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)

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

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