Extracting query modifications from nonlinear SVMs

ABSTRACT

When searching the WWW, users often desire results restricted to a particular document category. Ideally, a user would be able to filter results with a text classifier to minimize false positive results; however, current search engines allow only simple query modifications. To automate the process of generating effective query modifications, we introduce a sensitivity analysis-based method for extracting rules from nonlinear support vector machines. The proposed method allows the user to specify a desired precision while attempting to maximize the recall. Our method performs several levels of dimensionality reduction and is vastly faster than searching the combination feature space; moreover, it is very effective on real-world data.

REFERENCES

• 1: W. Cohen. Fast effective rule induction. In Proc. of the Twelfth Int. Conf. on Machine Learning, pages 115--123. Morgan Kaufmann, 1995.
• 2: Gary William Flake , Steve Lawrence, Efficient SVM Regression Training with SMO, Machine Learning, v.46 n.1-3, p.271-290, 2002 [doi>10.1023/A:1012474916001]
• 3: S. Gauch, G. Wang, and M. Gomez. ProFusion: Intelligent fusion from multiple, distributed search engines. Journal of Universal Computer Science, 2(9), 1996.
• 4: Eric J. Glover , Steve Lawrence , William P. Birmingham , C. Lee Giles, Architecture of a metasearch engine that supports user information needs, Proceedings of the eighth international conference on Information and knowledge management, p.210-216, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.319980]
• 5: E. J. Glover, S. Lawrence, M. D. Gordon, W. P. Birmingham, and C. L. Giles. Recommending web documents based on user preferences. In ACM SIGIR 99 Workshop on Recommender Systems, Berkeley, CA, August 1999. ACM Press.
• 6: Eric J. Glover , Gary W. Flake , Steve Lawrence , Andries Kruger , David M. Pennock , William P. Birmingham , C. Lee Giles, Improving Category Specific Web Search by Learning Query Modifications, Proceedings of the 2001 Symposium on Applications and the Internet (SAINT 2001), p.23, January 08-12, 2001
• 7: A. E. Howe and D. Dreilinger. SavvySearch: A meta-search engine that learns which search engines to query. AI Magazine, 18(2), 1997.
• 8: 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
• 9: Thorsten Joachims, Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the Sixteenth International Conference on Machine Learning, p.200-209, June 27-30, 1999
• 10: Steve Lawrence , C. Lee Giles, Context and Page Analysis for Improved Web Search, IEEE Internet Computing, v.2 n.4, p.38-46, July 1998 [doi>10.1109/4236.707689]
• 11: 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
• 12: J. Platt. Using sparseness and analytic QP to speed training of support vector machines. In M. S. Kearns, S. A. Solla, and D. A. Cohn, editors, Advances in Neural Information Processing Systems 11. MIT Press, 1999.
• 13: E. Selberg and O. Etzioni. The MetaCrawler architecture for resource aggregation on the Web. IEEE Expert, (January--February):11--14, 1997.
• 14: Geoffrey G. Towell , Jude W. Shavlik, Extracting Refined Rules from Knowledge-Based Neural Networks, Machine Learning, v.13 n.1, p.71-101, Oct. 1993 [doi>10.1023/A:1022683529158]
• 15: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

General Terms:
Algorithms, Experimentation

Keywords:
query modification, rule extraction, sensitivity analysis, support vector machine