Die Support Vector Machine (SVM) minimiert die folgenden Zielfunktionen.
\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 verfügt über einen Algorithmus, der diese Zielfunktion durch die probabilistische Gradientenabstiegsmethode minimiert. Es entsprach nicht dem Trick.
Als ich nach einer Implementierung von SVM mit dem Kernel-Trick nach der Methode des probabilistischen Gradientenabstiegs suchte, Pegasos: Primal Estimated Sub-GrAdient SOlver für SVM Ich habe ein Papier namens PegasosMPB.pdf gefunden.
In diesem Artikel werde ich den in diesem Artikel gezeigten Algorithmus implementieren.
Implementieren Sie Abb.3 im Papier. Die Eingabe des Algorithmus ist wie folgt.
Fig.Wählen Sie in 3$i_t \in \lbrace 0,\dots,|S| \rbrace
Die Ausgabe des Algorithmus ist ein Vektor von $ \ alpha_ {T + 1} $ mit $ m $ Elementen. Unter Verwendung des erhaltenen $ \ alpha_ {T + 1} $ kann die Vorhersage wie folgt gemacht werden.
\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})
Ich habe es wie sklearn implementiert. Außerdem wurde der Algorithmus modifiziert, um einen Bias-Term hinzuzufügen. Der Quellcode wurde auf [hier] hochgeladen (https://bitbucket.org/sz_dr/sgdsvc).
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
Hier ist eine Beispielvorhersage für den Iris-Datensatz. Um die Richtigkeit der Implementierung zu bestätigen, werden die während des Trainings verwendeten Daten wie im Test verwendet. Die Parameter sind $ \ lambda = 0.1, T = 100 $ und der Gaußsche Kernel ($ \ gamma = 0.1 $) wird für die Kernelfunktion verwendet. Zusätzlich werden die Trainingsdaten so skaliert, dass der Mittelwert 0 und die Varianz 1 ist.
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]
#Label ist 1, -1
y = map(lambda l: 1 if l == 1 else -1, y)
#Skalierung
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))
Das Ausführungsergebnis ist wie folgt.
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
Wie oben erwähnt, ist dies das Ergebnis der Verwendung der während des Trainings verwendeten Daten wie für den Test. Sie können sehen, dass alle Datenpunkte korrekt klassifiziert sind.
Die Online-Version von SVM ist Passive Aggressive, aber Kapitel 1 dieses Dokuments beschreibt die Unterschiede zu PA. Auch der Name Pegasos ist wirklich cool.
(08.07.2015) Die Vorhersageformel wurde korrigiert, da sie leicht falsch war. (10.07.2015) Japanisch korrigiert. (15.01.2016) Der Link des zitierten Papiers wurde korrigiert.
Recommended Posts