| Parte de uma série sobre |
| Aprendizado de máquina e mineração de dados |
|---|
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).
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 -ésimo exemplo de treinamento e aprendem para ele um peso correspondente . 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 , denominada kernel, entre a entrada não rotulada e cada uma das entradas de treinamento . Por exemplo, um classificador binário com kernel normalmente calcula uma soma ponderada de similaridades 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.

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 podem ser expressas como um produto interno em outro espaço . A função é 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 . O cálculo fica muito mais simples se o kernel puder ser escrito na forma de um "mapa de características" que satisfaça 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 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 para todo , que conta o número de pontos dentro do conjunto , a integral do teorema de Mercer se reduz a um somatórioSe esse somatório for válido para todas as sequências finitas de pontos em e para todas as escolhas de coeficientes reais (cf. kernel definido positivo), então a função 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 em relação a (por vezes também chamada de "matriz kernel"), em que , deve ser semidefinida positiva (PSD). Empiricamente, no caso de heurísticas de aprendizado de máquina, escolhas de uma função que não satisfazem a condição de Mercer ainda podem ter desempenho razoável se ao menos se aproximar da noção intuitiva de similaridade. Independentemente de ser ou não um kernel de Mercer, ainda pode ser chamada de "kernel".
Se a função kernel 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.
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 , um kernel definido positivo e um parâmetro de regularização , a KRR minimiza o risco empírico penalizado
sobre o espaço de Hilbert com kernel reprodutor associado a . O teorema do representante estabelece que o minimizador é , em que e é a matriz de Gram do kernel.
Resolver diretamente esse sistema linear custa em tempo e 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 pontos de referência. Em muitos problemas, um da ordem de preserva a taxa estatística ótima, o que reduz o custo para cerca de . 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 em tempo e memória.
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.