Data analysis with arbitrary error measures approximated by piece-wise quadratic PQSQ functions

Alexander N. Gorban, Evgeny M. Mirkes, Andrei Yu. Zinovyev

Abstract

Defining an error function (a measure of deviation of a model prediction from the data) is a critical step in any optimization-based data analysis method, including regression, clustering and dimension reduction. Usual quadratic error function in case of real-life high-dimensional and noisy data suffers from non-robustness to presence of outliers. Therefore, using non-quadratic error functions in data analysis and machine learning (such as L1 norm-based) is an active field of modern research but the majority of methods suggested are either slow or imprecise (use arbitrary heuristics). We suggest a flexible and highly performant approach to generalize most of existing data analysis methods to an arbitrary error function of subquadratic growth. For this purpose, we exploit PQSQ functions (piece-wise quadratic of subquadratic growth), which can be minimized by a simple and fast splitting-based iterative algorithm. The theoretical basis of the PQSQ approach is an application of min-plus (idempotent) algebra to data approximation. We introduce the general idea of the approach and illustrate it on four standard tools of machine learning: simple regression, regularized regression, k-mean clustering and principal component analysis. In all cases, PQSQ-based methods achieve better robustness with respect to the presence of strong noise in the data compared to the standard methods.
BibTeX
@inproceedings{gorban2018data,
  author = {Alexander N. Gorban and Evgeny M. Mirkes and Andrei Yu. Zinovyev},
  title = {{Data analysis with arbitrary error measures approximated by piece-wise quadratic PQSQ functions}},
  booktitle = {IJCNN},
  year = {2018},
  doi = {10.1109/ijcnn.2018.8489568},
}

Loading related content...

Figure