Kernel Density Estimation, Kernel Methods, and Fast Learning in Large Data Sets

ISCAS OpenIR

	Kernel Density Estimation, Kernel Methods, and Fast Learning in Large Data Sets
	Wang, Shitong; Wang, Jun; Chung, Fu-lai
	2014
发表期刊	IEEE TRANSACTIONS ON CYBERNETICS
ISSN	2168-2267
卷号	44 期号:1 页码:1-20
摘要	Kernel methods such as the standard support vector machine and support vector regression trainings take O(N-3) time and O(N-2) space complexities in their naive implementations, where N is the training set size. It is thus computationally infeasible in applying them to large data sets, and a replacement of the naive method for finding the quadratic programming (QP) solutions is highly desirable. By observing that many kernel methods can be linked up with kernel density estimate (KDE) which can be efficiently implemented by some approximation techniques, a new learning method called fast KDE (FastKDE) is proposed to scale up kernel methods. It is based on establishing a connection between KDE and the QP problems formulated for kernel methods using an entropy-based integrated-squared-error criterion. As a result, FastKDE approximation methods can be applied to solve these QP problems. In this paper, the latest advance in fast data reduction via KDE is exploited. With just a simple sampling strategy, the resulted FastKDE method can be used to scale up various kernel methods with a theoretical guarantee that their performance does not degrade a lot. It has a time complexity of O(m(3)) where m is the number of the data points sampled from the training set. Experiments on different benchmarking data sets demonstrate that the proposed method has comparable performance with the state-of-art method and it is effective for a wide range of kernel methods to achieve fast learning in large data sets.; Kernel methods such as the standard support vector machine and support vector regression trainings take O(N-3) time and O(N-2) space complexities in their naive implementations, where N is the training set size. It is thus computationally infeasible in applying them to large data sets, and a replacement of the naive method for finding the quadratic programming (QP) solutions is highly desirable. By observing that many kernel methods can be linked up with kernel density estimate (KDE) which can be efficiently implemented by some approximation techniques, a new learning method called fast KDE (FastKDE) is proposed to scale up kernel methods. It is based on establishing a connection between KDE and the QP problems formulated for kernel methods using an entropy-based integrated-squared-error criterion. As a result, FastKDE approximation methods can be applied to solve these QP problems. In this paper, the latest advance in fast data reduction via KDE is exploited. With just a simple sampling strategy, the resulted FastKDE method can be used to scale up various kernel methods with a theoretical guarantee that their performance does not degrade a lot. It has a time complexity of O(m(3)) where m is the number of the data points sampled from the training set. Experiments on different benchmarking data sets demonstrate that the proposed method has comparable performance with the state-of-art method and it is effective for a wide range of kernel methods to achieve fast learning in large data sets.
收录类别	SCI
关键词	Kernel Density Estimate (Kde) Kernel Methods Quadratic Programming (Qp) Sampling Support Vector Machine (Svm)
部门归属	[Wang, Shitong; Wang, Jun] Jiangnan Univ, Sch Digital Media, Wuxi 214122, Peoples R China. [Wang, Shitong; Chung, Fu-lai] Hong Kong Polytech Univ, Dept Comp, Kowloon, Hong Kong, Peoples R China. [Wang, Shitong] Chinese Acad Sci, Inst Software, Natl Key Lab Comp Sci, Beijing 100080, Peoples R China.
语种	英语
WOS记录号	WOS:000328948900001
引用统计
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16891
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Wang, Shitong,Wang, Jun,Chung, Fu-lai. Kernel Density Estimation, Kernel Methods, and Fast Learning in Large Data Sets[J]. IEEE TRANSACTIONS ON CYBERNETICS,2014,44(1):1-20.
APA	Wang, Shitong,Wang, Jun,&Chung, Fu-lai.(2014).Kernel Density Estimation, Kernel Methods, and Fast Learning in Large Data Sets.IEEE TRANSACTIONS ON CYBERNETICS,44(1),1-20.
MLA	Wang, Shitong,et al."Kernel Density Estimation, Kernel Methods, and Fast Learning in Large Data Sets".IEEE TRANSACTIONS ON CYBERNETICS 44.1(2014):1-20.