jmlr jmlr2012 jmlr2012-15 jmlr2012-15-reference knowledge-graph by maker-knowledge-mining

15 jmlr-2012-Algebraic Geometric Comparison of Probability Distributions


Source: pdf

Author: Franz J. Király, Paul von Bünau, Frank C. Meinecke, Duncan A.J. Blythe, Klaus-Robert Müller

Abstract: We propose a novel algebraic algorithmic framework for dealing with probability distributions represented by their cumulants such as the mean and covariance matrix. As an example, we consider the unsupervised learning problem of finding the subspace on which several probability distributions agree. Instead of minimizing an objective function involving the estimated cumulants, we show that by treating the cumulants as elements of the polynomial ring we can directly solve the problem, at a lower computational cost and with higher accuracy. Moreover, the algebraic viewpoint on probability distributions allows us to invoke the theory of algebraic geometry, which we demonstrate in a compact proof for an identifiability criterion. Keywords: computational algebraic geometry, approximate algebra, unsupervised Learning


reference text

Shun’ichi Amari and Hiroshi Nagaoka. Methods of Information Geometry, volume 191 of Translations of mathematical monographs. American Mathematical Society, 2000. ISBN 9780821805312. Duncan A. J. Blythe, Paul von B¨ nau, Frank C. Meinecke, and Klaus-Robert M¨ ller. Feature extracu u tion for change-point detection using stationary subspace analysis. IEEE Transactions on Neural Networks and Learning Systems, 23(4):631–643, 2012. doi: 10.1109/TNNLS.2012.2185811. Massimo Caboara, Pasqualina Conti, and Carlo Traverse. Yet another ideal decomposition algorithm. In Teo Mora and Harold Mattson, editors, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, volume 1255 of Lecture Notes in Computer Science, pages 39–54. Springer Berlin / Heidelberg, 1997. Robert M. Corless, Patrizia M. Gianni, Barry M. Trager, and Steven M. Watt. The singular value decomposition for polynomial systems. Proc. ISSAC ’95, pages 195–207, 1995. David A. Cox, John Little, and Donal O’Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3/e (Undergraduate Texts in Mathematics). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2007. ISBN 0387356509. Mathias Drton, Bernd Sturmfels, and Seth Sullivant. Lectures on Algebraic Statistics. Oberwolfach Seminars. Birkhauser Basel, 2010. ISBN 9783764389048. David Eisenbud, Craig Huneke, and Wolmer Vasconcelos. Direct methods for primary decomposition. Inventiones Mathematicae, 110:207–235, 1992. ISSN 0020-9910. 901 ´ ¨ ¨ K IR ALY, VON B UNAU , M EINECKE , B LYTHE AND M ULLER Ronald A. Fisher. The use of multiple measurements in taxonomic problems. Annals Eugen., 7: 179–188, 1936. Jerome H. Friedman and John W. Tukey. A projection pursuit algorithm for exploratory data analysis. Computers, IEEE Transactions on, C-23(9):881 – 890, 9 1974. ISSN 0018-9340. doi: 10.1109/T-C.1974.224051. Ralf Fr¨ berg and Joachim Hollman. Hilbert series for ideals generated by generic forms. Journal of o Symbolic Computation, 17(2):149 – 157, 1994. ISSN 0747-7171. doi: DOI:10.1006/jsco.1994. 1008. Patrizia Gianni, Barry Trager, and Gail Zacharias. Groebner bases and primary decomposition of polynomial ideals. Journal of Symbolic Computation, 6(2-3):149 – 167, 1988. ISSN 0747-7171. doi: DOI:10.1016/S0747-7171(88)80040-3. Paolo Gibilisco, Eva Riccomagno, Maria Piera Rogantin, and Henry P. Wynn. Algebraic and Geometric Methods in Statistics. Cambridge University Press, 2010. ISBN 9780521896191. Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Sch¨ lkopf, and Alexander Smola. A o kernel method for the two sample problem. In Advances in Neural Information Processing Systems 19, pages 513–520. MIT Press, 2007. Satoshi Hara, Yoshinobu Kawahara, Takashi Washio, and Paul von B¨ nau. Stationary subspace u analysis as a generalized eigenvalue problem. In Proceedings of the 17th international conference on Neural information processing: theory and algorithms - Volume Part I, ICONIP’10, pages 422–429, Berlin, Heidelberg, 2010. Springer-Verlag. Daniel Heldt, Martin Kreuzer, Sebastian Pokutta, and Hennie Poulisse. Approximate computation of zero-dimensional polynomial ideals. Journal of Symbolic Computation, 44(11):1566 – 1591, 2009. ISSN 0747-7171. doi: DOI:10.1016/j.jsc.2008.11.010. In Memoriam Karin Gatermann. Grete Hermann. Die Frage der endlich vielen Schritte in der Theorie der Polynomideale - unter Benutzung nachgelassener S¨ tze von K. Hentzelt. Mathematische Annalen, 95(1):736 – 788, a 1926. ISSN 0747-7171. doi: DOI:10.1007/BF01206635. Harold Hotelling. The generalization of student’s ratio. Annals of Mathematical Statistics, 2(3): 360–378, 1932. Anthony Iarrobino. Compressed algebras: Artin algebras having given socle degrees and maximal length. Transactions of the American Mathematical Society, 285(1):337 – 378, 1984. Franz J. Kir´ ly, Paul von B¨ nau, Frank Meinecke, Duncan Blythe, and Klaus-Robert M¨ ller. Algea u u braic geometric comparison of probability distributions, 2011. Oberwolfach Preprint 2011-30. Risi Kondor. The skew spectrum of functions on finite groups and their homogeneous spaces, 2007. Eprint arXiv:0712.4259. Risi Kondor and Karsten M. Borgwardt. The skew spectrum of graphs. In Proceedings of the 25th international conference on Machine learning, ICML ’08, pages 496–503, New York, NY, USA, 2008. ACM. ISBN 978-1-60558-205-4. doi: http://doi.acm.org/10.1145/1390156.1390219. 902 A LGEBRAIC G EOMETRIC C OMPARISON OF P ROBABILITY D ISTRIBUTIONS Martin Kreuzer, Hennie Poulisse, and Lorenzo Robbiano. Approximate Commutative Algebra, chapter From Oil Fields to Hilbert Schemes. Springer-Verlag Berlin Heidelberg, 2009. Teresa Krick and Alessandro Logar. An algorithm for the computation of the radical of an ideal in the ring of polynomials. In Harold Mattson, Teo Mora, and T. Rao, editors, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, volume 539 of Lecture Notes in Computer Science, pages 195–205. Springer Berlin / Heidelberg, 1991. Santiago Laplagne. An algorithm for the computation of the radical of an ideal. In Proceedings of the 2006 international symposium on Symbolic and algebraic computation. ACM, 2006. Frank C. Meinecke, Paul von B¨ nau, Motoaki Kawanabe, and Klaus-Robert M¨ ller. Learning u u invariances with stationary subspace analysis. In Computer Vision Workshops (ICCV Workshops), 2009 IEEE 12th International Conference on, pages 87 –92, 2009. doi: 10.1109/ICCVW.2009. 5457715. Jan S. M¨ ller, Paul von B¨ nau, Frank C. Meinecke, Frank J. Kir´ ly, and Klaus-Robert M¨ ller. The u u a u stationary subspace analysis toolbox. Journal of Machine Learning Research, 12:3065–3069, 2011. Keith Pardue. Generic sequences of polynomials. Journal of Algebra, 324(4):579 – 590, 2010. ISSN 0021-8693. doi: DOI:10.1016/j.jalgebra.2010.04.018. Hans J. Stetter. Numerical polynomial algebra. Society for Industrial and Applied Mathematics, 2004. ISBN 0898715571. Bernd Sturmfels. Solving Systems of Polynomial Equations, volume 97 of CBMS Regional Conferences Series. Amer. Math. Soc., Providence, Rhode Island, 2002. Kari Torkkola. Feature extraction by non parametric mutual information maximization. J. Mach. Learn. Res., 3:1415–1438, March 2003. ISSN 1532-4435. URL http://portal.acm.org/ citation.cfm?id=944919.944981. Ren´ Vidal, Yi Ma, and Sastry Shankar. Generalized principal component analysis (GPCA). IEEE e Transactions on Pattern Analysis and Machine Intelligence, 27(12), 2005. Paul von B¨ nau, Frank C. Meinecke, Franz J. Kir´ ly, and Klaus-Robert M¨ ller. Finding stationary u a u subspaces in multivariate time series. Phys. Rev. Lett., 103(21):214101, Nov 2009. doi: 10.1103/ PhysRevLett.103.214101. Paul von B¨ nau, Frank C. Meinecke, Simon Scholler, and Klaus-Robert M¨ ller. Finding stationary u u brain sources in EEG data. In Proceedings of the 32nd Annual Conference of the IEEE EMBS, pages 2810–2813, 2010. Sumio Watanabe. Algebraic Geometry and Statistical Learning Theory. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, United Kingdom, 2009. ISBN 9780521864671. 903