Thesis Neminis

In order to find a connection between the works studied (Bregman Co-clustering and Support Vector Clustering) we have performed some research. An interesting result are the following paper:

• bibtex | link
  R. Nock and F. Nielsen, "Fitting the smallest enclosing Bregman balls," in 16th European Conference on Machine Learning, 2005, pp. 649-656.
  @conference{bregmanmeb05,
  author = {Richard Nock and Frank Nielsen},
  Booktitle = {16th European Conference on Machine Learning},
  Date-Added = {2007-06-23 11:00:19 +0200},
  Date-Modified = {2007-11-14 12:55:32 +0100},
  Keywords = {bregman, MEB},
  Number = {3720},
  Pages = {649–656},
  Publisher = {Springer-Verlag},
  Series = {Lectures Notes on Computer Science Series},
  Title = {{Fitting the smallest enclosing Bregman balls}},
  Url = {http://www.sonycsl.co.jp/person/nielsen/BregmanBall/nn-ecml-05.pdf},
  Year = {2005},
  Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGBwpZJGFyY2hpdmVyWCR2ZXJzaW9uVCR0b3BYJG9iamVjdHNfEA9OU0tleWVkQXJjaGl2ZXISAAGGoNEICVRyb290gAGoCwwXGBkaHiVVJG51bGzTDQ4PEBMWWk5TLm9iamVjdHNXTlMua2V5c1YkY2xhc3OiERKABIAFohQVgAKAA4AHXHJlbGF0aXZlUGF0aFlhbGlhc0RhdGFfEEUuLi8uLi8uLi9QYXBlcnMvTm9jay9GaXR0aW5nIHRoZSBzbWFsbGVzdCBlbmNsb3NpbmcgQnJlZ21hbiBiYWxscy5wZGbSGw8cHVdOUy5kYXRhTxECHAAAAAACHAACAAAJRG9jdW1lbnRzAAAAAAAAAAAAAAAAAAAAAAAAvs54rkgrAAAAN6DVH0ZpdHRpbmcgdGhlIHNtYWxsZXN0IzM3QTBEMy5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA3oNPCoreIAAAAAAAAAAAAAwADAAAJAAAAAAAAAAAAAAAAAAAAAAROb2NrABAACAAAvs5cjgAAABEACAAAwqKbaAAAAAEAFAA3oNUANxuAAACy8gAAEsYAABKtAAIAT0RvY3VtZW50czpuZW1vOkRvY3VtZW50czpVbml2ZXJzaXRhOlBhcGVyczpOb2NrOkZpdHRpbmcgdGhlIHNtYWxsZXN0IzM3QTBEMy5wZGYAAA4AYgAwAEYAaQB0AHQAaQBuAGcAIAB0AGgAZQAgAHMAbQBhAGwAbABlAHMAdAAgAGUAbgBjAGwAbwBzAGkAbgBnACAAQgByAGUAZwBtAGEAbgAgAGIAYQBsAGwAcwAuAHAAZABmAA8AFAAJAEQAbwBjAHUAbQBlAG4AdABzABIAVy9uZW1vL0RvY3VtZW50cy9Vbml2ZXJzaXRhL1BhcGVycy9Ob2NrL0ZpdHRpbmcgdGhlIHNtYWxsZXN0IGVuY2xvc2luZyBCcmVnbWFuIGJhbGxzLnBkZgAAEwASL1ZvbHVtZXMvRG9jdW1lbnRzABUAAgAX//8AAIAG0h8gISJYJGNsYXNzZXNaJGNsYXNzbmFtZaMiIyRdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3TSHyAmJ6InJFxOU0RpY3Rpb25hcnkACAARABsAJAApADIARABJAEwAUQBTAFwAYgBpAHQAfACDAIYAiACKAI0AjwCRAJMAoACqAPIA9wD/Ax8DIQMmAy8DOgM+A0wDUwNcA2EDZAAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAANx},
  Bdsk-Url-1 = {http://www.sonycsl.co.jp/person/nielsen/BregmanBall/nn-ecml-05.pdf}
}

The above paper generalizes the Minimum Enclosing Ball (MEB) problem to the Bregman divergences and also provide a generalization of the Bâdoiu-Clarkson (BC) approximation algorith. This is the same algorithm exploited in practical by the Core Vector Machines

• bibtex | link
  I. W. Tsang, J. T. Kwok, and P. Cheung, "Core vector machines: Fast SVM training on very large data sets," Journal of Machine Learning Research, vol. 6, pp. 363-392, 2005.
  @article{cvm05,
  author = {Ivor W. Tsang and James T. Kwok and Pak-Ming Cheung},
  Date-Added = {2007-05-26 12:49:30 +0200},
  Date-Modified = {2007-06-23 08:23:02 +0200},
  Journal = {Journal of Machine Learning Research},
  Keywords = {SVM, CVM, MEB, SVDD},
  Pages = {363–392},
  Title = {Core vector machines: Fast SVM training on very large data sets},
  Url = {http://www.cs.ust.hk/%7Eivor/publication/tsang05a.pdf},
  Volume = {6},
  Year = {2005},
  Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGBwpZJGFyY2hpdmVyWCR2ZXJzaW9uVCR0b3BYJG9iamVjdHNfEA9OU0tleWVkQXJjaGl2ZXISAAGGoNEICVRyb290gAGoCwwXGBkaHiVVJG51bGzTDQ4PEBMWWk5TLm9iamVjdHNXTlMua2V5c1YkY2xhc3OiERKABIAFohQVgAKAA4AHXHJlbGF0aXZlUGF0aFlhbGlhc0RhdGFfEFguLi8uLi8uLi9QYXBlcnMvVHNhbmcvQ29yZSB2ZWN0b3IgbWFjaGluZXMgRmFzdCBTVk0gdHJhaW5pbmcgb24gdmVyeSBsYXJnZSBkYXRhIHNldHMucGRm0hsPHB1XTlMuZGF0YU8RAlQAAAAAAlQAAgAACURvY3VtZW50cwAAAAAAAAAAAAAAAAAAAAAAAL7OeK5IKwAAADctuR9Db3JlIHZlY3RvciBtYWNoaW5lcyMzMkY0MjEucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAMvQhwn3aZgAAAAAAAAAAAAMAAwAACQAAAAAAAAAAAAAAAAAAAAAFVHNhbmcAABAACAAAvs5cjgAAABEACAAAwn2+RgAAAAEAFAA3LbkANxuAAACy8gAAEsYAABKtAAIAUERvY3VtZW50czpuZW1vOkRvY3VtZW50czpVbml2ZXJzaXRhOlBhcGVyczpUc2FuZzpDb3JlIHZlY3RvciBtYWNoaW5lcyMzMkY0MjEucGRmAA4AhgBCAEMAbwByAGUAIAB2AGUAYwB0AG8AcgAgAG0AYQBjAGgAaQBuAGUAcwAgAEYAYQBzAHQAIABTAFYATQAgAHQAcgBhAGkAbgBpAG4AZwAgAG8AbgAgAHYAZQByAHkAIABsAGEAcgBnAGUAIABkAGEAdABhACAAcwBlAHQAcwAuAHAAZABmAA8AFAAJAEQAbwBjAHUAbQBlAG4AdABzABIAai9uZW1vL0RvY3VtZW50cy9Vbml2ZXJzaXRhL1BhcGVycy9Uc2FuZy9Db3JlIHZlY3RvciBtYWNoaW5lcyBGYXN0IFNWTSB0cmFpbmluZyBvbiB2ZXJ5IGxhcmdlIGRhdGEgc2V0cy5wZGYAEwASL1ZvbHVtZXMvRG9jdW1lbnRzABUAAgAX//8AAIAG0h8gISJYJGNsYXNzZXNaJGNsYXNzbmFtZaMiIyRdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3TSHyAmJ6InJFxOU0RpY3Rpb25hcnkACAARABsAJAApADIARABJAEwAUQBTAFwAYgBpAHQAfACDAIYAiACKAI0AjwCRAJMAoACqAQUBCgESA2oDbANxA3oDhQOJA5cDngOnA6wDrwAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAAO8},
  Bdsk-Url-1 = {http://www.cs.ust.hk/~ivor/publication/tsang05a.pdf}
}

CVMs reformulate the SVMs as a MEB problem. Since they use the BC algorithm and such an algorithm has been generalized to the Bregman divergences, the research on vector machines could have interesting implications.

This is a modification of the experiments in this post.

I rapidly built a new training set and this time I use only this training set for training the SVM/CVM. Than, I test the new trained classifier on all three dataset of the previous post.

The training set contain 500 points and has been built using stars and galaxies from another portion of sky.

New accuracy results (SVM)

Longo 01: 95,96 %
Longo 02: 98,08 %
Longo 03: 97,956 %

New accuracy results (CVM)

Longo 01: 96,31 %
Longo 02: 97,67 %
Longo 03: 97,138 %

Let us consider the Longo 02 tested with CVM. We have

Completeness for Stars: 98,4 %
Contamination for Stars: 4,7 %

Completeness for Galaxies: 95,4 %
Contamination for Galaxies: 1,5 %

We have used some astrophysics star/galaxies datasets for our clustering problems, because they have heavily overlapping clusters.

Here we present some results of an SVM classification performed on the same datasets. In fact, S/G separation is usually faced in a supervised way.

We have used a simple nonlinear SVM/CVM classifier with a linear kernel (K(x,y) = x’ * y).

For each dataset, we have used 5% of it as training set. The rest is the test set.

Datasets:

Longo 01, 2500 items, 2000 stars, 500 galaxies
Longo 02, 9816 items, 2935 stars, 6883 galaxies
Longo 03, 10940 items, 2978 stars, 7964 galaxies

Accuracy results:

Longo 01: 95%
Longo 02: 98,0746%
Longo 03: 97,925%

Accuracy results with CVM:

Longo 01: 94,98%
Longo 02: 97,5%
Longo 03: 95,2%

Probably, other kernels could lead to better results, but it is necessary to understand in which way tune the hyperparameters, such as the kernel width and the soft margin constant, etc.

In the Documents section are available the slides entitled: “Novel Clustering Techniques: Support Vector Methods and Minimum Bregman Information principle”

SVC has been explained with more care because it still is a very experimental technique.

Three slides on Parallel and Distributed SVMs.

Download

References:

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1650264
http://esl.inf.cbs.dk/rup/index.php/DSVM
http://dm.unife.it/gpdt/ (and links therein)
http://www.cs.unibo.it/~roffilli/thesis/TURROPPT.pdf
http://www.cs.unibo.it/~roffilli/thesis/TURRON05.pdf
http://research.microsoft.com/users/jplatt/smo.html (and links therein)

L’algoritmo di Cluster Assignment usato

• bibtex | link
  S. Lee and K. M. Daniels, "Cone Cluster Labeling for Support Vector Clustering," in Proceedings of 6th SIAM Conference on Data Mining, 2006, pp. 484-488.
  @inproceedings{cone2006,
  author = {Sei-Hyung Lee and Karen M. Daniels},
  Booktitle = {Proceedings of 6th SIAM Conference on Data Mining},
  Date-Added = {2007-04-29 16:58:13 +0200},
  Date-Modified = {2007-06-19 18:52:22 +0200},
  Keywords = {SVM, clustering},
  Month = {May},
  Pages = {484–488},
  Title = {Cone Cluster Labeling for Support Vector Clustering},
  Url = {http://www.siam.org/meetings/sdm06/proceedings/046lees.pdf},
  Year = {2006},
  Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGBwpZJGFyY2hpdmVyWCR2ZXJzaW9uVCR0b3BYJG9iamVjdHNfEA9OU0tleWVkQXJjaGl2ZXISAAGGoNEICVRyb290gAGoCwwXGBkaHiVVJG51bGzTDQ4PEBMWWk5TLm9iamVjdHNXTlMua2V5c1YkY2xhc3OiERKABIAFohQVgAKAA4AHXHJlbGF0aXZlUGF0aFlhbGlhc0RhdGFfEEsuLi8uLi8uLi9QYXBlcnMvTGVlL0NvbmUgQ2×1c3RlciBMYWJlbGluZyBmb3IgU3VwcG9ydCBWZWN0b3IgQ2×1c3RlcmluZy5wZGbSGw8cHVdOUy5kYXRhTxECLgAAAAACLgACAAAJRG9jdW1lbnRzAAAAAAAAAAAAAAAAAAAAAAAAvs54rkgrAAAANyVBH0NvbmUgQ2×1c3RlciBMYWJlbGluIzJGMDk0My5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAvCUPCWn72AAAAAAAAAAAAAwADAAAJAAAAAAAAAAAAAAAAAAAAAANMZWUAABAACAAAvs5cjgAAABEACAAAwlpi1gAAAAEAFAA3JUEANxuAAACy8gAAEsYAABKtAAIATkRvY3VtZW50czpuZW1vOkRvY3VtZW50czpVbml2ZXJzaXRhOlBhcGVyczpMZWU6Q29uZSBDbHVzdGVyIExhYmVsaW4jMkYwOTQzLnBkZgAOAHAANwBDAG8AbgBlACAAQwBsAHUAcwB0AGUAcgAgAEwAYQBiAGUAbABpAG4AZwAgAGYAbwByACAAUwB1AHAAcABvAHIAdAAgAFYAZQBjAHQAbwByACAAQwBsAHUAcwB0AGUAcgBpAG4AZwAuAHAAZABmAA8AFAAJAEQAbwBjAHUAbQBlAG4AdABzABIAXS9uZW1vL0RvY3VtZW50cy9Vbml2ZXJzaXRhL1BhcGVycy9MZWUvQ29uZSBDbHVzdGVyIExhYmVsaW5nIGZvciBTdXBwb3J0IFZlY3RvciBDbHVzdGVyaW5nLnBkZgAAEwASL1ZvbHVtZXMvRG9jdW1lbnRzABUAAgAX//8AAIAG0h8gISJYJGNsYXNzZXNaJGNsYXNzbmFtZaMiIyRdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3TSHyAmJ6InJFxOU0RpY3Rpb25hcnkACAARABsAJAApADIARABJAEwAUQBTAFwAYgBpAHQAfACDAIYAiACKAI0AjwCRAJMAoACqAPgA/QEFAzcDOQM+A0cDUgNWA2QDawN0A3kDfAAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAAOJ},
  Bdsk-Url-1 = {http://www.siam.org/meetings/sdm06/proceedings/046lees.pdf}
}

come tutti gli altri proposti in letteratura non tratta esplicitamente la classificaizione dei Bounded Support Vector, ovvero di quei punti che, per effetto del valore della costante di margine morbido, finiscono fuori dalla sfera di descrizione del dominio anche se in realtà fanno parte di una delle classi del problema.

Il Cone Cluster Labeling prevede due passi:

• classificazione dei SV
• classificazione di tutti gli altri punti in relazione ai SV

che di fatto comprende anche i BSV in “tutti gli altri punti”.

Si è scelto di modificare in questo modo l’algoritmo:

• classificazione dei SV
• classificazione di tutti gli altri punti (tranne i BSV) in relazione ai SV
• classificazione dei BSV in relazione a tutti gli altri punti già classificati

Nel caso dell’IRIS data set, questa modifica ha portato l’accuratezza da un valore di 89,333% a un valore del 90%.

I limiti principali del Multi-Layer Perceptron (MLP) sono:

• la necessità di fissare a priori la struttura della rete, in termini di hidden layers e di numero di neuroni da porre in ognuno di essi
• l’eccessiva ampiezza delle maggiorazioni ottenute per la VC-dimension dei modelli impiegati praticamente
• difficoltà di addestramento nel caso di dataset non linearmente separabili:
• a causa dell’alto numero di dimensioni dello spazio dei pesi
• poiché le tecniche più diffuse, come la back-propagation, permettono di ottenere i pesi della rete risolvendo un problema di ottimizzazione non convesso e non vincolato che, di conseguenza, presenta un numero indeterminato di minimi locali.

Le SVM superano questi problemi.
Innanzitutto non c’è la necessità di costruire esplicitamente la funzione non lineare per mappare gli ingressi nello spazio degli attributi. Tramite il kernel trick si opera implicitamente nello spazio degli attributi (equivalente allo spazio degli hidden layers). In questo modo ci si svincola dall’obbligo di fissare a priori la struttura della rete neurale. Allo stesso tempo si rende le SVM scalabili rispetto a dati di alta dimensionalità.
Inoltre le SVM assicurano una soluzione unica e globale nel caso si scelta un kernel definito positivamente.