[ICLR 2018] Active learning for convolutional neural networks: A core-set approach – (Part 2)

[1] [Active Learning] A core-set approach (Part 1)

지난주 리뷰에서는 본 논문을 이해하기 위한 배경 지식에 대해 간단히 다뤄보았습니다. 따라서 본 리뷰를 읽기 전 Part 1 을 읽어보시는 것을 추천드립니다!

---

Active learning for convolutional neural networks: A core-set approach

Introduction

CNN은 지금까지 다양한 분야에서의 성과를 보였지만, 많은 양의 데이터가 필요하다는 단점이 있습니다. 데이터가 커질 수록 그와 비례하여 레이블링에 필요한 시간과 비용이 커지게 됩니다. 따라서 Part 1 에서 언급했던 것처럼 Active Learning (이하 AL) 에서는 가장 큰 성능 향상을 가져오는 데이터를 골라 레이블링하여 기존보다 효율적으로 레이블링하는 법에 대해 다루게됩니다.

그러나 기존 Active Learning 에 사용되던 Heuristics 한 방법론들은 CNN에 적합하지 않다고 합니다. 왜냐하면, 앞서 알아본 기존 방법들은 대부분 Instance 단위로 데이터를 쿼리하는데, 배치 단위로 학습하는 CNN 에 이 방법을 사용하는 것(하나씩 쿼리하는 것)은 비효율적이기 때문입니다.

따라서 본 논문에서는 Active Learning을 Label 정보가 필요한 Uncertainty 대신 CNN의 Feature 를 사용하여, 데이터 전체를 대표할 수 있는 Core-set Selection 문제로 새로 정의합니다. 여기서 이 Core-set만을 사용하여 모델을 학습시킨 성능이, 전체데이터를 사용한 성능과 거의 비슷할 정도로 전체 데이터를 대표하는 작은 데이터 집합을 Core-set 이라고 합니다.

Problem Definition

본 논문에서는 Active Learning을 Core-set Selection 문제로 접근합니다.

Active Learning의 목적은 레이블링된 초기 데이터셋S_0이 있을 때, 새로 선택한 데이터셋 S_1 을 통해 Future Expected Loss를 줄이는 것입니다. 다시 말해 S^1이 추가되었을 때의 전체 기대 에러를 최소화하는 방향의 S^1 데이터셋 고르기가 이 문제의 핵심입니다.

그리하여 상단 Future Expected Loss 식을 아래로 일반화할 수 있습니다.;

한 iteration에서 AL은 크게 (1) 데이터 셋을 고르고 레이블링 요청(query) (2) 레이블링된 데이터와 기존 학습데이터를 합쳐 다시 모델 학습; 이 두 단계로 나뉘어집니다. 본 논문에서는 두번째 단계를 Fully-Supervised 또는 Weakly Supervised 방식으로 수행합니다. (기존 방법들은 Fully에만 집중했지만, 본 논문에서는 Weakly에 대한 실험도 진행합니다.)

Method

Active Learning as a Set Cover

그렇다면 본 논문에서는 어떻게 Active Learning을 Core-Set Selection 문제로 풀 수 있었을까요? 지금부터는 어떻게 Core-Set Selection으로 재정의가 가능한지에 대해 알아보도록 하겠습니다.

기존 AL 에서는 Oracle(인간 어노테이터: 라벨링해주는 사람)에게 하나씩(b=1) 쿼리하여 레이블을 한 개씩 얻게됩니다. 그러나 CNN의 경우, 하나의 포인트로는 local optimization 알고리즘으로 인해 모델에 통계적으로 유의미한 영향을 주지 않습니다. 또한 practical problem of interest가 매우 크기 때문에, 데이터 수만큼 모델을 학습하는 것은 불가능합니다. 따라서 적절한 크기의 데이터셋을 선택하는 Batch Active Learning 에 집중합니다.

저자는 배치설정에 효과적인 AL을 설계하기 위해 문제를 정의한 후 아래와 같이 Upper Bound를 고려한 솔루션을 제안합니다.
즉, 왼쪽 항(앞서 살펴본 최소화하고자 설정한 Error)을 오른쪽 항으로 풀어서 서술할 수 있는데, 이 모든 에러의 합보다 작거나 같다는 Upper Bound 를 고려한 것입니다.

equation 1에서 본 Future Expected Loss는 위와 같이 분리시킬 수 있습니다. 여기서 Training Error와 Generalization Error는 CNN의 높은 표현력으로 인해 0이라고 가정할 수 있다고 합니다. (이미 CNN 모델들이 Generalization 능력이 좋다는 것이 증명된 논문들이 많고, Training 에러 역시 충분히 작게 만들 수 있기 때문) 따라서 Future Expected Loss는 Core-set Loss만 고려하게 됩니다.

• Generalization Error: over the full dataset ([n])
  ( 전체 모수에 대한 Expected Error와 n개에 대한 Expected Error의 차이 )
• Training Error: the model on the labelled subset
  ( 알고있는 training set 에 대한 Error )
• Core-set Loss: Critical Part for Active Learning

이로 인해 Core-set Loss를 재정의하면 식은 아래와 같이 변환이 되고, 이 식의 의미는 곧 Subset에서의 모델 성능과 전체 데이터셋에서의 성능 차이를 최소화하는 문제로 해석할 수 있게 됩니다.

아래 그림이 바로 본 논문을 대표하는 그림입니다.

즉, Core-set을 찾기 위해서는 위 그림에서 빨간색의 데이터 샘플은 모두 Cover 할 최적의 거리 δs를 구하고, 그에 해당하는 Core-point인 파란 데이터 샘플을 찾아야합니다. 따라서 이 δs를 최소화하는 방법에 대해 문제로 전환되게 됩니다.

여기서 계속 궁금한 것이 생기는데 그렇다면 거리는 어떻게 측정을 할까요?
이미지 데이터에서 거리를 측정하는 것이 아닌, Feature Vector 단에서 거리를 측정하는 것입니다.

SOLBING THE K-CENTER PROBLEM

δs를 최소화하는 방법에 대해 문제(Core-set 문제를 해결하기 위해서)는 K-Center (also called min-max facility location problem) 문제와 동일합니다.

쉽게 말해 데이터와 가장 가까운 센터 사이의 거리 중 가장 긴 값을 최소화하는 센터 b를 고르는 문제입니다. 이를 수식으로 정리하면 아래 eq.5와 같습니다.

그러나 아무런 조건이 없는 k-center problem을 해결하기 쉽지 않습니다. 이 문제는 *NP-Hard 이기 때문에 일반적인 접근으로는 풀 수 없고, greedy 방법을 사용한 **2-OPT solution을 통해 접근할 수 있습니다. 이렇게 얻게된 그 결과는 실제 Optimal Minimum의 2배보다는 작게 나온다고 합니다.

이번 문제에서 해결해야하는 것은 가장 큰  δs를 줄이는 것입니다. 그런데 이  δs 가 어떤 값이어야만 아래 우리가 원하는 제약식을 모두 만족시킬 수 있는지는 알 수가 없습니다. 그렇기 때문에 이를 쉽게 해결하기 위해 Upper bound와 Low bound를 정하고, 이를 계속 업데이트 하면서 이 사이 간격을 줄이다 Upper/Low가 같아지는 순간의 값이 최소가 되는 점이라고 가정하게 되는 것이며 이 것을 optimize solution이라 생각하여 반환하는 방식으로 문제를 해결하고 있습니다.

1. Outlier 를 고려
2. 몇 가지 제한사항과 Lower Bound를 추가

• u_j: 선택받은 core-set
• Ξ : 선택이 안된 데이터에 대한 제약 (모두를 커버하지 않아도 된다는 의미의 제약식, 조금 더 robust 하도록)
• w_i,j: 커버가 된 것에 대한 제약식

• 모든 data point들은 하나의 center에게 커버
• 초기 Lower bound는 Upper bound의 1/2 
• 초기 Upper bound는 maxjminj∈SgΔ(xi,xj) 
• Feasible 조건 만족 시, Upper bound를 낮춤
• Feasible 조건 불만족 시, Lower bound를 낮춤
• Upper bound와 Lower bound가 같을 때 ( 최적의  δs )까지 반복
• 최적의  δs 기반으로, Center node 추출
  • ※ 실제 구현된 코드를 확인해 보니, Radius정보를 바탕으로 Graph를 탐색하여 center point를 찾는다 

EXPERIMENTAL RESULTS

CIFAR-10, CIFAR-100, Caltech-256, SVHN 데이터 셋에 대한 실험으로 본 방법론 과 기존 방법들을 비교합니다.

여기서 기존 방법이라고 함은 아래와 같습니다

1. Random : Un-labeled Pool에서 랜덤으로 Uniform하게 라벨링할 데이터 선택
2. Best Empirical Uncertainty
3. Deep Bayesian Active Learning (DBAL)
4. Best Oracle Uncertainty
5. k-Median
6. Batch Mode Discriminative-Representative Active Learning
7. CEAL: CNN을 위해 제안된 weakly-supervised active learning

Our Method 에서는 Fully-Supervised 와 Weakly-Supervised 둘다 실험을 수행합니다.

또한 앞서 계속 설명하였듯, 라벨이 있는 초기 데이터셋은 랜덤하고 uniform하게 샘플링하여 시작합니다.

Weakly Supervised 모델은 라벨이 없는 샘플 뿐만 아니라 라벨이 있는 샘플에서도 사용할 수 있으며,
Fully-Supervised 모델은 라벨이 있는 데이터에만 접근할 수 있습니다.

5번의 랜덤 초기화로 실험을 진행하였으며, 평가 메트릭으로는 average classification accuracy를 사용하였습니다.

정확도에 대한 레이블링된 점의 수를 plot한 실험 결과는 아래와 같습니다.
모든 실험에서 다른 방법론들에 비해 훨씬 높은 성능을 보인다는 것을 확인할 수 있습니다.특히 Weakly-Supervised 실험에서 훨씬 높은 성능을 가지는데, 이는 본 방법론이 “Geometric” 하기 때문에 더 나은 Feature Space 갖기 때문이라고 합니다.

그러나 CIFAR-10 과 SVHN에 비해 CIFAR-100 과 Catlech-256에서는 덜 효과적이었는데, Core-Set Loss에 대한 Bound는 Class에 따라 확장되기 때문에 더 적은 class를 갖는 데이터셋에서 효과적임을 이론적으로 분석할 수 있었습니다.

뿐만 아니라 정성적 평가를 위해 TSNE를 시각화하였는데, 이를 통해 샘플 간의 상관관계에 대한 Uncertainty 기반 방법론보다 자신들의 방법론이 어느 한 쪽에 치우치지 않고 균일한 데이터를 다룰 수 있다고 하였습니다.

(참고)

Active Learning 관점 두 가지: 

1. Uncertainty(불확실성) : 모델이 헷갈리는 데이터를 query
2. Diversity : 데이터의 분포를 커버할 수 있는 데이터 포인터 query

이런 AL 접근법들은 보통 Uncertainty와 Diversity 간의 Trade-off 관계가 있다고 합니다.

Conclusion

CNN에서의 AL 문제를 다룬 논문입니다.
기존 Uncertainty 기반 방법론이 배치 샘플링에 의한 상관관계로 인해 CNN에 대한 적합하지 않음을 보이고,
AL 문제를 Core-set Seleection 문제로 재구성하여 CNN의 Core-set 문제를 다뤘습니다.

---

본 논문을 간단하게 정리하면 AL 방법 중 Diversity(다양성)에 관점에서 딥러닝 모델을 활용한 연구입니다. Active Learning 에 딥러닝을 직접 적용한 모델이라고 하여 읽어보았지만, 내용을 풀어가는 데에 있어서 근사 알고리즘/최적화 문제에 가까워서 이해에는 어려움이 있었습니다. 그러다 보니 완벽하게 이해하는데에 어려움이 있어 나아가 서술하는 것까지 설명이 부족하지 않았나 생각이 듭니다. 그리고 이로 인해 디테일한 부분은 제대로 다루지 못한 것 같습니다. 그래도 이번 기회에 Active Learning에 대해 아주 조금 알아갈 수 있었네요.