論文の概要: Robustifying Algorithms of Learning Latent Trees with Vector Variables
- arxiv url: http://arxiv.org/abs/2106.00885v1
- Date: Wed, 2 Jun 2021 01:37:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-03 14:40:17.637778
- Title: Robustifying Algorithms of Learning Latent Trees with Vector Variables
- Title(参考訳): ベクトル変数を用いた潜在木学習のロバスト化アルゴリズム
- Authors: Fengzhuo Zhang, Vincent Y. F. Tan
- Abstract要約: Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。
RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。
我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
- 参考スコア(独自算出の注目度): 92.18777020401484
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider learning the structures of Gaussian latent tree models with
vector observations when a subset of them are arbitrarily corrupted. First, we
present the sample complexities of Recursive Grouping (RG) and Chow-Liu
Recursive Grouping (CLRG) without the assumption that the effective depth is
bounded in the number of observed nodes, significantly generalizing the results
in Choi et al. (2011). We show that Chow-Liu initialization in CLRG greatly
reduces the sample complexity of RG from being exponential in the diameter of
the tree to only logarithmic in the diameter for the hidden Markov model (HMM).
Second, we robustify RG, CLRG, Neighbor Joining (NJ) and Spectral NJ (SNJ) by
using the truncated inner product. These robustified algorithms can tolerate a
number of corruptions up to the square root of the number of clean samples.
Finally, we derive the first known instance-dependent impossibility result for
structure learning of latent trees. The optimalities of the robust version of
CLRG and NJ are verified by comparing their sample complexities and the
impossibility result.
- Abstract(参考訳): 我々は,その部分集合が任意に破損した場合に,ベクトル観測によりガウスの潜在木モデルの構造を学習することを検討する。
まず、実効深度が観測ノード数で有界であるという仮定なしに、再帰的グループ (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑度を示し、Choi et al において結果を著しく一般化する。
(2011).
CLRGにおけるChow-Liu初期化は,木径の指数関数化から隠れマルコフモデル(HMM)の対数化まで,RGのサンプル複雑性を大幅に減少させることを示す。
次に,RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。
これらの堅牢化アルゴリズムは、クリーンサンプル数の平方根まで多くの汚職を許容することができる。
最後に、潜在木の構造学習において、最初の既知のインスタンス依存不合理性を導出する。
CLRG と NJ のロバストバージョンの最適性は、それらのサンプルの複雑さと不合理性の結果を比較して検証する。
関連論文リスト
- Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。
クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。
このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
論文 参考訳(メタデータ) (2023-05-24T11:05:12Z) - DynGFN: Towards Bayesian Inference of Gene Regulatory Networks with
GFlowNets [81.75973217676986]
遺伝子調節ネットワーク(GRN)は、遺伝子発現と細胞機能を制御する遺伝子とその産物間の相互作用を記述する。
既存の方法は、チャレンジ(1)、ダイナミックスから循環構造を識別すること、あるいはチャレンジ(2)、DAGよりも複雑なベイズ後部を学習することに焦点を当てるが、両方ではない。
本稿では、RNAベロシティ技術を用いて遺伝子発現の「速度」を推定できるという事実を活用し、両方の課題に対処するアプローチを開発する。
論文 参考訳(メタデータ) (2023-02-08T16:36:40Z) - Entailment Tree Explanations via Iterative Retrieval-Generation Reasoner [56.08919422452905]
我々はIRGR(Iterative Retrieval-Generation Reasoner)と呼ばれるアーキテクチャを提案する。
本モデルでは,テキストの前提からステップバイステップの説明を体系的に生成することにより,与えられた仮説を説明することができる。
前提条件の検索と細分化木の生成に関する既存のベンチマークを上回り、全体の正しさはおよそ300%向上した。
論文 参考訳(メタデータ) (2022-05-18T21:52:11Z) - 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) - Decentralized Learning of Tree-Structured Gaussian Graphical Models from
Noisy Data [1.52292571922932]
本稿では,木構造ガウス図形モデル(GGM)の雑音データからの分散学習について検討する。
GGMは遺伝子制御ネットワークやソーシャルネットワークのような複雑なネットワークをモデル化するために広く利用されている。
提案した分散学習では,木構造GGMの推定にChow-Liuアルゴリズムを用いる。
論文 参考訳(メタデータ) (2021-09-22T10:41:18Z) - Spectral Top-Down Recovery of Latent Tree Models [13.681975313065477]
スペクトルトップダウン・リカバリ (STDR) は、大きな潜在木モデルを推定するための分割・コンカレントアプローチである。
STDRの分割ステップは非ランダムです。
代わりに、観測されたノードに関連する適切なラプラシア行列のFiedlerベクトルに基づいている。
私達はSTDRが統計的に一貫性があることを証明し、高い確率で木を正確に回復するために必要なサンプルの数を縛ります。
論文 参考訳(メタデータ) (2021-02-26T02:47:42Z) - 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) - From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical
Clustering [33.000371053304676]
本稿では,Dasguptaの離散最適化問題に対して,証明可能な品質保証を用いた最初の連続緩和を提案する。
勾配勾配勾配の近似解でさえ、凝集性クラスタリングよりも優れた品質を有することを示す。
また、下流分類タスクにおけるエンドツーエンドトレーニングによるHypHCの柔軟性についても強調する。
論文 参考訳(メタデータ) (2020-10-01T13:43:19Z) - Spectral neighbor joining for reconstruction of latent tree models [5.229354894035374]
我々は,潜在木図形モデルの構造を復元する新しい手法であるSpectral Neighbor Joiningを開発した。
我々はSNJが一貫したものであることを証明し、推定された類似性行列から木回復を正すのに十分な条件を導出する。
SNJは,他の再建法と比較して,多数の葉や長い縁を持つ樹木を正確に復元するために,サンプルを少なくする。
論文 参考訳(メタデータ) (2020-02-28T05:13:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。