An interactive algorithm for asking and incorporating feature feedback into support vector machines

ABSTRACT

Standard machine learning techniques typically require ample training data in the form of labeled instances. In many situations it may be too tedious or costly to obtain sufficient labeled data for adequate classifier performance. However, in text classification, humans can easily guess the relevance of features, that is, words that are indicative of a topic, thereby enabling the classifier to focus its feature weights more appropriately in the absence of sufficient labeled data. We will describe an algorithm for tandem learning that begins with a couple of labeled instances, and then at each iteration recommends features and instances for a human to label. Tandem learning using an "oracle" results in much better performance than learning on only features or only instances. We find that humans can emulate the oracle to an extent that results in performance (accuracy) comparable to that of the oracle. Our unique experimental design helps factor out system error from human error, leading to a better understanding of when and why interactive feature selection works.

REFERENCES

• 1: J. Allan. Topic detection and tracking. Kluwer, 2002.
• 2: Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129746]
• 3: Ron Bekkerman , Ran El-Yaniv , Naftali Tishby , Yoad Winter, On feature distributional clustering for text categorization, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.146-153, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383976]
• 4: J. Brank, M. Grobelnik, N. Milic-Frayling, and D. Mladenic. Feature selection using linear support vector machines. Technical report, Microsoft Research, 2002.
• 5: J. Cohen. A coefficient of agreement for nominal scales. Educational and Psychological Measurement, 20, 1960.
• 6: David Cohn , Les Atlas , Richard Ladner, Improving Generalization with Active Learning, Machine Learning, v.15 n.2, p.201-221, May 1994 [doi>10.1023/A:1022673506211]
• 7: W. B. Croft , R. Das, Experiments with query acquisition and use in document retrieval systems, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.349-368, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98240]
• 8: Aynur Dayanik , David D. Lewis , David Madigan , Vladimir Menkov , Alexander Genkin, Constructing informative prior distributions from domain knowledge in text classification, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148255]
• 9: Shantanu Godbole , Abhay Harpale , Sunita Sarawagi , Soumen Chakrabarti, Document classification through interactive supervision of document and term labels, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.185-196, September 20-24, 2004, Pisa, Italy
• 10: Yifen Huang , Tom M. Mitchell, Text clustering with extended user feedback, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148242]
• 11: 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
• 12: G. Landis and G. Koch. The measurement of observer agreement for categorical data. Biometrics, 33:159--174, 1977.
• 13: K. Lang. Newsweeder: Learning to filter netnews. In ICML 95, pages 331--339, 1995.
• 14: D. D. Lewis and J. Catlett. Heterogeneous uncertainty sampling for supervised learning. In ICML 94, pages 148--156, 1994.
• 15: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 16: Mark Magennis , Cornelis J. van Rijsbergen, The potential and actual effectiveness of interactive query expansion, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.324-332, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 17: Hema Raghavan , James Allan, Tandem learning: a learning framework for document categorization, University of Massachusetts Amherst, 2007
• 18: Hema Raghavan , Omid Madani , Rosie Jones, Active Learning with Feedback on Features and Instances, The Journal of Machine Learning Research, 7, p.1655-1686, 12/1/2006
• 19: T. G. Rose, M. Stevenson, and M. Whitehead. The reuters corpus vol. 1 - from yesterday's news to tomorrow's language resources. In Proceedings of International Conference on Language Resources and Evaluation, 2002.
• 20: Ian Ruthven, Re-examining the potential effectiveness of interactive query expansion, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860475]
• 21: Robert E. Schapire , Marie Rochery , Mazin G. Rahim , Narendra Gupta, Incorporating Prior Knowledge into Boosting, Proceedings of the Nineteenth International Conference on Machine Learning, p.538-545, July 08-12, 2002
• 22: Scholkopf and Smola. Learning with kernels. MIT Press, Cambridge, MA, 2002.
• 23: 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]
• 24: T. Strohman, D. Metzler, H. Turtle, and W. B. Croft. Indri: A language model-based search engine for complex queries. In International Conference on Intelligence Analysis, 2005.
• 25: Simon Tong , Daphne Koller, Active learning: theory and applications, 2001
• 26: 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
• 27: 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]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human factors

General Terms:
Algorithms, Experimentation

Keywords:
term feedback, text classification