Previous |  Up |  Next


0/1 polytopes; linear codes; hierarchical models; exponential families
In this paper, we explore a connection between binary hierarchical models, their marginal polytopes, and codeword polytopes, the convex hulls of linear codes. The class of linear codes that are realizable by hierarchical models is determined. We classify all full dimensional polytopes with the property that their vertices form a linear code and give an algorithm that determines them.
[1] N. Ay and A. Knauf: Maximizing multi-information. Kybernetika 42 (2006), 517–538. MR 2283503
[2] S. Amari: Information geometry on hierarchy of probability distributions. IEEE Trans. Inform. Theory 47 (2001), 1701–1711. MR 1842511 | Zbl 0997.94009
[3] E. Caianiello: Synthesis of boolean nets and time behaviour of a general mathematical neuron. Biol. Cybernet. 18 (1975), 111–117. MR 0530379
[4] E. Caianiello: Neuronic equations revisited and completely solved. In: Brain Theory (G. Palm and A. Aertsen, eds.), Springer, Berlin 1986. MR 0847249
[5] I. Csiszár: $I$-divergence geometry of probability distributions and minimization problems. Ann. Probab. 3 (1975), 146–158. MR 0365798
[6] M. M. Deza and M. Laurent: Geometry of Cuts and Metrics. Algorithms and Combinatorics. Springer, Berlin 1997. MR 1460488
[7] J. N. Darroch and T. P. Speed: Additive and multiplicative models and interactions. Ann. Statist. 11 (1983), 3, 724–738. MR 0707924
[8] J. Feldman, M. Wainwright, and D. R. Karger: Using linear programming to decode linear codes. IEEE Trans. Inform. Theory 51 (2005), 3, 954–972. MR 2237962
[9] H.-O. Georgii: Gibbs Measures and Phase Transitions (de Gruyter Studies in Mathematics 9). Walter de Gruyter, Berlin 1988. MR 0956646
[10] E. Gawrilow and M. Joswig: polymake: a framework for analyzing convex polytopes. Polytopes – Combinatorics and Computation, pp. 43–47. Birkhäuser, Basel 2000. MR 1785292
[11] S. Hoşten and S. Sullivant: Gröbner bases and polyhedral geometry of reducible and cyclic models. J. Combin. Theory Ser. A 100 (2002), 2, 277–301. MR 1940337
[12] T. Kahle and N. Ay: Support sets of distributions with given interaction structure. In: Proc. WUPES 2006, 2006.
[13] T. Kahle: Neighborliness of marginal polytopes. 2008. submitted, arXiv:0809.0786.
[14] S. Kullback: Information Theory and Statistics. Dover, New York 1968. MR 1461541 | Zbl 0897.62003
[15] S. L. Lauritzen: Graphical Models. (Oxford Statistical Science Series.) Oxford University Press, 1996. MR 1419991 | Zbl 1055.62126
[16] J. H. van Lint: Introduction to Coding Theory. GTM. Third edition. Springer, Berlin 1999. MR 1664228 | Zbl 0936.94014
[17] W. Wenzel: Regular simplices inscribed into the cube and exhibiting a group structure. J. Combin. Math. Combin. Comput. 59 (2006), 213–220. MR 2277349 | Zbl 1127.52012
[18] G. Winkler: Image Analysis, Random Fields and Markov Chain Monte Carlo Methods. Second edition. Springer, Berlin 2003. MR 1950762 | Zbl 1008.68147
[19] M. J. Wainwright and M. I. Jordan: Variational inference in graphical models: The view from the marginal polytope. In: Allerton Conference on Communication, Control, and Computing, 2003.
[20] G. M. Ziegler: Lectures on Polytopes. GTM 142, Springer, Berlin 1994. MR 1311028 | Zbl 0823.52002
[21] G. M. Ziegler: Lectures on 0/1 polytopes. In: Polytopes – Combinatorics and Computation (G. Kalai and G. M. Ziegler, eds.), pp. 1–41. Birkhäuser, Basel 2000. MR 1785291 | Zbl 0966.52012
Partner of
EuDML logo