Алгоритмы неотрицательной матричной факторизации

Классический бумажный перевод NIPS 2000.

Резюме

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

Введение

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

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

неотрицательная матричная факторизация

Теперь мы формально начинаем анализировать, как использовать алгоритмы для решения следующих задач:

В неотрицательной матричной факторизации (NMF), учитывая неотрицательную матрицу V, найдите неотрицательные матричные множители W и H такие, что:

$(1): V\approx WH$

NMF может применять следующие методы статистического анализа многомерных данных. Учитывая набор многомерных n-мерных векторов данных в $n\times x$ в столбцах матрицы V (m — количество примеров в наборе данных). Затем эта матрица приблизительно разлагается на $n\times r$ Матрица W и $r\times m$ матрица Х. Обычно r меньше, чем n или m, так что W и H меньше, чем исходная матрица V. Конечным результатом является сжатая форма исходной матрицы данных.

Смысл приблизительно равных в формуле (1) заключается в том, что можно использовать формулу столбец за столбцом $v\approx Wh$ представить, где v и h - соответствующие столбцы матрицы V и матрицы H . То есть каждый вектор данных v приблизительно представляет собой линейную комбинацию столбцов матрицы W, взвешенных по компонентам h. Таким образом, можно считать, что W содержит базисные векторы, оптимизированные для линейной аппроксимации данных в V. Поскольку для представления большого количества векторов данных используется небольшое количество базисных векторов, хорошее приближение может быть достигнуто только в том случае, если базисные векторы обнаруживают скрытую структуру данных.

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

Здесь мы обсуждаем два алгоритма NMF, основанные на итеративном обновлении W и H. Поскольку эти два алгоритма просты в реализации и гарантируют их сходимость, они очень практичны в реальных ситуациях. Другие алгоритмы могут быть более эффективными с точки зрения общего времени вычислений, но их сложнее реализовать и трудно обобщить на другие функции стоимости. Факторы Алгоритм, аналогичный нашему, использовался для деконволюции эмиссионных томографических и астрономических изображений.

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

функция стоимости

найти $V\approx WH$ Приближенное решение , нам сначала нужно определить функцию стоимости для количественной оценки степени приближения. Эта функция стоимости может быть построена с использованием расстояния между двумя неотрицательными матрицами A и B. Одной из используемых мер расстояния является вычисление квадрата значения евклидова расстояния между A и B.

$(2): ||A-B||^2 = \sum_{ij}(A_{ij} - B_{ij})^2$

Нижняя граница этой формулы равна 0, и расстояние исчезает только при A=B.

Еще одна полезная мера:

$(3): D(A||B) = \sum_{ij}(A_{ij} \log{\frac{A_{ij}}{B_{ij}}} - A_{ij}+B_{ij})$

Подобно евклидову расстоянию, его нижняя граница равна 0, и расстояние исчезает, когда A=B. Но его нельзя назвать «расстоянием», потому что это выражение не является симметричным между А и В, поэтому мы называем его «расхождением» А по отношению к В. Его можно резюмировать как дивергенцию KL или относительную энтропию, когда $\sum_{ij}A_{ij}=\sum_{ij}B_{ij}=1$ , A и B можно рассматривать как стандартизированные распределения вероятностей.

Теперь мы можем сформулировать NMF как задачу оптимизации в соответствии со следующими двумя формулировками:

проблема оптимизации 1: в условиях ограничений $W, H \geq 0$ , с W и H в качестве параметров, минимизировать $||V - WH||^2$ .

проблема оптимизации 2: в условиях ограничений $W, H \geq 0$ , с W и H в качестве параметров, минимизировать $D(V||WH)$ .

Хотя уравнение $||V - WH||^2$ и $D(V||WH)$ Он выпуклый, когда рассматривается только одна из W или H, но не когда рассматриваются обе переменные WH. Поэтому нецелесообразно найти алгоритм, который может найти глобальный минимум для решения двух вышеуказанных задач оптимизации. Однако существует множество методов численной оптимизации, которые можно использовать для нахождения локальных минимумов.

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

Мультипликативное правило обновления

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

Теорема 1: Евклидово расстояние $||V-WH||$ Без приращения в следующих правилах обновления:

$(4): H_{a\mu} \leftarrow H_{a\mu}\frac{(W^T V)_{a\mu}}{(W^T W H)_{a\mu}}$

$(4): W_{ia} \leftarrow W_{ia}\frac{(V H^T)_{ia}}{(W H H^T)_{ia}}$

В приведенном выше правиле обновления евклидово расстояние будет фиксированным, когда W и H находятся в критической точке формулы расстояния.

Теорема 2:Расхождение $D(V|WH)$ Без приращения в следующих правилах обновления:

$(5): H_{a\mu} \leftarrow H_{a\mu}\frac{\frac{\sum_{i}W_{ia}V_{i\mu}}{WH_{i\mu}}}{\sum_k W_{ka}}$

$(5): W_{ia} \leftarrow W_{ia}\frac{\frac{\sum_{\mu}H_{a\mu}V_{i\mu}}{WH_{i\mu}}}{\sum_v H_{av}}$

В приведенном выше правиле обновления, когда W и H находятся в критической точке формулы дивергенции, дивергенция больше не будет обновляться.

Доказательство приведенной выше теоремы будет дано позже. Мы видим, что каждое обновление умножается на коэффициент. В частности, когда V = WH, можно интуитивно увидеть, что этот множитель один и тот же, и при фиксированном правиле обновления получается идеальное разложение.

Правила обновления умножения и сложения

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

$(6):H_{a\mu} \leftarrow H_{a\mu} + \eta_{a\mu}[(W^TV)_{a\mu} - (W^T WH)_{a\mu}]$

если $\eta_{a\mu}$ Если установить небольшое положительное число, приведенное выше уравнение эквивалентно обычному градиентному спуску. Пока число достаточно мало, оно может быть уменьшено при обновлении. $||V-WH||$ .

Если мы настроим переменную на самый крутой наклон и установим:

$(7): \eta_{a\mu}=\frac{H_{a\mu}}{(W^TWH)_{a\mu}}$

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

Для формулы дивергенции мы корректируем наклон самого крутого градиентного спуска следующим образом:

$(8): H_{a\mu} \leftarrow H_{a\mu} + \eta_{a\mu}[\sum_{i}W_{ia}\frac{V_{i\mu}}{(WH)_{i\mu}}-\sum_{i}W_{ia}]$

Аналогичным образом, если $\eta_{a\mu}$ Если установить небольшое положительное число, приведенное выше уравнение эквивалентно обычному градиентному спуску. Пока число достаточно мало, оно может быть уменьшено при обновлении. $D(V||WH)$ . Если установлено:

$(9): \eta_{a\mu} = \frac{H_{a\mu}}{\sum_i W_{ia}}$

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

Так как мы $\eta_{a\mu}$ недостаточно мала, чтобы гарантировать уменьшение функции стоимости этого скорректированного градиентного спуска. Удивительно, однако, как показано в следующем разделе, приведенные выше предположения верны.

Доказательство сходимости

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

Определение 1: $G(h,h')$ да $F(h)$ Вспомогательная функция, удовлетворяющая следующим условиям:

$(10): G(h,h')\geq F(h), G(h,h)=F(h)$

Эта вспомогательная функция является полезной концепцией в соответствии со следующей леммой. (Это также показано на вставке к рисунку 1)

Лемма 1: Если G является вспомогательной функцией, то F не увеличивается при обновлении следующим образом:

$(11): h^{t+1} = \arg\min_{h}G(h,h^t)$

доказывать: $F(h^{t+1}) \leq G(h^{t+1}, h^t) \leq G(h^t,h^t) = F(h^t)$

Обратите внимание, что только когда $h^t$ за $G(h,h^t)$ глобальный минимум $F(h^{t+1})=F(h^t)$ . Если производная F существует и $h^{t}$ Окрестность непрерывна, т. е. $\nabla F(h^t) = 0$ . Следовательно, многократно обновляя уравнение 11, мы можем получить локальный минимум, в котором целевая функция сходится. $h_{min} = \arg\min_h F(h)$

$(12): F(h_{min}) \leq ... F(h^{t+1})\leq F(h^t) ... \leq F(h_2) \leq F(h_1) \leq F(h_0)$

Ниже мы покажем, как $||V-WH||$ и $D(V,WH)$ Определите соответствующие вспомогательные функции $G(h,h^t)$ . Теоремы 1 и 2 могут напрямую следовать правилу обновления уравнения 11.

Лемма 2:если $K(h^t)$ диагональная матрица,

$(13): K_{ab}(h^t) = \delta_{ab}\frac{W^T Wh^t}{h^t_a}$

но

$(14): G(h,h^t)=F(h^t)+(h-h^t)^T \nabla F(h^t) + \frac{1}{2}(h-h^t)^T K(h^t)(h-h^t)$

за

$(15): F(h)=\frac{1}{2} \sum_i(v_i- \sum_a W_{ia} h_a)^2$

вспомогательная функция.

доказывать: потому что видимо $G(h,h)=F(h)$ , так что нужно только доказать $G(h,h') \geq F(h)$ . Чтобы доказать это неравенство, нам нужно

$(16): F(h) = F(h^t) + (h-h^t)^T \nabla F(h^t) + \frac{1}{2}(h-h^t)^T(W^TW)(h-h^t)$

Сравнивая с уравнением 14, находим, что $G(h,h') \geq F(h)$ Эквивалентно

$(17): 0 \leq (h-h^t)^T[K(h^t) - W^TW](h-h^t)$

Чтобы доказать положительный полуопределенный случай, рассмотрим матрицы:

$(18): M_{ab}(h^t)=h_a^t(K(h^t)-W^TW)_{ab}h_b^t$

Только $K-W^TW$ форма регулировки. Следовательно, только если M соответствует следующей формуле, $K-W^TW$ Имеет положительную полуопределенность:

(19):v^T Mv = \sum_{ab}v_a M_{ab} v_b \\ (20):=\sum_{ab}h^t_a(W^TW)_{ab}h^t_bv_a^2-v_ah^t_a(W^TW)_{ab}h_b^tv_b \\ (21):=\sum_{ab}(W^TW)_{ab}h_a^th_b^t[\frac{1}{2}v_a^2 + \frac{1}{2}v_b^2 - v_av_b] \\ (22):=\frac{1}{2}\sum_{ab}(W^TW)_{ab}h_a^th_b^t(v_a-v_b)^2 \\ (23):\geq 0

Теперь мы можем доказать сходимость теоремы 1.

Доказательство теоремы 1.: Используйте результат уравнения 14 для замены в уравнении 11 $G(h,h^t)$ , получить правило обновления:

$(24): h^{t+1}=h^t - K(h^t)^{-1} \nabla F(h^t)$

Поскольку уравнение 14 является вспомогательной функцией, согласно лемме 1 F не возрастает в правиле обновления. Запишите приведенную выше формулу полностью, вы можете получить:

$(25): h^{t+1}_a= h^{t}_a \frac{(W^Tv)_a}{(W^TWh^t)_a}$

Поменяв роли W и H в лемме 1 и лемме 2, можно доказать, что F не возрастает по правилу обновления W аналогичным образом.

Далее находим вспомогательные функции для уравнения стоимости дивергенции.

Лемма 3:определение

(26): G(h,h^t)=\sum_i(v_i \log{v_i} - v_i) + \sum_{ia} W_{ia}h_a \\ (27):-\sum_{ia}v_i\frac{W_{ia}h^t_a}{\sum_b W_{ib} h^t_b} (\log{W_{ia} h_a - \log{\frac{W_{ia}h^t_a}{\sum_b W_{ib} h^t_b}}})

за

(28): F(h)=\sum_i v_i \log(\frac{v_i}{\sum_a W_{ia} h_a})- v_i + \sum_a W_{ia} h_a

вспомогательная функция.

доказывать: потому что видимо $G(h,h)=F(h)$ , так что нужно только доказать $G(h,h') \geq F(h)$ . Выведем это неравенство из выпуклости логарифмической функции:

(29): -\log \sum_a W_{ia} h_a \leq -\sum_a a_a \log \frac{ W_{ia} h_a}{a_a}

Приведенная выше формула суммирует все союзы $a_a$ установлены. Предполагать

(30): a_a =\frac{ W_{ia} h_a}{\sum_b W_{ib} h_b}

Вы можете получить:

(31): -\log \sum_a W_{ia} h_a \leq - \sum_a \frac{ W_{ia} h_a}{\sum_b W_{ib} h_b} (\log W_{ia} h_a - \log\frac{ W_{ia} h_a}{\sum_b W_{ib} h_b} )

Приведенное выше неравенство следует $G(h,h') \geq F(h)$ .

Доказательство теоремы 2 следует лемме 1 и ее применению:

Теорема 2 Доказательство: заказать $G(h,h^t)$ Чтобы минимизировать, вам нужно установить градиент равным 0, чтобы найти h:

(32): \frac{dG(h,h^t)}{dh_a} = - \sum_i v_i \frac{ W_{ia} h_a^t}{\sum_b W_{ib} h_b^t} \frac{1}{h_a} + \sum_i W_{ia} = 0

Следовательно, правило обновления, принятое уравнением 11, должно быть следующим:

(33): h_a^{t+1} = \frac{h_a^t}{\sum_b W_{kb}} \sum_i \frac{v_i}{\sum_b W_{ib}h_b^t} W_{ia}

Поскольку G является вспомогательной функцией, F в уравнении 28 не увеличивается в правиле обновления. Перепишите приведенную выше формулу в матричной форме и найдите правило обновления, эквивалентное уравнению 5. Поменяв роли W и H, можно аналогичным образом доказать, что F не возрастает по правилу обновления W.

обсуждать

Мы показали, что применение правила обновления в Уравнении 4 и Уравнении 5 может найти локальные оптимальные решения Задачи 1 и Задачи 2. Сходимость функции доказывается определением подходящих вспомогательных функций. Мы обобщим эти доказательства на более сложные ограничения. Правило обновления в вычислительном отношении очень легко реализовать, и ожидается, что оно будет широко использоваться.

Спасибо Bell Labs за поддержку и Carlos Brody, Ken Clarkson, Corinna Cortes, Roland Freund, Linda Kaufman, Yann Le Cun, Sam Roweis, Larry Saul, Margaret Wright за помощь и обсуждения.

На самом деле, это проверка латексной функции :)