Trust region Newton methods for large-scale logistic regression

ABSTRACT

Large-scale logistic regression arises in many applications such as document classification and natural language processing. In this paper, we apply a trust region Newton method to maximize the log-likelihood of the logistic regression model. The proposed method uses only approximate Newton steps in the beginning, but achieves fast convergence in the end. Experiments show that it is faster than the commonly used quasi Newton approach for logistic regression. We also compare it with linear SVM implementations.

REFERENCES

• 1: Bernhard E. Boser , Isabelle M. Guyon , Vladimir N. Vapnik, A training algorithm for optimal margin classifiers, Proceedings of the fifth annual workshop on Computational learning theory, p.144-152, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130401]
• 2: Thorsten Joachims, Training linear SVMs in linear time, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150429]
• 3: S. Sathiya Keerthi , Dennis DeCoste, A Modified Finite Newton Method for Fast Solution of Large Scale Linear SVMs, The Journal of Machine Learning Research, 6, p.341-361, 12/1/2005
• 4: Komarek, P., & Moore, A. W. (2005). Making logistic regression a core data mining tool (Technical Report). Carnegie Mellon University.
• 5: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 6: Chih-Jen Lin , Jorge J. Moré, Newton's Method for Large Bound-Constrained Optimization Problems, SIAM Journal on Optimization, v.9 n.4, p.1100-1127, 1999 [doi>10.1137/S1052623498345075]
• 7: D. C. Liu , J. Nocedal, On the limited memory BFGS method for large scale optimization, Mathematical Programming: Series A and B, v.45 n.3, p.503-528, Dec. 1989 [doi>10.1007/BF01589116]
• 8: Robert Malouf, A comparison of algorithms for maximum entropy parameter estimation, proceeding of the 6th conference on Natural language learning, p.1-7, August 31, 2002 [doi>10.3115/1118853.1118871]
• 9: Mangasarian, O. L. (2002). A finite Newton method for classification. Optimization Methods and Software, 17, 913--929.
• 10: Stephen G. Nash, A survey of truncated-Newton methods, Journal of Computational and Applied Mathematics, v.124 n.1-2, p.45-59, Dec. 2000 [doi>10.1016/S0377-0427(00)00426-X]
• 11: Nocedal, J., & Nash, S. G. (1991). A numerical study of the limited memory BFGS method and the truncated-newton method for large scale optimization. SIAM Journal on Optimization, 1, 358--372.
• 12: Stephen Della Pietra , Vincent Della Pietra , John Lafferty, Inducing Features of Random Fields, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.4, p.380-393, April 1997 [doi>10.1109/34.588021]
• 13: Steihaug, T. (1983). The conjugate gradient method and trust regions in large scale optimization. SIAM Journal on Numerical Analysis, 20, 626--637.
• 14: Sutton, C., & McCallum, A. (2006). An introduction to conditional random fields for relational learning. In L. Getoor and B. Taskar (Eds.), Introduction to statistical relational learning. MIT Press.