O Truque do Kernel

• Explicar por que dados que não são linearmente separáveis no espaço de features original podem se tornar separáveis depois de mapeados para um espaço de dimensão maior.
• Enunciar o truque do kernel com precisão: trocar todo produto escalar da otimização da SVM por uma função kernel, sem nunca calcular explicitamente o mapeamento de dimensão maior.
• Nomear e descrever os kernels polinomial e gaussiano (RBF) e explicar o que cada um calcula.
• Explicar, com um exemplo resolvido, por que o truque do kernel é um atalho computacional genuíno, e não só uma conveniência de notação.

O classificador de margem máxima do conceito anterior encontra a melhor fronteira linear, mas muitos conjuntos de dados reais não são linearmente separáveis no espaço de features original, não importa como a margem seja otimizada. Uma opção é transformar explicitamente os dados num espaço de dimensão maior usando features não lineares construídas (como já mencionado como possibilidade para a regressão linear e logística, antes nesta disciplina), onde uma fronteira linear pode existir mesmo que não existisse nenhuma no espaço original. O truque do kernel torna essa ideia drasticamente mais barata: acontece que todo o problema de otimização da SVM, e sua regra de decisão final, dependem dos dados de treino apenas por meio de produtos escalares entre pares, nunca diretamente dos vetores de features brutos, e é exatamente essa a brecha que o truque do kernel explora.

Por que os produtos escalares são a única coisa que importa

A derivação matemática da margem ótima da SVM (omitida aqui, já que pertence a uma disciplina de otimização mais avançada) mostra que tanto o objetivo de treino quanto a função de decisão final podem ser escritos usando só produtos escalares entre pares de vetores de features, x⁽ⁱ⁾ · x⁽ʲ⁾, do conceito de produto escalar de foundations/mathematics-for-computing, e nunca os vetores brutos x⁽ⁱ⁾ e x⁽ʲ⁾ isolados. Essa observação é todo o fundamento do truque do kernel.

O próprio truque do kernel

Suponha que um mapeamento de features φ(x) leve os dados para um espaço de dimensão muito maior, onde eles se tornam linearmente separáveis. Calcular φ(x) explicitamente, e depois o produto escalar φ(x⁽ⁱ⁾) · φ(x⁽ʲ⁾) nesse espaço de alta dimensão, pode ser extremamente caro; às vezes o espaço de destino tem dimensão infinita. Uma função kernel K(x⁽ⁱ⁾, x⁽ʲ⁾) calcula o valor φ(x⁽ⁱ⁾) · φ(x⁽ʲ⁾) diretamente, muitas vezes em tempo proporcional só à dimensão original (baixa) de x, sem nunca construir φ(x) explicitamente. Como toda a maquinaria da SVM só precisa desses valores de produto escalar, substituir K(x⁽ⁱ⁾, x⁽ʲ⁾) em todo lugar onde um produto escalar apareceria permite que uma SVM opere como se os dados tivessem sido mapeados para o espaço de alta dimensão, ao custo computacional do espaço original.

Kernels comuns

• Kernel polinomial: K(x, z) = (x·z + c)^d, que corresponde implicitamente a mapear x para um espaço de todas as combinações polinomiais das suas features até o grau d.
• Kernel gaussiano (RBF): K(x, z) = exp(−‖x − z‖² / (2σ²)), que corresponde a um mapeamento implícito para um espaço de dimensão infinita e mede uma similaridade que decai suavemente com a distância entre x e z; é o kernel de uso geral mais usado na prática.

Exemplo 1: o kernel polinomial evitando o cálculo explícito em alta dimensão

Para entradas 2D x = (x₁, x₂), um mapeamento polinomial de grau 2 pode ser φ(x) = (x₁², √2·x₁x₂, x₂²), um espaço tridimensional. Calculando φ(x)·φ(z) diretamente:

text
φ(x)·φ(z) = x₁²z₁² + 2x₁x₂z₁z₂ + x₂²z₂² = (x₁z₁ + x₂z₂)²  =  (x·z)²

Esse é exatamente o kernel polinomial de grau 2, K(x,z) = (x·z)². Calcular o lado direito exige um produto escalar e uma elevação ao quadrado no espaço original de 2 dimensões, enquanto calcular o lado esquerdo diretamente exigiria primeiro construir os vetores tridimensionais φ(x) e φ(z). Para polinômios de grau maior ou mais features originais, essa diferença entre o custo do kernel e o custo do mapeamento explícito cresce bastante: uma economia computacional real e verificável, e não de notação.

Exemplo 2: o mapeamento de dimensão infinita do kernel RBF

O kernel gaussiano K(x,z) = exp(−‖x−z‖²/(2σ²)) corresponde a um mapeamento implícito de features para um espaço com infinitas dimensões (um fato demonstrável por uma expansão em série de Taylor da exponencial, cuja derivação completa está além do escopo desta disciplina). Não há como calcular φ(x) explicitamente para esse kernel, já que isso exigiria um vetor infinito. Mesmo assim, o próprio K(x,z) é trivialmente barato de calcular diretamente a partir dos x e z originais, de baixa dimensão. Aqui, o truque do kernel não é só um atalho: é a única forma de usar esse mapeamento de alta dimensão em particular.

• "O truque do kernel é só uma forma mais rápida de calcular o mesmo mapeamento explícito de features." Para kernels como o RBF, não existe nenhum mapeamento explícito finito para calcular. O truque do kernel não é a otimização de um cálculo que seria possível de outra forma: ele viabiliza um cálculo que seria impossível.
• "Qualquer função pode ser usada como kernel." Um kernel válido precisa corresponder a um produto escalar genuíno em algum espaço de features (formalmente, sua matriz de kernel precisa ser semidefinida positiva para qualquer conjunto de entradas). Funções de similaridade arbitrárias não necessariamente satisfazem isso e não podem simplesmente ser substituídas na maquinaria da SVM sem quebrar suas garantias matemáticas.
• "Um kernel mais complexo (grau polinomial maior, ou σ muito pequeno no kernel RBF) sempre tem desempenho melhor." Um kernel flexível demais para os dados disponíveis reintroduz exatamente o risco de overfitting do bloco de complexidade de modelos desta disciplina. O kernel e seus parâmetros (o grau d, ou σ) precisam ser escolhidos por validação cruzada, e não simplesmente pela opção mais expressiva disponível.

Como toda a otimização da SVM depende dos dados de treino apenas por meio de produtos escalares entre pares, o truque do kernel troca cada um desses produtos escalares por uma função kernel que calcula o produto escalar equivalente num espaço de features implícito, muitas vezes de dimensão muito maior, sem nunca construir esse espaço explicitamente. O kernel polinomial mapeia implicitamente para um espaço finito de combinações polinomiais de features; o kernel gaussiano (RBF) mapeia implicitamente para um espaço de dimensão infinita, o que o torna utilizável só pelo truque do kernel, nunca por um mapeamento explícito de features. Como toda outra flexibilidade que esta disciplina apresentou, a escolha do kernel e de seus parâmetros precisa ser ajustada por validação cruzada para não reintroduzir o overfitting.