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 = {Fabian Gieseke and Tapio Pahikkala and Christian Igel}, pages = {62--71}, year = {2013}, editor = {Cheng Soon Ong and Tu Bao Ho}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 62--71 %U http://proceedings.mlr.press %V 29 %W PMLR %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 PY - 2013/10/21 DA - 2013/10/21 ED - Cheng Soon Ong ED - Tu Bao Ho ID - pmlr-v29-Gieseke13 PB - PMLR SP - 62 DP - PMLR EP - 71 L1 - http://proceedings.mlr.press/v29/Gieseke13.pdf UR - http://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 PMLR 29:62-71

Related Material