Geodesic
Equivalence of compositional expressions and independence relations in compositional models
Kybernetika, Tome 50 (2014) no. 3, pp. 322-362
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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 $\cal H$ is star-like with centre $X$ if and only if every two compositional expressions with “base scheme” $\cal H$ and “key” $X$ are equivalent. This result is stronger than Jiroušek's result which states that, if $\cal H$ is star-like with centre $X$, then every two generating sequences with base scheme $\cal 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 $\cal H$ such that every two canonical expressions with base scheme $\cal 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.
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 $\cal H$ is star-like with centre $X$ if and only if every two compositional expressions with “base scheme” $\cal H$ and “key” $X$ are equivalent. This result is stronger than Jiroušek's result which states that, if $\cal H$ is star-like with centre $X$, then every two generating sequences with base scheme $\cal 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 $\cal H$ such that every two canonical expressions with base scheme $\cal 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.
DOI : 10.14736/kyb-2014-3-0322
Classification : 05C65, 05C85, 60E99, 62H05, 62H99, 65C50, 68T37
Keywords: compositional expression; compositional model; running intersection property; perfect sequence 
@article{10_14736_kyb_2014_3_0322,
     author = {Malvestuto, Francesco M.},
     title = {Equivalence of compositional expressions and independence relations in compositional models},
     journal = {Kybernetika},
     pages = {322--362},
     year = {2014},
     volume = {50},
     number = {3},
     doi = {10.14736/kyb-2014-3-0322},
     mrnumber = {3245534},
     zbl = {06357554},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2014-3-0322/}
}
TY  - JOUR
AU  - Malvestuto, Francesco M.
TI  - Equivalence of compositional expressions and independence relations in compositional models
JO  - Kybernetika
PY  - 2014
SP  - 322
EP  - 362
VL  - 50
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2014-3-0322/
DO  - 10.14736/kyb-2014-3-0322
LA  - en
ID  - 10_14736_kyb_2014_3_0322
ER  - 
%0 Journal Article
%A Malvestuto, Francesco M.
%T Equivalence of compositional expressions and independence relations in compositional models
%J Kybernetika
%D 2014
%P 322-362
%V 50
%N 3
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2014-3-0322/
%R 10.14736/kyb-2014-3-0322
%G en
%F 10_14736_kyb_2014_3_0322
Malvestuto, Francesco M. Equivalence of compositional expressions and independence relations in compositional models. Kybernetika, Tome 50 (2014) no. 3, pp. 322-362. doi: 10.14736/kyb-2014-3-0322

[1] Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. Assoc. Comput. Mach. 30 (1983), 479-513. | DOI | MR | Zbl

[2] Blair, J. R. S., Peyton, B.W.: An Introduction to Chordal Graphs and Clique Trees. Technical Report ORNL/TM-12203, 1992. | MR | Zbl

[3] Csiszár, I.: $I$-divergence geometry of probability distributions and minimization problems. Ann. Probab. 3 (1975), 146-158. | DOI | MR | Zbl

[4] Dawid, A. P.: Applications of a general propagation algorithm for probabilistic expert systems. Statist. Comput. 2 (1992), 25-36. | DOI

[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. | DOI | MR

[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. | MR

[7] Jiroušek, R.: Composition of probability measures on finite spaces. In: Proc. XIII International Conf. on Uncertainty in Artificial Intelligence (D. Geiger and P. P. Shenoy, eds.), 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. | DOI | MR | Zbl

[9] Jiroušek, R.: Detection of independence relations from persegrams. In: 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. In: Proc. XII International Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems (L. Magdalena, M. Ojeda-Aciego and J. L. Verdegay, eds.), Malaga 2008, pp. 915-922.

[11] Jiroušek, R.: Foundations of compositional model theory. Internat. J. General Systems 40 (2011), 623-678. | DOI | MR | Zbl

[12] Jiroušek, R.: Local computations in Dempster-Shafer theory of evidence. Internat. J. Approx. Reason. 53 (2012), 1155-1167. | DOI | MR | Zbl

[13] Jiroušek, R., Shenoy, P. P.: Compositional models in valuation-based systems. Internat. J. Approx. Reason. 55 (2014), 277-293. | DOI | MR | Zbl

[14] Jiroušek, R., Vejnarová, J.: General framework for multidimensional models. Internat. J. Approx. Reas. 18 (2003), 107-127. | Zbl

[15] Jiroušek, R., Vejnarová., J., Daniels, M.: Composition models of belief functions. In: Proc. V Symp. on Imprecise Probabilities and Their Applications (G. De Cooman, J. Vejnarová, and M. Zaffalon, eds.), 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. | DOI | MR | Zbl

[17] Kratochvíl, V.: Probabilistic compositional models: solution of an equivalence problem. Internat. J. Approx. Reason. 54 (2013), 590-601. | DOI | MR

[18] Lauritzen, S. L.: Graphical Models. Oxford University Press, Oxford 1996. | MR

[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. | MR

[20] Malvestuto, F. M.: Tree and local computations in a cross-entropy minimization problem with marginal constraints. Kybernetika 46 (2010), 621-654. | MR | Zbl

[21] Malvestuto, F. M.: The sum-product algorithm: algebraic independence and computational aspects. Kybernetika 49 (2013), 4-22. | MR

[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. In: 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

[25] Pearl, J.: Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann Pub., San Mateo 1988. | MR | Zbl

[26] Pourabbas, E., Shoshani, A.: Efficient estimation of joint queries from multiple OLAP databases. ACM Trans. Database Systems 32 (2007), 1, Article No. 2. | DOI

[27] Pourabbas, E., Shoshani, A.: Improving estimation accuracy of aggregate queries on data cubes. Data and Knowledge Engrg. 69 (2010), 50-72. | DOI

[28] Shenoy, P. P., Shafer, G.: Axioms for probability and belief-function propagation. In: Uncertainty in Artificial Intelligence (R. D. Shachter, T. Levitt, J. F. Lemmer, and L. N. Kanel, eds.), North-Holland 1990, Vol. 4. | MR

[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. | DOI | MR | Zbl

[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

Cité par Sources :