Я изучаю PCA из курса Coursera Эндрю Нг и других материалов. В первом задании Stanford NLP cs224n и в видео лекции Эндрю Нг они проводят разложение по сингулярным значениям вместо разложения по ковариационной матрице по собственным векторам, и Нг даже говорит, что SVD численно более устойчив, чем собственное разложение.
Насколько я понимаю, для PCA мы должны делать SVD матрицы данных (m,n)
размера, а не ковариационной матрицы (n,n)
размера. И разложение по собственным векторам ковариационной матрицы.
Почему они делают SVD ковариационной матрицы, а не матрицы данных?
pca
linear-algebra
svd
eigenvalues
numerics
DongukJu
источник
источник
x=randn(10000); x=x'*x; tic; eig(x); toc; tic; svd(x); toc;
на моей машине выводит 12s для eig () и 26s для svd (). Если он намного медленнее, он должен быть хотя бы более стабильным! :-)eig
илиsvd
на ковариационной матрице, но, насколько я знаю , нет большой разницы между использованиемeig
илиsvd
на матрице ковариаций --- они оба обратно устойчивых алгоритма. Во всяком случае, я бы положил свои деньги на то, чтобы быть более стабильным, так как он делает меньше вычислений (при условии, что оба они реализованы с использованием самых современных алгоритмов).Ответы:
Amoeba уже дал хороший ответ в комментариях, но если вы хотите формальный аргумент, здесь это идет.
Разложение по сингулярным числам матрицы имеет вид , где столбцы являются собственными векторами а диагональные элементы в являются квадратными корнями из собственных значений, то есть .A A=UΣVT V ATA Σ σii=λi(ATA)−−−−−−−√
Как вы знаете, главными компонентами являются ортогональные проекции ваших переменных на пространство собственных векторов эмпирической ковариационной матрицы . Дисперсия компонентов задается своими собственными значениями, .1n−1ATA λi(1n−1ATA)
Рассмотрим любую квадратную матрицу , и вектор такой, что . затемB α∈R v Bv=λv
Определим . SVD будет вычислять собственное разложение чтобы получитьS=1n−1ATA S STS=1(n−1)2ATAATA
Вуаля!
Что касается числовой стабильности, необходимо выяснить, что такое используемые алогриты. Если вы готовы, я считаю, что эти подпрограммы LAPACK используются numpy:
Обновление: Что касается стабильности, реализация SVD, похоже, использует подход «разделяй и властвуй», в то время как в собственной декомпозиции используется простой QR-алгоритм. Я не могу получить доступ к некоторым соответствующим документам SIAM из моего учреждения (сокращение исследований), но я нашел что-то, что могло бы поддержать оценку того, что процедура SVD является более стабильной.
В
они сравнивают устойчивость различных алгоритмов на собственные значения, и кажется, что подход «разделяй и властвуй» (в одном из экспериментов они используют тот же самый, что и numpy!) более стабилен, чем алгоритм QR. Это, наряду с другими заявлениями о том, что методы D & C действительно более стабильны, поддерживает выбор Ng.
источник
@amoeba были отличные ответы на PCA вопросы, в том числе это одно по отношению к СВД PCA. Отвечая на ваш точный вопрос, я сделаю три замечания:
Оказывается, что SVD более устойчив, чем типичные процедуры декомпозиции собственных значений, особенно для машинного обучения. В машинном обучении легко получить высоко коллинеарные регрессоры. SVD работает лучше в этих случаях.
Вот код Python для демонстрации сути. Я создал высококоллинеарную матрицу данных, получил ее ковариационную матрицу и попытался получить ее собственные значения. SVD все еще работает, в то время как обычная собственная декомпозиция терпит неудачу в этом случае.
Выход:
Обновить
Отвечая на комментарий Федерико Полони, вот код с тестированием стабильности SVD против Eig на 1000 случайных выборок той же матрицы выше. Во многих случаях Eig показывает 0 малых собственных значений, что привело бы к сингулярности матрицы, а SVD здесь этого не делает. SVD примерно в два раза точнее при определении небольшого собственного значения, которое может или не может быть важным в зависимости от вашей проблемы.
Выход:
Здесь код код работает. Вместо того, чтобы генерировать случайную ковариационную матрицу для проверки подпрограмм, я генерирую случайную матрицу данных с двумя переменными: где - независимые однородные случайные величины. Таким образом, ковариационная матрица имеет вид: где - дисперсия униформ и коэффициент корреляции между их.
Наименьшее собственное значение: Маленькое собственное значение не может быть вычислено простым подключением в формулу из-за ограниченной точности, поэтому вам нужно Тейлор развернуть его:
Я запускаю моделирования реализаций матрицы данных, вычисляю собственные значения моделируемой ковариационной матрицы и ошибки .j=1,…,m λ^j ej=λ−λ^j
источник
Для пользователей Python я хотел бы отметить, что для симметричных матриц (таких как ковариационная матрица) лучше использовать
numpy.linalg.eigh
функцию вместо общейnumpy.linalg.eig
функции.eigh
в 9-10 раз быстрее, чемeig
на моем компьютере (независимо от размера матрицы) и имеет лучшую точность (на основе теста точности @ Aksakal).Я не убежден в демонстрации преимущества точности SVD с небольшими собственными значениями. @ Тест Аксакала на 1-2 порядка более чувствителен к случайному состоянию, чем к алгоритму (попробуйте отобразить все ошибки вместо того, чтобы свести их к одному абсолютному максимуму). Это означает, что небольшие ошибки в ковариационной матрице будут иметь большее влияние на точность, чем выбор алгоритма собственного разложения. Кроме того, это не связано с основным вопросом, который касается PCA. Самые маленькие компоненты игнорируются в PCA.
Аналогичный аргумент может быть сделан в отношении численной устойчивости. Если бы мне пришлось использовать метод ковариационной матрицы для PCA, я бы разложил его
eigh
вместоsvd
. Если это не удастся (что еще не было продемонстрировано здесь), то, вероятно, стоит переосмыслить проблему, которую вы пытаетесь решить, прежде чем начинать искать лучший алгоритм.источник
eigh
vseig
: mail.scipy.org/pipermail/numpy-discussion/2006-March/…Чтобы ответить на последнюю часть вашего вопроса: «Почему они делают SVD из ковариационной матрицы, а не из матрицы данных?» Я считаю, что это из-за производительности и хранения. Как правило, будет очень большим числом, и даже если большое, мы ожидаем .m n m≫n
Вычисление ковариационной матрицы и последующее выполнение SVD для этого значительно быстрее, чем вычисление SVD для полной матрицы данных в этих условиях для того же результата.
Даже при довольно небольших значениях прирост производительности составляет тысячи (миллисекунд против секунд). Я провел несколько тестов на моей машине, чтобы сравнить с помощью Matlab:
Это просто процессорное время, но потребности в памяти так же, если не больше, важны. Если вы попытаетесь использовать SVD на матрице миллион на тысячу в Matlab, то это приведет к ошибке по умолчанию, поскольку для него требуется рабочий размер массива 7,4 ТБ.
источник