Qual é a função objetivo do PCA?

A análise de componentes principais pode usar a decomposição da matriz, mas isso é apenas uma ferramenta para chegar lá.

Como você encontraria os principais componentes sem o uso de álgebra matricial?

Qual é a função objetivo (objetivo) e quais são as restrições?

pca Neil McGuigan
fonte

Talvez esteja faltando alguma coisa, por favor, corrija-me se estiver errado, mas deve ser possível (pelo menos em princípio) construir o que é feito no PCA usando matrizes como um problema de programação linear (complicado), mas não saiba como você declararia todas as restrições necessárias. Também não tenho certeza de que seria muito simples de fazer, em comparação com apenas o uso do PCA. Por que você está tentando evitar matrizes?

Chris Simokat

@ Chris Não vejo como se pode chegar a um problema de programação linear. Também não entendi que matrizes deveriam ser evitadas no cálculo . A questão era que tipo de problema é resolvido pelo PCA, e não da maneira como é feito (calculando o SVD, por exemplo). A solução do cardeal diz que você encontra direções ortogonais sucessivas de variação máxima . A solução que apresentei diz que você encontra hiperplanos com o mínimo de erro de reconstrução.

NRH

@chris Espero encontrar outra maneira de visualizar o PCA, sem a álgebra matricial, para aumentar minha compreensão.

Neil McGuigan

@ Chris, você tem uma função de objetivo quadrático e uma restrição de igualdade de norma . Como alternativa, na formulação da resposta da @ NRH, você tem uma restrição de classificação da matriz. Isso não vai acabar com um problema de programação linear. O @NRH fornece uma boa intuição e, de fato, existe uma conexão muito estreita entre as duas perspectivas que foram dadas no PCA. Talvez em colaboração com o @NRH, possamos adicioná-lo ao seu post para tornar o conjunto completo de respostas mais completo.

ℓ_{2}

$\ell_2$

cardeal

@NRH, na verdade, eu gosto muito de ESL , mas acho que o tratamento desse tópico é bastante superficial, assim como ocorre com muitos dos tópicos do livro. Em particular, eles não provam (ou mesmo atribuem como exercício) a parte importante da solução para o problema de otimização que você fornece.

cardeal

Respostas:

Sem tentar fornecer um iniciador completo no PCA, do ponto de vista da otimização, a principal função objetivo é o quociente de Rayleigh . A matriz que figura no quociente é (alguns múltiplos) da matriz de covariância de amostra onde cada é um vector de características e é a matriz de tal modo que a -ésima linha é .

S = \frac{1}{n} \sum_{i = 1}^{n} x_{i} x_{i}^{T} = X^{T} X / n

$\newcommand{\m}[1]{\mathbf{#1}}\newcommand{\x}{\m{x}}\newcommand{\S}{\m{S}}\newcommand{\u}{\m{u}}\newcommand{\reals}{\mathbb{R}}\newcommand{\Q}{\m{Q}}\newcommand{\L}{\boldsymbol{\Lambda}} \S = \frac{1}{n} \sum_{i=1}^n \x_i \x_i^T = \m{X}^T \m{X} / n$

x_{i}

$\x_i$

p

$p$

X

$\m{X}$

i

$i$

x_{i}^{T}

$\x_i^T$

O PCA procura resolver uma sequência de problemas de otimização. O primeiro da sequência é o problema irrestrito

\begin{array}{ll} maximize & \frac{u^{T} S u}{u^{T} u}, u \in R^{p} . \end{array}

$\begin{array}{ll} \text{maximize} & \frac{\u^T \S \u}{\u^T\u} \;, \u \in \reals^p \> . \end{array}$

Desde, o problema irrestrito acima é equivalente ao problema restrito $\u^T \u = \|\u\|_2^2 = \|\u\| \|\u\|$

\begin{array}{ll} maximize & u^{T} S u \\ subject to & u^{T} u = 1 . \end{array}

$\begin{array}{ll} \text{maximize} & \u^T \S \u \\ \text{subject to} & \u^T \u = 1 \>. \end{array}$

Aqui é onde a álgebra da matriz entra. Como é uma matriz semidefinida positiva simétrica (por construção!), Ela tem uma decomposição de autovalor da forma onde é matriz ortogonal (então ) e é uma matriz diagonal com entradas não-negativas tais que . $\S$

S = Q Λ Q^{T},

$\S = \Q \L \Q^T \>,$

Q

$\Q$

Q Q^{T} = I

$\Q \Q^T = \m{I}$

Λ

$\L$

λ_{i}

$\lambda_i$

λ_{1} \geq λ_{2} \geq \dots \geq λ_{p} \geq 0

$\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_p \geq 0$

Portanto, . Como está restrito no problema a ter uma norma de um, também o é pois , em virtude de ser ortogonal. $\u^T \S \u = \u^T \Q \L \Q^T \u = \m{w}^T \L \m{w} = \sum_{i=1}^p \lambda_i w_i^2$ $\u$ $\m{w}$ $\|\m{w}\|_2 = \|\Q^T \u\|_2 = \|\u\|_2 = 1$ $\Q$

Mas, se queremos maximizar a quantidade sob as restrições que , o melhor que podemos fazer é: defina , ou seja, e para . $\sum_{i=1}^p \lambda_i w_i^2$ $\sum_{i=1}^p w_i^2 = 1$ $\m{w} = \m{e}_1$ $w_1 = 1$ $w_i = 0$ $i > 1$

Agora, retornando o correspondente , que é o que buscamos em primeiro lugar, obtemos que onde indica a primeira coluna de , isto é, o vector próprio correspondente ao maior valor próprio de . O valor da função objetivo também é facilmente visto como . $\u$

u^{⋆} = Q e_{1} = q_{1}

$\u^\star = \Q \m{e}_1 = \m{q}_1$

q_{1}

$\m{q}_1$

Q

$\Q$

S

$\S$

λ_{1}

$\lambda_1$

Os vetores de componentes principais restantes são encontrados resolvendo a sequência (indexada por ) dos problemas de otimização Portanto, o problema é o mesmo, exceto que adicionamos a restrição adicional de que a solução deve ser ortogonal a todas as soluções anteriores na sequência. Não é difícil estender a discussão acima indutivamente para mostrar que a solução do th problema é, de facto, , o th vector próprio de . $i$

\begin{array}{ll} maximize & u_{i}^{T} S u_{i} \\ subject to & u_{i}^{T} u_{i} = 1 \\ u_{i}^{T} u_{j} = 0 \forall 1 \leq j < i . \end{array}

$\begin{array}{ll} \text{maximize} & \u_i^T \S \u_i \\ \text{subject to} & \u_i^T \u_i = 1 \\ & \u_i^T \u_j = 0 \quad \forall 1 \leq j < i\>. \end{array}$

i

$i$

q_{i}

$\m{q}_i$

i

$i$

S

$\S$

A solução PCA também é frequentemente expressa em termos da decomposição de valor singular de . Para ver por isso, deixe . Então e então (estritamente falando, até assinar flips) e . $\m{X}$ $\m{X} = \m{U} \m{D} \m{V}^T$ $n \S = \m{X}^T \m{X} = \m{V} \m{D}^2 \m{V}^T$ $\m{V} = \m{Q}$ $\L = \m{D}^2 / n$

Os componentes principais são encontrados projetando nos vetores dos componentes principais. A partir da formulação SVD apresentada, é fácil ver que $\m{X}$

X Q = X V = U D V^{T} V = U D .

$\m{X} \m{Q} = \m{X} \m{V} = \m{U} \m{D} \m{V}^T \m{V} = \m{U} \m{D} \> .$

A simplicidade de representação dos vetores de componentes principais e dos próprios componentes principais em termos do SVD da matriz de recursos é um dos motivos pelos quais o SVD apresenta tanto destaque em alguns tratamentos de PCA.

cardeal
fonte

Se apenas os primeiros valores / vetores singulares forem necessários, Nash e Shlien fornecerão um algoritmo remanescente do método de potência usual para calcular valores próprios dominantes. Isso pode ser do interesse do OP.

JM não é estatístico

@ NRH, obrigado por capturar (e corrigir) meus erros de digitação antes que eu conseguisse vê-los!

cardeal

Olá @ cardinal, obrigado pela sua resposta. Mas parece que você não deu o passo de provar por que a otimização seqüencial leva a um ótimo global. Poderia, por favor, elaborar sobre isso? Obrigado!

Lifu Huang

A solução apresentada pelo cardeal concentra-se na matriz de covariância da amostra. Outro ponto de partida é o erro de reconstrução dos dados por um hiperplano q- dimensional. Se os pontos de dados p- dimensionais são o objetivo é resolver $x_1, \ldots, x_n$

min_{μ, λ_{1}, \dots, λ_{n}, V_{q}} \sum_{i = 1}^{n} | | x_{i} - μ - V_{q} λ_{i} | |^{2}

$\min_{\mu, \lambda_1,\ldots, \lambda_n, \mathbf{V}_q} \sum_{i=1}^n ||x_i - \mu - \mathbf{V}_q \lambda_i||^2$

para uma matriz com colunas ortonormais e . Isso fornece a melhor classificação q- reconstrução conforme medido pela norma euclidiana, e as colunas da solução são os primeiros q vetores de componentes principais. $p \times q$ $\mathbf{V}_q$ $\lambda_i \in \mathbb{R}^q$ $\mathbf{V}_q$

Para a solução para e (isso é regressão) é $\mathbf{V}_q$ $\mu$ $\lambda_i$

μ = \bar{x} = \frac{1}{n} \sum_{i = 1}^{n} x_{i} λ_{i} = V_{q}^{T} (x_{i} - \bar{x})

$\mu = \overline{x} = \frac{1}{n}\sum_{i=1}^n x_i \qquad \lambda_i = \mathbf{V}_q^T(x_i - \overline{x})$

Para facilitar a notação, vamos supor que tenha sido centralizado nos cálculos a seguir. Temos então que minimizar $x_i$

\sum_{i = 1}^{n} | | x_{i} - V_{q} V_{q}^{T} x_{i} | |^{2}

$\sum_{i=1}^n ||x_i - \mathbf{V}_q\mathbf{V}_q^T x_i||^2$

sobre com colunas ortonormais. Observe que é a projeção no espaço da coluna q- dimensional. Portanto, o problema é equivalente a minimizar ao longo do posto de q projecções . Ou seja, precisamos maximizar sobre a classificação q projeções , onde é a matriz de covariância de amostra. Agora $\mathbf{V}_q$ $P = \mathbf{V}_q\mathbf{V}_q^T$

\sum_{i = 1}^{n} | | x_{i} - P x_{i} | |^{2} = \sum_{i = 1}^{n} | | x_{i} | |^{2} - \sum_{i = 1}^{n} | | P x_{i} | |^{2}

$\sum_{i=1}^n ||x_i - P x_i||^2 = \sum_{i=1}^n ||x_i||^2 - \sum_{i=1}^n||Px_i||^2$

P

$P$

\sum_{i = 1}^{n} | | P x_{i} | |^{2} = \sum_{i = 1}^{n} x_{i}^{T} P x_{i} = tr (P \sum_{i = 1}^{n} x_{i} x_{i}^{T}) = n tr (P S)

$\sum_{i=1}^n||Px_i||^2 = \sum_{i=1}^n x_i^TPx_i = \text{tr}(P \sum_{i=1}^n x_i x_i^T) = n \text{tr}(P \mathbf{S})$

P

$P$

S

$\mathbf{S}$

tr (P S) = tr (V_{q}^{T} S V_{q}) = \sum_{i = 1}^{q} u_{i}^{T} S u_{i}

$\text{tr}(P\mathbf{S}) = \text{tr}(\mathbf{V}_q^T\mathbf{S}\mathbf{V}_q) = \sum_{i=1}^q u_i^T \mathbf{S} u_i$ onde são as colunas (ortonormais) em , e os argumentos apresentados na resposta do @ cardinal mostram que o máximo é obtido usando o ' s são vetores próprios para com os maiores valores próprios.

u_{1}, \dots, u_{q}

$u_1, \ldots, u_q$

q

$q$

V_{q}

$\mathbf{V}_q$

u_{i}

$u_i$

q

$q$

S

$\mathbf{S}$

q

$q$

O erro de reconstrução sugere uma série de generalizações úteis, por exemplo, componentes principais esparsos ou reconstruções por variedades de baixa dimensão em vez de hiperplanos. Para detalhes, consulte a Seção 14.5 em Os elementos do aprendizado estatístico .

NRH
fonte

(+1) Bons pontos. Algumas sugestões: Seria bom definir e seria muito bom fornecer uma prova curta do resultado. Ou, alternativamente, pode ser conectado ao problema de otimização que envolve os quocientes de Rayleight. Eu acho que isso tornaria as respostas para essa pergunta muito completas!

λ_{i}

$\lambda_i$

cardeal

@ cardinal, acredito que concluí as etapas que faltam para passar da formulação de reconstrução para o problema que você resolve.

NRH

Bom trabalho. Acredito que a única lacuna restante esteja em sua última declaração. Não é imediatamente aparente que otimizar a soma é o mesmo que executar a sequência de otimizações na minha resposta. Na verdade, acho que não segue diretamente, em geral. Mas, também não precisa ser abordado aqui.

cardeal

@ cardinal, segue por indução. Você fornece o início da indução e, na etapa de indução, escolha vetores ortonormais que maximizem a soma e organize-os para que seja um vetor unitário ortogonal a . Então, pelos seus resultados e pela suposição de indução . Obviamente, a base não é única para o espaço dimensional. Você também pode generalizar o "argumento de combinação convexa" usado para fornecer uma prova direta.

w_{1}, \dots, w_{q}

$w_1, \ldots, w_q$

w_{q}

$w_q$

u_{1}, \dots, u_{q - 1}

$u_1, \ldots, u_{q-1}$

w_{q}^{T} S w_{q} \leq u_{q}^{T} S u_{q}

$w_q^T \mathbf{S} w_q \leq u_q^T \mathbf{S} u_q$

\sum_{i = 1}^{q - 1} w_{i}^{T} S w_{i} \leq \sum_{i = 1}^{q - 1} u_{i}^{T} S u_{i}

$\sum_{i=1}^{q-1} w_i^T \mathbf{S} w_i \leq \sum_{i=1}^{q-1}u_i^T \mathbf{S} u_i$

q

$q$

NRH

@ cardinal, não estou forçando um aninhamento, apenas usando uma consideração de dimensão. Se tivermos um subespaço dimensional, você sempre poderá escolher nesse espaço, de modo que seja ortogonal a um subespaço -dimensional. Então você preenche a base da maneira que quiser.

q

$q$

w_{q}

$w_q$

(q - 1)

$(q-1)$

w

$w$

NRH

Veja NIPALS ( wiki ) para um algoritmo que não usa explicitamente uma decomposição de matriz. Suponho que é isso que você quer dizer quando diz que deseja evitar álgebra matricial, já que realmente não pode evitar álgebra matricial aqui :)

JMS
fonte