주어진 데이터로 예측 모델을 만들기 위해서는 적절한 loss function이 필요합니다. 이번 포스트에서는 2017년 NIPS에서 포스터로 발표된 논문인 “Learning with Average Top-k Loss”에 대해 소개하고자 합니다.

스크린샷 2018-04-24 오후 4.28.56

1. Introduction

지도 학습(supervised learning)은 주어진 data 및 feature x로부터 target y를 예측하는 기계학습의 큰 분야로, 다음의 최소화 문제를 푸는 과정을 다룹니다. 

\min_f{\{\L{}(\{\ell_i(f(x_i), y)\}_{i=1}^n) + \Omega(f)\}}

 위 식의 왼쪽 항은 ‘individual loss’를 통합하는 ‘aggregate loss’이며 오른쪽은 regularizer입니다. 여기서 individual loss( \ell )란 개별 샘플 (x, y) 에 대한 loss function입니다. 예를 들어, binary classification 문제에서는 hinge loss, logistic loss 등이 있습니다. Regression 문제에서는 square loss 및 absolute loss 등이 사용됩니다. 

  1. Hinge loss: \ell(f(x), y)=\max(0, 1-yf(x))
  2. Logistic loss: \ell(f(x), y)=\log_2(1+\exp(1-yf(x)))
  3. Square loss: \ell(f(x), y)=(f(x)-y)^2
  4. Absolute loss: \ell(f(x), y)=|f(x)-y|

 Aggregate loss( \L{} )로 가장 흔히 쓰이는 것은 average loss 입니다. Average loss는 모든 데이터의 loss 평균이므로, 편향되지 않고 outlier에 강합니다. 대신 주어진 데이터가 불균형적이거나 multimodal이면 성능이 좋지 않을 수 있습니다. 이러한 문제를 해결하기 위한 다른 대안으로는 maximum loss가 있습니다. Maximum loss minimization에서는 전체 데이터 중 loss가 가장 큰 데이터 샘플의 individual loss만을 최소화합니다. 그러나 maximum loss는 outlier에 너무 민감하게 반응하는 경향이 있습니다. 이를 막기 위해 top-k loss가 제시되었으나 [1], top-k loss는 loss가 convex하지 않아 gradient descent를 통한 minimization이 보장되지 않습니다.

  1. Average loss: \L{}_\text{avg}(\{\ell_i(f(x_i), y)\}_{i=1}^n)=\frac{1}{n}\sum_{i=1}^n \ell_i(f)
  2. Maximum loss: \L{}_\text{max}(\{\ell_i(f(x_i), y)\}_{i=1}^n)=\max_{1 \leq k \leq n} \ell_i(f)
  3. Top-k loss: \L{}_\text{top-k}(\{\ell_i(f(x_i), y)\}_{i=1}^n)= \ell_{[k]}(f)^2

 저자들을 average loss와 maximum loss의 일반화된 모델로서 ‘average top-k loss(AT-k loss)’를 제시합니다. AT-k loss는 전체 individual loss 중 가장 큰 k 개(top-k)의 평균을 구합니다. 수식은 다음과 같습니다.

 \L{}_\text{avt-k}(\{\ell_i(f)\}_{i=1}^n)=\frac{1}{k} \sum_{i=1}^k \ell_{[k]}

 AT-k loss는 average loss와 maximum loss의 특징을 섞은 aggregate loss로, average loss와 maximum loss 둘의 단점을 모두 완화할 수 있습니다. 아래는 논문에 제시된 synthetic dataset에서의 binary classification 학습을 각 aggregate loss로 비교한 결과입니다.

스크린샷 2018-04-24 오후 8.39.55

그림 1. Synthetic dataset에서의 aggregate loss의 비교

 4개의 실험 결과 중, 위의 두 실험은 데이터의 분포가 multimodal인 경우, 아래 두 실험은 레이블이 심하게 불균형인 상황입니다. 왼쪽의 위아래 두 실험은 hinge loss, 그리고 오른쪽은 logistic loss의 결과이고, outlier 샘플은 큰 x로 표시되어있습니다. 우선 위의 두 실험에서 average loss는 outlier에는 강하게 동작하나, 붉은 데이터의 작은 mode는 잘 분류하지 못합니다. maximum loss는 이런 작은 mode도 분류를 잘 하긴 하나, outlier 때문에 좋은 성능을 내지 못합니다. 아래의 두 실험에서는 average loss가 레이블의 불균형 때문에 제대로 학습되지 못합니다. Maximum loss에서는 이전 실험과 마찬가지로 outlier의 영향을 크게 받는 경향을 보입니다. 반면 AT-k loss로 학습된 분류기는 옅게 색칠된 최적 Bayes 분류기와 가장 가깝게 위치하며, 가장 좋은 성능을 내는 것을 볼 수 있습니다. 적절한 k 의 값은 grid search로 찾으며, 적절한 k 에서 AT-k loss는 maximum loss ( k=1 )일 때와 average loss ( k=n )일 때보다 성능이 좋거나 같습니다.

 저자들은 AT-k loss가 실제로 좋은 학습 loss임을 다양한 증명을 통해 검증합니다. 저자들의 증명에 따르면 (1) AT-k loss는 convex하며, (2) AT-k loss 기반 SVM은 현존하는 다양한 SVM 모델들을 일반화할 수 있습니다. 또, (3) AT-k loss는 classification calibration 특성이 있고, (3) 앞의 AT-k-SVM은 error가 bounded 되어있습니다. 모든 증명들은 논문의 appendix에서 자세하게 다루고 있으나, 이 포스트에서는 증명의 내용들을 간략하게 설명하도록 하겠습니다.

2. Formulation & Interpretation

  • AT-k Loss의 convexity

 Aggregate loss function이 individual loss들에 대하여 convex하면 gradient descent를 통해 해를 효율적으로 구할 수 있습니다. 그러나 AT-k loss는 individual loss들간의 sorting이 필요하므로, non-convex해 보일 수 있습니다. 만약 aggregate loss가 non-convex하다면 단순한 gradient descent로는 최적의 해를 얻을 수 없습니다. Appendix에 수록된 lemma 1에서 저자들은 linear programming로 풀어, AT-k loss를 \lambda에 의한 ‘shifted & truncated by hinge function’으로 재정의하고 AT-k loss가 convex함을 보입니다.

\L{}_\text{avt-k}(L_\bold{z}(f))=\frac{1}{k} \sum_{i=1}^k \ell_{[k]}\propto \min_{\lambda \geq 0}{\{\frac{1}{n} \sum_{i=1}^n [\ell_i(f)-\lambda]_+ + \frac{k}{n} \lambda \}}

스크린샷 2018-04-24 오후 9.44.19

그림 2. Shifted & truncated hinge function

 Individual loss level에서 저러한 AT-k loss는 이상적인 ‘0-1 loss’와 유사한 성질을 가지고 있습니다. Classification 문제에서 0-1 loss란 ‘올바르게 분류된 예시에서는 0의 penalty를 주고, 틀린 경우에는 상수 1의 penalty를 주는’ loss입니다. 이는 분명 이상적인 loss이지만, 연속적이지도 않고 convex하지도 않아 실제로는 사용할 수 없습니다. 아래는 여러 individual loss function들의 비교입니다. Shifted & truncated hinge loss는 잘 분류된 경우( z=yf(x) > 0 )에는 penalty가 매우 작습니다. 즉, AT-k loss는 그림 1 아래 실험에서의 average loss와는 달리 올바르게 분류된 샘플에 penalty를 잘 주지 않습니다.

스크린샷 2018-04-25 오전 10.43.57.png

그림 3. Individual loss level에서 본 shifted & truncated hinge function으로서의 AT-k loss

 파라미터 w 로 구성된 모델 f 에 대하여 individual loss가 w 에 대하여 convex할 때, AT-k loss의 최소화 문제는 아래와 같이 정의되며, 밑의 gradient descent로 최적화할 수 있습니다. (저자들은 이를 minimization of AT-k loss, MAT-k learning이라고 소개합니다.)

스크린샷 2018-04-25 오전 10.45.23

스크린샷 2018-04-25 오전 10.45.35

  • AT-k-SVM

Individual hinge loss를 사용하는 AT-k loss로 재생산 커널 힐버트 공간 (Reproducing Kernel Hilbert Space) H_K 의 멤버인 f 에 대해 다음과 같은 SVM을 모델링할 수 있습니다.

스크린샷 2018-04-25 오전 10.48.27

이는 정리하면 다음과 같습니다.

스크린샷 2018-04-25 오전 10.48.38

이때 이 모델은 k=n 일 때, 일반적인 C-SVM [2]과 같고, C=1 이고 모든 i 에 대해 K(x_i, x_i) \leq 1 이면 ν-SVM [3]으로 환원됩니다.

3.  Statistical Analysis

  •  Classification Calibration

\eta(x)=\text{Pr}(y=1|x) 인 Bayes rule f_c(x) = \text{sign}(\eta(x)-\frac{1}{2}) 을 정의하면, 이 f_c(x) 은 주어진 데이터에 대한 가장 강력한 binary classifier라고 볼 수 있습니다. 어떤 loss \ellclassification calibration 성질이 있다는 것은 f_c(x) \neq 0 이며 f^{*}_{\ell} = \inf_f \mathcal{E}_\ell(f)=\inf_f \mathbb{E}[\ell(yf(x))] 일 때, \text{sign}(f^{*}(x)) = \text{sign}(f_c(x)) 임을 의미합니다. 이는 충분히 많은 데이터로 최적의 해를 구했을 때, binary classification에서 Bayes rule과 같은 부호, 즉 같은 class(+1 또는 -1)를 준다는 것을 의미합니다. 데이터 샘플이 무한히 많으며 ( n \rightarrow \infty ),  그에 맞는 적절한 수 k 를 구했을 때 (  \frac{k}{n} \rightarrow \nu ), AT-k loss는 아래와 같이 환원됩니다.

스크린샷 2018-04-25 오전 11.33.55

스크린샷 2018-04-25 오전 11.34.06

여기에 추가로 \ell 이 convex하고 0에서 미분가능하며 \ell'(0) < 0 이면 위의 식으로부터 AT-k loss이 classification calibrated함을 도출할 수 있습니다. 이는 maximum loss ( k=1 인 AT-k loss) 와는 차이가 있는데, maximum loss가 어떤 데이터에서 classification calibration을 따른다면 데이터는 분명하게 구분되는 특성을 지녀야만 (  \frac{1}{n} \approx \nu \geq \mathcal{R}^{*} = \inf_f \mathcal{R}(f) = \inf_f \text{Pr}(y \neq f(x)) ) 합니다. 이런 면에서 AT-k loss는 더 robust하게 사용할 수 있습니다.

  • AT-k-SVM의 Error bound

과도한 오분류 에러(the excess misclassification error)는 \mathcal{R}(x)=\text{Pr}(y \neq f(x)) 일 때,  \mathcal{R}(\text{sign}(f_\bold{z}))-\mathcal{R}^{*} 로 정의할 수 있습니다. 이는 학습된 classifier의 에러가 최적의 Bayes 에러 ( \mathcal{R}^{*} )보다 더 큰 정도를 의미합니다. 앞에서 설명한 AT-k-SVM은 이러한 분류 오류가 전체 데이터 크기인 n이 충분히 크면 Bayes 에러에 높은 확률로 근사하게 됩니다. Error의 통계적 bound가 존재하므로, AT-k-SVM의 성능은 높은 확률로 보장된다고 볼 수 있습니다.

스크린샷 2018-04-25 오후 3.56.04.png

4. Experiments

이론적으로는 분명 좋은 loss인 것으로 보이나 실제로도 그것이 적용되는지 확인이 필요하기 때문에, 저자들은 binary classification 문제와 regression 문제에서 각각 AT-k loss를 average 및 maximum loss와 비교하여 성능을 평가했습니다. 다른 조건들을 최대한 단순하게 하기 위해 균질 선형 예측함수( f(x;w)=w^Tx )와 Tikhonov regularizer( \Omega(w)= \frac{1}{C}||w||^2 )를 사용했습니다. 학습은 앞에서 제시된 gradient descent 방법을 그대로 적용했습니다.

  • Binary classification

스크린샷 2018-04-25 오후 4.01.50.png

표 1. Binary classification의 각 aggregate loss 성능 비교

모든 경우에서 AT-k loss는 가장 좋은 성능을 보입니다. 이는 maximum 및 average loss가 모두 AT-k loss의 k=1k=n 인 특수한 경우들이기 때문에, 최적의 k 를 구한다면 성능은 항상 좋거나 같게 됩니다.

스크린샷 2018-04-25 오후 4.13.02.png

그림 4. k 및 individual loss에 따른 성능 비교

  • Regression

스크린샷 2018-04-25 오후 4.15.40

표 1. Regression의 각 aggregate loss 성능 비교

 Regression은 square 및 absolute loss를 사용하여 학습하고, test시에 Root mean square error (RMSE)를 측정합니다. Square loss와 AT-k loss를 사용한 경우가 가장 RMSE가 낮고, absolute loss에서도 AT-k loss가 가장 낮은 RMSE를 보입니다.

4. Discussion

저자들은 이 논문에서 AT-k loss를 소개하였고, 이를 다양한 증명을 통해 분석했습니다. 또, AT-k-SVM과 MAT-k learning이라는 지도 학습에 적용법 제시하였고 성능에 대하여도 분석했습니다. 저자들은 이 논문에서는 단순한 gradient descent를 통하여 학습을 하였으나, 더 강력한 최적화 방법을 사용하는 것도 현재 연구 중이며, 비지도 학습 및 딥러닝으로의 적용도 중요한 주제가 될 수 있을 것이라 언급합니다. 실제로 논문에서 적용한 모델은 단순한 선형 모델이고 이는 파라미터 w 에 대하여 convex 하지만, 현재 사용되는 딥러닝 모델들은 모두 non-convex 합니다. 논문과 같은 수학적인 증명은 다소 어렵겠지만, 데이터가 불균형적이거나 multimodal인 상황에서 딥러닝 학습에 실제로 도움이 되는지, 더 나아가 다양한 아키텍처에 따라 AT-k loss의 결과가 어떻게 다른지를 알아보는 것도 흥미로운 주제일 것 같습니다.

References
[1] S. Shalev-Shwartz and Y. Wexler. Minimizing the maximal loss: How and why. In ICML, 2016.
[2] C. Cortes and V. Vapnik. Support-vector networks. Machine learning, 20(3):273–297, 1995.
[3] B. Scholkopf, A. J. Smola, R. C. Williamson, and P. L. Bartlett. New support vector algorithms. ¨ Neural computation, 12(5):1207–1245, 2000.

Posted by:Inwan Yoo

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s