Equivalence of compositional expressions and independence relations in compositional models. (English) Zbl 1366.62103

Kybernetika 50, No. 3, 322-362 (2014); erratum ibid. 51, No. 2, 387-388 (2015).
Summary: We generalize Jiroušek’s (right) composition operator in such a way that it can be applied to distribution functions with values in a “semifield”, and introduce (parenthesized) compositional expressions, which in some sense generalize Jiroušek’s “generating sequences” of compositional models. We say that two compositional expressions are equivalent if their evaluations always produce the same results whenever they are defined. Our first result is that a set system \(\mathcal H\) is star-like with centre \(X\) if and only if every two compositional expressions with “base scheme” \(\mathcal H\) and “key” \(X\) are equivalent. This result is stronger than Jiroušek’s result which states that, if \(\mathcal H\) is star-like with centre \(X\), then every two generating sequences with base scheme \(\mathcal H\) and key \(X\) are equivalent. Then, we focus on canonical expressions, by which we mean compositional expressions \(\theta \) such that the sequence of the sets featured in \(\theta \) and arranged in order of appearance enjoys the “running intersection property”. Since every compositional expression, whose base scheme is a star-like set system with centre \(X\) and whose key is \(X\), is a canonical expression, we investigate the equivalence between two canonical expressions with the same base scheme and the same key. We state a graphical characterization of those set systems \(\mathcal H\) such that every two canonical expressions with base scheme \(\mathcal H\) and key \(X\) are equivalent, and also provide a graphical algorithm for their recognition. Finally, we discuss the problem of detecting conditional independences that hold in a compositional model.


62H05 Characterization and structure theory for multivariate probability distributions; copulas
60E99 Distribution theory
Full Text: Link


[1] Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. Assoc. Comput. Mach. 30 (1983), 479-513. · Zbl 0624.68087 · doi:10.1145/2402.322389
[2] Blair, J. R. S., Peyton, B.W.: An Introduction to Chordal Graphs and Clique Trees. Technical Report ORNL/TM-12203, 1992. · Zbl 0803.68081
[3] Csiszár, I.: \(I\)-divergence geometry of probability distributions and minimization problems. Ann. Probab. 3 (1975), 146-158. · Zbl 0318.60013 · doi:10.1214/aop/1176996454
[4] Dawid, A. P.: Applications of a general propagation algorithm for probabilistic expert systems. Statist. Comput. 2 (1992), 25-36. · doi:10.1007/BF01890546
[5] Deming, W. E., Stephan, F. F.: On least squares adjustment of a sampled frequency table when the expected marginal totals are known. Ann. Math. Stat. 11 (1940), 427-444. · Zbl 0024.05502 · doi:10.1214/aoms/1177731829
[6] Hara, H., Takemura, A.: Boundary cliques, clique trees and perfect sequences of maximaal cliques of a chordal graph. arXiv:cs/0607055v1 [cs.DM], 11 July 2006, pp. 1-24.
[7] Jiroušek, R.: Composition of probability measures on finite spaces. Proc. XIII International Conf. on Uncertainty in Artificial Intelligence (D. Geiger and P. P. Shenoy, Morgan Kaufmann, San Francisco 1997, pp. 274-281.
[8] Jiroušek, R.: Decomposition of multidimensional distributions represented by perfect sequences. Ann. Math. Artif. Intelligence 5 (2002), 215-226. · Zbl 1004.60010 · doi:10.1023/A:1014591402750
[9] Jiroušek, R.: Detection of independence relations from persegrams. Proc. VI International Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems, Annecy 2002, Vol. C, pp. 1261-1267.
[10] Jiroušek, R.: Persegrams of compositional models revisited: conditional independence. Proc. XII International Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems (L. Magdalena, M. Ojeda-Aciego and J. L. Verdegay, Malaga 2008, pp. 915-922.
[11] Jiroušek, R.: Foundations of compositional model theory. Internat. J. General Systems 40 (2011), 623-678. · Zbl 1252.68285 · doi:10.1080/03081079.2011.562627
[12] Jiroušek, R.: Local computations in Dempster-Shafer theory of evidence. Internat. J. Approx. Reason. 53 (2012), 1155-1167. · Zbl 1266.68177 · doi:10.1016/j.ijar.2012.06.012
[13] Jiroušek, R., Shenoy, P. P.: Compositional models in valuation-based systems. Internat. J. Approx. Reason. 55 (2014), 277-293. · Zbl 1252.68310 · doi:10.1007/978-3-642-31724-8_70
[14] Jiroušek, R., Vejnarová, J.: General framework for multidimensional models. Internat. J. Approx. Reas. 18 (2003), 107-127. · Zbl 1029.68131 · doi:10.1002/int.10077
[15] Jiroušek, R., Vejnarová., J., Daniels, M.: Composition models of belief functions. Proc. V Symp. on Imprecise Probabilities and Their Applications (G. De Cooman, J. Vejnarová, and M. Zaffalon, Action M Agency, Prague 2007, pp. 243-252.
[16] Kratochvíl, V.: Characteristic properties of equivalent structures in compositional models. Internat. J. Approx. Reason. 52 (2011), 599-612. · Zbl 1214.68400 · doi:10.1016/j.ijar.2010.12.005
[17] Kratochvíl, V.: Probabilistic compositional models: solution of an equivalence problem. Internat. J. Approx. Reason. 54 (2013), 590-601. · Zbl 1316.68181 · doi:10.1016/j.ijar.2013.01.002
[18] Lauritzen, S. L.: Graphical Models. Oxford University Press, Oxford 1996. · Zbl 0907.62001
[19] Lenz, H.-J., Talheim, B.: A formal framework of aggregation for the OLAP-OLTP model. J. of Universal Computer Science 15 (2009), 273-303. · Zbl 1216.68091
[20] Malvestuto, F. M.: Tree and local computations in a cross-entropy minimization problem with marginal constraints. Kybernetika 46 (2010), 621-654. · Zbl 1204.93113
[21] Malvestuto, F. M.: The sum-product algorithm: algebraic independence and computational aspects. Kybernetika 49 (2013), 4-22. · Zbl 1307.68092
[22] Malvestuto, F. M.: A join-like operator to combine data cubes, and answer queries from multiple data cubes. Unpublished manuscript, 2013.
[23] Malvestuto, F. M., Pourabbas, E.: Local computation of answers to table queries on summary databases. Proc. XVII International Conference on Scientific and Statistical Database Management, Santa Barbara 2005, pp. 263-270.
[24] Mosteller, F.: On pooling data. J. Amer. Statist. Assoc. 43 (1948), 231-242. · doi:10.1080/01621459.1948.10483259
[25] Pearl, J.: Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann Pub., San Mateo 1988. · Zbl 0746.68089
[26] Pourabbas, E., Shoshani, A.: Efficient estimation of joint queries from multiple OLAP databases. ACM Trans. Database Systems 32 (2007), 1, Article No. 2. · Zbl 1475.68109 · doi:10.1145/1206049.1206051
[27] Pourabbas, E., Shoshani, A.: Improving estimation accuracy of aggregate queries on data cubes. Data and Knowledge Engrg. 69 (2010), 50-72. · doi:10.1016/j.datak.2009.08.010
[28] Shenoy, P. P., Shafer, G.: Axioms for probability and belief-function propagation. Uncertainty in Artificial Intelligence (R. D. Shachter, T. Levitt, J. F. Lemmer, and L. N. Kanel, North-Holland 1990, Vol. 4.
[29] Tarjan, R. E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13 (1984), 566-579. · Zbl 0562.68055 · doi:10.1137/0214020
[30] Verma, V., Gagliardi, F., Ferretti, C.: On Pooling Data and Measures. Working Paper No. 84 University of Siena, 2009.
[31] Vomlel, J.: Integrating inconsistent data in a probabilistic model. J. Appl. Non-Classical Logics 49 (2003), 4-22. · Zbl 1185.68699 · doi:10.3166/jancl.14.367-386
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.