Implémentation d'un SVM binaire linéaire (machine à vecteurs de support)

Question

Je souhaite implémenter un classificateur SVM simple, dans le cas de données binaires de grande dimension (texte), pour lequel je pense qu'un SVM linéaire simple est le meilleur. La raison de la mise en œuvre moi-même est fondamentalement que je veux apprendre comment cela fonctionne, donc l'utilisation d'une bibliothèque n'est pas ce que je veux. Le problème est que la plupart des tutoriels vont jusqu'à une équation qui peut être résolue comme un "problème quadratique", mais ils ne montrent jamais un algorithme réel! Alors pourriez-vous me montrer soit une mise en œuvre très simple que je pourrais étudier, ou (mieux) un tutoriel allant jusqu'aux détails d'implémentation?

Merci beaucoup!

Answer 1

Certains pseudo-code pour la méthode séquentielle Optimisation minimale (SMO) se trouvent dans le présent document par John C. Platt: Fast Training of Support Vector Machines using Sequential Minimal Optimization. Il existe également une implémentation Java de l'algorithme SMO, développé à des fins de recherche et d'éducation (SVM-JAVA).

D'autres méthodes couramment utilisées pour résoudre le problème d'optimisation de QP comprennent:

• gradients conjugués contraintes
• méthodes de point intérieur
• méthodes set actifs

Mais il faut savoir que certaines connaissances mathématiques est nécessaire pour comprendre ces choses (multiplicateurs de Lagrange, conditions de Karush-Kuhn-Tucker, etc.).

Answer 2

Êtes-vous intéressé par l'utilisation des noyaux ou non? Sans noyaux, la meilleure façon de résoudre ce genre de problèmes d'optimisation passe par différentes formes de descente de gradient stochastique. Une bonne version est décrite dans http://ttic.uchicago.edu/~shai/papers/ShalevSiSr07.pdf et qui a un algorithme explicite.

L'algorithme explicite ne fonctionne pas avec les noyaux mais peut être modifié; Cependant, il serait plus complexe, à la fois en termes de complexité de code et d'exécution.

Answer 3

Jetez un oeil à liblinear et pour SVM non linéaire de à libsvm

Answer 4

Le document suivant « Pegasos: Primal Solver sous-Gradient estimé pour SVM » haut de la page 11 décrit l'algorithme Pegasos aussi pour kernels.It peut être téléchargé de http://ttic.uchicago.edu/~nati/Publications/PegasosMPB.pdf

Il semble s'agir d'un hybride de descente de coordonnées et de descente de sous-gradient. En outre, la ligne 6 de l'algorithme est erronée. Dans le prédicat, la deuxième apparition de y_i_t devrait être remplacée par y_j à la place.