[기계학습/ML] Ensemble Method

Bias-variance dilemma

어떤 하나의 문제를 풀이할 때 여러 가지 모델을 사용할 수 있다.

여러 가지 모델을 사용할 때 기본적으로 트레이닝 데이터를 핸덤하게 추출하여, 각 모델을 학습시킬 수 있다. 즉, 1,000개의 데이터에서 랜덤하게 300개의 데이터를 추출하여 하나의 모델을 만들고, 또 랜덤하게 300개의 데이터를 추출하여 두 번째 모델을 만드는 랜덤한 샘플링을 해주면 작은 데이터를 보지만 더 많은 모델을 만들어 줄 수 있다.

 

어떤 데이터가 선택되느냐에 따라 다른 모델이 학습이 되는데, 이러한 관점으로 deterministic한(결정적인) 알고리즘이 아니라, Stochastic한(확률적인) 알고리즘의 형태를 띨 수 있다.

 

- Bias

실제값과 예상값의 차이로 아래의 식으로 나타낼 수 있다.

θ은 실제값이고, θ^이 예측값의 필드라고 할 때, 어떤 모델이 예측값 평균이 기댓값이라고 할 수 있다.

 

- Variance

예측하는 값이 얼마나 넓고 다양하게 분포할 수 있는에 대한 값이다.

 

어떤 모델에 대해 bias와 variance 두 가지를 예측 성능의 척도로 볼 수 있는데,

두 값은 서로 한 쪽이 줄면 반대쪽이 커지는 trade-off관계이다.

 

 

위 식에서 볼 수 있듯이 MSE는 variance와 bias제곱의 합으로 표현된다.

 

이때 바이어스가 크다는 것은 실제값과 예측값 차이가 크다는 의미로 학습이 제대로 되지 않는다는 의미이다. 따라서 바이어스가 크면 트레이닝 데이터를 잘 표현하지 못하고 있는 underfitting 상태에 존재한다.

 

바이어스가 큰 상황에서 모델의 capacity를 늘림으로써 바이어스를 줄일 수 있지만 베리언스가 증가할 수 있어 overfitting 상태로 빠질 수 있다.

 

따라서 바이어스와 배리언스의 값의 합이 최소일 때 테스트 데이터에 대해 잘 설명해 줄 수 있다.

 

우리는 바이어스와 베리언스의 합이 gerneralization error라고 할 수 있다.

즉, 두 값의 합을 최소로 만들어주는 최적의 포인트는 존재하지만 둘 모두를 최소화할 수 있는 방법은 존재하지 않는다.

 

Ensemble method

바이어스와 배리언스의 trade-off 관계로 인해 하나의 모델로는 어떤 문제를 충분히 풀 수 없다. 하나의 모델로만 문제를 풀기보다는 여러 개의 모델을 사용하여 결합함으로써 성능을 높이는 것이 Ensemble Method의 기본 원리가 된다.

 

각 모델에서 기본이 되는 모델을 base learner라고 한다.

이러한 베이스 러너를 여러 개를 만들어주고 베이스 러너의 결합을 통해 결과를 만든다.

이때 중요한 점은 베이스 러너는 서로 다르거나 다른 뷰(관점)를 가져야 한다.

 

우리는 앙상블 메서드의 타입을 크게 두 가지로 나눌 수 있다.

 

Bagging

Bootstrap aggregating의 약자로 low bias, high variance인  base leaner를 사용한다.

즉 각각 base leaner가 오버피팅된 상태인데, 오버피팅 자체가 해당 데이터를

잘 표현하고 있다는 의미기 때문에 이와 같은 base leaner의 결합으로 전체적인 성능을 높인다.

이 결합을 통해 smoothing효과를 낼 수도 있다.

 

한 가지 예시로, kNN 알고리즘을 사용할 때, k의 값을 작게하는 모델을 여러 개 만들어

이들을 결합해주면 더 나은 성능을 보일 수 있다.

 

Boosting

high bias, low variance인  base leaner를 사용한다.

즉 언더피팅인 모델을 여러 개 사용하는 방법이다.

각자 트레이닝 데이터에 대한 표현력이 부족해도, 이들의 결합을 통해 언더피팅을 넘어서는 결과를 나타내 줄 수 있다.

 

Bagging (Bootstrap aggregating)

Low bias, high variance → variance reducing/cutting

 

variance가 높기 때문에 variance를 낮춰주는 방식으로 학습한다.

트레이닝 데이터를 랜덤하게 샘플링한 후 low bias를 가지는 base learner를 학습시킨다.

이후 이들을 결합하는데, regression인 경우 평균값, classification인 경우 major voting(다수결 투표) 방법을 통해 variance를 낮춰줄 수 있다.

 

위의 예시에서 30개의 모델 중 24개가 1이라는 결과값을 내고, 6개가 -1이라는 결과값을 냈는데, 다수결 투표에 의해 1이 채택되고 -1을 출력한 base learner는 overfitting 됐다고 판단할 수 있다.

 

Random forest

Random forest는 DT의 bagging version이라고 할 수 있다.

이 방법은 DT를 여러 개를 생성하는데, 생성할 때 데이터가 아닌 feature를 랜덤하게 추출한다.

feature를 랜덤하게 추출한 subset에 대하여 각각의 DT를 생성한다.

 

이때 base learner는 50개 이상, 즉 DT를 50개 이상 둔다.

base learner는 bootstrap라고도 하는데, 각각의 bootstrap는 서로 다른 view point를 둔다.

 

위 사진은 classification을 random forest로 진행할 때의 알고리즘을 나타낸다.

1. 생성할 트리의 개수만큼 아래 명령어를 실행한다.

2. 각 트리에 대해 N 크기의 트레이닝 데이터를 부트스트랩 방법으로 생성한다.

3. k개의 attributes를 무작위로 선택하고, best attribute로 dataset을 분할한다.

4. 재귀적으로 트리를 생성하는데, overfitting을 위하여 pruning을 하지 않는다.

5. End

6. test dataset에 존재하는 sample에 대한 확률을 계산한다: p(c|x) = (1/nTree)∑hj(c|x)

7. 다수결 투표로 결과 class를 예측하고 OOB error을 계산한다.

 

OOB error는 

데이터를 무작위로 선택할 때, othgonal하게 뽑지 않고 뽑을 때마다 랜덤으로 진행되기 때문에 선택되지 않는 데이터가 존재할 수 있다. 이러한 데이터를 out of bags(OOB)라고 하는데 이들을 통해 validation을 진행해주고, 이들에 대한 오류를 OOB error라고 한다.

 

Boosting

High bias, low variance → bias cutting

 

bias가 크고 variance가 작은 모델로 전체 모델을 구성하며, 각각 base learner에 대한 capacity는 떨어진다. 따라서 이러한 모델의 bias를 줄여주는 쪽으로 모델을 결합하게 된다.

 

overfitting된 모델을 smoothing하는 효과를 기대하기 보다 각각의 bias가 높기 때문에 sequential한 learning 방법을 통해 점점 모델의 성능을 향상시켜준다.

 

Ada boost

우리는 boosting 시에 Ada boost 방법을 가장 많이 사용한다.

Ada boost는 sequential learning 시 각각의 모델이 bias가 높으므로 training error이 높은 데이터들이 뒤에서 학습할 때 더 많이 sampling되도록 sampling 확률을 높여준다.

 

앞에서 제대로 설명되지 않은 데이터에 대해 뒤에서 더 잘 학습하도록 하고, 최종적으로 이러한 모델들의 결합으로 어떤 결정을 내리는 것이 sequential learning이라고 한다.

 

 

위 사진은 AdaBoost의 알고리즘을 나타낸 사진이다.

1. 얼마나 잘 샘플링 될 건지에 대한 observation weight를 동일하게 둔다.

 

2. M은 모델의 개수로 순차적으로 모델을 학습해준다.

앞에서 주어진 weight를 이용하여 sampling 한 후 학습을 한다.

classifier의 에러를 계산한다.

αm은 에러 값을 보고 나중에 모델을 결합할 때 얼마의 비중을 둘 것인지 결정해준다.

즉, 에러가 낮으면 비중을 낮춰주고, 에러가 높으면 비중을 높여주는 결합의 계수가 된다.

αm 값을 통해 샘플링 된 데이터들에 대한 weight를 다시 계산해준다.

이러한 과정을 반복하며 weight를 업데이트 해주고, α 계산하는 과정을 M번 반복하면 최종 classifier의 값은 이들의 결합으로 계산이 된다.

 

3. 이후 각각의 classifier의 결과에 반영 비율 αm을 곱하여 다 더해준 다음 1과 -1로 분류할 때 0보다 크면 1, 0보다 작으면 -1이라고 판단해 줄 수 있다.

 

 

 

위 사진은 AdaBoost의 예로 파란색 박스를 친 부분에 대해 더 집중해서 학습할 수 있도록, 다음 모델로 갈수록 비중을 높여주고 있다.

 

Gradient Descent(경사하강법)

최적화 방법 중 하나로 loss를 줄여주기 위한 포인트가 w 파라미터이다.

어떤 loss 함수에 대해서 이를 최소로 만들어주기 위한 w를 찾는 과정으로

loss 함수에 대해 기울기가 줄어드는 쪽으로 w를 업데이트해준다.

따라서 이러한 과정을 반복하면 최적의 값을 향하게 된다.

 

처음 initial 값을 잡은 후 해당 값이 줄어드는 방향으로 w_(k+1)을 옮겨준다.

이때, η는 learning rate로 기울기가 이동할 때 얼마나 더 이동할 것인지를 판단해준다.

η는 기울기 값에 절대적이지 않으며, 기울기가 0에서 멀면 많이, 가까우면 조금씩 이동해가며 w를 조정한다.

 

따라서 방향은 gradient의 역방향으로, 이동 거리는 gradient의 절대 크기에 임의로 정한 learning rate를 좁해서 weight의 업데이트 값이 결정된다.

 

출처: https://100s.tistory.com/31

 

이때, 기울기 그래프가 non-convex한 형태일 때에는 local minimum에 빠질 수 있다.

local minimum은 주변값보다 작아 경사하강법으로는 밖으로 나갈 수 없는, 기울기가 0인 곳을 이야기한다.

 

하지만, 경사하강법으로는 global minimum에 도달할 수 있는 방법이 없을 뿐더러 다른 알고리즘도 global minimum을 찾을 수 없기 때문에 local minimum이라도 찾기 위해서 경사하강법을 사용한다.

 

Gradient boost for regression

Gradient boost는 Gradient descent 방법을 통해 loss를 줄여주는 방식이다.

 

y는 실제값이고, ŷ은 예측값이다.

초기의 예측값은 평균값인 50으로 둔다.

 

따라서 leaf node가 1개인 DT를 만들 수 있다.

 

예측값으로 pseudo residuals을 구한다. 이 res.값은 (실제값)-(예측값)한 값이다.

 

 

따라서 각 값을 위와 같은 트리 형태로 만들어 다음 학습 시에 반영할 비중을 구해준다.

이때, 비슷한 값끼리 묶고 res.값을 각 res.의 평균으로 구한다.

 

 

Tree 0 + a*Tree 1을 통해 다음 값을 계산한다.

이때, learning rate는 0.1이다.

 

 

마찬가지로 결과값을 통해 트리 형태로 만들어 다음 학습 시에 반영할 비중을 구해준다.

 

 

Tree 0 + a*Tree 1 + a*Tree 2을 통해 다음 값을 계산한다.

이때 두 base learner의 learning rate는 동일하다.

 

이러한 과정을 정지 기준에 도달할 때까지 반복한다.

 

1. 가장 먼저 loss 함수를 줄여준다. 이때, γ은 loss를 줄여주는 쪽으로 값을 조정해주는데, loss function은 regression이므로 MSE로 지정한다.

 

2.

(a) 이후 loss gradient를 계산한다. 이때, gradient는 res. 값의 음수가 된다.

(b) 계산된 res. 값을 이용하여 gradient값을 타겟으로 한 regression 트리를 생성한다.

(c) 생성된 DT를 통해 새로운 예측값을 만들어준다.

(d) 이전 값과 새로운 DT의 값에 res.를 더한 값을 더하여 업데이트한다.

 

Gradient boost for classification

마찬가지로 Gradient boost를 통해 classification을 진행할 수 있다.

하지만 차이점으로는 regression에서는 res.가 -gradient가 되도록 하는 loss function을 줬는데, classification에서도 마찬가지로 실제 확률과 예측 확률의 차이를 res.로 두고 얘를 gradient가 되도록하는 loss 함수를 사용해야 한다.

 

이때 우리는 log(odd)를 사용하여 계산한다.

 

 

마찬가지로 y가 실제값, ŷ이 예측값이다.

초기 값은 실제 값의 평균으로 모두 예측을 진행한다.

 

따라서 그림과 같은 트리를 만들 수 있다.

이때 트리는 log(odd)값이고, 예측값은 실제 확률 값이기 때문에 변환이 복잡하다.

트리의 값은 0이 4개, 1이 6개이므로 log(6/4)으로 구하고 그 값은 0.41이다.

 

실제값에서 예측값을 뺀 res. 값을 구한다.

 

res. 값을 통해 새로운 DT를 만든다.

이때 중요한 점은 앞서 언급했듯이 트리의 리프노드 값은 res.의 log(odd)값이다.

이후 learning rate를 통해 결합할 때에도 log(odd)값을 사용하지만,

확률로 변환할 때에 예측값으로 바뀐다. 즉, 예측값을 구할 때 확률을 구한다.

 

 

이전의 확률과의 차이를 통해 residual에 관한 식으로 DT의 결과값을 둔다.

 

앞서 등장한 트리로 learning rate를 곱해 Tree 0 + a*Tree 1의 값을 구한다.

 

새롭게 등장한 예측값을 통해 res.값을 다시 구한다.

 

regression과 마찬가지로 위의 과정을 반복하며 res.를 구하고, res.에 대한 log(odd)의 확률을 구하고, 그 값은 learning rate를 곱해 계속해서 더해주면 된다.

 

자세하게 구하는 방법은 위와 같다.

베르누이 분포를 이용하여 loss function을 정의하고 음의 gradient를 통해 DT를 업데이트한 후 새로운 예측값을 구한다.

 

loss function을 구하는 식은 위와 같다.