Como explicar intuitivamente o que é um kernel?

97

Muitos classificadores de aprendizado de máquina (por exemplo, máquinas de vetores de suporte) permitem especificar um kernel. Qual seria uma maneira intuitiva de explicar o que é um kernel?

Um aspecto em que tenho pensado é a distinção entre núcleos lineares e não lineares. Em termos simples, eu poderia falar de 'funções de decisão lineares' e 'funções de decisão não lineares'. No entanto, não tenho certeza se chamar um kernel de 'função de decisão' é uma boa idéia.

Sugestões?

chave de hash
fonte

Respostas:

113

O kernel é uma maneira de calcular o produto escalar de dois vetores e em alguns espaços (possivelmente com dimensões muito altas), razão pela qual as funções do kernel são algumas vezes chamadas de "produto escalar generalizado".yxy

Suponha que tenhamos um mapeamento que traga nossos vetores em para algum espaço de recurso . Em seguida, o produto escalar de e neste espaço é . Um kernel é uma função que corresponde a esse produto escalar, ou seja, .R n R m x y φ( x ) T φ( y )kk( x , y )=φ( x ) T φ( y )φ:RnRmRnRmxyφ(x)Tφ(y)kk(x,y)=φ(x)Tφ(y)

Por que isso é útil? Os kernels permitem calcular produtos de ponto em algum espaço de recurso sem nem mesmo saber o que é esse espaço e o que é .φ

Por exemplo, considere um kernel polinomial simples com . Isso não parece corresponder a nenhuma função de mapeamento , é apenas uma função que retorna um número real. Supondo que e , vamos expandir esta expressão:x , yR 2 φ x = ( x 1 , x 2 ) y = ( Y 1 , Y 2 )k(x,y)=(1+xTy)2x,yR2φx=(x1,x2)y=(y1,y2)

k(x,y)=(1+xTy)2=(1+x1y1+x2y2)2==1+x12y12+x22y22+2x1y1+2x2y2+2x1x2y1y2

Observe que isso nada mais é do que um produto escalar entre dois vetores e e . Portanto, o kernel calcula um produto de ponto em Espaço 6-dimensional sem visitar explicitamente este espaço.(1,x12,x22,2x1,2x2,2x1x2)(1,y12,y22,2y1,2y2,2y1y2)φ(x)=φ(x1,x2)=(1,x12,x22,2x1,2x2,2x1x2)k(x,y)=(1+xTy)2=φ(x)Tφ(y)

Outro exemplo é o kernel gaussiano . Se expandirmos essa função por Taylor, veremos que ela corresponde a um codomain de dimensão infinita de .k(x,y)=exp(γxy2)φ

Por fim, eu recomendaria um curso on-line "Learning from Data", do professor Yaser Abu-Mostafa, como uma boa introdução aos métodos baseados em kernel. Especificamente, as palestras "Support Vector Machines" , "Kernel Methods" e "Radial Basis Functions" são sobre kernels.

Alexey Grigorev
fonte
2
Definição de tag atual: "Intuitivo: perguntas que buscam um entendimento conceitual ou não matemático das estatísticas". Nenhuma indicação clara se conceitual é tratado como sinônimo de não-matemático.
Roland2
40

Uma maneira muito simples e intuitiva de pensar sobre kernels (pelo menos para SVMs) é uma função de similaridade. Dados dois objetos, o kernel gera alguma pontuação de similaridade. Os objetos podem ser qualquer coisa, a partir de dois números inteiros, dois vetores com valor real, árvores o que for, desde que a função do kernel saiba como compará-los.

O exemplo sem dúvida mais simples é o kernel linear, também chamado de produto pontual. Dados dois vetores, a semelhança é o comprimento da projeção de um vetor em outro.

Outros exemplos interessantes de kernel são o kernel gaussiano. Dados dois vetores, a semelhança diminuirá com o raio de . A distância entre dois objetos é "re-ponderada" por este parâmetro de raio.σ

O sucesso do aprendizado com kernels (novamente, pelo menos para SVMs) depende muito fortemente da escolha do kernel. Você pode ver um kernel como uma representação compacta do conhecimento sobre seu problema de classificação. Muitas vezes, é específico do problema.

Eu não chamaria um kernel de função de decisão, pois o kernel é usado dentro da função de decisão. Dado um ponto de dados para classificar, a função de decisão faz uso do kernel comparando esse ponto de dados com vários vetores de suporte ponderados pelos parâmetros aprendidos . Os vetores de suporte estão no domínio desse ponto de dados e, ao longo dos parâmetros aprendidos são encontrados pelo algoritmo de aprendizado.αα

Vladislavs Dovgalecs
fonte
O produto e a projeção de pontos não são exatamente idênticos.
Ttnphns 18/05/19
No caso do SVM, acredito que os kernels são medidas de distância em diferentes espaços. Isso está de acordo com a idéia de que um SVM generaliza um classificador de vetor de suporte. Em geral, os kernels podem ser mais complicados.
Aginensky # 20/15
29

Um exemplo visual para ajudar a intuição

Considere o seguinte conjunto de dados em que os pontos amarelo e azul claramente não são separáveis ​​linearmente em duas dimensões.

insira a descrição da imagem aqui

Se pudéssemos encontrar um espaço dimensional mais alto no qual esses pontos fossem linearmente separáveis , poderíamos fazer o seguinte:

  • Mapeie os recursos originais para o espaço superior do transformador (mapeamento de recursos)
  • Realize SVM linear neste espaço superior
  • Obter um conjunto de pesos correspondente ao hiperplano de limite de decisão
  • Mapeie este hiperplano de volta ao espaço 2D original para obter um limite de decisão não linear

Existem muitos espaços dimensionais mais altos nos quais esses pontos são linearmente separáveis. Aqui está um exemplo

x1,x2:→z1,z2,z3
z1=2x1x2  z2=x12  z3=x22

É aqui que o truque do Kernel entra em cena. Citando as excelentes respostas acima

Suponha que tenhamos um mapeamento que traga nossos vetores em para algum espaço de recurso . Em seguida, o produto escalar de e neste espaço é . Um kernel é uma função que corresponde a esse produto escalar, ou seja,φ:RnRmRnRmxyφ(x)Tφ(y)kk(x,y)=φ(x)Tφ(y)

Se pudéssemos encontrar uma função do kernel equivalente ao mapa de recursos acima, poderíamos conectar a função do kernel no SVM linear e executar os cálculos com muita eficiência.

Kernel polinomial

Acontece que o mapa de recursos acima corresponde ao conhecido polinômio do kernel : . Seja e obtemosK(x,x)=(xTx)dd=2x=(x1,x2)T

k((x1x2),(x1x2))=(x1x2+x2x2)2=2x1x1x2x2+(x1x1)2+(x2x2)2=(2x1x2 x12 x22) (2x1x2x12x22)

k((x1x2),(x1x2))=ϕ(x)Tϕ(x)

ϕ((x1x2))=(2x1x2x12x22)

Visualizando o Mapa de Recursos e a Linha Limite Resultante

  • O gráfico do lado esquerdo mostra os pontos plotados no espaço transformado, juntamente com o hiperplano de limite linear SVM
  • O gráfico do lado direito mostra o resultado no espaço 2D original

insira a descrição da imagem aqui


Fonte

Xavier Bourret Sicotte
fonte
4

Muito simplesmente (mas com precisão) um núcleo é um fator de peso entre duas seqüências de dados. Esse fator de pesagem pode atribuir mais peso a um " ponto de dados " em um " ponto de tempo " que o outro " ponto de dados ", ou atribuir peso igual ou atribuir mais peso ao outro " ponto de dados " e assim por diante.

Dessa forma, a correlação ( produto escalar ) pode atribuir mais "importância" em alguns pontos do que outros e, assim, lidar com não linearidades (por exemplo , espaços não planos ), informações adicionais, suavização de dados e assim por diante.

Ainda de outra maneira, um kernel é uma maneira de alterar as dimensões relativas (ou unidades de dimensão ) de duas seqüências de dados para lidar com as coisas mencionadas acima.

De uma terceira maneira (relacionada às duas anteriores), um kernal é uma maneira de mapear ou projetar uma sequência de dados na outra de maneira 1 para 1, levando em consideração informações ou critérios fornecidos (por exemplo, espaço curvo, dados ausentes, dados reordenar e assim por diante). Assim, por exemplo, um dado núcleo pode esticar ou encolher ou colheita ou dobrar sequência de um dos dados, a fim de se encaixar ou mapa 1-para-um para o outro.

Um kernel pode agir como um Procrustes para " encaixar melhor "

Nikos M.
fonte
Eu acho que você pode estar falando sobre kernels no sentido de estimativa da densidade do kernel, e não os kernels Mercer semidefinidos positivos usados ​​nos SVMs e métodos relacionados.
Dougal
@Dougal, no sentido de esta resposta o núcleo é uma função de pesagem ou medida utilizada para correlacionar os dados de uma forma específica ou para explorar recursos de dados determinados, assim métodos de kernel SVM são cobertos também
Nikos M.