Вы никогда не будете бояться увидеть якобы пугающее уравнение матричной факторизации в своей жизни!
Код матричной факторизации: [здесь]
В этой статье вы узнаете о матричной факторизации, хлебе с маслом многих классических подходов к машинному обучению. В этой статье основное внимание будет уделено объяснению реальных приложений матричной факторизации (MF) (с примерами кода) и интуиции, лежащей в ее основе. Вы когда-нибудь думали, что матричную факторизацию можно использовать для перепрофилирования лекарств ❓
Если вы чем-то похожи на меня (надеюсь, нет), к концу этой статьи вы будете сожалеть о том, что преуменьшали важность матричной факторизации в своем курсе алгебры для студентов, потому что вы никогда не думали, что будете ее использовать.
Чтобы посетить мои предыдущие статьи из этой серии, используйте следующие буквы.
A B C D* E F G H I J K L* M* N O P Q R S T U V W X Y Z
Прелюдия
В студенческие годы математика никогда не была моей сильной стороной. Я никогда не понимал, почему важен угол касательной в данной точке кривой, или почему важен интеграл по кривой, приводящий к площади поверхности под кривой, или почему важна матричная факторизация? Конечно, многие данные, которые мы видим в цифровой сфере, могут быть представлены в виде матриц (или тензоров вообще). Но тут для меня это перестало иметь смысл. Например, если у вас уже есть полная матрица достоверности, зачем разбивать ее на две? преследовал меня на уроках алгебры.
Затем последовала аспирантура. Я работал над докторской диссертацией по глубокому обучению, и это был идеальный шторм для игнорирования таких тем, как матричная факторизация, поскольку это было чем-то, что редко упоминалось в литературе по глубокому обучению.
В настоящее время, как MLE, работающий над алгоритмами рекомендаций, я сразу же получил столь необходимое прозрение. «А-ха, так вот почему ты разбиваешь свою матрицу на две меньшие».
И, оглядываясь в прошлое на самого себя, наивного студента 10-летней давности, я не чувствую ничего, кроме глубокого сожаления о том, что не обратил на это больше внимания. Чтобы искупить свою вину, я собираюсь показать вам крутую матричную факторизацию, и ее концепции применимы к реальным приложениям. Я надеюсь, что это станет маяком для тех, кто может потерпеть крушение из-за тонущей математики и грубой алгебры.
Почему матрицы?
Задолго до матричной факторизации появились… матрицы. Многие данные, которые мы видим и с которыми работаем в науке о данных, могут быть представлены в виде матриц. Вот несколько примеров.
- 🖼 Изображение в градациях серого представляет собой матрицу пикселей, организованную в строки (высота) и столбцы (ширина).
- 📹 Видео может быть представлено в виде матрицы со строками, показывающими количество кадров и столбцов, представляющих собой изображение, развернутое в 1D-вектор.
- Корпус документов может быть представлен в виде матрицы, в которой строки представляют собой документы, а столбцы представляют собой все термины (то есть словарный запас), присутствующие в корпусе.
- 👟 Рейтинги элементов (таких как фильмы или продукты) могут быть представлены в виде матрицы со строками (по одному для каждого пользователя) и столбцами (по одному для каждого элемента).
Я надеюсь, что это достаточно убедительно, чтобы понять широко распространенный характер матриц в данных, с которыми мы сталкиваемся ежедневно.
Почему матричная факторизация?
Теперь, когда мы установили, что абсентеизма матриц нет, наша следующая цель — понять самый важный вопрос в этом обсуждении.
Зачем нам нужно разбивать (т.е. факторизовать) матрицы?
Я не могу дать универсального ответа, так как конкретное преимущество MF обычно зависит от приложения и самого алгоритма. Итак, позвольте мне мотивировать нас следующим образом.
Эти матрицы, которые я описал выше, не очень полезны сами по себе. Другими словами, думайте о них как о слое поверх лежащих в основе закономерностей в данных — это то, что мы обычно заинтересованы в раскрытии. Подобно тому, как вы огранили бы и отполировали алмаз, выкопанный из земли, чтобы повысить его привлекательность и ценность, этими наблюдаемыми матрицами необходимо определенным образом манипулировать, чтобы добраться до их сладкого центра. Матричная факторизация — это корабль для этого путешествия.
Матрицы данных, которые мы наблюдаем, содержат шаблоны/поведение источников, сгенерировавших эти данные.
Если говорить более подробно, обычно данные имеют внутренние шаблоны. Например, если часть изображения скрыта, вы все равно можете сделать вывод об отсутствующем контенте, используя информацию об окружающем пространстве. В другом примере, если некоторые слова изменены/удалены в документе, вы все равно можете понять значение или сообщение, передаваемое этим документом.
Почему это возможно? Это потому, что данные, которые мы видим, имеют в себе базовые закономерности. Пиксели на изображении не случайны. Текст в документе не случайный. С помощью матричной факторизации мы пытаемся прорезать наши наблюдаемые данные/шум, чтобы выявить такие закономерности. Почему важно изучать шаблоны, спросите вы? Наличие доступа к таким шаблонам является жизнеобеспечением систем поддержки принятия решений, которые мы разрабатываем. В конце концов, шаблоны обучения — это то, что делают модели машинного обучения.
Как МФ это делает?
Звучит немного сюрреалистично слышать, что разделение данных на несколько частей позволяет выявить лежащие в основе закономерности, обнаруженные в данных. Оказывается, проецирование данных в скрытое пространство заставляет результирующую матрицу обучаться шаблонам, отделяющим шум.
Существует множество различных алгоритмов MF, которые используют различные свойства результирующих факторизованных матриц. Некоторые могут ограничивать значения, чтобы они были неотрицательными, в то время как другие применяют разреженность. Поэтому алгоритм, который вы используете, будет определять характер получаемого вами результата. Мы увидим немало из них в нашем путешествии к его центру!
Покажите мне уже крутые штуки: Приложения MF
Возможно, вы уже устали слушать, как я постоянно говорю о MF. Пришло время увидеть эти алгоритмы в действии.
Сжатие изображения
Первый пример, который мы видим, — это сжатие изображений. Матричная факторизация может использоваться для хранения важного содержимого изображения, необходимого для его последующего восстановления (с меньшим объемом памяти). Здесь мы узнаем о методе, называемом разложением по сингулярным числам (SVD). Идея SVD состоит в том, чтобы представить матрицу A умножением трех матриц; U, Σ и V.
Здесь A — это n x m
, U — это n x n
, Σ — это n x m
, а V — это m x m
.
Матрица Σ представляет собой диагональную матрицу, которая содержит сингулярные значения на диагонали, что является важным побочным продуктом SVD. Эти сингулярные значения показывают, насколько вариативна для каждой строки/столбца U и V (или сингулярных векторов). Чем больше дисперсии вы зафиксируете, тем лучше будет реконструкция. Вы можете признать, что это тот же принцип, что и PCA.
Квадрат сингулярных значений пропорционален количеству информации, собранной (т.е. дисперсии) каждым сингулярным вектором.
Другая замечательная вещь заключается в том, что сингулярные значения упорядочены в порядке убывания. Это означает, что для получения p наиболее важных сингулярных значений вы просто обрезаете свои матрицы только для того, чтобы содержать столько сингулярных значений.
Существуют разные варианты СВД. Получение только самых больших сингулярных значений p без вычисления полной факторизации называется усеченным SVD. И более эффективный приближенный вариант этого известен как рандомизированный SVD. Вот что мы получаем при разном количестве компонентов для рандомизированного SVD.
Вот реализация в scikit-learn
.
Давайте вычислим сжатие для k=50
для изображения 512x512
.
- Исходное изображение = 512x512 = 262144 пикселей
- Реконструировано = 512x10 + 10x10 + 10x512 = 10340 пикселей (всего ~4% от исходного изображения)
Хороший! Мы только что реконструировали аппроксимацию, занимающую всего 4% памяти по сравнению с оригиналом. Полный сквозной код вы можете найти здесь.
Обнаружение переднего плана
Следующим на очереди у нас было обнаружение переднего плана. Если вы думали, что сжимать изображения — это круто, подождите, пока вы не увидите это! Вы можете разделить фон и передний план с помощью матричной факторизации 🤯*вставить потрясающий GIF*🤯. Подумайте об удивительных вещах, которые вы можете сделать в видеонаблюдении. Вы можете обнаружить людей или автомобили из видео. Давайте посмотрим, как это можно сделать.
Прежде всего, мы представляем наше видео в виде матрицы размера l x f
, где l
— длина одного кадра (т. е. высота и ширина кадра в градациях серого, развернутого в одномерный вектор), а f
— количество кадров в видео. В нашем случае у нас есть матрица размера 76800 x 794
(каждое изображение имеет размер 320x240=76800 пикселей).
Мы можем построить его и посмотреть, как он выглядит.
Волнистые линии, которые вы видите, — это движения людей, присутствующие в видео. Для этой задачи мы будем использовать другой метод матричной факторизации, называемый надежный PCA (rPCA). Идея состоит в том, чтобы разложить данную матрицу M на множители следующим образом.
Здесь L — приближение низкого ранга, а S — разреженная матрица. Холуп! 🛑 разве ты только что не сказал, что не собираешься запугивать нас отупляющей математикой? Итак, давайте интуитивно поймем, что это значит.
Ранг матрицы называется количеством линейно независимых столбцов. Столбец является линейно независимым, если он не может быть получен как линейное преобразование других столбцов в матрице. Почему это важно? Потому что чем больше линейно зависимых столбцов в матрице, тем больше избыточной информации, потому что вы получаете их из независимых. Если вы думаете о видеопотоке с камеры видеонаблюдения, фон статичен, поэтому содержит очень мало информации (или низкую энтропию). Таким образом, мы, вероятно, можем представить фон с небольшим количеством линейно независимых столбцов. Другими словами, если бы мне нужно было представить содержимое M как низкоранговую матрицу L, я бы зафиксировал в ней фон, присутствующий в M.
Примечание: в SVD количество ненулевых сингулярных значений представляет собой ранг этой матрицы.
Примером низкоранговой матрицы является статический фон видеопотока, представленный в виде матрицы.
Насчет разреженной матрицы. В этом было бы больше смысла. В видеопотоке статический фон будет содержать большую часть данных (данных, а не информации) с точки зрения объема. Оставшаяся разреженная информация относится к переднему плану, потому что передний план обычно занимает мало места в видео. Поэтому, если я попытаюсь заставить M стать разреженной матрицей S, я, вероятно, зафиксирую движения переднего плана в S. Другой способ думать, что S фиксирует выбросы в ваших данных!
Теперь сложение L и S должно дать нам исходное видео, о чем и говорит надежное уравнение PCA. Теперь легче сказать, чем сделать! Как мы на самом деле обеспечиваем эти свойства для этих матриц. Это выходит за рамки данной статьи. Но чтобы дать вам немного вкуса, вы можете использовать алгоритм, такой как Принципиальный компонент Метод преследования или переменного направления. Для rPCA я использовал и модифицировал исходный код, найденный здесь.
На высоком уровне давайте поймем, как мы можем оптимизировать эти специальные свойства.
Чтобы минимизировать ранг L, вы можете использовать ядерную норму L, которая является прокси для ранга. С другой стороны, если вы работали с линейной регрессией, вы, возможно, помните, что норма L1 поощряет разреженность в вашей матрице весов. Здесь используется тот же принцип, чтобы сделать S разреженной матрицей.
Глядя на 250-й кадр исходных frames_t
, L
и S
, мы получаем следующие три графика (по порядку).
А вот и видео.
Полный сквозной код доступен здесь.
Крутой трюк! Давайте проверим наши знания
На данный момент мы изучили две техники; СВД и rPCA. Мы также узнали, что в видео, организованных в виде матрицы, компонент низкого ранга захватывает фон.
Теперь в SVD есть такое интересное свойство, ранг равен количеству ненулевых сингулярных значений. Итак, что произойдет, если мы выполним усеченный SVD с несколькими компонентами (в нашем случае рандомизированный SVD) и реконструируем изображение?
Мы должны иметь возможность отделить фон. Тогда извлечение переднего плана тривиально. Просто вычтите пиксели фона из пикселей исходного изображения.
Выглядит неплохо. Мы можем видеть, что увеличение количества компонентов приводит к тому, что в реконструкции появляется больше переднего плана. Это довольно хороший пример того, насколько мощна интуиция, она позволяет уверенно и эффективно комбинировать разные техники, чтобы получить то, что вам нужно!
Но зачем тогда нам здесь нужен rPCA? Это ведет к дополнительным техническим деталям и выходит за рамки данного введения. Чтобы дать краткий ответ, разные алгоритмы имеют разные сильные и слабые стороны. И они не всегда выделяются в каждом конкретном случае использования. Одно очевидное отличие, которое я могу указать, заключается в том, что rPCA более устойчив к выбросам в данных.
До свидания
На этом я закончу нашу первую часть обсуждения. Сначала мы поняли, почему важны матрицы, что привело к тому, почему важна матричная факторизация. Затем мы обсудили два приложения компьютерного зрения; сжатие изображения и обнаружение переднего плана. Мы обсудили два алгоритма, SVD и rPCA, и даже проделали крутой трюк, адаптировав SVD для обнаружения переднего плана.
В следующей статье мы собираемся исследовать другие части области машинного обучения, где матричная факторизация правила (и правила)! Мы обсудим,
- Как матричная факторизация используется в НЛП для изучения понятий
- Как матричная факторизация используется для рекомендации товаров
А пока, до свидания!
Следующий пост
[TBA] Часть 2. Матричная факторизация
Дальнейшие чтения
[1] Курс fast.ai по линейной алгебре — Очень всесторонний рассказ о матричной факторизации и множестве приложений на Python.
[2] Разложение по сингулярным значениям
[4] Надежный ППШ