Дельта метод в АБ-тестах. Часть 2

Всем привет!

Эта статья является продолжением большого обсуждения дельта-метода.

В первой части мы рассмотрели введение, дали необходимую математическую базу метода и рассмотрели первый прикладной кейс, где дельта-метод будет эффективным - Lift-метрики.

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

Региональные тесты (Cluster randomized experiments)

Два ключевых понятия в типичном A/B-тесте — это единица рандомизации (уровень гранулярности, на котором выполняется рандомизация) и единица анализа (уровень агрегации, на котором производится вычисление метрики). Проводить анализ АБ-тестов несложно, когда единицы рандомизации и анализа совпадают, например, когда рандомизация проводится по пользователю, и одновременно вычисляется средний доход на пользователя.

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

Мы рассматриваем две усреднённые метрики test- и control-групп, которые предполагаются независимыми. Без потери общности сосредоточимся только на test-группе с K кластерами. Для i=1,…,K i-й кластер содержит N_i наблюдений на уровне единицы анализа Y_{ij}. Тогда соответствующая средняя метрика имеет вид:

Предполагаем, что внутри каждого кластера наблюдения Y_{ij}​ независимы и одинаково распределены с математическим ожиданием μ_i и дисперсией (σ_i)^2​, а между кластерами тройки (μ_i,σ_i,N_i) также независимы и одинаково распределены.

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

При строгих предположениях для этой задачи существуют решения (тут можно почитать или статья - Allan Donner. Statistical methodology for paired cluster designs). Когда N_i = m и (σ_i)^2 = σ^2 для всех i:

Однако, к сожалению, хотя формула и является теоретически корректной, её практическая ценность ограничена, поскольку сделанные предположения нереалистичны: в действительности размеры кластеров N_i и распределения Y_ij для каждого кластера i различны, что означает, что μ_i и (σ_i)^2 также различны.

Другим распространённым подходом является модель со смешанными эффектами (mixed effect model), также известная как многоуровневая/иерархическая регрессия (тут можно почитать), где Y_ij зависит от μ_i и σ_i^2 , а сами параметры подчиняются «распределению более высокого порядка». В этих условиях мы можем вывести эффект treatment как «фиксированный» эффект для индикаторного терма при treatment (т.е. коэффициент при treatment в лин. регрессии).

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

Дельта метод решает проблему напрямую, исходя из определения метрики.

Перепишем Y (c крышечкой) как:

Хотя Y (с крышечкой) не является средним независимых одинаково распределённых случайных величин, оно представляет собой отношение двух i.i.d. средних величин на уровне единицы рандомизации, поэтому мы можем применить дельта-метод:

Таким образом, дисперсия Y (с крышечкой) зависит от дисперсии центрированной версии S_i (с поправкой на N_i).

Интуитивно и дисперсия размера кластера N_i, и дисперсия внутрикластерной суммы наблюдений S_i вносят вклад в дисперсию. В частности, σ_N^2 = Var(N_i) является важным вкладчиком в дисперсию Y (с крышечкой), что приводит к практической рекомендации для экспериментаторов: желательно делать размеры кластеров однородными; в противном случае может оказаться трудно выявить небольшие эффекты test из-за низкой статистической мощности.

Моделирование

Пусть общее число кластеров K = 1000.

Чтобы имитировать гетерогенность кластеров, мы делим их на три категории: малые, средние и крупные. Число кластеров в трёх категориях мы генерируем из следующего мультиномиального распределения

Для i-го кластера, в зависимости от того, к какой категории он относится,

мы генерируем N_i, μ_i и σ_i следующим образом:

Для каждого фиксированного i пусть Y_ij ∼ Bernoulli(p = μ_i) для всех j = 1, . . . , N_i. Такой выбор мотивирован бинарными метриками. Благодаря этому мы можем определить истинное значение E(Y (с крышечкой)) = 0.667, вычислив средне-взвешенное μ_i, где веса - это размеры кластеров и соотношение малых, средних и больших кластеров.

Наша цель — вывести E(Y (с крышечкой)), и мы сравниваем 2 метода:

1. Наивный метод, предполагающий, что все наблюдения Y_ij независимы и одинаково распределены (тут просто применяют базовые формулы для оценки дисперсии из статистики);
2. Использование метрики Y (с крышечкой), как в первом методе, но для оценки дисперсии применяется дельта-метод.

Исходя из выше описанного механизма генерации данных, мы многократно и независимо генерируем 1000 наборов данных. Для каждого набора мы вычисляем точечные оценки и оценки дисперсий E(Y (с крышечкой)), используя наивный и дельта-метод. Затем мы вычисляем средние истинные дисперсии для двух методов и сравниваем их со средними значениями оценённых дисперсий.

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

Оценка квантилей

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

Даже в этом случае дельта-метод может быть очень полезен!

Давайте дадим теоретическую основу для метода:

Теоретический p-й квантиль распределения F определяется как:

Для простоты восприятия этой записи представлю график:

Что такое X_(1), ..., X_(n)?

Обычная случайная выборка: (4.2, 2.7, 5.0, 3.6, 2.9)

X_(1), ..., X_(5) - отсортированная выборка (выборка порядковых статистик):

Как делать оценку квантили в АБ-тестах?

Для простоты мы используем X(⌊np⌋), так как это не повлияет на асимптотические результаты.

Хорошо известен тот факт, что выборочная оценка квантили является асимптотически нормальной оценкой (теорема 1):

Доказательство теоремы можно глянуть тут

Однако, к сожалению, на практике мы редко имеем i.i.d.-наблюдения.

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

Чтобы упростить дальнейшие обозначения, положим:

Хотя формула из теоремы 1 теоретически корректна, трудность её применения на практике заключается в знаменателе f{F^{-1}(p)}, вычисление которого требует знания неизвестной функции плотности f в неизвестной квантильной точке F^{-1}(p).

Как построить доверительный интервал для квантилей?

Ядерное сглаживание плотности

Первый подход состоит в том, чтобы оценить f по наблюдённым X_i, используя непараметрические методы, такие как ядерная оценка плотности.

Идея метода:

1. В каждой точке выборки x_i​ ставится «окно» (ядро) — сглаживающая функция, чаще всего колоколообразная (например, гауссовское ядро).
2. Эти ядра суммируются, и получается сглаженная оценка плотности.
3. Ширина окна (параметр сглаживания h) контролирует баланс:

слишком маленький h → оценка рваная (переобучение),

слишком большой h → сглаживание слишком сильное (потеря деталей).

Формула:

Однако любой непараметрический метод оценки плотности балансирует между смещением и дисперсией. Чтобы уменьшить дисперсию, приходится вводить более сильное сглаживание и, следовательно, большее смещение. Эта проблема менее критична для квантилей в «теле» распределения, например, медианы, где плотность велика и больше данных находится вокруг квантили, что делает дисперсию меньше. Но по мере того, как мы переходим к хвосту, например, к 90%, 95% или 99% квантилям, шум в оценке плотности становится больше, и мы вынуждены вводить больше сглаживания и большее смещение. Так как плотность появляется в знаменателе и в хвосте часто стремится к нулю, даже небольшое смещение в оценённой плотности может привести к большому смещению в оценённой дисперсии

Бутстрэп

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

Внешние доверительные интервалы

Альтернативный метод, не требующий оценки плотности, называется «внешний доверительный интервал» (outer CI), который даёт замкнутую формулу для доверительных интервалов квантилей, используя комбинаторные рассуждения.

Вспомним, что Y_i:

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

Если Y_i - i.i.d., то сумма их имеет биномиальное распределение.

При большом n:

Если:

То логично, что среднее значение Y_i = r/n.

Тогда доверительный интервал для r/n:

Это означает, что с 95% вероятностью истинный процентиль находится между нижним рангом:

и верхним рангом:

Традиционный внешний ДИ зависит от того, что X_i независимы и одинаково распределены. Но если есть кластеры, то σ^2/n вместо p(1 − p)/n просто принимает другую формулу по дельта-методу, и результат выше всё равно сохраняется. Следовательно, доверительный интервал для квантили можно вычислить следующими шагами:

Моделирование

Для проверки дельта-метода мы используем сравнение его ошибки со стандартным непараметрическим бутстрэпом (N_B = 1000 реплик). Моделирование состоит из N_u = 100, . . . , 10000 пользователей (кластеров), при этом у каждого N_{u_i} = 1, . . . , 10 наблюдений (N_{u_i} равномерно распределены). Каждое наблюдение является суммой двух i.i.d. случайных величин X_{u_i} = X_i + X_u, где X_u фиксирован для каждого пользователя. Рассматриваем два случая: один симметричный и один с тяжёлым хвостом распределения:

Получаются следующие результаты (для оценки 95 квантиля):

Выводы:

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

Всем спасибо за внимание!