Switchback-эксперименты в Ситимобил: Часть 1. Зачем это нужно04.06.2021 05:46

Содержание

Введение
Про эксперименты
Что такое сетевой эффект?
Почему switchback помогает?
Зачем так сложно, может, у вас нет сетевого эффекта?
Убедили, как подобрать окно переключения по расстоянию и времени?
Слабые стороны Switchback
О следующей статье

Введение

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

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

Разработка алгоритма это творческий процесс, поэтому в своей работе мы генерируем и проверяем много гипотез, часть из которых потом-таки попадают в продовую версию алгоритма. Каждая такая идея проходит путь от аналитики и dry-mode (так мы называем что-то вроде backtesting’а) до экспериментов на реальных городах и, в лучшем случае, раскатки на всю Россию.

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

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

До середины 2019 года чаще всего мы проводили рандомизированные A/B-тесты со сплитованием по hash (id), реже W2W (week-to-week, то есть когда производится сравнение выборок за одно время и один день недели, но в разные периоды), или diff-in-diff (подробнее см. здесь) эксперименты. Но все эти подходы для наших задач имеют ряд больших недостатков.

В W2W и diff-in-diff оценках может быть сложно обеспечить сопоставимые условия в тестовой и контрольной группах. Как-то мы хотели провести W2W-оценку, а в нашем тестовом городе на второй неделе была песчаная буря.

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

С рандомизированными A/B-тестами проблемы не такие очевидные. Когда вы запускаете рандомизированный А/В-тест в двух-трёх-n-стороннем маркетплейсе, то у вас может возникнуть сетевой эффект (не бойтесь, об этом термине поговорим в следующем разделе), который ставит под вопрос валидность теста в целом.

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

Что такое сетевой эффект?

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

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

Слишком сложная схема, давайте на примере:

Пусть Миша с Колей живут в соседних домах напротив друг друга и каждое утро примерно в одно время едут на такси до метро. Наша команда динамического ценообразования начала эксперимент, и так получилось, что Миша и Коля оказались в разных группах. Для Коли цена будет рассчитываться старым алгоритмом, а для Миши — новым, который по каким-то причинам снизил утром на 5% цену поездки до метро. Наступает очередное утро, и Миша с Колей заказывают такси примерно в одно время. Цена у Миши ниже обычного, и он принимает решение о заказе такси быстрее, тем самым отнимая водителя у Коли. Коля оказывается без машины, и мы вынуждены изменить для него цену, чтобы он отказался от поездки, так как свободных машин в округе больше нет. Получается, что конверсия Коли занижена из-за Миши, то есть измененные условия повлияли не только на решение Миши, но и на Колю, и SUTVA не выполняется.

Это и есть сетевой эффект. Если формулировать более научно, то:

Сетевой эффект — это ситуация в экспериментах, когда поведение одного потребителя услуги или товара может влиять на характеристики или даже возможность предоставления услуги/товара для другого потребителя. Этот эффект особенно актуален для двустороннего маркетплейса, потому что предположение об отсутствии влияния (SUTVA) здесь не может быть принято.

Спасительный Switchback

SUTVA не выполняется, рандомизированный А/В-тест под угрозой. Как же нам теперь проводить честные эксперименты?

Здесь нам на помощь приходит тип эксперимента, который называется Switchback.

Switchback — метод геохроносплитования контрольных и тестовых групп с гиперпараметрами в виде длительности применения группы на все наблюдения и площади применения группы.

Суть метода Switchback заключается в следующем:

Имеющиеся районы разбивают на контрольные и экспериментальные группы. К экспериментальным применяется тестируемый алгоритм.
Через короткий промежуток времени районы случайно изменяются (мы считаем районами группы гексагонов, используем гексагональную сетку от Uber; подробнее читайте здесь). Затем они снова меняются, и так далее. Процесс перестановки продолжается в течение всего эксперимента.
Показатели за время, когда алгоритм действовал и бездействовал, считаются в разные «корзины».
Показатели из двух «корзин» сравниваются, что позволяет оценить влияние алгоритма на различные ситуации.

Теперь Миша и Коля с бОльшей вероятностью оказались бы в одной группе, так как они близко друг к другу по расстоянию и времени. Решение они принимали бы в одинаковых условиях, и SUTVA не нарушилось бы.

Почему Switchback помогает?

В какой ситуации сетевой эффект максимален? Когда пассажиры могут забирать друг у друга машины, то есть близки друг к другу по времени и расстоянию. А теперь попробуем визуализировать сетевой эффект и посмотрим, что делает Switchback. Обозначим взаимное влияние между пассажирами через линию. Она есть, если пассажиры относятся к разным группам — то есть влияют своим измененным поведением на неизменных участников; и линии нет, если пассажиры относятся к одной группе. В первом случае пользователи разбились на группы случайно, и внутри одной геозоны есть пользователи из разных групп; во втором случае вся геозона полностью относится к одной группе. Как видите, во втором случае количество взаимодействия (сиреневых линий) резко сократилось, это и есть главный эффект Switchback.

Мы даже можем оценить сокращение взаимодействия численно!

Немного математики для бесстрашных

Взаимное влияние пассажиров друг на друга

Пусть пассажир определяется вектором:

$r = \begin{bmatrix} t \\ latitude \\ longitude \end{bmatrix}, \\$

где

t — время, в которое клиент зашел в приложение;
latitude — долгота точки заказа;
longtitude — широта точки заказа.

Тогда взаимное влияние пассажиров друг на друга — interaction — введем следующим образом: как будто L_2 и мы считаем расстояние между точками, только одну из координат заменили на время:

$interaction = \frac{1}{\beta}, \\ \beta = \sqrt{\alpha_1^2(t_1-t_2)^2 + \alpha_2^2(\Delta d)^2} \\ \Delta d = f(lat_1, lat_2, lon_1, lon_2)$ Почему interaction это дробь?

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

Поэтому подходящие виды зависимостей для определения interaction могут быть следующие:

$y = \frac{1}{x^{\alpha}}, \alpha \geq 1 \\ y = e^{-x}$

Для определения interaction в данном примере была выбрана зависимость $\frac{1}{x}$ так как она убывает медленнее всего, значит позволит учитывать с бОльшим весом влияние между клиентами, которые находятся друг от друга далеко по времени или расстоянию, по сравнению с другими функциями. Интуитивно, кажется, что даже «далекие» к друг другу клиенты всё равно влияют на друг друга, поэтому мы и выбрали самую медленно убывающую функцию.

Зачем нужны веса?

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

В обычных метриках, например, L_2 , мы сравниваем между собой координаты и , эти величины имеют одинаковый масштаб. В нашем случае мы сравниваем метры и секунды. Поэтому чтобы они вносили одинаковый вклад их необходимо привести к одному масштабу. Здесь мы поступили очень просто и посмотрели на наших реальных данных отношение среднего времени между заходами клиентов в приложение, к среднему расстоянию между ними, и получили 1:16. Это соотношение и подставим в наши $\alpha_1, \alpha_2$ при расчетах.

Эта метрика не существует в нуле, но на наших данных и не было таких случаев, когда числитель был нулевым. Иначе можно было бы прибавить в знаменателе 1.

Сравним, как пассажиры влияют друг на друга в рандомизированном А/В и Switchback.

Теперь поступим так же, как в примере с кругами. Если пользователи относятся к разным группам, то взаимное влияние между ними есть, и мы его считаем по формуле для interaction выше. Если к разным, то считаем, что его нет. По сути, мы проставляем веса на черные линии из картинки выше и суммируем их для некоторого промежутка времени. Стоит отметить, что также для упрощения и ускорения подсчетов мы ограничили дельту между клиентами, когда учитываем их взаимное влияние, 6 минутами и 3 км, их также получили на реальных данных.

Если такое проделать на Москве в течение одного дня и сравнить уровень взаимодействия для рандомизированного эксперимента и Switchback, то Switchback снижает сетевой эффект более чем на 70%.

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

Зачем так сложно, может, у вас нет сетевого эффекта?

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

Краткая идея статьи

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

Идея следующая:

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

Убедили, как подобрать окно переключения по расстоянию и времени?

При определении длины временного промежутка и размера географической зоны основной вопрос заключается в качестве данных, которые мы соберем с выделенного кусочка. Глобально идея заключается в том, что нам необходимо найти компромисс между смещением данных (Bias) и предельной погрешностью выборки (Margin). Подробнее об этом можно почитать вот тут, но давайте кратко обсудим идею.

Сформулируем, что есть Bias, а что Margin of Error.

Разница в средних между нашими группами при семплирования назовем Bias — смещение. Например, когда мы делаем АА-тест нам бы очень хотелось, чтобы разница в средних между группами А1 и А2 не было, иначе мы не сможем запустить наш тест. Имеется в виду, конечно, что не будет статистически значимой разницы.

Margin of Error (предельная погрешность выборки) — насколько наше среднее в выборке будет отличаться от среднего в генеральной совокупности. Если уйти от точных определений и сказать простыми словами, то Margin of Error показывает, насколько широким мы получим доверительный интервал для оцениваемой величины. Здесь нам бы очень хотелось, чтобы коридор для среднего был узким, и мы как можно точнее оценили наше среднее.

Теперь опустимся на практику и поговорим про параметры сплитования, и как они связаны с Bias и Margin. Для более удобных формулировок введем понятие Unit. Unit — кусочек времени и пространства, который отсекается определенным промежутком времени и геозоной.

Теперь обсудим связь размера Unit’a c Bias. Когда мы уменьшаем географическую зону и промежуток переключения групп, выборка уменьшается, и мы с большей вероятностью соберем нерепрезентативные смещенные данные. Представим ситуацию, где мы хотим протестировать два алгоритма, один из которых обрабатывает заказы по мере поступления, а другой — обрабатывает сначала короткие поездки, а уже потом все остальные. Тогда при слишком быстром переключении мы можем получить ситуацию, при которой один алгоритм будет обрабатывать только короткие поездки, а другой будет пытаться исправить ситуацию после выбора другого алгоритма. При этом сделать какие-то обобщающие выводы мы не сможем, так как в данных по поездкам будет заложено смещение, которое возникло из-за слишком частой смены групп. То есть при уменьшении размера Unit’a (уменьшаем окно сплитования, например, было 20 минут стало 10, и уменьшении геозоны — стали работать с более маленькими гексагонами) растет Bias.

С Margin капельку сложнее, но мы справимся. Margin зависит от двух вещей — от разброса данных, с которыми мы работаем и от их количества (снова см. подробнее тут).

$Margin \sim \sqrt{\frac{D}{n}},$

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

Зависимость, конечно, не однозначная, но на практике всё-таки дисперсия растёт не так быстро, как количество зон, потому что города ведут себя относительно стабильно, за исключением, каких-то особых периодов, например, дождя или вечера 31-го декабря. Поэтому в целом можно сказать, что при уменьшении размера Unit’а Margin падает. Но важно иметь ввиду, что природа этой зависимости на ваших данных может оказаться другой.

Получается вот такая сложная зависимость, с которой нам нужно как-то жить, если хотим запустить Switchback):

Как же жить с такой сложной зависимостью на практике:

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

CookBook для запуска первого в вашей жизни Switchback-теста такой (такие вводные работают для нас):

держим тест около 2 недель в зависимости от объема рынка;
проводим сплитование по гексагонам размером 6 (то есть по районам площадью 36 кв. км.);
переключение происходит раз в 20 минут.

Выглядит это примерно так:

Теперь самое время пойти и запустить с первыми вводными AA-тест в Switchback на исторических данных для своего маркетплейса!

Слабые стороны Switchback

Конечно, Switchback не безгрешен и имеет несколько особенностей, с которыми стоит быть внимательными.

Сохранение сетевого эффекта

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

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

Осторожно, вы в эксперименте

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

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

Мощность ниже

Чистка может негативно повлиять на мощность эксперимента. Кроме этого, на мощность switchback негативно влияет и единица рандомайза — пара регион+время.

Сложность экспериментов с визуальными изменениями

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

Долгосрочный эффект

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

Сходимость групп

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

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

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

Если всё-таки ваш выбор пал на А/А/В-тест, то распределение по группам лучше держать 25%/25%/50%, так в теории мощность вашего теста будет выше (по сравнению с менее сбалансированными группами), подробнее об этом можно почитать вот тут.

О следующей статье

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

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