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\)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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.