Implementazione di un SVM lineare (binario di supporto)

Question

Voglio implementare un semplice classificatore SVM, nel caso di dati binari ad alta risoluzione (testo), per i quali penso che un SVM lineare semplice sia il migliore. La ragione per implementarla personalmente è fondamentalmente che voglio imparare come funziona, quindi usare una libreria non è quello che voglio.

Il problema è che la maggior parte dei tutorial arriva a un'equazione che può essere risolta come un "problema quadratico", ma non mostrano mai un algoritmo reale! Quindi potresti indicarmi una implementazione molto semplice che potrei studiare, o (meglio) un tutorial che arriva fino ai dettagli di implementazione?

Grazie mille!

Answer 1

Alcuni pseudocodice per il metodo ottimizzazione minima sequenziale (SMO) si possono trovare in questo articolo di John C. Platt: Fast Training of Support Vector Machines using Sequential Minimal Optimization. Esiste anche un'implementazione Java dell'algoritmo SMO, che è stato sviluppato per scopi di ricerca e didattici (SVM-JAVA).

Altri metodi comunemente usati per risolvere il problema di ottimizzazione QP includono:

• gradienti coniugati vincolati
• metodi a punti interni
• metodi set attivi

Ma essere consapevoli che una certa conoscenza di matematica è necessario per capire queste cose (moltiplicatori di Lagrange, condizioni Karush-Kuhn-Tucker, ecc.).

Answer 2

Sei interessato all'utilizzo di kernel o no? Senza i kernel, il modo migliore per risolvere questo tipo di problemi di ottimizzazione è attraverso varie forme di discesa del gradiente stocastico. Una buona versione è descritta in http://ttic.uchicago.edu/~shai/papers/ShalevSiSr07.pdf e ha un algoritmo esplicito.

L'algoritmo esplicito non funziona con i kernel ma può essere modificato; tuttavia, sarebbe più complesso, sia in termini di codice che di complessità di runtime.

Answer 3

Dai un'occhiata alla liblinear e per SVM non lineare all'indirizzo libsvm

Answer 4

Il seguente documento "Pegasos: Primal risolutore stimato sub-gradiente per SVM" parte superiore della pagina 11 descrive l'algoritmo Pegasos anche per kernels.It può essere scaricato da http://ttic.uchicago.edu/~nati/Publications/PegasosMPB.pdf

Sembra essere un ibrido di discesa di coordinate e discesa di subgradient. Inoltre, la riga 6 dell'algoritmo è errata. Nel predicato la seconda apparizione di y_i_t dovrebbe essere sostituita con y_j.