Polynomial runtime bounds for fixed-rank unsupervised least-squares classification

TY - GEN

T1 - Polynomial runtime bounds for fixed-rank unsupervised least-squares classification

AU - Gieseke, Fabian Cristian

AU - Pahikkala, Tapio

AU - Igel, Christian

N1 - Conference code: 5

PY - 2013

Y1 - 2013

N2 - Maximum margin clustering can be regarded as the direct extension of support vector machines to unsupervised learning scenarios. The goal is to partition unlabeled data into two classes such that a subsequent application of a support vector machine would yield the overall best result (with respect to the optimization problem associated with support vector machines). While being very appealing from a conceptual point of view, the combinatorial nature of the induced optimization problem renders a direct application of this concept difficult. In order to obtain efficient optimization schemes, various surrogates of the original problem definition have been proposed in the literature. In this work, we consider one of these variants, called unsupervised regularized least-squares classification, which is based on the square loss, and develop polynomial upper runtime bounds for the induced combinatorial optimization task. In particular, we show that for n patterns and kernel matrix of fixed rank r (with given eigendecomposition), one can obtain an optimal solution in O(nr) time for r ≤ 2 and in O(nr-1) time for r ≥ 3. The algorithmic framework is based on an interesting connection to the field of quadratic zero-one programming and permits the computation of exact solutions for the more general case of non-linear kernel functions in polynomial time. Keywords: Maximum Margin Clustering, Combinatorial Optimization, Unsupervised Learning.

AB - Maximum margin clustering can be regarded as the direct extension of support vector machines to unsupervised learning scenarios. The goal is to partition unlabeled data into two classes such that a subsequent application of a support vector machine would yield the overall best result (with respect to the optimization problem associated with support vector machines). While being very appealing from a conceptual point of view, the combinatorial nature of the induced optimization problem renders a direct application of this concept difficult. In order to obtain efficient optimization schemes, various surrogates of the original problem definition have been proposed in the literature. In this work, we consider one of these variants, called unsupervised regularized least-squares classification, which is based on the square loss, and develop polynomial upper runtime bounds for the induced combinatorial optimization task. In particular, we show that for n patterns and kernel matrix of fixed rank r (with given eigendecomposition), one can obtain an optimal solution in O(nr) time for r ≤ 2 and in O(nr-1) time for r ≥ 3. The algorithmic framework is based on an interesting connection to the field of quadratic zero-one programming and permits the computation of exact solutions for the more general case of non-linear kernel functions in polynomial time. Keywords: Maximum Margin Clustering, Combinatorial Optimization, Unsupervised Learning.

M3 - Article in proceedings

VL - 29

T3 - JMLR: Workshop and Conference Proceedings

SP - 62

EP - 71

BT - Asian Conference on Machine Learning

A2 - Ong, Cheng Soon

A2 - Ho, Tu Bao

T2 - Asian Conference on Machine Learning (ACML) 2013

Y2 - 13 November 2013 through 15 November 2013

ER -