PAVA (Pool Adjacent Violators Algorithm)

PAVA (Pool Adjacent Violators Algorithm) — это классический и эффективный алгоритм для решения задачи изотонической регрессии. Его название можно перевести как “Алгоритм объединения соседних нарушителей”.

Суть алгоритма в одном предложении:

PAVA последовательно находит и “исправляет” нарушения монотонности в данных, объединяя соседние точки или блоки, которые нарушают требуемый порядок.

---

Как работает PAVA: пошаговый пример

Задача: Найти монотонно неубывающую функцию для данных:

x (уже отсортирован по x): [1,   2,   3,   4,   5,   6]
y (исходные значения):     [0.1, 0.3, 0.2, 0.6, 0.55, 0.7]

Нам нужно преобразовать y в монотонную последовательность f(x).

Шаг 0: Инициализация

Каждую точку считаем отдельным блоком.

Блоки: [0.1], [0.3], [0.2], [0.6], [0.55], [0.7]

Шаг 1: Первое нарушение

Проходим слева направо, проверяя монотонность: 0.1 ≤ 0.3 ✓, 0.3 ≤ 0.2 ✗ (нарушение!). Нарушители — блоки [0.3] и [0.2]. Объединяем их в один блок и присваиваем среднее значение:

Новый блок = (0.3 + 0.2) / 2 = 0.25

Теперь последовательность:

[0.1], [0.25, 0.25], [0.6], [0.55], [0.7]
       ^^^^^^^^^^^^
        объединённый блок

Шаг 2: Проверка назад

После объединения нужно проверить, не возникло ли нарушение с предыдущим блоком ([0.1]). 0.1 ≤ 0.25 ✓ — нарушения нет, идём дальше.

Шаг 3: Второе нарушение

Продолжаем сканирование: 0.25 ≤ 0.6 ✓, 0.6 ≤ 0.55 ✗ (нарушение!). Объединяем [0.6] и [0.55]:

Новый блок = (0.6 + 0.55) / 2 = 0.575

Последовательность:

[0.1], [0.25, 0.25], [0.575, 0.575], [0.7]

Шаг 4: Проверка назад (снова)

После второго объединения проверяем новый блок [0.575] с предыдущим [0.25]: 0.25 ≤ 0.575 ✓ — нарушений нет.

Шаг 5: Завершение

Проверяем последнюю пару: 0.575 ≤ 0.7 ✓. Все нарушения устранены!

Итоговое решение PAVA:

x: [1,    2,    3,    4,    5,    6]
f: [0.1, 0.25, 0.25, 0.575, 0.575, 0.7]

Это кусочно-постоянная монотонная функция.

---

Ключевые свойства PAVA

1. Жадный, но оптимальный: Алгоритм локально объединяет нарушителей, но глобально даёт решение, минимизирующее сумму квадратов ошибок (SSE).
2. Сложность: O(n), работает за один проход с откатами назад.
3. Выход — “ступеньки”: Результатом всегда является кусочно-постоянная функция (серии одинаковых значений).
4. Весовая версия: Существует обобщённая версия, которая учитывает веса наблюдений (например, размер бинов при калибровке). Тогда при объединении считается взвешенное среднее.

Визуализация работы PAVA

Представьте, что вы смотрите на точки слева направо. Как только видите, что следующая точка ниже предыдущей (для неубывающей регрессии), вы:

1. “Схлопываете” эти две точки в одну горизонтальную платформу.
2. Поднимаете левую точку и опускаете правую до их общего среднего уровня.
3. Откатываетесь назад на шаг, чтобы проверить, не создали ли вы новое нарушение с предыдущей платформой.
4. Повторяете, пока все точки не будут упорядочены по возрастанию.

Связь с калибровкой моделей (практическое применение)

В контексте калибровки вероятностей:

1. Вход PAVA: Отсортированные по возрастанию “сырые” предсказания модели (pred) и соответствующие им бинарные метки (y).
2. Работа PAVA: Алгоритм находит оптимальные “ступеньки” — диапазоны предсказаний, внутри которых фактические доли событий постоянны и монотонно растут.
3. Результат: Таблица соответствия:

   Если исходное предсказание p ∈ [0.0, 0.2]   → откалиброванная вероятность = 0.05
   Если исходное предсказание p ∈ (0.2, 0.5]   → откалиброванная вероятность = 0.35
   Если исходное предсказание p ∈ (0.5, 1.0]   → откалиброванная вероятность = 0.8
   

   Эти границы и значения определяются PAVA автоматически.

Преимущества PAVA для калибровки:

• Автоматическое определение бинов: Не нужно заранее задавать количество или границы бинов — PAVA находит оптимальное разбиение.
• Монотонность гарантирована: Калибровочная функция никогда не будет уменьшаться.
• Адаптивность: Может исправить сложные нелинейные перекосы.

Недостаток:

На малых выборках может получиться слишком много “ступенек” (переобучение). На практике иногда используют сглаженные версии или ограничивают минимальный размер блока.

Альтернативы и расширения

• Сглаженный PAVA: Добавляет регуляризацию, чтобы избежать резких скачков.
• Изотоническая регрессия с ограничениями: Можно задать минимальный/максимальный размер блока.

PAVA — это эффективный, интуитивно понятный и широко применяемый алгоритм, который лежит в основе изотонической регрессии. Его ключевая идея — “исправлять монотонность через усреднение” — делает его незаменимым инструментом для постобработки прогнозов, особенно для калибровки вероятностных моделей.