Вальд: последовательный анализ и пробоины

Человек

Абрахам Вальд (1902–1950) родился в Клуже (тогда Австро-Венгрия, ныне Румыния) в ортодоксальной еврейской семье; в школу по субботам не ходил и учился в основном дома. В Вене работал у Карла Менгера, занимался геометрией и математической экономикой (ему принадлежит первое строгое доказательство существования равновесия в модели Вальраса). После аншлюса 1938 года бежал в США. Почти вся его семья погибла в Освенциме.

С 1942 года Вальд работает в Statistical Research Group Колумбийского университета — засекреченной группе, собравшей лучших американских статистиков для военных задач. Группа располагалась в Морнингсайд-Хайтс, в квартале от университета.

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

Задача. Военная приёмка боеприпасов. Есть партия; надо решить, принять её или забраковать. Классическая процедура: выбрать заранее объём выборки $n$, испытать $n$ штук, применить критерий. Но это расточительно: если партия откровенно плоха, это видно уже на десятом изделии, а испытания разрушающие и дорогие.

Идея Вальда: не фиксировать $n$ заранее. Испытывать по одному и после каждого испытания принимать одно из трёх решений: принять, отвергнуть или продолжить.

Последовательный критерий отношения правдоподобия (SPRT). После $n$ наблюдений вычисляем

$$\Lambda_n = \prod_{i=1}^{n} \frac{f_1(x_i)}{f_0(x_i)} .$$

Правило:

$$\Lambda_n \geqslant A \;\Rightarrow\; \text{принять } H_1; \qquad \Lambda_n \leqslant B \;\Rightarrow\; \text{принять } H_0; \qquad B < \Lambda_n < A \;\Rightarrow\; \text{продолжить}.$$

Границы подбираются по желаемым ошибкам первого и второго рода:

$$A \approx \frac{1-\beta}{\alpha}, \qquad B \approx \frac{\beta}{1-\alpha} .$$

Удобнее работать с логарифмами: $\ln \Lambda_n = \sum_i \ln\frac{f_1(x_i)}{f_0(x_i)}$ — случайное блуждание, которое надо остановить при выходе из полосы. Это сразу связывает задачу с классической теорией блужданий и задачей о разорении игрока.

Тождество Вальда. Если $N$ — момент остановки, а $X_i$ независимы и одинаково распределены, то

$$E\left[\sum_{i=1}^{N} X_i\right] = E[N]\cdot E[X_1] .$$

Утверждение неочевидное — $N$ ведь случаен и зависит от самих $X_i$! — и именно оно позволяет вычислить ожидаемое число испытаний. Результат: SPRT в среднем требует на 40–60% меньше наблюдений, чем оптимальный критерий с фиксированным объёмом при тех же ошибках. Позже Вальд и Вольфовиц (1948) докажут, что SPRT в этом смысле оптимален: никакая другая процедура с теми же вероятностями ошибок не обходится в среднем меньшим числом наблюдений.

Метод немедленно засекретили: экономия боеприпасов на приёмке была военным преимуществом. Открытая публикация — книга «Sequential Analysis» — вышла только в 1947 году.

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

Пробоины: что было на самом деле

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

Логика безупречна и стала каноническим примером ошибки выжившего (survivorship bias). Однако стоит быть точным насчёт источников.

Реально сохранились: (1) серия из восьми технических меморандумов Вальда 1943 года, главный из которых называется «A Method of Estimating Plane Vulnerability Based on Damage of Survivors», и (2) два кратких упоминания в мемуарах руководителя группы Аллена Уоллиса, где Вальд по имени даже не назван. Меморандумы засекречены и опубликованы только в 1980–1981 годах Центром военно-морского анализа.

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

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

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

Послевоенная линия: статистика решений

Теория статистических решений. Вальд в книге «Statistical Decision Functions» (1950) строит общую рамку: есть параметр $\theta$, решающее правило $\delta$, функция потерь $L(\theta, a)$, и надо минимизировать функцию риска

$$R(\theta, \delta) = E_{\theta}\left[L\left(\theta, \delta(X)\right)\right].$$

Минимаксное правило минимизирует $\sup_\theta R(\theta,\delta)$ — то есть худший случай. Байесовское правило минимизирует средний риск по априорному распределению. Оценивание, проверка гипотез и прогнозирование оказались частными случаями одной задачи. Это последняя крупная унификация в классической статистике.

Монте-Карло (Лос-Аламос, 1946). Станислав УламСтанислав Улампольско-американский математик · 1909–1984Раскладывая пасьянс после болезни, придумал метод Монте-Карло — считать вероятность не формулой, а перебором случайных исходов. Заодно ему принадлежит схема, сделавшая водородную бомбу возможной., выздоравливая после болезни и раскладывая пасьянс, задумался, как посчитать вероятность его схождения, — и понял, что вместо комбинаторики проще много раз сыграть. Вместе с фон НейманомДжон фон Нейманвенгеро-американский математик · 1903–1957Аксиоматизировал квантовую механику, основал теорию игр, придумал архитектуру компьютера и метод Монте-Карло — и всё это, по мнению современников, не напрягаясь. идея превратилась в метод численного интегрирования для задач нейтронной диффузии; название придумал Метрополис в честь казино, где играл дядя Улама. Метод переворачивает логику науки о случае: раньше вероятность вычисляли, теперь вероятность вычисляет.

Фильтр Калмана (Балтимор, 1960). Рудольф Калман публикует рекуррентный алгоритм оптимальной оценки состояния линейной динамической системы по шумным измерениям. Через девять лет фильтр ведёт «Аполлон-11» к Луне; сегодня работает в каждом GPS-приёмнике. Формально это байесовское обновление гауссовского апостериорного распределения — то есть формула из точки о Байесе, применённая рекуррентно в реальном времени.

Разведочный анализ данных (Принстон, 1977). Джон Тьюки в книге «Exploratory Data Analysis» настаивает: прежде чем проверять гипотезы, надо посмотреть на данные. Изобретает ящик с усами, диаграмму «стебель-лист», медианные сглаживания. Ему же принадлежат слова «бит» и «программное обеспечение» (software) и соавторство в алгоритме быстрого преобразования ФурьеЖозеф Фурьефранцузский математик, физик и префект Изера · 1768–1830Утверждал, что любую функцию можно сложить из синусов, — и был не прав ровно настолько, чтобы математике понадобилось сто лет и три новые теории, чтобы разобраться..

Бутстрэп (Стэнфорд, 1979). Брэдли Эфрон предлагает оценивать точность любой статистики, многократно пересэмплируя саму выборку с возвращением. Если выборка из $n$ элементов, берём $B$ псевдовыборок того же размера и смотрим на разброс интересующей нас величины. Никаких формул, никаких предположений о нормальности, никакого вывода распределений — только вычислительная мощность. Госсет в 1908-м делал это руками с карточками, потому что не мог доказать; Эфрон в 1979-м делает это принципиально, потому что доказывать не нужно.

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

Эпилог

13 декабря 1950 года Абрахам Вальд и его жена погибли в авиакатастрофе: самолёт Air India разбился в горах Нилгири на юге Индии, куда Вальд летел читать лекции по приглашению Индийского статистического института. Человек, научивший мир считать вероятность гибели самолёта, погиб в авиакатастрофе в 48 лет.