How sensitive is my system?: Condition number (조건수)

How sensitive is my system?

우리가 공학 수업시간에 배우는 많은 방법들은 대부분 analytically solvable한 경우를 다룹니다. 다만 이를 실제 환경에 적용하려다 보면, 수학 문제에서는 가능했던 아름다운 가정들이 다 사라지고 numerical methods에 기대어 근사값을 구해야하는 경우가 많죠. (현실은 시궁...)

문제는 이렇게 numerical methods를 이용해서 해를 구한 경우, 해당 알고리즘이(혹은 시스템이) 내 입력(혹은 시스템 파라미터)에 어쩔 수 없이 들어가는 노이즈에 대해 얼마나 믿을만한지 확인할 필요가 있습니다. 내가 사용한 방법이 그 계산 과정에 들어가는 다양한 perturbation (예를 들면 floating point error)에 의해 크게 민감해서 기껏 구한 값이 노이즈와 다를 바 없다면 의미가 없을테니까요. 

일반적으로 입력값에 대한 작은 변화가 출력값에 큰 변화를 일으킨다면 결과가 믿을만하지 않다고 하겠죠. 이를 조금 더 어려운 용어를 사용해서 표현하자면 어떤 문제가 민감한지 아닌지 그리고 numerical solution이 믿을만한지는 그 문제가 "well-behaved"인 지 "ill-behaved"인 지에 달려있습니다:

• If a small change in the input causes a small change in the output, the system is well-conditioned or well-behaved.
• If a small change in the input can cause a large change in the output, the system is ill-conditioned or ill-behaved.

Condition number

이렇게 시스템이 민감한 정도를 정량적으로 보여주는 값이 바로 absolute 혹은 relative conidtion number입니다:

$$\hat{\kappa}\geq\frac{||\text{change in output}||}{||\text{change in input}||}, \quad ||\text{change in output}||=\hat{\kappa}||\text{change in input}||\\
\kappa\geq\frac{||\text{change in output}||/||\text{output}||}{||\text{change in input}||/||\text{input}||}, \quad \frac{||\text{change in output}||}{||\text{output}||}=\kappa\frac{||\text{change in input}||}{||\text{input}||}$$

Absolute condition과 달리 relative condition number는 입력과 출력값에 대한 normalized change를 비교하기 때문에 특정 unit에 대해 변화하지 않는다는 특징이 있습니다.

여기서 $||x||$는 어떤 변수 $x$에 대한 norm("size")이며 $x$는 scalar, vector, matrix, function 등 다양한 변수일 수 있는데요. 보시다시피 condition number는 어떤 값들의 크기를 norm으로 비교하기 때문에 사용하는 norm의 종류에 따라 조금씩 값이 바뀔 수 있습니다. 앞으로는 편의상 vector에 대해서는 $p=2$ norm을 사용하고 matrix에 대해서는 spectral norm을 사용하겠습니다.

Condition number가 작을수록 내 문제에 대한 solution이 data에 포함된 error, noise, approximation 등으로 인한 perturbation에 대해 덜 민감하고 condition number가 클수록 문제가 ill-conditioned라고 할 수 있겠죠. 이제부턴 몇 가지 다른 시스템들에 대해 condition number(조건수)가 어떻게 정의되는지 좀 더 구체적으로 살펴보겠습니다.

System with single input and output variables

어떤 system이 단일입력 $x$와 단일출력 $y$를 갖는다고 해봅시다: $y=f(x)$. 임의의 점 $x$에 대하여 함수 $f$의 condition number는 입력값과 출력값의 worst case (greatest) 변화 비율로 정의됩니다:
$$\hat{\kappa}=\lim_{\epsilon\rightarrow0}\sup_{|\delta x|\leq \epsilon}\frac{|\delta f(x)|}{|\delta x|}, \quad \kappa=\lim_{\epsilon\rightarrow0}\sup_{|\delta x|\leq \epsilon}\frac{|\delta f(x)|/|f(x)|}{|\delta x|/|x|}.$$
주의할 점은 condition number가 일반적으로 $x$에 대한 함수라는 점입니다.

Perturbation $\delta x$가 작은 경우 함수 $f$를 Taylor expansion으로 근사할 수 있을 것이고 $$f(x+\delta x) = f(x) + f'(x)\delta x + f''(x)\frac{\delta x^2}{2} + \cdots \approx f(x) + f'(x)\delta x,$$
이는 곧, $$\delta y = f(x+\delta x)-f(x) \approx f'(x)\delta x $$
이므로, 양 변에 절대값을 씌우면 다음과 같습니다: $$|\delta y|=|f(x+ \delta x)-f(x)|\approx |f'(x)\delta x|=|f'(x)||\delta x|=\hat{\kappa}|\delta x|.$$
여기서 $\hat{\kappa}=\frac{|\delta y|}{|\delta x|}=|f'(x)|$는 absolute condition number입니다. 다시 양 변을 $|y|=|f(x)|$로 나누면,
$$\frac{|\delta y|}{|y|}=\frac{|f(x+\delta x)-f(x)|}{|f(x)|}\approx\frac{|f'(x)||\delta x|}{|f(x)|}=\frac{|x||f'(x)|}{|f(x)|}\frac{|\delta x|}{|x|}=\kappa\frac{|\delta x|}{|x|}$$를 얻을 수 있습니다. 여기서 $\kappa$는 relative condition number로
$$\kappa = \frac{|\delta y|/|y|}{|\delta x|/|x|}=\frac{|x||f'(x)|}{|f(x)|}=\frac{|f'(x)|}{|f(x)|/|x|}.$$
지금까지는 시스템의 출력 $y=f(x)$에 대해 입력 $x$에 대한 반응을 분석한 것인데요. 만약 반대로 $f(x)=0$가 주어지고 이에 대한 $x$를 찾는 문제를 생각해보겠습니다. 이 경우 앞서와는 다르게 $x$를 마치 출력처럼 생각하고 $y=f(x)=0$를 입력처럼 생각하면 됩니다. 즉, $y=0$일 때 $x=g(y)=f^{-1}(y)$인 inverse problem을 푸는 것으로 표현할 수 있습니다. 여기서 $g(y)$에 대한 absolute condition number는 다음과 같겠죠:
$$\hat{\kappa}=|g'(y)|=\left|\frac{d}{dy}[f^{-1}(y)]\right|=\frac{1}{|f'(x)|}.$$

즉, $|f'(x)|$에 대한 역수가 되므로 $|f'(x)|$가 클수록 $|g'(y)|$가 작으며 문제가 well-conditioned 된다는 것을 확인할 수 있습니다.

예를 들자면 위 그림과 같이 $|f_1'(x)|>|f_2'(x)|$인 경우 $f(x)=0$ 문제를 풀 때 $f_1(x)$가 $f_2(x)$보다 well-conditioned 시스템이며 반대로 $y=f(x)$의 경우 $f_1(x)$가 $f_2(x)$보다 ill-conditioned 시스템이 된다는 것을 알 수 있습니다.

Condition number가 $x$에 대한 함수인 이유를 좀 더 이해하기 쉽도록 하기 위해 예제를 하나 풀어보겠습니다: $$y=f(x)=\frac{x}{1-x},\quad f'(x)=\frac{1}{(1-x)^2}$$
이 함수는 $x=-0.99$일 때는 $$\kappa = \frac{f'(x)|}{|f(x)|/|x|}=\frac{1}{|1-x|}=\frac{1}{1.99}\approx 0.5$$이므로 $y=f(x)$ 문제를 푸는 것이 well-conditioned 문제이지만, $x=0.99$에서는 $$\kappa = \frac{f'(x)|}{|f(x)|/|x|}=\frac{1}{|1-x|}=\frac{1}{0.01}= 100$$으로 매우 ill-conditioned 문제임을 알 수 있습니다. 즉, $x=0.98$에서 $x=0.99$로 $|\delta x|=0.01$만큼 바뀌었을 떄, $|\delta y|=|99-49|=50$으로 매우 크게 바뀌는 것을 볼 수 있습니다.

System with multiple input and output variables

이제부터는 위에서 살펴본 단일 변수 시스템에 대한 결과를 다변수 시스템에 대해 일반화해보겠습니다. 이제 $\mathbf{x}=[x_1,\cdots,x_N]^T$와 $\mathbf{y}=[y_1,\cdots,y_M]^T$는 vector이며 둘의 관계는 $\mathbf{y}=\mathbf{f}(\mathbf{x})$으로 표현할 수 있습니다. 이 때, $\delta \mathbf{x}$에 대해 출력값의 변화량은 다음과 같습니다:
$$\delta \mathbf{y}=\mathbf{f}(\mathbf{x}+\delta \mathbf{x})-\mathbf{f}(\mathbf{x}).$$ 앞서와 마찬가지로  $\delta \mathbf{x}$가 작을 때 첫 항을 Taylor series expansion으로 근사하면:
$$\mathbf{f}(\mathbf{x}+\delta\mathbf{x})\approx \mathbf{f}(\mathbf{x})+\mathbf{J}_f(\mathbf{x})\delta\mathbf{x}$$이므로,
$$||\delta \mathbf{y}||=||\mathbf{f}(\mathbf{x}+\delta \mathbf{x})-\mathbf{f}(\mathbf{x})||\approx||\mathbf{J}_f(\mathbf{x})\delta\mathbf{x}||\leq||\mathbf{J}_f(\mathbf{x})||~||\delta\mathbf{x}||=\hat{\kappa}||\delta \mathbf{x}||$$
로 absolute condition number를 얻을 수 있습니다: $$\hat{\kappa}=\frac{||\delta \mathbf{y}||}{||\delta \mathbf{x}||}=||\mathbf{J}_f(\mathbf{x})||.$$
양변을 $||\mathbf{y}||=||\mathbf{f}(\mathbf{x})||$로 각각 나누어주면, $$\frac{||\delta\mathbf{y}||}{||\mathbf{y}||}\approx\frac{||\mathbf{J}_f(\mathbf{x})\delta \mathbf{x}||}{||\mathbf{f}(\mathbf{x})||}\leq \frac{||\mathbf{x}||~||\mathbf{J}_f(\mathbf{x})||}{||\mathbf{f}(\mathbf{x})||}\frac{||\delta \mathbf{x}||}{||\mathbf{x}||}=\kappa \frac{||\delta \mathbf{x}||}{||\mathbf{x}||}$$이므로, relative condition number $\kappa$는 $$\kappa=\frac{||\delta \mathbf{y}||/||\mathbf{y}||}{||\delta \mathbf{x}||/||\mathbf{x}||}=\frac{||\mathbf{x}||~\mathbf{J}_f(\mathbf{x})}{||\mathbf{f}(\mathbf{x})||}=\frac{\mathbf{J}_f(\mathbf{x})}{||\mathbf{f}(\mathbf{x})||/||\mathbf{x}||}.$$
이해하기 쉬운 linear system을 예시로 들자면, $N$-dim 입력 $\mathbf{x}=[x_1,\cdots,x_N]^T$와 $M$-dim 출력 $\mathbf{y}=[y_1,\cdots,y_M]^T$에 대해 둘의 관계는 $$\mathbf{y}=\mathbf{f}(\mathbf{x})=\mathbf{A}_{M\times N}\mathbf{x}$$로 표현됩니다.

이 때, forward problem에 대해서 absolute condition number는 정의에 의해 $\hat{\kappa}(\mathbf{A})=||\mathbf{J}_f(\mathbf{x})||=||\mathbf{A}||$이고 relative condition number는 $$\kappa(\mathbf{A})=\frac{||\mathbf{x}||~||\mathbf{J}_f(\mathbf{x})||}{||\mathbf{f}(\mathbf{x})||}=||\mathbf{A}||\frac{||\mathbf{x}||}{||\mathbf{Ax}||}$$입니다. 여기서 $$||\mathbf{x}||=||\mathbf{A^{-1}Ax}||\leq||\mathbf{A^{-1}}||~||\mathbf{Ax}||, \quad i.e.,~||\mathbf{Ax}||\geq\frac{||\mathbf{x}||}{||\mathbf{A^{-1}}||}$$이므로 이를 위 식에 대체해서 넣으면, relative condition number의 upper bound가 $||\mathbf{A}||~||\mathbf{A^{-1}}||$임을 알 수 있습니다: $$||\mathbf{A}||\frac{||\mathbf{x}||}{||\mathbf{Ax}||}\leq||\mathbf{A}||~||\mathbf{A^{-1}}||\frac{||\mathbf{x}||}{||\mathbf{x}||}=||\mathbf{A}||~||\mathbf{A^{-1}}||=\kappa(\mathbf{A}).$$ 한편, $\kappa$의 lower bound는 1로써 아래와 같이 매우 간단히 얻을 수 있습니다: $$\kappa(\mathbf{A})=||\mathbf{A}||~||\mathbf{A^{-1}}||\geq||\mathbf{A}\mathbf{A^{-1}}||=||\mathbf{I}||=1.$$ $\kappa=1$이라는 뜻은 최소한 내 시스템이 data가 가진 error를 그 이상의 단위(order)로 증폭시키지는 않는다는 것으로 해석할 수 있겠습니다.

Another representation

여기서 $\mathbf{A}$의 singular value들을 $\{\sigma_1\geq\cdots\geq\sigma_n\}$이라 하면 $\mathbf{A^{-1}}$의 singular value도 $\{1/\sigma_n\geq\cdots\geq1/\sigma_1\}$과 같이 정리할 수 있고 이 때, $||\mathbf{A}||=\sigma_{max}=\sigma_1$, $||\mathbf{A^{-1}}||=1/\sigma_{min}=1/\sigma_n$임을 알 수 있습니다. 따라서 $$\kappa(\mathbf{A}) = ||\mathbf{A}||~||\mathbf{A^{-1}}||=\frac{\sigma_{max}}{\sigma_{min}}$$로 깔끔하게 정리가 됩니다.

즉, $\mathbf{A}$의 최대 최소 singular value 간의 간극이 클수록 condition number가 크다는 것을 알 수 있습니다. 이는 다르게 해석하면 $\kappa(\mathbf{A})$가 $\mathbf{A}$의 singularity를 측정하는 방법이라고 생각할 수도 있습니다. 만약 $\mathbf{A}$가 singular하면 적어도 하나의 singular value가 0이고 이는 $\kappa(\mathbf{A})=\infty$를 뜻하기 때문입니다.

위에서 구한 식을 이용하여 $\mathbf{y}=\mathbf{Ax}$와 $\mathbf{x}=\mathbf{Ay}$ 각각의 linear system 문제에 대해 worst case scenario sensitivity를 살펴보겠습니다.

먼저 $\mathbf{A}$의 singular value decomposition을 해서 $\mathbf{A}=\mathbf{U\Sigma V^*}$ $\mathbf{\Sigma}$의 diagonal elements인 singular value들을 descending order로 sort해줍니다:  $\{\sigma_1\geq\cdots\geq\sigma_n\}$. 그러면 자연스럽게 $\mathbf{A^{-1}}=\mathbf{V\Sigma^{-1} U^*}$도 구할 수 있죠.

그럼 각각의 경우에 대해 문제를 살펴보겠습니다:

1) Worst case for $\mathbf{y}=\mathbf{Ax}$

$\mathbf{x}=\mathbf{v_n}$을 가장 작은 singular value $\sigma_{min}=\sigma_n$에 대응하는 right singular vector라고 하면, \begin{align*}\mathbf{y} &=\mathbf{Ax}=(\mathbf{U\Sigma V^*})\mathbf{v_n}\\
&=\sigma_n\mathbf{u_n}\end{align*}이므로 $$\mathbf{y}+\delta\mathbf{y}=\mathbf{A}(\mathbf{x}+\delta\mathbf{x})=\sigma_n\mathbf{u_n} + \mathbf{A}\delta \mathbf{x}$$입니다.

그럼 $||\delta \mathbf{x}||$가 작으면 absolute error $||\delta \mathbf{y}||=||\mathbf{A}\delta \mathbf{x}||$는 작을 수 있겠으나, $\sigma_{min}=\sigma_n$이 매우 작은 경우 $||\mathbf{y}||=|\sigma_n|~||\mathbf{u}||$도 매우 작을 수 있으므로 relative error $\frac{||\delta\mathbf{y}||}{||\mathbf{y}||}$는 absolute error와 달리 매우 클 수 있습니다.

2) Worst case for $\mathbf{x}=\mathbf{Ay}$

$\mathbf{x}=\mathbf{u_1}$을 가장 큰 singular value $\sigma_{max}=\sigma_1$에 대응하는 left singular vector라고 하면, \begin{align*}\mathbf{y} &=\mathbf{A^{-1}x}=(\mathbf{V\Sigma^{-1} U^*})\mathbf{u_1}\\

&=\frac{1}{\sigma_1}\mathbf{v_1}\end{align*}이므로 $$\mathbf{y}+\delta\mathbf{y}=\mathbf{A^{-1}}(\mathbf{x}+\delta\mathbf{x})=\frac{1}{\sigma_1}\mathbf{v_1} + \mathbf{A^{-1}}\delta \mathbf{x}$$입니다.

그럼 $||\delta \mathbf{x}||$가 작으면 absolute error $||\delta \mathbf{y}||=||\mathbf{A^{-1}}\delta \mathbf{x}||$는 작을 수 있겠으나, $\sigma_{max}=\sigma_1$이 매우 큰 경우 $||\mathbf{y}||=||\mathbf{u}||/|\sigma_1|$도 매우 작을 수 있으므로 relative error $\frac{||\delta\mathbf{y}||}{||\mathbf{y}||}$는 absolute error와 달리 매우 클 수 있습니다.

Approximate solution

지금까지 확인한 것을 바탕으로 어떤 시스템의 근사해를 구할 때 주의해야할 점을 알 수 있습니다. 어떤 문제를 풀 때 우리는 보통 어떤 loss function $\mathbf{f}$로 정의되는 $$||\mathbf{f}(\mathbf{\hat{x}})||\approx 0$$라는 criteria로 함수 값에서의 small residual 을 갖는 $\mathbf{\hat{x}}$을 구하게 되죠. 그런데 이렇게 구한 해가$$||\mathbf{\hat{x}}-\mathbf{x^*}||\approx 0, \quad \mathbf{}$$라는 criteria에서 볼 때 true solution (보통 모르지만) $\mathbf{x^*}$에 대해 가까운 $\mathbf{\hat{x}}$을 찾는 것과 합치하려면 우리가 만든 문제 자체가 "well-conditioned"여야만 한다는 것을 이해할 수 있습니다. 

지금까지 어떤 시스템의 sensitivity를 정량적으로 분석하는 방법 중 하나를 살펴보았습니다. 이만큼 공부하고 썼다고 주말이 사라졌네요. 오늘은 그럼 이 정도로 마무리 해야겠습니다. 예제들도 만드려면 만들 수 있는데, 차후 여유가 된다면 추가하는 것으로ㅎㅎ

그럼 다음 글들에서 뵙지요.

다음 읽을 거리

• 디지털 신호 처리가 궁금하다면: Signal Processing For Communications
• 머신러닝에 속하는 전반적인 연구 내용들이 궁금하다면: Machine learning
• GAN에 관심이 많다면: GAN
• 머신러닝에서 잘 사용되는 수학에 관심이 있다면: Mathematics