| Title:
|
Marginalization in models generated by compositional expressions (English) |
| Author:
|
Malvestuto, Francesco M. |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
51 |
| Issue:
|
4 |
| Year:
|
2015 |
| Pages:
|
541-570 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
In the framework of models generated by compositional expressions, we solve two topical marginalization problems (namely, the single-marginal problem and the marginal-representation problem) that were solved only for the special class of the so-called “canonical expressions”. We also show that the two problems can be solved “from scratch” with preliminary symbolic computation. (English) |
| Keyword:
|
compositional expression |
| Keyword:
|
compositional model |
| Keyword:
|
marginalization |
| Keyword:
|
syntax tree |
| MSC:
|
05C65 |
| MSC:
|
05C85 |
| MSC:
|
60E99 |
| MSC:
|
65C50 |
| MSC:
|
68T37 |
| idZBL:
|
Zbl 06537773 |
| idMR:
|
MR3423187 |
| DOI:
|
10.14736/kyb-2015-4-0541 |
| . |
| Date available:
|
2015-11-20T12:12:09Z |
| Last updated:
|
2016-04-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144467 |
| . |
| Reference:
|
[1] Aho, A. V., Hopcroft, J. E., Ullman, J. D.: Data Structures and Algorithms..Addison-Wesley Pub. Co, Reading 1987. Zbl 0487.68005, MR 0666695 |
| Reference:
|
[2] Aji, S. M., McEliece, R.-J.: The generalized distributive law..IEEE Trans. Inform. Theory 46 (2000), 325-343. Zbl 0998.65146, MR 1748973, 10.1109/18.825794 |
| Reference:
|
[3] Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes..J. ACM 30 (1983), 479-513. Zbl 0624.68087, MR 0709830, 10.1145/2402.322389 |
| Reference:
|
[4] Bína, V., Jiroušek, R.: Marginalization in multidimensional compositional models..Kybernetika 42 (2006), 405-422. Zbl 1249.65010, MR 2280521 |
| Reference:
|
[5] Gaubert, S., Plus, Max: Methods and applications of (max, +) linear algebra..In: Proc. XIV Symp. on Theoretical Aspects of Computer Science Hansestatdt Luebeck 1997. 10.1007/bfb0023465 |
| Reference:
|
[6] 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:
|
[7] Jiroušek, R.: Marginalization in composed probabilistic models..In: Proc. XVI International Conf. on Uncertainty in Artificial Intelligence, (C. Boutilier and M. Goldszmidt, eds.), Morgan-Kauffmann Pub., San Francisco 2000, vol. C, pp. 301-308. 10.1016/b978-1-4832-1451-1.50041-x |
| 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.: Foundations of compositional model theory..Int. J. General Systems 40 (2011), 623-678. Zbl 1252.68285, MR 2817988, 10.1080/03081079.2011.562627 |
| Reference:
|
[10] Jiroušek, R.: Local computations in Dempster-Shafer theory of evidence..Int. J. Approx. Reasoning 53 (2012), 1155-1167. Zbl 1266.68177, MR 2971864, 10.1016/j.ijar.2012.06.012 |
| Reference:
|
[11] Jiroušek, R.: On causal compositional models: simple examples..In: Proc. XIV International Conference on Information Processing and Management of Uncertainty in Knowledge-Bases Systems (IPMU 2014) (A. Laurent et al., eds.), Part I, CCIS 442, pp. 517-526. 10.1007/978-3-319-08795-5_53 |
| Reference:
|
[12] Jiroušek, R., Kratochvíl, V.: Marginalization algorithm for compositional models..In: Proc. XI International Conference on Information Processing and Management of Uncertainty in Knowledge-Bases Systems (IPMU 2006) (B. Bouchon-Meunier and R.R. Yager, eds.), pp. 2300-2307. |
| Reference:
|
[13] Jiroušek, R., Kratochvíl, V.: Foundations of compositional models: structural properties..Int. J. General Systems 44 (2015), 2-25. MR 3299901, 10.1080/03081079.2014.934370 |
| Reference:
|
[14] Jiroušek, R., Shenoy, P. P.: Compositional models in valuation-based systems..Int. J. Approx. Reasoning 55 (2014), 277-293. Zbl 1252.68310, MR 3133554, 10.1016/j.ijar.2013.02.002 |
| Reference:
|
[15] Jiroušek, R., Vejnarová, J.: General framework for multidimensional models..Int. J. General Systems 18 (2003), 107-127. Zbl 1029.68131, 10.1002/int.10077 |
| Reference:
|
[16] 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:
|
[17] Kohlas, J.: Information algebras: generic structures for inference..Springer-Verlag, 2003. Zbl 1027.68060, 10.1007/978-1-4471-0009-6 |
| Reference:
|
[18] Kohlas, J., Pouly, M., Schneuwly, C.: Generic local computation..J. Comput. System Sciences 78 (2012), 348-369. Zbl 1255.68156, MR 2896367, 10.1016/j.jcss.2011.05.012 |
| Reference:
|
[19] Kohlas, J., Schmid, J.: An algebraic theory of information: an introduction and survey..Information 5 (2014), 219-254. 10.3390/info5020219 |
| Reference:
|
[20] Kohlas, J., Shenoy, P. P.: Computation in valuation algebras..In: Handbook of Defeasible Reasoning and Uncertainty Management Systems, Volume 5: Algorithms for Uncertainty and Defeasible Reasoning (J. Kohlas and S. Moral, eds.), Kluwer, Dordrecht 2000, pp. 5-39. Zbl 1015.68196, MR 1928265, 10.1007/978-94-017-1737-3_2 |
| Reference:
|
[21] Kohlas, J., Wilson, N.: Semiring induced valuation algebra: exact and approximate local computation algorithms..Artificial Intelligence 172 (2008), 1360-1399. MR 2422488, 10.1016/j.artint.2008.03.003 |
| Reference:
|
[22] Kratochvíl, V.: Probabilistic compositional models: solution of an equivalence problem..Int. J. Approx. Reasoning 54 (2013), 590-601. MR 3041095, 10.1016/j.ijar.2013.01.002 |
| Reference:
|
[23] Kschinschang, F. R., Frey, B. J., Loeliger, H.-A.: Factor graphs and the sum-product algorithm..IEEE Trans. Inform. Theory 47 (2001), 498-519. MR 1820474, 10.1109/18.910572 |
| Reference:
|
[24] Lauritzen, S. L.: Graphical Models..Oxford University Press, Oxford 1996. MR 1419991, 10.1002/(sici)1097-0258(19991115)18:21<2983::aid-sim198>3.0.co;2-a |
| Reference:
|
[25] Litvinov, G. L., (eds.), S. N. Sergeev: Proc. of the International Workshop TROPICAL-07 on Tropical and Idempotent Mathematics..Contemporary Mathematics 495 (2007), American Mathematical Society. MR 2581510, 10.1090/conm/616 |
| Reference:
|
[26] Malvestuto, F. M.: A join-like operator to combine data cubes, and answer queries from multiple data cubes..ACM Trans. Database Syst. 39 (2014), 3, 1-31. MR 3268995, 10.1145/2638545 |
| Reference:
|
[27] Malvestuto, F. M.: Equivalence of compositional expressions and independence relations in compositional models..Kybernetika 50 (2014), 322-362. MR 3245534, 10.14736/kyb-2014-3-0322 |
| Reference:
|
[28] Malvestuto, F. M.: Erratum: Equivalence of compositional expressions and independence relations in compositional models..Kybernetika 51 (2015), 387-388. MR 3350569, 10.14736/kyb-2015-2-0387 |
| Reference:
|
[29] Speyer, D., Sturmfels, B.: Tropical mathematics..Mathematics Magazine 82 (2009), 163-173. Zbl 1227.14051, MR 2522909, 10.4169/193009809x468760 |
| . |
