Последовательный анализ Вальда

TL;DR
Позволяет ускорить тесты конверсий примерно на 60%. Эффективен в случае быстро вызревающих метрик и при отсутствии сезонностей.

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

Проблема
Хотим проводить эксперименты быстрее. Fixed-horizon подход требует заранее выбрать размер выборки Ν. При таком размере выборки мы сможем уверенно различить гипотезу Η(0) и альтернативу Η(1), разница между которыми равна MDE. Но можно ли сократить N, если анализировать данные по мере поступления, не дожидаясь завершения эксперимента?

Предположения
– Заранее определяем MDE.
– Знаем параметрическое семейство для выборки (например, бернуллиевское).
– Выборка из независимых и одинаково распределённых величин.

Решение
Фиксируем:
– вероятности ошибок α и β,
– минимальный эффект δ (MDE).
Вычисляем:
– границы A и B (по α и β).

Во время теста:
1. Добавляем наблюдение x.
2. Считаем логарифм отношения правдоподобий λ(x).
3. Если λ(x) < A → принимаем H(0);
если λ(x) > B → принимаем H(1);
иначе — продолжаем.

Алгоритм реализован для случая конверсий.

Достоинства
Алгоритм подходит для использования на быстро вызревающую конверсию в качестве целевой метрики теста.
– Минимизирует среднее N при H(0) и при H(1). Практическое ускорение порядка 60%.
– Позволяет быстрее остановить тест, если изменения больше MDE δ.
– Величины A, B, λ(x) считаются быстро и просто.
– Можно оценить среднюю длительность теста при планировании эксперимента.

Ограничения
Общие для последовательных критериев
– Очень сложно применять, если метрика долго вызревает.
– При завершении теста мы не всегда можем построить хороший доверительный интервал для значения метрики.
– Обладает меньшей мощностью в сравнении с fixed horizon подходом. Это не позволяет всегда останавливать тест быстрее, чем в fixed horizon подходе.

Специфичные для Вальда
– Если мы не знаем параметрическое семейство, величину λ(x) не посчитать. Это существенно для неконверсий.
– Требует, чтобы данные были одинаково распределены. При внутридневной сезонности критерий становится некорректным.
– Сложно адаптировать на тесты с несколькими выборками и метриками.

Библиография
– Вальд А. Последовательный анализ. – 1960.
– Подглядывай правильно: как ускорить принятие решений с помощью последовательного анализа.
– Реализация для конверсий.
– Калькулятор для среднего размера выборки.
– Tartakovsky A., Nikiforov I., Basseville M. Sequential analysis: Hypothesis Testing and Changepoint Detection. – CRC Press, 2014.