Bagging

:다중트리를 어떻게 생성하느냐 & 최대한 다양성을 어떻게 유지할건지

• Bootstrapping: original data로부터 랜덤한 subset을 여러개 생성 ⇒ various tree
• Aggregation: 다양한 트리를 고려해서 최종 예측 생성

Bootstrapping

Repeatedly extracting data from the initial training dataset to generate multiple distinct training datasets. Such sets are useful to minimize prediction variability, consequently significantly enhancing their predictive accuracy.

Aggregation

Bring together multiple learners, each trained on distinct bootstrapped samples, and average their predictions to decrease the prediction variance.

Random Forests - bagging의 예시

Random Forest for regression & classification

1. bootstrap data 생성 :랜덤 select (중복도 허용)

2. 데이터를 사용해 트리 형성 : B개의 트리에 대해 반복

3. Aggregate result from different trees : testing data를 대입하고 결과 총합

   regression에는 averaging, classification에는 voting

   만약 “yes”개수 > “No”개수라면 “yes”택 ⇒ 개수 많은 거 선택

목표: 각 트리들 간의 상관관계를 줄여서 배깅(bagging)의 분산 감소 효과를 향상시키되, 분산이 너무 많이 증가하지 않도록 하라

배깅을 사용할 때 여러 트리를 독립적으로 학습시키면서 예측 모델의 분산을 줄이는 것을 목표로 하는데, 트리들 간의 상관관계가 높으면 분산 감소 효과가 떨어질 수 있습니다. 따라서 상관관계를 줄여 각 트리가 서로 다른 데이터를 학습하게 만들어 예측 성능을 높이는 동시에, 분산이 너무 많이 증가하지 않도록 주의해야 한다는 뜻

Out-of-bag sample

testing data로 Out-of-bag sample 가능

처음에 랜덤하게 뽑히지 않았던 sample들.

Variable(feature) importance

Gini importance

Total decrease in node impurity averaged over all trees in the ensemble;

"앙상블 내 모든 트리에 걸쳐 노드 불순도(impurity)의 총 감소량을 평균한 값"

랜덤포레스트에서 각 트리가 데이터를 분할할 때마다 노드 불순도(예: 지니 계수, 엔트로피)가 감소하는데, 모든 트리에 걸쳐 이러한 감소량을 합산한 후 평균을 낸 값을 의미합니다. 이 값은 특정 변수가 예측에 얼마나 기여했는지를 평가하는 데 사용됩니다.

노드 불순도를 크게 줄이는 feature일수록 모델에서 더 중요한 역할을 한다는 의미

부모노드의 gini impurity에서 자식 노드의 gini impurity에 가중치를 곱해서 빼줌 → 그 차이가 크면 클수록 중요한 feature라는 뜻

Permutation importance(randomization)

모델에서 각 특성(피처)이 얼마나 중요한지를 측정하는 방법

• 원래 데이터셋으로 모델의 성능을 측정합니다.
• 각 특성 값을 무작위로 섞어서, 해당 특성이 가진 정보가 무의미해지도록 합니다.
• 변형된 데이터로 모델의 성능을 다시 측정합니다.
• 성능이 크게 떨어질수록 그 특성은 모델에 중요한 영향을 미친다고 평가합니다.

결측값 채우기

결측값이 있는 행에 대해서 lable이 같은 것만 본다! 해당 feature에 대해 가장 많이 나타나는 값 선택

숫자라면 평균값 선택

Similarity table

같은 leaf에 도달하는 레이블이면 1, 그렇지 않으면 0을 취해서 모든 레이블에 대해 테이블 생성

결측값이 있는 레이블(r9), 테이블에서 숫자가 가장 큰 레이블(r9와 유사도가 가장 큰)

만약 Testing data에 결측값이 있다면?

both cases를 모두 고려해본다 ⇒ 둘다 해보고 더 나은걸 선택

Boosting

original data로 트리를 형성 → 잘못 분류된 sample을 고려해서 다음 Tree를 형성

모델 자체에서 가중치(α)를 부여하고, sample에도 가중치 부여 (w)

⇒ 매번 샘플마다 다른 가중치를 부여하는지?

각 결과에 서로 다른 가중치를 부여해서 성능이 좋은 트리에서 나온 결과를 더 고려하겠다는 의미

Adaboost

• combination of weak learners(stump) level이 1개인 트리(부모와 2개의 자식노드만 있음)
• 각각의 leaner(stump)는 다른 가중치를 갖는다.
• 각각의 sample은 다른 가중치를 갖는다.
• letter learner는 이전 학습자가 misclassified sample에 더 집중함으로써, 이전 학습자의 성능을 향상시키기 위해 더 효과적으로 학습된다.

알고리즘

1. 초기 가중치: 각 샘플의 가중치는 모두 동일하게 1/N

2. 각 트리(stump)마다 error rate 계산 (트리개수 m개만큼 반복)

   각 트리마다 가중치 계산 (α_m)

   각 샘플마다 가중치 업데이트(I함수에서 misclassified면 1, 잘 분류되면 0이라서 결국 misclassified의 가중치만 update됨)

3. Output G(x) 는 G_m(x)와 가중치(α_m)를 곱한 값을 모두 더한 뒤 sign함수를 취한 값 ⇒ 1 또는 -1의 label을 가짐

각 feature들이 샘플을 어떻게 분류하는지 체크하고 gini impurity 계산

gini impurity가 작은 feature를 택한다!!

classifier의 가중치(α_m) 계산

α_m = log((1-err)/err)

가중치 업데이트

여기서 잘못 분류된 샘플의 가중치만 업데이트됨!

그래서 이 가중치를 어떻게 활용할까?

1. 가중치 정규화(normalize) : 가중치의 총합이 1이 되도록 조정하는 과정
2. Gini imputiry 계산할 때 사용 또는 샘플링 하는데 사용

샘플링할 때 가중치를 사용하면 가중치가 높은 샘플이 selected될 확률이 높아진다!!

Use it as the probability to pick the corresponding sample

각각의 stump는 서로 다른 가중치를 갖는다

Gradient boosting

• Adaboost에서는 stumps를 사용했지만 Gradient boosting는 실제 트리를 사용함(limitation on the number of leaves)
• leaf에서부터 시작해서 트리로 올라감

알고리즘

1. Compute the first leaf by taking average
2. Compute the residual
3. Build the regression tree with leaves residual
4. Take the average if the leaf contains ≥ 2 residuals
5. Update prediction

예시

1. 평균을 취해서 첫번째 leaf 계산하기
   예측할 feature의 평균을 구함 ⇒ 첫번째 leaf (initial hypothesis)

2. Residual 계산하기 ⇒ 두번째 트리 형성
   앞에서 구한 평균과 feature값과의 차이가 Residual
   (ground truth - hypothesis)

3. 다음 트리 형성 with residuals
   트리의 리프 노드(leaf node) 수를 4 이하로 제한한다고 가정
   만약 각 리프노드의 수가 2개 이상이면 평균을 취한 값으로 대체.

4. learning rate α 적용하기

   각각의 sample에 대해 어느 leaf(residual)에 도달했는지 찾고 residual에 α값 곱한 만큼 현재 hypothesis에 더해줌 ⇒ Predicted값 계산

   α가 크면 degree updata가 빨라짐

5. Residual 계산 ⇒ 세번째 트리 형성
   앞에서 계산한 Predicted값이 현재 hypothesis가 됨.
   (ground truth - current hypothesis) = Residual

6. Feed testing data