ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

An accelerator for kernel ridge regression algorithms based on data partition

  • 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

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2018.04.003
  • Received Date: 23 May 2017
  • Rev Recd Date: 24 June 2017
  • Publish Date: 30 April 2018
    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.

    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.
    • FullText(HTML)
  • loading
    • References(20)
  • [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.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [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.
    Recommended articles
    TrendMD
    Volume 48 Issue 4 page: 284-289
    Cover

    Article Metrics

    Article views (1031) PDF downloads(507)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return