SCORE: Statistical Certification of Regions of Attraction via Extreme Value Theory

1. 문제 정의 (Problem Statement)

• 배경: 고차원 비선형 동역학 시스템의 안정성을 보장하기 위해 '영역의 안정성 (Region of Attraction, ROA)'을 인증하는 것은 안전 임계 시스템 (Safety-critical systems) 에 필수적입니다.
• 현황 및 한계: 기존에 널리 사용되던 결정론적 검증 방법들 (Sum-of-Squares (SOS) 프로그래밍, Satisfiability Modulo Theories (SMT) 등) 은 엄격한 보장을 제공하지만, 차원의 저주 (Curse of Dimensionality) 에 시달립니다.
  • SOS 는 다항식의 차수가 높아질수록 행렬의 조합적 폭발 (Combinatorial matrix explosion) 로 인해 20 차원 이상에서 확장성이 떨어집니다.
  • SMT 솔버는 밀집된 (Dense) 표현 (예: 신경망 기반 Lyapunov 함수) 을 검증할 때 NP-hard 문제와 마주치며 확장성이 제한됩니다.
• 목표: 고차원 (예: 500 차원) 이자 밀집된 비선형 시스템에 대해 ROA 를 효율적으로 인증할 수 있는 새로운 프레임워크 개발.

2. 제안 방법론: SCORE 프레임워크

저자들은 결정론적 '완전 보장' 대신, **통계적 신뢰도 하에서 최악의 안전 위반 (Worst-case safety violation) 을 경계 (Bounding)**하는 접근법을 제안합니다. 핵심은 **극단값 이론 (Extreme Value Theory, EVT)**과 **투사 확률적 경사 랑게빈 동역학 (Projected Stochastic Gradient Langevin Dynamics, PSGLD)**을 결합한 것입니다.

A. 핵심 아이디어

1. 문제 재정의: ROA 인증 문제를 Lyapunov 함수 $V(x)$의 하위 레벨 집합 경계 (Manifold, $M$) 에서 Lyapunov 미분 $\dot{V}(x)$의 최대값을 찾는 문제로 환원합니다. ($\gamma^* = \max_{x \in M} \dot{V}(x)$). 만약 $\gamma^* < 0$이면 인증 완료.
2. 확률적 탐색 (PSGLD): 고차원 비볼록 공간에서 전역 최대값을 찾기 위해, 제약 매니폴드 위에서 PSGLD 를 사용하여 $\dot{V}(x)$의 국소 최대값들을 샘플링합니다.
3. 극단값 이론 (EVT) 적용:
   • 샘플링된 국소 최대값들의 분포가 Weibull 분포의 최대 영역 (Maximum Domain of Attraction) 에 속함을 이론적으로 증명합니다.
   • 이론적 근거: 매니폴드 위의 확률적 확산 과정은 국소적으로 2 차 (이차곡면) 기하학을 가지며, 이는 최적성 간격 (Optimality gap) 이 $\chi^2$ 분포를 따르게 만듭니다. 이로 인해 $\dot{V}(x)$의 꼬리 분포는 유한한 우측 끝점 (Finite right endpoint) 을 갖는 Weibull 분포로 모델링됩니다.
4. 통계적 상한 추정:
   • 블록 최대값 (Block Maxima) 방식을 사용하여 샘플 데이터를 블록으로 나누고 각 블록의 최댓값을 추출합니다.
   • 추출된 최댓값들을 Generalized Extreme Value (GEV) 분포에 피팅하여 Lyapunov 미분의 전역 최댓값에 대한 **통계적 상한 (Statistical Upper Bound)**을 계산합니다.
   • 부트스트래핑 (Bootstrapping) 을 통해 신뢰 구간 (Confidence Interval) 을 설정하고, 상한이 0 미만인지 확인하여 ROA 를 인증합니다.

B. 알고리즘 흐름

1. 샘플링: PSGLD 를 통해 매니폴드 $M$ 위에서 $\dot{V}(x)$ 값을 샘플링.
2. 블록 최대값 추출: 샘플을 $N$개의 블록으로 나누어 각 블록의 최댓값만 추출.
3. GEV 피팅: 추출된 최댓값들에 대해 최대우도추정 (MLE) 을 통해 GEV 분포 파라미터 (형상, 위치, 척도) 추정.
4. 인증 결정:
   • 형상 파라미터 $\hat{\xi} < 0$ (Weibull 영역) 인지 확인.
   • 추정된 상한 ($z^*$) 에 대한 신뢰 구간 상한 ($CI_{upper}$) 이 0 미만인지 확인.
   • 적합도 검정 (KS test) 통과 확인.
   • 모든 조건 만족 시 '인증됨 (Certified)' 판정.

3. 주요 기여 (Key Contributions)

1. 새로운 통계적 인증 프레임워크: 결정론적 방법의 병목 현상을 우회하기 위해 EVT 와 PSGLD 를 통합하여, ROA 인증을 '제약된 극단값 추정 문제'로 재정의했습니다.
2. 유계성 (Boundedness) 의 이론적 보장: 확률적 확산 과정이 컴팩트 매니폴드 위에서 수행될 때, Lyapunov 미분의 국소 최대값이 Weibull 영역에 속함을 증명하여, 유한한 통계적 상한을 유도할 수 있음을 이론적으로 입증했습니다.
3. 비약적인 확장성 (Scalability): 기존 방법들이 20 차원에서 한계에 부딪히는 반면, 제안된 방법은 500 차원의 밀집된 비선형 ODE 시스템에서도 99.99% 신뢰도로 성공적으로 ROA 를 인증했습니다.

4. 실험 결과 (Numerical Experiments)

• 2D Van der Pol 발진기 (정밀도 검증):
  • 기존 SOS (Sum-of-Squares) 방법과 비교하여, 제안된 방법 (EVT + SOS 기반 후보 함수) 은 95% 의 상태 공간 중 83% 를 인증하여 결정론적 방법과 매우 근접한 엄격함 (Tightness) 을 보였습니다.
  • 이는 통계적 바운딩이 이론적으로 타당하며 보수적이지 않음을 입증했습니다.
• 고차원 확장성 (Scalability):
  • 실험 환경: 10 분 타임아웃 내에서 다양한 방법론 비교.
  • 결과:
    • SOS, SMT 기반 신경망 (NLF, ICNN, PINN) 방법들은 220 차원에서 모두 실패하거나 매우 낮은 차원 (N=210) 에서만 작동했습니다.
    • 제안된 방법 (Dict-Gram + EVT): N=500 차원의 밀집된 시스템에서 성공적으로 ROA 를 인증했습니다.
  • 원인: 제안된 방법은 전역적인 대수적/논리적 제약 해결이 아닌, 국소적 기울기 평가에 기반한 확률적 탐색을 사용하므로 조합적 복잡성 (Combinatorial complexity) 의 영향을 받지 않습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 패러다임 전환: "완벽한 결정론적 증명"에서 "높은 통계적 신뢰도를 가진 위험 경계 설정"으로 ROA 인증의 패러다임을 전환했습니다.
• 실용적 가치: 고차원, 밀집된, 구조화되지 않은 (Unstructured) 시스템 (예: 복잡한 제어 시스템, PDE 이산화 시스템 등) 에 대한 안전성 검증을 가능하게 하여, 기존 형식 검증 (Formal Verification) 파이프라인의 확장성 한계를 극복했습니다.
• 향후 과제: Lyapunov 후보 함수 자체의 생성 (Synthesis) 최적화 문제와 무한 차원 시스템 (PDE 등) 으로의 확장이 향후 연구 과제로 제시되었습니다.

요약하자면, SCORE 는 극단값 이론을 활용하여 고차원 비선형 시스템의 안정성 영역을 기존 방법론으로는 불가능했던 규모 (500 차원) 에서 통계적으로 엄격하게 인증하는 획기적인 방법론을 제시했습니다.