0:00
[ЗАСТАВКА] Привет!
С вами Евгений.
Из этого видео вы узнаете про неотрицательные матричные разложения —
еще один способ факторизации матрицы.
Факторизация матриц или представление матрицы
в виде произведения двух матриц меньшего ранга — это задача,
которую вы в разных постановках уже несколько раз рассматривали.
Давайте рассмотрим еще одну постановку.
Чтобы вы не расслаблялись, давайте снова сменим все обозначения.
Пусть матрица X размера n х m — это то, что нам дано.
Мы хотим ее представить в виде произведения матриц W,
размера n х r, и H, размера r х m.
r, естественно, меньше чем минимум между n и m.
Задача поиска таких матриц может быть представлена, как оптимизационная,
то есть задача минимизации некоторого функционала D (X, W * H).
Этот функционал будет измерять насколько
точно наше произведение приближает исходную матрицу X.
Особенность задачи неотрицательных матричных разложений, или NMF,
заключается в том, что решение W и H мы будем искать в множестве матриц
с неотрицательными элементами.
Такая постановка часто имеет смысл,
если матрицы W и H вы хотите по итогам разложения как-то интерпретировать.
Например, эти матрицы могут представлять собой вероятности
появления слов в каких-то текстах,
документах, или концентрации веществ в растворах и так далее.
То есть, если вам важно, чтобы они были неотрицательными, используйте этот метод.
Давайте обозначим за X с крышкой произведение W * H.
Нас будут интересовать функции потерь D,
которые распадаются на суммы функции потерь между
ij компонентой исходной матрицы X и ij компонентой матрицы X с крышкой.
Такие функции потерь называются сепарабельными.
Чаще всего в задаче неотрицательного матричного разложения в качестве функции
потерь используют норму Фробениуса, то есть,
просто сумму квадратов отклонений X (X с крышкой).
В задаче получения неотрицательных матричных разложений есть несколько
проблем.
Во-первых, она некорректно поставлена.
Если мы имеем какое-то решение этой задачи W0, H0,
то существует большое количество матриц Y, таких,
что W0 * Y и Y в минус первой * H0 также будут решением нашей задачи.
Если только у Y существует обратная матрица и преобразование
с помощью Y сохраняет неотрицательность элементов матриц W0, H0.
То есть, решение никогда не определяется однозначно.
Кроме того, функция потерь D и норма Фробениуса, которая берется чаще всего,
и многие другие не выпукла по совокупности аргументов W и H,
поэтому мы не можем использовать методы, которые находят глобальный минимум
нашей функции потерь и вынуждены использовать какие-то методы для бедных.
Чаще всего используется блочно-покоординатная минимизация,
то есть, мы фиксируем одну из матриц, например, W и обновляем матрицу H,
используя какую-то функцию f от исходной матрицы X,
матрицы W и матрицы H с предыдущего шага.
Затем обновляем матрицу W, используя вот это новое значение матрицы H.
И вот так делаем в цикле до тех пор, пока не сойдемся.
Поскольку эта задача симметричная, кстати говоря,
функция f должна быть очень похожа на функцию g, то есть, в частности она
должна быть равна g транспонированное от всех транспонированных элементов.
Давайте вернемся к задаче с нормой Фробениуса.
Если бы у нас не было ограничения неотрицательности,
мы легко получили бы решение с помощью сингулярного разложения.
Ну поскольку его нет, будем пользоваться какими-то градиентными методами.
Базовым методом для нас будет служить поочередный градиентный спуск,
то есть мы будем фиксировать одну матрицу по всем элементам второй матрицы
пробегать и делать какой-то шажок в направлении антиградиента.
Затем повторять то же самое со второй матрицей.
Проблема в том, что градиентный спуск не учитывает ограничение неотрицательности.
Это можно как-то исправить.
Способ номер №1: мы можем выбрать шаг градиентного спуска так,
что обновления наших матриц станут мультипликативными,
и тогда знак будет автоматически сохраняться.
Посмотрите, как это можно сделать.
Частная производная нашей функции потерь по элементу матрицы h
с индексами k и j равна разности двух положительных компонент.
Возьмем в качестве шага градиентного спуска отношение h
kj-го к вот этой первой положительной компоненте из разностей.
Если мы теперь это подставим в выражение для градиентного спуска и упростим,
мы получим, что наши обновления имеют мультипликативный вид, то есть,
старый элемент матрицы просто умножается на какое-то число и это число
неотрицательное, вообще говоря, даже 0 не может быть равно.
Таким образом, если мы инициализировали нашу матрицу H как-то удачно,
и там нет отрицательных компонент,
то в ходе итерационного процесса они не могут и появиться.
Это то, что нам нужно.
В матричном виде такие мультипликативные обновления можно записать следующим
образом.
Здесь крестик в кружочке обозначает поэлементное умножение матриц,
а черточка в кружочке — поэлементное деление.
Можно показать, что в алгоритме с мультипликативными
обновлениями функция потерь D на каждом шаге монотонно не возрастает,
то есть, мы постепенно уменьшаем нашу функцию потерь, ну или,
по крайней мере, не увеличиваем, то есть, задача как-то решается.
Такие методы очень популярны.
Потому что, во-первых, они просты в реализации.
Во-вторых, они хорошо масштабируются и легко приспосабливаются к работе с
разреженными матрицами.
И, кроме того, исторически эти методы были предложены в самой первой статье по
неотрицательным матричным разложениям.
Однако скорость сходимости таких методов не очень большая.
Впрочем, ее можно увеличить,
если обновлять матрицы W и H не по одному разу в цикле, а по несколько раз подряд.
Задача неотрицательного матричного разложения с нормой Фробениуса может
решаться еще несколькими очень эффективными интересными способами.
Давайте их тоже рассмотрим.
Поскольку, если мы фиксируем одну из двух матриц
внутри нашей нормы Фробениуса, мы получим задачу минимизации наименьших квадратов,
которую мы можем решать аналитически, кажется, что вот это знание как-то можно
использовать для ускорения поиска глобального минимума нашей задачи.
Это делает метод попеременных наименьших квадратов.
На каждом шаге мы находим точное решение задачи наименьших
квадратов по одной из компонент, но, к сожалению,
это решение может давать и неотрицательные значения в матрицах.
Просто будем все их заменять нулями,
то есть будем проецировать нашу матрицу на неотрицательную область.
Этот метод быстрый и грубый.
Итерационный процесс может не сходиться при таких обновлениях.
Функция потерь не монотонна, то есть она может увеличиваться,
и это все происходит из-за проецирования.
Этот метод можно использовать для инициализации каких-то других
более сложных методов.
На другом полюсе методов неотрицательного матричного разложения с нормой
Фробениуса находится метод попеременных неотрицательных наименьших квадратов.
Он действует сначала точно так же, как метод попеременных наименьших квадратов.
Мы фиксируем одну из матриц, ищем минимум нашей функции потерь по второй.
Но в этом методе мы будем его искать только в области
неотрицательности, то есть мы не будем вообще рассматривать
в качестве решения матрицы H с отрицательными элементами.
Решение такой задачи найти сложнее.
Аналитически его записать нельзя.
Поэтому этот метод медленнее, но он точнее.
Каждая итерация этого метода требует существенных вычислительных затрат,
поэтому им можно пользоваться для уточнения решения,
которое найдено более простыми методами.
Наконец, один из самых эффективных и
популярных методов неотрицательного матричного разложения с нормой Фробениуса
является метод иерархических попеременных наименьших квадратов.
Идея заключается в том, чтобы обновлять матрицы W и H не целиком,
а небольшими кусками.
Оказывается, что мы можем найти аналитически минимум нормы Фробениуса
не только по матрице W, но и по отдельному ее столбцу,
или то же самое по строке матрицы H, а затем мы вот этот
аналитический минимум будем проецировать на неотрицательную область.
Проекция здесь оказывает менее разрушительное действие,
чем в методе попеременных наименьших квадратов,
поскольку одновременно обновляются только небольшие куски матриц.
Такой метод достаточно вычислительно эффективен и
сходится он быстрее, чем метод мультипликативных обновлений.
Однако он более чувствителен к начальному приближению, то есть матрицы W и H,
которые вы подаете на вход, должны быть лучше.
Итак, в этом видео мы узнали, что такое неотрицательные матричные разложения.
Поставили задачу и узнали, какие у этой задачи есть проблемы,
а затем мы зафиксировали функционал потерь нормы Фробениуса и для этого
Функционала рассмотрели несколько классических методов получения
неотрицательного матричного разложения.
В следующем видео мы поговорим о том, какие еще можно брать функционалы потерь и
зачем это делать, а также откуда можно брать начальное приближение.
Evgeniy Riabenko
Evgeny Sokolov
Victor Kantor
Emeli Dral
Константин Воронцовдоктор физико-математических наук, профессор
