PCA com Kernel (Kernel PCA)

Visão geral

Análise de Componentes Principais com Kernel (Kernel Principal Component Analysis, Kernel PCA ou KPCA) é uma generalização não linear da Análise de Componentes Principais (Principal Component Analysis, PCA; frequentemente abreviada como ACP). Enquanto a ACP encontra direções lineares de máxima variância no espaço original de atributos, a ACP com kernel consegue descobrir estrutura não linear ao mapear implicitamente os dados para um (potencialmente muito alto-dimensional) espaço de características (feature space) e executar ACP ali.

A ideia central é o truque do kernel (kernel trick): em vez de calcular explicitamente o mapeamento de características (\phi(x)), a ACP com kernel só exige produtos internos (\langle \phi(x_i), \phi(x_j)\rangle), que podem ser computados por meio de uma função de kernel (kernel function) (k(x_i, x_j)). Esses produtos internos formam a matriz de Gram (Gram matrix) (também chamada de matriz de kernel), e a ACP é realizada por meio de uma decomposição espectral (eigen-decomposition) de uma versão centralizada dessa matriz.

A ACP com kernel é comumente usada para:

  • Redução de dimensionalidade não linear (compressão, extração de características)
  • Visualização não linear (incorporações (embeddings) em 2D/3D)
  • Pré-processamento para modelos a jusante (downstream models) (classificação/regressão)
  • Remoção de ruído e exploração de dados estruturados em variedade (manifold)

Ela fica entre a ACP linear e métodos puramente voltados à visualização como t-SNE e UMAP: pode produzir características úteis para tarefas a jusante, mas é mais cara e mais sensível a hiperparâmetros do que a ACP linear.

Intuição: por que a ACP se torna “kernelizada”

A ACP funciona encontrando direções nas quais os dados mais variam. Formalmente, com dados centralizados (X \in \mathbb{R}^{n\times d}), a ACP diagonaliza a matriz de covariância:

[ C = \frac{1}{n} X^\top X ]

A ACP com kernel substitui a entrada (x \in \mathbb{R}^d) por um mapeamento de características (\phi(x) \in \mathcal{H}) (frequentemente muito alto-dimensional, às vezes de dimensão infinita). Nesse espaço de características:

[ C_\phi = \frac{1}{n} \sum_{i=1}^n \phi(x_i)\phi(x_i)^\top ]

Gostaríamos de executar ACP em (\phi(x)), mas calcular (\phi(x)) explicitamente muitas vezes é inviável. O truque do kernel nos permite computar tudo usando apenas

[ k(x_i, x_j) = \langle \phi(x_i), \phi(x_j)\rangle ]

Isso torna a ACP com kernel prática para muitos espaços de características não lineares.

O truque do kernel e a matriz de Gram

Funções de kernel

Um kernel (k(\cdot,\cdot)) é uma função que se comporta como um produto interno em algum espaço de características:

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

Para a ACP com kernel, construímos a matriz de Gram (K \in \mathbb{R}^{n\times n}):

[ K_{ij} = k(x_i, x_j) ]

A ACP com kernel então realiza uma decomposição espectral de uma versão centralizada de (K).

Kernels comuns e hiperparâmetros

  1. Kernel linear (linear kernel)
    [ k(x, z) = x^\top z ] Isso reduz a ACP com kernel à ACP padrão (com diferenças apenas nos detalhes de centralização/escala).

  2. Kernel RBF / Gaussiano (RBF / Gaussian kernel) (o mais comum para estrutura não linear)
    [ k(x, z) = \exp(-\gamma |x - z|^2) ]

    • (\gamma) controla localidade/suavidade.
    • (\gamma) maior → mais local, mais flexível (risco: sobreajuste / “memorizar” pontos).
    • (\gamma) menor → mais suave, mais próximo de um comportamento linear.

  3. Kernel polinomial (polynomial kernel)
    [ k(x, z) = (\alpha, x^\top z + c)^{p} ]

    • grau (p) controla a não linearidade.
    • (c) desloca o kernel (características polinomiais não homogêneas).
    • (\alpha) é um fator de escala (frequentemente 1).

  4. Kernel sigmoide (sigmoid kernel) (menos comum; nem sempre semidefinido positivo (positive semidefinite, PSD) para todas as configurações)
    [ k(x, z) = \tanh(\alpha x^\top z + c) ] Na prática, muitas vezes é substituído pelo kernel RBF.

Orientação prática sobre hiperparâmetros:

  • Sempre escale/padronize as características antes de kernels RBF ou polinomiais.
  • Para RBF, um ponto de partida comum é (\gamma = \frac{1}{d \cdot \mathrm{Var}(X)}) ou usar a heurística da mediana (median heuristic) (baseada na mediana das distâncias par a par), e então ajustar via validação cruzada (cross-validation) com base no desempenho a jusante.

Centralização da matriz de kernel (crítico)

A ACP pressupõe que os dados estão centralizados (média zero). No espaço de características, precisamos de vetores de características centralizados:

[ \tilde{\phi}(x_i) = \phi(x_i) - \frac{1}{n}\sum_{m=1}^n \phi(x_m) ]

Em geral, não conseguimos calcular (\phi) explicitamente, então centralizamos via a matriz de Gram. Defina:

[ H = I - \frac{1}{n}\mathbf{1}\mathbf{1}^\top ]

Então a matriz de kernel centralizada é:

[ K_c = H K H ]

Essa “dupla centralização” garante que a ACP com kernel corresponda à ACP em características centralizadas em (\mathcal{H}).

Armadilha comum: esquecer de centralizar (K) (ou centralizar de forma inconsistente para novos pontos) pode distorcer severamente os componentes.

O problema de autovalores da ACP com kernel (o que realmente resolvemos)

A ACP com kernel encontra autovetores no espaço de características. Acontece que esses autovetores estão no subespaço gerado pelos vetores de características de treinamento, então podemos representar uma direção principal como:

[ v = \sum_{i=1}^n \alpha_i \tilde{\phi}(x_i) ]

Resolver o problema de ACP em (\mathcal{H}) torna-se resolver um problema de autovalores na matriz de Gram centralizada:

[ K_c \alpha = n \lambda \alpha ]

  • (\alpha) é um autovetor de (K_c)
  • (\lambda) corresponde à variância explicada (até uma escala por (n))

Projetando pontos nos componentes

Para um vetor de características (centralizado) (\tilde{\phi}(x)), a coordenada no componente (j) pode ser computada como:

[ z_j(x) = \langle v_j, \tilde{\phi}(x) \rangle = \sum_{i=1}^n \alpha_{j,i}, k_c(x_i, x) ]

onde (k_c(x_i, x)) denota a avaliação do kernel centralizado de forma apropriada entre o ponto de treinamento (x_i) e o ponto (x).

Para pontos de treinamento, essas projeções podem ser calculadas diretamente a partir de autovetores/autovalores de (K_c).

Escolhendo o número de componentes

Com a ACP linear, você frequentemente seleciona componentes com base na variância explicada (explained variance). Para a ACP com kernel, você pode inspecionar de modo semelhante os autovalores de (K_c), mas a interpretabilidade é um pouco diferente porque a variância é medida no espaço de características.

Estratégias práticas de seleção:

  • Espectro de autovalores (eigenvalue spectrum) (“método do cotovelo (elbow method)”): escolha (m) onde os autovalores começam a achatar.
  • Validação a jusante: escolha (m) que dá o melhor desempenho com validação cruzada na tarefa (ex.: acurácia de classificação após ACP com kernel + classificador).
  • Reconstrução/transformação inversa (inverse transform) (se disponível): escolha (m) que atinge um erro de reconstrução aceitável (observação: o mapeamento inverso é aproximado para ACP com kernel).

Importante: a ACP com kernel pode sobreajustar ao criar incorporações muito “onduladas”, especialmente com kernel RBF e (\gamma) grande. Escolher componentes demais pode prejudicar a generalização.

Extensão fora da amostra (transformando novos pontos)

Uma grande questão prática é: após ajustar a ACP com kernel nos dados de treinamento ({x_i}{i=1}^n), como incorporamos um novo ponto (x*) sem reajustar?

Etapa 1: calcular o vetor de kernel para os pontos de treinamento

[ k_* = [k(x_1,x_*), \dots, k(x_n,x_*)]^\top ]

Etapa 2: centralizá-lo de forma consistente com a centralização do treinamento

Se você centralizou via (K_c = H K H), você deve centralizar (k_*) de modo compatível. Uma fórmula explícita comum é:

[ k_{*,c} = k_* - \frac{1}{n}K\mathbf{1} - \frac{1}{n}\mathbf{1}\mathbf{1}^\top k_* + \frac{1}{n^2}\mathbf{1}\mathbf{1}^\top K \mathbf{1} ]

Na prática, bibliotecas armazenam as médias de linha/coluna necessárias para fazer isso internamente.

Etapa 3: projetar usando autovetores aprendidos

Se (\alpha_j) é o (j)-ésimo autovetor normalizado, a coordenada da incorporação é:

[ z_j(x_*) = \alpha_j^\top k_{*,c} ]

Isso é frequentemente chamado de extensão fora da amostra (out-of-sample extension) para a ACP com kernel.

Escalando para grandes conjuntos de dados: aproximação de Nyström

A ACP com kernel padrão precisa da decomposição espectral de uma matriz (n \times n), o que é caro para (n) grande. Uma alternativa comum é o método de Nyström (Nyström method), que aproxima (K) usando um subconjunto de pontos de referência, reduzindo bastante tempo/memória. Isso é especialmente relevante quando (n) está na casa de dezenas de milhares ou mais.

Considerações práticas

1. Complexidade e memória

A ACP com kernel tipicamente exige:

  • Construir (K): tempo (O(n^2 d)) (para kernels comuns), memória (O(n^2))
  • Decomposição espectral: tempo (O(n^3)) no pior caso (frequentemente menor com resolvedores parciais de autovalores)

Isso rapidamente se torna um gargalo.

Regras práticas:

  • Até alguns milhares de amostras: ACP com kernel padrão é viável em uma máquina moderna.
  • Acima disso: considere aproximações (Nyström, características aleatórias (random features)) ou outros métodos.

2. A escala das características importa (muito)

Como kernels dependem de distâncias e produtos escalares:

  • Para kernels RBF, características não escaladas podem fazer uma dimensão dominar as distâncias.
  • Para kernels polinomiais, características de grande magnitude podem explodir os produtos internos.

Pré-processamento típico:

  • Padronize cada característica para média zero e variância unitária.
  • Considere escalonamento robusto se houver outliers fortes.

3. Ajuste de hiperparâmetros não é opcional

Ao contrário da ACP, a ACP com kernel tem hiperparâmetros do kernel (ex.: (\gamma), grau). Boas configurações dependem de:

  • Escala dos dados (daí a importância de escalar!)
  • Nível de ruído
  • Curvatura da variedade e dimensão intrínseca

Em pipelines supervisionados (ex.: ACP com kernel → classificador), ajuste parâmetros do kernel e número de componentes via validação cruzada.

4. Interpretar componentes é mais difícil do que na ACP

Na ACP linear, cada componente é uma direção no espaço original de atributos; você pode inspecionar as cargas (loadings). Na ACP com kernel, os componentes vivem em um espaço de características implícito, então a interpretabilidade é limitada.

5. Transformação inversa e o “problema da pré-imagem (pre-image problem)”

Às vezes você quer mapear coordenadas de baixa dimensão da ACP com kernel de volta para o espaço de entrada (para reconstrução/remoção de ruído). Isso não é trivial porque (\phi(\cdot)) pode ser não invertível ou implícito.

  • Algumas implementações fornecem uma inversa aproximada (frequentemente via abordagens no estilo de regressão ridge com kernel (kernel ridge regression)).
  • A qualidade pode variar significativamente e depende da escolha do kernel e do ruído.

Exemplo trabalhado: estrutura não linear (círculos concêntricos)

Um cenário clássico em que a ACP falha, mas a ACP com kernel funciona, é um conjunto de dados em forma de círculos concêntricos: a variância não se alinha com uma direção linear.

A seguir há um exemplo prático em Python (scikit-learn) mostrando como a ACP com kernel pode “desenrolar” estrutura não linear.

import numpy as np
from sklearn.datasets import make_circles
from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import KernelPCA
from sklearn.pipeline import make_pipeline

# Nonlinear toy dataset
X, y = make_circles(n_samples=1000, factor=0.4, noise=0.05, random_state=0)

# RBF Kernel PCA pipeline with scaling
kpca = KernelPCA(n_components=2, kernel="rbf", gamma=10.0)
model = make_pipeline(StandardScaler(), kpca)

Z = model.fit_transform(X)  # 2D nonlinear embedding
print(Z.shape)  # (1000, 2)

O que esperar:

  • A ACP linear em grande parte preservará a estrutura circular (não linearmente separável).
  • A ACP com kernel RBF frequentemente produz uma incorporação na qual os círculos interno/externo se separam ao longo de um componente, tornando a estrutura mais fácil de modelar a jusante.

Exemplo: ACP com kernel como pré-processamento para classificação

A ACP com kernel pode ser usada como extrator de características antes de um classificador simples. Isso pode ajudar quando você quer características não lineares, mas prefere manter o modelo a jusante simples/rápido.

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

pipeline = make_pipeline(
    StandardScaler(),
    KernelPCA(n_components=10, kernel="rbf", gamma=5.0),
    SVC(kernel="linear")
)

scores = cross_val_score(pipeline, X, y, cv=5)
print(scores.mean(), scores.std())

Observações:

  • O classificador é linear, mas após a ACP com kernel as características são funções não lineares das entradas.
  • Em muitos casos, uma SVM com RBF (máquina de vetores de suporte (Support Vector Machine, SVM) com kernel RBF) pode ter desempenho semelhante ou melhor, mas a ACP com kernel ainda pode ser útil se você quiser características explícitas para múltiplas tarefas a jusante.

Como a ACP com kernel se compara a métodos relacionados

ACP com kernel vs ACP

  • ACP: linear, rápida, interpretável, escala bem.
  • ACP com kernel: não linear, mais flexível, mais cara, menos interpretável, exige ajuste de kernel.

Se a ACP linear já captura a estrutura de que você precisa, a ACP com kernel é uma complexidade desnecessária.

ACP com kernel vs t-SNE / UMAP

  • t-SNE e UMAP são projetados principalmente para visualização e preservação de vizinhanças.
  • A ACP com kernel produz uma representação global de características que pode ser usada mais diretamente em pipelines (embora possa não preservar vizinhanças tão fielmente quanto t-SNE/UMAP).

Se seu objetivo é um gráfico 2D fiel, t-SNE/UMAP geralmente são melhores. Se seu objetivo é obter características não lineares para aprendizado, a ACP com kernel é um padrão mais forte.

Checklist de dicas e armadilhas

  • Sempre escale as entradas antes de aplicar kernels baseados em distância.
  • Centralize a matriz de kernel (ou confie em uma implementação correta da biblioteca).
  • Ajuste (\gamma) / grau; escolhas ruins podem tornar incorporações inúteis.
  • Fique atento a sobreajuste: kernels muito flexíveis + muitos componentes podem codificar ruído.
  • Planeje para memória (O(n^2)): a ACP com kernel pode se tornar inviável rapidamente.
  • Para (n) grande, considere aproximações de Nyström ou métodos alternativos.

Resumo

A ACP com kernel estende a ACP para cenários não lineares ao realizar ACP em um espaço de características implícito definido por uma função de kernel. Ela depende do truque do kernel para evitar mapeamentos explícitos de características, funciona pela decomposição espectral de uma matriz de Gram centralizada e pode produzir incorporações não lineares poderosas, úteis para visualização e aprendizado a jusante. Na prática, o sucesso depende fortemente de centralização correta do kernel, escalonamento cuidadoso das características, ajuste criterioso de hiperparâmetros e controle do custo computacional — especialmente quando você precisa de incorporações fora da amostra ou deve escalar para grandes conjuntos de dados.