Как устроено A/B-тестирование в Авито
Всем привет. Меня зовут Данила, я работаю в команде, которая развивает аналитическую инфраструктуру в Авито. Центральное место в этой инфраструктуре занимает А/B-тестирование.
А/B эксперименты — ключевой инструмент принятия решений в Авито. В нашем цикле продуктовой разработки А/B-тест является обязательным этапом. Мы проверяем каждую гипотезу и выкатываем только позитивные изменения.
Мы собираем сотни метрик и умеем детализировать их до бизнес-разрезов: вертикали, регионы, авторизованные пользователи и т. д. Мы делаем это автоматизированно с помощью единой платформы для экспериментов. В статье я достаточно подробно расскажу, как платформа устроена и мы с вами погрузимся в некоторые интересные технические детали.
Основные функции платформы A/B мы формулируем следующим образом.
Другими словами, платформа помогает наиболее быстро принимать безошибочные решения.
Если оставить за скобками процесс разработки фич, которые отправляются в тестирование, то полный цикл эксперимента выглядит так:
Весь транспорт данных в цикле занимает один день. Эксперименты длятся, как правило, неделю, но заказчик получает инкремент результатов каждый день.
Теперь давайте погрузимся в детали.
Управление экспериментом
В админке для конфигурации экспериментов используется формат YAML.
Это удобное решение для небольшой команды: доработка возможностей конфига обходится без фронта. Использование текстовых конфигов упрощает работу и пользователю: нужно делать меньше кликов мышкой. Похожее решение используется A/B-фреймворке Airbnb.
Аллокация трафика
Для деления трафика на группы используем распространенную технику хеширования с солью.
Для устранения эффекта «памяти» пользователей, при запуске нового эксперимента, мы делаем дополнительное перемешивание второй солью:
Этот же принцип описан в презентации Яндекса.
Чтобы не допускать потенциально опасных пересечений экспериментов, мы используем логику, схожую со «слоями» в Google. О наших слоях я рассказывал в одном из докладов на Матемаркетинге-2019.
Попробую дать вам интуитивное понимание слоев. Представим сначала, что мы не допускаем пересечений экспериментов вообще. Т. е. все эксперименты «разводятся» с помощью независимых диапазонов хешей. Так жить долго не получится — слишком маленькая пропускная способность.
Другая крайность — на каждый эксперимент выделять свою соль. Все эксперименты будут ортогональны друг другу. Опытный аналитик или разработчик знает — это тоже не всегда хорошо. Потому что эксперименты могут конфликтовать на уровне кода. Тестовые группы двух разных экспериментов могут быть с друг другом «несовместимы», что негативно скажется на опыте пользователей, а значит и на результатах обоих экспериментов.
Поэтому нужно решение по-середине. Разрешить безопасные ортогональные пересечения и запретить опасные. Другими словами, нужно ограничить создание солей и наделить каждую собственной семантикой (платформа, страница, регион пользователя и т. д.). Так и получаются слои. Задача платформы А/Б — обеспечить, чтобы потенциально конфликтующие эксперименты всегда находились в одном слое. А эксперименты, располагающиеся на разных слоях, не конфликтовали друг с другом на уровне кода или отображения пользователю.
Сбор метрик
Сырые логи мы раскладываем в Vertica и агрегируем в таблицы-препараты со структурой:
Observations (наблюдения) — это, как правило, простые каунтеры событий. Наблюдения используются как компоненты в формуле расчета метрик.
Формула расчета любой метрики — это дробь, в числителе и знаменателе которой стоит сумма наблюдений:
В одном из докладов Яндекса метрики подразделялись на два типа: по юзерам и Ratio. В этом есть бизнес-смысл, но в инфраструктуре удобнее все метрики считать единообразно в виде Ratio. Это обобщение валидно, потому что «поюзерная» метрика очевидно представима в виде дроби:
Наблюдения в числителе и знаменателе метрики мы суммируем двумя способами.
Простым:
Это обычная сумма любого набора наблюдений: количество поисков, кликов по объявлениям и т. д.
И посложнее:
Уникальное количество ключей, в группировке по которым сумма наблюдений больше заданного порога.
Такие формулы легко задаются с помощью YAML-конфига:
Параметры groupby и threshold опциональны. Как раз они и определяют второй способ суммирования.
Описанные стандарты позволяют сконфигурировать почти любую онлайн-метрику, которую только можно придумать. При этом сохраняется простая логика, не накладывающая избыточную нагрузку на инфраструктуру.
Статистический критерий
Значимость отклонений по метрикам мы измеряем классическими методами: T-test, Mann-Whitney U-test. Главное необходимое условие для применения этих критериев — наблюдения в выборке не должны зависеть друг от друга. Почти во всех наших экспериментах мы считаем, что пользователи (Uid) удовлетворяют этому условию.
Теперь возникает вопрос: как провести T-test и MW-test для Ratio-метрик? Для T-test нужно уметь считать дисперсию выборки, а для MW выборка должна быть «поюзерной».
Ответ: нужно разложить Ratio в ряд Тейлора до первого порядка в точке 
:
Данная формула преобразует две выборки (числитель и знаменатель) в одну, сохраняя среднее и дисперсию (асимптотически), что позволяет применять классические стат. тесты.
Похожую идею коллеги из Яндекса называют методом линеаризации Ratio (выступления раз и два).
UPD. Для расчета дисперсии Ratio и применения t-теста можно сразу воспользоваться Дельта-методом. При большом объеме данных это куда более простое решение, т. к. необходимо лишь сделать три простые агрегации: сумма числителя и знаменателя отдельно, сумма их квадратов, и сумма их попарных произведений.
Производительность при масштабировании
Использование быстрых для CPU стат. критериев дает возможность проводить миллионы итераций (сравнений treatment vs. control) за считанные минуты на вполне обычном сервере с 56 ядрами. Но в случае больших объемов данных производительность упирается, в первую очередь, в хранение и время считывания с диска.
Расчет метрик по Uid ежедневно порождает выборки общим размером в сотни миллиардов значений (ввиду большого количества одновременных экспериментов, сотен метрик и кумулятивного накопления). Каждый день выгребать такие объемы с диска слишком проблематично (несмотря на большой кластер колоночной базы Vertica). Поэтому мы вынужденно сокращаем кардинальность данных. Но делаем это почти без потери информации о дисперсии с помощью техники, которую называем «Бакеты».
Идея проста: хешируем Uid’ы и по остатку от деления «разбрасываем» их на некоторое количество бакетов (обозначим их число за B):
Теперь переходим к новой экспериментальной единице — бакет. Наблюдения в бакете суммируем (числитель и знаменатель независимо):
При таком преобразовании условие о независимости наблюдений выполняется, значение метрики не изменяется, и легко проверить, что и дисперсия метрики (среднего по выборке наблюдений) сохраняется:
Чем больше бакетов, тем меньше информации теряется, и тем меньше ошибка в равенстве. В Авито мы берем B = 200.
Плотность распределения метрики после бакетного преобразования всегда становится схожа с нормальным.
Сколь угодно большие выборки можно сокращать до фиксированного размера. Рост в количестве хранимых данных в таком случае лишь линейно зависит от количества экспериментов и метрик.
Визуализация результатов
В качестве инструмента визуализации мы используем Tableau и веб-вью на Tableau Server. У каждого сотрудника Авито есть туда доступ. Следует отметить, что Tableau с задачей справляется хорошо. Реализовать аналогичное решение с помощью полноценной бэк/фронт разработки было бы куда более ресурсоемкой задачей.
UPD. С ростом данных Табло-сервер становится либо слишком медленным, либо слишком дорогим. Рекомендую сразу вложиться в визуализацию на вебе собственными руками.
Результаты каждого эксперимента — это простыня из нескольких тысяч чисел. Визуализация обязана быть такой, чтобы минимизировать неправильные выводы в случае реализации ошибок I и II рода, и при этом не «проморгать» изменения в важных метриках и срезах.
Во-первых, мы мониторим метрики «здоровья» экспериментов. Т. е. отвечаем на вопросы: «Поровну ли участников «налилось» в каждую из групп?», «Поровну ли авторизованных или новых пользователей?».
В случае статистически значимых отклонений соответствующие клеточки подсвечиваются. При наведении на любое число отображается кумулятивная динамика по дням.
Главный дашборд с метриками выглядит так:
Каждая строка — сравнение групп по конкретной метрике в конкретном разрезе. Справа — панель с фильтрами по экспериментам и метрикам. Снизу — панель фильтров по разрезам.
Каждое сравнение по метрике состоит из нескольких показателей. Разберем их значения слева направо:
1. MDE. Minimum Detectable Effect
⍺ и β — заранее выбранные вероятности ошибки I и II рода. MDE очень важен, если изменение статистически не значимо. При принятии решения заказчик должен помнить, что отсутствие стат. значимости не равносильно отсутствию эффекта. Достаточно уверенно можно утверждать лишь то, что возможный эффект не больше, чем MDE.
2. MW | T. Результаты Mann-Whitney U- и T-test
На панель выводим значение z- и t-статистики (для MW и T соответственно). В тултип — динамику p-value. Если изменение значимое, то клетка подсвечивается красным или зеленым цветом в зависимости от знака разницы между группами. В таком случае мы говорим, что метрика «прокрасилась».
3. Lift. Разница между группами в процентах
4. Mean | Num | Den. Значение метрики, а также числитель и знаменатель отдельно
К числителю и знаменателю применяем еще один T-test, который помогает понять, чей вклад решающий.
5. Std. Выборочное стандартное отклонение
6. Hist. Тест Шапиро-Уилка на нормальность «бакетного» распределения.
Если индикатор красный, то, возможно, в выборке есть выбросы или аномально длинный хвост. В таком случае принимать результат по этой метрике нужно осторожно, либо не принимать вовсе. Клик на индикатор открывает гистограммы метрики по группам. По гистограмме однозначно видны аномалии — так проще делать выводы.
Заключение
Появление платформы A/B в Авито — переломная точка, когда наш продукт стал развиваться быстрее. Каждый день мы принимаем «зеленые» эксперименты, которые заряжают команду; и «красные», которые дают полезную пищу для размышлений.
Нам удалось построить эффективную систему A/B-тестинга и метрик. Часто сложные проблемы мы решали простыми методами. Благодаря этой простоте, инфраструктура имеет хороший запас прочности.
Уверен, те, кто собирается построить платформу A/B в своей компании, нашли в статье несколько интересных инсайтов. Я рад поделиться с вами нашим опытом.
Пишите вопросы и комментарии — постараемся на них ответить.
Увеличиваем чувствительность экспериментов при помощи ранговой трансформации
Это перевод статьи booking.ai про увеличение чувствительности метрик в экспериментах с маленькими эффектами.
Описанная ниже методика трансформации позволяет увеличить скорость проведения эксперимента. В предыдущей статье в нашем блоге, мы рассказывали про метод CUPED, который в том числе позволяет ускорять A/B. Крайне желательно сначала изучить как работает CUPED перед прочтением этой статьи.
Записывайтесь на следующий поток интенсивного курса по математической статистике и A/B-тестированиям, который пройдет в октябре 2020 г.
A/B тесты и математическая статистика
Как проходит проверка домашних заданий? После каждой лекции даются задачи для работы в интерактивном калькуляторе…
Для Booking.com контролируемые онлайн эксперименты (A/B тестирование) — это ключевой способ измерения и оценки изменений на сайте, а также основной источник информации для принятия решений (Kaufman, Pitchforth, & Vermeer, 2017). Учитывая размеры и масштаб Booking.com, повышение метрики даже на долю процента приносит существенные для бизнеса результаты. (Jackson, 2018). Мы давно прорабатываем тему повышения чувствительности экспериментов. Это позволяет нам выявлять менее масштабные эффекты или же работать с меньшей выборкой (или в более короткие сроки) и таким образом ускорять разработку. В частности, для повышения чувствительности экспериментов мы часто используем метод CUPED (контролируемый эксперимент с использованием данных “до эксперимента”).
Однако классические методы A/B тестирования (такие как двухвыборочный независимый t-тест) могут быть недостаточно чувствительными, когда распределение данных далеко от нормального — даже с учетом использования методов уменьшения дисперсии вроде CUPED. В основе t-теста лежит предположение о нормальном распределении данных. Эмпирически, это предположение не всегда соответствует реальности.
К примеру, на рис. 1. изображено распределение реальной метрики, которое мы зафиксировали на Booking.com. Метрика сильно искажена целым рядом отклонений.
Исследования показывают, что t-тест достаточно устойчив к отклонениям от нормального распределения при условии что объем выборки достаточно большой. Однако, нельзя сказать наверняка, насколько именно “большой” должна быть выборка и достаточно ли она велика для решения отдельно взятой проблемы. Если мы не знаем природы и степени отклонения от взятого за основу предположения о нормальном распределении, то мы и не можем предугадать величину ошибок, которые появятся в результате этого предположения. (Colquhoun, 1971).
В этой статье мы предлагаем проводить t-тест не на изначальных данных, а на рангах, присвоенных этим данным — как способ повышения чувствительности экспериментов в ситуациях вроде той, что описана выше. Мы также хотим подчеркнуть, как важно понимать базовые интересы бизнеса, уделять внимание распределению данных и проводить моделирование чувствительности при выборе статистических методов.
Во-первых, мы покажем, что из себя представляет ранговая трансформация и продемонстрируем, что проведение t-теста на рангах дает примерно такие же результаты, как при применении непараметрического U-критерия Манна-Уитни.
Далее мы разберем реальные примеры с Booking.com, которые показывают, как увеличилась чувствительность экспериментов в результате применения t-теста к рангам данных. В конце статьи мы приводим конкретные рекомендации: когда использовать ранговую трансформацию в коммерческом A/B тестировании, а когда не стоит.
Ранговая трансформация
Метод
Ранговая трансформация — это просто преобразование данных путем присвоения им рангов. Таким образом, параметрический тест (например, t-тест) проводится не на самих данных, а на рангах. Данные из контрольной и тестовой выборок ранжируются вместе от меньшего к большему, а при наличии связей присваивается средний ранг.
В нашем примере в исходных данных есть большой выброс (нижний ряд). Исходное значение метрики — 100, и это сильно исказило бы статистику, если бы мы работали с самими данными,. Однако величина выброса не влияет на ранг. Самому большому значению будет присвоен ранг 6 — и не важно, 100 это или 3.
Как вариант, при распределении трафика в эксперименте 50/50, трансформацию можно определить как:
где N — это общий размер выборки. С точки зрения мощности эксперимента, трансформация сравнима по эффективности с простым ранжированием элементов выборки, но интерпретируемость трансформированной метрики лучше — и вот почему:
Взаимосвязь между t-тестом на рангах и U-критерием Манна-Уитни
Проведение t-теста на рангах данных дает примерно такие же результаты, как применение непараметрического U-критерия Манна-Уитни. Когда применение U-критерия Манна-Уитни к инфраструктуре, с которой вы работаете, не представляется возможным, практически эквивалентной альтернативой будет t-тест на рангах, который, к тому же, достаточно прост в проведении.
Поскольку U-тест Манна-Уитни — непараметрический, он не предполагает какого-то конкретного распределения данных. Нулевая гипотеза звучит так: случайно выбранное значение из одной выборки может быть равновероятно больше или меньше случайного значения из другой выборки. Или в виде формулы:
В то же время у t-теста другая нулевая гипотеза: что средние значения в двух выборках равны:
Таким образом, принимая решение о применении того или иного теста для решения наших задач, мы будем руководствоваться именно нулевой гипотезой.
Измерим при помощи вывода формул и моделирования, насколько “эквивалентными” являются t-тест на рангах и U-критерий Манна-Уитни. (Zimmerman, 2012).
Мы знаем, что по двухвыборочному t-тесту для независимых выборок у нас есть t-статистика:
где n — это объем выборки для выборки X, m — это объем выборки для выборки Y. N = n+m, а t-статистика сравнивается с квантилями из t-распределения с N-2 степенями свободы.
В непараметрическом U-тесте Манна-Уитни, мы заменяем значения данных на присвоенные им ранги Rᵢ от 1 до N и используем статистику (с поправкой на связи в рангах).
Minimum Detectable Effect (MDE)
1. What is Minimum Detectable Effect (MDE)?
It’s a minimum improvement over the conversion rate of the existing asset (baseline conversion rate) that you want the experiment to detect.
By setting MDE, you define the conversion rate increase sufficient for the system to declare the new asset winner. The lower MDE you set, the slighter conversion changes will be detected by the system. Basically, MDE measures the experiment sensitivity.
Highly sensitive settings, or low MDE, come along with a big sample size. The lower MDE, the more traffic you need to detect minor changes, hence the more money you have to spend on driving that traffic.
So, by configuring MDE you are flexible about connecting the experiment design with the costs you are ready to incur.
2. What’s the optimal MDE?
There’s no such thing as an ideal MDE, so SplitMetrics can’t recommend you the optimal value. This is a key custom parameter affecting your sample size and, by implication, the costs associated with the traffic. In other words, we suggest you defining MDE by yourself, taking into consideration your individual risks – money and time.
3. How does MDE affect my sample size?
MDE has a dramatic effect on the amount of traffic required to reach statistical significance. To know your maximum sample size, use the Evan Miller calculator for sequential A/B sampling. Make sure that your insert relative value for MDE rather than absolute.
For example, to reach the significance level of 5%, you’ll require 2,922 total conversions with MDE = 10%. with MDE = 5% the sample size grows up to 11,141 total conversions.
Remember, however, that the sample size you see is only the maximum threshold required for a statistically significant result. Due to the nature of sequential A/B testing, the system will constantly check the difference between conversion rates of variations under testing. Once the difference is found, the test is finished and there’s no need to score the entire sample size.
4. How to calculate my MDE?
Although our system can count MDE for you, we strongly recommend setting it by yourself. This parameter depends on your own risks – money you’re ready to allocate for the traffic acquisition and time you can wait for the experiment to run.
To get MDE that works for you, you have to understand:
The best possible MDE implies that the potential revenue exceeds or compensates for the traffic acquisition costs.
MDE calculation workflow
Step 1. Estimate the desired conversion rate lift
Let’s say the conversion rate of your product page with the existing icon is 20% (baseline conversion rate). You assume that the new icon should have at least a 22% conversion rate for you to use it instead of the existing icon.
So, you have to configure an experiment in such a way that it declares the winner when the conversion rate difference is at least 22% – 20% = 2%. To set that up, you have to count your estimated MDE.
MDE is calculated as a percent of the baseline conversion rate:
MDE = desired conversion rate lift / baseline conversion rate x 100%
In this example, 2% of the 20% baseline conversion rate is 10% – this is your estimated MDE for the experiment.
Step 2. Calculate your sample size
Next step is to get your sample size, using the Evan Miller’s calculator for sequential A/B testing.
You will see the following:
Control wins if: 2,922 total conversions – this is the maximum sample size per two variations (A+B) needed to finish the experiment.
Treatment wins: 106 conversions ahead – means that the system will sequentially check the difference in conversions between variation A (control) and B, and may finish the experiment once the difference of 106 is found, even before reaching the maximum sample size.
Why? Each pair of variations has its individual significance level. As the number of variations under testing grows, so does the overall significance level because those individual values accumulate. The Sidak correction balances out individual significance levels so that the overall significance level equals 5%.
To apply the Sidak correction, use the following significant level values:
The total conversions will appear after you insert all the above in the calculator.
For example, you want to run an experiment with 3 variations – A+B+C. Things you’ll insert in the calculator will be:
Total conversions required: 3,472
In the above example with 3 variations, you’ll get:
total conversions / 2 = 3,472 / 2 = 1,736
Back to the example, as you run an A+B+C experiment, 3 will be your multiplier:
total conversions / 2 * 3 = 5,208
5,208 is the rough estimation of the maximum sample size for an experiment with 3 variations (A+B+C).
Step 3. Calculate your traffic acquisition costs
In step 2, we’ve calculated the maximum required conversions for an experiment with two variations (A+B) – 2,922. Now that you know the maximum required sample size, you can calculate the possible traffic acquisition costs. Use this formula:
traffic acquisition costs = total conversions / baseline conversion rate * Сost per Сlick
Note: By dividing the total conversions by your baseline conversion rate you gauge your sample size in visitors (those who click on your ad banner).
When you have SplitMetrics integrated with Facebook Pixel, you may configure “Complete Registration” as a conversion event. In such a case, the traffic acquisition costs will be calculated considering users who click on the “Get” button rather than those who click on an ad banner.
The formula for cost calculations in such cases will include Cost per Install (not Сost per Сlick):
traffic acquisition costs = total conversions x CPI
Note: As you can see, you don’t have to recalculate sample size in visitors. Just multiply CPI by the total conversions obtained in the Evan Miller calculator.
At this point, you have to make sure that these costs line up with the budget allocated for the traffic acquisition:
Step 4. Calculate the potential revenue
You may use different ways to calculate the potential revenue from the conversion rate lift, for example, based on the LTV of ASO-acquired app subscribers. In the above described example with two variations (A+B), you have to calculate how much money you will generate from a 2% conversion rate lift.
Once you have your Potential revenue ($Y) calculated, compare it with the Traffic acquisition costs ($X):
5. At what experiment stage should I set MDE?
MDE is configured after the experiment is created but before you start driving traffic. If you change your MDE after the traffic starts driving to the experiment, you will lose all the statistics.
6. Can I change my MDE during the experiment?
Don’t modify MDE after you start driving traffic to your experiment. Otherwise, all the statistics – visitors, conversions, improvement, etc. – will be reset.
7. How does SplitMetrics calculate my MDE?
To arrive at your best possible MDE, our algorithm will rely on your baseline conversion. Your ideal MDE will be the value which produces a sufficiently large sample size, yet comparable to that in classic A/B testing.
If SplitMetrics calculates MDE for you, be aware that the result won’t appear straight away. The algorithm will gauge and display your MDE in the interface after your variations gain enough conversions.
