Graduated Non-Convexity (2)
지난 (1)편에서는 robust estimation의 기본 문제 설정을 정리했다. 핵심은, 단순한 least squares인 식 (1)에 robust kernel $\rho(\cdot)$를 씌운 식 (2)가 outlier에 강건해지는 대신, non-convexity 때문에 local optimum 문제가 생긴다는 것이었다.
이번 글에서는 논문이 그 문제를 다루기 위해 가져오는 첫 번째 도구, Black–Rangarajan Duality를 정리한다.
Black–Rangarajan Duality
논문의 핵심 주장 중 하나는, 식 (2)의 robust estimation 문제를 전혀 다른 형태로 다시 쓸 수 있다는 것이다. 바로 다음 식이다:
\[\min_{\mathbf{x},\, w_i \in [0,1]} \sum_{i=1}^{N} \left( w_i r_i^2(\mathbf{x}) + \Phi_{\rho}(w_i) \right). \tag{3}\]각 기호는 다음과 같다.
- $r_i(\mathbf{x})$: $i$번째 measurement의 residual
- $w_i \in [0,1]$: 각 measurement에 대응하는 weight (slack variable)
- $\Phi_\rho(w_i)$: weight에 대한 penalty term — 논문에서 이를 outlier process라 부른다
outlier process란?
penalty term $\Phi_\rho(w)$는 weight가 0 또는 1이 아닌 애매한 중간값에 머물 때 벌점을 부과하는 함수다. 직관적으로는 “weight가 0.5 같은 데 애매하게 있으면 벌점을 물린다”는 뜻이다. 이 term 덕분에 최적화 과정에서 각 $w_i$는 자연스럽게 inlier면 1, outlier면 0으로 수렴하게 된다. 즉 outlier process = weight의 이진화를 유도하는 regularizer라고 이해하면 된다.
즉 원래는
\[\min_{\mathbf{x}} \sum_{i=1}^N \rho(r_i(\mathbf{x})) \tag{2}\]를 풀고 있었는데, 이를
\[\min_{\mathbf{x},\,w_i} \sum_i \Big( w_i r_i^2(\mathbf{x}) + \Phi_\rho(w_i) \Big) \tag{3}\]꼴로 바꾸어 생각할 수 있다는 것이다.
처음 보면 “아니 갑자기 $w_i$는 왜 튀어나오지?” 싶다.
근데 이 표현은 생각보다 직관적이다.
- residual이 작은 measurement는 $w_i \approx 1$
- residual이 큰 measurement는 $w_i \approx 0$
이 되도록 유도하면, 결국 각 measurement마다 “이 놈을 얼마나 믿을지”를 weight로 표현하는 셈이다.
즉 robust estimation = weighted least squares + outlier process 로 볼 수 있다는 것이다.
왜 식 (2)와 식 (3)이 equivalent한가?
핵심은 $\rho(r)$를 그냥 residual $r$의 함수로 보지 않고, squared residual의 함수로 다시 보는 데 있다.
논문은 다음을 정의한다:
\[\phi(z) := \rho(\sqrt{z}), \qquad z \ge 0.\]즉 $z = r^2$라고 보면 $\rho(r) = \phi(r^2)$이다.
이제 $\phi(z)$가 다음 조건을 만족한다고 하자:
\[\lim_{z\to 0}\phi'(z)=1,\qquad \lim_{z\to\infty}\phi'(z)=0,\qquad \phi''(z)<0.\]이 조건의 의미는 꽤 예쁘다.
- 작은 오차 영역에서는 $\phi’(z)\approx 1$, 즉 quadratic cost처럼 동작한다.
- 큰 오차 영역에서는 $\phi’(z)\approx 0$, 즉 큰 residual의 영향력이 점점 줄어든다.
- 그리고 $\phi’‘(z)<0$이므로 $\phi$는 strictly concave하다.
여기서 제일 중요하다.
concave function은 접선들의 하한 envelope로 표현할 수 있다.
임의의 $z_0$에서 $\phi$의 접선은
\[\phi(z_0)+\phi'(z_0)(z-z_0)\]이고, concavity 때문에 모든 $z$에 대해
\[\phi(z)\le \phi(z_0)+\phi'(z_0)(z-z_0)\]가 성립한다.
이를 정리하면
\[\phi(z)\le \underbrace{\phi'(z_0)}_{=:\,w} z + \underbrace{\big(\phi(z_0)-\phi'(z_0)z_0\big)}_{=:\,\Phi_\rho(w)}.\]즉 각 $z_0$에 대해 하나의 직선 $wz + \Phi_\rho(w)$를 얻는다.
그리고 $w = \phi’(z_0)$인데, 위 조건상 $\phi’(z)$는 $1$에서 $0$으로 감소하므로 $w \in [0,1]$이다.
결국 모든 접선들 중 가장 아래에 있는 것을 취하면 원래 함수가 복원된다:
\[\phi(z) = \min_{w\in[0,1]} \left( wz+\Phi_\rho(w) \right).\]이제 $z = r_i^2(\mathbf{x})$를 대입하면
\[\rho(r_i(\mathbf{x})) = \phi(r_i^2(\mathbf{x})) = \min_{w_i\in[0,1]} \left( w_i r_i^2(\mathbf{x})+\Phi_\rho(w_i) \right).\]이를 모든 $i$에 대해 합치면
\[\sum_{i=1}^N \rho(r_i(\mathbf{x})) = \min_{w_i\in[0,1]} \sum_{i=1}^N \left( w_i r_i^2(\mathbf{x})+\Phi_\rho(w_i) \right).\]마지막으로 $\mathbf{x}$에 대한 최소화까지 포함하면 식 (2)와 식 (3)이 동치가 된다.
즉 Black–Rangarajan duality의 본질은 다음 한 줄이다:
로버스트 커널을 직접 다루는 대신, 각 measurement마다 “신뢰도 weight”를 도입한 weighted least squares 문제로 다시 쓸 수 있다.
Geman–McClure (GM) 예시
이제 위의 추상적인 이야기에서 제일 중요한 concrete example 하나를 보자.
바로 Geman–McClure (GM) robust kernel이다.
논문에서 GM cost는 다음과 같이 등장한다:
\[\rho(r)=\frac{\bar c^2 r^2}{\bar c^2+r^2}. \tag{4}\]그리고 GNC를 위해 control parameter $\mu$를 도입한 surrogate는
\[\rho_\mu(r)=\frac{\mu \bar c^2 r^2}{\mu \bar c^2+r^2}. \tag{5}\]이 식은 형태가 아주 좋다.
- $\mu \to \infty$이면 거의 $r^2$에 가까워져서 quadratic처럼 보인다.
- $\mu = 1$이면 원래 GM cost를 회복한다.
즉 처음에는 완만한 convex-like surrogate로 시작해서, 점점 진짜 robust cost로 접근시키는 것이 GNC의 전략이다.
GM이 위 조건을 만족하는지 체크
$\phi(z)=\rho(\sqrt{z})$이므로, GM surrogate에 대해서
\[\phi_\mu(z) = \rho_\mu(\sqrt z) = \frac{\mu \bar c^2 z}{\mu \bar c^2+z}\]를 보자.
1차 미분은
\[\phi_\mu'(z) = \frac{(\mu \bar c^2)^2}{(\mu \bar c^2+z)^2}.\]따라서
\[\lim_{z\to 0}\phi_\mu'(z)=1,\qquad \lim_{z\to\infty}\phi_\mu'(z)=0.\]2차 미분은
\[\phi_\mu''(z) = -\frac{2(\mu \bar c^2)^2}{(\mu \bar c^2+z)^3}<0.\]즉 전 구간에서 strictly concave하다. GM surrogate는 Black–Rangarajan duality의 가정을 아주 예쁘게 만족한다.
GM을 Black–Rangarajan formulation으로 바꾸기
이제 목표는 다음과 같다.
\[\rho_\mu(r) = \frac{\mu \bar c^2 r^2}{\mu \bar c^2+r^2} \quad\Longleftrightarrow\quad \min_{w\in[0,1]} \left( wr^2+\Phi_{\rho_\mu}(w) \right).\]논문은 이때 대응하는 outlier process를
\[\Phi_{\rho_\mu}(w)=\mu \bar c^2(\sqrt{w}-1)^2 \tag{6}\]로 둔다. 즉 GM은 다음과 동치다:
\[\rho_\mu(r) = \min_{w\in[0,1]} \left( wr^2+\mu \bar c^2(\sqrt{w}-1)^2 \right). \tag{7}\]실제 유도
다음 1차원 문제를 생각하자:
\[f(w)=wr^2+\mu \bar c^2(\sqrt{w}-1)^2, \qquad w\in[0,1].\]$\sqrt{w}$가 보기 싫으니 $u := \sqrt{w}$, $u \in [0,1]$, $w = u^2$으로 치환하면
\[f(u)=u^2r^2+\mu \bar c^2(u-1)^2.\]$u$에 대해 미분하면
\[\frac{df}{du} = 2ur^2+2\mu \bar c^2(u-1).\]최적점에서 $\frac{df}{du}=0$이므로
\[u(r^2+\mu \bar c^2)=\mu \bar c^2 \quad\Longrightarrow\quad u^\star=\frac{\mu \bar c^2}{r^2+\mu \bar c^2}.\]따라서 최적 weight는
\[w^\star=(u^\star)^2 = \left( \frac{\mu \bar c^2}{r^2+\mu \bar c^2} \right)^2. \tag{8}\]이게 바로 GM의 closed-form weight update다.
정말로 원래 GM cost가 복원되는지
$u^\star$를 다시 $f(u)$에 넣어보자.
\[u^\star-1 = \frac{\mu \bar c^2}{r^2+\mu \bar c^2}-1 = -\frac{r^2}{r^2+\mu \bar c^2}.\]따라서
\[(u^\star)^2r^2 = \frac{(\mu \bar c^2)^2 r^2}{(r^2+\mu \bar c^2)^2}, \qquad \mu \bar c^2(u^\star-1)^2 = \frac{\mu \bar c^2 r^4}{(r^2+\mu \bar c^2)^2}.\]두 항을 더하면
\[f(u^\star) = \frac{\mu \bar c^2 r^2(\mu \bar c^2+r^2)}{(r^2+\mu \bar c^2)^2} = \frac{\mu \bar c^2 r^2}{r^2+\mu \bar c^2} = \rho_\mu(r).\]정말로 원래 GM surrogate와 정확히 일치한다.
이 weight가 의미하는 것
GM에서 최적 weight는
\[w^\star = \left( \frac{\mu \bar c^2}{r^2+\mu \bar c^2} \right)^2\]였다. 이걸 보면 아주 직관적이다.
- $r^2 \ll \mu \bar c^2$이면 $w^\star \approx 1$
- $r^2 \gg \mu \bar c^2$이면 $w^\star \approx 0$
즉 residual이 작은 점은 거의 full weight를 받고, residual이 큰 점은 거의 버려진다.
원래는 $\rho(r)$라는 비선형 robust kernel 하나만 보고 있었는데, BR duality로 보면 사실은
“각 measurement마다 inlier일 가능성을 나타내는 weight를 같이 최적화하고 있구나”
라고 해석할 수 있게 된다. 나는 이 해석이 이 논문의 가장 예쁜 부분 중 하나라고 느꼈다.
왜 이 표현이 실제 알고리즘에 유리한가?
식 (3) 형태로 바꾸면 optimization이 아주 자연스러워진다.
먼저 $w_i$를 고정하면, 문제는
\[\min_{\mathbf{x}} \sum_i w_i r_i^2(\mathbf{x})\]가 되는데, 이건 그냥 weighted least squares다.
즉 기존에 가지고 있던 non-minimal solver를 그대로 넣을 수 있다.
반대로 $\mathbf{x}$를 고정하면 각 $w_i$는 독립적인 1차원 문제라서, GM의 경우 위에서 본 closed form
\[w_i = \left( \frac{\mu \bar c^2}{r_i^2(\mathbf{x})+\mu \bar c^2} \right)^2\]로 바로 갱신된다.
즉 robust estimation이
- 원래는 non-convex robust cost minimization 문제였는데
- BR duality를 거치면 weighted least squares + scalar weight update
- 그리고 GNC를 붙이면 처음에는 쉬운 surrogate부터 시작해서 점점 진짜 robust cost로 접근
하는 구조가 된다.
결국 이 논문은 Black–Rangarajan duality로 robust cost를 다루기 쉬운 형태로 바꾸고, GNC로 local optimum 문제를 피하려고 하는 논문이라고 이해하면 일단 큰 줄기는 맞아 보인다.
마무리
이번 글에서는 논문의 전체 알고리즘보다도, 그 기반이 되는 Black–Rangarajan Duality 쪽을 먼저 정리해봤다.
핵심은 다음이다.
① robust estimation 문제를 outlier process 형태로 다시 쓸 수 있다.
\[\min_{\mathbf{x}}\sum_i \rho(r_i(\mathbf{x})) \quad\Longleftrightarrow\quad \min_{\mathbf{x},\,w_i} \sum_i \Big(w_i r_i^2(\mathbf{x})+\Phi_\rho(w_i)\Big)\]② Geman–McClure의 경우 outlier process는
\[\Phi_{\rho_\mu}(w)=\mu \bar c^2(\sqrt{w}-1)^2\]③ 최적 weight는 closed form으로 나온다.
\[w^\star= \left( \frac{\mu \bar c^2}{r^2+\mu \bar c^2} \right)^2\]개인적으로는, robust kernel이 그냥 “이상치에 둔감한 loss”가 아니라 각 measurement의 신뢰도를 latent variable로 들고 들어오는 formulation으로 보인다는 점이 꽤 인상적이었다.
다음 글에서는 지금까지 정리한 Black–Rangarajan Duality가 GNC에서 정확하게 어떻게 활용되는지를 다뤄보겠다. 구체적으로는, $\mu$를 어떻게 스케줄링하면서 local minimum을 피해나가는지, 그리고 그 과정에서 이 duality가 어떤 역할을 하는지를 정리할 예정이다.