Robust generalized eigenvalue classifier with ellipsoidal uncertainty. (English) Zbl 1296.90084
Summary: Uncertainty is a concept associated with data acquisition and analysis, usually appearing in the form of noise or measure error, often due to some technological constraint. In supervised learning, uncertainty affects classification accuracy and yields low quality solutions. For this reason, it is essential to develop machine learning algorithms able to handle efficiently data with imprecision. In this paper we study this problem from a robust optimization perspective. We consider a supervised learning algorithm based on generalized eigenvalues and we provide a robust counterpart formulation and solution in case of ellipsoidal uncertainty sets. We demonstrate the performance of the proposed robust scheme on artificial and benchmark datasets from University of California Irvine (UCI) machine learning repository and we compare results against a robust implementation of Support Vector Machines.
References:
| [1] | Aeberhard, S., Coomans, D., & De Vel, O. (1992a). Comparison of classifiers in high dimensional settings. Tech. Rep. Dept. Math. Statist., James Cook Univ. North Queensland, Australia |
| [2] | Aeberhard, S., Coomans, D., & De Vel, O. (1992b). The classification performance of RDA, Cambridge. Tech. Rep. (pp. 92–01). Dept. of Computer Science/Dept. of Mathematics and Statistics, James Cook University of North Queensland |
| [3] | Andersen, M. S., Dahl, J., Liu, Z., & Vandenberghe, L. (2011). Interior-point methods for large-scale cone programming. Optimization for machine learning. Cambridge: MIT Press. |
| [4] | Ben-Tal, A., El Ghaoui, L., & Nemirovski, A. S. (2009). Robust optimization. Princeton: Princeton University Press. · Zbl 1221.90001 |
| [5] | Ben-Tal, A., & Nemirovski, A. (1998). Robust convex optimization. Mathematics of Operations Research, 23(4), 769–805. · Zbl 0977.90052 · doi:10.1287/moor.23.4.769 |
| [6] | Ben-Tal, A., & Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters, 25(1), 1–14. · Zbl 0941.90053 · doi:10.1016/S0167-6377(99)00016-4 |
| [7] | Ben-Tal, A., & Nemirovski, A. (2000). Robust solutions of linear programming problems contaminated with uncertain data. Mathematical Programming, 88(3), 411–424. · Zbl 0964.90025 · doi:10.1007/PL00011380 |
| [8] | Ben-Tal, A., & Nemirovski, A. S. (2002). Robust optimization–methodology and applications. Mathematical Programming, 92(3), 453–480. · Zbl 1007.90047 · doi:10.1007/s101070100286 |
| [9] | Bertsimas, D., Brown, D. B., & Caramanis, C. (2011). Theory and applications of robust optimization. SIAM Review 53(3), 464–501. · Zbl 1233.90259 · doi:10.1137/080734510 |
| [10] | Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53. · Zbl 1165.90565 · doi:10.1287/opre.1030.0065 |
| [11] | Caramanis, C., Mannor, S., & Xu, H. (2011). Robust optimization in machine learning. In S. Sra, S. Nowozin, & S. J. Wright (Eds.), Optimization for machine learning (pp. 369–402). Cambridge: MIT Press. |
| [12] | Cifarelli, C., Guarracino, M. R., Seref, O., Cuciniello, S., & Pardalos, P. M. (2007). Incremental classification with generalized eigenvalues. Journal of Classification, 24(2), 205–219. · Zbl 1234.62098 · doi:10.1007/s00357-007-0012-z |
| [13] | Cortes, C., & Vapnik, V. N. (1995). Support-vector networks. Machine Learning, 20(3), 273–297. · Zbl 0831.68098 |
| [14] | D’Aspremont, A., Ghaoui, L., Jordan, M., & Lanckriet, G. (2004). A direct formulation for sparse PCA using semidefinite programming. SIAM Review, 49(3), 434–448. · Zbl 1128.90050 · doi:10.1137/050645506 |
| [15] | El Ghaoui, L., & Lebret, H. (1997). Robust solutions to least-squares problems with uncertain data. SIAM Journal on Matrix Analysis and Applications, 18, 1035–1064. · Zbl 0891.65039 · doi:10.1137/S0895479896298130 |
| [16] | El Ghaoui, L., Oustry, F., Lebret, H., et al. (1998). Robust solutions to uncertain semidefinite programs. SIAM Journal on Optimization, 9, 33–52. · Zbl 0960.93007 · doi:10.1137/S1052623496305717 |
| [17] | Evgeniou, T., Pontil, M., & Poggio, T. (2000). Regularization networks and support vector machines. Advances in Computational Mathematics, 13(1), 1–50. · Zbl 0939.68098 · doi:10.1023/A:1018946025316 |
| [18] | Fisher, R., et al. (1936). The use of multiple measurements in taxonomic problems. Annals of Eugenics, 7, 179–188. · doi:10.1111/j.1469-1809.1936.tb02137.x |
| [19] | Frank, A., & Asuncion, A. (2010). UCI machine learning repository. http://archive.ics.uci.edu/ml . |
| [20] | Guarracino, M. R., Cifarelli, C., Seref, O., & Pardalos, P. M. (2007). A classification method based on generalized eigenvalue problems. Optimization Methods & Software, 22(1), 73–81. · Zbl 1125.15013 · doi:10.1080/10556780600883874 |
| [21] | Huber, P., & Ronchetti, E. (1981). MyiLibrary: robust statistics (Vol. 1). Hoboken: Wiley Online Library. |
| [22] | Hubert, M., Rousseeuw, P., & Vanden Branden, K. (2005). ROBPCA: a new approach to robust principal component analysis. Technometrics, 47(1), 64–79. · doi:10.1198/004017004000000563 |
| [23] | Irpino, A., Guarracino, M. R., & Verde, R. (2010). Multiclass generalized eigenvalue proximal support vector machines. In 4th IEEE conference on complex, intelligent and software intensive systems (CISIS 2010). (pp. 25–32). Los Alamitos: IEEE Computer Society. |
| [24] | Kim, S. J., & Boyd, S. (2008). A minimax theorem with applications to machine learning, signal processing, and finance. SIAM Journal on Optimization, 19(3), 1344–1367. · Zbl 1175.90412 · doi:10.1137/060677586 |
| [25] | Kim, S. J., Magnani, A., & Boyd, S. (2006). Robust fisher discriminant analysis. Advances in Neural Information Processing Systems, 18, 659. |
| [26] | Mangasarian, O. L., & Wild, E. W. (2006). Multisurface proximal support vector machine classification via generalized eigenvalues. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(1), 69–74. · doi:10.1109/TPAMI.2006.17 |
| [27] | Musicant, D. R. (1998). NDC: normally distributed clustered datasets. http://www.cs.wisc.edu/dmi/svm/ndc/ . |
| [28] | Pothin, J., & Richard, C. (2006). Incorporating prior information into support vector machines in the form of ellipsoidal knowledge sets. Citeseer. |
| [29] | Shahbazpanahi, S., Gershman, A., Luo, Z., & Wong, K. (2003). Robust adaptive beamforming using worst-case SINR optimization: a new diagonal loading-type solution for general-rank signal models. In 2003 IEEE international conference on acoustics, speech, and signal processing. Proceedings (ICASSP’03) (Vol. 5). New York: IEEE Press. |
| [30] | Shivaswamy, P., Bhattacharyya, C., & Smola, A. (2006). Second order cone programming approaches for handling missing and uncertain data. The Journal of Machine Learning Research, 7, 1283–1314. · Zbl 1222.68305 |
| [31] | Smith, J. W., Everhart, J. E., Dickson, W. C., Knowler, W. C., & Johannes, R. S. (1988). Using the adap learning algorithm to forecast the onset of diabetes mellitus. Johns Hopkins APL Technical Digest, 10, 262–266. |
| [32] | Smola, A. J., Schölkopf, B., & Müller, K. R. (1998). The connection between regularization operators and support vector kernels. Neural Networks, 11(4), 637–649. · doi:10.1016/S0893-6080(98)00032-X |
| [33] | Song, Q., Hu, W., & Xie, W. (2002). Robust support vector machine with bullet hole image classification. IEEE Transactions on Systems, Man, and Cybernetics, Part C, 32(4), 440–448. · doi:10.1109/TSMCC.2002.807277 |
| [34] | Trafalis, T. B., & Gilbert, R. C. (2006). Robust classification and regression using support vector machines. European Journal of Operational Research, 173(3), 893–909. · Zbl 1132.62336 · doi:10.1016/j.ejor.2005.07.024 |
| [35] | Trafalis, T. B., & Gilbert, R. C. (2007). Robust support vector machines for classification and computational issues. Optimization Methods & Software, 22(1), 187–198. · Zbl 1116.62070 · doi:10.1080/10556780600883791 |
| [36] | Vandenberghe, L. (2010). The CVXOPT linear and quadratic cone program solvers. |
| [37] | Vapnik, V. N. (1999). The nature of statistical learning theory. Information science and statistics. Berlin: Springer. · Zbl 0928.68093 |
| [38] | Verdú, S., & Poor, H. (2002). On minimax robustness: a general approach and applications. IEEE Transactions on Information Theory, 30(2), 328–340. · Zbl 0544.93064 · doi:10.1109/TIT.1984.1056876 |
| [39] | Xanthopoulos, P., Pardalos, P. M., & Trafalis, T. B. (2012). Robust data mining. New York: Springer. · Zbl 1260.90003 |
| [40] | Xu, H., Caramanis, C., & Mannor, S. (2009). Robustness and regularization of support vector machines. Journal of Machine Learning Research, 10, 1485–1510. · Zbl 1235.68209 |
| [41] | Xu, H., Caramanis, C., & Mannor, S. (2010). Robust regression and lasso. IEEE Transactions on Information Theory, 56(7), 3561–3574. · Zbl 1366.62147 · doi:10.1109/TIT.2010.2048503 |
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.
