[ML] Online bagging

 

Background

Poisson distribution

• 정해진 시간 안에 어떤 사건이 일어날 횟수에 대한 기댓값을 λ라고 했을 때, 그 사건이 k회 일어날 확률

• 더 자세한 내용 - 참조

Bagging

• N개의 dataset에서 m개를 복원표본추출하여 새로운 데이터 셋을 생성
• 더 자세한 내용 - 참조

 

Definition

• T: 사이즈가 N개인 training dataset
• M: 표준 batch bagging은 M개의 기본 모델들을 만든다.
• $L_{b}$: batch learning algorithm

 

Online Bagging

각 모델은 원래 학습 세트에서 임의의 샘플을 중복 추출하여 생성된 N 크기의 bootstrap sample에 $L_{b}$를 호출하여 학습힌다.

 

기본 모델의 training set에는 원본 training example 각각의 K 복사본이 포함된다.

 

이는 이항분포이다. (-> 원본 트레이닝 예가 각 트레이닝 예를 k번 가질 확률은 이항분포를 따른다)

N -> ∞일 때, K의 분포는 Poisson(1) 분포인 경향이 있다: P(K = k) ~ exp(−1)/k!

 

[1][2]에서 논의된 바와 같이, 우리는 다음과 같이 온라인으로 배깅을 수행할 수 있다: 각 training example d=(x,y)가 우리의 알고리즘에 제시될 때(들어오면), 각 기본 모델마다 example K~Poisson(1)를 선택하여 Online base model learning algorithm인 $L_{o}$를 사용하여 베이스 모델을 업데이트한다.

새로운 예는 online 및 batch bagging에서 동일한 방식으로 M base model의 비가중 투표(unweighted voting)로 분류된다.

 

[이항분포와 Poisson 분포 설명] - 2019/08/27 - [Machine learning] - [ML] 푸아송 분포(Poisson distribution)

 

• d: 새로운 training example set
• h: training된 base model set

 

동일한 original training set를 두 개의 bagging algorithm에 공급할 경우, original training set의 크기가 무한대로 증가함에 따라 batch 및 online bagging으로 base model에 공급되는 training set에 대한 분포가 수렴된다는 것을 증명했다.

 

 

 

Summary

• Poisson($\lambda$)로 만들어진 random number → k
• $\lambda$는 여기서 1로 설정
• 새로운 데이터가 들어올 때, 각 base model(tree)마다 k를 뽑는다

 

 

K의 의미:

bagging으로 sample을 뽑았을 때, 현재 들어온 데이터가 k번 나왔을 것이다. 그러므로 이 데이터에 대해 k번 업데이트를 해야한다.

 

 

$\lambda$=1일 때, k는 보통 1이 나올 확률이 높음.

 

우리가 bagging으로 sampling할 때, 같은 데이터 셋을 여러번 뽑을 확률은 낮으므로 $\lambda$=1로 설정했다고 생각됨.

 

 

• 이 데이터를 현재 tree에 k번 업데이트한다.

 

 

 

 

 

 

 

출처 - [Online Bagging and Boosting] 논문

출처 - [On-line Random Forest] 논문