1. Introduction

[Problem]: Online Class-Incremental Continual Learning

[Dataset]: Non-i.i.d streaming data (각 샘플은 한번만 보여짐)

[Approach]: Replay method

[Main Issue]:

  • 제한된 replay buffer로 인한 오래된 클래스들과 최근 클래스들 사이의 imbalance
  • 특히, softmax 분류기와 FC layer는 class imbalance에 심각하게 영향을 받음
    - Recency Bias : 모델이 최근 클래스들에 편향되게 학습되는 경향이 있음

[Contribution]:

  • Softmax classifier의 결점들을 해결하기 위해 NCM을 사용
  • NCM의 정확도 향상을 위해 supervised contrastive learning을 experience replay-based training과 결합

 

2. Method

2.1. Softmax Classifier vs. NCM Classifier

Softmax classifier

Neural networks에서 cross-entropy loss와 함께 흔히 사용되는 Softmax classifier는 다음과 같은 결점들을 가진다.

  • Architecture modification for new classes: 새로운 클래스가 들어오면 training을 멈추고 FC layer에 출력 노드 및 해당하는 connections을 추가해야한다.
  • Decoupled representation and classification: 위와 같은 이유로 encoder와 분류 layer를 따로 학습시켜야 함
  • Task-recency bias: 모델이 최근 클래스들에 편향되게 학습되는 경향이 있음

 

Nearest Class Mean (NCM) Classifier

Embeding network $f$가 training된 후, NCM은 1) 각 클래스의 평균 벡터 or prototype을 계산하고, 2) 새로운 샘플 $x$에 대해 그것의 임베딩을 모든 prototype들과 비교한뒤 가장 비슷한 것의 클래스로 할당한다:

$$\begin{equation} \mu_c = \frac{1}{n_c} \sum_i f(x_i) \cdot 1\{y_i=c\} \end{equation} \tag{1}$$

$$\begin{equation} y^\ast = \arg\min_{c=1,...,t} \| f(x) - \mu_c \| \end{equation} \tag{2}$$

여기서 $1\{y_i=c\}$는 $y_i = c$에 대한 indicator이다.

 

NCM의 이점

  • 새로운 클래스가 더해질 때 FC layer의 추가 혹은 수정을 요구하지 않음
  • Eq. (1)에서, 인코더의 변화에 따라 prototype도 알아서 변하므로 거리 계산만 하면 됨
  • NCM 분류기는 FC layer를 포함하지 않으므로 task-recency bias가 덜함

 

2.2. Supervised Contrastive Replay

Supervised Contrastive Learning (SCL)

NCM의 정확도 향상을 위해, SCL을 적용 (같은 클래스는 가깝게, 다른 클래스는 멀게 보일 수 있도록 학습)

SCL은 세가지 메인 컴포넌트들로 구성된다.

  1. $Aug(\cdot)$은 데이터 샘플 $x$의 augmented view $\tilde{x}$를 생성, i.e., $\tilde{x}=Aug(x)$.
  2. Encoder network $Enc(\cdot)$은 $x$를 embedding $r$로 매핑, i.e., $r=Enc(x) \in \mathbb{R}^{D_E}$.
  3. Projection network $Proj(\cdot)$은 $r$을 projected vector $z$로 매핑, i.e., $z=Proj(r) \in \mathbb{R}^{D_P} $

b개의 샘플들을 가진 batch $B = \{x_k,y_k\}_{k=1,...,b}$가 주어지면, 2b개의 샘플을 가진 multiviewed batch $B_I=B\cup \tilde{B}$가 생성, 여기서 $\tilde{B} = \{ \tilde{x}_k=Aug(x_k), y_k \}_{k=1,...,b}$.

 

SCL loss는 다음과 같이 계산된다.

$$\begin{equation} \mathcal{L}_{\text{SCL}}(Z_I) = \sum_{i\in I} \frac{-1}{\vert P(i) \vert} \sum_{p\in P(i)} \log \frac{\text{exp}(z_i \cdot z_p / \tau)}{\sum_{j\in A(i)} \text{exp}(z_i \cdot z_j / \tau) } \end{equation} \tag{3}$$

여기서 $I$는 $B_I$의 indices set이고, $A(i)=I\setminus\{i\}$는 $B_I$에서 샘플 i를 제외한 모든 샘플의 indices set이다.

$P(i) \equiv \{ p \in A(i) : y_p=y_i \}$는 $A(i)$에서 샘플 i와 같은 labels을 가진 샘플들 (positives)의 집합이다.

$Z(i) = \{z_i\}_{i \in I} = \{ Proj(Enc(x_i)) \}_{i \in I}$이고, $\tau \in \mathbb{R}^+$는 temperature parameter이다.

→ positives과의 내적이 negative와의 것보다 크도록 학습된다.

 

Supervised Contrastive Replay (SCR)

An overview of SCR

  • Training step: 1) data stream $\mathcal{S}$에서의 minibatch $B_n$과 memory buffer $\mathcal{M}$에서의 minibatch $B_{\mathcal{M}}$은 결합되고, augmented view를 생성한다. 2) input batch와 augmented view는 shared encoder와 projection head에 의해 인코딩되고 SCL에 의해 encoder와 projection은 업데이트된다. 3) $B_n$은 memory buffer $\mathcal{M}$로 업데이트 된다.
  • Test step: 1) 모든 buffered 샘플들은 encoder에 의해 임베딩되고 prototypes을 계산하는데 사용된다. 2) 임베딩 공간에서 NCM 분류기가 수행된다.

Training 이후 메모리 버퍼 $\mathcal{M}$에서 데이터 임베딩들의 시각화는 다음과 같다.

Cross-entropy loss를 사용하는 기존 방법들과 달리 contrastive loss를 사용하는 방법이 클래스들을 더 잘 구별할 수 있는 임베딩 공간을 찾는다. → Distance metric learning

 

 

Run time이 그렇게 빠르지는 않다. (e.g. encoder network가 업데이트 될때마다 클래스 평균 다시 계산 하는 등)

→ 임베딩 공간의 효율적인 학습 전략이 필요할 듯 하다.

 

본 논문 링크: [Link]

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]

+ Recent posts