O que torna o núcleo gaussiano tão mágico para o PCA e também em geral?

67

Eu estava lendo sobre o kernel PCA ( 1 , 2 , 3 ) com núcleos gaussianos e polinomiais.

Como o kernel gaussiano separa aparentemente qualquer tipo de dados não lineares excepcionalmente bem? Por favor, faça uma análise intuitiva, bem como uma análise matematicamente envolvida, se possível.
O que é uma propriedade do kernel gaussiano (com ideal ) que outros kernels não possuem? Redes neurais, SVMs e redes RBF vêm à mente. $\sigma$
Por que não colocamos a norma em, digamos, um PDF Cauchy e esperamos os mesmos resultados?

machine-learning pca svm kernel-trick Simon Kuang
fonte

11

+1. Excelente pergunta que quase esqueci, porque não tinha uma etiqueta [pca]! Editado agora.

Ameba diz Restabelecer Monica

4

Boa pergunta. Eu estou querendo saber se a resposta pode ser "sim, muitos outros kernels iria funcionar bem também, mas Gaussian é bem conhecida / fácil"

Stumpy Joe Pete

@StumpyJoePete Eu não acho que seja uma resposta tão trivial. Qual parâmetro de localização de outra distribuição também é o seu significado? Qual parâmetro de escala de outras distribuições também é sua variação? Que outra distribuição é tão universalmente intuitiva? Certamente não a distribuição Cauchy - ela nem tem um significado!

shadowtalker

3

@ssdecontrol Estou feliz por provar que estou errado; Eu votei tanto na pergunta quanto em uma das respostas - acho que minha resposta chata, hum-hum e deflacionária faz um bom padrão que uma resposta real deve refutar.

Stumpy Joe Pete

Eu acho que isso pode ajudar: stats.stackexchange.com/questions/168051/…

54

Eu acho que a chave da magia é a suavidade. Minha longa resposta a seguir é simplesmente explicar sobre essa suavidade. Pode ou não ser uma resposta que você espera.

Resposta curta:

Dado um kernel definido positivo , existe seu espaço correspondente de funções . As propriedades das funções são determinadas pelo kernel. Acontece que se é um kernel gaussiano, as funções em são muito suaves. Portanto, uma função aprendida (por exemplo, uma função de regressão, componentes principais no RKHS e no PCA do kernel) é muito suave. Geralmente, a suposição de suavidade é sensata para a maioria dos conjuntos de dados que queremos abordar. Isso explica por que um núcleo gaussiano é mágico. $k$ $\mathcal{H}$ $k$ $\mathcal{H}$

Resposta longa por que um kernel gaussiano oferece funções suaves:

Um kernel definido positivo define (implicitamente) um produto interno para o vetor de característica construído a partir da sua entrada , e é um espaço de Hilbert. A notação significa um produto interno entre e . Para nosso propósito, você pode imaginar como o espaço euclidiano usual, mas possivelmente com um número inifinito de dimensões. Imagine o vetor usual que é infinitamente longo como $k(x,y)$ $k(x,y)=\left\langle \phi(x),\phi(y)\right\rangle _{\mathcal{H}}$ $\phi(x)$ $x$ $\mathcal{H}$ $\left\langle \phi(x),\phi(y)\right\rangle$ $\phi(x)$ $\phi(y)$ $\mathcal{H}$ $\phi(x)=\left(\phi_{1}(x),\phi_{2}(x),\ldots\right)$ . Nos métodos do kernel, é um espaço de funções chamado reproduzir o espaço Hilbert do kernel (RKHS). Esse espaço tem uma propriedade especial chamada `` propriedade de reprodução '', que é . Isso diz que, para avaliar , primeiro você constrói um vetor de recurso (infinitamente longo, conforme mencionado) para . Então você constrói seu vetor de característica para indicado por (infinitamente longo). A avaliação de é feita usando um produto interno dos dois. Obviamente, na prática, ninguém construirá um vetor infinitamente longo. Como nos preocupamos apenas com o seu produto interno, apenas avaliamos diretamente o kernel $\mathcal{H}$ $f(x)=\left\langle f,\phi(x)\right\rangle$ $f(x)$ $f$ $x$ $\phi(x)$ $f(x)$ $k$ . Ignorar a computação de recursos explícitos e computar diretamente seu produto interno é conhecido como "truque do kernel".

Quais são os recursos?

Eu ficava dizendo os recursos sem especificar o que são. Dado um kernel , os recursos não são exclusivos. Mas é determinado exclusivamente. Para explicar a suavidade das funções, vamos considerar os recursos de Fourier. Suponha um kernel invariável de tradução , significando , isto é, o kernel depende apenas da diferença dos dois argumentos. O kernel gaussiano tem essa propriedade. Vamos denotar a transformada de Fourier de . $\phi_{1}(x),\phi_{2}(x),\ldots$ $k$ $\left\langle \phi(x),\phi(y)\right\rangle$ $k$ $k(x,y)=k(x-y)$ $\hat{k}$ $k$

Nesse ponto de vista de Fourier, os recursos de são dados por . Isto está dizendo que a representação do recurso de sua função é dada por sua transformação de Fourier dividida pela transformação de Fourer do kernel . A representação do recurso de , que é é em que . Pode-se mostrar que a propriedade de reprodução é válida (um exercício para os leitores). $f$ $f:=\left(\cdots,\hat{f}_{l}/\sqrt{\hat{k}_{l}},\cdots\right)$ $f$ $k$ $x$ $\phi(x)$ $\left(\cdots,\sqrt{\hat{k}_{l}}\exp\left(-ilx\right),\cdots\right)$ $i=\sqrt{-1}$

Como em qualquer espaço de Hilbert, todos os elementos pertencentes ao espaço devem ter uma norma finita. Vamos considerar a norma ao quadrado de um : $f\in\mathcal{H}$

$\|f\|_{\mathcal{H}}^{2}=\left\langle f,f\right\rangle _{\mathcal{H}}=\sum_{l=-\infty}^{\infty}\frac{\hat{f}_{l}^{2}}{\hat{k}_{l}}.$

Então, quando essa norma é finita, ou seja, pertence ao espaço? É quando cai mais rápido que para que a soma converja. Agora, a transformação de Fourier de um kernel gaussiano $f$ $\hat{f}_{l}^{2}$ $\hat{k}_{l}$ $k(x,y)=\exp\left(-\frac{\|x-y\|^{2}}{\sigma^{2}}\right)$

é outro gaussiano onde diminui exponencialmente rapidamente com . Portanto, se estiver nesse espaço, sua transformação de Fourier deve cair ainda mais rápido que a de . Isso significa que a função terá efetivamente apenas alguns componentes de baixa frequência com pesos altos. Um sinal com apenas componentes de baixa frequência não `` mexe '' muito. Isso explica por que um kernel gaussiano oferece uma função suave. $\hat{k}_{l}$ $l$ $f$ $k$

Extra: Que tal um kernel de Laplace?

Se você considerar um kernel de Laplace , sua transformação de Fourier é uma distribuição Cauchy que cai muito mais lentamente que o exponencial função na transformada de Fourier de um núcleo gaussiano. Isso significa que uma função terá mais componentes de alta frequência. Como resultado, a função dada por um kernel Laplace é `` mais áspera '' do que a dada por um kernel gaussiano. $k(x,y)=\exp\left(-\frac{\|x-y\|}{\sigma}\right)$ $f$

O que é uma propriedade do kernel gaussiano que outros kernels não possuem?

Independentemente da largura gaussiana, uma propriedade é que o kernel gaussiano é `` universal ''. Intuitivamente, isso significa que, dada uma função contínua limitada (arbitrária), existe uma função tal que e estão próximos (no sentido de até precisão arbitrária necessária. Basicamente, isso significa que o kernel Gaussiano fornece funções que podem aproximar arbitrariamente bem as funções "agradáveis" (limitadas, contínuas). Os núcleos Gaussian e Laplace são universais. Um núcleo polinomial, por exemplo, não é. $g$ $f\in\mathcal{H}$ $f$ $g$ $\|\cdot\|_{\infty})$

Por que não colocamos a norma em, digamos, um PDF Cauchy e esperamos os mesmos resultados?

Em geral, você pode fazer o que quiser, desde que o resultante seja definido positivamente. Definitividade positiva é definida como para todos , e todos os (conjunto de números naturais) . Se não for positivo definido, ele não corresponderá a um espaço interno do produto. Toda a análise é interrompida porque você nem possui um espaço de funções conforme mencionado. No entanto, pode funcionar empiricamente. Por exemplo, o núcleo hiperbólico da tangente (veja o número 7 nesta página ) $k$ $\sum_{i=1}^{N}\sum_{j=1}^{N}k(x_{i},x_{j})\alpha_{i}\alpha_{j}>0$ $\alpha_{i}\in\mathbb{R}$ $\{x_{i}\}_{i=1}^{N}$ $N\in\mathbb{N}$ $k$ $\mathcal{H}$

$k(x,y) = tanh(\alpha x^\top y + c)$

que se destina a imitar unidades de ativação sigmóide em redes neurais, é apenas definitivo positivo para algumas configurações de e . Ainda foi relatado que funciona na prática. $\alpha$ $c$

E quanto a outros tipos de recursos?

Eu disse que os recursos não são únicos. Para o kernel gaussiano, outro conjunto de recursos é dado pela expansão da Mercer . Veja a Seção 4.3.1 do famoso livro de processo Gaussiano . Nesse caso, os recursos são polinômios Hermite avaliados em . $\phi(x)$ $x$

wij
fonte

2

Eu não estou prestes a adjudicar o prêmio apenas ainda, mas estou tentado a atribuí-lo a esta resposta, porque é muito segmentado para a questão e faz comparações explícitas a outros kernels

shadowtalker

Finalmente, esta pergunta obteve uma ótima resposta! (+1) Fiquei brevemente confuso com a notação que você usou aqui: - e nos parágrafos a seguir. Uma notação mais explícita seria mais clara ao separar uma função atuando no espaço original e em um vetor , onde é funcional? A propósito, que funções são garantidas como "reproduzidas" pela "propriedade reprodutora"? Tudo? Contínuo? Suave?

f (x) = ⟨ f, ϕ (x) ⟩

$f(x)=\left\langle f,\phi(x)\right\rangle$

f (x) = ⟨ Ψ (f), ϕ (x) ⟩

$f(x)=\left\langle \Psi(f),\phi(x)\right\rangle$

f (\cdot)

$f(\cdot)$

Ψ (f) \in H

$\Psi(f) \in \mathcal H$

Ψ (\cdot)

$\Psi(\cdot)$

Ameba diz Reinstate Monica

@amoeba Na literatura, as pessoas não distinguem uma representação de e a própria função. Se necessário, às vezes eles usam para representação para uma função. Todas as funções no espaço têm a propriedade de reprodução. Suave ou não, isso é especificado pelo kernel. :)

f

$f$

f

$f$

f (\cdot)

$f(\cdot)$

H

$\mathcal{H}$

wij

Atualizado a postagem. Adicionado um pouco mais no tanh kernel.

wij

Hummm, acho que estou confuso aqui. Começamos com um espaço vetorial , onde os pontos de dados vivem. Em seguida, escolha um kernel definida positiva . Então afirmamos que o Teorema 1 contém: pode ser realizado como um produto escalar em algum espaço de Hilbert , de modo que , onde . OK. E agora você diz que qualquer função atuando em pode ser realizada como um produto escalar de sua representação

X

$\mathcal X$

x

$x$

k (\cdot, \cdot) : X \times X \to R

$k(\cdot, \cdot): \mathcal X \times \mathcal X \to \mathbb R$

k

$k$

H

$\mathcal H$

k (x, y) = ⟨ ϕ (x), ϕ (y) ⟩

$k(x,y) = \langle \phi(x), \phi(y)\rangle$

ϕ : X \to H

$\phi:\mathcal X \to \mathcal H$

f (x)

$f(x)$

X

$\mathcal X$

f \in H

$f\in \mathcal H$ com ? Isto está certo?

ϕ (x)

$\phi(x)$

ameba diz Restabelecer Monica

18

Farei o possível para responder a essa pergunta não porque sou especialista no assunto (pelo contrário), mas porque tenho curiosidade sobre o campo e o assunto, combinada com a ideia de que poderia ser uma boa experiência educacional . De qualquer forma, aqui está o resultado da minha breve pesquisa amadora sobre o assunto.

TL; DR : Eu consideraria a seguinte passagem do trabalho de pesquisa "A conexão entre operadores de regularização e kernels de vetor de suporte" como a resposta curta a esta pergunta:

Os núcleos gaussianos tendem a produzir um bom desempenho sob suposições gerais de suavidade e devem ser considerados especialmente se nenhum conhecimento adicional dos dados estiver disponível.

Agora, uma resposta detalhada (da melhor maneira possível; para detalhes matemáticos, use referências).

Como sabemos, a análise de componentes principais (PCA) é uma abordagem altamente popular para a redução da dimensionalidade , sozinha e para posterior classificação dos dados: http://www.visiondummy.com/2014/05/feature-extraction-using-pca . No entanto, em situações em que os dados carregam dependências não lineares (em outras palavras, linearmente inseparáveis ), o PCA tradicional não é aplicável (não apresenta bom desempenho). Para esses casos, outras abordagens podem ser usadas, e o PCA não linear é uma delas.

As abordagens, nas quais o PCA se baseia no uso da função kernel, geralmente são referidas, usando um termo genérico "kernel PCA" ( kPCA ). O uso do kernel da função radial de base gaussiana (RBF) é provavelmente a variação mais popular. Essa abordagem é descrita em detalhes em várias fontes, mas eu gosto muito de uma excelente explicação de Sebastian Raschka nesta postagem do blog . No entanto, ao mencionar a possibilidade de usar funções do kernel, que não sejam o Gaussian RBF, o post enfoca o último devido à sua popularidade. Este belo post no blog , apresentando aproximações e truques do kernel , menciona mais uma possível razão para a popularidade do kernel gaussiano no PCA: dimensionalidade infinita.

Informações adicionais podem ser encontradas em várias respostas no Quora. Em particular, a leitura desta excelente discussão revela vários pontos sobre possíveis razões da popularidade do kernel gaussiano, como segue.

Os núcleos gaussianos são universais :

Os núcleos gaussianos são núcleos universais, ou seja, seu uso com regularização apropriada garante um preditor globalmente ideal que minimiza os erros de estimativa e aproximação de um classificador.

Os núcleos gaussianos são circulares (o que leva à dimensionalidade infinita acima mencionada?)
Núcleos gaussianos podem representar "terrenos altamente variáveis"
O ponto a seguir, apoiando a principal conclusão acima, é melhor citado pelo autor:

O kernel Gaussian RBF é muito popular e faz um bom kernel padrão, especialmente na ausência de conhecimento especializado sobre dados e domínio, porque também inclui o kernel polinomial e linear. Núcleos lineares e núcleos polinomiais são um caso especial do kernel Gaussian RBF. Os kernels RBF gaussianos são um modelo não paramétrico, o que significa essencialmente que a complexidade do modelo é potencialmente infinita, porque o número de funções analíticas é infinito.

Os núcleos gaussianos são ótimos (sobre suavidade , leia mais aqui - mesmo autor):

Um kernel gaussiano é apenas um filtro de passagem de banda; seleciona a solução mais suave. [...] Um kernel gaussiano funciona melhor quando a soma infinita de derivadas de alta ordem converge mais rapidamente - e isso acontece para as soluções mais suaves.

Finalmente, pontos adicionais desta bela resposta :

Os núcleos gaussianos suportam modelos infinitamente complexos
Núcleos gaussianos são mais flexíveis

NOTAS:

O ponto acima mencionado sobre a escolha ideal do kernel gaussiano , especialmente quando não há conhecimento prévio sobre os dados, é suportado pela seguinte frase desta resposta do CV :

Na falta de conhecimento especializado, o kernel da Função Base Radial cria um bom kernel padrão (depois de estabelecer, é um problema que requer um modelo não linear).

Para aqueles curiosos sobre diferenças não essenciais entre o kernel Gaussian RBF e o kernel Gaussian padrão, esta resposta pode ser interessante: https://stats.stackexchange.com/a/79193/31372 .

Para aqueles interessados em implementar o kPCA por prazer ou negócios, este belo post pode ser útil. Ele foi escrito por um dos autores (criadores?) Do Accord.NET - um framework de código aberto .NET muito interessante para análise estatística, aprendizado de máquina, processamento de sinais e muito mais.

Aleksandr Blekh
fonte

5

Aprecio e aplaudo o esforço feito para compor essa resposta, mas, ao mesmo tempo, devo dizer que cita muitas fontes que não são muito autoritárias e que fornecem apenas esse tipo de explicações gerais que podem estar corretas, mas podem também ser completamente falso. Portanto, o núcleo RBF é um núcleo estacionário isotrópico com um espaço Hilbert reprodutivo de dimensão infinita. Boa! Existem outros kernels com essas propriedades? Se sim, por que o RBF seria melhor que todos eles? De fato, existe algum suporte empírico à alegação de que a RBF supera esses concorrentes?

Ameba diz Reinstate Monica

@amoeba: Obrigado por palavras gentis. Em relação às fontes que eu usei, você está parcialmente certo - é uma mistura e algumas fontes são apenas opiniões. No entanto, algumas fontes (ou seja, as postagens do blog) citam documentos sólidos. Nesse ponto, fiquei mais atraído pela qualidade de uma explicação do que pelo seu rigor. No que diz respeito às suas perguntas, estou me preparando para abordá-las mais tarde. Eu preciso ler um pouco mais de teoria. Eu já compilei fontes com suporte empírico, mas preciso de mais tempo para sua sistematização (e um pouco de sono, :).

Aleksandr Blekh

11

Tenho a sensação do fato de que o Gaussian tem entropia máxima entre as distribuições simétricas reais desempenha um papel no seu primeiro ponto sobre o bom desempenho sob suposição geral

shadowtalker

2

Também @AleksandrBlekh, esta é uma compilação fantástica. As pessoas se incomodam com o Quora, mas não é menos autoritário do que vincular-se a outra resposta aqui

#

@ssdecontrol: Obrigado por palavras gentis. Fico feliz que estamos na mesma página sobre o tema. Eu tenho algumas informações adicionais para abordar o comentário da ameba, então assista este espaço, se você estiver interessado.

Aleksandr Blekh

8

Deixe-me colocar meus dois centavos.

A maneira como penso sobre os núcleos gaussianos é como classificadores de vizinhos mais próximos em algum sentido. O que um kernel gaussiano faz é que ele representa cada ponto com a distância de todos os outros pontos no conjunto de dados. Agora pense em classificadores com limites lineares ou polinomiais, os limites são limitados a certas formas. No entanto, quando você olha para o vizinho mais próximo, o limite pode praticamente assumir qualquer forma. É por isso que penso que o kernel gaussiano também é não-paramétrico, ou seja, ajustando o limite dependendo dos dados. Outra maneira de pensar nisso é que o kernel gaussiano se ajusta à forma local em uma região, semelhante à maneira como um vizinho mais próximo ajusta localmente o limite olhando a distância para outros pontos da região local.

Não tenho um argumento matemático para isso, mas acho que o fato de o núcleo gaussiano ser de fato mapeado para um espaço dimensional infinito tem algo a ver com seu sucesso. Para os núcleos linear e polinomial, os produtos de ponto são obtidos em espaços dimensionais finitos; portanto, parece mais poderoso fazer as coisas em um espaço maior. Espero que alguém tenha uma melhor compreensão dessas coisas. Isso também significa que, se pudermos encontrar outros núcleos com espaços dimensionais infinitos, eles também deverão ser bastante poderosos. Infelizmente, não estou familiarizado com nenhum kernel desse tipo.

Para seu último argumento, acho que o pdf de Cauchy ou qualquer outro pdf que, de alguma forma, mede a distância de outros pontos deve funcionar igualmente bem. Novamente, não tenho um bom argumento matemático para isso, mas a conexão com o vizinho mais próximo torna isso plausível.

Editar:

Aqui estão algumas idéias sobre como pensar em um classificador usando kernels gaussianos como classificadores de vizinhos mais próximos. Primeiro, vamos pensar no que um classificador de vizinho mais próximo faz. Essencialmente, um classificador de vizinho mais próximo é um classificador padrão que usa as distâncias entre pontos como entradas. Mais formalmente, imagine que criamos uma representação de recurso para cada ponto no conjunto de dados calculando sua distância para todos os outros pontos. Acima, é uma função de distância. Então, o que o classificador vizinho mais próximo faz é prever o rótulo da classe para um ponto com base nessa representação de recurso e nos rótulos da classe para os dados. em que $\phi_i$ $x_i$

ϕ_{i} = (d (x_{i}, x_{1}), d (x_{i}, x_{2}), \dots, d (x_{i}, x_{n}))

$\phi_i = (d(x_i,x_1), d(x_i, x_2), \ldots, d(x_i, x_n))$

d

$d$

p_{i} = f (ϕ_{i}, y)

$p_i = f(\phi_i, y)$

p_{i}

$p_i$ é a previsão para o ponto de dados e é um vetor de rótulos de classe para .

x_{i}

$x_i$

y

$y$

x_{1}, x_{2}, \dots, x_{n}

$x_1, x_2, \ldots, x_n$

A maneira como penso sobre os kernels é que eles fazem uma coisa semelhante; eles criam uma representação de recurso de cada ponto usando seus valores de kernel com outros pontos no conjunto de dados. Semelhante ao caso do vizinho mais próximo, mais formalmente seria Agora a conexão com o vizinho mais próximo é bastante óbvia; se nossa função do kernel é alguma medida relacionada às medidas de distância que usamos nos classificadores de vizinhos mais próximos, nosso classificador baseado em kernel será semelhante ao modelo de vizinho mais próximo.

ϕ_{i} = (k (x_{i}, x_{1}), k (x_{i}, x_{2}), \dots, k (x_{i}, x_{n}))

$\phi_i = (k(x_i, x_1), k(x_i, x_2), \ldots, k(x_i, x_n))$

Nota: Os classificadores que treinamos usando kernels não funcionam diretamente com essas representações , mas acho que é isso que eles fazem implicitamente. $\phi_i$

goker
fonte

A interpretação dos vizinhos mais próximos é interessante. Você acha que poderia expandir isso um pouco? Acho que entendi, mas não tenho certeza.

shadowtalker

@ssdecontrol Adicionei alguns comentários; Espero que sejam úteis.

Goker

6

O motivo é que a dimensão VC para os núcleos gaussianos é infinita e, portanto, dados os valores corretos para os parâmetros (sigma), eles podem classificar corretamente um número arbitrariamente grande de amostras.

Os RBFs funcionam bem porque garantem que a matriz seja de classificação completa. A idéia é que e termos fora da diagonal podem ser arbitrariamente pequenos, diminuindo o valor de . Observe que o kernel corresponde a um produto de ponto no espaço de recursos. Nesse espaço de recursos, a dimensão é infinita (considerando a expansão em série do exponencial). Pode-se ver isso projetando esses pontos em diferentes dimensões para que você possa separá-los. $K(x_{i},x_{j})$ $K(x_{i},x_{i}) > 0$ $\sigma$

Por outro lado, considere o caso dos núcleos lineares, que só podem quebrar quatro pontos no plano.

Você pode dar uma olhada neste artigo , embora seja muito técnico. Um dos livros padrão sobre SVMs deve tornar esse conceito mais acessível.

jpmuc
fonte

11

'RBFs funcionam bem porque garantem que a matriz seja de classificação completa': isso é válido para todas as funções válidas do kernel (Mercer) (incluindo a linear), por isso não tenho certeza de como explica a suposta saída desempenho da RBF.

K (x_{i}, x_{j})

$K(x_i,x_j)$

user603

2

Além do que o @ user603 acabou de escrever: existem outros kernels populares com dimensão infinita de VC (dimensão do espaço de destino)? Se sim, eles são tão bons quanto o RBF?

ameba diz Restabelecer Monica

2

A dimensão VC não é propriedade de um conjunto de classificadores, não é propriedade de um kernel?

wij

2

@ user603: isso não é verdade. Os kernels Mercer exigem apenas que a matriz do kernel seja positiva semidefinida; eles podem ser singulares. Por exemplo, o kernel linear de fato fornece matrizes singulares do kernel se estiver no seu conjunto de pontos. (Claro, a maioria dos kernels são estritamente definida positiva e por isso esta não é uma propriedade particularmente distintivo da RBF Gaussian.)

x_{i} = 0

$x_i = 0$

Dougal

O que torna o núcleo gaussiano tão mágico para o PCA e também em geral?

Respostas: