CUPED (Controlled-experiment Using Pre-Experiment Data) — техника A/Б-экспериментов, которую стали применять в продакшене сравнительно недавно. Она позволяет увеличить чувствительность метрик за счёт использования данных, полученных ранее. Чем больше чувствительность, тем более слабые изменения можно замечать и учитывать в эксперименте. Первой компанией, внедрившей CUPED, была Microsoft. Теперь этой техникой пользуются многие международные фирмы. В своём докладе Валерий Бабушкин venheads объяснил, в чём заключается смысл CUPED и каких результатов можно достичь, а перед этим разобрал метод стратификации, который также улучшает чувствительность.


— Меня зовут Валерий Бабушкин, я директор по моделированию и анализу данных в X5 Retail Group и советник в Яндекс.Маркете. В свободное время преподаю в Высшей школе экономики и частенько летаю в Казахстан, преподаю в Нацбанке Казахстана.

Помимо этого, раньше я любил заниматься соревновательным машинным обучением. На платформе Kaggle я в свое время добился звания Competitions Grand Master и 23 места в мировом рейтинге из 120 тысяч. Kaggle устроен очень простым образом: не выступаешь — падаешь в рейтинге. Так что я стараюсь туда больше не заходить, чтобы не видеть эти цифры.



В моей презентации будет два этапа: стратификация и Control Variates. Скорее всего, вы знаете, что такое А/Б-тесты и зачем они нужны. Но эту формулу мы не будем пропускать.



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

В частотном подходе есть одна простая формулка. Их две, но одна рассматривает случай дискретного распределения, другая — непрерывного распределения, поэтому будем считать это одной формулкой.

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

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

Мы видим здесь очень простую формулку для n, где n — количество наблюдений, которое необходимо в каждой из групп. В числителе $z^2$, где $z^2$ — доверительный интервал, та степень надежности, с которой мы хотим наш результат выдавать.

Кажется очевидным, что $z$ мы фиксируем один раз и дальше менять не можем. Мы, конечно, можем сказать, что результат выдаем с нулевой степенью надежности, и тогда нам нужно ноль наблюдений. Это было бы очень удобно, но так мы обычно не делаем.

Дальше в числителе, если мы посмотрим на дискретную формулку, находится $\hat{p}(1-\hat{p})$, что равняется дисперсии биномиального распределения. В непрерывном случае — то же самое, ?2, то есть дисперсия. И кажется логичным, что чем больше дисперсия, тем больше наблюдений нам нужно.

В знаменателе же находится m2 или margin of error — та минимальная разница, которую мы хотим поймать, и тут ситуация обратная. Чем меньше разницу мы хотим поймать, тем больше наблюдений нам нужно. То есть это нечто вроде погрешности.

Если нам нужна погрешность 0,01, то там нужно в 100 раз больше наблюдений, чем если нам нужна погрешность 0,1. Они отличаются между собой в десять раз, но там квадратичная зависимость, получается, что нужно в 100 раз больше наблюдений.

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

А если мы дисперсию уменьшим в два раза, то нам нужно всего в два раза больше наблюдений. Поэтому уменьшить что-то в четыре раза в знаменателе — это выигрыш в 16 раз, а в четыре раза в числителе — всего в четыре.

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

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



Итак, поговорим про стратификацию. Что мы знаем? Мы знаем, что снижение дисперсии снижает количество наблюдений. Допустим, наша искомая метрика, по которой мы проводим анализ, может быть разбита по каким-то регионам, по группировкам. Очень хороший вопрос, который уже был задан: как это разбивать? По странам? А может, по браузерам? Может, пойти в операционные системы? Может, пользователи, которые заходят с Mac, Windows и Linux — это три разных типа пользователей.

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

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

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



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

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

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

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

Пока все кажется довольно разумным. И в итоге дисперсия по всему стратифицированному будет равна вот такой формулке. Неважно, если вы сейчас не понимаете, почему. Главное — запомнить.



Теперь поговорим о среднем и дисперсии при случайном сэмплировании. SRS — это simple random sampling, то есть случайное сэмплирование.

Как можно догадаться, среднее значение случайного сэмплирования равно среднему. Тут особо, я думаю, не нужно во что-то углубляться. А вот дисперсия случайного сэмплирования, если посмотреть в классической формуле, очень понятна. Это ?2, умноженная на единицу, деленная на n. Если мы вспомним формулу стандартной ошибки, то это ?, деленная на корень из n. Это дисперсия среднего.

Но хочется разбить ее на составляющие.



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



Запомните вот это. Это дисперсия в случае стратификации, верьте мне.



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

В чем суть? Если кратко подумать, то дисперсия случайного сэмплирования может быть представлена в виде суммы дисперсии внутри группы стратифицированной, и между стратифицированными группами. Есть n групп, присутствует дисперсия a внутри группы, b — дисперсия между группами. Если кто-то помнит, оно примерно также там считается анализ. Там есть дисперсия внутри группы и дисперсия между группами. Логично.

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



Это то же самое, что я говорил сейчас, так что это пропустим. Но у вас же будет наверняка интерес разобрать то, о чем я говорил. Кстати, внизу каждого слайда есть название статьи, из которой эта формула взята. В этой презентации участвовало три статьи, можете потом почитать*.

Прочитали какую-то статью, что-то поговорили, но это не очень интересно. Интересно посмотреть, как что-то работает в реальной жизни. Про это — следующий слайд.



Я взял данные, начал смотреть, как это работает в реальной жизни. В реальной жизни дисперсия у меня снизилась аж на один процент.

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

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

Перейдем ко второй части. Cuped. Я точно не знаю, как правильно произносить, по факту это ковариаты, используем экспериментальные данные.



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

Как этого добиться? Проще всего взять переменную X, которая была получена еще до начала эксперимента. Тогда мы можем быть точно уверены, что эксперимент на нее не повлиял.

Дальше. Мы можем представить новую метрику, которую мы хотим рассчитывать как разность Y и ?X. Это и представлено в формулке: новая метрика, назовем ее Ycuped, — это наша искомая метрика минус ?, умноженная на X.

То, о чем мы уже говорили. Простая формулка, которая позволяет нам вычислить дисперсию разницы двух величин. Это дисперсия первой величины. Так как у нее коэффициент единица, 12, мы ее убираем. Плюс коэффициент второй величины ?2, дисперсия X. Но так как это вычитание, то минус 2?, ковариация между Y и X.

Если бы это были независимые величины, чему это было бы равно? Нулю. Ковариация между независимыми величинами равна нулю. Кажется, что если мы возьмем независимую величину, то тогда у нас лучше точно не станет.



Тогда надо взять какую-то зависимую величину, и у нас же есть еще один гиперпараметр, назовем его ?. Когда мы можем минимизировать дисперсию? Когда ? у нас равна ковариации между Y и X, деленная на дисперсию X.



Я сейчас не буду подробно рассматривать, почему это так, но если вы посмотрите на это простое уравненьице, то тоже сможете это вывести.



Если мы так сделаем, у нас получится очень удобное простое преобразование, и итоговая дисперсия будет представлена в виде дисперсии Y, умноженной на единицу минус корреляция в квадрате между метрикой Y и метрикой X. Кажется, неплохо.

Почему это работает? Мы делаем некое предположение, что у нас дисперсия нашей метрики Y обусловлена двумя факторами или двумя причинами. Она обусловлена каким-то ковариатом X и всем остальным. Мы же можем так сделать, правильно? И говорим: ребята, то, что у нас обусловлено X, мы убираем, оставляем только то, что обусловлено всеми другими причинами.



Из графика на следующем слайде будет понятно, почему это работает. Есть мысли на тему, почему это работает? Кроме той формулы, которую я написал, до этого же тоже были формулы. Оказалось, что не работает. В конце концов, мы еще не видели итоговые результаты, там тоже окажется, что не работает.

Что нас интересует в первую очередь, когда мы проводим А/Б-тесты? Разница средних. В подавляющем большинстве случаев мы не смотрим какие-то квантили. Хотя, кстати, Uber очень любит смотреть на квартили, и иногда на них смотреть очень важно, средние могут остаться неизменными, квантили — резко поменяться, и начнут отваливаться пользователи, у которых увеличился какой-нибудь 99-процентный квантиль. У Uber это время ожидания. Это хозяйке на заметку.

Но нас зачастую интересует разница средних. И нам хочется использовать такие методы, которые эту разницу средних не изменяют. Потому что если мы говорим про линеаризацию, то мы переходим в новое признаковое пространство. Да, все круто. Мы можем посчитать какой-нибудь А/Б-тест в 64 раза быстрее. Да, он пропорционален, но мы не можем сказать, насколько эта разница средних действительно такова.

Чтобы посчитать разницу средних и сделать вывод обо всем, нужно иметь ?, единую на все группы. Группа — это A1, A2, B, C и так далее. Это тестовые ячейки или вариации вашего А/Б-теста.

Как же выбрать метрику X? Логичным выбором метрики X будет та же самая метрика Y, но на периоде, предшествующем периоду эксперимента. Например, если это у вас продолжительность сессии для пользователя средняя, то вы можете посчитать среднюю продолжительность сессии пользователя до эксперимента за какой-то период, во время эксперимента, вычесть одну из другой, и посмотреть только отклонения между ними. Это вас, наверное, интересует больше.

Тут, кстати, возникает интересный вопрос — за какой период нам брать метрику X? За один день, за неделю, за две недели? Теоретического ответа нет, а практический ответ показывает, что две недели — это плюс-минус оптимум. В принципе, можно на экспериментальных данных взять и построить график того, насколько снижается дисперсия и насколько у нас быстрее сходится тест в зависимости от того, за какой период мы берем X.



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

Что мы делаем? Подбираем ?. Мы точно так же можем подобрать ее через метод наименьших квадратов. То есть это некая средняя линия, которая дает минимальную сумму остатков. Остаток — разница между тем, что есть, и тем, что на линии.

Таким образом, мы как-то пытаемся усреднить и по-прежнему получаем среднее значение метрики. Среднее значение метрики не меняется. Мне кажется, я сам не до конца понял, что сказал сейчас, и вам наверняка пришлось еще тяжелее, потому что я-то это уже видел. Попробуем еще раз. У нас есть ось X и есть ось Y. Мы можем на оси X отметить те значения, которые были до эксперимента, а на оси Y — соответствующие значения в период эксперимента. То есть мы получаем некую точку в координатах XY. Можем ее отметить на графике.

Если у нас никаких изменений не произошло, то у нас эти точки будут совпадать. Это у нас будет биссектриса. Потому что X равно Y. Но по факту такого не будет, согласны? В каких-то случаях значение метрики Y будет больше, в каких-то случаях меньше.

Нам хочется понять и получить именно эту разницу. Потому что все остальное нас не так интересует. Например, если у нас нет никакой разницы, мы провели эксперимент и X равно Y — значит, наш эксперимент, скорее всего, не повлиял. Если мы провели наш эксперимент и видим, что Y просто стабильно выше этого X везде, это уже повод задуматься, что, возможно, на что-то мы повлияли. Если у нас стабильно Y ниже X, тоже не очень хорошо. Скорее всего, мы повлияли в минус.

Получается, что мы пытаемся провести некую линию, которая описывает зависимость между X и Y, минимизируя эту разницу. Линейная регрессия так же делается. Согласитесь, что есть линейная регрессия, у вас, считайте, одна независимая переменная и одна зависимая переменная. Вы хотите провести описывающую максимально точно.

Это и есть наша линия, это и есть наша новая метрика cuped, и это именно то, почему среднее значение cuped не меняется. Значение Ycuped не будет меняться от значения Y среднего. Почему? Потому. Надо было сразу так объяснять. :) Кстати, в оригинальной статье так и говорится: обратите внимание, есть очень интересная связь между поиском ? и проведением регрессии. Это оно и есть.

Повторюсь, нам интересно посмотреть, как сам эксперимент повлиял на пользовательское поведение, насколько оно изменилось относительно базового. Предположим, он всегда проводился и есть два пользователя: один всегда имел сессию длиной десять минут, а другой — 100 минут. Тут произошло какое-то изменение, и первый пользователь по-прежнему проводит 100 минут, а у второго стало 12 минут. Разница в одном случае ноль, в другом — два. Но просто сравнивать между собой цифры 12 и 100, наверное, не очень разумно. Нам хочется другого. Назовем это «нормализовать». Это, конечно, не корректно, но тем не менее.

Теперь перейдем к эксперименту.



Что мы видим? Это скриншот из Jupyter ноутбука, который я очень не люблю (больше люблю PyCharm), но все же я это сделал. Здесь уже представлена дисперсия метрики cuped и дисперсия стандартной метрики. Видите, как они сильно различаются? Ycuped сильно меньше, а средние не отличаются.

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

Что мы здесь видим? Дисперсия упала на 45%. Это данные из онлайна. То, что мы наблюдали в X5, — это что дисперсия падает в четыре раза. В X5 у нас есть какое-то поведение в рамках магазина, оно может быть среднее для дня недели, для часа, для часа и дня недели. Видите, мы можем подбирать ковариаты, которые все более и более коррелируют. Кажется, что условное количество людей, которое пришло в понедельник, должно коррелировать с количеством людей, которые пришли в следующий понедельник. Если мы рассматриваем чуть глубже, то понедельник, шесть часов вечера, должен еще сильнее коррелировать с понедельником, шесть часов вечера. А воскресенье, три часа дня, с другим воскресеньем, три часа дня.

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



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

В некоторых случаях могут быть сложности в том, как правильно подбирать ковариат, но зачастую это не проблема. Всегда можно (очень редко, когда нельзя) взять значение за предыдущий экспериментальный период. Это работает. Снижение дисперсии в 19 раз означает, что количество данных, необходимых для А/Б-теста, тоже снижается в 19 раз. То есть вы тем самым можете быстрее получить ваш результат, а это повышает чувствительность теста.

Если у вас уже есть какое-то количество А/Б-тестов, то вы можете точно так же ретроспективно прогнать этот cuped, посчитать ошибки первого рода и второго рода. Ошибки первого рода вы можете посчитать, если проводите AA-тест. На cuped вы его проведете точно так же — и точно так же сможете оценить, насколько у вас увеличилась чувствительность.


* Использованные статьи:
Improving the Sensitivity of Online Controlled Experiments by Utilizing Pre-Experiment Data
Improving the Sensitivity of Online Controlled Experiments: Case Studies at Netflix
How Booking.com increases the power of online experiments with CUPED