Implementa facilmente SVM multiclasse da zero in Python | di Essam Wisam | Novembre 2023 | Intelligenza-Artificiale

Si può dimostrare che l’equazione di inferenza non cambia:

Tuttavia, ora (xₛ,yₛ) deve ora essere un vettore di supporto che non ha commesso violazioni perché l’equazione presuppone che sia sul bordo del margine (in precedenza, era possibile utilizzare qualsiasi vettore di supporto).

SVM margine morbido del kernel

Soft Margin SVM estende l’Hard Margin SVM per gestire il rumore, ma spesso i dati non sono separabili da un iperpiano a causa di fattori oltre il rumore, come la loro natura non lineare. Soft Margin SVM può essere utilizzato in casi come questi, ma in tal caso la soluzione ottimale implicherà probabilmente un iperpiano che consente molti più errori di quanto sia tollerabile nella realtà.

Kernel Soft Margin SVM generalizza Soft Margin SVM per gestire situazioni in cui i dati sono naturalmente non lineari. Ad esempio, nell’esempio mostrato a sinistra non esiste un iperpiano lineare che Soft Margin SVM possa trovare, indipendentemente dall’impostazione di C, che separerebbe decentemente i dati.

È possibile, tuttavia, mappare ogni punto X nel set di dati a una dimensione superiore tramite una funzione di trasformazione z=Φ(x) per rendere i dati più lineari (o perfettamente lineari) nel nuovo spazio dimensionale superiore. Ciò equivale a sostituire X con z nel duale per ottenere:

In realtà, soprattutto quando Fi si trasforma in uno spazio ad altissima dimensionalità, informatico z può richiedere molto tempo. Questo viene risolto dal trucco del kernel che sostituisce il file zᵗz con un equivalente calcolo di una funzione matematica (chiamata funzione kernel) e che è molto più veloce (ad esempio, una semplificazione algebrica di zᵗz). Ad esempio, ecco alcune funzioni popolari del kernel (ognuna delle quali corrisponde a qualche trasformazione Fi ad uno spazio dimensionale superiore):

Con ciò il problema di ottimizzazione doppia diventa:

e intuitivamente, l’equazione di inferenza diventa (dopo la manipolazione algebrica):

Una derivazione completa di tutte le equazioni sopra presupponendo che tu abbia il sfondo matematico possono essere trovati Qui.

Per l’implementazione useremo

Importazioni di base

Iniziamo importando alcune librerie di base:

import numpy as np                  # for basic operations over arrays
from scipy.spatial import distance  # to compute the Gaussian kernel
import cvxopt                       # to solve the dual opt. problem
import copy                         # to copy numpy arrays 

Definizione di kernel e iperparametri SVM

Iniziamo definendo i tre kernel utilizzando le rispettive funzioni

class SVM:
linear = lambda x, xࠤ , c=0: x @ xࠤ.T
polynomial = lambda x, xࠤ , Q=5: (1 + x @ xࠤ.T)**Q
rbf = lambda x, xࠤ, γ=10: np.exp(-γ*distance.cdist(x, xࠤ,'sqeuclidean'))
kernel_funs = {'linear': linear, 'polynomial': polynomial, 'rbf': rbf}

Per coerenza con gli altri kernel, il kernel lineare accetta un iperparametro aggiuntivo inutile. Come ovvio, kernel_funs prende una stringa per il kernel e restituisce la corrispondente funzione del kernel.

Ora proseguiamo definendo il costruttore:

class SVM:
linear = lambda x, xࠤ , c=0: x @ xࠤ.T
polynomial = lambda x, xࠤ , Q=5: (1 + x @ xࠤ.T)**Q
rbf = lambda x, xࠤ, γ=10: np.exp(-γ*distance.cdist(x, xࠤ,'sqeuclidean'))
kernel_funs = {'linear': linear, 'polynomial': polynomial, 'rbf': rbf}
def __init__(self, kernel='rbf', C=1, k=2):
# set the hyperparameters
self.kernel_str = kernel
self.kernel = SVM.kernel_funs(kernel)
self.C = C                  # regularization parameter
self.k = k                  # kernel parameter
# training data and support vectors (set later)
self.X, y = None, None
self.αs = None
# for multi-class classification (set later)
self.multiclass = False
self.clfs = ()                          

L’SVM ha tre iperparametri principali, il kernel (memorizziamo la stringa data e la corrispondente funzione del kernel), il parametro di regolarizzazione C e l’iperparametro del kernel (da passare alla funzione del kernel); rappresenta Q per il kernel polinomiale e γ per il kernel RBF.

Definire il metodo di adattamento

Per estendere questa lezione con fit E predict funzioni in celle separate, definiremo la seguente funzione e la utilizzeremo come decoratore in seguito:

SVMClass = lambda func: setattr(SVM, func.__name__, func) or func

Ricordiamo che adattare la SVM corrisponde a trovare il vettore di supporto UN per ogni punto risolvendo il problema di ottimizzazione duale:

Permettere UN essere un vettore colonna variabile (UN₁ α₂…α_N)ᵗ e sia y un vettore colonna costante per le etichette (sì₁ y₂ … y_N)ᵗ e lascia K essere una matrice costante dove K(n,m) calcola il kernel in (xₙ, xₘ). Ricordiamo le seguenti equivalenze basate sull’indice rispettivamente per il prodotto scalare, il prodotto esterno e la forma quadratica:

poter scrivere il problema di ottimizzazione duale in forma matriciale come segue:

Sapendo che questo è un programma quadratico come accennato in precedenza, possiamo leggere la programmazione quadratica nella documentazione di CVXOPT:

Le parentesi quadre ti dicono che puoi chiamarlo con (P,q) solo o (P,q,Sol,h) O (P, q, SOL, h, LA, b) e così via (tutto ciò che non viene indicato verrà impostato con un valore predefinito come 1).

Per conoscere i valori di (P, q, SOL, h, LA, b) nel nostro caso, facciamo il seguente confronto:

Rendiamo più semplice il confronto riscrivendo il primo come segue:

Ora è ovvio che (notalo 0≤UN è equivalente a -α≤0):

In questo modo possiamo scrivere la seguente funzione di adattamento:

@SVMClass
def fit(self, X, y, eval_train=False):
# if more than two unique labels, call the multiclass version
if len(np.unique(y)) > 2:
self.multiclass = True
return self.multi_fit(X, y, eval_train)
# if labels given in {0,1} change it to {-1,1}
if set(np.unique(y)) == {0, 1}: y(y == 0) = -1
# ensure y is a Nx1 column vector (needed by CVXOPT)
self.y = y.reshape(-1, 1).astype(np.double) # Has to be a column vector
self.X = X
N = X.shape(0)  # Number of points
# compute the kernel over all possible pairs of (x, x') in the data
# by Numpy's vectorization this yields the matrix K
self.K = self.kernel(X, X, self.k)
### Set up optimization parameters
# For 1/2 x^T P x + q^T x
P = cvxopt.matrix(self.y @ self.y.T * self.K)
q = cvxopt.matrix(-np.ones((N, 1)))
# For Ax = b
A = cvxopt.matrix(self.y.T)
b = cvxopt.matrix(np.zeros(1))
# For Gx <= h
G = cvxopt.matrix(np.vstack((-np.identity(N),
np.identity(N))))
h = cvxopt.matrix(np.vstack((np.zeros((N,1)),
np.ones((N,1)) * self.C)))
# Solve    
cvxopt.solvers.options('show_progress') = False
sol = cvxopt.solvers.qp(P, q, G, h, A, b)
self.αs = np.array(sol("x"))            # our solution
# a Boolean array that flags points which are support vectors
self.is_sv = ((self.αs-1e-3 > 0)&(self.αs <= self.C)).squeeze()
# an index of some margin support vector
self.margin_sv = np.argmax((0 < self.αs-1e-3)&(self.αs < self.C-1e-3))
if eval_train:  
print(f"Finished training with accuracy{self.evaluate(X, y)}")

Ci assicuriamo che si tratti di un problema binario e che le etichette binarie siano impostate come previsto da SVM (±1) e così via sì è un vettore colonna con dimensioni (N,1). Quindi risolviamo il problema di ottimizzazione da trovare (UN₁ α₂…α_N)ᵗ.

Noi usiamo (UN₁ α₂…α_N)ᵗ per ottenere un array di flag che sia 1 in ogni indice corrispondente a un vettore di supporto in modo da poter successivamente applicare l’equazione di previsione sommando solo i vettori di supporto e un indice per un vettore di supporto del margine per (xₛ,yₛ). Si noti che nei controlli si presuppone che i vettori non di supporto potrebbero non averlo α=0 esattamente, se lo è α≤1e-3 allora questo è approssimativamente zero (sappiamo che i risultati CVXOPT potrebbero non essere fondamentalmente precisi). Allo stesso modo, assumiamo che i vettori di supporto non marginali potrebbero non averlo α=C esattamente.

Definire il metodo di previsione

Ricordiamo che l’equazione di previsione è:

@SVMClass
def predict(self, X_t):
if self.multiclass: return self.multi_predict(X_t)
# compute (xₛ, yₛ)
xₛ, yₛ = self.X(self.margin_sv, np.newaxis), self.y(self.margin_sv)
# find support vectors
αs, y, X= self.αs(self.is_sv), self.y(self.is_sv), self.X(self.is_sv)
# compute the second term
b = yₛ - np.sum(αs * y * self.kernel(X, xₛ, self.k), axis=0)
# compute the score
score = np.sum(αs * y * self.kernel(X, X_t, self.k), axis=0) + b
return np.sign(score).astype(int), score

Questo è tutto. Possiamo anche implementare un evaluate metodo per calcolare l’accuratezza (utilizzato in adattamento sopra).

@SVMClass
def evaluate(self, X,y):  
outputs, _ = self.predict(X)
accuracy = np.sum(outputs == y) / len(y)
return round(accuracy, 2)

Testare l’implementazione

from sklearn.datasets import make_classification
import numpy as np
# Load the dataset
np.random.seed(1)
X, y = make_classification(n_samples=2500, n_features=5, 
n_redundant=0, n_informative=5, 
n_classes=2,  class_sep=0.3)
# Test Implemented SVM
svm = SVM(kernel='rbf', k=1)
svm.fit(X, y, eval_train=True)
y_pred, _ = svm.predict(X)
print(f"Accuracy: {np.sum(y==y_pred)/y.shape(0)}")  #0.9108
# Test with Scikit
from sklearn.svm import SVC
clf = SVC(kernel='rbf', C=1, gamma=1)
clf.fit(X, y)
y_pred = clf.predict(X)
print(f"Accuracy: {sum(y==y_pred)/y.shape(0)}")    #0.9108

È possibile modificare il set di dati e l’iperparametro per garantire ulteriormente che siano gli stessi. Idealmente, farlo confrontando le funzioni decisionali piuttosto che l’accuratezza.

Generalizzare l’adattamento alla multiclasse

@SVMClass
def multi_fit(self, X, y, eval_train=False):
self.k = len(np.unique(y))      # number of classes
# for each pair of classes
for i in range(self.k):
# get the data for the pair
Xs, Ys = X, copy.copy(y)
# change the labels to -1 and 1
Ys(Ys!=i), Ys(Ys==i) = -1, +1
# fit the classifier
clf = SVM(kernel=self.kernel_str, C=self.C, k=self.k)
clf.fit(Xs, Ys)
# save the classifier
self.clfs.append(clf)
if eval_train:  
print(f"Finished training with accuracy {self.evaluate(X, y)}")

Per generalizzare il modello al multiclasse, passo K classi. Formiamo un classificatore SVM binario per ogni classe presente in cui eseguiamo il loop su ciascuna classe e rietichettamo i punti ad essa appartenenti in +1 e i punti di tutte le altre classi in -1.

Il risultato della formazione è K classificatori quando forniti K classi in cui il ith il classificatore è stato addestrato sui dati con il metodo ith classe etichettata come +1 e tutte le altre etichettate come -1.

Generalizzare la previsione in multiclasse

Quindi, per eseguire la previsione su un nuovo esempio, scegliamo la classe per la quale il classificatore corrispondente è più sicuro (ha il punteggio più alto)

@SVMClass
def multi_predict(self, X):
# get the predictions from all classifiers
N = X.shape(0)
preds = np.zeros((N, self.k))
for i, clf in enumerate(self.clfs):
_, preds(:, i) = clf.predict(X)
# get the argmax and the corresponding score
return np.argmax(preds, axis=1), np.max(preds, axis=1)

Testare l’implementazione

from sklearn.datasets import make_classification
import numpy as np
# Load the dataset
np.random.seed(1)
X, y = make_classification(n_samples=500, n_features=2, 
n_redundant=0, n_informative=2, 
n_classes=4, n_clusters_per_class=1,  
class_sep=0.3)
# Test SVM
svm = SVM(kernel='rbf', k=4)
svm.fit(X, y, eval_train=True)
y_pred = svm.predict(X)
print(f"Accuracy: {np.sum(y==y_pred)/y.shape(0)}") # 0.65
# Test with Scikit
from sklearn.multiclass import OneVsRestClassifier
from sklearn.svm import SVC
clf = OneVsRestClassifier(SVC(kernel='rbf', C=1, gamma=4)).fit(X, y)
y_pred = clf.predict(X)
print(f"Accuracy: {sum(y==y_pred)/y.shape(0)}")    # 0.65

Tracciare le regioni decisionali per ciascuna ulteriore porta al seguente grafico:

Tieni presente che, sebbene SVM di Sci-kit Learn supporti OVR per impostazione predefinita (senza una chiamata esplicita come mostrato sopra), potenzialmente ha anche ulteriori ottimizzazioni specifiche per SVM.

Codice completo

import numpy as np                  # for basic operations over arrays
from scipy.spatial import distance  # to compute the Gaussian kernel
import cvxopt                       # to solve the dual optimization problem
import copy                         # to copy numpy arrays 
class SVM:
linear = lambda x, xࠤ , c=0: x @ xࠤ .T
polynomial = lambda x, xࠤ , Q=5: (1 + x @ xࠤ.T)**Q
rbf = lambda x, xࠤ , γ=10: np.exp(-γ * distance.cdist(x, xࠤ,'sqeuclidean'))
kernel_funs = {'linear': linear, 'polynomial': polynomial, 'rbf': rbf}
def __init__(self, kernel='rbf', C=1, k=2):
# set the hyperparameters
self.kernel_str = kernel
self.kernel = SVM.kernel_funs(kernel)
self.C = C                  # regularization parameter
self.k = k                  # kernel parameter
# training data and support vectors
self.X, y = None, None
self.αs = None
# for multi-class classification
self.multiclass = False
self.clfs = ()                                  
# This is useless here (only for notebook)
SVMClass = lambda func: setattr(SVM, func.__name__, func) or func
@SVMClass
def fit(self, X, y, eval_train=False):
if len(np.unique(y)) > 2:
self.multiclass = True
return self.multi_fit(X, y, eval_train)
# relabel if needed
if set(np.unique(y)) == {0, 1}: y(y == 0) = -1
# ensure y has dimensions Nx1
self.y = y.reshape(-1, 1).astype(np.double) # Has to be a column vector
self.X = X
N = X.shape(0)
# compute the kernel over all possible pairs of (x, x') in the data
self.K = self.kernel(X, X, self.k)
# For 1/2 x^T P x + q^T x
P = cvxopt.matrix(self.y @ self.y.T * self.K)
q = cvxopt.matrix(-np.ones((N, 1)))
# For Ax = b
A = cvxopt.matrix(self.y.T)
b = cvxopt.matrix(np.zeros(1))
# For Gx <= h
G = cvxopt.matrix(np.vstack((-np.identity(N),
np.identity(N))))
h = cvxopt.matrix(np.vstack((np.zeros((N,1)),
np.ones((N,1)) * self.C)))
# Solve    
cvxopt.solvers.options('show_progress') = False
sol = cvxopt.solvers.qp(P, q, G, h, A, b)
self.αs = np.array(sol("x"))
# Maps into support vectors
self.is_sv = ((self.αs > 1e-3) & (self.αs <= self.C)).squeeze()
self.margin_sv = np.argmax((1e-3 < self.αs) & (self.αs < self.C - 1e-3))
if eval_train:  
print(f"Finished training with accuracy {self.evaluate(X, y)}")
@SVMClass
def multi_fit(self, X, y, eval_train=False):
self.k = len(np.unique(y))      # number of classes
# for each pair of classes
for i in range(self.k):
# get the data for the pair
Xs, Ys = X, copy.copy(y)
# change the labels to -1 and 1
Ys(Ys!=i), Ys(Ys==i) = -1, +1
# fit the classifier
clf = SVM(kernel=self.kernel_str, C=self.C, k=self.k)
clf.fit(Xs, Ys)
# save the classifier
self.clfs.append(clf)
if eval_train:  
print(f"Finished training with accuracy {self.evaluate(X, y)}")
@SVMClass
def predict(self, X_t):
if self.multiclass: return self.multi_predict(X_t)
xₛ, yₛ = self.X(self.margin_sv, np.newaxis), self.y(self.margin_sv)
αs, y, X= self.αs(self.is_sv), self.y(self.is_sv), self.X(self.is_sv)
b = yₛ - np.sum(αs * y * self.kernel(X, xₛ, self.k), axis=0)
score = np.sum(αs * y * self.kernel(X, X_t, self.k), axis=0) + b
return np.sign(score).astype(int), score
@SVMClass
def multi_predict(self, X):
# get the predictions from all classifiers
preds = np.zeros((X.shape(0), self.k))
for i, clf in enumerate(self.clfs):
_, preds(:, i) = clf.predict(X)
# get the argmax and the corresponding score
return np.argmax(preds, axis=1)
@SVMClass
def evaluate(self, X,y):  
outputs, _ = self.predict(X)
accuracy = np.sum(outputs == y) / len(y)
return round(accuracy, 2)
from sklearn.datasets import make_classification
import numpy as np
# Load the dataset
np.random.seed(1)
X, y = make_classification(n_samples=500, n_features=2, 
n_redundant=0, n_informative=2, n_classes=4, 
n_clusters_per_class=1,  class_sep=0.3)
# Test SVM
svm = SVM(kernel='rbf', k=4)
svm.fit(X, y, eval_train=True)
y_pred = svm.predict(X)
print(f"Accuracy: {np.sum(y==y_pred)/y.shape(0)}")
# Test with Scikit
from sklearn.multiclass import OneVsRestClassifier
from sklearn.svm import SVC
clf = OneVsRestClassifier(SVC(kernel='rbf', C=1, gamma=4)).fit(X, y)
y_pred = clf.predict(X)
print(f"Accuracy: {sum(y==y_pred)/y.shape(0)}")

In sintesi, abbiamo implementato l’algoritmo di apprendimento Support Vector Machine (SVM), coprendo la sua forma generale a margine morbido e kernelizzata. Abbiamo fornito una panoramica di SVM, sviluppato il modello in codice, esteso per scenari multiclasse e convalidato la nostra implementazione utilizzando Sci-kit Learn.

Spero che ciò che hai imparato da questa storia possa essere utile per il tuo lavoro. Alla prossima, arrivederci.

Risorse:

Il codice è per lo più adattamenti rispetto a quello presente qui (LA MIA Licenza):
Persson, Aladino. “SVM from Scratch: Machine Learning Python (supporto Vector Machine).” Youtube.