Персонализация товарных рекомендаций на больших данных с помощью Vowpal Wabbit

Привет! Меня зовут Никита Учителев. Я представляю отдел Research & Development компании Lamoda. Нас 20+ человек, и мы работаем над различными рекомендациями на сайте и в приложениях, разрабатываем поиск, определяем сортировку товаров в каталогах, обеспечиваем возможность АБ-тестирования разнообразного функционала, а также поддерживаем несколько внутренних разработок вроде системы прогнозирования эластичности спроса и оптимизации логистики доставки.

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

Идеология товарных рекомендаций

Привычным для всех атрибутом любого интернет-магазина является страница товара. На ней обычно дается подробное описание, несколько крупных фотографий, отзывы покупателей, кнопка “Добавить в корзину” и другие привычные элементы навигации. В нижней части таких страниц располагается одна или несколько полок с другими товарами, которые называются “Похожие товары”, “С этим товаром покупают” или как-то еще. У каждой полки есть свое предназначение.

Например, полка с похожими товарами предназначена для того, чтобы дать пользователю дополнительное разнообразие товаров в текущем контексте выбора. Это может быть полезно, если в стоке нет размера пользователя или если же он находится на стадии выбора и хочет такой же товар, но “с перламутровыми пуговицами”. В то же время полка уводит покупателя со страницы товара, на которую он может уже не вернуться, а соответственно и не купить его.

На сайте и в приложениях Lamoda есть и вторая полка, которую мы называем полкой cross-рекомендаций. Она находится сразу под полкой с похожими товарами, и мы стараемся размещать на ней непохожие товары, которые чаще других встречаются в корзинах покупателей вместе с текущим SKU (Stock Keeping Unit или проще говоря артикул). Так, например, к курткам рекомендуются брюки и обувь, к свитерам — шарфы и шапки. Есть группа недорогих товаров, которые покупают чаще всего. Как правило, это носки и нижнее белье, поэтому их можно нередко увидеть на этой полке.

Данная техника продажи похожа на upsale. Мы пытаемся допродать какие-то крупные комплиментарные товары, при условии, что пользователю нравится текущий товар. В то же время это одно из немногих мест, в котором покупатели могут познакомиться с нашим ассортиментом. Например, увидеть бренд или подкатегорию, о наличии которых они раньше не знали. Мы называем это inspiration & discovery — когда мы вдохновляем покупателей на новые покупки и рассказываем, какой широкий у нас ассортимент, показываем цены и скидки.

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

Идея следующая: мы обучаем некоторую модель, которая умеет присваивать парам “пользователь + товар” вероятность конверсии или просто клика, а затем отображаем их на полке слева направо в порядке убывания этой вероятности. Поскольку на первом экране карусели отображается только от 4 до 6 SKU в зависимости от разрешения экрана, а всего мы можем предрасчитывать их, скажем, до сотни, то достигается вполне приемлемая “глубина” персонализации.

Решаем задачу с конца

Перейдем к технической части. У нас есть ограничения на время ответа API. Например, в приложениях будущему сервису нужно будет успевать отвечать за 100 мс. За это время нужно сходить в разные БД за данными о пользователе и о товарах, отранжировать сотню примеров под нагрузкой до 100 QPS в пике. Это приводит нас к необходимости использовать субмилисекундные фреймворки машинного обучения. Одним из наиболее известных является Vowpal Wabbit.

Типичная область применения этого фреймворка — adtech, а именно предсказание CTR рекламного объявления при оптимизации ставки для RTB-аукциона. С математической точки зрения мы можем поставить похожую задачу. Допустим, мы хотим прогнозировать вероятность клика, обучая модель на показах товаров. Нагрузка на модель до 10k QPS сравнима с рекламными показателями и, в целом, оправдывает необходимость ограничиться только линейными алгоритмами на стадии прототипирования и MVP.

Давайте теперь подумаем, какие данные о пользователе могут содержать нужный нам сигнал и хорошо различать пользователей между собой. Раз мы говорим о рекомендациях товаров и продуктовой странице, на которую заходит пользователь, то, скорее всего, он находится на стадии выбора. У него в голове есть некий образ “идеальных туфель”, с которым он сравнивает все товары, попадающиеся на глаза. Пусть первым делом он идет в каталог товаров нужной категории и начинает поиск, кликая на все, что более-менее похоже на его представление. Тем самым пользователь оставляет за собой некоторый “цифровой след” из просмотренных товаров. На основе агрегата по этому следу и будем делать персонализацию.

Векторные представления объектов

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

В данном случае пользователь посмотрел 10 товаров: 5 золотого цвета, 2 — черного и 3 — красного. А добавил он в корзину 2 красных и 2 черных, золотые не добавлял. Аналогично с брендами А, B и C, а также с любыми значениями атрибутов. Далее такой вектор можно конкатенировать с one-hot encoded вектором значений атрибутов у конкретного товара.

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

Если посмотреть на пространство, в которое мы научились отображать исторические клики, то видно, что одну часть занимает бинарное подпространство, а другую — вещественное, и они никак не связаны друг с другом. Наша линейная модель в таком случае — это линейная комбинация (взвешенная сумма) координат точек в этом пространстве. Если она будет обучаться на таких примерах, то выучит просто априорные вероятности. Например, весом перед координатой, соответствующей красному цвету товара, будет величина прямо пропорциональная CTR красных товаров. Так и конкретные пользовательские координаты окажутся взвешены частотными характеристиками кликов разных пользователей по любым товарам из каталога. Но это не совсем то, чего бы нам хотелось.

На помощь приходят полиномиальные фичи — результат перемножения всех бинарных величин со всеми вещественными. Фреймворк Vowpal Wabbit обладает мощным инструментом для генерации степенных фич из неймспейсов. Давайте попробуем составить строку в формате vw для нашего примера, разнеся пользовательские и товарные фичи по разным неймспейсам.

|user_color красный:0.5 черный:0.2 белый:0.3 |product_color красный

Теперь если при обучении мы добавим ключ -q pu, то появятся такие ненулевые квадратичные фичи:

user_color^красный * product_color^красный = 0.5
user_color^черынй * product_color^красный = 0.2
user_color^белый * product_color^красный = 0.3

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

Данный подход к feature engineering драматически увеличивает размерность пространства, в котором происходит обучение. В ситуации, когда у нас всего 4 цвета, размерность такого пространства равна 8 (4 цвета для товара и 4 — для пользователя). При добавлении 16-ти квадратичных признаков она увеличивается до 24. В production, помимо цветов, мы используем еще 13 атрибутов товаров, включая, например, бренд. Поэтому полная размерность пространства, в котором работают наши модели, может составлять до 3 миллионов признаков. При этом мы хотим поддерживать соотношение числа обучающих примеров к размерности пространства на уровне 1:100. Для этого нам нужно сгенерировать в общей сложности примерно 300 миллионов наблюдений.

Архитектура платформы персонализации

Мы храним кликстрим наших пользователей в Hadoop (Spark Streaming из Apache Kafka в Hive-таблицу). В сутки мы обычно получаем порядка 30 гигабайт сжатых данных — это больше сотни различных типов действий, которые пользователи могут совершать на сайте и в приложениях, включая показы товаров в различных плейсментах.

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

Наше решение — ежедневная агрегация пользовательских данных с помощью Spark и инкрементальная загрузка этих данных в HBase. Рассмотрим структуру такого агрегата.

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

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

Кому-то может показаться спорным такой выбор хранилища, но у меня был удачный опыт работы с HBase в похожих проектах. Кроме того, в Lamoda эта БД уже активно используется, так что нам ничего не стоило использовать уже развернутую систему для MVP. Функционал версионирования на данный момент мы не используем, но вот доступ по ключу показался полезным для возможности многопоточного обучения моделей в будущем и организации лямбда-архитектуры загрузки данных и других realtime-кейсов.

Поскольку в HBase нет схемы, нам нужен свой контейнер для данных. Можно было бы использовать lambda x: json.dumps(x).encode(), но хотелось чего-то побыстрее. Вполне стандартным решением является использование контейнеров protobuf. Поскольку разработка всего проекта ведется на python, для меня привычнее использовать кастомную библиотеку pyrobuf от AppNexus вместо официальной от Google. По бенчмаркам производительность базового функционала протобуфов в несколько раз превосходит оригинал. Примерная схема нашего протобуфа такова:

enum Location {
   ru = 1;
   by = 2;
   ua = 3;
   kz = 4;
   special = 5;
}

enum Platform {
   desktop = 1;
   mobile = 2;
   a_phone = 3;
   a_tablet = 4;
   iphone = 5;
   ipad = 6;
}

message Action {

   enum ActionType {
       pageview = 1;
       quickview = 2;
       rec_click = 3;
       catalog_click = 4;
       fav_add = 5;
       cart_add = 6;
       order_submit = 7;
   }

   required uint64 ts = 1;
   required ActionType action_type = 2;
   optional string sku = 3;
   required bool is_office = 4;
   repeated string skus = 5;       
   optional uint32 delta = 6;       
   optional string sku_source = 7;
   optional bool stock = 8;         
   optional uint32 base_price = 9;
   optional uint32 price = 10;    
   optional string type = 11;      
}

message Session {
   required string session_id = 1;
   repeated Action actions = 2;
   required uint64 session_start = 3;
   required uint64 session_end = 4;
   optional uint32 actions_count = 5;
}

message LID {
   required string uid = 1;
   repeated Session sessions = 2;
   required Location location = 3;
   required Platform platform = 4;
   optional uint32 sessions_count = 5; 
}

Если кратко, то есть объект “Пользователь” (LID, Lamoda ID). Внутри него есть массив объектов “Сессия”, каждый из которых — это массив объектов “Действие”. Действия мы разделили по типам и храним в разных Column Family, что позволяет немного оптимизировать чтение, когда нам нужны только события определенных типов (просмотры товаров, атрибуцированные клики по разным типам рекомендаций и прочее).

Тестирование

На протяжении трех недель мы проводили АБ-тест на десктопном сайте lamoda.ru в следующем дизайне:

• Контроль: API рекомендаций обращается к сервису персонализации, дожидается результата, но отдает товары в исходном порядке, одинаковом для всех.
• Тест: товары отображаются слева направо в порядке убывания прогноза вероятности клика.

Деление на два варианта происходит на основе LID пользователя — по сути по его cookie. Наша платформа для экспериментов гарантирует, что собранные наблюдения в двух вариантах оказываются независимыми и равномерно распределенными, а изменения метрик оцениваются с уровнем значимости 5% (p-value 0.05). В итоге мы получили +10% CTR полки целиком и значимое положительное изменение выручки. На прошлой неделе мы раскатили данный функционал на всех пользователей сайта.

Чтобы проверить персонализацию на себе, достаточно посмотреть несколько различных товаров и затем сравнить сортировку рекомендаций на одной из полок “С этим товаром покупают” в двух разных браузерах или воспользоваться режимом “Инкогнито”. Конечно, если вы ранее не посещали наш сайт, то и данных по вам в платформе еще немного. Попробуйте повыбирать себе зимнюю куртку и сравните порядок товаров еще раз через некоторое время.

От сервиса к платформе

Так у нас получилась целая платформа — набор программных средств, которые осуществляют агрегацию данных и их хранение, а также фреймворк по векторизации бизнес-объектов на произвольный момент времени в прошлом, который позволяет строить скоринговые модели для оценки вероятности совершения различных действий. Инференс моделей осуществляется через веб-сервис, который умеет собирать актуальные вектора из различных источников данных и прогонять их через модель. Он принимает на вход LID (идентификатор пользователя), список SKU, которые нужно отскорить и различную дополнительную информацию, возвращая тот же список товаров в обогащенный прогнозами вероятности клика. Ниже представлена схема концептуальной архитектуры нашей платформы:

Элемент ML Core представляет из себя набор виртуалок, на которых установлены клиенты к Hadoop и воркеры Airflow. Мы задаем конфигурацию, с какими параметрами обучить модель, откуда взять исторические данные и прочее. В итоге модель обучается и публикуется в artifactory, а информация о процессе обучения и интересующие нас метрики качества сохраняются в метахранилище.

Уже сейчас тестируются или готовятся к тестам системы персонализации рекомендаций в почтовых рассылках, на главных страницах и полке с рекомендациями похожих товаров, look-alike сегменты для таргетинга внутренней и внешней рекламы и многое другое.

--

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

Автор: Учителев Никита

Источник