랜덤 포레스트에서 어떤 데이터 포인트가 부트스트랩 샘플에 포함되지 않을 확률

원문에서는 랜덤 포레스트 모델이 훈련 데이터를 무작위로 선택할 때 한번도 포함되지 않을 확률을 대략 1/3로 표현했습니다. 옮긴이의 주석에서 한가지 사례를 들어 100개의 샘플 중 한번도 선택되지 않을 확률을 계산했더니 36.6%가 나왔습니다. 이 글에서는 조금 더 이를 일반화해 보겠습니다.

n개의 샘플에서 하나를 무작위로 추출했을 때 선택되지 않을 확률은 1-\dfrac{1}{n}입니다. 그리고 이를 n번 반복했을 때 한번도 선택되지 않을 확률 y는 이 값을 n번 곱하면 됩니다.

y = \left(1 - \dfrac{1}{n}\right)^n

수학적 트릭을 위해 양변에 로그를 취합니다.

ln(y) = ln \left( 1 - \dfrac{1}{n}\right)^n = n\,ln \left( 1 - \dfrac{1}{n}\right)

그런 다음 새로운 변수 x = \dfrac {1}{n}를 적용합니다.

= \dfrac {1}{x} ln (1 - x) = \dfrac {ln (1 - x)}{x}

n \to \infty, 즉 x \to 0일 때 로피탈의 정리를 적용하면

ln(y) = \underset{x \to 0}{\lim} \dfrac {ln (1 - x)}{x} = \underset{x \to 0}{\lim} \dfrac {\frac{d}{dx}ln (1 - x)}{\frac{d}{dx}x} = \underset{x \to 0}{\lim} \dfrac{-1}{1-x} = -1

이 됩니다. 이제 로그를 풀고 y에 대해 정리하면

y = e^{-1} = 0.3678794...

이 됩니다. 즉 샘플 개수 n이 아주 클 때, 어떤 샘플이 무작위한 n번의 선택에 한번도 포함되지 않을 확률은 36.8%정도 입니다. 그리고 샘플 개수가 아주 작을 때 가령 n=3이면

y = \left(1-\dfrac{1}{3}\right)^3=0.296296...

입니다. 그래서 샘플의 개수 차이가 크더라도 대략 30~37% 사이가 됩니다. 따라서 랜덤 포레스트에서 선택되지 않고 누락될 샘플의 양은 대략 1/3정도라고 말할 수 있습니다.