Является ли оптимизация PCA выпуклой?

Целевой функцией анализа главных компонентов (PCA) является минимизация ошибки восстановления в норме L2 (см. Раздел 2.12 здесь . Другое представление пытается максимизировать дисперсию проекции. У нас также есть отличная статья здесь: Какова целевая функция PCA ? )

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

machine-learning pca optimization convex Хайтау Ду
источник

Нет. Вы максимизируете выпуклую функцию (при ограничениях).

user603

Я думаю, что вам нужно определиться с тем, что вы подразумеваете под «оптимизацией PCA». Одна стандартная формулировка состоит в том, чтобы максимизировать

x^{'} A x

$x^\prime\mathbb{A}x$ учетом

x^{'} x = 1

$x^\prime x=1$ . Проблема в том, что выпуклость даже не имеет смысла: область

x^{'} x = 1

$x^\prime x=1$ является сферой, а не евклидовым пространством.

whuber

@ whuber спасибо за ваш комментарий, я не могу уточнить вопрос из-за ограниченных знаний. Я могу подождать, пока некоторые ответы помогут мне прояснить вопрос одновременно.

Haitao Du

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

а не

. Решение то же самое - и ответ становится совершенно ясным.

x^{'} x \leq 1

$x^\prime x\le1$

x^{'} x = 1

$x^\prime x=1$

whuber

Ответы:

Нет, обычные формулировки PCA не являются выпуклыми проблемами. Но они могут быть преобразованы в выпуклую задачу оптимизации.

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

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

Если вы пристально наблюдаете, вы можете увидеть скрывающиеся множители SVD и Лагранжа - но это всего лишь второстепенное шоу, представляющее интерес для сценического интереса, и я не буду комментировать их дальше.

Стандартная максимизирующая дисперсию формулировка PCA (или, по крайней мере, ее ключевой шаг)

\begin{matrix} (*) & Maximize f (x) = x^{'} A x subject to x^{'} x = 1 \end{matrix}

$\text{Maximize }f(x)=\ x^\prime \mathbb{A} x\ \text{ subject to }\ x^\prime x=1\tag{*}$

где матрица - это симметричная положительно-полуопределенная матрица, построенная из данных (обычно это сумма квадратов и матрицы произведений, ее ковариационная матрица или корреляционная матрица). $n\times n$ $\mathbb A$

(Эквивалентно, мы можем попытаться максимизировать неограниченную цель . Мало того, что это более неприятное выражение - это больше не квадратичная функция - но графические особые случаи будут быстро покажем, что она также не является выпуклой функцией. Обычно можно заметить, что эта функция инвариантна относительно пересчетов а затем сводит ее к ограниченной формулировке .) $x^\prime \mathbb{A} x / x^\prime x$ $x\to \lambda x$ $(*)$

Любая проблема оптимизации может быть абстрактно сформулирована как

Найдите хотя бы один который делает функцию как можно большей. $x\in\mathcal{X}$ $f:\mathcal{X}\to\mathbb{R}$

Напомним, что проблема оптимизации является выпуклой, когда она имеет два отдельных свойства:

Домен выпукла. $\mathcal{X}\subset\mathbb{R}^n$ Это можно сформулировать многими способами. Во-первых, всякий раз, когда и и , также , Геометрически: всякий раз , когда две конечные точки отрезка линии лежат в , весь отрезок лежит в . $x\in\mathcal{X}$ $y\in\mathcal{X}$ $0 \le \lambda \le 1$ $\lambda x + (1-\lambda)y\in\mathcal{X}$ $\mathcal X$ $\mathcal X$
Функция выпукла. $f$ Это также может быть сформулировано многими способами. Во-первых, всякий раз, когда и и ,(Нам нужно было, чтобы был выпуклым, чтобы это условие имело какой-либо смысл.) Геометрически: всякий раз, когда является любым отрезком в , график функции (ограниченный этим отрезком) лежит выше или на отрезке, соединяющем и в . $x\in\mathcal{X}$ $y\in\mathcal{X}$ $0 \le \lambda \le 1$
$f (λ x + (1 - λ) y) \geq λ f (x) + (1 - λ) f (y) .$ $f(\lambda x + (1-\lambda)y) \ge \lambda f(x) + (1-\lambda) f(y).$ $\mathcal X$ $\bar{xy}$ $\mathcal X$ $f$ $(x,f(x))$ $(y,f(y))$ $\mathbb{R}^{n+1}$
Архетип выпуклой функции локально всюду параболичен с неположительным старшим коэффициентом: на любом отрезке она может быть выражена в виде с $y\to a y^2 + b y + c$ $a \le 0.$

Сложность с состоит в том, что - это единичная сфера , которая явно не выпуклая. $(*)$ $\mathcal X$ $S^{n-1}\subset\mathbb{R}^n$ Однако мы можем изменить эту проблему, включив меньшие векторы. Это потому, что когда мы масштабируем с коэффициентом , умножается на . Когда , мы можем масштабировать до длины единицы, умножив ее на , увеличивая тем самым но оставаясь в пределах единичный шар . $x$ $\lambda$ $f$ $\lambda^2$ $0 \lt x^\prime x \lt 1$ $x$ $\lambda=1/\sqrt{x^\prime x} \gt 1$ $f$ $D^n = \{x\in\mathbb{R}^n\mid x^\prime x \le 1\}$ Поэтому давайте переформулируем как $(*)$

\begin{matrix} (**) & Maximize f (x) = x^{'} A x subject to x^{'} x \leq 1 \end{matrix}

$\text{Maximize }f(x)=\ x^\prime \mathbb{A} x\ \text{ subject to }\ x^\prime x\le1\tag{**}$

Его домен который явно выпуклый, так что мы на полпути. Осталось рассмотреть выпуклость графика функции . $\mathcal{X}=D^n$ $f$

Хороший способ подумать о проблеме даже если вы не собираетесь выполнять соответствующие вычисления - в терминах спектральной теоремы. $(**)$ В нем говорится, что с помощью ортогонального преобразования вы можете найти хотя бы один базис в котором диагональ: $\mathbb P$ $\mathbb{R}^n$ $\mathbb A$

A = P^{'} Σ P

$\mathbb {A = P^\prime \Sigma P}$

где все недиагональные элементы равны нулю. Такой выбор можно представить как ничего не изменяющий , а просто изменяющий способ его описания : когда вы поворачиваете свою точку зрения, оси гиперповерхностей уровня функции (которые всегда были эллипсоидами) выровнены с осями координат. $\Sigma$ $\mathbb{P}$ $\mathbb A$ $x\to x^\prime \mathbb{A} x$

Поскольку является положительно-полуопределенным, все диагональные элементы в должны быть неотрицательными. Мы можем дополнительно переставить оси (что является еще одним ортогональным преобразованием и поэтому может быть поглощено в ), чтобы гарантировать, что $\mathbb A$ $\Sigma$ $\mathbb P$

σ_{1} \geq σ_{2} \geq \dots \geq σ_{n} \geq 0.

$\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n \ge 0.$

Если мы примем новыми координатами (в том числе ), функция будет $x=\mathbb{P}^\prime y$ $x$ $y=\mathbb{P}x$ $f$

f (y) = y^{'} A y = x^{'} P^{'} A P x = x^{'} Σ x = σ_{1} x_{1}^{2} + σ_{2} x_{2}^{2} + \dots + σ_{n} x_{n}^{2} .

$f(y) = y^\prime \mathbb{A} y = x^\prime \mathbb{P^\prime A P} x = x^\prime \Sigma x = \sigma_1 x_1^2 + \sigma_2 x_2^2 + \cdots + \sigma_n x_n^2.$

Эта функция явно не выпуклая! Его график выглядит как часть гиперпараболоида: в каждой точке внутри тот факт, что все неотрицательны, заставляет его скручиваться вверх, а не вниз . $\mathcal X$ $\sigma_i$

Однако мы можем превратить в выпуклую задачу с помощью одного очень полезного метода. $(**)$ Зная, что максимум произойдет там, где , давайте вычтем постоянную из , по крайней мере, для точек на границе . Это не изменит местоположения каких-либо точек на границе, в которой оптимизируется , потому что оно понижает все значения на границе на одно и то же значение . Это предполагает изучение функции $x^\prime x = 1$ $\sigma_1$ $f$ $\mathcal{X}$ $f$ $f$ $\sigma_1$

g (y) = f (y) - σ_{1} y^{'} y .

$g(y) = f(y) - \sigma_1 y^\prime y.$

Это действительно вычитает постоянную из в граничных точках и вычитает меньшие значения во внутренних точках. Это будет гарантировать , что , по сравнению с , не имеет никакого нового глобального максимума на внутренней части . $\sigma_1$ $f$ $g$ $f$ $\mathcal X$

Давайте рассмотрим, что произошло с ловкостью рук замены на . Поскольку ортогонально, . (Это практически определение ортогонального преобразования.) Следовательно, в терминах координат можно записать $-\sigma_1$ $-\sigma_1 y^\prime y$ $\mathbb P$ $y^\prime y = x^\prime x$ $x$ $g$

g (y) = σ_{1} x_{1}^{2} + \dots + σ_{n} x_{n}^{2} - σ_{1} (x_{1}^{2} + \dots + x_{n}^{2}) = (σ_{2} - σ_{1}) x_{2}^{2} + \dots + (σ_{n} - σ_{1}) x_{n}^{2} .

$g(y) = \sigma_1 x_1 ^2 + \cdots + \sigma_n x_n^2 - \sigma_1(x_1^2 + \cdots + x_n^2) = (\sigma_2-\sigma_1)x_2^2 + \cdots + (\sigma_n - \sigma_1)x_n^2.$

Поскольку для всех , каждый из коэффициентов равен нулю или отрицателен. Следовательно, (a) является выпуклым и (b) оптимизируется, когда . ( тогда подразумевает и оптимум достигается, когда , то есть - до знак - первый столбец ) $\sigma_1 \ge \sigma_i$ $i$ $g$ $g$ $x_2=x_3=\cdots=x_n=0$ $x^\prime x=1$ $x_1=\pm 1$ $y = \mathbb{P} (\pm 1,0,\ldots, 0)^\prime$ $\mathbb P$

Давайте повторим логику. Поскольку оптимизируется на границе где , потому что отличается от просто константой на этой границе, а также потому, что значения еще ближе к значениям внутри , максимумы должны совпадать с максимумами . $g$ $\partial D^n=S^{n-1}$ $y^\prime y = 1$ $f$ $g$ $\sigma_1$ $g$ $f$ $D^n$ $f$ $g$

Whuber
источник

σ_{1}

$\sigma_1$

@amoeba Право по всем пунктам; Спасибо. Я усилил обсуждение этого вопроса.

whuber

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

user795305

g

$g$

X

$\mathcal X$

f

$f$

f

$f$

g

$g$

g

$g$

Нет.

$k$ $M$

$\hat{X} = \underset{rank(X) \leq k}{argmin} \| M - X\|_F^2$

( - норма Фробениуса ). Для вывода см. Теорему Эккарта-Юнга . $\|\cdot\|_F$

Хотя норма выпуклая, множество, над которым она оптимизируется, невыпукло.

Выпуклым релаксации задачи РПЖ, называется Выпуклые Низкий ранг Аппроксимация

$\hat{X} = \underset{\|X\|_* \leq c}{argmin} \| M - X\|_F^2$

( - ядерная норма . Это выпуклая релаксация ранга - точно так же, как - выпуклая релаксация числа ненулевых элементов для векторов) $\|\cdot\|_*$ $\|\cdot\|_1$

Вы можете увидеть статистическое обучение с разреженностью , раздел 6 (матричные разложения) для деталей.

Если вас интересуют более общие проблемы и их связь с выпуклостью, см. Обобщенные модели низкого ранга .

Якуб Барчук
источник

Отказ от ответственности: предыдущие ответы довольно хорошо объясняют, как PCA в своей первоначальной формулировке невыпуклый, но может быть преобразован в выпуклую задачу оптимизации. Мой ответ предназначен только для тех бедных душ (таких как я), которые не очень знакомы с жаргоном юнит-сфер и СВД - что, кстати, приятно знать.

Мой источник - это лекция профессора Тибширани

Для решения задачи оптимизации с помощью выпуклых методов оптимизации существуют две предпосылки.

Целевая функция должна быть выпуклой.
Функции ограничения также должны быть выпуклыми.

Большинство формулировок PCA включают ограничение на ранг матрицы.

В препаратах этого типа PCA условие 2 нарушается. Потому что ограничение, что не является выпуклым. Например, пусть , будут 2 × 2 нулевыми матрицами с одиночной 1 в верхнем левом углу и нижнем правом углу соответственно. Затем каждый из них имеет ранг 1, но их среднее значение имеет ранг 2. $rank(X) = k,$ $J_{11}$ $J_{22}$

honeybadger
источник

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

X

$X$

k

$k$

whuber

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

X

$X$

k

$k$

honeybadger