В институтах студентов учат интегрировать аналитически, а потом обнаруживается, что на практике интегралы почти все считают численными методами. Ну или по крайней мере проверяют таким образом аналитическое решение.
В статистике тоже есть нечестный метод, который позволяет получить примерный ответ на многие практические вопросы без анализа, грубой компьютерной силой: бутстрап (англ. bootstrap). Придумал и опубликовал его в 1979 году Брэдли Эфрон.
Допустим, есть у нас интернет-магазин, где мы торгуем всякой всячиной и привлекаем клиентов разными способами. Понятное дело, что мы постоянно что-то тестируем — расположение картинок и кнопок на странице, рекламный текст, AdWords, баннеры на сайтах партнёров и так далее. И вот свежие результаты — в тестовой группе из 893 пришедших у нас что-то купили 34, а в контрольной группе из 923 пришедших что-то купили 28.
Возникает вопрос — идти к начальству и говорить «в тестовой группе конверсия 3.81%, в контрольной группе 3.03%, налицо улучшение на 26%, где моя премия?» или продолжать сбор данных, потому что разница в 6 человек — ещё не статистика?
Эту задачу несложно решить аналитически. Видим две случайные величины (процент конверсии в тестовой и контрольной группе). При большом количестве наблюдений биномиальное распределение похоже на нормальное. Нас интересует разность. Нормальное распределение бесконечно делимо, вычитаем матожидания и складываем дисперсии, получаем матожидание 34/893-28/923 = 0.77% и дисперсию (34/893)*(1-34/893)/893+(28/923)*(1-28/923)/923. Стандартное отклонение равно корню из дисперсии, в нашем случае 0.85%. Истинное значение с 95% вероятностью лежит в пределах плюс-минус двух стандартных отклонений от матожидания, то есть между -0.93% и 2.48%.
Так что премия пока не светит, надо продолжать собирать данные.
Теперь решим эту же задачу бутстрапом. Основная идея такова: хорошо бы повторить наш эксперимент много раз и посмотреть на распределение результатов. Но мы это сделать не можем, поэтому будем действовать нечестно — надёргаем выборок из имеющихся данных и сделаем вид, что каждая из них — результат повторения нашего эксперимента.
Алгоритм:
- Выбираем наугад одно наблюдение из имеющихся.
- Повторяем пункт 1 столько раз, сколько у нас есть наблюдений. При этом некоторые из них мы выберем несколько раз, некотороые не выберем вообще — это нормально.
- Считаем интересующие нас метрики по этой новой выборке. Запоминаем результат.
- Повторяем пункты 1-3 много раз. Например, 10 тысяч. Можно меньше, но точность будет хуже. Можно больше, но долго будет считать.
Теперь у нас есть распределение, на которое мы можем посмотреть или что-то по нему посчитать. Например, доверительный интервал, медиану или стандартное отклонение.
Обратите внимание на то, что мы не делаем никаких предположений о распределении чего-либо. Распределения могут быть несимметричными, с толстыми хвостами и вообще иметь причудливую форму. Алгоритм от этого не меняется.
Чудес, правда, не бывает. Если у распределения нет матожидания (такие встречаются), бутстрап его не найдёт. Ну то есть он найдёт матожидание выборки, но не генеральной совокупности. То же касается ситуации, когда выборка нерепрезентативна или просто маленькая.
Бутстрап прост в имплементации. Приведённый ниже пример написан на C (проще не бывает) и кроме ввода-вывода использует только две библиотечные функции: генератор псевдослучайных чисел и сортировку. Разберём его по частям.
Пролог особых комментариев не требует. В C нет bool, данные будем хранить в int.
#include <stdio.h>
#include <stdlib.h>
typedef int Data_t;
#define ARRAY_SIZE(x) sizeof(x)/sizeof(x[0])
Функция, которая на лету делает выборку и считает по ней процент конверсии.
Правильнее было бы использовать более точный алгоритм вычисления среднего значения,
но для нашего примера это не важно.
static double bootstrap(const Data_t* data, unsigned n)
{
unsigned i;
double sum = 0;
for (i = 0; i < n; i++) {
sum += data[rand() % n];
}
return sum / n;
}
Функция сравнения для сортировки результатов
static int compare(const void* a, const void* b)
{
if (*(double*)a > *(double*)b) return 1;
if (*(double*)a < *(double*)b) return -1;
return 0;
}
Исходные данные
int main(int argc, char* argv[])
{
Data_t test[893] = { 0 };
Data_t control[923] = { 0 };
unsigned i;
for (i = 0; i < 34; i++) {
test[i] = 1;
}
for (i = 0; i < 28; i++) {
control[i] = 1;
}
Инициализируем генератор псевдослучайных чисел параметром из командной строки. Если мы
всё сделали правильно, то результаты не должны сильно плавать при изменении этого
параметра.
if (argc == 2) {
srand(atoi(argv[1]));
}
Сюда будем складывать результаты
double t_minus_c[10000];
Главный цикл
for (i = 0; i < ARRAY_SIZE(t_minus_c); i++) {
t_minus_c[i] = bootstrap(test, ARRAY_SIZE(test))
- bootstrap(control, ARRAY_SIZE(control));
}
Определяем 95% доверительный интервал: cортируем результаты, отбрасываем 2.5% снизу и столько же сверху, показываем результат.
qsort(t_minus_c, ARRAY_SIZE(t_minus_c), sizeof(double), compare);
printf("LCL=%g%%n", 100. * t_minus_c[250]);
printf("UCL=%g%%n", 100. * t_minus_c[9750]);
return 0;
}
Проверяем:
$ gcc -Wall -o bootstrap bootstrap.c $ ./bootstrap LCL=-0.891368% UCL=2.43898%
Ещё пару раз с другими псевдослучайными числами:
$ ./bootstrap 42 LCL=-0.86589% UCL=2.43898% $ ./bootstrap 2013 LCL=-0.959673% UCL=2.52184%
Похоже на теоретический результат (от -0.93% до 2.48%).
И зачем было огород городить?
У этой задачи есть простое аналитическое решение, но у многих реальных задач его или нет вообще, или оно есть, но очень сложное. Представьте, что вместо процента конверсии нас интересует отношение прибыли от клиента к затратам на его привлечение. Распределение такой метрики вряд ли будет нормальным, и формулы перестанут укладываться в пару строчек. А бутстрап будет работать точно так же, достаточно поменять Data_t на double и положить туда новые данные.
Первоисточники
- Efron B (1979). Bootstrap methods: Another look at the jackknife. Ann. Statist. 7 1–26
- Donald E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming, chapter 4.2.2, page 232. Addison-Wesley, Boston, third edition, 1998.
Автор: dimview
