A New Method for Computing Elimination Ideals of Likelihood Equations
Pages 339 - 346
Abstract
We develop a probabilistic algorithm for computing elimination ideals of likelihood equations. We show experimentally that it is far more efficient than directly computing Groebner bases or the interpolation method for medium to large size models. Furthermore, we deduce discriminants of the elimination ideals, which play a central role in real root classification. In particular, we can compute the discriminant of one Jukes-Cantor model in phylogenetics (with size 8 GB text file).
References
[1]
C. Amendola, N. Bliss, I. Burke, C. R. Gibbons, M. Helmer, S. Hocsten, E. D. Nash, J. I. Rodriguez, and D. Smolkin. 2018. The maximum likelihood degree of toric varieties. (2018). Accepted by J. Symb. Comput. Arxiv: 1703.02251.
[2]
D. S. Arnon and S. Dennis. 1988. A cluster-based cylindrical algebraic decompoisition algorithm. J. Symb. Comput., Vol. 5, 1 (1988), 189--212.
[3]
S. Basu, R. Pollack, and M. F. Roy. 1996. On the combinatorial and algebraic complexity of quantifier elimination. Journal of ACM, Vol. 43, 6 (1996), 1002--1045.
[4]
S. Basu, R. Pollack, and M. F. Roy. 1999. Computing roadmaps of semi-algebraic sets on a variety. Journal of the AMS, Vol. 3, 1 (1999), 55--82.
[5]
S. Basu, R. Pollack, and M. F. Roy. 2006. Algorithms in Real Algebraic Geometry .Springer-Verlag.
[6]
E. Becker, M. G. Marinari, T. Mora, and C. Traverso. 1994. The shape of the Shape Lemma. In Proceedings of ISSAC'94. ACM New York, 129--133.
[7]
C. W. Brown. 2001 a. Improved projection for cylindrical algebraic decomposition. J. Symb. Comput., Vol. 32, 5 (2001), 447--465.
[8]
C. W. Brown. 2001 b. Simple CAD construction and its applications. J. Symb. Comput., Vol. 31, 5 (2001), 521--547.
[9]
C. W. Brown. 2003. QEPCAD B: a program for computing with semi-algebraic sets using CADs. ACM SIGSAM Bulletin, Vol. 37, 4 (2003), 97--108.
[10]
C. W. Brown. 2012. Fast simplifications for Tarski formulas based on monomial inequalities. J. Symb. Comput, Vol. 47, 7 (2012), 859--882.
[11]
C. W. Brown. 2013. Constructing a single open cell in a cylindrical algebraic decomposition. In ISSAC Proceedings of the International Symposium on Symbolic and Algebraic Computation. acm, 133--140.
[12]
B. Buchberger. 1965. An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. J. Symb. Comput., Vol. 41, 3 (1965), 475--511.
[13]
M.-L. G. Buot, S. Hocsten, and D. Richards. 2007. Counting and locating the solutions of polynomial systems of maximum likelihood equations, II: The Behrens-Fisher problem. Statistica Sinica, Vol. 17 (2007), 1343--1354.
[14]
F. Catanese, S. Hocsten, A. Khetan, and B. Sturmfels. 2006. The maximum likelihood degree. Amer. J. Math., Vol. 128, 3 (2006), 671--697.
[15]
C. Chen, J. H. Davemport, J. P. May, M. M. Maza, B. Xia, and R. Xiao. 2010. Triangular decomposition of semi-algebraic systems. In ISSAC'10 Proceedings of the 35th International Symposium on Symbolic and Algebraic Computation. ACM New York, 187--194.
[16]
G. E. Collins. 1975. Quantifier Elimination for the Elementary Theory of Real Closed Fields by Cylindrical Algebraic Decomposition. In Lecture Notes In Computer Science, Vol. 33. Springer-Verlag, Berlin, 134--183.
[17]
G. E. Collins and H. Hong. 1991. Cylindrical algebraic decomposition for quntifier elimination. J. Symb. Comput., Vol. 12, 3 (1991), 299--328.
[18]
D. A. Cox, J. Little, and D. Oshea. 2015. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra .Springer.
[19]
A. Dickenstein, M. P. Millán, A. Shiu, and X. Tang. 2019. Multistationarity in structrued reaction networks. Bulletin of Mathematical Biology., Vol. 81, 5 (2019), 1527--1581.
[20]
M. Drton, B. Sturmfels, and S. Sullivant. 2009. Lectures on algebraic statistics .Springer.
[21]
J. C. Faugère. 1999. A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra, Vol. 139, 1 (1999), 61--88.
[22]
J. C. Faugère, P. Gianni, D. Lazard, and T. Mora. 1993. Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. Symb. Comput., Vol. 16, 4 (1993), 329--344.
[23]
D. Grigoriev. 1988. Complexity of deciding Tarski algebra. J. Symb. Comput., Vol. 5, 1--2 (1988), 65--108.
[24]
E. Gross, M. Drton, and S. Petrović. 2012. Maximum likelihood degree of variance component models. Electronic Journal of Statistics, Vol. 6 (2012), 993--1016.
[25]
E. Gross and J. I. Rodriguez. 2014. Maximum likelihood geometry in the presence of data zeros. In ISSAC'14 Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. ACM New York, 232--239.
[26]
J. Hauenstein, J. I. Rodriguez, and B. Sturmfels. 2012. Maximum likelihood for matrices with rank constraints. Journal of Algebraic Statistics (2012). To Appear.
[27]
S. Hocsten, A. Khetan, and B. Sturmfels. 2005. Solving the likelihood equations. Foundations of Computational Mathematics, Vol. 5, 4 (2005), 389--407.
[28]
H. Hong. 1990. An improvement of the projection operator in cylindrical algebraic decomposition. In ISSAC Proceedings of the International Symposium on Symbolic and Algebraic Computation. ACM, 261--264.
[29]
H. Hong. 1992. Simple solution formula construction in cylindrical algebraic decomposition based quantifier elimination. In ISSAC Proceedings of the International Symposium on Symbolic and Algebraic Computation. ACM, 177--188.
[30]
H. Hong and M. Safey EI Din. 2012. Variant Quantifier Elimination. J. Symb. Comput., Vol. 47, 7 (2012), 883--901.
[31]
J. Huh and B. Sturmfels. 2014. Likelihood geometry. Number 63--117. Springer International Publishing.
[32]
D. Kapur, Y. Sun, and D. K. Wang. 2010. A new algorithm for computing comprehensive Gröbner systems. In ISSAC'10 Proceedings of the 35th International Symposium on Symbolic and Algebraic Computation. 29--36.
[33]
D. Lazard and F. Rouillier. 2005. Solving parametric polynomial systems. Journal of Symbolic Computation, Vol. 42, 6 (2005), 636--667.
[34]
S. McCallum. 1988. An improved projection operation for cylindrical algebraic decomposition of three-dimensional space. J. Symb. Comput., Vol. 5, 1 (1988), 141--161.
[35]
S. McCallum. 1999. On projection in CAD-Based quantifier elimination with equational constrants. In ISSAC Proceedings of the International Symposium on Symbolic and Algebraic Computation. ACM, 145--149.
[36]
J. Renegar. 1992a. On the computational comlexity and geometry of the first-order theory of the reals. Part I. J. Symb. Comput., Vol. 13, 3 (1992), 255--299.
[37]
J. Renegar. 1992b. On the computational comlexity and geometry of the first-order theory of the reals. Part II. J. Symb. Comput., Vol. 13, 3 (1992), 301--327.
[38]
J. Renegar. 1992c. On the computational comlexity and geometry of the first-order theory of the reals. Part III. J. Symb. Comput., Vol. 13, 3 (1992), 329--352.
[39]
J. I. Rodriguez and X. Tang. 2015. Data-Discriminants of Likelihood Equations. In ISSAC'15 Proceedings of the 40th International Symposium on Symbolic and Algebraic Computation. ACM New York, 307--314.
[40]
J. I. Rodriguez and X. Tang. 2017. A Probabilistic Algorithm for Computing Data-Discriminants of Likelihood Equations. Journal of Symbolic Computation, Vol. 83 (2017), 342--364.
[41]
M. Safey EI Din and E. Schost. 2003. Polar varieties and computation of one point in each connected component of a smooth real algebraic set. In ISSAC'03 Proceedings of International Symposium on Symbolic and Algebraic Computation. 224--231.
[42]
M. Safey EI Din and E. Schost. 2004. Properness defects of projections and computaion of in each connected component of a real algebraic set. Discrete and Computational Geometry, Vol. 32, 3 (2004), 417--430.
[43]
B. Sturmfels. 2002. Solving systems of polynomial equations. In Regional conference series in mathematics. Vol. 97. American Mathematical Society, Providence, R. I.
[44]
S. Sullivant. 2018. Algebraic Statistics. Graduate Studies in Mathematics, Vol. 194. American Mathematical Society.
[45]
A. Tarski. 1951. A decision method for elementary algebra and geometry. University of California Press. University of California Press. University of California Press.
[46]
M. B. Villarino, W. Gasarch, and K. W. Regan. 2018. Hilbert's proof of his irreducibility theorem. The American Mathematical Monthly, Vol. 125, 6 (2018), 513--530.
[47]
L. Yang, X. Hou, and B. Xia. 2001. A complete algorithm for automated discovering of a class of inequality-type theorems. Science in China Series F: Information Sciences, Vol. 44, 1 (2001), 33--49.
Index Terms
- A New Method for Computing Elimination Ideals of Likelihood Equations
Recommendations
Data-Discriminants of Likelihood Equations
ISSAC '15: Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic ComputationMaximum likelihood estimation (MLE) is a fundamental computational problem in statistics. The problem is to maximize the likelihood function with respect to given data on a statistical model. An algebraic approach to this problem is to solve a very ...
Computing all roots of the likelihood equations of seemingly unrelated regressions
Seemingly unrelated regressions are statistical regression models based on the Gaussian distribution. They are popular in econometrics but also arise in graphical modeling of multivariate dependencies. In maximum likelihood estimation, the parameters of ...
The Large Sample Performance of a Maximum Likelihood Method for OFDM Carrier Frequency Offset Estimation
This paper is concerned with the performance analysis of a blind method for carrier frequency offset (CFO) estimation in OFDM systems. The method generates a maximum likelihood CFO estimate when message-carrying symbols and channel are assumed ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2019
418 pages
ISBN:9781450360845
DOI:10.1145/3326229
- General Chairs:
- James Davenport,
- Dongming Wang,
- Program Chair:
- Manuel Kauers,
- Publications Chair:
- Russell Bradford
Copyright © 2019 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 July 2019
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- DFG
- NSF
Conference
ISSAC '19
ISSAC '19: International Symposium on Symbolic and Algebraic Computation
July 15 - 18, 2019
Beijing, China
Acceptance Rates
Overall Acceptance Rate 395 of 838 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 264Total Downloads
- Downloads (Last 12 months)44
- Downloads (Last 6 weeks)7
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in