Approximate regularized least squares algorithm for classification

Jing Peng, Alex J. Aved

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

In machine learning, a good predictive model is the one that generalizes well over future unseen data. In general, this problem is ill-posed. To mitigate this problem, a predictive model can be constructed by simultaneously minimizing an empirical error over training samples and controlling the complexity of the model. Thus, the regularized least squares (RLS) is developed. RLS requires matrix inversion, which is expensive. And as such, its "big data" applications can be adversely affected. To address this issue, we have developed an efficient machine learning algorithm for pattern recognition that approximates RLS. The algorithm does not require matrix inversion, and achieves competitive performance against the RLS algorithm. It has been shown mathematically that RLS is a sound learning algorithm. Therefore, a definitive statement about the relationship between the new algorithm and RLS will lay a solid theoretical foundation for the new algorithm. A recent study shows that the spectral norm of the kernel matrix in RLS is tightly bounded above by the size of the matrix. This spectral norm becomes a constant when the training samples have independent centered sub-Gaussian coordinators. For example, typical sub-Gaussian random vectors such as the standard normal and Bernoulli satisfy this assumption. Basically, each sample is drawn from a product distribution formed from some centered univariate sub-Gaussian distributions. These new results allow us to establish a bound between the new algorithm and RLS in finite samples and show that the new algorithm converges to RLS in the limit. Experimental results are provided that validate the theoretical analysis and demonstrate the new algorithm to be very promising in solving "big data" classification problems.

Original languageEnglish
Title of host publicationPattern Recognition and Tracking XXIX
EditorsMohammad S. Alam
PublisherSPIE
Volume10649
ISBN (Electronic)9781510618091
DOIs
StatePublished - 1 Jan 2018
EventPattern Recognition and Tracking XXIX 2018 - Orlando, United States
Duration: 18 Apr 201819 Apr 2018

Other

OtherPattern Recognition and Tracking XXIX 2018
CountryUnited States
CityOrlando
Period18/04/1819/04/18

Fingerprint

Approximate Algorithm
Least Square Algorithm
Least Squares
Spectral Norm
Matrix Inversion
Predictive Model
Training Samples
machine learning
Learning algorithms
Learning systems
norms
Learning Algorithm
Machine Learning
education
Gaussian distribution
inversions
Data Classification
Pattern recognition
Random Vector
Bernoulli

Keywords

  • Classification
  • regularized least squares
  • ridge regression

Cite this

Peng, J., & Aved, A. J. (2018). Approximate regularized least squares algorithm for classification. In M. S. Alam (Ed.), Pattern Recognition and Tracking XXIX (Vol. 10649). [106490S] SPIE. https://doi.org/10.1117/12.2305075
Peng, Jing ; Aved, Alex J. / Approximate regularized least squares algorithm for classification. Pattern Recognition and Tracking XXIX. editor / Mohammad S. Alam. Vol. 10649 SPIE, 2018.
@inproceedings{15bdc6df09bc4414b1ad06faeec0f55b,
title = "Approximate regularized least squares algorithm for classification",
abstract = "In machine learning, a good predictive model is the one that generalizes well over future unseen data. In general, this problem is ill-posed. To mitigate this problem, a predictive model can be constructed by simultaneously minimizing an empirical error over training samples and controlling the complexity of the model. Thus, the regularized least squares (RLS) is developed. RLS requires matrix inversion, which is expensive. And as such, its {"}big data{"} applications can be adversely affected. To address this issue, we have developed an efficient machine learning algorithm for pattern recognition that approximates RLS. The algorithm does not require matrix inversion, and achieves competitive performance against the RLS algorithm. It has been shown mathematically that RLS is a sound learning algorithm. Therefore, a definitive statement about the relationship between the new algorithm and RLS will lay a solid theoretical foundation for the new algorithm. A recent study shows that the spectral norm of the kernel matrix in RLS is tightly bounded above by the size of the matrix. This spectral norm becomes a constant when the training samples have independent centered sub-Gaussian coordinators. For example, typical sub-Gaussian random vectors such as the standard normal and Bernoulli satisfy this assumption. Basically, each sample is drawn from a product distribution formed from some centered univariate sub-Gaussian distributions. These new results allow us to establish a bound between the new algorithm and RLS in finite samples and show that the new algorithm converges to RLS in the limit. Experimental results are provided that validate the theoretical analysis and demonstrate the new algorithm to be very promising in solving {"}big data{"} classification problems.",
keywords = "Classification, regularized least squares, ridge regression",
author = "Jing Peng and Aved, {Alex J.}",
year = "2018",
month = "1",
day = "1",
doi = "10.1117/12.2305075",
language = "English",
volume = "10649",
editor = "Alam, {Mohammad S.}",
booktitle = "Pattern Recognition and Tracking XXIX",
publisher = "SPIE",

}

Peng, J & Aved, AJ 2018, Approximate regularized least squares algorithm for classification. in MS Alam (ed.), Pattern Recognition and Tracking XXIX. vol. 10649, 106490S, SPIE, Pattern Recognition and Tracking XXIX 2018, Orlando, United States, 18/04/18. https://doi.org/10.1117/12.2305075

Approximate regularized least squares algorithm for classification. / Peng, Jing; Aved, Alex J.

Pattern Recognition and Tracking XXIX. ed. / Mohammad S. Alam. Vol. 10649 SPIE, 2018. 106490S.

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

T1 - Approximate regularized least squares algorithm for classification

AU - Peng, Jing

AU - Aved, Alex J.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - In machine learning, a good predictive model is the one that generalizes well over future unseen data. In general, this problem is ill-posed. To mitigate this problem, a predictive model can be constructed by simultaneously minimizing an empirical error over training samples and controlling the complexity of the model. Thus, the regularized least squares (RLS) is developed. RLS requires matrix inversion, which is expensive. And as such, its "big data" applications can be adversely affected. To address this issue, we have developed an efficient machine learning algorithm for pattern recognition that approximates RLS. The algorithm does not require matrix inversion, and achieves competitive performance against the RLS algorithm. It has been shown mathematically that RLS is a sound learning algorithm. Therefore, a definitive statement about the relationship between the new algorithm and RLS will lay a solid theoretical foundation for the new algorithm. A recent study shows that the spectral norm of the kernel matrix in RLS is tightly bounded above by the size of the matrix. This spectral norm becomes a constant when the training samples have independent centered sub-Gaussian coordinators. For example, typical sub-Gaussian random vectors such as the standard normal and Bernoulli satisfy this assumption. Basically, each sample is drawn from a product distribution formed from some centered univariate sub-Gaussian distributions. These new results allow us to establish a bound between the new algorithm and RLS in finite samples and show that the new algorithm converges to RLS in the limit. Experimental results are provided that validate the theoretical analysis and demonstrate the new algorithm to be very promising in solving "big data" classification problems.

AB - In machine learning, a good predictive model is the one that generalizes well over future unseen data. In general, this problem is ill-posed. To mitigate this problem, a predictive model can be constructed by simultaneously minimizing an empirical error over training samples and controlling the complexity of the model. Thus, the regularized least squares (RLS) is developed. RLS requires matrix inversion, which is expensive. And as such, its "big data" applications can be adversely affected. To address this issue, we have developed an efficient machine learning algorithm for pattern recognition that approximates RLS. The algorithm does not require matrix inversion, and achieves competitive performance against the RLS algorithm. It has been shown mathematically that RLS is a sound learning algorithm. Therefore, a definitive statement about the relationship between the new algorithm and RLS will lay a solid theoretical foundation for the new algorithm. A recent study shows that the spectral norm of the kernel matrix in RLS is tightly bounded above by the size of the matrix. This spectral norm becomes a constant when the training samples have independent centered sub-Gaussian coordinators. For example, typical sub-Gaussian random vectors such as the standard normal and Bernoulli satisfy this assumption. Basically, each sample is drawn from a product distribution formed from some centered univariate sub-Gaussian distributions. These new results allow us to establish a bound between the new algorithm and RLS in finite samples and show that the new algorithm converges to RLS in the limit. Experimental results are provided that validate the theoretical analysis and demonstrate the new algorithm to be very promising in solving "big data" classification problems.

KW - Classification

KW - regularized least squares

KW - ridge regression

UR - http://www.scopus.com/inward/record.url?scp=85049185425&partnerID=8YFLogxK

U2 - 10.1117/12.2305075

DO - 10.1117/12.2305075

M3 - Conference contribution

VL - 10649

BT - Pattern Recognition and Tracking XXIX

A2 - Alam, Mohammad S.

PB - SPIE

ER -

Peng J, Aved AJ. Approximate regularized least squares algorithm for classification. In Alam MS, editor, Pattern Recognition and Tracking XXIX. Vol. 10649. SPIE. 2018. 106490S https://doi.org/10.1117/12.2305075