Привет! Меня зовут Артём, я руковожу командой эффективности рекламы в Ozon. Наша задача состоит не только в том, чтобы реклама приносила деньги компании, заказы рекламодателям и была релевантной для пользователей, но и в том, чтобы сделать запуск рекламных кампаний удобным и эффективным для рекламодателей. 

В статье я расскажу о том:

• как мы пришли к идее автоматического управления ставками в рекламных кампаниях на платформе;

• какие алгоритмы оптимизации и машинного обучения нам помогли;

• как построена архитектура автобиддера;

• как выкатить новый продукт в прод и измерять эффективность.

Пара слов о том, как устроено поисковое продвижение в Ozon

Как и на большинстве e-commerce сайтов, у пользователя есть возможность найти подходящие товары по текстовому описанию. После ввода текста под капотом происходит запрос в поисковый индекс, который возвращает набор релевантных товаров. Для глубокого технического погружения в принцип работы поиска в Ozon рекомендую прочитать статью: Как мы делали свой поиск в Ozon: эволюция архитектуры от SQL до O2.

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

Рекламодателю для запуска рекламы товара sku нужно определить ставку в рублях bid(sku) за получение целевого действия. На площадке доступны несколько форматов оплаты рекламы: CPM (cost per mille: за показ), CPC (cost per click: за клик), CPO (cost per order: за заказ). Замечу, что просто по размеру ставки товары из разных форматов ранжировать не получится, ведь ценность у целевых действий разная. Поэтому для каждого пользовательского запроса проводится аукцион. Скор товара для участия в нём определяется по следующей формуле: score(sku, query) = bid(sku) * p_target(sku, query), где p_target — вероятность целевого действия после показа рекламы, которая оценивается моделями машинного обучения с использованием информации о товаре sku и контекста пользовательского запроса query (информация о пользователе, запросе, категории товара, времени и т. д.). Ранжирование происходит по значению полученных скоров score(sku, query), то есть математическому ожиданию рекламной прибыли с показа товара пользователю. При выигрыше аукциона и получении товаром sku необходимого целевого действия площадка списывает с рекламодателя плату bid(sku).

Для простоты будем в дальнейшем считать, что рекламный аукцион состоит только из CPM-товаров, — тогда ранжирование в аукционе происходит по размеру ставки за показ, ведь p_target(sku, query) = 1 в случае показа. Выше будет стоять товар того рекламодателя, который готов заплатить больше за его показ по тому или иному запросу.

Пара слов о том, как устроен запуск рекламной кампании в Ozon для рекламодателя

Процесс заведения рекламной кампании состоит из следующих шагов:

• выбираем список товаров, которые необходимо продвигать;

• указываем дневной бюджет, который готовы тратить на рекламу;

• указываем ставки за показ для каждого товара.

После, следим за эффективностью рекламной кампании (как минимум за тем, что реклама окупается, товары находятся на высоких позициях в выдаче по релевантным запросам) и при необходимости корректируем ставки.

Кажется, что такой процесс не совсем удобен рекламодателям, потому что:

• лишь крупный бизнес хорошо понимает, сколько он готов тратить на рекламу;

• число товаров может достигать нескольких сотен, а иногда и тысяч на кампанию;

• непонятно, как выбрать ставки так, чтобы не потратить весь дневной бюджет за минуты;

• непонятно, как выбрать ставки так, чтобы в итоге реклама окупила вложения.

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

Описание задачи

Автоматическое управление ставками — достаточно распространённая задача в индустрии. Статьи об этом можно найти по ключевым словам auto bidding и budget pacing.

Делюсь рассказом бывших коллег о реализации алгоритма ВКонтакте (привет, Дима и Даша!) и докладом команды Яндекс Директа.

Об этой и других задачах в области Computational Advertising также можно почитать в монографии: Display Advertising with Real-Time Bidding (RTB) and Behavioural Targeting.

Математически это можно сформулировать как задачу оптимизации с ограничениями: максимизировать число показов товаров рекламной кампании с учётом ограничения на дневной бюджет. Давайте подойдём к ней как к задаче комбинаторной оптимизации, а именно как к некой вариации задачи рюкзака (Multiple-Choice Knapsack Problem). Есть N предметов, у каждого есть стоимость и вес, и каждый принадлежит к одному из M классов. Требуется выбрать по одному предмету из каждого класса таким образом, чтобы их стоимость была максимальна, а суммарный вес не превышал объём рюкзака. Проводя аналогии: объём рюкзака — дневной бюджет; предметы — рекламные ставки для участия в аукционах; класс предмета — пара «товар — запрос», по которой проводится аукцион; ценности предметов — количество показов, которое мы ожидаем получить с такими ставками. 

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

Дизайн нашего алгоритма

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

Разберём алгоритм построения на примере игрушечной рекламной кампании c двумя товарами (пусть это будут пара чёрных кроссовок Adidas и мужская футболка с фотографией кота) и дневным бюджетом в 1000 рублей. После ранжирования по ставке таблица будет выглядеть так:

В поле «Ожидаемый накопленный бюджет» суммируются траты для текущей тройки «товар — запрос — ставка» и всех троек из данной рекламной кампании с более низкими ставками. Зелёные тройки проходят все ограничения и попадают в рюкзак. А вот на более дорогой запрос «премиум футболка» мы не сможем выставить ставку — не хватит бюджета. 

Таким образом, оптимальные ставки для рекламной кампании будут выглядеть так:

Давайте подробнее рассмотрим процесс построения такой таблицы. Что необходимо для выбора множества кандидатов для рюкзака?

Начнём с таргетинга, назовём так наборы запросов, релевантных товарам из кампании. Как уже было упомянуто, за рекламными кандидатами продакшен-сервис рекламы ходит в отдельный поисковый движок, который на лету подбирает подходящие под все критерии товары для каждого запроса пользователя. Подробнее об устройстве поискового индекса и его внутренних структурах данных можно почитать в статье Устройство поисковых систем: базовый поиск и инвертированный индекс.

Структура поискового индекса устроена таким образом, чтобы быстро решать задачу поиска товаров для определённого текстового запроса, но для решения обратной задачи поиска всех запросов для товара она не приспособлена. Соответственно, полное множество текстовых запросов, по которым товар может попасть в поисковую выдачу, нам неизвестно. Для того чтобы его получить, нам фактически нужно было бы инвертировать инвертированный индекс обратить поисковый индекс рекламного движка. Сделать это можно с помощью методов поиска ближайших соседей, заранее построив векторы запросов и товаров в едином векторном пространстве (например, с помощью связки модели семантической близости DSSM, обученной на тексте запроса и тексте атрибутов товара, и библиотеки для быстрого векторного поиска FAISS) или с помощью эвристик (например, использование всех текстовых запросов из истории показов товара и запросов, похожих на них).

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

Основные факторы, влияющие на число показов товара:

• трафик на запрос ограничен как минимум количеством посетителей сайта;

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

  • поисковые фильтры (цвет, размер, цена и т. д.);

  • геолокация пользователя (товар может не доставляться туда, где он находится);

  • наличие на складе (товар банально может закончиться);

  • ограничения бюджета;

• размер ставки за показ. Число показов по запросу увеличивается при росте ставки за целевое действие, что логично: чем выше ставка, тем более высокую позицию в выдаче сможет получить товар.

Попробуем оценить каждый из этих факторов в отдельности.

Оценка трафика на различные поисковые запросы похожа на задачу прогнозирования спроса в e-commerce и ритейле с одной оговоркой: вместо числа заказов различных товаров мы будем оценивать число уникальных пользовательских сессий для каждого запроса. Кажущаяся простота задачи обманчива, поскольку на трафик влияет много факторов: сезонные, географические, новостные. 

С поисковыми ограничениями всё ещё сложнее: фактически мы хотим решать задачу регрессии — предсказание доли участия товара в аукционе по релевантному запросу. В литературе рассматриваются разные подходы. Например, в статье Ad Impression Forecasting for Sponsored Search для оценки трафика на запрос предлагается использовать Dynamic Linear Models, а для оценки ограничений участия товара в аукционе — продвинутые эвристики. Мы начали с достаточно простых решений, но активно двигаемся в сторону ML. Благо данных для этого достаточно: признаки товаров, запросов, категорий, парные признаки по нескольким срезам и т. д.

Подведём промежуточный итог: мы знаем, по каким запросам товар (sku) может попасть в поисковую выдачу (Targeting(sku)), знаем трафик на запрос (Traffic(query)) и учитываем ограничения поиска (pRatio(sku, query)). Если собрать все факторы в формулу, то получим оценку максимально доступного товару поискового трафика:

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

Переходим к оценке вероятности показа товара по запросу в зависимости от ставки в аукционе. В литературе задача известна под алиасом Bid Landscape Forecasting. Один из наиболее распространённых подходов: в предположении, что распределение ставки принадлежит определённому семейству, оцениваются параметры распределения ставок по историческим логам аукционов при максимизации правдоподобия выборки.

Итоговая оценка кандидатов для рюкзака строится так:

• для каждого товара из рекламной кампании добавляются запросы из прогнозируемого таргетинга;

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

• ожидаемое число показов считается в разрезе тройки «товар — запрос — ставка»:

  

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

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

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

Согласно исходному алгоритму, более высокая ставка на запрос «футболка мужская» приведёт к выкупу большего количества показов, а значит, мы возьмём в рюкзак именно её. Но увеличение ставки для этого запроса приводит к тому, что общее число показов кампании уменьшается с 4600 до 4500, ведь если бы мы не повысили ставку для этого запроса, то смогли бы выкупить показы по запросам «футболка» и «кроссовки». То есть выгоднее использовать низкую ставку, хоть более высокая и подходит под условия алгоритма и вписывается в ограничения задачи.

Для решения проблемы можно ранжировать прогнозы не по размеру ставки, а по эластичности аукциона — ценности, которую получит кампания при увеличении ставки на данный текстовый запрос. Под этой ценностью мы понимаем отношение изменения объёма трат к изменению числа показов при повышении ставки на запрос.

Небольшой блок для любителей математики и строгих доказательств

Разберёмся с эластичностью аукциона и адаптацией алгоритма для ранжирования ставок по этому показателю.

Начнём с вводных. Пусть bid_i и bid_j — ставки на запрос, где bid_i < bid_j.Из условия монотонности аукциона, число показов за ставку views_i < views_j.

Назовём эластичностью аукциона для пары ставок bid_i и bid_j отношение изменения объёма трат к числу показов при повышении ставки c bid_i до bid_j для текстового запроса: 

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

Рассмотрим основные моменты:

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

• Алгоритм должен обеспечивать монотонность по ставке: на каждой новой итерации либо в рюкзак добавляется ставка на новый запрос, либо увеличивается ставка существующего. В случае ранжирования по эластичности с помощью исходного алгоритма монотонность может нарушиться. Это можно заметить в примере выше с запросом «футболка мужская»: при изменениях ставки 0,15 < 0,25 < 0,35 эластичность не монотонна:

Можно ли упростить алгоритм? Оказывается, да: можно сохранить монотонность по ставкам, выбросив те из них, которые заведомо неоптимальны. 

Рассмотрим тройку ставок для запроса bid_i < bid_j < bid_k:

Следовательно: 

Из условия монотонности аукциона следует, что: 

Следовательно:

А значит, из кандидатов можно смело удалить все ставки, для которых после упорядочивания по значению ставки нарушается монотонность эластичности аукциона.

Архитектура системы

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

Для ускорения расчёта оптимальных ставок для новых и отредактированных (изменение набора товаров или лимита дневного бюджета) кампаний мы решили разделить систему доставки оптимальных ставок до прода на две части:

1. Реалтайм-сервис, который аппроксимирует оптимальные ставки для быстрого старта новой или отредактированной кампании.

2. ETL-пайплайн, ежедневно пересчитывающий оптимальные ставки по недельным логам аукционов.

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

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

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

Логи показов товаров со всеми параметрами автобиддера отправляются в ClickHouse через топик Kafka и используются для анализа качества работы системы.

Пара слов о том, как мы выкатывали проект в прод

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

После фаз активного ресёрча, аналитики и разработки появились важные вопросы: как оценить качество нового продукта и как выкатывать его на реальных пользователей?

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

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

Другие варианты, которые мы отвергли:

• разбиение экспериментальных группы по кампаниям с товарами одной категории: в теории это должно помочь изолировать группы в рамках аукционов;

• использование метода тройной разности: тут важно отметить, что долгоживущих кампаний не так много и в них присутствует систематический баес (если кампанию долго не отключают, возможно, её результаты слишком хороши и при ручном управлении).

Итог: проводить А/Б-эксперименты для автобиддеров тяжело по нескольким причинам:

• нужно следить за корректностью разбиения кампаний по группам;

• срок жизни рекламных кампаний слишком короткий;

• сложно изолировать аукционы для контрольной и тестовой групп.

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

Доступ к продукту открывали итерациями по N кампаний: следили за метриками суммарного бюджета, роста кампаний и оттока рекламодателей. Путь от MVP на коленке до поддержки продукта для 100% рекламодателей на проде занял примерно шесть месяцев.

После релиза мы продолжаем итеративно улучшать продукт, и сейчас в процессе разработки находится часть сервиса, которая позволить запускать А/Б-эксперименты на основе аналога метода тройной разности. Есть надежда, что это позволит нам ускорить выкатку новых фич.

Метрики продукта

• Доля в CPM выручке в поиске ~75%

• Cредний ДРР кампаний на 36% ниже, чем у кампаний с ручными ставками

• Средняя ставка кампаний на 27% выше, чем у кампаний с ручными ставками

• Средний CR товаров на 33% выше, чем у кампаний с ручными ставками

• Средняя утилизация бюджета на 30% выше, чем у кампаний с ручными ставками

Что дальше

Хоть мы и проделали большую работу, впереди ещё долгий путь:

• отказ от реалтайм-сервиса в пользу Spark Structured Streaming подхода

• замена эвристик для оценки факторов прогноза eViews ML-моделями;

• рост масштабируемости за счёт использования логов показов вместо полного лога аукционов со всеми кандидатами на выдачу;

• развитие культуры А/Б-экспериментов с разными версиями биддера;

• мониторинг, метрики, разбор корнер-кейсов и фидбэка от пользователей.

P.S: Мы активно растём и ищем:

• ML-инженеров для улучшения релевантности рекламы и разработки автобиддеров

• Go-разработчиков для сервисов эффективности рекламы.

Если у вас есть опыт решения подобных задач или большой интерес к ним, то приходите к нам, пишите в комментариях или в Telegram: @artem_panin.