Конформные пороговые интервалы для эффективной регрессии

Основная информация

• ID статьи: 2407.14495
• Название: Conformal Thresholded Intervals for Efficient Regression
• Авторы: Rui Luo (City University of Hong Kong), Zhixin Zhou (Alpha Benito Research)
• Классификация: cs.LG, stat.ML
• Время публикации/конференция: AAAI 2025
• Ссылка на статью: https://arxiv.org/abs/2407.14495
• Ссылка на код: https://github.com/luo-lorry/CTI

Аннотация

В данной работе предлагается метод конформных пороговых интервалов (Conformal Thresholded Intervals, CTI) — новый подход к конформной регрессии, направленный на получение минимальных предсказательных множеств при гарантированном уровне покрытия. В отличие от существующих методов, опирающихся на вложенную конформную схему и полную оценку условного распределения, CTI использует готовые многовыходные квантильные регрессии для оценки условной плотности вероятности попадания нового ответа в каждый межквантильный интервал. Используя обратную зависимость между длиной интервала и плотностью вероятности, CTI строит предсказательные множества путём пороговой обработки межквантильных интервалов на основе их длины. Оптимальный порог определяется с использованием калибровочного набора для обеспечения маргинального покрытия, эффективно балансируя компромисс между размером предсказательного множества и уровнем покрытия.

Исследовательский контекст и мотивация

Постановка проблемы

Конформное предсказание — это мощный фреймворк для построения предсказательных множеств с гарантиями покрытия на конечных выборках. Существующие методы конформной регрессии подразделяются на две основные категории:

1. Прямое использование моделей квантильной регрессии для предсказания нижней и верхней границ интервала
2. Предварительная оценка полного условного распределения с последующей инверсией для получения предсказательного множества

Ограничения существующих методов

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

Исследовательская мотивация

• Существующие методы могут производить субоптимальные предсказательные множества при асимметричных условных распределениях
• Требуется метод, который одновременно адаптируется к локальной плотности данных и является вычислительно эффективным
• Желательно избежать сложности оценки полного условного распределения

Основные вклады

1. Предложение метода CTI: новый подход к конформной предсказательной регрессии, использующий многовыходные квантильные регрессии для оценки межквантильных интервалов и построения предсказательных множеств путём их пороговой обработки
2. Теоретический анализ: доказательство того, что CTI гарантирует маргинальное покрытие и при определённых условиях достигает желаемого условного покрытия и минимальной ожидаемой длины предсказательного интервала
3. Экспериментальная верификация: обширные численные эксперименты на смоделированных и реальных наборах данных, демонстрирующие, что CTI производит меньшие предсказательные множества при сохранении эффективного покрытия
4. Практическая применимость: метод прост в реализации и интерпретации, привлекателен для практиков, ищущих надёжное количественное определение неопределённости

Описание метода

Определение задачи

Дан набор данных регрессии $\{(x_i, y_i)\}_{i=1}^n$, где $x_i \in \mathcal{X} \subseteq \mathbb{R}^d$, $y_i \in \mathcal{Y} \subseteq \mathbb{R}$. Цель состоит в построении конформного предсказателя, который для каждого тестового входа $x$ выдаёт предсказательное множество $C(x) \subseteq \mathcal{Y}$, удовлетворяющее условию: $P(Y \in C(X)) \geq 1-\alpha$ при одновременной минимизации ожидаемого размера предсказательного множества.

Архитектура модели

Ключевая идея

Ключевое понимание CTI заключается в использовании обратной зависимости между длиной интервала и плотностью вероятности. Для условной плотности вероятности $f(y|x)$, если квантильная регрессия достаточно точна, то: $f(y|x) \approx \frac{1}{K \cdot \mu(I_k(x))}$ где $\mu(I_k(x))$ — длина интервала $I_k(x)$.

Алгоритм

Шаг 1: Многовыходная квантильная регрессия Применение квантильной регрессии на обучающем наборе для предсказания $\tau$-квантилей условного распределения $Y|X=x$: $\hat{q}_k(x) \text{ для } k = 0, 1, \ldots, K$ где $\tau = k/K$.

Шаг 2: Определение межквантильных интервалов$I_k(x) = (\hat{q}_{k-1}(x), \hat{q}_k(x)] \text{ для } k = 1, \ldots, K$

Шаг 3: Построение предсказательного множества Пороговая обработка на основе длины интервала: $C(x) = \bigcup\{I_k(x) : \mu(I_k(x)) \leq t, k = 1, \ldots, K\}$

Шаг 4: Определение порога Использование калибровочного набора для определения порога $t$: $t = (1-\alpha)\text{-й квантиль } \frac{1}{1+|\mathcal{I}_{cal}|}\sum_{i \in \mathcal{I}_{cal}} \delta_{\mu(I_{k(y_i)}(x_i))} + \delta_\infty$

Технические инновации

1. Стратегия прямой пороговой обработки: в отличие от CHR, требующего явного разбиения пространства ответов, CTI непосредственно обучает модель многовыходной квантильной регрессии
2. Глобальная пороговая обработка: CTI применяет глобальный подход к пороговой обработке межквантильных интервалов для всех значений $x$, повышая эффективность маргинального покрытия
3. Теоретическая оптимальность: на основе леммы Неймана-Пирсона CTI теоретически приближается к оптимальному предсказательному множеству

Экспериментальная установка

Наборы данных

Смоделированные данные:

• Генерация $n = 10000$ образцов, $X_i \sim \text{Uniform}[0,1]$
• Переменная ответа: $y \sim \text{Triangular}(0, x, x)$
• Условная плотность: $f(y|x) = \frac{2y}{x^2}\mathbf{1}\{y \in (0,x)\}$

Реальные наборы данных (13 наборов): bike, bio, blog, community, concrete, facebook1, facebook2, homes, meps19, meps20, meps21, star и др.

Метрики оценки

1. Покрытие (Coverage): доля предсказательных множеств, содержащих истинное значение
2. Размер предсказательного множества (Size): средняя длина/мера предсказательного множества

Методы сравнения

• Split Conformal: базовый метод разделённого конформного предсказания
• CQR (Conformal Quantile Regression): конформная квантильная регрессия
• CHR (Conformal Histogram Regression): конформная гистограммная регрессия

Детали реализации

• Разделение данных: 20% тестирование, остаток: 70% обучение, 30% калибровка
• Количество квантилей: $K = 100$
• Базовые модели: случайный лес (RF) и нейронная сеть (NN)
• Повторные эксперименты: 10 независимых запусков
• Уровень значимости: $\alpha = 0.1$ (90% покрытие)

Результаты экспериментов

Основные результаты

Результаты на смоделированных данных:

• Теоретический ожидаемый размер множества CTI: 0.317
• Теоретический ожидаемый размер множества CHR: 0.342
• Теоретический ожидаемый размер множества CQR: 0.376
• Фактическая производительность CTI: CTI(RF) 0.345±0.005, CTI(NN) 0.369±0.015
• Все методы достигли примерно 90% покрытия

Результаты на реальных наборах данных: На 11 из 13 наборов данных CTI производит меньшие предсказательные множества, чем другие методы, при этом сохраняя требуемый уровень покрытия.

Ключевые находки

1. Последовательное преимущество: CTI превосходит базовые методы на большинстве наборов данных
2. Зависимость от модели: эффективность CTI зависит от качества базовой модели квантильной регрессии
3. Вызовы на малых наборах данных: на наборах данных с малым объёмом выборки (например, star, n=2161) CQR может показать лучшую производительность

Абляционные эксперименты

Анализ длины интервала: Сравнение распределения длин интервалов ответов со всеми интервалами показывает, что производительность CTI зависит от конкретного набора данных и базовой модели квантильной регрессии. Теоретически средние значения двух распределений должны быть равны, но на практике существует смещение, подчёркивающее зависимость метода от данных и модели.

Связанные работы

Методы квантильной регрессии

• Традиционные методы: Hunter & Lange (2000), Meinshausen (2006) и др.
• Оценка множественных квантилей: Cho et al. (2017) показали, что одновременная оценка нескольких квантилей более эффективна, чем отдельная оценка
• Ограничения на пересечение: Moon et al. (2021), Brando et al. (2022) и др. решают проблему пересечения квантилей

Методы конформного предсказания

• Вложенное конформное предсказание: Romano et al. (2019), Sesia & Candès (2020) и др.
• Методы оценки плотности: Izbicki et al. (2020), Sesia & Romano (2021) и др.
• Инновация данной работы: прямая оценка условной плотности вероятности вместо полного условного распределения

Заключение и обсуждение

Основные выводы

1. CTI предоставляет простой и эффективный метод конформной регрессии
2. Путём пороговой обработки межквантильных интервалов CTI может производить меньшие предсказательные множества, чем существующие методы
3. Метод имеет теоретическую поддержку леммы Неймана-Пирсона, гарантирующей оптимальность
4. Экспериментальная верификация подтверждает эффективность метода на множестве наборов данных

Ограничения

1. Ограничение на форму интервала: текущая реализация не гарантирует, что предсказательное множество всегда имеет форму интервала
2. Зависимость от модели: производительность сильно зависит от точности базовой модели квантильной регрессии
3. Вызовы на малых выборках: на малых наборах данных может быть менее эффективным, чем традиционные методы
4. Выбор параметров: выбор количества квантилей K требует баланса между выразительной способностью и вычислительной эффективностью

Направления будущих исследований

1. Разработка вариантов CTI, которые гарантируют интервальную форму предсказательных множеств
2. Улучшение производительности в случаях малых выборок
3. Исследование методов адаптивного выбора количества квантилей K
4. Интеграция с другими методами количественного определения неопределённости

Глубокая оценка

Преимущества

1. Прочная теоретическая база: теоретическая гарантия оптимальности на основе леммы Неймана-Пирсона
2. Простота метода: избегает сложности оценки полного условного распределения
3. Обширные эксперименты: всестороннее тестирование на смоделированных и реальных данных
4. Высокая практическая ценность: простота реализации и интерпретации, подходит для практиков
5. Сильная инновационность: успешное применение идей пороговой обработки из классификации к задачам регрессии

Недостатки

1. Область применения: может показать слабую производительность на наборах данных с малым объёмом выборки
2. Форма предсказательного множества: не может гарантировать интервальную форму предсказательного множества, может производить несвязные множества
3. Чувствительность к гиперпараметрам: относительно чувствителен к выбору количества квантилей K
4. Теоретический анализ: некоторые теоретические результаты основаны на достаточно сильных предположениях

Влияние

1. Академический вклад: предоставляет новые идеи и методы для области конформного предсказания
2. Практическая ценность: простота и эффективность обеспечивают хорошие перспективы применения
3. Воспроизводимость: предоставление открытого исходного кода облегчает воспроизведение и расширение

Сценарии применения

1. Наборы данных среднего и большого размера: лучшие результаты при достаточном объёме выборки
2. Количественное определение неопределённости: задачи регрессии, требующие надёжных доверительных интервалов
3. Приложения в реальном времени: сценарии с высокими требованиями к вычислительной эффективности
4. Задачи с асимметричными распределениями: проблемы регрессии с асимметричными условными распределениями

Библиография

1. Romano, Y., Patterson, E., and Candès, E. (2019). Conformalized quantile regression. NeurIPS.
2. Sesia, M., and Romano, Y. (2021). Conformal prediction using conditional histograms. NeurIPS.
3. Meinshausen, N. (2006). Quantile regression forests. JMLR.
4. Sadinle, M., Lei, J., and Wasserman, L. (2019). Least ambiguous set-valued classifiers with bounded error levels. JASA.