[ICLR 2020] Deep Batch active Learning by Diverse, Uncertain Gradient Lower Bounds

안녕하세요 정의철 연구원입니다. 제가 이번에 리뷰할 논문은 ‘ Deep Batch active Learning by Diverse, Uncertain Gradient Lower Bounds’입니다. 이 논문에서는 Batch active Learning에 대한 새로운 알고리즘을 제안합니다. Batch Active learning by Diverse Gradient Embeddings (BADGE)은 예측 불확실성과 데이터의 다양성을 모두 고려하기 위해 고안된 전략으로 Hybrid 쿼리 전략에 해당합니다.쿼리 전략에 대한 내용은 [arXiv 2019] Diverse mini-batch Active Learning을 참고해주세요. BADGE의 주요한 특징으로는 그래디언트 공간을 활용하여 데이터 그룹을 샘플링하는 것입니다. 결론적으로 BADGE는 불확실성과 다양성 간을 모두 고려하면서 하이퍼파라미터 , 특정한 배치 크기나 아키텍처에 관계없이 일관되게 동일하거나 더 나은 성능을 달성합니다.

1. INTRODUCTION

딥러닝 모델은 다양한 지도 학습 테스크에서 높은 성능을 달성하고 있습니다. 그러나 이러한 성공의 많은 부분은 대량의 레이블이 지정된 데이터가 있는 도메인에 제한되어 있습니다. 레이블을 지정하는 비용을 줄이기 위한 접근 방법이 액티브 러닝(Active learning)입니다. 액티브 러닝은 최대한 정보량이 높은 데이터를 선별하여 레이블을 지정하고 최소한의 레이블링 작업으로 높은 성능 달성하려고 합니다.

불확실성이나 다양성만을 이용하는 방법은 모델 아키텍처, 배치 크기 또는 데이터 세트에 따라 일관되게 작동하지 않을 수 있습니다. 예를 들어 다양성 기반 접근법은 배치 크기가 매우 큰 경우에는 잘 작동할 수 있지만, 배치 크기가 작은 경우에는 작동하지 않을 수 있습니다. 또한 “큰” 또는 “작은” 배치 크기가 무엇인지는 주어진 데이터의 통계적 특성에 따라 크게 달라집니다. 이러한 문제는 실제 액티브 러닝 상황에서 문제를 발생시킵니다. 결론적으로 액티브 러닝 알고리즘은 특정 요소(모델 아키텍처, 배치 크기 또는 데이터 세트)에 한정되지 않고 일관되게 잘 작동해야합니다.

이러한 관찰을 바탕으로 저자는 불확실한과 다양성을 모두 포함하는 Batch Active learning by Diverse Gradient Embeddings (BADGE)을 제안합니다. 그러면 BADGE알고리즘이 어떻게 설계되었는지 살펴보겠습니다.

2. ALGORITHM

알고리즘 1에 대한 설명은 다음과 같습니다.

1. BADGE는 U에서 초기 M개의 예제를 균일하게 무작위로 추출하고 그들의 레이블을 요청함으로써 시작합니다.
2. 그런 다음 각 단계에서 두 가지 주요 계산을 수행하여 반복적으로 진행됩니다.
   1. 각 단계 t에서 모든 x에 대해 현재 모델에 의해 예측된 레이블 yˆ(x)를 계산합니다.
   2. 네트워크의 마지막 레이어의 매개변수에 대한 (x, yˆ(x))의 손실에 대한 그라디언트 gx를 계산합니다.
3. 이러한 그라디언트 임베딩 벡터 {gx : x ∈ U}가 주어지면 BADGE는 k-MEANS++ 초기화 방법을 통해 포인트 세트를 선택합니다 (Arthur 및 Vassilvitskii, 2007).
4. 알고리즘은 이러한 예제의 레이블을 쿼리하고 모델을 재학습하며 반복합니다.

이제 이러한 주요 계산, 즉 임베딩 및 샘플링 단계에 대해 자세히 알아보겠습니다.

The gradient embedding

딥러닝 모델의 학습은 그라디언트 기반 방법을 사용하여 최적화되므로 저자는 그라디언트의 관점에서 데이터에 대한 불확실성을 측정합니다. 예를 들어 loss값의 그라디언트가 크다면 이는 모델의 파라미터의 변화가 크게 일어나야한다는 것을 의미하고 이는 예제에 대해 불확실하다고 판단합니다.

하지만 이러한 방법을 적용시키기에는 어려움이 있는데 AL은 unlabeled pool에 대해 예측을 하기 때문에 true label을 모른다는 것입니다. 따라서 하나의 트릭으로 현재 모델이 예측한 레이블이 실제 레이블인 것처럼 가정을 하고 그라디언트를 계산합니다.

이러한 가정을 통해 가상의 그라디언트를 구하고 이의 벡터 길이를 구하게 되는데 만약 모델이 예측값을 확신한다면 예제의 그라디언트는 작은 벡터 길이를 가질 것이고 모델이 불확실한 경우 큰 벡터 길이를 가지게 될 것 입니다. 그리고 BADGE는 그라디언트의 벡터 길이를 활용해 라벨링할 데이터를 선별하게 됩니다.

The sampling step

gradient embedding 공간에서 데이터를 선별했다면 우리는 이 데이터 집합이 다양성을 가지기를 원합니다. 이를 만들 수 있는 방법에는 k-Determinantal Point Process (k-DPP; (Kulesza 및 Taskar, 2011))이 있습니다. k-DPP는 N개의 데이터가 있을때 이 중에서 k개의 적절히 분포된 데이터를 포함하는 부분집합을 선택하는 확률 모델입니다. 이 모델은 서로 다른 부분집합을 선택할 가능성을 높이고, 유사한 부분집합을 선택할 가능성을 낮추는 특징을 가지고 있습니다.

하지만 이 방법은 계산 비용과 소요 시간이 많이 들기 때문에 대신 k-MEANS++ 알고리즘(Arthur 및 Vassilvitskii, 2007)을 사용하여 샘플링하는 것을 제안합니다. 이 알고리즘은 주로 k-means 클러스터링에 좋은 초기화를 생성하기 위해 개발되었습니다. k-MEANS++ 초기화는 이미 선택된 중심으로부터의 제곱 거리에 비례하여 반복적으로 점을 샘플링하여 선택합니다. 이 방법론은 k-DPP처럼 다양한 샘플을 선택하는 경향을 보여줍니다.

위의 사진(Fig1)은 k-DPP와 k-MEANS++ 방법론을 적용시켰을 때 Accuracy와 running time을 비교한 실험입니다. 왼쪽과 오른쪽 실험 결과를 보면 성능이 거의 비슷한 것을 확인할 수 있습니다. 하지만 오른쪽 실험 결과에서는 k-DPP의 running time이 k-MEANS++에 비해 더 오래 걸리는 것을 확인할 수 있습니다.

따라서 저자는 k-DPP를 k-MEANS++로 대체하는 것을 제안합니다.

추가로 K-Means와 K-Means++ 알고리즘에 보충 설명을 하자면 다음과 같습니다.

K-Means 알고리즘

K-Means 알고리즘은 데이터를 k개의 클러스터로 분류하는 알고리즘입니다. K-Means 알고리즘은 다음과 같은 단계를 거칩니다:

1. 클러스터 수 k를 선택
2. 데이터 포인트 중 임의의 포인트를 선택
3. 각 데이터 포인트를 가장 가까운 클러스터에 할당
4. 각 클러스터의 중심을 새롭게 계산
5. 3-4 단계를 반복

K-Means 알고리즘의 문제점 K-Means 알고리즘은 초기 클러스터 중심에 민감하기 때문에 초기 클러스터 중심이 잘 선택되지 않으면 최적의 솔루션을 찾지 못할 수 있습니다.

K-Means++ 알고리즘은 K-Means의 초기 클러스터 중심에 민감한 문제를 보완한 알고리즘입니다.

K-Means++ 알고리즘

K-Means++ 알고리즘은 다음과 같은 단계를 거칩니다:

1. 첫 번째 클러스터 중심을 임의로 선택
2. 다음 클러스터 중심은 나머지 데이터들에 대해 첫 번째 centroid 까지의 거리를 각각 계산한 후에 첫 번째 centroid부터 최대한 먼 곳에 배치된 데이터를 두 번째 centroid로 지정
3. k개의 클러스터 중심을 모두 선택할 때까지 반복

위 내용을 정리하면 K-Means++ 한 번에 k개의 센트로이드를 생성하는 것이 아니라, 센트로이드 사이의 거리를 최대한 멀리 위치시키는 방향으로 1개씩 총 k번 반복하여 k개의 클러스터를 만들어내게 됩니다.

3. EXPERIMENT

저자는 BADGE의 성능을 문헌에서 제시된 여러 알고리즘과 비교합니다. 자세한 실험 셋팅은 다음과 같습니다.

1. CORESET: representative sampling(diversity sampling) 방법론
2. CONF (Confidence 샘플링): uncertainty based sampling 방법론
3. MARG (Margin 샘플링): uncertainty based sampling 방법론
4. ENTROPY: uncertainty based sampling 방법론
5. ALBL (Active Learning by Learning): hybrid sampling 방법론
6. RAND: random sampling 방법론

신경망 모델로는 MLP, ResNet(18-layer),VGG를 사용하고

이미지 데이터셋은 SVHN, CIFAR10, MNIST

비이미지 데이터셋은 OpenML repository (#6, #155, #156, and #184)를 사용합니다.

Learning curves

여기서는 배치 크기, 아키텍처 및 데이터 세트와 관련하여 액티브러닝 알고리즘의 취약성과 관련한 현상을 그래프를 통해 관찰합니다.

Fig 3a를 통해서 CORESET이 처음에는 confidence-based methods 보다 성능이 뛰어나지만 나중에는 이러한 방법보다 성능이 떨어지는 것을 보여줍니다. 이를 통해 액티브 러닝 훈련 초기에는 다양성 샘플링을 수행하는 것이 더 좋고, 훈련 후반에는 불확실성 샘플링을 수행하는 것이 더 낫다는 것을 알 수 있습니다.

Fig b 에서는 다양성을 고려한 샘플링의 경우 데이터가 쉽게 학습 가능한 경우나 모델이 학습하는 동안 특정한 아키텍처나 구조적인 특성을 선호하거나 강조하는 경향이 있는 경우에만 잘 작동하는 것을 확인할 수 있습니다. 따라서 CORESET은 컨볼루션 네트워크를 사용하지 않을 때 복잡한 데이터셋에서 random sampling 방법론을 적용시켰을 때보다 성능이 나쁘게 나오는 것을 확인할 수 있습니다.

하지만 BADGE의 경우 다양성과 불확실성을 모두 고려하기 때문에 Fig3의 결과에 나와있는 것처럼 어떤 모델을 사용하든 또는 어떤 batch size를 사용하든 높은 성능을 달성함을 확인할 수 있습니다.