Каково интуитивное объяснение того, как PCA превращается из геометрической задачи (с расстояниями) в задачу линейной алгебры (с собственными векторами)?

Я много читал о PCA, включая различные учебники и вопросы (такие как этот , этот , этот и этот ).

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

Когда я впервые прочитал это, я сразу подумал о чем-то вроде линейной регрессии; может быть, вы можете решить это с помощью градиентного спуска, если это необходимо.

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

Итак, мой вопрос: как PCA может превратиться из задачи геометрической оптимизации в задачу линейной алгебры? Может ли кто-нибудь дать интуитивное объяснение?

Я не ищу ответ, подобный этому, который гласит: «Когда вы решаете математическую проблему PCA, она оказывается эквивалентной поиску собственных значений и собственных векторов ковариационной матрицы». Пожалуйста, объясните, почему собственные векторы оказываются основными компонентами и почему собственные значения оказываются дисперсией проецируемых на них данных

Кстати, я инженер-программист, а не математик.

Примечание: рисунок выше был взят и изменен из этого руководства PCA .

Постановка задачи

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

Верно. Я объясняю связь между этими двумя формулировками в моем ответе здесь (без математики) или здесь (с математикой).

Давайте возьмем вторую формулировку: PCA пытается найти направление, в котором проекция данных на него имеет максимально возможную дисперсию. Это направление по определению называется первым основным направлением. Мы можем формализовать это следующим образом: учитывая ковариационную матрицу , мы ищем вектор имеющий единичную длину, , такой, что максимально.$\mathbf C$$\mathbf w$$\|\mathbf w\|=1$$\mathbf w^\top \mathbf{Cw}$

(На всякий случай, если это не ясно: если является центрированной матрицей данных, то проекция задается как а ее дисперсия .)$\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}$

С другой стороны, собственный вектор по определению является любым вектором , для которого .$\mathbf C$$\mathbf v$$\mathbf{Cv}=\lambda \mathbf v$

Оказывается, первое главное направление задается собственным вектором с наибольшим собственным значением. Это нетривиальное и удивительное утверждение.

Доказательств

Если кто-то откроет какую-либо книгу или учебник по PCA, он может найти там следующее почти однострочное доказательство приведенного выше утверждения. Мы хотим максимизировать при условии, что ; это можно сделать, введя множитель Лагранжа и максимизируя ; дифференцируя, мы получаем , который является уравнением собственного вектора. Мы видим, что фактически является наибольшим собственным значением, подставляя это решение в целевую функцию, которая дает$\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$ . В силу того, что эта целевая функция должна быть максимизирована, должно быть наибольшим собственным значением, QED.$\lambda$

Это имеет тенденцию быть не очень интуитивным для большинства людей.

Лучшее доказательство (см., Например, этот аккуратный ответ @cardinal ) говорит, что, поскольку является симметричной матрицей, она является диагональной в своем базисе собственных векторов. (На самом деле это называется спектральной теоремой .) Таким образом, мы можем выбрать ортогональный базис, а именно тот, который задается собственными векторами, где является диагональным и имеет собственные значения на диагонали. На этом основании упрощается до , или, другими словами, дисперсия определяется взвешенной суммой собственных значений. Почти сразу же, чтобы максимизировать это выражение, нужно просто взять$\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)$первый собственный вектор, дающий дисперсию (действительно, отклонение от этого решения и «обмен» частями наибольшего собственного значения на части меньших приведет только к меньшей общей дисперсии). Обратите внимание, что значение не зависит от базиса! Переход к базису собственных векторов равносилен вращению, поэтому в 2D можно представить просто вращение листа бумаги с диаграммой рассеяния; очевидно, это не может изменить любые отклонения.$\lambda_1$$\mathbf w^\top \mathbf{C w}$

Я думаю, что это очень интуитивный и очень полезный аргумент, но он опирается на спектральную теорему. Так что реальная проблема здесь, я думаю, заключается в следующем: какова интуиция, лежащая в основе спектральной теоремы?

Спектральная теорема

Возьмем симметричная матрица . Возьмите его собственный вектор с наибольшим собственным значением . Сделайте этот собственный вектор первым базисным вектором и случайным образом выберите другие базисные векторы (чтобы все они были ортонормированными). Как будет выглядеть на этом основании?$\mathbf C$$\mathbf w_1$$\lambda_1$$\mathbf C$

Он будет иметь в верхнем левом углу, потому что в этом базисе и должен быть равен .$\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)$

По тому же аргументу он будет иметь нули в первом столбце под .$\lambda_1$

Но поскольку он симметричен, он будет иметь нули в первой строке после . Так это будет выглядеть так:$\lambda_1$

где пустое пространство означает, что там есть блок из нескольких элементов. Поскольку матрица симметрична, этот блок также будет симметричным. Таким образом, мы можем применить к нему точно такой же аргумент, эффективно используя второй собственный вектор в качестве второго базисного вектора и получая и по диагонали. Это может продолжаться до тех пор, пока станет диагональным. Это по существу спектральная теорема. (Обратите внимание, как это работает только потому, что симметричен.)$\lambda_1$$\lambda_2$$\mathbf C$$\mathbf C$

Вот более абстрактная переформулировка того же аргумента.

Мы знаем, что , поэтому первый собственный вектор определяет одномерное подпространство, где действует как скалярное умножение. Теперь возьмем любой вектор ортогональный . Тогда почти сразу же также ортогонален . На самом деле:$\mathbf{Cw}_1 = \lambda_1 \mathbf w_1$$\mathbf C$$\mathbf v$$\mathbf w_1$$\mathbf {Cv}$$\mathbf w_1$

Это означает, что действует на всем оставшемся подпространстве, ортогональном , так что он остается отделенным от . Это важнейшее свойство симметричных матриц. Таким образом, мы можем найти самый большой собственный вектор там, , и действовать аналогичным образом, в конечном итоге построив ортонормированный базис собственных векторов.$\mathbf C$$\mathbf w_1$$\mathbf w_1$$\mathbf w_2$

Экартом и Янгом был получен результат 1936 года ( https://ccrma.stanford.edu/~dattorro/eckart%26young.1936.pdf ), в котором говорится:

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

где M (r) - множество матриц ранга r, что в основном означает, что первые r компонентов SVD X дают наилучшее приближение матрицы ранга X, а наилучший определяется в терминах квадрата нормы Фробениуса - суммы квадратов элементы матрицы.

Это общий результат для матриц и на первый взгляд не имеет ничего общего с наборами данных или уменьшением размерности.

Однако, если вы не думаете о как о матрице, а скорее думаете о столбцах матрицы представляющих векторы точек данных, то является приближением с минимальной ошибкой представления в терминах квадратов разностей ошибок.$X$$X$$\hat{X}$

Это мой взгляд на линейную алгебру позади PCA. В линейной алгебре одной из ключевых теорем является . В нем говорится, что если S является любой симметричной n на n матрицей с действительными коэффициентами, то S имеет n собственных векторов, причем все собственные значения являются действительными. Это означает, что мы можем написать с D диагональной матрицей с положительными элементами. Это и нет ничего плохого в предположении . А - это изменение базисной матрицы. То есть, если наш исходный базис был , то относительно базиса, заданного$\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)$действие S диагонально. Это также означает, что можно рассматривать как ортогональный базис с Если бы наша ковариационная матрица была для n наблюдений n переменных, мы бы сделали это. Базис, предоставленный является базой PCA. Это следует из фактов линейной алгебры. По сути, это так, потому что базис PCA является базисом собственных векторов, и существует не более n собственных векторов квадратной матрицы размера n. Конечно, большинство матриц данных не являются квадратными. Если X - матрица данных с n наблюдениями p переменных, то X имеет размер n по p. Я буду предполагать, что (больше наблюдений, чем переменных) и что$A(x_i)$$||A(x_i)|| = \lambda_i$$A(x_i)$
$n>p$$rk(X) = p$(все переменные линейно независимы). Никакое предположение не является необходимым, но оно поможет с интуицией. Линейная алгебра имеет обобщение из спектральной теоремы, называемое сингулярным разложением. Для такого X он утверждает, что с U, V ортонормированными (квадратными) матрицами размера n и p и вещественная диагональная матрица с только неотрицательной записи по диагонали. Опять же, мы можем переставить базис V так, чтобы В матричных терминах это означало, что если и если . $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$дать разложение PCA. Точнее - разложение PCA. Почему? Опять же, линейная алгебра говорит, что могут быть только собственные векторы. SVD дает новые переменные (заданные столбцами V), которые являются ортогональными и имеют убывающую норму. $\Sigma V^{t}$

«который одновременно максимизирует дисперсию проецируемых данных». Вы слышали о коэффициенте Рэлея ? Может быть, это один из способов увидеть это. А именно, коэффициент Релея ковариационной матрицы дает дисперсию проецируемых данных. (а вики-страница объясняет, почему собственные векторы максимизируют фактор Рэлея)

@amoeba дает аккуратную формализацию и доказательство:

Мы можем формализовать это следующим образом: учитывая ковариационную матрицу C, мы ищем вектор w, имеющий единичную длину, ‖w‖ = 1, такой, что w ^T Cw является максимальным.

Но я думаю, что есть одно интуитивное доказательство:

Оказывается, первое главное направление задается собственным вектором с наибольшим собственным значением. Это нетривиальное и удивительное утверждение.

Мы можем интерпретировать w ^T Cw как точечное произведение между вектором w и Cw, которое получается путем преобразования w :

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

Поскольку w имеет фиксированную длину, для максимизации w ^T Cw нам понадобится:

1. увеличить imizeCw‖
2. увеличить cos (w, Cw)

Оказывается, если мы возьмем w как собственный вектор C с наибольшим собственным значением, мы можем заархивировать оба одновременно:

1. ‖Cw‖ - это максимум, (если w отклоняется от этого собственного вектора, разложите его вдоль ортогональных собственных векторов, вы должны увидеть уменьшение «Cw».)
2. w и Cw в одном направлении, cos (w, Cw) = 1, не более

Поскольку собственные векторы ортогональны, вместе с другими собственными векторами C они образуют набор главных компонент X.

доказательство 1

разложить w на ортогональный первичный и вторичный собственные векторы v1 и v2 , предположим, что их длина равна v1 и v2 соответственно. мы хотим доказать

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

поскольку λ ₁ > λ ₂ , мы имеем

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

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

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

= (λ ₁ ) ² * w ²