안녕하세요.

이번 글(Part2)에서는 지난 Part1에 이어서 GAN의 수학적 증명그 외 나머지 부분들에 대해 정리하려고 합니다.

 

(↓↓GAN part1 ↓)

https://89douner.tistory.com/329?category=908620 

 

5-1. GAN (Part1. GAN architecture)

안녕하세요. 이번 글에서는 최초의 GAN 논문인 "Generative Adversarial Nets"을 리뷰하려고 합니다. 우선, GAN이라는 모델이 설명할 내용이 많다고 판단하여 파트를 두 개로 나누었습니다. Part1에서는 GAN a

89douner.tistory.com

 

 

논문의 section 4, 5, 6 부분들 마저 다룰 예정인데, 설명의 편의를 위해 'section 5'와 'section 6'의 순서만 바꾸도록 하겠습니다.

 

  • Section 4: Theoretical Results
  • Section 6: Advantages and disadvantages
  • Section 5: Experiments

 

먼저, "section 4: Theoretical Results"리뷰하기 딥러닝 모델을 설계할 시 필요한 몇 가지 기준(질문)들에 대해서 이야기 하려고 합니다. 

 

 

 

 

 

1. 딥러닝 모델 설계를 위한 네 가지 기준(질문)

딥러닝 모델을 확률 모델로써 설계할 때에는 네 가지 기준(질문)을 충족하는지 따져봐야 합니다. (물론 더 많은 기준(질문)이 있겠지만 GAN 논문에서는 크게 네 가지 기준으로 요약하고 있습니다.

 

(뒤에서 더 자세히 설명하겠지만, 실제 neural network가 사용되면 아래 기준을 이상적으로 만족하는게 불가능하다고 합니다. 그러니, 아래 기준들은 딥러닝 설계 시 이상적인 guideline 정도로 보시면 좋을 것 같습니다.)

 

  1. 설계한 확률(딥러닝)모델이 tractable 한 것인가? (계산 시스템 관점에서 충분히 다룰 수 있는 알고리즘인가?)
  2. 설계한 확률(딥러닝)모델이 최적해(global optimum)를 갖는가?
  3. 설계한 확률(딥러닝)모델이 최적해(global optimum)에 수렴하는가?
  4. 설계한 확률(딥러닝)모델의 최적해(global optimum)을 찾을 수 있는 알고리즘이 존재하는가?

 

먼저, 첫 번째 질문tractable과 관련한 답은 이미 part1에서 했기 때문에 아래 링크를 참고해주시면 좋을 것 같습니다.

 

(↓아래 링크에서 “3.Adverarial nets” → "[3-1-1-. First paragraph & Second sentence]" 부분 참고)

https://89douner.tistory.com/329

 

5-1. GAN (Part1. GAN architecture)

안녕하세요. 이번 글에서는 최초의 GAN 논문인 "Generative Adversarial Nets"을 리뷰하려고 합니다. 우선, GAN이라는 모델이 설명할 내용이 많다고 판단하여 파트를 두 개로 나누었습니다. Part1에서는 GAN a

89douner.tistory.com

 

 

 

나머지 질문들은 "4. Theoretical Results"를 리뷰하면서 설명해보도록 하겠습니다. 

 

 

 

 



 

4. Theoretical Results

[ 4-1. Global optimality of \(p_{g}=p_{data}\) ]

 

"설계한 확률(딥러닝)모델이 최적해(global optimum)를 갖는가?"

 

딥러닝에서 분류(classification)하는 문제에서는 최종 losscross-entropy 값이 0에 도달하기를 바랍니다.

 

<그림 출처: https://towardsdatascience.com/cross-entropy-loss-function-f38c4ec8643e>

 

 

 

"그렇다면, GAN의 최종 loss는 어떠한 값을 갖어야 global optimum이라고 할 수 있을까요?"

"즉, 최종적으로 도달하고자 하는 loss 값은 무엇일까요?

 

 

지금부터 이에 대한 답을 해보도록 하겠습니다.

 

 

Generator 관점에서 MinMax problem (value function)은 \(P_{g}=P_{data}\) 에서 global optimum 값을 갖아야 합니다. 직관적으로 봤을 때, GeneratorData와 유사한 distribution을 형성하는 지점인 곳에서 global optimum 값을 찾게 되면 학습을 중단하겠죠?

 

이 논문에서는 optimal discriminator의 global optimum 값은 아래와 같은 수식에 의해 도출 된다고 합니다.

 

\(D^{*}(x)=\frac{P_{data}(x)}{P_{data}(x)+P_{g}(x)}\)

 

 

위 수식의 직관적인 설명은 아래와 같습니다.

 

\(P_{g}=P_{data}\) 일 경우 \(D^{*}(x)=\frac{1}{2}\) 값을 갖는데, 이것이 의미하는 바는 discriminator가 가짜 이미지와 진짜 이미지를 판별할 확률이 모두 \(\frac{1}{2}\)라는 사실과 값습니다. 즉, 가짜와 진짜를 완벽히 혼동한 상태인 것이죠. 그러므로, GAN loss function인 V(D,G) 값이 \(\frac{1}{2}\)에 가까이 도달하면 학습을 종료하면 됩니다. (CNN loss인 Cross entropy 에서는 0값에 도달하면 보통 학습을 중단시키죠)

 

"그럼, 이제부터 어떻게 optimal discriminator 수식이 V(D,G) 수식에서 \(D^{*}(x)=\frac{P_{data}(x)}{P_{data}(x)+P_{g}(x)}\) 수식으로 유도되는지 수학적으로 살펴볼까요?" 

 

 

(유도과정과 관련된 내용은 아래 영상 내용을 기반으로 작성했으니 참고해주세요.)

https://www.youtube.com/watch?v=odpjk7_tGY0 

 

 

 

 

 

 

Optimal discriminator 상태에 도달했다는 것은 Generator관점에서 봤을 때 이미 \(P_{data}=P_{g}\) 상태로 학습이 거의 다 됐다는 것을 의미합니다.  G가 이미 최상의 상태에 도달했다고 가정하여 Gfix시키고 optimal discriminator D*(x)에 대한 수식만 찾는 것이죠.

 

위와 같은 사실을 봤을 때, GAN이라는 모델은 generator와 관련된 loss가 아닌 discriminator와 관련된 loss에 의해 학습을 종료할지 말지 결정하게 되는 것이죠. 바꿔 말하자면, optimal discriminator의 값을 찾기 위해 discriminator(D) 부분만 고려하겠다는 것입니다.

 

 

 

위 수식을 보면 G(z)를 x로 바꿔 주면서 \(E_{z\sim ~p_{z}(z)}\) 수식부분이 \(E_{x\sim ~p_{g}(x)}\) 로 변경된 것을 확인할 수 있습니다. 이것이 가능한 이유는 G(z)의 차원이 곧 X차원과 동일하여 G(z)에서 발생한 값을 X 차원 상의 하나의 x값으로 표현(=mapping)할 수 있기 때문입니다.

 

  • Pz(z): low dimension distribution,  z = 100
  • Pg(x): high dimension distribution, x = 64x64 

 

 

위와 관련된 내용아래 링크(글)에서 3. Adversarial nets” “[3-2-2. Second paragraph & Second sentence]" 부분을 참고해주세요. 

 

https://89douner.tistory.com/329?category=908620 

 

5-1. GAN (Part1. GAN architecture)

안녕하세요. 이번 글에서는 최초의 GAN 논문인 "Generative Adversarial Nets"을 리뷰하려고 합니다. 우선, GAN이라는 모델이 설명할 내용이 많다고 판단하여 파트를 두 개로 나누었습니다. Part1에서는 GAN a

89douner.tistory.com

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(지금까지 설명한 내용논문에서는 아래와 같이 함축해서 설명하고 있습니다)

 

 

 

앞서 \(\frac{a}{a+b}\)에서 global optimum을 갖는걸 파악했습니다.

 

그렇다면, a=b or \(P_{data}=P_{g}\)라는 조건 하에 global optimum을 갖는지,

global optimum 값이 왜 1/2이 되는지 수학적으로 증명해보겠습니다.

 

 

 

 

 

 

 

 

(지금까지 설명한 내용을 논문에서는 아래와 같이 함축해서 설명하고 있습니다)

 

 

 

정리하자면, 앞서 언급했던 질문인 "설계한 확률(딥러닝)모델이 최적해(global optimum)를 갖는가?" 에 대해서 

"최적해(global optimum)"을 갖는다고 할 수 있습니다.

 

 

"다시 말해, MinMax 구조의 함수에서 \(P_{data}=P_{g}\)일 때, global optimum을 갖는다고 할 수 있습니다.”

 

 

 

 

 

 

[ 4-2. Convergence of Algorithm 1 ]

앞서, GAN 이라는 확률(딥러닝) 모델은 loss를 통해 살펴 봤듯이 최적해(global optimum)존재하는걸 볼 수 있었습니다. 딥러닝 모델을 해(solution)를 찾을 수 있는 조건 중 하나가 loss가 convex function인지 확인하는 것입니다.

 

 

"그래야 grident descent 와 같은 iterative optimization 방식을 통해 해를 찾을 수 있기 때문입니다."

 

 

(↓iterative optimization과 딥러닝과의 관계를 설명한 글; "3.Adversarial nets" -> "[3-3-2. Third paragraph & The last sentence]" 부분을 참고)

https://89douner.tistory.com/329?category=908620 

 

5-1. GAN (Part1. GAN architecture)

안녕하세요. 이번 글에서는 최초의 GAN 논문인 "Generative Adversarial Nets"을 리뷰하려고 합니다. 우선, GAN이라는 모델이 설명할 내용이 많다고 판단하여 파트를 두 개로 나누었습니다. Part1에서는 GAN a

89douner.tistory.com

 

 

그럼, 딥러닝 모델 설계 시 고려해야 하는 4가지 질문 중, 세 번째 질문에 대한 답을 설명드려보겠습니다.

 

"설계한 확률(딥러닝)모델이 최적해(global optimum)에 수렴하는가?"

 

위에 있는 질문을 바꿔서 표현하면 "\(p_{g}\)가 \(p_{data}\)로 수렴할 수 있는가?"로 표현할 수 있습니다. 즉, generative model인 \(p_{g}\) 관점에서 loss 함수가 (global optimum으로) convergence(수렴) 할 수 있는지 따져야 하는 것입니다.

 

"Generative model인 \(p_{g}\) 관점에서 loss 함수가 (global optimum으로) convergence(수렴) 할 수 있는지 따지기 위해서는 'D를 고정시키고, loss 함수가 convex한지 확인하는 것' 입니다." 

 

 

 

아래 그림을 잠깐 설명해보겠습니다. D는 고정했기 때문에 \(U(P_{g},D)\) 를 \(P_{g}\) 관점에서 보면 D는 (고정된) 상수값입니다. 바꿔말해, \(P_{g}\) 관점에서 보면 \(U(P_{g},D)\)의 변수는 \(P_{g}\)인 셈인 것입니다. 결국, \(P_{g}\)가 학습함에 따라서 변할 텐데, 변하는 \(P_{g}\)에 따라서 \(U(P_{g},D)\)convex한지 알아봐야 iterative optimization(=ex: gradient descent) 방식으로 global optimum을 찾을 수 있는지 확인 할 수 있습니다.

 

 

위의 설명 중에서 "어떤 함수를 미분했을 때, 해당 함수가 상수 값을 갖는다면 그 함수는 convex하다고 할 수 있다"는 개념이 있습니다. 예를 들어 보충 설명하면, 2x+1라는 수식에서 x에 대해서 미분하면 미분값=2가 나옵니다. 즉, 어떤 수식을 x로 미분 했더니 상수가 나오면 그 수식은 선형함수가 되는 것입니다. 그리고, 선형함수는 convex 라고 할 수 있는데, 특정 구간 (ex=(0,1))을 설정해놓으면, 해당 구간에서 minimum 값을 찾을 수 있게 됩니다.

 

(↓↓↓linear function이 convex function 임을 보여주는 글↓↓↓)

https://89douner.tistory.com/221?category=985926 

 

[Convex function]2-2. Example of Convex function

※시간이 충분하지 않아 필기로 정리한 내용을 아직 블로그 글로 옮기지 못해 이미지로 공유하는점 양해부탁드립니다. 아래 내용의 키워드는 다음과 같습니다. Exponential function, affine function, powe

89douner.tistory.com

 

 

 

 

 

 

 

 

(지금까지 설명한 내용을 논문에서는 아래와 같이 함축해서 설명하고 있음)

 

 

 

[그 외 위에서 본 수식과 관련된 background or 용어]

 

 

 

 

[ 4-2. Algorithm 1 ]

"설계한 확률(딥러닝)모델의 최적해(global optimum)을 찾을 수 있는 알고리즘이 존재하는가?"

 

 

이 논문에서는 아래와 같은 방식으로 D와 G를 서로 학습함으로써 최적해(global optimum)을 찾을 수 있음을 보여줬습니다.

 

 

위의 알고리즘을 실제로 코딩할 때 아래와 같이 구현할 수 있습니다. (D학습시 따로 k step을 두진 않은 것 같네요)

 

(↓↓D, G 관련 loss가 왜 아래와 같이 변하는지는 GAN part1에서 설명 함)

 

 

[Neural network를 Generative model에 도입할 경우]

 

GAN을 통해 생성하는 데이터의 분포 \(p_{g}\)를 추정하고 최적화 하는 것이 아니라, \(p_{g}\)를 생성하는데 직접적인 영향을 미치는 parameter인 \(\theta_{g}\)를 추정하고 최적화 합니다. 또한, 엄밀히 말하자면 수학적인 증명에서는 generative model, discriminative model이 neural network를 사용한다는 언급이 없습니다. 그런데, Generative model을 MLP(multilayer perceptron; neural network; deep learning)와 같은 것으로 설정하게 되면 실제로 최종 loss function 자체가 convex하지 않을 수 있고, 즉 multiple critical points를 가질 수 있습니다. 하지만, 마법같은 MLP는 이러한 theoretical guarantees가 굳이 보장되지 않고도 나름 생성모델에서 잘 작동한다고 주장하고 있습니다.

 

 

 

 

5. Advantages and disadvantages

이 부분("5. Advantages and disadvantages")은 GAN의 대표적인 disadvantage라고 할 수 있는 mode collapse에 대해서만 설명하도록 하겠습니다.

 

먼저, mode라는 용어에 대해서 이해하도록 하겠습니다.

 

보통 통계학에서 mean, median, mode, range라는 용어가 사용되는데, 해당 용어들이 의미하는바는 아래와 같습니다.

 

<그림 출처. https://danielmiessler.com/blog/difference-median-mean/>

 

 

위의 개념들을 distribution 상에서 설명하면 아래와 같이 표현할 수 있습니다.

<그림출처. https://medium.com/@nhan.tran/mean-median-an-mode-in-statistics-3359d3774b0b>

 

<그림 출처. https://velog.io/@tobigs-gm1/basicofgan>

 

 

 

쉽게 말해 mode는 빈도수가 가장 많은 수를 일컫습니다.

 

"The mode is the most frequent value."

 

 

그렇다면 이제 mode collpase에 대해 설명해보도록 하겠습니다.

 

MinMax Value function을 살펴보면, 학습 시 G(z)가 생성하는 이미지의 종류에 대해서는 고려하지 않습니다. 예를 들어서, G(z)가 MNIST의 1이라는 이미지를 생성하는데 D가 계속해서 판별을 못하고, G(z)가 생성하는 MNIST의 2라는 이미지만 잘 판별해도 되면 결국 value loss 값은 낮아지게 되는 것이죠. 극단적으로 설명해서 MinMax 방식으로 서로 학습하면 D가 만족하는 (판별을 잘 할 수 있는) 이미지(from G(z))만 생성하도록 G가 학습할 것이며, 결국 (서로 좋은쪽으로만) 편향되게 D와 G는 alternative하게 학습하게 될 것 입니다. 

 

 

앞서 설명한 것을 다르게 표현하면, G(z)는 MNIST의 1의 distribution은 잘 표현해주지 못하고, 2라는 이미지의 distribution만 잘 표현해도 전체 value function의 loss 값은 낮게 나올 수 있습니다. 이렇게 되면 Generative model G가 특정 숫자만 생성하게 되겠죠.

 

 

Mode collpase를 정리하자면 아래와 같이 표현할 수 있습니다.

 

"Mode collapse happens when the generator can only produce a single type of output or a small set of outputs. This may happen due to problems in training, such as the generator finds a type of data that is easily able to fool the discriminator and thus keeps generating that one type."

 

 

 

 

위의 그림을 설명하면 다음과 같습니다.

 

먼저 3개의 검은색 실선이 실제 이미지를 나타내는 것이라고 볼 수 있습니다예를 들어, 각각실선들은 금발여성, 흑발과 안경을 쓰고 있는 남성, 흑발 여성을 나타낸다고 해보겠습니다.

 

"즉 우리가 원하는 목표는 실선 3개를 모두 표현해줄 수 있는 확률 분포를 익히는 것이라고 볼 수 있습니다."

 

가운데 실선에 해당하는 데이터 셋이 제일 많다고 하면, VAE는 제일 데이터 셋이 많은 그룹에 맞게 distribution을 형성하면서 동시에 normal distribution을 이용해 주변 이미지 그룹들도 다 포괄할 수 있도록 학습을 하기 때문에 모든 데이터 그룹을 포괄하려는 것을 볼 수 있습니다.

 

반대로 GANgenerator가 만드는 이미지 그룹을 discriminator가 더 이상 구별해내지 못할 때 (real image가 들어왔을 때 맞출 확률 ½, fake image가 들어왔을 때 맞출 확률 ½ 이 될 때) 학습이 종료가 됩니다. 그렇기 때문에 이미지 데이터 셋이 많은 (가운데 실선에 해당하는) 그룹만 학습하다 끝내버리면 해당 그룹만 잘 generation해주는 현상이 발생 할 수 있습니다.

 

각각의 실선 (이미지 그룹)이 우리가 representation (By generator)해야 할 중요한 mode라고 부르기도 하는데, GAN에서는 이러한 mode들을 잘 학습하는 것이 안되는 붕괴(collapsing) 현상이 일어난다고 하여 mode collapsing의 단점을 갖고 있다고도 합니다.

 

 

 

그 외 mode collpase에 대한 설명이 필요하시면 아래 링크를 참고해주시면 좋을 것 같습니다.

http://jaejunyoo.blogspot.com/2017/02/unrolled-generative-adversarial-network-1.html

 

초짜 대학원생의 입장에서 이해하는 Unrolled Generative Adversarial Networks (1)

Easy explanation for unrolled generative adversarial network (쉽게 풀어 설명하는 Unrolled GAN)

jaejunyoo.blogspot.com

 

https://wandb.ai/authors/DCGAN-ndb-test/reports/Measuring-Mode-Collapse-in-GANs--VmlldzoxNzg5MDk

 

Measuring Mode Collapse in GANs

Evaluate and quantitatively measure the GAN failure case of mode collapse - when the model fails to generate diverse enough outputs.

wandb.ai

 

 

 

 

 

 

 

6. Experiments

 

사용된 데이터셋

  • MNIST
  • Toronto Face Database (TFD)
  • CIFAR-10

 

Activation function

  • Generator nets: a mixture of rectifier activations and sigmoid activations
  • Discriminator net: maxout activations

 

Drop out

  • discriminator net 학습시에만 drop out 적용

 

 Noise

  • 이론적으로는 intermediate layers of generator에 주겠금 되어있음
  • 하지만, 실제 구현 상에서는 "the bottommost layer of the generator network"의 input에 해당하는 data에 noise를 주어 학습 시킴

 

"Conventionally people usually draw neural networks from left to right or from bottom-up (input to output). So by “top layer” it’s more likely to be the last (output) layer."

 

<그림 출처: https://velog.io/@hwany/GAN>

 

 

 

아래 그림 처럼 논문에서는 1과 5 사이의 vector linear interpolation, 7과 1사이의 vector linear interpolation 했을 때의 결과를 보여줍니다.

 

 

 

아래 수식을 이용하면 실제 이미지 데이터에 대응하는 z 값을 찾을 수 있습니다.

 

이렇게 찾은 z값들 간에 vector linear interpolation을 하게 되면, 7과 1사이의 z 중간 값이 9가 나오는걸 확인할 수 있습니다.

 

 

 

 

 

 

 

실제 논문에서는 결과에 대한 여러 해석들이 있는데, 요즘에 사용하고 있는 GAN 평가지표와는 다른 부분이 있어 생략하도록 하겠습니다.

 

 

 

 

지금까지 GAN 논문에서 설명하고 있는 이론적 배경에 대해 다루어봤습니다.

감사합니다.

 

 

 

[Reference]

1. Yunjey Choi, NAVER AI Lab

https://www.youtube.com/watch?v=odpjk7_tGY0 

 

2. Yoo Jaejun, UNIST

https://www.youtube.com/watch?v=kLDuxRtxGD8 

 

https://jaejunyoo.blogspot.com/2017/01/generative-adversarial-nets-2.html

 

초짜 대학원생 입장에서 이해하는 Generative Adversarial Nets (2)

쉽게 풀어 설명하는 Generative Adversarial Nets (GAN)

jaejunyoo.blogspot.com

 

https://brunch.co.kr/@kakao-it/145

 

[카카오AI리포트]Do you know GAN? 1/2

유재준 | 카이스트 | 최근 딥러닝 분야에서 가장 뜨겁게 연구되고 있는 주제인 GAN(generative adversarial network)을 소개하고 학습할 수 있는글을 연재하려고 한다. GAN은 이름 그대로 뉴럴 네트워크(neur

brunch.co.kr

 

안녕하세요.

이번 글에서는 최초 GAN 논문"Generative Adversarial Nets"을 리뷰하려고 합니다.

 

우선, GAN이라는 모델이 설명할 내용이 많다고 판단하여 파트를 두 개로 나누었습니다. 

 

Part1에서는 GAN architecture를 포함한 GAN에 대한 전반적인 내용(Abstract, 1.introduction, 3.Adversarial nets)을 이야기하고, Part2에서는 GAN수학적으로 정리한 내용(4.Theoretical results)나머지 부분(5.Experiments, 6.Advantages and disadvantages)에 대해 이야기 해보도록 하겠습니다.

 

그럼 이번 글에서는 Part1에 대해 설명하도록 하겠습니다.

 

 

https://arxiv.org/abs/1406.2661

 

Generative Adversarial Networks

We propose a new framework for estimating generative models via an adversarial process, in which we simultaneously train two models: a generative model G that captures the data distribution, and a discriminative model D that estimates the probability that

arxiv.org

 

 

 

Paper: Generative Adversarial Networks

arXiv: 2014.06.10 등록

Conference: 2016 NIPS

 

 

 

 

Ian J. Goodfellow

논문을 리뷰하기 전에 GAN저자Ian J. Goodfellow를 간략히 소개할까 합니다. (딥러닝 하시는 분들이라면 대부분 알고 있으실테니, 보기 편하게 간략히 정리하는 정도로만 하겠습니다~)

 

  • B.S, M.S (2004~2009)
    • University: Stanford University
    • Major: Computer Science
    • Supervisor: Andrew Ng
  • Ph.D (2010~2014)
    • University: Université de Montréal
    • Major: Machine Learning
    • Supervisor1: Yoshua Bengio
    • Supervisor2: Aaron Courville
    • GAN 논문은 박사과정때 쓴 것 (arXiv 2014.06)
  • Google Brain (2015~2016)
    • Senior Research Scientist
  • Open AI (2016~2017)
    • Research Scientist
    • GAN논문이 NIPS에 accept되어, presentation 발표함
  • Google Research (2017~2019)
    • Senior Staff Research Scientist
  • Apple (2019~Current)
    • Director of Machine Learning

 

 

(↓↓↓2016 NIPS에서 Open AI 소속으로 GAN발표하는 Ian J. Goodfellow↓↓↓)

 

 

Ian J. Goodfellow박사과정 졸업 후, supervisor인 Yoshua Bengio, Aaron Courville와 함께 Deep Learning book편찬했습니다. 제 생각에는 책의 발행년도가 2015년이니 이전부터 아마 박사과정 졸업 논문을 쓰면서 background로 정리해 놨던 내용들을 지도교수들과 함께 책으로 만든게 아닌가 싶습니다. 제가 석사 때 다녔던 대학원을 포함해, 많은 학교에서 이 책을 deep learning 수업교재로 사용했던걸로 기억합니다.

 

(이 책은 아래 사이트에서 무료로 볼 수 있습니다↓)

<그림 출처: https://www.techleer.com/articles/260-deep-learning-by-goodfellow-bengio-and-courville/>

https://www.deeplearningbook.org/

 

Deep Learning

What is the best way to print the HTML format? Printing seems to work best printing directly from the browser, using Chrome. Other browsers do not work as well.

www.deeplearningbook.org

 

 

(↓↓↓Ian J. Goodfellow LinkedIn↓↓↓)

https://www.linkedin.com/in/ian-goodfellow-b7187213/

 

GAN의 저자인 Ian J. Goodfellow에 대해서 간단히 알아봤으니 이제부터는 논문을 본격적으로 리뷰해보도록 하겠습니다.

 

 

 

 

 

 

0. Abstract

 

 

Abstract에서 설명한 내용을 6가지 key words로 나누어 설명드리고자 합니다.

  1. Adversarial process (Abstract에서 분홍색 음영처리 된 부분)
  2. Minimax two-player game (Abstract에서 주황색 음영처리 된 부분) 
  3. Estimating generative models (Abstract에서 노란색 음영처리 된 부분)
  4. A unique solution (Abstract에서 보라색 음영처리 된 부분)
  5. Architecture (Abstract에서 빨간색 음영처리 된 부분)
  6. Qualitative and quantitative evaluation (Abstract에서 회색 음영처리 된 부분)

 

 

[0-1. Adversarial process]

 

 

"GAN이라는 것은 기본적으로 generative model의 성능을 높이기 위해 고안된 architecture입니다."

 

 

즉, 실제와 유사한  이미지를 생성해주는 generative model을 만드는 것이 목적이죠. 

이렇게 이상적인 generative model을 만들기 위해 생각한 것이 generative model을 경쟁시키는 것입니다.

 

 

"우리도 경쟁을 통해서 성장하는 것 처럼 generative model도 경쟁을 통해 성장하게 하는 것이 GAN 논문의 기본 철학이죠."

 

 

GAN이라는 구조에서는 generative model경쟁자discriminator model로 두고 있습니다. 그리고, 앞서 언급한 경쟁이라는 표현보다는 "adversarial(적대적)"이라는 표현을 사용합니다. "Adversarial"이라는 표현을 쓴 이유는  generative model과 discriminator model은 서로 반대의 목적을 갖고 있었기 때문이라고 생각합니다 (경쟁이라는 표현은 사실 같은 목적을 두고도 사용할 수 있으니까요).

 

예를 들어, 위조 지폐범경찰서로 적대적이라고 할 수 있습니다. 왜냐하면, 위조지폐범은 일반인들이 진짜라고 믿게 만드는 fake money를  잘 생성하는 것이 목적이고, 경찰은 일반인들이 위조지폐를 가려낼 수 있는 방법들을 알려주는 것이 목적이기 때문입니다.

 

 

"범죄라는 것이 항상 '만들어 놓은 예방법을 피해가려는' 속성이 있기 때문에, 위조지폐를 가려낼 수 있는 방법이 좋아질 수록, 이를 피해 위조지폐를 만드는 기술도 더욱 교묘해 집니다." 

 

<그림 출처:  https://lepoeme20.github.io/archive/ADV_Training>

 

 

"이렇게 서로 적대적인 경쟁을 하다보면 위조지폐(=generative model)의 성능은 계속해서 좋아질 겁니다."

 

 

 

"a discriminative model D that estimates the probability that a sample came from the training data rather than G."라는 표현을 쓴 이유는 discriminative model이 기준을 'generative model로 부터 생성된 이미지인지를 판별하는 것'에 두는 것이 아니라, '실제 이미지인지를 판별하는 것'에 두는 것으로 봤기 때문이 아닌가 싶습니다. (CNN 관점에서 보면 background or negative sample 들을 잘 구별할 수 있게 학습하는 것과, foreground or positive sample들을 잘 구별할 수 있게 학습하는 것은 다른 문제이니까요. 예를 들어, 한 이미지에는 대부분 negative sample or background들이 많을 텐데, 이를 방치해두면 학습시 인공지능 모델이 background or negative sample만 잘 구분할 수 있도록 학습하게 될거에요. ) ← 혹시 이 부분에  대해서 다른 의견이 있으면 댓글로 남겨주세요!

 

 

 

[0-2. Minmax two-player game] 

 

앞서 언급한 "adversarial"이라는 개념을 좀 더 간단히 표현하면 다음과 같습니다.

 

 

"경찰(D)가 최대한(max) 위조지폐를 구분할 수 있는 능력을 높일수록, (adversarial 관계에 의해) 위조지폐범(G)은  (경찰을 속이기 위해) 자신들이 만들어내는 가짜 이미지와 실제 이미지의 차이를 최소화(min)하게 된다."

 

 

위의 말수식적으로 아래와 같이 표현하는데, 아래 수식에 대한 설명은 뒤에서 더 자세히 다루도록 하겠습니다.

 

 

 

 

 

[0-3. Estimating generative models]

 

Generative model추정(estimating)한다는 것의 의미를 파악하기 위해서는 이미지라는 개념을 distribution 관점에서 해석할 수 있어야 합니다.

 

(↓↓ 이미지, 차원, 분포와 관련된 개념들↓)

https://89douner.tistory.com/330?category=908620 

 

1. 이미지, 차원(dimension), 그리고 분포(distribution)간의 관계

안녕하세요. 이번 글에서는 이미지(data), 차원(dimension), 그리고 분포(distribution)간의 관계에 대해서 설명해보도록 하겠습니다. 앞으로 AutoEncoder, VAE, GAN을 이해하기 위한 가장 기본적인 background이..

89douner.tistory.com

 

 

(↓↓↓latent space와 이미지를 2차원 상에서 확률분포로 표현하는 의미↓↓↓)

링크 업로드 예정

 

 

 

위의 링크를 토대로 추가적인 설명하면 generative model을 추정한다는 개념을 아래와 같이 정리할 수 있습니다. 

 

"Generative model을 추정한다는 것은 실제 이미지 확률 분포에 maximum likelihood하도록 하는 generative model의 확률 분포를 추정(estimating)한다고 간주할 수 있습니다."

 

 

 

 

[0-4. A unique solution]

 

이 부분은 "3.Adversarial nets", "4.Theoretical results"에서 좀 더 상세히 설명하도록 하겠습니다.

 

 

 

 

[0-5. Architecture]

 

위의 내용에 대한 설명은 아래 그림으로 대체하겠습니다. (보통 Vision 분야에서 생각하고 있는 GAN은 DCGAN을 기반으로 한 것인데, DCGAN은 이 논문 이후에 나온 모델입니다. 그래서, 아래 그림은 현재 논문에서 설명하고 있는 MLP를 기반으로 구성되었습니다)

 

<그림1 출처:  https://towardsdatascience.com/applied-deep-learning-part-3-autoencoders-1c083af4d798>    <그림2 출처:  https://techblog-history-younghunjo1.tistory.com/130>

 

 

 

 

[0-6. Qualitative and quantitative evaluation]

 

CNN, Object detection, Segmentation 모두 각각의 task에 대한 성능을 평가하기 위한 지표들이 존재합니다. (ex: F1 score, ACC, mAP, Dice loss, etc ...) 예를 들어, CNN model에서는 VGGNet보다 ResNet의 ACC가 더 좋으면 ResNet이 더 좋은 모델이라고 (일반적으로) 평가하죠. 

 

마찬가지로 generative model도 여러 종류들이 있을 텐데 어떠한 생성모델이  좋은지 평가할 수 있는 기준이 있어야겠죠? 

 

보통 generative model의 성능 평가 지표는 두 가지 큰 categories가 있습니다.

  1. Qualitative measures are those measures that are not numerical and often involve human subjective evaluation or evaluation via comparison.
    • ex) Rapid Scene Categorization: 사람한테 잠깐 보여주고 이미지가 뭔지 맞추게 하여 생성모델이 이미지를 잘 생성하는지 평가
  2. Quantitative GAN generator evaluation refers to the calculation of specific numerical scores used to summarize the quality of generated images
    • ex) Frechet Inception Score (FIS) → DCGAN paper에서 설명할 예정

https://machinelearningmastery.com/how-to-evaluate-generative-adversarial-networks/

 

How to Evaluate Generative Adversarial Networks

Generative adversarial networks, or GANs for short, are an effective deep learning approach for developing generative models. Unlike other deep […]

machinelearningmastery.com

 

※이 논문에서 Markov Chain 관련 내용이 많이 나오는데, 이 글에서는 넘어가도록 하겠습니다. Markov Chain에 대한 설명까지 하게 되면 글이 너무 길어질 것 같아서....

 

 

 

 

 

 

 

 

1. Introduction

Introduction 부분은 문단(paragraph) 별, 문장(sentence) 별로 설명할 내용들이 많아 따로따로 나누어서 설명하도록 하겠습니다.

 

 

[1-1-1. First paragraph & First sentence]

[영어단어]

  • corpora: 말뭉치(corpus의 복수형태)

 

 

 

보통 CNN 같은 경우 다양하고(rich) 구조적(hierarchical)으로 filter가 구성되어 있습니다. 예를 들어, low-level layer 만해도 가로 edge, 세로 edge 등 다양한 feature들을 extraction 해줄 수 있는 filter들로 구성 되어있죠. 또한, low-level layer에서는 edge, middle-level layer에서는 texture, high-level layer에서는 semantic 정보들을 추출해 줄 수 있게 filter가 구성되어 있습니다.

 

 

<그림 출처: https://slidetodoc.com/introduction-to-deep-learning-professor-qiang-yang-outline/>

 

위와 같은 CNN(discriminator)모델은 어떤 이미지를 분류하기 위해 filter들이 최적화되었다고 볼 수 있습니다. 결국 어떤 이미지를 생성하는 generative model 역시 다양한 이미지를 생성하기 위해 rich and hierarchical feature들을 생성해야겠죠. (※CNN과 같은 discriminative modelfeature extraction하고, GAN과 같은 generative modelfeature generation한다고 보면 될 것 같네요)

 

"즉, generative model 입장에서는 어떤 이미지를 생성하기 위해 filter들을 최적화해야 합니다."

 

하지만, 이 논문에서 딥러닝의 미래는 이렇게 어떤 이미지를 분류하는 것이 아닌 어떤 데이터들을 그대로 표현(representation)해 줄 수 있는 모델을 만드는 것에 있다고 주장합니다. (어떤 데이터들을 그대로 표현해줄 수 있다면 해당 데이터들 또한 생성 할 수 있게 됩니다. 이에 대한 구체적인 설명은 논문을 리뷰해가면서 자세히 알아가도록 하겠습니다) 

 

 

 

 

 

[1-1-2. First paragraph & Second, Third sentence]

 

이 논문의 저자는 CNN(=discriminative model)과 같은 딥러닝 모델 성공한 이유세 가지 측면에서 설명하고 있습니다. 

 

<그림 출처:  https://towardsdatascience.com/a-comprehensive-guide-to-convolutional-neural-networks-the-eli5-way-3bd2b1164a53>

  1. Map a high-dimensional, rich sensory input to a class label. ← discrimination(or classification)을 위해 저차원 vector(=FC layer의 neuron들)를 선별해줌 (Curse of dimensionality 극복)
  2. Backpropagation and dropout algorithms ← Neural network의 첫 번째 겨울을 극복하게 해준 알고리즘
  3. Piecewise linear units ← Neural network의 두 번째 겨울을 극복하게 해준 ReLU (Vanishing gradient 극복)  
    • ReLU0을 기점으로 구분적으로 linear한 성격을 갖고 있습니다. Sigmoid보다 piecewise linear units (ReLU)에 의해 gradient가 더 잘 작동되었습니다.
    • piecewise 뜻: [수학] 구분적으로

<그림 출처: https://sanghyu.tistory.com/102>

 

 

 

 

[1-1-3. First paragraph & Fourth, Fifth sentence]

[영어단어]

  • sidestep: If you sidestep a problem, you avoid discussing it or dealing with it.

 

 

Deep generative model은 CNN 만큼 큰 임팩트를 주지는 못했는데, 그 이유는 deep generative model의 계산 복잡성 때문입니다. Deep generative model과 같은 확률모델을 생성하기 위해 maximum likelihood 계산을 할 때는 (보통) 계산시스템 관점에서 intractable problem 문제에 부딪히는 경우가 많습니다. 예를 들어, VAE와 같은 deep generative model은 본래 intractable problem이었는데, variational inference라는 mathematical trick을 이용하여 tractable problem으로 변경해주었죠. (VAE 관련 글은 짧은 시간내에 다루도록 하겠습니다. 정리는 해놨는데 시간 때문에 옮겨적고 있지 못하고 있어서ㅜ...;;)

 

(↓intractable에 대한 설명을 다룬 글↓)

https://89douner.tistory.com/327

 

3. Intractable problem이란? (Feat. Turing machine)

안녕하세요. 이번 글에서는 intractable problem에 대해서 설명드리려고 합니다. 딥러닝 뿐만 아니라 컴퓨터를 통해 연구를 할 때, 자신이 설계한 모델이 컴퓨터 상에 돌아갈 수 있는지 없는지를 알아

89douner.tistory.com

 

또한, 기존 deep generative model ReLU와 같이 piecewise linear units의 장점을 잘 살리기도 어려웠다고 합니다.

 

"이러한 문제를 해결하기 위해 Ian Goodfellow는 새로운 generative model estimation procedure 방식을 제안하게 됩니다."

 

 

 

 

[1-2. Second paragraph & First sentence]

[영어단어]

  • pit (somebody/something) against something: ~를 ~와 겨루게(경쟁하게) 하다.
  • counterfeiter: 위조자

 

 

앞서 abstract의 "0-1.Adversarial process"의 내용을 다시 설명한 문단입니다.

 

 

<그림 출처: https://www.slideshare.net/NaverEngineering/1-gangenerative-adversarial-network>

 

다시 말하자면, 결국 adversarial 경쟁으로 위조자와 판별자의 능력이 서로 향상된다는 내용입니다. 위조지폐범의 위조지폐제작 기술은 경쟁하기 전 보다 훨씬 발전해 있을 것이고, 경찰의 위조지폐판독 기술 역시 경쟁 전 보다 훨씬 발전해 있을 것 임.

 

<그림 출처:  https://lepoeme20.github.io/archive/ADV_Training>

 

 

 

 

 

[1-3. Third paragraph]

 

위의 문단에 대한 설명은 아래 그림으로 대신하도록 하겠습니다.

 

<그림1 출처:  https://towardsdatascience.com/applied-deep-learning-part-3-autoencoders-1c083af4d798>    <그림2 출처:  https://techblog-history-younghunjo1.tistory.com/130>

 

 

VAE에서 와 같은 variational inference (approximate inference) 기법이나, 전통적인 생성모델에 쓰이던 Markov chains 같은 거 안써도 된다는 것이 GAN의 큰 장점이라고 합니다. (앞서 언급했듯이, VAE와 Markov chains은 나중에 따로 글을 작성하여 설명하도록 하겠습니다)

 

 

 

 

 

 

 

 

3. Adversarial nets

"3.Adversarial nets" 부분도 문단(paragraph) 별, 문장(sentence) 별로 설명할 내용들이 많아 따로따로 나누어서 설명하도록 하겠습니다.

 

 

[3-1-1. First paragraph & Second sentence]

 

논문에서는 uniform distribution으로 input noise를 sampling 했다고 합니다. 그 외 설명은 아래 이미지로 대신할 수 있을 것 같습니다.

 

 

여기서 한 가지 질문을 해보도록 하겠습니다.

 

"앞서, uniform sampling을 했다고 했는데, gaussian sampling을 하는건 안되나요?"

 

지금부터 이에 대한 답을 간단히 하기 위해 generative modeltaxonomy를 살펴보도록 하겠습니다.

 

앞서 "[0-3. Estimating generative models]"에서도 언급했듯이 우리는 generative model이 이미지 데이터의 확률분포를 maximum likelihood 하기를 원합니다. 하지만, 이미지 데이터를 표현(representation)하는 확률분포를 단 번에 아는 것은 쉬운일이 아니죠. 그래서, 학습을 통해 generative model을 이미지 데이터의 확률분포에 maximum likelihood 하도록 estimation(추정)하게 되는 것입니다.  이렇게 추정을 하는 방식에는 크게 두 가지로 나눌 수 있습니다. 

 

 

 

첫 번째 방식은 explicit desnity입니다.  예를 들어, VAE에서는 이미지 데이터 확률분포  \(x\sim~p_{x}(x)\) or \(p_{x\sim~data}(x)\) 를 표현(representaiton)해주기 위해 이상적인 z 값을 sampling하기를 원합니다. 즉, 이상적인 z의 확률분포인 \(z\sim~p_{z}(z)\) or \(p_{z\sim~latent}(z)\)를 알아내고 싶은 것이죠. 그래서, VAE 모델은 사전명시적(explicit)으로 z의 확률분포인 \(p_{z\sim~latent}(z)\)가 특정 probability distribution인  gaussian distribution을 따를 것이라 가정합니다.  특히, VAE에서 초기에 설정한 density estimation 수식은 intractable했기 때문에 이를 variational inference를 이용해 approximation하도록 하여 tractable하게 바꾸게 됩니다. (← 이 부분에 대한 자세한 설명에서는 VAE paper 리뷰하면서 하도록 하겠습니다)

 

\(Z\sim~N(\mu, \sigma^{2})\)

\(P_{Z}(z)\)

 

<그림 출처: https://taeu.github.io/paper/deeplearning-paper-vae/>

 

 

두 번째는 GAN과 같은 implicit density 방식입니다. 앞서 VAE에서 언급한 것 처럼 explicit density(명시된 사전 확률분포)를 이용하는 방식아닌 사전에 어떠한 확률 분포도 명시하지 않습니다. 이것의 의미하는 바는 z의 확률 분포가 특정 확률분포를 따라야 한다는 가정이 없어도 된다는 뜻입니다.  그래서 앞서 input noise에 해당하는 z를 sampling 할 때, z가 uniform distribution을 따른 다는 가정하에 sampling을 해도 되고, gaussian distribution을 따른 다는 가정하에 sampling을 해도됩니다. 즉,  GAN 방식에서의 generative model은 (z의 확률분포가 무엇인지와는 별개로) 알아서 이미지 데이터의 확률 분포를 estimation할 수 있게 됩니다. 

 

앞서 VAE에서 intractable하다고 했던 이유는 사전에 명시적(explicit)으로 정의된 z의 probability distribution(=density function) 때문이라고 했는데, GAN에서는 z의 probability distribution에 대한 제약이 없으니 애초에 intractable density funciton을 approximating 할 필요가 없게 되는 것이죠.

 

"Since an adversarial learning method is adopted, we need not care about approximating intractable density functions."

 

(↓↓↓위의 영어문장을 발췌한 사이트↓↓↓)

https://towardsdatascience.com/generative-adversarial-networks-explained-34472718707a

 

Generative Adversarial Networks — Explained

Deep learning has changed the way we work, compute and has made our lives a lot easier. As Andrej Karpathy mentioned it is indeed the…

towardsdatascience.com

 

 

즉, GAN은 구조적으로 adverarial training 방식을 채택함으로써 몇몇 generative model에서 겪었던 intractable 문제들을 다룰 수 있게 된 것입니다. 

 

"It's this back and forth that allows GANs to tackle otherwise intractable generative problems."

 

(↓↓↓위의 영어문장을 발췌한 사이트↓↓↓)

https://developers.google.com/machine-learning/gan/training

 

GAN Training  |  Generative Adversarial Networks  |  Google Developers

Send feedback GAN Training Because a GAN contains two separately trained networks, its training algorithm must address two complications: GANs must juggle two different kinds of training (generator and discriminator). GAN convergence is hard to identify. A

developers.google.com

 

 

 

 

 

 

[3-1-2. First paragraph & Third, Fourth sentence]

 

세 번째 문장은 아래 그림으로 대체하고, 네 번째 문장은 "0-1. Adversasrial process"에서 설명했으니 넘어가도록 하겠습니다.

 

 

[3-1-3. First paragraph & Fifth sentence]

 

 

"Discriminator 관점에서는 Value function(=V(D,G)maximization 되어야 하고, Generator 관점에서는 Value functionminimization되어야 합니다."

 

 

지금부터 이 부분에 대한 설명을 조금 더 자세히 해보도록 하겠습니다.

 

 

[Discriminator 관점]

먼저 Discriminator 관점에서 Value function(=V(D,G))해석해보겠습니다.

 

<그림 출처: https://www.slideshare.net/NaverEngineering/1-gangenerative-adversarial-network>

 

"Discriminator 관점에서는 real datax가 들어왔을 때 true=1 이라고 판별해줘야 하고 (D(x)=1), z로부터 생성된 fake dataG(z)가 들어왔을 때는 fake=0 이라고 판별해줘야 합니다(→D(G(z))=0)."

 

Discriminator가 이상적으로 작동하게 되면 D(x)=1, D(G(z))=0이기 때문에 V(D,G) 값은 0이 출력됩니다. 반대로, discriminator가 제 기능을 하지 못 하면 D(x)=0, D(G(x))=1 과 같은 값을 출력합니다. 이 때는, V(D,G) 값이 -∞로 흘러가죠. (D(x)=1, D(G(x))=1), (D(x)=0, D(G(x))=0) 다양한 조합을 생각해 보더라도 V(D,G)의 max 값은 0이고, min 값은 -∞ 인것을 알 수 있죠. 그래서 V(D,G) 함수가 갖는 range0 ~ -∞ 가 됩니다.

 

즉, discriminator 관점에서 봤을 때 V(D,G)maximization 한다는 것, 0값에 수렴한다는 뜻과 같습니다.

 

사실 위와 같은 수식은 어떤 새로운 개념이 아니라, binary cross classification (real or fake)을 위해 binary cross entropy 수식을 이용한 것이라고 보시면 됩니다.

 

 

 

[Generator 관점]

Generator 관점에서는 Value function(=V(D,G))minimization되어야 합니다.

 

<그림 출처: https://www.slideshare.net/NaverEngineering/1-gangenerative-adversarial-network>

 

V(D,G)두 식으로 구성된다고 봤을 때, generator 관점에서 좌측 식은 고려 대상이 아닙니다. 왜냐하면, generator는 단지 z만을 입력으로 받기 때문이죠. (아래 그림 참고)

 

Generator는 discriminator를 속여야 하기 때문에 D(G(z))=1 방향으로 학습을 진행하게 됩니다. 이러한 방향으로 학습이 되다보면, 우측식에 의해 Value function(=V(D,G)은 min 값인 -∞ 으로 수렴하게 되기 때문에, V(D,G)minimize 하는 방향으로 학습하게 됩니다.

 

 

즉 이렇게 Generator를 학습시기키기 위해 Generator와 Discriminator가 상반된 (Adversarial) 목적을 갖는 다는 특성이 있기 때문에 Generative Adversarial Network 라고 부르게 됩니다.

 

<그림 출처: cs231n. lecture 14. Generative models>

 

 

수식에서 평균의미하는 바는 간단합니다.

  • X: Real image dataset, G(z): Fake image dataset

 

 

V(D,G)라는 objective function은 결국 GAN이 어떠한 방향으로 학습하길 원하는지를 의미합니다. 만약, E라는 수식이 없으면 V(D,G)를 통해 GAN이 학습 할 때, 하나의 X 데이터, 하나의 G(z) 데이터만을 고려해서 학습하게 됩니다. 이렇게 되면 GAN이 굉장히 불안정하게 학습을 하게 되죠. 왜냐하면 다음에 학습할 X데이터와 G(z) 데이터가 이전  X, G(z) 데이터들과 확연히 다를 수 있기 때문입니다.

 

이는, 우리가 batch를 크게 잡아주지 않을 때와, 크게 잡아줄 때의 차이점을 생각해보면 더 이해가 쉬울 듯 한데, 아래 링크에서 “3-1.large batch training”&”3-1-1.linear scaling learning rate” 부분을 참고하시면 좋을 것 같습니다.

 

https://89douner.tistory.com/248

 

2. Bag of Tricks for Image Classification with Convolutional Neural Networks

안녕하세요. 이번 글에서는 아래 논문을 리뷰해보도록 하겠습니다.(아직 2차 검토를 하지 않은 상태라 설명이 비약적이거나 문장이 어색할 수 있습니다.) ※덧 분여 제가 medical image에서 tranasfer l

89douner.tistory.com

 

다시말해, 다수의 X데이터, 다수의 G(z) 데이터를 평균적으로 고려할 수 있게 학습해야 GAN이 하나의 X real data, 하나의 G(z) 데이터가 아닌 X real dataset, G(z) fake dataset 모두를 고려하여 학습하게 되죠. 이렇게 모든 dataset을 고려한다는 표현에 평균과 distribution이라는 개념이 동시 내포되어 있는것이라고 생각합니다. (흔히 우리가 알고 있는 mini-batch 관점에서 해석해볼 수 있을 것 같습니다.)

 

 

 

 

[3-2-1. Second paragraph & First sentence]

 

다음 section4장(="4.Theoretical Results")에서는 GAN이라는 모델을 이론적으로 분석하는 내용들에 대해서 소개합니다

 

위의 문장 중 아래 부분에 해당되는 내용을 잠깐 설명드리겠습니다. 

 

"the training criterion allows one to recover the data generating distribution as G and D are given enough capacity, i.e, in the non-parametric limit"

 

Discriminator가 충분히 학습이 되면, generatorrecover할 수 있다고 표현하는데, 이 때 recover라는 뜻은 아래 의미 중 세 번째 의미로 쓰인 것 같습니다. , discriminator를 먼저 학습을 시킴으로써 초기에 어려운 상황에 놓인 generator가 성장할 수 있다는 의미를 내포하고 있는 것 같습니다.

 

 

Machine learning book에서는 parametric과 non-parametric의 차이를 아래와 같이 정의하고 있습니다.

 

"Does the model have a fixed number of parameters, or does the number of parameters grow with the amount of training data? The former is called a parametric model, and the latter is called a nonparametric model."

 

GAN이라는 모델은 데이터셋의 크기에 따라 generator, discriminator를 구성하는 parameter들의 수가 달라야 합니다. 그렇기 때문에, 신경망을 사용하는 GAN 모델을 non-parametric model로 보는 것 같네요.

 

개인적으로는 아래 인용구 처럼 Yann LeCun이 페이스북에서 언급했던 내용이 직관적으로 받아드리기 좀 수월했던 것 같습니다.

 

"In general, a model that you cannot "saturate" as you increase training dataset is non parametirc."

 

또한, 책에서는 parametric model과 non-parametric model의 장단점을 아래와 같이 정의하고 있습니다.

 

Parametric model

  • 장점: faster to use
  • 단점: stronger assumptions about the nature of the data distribution → 예를 들어, parameter 수가 고정 된 어떤 모델에 사전 확률 분포를 미리 설정하여 generative model을 만든다는건, data distribution이 설정된 사전 확률 분포를 따를 것이라고 가정하는 것 → 하지만, 현실 세계에서 data distribution이 앞서 설정한 강력한 가정(="사전확률 분포를 따를 것이다")을 따르는 경우가 많지 않음

 

Non-parametric model

  • 장점: flexible → 굳이 사전확률 분포같은 것을 안정해도 됨
  • 단점: often computationally intractable for large datasets. → 큰 데이터셋에서는 많은 parameter들이 필요하므로 종종 계산 시스템 관점에서 intractable할 수 있음

 

"the training criterion allows one to recover the data generating distribution as G and D are given enough capacity, i.e, in the non-parametric limit"

 

논문의 문장을 다시 한 번 살펴보겠습니다. 

 

Non-parametric (model의) limit(한계)은 computaionally intractable 문제를 늘 갖고 있습니다. 그래서 이러한 computationally intractable을 다룰 수 있는 enough capacity가 주어진다면, GAN training이 잘 될 수 있을거라 보고 있습니다.

 

(사실 앞서 GAN이 generative model에서 겪는 intractable 한 것을 해결했다고 하지만, 엄밀히 말해 "enough capacity"에 따라서 다시 intractable해질 수 있는 듯 합니다. )

 

(↓↓↓machine learning book에서 언급하는 parametric VS non-parametric models; "1.4.1 parametric vs non-parametric models" 참고↓↓↓)

http://noiselab.ucsd.edu/ECE228/Murphy_Machine_Learning.pdf

 

 

 

[3-2-2. Second paragraph & Second sentence]

 

이 문장에서는 Figure 1에 대해서 설명하도록 하겠습니다.

  • \(D\): Dashed blue line = discriminative distribution
  • \(p_{x}\): Dotted block line = data distribution
  • \(p_{g}(G)\): Solid green line = generative distribution

 

이미지를 표현할 수 있는 저차원 latent space를 z차원으로 간주하고, z차원에서 sampling할 때 사전확률 분포를 uniform distribution \(z\sim~p_{z}(z)\)으로 설정하면 아래와 같이 일정한 간격으로 sampling됩니다. 추출된 각각의 sample들로부터 generated image가 생성 됩니다.

 

 

 

 

 

 

(실제로 z축의 차원과 x축의 차원은 다르기 때문에 1차원 개념으로 표현하는건 엄밀히 말하자면 잘 못 된 이지만, 이해를 돕기 위해 이렇게 한 듯 합니다. 그래서, “a less formal, more pedagogical explanation of the approach”라는 표현을 쓴게 아닌가 싶기도 하네요..)

 

위에서 설명한 내용을 아래와 그림과 같이 표현 할 수 있을 것 같습니다.

 

 

 

 

 

위 ③에서는 이미지 같은 데이터non-uniform distribution으로 표현(representation)될 수 있음을 언급하고 있습니다. 여기서의 포인트는 이미지 데이터의 차원에서 이미지 데이터들의 분포를 표현할 때는 uniform distribution으로 표현하기 어렵다(or 표현할 수 없다)라는 사실 입니다. 그러므로, 정규분포가 아닌 다른 non-uniform distribution으로 볼 수 있습니다.

 

(↓이미지와 non-uniform distribution간의 관계를 설명한 글↓)

https://89douner.tistory.com/330?category=908620 

 

1. 이미지, 차원(dimension), 그리고 분포(distribution)간의 관계

안녕하세요. 이번 글에서는 이미지(data), 차원(dimension), 그리고 분포(distribution)간의 관계에 대해서 설명해보도록 하겠습니다. 앞으로 AutoEncoder, VAE, GAN을 이해하기 위한 가장 기본적인 background이..

89douner.tistory.com

 

 

 

 

그럼 이제부터 (a), (b), (c), (d)에 대한 설명을 해보도록 하겠습니다.

  • \(D\): Dashed blue line = discriminative distribution
  • \(p_{x}\): Dotted block line = data distribution
  • \(p_{g}(G)\): Solid green line = generative distribution
  • (a): data distributiongenerative distribution이 어느 정도 유사한 상태 (pg is similar to pdata) → D가 아직까지는 잘 구분해주긴 하나, 조금 불안정한 상태
  • (b): D가 잘 학습이 된 상태 → 예를 들어, (b) 그림상 해당 지점에서 왼쪽 값이면 real data로 구분, 오른쪽 값이면 fake data로 구분 D분포(관점)에서 x축 상의 값이 왼쪽일 수록 fake이미지라고 판단할 확률(y)이 높아짐 → D*관련 식은 뒤에서 설명
  • (c): G를 업데이트 한 후, 학습이 잘 된 D분포의 gradient가 G(z)가 좀 더 의미있는 이미지를 생성할 수 있게 유도 함→ 이 부분은 문장에 어떤 숨어 있는 뜻이 있는지 잘 이해를 못했는데, 그냥 학습이 잘 된 D로 인해 \(p_{g}(G)\)분포가 업데이트 되면서 점점 \(p_{x}\)분포에 가까워진다는 것으로 이해함
  • (d): GD가 충분히 학습되면 결국, G의 성능이 매우 높아져 Dreal datafake data전혀구분하지 못함 → 1/2 uniform distribution이 형성 됨

 

 

 

 

[3-2-3. Second paragraph & The rest]

 

 

 

[3-3-1. Third paragraph & First, Second, Third, Fourth sentence]

 

초기에는 D(G(z))=0 이나옵니다. 왜냐하면 초반에는 G:Generative model”이 정교하지 않은 fake 이미지를 생성하기 때문에, discriminatorG(z)로 생성된 이미지를 fake라고 잘 판별(D(G(z))=0)하게 됩니다. 그런데, log(1-(D(G(z)))) 꼴의 함수에서 초기 D(G(z)) 값이 0이 나온다면 gradient 값 자체가 saturation 된 상태이기 때문에, 업데이트가 더딜 수 있습니다.

 

그래서, G를 학습시키는 관점을 log(1-D(G(z)))minimization 하는 방향이 아니라, log(D(G(z)))maximization 하는 방향으로 학습시키게 하기 위해 term을 변경해 줍니다. 이렇게 term 변경이 가능한 이유는 아래와 같습니다.

 

"log(1-D(G(z)))minimization 한다 = D(G(z))=1 뱉어내도록 G를 학습시키기만 하면된다 =log(D(G(z)))maximization 하게 학습시킨다 = D(G(z)))=1뱉어내도록 G가 학습된다."

 

 

 

위와 같은 이유로 인해 실제 학습에 쓰이는 Value function (=V(D,G))는 아래와 같이 변경됩니다.

 

 

 

 

[3-3-2. Third paragraph & The last sentence]

 

위의 문장을 이해하기 위한 핵심 키워드"the same fixed point of the dynamics" 입니다. 이 키워드에 대한 개념을 세 가지 부분으로 나누어 차례대로 설명하겠습니다.

  1. Numerical Analysis
  2. Fixed point iteration (with 경사하강법(Steepest Gradient Descent))
  3. Dynamics

 

[Numerical Analysis]

수치해석학(numerical analysis)해석학 문제에서 수치적인 근삿값을 구하는 알고리즘을 연구하는 학문입니다. 현대의 수치해석 역시 정확한 해를 구하지는 않습니다. 왜냐하면 현실에서 많은 문제들을 접했을 때, 실제로 정확한 해를 구하는 것이 불가능한 경우가 많기 때문입니다. 그대신 대다수의 경우, 수치해석을 이용해 합리적인 수준의 오차를 갖는 근사값을 구하는 것에 집중합니다.

 

그래서, 수치해석에서 optimization 이라는 용어가 쓰입니다. 최적화(optimization)라는 뜻 자체가 완벽하지 않다는 것을 가정하에 어느 정도의 오류를 수용하면서 최적의 값을 얻어내는 과정을 의미합니다.

 

수치해석 응용분야 예시

  • 미분방정식: 수치적으로 미분 방정식을 푼다는 것은 주어진 미분 방정식의 근사해를 찾는 것 → Ex) Euler’s Methods
  • 확률미분방정식과 Markov Chain
  • 선형대수

 

최신 한양대 응용수학과 커리큘럼을 보면 수치해석을 위한 선수과목이 무엇인지 알 수 있습니다. (최적화이론에 convex optimization 같은게 들어있는 것 같은데..., 평소에 인공지능 하면서 부족하다거나 배우고 싶어했던 수학과목들이 체계적으로 잘 정리되어 있다는 느낌을 받았습니다)

<그림 출처:  http://amath.hanyang.ac.kr/page/?pid=curriculum1>

 

 

 

[Fixed point]

보통 Numerical Analysis 수업 자료들을 살펴보면 Fixed point라는 개념Chapter 3 정도에 위치해 있습니다.

 

<그림 출처:  https://web.ma.utexas.edu/CNA/NA2/toc.html>

 

Fixed points는 Nonlinear Equations(비선형 방정식)과 관련이 되어있기 때문에 먼저, Noninear Equations에 대해서 알아보도록 하겠습니다.

 

Nonlinear Equations은 일차 함수식처럼 변수들 사이의 관계가 직선적으로 증가하거나 감소하는 것이 아니라, 변수들 사이의 관계가 곡선적으로 증가하거나 감소하는 현상을 나타내는 방정식을 말합니다.

 

딥러닝 activation function, softmax와 같은 non-linear 함수가 결합된 합성함수 형태이므로 딥러닝의 최종 loss function 자체는 nonlinear function이라 할 수 있습니다

 

(↓딥러닝과 nonlinear function과의 관계를 설명한 글)

https://89douner.tistory.com/22

 

4. Activation Function은 왜 만들었나요?

Q. Activation function은 왜 쓰이는건가요? Q. Activation function은 왜 이렇게 종류가 다양한건가요? 앞서 Neural Network에 대해서 배워보았습니다. 다시 Neural Network를 살펴볼까요? 아래그림중에 f라고 표..

89douner.tistory.com

 

https://89douner.tistory.com/23

 

5.Multi-Layer Perceptron (MLP), Universal Theorem

Q. 왜 단층 Perceptron 모델에서 Layer를 추가하게 되었나요? Q. Universal Approximation Theorem은 뭔가요? 2~4장까지 배웠던 부분을 아래와 같이 하나의 그림으로 요약을 할 수 있습니다. 1.입력값들이 가중치.

89douner.tistory.com

 

 

 

 

 

 

"딥러닝을 학습한다는 concept을 non-linear (loss) equation을 푸는(solving; solution) concept으로 이해할 수 있습니다."

 

 

이 때, x를 입력 데이터라고 하면 non-linear (loss) equation = f(x) = 0 의 값을 찾는 것이 목적이 됩니다. 하지만, 현실에서 loss=0 값을 찾는건 불가능에 가깝기 때문에 0에 가까운 loss 값을 찾기 위해 반복(iteration)하여 학습을 하게 되는 것이죠.

 

 

"이렇게 반복적인 방법으로 0(허용오차 범위 내에 있는) 근사값을 찾는 방법 중에 하나가 fixed-point iteration이라는 방법입니다."

 

 

Fixed-point iteration을 알아보기에 앞서 fixed-point의 수학적 정의가 무엇인지 살펴보겠습니다.

 

"In mathematics, a fixed point (sometimes shortened to fixpoint, also known as an invariant point) of a function is an element of the function's domain that is mapped to itself by the function."

 

(↓↓↓함수에서 Domain과 Range의 개념을 잘 보여주는 그림↓↓↓)

<그림 출처:  https://www.cuemath.com/calculus/domain-and-range-of-a-function/>

 

 

 

아래 그림의 f(x) 함수에서는 3개의 fixed opints를 갖습니다.

 

"y = f(x) = x → a fixed set = {fixed point1, fixed point2, fixed point3}"

 

Fixed point에 대해서 알아봤으니, 이제는 Fixed point iteration에 대해서 알아보도록 하겠습니다. 

  • Fixed point iteration은 x=f(x)를 만족하는 x(=fixed point) 값을 알면 g(x)=0를 풀 수 있다는 관점에서 출발합니다.
  • 하지만, x=f(x)를 만족시키는 x를 찾는 것은 현실세계에서 쉬운 문제는 아닙니다.
  • 그래서, x값을 iteration 방식을 통해 업데이터 하여 x=f(x)에 근사하게 만드는 것이죠.
  • x=f(x)를 만족시키는 근사값 x를 구하게 되면 g(x)=0을 풀 수 있게 됩니다.
  • iteration을 구하는 방식을 예로 들면 아래와 같습니다.
  • \(x_{2}=g(x_{1})\)    →    \(x_{3}=g(x_{2})\)    →    \(x_{4}=g(x_{3})\)    →    ...    →    \(x_{i+1}=g(x_{i})\)
  • 위와 같은 방식을 통해 x=g(x)를 만족시키는 근사값 \(x_{i+1}\)을 구합니다. 그리고, 이를 통해 g(x)=0의 최적해인 x값을 구하게 되는 것이죠
  • (여기서 간주해야 할 것이 fixed point iteration을 통해 최적해를 찾아가기 위해서는 f, g 함수 모두 연속적이어야 한다는 점입니다.
  • 아래 문제를 통해 위에서 설명한 내용들을 직관적으로 이해해보도록 하겠습니다.

[문제1] g(x) = log(x)-x = 0을 구하기 위한 fixed point iteration 풀이법은?

  1. g(x) = log(x) - x
  2. f(x) = log(x) = x
  3. \(x_{1}=g(x_{0})\)    →    \(x_{2}=g(x_{1})\)    →    ...    →    \(x_{i+1}=g(x_{i})\)

<그림 출처:  https://pseudo-code.tistory.com/123>

 

[문제2] 아래 그림을 보고 fixed point iteration으로 해를 찾아가는 방식을 이해하시오.

 

※참고로 fixed point iteration 방식을 이용해 근사해를 찾을 수 있는지 없는지에 대해 알아보려면 아래와 같은 조건을 따져보면 됩니다.

  • Fixed point (a)에서 f'(a)가 1보다 작은지? 큰지? 확인

<그림 출처:  https://cae.seoultech.ac.kr/num/m06_Equation2.pdf>

 

Fixed point iteration에 대해 알아봤으니 이것이 딥러닝에서 사용되는 경사하강법과 어떠한 연관이 있는지 알아보겠습니다.

 

먼저, 아래 내용은 위스콘신 대학 computer science 부서의 Stephen J. Wright 교수의 수업교재 중 일부를 발췌한 내용입니다.

 

우리가 deep learning을 통해 배운 경사하강법 (Steepest Descent method) 방식은 Fixed point iteration 으로 간주할 수 있습니다. 앞서 배운 fixed point iteration과 조금 다른 점은 아래와 같습니다. 

  • 함수는 convex 조건을 만족해야 최적해를 구할 수 있다.
  • 기존 f(x)=0 방식이 아닌 (앞선 설명에서는 g(x)=0로 표기했습니다), gradient 관점에서 ∇f(x)=0 의 최적해를 구하기 위해 iteration 방식을 적용한다.

 

(아래 x*는 실제 해라고 가정하는 x의 근사값(=최적값)으로 볼 수 있습니다)

 

 

 

 

다시 논문으로 돌아와 해당 문장을 살펴보겠습니다.

 

 

 

 

앞서 설명한 내용을 요약하면 generator 부분의 초기 학습 시, log(1-D(G(z)))의 gradient값이 굉장히 낮기 때문에 saturation되는 현상을 보여줍니다. 그래서 G 입장에서는 log(1-D(G(z))의 gradient 값으로 학습해야 하는데, 충분한 gradient가 backpropagation되지 않기 때문에 초기 학습에 어려움을 느낍니다. 그래서, 아래 그림과 같이 log(D(G(z)))와 같은 형태로 변경시켜주었죠. (←이렇게 변경이 가능한 이유는 "3-3-1. Third paragraph & First, Second, Third, Fourth sentence"에서 설명드렸습니다)

 

 

 

문맥상에서 보면 log(D(G(z))로 변경시켜 주기 전에는 "the same fixed point of the dynamics of G and D" 가 아니었다고 생각하는데, 구체적으로 dynamcis와 same fixed point간의 관계를 파악하진 못했습니다. 여기서 말하는 dynamics라는 것도 결국에는 dynamic optimization(or programming) 관점에서 해석할 수 있고, "chain rule + dynamic programming = neural network"이기 때문에 여기서 언급하는 dynamics가 gradient를 내포하고 있는 듯 합니다. 그래서, log(D(G(z))로 변경되면 같은 gradient가 전파가 되고, 이것이 the same fixed point"와 연관이 있을 것 같긴한데, 아직까지 정확한 연결고리를 찾진 못했네요. 혹시 아시는 분 있으면 알려주세요!

 

 

 

 

 

 

 

 

지금까지 GAN에 대한 구조적인 부분에 대해서 설명해보았습니다.

 

설명이 잘 못 됐다고 생각되는 부분은 언제든 댓글을 남겨주세요!

 

다음에는 GAN이라는 모델이 numerical, iterative 방식으로 최적해(optimum)을 구할 수 있는지 증명하는 "4.Theoretical Results"에 대해설명하도록 하겠습니다.

 

 

감사합니다!

 

 

 

 

 

 

[Refernece]

1. 1시간 만에 GAN 학습하기

https://www.youtube.com/watch?v=odpjk7_tGY0 

 

 

2. CS231n. Lecture13. Generative Models 

https://www.youtube.com/watch?v=5WoItGTWV54 

 

 

 

 

안녕하세요. 

이번 글에서는 intractable problem에 대해서 설명드리려고 합니다.

 

딥러닝 뿐만 아니라 컴퓨터를 통해 연구를 할 때, 자신이 설계한 모델컴퓨터 상에 돌아갈 수 있는지 없는지를 알아내는 것은 굉장히 중요한 문제입니다.

 

"왜냐하면, 어렵게  어렵게 모델을 설계했는데, 해당 모델이 계산 불가능하다면 컴퓨터 상에서 쓸 수 없기 때문이죠."

 

컴퓨터 과학에서는 보통 계산 불가능하다는 것intractable하다고 표현합니다.

 

"그렇다면, 계산 불가능하다는 것을 어떻게 정의할 수 있을까요? " 

 

지금부터 위의 질문에 대한 답을 찾아가면서 intractable에 대한 개념을 이해해보도록 하겠습니다.

 

※Note. 참고로 intractable computation을 설명하기 위해서는 필연적으로 수학 역사를 다루어야 합니다. 하지만, 제가 수학과가 아니기 때문에 잘 못 된 설명이 있을 수 있으니 발견 시 꼭 댓글 달아주시면 감사하겠습니다!!!!!   

 

 

 

 

 

 

1. 무한이라는 개념의 등장

식탁에 있는 오렌지 하나냉장고에 있는 오렌지 하나를 가져와 제 접시에 놓았습니다. 그렇다면, 제 접시에는 두 개의 오렌지가 있을 겁니다. 이것을 수식으로 표현하면 아래와 같죠.

1 + 1 = 2

오렌지라는 물체를 하나의 단위(unit) 즉 수(number)로 간주하기 때문에 위와 같은 식이 성립하죠. 이것은 우리 눈으로 직관적으로 확인 할 수 있기 때문에 매우 자명하다고 할 수 있습니다. 

 

"그런데, 여러분은 무한이라는 개념을 직관적으로 설명하실 수 있으신가요?"

"우리 주변에 무한이라는 개념을 관찰할 수 있는 것이 무엇이 있죠?"

 

처음에 이런 질문들을 듣는다면 굉장히 혼란스러우실 겁니다. 어떤 분들은 무한대(∞)를 세상에서 가장 큰 수라고 이야기 하기도 하지요. 그런데, 수라는 관점에서 무한대(∞)를 해석하면 "1+무한대>무한대"가 되어야 하는데, 수학적 정의에 따르면 "1+무한대=무한대" 이죠. 그래서, 무한대(∞)라는 것을 수라는 관점으로 제한하기에는 무리가 있어보입니다.

 

"그렇다면, 무한대라는 개념을 어떤 관점에서 이해하면 되는 것일까요?"

먼저, 아래 영상을 살펴보도록 하겠습니다!

 

 

 

"위 영상에서 살펴봤듯이 무한이라는 개념은 "과정(process)"이라는 관점에서 이해할 수 있습니다."

 

아래 영상에서 아르키메데스(Archimedes; BC.287)삼각형의 변의 무한이 작게 만들어가는 과정을 통해 원의 둘레정의하기도 했죠. 이때, 한 변의 길이가 무한히 작게 간다는 것은 0에 가까워 지는 것과 같은데, 이러한 과정을 설명하기 위해 무한소(infinitesimal)라는 개념이 등장하게 됩니다. (반대로, 무한대는 무한히 커지는 과정을 의미하겠죠?)

 

 

 

이 후, 아이작 뉴턴(Isaac Newton; 1642), 라이프니츠( Gottfried Wilhelm Leibniz; 1646)무한소(infinitesimal)라는 개념을 이용미적분학발전시키게 됩니다.

 

 

하지만, 당시 미적분학체계가 갖춰지지 않은 상태였기 때문에 베르나도 볼차노(Bernard Placidus Johann Nepomuk Bolzano; 1781), 오귀스탱 루이 코시(Augustin Louis Cauchy; 1789), 카를 바이어슈트라스(Karl Theodor Wilhelm Weierstraß; 1815) 등의 수학자들이 엡실론-델타 논법을 발명했고, 이를 통해 극한, 미분, 적분 등의 개념들을 엄밀화하기 시작합니다. 예를 들어, 극한이라는 개념은 "x가 한없이 커질 때, f(x)가 한 없이 어떤 값에 가까워지면 그 값을 극한 값"이라고 하는데, 이때 "한없이"라는 개념과 "가까워진다"라는 개념을 공리(axiom), 정리(definition) 이용 수학적으로 엄밀하게 정의한 것이죠. 그리고, 이러한 노력들을 통해 초기 해석학(analysis)이 탄생합니다. 

 

(↓↓↓코시의 엡실론-델타 논법 설명↓↓↓)

 

 

(↓↓↓ 해석학 탄생의 역사↓↓↓)

 

 

또한, 칸토어(Georg Ferdinand Ludwig Philipp Cantor; 1845)무한이라는 개념을 집합의 관점에서 정리하였고, 데데킨트(Julius Wilhelm Richard Dedekind; 1831) 실수체계를 엄밀하게 정리함으로써 무한이라는 개념을 체계화시켰습니다. 결국 해석학을 통해 대수학, 기하학에 대한 개념을 엄밀하게 하려는 시도까지 하게 되죠.

 

 

그림 출처: https://dm19sky.tistory.com/59

 

이렇게 무한이나 극한에 대한 개념체계화 함으로써 미적분학, 해석학이 발전해갔습니다. 하지만, 이러한 분야가 발전하는 것을 마음에 들지 않았던 수학자도 있었죠. "라위천 에흐베르튀스 얀 브라우어르(Luitzen Egbertus Jan Brouwer: 1881)"는 18~19세기 미적분학, 해석학의 발전이 기존 수학에 많은 문제점을 야기했다고 주장하는데 그 이유는 아래와 같습니다.

 

"수학이라는 것은 철저하게 공리(axiom)과 정리(definition)에 의해 견고하게 구축되어야 하는 분야인데, 무한이나 극한 같이 관찰하기 어려운 개념들을 추상화 되면서 이러한 체계들이 무너지고 있다"

 

라위천 에흐베르튀스 얀 브라우어르

 

 

예를 들어, 이 당시 집합론은 모든 수학의 근간이었는데, 러셀(Bertrand Arthur William Russell; 1872)이 집합론에 모순이 있다고 주장합니다. (러셀의 역설(Bertrand Russel's paradox)이라고 알려져있죠)

 

러셀

 

"이렇게 수학의 체계가 흔들리려고 할 때즘 독일의 수학자 힐베르트(David Hilbert; 1862)가 등장합니다."

 

 

 

 

2. 힐베르트와 괴델의 불완전성 정리

"힐베르트(David Hilbert; 1862)는 공리계를 잘 설계할 수 있다면 '러셀의 역설' 이 해결 될 수 있다고 주장했습니다."

즉, 당시 수학 개념들은 충분히 체계화 시킬 수 있다고 본 것이죠.

 

힐베르트

 

힐베르트는 1928년 볼로냐 세계 수학자대회에서 한 가지 문제를 던집니다.

 

"현재 존재하는 모든 수학 문제들을 풀 수 있는 일반적인 알고리즘(기계)이 존재하는가?"

 

이러한 질문을 던진 이유는 "모든 수학 문제들을 풀 수 있는 일반적인 알고리즘 또는 기계가 있다면 모든 수학 체계를 형식화 할 수 있다는 것을 의미"했기 때문입니다.

 

만약 모든 수학 문제들을 풀 수 있는 일반적인 알고리즘 또는 기계가 등장한다면 수학자들이 찾아내는 모든 수학 공식들을 계산 할 수 있을 것이고, 그렇게 되면 수학자들은 모두 실직할 것이라고 봤죠.

 

또한, 앞서 언급한 알고리즘(or 기계)이 등장하면 수학의 '무모순성', '완전성', 그리고 '결정가능성'을 증명할 수 있다고 주장합니다.

 

미국의 수학자 괴델( Kurt Gödel; 1906)은 힐베르트가 궁금해 했던 "모든 수학 문제들을 풀 수 있는 일반적인 알고리즘"은 없다고 주장합니다. 아무리 공리 체계가 잘 설계되더라도 러셀의 역설은 피할 수 없다고 주장하죠. 자신의 주장을 증명하기 위해 "괴델의 불완전성 정리(Gödel's incompleteness theorems)"를 발표합니다. 

 

괴델

 

또한 괴델주장뒷 받침수학자가 있었습니다. 바로, Alan Turing인데요.

 

"지금부터 Alan Turing에 대해 설명하면서 좀 더 intractable이라는 개념에 다가가도록 하겠습니다."

 

 

 

3. Alan Turing 그리고 Halting problem

Alan Turing(1921)1934년 케임브리지 수학과졸업하고, 학업더 연장하게 됩니다.

 

"1935년 Max Newman 교수의 수업 중 "괴델의 불완정성 법칙"에 대한 이야기를 듣게 됩니다."

 

그리고 힐베르트가 말한 "모든 수학문제를 풀 수 있는 일반적인 기계"에 대해서 관심을 갖게 됩니다. 결국, 1936년 "On Computable Numbers, with an Application to the Entscheidungsproblem" 이라는 논문에서 앞서 언급한 기계를 고안하게 되죠.  그리고, 오늘날 이 기계를 Turing Machine이라 부릅니다.  (해당 논문에서는 universal mahince이라고 표현된 것을 오늘날 Turing Machine이라고 부르게 된 것이죠)

 

https://www.semanticscholar.org/paper/On-Computable-Numbers%2C-with-an-Application-to-the-Turing/ab7790485f26ce65f9d83dd700c43e49058bdd2b

 

[PDF] On Computable Numbers, with an Application to the Entscheidungsproblem | Semantic Scholar

1. Computing machines. 2. Definitions. Automatic machines. Computing machines. Circle and circle-free numbers. Computable sequences and numbers. 3. Examples of computing machines. 4. Abbreviated tables Further examples. 5. Enumeration of computable sequenc

www.semanticscholar.org

 

 

 

 

힐베르트가 말한 "모든 수학문제를 풀 수 있는 일반적인 기계"는 바꿔말해 "모든 연산(=계산; computation)이 가능한 가상의 기계"라는 것과 같습니다. 왜냐하면 결국 "수학문제를 푼다는 것"은 "계산을 한다는 것"과 같으니까요.

 

"그렇다면, 이러한 Turing Machine을 이용해 어떻게 괴델의 주장을 뒷받침 했을까요?"

 

이에 대한 답을 하기 위해서 Turing Machine에 대해서 잠깐 설명해보도록 하겠습니다. 

 

 

[Turing machine 작동원리]

Turing machine 작동원리는 아래 영상들을 참고해주세요!

 

 

 

[Hibert's Decision Problem & Halting Problem]

힐베르트는 "'모든 수학 문제들을 풀 수 있는 일반적인 알고리즘 또는 기계'가 존재하면 '모든 수학적 문제에 대해서 그 문제가 참인지 거짓인지를 확실하게 결정해 줄 명확한 방법이 존재할 수 있는지'" 궁금해했습니다.

 

이러한 질문을 "힐베르트의 결정 문제(Hilbert's Decision Problem)"라고 합니다. 이 문제에 답을 하기 위해서는 수학 문제가 참인지 거짓인지 증명이 되어야 합니다. 앞서 Turing 머신은 모든 연산을 할 수 있기다고 배웠습니다. 그렇다면, 모든 수학적 문제를 Turing 머신에 넣었을 때 참인지 거짓인지 판명하면 수학의 '결정가능성'을 입증할 수 있게 되는 것이죠. 

 

 

"그런데 반대로, 수학의 '결정가능성'을 반증하려면 어떻게 해야할까요?"

 

Turing machine이 수학 문제를 입력 받았을 때, 참 또는 거짓과 같은 답을 내놓지 않는다면 '결정가능성'을 반증할 수 있을겁니다. 참 또는 거짓과 같은 답을 내놓지 않는다는건 Turing Machine이 어떤 결론에 도달하지 않고, 즉 멈추지 않고 계속해서 돌아간다는 뜻이죠. 그래서 Turing은 힐베르트의 결정 문제(Hilbert's Decision Problem)를 "(수학 계산이 가능한) Turing machine에 데이터를 입력했을 때, 해당 machine이 궁극적으로 정지하는지 정지하지 않는지"에 대한 문제인 Halting Problem으로 바꿔 생각합니다. 만약, 정지하지 않으면 수학의 '결정가능성'을 반증하게 되는 것이죠.

 

 

 

 

[Turing Machine과 오늘날 컴퓨터]

Turing Machine계산이 가능한 시스템을 갖고 있습니다. 폰 노이만(John von Neumann; 1903)은 이러한 Turing machine확장하여 폰 노이만 구조설계하죠. 그리고, 오늘날 폰 노이만 구조를 오늘날 컴퓨터의 prototype으로 보고 있습니다.

 

"바꿔 말해, 모든 컴퓨터는 Turing Machine을 기반으로 하고 있다고 할 수 있습니다."

 

예를 들어서, 슈퍼컴퓨터가 할 수 있는 계산은 일반 컴퓨터에서 할 수 있습니다.  왜냐하면 모두 CPU, GPU 같은 장치들로 연산이되기 때문이죠. 단지 일반 컴퓨터에서는 시간이 더 오래걸릴 뿐입니다. 다시말해, 계산 능력자체는 동일한 것이라 할 수 있습니다. 이와 같은 맥락으로, 일반 컴퓨터의 계산 능력은 Turing machine과 동일하다고 할 수 있는 것이죠. 

 

 

 

 

4. Intractable & Tractable (Feat. NP & P 문제)

Turing machine은 다른 말로 "결정론적 튜링 기계(Deterministic Turing Machine: DTM)"라고도 합니다. 

 

결정론적이라는 표현이 붙은 이유는 Turing Machine 작동원리 영상에서 언급됐듯이 "테이프의 symbol이 s이고, 현재 상태가 q라면 알고리즘에 의해 다음 명령어가 유일하게 결정"되기 때문이죠.  

 

Deterministic Turing Machine은 현대 모든 계산 기능을 갖춘 기계들 (ex: 컴퓨터, 스마트폰, 슈퍼 컴퓨터 등)을 대표합니다. 그래서, "어떤 문제를 컴퓨터를 사용해 다항시간(polynomial time) 내에 답을 구할 수 있냐?"는 질문을 "어떤 문제를 Deterministic Turing Machine을 사용해 다항시간내에 답을 구할 수 있냐?"라는 문제로 치환할 수 있는 것이죠.

 

"어떤 문제를 Deterministic Turing Machine을 사용해  다항시간내에 답을 구할 수 있냐?"

 

이 치환된 질문은 굉장히 중요합니다. 왜냐하면, 이 질문을 기준으로 intractable computation(problem)인지 tractable computation(problem)인지 구분하기 때문이죠. Deterministic Turing Machine을 이용하여 어떤 문제를 polynomial time(다항시간) 안에 풀 수 있으면 "해당 문제는 polynomial time complexity을 갖는다"라고 말할 수 있게되고, 해당 문제를 tractable problem으로 간주하게 됩니다. 반대로, polynomial time 안에 풀 수 없으면 intractable problem으로 간주하게 되죠.

 

 

[P문제]

컴퓨터 과학에서는 tractable computation(problem)을 Polynomial의 P를 따서 P문제라고 정의합니다. 다시 말해, polynomial time complexity를 가지면, tractable(=풀만한; feasible) 문제라고 여기며, 이러한 문제들의 집한을 P라고 나타내는 것이죠. 

 

 

현실에서는 어떤 문제를 풀 때 이용되는 알고리즘이 (차수가) 2차 이하의 time complexity를 가진다면 유효한 알고리즘이라고 합니다. 이러한 알고리즘으로 풀리는 문제들을 P 문제 또는 tractable problem이라고 하죠. 예를 들어, shortest path 같은 최단거리를 다루는 다양한 알고리즘은 이미 P문제, 즉 tractable problem이라는 것이 증명되었죠.

 

 

그림 출처: https://www.joyk.com/dig/detail/1608665582509127

 

 

[NP문제]

반대로 None-Polynomial time complexity를 가진다면 intractable computation(problem)으로 여기며, 이러한 문제들의 집합을 NP라 합니다.

 

현실적에서는 3차 이상의 time complexity를 갖고 있을 경우 NP로 정의합니다.

 

"정리하자면, P, NP 문제는 Turing machine과 같은 계산 시스템 관점에서 풀기 어려운 (=intractable; NP) 문제인지 그래도 현실적으로 풀기 수월한 (=tractable; P) 문제인지에 따라 결정되는 것입니다."

 

 

 

 

 

5. 왜 P, NP 문제를 구분하는 것이 중요한가요?

현재 딥러닝을 연구하는 사람들에게 컴퓨터는 빼놓을 수 없는 장비입니다. 설계한 딥러닝 모델을 컴퓨터에서 학습시키고 그 결과를 도출해야하기 때문이죠. 새로운 딥러닝 모델을 설계하기 위해서는 기존에 쓰이지 않은 개념들을 접목시켜야 합니다.

 

"그런데, 이러한 새로운 모델을 설계하고 연구 할 때 중요한 것이 "기존에 쓰이지 않은 개념"을 접목시킨 새로운 딥러닝 모델이 계산 가능해야 한다는 것입니다."

 

만약, 새로 설계된 새로운 딥러닝 모델이 계산 불가능하다면, 해당 모델을 학습시키는건 현실적으로 불가능하다고 볼 수 있겠죠?

 

예를 들어서, 초기에 딥러닝이 막 나왔을 때에는 mutual information이라는 개념이 접목되지 않은 상태였습니다. 그렇기 때문에 연구자들은 mutual information을 접목시켜 새로운 딥러닝 모델을 만들려고 했죠. 하지만, mutual information이라는 개념을 딥러닝에 적용하여 수식화해보니 intractable computation(problem) 인 것으로 판명됐습니다. (←이 부분에 대한 자세한 설명은 Self-Supervised Learning 카테고리에서 글을 작성한 후 링크를 걸어두도록 하겠습니다)

 

그렇다면, 연구자들은 mutual information이라는 개념을 적용하는 것을 포기해야 할까요? 

 

컴퓨터 분야(or 딥러닝 분야)에서는 이와같이 intractable computation 문제를 tractable computation하게 바꿔주는 mathematical trick이 사용되기도 합니다. 예를 들어, VAE에서는 generative model을 만들기 위해 variational inference를 사용해 intractable generative model을 tractable generative model로 바꿔 주었고, Self-Supervised Learning 분야에서는 contrastive learning을 하기 위해 intractable mutual information 문제를  tractable하게 바꿔주기도 합니다.

 

"다시말해, intractable computation 문제들을 tractable computation으로 변경해주는 mathematical trick을 이용하는 것이죠. "

 

 

 

 

지금까지 intractable이라는 개념에 대해서 알아보았습니다.

"앞에서 배운것을 요약하면 'Deterministic Turing Machine으로 어떤 문제를 다항시간안에 풀 수 있는지 없는지에 따라 intractable, tractable을 구분할 수 있다'라고 정리할 수 있습니다."

 

 

 

글을 마치면서 질문을 하나 남기겠습니다.

"최근에 나온 양자컴퓨팅은 nondeterministic Turing machine입니다. 그렇다면, 양자컴퓨팅을 이용하면 NP였던 문제들이 P문제가 될 수 있을까요?"

 

답은 아래영상에서 확인하시면 좋을 것 같습니다.

 

 

 

[Reference]

https://blog.zarathu.com/posts/2019-05-20-godelincompleteness/

 

Zarathu Blog: 괴델의 불완전성 정리

괴델(Kurt Gödel)의 불완전성 정리가 나온 배경을 소개하고 증명의 핵심 아이디어를 수학과 메타수학(meta-mathematics), 괴델수(Gödel number), 그리고 메타수학의 수학화 3가지로 나누어 설명하였습니다.

blog.zarathu.com

 

안녕하세요. 

이번 글에서는 이미지(data), 차원(dimension), 그리고 분포(distribution)간의 관계에 대해서 설명해보도록 하겠습니다.

 

앞으로 AutoEncoder, VAE, GAN이해하기 위한 가장 기본적인 background이니 만큼 잘 설명해보도록 하겠습니다.

 

 

 

1. 이미지와 차원(dimension) 간의 관계

먼저, 한 가지 질문을 던지면서 글을 시작하도록 하겠습니다.

 

"색(color)을 표현(representation)하기 위해서는 몇 차원이 필요한가요?"

 

답부터 말씀드리면 "색을 표현하기 위해서는 3차원이 필요"합니다. 현실세계에서는 3차원 (R,G,B) 값을 다양하게 조합하여 색상표현할 수 있죠. 그리고, 이렇게 표현된 공간을 "색 공간 (color space)"라고 부릅니다.

 

<그림 출처: https://geraldbakker.nl/psnumbers/rgb-explained.html>
<위 그림을 설명을 위해첨부되었습니다 . 실제 pixel 값과 색상이 매칭이 안될 수 도 있으니 유의하세요 !>

 

 

 

 

 

"그렇다면, 색을 표현할 수 있는 모든 경우의 수는 어떻게 될까요?"

 

당연히 조합 경우의 수를 구하면 되므로 \(255^{3}\)  이 될 것입니다

 

<그림 출처:  https://overface.tistory.com/593>

 

 

 

 

 

"gray color를 표현하기 위해서 필요한 차원은 무엇일까요?"

 

gray color1차원 (0~255) 으로 모두 표현 가능합니다. 또한, gray color표현할 수 있는 모든 경우의 수255가지가 되겠죠. 그래서, 흑백 이미지를 다루는 문제에서는 이미지를 1차원으로 가정하고 gray scale이라고 표현하기도 합니다.

 

<그림 출처:  https://medium.com/javarevisited/converting-rgb-image-to-the-grayscale-image-in-java-9e1edc5bd6e7>

 

 

 

 

 

"앞서 색상관련해서는 정해진 차원(1차원 or 3차원)이 필요하다고 했는데, 그렇다면 이미지를 표현하기 위해서도 정해진 차원이 필요한가요?"

 

결론부터 말씀드리면, 이미지에 대한 차원은 "이미지 크기에 따라 달라진다" 입니다. 아래 gray scale의 튜링 이미지의 크기가 200×200이라고 한다면, 이러한 이미지를 표현하기 위해서는 40000 차원이 필요합니다. 왜 이렇게 고차원이 나오는지 설명해보도록 하겠습니다. (사실 엄밀히 말하면 색상도 R,G,B외에 다른 요소들로 표현할 수 있으면 색상의 차원은 또 달라질 수 있습니다)

 

 

 

 

200×200 gray scale 이미지를 표현한다고 하면 어떻게 생각해볼 수 있을까요? 먼저, 이미지라는 것은 pixel의 조합으로 이루어져 있습니다. 그리고, 하나의 픽셀에는 하나의 색 표현이 가능하죠. Gray scale인 경우에는 하나의 pixel0~255 사이 값 중 하나가 할당될 수 있습니다.

 

<그림 참고: https://blog.tonkabi.com/blog/post/computer-vision-vs-human-vision>

 

 

그렇다면, 200×200 gray scale 이미지의 pixel들을 1차원 일렬로 늘린다고 생각해보겠습니다.

 

<2D 이미지를 1D 이미지로 늘리는 예시>

 

 

그럼 40000개의 pixel이 나올 것입니다. 이때, 각각의 pixel들은 0~255개의 값을 지니고 있죠. 이를 다른 관점에서 보면, 40000개의 독립된 변수로 볼 수 있고, 각각의 변수는 0~255 값의 범위를 갖고 있다고 할 수 있죠. 40000개의 독립된 변수하나의 이미지 구성될 수 있기 때문에, 200×200 gray scale 이미지는 40000차원을 갖는다고 할 수 있습니다. 200×200 이미지는 40000 차원의 독립된 변수들이 갖는 고유의 값들에 의해 표현될 수 있는 것이죠. 

 

 

 

"그렇다면, 200×200 gray scale 이미지를 표현할 수 있는 모든 경우의 수는 어떻게 될까요?"

 

정답은 아래에서 구한 것 처럼 \(10^{96329}\) 경우의 수가 됩니다.

 

 

 

 

 

2. 이미지와 분포간의 관계 

앞서 200×200 gray scale 이미지의 차원 40000차원이고, 표현할 수 있는 이미지의 개수 (경우의 수)는 대략  \(10^{96329}\) 라고 했습니다.

 

"그렇다면, 200×200 gray scale 에서 표현될 수 있는 모든 경우의 수에 해당하는 이미지들은 의미가 있다고 할 수 을까요?"

예를 들어, \(10^{96329}\) 경우의 조합들 중에서는 아래 왼쪽과 같이 의미 없는 이미지(noise image)들도 있을 것이고, 오른쪽 같이 사람이 구별할 수 있는 의미 있는 이미지가 있을 수 있습니다. 

 

<그림 출처: http://web.mit.edu/kenta/www/three/grayscale-noise/zxevanas/images/?S=A>

 

 

여기서 우리는 또 한 가지 질문을 던져볼 수 있습니다.

 

"200×200 gray scale  즉, 40000차원 상에서 의미있는 이미지들은 고르게 분포(uniform distribution)하고 있을까요? 아니면 40000차원이라는 공간의 특정 영역에 몰려있거나 특정 패턴으로 분포(non-uniform distribution)하고 있을까요?"

 

이러한 질문에 을 하는 방법 중 하나는 200×200 gray scale 이미지들을 uniform distribution으로 수 없이 샘플링 해봐서 경험적으로 보여주는 것입니다. 만약, uniform distribution을 전제로 수 없이 샘플링 했을 때, 의미있는 이미지들이 종종 보인다면 의미있는 이미지들이 40000차원 상에 고르게 분포한다고 볼 수 있겠죠.

 

(※ 직관적으로 이해하기 위해 편의상 40000차원을 아래 이미지 처럼 3차원으로 표현했습니다. (즉, 아래 그림은 '본래 40000차원이다'라고 간주하시면 될 것 같습니다))

 

 

"오토인코더의 모든 것"이라는 영상에서 이활석님은 20만번 샘플링한 결과 의미없는 이미지(noisy image)만 추출된 것을 확인 할 수 있었다고 합니다. 이러한 실험을 통해 의미있는 이미지들은 40000차원에서 특정 패턴 또는 특정 위치에 분포해 있다고 경험적으로 결론내릴 수 있게 되는 것이죠.

 

(↓아래 영상 1:01:25초 부터)

 

 

 

 

 

 

 

지금까지 AutoEncoder, VAE, GAN을 배우기 위한 기본 지식들을 정리해봤습니다.

다음 글에서는 AutoEncoder에 대해서 다루면서 dimension reduction에 대한 개념을 소개하도록 하겠습니다. 왜냐하면 VAE, GAN 같은 논문들을 살펴보려면 "latent"말을 이해하기 중요하기 때문이죠!

 

그럼 다음 글에서 뵙도록 하겠습니다! 

 

 

 

안녕하세요.

이번 글에서는 앞으로 GAN에 대한 글을 어떠한 방식으로 작성해나갈지 간단히 설명하려고 합니다.

 

  1. AutoEncoder
  2. VAE (paper review)
  3. GAN (paper review)
  4. DCGAN (paper review)
  5. 이외 다른 GAN 모델들 (paper review 위주)

 

첫 번째 AutoEncoder를 다루는 이유는 VAE라는 모델 설명하기 위해서 입니다.

AutoEncoder는 본래 generative model concept 목적으로 연구된 것이 아니라, dimension reduction 연구를 위해 사용되던 모델입니다. 하지만, VAE라는 모델이 AutoEncoder 기반으로 이루어져있기 때문에 VAE를 배우면서 AutoEncoder 관련 용어들이 종종 등장합니다. 그렇기 때문에 AutoEncoder를 제일 먼저 다루려고 합니다.

 

두 번째로 VAE를 다룰 예정입니다. 기존generative model을 만들기 위해서는 여러 어려움이 존재했습니다. 대표적으로 intractable computation 문제가 있었죠. 쉽게 말해, 컴퓨터로 generative model을 만들려고 하면 계산이 불가능할 정도의 복잡한 수식을 풀어내야 합니다. VAE는 이러한 intractable computation 문제를 tractable computation 문제로 전환시키는 기법을 도입하여 generative model을 만드는 시도를 했습니다. Generative model을 자주 다루다 보면 intractable이라는 용어와 probabilistic 이라는 용어가 자주 사용되는데, VAE 논문 리뷰하면서 이러한 용어들에 대한 설명을 하려고 합니다. 

 

세 번째로는 GAN을 다룰 예정입니다. Ian J. Goodfellow 논문리뷰하면서 GAN에 대해서 알아보려고 합니다. 그리고, 네 번째DCGAN을 다루면서 vision 분야에서 GAN을  어떻게 적용했는지 알아보겠습니다.

 

 

처음 GAN을 접하시는 분들이라면 지금 말씀드린 내용이 모두 이해가 안되시는게 당연합니다.

앞으로 포스팅 하는 글을 최대한 열심히 작성하여 다시 이 글을 보셨을 때, 이해하실 수 있게 노력해보도록 하겠습니다!

 

+ Recent posts