Ситимобил

От эвристики до машинного обучения поисковые подсказки в Ситимобил

17.09.2020 16:18:03 |

Автор: admin

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

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

Один из центральных элементов на первом экране (тот, который видит пользователь после авторизации) это поисковые подсказки. В команде гео-поиска мы называем их саджестами (от англ. suggestion). Они предлагают пользователю конечные адреса маршрута (точки Б) из его истории поездок в зависимости от текущего местонахождения пина (т.е. точки подачи) и времени дня без ввода поискового запроса. С помощью саджестов мы стараемся помочь пользователю сформировать заказ в один клик. Вактуальной версии клиентского iOS-приложения саджесты выглядят так:

Гео-поиск за счет алгоритмов формирования поисковой выдачи может влиять на одни из важнейших продуктовых метрик для клиентского приложения таких как время, потраченное на заказ такси (Time to order, или T2O), а также количество действий, которые потребовались клиенту, чтобы сформировать заказ (Actions to order, или A2O). Поэтому мы решили разработать алгоритм, который будет предсказывать наиболее вероятные конечные точки маршрута (точки Б) при заданном местоположении и времени суток.

Эвристика

Один из backend-разработчиков команды гео-поиска (vasilesk, привет!) придумал достаточно простую эвристику для формирования саджестов, которая работала как для начальной точки А, так и для конечной точки Б. Сразу стоит оговориться, что эвристика работала не на истории поездок пользователя, а на истории нажатий на объекты поисковой выдачи, что повлекло за собой некоторые проблемы. Эти объекты мы называем пиками (от англ. pick). Эвристика выглядела следующим образом:

Для текущего пользователя берем все его исторические пики.
Фильтруем их, оставляя те, которые были с тем же таргетом (откуда/куда).
Фильтруем пики, оставляя те, которые были в радиусе 300 метров от парной локации (то есть для таргета куда 300 метров от откуда, для таргета откуда 300 метров от куда). Если нет парных координат, то считаем расстояние от GPS-координат пользователя.
Фильтруем пики, оставляя те, которые были сделаны в будние дни, если сейчас будний день, или в выходные, если сейчас выходной.
Фильтруем пики, оставляя те, которые были сделаны между 3:00 и 14:00, если сейчас этот временной промежуток, и аналогично для обратной ситуации.
Вытаскиваем из пиков гео-респонсы (метаинформацию), склеиваем дубликаты, упорядочиваем по количеству пиков с таким гео-респонсом и времени пика по убыванию.
Показываем первые три позиции пользователю.

Этот алгоритм работал некоторое время, и в целом был хорош для MVP (о метриках поговорим чуть позже), но обладал рядом недостатков. Помимо достаточно примитивной логики работы, он базировался не на поездках, а на пиках пользователя. Из-за этого порой у пользователей появлялась неочевидная выдача в поиске. А также ввиду специфичного способа хранения истории пиков было довольно сложно проводить быструю аналитику. Исходя из этого мы решили попробовать применить машинное обучение. Дальше мы рассмотрим формулировки задач ранжирования и сведем нашу задачу к бинарной классификации.

Постановка задачи ранжирования

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

$inline$ множество объектов.

$X^l = \{x_1, \dots, x_l \}$ обучающая выборка.

$i \prec j$ правильный порядок на парах $inline$

Задача: построить ранжирующую функцию $a: X \rightarrow$ , при которой

$i \prec j a(x_i) < a(x_j)$

Теперь сформулируем задачу ранжирования поисковой выдачи по запросу. От общей задачи ранжирования она отличается тем, что вместо общего множества объектов, которое нам нужно отсортировать, появляется два множества $inline$ и $inline$ множества документов и запросов.

$inline$ коллекция документов (ответов).

$inline$ множество запросов.

$D_q \subseteq D$ множество документов, найденных по запросу q.

$X = Q \times D$ объектами являются пары запрос, документ: $x \equiv (q, d), q \in Q, d \in D_q$

$inline$ упорядоченное множество рейтингов (оценок).

$y(q, d): X \rightarrow Y$ оценки релевантности.

Чем выше оценка $inline$ , тем релевантнее документ $inline$ запросу $inline$ .

Правильный порядок определен только между теми документами, которые были найдены по одному и тому же запросу $inline$ :

$(q, d) \prec (q, d') \Leftrightarrow y(q, d) < y(q, d')$

В нашей задаче рекомендаций конечных точек маршрута множество рейтингов бинарно. Для пользователя предложенный адрес может быть или релевантным, или нерелевантным (не берем в расчет случаи со сложным маршрутом с несколькими конечными точками). Если рассматривать задачу в контексте пользователя, то $inline$ запрос к сервису, который содержит в себе id клиента, гео-позицию, дату и время; $inline$ множество исторических конечных точек Б по поездкам пользователя (мы делаем предложения только на основании адресов прошлых поездок). И каждый допустимый ответ $d \in D_q$ на запрос $inline$ может быть или релевантным для пользователя (из текущей точки и в текущее время пользователю нужно уехать именно сюда) или нерелевантным.

Для полноты картины осталось только описать процесс создания выборки пар запрос-ответ с таргетом. Рассмотрим для простоты одного клиента, у которого было 5 поездок. Проранжируем эти поездки от самой первой до последней. Для первой поездки мы не знаем ничего о поездках пользователя, поэтому предложить ему саджест с помощью описанного алгоритма машинного обучения мы не можем (тут работает эвристика для новых пользователей). Для второй поездки мы знаем конечный пункт назначения из первой поездки и можем предложить этот адрес пользователю в том случае, если он успешно пройдет процедуру постобработки (находится дальше 1 км от текущего местоположения, в том же регионе, и т.д.). Для третьей поездки у нас уже может быть от одного до двух возможных саджестов, если конечный адрес второй поездки совпал с конечным адресом первой и если конечные адреса были разными соответственно. Если саджест совпал с конечной точкой Б (то есть попал в один и тот же гексагон фиксированного размера), то в качестве таргета мы ставим 1, иначе 0. По этому алгоритму мы формируем всевозможные пары вида запрос-(возможный) ответ для каждого клиента.

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

Метрики

В задачах ранжирования метрику, которая показывает долю правильных ответов из документов $inline$ в топ $inline$ списка ранжирования при запросе $inline$ , называют Precision@n. Нас интересуют Precision@1/2/3, поскольку общая доля кликов (Click Through Rate) на первые три позиции составляет около 95 %. При этом правильный конечный адрес только один (естественно, если пользователь хочет уехать в адрес из своей истории), следовательно, эта метрика как раз будет показывать долю случаев, когда правильная конечная точка Б попадает в топ 1/2/3 адресов, которые предложил наш алгоритм.

Напомним, что в нашей задаче $Y = \{0, 1\},\; y(q, d)$ релевантность, $inline$ искомая функция ранжирования. Тогда Precision@n можно записать как:

$P_n(q) = \frac{1}{n}\sum_{i=1}^{n} y(q, d_q^{(i)})$

Признаки и модель

Признаки для модели в нашей задаче можно разделить на несколько блоков:

Только для документа $d \in D_q$ (конечный адрес, точка Б).
Только для запроса $inline$ (начальный адрес, точка А).
Общие для запроса и документа $inline$ (маршрут из А в Б).
Общие для пользователя.

Приведем несколько примеров для каждого из них.

Примеры признаков только для документа (точка Б):

Количество поездок в точку Б за последние K дней.
Количество поездок в точку Б в разрезе дней недели и времени суток.
Когда была совершена предыдущая поездка в точку Б.
Флаг, что предыдущая поездка была совершена в точку Б.
Является ли точка Б избранным адресом/домом/работой.

Примеры признаков только для запроса $inline$ (точка А + дата/время):

Флаг, новая ли текущая локация для пользователя.
Когда была совершена предыдущая поездка из точки А.
Количество поездок из точки А за последние K дней.
Количество поездок из точки А в разрезе дней недели и времени суток.
Является ли точка А избранным адресом/домом/работой.
День недели/время суток для запроса $inline$ .
Дистанция до точки Б.

Примеры признаков, общих для запроса и документа $inline$ (маршрут из А в Б):

Флаг, была ли ранее поездка по маршруту.
Когда была совершена предыдущая поездка по маршруту.
Отношение поездок по маршруту ко всем историческим поездкам.

Примеры признаков для пользователя:

Количество поездок пользователя за последние K дней.
Количество избранных и флаги наличия домашнего адреса и адреса работы.
Статистики по историческим поездкам (среднее, квантили, медиана дистанции поездки, др.).

В итоге мы получили больше 100 признаков, которые описывают пару объектов запрос-документ. Так как мы хотим максимизировать Precision@1/2/3, то логично, что нужно прогнозировать вероятность поездки пользователя в конкретный конечный пункт и ранжировать возможных кандидатов по полученной вероятности. Мы пробовали разные алгоритмы и разные функции потерь, и остановились на градиентном бустинге на деревьях и loglossе. Результаты, которые были получены на момент использования эвристики:

	Эвристика	ML-алгоритм
Precision@1	0,657	0,789
Precision@2	0,719	0,872
Precision@3	0,761	0,923

Production

Естественно, что прежде чем придумывать какие-то сложные алгоритмы, фичи и обучать модели, нужно подумать о том, как это всё будет работать в бою под нагрузкой, при этом не забывая о масштабировании. Собравшись с командой backend-разработки, мы набросали примерную схему того, как должен выглядеть наш сервис. Обученную модель машинного обучения мы решили обернуть в async-await web-фреймворк Sanic, на который будет слать запросы сервис поиска. Помимо вертикального масштабирования мы реализовали возможность деплоя на несколько машин. Запросы к сервису будут отправляться на URL балансировщика нагрузки, и далее будет происходить проксирование на ту или иную машину алгоритмом Round-robin. После реализации первого прототипа сервиса мы поняли, что можем значительно сократить объем запросов в MySQL. Так как любой сдвиг пина с выбором точки подачи это новый запрос на поиск, а значит и на наш сервис, то мы подумали, что можем хранить кэш с историей поездок пользователя в течение N минут с момента запроса в Redis. Благодаря этому мы сократили нагрузку на базу в три раза. В итоге схему сервиса можно представить так:

Запросы к сервису и его ответы мы храним в ElasticSearch, а метрики, которые отвечают за стабильность работы, мы передаем и мониторим в NewRelic.

Общий рабочий процесс нашего сервиса:

Сервис поиска шлет запрос к сервису поисковых подсказок.
Балансировщик выбирает одну из машин и передает на нее этот запрос.
Внутри машины запрос передается на один из открытых workerов или встает в очередь.
Внутри workera:
1. Валидируем входящий запрос.
2. Делаем запрос в Redis, если истории заказов по пользователю нет, то идем в MySQL и записываем полученные данные в Redis.
3. Делаем базовую предобработку данных и собираем фичи для модели.
4. Делаем predict_proba() по всем сформированным саджестам и сортируем их по вероятности.
5. Делаем дополнительную постобработку данных и формируем ответ.
6. Возвращаем ответ в сервис поиска.

Что дальше?

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

Подробнее..

Категории: Машинное обучение , Machine learning , Анализ данных , Блог компании ситимобил , Ситимобил , Поисковые подсказки , Саджест

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

03.06.2021 20:19:56 |

Автор: admin

Содержание

Введение
Про эксперименты
Что такое сетевой эффект?
Почему 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, Искандеру Мирмахмадову и Виталию Черемисинову.