Modeling the distribution of high dimensional data by a latent tree graphical model is a prevalent approach in multiple scientific domains. A common task is to infer the underlying tree structure, given only observations of its 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 of multiple, possibly random subsets of the terminal nodes. Second, merge the resulting subtrees to form a full tree. Here, we develop Spectral Top-Down Recovery (STDR), a deterministic divide-and-conquer approach to infer large latent tree models. Unlike previous methods, STDR partitions the terminal nodes in a non random way, 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.


翻译:以隐形树图形模型模拟高维数据分布是多个科学领域的普遍做法。 一项共同任务是推断树底结构, 仅对其终端节点进行观察。 许多树的恢复算法是计算密集的, 限制了其对中小树的可适用性。 对于大树, 一种共同的方法, 称为分裂和征服, 是将树结构分成两步。 首先, 将终端节点的多个、 可能是随机的子集分开, 其次, 其次, 其次, 合并成一整棵树。 在这里, 我们开发了光谱顶层恢复( STDR), 这是一种决定性的分化分化法, 用以推断大树的树形模型。 与以前的方法不同, STDR 以非随机的方式将终端节点分割成非随机的。 我们证明, 在某些条件下, 此间隔断结构与树底结构结构结构相符合。 而这又导致小子树底树的合并程序大大简化。 我们证明, STDR 与许多相似的模型具有统计性、 和固定的精确性, 在树底模型中, 的模型中, 我们用大量的模型显示。

0
下载
关闭预览

相关内容

专知会员服务
42+阅读 · 2020年12月18日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
最新【深度生成模型】Deep Generative Models,104页ppt
专知会员服务
68+阅读 · 2020年10月24日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2022年2月8日
Arxiv
0+阅读 · 2022年2月8日
Arxiv
5+阅读 · 2018年2月26日
VIP会员
相关资讯
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员