×

zbMATH — the first resource for mathematics

Exploiting tensor rank-one decomposition in probabilistic inference. (English) Zbl 1148.68539
Summary: We propose a new additive decomposition of probability tables tensor rank-one decomposition. The basic idea is to decompose a probability table into a series of tables, such that the table that is the sum of the series is equal to the original table. Each table in the series has the same domain as the original table but can be expressed as a product of one-dimensional tables. Entries in tables are allowed to be any real number, i. e. they can be also negative numbers. The possibility of having negative numbers, in contrast to a multiplicative decomposition, opens new possibilities for a compact representation of probability tables. We show that tensor rank-one decomposition can be used to reduce the space and time requirements in probabilistic inference. We provide a closed form solution for minimal tensor rank-one decomposition for some special tables and propose a numerical algorithm that can be used in cases when the closed form solution is not known.

MSC:
68T37 Reasoning under uncertainty in the context of artificial intelligence
62E15 Exact distribution theory in statistics
15A69 Multilinear algebra, tensor calculus
PDF BibTeX XML Cite
Full Text: Link EuDML
References:
[1] Chavira M., Darwiche A.: Compiling Bayesian networks with local structure. Proc. 19th Internat. Joint Conference on Artificial Intelligence (IJCAI), Edinburgh 2005, pp. 1306-1312
[2] Darwiche A.: A differential approach to inference in Bayesian networks. J. Assoc. Comput. Mach. 50 (2003), 3, 280-305 · Zbl 1325.68226 · doi:10.1145/765568.765570
[3] Lathauwer L. De, Moor B. De: From matrix to tensor: multilinear algebra and signal processing. 4th Internat. Conference on Mathematics in Signal Processing, Part I, IMA Conference Series, Warwick 1996, pp. 1-11
[4] Lathauwer L. De, Moor, B. De, Vandewalle J.: On the best Rank-1 and Rank-\((R_1,R_2,\ldots ,R_N)\) approximation of higher-order tensors. SIAM J. Matrix Anal. Appl. 21 (2000), 4, 1324-1342 · Zbl 0958.15026 · doi:10.1137/S0895479898346995
[5] Díez F. J., Galán S. F.: An efficient factorization for the noisy MAX. Internat. J. Intell. Systems 18 (2003), 2, 165-177 · Zbl 1028.68164
[6] Golub G. H., Loan C. F. Van: Matrix Computations. Third edition. Johns Hopkins University Press, Baltimore 1996 · Zbl 0865.65009
[7] Heckerman D.: A tractable inference algorithm for diagnosing multiple diseases. Proc. Fifth Annual Conference on Uncertainty in AI (M. Henrion, R. D. Shachter, L. N. Kanal, and J. F. Lemmer, August 18-21, 1989, Windsor, ON, pp. 163-171
[8] Heckerman D.: Causal independence for knowledge acquisition and inference. Proc. Ninth Conference on Uncertainty in AI (D. Heckerman and A. Mamdani, July 9-11, 1993, Washington, D.C., pp. 122-127
[9] Heckerman D., Breese J. S.: A new look at causal independence. Proc. Tenth Conference on Uncertainty in AI (R. Lopez de Mantaras and D. Poole, July 29-31, 1994, Seattle, WA, pp. 286-292
[10] Håstad J.: Tensor Rank is NP-complete. J. Algorithms 11 (1990), 644-654 · Zbl 0716.65043 · doi:10.1016/0196-6774(90)90014-6
[11] Jensen F. V.: Bayesian Networks and Decision Graphs. (Statistics for Engineering and Information Science.) Springer-Verlag, New York - Berlin - Heidelberg 2001 · Zbl 0973.62005
[12] Jensen F. V., Lauritzen S. L., Olesen K. G.: Bayesian updating in recursive graphical models by local computation. Computat. Statist. Quart. 4 (1990), 269-282 · Zbl 0715.68076
[13] Lauritzen S. L.: Graphical Models. Clarendon Press, Oxford 1996 · Zbl 1055.62126 · doi:10.1214/ss/1081443232
[14] Olesen K. G., Kjærulff U., Jensen F., Jensen F. V., Falck B., Andreassen S., Andersen S. K.: A MUNIN network for the median nerve - a case study on loops. Appl. Artif. Intell., Special issue: Towards Causal AI Models in Practice 3 (1989), 384-403
[15] Polak E.: Computational Methods in Optimization: A Unified Approach. Academic Press, New York 1971 · Zbl 0301.90040
[16] Takikawa M., D’Ambrosio B.: Multiplicative factorization of noisy-max. Proc. Fifteenth Conference on Uncertainty in AI (K. B. Laskey and H. Prade, July 30 - August 1, 1999, Stockholm, pp. 622-630
[17] Vomlel J.: Exploiting functional dependence in Bayesian network inference. Proc. Eighteenth Conference on Uncertainty in AI (UAI) - Edmonton (Canada), Morgan Kaufmann, San Francisco 2002, pp. 528-535
[18] Zhang N. L., Poole D.: Exploiting causal independence in Bayesian network inference. J. Artif. Intell. Res. 5 (1996), 301-328 · Zbl 0900.68384 · www.jair.org
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.