Diferencia entre las implementaciones de scikit-learn de PCA y TruncatedSVD

Question

Entiendo la relación entre el Análisis de Componentes Principales y la Descomposición de Valores Singulares a nivel algebraico/exacto. Mi pregunta es sobre la implementación de scikit-learn .

La documentación dice: " [TruncatedSVD] es muy similar a PCA, pero opera sobre los vectores de muestra directamente, en lugar de sobre una matriz de covarianza. ", lo que reflejaría la diferencia algebraica entre ambos enfoques. Sin embargo, más adelante dice: " Este estimador [TruncatedSVD] admite dos algoritmos: un solucionador aleatorio rápido de SVD, y un algoritmo "ingenuo" que utiliza ARPACK como eigensolver en (X * X.T) o (X.T * X), lo que sea más eficiente. ". En cuanto a PCA dice: "Reducción lineal de la dimensionalidad utilizando la descomposición del valor singular de los datos para proyectarlos...". Y la implementación de PCA soporta los mismos dos algoritmos (randomized y ARPACK) solvers más otro, LAPACK. Mirando en el código puedo ver que tanto ARPACK como LAPACK tanto en PCA como en TruncatedSVD hacen svd en los datos de muestra X, siendo ARPACK capaz de tratar con matrices dispersas (usando svds).

Así que, aparte de los diferentes atributos y métodos y de que PCA puede hacer adicionalmente la descomposición de valor singular completa exacta usando LAPACK, las implementaciones de PCA y TruncatedSVD de scikit-learn parecen ser exactamente el mismo algoritmo. Primera pregunta: ¿Es esto correcto?

Segunda cuestión: aunque LAPACK y ARPACK utilizan scipy.linalg.svd(X) y scipy.linalg.svds(X), siendo X la matriz de muestra, calculan la descomposición de valores singulares o la descomposición de valores propios de $X^T*X$ o $X*X^T$ internamente. Mientras que el solucionador "aleatorio" no necesita calcular el producto. (Esto es relevante en relación con la estabilidad numérica, véase ¿Por qué el ACP de los datos mediante la SVD de los datos? ). ¿Es esto correcto?

Código correspondiente: PCA línea 415. TruncatedSVD línea 137.

Answer 1

Las implementaciones de PCA y TruncatedSVD de scikit-learn parecen ser exactamente el mismo algoritmo.

No: PCA es SVD (truncado) sobre datos centrados (por sustracción de la característica se entiende). Si los datos ya están centrados, esas dos clases harán lo mismo.

En la práctica TruncatedSVD es útil en grandes conjuntos de datos dispersos que no pueden ser centrados sin hacer explotar el uso de la memoria.

• numpy.linalg.svd y scipy.linalg.svd ambos se basan en LAPACK _GESDD descrito aquí: http://www.netlib.org/lapack/lug/node32.html (conductor de "divide y vencerás")

• scipy.sparse.linalg.svds se basa en ARPACK para hacer una descomposición del valor propio de XT . X o X . X.T (dependiendo de la forma de los datos) mediante el método de iteración de Arnoldi. La guía de usuario HTML de ARPACK tiene un formato roto que oculta los detalles computacionales pero la iteración de Arnoldi está bien descrita en wikipedia: https://en.wikipedia.org/wiki/Arnoldi_iteration

Aquí está el código para el SVD basado en ARPACK en scipy:

https://github.com/scipy/scipy/blob/master/scipy/sparse/linalg/eigen/arpack/arpack.py#L1642 (buscar la cadena de "def svds" en caso de cambio de línea en el código fuente).

Answer 2

También hay una diferencia en la forma de atribuir explained_variance_ se calcula.

Que la matriz de datos $\mathbf X$ ser de $n \times p$ tamaño, donde $n$ es el número de muestras y $p$ es el número de variables. Y $\mathbf{X}_c$ es la matriz de datos centrada, es decir, las medias de las columnas se han restado y ahora son iguales a cero en esta matriz. Supongamos que estamos reduciendo la dimensionalidad de los datos de $p$ a $k \lt p$ .

Entonces para sklearn.decomposition.PCA tenemos las siguientes expresiones: $$\mathbf{X}_c \approx \mathbf{U}_k \mathbf{S}_k \mathbf{V}_k^T \qquad (\text{truncated SVD of } \mathbf{X}_c);$$ $$\mathbf{L}_k = \frac{1}{n-1} \mathbf{S}^2_k \quad \Longleftrightarrow \quad \lambda_j = \frac{s_j^2}{n-1}, \quad \forall j =1,\ldots,k; \qquad(*)$$

donde $\mathbf{L}_k = \mathrm{diag}(\lambda_1, \ldots, \lambda_k)$ es la matriz de $k$ mayores valores propios de la matriz de covarianza $\mathbf{C} = \frac{1}{n-1} \mathbf{X}_c^T\mathbf{X}_c$ et $\mathbf{S}_k = \mathrm{diag}(s_1, \ldots, s_k)$ es la matriz de $k$ mayores valores singulares de $\mathbf{X}_c$ . Simplemente puede probar $(*)$ si se sustituye la SVD truncada de $\mathbf{X}_c$ en la expresión de la matriz de covarianza $\mathbf{C}$ y comparar el resultado con la eigendecomposición truncada $\mathbf{C} \approx \mathbf{V}_k \mathbf{L} \mathbf{V}_k^T$ ( aquí se hizo para las descomposiciones completas). Matriz $\mathbf{L}_k$ se llama explained_variance_ atributo en sklearn.decomposition.PCA .

Pero para sklearn.decomposition.TruncatedSVD sólo se sostiene lo siguiente: $$\mathbf{X} \approx \tilde{\mathbf{U}}_k \tilde{\mathbf{S}}_k \tilde{\mathbf{V}}_k^T \qquad (\text{truncated SVD of } \mathbf{X}).$$ En este caso no podemos obtener una ecuación simple como $(*)$ que enlazará $\mathbf{L}_k$ y $\tilde{\mathbf{S}}_k$ porque la sustitución de la SVD truncada de $\mathbf{X}$ en la expresión $\mathbf{C} = \frac{1}{n-1} \mathbf{X}_c^T\mathbf{X}_c = \frac{1}{n-1}\mathbf{X}^T\mathbf{X} - \frac{n}{n-1}\bar{x}\bar{x}^T$ no será muy útil. Así que explained_variance_ en sklearn.decomposition.TruncatedSVD se calcula, en cambio, mediante np.var(X_transformed, axis=0) , donde X_transformed = $\mathbf{X} \tilde{\mathbf{V}}_k$ - matriz de puntuaciones (nuevas características).