Всем привет! Меня зовут Вардан Манучарян, я аналитик в команде Монетизации Авито, и мы отвечаем за механику алгоритмов продвижения, то есть управляем порядком, в котором пользователи видят объявления. Для этого нам нужно отслеживать, как изменения в ранжировании влияют на бизнес и покупателей. В этой статье расскажу про интерливинг, — метод, который помогает корректно проводить A/B-тесты с изменением ранжирования. Статья будет интересна аналитикам, которые проводят много A/B-тестов.
В этой статье:
Что тестирует наша команда
Авито — большая площадка объявлений. Мы работаем для разных пользователей: от обычных людей, которым надо продать лишние вещи, до крупных компаний. Если продавец захотел сделать свои объявления заметнее, он начинает платить площадке за каждый уникальный клик по объявлению — это монетизация. Сумма платежей за все клики — выручка площадки.
Покупатели ищут в Авито товары, для чего пишут в строке поиска нужные слова, а система показывает подходящие объявления. Предложения продавцов выстраиваются не в случайном порядке, а ранжируются с учётом множества условий: релевантности запросу, свежести объявления, подключённой монетизации и других условий.
Иногда условия сервисов меняются, добавляются новые функции или, наоборот, что-то исчезает. Мы учитываем эти изменения и корректируем работу алгоритма ранжирования. Прежде чем запускать новый алгоритм в прод, всё надо протестировать и убедиться, что свежая версия работает правильно. Чтобы оценить реальное влияние изменений, нужен точный метод, который покажет цифры без смещений. Посмотрим, что можно для этого использовать и каким методом пользуемся мы.
Стандартные методы измерений
Базовые способы — это A/B-тесты, в которых можно попробовать сравнить два ранжирования — с изменениями и без них.
Допустим, Авито хочет дать частным лицам (далее для простоты будем называть их частниками) преимущество перед крупными продавцами. Чтобы это сделать, настроили ранжирование так, что объявление большого бизнеса находятся ниже предложений частников. Теперь надо проверить, насколько корректно всё работает. В реальной жизни мы будем отслеживать несколько метрик, но в этой статье для простоты поговорим только о выручке. Сначала оценим стандартные A/B-тесты.
A/B-тест для покупателей. Для начала мы делим всех покупателей на две части:
Группа A — покупатели, которым показываем текущее ранжирование без изменений.
Группа B — покупатели, которые видят ранжирование, где объявления от частников попадаются выше.
Мы многократно (на массиве из миллионов покупателей) повторяем тест, затем считаем выручку в группах и смотрим, есть ли расхождение.
➕ Метод очень чувствительный, потому что покупателей на Авито очень много.
➖ Невозможно обнаружить изменения в поведении продавца. Например, если у частников увеличится retention, наша выручка вырастет, но мы этого в тесте не увидим. Дело в том, что у каждого продавца в половине случаев объявление будет показываться как обычно, а в другой половине — выше конкурентов, поэтому они не заметят эффекта в A/B.
A/B-тест для продавцов. В этом случае мы разделяем на контрольную и тестовую группу продавцов. Если частник попадёт в тест, мы будем показывать его выше в выдаче для всех покупателей.
➕ Мы можем посчитать выручку на каждого продавца и увидим изменения их поведения.
➖ Возникают сетевые эффекты, из-за которых оценка получается смещённой и не совсем корректной.
Что я имею в виду под сетевым эффектом
Допустим, у нас есть выдача из 6 элементов. Числа в ячейках — ожидаемая выручка с объявления, если на него кликнут. Цветные ячейки — частники.
В контрольной группе (первый столбик) они находятся внизу. Суммарная выручка с выдачи: 0,4+0,5+0,6+0,7=2,2 рубля.
Если раскатить изменения на всех, то все частники окажутся в топе, а выручка вырастет: 0,6+0,7+0,8+0,9=3 рубля. Посчитаем аплифт: 3/2,2= 1,36, то есть 36%.
Во время эксперимента частники в тестовой группе (в красных ячейках) принесли такую выручку: 0,8+0,9=1,7. У контрольной группы (в синих ячейках) она будет 0,4+0,5=0,9. Посчитаем аплифт: 1,7/0,9=1,88 то есть 88%. Вдвое больше, чем на самом деле — тест показывает некорректные числа.
Кластерный тест. В нём мы делим продавцов с покупателями на несколько групп, которые не пересекаются между собой. В тестовых кластерах изменения раскатаны на всех. Считаем выручку на продавца и разницу между контрольными и тестовыми кластерами.
Например, в Авито мы делаем так: разбиваем все регионы на тест и контроль. В одной половине регионов — изменения, в другой — контрольная группа.
➕ Можем обнаружить изменения на продавца и покупателя, и минимальный сетевой эффект.
➖ Кластеров очень мало, поэтому получается очень большой MDE, который мешает увидеть изменение выручки.
➖ Кластеры сложно подбирать.
Как выглядит идеальное честное сравнение. Это тест для каждого покупателя, в котором мы делаем следующее:
Показываем контрольную выдачу и измеряем выручку.
Стираем память 🪄
Показываем тестовую выдачу и снова измеряем выручку.
Считаем разницу между контролем и тестом.
Только так можно увидеть несмещённый аплифт. Разумеется, стереть память невозможно, но мы используем метод, который максимально симулирует этот процесс. Рассмотрим его подробнее.
Новый подход: counterfactual Interleaving
Это метод сравнения двух систем ранжирования, при котором пользователю показывается перемешанный результат работы двух алгоритмов. Быстро, безопасно и очень чувствительно к малым изменениям.
Чтобы запустить тесты с новым подходом, мы делаем вот что:
1️⃣ Заранее делим всех продавцов на две группы: контрольная и тестовая.
2️⃣ Мы генерируем контрольное (R0) и тестовое (R1) ранжирование для каждого покупателя, когда он ищет что-то в Авито. В обоих ранжированиях будут объявления продавцов из обеих групп.
3️⃣ Формируем смешанное ранжирование. Для контрольных продавцов берём позицию из контрольного синего столбика, а для тестовых — из красного тестового.
Например, у нас есть объявление от продавца №3. Мы определили его как контрольное (надпись синего цвета), поэтому в смешанном ранжировании оно займёт такое же место, как и в контрольной группе. Также мы берём объявление от продавца №2, но оно тестовое (красное). Значит, мы присваиваем ему место из тестового ранжирования. Также поступаем с другими объявлениями, у которых нет коллизии, при которой на одно место на равных правах претендуют два объявления.
Проблема коллизий. На третью позицию претендуют два объявления: от продавца №4 из тестовой группы и от продавца №1 из контрольной. Мы не можем поместить два объявления на одну позицию, поэтому подбрасываем монетку, которая устроена по сложному алгоритму. Она определяет, кому достанется место. Оставшиеся вакантные места заполняются объявлениями, которые в монетке проиграли. В итоге получаем смешанные результаты поиска.
Нюанс
В результате разрешения коллизии объявлению достаётся случайная позиция. Поэтому, чтобы сделать смешивание честным, мы поддерживаем два инварианта:
1️⃣ Относительный порядок объявлений в каждой выдаче. Если в контрольном ранжировании контрольное объявление А выше контрольного объявления Б, то в смешанной выдаче А должно быть выше Б. Аналогично для теста.
2️⃣ Шум от коллизий должен быть одинаковым для контрольной и тестовой групп. Тогда разница в выручке между ними будет обусловлена только самими ранжированиями, а не тем, как мы смешиваем.
Теоретически, мы получим честный аплифт, если будем соблюдать эти инварианты. Подробнее можно прочитать в статье Producer-Side Experiments Based on Counterfactual Interleaving Designs for Online Recommender Systems.
Итак, мы получили финальную выдачу, но пока не верим, что всё сработало правильно. Ниже расскажу, как всё проверяли.
Проверка подхода
Мы оценивали корректность с помощью инструмента офлайн-приёмки — симуляции выдачи Авито. Взяли актуальный пул запросов и для каждого посмотрели на текущее и тестовое ранжирование. Для всех объявлений рассчитали ожидаемую выручку и CTR, поэтому смогли подсчитать ожидаемый аплифт.
Чтобы доверять результату, нужно было убедиться в двух вещах:
1. Мы корректно смешиваем. Инварианты работают и мы не вносим лишнего шума при разрешении коллизий.
2. Выбранные инварианты дают достаточно честную оценку. Итоговый аплифт в метриках окажется настоящим.
Чтобы всё проверить, мы провели четыре теста с помощью офлайн-приёмки и ещё один онлайн.
A/A-тест. В офлайн-приёмке сделали тестовое и контрольное ранжирование для 3 тысяч запросов. Затем сэмплировали случайные 300 запросов без возвращения и на них посчитали выручку на продавца. После сравнили среднее между контрольной и тестовой группами через t-test и посчитали p-value. Повторили упражнение 10 тысяч раз и оценили, как распределился p-value. Доверительный интервал для уровня значимости 0.05 получился 0.03–0.04, что чуть меньше реальных 0.05. То есть мы контролируем FPR.
Зависимость от доли продавцов. Мы проверили, влияет ли на метрики доля продавцов в тестовой группе. Для этого провели серию тестов, в которых доли продавцов разнились от 5 до 95%. Проводили тестирование с 1 тыс запросов, для каждой группы считали аплифт выручки, а затем строили доверительный интервал. Поскольку интервалы во всех группах перекрываются, интерливинг неизменно приводит к одному и тому же значению метрики. При этом чем больше дисбаланс между долями теста и контроля, тем ожидаемо выше уровень шума в оценке.
Распределение шума от коллизий в контроле и тесте. Мы запустили интерливинг тысячу раз, нашли все коллизии и выявили шум от смешивания. Когда сравнили результаты в контрольной и тестовой группах — увидели, что уровень одинаковый. Это подтверждает, что смешивание работает корректно.
Совпадение с истинным аплифтом. В оффлайне мы можем повторить сравнение со стиранием памяти: берём контрольную и тестовую выдачу, считаем выручку и получаем истинный аплифт. Затем запускаем интерливинг для тысячи запросов и сравниваем результаты. Интерливинг совпадал с истинным значением в 100% случаев.
Онлайн-валидация. Провели два параллельных онлайн-теста, в котором продвигали частников: A/B-тест для покупателей и интерливинг для продавцов. Затем посчитали аплифты и выяснили, что значения совпали с точностью до доверительного интервала.
Тестировали в течение одной недели, поэтому долгосрочными изменениями в поведении продавцов пренебрегли.
Достоинства и недостатки подхода
Главный плюс состоит в том, что в нашем тесте нет сетевых эффектов. В результате получаем честную оценку и при этом сильно улучшаем MDE. В кластерном тесте MDE выручки 8.5%, а в интерливинге — 2.5%.
Пара дополнительных бонусов:
➕ Можем измерять поведение продавцов и рассчитывать метрики.
➕ Получаем несмещённую оценку и сохраняем видимость на уровне объявления.
Главный минус — не удалось до конца убрать сетевой эффект: соседние объявления в выдаче влияют друг на друга. Мы считаем этот эффект малозначительным, потому что дальнейшие тесты показали честность оценки интерливинга.
Парочка недостатков:
➖ Нельзя тестировать новые продукты, поскольку можем измерить только изменение ранжирования.
➖ Подходит только для аддитивных метрик.
Кратко о методе counterfactual Interleaving
Мы в Авито применяем сложные алгоритмы для ранжирования объявлений. Изменения проверяем с помощью метода counterfactual Interleaving чтобы достичь максимальной точности измерений.
Интерливинг показывает пользователю перемешанную выдачу от двух алгоритмов, благодаря чему можно получить несмещённую оценку.
Чтобы повысить честность мы сохранили два инварианта: относительный порядок объявлений в каждой выдаче и равную долю шума в группах.
Мы проверили метод и выяснили, что интерливинг корректно смешивает объявления из тестовой и контрольной группы, а в результате получается чистый аплифт.
Больше интересного про A/B-тесты можно найти в канале «Коммуналка аналитиков». Аналитики Авито лично пишут туда живые посты про свои будни. Подписывайтесь!
