1. Introduction
[Dataset]: ImageNet-10K
[Problem]: Class-Incremental Learning at near-zero cost
[Approach]: Distance-based classifiers
- k-Nearest Neighbor (kNN) classifier
- Nearest Class Mean (NCM) classifier
이러한 분류기들의 성능은 distance metric에 상당히 의존적이므로 이 논문에서는 모든 클래스들에서 공유되는 low-rank 마할라노비스 거리를 학습하는 것을 중점적으로 다룬다.
[Contribution]:
- NCM 분류기를 위한 metric learning 알고리즘 제안
- 효율성 향상을 위해 low-rank 마할라노비스 거리 도입
2. The Nearest Class Mean Classifier
$d(x, \mu_c)$를 image $x$와 클래스 평균 $\mu_c$사이의 유클리디안 거리라고 하자.
NCM은 입력 $x$를 가장 가까운 클래스 평균을 가진 대응되는 클래스 $c^{\ast} \in \{1,...,C\}$로 다음과 같이 할당한다.
$$\begin{equation} c^{\ast}=\text{argmin}_c d(x, \mu_c) \tag{1} \end{equation}$$
$$\begin{equation} \mu_c = \frac{1}{N_c} \sum_{i:y_i=c} x_i \tag{2} \end{equation}$$
여기서 $y_i$는 ground-truth, $N_c$는 각 클래스에 해당하는 instances의 수이다.
2.1. Metric Learning for the NCM Classifier
이 섹션에서는 제안된 Nearest Class Mean Metric Learning (NCMML)을 소개한다.
Eq. (1)에서 유클리디안 거리는 trainable 마할라노비스 거리로 대체된다:
$$ \begin{equation} d_{M}(x, x')= (x - x')^\top M (x - x') \end{equation} \tag{3}$$
여기서 $x$와 $x'$는 D-차원 벡터들이고 $M$은 positive definite matrix이다.
계산 및 메모리 효율성 향상의 목적으로 위의 그림과 같이 입력들을 (클래스들을 잘 분리해낼 수 있는) 저차원 공간에 projection시키기 위해 $M$을 low-lank metrics로 쪼갠다.
즉, $M=W^\top W$, $W \in \mathbb{R}^{d \times D}$, $d \leq D$.
$$ \begin{align} d_{W}(x, x')&= (x - x')^\top W^\top W (x - x') \\ &= \| Wx-Wx' \|^2_2 \\ \end{align} \tag{4}$$
Eq. (4)는 W를 통해 입력공간을 저차원 공간으로 linear projection한 뒤 squared $l_2$ norm을 구하는 것과 동일하다.
이를 토대로 NCM 분류기는 다음의 확률 모델을 사용하여 각 클래스를 분류한다.
$$ \begin{equation} p(c \vert x)= \frac{\text{exp}(-\frac{1}{2}d_W(x, \mu_c))}{\sum^C_{c'=1}\text{exp}(-\frac{1}{2}d_W(x, \mu_{c'}))} \end{equation} \tag{5}$$
Projection 행렬 $W$를 학습하기 위해 다음과 같이 목적함수를 log-likelihood로 정의하고 이를 최적화하기 위한 grandient를 계산한다.
$$ \begin{equation} \mathcal{L}=\frac{1}{N} \sum^N_{i=1}\text{ln} \; p(y_i \vert x_i) \end{equation} \tag{6}$$
$$ \begin{equation} \bigtriangledown_W \mathcal{L}=\frac{1}{N} \sum^N_{i=1} \sum^C_{c=1} \alpha_{ic} W z_{ic}z_{ic}^\top \end{equation} \tag{7}$$
여기서 $\alpha_{ic}=p(c \vert x_i)- [y_i=c]$, $z_ic=\mu_c - x_i$이다. ($[\cdot]$은 Iverson bracket)
2.2. Nonlinear NCM with Mulitple Class Centroids
이 섹션에서는 클래스 평균만 사용하는 것 대신 centroids의 집합을 사용하여 각 클래스를 표현하는 것에 의해 NCM을 비선형 분류기로 확장한다.
각 클래스 $c$에 대해 $k$개의 centroid들의 집합 $\{m_{cj}\}^k_{j=1}$이 있다고 하자.
각 클래스의 사후 확률은 다음과 같이 정의된다.
$$ \begin{equation} p(c \vert x)= \sum^k_{j=1} p(m_{cj} \vert x) \end{equation} \tag{8}$$
$$ \begin{equation} p(m_{cj} \vert x) = \frac{1}{Z} \text{exp} \left( -\frac{1}{2} d_W(x,m_{cj}) \right) \end{equation} \tag{9}$$
여기서 $Z$는 normalizer이며, 각 클래스의 centroids을 얻기 위해 k-means clustering을 사용한다.
2.3. Alternative Objective for Small SGD Batches
Eq (7)에서 gradient를 계산하는 것은 매 업데이트마다 Eq (4)를 $N \times C$번 계산해야하기 때문에 값비싸다.
Eq (5)에서 $-\frac{1}{2}d_W(x, \mu_c)$는 다음과 같이 계산된다.
$$ \begin{equation} -\frac{1}{2}\| Wx \|^2_2 -\frac{1}{2}\| W \mu_c \|^2_2 + x^\top W^\top W \mu_c \end{equation}$$
여기서 첫번째 항은 클래스 $c$를 분류하는 것과 관련이 없으므로 제거될 수 있다.
그러므로 Eq (5)는 다음과 같이 negative dot-product와 class-specific bias의 합으로 나타낼 수 있다.
$$ \begin{align} p(c \vert x_i) &= -\frac{1}{Z} \text{exp} ( x_i^\top W^\top W \mu_c + s_c) \\ s_c&=-\frac{1}{2}\| W \mu_c \|^2_2 \\ \end{align} \tag{10}$$
결과적으로, 새로운 클래스가 들어오면 그것에 대한 평균만 계산하여 간단히 일반화 할 수 있다.
3. K-NN Metric Learning
위의 소개된 MCMML과의 비교를 위해 Large Margin Nearest Neighbor (LMNN) classification 방법을 약간 수정하여 사용하였다.
LMNN은 지난 포스트 [Link]에서 짧게 다루었다.
자세한 실험 결과들은 본 논문 참고 [Link]