A Normalized Gaussian Wasserstein Distance for Tiny Object Detection
CIoU, DIoU, GIoU와 같이 단순히 IoU를 사용하는 방법의 문제점을 제시하며 새로운 방법론을 제시하는 논문이다.
이 때, 기존 CIoU, DIoU등은 BBox가 아예 겹치지 않았을 때 거리를 고려하지않고 완전 터무니없는 후보군과 나름대로 가깝게 추론한 후보 BBox를 모두 0으로 똑같이 취급하는 문제점을 꼽았다면, 본 논문에서는 Tiny Object(소형 객체)탐지에서 발생하는 문제점을 꼽고, BBox의 크기에 의존성이 없도록 두 BoundBox간의 Wasserstein Distance를 구하고 이를 Normalize하여 Metric 형식으로 사용할 수 있도록하는 Normalized Gaussian Wasserstein Distance를 제안한다.
Abstract
Object Detection 분야에서 Tiny Object를 탐지하는 것은 굉장히 까다로운 문제이다. 그 근본적인 원인은 Tiny Object는 포함된 Pixel 수 자체도 매우 적기 때문이다.
저자들은 꽤나 높은 정확도를 가진 SOTA 모델들도 Tiny Object에 대해서는 만족스럽지 못한 결과물을 나타내는 것에 문제 의식을 가졌다.
저자들은 이러한 현상의 원인이, Intersection over Union(IoU) 기반 Metric이 Tiny Object에서는 위치 정보의 사소한 변화에도 너무 Sensitive하게 변화하는 특성 때문이라고 생각하였다.
- Ex) 거대한 Bounding Box에서는 Ground Truth와 Predicted Box가 1Pixel 정도 차이난다고 하더라도, 높은 IoU를 얻을 수 있지만, Bounding Box가 워낙 작아서 넓이가 불과 몇 픽셀밖에 안되는 Tiny Object에서는 1Pixel이라도 Ground Truth와 차이가 발생하게 되면 IoU가 매우 크게 감소하여, Threshold 값을 결국 넘기지 못하는 상황이 발생
이를 보완하기 위해서, 저자들은 Wasserstein Distance를 활용한 새로운 Evaluation Metric을 제안한다.
본 논문에서 제안하는 방법은 첫째로, Bounding Box들을 2D Gaussian Distribution 형태로 변환한후, Normalized Wasserstein Distance(NWD)를 통해 두 Gaussian Distribution의 유사성을 구한다.
위와 같은 방식으로 계산된 NWD는 Non-maximum suppression(NMS), IoU Loss 등에서 기존 방식을 대체하여 사용될 수 있으며, Tiny Object만으로 구성된 Dataset인 AI-TOD에서 기존 방식 대비 AP가 무려 6.7이나 향상되었다고 저자들은 주장한다.
Introduction
Tiny Object 탐지는 자율주행과 같은 다양한 Task에 있어서 중요한 요소중 한가지이다. 비록 Object Detection 성능 자체는 매우 큰폭으로 향상되었지만, 아직도 소형 객체 탐지 성능은 상용화되기 어려울 정도로 정확도가 떨어진다.
16 x 16 pixel 보다 적은 객체들로 구성된 AI-TOD 데이터셋의 경우, 굉장히 한정된 양의 시각 데이터를 제공하며, 이로 인해서 이러한 Tiny Object를 탐지해내는 것은 굉장히 어려운 문제로 꼽힌다.
최근 진행된 연구에서는 이러한 한계점을 해결하기위해서, GAN을 활용한 Super Resolution 방식으로 작은 Object의 크기를 크게 만들어 학습을 진행한다던가, FPN등의 Multi-scale Feature를 활용하는 방법을 적용하였으나, Tiny Object를 탐지하기위해서 별도의 추가적인 작업이 필요하다는 단점이 있다.
본 논문에서는 Tiny Object 탐지를 어렵게 하는 근본적인 원인인 IoU의 한계점을 설명하고, 이를 해결하기 위한 방법론을 제시한다. 6x6 크기의 Tiny Scale Object와 36x36 크기의 Normal Scale Object
위 그림에서 A는 Ground Truth, B는 GT에서 1 pixel만큼 shifting 한 Bounding Box, C는 4 pixel 만큼 shifting한 Bounding Box이다. Normal Scale Object는 1Pixel에선 0.9, 4Pixel에서는 0.65의 IoU를 가졌지만, 반면 Tiny Scale Object는 1Pixel 차이만으로도 이미 IoU가 0.53으로 크게 하락하고, C의 경우에는 아예 0.06으로 매우 낮은 IoU를 가지게 되는 것을 볼 수 있다.
즉, Tiny Scale Object에서의 IoU는 Ground Truth와 거의 완벽히 일치하지 않는 이상, IoU Threshold를 넘는 IoU값을 가지게 되는 것이 어렵고, Positive Sample로 Labeling되기 어렵다는 사실을 나타낸다.
Methodology
저자들이 제안하는 새로운 Metric은 다음과 같다.
먼저, Bounding Box (cx, cy, w, h)에 대해서, 내부에 내접하는 타원의 형태를 나타내면 아래와 같다.
그리고 2D Gaussian Distribution의 확률 분포 함수는 아래와 같다.
이 때, Gaussian Distribution의 Mean Vector와 공분산 행렬이 아래 조건을 만족시킬 경우, 위 수식의 타원이 2D Gaussian Distribution의 Density Contour가 되므로, Bounding Box (cx,cy,w,h)는 다음과 같은 2D Gaussian Distribution으로 표현될 수 있다.
이는 즉, Bounding Box A와 B의 유사도가 두 Gaussian Distribution의 거리로 표현될 수 있음을 의미한다. 본 저자들은 두 Gaussian Distribution의 거리를 측정하기 위해서 Wasserstein Distance 개념을 적용하였다. 엄청 어려워보이지만, 쉽게 말하면 두 Bounding Box를 바탕으로 2D Gaussian Distribution으로 전환하고, L2 Norm 개념으로 두 2D Gaussian Distribution의 유클리디언 거리를 구한다라는 느낌으로 이해하면 되는 것으로 보인다.
IoU를 대체하는 식으로 사용하기 위해서는 0과 1사이의 값을 가지도록 변경해주어야 하므로, 저자는 아래와 같은 방식으로 Normalize를 진행한다. 이 때, 분모 C는 데이터셋에 맞게 조정되는 Hyperparameter이다.
Experiments
위 표는 AI-TOD에 적용한 다양한 Evaluation Metric의 결과이다. NWD를 기존 방식들과 비교했을 때, Label Assigning에서 가장 효과적이었다.
이는 위에서 언급한 IoU의 과도한 민감도로 인해 IoU Threshold를 넘지 못하는 문제를 효과적으로 해결했기 때문으로 보이며, 후처리를 담당하는 NMS에서는 그다지 좋은 모습을 보여주지는 않는다.
다만 위 표만 봐도 어느정도 예상이 되는 부분이 있는데, Large를 뜻하는 AP_L이 없다. 즉, Tiny Object에 강인해진 대신, 그 여파로 Large Object에 대해서는 성능이 하락된 것으로 보인다.
실제로 직접 실험한 것은 아니지만, 딥러닝논문읽기모임의 안종식님의 말에 따르면(https://www.youtube.com/watch?v=eGKlg4sZ0Zw), VisDrone 데이터셋을 분류한 결과, AP_S(small)은 기존 IoU 방식 mAP 0.258에서 NWD를 사용했을 시 0.292로 향상되는 모습을 보였지만, AP_L(Large)의 경우에는 기존 IoU 방식 0.655에서 NWD방식 0.405로 큰폭의 하락이 존재했다고 한다.
결국 해당 방식도, Anchor Size를 줄여서 작은 Object를 잘 찾게 되면, 큰 Object를 못 찾게 되는것과 유사한 모습을 보인다는 것을 확인할 수 있다.
Conclusion
비록 한계점도 존재하는 연구이긴 하지만, 본 논문에서는 Tiny Object를 효과적으로 탐지할 수 있는 방법론을 소개했다.
작은 객체로만 이루어진 AI-TOD 데이터셋에서 SOTA를 달성하였으며, VisDrone 데이터셋의 경우에도 mAP_L이 비록 감소하긴 했지만 최종적인 mAP@0.5가 조금이나마 개선되는 모습을 보였다.
따라서 본 방식은 소형 객체 탐지에 특화된 모델을 만드는데에 주요하게 동작할 것으로 보인다.
Masked Autoencoders Are Scalable Vision Learners(MAE)
최근엔 주로 교신저자로만 이름을 올리던 Kaiming He 님의 1저자 논문인 MAE이다. 본 논문의 내용도 역시나 Kaiming He 답게 굉장히 유망한 결과를 보이고 있다. 항상 느끼는 것이, 이런 류의 논문은 성능 자체가 중요한 게 아니라, AI 연구의 한가지 방향성을 개척한다는 점에서 의미가 큰 것 같다.
Abstract
본 논문에서는 확장 가능한(Scalable) Self Supervised Learning 모델인 Masked AutoEncoder를 제안한다.
MAE의 접근 방법은 간단하다. 입력 이미지의 Patch를 임의로 골라서 마스킹 작업하고, 손실된 픽셀을 재구축하는 방식으로 학습을 진행한다.
본 구조의 첫 번째 핵심 설계는, 비대칭 형태의 Encoder-Decoder 구조이다. Encoder는 Masking된 patch를 제외하고 Visible Patches만을 사용한다. 반면 Lightweighted Decoder는 여기서 얻어진 Encoder에서 얻어진 Latent Representation과 Masked Patches를 함께 사용하여 이미지를 Reconstruction 한다.
두 번째 핵심 설계는, 높은 masking 비율이다. 본 논문에서는 효과적인 Self Supervisory Task를 수행하기 위해서 75%의 Mask Ratio를 가지고 있다. 너무 작은 Masking 비율을 둘 경우, Image의 각 픽셀은 그다지 Semantic하지 않기 때문에 단순히 주변 영역을 보고 쉽게 추론할 수 있기 때문에 높은 Masking을 통해 학습을 진행하였다.
이러한 두가지 설계를 합쳐서 구현한 MAE는 3배 이상의 속도 향상을 이뤄냈고, (인코더의 입력 차원이 줄었으므로), 정확도 또한 ImageNet 1K 데이터만으로 ViT-Huge에서 87.8%의 정확도를 얻어냈으며, 이는 기존 Supervised Learning 방식의 정확도보다 높다.
뿐만 아니라, Downstream Task에서도 기존 지도 학습 방식을 능가하는 정확도를 보였으며, Vision Task도 BERT와 같은 Masking 방식으로 Self Supervised Learning을 통해 이해능력을 학습시킨 후, 그를 바탕으로 Fine Tuning Approach가 가능하다는 방향성을 제시한 유망한 결과를 보인다.
Introduction
딥러닝 연구가 빠르게 성장함에 따라 좀 더 크고, 거대한 딥러닝 아키텍쳐들이 쏟아져 나오고 있다.
하드웨어가 발전하면서, 이러한 거대한 아키텍처의 모델들은 백만장정도의 이미지에는 너무나도 쉽게 Overfitting되고 있으며, 이제는 수백만장의 이미지를 통해 학습을 하려는 시도가 늘고 있다.
많은 데이터에 대한 이러한 수요는 NLP 분야에서 Self-supervised pre-training이라는 방법론을 통해 효과적으로 해결되었다. GPT와 BERT와 같은 모델은 데이터의 일부를 제거하고, 원본 데이터를 예측하는 방식으로 학습을 진행한다.
본 논문에서 제안하는 MAE의 기존 개념은 좀 더 General한 Denoising AutoEncoder라고 볼 수 있으며, 이는 Vision Task에서 자연스럽게 적용이 될 수 있다. 실제로 비슷한 다른 연구 사례가 BERT 이전에 존재하기도 했었다.
그럼에도 불구하고, BERT에서 대단히 성공적이었던 이러한 방법론은 Vision 분야에서는 그다지 큰 효용을 얻지 못했다는점에서 한가지 의문이 발생한다. Masked Autoencoding이 왜 Vision과 NLP 분야에서 차이를 가지는가?
저자들은 첫째로, Vision과 NLP의 근본적인 구조 차이를 원인으로 꼽았다. 기존 Vision Task에서는 CNN이 압도적으로 우세했고, CNN은 정규 이미지를 입력으로 받아 처리를 진행하는 과정을 거치므로, Mask Token이나 Positional Embedding과 같은 부수적인 Indicator들을 적절히 통합하는 것이 굉장히 어려운 일이었다. 하지만, 최근 ViT가 소개됨에 따라 이러한 구조의 차이는 더 이상 장애물이 되지 않는다.
둘째로, 정보의 밀도 자체가 다르다는 점을 꼽았다. 언어는 사람이 직접 만드는 일종의 고밀도 신호체계라고 볼 수 있다. 단순히 몇개의 Missing Word를 찾아내는 과정에서도 매우 높은 수준의 언어적 이해가 필요하기 때문이다.
반면, 이미지의 경우, 공간적 특성을 매우 크게 담고 있는 일종의 자연 신호이다. 따라서, 특정 patch가 지워진다고 하더라도 주변의 patch를 통해 손쉽게 복원이 가능하며, 그다지 높은 수준의 이미지 이해 능력이 없더라도 쉽게 수행될 수 있다.
본 논문에서는 이러한 단점을 타파하기 위해 굉장히 높은 비율로 Masking을 진행한다. 이러한 전략을 통해 이미지 전반을 충분히 이해하지 못하면 복원이 불가능하게끔 유도하여 효과적인 학습을 유도할 수 있다.
뿐만 아니라 비대칭성 Encoder-Decoder 구조를 통해서 Encoder에서는 전체 패치의 25%(Visible Patches)만을 사용하고, 이를 통해 메모리 사용량과 학습 속도를 개선시켜 거대한 모델에도 효과적으로 적용할 수 있다.
해당 방법을 ViT-Large/Huge에 적용한 결과 ImageNet-1K에서 더 높은 일반화 성능을 보여주었으며 87.8%의 정확도를 달성하여 기존 방식보다 우수함을 입증하였다.
Approach
논문 그림 발췌
Masking의 경우 75%정도로, 매우 높은 비율의 Masking을 진행함으로써 주변 Pixel을 통해 단순히 Masked Patches를 찾아낼 수 없도록 유도한다.
MAE Encoder 부분은 ViT를 그대로 사용하였으며, 차이점은 Visible(Unmasked Patches)만을 사용했다는 점이다. 이러한 특성으로 인해 메모리 사용량 및 계산량에서 큰 이점을 가지며, 전체 입력 데이터의 25%만을 사용하는 효과가 있다.
MAE Decoder는 Visible과 Masked Patches를 모두 사용하는 방식으로 구성되며, 비어있는 patches들을 채워 넣는 방식으로 reconstruction을 진행한다. decoder는 사전 학습시에만 사용되기 때문에 Encoder와 별개로 사용자들이 원하는 디자인으로 유동적으로 변경할 수 있는 구조이다. Decoder 자체는 Encoder에서 Latent Vector만 잘 뽑아낸다면 상대적으로 그다지 복잡한 작업을 요하지 않기 때문에 저자들은 Encoder보다 좁고 짧은 lightweight decoder 구조를 사용하였으며 성능 차이가 그렇게 크지 않았다고 한다.
학습할때는 Masked Patch에 대해서만 MSE(Mean Squared Error)를 구하는 방식으로 진행되며, 이는 BERT의 학습 메커니즘과 동일하다.
Experiments
Classification 성능(좌), Fine-tuning을 통한 Segmentation 성능(우)
기존 방식들에 비해서 더 높은 Generalization 성능을 바탕으로 정확도가 향상되었다.
뿐만아니라, Random Sampling과 Masking 자체가 이미 꽤나 강력한 Augmentation과 같은 기능을 하기 때문에, 최소한의 Augmentation만으로도 높은 정확도를 달성할 수 있었다고 한다.
기존 방식 대비 Encoder에서 사용하는 입력 사이즈가 1/4 정도 수준이기 때문에, Parameter가 보다 적고 가벼우며, Scalable 한 특성을 지닌다.
Conclusion
본 논문은 NLP에서 자주 쓰이는 방식인 Self-Supervised Learning을 Vision Task에도 적용시키기 위한 MAE를 제안하였다.
매우 높은 Masking Ratio를 통해 단순히 주변 Pixel을 활용하여 추론이 불가능하도록 하게 함으로써, 모델로 하여금 Visual Understanding을 학습하도록 강제하고, 실제로 유망한 결과를 얻어낼 수 있었다.
뿐만 아니라, 위와 같은 방식으로 전체적으로 Image를 보는 방법에 대해 학습한 모델은, Down-stream Task에 대해서도 약간의 Fine-tuning을 진행하면 마치 BERT와 같이 효과적으로 동작함을 보였다.
Encoder에서 25%정도의 Patch를 사용하는 방식을 통해 ViT의 한계점이라고도 볼 수 있는 고화질, 대량 데이터 학습에 있어서 보다 빠른 학습이 가능하고 Down-stream Task에 빠르게 적용시킬 수 있는 Scalable 모델을 제시하였다는 점이 가장 큰 Contribution이라고 생각한다.
역시 Kaiming He답게 굉장한 내용의 논문이었다. 구현 난이도와 Concept 자체는 심플하지만, 강력한 성능을 가지는 방법. 항상 존경스러운 마음뿐이다.
Precision(정밀도) - TP / (TP + FP) - 모델이 예측한 positive중에서 실제 Positive의 비율
Recall (재현율) - TP / (TP + FN) - 실제 Positive중 모델이 예측한 비율
Fall-Out - FP / (FP + TN) - 실제로는 Negative인데 모델이 Positive로 오탐한 비율
F1 Score - 무조건 Positive로 분류하면 Recall이 1이 되지만 Precision이 폭락하고, 무조건 Negative로 분류하면 Precision은 1이 되지만 Recall이 0이 된다. - 이처럼 Precision이나 Recall은 단일 Metric으로 사용하기엔 모델의 일반화 성능을 나타낼 수 없다는 한계점이 존재하기 때문에 Precision 과 Recall의 조화평균값인 F1 Score를 사용할 수 있다.
Receiver Operation Characteristic Curve(ROC) - Area Under Curve(AUC) 출처: https://glassboxmedicine.com/2019/02/23/measuring-performance-auc-auroc/ - 통칭 ROC-AUC - Fall out과 Recall을 통해 FPR, TPR을 X,Y축으로 두고 Threshold를 변경시키면서 그린 곡선을 ROC라고 한다. - 이 때, ROC를 수치화 할 수 있는 방법이 딱히 없으므로, Area Under Curve라는 곡선 밑 부분의 넓이 값을 통해 성능을 측정한다. Recall이 높고, Fall Out은 낮을 수록 넓이가 1에 가까워진다.
Regression(회귀) Metrics
MAE(Mean Absolute Error) - 예측값과 Ground Truth 사이의 차이의 절대값의 평균
MSE(Mean Squared Error) - 예측값과 Ground Truth 사이의 차이의 제곱의 평균 - 제곱 때문에 Anomaly Data에 매우 민감함(크기가 어마어마하게 커질 수 있음)
RMSE(Root Mean Squared Error) - MSE에 루트를 씌운 값 - Anomaly에 상대적으로 덜 민감함
RMSLE(Root Mean Squared Logarithmic Error) - 예측값과 정답값에 로그를 취한 뒤 계산한 RMSE
Learning Phrase Representations using RNN Encoder Decoder for Statistical Machine Translation
자랑스러운 한국인 연구자이신 조경현 교수님의 논문으로, Seq2Seq의 근원이 된 논문이다. 본 논문은 RNN에서의 Encoder Decoder를 최초로 제시했을 뿐만 아니라, LSTM을 보다 효율적으로 바꾼 GRU(Gated Recurrent Unit)을 제안했다. Encoder Decoder 구조는 나중에 Seq2Seq 논문 리뷰에서 자세히 다루고(본 논문의 저자인 조경현 교수님께서 Seq2Seq에 최초로 Attention을 도입한 논문도 있다!) 본 포스팅에서는 LSTM에 이어서 GRU만 일단 다뤄보도록 하자.
LSTM 개념을 숙지하지 않으셨다면, LSTM 논문 리뷰를 먼저 보고 오시면 이해가 보다 쉬울 것이다.
RNN의 전설을 쓴 논문 LSTM이다. 1997년에 어떻게 이런 구조를 고안해내셨는지 놀라운 따름이다.비록 1997년에 연구되었지만, 아직까지도 시계열 분석등에 종종 사용되고 있는 LSTM 논문을 리뷰해보자.원문 논문은 32장인데다가, 예전 논문이라 그런지 지금 나오는 논문과는 전개 방식이나 다루는 관련연구가 너무 달라서 개인적으로 이해하는데 굉장히 어려웠다.
Idea Factory KAIST에 올라와있는 강의를 보면서 이해하니까 논문 본문이 술술 읽히는 느낌이었다.너무 좋은 강의해주신 조재영님께 감사의 말씀을 올린다.
Abstract
기존 Vanilla RNN은 Time Interval이 큰 데이터에 대한 지식을 잘 저장하지 못하는 한계점이 존재한다.
이러한 한계점은 Error back flow(back propagation)과정이 정보를 충분히 전달하지 못하기 때문이고, 수 많은 Layer를 지나면서 Weight가 Vanishing 되기 때문이다.
본 논문에서는 이러한 문제점을 해결할 수 있는 novel, efficient gradient-based method인 LSTM(Long Short-Term Memory)를 제안한다.
LSTM에서는 특정 정보가 Gradient에 안좋은 영향을 미치지 않는 한, 약 1000번의 time step 이상의 interval에도 정보를 소실하지 않고 효과적으로 정보를 전달할 수 있다.
본 논문에서는 인위적으로 만들어낸 다양한 패턴들에 대해서 LSTM을 적용시켜 RTRL, BPTT, Recurrent Cascade-Correlation, Elman nets, Neural Sequence Chnking등과 비교해보았으며, 실험을 통해 LSTM의 우수함을 입증하였다.
단순히 성능 지표만 높을 뿐 아니라, 기존 RNN류 모델들이 풀지 못했던 Long Time Lag Task에서 최초로 성공을 거두었다고한다.
Long Short-Term Memory(LSTM)
LSTM Cell의 구조는 위와 같다.
기존 Vanilla RNN이 hidden state만을 사용하던 것과 달리, LSTM에서는 Cell State라는 새로운 Flow를 도입하였다. 이는 마치 컨베이어 벨트처럼 이전에 입력됐던 정보들을 전달해주는 역할을 한다.
이전 Cell에서 넘어온 hidden state에 대해서 과거의 정보중 어느 것을 Cell State에 반영할 것인지를 정하는 Forget Gate(불필요한 정보를 잊는다는 의미), 현재 입력된 정보를 얼마나 Cell State에 반영할 것인지를 정하는 Input Gate, 다음 Cell에 전달할 hidden state 값에 Cell State를 얼마나 반영할 것인지를 정하는 Output Gate로 구성된다.
Forget Gate
과거에서 넘어온 정보 중, 불필요하다고 여겨지는 데이터들을 삭제해주는 역할을 한다.
정확히는 삭제라기보다는, Sigmoid 함수를 통해 얻어진 0~1 사이의 가중치를 곱해줘서 학습을 하면서 상대적으로 중요한 정보에는 높은 가중치를, Gradient 갱신에 별로 좋지 않은 영향을 끼치는 정보에 대해서는 낮은 가중치를 가지게 한다.
즉 Neural Network를 학습하여 얻어진 W_f(Weight of Forget Gate)와 B_f(Bias of Forget Gate)를 바탕으로 0에 가까운 값이 나오면 정보를 버리는 효과, 아예 0이 되면 삭제 반대로 1에 가까울 수록 정보 보존, 1일 경우 데이터 그대로 전달의 역할을 함으로써 Cell을 지나면서도 계속적으로 유의미한 데이터들은 Cell State Flow에 보존되도록 한다.
Input Gate
현재의 입력값 X_t와 이전 hidden state를 적절히 사용하여 현재 Cell의 Local State를 얻어내고, 이를 Global Cell State에 얼마나 반영할지를 결정하는 게이트이다.
마찬가지로 Sigmoid 함수를 사용하므로, 현재 시점에서 얻은 정보가 큰 효용가치가 있을 경우 Cell State에 많이 반영하고, 별로 의미가 없는 데이터일 경우에는 0에 가까운 가중치를 줘서 반영을 최소화한다.
이후, 과거 hidden state에서 적절히 forget이 이루어진 cell state와, 현재 cell에서 얻을 수 있는 새로운 데이터를 반영한 cell state를 더해서 최종적인 global cell state를 update하게 된다.
Output Gate
최종적으로 얻어진 Cell State 값에서 어느정도를 취해서 Hidden State로 전달할 것인지를 정하는 마지막 Gate이다.
여기서 최종적으로 얻어진 h_t를 바탕으로 다음 셀에서는 C_t+1을 구하게 된다.
Conclusion
본 논문은 기존 Vanilla RNN이 가지는 문제점인 Long-term dependencies를 효과적으로 해결할 수 있는 LSTM 방식을 제안한다.
LSTM은 Cell State 개념을 도입하여 과거의 데이터를 유지하면서도 불필요한 데이터는 Forget Gate를 통해 삭제하여 Gradient Update에 최적의 상태를 유지한다.
기존 RNN 방식 대비 정확도를 크게 향상시킬 수 있었으며, Long Time Lack Task의 경우 기존 RNN 모델들이 해결하지 못했던 문제를 해결할 수 있었다.
BERT: Pretraining of Deep Bidirectional Transformers for Language Understanding
NLP계의 전설, BERT 논문을 리뷰해보자.
Abstract
본 논문은 새로운 방식의 Language Model을 소개한다. Bidirectional Encoder Representations from Transformer(BERT)이다.
기존 ELMo와 같은 방법은 Shallow Bidirectional 하거나, GPT와 같이 Unidirectional 하였지만, 본 논문의 BERT는 모든 Layer에서 좌측과 우측에 있는 모든 내용을 학습한다.
그 결과로 BERT 모델은 단순히 output layer를 하나 추가하는 방식으로 대다수의 NLP Task에서 SOTA를 달성하였다.
GLUE 성능 80.5%(기존 SOTA 대비 7.7% 향상), MultiNLI 성능 86.7% (기존 SOTA 대비 4.6% 향상), SQuAD v1.1 에서 F1 93.2(기존 SOTA 대비 1.5 point 향상), SQuAD v2.0에서 F1 83.1(기존 SOTA 대비 5.1 point 향상)
Introduction
Language Modeling에서 Pre-training은 NLP Task 성능을 높이는데 크게 기여해왔다.
이러한 NLP Task들은 Natural Language Inference나 Paraphrasing과 같은 문장간의 관계를 예측하는 문장 단위 Task와 Named Entity Recogintion(NER)와 Question Answering과 같이 토큰 단위의 정밀한 Output을 반환해야 하는 토큰 단위 Task로 나뉜다.
Pre-training 방식을 Down-stream Task에 적용하는 방법론은 크게 2가지로 나뉠 수 있다고 저자는 설명한다.
첫 번째로는, ELMo와 같은 Feature-based Approach로 사전 학습된 모델 Feature를 특정 Task를 수행하는 곳에 Freeze한채로 붙여서 사용하는 방식이다.
두번째로는, GPT와 같은 방식의 Fine-tuning Approach로, 대량의 데이터로 학습된 모델을 특정 Task에 맞는 Dataset으로 Fine Tuning 시키는 것이다. Feature-based와 달리 Fine-tuning 과정에서 Pre-trained Feature들 또한 갱신된다.
ELMo 방식의 경우 Left to Right 방식과 Right to Left 방식에서 추출된 Embedding을 Concat하여 사용하는 Shallow Bidirection이고, GPT의 경우 Left to Right의 단방향성(Unidirection) 방식으로 학습을 진행한다.
이러한 단방향성 접근은 Pre-trained Representation의 성능을 크게 제한한다고 저자는 주장한다. 예를 들어, OpenAI의 GPT모델의 경우 Left to Right 구조를 지니고 있는데, 이는 각각의 토큰이 자신의 위치 이전에 있는 토큰만을 접근할 수 있음을 의미하며, 문장 단위 Task에서는 최적의 성능을 얻지 못하게 되고, Question Answering과 같은 토큰에 굉장히 민감한 Task에서는 매우 심각한 성능 향상을 일으킬 수 있다.
본 논문에서는 양방향성을 고려한 Fine-tuning Approach 모델인 BERT를 소개한다. Mask Language Model 방식을 통해 특정 토큰을 임의로 마스크를 씌워주고, 원본 단어를 예측하는 방식으로 학습을 진행한다.
이 과정에서 MLM은 왼쪽에 존재하는 토큰과 오른쪽에 존재하는 토큰을 모두 고려하게되는데, 이것이 바로 BERT의 양방향성을 가지게 하는 요소이다.
MLM 뿐만 아니라, BERT에서는 Next Sentence Prediction(NSP)까지 활용을 한다. 이를 통해 문장간의 연관관계를 좀 더 잘 나타낼 수 있으며, Question Answering과 같은 문제에서 높은 성능 향상을 가져온다.
본 논문의 기여점은 다음과 같다. 첫째로는 Bidirectional Language Model을 제시했다는 점, 둘째로는 Fine-tuning based 방식으로는 최초로 SOTA를 달성했으며, 별도의 Task Specific한 구조없이 단순히 Fine-tuning을 통해서 높은 성능을 달성할 수 있기에 공학적 편리성을 제공한다는 점이 있다.
BERT
BERT는 크게 2가지 단계로 나뉘는데, 첫 단계는 대규모 데이터셋을 바탕으로 문장 이해를 학습하는 pre-training 과정과 down-stream task에 맞게 fine-tuning 하는 과정이다.
pre-training 과정에서는 특정 task에 상관없이 unlabeled 데이터를 통해서 기본적인 문맥 이해를 위한 학습이 진행되며, fine-tuning 과정에서는 pre-training 과정에서 생성된 parameter를 바탕으로 labeled 데이터를 통해서 fine-tuning을 진행한다.
fine-tuning 과정을 통해서 각각의 down-stream task에 대해 서로 다른 모델들이 생성되지만, 이들은 기존 pretrained 에 사용된 Architecture와 크게 다르지 않다. 마지막에 Dense Layer만 추가되는 정도이다.
모델 구조는 기본적으로 Transformer의 Encoder 부분을 활용하여 구현되었으며, Layer 12개, Hidden Layer Size 768, Multi-head Self Attention의 Head 개수 12개를 바탕으로 하는 BERT Base 모델과 Layer 24개, Hidden Layer Size 1024, Head 개수 16개를 바탕으로하는 BERT Large 모델을 실험하였다.
BERT Base 모델은 GPT 와 거의 비슷한 수준의 파라미터 수를 가진다.
BERT - Input/Output Representations
BERT가 다양한 Down-stream task들을 아키텍처의 변화 없이 높은 정확도로 수행하기 위해서는 input representation이 단일 문장 뿐만 아니라, Question Answer와 같은 문장의 pair도 효과적으로 표현할 수 있어야 한다.
본 논문에서 다루는 "Sentence"란, 실제 언어학적인 문장의 의미보다는 연속적인 text들의 배열이다. 즉, Input Sequence란, 입력으로 들어오는 토큰들의 집합이다. 그것은 1문장일 수도, 2문장일 수도 있다.
BERT는 WordPiece embedding을 사용하였으며 약 30000개의 token vocabulary를 통해 구축되었다.
첫 문장은 반드시 classification 토큰인 [CLS]로 시작하며, 해당 토큰의 최종 hidden state값을 바탕으로 해당 문장이 정확히 어떤 내용을 다루는지를 인식하고 Classification을 진행하게 된다.
필요에 따라서, Sentence Pair가 1개의 Sequence로 입력될 수 있다. 이를 효과적으로 처리하기 위해서 BERT는 두가지 문장을 [SEP] 토큰을 통해서 구분한다. 그 후, 학습 가능한 Embedding을 각각의 토큰에 더해줌으로써 해당 토큰이 문장 A에 속하는지, 문장 B에 속하는지 구분가능하도록 한다.
Pre-training BERT
ELMo나 GPT의 방식과 달리 BERT는 기존의 Left to Right, Right to Left 방식을 사용하지 않는다.
그 대신, BERT에서는 두가지 unsupervised task를 통해서 문장을 이해하는 능력을 습득하게 된다.
Task #1 Masked LM
BERT는 양방향 학습을 위해서 Masked Language Modeling(MLM)이라는 과정을 제안한다. 이 과정은 1953년에 발표됐던 논문에서 착안하였으며, Cloze task라고 불리던 방식이다.
입력 Sentence에 대해서 15% 정도의 Token을 Mask로 사용하게 되며, Mask로 지정된 부분을 예측하고 softmax를 통해 vocabulary에서 최종 토큰을 가져오는 방식으로 동작한다. 이 때, 문장 전체를 예측하지 않고 Mask에 해당하는 토큰 부분만 예측한다.
이를 통해 Bidirectional Pre-trained 모델을 얻어낼 수는 있지만, 실제 fine-tuning과정에서는 [Mask]를 사용하지 않기 때문에 이러한 차이를 제거해주기위해서 항상 Mask 토큰을 [Mask]로 대체하지는 않는다.
본 논문의 저자들은 임의로 전체 토큰의 15% 정도를 예측에 사용하기 위한 토큰으로 사용하고, 이중 80%를 [Mask]로 대체하고, 10%는 임의로 아무 토큰값이나 넣어 대체하고, 10%는 아예 변경하지 않는 방식으로 학습을 진행한다. 이 때, 아예 변경하지 않았던 10%의 토큰의 경우에도, BERT는 이것이 원본인지 임의로 바뀐 것인지 구분하지 못하므로, 예측을 진행해야 한다.
각각의 토큰에 대해서 예측을 진행하고, Cross Entropy Loss를 통해 모델을 학습시킨다.
Task #2 Next Sentence Prediction(NSP)
NLP Task중에서 Question Answering(QA)나 Natural Language Inference(NLI)의 경우 두 문장간의 관계성을 확실히 이해할 수 있어야 한다. 이는 단순히 Language Modeling만으로는 얻을 수 없는 정보이다.
이런 문장간의 관계성을 학습시키기 위해서 BERT에서는 Next Sentence Prediction(NSP)라고 불리는 Binary Classification을 수행한다.
전체 데이터중에 절반은 문장 A와 실제 문장 A의 뒤에 오는 문장인 문장 B를 뽑고, 나머지 절반은 문장 A와 전혀 관련 없는 문장 B를 뽑는 방식으로 샘플링을 한 다음 학습을 진행한다.
B가 정말 A의 다음 문장이라면 IsNext Label을, B가 A와 관련 없는 문장이라면 NotNext Label을 사용하는 방식으로 문장간의 연관관계를 학습하게 되는데, 구현상으로 굉장히 간단하지만 QA와 NLI 부분에서 굉장히 높은 수준의 정확도 향상을 가져왔다고 저자들은 주장한다.
Fine-tuning BERT
Fine tuning은 Pretrain에 비해서 훨씬 더 빠르게 진행되며, 대략 2~3epoch만 학습해도 SOTA 수준에 이르는 것을 저자들은 실험을 통해 보여준다.
위 그림은 각각의 NLP Task에 대해서 Fine-tuning이 어떻게 이뤄지는지를 도식화한 그림이다.
Conclusion
본 논문에서 진행한 실험의 결과물들은 Language Model에 있어서 Unsupervised Pre-training은 매우 중요한 요소라는 것을 입증하고 있다.
특히, 본 논문에서 제시한 Bidirectional Pre-training은 데이터가 적은 fine-tuning task에서도 효과적인 성능을 보인다는것을 알수 있었다.
본 논문이 학계에 기여하는 바로 가장 주요한 것은, Bidirectional Pre-training의 효과를 down-stream task에 즉시 적용할 수 있도록 거의 변화가 없는 (Dense Layer만 뒤에 붙이면 되는) 아키텍처를 제시했다는 점에 있다고 저자들은 주장한다.
역시 전설적인 논문답게 배울 점이 많은 논문이었다. 도대체 구글의 리서쳐들은 어떻게 이런 아이디어들을 내는 건지 궁금하다. 복잡한 수식 없이도 굉장히 직관적으로 이해가 가능하며, 이론적 근간이 충분하지 않은 사람이 듣더라도 고개를 끄덕일 만한 설득력 있는 주장을 펼쳐나가면서 결과까지 기존 연구보다 압도적으로 좋게 나타난다. 경이로울 지경이다.
N까지의 소수를 모두 구하는 문제는 알고리즘 풀이 사이트 빈출 유형일 뿐만 아니라, 기업체에서 가볍게 보는 라이브 코딩이나 손코딩 문제로 매우 자주 출제된다.
그 이유는, 난이도 자체는 쉽지만 최적화 할 수 있는 여지가 굉장히 많기 때문이다.
대표적인 손코딩/라이브코딩 시나리오는 아래와 같다.
1. for문으로 한번 짜보실래요?
2. 지금 코드의 시간복잡도 설명해보실래요?
3. for문의 연산 수를 줄일 수 있는 방법이 있을까요?
4. 이 보다도 더 줄일 수 있는 방법이 있을까요?
시나리오를 따라서 한번 문제를 풀어보자!
Req1) 단순 반복문으로 짜보실래요?
def GetPrimeNoOpt(n):
res = []
for i in range(2, n+1):
is_prime = True
for j in range(2, i):
if i % j == 0:
is_prime = False
break
if is_prime:
res.append(i)
return res
2부터 n-1까지의 숫자들 중 약수가 존재하면 소수가 아니다.
만약 끝까지 약수가 없었으면 소수 목록에 추가
시간복잡도 N^2
Req2) For문 연산 수를 줄여보실래요?
def GetPrimeSqrt(n):
res = []
for i in range(2, n+1):
is_prime = True
for j in range(2, int(math.sqrt(i))+1):
if i % j == 0:
is_prime = False
break
if is_prime:
res.append(i)
return res
약수는 항상 대칭성의 원리를 만족함
16의 약수 1,2,4,8,16은 중앙값 4를 중심으로 했을 때, 2로 곱하고, 나누고를 통해서 만들어 낼 수 있는 숫자임
즉, 숫자 N의 소수 여부를 판별하기 위해서는, 굳이 N-1까지의 약수를 모두 체크할 필요 없이, N의 제곱근까지만 검사했을 때 약수가 없으면, 그냥 약수가 없다는 것을 의미함
이를 활용하면 시간복잡도를 nlogn으로 줄일 수 있음
Req3) 그럼 실행시간을 여기서 더 줄일 수 있는 방법이 있을까요?
def GetPrimeEratosthenes(n):
chk = [True]*(n+1)
res = []
chk[0], chk[1] = False, False
for i in range(2, int(math.sqrt(n))+1):
if chk[i]:
res.append(i)
j = 2
while i*j <= n:
chk[i*j] = False
j += 1
res = [x for x in range(n+1) if chk[x]]
return res
취준 중에 알고리즘 문제 사이트에서 문제를 풀었다면 한번쯤 만나봤을, "에라토스테네스의 체"를 활용할 수 있다.
그리고 에라토스테네스의 체를 사용할 때에도, 위의 대칭성의 원리를 활용하면 더 연산량을 줄일 수 있다.
해당 방식은 n이 클 때 유리한 방법으로, 불필요한 반복 연산을 줄여준다.
100,000까지의 소수 구하기 실행 시간 비교
실제로 최적화가 효과가 있었는지, 실험을 진행해보자.
1부터 100,000까지의 소수를 위의 세가지 방식으로 구해보고 걸린 시간을 측정해봤다.
# get prime numbers in range(1, N)
# GetPrimeNoOpt - No Optimization
# GetPrimeSqrt - Sqrt Optimization
# GetPrimeEratosthenes - Sieve of Eratosthenes
import math, time
def GetPrimeNoOpt(n):
res = []
for i in range(2, n+1):
is_prime = True
for j in range(2, i):
if i % j == 0:
is_prime = False
break
if is_prime:
res.append(i)
return res
def GetPrimeSqrt(n):
res = []
for i in range(2, n+1):
is_prime = True
for j in range(2, int(math.sqrt(i))+1):
if i % j == 0:
is_prime = False
break
if is_prime:
res.append(i)
return res
def GetPrimeEratosthenes(n):
chk = [True]*(n+1)
res = []
chk[0], chk[1] = False, False
for i in range(2, int(math.sqrt(n))+1):
if chk[i]:
res.append(i)
j = 2
while i*j <= n:
chk[i*j] = False
j += 1
res = [x for x in range(n+1) if chk[x]]
return res
start = time.time()
GetPrimeNoOpt(100000)
print("GetPrimeNoOpt")
print(f"{(time.time() - start)*1000}ms")
start = time.time()
GetPrimeSqrt(100000)
print("GetPrimeSqrt")
print(f"{(time.time() - start)*1000}ms")
start = time.time()
GetPrimeEratosthenes(100000)
print("GetPrimeEratosthenes")
print(f"{(time.time() - start)*1000}ms")
결과
GetPrimeNoOpt
11862.13207244873ms
# 약 11.86초
GetPrimeSqrt
73.03857803344727ms
# 73 ms
GetPrimeEratosthenes
13.015270233154297ms
# 13 ms
각각의 Sorting 방식을 간단히 알아보고 구현 코드를 하나씩 알아보자.(원래 나눠서 포스팅을 올릴까하였으나, 그냥 한곳에 몰아놓는게 저도, 여러분들도 보기 편하실 것 같아 모았습니다.)
Bubble Sort(버블 정렬, 거품 정렬) 기초
Bubble Sort GIF, Wikipedia
앞에서부터 i번째 인덱스와 i+1번째 인덱스의 원소를 비교하며, 오름차순의 경우 i번째 인덱스의 원소가 i+1번째 인덱스의 원소보다 값이 클 경우, 두 값을 바꿔주는 방식으로 정렬을 진행
한번의 Iteration을 다 돌고 나면, 적어도 배열의 맨 끝에는 항상 "최댓값"이 가게 되므로, 배열의 길이가 N일 때, 최대 N번의 Iteration을 돌고나면 확정적으로 정렬이 완료된다.
N번, N-1번, N-2번, ... 2번, 1번 순으로 연산이 수행되므로 Big-O는 (N^2)이다.
Insertion Sort(삽입 정렬) 기초
Insertion Sort GIF, Wikipedia
앞에서부터 스캔하며, i번째 원소가 들어갈 적절한 위치를 찾아서 삽입해주는 방식이라고 하여 삽입 정렬이라는 이름을 가지게 되었다.
오름차순의 경우, 왼쪽엔 i번째 원소보다 작은 값, 오른쪽엔 i번째 원소보다 큰 값을 만족하는 위치에 적절히 원소를 삽입하여 정렬을 진행하게 된다.
배열 arr가 주어졌을 때, arr[i-1, i-2, ..., 1, 0]의 원소를 탐색하면서 arr[i] 값보다 큰 원소들의 경우 한 칸씩 값을 밀어주고 (arr[j] = arr[j-1]), 최초로 자신보다 작은 값이 나오면 해당 인덱스 옆에 arr[i]를 넣어준다. (말로 이해가 안간다면, GIF를 참고하고 코드를 보자.)
def HyunBubble(numbers):
for i in range(len(numbers), 1, -1):
for j in range(i-1):
if numbers[j] > numbers[j+1]:
numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
return numbers
Insertion Sort 구현
def HyunInsertion(numbers):
for i in range(1, len(numbers)):
target = numbers[i]
for j in range(i, 0, -1):
if numbers[j-1] > target:
numbers[j], numbers[j-1] = numbers[j-1], numbers[j]
else:
break
return numbers
Selection Sort 구현
def HyunSelection(numbers):
for i in range(len(numbers)):
mn = 999999999
for j in range(i, len(numbers)):
if numbers[j] < mn:
mn = numbers[j]
mn_idx = j
numbers[i], numbers[mn_idx] = numbers[mn_idx], numbers[i]
return numbers
Quick Sort 구현
Quick Sort의 경우, 사실 in-place sort로 하면서 pivot을 바꾸고 하는 과정이 굉장히 많지만,
그냥 최대한 단순히 Pythonic 하게 구현하면 아래와 같다.
연산량이 조금 더 많아지긴 하겠지만, 그럼에도 불구하고 높은 성능을 가진다.
def HyunQuick(numbers):
if len(numbers) <= 1:
return numbers
pivot = numbers[len(numbers)//2]
left, right, equal = [], [], []
for num in numbers:
if num < pivot:
left.append(num)
elif num > pivot:
right.append(num)
else:
equal.append(num)
return HyunQuick(left) + equal + HyunQuick(right)
Merge Sort 구현
def HyunMerge(left, right):
result = []
i,j = 0,0
while True:
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
if i >= len(left) or j >= len(right):
break
result = result + right[j:] if i==len(left) else result + left[i:]
return result
def HyunMergeSort(numbers):
if len(numbers) <= 1:
return numbers
mid = len(numbers)//2
left = HyunMergeSort(numbers[:mid])
right = HyunMergeSort(numbers[mid:])
return HyunMerge(left, right)
Heap Sort 구현
Heap Sort의 경우, Python에서는 heapq 라이브러리를 통해 아주 쉽게 리스트를 최소힙으로 바꿀 수 있으므로, 오히려 구현 난이도가 쉬운편이다.
import heapq
def HyunHeap(numbers):
result = []
heapq.heapify(numbers)
while numbers:
result.append(heapq.heappop(numbers))
return result
