Learning with Average Top-k Loss
이 포스팅은 루닛 블로그에 2018년 4월에 올렸던 포스트입니다. 수식이 많은 analysis 부분은 생략했습니다. 생략된 부분은 아래 원문에서 확인가능하십니다. (https://blog.lunit.io/2018/04/27/learning-with-average-top-k-loss/)
1. Introduction
주어진 데이터로 예측 모델을 만들기 위해서는 적절한 loss function이 필요합니다. 이번 포스트에서는 2017년 NIPS에서 포스터로 발표된 논문인 “Learning with Average Top-k Loss”에 대해 소개하고자 합니다.
지도 학습(supervised learning)은 주어진 data 및 feature x로부터 target y를 예측하는 기계학습의 큰 분야로, 다음의 최소화 문제를 푸는 과정을 다룹니다.
위 식의 왼쪽 항은 ‘individual loss’를 통합하는 ‘aggregate loss’이며 오른쪽은 regularizer입니다. 여기서 individual loss란 개별 샘플(x, y)에 대한 loss function입니다. 예를 들어, binary classification 문제에서는 hinge loss, logistic loss 등이 있습니다. Regression 문제에서는 square loss 및 absolute loss 등이 사용됩니다.
Aggregate loss로 가장 흔히 쓰이는 것은 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이 보장되지 않습니다.
저자들을 average loss와 maximum loss의 일반화된 모델로서 ‘average top-k loss(AT-k loss)’를 제시합니다. AT-k loss는 전체 individual loss 중 가장 큰 k개(top-k)의 평균을 구합니다. 수식은 다음과 같습니다.
AT-k loss는 average loss와 maximum loss의 특징을 섞은 aggregate loss로, average loss와 maximum loss 둘의 단점을 모두 완화할 수 있습니다. 아래는 논문에 제시된 synthetic dataset에서의 binary classification 학습을 각 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를 λ에 의한 ‘shifted & truncated by hinge function’으로 재정의하고 AT-k loss가 convex함을 보입니다.
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를 잘 주지 않습니다.
파라미터 w로 구성된 모델 f에 대하여 individual loss가 w에 대하여 convex할 때, AT-k loss의 최소화 문제는 아래와 같이 정의되며, 밑의 gradient descent로 최적화할 수 있습니다. (저자들은 이를 minimization of AT-k loss, MAT-k learning이라고 소개합니다.)
- AT-k-SVM
Individual hinge loss를 사용하는 AT-k loss로 재생산 커널 힐버트 공간 (Reproducing Kernel Hilbert Space) H_k의 멤버인 f에 대해 다음과 같은 SVM을 모델링할 수 있습니다.
이는 정리하면 다음과 같습니다.
이때 이 모델은 k=n일 때, 일반적인 C-SVM [2]과 같고, C=1이고 모든 i에 대해 K(x_i, x_i) ≤ 1이면 ν-SVM [3]으로 환원됩니다.
3. Experiments
이론적으로는 분명 좋은 loss인 것으로 보이나 실제로도 그것이 적용되는지 확인이 필요하기 때문에, 저자들은 binary classification 문제와 regression 문제에서 각각 AT-k loss를 average 및 maximum loss와 비교하여 성능을 평가했습니다. 다른 조건들을 최대한 단순하게 하기 위해 균질 선형 예측함수와 Tikhonov regularizer를 사용했습니다.
학습은 앞에서 제시된 gradient descent 방법을 그대로 적용했습니다.
- Binary classification
모든 경우에서 AT-k loss는 가장 좋은 성능을 보입니다. 이는 maximum 및 average loss가 모두 AT-k loss의 k=1 및 k=n인 특수한 경우들이기 때문에, 최적의 k를 구한다면 성능은 항상 좋거나 같게 됩니다.
- Regression
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.
