Хабр·Russia·Wednesday, October 7, 2026 at 09:43 AM UTC

Бакеты вместо миллионов строк: как мы ускоряем рассчёты A/B-тестов без потери точности

Translate

yurkinskaya21 минуту назад

Представьте, что у вас одновременно запущено несколько десятков экспериментов. В каждом миллионы пользователей и несколько метрик с ежедневным пересчётом. У нас как раз такой кейс, поэтому ещё при проектировании платформы мы подумали, что считать метрики на уровне пользователей будет слишком дорого и медленно…

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

Но сразу возникает вопрос: а не теряется ли при этом статистическая корректность? Ведь нам важно оценивать эффект именно на пользователя, а не на бакет, работать со всеми типами метрик, включая ratio, и поддерживать всевозможные сплиты. Кроме того, мы хотим применять CUPED, который снижает дисперсию через исторические данные, но ещё сильнее усложняет расчёты.

Всем привет! На связи команда ABSalute, а именно аналитик Юля и руководитель аналитики Денис. Мы развиваем А/Б-платформу для онлайна X5. В этой статье мы разберём, как устроена статистическая машина внутри ABSalute. Мы пройдём основные шаги нашего вычислительного пайплайна, включая линеаризацию, взвешенную регрессию и CUPED, и покажем, что бакетирование не ломает оценку эффекта на пользователя.

Как мы сжимаем данные

Механика бакетирования

Прежде чем переходить к статистике, нужно разобраться, с какими именно данными мы работаем и как они устроены.

В нашей системе каждый пользователь, попавший в эксперимент, получает два признака. Первый показывает, к какой группе он относится, контрольной или пилотной. Обозначаем его как $G_u \in \{0, 1\}$ . Второй определяет номер одного из 256 бакетов. Обозначаем его как $b(u) \in \{0, . . . , 255\}$ . Оба признака вычисляются по $\texttt{user\_id}$ и $\texttt{experiment\_id}$ , но через разные процедуры. Распределение в группу происходит в два этапа.

Этап 1. Попадание в эксперимент.

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

$\texttt{slot}(u) = \text{hash}(\texttt{user\_id}, \texttt{layer\_id}) \bmod M_{\text{slots}}.$

Пользователь участвует в эксперименте, только если его слот заранее для этого зарезервирован. Это исключает пересечение конфликтующих экспериментов на одном слое.

Этап 2. Распределение по группам.

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

Бин пользователя вычисляется по формуле:

$\texttt{bin}(u) = \text{hash}(\texttt{user\_id}, \texttt{salt}) \bmod 100,$

где $\texttt{salt}$ — уникальная строка для каждого теста, а группа пользователя зависит от того, в какой бин он попал.

Распределение в бакет

Номер бакета вычисляется отдельной формулой:

$b(u) = \text{hash}(\texttt{user\_id}, \texttt{experiment\_id}) \bmod 256.$

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

Почему бакет не зависит от группы

Группа и бакет вычисляются разными хэшами с разными входными данными. Хорошая хэш-функция не создаёт систематической связи между полученными значениями. На практике это означает, что в каждом бакете пользователи распределены по группам ровно в той же пропорции, что и во всём эксперименте. Если сплит 90/10, то в каждом бакете тоже будет примерно 90% пользователей из пилотной группы и 10% из контрольной. Бакет ничего не знает о группе.

Структура датафрейма

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

поле	обозначение	смысл
numerator	$N_{bg}$	Сумма вкладов пользователей в числитель метрики
denominator	$D_{bg}$	Сумма вкладов пользователей в знаменатель метрики
users_cnt	$n_{bg}$	Число уникальных пользователей в ячейке

Все метрики в ABSalute записываются в едином формате «числитель/знаменатель», но содержательно делятся на два типа.

У ratio-метрик числитель и знаменатель суммируют разные события пользователя. Классический пример — средний чек. В числителе выручка, в знаменателе число заказов. Формально метрика определяется как отношение математических ожиданий:

$\mu_g = \frac{\mathbb{E}[X_u \mid G_u = g]}{\mathbb{E}[Y_u \mid G_u = g]},$

где $X_u \geq 0$ — вклад пользователя в числитель,

— вклад в знаменатель.

Обратите внимание: это отношение средних, а не среднее отношений. Разница принципиальна.

Simple-метрики считаются как среднее на пользователя. Например, средняя выручка, число сессий и конверсия. Их тоже можно записать как дробь: полагаем $Y_u \equiv 1$ , и тогда знаменателем становится число пользователей:

$\mu_g^{\text{simple}} = \frac{\mathbb{E}[X_u \mid G_u = g]}{\mathbb{E}[1 \mid G_u = g]} = E[X_u \mid G_u = g].$

Формально simple — частный случай ratio, и весь дальнейший пайплайн одинаков для обоих типов. Это принципиальное архитектурное решение. Разделение на simple и ratio нужно только на этапе агрегации по периоду рассчёта, но не в статистических вычислениях. Третье поле users_count отличает наш датафрейм от наивной агрегации и делает возможным все дальнейшие вычисления, включая взвешенную регрессию, корректную оценку эффекта и CUPED.

Две ловушки, в которые легко попасть

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

Первая ловушка: ratio-метрики нельзя усреднять.

Вспомним, что целевая метрика $\mu_g$ — это отношение математических ожиданий $\mathbb{E}[X]/\mathbb{E}[Y]$ . Если для каждого пользователя посчитать индивидуальную дробь и усреднить результаты, мы получим оценку совсем другой величины $\mathbb{E}[X_u / Y_u]$ . В общем случае, эти два функционала не совпадают.

Пользователи с малым знаменателем дают экстремальные значения дроби и перетягивают среднее. По той же причине нельзя рассчитать $N_{bg} / D_{bg}$ по бакету и усреднить результаты. Корректная оценки метрики — это отношение полных сумм: $\hat{\mu}_g = (\sum X_u)/(\sum Y_u).$

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

Вторая ловушка: неравные размеры бакетов.

Мы будем оценивать эффект одной регрессией по всем 512 бакетам, объединяя контрольную и пилотную группы. Если сплит равный (50/50), благодаря хэшированию размеры бакетов почти одинаковые, и проблема невелика. Но далеко не все эксперименты используют равный сплит.

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

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

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

Линеаризация: от поюзерной величины к бакетным агрегатам

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

Дельта-метод: линеаризация на уровне пользователя

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

Разложим функцию в ряд Тейлора первого порядка вокруг точки c

$f(A,B) \approx \frac{a_0}{b_0} + \frac{1}{b_0}(A - a_0) - \frac{a_0}{b_0^2}(B - b_0).$

Раскрываем скобки: $f(A,B) \approx \frac{1}{b_0}A - \frac{a_0}{b_0^2}B \;+\; \frac{a_0}{b_0}.$

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

Оставшаяся часть является линейной функцией от . Это и есть та аддитивная величина на уровне пользователя, которую мы искали в предыдущем разделе. Её можно суммировать по пользователям, усреднять и подставлять в регрессию. Назовём её линеаризованной величиной для пользователя и обозначим $\ell_u$ :

$\ell_u = \frac{1}{b_0}\, X_u - \frac{a_0}{b_0^2}\, Y_u.$

В качестве точки разложения возьмём средние значения на пользователя в контрольной группе:

$a_0 = E[X_u \mid G=0], ~b_0 = E[Y_u \mid G=0].$

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

Рассмотрим пример со средним чеком, который рассчитывается как отношение выручки к числу заказов.

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

Линеаризованный средний чек рассчитывается так: $\ell_u = 0,5 X_u −750 Y_u.$

Для пользователя со средним поведением получаем $\ell_u = 0$ . А если средняя выручка в пилотной группе вырастет до 3200 рублей, при тех же 2 заказа на пользователя, разность средних $\bar{\ell}_1 - \bar{\ell}_0 = 0,5 \times 200 = 100$ рублей будет совпадать с истинным $\Delta\mu = 1600 - 1500 = 100$ рублей.

Будем разбавлять формулы иллюстрациями. Все графики в этой статье построили на одном симулированном эксперименте с параметрами из примера выше. Мы сгенерировали около миллиона пользователей и разбили их на 256 бакетов и на группы контроль/пилот = 90/10. У каждого пользователя два устойчивых признака: интенсивность заказов (в среднем два за период, у трети пользователей заказов не было) и выручка в чеке (в среднем 1500 ₽). Посмотреть код симуляций и графиков можно в репозитории.

Рис. 1. Каждая точка на графике – это линеаризованное значение метрики на пользователя в контроле. Прямая – это множество точек, у которых l_u=0.

Поюзерная модель оценки ATE

Применению регрессии в A/B-экспериментах посвящена отдельная статья наших коллег, которую мы рекомендуем для более глубокого погружения. Здесь ограничимся основными моментами.

Запишем линейную модель для отдельного пользователя, используя линеаризованную метрику :

$\ell_u = \beta_0 + \tau_L\,g_u + \eta_u$

где $\beta_0 = \mathbb{E}[\ell_u \mid G=0]$ — базовый уровень линеаризованной метрики на пользователя в контроле, $\tau_L$ — эффект на пользователя, $g_u \in \{0,1\}$ — индикатор группы, $\eta_u$ — случайная ошибка модели на уровне пользователя.

Матрица регрессоров для пользователя u имеет вид: $x_u = \bigl(1, \;\; g_u\bigr).$

Чтобы оценить $\beta_0$ и по данным, применим обычный метод наименьших квадратов, или МНК (в англоязычной литературе он обозначается как OLS — ordinary least squares). С его помощью подбираются такие $\hat{\beta}_0$ и $\hat{\tau}_L$ , при которых сумма квадратов остатков $\sum_u (\ell_u - \hat{\beta}_0 - \hat{\tau}_L\,g_u)^2$ минимальна. В нашей модели это даёт интуитивно ожидаемый результат — разность средних значений линеаризованной метрики между группами:

$\hat{\tau}_L = \bar{\ell}_1 - \bar{\ell}_0.$

Рис. 2. Прямая оцененной регрессии l_u проходит через точки средних линеаризованных значений метрики в контроле и в пилоте. Усы (±2SE среднего) в пилоте втрое длиннее, потому что пользователей в нём в девять раз меньше.

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

Переход к бакетам: суммирование поюзерной модели

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

$\sum_{u \in i} \ell_u = \beta_0 \sum_{u \in i} 1 \;+\; \tau_L \sum_{u \in i} g_u \;+\; \sum_{u \in i} \eta_u.$

Все пользователи в ячейке принадлежат одной группе, поэтому для всех $u \in i$ . После преобразования сумм получаем:

$\boxed{L_i = \beta_0\,n_i + \tau_L\,(n_i\,g_i) + \varepsilon_i,}$

где $L_i = \sum_{u \in i} \ell_u$ — сумма линеаризованных значений по ячейке, $\varepsilon_i = \sum_{u \in i} \eta_u$ — сумма ошибок.

Таким образом, получаем матрицу регрессоров для ячейки:

$x_i = (n_i, \;\; n_i\,g_i).$

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

$\hat{a}_0 = \frac{\sum_b N_{b_0}}{\sum_b n_{b_0}}, \qquad \hat{b}_0 = \frac{\sum_b D_{b_0}}{\sum_b n_{b_0}}.$

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

$L_{bg} = \frac{1}{\hat{b}_0}\,N_{bg} - \frac{\hat{a}_0}{\hat{b}_0^2}\,D_{bg}.$

Рис. 3. Прямые – средний чек контроля и пилота как отношение сумм по группе. Контрольные точки-ячейки лежат кучнее, потому что в них аггрегировано в девять раз больше пользователей. Связь с рис.1: оси те же, что на рис. 1, и точка-ячейка на данном графике – это центр облака пользователей, сбакетированных в эту ячейку. Поэтому аналогично расстояние от точки до прямой контроля, делённое на b₀, – это линеаризованное значение ячейки ℓ̄_i. У контрольных ячеек оно около нуля, у пилотных около 100.

Зафиксируем обозначения до конца статьи:

— линеаризованное значение для пользователя,
— сумма по ячейке (линеаризованный бакет),
$\bar{\ell}_i = L_i / n_i$ — среднее на пользователя.

Для simple-метрик (, ) линеаризация сводится к центрированию $\ell_u = X_u - a_0$ . На бакетах $L_{bg} = N_{bg} - a_0 \cdot n_{bg}$ . Константа сокращается при разности средних, и весь пайплайн работает без изменений.

Что мы получили и чего нам не хватает

Разность средних линеаризованных значений приближает ATE с точностью до остатка второго порядка: $\tau = (\bar{\ell}_1 - \bar{\ell}_0) + O\!\left(\|\Delta\|^2\right),$

где $\Delta = (a_1 - a_0,\; b_1 - b_0)$ . Остаток $O(\|\Delta\|^2)$ — систематическая ошибка (bias), не стохастический шум.

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

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

Однако нам всё ещё нужен корректный способ оценить эту модель. Потому что суммирование поюзерных ошибок по ячейке создаёт проблему: если имеют одинаковую дисперсию $\sigma_{\eta}^2$ и независимы внутри ячейки, то

$\mathrm{Var}(\varepsilon_i) = \mathrm{Var}\!\left(\sum_{u \in i} \eta_u\right) = n_i\,\sigma_\eta^2.$

Получается, что дисперсия ошибки растет с размером ячейки, и возникает гетероскедастичность. Например, для ячейки с 4 000 пользователями дисперсия ошибки будет в четыре раза больше, чем для ячейки с 1 000 пользователей. Обычный МНК не учитывает эту зависимость и рассматривает все наблюдения так, будто дисперсия ошибок у них одинакова, и в результате подстраивается под большие ячейки, у которых большие и большие остатки, в ущерб малым. Поэтому оценка по бакетным суммам не воспроизводит поюзерную модель, а стандартные ошибки, рассчитанные обычным способом, оказываются некорректными. И чтобы учесть разный размер ячеек и вернуть каждому пользователю одинаковый вклад в результат, добавим в регрессию веса.

Взвешенный МНК (WLS)

Почему взвешенный МНК даёт эффективную оценку при гетероскедастичности

Каждому наблюдению i присваивается вес , и регрессия минимизирует взвешенную сумму квадратов остатков: $\sum_i w_i\,\hat{e}_i^2 = \sum_i \frac{\hat{e}_i^2}{n_i}.$

Большие ячейки имеют более высокую дисперсию ошибки, поэтому получают меньший вес и перестают доминировать при оценке коэффициентов. Остаётся понять, почему подходят именно такие веса. Есть стандартный факт из теории регрессии: МНК с весами эквивалентен обычному МНК на преобразованных данных, где каждое наблюдение домножено на $\sqrt{w_i}$ . Для наших весов это означает деление на $\sqrt{n_i}$ . Это преобразование не нужно делать руками, потому что оно зашито внутрь формулы взвешенного МНК. Оно помогает увидеть, почему веса работают.

Разделим обе стороны формулы для линеаризованного бакета на $\sqrt{n_i}:$

$\underbrace{\frac{L_i}{\sqrt{n_i}}}_{\tilde{y}_i} = \beta_0\,\underbrace{\frac{n_i}{\sqrt{n_i}}}_{\sqrt{n_i}} + \tau_L\,\underbrace{\frac{n_i\,g_i}{\sqrt{n_i}}}_{\sqrt{n_i}\,g_i} + \underbrace{\frac{\varepsilon_i}{\sqrt{n_i}}}_{\tilde{\varepsilon}_i}.$

Теперь посмотрим на дисперсию преобразованной ошибки:

$\mathrm{Var}(\tilde{\varepsilon}_i) = \mathrm{Var}\!\left(\frac{\varepsilon_i}{\sqrt{n_i}}\right) = \frac{\mathrm{Var}(\varepsilon_i)}{n_i} = \frac{n_i\,\sigma_\eta^2}{n_i} = \sigma_\eta^2.$

Дисперсия $\tilde{\varepsilon}_i$ больше не зависит от и становится одинаковой для всех наблюдений. Проблема гетероскедастичности решена. Только делить нужно именно на , потому что чтобы разделить дисперсию на , нужно разделить случайную величину на . Таким образом, мы подаём в регрессию исходные данные и веса .

Рис. 4. Остатки бакетной модели ê_i по размерам ячейки n_i. (а) Разброс растёт как √n_i: у контрольных бакетов втрое шире, чем у пилотных, а обычный МНК считает его одинаковым и ошибается в SE. (б) После деления на √n_i – это и делают веса 1/n_i – разброс одинаковый, и SE верна.

Матричная запись

В матричной форме WLS-оценка записывается как:

$\hat{\beta} = \begin{pmatrix} \hat{\beta}_0 \\ \hat{\tau}_L \end{pmatrix} = (X^\top W X)^{-1} X^\top W y,$

где $y = (L_1, \ldots, L_m)^\top$ — вектор зависимой переменной,

$X = \begin{pmatrix} n_1 & n_1 g_1 \\ \vdots & \vdots \\ n_m & n_m g_m \end{pmatrix}, \quad W = \mathrm{diag}\!\left(\frac{1}{n_1}, \ldots, \frac{1}{n_m}\right).$

Это стандартная формула обобщённого МНК: вместо минимизации $\|y - X\beta\|^2$ мы минимизируем $\|y - X\beta\|^2_W = (y - X\beta)^\top W (y - X\beta)$ , что эквивалентно OLS на преобразованных данных.

Что оценивает τˆ_L

Матричная запись компактная, но непрозрачная. Она не показывает явно к какой именно оценке эффекта мы приходим. Поэтому разберём вычисления по шагам. Любую МНК или взвешенную МНК-оценку можно найти из системы нормальных уравнений. Это условие минимума обычной или взвешенной суммы квадратов остатков, записанное как система линейных уравнений на коэффициенты.

Для обычного OLS условие $\partial/\partial\beta \sum \hat{e}_i^2 = 0$ даёт систему $X^\top X\,\hat{\beta} = X^\top y$ . Для МНК с весами аналогично: $X^\top W X\,\hat{\beta} = X^\top W y$ .

Вычислим $X^\top WX$ и $X^\top Wy$ для нашей модели.

Введём обозначения: $n^{(g)} = \sum_{i:\,g_i=g} n_i$ — суммарное число пользователей в группе , и $S_g = \sum_{i:\,g_i=g} L_i$ — суммарная линеаризованная метрика по группе .

Начнём с . Каждое слагаемое — это $w_i\,x_i\,x_i^\top$ , где $x_i = (n_i,\;n_i g_i)$ , :

$w_i\,x_i\,x_i^\top = \frac{1}{n_i}\begin{pmatrix} n_i \\ n_i g_i \end{pmatrix}\begin{pmatrix} n_i & n_i g_i \end{pmatrix} = \begin{pmatrix} n_i & n_i g_i \\ n_i g_i & n_i g_i^2 \end{pmatrix}.$

Поскольку $g_i \in \{0,1\}$ , имеем . После суммирования по всем ячейкам получаем:

$X^\top W X = \begin{pmatrix} n^{(0)} + n^{(1)} & n^{(1)} \\ n^{(1)} & n^{(1)} \end{pmatrix}.$

Аналогично $X^\top W y$ :

$(X^\top W y)_j = \sum_i w_i\,(x_i)_j\,L_i.$

Первая компонента: $\sum_i \frac{1}{n_i}\cdot n_i \cdot L_i = \sum_i L_i = S_0 + S_1$ .

Вторая: $\sum_i \frac{1}{n_i}\cdot n_i g_i \cdot L_i = \sum_{i:\,g_i=1} L_i = S_1$ .

Система нормальных уравнений :

$(n^{(0)} + n^{(1)})\,\hat{\beta}_0 + n^{(1)}\,\hat{\tau}_L &= S_0 + S_1,$ $n^{(1)}\,\hat{\beta}_0 + n^{(1)}\,\hat{\tau}_L &= S_1.$

Мы получили систему двух линейных уравнений с двумя неизвестными и . Решим её.

$n^{(0)}\,\hat{\beta}_0 = S_0, \qquad\Rightarrow\qquad \hat{\beta}_0 = \frac{S_0}{n^{(0)}} = \frac{\sum_{i:\,g_i=0} L_i}{\sum_{i:\,g_i=0} n_i}.$

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

$n^{(1)}\,\hat{\tau}_L = S_1 - n^{(1)}\,\hat{\beta}_0 = S_1 - n^{(1)}\,\frac{S_0}{n^{(0)}},$ $\hat{\tau}_L = \frac{S_1}{n^{(1)}} - \frac{S_0}{n^{(0)}} = \frac{\sum_{i:\,g_i=1} L_i}{\sum_{i:\,g_i=1} n_i} - \frac{\sum_{i:\,g_i=0} L_i}{\sum_{i:\,g_i=0} n_i}.$

Нигде в выводе не использовалось равенство размеров групп. Полученная формула для верна для любого сплита. При неравном сплите $n^{(0)} \neq n^{(1)}$ , и это автоматически учитывается — каждая группа нормируется на своё суммарное число пользователей.

Эквивалентность поюзерной и побакетной оценок

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

$\hat{\tau}_L = \frac{\sum_{u:\,G_u=1} \ell_u}{n^{(1)}} - \frac{\sum_{u:\,G_u=0} \ell_u}{n^{(0)}} = \bar{\ell}_1 - \bar{\ell}_0.$

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

Рис. 5. Разность между оценкой по бакетам и оценкой по пользователям, одна точка – один эксперимент. Бакетный WLS в точности воспроизводит поюзерный OLS: все его точки лежат на нуле. Бакетный OLS без весов дает небольшое отклонение оценки на ±0,2 ₽ при SE ≈ 3,4 ₽, то есть практическая разница между бакетными оценками не в точке, а в стандартной ошибке (см. рис. 6).

Вот зачем нужна вся цепочка: суммирование сжимает данные с миллионов строк до 512, взвешенный МНК корректно обрабатывает сжатое представление, а на выходе мы получаем ту же оценку, которую бы дали поюзерные вычисления.

Стандартные ошибки: что мы теряем и насколько это критично

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

Поюзерная оценка дисперсии основана на индивидуальных остатках $\hat{\eta}_u = \ell_u - \bar{\ell}_{g_u}$ :

$\hat{\sigma}^2_{\text{user}} = \frac{\sum_u \hat{\eta}_u^2}{N - 2},$

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

Побакетная оценка основана на бакетных остатках $\hat{e}_i = L_i - \hat{\beta}_0 n_i - \hat{\tau}_L n_i g_i$ :

$\hat{\sigma}^2_{\text{bucket}} = \frac{\sum_i \hat{e}_i^2 / n_i}{m - 2},$

где — число ячеек (бакеты контроля плюс бакеты пилота).

Обе оценки несмещены: $\mathbb{E}[\hat{\sigma}^2_{\text{user}}] = \mathbb{E}[\hat{\sigma}^2_{\text{bucket}}] = \sigma_\eta^2$ . Побакетная оценка не занижает и не завышает дисперсию в среднем. Различие заключается в точности самой оценки: она вычисляется по 510 степеням свободы вместо ${\sim}\,10^6$ .

Относительная погрешность оценки дисперсии при $\mathrm{df}$ степенях свободы составляет $\sqrt{2/\mathrm{df}}$ . Для поюзерной оценки: $\sqrt{2/10^6} \approx 0{,}14\%$ , для побакетной: $\sqrt{2/510} \approx 6\%$ .

Но стандартная ошибка зависит от $\sigma$ , а не от $\sigma^2$ . Из разложения в ряд Тейлора следует что если величина отклоняется на $\delta$ , то её корень отклоняется примерно на $\delta / 2$ . Поскольку у нас $\sigma = \sqrt{\sigma^2}$ , относительная погрешность оценки вдвое меньше, чем у . Отсюда погрешность SE при бакетном подходе получается около 6%/2 = 3%.

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

Рис. 6. (а) Отношение SE бакетной оценки (WLS) к поюзерной, по одному значению на эксперимент: среднее 1,00, разброс 3,2 % (при теоретическом (√2/510)/2=3,1%) б) То же отношение для WLS и для OLS без весов на общей оси: при сплите 90/10 стандартная ошибка без весов завышена в 2,1 раза.

CUPED: снижаем дисперсию через прошлое

Идея

У нас есть корректная оценка ATE с корректными стандартными ошибками. Но чем больше дисперсия оценки, тем шире доверительный интервал и тем дольше нужно держать эксперимент, чтобы обнаружить реальный эффект. CUPED, или Controlled-experiment Using Pre-Experiment Data решает эту проблему. Он основан на том, что поведение пользователя до эксперимента обычно коррелирует с его поведением во время эксперимента. Кто много покупал на прошлой неделе, скорее всего, будет много покупать и на этой. Такая корреляция становится источником предсказуемого шума, поскольку часть вариации пост-метрики объясняется устойчивыми привычками пользователей. CUPED «вычитает» эту предсказуемую часть. Эффект остаётся несмещённым, потому что пре-период не зависит от группы, а дисперсия падает. На практике это позволяет обнаружить более маленькие эффекты, либо быстрее находить тот же эффект. В ABSalute в качестве ковариаты мы используем ту же метрику, предварительно линеаризованную, за три недели до старта эксперимента.

Поюзерная модель CUPED.

Начнём с уровня пользователя, а затем агрегируем. Классический CUPED определяет скорректированную метрику так:

$\ell_u^{\text{cuped}} = \ell_u^{\text{post}} - \theta\,(\ell_u^{\text{pre}} - E[\ell^{\text{pre}}]),$

где $\ell_u^{\text{post}}$ , $\ell_u^{\text{pre}}$ — линеаризованные метрики за период эксперимента и за период до эксперимента соответсвенно, $\theta$ — коэффициент, минимизирующий дисперсию $\ell_u^{\text{cuped}}$ .

Варьируя , находим минимум:

$\theta^* = \frac{\mathrm{Cov}(\ell^{\text{post}}, \ell^{\text{pre}})}{\mathrm{Var}(\ell^{\text{pre}})}.$

Это в точности коэффициент линейной регрессии $\ell^{\text{post}}$ на $\ell^{\text{pre}}$ . А значит, вычитание ковариаты вручную эквивалентно добавлению как регрессора в линейную модель:

$\ell_u^{\text{post}} = \beta_0 + \tau_L\,g_u + \gamma\,\ell_u^{\text{pre}} + \eta_u.$

Регрессия сама подберёт оптимальное (минимизирующее дисперсию) $\hat{\gamma} \approx \theta^*$ , и коэффициент при будет CUPED-оценкой эффекта. Никакие дополнительные шаги не нужны, поскольку всё решается одной регрессией.

Почему оценка остаётся несмещённой

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

$\mathbb{E}[\ell_u^{\text{pre}} \mid g_u = 1] = \mathbb{E}[\ell_u^{\text{pre}} \mid g_u = 0].$

Когда регрессор ортогонален другому регрессору, их коэффициенты оцениваются независимо друг от друга. Формально это следствие теоремы Фриша - Во - Ловелла: если некоррелирована с , то коэффициент при одинаков вне зависимости от того, включена ковариата в модель или нет.

CUPED уменьшает дисперсию остатков . Регрессия «объясняет» часть вариации через и то, что остаётся (), менее шумно. В результате точечная оценка не сдвигается, но её стандартная ошибка уменьшается.

Важная оговорка: мы говорим о несмещённости как оценки линеаризованного ATE. Смещение линеаризации , которое мы обсудили в разделе Линеаризация, по-прежнему присутствует, но CUPED его не увеличивает. Совокупное смещение остаётся на уровне, унаследованном от дельта-метода.

Насколько снижается дисперсия

Дисперсия CUPED-оценки связана с дисперсией базовой оценки:

$\mathrm{Var}(\hat{\tau}^{\text{cuped}}) \approx \mathrm{Var}(\hat{\tau}) \cdot (1 - \rho^2),$

где $\rho$ — корреляция между и .

Чем сильнее , тем больше выигрыш. Для поведенческих метрик, таких как выручка, сессии, клики, корреляция между тремя неделями до эксперимента и первой неделей эксперимента обычно составляет = 0,6–0,8. Это означает снижение дисперсии на 36%–64%, что позволяет пропорционально сократить необходимый размер выборки. По данным экспериментов в ABSalute, использование CUPED снижает дисперсию на 45–55% в зависимости от метрики.

Переход к бакетам: суммирование поюзерной модели с CUPED

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

$\sum_{u \in i} \ell_u^{\text{post}} = \beta_0 \sum_{u \in i} 1 + \tau_L \sum_{u \in i} g_u + \gamma \sum_{u \in i} \ell_u^{\text{pre}} + \sum_{u \in i} \eta_u.$

Все пользователи в ячейке принадлежат одной группе ( для всех ). Раскрываем суммы:

$\boxed{L_i^{\text{post}} = \beta_0\,n_i + \tau_L\,(n_i\,g_i) + \gamma\,L_i^{\text{pre}} + \varepsilon_i,}$

где $L_i^{\text{pre}} = \sum_{u \in i} \ell_u^{\text{pre}} = n_i\,\bar{\ell}_i^{\text{pre}}$ , $\;\varepsilon_i = \sum_{u \in i} \eta_u$ .

Матрица регрессоров для ячейки:

$x_i = \bigl(n_i, \;\; n_i\,g_i, \;\; L_i^{\text{pre}}\bigr) = n_i \cdot \bigl(1, \;\; g_i, \;\; \bar{\ell}_i^{\text{pre}}\bigr).$

Применяем МНК с весами , потому что суммирование создаёт гетероскедастичность $\mathrm{Var}(\varepsilon_i) = n_i\,\sigma_\eta^2$ , и веса позволяют корректно с ней работать.

Несмещённость в бакетной модели — это прямое следствие поюзерной конструкции. Рандомизация гарантирует ортогональность и $\bar{\ell}_i^{\text{pre}}$ , и включение ортогонального регрессора не смещает коэффициент при . Коэффициент $\hat{\gamma}$ оценивает $\theta^*$ — то самое оптимальное значение, минимизирующее дисперсию.

Рис. 7. (а) 512 ячеек и две прямые бакетной регрессии с ковариатой: у них общий наклон, поэтому они параллельны, а вертикальный зазор между ними – CUPED-оценка эффекта. Разброс точек вокруг прямых – то, что остаётся от дисперсии после CUPED. (б) Распределение оценки эффекта в 1000 экспериментах без CUPED и с ним: центр тот же (истинные 100 ₽)

Препериод тоже линеаризован, и это важно

В поюзерной модели в качестве ковариаты используется линеаризованная препериодная метрика $\ell_u^{\text{pre}} = \frac{1}{b_0^{\text{pre}}} X_u^{\text{pre}} - \frac{a_0^{\text{pre}}}{(b_0^{\text{pre}})^2} Y_u^{\text{pre}}$ .

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

$L_i^{\text{pre}} = \frac{1}{\hat{b}_0^{\text{pre}}}\,N_i^{\text{pre}} - \frac{\hat{a}_0^{\text{pre}}}{(\hat{b}_0^{\text{pre}})^2}\,D_i^{\text{pre}},$

где точки линеаризации $(\hat{a}_0^{\text{pre}}, \hat{b}_0^{\text{pre}})$ оцениваются по контрольной группе на данных препериода. Эта конструкция требует пояснения по двум пунктам.

Почему линеаризованная ковариата

Формально в модель можно подставить сырую ratio-метрику $N_i^{\text{pre}}/D_i^{\text{pre}}$ . Рандомизация гарантирует независимость от группы для любой преэкспериментальной величины, будь то линеаризованная метрика , сырая дробь или любая другая функция от данных до эксперимента. Оценка останется несмещённой при любом выборе ковариаты.

Но «можно» не значит «оптимально». CUPED снижает дисперсию пропорционально корреляции между ковариатой и зависимой переменной. Если ковариата линеаризована тем же преобразованием, она является линейной функцией от тех же величин с теми же коэффициентами, и корреляция между ними максимальна. Дробь — другая функция тех же данных, и поэтому её корреляция с $L_i^{\text{post}}$ слабее. Снижение дисперсии будет менее эффективным.

Почему точка линеаризации оценивается на данных препериода

С точки точки зрения несмещенности выбор или $(\hat{a}_0^{\text{post}}, \hat{b}_0^{\text{post}})$ формально безразличен.

Однако оценка точки линеаризации для ковариат по препериоду обеспечивает методологическую чистоту: ковариата строго принадлежит препериоду и не зависит от постэкспериментальных данных. На практике при стационарном поведении пользователей $\hat{R}_A^{\text{pre}} \approx \hat{R}_A^{\text{post}}$ , и оба выбора дают близкую корреляцию $L^{\text{pre}}$ с $L^{\text{post}}$ . Тем не менее пре-периодная точка предпочтительнее с методологической точки зрения. Для каждого периода точка линеаризации оценивается по данным этого же периода, а ковариата не использует никакой информации, появившейся после начала эксперимента.

Заключение

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

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

View the original on Хабр →

KioskNews shows a cleaned-up reading view extracted from the publisher’s page — the original always lives on their site, not ours.