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

Всем привет!

В этом посте я хочу:

1. Собрать супер подробную информацию о дельта-методе.
2. Дать так информацию, чтобы любой читатель, который когда-то видел, как считать производные, мог объяснить, откуда взялись известные формулы для дельта-метода.
3. Сравнить его с различными методами, которые используются для решения рассматриваемой прикладной задачи, и убедить себя и вас отказаться в использовании этих методов (например, бутстрапа) для построения CI в пользу использования дельта-метода.

Перед тем, как нам начать говорить про дельта-метод дадим предпосылки. Для этого давайте рассмотрим - ЦПТ (центральную предельную теорему):

Обычное применение центральной предельной теоремы заключается в построении 100(1 - alpha)% доверительного интервала для mu в виде:

Хотя центральная предельная теорема является величайшим результатом, в своей базовой форме она применима только к среднему i.i.d. случайных величин, тогда как на практике наши метрики часто более сложны. Чтобы воспользоваться плюсами больших данных, мы применяем дельта метод, который широко обобщает результаты ЦПТ.

Дельта-метод

Не пугайтесь! Давайте разберём по пунктам все слова:

Что такое вообще эти T_n?

Это на самом деле это и есть ваша метрика, которую вы считаете, чтобы оценить матожидание или перцентиль в АБ-тесте. Вот от всех этих метрик требуется, чтобы выполнялось условие нормальности - т.е. выполнение ЦПТ. На практике все метрики из АБ-тестов подходят под это условие, потому что это в 90% случаев используется - среднее, в 8% - медиана, в 2% - другие перцентили (проценты условны).

Наверное, вас могло смутить последнее предложение, так как, я, как минимум, забыл сказать про ratio-метрики?

На самом деле я не забыл, потому что ratio-метрики и другие "экзотические" метрики это есть просто какая-то "хорошая" функция от стандартных метрик. Например, конверсия - отношение суммы (среднего) случайных величин на сумму (среднее) случайных величин (среднее количество просмотров / среднее количество показов = конверсия в просмотр из показа).

Как раз вторая часть теоремы нам и говорит, что если мы знаем, как преобразовали наши стандартные метрики (т.е. знаем явно функцию-преобразования phi и эта функция "хорошая" (дифференцируемая)), то мы можем легко оценить, уже параметры преобразованной метрики. Например, в конверсии в качестве преобразования мы используем просто функцию phi = x / y, где в x - мы подставляем количество (или среднее количество) просмотров, а в y - количество (или среднее количество) показов.

Идея метода (что внутри)

Разложим phi по формуле Тейлора:

Мы любую дифференцируемую функцию можем представить в виде суммы полиномов (это и есть формула Тейлора). Но в дельта-методе мы останавливаемся до полинома первой степени, чтобы наша "экзотическая" метрика свелась на самом деле к записи, когда мы можем применить ЦПТ. Делаем несложные преобразования (перенесли влево phi(theta) и умножили на sqrt(n)) и получаем:

Далее - математика, используя условия теоремы, что у нас метрика T_n - асимптотически нормальная (обсуждали выше) и используя другой факт - теорему Слуцкого мы получаем обоснование вывода формулы:

Коротко ещё раз: дельта-метод - это разложение "экзотической" функции в ряд Тейлора до первого полинома и применение ЦПТ к разложению!

Давайте рассмотрим пример:

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

Т.е. исходная у нас метрика T_n - среднее, а преобразование, которое нужно менеджеру, квадрат от этого среднего phi = x^2.

Очень легко можно взять производную от (x^2)' = 2x и подставить в формулу из дельта-метода:

Ну и что мы получаем?

Доверительный интервал для квадрата матожидания для менеджера:

1. Стандартная ошибка:

2. Подставляем оценки параметров, вместо mu, sigma - так как это истинные параметры распределения, которые мы не знаем:

3. Итого доверительный интервал:

Ratio, Ratio, Ratio...

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

А что же делать, когда у нас ratio-метрика или любая другая странная? На примере ratio - это случай из 2-ух метрик и функции phi = x / y.

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

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

Матрица Якоби - это просто многомерная версия производной:

Использование дельта-метода на практике: Lift-метрики

Итак, давайте рассмотрим серию практических сюжетов, в которых разумно использовать дельта-метод.

Предположим, что наша задача - оценить Lift-метрики:

которая оценивается через

Наша ключевая задача — построение 100(1 − α)% доверительного интервала для ∆%. Для этой классической задачи первым решение предложил Фиеллер:

Тогда интервал Фиеллера для ∆% имеет вид:

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

Метод дельты предоставляет более интуитивное альтернативное решение.

Итак, какая функция преобразования в Lift-метрики?

Тогда градиент этой функции:

Откуда следует:

Сделаем замену:

Тогда:

По ЦПТ:

Дисперсия W_i:

Подставим теперь вместо истинных параметров mu, sigma - оценки их:

Стандартная ошибка тогда:

Итоговый доверительный интервал для Lift-метрики:

Формула из результата дельта-метода легче реализуется, чем формула Фиеллера, и фактически является пределом её в случае большой выборки:

НО доверительный интервал Фиеллера может быть более точным для малых выборок.

Как можно улучшить точность дельта-метода?

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

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

Итак, разложение до второго порядка выглядит следующим образом:

где

А H - матрица Гессе (матрица вторых производных). В случае Lift метрики:

Или

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

Получаем практически формулу на смещение, на которое мы ошибаемся в дельта-методе:

Раскрываем то, что в скобках в матожидании справа:

Получаем точное значение на Bias:

Обратите внимание, что:

Тогда после подстановки выборочных статистик:

Мы получаем финальную формулу оценки bias, которую мы будем прибавлять к формуле доверительного интервала для Lift-метрики:

Итоговый улучшенный дельта-метод с поправкой на смещение:

Численное моделирование:

Берём размер выборки n=20,50,200,2000.

Для каждого фиксированного n предполагаем, что экспериментальная и контрольная группы независимы, и рассматриваем три симуляционных модели для i.i.d. экспериментальных единиц i=1,…,n:

Для каждого случая многократно выбираем M=10,000 наборов данных, и для каждого набора строим интервалы Фиеллера и дельта-метода, а затем добавляем поправку к результату дельта-метода.

Выводы:

• Для больших данных (n≥200) все методы достигают номинальных (т.е. ≈ 95%) ошибок для всех симуляционных моделей.
• Для малых данных (n≤50), хотя интервал Фиеллера кажется более точным для некоторых симуляционных моделей (например, нормальное распределение), другие методы показывают сопоставимые результаты, особенно после поправки на смещение.
• Бутстрап можно не использовать из-за его вычислительно сложности, так как дельта-метод даёт сопоставимые результаты.

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