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

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

• ID статьи: 2506.19155
• Название: Relative Explanations for Contextual Problems with Endogenous Uncertainty: An Application to Competitive Facility Location
• Авторы: Jasone Ramírez-Ayerbe, Emma Frejinger (CIRRELT и Департамент компьютерных наук и исследований операций, Университет Монреаля)
• Классификация: math.OC (математическая оптимизация и управление)
• Дата публикации: 14 октября 2025 г. (препринт arXiv, версия 3)
• Ссылка на статью: https://arxiv.org/abs/2506.19155v3

Аннотация

В данной работе исследуются задачи контекстной стохастической оптимизации с эндогенной неопределённостью, где решения влияют на базовое распределение. Для практической реализации таких решений критически важно обеспечить их интерпретируемость и надёжность. С этой целью авторы вычисляют относительные контрфактические объяснения, предоставляя практикам конкретные изменения контекстных ковариат, необходимые для удовлетворения решением определённых ограничений. Хотя относительные объяснения были введены в предыдущей литературе, это первая работа, сосредоточенная на задачах с бинарными переменными решений и эндогенной неопределённостью. Авторы предлагают метод, использующий расстояние Вассерштейна в качестве регуляризирующего члена, который сокращает время вычисления по сравнению с нерегуляризованным аналогом.

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

Предпосылки проблемы

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

Основные проблемы

1. Эндогенная неопределённость: переменные решения z влияют на условное распределение вероятностей P(y|z,x) случайной величины y
2. Требования интерпретируемости: необходимо понимать, как изменения контекста приводят к изменениям решений и какие изменения требуются для соответствия решения определённым ограничениям
3. Практические сценарии применения: например, при планировании медицинской инфраструктуры местные органы власти могут спросить, какие минимальные изменения данных приведут к открытию центра в их районе

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

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

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

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

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

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

Для заданной задачи контекстной стохастической оптимизации:

z*(x⁰) ∈ argmax_{z∈Z} E_{P(y|z,x⁰)}[r(y,z)]

где:

• z ∈ Z: вектор переменных решения
• x⁰ ∈ X ⊆ ℝ^{dx}: непрерывные контекстные ковариаты (признаки)
• y: вектор случайных величин, отражающих эндогенную неопределённость
• P(y|z,x⁰): условное распределение вероятностей

Определение относительного контрфактического объяснения

Определение 1.1: Для заданного коэффициента α ∈ (0,∞] и ожидаемого множества D относительное объяснение задачи (1) — это новый контекст x, такой что существует допустимое решение в D, ожидаемое вознаграждение которого изменяется не более чем в α раз.

Основная задача оптимизации

Вычисление относительного объяснения может быть сформулировано как следующая невыпуклая задача оптимизации:

L*_free := min_{x∈X,z∈Z} L(x,x⁰)
s.t. E_{P(y|z,x)}[r(y,z)] ≥ α · E_{P(y|z⁰,x⁰)}[r(y,z⁰)]
     z ∈ D

Функция стоимости и регуляризация Вассерштейна

Функция стоимости принимает следующую форму:

L(x⁰,x) = J(x⁰,x) + λΩ(x⁰,x)

где:

• J(x⁰,x): компонента непохожести
• Ω(x⁰,x): регуляризирующий член, использующий 2-расстояние Вассерштейна

Определение расстояния Вассерштейна: Для двух дискретных распределений вероятностей P⁰ и P квадрат 2-расстояния Вассерштейна определяется как:

W²₂(P⁰,P) := min_{π∈Π} ∑_{c∈C} ∑_{c'∈C} π_{cc'} δ(c,c')²

при ограничениях:

• ∑{c'∈C} π{cc'} = P⁰(c) ∀c ∈ C
• ∑{c∈C} π{cc'} = P(c') ∀c' ∈ C
• π_{cc'} ≥ 0

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

1. Регуляризация расстояния распределений: использование расстояния Вассерштейна для обеспечения близости контрфактического и фактического распределений
2. Модельно-независимые нижние границы: предоставление модельно-независимого метода вычисления нижних границ
3. Индукция разреженности: совместное использование ℓ₁-нормы и регуляризации Вассерштейна для получения разреженных решений

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

Сценарий применения: задача конкурентного размещения объектов на основе выбора (CFLP)

• Модель: мультиномиальная логит-модель (MNL)
• Решение: выбор подмножества кандидатов мест при бюджетных ограничениях для максимизации ожидаемого захвата спроса
• Функция полезности: v_ = -0.1θ_ + x_d, где θ_ — расстояние, x_d — оценка привлекательности

Конфигурация наборов данных

• Малый пример: |N|=4 пользователя, |D|=3 кандидата, |E|=2 конкурента, r=2 открытых объекта
• Крупномасштабные экземпляры:
  • Количество пользователей: 100, 200
  • Количество кандидатов: 10, 20, 40
  • Бюджет: 4, 8
  • Конкуренты: 5 фиксированных объектов

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

• Время вычисления: среднее и медианное время решения
• Расстояние Вассерштейна: W²₂
• Разреженность: процент изменённых контекстных признаков
• Захват спроса: фактический и контрфактический объёмы спроса
• ℓ₁-норма: L1-расстояние изменения контекста

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

• Решатель: Gurobi 11.0.1
• Среда программирования: Python 3.11.7
• Вычислительная платформа: процессор Intel Core i9-10980XE
• Временное ограничение: 1 час
• Параметры регуляризации: λ ∈ {0, 0.1, 1}

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

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

1. Значительное повышение вычислительной эффективности:
   • При λ=0.1 среднее время решения значительно сокращается по сравнению с λ=0
   • Пример: при N=100, D=10, r=4 среднее время λ=0.1 составляет 137.92s против 266.49s при λ=0
2. Улучшение разреженности:
   • Регуляризация Вассерштейна повышает разреженность решений
   • При λ=0.1 разреженность обычно лучше, чем при λ=0
3. Оптимизационный зазор:
   • В экземплярах, достигших временного ограничения, нерегуляризованный случай показывает значительно больший оптимизационный зазор

Анализ конкретного примера

Результаты малого примера:

• Без регуляризации (λ=0): x_=0.350, W²₂=164.917
• С регуляризацией (λ=0.25): x_=0.479, W²₂=90.849
• Регуляризованная версия, хотя и имеет большее изменение контекста, показывает меньшее расстояние между распределениями при одинаковой разреженности

Экспериментальные выводы

1. Эффект регуляризации: умеренная регуляризация Вассерштейна не только улучшает время выполнения и разреженность, но и приводит к более плавному переходу распределения спроса
2. Вычислительная сложность: контрфактическая задача наследует сложность базовой фактической задачи; экземпляры с большим бюджетом r часто достигают временного ограничения
3. Механизм разреженности: разреженные изменения достигаются не только минимизацией ℓ₁-нормы; регуляризация также побуждает модель концентрировать изменения на меньшем числе объектов вместо распределения небольших изменений

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

Контрфактические объяснения для задач оптимизации

• Bogetoft et al. (2024): применение концепции к анализу охвата данных (DEA)
• Kurtz et al. (2025): контрфактические объяснения для линейного программирования, формализация слабых, сильных и относительных типов
• Серия работ Корикова: вычисление слабых контрфактических объяснений для целочисленного линейного программирования через обратную оптимизацию

Контекстные задачи оптимизации

• Forel et al. (2023): предположение, что параметры оцениваются из контекстных ковариат с использованием случайных лесов или k-NN в качестве предикторов
• Vivier-Ardisson et al. (2024): расширение на дифференцируемые классификаторы, включая нейронные сети

Отличие данной работы от связанных исследований

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

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

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

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

Ограничения

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

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

1. Слабые контрфактические объяснения: вычисление слабых контрфактических объяснений, которые принуждают новое решение быть оптимальным, вместо относительных объяснений
2. Расширение распределений: расширение на другие вероятностные распределения
3. Области применения: применение в задачах классификационной оптимизации и ценообразования
4. Гарантии единственности: включение целевых членов для обеспечения единственности решений

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

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

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

Недостатки

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

Влияние

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

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

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

Список литературы

Статья цитирует 63 связанные работы, охватывающие контрфактические объяснения, теорию оптимизации, задачи размещения объектов и другие важные области, обеспечивая прочную теоретическую базу для исследования.

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