Learning Acyclic Probabilistic Circuits Using Test Paths
Abstract
We define a model of learning probabilistic acyclic circuits using value injection queries, in which an arbitrary subset of wires is set to fixed values, and the value on the single output wire is observed. We adapt the approach of using test paths from the Circuit Builder algorithm [AACW06] to show that there is a polynomial time algorithm that uses value injection queries to learn Boolean probabilistic circuits of constant fan-in and log depth. In the process, we discover that test paths fail utterly for circuits over alphabets of size greater than two and establish upper and lower bounds on the attenuation factor for general and transitively reduced Boolean probabilistic circuits of test paths versus general experiments. To overcome the limitations of test paths for non-Boolean alphabets, we introduce function injection queries, which allow the symbols on a wire to be mapped to other symbols rather than just to themselves or constants.
Cite
Text
Angluin et al. "Learning Acyclic Probabilistic Circuits Using Test Paths." Annual Conference on Computational Learning Theory, 2008. doi:10.5555/1577069.1755848Markdown
[Angluin et al. "Learning Acyclic Probabilistic Circuits Using Test Paths." Annual Conference on Computational Learning Theory, 2008.](https://mlanthology.org/colt/2008/angluin2008colt-learning/) doi:10.5555/1577069.1755848BibTeX
@inproceedings{angluin2008colt-learning,
title = {{Learning Acyclic Probabilistic Circuits Using Test Paths}},
author = {Angluin, Dana and Aspnes, James and Chen, Jiang and Eisenstat, David and Reyzin, Lev},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2008},
pages = {169-180},
doi = {10.5555/1577069.1755848},
url = {https://mlanthology.org/colt/2008/angluin2008colt-learning/}
}