Неотрицательное матричное разложение
Неотрицательное матричное разложение (НМР), а также неотрицательное приближение матрицы[1][2], это группа алгоритмов в мультивариантном анализе[en] и линейной алгебре, в которых матрица V разлагается на (обычно) две матрицы W и H, со свойством, что все три матрицы имеют неотрицательные элементы. Эта неотрицательность делает получившиеся матрицы более простыми для исследования. В приложениях, таких как обработка спектрограмм аудиосигнала или данных мускульной активности, неотрицательность свойственна рассматриваемым данным. Поскольку задача в общем случае неразрешима, её обычно численно аппроксимируют.
НМР нашёл применение в таких областях как астрономия[3][4], компьютерное зрение, кластеризация документов[1], хемометрика, обработка аудиосигнала[en], рекомендательные системы,[5][6] и биоинформатика[7].
ИсторияПравить
В хемометрике неотрицательное матричное разложение имеет долгую историю под названием «метод автомодельного разрешения кривых»[8] В этом контексте вектора в правой матрице являются непрерывными кривыми, а не дискретными векторами. Ранние работы по неотрицательному матричному разложению были проведены финской группой исследователей в середине 1990-х под названием положительное разложение матрицы[9][10]. Метод стал более широко известен как неотрицательное матричное разложение, после того как Ли и Сын исследовали свойства алгоритма и опубликовали несколько простых полезных алгоритмов для двух видов разложения[11][12].
ПредпосылкиПравить
Пусть матрица V является произведением матриц W и H,
Умножение матриц может быть имплементировано через вычисление вектора-столбца матрицы V как линейной комбинации векторов-столбцов в W, используя коэффициенты из столбцов матрицы H. То есть каждый столбец матрицы V может быть вычислен следующим образом:
где vi является i-ым вектор-столбцом произведения матрицы V, а hi является 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], т.е. он автоматически кластеризует столбцы входных данных . Это то свойство, которое востребовано большинством приложений НМР.
Более конкретно, приближение посредством достигается минимизацией функции ошибок
при условиях
Более того, вычисленная матрица даёт индикатор кластеров, т.е. если , этот факт показывает, что входные данные принадлежат k-му кластеру. Вычисленная же матрица даёт центры кластеров, т.е. k-ый столбец задаёт центр k-го кластера. Это представление центров может быть существенно улучшено посредством выпуклого НМР.
Если ортогональность не указана явно, ортогональность выполняется достаточно сильно и свойство кластеризации также имеет место. Кластеризация является главной целью большинства приложений НМР для data mining.
Если в качестве функции ошибки используется расстояние Кульбака — Лейблера, НМР идентично вероятностному латентно-семантическому анализу, популярному методу кластеризации документов[14].
ТипыПравить
Приближённое неотрицательное разложение матрицыПравить
Обычно число столбцов матрицы W и число строк матрицы H в НМР выбирается так, что произведение WH становится приближением к V. Полное разложение матрицы V тогда состоит из двух неотрицательных матриц W и H, а также из остаточной матрицы U, такой, что V=WH + U. Элементы остаточной матрицы могут быть и положительными, и отрицательными.
Если W и H меньше, чем V, их проще запомнить и с ними легче работать. Другая причина разложения V на меньшие матрицы W и H заключается в том, что если можно приблизительно представить элементы матрицы V существенно меньшим количеством данных, то можем заключить о некоторой неявной структуре данных.
Выпуклое неотрицательное разложение матрицыПравить
В стандартном НМР множитель ,т.е. матрица W может быть любой в этом пространстве. Выпуклый НМР[15] ограничивает столбцы матрицы W до выпуклых комбинаций входных векторов . Это существенно улучшает качество представления данных матрицы W. Более того, множитель H становится более разрежен и ортогонален.
Разложение неотрицательного рангаПравить
В случае, когда неотрицательный ранг[en] матрицы V равен обычному рангу, V=WH называется разложением неотрицательного ранга (НРР, англ. Nonnegative rank factorization, NRF)[16][17][18]. Известно, что задача поиска НРР матрицы V, если такой существует, NP-трудна[19].
Различные функции цены и регуляризацияПравить
Существуют различные виды неотрицательного разложения матрицы. Различные виды возникают от использования различных функций цены для измерения расхождения между V и WH и возможной регуляризации матрицы W и/или матрицы H[1].
Две простые функции расхождения, которые изучали Ли и Сын, были квадратичное отклонение (или норма Фробениуса) и расширение понятия расстояния Кульбака — Лейблера на положительные матрицы (изначально расстояние Кульбака — Лейблера было определено для вероятностных распределений). Каждая функция расхождения приводит к своему алгоритму НМР, который обычно минимизирует расхождение с помощью итеративных правил обновления.
Задача разложения в версии функции квадратичной ошибки для НМР может быть сформулирована следующим образом: Если дана матрица , нужно найти неотрицательные матрицы W и H, которые минимизируют функцию
Другой вид НМР для изображений базируется на норме, определяемой полной вариацией[20].
Если L1 регуляризация (сходная с Lasso[en], англ. Least Absolute Shrinkage and Selection Operator) добавлена к НМР с целевой функцией, равной среднему квадрату ошибки, получающаяся задача может быть названа неотрицательным разреженным кодированием ввиду похожести на задачу разреженного кодирования[21][22], хотя она может упоминаться и под названием НМР[23].
Онлайн НМРПравить
Многие стандартные НМР алгоритмы анализируют все данные вместе. Т.е. вся матрица доступна с самого начала. Это может оказаться неприемлемым для приложений, в которых данные занимают слишком много памяти, чтобы поместить их все в одновременно, или где данные поступают в виде потока. Такая ситуация характерна для коллаборативной фильтрации в рекомендательных системах, где может имеется много пользователей и много объектов для рекомендации, а пересчитывать всё было бы неэффективно, когда в систему добавляется пользователь или объект. Целевая функция для оптимизации в этих случаях может быть, а может и не быть такой же, как в стандартном НМР, но алгоритмы должны отличаться[24][25][26].
АлгоритмыПравить
Есть несколько способов, каким может быть найдены W и H. Мультипликативное правило обновления[en] Ли и Сына[12] было популярно ввиду простоты имплементации.
Алгоритм:
- Инициализация: W и H не отрицательны.
- Обновляем значения в W и H путём вычисления (здесь — индекс итерации)
- и
- Пока 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]. Вклады компонент МГК ранжируются по величине их соответствующих собственных значений. Для НМР его компоненты можно ранжировать эмпирически, если они строятся один за другим (последовательно), т.е. строим -ую компоненту с уже построенными первыми компонентами.
Вклады последовательных компонент НМР можно сравнивать по теореме Карунена — Лоэва с помощью графика собственных значений. Типичный выбор числа компонент в МГК базируется на точке «изгиба», тогда существование плоского участка свидетельствует, что МГК не воспринимает данные эффективно, а если существует неожиданное падение, это говорит о случайном шуме и попадании в режим чрезмерной подгонки[34][35]. Для последовательного НМР график собственных значений приближается графиком относительной остаточной дисперсии, где кривая убывает непрерывно и сходится к большему значению, чем МГК[4], что говорит о меньшей чрезмерной подгонке последовательного НМР.
Точный НМРПравить
Точные решения для вариантов НМР могут быть проверены (за полиномиальное время), если выполняются дополнительные ограничения для матрицы V. Алгоритм полиномиального времени решения неотрицательного рангового разложения, когда матрица V содержит мономиальную подматрицу с рангом, равным рангу матрицы дали Кэмпбелл и Пул в 1981[36]. Калофольяс и Галлопоулус (2012)[37] решили симметричный аналог этой задачи, где V является симметричной и содержит диагональную главную подматрицу ранга r. Их алгоритм работает за время в плотном случае. Арора с группой исследователей предложили алгоритм полиномиального времени для точного НМР, который работает в случае, когда один из множителей W удовлетворяет условию отделимости[38].
Связь с другими техникамиПравить
В статье Изучение частей объектов путём неотрицательных разложений матрицы Ли и Сын [39] предложили НМР главным образом для основанного на частях разложения изображений. В статье НМР сравнивается с векторным квантованием и методом главных компонент и показывается, что, хотя эти три техники могут быть записаны как разложения, они воспринимают различные ограничения, а потому дают различные результаты.
Позднее было показано, что некоторые типы НМР являются экземплярами более общей вероятностной модели, называемой «мультиномиальной МГК»[40]. Если НМР получено путём минимизации расстояния Кульбака — Лейблера, это, фактически, эквивалентно другому экземпляру мультиномильной МГК, вероятностному латентно-семантическому анализу[41], настроенному с помощью оценки максимального правдоподобия. Этот метод обычно используется для анализа и кластеризации текстовых данных и он связан также с латентной классовой моделью[en].
НМР с целевой функцией метода наименьших квадратов эквивалентен ослабленной форме метода k-средних — матричный множитель W содержит центроиды кластеров, а H содержит индикаторы принадлежности кластерам [13][42]. Это даёт теоретическое обоснование для применения НМР для кластеризации данных. Однако k-средние не обеспечивают неотрицательности на центроидах, так что наиболее близкой аналогией является, фактически, «полу-НМР»[15].
НМР можно рассматривать как двухуровневую ориентированную графическую модель с одним уровнем наблюдаемых случайных переменных и одним уровнем скрытых случайных переменных[43].
НМР можно расширить с матриц до тензоров произвольного порядка[44][45][46]. Это расширение можно рассматривать как неотрицательный аналог, например, модели PARAFAC[en].
Другие расширения НМР включают совместное разложение нескольких матриц и тензоров, где некоторые сомножители одинаковы. Такие модели полезны для сочетания датчиков и обучению связям[47].
НМР является экземпляром неотрицательного квадратичного программирования (НКП), точно так же, как и метод опорных векторов (МОВ). Однако МОВ и НМР связаны более тесно, чем просто через НКП, что позволяет прямое применение алгоритмов, разработанных для решений любого из двух методов, к задачам обоих областей[48].
ЕдинственностьПравить
Разложение не единственно — матрица и её обратная могут быть использованы для преобразования двух матриц разложения посредством, например,[49],
Если две новые матрицы и неотрицательны, они образуют другую параметризацию разложения.
Неотрицательность и следует, если, по меньшей мере, 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].
Предсказание масштабируемого сетевого расстоянияПравить
НМР используется в предсказании масштабируемого сетевого расстояния в интернете (время оборота пакета). Для сети с хостами с помощью НМР расстояния всех соединений от точки до точки могут быть предсказаны после проведения лишь измерений. Этот вид метода был впервые предложен в «Сервисе оценки интернет-расстояния» (англ. Internet Distance Estimation Service, IDES)[59]. Впоследствии, как полностью децентрализованный подход, была предложена сетевая координатная система Phoenix (англ. Phoenix network coordinate system)[60]. Она достигла лучшей предсказуемости путём введения концепции веса.
Удаление нестационарного шума из разговораПравить
Удаление шума из разговора является давней проблемой в обработке аудиосигнала[en]. Есть большое число алгоритмов удаления шума, если шум стационарен. Например, фильтр Винера пригоден для аддитивного гауссова шума. Однако, если шум не стационарен, классические алгоритмы удаления шума обычно имеют плохую производительность, поскольку статистическую информацию о нестационарном шуме трудно оценить. Шмидт и др.[61] использовали НМР для удаления нестационарного шума в разговоре, что полностью отличается от классических статистических подходов. Ключевой идеей является то, что чистый сигнал может быть представлен словарём разговора, а нестационарный шум представлен быть не может. Аналогично, нестационарный шум может быть представлен словарём шумов, а разговор не может.
Алгоритм для удаления шума с помощью НМР работает следующим образом. Необходимо обучить офлайн два словаря, один для разговора, другой для шума. Как только подаётся разговор с шумом, сначала вычисляем величину оконного преобразования Фурье. Затем разделяем его на две части с помощью НМР, одна часть может быть представлена словарём разговора, а другая часть может быть представлена словарём шума. На третьем шаге часть, представленная словарём разговора, оценивается как чистый разговор.
БиоинформатикаПравить
НМР успешно применяется в биоинформатике для кластеризации данных экспрессии генов и метилирования ДНК и поиска генов, наиболее представляющих кластеры[22][62][63][64]. В анализе мутаций рака это используется для выделения общих механизмов возникновения мутации, которые случаются во многих случаях рака и, возможно, имеют различные причины [65].
Радионуклидная визуализацияПравить
НМР, упоминаемый в этой области как факторный анализ, используется здесь с 1980-ых годов[66] для анализа последовательности изображений в ОФЭКТ и ПЭТ. Неоднозначность НМР решалась наложением ограничения разреженности[67].
Текущие исследованияПравить
Текущие исследования (с 2010 года) по разложению неотрицательных матриц включают, но не ограничиваются следующими вопросами
- Алгоритмические вопросы: поиск глобального минимума множителей и инициализация множителя[68].
- Вопросы масштабирования: как разложить матрицы размером миллион-на-миллиард, которые возникают при анализе данных в сетях. См. статьи «Распределённое неотрицательное разложение матрицы (DNMF)»[69] и «Масшабируемое неотрицательное разложение матрицы (ScalableNMF)»[70].
- Онлайн-обработка: как обновлять разложение, когда приходят новые данные, без полного вычисления с нуля[71].
- Совместное разложение: разложение нескольких внутренне связанных матриц для многопозиционной кластеризации, см. CoNMF[72] и MultiNMF[73].
- Задача Коэна и Ротблюма 1993 года: всегда ли рациональная матрица имеет НМР минимальной внутренней размерности, множители которой также рациональны. Недавно на этот вопрос был получен отрицательный ответ[74].
См. такжеПравить
ПримечанияПравить
- ↑ 1 2 3 Dhillon, Sra, 2005.
- ↑ Tandon, Sra, 2010.
- ↑ 1 2 3 Blanton, Roweis, 2007, с. 734-754.
- ↑ 1 2 3 4 5 6 7 Ren, Pueyo, Zhu, Duchêne, 2018, с. 104.
- ↑ 1 2 Gemulla, Nijkamp, Haas, Sismanis, 2011, с. 69–77.
- ↑ Bao, 2014.
- ↑ Murrell, 2011, с. e28898.
- ↑ Lawton, Sylvestre, 1971, с. 617+.
- ↑ Paatero, Tapper, 1994, с. 111–126.
- ↑ Anttila, Paatero, Tapper, Järvinen, 1995, с. 1705-1718.
- ↑ 1 2 Lee, Seung, 1999, с. 788-791.
- ↑ 1 2 Lee, Seung, 2001, с. 556-562.
- ↑ 1 2 3 Ding, He, Simon, 2005, с. 606-610.
- ↑ Ding, Li, Peng, 2008, с. 3913-3927.
- ↑ 1 2 Ding, Li, Jordan, 2010, с. 45-55.
- ↑ Berman, Plemmons, 1974, с. 161–172.
- ↑ Berman, Plemmons, 1994.
- ↑ Thomas, 1974, с. 393–394.
- ↑ Vavasis, 2009, с. 1364–1377.
- ↑ Zhang, Fang, Liu, Tang и др., 2008, с. 1824–183.
- ↑ 1 2 Hoyer, 2002.
- ↑ 1 2 Taslaman, Nilsson, 2012, с. e46331.
- ↑ Hsieh, Dhillon, 2011, с. 1064.
- ↑ Архивированная копия (неопр.). Дата обращения: 16 октября 2018. Архивировано 24 сентября 2015 года.
- ↑ Fung, Li, Cheung, 2007, с. 284–287.
- ↑ Guan, Tao, Luo, Yuan, 2012, с. 1087–1099.
- ↑ 1 2 Lin, 2007, с. 2756–2779.
- ↑ Lin, 2007, с. 1589–1596.
- ↑ Kim, Park, 2008, с. 713-730.
- ↑ Guan, Tao, Luo, Yuan, 2012, с. 2882–2898.
- ↑ Kim, Park, 2011, с. 3261-3281.
- ↑ Kim, He, Park, 2013, с. 285-319.
- ↑ 1 2 Zhu, Guangtun B. (2016-12-19), Nonnegative Matrix Factorization (NMF) with Heteroscedastic Uncertainties and Missing data, arΧiv:1612.06037 [astro-ph.IM].
- ↑ 1 2 Soummer, Pueyo, Larkin, 2012, с. L28.
- ↑ 1 2 3 Pueyo, 2016, с. 117.
- ↑ Campbell, Poole, 1981, с. 175–182.
- ↑ Kalofolias, Gallopoulos, 2012, с. 421–435.
- ↑ 1 2 Arora, Ge, Halpern, Mimno и др., 2013.
- ↑ Lee, Seung, 1999, с. 788–791.
- ↑ Buntine, 2002, с. 23–34.
- ↑ Gaussier, Goutte, 2005, с. 601–602.
- ↑ Zass, Shashua, 2005.
- ↑ Welling, Rosen-zvi, Hinton, 2004.
- ↑ Paatero, 1999, с. 854-888.
- ↑ Welling, Weber, 2001, с. 1255-1261.
- ↑ Kim, Park, 2012, с. 311-326.
- ↑ Yilmaz, Cemgil, Simsekli, 2011.
- ↑ Potluru, Plis, Morup, Calhoun, Lane, 2009, с. 1218–1229.
- ↑ Xu, Liu, Gong, 2003, с. 267-273.
- ↑ Eggert, Körner, 2004, с. 2529-2533.
- ↑ Lafrenière, Maroid, Doyon, Barman, 2009.
- ↑ Amara, Quanz, 2012, с. 948.
- ↑ Wahhaj, Cieza, Mawet, Yang и др., 2015, с. A24.
- ↑ Nielsen, Balslev, Hansen, 2005, с. 520–522.
- ↑ Cohen, 2005.
- ↑ Berry, Browne, 2005, с. 249-264.
- ↑ Nielsen, 2008.
- ↑ Berry, Browne, Langville, Pauca, Plemmons, 2007, с. 155-173.
- ↑ Mao, Saul, Smith, 2006, с. 2273-2284.
- ↑ Chen, Wang, Shi, 2011, с. 334–347.
- ↑ Schmidt, Larsen, Hsiao, 2007, с. 431–436.
- ↑ Devarajan, 2008, с. e1000029.
- ↑ Kim, Park, 2007, с. 1495-1502.
- ↑ Schwalbe, 2013, с. 359-371.
- ↑ Alexandrov, Nik-Zainal, Wedge, Campbell, Stratton, 2013, с. 246–259.
- ↑ Di Paola, Bazin, Aubry, Aurengo и др., 1982, с. 1310–21.
- ↑ Sitek, Gullberg, Huesman, 2002, с. 216–25.
- ↑ Boutsidis, Gallopoulos, 2008, с. 1350–1362.
- ↑ Liu, Yang, Fan, He, Wang, 2010.
- ↑ Yin, Gao, Zhang, 2014.
- ↑ Wang, Vipperla, Evans, Zheng, 2013, с. 44–56.
- ↑ He, Kan, Xie, Chen, 2014.
- ↑ Liu, Wang, Gao, Han, 2013, с. 252–260.
- ↑ Chistikov, Dmitry; Kiefer, Stefan; Marušić, Ines; Shirmohammadi, Mahsa & Worrell, James (2016-05-22), Nonnegative Matrix Factorization Requires Irrationality, arΧiv:1605.06848 [cs.CC].
ЛитератураПравить
- Max Welling, Michal Rosen-zvi, Geoffrey E. Hinton. Exponential Family Harmoniums with an Application to Information Retrieval // Advances in Neural Information Processing Systems (NIPS).. — 2004.
- Julian Eggert, Edgar Körner. Sparse coding and NMF // Proceedings. 2004 IEEE International Joint Conference on Neural Networks. — 2004.
- Schmidt M.N., Larsen J., Hsiao F.T. Wind noise reduction using non-negative sparse coding // Machine Learning for Signal Processing, IEEE Workshop. — 2007.
- Ron Zass, Amnon Shashua. A Unifying Approach to Hard and Probabilistic Clustering // International Conference on Computer Vision (ICCV). — Beijing, China, 2005.
- Ding C., Li T., Jordan M.I. Convex and semi-nonnegative matrix factorizations // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2010.
- Pentti Paatero. The Multilinear Engine: A Table-Driven, Least Squares Program for Solving Multilinear Problems, including the n-Way Parallel Factor Analysis Model // Journal of Computational and Graphical Statistics. — 1999. — Т. 8, вып. 4. — С. 854–888. — doi:10.2307/1390831. — JSTOR 1390831.
- Max Welling, Markus Weber. Positive Tensor Factorization // Pattern Recognition Letters. — 2001. — Т. 22, вып. 12. — doi:10.1016/S0167-8655(01)00070-8.
- Jingu Kim, Haesun Park. Fast Nonnegative Tensor Factorization with an Active-set-like Method // High-Performance Scientific Computing: Algorithms and Applications. — Springer, 2012. — С. 311–326.
- Kenan Yilmaz, A. Taylan Cemgil, Umut Simsekli. Generalized Coupled Tensor Factorization // Advances in Neural Information Processing Systems (NIPS).. — 2011.
- Vamsi K. Potluru, Sergey M. Plis, Morten Morup, Vince D. Calhoun, Terran Lane. Efficient Multiplicative updates for Support Vector Machines // Proceedings of the 2009 SIAM Conference on Data Mining (SDM). — 2009. — С. 1218–1229.
- Wei Xu, Xin Liu, Yihong Gong. Document clustering based on non-negative matrix factorization // Proceedings of the 26th annual international ACM SIGIR conference on Research and development in information retrieval. — New York: Association for Computing Machinery, 2003.
- Rashish Tandon, Suvrit Sra. Sparse nonnegative matrix approximation: new formulations and algorithms. — 2010. — (Technical Report).
- Rainer Gemulla, Erik Nijkamp, Peter J Haas, Yannis Sismanis. Large-scale matrix factorization with distributed stochastic gradient descent // Proc. ACM SIGKDD Int'l Conf. on Knowledge discovery and data mining. — 2011. — С. 69–77. (недоступная ссылка)
- Yang Bao. TopicMF: Simultaneously Exploiting Ratings and Reviews for Recommendation // American Association for Artificial Intelligence. — 2014.
- Ben Murrell. Non-Negative Matrix Factorization for Learning Alignment-Specific Models of Protein Evolution // PLoS ONE. — 2011. — Т. 6, вып. 12. — doi:10.1371/journal.pone.0028898. — PMID 22216138.
- Ding C., Li T., Peng W. On the equivalence between non-negative matrix factorization and probabilistic latent semantic indexing // Computational Statistics & Data Analysis. — 2008. — Вып. 52. Архивировано 4 марта 2016 года.
- William H. Lawton, Edward A. Sylvestre. Self modeling curve resolution // Technometrics. — 1971. — Т. 13, вып. 3. — doi:10.2307/1267173. — JSTOR 1267173.
- Paatero P., Tapper U. Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values // Environmetrics. — 1994. — Т. 5, вып. 2. — doi:10.1002/env.3170050203.
- Pia Anttila, Pentti Paatero, Unto Tapper, Olli Järvinen. Source identification of bulk wet deposition in Finland by positive matrix factorization // Atmospheric Environment. — 1995. — Т. 29, вып. 14. — doi:10.1016/1352-2310(94)00367-T. — Bibcode: 1995AtmEn..29.1705A.
- Daniel D. Lee, H. Sebastian Seung. Learning the parts of objects by non-negative matrix factorization // Nature. — 1999. — Т. 401, вып. 6755. — doi:10.1038/44565. — Bibcode: 1999Natur.401..788L. — PMID 10548103.
- Daniel D. Lee, H. Sebastian Seung. Algorithms for Non-negative Matrix Factorization // Advances in Neural Information Processing Systems 13: Proceedings of the 2000 Conference. — MIT Press, 2001.
- Zhang T., Fang B., Liu W., Tang Y. Y., He G., Wen J. Total variation norm-based nonnegative matrix factorization for identifying discriminant representation of image patterns // Neurocomputing. — 2008. — Т. 71, вып. 10–12. — doi:10.1016/j.neucom.2008.01.022.
- Berman A., Plemmons R.J. Inverses of nonnegative matrices // Linear and Multilinear Algebra. — 1974. — Т. 2, вып. 2. — С. 161–172. — doi:10.1080/03081087408817055.
- Berman A., Plemmons R.J. Nonnegative matrices in the Mathematical Sciences. — Philadelphia: SIAM, 1994.
- Thomas L.B. Problem 73-14, Rank factorization of nonnegative matrices // SIAM Rev.. — 1974. — Т. 16, вып. 3. — doi:10.1137/1016064.
- Vavasis S.A. On the complexity of nonnegative matrix factorization // SIAM J. Optim.. — 2009. — Т. 20, вып. 3. — doi:10.1137/070709967. — arXiv:0708.4149.
- Inderjit S. Dhillon, Suvrit Sra. Generalized Nonnegative Matrix Approximations with Bregman Divergences // NIPS. — 2005.
- Campbell S.L., Poole G.D. Computing nonnegative rank factorizations // Linear Algebra Appl.. — 1981. — Т. 35. — doi:10.1016/0024-3795(81)90272-x.
- Kalofolias V., Gallopoulos E. Computing symmetric nonnegative rank factorizations // Linear Algebra Appl. — 2012. — Т. 436, вып. 2. — doi:10.1016/j.laa.2011.03.016.
- Sanjeev Arora, Rong Ge, Yoni Halpern, David Mimno, Ankur Moitra, David Sontag, Yichen Wu, Michael Zhu. A practical algorithm for topic modeling with provable guarantees // Proceedings of the 30th International Conference on Machine Learning. — 2013.
- Daniel D Lee, H Sebastian Seung. Learning the parts of objects by non-negative matrix factorization // Nature. — 1999. — Т. 401, вып. 6755. — doi:10.1038/44565. — Bibcode: 1999Natur.401..788L. — PMID 10548103.
- Wray Buntine. Variational Extensions to EM and Multinomial PCA // Proc. European Conference on Machine Learning (ECML-02). — 2002. — Т. 2430. — (LNAI).
- Eric Gaussier, Cyril Goutte. Relation between PLSA and NMF and Implications // Proc. 28th international ACM SIGIR conference on Research and development in information retrieval (SIGIR-05). — 2005. Архивная копия от 28 сентября 2007 на Wayback Machine
- Patrik O. Hoyer. Non-negative sparse coding // Proc. IEEE Workshop on Neural Networks for Signal Processing. — 2002.
- Leo Taslaman, Björn Nilsson. A framework for regularized non-negative matrix factorization, with application to the analysis of gene expression data // PLoS One. — 2012. — Т. 7, вып. 11. — С. e46331. — doi:10.1371/journal.pone.0046331. — Bibcode: 2012PLoSO...746331T. — PMID 23133590.
- Hsieh C. J., Dhillon I. S. Fast coordinate descent methods with variable selection for non-negative matrix factorization // Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '11. — 2011. — ISBN 9781450308137. — doi:10.1145/2020408.2020577.
- Yik-Hing Fung, Chun-Hung Li, William K. Cheung. Online Discussion Participation Prediction Using Non-negative Matrix Factorization. — IEEE Computer Society, 2007. — Ноябрь.
- Naiyang Guan, Dacheng Tao, Zhigang Luo, Bo Yuan. Online Nonnegative Matrix Factorization With Robust Stochastic Approximation // IEEE Transactions on Neural Networks and Learning Systems. — 2012. — Июль (т. 23, вып. 7). — doi:10.1109/TNNLS.2012.2197827. — PMID 24807135.
- Chih-Jen Lin. Projected Gradient Methods for Nonnegative Matrix Factorization // Neural Computation. — 2007. — Т. 19, вып. 10. — С. 2756–2779. — doi:10.1162/neco.2007.19.10.2756. — PMID 17716011.
- Chih-Jen Lin. On the Convergence of Multiplicative Update Algorithms for Nonnegative Matrix Factorization // IEEE Transactions on Neural Networks. — 2007. — Т. 18, вып. 6. — doi:10.1109/TNN.2007.895831.
- Hyunsoo Kim, Haesun Park. Nonnegative Matrix Factorization Based on Alternating Nonnegativity Constrained Least Squares and Active Set Method // SIAM Journal on Matrix Analysis and Applications. — 2008. — Т. 30, вып. 2. — С. 713–730. — doi:10.1137/07069239x.
- Naiyang Guan, Dacheng Tao, Zhigang Luo, Bo Yuan. NeNMF: An Optimal Gradient Method for Nonnegative Matrix Factorization // IEEE Transactions on Signal Processing. — 2012. — Июнь (т. 60, вып. 6). — С. 2882–2898. — doi:10.1109/TSP.2012.2190406. — Bibcode: 2012ITSP...60.2882G.
- Jingu Kim, Haesun Park. Fast Nonnegative Matrix Factorization: An Active-set-like Method and Comparisons // SIAM Journal on Scientific Computing. — 2011. — Т. 58, вып. 6. — doi:10.1137/110821172. (недоступная ссылка)
- Jingu Kim, Yunlong He, Haesun Park. Algorithms for nonnegative matrix and tensor factorizations: A unified view based on block coordinate descent framework // Journal of Global Optimization. — 2013. — Т. 33, вып. 2. — С. 285–319. — doi:10.1007/s10898-013-0035-4.
- Ding C., He X., Simon H.D. On the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering // Proc. SIAM Int'l Conf. Data Mining. — 2005. — Т. 4. — ISBN 978-0-89871-593-4. — doi:10.1137/1.9781611972757.70.
- Michael R. Blanton, Sam Roweis. K-corrections and filter transformations in the ultraviolet, optical, and near infrared // The Astronomical Journal. — 2007. — Т. 133, вып. 2. — doi:10.1086/510127. — Bibcode: 2007AJ....133..734B. — arXiv:astro-ph/0606170.
- Bin Ren, Laurent Pueyo, Guangtun B. Zhu, Gaspard Duchêne. Non-negative Matrix Factorization: Robust Extraction of Extended Structures // The Astrophysical Journal. — 2018. — Т. 852, вып. 2. — С. 104. — doi:10.3847/1538-4357/aaa1f2. — Bibcode: 2018ApJ...852..104R. — arXiv:1712.10317.
- David Lafrenière, Christian Maroid, René Doyon, Travis Barman. HST/NICMOS Detection of HR 8799 b in 1998 // The Astrophysical Journal Letters. — 2009. — Т. 694, вып. 2. — С. L148. — doi:10.1088/0004-637X/694/2/L148. — Bibcode: 2009ApJ...694L.148L. — arXiv:0902.3247.
- Adam Amara, Sascha P. Quanz. PYNPOINT: an image processing package for finding exoplanets // Monthly Notices of the Royal Astronomical Society. — 2012. — Т. 427, вып. 2. — doi:10.1111/j.1365-2966.2012.21918.x. — Bibcode: 2012MNRAS.427..948A. — arXiv:1207.6637.
- Rémi Soummer, Laurent Pueyo, James Larkin. Detection and Characterization of Exoplanets and Disks Using Projections on Karhunen-Loève Eigenimages // The Astrophysical Journal Letters. — 2012. — Т. 755, вып. 2. — doi:10.1088/2041-8205/755/2/L28. — Bibcode: 2012ApJ...755L..28S. — arXiv:1207.4197.
- Zahed Wahhaj, Lucas A. Cieza, Dimitri Mawet, Bin Yang, Hector Canovas, Jozua de Boer, Simon Casassus, François Ménard, Matthias R. Schreiber, Michael C. Liu, Beth A. Biller, Eric L. Nielsen, Thomas L. Hayward. Improving signal-to-noise in the direct imaging of exoplanets and circumstellar disks with MLOCI // Astronomy & Astrophysics. — 2015. — Т. 581, вып. 24. — С. A24. — doi:10.1051/0004-6361/201525837. — Bibcode: 2015A&A...581A..24W. — arXiv:1502.03092.
- Laurent Pueyo. Detection and Characterization of Exoplanets using Projections on Karhunen Loeve Eigenimages: Forward Modeling // The Astrophysical Journal. — 2016. — Т. 824, вып. 2. — doi:10.3847/0004-637X/824/2/117. — Bibcode: 2016ApJ...824..117P. — arXiv:1604.06097.
- Finn Årup Nielsen, Daniela Balslev, Lars Kai Hansen. Mining the posterior cingulate: segregation between memory and pain components // NeuroImage. — 2005. — Т. 27, вып. 3. — С. 520–522. — doi:10.1016/j.neuroimage.2005.04.034. — PMID 15946864.
- William Cohen. Enron Email Dataset. — 2005. — Апрель.
- Michael W. Berry, Murray Browne. Email Surveillance Using Non-negative Matrix Factorization // Computational and Mathematical Organization Theory. — 2005. — Т. 11, вып. 3. — doi:10.1007/s10588-005-5380-5.
- Finn Årup Nielsen. Clustering of scientific citations in Wikipedia // Wikimania. — 2008.
- Berry M.W., Browne M., Langville A.N., Pauca V.P., Plemmons R.J. Algorithms and Applications for Approximate Nonnegative Matrix Factorization // Computational Statistics and Data Analysis. — 2007.
- Yun Mao, Lawrence Saul, Jonathan M. Smith. IDES: An Internet Distance Estimation Service for Large Networks // IEEE Journal on Selected Areas in Communications. — 2006. — Т. 24, вып. 12. — С. 2273–2284. — doi:10.1109/JSAC.2006.884026.
- Yang Chen, Xiao Wang, Cong Shi. Phoenix: A Weight-based Network Coordinate System Using Matrix Factorization. — 2011. — Т. 8, вып. 4. — doi:10.1109/tnsm.2011.110911.100079. Архивировано 14 ноября 2011 года.
- Devarajan K. Nonnegative Matrix Factorization: An Analytical and Interpretive Tool in Computational Biology // PLoS Computational Biology. — 2008. — Т. 4, вып. 7. — doi:10.1371/journal.pcbi.1000029. — Bibcode: 2008PLSCB...4E0029D. — PMID 18654623.
- Hyunsoo Kim, Haesun Park. Sparse non-negative matrix factorizations via alternating non-negativity-constrained least squares for microarray data analysis // Bioinformatics. — 2007. — Т. 23, вып. 12. — doi:10.1093/bioinformatics/btm134. — PMID 17483501.
- Schwalbe E. DNA methylation profiling of medulloblastoma allows robust sub-classification and improved outcome prediction using formalin-fixed biopsies // Acta Neuropathologica. — 2013. — Т. 125, вып. 3. — doi:10.1007/s00401-012-1077-2. — PMID 23291781.
- Ludmil B. Alexandrov, Serena Nik-Zainal, David C. Wedge, Peter J. Campbell, Michael R. Stratton. Deciphering signatures of mutational processes operative in human cancer // Cell Reports. — 2013. — Январь (т. 3, вып. 1). — ISSN 2211-1247. — doi:10.1016/j.celrep.2012.12.008. — PMID 23318258.
- Di Paola R., Bazin J.P., Aubry F., Aurengo A., Cavailloles F., Herry J.Y., Kahn E. Handling of dynamic sequences in nuclear medicine // IEEE Trans Nucl Sci. — 1982. — Т. NS-29, вып. 4. — doi:10.1109/tns.1982.4332188. — Bibcode: 1982ITNS...29.1310D.
- Sitek A., Gullberg G.T., Huesman R.H. Correction for ambiguous solutions in factor analysis using a penalized least squares objective // IEEE Trans Med Imaging. — 2002. — Т. 21, вып. 3. — doi:10.1109/42.996340. — PMID 11989846.
- Boutsidis C., Gallopoulos E. SVD based initialization: A head start for nonnegative matrix factorization // Pattern Recognition. — 2008. — Т. 41, вып. 4. — С. 1350–1362. — doi:10.1016/j.patcog.2007.09.010.
- Chao Liu, Hung-chih Yang, Jinliang Fan, Li-Wei He, Yi-Min Wang. Distributed Nonnegative Matrix Factorization for Web-Scale Dyadic Data Analysis on MapReduce // Proceedings of the 19th International World Wide Web Conference. — 2010.
- Jiangtao Yin, Lixin Gao, Zhongfei (Mark) Zhang. Scalable Nonnegative Matrix Factorization with Block-wise Updates // Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. — 2014.
- Dong Wang, Ravichander Vipperla, Nick Evans, Thomas Fang Zheng. Online Non-Negative Convolutive Pattern Learning for Speech Signals // IEEE Transactions on Signal Processing. — 2013. — Т. 61, вып. 1. — С. 44–56. — doi:10.1109/tsp.2012.2222381. — Bibcode: 2013ITSP...61...44W. Архивировано 19 апреля 2015 года.
- Xiangnan He, Min-Yen Kan, Peichu Xie, Xiao Chen. Comment-based Multi-View Clustering of Web 2.0 Items // Proceedings of the 23rd International World Wide Web Conference. — 2014. Архивировано 2 апреля 2015 года.
- Jialu Liu, Chi Wang, Jing Gao, Jiawei Han. Multi-View Clustering via Joint Nonnegative Matrix Factorization. — Proceedings of SIAM Data Mining Conference. — 2013. — С. 252–260. — ISBN 978-1-61197-262-7. — doi:10.1137/1.9781611972832.28.
Дополнительная литератураПравить
- Shen J., Israël G. W. A receptor model using a specific non-negative transformation technique for ambient aerosol // Atmospheric Environment. — 1989. — Т. 23, вып. 10. — С. 2289–2298. — doi:10.1016/0004-6981(89)90190-X. — Bibcode: 1989AtmEn..23.2289S.
- Pentti Paatero. Least squares formulation of robust non-negative factor analysis // Chemometrics and Intelligent Laboratory Systems. — 1997. — Т. 37, вып. 1. — С. 23–35. — doi:10.1016/S0169-7439(96)00044-5.
- Raul Kompass. A Generalized Divergence Measure for Nonnegative Matrix Factorization // Neural Computation. — 2007. — Т. 19, вып. 3. — С. 780–791. — doi:10.1162/neco.2007.19.3.780. — PMID 17298233.
- Liu W.X., Zheng N.N., You Q.B. Nonnegative Matrix Factorization and its applications in pattern recognition // Chinese Science Bulletin. — 2006. — Т. 51, вып. 17–18. — С. 7–18. — doi:10.1007/s11434-005-1109-6. — Bibcode: 2006ChSBu..51....7L. (недоступная ссылка)
- Ngoc-Diep Ho, Paul Van Dooren, Vincent Blondel. Descent Methods for Nonnegative Matrix Factorization. — 2008.
- Andrzej Cichocki, Rafal Zdunek, Shun-ichi Amari. Nonnegative Matrix and Tensor Factorization // IEEE Signal Processing Magazine. — 2008. — Т. 25, вып. 1. — С. 142–145. — doi:10.1109/MSP.2008.4408452. — Bibcode: 2008ISPM...25R.142C.
- Cédric Févotte, Nancy Bertin, Jean-Louis Durrieu. Nonnegative Matrix Factorization with the Itakura-Saito Divergence: With Application to Music Analysis // Neural Computation. — 2009. — Т. 21, вып. 3. — С. 793–830. — doi:10.1162/neco.2008.04-08-771. — PMID 18785855.
- Ali Taylan Cemgil. Bayesian Inference for Nonnegative Matrix Factorisation Models // Computational Intelligence and Neuroscience. — 2009. — Т. 2009, вып. 2. — С. 1–17. — doi:10.1155/2009/785152. — PMID 19536273. (недоступная ссылка)
Для улучшения этой статьи желательно:
|