Maximum margin clustering made practical

ABSTRACT

Maximum margin clustering (MMC) is a recent large margin unsupervised learning approach that has often outperformed conventional clustering methods. Computationally, it involves non-convex optimization and has to be relaxed to different semidefinite programs (SDP). However, SDP solvers are computationally very expensive and only small data sets can be handled by MMC so far. To make MMC more practical, we avoid SDP relaxations and propose in this paper an efficient approach that performs alternating optimization directly on the original non-convex problem. A key step to avoid premature convergence is on the use of SVR with the Laplacian loss, instead of SVM with the hinge loss, in the inner optimization subproblem. Experiments on a number of synthetic and real-world data sets demonstrate that the proposed approach is often more accurate, much faster and can handle much larger data sets.

REFERENCES

• 1: James C. Bezdek , Richard J. Hathaway, Convergence of alternating optimization, Neural, Parallel & Scientific Computations, v.11 n.4, p.351-368, December 2003
• 2: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 3: Mario A. T. Figueiredo , Anil K. Jain, Unsupervised Learning of Finite Mixture Models, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.3, p.381-396, March 2002 [doi>10.1109/34.990138 ]
• 4: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 5: Gert R. G. Lanckriet , Nello Cristianini , Peter Bartlett , Laurent El Ghaoui , Michael I. Jordan, Learning the Kernel Matrix with Semidefinite Programming, The Journal of Machine Learning Research, 5, p.27-72, 12/1/2004
• 6: Lobo, M., Vandenberghe, L., Boyd, S., & Lebret, H. (1998). Applications of second-order cone programming. Linear Algebra Applications, 284, 193--228.
• 7: Nesterov, Y., & Nemirovskii, A. (1994). Interior-point polynomial algorithms in convex programming. Philadelphia, PA: Society for Industrial and Applied Mathematics.
• 8: John C. Platt, Fast training of support vector machines using sequential minimal optimization, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 9: Schölkopf, B., & Smola, A. (2002). Learning with kernels. Cambridge, MA: MIT Press.
• 10: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688 ]
• 11: J. A. K. Suykens , J. Vandewalle, Least Squares Support Vector Machine Classifiers, Neural Processing Letters, v.9 n.3, p.293-300, June 1999 [doi>10.1023/A:1018628609742 ]
• 12: Valizadegan, H., & Jin, R. (2007). Generalized maximum margin clustering and unsupervised kernel learning. Advances in Neural Information Processing Systems 19. Cambridge, MA: MIT Press.
• 13: Xu, L., Neufeld, J., Larson, B., & Schuurmans, D. (2005). Maximum margin clustering. Advances in Neural Information Processing Systems 17. Cambridge, MA: MIT Press.
• 14: Xu, L., & Schuurmans, D. (2005). Unsupervised and semi-supervised multi-class support vector machines. Proceedings of The Twentieth National Conference on Artificial Intelligence (pp. 904--910). Pittsburgh, PA, USA.
• 15: Linli Xu , Dana Wilkinson , Finnegan Southey , Dale Schuurmans, Discriminative unsupervised learning of structured predictors, Proceedings of the 23rd international conference on Machine learning, p.1057-1064, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143977]