Implémentation de SVM par méthode de descente de gradient probabiliste

Quel est cet article?

La machine à vecteurs de support (SVM) minimise les fonctions objectives suivantes.

\min_{\bf w}\frac{\lambda}{2}\|{\bf w}\|^2+\frac{1}{m}\sum_{({\bf x},y)\in S}l({\bf w}; ({\bf x}, y)) \\
l({\bf w}; ({\bf x},y))=\max(0,1-y\left<{\bf w},{\bf x} \right>)

Online Machine Learning dispose d'un algorithme qui minimise cette fonction objective par la méthode de descente de gradient probabiliste. Cela ne correspondait pas à l'astuce.

Ainsi, lorsque je cherchais une implémentation de SVM utilisant l'astuce du noyau par la méthode de descente de gradient probabiliste, [Pegasos: Primal Estimated sub-GrAdient SOlver for SVM](http://ttic.uchicago.edu/~nati/Publications/ J'ai trouvé un article appelé PegasosMPB.pdf).

Dans cet article, je vais implémenter l'algorithme montré dans l'article.

Entrée et sortie d'algorithme

Implémentez la figure 3 dans le document. L'entrée de l'algorithme est la suivante.

Fig.Choisissez en 3$i_t \in \lbrace 0,\dots,|S| \rbraceUne partie est choisiri_t \in \lbrace 1,\dots,|S|\rbrace$Je pense que c'est une erreur (probablement).

La sortie de l'algorithme est un vecteur de $ \ alpha_ {T + 1} $ avec des éléments $ m $. En utilisant le $ \ alpha_ {T + 1} $ obtenu, la prédiction peut être faite comme suit.

\hat{y}={\bf w}_{T+1}^{\rm T}\phi({\bf x})=\frac{1}{\lambda t}\sum_{j=1}^{m}\alpha_{T+1}[j]y_jK({\bf x}_j,{\bf x})

Exemple d'implémentation par python

Je l'ai implémenté comme sklearn. De plus, l'algorithme a été modifié pour ajouter un terme de biais. Le code source a été téléchargé sur ici.

SGDSVC.py


import numpy as np


class SGDSVC(object):

    def __init__(self,
                 kernel="rbf", lmd=1e-1, gamma=0.1, bias=1.0, max_iter=100):
        if kernel not in self.__kernel_dict:
            print(kernel + " kernel does not exist!\nUse rbf kernel.")
            kernel = "rbf"
        if kernel == "rbf":
            def kernel_func(x, y):
                return self.__kernel_dict[kernel](x,y,gamma=gamma)
        else:
            kernel_func = self.__kernel_dict[kernel]
        self.kernel = kernel_func
        self.lmd = lmd
        self.bias = bias
        self.max_iter = max_iter

    def __linear_kernel(x, y):
        return np.dot(x, y)

    def __gaussian_kernel(x, y, gamma):
        diff = x - y
        return np.exp(-gamma * np.dot(diff, diff))

    __kernel_dict = {"linear": __linear_kernel, "rbf": __gaussian_kernel}

    def fit(self, X, y):
        def update_alpha(alpha, t):
            data_size, feature_size = np.shape(self.X_with_bias)
            new_alpha = np.copy(alpha)
            it = np.random.randint(low=0, high=data_size)
            x_it = self.X_with_bias[it]
            y_it = self.y[it]
            if (y_it *
                (1. / (self.lmd * t)) *
                sum([alpha_j * y_it * self.kernel(x_it, x_j)
                     for x_j, alpha_j in zip(self.X_with_bias, alpha)])) < 1.:
                new_alpha[it] += 1
            return new_alpha

        self.X_with_bias = np.c_[X, np.ones((np.shape(X)[0])) * self.bias]
        self.y = y
        alpha = np.zeros((np.shape(self.X_with_bias)[0], 1))
        for t in range(1, self.max_iter + 1):
            alpha = update_alpha(alpha, t)
        self.alpha = alpha

    def decision_function(self, X):
        X_with_bias = np.c_[X, np.ones((np.shape(X)[0])) * self.bias]
        y_score = [(1. / (self.lmd * self.max_iter)) *
                   sum([alpha_j * y_j * self.kernel(x_j, x)
                        for (x_j, y_j, alpha_j) in zip(
                        self.X_with_bias, self.y, self.alpha)])
                   for x in X_with_bias]
        return np.array(y_score)

    def predict(self, X):
        y_score = self.decision_function(X)
        y_predict = map(lambda s: 1 if s >= 0. else -1, y_score)
        return y_predict

Exemple d'exécution

Voici un exemple de prédiction pour l'ensemble de données d'iris. Afin de confirmer l'exactitude de l'implémentation, les données utilisées lors de la formation sont utilisées telles quelles dans le test. Les paramètres sont $ \ lambda = 0,1, T = 100 $ et le noyau gaussien ($ \ gamma = 0,1 $) est utilisé pour la fonction noyau. En outre, les données d'apprentissage sont mises à l'échelle de sorte que la moyenne soit 0 et la variance 1.

main.py


# -*- coding: utf-8 -*-
import SGDSVC
from sklearn import datasets
from sklearn import preprocessing
from sklearn import metrics

if __name__ == '__main__':
    iris = datasets.load_iris()
    X = iris.data[:100]
    y = iris.target[:100]
    #L'étiquette est 1, -1
    y = map(lambda l: 1 if l == 1 else -1, y)
    #mise à l'échelle
    scaler = preprocessing.StandardScaler()
    X = scaler.fit_transform(X)
    clf = SGDSVC.SGDSVC()
    clf.fit(X, y)
    y_pred = clf.predict(X)
    print("Confusion Matrix")
    print(metrics.confusion_matrix(y, y_pred))
    print(metrics.classification_report(y, y_pred))

Le résultat de l'exécution est le suivant.

Confusion Matrix
[[50  0]
 [ 0 50]]
             precision    recall  f1-score   support

         -1       1.00      1.00      1.00        50
          1       1.00      1.00      1.00        50

avg / total       1.00      1.00      1.00       100

Comme mentionné ci-dessus, c'est le résultat de l'utilisation des données utilisées pendant l'entraînement comme pour le test. Vous pouvez voir que tous les points de données sont correctement classés.

Autre

La version en ligne de SVM est Passive Aggressive, mais le chapitre 1 de cet article décrit la différence avec l'AP. De plus, le nom Pegasos est vraiment cool.

(2015/7/8) Correction de la formule de prédiction car elle était légèrement erronée. (2015/7/10) Japonais corrigé. (2016/1/15) Correction du lien du document cité.

Recommended Posts

Implémentation de SVM par méthode de descente de gradient probabiliste
[TensorFlow] Régression linéaire carrée minimale par méthode de descente de gradient (méthode de descente la plus raide)
Expliquez ce qu'est la méthode de descente de gradient stochastique en l'exécutant en Python
Simulation de Deep Learning / Probabilistic Gradient Descente (SGD)
Implémentation de la méthode de gradient 1
Apprentissage profond appris par mise en œuvre (segmentation) ~ Mise en œuvre de SegNet ~
Présentation de DNC (Differentiable Neural Computers) + Implémentation par Chainer
Implémentation de l'écran de l'administrateur DB par Flask-Admin et Flask-Login
Liste des méthodes de descente de gradient (2020)
Implémentation de la séquence de Fibonacci
Implémentation SVM à une classe
Implémentation SVM en python
Apprentissage des classements à l'aide d'un réseau neuronal (implémentation RankNet par Chainer)
Sauvegardez la sortie de GAN une par une ~ Avec l'implémentation de GAN par PyTorch ~
Sortie du résultat de la méthode de descente de dégradé sous forme d'animation matplotlib