Y Tech Blog search

VQ-VAE 2 논문 설명(Generating Diverse High-Fidelity Images with VQ-VAE-2)

|

이 글에서는 2019년 NIPS에 게재된 Generating Diverse High-Fidelity Images with VQ-VAE-2(VQ-VAE2) 논문을 살펴보고자 한다.

중요한 부분만 적을 예정이므로 전체가 궁금하면 원 논문을 찾아 읽어보면 된다.


Generating Diverse High-Fidelity Images with VQ-VAE-2

논문 링크: Generating Diverse High-Fidelity Images with VQ-VAE-2

Github: https://github.com/rosinality/vq-vae-2-pytorch

  • 2019년 6월, NIPS 2019
  • DeepMind
  • Ali Razavi, Aaron van den Oord, Oriol Vinyals

초록(Abstract)

이 논문에서는 VQ-VAE(Vector Quantized Variational AutoEncoder)로 large-scale 이미지 생성 문제를 다루려 한다. 이를 위해 prior를 더욱 강화하여 이전보다 더 일관성, 현실성 있는 이미지를 만들었다. 모델은 단순한 feed-forward encoder와 decoder를 사용하였으며 회귀모델은 오직 latent space 안에서만 쓰여 pixel space에서는 기존보다 더욱 빠른 속도를 갖는다. 최종적으로 GAN과 비슷한 성능을 보이면서도 mode collapsing과 같은 GAN의 고질적인 문제를 겪지 않는 생성 모델을 만들었다.


1. 서론(Introduction)

Deep Generative model은 최근 크게 발전하며 실제와 분간이 힘든 이미지를 생성할 수 있는 수준에 이르렀다. GAN은 minimax 방식을 사용하여 현실적인 이미지를 생성하였지만 실제 세상의 이미지 분포를 그대로 따라가지 못하는 문제가 존재한다. 또한 생성한 이미지를 평가하기도 매우 어려워서 근사하는 방식인 FID 등의 metric으로 평가를 해야 한다.

VQVAE2

이와는 대조적으로 likelihood 기반 방식은 NLL을 최적화하며 이는 모델 비교와 아직 보지 못한 일반화 성능을 측정할 수 있게 한다. 또 모델은 학습 셋의 모든 example에 대한 확률을 최대화하므로 분포 문제에서도 자유로운 편이다. 그러나 이 방식 역시 어려운 점이 있는데,

  • Pixel space에서의 NLL은 sample의 품질을 측정하기 적합하지 않고
  • 다른 model class 사이의 비교하는 데 사용하기도 어렵다.

본 논문에서는 무시해도 되는 정보를 모델링하는 데 드는 노력을 최소화하도록 lossy compression으로부터 얻은 아이디어를 사용한다. 사실 JPEG 압축 방식은 이미지 품질에 영향을 주지 않는 선에서 80%의 용량을 줄일 수 있는 방식이다. 이와 비슷한 아이디어로, 본 논문에서는 이미지를 매우 작은 discrete latent space로 옮겨 저장하는 방식을 취한다. 이는 30배 더 작은 공간을 차지하면서도 decoder가 원래 이미지를 (눈으로 보기에) 거의 비슷하게 복원할 수 있게 한다.

이산표현에서 prior는 PixelCNN + self-attention으로 모델링이 가능하여(PixelSnail), prior로부터 sampling할 때 디코딩된 이미지는 복원 시 고품질과 높은 coherence를 가진다. 인코딩된 이미지는 원본 이미지보다 30배 가량 작고 또 모델의 속도도 빨라서 기존의 생성모델에 비견될 만한 성능을 보인다.


2. 배경(Background)

2.1 Vector Quantized Variational AutoEncoder

VQ-VAE는 Variational AutoEncoder와 거의 비슷한 구조를 갖는데, 가장 중요한 차이점은 latent space가 discrete하다는 것이다. 지정된 크기(ex. 512)의 codebook(embedding space)을 유지하면서 이미지의 각 부분을 하나의 embedding의 인덱스에 대응시켜 이미지를 표현한다. Encoder는 입력 $x$에 대해 $x \mapsto E(x)$의 역할을 수행한다. 이 벡터 $E(x)$는 codebook vector $e_k$와의 거리에 기반하여 quantized되며 이는 decoder로 전달된다.

[\text{Quantize}(E(x)) = \textbf{e}_k \qquad \text{where} \quad k = \argmin_j \Vert E(x) - \textbf{e}_j \Vert]

Decoder는 이미지를 표현한 인덱스를 다시 대응되는 codebook vector로 mapping한다.

VQ-VAE는 다음 식으로 최적화된다.

[L = \log p(x \vert z_q(x)) + \Vert \text{sg}[z_e(x)]-e \Vert_2^2 + \beta \Vert z_e(x)-\text{sg}[e] \Vert_2^2 , \qquad (3)]

Encoder의 출력과 codebook의 벡터 공간을 일치시키는 것에 대해 두 가지 loss를 포함한다.

  • codebook loss: 오직 codebook에만 영향을 준다. 선택된 codebook $\textbf{e}$를 encoder의 출력 $E(x)$에 가까워지도록 한다.
  • the commitment loss: encoder의 weight에만 영향을 준다. encoder의 출력이 선택된 codebook 벡터에 가까워지도록 해서 여러 codebook 사이를 자꾸 왔다갔다하지 않도록 하는 역할을 한다.

본 논문에서는 여기에 exponential moving average를 적용시킨다.


3. 방법(Method)

두 단계로 이루어진다.

  1. 이미지를 discrete latent space로 mapping하기 위해 VQ-VAE를 학습시킨다.
  2. 모든 데이터를 사용하여 PixelCNN prior를 이 discrete latent space에 fit시킨다.
VQVAE2

3.1 Stage 1: Learning Hierarchical Latent Codes

vanilla VQ-VAE와 다른 점은 더 큰 이미지를 다룰 수 있기 위해 vector quantized codes를 계층 구조로 사용한다는 것이다.

VQVAE2

위 그림에서 원본 이미지를 인코딩하여 얻은 bottom latent code는 세부적인 부분을 모델링하고, 이 bottom latent code를 한번 더 인코딩한 Top latent code는 global한 특징을 모델링한다. 여기서 bottom latent code는 top latent code에 의존하는데, 그래야 top latent code가 세부적인 특징까지 혼자 다 모델링하려고 하는 현상이 방지된다(분업한다고 생각하면 된다).

256 x 256 이미지는 bottom level에서 64 x 64로 줄어들고, top level은 32 x 32 크기를 갖는다. Decoder 부분에서는 인코딩된 vector quantized code를 전부 받아서 디코딩을 수행한다. 이는 residual block과 strided transposed convolution으로 수행된다.

VQVAE2

3.2 Stage 2: Learning Priors over Latent Codes

이미지 압축 및 stage 1에서 학습한 모델로부터 샘플링을 할 수 있도록 prior를 latent code로 학습시키는 단계이다. Prior를 학습 데이터로 학습시킴으로써 성능을 향상시키고 marginal posterior와 prior 간 괴리를 줄이며, 학습된 prior로부터 샘플링된 latenr variable은 decoder가 학습하는 동안 관찰한 것과 비슷해진다.
이러한 관점에서, prior를 학습된 posterior에 fit하는 과정은 latent variable을 re-encoding함으로써 latenr space를 무손실 압축하는 것으로 볼 수 있다(결과는 Shannon’s entropy에 가깝다). 따라서 학습된 prior의 NLL과 true entropy의 괴리를 줄이고, 더 실제적인 이미지 샘플을 기대할 수 있다.

VQ-VAE framework에서, 이 auxiliary prior는 post-hoc, stage 2에서 PixelCNN과 같은 강력한 회귀모델로 모델링된다.

  • Top latent map에서의 prior는 전체 구조를 모델링하는 책임이 있으므로 multi-head self-attention layer를 사용, spatial location 간 상관관계를 얻기 위해 더 큰 receptive field를 사용할 수 있다.
  • 이와 대조적으로, bottom level에서의 조건부 prior는 local info를 모델링한다. 여기서는 메모리 문제 때문에 self-attention layer를 쓰는 것은 힘들고, 대신 large conditioning stacks를 사용한다.
  • 더 자세한 내용은 알고리즘 3 참조.

Top-level prior는 32 x 32 latent variable을 모델링한다.

  • 매 5개의 layer마다 residual gated conv layer + causal multi-headed attention을 추가한다.
  • 각 attention matrix, residual block 뒤에 dropout을 추가한다.
  • PixelCNN stack에다가 1x1 conv로 구성된 deep residual net을 추가하는 것은 학습 시간이나 메모리 사용량을 별로 늘리지 않으면서 likelihood를 증가시킬 수 있다.

Bottom level에서는 64 x 64 latent variable을 사용한다.

  • 앞서 언급했듯 여기서 같은 방식을 사용하면 자원 사용량이 너무 많아지다.
  • 그래서 attention layer를 따로 사용하지 않는다.

3.3 Trading off Diversity with Classifier Based Rejection Sampling

GAN과는 다르게 Maximum Likelihood 기반 확률모델은 모든 학습 데이터 분포(+ 모든 mode에 대한 데이터)를 모델링하는 것이 강제된다. 최근 GAN framework 중에서는 다양성과 품질을 trade-off하는 샘플 선택을 자동화하는 과정을 제안하기도 했다.

우리가 생성한 샘플이 실제 data manifold에 더 가까울수록, 그 샘플들이 사전학습된 분류기에 의해 올바른 class label로 분류될 가능성이 더 증가한다는 직관에 기반해서, 이 논문에서는 샘플의 다양성과 품질을 trade-off하는 자동화된 방법을 제안한다. 특히, 분류기가 올바른 class로 분류할 확률에 따라 샘플의 점수를 매기기 위해 ImageNet에서 학습된 분류 network를 사용한다.


4. 관련 연구(Related Works)

  • VQ-VAE
  • Gated PixelCNN(+self-attention)
  • BigGAN: 구조적인 이점, 안정화 방법, TPU로 모델을 scale up하는 것 등으로 FID/Inception score에서 SOTA 모델이다.

5. 실험(Experiments)

256 x 256 ImageNet에서 학습한 모델의 양적/질적 결과를 (BigGAN-deep과) 비교한다.

5.1 Modeling High-Resolution Face Images

데이터 상 매우 긴 범위의 의존성을 잡아내기 위한 방법으로 이 논문에서 제시한 multi-scale 접근법을 평가하기 위해 FFHQ dataset(1024 x 1024)에서 3-level 계층 모델을 학습시킨다. 이 데이터셋은 성별, 인종 등 다양한 domain으로 구성된 7만 개의 고품질 초상화 (사진)으로 구성되어 있다.

초장거리 의존성의 예: 인물 사진의 경우 양쪽 눈이 (거의) 대칭적으로 이루어져 있어야 한다. 이는 수백 pixel 떨어진 곳에서 동일한 색상+ 비슷한 크기 등으로 이미지를 생성해 내야 하는, 장거리 의존성에 대한 이해가 필수이다.

VQVAE2
VQVAE2
VQVAE2

5.2 Quantitative Evaluation

5.2.1 Negative Log-Likelihood and Reconstruction Error

Likelihood 기반 생성모델을 사용하는 핵심 이유 중 하나는 일반화에 대한 성능 평가가 가능하여 over-fitting이 일어나는지를 관찰할 수 있다는 것이다.
일반적으로 사용되는 FID와 Inception score의 경우 일반화 문제를 무시한다.

그래서 NLL(+MSE)로 top & bottom prior에 대한 결과가 아래 표에 있다. 여기서 NLL 값은 같은 사전학습 VQ-VAE를 사용한 경우에만 비교가 유효하다.

VQVAE2

5.2.2 Precision - Recall Metric

PR metric은 GAN에서 FID와 Inceptino score의 대안으로서 제안되었다. 아래 그림에서 BigGAN-deep와 비교한 결과를 볼 수 있다. Precision은 VQ-VAE가 조금 낮지만, Recall은 더 높다.

VQVAE2

5.3 Classification Accuracy Score

최근 제안된 평가방법인 Classificatino Accuracy Score(CAS)로도 비교하였다. 이는 ImageNet 분류기를 후보 모델에서 생성된 샘플에서만 학습하고 test set의 real image에서 분류 정확도를 측정하여 결과적으로 품질과 다양성을 평가할 수 있는 방법이다. 결과는 아래와 같다.

VQVAE2

VQ-VAE의 경우 압축 때문에 high-frequency signal(~noise)이 부족하다.

VQ-VAE reconstruction은 “domain gap”을 좁히고 분류기를 재학습시키지 않고도 더 높은 CAS score를 받았다.

5.3.1 FID and Inception Score

단점이 존재하기는 하지만 GAN을 평가하는 가장 일반적인 방법인 FID와 Inception score로도 평가를 진행하였다. 결과는 위에 있는 그림 7a에서 볼 수 있다.

다양성과 품질을 trade-off하는 방법으로 classifier-based rejection sampling을 사용하였다.

VQ-VAE는 FID와 IS 모두 향상되었다(30 $\rightarrow$ 10). BigGAN-deep에서 rejection sampling은 BigGAN 논문에서 제안된 truncation method보다 낫다.


6. 결론(Conclusion)

VQ-VAE와 강력한 회귀모델을 prior로 사용하여 다양한 고해상도 이미지를 생성하는 간단한 방법을 제시하였다. 계층적 구조의 latent map을 사용하여 SOTA GAN과 비슷한 수준의 이미지 생성 결과를 보여주었고 GAN 방식이 아닌 생성 모델의 한 갈래를 제시했다는 점에서 높이 평가할 만한 논문이다.


참고문헌(References)

논문 참조!


부록 A(Architecture Details and Hyperparameters)

A.1 PixelCNN Prior Networks

VQVAE2
VQVAE2

A.2 VQ-VAE Encoder and Decoder

VQVAE2

부록 B(Additional Samples)

논문 전체 및 무손실 압축으로 rendering된 결과 등을 추가로 보고 싶다면 아래 링크를 참조하면 된다.

  • https://drive.google.com/file/d/1H2nr_Cu7OK18tRemsWn_6o5DGMNYentM/view?usp=sharing
Comment  Read more

VQ-VAE 논문 설명(Neural Discrete Representation Learning)

|

이 글에서는 2017년 NIPS에 게재된 Neural Discrete Representation Learning(흔히 VQ-VAE라 부른다) 논문을 살펴보고자 한다.

중요한 부분만 적을 예정이므로 전체가 궁금하면 원 논문을 찾아 읽어보면 된다.


Neural Discrete Representation Learning

논문 링크: Neural Discrete Representation Learning

Github(not official?): https://github.com/1Konny/VQ-VAE

  • 2017년 11월, NIPS 2017
  • DeepMind
  • Aaron van den Oord, Oriol Vinyals, Koray Kavukcuoglu

초록(Abstract)

어떠한 지도 없이 유용한 표현을 학습하는 것은 머신 러닝의 핵심 과제로 남아 있다. 본 논문에서는 이러한 이산 표현을 학습하는 간단하면서도 강력한 생성 모델을 제안한다. 제안하는 VQ-VAE(Vector Quantised-Variational AutoEncoder) 모델은 두 가지 면에서 VAE와 다르다:

  1. Encoder network는 연속적인 codes를 생성하나 VQ-VAE는 이산 codes를 출력한다.
  2. Prior는 정적(static)이지 않고 대신 학습이 가능하다.

이산 잠재 표현을 학습하기 위해 벡터 양자화(VQ: Vector Quantisation)의 아이디어를 통합하였다. VQ 방법을 사용하면 모델이 강력한 autoregressive decoder와 짝을 이룰 때 latent들이 무시되는 “Posterior Collapse” 문제(VAE framework에서 곧잘 나타난다)를 피할 수 있다.

이러한 표현을 autoregressive prior와 짝지으면 모델은 고품질 image, video, audio을 생성할 수 있을 뿐만 아니라 speaker conversion 및 음소의 비지도 학습을 수행하여 학습된 표현이 유용함을 보일 수 있다.


1. 서론(Introduction)

Image, audio, video를 생성하는 분야에서는 많은 발전이 있었다. 어려운 과제인 few-shot learning, domain adaptation, RL 등은 학습된 표현에 크게 의존하였으나 일반적 표현을 얻는 것은 여전히 한계가 있다. Pixel domain에서 가장 효과적인 모델은 PixelCNN(1, 2)이지만, 연속적인 표현을 사용한다. 이 논문에서는, 연속(continuous)이 아닌, 이산적(discrete)인 표현을 다룬다.

언어는 본질적으로 이산적인 성질을 가지며(단어의 수는 한정적이며, 단어와 단어 사이 중간쯤이 명확히 정의되지 않음을 생각하면 된다), 음성도 비슷한 특성을 가진다. 이미지는 언어로 표현될 수 있다. 이러한 점에서, 이산적인 표현은 이러한 이산적인 domain에 잘 맞을 것이라 생각할 수 있다.

이 논문에서는 VAE와 이산표현을 결합한 새로운 생성모델(VQ-VAE)을 제안한다. Vector Quantisation(VQ)를 사용하여 너무 큰 분산으로 생기는 어려움을 피하면서 학습하기 편하고 Posterior Collapse 문제를 회피할 수 있다. 그러면서도 연속표현을 사용하는 모델과 비등하면서도 이산표현의 유연함을 제공한다.

VQ-VAE는 데이터 공간을 효과적으로 사용할 수 있게 하여, 큰 차원의 데이터(이미지의 픽셀, 음성의 음소, 텍스트의 메시지 등)에서 local이라 부르는 작은 부분, noise에 집중하는 대신 중요한 feature만을 성공적으로 모델링할 수 있게 한다.

또 강력한 prior를 제공할 수 있는데, 단어나 음소에 대한 어떤 사전 지식 없이도 언어의 구조를 파악할 수 있거나, 말하는 내용은 그대로 두면서 목소리만 바꿀 수(speaker conversion)도 있다.

그래서 이 논문이 기여한 바는,

  • “posterior collapse” 문제에서 자유롭고 큰 분산 문제가 없는, 이산표현을 사용하는 VQ-VAE 모델을 제안한다.
  • 이산표현 모델 VQ-VAE는 연속표현 모델만큼이나 성능이 좋음을 보인다.
  • 강력한 prior가 있을 때, sample은 speech/video generation과 같은 다양한 응용 분야에서 뛰어난 결과를 생성한다.
  • 어떤 명시적인 지도 없이도 언어의 속성을 파악하고 speaker를 바꿀 수도 있다.

2. 관련 연구(Related Work)

VAE는 여러 방면에서 연구되어 왔지만, discrete domain을 가지는 분야에서조차 연속표현을 사용해왔다.

사실 이산적인 변수는 backprop이 불가능하여, 이산표현의 특성을 일부 가지면서도 미분이 가능하도록 대체 방안이 연구되었다. Concrete softmaxGumbel-softmax가 대표적인 예이다.

또, PixelCNN, Vector Quantisation 등이 연관 분야로 수록되어 있다.


3. VQ-VAE

VAE가 가장 연관이 있을 분야라고 논문에서는 언급한다(그러나 사실 VAE가 아니라 AE에 더 가깝다고 생각되기도 한다).

VAE는 input data $x$, prior distribution $p(z)$가 주어질 때,

  • 이산 latent random variable $z$에 대해 posterior distribution $q(z \vert x)$를 parameterise하는 encoder,
  • input data에 대한 분포 $p(x \vert z)$를 다루는 decoder

로 구성된다.

VAE에서 내부적으로 취급하는 분포는 대개 Gaussian 분포를 따른다고 가정한다. 확장 버전은 autoregressive prior, posterior model, normalising flow, inverse autoregressive posterior 등을 포함하기도 한다.

VQ-VAE는 여기에 이산 표현을 다루도록 한다. VQ른 사용하면서, posterior과 prior distribution은 categorical하며, 이 분포로부터 생성된 sample은 embedding table을 indexing한다. 이 embeddings는 decoder의 입력으로 들어간다.

3.1 Discrete Latent variables

VQVAE

위 그림에서 embedding $e \in R^{K \times D}$가 이산표현을 나타낸다. 이를 codebook이라 하며, $K$는 이산 표현 공간의 크기($K$-way categorical과 같음), $D$는 각 embedding vector $e_i$의 차원이다.

즉 $e_i \in R^D, i \in 1, 2, …, K$이며, embedding vector가 $K$개가 있는 것이다.

모델의 encoder는 입력 $x$를 받아 $z_e(x)$를 출력한다. 이산표현벡터 $z$는 embedding space $e$에서 가장 가까운 embedding vector를 찾는다(look-up).

VQVAE

그래서 이 모델을 VAE라 할 수 있으며(논문 주장), $\log p(x)$를 ELBO로 bound할 수 있다. 제안한 분포 $q(z=k \vert x)$는 deterministic하고 $z$에 대해 단순균등 prior를 정의함으로써 KL divergence를 상수($\log K$)로 얻을 수 있다.

표현 $z_e(x)$는 식 1, 2에 주어진 대로 임베딩 $e$ 중 가장 가까운 원소를 찾고 discretisation bottlenect으로 전달된다.

[z_q(x) = e_k, \quad \text{where} \quad k=\argmin_j \Vert z_e(x) - e_j \Vert_2 \qquad (2)]

3.2 Learning

한 가지 중요한 점은 식 2에서는 real gradient가 없다는 점이다.

  • 이는 straight-through estimator와 비슷한 방법을 사용하여 gradient를 근사할 수 있다.
  • decoder input $z_q(x)$를 encoder output으로 gradient를 복사하면 된다.
  • Quantisation operation을 통해 subgradient를 사용할 수도 있지만, 본 논문의 실험에서는 위의 단순한 estimator만으로도 충분했다.

Forward에서는 $z_q(x)$가 decoder로 전달된다.
Backward에서는 gradient $\nabla_zL$이 encoder로 그대로 전달된다.

Encoder의 출력과 Decoder의 입력은 $D$ 차원의 같은 공간에 존재하여, gradient가 어떻게 변화해야 하는지 정보를 줄 수 있다.

전체 objective는 다음 식으로 표현된다.

[L = \log p(x \vert z_q(x)) + \Vert \text{sg}[z_e(x)]-e \Vert_2^2 + \beta \Vert z_e(x)-\text{sg}[e] \Vert_2^2 , \qquad (3)]

  1. 1번째 항은 reconstruction loss으로 위에서 설명한 estimator를 통해 decoder와 encoder를 모두 최적화한다.
  2. 임베딩 $e_i$는 어떤 gradient도 받지 못하기 때문에 Vector Quantisation(VQ)를 사용한다.
    • VQ objective는 각 e를 encoder의 출력 $z_e(x)$로 이동하게끔 한다. 이 부분이 2번째 항이다.
  3. embedding space는 무한하기 때문에 $e_i$는 encoder parameter만큼 빠르게 학습되지 않을 수 있다. Encoder가 embedding과 출력이 grow할 수 있게 만들기 위해 3번째 항 commitment loss를 추가한다.

sg는 stop gradient를 의미한다. 또 $\beta$는 commitment loss의 중요도를 정하는 hyperparameter인데, 논문의 저자는 모델이 이 값에 robust하다고 한다. $\beta$는 0.1~2.0의 값에서 최종 결과가 그다지 변하지 않았으며 모든 실험에서 $\beta=0.25$를 사용했다고 한다.

Embedding $e_i$들은 벡터의 형태로 설명하였지만, ImageNet 등 image에서는 2차원 이상의 형태를 갖는다(ImageNet: 32 x 32, CIFAR10: 8 x 8 x 10). embedding vector의 수는 총 $K$개이며, k-means와 commitment loss를 계산할 때 평균을 취한다.

논문의 이 부분에는 $N$이라 되어 있는데, 이후 부분 및 다른 논문들은 embedding space(codebook)의 크기를 $K$로 쓴다.

모델 $\log p(x)$는 다음과 같다.

[\log p(x) = \log \sum_k p(x \vert z_k)p(z_k)]

decoder $p(x \vert z)$는 MAP 추론으로부터 $z=z_q(x)$로 학습되었다.

따라서 $z \ne z_q(x)$인 경우에 decoder는 어떤 확률밀도도 구할 필요가 없다. 즉,

[\log p(x) \approx \log p(x \vert z_q(x))p(z_q(x))]

이다. Jensen’s equality를 생각하면 부등호로 바꿔 쓸 수 있다.

3.3 Prior

Discrete latents $p(z)$에 대한 prior distribution은 categorical distribution이며, feature map 안에서 다른 $z$에 의존하여 autoregressive하게 만들어질 수 있다. VQ-VAE를 학습하는 동안 prior는 상수로, 균등하게 유지된다.

학습 후에는, $z$에 대한 자동회귀 분포에 맞춰서 ancestral sampling을 통해 $x$를 생성할 수 있다.

Image에 대해서는 PixelCNN을, raw audio에 대해서는 WaveNet 모델을 사용한다. Prior와 VQ-VAE를 같이 학습시킴으로써 더 좋은 결과를 얻는 것은 추후 연구로 남겨두었다.

4. 실험(Experiments)

4.1 Comparison with continuous variables

VQ-VQE, 그냥 VAE(continuous variables 사용), VIMCO(독립 Gaussian or categorical prior)를 비교한다. 각 모델은 각각 다음과 같은 값을 갖는다.

VAE VQ-VAE VIMCO
4.51 bits/dim 4.67 bits/dim 5.14 bits/dim

중요한 목표는 discrete latent를 사용해도 continuous latent를 사용했을 때와 비교해서 성능이 충분히 좋은지를 확인하는 것인데, 그 목표는 달성된 듯 하다.. 이후 결과에서 생성 결과를 볼 수 있다.

4.2 Images

ImageNet의 $128 \times 128 \times 3$ 크기의 이미지를 purely deconvolutional $p(x \vert z)$를 통해 $z=32 \times 32 \times 1$의 discrete space로 압축한다($K=512$이다). 따라서 $z$의 하나의 unit에 담긴 정보는 다음과 같다.

[\frac{128 \times 128 \times 3 \times 8}{32 \times 32 \times 9} \simeq 42.6]

바꿔 말하자면 42.6배 압축되었다고도 볼 수 있다. $32 \times 32$의 각 bit는 embedding space의 index를 나타내며, 9라는 숫자는 $\log K=\log(512)=9$에서 나왔다(9bit면 512개의 숫자를 표현할 수 있음을 생각하면 된다).

그리고 encoder에 의해 생성된 $z$를 갖고 prior인 PixelCNN를 학습시킨다. 이는 학습이나 sampling 속도를 크게 향상시켜주는 방법은 아니지만, 너무 디테일한 부분(noise 등)보다는 이미지의 전체적인 부분을 잡아낼 수 있도록 하는 것에 가깝다.

VQVAE

왼쪽 사진을 $z$로 변환했다가 VQ-VAE의 decoder로 다시 복원한 게 오른쪽 이미지들이다. 디테일은 살짝 사라졌으나(약간 blurry해짐) 거의 원상복구된 것을 볼 수 있는데, 이는 discrete encoding을 통해 차원을 매우 줄였음에도 중요한 정보는 잃지 않고 압축할 수 있음을 보여준다.

PixelCNN을 discretised $32 \times 32 \times 1$ latent space에서 학습시킨 다음 생성한 이미지는 아래에서 볼 수 있다.

VQVAE

DeepMind Lab 환경에서 얻은 $84 \times 84 \times 3$의 이미지에 같은 실험을 한 결과는 아래에서 볼 수 있다.

VQVAE

마지막으로, DM-Lab frame에서 1번째 VQ-VAE에서 얻은 $21 \times 21 \times 1$ latent space 상에서 2번째 VQ-VAE를 PixelCNN decoder로 학습시켰다. 이러한 세팅은 “posterior collapse” 문제를 피할 수 있게 해 준다. 여기서 latent variable은 단 3개만 사용하여, 전체 bit는 $3 \times 9 = 27$bit로 float32보다도 작게 된다. 결과는 그림 5에서 볼 수 있다.

VQVAE

4.3 Audio

참고: 생성된 오디오 샘플은 홈페이지에서 확인할 수 있다.

109명의 speaker의 음성 녹음본이 포함된 VCTK 데이터셋을 학습에 사용했다. 6 strided convolution, stride 2, window-size 4를 사용하여 원본 파일보다 64배 압축하는 데 성공했다. latent는 512차원이며, decoder는 latent와 speaker를 나타내는 one-hot embedding 모두에 의존성을 갖는다.

VQVAE

우선 VQ-VAE를 오직 long-term 상관관계(정보)만을 보존하도록 latent space를 만든 뒤 decoder로 복원하는 작업을 수행하였다. 홈페이지에서 예시를 들어보면 알 수 있겠지만, 그 내용은 변하지 않았으나 운율은 상당히 바뀐 것을 들을 수 있다. 이는 VQ-VAE가 어떤 언어적 지도 없이 고수준의 추상공간을 이해하고 중요하지 않은 부분은 버리며 음성의 내용만을 잡아냈음을 뜻한다.

다음은 unconditional sample을 분석하는 실험인데,

  • audio에서 추출한 latent representation이 주어지면
  • 이걸로 prior을 학습시켜 데이터의 장기(long-term) 의존성을 모델링하는 것이다.

결과적으로,

  • 40960 timestep을 320 latent timestep으로 줄였다.
  • 원래 WaveNet에서는 상당히 시끌벅적한?(babbling) 소리가 생성된 반면에 VQ-VAE는 상대적으로 깨끗한 소리를 생성하였다.
  • 이는 가장 기본적인 음소 수준을 모델링할 수 있음을 보여준다.

3번째 실험은 speaker를 바꾸는 것이다. 즉, A라는 사람이 말한 내용을 그대로 말하되 B의 목소리로 바꾸는 것인데, 홈페이지를 가서 들어보면 꽤 잘 바뀌었다.

마지막으로 볼 것은 latent를 더 잘 이해하기 위해 각 latent를 GT phoneme-sequence와 비교한 것이다. 각 latent를 41개의 음소와 대응시켜서 classification을 수행해 보면 49.3%로 랜덤인 경우 7.2%에 비해 매우 높음을 볼 수 있다. 즉 VQ-VAE의 latent는 어떤 언어적 지도 없이도 음소 정보를 터득했다고 볼 수 있을 듯하다.

4.4 Video

DeepMind Lab 환경에서 처음 6 frame이 주어지면 나머지 10 frame을 이어지는 내용으로 채우는 task인데, 여기서 VQ-VAE가 하는 것은 오직 latent space($z_t$) 상에서만 생성할 뿐 이미지를 직접 생성하지는 않는다.

sequence $x_i$ 안의 각 이미지는 prior model만 사용하여 모든 latent를 생성한 후 deterministic decoder로 대응되는 latent와 mapping시켜서 생성하게 된다. 따라서 VQ-VAE는 latent space 안에서만 수행하고 pixel space에서는 작업하지 않는다. 생성 결과는 아래 그림과 같다.

VQVAE

5. 결론(Conclusion)

  • VAE와 discrete latent 표현을 위한 VQ를 결합하여 새로운 생성 모델을 만들었다.
  • VQ-VAE는 long-term dependency를 잘 모델링할 수 있다.
  • 원본 source를 작은 latent로 수십 배 압축할 수 있다.
  • 이러한 latent는 discrete하며, continuous latent와 비교하여 성능이 필적할 만하다.
  • Image, audio, video 모두에 대해서 잘 모델링 및 압축한 후 중요한 내용을 잘 보존하면서 복원이 가능하다.

즉, 이 논문은 discrete latent representation을 잘 정립한 논문이라 할 수 있겠다.


참고문헌(References)

논문 참조!


Comment  Read more

Margin-based Loss 설명

|

이 글에서는 Margin-based Loss를 정리한다.


Margin-based Loss

간단하게는 true target $y$와 prediction result $\hat{y}$의 곱 $y\hat{y}$을 갖고 계산하는 loss라고 생각할 수 있다.

Distance-based Loss와는 다르게, true target과 prediction 사이의 차이(difference)에 대해 신경 쓰지 않는다. 대신, target의 sign과 얼마나 잘 agree(혹은 일치)하는지에 기반한 prediction을 penalize한다.

Margin-based Loss는 단 하나의 변수 $v = yf(x)$에 의해 정의될 수 있고, 적절히 선택된 함수 $\phi : \mathbb{R} \rightarrow \mathbb{R}$에 대해 $V(f(\vec{x}), y) = \phi(yf(\vec{x})) = \phi(v)$이다.

보통 이진 분류(binary classification)에서 유용하게 사용된다.


ZeroOneLoss

전통적인 분류 loss로, 간단히 말해서 맞으면 loss가 0, 틀리면 1이다. non-convex, non-continuous하며 그냥은 잘 쓰이지 않는다. 대신 surrogate loss인 L1HingeLoss 등을 쓴다.


PerceptronLoss

agreement $\le 0$일 수록 penalize하는 방법으로 Lipschitz continuous, Lipschitz convex하지만 strict convex하지는 않다.


L1HingeLoss

PerceptronLoss와 비슷하지만 agreement $\le 1$인 경우에 penalize한다는 점이 다르다.


SmoothedL1HingeLoss

L1 Hinge Loss와 비슷하지만, $y\hat{y}=1$인 지점에서 미분이 안 되는 점을 보완한 것으로 부드럽게 꺾이는 것을 볼 수 있다. 여전히 strict convex하지는 않다. parameter로 $\gamma$와 $\alpha$가 있다.


ModifiedHuberLoss

SmoothedL1HingeLoss에서 $\gamma=2$인 특수한 경우이다.


DWDMarginLoss

Distance Weighted Discrimination margin loss이다. L1HingeLoss의 미분가능한 일반적인 버전으로 SmoothedL1HingeLoss와는 다른 loss 함수이다.


L2MarginLoss

L2 loss를 생각하면 된다. agreement $\ne 1$인 경우에 모두 이차함수적으로 penalize하는 방식이다. Lipschitz continuous하며 strongly convex하다.


L2HingeLoss

L1HingeLoss와 L2 margin loss를 합친 것이라고 생각하면 된다. agreement $\lt 1$인 경우에 이차함수적으로 penalize한다. 지역적으로 Lipschitz continuous하며 convex하지만 strongly convex하지는 않다.


SigmoidLoss

$(0, 2)$ 범위에서 모든 예측 결과에 대해 penalize하는 방법으로 무한히 미분 가능하며 Lipschitz continuous하지만 non-convex하다.


LogitMarginLoss

Logistic loss의 margin 버전이다. 무한히 미분 가능하며 Lipschitz continuous하다.


ExpLoss

모든 예측 결과를 지수적으로 penalize한다. 무한히 미분 가능하며 Lipschitz continuous하고 또한 strictly convex하지만, clipable하지는 않다.


Comment  Read more

CNN 기본 모델(ImageNet Challenge - AlexNet, ZFNet, VGG, GoogLeNet, ResNet, InceptionNet)

|

이 글에서는 ImageNet Challenge에서 2012~2015년까지 좋은 성능을 낸 대표적인 모델인 AlexNet, ZFNet, VGG, GoogLeNet(InceptionNet), ResNet을 살펴본다.

ImageNet에서 사람의 오류율(이미지 class를 잘못 분류한 비율)은 5.1%로 나와 있음을 참고한다.
각각에 대해 간단히 설명하면,

  • AlexNet: ImageNet Challenge에서 사실상 최초로 만든 Deep Neural Network 모델이다(이전에는 Shallow model이 대세였다). 2012년, 8 layers, 오류율 16.4%.
  • ZFNet: AlexNet을 최적화한 모델이다. 2013년, 8 layers, 오류율 11.7%.
  • VGGNet: Filter의 size를 크게 줄이고 대신 더 깊게 layer를 쌓아 만든 모델이다. 2014년, 19 layers, 오류율 7.3%.
  • GoogLeNet: InceptionNet 으로도 부른다. 이름답게 Google에서 만들었으며 한 layer에서 여러 크기의 Conv filter를 사용하여 성능을 높였다. 2014년, 19 layers, 오류율 6.7%.
  • ResNet: Residual Network를 개발한 논문으로 identity mapping을 추가하는 기술을 통해 깊이가 매우 깊어진 모델의 학습을 가능하게 하였다. 2015년, 152 layers, 오류율 3.6%. 이때부터 사람의 정확도를 능가하였다고 평가받는다.
  • Inception v2,3, v4: GoogleNet(Inception)을 개량한 버전으로 ResNet보다 더 높은 성능을 보여준다. 2016년.

AlexNet

논문 링크: AlexNet

2012 NIPS에서 발표된 ImageNet Challenge에서의 (사실상) 최초의 Deep Neural Network이다.

8개의 layers를 쌓은 지금으로서는 상당히 간단한 모델이지만 당시에는 꽤 복잡한 모델이었다.

8개의 layers라는 말은 학습가능한 parameter가 있는 layer의 개수를 의미하며 learnable parameters가 없는 pooling layer 등은 제외한다.

입력 이미지 크기는 [224, 224, 3]이며 이 이미지는

  • conv - pooling - layer norm을 총 2번 거친 다음
  • conv layer를 3번 연속 통과하고
  • pooling layer를 1번 통과한 뒤
  • fully connected layer를 3번 통과하여 최종적으로 1000개의 class일 확률을 예측하는 [1000, 1] 벡터를 출력한다.

첫 2개의 conv layer에서는 각각 크기가 11, 5인 filter를 사용하는데, 이는 지금 기준으로 매우 큰 크기이다. 이는 이후 모델이 발전하면서 작아지는 쪽으로 바뀌게 된다.

전체 구조를 정리하면 다음과 같다.

Layer Input size Filters Output size
Conv 1 [224, 224, 3] 96 [11 x 11] filters, stride=4, pad=1.5 [55, 55, 96]
Pool 1 [55, 55, 96] [3 x 3] filters, stride=2] [27, 27, 96]
Norm 1 [27, 27, 96] Layer Norm(not Batch Norm) [27, 27, 96]
Conv 2 [27, 27, 96] 256 [5 x 5] filters, stride=1, pad=2 [27, 27, 256]
Pool 2 [27, 27, 256] [3 x 3] filters, stride=2] [13, 13, 256]
Norm 2 [13, 13, 256] Layer Norm(not Batch Norm) [13, 13, 256]
Conv 3 [13, 13, 256] 384 [3 x 3] filters, stride=1, pad=1 [13, 13, 384]
Conv 4 [13, 13, 384] 384 [3 x 3] filters, stride=1, pad=1 [13, 13, 384]
Conv 5 [13, 13, 384] 256 [3 x 3] filters, stride=1, pad=1 [13, 13, 256]
Pool 3 [13, 13, 384] [3 x 3] filters, stride=2] [6, 6, 256]
FC 6 [6, 6, 256] Fully-connected [4096]
FC 7 [4096] Fully-connected [4096]
FC 8 [4096] Fully-connected [1000]

살펴볼만한 특징은,

  • 이 논문은 최초의 CNN 기반 모델로 ReLU를 처음 사용하였다.
  • Normalization Layer를 사용하였는데, 참고로 최근에는 거의 쓰이지 않는다.
  • Data Augmentation을 상당히 많이 사용하였다.
  • Dropout 0.5, Batch size 128, SGD(Momemtum 0.9)
  • Learning rate는 0.01 이후 성능이 정체되면 1/10으로 줄인다.
  • L2 weight decay(5e-4)를 hyperparameter로 사용하였다.

ZFNet

논문 링크: ZFNet

AlexNet을 최적화하여 다음 연도(2013년)에 발표된 논문으로, 모델의 구조는 딱히 다를 것이 없으나 filter size 등 여러 hyperparameter를 최적화하여 성능을 상당히 높인 모델이다.


VGGNet

논문 링크: VGGNet

AlexNet의 필터 크기는 11, 5로 상당히 크다. 이는 parameter의 수와 계산량을 크게 증가시키는데, 2014년 발표된 VGGNet에서는 filter 크기를 3인 것만 사용하고, 대신 모델의 깊이를 더 깊게 쌓아서 더 좋은 성능을 얻는 데 성공한다.

예로 [5 x 5] filter 1개를 사용하는 경우와 2개의 [3 x 3] filter를 사용하는 경우를 비교하면, 둘 다 [5 x 5] 범위를 살펴볼 수 있다. 그러나,

  • 1개의 [5 x 5] filter는 총 $1 \times (5 \times 5) \times C^2 = 25C^2$개의 parameter를 사용한다.
  • 2개의 [3 x 3] filter는 총 $2 \times (3 \times 3) \times C^2 = 18C^2$개의 parameter를 사용한다.

즉 갈은 범위를 처리할 수 있으면서도 필요한 parameter 수는 크게 줄어든다. [11 x 11]의 경우는 차이가 훨씬 크게 나게 된다.

VGGNet의 경우 버전이 여러 개 있는데, 보통 각각 16, 19개의 layer를 사용한 VGG16과 VGG19가 현재까지도 곧잘 사용된다. filter size와 layer의 수를 제외하면 큰 구조는 AlexNet과 꽤 비슷하다.

오류율이 7.3%로 줄어들어 사람의 성능(?)과 매우 근접한 수준까지 온 모델이다. VGGNet의 상세한 사항은 AlexNet과 비슷하지만, AlexNet에서는 사용한 local-response Normalization(LRN) layer를 사용하지 않았다. Batch size는 256으로 증가되었다.


GoogLeNet

논문 링크: GoogLeNet

역시 2014년 발표된 논문이다. 모델이 점점 더 깊어진다는 뜻에서 inception module이라는 것을 사용한다(영화 인셉션을 생각하라..).
각 conv layer에서, filter size를 1,3,5로 다양하게 사용하여 여러 receptive field size를 취하고 channel별로 concat하여 사용한다. 이를 통해 좀 더 다양한 정보를 학습할 수 있다.

왼쪽이 Inception Module의 구상이고, 오른쪽은 계산량을 줄이기 위해 [1 x 1] conv를 앞에다 붙여서 사용한 것을 나타낸다. 각 layer마다 사용하는 filter가 3개씩(+pooling) 있기 때문에 계산량이 매우 많아지는데, 계산량이 많을 수밖에 없는 [3 x 3]과 [5 x 5] 필터를 사용하기 전 [1 x 1] filter를 적용하여 채널 수를 줄인 다음 계산하면 계산량이 3~4배 줄어들게 된다.

전체 구조는 다음과 같다. 각 layer마다 inception module이 들어가기 때문에 매우 복잡해 보이지만, 총 깊이는 22 layer이다.

크게 4부분을 떼어 놓고 볼 수 있다.

  1. 맨 앞부분(빨간색 박스)은 input image를 받는 부분인데, Stem Network라 부른다. 이전 모델인 AlexNet과 VGGNet과 비슷하게, Conv-Pool-Norm-Conv-Conv-Norm-Pool Layer로 구성되어 있다.
  2. 중간 부분(노란색 박스)은 inception module를 쌓아 만든 부분이다.
  3. 마지막 부분(파란색 박스)은 앞에서 얻은 feature를 가지고 class를 분류하는 부분으로 Classifier output을 최종적으로 내보낸다.
  4. 아래쪽에 달려 있는 초록색 박스로 표시한 두 부분이 있는데, 이는 Auxilizary Classification loss를 사용하는 부분이다. GoogLeNet이 꽤 깊기 때문에 loss가 앞 layer까지 backprop이 잘 일어나지 않는다. 따라서 중간에 auxiliary classification loss를 추가하여 앞 부분에도 잘 전파될 수 있도록 하는 부분이다.

기타 살펴볼 특징은 다음과 같다.

  • 22층의 layer를 사용하였다.
  • AlexNet보다 12배, VGG16보다 27배 더 적은 parameter를 사용하면서도 성능이 더 좋다.
  • Learning rate는 매 8 epoch 마다 4%씩 감소시킨다.

ResNet

논문 링크: ResNet

Microsoft에서 개발한 모델로 2015년 발표되었고, 최초로 사람의 분류 성능을 뛰어넘은 모델로 평가된다.

매우 깊은 모델(152층)이며, 이 이후부터는 매우 깊고 큰 모델을 사용하게 된다.

ResNet의 출발점은 다음과 같다. 어떤 shallow 모델이 있고, 여기에 더해 Layer를 몇층 더 쌓은 deep 모델이 있다. 그러면 deep model은, shallow 모델을 포함하니까 적어도 shallow 모델만큼은 성능이 나와 주어야 하는데(추가한 layer는 identity mapping을 한다고 하면 명백하다), 실제로 실험을 해보면 그렇지 않은 결과가 나온다. 이는 깊은 모델일수록 학습이 잘 이루어지지 않기 때문이다.

어쨌든 deep 모델이 shallow 모델만큼의 성능을 확보하려면, 강제적으로 이미 학습한 부분을 identity mapping으로 다음 layer에 전달하면 최소한 shallow 모델만큼은 성능이 확보될 것이다. 이 내용이 ResNet의 motivation이다.

그래서 그냥 identity mapping(혹은 Shortcut Connection이라고도 함)을 layer의 끝에다 그냥 더해버린다.

이러한 residual block을 152개까지 쌓는다. GoogLeNet과 비슷하게 Stem network가 처음에 있으며, 추가 FC layer는 사용하지 않는다.

각 block 내에는 각각 크기 1, 3, 1인 conv filter를 사용한다. ResNet도 여러 버전이 있는데(18, 34, 50, 101, 152 layers) 50 이후로는 사용하는 메모리에 비해 성능이 그닥 크게 증가하지는 않는다.

버전별 ResNet 구조는 다음과 같다.

  • Xavier Initialization을 사용하였다.
  • 모든 conv layer 이후 batch norm이 사용되었다.
  • Dropout은 사용하지 않는다.

InceptionNet v2,3, v4

논문 링크: Inception v2, 3, Inception v4

기존의 InceptionNet(GoogLeNet)을 발전시킨 모델이다.

v2, 3에서는 Conv Filter Factorization과 Grid Size Reduction을 통해 기존 모델을 발전시켰다.

Conv Filter Factorization은 [n x n] filter를 [1 x n], [n x 1] 2개로 나누어 계산하는 방법으로 $n \times n$ 범위를 처리할 수 있으면서 계산량을 줄일 수 있는 방법이다.

Grid size Reduction은 Pooling-Inception 순서로 할 경우 계산은 빠르지만 spatial 정보 손실이 일어나는 점, Inception-Pooling 순서의 경우 정보는 보존되지만 계산량이 많다는 점을 착안해, 이 두가지 방식을 적절히 섞어서(즉, 크기를 줄인 채 두 방법 모두를 사용하여) 2가지 장점을 모두 가지려 한 방법이라 생각하면 된다.

Inception v4는 ResNet 이후에 나온 모델이다. 그래서 Inception v3에다가 Residual 기법을 사용한 모델로, ResNet152보다 Inception v4의 성능이 더 좋다.


이후 모델은 ResNeXt, DenseNet, MobileNets 등이 있다.

Comment  Read more

HGT(Heterogeneous Graph Transformer) 설명

|

이번 글에서는 HGT란 알고리즘에 대해 다뤄보겠다. 상세한 내용은 논문 원본을 참고하길 바라며, 본 글에서는 핵심적인 부분에 대해 요약 정리하도록 할 것이다. 저자의 코드는 Github에서 확인할 수 있다.


Heterogeneous Graph Transformer 설명

1. Background

기존의 많은 GNN이 Homogenous Graph에만 집중된 것에 반해, HGT는 여러 node type, edge type을 가진 Heterogenous Graph 데이터에 대해 적합한 알고리즘으로 제안되었다.

Heterogenous Graph에 대한 접근법은 여러 가지가 있지만 대표적으로 meta-path를 이용한 방법과 GNN을 이용한 방법이 존재한다. 그런데 이러한 방법에는 몇 가지 결점이 존재한다.

  • heterogenous graph의 각 type에 맞는 meta-path design을 하려면 구체적인 domain 지식이 필요하다.
  • 다른 type의 node/edge가 같은 feature를 공유하거나, 혹은 아예 다른 feature를 갖는 경우 graph의 특징을 온전히 포착하기는 어렵다.
  • 모든 graph의 동적 특성은 대부분 무시되고 있다.

HGT의 목표는 다음과 같다.

  • Network dynamics는 포착하면서 각 node/edge-type에 적합한 representation 학습
  • customized meta-path를 특별히 설계하지 않음
  • Web-scale graph에 적합하도록 highly scalable할 것

2. Heterogenous Graph Mining

Heterogenous Graph의 정의에 대해 살펴보자.

[G = (\mathcal{V}, \mathcal{E}, \mathcal{A}, \mathcal{R})]

각 집합은 node, edge, node type, edge type을 의미한다. 이 때 각 node $v \in \mathcal{V}$ 이고, 각 edge $e \in \mathcal{E}$ 이다. 그리고 다음과 같은 type mapping 함수가 존재한다.

[\tau(v): V \rightarrow \mathcal{A}, \phi(e): E \rightarrow \mathcal{R}]

본격적인 구조 설명에 앞서 몇 가지 개념들에 대해 짚고 넘어간다.

Meta Relation
edge $e = (s, t)$ 가 존재할 때, 각 node $s, t$ 는 물론 edge $e$ 도 각자의 type을 가질 것이다. 이 때 이들 관계의 meta relation은 아래와 같이 표현할 수 있다.

[<\tau(s), \phi(e), \tau(t)>]

이는 기존의 여러 meta-path 방법론에서도 설명된 개념이다. 3개의 요소 모두가 같아야만 같은 관계로 인식된다. 그런데 HGT는 여기에서 시간의 개념을 추가한다.

Dynamic Heterogenous Graph
앞서 예시로 들었던 edge $e=(s, t)$ 에 timestamp $T$ 를 할당해보자. 이는 node $s$ 가 $T$ 시점에 node $t$ 와 연결되었음을 의미한다. 이러한 관계가 처음으로 나타났다면 $s$ 에게 $T$ 시점이 할당된다. 물론 node $s$ 가 여러 번 연결된다면 복수의 timestamp를 갖게 될 것이다.

이는 edge의 timestamp는 불변함을 의미한다. 당연하다. 예를 들어 어떤 논문이 WWW에 1994년에 등재되었다면, 이 때의 timestamp는 1994년인 것이다.


3. Heterogenous Graph Transformer

HGT의 목표는 source node로 부터 정보를 통합하여 target node $t$ 에 대한 contextualized representation을 얻는 것이다.

3.1. Heterogenous Message Passing & Aggregation

아래 그림은 전체적인 구조를 나타낸다. 총 $L$ 개의 Layer를 쌓는 방식으로 되어 있고, $H^l$ 은 $l$ 번째 HGT layer의 output이다.

(1), (2), (3)으로 구분되어 있듯이 이 과정은 크게 3가지로 구분되며, 효과적인 학습을 위해 3가지의 추가적인 장치가 배치된다. 추가적인 장치는 3.2에서 설명하도록 하겠다.

Step1: Heterogenous Mutual Attention
Step2: Heterogenous Message Passingg
Step3: Target-specific Aggregation

일단 주어진 상황은 다음과 같다. 특정 target node $t$ 가 존재할 때, 2개의 source node $s_1, s_2$ 가 $e_1, e_2$ 라는 edge를 통해 target node와 관계를 맺고 있는 것이다. 이 때 node인 $t, s_1, s_2$ 의 경우 node feature 벡터를 갖는다. (node feature가 없으면 인위적으로 생성해야 한다.) 각 feature 벡터의 길이는 일단 $d$ 로 같다고 가정한다. 실제로는 최초의 Projection Layer에서 같은 길이로 통일되기 때문에 node type별로 다른 feature 길이를 가져도 무방하다. 어쨌든 지금은 $d$ 라는 길이로 통일되어 있다고 생각하자. 그렇다면 지금까지의 이야기로 2개의 meta relation이 존재하는 것이다.

[<\tau(s_1), \phi(e_1), \tau(t)>, <\tau(s_2), \phi(e_2), \tau(t)>]

1번째 meta relation을 기준으로 이야기를 이어나가 보겠다. Step1, 2에서 해야할 일은 source node $s_1$ 이 $e_1$ 이라는 edge를 통해 target node $t$ 에 주는 영향력을 수식으로 나타내는 것이다. 이는 Multi-head Attention으로 구현되는데, 기존의 Vanilla Transformer를 사용하면 다른 source/target node, 여러 node type 모두 같은 feature distribution을 공유하게 되므로 이는 현재 상황에 적합한 세팅은 아니다.

Step1: Heterogenous Mutual Attention

이러한 단점을 보완하기 위해 Heterogenous Mutual Attention 메커니즘이 도입된다. 이 메커니즘은 Multi-head Attention의 핵심 구조는 그대로 따르지만 몇 가지 차이점이 있다. 먼저 target node 벡터와 source node 벡터는 각각 Query 벡터, Key 벡터로 매핑되는데 이 때 각각의 node type에 따라 projection weight parameter가 다르다. 즉 만약 node type이 10개 있다고 하면, Query 벡터를 만들기 위한 weight matrix는 기본적으로 10 종류가 있는 것이다. (후에 여기에 attention head 수를 곱해야 한다.)

여기가 끝이 아니다. edge type도 weight parameter를 구분한다. $W_{\phi(e)}^{ATT}$ 가 edge type에 dependent한 weight으로 Query 벡터와 Key 벡터의 유사도를 반영한다. 지금까지 설명한 것을 식으로 보자.

[Attention(s, e, t) = Softmax_{\forall s \in N(t)} ( \Vert_{i \in [1, h]} ATT {\text -} head^i(s, e, t) )]

[ATT {\text -} head^i(s, e, t) = (K^i(s) W_{\phi(e)}^{ATT} Q^i(t)^T)) \cdot \frac{\mu <\tau(s), \phi(e), \tau(t)>}{\sqrt{d}}]

2번째 식을 $h$ 개 만들고 이를 concat한 뒤 target별로 softmax 함수를 적용한 것이 최종 결과이다. 즉 2번째 식은 head 1개에 대한 결과물을 의미한다.

식의 좌측이 앞서 설명한 부분으로 아래와 같이 좀 더 세부적으로 표현할 수 있다.

[K^i(s) = K {\text -} Linear^i_{\tau(s)} (H^{l-1}[s])]

[Q^i(t) = Q {\text -} Linear^i_{\tau(t)} (H^{l-1}[t])]

위는 node type에 따라 weight를 구분하는 projection layer다. 이전 layer의 결과물을 받아 linear layer 하나를 통과시켜 Query/Key 벡터를 얻는다. 최종적으로 $h$ 개의 attention head를 얻기 때문에 Query/Key 벡터는 $\mathcal{R}^d \rightarrow \mathcal{R}^{\frac{d}{h}}$ 로 바뀐다. $W_{\phi(e)}^{ATT}$ 는 $\mathcal{R}^{\frac{d}{h}, \frac{d}{h}}$ 의 형상을 갖는다.

지금까지의 과정을 종합해보면, 이 Heterogenous Mutual Attention 메커니즘이 여러 종류의 semantic relation을 충분히 포착할 수 있을 구조를 갖고 있다는 느낌이 들기 시작한다. 그 효용성에 대해서는 검증해보아야겠지만 일단 장치는 마련해둔 셈이다.

2번째 식에서 우측을 보면 아래와 같은 수식이 있다.

[\frac{\mu <\tau(s), \phi(e), \tau(t)>}{\sqrt{d}}]

논문에서는 이 식을 prior tensor라고 지칭하고 있다. 생각해보면, 모든 node/edge type이 같은 영향력을 지니지는 않을 것이다. 즉 데이터 전반을 볼 때 특정 node/edge type이 더 강한 영향력을 지닐 수도 있는 것이다. 이를 반영하기 위해 만들어진 tensor라고 생각하면 된다. 이 tensor를 통해 attention에 대해 adaptive scaling을 수행한다.

코드를 잠시 보고 지나가겠다.

self.relation_pri = nn.Parameter(torch.ones(num_relations, self.n_heads))

논문 원본에는 모든 node/edge type에 따른 prior를 부여하였는데, 저자의 코드는 이를 좀 단순화하여 나타냈다. 만약 원본 코드를 사용할 계획이라면 상황에 따라 수정을 가할 수도 있을 것이다. 만약 수정을 원한다면 아래 부분에서 행렬 곱 연산을 수행한 후에 합 연산을 수행하는 형태로 바꿔줘야 한다.

res_att[idx] = (q_mat * k_mat).sum(dim=-1) * self.relation_pri[relation_type] / self.sqrt_dk

코드에 대한 자세한 리뷰는 추후에 업로드하도록 하겠다.

앞서 언급하였듯이 최종 단계에서의 softmax는 target node를 기준으로 이루어지기 때문에 현재와 같이 1번째 meta relation 만을 기준으로 연산을 수행한다면 각각의 head에 대해 softmax가 아닌 sigmoid 함수가 적용되게 될 것이다. 2번째 meta relation까지 한번에 계산했다면 2개의 target node에 대해 softmax 함수가 적용되어 결과물로 길이 $h$ 의 벡터가 2개 주어질 것이다.

이를 그림으로 나타내면 아래와 같다.

Step2: Heterogenous Message Passing

이전 섹션에서 주어진 edge type 하에서 source node와 target node 사이의 유사성에 대해 계산하였다면, 본 섹션에서는 이제 source node로부터 수집한 정보를 target node로 전달할 차례이다. 이 때 일반적인 honogenous graph network에서는 이러한 정보가 동일한 파라미터를 통해 업데이트되었겠지만, Heterogenous Message Passing 메커니즘에서는 source node type과 edge type에 따라 다른 파라미터를 지정하여 진행하게 된다.

[Message(s, e, t) = \Vert_{i \in [1, h]} MSG {\text -} head^i(s, e, t)]

[MSG {\text -} head^i(s, e, t) = M {\text -} Linear^i_{\tau(s)} (H^{l-1}[s]) W_{\phi(e)}^{MSG}]

Mutual Attention 과정을 보았기 때문에 특별히 어려울 것은 없다. 다만 위 수식에서의 M은 Transformer의 V 부분을 의미하고 실제 저자의 코드에서는 V-Linear라고 표기되어 있음에 유의하자.

Step3: Target-specific Aggregation

이전 2개 과정을 통해 attention score와 message를 수집/계산하였다. 지금부터는 이를 target node에 맞춰 통합하는 과정으로 이어진다.

[<\tau(s_1), \phi(e_1), \tau(t)>, <\tau(s_2), \phi(e_2), \tau(t)>]

위 meta relation 들에 대하여 attention score와 message를 모두 얻었다면 이 둘을 곱하여 updated vector를 얻을 차례이다.

[\tilde{H}^l [t] = \oplus_{\forall s \in N(t)} ( {\text Attention}(s, e, t) \cdot {\text Message} (s, e, t) )]

이 과정을 거치면 다른 feature distribution을 갖는 source node의 이웃들이 target node $t$ 로 정보를 통합하게 될 것이다. 이제 target node $t$ 의 updated vector를 맞는 type에 따라 다시 한 번 linear layer를 통과시킨다. 그리고 이전 layer의 output을 직접적으로 더해주어 residual connection 또한 추가해준다.

[H^l[t] = A {\text -}Linear_{\tau(t)} ( \sigma (\tilde{H}^l [t]) + H^{l-1}[t] )]

이와 같은 과정을 $L$ 번 반복해주면 바로 그 결과물이 target node의 contextualized representaion이 되는 것이고, 이를 통해 node classification이나 link prediction과 같은 downstream task에 활용하면 된다.

정리를 좀 해보면, HGT는 분명 meta relation을 활용하여 각 type에 맞는 weight matrix를 따로 설정하고 이를 자연스럽게 통합하고 있다. 다만 이렇게 별개의 weight matrix를 모두 만들 경우 분명 model이 무거워지는 것은 사실이다. 따라서 실제 적용 시에는 이러한 부분에 대해 유의해야 할 것이다.

3.2. Additional setting

앞서 효과적인 학습을 위해 3가지의 추가적인 장치가 구현되어 있다고 언급한 바 있다. 이제 이 부분에 대해 살펴볼 것이다.

1번째 장치: Relative Temporal Encoding

RTE는 graph dynamic을 다루기 위해 도입된 개념이다. 시간적 정보를 활용하기 위해 시간대 별로 분리된 graph를 구성하는 이전의 방법은 여러 time slot간의 구조적인 연결성을 잃어버리기 때문에 효과적인 방법으로 보기 어렵다. dynamic graph를 모델링하는 것의 핵심은 바로 모든 node/edge가 다른 timestamp에서도 서로 상호작용할 수 있게 만들어주는 것이다.

이러한 철학은 Transformer의 positional encoding을 변형하여 구현된다.

source node $s$ 의 timestamp는 $T(s)$ 이고 target node $t$ 의 timestamp는 $T(t)$ 이다. 이 둘 사이의 relative time gap은 $\Delta T(t, s) = T(t) - T(s)$ 로 표현할 수 있고, relative temporal encoding을 $RTE(\Delta T(t, s))$ 라고 표기한다.

학습 데이터셋이 모든 time gap을 커버하는 것은 아니기 때문에 RTE는 본 적 없는 시간에 대해서도 일반화할 수 있어야 한다. 이를 위해 논문에서는 sinusoid 함수를 basis로 놓고 학습 가능한 projection layer를 하나 더 둔다.

[Base(\Delta T(t, s), 2i) = sin (\Delta T(t, s) / 10000^{\frac{2i}{d}})]

[Base(\Delta T(t, s), 2i+1) = cos (\Delta T(t, s) / 10000^{\frac{2i+1}{d}})]

[RTE(\Delta T(t, s)) = T{\text -}Linear (Base(\Delta T(t, s)))]

최종적으로 target node $t$ 에 대한 temporal encoding은 source node $s$ 의 representation에 더해진다.

[\hat{H}^{l-1} [s] = H^{l-1}[s] + RTE(\Delta T(t, s))]

이 과정을 그림으로 나타내면 아래와 같다.

코드로 구현하면 아래와 같다.

class RelTemporalEncoding(nn.Module):
    # Implement the Temporal Encoding (Sinusoid) function.
    def __init__(self, n_hid, max_len=240):
        super(RelTemporalEncoding, self).__init__()
        position = torch.arange(0., max_len).unsqueeze(1)
        div_term = torch.exp(torch.arange(0, n_hid, 2) * -(math.log(10000.0) / n_hid))

        emb = nn.Embedding(max_len, n_hid)
        emb.weight.data[:, 0::2] = torch.sin(position * div_term) / math.sqrt(n_hid)
        emb.weight.data[:, 1::2] = torch.cos(position * div_term) / math.sqrt(n_hid)
        emb.requires_grad = False

        self.emb = emb
        self.lin = nn.Linear(n_hid, n_hid)
    def forward(self, x, t):
        return x + self.lin(self.emb(t))

edge_time이 주어지고, meta relation이 주어졌을 때 temporal encoding이 source node $s$ 의 representation에 더해지는 과정은 아래와 같이 구현된다.

rte = RelTemporalEncoding(n_hid=10)

source_node_vec = rte(source_node_vec, edge_time[idx])

2번째 장치: HGSampling

지금부터 설명할 2개의 방법론은 모두 scalibility를 향상시키기 위해 도입된 장치들이다.

작은 graph가 아니라면 full-batch GNN 학습은 현실적으로 힘든 경우가 많다. 그리고 속도와 효율을 중시하는 실제 서비스에 적용하기에는 부담스러운 측면도 있다. 이를 위해 sampling 방법이 많이 도입 되었는데, 이를 node-level로 추출할 수도 있고, grpah-level로 추출할 수도 있다. 이와 관련된 연구는 매우 많지만 node-level sampling을 적용한 알고리즘으로는 GraphSAGE, PinSAGE가 있고, IGMC, GraphSAINT는 graph-level sampling을 적용하였다.

그런데 앞서 소개한 방법들을 그대로 heterogenous graph에 적용할 경우, 만약 node type별 분포가 크게 다를 경우 상당히 불균형적이고 왜곡된 subgraph가 추출될 수 있다. 따라서 이를 위해 HGSampling이라는 방법이 제안된다.

HGSampling은 각 node/edge type에 속하는 수를 유사하게 맞춰주면서 정보 손실을 최소화하고 sample variance를 줄이기 위해 추출된 subgraph를 dense하게 유지할 수 있는 알고리즘이다.

아래 도식에서 HGSampling의 수행 과정을 살펴볼 수 있다. 기본적으로 각 node type $\tau{r}$ 에 대해 budget 딕셔너리 $B[\tau{r}]$ 를 만들어준다. 그리고 중요도 기반의 sampling을 사용하여 node type 별로 같은 수의 node를 추출해준다.

node $t$ 가 이미 추출되었다고 할 때, 이 node의 직접적인 이웃들을 모두 상응하는 budget에 추가해준다. 추가하는 방식은 아래와 같다.

그리고 이 이웃들에게는 node $t$ 의 normalized degree를 더해준다. 이 값은 추후에 sampling 확률을 계산하기 위해 사용된다. 이러한 normalization은 high-degree node에 의해 크게 좌지우지 되는 sampling 방식을 피하면서도, 이웃들에 대한 각 sampled node의 random walk 확률을 모으는 것과 같은 효과를 지닌다.

budget이 업데이트된 이후, 알고리즘1의 line9에서 각 budget 속에 있는 각 node $s$ 의 cumulative normalized degree를 계산한다. 이러한 sampling probability는 sampling variance를 감소시키는 효과를 지닌다.

이후 계산된 확률에 기반하여 type $\tau$ 의 $n$ 개의 node를 추출하고 이를 output node set에 추가하고, 이웃목록을 budget에 업데이트한다. 추출된 node는 budget에서 제거된다.

최종적으로 우리는 이렇게 sampled된 node에 기반하여 adjacency matrix를 다시 생성한다.

위와 같은 과정으로 생성한 subgraph는 node type별로 유사한 수의 node를 갖게 되고, sampling variance를 감소시킬 수 있을만큼 충분히 dense하다. 따라서 이를 활용하여 web-scale heterogenous graph를 효과적으로 학습할 수 있다.

그림으로 표현하면 아래와 같다.

3번째 장치: Inductive Timestamp Assignmant

지금까지 우리는 각 node $t$가 timestamp $T(t)$ 에 assign되었다고 가정했는데 실 세계의 heterogenous graph에서 많은 node들은 고정된 시간으로 묶여있지 않다. 따라서 그러한 node에게는 다른 timestamp 들을 할당해주어야 하는데, 이러한 node를 plain nodes라고 한다.

또한 명시적인 timestamp를 갖고 있는 node들이 있는데 이들을 event nodes라고 한다. 본 논문에서는 event node의 timestamp에 기반하여 plain node의 timestamp를 assign하는 inductive timestamp assignment 알고리즘을 제안한다. plain node는 event node로 부터 timestamp를 상속받게 된다.


4. Evaluation and Conclusion

Comment  Read more