Введение

Алгоритмы разложения матриц

Неотрицательная матричная факторизация (НМФ или ННМФ), также известная как неотрицательная матричная аппроксимация, – это группа алгоритмов в многомерном анализе и линейной алгебре, в которых матрица 'V' разлагается на (обычно) две матрицы 'W' и 'H', при этом все три матрицы не содержат отрицательных элементов. Такая неотрицательность упрощает анализ полученных матриц. Кроме того, в приложениях, таких как обработка аудиоспектрограмм или данных о мышечной активности, неотрицательность является неотъемлемым свойством рассматриваемых данных. Поскольку задача, как правило, не имеет точного решения, она обычно решается численными методами приближения. НМФ находит применение в таких областях, как астрономия, хемометрика, обработка звуковых сигналов, рекомендательные системы и биоинформатика.

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

Обычно число столбцов матрицы 'W' и число строк матрицы 'H' в NMF выбираются таким образом, чтобы произведение 'WH' являлось приближением к матрице 'V'. Полное разложение матрицы 'V' тогда сводится к двум неотрицательным матрицам 'W' и 'H', а также к остатку 'U', таким образом, что: 'V' = 'WH' + 'U'. Элементы остаточной матрицы могут быть как отрицательными, так и положительными. Когда матрицы 'W' и 'H' меньше матрицы 'V' по размеру, их легче хранить и обрабатывать. Другая причина разложения матрицы 'V' на меньшие матрицы 'W' и 'H' заключается в том, что если цель состоит в приближенном представлении элементов 'V' значительно меньшим объемом данных, то необходимо выявить некоторую скрытую структуру в данных.

Факторизация выпуклой неотрицательной матрицы

В стандартном NMF матричный фактор "W" ∈ R+^(m × k), то есть "W" может принимать любые значения в этом пространстве. Выпуклый NMF ограничивает столбцы "W" выпуклыми комбинациями входных векторов данных. Это значительно улучшает качество представления данных матрицей "W". Кроме того, результирующий матричный фактор "H" становится более разреженным и ортогональным.

Неотрицательная факторная оценка ранга

В случае, если неотрицательный ранг матрицы 'V' равен её обычному рангу, разложение 1 = 'V' = 'WH' называется неотрицательной ранговой факторизацией (NRF). Задача нахождения NRF для 'V', если такое разложение существует, известна как NP-трудная задача.

Онлайн-МФН

Многие стандартные алгоритмы NMF анализируют все данные целиком, то есть вся матрица доступна с самого начала. Это может быть неудовлетворительно в приложениях, где объем данных слишком велик для размещения в памяти или когда данные поступают в виде потока. Один из таких примеров – совместная фильтрация в рекомендательных системах, где может быть большое количество пользователей и элементов для рекомендации, и пересчет всего при добавлении нового пользователя или элемента был бы неэффективен. Функция потерь для оптимизации в таких случаях может совпадать, а может и не совпадать со стандартной NMF, но сами алгоритмы должны существенно отличаться.

Конволюционная МФМ

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

Алгоритмы

Существует несколько способов нахождения матриц 'W' и 'H': итеративное обновление по Ли и Сёну, метод активного множества, метод оптимального градиента и метод блочного главного поворота – лишь некоторые из них. Современные алгоритмы являются субоптимальными, поскольку гарантируют нахождение лишь локального, а не глобального минимума целевой функции. Вероятность создания алгоритма, гарантированно находящего оптимальное решение, невелика в ближайшем будущем, так как показано, что данная задача обобщает задачу k-средних кластеризации, известную как NP-полная. Однако, как и во многих других задачах анализа данных, локальный минимум все равно может оказаться полезным. Помимо этапа оптимизации, значительное влияние на NMF оказывает инициализация. Начальные значения, выбранные для матриц 'W' и 'H', могут влиять не только на скорость сходимости, но и на общую ошибку в точке сходимости. Варианты инициализации включают полную рандомизацию, SVD, k-средних кластеризацию и более сложные стратегии, основанные на этих и других подходах. Сравнение фракционных остаточных дисперсий для PCA и NMF.pdf; Калофолиас и Галлопулос (2012) решили симметричную версию этой задачи, где матрица 'V' симметрична и содержит диагональную главную подматрицу ранга r. Их алгоритм работает за время O(rm²) в плотном случае. Арора, Ге, Халперн, Мимно, Моитра, Сонтаг, Ву и Чжу (2013) предложили алгоритм полиномиального времени для точного NMF, который работает в случае, когда один из факторов W удовлетворяет условию разделимости.

Уникальность

Факторизация не является единственной: матрица и ее обратная могут быть использованы для преобразования двух матриц факторизации, например, следующим образом.

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

Спектральный анализ данных

NMF также используется для анализа спектральных данных; одно из таких применений — в классификации космических объектов и космического мусора.

Прогноз расстояния через Интернет

NMF применяется для масштабируемого предсказания расстояний в Интернете (времени кругового обхода). Для сети с хостами, с помощью NMF, расстояния для всех конечных соединений могут быть предсказаны после проведения всего лишь измерений. Этот метод был впервые представлен в службе оценки расстояний в Интернете (IDES). Впоследствии, как полностью децентрализованный подход, была предложена система сетевых координат Phoenix. Она достигает более высокой общей точности предсказания, вводя понятие веса.

Нестационарная деноизация речи

Подавление шума в речи – давняя проблема в области обработки аудиосигналов. Существует множество алгоритмов для подавления шума, если он стационарен. Например, фильтр Винера подходит для аддитивного гауссовского шума. Однако, если шум нестационарен, классические алгоритмы подавления шума обычно показывают плохие результаты, поскольку статистическую информацию о нестационарном шуме сложно оценить. Шмидт и др. используют NMF для подавления шума в речи при нестационарном шуме, что принципиально отличается от классических статистических подходов. Основная идея заключается в том, что чистый речевой сигнал может быть разреженно представлен речевым словарем, а нестационарный шум – нет. Аналогично, нестационарный шум также может быть разреженно представлен шумовым словарем, а речь – нет. Алгоритм подавления шума с использованием NMF выглядит следующим образом. Два словаря – один для речи и один для шума – необходимо обучить заранее, в автономном режиме. Получив зашумленный речевой сигнал, мы сначала вычисляем амплитуду кратковременного преобразования Фурье. Затем, с помощью NMF, разделяем его на две составляющие: одна разреженно представляется речевым словарем, а другая – шумовым. Наконец, составляющая, представленная речевым словарем, является оценкой чистого речевого сигнала.

Генетика популяций

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

Биоинформатика

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

Ядерная визуализация

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

Другие

Анджей Чихоцкий, Мортен Мруп и др. : "Достижения в области неотрицательной матричной и тензорной факторизации", Hindawi Publishing Corporation, (2008). Анджей Чихоцкий, Рафаль Здунек, Ан Хуй Фан и Шун Ичи Амари: "Неотрицательные матричные и тензорные факторизации: применение к исследованию многомерного анализа данных и разделению слепых источников", Wiley, (2009). Андри Мирзал: "Неотрицательные матричные факторизации для кластеризации и LSI: теория и программирование", LAP LAMBERT Academic Publishing, (2011). Юн Сян: "Разделение слепых источников: анализ зависимых компонент", Springer, (2014). Ганеш Р. Наик (ред.): "Методы неотрицательной матричной факторизации: достижения в теории и приложениях", Springer, (2016). Джулиан Беккер: "Неотрицательная матричная факторизация с адаптивными элементами для разделения монофонических аудиоисточников: 1", Shaker Verlag GmbH, Германия, (2016). Джен Тзунг Чин: "Разделение источников и машинное обучение", Academic Press, (2018). Шодзи Макино (ред.): "Разделение аудиоисточников", Springer, (2019). Николас Гиллис: "Неотрицательная матричная факторизация", SIAM, (2020).