Целевая функция PCA: какова связь между максимизацией дисперсии и минимизацией ошибки?

Алгоритм PCA может быть сформулирован в терминах корреляционной матрицы (предположим, что данные уже нормализованы, и мы рассматриваем только проекцию на первый ПК). Целевая функция может быть записана как: $X$

max_{w} (X w)^{T} (X w) s.t. w^{T} w = 1.

$\max_w (Xw)^T(Xw)\; \: \text{s.t.} \: \:w^Tw = 1.$

Это хорошо, и мы используем множители Лагранжа, чтобы решить это, то есть переписать это как:

max_{w} [(X w)^{T} (X w) - λ w^{T} w],

$\max_w [(Xw)^T(Xw) - \lambda w^Tw],$

что эквивалентно

max_{w} \frac{(X w)^{T} (X w)}{w^{T} w},

$\max_w \frac{ (Xw)^T(Xw) }{w^Tw},$

и, следовательно, ( см. здесь, в Mathworld ) кажется равным

max_{w} \sum_{i = 1}^{n} {(distance from point x_{i} to line w)}^{2} .

$\max_w \sum_{i=1}^n \text{(distance from point $x_i$ to line $w$)}^2.$

Но это говорит о том, чтобы максимизировать расстояние между точкой и линией, и из того, что я прочитал здесь , это неверно - оно должно быть $\min$ , а не $\max$ . Где моя ошибка?

Или кто-то может показать мне связь между максимизацией дисперсии в проецируемом пространстве и минимизацией расстояния между точкой и линией?

pca optimization Cam.Davidson.Pilon
источник

Я думаю, что минимальное расстояние используется для соответствия критерию ортогональности для компонентов. Точки проецируются на ПК, которые ортогональны друг другу, но в каждом последующем компоненте оставшаяся дисперсия максимизируется.

Майкл Р. Черник,

Подсказка: что происходит, когда вы сначала рассматриваете наименьшее собственное значение, а не наибольшее?

whuber

@whuber Наименьшее собственное значение, вероятно, имеет ПК, который является решением для конечной целевой функции. Но этот ПК не максимизирует исходную целевую функцию.

Cam.Davidson.Pilon

Я не уверен, что вы подразумеваете под «конечной» и «оригинальной» целевой функцией, Кэм. PCA не является (концептуально) программой оптимизации. Его вывод представляет собой набор основных направлений, а не только одно. Это (интересная) математическая теорема, что эти направления могут быть найдены путем решения последовательности квадратичных программ с ограничениями, но это не является основным для концепций или практики PCA. Я только предполагаю, что, сосредоточившись на наименьшем собственном значении, а не на самом большом, вы можете согласовать две идеи: (1) минимизации расстояний и (2) взгляда на оптимизацию PCA.

whuber

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

Cam.Davidson.Pilon

Ответы:

Пусть - центрированная матрица данных с наблюдениями в строках. Пусть - его ковариационная матрица. Пусть будет единичным вектором, задающим ось в пространстве переменных. Мы хотим, чтобы была первой главной осью. $\newcommand{\X}{\mathbf X}\X$ $n$ $\newcommand{\S}{\boldsymbol \Sigma}\S=\X^\top\X/(n-1)$ $\newcommand{\w}{\mathbf w}\w$ $\w$

Согласно первому подходу первая главная ось максимизирует дисперсию проекции (дисперсия первой главной компоненты). Эта дисперсия определяется как $\X \w$

V a r (X w) = w^{⊤} X^{⊤} X w / (n - 1) = w^{⊤} Σ w .

$\mathrm{Var}(\X\w)=\w^\top\X^\top \X \w/(n-1)=\w^\top\S\w.$

Согласно второму подходу первая главная ось минимизирует ошибку восстановления между и ее восстановлением , то есть сумму квадратов расстояний между исходными точками и их проекциями на . Квадрат ошибки восстановления задается как $\X$ $\X\w\w^\top$ $\w$

\begin{aligned} ‖ X - X w w^{⊤} ‖^{2} & = t r ((X - X w w^{⊤}) (X - X w w^{⊤})^{⊤}) \\ = t r ((X - X w w^{⊤}) (X^{⊤} - w w^{⊤} X^{⊤})) \\ = t r (X X^{⊤}) - 2 t r (X w w^{⊤} X^{⊤}) + t r (X w w^{⊤} w w^{⊤} X^{⊤}) \\ = c o n s t - t r (X w w^{⊤} X^{⊤}) \\ = c o n s t - t r (w^{⊤} X^{⊤} X w) \\ = c o n s t - c o n s t \cdot w^{⊤} Σ w . \end{aligned}

$\begin{align}\newcommand{\tr}{\mathrm{tr}} \|\X-\X\w\w^\top\|^2 &=\tr\left((\X-\X\w\w^\top)(\X-\X\w\w^\top)^\top\right) \\ &=\tr\left((\X-\X\w\w^\top)(\X^\top-\w\w^\top\X^\top)\right) \\ &=\tr(\X\X^\top)-2\tr(\X\w\w^\top\X^\top)+\tr(\X\w\w^\top\w\w^\top\X^\top) \\ &=\mathrm{const}-\tr(\X\w\w^\top\X^\top) \\ &=\mathrm{const}-\tr(\w^\top\X^\top\X\w) \\ &=\mathrm{const} - \mathrm{const} \cdot \w^\top \S \w. \end{align}$

Обратите внимание на знак минус перед основным членом. Из-за этого минимизация ошибки восстановления сводится к максимизации , что является дисперсией. Таким образом, минимизация ошибки восстановления эквивалентна максимизации дисперсии; обе формулировки дают одинаковые . $\w^\top \S \w$ $\w$

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

Что-то, что я заметил, не является ли выпуклой функцией (Что касается поскольку - это PSD? Почему мы пытаемся максимизировать его?

w^{T} Σ w

${w}^{T} \Sigma w$

w

$w$

Σ

$\Sigma$

Рой,

@amoeba Можете ли вы объяснить, как вы переходите от tr () к const на последнем шаге?

Альберто

@alberto Внутри трассы находится число (матрица 1x1); след числа - это само число, поэтому след можно удалить. Эта константа появляется потому, что равна , поэтому существует коэффициент .

Σ

$\Sigma$

X^{⊤} X / n

$X^\top X/n$

1 / n

$1/n$

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

@Leullame Вычисление будет содержать дословно для если это матрица с ортонормированными столбцами. Вам нужно чтобы перейти от строки № 3 к строке № 4. Если матрица имеет ортонормированные столбцы, то действительно будет проекцией на подпространство, натянутое на столбцы (здесь - вектор строки).

W

$W$

W^{⊤} W = I

$W^\top W = I$

W

$W$

x W W^{⊤}

$xWW^\top$

x

$x$

W

$W$

x

$x$

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

@ DanielLópez Ну, мы ищем одномерное подпространство, минимизирующее ошибку реконструкции. 1-мерное подпространство может быть определено вектором единичной нормы, указывающим на его направление, которым является то, что принято считать . Он имеет единичную норму по конструкции.

w

$w$

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