Multi-labelled classification using maximum entropy method

ABSTRACT

Many classification problems require classifiers to assign each single document into more than one category, which is called multi-labelled classification. The categories in such problems usually are neither conditionally independent from each other nor mutually exclusive, therefore it is not trivial to directly employ state-of-the-art classification algorithms without losing information of relation among categories. In this paper, we explore correlations among categories with maximum entropy method and derive a classification algorithm for multi-labelled documents. Our experiments show that this method significantly outperforms the combination of single label approach.

REFERENCES

• 1: Benson, S. J., McInnes, L. C., Moré, J., & Sarich, J. (2004). TAO user manual (revision 1.7) (Technical Report ANL/MCS-TM-242). Mathematics and Computer Science Division, Argonne National Laboratory. http://www.mcs.anl.gov/tao.
• 2: Lijuan Cai , Thomas Hofmann, Hierarchical document categorization with support vector machines, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031186]
• 3: Chen, S. F., & Rosenfeld, R. (1999). A Gaussian prior for smoothing maximum entropy models (Technical Report CMU-CS-99-108). School of Computer Science Carnegie Mellon University.
• 4: Amanda Clare , Ross D. King, Knowledge Discovery in Multi-label Phenotype Data, Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery, p.42-53, September 03-05, 2001
• 5: Comite, F. D., Gilleron, R., & Tommasi, M. (2001). Learning multi-label alternating decision trees and applications. Proceedings of CAP'01 (pp. 195--210).
• 6: Koby Crammer , Yoram Singer, A new family of online algorithms for category ranking, 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.564404]
• 7: Stephen Della Pietra , Vincent Della Pietra , John Lafferty, Inducing Features of Random Fields, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.4, p.380-393, April 1997 [doi>10.1109/34.588021]
• 8: Elisseeff, A., & Weston, J. (2002). A kernel method for multi-labelled classification. Advances in Neural Information Processing Systems 14 (pp. 681--687). Cambridge, MA: MIT Press.
• 9: Sheng Gao , Wen Wu , Chin-Hui Lee , Tat-Seng Chua, A MFoM learning approach to robust multiclass multi-label text categorization, Proceedings of the twenty-first international conference on Machine learning, p.42, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015361]
• 10: Godbole, S., & Sarawagi, S. (2004). Discriminative methods for multi-labeled classification. PAKDD.
• 11: Har-Peled, S., Roth, D., & Zimak, D. Constraint classification for multiclass classification and ranking. In S. T. S. Becker and K. Obermayer (Eds.), Advances in neural information processing systems 15. MIT Press.
• 12: Jaynes, E. T. (1957). Information theory and statistical mechanics. Physical Review, 106, 620--630.
• 13: Robert Malouf, A comparison of algorithms for maximum entropy parameter estimation, proceeding of the 6th conference on Natural language learning, p.1-7, August 31, 2002 [doi>10.3115/1118853.1118871]
• 14: McCallum, A. (1999). Multi-label text classification with a mixture model trained by EM. AAAI'99 Workshop on Text Learning.
• 15: Nigam, K., Lafferty, J., & McCallum, A. (1999). Using maximum entropy for text classification. IJCAI-99 Workshop on Machine Learning for Information Filtering (pp. 61--67).
• 16: Robert E. Schapire , Yoram Singer, BoosTexter: A Boosting-based Systemfor Text Categorization, Machine Learning, v.39 n.2-3, p.135-168, May-June 2000 [doi>10.1023/A:1007649029923]
• 17: Ueda, N., & Saito, K. Parametric mixture models for multi-labeled text. Advances in Neural Information Processing Systems 15. MIT Press.
• 18: Wilcoxon, F. (1945). Individual comparisons by ranking methods. Biometrics, 1, 80--93.
• 19: Yiming Yang , Xin Liu, A re-examination of text categorization methods, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.42-49, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312647]
• 20: Tong Zhang , Frank J. Oles, Text Categorization Based on Regularized Linear Classification Methods, Information Retrieval, v.4 n.1, p.5-31, April 2001 [doi>10.1023/A:1011441423217]
• 21: Zhu, J., & Hastie, T. (2003). Classification of gene microarrays by penalized logistic regression. Biostatistics.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation

Keywords:
maximum entropy method, multi-labelled classification