что такое рекомендательная система
Знакомство с рекомендательными системами
Давайте вернемся к периодически затрагиваемой у нас теме машинного обучения и нейронных сетей. Сегодня речь пойдет об основных типах рекомендательных систем, их достоинствах и недостатках. Под катом — интересная статья Тоби Дейгла с кодом на Python,
Над катом — ссылка на большую презентацию нашего замечательного автора Сергея Николенко, чью книгу «Глубокое обучение. Погружение в мир нейронных сетей», написанную в соавторстве с Артуром Кадуриным и Екатериной Архангельской, мы просто не успеваем допечатывать. В презентации описаны основные типы рекомендательных систем и принципы их работы.
Читаем и комментируем!
Многие получают советы, но лишь мудрые в состоянии ими воспользоваться. — Харпер Ли
Рекомендательные системы кажутся многим волшебными артефактами, словно читающими наши мысли. Вспомните хотя бы рекомендательный движок Netflix, подсказывающий нам новые фильмы, или сервис Amazon, предлагающий нам товары, которые могут понравиться. С самого зарождения такие инструменты совершенствовались и оттачивались, пользоваться ими становилось все удобнее. Но, пусть многие из рекомендательных движков — очень сложные системы, фундаментально их устройство весьма незамысловато.
Что такое рекомендательная система?
Рекомендательные движки — это подсемейство систем для фильтрации контента, предоставляющих пользователю те элементы, которые могли бы его заинтересовать. Рекомендации подбираются на основе преференций и поведения пользователя. Система должна спрогнозировать вашу реакцию на тот или иной элемент – и предложить другие, которые также могут вам понравиться.
Как создать рекомендательную систему?
Хотя, при программировании рекомендательных систем применяется множество методов, расскажу вам о трех самых простых, которые используются чаще всего. Речь пойдет о коллаборативной фильтрации (collaborative filtering), контентная фильтрация (content-based filtering) и, наконец, экспертные системы (knowledge-based systems). По каждой системе я опишу ее слабые места, потенциальные подводные камни и расскажу, как их обходить. Наконец, в финале статьи я приведу полноценную реализацию рекомендательного движка.
Первый из рассматриваемых методов, коллаборативная фильтрация — один из простейших и наиболее эффективных. Этот трехэтапный процесс начинается со сбора пользовательской информации. Затем выстраивается матрица для расчета ассоциаций и, наконец, дается весьма достоверная рекомендация. Существует две основные разновидности этого метода: на основе пользователей, занимающихся поиском, и на основе элементов, образующих ту или иную категорию.
Пользовательская коллаборативная фильтрация
Идея, на которой основан этот метод – искать пользователей, чьи вкусы похожи на предпочтения нашего целевого пользователя. Если ранее Жан-Пьер и Джейсон проставили схожие оценки нескольким фильмам, то мы считаем, что вкусы у них подобны, и по рейтингам тех или иных фильмов, проставленным Жаном-Пьером, можем угадать неизвестные рейтинги Джейсона. Например, если Жану-Пьеру понравились фильмы «Возвращение джедая» и «Империя наносит ответный удар», а Джейсону понравился фильм «Возвращение джедая», то мы определенно должны подсказать Джейсону и фильм «Империя наносит ответный удар». В принципе, для прогнозирования интересов Джейсона нужно найти несколько пользователей, с которыми у него схожие вкусы.
В таблице, где каждый ряд соответствует пользователю, а каждый столбец – фильму, просто найти сходство между рядами в матрице и, соответственно, подыскать пользователей с общими интересами.
Однако, такая реализация сопряжена с рядом проблем:
Процесс прост. Сходство двух элементов рассчитывается по рейтингам, выставленным пользователем. Вернемся к примеру с Жаном-Пьером и Джейсоном — как мы помним, обоим понравились фильмы «Возвращение джедая» и «Империя наносит ответный удар». Можно сделать вывод, что большинству пользователей, высоко оценивших первый фильм, должен понравиться и второй. Таким образом, было бы релевантно предложить фильм «Империя наносит ответный удар» Ларри, которому понравился фильм «Возвращение джедая».
Следовательно, сходство вычисляется по столбцам, а не по строкам (как понятно из матрицы с пользователями и фильмами, приведенной выше). Зачастую предпочитается именно коллаборативная фильтрация по элементам, так как она лишена всех недостатков, присущих пользовательской фильтрации. Во-первых, элементы в системе (здесь — фильмы) не изменяются со временем, поэтому рекомендации получатся более релевантными. Кроме того, элементов обычно гораздо меньше, чем пользователей, поэтому обработка данных при такой фильтрации происходит быстрее. В конечном итоге, такие системы гораздо сложнее обмануть.
Контентная рекомендательная система
В контентных рекомендательных системах рекомендации формулируются на основе атрибутов, присваиваемых каждому элементу. Термин «контент» относится именно к этим описаниям. Например, если изучить историю музыкальных интересов Софи, можно заметить, что ей нравится жанр кантри. Следовательно, система может рекомендовать ей композиции в стиле кантри, а также композиции схожих жанров. Более сложные системы в состоянии выявлять соотношения между множественными атрибутами и давать более качественные рекомендации. Так, на сайте Music Genome Project каждая композиция, имеющаяся в базе данных, категоризируется по 450 различным атрибутам. Именно на основе этого движка работает музыкальная рекомендательная система на сайте Pandora.
Экспертные рекомендательные системы
Экспертные рекомендательные системы особенно хороши для работы с такими элементами, которые приобретаются нечасто – например, дома, автомобили, финансовые активы или дорогие предметы роскоши. В таких случаях рекомендательный процесс осложняется из-за дефицита рейтингов по товарам. В экспертных системах рекомендации предлагаются не на основе рейтингов, а на базе сходства между пользовательскими требованиями и описанием продукта, либо в зависимости от ограничений, выставляемых пользователем при конкретизации желаемого продукта. Поэтому система такого типа получается уникальной, ведь она позволяет клиенту явно указать, чего он хочет. Что касается ограничений – в случаях, когда они вообще применяются – обычно такие ограничения известны с самого начала и реализуются экспертами в данной предметной области. Например, если пользователь явно указывает, что ищет недвижимость в данной ценовой категории, то система должна ориентироваться на данную спецификацию при подборе вариантов.
Проблема холодного старта в рекомендательных системах
Одна из важнейших проблем, связанных с рекомендательными системами, заключается в том, что исходное количество доступных рейтингов обычно невелико. Что делать, если новоиспеченный пользователь пока не рейтинговал фильмов, либо, если в систему добавился новый фильм? В таких случаях затруднительно применять традиционные модели коллаборативной фильтрации. Контентные методы и экспертные системы справляются с проблемой холодного старта увереннее коллаборативных моделей, но и они не всегда есть в распоряжении. Поэтому именно для таких случаев был разработан ряд альтернативных решений – например, гибридные системы.
Гибридные рекомендательные системы
Итак, у всех разнообразных рекомендательных систем, рассмотренных выше, есть свои достоинства и недостатки, и предлагаемые этими системами варианты базируются на разных исходных данных. Некоторые рекомендательные движки, в частности, экспертные системы, наиболее эффективны в контекстах, где количество доступных данных ограничено. Другие системы, например, коллаборативная фильтрация, лучше всего работают в средах, где имеются большие массивы данных. Зачастую, когда данные диверсифицированы, мы располагаем достаточной гибкостью, чтобы решать одну и ту же задачу разными методами. Следовательно, можно скомбинировать рекомендации, полученные несколькими способами, тем самым повысив качество системы в целом. Исследовано множество комбинаторных приемов, в том числе:
Рекомендательные системы часто используются в контексте искусственного интеллекта. Возможность выдачи подсказок, прогнозирования событий и подчеркивание корреляций – все это результаты применения ИИ. С другой стороны, при воплощении рекомендательных систем часто используются приемы машинного обучения. Например, компания Arcbees написала эффективный рекомендательный движок, работающий на основе нейронных сетей и данных, которые берутся из IMdB. Нейронные сети позволяют быстро решать сложные задачи и с легкостью манипулировать большими данными. Взяв в качестве ввода список фильмов, и сопоставив вывод с пользовательскими оценками, сеть может усвоить правила и затем руководствоваться ими, прогнозируя дальнейшие рейтинги, которые может проставить конкретный пользователь.
Читая материалы по этой теме, я нашел два отличных совета от экспертов. Во-первых, базовым материалом для работы рекомендательного движка должны быть такие элементы, за которые пользователи готовы платить. В таком случае можно быть уверенным, что оценки выставляемые пользователями, будут довольно точными и релевантными. Во-вторых, всегда лучше опираться на совокупности алгоритмов, а не на единственный алгоритм. Хороший пример — Netflix Prize.
Реализация рекомендательной системы на основе подбора элементов
В следующем коде показано, как легко и быстро можно реализовать рекомендательный движок, в котором используется коллаборативная фильтрация. Код написан на Python, здесь использованы библиотеки Pandas и Numpy – одни из самых популярных в данном сегменте. В качестве массива данных использовались рейтинги фильмов, а само множество данных доступно на MovieLens.
Этап 1: Находим похожие фильмы
Выбираем кино и генерируем индекс схожести (корреляции) между этим фильмом и всеми остальными
Удаляем непопулярные фильмы, чтобы система не подкидывала нам неподходящих рекомендаций
Извлекаем популярные фильмы, похожие на целевой
Этап 2: предлагаем пользователю рекомендации в зависимости от проставленных им оценок
Генерируем индекс схожести в каждой паре фильмов и оставляем только популярные
Генерируем рекомендации для каждого фильма, просмотренного и оцененного нашим пользователем (здесь – данные для пользователя 0)
Суммируем показатели идентичных фильмов
Оставляем лишь те фильмы, которые пользователь еще не смотрел
В вышеприведенном случае нам вполне удалось обработать множество данных MovieLens при помощи библиотеки Pandas на обычном процессоре. Однако, обработка более крупных наборов данных может занимать больше времени. В таких случаях могут помочь более мощные решения – например, Spark или MapReduce.
Рекомендательные системы: как помочь пользователю найти то, что ему нужно?
Рекомендательные системы стали настоящим бумом и сегодня представить какую-нибудь условную Lamoda без блока «Возможно, вас заинтересуют другие товары» сложно. Мы подготовили для вас подробную статью о том, что собой представляют рекомендательные системы и какую пользу они могут принести бизнесу.
Что такое рекомендательные системы?
Рекомендательная система — комплекс алгоритмов, программ и сервисов, задача которого предсказать, что может заинтересовать того или иного пользователя. В основе работы лежит информация о профиле человека и иные данные.
Яркий пример рекомендательной системы — Tik-Tok, о котором в последнее время говорят очень много. Первые несколько дней пользователи видят в ленте все подряд, но потом приложение показывает пользователю только интересующее его видео на основе предыдущих оценок.
Даже музыкальные приложения не обходятся без рекомендательных систем. Одной из лучших обладает Spotify, которое недавно «пришло» в Россию. Через несколько дней после установки программа подбирает для пользователя треки, которые с высокой долей вероятности заинтересуют его.
Типы рекомендательных систем
Существует 4 чипа рекомендательных систем:
Коллаборативная фильтрация (collaborative filtering).
Основанные на контенте (content-based).
Основанные на знаниях (knowledge-based).
Давайте подробнее рассмотрим каждый из них.
Коллаборативная фильтрация (collaborative filtering)
Рекомендации основаны на истории оценок как самого пользователя, так и других. Во втором случае системы рассматривают потребителей, оценки или интересы которых похожи на ваши.
Простой пример: Гена и Витя любят рыбачить и заказывать пиццу по вечерам. А еще они оба любят BMW и ездят на машинах этой марки. Еще есть Олег, который тоже не прочь посидеть с удочкой на выходных и заказать пиццу после тяжелого рабочего дня. Но о покупке BMW он никогда не задумывался. Так как его интересы (оценки) совпадают с Геной и Витей, ему можно порекомендовать BMW.
По такому принципу работает много сервисов, например, Имхонет или last.fm. Главное преимущество этого типа — высокая теоретическая точность. Но есть и минус: показывать хорошие рекомендации новым пользователям не получится, ведь о них нет никакой информации. Из-за этого будет большой процент отказов.
Основанные на контенте (content-based)
Этот тип лежит в основе многих рекомендательных систем. В отличие от коллаборативной фильтрации, этап знакомства с пользователем опускается. Товары и услуги рекомендуются на основе знаний о них: жанр, производитель, конкретные функции и т.п. В общем, применяют любые данные, которые можно собрать.
По такому принципу работают системы интернет-магазинов, онлайн-кинотеатров и других сервисов. Например, IVI выстраивает рекомендации по жанрам, странам-производителям фильмов, актерам и т.п.
Создатели платформ используют этот тип систем, чтобы не потерять новых пользователей, данных о которых еще нет. Отсюда же вытекают два недостатка: первое время системы действуют неточно и требуется больше времени на реализацию.
Основанные на знаниях (knowledge-based)
Этот тип работает на основе знаний о какой-то предметной области: о пользователях, товарах и других, которые могут помочь в ранжировании. Как и в случае с «content-based», оценки других пользователей системы не учитывают. Есть несколько разновидностей: case-based, demographic-based, utility-based, critique-based, whatever-you-want-based и т.д.
На самом деле количество подтипов ограничено фантазией создателей. При реализации нового проекта в зависимости от сферы деятельности в рекомендательную систему можно заложить любую предметную область и ранжировать по ней.
Например, магазин техники Apple «reStore» подбирает потенциальным покупателям наборы, в зависимости от просматриваемого товара:
Неплохо работает аналогичная система в интернет-магазине М.Видео:
При выборе новой игровой консоли PS4 посетителю сайта предлагают купить дополнительные геймпады, шлем виртуальной реальности, популярные игры и другие сопутствующие товары. Как итог, человек совершает больше покупок и увеличивает прибыль компании.
Очевидное преимущество системы — высокая точность. Рекомендательная система М.Видео показывает товары, которые могут реально заинтересовать посетителя. Было бы странно, если при выборе PlayStation 4 магазин советовал докупить человеку кухонный гарнитур.
Но есть и минус — для разработки этой системы требуется много времени и ресурсов. Но результат оправдывает средства.
Гибридные (hybrid)
Наверно, нет такой сферы деятельности, в которой не нашлось бы энтузиастов собрать «все в одно». Рекомендательные системы не стали исключением. У всех описанных ранее типов есть определенные недостатки. Комбинирование нескольких алгоритмов в рамках одной платформы позволяет если не устранить их полностью, то хотя бы минимизировать.
Крупные сервисы и интернет-магазины используют гибридные варианты. Чуть-чуть там, немного здесь и получается уникальная система. Универсальной инструкции и рекомендаций по реализации такого инструмента нет. Все ограничивается возможностями и фантазией разработчиков. Например, у Netflix в рекомендательной системе объединено 27 (!) алгоритмов.
Есть несколько распространенных типов комбинирования:
реализация по отдельности коллаборативных и контентных алгоритмов и объединение их предположений;
включение некоторых контентных правил в коллаборативную методику;
включение некоторых коллаборативных правил в контентную методику;
построение общей модели, включающей в себя правила обеих методик.
Обычно эти варианты берут в качестве основы и дополняют по собственному желанию и по критериям сферы деятельности. Как и в случае с knowledge-based, основной недостаток гибридных систем — сложность разработки.
Как работают рекомендательные системы
С назначением рекомендательных систем разобрались — они предлагают клиентам те товары и/или услуги, которые заинтересуют их с большей вероятностью. С разновидностями тоже все понятно, поэтому теперь поговорим об основных принципах деятельности и сферах применения.
Рекомендательные системы работают на двух уровнях:
Глобальные оценки; особенности и предпочтения, не меняющиеся месяцами или годами; интересные страницы; зависимость от характерных пользовательских черт: пол, место проживания и т.п.
Кратковременные тренды и быстрые изменения интересов во времени.
Данные собирают «явным» и/или «неявным» способами. В первом случае посетителю предлагают заполнять анкеты, проходить опросы и т.п. для определения его предпочтений. Метод эффективный, только пользователи не всегда соглашаются на заполнение анкет и прохождение опросов. Поэтому придумывают, как заинтересовать их этим (обычно предлагают какую-то выгоду в обмен).
Второй метод предусматривает фиксирование поведения потребителя на сайте или в приложении: какие страницы/разделы посмотрел, что добавлял в корзину, какие и где оставлял комментарии и т.п. При правильной организации сбора данных и дальнейшей аналитике метод дает хорошие результаты. Но и здесь есть ряд сложностей. Во-первых, просмотр отдельных страниц или карточек товара не дает сведений, понравилось ли в конечном итоге человеку предложение. Во-вторых, даже если совершена покупка, сложно предположить, что конкретно подтолкнуло человека к ее совершению.
Как и в случае с типами рекомендательных систем, по отдельности способы используют редко. Для получения наилучших результатов их комбинируют.
Грамотно настроенный сбор информации позволяет сделать рекомендации релевантными. С их помощью сокращается время поиска нужных товаров или услуг, а также повышается вероятность совершения сопутствующих целевых действий. Например, потребитель хотел купить только смартфон, но в результате дополнительно приобрел чехол для него. Когда потребитель тратит минимум времени для поиска нужных вещей и получает желанное, его лояльность к платформе повышается.
Еще один важный момент в работе рекомендательных систем, который стоит учитывать — соблюдение конфиденциальности. Они могут спрогнозировать такие результаты и выявить такие закономерности, о которых пользователь даже не задумывался или не хотел, чтобы это стало кому-то известно.
Что касается сфер применения рекомендательных систем, то здесь, по сути, ограничений никаких нет. Ранее мы уже не раз говорили, что все зависит от фантазии разработчиков. Их можно использовать в приложениях, интернет-магазинах, онлайн-кинотеатрах и других сервисах, которые предлагают какой-то контент, товары или услуги.
Любая компания, даже небольшой интернет-магазин диванов из региона, должна использовать рекомендательные системы. Они помогут в удержании текущих потребителей, привлечении новых и повышении прибыли.
Мифы о рекомендательных системах
К использованию рекомендательных систем пока что в основном прибегают крупные компании с большими запасами ресурсов. В среде малого и среднего бизнеса они медленно набирают популярность из-за ряда заблуждений.
Сложно собрать и подготовить данные для ИИ
Для работы рекомендательной системы собирают DataSet и информацию о продажах за последние несколько месяцев или лет. Если в деятельность сервиса или интернет-магазина внедрена онлайн-касса, то вопрос о накоплении нужных данных решен. Остается привести их в должный вид и начать применять на практике.
ИИ не способен давать качественный результат
Предприниматели и мелкие организации зачастую не верят в точность программных решений. Распространенная причина отказа от использования рекомендательных систем — незнание способов измерения и оценки пользы. В реальности все это можно измерить, причем делается это достаточно просто. А опыт крупных компаний доказывает, что польза от внедрения рекомендательных систем есть.
Нужно много денег на реализацию
Да, ресурсы на создание и внедрение рекомендательной системы нужны, но не в таких больших количествах, как может показаться на первый взгляд.
Во-первых, все зависит от размеров бизнеса. Если сервис, интернет-магазин или другие предприятия небольшие, то и денег на реализацию потребуется немного. Во-вторых, необязательно создавать собственную систему с нуля. Достаточно воспользоваться готовым фреймворком (TensofFlow, Apple Core ML) или внешним решением (Google ML Kit). Это позволит существенно сократить расходы.
На практике уже не раз было доказано, что рекомендательные системы увеличивают продажи и повышают количество вернувшихся клиентов. Инвестиции на реализацию и внедрение могут вернуться через 3-6 месяцев.
В этой статье мы постарались дать необходимую информацию о рекомендательных системах, которые должен знать начинающий продакт или предприниматель. Конечно, реализация тесно связана с программированием, математическими формулами и другими техническими дебрями, о которых можно рассказывать очень долго. Можно не разбираться во всех тонкостях, потому что обычно создание и внедрение рекомендательной системы поручают опытном программисту.
Ваша задача — понять пользу инструмента и запланировать его внедрение в своей проект (не важно, работает он уже или вы только собираетесь заняться реализацией). Он поможет повысить объем продаж и, как следствие, прибыль, поэтому не откладывайте рекомендательные системы в «долгий» ящик.
Как работают рекомендательные системы. Лекция в Яндексе
Привет, меня зовут Михаил Ройзнер. Недавно я выступил перед студентами Малого Шада Яндекса с лекцией о том, что такое рекомендательные системы и какие методы там бывают. На основе лекции я подготовил этот пост.
Начнем с простого: что вообще такое рекомендательные системы, и какими они бывают. Наверное, все уже сталкивались с ними в интернете. Первый пример — рекомендательные системы фильмов.
На сайте imdb.com пользователи могут оценивать фильмы по десятибалльной шкале. Оценки агрегируются, получается средний рейтинг фильма. На этом же сайте есть блок с рекомендациями для конкретного пользователя. Если я зашел на сайт и оценил несколько фильмов, imdb сможет порекомендовать мне еще какие-нибудь фильмы. Похожий блок есть и на фейсбуке.
Нечто сходное, но только для музыки, делает last.fm. Он рекомендует мне исполнителей, альбомы, мероприятия, на которые мне стоит сходить. Сервис Pandora в России почти неизвестен, т.к. у нас он не работает, однако в Америке он очень популярен. Это такое персональное радио, которое постепенно подстраивается под пользователя на основе его оценок, и в итоге играет только те треки, которые ему нравятся.
Еще одна известная область — рекомендация товаров. На картинке ниже у нас, конечно же, Amazon. Если вы купили что-то на амазоне, за вами будут охотиться с дополнительными предложениями: похожими товарами или аксессуарами. Это хорошо и для пользователей (им не нужно искать эти товары самостоятельно), и конечно, это хорошо для самого магазина.
Мы перечислили три категории, но на самом деле их гораздо больше: заведения на карте, новости, статьи, сайты, концерты, театры, выставки, видео, книги, приложения, игры, путешествия, социальные связи и многое другое.
Виды рекомендательных систем
Можно выделить два основных типа рекомендательных систем. Их, конечно же больше, но мы сегодня будем рассматривать именно эти и в особенности коллаборативную фильтрацию.
Простейшие алгоритмы
Таблица оценок
Допустим, нам дана таблица с оценками пользователей:
На нужно как можно лучше предсказать, какие оценки должны быть в ячейках со знаками вопроса:
Кластеризация пользователей
Напомним, что основная идея коллаборативной фильтрации — похожим пользователям обычно нравятся похожие объекты. Начнем с самого простого метода.
У этого алгоритма есть несколько проблем:
User-based
Попробуем несколько улучшить предыдущий метод и заменить жесткую кластеризацию на следующую формулу:
Однако у этого алгоритма также есть свои проблемы:
Item-based
В предыдущем методе мы отталкивались от идеи, что, скажем, фильм понравится пользователю, если он понравился его друзьям. Здесь же мы считаем, что фильм понравится пользователю, если ему понравились похожие фильмы.
Общие проблемы перечисленных методов
Поэтому перейдем к более сложному алгоритму, который практически лишен этих недостатков.
Алгоритм SVD
Для этого алгоритма нам потребуется несколько понятий из линейной алгебры: векторы, матрицы и операции с ними. Я не буду здесь приводить все определения, если вам нужно освежить эти знания, то все объяснения есть в видеозаписи лекции примерно с 33 минуты.
SVD (Singular Value Decomposition), переводится как сингулярное разложение матрицы. В теореме о сингулярном разложении утверждается, что у любой матрицы 𝐀 размера 𝑛×𝑚 существует разложение в произведение трех матриц: 𝑈, Ʃ и 𝑉 𝑇 :
Матрицы 𝑈 и 𝑉 ортогональные, а Ʃ — диагональная (хотя и не квадратная).
Причем лямбды в матрице Ʃ будут упорядочены по невозрастанию. Сейчас мы эту теорему не будем доказывать не будем, просто воспользуемся самим разложением.
Но что нам с того, что мы можем какую-то матрицу в произведение трех еще более непонятных матриц. Для нас тут будет интересно следующее. Помимо обычного разложения бывает еще усеченное, когда из лямбд, остаются только первые 𝑑 чисел, а остальные мы полагаем равными нулю.
Это равносильно тому, что у матриц 𝑈 и 𝑉 мы оставляем только первые 𝑑
столбцов, а матрицу Ʃ обрезаем до квадратной 𝑑×𝑑.
Так вот, оказывается, что полученная матрица 𝐀′ хорошо приближает исходную матрицу 𝐀 и, более того, является наилучшим низкоранговым приближением с точки зрения средне-квадратичного отклонения.
SVD для рекомендаций
Как же использовать все это для рекомендаций? У нас была матрица, мы разложили ее в произведение трех матриц. При чем разложили не точно, а приблизительно. Упростим все немного, обозначив произведение первых двух матриц за одну матрицу:
Теперь отвлечемся немного от всех этих матриц и сконцентрируемся на получившемся алгоритме: чтобы предсказать оценку пользователя 𝑈 для фильма 𝐼, мы берем некоторый вектор 𝑝𝑢 (набор параметров) для данного пользователя и вектор для данного фильма 𝑞𝑖. Их скалярное произведение и будет нужным нам предсказанием: 𝑟̂𝑢𝑖 = ⟨𝑝𝑢,𝑞𝑖⟩.
Алгоритм достаточно простой, но дает удивительные результаты. Он не просто позволяет нам предсказывать оценки. С его помощью мы можем по истории пользователей выявлять скрытые признаки объектов и интересы пользователей. Например, может так получиться, что на первой координате вектора у каждого пользователя будет стоять число, показывающее, похож ли пользователь больше на мальчика или на девочку, на второй координате — число, отражающее примерный возраст пользователя. У фильма же первая координата будет показывать, интересен ли он больше мальчикам или девочкам, а вторая — какой возрастной группе пользователей он интересен.
Но не все так просто. Есть несколько проблем. Во-первых, матрица оценок 𝑹 нам полностью не известна, поэтому мы не можем просто взять ее SVD-разложение. Во-вторых, SVD-разложение не единственное: (𝑈Ω)Ʃ(𝑉Ω)𝑇=𝑈Ʃ𝑉𝑇, поэтому даже если мы найдем хоть какое-то разложение, вряд ли именно в нем первая координата будет соответствовать полу пользователя, а вторая — возрасту.
Обучение
Попробуем разобраться с первой проблемой. Тут нам понадобится машинное обучение. Итак, мы не можем найти SVD-разложение матрицы, т.к. мы не знаем саму матрицу. Но мы хотим воспользоваться этой идеей и придумать модель предсказания, которая будет работать сходным с SVD образом. Наша модель будет зависеть от многих параметров — векторов пользователей и фильмов. Для заданных параметров, чтобы предсказать оценку, мы возьмем вектор пользователя, вектор фильма и получим их скалярное произведение:
Но так как векторов мы не знаем, их еще нужно получить. Идея заключается в том, что у нас есть оценки пользователей, при помощи которых мы можем найти такие оптимальные параметры, при которых наша модель предсказывала бы эти оценки как можно лучше:
Итак, мы хотим найти такие параметры θ, чтобы квадрат ошибки был как можно меньше. Но тут есть парадокс: мы хотим меньше ошибаться в будущем, но мы не знаем, какие оценки у нас будут спрашивать. Соответственно и оптимизировать это мы не можем. Но нам известны уже проставленные пользователями оценки. Попробуем подобрать параметры так, чтобы на тех оценках, которые у нас уже есть, ошибка была как можно меньше. Кроме того, добавим еще одно слагаемое — регуляризатор.
Зачем нужен регуляризатор?
Регуляризация нужна для борьбы с переобучением — явлением, когда построенная модель хорошо объясняет примеры из обучающей выборки, но достаточно плохо работает на примерах, не участвовавших в обучении. Вообще, методов борьбы с переобучением существует несколько, хочется отметить два из них. Во-первых, нужно выбирать простые модели. Чем проще модель, тем лучше она обобщается на будущие данные (это похоже на известный принцип бритвы Оккама). А второй метод — это как раз регуляризация. Когда мы настраиваем модель для обучающей выборки, мы оптимизируем ошибку. Регуляризация заключается том, что мы оптимизируем не просто ошибку, а ошибку плюс некоторая функция от параметров (например, норма вектора параметров). Это позволяет ограничить размер параметров в решении, уменьшает степень свободы модели.
Численная оптимизация
Как же нам найти оптимальные параметры? Нам нужно оптимизировать вот такой функционал:
Параметров много: для каждого пользователя, для каждого объекта у нас есть свой вектор, который мы хотим оптимизировать. У нас есть функция, зависящая от большого количества переменных. Как найти ее минимум? Тут нам потребуется градиент — вектор из частных производных по каждому параметру.
Градиент очень удобно представлять себе визуально. На иллюстрации у нас изображена поверхность: функция от двух переменных. Например, высота над уровнем моря. Тогда градиент в какой-нибудь конкретной точке — это такой вектор, направленный в ту сторону, куда больше всего растет наша функция. А если пустить воду из этой точки, она потечет по направлению противоположному градиенту.
Самый известный метод оптимизации функций — градиентный спуск. Допустим у нас есть функция от многих переменных, мы хотим ее оптимизировать. Мы берем какое-нибудь изначальное значение, а потом смотрим, куда можно двигаться, чтобы минимизировать это значение. Метод градиентного спуска — это итеративный алгоритм: он многократно берет параметры определенной точки, смотрит на градиент и шагает против его направления:
Проблемы этого метода заключаются в том, что он, во-первых, в нашем случае работает очень медленно и, во-вторых, находит локальные, а не глобальные минимумы. Вторая проблема для нас не так страшна, т.к. в нашем случае значение функционала в локальных минимумах оказывается близким к глобальному оптимуму.
Alternating Least Squares
Однако метод градиентного спуска применять нужно не всегда. Например, если нам нужно посчитать минимум для параболы, действовать этим методом необходимости нет, мы точно знаем, где находится ее минимум. Оказывается, что функционал, который мы пытаемся оптимизировать — сумма квадратов ошибок плюс сумма квадратов всех параметров — это тоже квадратичный функционал, он очень похож на параболу. Для каждого конкретного параметра, если мы зафиксируем все остальные, это будет как раз параболой. Т.е. минимум по одной координате мы можем точно определить. На этом соображении и основан метод Alternating Least Squares. Я не буду на нем подробно останавливаться. Скажу лишь, что в нем мы попеременно точно находим минимумы то по одним координатам, то по другим:
Мы фиксируем все параметры объектов, оптимизируем точно параметры пользователей, дальше фиксируем параметры пользователей и оптимизируем параметры объектов. Действуем итеративно:
Работает все это достаточно быстро, при этом каждый шаг можно распараллелить.
Измерение качества рекомендаций
Если мы хотим улучшить качество рекомендаций, нам нужно научиться его измерять. Для этого алгоритм, обученный на одной выборке — обучающей, проверяется на другой — тестовой. Netflix предложил измерять качество рекомендаций по метрике RMSE:
Сегодня это стандартная метрика для предсказания оценки. Однако у нее есть свои недостатки:
Метрики ранжирования
Существуют и другие метрики — метрики ранжирования, например, основанные на полноте и точности. Пусть 𝑹 — множество рекомендованных объектов, 𝑷 — множество объектов, которые на самом деле пользователю понравятся.
Тут тоже есть проблемы:
Другие свойства рекомендаций
Оказывается, что на восприятие рекомендаций влияет не только качество ранжирования, но и некоторые другие характеристики. Среди них, например, разнообразие (не стоит выдавать пользователю фильмы только на одну тему или из одной серии), неожиданность (если рекомендовать очень популярные фильмы, то такие рекомендации будут слишком банальными и почти бесполезными), новизна (многим нравятся классические фильмы, но рекомендациями обычно пользуются, чтобы открыть для себя что-то новое) и многие другие.
Похожие объекты
Похожесть объектов не такая уж очевидная вещь. К этой задаче могут быть разные подходы: