Multi-classification by categorical features via clustering

ABSTRACT

We derive a generalization bound for multi-classification schemes based on grid clustering in categorical parameter product spaces. Grid clustering partitions the parameter space in the form of a Cartesian product of partitions for each of the parameters. The derived bound provides a means to evaluate clustering solutions in terms of the generalization power of a built-on classifier. For classification based on a single feature the bound serves to find a globally optimal classification rule. Comparison of the generalization power of individual features can then be used for feature ranking. Our experiments show that in this role the bound is much more precise than mutual information or normalized correlation indices.

REFERENCES

• 1: Asuncion, A., & Newman, D. (2007). UCI machine learning repository. http://www.ics.uci.edu/~mlearn/MLRepository.html.
• 2: Blanchard, G., & Fleuret, F. (2007). Occam's hammer. COLT.
• 3: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 4: John Langford, Tutorial on Practical Prediction Theory for Classification, The Journal of Machine Learning Research, 6, p.273-306, 12/1/2005
• 5: Maurer, A. (2004). A note on the PAC-Bayesian theorem. www.arxiv.org.
• 6: David A. McAllester, Some PAC-Bayesian Theorems, Machine Learning, v.37 n.3, p.355-363, Dec. 1999 [doi>10.1023/A:1007618624809]
• 7: Liam Paninski, Estimation of entropy and mutual information, Neural Computation, v.15 n.6, p.1191-1253, June 2003 [doi>10.1162/089976603321780272]
• 8: Sabato, S., & Shalev-Shwartz, S. (2007). Prediction by categorical features: Generalization properties and application to feature ranking. COLT.
• 9: Seldin, Y., Slonim, N., & Tishby, N. (2007). Information bottleneck for non co-occurrence data. NIPS.
• 10: Shamir, O., Sabato, S., & Tishby, N. (2008). Learning and generalization with the information bottleneck method. Preprint.
• 11: Nathan Srebro , Tommi S. Jaakkola, Learning with matrix factorizations, Massachusetts Institute of Technology, Cambridge, MA, 2004

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection
      I.5.3 Clustering
          Subjects: Algorithms
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory