이번에도 Active Leaning 관련 리뷰입니다.

저는 최근 몇 주동안 Active Learning 논문에 대해 리뷰를 작성하였습니다.

Active Learning 이란 Unlabeled Data에서 사람이 반드시 라벨링을 해야하는 데이터를 찾는 법에 대한 연구입니다.

라벨링할 데이터를 찾는 방식은 여러 분야가 있는데요, 크게 Uncertainty (정보량, 표현력 이라고도 함)와 Diversity 기반의 Active Learning으로 나눌 수 있습니다.

- Informative: 쿼리하는 인스턴스는 정보력을 가져야 한다.
								-> 모델이 판단하기 어려운 데이터를 의미하기도 함
- Diversity: 쿼리하는 인스턴스는 서로 분별된 정보를 가지고 있어야 한다.
								-> 전체 데이터를 대표할 만한 다양성을 가지는 데이터의 집합을 의미하기도 함

제가 그동안 x-review 로 작성한 논문들을 살펴보니, 나름대로 순차적으로 두 개의 큰 흐름을 공부해보고자 엑스 리뷰를 작성했던 것 같습니다.

1. heuristic 한 Uncertainty 기반의 대표적인 몇 가지 방법론에 대하여 – [ICLR 2018] Active learning for convolutional neural networks: A core-set approach – (Part 1)
2. Diversity 기반으로 CNN에 최적화된 Active Learning : Core-set – [ICLR 2018] Active learning for convolutional neural networks: A core-set approach – (Part 2)
3. Diversity 와 Uncertainty 를 모두 고려한 Hybrid 기반의 Active Learning – [arXiv 2019] Diverse mini-batch Active Learning

제가 이번에 리뷰할 논문은 바로 직전에 리뷰한 방법과 동일한 Hybrid 기반의 방법론입니다. 사실 처음 AL을 읽으면서 자연스럽게 두 가지 흐름을 모두 고려하는 방법은 없을까 생각했는데 역시나 진행중이더군요. 과연 어떻게 적용하였는지를 중심으로 논문을 리뷰해보도록 하겠습니다.

참고로 아래 그림을 통해 두 가지 모두를 고려하였을 때의 샘플링 결과를 확인할 수 있습니다. 즉, 두 가지를 고려하였을 때 대표적이면서도 비슷하지 않은 샘플들을 효율적으로 선정하 수 있는 것이죠.

---

Deep Batch active Learning by Diverse, Uncertain Gradient Lower Bounds – [바로가기]

해당 논문은 제가 기존에 리뷰한 논문과 동일하게 배치 기반의 쿼리 방식을 제안합니다. 우리가 전형적으로 생각하기 쉬운 AL은 보통 데이터 샘플 하나하나 단위로 평가하여 순위를 매겨 뽑는 것일것입니다. 앞서 언급한 휴리스틱 기반 쿼리 방식이 그런 경우죠. 그러나 딥러닝은 배치 단위로 학습이 되는데다 분포를 배우는 것이기 때문에 개별 데이터 뿐만 아니라 데이터의 조합이 가지는 정보가 중요하기 때문에 배치 기반의 쿼리 방식이 필요하였습니다.

Introduction

Uncertainty 기반의 방법론은 정보량이 많지만 비슷한 샘플들만 쿼리되는 문제가 있고, Diversity 기반의 방법론은 새로운 정보는 제공하지 않는 문제점이 있습니다.

이런 이유로 둘 중 하나에만 기반하는 모델은 Backbone / batch size / Dataset 마다 일관되지 않고 상이한 성능을 내기 마련입니다. 배치 사이즈의 경우 보통 데이터셋이 크고 다양하면서 배치 사이즈가 커야 좋은 성능을 가지기는 하지만, 데이터에 의존하는 통계적 속성이기에 어떤 값이 가장 좋은지는 결국 실험적이라는 한계가 있습니다. 마지막으로 hyperparameter마다 샘플링되는 데이터가 다르다는 문제도 있습니다.

따라서 본 논문에서는 효과적인 배치 기반의 쿼리 방식을 제안하고자 Uncertainty 를 기반으로 Diversity까지 고려할 수 있는 방식을 제안합니다.

그렇다면 정말 두 방식을 모두 통합되는지, 그리고 어떻게 적용하였는지에 대해 알아보도록 하겠습니다.

Algorithm

본 논문에서 제안하는 BADGE(Batch Active learning by Diverse Gradient Embedding) 알고리즘은 데이터를 hallucinated gradient space 에 표현하여 이질적이고 높은 크기의 포인트 그룹을 샘플링하는 방식입니다. 이 방식은 Uncertainty와 Diversity를 모두 선택된 모든 배치에 통합하도록 설계된 방법론이라고 합니다.

다시 설명하자면, 마지막 레이어(output)의 매개 변수에 대한 Uncertainty는 gradients magnitude로 측정하고, 그와 동시에 Diversity 역시 계산하기 위해 앞서 구한 gradients의 다양한 방향 집합에 걸쳐 있는 데이터를 선정합니다. 아래 알고리즘을 통해 각 단계별로 설명드리도록 하겠습니다.

본 논문이 제안하는 알고리즘 BADGE (Batch Active learning by Diverse Gradient Embeddings)

1. 초기 학습을 위한 라벨링된 데이터를 U (unlabeled dataset) 에서 S개 만큼 uniformly random 하게 추출
2. 라벨링이 있는 S개의 데이터로 분류 모델 학습
3. 이제 T번동안 데이터를 선별하여 쿼리하는데, 데이터를 선별하는 과정마다 두 가지(gradient embedding computation, sampling computation) 주요 계산이 반복적으로 진행됩니다.
4. 모든 x는 unlabeled 데이터 U에 포함되며,
   1. 먼저 2번째 단계에서 학습한 모델로부터 x에 대한 예측값 \hat{y}(x) 를 계산한다
   2. 이후, 마지막 레이어의 파라미터에 대한 gradient embedding인 g_x를 계산합니다.
5. t번째에서 선택한 라벨링할 데이터 S_t 를 구하고, K-means++ 초기화 방식을 통해 샘플링할 포인트 집합을 선택합니다.
6. t번째 단계에서 선택한 t개의 라벨링 데이터와 기존 초기 라벨링한 데이터를 합쳐서
7. t+1번째에 대한 분류 모델을 학습합니다.
8. for 문이 끝날 대 까지
9. 즉, T번째의 쿼리가 끝난 후, T번째의 모델 학습이 끝나면 완료됩니다.

The Gradient Embedding?

저자는 먼저 deep neural network는 gradients 기반 방법을 사용하여 최적화되기 때문에 gradients를 통한 uncertainty를 계산하였다고 합니다. 특히, 저자는 레이블을 아는 것이 모델 매개 변수와 관련하여 loss의 큰 gradients를 유발하여 모델에 대한 큰 업데이트를 발생시키는 경우에, 해당 예시에 대해 모델이 불확실하다고 생각하였다고 합니다. 그러나 여기서 문제는 데이터의 라벨을 알아야 한다는 것입니다. 따라서 앞서 라벨링있는 데이터로 학습한 모델의 예측값을 정답값으로 가정하여 gradients를 계산하였습니다.
gradients embedding은 한 example에서 레이블을 받을 때 모델의 uncertainty와 잠재적인 업데이트 방향에 대한 정보를 모두 전달합니다.

The sampling step?

AL은 가능한 적은 샘플링 데이터만으로 모델에 크고 다양한 변화를 가져오길 원하는 방법론인데요, 이를 위해 저자는 표본 크기(sample magnitude)와 배치 다양성(batch diversity) 모두에 유리한 데이터 샘플링 방식을 제안합니다. 추가적인 하이퍼 파라미터 없이 이를 선택하기 위해 도입한 방법은 k-Determinantal Point Process (k-DPP; (Kulesza and Taskar, 2011)) 입니다. 이는 Gram 행렬의 결정 요인에 비례하는 확률을 갖는 k개의 점 배치를 선택하는 방식입니다.

… 참고로 k-DPP에 대해서 아래에 간단하게 찾아보았는데요 .. 이는 제가 추후 보충해야 할 것 같습니다.. 혹시 이에 대해 아시는 분이 있으면 댓글로 알려주시거나 추천할 서적 및 자료가 있다면 남겨주시기 바랍니다. (그분에게는 압도적 감사를..)

k-DPP란?

예를 들어 N개의 데이터가 있을 때, 이 중 k개의 적절히 분포된 데이터를 고르고 싶다고 합시다(딱 지금과 같은 상황이네요).
이 때, 단순히 k개를 uniform하게 뽑는 것은 그리 좋은 방법이 아니라고 합니다. 이런 경우에 사용될 수 있는 것이 “k-DPP”라고 합니다. 

어떤 Discrete set Y = \{ 1, 2, ..., N\} 에 정의된 k-DPP는 k의 cardinality를 같은 set y \subseteq Y의 확률이고, 다음과 같이 정의됩니다.

P_L^k(Y) = \frac{det(L_Y)}{\sum_{|Y'| = k}det(L_{Y'})}

…

아무튼 다시 본론으로 돌아가자면 문제는 k-DPP로 정의할 수는 있지만 k-DPP에서 표본을 추출하는 것은 쉬운 일은 아닙니다. 계산 복잡도와 소요 시간이 매우 많다는게 이유인데요, 이 원인에 대해서느 제가 조금 더 공부한 이후에 core-set 논문과 함께 수식적인 내용을 보강하여 작성해보도록 하겠습니다.

따라서 결론부터 말하자면 저자는 이런 계산의 어려움 극복하기 위해 k-MEANS++ 알고리즘을 사용하여 샘플링을 제안합니다. k-MEANS++ 는 가장 가까운 중심에서 제곱 거리에 비례하여 점을 반복적으로 샘플링하여 중심점을 선택하는 방법론입니다. K-Means++인 것을 보면 K-means에서 조금 발전한 것 같은데, 그럼 이건 무슨 차이가 있느냐!
그건 바로 K-means 에서의 가장 첫번째 단계인 중심점을 배치하는 과정을 랜덤하게 배치하는 것이 아닌, 다른 방법을 채택하였다는 것입니다.

K-means++ ?

1. 가지고 있는 데이터 포인트 중에서 랜덤하게 1개를 선택하고 이를 첫번째 중심점으로 선택
2. 나머지 데이터 포인트들에 대해 그 첫번째 중심점까지의 거리를 계산
3. 두번째 중심점은 각 점들로부터 거리비례 확률에 따라 선택한다. 즉, 이미 지정된 중심점으로부터 최대한 먼 곳에 배치된 데이터포인트를 그 다음 중심점으로 지정한다.
4. 중심점이 k개가 될 때까지 2, 3번을 반복한다. (기존 K-means 와 동일)

Experiments

• 초기 라벨링 데이터 개수 M = 100
• 배치 사이즈는 {100, 1000, 10000}로 변화

실험을 통해 비교하는 방법론 리스트

1. CORESET: 배치 기반의 Diversity 방법론
2. CONF (Confidence Sampling): 휴리스틱한 Uncertainty 기반 방법론 (1)
3. MARG (Margin Sampling): 휴리스틱한 Uncertainty 기반 방법론 (2)
4. ENTROPY: 휴리스틱한 Uncertainty 기반 방법론(3)
5. ALBL (Active Learning by Learning): 매 라운드마다 CORESET과 CONF 사이에서 선택하는 메타 학습 방법론
6. RAND: 랜덤 선택

실험 데이터는 CIFAR-10, SVHN, MNIST 와 같은 이미지 데이터 말고도 OpenML과 같은 비이미지 데이터도 포함됩니다.

위 결과를 통해 초기 학습에서는 다양성 샘플링을 쿼리하고, 이후에는 불확실성 기반의 샘플링을 수행하는 것이 더 낫다는 것을 알 수 있습니다. 왜냐하면 다양성 기반의 방법론인 CORE-SET이 처음에는 불확실성 기반의 방법론인 conf. 보다 뛰어나지만 쿼리가 반복될 수록 성능이 떨어지는 것을 통해 그러한 분석을 도출해냈다고 합니다.

이와는 별도로, 다양성기반 샘플링은 모델에 inductive biases가 있거나 전체 데이터의 분포를 알아차리기 쉬운 경우에만 좋은 성능을 낸다고 합니다. 이러한 이유로, (그림 3b)를 통해 CORESET은 컨볼루션 네트워크를 사용하지 않을 때 충분히 복잡한 데이터에서 Rand. 보다 성능이 떨어지는 경우가 있다는 것을 확인할 수 있었습니다. 즉, 무조건적인 랜덤 표본 추출에 의해 유도된 다양성은 종종 데이터를 더 잘 나타내는 배치를 생성하기도 한다는 것이죠. 배치 크기가 크고 모델에 유용한 inductive biases이 있는 경우에도, BADGE의 불확실성 정보는 다양성만 고려한 방법로에 비해 오히려 좋은 성능을 제공하기도 합니다(그림 3c).

---

이전부터 Active Learning의 내용을 온전히 이해하는 데에는 어려움이 있었습니다. 빠른 시일내에 이를 이해하고자 다양한 논문과 수식적인 공부를 해야할 것 같습니다.