Boosting support vector machines for text classification through parameter-free threshold relaxation

ABSTRACT

Support vector machine (SVM) learning algorithms focus on finding the hyperplane that maximizes the margin (the distance from the separating hyperplane to the nearest examples) since this criterion provides a good upper bound of the generalization error. When applied to text classification, these learning algorithms lead to SVMs with excellent precision but poor recall. Various relaxation approaches have been proposed to counter this problem including: asymmetric SVM learning algorithms (soft SVMs with asymmetric misclassification costs); uneven margin based learning; and thresholding. A review of these approaches is presented here. In addition, in this paper, we describe a new threshold relaxation algorithm. This approach builds on previous thresholding work based upon the beta-gamma algorithm. The proposed thresholding strategy is parameter free, relying on a process of retrofitting and cross validation to set algorithm parameters empirically, whereas our previous approach required the specification of two parameters (beta and gamma). The proposed approach is more efficient, does not require the specification of any parameters, and similarly to the parameter-based approach, boosts the performance of baseline SVMs by at least 20% for standard information retrieval measures.

REFERENCES

• 1: Arampatzis A., Unbiased S-D Threshold Optimization, Initial Query Degradation, Decay, and Incrementality, for Adaptive Document Filtering, Tenth Text Retrieval Conference (TREC-2001), 2002, 596--605.
• 2: Ault T., Yang Y., kNN, Rocchio and Metrics for Information Filtering at TREC-10, Tenth Text Retrieval Conference (TREC-2001), 2002, 84--93
• 3: Cancedda N. et al., Kernel Methods for Document Filtering, Eleventh Text Retrieval Conference (TREC-11), 2003.
• 4: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 5: Evans, D. A., Shanahan, J., Tong, X., Roma, N., Stoica, E., Sheftel, V., Montgomery, J., Bennett, J., Fujita, S., Grefenstette, G. Topic Specific Optimization and Structuring. Tenth Text Retrieval Conference (TREC-2001), 2002, 132--141.
• 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: Keerthi, S. S., Shevade, S. K., Bhattacharyya, C., Murthy, K. R. K. Improvements to Platt's SMO algorithm for SVM classifier design. Technical report, Dept of CSA, IISc, Bangalore, India, 1999.
• 8: LeCun, Y., Jackel, L. D., Bottou, L., Cortes, C., Denker, J. S., Drucker, H., Guyon, I., Muller, U. A., Sackinger, E., Simard, P. and Vapnik, V. Learning algorithms for classification: A comparison on handwritten digit recognition. Neural Networks: The Statistical Mechanics Perspective, 261--276, 1995.
• 9: Lewis D. D., The Reuters-21578 text categorization test collection. http://www.research.att.com/ lewis/reuters21578.html. Checked on 11 May 1998; Timestamp Tue Jan 20 21:07:21 EST 1998.
• 10: Lewis D. D., Applying Support Vector Machines to the TREC-2001 Batch Filtering and Routing Tasks, Tenth Text Retrieval Conference (TREC-2001), 2002, 286--294.
• 11: Yaoyong Li , Hugo Zaragoza , Ralf Herbrich , John Shawe-Taylor , Jaz S. Kandola, The Perceptron Algorithm with Uneven Margins, Proceedings of the Nineteenth International Conference on Machine Learning, p.379-386, July 08-12, 2002
• 12: Mayfield J., McNamee P., Costello C., Piatko C., Banerjee A., JHU/APL at TREC 2001: Experiments in Filtering and in Arabic, Video, and Web Retrieval, at TREC-10, Tenth Text Retrieval Conference (TREC-2001), 2002, 322--332.
• 13: Katharina Morik , Peter Brockhausen , Thorsten Joachims, Combining Statistical Learning with a Knowledge-Based Approach - A Case Study in Intensive Care Monitoring, Proceedings of the Sixteenth International Conference on Machine Learning, p.268-277, June 27-30, 1999
• 14: Edgar Osuna , Robert Freund , Federico Girosi, Training Support Vector Machines: an Application to Face Detection, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.130, June 17-19, 1997
• 15: 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
• 16: Robertson S. E., Soboroff I., The TREC 2001 Filtering Track Report, Tenth Text Retrieval Conference (TREC-2001), 2002, 26--37.
• 17: Robertson S. E., Walker S., Zaragoza H., Herbrich H., Microsoft Cambridge at TREC 2002: Filtering Track, Eleventh Text Retrieval Conference (TREC-2002), 2003.
• 18: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 19: Shanahan J. G., Roma N., Improving SVM Text Classification Performance through Threshold Adjustment, European Conference on Machine Learning (ECML) 2003, To Appear.
• 20: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 21: Vapnik, V., Statistical Learning Theory, Wiley, 1998
• 22: Voorhees E.M., Overview of TREC 2002, Eleventh Text Retrieval Conference (TREC-2002), 2002, 1--16.
• 23: Yiming Yang, A study of thresholding strategies for text categorization, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.137-145, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383975]
• 24: Zhai, C., Jansen, P., Stoica, E., Grot, N., Evans, D. A. Threshold Calibration in CLARIT Adaptive Filtering. Seventh Text Retrieval Conference (TREC-7), 1999, 149--156.
• 25: Y. Zhang and J. Callan. "YFilter at TREC-9". In Proceedings of the Ninth Text REtrieval Conference (TREC-9), (pp. 135--140). National Institute of Standards and Technology, 2001, special publication 500-249.

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
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Parameter learning

General Terms:
Algorithms, Experimentation, Management, Performance

Keywords:
support vector machines, text classification, thresholding