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

Почему SVD разлагает лица на призрачные глобальные паттерны, а NMF - на нос, рот, глаза? В чём математическая причина этого различия?

• **Spotify:** тематическое профилирование 20 млн треков x 50 латентных факторов NMF - основа плейлистов 'Discover Weekly'
• **Геномика:** разложение матриц мутационных сигнатур: опухолевые образцы = смесь мутационных процессов (COSMIC SBS signatures)
• **NLP:** тематическое моделирование документов без вероятностных предположений LDA - NMF на матрице TF-IDF
• **Рекомендательные системы:** Netflix Prize: матрица рейтингов пользователь x фильм факторизуется NMF в латентные предпочтения

Предварительные знания

• Сингулярное разложение SVD
• Норма Фробениуса
• Условия Каруша-Куна-Таккера (KKT)

• SVD и псевдообратная матрица
• Нормы матриц

Определение и функция потерь

Дэниел Ли и Себастьян Сеунг в 1999 году опубликовали NMF в Nature. Разложение изображений лиц: при W,H >= 0 компоненты W - локальные части (нос, глаз, рот), а не глобальные. Spotify применяет NMF для построения тематических профилей плейлистов: 20 млн треков x 50 латентных факторов, обновление ежедневно.

NMF решает задачу аппроксимации V приближённым произведением WH при ограничении неотрицательности. Физический смысл: каждый столбец V (например, изображение или документ) является неотрицательной линейной комбинацией столбцов W (базисных элементов). Это и есть 'части целого' - интерпретация, недоступная SVD.

Ключевое отличие NMF от SVD: при W, H >= 0 каждый столбец V представляется как неотрицательная линейная комбинация столбцов W. Это гарантирует интерпретацию как 'части целого' без взаимного вычитания компонент.

Алгоритм мультипликативных обновлений

Алгоритм Ли-Сеунга использует мультипликативные обновления вместо аддитивных - так гарантируется сохранение неотрицательности W и H на каждой итерации. Метод сходится монотонно к локальному минимуму нормы Фробениуса.

H_{a,mu} <- H_{a,mu} * (W^T V)_{a,mu} / (W^T W H)_{a,mu} W_{i,a} <- W_{i,a} * (V H^T)_{i,a} / (W H H^T)_{i,a} Каждый шаг сохраняет H, W >= 0 за счёт мультипликативной формы. Монотонно убывает loss = ||V - WH||_F^2.

Sparse, ортогональный NMF и применения

Базовый NMF расширяется добавлением регуляризаторов и ограничений. Sparse NMF с L1-штрафом - индустриальный стандарт для тематического моделирования: каждый документ описывается малым числом компонент. Ортогональный NMF (H H^T = I) сводится к жёсткой кластеризации.

Единственность NMF не гарантирована: при разных стартовых W0, H0 алгоритм сходится к разным локальным минимумам. На практике запускают несколько случайных инициализаций и выбирают результат с минимальной ошибкой реконструкции.

Связи с другими методами разложения

NMF занимает особое место среди методов матричного разложения - между SVD и кластеризацией.

• SVD и PCA — Связанная тема
• K-средние — Связанная тема
• LDA (латентное размещение Дирихле) — Связанная тема
• Тензорные разложения — Связанная тема

Итоги

• NMF: V approx WH с W, H >= 0 - разложение на 'части целого' без отрицательных весов
• Мультипликативные обновления Ли-Сеунга монотонно уменьшают ||V - WH||_F^2 при сохранении неотрицательности
• Задача NMF NP-сложна в общем случае: алгоритм находит локальный минимум, зависящий от инициализации
• Sparse NMF с L1-регуляризацией и ортогональный NMF - расширения для улучшения интерпретируемости
• Ранг k выбирается через cophenetic coefficient или стабильность нескольких запусков
• Применения: геномика, NLP, рекомендательные системы, анализ гиперспектральных изображений

Что гарантирует монотонность мультипликативных обновлений NMF?

Ли и Сеунг доказали монотонность через конструкцию вспомогательной функции G(h, h') >= L(h), G(h, h) = L(h). Шаг обновления минимизирует G, что гарантирует L(t+1) <= L(t). Задача не является выпуклой по (W, H) совместно - только по каждой переменной по отдельности.