2025-11-13T21:28:11.123642

Relative Explanations for Contextual Problems with Endogenous Uncertainty: An Application to Competitive Facility Location

Ramírez-Ayerbe, Frejinger
In this paper, we consider contextual stochastic optimization problems under endogenous uncertainty, where decisions affect the underlying distributions. To implement such decisions in practice, it is crucial to ensure that their outcomes are interpretable and trustworthy. To this end, we compute relative counterfactual explanations that provide practitioners with concrete changes in the contextual covariates required for a solution to satisfy specific constraints. Whereas relative explanations have been introduced in prior literature, to the best of our knowledge this is the first work focusing on problems with binary decision variables and endogenous uncertainty. We propose a methodology that uses the Wasserstein distance as a regularization term, which leads to a reduction in computation times compared to its unregularized counterpart. We illustrate the method using a choice-based competitive facility location problem and present numerical experiments that demonstrate its ability to efficiently compute sparse and interpretable explanations.
academic

内生不確実性を伴う文脈的問題に対する相対的説明：競争的施設立地への応用

基本情報

  • 論文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（数学最適化および制御）
  • 発表日: 2025年10月14日（arXivプレプリント第3版）
  • 論文リンク: https://arxiv.org/abs/2506.19155v3

要旨

本論文は、意思決定が基礎となる分布に影響を与える内生不確実性下の文脈的確率最適化問題を研究する。実践においてこのような意思決定を実施するためには、その結果の解釈可能性と信頼性を確保することが重要である。このため、著者らは相対的反事実説明を計算し、実務家に対して特定の制約を満たすソリューションを得るために必要な文脈的共変量の具体的な変化を提供する。相対的説明は先行文献で紹介されているが、著者らの知る限り、二値決定変数と内生不確実性を伴う問題に焦点を当てた最初の研究である。著者らは、Wasserstein距離を正則化項として使用する方法を提案し、正則化されていない対応する方法と比較して計算時間を削減する。

研究背景と動機

問題背景

機械学習と最適化の意思決定問題への応用が増加するにつれ、特に医療、住宅配分、社会サービスなどのハイリスク意思決定環境において、ソリューションの解釈可能性と信頼性を確保することが重要になっている。欧州連合、米国ホワイトハウス科学技術政策局、カナダ政府などの機関は、解釈可能性に対する増加するニーズを認識している。

核心的問題

  1. 内生不確実性：決定変数zが確率変数yの条件付き確率分布P(y|z,x)に影響を与える
  2. 解釈可能性の必要性：文脈的変化がいかに意思決定の変化をもたらすか、およびソリューションが特定の制約を満たすために必要な変化を理解する必要がある
  3. 実際の応用シナリオ：医療基盤計画において、地方自治体がデータの最小限の変化がその地域でセンターを開設する決定にどのように影響するかを問う場合など

既存方法の限界

  • 既存の反事実説明は主に監督分類問題に焦点を当てている
  • 二値決定変数と内生不確実性を伴う最適化問題に対する研究が不足している
  • 従来の方法は計算複雑性が高く、効果的な正則化メカニズムが不足している

核心的貢献

  1. 研究範囲の拡張：内生不確実性下の文脈的確率最適化問題に相対的反事実説明を初めて適用
  2. 既存方法の一般化：単一の目標ソリューションではなく期待可行集合Dを許可し、専門家提供ソリューションに基づく既存方法を一般化
  3. 二値変数の処理：二値決定変数設定における相対的説明問題に対応
  4. Wasserstein正則化：反事実および事実ソリューションが誘導する分布間の距離を最小化する正則化項を使用
  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

コスト関数とWasserstein正則化

コスト関数は以下の形式を採用する：

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

ここで：

  • J(x⁰,x)：非類似性成分
  • Ω(x⁰,x)：正則化項、2-Wasserstein距離を使用

Wasserstein距離の定義： 2つの離散確率分布P⁰とPに対して、2-Wasserstein距離の二乗は以下のように定義される：

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. 分布距離正則化：Wasserstein距離を使用して反事実分布と事実分布の近接性を確保
  2. モデル非依存下界：計算下界のモデル非依存方法を提供
  3. 疎性誘導：ℓ₁ノルムとWasserstein正則化の共同作用により疎解を実現

実験設定

応用シナリオ：選択ベース競争的施設立地問題(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個

評価指標

  • 計算時間：平均および中央値求解時間
  • Wasserstein距離：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.92秒 対 λ=0の266.49秒
  2. 疎性の改善：
    • Wasserstein正則化がソリューションの疎性を向上
    • λ=0.1時の疎性は通常λ=0の場合より優れている
  3. 最適化ギャップ：
    • 時間制限に達したインスタンスにおいて、正則化されていない場合の最適化ギャップが明らかに大きい

ケース分析

小規模例の結果：

  • 正則化なし(λ=0)：x_=0.350、W²₂=164.917
  • 正則化あり(λ=0.25)：x_=0.479、W²₂=90.849
  • 正則化版は文脈変化がより大きいが、分布距離がより小さく、疎性は同じ

実験的発見

  1. 正則化効果：適度なWasserstein正則化は実行時間と疎性を改善するだけでなく、需要分布のスムーズな遷移をもたらす
  2. 計算複雑性：反事実問題は基礎となる事実問題の複雑性を継承し、予算rが大きいインスタンスは頻繁に時間制限に達する
  3. 疎性メカニズム：疎な変化はℓ₁ノルムの最小化を通じてのみならず、正則化は変化を少数の施設に集中させ、小さな修正を分散させることを促進する

関連研究

最適化問題の反事実説明

  • Bogetoft et al. (2024)：データ包絡分析(DEA)への概念の応用
  • Kurtz et al. (2025)：線形計画の反事実説明、弱、強、相対の3つのタイプを形式化
  • Korikov系列の研究：逆最適化を通じた整数線形計画の弱反事実説明の計算

文脈的最適化問題

  • Forel et al. (2023)：パラメータが文脈共変量から推定されると仮定、ランダムフォレストまたはk-NNを予測器として使用
  • Vivier-Ardisson et al. (2024)：ニューラルネットワークを含む微分可能分類器への拡張

本論文と関連研究の相違

  1. 目標設定：専門家提供の単一目標ではなく期待可行集合Dを許可
  2. 不確実性のタイプ：内生不確実性に焦点
  3. 変数タイプ：二値決定変数を処理
  4. 正則化の革新：Wasserstein距離正則化を導入

結論と考察

主要な結論

  1. 方法の有効性：反事実説明を内生不確実性を伴う文脈的確率問題に正常に拡張
  2. 計算上の利点：Wasserstein正則化により計算効率が大幅に向上
  3. ソリューション品質：より疎で解釈可能な説明を取得し、選択確率の変化がより滑らか

限界

  1. 連続変数の制限：現在の定式化は文脈共変量が連続型であることを要求し、カテゴリカル共変量への拡張は依然として課題
  2. ソリューションの一意性：ソリューションは通常一意ではなく、利害関係者間の相違と説明の操作可能性につながる可能性
  3. 倫理的考慮：複数の有効な反事実説明は倫理的問題を引き起こす可能性があり、例えば機密の文脈特徴を隠す

今後の方向性

  1. 弱反事実：相対的反事実ではなく、新しいソリューションの最適性を強制する弱反事実の計算
  2. 分布拡張：他の確率分布への拡張
  3. 応用分野：分類最適化と価格設定などの文脈的問題への応用
  4. 一意性保証：ソリューションの一意性を確保する目的項の組み込み

深層的評価

利点

  1. 理論的貢献：内生不確実性問題への反事実説明の適用を初めて体系的に行い、理論的枠組みが完全
  2. 方法的革新：Wasserstein正則化の導入は理論的根拠があり実際的効果があり、計算性能を大幅に改善
  3. 実験の充実：小規模例から大規模インスタンスまでの包括的な実験、多次元の評価指標
  4. 実用的価値：選択されたCFLP応用は重要な実際的意義を持ち、結果は実行可能

不足

  1. 適用範囲の制限：連続文脈変数のみに適用可能で、方法の普遍性を制限
  2. 複雑性分析の不足：アルゴリズム複雑性の理論的分析が不足
  3. パラメータ選択：Wasserstein正則化パラメータλの選択に体系的なガイダンスが不足
  4. 比較実験：他の反事実説明方法との比較が不十分

影響力

  1. 学術的貢献：文脈的最適化の解釈可能性研究に新しい方向を開く
  2. 実用的価値：施設立地、資源配分などの実際の問題に解釈可能な意思決定支援を提供
  3. 再現性：完全なコードと例を提供し、再現と拡張を容易にする

適用シナリオ

  1. 施設計画：医療施設、学校、商業拠点の立地決定
  2. 資源配分：決定理由の説明が必要な公共資源配分問題
  3. 政策立案：透明性と解釈可能性が必要な政府意思決定プロセス
  4. 商業決定：競争環境における戦略的位置選択

参考文献

論文は反事実説明、最適化理論、施設立地問題など複数の分野の重要な研究を含む63の関連文献を引用し、研究に堅実な理論的基礎を提供する。

総合評価：これは理論的革新と実際の応用の間で良好なバランスを達成した高品質の学術論文である。Wasserstein正則化の導入は、理論的根拠があるだけでなく実際の計算上の利点をもたらすハイライトである。いくつかの限界があるにもかかわらず、文脈的最適化問題の解釈可能性研究に重要な貢献をしている。