딥러닝 모델은 많은 라벨 데이터를 필요로 한다. 하지만 실제 현장에서는 라벨링 비용이 크다.
의료 영상처럼 전문가가 직접 라벨을 달아야 하는 경우에는 수천, 수만 개의 라벨을 확보하기 어렵다.
이때 등장하는 방법이 Active Learning이다.
Active Learning의 목표는 간단하다.
라벨링 예산이 b개뿐이라면, 어떤 b개의 데이터를 라벨링해야 모델 성능이 가장 좋아질까?
기존 Active Learning은 주로 두 가지 원칙을 따른다.
- 모델이 헷갈려 하는 샘플을 고르는 uncertainty sampling이다.
- 데이터 분포를 다양하게 대표하도록 샘플을 고르는 diversity sampling이다.
하지만 문제는 very low-budget regime에서 발생한다.
라벨 예산이 클래스 수와 비슷하거나 그보다 조금 많은 수준이라면, 모델은 아직 충분히 학습되지 않았기 때문에 uncertainty 자체를 신뢰하기 어렵다.
논문 Active Learning Through a Covering Lens는 이 문제를 해결하기 위해 Active Learning을 “coverage”, 즉 데이터 공간을 얼마나 잘 덮는가의 관점에서 다시 정의한다.
이 논문이 제안하는 핵심은 라벨링할 샘플은 embedding 공간에서 주변의 많은 샘플을 대표할 수 있어야 한다는 것이다.
자기지도학습으로 얻은 embedding 공간에서는 의미적으로 비슷한 이미지들이 가까이 모인다.
예를 들어 고양이 이미지는 고양이 이미지끼리, 자동차 이미지는 자동차 이미지끼리 가까운 위치에 놓일 가능성이 높다.
그렇다면 어떤 샘플 하나를 라벨링했을 때, 그 주변의 가까운 샘플들도 같은 라벨일 가능성이 높다.
입력 공간을 $X$, 데이터 분포를 $P$, 라벨 함수는 $f: X \rightarrow Y$라고 하자.
라벨링 예산은 $b$개 이고, 선택된 라벨 집합을 $L$이라고 하자.
각 선택 샘플 $x \in L$ 주변에 반지름 $\delta$인 ball을 만든다.
$$B_\delta(x)=\{x':||x'-x||_2 \le \delta\}$$
선택된 샘플들이 덮는 영역은 다음과 같다.
$$C(L,\delta)=\cup_{x\in L} B_\delta(x)$$
ProbCover는 이 덮인 영역의 확률 질량을 최대화하려고 한다.
$$\text{argmax}_{L \subseteq X; |L|=b} P(\cup_{x\in L} B_\delta(x))$$
즉, 제한된 개수의 라벨 샘플로 데이터 분포에서 가능한 한 많은 영역을 덮는 것이 목표다.
논문은 1-NN classifier를 이용해 이 아이디어를 이론적으로 설명한다.
1-NN은 어떤 테스트 샘플이 들어오면, 라벨링된 샘플 중 가장 가까운 샘플의 라벨을 그대로 예측한다.
이때 중요한 개념이 $\delta-\text{purity}$다.
어떤 점 $x$를 중심으로 한 ball $B_\delta(x)$ 안의 모든 점이 $x$와 같은 라벨을 가진다면, 이 ball은 pure하다고 한다.
$B_\delta(x)$가 pure ↔ 모든 $x'\in B_\delta(x)$에 대해 $f(x')=f(x)$
그리고 $\delta$의 puritya를 다음처럼 정의한다.
$$\pi(\delta)=P({x:B_\delta(x) \text{ is pure}})$$
$\delta$가 작으면 가까운 점들만 포함하므로 purity가 높다.
반대로 $\delta$가 커지면 더 많은 점을 덮지만, 서로 다른 클래스가 섞일 가능성이 커져 purity가 낮아진다.
논문은 1-NN classifier의 일반화 오차를 다음과 같이 측정한다.
$$\mathbb{E}\left[\hat f(x)\neq f(x)\right]\le (1-P(C(L,\delta))+(1-\pi(\delta))$$
첫 번째 항은 선택된 라벨 샘플들이 덮지 못한 영역이다.
coverage가 클수록 이 항은 작아진다.
두 번째 항은 덮인 영역 안에서도 라벨이 섞여 있을 위험이다.
purity가 높을수록 이 항은 작아진다.
따라서 $\delta$를 적절히 정해 purity를 유지하면서, 선택된 샘플들이 가능한 한 많은 확률 질량을 덮도록 해야 한다.
이 논문에서는 ProbCover와 Coreset의 차이를 dual하게 설명한다.
Coreset은 다음 목표를 가진다.
$$\delta(L)=\text{max}_{x\in X} \text{min}_{c\in L} d(x, c)$$
전체 데이터를 반드시 덮는다고 가정하고, 필요한 최대 반지름을 최소화한다.
이는 high-budget regime에서는 합리적이다.
라벨 예산이 충분히 크면 전체 데이터 분포를 골고루 덮을 수 있기 때문이다.
반면 low-budget에서는 전체 데이터를 덮으려는 시도가 오히려 문제가 된다.
예산이 너무 작기 때문에 전체 분포를 억지로 덮으려 하면, Coreset은 데이터 외곽의 outlier나 희소한 영역을 선택하기 쉽다.
Coreset은 적은 예산에서 분포의 끝점들을 선택하는 반면, ProbCover는 고밀도 영역의 대표 샘플을 선택한다.
정리하자면,
- Coreset은 전체를 덮되 반지름을 최소화한다.
- ProbCover는 반지름을 고정하고 덮는 확률 질량을 최대화한다.
low-budget에서는 후자가 더 적합하다.
모든 영역을 조금씩 건드리기보다, 실제 데이터가 많이 몰려 있는 대표 영역을 먼저 라벨링하는 것이 더 효과적이기 때문이다.
알고리즘
실제 데이터 분포 $p$는 알 수 없으므로, 논문은 empirical distribution을 사용한다.
이 경우 Max Probability Cover는 고전적인 Max Coverage 문제로 바뀐다.
데이터 포인트들을 임베딩 공간에 놓고, 각 점을 노드로 본다.
두 점의 거리가 $\delta$ 이하이면 edge를 만든다.
$$(x,x')\in E \Leftrightarrow d(x, x') \le \delta$$
이때 어떤 노드의 out-degree는 그 샘플을 선택했을 때 덮을 수 있는 데이터 수를 의미한다.
ProbCover는 다음 과정을 반복한다.
- 아직 덮이지 않은 점들을 가장 많이 덮는 샘플을 선택한다.
- 그 샘플이 덮은 점들을 graph에서 제거한다.
- 예산 $b$개를 다 쓸 때까지 반복한다.
Max Coverage는 NP-hard 문제지만, greedy 알고리즘은 submodular maximization의 성질 때문에 $1 - 1/e$ 근사 보장을 갖는다.
최적해를 정확히 찾기는 어렵지만, greedy하게 골라도 이론적으로 강한 근사 성능을 보장할 수 있다.
$\delta$는 어떻게 정하는가?
ProbCover에서 가장 중요한 하이퍼파라미터는 ball radius $\delta$다.
$\delta$가 너무 작으면 purity는 높지만 cverage가 낮다.
선택한 샘플 하나가 거의 자기 자신만 대표하게 된다.
$\delta$가 너무 크면 coverage는 높지만 purity가 낮다.
서로 다른 클래스가 한 ball 안에 섞이면서 잘못된 라벨 전파가 일어날 수 있다.
논문은 이를 해결하기 위해 purity threshold $\alpha$를 사용한다.
$$\delta^\ast=\text{max}\{\delta: \pi(\delta) \ge \alpha\}$$
purity가 일정 수준 이상 유지되는 가장 큰 \delta를 선택한다.
실험에서는 $\alpha=0.95$를 사용했다.
하지만 실제 라벨은 아직 없기 때문에 true purity를 계산할 수 없다.
그래서 논문은 self-supervised feature를 k-means로 clustering하고, cluster label을 pseudo-label처럼 사용해 purity를 추정한다.
이는 ProbCover가 라벨 없이도 작동할 수 있게 만드는 중요한 장치다.
실험 결과
논문은 CIFAR-10, CIFAR-100, Tiny-ImageNet, ImageNet 등 여러 이미지 분류 데이터셋에서 ProbCover를 평가한다.
실험은 크게 세 가지 설정에서 진행된다.
첫째, fully supervised setting이다.
선택된 라벨 데이터만으로 ResNet-18을 학습한다.
둘째, self-supervised embedding 기반 1-NN setting이다.
자기지도학습으로 얻은 embedding에서 선택된 라벨 샘플을 기준으로 nearest neighbor classification을 수행한다.
셋째, fully semi-supervised setting이다.
선택된 라벨 데이터와 전체 unlabeled data를 함께 사용해 FlexMatch를 학습한다.
결과적으로 ProbCover는 low-budget regime에서 대부분의 baseline보다 우수한 성능을 보인다.
ProbCover는 Active Learning을 “어떤 샘플이 가장 불확실한가”가 아니라 “어떤 샘플이 가장 많은 데이터를 대표하는가”로 바라본다.
Low-budget active learning에서는 outlier를 찾는 것보다, 데이터 분포의 고밀도 영역을 잘 덮는 대표 샘플을 고르는 것이 중요하다는 인사이트를 준다.