2019년 5월 13일 월요일

카카오 리포트 (Part II)

지난 글에서 GAN의 기본 원리와 배경 이론에 대해 살펴보았다면, 이번 글에서는 GAN에 대한 기본적인 이해를 바탕으로 GAN의 특징과 장단점에 대해 조금 더 심화된 내용을 다루고자 한다. 

DCGAN


초창기 GAN에 대해 얘기하려고 하면 빼놓을 수 없는 연구가 바로 DCGAN이다. GAN이 지금은 매우 뛰어난 결과들을 보여주고 있지만, 초기 결과는 아이디어의 참신성에 비해 그리 인상적이지 않았다. GAN 구조가 학습시키기 매우 어려웠다는 것도 여러 이유 중 하나였는데 Deep Convolutional GAN (DCGAN)이 나온 이후, GAN으로 만드는 결과들이 매우 급격하게 발전하기 시작했다. 크게 이 논문이 기여한 바를 정리해보면,

  • 대부분의 상황에서 언제나 안정적으로 학습이 되는 구조를 제안하였다는 점
  • 마치 word2vec과 같이 DCGAN으로 학습된 생성기가 벡터 산술 연산이 가능한 성질을 갖고 이것으로 의미론적(semantic)으로 신규 샘플을 생성할 수 있다는 것을 보여주었다는 점

등이 있겠다. 

DCGAN 논문은 GAN이 잘 학습되는 구조를 매우 세세한 가이드라인으로 제시한 연구이다. 이 논문 이후에 나온 대부분의 GAN 연구들은 어떤 형태로든 DCGAN 구조를 바탕으로 하고 있다고 할 정도로 매우 잘 확립된 구조이다. 일단 DCGAN에서 제시한 가이드 라인대로 GAN 구조를 짜면 상당히 안정적으로 학습이 된다. 이런 구조를 발견하기 위해서 얼마나 대학원생들이 힘들었을지 논문의 한 구절에서 언뜻 느껴볼 수 있다. 

“However, after extensive model exploration, we identified a family of architectures that resulted in stable training across a range of datasets and allowed for higher resolution and deeper generative models.”

DCGAN은 이름에서 알 수 있듯이 convolution 구조를 GAN에 잘 결합한 것이다. Convolutional neural network (CNN)이 지도학습(supervised learning)에서 매우 큰 성공을 거둔 것에 비해 비지도 학습(unsupervised learning)에서는 상대적으로 잘 사용되지 못하였다. 그런 면에서 DCGAN 논문은 지도학습에서 CNN의 성공적인 모습과 비지도 학습에서의 격차를 줄이는 데에 큰 역할을 하였다고도 평가된다. 그러나 이렇게 추상적인 영향력을 굳이 말할 필요가 없을 정도로 생성한 이미지의 질부터 매우 인상적인 것을 볼 수 있다. 

DCGAN 결과에서 가장 재미있는 부분은 아래와 같이 생성기의 입력으로 들어가는 $z$ 은닉 공간(latent space)에서 벡터 산술 연산이 가능하다는 점이다. 가장 흔한 예시로 word2vec 연구가 있다. 다음 수식을 계산하고 답을 추정해보자: $$KING~(왕) - MAN~(남자) + WOMAN~(여자)$$
사람은 생각보다 쉽게 
$$QUEEN~(여왕)$$
이라는 단어를 연상할 수 있지만 컴퓨터에게 이런 연산은 사실 

  1. 단어의 의미를 이해하고,
  2. 그에 맞는 새로운 단어를 찾는 등의

매우 고차원의 처리가 필요한 어려운 문제이다. 기존의 word2vec 연구에서는 뉴럴넷을 사용하여 말뭉치에서 실제로 단어 간의 관계를 학습하는 것을 보여주었고, DCGAN은 이런 문제를 말뭉치가 아닌 이미지에서 하는 것이 가능하다는 것을 보여주었다. 아래 그림이 바로 그 결과이다.



실제로 모두 DCGAN으로 생성된 결과들이다. 상당히 진짜 같은 결과만으로도 놀라운데, 이미지가 갖는 의미를 바탕으로 직관적인 벡터 산술이 된다는 것을 알 수 있다. 안경을 쓴 남자와 그냥 남자 그리고 일반 여자를 생성하게 하는 입력값들이 은닉 공간에 각각 벡터로 존재하고 있을텐데, 각각의 벡터를 서로 빼고 더해주면 최종적으로는 안경을 쓴 여자를 생성하는 입력 벡터를 찾을 수 있다는 것이다. 

물론 생성기의 입력인 $z$ 벡터 하나만으로는 깔끔한 결과가 나오지 않기에 세 개 정도를 평균한 $\bar{z}$ 벡터를 사용해서 결과를 만든 것이기는 하지만 신기한 것은 매한가지다. 어떻게 보면 네트워크가 영상의 의미를 이해했다고 생각할 수 있다. 

이 외에도 아래와 같이 침실을 생성한 결과 그림들을 보면 작은 그림이긴 하지만 꽤나 그럴듯한 결과를 만들어 냈다는 것을 확인할 수 있다. 

다섯 번 epoch을 돌려 학습한 후 생성된 침실 사진

뿐만 아니라 논문에서 "공간을 걷는다"라고 표현하였듯이 은닉 공간에서 천천히 벡터의 값을 바꿔가면, 생성기가 내보내는 이미지가 하나의 침실에서 다른 침실로 위화감 없이 부드럽게 변화하는 것을 볼 수 있다. 특히 벽이었던 부분이 자연스럽게 하나의 창으로 변화해가는 것을 보면 매우 놀랍다. 

"은닉 공간에서 돌아다니기"

만약 생성기가 단순하게 영상을 외워서 보여줄 뿐이라면 주어진 특정 입력에 대해 특정 이미지를 내보내는 일대일 대응 함수를 학습한 것으로 생각할 수 있다. 이럴 경우 은닉 공간에서 굳이 부드러운 변화가 있을 이유가 없다. 바로 옆의 $z$ 벡터가 전혀 다른 샘플과 일대일로 연동될 수 있기 때문이다. 이렇듯 은닉 공간에서 벡터 연산이 가능하다는 것과 입력에 변화를 줬을 때 생성되는 결과가 부드럽게 변하는 것을 보는 등의 분석이 중요한 이유는 우리가 학습시킨 GAN의 생성기가 일대일 대응 함수와 같이 매우 단순한 의미없는 함수(mapping)를 학습한 것이 아니란 것을 시사하기 때문이다. 

이렇게 수많은 이미지를 표현할 수 있는 정보들을 포괄할 수 있으면서도 부드러운 변화에 대응할 수 있는 함수를 학습할 수 있게 하기 위해서 은닉 공간을 잘 정하는 것도 매우 중요한 일이다. GAN에서는 보통 $z$ 은닉 공간은 고차원의 가우시안 분포를 많이 사용한다. 적절한 가정 하에서 충분히 복잡한 함수를 사용하여 대응시킬 수만 있다면 임의의 $d$ 차원 분포는 정규 분포를 따르는 $d$개의 변수로 나타낼 수 있다는 것이 알려져 있기 때문이다. 

기존 생성 모델과 GAN의 차이점


그러면 GAN은 기존의 생성 모델들과 어떤 면이 다르기에 이렇게 비교적 또렷한 이미지를 만들 수 있는 것일까? GAN의 특징이자 가장 큰 차이점은 바로 GAN이 사실 샘플러(sampler)라는 것이다.  즉, 직접적으로 데이터의 분포를 학습하는 형태가 아니라 하나의 입력이 들어갔을 때 하나의 출력을 주는 형태의 독특한 특징을 지닌다.

조금 더 자세히 이해하기 위해 "확률 모델을 학습한다"는 것에 대해 생각해보면,


모델을 추정한다는 것은 일반적으로 우리가 알고 싶은 $\cal{P}$라는 진짜 데이터의 분포가 어딘가에 있을 때, 이로부터 얻은 샘플들이 i.i.d.하게 관측되었다고 가정한 후 $\cal{Q}$라는 모수 모델 클래스(parametric model class)를 만들어 그 안에서 $\cal{P}$와 가장 "가까운" 모델의 모수를 찾아내는 것을 말한다. 가장 간단한 예시로 데이터의 분포가 정규 분포를 따를 것이라 가정하여 가우시안 모델을 세우고 현재 내가 갖고 있는 데이터를 가장 잘 설명할 수 있는 평균과 분산 값을 찾는 과정을 생각해볼 수 있다.

이를 위해서는 $\cal{P}$와 $\cal{Q}$의 "차이" 혹은 "거리"를 계산할 수 있어야 한다. 그러면 구한 두 분포 사이의 거리를 줄여나가는 방향으로 모델의 모수들을 조정할 수 있고, 이 과정을 적합(fitting)이라고 한다. GAN도 Jensen-Shannon divergence라는 측도를 사용하여 분포 간의 거리를 계산하고 이를 최소화하는 방향으로 생성기를 학습한다고 분석할 수 있다. 

보통 기존의 방식에서는 아래와 같은 $\cal{Q}$에 대한 가정들을 사용하는데:
  • tractable sampling
  • tractable parameter gradient with respect to sample
  • tractable likelihood function

이 중 가장 강력한 가정이 바로 우도 함수(likelihood function)가 계산 가능하다(tractable)는 것이다. 많은 경우 현실의 모델은 계산이 불가능한 형태의 수식으로 나타나는 것을 상기한다면 기존의 모델들이 얼마나 강력한 가정을 사용하고 있는지 알 수 있다. 

한편 GAN 형태의 모델들은 임의의 확률 변수 입력 값을 사용하여 비선형 변환 함수를 통과시키면 출력으로 샘플이 하나 튀어나오는 구조이다. 마치 버튼을 누르면 샘플이 튀어나오는 자판기처럼 생각할 수 있다. GAN 모델들의 독특한 점은 바로 이 부분에서 나온다. GAN 모델들은 다른 확률 모델들과는 달리 우도 함수를 근사하려하지 않고 샘플을 뽑아주는 함수를 학습했을뿐이기 때문에 우도 함수 모델링이 필요없는(likelihood-free) 모델이라고 할 수 있기 때문이다. 

물론 이 부분은 GAN의 특징일뿐 장점일 수도 있고 단점이라 할 수도 있다. 데이터 분포에 대한 모델을 특정하지 않고 하나의 샘플을 뽑아서 보여주기 때문에 고정된 모델에 한계에 제약을 받지 않고 또렷한 이미지를 보여줄 수 있기도 하지만, 다른 한편으로는 정작 이미지를 잘 뽑더라도 데이터의 분포에 대한 정보를 직접적으로 얻기는 어렵기 때문에 분포를 알았을 때 시도해볼 수 있는 많은 분석들을 시도할 수가 없다는 아쉬움이 있다. 이 부분에 대해서는 Ian Goodfellow의 NIPS 2016 tutorial 논문[ref]이나 같은 워크샵에서 발표된 Sebastian Nowozin의 f-GAN [ref] 논문을 참고한다면 조금 더 심화된 내용을 확인할 수 있다.

이외에도 이후 연구된 WGAN에서는 기존의 GAN이 divergence를 측도로 사용하기 때문에 생기는 여러가지 문제를 지적하며 다른 방식의 측도를 제안하는 등, 점차 수식적인 분석과 함께 GAN의 가치 함수 자체를 근본적으로 수정하는 방향으로 연구가 발전되었다. 이를 바탕으로 보다 안정적인 학습과 결과를 보여주었는데 EBGAN LSGAN BEGAN 등 이후 나온 많은 GAN들이 WGAN의 카테고리로 분류할 수 있다.

이렇게 보면 모든 연구가 끝나서 더이상 할 것이 없는 것처럼 보이고 점차 이론적인 문제로 깊게 들어가면서 수학이 많이 들어가고 공학자들이 개입할 수 있는 여지가 없는 것 같지만 아직은 직관이 필요한 부분들이 많이 남아있으며 풀어야할 문제들도 많이 남아있다. 

학습이 예전에 비해 수월해졌다는 것이지 정말 쉬워졌다는 것을 의미하진 않고 네트워크의 안정적으로 학습이 이미지의 질을 보장하지 않는 경우가 많으며 수렴은 여전히 어렵고 이어 소개할 mode collapse나 모델 평가 등 역시 아직도 풀어야 할 문제가 산적해 있다. 그런 의미에서 GAN 학습이 어려운 이유를 하나씩 소개하겠다. 

GAN 학습이 어려운 이유 I: Convergence


지난 글에서 소개하였듯이 원 논문에서 GAN에 대한 이론적 근거를 증명해주었지만 아쉽게도 실제 구현은 이론적 배경이 되는 가정과 거리가 있다. 때문에 GAN 가치 함수를 뉴럴넷을 이용하여 풀었을 때 이상적인 전역해로 수렴한다는 보장이 되지 않는다. 게다가 풀어야하는 문제의 형태부터 이미 쉽게 문제를 풀 수 있는 볼록 함수 형태가 아닌 변수 두 개가 서로 엮여있는 안장점 문제(saddle point problem)를 고려해야하기 때문에 GAN은 학습이 매우 어렵기로 유명하다. 

이 때문에 많은 사람들이 생각보다 간단한 예제에서도 문제를 풀기가 어려울 수 있는데 더 복잡한 문제에서 GAN 형태가 잘 풀릴 것인지에 대해 의문을 제기한 바 있다. 이 문제를 약간 더 직접적으로 느끼기 위해서 실제로 간단한 예제인 $V(x,y) = xy$가 어떻게 생겼는지 그려보면 다음과 같다. 
f(x,y) = xy

이 문제는 $x=0, y=0$에서 안장점을 갖는 매우 대표적인 예시다. 그리고 $x$와 $y$에 대해 최소최대 문제를 풀면 이 안장점이 평형점이라는 것도 쉽게 알 수 있다. 사실 안장점이 모두 평형점이 되는 것은 아니지만 이 경우 하나의 변수에 대한 작은 변화가 다른 변수에 대해 가치 값을 줄일 수 없기 때문에 평형점이 되는 것이다. 만약 이 문제를 구배 감소법(gradient descent)으로 풀면 결과가 평형점 주변에서 수렴하지 못하고 최초 시작점에 따라서 반지름이 정해지는 궤도(orbit)를 영원히 움직이는 것을 확인할 수 있다. 심지어 학습율(learning rate)이 크면, 바깥 방향으로 발산하는 경우도 생길 수 있다. 

이를 수식과 함께 확인해보면 좀 더 명확해진다. 학습율 $\gamma$를 고정하고 $n\in\mathbb{N}$일 때, 각 변수에 대해 구배 감소를 번갈아 계산하는 것은
$$\begin{align*} &x_{n+1} = x_n-\gamma y_n \\&y_{n+1}= y_n+\gamma x_n\end{align*}$$
와 같이 나타낼 수 있다. 이 때,
$$\left[ {\begin{array}{c}
x_{n+1} \\
y_{n+1} \\
\end{array} }\right] = \left[ {\begin{array}{cc}

1 & -\gamma \\

\gamma & 1 \\

\end{array} }\right] \left[{\begin{array}{c}

x_n \\

y_n \\

\end{array} }\right]$$
이므로 여기서 $$\left[{\begin{array}{cc}
1 & -\gamma \\
\gamma & 1 \\
\end{array} }\right] = \frac{1}{\alpha}\left[ {\begin{array}{cc}
\alpha & -\alpha\gamma \\
\alpha\gamma & \alpha \\
\end{array} }\right] = \frac{1}{\alpha}\left[{\begin{array}{cc}
\cos\theta & -\sin\theta \\
\sin\theta & \cos\theta \\
\end{array} }\right] $$
로 바꾸고 $\alpha = \sqrt{\frac{1}{1+\gamma^2}}\in(0,1), \theta = \cos^{-1}\alpha\in\left(0,\frac{\pi}{2}\right)$이라 해보겠다. 고등학교에서 회전 행렬에 대해 배운 사람이라면 위의 행렬식이 매우 익숙할 것이다.  $\gamma\approx0$일 때, 즉 학습율이 충분히 작아서 $\alpha\approx 1$이면 구배 감소의 결과가 언제나 안정한 궤도(stable orbit)으로 빠지고, $\alpha<1$인 경우 $(x_n,y_n)$이 나선형으로 발산하게 된다. 

GAN 학습이 어려운 이유 II: Mode Collapse


앞서 소개한 문제도 그렇지만 GAN 학습이 어려운 이유는 대부분 그 가치 함수의 형태에서 기인한다. 두 번째로 소개할 mode collapse 문제 역시도 GAN의 독특한 가치 함수와 그 문제 풀이 방식 때문에 생기는 것으로 해석할 수 있다. 
Mode Collpase 예시 [ref]

위 그림이 전형적인 mode collapse 문제의 예시다. 맨 오른쪽의 목표 분포를 보시면 가우시안 혼합 모델로 총 여덟 개의 최빈값(mode)이 있는 것을 볼 수 있다. 아래 줄의 그림이 이 목표 분포를 근사하기 위해 GAN으로 여러번 반복하여 학습을 한 결과들을 보여준다. 

GAN이 뽑은 샘플들을 보면 각각의 최빈값들을 각 단계마다 돌아가며 방문하는 것을 볼 수 있다. 즉, 원래라면 윗 줄과 같이 전체 최빈값들을 보고 목표 분포가 여덟 개의 최빈값을 갖는 분포라는 것을 찾아내야하지만, GAN은 그렇게 하지 못하는 모습을 보여준다. 좀 더 직접적인 예를 들자면 숫자가 1부터 8까지 섞여 있는 이미지들로 데이터 분포가 있을 때, 우리는 GAN이 1부터 8까지 모든 숫자들을 만들어낼 수 있기를 바라는데 실제로는 1과 같이 가장 쉬운 한 가지 숫자만 만드는 모델을 학습한다는 것이다. 이런 현상을 하나의 최빈값에만 함몰되는 모델이나 함수를 학습한다고 하여 mode collapse 문제라고 부른다. 

사실 우리가 매 단계마다 최적의 구별자 $D^*$를 계산할 수 있다면야 이런 문제가 생기지 않겠지만 뉴럴넷으로 모델을 만들 경우 수렴이 될 때까지 계산을 매우 여러 번 해야하고 여러 가정이 깨지면서 수렴이 보장되지도 않는다. 따라서 현실적으로는 가치 함수를 각각의 변수에 대해 일정 횟수만큼 번갈아 푸는 방식을 택하는데 이런 방식 때문에 문제가 생기게 된다. 

원래 풀고자하는 GAN의 가치 문제는 다음과 같은 최소최대 문제이다:
$$G^* = \min_G \max_D V(G,D).$$
그렇지만 실제 학습을 할 때는 $G$와 $D$에 대해 번갈아가며 풀어주기 때문에 뉴럴넷의 입장에서는 이러한 최소최대 문제와 아래 같은 최대최소 문제가 구별되지 않는다:
$$G^* = \max_D \min_G V(G,D).$$
문제는 최대최소 문제에서 생긴다. 수식의 안 쪽부터 살펴보면 $G$에 대한 최소 문제가 먼저 있기 때문에 생성자의 입장에서는 현재 고정되어있는 (비최적, non-optimal) 구별자가 가장 헷갈려 할 수 있는 샘플 하나만 학습하면 된다. 즉, 가치 함수를 가장 최소화할 수 있는 최빈값 하나만 내보내면 된다. 이렇듯 GAN의 가치 함수 자체와 엮여 있는 문제이기 때문에 mode collapse 문제는 아직도 GAN에서 완전히 해결되지 않고 있다. 

GAN 학습이 어려운 이유 III: Evaluation


이에 더해 모든 생성 모델이 갖는 고질적인 문제가 파로 평가의 객관성이다. 생성을 한 이미지의 질을 평가할 수 있는 객관적인 기준을 정하는 것이 매우 어렵기 때문에 새로운 모델이 예전의 모델에 비해 발전한 것인지 평가하는 것이 쉽지 않고 연구의 방향을 잡기도 어렵다.

현재 사용되는 방식을 몇 가지 살펴보자면 대표적인 것이 아마존 매카니컬 터크(Amazon Mechanical Turk)를 사용하여 사람이 직접 평가하도록 하는 방식이다. 그러나 이런 방법은 매우 주관적이고, 일관된 평가가 어려우며, 위에서 설명한 mode collapse가 일어난 경우 전혀 모델의 문제점을 파악할 수 없다는 단점이 있다. Mode collapse가 일어난 모델의 경우 생성하는 이미지의 다양성이 부족할 뿐이지 단일 이미지의 자체는 상당히 질이 좋을 수 있기 때문이다.

두번째로는 Inception score라고 하여 구글의 인셉션 이미지 분류 모델에 생성된 이미지를 넣어 나오는 값을 바탕으로 평가를 하는 방식이 있다. 이 방법은 값이 일관되고 어느 정도 객관성을 보장할 수 있다는 장점이 있어 꽤 자주 사용되고 있다. 하지만 굳이 인셉션 모델을 사용해야하는 이유도 없고 어떤 모델의 경우 인셉션 모델에 특화(overfitting)되어 실제 이미지의 질과는 무관하게 점수가 좋게 나올 수도 있다는 문제를 안고 있다.

이렇게 앞서 소개한 문제들 외에도 다양한 연구거리가 남아있겠지만 세 가지로 크게 정리해보았다. GAN 연구가 활발하고 매일 하루가 멀다하고 쏟아지는만큼 더이상 연구할 것이 없고 너무 늦었다고 생각할 수 있으나 알고보면 아직 가야할 길이 멀다.

창GAN기-믿거나 말거나


마지막으로 GAN에 대한 탄생비화 [ref]를 소개해드리면서 글을 마무리하겠다. Ian Goodfellow가 최초로 만든 GAN은 multi-layer perceptron (MLP)을 이용한 매우 단순한 형태의 GAN이었다고 한다. 거짓말 같지만 단 한 번의 시도만에 바로 성공했다는데... 물론 매우 간단한 문제에 대해 적용해봤을 것으로 추측되지만 GAN이 수렴시키기 어렵기로 악명 높다는 것을 생각해보면 솔직히 믿기지 않는 일화이다 (마치 박혁거세 설화를 보는 느낌이랄까...). 

Ian Goodfellow가 GAN에 대한 아이디어를 처음 떠올린 순간은 몬트리올의 ``The 3 Brewers''라는 펍에서 친구들과 얘기를 하던 중이었다고 한다. 박사를 마치고 연구실을 떠나는 친구를 송별하는 자리였는데, 그렇게 모인 친구들 중 한 명이 모든 사진의 통계적 정보를 넣어서 스스로 사진을 만들어 낼 수 있는 기계에 대해 얘기를 꺼냈고, 어떻게 하면 그런 기계를 현실적으로 만들 수 있을 지에 대해 논쟁이 벌어졌다. 

존재하는 모든 사진에 대한 통계적인 정보를 얻는 것부터 일단 말이 되지 않으니 불가능한 프로젝트라고 생각하다가 순간 뉴럴넷을 사용해서 기계를 가르치면 더 진짜 같은 사진을 만들 수 있지 않을까 하는 생각이 들었다고 한다. 하지만 친구들은 그 아이디어에 대해 부정적이였고, 살짝 열이 받은 Ian은 새벽에 술자리에서 돌아오자마자 앉은 자리에서 노트북으로 GAN을 코딩했다고 한다. 그리고 거짓말 같이 단 번에 성공했다는데, 이후 인터뷰에서도 ``매우 매우 운이 좋았다. 만약 GAN이 한 번에 성공하지 않았다면, 그냥 포기했을 것이다'' 라며 스스로도 운이 좋았다고 하였다. 

이 인터뷰 내용이 사실이라면 여기서 우리는 여러가지 교훈을 얻을 수 있다 (옛날 이야기에는 언제나 교훈이 있는 법). 문제를 설정하고 풀 때 직관력이 매우 중요하다는 것과 그 직관으로 얻은 아이디어를 바로 실험해보는 실행력이 중요하다는 것, 술자리에서 연구 얘기만 주구장창 하여도 진지하고 재미있게 들어줄 사람들이 있는 집단에 들어가야 한다는 것 그리고 마지막으로 되는 놈은 뭘 해도 된다고 운도 조금은 좋아야 한다는 것이다. 희망적인 것은 어떤 문제에 대한 직관력은 그 분야와 연관된 깊은 수학적 지식에서 나올 수도 있지만 수많은 시행착오(a.k.a. 삽질)을 바탕으로 한 경험으로 길러질 수도 있다는 점이다. 그리고 매우 다양하게 많은 시도를 하다보면 통계적으로 되는 방법을 찾을 확률이 높으니 운이라는 것도 어느 정도 통계에 기대볼 수 있을 것 같다. 이렇게 열정적으로 문제를 풀다보면 비슷한 사람들이 모여있는 집단(카카오..?)에 갈 수 있는 기회가 생기고, 더 재미있게 잘 연구를 할 수 있는 선순환이 이루어지지 않을까? 

엄밀한 수학 지식을 바탕으로 차근차근 쌓아 올렸을 것 같은 매우 복잡한 이론들도 순간적인 직관에서 시작하는 경우가 매우 많은 것 같다. 그러니 수학이 어려운 공학자들이여 우리 모두 힘을 내자! 수학을 잘하는 수학자들과 실험을 바탕으로 감이 살아있는 공학자들이 각자가 잘하는 영역에서 연구를 하며 협업을 통해 문제를 발전시켜 나간다면 언젠가는 정말로 이미지뿐만 아니라 사람의 생각을 모사하는 궁극의 생성 모델을 만들 수 있지 않을까 기대해본다.

다음 읽을 거리





카카오 리포트 (Part I)

이전에 카카오 리포트에 기고한 글을 개인 블로그에도 올린다. 두 파트로 나뉘어 글을 기고하였는데, 둘이 합쳐 GAN에 대한 전체적인 조망이 되기 때문에, 개별 GAN 논문을 리뷰하는 것에 비해 개괄적인 정보를 알 수 있을 것이다.

파트 I은 GAN에 대한 소개로 이전 초짜 대학원생 시리즈에서 대부분 다룬 내용이지만 첫 글 이후로 GAN에 대해 이해가 더 깊어진 후 정리한 글이기에 내용적 측면에서 낫다는 장점도 있겠다. 파트 II는 GAN 연구에 대해 좀 더 개괄적으로 다루고 있으므로 연구 방향이나 흐름을 빠르게 알고 싶은 사람들에게 도움이 되리라 생각한다.

** 이 글을 기고할 당시만 해도 대학원생으로 박사 졸업을 언제 할 수 있을지 불분명 하였을뿐 아니라, GAN이 참 재미있으면서도 내 연구 주제에 머신러닝을 적용하는 것이 가능할지도 잘 모르던 때였는데, 지금은 네이버에서 본격적으로 generative model들을 연구하고 있으니 시간이 참 빠르다. 열심히 살아야지. 
2019.05.13




2019년 5월 12일 일요일

Image Restoration (IR): inverse problem point of view (1)

제 박사 학위 논문 제목은 "Learning-based approaches for Inverse Scattering Problems"입니다. 이 제목은 제 지도 교수님께서 지어주셨는데, 박사 학위 디펜스를 하면서 committee 교수님들께 학위 논문이 아니라 textbook에나 어울리는 제목이라고 좀 더 범위를 좁혀 수정을 하라는 지적을 다수 받았던 기억이 납니다.
** 그럼에도 불구하고 지도 교수님께서는 차라리 다른 imaging modality에 대한 연구를 추가로 할지언정 이 제목은 꿋꿋히 유지하라고 말씀하셨고, 결국에는 추가 연구를 더 해서 넣고 (하하하...orz...) 결국 제 학위 논문의 제목은 그대로 유지했습니다. 

오늘 소개할 내용은 제 학위 논문 제목에도 나와있는 inverse problem에 대한 얘기입니다. 그 중에서도 영상(image)에 대한 inverse problem에 대한 것으로 좀 더 좁게는 image restoration 문제에 대한 정리를 하고자 합니다.

Inverse Problems

An inverse problem in science is the process of calculating from a set of observations the causal factors that produced them: for example, calculating an image in X-ray computed tomography, source reconstruction in acoustics, or calculating the density of the Earth from measurements of its gravity field. It is called an inverse problem because it starts with the effects and then calculates the causes. It is the inverse of a forward problem, which starts with the causes and then calculates the effects.
어느 정도 감을 잡으셨을지 모르겠습니다만, 사실 committee 교수님들께서 제게 주셨던 의견들은 매우 온당한 것으로 inverse problem이라는 분야는 매우 광범위합니다. 위의 정의에서도 볼 수 있듯이 어떤 물리적 시스템을 묘사하는 문제를 forward modeling이라 한다면 그의 반대 방향을 모델링하고 연구하는 것을 inverse problem이라 할 수 있겠습니다.

하나의 예시로 아래와 같이 어떤 시스템 (e.g., 카메라)을 통과한 자연 이미지(latent original image)가 natural noise (e.g., additive white Gaussian noise, AWGN)뿐만 아니라 blurring 혹은 down-sampling과 같은 시스템의 특성으로 인한 degradation이 추가되어 관측된 이미지를 얻은 상황을 고려해보겠습니다:


이 때, 시스템 함수 혹은 operator $G$에 대한 물리적인 이해를 바탕으로 이를 찾거나 모델링하는 것을 forward problem이라 하고, 반대로 관측한 이미지를 바탕으로 깨끗한 원래 이미지를 찾는 문제를 inverse problem이라 합니다. 시스템에서 일어난 degradation에 따라서 각각 deblurring, denoising, super-resolution 등의 여러 영상 복원 (image restoration) 문제들로 세분화 될 수 있습니다.

Problem statement


General formulation


Image restoration을 수식적으로 모델링하는 방법은 매우 다양하겠으나, 측정 벡터 $y$가 임의의 선형 시스템 행렬 $H$와 가우시안 노이즈 (additive white Gaussian noise, AWGN)에 대해 $$y=Hx+v$$로 표현하는 것이 가장 일반적이며, 시스템 행렬 혹은 operator $H$가 어떤 것이냐에 따라 여러가지 영상 복원 문제가 모델링됩니다.

예를 들어 denoising은 $H=I$, deblurring (deconvolution)은 $H$가 convolution filter로 $Hx = k\circledast x$인 경우가 되며, inpainting은 $H$가 identity matrix이되 missing samples에 해당하는 부분이 듬성듬성 비어있는 degradation matrix로 모델링이 가능합니다. 또한 super-resolution은 $H$가 blur kernel과 sub-sampling (혹은 down-sampling)이 결합된 형태이며, 의료 영상 분야에서 사용되는 tomographic reconstruction은 $H$가 특정한 physical projections (e.g., Radon projections)이라 할 수 있겠습니다. 

영상에 가해진 degradation으로 인해 이를 되돌리는 것은 매우 "어려운데", 여기서 어렵다는 것은 image restoration (IR)은 "ill-posed" inverse problem (**)이라는 뜻입니다. 예를 들어 Single Image Super-Resolution (SISR)은 대표적인  ill-posed problem으로 방정식의 변수가 독립적으로 구성할 수 있는 식의 갯수보다 많은 경우입니다. 좀 더 구체적으로는 $H$의 row 수에 비해 column의 수가 훨씬 많기에 $x$의 해가 무한히 많을 수 있어서 진짜 $x^*$를 특정하기 어렵다는 것으로, 한 장의 저해상도 이미지에 대응할 수 있는 고해상도 이미지는 다양한 경우의 수가 있다는 예시로 이해하시면 쉽습니다.
** ill-posedness를 알고 싶다면 well-posed problem이 무엇인지를 알면 됩니다. 이는 wikipedia를 참고하시면 되겠습니다. 

특히나 natural image와 같이 전체 공간(search space)이 매우 큰 경우 해를 찾는 일이 더 지난하기 때문에, 가능한 해가 살고 있는 공간(solution space)을 좁히기 위해서 문제에 따라 시스템에 따라 적절한 constraint를 바탕으로 제약(regularize)을 걸어주는 방식을 취하게 됩니다. 따라서 관측된 데이터 $y$로부터 $x$를 구하기 위해서는 $$\min_x\frac{1}{2}||Hx-y||^2_2+\lambda\rho (x)$$를 푸는 것이 일반적이며 $\rho(x)$는 우리가 고른 regularization 항이 되겠습니다.

Bayesian perspective


이를 Bayesian 관점으로 표현하면, likelihood function $P(y|x)=exp(-\frac{1}{2\sigma^2}||y-Hx||^2_2)$에 적절한 image prior $P(x)$를 사용하여 $P(x|y)$를 구하는 maximum a posteriori (MAP) estimation으로 생각할 수 있습니다:$$\begin{align*} \hat{x} &=\arg\min_x\{-\log P(y|x)-\log P(x)\} \\ &= \arg\min_x\{\frac{1}{2\sigma^2}||y-Hx||^2_2+\lambda\rho(x)\}\end{align*}$$ 여기서 $\sigma^2$는 $\lambda$에 흡수될 수 있으므로 결과적으로 같은 형태가 된다는 것을 알 수 있죠.

이런 MAP framework로 IR 분야에 연구들을 살펴보면, image에 대한 prior를 어떤 것으로 정하느냐가 모델링의 주안점이 되어왔다는 것을 알 수 있습니다. 대표적인 image prior 모델로는 sparsity-inducing prior나 low-rank prior가 있겠으며, 이를 이용하여 optimization 문제를 푸는 전통적인 방식을 model-based optimization이라는 하나의 큰 카테고리로 묶을 수 있습니다.

한편 model-based optimization과는 조금 다른 갈래가 최근 트랜드인 deep learning입니다. 이를 MAP framework 관점에서 생각하면 deep learning 역시도 일종의 discriminative learning prior로써 image prior 모델링의 한 종류라고 생각할 수 있겠습니다.

지금부터는 이런 분류를 바탕으로 각 카테고리의 방식들을 하나씩 소개하겠습니다.

Sparse representation


많은 IR 알고리즘들이 sparsity prior를 사용하고 있습니다. 대표적인 예로는 total variation (TV)이 있으며, wavelet transform 이후 soft-thresholding을 하는 간단하지만 강력한 denoising 기법들이 있습니다. (이 방식은 natural image에 대한 wavelet domain representation이 일반적으로 sparse하다는 것을 근거로 합니다.)

또한 이미지 patch들이 sparse dictionary representation이 가능하다는 것 역시도 잘 알려진 사실이며 이를 이용하는 대표적인 알고리즘이 sparse coding입니다. IR에 대한 일반적인 sparse representation 모델은 overcomplete dictionary $D$와 이에 대응하는 coding (coefficients) vector $\alpha$에 $l_1$-norm을 취한 sparsity regularization이 더해진 형태입니다 (i.e., $\min_\alpha ||\alpha||_1$ s.t. $x=D\alpha$): $$\hat{\alpha}=\arg\min_\alpha||y-HD\alpha||+\lambda||\alpha||_1$$ 즉, sparse coding에서는 $x$에 대한 문제를 $\alpha$에 대한 estimation으로 문제를 바꾸어 풉니다. 

Sparse representation이 IR에서 성공적이었던 이유는 여러 가지로 방향으로 설명이 가능한데,
  1. Bayesian 관점에서 보면 sparsity prior를 이용하여 MAP 문제를 매우 잘 풀었다고 할 수 있고,
  2. neuroscience 측면에서 보면 실제로 인간의 primary visual cortex의 simple cells들이 들어오는 시각 신호에 대해 spatially localized, oriented 혹은 band-passed 형태로 각각 특화되어 있는데, wavelet filter를 사용한 sparsity-inducing representation이 이를 잘 모사하기 때문일 수도 있으며,
  3. compressed sensing 관점에서는 image patch들이 $k$-sparse한 신호들이라서 애초에 sparse optimization 형태로 가장 잘 풀 수 있는 문제이므로 여러 모로 성격이 잘 맞았다고 설명할 수도 있습니다. 

Sparse Dictionary Learning


Sparse representation 방식이 잘 통하려면 이를 표현할 atom들이 모인 dictionary를 잘 만드는 것이 가장 기본이 되겠습니다. 초기에는 DCT나 wavelets, curvelets 등을 사용한 analytical dictionary 구성이 주를 이루었으나 natural image의 복잡성을 충분히 표현하기에는 이런 hand-crafted analytical dictionary로는 한계가 있었습니다. 즉, 복잡한 이미지에 대해서는 더 많은 atom들이 필요했고 자연스럽게 sparseness가 떨어지는 문제가 있었죠.

이를 해결하기 위해 다음으로 연구된 것이 dictionary에 들어갈 atom들을 이미지들로부터 학습하는 것이었습니다. 즉, $Y=[y_1,\cdots,y_n]$과 같은 학습 샘플들이 있을 때, $m<n$인 atom을 갖는 dictionary $D=[d_1,\cdots, d_m]$을 $Y$로부터 배우되 $Y=D\Lambda,~\Lambda=[\alpha_1,\cdots, \alpha_n]$을 만족하는 code $\alpha$에 $l_0$-norm sparsity constraint를 주어 학습시킵니다. 여기서 $y_i$는 vectorized된 이미지 patch로 생각하시면 됩니다. 이 카테고리의 가장 대표적인 알고리즘으로는 K-SVD가 있습니다. 

Dictionary learning 방식은 analytically designed dictionary에 비해 특정 task나 data에 좀 더 adaptive한 표현이 가능했기에 일반적으로 더 좋은 성능을 보여주었고, multi-scale dictionary learning, double sparsity, adaptive PCA dictionaries, semi-coupled dictionary learning 등 다양한 알고리즘들이 개발되었으며 많은 연구 분야에서 애용되어 왔습니다. 

Low-rank minimization


Natural image에서 patch를 뽑으면 생각보다 패턴이 반복되는 경우가 많습니다. 이런 경험적인 지식을 바탕으로 non-local self-similarity (NSS) prior를 사용하는 연구들이 있는데요. 이런 방법들은 보통 이미지 내에 correlated patch들을 여러 장 모아 사용합니다. 각각의 이미지 patch를 따로따로 처리하는 sparse representation과는 확실히 다르다는 것을 알 수있습니다.

Non-local self-similarity in natural image

그림과 같이 이미지로부터 patch들을 뽑은 다음 column의 형태로 옆으로 쌓아 matrix 형태로 만들면, 이렇게 만든 matrix는 correlated patch들로 인해 low-rank한 특징을 갖게 됩니다.

이런 특징을 이용하는 IR 방법을 low-rank minimization이라 합니다. 예를 들어 이미지에 Gaussian noise가 더해지는 denoising 문제를 생각해보겠습니다. Noise는 패치들을 여럿 모은다고 해서 서로 correlate 할 이유가 없으므로 일반적으로 full-rank한 특성을 갖겠지만, 우리가 원하는 실제 이미지는 low-rank한 특성이 있을테니 데이터 행렬을 low-rank한 행렬로 approximation하므로써 denoising이 가능합니다. 즉, corrupted patch를 다른 patch로부터 수집한 redundant information을 바탕으로 수정하는 것이죠. 

문제는 행렬의 rank를 minimize하는 것이 매우 잘 알려진 NP-hard 문제라는 것입니다. 따라서 rank minimization 문제는 rank penalty의 convex relaxation인 nuclear norm을 사용해서 문제를 풀게 됩니다: $$\hat{X}=\arg\min_X ||Y-X||^2_F+\lambda||X||_*$$ 이 때, $X$의 nuclear norm은 $||X||_*=\sum_i||\sigma_i(X)||_1$로써 singular value의 합입니다. 이런 formulation의 장점은 문제의 closed-form solution이 존재한다는 것입니다. $Y=U\Sigma V^T$일 때, $$\hat{X}=US_{\frac{\lambda}{2}}(\Sigma)V^T$$이며, $S_{\frac{\lambda}{2}}(\Sigma)_{ii}=\max(\Sigma_{ii}-\frac{\lambda}{2},0)$으로 일종의 thresholding operator입니다. 이렇게 보면 행렬 $X$에 low-rankness도 다르게 말하면 행렬의 singular value들이 sparsely distribute할 것이라는 가정에서 시작하는 것이므로 sparsity prior라고 할 수 있겠습니다.

지금까지 매우 간결하게 Image restoration에서 사용되어 온 큰 줄기를 훑어보았는데요. 다음 글에서는 이런 model-based optimization 방식과는 좀 다른 결을 보여주는 learning-based approach를 소개하겠습니다.

간단히만 소개하자면, MAP estimation이라는 관점에서 discriminative learning 방식은 MAP inference를 predefined nonlinear function으로 대체하여 문제를 푸는 것으로 생각할 수 있습니다: $$\min_\theta l(\hat{x},x),~\text{s.t}~\hat{x}=\mathcal{F}(y,H;\theta)$$ 여기서 $\mathcal{F(\cdot)}$는 CNN이라고 생각하시면 됩니다.

이런 discriminative learning 방식은 model-based optimization 방식에 비해 유연성이 떨어지지만, 대신 test time에서 inference 속도가 빠르다는 장점이 있습니다. 이 외에도 여러 장단점과 특징이 있는데 왜 그러한 특징이 생기는지 등 자세한 것은 다음 글에서 다루겠습니다.

결국 하고 싶은 말은 deep learning을 사용하는 방식이 절대로 기존에 연구되어 온 많은 연구들과 완전 다른 길을 걷고 있는 것이 아니고, 이 역시도 크게는 image prior $P(x)$를 모델링하는 방식 중 하나라는 관점에서 설명할 수 있다는 것입니다.

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

다음 읽을 거리






2019년 5월 11일 토요일

Signal Processing For Communications (0)

이 시리즈는 signal processing을 학부 때 배웠으나 여러 이유로 이해를 잘 하지 못하다가 뒤늦게서야 유용성을 깨닫고 개인적으로 공부하며 정리한 흔적입니다.

어느날 문득 결국 machine learning을 하든 deep learning을 하든 모두 신호를 다루기 위한 도구일 따름이고, 주로 다루는 신호가 이미지라는 형태를 띄고 있을뿐 근본적으로 디지털 신호 처리에서 다루는 내용에서 벗어나지 않는다는 생각이 들었습니다.

이런 맥락에서 신호 처리에 대해 좀 더 잘 알고 싶다는 생각에 정리를 시작하였는데, 대부분의 글은 주로 EPFL의 Martin Vetterli 교수님의 textbook을 기반으로 요약하되 제가 여기저기서 찾아 이해한 내용들로 주석을 달거나 내용을 추가했습니다.

앞으로 쓸 글들은 (얼마나 걸릴지는 모르겠지만) 모두 신호처리의 기본에 대해 대학교 학부생을 위한 기초 수준으로 작성될 것입니다. 제 스스로가 그 이상을 설명할만큼 잘 알고 있다고 생각하지도 않는만큼, 차후 시간이 흘러 다시 이 글을 봤을 때도 이해가 쉽게 하겠다는 목적을 갖고 글을 정리해보고자 합니다.

약간의 선형대수학, 신호처리에 대한 기초 지식 그리고 더 나가서 해석학을 들어본 적이 있다면 보다 깊은 이해에 도움이 될 것이지만, 그런 선행 지식이 없이도 어렵지 않게 이해할 수 있는 수준으로 작성하고자 노력하였습니다.

간단한 예시 그리고 덜 형식적인 설명을 바탕으로 신호처리라는 딱딱한 주제에 대해 쉽게 접근할 수 있도록 작성하였으며, 이해하기 쉬운 설명을 위해 수학적 엄밀성 강조하지는 않겠지만 최소한 틀리지 않는 정확한 설명을 하는 것에 주안점을 두었습니다. 계획된 목차는 아래와 같습니다.

목차 (planned)



다만, 꼭 순서대로 글이 작성되리라는 보장은 없으며, 각 글의 제목 뒤에 붙은 숫자는 책에서 해당 내용이 다뤄진 chapter를 따랐습니다. 따라서 모든 chapter를 정리하지는 않을 예정이므로 숫자가 다 채워질 이유도 순서대로 나열될 이유도 없지요. 이 preface 글의 목차는 글을 써가면서 매번 업데이트 될 예정입니다.

마찬가지로 읽는 분도 원하시는 것만 골라 읽으실 수도 있을 것이고, 순서대로 차근차근 읽으실 수도 있을 것이나, 제가 염두에 두고 쓴 순서를 추천드리자면, 먼저 (1)을 읽으시고 (9-1)로 넘어가신 후 다시 (2)로 돌아가서 쭉 순서대로 읽으시는 것을 권해드립니다. 개인적으로는 그렇게 하는 것이 신호처리를 배우는 목적을 이해하고 전체적인 감을 잡는 것에 훨씬 도움이 된다고 생각합니다.

현재 이 글은 서문과 같은 역할이므로 chapter 0라 임의로 칭했고, 따라서 제목이 다음과 같습니다; Signal Processing For Communications (0)



Signal Processing For Communications (1)

What Is Digital Signal Processing?


신호(signal)와 신호 처리(signal processing) 대해서 정의를 내리자면 각각 다음과 같습니다:
신호: 시간 혹은 공간에 대해 변화하는 현상에 대한 formal description
신호 처리: 신호에 들어있는 정보를 바꾸거나 분석하는 any operation.
예를 들어 주변 온도를 우리가 Celsius degree라는 물리적 변수를 기준으로 시간에 따른 온도의 변화를 기록하는 경우, 이렇게 만들어진 data set은 온도 "신호"가 될 것입니다. 이 신호에 대한 가장 단순한 "처리"로는 월간 온도 평균과 같은 어떤 파라미터를 계산하는 것이 있겠죠.

또한 신호 처리는 어떤 물리적인 값 자체에 직접 가해지는 것이 아니라 물리적인 값의 "abstract representation"을 기반으로 수행된다는 점이 중요합니다. 이런 abstract representation의 방식에 따라서 신호 처리의 기본 단위(unit)가 정해지게 됩니다.

한편 "디지털 (digital)"이라는 수식어구는 라틴어 digitus에서 유래한 것으로 손가락을 의미하는데, counting은 가장 기초적이고 오래된 abstraction이라 합니다. 즉, 디지털 신호 처리는 시간을 포함한 모든 것들에 정수(integer number)와 같이 countable한 abstraction representation을 사용한다는 것을 의미합니다.

좀 더 구체적 예시로는, 주변 온도를 측정한 각각의 관측(instants)이 셀 수 있는 집합(the days in a month)을 이루고 각 관측값(measure)들 역시도 온도계의 눈금 단위와 같이 유한한 수의 집합으로 표현되는 것을 생각해보면 되겠습니다.

재미있는 점은 디지털 신호 처리에서는 신호가 "어디서 유래한 것인가에 관계없이" 이를 "정수로 표현 가능한" abstract representation을 사용한다는 것인데요. 지금 당장은 이 사실이 별달리 중요해보이지 않을 수 있으나, 이 특징이 디지털 신호처리가 지금과 같이 크게 발전할 수 있었던 큰 동력이라는 점은 차차 글이 진행됨에 따라 분명해지리라 생각합니다.

Analog vs. Digital worlds


세계에 대한 "digital" 혹은 정수를 이용한 표현 방식은 우리가 다루는 문제가 가축이나 날짜를 세는 것과 같이 간단할 때까지는 아무 문제가 없이 잘 동작했으나, 점차 세상이 복잡해지고 이를 설명하는 모델 역시도 복잡해질 필요가 생기면서 한계에 부닥쳤습니다.

신호 처리 쪽 용어로 얘기하자면, 정수로 표현되는 세계가 "analog"와 같이 연속적인 세계를 설명하는 잣대로 사용하기에는 너무 초보적이고 거칠어서 마치 정밀한 시계를 다루는 시계공이 못을 박는 망치를 들고 있는 것과 같다는 것입니다.

문제는 무한대와 무한소로 나눠질 수 있는 연속적인 analog 세계의 analytical 모델을 사용하면 이론적으로 분석하기는 편할지언정, 실제로 이를 사용하기 위해서는 언제나 유한하고 이산적인 digital 세계로 내려와야한다는 점입니다.

예를 들어 온도를 측정하는 것만해도, 우리가 얻을 수 있는 것은 언제나 일정 간격(time)을 두고 측정한 관측값들일 뿐 임의의 시간에 대해 해당하는 온도에 대한 관계를 보여주는 analytical 모델이 아니죠.

따라서 analog와 digital representation이 서로 만족할만한 합의에 이르기 위해 부단한 노력들이 있어 왔고, series expansion이나 numerical integration 등의 알고리즘들이 analytic 결과를 practically computable한 형태로 만들기 위한 노력의 예시들이라 하겠습니다.

디지털 신호 처리가 멋진 것은 이렇게 양분된 두 세계가 서로 가장 만족스러운 형태로 합의에 이를 수 있도록 한다는 점입니다.

Discrete Time


아날로그 기록 방식의 가장 큰 문제점은 신호를 추상화 하여 기록하는 것이 아닌 하나의 물리적인 현상을 또 다른 물리적 현상으로 옮기는 것에 불과하다는 점인데요. 이 때문에 근본적으로 아날로그 신호는 기록(recording)의 형태에 따라 각각 다른 신호 처리 시스템이 필요하게 됩니다. 예를 들어 우리가 온도 변화 함수 $f(t)$를 알고 있고,

Analytical and empirical averages

일정 간격 $[T_0, T_1]$ 사이에 일어난 온도 변화의 평균값을 알고싶다면 이에 대한 analytical solution은 다음과 같은 적분 방적식을 푸는 것이 됩니다: $$\bar{C} = \frac{1}{T_1-T_0}\int_{T_0}^{T_1} f(t) dt.$$ 그러나 analytic model이 없는 현실에서는 어떤 기기를 사용하여 온도를 측정, 기록하였을 것이고 그 데이터를 가지고 평균 온도를 계산할텐데요. 만약 온도가 thermograph를 이용하여 그래프의 형태로 기록되었다면 plainmeter라는 면적을 구하는 기계적 도구를 사용하여 면적을 알 수 있을 것입니다. 그러나 온도 변화가 thermocouple과 같이 전압을 이용하여 기록을 하는 경우 학부 전자기초 시간에 배우는 RC 네트워크로 voltage integration 회로를 만들어 평균값을 계산해야 할테죠. 이렇듯 아날로그 신호에서는 평균을 구하는 매우 단순한 예에서도 각 경우마다 특정한 디자인이 필요하기에 범용적으로 사용할 수 있는 방식을 고안하기 어렵다는 것을 알 수 있습니다.

한편, 디지털 방식과 같이 하루에 한 번씩 측정한 온도에 대해 평균을 구하는 것은 매우 쉽습니다: $$\hat{C}=\frac{1}{D}\sum^D_{n=1}c_n.$$ 단순히 초보적인 덧셈과 나눗셈만 수행하면 원하는 값을 얻을 수 있죠! 그렇다면,
"$\bar{C}$와 $\hat{C}$의 차이가 (만약 있다면) 얼마나 될까요?"
만약 저 자연계 어딘가에 $f(t)$라는 온도 함수가 있다는 것을 받아들인다면 하루 주기($T_s$)마다 측정한 $c_n$ 온도 측정값들은 이 함수의 $samples$라고 할 수 있습니다: $$c_n=f(nT_s).$$ 이런 맥락에서 보면 $\hat{C}$는 $\bar{C}$의 Riemann approximation이라고 할 수 있으며 앞선 질문은 이 approximation의 질 즉, continuous-time 함수에서 일부 샘플들만 취함으로써 우리가 얼마나 정보를 버렸는지에 대해 묻는 것과 같습니다.

이에 대한 정답은 놀랍게도 해당 물리적 현상이 "그렇게 빨리 변하지 않는다"는 가정 하에, 두 representation이 "완벽히 일치한다"는 것입니다. 즉, continuous-time function과 우리가 얻은 측정 샘플들 간의 정보 손실이 전혀 없다는 뜻이죠.

잠시 가정에 대한 걱정을 내려놓고, 이 사실이 얘기해주는 것에만 집중해보면 매우 놀랍게도
  1. 아날로그와 디지털 세계가 완전히 공존하는 것이 가능하다는 뜻이며 
  2. 우리가 두 세계 사이를 오갈 수 있는 매우 강력한 도구를 갖고 있다는 것입니다 (sampling theorem). 
20세기 초에 발견된 이 놀라운 정리는 우리가 가진 샘플들을 바탕으로 임의의 continous-time function를 알아내는 것이 가능하다는 것을 말해주는데요:
$$f(t)=\sum_{n=-\infty}^\infty c_n \frac{\sin(\pi(t-nT_s)/T_s)}{\pi(t-nT_s)/T_s}.$$ 따라서 이론적으로는 우리가 측정값들을 가지고만 있다면 이를 바탕으로 continous-time 형태로 표현하는 것이 가능하며, 이것은 이어서 우리가 갖고 있는 매우 강력한 수학적 도구인 미분을 사용하여 함수를 분석하는 것이 가능해진다는 것을 뜻합니다.

더 좋은 점은 continous-time에서 이루어진 미분과 같은 분석이 항상 discrete-time에 대응하는 방식이 존재하여 굳이 우리가 얻은 측정값들을 가지고 continous domain으로 옮겨서 분석한 후, 다시 discrete domain으로 내려오는 복잡한 방식을 취할 것 없이 discrete domain에서 바로 분석을 하면 된다는 것입니다.

Discrete과 continuous representations 사이의 equivalence는 우리가 샘플을 얻는 속도에 비해 다루는 신호가 얼마나 충분히 "느린가"에 달려 있습니다. 즉, 연속된 샘플을 측정하는 사이에 신호가 갑자기 이상하게 움직이지 않고 충분히 부드럽게 (smooth and well behaved) 움직인다면 문제가 없다는 뜻입니다.

그래서 sampling theorem이 해주는 역할은 (좀 더 쉽게 설명하자면) 신호가 갖는 최대 주파수와 우리가 얼마나 자주 혹은 빨리 샘플을 얻어야 하는지에 대한 정량적인 기준을 알려주는 것입니다. 대다수의 학부 수준 디지털 신호 처리 과목의 반절 혹은 그 이상은 이 sampling theorem을 배우기 위한 준비와 theorem의 의미에 대해 공부하는 것이겠습니다. 특히 주파수 영역은 Fourier transform을 사용하여 알아낼 수 있기에 이를 신호 처리 과목에서 중요하게 다루며 배우는 것이라 할 수 있는데, 재미있는 점은 Fourier transform이라는 것 자체가 주기성을 띄는 함수들을 "셀 수 있는" 값들로 표현하기 위한 도구로서 사용된다는 것입니다. 도구만 달라졌을뿐 앞에 손가락으로 숫자를 세던 것이 생각나지 않으시나요?
"Everything comes together."

Discrete Amplitude


시간 연속성에 대한 문제는 sampling theorem으로 어느 정도 해결이 되었지만, 여전히 남아있는 문제가 하나 있습니다. 현실 세계의 한계로 인해 실제 측정을 할 때 생기는 오차는 우리가 어찌 할 수 없는 문제이지요.

만약 우리가 analytical model을 다룬다면 시간축뿐만 아니라 함수 값 역시도 연속적인 성격을 갖고 있는데요. 그러나 현실에서는 절대로 이와 같은 무한대의 정밀성을 얻을 수 없다는 것은 자명합니다. (아무리 온도계의 눈금을 잘게 쪼개어 기록을 하더라도 한계가 있는 것처럼)

따라서 실제로는 우리가 얻는 측정값들도 결국 유한한 숫자들의 집합이고, 그렇다면 이들은 셀 수 있기에 정수로 mapping하는 것이 가능해집니다. 이러한 과정을 quantization이라고 부르고 이는 sampling과 함께 digital signal을 얻는데 필수적인 요소가 되는데요.

Quantization은 정보 손실을 어쩔 수 없는 것으로 받아들인다는 점에서 연속체 문제를 시간에 비해 매우 거칠게 해결하는 것이라 할 수 있습니다. 여기에는 그럴 수 밖에 없는 이유가 있는데 그게 바로 신호 처리를 하다보면 언제나 만나게 되는 "noise"입니다.

우리가 어떠한 기계적 기록 장치를 쓴다고 해도 아날로그 기록을 하는 기기라면 언제나 noise가 함께하게 됩니다. Noise는 자연에서 오는 것이고 이를 완전히 제거하는 것은 불가능하기 때문에 신호 처리를 할 때 일정 수준의 정밀성으로 만족하는 정도로 합의를 하는 것이죠.

문제는 noise가 단순히 측정에서만의 문제가 아니라 처리를 할 때도 함께한다는 점입니다.
여기서 디지털 신호 처리의 또 다른 장점이 나오는데, 디지털 신호 처리는 언제나 셀 수 있는 정수의 수열을 다루기 때문에 디지털 영역에서는 processing으로 인한 noise가 생기지 않습니다.

매우 자명한 예로 신호를 복제하는 것을 생각해보면, 테이프를 복사하는 것은 원본 테이프를 복사본과 그 복사본을 이용한 다음 복사본으로 넘어갈 때마다 추가적인 nosie가 더해져서 점점 음질이 열화되지만 mp3의 경우 원본과 복사본이 근본적으로 차이가 없다는 것을 알 수 있습니다.

Terminology


마지막으로 용어에 대해 한가지 짚고 넘어가겠습니다. Amplitude에 대한 정확성은 사실 하드웨어에 달린 문제로, 예를 들자면 CD와 DVD는 서로 precision 즉 샘플 당 담을 수 있는 정보량에 차이가 있습니다. 이렇게 amplitude에 대한 정밀성은 하드웨어에 의존적이므로 사실상 신호 처리 이론에 대해 배우거나 개발할 때는 quantization을 고려하지 않고 마치 연속된 실수 값인 것 마냥 취급하게 됩니다. 따라서 사실상 우리가 앞으로 배우는 것은 엄밀히 말하자면 모두 discrete-time signal processing이라 불러야 맞고 digital signal processing은 실제 기기의 영역에서 이뤄지는 일임을 알아야 합니다. 그러나 quantization을 고려하지 않는 것이 좀 더 이론적으로 다루기도 쉽고 일반적인 분석이 가능하기 때문에 이를 잘 구별하지 않고 digital signal processing이라 얘기한다는 점을 분명히 알아야겠습니다.

아 마지막으로 글을 읽는데 순서를 추천드리자면 이 다음에 (9-1)로 넘어가시는 것을 권해드립니다. 그렇게 하는 것이 신호처리를 배우는 목적을 이해하고 전체적인 감을 잡는 것에 훨씬 도움이 된다고 생각합니다. 

To be continued ... (planned)


  • Preface 
  • What is Digital Signal Processing? ($\leftarrow$)
  • Discrete-Time Signals (2)
  • Signals and Hilbert Spaces
    • Euclidean Spaces and Hilbert Spaces (3-1
    • Subspaces, Bases, Projections, Haar basis (3-2)
  • Fourier Analysis
  • Interpolation and Sampling (9-1 $\leftarrow$ next to read)
    • Interpolation
    • Sampling theorem
    • Aliasing
  • Multirate Signal Processing
    • Downsampling
    • Upsampling
    • Oversampling



2019년 5월 7일 화요일

공이 점점 비눗방울처럼 변할 때 (When ball becomes a soap bubble)

공이 점점 비눗방울처럼 변할 때


이전에 소개했던 박스 안에 넣은 공의 지름이 박스보다 클 때처럼 고차원으로 갈 때 우리의 직관이 얼마나 달라질 수 있는지를 알려주는 또 다른 좋은 예시를 소개해보자.

구의 부피


또다시 공(ball)이다! 수학적인 용어에서의 공은 간단히 말해 겉껍질이 자기보다 한차원 낮은 구(sphere)로 쌓여있는 닫힌 공간 전체, 즉, 안이 꽉 찬 공간을 뜻한다. 1차원 공(ball)은 선(line segment)이고 2차원 공은 원반(disk), 3차원 공은 음...공(ordinary ball)이다. 대응되는 구(sphere)를 생각해보면 0차원 구는 시작과 끝 점(point), 1차원 구는 원(circle), 2차원 구는 구(ordinary sphere)다.

이런 공의 부피를 바탕으로 초등학교 시절 배운 내용 수준만으로 아주 쉽고 간단하게 고차원에서는 직관이 우리를 배반한다는 것을 보일 수 있다.

이전 글과 같이 먼저 쉽고 우리 직관이 잘 통하는 2차원에서부터 시작해보자:


우리 모두 초등학교 때, 원의 부피, 즉 2차원에서의 넓이를 구하는 것은 배웠을 것이다: $$V_2(r)=\pi r^2.$$ 한 차원 더 나가서,


3차원 공의 부피는 $$V_3=\frac{4\pi}{3}r^3$$이라는 것도 열심히 외웠을 것이다.

그리고 아마도 이걸 $d$차원에 대해 일반화하는 공식은 테이블 형태로 "심화 학습" 뭐 이런 형태로 가볍게 보여주고 지나갔을 것이다: $$V_d(r)=k_d r^d.$$ 여기서 $k_d$는 상수다.

구각 (Spherical shell)


이제부터 좀 재미있는 실험을 할텐데, 원점을 중심으로 반지름이 1인 구와 반지름이 $1-\epsilon$으로 그보다 아주 약간 ($\epsilon\ll 1$만큼) 공 두 개를 준비하고 이 두 공 부피의 차를 구해보자: $$V_d(1) - V_d(1-\epsilon).$$
이걸 겉 껍데기를 구하는 것이라 해서 구각(spherical shell)이라 하는데 두 공의 반지름의 차이가 $\epsilon$만큼 나기 때문에 우리가 생각하는 겉껍질(구각)이 차지하는 부피는 매우 작다.

만약 정확히 그 비율이 얼마나 되는지 알고 싶다면 반지름이 1인 구와 위에서 구한 구각의 비율을 구하면 될텐데 이 비율은 간단히: $$\frac{V_d(1) - V_d(1-\epsilon)}{V_d(1)}=1-(1-\epsilon)^d$$가 될 것이다.

이제 준비물은 모두 모았으니 사고 실험을 해보면 재미있는 일이 벌어지는 것을 알 수 있다.  점점 고차원으로 갈수록 ($d\rightarrow \infty$) 두번째 항의 값이 0에 가까워지고 공과 구각의 비율이 1로 수렴한다! 즉, "공이 점점 비눗방울처럼 바뀌는 것" 이다.

모든 부피가 껍데기에만 몰려있고 안이 텅텅 비어있는 매우 요상한 "속이 꽉찬" 공이 될 것이다. 이 역시도 고차원으로 넘어갈 때, 우리의 직관이 얼마나 틀릴 수 있는지 보여주는 좋은 예시로 이 글을 읽는 다른 분들에게도 brain candy가 되었길 기대한다.

딴 이야기 

(for those who are interested in GANs)


재미있는 GAN blog 글로 유명한 inFERENCe가 "Gaussian Distributions are Soap Bubbles"라는 제목으로 글을 써서 화제가 된 적이 한 번 있는데, 생각보다 복잡하게 설명을 해서 이해하기 어려울 수 있지만 사실 지금 한 얘기를 다른 방식으로 열심히 적은 것이다.

GAN 모델을 학습시킨 다음 High dimensional Gaussian latent space에서 walking을 하기 위해 두 latent vector간의 interpolation을 할 때, 왜 linear interpolation을 하면 문제가 될 수 있는지 이 글을 읽으신 분들이 이해가 쉽게 될 것이라 생각한다.

어떤 의미에서는 중간이 텅 비어있는데 겉껍질을 타고(polar) 움직여야지(interpolate) 중간을 쑥 뚫고(linear) 움직이면 본적이 없는 latent vector가 model로 들어갈 수 있기 때문이다.

다음 읽을거리





2018년 9월 2일 일요일

[The Art of Readable Code, 읽기 좋은 코드가 좋은 코드다] 2. 이름에 정보 담기

표면적인 수준에서의 개선



"표면적 수준이란 좋은 이름을 짓고, 좋은 설명을 달고, 코드를 보기 좋게 정렬하는 따위를 의미한다."

책의 첫 단락은 표면적인 수준에서의 개선부터 시작합니다. 이런 수정은 코드를 통째로 바꾸거나 동작하는 방식을 변화시키지 않고 '그 자리에서' 곧바로 만들 수 있기에 첫 시작으로 매우 적절하다 생각합니다.

물론 가독성에 관련된 논의는 이 수준보다 더 나아가 많은 내용을 담고 있겠으나 이는 차차 살펴갈 것이며 먼저 1부에서는 폭넓게 적용할 수 있고, 그다지 많은 노력을 요구하지 않는 내용을 우선적으로 다룹니다.

이름에 정보 담기


변수, 함수, 혹은 클래스 등의 이름을 결정할 때는 항상 같은 원리가 적용합니다. 
"이름을 일종의 설명문으로 간주해야 한다."
충분한 공간은 아니지만, 좋은 이름을 선택하면 생각보다 많은 정보를 전달할 수 있다는 것이죠. 구체적으로는 아래의 여섯 가지 방법을 제안합니다.
  • 특정한 단어 고르기
  • 보편적인 이름 피하기 (혹은 언제 그런 이름을 사용해야 하는지 깨닫기)
  • 추상적인 이름 대식 구체적인 이름 사용하기
  • 접두사 혹은 접미사로 이름에 추가적인 정보 덧붙이기
  • 이름이 얼마나 길어져도 좋은지 결정하기
  • 추가적인 정보를 담을 수 있게 이름 구성하기
앞으로는 책에 나온 내용을 모두 다 소개하기 보다는 개중 제가 재미있었던 내용들을 좀 골라서 예시와 함께 알아보겠습니다. 

특정한 단어 고르기


매우 구체적인 단어를 선택하여 "무의미한" 단어를 피하자. 

예를 들어 "get"은 지나치게 보편적입니다.

def GetPage(url):
    ...

여기서 "get"보다는 메소드가 어디에서 페이지를 가져오는 지 알려줄 수 있게 FetchPage() 혹은 DownloadPage()와 같이 구체적으로 명명하는 것이 더 좋습니다.

사실 위 예시보다 다음 예시가 더 좋았는데요. 다음과 같이 BinaryTree 클래스에서

class BinaryTree {
    int Size();
    ...
}

우리는 Size() 메소드가 반환하는 것이 무엇일 지 이름만 봐서는 알 수 없습니다. 트리의 높이, 노드의 개수, 혹은 트리의 메모리 사용량이 될 수도 있겠죠.  따라서 Height(), NumNodes(), 혹은 MemoryBytes() 등이 더 의미 있는 이름이라는 것에는 모두 동의하리라 생각합니다. 

같은 맥락에서 저자들은 thesaurus를 뒤져보고 더 나은 이름을 생각하기를 권합니다. 다만 너무 "재치" 있는 이름보다는 명확하고 간결한 이름이 더 좋습니다. 다음에 이어지는 내용들도 사실 같은 내용인데 예제들과 소소한 팁 위주로 살펴보곘습니다.

tmp나 retval 같은 표편적인 이름 피하기


"변수값을 설명하는 이름을 사용하라"

예를 들어, 다음과 같이 Euclidean norm을 계산하는 자바스크립트 코드에서

var euclidean_norm = function (v) {
    var retval = 0.0;
    for (var = i = 0; i<v.length; i+=1)
        retval += v[i];
    return Math.sqrt(retval);
};

retval보다는 sum_squares라고 이름을 붙여준다면 변수의 목적을 바로 이해할 수 있으며 나중에 버그를 잡을 때도 용의합니다.

retval += v[i]; 부분이 sum_squares += v[i]; 였다면 훨씬 눈에 잘 띄었겠죠.

물론 아래와 같이 정말로 대상이 짧게 임시적으로만 존재하고, 임시적 존재 자체가 변수의 가장 중요한 용도일 때는 tmp와 같은 변수를 사용할 수 있겠습니다.

두 변수를 서로 교환하는 알고리즘 예:

if (right<left) {
    tmp = right;
    right = left;
    left = tmp;
}

같은 맥락으로 i, j, iter, it 같은 이름이 인덱스나 루프 반복자로 사용되는 것은 충분히 괜찮습니다. 다만 이 역시도 디버깅의 용이성을 위해서 아래와 같이 소속을 표현해준다면 더 좋겠죠.

(i, j, k) -> (club_i, members_j, users_i) or (ci, mj, ui)

활용 예:
if (clubs[ci].members[ui] == users[mi]) # 버그! 처음 문자가 일치 하지 않는다.

따라서 표편적인 이름이 항상 나쁜 것은 아니지만, 이를 사용하려면 꼭 그렇게 해야하는 이유가 있어야 합니다. 


추가적인 정보를 이름에 추가하기 


단위(sec, millisecond, kg 등)를 포함하거나 다른 중요한 속성(unsafe, utf_8 등)이 있을 때는 변수에 그런 내용을 추가해주면 좋습니다. 

start -> start_ms, elapsed -> elapsed_ms
html -> html_utf-8 # html의 바이트가 UTF-8으로 변환되었다. 

이름은 얼마나 길어야 하는가?


만일 변수가 좁은 scope (예: 끽해야 몇 줄 안의 함수 scope)에서 사용된다면 멤버 변수가 "m"과 같이 매우 짧은 이름을 사용해도 별 문제가 없으나 이 변수의 scope이 클래스나 전역으로 넓어지면 가독성이 매우 떨어지게 되므로 상황에 따라 잘 사용하라고 하는군요. 

게다가 요즘은 긴 이름을 입력하는 것이 자동완성 기능으로 매우 편해져서 그리 주저할 일이 아닙니다. 그렇기 때문에 약어와 축약형은 매우 보편적인 경우(string-> str과 같이)를 제외하고는 지양하는 편이 좋겠습니다. 

이에 좀 더 더한다면 ConvertToString()에서 ToString()과 같이 불필요한 단어를 제거해서 간결하게 만드는 등의 팁이 있으나 앞의 내용들이 더 핵심에 가까운 것으로 보입니다. 

이로써 이름에 정보를 넣는 방법에 대해 요약해보았습니다. 

책에서 다음 장은 의미를 오해하기 쉬운 이름들에 대한 팁입니다만 사실 오늘 소개한 내용에 어느 정도 포함되는 것 같습니다. 다음 글에서는 미학(Aesthetics) 즉 "눈을 편하게" 하는 코드에 대해 정리하겠습니다.