| Title:
|
Equivalence of compositional expressions and independence relations in compositional models (English) |
| Author:
|
Malvestuto, Francesco M. |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
50 |
| Issue:
|
3 |
| Year:
|
2014 |
| Pages:
|
322-362 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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 $\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. (English) |
| Keyword:
|
compositional expression |
| Keyword:
|
compositional model |
| Keyword:
|
running intersection property |
| Keyword:
|
perfect sequence |
| MSC:
|
05C65 |
| MSC:
|
05C85 |
| MSC:
|
60E99 |
| MSC:
|
62H05 |
| MSC:
|
62H99 |
| MSC:
|
65C50 |
| MSC:
|
68T37 |
| idZBL:
|
Zbl 06357554 |
| idMR:
|
MR3245534 |
| DOI:
|
10.14736/kyb-2014-3-0322 |
| . |
| Date available:
|
2014-07-29T13:07:31Z |
| Last updated:
|
2016-01-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143879 |
| . |
| Related article:
|
http://dml.cz/handle/10338.dmlcz/144305 |
| . |
| Reference:
|
[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, MR 0709830, 10.1145/2402.322389 |
| Reference:
|
[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, MR 1320296 |
| Reference:
|
[3] Csiszár, I.: $I$-divergence geometry of probability distributions and minimization problems..Ann. Probab. 3 (1975), 146-158. Zbl 0318.60013, MR 0365798, 10.1214/aop/1176996454 |
| Reference:
|
[4] Dawid, A. P.: Applications of a general propagation algorithm for probabilistic expert systems..Statist. Comput. 2 (1992), 25-36. 10.1007/BF01890546 |
| Reference:
|
[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. MR 0003527, 10.1214/aoms/1177731829 |
| Reference:
|
[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 2266415 |
| Reference:
|
[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. |
| Reference:
|
[8] Jiroušek, R.: Decomposition of multidimensional distributions represented by perfect sequences..Ann. Math. Artif. Intelligence 5 (2002), 215-226. Zbl 1004.60010, MR 1899952, 10.1023/A:1014591402750 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[11] Jiroušek, R.: Foundations of compositional model theory..Internat. J. General Systems 40 (2011), 623-678. Zbl 1252.68285, MR 2817988, 10.1080/03081079.2011.562627 |
| Reference:
|
[12] Jiroušek, R.: Local computations in Dempster-Shafer theory of evidence..Internat. J. Approx. Reason. 53 (2012), 1155-1167. Zbl 1266.68177, MR 2971864, 10.1016/j.ijar.2012.06.012 |
| Reference:
|
[13] Jiroušek, R., Shenoy, P. P.: Compositional models in valuation-based systems..Internat. J. Approx. Reason. 55 (2014), 277-293. Zbl 1252.68310, MR 3133554, 10.1016/j.ijar.2013.02.002 |
| Reference:
|
[14] Jiroušek, R., Vejnarová, J.: General framework for multidimensional models..Internat. J. Approx. Reas. 18 (2003), 107-127. Zbl 1029.68131 |
| Reference:
|
[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. |
| Reference:
|
[16] Kratochvíl, V.: Characteristic properties of equivalent structures in compositional models..Internat. J. Approx. Reason. 52 (2011), 599-612. Zbl 1214.68400, MR 2787020, 10.1016/j.ijar.2010.12.005 |
| Reference:
|
[17] Kratochvíl, V.: Probabilistic compositional models: solution of an equivalence problem..Internat. J. Approx. Reason. 54 (2013), 590-601. MR 3041095, 10.1016/j.ijar.2013.01.002 |
| Reference:
|
[18] Lauritzen, S. L.: Graphical Models..Oxford University Press, Oxford 1996. MR 1419991 |
| Reference:
|
[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 2497221 |
| Reference:
|
[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, MR 2722092 |
| Reference:
|
[21] Malvestuto, F. M.: The sum-product algorithm: algebraic independence and computational aspects..Kybernetika 49 (2013), 4-22. MR 3088472 |
| Reference:
|
[22] Malvestuto, F. M.: A join-like operator to combine data cubes, and answer queries from multiple data cubes..Unpublished manuscript, 2013. |
| Reference:
|
[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. |
| Reference:
|
[24] Mosteller, F.: On pooling data..J. Amer. Statist. Assoc. 43 (1948), 231-242. 10.1080/01621459.1948.10483259 |
| Reference:
|
[25] Pearl, J.: Probabilistic Reasoning in Intelligent Systems..Morgan Kaufmann Pub., San Mateo 1988. Zbl 0746.68089, MR 0965765 |
| Reference:
|
[26] Pourabbas, E., Shoshani, A.: Efficient estimation of joint queries from multiple OLAP databases..ACM Trans. Database Systems 32 (2007), 1, Article No. 2. 10.1145/1206049.1206051 |
| Reference:
|
[27] Pourabbas, E., Shoshani, A.: Improving estimation accuracy of aggregate queries on data cubes..Data and Knowledge Engrg. 69 (2010), 50-72. 10.1016/j.datak.2009.08.010 |
| Reference:
|
[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 1166831 |
| Reference:
|
[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, MR 0749707, 10.1137/0213035 |
| Reference:
|
[30] Verma, V., Gagliardi, F., Ferretti, C.: On Pooling Data and Measures..Working Paper No. 84 University of Siena, 2009. |
| Reference:
|
[31] Vomlel, J.: Integrating inconsistent data in a probabilistic model..J. Appl. Non-Classical Logics 49 (2003), 4-22. Zbl 1185.68699 |
| . |
