• Swin Transformer
• Swin Transformer V2
• Video Swin Transformer

이 글에서는 Microsoft Research Asia에서 발표한 Swin Transformer 논문을 간략하게 정리한다.

Swin Transformer: Hierarchical Vision Transformer using Shifted Windows

논문 링크: Swin Transformer: Hierarchical Vision Transformer using Shifted Windows

Github: https://github.com/microsoft/Swin-Transformer

• 2021년 3월(Arxiv), ICCV 2021 best paper
• Microsoft Research Asia
• Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, Baining Guo

Computer Vision 분야에서 general-backbone으로 사용될 수 있는 새로운 Vision Transformer인 Shifted WINdow Transformer이다.

Abstract

Transformer는 원래 자연어를 처리하기 위한 것인데 이를 Vision 분야로 가져왔다. 이 과정에서 어려운 점은 이미지의 경우 visual entity의 크기(scale)와 해상도가 매우 다양하다는 문제가 있다는 것이다. 이를 위해 제안한 hierarchical Shifted WINdow 방식은, 기존 self-attention의 제곱에 비례하는 계산량을 선형 비례하게 줄이면서도 다양한 scale을 처리할 수 있는 접근법이다. 이로써 image classification, object detection, semantic segmentation 등 다양한 범위의 vision task에서 훌륭한 성과를 보였다.

1. Introduction

이미지 관련 분야는 CNN을 통해, NLP 관련 분야는 Transformer를 통해 발전해왔다. 이 논문에서는 Transformer를 vision 분야에 효율적으로 적용하는 방법을 연구한다(사실 이러한 시도 자체는 ViT에서 있었다). 기존의 Transformer와 ViT는 고정된 크기의 token만을 사용하기 때문에 고해상도, 다양한 크기의 entity를 갖는 이미지 분야에서는 적합하지 않다.

따라서 이 논문에서는 Shifted WINdow 기법을 사용하는 Swin-Transformer를 제안한다. 위 그림 1과 갈이, 이는

• 작은 크기의 patch 안에서만 self-attention을 수행하고
• layer를 통과하면서 인접한 patch들을 점점 합치면서 계산한다.

이러한 구조 덕분에 FPN이나 U-Net처럼 계층적인 정보를 활용한 여러 테크닉도 사용할 수 있다. 가장 작은 window 안의 patch 수는 고정되어 있기 때문에 이미지 크기에 선형 비례하는 계산량만 필요로 한다. 이러한 이점 덕에 여러 vision task에서 backbone net으로 사용할 수 있다.

또 하나의 핵심 구조는 다음과 같다. 위와 같이 window를 나누어서 계산을 수행하면 각 window의 경계 근처 pixel들은 인접해 있음에도 self-attention 계산이 수행되지 않는데, 이를 위해 window 크기의 절반만큼 shift하여 비슷한 계산을 수행한다.

여기서 이러한 shifted window 방식은 기존의 sliding window 방식에 비해 더 효율적이다, 그 이유는

• self-attention 계산을 수행할 때, sliding window 방식에서는 각각 다른 query pixel에 대해 다른 key sets에 대해 계산을 수행해야 해서 일반적인 하드웨어에서 low latency 문제를 경험하게 된다.
• 이와 달리 shifted window 방식은 window 내의 모든 query patch는 같은 key set을 공유하기 때문에 하드웨어 상에서 memory access 면에서 latency가 더 적기 때문이다.

결과적으로, Swin Transformer는 Image Classification, Object Detection, Semantic Segmentation에서 ViT, DeiT, RexNe(X)t를 능가하였다.

2. Related Work

CNN and variants: CNN, VGG, GoogleNet, ResNet, DenseNet, HRNet, EfficientNet 등 여러 논문이 수 년에 걸쳐서 빠르게 발전해왔다. 위의 논문들에 대해서는 여기를 참고하자.

Self-attention based backbone architectures: ResNet 기반 conv layer를 self-attention layer로 대체하는 시도가 있었으나 sliding window 방식으로 인핸 memory access 문제가 있었다. 전술했듯이 이 논문에서는 shifted window 방식을 사용하여 이를 해결했다.

Self-attention/Transformers to complement CNNs: CNN을 self-attention이나 Transformer로 보강하는 연구도 있었다. 최근에는 Transformer를 object detection이나 segmentation에 사용하기도 하였다.

Transformer based vision backbones: 말 그대로 Transformer를 vision 분야에다 적용시켜 backbone으로도 사용할 수 있는 건데 ViT와 DeiT 및 그 후속 논문들이 대표적이다.

3. Method

3.1. Overall Architecture

Swin Transformer는 4가지 버전이 있는데(Tiny, Small, Base, Large) 아래는 T 버전의 전체 구조이다.

• 맨 앞에 Patch partition 과정이 있다. 여기서는 먼저 ViT와 같은 patch 분리 모듈을 통해 입력 RGB 이미지를 겹치지 않는 patch들로 나눈다.
  • 각 patch는 하나의 “token”과 같으며 그 feature는 raw pixel RGB 값을 이어붙인 것이다.
  • 이 논문에서는 각 patch의 크기는 $4 \times 4$이며, 따라서 feature는 $4 \times 4 \times 3 = 48$이 된다.
• Stage 1:
  • 이후 Linear Layer를 통해 $H/4 \times W/4 \times 48$ 텐서를 $H/4 \times W/4 \times C$ 텐서로 변환한다. 생긴 걸 보면 $1 \times 1$ conv 같지만 Linear Layer가 맞다.
  • Swin Transformer Block이 이제 등장한다. 얘는 위 그림의 (b)에서 볼 수 있는데, 일반적인 MSA(Multi-head Self Attention) 대신 W-MSA(Window MSA)와 SW-MSA(Shifted Window MSA)라는 것을 사용한다. 이건 다음 섹션에서 설명한다. Activation function으로는 GELU를 사용한다.
• Stage 2~4에서는 Patch Merging이 있다.
  • 이건 맨 처음 $4 \times 4$ 크기의 작은 patch들을 점점 합쳐가면서 더 넓은 부분을 한번에 보려는 과정이다.
  • 먼저 인접한 $2 \times 2$개의 patch를 concat한다. 그러면 채널 수가 4배로 된다.
  • 이를 linear layer를 써서 2C로 맞춘다. 따라서 Patch Merging을 통과하면 해상도는 $2 \times 2$배 줄고 채널은 2배로 늘어난다.
• 이렇게 hierarchical한 구조로 각 단계마다 representation을 갖기 때문에 다양한 scale의 entity를 다루어야 하는 image 분야에서 괜찮은 성능을 낼 수 있는 것이다. 어떻게 보면 생긴 게 VGGNet이나 ResNet과 비슷하므로, 여러 vision task에서 이 Swin Transformer를 backbone으로 사용할 수 있다.
• 참고로, (b)는 거의 비슷한 Swin Transformer를 2개 붙여 놓은 것이기 때문에, (a) 부분에서 $\times2$, $\times6$이라 되어 있는 부분은 각각 (b)를 1번, 3번 붙여 놓은 것이다.

3.2. Shifted Window based SelfAttention

위에서도 말했듯이 기존 Self-Attention은 모든 부분의 쌍에 대해 연산해야 하므로 계산량이 제곱에 비례한다. 이를 해결하고자 한다.

Self-attention in non-overlapped windows

사실 같은 내용이다.

• 가장 작은 patch는 $4 \times 4$ pixel로 구성되어 있다.
• Window는 $M \times M$개의 patch로 구성된다. 이 논문에서는 $M=7$로 고정이다.
• 이미지는 이 Window가 $h \times w$개 있다. 이미지의 해상도는 $4Mh \times 4Mw$임을 알 수 있다.

즉 이미지 해상도가 $224 \times 224$라면, 첫번째 layer에서 patch의 크기는 $4 \times 4$이고, 이 patch를 $7 \times 7$개 모은 Window가 $h \times w = 8 \times 8$개가 존재한다.

이렇게 하면 그냥 MSA에 비해 많이 줄어든다.

• $\Omega(\text{MSA})$ : $4hwC^2 + 2(hw)^2C$
• $\Omega(\text{W-MSA})$ : $4hwC^2 + 2M^2hwC$

$M=7$으로 고정이므로 이미지 크기에 선형으로 비례한다.

Shifted window partitioning in successive blocks

위의 Window 방식이 좋기는 한데, Window 경계에 있는 patch들은 서로 인접해 있음에도 attention 계산을 수행할 수 없게 된다. 이를 위해 Window를 $\lfloor M/2 \rfloor$만큼 cyclic하게 shift한 다음에 비슷한 계산을 수행한다.

즉, Swin Transformer block은 다음과 같은 과정을 따른다. Layer Norm은 생략하고 설명하면(그림 3b와 같은 부분이다),

• 이전 layer의 입력이 들어오면
• W-MSA를 수행한다.
• MLP에 통과시킨다.
• SW-MSA를 수행한다: 이는 Cyclic Shift를 시키고 W-MSA 계산을 수행하는 것과 거의 같다. 그 다음엔 Cyclic shift 했던 것을 다시 되돌린다(Reverse cyclic shift).
• MLP에 통과시킨다.
• 그러면 이제 Swin Transformer block의 output이 나온다. 이는 다음 layer로 전달될 것이다.

물론, residual connection도 있는데 이는 그림을 보면 쉽게 이해할 수 있다.

Efficient batch computation for shifted configuration

Window를 shift하고 나면 우측과 하단 경계에 있는 Window들은 $M \times M$보다 크기가 작아진다.

SW-MSA 과정에서 Cyclic shift를 하면 전체 이미지의 반대쪽 경계에 있던 부분(A, B, C로 표시)끼리 연산을 하게 되는 것을 막기 위해 해당 부분을 mask 처리한다.

참고: zero padding으로도 할 수는 있는데 연산량이 증가하므로 이 논문에서는 쓰지 않았다.

Relative position bias

기존 Transformer에서는 Sinusodal 함수를 사용해서 positional encoding을 추가했었다.

이것보다는 상대좌표의 차이를 넣어주는 것이 성능 상으로 더 좋다고 한다. 그리고 아래 식과 같이 더해주는 부분도 Attention 연산 중으로 옮겨온 것을 알 수 있다.

[\text{Attention}(Q, K, V) = \text{SoftMax}(QK^T / \sqrt{d} + B)V]

$B \in \mathbb{R}^{(2M-1) \times (2M-1)}$가 relative position bias이다.

3.3. Architecture Variants

Swin Transformer도 ViT, DeiT와 비슷하게 Base model이 있다. Tiny는 4배 작고, Small은 절반, L은 2배 크다.

• Swin-T: $C = 96$, layer numbers = {2, 2, 6, 2}. ResNet-50(DeiT-S)와 크기가 비슷하다.
• Swin-S: $C = 96$, layer numbers = {2, 2, 18, 2}. ResNet-101과 크기가 비슷하다.
• Swin-B: $C = 128$, layer numbers = {2, 2, 18, 2}
• Swin-L: $C = 192$, layer numbers = {2, 2, 18, 2}

$C$는 채널 수이고, layer 수는 그림 3에서 Swin Transformer Block이 $\times 2, \times 6$만큼 있있던 것을 생각하면 된다.

4. Experiments

• Image Classification으로는 ImageNet
• Object Detection으로는 COCO
• Sementic Segmentation으로는 ADE20K

데이터셋을 사용하였다.

4.1. Image Classification on ImageNet1K

Regular ImageNet-1K으로 학습한 model들의 비교가 (a)이다. Swin-B는 RegNet이나 DeiT에 비해서는 확실히 모델 크기과 계산량 대비 성능이 좋다. EfficientNet과는 비등한 수준이다.

ImageNet-22K로 학습한 모델끼리 비교한 결과는 (b)인데 Swin이 크기와 계산량 대비 확실히 더 성능이 좋다.

4.2. Object Detection on COCO

계산량 대비 성능이 Image Classification 때보다 더 크게 앞선다.

4.3. Semantic Segmentation on ADE20K

다른 Task(Object Detection, Semantic Segmentation)의 backbone으로 사용했을 때의 성능은 거의 state-of-the-art이다.

4.4. Ablation Study

• Shifted windows 기법을 사용한 경우에 모든 task에서 성능이 더 높게 나온다.
• Relative position bias의 효과를 분석하였는데, absolut position을 단독으로 쓰거나 같이 쓰는 것보다 relative position bias만 쓰는 것이 제일 좋다고 한다.

V100 GPU로 계산하면 이 정도의 시간이 걸린다. 꽤 빠르다고 알려진 Performer architecture보다 살짝 더 빠르다.

5. Conclusion

• Swin Transformer는 기존 Transformer 대비 계산량을 줄이면서도 다양한 scale의 이미지를 처리할 수 있다.
• Image Classification, Object Detection, Semantic Segmentation 등 여러 Vision task의 backbone으로 쓸 수 있다.
• Shifted Window 방식은 충분히 효율적이다.

이 글에서는 Google Research에서 발표한 VideoBERT(와 CBT) 논문을 간략하게 정리한다.

VideoBERT: A Joint Model for Video and Language Representation Learning

논문 링크: VideoBERT: A Joint Model for Video and Language Representation Learning

Github: maybe, https://github.com/ammesatyajit/VideoBERT

• 2019년 9월(Arxiv), ICCV 2019
• Google Research
• Chen Sun, Austin Myers, Carl Vondrick, Kevin Murphy, and Cordelia Schmid

Video에다가 BERT를 적용한 논문이다. Visual info는 Video의 frame를 1.5초마다 하나씩 뽑아 S3D embedding을 만들고, Audio는 ASR을 사용하여 텍스트로 변환하여 사용했다.

VL-BERT나 ViLBERT와는 달리 detection model이 없으므로, 그냥 S3D embedding을 갖고 clustering을 수행한다.그러면 어떤 frame이 어느 cluster에 속하는지 알기 때문에 대략적인 classification을 수행할 수 있게 된다.

학습은 3가지 task를 사용한다.

1. Linguistic-visual alignment: 텍스트가 video frame의 장면과 일치하는지를 판별한다.
2. Masked Language Modeling(MLM): BERT의 것과 같다.
3. Masked Frame Modeling(MFM): MLM과 비슷한데, word token을 복구하는 대신 masked frame의 cluster class를 예측한다.

Downstream task로

• Recipe Illustration(입력 문장이 들어오면 그에 맞는 video token을 생성한다)
• Future frame prediction(다음 frame 예측)
• Zero-shot action classification(비디오와 How to <mask> the <mask>와 갈은 템플릿 문장을 주면 문장을 완성하면서 어떤 action을 수행하는지를 맞추는 task)
• Video captioning(Video에 맞는 caption 생성)

등을 수행하여 좋은 결과를 얻었다. 일부 결과를 아래에서 볼 수 있다.

CBT(Learning Video Representations using Contrastive Bidirectional Transformer)

논문 링크: Learning Video Representations using Contrastive Bidirectional Transformer

• 2019년 9월
• Google Research
• Chen Sun1 Fabien Baradel1;2 Kevin Murphy1 Cordelia Schmid1

(거의) 갈은 저자들이 위의 VideoBERT 논문에서 end-to-end 학습을 막는 Clustering을 대체하는 방법을 제안한 논문이다.

텍스트에서 loss를 구할 때는 BERT에서와 같이 cross-entropy를 모든 단어에 대해서 확률을 계산하여 얻는다. 식으로 나타내면 다음과 같다.

그러나 Video에서는 모든 video에 대해 계산을 할 수가 없다(Video frame의 차원이 너무 높음). 따라서 모든 경우에 대해 하는 대신 negative sampling을 통해 일부만 뽑아서 계산을 수행하게 된다. 식으로 나타내면 다음과 같다.

위와 같이 NCE loss를 사용하여 Clustering을 없애면 end-to-end 학습이 가능하게 된다.

요약하면,

• frame $\mathbf{x} = \lbrace x_1, …, x_m \rbrace $과 ASR token $\mathbf{y} = \lbrace y_1, …, y_n \rbrace $이 주어지면 모델은 그 correspondence/alignment를 학습한다.
• $\mathbf{x, y}$를 concat하여 cross-modal Transformer(VideoBERT 등)에 집어넣으면 embedding sequence $\mathbf{h} = \lbrace h_1, …, h_{m+n} \rbrace$를 얻을 수 있다.
• 전체 모델은 BERT, CBT, Cross-modal loss를 가중합하여 loss function으로 사용한다.

결과는 대략 아래와 같다.

이 글에서는 VL-BERT와 ViLBERT 논문을 간략하게 정리한다.

VL-BERT: Pre-training of Generic Visual-Linguistic Representations

논문 링크: VL-BERT: Pre-training of Generic Visual-Linguistic Representations

Github: https://github.com/jackroos/VL-BERT

• 2020년 2월(Arxiv), ICLR 2020
• University of Science and Technology of China, Microsoft Research Asia
• Weijie Su, Xizhou Zhu, Yue Cao, Bin Li, Lewei Lu, Furu Wei, Jifeng Dai

Visual-Language BERT로, Visual info와 Language info를 BERT에다가 넣는 방법론을 제시한다.

• 학습 샘플은 image + 이미지를 설명하는 sentence 쌍으로 이루어진다.
• VQA task에 대해서는 2개의 문장(question, answer)이다.

BERT와 굉장히 유사하다. Langauge 쪽은 거의 똑갈다고 보면 된다.

왼쪽의 파란색 부분을 텍스트 부분, 중간~오른쪽의 붉은색 부분을 이미지 부분이라 하자.

다른 점은

• Visual Feature Embedding이 새로 추가가 되었다.
  • 텍스트 부분에서는 이미지 전체를 visual feature embedding으로 만들어 넣는다.
  • 이미지 부분에서는 detect된 object들을 하나하나 embedding으로 만들어 넣는다.
• BERT의 2번째 문장 대신 [IMG] token을 사용한다.
• 마지막에 [END] token이 추가되었다.
• Segment Embedding은 텍스트의 경우 A, 이미지의 경우 C로 넣는다.
• 이미지 부분의 Sequence Position Embedding은 딱히 순서가 없으므로 똑같은 값을 넣는다. (위 예시에서는 image region은 7의 값을 갖는다)

Pre-training task는 MLM과 비슷한 task를 진행하는데,

• 텍스트에 대해서는 MLM과 같다. 단, MLM with Visual clues라고 이름 붙였는데, 텍스트만 있는 게 아니라 이미지 정보를 같이 사용하여 예측하기 때문이다.
• Object detect를 할 때 Faster-RCNN으로 뽑아내는데, 이 때 object class가 나온다. 이를 Ground Truth로 사용하여, 특정 object 부분이 가려졌을 때, 이미지의 나머지 부분 + 텍스트 정보를 갖고 이 class를 예측하는 task를 수행할 수 있다. 이는 Masked RoI Classification with Linguistic Clues라 부른다.

VQA에 대해서 학습할 때도 거의 갈은데, Question에는 Mask를 씌우지 않고 대신 Answer에만 masking을 수행한다. 그러면 주어진 Question에 대해 답을 맞추는 것과 같아진다.

위 그림에서는 VQA 말고도 다른 downstream task에서 input/output의 형태를 나타내고 있다.

VCR, VQA, Reffering Expression Comprehension) downstream task에 대한 결과는 아래와 같다.

ViLBERT: Pretraining Task-Agnostic Visiolinguistic Representations for Vision-and-Language Tasks

논문 링크: ViLBERT: Pretraining Task-Agnostic Visiolinguistic Representations for Vision-and-Language Tasks

Github: https://github.com/facebookresearch/vilbert-multi-task

• 2019년 8월(Arxiv), NIPS 2020
• Georgia Institute of Technology, Facebook AI Research, Oregon State University
• Jiasen Lu, Dhruv Batra, Devi Parikh, Stefan Lee

위의 VL-BERT와 거의 같은 방식인데(이름도 비슷하다), Cross-modal Attention을 썼다는 점이 가장 중요한 차이이다.

참고로 TRM은 Transformer이다.

TRM은 원래의 것과 같고, Co-TRM이 Co-attention Transformer이다. 아래 그림에서 그 차이를 볼 수 있다.

Co-TRM을 보면 왼쪽의 Co-TRM에서는 Q를 Visual 쪽에서, K와 V는 Language 쪽에서 받는다.
반대로, 오른쪽 Co-TRM에서는 Q를 Language 쪽에서, K와 V는 Visual 쪽에서 받는다.

Training task로는 BERT의 MLM과 NSP와 거의 비슷하다.

• Masked multi-modal learning(MLM과 비슷함): image region에 대해 semantic classes의 distribution을 예측한다. Faster-RCNN의 예측 결과가 GT로 사용된다(이 부분은 VL-BERT의 것과 같다).
  • 텍스트 부분은 MLM과 같다.
• Multi-modal alignment prediction(NSP와 비슷함): 모델은 (image, text) 쌍을 입력으로 받아 여러 image patch를 추출한다. 텍스트의 각 부분과 이미지의 각 부분이 연관이 있는지(aligned / not aligned)를 예측한다. 이 task가 상당히 강력하다고 한다.

VQA, VCR, Grounding Referring Expressions, Caption-Based Image Retrieval, ‘Zero-shot’ Caption-Based Image Retrieval 등에 대해 실험을 진행하였고 결과는 아래와 같다. 비교한 모든 부분에서 성능이 제일 좋다고 한다.

이번 글에서는 BERT 구조를 차용하여 추천 알고리즘을 구성해본 Bert4Rec이란 논문에 대해 다뤄보겠습니다. 논문 원본은 이 곳에서 확인할 수 있습니다. 본 글에서는 핵심적인 부분에 대해서만 살펴보겠습니다.

Bert4Rec: Sequential Recommendation with Bidirectional Encoder Representations from Transformer 설명

1. Background

RNN을 필두로 한 left-to-right unidirectional model은 user behavior sequence를 파악하기에 충분하지 않습니다. 왜냐하면 user의 historical interaction에서 일어난 item 선택 과정에 대해 살펴보면, 여러 이유로 인해 꼭 그 순서 자체가 중요하다고 말할 수 없는 경우가 자주 발생하기 때문입니다. 예를 들어 어떤 user가 토너와 화장솜을 사고 싶다고 할 때 토너를 먼저 구매할 수도 있고, 화장솜을 먼저 구매할 수도 있습니다. 사실 어떤 것이 먼저 오냐는 관점에 따라 크게 중요하지 않은 사실이 될 가능성이 높습니다.

따라서 논문에서는 sequence representations learning을 위해 두 방향 모두에서 context를 통합해야 한다고 이야기합니다. 우리는 이미 BERT 논문을 통해 이러한 방법이 특히 언어 모델에서 매우 잘 작동한다는 사실을 알고 있습니다.

논문 2장에 나온 Related Work에 관해서는 직접 확인하길 바랍니다. 이전에 다룬 내용들이 많아 본 글에서는 생략합니다.

2. Architecture

$u, v$ 를 각각 user, item이라고 할 때 $S_u = [v_1^u, …, v_t^u, …, v_{n_u}^u]$ 는 user $u \in \mathcal{U}$ 가 상호작용한 item 목록, 즉 interaction sequence입니다. 이 때 $v_t^u \in \mathcal{V}$ 는 user $u$ 가 $t$ step에서 상호작용한 item이고 $n_u$ 는 user $u$ 의 interaction sequence의 총 길이입니다.

따라서 user $u$ 가 $n_u+1$ time에서 특정 item $v$ 를 선택할 확률은 아래와 같이 표현할 수 있습니다.

아래 그림은 Bert4Rec의 전체 구조와 비교 대상인 RNN의 구조를 도식으로 나타내고 있습니다.

Bert4Rec의 핵심은 stacked된 $L$ 개의 bidirectional Transformer layer입니다. 병렬적으로 이전 layer에 존재하는 모든 position에 있는 정보들을 상호 교환하여 모든 position의 representation을 수정함으로써 학습을 진행합니다. self-attention 메커니즘을 통해 위치/거리 제약 없이 직접적으로 dependency를 포착할 수 있습니다. 이러한 메커니즘은 일종의 global receptive field로 귀결됩니다.

Transformer layer에 대해서는 몇 가지 포인트만 짚고 넘어가겠습니다. 자세한 내용은 원 논문을 참조하시길 바랍니다.

Transformer layer는 multi-head self-attention과 position-wise feed-forward network로 구성됩니다. 후자는 attention sub-layer의 결과물에 대해 적용되는데 이를 통해 여러 dimension 사이에 존재하는 상호작용을 포착하고 비선형성을 강화해줍니다. 본 논문에서는 feed-forward network의 활성화함수로 GELU를 사용하였으니 참고하시길 바랍니다.

이렇게 여러 Transformer layer를 쌓으면 분명 네트워크가 상당히 깊어지기 때문에 residual connection은 필수적으로 들어가게 됩니다. 이 과정을 요약하면 아래와 같습니다.

[\forall l \in [1, …, L]]

[H^l = Trm(H^{l-1}) = LN(A^{l-1} + Dropout(PFFN(A^{l-1})))]

[A^{l-1} = LN(H^{l-1} + Dropout(MH(H^{l-1})))]

Embedding layer에서는 2가지를 기억하면 됩니다. 일단 positional embedding을 할 때 기존의 transformer와 달리 학습 가능한 방법을 사용했다는 것입니다.

[h_i^0 = v_i + p_i, p_i \in P, P \in \mathbb{R}^{N, d}]

그리고 만약 길이가 $N$ 을 넘는 sequence가 있다면 마지막 $N$ 개에 대해서만 학습/추론을 진행하였습니다.

논문에 명시된 것은 아니지만, 1가지 덧붙이자면 논문 원본의 경우 이렇게 $N$ 개의 item을 산정하고 학습을 진행하기 때문에 inductive inference는 불가능한 상황입니다. 따라서 새롭게 item이 자주 들어오고 나오는 상황에서는 다른 학습 환경이 필요할 것으로 판단됩니다.

$L$ 개의 layer를 통과하고 나면 드디어 최종 결과물을 얻을 수 있게 됩니다.

[P(v) = softmax(GELU(h_t^L W^P + b^P)E^T + b^O)]

3. Model Learning

학습은 Masked Language Model라고도 알려진 Cloze task를 sequential recommendation에 적용함으로써 진행됩니다. 각 학습 단계에서 input sequence의 모든 item 중 $p$ %를 무작위로 masking하고 주변 context를 통해 masked item의 original ID를 추론하는 것입니다.

이제 각 masked된 input $\grave{S_u}$ 를 masked target의 negative log-likelihood로 정의할 수 있습니다.

[\mathcal{L} = \frac{1}{\vert S_u^m \vert} \Sigma_{v_m \in S_u^m} -log P(v_m = v_m^* \vert \grave{S_u})]

이 때 $\grave{S_u}$ 는 user behavior history의 masked version이고, $v_m^*$ 는 masked item $v_m$ 의 true item입니다.

이러한 방식으로 학습 데이터를 구성하게 되면 사실 Bert4Rec은 만약 무작위로 $k$ 개의 item을 masking한다고 했을 때 $\binom{n}{k}$ 개의 sample을 얻을 수 있으므로 더욱 방대하고 다양한 데이터셋을 얻을 수 있을 것입니다.

학습과 달리 테스트 시에는 mask라고 하는 special token을 user behavior sequence의 맨 끝에 놓고 이 token의 final hidden representation에 기반하여 next item을 예측하도록 설정하였습니다.

4. Experiments and Conclusion

학습 데이터는 아래와 같습니다.

비교 대상 알고리즘, 평가 환경 세팅 등 자세한 내용은 논문 본문을 참조하시길 바랍니다.

논문 후반부에는 attention head에 대한 시각화 자료가 존재하며 hidden vector 차원 및 sequence 길이에 따른 성능 변화에 대한 연구도 포함되어 있어 인사이트를 얻기 좋습니다.

Bert4Rec은 NLP에서 괄목할 만한 성과를 거둔 BERT 구조를 추천 시스템에 적용한 알고리즘입니다. 전체적으로 알고리즘의 component에 대한 설명과 실험 결과에 대해 기술한 부분이 매우 합리적이고 실제 현업에서 적용하기에도 좋은 아이템이라고 판단됩니다. 다만 역시 sequence 형태의 데이터에 기반하였다보니 item 간의 상호작용이 꽤 분명한 task에서 잘 작동할 것으로 예상됩니다.

이번 글에서는 Heterogenous Network에서 node representation을 학습하는 metapath2vec이란 논문에 대해 다뤄보겠습니다. 논문 원본은 이 곳에서 확인할 수 있습니다. 본 글에서는 핵심적인 부분에 대해서만 살펴보겠습니다.

그리고 관련하여 학습/분석 코드는 이 곳에 작성해두었으니 참고하셔도 좋을 것 같습니다.

metapath2vec: Scalable Representation Learning for Heterogeneous Networks 설명

1. Introduction

word2vec 기반의 network representation learning framework로는 DeepWalk, LINE, node2vec 등이 있고, 이들은 raw network로 부터 유용하고 의미있는 잠재적 feature를 자동적으로 발견해내는 역할을 수행합니다. 그러나 이들은 모두 homegenous network 기반의 알고리즘으로 여러 node/edge type이 존재하는 heterogenous network에서는 적용하기 어렵습니다.

본 논문은 heterogenous network에서 적용할 수 있는 meta-path-guided random walk strategy를 제시하고 있으며 이 방법론은 아래와 같은 특징을 갖습니다.

• 여러 다른 type의 node/relation에서 구조적이고 의미론적인 상관관계를 포착
• 복수의 node type 맥락 속에서 skip-gram 기반으로 network probability를 최대화
• 효과적이고 효율적인 heterogenous negative sampling 기법 적용
• similarity search, node classification, clustering 등에 적용 가능

논문에서는 metapath2vec과 이를 수정한 형태의 metapath2vec++를 제안하고 있습니다. 모든 node type에 대해서 같은 space에서 embedding을 생성하던 기존 방법과 달리 후자의 경우 각 node type 마다 별도의 space에서 embedding을 생성합니다.

2. Metapath2vec framework

hetegenous network는 $G=(V, E, T)$ 라고 하는 그래프로 정의됩니다. 이 때 여러 node/edge type을 표현하기 위한 mapping function이 존재합니다.

[\phi(v): V \rightarrow T_v]

[\varphi(e): E \rightarrow T_E]

위에서부터 각각 node type, edge type을 결정합니다. 물론 $\vert T_v \vert + \vert T_E \vert > 2 $ 여야 할 것입니다. 만약 $=2$ 라면 homogenous network가 되겠지요.

metapath2vec의 embedding은 homegenous skip-gram model을 수정, 발전시킨 형태입니다. node $v$ 가 주어졌을 때, $N_t(v), t \in T_V$ 라는 heterogenous context를 갖는 확률을 최대화하는 node representation을 학습하는 것이 이 알고리즘의 목표입니다.

skip-gram 모델의 아이디어와 마찬가지로 중심 node가 있을 때 주변 node의 특성을 학습한다는 설정은 동일하지만, 이 때 적절한 node type에 따라 학습해야 하는 것입니다.

[\underset{\theta}{argmax} \Sigma_{v \in V} \Sigma_{t \in T_v} \Sigma_{c_t \in N_t(v)} log p(c_t \vert v; \theta)]

$p$ 함수는 softmax 함수이고, $N_t(v)$ 는 node type $t$ 을 갖는 $v$ 의 이웃을 의미합니다. $X_v$ 는 $\mathbf{X}$ 의 $v$ 번째 row로 node $v$ 의 embedding vector를 의미합니다. 좀 더 자세한 설명은 논문의 3페이지를 참고하길 바랍니다.

학습의 효율성을 증대하기 위해 negative sampling 기법이 적용되었습니다. metapath2vec은 다만 node type과 상관없이 negative sample을 추출하며, metapath2vec++은 이와 달리 node type specific하게 샘플링을 진행합니다.

meta-path scheme $\mathcal{P}$ 는 아래와 같이 정의할 수 있습니다.

[V_1 \xrightarrow{R_1} V_2 \xrightarrow{R_2} … V_t \xrightarrow{R_t} V_{t+1} … \xrightarrow{R_{l-1}} V_l]

위 그림에서 예시를 들자면 APVPA는 2명의 작가가 어떤 paper를 냈고 이들이 같은 venue에서 accept되었다는 것을 의미합니다. 이러한 meta-path는 사실 metapath2vec에서는 domain 지식을 통해 사전에 설정되어야 합니다. 이는 많은 경우에 단점이 될 수 있는데, 이렇게 사전에 meta-path를 설정하기 어려운 경우가 많고, 어떤 path가 유의미한지 인간이 판단하기 어려울 때가 많기 때문입니다. 참고로 meta-path를 굳이 사전에 설정하지 않아도 자동적으로 찾는 기법을 고안한 논문으로는 Graph Transformer Networks가 있습니다.

metapath2vec에서 step $i$ 에서의 transition probability는 아래와 같이 정의합니다.

앞서 설명하였다시피 metapath2vec은 softmax 함수에서 node type 정보를 무시합니다. 이를 수정한 버전이 metapath2vec++입니다. 이 방법에서 softmax 함수는 context $c_t$ 의 node type에 따라 normalized됩니다. 이렇게 함으로써 skip-graph 모델의 output layer에서 각 type에 맞는 multinomial distribution을 정의할 수 있게 되는 것입니다.

목적함수는 아래와 같습니다.

알고리즘의 pseudo code는 아래와 같습니다.

3. Experiments & Conclusion

실험을 위해 2가지 데이터셋이 사용되었습니다. 자세한 사항은 논문을 참조하시길 바랍니다. 두 데이터 모두 author, paper, venue의 관계를 탐색합니다.

실험에서 주목할만한 결과만 간단히 기록하겠습니다.

• Multiclass 분류 문제에서는 Macro F-1, Micro F-1 score를 통해 평가가 진행되었습니다. (이 metric은 이 곳에서 설명을 확인할 수 있습니다.) 대체적으로 metapath2vec 계열의 성능이 우수하였는데 특히 적은 데이터를 사용한 구간(전체 데이터의 20% 이하를 사용)에서의 성능이 돋보였습니다.

• node별 walk 수, walk length, embedding dim, neighborhood size라는 4개의 parameter에 대해서 sensitivity test를 해보았는데, 값을 더 늘린다고 성능이 향상되지는 않았습니다. 이는 곧 적당히 효율적인 size로 충분한 효과를 발휘할 수 있음을 증명합니다.

• Normalized Mutual Information을 metric으로 하여 node clustering 성능도 측정하였는데, metapath2vec 계열의 성능이 더욱 우수하였습니다.

• 다른 알고리즘과 달리 metapath2vec++은 정확히 node type을 구분하면서도 실제 관련이 높은 node 사이의 거리를 가깝게 만드는데 성공한 것으로 보입니다.

글 서두에서도 밝혔듯이 metapath2vec과 metapath2vec++은 heterogenous graph에서 구조적인 node representation learning을 가능하게 한 효과적인 방법론입니다. 핵심적인 아이디어가 돋보인 논문이고 그렇기 때문에 추후에 진행된 많은 연구에서 언급되고 있는 것으로 보입니다.

몇 가지 한계점도 있습니다. 일단 large intermediate output data가 존재할 때 학습하는 것이 쉽지 않습니다. 그리고 meta-path를 사전에 설정하는 해야 하는 것도 때때로 문제가 됩니다.