Неотрицательное матричное разложение

В хемометрике неотрицательное матричное разложение имеет долгую историю под названием «метод автомодельного разрешения кривых»[8] В этом контексте вектора в правой матрице являются непрерывными кривыми, а не дискретными векторами. Ранние работы по неотрицательному матричному разложению были проведены финской группой исследователей в середине 1990-х под названием положительное разложение матрицы[9][10]. Метод стал более широко известен как неотрицательное матричное разложение, после того как Ли и Сын исследовали свойства алгоритма и опубликовали несколько простых полезных алгоритмов для двух видов разложения[11][12].

Пусть матрица V является произведением матриц W и H,

${\displaystyle \mathbf {V} =\mathbf {W} \mathbf {H} \,.}$

Умножение матриц может быть имплементировано через вычисление вектора-столбца матрицы V как линейной комбинации векторов-столбцов в W, используя коэффициенты из столбцов матрицы H. То есть каждый столбец матрицы V может быть вычислен следующим образом:

${\displaystyle \mathbf {v} _{i}=\mathbf {W} \mathbf {h} _{i}\,,}$

где v_i является i-ым вектор-столбцом произведения матрицы V, а h_i является i-ым вектор-столбцом матрицы H.

При умножении матриц размерности матриц-сомножителей могут быть существенно меньше, чем размерность произведения матриц, и это то свойство, которое подводит базис под НМР. НМР создаёт множители с существенно уменьшенными размерностями по сравнению с исходной матрицей. Например, если V является m × n матрицей, W является m × p матрицей, а H является p × n матрицей, то p может быть существенно меньше как m, так и n.

Вот пример на основе приложения анализа текста:

• Пусть входная матрица (разлагаемая матрица) будет V с 10000 строками и 500 столбцами, где слова соответствуют строкам, а документы соответствуют столбцам. То есть у нас есть 500 документов, проиндексированных 10000 словами. Отсюда следует, что вектор-столбец v в V представляет документ.
• Допустим, мы спрашиваем алгоритм найти 10 признаков в порядке образования матрицы признаков W с 10000 строк и 10 столбцами и матрицу коэффициентов H с 10 строками и 500 столбцами.
• Произведение W и H является матрицей с 10000 строками и 500 столбцами, те же размеры, что и входная матрица V и, если разложение работает, оно является приемлемым приближением входной матрицы V.
• Из описания умножения матриц выше следует, что каждый столбец в произведении матриц WH является линейной комбинацией 10 вектор-столбцов в матрице признаков W с коэффициентами, полученными из матрицы H.

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

Полезно думать о каждом признаке (вектор-столбце) в матрице признаков W как о прототипе документа, включающем набор слов, в котором каждая ячейка, соответствующая слову, определяет ранг слова в признаке — чем выше значение в ячейке слова, тем выше ранг слова в признаке. Столбец в матрице коэффициентов H представляет оригинальный документ со значениями ячеек, определяющих ранг документа для признака. Мы теперь можем восстановить документ (вектор-столбец) из нашей входной матрицы в виде линейной комбинации наших признаков (вектор-столбцов из W), где каждый признак берётся с весом, определяемым значением признака из вектор-столбца матрицы H.

НМР имеет внутреннее свойство кластеризации[13], т.е. он автоматически кластеризует столбцы входных данных ${\displaystyle \mathbf {V} =(v_{1},\cdots ,v_{n})}$. Это то свойство, которое востребовано большинством приложений НМР.

Более конкретно, приближение ${\displaystyle \mathbf {V} }$ посредством ${\displaystyle \mathbf {V} \simeq \mathbf {W} \mathbf {H} }$ достигается минимизацией функции ошибок

${\displaystyle \min _{W,H}||V-WH||_{F},}$ при условиях ${\displaystyle W\geqslant 0,H\geqslant 0.}$

Более того, вычисленная матрица ${\displaystyle H}$ даёт индикатор кластеров, т.е. если ${\displaystyle \mathbf {H} _{kj}>0}$, этот факт показывает, что входные данные ${\displaystyle v_{j}}$ принадлежат k-му кластеру. Вычисленная же матрица ${\displaystyle W}$ даёт центры кластеров, т.е. k-ый столбец задаёт центр k-го кластера. Это представление центров может быть существенно улучшено посредством выпуклого НМР.

Если ортогональность ${\displaystyle HH^{T}=E}$ не указана явно, ортогональность выполняется достаточно сильно и свойство кластеризации также имеет место. Кластеризация является главной целью большинства приложений НМР для data mining.

Если в качестве функции ошибки используется расстояние Кульбака — Лейблера, НМР идентично вероятностному латентно-семантическому анализу, популярному методу кластеризации документов[14].

Есть несколько способов, каким может быть найдены W и H. Мультипликативное правило обновления Ли и Сына[12] было популярно ввиду простоты имплементации.

Алгоритм:

Инициализация: W и H не отрицательны.

Обновляем значения в W и H путём вычисления (здесь ${\displaystyle n}$ — индекс итерации)

${\displaystyle H_{[i,j]}^{n+1}\leftarrow H_{[i,j]}^{n}{\frac {((W^{n})^{T}V)_{[i,j]}}{((W^{n})^{T}W^{n}H^{n})_{[i,j]}}}}$

и

${\displaystyle W_{[i,j]}^{n+1}\leftarrow W_{[i,j]}^{n}{\frac {(V(H^{n+1})^{T})_{[i,j]}}{(W^{n}H^{n+1}(H^{n+1})^{T})_{[i,j]}}}}$

Пока W и H не стабилизируются.

Заметим, что обновление осуществляется поэлементно, не умножением матриц.

Недавно был разработан другой алгоритм. Некоторые подходы базируются на чередуемом методе наименьших квадратов с неотрицательными весами (МНКНВ) — на каждом шаге такого алгоритма фиксируется сначала H, а W ищется с помощью МНКНВ, затем фиксируется W и теперь находится H аналогично. Процедуры, используемые для поиска W и H, могут быть теми же самыми [27] или различными, так как некоторые варианты НМР регуляризуют одну из матриц W или H[21]. Некоторые подходы включают, среди других, методы проецируемого градиентного спуска[27][28], метод активных ограничений[5][29], метод оптимального градиента[30] и блочный метод главного ведущего элемента[31][32].

Существующие в настоящее время алгоритмы субоптимальны, поскольку они гарантируют нахождение только локального, а не глобального минимума целевой функции. Доказанные оптимальные алгоритмы в ближайшем будущем вряд ли появятся, поскольку задача, как было показано, обобщает метод k-средних, который, как известно, NP-полон[13]. Однако, как и во многих других задачах анализа данных, знание локального минимума тоже полезно.

Графики относительной остаточной дисперсии (ООД, англ. Fractional residual variance, FRV) для МГК и последовательного НМР[4]. Для МГК теоретические значения получаются из остаточных собственных значений. Для сравнения, кривые ООД для МГК достигают плоского участка, где сигнал не воспринимается эффективно, в то время как кривые НМР ООД снижаются непрерывно, что говорит о лучшей возможности воспринимать сигнал. Кривые ООД для НМР также сходятся к более высоким уровням, чем МГК, что говорит о свойстве меньшей переподгонки метода НМР.

В статье Изучение частей объектов путём неотрицательных разложений матрицы Ли и Сын [39] предложили НМР главным образом для основанного на частях разложения изображений. В статье НМР сравнивается с векторным квантованием и методом главных компонент и показывается, что, хотя эти три техники могут быть записаны как разложения, они воспринимают различные ограничения, а потому дают различные результаты.

НМР как вероятностная графическая модель — видимые — видимые единицы (V) связаны со скрытыми единицами (H) посредством весов W, так что V порождена распределением вероятностей со средним ${\displaystyle \sum _{a}W_{ia}h_{a}}$[11].

Позднее было показано, что некоторые типы НМР являются экземплярами более общей вероятностной модели, называемой «мультиномиальной МГК»[40]. Если НМР получено путём минимизации расстояния Кульбака — Лейблера, это, фактически, эквивалентно другому экземпляру мультиномильной МГК, вероятностному латентно-семантическому анализу[41], настроенному с помощью оценки максимального правдоподобия. Этот метод обычно используется для анализа и кластеризации текстовых данных и он связан также с латентной классовой моделью.

НМР с целевой функцией метода наименьших квадратов эквивалентен ослабленной форме метода k-средних — матричный множитель W содержит центроиды кластеров, а H содержит индикаторы принадлежности кластерам [13][42]. Это даёт теоретическое обоснование для применения НМР для кластеризации данных. Однако k-средние не обеспечивают неотрицательности на центроидах, так что наиболее близкой аналогией является, фактически, «полу-НМР»[15].

НМР можно рассматривать как двухуровневую ориентированную графическую модель с одним уровнем наблюдаемых случайных переменных и одним уровнем скрытых случайных переменных[43].

НМР можно расширить с матриц до тензоров произвольного порядка[44][45][46]. Это расширение можно рассматривать как неотрицательный аналог, например, модели PARAFAC.

Другие расширения НМР включают совместное разложение нескольких матриц и тензоров, где некоторые сомножители одинаковы. Такие модели полезны для сочетания датчиков и обучению связям[47].

НМР является экземпляром неотрицательного квадратичного программирования (НКП), точно так же, как и метод опорных векторов (МОВ). Однако МОВ и НМР связаны более тесно, чем просто через НКП, что позволяет прямое применение алгоритмов, разработанных для решений любого из двух методов, к задачам обоих областей[48].

Разложение не единственно — матрица и её обратная могут быть использованы для преобразования двух матриц разложения посредством, например,[49],

${\displaystyle \mathbf {WH} =\mathbf {WBB} ^{-1}\mathbf {H} }$

Если две новые матрицы ${\displaystyle \mathbf {{\tilde {W}}=WB} }$ и ${\displaystyle \mathbf {\tilde {H}} =\mathbf {B} ^{-1}\mathbf {H} }$ неотрицательны, они образуют другую параметризацию разложения.

Неотрицательность ${\displaystyle \mathbf {\tilde {W}} }$ и ${\displaystyle \mathbf {\tilde {H}} }$ следует, если, по меньшей мере, B является неотрицательной мономиальной матрицей. В этом простом случае она соответствует просто масштабированию и перестановке.

Дополнительный контроль над неоднозначностью НМР приобретается ограничением заполненности матриц [50].

Текущие исследования (с 2010 года) по разложению неотрицательных матриц включают, но не ограничиваются следующими вопросами

1. Алгоритмические вопросы: поиск глобального минимума множителей и инициализация множителя[68].
2. Вопросы масштабирования: как разложить матрицы размером миллион-на-миллиард, которые возникают при анализе данных в сетях. См. статьи «Распределённое неотрицательное разложение матрицы (DNMF)»[69] и «Масшабируемое неотрицательное разложение матрицы (ScalableNMF)»[70].
3. Онлайн-обработка: как обновлять разложение, когда приходят новые данные, без полного вычисления с нуля[71].
4. Совместное разложение: разложение нескольких внутренне связанных матриц для многопозиционной кластеризации, см. CoNMF[72] и MultiNMF[73].
5. Задача Коэна и Ротблюма 1993 года: всегда ли рациональная матрица имеет НМР минимальной внутренней размерности, множители которой также рациональны. Недавно на этот вопрос был получен отрицательный ответ[74].

• Полилинейная алгебра
• Полилинейное обучение подпространств
• Тензор