A refinement approach to handling model misfit in text categorization

ABSTRACT

Text categorization or classification is the automated assigning of text documents to pre-defined classes based on their contents. This problem has been studied in information retrieval, machine learning and data mining. So far, many effective techniques have been proposed. However, most techniques are based on some underlying models and/or assumptions. When the data fits the model well, the classification accuracy will be high. However, when the data does not fit the model well, the classification accuracy can be very low. In this paper, we propose a refinement approach to dealing with this problem of model misfit. We show that we do not need to change the classification technique itself (or its underlying model) to make it more flexible. Instead, we propose to use successive refinements of classification on the training data to correct the model misfit. We apply the proposed technique to improve the classification performance of two simple and efficient text classifiers, the Rocchio classifier and the naïve Bayesian classifier. These techniques are suitable for very large text collections because they allow the data to reside on disk and need only one scan of the data to build a text classifier. Extensive experiments on two benchmark document corpora show that the proposed technique is able to improve text categorization accuracy of the two techniques dramatically. In particular, our refined model is able to improve the naïve Bayesian or Rocchio classifier's prediction performance by 45% on average.

REFERENCES

• 1: Kamal M. Ali , Michael J. Pazzani, Error reduction through learning multiple descriptions, Machine Learning, v.24 n.3, p.173-202, Sept. 1996 [doi>10.1023/A:1018249309965 ]
• 2: Apte, C., Hong, S., Hosking, J., Lepre, J., Pednault, E. and Rosen, B. Decomposition of heterogeneous classification problems, Intelligent Data Analysis, 1998.
• 3: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350 ]
• 4: Chris Buckley , Gerard Salton , James Allan, The effect of adding relevance information in a relevance feedback environment, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.292-300, July 03-06, 1994, Dublin, Ireland
• 5: Chan, P. and Stolfo, S. Comparative evaluation of voting and meta-learning on partitioned data. In Proceedings of the Twelfth International Conference on Machine Learning, 1995.
• 6: Chan, P. and Stolfo, S. Learning arbiter and combiner trees from partitioned data for scaling machine learning. In Proceedings of the International Conference on Knowledge Discovery and Data Mining, 1995.
• 7: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 8: Mark Craven , Dan DiPasquo , Dayne Freitag , Andrew McCallum , Tom Mitchell , Kamal Nigam , Seán Slattery, Learning to extract symbolic knowledge from the World Wide Web, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.509-516, July 1998, Madison, Wisconsin, United States
• 9: Duda, R. and Hart, P. Pattern Classification and Scene Analysis, 1973.
• 10: Elkan, C. Boosting and naive Bayesian learning. In Proceedings of the International Conference on Knowledge Discovery and Data Mining, 1997.
• 11: Dayne Freitag, Multistrategy Learning for Information Extraction, Proceedings of the Fifteenth International Conference on Machine Learning, p.161-169, July 24-27, 1998
• 12: Freund, Y. and Schapire, R. Experiments with a new boosting algorithm, In Proceedings of the Thirteenth International Conference on Machine Learning, 1996.
• 13: Friedman, J. Flexible metric nearest neighbor classification, Technical Report, 1994.
• 14: Guo, Y. and Sutiwaraphun, J. Knowledge probing in distributed data mining. In Advances in Distributed and Parallel Knowledge Discovery, 1999.
• 15: Hand, D. and Yu, K. Idiot's Bayes - Not so Stupid after All? 2001.
• 16: David A. Hull , Jan O. Pedersen , Hinrich Schütze, Method combination for document filtering, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.279-287, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243275]
• 17: Vijay S. Iyengar , Chidanand Apte , Tong Zhang, Active learning using adaptive resampling, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.91-98, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347110]
• 18: 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
• 19: 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
• 20: Yu-Hwan Kim , Shang-Yoon Hahn , Byoung-Tak Zhang, Text filtering by boosting naive Bayes classifiers, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.168-175, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345572]
• 21: Kohavi, R. Scaling up the accuracy of naïve-Bayes classifiers: A decision-tree hybrid. In Proceedings of the Second International. Conference on Knowledge Discovery Data Mining, 1996.
• 22: Shailesh Kumar , Joydeep Ghosh , Melba M. Crawford, A Hierarchical Multiclassifier System for Hyperspectral Data Analysis, Proceedings of the First International Workshop on Multiple Classifier Systems, p.270-279, June 21-23, 2000
• 23: Wai Lam , Kwok-Yin Lai, A meta-learning approach for text categorization, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.303-309, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384011]
• 24: Lang, K. Newsweeder: Learning to filter netnews. In Proceedings of International Conference on Machine Learning, 1995.
• 25: Leah S. Larkey , W. Bruce Croft, Combining classifiers in text categorization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.289-297, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243276]
• 26: David D. Lewis , William A. Gale, A sequential algorithm for training text classifiers, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.3-12, July 03-06, 1994, Dublin, Ireland
• 27: Lewis, D. & Ringuette, M. A comparison of two learning algorithms for text categorization, Third Annual Symposium on Document Analysis and Information Retrieval (pp. 81--93), 1994.
• 28: Nick Littlestone , Manfred K. Warmuth, THE WEIGHTED MAJORITY ALGORITHM (Supersedes 89-16), University of California at Santa Cruz, Santa Cruz, CA, 1992
• 29: McCallum, A., & Nigam, K. A comparison of event models for naïïve Bayes text classification, AAAI-98 Workshop on Learning for Text Categorization. Tech. Rep. WS-98-05, AAAI Press, 1998
• 30: Pavlov, D. and Mao, J. Scaling-up Support Vector machines using boosting algorithm. In International Conference on Pattern Recognition, 2000.
• 31: Quinlan, J. Bagging, boosting and C4.5. In Proceedings AAAI, 1996.
• 32: Robert E. Schapire , Yoav Freund , Peter Barlett , Wee Sun Lee, Boosting the margin: A new explanation for the effectiveness of voting methods, Proceedings of the Fourteenth International Conference on Machine Learning, p.322-330, July 08-12, 1997
• 33: Robert E. Schapire , Yoram Singer , Amit Singhal, Boosting and Rocchio applied to text filtering, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.215-223, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290996]
• 34: Robert E. Schapire , Yoram Singer, Improved Boosting Algorithms Using Confidence-rated Predictions, Machine Learning, v.37 n.3, p.297-336, Dec. 1999 [doi>10.1023/A:1007614523901 ]
• 35: 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
• 36: Ting, K. and Witten, I. Stacked generalization: when does it work? In Proceedings of the Fifteenth International oint Conference on Artificial Intelligence, 1997.
• 37: Kai Ming Ting , Zijian Zheng, Improving the Performance of Boosting for Naive Bayesian Classification, Proceedings of the Third Pacific-Asia Conference on Methodologies for Knowledge Discovery and Data Mining, p.296-305, April 26-28, 1999
• 38: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 39: David H. Wolpert, Stacked generalization, Neural Networks, v.5 n.2, p.241-259, 1992 [doi>10.1016/S0893-6080(05)80023-1]
• 40: Yiming Yang, An Evaluation of Statistical Approaches to Text Categorization, Information Retrieval, v.1 n.1-2, p.69-90, 1999
• 41: 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]
• 42: 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

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Text analysis

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo); Statistical computing

General Terms:
Algorithms, Measurement, Performance

Keywords:
Rocchio algorithm, naïve Bayesian classifier, text categorization