Pull to refresh
0
Rating

Рекомендательные системы: SVD, часть I

Surfingbird corporate blog
Продолжаем разговор о рекомендательных системах. В прошлый раз мы сделали первую попытку определить схожесть между пользователями и схожесть между продуктами. Сегодня мы подойдём к той же задаче с другой стороны – попытаемся обучить факторы, характеризующие пользователей и продукты. Если Васе из предыдущего поста нравятся фильмы о тракторах и не нравятся фильмы о поросятах, а Петру – наоборот, было бы просто замечательно научиться понимать, какие фильмы «о поросятах», и рекомендовать их Петру, а какие фильмы – «о тракторах», и рекомендовать их Васе.

image

Напоминаю ещё раз (и, видимо, буду напоминать до конца времён), что у нас есть матрица, состоящая из рейтингов (лайков, фактов покупки и т.п.), которые пользователи (строки матрицы) присвоили продуктам (столбцы матрицы). Давайте присмотримся к матрице image, в которой записаны известные нам рейтинги. Как правило, один пользователь не сможет оценить значительную долю продуктов, и вряд ли будет много продуктов, которые готова оценить значительная доля пользователей. Это значит, что матрица R разреженная (sparse); нельзя ли этим как-нибудь воспользоваться?

Главным инструментом для нас станет так называемое сингулярное разложение матрицы R:
image
Сингулярное разложение – это достаточно простой, но очень мощный инструмент. Собственно, это один из главных с практической точки зрения результатов линейной алгебры, и результат уже весьма не новый (свойства SVD были изучены самое позднее в 1930-х годах), – и тем удивительнее бывает, когда университетские курсы линейной алгебры, довольно подробные в каких-то других аспектах, совершенно обходят SVD стороной.

Если у вас есть три минуты, можете насладиться ярким образчиком математического юмора; юмор, конечно, математический, так что не то чтобы смешно, но суть изложена доходчиво, а музыка наверняка понравится любителям… хм, на хабре, наверное, лучше будет сказать, что понравится любителям Fallout:


На случай, если трёх минут всё-таки не нашлось, я выделю главное для нас свойство: если R – матрица большого размера image, но малого ранга f (в частности, разреженные матрицы часто бывают малого ранга), её можно разложить в произведение матрицы image и матрицы image, тем самым резко сократив число параметров, c NM до (N+M)f (чтобы понять, что это большой прогресс, представьте, что, как это обычно бывает на практике, N и M измеряются сотнями тысяч и миллионами, а f меньше десятка).

SVD очень широко употребляется в машинном обучении; фактически, если вы хотите что-то чем-то приблизить, не исключено, что вам где-то по дороге встретится SVD. Классический пример применения SVD – шумоподавление, например, в изображениях. Рассмотрим (чёрно-белое) изображение как матрицу X размера image, элементы которой – интенсивности каждого пикселя. Теперь попробуем выбрать f столбцов пикселей из изображения, счесть их «репрезентативными» и представить каждый из оставшихся столбцов в виде линейной комбинации этих. Я не буду сейчас углубляться в математику, но в результате, когда вы найдёте оптимальные представления каждого столбца, получится, что вы представили исходную матрицу в виде произведения image матриц размера image и image, то есть как раз приблизили матрицу X матрицей малого ранга f.

Основное же свойство SVD – в том, что SVD даёт оптимальное такое приближение, если в матрице D просто оставить ровно f первых диагональных элементов, а остальные занулить:
image
В диагональной матрице D, которая в середине сингулярного разложения, элементы упорядочены по размеру: image, так что обнулить последние элементы – это значит обнулить наименьшие элементы.

Если хорошо подобрать f, то в результате изображение и в весе потеряет, и шума на нём станет меньше. А f в данном случае можно подбирать, исходя из размера сингулярных значений матрицы, т.е. тех самых диагональных элементов матрицы D: желательно отбрасывать как можно больше, но при этом как можно более маленьких таких элементов.

Но мы отвлеклись. В случае рекомендательных систем получается, что мы представляем каждого пользователя вектором из f факторов image и представляем каждый продукт вектором из f факторов image, а потом, чтобы предсказать рейтинг пользователя i товару j, берём их скалярное произведение image. Можно сказать, что вектор факторов пользователя показывает, насколько пользователю нравится или не нравится тот или иной фактор, а вектор факторов продукта показывает, насколько тот или иной фактор в продукте выражен. Линейная же алгебра подсказывает нам, что для разреженной матрицы рейтингов такое разложение часто возможно и имеет содержательный смысл.

Может оказаться, кстати, что некоторые факторы легко будет понять человеческим умом: для фильмов может выделиться что-нибудь в духе «комедия–драма», «доля action'а», «доля романтики» и т.п., а факторы пользователей, соответственно, будут показывать, насколько соответствующие характеристики фильма им по вкусу. Но может и не выделиться ничего содержательного – тут гарантий нет, формально мы просто жонглируем цифрами.

В следующий раз мы превратим эту базовую идею – приблизить матрицу рейтингов матрицей малого ранга посредством SVD – в хорошо поставленную задачу оптимизации и научимся её решать.
Tags:
Hubs:
Total votes 17: ↑15 and ↓2 +13
Views 53K
Comments Comments 5

Information

Location
Россия
Website
surfingbird.ru
Employees
11–30 employees
Registered