Graduated Non-Convexity (1)
Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection 논문을 리뷰해보려 한다.
아직 완전히 이해한 것은 아니지만, 대략적으로는 (i) Graduated Non-Convexity (GNC) 와 (ii) Robust Estimation ≈ Outlier Process (Black–Rangarajan Duality) 두 이론을 결합한 논문으로 보인다.
이 논문의 목표는 (a) outlier에 강건 하면서도 (b) local optimum에 갇히지 않는 robust solver를 만드는 것으로 보인다. 왜 (a) 와 (b) 가 중요할까?
관측 모델이 현실에서 불완전하기 때문이다. 로보틱스에서 자주 쓰는 목적 함수의 기본 형태는 다음과 같다:
\[\min_{\mathbf{x}} \sum_{i} \left\lVert \mathbf{y}_i - \mathbf{h}(\mathbf{x}) \right\rVert_2^2. \tag{1}\]각 기호는 다음과 같다.
- $\mathbf{y}_i$: 관측값 (sensor raw 값 또는 neural network 출력 등)
- $\mathbf{x}$: 추정 변수 (rotation, translation, scale 등)
- $\boldsymbol{\epsilon}_i$: 노이즈 (isotropic / anisotropic Gaussian 등으로 모델링)
관측–변수–모델 $ \mathbf{h}(\cdot) $이 이상적으로 잘 맞으면 $\mathbf{x}$를 찾으면 된다. 하지만 현실에는 모델링의 한계 때문에 outlier가 존재하므로, 모델 불확실성 때문에 (a)의 특성을 가진, robust solver가 필요하다.
Outlier에 강건하게 만들기 위해 다음과 같은 형태로 목적을 바꾼다:
\[\min_{\mathbf{x}} \sum_{i} \rho\!\left( \left\lVert \mathbf{y}_i - \mathbf{h}(\mathbf{x}) \right\rVert_2^2 \right). \tag{2}\]기본적인 최적화 문제인 식 (1)은 “오차는 평균 근처에 종처럼 모여 있고, 아주 큰 오차(outlier)는 거의 없을 거야”라고 믿는 Gaussian Distribution를 암묵적으로 가정한 것이다. 이는 마치 과녁의 정중앙 근처에 대부분의 화살이 맞는 이상적인 상황과 같다.
하지만 현실 데이터에는 예상치 못하게 멀리 빗나간 화살, 즉 outlier가 종종 섞여 있다. 이런 outlier의 존재를 인정하고 그 영향을 줄이기 위해, 우리는 더 관대한 분포 모델인 Cauchy Distribution 같은 heavy-tail Distribution를 가정할 수 있다.
수학적으로, 이렇게 분포 가정을 바꾸는 것은 기존의 오차 계산식에 robust kernel $\rho{(\cdot)}$ 이라는 함수를 씌우는 것으로 표현할 수 있다.
이 $\rho{(\cdot)}$ 커널은 outlier처럼 아주 큰 오차 값에 대해서는 영향력을 줄이는 충격 흡수 장치 같은 역할을 한다. 그 결과, 우리는 outlier에 더 강건한(robust) 식 (2)를 얻게 된다.
그렇다면 왜 처음부터 $\rho{(\cdot)}$ 커널이 포함된 강건한 식 (2)를 사용하지 않을까?
여기에 중요한 트레이드오프가 있다. 식 (1)은 정답을 향한 내리막길이 상대적으로 매끈한 언덕과 같아서, 가장 낮은 지점인 global optimum에 쉽게 도달한다.
반면, 로버스트 커널 $\rho{(\cdot)}$ 이 추가된 식 (2)는 지형을 심각하게 울퉁불퉁한 산맥으로 만든다. 이 비선형성(non-convexity) 때문에 잘못하면 움푹 파인 수많은 local optimum(지역 최적해) 중 하나에 빠져버려, 더 깊은 진짜 계곡(global optimum)이 있어도 도달하지 못하게 된다.
결국 우리의 목표는 outlier에 흔들리지 않는 로버스트 커널 $\rho{(\cdot)}$ 의 장점은 취하면서도, 그것이 만들어내는 (b) 수많은 가짜 계곡(local optimum)을 피해 가장 깊은 진짜 계곡(global optimum)을 찾아내는 것이다.
이제 배경을 정리했으니, 논문이 제시하는 수학적 유도를 구체적으로 살펴본다.