Продолжаем разговор о рекомендательных системах. В прошлый раз мы сделали первую попытку определить схожесть между пользователями и схожесть между продуктами. Сегодня мы подойдём к той же задаче с другой стороны – попытаемся обучить факторы, характеризующие пользователей и продукты. Если Васе из предыдущего поста нравятся фильмы о тракторах и не нравятся фильмы о поросятах, а Петру – наоборот, было бы просто замечательно научиться понимать, какие фильмы «о поросятах», и рекомендовать их Петру, а какие фильмы – «о тракторах», и рекомендовать их Васе.
Напоминаю ещё раз (и, видимо, буду напоминать до конца времён), что у нас есть матрица, состоящая из рейтингов (лайков, фактов покупки и т.п.), которые пользователи (строки матрицы) присвоили продуктам (столбцы матрицы). Давайте присмотримся к матрице 
, в которой записаны известные нам рейтинги. Как правило, один пользователь не сможет оценить значительную долю продуктов, и вряд ли будет много продуктов, которые готова оценить значительная доля пользователей. Это значит, что матрица R разреженная (sparse); нельзя ли этим как-нибудь воспользоваться?
Главным инструментом для нас станет так называемое сингулярное разложение матрицы R:
Сингулярное разложение – это достаточно простой, но очень мощный инструмент. Собственно, это один из главных с практической точки зрения результатов линейной алгебры, и результат уже весьма не новый (свойства SVD были изучены самое позднее в 1930-х годах), – и тем удивительнее бывает, когда университетские курсы линейной алгебры, довольно подробные в каких-то других аспектах, совершенно обходят SVD стороной.
Если у вас есть три минуты, можете насладиться ярким образчиком математического юмора; юмор, конечно, математический, так что не то чтобы смешно, но суть изложена доходчиво, а музыка наверняка понравится любителям… хм, на хабре, наверное, лучше будет сказать, что понравится любителям Fallout:
На случай, если трёх минут всё-таки не нашлось, я выделю главное для нас свойство: если R – матрица большого размера 
, но малого ранга f (в частности, разреженные матрицы часто бывают малого ранга), её можно разложить в произведение матрицы 
и матрицы 
, тем самым резко сократив число параметров, c NM до (N+M)f (чтобы понять, что это большой прогресс, представьте, что, как это обычно бывает на практике, N и M измеряются сотнями тысяч и миллионами, а f меньше десятка).
SVD очень широко употребляется в машинном обучении; фактически, если вы хотите что-то чем-то приблизить, не исключено, что вам где-то по дороге встретится SVD. Классический пример применения SVD – шумоподавление, например, в изображениях. Рассмотрим (чёрно-белое) изображение как матрицу X размера 
, элементы которой – интенсивности каждого пикселя. Теперь попробуем выбрать f столбцов пикселей из изображения, счесть их «репрезентативными» и представить каждый из оставшихся столбцов в виде линейной комбинации этих. Я не буду сейчас углубляться в математику, но в результате, когда вы найдёте оптимальные представления каждого столбца, получится, что вы представили исходную матрицу в виде произведения 
матриц размера 
и 
, то есть как раз приблизили матрицу X матрицей малого ранга f.
Основное же свойство SVD – в том, что SVD даёт оптимальное такое приближение, если в матрице D просто оставить ровно f первых диагональных элементов, а остальные занулить:
В диагональной матрице D, которая в середине сингулярного разложения, элементы упорядочены по размеру: 
, так что обнулить последние элементы – это значит обнулить наименьшие элементы.
Если хорошо подобрать f, то в результате изображение и в весе потеряет, и шума на нём станет меньше. А f в данном случае можно подбирать, исходя из размера сингулярных значений матрицы, т.е. тех самых диагональных элементов матрицы D: желательно отбрасывать как можно больше, но при этом как можно более маленьких таких элементов.
Но мы отвлеклись. В случае рекомендательных систем получается, что мы представляем каждого пользователя вектором из f факторов 
и представляем каждый продукт вектором из f факторов 
, а потом, чтобы предсказать рейтинг пользователя i товару j, берём их скалярное произведение 
. Можно сказать, что вектор факторов пользователя показывает, насколько пользователю нравится или не нравится тот или иной фактор, а вектор факторов продукта показывает, насколько тот или иной фактор в продукте выражен. Линейная же алгебра подсказывает нам, что для разреженной матрицы рейтингов такое разложение часто возможно и имеет содержательный смысл.
Может оказаться, кстати, что некоторые факторы легко будет понять человеческим умом: для фильмов может выделиться что-нибудь в духе «комедия–драма», «доля action'а», «доля романтики» и т.п., а факторы пользователей, соответственно, будут показывать, насколько соответствующие характеристики фильма им по вкусу. Но может и не выделиться ничего содержательного – тут гарантий нет, формально мы просто жонглируем цифрами.
В следующий раз мы превратим эту базовую идею – приблизить матрицу рейтингов матрицей малого ранга посредством SVD – в хорошо поставленную задачу оптимизации и научимся её решать.
Автор: snikolenko
