¿Cuál es la función objetivo de PCA?

El análisis de componentes principales puede usar la descomposición de la matriz, pero eso es solo una herramienta para llegar allí.

¿Cómo encontrarías los componentes principales sin el uso de álgebra matricial?

¿Cuál es la función objetivo (meta) y cuáles son las restricciones?

pca Neil McGuigan
fuente

Tal vez me falta algo, así que corríjame si me equivoco, pero debería ser posible (al menos en principio) construir lo que se hace en PCA utilizando matrices como un problema de programación lineal (complicado), pero no sepa cómo declararía todas las restricciones requeridas. Además, no estoy seguro de que sea muy fácil de hacer en comparación con solo usar PCA. ¿Por qué estás tratando de evitar matrices?

Chris Simokat

@ Chris No veo cómo se puede llegar a un problema de programación lineal. Tampoco entendí que las matrices deberían evitarse en el cálculo . La pregunta era qué tipo de problema resuelve la PCA y no la forma en que se hace (calculando la SVD, por ejemplo). La solución del cardenal dice que encuentra sucesivas direcciones ortogonales de máxima varianza . La solución que presenté dice que encuentras hiperplanos con un mínimo error de reconstrucción.

NRH

@chris Espero encontrar otra forma de ver PCA, sin el álgebra matricial, para aumentar mi comprensión de él.

Neil McGuigan

@ Chris, tienes una función objetivo cuadrática y una restricción de igualdad de norma

ℓ_{2}

$\ell_2$ . Alternativamente, bajo la formulación en la respuesta de @ NRH, tiene una restricción de rango de matriz. Eso no se reducirá a un problema de programación lineal. @NRH ofrece una buena intuición y, de hecho, existe una conexión muy estrecha entre las dos perspectivas sobre PCA que se han dado. Quizás en colaboración con @NRH, podamos agregar eso a su publicación para que el conjunto completo de respuestas sea más completo.

cardenal

@NRH, en realidad, me gusta mucho ESL , pero creo que el tratamiento de este tema es bastante superficial, como lo es para muchos de los temas del libro. En particular, no prueban (o incluso asignan como ejercicio) la parte importante de la solución para el problema de optimización que usted brinda.

cardenal

Respuestas:

Sin tratar de dar una cartilla completa sobre PCA, desde el punto de vista de la optimización, la función objetivo principal es el cociente de Rayleigh . La matriz que figura en el cociente es (algún múltiplo de) la matriz de covarianza de muestra , donde cada es un vector de características y es la matriz de tal manera que el -ésimo renglón es .

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$

PCA busca resolver una secuencia de problemas de optimización. El primero en la secuencia es el problema sin restricciones

\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, el problema sin restricciones anterior es equivalente al problema restringido $\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}$

Aquí es donde entra el álgebra matricial. Dado que es una matriz semidefinida positiva simétrica (¡por construcción!) Tiene una descomposición de valor propio de la forma donde es un matriz ortogonal (entonces ) y es una matriz diagonal con entradas no negativas tal 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$

Por lo tanto, . Como está limitado en el problema a tener una norma de uno, entonces también lo está ya que , en virtud de que es 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$

Pero, si queremos maximizar la cantidad bajo las restricciones que , entonces lo mejor que podemos hacer es set , es decir, y 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$

Ahora, retrocediendo el correspondiente , que es lo que buscamos en primer lugar, obtenemos que donde denota la primera columna de , es decir, el vector propio que corresponde al valor propio más grande de . El valor de la función objetivo también se ve fácilmente 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$

Los restantes vectores componentes principales se encuentran resolviendo la secuencia (indexada por ) de los problemas de optimización Entonces, el problema es el mismo, excepto que agregamos la restricción adicional de que la solución debe ser ortogonal a todas las soluciones anteriores en la secuencia. No es difícil extender el argumento anterior inductivamente para demostrar que la solución de la ésimo problema es, de hecho, , el ésimo vector propio 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$

La solución PCA también se expresa a menudo en términos de la descomposición del valor singular de . Para ver por qué, vamos a . Entonces y así (estrictamente hablando, hasta firmar flips) y . $\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$

Los componentes principales se encuentran proyectando en los vectores de componentes principales. De la formulación SVD recién dada, es 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} \> .$

La simplicidad de la representación de los vectores componentes principales y los componentes principales en sí mismos en términos de la SVD de la matriz de características es una de las razones por las cuales la SVD se destaca tan prominentemente en algunos tratamientos de PCA.

cardenal
fuente

Si solo se necesitan los primeros pocos valores / vectores singulares, Nash y Shlien ofrecen un algoritmo que recuerda el método de potencia habitual para calcular valores propios dominantes. Esto puede ser de interés para el OP.

JM no es estadístico

@NRH, ¡Gracias por detectar (y corregir) mis errores tipográficos antes de que pudiera verlos!

Cardenal

Hola @cardinal, gracias por tu respuesta. Pero parece que no dio el paso de probar por qué la optimización secuencial conduce a un óptimo global. ¿Podrías por favor explicar eso? ¡Gracias!

Lifu Huang

La solución presentada por cardinal se centra en la matriz de covarianza de la muestra. Otro punto de partida es el error de reconstrucción de los datos por un hiperplano q -dimensional. Si los puntos de datos p -dimensionales son el objetivo es 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 una matriz con columnas ortonormales y . Esto proporciona la mejor reconstrucción de rango q medida por la norma euclidiana, y las columnas de la solución son los primeros q componentes principales vectores. $p \times q$ $\mathbf{V}_q$ $\lambda_i \in \mathbb{R}^q$ $\mathbf{V}_q$

Para fijo la solución para y (esto es regresión) son $\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 la notación, supongamos que se ha centrado en los siguientes cálculos. Luego tenemos 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 con columnas ortonormales. Tenga en cuenta que es la proyección en el espacio de columna q -dimensional. Por lo tanto, el problema es equivalente a minimizar sobre rango q proyecciones . Es decir, necesitamos maximizar sobre las proyecciones de rango q , donde es la matriz de covarianza de muestra. Ahora $\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$ donde son las columnas (ortonormal) en , y los argumentos presentados en la respuesta de @ cardinal muestran que el máximo se obtiene tomando el ' s ser vectores propios para con los valores propios más grandes.

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$

El error de reconstrucción sugiere una serie de generalizaciones útiles, por ejemplo, componentes principales dispersos o reconstrucciones por colectores de baja dimensión en lugar de hiperplanos. Para más detalles, consulte la Sección 14.5 en Los elementos del aprendizaje estadístico .

NRH
fuente

(+1) Buenos puntos. Algunas sugerencias: Sería bueno definir y sería realmente bueno dar una breve prueba del resultado. O, alternativamente, se puede conectar al problema de optimización que involucra a los cocientes de Rayleight. ¡Creo que eso haría que las respuestas a esta pregunta fueran muy completas!

λ_{i}

$\lambda_i$

Cardenal

@cardinal, creo que completé los pasos que faltan para pasar de la formulación de reconstrucción al problema que resuelve.

NRH

Buen trabajo. Creo que la única brecha restante está en su última declaración. No es evidente de inmediato que optimizar la suma es lo mismo que realizar la secuencia de optimizaciones en mi respuesta. De hecho, no creo que se siga directamente, en general. Pero tampoco es necesario abordarlo aquí.

Cardenal

@ cardinal, se sigue por inducción. Proporciona el inicio de la inducción y, en el paso de inducción, elige los vectores ortonormales que maximizan la suma y la organizan de modo que sea un vector unitario ortogonal a . Luego, según sus resultados, y mediante el supuesto de inducción . Por supuesto, la base no es una base única para el espacio -dimensional. También puede generalizar el "argumento de combinación convexo" que utiliza para dar una prueba directa.

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, no estoy forzando un anidamiento, simplemente usando una consideración de dimensión. Si tenemos un subespacio -dimensional, siempre puede elegir en ese espacio de modo que sea ortogonal a un subespacio . Luego, llene la base de la forma que desee.

q

$q$

w_{q}

$w_q$

(q - 1)

$(q-1)$

w

$w$

NRH

Ver NIPALS ( wiki ) para un algoritmo que no usa explícitamente una descomposición de matriz. Supongo que eso es lo que quieres decir cuando dices que quieres evitar el álgebra matricial ya que realmente no puedes evitar el álgebra matricial aquí :)

JMS
fuente