An accelerator for kernel ridge regression algorithms based on data partition

doi:10.3969/j.issn.0253-2778.2018.04.003

Journal of University of Science and Technology of China ›› 2018, Vol. 48 ›› Issue (4): 284-289.DOI: 10.3969/j.issn.0253-2778.2018.04.003

• Original Paper • Previous Articles Next Articles

An accelerator for kernel ridge regression algorithms based on data partition

LIU Enjiang, SONG Yunsheng, LIANG Jiye,

1. School of Computer and Information Technology，Shanxi University，Taiyuan 030006， China；
2. Key Laboratory of Computational Intelligence and Chinese Information Processing， Taiyuan 030006， China）

Received:2017-05-23 Revised:2017-06-24 Online:2018-04-30 Published:2018-04-30

Abstract

Abstract: Kernel ridge regression (KRR) is an important regression algorithm widely used in pattern recognition and data mining for its interpretability and strong generalization capability. However, it has the defect of low training efficiency when faced with large-scale data. To address this problem， an accelerating algorithm is proposed which uses the concept of divide-and-conquer for kernel ridge regression based on data partition (PP-KRR). Firstly, the current training data space is divided into m mutually disjoint regions by a bunch of parallel hyperplanes. Secondly, each KRR model is trained on each region respectively. Finally, each unlabeled instance is predicted by the KRR model within the same region. Comparisons with three traditional algorithms on real datasets show that the proposed algorithm obtains similar prediction accuracy with less training time.

Key words: kernel ridge regression, divide-and-conquer, parallel partition, principal component analysis

CLC Number:

TP391

LIU Enjiang, SONG Yunsheng, LIANG Jiye,. An accelerator for kernel ridge regression algorithms based on data partition[J]. Journal of University of Science and Technology of China, 2018, 48(4): 284-289.

References

［1］
ROSIPAL R. Kernel-based regression and objective nonlinear measures to assess brain functioning[D]. Scotland: University of Paisley, 2001.
[2] SCHLKOPF B, SMOLA A, MLLER K R. Nonlinear component analysis as a kernel eigenvalue problem[J]. Neural computation, 1998, 10(5): 1299-1319.
[3] FINE S, SCHEINBERG K. Efficient SVM training using low-rank kernel representations[J]. Journal of Machine Learning Research, 2001, 2: 243-264.
[4] WILLIAMS C K I, SEEGER M. Using the Nystrm method to speed up kernel machines[C]// Proceedings of the 13th Conference on Neural Information Processing Systems. Cambridge: MIT press, 2000: 661-667.
[5] BACH F. Sharp analysis of low-rank kernel matrix approximations[J]. Journal of Machine Learning Research, 2012, 30: 185-209.
[6] ALAOUI A E, MAHONEY M W. Fast randomized kernel ridge regression with statistical guarantees[C]// Proceedings of the 28th Conference on Neural Information Processing Systems. Cambridge: MIT Press, 2015: 775-783.
[7] RUDI A, CAMORIANO R, ROSASCO L. Less is more: Nystrm computational regularization[C]// Proceedings of the 28th Conference on Neural Information Processing Systems. Cambridge: MIT Press, 2015: 1657-1665.
[8] RAHIMI A, RECHT B. Random features for large-scale kernel machines[C]// Proceedings of the 20th Conference on Neural Information Processing Systems. Cambridge: MIT Press, 2007: 1177-1184.
[9] YAO Y, ROSASCO L, CAPONNETTO A. On early stopping in gradient descent learning[J]. Constructive Approximation, 2007, 26(2): 289-315.
[10] BLANCHARD G, KRMER N. Optimal learning rates for kernel conjugate gradient regression[C]// Proceedings of the 20th Conference on Neural Information Processing Systems. Cambridge: MIT Press, 2010: 226-234.
[11] ZHANG Y, DUCHI J, WAINWRIGHT M. Divide and conquer kernel ridge regression: A distributed algorithm with minimax optimal rates[J]. Journal of Machine Learning Research, 2015, 16: 3299-3340.
[12] GU Q, HAN J. Clustered support vector machines[C]// Proceedings of the 16th International Conference on Artificial Intelligence and Statistics. Scottsdale: PMLR, 2013, 31: 307-315.
[13] HSIEH C J, SI S, DHILLON I S. A divide-and-conquer solver for kernel support vector machines[C]// Proceedings of the 31th International Conference on Machine Learning. Beijing: PMLR, 2014, 32(1): 566-574.
[14] TANDON R, SI S, RAVIKUMAR P, et al. Kernel ridge regression via partitioning[J/OL]. (2016.8.5) [2017.5.24]. https : // arxix.org/pdf/1608.01976.pdf
[15] GITTENS A, MAHONEY M W. Revisiting the Nystrm method for improved large scale machine learning[J]. Journal of Machine Learning Research, 2016, 17(1): 3977-4041.
[16] HUANG P S, AVRON H, SAINATH T N, et al. Kernel methods match deep neural networks on TIMIT[C]// Proceedings of the 39th IEEE International Conference on Acoustics, Speech and Signal Processing. Piscataway: IEEE press, 2014: 205-209.
[17] BOTTOU L, VAPNIK V. Local learning algorithms[J]. Neural computation, 1992, 4(6): 888-900.
[18] ZHANG Y, DUCHI J C, WAINWRIGHT M J. Communication-efficient algorithms for statistical optimization[J]. Journal of Machine Learning Research, 2012, 14(1): 3321-3363.
[19] MACKEY L, TALWALKAR A, JORDAN M I. Divide-and-Conquer matrix factorization[C]// Proceedings of the 25th Conference on Neural Information Processing Systems. Cambridge: MIT Press, 2012: 1134-1142.
[20] PAN Y, XIA R, YIN J, et al. A divide-and-conquer method for scalable robust multitask learning[J]. IEEE transactions on neural networks and learning systems, 2015, 26(12): 3163-3175.

()
(

[1]	JIN Baisuo, LI Chikun. Outlier detection of Yangtze River basin meteorological databased on robust S-estimator [J]. Journal of University of Science and Technology of China, 2018, 48(11): 869-876.
[2]	LU Wei, SHAO Limin. Estimation of the number of primary factors based on residual matrix variance ratio [J]. Journal of University of Science and Technology of China, 2014, 44(11): 881-886.

An accelerator for kernel ridge regression algorithms based on data partition

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments