Função objetivo do PCA: qual é a conexão entre maximizar a variação e minimizar o erro?

O algoritmo PCA pode ser formulado em termos da matriz de correlação (suponha que os dados $X$ já tenham sido normalizados e estamos considerando apenas a projeção no primeiro PC). A função objetivo pode ser escrita como:

max_{w} (X w)^{T} (X w) s.t. w^{T} w = 1.

$\max_w (Xw)^T(Xw)\; \: \text{s.t.} \: \:w^Tw = 1.$

Isso é bom e usamos multiplicadores lagrangianos para resolvê-lo, ou seja, reescrevendo-o como:

max_{w} [(X w)^{T} (X w) - λ w^{T} w],

$\max_w [(Xw)^T(Xw) - \lambda w^Tw],$

que é equivalente a

max_{w} \frac{(X w)^{T} (X w)}{w^{T} w},

$\max_w \frac{ (Xw)^T(Xw) }{w^Tw},$

e, portanto, ( veja aqui no Mathworld ) parece ser igual a

max_{w} \sum_{i = 1}^{n} {(distance from point x_{i} to line w)}^{2} .

$\max_w \sum_{i=1}^n \text{(distance from point $x_i$ to line $w$)}^2.$

Mas isso significa maximizar a distância entre ponto e linha e, pelo que li aqui , isso está incorreto - deve ser $\min$ , não $\max$ . Onde está o meu erro?

Ou alguém pode me mostrar o elo entre maximizar a variação no espaço projetado e minimizar a distância entre ponto e linha?

pca optimization Cam.Davidson.Pilon
fonte

Eu acho que a distância mínima é usada para atender ao critério de ortogonalidade dos componentes. Os pontos são projetados nos PCs que são ortogonais entre si, mas em cada componente sucessivo a variação restante é maximizada.

Michael R. Chernick

Dica: O que acontece quando você considera o menor autovalor primeiro, e não o maior?

whuber

@whuber O menor valor próprio provavelmente tem o PC que é a solução para a função objetivo final. Mas este PC não maximiza a função objetivo original.

68468 Camdavidson.Pilon 12/12/12

Não sei ao certo o que você quer dizer com função objetivo "final" e "original", Cam. O PCA não é (conceitualmente) um programa de otimização. Sua saída é um conjunto de direções principais, não apenas uma. É um teorema matemático (interessante) que essas direções podem ser encontradas através da resolução de uma sequência de programas quadráticos restritos, mas isso não é básico para os conceitos ou a prática do PCA. Estou apenas sugerindo que, concentrando-se no menor autovalor, e não no maior, é possível reconciliar as duas idéias de (1) minimizar distâncias e (2) adotar uma visão de otimização do PCA.

whuber

Tudo bem - sua resposta foi a versão sem erros do que eu estava tentando fazer.

Cam.Davidson.Pilon

Respostas:

Seja uma matriz de dados centralizada com observações em linhas. Seja seja sua matriz de covariância. Seja um vetor unitário especificando um eixo no espaço variável. Queremos que seja o primeiro eixo principal. $\newcommand{\X}{\mathbf X}\X$ $n$ $\newcommand{\S}{\boldsymbol \Sigma}\S=\X^\top\X/(n-1)$ $\newcommand{\w}{\mathbf w}\w$ $\w$

$\X \w$

V a r (X w) = w^{⊤} X^{⊤} X w / (n - 1) = w^{⊤} Σ w .

$\mathrm{Var}(\X\w)=\w^\top\X^\top \X \w/(n-1)=\w^\top\S\w.$

$\X$ $\X\w\w^\top$ $\w$

\begin{aligned} ‖ X - X w w^{⊤} ‖^{2} & = t r ((X - X w w^{⊤}) (X - X w w^{⊤})^{⊤}) \\ = t r ((X - X w w^{⊤}) (X^{⊤} - w w^{⊤} X^{⊤})) \\ = t r (X X^{⊤}) - 2 t r (X w w^{⊤} X^{⊤}) + t r (X w w^{⊤} w w^{⊤} X^{⊤}) \\ = c o n s t - t r (X w w^{⊤} X^{⊤}) \\ = c o n s t - t r (w^{⊤} X^{⊤} X w) \\ = c o n s t - c o n s t \cdot w^{⊤} Σ w . \end{aligned}

$\begin{align}\newcommand{\tr}{\mathrm{tr}} \|\X-\X\w\w^\top\|^2 &=\tr\left((\X-\X\w\w^\top)(\X-\X\w\w^\top)^\top\right) \\ &=\tr\left((\X-\X\w\w^\top)(\X^\top-\w\w^\top\X^\top)\right) \\ &=\tr(\X\X^\top)-2\tr(\X\w\w^\top\X^\top)+\tr(\X\w\w^\top\w\w^\top\X^\top) \\ &=\mathrm{const}-\tr(\X\w\w^\top\X^\top) \\ &=\mathrm{const}-\tr(\w^\top\X^\top\X\w) \\ &=\mathrm{const} - \mathrm{const} \cdot \w^\top \S \w. \end{align}$

$\w^\top \S \w$ $\w$ .

ameba diz Restabelecer Monica
fonte

Algo que eu notei, não é

w^{T} Σ w

${w}^{T} \Sigma w$ uma função convexa (em relação a

w

$w$ Como

Σ

$\Sigma$ é PSD? Como é que tentamos maximizar isso?

Royi 24/12/16

@amoeba can you explain how you go from tr() to const in the last step?

alberto

@alberto What is inside the trace is a number (1x1 matrix); a trace of a number is this number itself, so the trace can be removed. The constant appears because

Σ

$\Sigma$ is equal to

X^{⊤} X / n

$X^\top X/n$ , so there is this

1 / n

$1/n$ factor.

amoeba says Reinstate Monica

@Leullame The calculation will hold verbatim for

W

$W$ if it is a matrix with orthonormal columns. You need

W^{⊤} W = I

$W^\top W = I$ to go from line #3 to line #4. If matrix

W

$W$ has orthonormal columns, then indeed

x W W^{⊤}

$xWW^\top$ will be a projection of

x

$x$ onto the subspace spanned by the columns of

W

$W$ (here

x

$x$ is a row vector).

amoeba says Reinstate Monica

@DanielLópez Well, we are looking for a 1-dimensional subspace minimizing reconstruction error. A 1-dimensional subspace can be defined by a unit-norm vector pointing into its direction, which is what

w

$w$ is taken to be. It has unit norm by construction.

amoeba says Reinstate Monica