Global Optimization Methods for Extended Fisher Discriminant Analysis

Satoru Iwata, Yuji Nakatsukasa, Akiko Takeda
Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, PMLR 33:411-419, 2014.

Abstract

The Fisher discriminant analysis (FDA) is a common technique for binary classification. A parametrized extension, which we call the extended FDA, has been introduced from the viewpoint of robust optimization. In this work, we first give a new probabilistic interpretation of the extended FDA. We then develop algorithms for solving an optimization problem that arises from the extended FDA: computing the distance between a point and the surface of an ellipsoid. We solve this problem via the KKT points, which we show are obtained by solving a generalized eigenvalue problem. We speed up the algorithm by taking advantage of the matrix structure and proving that a globally optimal solution is a KKT point with the smallest Lagrange multiplier, which can be computed efficiently as the leftmost eigenvalue. Numerical experiments illustrate the efficiency and effectiveness of the extended FDA model combined with our algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v33-iwata14, title = {{Global Optimization Methods for Extended Fisher Discriminant Analysis}}, author = {Iwata, Satoru and Nakatsukasa, Yuji and Takeda, Akiko}, booktitle = {Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics}, pages = {411--419}, year = {2014}, editor = {Kaski, Samuel and Corander, Jukka}, volume = {33}, series = {Proceedings of Machine Learning Research}, address = {Reykjavik, Iceland}, month = {22--25 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v33/iwata14.pdf}, url = {https://proceedings.mlr.press/v33/iwata14.html}, abstract = {The Fisher discriminant analysis (FDA) is a common technique for binary classification. A parametrized extension, which we call the extended FDA, has been introduced from the viewpoint of robust optimization. In this work, we first give a new probabilistic interpretation of the extended FDA. We then develop algorithms for solving an optimization problem that arises from the extended FDA: computing the distance between a point and the surface of an ellipsoid. We solve this problem via the KKT points, which we show are obtained by solving a generalized eigenvalue problem. We speed up the algorithm by taking advantage of the matrix structure and proving that a globally optimal solution is a KKT point with the smallest Lagrange multiplier, which can be computed efficiently as the leftmost eigenvalue. Numerical experiments illustrate the efficiency and effectiveness of the extended FDA model combined with our algorithm.} }
Endnote
%0 Conference Paper %T Global Optimization Methods for Extended Fisher Discriminant Analysis %A Satoru Iwata %A Yuji Nakatsukasa %A Akiko Takeda %B Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2014 %E Samuel Kaski %E Jukka Corander %F pmlr-v33-iwata14 %I PMLR %P 411--419 %U https://proceedings.mlr.press/v33/iwata14.html %V 33 %X The Fisher discriminant analysis (FDA) is a common technique for binary classification. A parametrized extension, which we call the extended FDA, has been introduced from the viewpoint of robust optimization. In this work, we first give a new probabilistic interpretation of the extended FDA. We then develop algorithms for solving an optimization problem that arises from the extended FDA: computing the distance between a point and the surface of an ellipsoid. We solve this problem via the KKT points, which we show are obtained by solving a generalized eigenvalue problem. We speed up the algorithm by taking advantage of the matrix structure and proving that a globally optimal solution is a KKT point with the smallest Lagrange multiplier, which can be computed efficiently as the leftmost eigenvalue. Numerical experiments illustrate the efficiency and effectiveness of the extended FDA model combined with our algorithm.
RIS
TY - CPAPER TI - Global Optimization Methods for Extended Fisher Discriminant Analysis AU - Satoru Iwata AU - Yuji Nakatsukasa AU - Akiko Takeda BT - Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics DA - 2014/04/02 ED - Samuel Kaski ED - Jukka Corander ID - pmlr-v33-iwata14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 33 SP - 411 EP - 419 L1 - http://proceedings.mlr.press/v33/iwata14.pdf UR - https://proceedings.mlr.press/v33/iwata14.html AB - The Fisher discriminant analysis (FDA) is a common technique for binary classification. A parametrized extension, which we call the extended FDA, has been introduced from the viewpoint of robust optimization. In this work, we first give a new probabilistic interpretation of the extended FDA. We then develop algorithms for solving an optimization problem that arises from the extended FDA: computing the distance between a point and the surface of an ellipsoid. We solve this problem via the KKT points, which we show are obtained by solving a generalized eigenvalue problem. We speed up the algorithm by taking advantage of the matrix structure and proving that a globally optimal solution is a KKT point with the smallest Lagrange multiplier, which can be computed efficiently as the leftmost eigenvalue. Numerical experiments illustrate the efficiency and effectiveness of the extended FDA model combined with our algorithm. ER -
APA
Iwata, S., Nakatsukasa, Y. & Takeda, A.. (2014). Global Optimization Methods for Extended Fisher Discriminant Analysis. Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 33:411-419 Available from https://proceedings.mlr.press/v33/iwata14.html.

Related Material