tailieunhanh - Báo cáo khoa học: "An Approximate Approach for Training Polynomial Kernel SVMs in Linear Time"

count instead of explicitly combines features. By setting with polynomial kernel degree (., d), different number of feature conjunctions can be imKernel methods such as support vector maplicitly computed. In this way, polynomial kernel chines (SVMs) have attracted a great deal SVM is often better than linear kernel which did of popularity in the machine learning and not use feature conjunctions. However, the training natural language processing (NLP) comand testing time costs for polynomial kernel SVM munities. . | An Approximate Approach for Training Polynomial Kernel SVMs in Linear Time Yu-Chieh Wu Dept. of Computer Science and Information Engineering National Central University Taoyuan Taiwan bcbb@ Jie-Chi Yang Graduate Institute of Network Learning Technology National Central University Taoyuan Taiwan yang@. tw Yue-Shi Lee Dept. of Computer Science and Information Engineering Ming Chuan University Taoyuan Taiwan lees@ Abstract Kernel methods such as support vector machines SVMs have attracted a great deal of popularity in the machine learning and natural language processing NLP communities. Polynomial kernel SVMs showed very competitive accuracy in many NLP problems like part-of-speech tagging and chunking. However these methods are usually too inefficient to be applied to large dataset and real time purpose. In this paper we propose an approximate method to analogy polynomial kernel with efficient data mining approaches. To prevent exponential-scaled testing time complexity we also present a new method for speeding up SVM classifying which does independent to the polynomial degree d. The experimental results showed that our method is and 450 times faster than traditional polynomial kernel in terms of training and testing respectively. 1 Introduction Kernel methods for example support vector machines SVM Vapnik 1995 are successfully applied to many natural language processing NLP problems. They yielded very competitive and satisfactory performance in many classification tasks such as part-of-speech POS tagging Gimenez and Marquez 2003 shallow parsing Kudo and Matsumoto 2001 2004 Lee and Wu 2007 named entity recognition Isozaki and Kazawa 2002 and parsing Nivre et al. 2006 . In particular the use of polynomial kernel SVM implicitly takes the feature combinations into ac count instead of explicitly combines features. By setting with polynomial kernel degree . d different number of feature conjunctions can be implicitly .