Método Kernel

No aprendizado de máquina, as máquinas de kernel constituem uma classe de algoritmos para análise de padrões, cujo representante mais conhecido é a máquina de vetores de suporte (SVM, na sigla em inglês). Esses métodos utilizam classificadores lineares para resolver problemas não lineares. A tarefa geral da análise de padrões consiste em encontrar e estudar tipos gerais de relações (por exemplo, agrupamentos, ordenações, componentes principais, correlações e classificações) em conjuntos de dados. Em muitos algoritmos que resolvem essas tarefas, os dados em sua representação bruta precisam ser explicitamente transformados em representações por vetores de características por meio de um mapa de características especificado pelo usuário. Os métodos kernel, por outro lado, exigem apenas um kernel especificado pelo usuário, isto é, uma função de similaridade sobre todos os pares de pontos de dados, calculada por meio de produtos internos. O mapa de características nas máquinas de kernel tem dimensão infinita, mas, de acordo com o teorema do representante, requer apenas uma matriz de dimensão finita a partir dos dados fornecidos pelo usuário. Sem processamento paralelo, as máquinas de kernel são lentas para conjuntos de dados com mais de alguns milhares de exemplos.

Os métodos kernel devem seu nome ao uso de funções kernel, que lhes permitem operar em um espaço de características de alta dimensão e implícito sem jamais calcular as coordenadas dos dados nesse espaço; basta calcular os produtos internos entre as imagens de todos os pares de dados no espaço de características. Essa operação costuma ser computacionalmente mais barata do que o cálculo explícito das coordenadas. Essa abordagem é chamada de "truque do kernel" (kernel trick). Já foram propostas funções kernel para dados sequenciais, grafos, textos e imagens, além de vetores.

Entre os algoritmos capazes de operar com kernels estão o perceptron de kernel, as máquinas de vetores de suporte (SVM), os processos gaussianos, a análise de componentes principais (PCA), a análise de correlação canônica, a regressão ridge, o agrupamento espectral, os filtros adaptativos lineares e muitos outros.

A maioria dos algoritmos de kernel baseia-se em otimização convexa ou em problemas de autovalores e tem sólida fundamentação estatística. Suas propriedades estatísticas costumam ser analisadas por meio da teoria do aprendizado estatístico (por exemplo, com o uso da complexidade de Rademacher).

Motivação e explicação informal

Os métodos kernel podem ser entendidos como aprendizes baseados em instâncias: em vez de aprender um conjunto fixo de parâmetros correspondentes às características de suas entradas, eles "memorizam" o i-ésimo exemplo de treinamento (𝐱i,yi) e aprendem para ele um peso correspondente wi. A previsão para entradas não rotuladas, isto é, aquelas que não pertencem ao conjunto de treinamento, é feita pela aplicação de uma função de similaridade k, denominada kernel, entre a entrada não rotulada 𝐱′ e cada uma das entradas de treinamento 𝐱i. Por exemplo, um classificador binário com kernel normalmente calcula uma soma ponderada de similaridades ŷ=sgn⁡∑i=1nwiyik(𝐱i,𝐱′), em que

Os classificadores de kernel foram descritos já na década de 1960, com a invenção do perceptron de kernel. Eles ganharam grande destaque com a popularização da máquina de vetores de suporte (SVM) na década de 1990, quando se constatou que a SVM era competitiva com as redes neurais em tarefas como o reconhecimento de escrita manual.

Matemática: o truque do kernel

SVM com mapa de características dado por φ((a,b))=(a,b,a2+b2) e, portanto, com a função kernel k(𝐱,𝐲)=𝐱⋅𝐲+‖𝐱‖2‖𝐲‖2. Os pontos de treinamento são mapeados para um espaço tridimensional, no qual é fácil encontrar um hiperplano separador.

O truque do kernel dispensa o mapeamento explícito necessário para que algoritmos de aprendizado lineares aprendam uma função não linear ou uma fronteira de decisão. Para todos os 𝐱 e 𝐱′ no espaço de entrada 𝒳, certas funções k(𝐱,𝐱′) podem ser expressas como um produto interno em outro espaço 𝒱. A função k:𝒳×𝒳→ℝ é frequentemente chamada de kernel ou função kernel. Na matemática, a palavra "kernel" (núcleo) designa uma função de ponderação para uma soma ponderada ou uma integral.

Certos problemas de aprendizado de máquina têm mais estrutura do que uma função de ponderação arbitrária k. O cálculo fica muito mais simples se o kernel puder ser escrito na forma de um "mapa de características" φ:𝒳→𝒱 que satisfaça k(𝐱,𝐱′)=⟨φ(𝐱),φ(𝐱′)⟩𝒱.Aprincipal restrição é que ⟨⋅,⋅⟩𝒱 deve ser um produto interno propriamente dito. Por outro lado, não é necessária uma representação explícita de φ, desde que 𝒱 seja um espaço com produto interno. Essa alternativa decorre do teorema de Mercer: existe uma função φ definida implicitamente sempre que o espaço 𝒳 puder ser munido de uma medida adequada que garanta que a função k satisfaça a condição de Mercer.

O teorema de Mercer é semelhante a uma generalização do resultado da álgebra linear que associa um produto interno a qualquer matriz definida positiva. De fato, a condição de Mercer pode ser reduzida a esse caso mais simples. Se escolhermos como medida a medida de contagem μ(T)=|T| para todo T⊂X, que conta o número de pontos dentro do conjunto T, a integral do teorema de Mercer se reduz a um somatório∑i=1n∑j=1nk(𝐱i,𝐱j)cicj≥0.Se esse somatório for válido para todas as sequências finitas de pontos (𝐱1,…,𝐱n) em 𝒳 e para todas as escolhas de n coeficientes reais (c1,…,cn) (cf. kernel definido positivo), então a função k satisfaz a condição de Mercer.

Alguns algoritmos que dependem de relações arbitrárias no espaço nativo 𝒳 teriam, na verdade, uma interpretação linear em outro contexto: o espaço imagem de φ. A interpretação linear oferece uma melhor compreensão do algoritmo. Além disso, muitas vezes não é necessário calcular φ diretamente durante a computação, como ocorre com as máquinas de vetores de suporte. Há quem aponte essa redução no tempo de execução como a principal vantagem do método. Os pesquisadores também a utilizam para justificar os significados e as propriedades de algoritmos já existentes.

Teoricamente, uma matriz de Gram 𝐊∈ℝn×n em relação a {𝐱1,…,𝐱n} (por vezes também chamada de "matriz kernel"), em que Kij=k(𝐱i,𝐱j), deve ser semidefinida positiva (PSD). Empiricamente, no caso de heurísticas de aprendizado de máquina, escolhas de uma função k que não satisfazem a condição de Mercer ainda podem ter desempenho razoável se k ao menos se aproximar da noção intuitiva de similaridade. Independentemente de k ser ou não um kernel de Mercer, k ainda pode ser chamada de "kernel".

Se a função kernel k também for uma função de covariância, como as usadas em processos gaussianos, a matriz de Gram 𝐊 também pode ser chamada de matriz de covariância.

Regressão ridge com kernel

A regressão ridge com kernel (KRR, na sigla em inglês) combina a regressão ridge com o truque do kernel. Dados os dados de treinamento (𝐱1,y1),…,(𝐱n,yn), um kernel definido positivo k e um parâmetro de regularização λ>0, a KRR minimiza o risco empírico penalizado

1n∑i=1n(f(𝐱i)−yi)2+λ‖f‖ℋ2

sobre o espaço de Hilbert com kernel reprodutor ℋ associado a k. O teorema do representante estabelece que o minimizador é f̂(𝐱)=∑i=1nαik(𝐱i,𝐱), em que α=(K+nλIn)−1y e K=(k(𝐱i,𝐱j))1≤i,j≤n é a matriz de Gram do kernel.

Resolver diretamente esse sistema linear custa O(n3) em tempo e O(n2) em memória, o que restringe os métodos kernel exatos a conjuntos de dados de tamanho moderado. Aproximações como o método de Nyström e as características aleatórias de Fourier (random Fourier features) substituem a matriz de Gram por uma aproximação de posto baixo construída a partir de M≪n pontos de referência. Em muitos problemas, um M da ordem de n preserva a taxa estatística ótima, o que reduz o custo para cerca de O(nn). Quando o kernel tem uma expansão de Fourier explícita, como os kernels de Matérn, o estimador pode ser calculado em uma base de Fourier truncada por meio de transformadas rápidas de Fourier não uniformes, com custo O(nlog⁡n) em tempo e memória.

Aplicações

As áreas de aplicação dos métodos kernel são diversas e incluem a geoestatística, a krigagem, a ponderação pelo inverso da distância, a reconstrução 3D, a bioinformática, a quimioinformática, a extração de informação e o reconhecimento de escrita manual.

Kernels populares

Ver também

Referências

  1. 1 2 Hofmann, Thomas; Schölkopf, Bernhard; Smola, Alexander J. (2008). «Kernel Methods in Machine Learning» [Métodos kernel no aprendizado de máquina]. The Annals of Statistics. 36 (3). arXiv:math/0701907Acessível livremente. doi:10.1214/009053607000000677Acessível livremente. Consultado em 5 de novembro de 2026. Cópia arquivada em 20 de julho de 2025
  2. ↑ Theodoridis, Sergios (2008). Pattern Recognition [Reconhecimento de padrões]. [S.l.]: Elsevier B.V. 203 páginas. ISBN 9780080949123
  3. ↑ Shawe-Taylor, John; Cristianini, Nello (2004). Kernel Methods for Pattern Analysis [Métodos kernel para análise de padrões] (em inglês). [S.l.]: Cambridge University Press. ISBN 978-0-521-81397-6. doi:10.1017/CBO9780511809682
  4. ↑ Bartlett, Peter L.; Mendelson, Shahar (2002). «Rademacher and Gaussian complexities: risk bounds and structural results» [Complexidades de Rademacher e gaussiana: limites de risco e resultados estruturais]. Journal of Machine Learning Research (em inglês). 3: 463–482. Consultado em 5 de novembro de 2026. Cópia arquivada em 8 de outubro de 2026
  5. ↑ Schölkopf, Bernhard; Smola, Alexander J. (2002). Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond [Aprendizado com kernels: máquinas de vetores de suporte, regularização, otimização e além] (em inglês). Cambridge, Massachusetts: MIT Press. ISBN 0-262-19475-9
  6. ↑ Aizerman, M. A.; Braverman, Emmanuel M.; Rozonoer, L. I. (1964). «Theoretical foundations of the potential function method in pattern recognition learning» [Fundamentos teóricos do método da função potencial no aprendizado para reconhecimento de padrões]. Automation and Remote Control. 25: 821–837 Citado em Guyon, Isabelle; Boser, B.; Vapnik, Vladimir (1993). Automatic capacity tuning of very large VC-dimension classifiers [Ajuste automático de capacidade de classificadores de dimensão VC muito grande]. Advances in neural information processing systems. CiteSeerX 10.1.1.17.7215Acessível livremente
  7. ↑ Boser, Bernhard E.; Guyon, Isabelle M.; Vapnik, Vladimir N. (1992). A training algorithm for optimal margin classifiers [Um algoritmo de treinamento para classificadores de margem ótima]. Proceedings of the Fifth Annual Workshop on Computational Learning Theory (COLT '92) (em inglês). pp. 144–152. doi:10.1145/130385.130401
  8. ↑ Mercer, J. (1909). «Functions of positive and negative type, and their connection with the theory of integral equations» [Funções de tipo positivo e negativo e sua relação com a teoria das equações integrais]. Philosophical Transactions of the Royal Society A (em inglês). 209 (441–458): 415–446. doi:10.1098/rsta.1909.0016
  9. ↑ Aronszajn, N. (1950). «Theory of reproducing kernels» [Teoria dos kernels reprodutores]. Transactions of the American Mathematical Society (em inglês). 68 (3): 337–404. doi:10.1090/S0002-9947-1950-0051437-7
  10. ↑ Schölkopf, Bernhard; Smola, Alexander; Müller, Klaus-Robert (1998). «Nonlinear component analysis as a kernel eigenvalue problem» [Análise de componentes não linear como um problema de autovalores com kernel]. Neural Computation (em inglês). 10 (5): 1299–1319. doi:10.1162/089976698300017467
  11. ↑ Mohri, Mehryar; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Foundations of Machine Learning [Fundamentos do aprendizado de máquina]. Massachusetts, EUA: MIT Press. ISBN 9780262018258
  12. ↑ Sewell, Martin. «Support Vector Machines: Mercer's Condition» [Máquinas de vetores de suporte: condição de Mercer]. Support Vector Machines. Consultado em 5 de novembro de 2026. Arquivado do original em 15 de outubro de 2018
  13. ↑ Rasmussen, Carl Edward; Williams, Christopher K. I. (2006). Gaussian Processes for Machine Learning [Processos gaussianos para aprendizado de máquina]. [S.l.]: MIT Press. ISBN 0-262-18253-X [falta página]
  14. ↑ Saunders, Craig; Gammerman, Alexander; Vovk, Volodya (1998). Ridge regression learning algorithm in dual variables [Algoritmo de aprendizado por regressão ridge em variáveis duais]. Proceedings of the 15th International Conference on Machine Learning (ICML 1998) (em inglês). pp. 515–521. Consultado em 5 de novembro de 2026. Cópia arquivada em 10 de julho de 2026
  15. ↑ Schölkopf, Bernhard; Herbrich, Ralf; Smola, Alex J. (2001). A generalized representer theorem [Um teorema do representante generalizado]. Computational Learning Theory (COLT 2001). Lecture Notes in Computer Science (em inglês). 2111. pp. 416–426. doi:10.1007/3-540-44581-1_27
  16. ↑ Williams, Christopher K. I.; Seeger, Matthias (2001). Using the Nyström method to speed up kernel machines [Uso do método de Nyström para acelerar máquinas de kernel]. Advances in Neural Information Processing Systems 13. pp. 682–688
  17. ↑ Rahimi, Ali; Recht, Benjamin (2007). Random features for large-scale kernel machines [Características aleatórias para máquinas de kernel em larga escala]. Advances in Neural Information Processing Systems 20. pp. 1177–1184
  18. ↑ Rudi, Alessandro; Carratino, Luigi; Rosasco, Lorenzo (2017). FALKON: An optimal large scale kernel method [FALKON: um método kernel ótimo em larga escala]. Advances in Neural Information Processing Systems 30. arXiv:1705.10958Acessível livremente
  19. ↑ Doumèche, Nathan; Bach, Francis; Biau, Gérard; Boyer, Claire (2026). Fast kernel methods: Sobolev, physics-informed, and additive models [Métodos kernel rápidos: modelos de Sobolev, informados pela física e aditivos]. Proceedings of the 43rd International Conference on Machine Learning. Proceedings of Machine Learning Research. 306. pp. 26319–26340. arXiv:2509.02649Acessível livremente. Consultado em 5 de novembro de 2026. Cópia arquivada em 23 de outubro de 2026
  20. ↑ Honarkhah, M.; Caers, J. (2010). «Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling» [Simulação estocástica de padrões usando modelagem de padrões baseada em distância]. Mathematical Geosciences. 42 (5): 487–517. Bibcode:2010MaGeo..42..487H. doi:10.1007/s11004-010-9276-7

Leitura adicional

Ligações externas