기술 요약: 정규화된 대규모 이웃 탐색 (Regularized Large Neighborhood Search, RLNS)

문제 정의

조합 최적화 레이어를 신경망에 통합하는 것은 구조적 예측(structured prediction)을 위한 강력한 패러다임으로 부상하였으며, 이를 통해 모델이 복잡한 제약 조건을 만족하는 이산적 결정을 출력할 수 있게 한다. 표준적인 정형은 $\hat{y}(\theta) \triangleq \arg \max_{y \in \mathcal{Y}} \langle \theta, y \rangle$로 정의되는 레이어를 포함하며, 여기서 $\mathcal{Y}$는 유한하지만 조합론적으로 매우 큰 가능한 출력 집합이다.

이 설정의 근본적인 과제는 미분 가능성이다. $\arg \max$ 연산자는 거의 모든 곳에서 그래디언트가 0이 되기 때문에, 기존 방식들은 일반적으로 연속적이고 미분 가능한 완화(relaxation)를 생성하기 위해 정규화에 의존한다. 그러나 대부분의 현재 방법론(예: Fenchel-Young 손실, 섭동된 최적화 도구)은 깁스 분포(Gibbs distribution)의 기댓값을 계산하기 위해 전역 정확한 솔버(global exact solver, 전역 MAP 오라클) 또는 마진 오라클(marginal oracle)에 대한 접근을 근본적으로 가정한다. 운영 연구(operations research)에서 흔히 볼 수 있는 NP-hard 최적화 문제의 경우, 매 훈련 단계마다 전역 오라클을 호출하는 것은 계산적으로 불가능하다. 결과적으로 실무자들은 변수의 일부를 고정하고 나머지를 재최적화함으로써 해를 반복적으로 개선하는 **대규모 이웃 탐색(Large Neighborhood Search, LNS)**과 같은 확장 가능한 휴리스틱에 의존한다. LNS를 미분 가능한 조합 레이어로 사용하기 위한 원칙적인 프레임워크의 부재는 중요한 병목 현상으로 남아 있다.

방법론: 정규화된 LNS (RLNS)

저자들은 LNS의 확률적 버전으로서, 확장 가능한 휴리스틱과 미분 가능한 최적화 레이어 사이의 간극을 메우는 **정규화된 대규모 이웃 탐색(Regularized Large Neighborhood Search, RLNS)**을 소개한다. 핵심 아이디어는 LNS 프레임워크 내의 국소적 하위 문제(local subproblems)를 정규화하거나 섭동(perturbation)시켜, 이 휴리스틱을 조합 가능한 해 집합에 대한 효율적인 마르코프 체인 몬테카를로(MCMC) 샘플러로 변환하는 것이다.

1. 프레임워크 및 국소 정규화

RLNS는 전역 정규화 함수 $\Omega$로부터 유도된 국소 정규화 함수 패밀리를 정의한다. 해의 부분 집합 $\mathcal{Z} \subseteq \mathcal{Y}$에 대하여, 국소 정규화 함수 $\Omega_{\mathcal{Z}}$는 포함 사상(inclusion map)을 통해 정의된다. 전역 정규화 문제를 직접 푸는 대신, RLNS는 고정된 좌표의 부분 집합 $S^{(k)}$에 의해 정의된 국소 이웃 $\mathcal{Y}(k)$에 대해 국소적으로 정규화된 분포 $p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)])$로부터 반복적으로 샘플링한다.

2. 엔트로피 정규화 및 블록 깁스 샘플링

전역 정규화가 샤논의 음의 엔트로피($\Omega = -\gamma H_s$)일 때, 저자들은 RLNS가 **정확한 블록 깁스 샘플링(exact block Gibbs sampling)**을 수행함을 증명한다. 구체적으로, 국소적으로 정규화된 분포는 고정된 변수들에 대해 조건화된 전역 정규화 깁스 분포와 일치한다:
$$p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)](y) = p_{\Omega}(s_\theta)(y \mid y^{(k)}_{[S^{(k)}]})$$
기약 변수 선택 스킴(irreducible variable selection scheme) 하에서, RLNS 반복의 정상 분포(stationary distribution)는 전역적으로 정규화된 깁스 분포로 정확하게 수렴한다. 이 결과는 엔트로피 정규화에 고유한 특성이다. 명제 2는 샤논의 엔트로피가 이러한 정확성을 보장하는 유일한 분리 가능한(separable) 정규화임을 규명한다.

3. 섭동 기반 정규화

국소 마진 오라클(엔트로피 샘플링에 필요)은 다루기 어렵지만 국소 MAP 오라클은 사용 가능한 시나리오를 위해, 저자들은 **섭동 기반 정규화(perturbation-based regularization)**를 제안한다. 국소 점수(scores)에 노이즈 $\epsilon Z$를 더하고 섭동된 국소 최대화 문제를 해결함으로써, RLNS는 국소 정규화 분포으로부터 샘플링할 수 있다. 이 접근법은 Metropolis-Hastings 기반의 국소 탐색과 달리, 샘플 거부 메커니즘 없이 표준 LNS 오라클(예: 배낭 문제(knapsack subproblems)를 위한 동적 계획법)을 활용할 수 있게 한다.

4. 학습 및 보간(Interpolation)

본 논문은 RLNS 반복 횟수($K$)와 학습 목적 함수 사이의 관계를 확립한다:

• $K=1$ (국소 Fenchel-Young 손실): 단일 단계의 RLNS는 국소 Fenchel-Young 손실에 대한 불편 추정량(unbiased estimator)을 제공한다. 엔트로피 설정에서 이는 의사 우도(pseudolikelihood)(합성 가능도, composite likelihood) 목적 함수를 회복하며, 이는 나머지 변수들에 조건화된 변수들의 부분 집합에 대한 가능도를 최대화한다.
• $K \to \infty$ (전역 Fenchel-Young 손실): 반복 횟수가 증가함에 따라, 추정량은 전역 Fenchel-Young 손실의 그래디언트로 수렴하며, 이는 정확한 최대 가능도 추정(maximum likelihood estimation)을 근사한다.
  이를 통해 실무자들은 $K$를 조정함으로써 의사 우도와 정확한 최대 가능도 추정 사이를 보간할 수 있으며, 전역 솔버 없이도 엔드 투 엔드 학습을 가능하게 한다.

주요 기여

1. RLNS 프레임워크: 국소 정규화를 LNS 하위 문제에 통합하여 미분 가능한 조합 레이어를 생성하는, 정규화된 확률적 버전의 LNS를 도입하였다.
2. 이론적 등가성: 엔트로피 정규화 하에서 RLNS가 전역 정규화 깁스 분포와 일치하는 정상 분포를 갖는 정확한 블록 깁스 샘플러를 구현함을 증명하였다.
3. 섭동을 통한 트랙터빌리티(Tractability): 섭동 기반 정규화가 RLNS가 표준 국소 MAP 오라클을 사용할 수 있게 함을 보여줌으로써, 표준 LNS가 실행 가능한 경우 언제든 계산 가능한 경로를 확보하였다.
4. 학습 패러다임의 보간: RLNS 반복 횟수를 통해 의사 우도와 정확한 최대 가능도 추정 사이의 보간이 가능하다는 것을 이론적, 경험적으로 입증하였다.
5. 경험적 검증: 다음 세 가지 문제에 대해 평가를 수행하였다:
   • $\kappa$-hot 벡터: 지면 진실(ground truth)에 대한 수렴성을 검증하는 제어된 추정 작업.
   • 일반화된 할당 문제 (GAP): 국소 하위 문제가 0/1 배낭 문제인 할당 예측 학습.
   • 확률적 차량 스케줄링: RLNS-1이 블랙박스 미분 및 이진 교차 엔트로피(BCE) 베이스라인보다 우수하면서도, 전역 솔버보다 훨씬 적은 계산량을 요구하는 실제 벤치마크.

결과

• 수렴성: $\kappa$-hot 벡터 실험에서, RLNS는 로컬 서치 MCMC보다 빠르게 수렴하며, 동일한 샘플 수에 대해 몬테카를로 추정보다 낮은 평균 절대 오차(MAE)를 달성한다. 특히 많은 비율의 변수가 자유 상태(free)로 유지될 때 더욱 그러하다.
• 확장성: GAP 실험에서, RLNS가 사용하는 국소 MAP 오라클은 문제 규모가 커질수록 전역 혼합 정수 선형 계획법(MILP) 솔버보다 수 차례 더 빠르다.
• 성능: 확률적 차량 스케줄링에서, RLNS-1(단일 반복 사용)은 지연 비용 측면에서 전역 섭동된 Fenchel-Young(PFY) 학습과 거의 대등한 성능을 보이면서도, 원래 크기의 약 1/3 정도의 하위 문제만을 처리하면 된다. 또한 블랙박스 미분(DBB) 및 이진 교차 엔트로피(BCE) 베이스라인을 크게 상회한다.
• 편향 분석: 이론적 경계값은 고정된 변수와 자유 변수 사이의 공유 제약 조건(cut constraints) 수에 따라 근사 오차가 어떻게 스케일링되는지 보여주며, 이는 변수 선택 스킴(예: min-cut selection)이 이러한 상호 의존성을 최소화해야 함을 시사한다.

의의 및 주장

본 논문은 고도로 확장 가능한 휴리스틱(LNS)을 미분 가능한 레이어로 사용하여, 계산적으로 불가능한 전역 솔버에 대한 의존성을 제거함으로써 기존 문헌의 중요한 간극을 메운다고 주장한다. LNS와 깁스 샘플링 사이의 엄격한 연결을 구축함으로써, 본 연구는 국소 오라클만을 사용하여 조합 최적화 레이를 미분할 수 있는 원칙적인 프레임워크를 제공한다. 저자들은 RLNS를 NP-hard 제약이 포함된 구조적 예측 작업에서 엔드 투 엔드 학습을 위한 실용적인 솔루션으로 제시하며, 반복 횟수 $K$를 통해 계산 비용과 통계적 정확도 사이의 조절 가능한 트레이드오프를 제공한다.