Equivalence of compositional expressions and independence relations in compositional models

Francesco M. Malvestuto

Kybernetika (2014)

  • Volume: 50, Issue: 3, page 322-362
  • ISSN: 0023-5954

Abstract

top
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 ℋ is star-like with centre X if and only if every two compositional expressions with “base scheme” ℋ and “key” X are equivalent. This result is stronger than Jiroušek’s result which states that, if ℋ is star-like with centre X , then every two generating sequences with base scheme ℋ and key X are equivalent. Then, we focus on canonical expressions, by which we mean compositional expressions θ such that the sequence of the sets featured in θ 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 ℋ such that every two canonical expressions with base scheme ℋ 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.

How to cite

top

Malvestuto, Francesco M.. "Equivalence of compositional expressions and independence relations in compositional models." Kybernetika 50.3 (2014): 322-362. <http://eudml.org/doc/261903>.

@article{Malvestuto2014,
abstract = {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.},
author = {Malvestuto, Francesco M.},
journal = {Kybernetika},
keywords = {compositional expression; compositional model; running intersection property; perfect sequence; compositional expression; compositional model; running intersection property; perfect sequence},
language = {eng},
number = {3},
pages = {322-362},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Equivalence of compositional expressions and independence relations in compositional models},
url = {http://eudml.org/doc/261903},
volume = {50},
year = {2014},
}

TY - JOUR
AU - Malvestuto, Francesco M.
TI - Equivalence of compositional expressions and independence relations in compositional models
JO - Kybernetika
PY - 2014
PB - Institute of Information Theory and Automation AS CR
VL - 50
IS - 3
SP - 322
EP - 362
AB - 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.
LA - eng
KW - compositional expression; compositional model; running intersection property; perfect sequence; compositional expression; compositional model; running intersection property; perfect sequence
UR - http://eudml.org/doc/261903
ER -

References

top
  1. Beeri, C., Fagin, R., Maier, D., Yannakakis, M., 10.1145/2402.322389, J. Assoc. Comput. Mach. 30 (1983), 479-513. Zbl0624.68087MR0709830DOI10.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. Zbl0803.68081MR1320296
  3. Csiszár, I., 10.1214/aop/1176996454, Ann. Probab. 3 (1975), 146-158. Zbl0318.60013MR0365798DOI10.1214/aop/1176996454
  4. Dawid, A. P., 10.1007/BF01890546, Statist. Comput. 2 (1992), 25-36. DOI10.1007/BF01890546
  5. Deming, W. E., Stephan, F. F., 10.1214/aoms/1177731829, Ann. Math. Stat. 11 (1940), 427-444. MR0003527DOI10.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. MR2266415
  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., 10.1023/A:1014591402750, Ann. Math. Artif. Intelligence 5 (2002), 215-226. Zbl1004.60010MR1899952DOI10.1023/A:1014591402750
  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., 10.1080/03081079.2011.562627, Internat. J. General Systems 40 (2011), 623-678. Zbl1252.68285MR2817988DOI10.1080/03081079.2011.562627
  12. Jiroušek, R., 10.1016/j.ijar.2012.06.012, Internat. J. Approx. Reason. 53 (2012), 1155-1167. Zbl1266.68177MR2971864DOI10.1016/j.ijar.2012.06.012
  13. Jiroušek, R., Shenoy, P. P., 10.1016/j.ijar.2013.02.002, Internat. J. Approx. Reason. 55 (2014), 277-293. Zbl1252.68310MR3133554DOI10.1016/j.ijar.2013.02.002
  14. Jiroušek, R., Vejnarová, J., General framework for multidimensional models., Internat. J. Approx. Reas. 18 (2003), 107-127. Zbl1029.68131
  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., 10.1016/j.ijar.2010.12.005, Internat. J. Approx. Reason. 52 (2011), 599-612. Zbl1214.68400MR2787020DOI10.1016/j.ijar.2010.12.005
  17. Kratochvíl, V., 10.1016/j.ijar.2013.01.002, Internat. J. Approx. Reason. 54 (2013), 590-601. MR3041095DOI10.1016/j.ijar.2013.01.002
  18. Lauritzen, S. L., Graphical Models., Oxford University Press, Oxford 1996. MR1419991
  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. MR2497221
  20. Malvestuto, F. M., Tree and local computations in a cross-entropy minimization problem with marginal constraints., Kybernetika 46 (2010), 621-654. Zbl1204.93113MR2722092
  21. Malvestuto, F. M., The sum-product algorithm: algebraic independence and computational aspects., Kybernetika 49 (2013), 4-22. MR3088472
  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., 10.1080/01621459.1948.10483259, J. Amer. Statist. Assoc. 43 (1948), 231-242. DOI10.1080/01621459.1948.10483259
  25. Pearl, J., Probabilistic Reasoning in Intelligent Systems., Morgan Kaufmann Pub., San Mateo 1988. Zbl0746.68089MR0965765
  26. Pourabbas, E., Shoshani, A., 10.1145/1206049.1206051, ACM Trans. Database Systems 32 (2007), 1, Article No. 2. DOI10.1145/1206049.1206051
  27. Pourabbas, E., Shoshani, A., 10.1016/j.datak.2009.08.010, Data and Knowledge Engrg. 69 (2010), 50-72. DOI10.1016/j.datak.2009.08.010
  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. MR1166831
  29. Tarjan, R. E., Yannakakis, M., 10.1137/0213035, SIAM J. Comput. 13 (1984), 566-579. Zbl0562.68055MR0749707DOI10.1137/0213035
  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. Zbl1185.68699

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.