Почему PCA данных с помощью SVD данных?

Этот вопрос касается эффективного способа вычисления основных компонентов.

Многие тексты по линейному PCA рекомендуют использовать разложение по регистру данных по сингулярным значениям . То есть, если у нас есть данные и мы хотим заменить переменные (их столбцы ) на главные компоненты, мы делаем SVD: , особые значения (квадратные корни из собственных значений), занимающие основную диагональ , правые собственные векторы - это ортогональная матрица вращения осей-переменных в оси-компоненты, левые собственные векторы подобны , только для случаев. Затем мы можем вычислить значения компонентов как . $\bf X$ $\bf X=USV'$ $\bf S$ $\bf V$ $\bf U$ $\bf V$ $\bf C=XV=US$
Другим способом сделать PCA переменных является разложение квадратной матрицы (т. может быть корреляциями или ковариациями и т. Д. Между переменными). Разложение может быть собственным разложением или разложением по сингулярному значению: с квадратно-симметричной положительной полуопределенной матрицей они дадут тот же результат с собственными значениями, что и диагональ , и как описано ранее. Значения компонентов будут . $\bf R=X'X$ $\bf R$ $\bf R=VLV'$ $\bf L$ $\bf V$ $\bf C=XV$

Теперь мой вопрос: если data - большая матрица, а число случаев (что часто бывает) намного больше, чем число переменных, то путь (1), как ожидается, будет намного медленнее, чем путь (2) ), поскольку способ (1) применяет довольно дорогой алгоритм (такой как SVD) к большой матрице; он вычисляет и хранит огромную матрицу которая нам действительно не нужна в нашем случае (PCA переменных). Если так, то почему так много учебников, кажется, отстаивают или просто упоминают только один путь (1)? Может быть , это является эффективным и я что - то не хватает? $\bf X$ $\bf U$

pca algorithms svd matrix-decomposition ttnphns
источник

Как правило, нас интересуют только несколько основных компонентов, которые объясняют большую часть дисперсии. Можно сделать уменьшенный СВД; например , если имеет размерность , где , то «s функция будет вычислять только первые левые и правые сингулярные векторы по умолчанию.

X

$X$

N \times p

$N \times p$

p << N

$p << N$ Rsvd

p

$p$

М. Берк

@ M.Berk: однако, одинаков в обоих подходах: они дают эквивалентные результаты (равны до изменения знака). Также, например, R вычисляет только по запросу.

p

$p$

C

$\mathbf C$

cbeleites поддерживает Монику

У вас есть ссылки на способ (1)? Мне известно только о том, что PCA реализуется через SVD на ковариационной матрице (т. Е. Способ 2), поскольку это позволяет избежать некоторых численных проблем и очевидно масштабируется с размерностью, а не с размером набора данных. Способ (1) Я бы назвал SVD, а не PCA вообще. Я видел это только в чистом контексте SVD, где нельзя было бы выполнить полную декомпозицию.

Anony-Mousse -Восстановить Монику

@ Anony-Mousse, только один, чтобы упомянуть, Joliffe, Principal component analysis, 2nd ed.На самом деле, Джолифф описывает оба пути, но, насколько я помню, в основной главе по PCA он говорит только о способе 1.

ttnphns

@ Anony-Mousse, путь 1 для меня важен с теоретической точки зрения, потому что он ясно показывает, как PCA напрямую связан с простым анализом соответствия .

ttnphns

Ответы:

Вот мой 2ct по теме

На лекции по хемометрике, где я впервые узнал, что PCA использовал решение (2), но он не был ориентирован на нумерацию, а моя числовая лекция была только вводной и, насколько я помню, не обсуждала SVD.
Если я правильно понимаю Holmes: Fast SVD для крупномасштабных матриц , ваша идея использовалась для получения вычислительно быстрого SVD длинных матриц.
Это означало бы, что хорошая реализация SVD может внутренне следовать (2), если она встречает подходящие матрицы (я не знаю, есть ли еще лучшие возможности). Это будет означать, что для реализации высокого уровня лучше использовать SVD (1) и предоставить BLAS возможность решать, какой алгоритм использовать для внутреннего использования.
Быстрая практическая проверка: svd в OpenBLAS, похоже, не делает этого различия на матрице 5e4 x 100, svd (X, nu = 0)занимает в среднем 3,5 с и svd (crossprod (X), nu = 0)занимает 54 мс ( вызывается из R с помощью microbenchmark).
Конечно, возведение в квадрат собственных значений быстрое, и до этого результаты обоих вызовов эквивалентны.
```
timing  <- microbenchmark (svd (X, nu = 0), svd (crossprod (X), nu = 0), times = 10)
timing
# Unit: milliseconds
#                      expr        min         lq    median         uq        max neval
#            svd(X, nu = 0) 3383.77710 3422.68455 3507.2597 3542.91083 3724.24130    10
# svd(crossprod(X), nu = 0)   48.49297   50.16464   53.6881   56.28776   59.21218    10
```

обновление: взгляните на Wu, W .; Massart, D. & de Jong, S .: Алгоритмы PCA ядра для широких данных. Часть I: Теория и алгоритмы, Хемометрика и интеллектуальные лабораторные системы, 36, 165 - 172 (1997). DOI: http://dx.doi.org/10.1016/S0169-7439(97)00010-5

В этой статье обсуждаются численные и вычислительные свойства 4 различных алгоритмов для PCA: SVD, собственное разложение (EVD), NIPALS и POWER.

Они связаны следующим образом:

computes on      extract all PCs at once       sequential extraction    
X                SVD                           NIPALS    
X'X              EVD                           POWER

Контекст статьи широкий , и они работают на (ядро PCA) - это ситуация, прямо противоположная той, о которой вы спрашиваете. Поэтому, чтобы ответить на ваш вопрос о поведении длинных матриц, вам нужно поменять значения «ядро» и «классическое». $\mathbf X^{(30 \times 500)}$ $\mathbf{XX'}$

сравнение производительности

Неудивительно, что EVD и SVD меняются местами в зависимости от того, используются ли классические алгоритмы или алгоритмы ядра. В контексте этого вопроса это означает, что один или другой может быть лучше в зависимости от формы матрицы.

Но из их обсуждения «классических» SVD и EVD становится ясно, что разложение является очень обычным способом вычисления PCA. Однако они не указывают, какой алгоритм SVD используется, кроме того, что они используют функцию Matlab . $\mathbf{X'X}$ svd ()

    > sessionInfo ()
    R version 3.0.2 (2013-09-25)
    Platform: x86_64-pc-linux-gnu (64-bit)

    locale:
     [1] LC_CTYPE=de_DE.UTF-8       LC_NUMERIC=C               LC_TIME=de_DE.UTF-8        LC_COLLATE=de_DE.UTF-8     LC_MONETARY=de_DE.UTF-8   
     [6] LC_MESSAGES=de_DE.UTF-8    LC_PAPER=de_DE.UTF-8       LC_NAME=C                  LC_ADDRESS=C               LC_TELEPHONE=C            
    [11] LC_MEASUREMENT=de_DE.UTF-8 LC_IDENTIFICATION=C       

    attached base packages:
    [1] stats     graphics  grDevices utils     datasets  methods   base     

    other attached packages:
    [1] microbenchmark_1.3-0

loaded via a namespace (and not attached):
[1] tools_3.0.2

$ dpkg --list libopenblas*
[...]
ii  libopenblas-base              0.1alpha2.2-3                 Optimized BLAS (linear algebra) library based on GotoBLAS2
ii  libopenblas-dev               0.1alpha2.2-3                 Optimized BLAS (linear algebra) library based on GotoBLAS2

cbeleites поддерживает Монику
источник

Итак, ваше тестирование (3,5 с против 54 мс) поддерживает мою линию, что «путь 1» значительно медленнее. Правильно?

ttnphns

@ttnphns: да. Но так как svd предоставляется BLAS, это может отличаться от другого BLAS. Я бы ожидал, что хороший оптимизированный BLAS делает что-то вроде этого. Однако в OpenBLAS это не так. Мне лень проверять другие BLAS, но, возможно, несколько человек могли бы проверить свои другие BLAS, чтобы мы выяснили, какие из них оптимизированы для этого случая, а какие нет. (Я написал разработчику OpenBLAS по электронной почте и послал ему ссылку на этот вопрос, так что, возможно, он может добавить некоторую информацию, например, причины не переключать алгоритм svd (X'X)на длинные матрицы.)

cbeleites поддерживает Monica

X^{'}

$X'$

X

$X$

n < p

$n<p$

X^{'} X

$X'X$

u_{n + 1} = X^{'} X u_{n} / | | X^{'} X u_{n} | |

$u_{n+1} = X'Xu_n / ||X'Xu_n||$

v_{1}

$v_1$

X

$X$

X^{'} X

$X'X$

X^{'} \times (X u_{n})

$X' \times (X u_n)$

X X^{T}

$\mathbf X \mathbf X^T$

Я говорил о вашем обновлении, в котором участвует Nipals. Я подтверждаю, что Nipals не участвует в SVD Лапака. О вашем эксперименте с эталонным тестом microbenchmark(X <- matrix(rnorm(5e6), ncol=100), Y <- t(X), svd(X), svd(Y), control=list(order="inorder"), times = 5)тоже может быть что-то подобное .

Элвис

SVD медленнее, но часто считается предпочтительным методом из-за его более высокой числовой точности.

$\mathbf X$ $\frac{1}{n-1}\mathbf X^\top \mathbf X$ $\mathbf{XX}^\top$ $n\ll p$

Вот что написано в справкеpca() функции MATLAB :

Алгоритм главного компонента, который pcaиспользуется для выполнения анализа главного компонента [...]:

'svd' - по умолчанию. Разложение по сингулярным числам (SVD) X.

$n$ $p$

Последнее предложение подчеркивает ключевой компромисс между скоростью и точностью, который здесь присутствует.

$1000\times 100$

X = randn([1000 100]);

tic; svd(X); toc         %// Elapsed time is 0.004075 seconds.
tic; svd(X'); toc        %// Elapsed time is 0.011194 seconds.
tic; eig(X'*X); toc      %// Elapsed time is 0.001620 seconds.
tic; eig(X*X'); toc;     %// Elapsed time is 0.126723 seconds.

$n \ll p$ $\mathbf{XX}^\top$

$\mathbf X$ $X$ $XX^⊤$

X = (\begin{matrix} 1 & 1 & 1 \\ ϵ & 0 & 0 \\ 0 & ϵ & 0 \\ 0 & 0 & ϵ \end{matrix}),

$\mathbf X = \begin{pmatrix}1&1&1\\\epsilon & 0 & 0\\ 0 & \epsilon & 0 \\ 0 & 0 & \epsilon\end{pmatrix},$

3 + ϵ^{2}

$3+\epsilon^2$

ϵ^{2}

$\epsilon^2$

ϵ^{2}

$\epsilon^2$

ϵ = 10^{- 5}

$\epsilon = 10^{-5}$

eps = 1e-5;
X = [1 1 1; eye(3)*eps];
display(['Squared sing. values of X: ' num2str(sort(svd(X),'descend').^2')])
display(['Eigenvalues of X''*X:       ' num2str(sort(eig(X'*X),'descend')')])

получение идентичных результатов:

Squared sing. values of X: 3       1e-10       1e-10
Eigenvalues of X'*X:       3       1e-10       1e-10

$\epsilon = 10^{-10}$

Squared sing. values of X: 3       1e-20       1e-20
Eigenvalues of X'*X:       3           0 -3.3307e-16

$\mathbf X$ $\mathbf X$

Я должен добавить, что часто рады игнорировать эту потенциальную [крошечную] потерю точности и скорее использовать более быстрый метод.

амеба говорит восстановить монику
источник

X^{T}

$\mathbf X^T$

X

$\mathbf X$

Спасибо за ответ и за тщательное рассмотрение плюсов и минусов.

ttnphns

amoeba, может быть, вы нашли время, чтобы показать конкретный пример, где численная стабильность страдает от eig()подхода? (Читатели выиграют: между скоростью и стабильностью есть компромисс. Как можно определиться в конкретной практической ситуации?)

ttnphns

@ttnphns Я переписал весь ответ, предоставив конкретный пример. Посмотри.

говорит амеба, восстанови Монику

@amoeba, большое спасибо за то, что вернулись и привели пример! Я попробовал оба примера epsilon в SPSS и получил результаты, подобные вашим, за исключением самой последней строки: вместо 3 0 -3.3307e-16eigen в spss меня вернули 3 0 0. Похоже, что функция имеет некоторое встроенное и фиксированное значение допуска, выше которого она обнуляется. В этом примере функция выглядела так, как будто она взломала узел числовой нестабильности, обнуляя как крошечные собственные значения, «0» и «-16».

ttnphns