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.
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| \rbrace
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})
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
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.
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