Random forest

Addressing non-linearly separable data

Decision tree

비선형 분류기(Non-linear classifier)

트리는 축(axis) 별로 데이터를 반복 분할하며,
복잡한 경계도 표현 가능

• Pros: 해석 가능, 사용이 간편
• Cons:학습이 어려움, 과적합(overfitting) 되기 쉬움

Ensemble methods

각각의 모델(트리, SVM, 뉴럴넷 등)을
독립적으로 혹은 순차적으로 학습시켜 다양한 관점을 확보
→ 최종 예측은 개별 모델의 예측을 종합해서 결정

장점

• 예측 성능 향상
• 여러 모델의 약점을 서로 보완
• 다양한 모델 결합 가능
• 구현 간단, 큰 튜닝 불필요
• Bagging은 거의 파라미터 없이 바로 사용 가능

단점

• 모델 크기·복잡도 증가

Bagging VS Boosting

Bagging

1. 원본 데이터에서 중복 허용(random bootstrap) 샘플링으로
   여러 개의 서브셋을 만듦
2. 각 서브셋은 서로 겹치기도 하지만, 모델마다 독립적으로 랜덤하게 뽑힘

Boosting

1. 원본 데이터를 순회하면서 잘못 분류된 샘플에
   더 큰 가중치를 부여해 다음 분류기가 집중 학습하도록 함
2. 오류가 난 곳을 점점 더 강조해서 모델들이 순차적으로 보완

Random Forest

randomized trees을 모은 앙상블

• K개의 독립적인(tree) 결정트리 생성
  원본 데이터에서 중복 허용 랜덤 샘플을 뽑아 각 트리를 학습

• 병렬 학습
  모든 트리가 서로 영향을 주지 않고 병렬(Parallel)으로 학습

• 예측 시 앙상블 결합
  각 트리에서 나온 예측(레이블 혹은 확률)을 투표(vote) 하거나 평균 내어 최종 결정

Bagging

앙상블 모델(Bagging)의 클래스 c 에 대한 예측 확률
: 단순 평균으로 정의

T : 앙상블에 참여한 모델(트리) 수
$p_t(c | v)$ : t번째 모델이 예측한 입력 v가 클래스 c일 forest output probability

Bagging 기법의 핵심 원리와 동작 과정

알고리즘 흐름 관점

• Bootstrapping (무작위 샘플링)

• 병렬 모델 학습
  각 샘플셋마다 동일한 학습 알고리즘(ex. 결정 트리)을 적용해
  분류기(Classifier)를 만들어 냄

• Aggregating (결합)
  새 입력 v에 대해 각 분류기가 출력한 예측 확률들을 모아
  확률 평균 or 다수결 투표(majority vote) 방식으로 결합하여 최종 예측

통계적 효과(작동하는 이유)

• 분산 감소(Variance Reduction)
  서로 다른 서브셋으로 학습된 모델들의 예측 오차는 독립적이므로,
  평균·투표를 통해 편차가 상쇄

• 과적합 완화(Overfitting 완화)

• 불안정 학습기(Unstable Learner)에 특히 효과적
  ex. 결정 트리

Bootstrapping

무작위 샘플링(with replacement)
전체 훈련집합 S에서 크기 n인 샘플을 중복 허용으로 뽑아
$S_1, S_2, \ldots, S_M$을 생성

Aggregating

Committee Prediction
: 새 입력 x에 대해 각각의 모델 $h_i(x)$가 반환한 예측을 모아

평균(회귀) 또는 다수결 투표(분류)로 결합

Boosting

알고리즘 흐름 관점: 약한 학습기를 순차 보강

초기 가중치 부여

• 모든 훈련 샘플에 동일한 가중치를 줌

순차적 학습(Sequential Training)

• 첫 번째 모델(weak learner) $h_1$을 학습시킴
• $h_1$이 잘못 분류한 샘플들의 가중치를 증가
• 가중치가 업데이트된 데이터를 바탕으로 두 번째 모델 $h_2$ 학습
• 다시 오차 샘플 가중치 조정 → $h_3$ …
  T 단계까지 이어감

대표 알고리즘 : AdaBoost

장점

• 간단하고 범용적: 어떤 약한 학습기(결정트리, 선형 분류기)와도 결합 가능
• 사전 지식 불필요: 약한 학습기의 내부 구조나 성능 특성을 몰라도 됨
• 높은 정확도: 편향(Bias)을 효과적으로 줄여 단일 모델보다 성능 우수
• Non-parametric: 데이터 분포 가정 없이 적용

Adaboost

순차적 약한 학습기(Weak Learner) 학습

초기 가중치 설정 : N개의 훈련 샘플에 모두 동일하게 1/N 을 부여

오분류 샘플의 가중치는 높이고, 정분류 샘플의 가중치는 낮춰서
다음 단계 학습기가 틀린 곳에 더 집중하도록 만듦

최종 강한 학습기(Strong Learner) 결합

M단계까지 만든 모든 약한 학습기를 가중 합으로 결합

AdaBoost 알고리즘이 사용하는 세 가지 quantities

샘플 가중치 $w_n^{(m)}$
: m번째 단계에서 훈련 샘플 n에 부여된 중요도

오류율 $\mathcal{E}_m$
: m번째 약한 학습기가 가중치 데이터에 대해 계산한 분류 오류율

모델 가중치 $α_m$
: 최종 앙상블에서 $h_m$이 차지하는 기여도(믹싱 가중치)

Bagging and Boosting

: 의사결정트리(Decision Tree)를 개선

Bagging을 통한 개선 → 랜덤 포레스트(Random Forest)

랜덤 포레스트

• Bagging된 트리에 노드를 분할할 때마다
  피처를 무작위로 일부만 선택하는 추가 무작위성 도입

• 서로 다른 트리 간의 상관성을 낮춰 더 안정적이고 성능 좋은 앙상블 완성

Boosting을 통한 개선 → 그래디언트 부스팅 머신(GBM)

Random Forests

여러 개의 랜덤화된 결정 트리(randomized decision trees)를
모아 만든 앙상블 모델

데이터 샘플링과 feature 선택 두 가지 레벨에서 모두 랜덤하게 모델을 구성

Training Random Forests

결정 트리 학습의 전체 흐름

트리 성장(Growing a Tree)

루트 노드(root node)에서 시작해,
각 노드(node)에 할당된 부분 데이터셋 $S_j$을 기준으로 계속 분할(split)하며,
종료 조건이 만족될 때까지 이 과정을 반복

노드 분할(Splitting a Node)

각 내부 노드(internal node) j에서,
현재 데이터셋 $S_j$를

• 왼쪽 자식 $S_j^L$
• 오른쪽 자식 $S_j^R$

두 부분으로 나눔

분할 기준 함수(split function)

v : 샘플의 feature 벡터
θ : 어떤 feature를 어느 값을 기준으로 분류할지 에 대한 파라미터

이 기준에 따라,
처럼 데이터를 분리

파라미터 최적화(Choosing θ)

각 노드마다 여러 후보 θ를 시험해 보고,
최적의 θ*를 선택

종료·리프 노드(Leaf/Terminal Node)

더 이상 분할할 필요가 없다고 판단되면(종료 조건), 해당 노드를 리프로 마무리

랜덤 포레스트 내 트리가 어떻게 노드를 분할(split)하는지

split function :

$h(v,θ)∈{0,1}$
: 입력 샘플 v가 왼쪽 자식인지 오른쪽 자식인지 결정
→ 0 : 왼쪽, 1 : 오른쪽

$θ={φ,w,τ}$
: 분할 규칙을 구성하는 세 가지 파라미터 세트

• φ(v) (Feature Bagging)
  v의 전체 피처 벡터 중 무작위로 일부(feature subset)만 골라낸 뒤
  그 부분 벡터를 반환하는 필터링 연산
  → 서로 다른 feature 조합으로 분할 기준을 찾게 해, 트리 간의 다양성↑

• w (Hyperplane Weight Vector)
  φ(v)와 내적을 수행해 (φ(v)⋅w)를 만듦
  → 어떤 방향으로 데이터를 분리할지 정하는 가중치 벡터

• $τ=(τ_1,τ_2)$ (Threshold Values)
  $φ(v)⋅w$ 값이 구간 $(τ_1,τ_2)$ 안에 있으면 1, 밖이면 0
  → 2개의 boundary 설정

Parameter optimization

노드를 어떻게 나눠야 최적의 분할?

정보 이득이 높은 분할이 좋음

Entropy and Information Gain (Training Objective Function)

결정 트리에서 각 노드를 어떻게 최적으로 분할할지 결정하는 기준

엔트로피 $H(S_j)$

노드 j에 모여 있는 훈련 샘플 집합 $S_j$의
불확실성(uncertainty)을 측정하는 지표

Information Gain $I_j$

= 분할 전 불확실성 - 분할 후 불확실성

→ 분할을 통해 얼마나 줄인 불확실성(엔트로피)가 크면 클수록 좋은 분할이므로,
정보 이득 $I_j$ 가 최대가 되는 $θ$를 선택

split 전 entropy 큼
split 후 entropy 작아짐

Boosting with depth of a tree

노드마다 점점 더 작은 구역으로 쪼개면서 클래스의 순도(purity) 를 높임

종료 조건 (Termination Conditions)

• 깊이 제한(Depth Limit)
• 최소 샘플 수(Minimum Samples)

Ensemble Decision (Test)

앙상블 결합 (Ensemble Decision)

확률 평균(Averaging)

T개의 트리가 반환한 각 클래스별 확률을 단순 평균해서
최종 클래스 확률 분포를 만듦

→ 확률이 가장 큰 클래스를 선택

다수결 투표(Major Voting)

확률 대신, 각 트리가 가장 높게 점수 준 클래스를 1표로 count
ex. Tree 1은 ‘빨강’, Tree 2는 ‘초록’, Tree 3은 ‘빨강’
→ 최종 ‘빨강’