Por que o PCA maximiza a variação total da projeção?

Christopher Bishop escreve em seu livro Pattern Recognition and Machine Learning uma prova de que cada componente principal consecutivo maximiza a variação da projeção para uma dimensão, depois que os dados foram projetados no espaço ortogonal aos componentes selecionados anteriormente. Outros mostram provas semelhantes.

No entanto, isso prova apenas que cada componente consecutivo é a melhor projeção para uma dimensão, em termos de maximização da variação. Por que isso implica que a variação de uma projeção para dizer 5 dimensões seja maximizada escolhendo primeiro esses componentes?

machine-learning variance pca dimensionality-reduction eigenvalues Michal
fonte

Você poderia nos dizer exatamente o que significa a "variação" do conjunto de dados tridimensional resultante de uma projeção de um conjunto de dados em cinco dimensões? (Para que tal quantidade a ser sujeitos a maximização teria que ser um único número.)

whuber

Muito bom ponto. Chris Bishop em seu livro se refere à minimização da variação de uma projeção e não está muito claro o que isso significaria para mais de uma dimensão. Gostaria de saber em que sentido a variação é minimizada e por que esse procedimento a minimiza em conjunto.

Michal

@ user123675: No seu último comentário, você provavelmente quer dizer "maximizar", não "minimizar".

Ameba

Sim você está certo. Desculpa!

Michal

Respostas:

O que se entende por variação em várias dimensões ("variação total") é simplesmente uma soma de variações em cada dimensão. Matematicamente, é um traço da matriz de covariância: o traço é simplesmente uma soma de todos os elementos diagonais. Essa definição possui várias propriedades interessantes, por exemplo, o traço é invariável sob transformações lineares ortogonais, o que significa que se você girar seus eixos de coordenadas, a variação total permanecerá a mesma.

O que é provado no livro de Bishop (seção 12.1.1), é que o principal vetor próprio da matriz de covariância fornece a direção da variação máxima. O segundo vetor próprio fornece a direção da variação máxima sob uma restrição adicional de que ele deve ser ortogonal ao primeiro vetor próprio etc. (acredito que isso constitui o Exercício 12.1). Se o objetivo é maximizar a variação total no subespaço 2D, esse procedimento é uma maximização gananciosa: primeiro escolha um eixo que maximize a variação e depois outro.

Sua pergunta é: por que esse procedimento ganancioso obtém um máximo global?

Aqui está um bom argumento que @whuber sugeriu nos comentários. Vamos primeiro alinhar o sistema de coordenadas com os eixos PCA. A matriz de covariância se torna diagonal: . Por simplicidade, consideraremos o mesmo caso 2D, ou seja, qual é o plano com variação total máxima? Queremos provar que é o plano dado pelos dois primeiros vetores de base (com variação total ). $\boldsymbol{\Sigma} = \mathrm{diag}(\lambda_i)$ $\lambda_1+\lambda_2$

Considere um plano estendido por dois vetores ortogonais e . A variação total nesse plano éPortanto, é uma combinação linear de autovalores com coeficientes todos positivos, que não excedem (veja abaixo) e somam . Nesse caso, é quase óbvio que o máximo é atingido em . $\mathbf{u}$ $\mathbf{v}$

u^{⊤} Σ u + v^{⊤} Σ v = \sum λ_{i} u_{i}^{2} + \sum λ_{i} v_{i}^{2} = \sum λ_{i} (u_{i}^{2} + v_{i}^{2}) .

$\mathbf{u}^\top\boldsymbol{\Sigma}\mathbf{u} + \mathbf{v}^\top\boldsymbol{\Sigma}\mathbf{v} = \sum \lambda_i u_i^2 + \sum \lambda_i v_i^2 = \sum \lambda_i (u_i^2+v_i^2).$

λ_{i}

$\lambda_i$

1

$1$

2

$2$

λ_{1} + λ_{2}

$\lambda_1 + \lambda_2$

Só resta mostrar que os coeficientes não podem exceder . Observe que , onde é o ésimo vetor base. Essa quantidade é um comprimento ao quadrado de uma projeção de no plano medido por e . Portanto, ele deve ser menor que o comprimento ao quadrado de que é igual a , QED. $1$ $u_k^2+v_k^2 = (\mathbf{u}\cdot\mathbf{k})^2+(\mathbf{v}\cdot\mathbf{k})^2$ $\mathbf{k}$ $k$ $\mathbf k$ $\mathbf u$ $\mathbf v$ $\mathbf k$ $|\mathbf{k}|^2=1$

Veja também a resposta do @ cardinal para Qual é a função objetivo do PCA? (segue a mesma lógica).

ameba
fonte

(+1) Mas não é intuitivamente óbvio que, dada uma coleção de carteiras de várias quantias de dinheiro (modelando os autovalores não negativos) e um número fixo que você possa escolher, a seleção das carteiras mais ricas maximizará seu total dinheiro? A prova de que essa intuição está correta é quase trivial: se você não obteve o maior , pode melhorar sua soma trocando o menor que você tomou por um valor maior.

k

$k$

k

$k$

k

$k$

whuber

@amoeba: se o objetivo é maximizar a soma das variações e não a variação da soma, não há razão para a segunda projeção ser ortogonal à primeira.

Innuo

Peço desculpas - pensei que você já tivesse desenvolvido a análise a ponto de reconhecer que a variação total em um subespaço dimensional é uma combinação linear não negativa dos autovalores, na qual nenhum dos coeficientes pode exceder e o o total dos coeficientes é igual a . (Trata-se de uma simples multiplicação de matrizes - os multiplicadores Lagrange não são necessários.) Isso nos leva à metáfora das carteiras. Concordo que algumas dessas análises precisam ser feitas.

k

$k$

1

$1$

k

$k$

whuber

@amoeba: Quero dizer, estamos considerando o problema na base que consiste em vetores próprios (essa é a base de u e v se calcularmos sua variância multiplicando pela matriz de covariância diagonal). uev serão, no final, eles, mas no estágio desta prova não devemos assumir isso, eu acho. Não deveria ser o argumento de que, se em algum momento a soma fosse maior que 1, os 2 vetores não seriam mais ortogonais, já que a base é ortogonal e cada um dos vetores traz no máximo 1? Mas, novamente, por que nos restringimos aos vetores ortogonais u e v?

Michal

@Heisenberg: Ah, entendo! Não, é claro que eu não quis dizer isso! Mas agora vejo por que era confuso. Reescrevi este último trecho da prova para me livrar dessa etapa de "escolher uma base". Por favor, veja minha edição. Obrigado.

Ameba

Se você tiver variáveis aleatórias não correlacionadas classificadas em ordem decrescente de sua variância e for solicitado a escolher delas, de modo que a variação de sua soma seja maximizada, você concorda que a abordagem gananciosa de escolher o primeiro conseguiria isso? $N$ $k$ $k$

Os dados projetados nos autovetores de sua matriz de covariância são essencialmente colunas de dados não correlacionadas e cuja variação é igual aos respectivos autovalores. $N$

Para que a intuição seja mais clara, precisamos relacionar a maximização da variação com o cálculo do vetor próprio da matriz de covariância com o maior valor próprio e relacionar a projeção ortogonal à remoção de correlações.

A segunda relação é clara para mim porque o coeficiente de correlação entre dois vetores (média zero) é proporcional ao seu produto interno.

A relação entre a maximização da variância e a decomposição por eigen da matriz de covariância é a seguinte.

Suponha que é a matriz de dados após centralizar as colunas. Precisamos encontrar a direção da variação máxima. Para qualquer vetor de unidade , a variação após a projeção ao longo de é $D$ $v$ $v$

$E[(Dv)^t Dv] = v^t E[D^tD] v = v^t Cov(D) v$

que é maximizado se é o vetor próprio de correspondente ao maior valor próprio. $v$ $Cov(D)$

Innuo
fonte

A questão original é: escolha combinações lineares ortogonais delas (em oposição a delas) de modo que a soma de suas variações seja maximizada. Ainda é óbvio que a abordagem gananciosa de escolher o primeiro isso?

k

$k$

k

$k$

k

$k$

Ameba

Encontrar combinações lineares ortogonais e depois escolher a primeira variante mais delas é o que o processo descreve (vagamente). Minha resposta apenas afirma que a ortogonalidade é suficiente para que o processo ganancioso atinja o objetivo de maximizar a variação total.

N

$N$

k

$k$

Innuo

Não tenho certeza se sigo o argumento. Como a ortogonalidade importa? Se você tiver variáveis e precisar escolher com a variação total mais alta, deverá escolher com a variação mais alta (independentemente de elas estarem correlacionadas ou não).

N

$N$

k

$k$

k

$k$

ameba

Ah, eu entendo a confusão. Houve um erro de digitação na minha resposta. Corrigido agora.

Innuo

Eu acho que você pode estar interessado em algo aqui, mas a aparência mágica da soma precisa ser explicada. Que relevância isso tem para o PCA ou mesmo para decomposições espectrais?

whuber