Polynomial Runtime Bounds for Fixed-Rank Unsupervised Least-Squares Classification

Fabian Gieseke, Tapio Pahikkala, Christian Igel
Proceedings of the 5th Asian Conference on Machine Learning, PMLR 29:62-71, 2013.

Abstract

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 \mathcalO(n^r) time for r ≤2 and in \mathcalO(n^r-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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v29-Gieseke13, title = {Polynomial Runtime Bounds for Fixed-Rank Unsupervised Least-Squares Classification}, author = {Gieseke, Fabian and Pahikkala, Tapio and Igel, Christian}, booktitle = {Proceedings of the 5th Asian Conference on Machine Learning}, pages = {62--71}, year = {2013}, editor = {Ong, Cheng Soon and Ho, Tu Bao}, volume = {29}, series = {Proceedings of Machine Learning Research}, address = {Australian National University, Canberra, Australia}, month = {13--15 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v29/Gieseke13.pdf}, url = {https://proceedings.mlr.press/v29/Gieseke13.html}, abstract = {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 \mathcalO(n^r) time for r ≤2 and in \mathcalO(n^r-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.} }
Endnote
%0 Conference Paper %T Polynomial Runtime Bounds for Fixed-Rank Unsupervised Least-Squares Classification %A Fabian Gieseke %A Tapio Pahikkala %A Christian Igel %B Proceedings of the 5th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Cheng Soon Ong %E Tu Bao Ho %F pmlr-v29-Gieseke13 %I PMLR %P 62--71 %U https://proceedings.mlr.press/v29/Gieseke13.html %V 29 %X 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 \mathcalO(n^r) time for r ≤2 and in \mathcalO(n^r-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.
RIS
TY - CPAPER TI - Polynomial Runtime Bounds for Fixed-Rank Unsupervised Least-Squares Classification AU - Fabian Gieseke AU - Tapio Pahikkala AU - Christian Igel BT - Proceedings of the 5th Asian Conference on Machine Learning DA - 2013/10/21 ED - Cheng Soon Ong ED - Tu Bao Ho ID - pmlr-v29-Gieseke13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 29 SP - 62 EP - 71 L1 - http://proceedings.mlr.press/v29/Gieseke13.pdf UR - https://proceedings.mlr.press/v29/Gieseke13.html 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 \mathcalO(n^r) time for r ≤2 and in \mathcalO(n^r-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. ER -
APA
Gieseke, F., Pahikkala, T. & Igel, C.. (2013). Polynomial Runtime Bounds for Fixed-Rank Unsupervised Least-Squares Classification. Proceedings of the 5th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 29:62-71 Available from https://proceedings.mlr.press/v29/Gieseke13.html.

Related Material