Mașini cu vectori suport

Găsiți cea mai lată stradă dintre două clase. Aceasta este întreaga idee.

Tip: Construire Limbaj: Python Cerințe preliminare: Faza 1 (lecțiile 08 — Optimizare, 14 — Norme și distanțe și 18 — Optimizare convexă) Durată: ~90 de minute

Obiective de învățare

• Implementarea de la zero a unui SVM liniar folosind pierderea hinge și coborârea pe gradient asupra formulării primale
• Explicarea principiului marjei maxime și identificarea vectorilor suport dintr-un model antrenat
• Compararea nucleelor liniar, polinomial și RBF și explicarea modului în care artificiul nucleului evită transformarea explicită într-un spațiu cu multe dimensiuni
• Evaluarea compromisului controlat de parametrul C între lățimea marjei și erorile de clasificare

Problema

Aveți două clase de puncte de date și trebuie să trasați o dreaptă — sau un hiperplan — care să le separe. Ar putea funcționa o infinitate de drepte. Pe care ar trebui să o alegeți?

Pe cea cu marja cea mai mare. Marja este distanța dintre frontiera de decizie și cele mai apropiate puncte de date de pe fiecare parte. O marjă mai lată exprimă principiul conform căruia clasificatorul ar trebui să fie mai robust și să generalizeze mai bine pe date nevăzute.

Această intuiție conduce la mașinile cu vectori suport, unul dintre cei mai eleganți algoritmi din punct de vedere matematic în învățarea automată. SVM-urile au fost o metodă dominantă de clasificare înaintea învățării profunde și rămân o alegere competitivă pentru seturi de date mici, date cu multe dimensiuni și probleme în care este util un model principial, bine înțeles și susținut de rezultate teoretice.

SVM-urile se leagă direct de Faza 1: optimizarea este convexă (lecția 18), marja este măsurată cu norme (lecția 14), iar artificiul nucleului exploatează produsele scalare pentru a trata frontiere neliniare fără a calcula explicit coordonatele din spațiul cu multe dimensiuni.

Notă tehnică a traducerii: o marjă mai largă nu garantează singură o generalizare mai bună, iar SVM nu este în mod universal „cea mai bună alegere” pentru toate seturile mici sau cu multe dimensiuni. Rezultatul depinde de separabilitate, zgomot, nucleu, regularizare și selecția hiperparametrilor. Aceste formulări trebuie înțelese ca euristici de alegere a modelului, nu ca garanții absolute.

Conceptul

Clasificatorul cu marjă maximă

Pentru date separabile liniar, cu etichete y_i din {-1, +1} și vectori de caracteristici x_i, dorim un hiperplan w^T x + b = 0 care să separe clasele.

Distanța de la un punct x_i la hiperplan este:

distanța = |w^T x_i + b| / ||w||

Pentru un punct clasificat corect: y_i * (w^T x_i + b) > 0. Marja completă este de două ori distanța de la hiperplan la cel mai apropiat punct de pe fiecare parte.

Problema de optimizare este:

maximizează    2 / ||w||     (lățimea marjei)
cu condiția    y_i * (w^T x_i + b) >= 1  pentru orice i

Echivalent — minimizarea lui ||w||^2 este mai ușor de optimizat:

minimizează    (1/2) ||w||^2
cu condiția    y_i * (w^T x_i + b) >= 1  pentru orice i

Aceasta este o problemă de programare pătratică convexă, deci orice optim local este global. Punctele de date aflate exact pe frontierele marjei, unde y_i * (w^T x_i + b) = 1, sunt vectorii suport ai problemei cu marjă strictă. Ei determină frontiera de decizie; punctele cu restricții inactive nu contribuie direct la soluția duală.

Notă tehnică a traducerii: convexitatea garantează caracterul global al optimului, dar nu implică automat unicitatea tuturor variabilelor. Termenul strict convex în w face ca vectorul w optim să fie unic atunci când soluția există, însă interceptul b și coeficienții duali pot să nu fie unici în cazuri degenerate. Afirmația despre punctele aflate exact pe marjă se aplică formulării separabile cu marjă strictă; în SVM-ul cu marjă flexibilă, sunt vectori suport toate punctele cu coeficient dual nenul, inclusiv punctele din interiorul marjei sau clasificate greșit.

Vectorii suport: puținele puncte critice

Într-un SVM cu nucleu, funcția de decizie depinde numai de vectorii suport, nu de întregul set de antrenare. De aceea, dacă numărul vectorilor suport este redus, predicția poate necesita mai puțină memorie decât stocarea tuturor punctelor.

Numărul vectorilor suport apare și în anumite limite teoretice ale erorii de generalizare. Un raport mai mic între vectorii suport și dimensiunea setului de date poate fi un semn favorabil, dar nu este singur o garanție că modelul va generaliza mai bine.

Notă tehnică a traducerii: avantajul de memorie descris aici privește în special SVM-urile cu nucleu. Un clasificator SVM liniar poate stoca direct w și b, fără a păstra vectorii suport pentru predicție. Limitele de generalizare bazate pe numărul vectorilor suport sunt rezultate probabilistice cu ipoteze precise, nu o regulă universală potrivit căreia „mai puțini înseamnă întotdeauna mai bine”.

Marja flexibilă: tratarea zgomotului cu parametrul C

Datele reale sunt rareori perfect separabile. Unele puncte se pot afla pe partea greșită a frontierei sau în interiorul marjei. Formularea cu marjă flexibilă permite încălcări prin introducerea variabilelor de abatere.

minimizează    (1/2) ||w||^2 + C * sum(xi_i)
cu condiția    y_i * (w^T x_i + b) >= 1 - xi_i
               xi_i >= 0  pentru orice i

Variabila de abatere xi_i măsoară cât de mult încalcă punctul i marja. Parametrul C controlează compromisul:

Valoarea lui C	Comportament tipic
C mare	Penalizează puternic încălcările. Tinde către o marjă mai îngustă și mai puține erori de antrenare; poate supraînvăța
C mic	Permite mai multe încălcări. Tinde către o marjă mai lată și mai multe erori de antrenare; poate subînvăța

C este invers proporțional cu intensitatea regularizării. Un C mare înseamnă regularizare mai slabă, iar un C mic înseamnă regularizare mai puternică.

Notă tehnică a traducerii: efectele din tabel sunt tendințe, nu consecințe garantate pentru orice set de date. Lățimea marjei și numărul erorilor depind împreună de geometria datelor, nucleu și ceilalți hiperparametri; C trebuie ales prin validare.

Pierderea hinge: funcția de pierdere a SVM-ului

SVM-ul cu marjă flexibilă poate fi rescris ca o problemă de optimizare fără restricții:

minimizează    (1/2) ||w||^2 + C * sum(max(0, 1 - y_i * (w^T x_i + b)))

Termenul max(0, 1 - y_i * f(x_i)) este pierderea hinge. El este zero când punctul este clasificat corect și se află dincolo de marjă. Este liniar când punctul se află în interiorul marjei sau este clasificat greșit.

Pierderea hinge pentru un singur punct:

pierdere
  |
  | \
  |  \
  |   \
  |    \
  |     \_______________
  |
  +-----|-----|-------->  y * f(x)
       0     1

Pierdere zero când y*f(x) >= 1 (clasificare corectă, în afara marjei).
Penalizare liniară când y*f(x) < 1.

Comparați-o cu pierderea logistică, folosită în regresia logistică:

Hinge:      max(0, 1 - y*f(x))          Prag ferm la marjă
Logistică:  log(1 + exp(-y*f(x)))       Netedă, niciodată exact zero

Pierderea hinge face ca numai punctele aflate pe marjă sau în interiorul ei să aibă o contribuție nenulă la termenul de pierdere. Pierderea logistică atribuie o contribuție nenulă tuturor punctelor finite. În formularea duală cu nucleu, această proprietate conduce la o reprezentare bazată pe vectorii suport.

Notă tehnică a traducerii: „soluție rară” înseamnă aici coeficienți duali nuli pentru multe eșantioane, nu neapărat ponderi w rare. Economia de memorie la predicție se aplică reprezentării cu nucleu; un SVM liniar folosește în mod obișnuit direct vectorul de ponderi.

Antrenarea unui SVM liniar prin coborâre pe gradient

Puteți antrena un SVM liniar prin coborâre pe gradient asupra pierderii hinge cu regularizare L2, fără a rezolva problema pătratică cu restricții:

L(w, b) = (lambda/2) * ||w||^2 + (1/n) * sum(max(0, 1 - y_i * (w^T x_i + b)))

Contribuția la gradient în raport cu w pentru eșantionul i:
  Dacă y_i * (w^T x_i + b) >= 1:  dL_i/dw = lambda * w
  Dacă y_i * (w^T x_i + b) < 1:   dL_i/dw = lambda * w - y_i * x_i

Contribuția la gradient în raport cu b pentru eșantionul i:
  Dacă y_i * (w^T x_i + b) >= 1:  dL_i/db = 0
  Dacă y_i * (w^T x_i + b) < 1:   dL_i/db = -y_i

Aceasta se numește formularea primală. O epocă de actualizări pe eșantioane necesită O(n * d) operații aritmetice pentru date dense, unde n este numărul de eșantioane, iar d este numărul de caracteristici. Pentru date rare, cu multe dimensiuni, precum clasificarea textului, algoritmii liniari pot fi foarte rapizi.

Notă tehnică a traducerii: expresiile pe cazuri de mai sus sunt subgradienți pentru contribuția unui singur eșantion, potriviți unei actualizări stocastice. Gradientul termenului mediu din obiectivul complet trebuie să însumeze contribuțiile eșantioanelor active și să le împartă la n. În punctul exact y_i f(x_i) = 1, pierderea hinge nu este derivabilă și se alege un subgradient.

Formularea duală și artificiul nucleului

Dualul lagrangian al problemei SVM — pornind de la condițiile KKT din lecția 18 a Fazei 1 — este:

maximizează    sum(alpha_i) - (1/2) * sum_ij(alpha_i * alpha_j * y_i * y_j * (x_i . x_j))
cu condiția    0 <= alpha_i <= C
               sum(alpha_i * y_i) = 0

Dualul implică numai produsele scalare x_i . x_j dintre punctele de date. Aceasta este observația esențială. Înlocuiți fiecare produs scalar cu o funcție nucleu K(x_i, x_j), iar SVM-ul poate învăța frontiere neliniare fără a calcula vreodată explicit transformarea.

Nucleu liniar:       K(x, z) = x . z
Nucleu polinomial:   K(x, z) = (x . z + c)^d
RBF (gaussian):      K(x, z) = exp(-gamma * ||x - z||^2)

Nucleul RBF corespunde unui spațiu de caracteristici infinit-dimensional. Punctele apropiate în spațiul de intrare au o valoare a nucleului apropiată de 1. Punctele îndepărtate au o valoare apropiată de 0. Cu hiperparametri adecvați, el poate aproxima o gamă foarte largă de frontiere de decizie netede.

Artificiul nucleului calculează produsul scalar din spațiul cu multe dimensiuni fără a construi explicit coordonatele din acel spațiu. Pentru nucleul polinomial de grad d în D dimensiuni, numărul termenilor dintr-o reprezentare explicită crește combinatorial și este de ordinul O(D^d) când d este fix. Însă K(x, z) se calculează în O(D) pentru evaluarea directă a produsului scalar și a puterii scalare.

Notă tehnică a traducerii: caracterul universal al nucleului RBF este o proprietate de aproximare formulată sub ipoteze matematice și nu înseamnă că un SVM finit, cu orice valori C și gamma, va învăța automat orice frontieră netedă. Alegerea acestor hiperparametri este esențială.

SVM pentru regresie (SVR)

Regresia cu vectori suport ajustează în jurul datelor un tub cu lățimea controlată de epsilon. Punctele din interiorul tubului au pierdere zero. Punctele din exterior sunt penalizate liniar.

minimizează    (1/2) ||w||^2 + C * sum(xi_i + xi_i*)
cu condiția    y_i - (w^T x_i + b) <= epsilon + xi_i
               (w^T x_i + b) - y_i <= epsilon + xi_i*
               xi_i, xi_i* >= 0

Parametrul epsilon controlează lățimea tubului. Un tub mai lat tinde să producă mai puțini vectori suport și o ajustare mai netedă. Un tub mai îngust tinde să producă mai mulți vectori suport și o ajustare mai fidelă datelor.

De ce SVM-urile au fost depășite de învățarea profundă și când rămân utile

SVM-urile au dominat multe aplicații ale învățării automate de la sfârșitul anilor 1990 până la începutul anilor 2010. Învățarea profundă le-a depășit în numeroase domenii din câteva motive:

Factor	SVM-uri	Învățare profundă
Ingineria caracteristicilor	O necesită adesea	Poate învăța reprezentări
Scalabilitate	Metodele cu nucleu cresc cel puțin pătratic în numărul eșantioanelor în implementări uzuale	Antrenarea mini-batch poate crește aproximativ liniar pe epocă
Imagini/text/audio	Necesită adesea caracteristici proiectate	Poate învăța din date brute
Seturi de date mari (>100.000)	SVM-ul cu nucleu poate fi lent	Se scalează adesea mai bine
Accelerare pe GPU	Beneficiu dependent de implementare	Accelerare substanțială în ecosistemele moderne

SVM-urile rămân competitive în situații precum:

• seturi de date mici, de la sute la câteva mii de eșantioane;
• date rare, cu multe dimensiuni, precum texte reprezentate prin TF-IDF;
• situații în care sunt utile rezultate teoretice despre marjă;
• situații în care timpul de antrenare trebuie să fie redus și un SVM liniar este potrivit;
• clasificare binară cu o structură clară a marjei;
• detectarea anomaliilor cu un SVM cu o singură clasă.

Notă tehnică a traducerii: complexitatea O(n^2)–O(n^3) se referă la solvere SVM cu nucleu și depinde și de numărul caracteristicilor, de cache și de date. Documentația scikit-learn indică pentru implementarea bazată pe libsvm un interval practic între O(n_features * n_samples^2) și O(n_features * n_samples^3), în timp ce metodele liniare precum LinearSVC se pot scala aproape liniar. Consultați secțiunea oficială despre complexitate.

svm-margin

Construiți

Pasul 1: pierderea hinge și gradientul

Începeți cu baza: calculați pierderea hinge pentru un lot și gradientul acesteia.

def hinge_loss(X, y, w, b):
    n = len(X)
    total_loss = 0.0
    for i in range(n):
        margin = y[i] * (dot(w, X[i]) + b)
        total_loss += max(0.0, 1.0 - margin)
    return total_loss / n

Pasul 2: SVM liniar prin coborâre pe gradient

Antrenați modelul minimizând pierderea hinge regularizată. Nu este necesar un solver de programare pătratică.

class LinearSVM:
    def __init__(self, lr=0.001, lambda_param=0.01, n_epochs=1000):
        self.lr = lr
        self.lambda_param = lambda_param
        self.n_epochs = n_epochs
        self.w = None
        self.b = 0.0

    def fit(self, X, y):
        n_features = len(X[0])
        self.w = [0.0] * n_features
        self.b = 0.0

        for epoch in range(self.n_epochs):
            for i in range(len(X)):
                margin = y[i] * (dot(self.w, X[i]) + self.b)
                if margin >= 1:
                    self.w = [wj - self.lr * self.lambda_param * wj
                              for wj in self.w]
                else:
                    self.w = [wj - self.lr * (self.lambda_param * wj - y[i] * X[i][j])
                              for j, wj in enumerate(self.w)]
                    self.b -= self.lr * (-y[i])

    def predict(self, X):
        return [1 if dot(self.w, x) + self.b >= 0 else -1 for x in X]

Pasul 3: funcții nucleu

Implementați nucleele liniar, polinomial și RBF.

def linear_kernel(x, z):
    return dot(x, z)

def polynomial_kernel(x, z, degree=3, c=1.0):
    return (dot(x, z) + c) ** degree

def rbf_kernel(x, z, gamma=0.5):
    diff = [xi - zi for xi, zi in zip(x, z)]
    return math.exp(-gamma * dot(diff, diff))

Pasul 4: identificarea marjei și a vectorilor suport

După antrenare, identificați punctele aflate aproximativ pe frontiera marjei.

def find_support_vectors(X, y, w, b, tol=1e-3):
    support_vectors = []
    for i in range(len(X)):
        margin = y[i] * (dot(w, X[i]) + b)
        if abs(margin - 1.0) < tol:
            support_vectors.append(i)
    return support_vectors

Consultați code/svm.py pentru implementarea completă și toate demonstrațiile.

Notă tehnică a traducerii: fragmentele nu sunt autonome: funcția dot nu este definită, iar pentru nucleul RBF lipsește import math. În plus, funcția din pasul 4 nu calculează lățimea marjei 2 / ||w|| și găsește numai punctele cu y_i f(x_i) aproximativ egal cu 1. Pentru un SVM cu marjă flexibilă, vectorii suport pot avea y_i f(x_i) <= 1, inclusiv puncte din interiorul marjei și puncte clasificate greșit; identificarea exactă se face în mod obișnuit prin coeficienții duali nenuli.

Folosiți

Cu scikit-learn:

from sklearn.svm import SVC, LinearSVC, SVR
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm", SVC(kernel="rbf", C=1.0, gamma="scale")),
])
clf.fit(X_train, y_train)
print(f"Accuracy: {clf.score(X_test, y_test):.4f}")
print(f"Support vectors: {clf['svm'].n_support_}")

Important: este foarte recomandat să scalați caracteristicile înainte de antrenarea unui SVM. SVM-urile sunt sensibile la magnitudinea caracteristicilor deoarece marja depinde de ||w||, iar scările foarte diferite distorsionează geometria. Aceeași transformare învățată pe datele de antrenare trebuie aplicată și datelor de test; conducta de mai sus face acest lucru în siguranță.

Pentru seturi de date mari și un model liniar, folosiți LinearSVC, care se scalează de regulă mult mai bine decât SVC cu nucleu:

from sklearn.svm import LinearSVC

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("svm", LinearSVC(C=1.0, max_iter=10000)),
])

Notă tehnică a traducerii: LinearSVC nu folosește în mod obligatoriu formularea primală. În scikit-learn actual, parametrul implicit dual="auto" alege între solverul primal și cel dual pe baza numărului de eșantioane, a numărului de caracteristici și a configurației. De asemenea, pierderea implicită este squared_hinge, nu hinge. Consultați documentația oficială LinearSVC.

Exerciții

1. Generați un set de date bidimensional separabil liniar. Antrenați clasa dumneavoastră LinearSVM și identificați vectorii suport. Verificați că vectorii suport ai soluției cu marjă strictă sunt punctele cele mai apropiate de frontiera de decizie.

2. Variați C între 0,001 și 1.000 pe un set de date zgomotos. Reprezentați frontiera de decizie pentru fiecare valoare C. Observați tranziția tipică de la o marjă largă, cu risc de subînvățare, la o marjă îngustă, cu risc de supraînvățare.

3. Creați un set de date în care frontierele claselor sunt circulare, deci nu liniare. Arătați că un SVM liniar eșuează. Calculați matricea nucleului RBF și arătați că clasele pot fi separate în spațiul caracteristicilor indus de nucleu.

4. Comparați pierderea hinge cu pierderea logistică pe același set de date. Antrenați un SVM liniar și o regresie logistică. Numărați câte puncte de antrenare au o contribuție nenulă la termenul de pierdere al fiecărui model: punctele de pe marjă sau din interiorul ei pentru SVM, respectiv toate punctele finite pentru regresia logistică.

5. Implementați SVR cu pierdere insensibilă în intervalul epsilon. Ajustați modelul pentru y = sin(x) + zgomot. Reprezentați tubul epsilon în jurul predicțiilor și evidențiați vectorii suport, inclusiv punctele de pe frontiera tubului sau din afara lui.

Termeni-cheie

Termen	Ce înseamnă de fapt
Vectori suport	Punctele de antrenare cu coeficienți duali nenuli; în cazul separabil se află pe marginile cele mai apropiate de frontiera de decizie și determină hiperplanul
Marjă	Distanța dintre frontiera de decizie și cei mai apropiați vectori suport. SVM-urile maximizează această distanță în formularea cu marjă strictă
Pierdere hinge	max(0, 1 - y*f(x)). Este zero pentru o clasificare corectă dincolo de marjă și aplică altfel o penalizare liniară
Parametrul C	Compromisul dintre lățimea marjei și erorile de clasificare. Un C mare înseamnă regularizare mai slabă, iar un C mic, regularizare mai puternică
Marjă flexibilă	Formulare SVM care permite încălcări ale marjei prin variabile de abatere și tratează date neseparabile
Artificiul nucleului	Calcularea produselor scalare într-un spațiu de caracteristici cu multe dimensiuni fără transformarea explicită în acel spațiu
Nucleu liniar	K(x, z) = x . z. Echivalent cu produsul scalar obișnuit; produce o frontieră liniară
Nucleu RBF	K(x, z) = exp(-gamma * ||x-z||^2). Corespunde unui spațiu infinit-dimensional și poate modela frontiere neliniare flexibile
Nucleu polinomial	K(x, z) = (x . z + c)^d. Corespunde unui spațiu de caracteristici format din combinații polinomiale
Formulare duală	Reformularea problemei SVM în funcție numai de produse scalare între punctele de date; permite folosirea nucleelor
SVR	Regresie cu vectori suport. Ajustează în jurul datelor un tub epsilon; punctele din interiorul tubului au pierdere zero
Variabile de abatere	xi_i măsoară cât încalcă un punct marja; este zero pentru punctele clasificate corect dincolo de marjă
Marjă maximă	Principiul alegerii hiperplanului care maximizează distanța față de cele mai apropiate puncte ale fiecărei clase

Lecturi suplimentare

• Vapnik: The Nature of Statistical Learning Theory (1995) — textul fundamental despre SVM-uri și învățarea statistică
• Cortes și Vapnik: Support-vector networks (1995) — lucrarea originală despre SVM
• Platt: Sequential Minimal Optimization (1998) — algoritmul SMO care a făcut practică antrenarea SVM-urilor
• Documentația scikit-learn despre SVM — ghid practic cu detalii de implementare
• LIBSVM: A Library for Support Vector Machines — biblioteca C++ aflată la baza multor implementări SVM

---

Sursă: Support Vector Machines — original

Navigare: înapoi: 02.04 — Arbori de decizie și păduri aleatoare · Faza 2 — Bazele învățării automate · Catalog complet · în continuare: 02.06 — Cei mai apropiați k vecini și distanțe.