Learning non-redundant codebooks for classifying complex objects

ABSTRACT

Codebook-based representations are widely employed in the classification of complex objects such as images and documents. Most previous codebook-based methods construct a single codebook via clustering that maps a bag of low-level features into a fixed-length histogram that describes the distribution of these features. This paper describes a simple yet effective framework for learning multiple non-redundant codebooks that produces surprisingly good results. In this framework, each codebook is learned in sequence to extract discriminative information that was not captured by preceding codebooks and their corresponding classifiers. We apply this framework to two application domains: visual object categorization and document classification. Experiments on large classification tasks show substantial improvements in performance compared to a single codebook or codebooks learned in a bagging style.

REFERENCES

• 1: L. Douglas Baker , Andrew Kachites McCallum, Distributional clustering of words for text classification, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.96-103, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290970]
• 2: Ron Bekkerman , Ran El-Yaniv , Naftali Tishby , Yoad Winter, Distributional word clusters vs. words for text categorization, The Journal of Machine Learning Research, 3, 3/1/2003
• 3: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 4: Chechik, G. & Tishby, N. (2002). Extracting relevant structures with side information. Proc. Advances in Neural Information Processing Systems, pp 857--864.
• 5: Csurka, G., Dance, C. R., Fan L., Willamowski, J., & Bray, C. (2004). Visual categorization with bags of keypoints. Euro. Conf. Comput. Vision Workshop, pp 59--74.
• 6: Ying Cui , Xiaoli Z. Fern , Jennifer G. Dy, Non-redundant Multi-view Clustering via Orthogonalization, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.133-142, October 28-31, 2007 [doi>10.1109/ICDM.2007.94]
• 7: Deng, H., Zhang W., Mortensen, E., Dietterich, T. & Shapiro, L. (2007). Principal curvature-based region detector for object recognition. Proc. IEEE Conf. Comput. Vision Pattern Recognition, pp 1--8.
• 8: Inderjit S. Dhillon , Subramanyam Mallela , Rahul Kumar, A divisive information theoretic feature clustering algorithm for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 9: Thomas G. Dietterich , Richard H. Lathrop , Tomás Lozano-Pérez, Solving the multiple instance problem with axis-parallel rectangles, Artificial Intelligence, v.89 n.1-2, p.31-71, Jan. 1997 [doi>10.1016/S0004-3702(96)00034-3]
• 10: Thomas G. Dietterich, Approximate statistical tests for comparing supervised classification learning algorithms, Neural Computation, v.10 n.7, p.1895-1923, Oct. 1998 [doi>10.1162/089976698300017197]
• 11: Dorko, G. & Schmid, C. (2005). Object class recognition using discriminative local features. Technical Report RR-5497, INRIA-Rhone-Alpes.
• 12: Freund, Y. & Schapire, R. (1996). Experiments with a new boosting algorithm. Proc. Int'l Conf. Machine Learning, pp 148--156.
• 13: Prateek Jain , Raghu Meka , Inderjit S. Dhillon, Simultaneous Unsupervised Learning of Disparate Clusterings, Statistical Analysis and Data Mining, v.1 n.3, p.195-210, November 2008 [doi>10.1002/sam.v1:3]
• 14: Frederic Jurie , Bill Triggs, Creating Efficient Codebooks for Visual Recognition, Proceedings of the Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, p.604-610, October 17-20, 2005 [doi>10.1109/ICCV.2005.66]
• 15: Kadir, T., Zisserman A., & Brady, M. (2004). An affine invariant salient region detector. Proc. Euro. Conf. Comput. Vision, pp 228--241.
• 16: Kalal, Z., Matas, J., & Mikolajczyk K. (2008). Weighted sampling for large-scale boosting. Proc. Brit. Machine Vision Conf.
• 17: Natalia Larios , Hongli Deng , Wei Zhang , Matt Sarpola , Jenny Yuen , Robert Paasch , Andrew Moldenke , David A. Lytle , Salvador Ruiz Correa , Eric N. Mortensen , Linda G. Shapiro , Thomas G. Dietterich, Automated insect identification through concatenated histograms of local appearance features: feature vector generation and region detection for deformable objects, Machine Vision and Applications, v.19 n.2, p.105-123, January 2008 [doi>10.1007/s00138-007-0086-y]
• 18: David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, v.60 n.2, p.91-110, November 2004 [doi>10.1023/B:VISI.0000029664.99615.94]
• 19: McCallum, A. K. (2002). MALLET: A machine learning for language toolkit. http://mallet.cs.umass.edu.
• 20: Krystian Mikolajczyk , Cordelia Schmid, Scale & Affine Invariant Interest Point Detectors, International Journal of Computer Vision, v.60 n.1, p.63-86, October 2004 [doi>10.1023/B:VISI.0000027790.02288.f2]
• 21: K. Mikolajczyk , T. Tuytelaars , C. Schmid , A. Zisserman , J. Matas , F. Schaffalitzky , T. Kadir , L. Van Gool, A Comparison of Affine Region Detectors, International Journal of Computer Vision, v.65 n.1-2, p.43-72, November 2005 [doi>10.1007/s11263-005-3848-x]
• 22: Moosmann, F., Triggs, B. & Jurie, F. (2007). Fast discriminative visual codebooks using randomized clustering forests. Proc. Advances in Neural Information Processing Systems, pp 985--992.
• 23: Andreas Opelt , Axel Pinz , Michael Fussenegger , Peter Auer, Generic Object Recognition with Boosting, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.3, p.416-431, March 2006 [doi>10.1109/TPAMI.2006.54]
• 24: Perronnin, F., Dance, C., Csurka, G. & Bressan, M. (2006). Adapted vocabularies for generic visual categorization. Proc. Euro. Conf. Comput. Vision, pp 464--475.
• 25: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 26: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• 27: Slonim, N. & Tishby, N. (2001). The power of word clusters for text classification. In Proc. Euro. Colloq. Information Retrieval Research.
• 28: Noam Slonim , Nir Friedman , Naftali Tishby, Unsupervised document classification using sequential information maximization, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564401]
• 29: Viola, P. & Jones, M. (2001). Rapid object detection using a boosted cascade of simple features. Proc. IEEE Conf. Comput. Vision Pattern Recognition, pp 511--518.
• 30: J. Winn , A. Criminisi , T. Minka, Object Categorization by Learned Universal Visual Dictionary, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.1800-1807, October 17-20, 2005 [doi>10.1109/ICCV.2005.171]
• 31: Yang, L., Jin, R., Sukthankar R., & Jurie, F. (2008). Unifying discriminative visual codebook generation with classifier training for object category recognition. Proc. IEEE Conf. Comput. Vision Pattern Recognition, pp 1--8.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Experimental design

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection; 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, Experimentation, Performance