Category Archives: SVM

Bregman divergences, SVMs and possible implications

Posted on by

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:

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

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.

[OT] Star galaxies separation via SVM/CVM classification – Part 2

Posted on by

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 %

[OT] Star galaxies separation via SVM/CVM classification

Posted on by

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.

[OT] Parallel and Distributed SVM

Posted on by

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)

SVC: politica per classificazione BSV

Posted on by

L’algoritmo di Cluster Assignment usato

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%.

Appunti: differenze tra MLP e SVM

Posted on by

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.

SVC: prestazioni del cluster assignment

Posted on by

With regard of this document, recently we have performed the test described at the paragraph 5 with all of two cluster assignment algorithms implemented: Complete Graph Cluster Labeling (CGCL, the classic one) and the Cone Cluster Labeling, respectively presented in

and

In the first case we have a total execution time of 280.87 seconds; in the second case only 0.47 seconds was taken. In both cases, 0.25 seconds was taken in the domain description by the SVM. So, we can say that the classic algorithm was slower than CCL about of 99.92%.

The clustering results are the same and they are reported in the document mentioned above.