Рекомендательные системы
16 февраля 2014 :: 19 комментариев :: 24591 просмотр :: 1608 слов

Продолжая серию постов про поиск и обработку языка, хотелось бы провести небольшую работу над ошибками. Предыдущий пост про извлечение фактов по всей видимости оказался крепким орешком для неподготовленного читателя. Несмотря на то, что я потратил на него в 2 раза больше времени, я получил в 4 раза меньше тематического фидбека.

Вообще когда я затевал эту идею, я боялся, что посты покажутся слишком дилетантскими, набигут выколобые интеллектуалы и, размахивая теоремами высшей дискретной геометрии и зачеткой за второй курс факультета математики и матанализов, разнесут мою мотивацию продолжать писать в пух и прах. Однако сейчас мне становится очевидно, что бояться нужно противоположного — что посты будут непонятными широкому кругу читателей.

Потому теперь я снова стараюсь вернуться к популярному стилю изложения, целью которого является заинтересовать, а не объяснить в подробностях. Оставшихся же 0 человек, которым будут интересны подробности, я приглашаю в комментарии или на рюмочку чая. Попробуем такую схему.

Всегда сложно выбирать тему для поста, это как назвать все слова, которые знаешь. Даже если ваш словарный запас — тысячи, на втором десятке вы уже затупите (намекаю, что стоит подсказывать мне новые интересующие вас темы). Сегодня хотелось бы затронуть область, напрямую не связанную с NLP, однако идущую с ней бок-о-бок: рекомендательные системы.

С рекомендательными системами нам приходится встречаться всё чаще и чаще по банальной причине: сферические моркетологи каждый год проводят сферические исследования, в которых огромными сферическими процентами намекают как увеличивается количество покупок (aka конверсия) в вашем интернет-магазине, если под каждым товаром висит блок «похожие товары», или «возможно вы захотите приобрести», или «с данным товаром покупают еще».

Ну а если без шуток, то это действительно так.

Всем известный last.fm вырос благодаря рекомендательным алгоритмам

Потому из всей нашей сферы наверное именно рекомендательные системы имеют самую большую популярность, их полезность легче всего доказывается вашему начальству с помощью красивых графиков, в отличии от всех остальных систем. На основе одних только рекомендательных алгоритмов строят целые проекты, тот же LastFM или Имхонет, Prismatic или наш отечественный Surfingbird, а Яндекс недавно решил снова всех побить и выпустил «рекомендации для всех и обо всём» под названием Яндекс.Атом.

Рекомендательные системы — это комплексы алгоритмов, которые пытаются предсказать какие объекты (товары) будут интересны пользователю, имея определенные данные о его профиле (интересах, истории просмотров, оценок). Традиционно рекомендательные системы разделяют на четыре типа:

Коллаборативная фильтрация (collaborative filtering)
Рекомендации на основе оценок других пользователей. Примеры условий: Юзеру N, со схожими с вашими оценками, понравился этот фильм, вероятно вам он тоже понравится. Фильм M похож на фильмы, которые вы уже высоко оценили, возможно он вам тоже понравится. Примеры сервисов: Имхонет, last.fm. Плюсы: Теоретически высокая точность. Минусы: Высокий порог входа: не зная ничего об интересах юзера, рекомендации практически бесполезны, многие юзеры будут просто сразу уходить.
Основанные на контенте (content-based)
Рекомендации на основе данных, собранных о каждом конкретном товаре. Примеры условий: Начиная от простых: «Книги того же жанра или автора», «Вещи того же производителя», до «Вам нравятся комедии с Джимом Керри, вот вам подборка комедий с ним». Примеры сервисов: Prismatic, Surfingbird. Плюсы: Можно делать рекомендации даже незнакомым юзерам, тем самым вовлекая их в сервис. Возможность рекомендовать те объекты, которые еще не были никем оценены. Минусы: Точность сильно падает, время разработки немного возрастает.
Основанные на знаниях (knowledge-based)
Рекомендации, основанные на знаниях о предметной области (а не о каждом товаре). Часто предыдущий тип (content-based) определяют как частный случай knowledge-based, где знаниями являются сведения о товаре, но content-based имеет такую широкую распространенность, что имеет смысл выносить его в отдельный тип (и в большинстве литературы так и делают). Эти самые дополнительные знания позволяют делать рекомендации не основываясь на «похожести» чего-либо, а с более сложными условиями. Примеры условий: К этому плееру вам возможно пригодятся наушники. Вы купили отличную камеру, вот вам 10% скидки на сумку для нее. Примеры сервисов: Крупные интернет-магазины, в том числе Российские (точно видел у связного). Плюсы: Возможность исключить любимую ситуацию всех систем рекомендации: «Вы только что купили квартиру в Москве? Вероятно вот эти 5 квартир в Москве вам тоже пригодятся!». Возможность регулировать ситуации типа «макбук 2007 года оценили на 5.0, а макбук 2014 на 4.9, значит макбук 2007 года лучше». Минусы: Высокая сложность разработки и сбора данных.
Гибридные (hybrid)
Как обычно идея «взять самое лучшее от каждого типа» не заставила себя долго ждать. И при определенном упорстве, получается. Например самой крутой на данный момент рекомендательной системой считается система Netflix (BellKor), выигравшая миллион долларов на Netflix Prize в 2009-м, она является комбинацией 27 (!) рекомендательных алгоритмов. Примеры условий: Ограничены только воображением создателей. Примеры сервисов: кроме Netflix не удалось нагуглить примеров. Плюсы: Самая высокая точность, у Netflix погрешность примерно 0.86 балла для 5-балльной шкалы оценок. Хотя, конечно, всё зависит от реализации. Минусы: Самая высокая сложность разработки.

Пример коллаборативной фильтрации на имхонете

Коллаборативная фильтрация

Разберем немного подробней каждый из типов систем. Коллаборативная фильтрация всегда предполагает то, что у нас есть данные о пользователях и объектах, которые они оценили (в том числе о текущем пользователе). Тогда фильтрация разделяется на два типа: user-based и item-based.

В случае user-based рекомендации строятся по принципу: «найти пользователей, похожих на меня, и посмотреть нравится ли им данный объект». Например: «Пользователи Алеша и Борис любят митболы, латте и стартапы, а пользователь Валера любит митболы и латте, значит скорее всему ему нужно начинать стартап».

В случае item-based логика рекомендаций поворачиваются другой стороной: «найти объекты, похожие на заданный, и посмотреть как я их оценивал ранее». Например: «Понравится ли Валере делать стартапы? Валера любит латте и митболы, значит скорее всего ему понравятся стартапы».

По ссылке выше user- и item-based системы описаны достаточно хорошим и простым языком, в благодарность автору отправляю всех читателей, заинтересованных в подробностях, именно туда. Коллаборативная фильтрация в теории — штука достаточно простая: найти юзеров, оценивших данный объект, а затем посчитать коэффициент корреляции векторов их оценок всем объектам в базе. Взять, например, k юзеров с самыми высокими коэффициентами корреляции и посмотреть как они чаще всего оценивали данный объект (типичный алгоритм k-ближайших соседей). Для увеличения точности не забыть разделить каждую оценку на среднюю оценку юзера (чтобы сгладить влияние «хейтеров» и «мне нравится всё» юзеров).

Здесь я хотел упомянуть еще метод SVD (Сингулярное Разложение Векторов — какое название-то!), который на данный момент является передовым в области коллаборативной фильтрации, но статья и так получается длинной, можете попросить написать продолжение.

Основанные на контенте

Content-based системы опираются на знания об объектах, совершенно игнорируя как там эти объекты оценивали другие пользователи. В качестве знаний об объекте выступают любые его свойства, которые мы можем добыть: жанр, производитель, автор, страна, в общем всё, что вы сможете добыть в вашей области. Только увлекаться тоже не стоит, например, производитель процессора не часто является релевантным свойством при выборе смартфона.

В последнее время именно content-based рекомендации становятся самыми популярными, потому что никто из пользователей не хочет тратить время на «обучение» системы своим предпочтениями, а никто из создаталей систем не хочет терять кучу пользователей сразу после регистрации. Отсюда и имеем кучу жалоб и шуток про то, что «я купил джинсы на ибее и он теперь мне постоянно джинсы предлагает» или «зашел на сайт с обручальными кольцами, теперь Яндекс.Директ везде предлагает купить их».

Content-based системы стали настолько популярны, что всех начинает тошнить от их глупых и неуместных рекомендаций. Так что думайте, перед тем как пилить очередную контент-ориентированную систему, не будет ли она раздражать ваших пользователей как 90% существующих. Или может у вас есть время и мозги, чтобы попробовать расширить ее дополнительными условиями и двинуться в сторону knowledge-based.

Зато эти системы опираются на уже известные нам знания про TF-IDF и схожесть документов и практически ничего нового при их написании изучать не придется. Та же обработка языка, та же классификация (кстати хотел написать про фильтрацию спама, но пока думаю не банально ли это, если хоть кому-то это интересно, опишитесь), всё это понятно, известно и достаточно просто: нашел похожие документы и выдал на странице.

Prismatic — типичная content-based система

Основанные на знаниях

Рекомендательные системы основанные на знаниях так же не опираются на оценки других юзеров, а смотрят только на профиль пользователя и товара. Дальнейшие пути всегда различны. Объединяет их то, что каждый путь подразумевает наличие знаний о какой-то предметной области. Либо о пользователях, либо о товарах, либо еще о чем-либо, что может помочь ранжированию.

Case-based подход подразумевает наличие дополнительной сущности: требований пользователя (user requirements). Требования могут выглядеть как: «современная зеркальная камера с минимум 32 точками автофокуса и ценой до $2000» и могут задаваться путем выбора нужных чекбоксов. Задача подхода заключается просто в том, чтобы найти рекомендованные товары, согласно требованиям.

Demographic-based учитывает свойства непосредственно пользователя. Насколько он обеспечен, где живет, сколько зарабатывает, и.т.д.

Шкала на имхонете. Правда по качеству его рекомендаций мне кажется она сделана только для красоты.

Utility-based рассчитывает относительную полезность каждого товара для пользователя. Если пользователь гик, скорее всего и фотоаппарат он выберет с наибольшим количеством функций. Если пользователь купил фотоаппарат, скорее всего он за объективами для него придет.

Critique-based имеют дополнительный интерфейс для «критики». Например две оси, по которым пользователь будет задавать «хочу дороже, но с большим количеством мегапикселей», а система пытаться подстроиться под запрос.

Whatever-you-want-based как можно заметить, практически все подвиды knowledge-based систем зависят исключительно от воображения их авторов. В каждом конкретном случае можно выдумывать свои области знаний и ранжировать по ним, достигая максимальных результатов. Всё зависит только от вас.

Пример основанных на знаниях рекомендаций у Связного

Гибридные

В гибридных рекомендательных системах уже, как говорится у классика, «пацаны ебашатся по хардкору». Все «настоящие» рекомендательные системы, как и поисковые системы, почти всегда — гибриды. Их разработчики применяют машинное обучение чтобы выделять самые релевантные для пользователя алгоритмы, применяют методы оптимизации для поиска наилучших коэффициентов, в общем развлекаются как хотят. Единого алгоритма построения гибридных систем нет, к ним просто приходят все, кто попробует вышеперечисленные.

Система рекоменданий Netflix

Вот вроде и всё небольшое введение. Надеюсь, хотя бы 5% дочитало досюда, за что им спасибо. По ходу изложения я достаточно часто просил всех отписываться о том, что вам было бы интересно, а что нет. Это поможет мне сориентироваться при выборе тем в дальнейшем. Вполне вероятно, что я могу считать какую-то интересную тему попросту «очевидной» (как ваш препод по матану считал очевидной 4-этажную формулу на доске), а кому-то она будет интересна. Так же пока у меня читателей не очень много, приятно будет видеть любые даже банальные благодарности, буду расценивать их как «лайки» и дополнительную мотивацию на следующей неделе снова тратить пол дня на новый пост.

Еще? Тогда вот