論文の概要: Spectral Top-Down Recovery of Latent Tree Models
- arxiv url: http://arxiv.org/abs/2102.13276v1
- Date: Fri, 26 Feb 2021 02:47:42 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-01 13:58:38.294378
- Title: Spectral Top-Down Recovery of Latent Tree Models
- Title(参考訳): 潜在木モデルのスペクトルトップダウン復元
- Authors: Yariv Aizenbud, Ariel Jaffe, Meng Wang, Amber Hu, Noah Amsel, Boaz
Nadler, Joseph T. Chang, Yuval Kluger
- Abstract要約: スペクトルトップダウン・リカバリ (STDR) は、大きな潜在木モデルを推定するための分割・コンカレントアプローチである。
STDRの分割ステップは非ランダムです。
代わりに、観測されたノードに関連する適切なラプラシア行列のFiedlerベクトルに基づいている。
私達はSTDRが統計的に一貫性があることを証明し、高い確率で木を正確に回復するために必要なサンプルの数を縛ります。
- 参考スコア(独自算出の注目度): 13.681975313065477
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Modeling the distribution of high dimensional data by a latent tree graphical
model is a common approach in multiple scientific domains. A common task is to
infer the underlying tree structure given only observations of the terminal
nodes. Many algorithms for tree recovery are computationally intensive, which
limits their applicability to trees of moderate size. For large trees, a common
approach, termed divide-and-conquer, is to recover the tree structure in two
steps. First, recover the structure separately for multiple randomly selected
subsets of the terminal nodes. Second, merge the resulting subtrees to form a
full tree. Here, we develop Spectral Top-Down Recovery (STDR), a
divide-and-conquer approach for inference of large latent tree models. Unlike
previous methods, STDR's partitioning step is non-random. Instead, it is based
on the Fiedler vector of a suitable Laplacian matrix related to the observed
nodes. We prove that under certain conditions this partitioning is consistent
with the tree structure. This, in turn leads to a significantly simpler merging
procedure of the small subtrees. We prove that STDR is statistically
consistent, and bound the number of samples required to accurately recover the
tree with high probability. Using simulated data from several common tree
models in phylogenetics, we demonstrate that STDR has a significant advantage
in terms of runtime, with improved or similar accuracy.
- Abstract(参考訳): 潜伏木グラフモデルによる高次元データの分布のモデル化は、複数の科学的領域において共通のアプローチである。
共通するタスクは、端末ノードの観測のみを前提としたツリー構造を推測することである。
多くの木回復アルゴリズムは計算量が多いため、適度な大きさの木への適用性が制限されている。
大きな木の場合、分割と分割と呼ばれる一般的なアプローチは、2つのステップで木構造を回復することである。
まず、複数の端末ノードのランダムに選択されたサブセットに対して別々に構造を復元する。
次に、結果のサブツリーをマージして、フルツリーを形成する。
本研究では,大規模潜在木モデルの推定のための分割・解法であるスペクトルトップダウンリカバリ(stdr)を開発した。
従来の方法とは異なり、STDRの分割ステップは非ランダムである。
代わりに、観測されたノードに関連する適切なラプラシア行列のFiedlerベクトルに基づいている。
特定の条件下では、この分割はツリー構造と一致していることを示す。
これにより、小さな部分木のマージ手順が大幅に単純化される。
私達はSTDRが統計的に一貫性があることを証明し、高い確率で木を正確に回復するために必要なサンプルの数を縛ります。
系統学におけるいくつかの共通木モデルのシミュレーションデータを用いて,STDRは実行時において,改良あるいは類似した精度で大きな優位性を有することを示した。
関連論文リスト
- Sharded Bayesian Additive Regression Trees [1.4213973379473654]
データの分割を決定するためにランダム化補助変数とシャーディングツリーを導入する。
積空間上の部分モデルに対する最適シャーディングを最適に設計できることを観察することにより、交差木構造を導入し、木構造のみを用いてシャーディングとモデリングの両方を完全に指定する。
論文 参考訳(メタデータ) (2023-06-01T05:41:31Z) - Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。
クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。
このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
論文 参考訳(メタデータ) (2023-05-24T11:05:12Z) - SETAR-Tree: A Novel and Accurate Tree Algorithm for Global Time Series
Forecasting [7.206754802573034]
本稿では,TARモデルと回帰木との密接な関係について検討する。
本研究では,葉のグローバルプール回帰(PR)モデルをトレーニングする,予測固有木アルゴリズムを提案する。
本評価では, 提案した樹木モデルと森林モデルを用いて, 最先端の樹木モデルよりも精度の高い木モデルを提案する。
論文 参考訳(メタデータ) (2022-11-16T04:30:42Z) - Unbiased and Efficient Sampling of Dependency Trees [0.0]
ほとんどのツリーバンクは、すべての有効な依存ツリーがROOTノードから出てくる単一のエッジを持つ必要がある。
Zmigrodらは最近、単一ルート依存ツリーの分布から置き換えることなくサンプリングするアルゴリズムを提案している。
我々は、Wilson-RCを置換したサンプリングアルゴリズムが実際にバイアスを受けていることを示す。
論文 参考訳(メタデータ) (2022-05-25T09:57:28Z) - Hierarchical Shrinkage: improving the accuracy and interpretability of
tree-based methods [10.289846887751079]
木構造を改変しないポストホックアルゴリズムである階層収縮(Hierarchical Shrinkage, HS)を導入する。
HSは、他の正規化技術と併用しても、決定木の予測性能を大幅に向上させる。
すべてのコードとモデルはGithubにある本格的なパッケージでリリースされている。
論文 参考訳(メタデータ) (2022-02-02T02:43:23Z) - 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) - Visualizing hierarchies in scRNA-seq data using a density tree-biased
autoencoder [50.591267188664666]
本研究では,高次元scRNA-seqデータから意味のある木構造を同定する手法を提案する。
次に、低次元空間におけるデータのツリー構造を強調する木バイアスオートエンコーダDTAEを紹介する。
論文 参考訳(メタデータ) (2021-02-11T08:48:48Z) - 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) - Growing Deep Forests Efficiently with Soft Routing and Learned
Connectivity [79.83903179393164]
この論文は、いくつかの重要な側面で深い森林のアイデアをさらに拡張します。
我々は、ノードがハードバイナリ決定ではなく、確率的ルーティング決定、すなわちソフトルーティングを行う確率的ツリーを採用する。
MNISTデータセットの実験は、私たちの力のある深部森林が[1]、[3]よりも優れたまたは匹敵するパフォーマンスを達成できることを示しています。
論文 参考訳(メタデータ) (2020-12-29T18:05:05Z) - Convex Polytope Trees [57.56078843831244]
コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。
木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
論文 参考訳(メタデータ) (2020-10-21T19:38:57Z) - Spectral neighbor joining for reconstruction of latent tree models [5.229354894035374]
我々は,潜在木図形モデルの構造を復元する新しい手法であるSpectral Neighbor Joiningを開発した。
我々はSNJが一貫したものであることを証明し、推定された類似性行列から木回復を正すのに十分な条件を導出する。
SNJは,他の再建法と比較して,多数の葉や長い縁を持つ樹木を正確に復元するために,サンプルを少なくする。
論文 参考訳(メタデータ) (2020-02-28T05:13:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。