Feature subset selection for the multinomial logit model via mixed-integer optimization

Shunsuke Kamiya, Ryuhei Miyashiro, Yuichi Takano
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:1254-1263, 2019.

Abstract

This paper is concerned with a feature subset selection problem for the multinomial logit (MNL) model. There are several convex approximation algorithms for this problem, but to date the only exact algorithms are those for the binomial logit model. In this paper, we propose an exact algorithm to solve the problem for the MNL model. Our algorithm is based on a mixed-integer optimization approach with an outer approximation method. We prove the convergence properties of the algorithm for more general models including generalized linear models for multiclass classification. We also propose approximation of loss functions to accelerate the algorithm computationally. Numerical experiments demonstrate that our exact and approximation algorithms achieve better generalization performance than does an L1-regularization method.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-kamiya19a, title = {Feature subset selection for the multinomial logit model via mixed-integer optimization}, author = {Kamiya, Shunsuke and Miyashiro, Ryuhei and Takano, Yuichi}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {1254--1263}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/kamiya19a/kamiya19a.pdf}, url = {https://proceedings.mlr.press/v89/kamiya19a.html}, abstract = {This paper is concerned with a feature subset selection problem for the multinomial logit (MNL) model. There are several convex approximation algorithms for this problem, but to date the only exact algorithms are those for the binomial logit model. In this paper, we propose an exact algorithm to solve the problem for the MNL model. Our algorithm is based on a mixed-integer optimization approach with an outer approximation method. We prove the convergence properties of the algorithm for more general models including generalized linear models for multiclass classification. We also propose approximation of loss functions to accelerate the algorithm computationally. Numerical experiments demonstrate that our exact and approximation algorithms achieve better generalization performance than does an L1-regularization method.} }
Endnote
%0 Conference Paper %T Feature subset selection for the multinomial logit model via mixed-integer optimization %A Shunsuke Kamiya %A Ryuhei Miyashiro %A Yuichi Takano %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-kamiya19a %I PMLR %P 1254--1263 %U https://proceedings.mlr.press/v89/kamiya19a.html %V 89 %X This paper is concerned with a feature subset selection problem for the multinomial logit (MNL) model. There are several convex approximation algorithms for this problem, but to date the only exact algorithms are those for the binomial logit model. In this paper, we propose an exact algorithm to solve the problem for the MNL model. Our algorithm is based on a mixed-integer optimization approach with an outer approximation method. We prove the convergence properties of the algorithm for more general models including generalized linear models for multiclass classification. We also propose approximation of loss functions to accelerate the algorithm computationally. Numerical experiments demonstrate that our exact and approximation algorithms achieve better generalization performance than does an L1-regularization method.
APA
Kamiya, S., Miyashiro, R. & Takano, Y.. (2019). Feature subset selection for the multinomial logit model via mixed-integer optimization. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:1254-1263 Available from https://proceedings.mlr.press/v89/kamiya19a.html.

Related Material