Active Learning의 목표는 전체 데이터에 라벨을 다는 대신, 모델 학습에 가장 도움이 될 샘플만 골라 라벨링 비용을 줄이는 것이다.
라벨 예산이 작을 때는 불확실한 샘플보다, 전체 데이터 분포를 잘 대표하는 샘플을 고르는 것이 더 중요하다.
이 관점에서 기존 연구 ProbCover는 매우 자연스러운 아이디어를 제안했다.
선택된 라벨 샘플들이 전체 데이터 분포를 얼마나 잘 “덮고 있는지”를 최대화하자는 것이다.
하지만 ProbCover는 coverage를 정의할 때 사용하는 반경 ($\delta$)에 성능이 민감하다.
이 논문은 이 문제를 해결하기 위해 ProbCover의 coverage 개념을 더 일반적이고 부드러운 형태로 확장한다.
그리고 이를 효율적으로 최대화하는 greedy 알고리즘인 MaxHerding을 제안한다.
알고리즘
hard threhsold 기반 coverage를 더 일반적인 형태로 확장한 것으로, 핵심 정의는 다음과 같다.
$$C_k(\mathcal{L})=\mathbb{E}_x \left[\text{max}_{x'\in\mathcal{L}} k(x, x')\right]$$
여기서 $k(x,x')$는 두 데이터 포인트 사이의 유사도를 나타내는 함수로, Gaussian kernel을 사용할 수 있다.
$$k(x,\tilde x)=\text{exp}\left(-\frac{1}{2\sigma^2} ||x-\tilde x||^2\right)$$
어떤 데이터 $x$에 대해, 라벨 샘플 집합 $\mathcal{L}$ 중 가장 유사한 샘플과의 유사도를 coverage로 본다.
그리고 전체 데이터 분포에 대해 이를 평규낸 것이 generalized coverage이다.
즉, $C_k(\mathcal{L})$가 크다는 것은 대부분의 데이터가 적어도 하나의 라벨 샘플과 충분히 유사함을 의미한다.
ProbCover의 coverage는 $k$를 top-hat 함수로 둔 경우이다.
MaxHerding은 ProbCover의 1-NN 오류를 다음과 같이 일반화한다.
$$\text{Pr}_x(f(x)\ne \hat f(x))\le \left(1-\mathbb{E}_x\left[\text{max}_{x'\in\mathcal{L}} k(x,x')\right]\right)+\mathbb{E}_x\left[\text{max}_{x':x'(x)\ne f(x')} k(x,x')\right]$$
첫 번째 항은 generalized coverage의 보수다.
$1-C_k(\mathcal{X})$로, 선택된 라벨 샘플들이 전체 데이터 분포를 충분히 잘 덮지 못하면 오류가 커질 수 있다.
두 번째 항은 kernel 기반 impurity다.
$x$와 label이 다른 점들 중 $x$와 유사한 점이 많다면, 그 근방은 decision boundary에 가까울 가능성이 높다.
이 경우 1-NN classifier는 잘못된 라벨을 가져올 수 있다.
이 bound는 좋은 라벨 샘플 집합은 generalized coverage를 크게 만들면서, label impurity가 낮은 kernel scale을 사용해야 함을 말한다.
ProbCover에서는 이 역할을 $\delta$가 했다. MaxHerding에서는 Gaussian kernel의 lengthscale $\sigma$가 비슷한 역할을 하지만, top-hat처럼 hard cutoff가 아니기 때문에 훨씬 안정적이다.
실제로는 전체 분포에 대한 expectation을 알 수 없으므로, unlabeled pool 위에서 empirical coverage를 사용한다.
$$C_k(\mathcal{L})\approx \frac{1}{N}\sum_{n=1}^N\left(\text{max}_{x'\in \mathcal{L}} k(x_, x')\right)=: \hat C_k(\mathcal{L})$$
MaxHerding은 이 값을 greedy하게 최대화한다.
현재 라벨 집합이 $\mathcal{L}$일때, 새 후보 $\tilde x$를 추가하면 coverage 증가는 다음과 같다.
$$\text{max}_{\tilde x}\left(\frac{1}{N}\sum_{n=1}^N \text{max}_{x' \in \mathcal{L}\cup\{\tilde x\}} k(x_n,x')-\frac{1}{N}\sum_{n=1}^N \text{max}_{x'\in\mathcal{L}} k(x_n, x')\right)$$
각 데이터 $x_n$에 대해 이미 기존 라벨 샘플 중 충분히 유사한 것이 있다면, 새 후보 $\tilde x$는 그 데이터에 거의 기여하지 못한다.
반대로 기존 라벨 샘플들이 잘 설명하지 못하던 데이터라면, $\tilde x$가 큰 coverage gain을 줄 수 있다.
MaxHerding은 단순히 밀도가 높은 곳을 반복적으로 고르지 않는다.
이미 덮인 영역은 무시하고, 아직 덜 덮인 영역을 가장 많이 보완하는 점을 선택한다.
MaxHerding의 목적 함수는 $g(\mathcal{S}):=\sum_{i=1}^N \text{max}_{j\in \mathcal{S}}M_{i,j}, M_{i,j}\ge 0$이다.
이 함수는 nonnegative similarity에 대해 monotone submodular function이다.
Submodular function은 직관적으로 “수확 체감” 성질을 갖는다.
즉, 어떤 샘플 하나를 추가했을 때의 이득은 이미 선택된 샘플이 많아질수록 줄어든다.
이 성질은 coverage 문제와 잘 맞는다.
아직 아무것도 선택하지 않았을 때는 중심적인 샘플 하나가 큰 coverage gain을 준다.
하지만 이미 그 주변이 덮였다면, 같은 지역에서 샘플을 하나 더 고르는 이득은 작다.
Kernel herding은 어떤 분포를 소수의 대표 샘플로 요약하는 방법이다.
선택된 샘플들의 kernel mean embedding이 전체 데이터 분포의 kernel mean embedding과 가까워지도록 샘플을 고른다.
이를 위해 현재 라벨 집합 $\mathcal{L}$에 대해 다음과 같은 max kernel을 정의한다.
$$k(x,\tilde x; \mathcal{L}):=\text{max}\{k(x,\tilde x)-\text{max}_{x'\in\mathcal{L}}k(x,x'),0\}$$
이 식은 새 후보 $\tilde x$가 데이터 $x$에 대해 얼마나 추가적인 coverage gain을 주는지를 나타낸다.
이 max kernel을 사용하면 MaxHerding의 coverage 증가를 다음처럼 쓸 수 있다.
$$\text{max}_{\tilde x} \frac{1}{N}\sum_{n=1}^N k(x_n,\tilde x';\mathcal{L})-\frac{1}{|L|+1}\sum_{l=1}^{|L|} k(\tilde x_l,\tilde x;\mathcal{L})$$
이 형태는 kernel herding의 선택 기준과 매우 유사하다.
하지만 핵심 차이는 MaxHerding이 일반 kernel $k(x,\tilde x)$가 아니라, 현재까지의 coverage를 고려한 max kernel $k(x,\tilde x;\mathcal{L})$을 사용한다는 점이다.
Kernel herding은 분포의 밀도를 잘 맞추는 것이 목표이므로, 데이터가 많이 몰린 영역에서 여러 샘플을 선택할 수 있다.
반면 MaxHerding은 이미 충분히 덮인 영역의 추가 기여를 줄인다.
따라서 kernel herding이 “전체 분포를 잘 근사하는 샘플”을 고른다면, MaxHerding은 “분류에 필요한 label coverage를 넓히는 샘플”을 고른다고 볼 수 있다.
논문은 generalized coverage를 비-greedy하게 최적화하는 방식도 분석한다. 새 batch $\mathcal{S}$를 한 번에 고르는 문제는 다음과 같다.
$$\text{argmax}_{\mathcal{S}\subset \mathcal{X},|\mathcal{S}|=B}\frac{1}{N}\sum_{n=1}^N \text{min}_{x' \in \mathcal{L}\cup\mathcal{S}} ||\phi(x_n)-\phi(x')||_\mathcal{H}^2$$
Kernel feature map을 $\phi$라 하면,
$$||\phi(x_n)-\phi(x')||_\mathcal{H}^2=k(x_n,x_n)+k(x',x')-2k(x_n,x')$$이다.
$k(x,x)$가 constant라면, similarity $k(x_n,x')$를 최대화하는 것은 feature space 거리 $||\phi(x_n)-\phi(x')||^2$를 최소화하는 것과 같다.
따라서 generalized coverage maximization은 kernel k-medoids와 연결된다.
다만 active learning에서는 실제 데이터 포인트에 라벨을 요청해야 하므로 임의의 cluster center를 선택할 수 없다.
이 때문에 k-means보다 k-medoids가 더 자연스럽다. 하지만 k-medoids는 계산 비용이 크다.
실험에서도 kernel k-medoids는 MaxHerding보다 약간 나을 수 있지만 훨씬 느리다. 그래서 논문은 실용적으로 MaxHerding을 추천한다.
MaxHerding이 이미 설명된 영역을 다시 선택하지 않음을 ($a$), gaussian kernel 기반의 부드러운 coverage를 사용함으로써 더 다양한 영역을 탐색하고, 하이퍼파라미터 변화에도 훨씬 안정적임을 ($b$) 보여준다.
Low-budget 환경에서는 uncertainty 기반 active learning이 오히려 random sampling보다 못한 성능을 보이는 반면, coverage 기반 접근은 일관되게 우수한 성능을 보인다.
특히 데이터가 불균형해질수록 단순히 밀도가 높은 영역을 선택하는 방법보다, 아직 충분히 설명되지 않은 영역을 탐색하는 MaxHerding의 전략이 더욱 효과적으로 작동한다.
결국 MaxHerding은 "가장 대표적인 샘플"이 아니라 "가장 부족한 coverage를 보완하는 샘플"을 선택함으로써 다양한 데이터 분포에서 안정적인 성능을 달성한다.