Context-sensitive learning methods for text categorization

ABSTRACT

Two recently implemented machine-learning algorithms, RIPPERand sleeping-experts for phrases, are evaluated on a number of large text categorization problems. These algorithms both construct classifiers that allow the “context” of a word w to affect how (or even whether) the presence or absence of w will contribute to a classification. However, RIPPER and sleeping-experts differ radically in many other respects: differences include different notions as to what constitutes a context, different ways of combining contexts to construct a classifier, different methods to search for a combination of contexts, and different criteria as to what contexts should be included in such a combination. In spite of these differences, both RIPPER and sleeping-experts perform extremely well across a wide variety of categorization problems, generally outperforming previously applied learning methods. We view this result as a confirmation of the usefulness of classifiers that represent contextual information.

REFERENCES

• 1: ALMUALLIM, H. AND DIETTERICH, T. 1991. Learning with many irrelevant features. In Proceedings of the 9th National Conference on Artificial Intelligence (AAAI-91, July 14-19), T. Dean and K. McKeown, Eds. MIT Press, Cambridge, MA.
• 2: Chidanand Apté , Fred Damerau , Sholom M. Weiss, Towards language independent automated learning of text categorization models, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.23-30, July 03-06, 1994, Dublin, Ireland
• 3: Chidanand Apté , Fred Damerau , Sholom M. Weiss, Automated learning of decision rules for text categorization, ACM Transactions on Information Systems (TOIS), v.12 n.3, p.233-251, July 1994 [doi>10.1145/183422.183423]
• 4: ARMSTRONG, R., FRIETAG, D., JOACHIMS, T., AND MITCHELL, T. M. 1995. WebWatcher: A learning apprentice for the World Wide Web. In Proceedings of the 1995 AAAI Spring Symposium on Information Gathering from Heterogenous Distributed Environments (Stanford, CA, Mar.). AAAI Press, Menlo Park, CA.
• 5: A. Blum, Learning boolean functions in an infinite attribute space, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.64-72, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100224]
• 6: BLUM, A. 1995. Empirical support for WINNOW and weighted majority algorithms: Results on a calendar scheduling domain. In Proceedings of the 12th International Conference on Machine Learning (Lake Tahoe, CA).
• 7: BRUNK, C. AND PAZZANI, M. 1991. Noise-tolerant relational concept learning algorithms. In Proceedings of the 8th International Workshop on Machine Learning (Ithaca, NY). Morgan Kaufmann, San Mateo, California.
• 8: Chris Buckley , Gerard Salton, Optimization of relevance feedback weights, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.351-357, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215383]
• 9: 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
• 10: Nicolò Cesa-Bianchi , Yoav Freund , David P. Helmbold , David Haussler , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.382-391, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167198]
• 11: CHURCH, K. W. AND GALE, W.A. 1995. Poisson mixtures. Nat. Lang. Eng. 1, 2, 163-190.
• 12: COHEN, W. W. 1993. Efficient pruning methods for separate-and-conquer rule learning systems. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (Chambery, France).
• 13: COHEN, W. W. 1995a. Fast effective rule induction. In Proceedings of the 12th International Conference on Machine Learning (Lake Tahoe, CA).
• 14: COHEN, W. W. 1995b. Text categorization and relational learning. In Proceedings of the 12th International Conference on Machine Learning (Lake Tahoe, CA).
• 15: COHEN, W. W. 1996a. Learning rules that classify e-mail. In Proceedings of the 1996 AAAI Spring Symposium on Machine Learning and Information Access (Palo Alto, CA). AAAI Press, Menlo Park, CA.
• 16: COHEN, W. W. 1996b. Learning with set-valued features. In Proceedings of the 13th National Conference on Artificial Intelligence (Portland, OR).
• 17: COHEN, W. W. AND SINGER, Y. 1996. Learning to query the Web. In Proceedings of AAAI-96 Workshop on Internet-Based Information Systems. AAAI Press, Menlo Park, CA.
• 18: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Proceedings of the Second European Conference on Computational Learning Theory, p.23-37, March 13-15, 1995
• 19: Yoav Freund , Robert E. Schapire , Yoram Singer , Manfred K. Warmuth, Using and combining predictors that specialize, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.334-343, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258616]
• 20: F RNKRANZ, J. AND WIDMER, G. 1994. Incremental reduced error pruning. In Proceedings of the 11th Annual Conference on Machine Learning (New Brunswick, NJ). Morgan Kaufmann Publishers Inc., San Francisco, CA.
• 21: David A. Hull, Stemming algorithms: a case study for detailed evaluation, Journal of the American Society for Information Science, v.47 n.1, p.70-84, Jan. 1996 [doi>10.1002/(SICI)1097-4571(199601)47:1<70::AID-ASI7>3.3.CO;2-Q]
• 22: HULL, S., PEDERSEN, J., AND SCHUTZE, H. 1995. Method combination for document filtering. In Proceedings of the 18th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '95, Seattle, WA, July 9-13), E. A. Fox, P. Ingwersen, and R. Fidel, Eds. ACM Press, New York, NY.
• 23: ITTNER, D. g., LEWIS, D. D., AND AHN, D. D. 1995. Text categorization of low quality images. In Symposium on Document Analysis and Information Retrieval (Las Vegas, NV). 301-315.
• 24: JOHN, G., KOHAVI, R., AND PFEGER, K. 1994. Irrelevant features and the subset selection problem. In Proceedings of the 11th Annual Conference on Machine Learning (New Brunswick, NJ). Morgan Kaufmann Publishers Inc., San Francisco, CA.
• 25: Jyrki Kivinen , Manfred Warmuth, EXPONENTIATED GRADIENT VERSUS GRADIENT DESCENT FOR LINEAR PREDICTORS, University of California at Santa Cruz, Santa Cruz, CA, 1994
• 26: David D. Lewis, An evaluation of phrasal and clustered representations on a text categorization task, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.37-50, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133172]
• 27: David Dolan Lewis, Representation and learning in information retrieval, University of Massachusetts, Amherst, MA, 1992
• 28: LEWIS, D. AND CATLETT, g. 1994. Heterogeneous uncertainty sampling for supervised learning. In Proceedings of the 11th Annual Conference on Machine Learning (New Brunswick, NJ). Morgan Kaufmann Publishers Inc., San Francisco, CA.
• 29: 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
• 30: LEWIS, D. AND RINGUETTE, M. 1994. A comparison of two learning algorithms for text categorization. In Symposium on Document Analysis and Information Retrieval (Las Vegas, NV).
• 31: David D. Lewis , Robert E. Schapire , James P. Callan , Ron Papka, Training algorithms for linear text classifiers, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.298-306, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243277]
• 32: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 33: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]
• 34: Hwee Tou Ng , Wei Boon Goh , Kok Leong Low, Feature selection, perception learning, and a usability case study for text categorization, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.67-73, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 35: Giulia Pagallo , David Haussler, Boolean Feature Discovery in Empirical Learning, Machine Learning, v.5 n.1, p.71-99, Mar. 1990 [doi>10.1023/A:1022611825350]
• 36: Michael Pazzani , Larry Nguyen , Stefanus Mantik, Learning from Hotlists and Coldlists: Towards a WWW Information Filtering and Seeking Agent, Proceedings of the Seventh International Conference on Tools with Artificial Intelligence, p.492, November 05-08, 1995
• 37: Pat Langley, Editorial: Advice to Machine Learning Authors, Machine Learning, v.5 n.3, p.233-237, Aug. 1990 [doi>10.1023/A:1022647305786]
• 38: QUINLAN, J. R. 1995. MDL and categorical theories (continued). In Proceedings of the 12th International Conference on Machine Learning (Lake Tahoe, CA).
• 39: ROCCHIO, J. 1971. Relevance feedback information retrieval. In The Smart Retrieval System--Experiments in Automatic Document Processing, G. Salton, Ed. Prentice-Hall, Englewood Cliffs, NJ, 313-323.
• 40: SALTON, G. 1991. Developments in automatic text retrieval. Science 253, 974-980.
• 41: 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]
• 42: SCHUTZE, H., HULL, D., AND PEDERSEN, g. 1996. A comparison of classifiers and document representations for the routing problem. In Proceedings of the 19th Annual ACM International SIGIR Conference on Research and Development in Information Retrieval (Zurich, Switzerland). ACM Press, New York, NY.
• 43: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 44: Volodimir G. Vovk, Aggregating strategies, Proceedings of the third annual workshop on Computational learning theory, p.371-386, August 06-08, 1990, Rochester, New York, United States
• 45: WIENER, E., PEDERSON, J. O., AND WIEGEND, A. S. 1995. A neural network approach to topic spotting. In Symposium on Document Analysis and Information Retrieval (Las Vegas, NV). 317-332.
• 46: Yiming Yang, Expert network: effective and efficient learning from human decisions in text categorization and retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.13-22, July 03-06, 1994, Dublin, Ireland
• 47: Yiming Yang , Christopher G. Chute, An example-based mapping method for text categorization and retrieval, ACM Transactions on Information Systems (TOIS), v.12 n.3, p.252-277, July 1994 [doi>10.1145/183422.183424]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Parameter learning; Concept learning
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing

General Terms:
Algorithms, Experimentation

Keywords:
context-sensitive models, mistake-driven algorithms, on-line learning, rule learning, text categorization