Неотрицательное матричное разложение (НМР), а также неотрицательное приближение матрицы, это группа алгоритмов в и линейной алгебре, в которых матрица разлагается на (обычно) две матрицы и , со свойством, что все три матрицы имеют неотрицательные элементы. Эта неотрицательность делает получившиеся матрицы более простыми для исследования. В приложениях, таких как обработка спектрограмм аудиосигнала или данных мускульной активности, неотрицательность свойственна рассматриваемым данным. Поскольку задача в общем случае неразрешима, её обычно численно аппроксимируют.
НМР нашёл применение в таких областях как астрономия, компьютерное зрение, кластеризация документов, хемометрика, , рекомендательные системы, и биоинформатика.
История В хемометрике неотрицательное матричное разложение имеет долгую историю под названием «метод автомодельного разрешения кривых» В этом контексте вектора в правой матрице являются непрерывными кривыми, а не дискретными векторами. Ранние работы по неотрицательному матричному разложению были проведены финской группой исследователей в середине 1990-х под названием положительное разложение матрицы. Метод стал более широко известен как неотрицательное матричное разложение, после того как Ли и Сын исследовали свойства алгоритма и опубликовали несколько простых полезных алгоритмов для двух видов разложения.
Предпосылки
Пусть матрица является произведением матриц и ,
Умножение матриц может быть имплементировано через вычисление вектора-столбца матрицы как линейной комбинации векторов-столбцов в , используя коэффициенты из столбцов матрицы . То есть каждый столбец матрицы может быть вычислен следующим образом:
где является -ым вектор-столбцом произведения матрицы , а является -ым вектор-столбцом матрицы .
При умножении матриц размерности матриц-сомножителей могут быть существенно меньше, чем размерность произведения матриц, и это то свойство, которое подводит базис под НМР. НМР создаёт множители с существенно уменьшенными размерностями по сравнению с исходной матрицей. Например, если является матрицей, является матрицей, а является матрицей, то может быть существенно меньше как , так и .
Вот пример на основе приложения анализа текста: Пусть входная матрица (разлагаемая матрица) будет с 10000 строками и 500 столбцами, где слова соответствуют строкам, а документы соответствуют столбцам. То есть у нас есть 500 документов, проиндексированных 10000 словами. Отсюда следует, что вектор-столбец в представляет документ. Допустим, мы спрашиваем алгоритм найти 10 признаков в порядке образования матрицы признаков с 10000 строк и 10 столбцами и матрицу коэффициентов с 10 строками и 500 столбцами. Произведение и является матрицей с 10000 строками и 500 столбцами, те же размеры, что и входная матрица и, если разложение работает, оно является приемлемым приближением входной матрицы . Из описания умножения матриц выше следует, что каждый столбец в произведении матриц является линейной комбинацией 10 вектор-столбцов в матрице признаков с коэффициентами, полученными из матрицы .
Это последнее свойство является базисом НМР, поскольку мы можем рассматривать каждый оригинальный документ в нашем примере как построенный из небольшого набора скрытых признаков. НМР создаёт эти признаки.
Полезно думать о каждом признаке (вектор-столбце) в матрице признаков как о прототипе документа, включающем набор слов, в котором каждая ячейка, соответствующая слову, определяет ранг слова в признаке — чем выше значение в ячейке слова, тем выше ранг слова в признаке. Столбец в матрице коэффициентов представляет оригинальный документ со значениями ячеек, определяющих ранг документа для признака. Мы теперь можем восстановить документ (вектор-столбец) из нашей входной матрицы в виде линейной комбинации наших признаков (вектор-столбцов из ), где каждый признак берётся с весом, определяемым значением признака из вектор-столбца матрицы .
Свойство кластеризации НМР имеет внутреннее свойство кластеризации, т.е. он автоматически кластеризует столбцы входных данных . Это то свойство, которое востребовано большинством приложений НМР.
Более конкретно, приближение посредством достигается минимизацией функции ошибок
при условиях
Более того, вычисленная матрица даёт индикатор кластеров, т.е. если , этот факт показывает, что входные данные принадлежат k-му кластеру. Вычисленная же матрица даёт центры кластеров, т.е. k-ый столбец задаёт центр k-го кластера. Это представление центров может быть существенно улучшено посредством выпуклого НМР.
Если ортогональность не указана явно, ортогональность выполняется достаточно сильно и свойство кластеризации также имеет место. Кластеризация является главной целью большинства приложений НМР для data mining.
Если в качестве функции ошибки используется расстояние Кульбака — Лейблера, НМР идентично вероятностному латентно-семантическому анализу, популярному методу кластеризации документов.
Типы
Приближённое неотрицательное разложение матрицы Обычно число столбцов матрицы и число строк матрицы в НМР выбирается так, что произведение становится приближением к . Полное разложение матрицы тогда состоит из двух неотрицательных матриц и , а также из остаточной матрицы , такой, что . Элементы остаточной матрицы могут быть и положительными, и отрицательными.
Если и меньше, чем , их проще запомнить и с ними легче работать. Другая причина разложения на меньшие матрицы и заключается в том, что если можно приблизительно представить элементы матрицы существенно меньшим количеством данных, то можем заключить о некоторой неявной структуре данных.
Выпуклое неотрицательное разложение матрицы
В стандартном НМР множитель ，т.е. матрица может быть любой в этом пространстве. Выпуклый НМР ограничивает столбцы матрицы до выпуклых комбинаций входных векторов . Это существенно улучшает качество представления данных матрицы . Более того, множитель становится более разрежен и ортогонален.
Разложение неотрицательного ранга В случае, когда матрицы равен обычному рангу, называется разложением неотрицательного ранга (НРР, , NRF). Известно, что задача поиска НРР матрицы , если такой существует, NP-трудна.
Различные функции цены и регуляризация
Существуют различные виды неотрицательного разложения матрицы. Различные виды возникают от использования различных функций цены для измерения расхождения между и и возможной регуляризации матрицы и/или матрицы .
Две простые функции расхождения, которые изучали Ли и Сын, были квадратичное отклонение (или норма Фробениуса) и расширение понятия расстояния Кульбака — Лейблера на положительные матрицы (изначально расстояние Кульбака — Лейблера было определено для вероятностных распределений). Каждая функция расхождения приводит к своему алгоритму НМР, который обычно минимизирует расхождение с помощью итеративных правил обновления.
Задача разложения в версии функции квадратичной ошибки для НМР может быть сформулирована следующим образом: Если дана матрица , нужно найти неотрицательные матрицы W и H, которые минимизируют функцию
Другой вид НМР для изображений базируется на норме, определяемой полной вариацией.
Если L1 регуляризация (сходная с , ) добавлена к НМР с целевой функцией, равной среднему квадрату ошибки, получающаяся задача может быть названа неотрицательным разреженным кодированием ввиду похожести на задачу разреженного кодирования, хотя она может упоминаться и под названием НМР.
Онлайн НМР Многие стандартные НМР алгоритмы анализируют все данные вместе. Т.е. вся матрица доступна с самого начала. Это может оказаться неприемлемым для приложений, в которых данные занимают слишком много памяти, чтобы поместить их все в одновременно, или где данные поступают в виде потока. Такая ситуация характерна для коллаборативной фильтрации в рекомендательных системах, где может имеется много пользователей и много объектов для рекомендации, а пересчитывать всё было бы неэффективно, когда в систему добавляется пользователь или объект. Целевая функция для оптимизации в этих случаях может быть, а может и не быть такой же, как в стандартном НМР, но алгоритмы должны отличаться.
Алгоритмы Есть несколько способов, каким может быть найдены и . Ли и Сына было популярно ввиду простоты имплементации.
Алгоритм: Инициализация: и не отрицательны. Обновляем значения в и путём вычисления (здесь — индекс итерации)
и
Пока и не стабилизируются. Заметим, что обновление осуществляется поэлементно, не умножением матриц.
Недавно был разработан другой алгоритм. Некоторые подходы базируются на чередуемом (МНКНВ) — на каждом шаге такого алгоритма фиксируется сначала , а ищется с помощью МНКНВ, затем фиксируется и теперь находится аналогично. Процедуры, используемые для поиска и , могут быть теми же самыми или различными, так как некоторые варианты НМР регуляризуют одну из матриц или . Некоторые подходы включают, среди других, методы проецируемого градиентного спуска, , метод оптимального градиента и блочный метод главного ведущего элемента.
Существующие в настоящее время алгоритмы субоптимальны, поскольку они гарантируют нахождение только локального, а не глобального минимума целевой функции. Доказанные оптимальные алгоритмы в ближайшем будущем вряд ли появятся, поскольку задача, как было показано, обобщает метод k-средних, который, как известно, NP-полон. Однако, как и во многих других задачах анализа данных, знание локального минимума тоже полезно.
Последовательный НМР
Последовательное построение компонент НМР ( и ) было первоначально использовано для связывания НМР с методом главных компонент (МГК) в астрономии. Вклады компонент МГК ранжируются по величине их соответствующих собственных значений. Для НМР его компоненты можно ранжировать эмпирически, если они строятся один за другим (последовательно), т.е. строим -ую компоненту с уже построенными первыми компонентами.
Вклады последовательных компонент НМР можно сравнивать по теореме Карунена — Лоэва с помощью графика собственных значений. Типичный выбор числа компонент в МГК базируется на точке «изгиба», тогда существование плоского участка свидетельствует, что МГК не воспринимает данные эффективно, а если существует неожиданное падение, это говорит о случайном шуме и попадании в режим чрезмерной подгонки. Для последовательного НМР график собственных значений приближается графиком относительной остаточной дисперсии, где кривая убывает непрерывно и сходится к большему значению, чем МГК, что говорит о меньшей чрезмерной подгонке последовательного НМР.
Точный НМР Точные решения для вариантов НМР могут быть проверены (за полиномиальное время), если выполняются дополнительные ограничения для матрицы . Алгоритм полиномиального времени решения неотрицательного рангового разложения, когда матрица содержит мономиальную подматрицу с рангом, равным рангу матрицы дали Кэмпбелл и Пул в 1981. Калофольяс и Галлопоулус (2012) решили симметричный аналог этой задачи, где является симметричной и содержит диагональную главную подматрицу ранга r. Их алгоритм работает за время в плотном случае. Арора с группой исследователей предложили алгоритм полиномиального времени для точного НМР, который работает в случае, когда один из множителей W удовлетворяет условию отделимости.
Связь с другими техниками
В статье Изучение частей объектов путём неотрицательных разложений матрицы Ли и Сын предложили НМР главным образом для основанного на частях разложения изображений. В статье НМР сравнивается с векторным квантованием и методом главных компонент и показывается, что, хотя эти три техники могут быть записаны как разложения, они воспринимают различные ограничения, а потому дают различные результаты.
Позднее было показано, что некоторые типы НМР являются экземплярами более общей вероятностной модели, называемой «мультиномиальной МГК». Если НМР получено путём минимизации расстояния Кульбака — Лейблера, это, фактически, эквивалентно другому экземпляру мультиномильной МГК, вероятностному латентно-семантическому анализу, настроенному с помощью оценки максимального правдоподобия.