yupsung Computer Science blog

 04_7 : Ensemble Learning : XGBoost : A Scalable Tree Boosting System 이 글은 XGBoost를 공부하면서 이해한 내용들을 정리한 글이다. 논문에는 생략되어있는 수식 전개를 나름 쉽게 설명해보려 하다보니 내용도 많고 수식도 많다. 정리하는데 너무 힘들었다ㅠㅜ  각 항목별로 논문의 몇번째 항목인지 부제목 옆에 적어놓았으니, 글을 읽을 때 논문을 함께 보도록 하자! ( 논문 )  XGBoost는 기존 Gradient Boosting 방법에 Approximation 방법을 적용하여 Parallelize를 가능하게 하고, 하드웨어적인 최적화를 하여 더 빠르게 학습을 진행하면서 동시에 좋은 성능을 보인다. XGBoost가 각광받은 이유 중 하나는 Scalability(확장성)이다. 여러 종류의 데이터들과 목적에 잘 적용되고, 빠르고, 좋은 성능을 보인다. 우선 앞서 다른 글에서 이야기 했었지만, 다시한번 기본적인 Ensemble : Tree Boosting 방법에 대하여 짚고 넘어가자. Regularized Learning Objective (Article 2.1) 주어진 Dataset이 $n$개의 example(instance)들과 $m$개의 feature(variable)로 이루어져 있다고 가정하자. 그렇다면 Ensemble model의 추정값은 아래와 같다. $$\hat{y}_i = \phi (x_i) = \sum_{k=1}^K f_k(x_i),\;\;\;\;\;\;f_k \in \mathcal{F}$$ $$where\;\;\mathcal{F} = \{f(x) = w_{q(x)}\}\;\;(q:\mathbb{R}^m \rightarrow T,\;w\in \mathbb{R}^T)$$ $\mathcal{F}$는 모든 가능한 함수들을 포함하는 Function space이고, 함수 $f_k$는 각각의 Classification and regression tree(CART)이다. CART에서는 각 data들을 $q(x)

  04_6 : Ensemble Learning : Gradient Boosting Machine (GBM) 이번 글에서는 Boosting 방법 중 하나인 Gradient Boosting Machine (GBM)을 알아보도록 하자. GBM에서 파생된 많은 Boosting 알고리즘들이 있다. 예를들어, XGBoost, LightGBM, CatBoost가 있는데, 이후 포스팅 할 글들을 통해 천천히 알아보도록 하자. Gradient Boosting 이란? Gradient Boosting = Gradient Descent + Boosting Ada Boost 방법의 경우, 이전 base(weak) learner가 잘 분류/반영하지 못했던 단점(point들)을 다음 data sampling과정에서 high-weight를 주는 방법으로 성능을 개선하였다. Gradient Boost 방법의 경우, 이름처럼 이전 base learner의 단점을 gradient로 나타내고, 이를 통해 Loss function이 최소가 되는 방향으로 base learner들의 학습을 진행해 나간다. Gradient Boosting 또한 Regression, Classification, Ranking 모든 경우에 적용 가능하지만, Loss function 미분을 정의하기 어려운 순서대로 Regression<Regression<Ranking 순으로 이해가 더 어렵다. 우선 가장 직관적으로 이해하기 쉬운 Regression을 예시로 생각해보자. Motivation (for Regression problem) Data point를 예측한 Linear regression model이 위와 같은 함수를 예측했다고 생각해보자. 그렇다면 모델이 실제 data point를 반영하지 못한 오차는 전차(residual)로 나타난다. $$the\;predicted\;value\;:\;\; \hat{y}_i = f_1(x)$$ $$residual\;:\;\;y-f_1(x)$$ 이때 GBM의 아이디어는 다

04_4 : Ensemble Learning : Random-Forests Random Forest는 이전 글에서 공부했던 Bagging 방법의 특수한 형태로써 Decision Tree를 Base Learner로 사용한다. Random 하게 변수를 선택하여 여러개의 Decision Tree들( Forest )을 학습시키는 방법을 사용한다. 우선 Decision Tree에 대하여 알아보자. Decision Tree $d$개의 변수를 가지는 Data가 주어졌다고 가정하자. 이때 하나의 data point $v$는 아래와 같이 정의된다. $$v = (x_1,x_2,\cdots ,x_d) \in \mathbb{R}^d $$ 각 $x_i$는 변수 하나하나를 나타내는 스칼라 값이다. 변수가 매우 많은 경우, 앞서 배운 차원축소와 같은 방법을 사용하거나 이후에 다룰 Random Forest처럼 임의로 변수를 추출하여 사용한다. 변수의 추출은 $\phi (v)$ 함수에 의해서 이루어진다. $$\phi\;:\;\mathbb{R}^d \rightarrow \mathbb{R}^{d^\prime},\;\;\;\;d > d^\prime$$ Training Training 단계에서는 초록색 end node에 대응하는 정답 Label($y$)을 사용하여 각 노드를 분할하는 Split function의 매개변수를 최적화 한다. 각 노드에 대응되는 Data set을 $S$라고 하자. 그렇다면, 해당 집합은 Split function에 의하여 $S^L,\;S^R$ 두개의 집합으로 분할된다.  $$S_i = S_i^L \cup S_i^R,\;\;S_i^L \cap S_i^R = \emptyset $$ 이렇게 Data를 분할하는 Split function은 데이터를 정보 획득량(information gain : $I$)이 최대화 되도록 분리한다. $$I = H(S) - \sum_{i\in\{L,R\}} \frac{|S^i|}{|S|} H(S^i),\;\;\;\;H(S) = -\sum_{c\

 04_3 : Ensemble Learning : Bagging 앙상블 방법의 핵심은 Diversity (다양성)을 확보하는 것이다. Bagging 방법은 Implicit diversity 관점에서 Data의 다양성을 확보하려는 방법이다. 우리에게 주어진 Dataset은 하나의 큰 data 집합이다. 이 Dataset을 여러 방법으로 조절하여 다양성을 늘려보자.  K-fold data split K-fold 방법은 가장 처음 시도된 방법론이다. 딥러닝에서 Cross validation과 거의 동일한 메커니즘으로 동작한다.  우선 전체 Dataset을 K개의 subset으로 분할한다.  그리고 각 model마다 사용할 train dataset으로 대응되는 subset 1개를 제외하고 K-1개의 subset을 사용한다. 예를들어 2번째 model $f_2$가 사용할 train dataset으로는 k-1번째 subset이 제외된 나머지 dataset이 사용된다. 모든 모델의 학습이 완료되면 aggregation function $\delta(\cdot )$을 사용하여 결과를 구한다. $$ \hat{y} = \delta \big( f_1(x), f_2(x), \cdots, f_k(x)\big) $$ 서로 다른 train dataset을 사용하였으니, $f_1 \neq f_2 \neq \cdots \neq f_k$ 이다. 하지만 개별 model들이 완전히 독립적이지 않다는 문제점이 있다. 왜냐하면, 항상 임의의 $f_i$와 $f_j$는 $k-2$개의 fold를 공유하기 때문이다. 또한 데이터를 subset으로 나누는데 한계가 있다. 그렇기 때문에 K-fold방법으로 생성가능한 train dataset의 개수에도 한계가 있다. K-fold data split은 위와 같은 단점 때문에 요즘에는 잘 쓰이지 않는 방법이다. Bootstrap Aggregating (Bagging) Data Sampling Bagging 방법은 $N$개의 Original data로 부터 복원추출

04_2 : Ensemble Learning : Bias-Variance Decomposition 이번 글에서는 Ensemble learning의 이론적 Background로 필요한 Bias-Variance Decomposition을 알아보고, 수학적으로 앙상블 기법을 사용하는 것이 왜 좋은지 증명해 보도록 하자. Bias-Variance Decomposition 데이터가 Additive error model로 부터 생성된다고 가정하자. $$y = F^*(x) + \epsilon,\;\;\;\epsilon \sim N(0,\sigma^2) $$ $F^*$는 target function이다. 우리가 모르기 때문에 학습을 통해 추측하려 한다. Error $\epsilon$은 independent and identically distributed (iid) 즉, 상호 독립적이고 동일한 정규분포 $N$을 따른다고 가정하자. 우리는 각각의 학습 Dataset을 통해 여러개의 Model을 추정할 것이다. 추정한 함수를 $\widehat{F}_N(x)$라고 하자. 추정을 반복했을 때 그 함수의 기대값을 $\overline{F}(x)$라고 한다. $$\overline{F}(x) = E\big[\widehat{F}_D(x)\big]$$ 이제 특정 data point $x_0$에 대하여 Mean Squared Error가 어떻게 계산되는지 살펴보고, 여기서 Bias-Variance Decomposition을 유도해보자. $$\begin{align*}Err(x_0) &= E\big[y-\widehat{F}(x) | x=x_0 \big]^2\\&=E\big[(F^*(x_0)+\epsilon)-\widehat{F}(x_0) \big]^2\;\;\;\;\;(y = F^*(x)+\epsilon)\\&=E\big[F^*(x_0)-\widehat{F}(x_0)+\epsilon\big]^2\end{align*}$$ 제곱항을 풀기 위해서 $F^*(x_0)-\widehat{