Métodos de Kernel

O que são métodos de kernel?

Métodos de kernel (kernel methods) são uma família de algoritmos que aprendem funções de decisão não lineares ao trabalhar com uma representação implícita (frequentemente de dimensão muito alta) de atributos — sem nunca calcular explicitamente essa representação. Eles fazem isso por meio de uma função kernel (kernel function) que mede a similaridade entre pares de entradas.

Os métodos de kernel ficam em um ponto de equilíbrio entre modelos lineares clássicos (rápidos, interpretáveis, não linearidades limitadas) e modelos modernos flexíveis como Redes Neurais (alta capacidade, mais ajuste fino, mais famintos por dados). Eles são especialmente eficazes quando:

  • O conjunto de dados é pequeno a médio (centenas a dezenas de milhares de pontos).
  • Você quer forte desempenho não linear com boa base teórica.
  • Você precisa de otimização convexa (convex optimization) (por exemplo, SVMs) ou incerteza bem fundamentada (processos gaussianos).

Algoritmos comuns de métodos de kernel incluem:

  • Máquinas de Vetores de Suporte (Support Vector Machines, SVMs) para classificação e regressão (veja Máquinas de Vetores de Suporte)
  • Regressão de crista com kernel (kernel ridge regression, KRR) para regressão (e classificação via regressão)
  • Processos gaussianos (Gaussian processes, GPs) para regressão/classificação probabilística (veja Processos Gaussianos)

Evite pensar em “métodos de kernel” como um único modelo; é um kit de ferramentas construído em torno de kernels, espaços de atributos e regularização.

A ideia central: modelos lineares em um espaço de atributos não linear

Muitos algoritmos de aprendizado são mais simples e mais estáveis quando o modelo é linear:

[ f(x) = w^\top x ]

Mas fronteiras de decisão lineares não conseguem separar problemas como círculos concêntricos. Métodos de kernel resolvem isso mapeando as entradas para um espaço de atributos mais rico:

[ \phi: \mathcal{X} \to \mathcal{H}, \quad f(x) = w^\top \phi(x) ]

Se (\phi(x)) tem alta dimensionalidade (possivelmente dimensionalidade infinita), computá-la explicitamente pode ser impossível. O truque do kernel evita isso.

O truque do kernel (kernel trick)

Uma função kernel (k(x, x')) é definida como um produto interno em algum espaço de atributos:

[ k(x, x') = \langle \phi(x), \phi(x') \rangle ]

Muitos algoritmos (SVMs, regressão de crista, PCA etc.) podem ser escritos de modo que dependam apenas de produtos internos entre exemplos. Substitua (\langle x, x' \rangle) por (k(x, x')), e você “kernelizou” o algoritmo.

Isso permite aprendizado não linear enquanto mantém os cálculos em termos de uma matriz de Gram (Gram matrix) (K) de dimensão (n \times n), onde (K_{ij} = k(x_i, x_j)).

Kernels positivos semidefinidos e por que eles importam

Nem toda função de similaridade é um kernel válido. Para que métodos de kernel se comportem como produtos internos em algum espaço de atributos, o kernel precisa ser positivo semidefinido (positive semidefinite, PSD).

Definição (kernel PSD)

Uma função simétrica (k) é PSD se, para qualquer conjunto de pontos (x_1,\dots,x_n), a matriz de Gram (K) definida por (K_{ij} = k(x_i, x_j)) for PSD:

[ \forall a \in \mathbb{R}^n,\quad a^\top K a \ge 0 ]

Intuição: PSD garante que as similaridades sejam consistentes com a geometria em algum espaço de Hilbert (possivelmente de alta dimensionalidade). Isso é o que torna a otimização convexa para muitos métodos de kernel e garante que “regularizar a função” tenha um significado bem definido.

Teorema de Mercer (alto nível)

O teorema de Mercer (Mercer’s theorem) conecta kernels PSD a expansões de atributos: sob condições brandas, um kernel PSD corresponde a um produto interno em um espaço de atributos (frequentemente de dimensionalidade infinita). Na prática, raramente é necessário construir (\phi); você só precisa que (k) seja PSD.

Construindo kernels PSD

Fatos úteis na prática:

  • Se (k_1) e (k_2) são PSD, então também são:
    • (k(x,x') = k_1(x,x') + k_2(x,x'))
    • (k(x,x') = c \cdot k_1(x,x')) para (c \ge 0)
    • (k(x,x') = k_1(x,x') \cdot k_2(x,x')) (kernel produto)
  • Se (\phi(x)) é qualquer mapa de atributos, então (k(x,x')=\phi(x)^\top \phi(x')) é PSD por construção.

Essas propriedades de fechamento são frequentemente usadas para projetar kernels que codificam estrutura de domínio (por exemplo, kernels aditivos para grupos de atributos, kernels produto para interações).

Kernels comuns e como escolhê-los

Aqui estão kernels amplamente usados e o que eles implicam:

Kernel linear

[ k(x,x') = x^\top x' ]

Equivalente a nenhuma expansão de atributos. Muitas vezes é uma linha de base forte, especialmente para atributos esparsos de alta dimensionalidade (por exemplo, saco de palavras (bag-of-words)).

Relacionado a Regressão Linear/Logística e SVMs lineares.

Kernel polinomial

[ k(x,x') = (x^\top x' + c)^d ]

Captura interações entre atributos até grau (d). Funciona bem quando interações são importantes e as entradas são normalizadas.

Kernel RBF (Gaussiano) (RBF (Gaussian) kernel)

[ k(x,x') = \exp\left(-\frac{|x-x'|^2}{2\sigma^2}\right) ]

Um padrão altamente flexível. Ele produz funções suaves e pode aproximar muitas fronteiras de decisão, dados dados suficientes.

Hiperparâmetro (hyperparameter): largura de banda (bandwidth) (\sigma) (ou (\gamma = 1/(2\sigma^2))). Muito pequena → muito “ondulada” / sobreajuste. Muito grande → quase linear / subajuste.

Kernels de Matérn (Matérn kernels) (comuns em processos gaussianos)

Kernels de Matérn controlam explicitamente a suavidade e são populares em modelagem bayesiana; veja Processos Gaussianos.

Orientação prática

  • Sempre escale os atributos (por exemplo, padronização (standardization)). Kernels baseados em distância (RBF) são extremamente sensíveis às escalas dos atributos.
  • Use RBF como uma escolha forte e de propósito geral para estrutura não linear.
  • Use linear quando você espera estrutura quase linear ou tem muitos atributos e dados limitados.
  • Use polinomial quando interações de um grau conhecido são importantes.
  • Ajuste hiperparâmetros do kernel com validação cruzada (cross-validation); a escolha do kernel faz parte do controle de capacidade do modelo.

Regularização e o teorema do representador

Métodos de kernel são tipicamente treinados minimizando um objetivo como:

[ \min_{f \in \mathcal{H}} \sum_{i=1}^n \ell(y_i, f(x_i)) + \lambda |f|_{\mathcal{H}}^2 ]

Aqui:

  • (\ell) é uma função de perda (perda quadrática (squared loss), perda hinge (hinge loss), perda logística (logistic loss) etc.)
  • (|f|_{\mathcal{H}}) é a norma no RKHS (espaço de Hilbert com kernel reprodutor (reproducing kernel Hilbert space, RKHS)) induzido por (k)
  • (\lambda) controla a regularização (regularization) (suavidade/complexidade)

Teorema do representador (por que as soluções dependem de kernels)

Um resultado fundamental: o minimizador (f^*) tem a forma:

[ f^*(x) = \sum_{i=1}^n \alpha_i , k(x_i, x) ]

Assim, em vez de aprender parâmetros no espaço de atributos, você aprende coeficientes (\alpha \in \mathbb{R}^n). É por isso que métodos de kernel frequentemente escalam com o número de pontos de treino (n).

Interpretação: previsões são uma combinação ponderada de similaridades com pontos de treino.

Conexões com teoria de aprendizado: capacidade, margens e generalização

Métodos de kernel estão profundamente conectados à teoria estatística do aprendizado porque fornecem medidas limpas de capacidade e generalização.

Controle de capacidade via norma do RKHS

A norma do RKHS (|f|_{\mathcal{H}}) atua como uma medida de complexidade: normas menores correspondem a funções “mais simples” na geometria definida pelo kernel. A regularização ((\lambda)) faz explicitamente a troca entre ajuste e complexidade.

Isso é análogo à regularização L2 em modelos lineares, mas em um espaço potencialmente de dimensionalidade infinita.

Margens e generalização em SVM

Em SVMs, a margem (margin) é central. Para dados separáveis, a SVM de margem rígida (hard-margin) encontra o classificador com máxima margem geométrica. Com kernels, isso se torna o classificador de margem máxima no espaço de atributos.

Margens grandes estão associadas a melhores limites de generalização (aproximadamente: margem maior → menor capacidade efetiva). Essa é uma das razões pelas quais SVMs com kernel frequentemente funcionam bem na prática mesmo com kernels muito flexíveis.

Para mais, veja Máquinas de Vetores de Suporte.

Dimensão efetiva e autovalores da matriz de kernel

O comportamento de generalização também depende do espectro da matriz de kernel (ou do operador integral de kernel): se os autovalores decaem rapidamente, a classe de funções se comporta como um espaço de menor dimensionalidade. Isso ajuda a explicar por que kernels podem generalizar bem mesmo quando o espaço de atributos implícito é de dimensionalidade infinita.

Regressão de crista com kernel (KRR)

A regressão de crista com kernel é a versão kernelizada da regressão de crista. Ela usa perda quadrática com regularização L2/RKHS:

[ \min_{f \in \mathcal{H}} \sum_{i=1}^n (y_i - f(x_i))^2 + \lambda |f|_{\mathcal{H}}^2 ]

Usando o teorema do representador, (f(x) = \sum_i \alpha_i k(x_i, x)). Seja (K) a matriz de Gram; então os coeficientes satisfazem:

[ \alpha = (K + \lambda I)^{-1} y ]

Prós e contras

  • Prós: solução em forma fechada; linha de base forte para regressão; fácil de implementar.
  • Contras: requer resolver um sistema linear (n \times n) (caro para (n) grande); sensível aos hiperparâmetros do kernel.

Exemplo prático (scikit-learn)

import numpy as np
from sklearn.kernel_ridge import KernelRidge
from sklearn.model_selection import GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline

X, y = ...  # your data

model = make_pipeline(
    StandardScaler(),
    GridSearchCV(
        KernelRidge(kernel="rbf"),
        param_grid={
            "kernelridge__alpha": [1e-3, 1e-2, 1e-1, 1.0],
            "kernelridge__gamma": [1e-2, 1e-1, 1.0, 10.0],  # gamma = 1/(2*sigma^2)
        },
        cv=5
    )
)

model.fit(X, y)
pred = model.predict(X[:5])

Máquinas de Vetores de Suporte (SVMs) com kernels (alto nível)

SVMs com kernel aprendem fronteiras de decisão da forma:

[ f(x) = \sum_{i=1}^n \alpha_i y_i k(x_i, x) + b ]

Mas uma propriedade-chave é que muitos (\alpha_i) se tornam exatamente zero. Os pontos restantes são vetores de suporte (support vectors), que definem a fronteira de decisão.

Por que isso importa

  • Esparsidade no tempo de predição: apenas vetores de suporte contribuem (embora, nos piores casos, muitos pontos possam se tornar vetores de suporte).
  • Maximização de margem: forte comportamento de generalização e robustez.

Para um tratamento mais aprofundado, veja Máquinas de Vetores de Suporte.

Exemplo prático (SVM RBF)

from sklearn.svm import SVC
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

clf = make_pipeline(
    StandardScaler(),
    SVC(kernel="rbf", C=10.0, gamma="scale")  # gamma can also be a float
)

clf.fit(X, y_class)
yhat = clf.predict(X_test)

Hiperparâmetros:

  • C: força de regularização inversa (valores maiores de C ajustam os dados de treino de forma mais agressiva).
  • gamma: controle da largura de banda do RBF.

Processos gaussianos: kernels como a priori sobre funções (alto nível)

Um processo gaussiano (GP) usa um kernel como uma função de covariância, definindo uma distribuição sobre funções:

[ f \sim \mathcal{GP}(0, k(\cdot,\cdot)) ]

Dado um conjunto de dados, o GP produz uma distribuição a posteriori (posterior) sobre valores de função, fornecendo:

  • Uma predição média (como regressão)
  • Uma estimativa de incerteza calibrada (uma grande vantagem em muitos domínios)

GPs se conectam de perto à regressão de crista com kernel: com ruído gaussiano (Gaussian noise) e uma distribuição a priori (prior) apropriada, a média a posteriori do GP corresponde a uma solução regularizada por kernel. Isso torna GPs um contraponto bayesiano a métodos de kernel regularizados; veja também Modelos Bayesianos.

Para detalhes, veja Processos Gaussianos.

Exemplo prático (regressão com processo gaussiano)

from sklearn.gaussian_process import GaussianProcessRegressor
from sklearn.gaussian_process.kernels import RBF, ConstantKernel as C

kernel = C(1.0, (1e-2, 1e2)) * RBF(length_scale=1.0, length_scale_bounds=(1e-2, 1e2))
gpr = GaussianProcessRegressor(kernel=kernel, alpha=1e-2, normalize_y=True)

gpr.fit(X, y)
mean, std = gpr.predict(X_test, return_std=True)

Uma intuição concreta: classificação não linear via similaridade

Considere um conjunto de dados de pontos em 2D formando dois círculos concêntricos. Nenhum classificador linear consegue separá-los no espaço original. Com um kernel RBF:

  • Pontos no mesmo círculo estão relativamente próximos → alta similaridade
  • Pontos em círculos diferentes estão mais distantes → menor similaridade

Uma SVM treinada nessas similaridades pode produzir uma fronteira de decisão circular sem criar explicitamente atributos como (x_1^2 + x_2^2). O kernel fornece implicitamente a geometria necessária para a separação.

Essa mesma intuição — “aprender usando similaridades” — também conecta métodos de kernel a modelos baseados em distância como k-NN, Bayes Ingênuo (Naive Bayes) (k-NN usa distâncias diretamente, enquanto kernels produzem um modelo linear aprendível no espaço de similaridade).

Considerações computacionais e escalabilidade

O principal custo dos métodos de kernel clássicos é construir e usar a matriz de Gram (K):

  • Memória: (O(n^2))
  • Tempo de treino: frequentemente (O(n^3)) para solucionadores ingênuos (por exemplo, inversão de matriz), embora existam solucionadores melhores
  • Tempo de predição: tipicamente (O(n)) por ponto de teste (ou (O(#SV)) para SVMs)

Por isso, métodos de kernel são mais comuns para (n) pequeno/médio.

Métodos de kernel aproximados e escaláveis

Para escalar kernels para conjuntos de dados maiores, abordagens comuns incluem:

  • Aproximação de Nyström (Nyström approximation): aproxima (K) usando um subconjunto de pontos de referência.
  • Características de Fourier Aleatórias (Random Fourier Features, RFF): aproximam kernels invariantes a deslocamentos (shift-invariant) (como RBF) por um mapa explícito de atributos de baixa dimensão, permitindo treino linear.
  • Interpolação estruturada de kernel / pontos indutores (structured kernel interpolation / inducing points): amplamente usados em processos gaussianos escaláveis.

Esses métodos trocam um pouco de acurácia por grandes ganhos em velocidade e memória, frequentemente tornando um desempenho “tipo kernel” viável em escalas muito maiores.

Fluxo de trabalho prático e armadilhas

Fluxo de trabalho recomendado

  1. Comece com uma linha de base (modelo linear ou ensemble de árvores (tree ensemble) dependendo do tipo de dados).
  2. Se você precisa de estrutura não linear e (n) é administrável:
    • Tente SVM RBF (classificação) ou KRR (regressão).
  3. Escale/padronize os atributos.
  4. Ajuste:
    • regularização (C ou alpha)
    • parâmetros do kernel (gamma / largura de banda, grau polinomial)
  5. Valide cuidadosamente com validação cruzada.

Armadilhas comuns

  • Atributos não escalados com kernels RBF → um atributo domina as distâncias.
  • Faixas ruins de hiperparâmetros → kernels podem parecer “quebrados” se a largura de banda estiver muito fora.
  • Conjuntos de dados grandes demais → falta de memória com matrizes de Gram.
  • Pré-processamento com vazamento (leaky preprocessing) → calcule parâmetros de escala apenas nos folds de treino.

Onde métodos de kernel são usados

Métodos de kernel aparecem em ML, às vezes explicitamente e às vezes como blocos de construção:

  • Classificação/regressão não linear (SVM, KRR)
  • Modelagem com incerteza (processos gaussianos) em ML científico e otimização bayesiana (Bayesian optimization)
  • PCA com kernel (kernel PCA) e outros métodos lineares kernelizados para estrutura não linear (relacionado a Redução de Dimensionalidade)
  • Aprendizado de similaridade e kernels para dados estruturados (strings, grafos), relacionados em espírito a Aprendizado Métrico

Na prática moderna, métodos de kernel continuam competitivos em muitos problemas pequenos/médios e frequentemente são preferidos quando você quer objetivos convexos (SVM/KRR) ou incerteza calibrada (GPs).

Resumo

Métodos de kernel fornecem uma forma fundamentada de aprender funções não lineares substituindo atributos explícitos por uma função kernel que atua como um produto interno em um espaço de atributos implícito. Ingredientes-chave incluem:

  • Kernels PSD (produtos internos válidos) e matrizes de Gram
  • O truque do kernel, permitindo aprendizado não linear com maquinaria de álgebra linear
  • Regularização em RKHS, controlando capacidade e melhorando generalização
  • Fortes conexões com teoria de aprendizado por meio de margens (SVMs) e controle de complexidade baseado em norma
  • Algoritmos amplamente usados: regressão de crista com kernel, SVMs com kernel e processos gaussianos

Eles são mais eficazes quando o tamanho dos dados é moderado, o escalonamento de atributos é tratado com cuidado e os hiperparâmetros de kernel/regularização são ajustados de forma criteriosa.