기술 요약: 신경망 CO 정책의 제약-앵커링 귀속

문제 제기

조합 최적화 (CO) 를 위한 신경망 정책은 라우팅 및 스케줄링 문제 해결에 점점 더 효과적이지만, 그 의사결정 과정은 여전히 불투명합니다. 그라디언트 기반 특징 귀속 (예: 통합 그라디언트, DeepLIFT) 과 같은 표준 설명 가능한 AI(XAI) 방법은 특징 수준이 아닌 제약 수준에서 작동하기 때문에 CO 영역에서는 실패합니다. CO 문제는 용량, 시간 창, 우선순위 등 여러 계층의 다양한 특징 텐서에 걸쳐 있는 제약 조건들의 집합으로 정의되므로, 높은 계층의 특징 텐서들은 해당 의사결정을 주도하는 구속 제약 조건을 대표하지 않더라도 과도한 그라디언트 질량을 축적할 수 있어 정렬되지 않은 귀속을 초래합니다.

기존의 CO 전용 설명 도구들은 종종 문제의 실현 가능성을 위반하는 (예: 음수 수요 또는 역전된 시간 창) 제약이 없는 반사실적 예상에 의존하거나, 신경망 정책의 자기회귀 디코딩 과정이 아닌 정적 대리 모델을 대상으로 합니다. 제약 조건 계열별로 신경망 CO 의사결정을 분해하면서 형식적인 실현 가능성 보장을 제공하는 방법론은 부재합니다.

방법론: 제약-앵커링 귀속 (CAX)

본 논문은 신경망 설명을 근본적인 최적화 구조와 연결하는 세 가지 원시 요소로 구성된 CAX 프레임워크를 제안합니다.

1. $\Lambda$-귀속

이 방법은 개별 특징이 아닌 제약 조건 계열별로 정책의 의사결정 그라디언트를 분해합니다. $t$ 단계에서의 의사결정 $a_t$에 대해, 제약 조건 계열 $c_k$에 대한 귀속은 다음과 같이 계산됩니다:
$$\Lambda_k(t) = \lambda^*_k(x) \cdot \sum_{i \in F(c_k)} \sum_j |\nabla_{x^{(i)}_j} \log \pi_\theta(a_t | s_t) \cdot x^{(i)}_j|$$
여기서 $\lambda^*_k$는 문제의 선형 계획법 (LP) 완화에서 도출된 라그랑주 승수 (이중 값) 를 계열별로 집계한 것을 나타냅니다. 이 스케일링은 귀속이 제약 조건의 "구속 압력"을 반영하도록 보장합니다. 본 프레임워크는 $\lambda^*$를 추정하기 위해 세 가지 백엔드를 지원합니다.

• LP: LP 완화에서 도출된 이중 값.
• Subgrad: 완화된 부분 문제에 대한 라그랑주 서브그라디언트 상승법.
• Proxy: 균일 가중치 ($\lambda_k=1$), 이는 제약 조건이 분할된 그라디언트 $\times$ 특징과 동일합니다.

2. 보페로니-PAC 충분 부분집합

정책의 argmax 의사결정을 유지하는 데 필요한 최소 노드 집합을 결정하기 위해, 이 방법은 Koriche 등 의 CO 디코더 접근법을 적용합니다. 가우시안 교란 하에서 정책이 의사결정을 유지할 확률이 적어도 $1-\epsilon$이 되도록 하는 가장 작은 부분집합 $S$를 찾습니다.

• 탐욕 알고리즘이 귀속 순서를 탐색하여 경험적 유지율이 $1-\epsilon$을 초과하는 가장 작은 $k$를 찾습니다.
• 적응형 쿼리 (최대 $k_{max}$) 전반의 가족별 오류율을 통제하기 위해 호에딩 경계에 보페로니 보정이 적용됩니다. 이를 통해 탐욕 순서를 따라 $(1-\delta)$-PAC 경계를 보장하는 표본 크기 $M_{bonf}$가 도출됩니다.

3. CSP 인증 반사실적 예시 (CF)

교란 노름을 최소화하지만 실현 가능성 보장은 제공하지 않는 표준 Wachter 스타일의 반사실적 예시와 달리, CAX는 조합 최적화 실현 가능성 인증서를 부과합니다.

• 프로세스: 샘플러가 argmax 의사결정을 반전시키는 교란을 생성합니다. 후보들은 먼저 산술적 검사 (예: 필드 경계) 를 거칩니다.
• 인증: 최상의 후보는 제약 프로그래밍 (CP) 실현 가능성 - 의사결정 모델 (CP-SAT 를 통해 구현됨) 에 대해 검증됩니다.
• 판정 신호: CSP 인증 반전 교란에서 가장 큰 $L_1$ 질량을 지닌 계열은 정책의 국부적 민감도에 대한 기준 신호로 작용합니다. 이 신호는 교란 노름 ($L_1, L_2, L_\infty$) 및 차원 정규화에 불변입니다.

주요 기여

1. 제약 수준 분해: CAX는 LP 완화 이중 값을 사용하여 제약 조건 계열별로 신경망 CO 정책 의사결정을 분해하는 최초의 방법으로, 특징 수준 귀속에 내재된 잘못된 순위 문제를 수정합니다.
2. 실현 가능성 인증 반사실적 예시: CSP 실현 가능성 - 의사결정 모델을 통해 문제 제약 조건을 엄격히 준수하는 반사실적 예시 생성 과정을 도입하여, 제약이 없는 XAI 방법과 구별됩니다.
3. PAC 충분 부분집합: 신경망 CO 정책에 대한 충분 설명 부분집합의 크기에 대한 보페로니 보정 및 호에딩 제어 경계를 제공합니다.
4. 경험적 판정: 프레임워크는 CF 에서 도출된 신호를 사용하여 귀속 백엔드를 검증하며, 특징 계층과 구속 제약 조건이 정렬되지 않을 때 LP 이중 값이 귀속 정확도를 회복시킨다는 것을 입증합니다.

실험 결과

본 프레임워크는 용량 제한 차량 라우팅 문제 (CVRPTW), 오리엔티어링 문제 (OP), 유연한 작업장 스케줄링 문제 (FJSP) 라는 세 가지 다른 CO 문제에서 평가되었습니다.

• CF 신호와의 일치:
  • CVRPTW: LP-앵커링 $\Lambda$-귀속은 344 건 ($n_{cert}=344$) 중 **96.5%**의 사례에서 CF-도출 신호와 일치하여, 프록시 그라디언트 (75.0%) 를 크게 능가했습니다. 차이 (+0.215) 는 통계적으로 유의미했습니다 (McNemar $p \le 10^{-14}$).
  • OP: LP-앵커링 귀속은 **77.2%**의 일치율을 보인 반면 (281 건, $n_{cert}=281$), 프록시는 35.2%에 그쳤습니다 (차이 +0.420, $p \le 10^{-14}$).
  • FJSP: 고질량 텐서가 구속 계열과 일치하는 "계층 정렬" 영역에서, LP 및 프록시 백엔드 모두 59 건의 인증된 반전 모두에서 **100%**의 일치율을 달성하여, 계층이 정렬될 때 LP 이중 값이 추가 정보를 제공하지 않는다는 이론적 예측을 확인했습니다.
• 실현 가능성률: CSP 인증 반사실적 예시는 높은 실현 가능성을 유지했습니다. 산술적 필터링만으로도 승자 100% 가 통과된 반면, 매칭된 제약이 없는 기준선은 후보의 19.3% 만 통과했습니다.
• PAC 부분집합: CVRPTW 에서 보페로니 보정 PAC 부분집합은 단계당 평균 5.0 개의 노드였습니다 ($M=70, \epsilon=\delta=0.2$).

중요성 및 주장

본 논문은 CAX 가 신경망 CO 정책을 설명하기 위한 엄격하고 제약 기반의 접근법을 제공한다고 주장합니다. 그 주요 중요성은 LP 이중 값이 특징 텐서 계층이 구속 제약 조건 계열과 정렬되지 않을 때만 정확한 귀속에 필요하다는 것을 입증하는 데 있습니다. 정렬될 때는 더 간단한 방법으로 충분하지만, 정렬되지 않을 때는 특징 수준 방법이 실패하며 LP-앵커링 방법이 올바른 제약 수준 신호를 회복합니다.

이 프레임워크는 범위가 제한적입니다. 실현 가능성 모델 (여기서는 CSP 로 구현됨) 만 필요로 하며, 사후 분석 도구로 작동합니다. 전체 부분집합 격자 최적화 (정확한 PAC 최적 부분집합은 여전히 미해결 문제임) 를 해결한다고 주장하지는 않지만, 탐욕 순서를 통해 보수적이고 인증된 경계를 제공합니다. 이 연구는 휴리스틱 특징 중요도를 넘어 제약 기반 유효성으로 이동함으로써, CSP 인증 반사실적 예시를 판정 신호로 사용하여 CO 에서의 XAI 평가에 대한 새로운 벤치마크를 확립합니다.