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

Неотрицательное матричное разложение (НМР), а также неотрицательное приближение матрицы^[1][2], это группа алгоритмов в мультивариантном анализе^[en] и линейной алгебре, в которых матрица V разлагается на (обычно) две матрицы W и H, со свойством, что все три матрицы имеют неотрицательные элементы. Эта неотрицательность делает получившиеся матрицы более простыми для исследования. В приложениях, таких как обработка спектрограмм аудиосигнала или данных мускульной активности, неотрицательность свойственна рассматриваемым данным. Поскольку задача в общем случае неразрешима, её обычно численно аппроксимируют.

НМР нашёл применение в таких областях как астрономия^[3][4], компьютерное зрение, кластеризация документов^[1], хемометрика, обработка аудиосигнала^[en], рекомендательные системы,^[5][6] и биоинформатика^[7].

История[править | править код]

В хемометрике неотрицательное матричное разложение имеет долгую историю под названием «метод автомодельного разрешения кривых»^[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 в НМР выбирается так, что произведение WH становится приближением к V. Полное разложение матрицы V тогда состоит из двух неотрицательных матриц W и H, а также из остаточной матрицы U, такой, что V=WH + U. Элементы остаточной матрицы могут быть и положительными, и отрицательными.

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

Выпуклое неотрицательное разложение матрицы[править | править код]

В стандартном НМР множитель ${\displaystyle \mathbf {W} \in \mathbb {R} _{+}^{m\times k}}$，т.е. матрица W может быть любой в этом пространстве. Выпуклый НМР^[15] ограничивает столбцы матрицы W до выпуклых комбинаций входных векторов ${\displaystyle (v_{1},\cdots ,v_{n})}$. Это существенно улучшает качество представления данных матрицы W. Более того, множитель H становится более разрежен и ортогонален.

Разложение неотрицательного ранга[править | править код]

В случае, когда неотрицательный ранг^[en] матрицы V равен обычному рангу, V=WH называется разложением неотрицательного ранга (НРР, англ. Nonnegative rank factorization, NRF)^[16][17][18]. Известно, что задача поиска НРР матрицы V, если такой существует, NP-трудна^[19].

Различные функции цены и регуляризация[править | править код]

Существуют различные виды неотрицательного разложения матрицы. Различные виды возникают от использования различных функций цены для измерения расхождения между V и WH и возможной регуляризации матрицы W и/или матрицы H^[1].

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

Задача разложения в версии функции квадратичной ошибки для НМР может быть сформулирована следующим образом: Если дана матрица ${\displaystyle \mathbf {V} }$, нужно найти неотрицательные матрицы W и H, которые минимизируют функцию

${\displaystyle F(\mathbf {W} ,\mathbf {H} )=\|\mathbf {V} -\mathbf {WH} \|_{F}^{2}}$

Другой вид НМР для изображений базируется на норме, определяемой полной вариацией^[20].

Если L1 регуляризация (сходная с Lasso^[en], англ. Least Absolute Shrinkage and Selection Operator) добавлена к НМР с целевой функцией, равной среднему квадрату ошибки, получающаяся задача может быть названа неотрицательным разреженным кодированием ввиду похожести на задачу разреженного кодирования^[21][22], хотя она может упоминаться и под названием НМР^[23].

Онлайн НМР[править | править код]

Многие стандартные НМР алгоритмы анализируют все данные вместе. Т.е. вся матрица доступна с самого начала. Это может оказаться неприемлемым для приложений, в которых данные занимают слишком много памяти, чтобы поместить их все в одновременно, или где данные поступают в виде потока. Такая ситуация характерна для коллаборативной фильтрации в рекомендательных системах, где может имеется много пользователей и много объектов для рекомендации, а пересчитывать всё было бы неэффективно, когда в систему добавляется пользователь или объект. Целевая функция для оптимизации в этих случаях может быть, а может и не быть такой же, как в стандартном НМР, но алгоритмы должны отличаться^[24][25][26].

Алгоритмы[править | править код]

Есть несколько способов, каким может быть найдены W и H. Мультипликативное правило обновления^[en] Ли и Сына^[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 не стабилизируются.

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

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

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

Последовательный НМР[править | править код]

Последовательное построение компонент НМР (W и H) было первоначально использовано для связывания НМР с методом главных компонент (МГК) в астрономии^[33]. Вклады компонент МГК ранжируются по величине их соответствующих собственных значений. Для НМР его компоненты можно ранжировать эмпирически, если они строятся один за другим (последовательно), т.е. строим ${\displaystyle (n+1)}$-ую компоненту с уже построенными первыми ${\displaystyle n}$ компонентами.

Вклады последовательных компонент НМР можно сравнивать по теореме Карунена — Лоэва с помощью графика собственных значений. Типичный выбор числа компонент в МГК базируется на точке «изгиба», тогда существование плоского участка свидетельствует, что МГК не воспринимает данные эффективно, а если существует неожиданное падение, это говорит о случайном шуме и попадании в режим чрезмерной подгонки^[34][35]. Для последовательного НМР график собственных значений приближается графиком относительной остаточной дисперсии, где кривая убывает непрерывно и сходится к большему значению, чем МГК^[4], что говорит о меньшей чрезмерной подгонке последовательного НМР.

Точный НМР[править | править код]

Точные решения для вариантов НМР могут быть проверены (за полиномиальное время), если выполняются дополнительные ограничения для матрицы V. Алгоритм полиномиального времени решения неотрицательного рангового разложения, когда матрица V содержит мономиальную подматрицу с рангом, равным рангу матрицы дали Кэмпбелл и Пул в 1981^[36]. Калофольяс и Галлопоулус (2012)^[37] решили симметричный аналог этой задачи, где V является симметричной и содержит диагональную главную подматрицу ранга r. Их алгоритм работает за время ${\displaystyle O(rm^{2})}$ в плотном случае. Арора с группой исследователей предложили алгоритм полиномиального времени для точного НМР, который работает в случае, когда один из множителей W удовлетворяет условию отделимости^[38].

Связь с другими техниками[править | править код]

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

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

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

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

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

Другие расширения НМР включают совместное разложение нескольких матриц и тензоров, где некоторые сомножители одинаковы. Такие модели полезны для сочетания датчиков и обучению связям^[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 является неотрицательной мономиальной матрицей^[en]. В этом простом случае она соответствует просто масштабированию и перестановке.

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

Приложения[править | править код]

Астрономия[править | править код]

В астрономии НМР является многообещающим методом для понижения размерности в смысле, что астрофизические сигналы являются неорицательными. НМР применяется для спектроскопических наблюдений ^[3] и прямых наблюдений^[4] как метод изучения общих свойств астрономического объекта и постобработки астрономических наблюдений. Продвижение в спектроскопических наблюдениях исследователей Блэнтона и Роуиза (2007)^[3] связано с принятием во внимание неопределённости астрономических наблюдений, что позднее улучшил Зу (2016) ^[33], который рассматривал также отсутствие данных и использовал параллельные вычисления. Их методы затем приспособили Рен и др. (2018) ^[4] для прямого поля наблюдения как один из методов обнаружения экзопланет, особенно для прямого наблюдения околозвёздных дисков.

Рен и др. (2018)^[4] смогли показать стабильность компонент НМР, когда они строятся последовательно (т.е. одна за другой), что обеспечивает линейность процесса моделирования НМР. Свойство линейности использовалось для отделения света звезды от рассеянного света экзопланет и околозвёздных дисков.

При прямом наблюдении для выделения тусклых экзопланет и околозвёздных дисков от окружающего звезду яркого света, который имеет типичную контрастность от 10⁵ до 10¹⁰, были приспособлены различные статистические методы ^[51][52][34], однако выделение света от экзопланет или околозвёздных дисков обычно страдает переподгонкой, так что для обнаружения истинного течения должно быть применено последующее моделирование^[53][35]. Моделирование на настоящее время оптимизировано для точечных источников ^[35], но не для структур с нерегулярными формами, такими как s околозвёздные диски. В этой ситуации НМР является отличным методом, менее страдающим от переподгонки в смысле неотрицательности и разреженности коэффициентов моделирования НМР, поэтому моделирование может быть осуществлено с несколькими масштабирующими множителями^[4] вместо вычислительно ёмкой переобработки данных на полученных моделях.

Интеллектуальный анализ текста[править | править код]

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

Одно из приложений использует иерархический НМР на небольшом подмножестве научных абстракций из PubMed^[54]. Другая группа исследователей сгруппировала множество email компании Enron ^[55] (65033 сообщений и 91133 объектов) в 50 кластеров^[56]. НМР применяется также для данных о цитировании, с одним примером кластеризации статей английской Википедии и научных журналов, основываясь на научных цитатах в английской Википедии^[57].

Арора и др. предложили алгоритмы полиномиального времени для обучения тематических моделей с помощью НМР. Алгоритм предполагает, что тематическая матрица удовлетворяет условию отделимости, что часто выполняется в таких условиях^[38].

Спектральный анализ данных[править | править код]

НМР используется также в анализе спектральных данных. Одно из таких применений — классификация межпланетных объектов и обломков^[58].

Предсказание масштабируемого сетевого расстояния[править | править код]

НМР используется в предсказании масштабируемого сетевого расстояния в интернете (время оборота пакета). Для сети с ${\displaystyle N}$ хостами с помощью НМР расстояния всех ${\displaystyle N^{2}}$ соединений от точки до точки могут быть предсказаны после проведения лишь ${\displaystyle O(N)}$ измерений. Этот вид метода был впервые предложен в «Сервисе оценки интернет-расстояния» (англ. Internet Distance Estimation Service, IDES)^[59]. Впоследствии, как полностью децентрализованный подход, была предложена сетевая координатная система Phoenix (англ. Phoenix network coordinate system)^[60]. Она достигла лучшей предсказуемости путём введения концепции веса.

Удаление нестационарного шума из разговора[править | править код]

Удаление шума из разговора является давней проблемой в обработке аудиосигнала^[en]. Есть большое число алгоритмов удаления шума, если шум стационарен. Например, фильтр Винера пригоден для аддитивного гауссова шума. Однако, если шум не стационарен, классические алгоритмы удаления шума обычно имеют плохую производительность, поскольку статистическую информацию о нестационарном шуме трудно оценить. Шмидт и др.^[61] использовали НМР для удаления нестационарного шума в разговоре, что полностью отличается от классических статистических подходов. Ключевой идеей является то, что чистый сигнал может быть представлен словарём разговора, а нестационарный шум представлен быть не может. Аналогично, нестационарный шум может быть представлен словарём шумов, а разговор не может.

Алгоритм для удаления шума с помощью НМР работает следующим образом. Необходимо обучить офлайн два словаря, один для разговора, другой для шума. Как только подаётся разговор с шумом, сначала вычисляем величину оконного преобразования Фурье. Затем разделяем его на две части с помощью НМР, одна часть может быть представлена словарём разговора, а другая часть может быть представлена словарём шума. На третьем шаге часть, представленная словарём разговора, оценивается как чистый разговор.

Биоинформатика[править | править код]

НМР успешно применяется в биоинформатике для кластеризации данных экспрессии генов и метилирования ДНК и поиска генов, наиболее представляющих кластеры^{[22][62][63][64]}. В анализе мутаций рака это используется для выделения общих механизмов возникновения мутации, которые случаются во многих случаях рака и, возможно, имеют различные причины ^[65].

Радионуклидная визуализация[править | править код]

НМР, упоминаемый в этой области как факторный анализ, используется здесь с 1980-ых годов^[66] для анализа последовательности изображений в ОФЭКТ и ПЭТ. Неоднозначность НМР решалась наложением ограничения разреженности^[67].

Текущие исследования[править | править код]

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

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

См. также[править | править код]

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

Примечания[править | править код]

Литература[править | править код]

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