nips nips2002 nips2002-4 nips2002-4-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: James D. Park, Adnan Darwiche
Abstract: A new approach to inference in belief networks has been recently proposed, which is based on an algebraic representation of belief networks using multi–linear functions. According to this approach, the key computational question is that of representing multi–linear functions compactly, since inference reduces to a simple process of ev aluating and differentiating such functions. W e show here that mainstream inference algorithms based on jointrees are a special case of this approach in a v ery precise sense. W e use this result to prov e new properties of jointree algorithms, and then discuss some of its practical and theoretical implications. 1
[1] H. Chan and A. Darwiche. When do numbers really matter? JAIR, 17: 265–287, 2002.
[2] A. Darwiche. A differential approach to inference in Bay esian networks. In UAI’00, pages 123–132, 2000. T o appear in JACM.
[3] A. Darwiche. A logical approach to factoring belief networks. In KR’02, pages 409– 420, 2002.
[4] A. Darwiche. On the factorization of multi–linear functions. T echnical Report D–128, UCLA, Los Angeles, Ca 90095, 2002.
[5] J. Hoey , R. St-Aubin, A. Hu, and G. Boutilier. SPUDD: Stochastic planning using decision diagrams. In UAI’99, pages 279–288, 1999.
[6] C. Huang and A. Darwiche. Inference in belief networks: A procedural guide. IJAR, 15(3): 225–263, 1996.
[7] M. Iri. Simultaneous computation of functions, partial deriv ativ es and estimates of rounding error. Japan J. Appl. Math., 1:223–252, 1984.
[8] F. V. Jensen, S.L. Lauritzen, and K.G. Olesen. Bay esian updating in recursiv e graphical models by local computation. Comp. Stat. Quart., 4:269–282, 1990.
[9] J. Park. MAP complexity results and approximation methods. In UAI’02, pages 388–396, 2002.
[10] J. Park and A. Darwiche. Approximating MAP using stochastic local search. In UAI’01, pages 403–410, 2001.
[11] J. Park and A. Darwiche. A differential semantics for jointree algorithms. T echnical Report D–118, UCLA, Los Angeles, Ca 90095, 2001.
[12] G. Rote. Path problems in graphs. Computing Suppl., 7:155–189, 1990.
[13] S. Russell, J. Binder, D. Koller, and K. Kanazawa. Local learning in probabilistic networks with hidden v ariables. In UAI’95, pages 1146–1152, 1995.
[14] P. P. Shenoy and G. Shafer. Propagating belief functions with local computations. IEEE Expert, 1(3):43–52, 1986.
[15] J. v on zur Gathen. Algebraic complexity theory . Ann. Rev. Comp. Sci., 3:317–347, 1988.