앙상블 학습과 랜덤 포레스트(Ensemble Learning & Random Forest)
1. 투표기반 분류기
다수의 의견이 소수의 의견보다 더 옳은 경향이 있다는 것은 지금 우리 사회를 유지하는 방향이다.
왜 그런 방향으로 사회가 구성될까? 그것이 정말 옳은 방향이 맞을까?
큰 수의 법칙(Law of large number)
어떤 독립시행에서 사건 K가 일어날 횟수를 k라고 하고 시행 횟수를 n이라고 하면, 통계적 확률에 따른 확률
는 n이 한없이 커질 때
예를 들어보자.
조금 이상한 동전이 있다. 앞면이 51% 확률로 나오고, 뒷면이 49% 확률로 나오는 동전.
상식적으로 알 수 있듯이 던지는 횟수가 적을 때는 뒷면이 더 많이 나올 수 있지만 시행횟수를 늘리게 되면 수학적 확률에 근접한다는 것을 알 수 있다.
실제로 10번의 실험을 했을 때, 다음과 같은 결과를 얻을 수 있다.
결국, 많은 시행 (다수의 사람)의 결과가 수학적 (이성적) 결과를 가져온다.
그렇기 때문에 무언가를 운영함에 있어서 합리적인 방법으로 가는 방법은 다수의 의견을 따르는 것이
어느정도 옳다는 결론을 내릴 수 있다.
(물론 실제에서는 독립적인 판단을 내려서 투표하기가 힘들겠죠? 지인이라던가.. )
그렇다면 이 간단한 아이디어를 분류기에 사용해보자!
직접투표 & 간접투표
분류
한 데이터에 대해 훈련한 모델을 각 사람에 치환한다면 이 방법을 사용할 수 있다.
각 모델은 다음 모델에 영향을 끼치지 않으므로 독립 시행이라 볼 수 있으므로 큰 수의 법칙이 적용된다.
다음과 같이 여러개의 분류 모델을 우리는 만들 수 있다. (SVM, K-means, Logistic...)
각 모델의 정확도가 80%일 때, 특정 데이터에 대해 각 모델이 예측하는 결과가 있을 것이다.
이걸 종합하여 결과를 산출한다.
다음과 같이 1로 예측한 결과가 가장 많기 때문에 각 모델의 결과를 종합한 1을 예측결과로 반환한다.
이 방법은 우리가 투표할 때 방식과 동일한 직접투표 방식이다.
한편, 각 모델이 분류할 때 이를 예측 클래스값으로 결과를 내보내지 않고 클래스에 속할 확률로 값을 나타낼 수 있다면,
이때는 해당 클래스에 속할 확률을 각 분류기에 대해 평균을 취하고, 이것이 가장 높은 클래스로 예측 클래스를 결정할 수 있다.
이렇게 예측할 경우 높은 확률의 결과값을 내놓은 모델의 비중을 고려할 수 있기 때문에 예측률이 더 높다.
이 방법을 간접투표 방식이라 한다.
회귀
회귀에 있어서는 다수결이 불가하기 때문에 예측값을 평균값으로 채택한다.
이 방법들을 플로우차트로 정리하면 다음처럼 정리할 수 있다.
graph TD
A(투표기반 방법) --> B[회귀]
A --> C[분류]
B --> D[평균값으로 채택]
C --> |직접투표|F[다수결로 채택]
C --> |간접투표|G[확률의 평균으로 채택]
위와 같은 투표기반 방법은,
- 같은 훈련 데이터 사용
- 다른 알고리즘 사용
- 예측값 추합
의 과정으로 요약할 수 있다.
2. Bagging & Pasting
하지만 독립시행을 만드는데 있어 우리는 다른 방법을 생각할 수 있다.
- 다른 훈련 데이터 사용
- 같은 알고리즘을 사용
- 예측값 추합
여전히 다음 모델에 영향을 주지 않는 독립시행이므로 이런 방법을 생각해 볼 수 있다.
이때, 어떻게 다른 훈련 데이터를 사용 할 수 있을까?
이 데이터 사용방법에 따라 Bagging과 Pasting이 나뉜다.
Bagging
복원 추출이다.
Pasting
비복원 추출이다.
OOB 평가
Bagging에 한정해서 복원추출을 진행할 때, 데이터의 37% 정도는 뽑히지 않는다.
우리는 그 뽑히지 않은 데이터를 Test셋으로 사용할 수 있다.
m개의 샘플에서 무작위로 하나를 추출할 때 선택되지 않을 확률은,
이를 m번 반복했을 때 선택되지 않을 확률은,
이 때, y에 로그를 씌우고 로피탈의 정리를 사용하면,
y에 대해 정리하면,
따라서 뽑히지 않을 확률은 0.37% 정도가 된다.
이 확률은 m이 커질 수록 증가한다.
3. Random Patch, Random Subspace
지금까지는 data의 row를 기반으로 trains set을 정했다.
그런데 Feature에 대해서도 샘플링을 할 수 있지 않을까?
Random Patch
- Feature 샘플링
- row 샘플링
Random Subspace
- Feature 샘플링
- row는 모두 사용
4. Random Forest
Bagging & Random Patch & Decision Tree 방식을 사용한 전체 알고리즘을 Random Forest라 부른다.
Random Forest Algorithm
모든 피쳐에 대해 Greedy한 방법을 쓰는 Desision Tree는 Varience가 낮아 일반성에서 손해를 본다는 단점을 가지고 있다.
Random Forest에서는 Feature도 복원추출함으로써, 무작위성을 증가시킨다.
따라서 다양한 트리를 종합하는 결과를 가져올 수 있고, 결과적으로 Decision Tree에 비해
Varience를 낮추어 나은 모델을 만들 수 있다.
Extra Tree (Extremely Randomized Tree)
알고리즘으로 사용하는 Decision Tree의 Greedy 방식에서 무작위성을 추가한다.
최적의 노드값을 기준으로 트리를 만들지 말고, 복원추출한 Feature에서 무작위로 분할한다.
효과
- 시간복잡도를 줄일 수 있다.
- Varience를 줄일 수 있다.
Feature Importance
기본적으로 Decision Tree는 특성 중요도를 제공한다.
하지만 Greedy Algorithm 때문에 몇몇 특성을 중요도를 배제한다는 단점이 있다.
무작위성이 가미된 Random Forest는 거의 모든 특성에 대해 중요도를 평가할 수 있다.
다음과 같은 트리가 있을 때, A의 특성 중요도 계산 방법은,
graph TD
A --> B
A --> C
B --> D
B --> E
로 구할 수 있다.
MNIST 데이터 셋(손글씨 픽셀 데이터) 에 대해 특성중요도를 판단해보면,
다음과 같은 그림이 나온다.
이 그래프를 보고 우리는, 이 이미지를 판단함에 있어 밝게 표시된 Feature(픽셀)이 영향력이 가장 크다는 정보를 얻을 수 있다.
Random Forest 까지 간단하게 Flow chart로 정리해 보면,
graph TD
D[Training Set 선택방법] --> |추출방법|E[방법이름]
E --> |알고리즘 방법|G[명칭]
A[Data Sampling] --> |복원추출|B[Bagging]
A --> |비복원추출|C[Pasting]
B --> |Decision tree|F[Random Forest]
5. Boosting
Boosting은 지금까지 본 앙상블 방법과 조금 상이할 수 있다.
독립적인 모델을 합산하여 산출하기보다는 기존의 모델을 어떻게 보면 개선시키는 방향이기 때문이다.
즉, 약한 모델(Weak Learner)을 결합하여 강한 모델 (Strong Learner)을 만드는 방법이다.
남아있는 오류에 대해 어떤 알고리즘으로 보완하느냐에 따라 방법이 변화한다.
가장 인기있는 모델은, Adaboost, Gradient Boosting이 있다.
Adaboost
핵심적인 아이디어는 종속시행 이다. (훈련 알고리즘은 정해지지 않았다.)
처음 Traing Data를 통해 만든 모델에서 오분류한 데이터가 뽑힐 확률을 높히는 것이다.
장점
- 오분류 데이터에 대해 모델을 적합할 수 있다.
단점
- 잘못하면 Varience를 높힐 수 있다.
- 계산과정에 있어 병렬 수행이 불가하다.
Gradient Boosting
이번에는 맞추지 못한 데이터를 더 많이 적합시키는 방법보다는,
오차에 대해 적합을 수행하는 방법이다.
그 오차는 손실함수로 표현되고, 이 손실함수를 최적화하는데 있어 Gradient Descent를 사용한다.
즉, Boosting : 드러난 약점을 보완한다.
Gradient : 손실함수를 최소화할 때, Gradient Descent를 사용한다.
이 두가지 의미를 포함하는 방법이라 할 수 있다.
Gradient Descent은, 이 $\theta$ 를 구하는 것이 목표였다. ($J$는 손실함수)
손실함수를 파라미터로 미분해서 기울기를 구하고,
값이 작아지는 방향으로 파라미터를 움직이면서 손실함수가 최소화되는 지점에 도달하는 것이다.
Gradient Boosting은
손실함수를 파라미터가 아니라 현재까지 학습된 모델 함수로 미분한다.
그런데, 기존에 했던 방식인, 손실함수를 MSE(Sqauared Error ${1\over2}(y-f_i)^2$) 로 잡고서 $\frac{\partial{J}}{\partial{f_{i}}}$ 을 구해보면,
가 되어 ${f_i+1} = y $ 가 된다. 이건 의미가 없다.
따라서 Gradient Boosting은 손실함수를 잔차 (Residual Error) 로 잡아 다음 모델을 업데이트한다.
Gradient Descent와 마찬가지로 학습률을 조정해서 업데이트율을 변경할 수 있다.
알고리즘을 Decision Tree를 사용했을 때, 그래프를 보며 직관적 이해를 해보자.
왼쪽은 시행에 따른 잔차 그래프이다.
오른쪽은 이를 더함으로써 모델적합을 한 그래프이다.
당연하게도 너무 많은 시행(트리에서는 트리의 개수)은 Underfitting, Overfitting을 불러올 수 있다.
왼쪽은 너무 적은 시행, 오른쪽은 너무 많은 시행을 한 결과이다.
최적의 트리수를 찾기 위해서 Early stop 방법을 사용해야 한다.
검증 오차 그래프를 사용해 최적의 트리수를 찾는다.
Gradient Descent에서 샘플의 집합에 따른 분류를 할 수 있었다.
- Batch 배치
- MiniBatch 미니배치
- Stochastic 확률적
3으로 내려올 수록 샘플 집합의 크기는 감소했다.
마찬가지로 Gradient Descent 방법을 사용하므로 이 분류를 사용할 수 있다.
Gradient Boosting 은 샘플의 비율을 결정하는 매개변수를 지원한다.
이를 Stochastic Gradient Boosting, 확률적 그래디언트 부스팅 이라 한다.
graph TD
D[Training Set 선택방법] --> |Boosting Method|E[방법이름]
E --> |알고리즘 방법|G[명칭]
전체[Cross Validation] --> |오분류 샘플 가중치|부스팅[AdaBoosting]
전체 --> |Gradient Descent for Model|그래디언트[Gradient Boosting]
부스팅 --> |내가 선택|없음
그래디언트 --> |내가 선택|없음
6. Stacking
우리는 처음에 앙상블 방법의 핵심 매커니즘인 투표기반 분류기에 대해 공부했다.
이때 회귀에 대해서는 평균값으로 이를 대치한다고 했다.
또는 분류에 대해서는 직접투표(다수결), 간접투표(확률에 대한 평균)을 사용한다고 했다.
- 직접투표
- 간접투표
그런데 이 각 모델이 내놓은 값들을 이런 간단한 함수로 산출하는 대신,
이 값을 기반으로한 모델을 훈련시킬수는 없을까?
Blender (Meta Learner)
여러가지 모델을 사용한 결과를 모으는 곳을 Layer라고 한다.
지금 같은 경우 Predictions에 해당하는 숫자들이 1 Layer가 될 것이다.
Blending에서 이 데이터를 가지고 특정 알고리즘을 돌려 최종 값인 3을 출력할 것이다.
그런데 이 때 Blending에 사용하는 모델은 사실 여러가지를 사용할 수 있다.
다음과 같이 Blending을 담당하는 Layer 2에 세가지 모델을 달아버릴 수도 있다.
그렇게 된다면 Layer 1에서 나온 예측값을 Layer 2에 해당하는 각각의 모델의 input으로 넣을 수 있고,
Layer 2를 통과한 값들을 다시 Blending해서 최종값을 얻을 수도 있을 것이다.