Всім привіт! Мене звуть Сашко, я CTO & Co-Founder у LoyaltyLab. Два роки тому я з друзями, як і всі бідні студенти, ходив увечері за пивом до найближчої крамниці біля будинку. Нас дуже засмучувало, що рітейлер, знаючи, що ми прийдемо за пивом, не пропонує знижку на чіпси чи сухарики, хоч це так логічно! Ми не зрозуміли чому така ситуація відбувається і вирішили зробити свою компанію. Ну і як бонус виписувати собі знижки щоп'ятниці на ті самі чіпси.

І дійшло все до того, що з матеріалом з технічного боку продукту я виступаю на NVIDIA GTC. Ми раді ділитися доробками з ком'юніті, тому я викладаю свою доповідь у вигляді статті.

Запровадження

Як і все на початку шляху, ми стартували з огляду на те, як робляться рекомендаційні системи. І найпопулярнішою виявилася архітектура такого типу:

Вона складається із двох частин:

1. Семплювання кандидатів для рекомендацій простою та швидкою моделлю, зазвичай колаборативною.
2. Ранжування кандидатів більш складною та повільною контентною моделлю з урахуванням всіх можливих ознак даних.

Тут і далі використовуватиму наступні терміни:

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

На першому кроці зазвичай використовують різні варіації колаборативної фільтрації. Найпопулярніша - БАС. Дивно, що більшість статей про рекомендаційні системи розкривають лише різні покращення колаборативних моделей на першому етапі, але про інші методи семплювання особливо ніхто не розповідає. Для нас підхід з використанням тільки колаборативних моделей та різних оптимізацій з ними не спрацював з якістю, на які ми очікували, тому ми закопалися в дослідження конкретно з цієї частини. А наприкінці статті я покажу, наскільки ми змогли покращити ALS, який був для нас baseline'ом.

Перед тим, як я перейду до опису нашого підходу, важливо зазначити, що при реальнихчасових рекомендаціях, коли нам важливо враховувати дані, які відбулися 30 хвилин тому, дійсно, не так багато підходів, які можуть працювати за потрібний час. Але, в нашому випадку, збирати рекомендації доводиться не частіше, ніж раз на день, а в більшості випадків – раз на тиждень, що дає можливість використовувати складні моделі і кратно підвищити якість.

Візьмемо за baseline те, які метрики показує лише ALS на завданні кандидатів. Ключові метрики, за якими ми стежимо, такі:

• Precision – частка правильно підібраних кандидатів із насемпльованих.
• Recall - частка кандидатів, що трапилися, з тих, які реально були в target інтервалі.
• F1-score - F-мера, розрахована на попередніх двох пунктах.

Також дивитимемося на метрики фінальної моделі після навчання градієнтного бустингу з додатковими контентними ознаками. Тут також 3 основні метрики:

• precision@5 - середня частка влучення товарів з топ-5 по кожному покупцю.
• response-rate@5 — конверсія покупців з візиту до магазину на покупку хоча б однієї персональної пропозиції (в одному реченні 5 товарів).
• avg roc-auc per user — середній roc-auc щодо кожного покупця.

Важливо, що всі названі метрики вимірюються на time-series крос-валідації, тобто навчання відбувається на перших k тижнях, а як test даних береться k +1 тиждень. Таким чином, сезонні зльоти/падіння мінімально відбивалися на інтерпретації якості моделей. Далі на всіх графіках вісь абсцис означатиме номер тижня у крос-валідації, а вісь ординат – значення вказаної метрики. Усі графіки побудовані на транзакційних даних одного клієнта, щоб порівняння було коректним.

Перед тим, як почати описувати наш підхід, спочатку подивимося на baseline, який є навченою ALS моделью.
Метрики з вилучення кандидатів:

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

Я належу до всіх реалізацій алгоритмів, як до деякої бізнес гіпотези. Таким чином, дуже грубо, будь-які колаборативні моделі можна розглядати як гіпотезу, що “люди схильні купувати те, що купують схожі на них люди”. Як я вже казав, тільки такою семантикою ми не обмежилися і ось які гіпотези ще круто працює на даних в оффлайн рітейлі:

1. Що вже купував раніше.
2. Схоже, що купував раніше.
3. Період давно минулої покупки.
4. Популярне за категоріями/брендами.
5. Почергові покупки різних товарів від тижня до тижня (ланцюги Маркова).
6. Схожі товари на покупців за характеристиками, побудованими різними моделями (Word2Vec, DSSM, etc.).

Що купував раніше

Найочевидніша евристика, яка дуже добре працює у продуктовому ритейлі. Тут ми беремо всі товари, які власник картки лояльності купував за останні K днів (зазвичай 1-3 тижні), або K днів за рік тому. Застосувавши лише такий метод, отримуємо такі метрики:

Тут цілком очевидно, що чим більше ми беремо період, тим більше у нас recall і менше precision і навпаки. Найкраще результати в середньому по клієнтам дає останні 2 тижні.

Схоже на те, що купував раніше

Не дивно, що для продуктового рітейлу "що купував раніше" працює добре, але витягувати кандидатів тільки з того, що користувач вже купував не дуже круто, тому що так здивувати покупця якимсь новим товаром навряд чи вийде. Тому пропонуємо трохи удосконалимо цю евристику за допомогою тих самих колаборативних моделей. З векторів, які ми отримали під час навчання ALS, можна дістати схожі товари на те, що вже купував користувач. Така ідея дуже схожа на “схожі ролики” в сервісах перегляду відеоконтенту, але оскільки ми не знаємо, що в конкретний момент їсть/купує користувач, нам залишається тільки шукати схоже тільки до того, що він вже купував, тим більше, що ми вже знаємо, як це добре працює. Застосувавши такий метод на транзакціях користувачів за останні 2 тижні, отримуємо наступні метрики:

Тут k — кількість схожих товарів, які витягуються за кожен куплений покупцем товар протягом останніх 14 днів.
Цей підхід особливо добре спрацював на клієнті, якому було критично зовсім не рекомендувати те, що вже було в історії покупок користувача.

Період давно минулої покупки

Як ми вже з'ясували, через високу періодичність купівлі товарів перший підхід добре працює на нашій специфіці. Але як бути з товарами типу пральний порошок/шампунь/тд. Тобто з такими продуктами, які навряд чи потрібні щотижня-два, які попередні методи не можуть витягти. Звідси випливає наступна ідея - пропонується обчислювати період купівлі кожного товару в середньому по покупцям, які купували товар більше k разів. А далі отримувати те, що, швидше за все, у покупця вже закінчилося. Підраховані періоди товарів можна перевірити очима на адекватність:

А далі будемо дивитися, чи попадає кінець періоду продукту в інтервал часу, коли рекомендації будуть у продакшн і семплювати те, що потрапляє. Проілюструвати підхід можна так:

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

1. Чи потрібно семплювати товари покупцям, які купували товар менше ніж K разів.
2. Чи потрібно семплювати товар, якщо кінець його періоду потрапляє на початок таргет інтервалу.

На наступному графіку видно, які результати досягає такий метод із різними гіперпараметрами:

ft - Брати тільки покупців, які купували продукт не менше K (тут K = 5) разів
tm — Брати лише кандидатів, які потрапляють до таргету інтервалу

Не дивно, що може (0, 0) найбільший згадувати і найменший точність, оскільки за такої умови витягується найбільше кандидатів. Однак найкращих результатів досягає ситуація, коли ми не семплюємо товари для покупців, які купували конкретний товар. k раз і витягуємо у тому числі товари, кінець періоду яких потрапляє до таргет інтервалу.

Популярне за категорією

Ще одна досить очевидна ідея — семплювати популярні товари за різними категоріями або брендами. Тут ми для кожного покупця обчислюємо топ-k “улюблених” категорій/брендів та витягуємо “популярне” з цієї категорії/бренду. У нашому випадку визначимо "улюблені" та "популярні" за кількістю покупок товару. Додатковою перевагою цього підходу є застосування в кейсі холодного старту. Тобто для покупців, які зробили або дуже мало покупок, або давно не були в магазині, або взагалі оформили карту лояльності. Для них простіше і найкраще накидати товари з популярного у покупців із наявною історією. Метрики виходять такі:

Тут цифра після слова "category" означає рівень вкладеності категорії.

Загалом, також не дивно, що найкращих результатів досягають вужчі категорії, оскільки витягують точніші “улюблені” товари для покупців.

Почергові покупки різних товарів від тижня до тижня

Цікавий підхід, якого я не бачив у статтях про рекомендаційні системи, — досить простий і водночас робочий статистичний метод ланцюгів Маркова. Тут ми беремо два різні тижні, далі по кожному покупцю будуємо пари продуктів [купив на тиждень i]-[купив на тиждень j], де j > i, а звідси вважаємо для кожного товару можливість переходу до іншого товару наступного тижня. Тобто для кожної пари товарів producti-productj рахуємо їх кількість у знайдених парах і ділимо на кількість пар, де producti був на першому тижні. Для отримання кандидатів беремо останній чек покупця і дістаємо топ-k найімовірніших наступних товарів з матриці переходів, яку ми отримали. Процес побудови матриці переходів має такий вигляд:

З реальних прикладів у матриці ймовірностей переходів бачимо такі цікаві явища:

Тут можна помітити цікаві залежності, які виявляються у споживчій поведінці: наприклад, любителі цитрусів чи бренд молока, з якого з великої ймовірності переходять на інший. Також не дивно, що товари з великою частотою повторних покупок, як олія, також тут виявляються.

Метрики у методі з ланцюгами Маркова виходять такі:

k — кількість товарів, які витягуються за кожен куплений товар з останньої транзакції покупця.
Як бачимо, найкращий результат показує конфігурація з k=4. Сплеск на 4 тижні можна пояснити сезонною поведінкою у святкові дні. 

Схожі товари на покупців, за характеристиками, побудованими різними моделями

Ось ми й підійшли до найскладнішої та найцікавішої частини — пошуку найближчих сусідів за векторами покупців та продуктів, побудованих за різними моделями. У своїй роботі ми таких моделей використовуємо 3:

• БАС
• Word2Vec (Item2Vec для таких завдань)
• DSSM

З ALS ми вже розібралися, прочитати про те, як він навчається можна тут. У випадку з Word2Vec, ми використовуємо всім відому реалізацію моделі з генсім. За аналогією з текстами, визначаємо пропозицію, як чек покупки. Таким чином, при побудові вектора продукту модель вчиться передбачати по товару в чеку його "контекст" (інші товари в чеку). У ecommerce даних краще замість чека використовувати сесію покупця, про це круто написали хлопці з озон. А DSSM розібрати цікавіше. Спочатку його написали хлопці з Microsoft, як модель для пошуку, тут можна прочитати вихідний research paper. Архітектура моделі виглядає так:

Тут Q - Query, пошуковий запит користувача, D[i] - Document, інтернет-сторінка. На вхід моделі надходять ознаки запиту та сторінок, відповідно. Після кожного вхідного шару йде кілька повнозв'язкових шарів (multilayer perceptron). Далі модель вчиться мінімізувати косинус між векторами, які в останніх шарах моделі.
У завданнях рекомендацій використовується така сама архітектура, тільки замість запиту йде користувач, а замість сторінок — товари. І в нашому випадку така архітектура трансформується у таке:

Тепер для перевірки результатів залишилося покрити останній момент – якщо у випадку ALS та DSSM вектори користувачів у нас явно визначені, то у випадку з Word2Vec у нас є лише вектори товарів. Тут для побудови вектора користувача ми визначили 3 основні підходи:

1. Просто скласти вектори, тоді для косинусної відстані вийде, що ми просто усереднили товари купівельної історії.
2. Підсумовування векторів із деяким зважуванням за часом.
3. Зважування товарів із TF-IDF коефіцієнтом.

У разі лінійного зважування вектора покупця ми виходимо з гіпотези про те, що товар, який користувач купив учора, більше впливає на його поведінку, ніж товар, який він купив півроку тому. Так ми вважаємо попередній тиждень покупця з коефіцієнтом 1, а те, що було далі з коефіцієнтами ½, ⅓, і т.д.

Для TF-IDF коефіцієнтів ми робимо те саме, що й у TF-IDF для текстів, тільки вважаємо покупця за документ, а чек за пропозицію, відповідно, слово — товар. Так вектор користувача більше зрушуватиметься у бік рідкісних товарів, а часті та звичні для покупця товари його змінювати особливо не будуть. Проілюструвати підхід можна так:

Тепер подивимось на метрики. Так виглядають результати ALS:

Метрики по Item2Vec із різними варіаціями побудови вектора покупця:

В даному випадку використовується рівно та сама модель, що і в нашому базіline. Різниця лише в тому, яке ми будемо використовувати. Щоб використовувати лише колаборативні моделі, доводиться брати близько 50-70 найближчих товарів кожного покупця.

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

Як поєднати всі методи?

Класно, скажете ви, але що робити з таким величезним набором інструментів для отримання кандидатів? Як вибрати оптимальну конфігурацію під свої дані? Тут у нас виникає кілька завдань:

1. Треба якось обмежити простір пошуку гіперпараметрів у кожному методі. Воно, звичайно, дискретне скрізь, але кількість можливих точок дуже велика.
2. Як по невеликій обмеженій вибірці з конкретних методів із конкретними гіперпараметрами підібрати найкращу конфігурацію під свою метрику?

Однозначно правильної відповіді на перше запитання ми поки не знайшли, тому виходимо з наступного: під кожен метод написано обмежувач простору пошуку гіперпараметрів залежно від деяких статистик за даними, які ми маємо. Таким чином, знаючи середній період між покупками у людей, ми можемо припускати, з яким періодом використовувати метод "що вже купували" і "період покупки, що давно минула".

А після того, як ми перебрали деяку адекватну кількість варіацій різних методів, зауважимо таке: кожна реалізація отримує деяку кількість кандидатів і має певне значення ключової для нас метрики (recall). Ми хочемо в сумі отримати певну кількість кандидатів, яка залежить від наших допустимих обчислювальних потужностей, з максимально можливою метрикою. Тут завдання красиво хлопається у завдання про рюкзак.

Тут кількість кандидатів - вага зливка, а recall методу - його цінність. Однак є ще 2 моменти, які варто закладати під час реалізації алгоритму:

• У методів може бути перетин у кандидатах, які вони дістають.
• У деяких випадках взяти один метод двічі з різними параметрами буде коректно і кандидати на виході з першого не будуть підмножиною другого.

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

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

На фінальних метриках бачимо таку картину:

Однак тут можна помітити, що залишився один непокритий момент для корисних для рекомендацій бізнесу. Зараз ми просто навчилися круто пророкувати те, що користувач придбає, наприклад, наступного тижня. Але просто давати знижку на те, що він і так придбає не дуже прикольно. Зате круто максимізувати маточування, наприклад, наступних метрик:

1. Маржу/товарообіг за персональними рекомендаціями.
2. Середній чек покупців.
3. Частота візитів.

Так ми множимо отримані можливості на різні коефіцієнти і переранжуємо їх так, щоб у топ потрапляли товари, що впливають на метрики вище. Тут немає готового рішення, який підхід краще використати. Навіть ми експериментуємо з такими коефіцієнтами проводимо прямо у продакшн. Але ось цікаві прийоми, які найчастіше дають у нас найкращі результати:

1. Домножувати на ціну/маржу товару.
2. Домножувати середній чек, у якому зустрічається товар. Так нагору вилізуть товари, з якими зазвичай беруть ще щось.
3. Примножувати на середню частоту візитів покупців даного товару, виходячи з гіпотези, що цей товар провокує частіше за ним повертатися.

Провівши експерименти з коефіцієнтами, ми отримали наступні метрики в продакшн:

Тут overall products conversion — частка куплених товарів із усіх товарів у рекомендаціях, які ми згенерували.

Уважний читач помітить суттєву різницю між офлайн та онлайн метриками. Така поведінка пояснюється тим, що далеко не всі динамічні фільтри товарів, які можна рекомендувати, можливо враховувати при навчанні моделі. Для нас нормальна історія, коли половина вилучених кандидатів може бути відфільтрована, така специфіка є характерною в нашій галузі.

За виторгом виходить наступна історія, видно, що після запуску рекомендацій, виручка у тестової групи сильно зростає, зараз середній приріст виручки з нашими рекомендаціями - 3-4%.

На закінчення хочу сказати, що, якщо вам потрібні не реальнічасові рекомендації, то дуже великий приріст в якості знаходиться в експериментах з вилученням кандидатів для рекомендацій. Багато часу для їх генерації дає можливість комбінувати багато хороших методів, що в сумі дасть круті результати для бізнесу.

Радий поспілкуватися в коментарях з усіма, хто вважатиме матеріал цікавим. Запитати можна мені особисто в телеграма. Також я поділяюся своїми думками про AI/стартапи у своєму telegram каналі - welcome 🙂

Джерело: habr.com