Che ruolo giocano i vettori di supporto nel definire il confine decisionale di una SVM e come vengono identificati durante il processo di formazione?

/ / Pubblicato in Intelligenza Artificiale, Apprendimento automatico EITC/AI/MLP con Python, Supporta la macchina vettoriale, Completare SVM da zero, Revisione d'esame

Le Support Vector Machine (SVM) sono una classe di modelli di apprendimento supervisionato utilizzati per la classificazione e l'analisi di regressione. Il concetto fondamentale alla base delle SVM è trovare l'iperpiano ottimale che separi al meglio i punti dati di classi diverse. I vettori di supporto sono elementi importanti nella definizione di questo confine decisionale. Questa risposta chiarirà il ruolo dei vettori di supporto nelle SVM, la loro identificazione durante il processo di training e fornirà una comprensione completa del loro significato.

Ruolo dei vettori di supporto nella definizione del confine decisionale

In una SVM, il confine decisionale è un iperpiano che separa le classi di punti dati. L’iperpiano ottimale è quello che massimizza il margine tra le classi. Il margine è definito come la distanza tra l'iperpiano e i punti dati più vicini di entrambe le classi. Questi punti dati più vicini sono noti come vettori di supporto. Sono fondamentali perché influenzano direttamente la posizione e l'orientamento dell'iperpiano.

1. Massimizzazione del margine: L'obiettivo principale di un SVM è massimizzare il margine tra le classi. Il margine è definito dalla distanza dai vettori di supporto più vicini. Massimizzando questo margine, la SVM mira a migliorare la capacità di generalizzazione del modello, riducendo così la probabilità di overfitting.

2. Definizione dell'iperpiano: L'equazione dell'iperpiano in uno spazio bidimensionale può essere scritta come w \cpunto x + b = 0Durante la serata, w è il vettore dei pesi, x è il vettore di input e b è il termine bias. I vettori di supporto sono i punti dati che si trovano più vicini all'iperpiano e soddisfano la condizione y_i (w \cdot x_i + b) = 1Durante la serata, sì_io è l'etichetta della classe del vettore di supporto x_i. Questi punti sono critici perché definiscono i parametri w e b dell'iperpiano.

3. Influenzare il confine della decisione: Se i vettori di supporto vengono spostati, la posizione dell'iperpiano cambierà. Questo perché i vettori di supporto sono i punti utilizzati per calcolare il margine. Altri punti dati che non sono vettori di supporto non influiscono direttamente sul confine decisionale.

Identificazione dei vettori di supporto durante l'allenamento

Il processo di addestramento di una SVM prevede la risoluzione di un problema di ottimizzazione quadratica con vincoli. L'obiettivo è trovare il vettore dei pesi w e pregiudizio b che massimizzano il margine classificando correttamente i dati di addestramento. Questo può essere formulato come:

    \[ \min_{w, b} \frac{1}{2} \|w\|^2 \]

    \[ \text{soggetto a } y_i (w \cdot x_i + b) \geq 1, \forall i \]

Questo problema di ottimizzazione può essere risolto utilizzando tecniche come l'algoritmo Sequential Minimal Optimization (SMO) o utilizzando solutori di programmazione quadratica. Durante questo processo, i vettori di supporto sono identificati come segue:

1. Moltiplicatori di Lagrange: Il problema di ottimizzazione viene spesso risolto utilizzando il metodo dei moltiplicatori di Lagrange. La forma duale del problema di ottimizzazione introduce i moltiplicatori di Lagrange \alpha_i per ciascun vincolo. Il duplice problema è dato da:

    \[ \max_{\alpha} \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{ n} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) \]

    \[ \text{soggetto a } \sum_{i=1}^{n} \alpha_i y_i = 0 \]

    \[ \text{and } 0 \leq \alpha_i \leq C, \forall i \]

where C è un parametro di regolarizzazione che controlla il compromesso tra la massimizzazione del margine e la minimizzazione dell'errore di classificazione.

2. Supporta l'identificazione dei vettori: I vettori di supporto sono i punti dati per i quali corrispondono i moltiplicatori di Lagrange \alpha_i sono diversi da zero. Questi punti si trovano al margine e soddisfano la condizione y_i (w \cdot x_i + b) = 1. Il vettore dei pesi w può essere espresso in termini di vettori di supporto come:

    \[ w = \sum_{i=1}^{n} \alpha_i y_i x_i \]

3. Calcolo del termine di polarizzazione: Il termine bias b viene calcolato utilizzando i vettori di supporto. Per qualsiasi vettore di supporto x_i, la distorsione può essere calcolata come:

    \[ b = y_i - \sum_{j=1}^{n} \alpha_j y_j (x_j \cdot x_i) \]

Ciò garantisce che l'iperpiano classifichi correttamente i vettori di supporto.

Esempio

Consideriamo un semplice set di dati bidimensionale con due classi. I punti dati possono essere rappresentati come segue:

Classe 1: (1, 2), (2, 3), (3, 3)
Classe 2: (6, 6), (7, 7), (8, 8)

L'obiettivo dell'SVM è trovare l'iperpiano ottimale che separa queste due classi. Durante il processo di addestramento, l'SVM identifica i vettori di supporto, che sono i punti più vicini all'iperpiano. In questo caso, i vettori di supporto potrebbero essere (3, 3) dalla Classe 1 e (6, 6) dalla Classe 2. Questi punti verranno utilizzati per definire l'iperpiano e calcolare il margine.

Formulazione matematica

La forma primordiale del problema di ottimizzazione SVM è:

    \[ \min_{w, b} \frac{1}{2} \|w\|^2 \]

    \[ \text{soggetto a } y_i (w \cdot x_i + b) \geq 1, \forall i \]

La forma duale è:

    \[ \max_{\alpha} \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{ n} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) \]

    \[ \text{soggetto a } \sum_{i=1}^{n} \alpha_i y_i = 0 \]

    \[ \text{and } 0 \leq \alpha_i \leq C, \forall i \]

I vettori di supporto sono identificati dai moltiplicatori di Lagrange diversi da zero \alpha_i. Il vettore dei pesi w è calcolato come:

    \[ w = \sum_{i=1}^{n} \alpha_i y_i x_i \]

Il termine pregiudiziale b viene calcolato utilizzando i vettori di supporto:

    \[ b = y_i - \sum_{j=1}^{n} \alpha_j y_j (x_j \cdot x_i) \]

Implementazione in Python

Per implementare una SVM da zero in Python, seguire questi passaggi:

1. Preparazione dei dati: carica e preelabora il set di dati.
2. Funzione del nocciolo: Definire la funzione del kernel (ad esempio, lineare, polinomiale, RBF).
3. OTTIMIZZAZIONE: Risolvi il problema di ottimizzazione doppia utilizzando un risolutore di programmazione quadratica o un algoritmo iterativo come SMO.
4. Supporta l'identificazione dei vettori: Identificare i vettori di supporto in base ai moltiplicatori di Lagrange.
5. Calcolo dell'iperpiano: Calcola il vettore del peso w e termine di pregiudizio b.
6. Predizione: Utilizza l'iperpiano per classificare nuovi punti dati.

Ecco un'implementazione semplificata di una SVM lineare da zero:

python
import numpy as np
from cvxopt import matrix, solvers

class SVM:
    def __init__(self, C=1.0):
        self.C = C
        self.w = None
        self.b = None
        self.support_vectors = None

    def fit(self, X, y):
        n_samples, n_features = X.shape

        # Calculate the Gram matrix
        K = np.dot(X, X.T)

        # Set up the parameters for the quadratic programming solver
        P = matrix(np.outer(y, y) * K)
        q = matrix(-np.ones(n_samples))
        G = matrix(np.vstack((-np.eye(n_samples), np.eye(n_samples))))
        h = matrix(np.hstack((np.zeros(n_samples), np.ones(n_samples) * self.C)))
        A = matrix(y, (1, n_samples), 'd')
        b = matrix(0.0)

        # Solve the quadratic programming problem
        solution = solvers.qp(P, q, G, h, A, b)
        alphas = np.ravel(solution['x'])

        # Identify the support vectors
        support_vector_indices = alphas > 1e-5
        self.support_vectors = X[support_vector_indices]
        self.alphas = alphas[support_vector_indices]
        self.sv_y = y[support_vector_indices]

        # Calculate the weight vector
        self.w = np.sum(self.alphas[:, None] * self.sv_y[:, None] * self.support_vectors, axis=0)

        # Calculate the bias term
        self.b = np.mean(self.sv_y - np.dot(self.support_vectors, self.w))

    def predict(self, X):
        return np.sign(np.dot(X, self.w) + self.b)

# Example usage
X = np.array([[1, 2], [2, 3], [3, 3], [6, 6], [7, 7], [8, 8]])
y = np.array([-1, -1, -1, 1, 1, 1])

svm = SVM(C=1.0)
svm.fit(X, y)
predictions = svm.predict(X)
print(predictions)

In questo esempio, la classe "SVM" definisce il modello SVM e il metodo "fit" addestra il modello risolvendo il problema di ottimizzazione doppia. I vettori di supporto vengono identificati in base ai moltiplicatori di Lagrange e il vettore del peso e il termine di bias vengono calcolati di conseguenza. Il metodo "predict" viene quindi utilizzato per classificare nuovi punti dati. I vettori di supporto svolgono un ruolo fondamentale nella definizione del confine decisionale di una SVM. Sono i punti dati che si trovano più vicini all'iperpiano e ne influenzano direttamente la posizione e l'orientamento. Durante il processo di addestramento, i vettori di supporto vengono identificati attraverso l'ottimizzazione della funzione obiettivo SVM e vengono utilizzati per calcolare il vettore dei pesi e il termine di bias che definiscono l'iperpiano. Comprendere il significato dei vettori di supporto è essenziale per comprendere come le SVM raggiungono i loro obiettivi di classificazione e per implementare le SVM da zero in Python.

Altre domande e risposte recenti riguardanti Completare SVM da zero:

Altre domande e risposte:

Etichettato sotto: , , , , ,