Эксперименты в Ситимобил. Эпизод 2: Атака тестов на Switchback31.08.2021 13:46

Введение
Воспоминания
Что по тестам, ребят?
Проверка экспериментов
Куда дальше?

Введение

Всем привет! На линию выходит команда динамического ценообразования Маркетплейса Ситимобил.

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

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

Воспоминания

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

В многосторонних маркетплейсах в эксперименты может вторгаться сетевой социальный эффект.

Сетевой эффект — это ситуация в экспериментах, когда поведение одного участника изменяет поведение другого.

Сетевой эффект нарушает предпосылки, на которых базируется «верность» рандомизированного эксперимента — Stable Unit Treatment Value Assumption SUTVA.

SUTVA — условие валидности А/В-теста, которое гласит, что измененные условия воздействуют только на группу, к которой они были применены, и не воздействуют на пользователей из других групп.

Чтобы дальше проводить со спокойной душой корректные эксперименты, необходимо избавиться от сетевого эффекта или хотя бы снизить его. Один из эффективных способов сделать это — Switchback.

Switchback — это способ разделения участников на пилотные и контрольные группы по временным промежуткам и географическим зонам.

И последнее, что мы будем использовать для простоты, это обозначение Unit.

Unit — единица разбиения на группы в Switchback-эксперименте, которая включает в себя геозону и некоторый промежуток времени.

Кажется всё, пора переходить к основной части, в которой нам нужно будет запастись терпением и любовью к математике.

Что по тестам, ребят?

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

Ride-level и unit-level

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

Первый и самый простой способ: смотреть на данные «как прометились» — не важно, в каком unit’е было наблюдение клиентскаясессия, важно, что оно оказалось в группе А или В. Такой уровень агрегации мы назовём ride-level.

Второй способ — это агрегировать данные до unit’ов. Его мы назовём unit-level.

Я всё ещё не понял (а), что такое unit, объясните, пожалуйста.

В прошлой статье мы визуализировали идею Switchback следующим образом:

Так вот, Unit — это один прямоугольник на картинке выше, а в жизни у нас — это гексагон.

Оба подхода, конечно, «грешны», и важно понимать, чем.

В ride-level мы не учитываем, что один и тот же клиент тутможетбытьипассажир, иводитель может оказаться и в группе А, и в группе В, поэтому выборки независимыми не будут. Но зато при таком подходе у нас много наблюдений, а это хорошо для получения статистически значимых результатов.

В unit-level же ситуация как-будто зеркальная. Используя такую агрегацию мы резко сокращаем количество доступных нам наблюдений. Например, в некотором unite’е совершилось поездок, но посчитаем мы его как одно наблюдение. Это напрямую будет влиять на мощность наших тестов. Вторая проблема — это не полностью равнозначные между собой unit’ы. Так, наши изменения будут по-разному влиять на unit’ы, полученные ночью, когда мало наблюдений, и днем, когда наблюдений в unit’ах много. Это, в целом, может затруднять понимание эксперимента и формулирование выводов, так как результаты могут получиться противоречивые.

Чтобы нивелировать эти проблемные моменты, мы улучшим подход unit-level всякими интересными фишками, которые обсудим ниже в разделе «Проверка экспериментов».

Как будем сравнивать

Ну и ещё небольшая остановка перед самым интересным.

Применимость тестов

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

Куда же смотреть, чтобы понять, что у нас всё хорошо и какие графики построить, чтобы быть спокойными? Ответом на вопрос будут графики с распределением p-value, которые получены, например, на некотором наборе сгенерированных А/А-тестов какможносгенерироватьсебеданные, мырасскажемниже. Если распределение p-value равномерное, то у нас всё хорошо, и можно дальше спокойно применять наши тесты, если это не так, то FPR НЕ контролируется p-value.

В целом хорошая картинка должна выглядеть примерно так:

Сравнение тестов между собой

Нам необходимо понять, по каким критериям мы скажем, что один статистический тест, который мы будем применять, лучше другого. В нашем случае мы не сильно отошли от классики и будем смотреть на false positive rate FPR и sensitivity truepositiverate.

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

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

FPR — это вероятность сказать, что эффект был, когда на самом деле его не было чемменьше, темлучше.

Sensitivity 1−FalseNegative — это вероятность того, что мы почувствуем/различим эффект, если он правда есть чембольше, темлучше.

На практике эти два понятия взаимообратны. Мы можем получить нулевой FPR, просто всегда говоря, что эффекта нет, при этом будем иметь нулевую Sensitivity. И наоборот, всегда говоря, что эффект есть, мы получим 100% Sensitivity и FPR в 100%. Зависимость FPR от Sensitivity выглядит следующим образом:

Чем больше кривая «вжата» в левый верхний угол, тем мы счастливее.

Наша задача — найти тест, который даст для наших данных лучшую пару FPR-Sensitivity.

Для знакомых с машинным обучением это выглядит совсем как кривая ROC-AUC, а если переписать табличку в таком виде какбудторешаемзадачубинарнойклассификации, то аналогия совсем очевидна.

Тогда наши метрики перепишутся в совсем знакомом виде:

$FPR = \frac{FP}{FP + TN}$ $Sensitivity (TPR)= 1- FNR = 1 - \frac{FN}{FN+TP} = \frac{TP}{FN + TP}$

На практике мы будем симулировать много экспериментов для проверки одного статистического теста обэтомниже, и наши FPR и Sensitivity перепишутся в представленном ниже виде. Для FPR в случае А/А-теста аналогичнодляSensitivityвслучаеА/В−теста:

$\text{FPR} = { {1\over{N_{sim}}} {\sum^{N{sim}}_{n=1}}I\{P_{(n)}\leq \alpha\} } ,$

где P_n — p-value в эксперименте с номером, $\alpha$ — уровень значимости.

Что будем сравнивать

И наконец, нам необходимо немного поговорить о метриках. Работу маркетплейса такси упрощенно можно представить следующей цепочкой действий:

Клиентская сессия → заказ → назначение водителя → поездка

Одной из метрик качества сервиса является отношение назначенных водителей к заказам. Будем называть эту метрику назначаемостью, или O2DA , что означает Orders to Drivers Assigned да, названиеирасчётперевернуты, нотаковасилатрадиций.

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

Тесты для сравнения

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

На z-test для пропорций и t-test мы останавливаться не будем, потому что по этой теме уже много публикаций, например, можно почитать вот эту. А вот о Multi Level Modelling MLM информации мало особенновприменениикА/В−тестированию, поэтому его стоит обсудить! Такой подход был навеян нам статьей компании DoorDash, которая уже сталкивалась с оценкой эффектов в экспериментах Switchback.

MLM позволяет строить модели на данных, которые могут быть кластеризованы по тому или иному признаку. Вероятно, здесь нужно на пару минут остановиться и осознать эту фразу, но на самом деле за ней скрывается очень простая идея. Часто мы работаем с данными, имеющими вложенную структуру, например, мы сравниваем пользователей, которые могут жить в разных городах или иметь разное образование. Эти особенности пользователей дажескореегрупппользователей, объединённыхпокакому−топризнаку оказывают эффект на нашу целевую метрику. Поэтому если мы сможем их учесть, то это позволит снизить волатильность целевой метрики и потенциально повысит мощность нашего теста. Другая важная мысль заключается в том, что метрики внутри групп, как правило, более выражено коррелируют друг с другом. А это значит, что нарушается стандартное предположение, которое используется в статистических тестах, о том, что данные, с которыми мы работаем, независимы между собой. Этого тоже хотелось бы избежать.

На практике информацию о вложенности на примере пользователей из разных городов можно записать следующим образом:

$y_i = \alpha_{j[i]} + \beta \cdot x_i + \varepsilon_i, \text{ user } i = 1,\dots, n \\ \alpha_{j} = a + b\cdot u_j + \eta_j, \text{ city } j = 1,\dots, k$

Первое — это регрессия на пользователей, второе — на города. Учитывать и записать вложенность можно не только так, другие способы можно найти тут. Конечно, для учёта вложенной структуры данных можно было бы использовать и классические дамми-переменные соответствующих кластеров, однако здесь возникают свои сложности, например, кластеры могут быть несбалансированы унасименнотакие по объёму наблюдений. Из-за чего может случиться неоправданный overfit.

Как мы записали MLM для себя? В нашем случае верхний уровень — это заказы, а второй уровень — это unit’ы по гео и времени, которые мы обговорили ранее. То есть MLM нам необходимо было применить для переменной $is\_driver\_assigned$ , которая для каждого конкретного заказа принимает значение 0 либо 1. Поэтому мы обучали логистическую регрессию следующего вида:

$is\_driver\_assigned= c + b*is\_test+effect_{geo}+effect_{time}+\varepsilon,$

где переменная $is\_test$ — это индикатор, применяется ли для данного наблюдения тестовая модель или нет.

При этом

$effect_{geo}\sim \mathcal{N}(0, \tau_{geo}) \\ effect_{time}\sim \mathcal{N}(0, \tau_{time})$

Таким образом, можно переписать наше уравнение:

$is\_driver\_assigned=(c+effect_{geo}+effect_{time})+b*is\_test+\varepsilon \\ is\_driver\_assigned=c_{time+geo}+b*is\_test+\varepsilon \\ \text{ где } c_{time+geo}\sim\mathcal{N}(c, \sigma^2_{geo}+\sigma^2_{time})$

Такая регрессия учитывает информацию о unit’е и позволяет ответить на вопрос, значим ли коэффициент перед переменной $is\_test$ , и если да, то такой эффект можно ожидать для каждого unit’а.

Проверка экспериментов

Генерирование данных

Для проверки гипотез мы взяли данные на уровне клиентских сессий за несколько недель в одном из наших городов, где в это время не проводилось каких-то существенных изменений, влияющих на нашу метрику. На этих данных будем генерировать множество синтетических тестов, где каждое наблюдение относится к одной из групп A_1 , A_2 или (да-да, у нас будет две группы об этом упоминалось в первом эпизоде). Разные тесты будем получать с помощью рандомизации unit’ов, как описано в нашей первой статье.

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

Классический подход

Сначала убеждаемся, что наши статистические тесты применимы нет.

Видно, что z-test для пропорций не подходит для ride-level агрегации, как мы и говорили выше, в разделе о слабых местах. Отлично, убедились в этом дальше всё равно покажем его на графиках, но применять в эксплуатации, конечно же, не будем.

С MLM чуть получше, но всё равно не прекрасно, а вот unit-level + t-test вполне себе неплох и наши графики выглядят как идеальные.

Посмотрим, что на А/В-тесте. Тут мы фиксировали некоторый uplift, который хотели бы находить нашими тестами.

Ситуация, конечно, патовая. Получаем, что у t-test’а, который мы можем применять, очень низкая мощность, а z-test и MLM применять мы не можем по описанным выше доводам. Срочно нужно повышать мощность t-test’a.

Улучшенная версия: линеаризация + дельта-метод

Идея рассматриваемых далее методов будет основываться на предпосылке:

Если бы у нас был способ снизить дисперсию метрик, которые мы наблюдаем, то это позволило бы нашему тесту стать мощнее — повысить Sensitivity.

Мы возьмём самые быстро работающие и хорошо зарекомендовавшие себя методы — дельта-метод и линеаризацию.

Линеаризация

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

Считаем rides и orders для каждого unit’а в разрезе пилот/контроль.
Строим на контрольной выборке регрессию, из которой получаем коэффициент :
$\text{assigned drivers} = k \cdot \text{orders}$
Кстати говоря, вместо регрессии можно просто взять $global\ ratio$ по контролю.
Получаем новую метрику для каждого unit’а:
$\text{assigned drivers}_{\text{linearized}} = \text{assigned drivers} - k\cdot \text{orders}$
Считаем для полученной метрики t-test.
Профит, вы и ваш тест прекрасны!

Дельта-метод

Сам по себе дельта-метод — это классический статистический подход, а теорема про дельта-метод известна многим (а если вдруг неизвестна, то можно посмотреть вот это видео). Но как применять его в А/В-тестировании, не очевидно. Статью Microsoft на эту тему можно почитать тут. А мы на пальцах объясним суть.

У нас есть замечательная центральная предельная теорема ЦПТ, благодаря которой мы можем получить доверительный интервал confident interval (CI) для среднего, если у нас есть некоторый набор независимых, одинаково распределённых случайных величин $X_1, X_2, \dots, X_n$ :

$\frac{\sqrt{n}(\overline{X}-\mu)}{\sigma} \to N(0,1) \\ CI (\mu) = \overline{X} \pm z_{\alpha/2}\frac{\sigma}{\sqrt{n}}, \\ \text{где } z_{\alpha/2} \text{ }\alpha/2\text{-квантиль для }N(0,1)$

Это очень классно, если наша метрика, например, представляет собой среднее время подачи машины или какую-либо другую несоставную метрику. Но что делать с композитными метриками, такими как наша назначаемость? Ведь даже простая выборочная оценка среднего имеет некоторое смещение относительно истинного среднего хоть и стремящееся к 0 на бесконечности. Истинная же дисперсия вообще может не существовать. Тогда возникает вопрос о применимости ЦПТ.

И здесь на помощь приходит дельта-метод, который расширяет заявленную в ЦПТ асимптотическую нормальность на любое дифференцируемое преобразование $g(\dots)$ от некоторой случайной величины T_n и утверждает, что:

$\text{Если для } T_n \text{ и некоторой константы } \theta \text{ выполняется} \\ \sqrt{n}(T_n-\theta) \to N(0,1) \text{ при } n\to \infty, \\ \text{то для дифференцируемой функции } g(\dots) \text{ верно: } \\ \sqrt{n}(g(T_n) - g(\theta)) \to N(0, g'(\theta)^2)$

Так чем же это хорошо? А тем, что вместо T_n мы можем рассматривать пару (Y_n, X_n) , где Y_n — это, например, наши назначенные автомобили, а X_n — заказы. В качестве $\theta$ можно взять $(\overline{X}, \overline{Y})$ , в качестве $g(\dots)$ взять $g(x,y) = \frac{y}{x}$ . Вот и всё, мы уже в шаге от доверительного интервала для нашей конверсии, правда, он чуть менее простой (полный вывод смотрите в статье Microsoft), чем в изначальном варианте, но его всё ещё легко закодить:

$\frac{\overline{X}}{\overline{Y}} - 1 \pm \frac{z_{\alpha/2}}{\sqrt{n}\overline{X}}\sqrt{s_y^2 - 2\frac{\overline{Y}}{\overline{X}}s_{xy} + \frac{\overline{Y}^2}{\overline{X}^2}s^2_x}$

Ну всё, поехали сравнивать улучшенные варианты тестов.

Результаты

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

Ничего нового, с линеаризацией и дельта-методом всё хорошо.

Ну и наконец (барабанная дробь), результаты наших финалистов! С маленьким, но преимуществом в третьем знаке после запятой по выдаваемой мощности побеждает t-test + линеаризация!

Результаты отчасти ожидаемые, но всё равно приятные

Куда дальше?

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

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

В подготовке статьи участвовали Артём Солоухин, Ксения Мензорова, Николай Ишмаметьев. Также выражаем благодарность за помощь в подготовке статьи ребятам из expf.ru, Искандеру Мирмахмадову и Виталию Черемисинову.