Здравейте на всички! Казвам се Саша, управлявам технологиите и съм съосновател на LoyaltyLab. Преди две години, като повечето бедни студенти, с приятели обикаляхме вечер за бири в най-близкия магазин. Много ни дразнеше, че retailer-ът, знаейки, че идваме за бира, не предлага отстъпка за чипсове или сухарки, въпреки че това изглежда толкова логично! Не разбрахме защо се случва такава ситуация и решихме да създадем собствена компания. А като бонус, да си правим отстъпки всяка петък за споменатите чипсове.

И стигнахме до там, че с материала за техническата страна на продукта, аз ще участвам на NVIDIA GTC. Радваме се да споделяме разработки с общността, затова публикувам доклада си под формата на статия.

Въведение

Както много в началото на пътя, започнахме с преглед на това как се изграждат системите за препоръки. Най-популярната се оказа архитектура от следния тип:

Тя се състои от две части:

Семплиране на кандидати за препоръки чрез проста и бърза модел, обикновено колаборативен.
Ранжиране на кандидатите чрез по-сложен и бавен контентен модел, който взема предвид всички възможни признаци в данните.

Оттук нататък ще използвам следните термини:

candidate/кандидат за препоръки — двойка user-product, която потенциално може да бъде включена в препоръките в продукция.
candidates extraction/extractor/метод на извличане на кандидати — процес или метод за извличане на "кандидати за препоръки" от наличните данни.

На първия етап обикновено се използват различни вариации на колаборативна филтрация. Най-популярната е ALS. Удивително е, че повечето статии за системи за препоръки разкриват само различни подобрения на колаборативни модели на първия етап, но никой не говори особено за други методи на семплиране. За нас подходът с използване само на колаборативни модели и различни оптимизации с тях не даде толкова добро качество, колкото очаквахме, затова се задълбочихме в изследвания специално по тази тема. А в края на статията ще покажа колко сме успели да подобрим ALS, който беше нашият baseline.

Преди да премина към описанието на нашия подход, е важно да отбележа, че при realtime препоръки, когато е важно да вземем предвид данните, случили се преди 30 минути, действително не съществуват много подходи, които могат да работят в зададеното време. Но в нашия случай, събирането на препоръки се извършва не по-често от веднъж на ден, а в повечето случаи - веднъж седмично, което ни дава възможност да използваме сложни модели и многократно да повишим качеството.

Нека вземем за baseline метриките, които показва само ALS при задачата за извличане на кандидати. Ключовите метрики, по които следим, са следните:

Precision — дял на правилно подбраните кандидати от насемплираните.
Recall — дял на случилите се кандидати от тези, които наистина бяха в целевия интервал.
F1-score — F-мера, изчислена на базата на предишните два пункта.

Също така ще наблюдаваме метриките на финалния модел след обучението на градиентно бустиране с допълнителни контентни признаци. Тук също има 3 основни метрики:

precision@5 — среден дял на попадение на стоки от топ-5 по вероятност за всеки купувач.
response-rate@5 — конверсия на купувачите от посещение в магазина в покупка на поне една персонализирана оферта (с едно предложение от 5 стоки).
avg roc-auc per user — среден roc-auc за всеки купувач.

Важно е да се отбележи, че всички посочени метрики се измерват на time-series крос-валидация, т.е. обучението става на първите k седмици, а като тестови данни се взема k+1 седмица. По този начин сезонните възходи/падения минимално влияят на интерпретацията на качеството на моделите. На всички графики, ос на абсцисите ще означава номера на седмицата в крос-валидацията, а ос на ординатите — стойността на указаната метрика. Всички графики са построени на транзакционни данни на един клиент, за да бъде сравнението между тях коректно.

Преди да започнем да описваме нашия подход, първо нека погледнем базовата линия, която представлява обучената ALS модел.
Метрики за извличане на кандидати:

Финални метрики:

Отнасям се към всички реализации на алгоритми като към определена бизнес хипотеза. По този начин, много грубо, всяка колаборативна модел може да се разглежда като хипотеза, че "хората са склонни да купуват това, което купуват подобни на тях хора". Както вече казах, само с такава семантика не се ограничихме и ето какви хипотези още работят страхотно с данните в офлайн търговията:

Какво е купувано преди.
Подобно на това, което е купувано преди.
Период от предишната покупка.
Популярно по категории/брандове.
Последователни покупки на различни стоки от седмица на седмица (Маркови вериги).
Подобни стоки на купувачите, по характеристики, изградени от различни модели (Word2Vec, DSSM и др.).

Какво е купувано преди

Най-очевидната хенрутика, която работи много добре в продуктовия ритейл. Тук вземаме всички стоки, които притежателят на лоялна карта е купувал през последните K дни (обикновено 1-3 седмици) или K дни преди година. Като приложим само този метод, получаваме следните метрики:

Тук е напълно очевидно, че колкото по-дълъг е периодът, който взимаме, толкова по-голямо е нашето припомняне и по-ниска е прецизността и обратно. Най-добрите резултати в средно по клиенти дават "последните 2 седмици".

Подобно на това, което е купувано преди

Не е изненадващо, че за продуктовия ритейл "какво е купувано преди" работи добре, но извличането на кандидати само от това, което потребителят вече е купувал, не е много ефективно, тъй като е трудно да се изненада купувача с нов продукт. Затова предлагаме да подобрим малко тази хенрутика с помощта на същите колаборативни модели. От векторите, които получаваме по време на обучението на ALS, можем да извлечем подобни стоки на това, което потребителят вече е купувал. Идеята е много подобна на "подобни видеа" в сервисите за стрийминг на видеосъдържание, но тъй като не знаем какво в конкретен момент потребителят гледа/купува, остава само да търсим подобно на това, което вече е купувал, особено, че вече знаем колко добре работи това. Прилагането на този метод на транзакции на потребителите през последните 2 седмици дава следните метрики:

Тук k — количеството подобни стоки, които се извлекат за всеки закупен продукт от потребителя през последните 14 дни.
Този подход при нас се оказа особено ефективен за клиента, който беше критично важно да не се препоръчва нищо, което вече е в историята на покупките на потребителя.

Период отдавна направена покупка

Както вече установихме, поради високата периодичност на покупките на продукти, първият подход работи добре в нашата специфика. Но какво да правим с продукти като прах за пране/шампоан и т.н.? Тоест с такива продукти, които едва ли са нужни всяка седмица-две, и които предишните методи не могат да извлекат. Оттук произтича следващата идея — да се изчисли средният период на покупка на всеки продукт по покупатели, които са го придобили повече k пъти. А след това да извлечем онова, което най-вероятно вече е свършило за купувача. Изчислените периоди за продуктите могат да се проверят визуално за адекватност:

А после ще следим дали краят на периода на продукта попада в интервала, когато препоръките ще бъдат в производство и да извлечем онова, което попада. Пример за подхода може да се илюстрира така:

Тук имаме 2 основни случая, които можем да разгледаме:

Трябва ли да се извлекат продукти за купувачи, които са купували продукта по-малко от K пъти.
Трябва ли да се извлече продукт, ако краят на неговия период попада преди началото на таргетния интервал.

На следващия график се виждат какви резултати постигат такива методи с различни хиперпараметри:

ft — Да се вземат само купувачи, които са купували продукта най-малко K (тук K=5) пъти
tm — Да се вземат само кандидати, които попадат в таргетния интервал

Не е изненада, че в състояние (0, 0) най-голямото recall и най-малкото precision, тъй като при такова условие се извлекат най-много кандидати. Въпреки това, най-добри резултати се постигат, когато не извличаме продукти за купувачи, които са купували конкретен продукт по-малко от k пъти и извличаме също така продукти, чиито край на периода попада преди таргетния интервал.

Последователни покупки на различни стоки от седмица на седмица

Интересен подход, който не съм виждал в статии за системи за препоръки — доста прост и в същото време работещ статистически метод на Марковите вериги. Тук вземаме 2 различни седмици и за всеки купувач изграждаме двойки продукти [купил в седмица i]-[купил в седмица j], където j > i, а оттук считаме за всеки продукт вероятността за преход към друг продукт през следващата седмица. Тоест, за всяка двойка продукти producti-productj считаме техния брой в намерените двойки и делим на броя на двойките, в които producti беше през първата седмица. За извличане на кандидати вземаме последния чек на купувача и получаваме топ-k най-вероятните следващи стоки от матрицата на преходите, която сме получили. Процесът на изграждане на матрицата на преходите изглежда така:

От реални примери в матрицата на вероятностите за преходи виждаме следните интересни явления:

Тук можем да забележим интересни зависимости, които се откриват в потребителското поведение: например, любители на цитруси или бранд мляко, от което с голяма вероятност преминават към друг. Също така, не е изненадващо, че стоките с висока честота на повторни покупки, като масло, също присъстват тук.

Метриките в метода с Марковите вериги са следните:

k — броят на стоките, които се извличат за всеки закупен товар от последната транзакция на купувача.
Както виждаме, най-добрият резултат показва конфигурацията с k=4. Скокът през 4-та седмица може да бъде обяснен със сезонното поведение по време на празничните дни.

Подобни стоки на купувачите, по характеристики, изградени от различни модели.

Ето на какво пристигнахме на най-сложната и интересна част — търсенето на най-близките съседи по векторите на купувачите и продуктите, изградени по различни модели. В своята работа използваме 3 такива модела:

ALS
Word2Vec (Item2Vec за такива задачи)
DSSM

С ALS вече се запознахме, може да прочетете как той се обучава тук. В случая с Word2Vec използваме известната реализация на модела от gensim. По аналогия с текстовете, определяме предложението, като касов бон. Така при изграждането на вектора на продукта, моделът се учи да предсказва по продукта в касовия бон неговия 'контекст' (останалите стоки в касовия бон). В екомерс данните е по-добре вместо касов бон да използваме сесията на купувача, за което страхотно написаха момчетата от Ozon. А DSSM е по-интересен за разглеждане. Първоначално той е създаден от момчетата от Microsoft, като модел за търсене, тук може да се прочете оригиналната изследователска статия. Архитектурата на модела изглежда така:

Тук Q — query, търсене на потребителя, D[i] — document, интернет-страница. На входа на модела постъпват признаци на заявката и страниците, съответно. След всеки входен слой има определено количество напълно свързани слоеве (многослойна перцептрон). След това моделът се учи да минимизира косинуса между векторите, получени в последните слоеве на модела.
В задачите за препоръки се използва точно такава същата архитектура, само че вместо заявка постъпва потребител, а вместо страници — стоки. И в нашия случай такава архитектура се трансформира в следното:

Сега за проверка на резултатите остава да покрием последния момент — ако в случая на ALS и DSSM векторите на потребителите са явно определени, то в случая с Word2Vec имаме само вектори на стоките. Тук за изграждането на вектора на потребителя сме определили 3 основни подхода:

Просто да съберем векторите, тогава за косинусното разстояние ще получим, че просто сме средноизчислили стоките в историята на покупките.
Сумиране на векторите с определено тегло по време.
Теглене на стоките с TF-IDF коефициент.

В случай на линейно претегляне на вектора на купувача, ние изхождаме от хипотезата, че продуктът, който потребителят е купил вчера, оказва по-голямо влияние върху поведението му, отколкото продуктът, който е купил преди шест месеца. Така считаме предишната седмица на купувача с коефициент 1, а всичко, което е било по-рано, с коефициенти ½, ⅓ и т.н.:

За коэффициентите TF-IDF ние правим точно същото, което правим и в TF-IDF за текстовете, като просто считаме купувача за документ, а касовата бележка за предложение, съответно, думата — продукт. Така векторът на потребителя ще се измества повече към редките стоки, а често срещаните и познатите за купувача стоки няма да го променят особено. Подходът може да бъде илюстриран така:

Сега да погледнем метриките. Така изглеждат резултатите от ALS:

Метриките за Item2Vec с различни вариации на изграждането на вектора на купувача:

В този случай се използва точно същата модел, която имаме в нашия baseline. Разликата е само в това, какво k ще използваме. За да използваме само колаборативни модели, трябва да вземем около 50-70 най-близки продукта за всеки купувач.

И метриките за DSSM:

Как да обединим всички методи?

Страхотно, ще кажете вие, но какво да правим с толкова голям набор от инструменти за извличане на кандидати? Как да подберем оптималната конфигурация за нашите данни? Тук имаме няколко задачи:

Трябва някак да ограничим пространството за търсене на хиперпараметри във всеки метод. То, разбира се, е дискретно навсякъде, но количеството възможни точки е много голямо.
Как да подберем най-добрата конфигурация за нашата метрика от малка ограничена извадка от конкретни методи с конкретни хиперпараметри?

Ясно определен отговор на първия въпрос все още не сме намерили, затова изхождаме от следното: за всеки метод е написан ограничител на пространството за търсене на хиперпараметри в зависимост от определени статистики за данните, които имаме. По този начин, знаейки средния период между покупките на хората, можем да предположим, с какъв период да използваме метода "какво са купували" и "период на отдавна правена покупка".

След като разгледахме различни методи, забелязваме следното: всяка реализация извлича определен брой кандидати и има значение за нас метриката (recall). Искаме да получим определен брой кандидати, в зависимост от нашите допустими изчислителни мощности, с максимално възможната метрика. Тук задачата естествено преминава в задача за раница.

Тук броят на кандидатите е теглото на златния блок, а recall на метода — неговата стойност. Въпреки това, има и още два момента, които трябва да се вземат предвид при реализацията на алгоритъма:

Методите могат да имат припокрития в кандидатите, които извличат.
В някои случаи вземането на един метод два пъти с различни параметри ще бъде коректно и кандидатите, извлечени от първия, не ще бъдат подмножество на втория.

Например, ако вземем реализацията на метода „това, което вече сме купували“ с различни интервали за извличане, множествата на кандидатите ще бъдат вложени едно в друго. В същото време, различните параметри в “периодичните покупки” в изхода не дават пълно припокритие. Следователно, разделяме методите на блокове, така че от всеки блок да искаме да вземем не повече от един подход за извличане с конкретни хиперпараметри. За това малко трябва да се хитрува в реализацията на задачата за раница, но асимптиката и резултатът от това няма да се променят.

Тази умна комбинация ни позволява да получим следните метрики в сравнение с просто колаборативни модели:

На крайните метрики виждаме следната картина:

Въпреки това, тук можем да забележим, че остава един непокрит момент за препоръки, полезни за бизнеса. Сега просто сме научили как да предсказваме какво потребителят ще купи, например, следващата седмица. Но просто даването на отстъпка за това, което той и така ще купи, не е много интересно. Вместо това е супер да се максимизира математическото очакване, например, на следните метрики:

Маржът/търговският оборот по персонални препоръки.
Средният чек на купувачите.
Честотата на посещенията.

Така ние умножаваме получените вероятности по различни коефициенти и ги пренареждаме, така че в топа да попадат стоки, които влияят на метриките по-високо. Тук няма готово решение, кой подход е по-добър. Дори ние експериментираме с такива коефициенти директно в продукция. Но ето интересни техники, които най-често дават у нас най-добри резултати:

Умножавайте по цената/маржата на продукта.
Умножавайте по средния чек, в който се среща продуктът. Така на върха ще излязат стоки, с които обикновено се вземат още неща.
Умножавайте по средната честота на посещенията на купувачите на този продукт, въз основа на хипотезата, че този продукт провокира по-често връщане.

След провеждане на експерименти с коефициентите получихме следните метрики в продукцията:

Тук обща конверсия на продуктите — делът на купените стоки от всички стоки в препоръките, които генерирахме.

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

По отношение на приходите получаваме следната история, видно е, че след старта на препоръките, приходите на тестовата група значително нарастват, в момента средното увеличение на приходите с нашите препоръки е 3-4%:

В заключение искам да кажа, че ако имате нужда от непристигнали в реално време препоръки, много голямо подобрение в качеството идва от експерименти с извличането на кандидати за препоръки. Голямо количество време за тяхната генерация предоставя възможност да комбинираме много добри методи, което в крайна сметка ще доведе до страхотни резултати за бизнеса.

Ще се радвам да общувам в коментарите с всички, които сметнат материала за интересен. Въпроси можете да зададете лично на мен в telegram. Също така споделям своите мисли за AI/стартапи в своя telegram канал — добре дошли 🙂

Източник: habr.com