이번 포스트에서 리뷰할 논문은 Chien-Liang Liu와 Yu-Hua Chang이 작성한 'Learning From Imbalanced Data with Deep Density Hybrid Sampling'이다. 논문은 아래 사이트에 기재되어 있다.

https://ieeexplore.ieee.org/document/9723474

Learning From Imbalanced Data With Deep Density Hybrid Sampling

Learning from imbalanced data is an important and challenging topic in machine learning. Many works have devised methods to cope with imbalanced data, but most methods only consider minority or majority classes without considering the relationship between

ieeexplore.ieee.org

 어떤 대회에서 이진 분류 task가 주어진다면 그 대회는 imbalance data일 확률이 높다. 저번 LG Aimers 4기 문제였던 영업 전환 여부를 구하는 문제도 imbalance한 문제였고 현재 kaggle playground에서 active한 대회인 binary classification of insurance cross selling 역시 그러하다. 저번 공모전에서는 SMOTE와 이를 응용한 방법, 모델에 scale_pos_weight 같은 minority calss의 loss에 가중치를 부여하는 방식 사이에서 고민을 많이 했는데 이 논문을 읽고 나서 이런 imbalance에 대처하기 위해 진행된 연구가 내 생각보다 많이 진행되어있었다. 위 논문은 간단히 말하면 auto-encoder의 idea인 latent space를 활용해서 oversampling과 undersampling을 동시에 수행하는 method이다. 이제 자세히 알아가보자.

Abstract

  •  Machine learning에서 imabalance data로부터 학습하는 것은 중요하면서 어려운 주제이다.
  • 하지만 대부분의 방법은 minority class와 majority class간의 relationship은 고려하지 않는다.
  • 또한 oversampling 방법은 original feature space에서 합성하고 neighbors 판단하는 기준이 Euclidean distance이다. 
    • Euclidean distance는 high-dimensional space에 적합하지 않다고 지적
  • 우리는 새로운 방법인 deep density hybrid sampling(DDHS)를 제안한다.
    • Embedding network를 통해 data samples를 low-dimensional separable latent space에 project 한다.
    • 목표는 class간 proximity(가까움)을 data projection시 유지하려 하고
    • within-class와 between-class concepts에서 고안한 loss functions을 사용한다.
    • density를 통해 minority, majority samples를 구하고
    • feature-level approach를 통해 선택된 minority samples로부터 다양하고 유용한 합성의 samples를 만든다.
  • 다양한 실험 환경에서 제안한 방법이 전도 유망하면서 안정적인 결과를 도출해 냈다.
  • 제안하는 방법은 data-level algorithm이기 때문에 boosting technique과 결합할 수 있었고 그 방법인 DDHS-boosting이다. 이 역시 좋은 결과를 가져옴.

1. Introduction

  • Learning from imbalanced data에 대해 보완책을 마련해야하는 이유는 대부분의 machine learning algorithms이 balanced class를 가정하기 때문이다.
    • 따라서 대처가 없다면 classifers는 majority class에 biased 됨.
    • 이 문제는 많은 domains에서 나타남.
  • 많은 방법들이 고안되었지만 high-dimensional, imbalanced dataset에서 stable performance를 달성하는 것은 여전히 어려운 문제임.
    • Random sampling methods(oversampling, undersampling)
      • oversampling -> overfitting 위험성
      • undersampling -> valuable information을 제거할 위험성
    • Synthetic minority oversampling technique(SMOTE) 
      • minority sample과 그들의 k-nearest neighbors에 linear interpolation을 사용하여 oversampling하는 기법
      • minority class만을 오직 고려한다는 점, high-dimensional space에서 부정적인 성능을 가져온다는 점이 문제임.
    • Hybrid methods of oversampling and undersampling
      • oversampling과 undersampling을 결합하여 접근하는 방식
      • original data distribution이나 characteristices를 해치는 arbitrary data samples를 제거한다.
  • Article에서 주장하는 deep density hybrid sampling(DDHS)는
    • embedding network를 학습하여 data samples를 low-dimensional separable latent space에 project 한다.
    • project할 때 목표는 data projection시 class간 proximity를 유지하는 것
    • within-class와 between-class concepts으로 이끌어낸 loss fucntion을 사용한다.
    • density를 기준으로 high quality의 samples를 구하고
    • feature-level method를 통해서 선택된 minority samples에서 훌륭한 samples를 만들어낸다.
  • 다른 sota methods와 비교했을 때 유망하고 안정적인 결과를 가져옴.(low, high dimension 가릴 것 없이)
  • 제안된 방법은 data-level algorithm이기 때문에 boosting technique과 결합할 수 있었고 그 방법이 DDHS-boosting임. 이 역시 좋은 결과를 가져옴.
  • 제안한 방법이 공헌하는 바는 다음과 같음.
    •  imbalanced data 문제를 다루는 새로운 method
      • key idea: data projection시 class proximity를 유지하는 것
      • density를 통한 선택을 통해 high quality samples만 남긴다.
    • 방대한 실험을 통해 제안된 방법이 low, high dimenstion에서 모두 좋은 성능을 보인 것.
    • 제안된 방법을 분석하기 위해 추가적인 실험들을 수행함. + boosting technique과의 결합

2. Related Work

  • Imbalanced data problems를 다루기 위한 방법들은 크게 data-level, algorithm-level, ensemble learning, deep learning approaches로 나뉜다.
  • Data-Level Methods
    • key idea: class distributions를 balancing하여 classifiers가 bias 하지 않게 만들자!
    • 어느 classifier에 적용될 수 있기 때문에 활용성이 큰 장점이 있다.
    • random sampling
      • oversampling
        • minority class의 data를 복제한다.
        • overfitting에 취약함.
        •   
          oversampling
      • undersampling
        • majority class의 data를 제거한다.
        • 실제 데이터 분포를 잘 나타내는 samples를 제거할 수 있는 위험이 있음.
        • undersampling
      • hybrid methods
        •  oversampling + undersampling
        • hyprid methods
    • SMOTE(Synthetic Minority Over sampling Technique)
      • minority class의 두 data samples 사이의 line segment 사이의 data로 생산한다.
      • generated data samples가 제한된다는 단점(why? line segment 이외의 요소를 만들 수 없으니까)
        • sol) model-based synthetic sampling(MBS)
          • feature relationships을 capture 하기 위해 linear regression을 사용
          • feature relationship을 기반으로 합성 samples를 생성
      • SMOTE(빨간선 이외의 sample을 생성하지 못하는 단점.)
      • 알고리즘상 k nearest neigbors를 고르는 distance metric에 의존함.
        • 일반적으로 Euclidean distance를 고르지만 high-dimenstional space에서 두 데이터 사이의 거리를 정확하기 측정할 수 없음.
          • why? 차원의 저주(Curse of Dimensionality) 때문임.
            • 고차원의 데이터가 가지는 문제로 다음을 포함함.
              • 데이터 희소성: 차원이 증가할수록 데이터 포인트들이 점점 희소해지는 현상
              • 거리 측정의 비유효성: 고차원 공간에서는 모든 점들 사이의 거리가 거의 동일해지는 경향이 있음.(최소 거리와 최대 거리 사이의 차이가 작아짐.)
              • 노이즈 민감도: 고차원 공간에서는 노이즈가 축적되는 경향
              • 계산 복잡도 증가
            • high dimensions에서 일어나는 일들이 궁금해서 더 찾아봤는데  "A Few Useful Thing to Know about Machine Learning" by Pedro Domingos at the University of Washington에서 Intuition Fails in High Dimensions를 읽어보니 차원이 커질 때 일반화하는 것이 어렵고 중요하지 않는 features가 중요한 features보다 많다면 그 영향을 가려버린다고 한다. -> 예측 어려워짐. 뿐만 아니라 중요한 features가 많더라도 차원이 많아지면 가깝다고 판단하는 데이터들 역시 많아져(격자에서 d만큼 떨어진 게  1차원은 2개, 2차원은 4개, 3차원은 8개..) 가까운 몇 개를 정하는 일이 쉬운 일이 아니다. 이외에도 차원이 늘어나면 hypercube로 근사할 때의 오차, classifier가 reasonable frontier 찾기 어려움 등의 문제가 있다.(그런데 이런 문제들이 대부분 어떤 전제(uniformly distributed)를 가정하기 때문에 정확하지 않을 수 있고 생각보다 해결이 쉬울 수도 있다. 실제로 위 글의 마지막 부분에 handwritten digit recognition에서 대부분의 data들이 lower dimensional manifold(데이터가 존재하는 영역)에 존재해 dimension을 줄이는 algo.(ex. PCA)를 쓰면 완화할 수 있다고 한다.)  
            • Charu C. Aggarwal, Alexander Hinneburg, Daniel A. Keim, "On the Surprising Behavior of Distance Metrics in High Dimensional Space"(2001) 이 논문은 어떤 전제하에 선 the ratio of the distances of the nearest and farthest neighbors to a given target in high dimensional space가 1에 가까워지는 문제를 L_k에서 k가 작을 때(k=1이면 Manhattan, k=2이면 Euclidean) 완화되어서 L_k(k <1)라는 fractional distance norms를 써야 한다라고 주장하는 논문인데 바로 반박하는 "Fractional norms and quasinorms do not help to overcome the curse of dimensionality" by Mirkes, Allohibi, & Gorban (2020) 논문이 있어 연구가 더 필요해 보인다.
            • 해결책까진 완벽하진 않지만 확실한 건 고차원에서 단순 Euclidean distance로 similar를 다루는 것은 지양한다.
            • 더 많은 내용은 https://stats.stackexchange.com/questions/99171/why-is-euclidean-distance-not-a-good-metric-in-high-dimensions를 참고..
          • + 논문 스터디 참가자 중 한분이 말씀하신 대로 categorical data에서 과연 Euclidean distance가 무슨 의미를 갖는지? 에 관한 고찰도 동의한다. 임의로 부여하는 순서와 값들로 이 변수들의 가깝고 멂을 나타내는 것은 타당하지 않기 때문(마치 categorical data를 레이블 인코딩할 때의 단점)!
    • ADASYN(Adaptive Synthetic Sampling, 논문엔 없지만 이 아이도 유명해서 넣음.)
      • SMOTE를 확장해 minority class sample 주변에 majority class가 많이 분포해 있으면 더 많이 생성하는 방식
      • 경계에 위치한 minority samples를 더 생성하는 것이 목적 
    • Tomek link
      • overlapping samples를 제거하는 방식인 undersampling methods
      • overlapping을 정의해야 함.
        • minority sample a와 majority sample b가 있다 하고 d(a, b)를 둘 사이의 거리로 정의하자. 이때  a에  b 보다가 가운 majority sample이 없고 b에 a보다 가까운 minority sample이 없을 때 두 sample의 쌍을 Tomek link라 한다. 그럼 a와 b의 두 classes의 경계에 있는 것이므로 major sample b는 제거돼야 한다.
        •  
    •  borderline-SMOTE
      • SMOTE를 확장한 버전으로 idea는 Tomek link와 같다.
      • SMOTE는 모든 minority sample을 동등하게 보지만 경계에 있는 samples는 잘못 분류될 확률이 높기 때문에 더 중요하게 다루어야 한다.
      • 따라서, minority data를 safe level, danger level, noise level로 나누고 danger level에 해당하는 data들로 합성 samples를 만든다.
    • safe-level-SMOTE
      • SMOTE에서 생기는 class overlap을 지적함.
      • minority class의 모든 sample들은 safe score을 할당받음.
      • safe score를 기반으로 다양한 경우에 따라 합성 samples를 만들어서 합성 samples가 안전한 영역에 분포되게 함.
    • noise reduction a priori synthetic(NRAS)
      • noise reduction과 data generation에 기반한 oversampling method
      • non-noise minority samples로 합성 data samples를 만든다.
    • kernel density estimation(KDE)
      • random oversamppling은 underlying data distributions를 고려하지 않고 data samples를 만드는 것을 지적함.
      • nonparametric method(비모수 방법)
        • 데이터의 기저 분포나 특정 모수를 가정하지 않는 통계적 기법
      • kernel homogeneous funtions를 모아 평균 내어 density function을 추정한다.
      • minority class의 분포를 추정하고 추정한 분포로부터 데이터를 합성하는 방식
      • 아래에서 좀 더 자세히 다루겠음.
  • Algorithm-Level Methods
    • key idea: class별로 misclassification costs에 차이를 두어 classifiers가 minority class에 더 집중하게 만들자!
    • 만약 positive가 minority class라 가정하면 FN(P를 N으로 예측하는)이 FP에 비해 더 높은 cost를 가지는 방식 = cost-sensitive loss function
    • Sun이 주장한 meta-techniques
      • three cost-sensitive boosting algorithms
        • cost-sensitive learning with AdaBoost
    • Zhou and Liu가 주장한 methods
      • sampling과 threshold-moving, soft-ensemble을 통한 cost-sensitive neural networks 구현
    • complementary neural network(CMTNN)과 SMOTE를 결합한 방식
      • undersampling과 oversampling 기법을 결합
      • CMTNN은 Truth NN과 Falsity NN이라는 feedforward NN을 통해서 misclassified data samples를 찾고 제거한다.
  • Ensemble Methods
    • key idea: 이미 우리 알고 있는 bagging, boosting 같은 ensemble methods와 엮어보자! 
    • SMOTEBagging
      • bagging과 SMOTE 기법의 결합
      • 합성 샘플을 다양화하고 majority vote로 분류한다.
    • SMOTEBoost
      • boosting algo. 와 SMOTE를 결합
      • 매 boosting iteration마다 minority class의 합성 sample을 생성한다.
    • RUSBoost
      • 위 두 방식은 oversampling 기법, RUSBoost는 random undersampling에 기반
      • training time을 줄이고 AdaBoost와 결합하여 성능이 향상된다.
    • self-paced ensemble(SPE)
      • classification hardness = classifier가 정확히 예측한 예측을 기반으로 측정하는 classifier의 난이도를 측정하는 개념
        • noise가 많으면 어려운 거임.
      • imformative majority samples를 selecting 해서 얻는 hardness value를 기반으로 학습하는 방법
      • undersampling 기법
      • distance metric에 대한 고민 필요 없음.
  • Deep Learning
    •  key idea: deep neural networks를 통해 feature representations를 학습하고 classification tasks를 동시에 수행하는 것
    • deep learning 역시 balanced class distribution을 기반으로 만들어짐.
    • Buda 등은 CNN에서 imbalance가 야기하는 문제를 지적하고 oversampling이 dominant method임을 밝힘.
    • Havaei 등은 two-phase training을 제안함.
      • transfer learning technique
      • first phase: balanced dataset을 통한 pretrain
      • second phase: fine-tuning technique을 통해 representative distribution을 만듦
    • He 등은 cost-effective semisupervised learning with crowd framework(CSLC)를 제안함.
      • two sampling strategies와 cost-sensitive crowd labeling approach를 축적한 multivariate time series에 집중함.
    • Wang 등은 AUC maximization과 extreme learning machines(ELMs)를 결합함  -> AUC-ELM
      • SAUC-ELM은 imbalanced binary classification을 다룸.
    • Khan 등은 cost-sensitive deep neural network(CoSen)을 제안
      • network parameters와 class-sensitive costs를 동시에 optimize하는 방법을 제안. -> algorithm-level method이기도 함.
    • Arefeen 등은 undersampling methods인 NUS-1과 NUS-2를 제안함.
      • neural networks에 기반하여 minority class에 overlap 하는 majority samples를 제거하는 방식임.

3. Proposed Method

  • 많은 data-level methods는 SMOTE의 개념을 확장한 방법인데 imbalanced and high-dimensional datasets를 만나는 경우 두 가지 문제점이 존재
    • 1. minority samples만을 고려하고 majority class에서 오는 영향을 무시함.
    • 2. high-dimensional datasets에선 Euclidean distance가 data 간 거리를 정확히 측정하지 못함.
  • 많은 learning models는 data를 optimal lower-dimensional representation에 projecting하는 것이 이득임을 알려줌.
    • projection은 spectral clustering을 도와 optimal neighbors를 알게 해 준다.
      • spectral clustering: 그래프 이론에 기반한 클러스터링 알고리즘으로, 라플라시안 행렬을 사용한 projection을 통해 데이터 간의 유사도를 바탕으로 클러스터링을 수행한다.
      • 'optimal neigibor를 알게 해 준다'는 것은 그 데이터 포인트에 가까운 것을 찾는 것을 의미함.
    • 내재적인 cluster structure을 밝혀내게 해 준다.(고차원에서 안 보였던 것들이 보이는 느낌..)
    • terms 사이 계산이 더 정확해진다.(차원의 저주 완화)
  • 그러므로, 우리는 다음의 steps를 가진 DDHS를 제안한다.
    • learnable embedding network를 통해 data points를 low-dimensional separable latent sapce에 project한다.
      • separable은 서로 다른 클래스의 데이터 포인트들이 잘 구분됨을 의미
      • 따라서 class proximity(동일한 클래스에 속하는 데이터 포인트들이 가깝게 위치함.)를 유지
    • density를 통해 high-quality data samples를 고름
    • feature-level oversampling을 통해 minority samples를 합성함.
    • 합성된 samples가 요구 사항을 충족하는지 검증
    • minority samples와 합성된 samples를 합함. majority samples 중 density criterion을 만족하는 samples만 사용
      • minority class oversampling, majority class downsampling이 동시에 수행되므로 hybrid approach임.
  • Notation
    • D: 원래 feature vector 차원
    • m: training examples 개수
    • d: projected data point의 차원
    • positive가 minority class라 가정
  • Embedding Network
    • autoencoder를 확장시킴
    • Traditional autoencoder
      • encoder와 decoder로 이루어짐
      • encoder는 original data를 low-dimenstional latent representation으로 바꾸는 역할
      • decoder는 latent representation을 original data로 reconstruction 하는 역할
      • 목표는 reconstruction loss를 최소화하는 것으로 encoder와 decoder를 동시에 optimize 함.
reconstruction loss

 

  • labeled data를 동반하는 문제들은 training process에 label information을 활용하면 prediction performance가 향상되니 label information을 통해 class proximity 성질을 유지하면서 latent space를 학습하게 설계함.(reconstruction loss를 사용해 보다 정확하게 재구성하게 한다.) 
  • 이 접근은 세 가지 loss functions를 갖는데
    • reconstruction loss
      • autoencoder에 사용되는 loss로 MSE를 사용한다.
      •  
      • 잠재 공간으로부터 재구성한 공간을 학습하는 term으로 데이터에서 노이즈를 제거할 기반을 마련한다. 
    • 그다음은 between-class loss와 within-class loss로 class proximity를 유지하는 것이 목표이다.
      • between-class loss는 다른 classes의 data points는 가능한 한 멀게 만드는 것이 목표
      • within-class loss는 같은 class의 data들이 가깝게 만드는 것이 목표
      • 제안한 방법은 cross-entropy loss를 between-class loss로, center loss를 within-class loss로 설정함.
      • cross-entropy loss
      • cross-entropy loss는 data가 incorrect classes로 분류되었을 때 더 많은 penalty를 부과한다.
      • center-loss
      • centor-loss는 class center로부터 data가 멀리 떨어져 있을 때 더 많은 penalty를 부과한다.
      • 데이터들의 class의 center로 모이게 하는 효과
    • 제안한 방법은 세 가지 loss를 모두 결합하여 latent space에서 separable latent space를 만드는 represenations를 학습하는 것임. 
    • latent space의 차원은 orginal feature space의 차원보다 충분히 작아 고차원에서 일어나는 문제들을 완화할 수 있음. 
    • 따라서 최종 loss 식은 다음과 같음.
  • Density-Based Filtering
    • embedding network 학습이 끝난 후 latent sapce로 data들을 옮긴 다음 density를 통해 high-quality data points를 선별한다.
      • low-density data point는 다른 data points부터 멀리 있는 영역에 있는 점들을 말하고 noise일 확률이 높다.
      • high-density data point는 cluster를 잘 대표하는 data일 가능성이 높다.
    • 즉, high-density area를 선별하고 high-quality 데이터들을 얻는 것.
    • 저자들은 KDE를 통해 points들의 density를 계산하였다. 위에서도 잠깐 언급하였지만 KDE는 nonparameteric method로 random variable의 PDF를 추정하는 방식인데 각 data에서 PDF의 모양을 결정하는 kernel function과 각 density의 폭을 결정하는 bandwidth parameter가 중요하다.
    • Gaussian kernel은 class의 중심에 데이터가 모여있을 때 그 지점의 PDF가 높은 값을 갖게 하고 strong computational advantages를 가지기 때문에 선택하였다.
      • 뒤의 discussion에서 자세히 다룸.
    • bandwidth h는 Scott's rule을 통해 계산되었다.
    • density를 계산하는 방법을 좀 더 자세히 살펴보면 majority class와 minority class의 densities를 각각 계산하고 quartile of density를 통해 high-quality samples를 추출하였다. majority class의 경우 Q2 이상의 desnity보다 큰 density를 갖는 samples로 선정하였고 minority class의 경우 더 높은 Q3 이상의 density보다 큰 density를 갖는 samples로 선정하였다.
    • 즉, 25%의 minority samples는 high-quality로 선정되어 generation process로 넘어가고 나머지 75%는 classifier training process에만 활용되었다. majority의 경우 50%만 훈련하는 데 사용함.
  • Generation of Synthetic Samples
    • 다양하고 유효한 samples를 만들기 위해 feature-level sampling technique을 사용하였다.
    • feature domain V = [v_1, ... , v_d]는 각 feature의 값들을 모아둔 list(ex. v_1은 1번째 latent feature의 값들을 모아둔 것)를 원소로 갖는 list이다.
    • 각 v_i에서 feature를 하나씩 뽑아 합성하는 방식으로 사용


    • 이미 존재하는 feature 값들로부터 만들기 때문에 생성된 samples feature의 값이 유효하고 random process로 다양한 합성 samples를 만들 수 있다는 것이 장점!
  • Verification of Synthetic Samples
    • 합성 후 synthetic samples가 good quality인지 검증하는 과정
    • 마찬가지로 density를 사용하여 density가 높은 곳은 class의 center, 낮은 곳은 class의 boudary를 나타낸다고 보았다.


    • 이 그림에서 c^M과 c^N은 각각 majority, minority class의 center이고 minority class(25%로 선택된 거)에서 center와 boundary 사이의 거리를 minority classes의 radius인 r^N으로 잡았다. 합성된 sample인 z^S가 있을 때 2가지 기준을 통해 검증하였는데
      • z^S가 c^M보다 c^N에 더 가까워야 한다.(minority class의 center에 더 가까워야 한다.)
      • z^S와 c^N의 거리는 r^N보다 작아야 한다.(minority class의 바운더리 안에 존재햐야한다.)이다.
    • 식으로 나타내면
  • Algorithm for DDHS
    • 알고리즘을 정리하면 다음과 같다.
    • input은 training data와 oversampling rate p, output은 classifier에 사용될 dataset이다.
    • line 1-4에서 embedding network가 훈련되어 discriminative space를 학습하고 그 network로 project한다.
    • line 5-6에서 density-based filtering(DBF)를 통해 high-quality samples를 선별하고 low-quality majority samples를 제거한다.
    • line 7-14에서 DDHS는 data generation process를 수행하고 synthetic data를 검증한다.
  • Time Complexity Analysis
    • 대부분의 시간은 embeddidng network를 훈련하는 데 사용됨.
    • embedding network는 autoencdoer와 fully connected layer로 이루어져 있고 autoencoder는 encoder와 decoder로 구성됨.(각각은 three layers로 구성)
    • encoder의 3 hidden layers의 unit이 n_1, n_2, n_3 순이고 fully connected layers의 뉴런이 n_f = n_3, decoder는 encdoer의 reverse구조, data samples가 m개, epoch가 e회, data sample의 dimension을 D라 하면 한 epoch당 forward pass의 time complexity는
      • O(2m(Dn_1+n_2n_3+n_2n_3)+m(n_3n_f+n_f*2)) -> 논문 식이 말이 안 된다고 생각해서 바꿔봤는데 다른 의견이 있으시면 남겨주세요.. 
      • 인데 n_f = n_3, n_f는 n_2보다 작음, backpropagation은 forward pass와 time complexity가 같음, 모든 뉴런의 개수는 상수이니 time complexity는 O(emD)이다.

4. Experiments

  • Datasets
    • 사용한 dataset은 다음과 같다.
  • Comparison Methods
    • 11개의 comparison methods와 아무것도 하지 않은 baseline method와 비교함.
    • 제안하는 알고리즘이 data-level algorithm이므로 다른 data-level algorithm과 비교함.
      • SMOTE, Oversampling, Undersampling, Borderline SMOTE 1, Borderline SMOTE 2, Tomek Link, SMOTE Tomek, Safe-level SMOTE, Gaussian SMOTE, NRAS oversampling, MBS
  • Experimental Setting
    • 실험은 두 parts로 나뉨.
      • random하게 training sets와 test sets를 10개의 다른 random seeds로 나눔.(random sampling에 의해 달라지는 효과를 완화하기 위해서)
      • 대부분의 data-level methods는 sampling technique을 수반하기 때문에 이 역시 random seeds의 영향을 받아 10개의 다른 random seeds로 수행함.
      • 따라서, 총 100번의 실험을 하고 평균 냄.
    • 분류기 부분에는 아무거나 쓸 수 있었는데 linear support vector machine(SVM), logistic regression을 사용함. 이유는
      • feature combinations이나 kernel tricks를 쓰지 않는 linear methods라 data quality에 잘 의존하기 때문
      • 실제 settings에서 주로 쓰이기 때문
    • oversampling과 undersampling ratios는 모두 100%
    • 제안하는 방법은 latent space의 dimension이 하이퍼파라미터인데 16을 기준으로 dataset을 high-dimensional, low-dimensional으로 나누고 high- dataset에서는 latent space의 차원을 16으로, low- dataset에서는 latent space의 차원을 2로 만들었다.
    • Embedding network의 구성을 좀 더 살펴보면
      • encoder와 decoder 모두 3-layer로
        • high-dimensional dataset에서
          • (input size, 256), (256, 64), (64,16)으로 층을 쌓았고
        • low-dimensional은 
          • (input size, 64), (64, 16), (16, 2)으로 층을 쌓았다.
        • hidden layers의 activation은 ReLU, output layer에서는 sigmoid function을 사용함.
  • Evaluation Metric
    • AUC와 AUPRC를 사용
      • AUC: ROC (Receiver Operating Characteristic) 곡선 아래의 면적을 나타내며, 분류 모델의 성능을 평가하는 지표. ROC 곡선은 참 양성 비율(TPR, True Positive Rate)과 거짓 양성 비율(FPR, False Positive Rate)의 관계를 그래프로 나타낸 것
      • AUPRC: Precision-Recall 곡선 아래의 면적을 나타내며, 특히 불균형 데이터셋에서 분류 모델의 성능을 평가하는 데 사용됨. Precision-Recall 곡선은 정밀도(Precision)와 재현율(Recall, 또는 TPR)의 관계를 그래프로 나타낸 것
  • Experiments Results
    • First experiments(wiht linear SVM)
      • 제안한 방법 좋은 성능을 보임.
      • extremely high-dimension datset인 Isolet에서도 좋은 성능을 보임.
    • Second experiment(with. logistic regression)
      • 마찬가지로 좋은 성능을 보임.
    • 추가로 Wilcoxon rank-sum test(검증 방법 중 하나)를 통해 실제로 우리가 제안한 방법이 다른 방법들보다 유의미하게 좋은지 판단해 보았는데 위의 Table 2와 Table 4에서 asterisk가 표시된 것이 유의미한 차이가 없는 것.(위에 표 보면 대부분 유의미한 차이가 있음)
    • 또한 model training 하는 과정에서 data points를 시각화해 보기 위해 PCA와 scaler를 통해 data points들을 이차원 공간에 표현해 보았다.(자세한 이야기는 없지만 latent sapce에서의 vectors에 PCA를 수행한 것 같다.)


      • 처음에서는 overlap이 심했던 dataset(위쪽 4개의 그림) embedding network를 지난 후(아래쪽 4개의 그림) 밀도가 높아지면서 분리가 된 것을 알 수 있다.

 

5. Discussion

  • Loss Functions in Embedding Network
    • 실제로 embedding network는 3개의 loss를 결합한 loss function을 사용하였는데 세 개를 다 사용하는 것이 아닌 다른 조합에서는 어떨지 궁금하여 추가적인 실험을 진행함.


    • 위 그림과 표를 참고하면 위 그림에서 (b)와 (g)에 해당하는 세 개의 loss를 모두 쓸 때 가장 잘 분리가 되었고 실제 지표로도 가장 높은 성능을 보임을 알 수 있다.
    • 또한 Table 6에서 추가적인 분석을 해보면
      • L_CE가 매우 중요한 loss임을 알 수 있음.(L_C와 L_R만 쓰는 경우 성능이 확 떨어진다.)
      • 그러나 L_C와 L_R 역시 도움이 되는 게
        • L_C는 class center에 모델의 latent 표현이 집중되도록 도와주고
        • L_R은 data의 noise를 줄이면서 latent 표현을 모델이 만들도록 도와주기 때문으로 분석
    • 시각화 자료에서 추가적인 분석을 해보면
      • L_CE는 between-class loss의 역할을 잘 수행하고 있고(그림 (b)와 (e), (g)와 (j)를 비교하면 L_CE가 없는 경우 두 class간 구분을 잘하지 못한다.)
      • L_C는 within-class loss의 역할을 잘 수행하고 있음.(그림 (b)와 (d), (g)와 (i)를 비교하면 L_C가 없는 경우 class가 density가 확 옅어짐.)
  • Ablation(제거) Study of Density-Based Filtering(DDF)
    • 제안한 알고리즘에서 density를 기준으로 high-quality data samples를 선택하는 과정이 있다. 이 discussion에선 이 제거가 어떤 영향을 미치는지 살펴보겠음.(DDF를 했을 때와 DDF를 하지 않았을 때를 비교)
    • 위 table 7에서 보면 DBF를 수행하였을 때 항상 성능이 개선됨을 알 수 있음.
  • Comparison With PCA and Its Variants
    • 사실 low-dimension에서 data를 다루는 가장 유명한 방법은 PCA이다. 그래서 이 discussion에선 제안한 방법과 PCA, PCA의 변형(Kernel PCA, supervised PCA)간의 성능 비교를 해보겠다.
    • 위 table 8을 보면 DDHS가 다른 방법들보다 좋은 성능을 보인다.
    • 이유를 생각해 보면 PCA와 kernel PCA는 project 할 때 label information을 사용하지 않고 Supervised PCA는 linear transformation을 사용하지만 DDHS는 label information과 data reconstruction을 반영하는 three loss functions와 deep neural networks를 통한 nonlinear transformation을 수행하기 때문에 좋은 성능을 보이는 것이다.
  • Comparison of Kernel Density Estimation
    • 제안한 방법은 Gaussian kernel을 KDE kernel function으로 사용하는데 다른 kernel(linear, tophat, exponential, Epanechnikov) 역시 사용할 수 있으므로 비교가 필요하다.
    • Performance 측면과 computational time 측면에서 비교함.


    • performance를 보면 gaussian이 다른 kernel들에 비해 평균적으로 살짝 높지만 computational time은 다른 kenel들에 비해 압도적으로 작음. -> gaussian을 선택하게 된 이유
  • Ensemble Learning and Cost-Sensitive Models
    • Ensemble learning과 cost-sesnsitive learning은 algorithm-level methods에서 imbalance 문제를 해결하는데 유명한 technique임.
    • 제안한 방법은 data-level approach이기 때문에 이 둘을 결합하는 것은 어렵지 않음.
    • 그렇게 DDHS와 AdaBoost를 엮어 만든 algorithm이 DDHS-Boosting임.(각 훈련 iteration 마다 DDHS를 수행하는 방식)
    • DDHS-boosting와 다른 ensemble learning을 하는 sota methods(Isolation Forest, RUSBoost, SMOTEBoost, SMOTEBagging, SPE)와 비교해 봄. + cost-sensitive learning methods인 cost-sensitive decistion tree와도 비교해 봄.
    •  
    • 위 table 9를 보면 SPE가 top conference에서 출판된 최신 연구라 좋은 성능을 보일 때가 있지만 전반적으로 DDHS-Boosting이 좋은 성능을 보임.
  • Training Time and Predicntion Time
    • 제안한 방법을 large-scale datasets에 적용해 봄.
    • 20번의 실험을 반복하고 training time과 prediction time을 기록함.
    • Isolet, mnist, spambase, optdigits, crime datasets에 대해
      • training time는 288, 174, 179, 131, 48s가 걸렸고
      • prediction time은 0.016, 0.014, 0.0133, 0.009, 0.011s가 걸림
    • 제안한 방법이 large-scale datasets에서도 적용될 수 있음을 알 수 있음.

6. Conclusion

  • 본 article은 class imbalance problem을 다루기 위한 DDHS라는 method를 제안함.
  • 제안한 방법은 data-level method로 deep learning과 결합하여 발전시켰음.
  • 제안한 방법의 핵심은 embedding network로 저차원에서 데이터를 잘 분리시키는 latent sapce를 학습함.
  • Embedding network가 학습되고 project 한 다음 density-based data filtering과 feature-level method를 통해 유효하고 다양한 synthetic samples를 생성함.
  • Embedding network를 디자인할 때 latent space에서 data points가 class proximity 성질을 유지하기 위해서 cross-entropy와 center losses를 각각 between-class, within-class loss로 사용함.
  • 추가로 reconstruction loss를 통해 좋은 feature 표현을 학습하기 위한 제약을 둠.
  • 실험 결과 DDHS는 유망한 결과들을 보여줌.
  • 뿐만 아니라 DDHS를 boosting framework와 결합하여 다른 ensemble learning approaches를 능가함.

느낀 점

 논문의 conclusion에서 저자들이 써놓았듯이 imbalance problem을 deep learning을 통해 접근한 방식은 매우 참신했다. 구현 알고리즘을 보면 minority class에서 생성하는 과정, majority class에서 제거하는 과정 모두 세밀하게 연구하고 반영해 두어서 성능이 잘 나올 수밖에 없다고 생각한다.(매우 좋은 접근과 idea라고 생각함.)
 최근에 embedding network와 비슷한 auto-encoder에 대한 논문과 구현 과정을 보면서 생각보다 이 방식도 구현이 어렵지 않아 보였다. 당장 Kaggle 7월 playground에 적용할 수 있을지 모르겠지만(시간이...) 시간적 여유만 있다면 적용해보고 싶다.
 

+ Recent posts

티스토리툴바