Ensemble Learning : Overview

-
04_1 : Ensemble Learning : Overview

이번 글에서는 간략하게 Ensemble 기법이 어떤 것인지, 왜 사용하는지 알아보도록 하자.

Backgrounds

위의 예시는 여러 종류의 데이터 셋에 대하여 각 Classification 알고리즘들이 얼만큼의 성능을 보이는지 Error율을 기반으로 표현한 그래프이다. 그래프를 보면, 모든 데이터 셋에 대하여 우월한 성능을 보이는 알고리즘은 없는 것을 확인할 수 있다. 각 데이터 셋의 특성에 따라 더 좋은 알고리즘이 그때 그때 다르다.

그렇다면 다른 모든 알고리즘들 보다 우월한, 모든 데이터 종류에 대하여 항상 좋은 성능을 보이는 알고리즘은 존재하지 않는걸까?

No Free Lunch Theorem

"공짜 점심은 없다"는 이 이론에 따르면, 그런 알고리즘은 존재하지 않는다. 정확히는 어떤 알고리즘도 모든 상황에서 다른 알고리즘보다 우월하다는 결론을 내릴 수 없다. 이 이론을 설명하는 논문에 제시된 결론은 다음과 같다.
  • 좋은 일반화 성능을 원한다면, Context-independent 하거나 Usage-independent 한 이유로 한 알고리즘을 선호할 수 없다. (다시 말해, 항상 Context와 사용할 용도를 고려하여 알고리즘을 선택해야 한다는 뜻이다)
  • 만약 한 알고리즘이 다른 알고리즘들에 비해 좋은 성능을 보인다면, 그것은 그 알고리즘이 해당 데이터 셋의 특성과, 용도에 적합하기 때문이다.
때문에 우리는 엄청난 알고리즘 하나만을 여기저기 사용하여 공짜 점심을 먹으려 날로먹으려 하지 말고, 사용할 용도와 Data의 특성, Context, 경험적인 지식, 통계적인 정보 등 여러 지표를 종합적으로 고려하여 적절한 알고리즘을 선택해야 한다.

그런데 No Free Lunch 이론을 제시한 논문에서, 추가적으로 아래와 같은 실험 결과를 제시하였다.

"However, if they are properly combined ... 
Every ensemble method competes well against the best of the individual algorithm"

놀랍게도 적절하게 Ensemble기법들을 적용했더니, 하나의 알고리즘 만을 사용한 것들 중 가장 좋은 성능 이상의 성능을 보인 것이다.


Empirical Evidence (경험적 증거)

2014년 (그당시 주로 쓰이던) 많은 알고리즘들의 성능을 실험해본 논문이 있다.
"Do we Need Hundreds of Classifiers to Solve Real World Classification Problems?"(링크)

이 논문에서는 실험적으로 179개의 알고리즘들을 121개의 datasets 모두에 대한 성능을 측정하였다. 그리고 성능지표를 기반으로 각 데이터 셋 마다 알고리즘들의 순위를 매겼다. 실험 결과로 논문이 제시하는 것은 다음과 같다.
  • No Free Lunch theorem이 맞다. (모든 경우에 Rank가 1인 알고리즘이 없었다)
  • Random Forest (앙상블 기법 중 하나)와 SVM 계열 알고리즘들이 상대적으로 분류 성능이 좋았다. (통계적으로 유의미할 정도로)
하지만 이 논문에서 반영하지 못한 알고리즘들이 있다. 이후에 공부하겠지만 앙상블 기법 중 Boosting계열의 알고리즘들은 실험되지 않았다.

이후 실험과 대회, 논문에 발표되는 성능을 바탕으로 앙상블 기법을 사용하는 알고리즘들이 훨신 좋은 성능을 보인다는 것이 보여졌다. 때문에 점점 많은 분야에서 단일 알고리즘을 사용하기 보다, 앙상블 기법을 적용하는 것이 추세이다.

방대한 이미지 분류 성능을 겨루는 대회, ImageNet Challenge (LSVRC)에서도 이러한 변화가 보여진다.
2015년 까지만 해도 더 깊은 DNN 구조를 사용하여 복잡한 모델을 통해 기하급수적인 성능의 향상이 이루어지고 있었다. 그러던 중 2016년 부터 앙상블 기법을 사용한 알고리즘들이 압도적인 성능으로 대회를 우승하기 시작했다. 



위에서 열심히 예시를 들어 말하고자 하는 것은 다음과 같다.
"Ensembles almost always work better than the single best model"

이렇게 강력한 앙상블 기법을 지금부터 공부해볼 것이다. 그 전에 다음 글에서 Bias-Variance Decomposition과 수학적으로 앙상블 기법이 왜 더 좋은지 증명해 보도록 하자.



※ 이 글은 고려대학교 산업경영공학과 강필성 교수님의 IME654 강의를 정리하고, 공부한 내용을 추가하여 작성되었습니다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

One-Class SVM & SVDD

-
이미지
03_6 : Anomaly Detection : Auto-Encoder, 1-SVM, SVDD MoG와 같은 밀도기반 방법론들은 특정 객체가 정상범주에 속할 확률을 구했다. 반면 Support vector 기반 방법론들은 normal과 abnormal을 구분하는 분류경계면을 찾는다. 이번 글에서는 Support vector 기반의 Anomaly detection 방법 중 one-class SVM과 SVDD를 알아보자. One-class Support Vector Machine (1-SVM, OCSVM) 1-SVM의 목표는 Data를 feature space로 mapping 한 뒤, 분류경계면을 통해 mapping된 Data 중 normal data들이 원점으로부터 최대한 멀어지게 만드는 것이다. 위 그림에서 파란색 분류경계면이 (+1) normal data들을 구분하는 것을 확인할 수 있다. 이 목표를 수식화 한 Optimization problem부터 살펴보자. Optimization Problem $$\min_{\textbf{w}}\;\;\;\frac{1}{2}||\textbf{w}||^2 + \frac{1}{\nu l} \sum_{i=1}^l \xi_i - \rho$$ $$s.t.\;\;\;\textbf{w}\cdot \Phi (x_i) \geq \rho - \xi_i\;\;\;\;(i=1,2,\cdots,l),\;\;\xi_i\geq 0$$ $\frac{1}{2}||\textbf{w}||^2$ term은 SVR과 같이 $x$의 변화에 따른 변동이 크지 않도록 Regularization을 하는 term이다. $\rho$는 위 그림에서 주황 직선을 나타내는데, 원점과 분류경계면 Hyperplane과의 거리를 나타낸다. 이 값을 뺌으로써 최소화 문제를 만족하는 최적해일때 $\rho$가 최대가 되도록 한다. (원점에서 Hyperplane이 최대한 멀어지게 만든다) $\frac{1}{\nu l} \sum_{i=1}^l \xi_i$ term은 제약식에 따라 Hyp...
자세한 내용 보기

Support Vector Regression (SVR)

-
이미지
02_4 : Kernel based learning : Support Vector Regression (SVR) 앞에서 공부했던 SVM은 binary classification을 하기 위한 방법이었다. 이번 글에서 알아볼 SVR은 함수를 추정하여 연속적인 수치변수를 예측하는 회귀 방법이다.  SVR을 알아보기에 앞서 우리가 하려는 함수추정의 목적을 살펴보자. Fitting function 함수를 추정하고 싶을 때 우리의 목적은 크게 2가지로 나뉜다. Minimize an error measure (Loss function) 한마디로 error를 최소화 하여야 한다. (잘 맞춰야 한다) Function to be simple 같은 성능이라면, 함수는 최대한 단순해야 한다. 함수가 단순하다는 뜻은 아래의 조건들을 의미한다. Fewest basis functions Simplest basis functions Flatness is desirable Support Vector Regression (SVR) 위에서 살펴보았던 Loss function과 Flatness를 반영하도록 목적함수를 만들 것이다. SVR에도 여러 종류가 있는데, 우선 $\varepsilon$-SVR에 대하여 알아보자. 현실의 Data들은 어쩔 수 없이 발생하는 noise가 존재한다. 아래 식에서 noise는 $\varepsilon$이다. $$y = f(x)+\varepsilon$$ $\varepsilon$-SVR에서 핵심 아이디어는 $\varepsilon$ 보다 작은 noise에 대해서는 Loss를 주지 말자는 것이다.  왼쪽 그림에서 색이 칠해진 영역을 Epsilon-tube 라고 하는데, 이 영역안에 있는 객체들에게는 Loss를 부여하지 않는다. 이를 위한 Loss function은 오른쪽에 표현된다. 이 Loss function은 hinge를 닮았다고 해서, Hinge Loss 라고 불린다. 차이가 $\varepsilon$ 보다 작은 경우 loss는 0이고, $\vareps...
자세한 내용 보기

Self-Training & Co-Training

-
이미지
 05_2 : Semi-Supervised Learning : Self-Training and Co-Training 우선 가장 기본적인 준지도학습 방법 Self-Training에 대하여 알아보자.  Self-Training 우리에게 주어진 정보는 Labeled data $(\mathbf{X}_l,y_l)$과 Unlabeled data $\mathbf{X}_u$이다. Self-training과정은 다음과 같이 진행된다.  1. 우선 주어진 Labeled data $(\mathbf{X}_l,y_l)$를 사용하여 예측함수 $f$를 학습시킨다. $$y_l = f(x_l)$$ 2. 학습이 완료되면, 예측함수 $f$를 사용해 Unlabeled data $\mathbf{X}_u$의 예측값 $\hat{y}_u$를 구한다. $$\hat{y}_u = f(x_u)$$ $$\Downarrow$$ 3. 이제 기존의 Labeled data와 예측함수에 의해 labeling이 된 Unlabeled data를 합치고, 이 data를 사용해 예측함수 $g$를 학습한다. 이때 어떻게 Unlabeled data를 합치는지에 따라서 많은 variation이 있다. 대표적으로 Add all $(x_u,\hat{y}_u)$ to labeled data Add a few most confident $(x_u,\hat{y}_u)$ to labeled data Add all $(x_u,\hat{y}_u)$ to labeled data, weight each by confidence. 모든 Unlabeled data를 합치는 방법, 몇몇개의 가장 예측 confidence가 높은 data만을 합치는 방법, 모든 data를 합치치만 예측 confidence에 따라서 weight를 지정하는 방법 등이 있다. 4. 위와 같은 과정을 Unlabeled data가 없어지거나, 수렴할 때 까지 반복한다. Propagating 1-Nearest Neighbor 다른 예시로 Propagating ...
자세한 내용 보기