Optimal estimation of Gaussian (poly)trees
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911774147608576 |
|---|---|
| author | Wang, Yuhao Gao, Ming Tai, Wai Ming Aragam, Bryon Bhattacharyya, Arnab |
| author_facet | Wang, Yuhao Gao, Ming Tai, Wai Ming Aragam, Bryon Bhattacharyya, Arnab |
| contents | We develop optimal algorithms for learning undirected Gaussian trees and directed Gaussian polytrees from data. We consider both problems of distribution learning (i.e. in KL distance) and structure learning (i.e. exact recovery). The first approach is based on the Chow-Liu algorithm, and learns an optimal tree-structured distribution efficiently. The second approach is a modification of the PC algorithm for polytrees that uses partial correlation as a conditional independence tester for constraint-based structure learning. We derive explicit finite-sample guarantees for both approaches, and show that both approaches are optimal by deriving matching lower bounds. Additionally, we conduct numerical experiments to compare the performance of various algorithms, providing further insights and empirical evidence. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_06380 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal estimation of Gaussian (poly)trees Wang, Yuhao Gao, Ming Tai, Wai Ming Aragam, Bryon Bhattacharyya, Arnab Machine Learning We develop optimal algorithms for learning undirected Gaussian trees and directed Gaussian polytrees from data. We consider both problems of distribution learning (i.e. in KL distance) and structure learning (i.e. exact recovery). The first approach is based on the Chow-Liu algorithm, and learns an optimal tree-structured distribution efficiently. The second approach is a modification of the PC algorithm for polytrees that uses partial correlation as a conditional independence tester for constraint-based structure learning. We derive explicit finite-sample guarantees for both approaches, and show that both approaches are optimal by deriving matching lower bounds. Additionally, we conduct numerical experiments to compare the performance of various algorithms, providing further insights and empirical evidence. |
| title | Optimal estimation of Gaussian (poly)trees |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2402.06380 |