Усиление повтором: когда хватает трёх запусков, а когда нужна медиана

Если ты отличишь одностороннюю ошибку от двусторонней, посчитаешь ошибку большинства из трёх запусков и объяснишь, почему оценки усиливают медианой, а не средним, - листай до «Теперь сам».

Как думаешь, что дадут три запуска

Алгоритм отвечает «да» или «нет» и ошибается в 25% запусков. Его запустили трижды, независимо, и взяли ответ, который встретился чаще.

Ответь себе до чтения: какова вероятность, что итоговый ответ неверен? Напрашивается 0,25³ ≈ 1,6%. Но это вероятность того, что ошиблись все три запуска, а большинству достаточно двух ошибок из трёх. Верный ответ - 15,6%. А 1,6% получилось бы у другого алгоритма с теми же 25% - такого, который ошибается только в одну сторону.

На что это похоже

Датчик дыма, который иногда не срабатывает, но никогда не срабатывает без дыма. Если он пищит - дым есть, сомнений нет. Поставь три таких датчика: пожар будет пропущен, только если промолчат все три. Это односторонняя ошибка, и её гасит правило «достаточно одного сигнала».

Трое часов, каждые из которых могут и спешить, и отставать. Тут одного показания мало: непонятно, какие часы врут. Остаётся верить двум совпавшим. Это двусторонняя ошибка, и чтобы большинство ошиблось, должна ошибиться половина часов, а не все.

Механизм: три вида ошибки - три способа повтора

Односторонняя ошибка. Один из ответов всегда верен. Тест Миллера-Рабина из раздела про числа: ответ «составное» - истина, ответ «простое» неверен с вероятностью не больше 1/4. Запускаем k раз с разными случайными основаниями. Если хоть раз получено «составное» - ответ найден. Ошибка итога - все k запусков ошиблись, а запуски независимы:

P(ошибка) ≤ pᵏ           p = 1/4:   k = 3 → 1/64,   k = 10 → 10⁻⁶,   k = 20 → 10⁻¹²

Двусторонняя ошибка, ответ «да» или «нет». Каждый запуск ошибается с вероятностью p < 1/2. Берём ответ большинства из k запусков. Итог неверен, когда ошиблось больше половины. Число ошибок - сумма независимых индикаторов со средним pk, и ему нужно уйти от среднего до k/2, то есть доля ошибок должна отклониться на 1/2 − p. По границе Хёфдинга:

P(ошибка большинства) ≤ e^(−2k · (1/2 − p)²)

Показатель пропорционален k, но множитель при нём - квадрат зазора между p и половиной. Если p близко к 1/2, каждый запуск почти ничего не сообщает, и повторов нужно очень много. При p = 1/2 запуск - это монета, и усилить нечего.

Числовая оценка. Алгоритм возвращает число, и оно «хорошее» - попадает в нужный отрезок вокруг истинного значения - с вероятностью не меньше 3/4. Плохая оценка может быть какой угодно, в том числе огромной. Запускаем k раз и берём медиану - число, которое стоит посередине после сортировки. Медиана плоха, только если плохих оценок не меньше половины: иначе хороших больше половины, они лежат рядом, и середина отсортированного списка попадает в их отрезок. По той же границе с зазором 1/4:

P(медиана плоха) ≤ e^(−2k · (1/4)²) = e^(−k/8)

Среднее арифметическое здесь не работает: одна плохая оценка, улетевшая на тысячу, сдвигает среднее всех k на 1000/k.

Если оценка в среднем равна истинному значению и имеет конечную дисперсию, но недостаточно надёжна даже на 3/4, её сначала улучшают усреднением: среднее t независимых оценок имеет дисперсию в t раз меньше, и по Чебышёву попадает в нужный отрезок с вероятностью 3/4 при подходящем t. Потом берут медиану нескольких таких средних. Приём называется медиана средних: среднее сужает разброс, медиана поднимает надёжность.

Во всех трёх формулах ошибка убывает экспоненциально по k, поэтому k, пропорциональное log n, делает её меньше 1/nᶜ для любой заранее выбранной постоянной c. Про событие, вероятность нарушения которого не больше 1/nᶜ, говорят, что оно происходит с высокой вероятностью.

Правило

Независимые повторы снижают вероятность ошибки так: при односторонней ошибке p - до pᵏ; при двусторонней с p < 1/2 ответ большинства из k запусков неверен с вероятностью не больше e^(−2k(1/2 − p)²); медиана k оценок, каждая из которых хороша с вероятностью не меньше 3/4, плоха с вероятностью не больше e^(−k/8). Чтобы вероятность ошибки стала не больше 1/nᶜ, во всех трёх случаях достаточно O(log n) повторов, если p и зазор до половины не зависят от n.

Разбор: большинство из k запусков, точный счёт

Вероятность того, что из k запусков ошиблись ровно j, равна C(k, j) · pʲ · (1 − p)ᵏ⁻ʲ: число способов выбрать, какие j запусков ошиблись, на вероятность такого набора. math.comb(k, j) - это число сочетаний C(k, j). Ошибка большинства - сумма по j больше половины.

import math

def oshibka_bolshinstva(p, k):
    summa = 0
    for j in range(k // 2 + 1, k + 1):
        summa = summa + math.comb(k, j) * p ** j * (1 - p) ** (k - j)
    return summa

for p in [0.1, 0.25, 0.4]:
    stroka = [p]
    for k in [1, 3, 5, 11, 21]:
        stroka.append(round(oshibka_bolshinstva(p, k), 6))
    print(stroka)

[0.1, 0.1, 0.028, 0.00856, 0.000296, 1e-06]
[0.25, 0.25, 0.15625, 0.103516, 0.034328, 0.006423]
[0.4, 0.4, 0.352, 0.31744, 0.246502, 0.174378]

В строке - вероятность ошибки одного запуска и ошибка большинства при 1, 3, 5, 11 и 21 запуске. При p = 0,1 три запуска снижают ошибку до 2,8%, а двадцать один - примерно до одной миллионной. При p = 0,25 три запуска оставляют 15,6%, двадцать один - 0,6%. При p = 0,4 даже двадцать один запуск оставляет 17%: зазор до половины всего 0,1, и в показателе стоит его квадрат.

Ответ на вопрос «когда хватает трёх запусков»: когда ошибка односторонняя или когда двусторонняя ошибка одного запуска уже мала. В остальных случаях три запуска - это самоуспокоение.

Разбор: медиана против среднего

Оценка с вероятностью 3/4 попадает в отрезок от 97 до 103 вокруг истинного значения 100, а с вероятностью 1/4 завышена на что угодно от 3 до 500. Для каждого k - четыреста опытов: доля промахов медианы, доля промахов среднего и граница e^(−k/8).

import math
import random

def ocenka():
    if random.random() < 0.75:
        return 100 + random.uniform(-3, 3)
    return 100 + random.uniform(3, 500)

random.seed(24)
opytov = 400
for k in [1, 5, 15, 31]:
    promahov_mediany = 0
    promahov_srednego = 0
    for opyt in range(opytov):
        ocenki = []
        for i in range(k):
            ocenki.append(ocenka())
        mediana = sorted(ocenki)[k // 2]
        srednee = sum(ocenki) / k
        if abs(mediana - 100) > 3:
            promahov_mediany = promahov_mediany + 1
        if abs(srednee - 100) > 3:
            promahov_srednego = promahov_srednego + 1
    print(k, promahov_mediany / opytov, promahov_srednego / opytov, round(math.exp(-k / 8), 4))

1 0.2475 0.2475 0.8825
5 0.085 0.755 0.5353
15 0.0075 0.9775 0.1534
31 0.0 1.0 0.0208

random.uniform(a, b) возвращает случайное дробное число от a до b. Медиана из пяти оценок промахивается в 8,5% опытов, из пятнадцати - в 0,75%, из тридцати одной не промахнулась ни разу. Граница e^(−k/8) выполнена везде с запасом.

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

Граница всех трёх приёмов - независимость запусков. Если повторы используют одни и те же случайные числа, они совершают одну и ту же ошибку, и большинство из ста одинаковых ответов ничем не лучше одного. Вторая граница - ошибка должна быть случайной. Оценка, которая на данном входе завышает всегда, после любого числа повторов остаётся завышенной: повторы убирают невезение, а не систематическую ошибку.

Что ломается без этого

pᵏ для двусторонней ошибки. Так считают, перенося формулу с Миллера-Рабина на любой рандомизированный алгоритм. Для большинства из трёх при p = 1/4 это ошибка в десять раз: 1,6% вместо 15,6%.

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

Среднее вместо медианы. Десять оценок, девять около 100 и одна 5000, дают среднее 590. Медиана тех же десяти - около 100.

Большинство там, где хватило бы одного сигнала. Если ответ «нет» всегда верен, голосовать незачем: первый же «нет» закрывает вопрос, и снижение идёт как pᵏ, а не как у большинства.

Зачем это в работе

Проверка простоты при генерации ключей: число раундов теста выбирают так, чтобы 1/4ᵏ стало меньше вероятности аппаратного сбоя. Сорок раундов дают 2⁻⁸⁰, и ошибку теста можно больше не учитывать.

Вероятностные структуры из следующих глав устроены как усилители. Count-minРазбирается в разделе 20, глава «Фильтр Блума, count-min, HyperLogLog»: Count-min: частоты миллиона ключей в таблице фиксированного размера хранит несколько строк счётчиков и берёт минимум: его ошибка односторонняя, оценка только завышает, и минимум играет роль «достаточно одного честного ответа». Оценка второго момента потокаРазбирается в разделе 20, глава «Потоковые алгоритмы и резервуарная выборка»: Отпечаток мультимножества и второй момент: два потока в одном числе усредняет несколько счётчиков и берёт медиану средних - ровно по схеме этого урока.

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

Выражение «с высокой вероятностью» в описаниях алгоритмов значит конкретную вещь: вероятность неудачи не больше 1/nᶜ. Оно выбрано под оценку объединения: если каждая из n операций неудачна с вероятностью 1/n², то хоть одна из них - не больше 1/n.

Теперь сам

1. Ошибка односторонняя, p = 1/2. Сколько запусков нужно, чтобы вероятность ошибки стала меньше одной тысячной?
2. Ошибка двусторонняя, p = 0,25. Посчитай руками вероятность ошибки большинства из трёх запусков.
3. Ошибка двусторонняя, p = 0,4, запусков 500. Оцени ошибку большинства по формуле; e⁻¹⁰ ≈ 0,00005.
4. Каждая оценка хороша с вероятностью 3/4. Сколько оценок нужно для медианы, чтобы она была плоха с вероятностью не больше 0,001? Используй ln 1000 ≈ 6,9.
5. Каждая из 1000 вставок в структуру неудачна с вероятностью не больше одной миллиардной. Оцени вероятность того, что неудачна хотя бы одна.