Леха Захаров – «Слив топа Литрес» (страница 5)
Кульминацией же интереса к этой технологии стал Netflix Prize 2006 года. Стриминговый сервис пообещал 1 миллион долларов тому, кто сможет улучшить точность их собственной рекомендательной системы Cinematch на 10%. Этот конкурс привлёк тысячи исследователей и инженеров со всего мира, породил целый шквал инноваций в области матричного разложения и привёл к созданию гибридных моделей, которые до сих пор лежат в основе многих современных систем.
Любая коллаборативная модель начинается со сбора данных. Эти данные делятся на два типа, каждый из которых имеет свои преимущества и недостатки.
Явная обратная связь (Explicit Feedback) — это прямые действия пользователя, выражающие его мнение. Звёздный рейтинг на «ЛитРес» — самый яркий пример. Другие формы — лайки, дизлайки, написанные рецензии. Плюсы явной обратной связи в том, что она даёт чёткий и понятный сигнал: 5 звёзд — «мне очень нравится», 1 звезда — «это ужасно». Однако у неё есть два серьёзных недостатка. Во-первых, пользователи неохотно оценивают каждый товар. На «ЛитРес», как и на любом другом сервисе, абсолютное большинство книг, которые вы читаете, вы не оцениваете. Матрица «пользователь-товар» оказывается чудовищно разреженной. Во-вторых, явная обратная связь подвержена систематическим ошибкам: одни пользователи ставят 5 звёзд всему, что прочитали, другие — никогда не ставят выше 3.
Неявная обратная связь (Implicit Feedback) стала настоящим спасением для современных рекомендательных систем. Она включает в себя всевозможные действия пользователя, которые косвенно указывают на его предпочтения. На «ЛитРес» это:
Покупка книги — сильный, но не абсолютный сигнал (можно купить в подарок или по ошибке).
Факт прочтения — гораздо более надёжный сигнал.
Дочитывание до конца — самый сильный сигнал из возможных.
Время, проведённое на странице книги (долгое чтение = интерес).
Добавление в избранное, цитирование, репост.
Прокрутка страницы и клики.
Преимущество неявной обратной связи в её объёме и дешевизне. В отличие от звёздного рейтинга, эти данные собираются автоматически для каждого пользовательского сеанса. Проблема же в том, что эти сигналы неоднозначны. Покупка книги, которая так и не была прочитана, может означать всё что угодно: от разочарования до банальной нехватки времени. Поэтому современные алгоритмы, такие как ALS (Alternating Least Squares), специально адаптированы для работы с такими данными.
Независимо от того, использует система явную или неявную обратную связь, существует два фундаментальных подхода к поиску сходства.
Этот подход отвечает на вопрос: «Какие пользователи похожи на меня?»
Представьте себе многомерное пространство, в котором каждый пользователь — это точка, а координаты точки — это оценки, которые он поставил книгам. Алгоритм user-based находит пользователей, чьи векторы оценок наиболее близки к вашему. Обычно для этого используется метод k-ближайших соседей (k-NN), который находит k самых похожих на вас читателей.
Затем, чтобы сформировать рекомендацию, система смотрит на то, какие книги нравятся этим «соседям», но которые вы ещё не читали. Чем больше похожих пользователей оценили книгу высоко, и чем выше их сходство с вами, тем выше будет предсказанная оценка для вас.
Пример: Вы — поклонник твёрдой научной фантастики. Другой пользователь, Алиса, имеет с вами 90% совпадений в оценках по книгам Айзека Азимова, Артура Кларка и Филипа Дика. Система обнаруживает, что Алиса в восторге от романа «Слепое видение» Питера Уоттса, которого вы не читали. С большой вероятностью, этот роман будет вам рекомендован. Именно так работает принцип «друг читает то же, что и вы».
Преимущества UBCF:
Эффективен, когда пользователей относительно немного, а у каждого из них есть достаточно много оценок.
Способен предлагать неожиданные, «сёрендипные» находки (serendipity), которые могут выходить за рамки вашего обычного жанра.
Недостатки UBCF:
Плохо масштабируется: поиск похожих пользователей среди миллионов требует огромных вычислительных мощностей.
Страдает от проблемы «холодного старта» для новых пользователей (у которых ещё нет оценок).
Вкусы пользователей меняются со временем, и «сосед», который был похож на вас год назад, сегодня может им не быть.
Этот подход, напротив, отвечает на вопрос: «Какие книги похожи на те, что мне понравились?»
Здесь система ищет сходство не между пользователями, а между товарами. Она строит матрицу похожести книг: если пользователи часто покупают книгу А вместе с книгой Б, то между этими книгами возникает сильная связь. И как только вы прочитали книгу А, система автоматически рекомендует вам книгу Б. Именно этот подход лежит в основе знаменитого блока «Читатели, купившие эту книгу, также купили...» на Amazon.
Пример: На «ЛитРес» замечена сильная корреляция: 80% пользователей, купивших «Сто лет одиночества» Габриэля Гарсиа Маркеса, также купили «Игру в классики» Хулио Кортасара. Если вы купили Маркеса, система, не зная о ваших вкусах почти ничего, смело порекомендует вам Кортасара.
Преимущества IBCF:
Гораздо лучше масштабируется, так как количество товаров обычно стабильнее и меньше количества пользователей.
Менее чувствителен к смене вкусов: матрица похожести книг обновляется медленнее, чем профили пользователей.
Легче интерпретируем: «Вам рекомендуют эту книгу, потому что вы читали вот эту».
Недостатки IBCF:
Может привести к «пузырю фильтров»: вы будете получать рекомендации, очень похожие на то, что уже читали, и реже открывать для себя что-то совершенно новое.
Требует достаточного количества данных о совместных покупках. Для новой книги, которую ещё никто не покупал, связи построить невозможно («холодный старт»).
Поиск ближайших соседей (k-NN) — это мощный, но «жадный» алгоритм. Он требует попарного сравнения каждого пользователя с каждым или каждого товара с каждым, что для масштабов «ЛитРес» нереалистично. Именно поэтому современные системы используют модель, основанную на матричном разложении (Matrix Factorization).
Идея матричного разложения проста: представить огромную и разреженную матрицу «пользователи-книги» (в которой 99% ячеек пусты) как произведение двух (или более) матриц меньшего размера.
Представьте, что у каждого пользователя и каждой книги есть свой
Профиль пользователя — это вектор (список) из 100 чисел, описывающих его вкус в этом многомерном пространстве. Профиль книги — это тоже вектор из 100 чисел, описывающих её «вкусовую геометрию». Предсказанная оценка — это просто скалярное произведение этих двух векторов. Если векторы сонаправлены (пользователь и книга «подходят» друг другу), произведение будет большим; если ортогональны (пользователю это неинтересно) — маленьким.
Задача алгоритма — подобрать эти профили (векторы) для всех пользователей и всех книг так, чтобы предсказанные оценки максимально совпадали с реальными (где они есть). Но как это сделать, когда большинство реальных оценок неизвестны? Здесь на сцену выходит ALS (Alternating Least Squares) — метод, который итеративно решает эту задачу.
Алгоритм ALS работает следующим образом:
Инициализация: Профилям книг случайным образом присваиваются небольшие числа.
Шаг 1: Фиксируем профили книг и решаем задачу наименьших квадратов, чтобы найти оптимальные профили пользователей.
Шаг 2: Фиксируем новые профили пользователей и решаем задачу наименьших квадратов, чтобы найти оптимальные профили книг.
Повторение: Эти шаги повторяются (alternating) многократно, пока профили не сойдутся к оптимальным значениям.
Прелесть ALS в том, что он позволяет эффективно работать с
Почему коллаборативная фильтрация стала доминирующим подходом в индустрии? У неё есть несколько ключевых преимуществ:
Не требует знания предметной области (No domain knowledge necessary). Чтобы предсказать, понравится ли вам книга, системе не нужно знать, что такое «сюжет», «стиль» или «атмосфера». Она просто находит математические закономерности в ваших действиях и действиях других людей. Это делает алгоритм универсальным: его можно обучить на данных о фильмах, музыке, книгах или товарах, практически не меняя код.
Способность к «сёрендипности» (Serendipity). Контентная фильтрация (о которой мы поговорим позже) рекомендует вам то, что «похоже» на то, что вы уже потребляли: тот же жанр, того же автора. Коллаборативная фильтрация может найти скрытые, неочевидные связи. Она может порекомендовать вам книгу совершенно незнакомого автора в жанре, который вы обычно не читаете, потому что другие пользователи с вашими вкусами её полюбили.