Анализ главных компонент L1-нормы

L1-PCA по сравнению с PCA. Номинальные данные (синие точки); выброс (красная точка); ПК (черная линия); L1-ПК (красная линия); номинальная линия максимального отклонения (пунктирная линия).

Анализ главных компонент L1-нормы (L1-PCA) — это общий метод многомерного анализа данных. L1-PCA часто предпочтительнее стандартного анализа главных компонентов (PCA) L2-нормы, когда анализируемые данные могут содержать выбросы (ошибочные значения или искажения).

И L1-PCA, и стандартный PCA ищут набор ортогональных направлений (главных компонентов), которые определяют подпространство , в котором представление данных максимизируется в соответствии с выбранным критерием. Стандартный PCA количественно определяет представление данных как совокупность L2-нормы точек данных проекций в подпространство или, что эквивалентно, совокупное евклидово расстояние исходных точек от их представлений, спроецированных в подпространство. Вместо этого L1-PCA использует совокупность L1-нормы проекций точек данных в подпространство. В PCA и L1-PCA количество главных компонент (ПК) меньше ранга анализируемой матрицы, что совпадает с размерностью пространства, определяемого исходными точками данных. Поэтому PCA или L1-PCA обычно используются для уменьшения размерности с целью шумоподавления или сжатия данных. Среди преимуществ стандартного PCA, которые способствовали его высокой популярности, - дешевая вычислительная реализация с помощью разложения по сингулярным значениям (SVD). и статистическая оптимальность, когда набор данных генерируется на основе настоящего многомерного нормального источника данных.

Однако в современных больших наборах данных данные часто содержат поврежденные, ошибочные точки, обычно называемые выбросами. Известно, что стандартный PCA чувствителен к выбросам, даже если они составляют небольшую часть обработанных данных. Причина в том, что формулировка L2-PCA с нормой L2 уделяет особое внимание величине каждой координаты каждой точки данных, в конечном итоге переоценивая периферийные точки, такие как выбросы. С другой стороны, следуя формулировке нормы L1, L1-PCA уделяет линейное внимание координатам каждой точки данных, эффективно ограничивая выбросы.

Формулировка

Рассмотрим любую матрицу $\mathbf {X} =[\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{N}]\in \mathbb {R} ^{D\times N}$ состоящий из $N$ $D$-мерные точки данных. Определять $r=rank(\mathbf {X} )$. Для целого числа $K$ такой, что $1\leq K<r$, L1-PCA формулируется как:

${\begin{aligned}&{\underset {\mathbf {Q} =[\mathbf {q} _{1},\mathbf {q} _{2},\ldots ,\mathbf {q} _{K}]\in \mathbb {R} ^{D\times K}}{\max }}~~\|\mathbf {X} ^{\top }\mathbf {Q} \|_{1}\\&{\text{subject to}}~~\mathbf {Q} ^{\top }\mathbf {Q} =\mathbf {I} _{K}.\end{aligned}}$

( 1 )

Для $K=1$, ( 1 ) упрощается до нахождения главного компонента L1-нормы (L1-PC) $\mathbf {X}$ к

${\begin{aligned}&{\underset {\mathbf {q} \in \mathbb {R} ^{D\times 1}}{\max }}~~\|\mathbf {X} ^{\top }\mathbf {q} \|_{1}\\&{\text{subject to}}~~\|\mathbf {q} \|_{2}=1.\end{aligned}}$

( 2 )

В ( 1 )-( 2 ) L1-норма $\|\cdot \|_{1}$ возвращает сумму абсолютных записей своего аргумента и нормы L2 $\|\cdot \|_{2}$ возвращает сумму квадратов записей своего аргумента. Если заменить $\|\cdot \|_{1}$ в ( 2 ) по норме Фробениуса /L2 $\|\cdot \|_{F}$, то задача становится стандартной PCA и решается матрицей $\mathbf {Q}$ который содержит $K$ доминирующие сингулярные векторы $\mathbf {X}$ (т.е. сингулярные векторы, соответствующие $K$ высшие сингулярные значения ).

Метрику максимизации в ( 2 ) можно расширить как

$\|\mathbf {X} ^{\top }\mathbf {Q} \|_{1}=\sum _{k=1}^{K}\sum _{n=1}^{N}|\mathbf {x} _{n}^{\top }\mathbf {q} _{k}|.$

( 3 )

Решение

Для любой матрицы $\mathbf {A} \in \mathbb {R} ^{m\times n}$ с $m\geq n$, определять $\Phi (\mathbf {A} )$ как ближайшую (в смысле L2-нормы) матрицу к $\mathbf {A}$ который имеет ортонормированные столбцы. То есть определить

${\begin{aligned}\Phi (\mathbf {A} )=&{\underset {\mathbf {Q} \in \mathbb {R} ^{m\times n}}{\text{argmin}}}~~\|\mathbf {A} -\mathbf {Q} \|_{F}\\&{\text{subject to}}~~\mathbf {Q} ^{\top }\mathbf {Q} =\mathbf {I} _{n}.\end{aligned}}$

( 4 )

Теорема Прокруста утверждает, что если $\mathbf {A}$ есть СВД $\mathbf {U} _{m\times n}{\boldsymbol {\Sigma }}_{n\times n}\mathbf {V} _{n\times n}^{\top }$, затем $\Phi (\mathbf {A} )=\mathbf {U} \mathbf {V} ^{\top }$.

Маркопулос, Каристинос и Падос показал, что если $\mathbf {B} _{\text{BNM}}$ является точным решением проблемы максимизации бинарной ядерной нормы (BNM).

${\begin{aligned}{\underset {\mathbf {B} \in \{\pm 1\}^{N\times K}}{\text{max}}}~~\|\mathbf {X} \mathbf {B} \|_{*}^{2},\end{aligned}}$

( 5 )

затем

${\begin{aligned}\mathbf {Q} _{\text{L1}}=\Phi (\mathbf {X} \mathbf {B} _{\text{BNM}})\end{aligned}}$

( 6 )

является точным решением L1-PCA в ( 2 ). Ядерная норма $\|\cdot \|_{*}$ in ( 2 ) возвращает сумму сингулярных значений своего матричного аргумента и может быть рассчитана с помощью стандартного SVD. Более того, считается, что для решения L1-PCA $\mathbf {Q} _{\text{L1}}$, решение БНМ можно получить как

${\begin{aligned}\mathbf {B} _{\text{BNM}}={\text{sgn}}(\mathbf {X} ^{\top }\mathbf {Q} _{\text{L1}})\end{aligned}}$

( 7 )

где ${\text{sgn}}(\cdot )$ возвращает $\{\pm 1\}$-знаковая матрица своего матричного аргумента (без ограничения общности можно считать ${\text{sgn}}(0)=1$). Кроме того, отсюда следует, что $\|\mathbf {X} ^{\top }\mathbf {Q} _{\text{L1}}\|_{1}=\|\mathbf {X} \mathbf {B} _{\text{BNM}}\|_{*}$. БНМ в ( 5 ) представляет собой комбинаторную задачу над антиподальными двоичными переменными. Следовательно, ее точное решение может быть найдено путем исчерпывающей оценки всех $2^{NK}$ элементы его набора осуществимости с асимптотической стоимостью ${\mathcal {O}}(2^{NK})$. Таким образом, L1-PCA также можно решить с помощью BNM, но с затратами. ${\mathcal {O}}(2^{NK})$ (экспонента от произведения количества точек данных на количество искомых компонентов). Оказывается, L1-PCA можно решить оптимально (точно) с полиномиальной сложностью по $N$ для фиксированного размера данных $D$, ${\mathcal {O}}(N^{rK-K+1})$.

Для частного случая $K=1$ (один L1-ПК $\mathbf {X}$), BNM принимает форму двоично-квадратичной максимизации (BQM).

${\begin{aligned}&{\underset {\mathbf {b} \in \{\pm 1\}^{N\times 1}}{\text{max}}}~~\mathbf {b} ^{\top }\mathbf {X} ^{\top }\mathbf {X} \mathbf {b} .\end{aligned}}$

( 8 )

Переход от ( 5 ) к ( 8 ) для $K=1$ верно, поскольку уникальное сингулярное значение $\mathbf {X} \mathbf {b}$ равно $\|\mathbf {X} \mathbf {b} \|_{2}={\sqrt {\mathbf {b} ^{\top }\mathbf {X} ^{\top }\mathbf {X} \mathbf {b} }}$, для каждого $\mathbf {b}$. Тогда, если $\mathbf {b} _{\text{BNM}}$ является решением БКМ в ( 7 ), то верно, что

${\begin{aligned}\mathbf {q} _{\text{L1}}=\Phi (\mathbf {X} \mathbf {b} _{\text{BNM}})={\frac {\mathbf {X} \mathbf {b} _{\text{BNM}}}{\|\mathbf {X} \mathbf {b} _{\text{BNM}}\|_{2}}}\end{aligned}}$

( 9 )

это точный L1-ПК $\mathbf {X}$, как определено в ( 1 ). Кроме того, он утверждает, что $\mathbf {b} _{\text{BNM}}={\text{sgn}}(\mathbf {X} ^{\top }\mathbf {q} _{\text{L1}})$ и $\|\mathbf {X} ^{\top }\mathbf {q} _{\text{L1}}\|_{1}=\|\mathbf {X} \mathbf {b} _{\text{BNM}}\|_{2}$.

Алгоритмы

Точное решение экспоненциальной сложности

Как показано выше, точное решение L1-PCA можно получить с помощью следующего двухэтапного процесса:

1. Solve the problem in (5) to obtain $\mathbf {B} _{\text{BNM}}$.
2. Apply SVD on $\mathbf {X} \mathbf {B} _{\text{BNM}}$ to obtain $\mathbf {Q} _{\text{L1}}$.

БНМ в ( 5 ) может быть решена перебором в области $\mathbf {B}$ со стоимостью ${\mathcal {O}}(2^{NK})$.

Точное решение полиномиальной сложности

Кроме того, L1-PCA может быть решена оптимально с меньшими затратами. ${\mathcal {O}}(N^{rK-K+1})$, когда $r=rank(\mathbf {X} )$ является постоянным относительно $N$ (всегда верно для конечной размерности данных $D$).

Приближенные эффективные решатели

В 2008 году Квак предложил итерационный алгоритм приближенного решения L1-PCA для $K=1$. Позднее этот итерационный метод был обобщен для $K>1$ компоненты. Другой приближенный эффективный решатель был предложен Маккоем и Троппом. с помощью полуопределенного программирования (СДП). Совсем недавно L1-PCA (и BNM в ( 5 )) были эффективно решены с помощью итераций с переворотом битов (алгоритм L1-BF).

Алгоритм L1-BF

 1  function L1BF($\mathbf {X}$, $K$):
 2      Initialize $\mathbf {B} ^{(0)}\in \{\pm 1\}^{N\times K}$ and ${\mathcal {L}}\leftarrow \{1,2,\ldots ,NK\}$
 3      Set $t\leftarrow 0$ and $\omega \leftarrow \|\mathbf {X} \mathbf {B} ^{(0)}\|_{*}$
 4      Until termination (or $T$ iterations)
 5          $\mathbf {B} \leftarrow \mathbf {B} ^{(t)}$, $t'\leftarrow t$
 6          For $x\in {\mathcal {L}}$
 7              $k\leftarrow \lceil {\frac {x}{N}}\rceil$, $n\leftarrow x-N(k-1)$
 8              $[\mathbf {B} ]_{n,k}\leftarrow -[\mathbf {B} ]_{n,k}$                // flip bit
 9              $a(n,k)\leftarrow \|\mathbf {X} \mathbf {B} \|_{*}$               // calculated by SVD or faster (see)
10              if $a(n,k)>\omega$
11                  $\mathbf {B} ^{(t)}\leftarrow \mathbf {B}$, $t'\leftarrow t+1$
12                  $\omega \leftarrow a(n,k)$
13              end
14              if $t'=t$                    // no bit was flipped
15                  if ${\mathcal {L}}=\{1,2,\ldots ,NK\}$
16                      terminate
17                  else
18                      ${\mathcal {L}}\leftarrow \{1,2,\ldots ,NK\}$

Вычислительная стоимость L1-BF составляет ${\mathcal {O}}(NDmin\{N,D\}+N^{2}K^{2}(K^{2}+r))$.

Сложные данные

L1-PCA также был распространен для обработки сложных данных. Для сложного L1-PCA в 2018 году были предложены два эффективных алгоритма.

Тензорные данные

L1-PCA также был расширен для анализа тензорных данных в форме L1-Tucker, устойчивого аналога стандартного разложения Такера по норме L1 . Два алгоритма решения задачи L1-Такера — это L1-HOSVD и L1-HOOI.

Код

Код MATLAB для L1-PCA доступен в MathWorks.