Discriminative k-metrics

ABSTRACT

The k q-flats algorithm is a generalization of the popular k-means algorithm where q dimensional best fit affine sets replace centroids as the cluster prototypes. In this work, a modification of the k q-flats framework for pattern classification is introduced. The basic idea is to replace the original reconstruction only energy, which is optimized to obtain the k affine spaces, by a new energy that incorporates discriminative terms. This way, the actual classification task is introduced as part of the design and optimization. The presentation of the proposed framework is complemented with experimental results, showing that the method is computationally very efficient and gives excellent results on standard supervised learning benchmarks.

REFERENCES

• 1: Aharon, M., Elad, M., & Bruckstein, A. (2006). KSVD: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Transactions on Signal Processing, 54, 4311--4322.
• 2: Bradley, P. S., & Mangasarian, O. L. (1998). k-plane clustering (Technical Report MP-TR-1998-08). Department of Computer Science, University of Wisconsin.
• 3: Raffaele Cappelli , Dario Maio , Davide Maltoni, Multispace KL for Pattern Representation and Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.9, p.977-996, September 2001 [doi>10.1109/34.955111]
• 4: Chapelle, O., Schölkopf, B., & Zien, A. (Eds.). (2006). Semi-supervised learning. Cambridge, MA: MIT Press.
• 5: Jason V. Davis , Brian Kulis , Prateek Jain , Suvrit Sra , Inderjit S. Dhillon, Information-theoretic metric learning, Proceedings of the 24th international conference on Machine learning, p.209-216, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273523]
• 6: Kambhatla, N., & Leen, T. K. (1993). Fast non-linear dimension reduction. Advances in Neural Information Processing Systems 6 (pp. 152--159).
• 7: Hugo Larochelle , Yoshua Bengio, Classification using discriminative restricted Boltzmann machines, Proceedings of the 25th international conference on Machine learning, p.536-543, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390224]
• 8: Mairal, J., Bach, F., Ponce, J., Sapiro, G., & Zisserman, A. (2008). Supervised dictionary learning. Advances in Neural Information Processing Systems (pp. 1033--1040). Vancouver, Canada.
• 9: Caroline Pantofaru , Gyuri Dorko , Cordelia Schmid , Martial Hebert, Combining Regions and Patches for Object Class Localization, Proceedings of the 2006 Conference on Computer Vision and Pattern Recognition Workshop, p.23, June 17-22, 2006 [doi>10.1109/CVPRW.2006.57]
• 10: Tropp, J. (2004). Topics in sparse approximation. Doctoral dissertation, Computational and Applied Mathematics, The University of Texas at Austin.
• 11: P. Tseng, Nearest q-flat to mpoints, Journal of Optimization Theory and Applications, v.105 n.1, p.249-252, April 2000 [doi>10.1023/A:1004678431677]
• 12: Tuytelaars, T., & Schmid, C. (2007). Vector quantizing feature space with a regular lattice. Proceedings of IEEE International Conference on Computer Vision (pp. 1--8).
• 13: Wakin, M. (2006). The geometry of low-dimensional signal models. Doctoral dissertation, Rice university.
• 14: Weinberger, K., Blitzer, J., & Saul, L. (2006). Distance metric learning for large margin nearest neighbor classification. Advances in Neural Information Processing Systems 18 (pp. 1473--1480). Cambridge, MA: MIT Press.
• 15: Xing, E. P., Ng, A. Y., Jordan, M. I., & Russell, S. (2003). Distance metric learning with application to clustering with side-information. Advances in Neural Information Processing Systems 15 (pp. 505--512). Cambridge, MA: MIT Press.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis; Classifier design and evaluation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory