Función objetivo de PCA: ¿cuál es la conexión entre maximizar la varianza y minimizar el error?

El algoritmo PCA se puede formular en términos de la matriz de correlación (suponga que los datos $X$ ya se han normalizado y solo estamos considerando la proyección en la primera PC). La función objetivo se puede escribir 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.$

Esto está bien, y usamos multiplicadores lagrangianos para resolverlo, es decir, reescribirlo como:

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

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

que es equivalente a

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

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

y por lo tanto ( ver aquí en Mathworld ) parece ser igual a

max_{w} \sum_{yo = 1}^{norte} {(distancia desde el punto X_{yo} alinear w)}^{2} .

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

Pero esto es para maximizar la distancia entre el punto y la línea, y por lo que he leído aquí , esto es incorrecto: debería ser , no . ¿Dónde está mi error? $\min$ $\max$

O, ¿alguien puede mostrarme el vínculo entre maximizar la varianza en el espacio proyectado y minimizar la distancia entre el punto y la línea?

pca optimization Cam.Davidson.Pilon
fuente

Creo que la distancia mínima se utiliza para cumplir el criterio de ortogonalidad para los componentes. Los puntos se proyectan en las PC que son ortogonales entre sí, pero en cada componente sucesivo se maximiza la variación restante.

Michael R. Chernick

Sugerencia: ¿Qué sucede cuando considera primero el valor propio más pequeño , en lugar del más grande?

whuber

@whuber El valor propio más pequeño probablemente tiene la PC que es la solución a la función objetivo final. Pero esta PC no maximiza la función objetivo original.

Cam.Davidson.Pilon

No estoy seguro de lo que quieres decir con función objetivo "final" y "original", Cam. PCA no es (conceptualmente) un programa de optimización. Su salida es un conjunto de direcciones principales, no solo una. Es un teorema matemático (interesante) que estas direcciones se pueden encontrar resolviendo una secuencia de programas cuadráticos restringidos, pero eso no es básico para los conceptos o la práctica de PCA. Solo sugiero que, al enfocarse en el valor propio más pequeño en lugar del más grande, puede conciliar las dos ideas de (1) minimizar distancias y (2) tomar una vista de optimización de PCA.

whuber

Está bien, su respuesta fue la versión sin error de lo que estaba tratando de hacer.

Cam.Davidson.Pilon

Respuestas:

Sea una matriz de datos centrada con observaciones en filas. Sea ser su matriz de covarianza. Sea ser un vector unitario que especifica un eje en el espacio variable. Queremos que sea el primer eje principal. $\newcommand{\X}{\mathbf X}\X$ $n$ $\newcommand{\S}{\boldsymbol \Sigma}\S=\X^\top\X/(n-1)$ $\newcommand{\w}{\mathbf w}\w$ $\w$

Según el primer enfoque, el primer eje principal maximiza la varianza de la proyección (varianza del primer componente principal). Esta variación viene dada por $\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.$

Según el segundo enfoque, el primer eje principal minimiza el error de reconstrucción entre y su reconstrucción , es decir, la suma de las distancias al cuadrado entre los puntos originales y sus proyecciones sobre . El cuadrado del error de reconstrucción viene dado por $\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}$

Observe el signo menos antes del término principal. Debido a eso, minimizar el error de reconstrucción equivale a maximizar , que es la varianza. Por lo tanto, minimizar el error de reconstrucción es equivalente a maximizar la varianza; ambas formulaciones producen el mismo . $\w^\top \S \w$ $\w$

ameba dice Reinstate Monica
fuente

Algo que noté, ¿no es una función convexa (con respecto a as es PSD? ¿Cómo es que tratamos de maximizarlo?

w^{T} Σ w

${w}^{T} \Sigma w$

w

$w$

Σ

$\Sigma$

Royi

@amoeba, ¿puedes explicar cómo pasas de tr () a const en el último paso?

alberto

@alberto Lo que está dentro de la traza es un número (matriz 1x1); un rastro de un número es este número en sí mismo, por lo que el rastro se puede eliminar. La constante aparece porque es igual a , por lo que existe este factor .

Σ

$\Sigma$

X^{⊤} X / n

$X^\top X/n$

1 / n

$1/n$

ameba dice Reinstate Monica

@Leullame El cálculo tendrá textualmente para si es una matriz con columnas ortonormales. Necesita para pasar de la línea 3 a la 4. Si la matriz tiene columnas ortonormales, entonces será una proyección de en el subespacio atravesado por las columnas de (aquí es un vector de fila).

W

$W$

W^{⊤} W = I

$W^\top W = I$

W

$W$

x W W^{⊤}

$xWW^\top$

x

$x$

W

$W$

x

$x$

ameba dice Reinstate Monica

@ DanielLópez Bueno, estamos buscando un subespacio unidimensional que minimice el error de reconstrucción. Un subespacio unidimensional se puede definir mediante un vector de unidad de norma que apunta en su dirección, que es lo que se considera . Tiene unidad de norma por construcción.

w

$w$

ameba dice Reinstate Monica