[БЕЗ_ЗВУКА] В этом уроке мы поговорим с вами про матричные разложения.
Мы уже затрагивали эту тему в самом первом курсе и сейчас выясним, как именно
матричные разложения можно будет применять в каких-то конкретных задачах.
Итак, сначала мы вспомним, что же такое матричные разложения,
после этого мы освежим в памяти, что такое сингулярное разложение
матриц и выясним, что это значит в машинном обучении.
После этого мы поговорим про использование разложения матриц в задачах рекомендаций,
затем в задачах анализа текстов и немножко обсудим особенности обозначения.
Итак, в задачах про матричные разложения мы пытаемся приблизить исходную
матрицу какого-то размера произведением двух других матриц.
При этом мы хотим, чтобы если исходная матрица была, например,
размера l на d, то матрица U была размера l на k,
матрица V транспонированное была размера k на d, причем k было чем-то небольшим.
То есть мы пытаемся получить вместо исходной матрицы X две матрицы U и V,
которые будут, по сути, представлять собой какое-то новое признаковое
описание объектов и изначальных признаков.
Как это можно записать?
Можно записать, что мы пытаемся приблизить X произведением U и V
транспонированное, то есть добиться того, чтобы норма разности была минимальна.
Но что за норма?
Какую норму можно ввести на матрице?
Например, можно ввести норму Фробениуса.
Корень из суммы квадратов элементов матрицы.
Если воспользоваться нормой Фробениуса,
то мы увидим, что вся эта задача выписывается в виде суммы по i и j,
квадрат отклонения xij от скалярного произведения ui на vj,
где ui — это новое описание i-го объекта, а vj — это новое описание j-го признака.
Давайте чуть подробнее разберемся с обозначениями.
Изначально мы имеем матрицу l на d, ее мы приближаем произведением матрицы
l на k — это матрица U, и матрицы размером k на d — это матрица V транспонированное.
Если мы посмотрим на элемент xij, то так как матрицы умножаются
— строка на столбец, понятно, что это будет произведение i-ой строки
матрицы U и j-го столбца матрицы V транспонированное.
Теперь вспомним про сингулярное разложение матриц.
Сингулярное разложение — это способ представить некоторую исходную матрицу в
виде произведения трех других матриц.
Ортогональной матрицы U,
диагональной матрицы Σ и ортогональной матрицы V транспонированное.
Геометрически это можно проиллюстрировать следующим образом.
Мы, конечно, об этом задумываемся не очень часто,
но любая матрица задает некоторое отображение, потому что мы можем
умножить некоторый вектор на эту матрицу и получить какой-то другой вектор.
И если мы рассмотрим матрицу X, как матрицу задающую некоторое отображение,
то можно это отображение разложить на составляющие,
то есть представить, что сначала мы как-то повернули пространство,
потом мы его растянули вдоль осей координат, а потом снова повернули.
На самом деле, говоря более точно, здесь могут быть не только повороты,
но и вращения некоторых осей,
но так или иначе в каком-то простом виде это все выглядит так.
Оказывается, что сингулярное разложение матриц может
быть полезно для нашей задачи приближения произведением двух матриц.
Действительно, давайте представим, что мы ее решаем, решаем по норме Фробениуса,
то есть по сумме квадратов отклонений.
И вот давайте рассмотрим сингулярное разложение
матрицы X на матрицу U «с волной», Σ и V «с волной» транспонированное.
Здесь мне пришлось прибегнуть к обозначениям U «с волной» и V «с
волной» чтобы не было пересечения с нашими обозначениями для разложения на
две матрицы.
Можно было бы выбрать какие-то другие обозначения,
но так получилось, что и обозначение для разложения на две матрицы,
и обозначение для сингулярного разложения достаточно хорошо прижилось.
Итак, мы можем понять, что мы получаем в этом сингулярном разложении.
Мы получаем представление произведением трех матриц.
Теперь давайте у каждой матрицы возьмем какую-то часть — от матрицы
U «с волной» возьмем первые k столбцов, от матрицы Σ возьмем квадрат размера k на k,
от матрицы V «с волной» транспонированное возьмем первые k строк.
И таким образом определим усеченные матрицы
из SVD — U «с волной» k-тое, Σ k-тое и V «с волной» k-тое.
Оказывается, если мы возьмем в качестве матрицы U U
«с волной» k-тое на Σ k-тое, а в качестве матрицы V — V «с
волной» k-тое — это будет решением нашей оптимизационной задачи.
Это действительно даст наилучшее приближение по норме Фробениуса,
это удивительное свойство SVD разложения.
При этом обратите внимание, мы могли бы отнести матрицу Σ и к матрице V, а
могли бы расписать — корень из Σ для одной матрицы и корень из Σ для другой матрицы.
Ну под корнем подразумевается такая же диагональная матрица,
только теперь взяты на диагонали не те же элементы, а корни из этих элементов.
Ну вот, это в целом указывает на неоднозначность решения
задачи матричного разложения, с которой мы еще будем
иметь в дальнейшем дело и которую еще вспомним не раз.
Так или иначе, часто оказывается,
что брать и выполнять SVD разложение — не очень быстрая операция,
и в принципе можно мыслить об этой задаче получения матриц U и V просто как самой
по себе задаче и оптимизации, и подбирать ui и vj,
то есть получаются некоторые профили объектов и профили исходных признаков
прямо из этой оптимизационной задачи каким-нибудь оптимизационным методом.
Поэтому SVD здесь с какой-то стороны уже ни при чем,
мы просто «в лоб» решаем эту задачу.
С другой стороны, мы помним, что здесь есть некоторая связь с SVD,
и если мы придумываем какое-то решением для этой задачи, примерно такое же решение
можно придумать для вычисления усеченных матриц из SVD.
Таким образом, в машинном обучении
прижилось SVD как матричное разложение по норме Фробениуса,
но на самом деле нужно понимать, что здесь речь идет не о сингулярном разложении
в обычном смысле, а именно о решении вот этой оптимизационной задачи.
Теперь перейдем к применению SVD в рекомендациях.
В рекомендациях мы обычно имеем матрицу пользователи-объекты,
и пользователи ставят какие-то оценки.
Ну вот пример такой матрицы сейчас вы видите на слайде.
Матрица заполнена не полностью,
и в целом довольно серьезный вопрос: а как же заполнить пропущенные места?
Можно вставить нули, можно оставить эти значения неизвестными и адаптировать
алгоритмы к этому, но так или иначе, если мы будем использовать матричные
разложения здесь, то i-тый j-тый элемент мы будем просто
приближать произведением профиля пользователя и профиля объекта.
В случае на слайде — профиля фильма.
Можно интерпретировать это как интересы пользователя и какие-то параметры фильма.
Хотя, конечно, интерпретировать полученные алгоритмические числа на практике,
то есть понять, что какое-то число соответствует количеству «экшена» фильма,
какое число соответствует длительности фильма, мелодраматичности его,
получается очень редко, даже, скорее, не получается.
Другой пример — это матрица частот слов.
Она часто встречается при анализе текстов, например, если нам нужно классифицировать
тексты, кластеризовать тексты, мы непременно построим такую матрицу.
И здесь мы снова имеем ситуацию,
когда на пересечении i-го и j-го столбца у нас есть некоторые значения, которые можно
приближать как скалярное произведение профиля документа и профиля термина.
В данном случае профиль можно интерпретировать как какие-то темы,
которым соответствует документ и которым соответствует термин.
Давайте еще немного поговорим про обозначения.
Дело в том, что здесь мы встречаем не просто представление матрицы
X в виде произведения U на V, а в виде произведения U на V транспонированное.
Возникает вопрос: а зачем понадобилось транспонировать?
Ну это просто некоторые эстетические соображения,
которые возникли из желания сделать так, чтобы и матрица U,
и матрица V представляла собой матрицу количества каких-то сущностей,
либо объектов, либо исходных признаков, на количество новых признаков k.
Тогда, если мы запишем,
что xij у нас приближается скалярным произведением ui на vj,
и вспомним, что обычно, когда мы говорим о скалярном произведении, мы имеем в виду
скалярное произведение векторов, а векторы мы обычно представляем столбцами,
становится понятно, почему можно встретить запись «xij
приближенно равно ui транспонированное на vj».
То есть это просто расписанное скалярное произведение,
сумма покоординатных произведений векторов.
Но эта же запись может вызвать вопросы.
Действительно, мы записываем таким образом,
для того чтобы передать мысль, что строка должна умножаться на столбец.
Следовательно, если нам нужно взять скалярное произведение
двух вектор-столбцов, нам нужно один из них транспонировать.
В то же время изначально ui — это строка в матрице U,
а не столбец, и vj — это строка в матрице V.
Конечно, не стоит путаться из-за этого и нужно понимать, что имеется в виду именно
покоординатное произведение ui и vj, которые были строчками в матрицах U и V.
На самом деле мы встречали аналогичную ситуацию,
когда говорили о линейных моделях.
Действительно, у нас была матрица признаков X,
и i-тый объект соответствовал i-той строке в матрице.
В то же время когда мы писали скалярное произведение вектора весов w на вектор xi,
иногда можно было расписывать — w транспонированное на xi.
Хотя xi действительно изначально было строчкой,
но в этой записи уже подразумевается столбец.
Кроме того, в матричных разложениях встречается много
различных обозначений в зависимости от того, для чего они применяются.
Часто в рекомендациях используются обозначения U и V для матриц,
на которые мы разлагаем исходную матрицу, а также встречаются обозначения P и
Q (тоже в рекомендациях), обозначения W и H часто используются в неотрицательных
матричных разложениях и в анализе текстов, и даже обозначения Φ и Θ, которые мы будем
использовать, когда будем говорить о вероятностных тематических моделях.
Мы могли бы выработать какое-то более-менее принятое в рамках
нашего курса обозначение, но тогда бы это могло вызвать какие-то сложности
при изучении соответствующих статей по той области, которая вас интересует.
Поэтому мы решили просто рассказать о том, что обозначения бывают разные,
и предупредить, что использовать мы тоже будем разные обозначения.
Итак, подведем итог.
Мы вспомнили, что такое матричные разложения, вспомнили,
что такое SVD в линейной алгебре, узнали, что такое SVD в машинном обучении
и что правильно будет говорить не SVD, а матричное разложение по норме Фробениуса.
Узнали, как можно применять SVD в рекомендациях,
как применяется SVD для анализа текстов,
и немножко поговорили про особенности обозначений.
В следующем видео мы узнаем,
а как же вычислить профили объектов и профили признаков.
Evgeniy Riabenko
Evgeny Sokolov
Victor Kantor
Emeli Dral
Константин Воронцовдоктор физико-математических наук, профессор
