[Paper Review] How Does Unlabeled Data Provably Help Out-of-Distribution Detection?

논문 링크 : SAL
How Does Unlabeled Data Provably Help Out-of-Distribution Detection? 논문 리뷰입니다.

Introduction

Real-World 환경에서 machine learning model을 배포할때, 안정성과 신뢰성은 종종 Out-of-distribution(OOD) data의 발생으로 위협받는다. OOD data는 unknown category에서 발생하며 model에 예측해서는 안된다. 문제는 model이 real-world에서 발생하는 OOD data에 대한 인식 능력이 부족하다는 것이다. model은 학습과정에서 unknown distribution에 명시적으로 노출되지 않기에 in-distribution(ID)와 OOD data간의 신뢰할 수 있는 경계를 학습할 수 없다.

 

이런 한계를 극복하고자 추가 데이터를 활용한 학습을 연구하기 시작했다. 이를 통해 OOD data에 대해 보수적이고 안전한 결정 경계를 형성할 수 있다.

 

최근 연구에서 label이 있는 ID data를 분류하는 동시에 label이 없는 wild data를 활용하여 model 학습을 regularization하는 방법을 제안했다. 하지만, wild data를 효과적으로 활용하는 것은 쉽지 않다. 이는 ID와 OOD data가 혼합형태로 존재하기 때문이다.

 

$\mathbb{P}_{wild}:=(1-\pi) \mathbb{P}_{in}+\pi \mathbb{P}_{out}$ 로 표현할 수 있는 wild data에서 개별 sample이 ID인지 OOD인지에 대한 명확한 정보를 알 수 없다.

 

본 연구에서는 핵심 질문을 제기한다.

 

"How does unlabeled wild data provably help OOD detection?"

Algorithmic contribution

본 논문에서는 wild data를 효과적으로 활용하기 위한 SAL(Separate And Learn) 프레임워크를 제안한다.

1. Filtering : unlabeled data에서 candidate outlier를 분리
2. Classification : candidate outlier와 labeled ID data를 이용해 OOD classifier를 학습

Candidate outlier를 분리하기 위해, 본 논문의 핵심 아이디어는 ID data로 학습된 classifier로 unlabeled data의 gradient를 계산하고, 이를 이용한 gradient matrix에 대해 singular value decomposition (SVD)를 수행한다. SAL에서는 unlabeled data가 top singular vector 방향으로의 projection값이 주어진 threshold값을 초과할 경우 candidate outlier로 간주한다. 적절한 조건하에서는 높은 확률로 top singular vector 방향에서 wild outlier data의 gradient 평균 크기가 ID data보다 더 크게 나타난다.

 

Candidate outlier를 분리한 후, SAL은 ID data와 candidate outlier간의 분류를 최적화하는 OOD classifier를 학습한다.

Theoretical significance

본 연구는 separability와 learnability 관점에서 새로운 이론을 제시하며, 제안한 알고리즘의 두 가지 구성 요소를 형식적으로 정당화한다.

 

Theorem 1에서는 filtering 절차를 통해 unlabeled wild data에서 outlier의 separability을 분석하고 error rate에 대한 엄밀한 bound를 제공한다. labeled ID data와 unlabeled data의 크기가 충분히 크다면, Theorem1과 2에 의해 outlier filtering의 error rate가 optimal ID risk에 비례하는 작은 bias로 제한될 수 있다.

 

Theorem 3에서는 noisy한 candidate outlier와 ID data를 기반으로 학습한 OOD classifier의 generalization error를 제시하고, 적절한 조건하에서 학습된 OOD classifier의 generalization error가 optimal OOD classifier의 risk에 의한 upper bound로 제한됨을 보인다.

Empirical validation

SAL은 modern neural networks와 같은 non-convex model에도 널리 사용가능하다. 본 논문에서는 SAL을 다양한 OOD detection task에 대해 광범위하게 평가했으며, state-of-the-art 성능을 달성하였다.

Problem Setup

• $\mathcal{X}$ : input space
• $\mathcal{Y}$ = $\{1, \dots , K\}$ : label space for ID data.
• $\mathcal{S}^{in}=\{(x_{1},y_{1}), \dots , (x_{n},y_{n})\}$ : labeled ID data
• $\mathbb{P}_{\mathcal{X}\mathcal{Y}}$ : unknown ID joint distribution
• $\mathbb{P}_{in}$ : marginal distribution $\mathcal{X}$
• $\mathcal{S}_{wild}={\tilde{x}_{1}, \dots, \tilde{x}_{m}}$ : unlabeled wild data
• $\mathbb{P}_{wild}:=(1-\pi)\mathbb{P}_{in}+ \pi \mathbb{P}_{out}$
  • $\pi \in (0, 1]$
  • $\mathbb{P}_{out}$ : OOD distribution over $\mathcal{X}$
• $\mathbf{h_{w}} : \mathcal{X} \mapsto \mathbb{R}^{K}$ : ID classifier
  • $\mathbf{w}\in\mathcal{W}$ : parameter space
• $l : \mathbb{R}^{K} \times \mathcal{Y} \mapsto \mathbb{R}$ : loss function
• $\mathbf{g_{\theta}} : \mathcal{X} \mapsto \mathbb{R}$ : OOD classifier
  • $\mathbf{\theta}\in\Theta$ : parameter space
• $l_{b}(\mathbf{g_{\theta}},y_{b})$ : binary loss function
  • $y_{b}\in \mathcal{Y}_{b}:=\{y_{+},y_{-}\}$
    • $y_{+}\in \mathbb{R}_{>0}$ : ID class
    • $y_{-}\in \mathbb{R}_{<0}$ : OOD class

Proposed Methodology

unlabeled wild data을 활용하여 OOD detection을 수행하는 새로운 학습 프레임워크 SAL을 보인다.

 

SAL은 ID data에만 의존하는 기존의 접근법보다 상당한 이점을 제공하며, model이 real world 환경에 배포되는 다양한 상황에 자연스럽게 적합하다.

1. Filtering : unlabeled data에서 candidate outlier를 분리
2. Classification : ID data와 candidate outlier를 함께 사용해 binary OOD classifier를 학습.

Separating Candidate Outlier from the Wild data

wild mixture $\mathcal{S}_{wild}$에서 candidiate outlier를 분리하기 위해, gradient 기반의 level-set estimation을 사용한다. Gradient는 ID data $\mathcal{S}_{in}$로 학습된 classifier $\mathbf{h_{w}}$로부터 추정된다.

Estimating the reference gradient from ID data.

먼저 SAL은 ID data $\mathcal{S}_{in}$에 대해 classifier $\mathbf{h_{w}}$를 ERM으로 학습하여 reference gradient를 추정한다.

$$ \mathbf{w}_{S^{\text{in}}} \in \underset{\mathbf{w} \in W}{\arg\min} R_{S^{\text{in}}}(\mathbf{h_{w}}), \quad \text{where} \quad R_{S^{\text{in}}}(\mathbf{h_{w}}) = \frac{1}{n} \sum_{({x_{i}}, y_{i}) \in S^{\text{in}}} \ell(\mathbf{h_{w}}({x_{i}}), y_{i}), \tag{3}$$

• $\mathbf{w}_{\mathcal{S}_{in}}$ : learned parameter
• $n$ : size of ID training set

평균 gradient는 아래와 같이 정의된다:
$$\bar{\nabla} = \frac{1}{n} \sum_{({x_{i}}, y_{i}) \in S^{\text{in}}} \nabla \ell(\mathbf{h}_{\mathbf{w}_{S^{\text{in}}}}({x_{i}}), y_{i}), \tag{4}$$

• $\bar{\nabla}$ : reference gradient

Separate candidate outlier from the unlabeled wild data.

학습된 classifier $\mathbf{h_{w}}$를 실제 환경에 배포하면 자연스럽게 unlabeled ID와 OOD가 혼합된 data $\mathcal{S}_{wild}$을 얻는다.

 

이 프레임워크의 핵심은 $\mathcal{S}_{wild}$에 대해 filtering을 수행하여, filtering score 기반으로 candidate outlier를 찾는 것이다. Filtering score를 정의하기 위해 $\mathcal{S}_{wild}$의 각 data를 reference gradient에 상대적인 gradient vector로 표현한다.

 

$$
\mathbf{G} =
\begin{bmatrix}
\big(\nabla \ell(\mathbf{h}_{\mathbf{w}_{S^{\mathrm{in}}}}(\tilde{x}_{1}), \hat{y}_{\tilde{x}_{1}}) - \bar{\nabla}\big)^{\!\top} \\
\vdots \\
\big(\nabla \ell(\mathbf{h}_{\mathbf{w}_{S^{\mathrm{in}}}}(\tilde{x}_{m}), \hat{y}_{\tilde{x}_{m}}) - \bar{\nabla}\big)^{\!\top}
\end{bmatrix}. \tag{5}
$$

• $m$ : size of the wild data
• $\hat{y_{\tilde{x}}}$ : predicted label for a wild sample $\tilde{x}$

각 data $\tilde{x} \in \mathcal{S}_{wild}$에 대해 filtering score $\tau_{i}$를 아래와 같이 정의한다:
$$\tau_{i} = \langle \nabla \ell(\mathbf{h}_{\mathbf{w}_{S^{\text{in}}}}(\tilde{x}_{i}), \hat{y}_{\tilde{x}_{i}}) - \bar{\nabla}, \mathbf{v} \rangle^{2}, \tag{6}$$

• $\langle \cdot , \cdot \rangle$ : dot product operator
• $\mathbf{v}$ : top singular vector of $\mathbf{G}$
  • wild data 전체에 대해 projected gradient가 원점에서 멀어지는 정도를 최대화하는 방향을 나타냄.

특히, $\mathbf{v}$는 unit-norm vector이며 아래와 같이 계산된다:
$$
\mathbf{v} \in \underset{\Vert \mathbf{u} \Vert_{2}=1}{\arg\max} \sum_{\tilde{x}_{i} \in S_{\text{wild}}} \langle \mathbf{u}, \nabla \ell(\mathbf{h}_{\mathbf{w}_{S^{\text{in}}}}(\tilde{x}_{i}), \hat{y}_{\tilde{x}_{i}}) - \bar{\nabla} \rangle^{2}. \tag{7}
$$

즉, filtering score $\tau_{i}$는 해당 gradient vector를 top singular vector 방향으로 projection했을 때 $l_{2}$norm을 측정한다.

• (a) Gradient vector들을 top singular vector에 projection한 결과를 시각화.
• (b) Outlier gradient와 $\mathbf{v}$사이의 각도 $\theta$를 나타냄
  • x표시들이 원점으로부터 멀어지도록, 즉 wild data 전체 gradient의 거리 합이 최대화되는 방향으로 선택.

Remark 1.

적절한 가정하에 충분한 데이터와 큰 규모의 model을 사용할 경우 높은 확률로 다음이 성립한다:

• OOD gradient를 top singular vector $\mathbf{v}$ 방향으로 projection한 평균 크기는 $\frac{C}{\pi}$라는 양의 상수로 하한이 주어진다.
• ID gradient를 $\mathbf{v}$방향으로 projection한 평균 크기는 0에 가까운 작은 값으로 상한이 주어진다.

마지막으로, filtering을 통해 얻은 candidate outlier set은 아래와 같이 정의한다:
$$\mathcal{S}_{T}=\{\tilde{x} \in \mathcal{S}_{wild} : \tau_{i}>T\}$$

• $T$ : filtering threshold
  • ID data를 기반으로 선택 (ID sample의 95%가 threshold 이하가 되도록 설정)

An illustrative example of algorithm effect

이해를 돕기 위해 simulation을 하였다.

• wild data는 ID data(3 class gaussian)와 OOD data의 혼합으로 구성된다. 두 가지의 시나리오를 고려하였고, ground truth는 보라색이다.
• (b)는 제안한 방법으로 식별한 outlier(green)이다. 이는 ground truth와 크게 일치한다.

Remark 2.

Filtering 과정은 간단하게 K-class classification으로 확장 가능하다. 이 경우 class-conditional reference gradient $\bar{\nabla}_{k}$를 유지하며, 해당 class에 속하는 ID data로부터 추정되어 각 ID class의 특성을 포착한다. 이때 gradient matrix는 wild sample 중 class $k$로 예측된 data의 gradient vector로 구성된 $\mathbf{G}_{k}$로 대체된다.

Training the OOD classifier with the Candidate Outliers

wild data로부터 candidate outlier set $\mathcal{S}_{T}$를 얻은 후 ID vs. candidate outlier data간의 separability를 최적화하는 OOD classifier $\mathbf{g_{\theta}}$를 학습한다.

 

학습 목적은 level-set최적화(threshold 0)로 해석할 수 있다. 즉 ID data는 양수, 반대로 candidate outlier는 음수 값을 갖도록 학습한다.

 

$$
\begin{equation} \begin{split} R_{S^{\text{in}}, S_{T}}(\mathbf{g}_{\boldsymbol{\theta}}) &= R^{+}_{S^{\text{in}}}(\mathbf{g}_{\boldsymbol{\theta}}) + R^{-}_{S_{T}}(\mathbf{g}_{\boldsymbol{\theta}}) \\ &= \mathbb{E}_{x \in S^{\text{in}}} \mathbb{1}\{ \mathbf{g}_{\boldsymbol{\theta}}(x) \le 0 \} + \mathbb{E}_{\tilde{x} \in S_{T}} \mathbb{1}\{ \mathbf{g}_{\boldsymbol{\theta}}(\tilde{x}) > 0 \}. \end{split} \tag{8} \end{equation}
$$

 

0/1 loss는 계산이 불가능하기에, binary sigmoid loss로 대체한다. $\mathbf{g_{\theta}}$를 학습시킬때 (3)의 수식과 함께 최적화한다.

 

이러한 학습이 $\mathbb{P}_{out}$에서 추출된 real OOD sample에 대해 강력한 generalization 성능을 가능하게 한다.

 

자세한 증명과 이론적 보장은 논문을 참고

Experiments

WOODS와 실험 setup을 그대로 따른다.

• ID dataset $\mathbb{P}_{in}$: CIFAR10, CIFAR100
• OOD test dataset $\mathbb{P}_{out}$ : Textures, SVHN, Places365, LSUN-R, LSUN-C

실제 환경을 반영하기 위해 ID data와 OOD data를 혼합하여 wild data를 구성한다. ($\mathbb{P}_{wild}$ ($\pi=0.1$))

예를 들어, SVHN을 OOD로 사용할 경우 CIFAR + SVHN 조합을 unlabeled wild data로 사용하고, test는 SVHN으로 진행한다. 동일한 절차를 모든 OOD dataset에 적용한다.

 

CIFAR dataset은 절반으로 나누어 25000장은 ID train data로, 나머지 25000장은 wild mixture 생성을 위해 사용한다.

penultimate layer의 weight를 사용하여 gradient를 계산한다.

• CIFAR100에서 SAL은 WOODS 대비 5.92% 향상된 결과를 보인다.
• 작은 generalization error에 대한 이론적 보장과 맞게 강력한 실험 성능을 보인다.

Conclusion

• 본 논문에서는 unlabeled in-the-wild data를 활용한 OOD detection을 위한 새로운 학습 프레임워크 SAL을 제안하였다.
• SAL은 먼저 제안한 filtering score를 이용해 wild data에서 candidate outlier를 명시적으로 분리한 뒤, 이를 활용하여 binary OOD classifier를 학습한다.
• 이론적으로 SAL은 wild 환경에서 outlier의 separability와 OOD classifier의 learnability를 분석함으로써, unlabeled wild data가 OOD detection에 어떻게 기여할 수 있는지에 대한 질문에 답한다.
• 이를 통해 SAL은 두 핵심 구성 요소에 대해 provable error guarantee를 제공한다.