An evidential approach in ensembles

ABSTRACT

In this paper, we describe an approach to modeling the general process of combining decisions involved in ensembles of classifiers as an evidential reasoning process. This work proposes a novel structure, theoretical properties and manipulation mechanisms for representing classifier decisions as pieces of evidence. The advantage of the representation formalism is that it not only facilitates the distinguishing of trivial focal elements from important ones, resulting in the improvement of the ensemble performance, but it also effectively reduces the computation-time from exponential (as required in the conventional process of combining multiple pieces of evidence) to linear. We have conducted a comparative analysis on the effectiveness of the proposed evidence representation formalism in the text categorization domain. By comparing this method with majority voting and the previous results, we also demonstrate the advantage of this novel approach in combining classifiers.

REFERENCES

• 1: Melville P, and Mooney R. J. 2003. Constructing Diverse Classifier Ensembles using Artificial Training Examples. In Proc of IJCAI-2003, pages 505--510.
• 2: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350 ]
• 3: Freund Y. and Schapire, R. 1996. Experiments with a new boosting algorithm. In Proc of ICML '06, pages 148--156.
• 4: Thomas G. Dietterich, Ensemble Methods in Machine Learning, Proceedings of the First International Workshop on Multiple Classifier Systems, p.1-15, June 21-23, 2000
• 5: Christopher J. Merz, Using Correspondence Analysis to Combine Classifiers, Machine Learning, v.36 n.1-2, p.33-58, July-August 1999
• 6: Kuncheva L. 2001. Combining classifiers: Soft Computing Solutions. In Pal S. K. and Pal A. (Eds), Pattern Recognition: From Classical to Modern Approaches, p 427--451.
• 7: Xu L., Krzyzak A. and Suen C. Y. 1992. Several Methods for Combining Multiple Classifiers and Their Applications in Handwritten Character Recognition. IEEE Trans. on System, Man and Cybernetics, 22 (3): 418--435.
• 8: Lam L. and Suen C. Y. 1997. Application of majority voting to pattern recognition: An analysis of its behavior and performance. IEEE Trans on Systems, Man, and Cybernetics, 27(5): 553--568.
• 9: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 10: Yiming Yang , Tom Ault , Thomas Pierce, Combining Multiple Learning Strategies for Effective Cross Validation, Proceedings of the Seventeenth International Conference on Machine Learning, p.1167-1174, June 29-July 02, 2000
• 11: Tumer K. and Ghosh J. Robust. 2002. Combining of Disparate Classifiers through Order Statistics. Pattern Analysis & Applications. 6 (1): 41--46.
• 12: Denoeux T., 2000. A neural network classifier based on Dempster-Shafer theory. IEEE trans on Systems, Man and Cybernetics A, 30(2), page 131--150.
• 13: Bi, Y., Bell, D, Guan, J. W. (2004). Combining Evidence from Classifiers in Text Categorization. In Proc of KES'04, p 521--528.
• 14: Barnett, J A. 1981. Computational methods for a mathematical theory of evidence. In Proc of IJCAI'81, page 868--875.
• 15: Shafer, G. 1976. A Mathematical Theory of Evidence, Princeton University Press, Princeton, New Jersey.
• 16: Bi, Y. Combining Multiple Classifiers for Text Categorization using the Dempster-Shafter Theory of Evidence. PhD thesis, University of Ulster, 2004.
• 17: Chang, C. C and Lin, C. J. (2001). LIBSVM: a library for support vector machines (http://www.csie.ntu.edu.tw/~cjlin/libsvm).
• 18: Thorsten Joachims, A Probabilistic Analysis of the Rocchio Algorithm with TFIDF for Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.143-151, July 08-12, 1997
• 19: 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]
• 20: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Nonmonotonic reasoning and belief revision
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms
      I.5.4 Applications
          Subjects: Text processing

General Terms:
Algorithms, Design

Keywords:
ensembles of classifiers, evidential reasoning, text categorization