¿Cuál es una explicación intuitiva de cómo PCA pasa de un problema geométrico (con distancias) a un problema de álgebra lineal (con vectores propios)?

54

He leído mucho sobre PCA, incluidos varios tutoriales y preguntas (como este , este , este y este ).

El problema geométrico que PCA está tratando de optimizar es claro para mí: PCA trata de encontrar el primer componente principal minimizando el error de reconstrucción (proyección), que maximiza simultáneamente la varianza de los datos proyectados.

Cuando leí eso por primera vez, inmediatamente pensé en algo como la regresión lineal; tal vez puedas resolverlo usando el gradiente de descenso si es necesario.

Sin embargo, entonces me volví loco cuando leí que el problema de optimización se resuelve utilizando álgebra lineal y encontrando vectores propios y valores propios. Simplemente no entiendo cómo entra en juego este uso del álgebra lineal.

Entonces mi pregunta es: ¿cómo puede la PCA pasar de un problema de optimización geométrica a un problema de álgebra lineal? ¿Alguien puede proporcionar una explicación intuitiva?

No estoy buscando una respuesta como esta que diga "Cuando resuelves el problema matemático de PCA, termina siendo equivalente a encontrar los valores propios y los vectores propios de la matriz de covarianza". Explique por qué los vectores propios resultan ser los componentes principales y por qué los valores propios resultan ser una varianza de los datos proyectados sobre ellos.

Soy ingeniero de software y no matemático, por cierto.

Nota: la figura anterior fue tomada y modificada de este tutorial de PCA .

pca optimization linear-algebra intuition stackoverflowuser2010
fuente

2

En el largo hilo detrás de su primer enlace, hay una respuesta de @ amoeba con animación, que explica lo esencial. PCA es la rotación de los ejes de datos (columnas) hasta que no se correlacionan como vectores de datos (variables). Dicha matriz de rotación se encuentra mediante descomposición propia o descomposición de valores singulares y se denomina matriz de vectores propios.

ttnphns

2

Además, incluso si no eres matemático (yo tampoco lo soy), probablemente hayas oído hablar de que el álgebra lineal y la geometría euclidiana son campos matemáticos muy íntimamente ligados; incluso se estudian juntos como una disciplina llamada geometría analítica.

ttnphns

1

optimization problemSí, el problema de PCA podría resolverse mediante enfoques de optimización (iterativos, convergentes), creo. Pero dado que tiene una solución de forma cerrada a través de matemáticas, ¿por qué no usar esa solución más simple y eficiente?

ttnphns

Le preguntas a provide an intuitive explanation. Me pregunto por qué la respuesta intuitiva y clara de ameba, a la que me he vinculado, no le conviene. Usted pregunta por _why_ eigenvectors come out to be the principal components...qué? ¡Por definición! Los vectores propios son las direcciones principales de una nube de datos.

ttnphns

66

@ttnphns: Realmente creo que la pregunta es razonable. Así es como lo entiendo. PCA quiere encontrar la dirección de la varianza máxima de la proyección. Esta dirección se llama (por definición) la primera dirección principal. Por otro lado, un vector propio de la matriz de covarianza

es (por definición) tal vector

que

. Entonces, ¿por qué es la primera dirección principal dada por el vector propio con el mayor valor propio? ¿Cuál es la intuición aquí? Ciertamente no es por definición. Lo he estado pensando y sé cómo demostrarlo, pero es difícil de explicar intuitivamente.

C

$C$

w

$w$

C w = λ w

$Cw=\lambda w$

ameba dice Reinstate Monica

54

Planteamiento del problema

El problema geométrico que PCA está tratando de optimizar es claro para mí: PCA trata de encontrar el primer componente principal minimizando el error de reconstrucción (proyección), que maximiza simultáneamente la varianza de los datos proyectados.

Eso es correcto. Explico la conexión entre estas dos formulaciones en mi respuesta aquí (sin matemáticas) o aquí (con matemáticas).

$\mathbf C$ $\mathbf w$ $\|\mathbf w\|=1$ $\mathbf w^\top \mathbf{Cw}$

(Por si esto no está claro: si es la matriz de datos centrada, entonces la proyección está dada por y su varianza es .) $\mathbf X$ $\mathbf{Xw}$ $\frac{1}{n-1}(\mathbf{Xw})^\top \cdot \mathbf{Xw} = \mathbf w^\top\cdot (\frac{1}{n-1}\mathbf X^\top\mathbf X)\cdot \mathbf w = \mathbf w^\top \mathbf{Cw}$

Por otro lado, un vector propio de es, por definición, cualquier vector tal que . $\mathbf C$ $\mathbf v$ $\mathbf{Cv}=\lambda \mathbf v$

Resulta que la primera dirección principal está dada por el vector propio con el valor propio más grande. Esta es una declaración no trivial y sorprendente.

Pruebas

Si uno abre algún libro o tutorial sobre PCA, puede encontrar allí la siguiente prueba de casi una línea de la declaración anterior. Queremos maximizar bajo la restricción de que ; esto se puede hacer introduciendo un multiplicador de Lagrange y maximizando ; diferenciando, obtenemos , que es la ecuación del vector propio. Vemos que tiene que ser el mayor valor propio al sustituir esta solución en la función objetivo, que da $\mathbf w^\top \mathbf{Cw}$ $\|\mathbf w\|=\mathbf w^\top \mathbf w=1$ $\mathbf w^\top \mathbf{Cw}-\lambda(\mathbf w^\top \mathbf w-1)$ $\mathbf{Cw}-\lambda\mathbf w=0$ $\lambda$ $\mathbf w^\top \mathbf{Cw}-\lambda(\mathbf w^\top \mathbf w-1) = \mathbf w^\top \mathbf{Cw} = \lambda\mathbf w^\top \mathbf{w} = \lambda$ . En virtud del hecho de que esta función objetivo debe ser maximizada, debe ser el mayor valor propio, QED. $\lambda$

Esto tiende a ser poco intuitivo para la mayoría de las personas.

Una mejor prueba (ver, por ejemplo, esta clara respuesta de @cardinal ) dice que porque es una matriz simétrica, es diagonal en su base de vector propio. (Esto en realidad se llama teorema espectral ). Por lo tanto, podemos elegir una base ortogonal, a saber, la dada por los vectores propios, donde es diagonal y tiene valores propios en la diagonal. En esa base, simplifica a , o en otras palabras, la varianza está dada por la suma ponderada de los valores propios. Es casi inmediato que para maximizar esta expresión uno simplemente tome $\mathbf C$ $\mathbf C$ $\lambda_i$ $\mathbf w^\top \mathbf{C w}$ $\sum \lambda_i w_i^2$ $\mathbf w = (1,0,0,\ldots, 0)$ , es decir, el primer vector propio, que produce la varianza (de hecho, desviarse de esta solución y "intercambiar" partes del valor propio más grande por las partes de las más pequeñas solo conducirá a una variación general más pequeña). Tenga en cuenta que el valor de no depende de la base. Cambiar a la base del vector propio equivale a una rotación, por lo que en 2D se puede imaginar simplemente girando un trozo de papel con el diagrama de dispersión; obviamente esto no puede cambiar ninguna variación. $\lambda_1$ $\mathbf w^\top \mathbf{C w}$

Creo que este es un argumento muy intuitivo y muy útil, pero se basa en el teorema espectral. Entonces, el verdadero problema aquí creo es: ¿cuál es la intuición detrás del teorema espectral?

Teorema espectral

Tome una matriz simétrica . Tome su vector propio con el mayor valor propio . Convierta este vector propio en el primer vector base y elija otros vectores base al azar (de modo que todos sean ortonormales). ¿Cómo se verá en esta base? $\mathbf C$ $\mathbf w_1$ $\lambda_1$ $\mathbf C$

Tendrá en la esquina superior izquierda, porque en esta base y tiene que ser igual a . $\lambda_1$ $\mathbf w_1=(1,0,0\ldots 0)$ $\mathbf {Cw}_1=(C_{11}, C_{21}, \ldots C_{p1})$ $\lambda_1\mathbf w_1 = (\lambda_1,0,0 \ldots 0)$

Por el mismo argumento, tendrá ceros en la primera columna debajo de . $\lambda_1$

Pero como es simétrico, también tendrá ceros en la primera fila después de . Entonces se verá así: $\lambda_1$

C = (\begin{matrix} λ_{1} & 0 & \dots & 0 \\ 0 \\ ⋮ \\ 0 \end{matrix}),

$\mathbf C=\begin{pmatrix}\lambda_1 & 0 & \ldots & 0 \\ 0 & & & \\ \vdots & & & \\ 0 & & & \end{pmatrix},$

donde espacio vacío significa que hay un bloque de algunos elementos allí. Como la matriz es simétrica, este bloque también será simétrico. Entonces podemos aplicarle exactamente el mismo argumento, usando efectivamente el segundo vector propio como el segundo vector base y obteniendo y en la diagonal. Esto puede continuar hasta que sea diagonal. Ese es esencialmente el teorema espectral. (Observe cómo funciona solo porque es simétrico). $\lambda_1$ $\lambda_2$ $\mathbf C$ $\mathbf C$

Aquí hay una reformulación más abstracta de exactamente el mismo argumento.

Sabemos que , por lo que el primer vector propio define un subespacio unidimensional donde actúa como una multiplicación escalar. Tomemos ahora cualquier vector ortogonal a . Entonces es casi inmediato que también es ortogonal a . En efecto: $\mathbf{Cw}_1 = \lambda_1 \mathbf w_1$ $\mathbf C$ $\mathbf v$ $\mathbf w_1$ $\mathbf {Cv}$ $\mathbf w_1$

w_{1}^{⊤} C v = (w_{1}^{⊤} C v)^{⊤} = v^{⊤} C^{⊤} w_{1} = v^{⊤} {C w}_{1} = λ_{1} v^{⊤} w_{1} = λ_{1} \cdot 0 = 0.

$\mathbf w_1^\top \mathbf{Cv} = (\mathbf w_1^\top \mathbf{Cv})^\top = \mathbf v^\top \mathbf C^\top \mathbf w_1 = \mathbf v^\top \mathbf {Cw}_1=\lambda_1 \mathbf v^\top \mathbf w_1 = \lambda_1\cdot 0 = 0.$

Esto significa que actúa sobre todo el subespacio ortogonal restante a modo que se mantenga separado de . Esta es la propiedad crucial de las matrices simétricas. Entonces podemos encontrar el vector propio más grande allí, , y proceder de la misma manera, eventualmente construyendo una base ortonormal de vectores propios. $\mathbf C$ $\mathbf w_1$ $\mathbf w_1$ $\mathbf w_2$

ameba dice Reinstate Monica
fuente

El "multiplicador de Lagrange" es realmente claro para mí. Sin embargo, ¿podría decirme por qué necesitamos una restricción de longitud de unidad? Gracias

Haitao Du

2

@ hxd1011 Ya existe exactamente esta pregunta , pero brevemente: eso es porque de lo contrario puede multiplicar por cualquier número y aumentará por el cuadrado de este número. Entonces el problema se vuelve mal definido: el máximo de esta expresión es infinito. De hecho, la varianza de la proyección en la dirección de es solo si es la longitud de la unidad.

w

$w$

w^{⊤} C w

$w^\top Cw$

w

$w$

w^{⊤} C w

$w^\top Cw$

w

$w$

ameba dice Reinstate Monica

Supongo que podría ser un poco más familiar para la mayoría de los lectores; Lo reemplacé aquí. Gracias.

n - 1

$n-1$

ameba dice Reinstate Monica

@amoeba: Gracias por la respuesta. Estoy confundido por algo de tu notación. Utiliza w para indicar el vector de longitud unitaria que resulta ser el primer vector propio (componente principal). Cuando ejecuto PCA en R (por ejemplo prcomp(iris[,1:4], center=T, scale=T)), veo vectores propios de longitud de unidad con un montón de flotadores como (0.521, -0.269, 0.580, 0.564). Sin embargo, en su respuesta bajo "Pruebas", escribe Es casi inmediato que para maximizar esta expresión uno simplemente debe tomar w = (1,0,0, ..., 0), es decir, el primer vector propio . ¿Por qué el vector propio en su prueba se ve tan bien formado así?

stackoverflowuser2010

1

Hola @ user58865, gracias por el empujón: simplemente olvidé responder la primera vez. Lo delgado es, es un escalar, es solo un número. Cualquier número es "simétrico" :) y es igual a su transposición. ¿Tiene sentido?

w_{1}^{⊤} C v

$w^\top_1 C v$

ameba dice Reinstate Monica

5

Hay un resultado de 1936 por Eckart y Young ( https://ccrma.stanford.edu/~dattorro/eckart%26young.1936.pdf ), que establece lo siguiente

$\sum_1^r d_k u_k v_k^T = arg min_{\hat{X} \epsilon M(r)} ||X-\hat{X}||_F^2$

donde M (r) es el conjunto de matrices de rango r, lo que básicamente significa que los primeros componentes r de SVD de X dan la mejor aproximación de matriz de rango bajo de X y la mejor se define en términos de la norma de Frobenius al cuadrado: la suma del cuadrado elementos de una matriz.

Este es un resultado general para las matrices y, a primera vista, no tiene nada que ver con los conjuntos de datos o la reducción de dimensionalidad.

Sin embargo, si no piensa en como una matriz, sino que piensa en las columnas de la matriz representan vectores de puntos de datos, entonces es la aproximación con el error de representación mínimo en términos de diferencias de error al cuadrado. $X$ $X$ $\hat{X}$

Cagdas Ozgenc
fuente

4

Esta es mi opinión sobre el álgebra lineal detrás de PCA. En álgebra lineal, uno de los teoremas clave es el . Establece si S es una matriz simétrica n por n con coeficientes reales, entonces S tiene n vectores propios con todos los valores propios siendo reales. Eso significa que podemos escribir con D una matriz diagonal con entradas positivas. Eso es y no hay ningún daño en asumir . A es el cambio de matriz base. Es decir, si nuestra base original era , entonces con respecto a la base dada por $\textit{Spectral Theorem}$ $S = ADA^{-1}$ $D = \mbox{diag} (\lambda_1, \lambda_2, \ldots, \lambda_n)$ $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n$ $x_1,x_2, \ldots, x_n$ $A(x_1), A(x_2), \ldots A(x_n)$ , la acción de S es diagonal. Esto también significa que puede considerarse como una base ortogonal con Si nuestra matriz de covarianza fuera para n observaciones de n variables, estaríamos . La base proporcionada por es la base de PCA. Esto se desprende de los hechos de álgebra lineal. En esencia, es cierto porque una base de PCA es una base de vectores propios y hay al menos n vectores propios de una matriz cuadrada de tamaño n. Por supuesto, la mayoría de las matrices de datos no son cuadradas. Si X es una matriz de datos con n observaciones de p variables, entonces X es de tamaño n por p. Asumiré que (más observaciones que variables) y que $A(x_i)$ $||A(x_i)|| = \lambda_i$ $A(x_i)$
$n>p$ $rk(X) = p$ (todas las variables son linealmente independientes). Ninguna suposición es necesaria, pero ayudará con la intuición. El álgebra lineal tiene una generalización del teorema espectral llamada descomposición del valor singular. Para tal X, establece que con U, V matrices ortonormales (cuadradas) de tamaño nyp y una matriz diagonal real con solo no negativo entradas en la diagonal. Nuevamente, podemos reorganizar la base de V para que En términos de matriz, esto significa que si y si . El $X = U \Sigma V^{t}$ $\Sigma = (s_{ij})$ $s_{11} \geq s_{22} \geq \ldots s_{pp}> 0$ $X(v_i) = s_{ii} u_i$ $i \leq p$ $s_{ii} = 0$ $i> n$ $v_i$ dar la descomposición de PCA. Más precisamente, es la descomposición de PCA. ¿Por qué? De nuevo, el álgebra lineal dice que solo puede haber vectores propios. La SVD proporciona nuevas variables (dadas por las columnas de V) que son ortogonales y tienen una norma decreciente. $\Sigma V^{t}$

aginensky
fuente

4

"que maximiza simultáneamente la varianza de los datos proyectados". ¿Has oído hablar del cociente de Rayleigh ? Tal vez esa sea una forma de ver esto. Es decir, el cociente rayleigh de la matriz de covarianza le proporciona la varianza de los datos proyectados. (y la página wiki explica por qué los vectores propios maximizan el cociente de Rayleigh)

seanv507
fuente

1

@amoeba ofrece una formalización clara y prueba de:

Podemos formalizarlo de la siguiente manera: dada la matriz de covarianza C, estamos buscando un vector w que tenga una unidad de longitud, ‖w‖ = 1, de modo que w ^T Cw sea máximo.

Pero creo que hay una prueba intuitiva para:

Resulta que la primera dirección principal está dada por el vector propio con el valor propio más grande. Esta es una declaración no trivial y sorprendente.

Podemos interpretar w ^T Cw como un producto de punto entre el vector w y Cw, que se obtiene al pasar por la transformación C:

w ^T Cw = ‖w‖ * ‖Cw‖ * cos (w, Cw)

Como w tiene una longitud fija, para maximizar w ^T Cw, necesitamos:

maximizar ‖Cw‖
maximizar cos (w, Cw)

Resulta que si consideramos que w es un vector propio de C con el valor propio más grande, podemos archivar ambos simultáneamente:

‖Cw‖ es max, (si w se desvía de este vector propio, descomponga a lo largo de los vectores propios ortogonales, debería ver que ‖Cw‖ disminuye).
w y Cw en la misma dirección, cos (w, Cw) = 1, max

Como los vectores propios son ortogonales, junto con los otros vectores propios de C forman un conjunto de componentes principales para X.

prueba de 1

descomponer w en vectores propios primarios y secundarios ortogonales v1 y v2 , supongamos que su longitud es v1 y v2 respectivamente. queremos probar

(λ ₁ w) ² > ((λ ₁ v1) ² + (λ ₂ v2) ² )

desde λ ₁ > λ ₂ , tenemos

((λ ₁ v1) ² + (λ ₂ v2) ² )

<((λ ₁ v1) ² + (λ ₁ v2) ² )

= (λ ₁ ) ² * (v1 ² + v2 ² )

= (λ ₁ ) ² * w ²

Cielo
fuente

¿Cuál es una explicación intuitiva de cómo PCA pasa de un problema geométrico (con distancias) a un problema de álgebra lineal (con vectores propios)?

Respuestas:

Planteamiento del problema

Pruebas

Teorema espectral