Qual é uma explicação intuitiva de como o PCA passa de um problema geométrico (com distâncias) para um problema de álgebra linear (com vetores próprios)?

54

Eu li muito sobre o PCA, incluindo vários tutoriais e perguntas (como este , este , este e este ).

O problema geométrico que o PCA está tentando otimizar é claro para mim: o PCA tenta encontrar o primeiro componente principal minimizando o erro de reconstrução (projeção), que maximiza simultaneamente a variação dos dados projetados.

insira a descrição da imagem aqui

Quando li isso pela primeira vez, pensei imediatamente em algo como regressão linear; talvez você possa resolvê-lo usando a descida gradiente, se necessário.

No entanto, minha mente ficou abalada quando li que o problema de otimização é resolvido usando álgebra linear e encontrando autovetores e autovalores. Simplesmente não entendo como esse uso da álgebra linear entra em jogo.

Portanto, minha pergunta é: como o PCA pode passar de um problema de otimização geométrica para um problema de álgebra linear? Alguém pode fornecer uma explicação intuitiva?

Não estou procurando uma resposta como esta que diga "Quando você resolve o problema matemático do PCA, acaba sendo equivalente a encontrar os autovalores e autovetores da matriz de covariância". Por favor, explique por que os autovetores são os principais componentes e por que os autovalores são uma variação dos dados projetados neles

Eu sou um engenheiro de software e não um matemático, a propósito.

Nota: a figura acima foi obtida e modificada neste tutorial do PCA .

stackoverflowuser2010
fonte
2
No longo tópico por trás do seu primeiro link, há a resposta da @ amoeba com animação, que explica o principal. PCA é a rotação dos eixos de dados (colunas) até que eles não se correlacionem como vetores de dados (variáveis). Essa matriz de rotação é encontrada via composição automática ou decomposição de valor singular e é chamada matriz de vetor próprio.
ttnphns
2
Além disso, mesmo que você não seja um matemático (eu também não sou), você provavelmente já ouviu falar sobre a álgebra linear e a geometria euclidiana como campos da matemática intimamente ligados; eles são até estudados juntos como uma disciplina chamada geometria analítica.
precisa saber é o seguinte
11
optimization problemSim, o problema do PCA poderia ser resolvido por meio de abordagens de otimização (iterativas, convergentes), acredito. Mas como ele encerrou a solução de formulário via matemática, por que não usar essa solução mais simples e eficiente?
precisa saber é o seguinte
Você pede provide an intuitive explanation. Eu me pergunto por que a resposta intuitiva e clara da ameba, a que me vinculei, não combina com você. Você pergunta por _why_ eigenvectors come out to be the principal components...quê? Por definição! Os autovetores são as principais direções de uma nuvem de dados.
ttnphns
6
@ttnphns: Na verdade, acho que a pergunta é razoável. Aqui está como eu entendo isso. O PCA deseja encontrar a direção da variação máxima da projeção. Essa direção é chamada (por definição) a primeira direção principal. Por outro lado, um vetor próprio da matriz de covariância é (por definição) esse vetor que . Então, por que a primeira direção principal é dada pelo vetor próprio com o maior valor próprio? Qual é a intuição aqui? Certamente não é por definição. Eu estive pensando sobre isso e sei como provar isso, mas é difícil de explicar intuitivamente. w C w = λ wCwCw=λw
Ameba diz Restabelecer Monica

Respostas:

54

Declaração do problema

O problema geométrico que o PCA está tentando otimizar é claro para mim: o PCA tenta encontrar o primeiro componente principal minimizando o erro de reconstrução (projeção), que maximiza simultaneamente a variação dos dados projetados.

Está certo. Explico a conexão entre essas duas formulações na minha resposta aqui (sem matemática) ou aqui (com matemática).

Vamos tomar a segunda formulação: o PCA está tentando encontrar a direção de modo que a projeção dos dados contenha a maior variação possível. Essa direção é, por definição, chamada de primeira direção principal. Podemos formalizá-lo da seguinte forma: dada a matriz de covariância , estamos procurando por um vetor com comprimento unitário, , tal que é o máximo.Cww=1wCw

(Caso isso não esteja claro: se é a matriz de dados centralizada, a projeção é dada por e sua variação é .)XXw1n1(Xw)Xw=w(1n1XX)w=wCw

Por outro lado, um vetor próprio de é, por definição, qualquer vetor tal que .CvCv=λv

Acontece que a primeira direção principal é dada pelo vetor próprio com o maior valor próprio. Esta é uma afirmação não trivial e surpreendente.


Provas

Se alguém abrir um livro ou tutorial sobre o PCA, poderá encontrar a seguinte prova de quase uma linha da declaração acima. Queremos maximizar sob a restrição de que ; isso pode ser feito introduzindo um multiplicador Lagrange e maximizando ; diferenciando, obtemos , que é a equação do vetor próprio. Vemos que tem de fato o maior autovalor substituindo essa solução na função objetivo, que fornecewCww=ww=1wCwλ(ww1)Cwλw=0λwCwλ(ww1)=wCw=λww=λ . Em virtude do fato de que essa função objetivo deve ser maximizada, deve ser o maior autovalor, QED.λ

Isso tende a não ser muito intuitivo para a maioria das pessoas.

Uma prova melhor (veja, por exemplo, essa resposta elegante de @ cardinal ) diz que, como é uma matriz simétrica, é diagonal em sua base de vetor próprio. (Na verdade, isso é chamado de teorema espectral .) Portanto, podemos escolher uma base ortogonal, a que é fornecida pelos vetores próprios, em que é diagonal e tem valores próprios na diagonal. Nessa base, simplifica para , ou seja, a variação é dada pela soma ponderada dos valores próprios. É quase imediato que, para maximizar essa expressão, seja necessário simplesmenteCCλiwCwλiwi2w=(1,0,0,,0), ou seja, o primeiro vetor próprio, gerando variação (na verdade, desviar-se dessa solução e "negociar" partes do maior valor próprio pelas partes de menores resultará apenas em menor variação geral). Observe que o valor de não depende da base! Mudar para a base do vetor próprio equivale a uma rotação; portanto, em 2D, pode-se imaginar simplesmente girando um pedaço de papel com o gráfico de dispersão; obviamente isso não pode alterar nenhuma variação.λ1wCw

Penso que este é um argumento muito intuitivo e muito útil, mas se baseia no teorema espectral. Então, a questão real aqui que penso é: qual é a intuição por trás do teorema espectral?


Teorema espectral

Tomar uma matriz simétrica . Pegue seu vetor próprio com o maior valor próprio . Torne esse vetor próprio o primeiro vetor base e escolha outros vetores base aleatoriamente (de modo que todos sejam ortonormais). Como o ficará nesta base?Cw1λ1C

Ele terá no canto superior esquerdo, porque nessa base e deve ser igual a .λ1w1=(1,0,00)Cw1=(C11,C21,Cp1)λ1w1=(λ1,0,00)

Pelo mesmo argumento, ele terá zeros na primeira coluna sob o .λ1

Mas, por ser simétrica, também haverá zeros na primeira linha após . Então será assim:λ1

C=(λ10000),

onde espaço vazio significa que há um bloco de alguns elementos lá. Como a matriz é simétrica, esse bloco também será simétrico. Assim, podemos aplicar exatamente o mesmo argumento, usando efetivamente o segundo vetor próprio como o segundo vetor base e obtendo e na diagonal. Isso pode continuar até que seja diagonal. Esse é essencialmente o teorema espectral. (Observe como ele funciona apenas porque é simétrico.)λ1λ2CC


Aqui está uma reformulação mais abstrata exatamente do mesmo argumento.

Sabemos que ; portanto, o primeiro vetor próprio define um subespaço unidimensional em que atua como uma multiplicação escalar. Vamos agora pegar qualquer vetor ortogonal para . Então é quase imediato que também seja ortogonal a . De fato:Cw1=λ1w1Cvw1Cvw1

w1Cv=(w1Cv)=vCw1=vCw1=λ1vw1=λ10=0.

Isso significa que atua em todo o subespaço restante ortogonal a modo que permaneça separado de . Essa é a propriedade crucial das matrizes simétricas. Assim, podemos encontrar o maior vetor próprio, , e proceder da mesma maneira, eventualmente construindo uma base ortonormal de vetores próprios.Cw1w1w2

ameba diz Restabelecer Monica
fonte
"Multiplicador de Lagrange" é realmente claro para mim. No entanto, você poderia me dizer por que precisamos de uma restrição de comprimento da unidade? Obrigado
Haitao Du
2
@ hxd1011 Já existe exatamente essa pergunta aqui, mas brevemente: é porque, caso contrário, você pode multiplicar por qualquer número e aumentará pelo quadrado desse número. Portanto, o problema fica mal definido: o máximo dessa expressão é infinito. De fato, a variação da projeção na direção de é apenas se for o comprimento da unidade. wwCwwwCww
Ameba diz Reinstate Monica
Eu acho que o pode ser um pouco mais familiar para a maioria dos leitores; Troquei aqui. Obrigado. n1
Ameba diz Reinstate Monica
@amoeba: Obrigado pela resposta. Estou confuso com algumas das suas anotações. Você usa w para indicar o vetor de comprimento unitário que acaba sendo o primeiro vetor próprio (componente principal). Quando executo o PCA em R (por exemplo prcomp(iris[,1:4], center=T, scale=T)), vejo autovetores de tamanho unitário com vários carros alegóricos como (0.521, -0.269, 0.580, 0.564). No entanto, em sua resposta em "Provas", você escreve. É quase imediato que, para maximizar essa expressão, basta tomar w = (1,0,0, ..., 0), ou seja, o primeiro vetor próprio . Por que o vetor próprio em sua prova parece tão bem formado assim?
stackoverflowuser2010
11
Oi @ user58865, obrigado pela cutucada: simplesmente esqueci de responder pela primeira vez. O mais fino é que é um escalar - é apenas um número. Qualquer número é "simétrico" :) e é igual à sua transposição. Isso faz sentido? w1Cv
Ameba diz Reinstate Monica
5

Há um resultado de 1936 de Eckart and Young ( https://ccrma.stanford.edu/~dattorro/eckart%26young.1936.pdf ), que declara o seguinte

1rdkukvkT=argminX^ϵM(r)||XX^||F2

onde M (r) é o conjunto de matrizes rank-r, que basicamente significa que os primeiros componentes r de SVD de X fornecem a melhor aproximação de matriz de baixo escalão de X e melhor é definido em termos da norma de Frobenius ao quadrado - a soma do quadrado elementos de uma matriz.

Este é um resultado geral para matrizes e, à primeira vista, não tem nada a ver com conjuntos de dados ou redução de dimensionalidade.

No entanto, se você não pensa em como uma matriz, mas pensa nas colunas da matriz representando vetores de pontos de dados, é a aproximação com o erro mínimo de representação em termos de diferenças de erro ao quadrado.XXX^

Cagdas Ozgenc
fonte
4

Esta é a minha opinião sobre a álgebra linear por trás do PCA. Na álgebra linear, um dos principais teoremas é o . Ele afirma que S é qualquer matriz simétrica n por n com coeficientes reais, então S possui n vetores próprios com todos os valores próprios reais. Isso significa que podemos escrever com D uma matriz diagonal com entradas positivas. Isso é e não há mal em assumir . A é a matriz de mudança de base. Ou seja, se nossa base original fosse , em relação à base fornecida porSpectral TheoremS=ADA1D=diag(λ1,λ2,,λn)λ1λ2λnx1,x2,,xnA(x1),A(x2),A(xn), a ação de S é diagonal. Isso também significa que o pode ser considerado uma base ortogonal com Se nossa matriz de covariância fosse para n observações de n variáveis, estaríamos prontos. A base fornecida pelo é a base do PCA. Isso decorre dos fatos da álgebra linear. Em essência, é verdade porque uma base PCA é uma base de vetores próprios e existem no máximo n vetores próprios de uma matriz quadrada de tamanho n. Obviamente, a maioria das matrizes de dados não é quadrada. Se X é uma matriz de dados com n observações de variáveis ​​p, X é do tamanho n por p. Assumirei que (mais observações que variáveis) e queA(xi)||A(xi)||=λiA(xi)
n>prk(X)=p(todas as variáveis ​​são linearmente independentes). Nenhuma suposição é necessária, mas ajudará na intuição. A álgebra linear tem uma generalização a partir do teorema espectral chamado decomposição de valor singular. Para um X assim, afirma que com matrizes U, V ortonormais (quadradas) de tamanho ne ep uma matriz diagonal real com apenas não-negativas entradas na diagonal. Novamente, podemos reorganizar a base de V para que Em termos matriciais, isso significa que se e se . OX=UΣVtΣ=(sij)s11s22spp>0X(vi)=siiuiipsii=0i>nvidê a decomposição do PCA. Mais precisamente é a decomposição do PCA. Por que? Novamente, a álgebra linear diz que só pode haver vetores auto. O SVD fornece novas variáveis ​​(dadas pelas colunas de V) ortogonais e com norma decrescente. ΣVt

aginensky
fonte
4

"que maximiza simultaneamente a variação dos dados projetados". Você já ouviu falar do quociente de Rayleigh ? Talvez seja uma maneira de ver isso. Nomeadamente, o quociente rayleigh da matriz de covariância fornece a variação dos dados projetados. (e a página da wiki explica por que os vetores próprios maximizam o quociente de Rayleigh)

seanv507
fonte
1

O @amoeba oferece uma formalização e prova de:

Podemos formalizar-lo da seguinte maneira: dada a matriz covariância C, estamos em busca de um vector w tendo unidade de comprimento, ‖w‖ = 1, de tal modo que w t Cw é máxima.

Mas acho que há uma prova intuitiva para:

Acontece que a primeira direção principal é dada pelo vetor próprio com o maior valor próprio. Esta é uma afirmação não trivial e surpreendente.

Podemos interpretar w T Cw como um produto escalar entre o vetor we Cw, que é obtido por w passando pela transformação C:

w T Cw = "w" * "Cw" * cos (w, Cw)

Desde w tem comprimento correção, para maximizar w T CW, nós precisamos:

  1. maximizar "Cw"
  2. maximizar cos (w, Cw)

Se considerarmos que w é autovetor de C com o maior autovalor, podemos arquivar os dois simultaneamente:

  1. "Cw" é máximo (se você se desviar desse vetor próprio, decompô-lo ao longo dos vetores ortogonais, você deverá ver "Cw" diminuindo).
  2. w e Cw na mesma direção, cos (w, Cw) = 1, max

Como os autovetores são ortogonais, juntamente com os outros autovetores de C, eles formam um conjunto de componentes principais para X.


prova de 1

decompondo w no vetor próprio ortogonal primário e secundário v1 e v2 , suponha que seu comprimento seja v1 e v2 respectivamente. queremos provar

1 w) 2 > ((λ 1 v1) 2 + (λ 2 v2) 2 )

desde λ 1 > λ 2 , temos

((λ 1 v1) 2 + (λ 2 v2) 2 )

<((λ 1 v1) 2 + (λ 1 v2) 2 )

= (λ 1 ) 2 * (v1 2 + v2 2 )

= (λ 1 ) 2 * w 2

Céu
fonte