레이블이 kr인 게시물을 표시합니다. 모든 게시물 표시
레이블이 kr인 게시물을 표시합니다. 모든 게시물 표시

2022년 5월 13일 금요일

[PR12 Video] 385. Generative Modeling by Estimating Gradients of the Data Distribution


TensorFlowKR facebook comunity에서 모인 12명의 paper readers (PR12)가 읽어주는 deep learning papers

#385. Generative Modeling by Estimating Gradients of the Data Distribution


PR12 385번째 발표입니다. 요즘 하도 Diffusion model이 잘 되길래 이거 공부를 하긴 해야하겠는데..하다가 좀 각잡고 봐야겠다고 마음 먹었더니 NeurIPS 19년 논문으로 갔습니다. 사실 2005년에 나온 논문부터 해야하지만 발표를 위해 적절히 타협을..ㅎㅎ 재미있는 논문입니다. 보시면 Score-based generative model이 뭔지 아실 수 있으리라 생각합니다.




Paper:  https://arxiv.org/abs/1907.05600

다른 분들의 발표도 보고 싶다면 아래 링크에서 확인하시면 되겠습니다 :)
* 현재 4기가 진행 중입니다!


다음 읽을거리






2022년 3월 5일 토요일

[PR12 Video] 374. Fourier Features Let Networks Learn High-Frequency Functions in Low Dimensional Domains (+ NTK, Neural Tangent Kernel)


TensorFlowKR facebook comunity에서 모인 12명의 paper readers (PR12)가 읽어주는 deep learning papers

#374. Fourier Features Let Networks Learn High-Frequency Functions in Low Dimensional Domains


PR12 374번째 발표입니다. 오늘도 저번처럼 가면 갈수록 inductive bias를 줄여야한다고 외치고 있는 연구 방향과는 정반대로, 이론에 근간한 간단한 fix를 통해 훨씬 강력한 성능을 달성한 모델을 소개해보겠습니다. 매우 즐겁게? 읽었는데요. 다른 분들도 재미있으셨으면 좋겠습니다. (네...제가 그렇죠 뭐. 오늘도 매우 어려운 논문을 골라놓고 내일이 개강인데....난 왜 이 논문을 골라서 스스로 괴롭게 살까 계속 그 생각만 하면서 준비했습니다. 담부턴 좀 쉬운 논문 해야지 하면서 맨날 스스로도 소화하기 힘든 논문을 고르는건 과학인듯 합니다.) (꼭 고를 때 되면 쉽게 할 수 있어보이더라) (다 하보니 1시간...)




Paper:  https://arxiv.org/abs/2006.10739

다른 분들의 발표도 보고 싶다면 아래 링크에서 확인하시면 되겠습니다 :)
* 현재 4기가 진행 중입니다!


다음 읽을거리






2021년 8월 12일 목요일

[PR12 Video] 338. Alias-Free Generative Adversarial Networks (StyleGAN3) 리뷰 개념 정리


TensorFlowKR facebook comunity에서 모인 12명의 paper readers (PR12)가 읽어주는 deep learning papers

#338. Alias-Free Generative Adversarial Networks


PR12 338번째 발표입니다. 오늘도 저번처럼 가면 갈수록 inductive bias를 줄여야한다고 외치고 있는 연구 방향과는 정반대로, 이론에 근간한 간단한 fix를 통해 훨씬 강력한 성능을 달성한 모델을 소개해보겠습니다. Nvidia의 Tero Karras가 1저자인 논문입니다. 🙂 매우 즐겁게? 읽었는데요. 다른 분들도 재미있으셨으면 좋겠습니다. (너무 많은 내용을 하나에 담아서 설명하려고 했나 하면서 후회하고 있습니다 ㅋㅋ 힘들었어요...담부턴 좀 쉬운 논문 해야지 하면서 맨날 스스로도 소화하기 힘든 논문을 고르는건 무슨 이유일까요..orz)




Paper:  https://arxiv.org/abs/2106.12423

처음 PR12를 시작했을 때는 대학원생, 1기 마지막 발표 때는 네이버, 얼마 전까지는 EPFL에서 포닥, 이제 드디어 UNIST에서 조교수로 시작합니다. PR12와 제 커리어가 같이 흘러가는군요. 열심히 해보겠습니다. 다른 분들의 발표도 보고 싶다면 아래 링크에서 확인하시면 되겠습니다 :)
* 현재 4기가 진행 중입니다!


다음 읽을거리






[PR12 Video] 323. Separation and Concentration in Deep Networks


TensorFlowKR facebook comunity에서 모인 12명의 paper readers (PR12)가 읽어주는 deep learning papers

#323.Separation and Concentration in Deep Networks


오늘도 저번처럼 가면 갈수록 big model로 치닫고 있는 연구 방향과는 정반대로, 학습이 거의 없이 ImageNet에서 ResNet classification 성능을 제치는 모델을 소개해보겠습니다. NYU의 Joan Bruna와 신호처리의 거장 중 한명인 Stephane Mallat 교수님의 scattering network에 대해 아신다면 더 잘 이해가 가실 것 같습니다 🙂 매우 즐겁게 읽었는데요. 다른 분들도 재미있으셨으면 좋겠습니다.




Paper:  https://openreview.net/forum?id=8HhkbjrWLdE
슬라이드: https://www.slideshare.net/thinkingfactory/pr12-generative-models-as-distributions-of-functions

4기 되어 두번째 발표입니다. 다른 분들의 발표도 보고 싶다면 아래 링크에서 확인하시면 되겠습니다 :)
* 현재 4기가 진행 중입니다!


다음 읽을거리






2021년 4월 12일 월요일

[PR12 Video] 312. Generative Models as Distributions of Functions


TensorFlowKR facebook comunity에서 모인 12명의 paper readers (PR12)가 읽어주는 deep learning papers

#312.Generative Models as Distributions of Functions


오늘은 2021년 2월에 arXiv에 올라온 Generative Models as Distributions of Functions 논문을 리뷰하겠습니다. 1기 이후 오랜만에 PR12 멤버로 합류하게 되었는데요. 가면 갈수록 big model로 치닫고 있는 연구 방향과는 정반대로, 상당히 독특한 형태로 재미있게 생성 문제를 풀은 연구를 소개해봤습니다. 저는 개인적으로 매우 즐겁게 읽었는데요. 다른 분들도 재미있어 하시면 좋겠습니다.




Paper:  https://arxiv.org/abs/2102.04776
슬라이드: https://www.slideshare.net/thinkingfactory/pr12-generative-models-as-distributions-of-functions

처음 PR12를 시작했을 때는 대학원생, 1기 마지막 발표 때는 네이버, 지금은 EPFL에서 포닥, 곧 UNIST에서 조교수로 PR12와 제 커리어가 같이 흘러가고 있는걸 보니 또 나름 감회가 새롭네요. 다른 분들의 발표도 보고 싶다면 아래 링크에서 확인하시면 되겠습니다 :)
* 현재 4기가 진행 중입니다!


다음 읽을거리






2020년 4월 1일 수요일

복소 함수의 다가성 (multivaluedness of complex function)

오늘은 문제 하나를 들고 왔습니다. 본 내용에 들어가기 앞서 다음 문제를 한 번 같이 풀어보면 훨씬 더 재미있을 것이라 생각합니다.

먼저 오일러 공식에 따라 $e^{j2\pi t}$를 다음과 같이 표현할 수 있습니다: $$e^{j2\pi t}=\cos(2\pi t)+j\sin(2\pi t)$$ 그리고 이에 따라 $e^{j2\pi}=1$이 성립한다는 것도 알 수 있습니다. 이 때, 다음과 같은 등식을 살펴보시죠: $$e^{j2\pi t}= (e^{j2\pi})^t= 1^t = 1, \quad t \in \mathbb{R}$$ 수식 전개가 자연스러워보이지만 조금 더 생각해보면 매우 이상하다는 것을 알 수 있습니다. $t \in \mathbb{R}$일 때, *$e^{j2\pi t}\neq 1$이므로 결과가 서로 상충되기 때문입니다.
* 여기서 $e^{j2\pi t}\neq 1$가 바로 받아들여지지 않는다면 $t=\frac{1}{2}$인 경우를 생각해보면 됩니다. $e^{j\pi}=\cos(\pi)+j\sin(\pi)=-1.$ 

따라서 이를 위 식과 함께 써보면, $$1\neq e^{j2\pi t}= (e^{j2\pi})^t= 1^t = 1, \quad t \in \mathbb{R}$$ 이와 같이 매우 모순적인 결론에 이르게 됩니다.

"음... 어디가 잘못된 것일까요?"


복소 함수의 다가성


위 문제를 처음 봤을 때, 매우 당황스러웠습니다. 도무지 어디가 잘못되었는지 찾기가 어려웠기 때문입니다. 이 문제를 풀기 위해서 열심히 공부를 하다가 이 문제의 근원이 복소 함수의 다가성에 있다는 것을 알았는데요. 이 내용이 잘 받아들여지지 않아서 근원을 알고나서도 제대로 이해하기 위해 한참을 더 머리를 굴려야 했습니다.

복소 함수의 다가성을 좀 더 쉽게 이해하려면, 예시를 보는게 좋습니다. 가장 쉬운 예시로는 복소수 로그 함수 $f(z) = \ln z, z\in\mathbb{C}$가 있습니다. 복소수는 polar form으로 표현할 수 있고 $$z = re^{j\theta}, \quad z\in\mathbb{C},$$ 따라서 로그 함수를 다음과 같이 풀어 쓸 수 있습니다: $$f(z)=f(r,\theta)= \ln r e^{j\theta}= \ln r + \ln e^{j\theta} = \ln r + j\theta.$$ 그런데 여기서 $n\in\mathbb{Z}$에 대하여 $e^{j\theta} = e^{j(\theta+2\pi)} =e^{j(\theta+4\pi)}=\cdots =e^{j(\theta+2\pi n)}$로 $e^{j\theta}$는 periodic하기 때문에 $f(z)$는 무한히 많은 값을 갖습니다: $$f(z)= \ln r + i(\theta+2\pi n), \quad n\in\mathbb{Z}.$$ 따라서 이는 엄밀히 말하여 함수가 아니죠.

문제 풀이


이제 이를 이용하여 위의 문제를 풀어 보겠습니다. 먼저, 복소수 지수 함수의 정의는 다음과 같습니다: $$z^t = e^{t \ln z}=e^{t \ln (re^{j\theta})}, \quad t\in\mathbb{R}.$$ 마찬가지로 복소수 지수 함수 역시 편각 $\theta$에 따라 여러 값을 갖는다는 것을 알 수 있습니다. 그러면 위에서 전개했던 부분  $$1\neq e^{j2\pi t}= (e^{j2\pi})^t= 1^t = 1, \quad t \in \mathbb{R}.$$중에 정확히 어떤 부분이 틀렸던 것일까요? 정답은 가장 마지막 등호입니다. 마지막 등호로 넘어가면서 그전까지는 $\theta=2\pi$이던 것을 은근슬쩍 편각을 0으로 바꾸고 $\theta =0$에 대한 함수값 실수 '1'인양 취급하고 계산한 것입니다. $$1^t=e^{j2\pi t}= (e^{j2\pi})^t \neq (e^{j 0})^t = 1, \quad t \in \mathbb{R}.$$따라서 실수 '1'의 거듭제곱은 $t$에 따라 값이 바뀔 이유가 없지만 복소수 '1'의 거듭제곱은 값이 바뀔 수 있기에 등호가 성립하지 않는 것입니다. 앞서 들었던 예시와 같이 $t=\frac{1}{2}$인 경우를 살펴보시면 이해가 더 빠르실 것입니다: $$(e^{j2\pi})^{1/2}=-1\neq(e^{j 0})^{1/2}= 1.$$

같이 보면 좋을 참고문헌


* https://ghebook.blogspot.com/2012/08/multi-valuedness.html
https://www.youtube.com/watch?v=Q1YonFv6TqM

다음 읽을 거리





2020년 3월 28일 토요일

Signal Processing For Communications (3-2)

지난 글에서는 내적과 거리를 Hilbert 공간으로 확장해보았습니다. 이번 글에서는 bases, subspace, projection에 대해 다루고 Parseval's identity나 Bessel's inequality와 같이 orthonormal bases들이 갖는 유용한 특성을 살펴볼 것입니다. 한가지 재미있는 점은 이 두 특성이 이름은 다 다르지만 사실은 우리가 잘 알고 있는 유클리드 공간에서의 피타고라스 정리가 일반화 된 형태일 따름이라는 것이죠. 

Subspaces and Bases


어떤 공간에 대한 구조를 엿보려면 그 뼈대를 알아야합니다. 벡터 공간에서 이런 뼈대에 해당하는 것이 바로 basis인데요. 우리가 흔히 생각하는 뼈대와는 다르게 이런 수학적 공간에서의 뼈대는 상당히 유연해서, 공간을 망가뜨리지 않고 늘리거나 휘거나 돌리는 등의 변형이 가능합니다. 이를 선형 변환(linear transformation)이라고도 하죠.

이렇게 유연한 성질을 바탕으로, 기존 공간의 성질들을 망가뜨리지 않는 선에서 뼈대를 맘대로 바꾸는 것을 "change of basis"라고 합니다. 이렇게 뼈대를 바꾸는 까닭은 보통 현재의 구조로는 살펴보기가 힘든 정보가 있어서, 이를 좀 더 쉽게 살펴볼 수 있도록 시점을 바꾸기 위해서 입니다. 예를 들면 앞선 글에서 말했었듯 차후 배울 Fourier transform 역시도 대표적인 change of basis 중 하나입니다.

그리고 간혹 벡터 공간 전체가 아닌 좀 더 한정된 공간을 깊게 분석하기 위해 공간의 일부분만을 떼어서 살펴볼 때가 있습니다. 이를 subspace라고 부르는데요. Subspace는 벡터 공간 안에서 허용되는 operation들에 대해 닫혀있는 공간이기 때문에, 마치 샌드박스처럼 해당 공간을 벗어나지 않으면서도 하고 싶은 분석을 할 수 있게 됩니다. 당연하지만 subspace도 공간이기 때문에 자기 자신만의 뼈대를 가지고 있습니다.

그럼 Projection으로 넘어가기 전에 각각의 개념에 대해 좀 더 엄밀히 정의하고 넘어가겠습니다. 먼저 $H(V,S)$는 Hilbert 공간으로 여기서 $V$와 $S$는 각각 벡터 공간과 스칼라 집합입니다.

Subspace. 


$V$에 대한 subspace는 다음과 같은 성질을 만족하는 부분 집합 $P\subseteq V$를 말합니다:
$$\mathbf{x} \in P \text{ and } \mathbf{y}\in P \Rightarrow \mathbf{x}+\mathbf{y}\in P$$ $$\mathbf{x} \in P \text{ and } a\in S \Rightarrow a\mathbf{x}\in P$$ 당연하지만 $V$ 역시도 자기 자신의 subspace입니다.

Span.


임의의 $M$개 벡터 집합 $W=\{\mathbf{x}^{(m)}\}_{m = 0,1,\cdots,M-1}$에 대해
$$\text{span}(W)=\left\{\sum_{m=0}^{M-1}a_m\mathbf{x^{(m)}}\right\}\quad a_m\in S$$ 즉, $W$의 span이라는 것은 $W$에 속하는 벡터들의 모든 가능한 선형 조합을 원소로 갖는 집합입니다. 그리고 $W$의 벡터들이 다음과 같은 성질을 만족하면 서로 "선형 독립"이라 합니다: $$\sum_{m=0}^{M-1}a_m\mathbf{x^{(m)}}=0 \Longleftrightarrow a_m=0\quad \text{for } m=0,1,\cdots,M-1$$

Basis.


이제 앞서 정의한 두 개념을 바탕으로  basis를 정의하면, $P$ subspace에서 뽑은 $K$개 벡터들의 집합 $W=\{\mathbf{x}^{(k)}\}_{k = 0,1,\cdots,K-1}$는 다음과 같은 성질들을 만족할 때 $P$의 basis라고 불립니다:

  • $W$의 원소들이 서로 선형 독립이다.
  • $\text{span}(W)=P.$

두번째 조건은 $W$가 $P$에서 complete하다고 표현하기도 합니다.

Orthogonal/Orthonormal Basis.


Subspace $P$의 orthonormal basis는 다음과 같은 $K$개의 벡터 집합을 말합니다:
$$\langle \mathbf{x^{(i)}},\mathbf{x^{(j)}}\rangle = \delta[i-j] \quad 0\leq i,j<K$$ 벡터가 서로 orthogonal하지만 normal하지는 않을 수도 있는데 사실 서로 선형 독립이기만 하면 Gramm-Schmitt로 언제나 orthonormal하게 만들 수 있기 때문에 별 문제 될 것은 없습니다.

Orthonormal 벡터가 특별한 이유는 $N$-차원 subspace 안에서 얻은 $N$개의 벡터가 서로 orthonormal하면 곧 그 벡터들의 집합이 subspace의 basis라는 특징이 있기 때문입니다. 즉, 유한 차원에서는 모든 orthonormal 벡터들을 찾는 순간, 언제나 그 집합이 해당 공간을 span한다고 얘기할 수 있다는 뜻이죠.

Properties of Orthonormal Bases  


이제 Projection에 대해 설명하기 위한 재료들이 모두 소개가 끝났습니다. $P$ subspace의 orthonormal basis 집합 $W=\{\mathbf{x}^{(k)}\}_{k = 0,1,\cdots,K-1}$는 다음과 같은 성질들을 만족하는데요. 이들을 소개하면서 projection도 간단히 살펴보도록 하겠습니다.

Synthesis and Analysis Formula.


$\mathbf{y}\in P$는 아래와 같이 basis $W$의 선형 조합으로 표현할 수 있고 $$y=\sum_{k=0}^{K-1}a_k\mathbf{x}^{(k)}$$ 여기서 $a_k$는 각 basis 벡터에 대응하는 coefficient입니다. 이 때, 위 식을 일반적으로 synthesis formula라 하며 $a_k$ coefficient들은 *Fourier coefficient라 불립니다.

* Fourier coefficients라 하면 Fourier series에 대한 coefficients를 말하는 경우가 많지만,  사실 일반적으로 임의의 orthonormal basis에 대한 coefficients을 칭하는 말이기도 합니다. 

여기서 synthesis formula라고 부르는 까닭은 basis 집합과 각 basis에 대응하는 coefficent들이 있을 때 원래 신호 혹은 vector를 "만들어내는" 식이라고 생각할 수 있기 때문이죠. 한편, 해당 Fourier coefficients를 찾는 방법은 아래와 같으며: $$a_k = \langle\mathbf{x}^{(k)}, \mathbf{y}\rangle$$ 이를 synthesis formula에 대응하여 analysis formula라고 부릅니다. Fourier basis로 expansion 했을 때를 생각해보시면 신호의 주파수 성분들을 "찾거나 분석"한다고 생각할 수 있으므로 이렇게 이름을 붙이는게 자연스럽습니다.

Parseval's Identity.


Orthonormal basis들은 다음과 같은 norm conservation 성질을 만족하는데요:
$$||\mathbf{y}||^2=\sum_{k=0}^{K-1}\left| \langle\mathbf{x}^{(k)}, \mathbf{y}\rangle \right|^2.$$ 이를 물리적인 값으로 표현하자면 에너지를 뜻한다고도 생각할 수 있고, 따라서 Parseval's Identity는 에너지 보존 법칙이라고도 알려져 있습니다.

혹은! 피타고라스 정리이기도 하죠. 위 식이 2차원일 때를 생각해보시면 됩니다. 좌표평면에 두 좌표축(basis)의 coefficient 값들은 내적으로 계산되고 이렇게 직교하는 좌표축에 대해 각 좌표값의 제곱의 합은 빗변의 길이인 벡터 $y$의 길이의 제곱과 같다고 말하고 있습니다.
피타고라스 정리이지요!

Bessel's Inequality.


Parseval's equality를 한 번 더 일반화한 형태가 바로 Bessel's Inequality입니다. subspace $P$에서 $L$ 개의 orthonormal 벡터 집합 $G\subset P$, $G=\{\mathbf{g}^{(l)}\}_{l=0,1,\cdots,L-1}$에 대해 언제나 다음이 성립합니다:
$$||\mathbf{y}||^2 \geq \sum_{l=0}^{L-1}\left| \langle\mathbf{g}^{(l)}, \mathbf{y}\rangle \right|^2.$$ 여기서 lower bound는 $G$가 $P$에서 complete할 때 입니다 ($\text{span}(G)=P$).

Best Approximations (Projections).


Hilbert 공간에서 orthogonal basis가 중요한 이유 중 하나는, Hilbert projection theorem에 의해 가장 optimal한 approximation이 orthogonal projected vector로 유일하기 때문입니다. 즉, $P$가 $V$의 subspace이고 $\mathbf{y}\in V$에 대해 $P$에서 이에 가장 가까운 벡터를 찾기 위해서는 least squares appoximation과 orthogonal projections에 대한 개념이 필요합니다. 먼저 "가장 좋은" approximation을 $||\mathbf{y}-\mathbf{\hat{y}}||$가 최소가 되는 $\mathbf{\hat{y}}$라고 정의할 때, 아래 그림과 같이 간단히  $\mathbf{y}$를 $P$의 orthonormal basis에 project하는 것으로 얻을 수 있습니다.

여기서 projection은 아래와 같이 정의됩니다: $$||\mathbf{y}||^2 =\sum_{k=0}^{K-1} \langle\mathbf{x}^{(k)}, \mathbf{y}\rangle \mathbf{x}^{(k)}$$ 근사에 대한 error를 벡터 $\mathbf{d}=\mathbf{y}-\hat{\mathbf{y}}$라고 정의하면, $\mathbf{d}\perp\hat{\mathbf{y}}$이며, 위와 같은 방식이 error square norm을 최소화한다는 것을 알 수 있습니다.  $$\arg\min_{\hat{\mathbf{y}}\in P}||\mathbf{y}-\hat{\mathbf{y}}||_2 = \sum_{k=0}^{K-1} \langle\mathbf{x}^{(k)}, \mathbf{y}\rangle \mathbf{x}^{(k)}.$$

Examples of Bases


Finite Euclidean Spaces


$\mathbb{C}^N$과 같은 가장 간단한 Hilbert 공간에서는 orthonormal bases를 찾는 것이 매우 쉽습니다. 가장 클래식한 것이 canonical basis $\{\mathbf{\delta}^{(k)}\}_{k=0,\cdots,N-1}$이죠: $$\mathbf{\delta}_n^{(k)}=\delta[n-k]=\begin{cases}1 \quad\text{if } n=k \\ 0 \quad\text{otherwise}\end{cases}$$ 여기서는 analysis와 synthesis formula도 매우 간단한데요.

먼저 orthononal 벡터 $N$개 $\{\mathbf{x}^{(k)}\}$의 *conjugate 벡터를 행으로 쌓아 $N\times N$ 행렬 $M$을 만듭니다. 이 때, $m$번째 basis에 대한 $n$번째 원소는 다음과 같이 표현될 수 있는데요:  $$M_{mn}=\left(\mathbf{x}_n^{(m)}\right)^*$$ 이런 행렬 $M$을 change of basis 행렬이라고 부르고, 이제 이를 이용하여  syntheis formula와 analysis formula를 표현할 수 있습니다. 즉, $\mathbf{y}$가 주어졌을 때,  $\{\mathbf{a_k}\}_{k=0,\cdots,N-1}$은 coefficient 벡터 $\mathbf{a}\in \mathbb{C}^N$로 표현할 수 있으므로,  synthesis formula와 analysis formula는 각각 다음과 같습니다: $$\mathbf{y} = M^H\mathbf{a}$$$$\mathbf{a} = M\mathbf{y}.$$ * 사실 conjugate가 아니라도 전혀 상관없고 똑같은 결과를 만들 수 있지만 굳이 이렇게 한 이유는 다음 챕터에서 다룰 Discrete Fourier Transform가 같은 형태를 만들어 연관성을 보여주기 위함입니다. 

Haar basis


좀 더 재미있는 예시가 무엇이 있을까 생각해보다가 Haar basis를 가져와 봤습니다. 매우 간단하게 생겼지만 Haar basis는 Wavelet analysis의 시금석이라고도 할 수 있는 중요한 신호처리 도구 중 하나입니다. $\mathbb{C}^8$ 공간에서의 예시를 보자면 다음과 같이 Haar basis에 대한 change of basis 행렬을 만들 수 있습니다.
$$ H = \begin{bmatrix}
1&-1&0&0&0&0&0&0 \\
0&0&1&-1&0&0&0&0 \\
0&0&0&0&1&-1&0&0 \\
0&0&0&0&0&0&1&-1 \\
1&1&-1&-1&0&0&0&0 \\
0&0&0&0&1&1&-1&-1\\
1&1&1&1&-1&-1&-1&-1\\
1&1&1&1&1&1&1&1
\end{bmatrix}
$$
$H$의 각 행이 모두 선형 독립이라는 것은 쉽게 알 수 있죠. 따라서 각 행이 basis를 이룬다는 것은 간단히 증명되었습니다. 그리고 $HH^H$이 diagonal 행렬이란 것도 계산해보면 쉽게 알 수 있습니다. 즉, 각 행들이 서로 orthogonal하다는 것도 알 수 있습니다.

이제 이 녀석이 갖는 재미있는 성질을 약간 엿보고 싶다면 다음과 같이 간단한 예시들을 확인해보면 됩니다. 먼저 $\mathbf{y}=[1, 1,  \cdots, 1]^H$이라는 상수 신호를 Haar basis로 분해해보겠습니다: $$H\mathbf{y} = [0, 0, 0, 0, 0, 0, 0, 8] ^H$$이라는 것을 매우 간단히 알 수 있습니다. 그럼 $\mathbf{y}=[1, -1,  \cdots, 1,-1]^H$과 같이 부호가 교차되는 신호는 어떻게 될까요? 손으로도 쉽게 계산해볼 수 있지만 답을 알려드리자면, $$H\mathbf{y} = [2, 2, 2, 2, 0, 0, 0, 0]^H$$으로 표현이 가능합니다. 즉, 상수 신호의 경우는 마지막 basis만으로도 표현이 가능하고 부호가 교차하는 경우도 4개의 basis들만으로 표현이 가능합니다. 즉, Haar basis를 사용하면 매우 적은 수의 coefficient 조합으로 신호를 표현하는 것이 가능하다는 뜻입니다. 이런 성질을 바탕으로 다양한 이미지 분석 방법들이 개발되어 왔습니다.

마치며...


이제 드디어 도구들이 모두 준비가 끝났습니다. 지금까지 이런 도구들을 배우는 이유를 한 번 짧게 정리해보자면 다음과 같습니다.

먼저 Hilbert 공간에 대해 살펴봤었는데요. 지금까지 살펴본 유한 차원 신호들이나 periodic 신호들은 모두 $\mathbb{C}^N$에 포함되고 우리가 관심이 있을만한 무한 차원 신호들은 모두 $L_2$ 혹은 $\ell_2$에 포함됩니다. 이들은 모두 Hilbert 공간이기에 이를 알면 신호처리 전반을 하나의 통일된 관점에서 이해할 수 있게 되고, 따라서 매우 강력한 도구라 할 수 있습니다.

둘째로 orthogonal basis에 대해 다뤘는데요. 이들이 여러 종류가 있을 수 있음을 알 수 있고 basis 각각이 갖는 특성에 따라 같은 신호를 서로 다른 관점들로 분석하는 것이 가능하다는 것을 알 수 있었습니다. 이런 이해는 뒤에 있을 Fourier transform을 이해하는데 도움이 될 것입니다.

마지막으로 subspace projection과 approximation을 보았는데, 이는 신호를 filtering하거나 이미지를 압축하는 것을 이해할 때 사용할 도구입니다.

다음 글부터는 본격적으로 신호처리에 관련된 얘기들을 다루게 될 것입니다. 푸리에 해석(Fourier Anaylsis)이라고 불리는 다음 쳅터는 신호처리에서 매우 중요한 내용을 담고 있으니 꼭 이해하고 넘어가는 것이 좋습니다. 이름이 매우 무서워 보이지만 지금까지 다룬 기초 개념들을 잘 숙지하셨다면 매우 쉽게 이해하실 수 있을것이라 장담합니다. 제가 그렇게 되도록 도와드리겠습니다.

그럼 다음 글에서 뵙겠습니다.

To be continued ... (planned)





2020년 3월 21일 토요일

Signal Processing For Communications (3-1)

Signals and Hilbert Spaces


17세기 이후, 데카르트가 기하적인 구조를 대수적인 형태로 표현하는 방법을 제안하면서부터 대수 (algebra)와 기하(geometry) 분야가 서로 영향을 주고 받으며 엄청나게 발전했습니다.

대표적인 예로 기원전부터 연구되었지만 풀지 못했던 임의 각의 3등분 문제는 3차 방정식의 유리수 해가 존재하지 않는 것을 보이는 것으로 불가능하다는 것이 쉽게 증명되었습니다. 저도 수능 시험을 볼 때, 도형 문제를 좌표계로 표현해서 쉽게 풀었던 경험이 있습니다.

반대로 대수적인 방법으로는 풀기 어려운 문제를 기하적인 직관을 바탕으로 쉽게 이해하거나 풀 수 있는 경우도 많습니다. 예를 들어 거리라던가 직교라는 개념은 대수적인 해석보다는 기하적으로 이해할 때 좀 더 빠르고 쉽게 받아들일 수 있습니다.

하지만 3차원을 넘어서서 4차원, 더 나아가 무한 차원으로 확장했을 때도 우리가 직관적으로 알고 있는 공간에 대한 개념들을 그대로 적용해도 아무 문제가 없을까요? 과연 무한 차원 공간에서도 거리나 직교라는 기하학적인 개념이 우리가 알고 있는 방식으로 동작할지를 생각해보면, 이 부분이 생각보다 명확하지 않다는 것을 알 수 있습니다.

실제로 공간의 차원이 고차원으로 올라갈수록 우리의 직관이 우리를 배신하는 경우가 많기 때문에 주의해야합니다. 예를 들면, 박스 안에 공을 넣었는데 넣고 보니 박스 안에 들어간 공의 지름이 박스보다 커진다거나 (예시1), 분명 찰흙을 뭉쳐 속이 꽉 찬 공을 만들었는데 만들고 보니 무게가 모두 껍질 쪽에 몰려서 마치 비눗방울처럼 바뀐다거나 (예시2) 하는 황당한 상황들을 흔히 볼 수 있죠.

이와 같이 고차원 공간에서는 인간의 직관이 공간에 대해 제대로 이해하는 것을 오히려 방해하는 경우가 생깁니다. 하지만 그렇다고 우리가 태어나서부터 가지고 있던 편한 도구를 버리기에는 너무 아깝죠. 그렇기에 공간에 대한 우리의 직관적인 이해를 무한 차원에서도 그대로 확장해도 문제가 없기 위해서는 좀 더 엄밀하고 구체적인 제약을 지닌 공간이 필요할텐데요. 그런 공간을 만들기 위해 고안된 것이 바로 Hilbert space입니다.

신호 처리 공부하다가 뜬금없이 웬 해석학이냐고 할 수도 있지만, 이 부분이 신호 처리를 이해하는데 매우 좋은 도구가 된다는 것은 차차 자명해질 것입니다. 잠깐만 부연하자면, 이전 글에서 얘기했던 바와 같이 우리는 discrete-time 신호가 벡터의 형태로 표현이 가능하다는 것을 알고 있습니다. 이렇게 신호가 벡터로 표현되는 순간, 선형대수학이나 미적분학에서 개발된 강력한 도구들을 사용할 수 있게 되는데요. 이에 더해 이 신호가 Hilbert 공간 안에 있다는 것이 보장되면, 길이가 유한한 신호이든 함수와 같은 무한한 신호이든 상관없이 우리가 익숙하고 편하게 알고 있던 기하학적인 도구들을 문제없이 그대로 사용할 수 있게 됩니다.

예를 들어 2차원이나 3차원에서 사용하던 피타고라스 정리나 평행 4변형의 법칙과 같은 개념이 자연스럽게 확장되는 것이죠. 따라서, Hilbert 공간에서는 유한한 길이의 벡터 뿐만 아니라 무한한 길이의 벡터에 대한 추상적인 분석과 finite lenght 신호 대한 분석을 같은 관점에서 매끄럽게 설명할 수가 있게 됩니다.

여기까지 Hilbert 공간이 신호처리에서 중요한 이유를 살짝 소개해드렸는데요. 더 구체적인 내용은 먼저 우리에게 익숙한 유한 차원 유클리드 공간(Euclidean space)를 바탕으로 여러 개념들을 소개하고 이를 무한 차원 Hilbert 공간으로 확장해가면서 살펴보겠습니다.

Euclidean geometry


유클리드 기하는 우리가 태어나서부터 자연스럽게 갖고 있는 공간 감각과 매우 잘 맞아 떨어지는 면이 많습니다. 예를 들어 $\mathbb{R}^2$ 공간은 "평면"에 대한 경험과 대응되고 $\mathbb{R}^3$는 우리가 살고 있는 "공간"에 대한 이해로 자연스럽게 이어집니다. 여기서는 "거리"에 대한 개념도 매우 명백하고 "직교"한다는 것도 어떤 이미지인지 매우 명확하게 그릴 수 있습니다. 심지어 "기저 (basis)"와 같이 매우 추상적인 개념조차도 위도나 경도 높이와 같은 개념으로 치환하여 직관적인 이해하는 것이 가능하죠.

물론 앞서 말했듯이 고차원으로 갈수록 여러 문제가 생길 수 있다지만, 최소한 $N$ 차원으로 유한한 유클리드 공간에서는 여러가지 추상적인 개념을 우리가 익숙한 2차원 혹은 3차원으로 내려서 생각해도 문제가 없기 때문에, 여기서 먼저 복잡한 개념들을 소개하고 충분히 이해하는 것에 의미가 있습니다.

Vectors and Notation.


$\mathbb{R}^N$ 공간의 한 점은 $N$-tuple 좌표 형태로 나타낼 수 있습니다:
$$\mathbf{x} = [x_0, x_1, \cdots, x_{N-1}]^T.$$
우리는 이 것을 벡터라고 부르고 이 좌표는 "standard" 직교 기저들로 표현이 됩니다. 

Inner Product.


두 벡터 $\mathbf{x},\mathbf{y\in \mathbb{R}^N}$ 간의 내적은 다음과 같이 정의 됩니다. 
$$\langle \mathbf{x},\mathbf{y}\rangle=\sum^{N-1}_{n=0}x_n y_n$$
이 때 두 벡터의 내적이 0인 경우 우리는 이 두 벡터가 서로 직교한다고 말합니다.
$$\mathbf{x}\perp \mathbf{y} \Longleftrightarrow \langle \mathbf{x},\mathbf{y}\rangle=0$$

Norm.


벡터의 norm은 그 벡터의 길이를 나타냅니다. 보통 벡터의 norm은 내적으로 정의가 되는데 (induced) 기하적으로 생각하면 이해하기 매우 쉽습니다. (원점에서 벡터를 표현하는 좌표까지의 거리). 
$$||\mathbf{x}||_2=\sqrt{\sum^{N-1}_{n=0}x_n^2}=\langle \mathbf{x},\mathbf{x}\rangle^{1/2}$$

Distance.


위에서 정의한 norm은 자연스럽게 두 벡터 간의 유클리디안 거리를 정의하는데 사용됩니다. 
$$ d(\mathbf{x},\mathbf{y})=||\mathbf{x}-\mathbf{y}||_2=\sqrt{\sum^{N-1}_{n=0}(x_n-y_n)^2}$$

Bases.


$\mathbb{R}^N$에 대해 $N$개의 linear independent 벡터들을 골랐을 때: $\{\mathbf{x^{(k)}}\}_{k=0,\cdots,N-1}$, 이를 bases라고 부릅니다. 즉, 이 벡터들의 선형결합으로 임의의 $\mathbf{z}\in\mathbb{R}^N$와 $a_k\in \mathbb{R}$에 대해 다음과 같이 표현할 수 있다는 뜻입니다: 
$$\mathbf{z}=\sum^{N-1}_{k=0}a_k\mathbf{x}^{(k)}$$
이러한 bases들 중에 서로 직교하고 norm이 1인 녀석들을 orthonormal bases $\{\mathbf{y^{(k)}}\}_{k=0,\cdots,N-1}$라고 부릅니다: 
$$\langle \mathbf{y}^{(k)},\mathbf{y}^{(h)}\rangle=\begin{cases}1 \quad\text{if } k=h \\ 0 \quad\text{otherwise}\end{cases}$$
그리고 이러한 bases 중 가장 "기본적인(standard)" 녀석이라 하여 $\mathbb{R}^N$에 대해 다음과 같은 bases를 canonical bases $\{\mathbf{\delta}^{(k)}\}_{k=0,\cdots,N-1}$라 부릅니다:
$$\mathbf{\delta}_n^{(k)}=\delta[n-k]=\begin{cases}1 \quad\text{if } n=k \\ 0 \quad\text{otherwise}\end{cases}$$
이 bases가 orthonormal하다는 것은 매우 자명하죠. 이런 종류 중 또 다른 중요한 녀석이 있는데요. 바로 Fourier bases $\{\mathbf{w}^{(k)}\}_{k=0,\cdots,N-1}$ 입니다:
$$\mathbf{w}_n^{(k)}=\frac{1}{\sqrt{N}}e^{-j\frac{2\pi}{N}nk}$$
이 녀석에 대한 내용은 orthonormality 증명과 함께 나중 챕터에서 다룰 것입니다. 여기서 가져가실 점은 Fourier bases도 일종의 좌표축들이고 임의의 $\mathbf{x}\in\mathbb{R}^N$에 대해 이를 canonical 좌표계로 표현할 수도 있지만, Fourier 좌표로도 표현할 수도 있다는 점입니다. 다만 좌표축이 변한만큼 좌표값도 바뀌겠죠.

이렇게 하나의 좌표축으로 표현된 어떤 벡터를 다른 좌표축으로 바꿔 표현하는 것을 벡터에 대한 좌표축 "변환 (transform)"을 수행한다고 얘기합니다. 즉, Fourier transform은 별게 아니라 임의의 벡터를 Fourier bases로 좌표축을 바꿔서 표현하는 방법임을 알 수 있습니다.

눈치가 빠르신 분들은 이미 여기서부터 어째서 신호처리 개념들을 기하적으로 생각하는 것이 개념을 이해하는데 도움이 되는지 알 수 있으실거라 생각합니다. 그저 대수적인 표현 방식으로만 Fourier transform을 이해하려고 하면 적분과 복잡한 수식으로 이루어진 형태에 그 뒤에 숨어있는 뜻을 알기가 쉽지 않지만, 위와 같은 관점에서 보면 결국 Fourier transform은 그저 좌표축 치환하는 여러가지 방법 중 하나일 뿐이라는 것을 알 수 있죠. 적분은 차후 보시겠지만 내적의 일반적인 표현일 따름이구요.

From Vector Spaces to Hilbert Spaces


이제 앞서 얻은 유한 차원 유클리드 공간에 대한 이해를 바탕으로 무한 차원 Hilbert 공간으로 개념들을 확장해보겠습니다. 그런데 애초에 우리가 편하게 다룰 수 있는 유한 차원 공간에서 굳이 무한한 차원으로 넘어가야 하는 이유가 뭘까요?

두루뭉술하게 이렇게 일반화를 한 형태가 이론적으로 분석하거나 다루기가 더 쉽기 때문에 이론적인 발전을 위해서는 이런 확장이 필연적이었을 것이라 설명할 수도 있겠습니다만, 좀 더 구체적으로 그렇게 하지 않았을 때 어떤 문제가 생기는지를 보는게 더 이해가 쉽겠습니다.

일단 자연에 존재하는 신호가 굳이 discrete하고 유한한 값만을 가질 이유가 없다는 것은 동의하실겁니다. 곰곰히 생각해보면 임의의 신호가 굳이 유한한 차원 안에서 표현되야 한다는 것이 오히려 더 큰 제약이죠. 예를 들어 임의의 continuous 함수 $f: \mathbb{R}\rightarrow \mathbb{R}$는 모두 무한 차원 벡터로 표현될 수 있습니다. 그럼 이런 신호를 다루기 위해서 우리에게 익숙한 유한 차원 유클리드 공간 $\mathbb{R}^N$이나 $\mathbb{C}^N$을 적용하되 단순하게 $N$을 무한하게 키워서 사용하면 어떻게 될까요?

음... 당장 내적이나 norm부터 문제가 생기는군요. 예를 들어 모든 값이 1로 일정한 무한 수열과 같이 매우 단순한 수열을 생각해보시면 내적이나 norm 값들이 발산한다는 것을 쉽게 알 수 있습니다. 이렇듯 단순하게 공간을 확장해보면 우리가 알던 도구들이 잘 정의되지 않아서 신호를 다루기가 쉽지 않아집니다.

그래서 이런 도구들이 제대로 기능하면서도 위와 같은 문제가 없도록 벡터 공간에 적절한 제약을 걸어 일반화한 공간이 Hilbert space입니다. 이 제약을 신호처리에 가까운 언어로 간단히 표현하면, finite energy를 가지는 벡터들만이 Hilbert space의 원소가 되도록 제약을 걸었다고 생각할 수 있습니다.

이를 조금만 더 엄밀하게 얘기해보면 다음과 같습니다:

벡터 집합 $V$와 스칼라 집합 $S$에 대해, 간단한 사칙연산과 null vector 등이 정의된 벡터 공간 $H(V,S)$에 내적이 추가로 구비된 공간을 Inner Product Space라고 부릅니다. Hilbert 공간은 여기에 더해 "completeness"를 추가로 요구하는데요. (Hilbert 공간 = complete inner product space). 한국어로는 완비성이라고 부르는 이 개념은 $H(V,S)$ 공간의 코시 수열(Cauchy sequence)이 수렴할 때, 그 극한에 해당하는 벡터 역시도 같은 공간 $H(V,S)$ 안에 존재한다는 말입니다.  결국 completeness의 정의를 조금 생각해보면 Hilbert 공간이 구멍이 없이 꽉 차있다는 얘기입니다. (조밀성과는 다릅니다.)

음....사실 저는 처음 이런 추상적인 개념이 도대체 신호를 다룰 때 어째서 중요한지 아무도 알려주는 사람이 없어서 도무지 이해하기 어려웠습니다. 그냥 그런가보다 하고 넘어가기에는 답답해 하다가 찾은 나름의 답은 다음과 같습니다.

다시 무한한 support를 갖는 신호를 다루는 입장에서 생각해보겠습니다. 이 신호를 표현하기 위해 앞서 배웠던 유클리드 공간의 basis에 관한 내용을 확장해보면 다음과 같은데요: $$\mathbf{z}=\sum^{\infty}_{k=0}a_k\mathbf{x}^{(k)},\quad \mathbf{x}^{(k)},\mathbf{z}\in\mathbb{R}^\infty, a_k\in \mathbb{R}.$$ 즉, 임의의 신호에 대해 무한 개의, 무한 차원 basis들의 선형 결합으로 표현할 수 있다는 뜻이 됩니다.

문제는 일단 무한 차원의 벡터들에 대한 무한 합이라는 것부터 잘 정의가 될지부터 잘 감이 오지 않죠. 사실 이것이 가능하다는 것을 보여준 것이 Fourier series입니다. 언젠가 더 자세히 소개할 날이 오겠지만 Fourier의 업적 중 하나인 Fourier series는 임의의 함수를 무한 개의 sinusoidal basis 함수들의 합으로 표현이 가능하다는 것을 보여줍니다. 즉, 수렴합니다.

이 때, "신호"란 실제로 물질적인 세상(공간)에 존재하는 신호들로서 어떤 물리적인 조건(예: finite energy)들을 만족할텐데요. 어떤 신호가 이런 공간 내에 존재하지 않는다는 말은, 해당 신호가 물리적인 조건을 만족하지 않아 제대로 된 신호가 아니라고 이해할 수 있겠습니다.

그런데 만약 이런 basis들의 무한 합으로 신호를 표현하고 보니 그 합이 수렴하는 신호가 물질적인 세상을 벗어나 버린다면, 즉, 그 수렴 결과가 의미가 없는 신호라면 (혹은 또 다른 말로 해당 공간이 완비성이 보장되지 않는다면), 이 공간 안에서는 신호를 다루기가 까다로워집니다.

결국 Hilbert 공간 안에서는 벡터를 가지고 아주 이상한 짓을 하지 않는한 웬만해서는 어떤 연산을 하든 이 공간 안에서만 놀 수 있기 때문에 "좋은" 공간이라고 생각하시면 됩니다.

Hilbert space의 예시


결국 이런 좋은 성질들과 제약 덕분에, 이미 소개한 것 처럼 Hilbert 공간은 *함수들도 원소로 갖을 수 있는데요. 예를 들어 다음과 같은 녀석들이 있습니다:
(* 여기서 더 나아가는 것은 함수 해석학에서 배울 내용이니 여기서는 그런 것이 있다고만 알고 넘어가시면 됩니다. 단, 뒤에서도 유용하게 쓰일 녀석을 하나만 소개하자면 이전 글에서도 잠깐 언급되었었던 "the space of square integrable functions" 인데요. 이는 차후 continuous와 discrete-time 신호들 간의 관계를 보여줄 때 유용하게 사용될 것입니다.) 

Finite Euclidean Spaces.

유한한 $N$에 대해 내적이 $\langle \mathbf{x},\mathbf{y}\rangle=\sum^{N-1}_{n=0}x_n ^*y_n$으로 정의된 벡터 공간 $\mathbb{C}^N$은 Hilbert space입니다.

Polynomial Functions. 

functional Hilbert space의 한 예시로써 $[0,1]$ 구간에서 정의된 maximum degree가 $N$인 polynomial 함수들의 공간 $\mathbb{P}_N([0,1])$이 있습니다.

Square Summable Functions. 

또 다른 functional Hilbert space 예시로 square integrable functions이되 유한한 구간에서 정의된 square summable functions 공간이 있습니다. 예를 들어, $L_2([-1,1])$는 finite norm을 가지고 구간 $[-\pi,\pi]$에서 정의된 공간으로서 내적은 아래와 같이 정의됩니다:
$$\langle f,g \rangle = \int_{-1}^1 f^*(t)g(t)dt.$$
따라서 $f(t)$의 norm은 자연스럽게
$$||f(t)|| = \sqrt{\int_{-1}^1 |f(t)|^2dt}$$
로 정의되며 $L_2([-1,1])$에 속하는 $f(t)$는 모두 $||f||<\infty$를 만족해야합니다.

Inner Products and Distances


이제 앞서 유클리드 공간에서 소개했던 개념들을 하나씩 확장해보겠습니다.

먼저 내적을 조금 더 살펴보죠. 내적은 벡터 공간에서 벡터간의 "거리"라는 개념을 표현할 때 필수적인 요소입니다. 이를 이해할 때 기하적인 접근을 하면 훨씬 받아들이기가 쉬운데요. 예를 들어 $\mathbb{R}^N$ 유클리드 공간에서 $\mathbf{x}$ 벡터와 $\mathbf{y}$ 벡터가 있을 때 둘의 내적 $\langle \mathbf{x},\mathbf{y}\rangle$은 $\mathbf{y}$를 $\mathbf{x}$에 대해 orthogonal projection한 값이라고 할 수 있습니다.

정사영을 생각해보면 orthogonal projection이 $\mathbf{x}$의 점 중 $\mathbf{y}$에 가장 가까운 점을 찾는 방법임을 쉽게 알 수 있습니다.
$$\langle \mathbf{x},\mathbf{y}\rangle=||\mathbf{x}|| ||\mathbf{y}|| \cos\theta$$
여기서 $\theta$는 두 벡터 사이의 각도인데, 각도가 90도가 되면 cos 값이 0이 되면서 내적도 0이 되죠. 따라서 이런 관점에서, 내적은 두 벡터 간의 각도 차(혹은 두 벡터가 이루는 모양의 차이)를 바탕으로 유사도를 측정하는 방법이라 할 수 있습니다.

이런 내적은 신호처리에서 마주할 수 있는 다양한 상황에서 사용되는데요. 우리가 알고 싶은 내용에 따라 다른 이름으로 불리곤 합니다. 여러 신호 중 특정 신호를 찾고 싶을 때는 correlation이라는 용어로 사용되기도 하고, 신호를 바꾸거나 다른 신호로 근사하고 싶을 때는 filtering이라고 부르는데, 결국에는 모두 다 내적을 사용하여 두 신호 혹은 벡터 간의 유사성을 정량적으로 측정하는 것입니다.

위와 같은 맥락으로 이해하면 신호들 간에 orthogonality는 자연스럽게 두 신호가 완벽하게 구별이 가능하다는 뜻으로 이해할 수 있게됩니다. 즉, 두 신호의 생김새가 완전히 다른 것이죠.

이렇듯 유사성을 정량적으로 측정하기 위해 *내적으로부터 "거리"라는 개념이 나오고 우리가 잘 아는 유클리디안 거리가 나오는 것입니다.
$$ d(\mathbf{x},\mathbf{y})=\langle\mathbf{x}-\mathbf{y},\mathbf{x}-\mathbf{y}\rangle^{1/2}=||\mathbf{x}-\mathbf{y}||$$ 신호처리 분야에서는 이런 유클리디안 거리를 "root mean square error"라고 부르고 $\mathbf{y}$를 $\mathbf{x}$로 근사할 때 전반적인 "goodness of fit"을 정량적으로 측정하는 것에 많이 쓰입니다.
* 물론 여러가지 거리에 대한 정의들 중 내적이랑 관련이 없는 녀석도 있는데요: $ d(\mathbf{x},\mathbf{y})=\max_{0\leq n<N}|\mathbf{x}_n-\mathbf{y}_n|$. 이 녀석은 superemum norm을 바탕으로 정의되는 거리로 $||\mathbf{x}-\mathbf{y}||_\infty$로 표현되기도 합니다. 하지만 이에 대응하는 내적이 없기 때문에 이를 natural norm으로 갖는 Hilbert space는 존재하지 않습니다. 


Hilbert 공간에서는 위와 같이 유클리드 공간에서 자연스럽게 이해가 되는 내적이란 개념을 일반적인 함수에 대해 적용했을 때 아무런 문제 없이 확장이 가능합니다. 예를 들어 $L_2[-1,1]$ 공간에서 내적은 앞서 다음과 같이 정의된다고 말씀드렸었죠: $$\langle f,g \rangle = \int_{-1}^1 f^*(t)g(t)dt.$$ 이런 공간에 있는 함수 중에 다음과 같이 주기가 서로 다른 (즉, 전혀 다르게 "생긴") 두 함수에 대해 내적을 계산해보면 어떻게 될까요? 

재미있게도 이 두 함수가 정의에 따라 서로 orthogonal한 것을 확인할 수 있습니다. 


이를 엄밀하게 계산해볼 수도 있겠지만 위와 같이 간단하게 눈으로 확인해 볼 수도 있습니다. 빨간색으로 표현된 영역과 파란색으로 표현된 영역들이 서로 부호가 다르지만 넓이가 같은 짝이 있어서 서로서로 상쇄되어 결과적으로 적분을 하면 값이 0이 되는 것을 확인할 수 있습니다.

마찬가지로 거리 개념 역시도 확장하여 다음과 같이 나타내고 계산하는 것이 가능합니다: $$||f(t)-g(t)||^2 = \int_{-1}^1 |f(t)-g(t)|^2dt.$$

다음글 Preview


글이 좀 길어졌는데요. 여기서 잠시 끊고 다음 글에서 이어 확장해보도록 하겠습니다.

다음 글에서는 bases와 관련된 개념들을 소개할 것입니다. 여기서는 subspace라든가 projection 그리고 Parseval's identity나 Bessel's inequality와 같이 orthonormal bases들이 갖는 유용한 특성과 그런 bases들이 어떤 것들이 있는지 등을 다룰 것입니다.

한가지 재미있는 점은 이 Parseval's identity나 Bessel's inequality이라 불리는 두 특성이 이름은 서로 다르지만 사실은 우리가 매우 잘 알고 있는 유클리드 공간에서의 피타고라스 정리가 일반화 된 형태일 따름이라는 것이죠.

제가 계속 중간중간 언급을 하여 눈치채셨겠으나 이렇게 좀 기초적인 내용들을 계속 다루는 까닭은 신호처리의 중요한 개념들을 설명할 때 가져다 쓸 기초적인 도구이자 약속이기 때문이기도 하고 이를 바탕으로 좀 더 직관적 이해가 가능하기 때문입니다. 이 장이 익숙하거나 지루하신 분들은 차후 있을 Fourier Analysis 편으로 바로 넘어가셔도 되겠습니다.

그럼 다음 글에서 뵙겠습니다.

같이 읽으면 좋을 참고 문헌


  • http://www.math.lsa.umich.edu/~kesmith/infinite.pdf

To be continued ... (planned)





2019년 12월 21일 토요일

Signal Processing For Communications (2)

이전 글에서 continuous-time과 discrete-time 신호에 대해 짧게 논의했었습니다. 이 장에서는 차후 사용될 기본적인 도구들을 소개하고 discrete-time 신호에 대해 좀 더 자세하게 살펴보겠습니다.

기존의 많은 신호처리 교과서들이 그렇듯이 역사적인 흐름에 따라 소개를 하자면, 먼저 continuous-time 신호를 다루고 나서 discrete-time 신호 그리고 digital 신호를 다루는 것이 순서에 맞을 것입니다. 이에 맞추어 전통적인 관점에서는 discrete-time 신호를 continuous-time 신호의 discrete version으로 생각하기 때문에 sampling을 중요하게 다뤄왔죠.

하지만 요즘 같은 디저털 시대에는 점점 더 sampling보다는 discrete-time 신호를 synthesis하는 것에 더 초점을 맞추어 중요하게 다뤄야할 필요가 있습니다. 이런 관점에서 오히려 역사적 흐름과는 반대로 discrete-time 신호를 중심으로 이야기를 풀어갈 때 훨씬 이해가 쉽다는 것을 차차 느끼실 것이라 생각합니다.

Discrete-Time Signal



앞으로 우리가 다룰 discrete-time signal은 complex-valued sequence입니다. 이는 정수 값을 갖는 인덱스 n에 대한 complex-valued 함수로 표현할 수 있으며, 예를 들어 위 그림에 대한 analytical closed-form은 다음과 같습니다: $$x[n] =((n+5)~\text{mod}~11)-5$$ 이 때, n은 dimensionless time이고 그저 sequence에서의 시간적인 순서를 표현하는 값입니다.

이런 discrete-time signal은 우리 실생활과 매우 밀접하게 연계되어 있는 한편, 우리 인간이 가지고 있는 물리적인 한계를 잘 보여줍니다. 즉, 우리가 어떤 신호를 "보고" 그 값을 아무리 빠르게 "기록"한다고 할지라도 그 사이에는 항상 "받아 적는데 걸리는 시간"이 존재하겠죠.

이와 같이 "받아 적는다"라는 행위가 바로 "sampling" 이고, 이는 아날로그 신호에서 discrete-time 신호를 만들어내는 가장 필수적인 방법입니다.  그렇다면 위와 같은 물리적 한계를 생각할 때 sampling을 하는 과정에서 불가피하게 없어지는 정보들로 인해 우리가 무슨 짓을 해도 신호의 정보를 완벽하게 기록하는 것은 불가능하다는 결론에 이릅니다.

그러면 평소에 우리가 잘만 듣고 있는 라디오나 CD에 녹음된 노래들은 어떻게 이런 한계를 극복한 것일까요? 결론부터 말하자면,
Continuous-time과 discrete-time 세계 사이를 오갈 때 이 사이의 간극으로 인한 정보 손실이 전혀 없이 넘나드는 방법이 있습니다! 

어떤 면에서는 말이 안 되는 것 같은 이 결론이, 바로 우리가 앞으로 신호 처리를 공부할 때 배우게 될 주요 테마입니다. 지금은 전혀 말도 되지 않아보이지만 이에 대한 수학적 증명은 sampling tehorem을 공부할 때 알게 될 것입니다. 그 장에 이르기까지 좀 더 도구를 갖춰야 엄밀하게 이해할 수 있겠으나 저 같이 성질이 급한 분은 저번 글을 통해 조금이나마 그 과정을 엿볼 수 있었을 것이라 생각합니다.

어찌 되었건 이 사실을 받아들이고 넘어가면, discrete-time 신호가 갖는 강력한 장점 하나를 알 수 있습니다. 어떻게든 discrete-time 세계로 신호를 넘기고 나면, 이 후부터는 "측정 간의 시간"이라는 개념 자체가 사라진다는 점입니다. 즉, 우리가 가진 신호는 그저 값들이 나열된 순서가 있는 수열일 따름이고, 그렇기 때문에 신호를 어떻게 얻었는가와 전혀 상관이 없어진다는 것입니다. 이 부분이 바로 매번 시스템과 신호의 물리적인 성질을 고려해야 하는 아날로그 세계와는 크게 다른 discrete 세계의 장점이 되겠습니다. (같은 얘기에 대한 좀 더 자세한 예시는 이전 글을 참고해주세요.)

Elementary Operators


Sampling 된 신호를 가지고 여러가지 계산을 수행할 수 있을텐데, 여기서는 몇몇 기본적인 계산에 대해 소개하겠습니다. 매우 지루한 부분이지만 나중에 사용된 필터 부분의 기본적인 배경이 되기 때문에 꼭 알아야 할 중요한 개념이기도 합니다.

Shift. 


수열 $x[n]$를 정수 k만큼 shift하는 것은 간단히 $$y[n]=x[n-k]$$라고 표현할 수 있습니다. 여기서 k가 양수이면 오른쪽으로 음수이면 왼쪽으로 신호가 shift되는 것을 알 수 있고, 따라서 delay operator는 $$\cal{D}_k\{x[n]\}= x[n-k]$$라고 표현할 수 있습니다.

Scaling.


수열 $x[n]$를 factor $a\in\mathbb{C}$만큼 scaling하는 것은 $$y[n]=ax[n]$$이라 표현됩니다. 여기서 a가 실수이면 신호의 amplification($a>1$) 혹은 attenuation($a<1$)을 각각 표현할 수 있고 만약 a가 복소수이면 amplification과 attenuation에 더해 phase shift가 추가되었다는 것을 알면 되겠습니다. 


Sum. & Product.


수열 $x[n]$와 수열 $w[n]$을 더하거나 곱하는 것은 elementwise로 수행합니다: $$y[n]=x[n]+w[n], \quad y[n]=x[n]w[n]$$

Integration.


Discrete-time에서의 integration은 다음과 같이 합으로 정의됩니다: $$y[n]=\sum_{k=-\infty}^{n}x[k]$$

Differentiation. 


Discrete-time 신호에 대한 미분은 어떻게 하면 될까요? 미분의 기초적인 정의를 생각해보면 차분의 비율이죠. 하지만 이미 sampling 간격이 정수로 정해져 있는 discrete-time signal에서 continuous-time의 differentiation을 적용하는 것은 맞지 않아보입니다. 따라서 discrete-time에서는 differentiation을 dfference로 근사하여 사용하는데 가장 간단한 *1st order approximation은 다음과 같이 나타낼 수 있습니다:  $$y[n]=x[n] - x[n-1]$$ 예를 들어 Unit step은 discrete-time impulse를 integration operator에 통과시키면 만들 수 있고 반대로 unit step을 differentiation operator에 통과시키면 impluse를 얻을 수 있겠습니다.
* 차후에 "정확한" 근사는 $H(e^{j\omega})=j\omega$라는 filter로 나타내진다는 사실을 배울 것입니다. 하지만 보통 1st order difference만으로도 적용하는 것에는 문제가 없습니다.

The Reproducing Formula


위와 같은 기본적인 operations들에 더하여 앞으로 자주 보게 될 수식을 하나 더 소개하겠습니다. $$x[n]=\sum_{k=-\infty}^\infty x[k]\delta[n-k]$$
즉, 임의의 discrete-time 신호는 shifted impulse들의 선형 결합으로 표현이 가능하다는 것. 이렇게 매우 자명한 식을 굳이 한 번 더 강조하는 까닭은 앞으로 나올 discrete-time signal의 특징들을 얘기할 때 거듭해서 이 식이 자주 보일 것이기 때문입니다. 

Energy and Power


Discrete-time signal의 energy는 다음과 같이 정의됩니다: $$E_x=||x||^2_2=\sum_{n=-\infty}^\infty \left|x[n]\right|^2$$ 이 식에서 바로 알 수 있듯이 에너지는 위 식의 sum이 수렴할 때만 finite하죠. 다른 말로 하자면 $x[n]$이 square-summable 해야지만 에너지가 유한합니다. 이런 성질을 갖는 신호를 finite energy signal이라고 하고 가장 간단한 예시로 주기 함수는 모든 값이 0이 아닌한 square summable하지 않습니다. 이렇듯 신호의 summability는 무한한 길이의 신호를 다룰 때 중요한 성질인데, 여기서 absolute summability는 좀 더 강한 조건이고,  square summability (finite energy)는 그에 비해 좀 더 약한 조건이라고 할 수 있습니다.

이제 energy가 정의되었으니 시간에 대한 energy의 비율로 power를 정의할 수 있습니다: $$P_x=\lim_{N\rightarrow \infty}\frac{1}{2N}\sum^{N-1}_{-N}\left|x[n]\right|^2$$ 유한한 energy를 갖는 신호는 total power가 0이라는 것을 알 수 있습니다. Decay하지 않는 exponential 수열들의 경우는 infinite power를 갖는 것을 알 수 있지만, 주의할 점은 infinite energy를 갖는 모든 신호들이 그러하진 않다는 점입니다. 예를 들어 사인파와 같은 주기 신호의 경우 finite power를 갖는데 이 경우 위 식에서 limit가 잘 정의되지 않으므로 주기가 있는 신호에서는 average energy over a period로 power를 나타냅니다: $$P_x=\frac{1}{N}\sum^{N-1}_{n=0}\left|s[n]\right|^2.$$

Discrete-time 신호의 종류 네 가지


Finite-length signals

앞서도 보았지만 길이 N의 신호를 나타낼 때, 이를 벡터 형태로 표현할 수도 있고: $$x=[x_0, x_1, \cdots, x_{N-1}]^T$$ 다음과 같이 수열로 표현할 수도 있겠습니다: $$x[n], \quad n=0,\cdots,N-1$$ * 벡터로 표현하는 법은 몇몇 신호처리 operation들의 기하적인 성질을 이해할 때 유용할 수 있고, 수열로 표현하는 방법은 대수적인 성질을 표현할 때 유용하게 사용되므로 앞으로도 이 둘을 왔다갔다 하면서 사용하겠습니다. 신호를 벡터로 다루면서 얻을 수 있는 기하학적인 직관은 때로는 훨씬 간단하면서도 쉽게 신호 처리를 배울 수 있도록 도와주기 때문에, 이에 관한 기초적인 도구들은 다음 장에서 더 자세히 다룰 것이고 뒷 장에서도 계속 이 도구들을 이용할 것입니다.

여기서 한 가지 finite-length signal을 다룰 때 염두에 둘 점이 있습니다. $x[n]$이라는 신호가 support 바깥($n<0$ or $n>N-1$)에서는 정의되지 않는다는 것. 이런 경우 "앞서 배웠던 shift 같은 것을 finite length signal에서는 어떻게 정의해야할 것인가?"와 같은 문제가 생깁니다. 따라서 보통은 이런 "border effects"와 같은 문제를 없애기 위해 우리가 얻은 유한한 신호를 적절한 수열에 embedding하여 사용하게 됩니다.

* 대표적으로는 circular shift를 사용하여 finite-length signal을 N-periodic signal로 바꾼다거나 이 대신 support 바깥에 zero padding을 하여 finite-support signal로 바꾸는 방법 등이 있겠습니다. 각각의 방법은 특징이 있는데 그로 인해 생기는 현상도 서로 다릅니다. 예를 들어 circular shift를 사용하는 경우는 shifted sequence와 original signal 간의 equivalence가 존재하지만 zero padding의 경우는 그렇지 않죠. 특히 circular shift의 경우 discrete-time signal의 frequency domain 표현에 대해 배울 때 자연스럽게 등장할 것입니다.

Infinite-length signals: Aperiodic

대부분의 일반적인 discrete-time 신호는 finite할 수밖에 없기 때문에 무한정 긴 심지어 주기가 없는 이런 형태의 신호가 어떤 의미가 있는가 싶을 수 있죠. 하지만 가장 일반화된 형태인만큼 이론적으로 분석하기에는 매우 기본적인 바탕이 됩니다. 

Infinite-length signals: Periodic

주기 N을 갖는 주기 수열은 다음과 같이 표현될 수 있습니다. 
$$\tilde{x}[n] = \tilde{x}[n+kN], \quad k\in \mathbb{Z}.$$
앞으로 주기 수열을 표현할 때는 항상 물결 표시를 쓰도록 하겠습니다. Periodic 수열은 길이는 무한하지만 정보가 유한한 수의 샘플들 안에 모두 포함되어 있다는 점에서 유한 길이의 신호와 무한 길이의 신호 간의 가장 기본적인 다리 역할을 한다고 생각할 수 있습니다. 

그저 길이만 무한한 신호(aperiodic)는 함수와 같이 표현이 가능하므로 수학적인 일반화 혹은 추상화에 도움이 될 수는 있겠지만, 이를 처음부터 다루는 것은 실질적이지도 않고 우리가 저장하거나 다루기가 어렵기 때문에 일반적인 교과 과정에서 주기 함수를 중요하게 다루고 먼저 배우는 것이라고도 생각됩니다.

* Periodic extensions:  주기 수열은 무한한 길이를 갖지만 정보량 자체는 유한하죠. 이런 점을 이용하여 finite-length 신호 $x[n]$을 periodic sequence로 embedding하여 표현할 수 있습니다: 
$$\tilde{x}[n] = x[n~mod~N], \quad n\in \mathbb{Z}.$$
이를 finite-length 신호의 "periodic extension"이라고 부르는데, 주기적인 성질 덕분에 아래 수식에서 볼 수 있듯이 shifted sequence와 original signal 간의 equivalence가 존재합니다. 이를 circular shift라고 합니다. 

Infinite-length signals: Finite-support

무한한 길이를 갖는 또 다른 형태의 신호로는 일정 범위 안에서만 값을 갖고 (finite-support ) 그 밖에서는 모두 값이 0인 신호가 있겠습니다.
$$\exists N,M\in \mathbb{Z},\quad \bar{x}[n] = 0 \quad \text{for } n<M~\text{and } N>M+N-1.$$
쉽게 눈치챌 수 있지만, 이 역시도 finite-length 신호를 무한한 길이를 갖는 신호로 embedding을 할 수 있는 또다른 방법으로써, 앞서와 다른 점은 더이상 shift된 신호가 본 신호와의 equivalence가 없다는 점입니다. 

지금까지 간단하게 우리가 다룰 신호들의 종류와 성질 그리고 각 종류별 신호들 간의 관계들에 대해 알아보았습니다. 이렇게 각각의 신호를 다루는 방식에 대한 자세한 내용은 앞으로 차차 다루게 될 것이므로 여기서는 이런 것들이 있다고만 언급하고 넘어가겠습니다.

그럼 다음 글에서 뵙죠.

To be continued ... (planned)





2019년 7월 15일 월요일

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를 정량적으로 분석하는 방법 중 하나를 살펴보았습니다. 이만큼 공부하고 썼다고 주말이 사라졌네요. 오늘은 그럼 이 정도로 마무리 해야겠습니다. 예제들도 만드려면 만들 수 있는데, 차후 여유가 된다면 추가하는 것으로ㅎㅎ

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


다음 읽을 거리





2019년 5월 20일 월요일

[PR12-Video] 87. Spectral Normalization for Generative Adversarial Networks


TensorFlowKR facebook comunity에서 모인 12명의 paper readers (PR12)가 읽어주는 deep learning papers

#87.Spectral Normalization for Generative Adversarial Networks


이 리뷰에서는 ICLR 2018에 발표된 SNGAN 논문을 리뷰하겠습니다. 즐겁게 들어주시면 감사하겠습니다.




(paper) Spectral Normalization for Generative Adversarial Networks

Paper:  https://openreview.net/forum?id=B1QRgziT-
슬라이드: https://www.slideshare.net/thinkingfactory/pr12-spectral-normalization-for-generative-adversarial-networks

이 발표가 제가 PR12에서 마지막으로 발표한 논문이었네요. 처음 시작할 때는 언제 100회가 끝날까 싶었는데, 새삼 시간이 참 빠르게 흐른다는 생각을 해봅니다. 끝까지 열심히 했는데 다음에도 여유가 된다면 다시 참여하고 싶네요. 지금도 새로운 멤버로 계속되고 있는 것으로 알고 있으니 다른 분들의 발표도 보고 싶다면: PR12 딥러닝 논문읽기 모임 에서 확인하시면 되겠습니다 :)

다음 읽을거리






2019년 5월 17일 금요일

Deep Learning for Super-Resolution: A Survey (1)

Image Super-Resolution(이하 SR)은 컴퓨터 비전 분야의 중요한 갈래 중 하나로 이미지나 비디오의 해상도를 좋게 하는 영상처리 기술을 말합니다. 영화나 미드에서 위성 사진을 바탕으로 계속 확대해보라고 하는 장면이 종종 나오는데요, 이런 클리셰를 너무 많이 써먹은 나머지 아래와 같은 짤방이 만들어질 정도로 우리에게 SR은 꽤나 친숙한 기술입니다.



짤방에서는 비현실적인 예시로 클리셰를 비꼬고 있지만 최근 Deep learning을 이용한 SR 기술들을 보면 우리가 생각하는 것 이상으로 기술이 빠르게 발전하고 있다는 것을 알 수 있습니다.
“Any advanced technology is indistinguishable from magic”.
- Arthur C. Clarke
한 때 잠시 SR을 했었고 다시 또 SR에 관심을 가지게 되면서, 최신 연구 동향을 파악하고 스스로의 공부를 위해 정리 글을 작성해보고자 합니다.

Single Image Super-Resolution 


SR에는 Single Image(SI)를 이용한 방법 외에도 Multiple Images를 이용한 방법들 역시 많이 연구되었으나 이 글에서는 SISR 에서 external-example based methods에 속하며 그 중에서도 deep learning model을 사용한 연구에 집중하여 리뷰합니다. Survey의 형식이기 때문에 세세하게 설명하기 보다는 굵직한 모델들의 컨셉을 소개하고 전체적인 흐름을 위주로 짚어가며, 각 모델들에 대한 자세한 내용은 필요한 경우에 한해서만 다룰 생각입니다 (**).

Single Image Super-Resolution(SISR)은 한 장의 저해상도 이미지(low resolution image, LR)를 가지고 고해상도의 이미지(High resolution image, HR)를 만들어 내는 대표적인 low-level vision 문제입니다. 의료 영상에서부터 감시 카메라 및 보안 영상 등에 다양하게 적용이 가능한 기술이기에 컴퓨터 비전 분야에서 전통적으로 매우 중요하게 다뤄져 왔습니다.

Problem Definition


SISR에서 LR 이미지 $y$에 대한 수학적 모델은 일반적으로 다음과 같이 정의됩니다:
$$y = (x ⊗ k)↓s + n.$$ $x$와 $k$는 각각 우리가 모르는 원본 HR 이미지와 이에 씌워지는 (convolved) degradation or blur kernel입니다. 이렇게 degradation이 일어난 $x$에 $s$만큼 downsampling ($↓s$)되고 system noise $n$가 더해져서 LR image $y$가 얻어진다고 생각할 수 있습니다.

문제는 하나의 LR 이미지 $y$에 대응될 수 있는 HR 이미지 $x$가 매우 다양할 수 있기 때문에 SISR이 대표적인 ill-posed problem라는 점입니다 (**). 전통적으로는 sparsity나 image statistics를 이용한 prior knowledge를 기반으로 문제를 푸는 optimization 방법들이 활발히 연구되어 왔지만, 최근 Deep learning을 적용되면서 분야 전체가 믿기 힘들 정도로 더욱 빠르게 발전하고 있습니다. 단순히 deep network를 적용하는 것뿐만 아니라 전반적인 모델framework부터 데이터 전,후처리 방식, upsampling 방식 등 매우 다양한 방면으로 연구 및 발전이 이루어지고 있는 것을 보실 수 있습니다.
** 전통적인 SISR 방식에 대해 궁금하다면 (이 글)을 참고하시면 됩니다.
** why? 좀 더 자세하게 알고싶다면 (이 글)을 참고하시면 됩니다.


SRCNN: The Start of Deep Learning in SISR


언제나 그렇듯 각 분야마다 deep learning을 처음으로 도입한 cornerstone이 되는 연구가 하나씩 있기 마련인데요 SISR 분야에서 최초로 CNN을 적용한 연구는 SRCNN(Dong et al.)으로 이름도 찬란한 Kaiming He가 저자 중 1인입니다. (이 양반은 안 끼는데가 없네..)

요즘 나오는 모델들에 비교한다면 deep network라는 이름도 무색할만큼 매우 적은 channel과 layer 수를 갖는 매우 작은 네트워크라는 것을 볼 수 있는데요. 그럼에도 불구하고 여전히 눈여겨 볼 점은, 당시 state-of-the-art 알고리즘들을 큰 차이로 이기고 새로운 baseline을 개척했다는 점, 제안한 3개 layer짜리 SRCNN 구조가 empirical heuristic에 근거한 것이 아닌 전통적인 sparse coding method와의 연관성을 바탕으로 고안되었다는 것입니다. (혹은 최소한 그런 링크가 있다고 매우 그럴 듯하게 주장했ㄷ...)

SRCNN

그림에서 보실 수 있듯이 CNN에서 data-driven filter를 이용한 각각의 nonlinear transformation들이 전통적인 방식에서의 patch extraction, nonlinear mapping (from LR to HR patches) 그리고 reconstruction step에 대응된다고 얘기하고 있습니다:

1. Patch extraction and representation: LR 이미지에서 patch들을 추출해서 high dimensional feature vector로 표현하는 단계; 전통적으로는 PCA나 DCT, Haar 등을 사용해서 추출된 patch들을 pixel representation이 아닌 feature로 represent합니다. 이 과정 자체가 이미지 $\mathbf{Y}$에 특정 filter들을 사용하여 convolution operation을 수행하는 것으로 생각할 수 있으므로 아래와 같이 표현이 가능할 것입니다: $$F_1(\mathbf{Y}) = max(0,W_1 * \mathbf{Y} + B_1)$$ 2. Non-linear mapping: High dimensional feature space (e.g. LR patch space)의 patch들을 또 다른 high dimensional feature space (e.g. HR patch space)로 mapping해주는 단계; 하나의 feature space에서 다른 feature space로 mapping해주는 것 역시도 change of basis로 생각하면 learned basis 혹은 filter를 이용한 convolution operation으로 나타낼 수 있겠습니다: $$F_2(\mathbf{Y}) = max(0,W_2 * F_1(\mathbf{Y}) + B_2)$$ 3. Reconstruction: mapping된 feature vector를 바탕으로 HR 이미지를 만들어내는 단계; 마지막으로 feature domain에서 HR image domain으로 averaged output 생성입니다. 마찬가지로 convolution operation으로 표현이 가능합니다: $$F(\mathbf{Y}) = W_3 * F_2(\mathbf{Y}) + B_3$$
여기서 한가지 더 주목할 부분은 이전의 방식들이 각각의 단계를 처리하는 여러 알고리즘들이 종합적으로 합쳐져서 SR 문제를 풀었다면, SRCNN은 최초의 end-to-end 방식으로써 모든 step을 하나의 통합된 framework에서 처리한다는 것입니다. 특히 매우 단순 명료한 방법으로 기존의 신호처리 관점에서 바라보던 SISR 문제를 deep learning의 관점에서 풀어내면서도 양쪽을 이어주는 가교 역할을 했다는 것에 의의가 있습니다.

Problems to solve


SRCNN은 이후 CNN을 사용한 SISR methods들에 좋은 영감을 주었는데, (아아 그는 좋은 baseline이었다) 이후 나온 Deep learning 방식들은 큰 줄기에서 보면 모두 SRCNN의 단점들을 보완하기 위한 방향으로 발전되었습니다. 각각의 단점들을 크게 정리하면 아래 세 가지로 나눌 수 있습니다:
  1. Bicubic LR
  2. Shallow (three-layer) network
  3. Naive prior in the model

1. Bicubic LR

마지막에 HR 크기로 (최소한 비슷한 **) 이미지를 맞추기 위해 SRCNN은 먼저 bicubic upsampling을 적용한 LR 이미지를 input으로 사용합니다. 논문에서는 bicubic upsampling이라는 operation 자체도 또 하나의 deterministic convolution layer라고 할 수 있다고 설명합니다만 이렇게 upsample이 적용된 LR input을 주는 것으로 여러 애로사항이 꽃 피게 됩니다;
** 사실 SRCNN에서는 padding이 없어서 convolution layer를 지날 때마다 feature map size가 줄어든다.
1) 일단, bicubic upsampling을 LR에 적용해서 준다는 점 자체가 HR 이미지에 대한 degradation model에 대한 implicit prior를 주게 됩니다. 이로 인해 estimation bias가 생깁니다. 따라서 downsampling 혹은 degradation model이 bicubic이 아닌 알지 못하는 좀 더 realistic한 setup에서 학습된 모델의 성능이 저하되는 것을 막을 수 없지요.
2) 또한 처음부터 input size를 크게 사용하기 때문에 computation cost가 늘어나고 따라서 모델이 느려질 수 밖에 없습니다.

2. Shallow network

2014년이라는 시점을 생각하면 매우 당연한 일이기는 합니다만 SRCNN은 더 많은 데이터와 깊은 모델을 사용하면 좋은 성능을 보일지도 모른다는 가능성을 얘기하면서도, 실제로 그런 모델이 잘 동작한다는 것을 보이지는 못했습니다. (오히려 깊은 네트워크에서 성능이 떨어진다는 것을 보였지요) 따라서 이후 많은 연구들이 어떻게 하면 성능 향상을 위해 깊은 네트워크를 학습시킬 수 있을지에 대해 집중하였고, 이후 소개할 VDSR(very deep SR network)를 기점으로 다양한 모델들이 제안되었습니다.

3. Naive prior

앞서 첫번째에서 얘기한 것과 비슷한 맥락으로, SRCNN의 학습 방식은 network architecture에 대한 통찰력 있는 분석에 비해서는 좀 아쉬운 점이 있습니다. 단순히 최종 output과 HR 이미지의 MSE를 줄이는 모델을 바탕으로 학습하는데, SISR이라는 문제에 적합한 prior knowledge를 모델 디자인이나 loss 함수에 이를 적절히 녹여넣어 보다 나은 성능을 얻을 수 있지 않을까라는 질문을 할 수 있겠습니다. 이에 답하기 위해, 역시 이후 많은 연구들이 multi-scale learning 등의 다양한 framework들을 제안하였습니다.

Deep models for SISR


SRCNN이 매우 초기 연구고 여러가지 단점이 있지만 최신 모델들이 갖고 있는 중요한 요소들은 모두 갖추고 있습니다.  이런 관점에서 SRCNN을 큰 부분으로 나눠보면, upsampling methods, model framework, network design, learning strategy의 조합으로 이루어졌다는 것을 알 수 있는데요. 이제부터는 위에서 소개한 문제를 해결하기 위해 각 요소가 어떤 방향으로 발전되고 있는지 하나씩 정리해보겠습니다.

1. Upsampling methods


결국 SISR이라는 문제가 LR에서 HR 이미지로 크기를 키우는 방법을 연구하는 것이므로 먼저 주목을 받은 것은 CNN에서 이미지 크기를 "어떻게 키울 것인가"  입니다.

1) Interpolation-based Upsampling
가장 먼저 고려되었던 방식은 당연하게도 전통적인 interpolation입니다. 이런 upsampling 방식은 implementation이 쉽고, interpretable하다는 장점이 있어 pre-processing으로 많이 사용되었습니다:
  • Nearest-neighbor interpolation
  • Bilinear Interpolation
  • Bicubic Interpolation
그러나 전통적인 interpolation은 external data 정보를 이용하지 못하고, 따라서 dataset이 많을 때 기대할 수 있는 이점이 없기에 deep learning에서 추구하는 바와는 잘 맞지 않았습니다. 게다가 각 방식의 특성에 따라 blurring이나 noise amplification 등이 추가되는 경우가 있어서 초기에만 사용되었습니다. 

2) Learning-based Upsampling
위와 같은 문제들을 피하기 위해 SISR에서는 점차 upsampling operation 자체를 학습하는 방향으로 연구가 진행되었는데, 대표적인 예로는 두 가지 방식이 있습니다:
  • Transposed Convolution Layer
  • Sub-pixel Layer
Transposed Convolution Layer는 흔히 Deconvolution Layer라고도 불립니다. (다만 이러한 명칭에는 전통적으로 영상신호처리 얘기하는 deconvolution과 관련성이 없고 이름이 겹치며 실제 operation을 제대로 설명하고 있지 않다는 문제점이 있기에 Transposed Convolution이라는 표기를 더 선호합니다) 

SISR 분야에서 처음으로 Transposed Convolution을 사용한 연구는 SRCNN의 1저자 Dong이 후속으로 발표한 FSRCNN(Fast SRCNN)입니다. 명확한 이해를 위해서 먼저 각 operation에 대해 설명하는 그림을 보면 아래와 같습니다 (Fig. 4):

모든 learnable 방식이 공유하는 장점이겠으나, Transposed Convolution은 downsampling kernel이 알려지지 않았을 때, 단순한 interpolation 방식(handcrafted implicit prior)을 쓰는 것보다 더 나은 성능을 보여줍니다. External data로부터 정보를 얻을 수 있을뿐더러 부정확한 estimation으로 인한 side effect도 피할 수 있다는 장점이 있었기에 지금도 많은 모델에서 사용되고 있습니다.

한편, Sub-pixel Layer는 Transposed Convolution이 expanding 단계 이후 convolution operation을 할 때, 중복하여 계산되는 pixel이 많아 계산량에서 손해를 보는 단점이 있다는 것을 지적하고 이를 개선하기 위해 제안되었습니다. 그림(Fig. 5)에서 볼 수 있듯이 1) 계산하고자 하는 pixel을 channel쪽으로 밀어넣고, 2) 마지막에 pixel들의 위치를 배치하는 방식을 사용하여 매우 단순하지만 효과적인 방식으로 중복 연산을 없앴습니다.
** 기존 Transposed Convolution의 expanding 단계에서 추가되는 pixel이 nearest neighbor가 아닌 zero padding일 때, Sub-pixel 방식이 Transposed Convolution과 같아진다는 것을 알 수 있습니다.

이렇듯 Sub-pixel 방식은 계산이 효율적이기 때문에 많은 모델에서 사용되고 있습니다. 다만 일반적으로 Sub-pixel 방식은 학습 이후 gridding artifact가 생긴다는 점이 단점으로 지적되고 있어서 다른 variations를 찾는 연구들 역시 제안되고 있습니다.
** 이쪽은 관심이 없는지라 더 깊이 살펴보지는 않았습니다만 관심있으신 분들은 "Checkerboard artifacts free convolutional neural networks"와 논문을 보시면 되겠습니다. 

2. Model framework


한편 전반적인 model framework 관점에서 upsampling module을 어디에 놓는 것이 좋을 지에 대해서도 다양한 연구가 있었습니다. 이들을 크게 네 갈래로 나누자면 아래와 같습니다:
  1. Pre-upsampling
  2. Post-upsampling
  3. Progressive upsampling
  4. Iterative up-and-down sampling
이름에서도 명확히 드러나듯이 모델마다 upsampling을 앞 혹은 뒤에 놓는 것에 따라 특징이 있는데 각 방식에 대한 장단점을 분석해보겠습니다.

Pre-upsampling: 가장 초기에 사용된 방식입니다. 처음 upsampling을 한 이후 네트워크의 input과 output 크기가 동일하게 유지되기 때문에, 계산량에서 손해를 보므로 대다수의 후기 연구들에서는 사용하지 않게 되었습니다.
** 그러나 이것이 꼭 단점만은 아닐 수도 있습니다. 계산량과는 별개로 practical implementation 관점에서 input과 output의 크기가 같다는 점이 주는 장점이 있죠. Input의 크기가 원하는 output 크기와 같기 때문에 다양한 배율(scale)에 대해서 같은 네트워크를 적용할 수 있게 됩니다. 이후 소개를 하겠으나 x2, x3, x4, x8 등의 다양한 scale dataset을 모두 사용하는 multi-scale learning을 적용할 때, 이런 형태의 model framework은 input 크기를 바꿔주는 것이 deterministic하고 따라서 네트워크에 대한 별다른 구조적 변화를 고려하지 않아도 된다는 장점이 있습니다 

Post-upsampling: 앞서 잠시 언급했던 FSRCNN이 바로 이런 형태였습니다. Transposed Convolution을 사용하여 네트워크 마지막 부분에서만 upsample을 하기 때문에 앞에 대다수의 연산이 작은 feature space에서 이루어지고, 이로 인해 학습이 빨라지고 안정될 뿐만 아니라 계산량에서 큰 이득을 보게 됩니다. 이런 장점들로 인해 이후 거의 대부분의 모델들이 Post-upsampling 방식을 사용하고 있습니다.

Progressive upsampling: Post-upsampling 방식들은 마지막에서 한 번에 HR 이미지 크기로 올린다는 특징 때문에 배율이 높은 SR(e.g. x8) 모델 학습이 어렵습니다. 각 배율마다 별개의 네트워크가 필요하기에 multi-scale SR을 하는 모델에도 적합하지 않구요. 이런 문제들을 해결하기 위해 단계적으로 (progressively) 크기를 증가시키는 모델들이 제안되었고 CVPR 2017에 발표된 Laplacian pyramid SR Network (LapSRN)과 CVPR 2018에 발표된 Progressive SR (ProSR)이 그 대표적인 예시들입니다.
LapSRN 구조

이런 모델들의 경우 단일 모델이 한 번의 feed-forward 연산으로 여러 배율(x2, x4, x8 등)의 이미지를 만들 수 있어서 다른 방식에 비해 더 경제적인 multi-scale SR이 가능합니다. 
** 개인적으로 LapSRN과 같이 전통적인 Laplacian pyramid와 Deep model을 결합한 방식의 연구를 매우 좋아하는데, 한편으로는 매우 아쉬운 것이 같은 생각을 하여 모델을 만들었었다는 점입니다. 그리고나서 이 모델을 발견하고 세상에 새로운 것이라고는 없다는 것을 다시 한 번 깨달았습니다...orz.. 

Iterative up-and-down sampling: 이 model framework은 매우 최근에 제안된 모델 때문에 생긴 갈래로, CVPR 2018에 발표된 Deep Back-Projection Network (BPDN)입니다. Super-resolution competition으로 유명한 NTIRE workshop에서 2018년 우승(classical task)을 한 모델로 Bicubic downsampling track에서 뛰어난 성능을 보여주었습니다. LR-HR 이미지 간의 관계를 좀 더 잘 학습하기 위해서 optimization 분야의 iterative method들로부터 영감을 얻어 네트워크에 적용하였습니다. LR과 HR 이미지 domain 간에 up (projection)-and-down (back-projection) mapping을 반복하면서 최종 결과가 점차 개선되기를 기대해볼 수 있습니다.
** 저는 의료 영상 분야에서 와서 그런지 back-projection이 매우 익숙한 방식인데, 점차 이와 같은 classical optimization technique들을 deep learning model에 녹여넣는 형태의 연구들이 많이 소개되는 것으로 보입니다.
** Progressive와 iterative model framework는 모두 성능에서 좋은 향상을 불러왔지만 모델 구조가 복잡하고 학습이 어려워졌다는 단점이 따라오게 됩니다만, 개인적으로 이런 방향의 연구가 다른 framework들에 비해서 앞으로 좀 더 유망하다고 생각합니다. 

3. Network Design


Network design은 SISR 모델에 대한 연구에서 단연 가장 많은 분량을 차지하고 있는 요소이며 classical deep model의 발전과 함께 다양한 구조들이 시도되었습니다:


다양한 SISR 모델 구조 도식 [3]

위 그림에서 보여드리는 네트워크들은 SISR 모델로 제안된 수많은 연구들 중 일부에 불과합니다. 그러나 다행하게도! 이들을 잘 정리해보면, 대략 아래와 같이 큰 줄기로 나누어 정리할 수 있습니다:


SISR 모델 카테고리 [2]

Residual learning
Network design을 살필 때 가장 먼저 언급이되는 논문은 자랑스럽게도 한국인이 저자인 Very Deep SR network (VDSR, CVPR 2016)입니다. 현재 SK에 상무로 계시는 김지원님이 서울대 이경무 교수님 연구실에서 학생이던 때 발표한 모델인데요. SISR 분야 연구에 대해 얘기할 때면 SRCNN과 함께 가장 먼저 나오는 모델 중 하나이며, 여기서 제안된 residual learning은 지금도 여전히 많은 모델들이 사용하고 있는 방식입니다.

VDSR은 SRCNN과 같이 SISR의 cornerstone paper 중 하나로 가장 처음으로 SISR에 학습 가능한 깊은 모델을 제안하였습니다. VGG 네트워크 구조를 차용하여 20개 layer를 쌓아 학습을 시켰고, 깊은 모델의 학습을 위해 두 가지를 제안하였는데 첫째는 global residual learning이고 둘째는 gradient clipping을 동반한 adjustable high learning rate입니다.

이 중 residual learning은 여전히 사랑받고 있는 방법으로 위 그림에서 볼 수 있듯이 학습이 LR 이미지에서 HR 이미지로 mapping하도록 하는 것이 아닌 bicubic upsampled LR 이미지와 HR 이미지의 잔차(residual) 혹은 noise를 학습하는 방식을 제안합니다. (주의할 점은 ResNet의 residual과는 약간 결이 다르다는 점입니다. 이 맥락에서 ResNet은 보다 local residual learning을 수행한다고 할 수 있겠네요.)

Residual image로 학습 대상을 바꾼 것은 full HR 이미지보다 만들어야 하는 정보가 적기에 SISR 문제를 상대적으로 쉬운 문제로 치환하는 효과를 주었습니다. 이로 인해 deep network의 학습이 안정적이고 가속되면서도 성능에 매우 큰 향상이 가능해졌고 이후 많은 모델들이 동일한 전략을 취해 비슷하게 성능 향상을 report하였습니다.
** 같은 맥락에서 제가 CVPR 2017에 발표했던 Wavelet-based SR network에서도 네트워크가 고정되어 있을 때, 학습해야하는 input-output 쌍을 위상적으로 간단한 형태로 미리 변환(wavelet representation & residual learning)하여 어려운 문제를 쉬운 문제로 바꿔주는 방법을 제안했었고 이 것이 주효하여 3등을 할 수 있었습니다.  

Recursive Learning
Recursive learning은 VDSR과 같이 CVPR 2016에 발표된 Deep Recursive CNN (DRCN)이 최초로 사용한 방식으로 이 역시도 VDSR의 저자인 김지원님이 1저자입니다. 네트워크의 receptive field를 크게 가져가면서도 (increase effective depth) 전체 네트워크의 학습 parameter 수를 줄이기 위해 하나의 모듈을 16번 반복하는 형태를 제안한 것이 특징입니다.

태생적으로 gradient vanishing이나 exploding에 취약하기 때문에 이를 막기 위해 앞서 소개한 residual learning이나 차후 소개할 multi-supervision과 같은 학습 방식과 병행되곤 합니다. 재미있는 점은 반복을 하는 중간 중간의 feature output들을 모두 모아 마지막에 weighted sum(**)을 해서 HR 이미지를 만들어주는데, 이 부분이 특히 성능 향상에 큰 역할을 한 것으로 생각됩니다.
** 여기서 몇가지 아쉬운 점은 각 intermediate feature output의 weight scalar가 학습되는 형태기 때문에 input에 dependent하지 않아서 inference time에 유연성이 좀 떨어진다는 것입니다. 그리고 각 weight가 전체 feature output을 scaling하므로 한 장의 feature map에서 pixel-wise difference가 고려되지 않는다는 점도 개선의 여지가 있겠네요. 

DRCN 이후에도 같은 방식을 차용한 여러 모델들이 제안되었으며, 몇몇 예로는 VGG 형태의 네트워크가 아닌 ResNet을 기반으로 한 Deep Recursive Residual Network (DRRN, CVPR 2017)이나 Memory block을 제안하고 이를 반복하는 MemNet (ICCV 2017) 등이 있겠습니다.

Deeper and Denser Learning
VDSR이 깊은 모델을 성공적으로 학습시켰으나 VGG network 형태는 사실 이렇게 깊은 모델에 적합하지 않다는 것은 잘 알려져 있습니다. 더 나은 성능을 위해 가장 쉽게 해볼 수 있는 방법은 (그리고 잘 알려져있는 성공 공식은) 더 깊은 모델을 사용하는 것이죠. 이런 맥락에서 기본 모델의 골격을 ResNet이나 DenseNet처럼 이미 classification에서 성능이 검증된 모델들로 바꾸는 것이 자연스러운 흐름이었습니다. DenseNet도 ResNet에서 분화한 것이라고 생각한다면, 최근 모델들은 모두 ResNet을 기반으로 하고 있다고 말할 수 있겠습니다.

가장 처음으로 ResNet을 사용한 SR model은 SRResNet (CVPR 2017)으로 같은 논문에서 발표된 SRGAN 모델로 더 유명하기도 합니다. SRResNet은 batch normalization을 사용하기에 깊은 모델을 안정적으로 학습할 수 있었고 좋은 성능을 보였습니다. 비슷한 맥락에서 DenseNet을 사용한 모델으로는 SRDenseNet (ICCV 2017)이나 (연구자들의 naming sense...) Residual DenseNet (RDN, CVPR 2018)등이 있습니다. 어떤 면에서는 앞서 소개한 Recursive learning을 이용하는 모델들은 parameter 증가 없이 effective depth가 깊게 만드는 모델들이라 할 수 있고, DRCN에서 그러하듯 intermediate feature를 뽑아 마지막 단계에서 합치는 것은 dense connection을 주는 것이라 생각할 수 있겠네요.

한편 네트워크를 단순히 깊고 넓게 쌓는 것뿐만 아니라 기존 ResNet 모델을 SISR 문제에 좀 더 적합하도록 개선한 연구가 Enhanced Deep residual learning for SISR (EDSR)입니다. EDSR은 모델의 성능만으로도 매우 뛰어난 연구(**)일뿐만 아니라, 이후 SISR 모델들에 큰 영향을 미친 여러가지 유용한 분석들을 여럿 보여주기 때문에 꼭 알고 넘어가야 할 cornerstone paper 중 하나이므로 좀 자세히 리뷰하도록 하겠습니다.
** 또다시 서울대 이경무 교수님 연구실에서 나온 연구로 CVPR NTIRE 2017년 우승 모델입니다. EDSR의 강력한 점은 모델이 이해하기 쉽고 간단한데, 2017년에 발표된 모델의 성능이 2019년 5월 기준으로도 가장 상위에 속하는 모델들과 비견할만하다는 점입니다 (Table). Set5 dataset에 대한 PSNR과 SSIM을 보더라도 CVPR NTIRE 2018 우승 모델인 DBPN과 비등한 것을 보실 수 있습니다: 
Table 각종 benchmark dataset에 대한 model 성능 비교 [3]


EDSR: EDSR 이전의 모델들은 모두 classification에서 좋은 성능을 보였던 네트워크들(e.g. VGG, ResNet, DenseNet)이 SISR 문제도 잘 풀 것이다라는 가정을 바탕으로 네트워크를 디자인하였습니다. 그러나 잘 생각해보면 high-level abstraction이 중요한 classification과 대표적인 low-level vision 문제인 SISR은 서로 특성이 다릅니다.

 
EDSR의 ResBlock (c)

EDSR은 ResBlock에 붙어있는 batch normalization의 특성상 feature의 정보가 섞이거나 제한된다는 점에 주목하였습니다. Low-level feature를 잘 보존해야한다는 SISR 문제에서는 학습만 안정적으로 가능하다면 batch normalization layer를 제거하는 것이 가장 좋은 성능을 얻을 수 있다는 분석을 제시하였습니다. Batch normalization을 없애면 GPU 메모리 측면에서도 40% 가량 줄어드는 부가적인 이득이 있기 때문에, 지금은 SISR 모델이라면 기본적으로 따르는 프로토콜이 되었을 정도로 널리 사용되고 있습니다.

여기서 한 가지 주의할 점은 "학습만 안정적으로 가능하다면"이라는 전제조건입니다. 얕고 적은 수의 channel을 사용하는 수준이라면 (e.g. ResBlock: 16개, 64ch) 생각보다 학습이 안정적이기 때문에 별다른 처리가 필요없지만, 그 이상으로 깊이 그리고 넓게 쌓을 때는 나눠져서 처리된 feature들이 addition 부분에서 더해지면서 전체 variance가 매우 커지기 때문에 추가적인 처리가 필요해집니다. EDSR에서는 이를 고려하여 깊은 모델에서는 각 block의 마지막 convolution layers 이후에 0.1을 곱해주어(**) 문제를 해결하는데요. 이렇게 heuristic하지만 매우 효과적인 기술(residual scaling)을 바탕으로, 이전까지 존재하던 모델들 중 가장 깊고 넓은 모델을 성공적으로 학습시킬 수 있었습니다.
** 이것은 변수에 scaling이 그 값의 제곱으로 영향이 가는 분산의 성질 (wiki)을 생각하면 이해가 쉽습니다.  

이 외에도 EDSR에서 제안하고 여전히 자주 쓰이는 기법으로는 x2로 학습한 모델을 다른 배율 모델의 시작점으로 사용하는 pre-training이 있습니다. 이렇게 pre-trained model을 사용하면 학습이 가속되고 최종 성능도 올라간다는 것을 보였는데, 이런 결과는 각 배율 별 이미지들이 공유하는 정보가 있다는 점을 알려줍니다. 여기서 착안하여 EDSR에서는 EDSR 구조를 기본으로 하되, multi-scale 이미지를 하나의 모델로 처리하는 것이 가능한 Multi-scale SR network (MDSR)를 추가로 제안하였습니다:

MDSR 구조

그림에서 보실 수 있듯이, 앞과 뒤에 각 배율을 담당하는 작은 모듈들을 두고 중간에 공유하는 네트워크가 있어서 학습시에는 배율에 따라 해당하는 모듈들이 독립적으로 학습되데 공유 모듈은 항상 학습이 되도록 합니다. 이렇게 학습을 하면 단일 배율 모델에 비슷한 성능을 내면서도 하나의 모델로 다양한 배율에 대응이 가능하기 때문에 모델 parameter 측면에서 이득이 생깁니다. (43M$\rightarrow$8M)

SR 결과 비교 (x4 배율)

그림에서 확인하실 수 있듯이 bicubic upsample과는 비교도 안 될 정도로 원본 HR 이미지에 근접한 SR 결과를 보여줍니다.

중간 Summary (~2017)


글이 매우 길어졌기에 여기서 한 번 끊고 넘어가는 것이 좋을 것 같군요. 여기까지가 대략 2017년까지 발전된 SISR 모델들을 모두 정리한 것으로, 개인적으로는 EDSR이 2017년까지의 SISR을 대표하는 모델이라고 생각합니다. EDSR 이후로는 깊은 모델을 학습시키는 방향보다는 다른 형태의 정보를 추가해줄 수 있는 모듈들이 고안하거나 성능을 유지하되 좀 더 가벼운 모델을 만드는 쪽으로 연구의 주안점이 옮겨가기 시작했습니다. 이번 글의 완결성을 위해 network design에서 아직 남은 줄기를 훑으면 아래와 같습니다:

Exploiting Non-local or Attention modules

이제 깊은 모델을 사용하는 것이 SISR 성능 향상에 중요한 역할을 한다는 점은 매우 명확해졌습니다. 그러나 그저 ResBlock을 여러번 쌓는 것만으로는 올릴 수 있는 성능에 한계가 있었습니다. 자연스럽게 좀 더 효과적으로 모델을 학습시킬 수 있는 방법에 관심이 집중되었고 (2019년 기준) 최근에는 LR 이미지의 non-local 정보를 잘 이용하는 연구들이 많이 발표되고 있습니다. 

이런 모델들이 지적하는 기존 모델의 문제점으로는:
  • CNN의 receptive field size가 상대적으로 작다는 점,
  • Feature들이 담고 있는 local 혹은 global 정보가 동등하게 처리된다는 점
등이 있습니다. 더 큰 receptive field size는 더 많은 context 정보를 사용할 수 있도록 도와준다고 생각할 수 있는데, 여기서 context 정보라 함은 반복되는 패턴(e.g., 빌딩의 창문 격자 구조 등)과 같이 global한 정보를 뜻합니다.

이런 context 정보를 local image patch만 사용하여 유추하기는 어렵기 때문에 global한 정보를 얻을 수 있는 방법을 모델에 추가해줄 필요가 있겠죠. 이런 생각을 바탕으로 최근 제안된 모델들은 새로운 convolution (e.g., dilated convolution)이나 (spatial or channel-wise) attention,  다양한 pooling (e.g., pyramid or wavelet) 등을 이용하여 non-local module을 사용합니다.

사실 이렇게 global context 정보를 이용하기 위해 non-local filter를 사용하는 아이디어는 매우 오래전부터 model-based optimization에서 많이 연구되었습니다. 가장 대표적인 예로는 BM3D가 있죠. 최근 Kaiming He가 저자로 참여하고 CVPR 2018에 발표되어 유명했던 Non-local Neural Networks라는 연구에서도 이런 관계를 밝히며, 꼭 SISR에서가 아니더라도 global 정보를 잘 사용하므로써 CNN이 보다 좋은 성능을 낼 수 있다는 사실을 보여주고 있습니다. 
Generative Adversarial Networks in SR

한편 최근 뜨고 있는 모델 형태 중 하나는 generative adversarial network을 사용하는 것입니다. Image Super-resolution은 전통적으로 image "hallucination"이라고 불리기도 하는데요. 이름에서도 알 수 있듯이 없는 것을 만들어낸다는 점을 함의하고 있습니다. 결국 낮은 배율의 이미지가 가진 정보에서 최대한 쥐어짜 이미지를 복원하고 나면, 그 이상으로 할 수 있는 최선은 가장 그럴 듯하게 이미지를 "만들어내는 것"이겠습니다.

이런 맥락에서 인간이 봤을 때 더 그럴듯한 이미지로 SR을 하는 것에 대한 연구들이 진행되고 있습니다. 단순히 PSNR이나 SSIM 같은 hand-crafted metric을 만족시키는 것뿐만이 아니라 perceptual metric을 제안하고 사용하기 시작한 것이죠. SR 분야에서 처음으로 이런 시도를 한 연구는 SRGAN입니다.

다만 아직까지는 perceptual loss가 추가되면 필연적으로 PSNR과 SSIM에서 손해를 보기에 전통적인 competetion에서 이런 모델들이 두각을 보이진 못하고 있습니다. 그러나 ECCV 2018에서 SR 최초로 perceptual metric을 competition에 사용하면서 앞으로는 연구 관심이 더 확대될 것으로 기대됩니다.

관련 논문들: 
"Photo-Realistic Single Image Super-Resolution Using a Generative Adversarial Network" (SRGAN, CVPR 2017)
"A fully progressive approach to single-image super-resolution", (ProSR, CVPR NTIRE 2018)
"ESRGAN: Enhanced Super-Resolution Generative Adversarial Networks" ECCV 2018
"2018 PIRM Challenge on Perceptual Image Super-resolution", (ECCV 2018)

맺음말


여기까지가 2018년부터 2019년 CVPR 전까지 발표된 SISR 연구 흐름이라 생각됩니다. 아마 곧 있을 CVPR 2019에서 더 많은 논문들이 발표되겠죠. 다음 글에서는 위에 간략히 살펴본 내용과 더불어서 CVPR 2019에서 발표된 연구들까지 포함하는 것으로 network design에 대한 내용을 마무리 짓고 learning strategy 측면의 발전과 여전히 남은 한계점들에 대한 내용을 다룰 예정입니다. 그러면 이번 글은 여기서 마무리 하겠습니다. 다음 글에서 뵙지요.

참고 자료 


[1] Deep Learning for Image Super-resolution: A Survey Wang et al. 2019
[2] Deep Learning for Single Image Super-Resolution: A Brief Review Yang et al. 2018
[3] A Deep Journey into Super-resolution: A Survey Anwar et al. 2019


다음 읽을 거리