Привет, Хабр! Меня зовут Ян Пиле, руковожу в MAGNIT TECH направлением развития алгоритмов доступности товаров. Задача моей команды: сделать так, чтобы в магазине, куда вы зашли за своим любимым майонезом, он с большей вероятностью оказался на полке. А если не оказался – чтобы сотруднику магазина как можно быстрее прилетело задание: «проверь, почему именно этой позиции сейчас нет, и, если возможно, верни её обратно».

Мы уже дважды писали про OSA (On-Shelf Availability – уровень доступности товара на полке). В статье «Как OSA превращает пустые полки в полные корзины?» рассказывали про продуктовый контекст: зачем эта история нужна бизнесу и почему «товар числится в системе» и «товар реально лежит на полке» – это два совершенно разных утверждения. А в статье «Когда 0 в продажах — аномалия? CUSUM для поиска проблем в ритейле» мы подробно разбирали один из рабочих алгоритмов команды. В этот раз я хочу пройтись по всему стеку детекции целиком – от самых простых правил до А/Б-тестов, в которых приходится бороться с зависимыми наблюдениями.

Что такое OSA и почему «нет товара» — это совсем другое «нет»

Доступность – то насколько легко вы можете найти на полке оффлайн-магазина тот товар, за которым пришли. Формулировка очевидная, а задача – нет, потому что сценариев, при которых товара «нет», неприятно много. Самый скучный из них – товара нет физически: кончился, ещё не привезли. Бывает, что товар числится на балансе, а по факту его нет – это так называемый виртуальный остаток, честная и повседневная беда розницы. Бывает, что товар есть, но без ценника или с неправильным штрихкодом – и для покупателя это тоже «нет». Бывает, что в коробке недосчитались одной бутылки. Бывает, что товар в магазине есть, но лежит где-то в глубине склада, и, чтобы понять, что он там есть, надо пойти и порыться в коробках. Про этот зоопарк сценариев мы подробно писали в первой из двух статей – там же есть и подробный разбор того, почему OSA правильнее называть «последней милей» доступности.

Отдельно стоит история «ушедшего покупателя». Если, к примеру, человек два раза подряд не нашёл свой любимый майонез, то на третий раз он может не прийти в магазин вовсе. Мы теряем не одну конкретную продажу, а покупателя целиком – и это, пожалуй, самый дорогой сценарий из всех.

Почему не всё решается камерами

Магазинов «у дома» у нас около 21 тысячи, гипермаркетов – почти 470. В каждом магазине в среднем 5 тысяч товарных наименований. По всей этой сети ежедневно проходит порядка миллиона операций с товарами. Если перемножить эти числа, то получается объём, после которого довольно быстро хочется закрыть ноутбук.

Самая очевидная идея, которая приходит в голову при таких вводных: навесить в каждом магазине камер, натренировать большую CV-модель (CV – computer vision, компьютерное зрение) и просто смотреть на полки. Красиво до того момента, когда начинаешь считать. Несколько камер на магазин, умноженные на двадцать с лишним тысяч торговых точек, плюс вычислительные мощности под ежедневную обработку видео, плюс эксплуатация всего этого. К этому добавляется региональная неоднородность ассортимента, ротация упаковок, необходимость непрерывно размечать фотобанк. Словом, идея хорошая в витрине, но её трудно масштабировать на всю сеть.

Поэтому мы сделали ставку на табличные данные – продажи, остатки, характеристики магазинов и товаров. Это дешевле, интерпретируемо и хорошо масштабируется. Сигнал по таким данным получается зашумлённым, но с шумом, как выяснилось, вполне можно жить, если грамотно его обрабатывать.

Как алгоритм попадает в магазин

Снаружи всё выглядит так: каждый день мы смотрим на продажи и остатки, прогоняем через набор независимых детекторов, из всего, что они выловили, оставляем самое важное и отправляем в магазин в виде заданий. Задание – это конкретная товарная позиция, которую сотруднику нужно пойти и проверить.

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

Важное ограничение: сотрудников в магазине ограниченное количество, и у них помимо наших заданий хватает своей работы. Поэтому количество сигналов в день жёстко ограничено: магазин «у дома» получает порядка 15 сигналов в сутки, гипермаркет – около 50. Числа взяты не с потолка, они отражают реальную нагрузку на персонал и баланс «минимум трудозатрат – максимум эффекта».

У этого ограничения есть неочевидное следствие: задача «найти все проблемы» автоматически превращается в задачу «выбрать 15 (или 50 – для гипермаркетов) самых важных». И вся архитектура системы построена вокруг этого соображения.

Из чего состоит стек детекции

Сигналы генерирует не один «мегамозг», а несколько независимых источников. Каждый из них ловит свой тип проблем, и в таком виде система заметно надёжнее, чем один большой чёрный ящик.

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

Источников сигналов у нас пять: эвристики, отклонение дискретности продаж, CUSUM, прогноз самовосстановления продаж и несколько внешних каналов. По ним я и пойду дальше по порядку.

Эвристики

Самый простой слой – обычные бизнес-правила. Быстрые, понятные, их легко объяснить коллегам из бизнеса, и они хорошо ловят очевидные вещи. Недостаток тоже очевиден: покрытие у них небольшое. Если пытаться расширить эвристики до «ловим всё», то точность заметно проседает, поэтому имеет смысл держать их в узком, но надёжном коридоре.

Первый пример – истёкший срок годности. Если товар числится на балансе уже неприлично долго, то логично сходить и посмотреть, что с ним на полке. Второй пример – «корзина топ»: по магазину есть набор позиций, которые должны продаваться каждый день. Например, самое ходовое молоко в обычном магазине в спальном районе. Если по такой позиции один день нет продаж, это уже повод проверить полку. Никаких моделей, никакой статистики, один здравый смысл.

Эвристики закрывают часть сценариев, но далеко не все.

Отклонение дискретности продаж

Дискретность продаж – это насколько часто конкретная товарная позиция продаётся в конкретном магазине. Для одного товара «продаётся каждый день» – норма, для другого «продаётся раз в три дня» – тоже норма. Это значит, что одинаковый период «без продаж» для разных позиций совершенно разное значение, и один универсальный порог поверх всего не поставишь.

Берём товарную позицию и смотрим на её дискретность по группе похожих магазинов, чтобы было с чем сравнивать. Получается распределение: по горизонтали – редкость продаж, по вертикали – сколько магазинов попадает в каждую корзину. То, что оказалось в правом хвосте, – кандидаты на проблему.

Дальше мы корректируем порог по двум осям. Первая — базовый уровень продаж, его нам даёт ABC-анализ (классификация товаров по их вкладу в товарооборот), вторая – стабильность продаж, это уже XYZ-анализ (классификация по тому, насколько ровно идёт спрос). Попросту говоря, ABC отвечает на вопрос: «насколько эта позиция вообще значима», а XYZ – «насколько её продажам в принципе можно верить». После такой двойной поправки появляется та самая граница, за которой «дней без продаж больше, чем должно быть» превращается в сигнал.

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

CUSUM: когда ноль в продажах становится аномалией

Про этот алгоритм у нас целая отдельная статья в блоге, поэтому здесь я пройдусь только по сути.

CUSUM (cumulative sum) относится к семейству алгоритмов поиска точек разладки (changepoint detection). Идея простая: есть временной ряд, про который мы считаем, что он порождён каким-то распределением. В какой-то момент распределение меняется – например, средний уровень продаж резко падает. CUSUM нужен, чтобы это изменение аккуратно зафиксировать, со статистической интерпретацией.

Работает это у нас примерно так. Берём ряд продаж конкретной позиции в конкретном магазине. Сырые продажи неудобны – они «прыгают» из-за сезонности, праздников, промоакций, реакции на изменение цен. Поэтому мы нормируем ряд: коэффициенты сезонности и эластичности снимают значительную часть этого шума, и на выходе получается то, что можно сравнивать «само с собой» во времени. По этому нормированному ряду считаем CUSUM-статистику. Пока продажи идут плюс-минус как ожидается, она топчется около нуля. Как только продажи аномально проседают в ноль, статистика начинает накапливаться. Пробила критическое значение – фиксируем аномалию.

Одного локального ряда мало. Ноль в продажах может быть не из-за пустоты на полке, а по куче других причин: товар вышел из промоакции; его каннибализировала соседняя позиция; закончился сезон; в магазине в целом упал трафик. Поэтому каждую «пробившую» позицию мы дополнительно сверяем с магазинами-аналогами. Если у аналогов по этой же позиции ситуация нормальная, а здесь провал, значит проблема локальная и сигнал имеет смысл отправлять дальше. Если у аналогов та же картина, то, скорее всего, это общий эффект, и лезть туда незачем.

Прогноз старта продаж: куда не нужно идти

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

Отсюда ещё один блок в конвейере – прогноз самовосстановления продаж. Логика такая: берём остановившийся ряд, оцениваем его дискретность, собираем признаки и с помощью градиентного бустинга (CatBoost) отвечаем на вопрос: «насколько вероятно, что в пределах обычной для этого товара дискретности продажи начнутся сами?». Если вероятность высокая, то сигнал, скорее всего, обрабатывать не надо, в этом магазине и без нас всё под контролем. Если низкая – туда имеет смысл обращаться.

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

Внешние источники сигналов

Продажи – не единственный источник информации о том, что на полке что-то не так. Есть ещё минимум три канала, которые мы подмешиваем в общую копилку.

Первый – сборщики онлайн-заказов. Человек собирает заказ, не находит позицию и отмечает это в системе. Это не железобетонное доказательство проблемы: «не нашёл» может значить многое – от реально пустой полки до «не там посмотрел». Но игнорировать такой сигнал странно: если по товару один живой человек уже споткнулся, то это повод перепроверить.

Второй – внешние мерчандайзеры. Представитель бренда, например, приходит в магазин проверить свои позиции. По тому, что он нашёл или не нашёл, мы корректируем нашу картину.

Третий – распознавание изображений. У нас есть отдельный механизм, который по фотографиям полок понимает, что на них лежит. Работает это не по всей сети и не как ядро всей системы, а как дополнительный слой. Показательный пример: мы собирались выдать сигнал по какой-то позиции, а на свежем фото с полки эта позиция спокойно стоит. Значит, сигнал можно не тратить.

Фильтрующая модель и копилка сигналов

Всё, что нашли предыдущие блоки, сваливается в общую копилку сигналов. Их заметно больше, чем наш дневной лимит, а значит, нужен слой, который отбирает самые перспективные. Эту роль играет отдельная фильтрующая модель: по каждому сигналу она выдаёт балл; сигналы с низким баллом отсекаются по порогу, остальные идут в приоритизацию и отправку. Схема «генерировать → скорить → фильтровать → ранжировать» – это именно то, что обычно делают, когда нужно отобрать самое ценное при ограниченном количестве действий.

Интересный нюанс заключается не в самой схеме, а в том, на чём эта модель учится. Естественный таргет – обратная связь от магазина: «сигнал подтвердился или не подтвердился». Но обратная связь зашумлённая: где-то сотрудник торопился, устал, ответил формально. Если учиться на таком таргете как есть, то модель унаследует этот шум.

Чтобы убрать часть шума, мы используем модификацию стандартного logloss. Отдельно у нас есть небольшой чистый срез данных – это контрольные походы (про них подробнее ниже): люди, которым можно полностью доверять, приходят и выполняют задания без лени и без хитростей.

Данных немного, полноценную модель на них не обучишь, но обучить небольшую вспомогательную «исправляющую» модель, которая по зашумлённому ответу пытается восстановить настоящий, – хватает. Дальше в функции потерь основного CatBoost на месте «настоящих ответов» подставляются уже восстановленные этой вспомогательной моделью значения – то есть мы честно учитываем, что исходные метки неидеальны. На наших данных такой подход даёт заметно лучшее качество, чем обучение напрямую на сырой обратной связи. Полную математику конструкции, наверное, стоит разложить в отдельной статье, здесь она сильно усложнит чтение.

Верификация: контрольные походы и «спасённые продажи»

Если доверять только обратной связи с линии, то получится анекдот про «всё работает, сигналы закрываются, метрики летят вверх». Поэтому поверх обратной связи есть несколько независимых слоёв проверки.

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

Второй – метрика «спасённые продажи». Идея такая: зафиксировали сигнал после периода без продаж; если после нашего вмешательства по этой позиции продажи начинаются в течение стандартной дискретности, то объём продаж за этот период мы засчитываем как эффект от вмешательства. Это прокси сверху, но на обычных А/Б-тестах она хорошо коррелирует с реальными денежными метриками по целевым группам товаров, и мы пользуемся ею как рабочим ориентиром.

Третий слой – частичная разметка через CV. Не вся сеть прогоняется через модель, но там, где поступает фото с полки, это ещё один независимый источник правды.

И поверх всего этого – протокол А/Б-тестов, который мы за последний год заметно отладили. Без него ни один новый компонент в прод не уезжает.

CV и немного про мошенничество

Теперь про «тонкий момент». Как только сотрудник отрабатывает задание и отмечает «всё в порядке, товар на полке», то с некоторой вероятностью ему прилетает дополнительная просьба: сфотографируй, пожалуйста, полку. Это фото уходит в CV-модель на проверку.

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

А вот настоящее мошенничество – другая история. Самый простой вариант: сфотографировать, например, потолок или что-то другое, максимально далёкое от полки. Бывают варианты поизобретательнее, но углубляться в зоопарк адверсариальных атак на CV (попыток обмануть модель нестандартными входными данными) я тут не буду – тема отдельная. Главное, что CV здесь не ядро всей системы, а именно инструмент дополнительной проверки, и в этой роли он работает хорошо.

А/Б-тесты: GEE и switchback

У нас 21 тысяча магазинов. Для привычных А/Б-тестов «на пользователях» это очень мало, для А/Б «на магазинах» это много, но с точки зрения статистики всё ещё не разгуляешься.

Первая мысль, которая приходит в голову: считать тесты на гранулярности магазин-день (или магазин-неделя) – так количество наблюдений сразу становится заметно больше. Подвох в том, что наблюдения, снятые с одного и того же магазина в разные дни, сильно скоррелированы между собой. Магазин сегодня и магазин завтра – это почти один и тот же объект. Если проигнорировать эту корреляцию и посчитать тест, как будто наблюдения независимые, то он что-то насчитает, но доверять ему будет тяжело.

Хорошая новость в том, что задачу давно решают. Эконометристы много лет пользуются методом обобщённых оценочных уравнений – Generalized Estimating Equations, GEE. Идея такая: вы берёте зависимые наблюдения внутри одного «кластера» (у нас это магазин во времени), явно задаёте вид корреляционной структуры внутри кластера и поверх этого аккуратно считаете эффект. Если структуру корреляций удалось угадать хоть сколько-нибудь разумно, то в пределах большого количества магазинов оценка сходится куда надо, и тест становится корректным.

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

Точность — это не только про алгоритм

Важная оговорка, которую легко упустить. Если смотреть на качество детекции с позиции «алгоритм и только алгоритм», то можно долго улучшать модель в изоляции и не понимать, почему показатели не меняются.

Пример из жизни. Вы идёте по магазину, вокруг чипсы, сладкое, бакалея, и где-то среди этого всего одиноко стоит бутылка кваса. Будете ли вы искать квас в этом месте? Скорее всего нет. Покупатель пройдёт мимо, не найдёт – и это зафиксируется как проблема доступности, хотя формально товар в магазине есть. Никакой алгоритм такое не починит, это вопрос к раскладке и мерчандайзингу.

Кроме того, на конечную точность влияет масса операционных обстоятельств: насколько подробно в ТСД прописаны сценарии отработки; насколько аккуратно сотрудник выполняет задание и фиксирует результат; насколько устойчива система к попыткам её обойти. Отдельно мы ведём метрику исполнительности: долю заданий, действительно выполненных по процессу. Всё это – часть качества OSA наравне с самой моделью, и если операционный слой сломан, то никакие красивые алгоритмы сверху его не починят. Эта мысль проходит красной нитью и в первой нашей статье, и здесь я её специально повторяю: без разговора про процесс честно оценить «точность» продукта невозможно.

Технологический ландшафт

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

Что дальше

Несколько направлений, которые сейчас у нас в работе:

CUSUM в классическом виде – штука принципиально одномерная: он смотрит на ряд продаж одной конкретной позиции. Но в реальности покупатель, который пришёл за гречкой и не нашёл её, вполне может уйти с рисом, – и с точки зрения магазина с продажами всё хорошо, просто спрос переключился. Одномерный CUSUM такую замену не увидит. У метода есть расширения на многомерные ряды, сейчас мы смотрим в эту сторону.

Второе направление – детекция отклонений по схеме «план – факт». Идея простая: строится прогноз продаж на ближайший горизонт, фактические продажи сравниваются с прогнозом, заметные расхождения идут в копилку сигналов. Сейчас такой подход у нас стоит в тесте.

Третье – попытка заменить бустинг на основе фильтрующей модели на TabM. Это свежее семейство нейронных сетей для табличных данных, относительно несложное по сравнению с прошлыми попытками прикрутить нейросети к таблицам. Интересно оно тем, что за счёт архитектуры умеет частично работать с шумом в данных, что для нашей зашумлённой обратной связи звучит уместно. Не факт, что на нашей задаче результат получится лучше текущего CatBoost, но попробовать стоит.

Четвёртое — пересмотр системы поиска магазинов-аналогов. Сейчас она простая и рабочая, но выглядит так, как будто если сделать embedding (векторное представление) магазина или связки «магазин – товар» и искать аналоги в этом пространстве, то можно получить более тонкую картинку. Это пока гипотеза, а не готовое решение, но направление разумное.

Итоги

На сегодня продукт интегрирован во всю сеть – и в магазины у дома, и в гипермаркеты. Исполнительность по заданиям держится в районе 96%. В «спасённых продажах» система приносит порядка 12 миллионов рублей в день. А/Б-тестов по разным компонентам у нас идёт около десяти в месяц.

OSA в нашей постановке – это не одна красивая модель, а набор довольно разных слоёв, каждый со своей ролью. Эвристики закрывают очевидное. Дискретность продаж и CUSUM ловят статистически значимые провалы. Прогноз самовосстановления отсекает места, куда можно не обращаться. Внешние источники добавляют поперечный взгляд. Фильтрующая модель выбирает самое ценное под дневной бюджет сигналов. А/Б-методология честно измеряет эффект, несмотря на зависимые наблюдения. А живой процесс в магазине – через ТСД, исполнительность, контрольные походы и фотоверификации – превращает всё это из чисел на дашборде в реальный товар на полке.

А как вы считаете А/Б на объектах с сильной внутренней корреляцией? И как работаете с зашумлённой обратной связью в обучающей выборке, где в ваших задачах проходит граница между зоной ответственности алгоритма и зоной ответственности процесса?