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

Неотрицательное матричное разложение — это метод приближённого представления неотрицательной матрицы в виде произведения двух неотрицательных матриц меньшего размера.

Обычно задача записывается так:

$F\approx GU^T.$

Здесь $F$ — исходная матрица данных, $G$ и $U$ — искомые матрицы меньшей размерности.

Главное ограничение метода состоит в том, что все элементы матриц должны быть неотрицательными:

$f_{ij}\geq 0,\qquad g_{it}\geq 0,\qquad u_{jt}\geq 0.$

Из-за этого неотрицательное матричное разложение часто даёт более интерпретируемое представление данных, чем обычные матричные разложения. Объект описывается не через взаимную компенсацию положительных и отрицательных коэффициентов, а как сумма неотрицательных компонент.

Матричная постановка задачи

Пусть дана матрица

$F=(f_{ij})_{\ell\times n}.$

Строки этой матрицы соответствуют объектам, а столбцы — признакам.

Например, объектами могут быть пользователи, документы, изображения или товары. Признаками могут быть покупки, слова, пиксели, оценки или другие измеряемые характеристики.

Необходимо найти две матрицы:

$G=(g_{it})_{\ell\times m},$

$U=(u_{jt})_{n\times m},$

где

$m\ll n.$

Матрица $G$ задаёт новое описание объектов через $m$ скрытых факторов. Матрица $U$ показывает, как эти скрытые факторы связаны с исходными признаками.

Приближённое восстановление исходной матрицы имеет вид:

$\widehat F=GU^T.$

Для отдельного элемента матрицы:

$\widehat f_{ij}=\sum_{t=1}^{m} g_{it}u_{jt}.$

Задача состоит в том, чтобы восстановленная матрица $\widehat F$ была как можно ближе к исходной матрице $F$ .

Критерий качества

Один из стандартных критериев качества — сумма квадратов ошибок восстановления:

$Q(G,U)=\|GU^T-F\|^2\to\min_{G,U}.$

С учётом неотрицательности задача записывается так:

$Q(G,U)=\|GU^T-F\|^2\to\min_{G,U}, \qquad G\geq 0,\quad U\geq 0.$

В развернутом виде:

$Q(G,U)= \sum_{i=1}^{\ell}\sum_{j=1}^{n} \left( \sum_{t=1}^{m}g_{it}u_{jt}-f_{ij} \right)^2 \to\min_{G,U}.$

Если в матрице известны не все элементы, то сумма берётся только по множеству наблюдаемых пар:

$\Omega\subseteq \{1,\ldots,\ell\}\times\{1,\ldots,n\}.$

Тогда критерий имеет вид:

$Q(G,U)= \sum_{(i,j)\in\Omega} \left( \sum_{t=1}^{m}g_{it}u_{jt}-f_{ij} \right)^2 \to\min_{G,U}.$

Такая постановка особенно важна в рекомендательных системах, потому что пользователь обычно оценивает или покупает только малую часть всех товаров.

Смысл скрытых факторов

Неотрицательное матричное разложение можно понимать как поиск скрытой структуры в данных.

Каждый объект описывается не исходными признаками, а набором скрытых факторов:

$g_i=(g_{i1},\ldots,g_{im}).$

Каждый исходный признак также получает описание через эти факторы:

$u_j=(u_{j1},\ldots,u_{jm}).$

Если $g_{it}$ велико, это означает, что объект $i$ сильно связан с фактором $t$ .

Если $u_{jt}$ велико, это означает, что признак $j$ сильно связан с тем же фактором.

Например, в рекомендательной системе скрытый фактор может соответствовать интересу к фантастике, спорту, технике или образовательному контенту. Эти факторы заранее не задаются вручную. Они находятся по данным.

Пример с рекомендательной системой

Пусть матрица $F$ описывает взаимодействия пользователей с товарами.

Элемент

$f_{ij}$

может означать:

оценку пользователя $i$ товару $j$ ;
факт покупки;
лайк;
просмотр;
вероятность интереса к товару.

Тогда строка матрицы $G$ задаёт латентный вектор интересов пользователя:

$g_i=(g_{i1},\ldots,g_{im}).$

Строка матрицы $U$ задаёт латентный вектор свойств товара:

$u_j=(u_{j1},\ldots,u_{jm}).$

Прогноз интереса пользователя $i$ к товару $j$ вычисляется как скалярное произведение этих векторов:

$\widehat f_{ij}=\sum_{t=1}^{m}g_{it}u_{jt}.$

Если значение $\widehat f_{ij}$ большое, система может рекомендовать товар пользователю.

Отличие от метода главных компонент

Метод главных компонент также ищет низкоразмерное представление данных. В нём исходная матрица приближённо восстанавливается через произведение матриц:

$F\approx GU^T.$

Однако в методе главных компонент компоненты могут иметь как положительные, так и отрицательные значения.

В неотрицательном матричном разложении вводится дополнительное ограничение:

$G\geq 0,\qquad U\geq 0.$

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

Например, изображение можно рассматривать как сумму частей лица, документ — как смесь тем, а пользователя — как смесь интересов.

Интерпретируемость разложения

Главное достоинство неотрицательного разложения — интерпретируемость.

Если разрешены отрицательные коэффициенты, то один фактор может увеличивать значение признака, другой уменьшать, и итог получается как результат компенсации. Это усложняет объяснение модели.

В NMF используется только сложение неотрицательных вкладов:

$\widehat f_{ij}= g_{i1}u_{j1}+ g_{i2}u_{j2}+ \ldots+ g_{im}u_{jm}.$

Поэтому каждый фактор можно понимать как отдельную часть объекта.

Например:

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

Такое объяснение не всегда идеально, но оно часто понятнее, чем абстрактные ортогональные компоненты.

Метод чередующихся наименьших квадратов

Одним из способов решения задачи NMF является метод чередующихся наименьших квадратов.

Идея состоит в том, чтобы по очереди оптимизировать одну из матриц, считая другую фиксированной.

Сначала фиксируется $U$ и ищется $G$ .

Затем фиксируется $G$ и ищется $U$ .

Эти шаги повторяются много раз:

$G\to U\to G\to U\to\ldots$

Такой подход не гарантирует нахождение глобального минимума, потому что задача NMF в общем случае невыпуклая. Однако на практике он часто даёт полезное приближённое решение.

Покомпонентная идея ALS

Пусть разложение записано как сумма ранговых компонент:

$GU^T=\sum_{t=1}^{m}g_tu_t^T.$

Здесь $g_t$ и $u_t$ — столбцы матриц $G$ и $U$ .

Для обновления одной компоненты можно временно исключить её из суммы и рассмотреть остаточную матрицу:

$F_t=F-\sum_{s\neq t}g_su_s^T.$

Тогда задача для одной компоненты имеет вид:

$\|g_tu_t^T-F_t\|^2\to\min.$

При фиксированном $u_t$ обновление $g_t$ можно записать так:

$g_t= \left( \frac{F_tu_t}{u_t^Tu_t} \right)_+.$

При фиксированном $g_t$ обновление $u_t$ имеет вид:

$u_t= \left( \frac{F_t^Tg_t}{g_t^Tg_t} \right)_+.$

Обозначение $(z)_+$ означает положительную срезку:

$(z)_+=\max(z,0).$

Она нужна для выполнения условия неотрицательности.

Разреженные данные

Во многих реальных задачах матрица $F$ является разреженной. Это означает, что большая часть её элементов неизвестна или равна нулю.

Например, в рекомендательной системе пользователь видит только небольшую часть товаров. Поэтому матрица оценок пользователей почти всегда заполнена не полностью.

Если известные элементы задаются множеством $\Omega$ , то обучать модель нужно только по ним:

$(i,j)\in\Omega.$

Такой подход позволяет не требовать полной матрицы данных и одновременно восстанавливать пропущенные значения.

После обучения можно вычислить прогноз для неизвестной пары $(i,j)$ :

$\widehat f_{ij}=\sum_{t=1}^{m}g_{it}u_{jt}.$

Именно это делает матричные разложения полезными для рекомендаций.

Регуляризация

В прикладных задачах модель может переобучаться. Это означает, что она хорошо восстанавливает известные элементы матрицы, но плохо предсказывает неизвестные.

Для борьбы с переобучением добавляют регуляризацию:

$Q(G,U)= \sum_{(i,j)\in\Omega} \left( \sum_{t=1}^{m}g_{it}u_{jt}-f_{ij} \right)^2 + \lambda\|G\|^2+ \mu\|U\|^2 \to\min.$

Параметры $\lambda$ и $\mu$ управляют силой регуляризации.

Если они слишком малы, модель может переобучиться.

Если они слишком велики, модель станет слишком грубой и не сможет хорошо описать данные.

Выбор числа факторов

Число факторов $m$ — важный параметр модели.

Если $m$ слишком мало, модель не сможет описать сложную структуру данных.

Если $m$ слишком велико, модель может начать запоминать шум и случайные особенности обучающей выборки.

Обычно $m$ выбирают по качеству на отложенной выборке. В рекомендательной системе можно скрыть часть известных оценок, обучить модель на остальных и проверить, насколько хорошо она предсказывает скрытые значения.

Применения

Неотрицательное матричное разложение применяется в задачах, где данные естественно неотрицательны.

Основные примеры:

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

В текстах матрица $F$ может содержать частоты слов в документах. Тогда скрытые факторы можно интерпретировать как темы.

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

В рекомендациях матрица содержит действия пользователей. Тогда скрытые факторы описывают интересы пользователей и свойства товаров.

Преимущества метода

К преимуществам NMF относятся:

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

Ограничения метода

У метода есть и ограничения.

Во-первых, задача NMF обычно невыпуклая. Поэтому разные начальные приближения могут приводить к разным решениям.

Во-вторых, результат зависит от выбора числа факторов $m$ .

В-третьих, неотрицательность полезна не для всех данных. Если признаки по смыслу могут быть отрицательными, обычные методы вроде PCA или SVD могут быть более естественными.

В-четвёртых, интерпретируемость факторов не гарантируется автоматически. Иногда факторы действительно соответствуют понятным темам или группам признаков, а иногда их смысл приходится дополнительно анализировать.

Связь с обучаемой векторизацией

NMF можно рассматривать как один из способов обучаемой векторизации данных.

Исходный объект сначала задан длинным вектором признаков:

$x_i=(f_{i1},\ldots,f_{in}).$

После разложения он получает более короткое представление:

$g_i=(g_{i1},\ldots,g_{im}).$

Если

$m\ll n,$

то новое представление компактнее исходного.

Такое представление можно использовать для дальнейших задач: классификации, кластеризации, поиска похожих объектов или рекомендаций.

Вывод

Неотрицательное матричное разложение — это метод поиска скрытых факторов в неотрицательных данных.

Его основная идея состоит в приближении исходной матрицы произведением двух неотрицательных матриц:

$F\approx GU^T.$

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

Главное преимущество NMF — более понятная интерпретация факторов по сравнению с разложениями, где разрешены отрицательные коэффициенты. Главное ограничение — сложность оптимизации и зависимость результата от выбора числа факторов и начального приближения.

Литература

D. D. Lee, H. S. Seung. Learning the parts of objects by non-negative matrix factorization // Nature, 1999.
A. Cichocki, R. Zdunek, S. Amari. Hierarchical ALS algorithms for nonnegative matrix and 3D tensor factorization, 2007.
G. Takacs, I. Pilaszy, B. Nemeth, D. Tikk. Scalable collaborative filtering approaches for large recommendation systems // JMLR, 2009.
К. В. Воронцов. Обучаемая векторизация данных. Лекция курса «Философия. Введение в ИИ», 2026.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9D%D0%B5%D0%BE%D1%82%D1%80%D0%B8%D1%86%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%BB%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5»

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

Материал из MachineLearning.

Содержание