Reducing the human overhead in text categorization

ABSTRACT

Many applications in text processing require significant human effort for either labeling large document collections (when learning statistical models) or extrapolating rules from them (when using knowledge engineering). In this work, we describe away to reduce this effort, while retaining the methods' accuracy, by constructing a hybrid classifier that utilizes human reasoning over automatically discovered text patterns to complement machine learning. Using a standard sentiment-classification dataset and real customer feedback data, we demonstrate that the resulting technique results in significant reduction of the human effort required to obtain a given classification accuracy. Moreover, the hybrid text classifier also results in a significant boost in accuracy over machine-learning based classifiers when a comparable amount of labeled data is used.

REFERENCES

• 1: Polarity dataset v2.0. http://www.cs.cornell.edu/people/pabo/movie-review-data/.
• 2: Hiroki Arimura , Hiroki Asaka , Hiroshi Sakamoto , Setsuo Arikawa, Efficient Discovery of Proximity Patterns with Suffix Arrays, Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, p.152-156, July 01-04, 2001
• 3: Hiroki Arimura , Hiroshi Sakamoto , Setsuo Arikawa, Efficient Data Mining from Large Text Databases, Progress in Discovery Science, Final Report of the Japanese Discovery Science Project, p.123-139, January 2002
• 4: P. Beineke, T. Hastie, and S. Vaithyanathan. The Sentimental Factor: Improving Review Classification via Human-Provided Information. In Proceedings of the 42nd ACL Conference, 2004.
• 5: Susan Dumais , John Platt , David Heckerman , Mehran Sahami, Inductive learning algorithms and representations for text categorization, Proceedings of the seventh international conference on Information and knowledge management, p.148-155, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288651]
• 6: 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
• 7: J. Kärkkäinen and P. Sanders. Simple Linear Work Suffix Array Construction. In Proceedings of 13th International Conference on Automata, Languages and Programming, 2003.
• 8: B. Lui, X. Li, W. S. Lee, and P. S. Yu. Text Classification by Labeling Words. In Proceedings of the 19th National Conference on Artificial Intelligence, 2004.
• 9: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.319-327, January 22-24, 1990, San Francisco, California, United States
• 10: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 11: Kamal Nigam , Andrew McCallum , Sebastian Thrun , Tom Mitchell, Learning to classify text from labeled and unlabeled documents, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.792-799, July 1998, Madison, Wisconsin, United States
• 12: B. Pang and L. Lee. A Sentimental Education: Sentiment Analysis Using Subjectivity Summarization Based on Minimum Cuts. In Proceedings of the 42nd ACL Conference, 2004.
• 13: Bo Pang , Lillian Lee , Shivakumar Vaithyanathan, Thumbs up?: sentiment classification using machine learning techniques, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.79-86, July 06, 2002 [doi>10.3115/1118693.1118704]
• 14: John C. Platt, Fast training of support vector machines using sequential minimal optimization, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 15: H. Raghavan, O. Madani, and R. Jones. InterActive Feature Selection. In Proceedings of IJCAI-05, pages 841--846, 2005.
• 16: Mehran Sahami , Daphne Koller, Using machine learning to improve information access, 1999
• 17: H. S. Seung , M. Opper , H. Sompolinsky, Query by committee, Proceedings of the fifth annual workshop on Computational learning theory, p.287-294, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130417]
• 18: Simon Tong , Daphne Koller, Support vector machine active learning with applications to text classification, The Journal of Machine Learning Research, 2, p.45-66, 3/1/2002
• 19: V. Vapnik. Statistical Learning Theory. Whiley, 2000.
• 20: Xiaoyun Wu , Rohini Srihari, Incorporating prior knowledge with weighted margin support vector machines, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014089]
• 21: Mikio Yamamoto , Kenneth W. Church, Using suffix arrays to compute term frequency and document frequency for all substrings in a corpus, Computational Linguistics, v.27 n.1, p.1-30, March 2001 [doi>10.1162/089120101300346787]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human information processing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing

General Terms:
Algorithms, Experimentation

Keywords:
active learning, classification, machine learning, supervised learning, support vector machines, text classification, text mining