×

A probabilistic algorithm for computing data-discriminants of likelihood equations. (English) Zbl 1373.62090

Summary: An algebraic approach to the maximum likelihood estimation problem is to solve a very structured parameterized polynomial system called likelihood equations that have finitely many complex (real or non-real) solutions. The only solutions that are statistically meaningful are the real solutions with positive coordinates. In order to classify the parameters (data) according to the number of real/positive solutions, we study how to efficiently compute the discriminants, say data-discriminants (DD), of the likelihood equations. We develop a probabilistic algorithm with three different strategies for computing DDs. Our implemented probabilistic algorithm based on and is more efficient than our previous version [in: Proceedings of the 40th international symposium on symbolic and algebraic computation, ISSAC 2015, Bath, UK, July 6–9, 2015. New York, NY: Association for Computing Machinery (ACM). 307–314 (2015; Zbl 1345.65003)] and is also more efficient than the standard elimination for larger benchmarks. By applying RAGlib to a DD we compute, we give the real root classification of 3 by 3 symmetric matrix model.

MSC:

62F10 Point estimation
68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)

Citations:

Zbl 1345.65003

Software:

QEPCAD; FGb; Kronecker; RAGlib
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Budur, N.; Wang, B., The signed Euler characteristic of very affine varieties, Int. Math. Res. Not., 14, 5710-5714 (2015) · Zbl 1362.14062
[2] Buot, M.-L. G.; Hoşten, S.; Richards, D., Counting and locating the solutions of polynomial systems of maximum likelihood equations, II: the Behrens-Fisher problem, Stat. Sin., 17, 1343-1354 (2007) · Zbl 1132.62041
[3] Catanese, F.; Hoşten, S.; Khetan, A.; Sturmfels, B., The maximum likelihood degree, Am. J. Math., 128, 3, 671-697 (2006) · Zbl 1123.13019
[4] Chen, C.; Davemport, J. H.; May, J. P.; Maza, M. M.; Xia, B.; Xiao, R., Triangular decomposition of semi-algebraic systems, (Proceedings of ISSAC’10 (2010), ACM: ACM New York), 187-194 · Zbl 1321.68526
[5] Collins, G. E.; Hong, H., Partial Cylindrical Algebraic Decomposition for Quantifier Elimination (1998), Springer · Zbl 0900.03052
[6] Coste, M.; Shiota, M., Nash triviality in families of Nash manifolds, Invent. Math., 108, 1, 349-368 (1992) · Zbl 0801.14017
[7] Cox, D. A.; Little, J.; Oshea, D., Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (2007), Springer
[8] Draisma, J.; Horobet, E.; Ottaviani, G.; Sturmfels, B.; Thomas, R. R., The Euclidean distance degree of an algebraic variety, Found. Comput. Math., 16, 1, 99-149 (2016) · Zbl 1370.51020
[9] Drton, M.; Sturmfels, B.; Sullivant, S., Lectures on Algebraic Statistics (2009), Springer · Zbl 1166.13001
[10] Faugère, J.-C., Fgb: a library for computing Gröbner bases, (Fukuda, K.; Hoeven, J.; Joswig, M., Mathematical Software - ICMS 2010. Mathematical Software - ICMS 2010, Lect. Notes Comput. Sci., vol. 6327 (2010), Springer: Springer Berlin/Heidelberg), 84-87 · Zbl 1294.68156
[11] Faugère, J.-C.; Lachartre, S., Parallel Gaussian elimination for Gröbner bases computations in finite fields, (Proceedings of the 4th International Workshop on Parallel and Symbolic Computation (2010), ACM), 89-97
[12] Faugère, J.-C.; Safey El Din, M.; Spaenlehauer, P.-J., Gröbner bases and critical points: the unmixed case, (Proceedings of ISSAC’12 (2012), ACM: ACM New York), 162-169 · Zbl 1308.68171
[13] Giusti, M.; Heintz, J.; Morais, J. E.; Morgenstern, J.; Pardo, L. M., Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra, 124, 1, 101-146 (1998) · Zbl 0944.12004
[14] Giusti, M.; Lecerf, G.; Salvy, B., A Gröbner free alternative for polynomial system solving, J. Complex., 17, 154-211 (2001) · Zbl 1003.12005
[15] Greuet, A.; Safey El Din, M., Probabilistic algorithm for the global optimization of a polynomial over a real algebraic set, SIAM J. Optim., 24, 3, 1313-1343 (2014) · Zbl 1327.90232
[16] Gross, E.; Drton, M.; Petrović, S., Maximum likelihood degree of variance component models, Electron. J. Stat., 6, 993-1016 (2012) · Zbl 1281.62159
[17] Gross, E.; Rodriguez, J. I., Maximum likelihood geometry in the presence of data zeros, (Proceedings of ISSAC’14 (2014), ACM: ACM New York), 232-239 · Zbl 1325.68285
[18] Hauenstein, J.; Rodriguez, J. I.; Sturmfels, B., Maximum likelihood for matrices with rank constraints, J. Algebraic Stat., 5, 18-38 (2014) · Zbl 1345.62043
[19] Hong, H.; Safey El Din, M., Variant quantifier elimination, J. Symb. Comput., 47, 7, 883-901 (2012) · Zbl 1238.14001
[20] Hoşten, S.; Khetan, A.; Sturmfels, B., Solving the likelihood equations, Found. Comput. Math., 5, 4, 389-407 (2005) · Zbl 1097.13035
[21] Hoşten, S.; Sullivant, S., The algebraic complexity of maximum likelihood estimation for bivariate missing data, (Algebraic and Geometric Methods in Statistics (2009), Cambridge University Press), 123-133
[22] Huh, J., The maximum likelihood degree of a very affine variety, Compos. Math., 149, 8, 1245-1266 (2013) · Zbl 1282.14007
[23] Huh, J.; Sturmfels, B., Likelihood geometry, (Combinatorial Algebraic Geometry (2014)), 63-117 · Zbl 1328.14004
[24] Jelonek, Z., Testing sets for properness of polynomial mappings, Math. Ann., 315, 1-35 (1999) · Zbl 0946.14039
[25] Lazard, D.; Rouillier, F., Solving parametric polynomial systems, J. Symb. Comput., 42, 6, 636-667 (2005) · Zbl 1156.14044
[26] Rodriguez, J. I., Maximum likelihood for dual varieties, (Proceedings of the 2014 Symposium on Symbolic-Numeric Computation. Proceedings of the 2014 Symposium on Symbolic-Numeric Computation, SNC ’14 (2014), ACM: ACM New York, NY, USA), 43-49 · Zbl 1345.65002
[27] Rodriguez, J. I.; Tang, X., Data-discriminants of likelihood equations, (Proceedings of ISSAC’15 (2015), ACM), 307-314 · Zbl 1345.65003
[28] Safey El Din, M.; Schost, E., Polar varieties and computation of one point in each connected component of a smooth real algebraic set, (Proceedings of ISSAC’03 (2003), ACM Press), 224-231 · Zbl 1072.68693
[29] Safey El Din, M.; Schost, E., Properness defects of projections and computation of at least one point in each connected component of a real algebraic set, Discrete Comput. Geom., 32, 3, 417-430 (2004) · Zbl 1067.14057
[30] Schost, E., Computing parametric geometric resolutions, Appl. Algebra Eng. Commun. Comput., 13, 5, 349-393 (2003) · Zbl 1058.68123
[31] Uhler, C., Geometry of maximum likelihood estimation in Gaussian graphical models, Ann. Stat., 40, 1, 238-261 (2012) · Zbl 1246.62140
[32] Yang, L., Recent advances on determining the number of real roots of parametric polynomials, J. Symb. Comput., 28, 1, 225-242 (1999) · Zbl 0957.65041
[33] Yang, L.; Hou, X.; Xia, B., A complete algorithm for automated discovering of a class of inequality-type theorems, Sci. China, Ser. F, Inform. Sci., 44, 1, 33-49 (2001) · Zbl 1125.68406
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.