Learning bounded-degree polytrees with known skeleton
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911761540579328 |
|---|---|
| author | Choo, Davin Yang, Joy Qiping Bhattacharyya, Arnab Canonne, Clément L. |
| author_facet | Choo, Davin Yang, Joy Qiping Bhattacharyya, Arnab Canonne, Clément L. |
| contents | We establish finite-sample guarantees for efficient proper learning of bounded-degree polytrees, a rich class of high-dimensional probability distributions and a subclass of Bayesian networks, a widely-studied type of graphical model. Recently, Bhattacharyya et al. (2021) obtained finite-sample guarantees for recovering tree-structured Bayesian networks, i.e., 1-polytrees. We extend their results by providing an efficient algorithm which learns $d$-polytrees in polynomial time and sample complexity for any bounded $d$ when the underlying undirected graph (skeleton) is known. We complement our algorithm with an information-theoretic sample complexity lower bound, showing that the dependence on the dimension and target accuracy parameters are nearly tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_06333 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Learning bounded-degree polytrees with known skeleton Choo, Davin Yang, Joy Qiping Bhattacharyya, Arnab Canonne, Clément L. Machine Learning Data Structures and Algorithms Probability Statistics Theory We establish finite-sample guarantees for efficient proper learning of bounded-degree polytrees, a rich class of high-dimensional probability distributions and a subclass of Bayesian networks, a widely-studied type of graphical model. Recently, Bhattacharyya et al. (2021) obtained finite-sample guarantees for recovering tree-structured Bayesian networks, i.e., 1-polytrees. We extend their results by providing an efficient algorithm which learns $d$-polytrees in polynomial time and sample complexity for any bounded $d$ when the underlying undirected graph (skeleton) is known. We complement our algorithm with an information-theoretic sample complexity lower bound, showing that the dependence on the dimension and target accuracy parameters are nearly tight. |
| title | Learning bounded-degree polytrees with known skeleton |
| topic | Machine Learning Data Structures and Algorithms Probability Statistics Theory |
| url | https://arxiv.org/abs/2310.06333 |