[분류 예측 스터디] Extremely Randomized Trees paper review
작성자 : 염윤석
[논문에서 주목해서 봐야할 issue들]
Randomization(랜덤성, 임의성)과 bias/variance tradeoff 관계에 주목하자!
# Bias vs Variance
Error(X) = noise(X) + Bias(X) + Variance(X)
*noise(X) : 데이터 본질적인 한계
| Bias | Variance |
| *너무 단순한 모델에 의한 에러 *데이터 정보를 모두 학습X , 잘못된 학습 *bias가 크면 underfitting된 상태 *학습데이터를 충분히 모델이 표현하지 못하기 때문에 발생 |
*너무 복잡한 모델에 의한 에러 *실제와 관련없는 random한 것까지 학습해서 발생 *variance가 크면 overfitting된 상태 *과적합에 의해 일반화가 되지 않는다. |
#Decision Tree 기반 모델들간의 차이에 주목하자
- Single CART Tree(ST / PST) : Ensemble 기반이 아닌 independent한 decision tree + all features
- Tree Bagging(TB) : single tree들을 bootstrap을 통한 Tree ensemble + all features
- (Local) Random Subspace(RS) : tree들을 만드는 split node(locally)에서 일부분의 feature들만 선택
- RandomForest(RF) : bootstrap을 통한 tree ensemble + 각 node에서 feature들을 optimal하게 선택
- ExtraTrees(ET) : bootstrap을 사용하지 않고, 각 node에서 feature들을 random하게 선택
*Bootstrap : random sampling with replacement (무작위 복원 추출)
*Bagging(Bootstrp Aggregating) : bootstrap + feature을 sample별로 다르게 선택후, ensemble
1. Extra tree Algorithm
Randomforest vs Extremely randomized trees
RF(Bagging) : Bootstrap(randomization) + node feature select optimally
ET(no Bagging) : whole origin data + node feautre select randomly(randomization)
[learning sample]- bootstrap의 여부
-Randomfoest는 sample을 랜덤하게 복원추출하여 학습된 week tree들을 ensemble한다. -->increased variance
-Extratrees는 sample을 비복원추출하여 tree들을 학습한다. -->decreased bias
*학습 데이터에 대해 랜덤성이 부여되지 않기에, 모델의 전체 데이터에 대한 표현이 좋아지므로, extratree는 bias를 낮춘다.
[Tree형성 partision node형성] - node feature selection의 방법차이
-Randomforest는 각 node에서 feature을 선택할 때, 각 feature로 얻을 수 있는 Information content를 모두 계산 후, 제일 높은 feature부터 선택한다. --> features optimally selection
-Extratrees는 각 node에서 feature을 무작위로 선택 후, 선택된 feature들 한에서 최선의 partition을 찾는다.
-->features randomly selection
*feature선택이 equally random하기 때문에 각 decision tree별로 차등이 없기에 variance을 낮춘다.
*feature에 대한 Information content를 계산하지 않기에 연산 속도가 빨라진다.
2. Empirical Evaluation
-실제 Data를 적용하여 classification, regression에 대해 default parameter setting으로 여러 tree 알고리즘을 비교
*여러 tree 알고리즘 : ST, TB, RS, RF, ET
*defalut parameter
M : ensemble에 사용될 tree의 개수 [ default : 100]
n(min) : 각 node에 사용된 최소 sample size [default : 2(classification) / 5(regression)]
K : 각 node별로 랜덤하게 선택될 feature의 개수 [default : √n(classification) / n(regression)]
Fig1을 보면 single tree에 비해 ensemble 기반 tree 모델들이 확실히 좋은 것을 볼 수 있다. 하지만, ensemble끼리의 성능은 큰 차이가 없으나, TB, RS, RF, ET 중에는 확실히 ET(Extra Trees)가 성능이 제일 좋다.
Table3는 모델별로 numbers of leaves, 즉 split에 의한 node의 개수로 모델의 complexity를 계산한 결과이다.
하지만 Tree ensemble model별 평균 tree depth를 고려해보았을 때는, depth 증가 대비, complexity의 증가 속도는 Extratree 모델이 제일 작다. 따라서 최종 연산 속도를 생각해보았을 때, 다음과 같다.
Table 4에서 볼 수 있듯이, Single Tree를 제외하고 ensemble 중에서는 Extratree의 연산 속도가 제일 빠르다는 것을 알 수 있다.
3. On the Effect of parameters
M : ensemble에 사용될 tree의 개수
n(min) : 각 node에 사용된 최소 sample size
K : 각 node별로 랜덤하게 선택될 feature의 개수
-parameter 값을 바꿔가면서 model의 성능을 비교해보았다.
사실 parameter의 randomization의 효과가 모델별로 다르며, 분류/예측 문제의 특성에 따라 다르기 때문에, 이를 optimization을 하는 것을 분석가의 역량이라고 한다.
일례로 Fig.2에서 볼 수 있듯이, K(number of selected features at a node)가 증가할 수록 모델의 성능(error)가 변하는 그래프에서 문제별로 그래프가 다르기 때문에, K의 Extratree자체에 효과를 일반화할 수가 없다. 결국, 분류/예측별로 최적의 parameter를 찾아야한다.
4. Bias/Variance Analysis
이 부분이 개인적으로 논문을 읽을 때, 해석하기가 제일 어려웠다.
Tree ensemble기반의 모델들을 bias 와 variance 관점에서 비교한 부분인데, 모델의 randomization과 관련지어 설명하는 부분에서, "randomization"의 의미를 제대로 명시하지 않아 어려웠다.
예시로, randomforest와 extratreee의 모델 속, 랜덤성은 서로 다른 부분에서 부여가 되는데,
이를 같은 것으로 해석을 하면 bias나 variance 해석이 반대로 되기 때문에,
"randomization"을 Extratree에서 각 node에서 feature selection과 cut-point selection에 부여되는 랜덤성으로 해석했다.
논문에서 bias/variance 측면에서 모델들을 비교한 결과는 다음과 같다.
- Single Tree에 비해 Ensemble 모델들(TB, RS, RF, ET)들의 bias가 높았고, variance가 감소했다.
- Ensemble 중에 ET가 가장 bias와 variance trade off 효과가 제일 좋았다.
- single tree 대비, variance 감소는 약 95%, bias는 약 21% 증가했다.
- RS 보다 RF의 bias가 높았다. (RS는 bootstrap에 의한 randomization이 없다.)
- ET에서 K =1 때보다 K= optimal 때가 더 variance가 높고, bias가 낮다.
Randomization에 의한 bias/variance 효과를 정리하자면 다음과 같다.
- 랜덤성에 의해 individual tree에 대해서는 bias가 증가하고, variance가 증가한다. 단, sample 학습에 대해서는 variance가 감소한다. - 모델 overfitting 해결
- 랜덤성에 의해 증가한 variance는 ensemble 기법에 의해 어느 부분 해소된다.
- 랜덤성에 의한 bias/variance trade off 효과는 classification과 regression이 각각 다르다.
*1번을 생각해보았을 때, feature selction에서 extratree는 랜덤으로 선택하기 때문에 각 노드에서 형성된 tree들은 각기 다른 feature들로 분류기를 형성한다. 따라서 Tree들은 다른 구조를 가질 수 있다.(variance 증가) 하지만, 학습 과정을 생각해보면, 랜덤으로 feature들이 선택되어 나누어진 tree들은 서로 차등이 없기에, 최증 예측 결과에 대해 variance를 줄이는 방향이 될 수 있다.
2번은 랜덤성에 의해 일반적으로, 어느 정도 분류/예측 결과가 각 week tree별로 다르게 결과를 내기 때문에 variance가 증가하는 경향이 있는데, 이는 ensemble(ex. voting, averaging)을 통해 해소가 가능하다.
특히 3번의 경우, 논문에서는 다음과 같이 설명하고 있다.
"in particualr, classification problems can tolerate high levels of bias of clss probability estimates without yielding high classification error rates"
이는 분류 오류 빈도와 각 class 예측 편향도랑 상관관계가 적다는 말은 하고 있는데, 분류 결과, 일부 class에 대한 분류 bias가 높게 나와도, 이는 error일 경우가 적다는 것을 얘기하고 있다.
결론적으로는 회귀 문제보다는 분류 문제에서 Extratree model의 성능이 좋게 평가 될 수 있다.
모델 속, randomization은 randomforest와 extratree에서 다르게 해석될 수 있다고 했다.
randomforest에서는 bootstrap으로 인한 random sampling에 의해 week tree들의 결과들이 variance가 크지만 이는 2번에서 설명했듯이 ensemble 효과로 해소될 수 있다.
extratree에서는 randomly feature selection에 의해 형성된 week tree들의 차등이 없는 효과로, 결과 예측에서 variance를 줄일 수 있지만, bias/variance trade off 효과로 bias가 커질 수 있다. extratree는 bias가 커지는 것을 bagging을 하지 않는 것을 통해, 막을 수 있다.
5. Model Characterizations
-geometrical characterization과 kernel-based model에 대해 설명하고 있는 부분이다.
-앞서 1~4에서 설명한 부분을 수식적으로 풀어 설명한 부분이다.
[References]
- Geurts, Pierre, Damien Ernst, and Louis Wehenkel. "Extremely randomized trees." Machine learning 63.1 (2006): 3-42.
- http://machinelearningkorea.com/2019/08/03/extremely-randomized-tree-%EA%B7%B9%EB%8B%A8%EC%A0%81-%EB%9E%9C%EB%8D%A4-%ED%8A%B8%EB%A6%AC/
Extremely Randomized Tree (극단적 랜덤 트리) – Go Lab
machinelearningkorea.com
엑스트라 트리(Extra Trees) vs 랜덤 포레스트(Random Forest)
끙정입니다. 일전에 데이콘에서 주최하는 '시스템 품질 변화로 인한 사용자 불편 예지' 경진대회를 참가했을 때, 팀원이 pycaret을 사용해 모델의 성능들을 비교한 적이 있습니다. 생전 처음 보는
wyatt37.tistory.com