La mise en oeuvre d'un linéaire, SVM binaire (support vector machine)

Question

Je veux mettre en œuvre simple SVM, dans le cas de données binaires de grande dimension (texte), pour lequel je pense simple SVM linéaire est le meilleur. La raison de la mise en œuvre moi-même est fondamentalement que je veux savoir comment cela fonctionne, donc en utilisant une bibliothèque est pas ce que je veux.

Le problème est que la plupart des tutoriels vont à une équation qui peut être résolu comme un « problème quadratique », mais ils ne montrent jamais un algorithme réel! Pourriez-vous me diriger soit à une mise en œuvre très simple que je pourrais étudier, ou (mieux) à un tutoriel qui va tout le chemin aux détails de mise en œuvre?

Merci beaucoup!

Answer 1

Certains pseudo-code pour la Méthode séquentielle Optimisation minimale (SMO) se trouve dans ce document par John C. Platt: formation rapide de support Vector Machines utilisant l'optimisation séquentielle minimale . Il y a aussi une implémentation Java de l'algorithme de SMO, qui est développé pour la recherche et le but éducatif ( 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 de l'ensemble actif

Mais sachez que certaines connaissances mathématiques sont nécessaires pour comprendre ces choses (multiplicateurs de Lagrange, les conditions Karush-Kuhn-Tucker, etc.).

Answer 2

Êtes-vous intéressé à utiliser les noyaux ou non? Sans noyaux, la meilleure façon de résoudre ce genre de problèmes d'optimisation est soumis à diverses 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 code et de la complexité de l'exécution.

Answer 3

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

Answer 4

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

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