기술 요약: 이진 공간에서의 안전한 최적화를 위한 적응형 확률적 자연 경사법

1. 문제 정의

본 논문은 이진 검색 공간 ($\{0, 1\}^d$) 내의 안전한 최적화 과제를 다룹니다. 의료용 약물 조합 최적화 및 엔지니어링 제어 일정 조정과 같은 실제 응용 분야에서 후보 솔루션 평가는 잠재적 위험 (예: 독성 또는 기계 고장) 을 수반할 수 있습니다. 안전한 최적화는 "안전하지 않은" 솔루션의 평가를 엄격히 피하면서 목적 함수 $f(\mathbf{x})$ 를 최대화하는 것을 목표로 합니다.

이 문제는 다음과 같은 제약 최적화 작업으로 공식화됩니다:
$$\max_{\mathbf{x} \in \{0, 1\}^d} f(\mathbf{x}) \quad \text{s.t.} \quad s_j(\mathbf{x}) \geq 0, \quad \forall j = 1, \dots, p$$
여기서 $s_j$ 는 안전 함수입니다. 모든 제약을 만족하는 솔루션은 "안전"하며, 그렇지 않으면 "안전하지 않은" 것으로 간주됩니다. 최적화 과정은 $N_{seed}$ 개의 알려진 안전한 솔루션인 "안전 시드 (safe seeds)" 집합으로 초기화됩니다. 목표는 $s_j(\mathbf{x}) < 0$ 인 솔루션의 평가를 억제하면서 $f$ 를 최적화하는 것입니다.

연속 공간에서는 안전한 최적화 방법 (예: Safe CMA-ES) 이 존재하지만, 이진 공간을 위한 효과적인 방법 개발은 미흡한 실정입니다. "위반 회피 (violation avoidance)" (안전한 이웃이 발견될 때까지 생성을 재시도하는 것) 와 같은 기존 일반적 전략은 이진 영역에서 안전하지 않은 평가를 효율적으로 억제하는 데 종종 실패합니다.

2. 방법론: Safe ASNG

저자들은 이진 최적화를 위해 베르누이 분포 계열을 사용하는 ASNG 방법의 확장인 Safe ASNG(Safe Adaptive Stochastic Natural Gradient) 를 제안합니다. 핵심 메커니즘은 안전 영역을 구성하고 생성된 솔루션을 해당 영역으로 투영하는 것입니다.

2.1 대리 모델링 및 리프시츠 추정

안전 영역을 정의하기 위해 Safe ASNG 는 해밍 거리에 대한 안전 함수의 리프시츠 상수를 추정합니다.

• 대리 모델: 계산 비용이 많이 들고 ($O(N^3)$) 이진 공간에서 정확도가 낮은 가우시안 프로세스 (GP) 회귀 대신, Safe ASNG 는 **이산 왈시 함수 (discrete Walsh functions)**를 사용하여 대리 모델 $\hat{s}_j$ 를 구성합니다. 이 접근법은 계산 효율적이며 의사-부울 함수에 대해 더 정확한 근사치를 제공합니다.
• 리프시츠 상수 추정 ($\hat{L}_j$): 이 방법은 현재 분포에서 샘플을 생성하고, 대리 모델을 사용하여 그들의 이웃 (해밍 거리 = 1) 을 평가한 후, 안전 값의 최대 차이를 리프시츠 상수로 추정합니다.
• 과대 추정 처리: 안전을 보장하기 위해 훈련 데이터셋이 작을 때 리프시츠 상수를 과대 추정합니다. 또한, 2 차 아카이브에서 관찰된 최대 안전 값에 기반하여 리프시츠 상수를 제한하는 보정 메커니즘 (식 16) 을 통해 안전 영역이 퇴화 (아무것도 남지 않을 정도로 축소) 하는 것을 방지합니다.

2.2 안전 영역 계산

안전 영역 $\mathcal{X}_{safe}$ 는 이전에 평가된 안전한 솔루션 주변의 이웃들의 합집합으로 정의됩니다. 안전한 솔루션 $\mathbf{x}_{safe}$ 에 대해, 해밍 거리가 $s_j(\mathbf{x}_{safe}) / \hat{L}_j$ 이내인 모든 솔루션 $\mathbf{x}$ 는 안전이 보장됩니다.
$$\mathcal{X}_{safe} = \bigcup_{\mathbf{x}_{safe} \in \mathcal{D}} \left\{ \mathbf{x} \in \{0, 1\}^d \mid \text{dist}(\mathbf{x}, \mathbf{x}_{safe}) \leq \min_j \frac{s_j(\mathbf{x}_{safe})}{\hat{L}_j} \right\}$$
여기서 $\mathcal{D}$ 는 최근 안전한 솔루션들의 아카이브입니다.

2.3 투영 및 제약 처리

• 확률 기반 투영: 베르누이 분포에서 생성된 솔루션 $\mathbf{x}$ 가 $\mathcal{X}_{safe}$ 바깥에 떨어질 경우, 이를 가장 가까운 안전한 솔루션으로 투영합니다. 여러 개의 가장 가까운 이웃이 존재할 경우, 현재 분포 하에서 최대 확률을 갖는 것을 선택합니다. 투영으로 인해 중복 샘플 (정체 유발) 이 발생할 경우, 다양성을 보장하기 위해 차순위 비트를 반전시킵니다.
• 순위 기반 제약 처리: 2 차 안전 조치로서, 이 방법은 솔루션 순위를 매기기 위한 선호 관계를 사용합니다. 안전한 솔루션은 항상 안전하지 않은 솔루션보다 우선합니다. 안전하지 않은 솔루션 중에서는 제약 위반이 작은 것이 선호됩니다. 이는 몇몇 안전하지 않은 평가가 발생하더라도 자연 경사 업데이트를 안내합니다.
• 초기화: 분포 매개변수는 제공된 안전 시드의 평균을 사용하여 초기화됩니다.

3. 주요 기여

1. 이진 공간을 위한 최초의 안전한 최적화: 본 논문은 연속 공간 방법인 Safe CMA-ES 가 남긴 공백을 메우는 이진 검색 공간을 위한 최초의 전용 안전한 최적화 방법을 소개합니다.
2. 이산 왈시 대리 모델: 저자들은 효율적인 안전 함수 대리 모델을 구축하기 위해 이산 왈시 함수를 적용하여, GP 의 높은 계산 비용 없이 빠른 리프시츠 상수 추정을 가능하게 했습니다.
3. 투영 메커니즘: 새로운 투영 전략은 베르누이 분포 샘플을 가장 가까운 안전 영역으로 매핑하면서 확률 분포의 확률을 보존하여, 알고리즘이 갇히거나 안전하지 않은 점을 평가하는 것을 방지합니다.
4. 제약 처리 통합: 순위 기반 제약 처리 메커니즘의 통합은 대리 모델이 불완전할 때에도 견고성을 보장합니다.

4. 실험 결과

이 방법은 OneMax, LeadingOnes, BinVal, Reversed BinVal 과 같은 표준 이진 벤치마크에서 두 가지 설정 하에 평가되었습니다:

• 호환 설정: 목적 함수를 개선하는 것이 자연스럽게 더 안전한 솔루션으로 이어지는 경우.
• 충돌 설정: 목적 함수를 개선하는 것이 검색을 안전하지 않은 영역으로 이동시키는 경우.

결과:

• 안전하지 않은 평가 억제: 거의 모든 설정에서 Safe ASNG 는 안전하지 않은 솔루션 평가를 성공적으로 억제했습니다 (종종 안전하지 않은 평가가 0 에 도달함). 반면, 비교 방법 (위반 회피가 적용된 ASNG 및 제약 처리가 적용된 ASNG) 은 안전하지 않은 솔루션을 자주 평가했으며, 안전하지 않은 평가 예산을 초과하여 조기 종료되는 경우가 많았습니다.
• 최적화 효율성: Safe ASNG 는 비교 방법이 실패한 곳에서 최적의 안전한 솔루션을 찾아 효율적인 최적화를 달성했습니다.
• 초기 매개변수 민감도: 연구는 영역을 정의하는 데 사용된 안전 솔루션의 수 ($N_{safe}$) 가 중요함을 보여주었습니다. $N_{safe} = 10 \times d$ 설정은 잘 수행되었으나, $N_{safe} = 10 \times d^2$ 설정은 리프시츠 상수의 과대 추정과 정체로 이어졌습니다.

5. 중요성 및 주장

본 논문은 Safe ASNG 가 이전에 부재했던 이진 영역에서의 효율적인 안전한 최적화를 가능하게 함으로써 중요한 진전이라고 주장합니다. 저자들은 이진 공간에서 비교 방법이 안전하지 않은 평가를 억제하지 못하는 반면, Safe ASNG 는 최적화 진행과 안전 제약 사이의 효과적인 균형을 유지한다고 강조합니다.

그 중요성은 다음과 같습니다:

• 약물 조합, 일정 조정과 같은 고위험 이진 최적화 문제에 대한 실용적인 솔루션 제공.
• 계산 효율성과 정확성으로 인해 이 특정 맥락에서 GP 보다 이산 왈시 함수가 대리 모델링에 우월함을 입증.
• 향후 작업에서 정수, 범주형 등 다른 이산 변수 최적화 문제로 확장될 수 있는 프레임워크 확립.

저자들은 이 방법이 효과적이지만, LeadingOnes 와 같은 특정 어려운 함수에 대한 성능을 개선하고 초기 매개변수 민감도를 정교화하기 위해 추가 연구가 필요하다고 겸손하게 언급합니다.