Distribution Learning Meets Graph Structure Sampling
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909899891408896 |
|---|---|
| author | Bhattacharyya, Arnab Gayen, Sutanu John, Philips George Sen, Sayantan Vinodchandran, N. V. |
| author_facet | Bhattacharyya, Arnab Gayen, Sutanu John, Philips George Sen, Sayantan Vinodchandran, N. V. |
| contents | This work establishes a novel link between the problem of PAC-learning high-dimensional graphical models and the task of (efficient) counting and sampling of graph structures, using an online learning framework.
We observe that if we apply the exponentially weighted average (EWA) or randomized weighted majority (RWM) forecasters on a sequence of samples from a distribution P using the log loss function, the average regret incurred by the forecaster's predictions can be used to bound the expected KL divergence between P and the predictions. Known regret bounds for EWA and RWM then yield new sample complexity bounds for learning Bayes nets. Moreover, these algorithms can be made computationally efficient for several interesting classes of Bayes nets. Specifically, we give a new sample-optimal and polynomial time learning algorithm with respect to trees of unknown structure and the first polynomial sample and time algorithm for learning with respect to Bayes nets over a given chordal skeleton. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_07914 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distribution Learning Meets Graph Structure Sampling Bhattacharyya, Arnab Gayen, Sutanu John, Philips George Sen, Sayantan Vinodchandran, N. V. Machine Learning Data Structures and Algorithms This work establishes a novel link between the problem of PAC-learning high-dimensional graphical models and the task of (efficient) counting and sampling of graph structures, using an online learning framework. We observe that if we apply the exponentially weighted average (EWA) or randomized weighted majority (RWM) forecasters on a sequence of samples from a distribution P using the log loss function, the average regret incurred by the forecaster's predictions can be used to bound the expected KL divergence between P and the predictions. Known regret bounds for EWA and RWM then yield new sample complexity bounds for learning Bayes nets. Moreover, these algorithms can be made computationally efficient for several interesting classes of Bayes nets. Specifically, we give a new sample-optimal and polynomial time learning algorithm with respect to trees of unknown structure and the first polynomial sample and time algorithm for learning with respect to Bayes nets over a given chordal skeleton. |
| title | Distribution Learning Meets Graph Structure Sampling |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.07914 |