Learning to Assess the Reliability of Number-of-Runs Estimation in Stochastic Optimization

기술적 요약: 확률적 최적화에서 실행 횟수 추정의 신뢰성 평가 학습

문제 제기
확률적 최적화 알고리즘의 대규모 벤치마킹은 실험적 신뢰성과 계산 효율성 간의 근본적인 긴장 관계에 직면해 있습니다. 유효한 성능 평가를 위해서는 반복 실행이 필수적이지만, 알고리즘 포트폴리오의 규모와 문제 차원이 커질수록 광범위한 반복의 비용은 급격히 증가합니다. 현재의 관행은 실행 횟수를 15, 25, 또는 50 회로 고정하는 것과 같은 정적 설계 선택에 의존하는데, 이는 문제 전반에 걸쳐 알고리즘 행동이 균일하다는 것을 암묵적으로 가정합니다. 그러나 이러한 가정은 경험적 증거에 의해 거의 지지되지 않습니다.

최근 연구는 성능 안정성과 분포의 대칭성을 모니터링함으로써 인스턴스별 필요한 실행 횟수를 적응적으로 추정하는 경험적 온라인 휴리스틱을 도입했습니다. 이 방법은 총 실행 횟수를 약 50% 줄여 효율성을 개선하지만, 결정적인 한계를 지닙니다. 일부 경우 (5~25% 편차) 에서 추정된 실행 횟수가 부정확하다는 것입니다. 이러한 부정확성은 모든 실행이 완료된 후에만 사후적으로 감지될 수 있으므로, 실시간 의사결정이 필요한 완전한 온라인 벤치마킹 시나리오에는 적합하지 않습니다.

방법론
본 연구는 기존 경험적 온라인 휴리스틱을 학습 기반 확장으로 제안하여, 실행 횟수 추정의 부정확성을 조기에 감지할 수 있는 자기 평가 시스템을 구축합니다.

• 데이터 소스 및 주석: 본 연구는 20 차원 (COCO 벤치마크 스위트) 의 24 개 문제 클래스에 걸쳐 Nevergrad 프레임워크의 11 개 최적화 알고리즘으로 수행된 132,000 회 실행에서 파생된 데이터 세트를 활용합니다. ground truth 라벨 (신뢰할 수 있는 대 신뢰할 수 없는 추정) 은 3 가지 이상치 탐지 방법 (IQR, 백분위수 트리밍, 수정된 z-점수) 과 4 가지 왜도 임계값 (0.05, 0.10, 0.15, 0.20) 을 사용한 원래 적응적 중단 실험의 사후 분석을 통해 확립되었습니다.
• 특징 추출: 지도 학습을 가능하게 하기 위해 가변 길이의 목적 함수 값 시퀀스를 고정 차원의 특징 벡터로 변환합니다. 총 23 개의 특징이 추출되며, 다음과 같이 분류됩니다:
  • 통계적: 평균, 중앙값, 표준 편차, 분산, 사분위수, 사분위 범위, MAD, 변동 계수.
  • 분포적: 왜도, 첨도, 엔트로피.
  • 에너지 관련: 합, 절대값의 합, 신호 에너지, 제곱평균제곱근.
  • 형태 및 안정성: 성능 개선의 기울기, 이동 표준 편차, FFT 에너지, 자기상관.
• 학습 작업: 문제는 실행 횟수 추정이 올바른지 (1) 아니면 잘못된지 (0) 를 예측하는 이진 분류 작업으로 공식화됩니다.
  • 클래스 불균형: 데이터 세트는 강한 클래스 불균형을 보입니다. 본 연구는 조기 중단을 피하기 위해 잘못된 추정 (소수 클래스) 의 탐지를 우선시합니다.
  • 모델 선택: 트리 기반 및 앙상블 모델 (의사결정나무, 랜덤 포레스트, XGBoost, LightGBM, CatBoost) 에 대해 Optuna 를 사용하여 하이퍼파라미터 최적화를 수행합니다. 목적 함수는 정확도나 F1 점수가 아닌 Recall0(소수 클래스의 재현율) 을 최대화하도록 설정되는데, 이는 위음성 (신뢰할 수 없는 추정을 신뢰할 수 있는 것으로 예측) 이 위양성보다 더 해롭기 때문입니다.
  • 실험 설정: "구성 내 (within-configuration)" 학습 설정이 사용됩니다. 모델은 동일한 최적화기, 이상치 탐지 방법, 그리고 왜도 임계값을 공유하는 데이터로 훈련되고 테스트됩니다. 이로 인해 132 개의 고유한 데이터 세트 (3 가지 방법 × 4 가지 임계값 × 11 개 알고리즘) 가 생성됩니다.

주요 기여

1. 적응적 중단 재정의: 본 논문은 단순히 실행 횟수를 추정하는 것에서 벗어나, 실시간으로 그 추정의 신뢰성을 평가하는 데 초점을 옮깁니다.
2. 최적화 역학을 위한 특징 공학: 최적화 궤적에서 파생된 23 개의 통계적, 에너지 무관, 형태/안정성 특징 집합을 도입하여 수렴 행동을 특성화합니다.
3. 불균형 분류 전략: 벤치마킹 컨텍스트에서 불균형 데이터를 처리하는 구체적인 접근 방식을 제시합니다. 여기서 신뢰할 수 없는 추정을 놓치는 것 (위음성) 의 비용은 불필요한 실행 (위양성) 의 비용보다 더 큽니다.

결과
고정된 구성 내에서 신뢰성을 학습하는 데 있어 상당한 도전과 특정 성공이 드러났습니다:

• 제한된 일반화 가능성: 유효한 분류기 ($F1_1 > 0.70$ 및 $Recall_0 > 0.80$ 충족) 는 132 개 구성 중 단 48.5% (64/132) 에서만 얻어졌습니다. 이는 단일 최적화기와 고정된 실험 매개변수로 제한될 때 신뢰할 수 있는 모델을 학습하는 것이 얼마나 어려운지를 보여줍니다.
• 알고리즘 변동성: 예측 가능성은 알고리즘에 따라 크게 달라졌습니다. Differential Evolution (DE), Diagonal CMA, NGOpt14, NGOpt38 은 가장 높은 성공률 (유효 구성 66.7%) 을 보인 반면, NaiveIsoEMNA 는 예측이 가장 어려웠습니다 (유효 구성 8.3%).
• 기준선과의 트레이드오프: 다수 클래스 기준선 (모든 인스턴스를 신뢰할 수 있는 것으로 예측) 과 비교했을 때, 훈련된 분류기는 $F1_1$ 측면에서 종종 성능이 저하되었습니다 (데이터 세트의 6.8% 만 기준선을 상회). 그러나 기준선은 $Recall_0$이 0.00 이어서 신뢰할 수 없는 추정을 전혀 식별하지 못했습니다. 반면, 훈련된 분류기는 일관되게 0.80 이상의 $Recall_0$ 값을 달성하여 기준선이 놓친 문제적인 수렴 사례를 성공적으로 식별했습니다.

의의 및 주장
본 논문은 구성 내 시나리오에서 실행 횟수 신뢰성을 학습할 수 있으며, 높은 소수 클래스 재현율로 신뢰할 수 없는 추정을 감지할 수 있다고 주장합니다. 이 능력은 적응적 휴리스틱을 실시간 실험 결정을 지원하면서도 적응적 실행 추정의 효율성 이점을 유지하는 시스템으로 변환시킵니다.

그러나 저자들은 이러한 발견의 범위에 대해 겸손한 태도를 보입니다. 그들은 성능이 "고정된 구성 내 제한된 데이터 다양성에 의해 제한된다"고 명시적으로 언급합니다. 구성당 240 개의 인스턴스만으로는 모델이 다수 클래스 예측을 넘어 학습하는 데 어려움을 겪습니다. 본 연구는 신뢰성 예측이 가능하지만 데이터가 제한된 환경에서는 여전히 어렵다고 결론지으며, 향후 연구는 훈련 다양성을 높이기 위해 서로 다른 최적화 알고리즘의 데이터를 결합한 시나리오를 탐구해야 한다고 제안합니다.