jmlr jmlr2009 jmlr2009-44 jmlr2009-44-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Dana Angluin, James Aspnes, Jiang Chen, David Eisenstat, Lev Reyzin
Abstract: We define a model of learning probabilistic acyclic circuits using value injection queries, in which fixed values are assigned to an arbitrary subset of the wires and the value on the single output wire is observed. We adapt the approach of using test paths from the Circuit Builder algorithm (Angluin et al., 2009) to show that there is a polynomial time algorithm that uses value injection queries to learn acyclic Boolean probabilistic circuits of constant fan-in and log depth. We establish upper and lower bounds on the attenuation factor for general and transitively reduced Boolean probabilistic circuits of test paths versus general experiments. We give computational evidence that a polynomial time learning algorithm using general value injection experiments may not do much better than one using test paths. For probabilistic circuits with alphabets of size three or greater, we show that the test path lemmas (Angluin et al., 2009, 2008b) fail utterly. To overcome this obstacle, we introduce function injection queries, in which the values on a wire may be mapped to other values rather than just to themselves or constants, and prove a generalized test path lemma for this case. Keywords: nonadaptive learning algorithms, probabilistic circuits, causal Bayesian networks, value injection queries, test paths
Tatsuya Akutsu, Satoru Kuhara, Osamu Maruyama, and Satoru Miyano. Identification of genetic networks by strategic gene disruptions and gene overexpressions under a boolean model. Theor. Comput. Sci., 298(1):235–251, 2003. Dana Angluin and Michael Kharitonov. When won’t membership queries help? J. Comput. Syst. Sci., 50(2):336–355, 1995. Dana Angluin, James Aspnes, Jiang Chen, David Eisenstat, and Lev Reyzin. Learning acyclic probabilistic circuits using test paths. In Twenty-First Annual Conference on Learning Theory, pages 169–179. Omicron, July 2008a. Dana Angluin, James Aspnes, Jiang Chen, and Lev Reyzin. Learning large-alphabet and analog circuits with value injection queries. Machine Learning, 72(1-2):113–138, 2008b. Dana Angluin, James Aspnes, and Lev Reyzin. Optimally learning social networks with activations and suppressions. In Nineteenth International Conference on Algorithmic Learning Theory, volume 5254 of Lecture Notes in Computer Science, pages 272–286, October 2008c. 1910 L EARNING ACYCLIC P ROBABILISTIC C IRCUITS U SING T EST PATHS Dana Angluin, James Aspnes, Jiang Chen, and Yinghua Wu. Learning a circuit by injecting values. J. Comput. Syst. Sci., 75(1):60–77, 2009. Nir Friedman, Michal Linial, Iftach Nachman, and Dana Pe´er. Using Bayesian networks to analyze expression data. J. Comput. Biol., 7(3–4):601–620, 2000. Johan H˚ stad. Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001. a Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.), 43(4):439–561 (electronic), 2006. Trey E. Ideker, Vesteinn Thorsson, and Richard M. Karp. Discovery of regulatory interactions through perturbation: Inference and experimental design. In Pacific Symposium on Biocomputing 5, pages 302–313, 2000. ´ David Kempe, Jon M. Kleinberg, and Eva Tardos. Maximizing the spread of influence through a social network. In KDD ’03: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 137–146, New York, NY, USA, 2003. ACM. ´ David Kempe, Jon M. Kleinberg, and Eva Tardos. Influential nodes in a diffusion model for social networks. In ICALP, pages 1127–1138, 2005. Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2000. 1911