O Kernel PCA com kernel linear é equivalente ao PCA padrão?

17

Se no PCA do kernel eu escolher um kernel linear K(x,y)=xy , o resultado será diferente do PCA linear comum ? As soluções são fundamentalmente diferentes ou existe alguma relação bem definida?

tgoossens
fonte

Respostas:

27

Resumo: o PCA do kernel com kernel linear é exatamente equivalente ao PCA padrão.

Seja a matriz de dados centralizada do tamanho N × D com variáveis D em colunas e N pontos de dados em linhas. Em seguida, a D × D matriz de covariância é dada por XX / ( n - 1 ) , os seus vectores próprios são eixos principais e valores próprios são PC variâncias. Ao mesmo tempo, pode-se considerar a chamada Gram matriz X X do N × N tamanho. É fácil ver que ele tem os mesmos valores próprios (ou seja, variações de PC) até n - 1XN×DDND×DXX/(n-1)XXN×Nn1 e seus vetores próprios são os principais componentes dimensionados para a norma da unidade.

Este era o PCA padrão. Agora, no kernel PCA, consideramos alguma função que mapeia cada ponto de dados para outro espaço vetorial que geralmente possui uma maior dimensionalidade D n e w , possivelmente até infinita. A idéia do PCA do kernel é executar o PCA padrão neste novo espaço.ϕ(x)DneW

Como a dimensionalidade desse novo espaço é muito grande (ou infinita), é difícil ou impossível calcular uma matriz de covariância. No entanto, podemos aplicar a segunda abordagem ao PCA descrita acima. De fato, a matriz Gram ainda terá o mesmo tamanho gerenciável de Os elementos dessa matriz são dados por ϕ ( x i ) ϕ ( x j ) , que chamaremos de função do kernel K ( x i , x j ) = ϕ ( x i ) ϕ ( x j )N×Nϕ(xEu)ϕ(xj)K(xi,xj)=ϕ(xi)ϕ(xj). Isso é conhecido como truque do kernel : na verdade, nem sempre é necessário calcular , mas apenas K ( ) . Os autovetores dessa matriz Gram serão os principais componentes no espaço-alvo, nos quais estamos interessados.ϕ()K()

A resposta para sua pergunta agora se torna óbvia. Se , a matriz Gram do kernel reduz para X X ⊤, que é igual à matriz Gram padrão e, portanto, os componentes principais não serão alterados.K(x,y)=xyXX

Uma referência muito legível é Scholkopf B, Smola A e Müller KR, análise de componentes principais do Kernel, 1999 , e observe que, por exemplo, na Figura 1 eles se referem explicitamente ao PCA padrão como aquele que utiliza o produto escalar como uma função do kernel:

PCA do kernel

ameba diz Restabelecer Monica
fonte
onde estão essas fotos na sua resposta? De algum livro?
Pinocchio
@Pinocchio, a figura é retirada de Scholkopf et al. artigo, referenciado e vinculado na minha resposta.
ameba diz Restabelecer Monica
"É fácil ver que ele tem os mesmos valores próprios (ou seja, variações de PC) até o fator n-1 " - isso não significa que eles não são completamente equivalentes? Digamos que eu tenha uma matriz com n = 10 amostras, d = 200 dimensões. No PCA padrão, eu seria capaz de projetar os dados em 199 dimensões, se quisesse, mas no PCA do kernel com kernel linear, posso apenas até 10 dimensões.
Cesar
1
@ Cesar, não, se você tiver n = 10 amostras, a matriz de covariância terá classificação 10-1 = 9 e o PCA padrão encontrará apenas 9 dimensões (assim como o PCA do kernel). Consulte aqui: stats.stackexchange.com/questions/123318 .
ameba diz Reinstate Monica
Estou obtendo um arquivo não encontrado para o link de referência do Scholkopf B, Smola A e Müller KR.
pbible
5

XN×DDNX=UΣVUXXX=UΣ2U tem os mesmos vetores singulares à esquerda e, portanto, os mesmos componentes principais.

Martha White
fonte
Para o PCA padrão, pensei que nos importávamos, com o SVD da matriz de covariância, então realmente não entendo como o SVD de X é relevante, você pode expandir?
M0s #
@ m0s Para o PCA, nos preocupamos com a composição automática da matriz de covariância que normalmente executamos pelo SVD da matriz de dados (centralizada).
MrJrFenner
1

Parece-me que um KPCA com kernel linear deve ser o mesmo que o PCA simples.

A matriz de covariância da qual você obterá os valores próprios é a mesma:

linearKPCAmatrix=1lj=1lK(xj,xj)=1lj=1lxjxjT=PCAmatrix

You can check with more details here.

Jundiaius
fonte
3
Your answer is correct in spirit, but the formula looks confusing. KPCA works with Gram matrix K(xi,xj), not with covariance matrix (for many nonlinear kernels it's actually impossible to compute covariance matrix as the target space has infinite dimensionality). See page 2 of the paper you cite.
amoeba says Reinstate Monica