Formulação Matemática do SVM: Fundamentos teóricos e implementação

Compreendendo os Fundamentos Matemáticos dos Support Vector Machines

O tópico 1.4.7. Mathematical formulation descreve os princípios matemáticos que fundamentam os Support Vector Machines. Esta seção é crucial para entender como o SVM encontra o hiperplano ótimo que separa diferentes classes nos dados.

Formulação do Problema de Otimização

Primeiramente, o SVM resolve um problema de otimização convexa. Para dados linearmente separáveis, o objetivo é encontrar o hiperplano que maximiza a margem entre as classes. A formulação primal é expressa como:

\(\min_{w, b} \frac{1}{2} \|w\|^2\)

sujeito a:

\(y_i (w \cdot x_i + b) \geq 1 \quad \forall i\)

onde w é o vetor de pesos e b é o viés.

Problema Dual e Multiplicadores de Lagrange

Certamente, a formulação dual é mais eficiente computacionalmente. Através dos multiplicadores de Lagrange, transformamos o problema em:

\(\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\)

sujeito a:

\(\sum_{i=1}^n \alpha_i y_i = 0 \quad \text{e} \quad 0 \leq \alpha_i \leq C\)

import numpy as np
from sklearn.svm import SVC
from sklearn.datasets import make_classification
import cvxopt

# Implementação manual do problema dual
def svm_dual_manual(X, y, C=1.0):
    n_samples, n_features = X.shape
    
    # Matriz do kernel linear
    K = np.dot(X, X.T)
    
    # Configuração do problema de otimização quadrática
    P = cvxopt.matrix(np.outer(y, y) * K)
    q = cvxopt.matrix(-np.ones(n_samples))
    
    # Restrições de desigualdade
    G = cvxopt.matrix(np.vstack((-np.eye(n_samples), np.eye(n_samples))))
    h = cvxopt.matrix(np.hstack((np.zeros(n_samples), np.ones(n_samples) * C)))
    
    # Restrição de igualdade
    A = cvxopt.matrix(y, (1, n_samples))
    b = cvxopt.matrix(0.0)
    
    # Resolvendo o problema
    solution = cvxopt.solvers.qp(P, q, G, h, A, b)
    alphas = np.array(solution['x']).flatten()
    
    return alphas

# Gerando dados de exemplo
X, y = make_classification(n_samples=100, n_features=2, n_classes=2, 
                          n_redundant=0, n_informative=2, random_state=42)
y = 2 * y - 1  # Convertendo para -1, 1

# Calculando alphas
alphas = svm_dual_manual(X, y, C=1.0)
print("Multiplicadores de Lagrange calculados:")
print(f"Número de vetores suporte: {np.sum(alphas > 1e-5)}")

import numpy as np

from sklearn.svm import SVC

from sklearn.datasets import make_classification

import cvxopt

# Implementação manual do problema dual

def svm_dual_manual(X, y, C=1.0):

n_samples, n_features = X.shape

# Matriz do kernel linear

K = np.dot(X, X.T)

# Configuração do problema de otimização quadrática

P = cvxopt.matrix(np.outer(y, y) * K)

q = cvxopt.matrix(-np.ones(n_samples))

# Restrições de desigualdade

G = cvxopt.matrix(np.vstack((-np.eye(n_samples), np.eye(n_samples))))

h = cvxopt.matrix(np.hstack((np.zeros(n_samples), np.ones(n_samples) * C)))

# Restrição de igualdade

A = cvxopt.matrix(y, (1, n_samples))

b = cvxopt.matrix(0.0)

# Resolvendo o problema

solution = cvxopt.solvers.qp(P, q, G, h, A, b)

alphas = np.array(solution['x']).flatten()

return alphas

# Gerando dados de exemplo

X, y = make_classification(n_samples=100, n_features=2, n_classes=2,

n_redundant=0, n_informative=2, random_state=42)

y = 2 * y - 1 # Convertendo para -1, 1

# Calculando alphas

alphas = svm_dual_manual(X, y, C=1.0)

print("Multiplicadores de Lagrange calculados:")

print(f"Número de vetores suporte: {np.sum(alphas > 1e-5)}")

Casos Não Linearmente Separáveis

Conquanto a formulação anterior assuma separabilidade linear, dados reais frequentemente exigem abordagens mais sofisticadas. Para lidar com sobreposição de classes, introduzimos variáveis de folga (slack variables):

\(\min_{w, b, \xi} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^n \xi_i\)

sujeito a:

\(y_i (w \cdot x_i + b) \geq 1 – \xi_i \quad \text{e} \quad \xi_i \geq 0 \quad \forall i\)

O Parâmetro C e Controle de Complexidade

Embora a variável de folga permita violações da margem, decerto o parâmetro C controla o trade-off entre margem máxima e erro de classificação. Portanto, valores altos de C resultam em margens mais estreitas com menos violações.

from sklearn.svm import SVC
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

# Demonstrando o efeito do parâmetro C
X, y = make_blobs(n_samples=100, centers=2, cluster_std=2.0, random_state=42)

C_values = [0.1, 1, 10, 100]
fig, axes = plt.subplots(2, 2, figsize=(12, 10))

for ax, C in zip(axes.ravel(), C_values):
    svm_model = SVC(kernel='linear', C=C)
    svm_model.fit(X, y)
    
    # Plotando decisão boundary
    ax.scatter(X[:, 0], X[:, 1], c=y, cmap='bwr', alpha=0.6)
    
    # Criando grid para decision boundary
    xx, yy = np.meshgrid(np.linspace(X[:, 0].min()-1, X[:, 0].max()+1, 50),
                         np.linspace(X[:, 1].min()-1, X[:, 1].max()+1, 50))
    Z = svm_model.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    
    ax.contour(xx, yy, Z, colors='black', alpha=0.8)
    ax.set_title(f'SVM com C={C}')
    ax.set_xlabel('Feature 1')
    ax.set_ylabel('Feature 2')

plt.tight_layout()
plt.show()

from sklearn.svm import SVC

import matplotlib.pyplot as plt

from sklearn.datasets import make_blobs

# Demonstrando o efeito do parâmetro C

X, y = make_blobs(n_samples=100, centers=2, cluster_std=2.0, random_state=42)

C_values = [0.1, 1, 10, 100]

fig, axes = plt.subplots(2, 2, figsize=(12, 10))

for ax, C in zip(axes.ravel(), C_values):

svm_model = SVC(kernel='linear', C=C)

svm_model.fit(X, y)

# Plotando decisão boundary

ax.scatter(X[:, 0], X[:, 1], c=y, cmap='bwr', alpha=0.6)

# Criando grid para decision boundary

xx, yy = np.meshgrid(np.linspace(X[:, 0].min()-1, X[:, 0].max()+1, 50),

np.linspace(X[:, 1].min()-1, X[:, 1].max()+1, 50))

Z = svm_model.predict(np.c_[xx.ravel(), yy.ravel()])

Z = Z.reshape(xx.shape)

ax.contour(xx, yy, Z, colors='black', alpha=0.8)

ax.set_title(f'SVM com C={C}')

ax.set_xlabel('Feature 1')

ax.set_ylabel('Feature 2')

plt.tight_layout()

plt.show()

Kernel Trick e Espaços de Características

Atualmente, o kernel trick é uma das contribuições mais importantes dos SVMs. Aliás, esta técnica permite operar em espaços de alta dimensão sem computar explicitamente as coordenadas:

\(\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 K(x_i, x_j)\)

onde K(x_i, x_j) é a função kernel.

Implementação com Diferentes Kernels

Enquanto o kernel linear é fundamental, igualmente importantes são os kernels não lineares:

from sklearn.svm import SVC
from sklearn.datasets import make_circles
from sklearn.model_selection import cross_val_score

# Comparando diferentes kernels
X, y = make_circles(n_samples=200, noise=0.1, factor=0.3, random_state=42)

kernels = ['linear', 'poly', 'rbf', 'sigmoid']
results = {}

for kernel in kernels:
    if kernel == 'poly':
        svm_model = SVC(kernel=kernel, degree=3)
    else:
        svm_model = SVC(kernel=kernel)
    
    scores = cross_val_score(svm_model, X, y, cv=5, scoring='accuracy')
    results[kernel] = scores.mean()
    print(f"Kernel {kernel}: Acurácia média = {scores.mean():.4f}")

print("\nMelhor kernel:", max(results, key=results.get))

from sklearn.svm import SVC

from sklearn.datasets import make_circles

from sklearn.model_selection import cross_val_score

# Comparando diferentes kernels

X, y = make_circles(n_samples=200, noise=0.1, factor=0.3, random_state=42)

kernels = ['linear', 'poly', 'rbf', 'sigmoid']

results = {}

for kernel in kernels:

if kernel == 'poly':

svm_model = SVC(kernel=kernel, degree=3)

else:

svm_model = SVC(kernel=kernel)

scores = cross_val_score(svm_model, X, y, cv=5, scoring='accuracy')

results[kernel] = scores.mean()

print(f"Kernel {kernel}: Acurácia média = {scores.mean():.4f}")

print("\nMelhor kernel:", max(results, key=results.get))

Vetores Suporte e Decisão

Surpreendentemente, apenas um subconjunto dos pontos de treinamento influencia a decisão final. Estes são os support vectors, que satisfazem:

\(y_i (w \cdot x_i + b) = 1\)

A função de decisão é então:

\(f(x) = \sum_{i \in SV} \alpha_i y_i K(x_i, x) + b\)

Extraindo Vetores Suporte

from sklearn.svm import SVC
import numpy as np

# Extraindo informações dos vetores suporte
X, y = make_classification(n_samples=100, n_features=4, random_state=42)

svm_model = SVC(kernel='linear', C=1.0)
svm_model.fit(X, y)

# Informações dos vetores suporte
support_vectors = svm_model.support_vectors_
support_indices = svm_model.support_
dual_coef = svm_model.dual_coef_

print(f"Número de vetores suporte: {len(support_vectors)}")
print(f"Shape dos coeficientes duais: {dual_coef.shape}")
print(f"Intercept (b): {svm_model.intercept_}")

# Função de decisão para novos pontos
X_new = np.random.randn(5, 4)
decision_function = svm_model.decision_function(X_new)
print(f"Valores da função de decisão: {decision_function}")

from sklearn.svm import SVC

import numpy as np

# Extraindo informações dos vetores suporte

X, y = make_classification(n_samples=100, n_features=4, random_state=42)

svm_model = SVC(kernel='linear', C=1.0)

svm_model.fit(X, y)

# Informações dos vetores suporte

support_vectors = svm_model.support_vectors_

support_indices = svm_model.support_

dual_coef = svm_model.dual_coef_

print(f"Número de vetores suporte: {len(support_vectors)}")

print(f"Shape dos coeficientes duais: {dual_coef.shape}")

print(f"Intercept (b): {svm_model.intercept_}")

# Função de decisão para novos pontos

X_new = np.random.randn(5, 4)

decision_function = svm_model.decision_function(X_new)

print(f"Valores da função de decisão: {decision_function}")

Implementação Numérica e Estabilidade

Contudo, a implementação prática requer cuidados numéricos. Assim, o Scikit-Learn emprega algoritmos especializados:

LIBSVM para problemas de classificação
LIBLINEAR para problemas lineares em grande escala
Otimização de cache para grandes conjuntos de dados

Comparação de Solvers

from sklearn.svm import SVC
import time
from sklearn.datasets import make_classification

# Gerando dataset grande
X_large, y_large = make_classification(n_samples=10000, n_features=20, random_state=42)

# Comparando tempos de treinamento
solvers = ['liblinear', 'saga']  # Para problemas lineares

for solver in solvers:
    start_time = time.time()
    
    svm_model = SVC(kernel='linear', max_iter=1000, random_state=42)
    svm_model.fit(X_large, y_large)
    
    training_time = time.time() - start_time
    print(f"Solver: {solver}, Tempo: {training_time:.2f} segundos")
    print(f"Número de iterações: {svm_model.n_iter_}")

from sklearn.svm import SVC

import time

from sklearn.datasets import make_classification

# Gerando dataset grande

X_large, y_large = make_classification(n_samples=10000, n_features=20, random_state=42)

# Comparando tempos de treinamento

solvers = ['liblinear', 'saga'] # Para problemas lineares

for solver in solvers:

start_time = time.time()

svm_model = SVC(kernel='linear', max_iter=1000, random_state=42)

svm_model.fit(X_large, y_large)

training_time = time.time() - start_time

print(f"Solver: {solver}, Tempo: {training_time:.2f} segundos")

print(f"Número de iterações: {svm_model.n_iter_}")

Extensões e Variações do SVM

Inegavelmente, a formulação básica do SVM inspirou diversas variações. Então, considere estas extensões importantes:

SVR (Support Vector Regression) para problemas de regressão
One-Class SVM para detecção de anomalias
Nu-SVM com controle direto do número de vetores suporte

Exemplo com Support Vector Regression

from sklearn.svm import SVR
from sklearn.datasets import make_regression
from sklearn.metrics import mean_squared_error, r2_score

# Problema de regressão com SVR
X_reg, y_reg = make_regression(n_samples=200, n_features=2, noise=0.1, random_state=42)

svr_model = SVR(kernel='rbf', C=1.0, epsilon=0.1)
svr_model.fit(X_reg, y_reg)

y_pred = svr_model.predict(X_reg)
mse = mean_squared_error(y_reg, y_pred)
r2 = r2_score(y_reg, y_pred)

print(f"Support Vector Regression - MSE: {mse:.4f}, R²: {r2:.4f}")
print(f"Número de vetores suporte: {len(svr_model.support_vectors_)}")

from sklearn.svm import SVR

from sklearn.datasets import make_regression

from sklearn.metrics import mean_squared_error, r2_score

# Problema de regressão com SVR

X_reg, y_reg = make_regression(n_samples=200, n_features=2, noise=0.1, random_state=42)

svr_model = SVR(kernel='rbf', C=1.0, epsilon=0.1)

svr_model.fit(X_reg, y_reg)

y_pred = svr_model.predict(X_reg)

mse = mean_squared_error(y_reg, y_pred)

r2 = r2_score(y_reg, y_pred)

print(f"Support Vector Regression - MSE: {mse:.4f}, R²: {r2:.4f}")

print(f"Número de vetores suporte: {len(svr_model.support_vectors_)}")

Conclusão e Perspectivas Futuras

Enfim, a formulação matemática do SVM representa um marco no machine learning. Inegavelmente, sua base teórica sólida combinada com implementações eficientes explica sua popularidade duradoura.

Afinal, compreender os fundamentos matemáticos permite não apenas usar efetivamente os SVMs, mas também adaptá-los para problemas específicos. Eventualmente, este conhecimento facilita a transição para métodos mais avançados.

Portanto, domine estes conceitos fundamentais. Inclusive para desenvolver intuição sobre quando e como aplicar Support Vector Machines em problemas do mundo real.

Indice