CAIS (Continual AI Study)

1. Introduction

[Problem]: NCM 분류기의 정확도를 향상시키기 위해 값비싼 계산 과정 없이 non-linear deep representations을 학습하는 것

[Approach and Contribution]:

1. Distance metric을 학습시키는 것 대신 deep representation을 학습
2. representation을 업데이트 할때마다 클래스 평균을 다시 계산하는 과정을 approximation

논문 링크: [Link]

2. Deep Nearest Mean Classification

NCM은 각 이미지를 가장 가까운 평균을 가진 클래스로 할당한다.

$$\begin{equation} y^\star = {\arg\min}_{y \in \{1,...,Y\}} d(x,\mu_y) \end{equation} \tag{1}$$

이전 포스팅 참고 [Link] - [TPAMI 2013] Distance-Based Image Classification: Generalizing to New Classes at Near-Zero Cost

위 포스팅의 방법과 같이 고정된 표현에 대해 마할라노비스 척도 $W$를 학습하는 것 대신, 이 논문에서는 a deep representation $\phi(\cdot)$의 파라미터들을 학습한다.

이 논문의 아이디어는 비선형 딥 표현을 잘 학습한다면, 선형 척도 $W$를 학습할 필요없이 유클라디안 거리를 사용해도 충분하다는 것이다.

즉,

$$\begin{equation} d^\phi_{xy} = (\phi(x) - \mu^\phi_y)^\top (\phi(x) - \mu^\phi_y), \quad \mu^\phi_y=\frac{1}{N_y} \sum_{i:y_i=y} \phi(x_i) \end{equation} \tag{2}$$

여기서 $\phi(x)$는 convolutional layer 등이 사용될 수 있다.

이 때, 문제는 $\phi(x)$가 업데이트 될때마다 클래스 평균을 다시 계산해야한다는 것이다.

2.1. Mean Updates per Batch

계산 비용을 줄이기 위해, 클래스 평균들의 online estimate를 사용한다.

$$\begin{equation} \mu^\phi_{y_i} \gets \frac{n_{y_i}}{n_{y_i}+1}\mu^\phi_{y_i} + \frac{1}{n_{y_i}+1} \phi (x_i) \end{equation} \tag{3}$$

여기서 $n_{y_i}$는 클래스 $y_i$에 속하는 샘플들의 수이다.

즉, 각 배치에 대한 $\phi(x_i)$만 계산하면 된다.

위의 online mean방법을 더욱 향상시키기 위한 두가지 방법 또한 소개되었다.

Mean Condensation: 학습되는 표현이 지속적으로 변하므로, 최근에 들어오는 예제들에 더 많은 가중치를 할당한다.

이를 위해 각 epoch의 시작에서, $n_y = 1 \forall y \in Y$로 설정한다. 

즉 historical 클래스 평균들은 현재 epoch에서 싱글 데이터 포인트로써 카운트된다.

Decay Mean: epoch마다 평균을 다시 설정하는것 대신, 다음과 같이 decay scheme을 사용한다.

$$\begin{equation} \mu^\phi_{y_i} \gets \alpha \mu^\phi_{y_i} + (1-\alpha) \phi (x_i) \end{equation} \tag{4}$$

실제 구현에서는 single example $\phi(x_i)$대신 batch mean $\mu^\phi_{B_y}$를 사용한다.

3. Experiments

1. Introduction

[Problem]: Tiny device위에서 정확한 실시간 예측이 가능한 kNN

[Target Device]: $\leq$ 32kB RAM, 16MHz processor를 가진 IoT 디바이스

[Approach]: k-Nearest Neighbor (kNN)

• (kNN의 이점): tiny 디바이스에서 쉬운 구현, overfitting에 강함, 해석이 용이
• (kNN의 결점): a) Poor accuracy, b) Model size (예측하기 위해 전체 training data를 요구하므로) c) Prediction time (각 test instance에 대해 모든 training data와의 거리를 계산하므로)

[Contribution]:

• Sparse low-d projection: trainable sparse projection matrix를 사용하여 정확도를 보존하면서 전체 데이터를 저차원으로 projection
• Prototypes: 전체 트레이닝 데이터셋을 표현하기 위한 'prototypes'을 학습
• Joint optimization: 주어진 모델 사이즈 내에서 최적 모델을 얻을 수 있도록 최적화 과정에서 sparcity constraints을 부과

2. Problem Formulation

$n$개의 데이터 점들과 해당하는 label or class들을 각각 $X=[x_1,x_2,...,x_n]^T, x_i \in \mathbb{R}^d$와 $Y=[y_1,y_2,...,y_n]^T, y_i \in \mathcal{Y}$라고 하자.

kNN 예측 함수의 a smooth version으로써 다음을 고려하자.

$$\begin{equation} \hat{y}= \rho(\hat{s}) = \rho \left( \sum^n_{i=1} \sigma (y_i) K(x,x_i) \right) \end{equation} \tag{1}$$

여기서 $\hat{s}$는 score vector이고, $\rho: \mathbb{R}^L \to \mathcal{Y}$는 score vector를 출력 공간으로 mapping한다 (single-label이면 best score를 가진 클래스만 1로).

$\sigma:\mathcal{Y} \to \mathbb{R}^L$은 반대로 ground-truth를 score vector와 같은 차원으로 매핑한다.

$K: \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}$는 두 점사이의 similarity function이다. (such as $l_2$ distance)

전체 트레이닝 셋의 효율적인 표현으로써 학습할 prototypes을 $B=[b_1,...,b_m]$라 하고, 해당하는 score vectors $Z=[z_1,...,z_m] \in \mathbb{R}^{L \times m}$라고 하자.

결과적으로 decision function은 $ \hat{y}=\rho \left( \sum^m_{j=1} z_j K(x,b_j) \right) $로 주어진다.

또한 전체 데이터를 저차원으로 projection하기 위해 추가적인 matrix $W \in \mathbb{R}^{\hat{d} \times d}$를 사용한다.  (Distance Metric Learning으로 볼 수 있음)

따라서 Eq. (1)은 다음과 같이 쓰여질 수 있다.

$$\begin{equation} \hat{y}= \rho \left( \sum^n_{j=1} z_j K(Wx,b_j) \right) \end{equation} \tag{2}$$

여기서 $b_j \in \mathbb{R}^{\hat{d} \times m}, z_j \in \mathbb{R}^{L \times m}$이다.

이 논문에서는 similarity function으로써 다음과 같이 가우시안 커널을 사용하였다.

$$\begin{equation} K_\gamma = \text{exp} (-\gamma^2 \| x-y \|^2_2) \end{equation} $$

이제 $Z, B, W$를 어떻게 학습할 것인지에 대해 살펴보자.

각 샘플에 대한 loss function을 $\mathcal{L}(\hat{s}, y)$라 하면 (실험에서는 squared $l_2$ loss function 사용),

Empirical risk는 다음과 같이 정의된다.

$$\begin{equation} \mathcal{R}_{emp} (Z,B,W) = \frac{1}{n} \mathcal{L} \left( y_i, \sum^m_{j=1} z_j K_\gamma (b_j, Wx_i) \right) \end{equation} \tag{3}$$

결과적으로 목적 함수는 sparsity constraints을 부과하는 것에 의해 다음과 같이 정의된다.

$$\begin{equation} \min_{Z:\|Z\|_0 \leq s_Z, B:\|B\|_0 \leq s_B, W:\|W\|_0 \leq s_W} \mathcal{R}_{emp} (Z,B,W) \end{equation} \tag{4}$$

여기서 $\| Z \|_0$은 $Z$내에 zon-zero entries의 수이며 사용자 파라미터 $s_Z$에 의해 sparsity constraint를 가진다.

3. Algorithm

Eq. (4)는 non-convex이므로 이 논문에서는 $Z,B,W$를 한개씩 번갈아가면서 (다른 두개의 파라미터를 고정시켜놓고) 업데이트 한다.  

각각의 파라미터를 최적화하는 것 또한 non-convex이므로 projected SGD를 사용하여 업데이트 한다.

$B, W$를 고정시키고 $Z$에 관해 목적 함수를 최적화한다고 가정하자.

Mini-batch $S$에 대해 $Z$는 다음과 같이 업데이트 된다.

$$\begin{equation} Z \gets HT_{s_Z} \left( Z- \eta \sum_{i \in S} \bigtriangledown_Z \mathcal{L}_i(Z,B,W) \right) \end{equation} $$

여기서 $HT_{s_Z}(A)$는 $A$에서 가장 큰 $s_Z$개의 entries만 남기고 zero로 설정하는 hard thresholding operator이다.

결과적으로 최적화 과정은 다음과 같다.

제안하는 방법의 수렴 분석 및 자세한 실험들은 본논문 참고 [Link]

0. Background

Distance metric learning의 예제로써 'Large Margin Nearest Neighbor (LMNN) classification'을 살펴보자.

- 해당 논문은 2005년 NIPS에 발표되었다. [Link]

LMNN의 training 과정:

1. 각 입력 $\vec{x}_i$에 대해, 같은 class label $y_i$을 가진 점들 중 $k$개의 target neighbors를 식별한다. (prior knowledge가 없을 경우 Euclidean distance 사용)
2. Target neighbors가 모든 다른 labels을 가진 점들보다 $\vec{x}_i$에 가깝게 측정되는 distance metric을 찾는다.

Distance metric 추정을 위해 Mahalanobis distance metric을 다음과 같이 표현하여 convex 문제로 푼다.

임의의 두점 $\vec{x}_i, \vec{x}_j$에 대해,

$$ \begin{equation} d^2_{\mathbf{M}}(\vec{x}_i, \vec{x}_j)= (\vec{x}_i - \vec{x}_j)^\top \mathbf{M} (\vec{x}_i - \vec{x}_j) \end{equation} \tag{1}$$

여기서 $\mathbf{M}$이 항등행렬일 경우 Eq. (1)은 유클리디안 거리가 된다.

$\mathbf{M}$을 추정하기 위해 다음과 같이 semidefinite program (SDP) 문제를 정의한다.

• $j \leadsto i$는 $\vec{x}_j$가 $\vec{x}_i$의 target neighbor라는 것을 의미
• $\vec{x}_i$와 $\vec{x}_j$가 같은 label이면 $y_{ij}$는 1, 아니면 0.
• $\xi_{ijl}$는 $\vec{x}_i$을 기준으로 그것의 target neighbor $\vec{x}_j$ 들이 형성하는 어떤 경계선안에 다른 label을 가진 $\vec{x}_l$이 얼마나 있는지를 측정한다. (추후 다시 설명)

결국 loss function은 target neghbors은 가깝게 (first term), 서로다른 label의 점들끼린 멀게 (second term, margin을 높이면서) 측정되는 $\mathbf{M}$을 찾는것을 목적으로 한다.

1. Introduction

[Problem]: 기존 LMNN방법은 all training instances을 다 체크하고 (입력 공간 차원 $\times$ 입력 공간 차원)의 $\mathbf{M}$을 가지므로 large scale datasets에 적합하지 않음 (너무 오래걸림)

[Contribution]:

• SDP 문제를 효율적으로 풀기 위해 특정한 instances만 체크하는 solver를 제안하여 large scale datasets에 대한 학습을 가능하게 함
• Ball tree + low-rank approximation을 사용하여 training time과 testing time 감소
• 입력 공간을 여러 부분공간으로 나누고 각각에 대해 distance metric을 최적화함으로써 error rate 감소

2. Methodology

2.1. Solver

[목적]: SDP 과정을 통한 $\mathbf{M}$의 탐색 과정에서 일부 instances에 대한 sub-gradient를 계산하여 효율성 향상

위에서 소개한 SDP의 목적 함수를 $\mathbf{M}$의 함수로 표현할 수 있도록 먼저 slack 변수를 다음과 같이 표현한다.

$$ \begin{equation} \xi_{ijl}(\mathbf{M}) = [1+d^2_{\mathbf{M}}(\vec{x}_i, \vec{x}_j)-d^2_{\mathbf{M}}(\vec{x}_i, \vec{x}_l)]_+ \end{equation} \tag{2}$$

여기서 $[z]_+$는 $z>0$일 때 $z$이고 $z<0$일 때 0인 함수이다.

→ (다른 label을 가진 점과의 거리 - target neighbor과의 거리)가 1보다 작아야 값을 가진다. "Margin violation"

Slack 변수를 Eq. (2)로 대체하는 것에 의해 목적함수는 다음과 같이 formulation된다.

$$ \begin{equation} \varepsilon(\mathbf{M})=\sum_{j \leadsto i} [ d^2_{\mathbf{M}}(\vec{x}_i, \vec{x}_j)+\mu \sum_l (1-y_{il}) \xi_{ijl}(\mathbf{M}) ] \end{equation} \tag{3}$$

→ Second term은 다른 label을 가진 점들 중 $\vec{x}_i,$를 기준으로 (다른 label을 가진 점과의 거리 - target neighbor과의 거리)가 1보다 작을 경우에만 $\mathbf{M}$을 업데이트 한다.

→ 즉 서로 다른 label들 간의 점 사이의 "margin"을 1이상 가지도록하는 distance metric을 찾는다.

Eq. (3)은 미분 불가능하지만 convex이기 때문에, sub-gradient를 계산하는 것에 의해 standard descent algorithm을 사용할 수 있다.

먼저, Eq. (1)은 다음과 같이 나타낸다.

$$ \begin{equation} d^2_{\mathbf{M}}(\vec{x}_i, \vec{x}_j)= tr(\mathbf{C}_{ij}\mathbf{M}) \end{equation} \tag{4}$$

여기서 $\mathbf{C}_{ij} = (\vec{x}_i - \vec{x}_j)(\vec{x}_i - \vec{x}_j)^\top$이다.

각 iteration에서 $\mathcal{N}^t$를 triplet indices의 집합이라 하자. s.t. $(i,j,l)\in \mathcal{N}^t, \xi_{ijl}(\mathbf{M}^t)>0$.

이때, $t^{th}$ iteration에서, gradient $\mathbf{G}^t = \frac{\partial \varepsilon}{\partial \mathbf{M}}\vert_{\mathbf{M}^t}$는 다음과 같이 계산된다.

$$ \begin{equation} \mathbf{G}^t = \sum_{j \leadsto i} \mathbf{C}_{ij} + \mu \sum_{(i,j,l)\in\mathcal{N}^t} ( \mathbf{C}_{ij}-\mathbf{C}_{il})\end{equation} \tag{5}$$

여기서 margin violation이 얼만큼 되었는지에 대한 degree는 gradient값에 영향을 주지 않는다.

→ Eq. (4)를 $\mathbf{M}$에 관해 미분하면 0이됨

따라서 iteration이 다음으로 넘어갈때, gradient의 변화는 $\mathcal{N}^t$와 $\mathcal{N}^{t+1}$ 사이의 차에 의해 결정된다. 즉,

$$ \begin{equation} \mathbf{G}^{t+1} = \mathbf{G}^t - \mu \sum_{(i,j,l)\in\mathcal{N}^t-\mathcal{N}^{t+1}} ( \mathbf{C}_{ij}-\mathbf{C}_{il}) + \mu \sum_{(i,j,l)\in\mathcal{N}^{t+1}-\mathcal{N}^t} ( \mathbf{C}_{ij}-\mathbf{C}_{il}) \end{equation} \tag{6}$$

결과적으로 $\mathcal{N}$이 변할때 해당되는 instances에 대해서만 계산하여 업데이트가 가능하다.

2.2. Tree-Based Search

Nearest neighbor 탐색 과정은 instances을 트리같은 계층적 데이터 구조들로 저장하는 것에 의해 가속화될 수 있다.

이 논문에서는 ball tree방법을 적용하였다. (잘 알려진 방법이므로 위키로 대체 [Link])

추가로 SDP 과정에서 $\mathbf{M}$의 low-rank approximation을 사용하여 더욱 speedup시켰다.

2.3. Multiple Metrics

Error rate를 줄이기 위해 class label마다 서로 다른 distance metric을 사용한다.

자세한 실험들은 본논문 참고 [Link]