Почему PCA максимизирует общую дисперсию проекции?

Кристофер Бишоп пишет в своей книге « Распознавание образов и машинное обучение», доказывая, что каждый последовательный главный компонент максимизирует дисперсию проекции в одно измерение после того, как данные были спроецированы в ортогональное пространство для ранее выбранных компонентов. Другие показывают аналогичные доказательства.

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

machine-learning variance pca dimensionality-reduction eigenvalues Михал
источник

Не могли бы вы рассказать нам, что именно будет означать «дисперсия» пятимерного набора данных, возникающая в результате проекции набора данных на пять измерений? (Для того, чтобы такое количество было

максимально увеличено,

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

Михал

@ user123675: В своем последнем комментарии вы, вероятно, имеете в виду «максимизировать», а не «минимизировать».

амеба

Да ты прав. Сожалею!

Михал

Ответы:

То, что понимается под дисперсией в нескольких измерениях («общая дисперсия»), является просто суммой дисперсий в каждом измерении. Математически это след ковариационной матрицы: след просто сумма всех диагональных элементов. Это определение имеет различные приятные свойства, например, трасса инвариантна относительно линейных ортогональных преобразований, что означает, что если вы поворачиваете свои оси координат, общая дисперсия остается неизменной.

В книге Бишопа (раздел 12.1.1) доказано, что ведущий собственный вектор ковариационной матрицы задает направление максимальной дисперсии. Второй собственный вектор задает направление максимальной дисперсии при дополнительном ограничении на то, что он должен быть ортогональным первому собственному вектору и т. Д. (Я считаю, что это составляет упражнение 12.1). Если цель состоит в том, чтобы максимизировать общую дисперсию в двумерном подпространстве, то эта процедура является жадной максимизацией: сначала выберите одну ось, которая максимизирует дисперсию, а затем другую.

Ваш вопрос: почему эта жадная процедура получает глобальный максимум?

Вот хороший аргумент, который @whuber предложил в комментариях. Давайте сначала совместим систему координат с осями PCA. Ковариационная матрица становится диагональной: . Для простоты рассмотрим тот же 2D-случай, т. Е. Что такое плоскость с максимальной полной дисперсией? Мы хотим доказать, что это плоскость, заданная первыми двумя базисными векторами (с полной дисперсией ). $\boldsymbol{\Sigma} = \mathrm{diag}(\lambda_i)$ $\lambda_1+\lambda_2$

Рассмотрим плоскость, натянутую на два ортогональных вектора и . Общая дисперсия в этой плоскости равнаТаким образом, это линейная комбинация собственных значений с коэффициентами, которые все положительны, не превышают (см. Ниже) и суммируют до . Если это так, то почти очевидно, что максимум достигается в . $\mathbf{u}$ $\mathbf{v}$

u^{⊤} Σ u + v^{⊤} Σ v = \sum λ_{i} u_{i}^{2} + \sum λ_{i} v_{i}^{2} = \sum λ_{i} (u_{i}^{2} + v_{i}^{2}) .

$\mathbf{u}^\top\boldsymbol{\Sigma}\mathbf{u} + \mathbf{v}^\top\boldsymbol{\Sigma}\mathbf{v} = \sum \lambda_i u_i^2 + \sum \lambda_i v_i^2 = \sum \lambda_i (u_i^2+v_i^2).$

λ_{i}

$\lambda_i$

1

$1$

2

$2$

λ_{1} + λ_{2}

$\lambda_1 + \lambda_2$

Осталось только показать, что коэффициенты не могут превышать . Обратите внимание, что , где является в -го базисного вектора. Эта величина является квадратом длины проекции на плоскость, натянутую на и . Поэтому он должен быть меньше квадрата длины который равен , QED. $1$ $u_k^2+v_k^2 = (\mathbf{u}\cdot\mathbf{k})^2+(\mathbf{v}\cdot\mathbf{k})^2$ $\mathbf{k}$ $k$ $\mathbf k$ $\mathbf u$ $\mathbf v$ $\mathbf k$ $|\mathbf{k}|^2=1$

См. Также ответ @ cardinal на Какова целевая функция PCA? (следует той же логике).

амеба
источник

(+1) Но не является ли интуитивно очевидным, что при наличии набора кошельков с разной суммой наличности (моделирование неотрицательных собственных значений) и фиксированного числа которое вы можете выбрать, выбор самых богатых кошельков максимизирует вашу общую сумму денежные средства? Доказательство того, что эта интуиция верна, почти тривиально: если вы не взяли наибольших, вы можете улучшить свою сумму, заменив наименьшую, которую вы взяли, на большую сумму.

k

$k$

k

$k$

k

$k$

whuber

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

Innuo

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

k

$k$

1

$1$

k

$k$

whuber

@amoeba: я имею в виду, что мы рассматриваем проблему в базе, состоящей из собственных векторов (это база для u и v, если мы вычисляем их дисперсию путем умножения на диагональную ковариационную матрицу). В конце концов, вы и v окажетесь ими, но на этапе этого доказательства мы не должны предполагать это, я думаю. Не следует ли утверждать, что если бы в какой-то момент сумма была больше 1, то 2 вектора больше не были бы ортогональными, поскольку основание ортогонально, и каждый из векторов дает не более 1? Но опять же, почему мы ограничиваемся ортогональными векторами u и v?

Михал

@ Heisenberg: Ах, я вижу! Нет конечно я не это имел ввиду! Но теперь я понимаю, почему это сбивает с толку. Я переписал это последнее доказательство, чтобы избавиться от этого шага «выбора основы». Пожалуйста, смотрите мое редактирование. Спасибо.

амеба

Если у вас есть некоррелированных случайных величин, отсортированных в порядке убывания их дисперсии, и вас попросили выбрать из них так, чтобы дисперсия их суммы была максимизирована, согласитесь ли вы, что жадный подход выбора первых приведет этому? $N$ $k$ $k$

Данные, спроецированные на собственные векторы ее ковариационной матрицы, по существу представляют собой некоррелированных столбцов данных, дисперсия которых равна соответствующим собственным значениям. $N$

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

Второе соотношение мне ясно, потому что коэффициент корреляции между двумя (нулевым средним) векторами пропорционален их внутреннему произведению.

Связь между максимизацией дисперсии и собственным разложением ковариационной матрицы следующая.

Предположим, что - это матрица данных после центрирования столбцов. Нам нужно найти направление максимальной дисперсии. Для любого единичного вектора дисперсия после проецирования вдоль равна $D$ $v$ $v$

$E[(Dv)^t Dv] = v^t E[D^tD] v = v^t Cov(D) v$

который максимизируется, если - собственный вектор соответствующий наибольшему собственному значению. $v$ $Cov(D)$

Innuo
источник

Исходный вопрос скорее такой: выберите ортогональных линейных комбинаций из них (в отличие от из них), чтобы сумма их дисперсий была максимальной. Все еще очевидно, что жадный подход выбора первых делает?

k

$k$

k

$k$

k

$k$

амеба

Нахождение ортогональных линейных комбинаций, а затем выбор первого наиболее варианта из них - это то, что описывает процесс (в общих чертах). В моем ответе просто утверждается, что ортогональность - это то, что достаточно для того, чтобы жадный процесс достиг цели максимизации общей дисперсии.

N

$N$

k

$k$

Innuo

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

N

$N$

k

$k$

k

$k$

амеба

Ах, я понимаю путаницу. В моем ответе была опечатка. Исправлено сейчас.

Innuo

Я думаю, что вы можете кое-что здесь, но волшебный вид суммы требует объяснения. Какое отношение это имеет к PCA или даже к спектральному разложению?

whuber