난수생성기(Random Number Generator) 와 몬테카를로 적분(Montecarlo Integration)
난수생성기와 몬테카를로 적분을 이해하면 베이지안 통계치를 추정하고 이해하는데 큰 도움이 됩니다.
뿐만 아니라, 딥러닝 뿐만 아니라 모델링 전반을 이해하는데 있어서도 필수적 요소입니다.
글의요약
- Pseudo Random Number는 컴퓨터에서 특정 연산에 의해 생성되며, PC의 Word단위에 의존하고, 상호 미세한 상관관계를 가진다.
- Inverse Method를 활용해 Uniform 분포를 따르는 난수를 생성할 수 있다. Uniform 난수를 활용해 Normal, Exponential 등 다양한 난수도 생성할 수 있다.
- 몬테카를로 방법(Monte Carlo Method)은 posterior 난수를 생성하고 이의 평균, 분산을 활용해 parameter를 추정하는 방법을 일컫는다.
1. Random Number Generator
A. Pseudo Random Number
난수를 생성하는 방법을 얘기하기 전에, 난수의 개념에 대해서 짚고 넘어가야 합니다.
지난 아티클에서 다뤘던 내용입니다. 컴퓨터로 만드는 난수는 “Pseudo”라는 말이 생략됩니다. 이는 ‘진짜는 아니지만 이와 비슷한’ 정도의 의미로 생각할 수 있습니다. 즉, 컴퓨터로 만드는 난수는 모종의 블랙박스과정을 거쳐 생성되며, 이는 진짜같지만 특정한 알고리즘을 거쳐 생성된 숫자라고 말할 수 있습니다.
이 블랙박스를 조금만 더 자세히 들여다 보면, Seed(Input) → 연산 → Output (또다른 Seed) → 연산 → … 의 과정을 거칩니다.
풀어쓰면, Seed값을 Input으로 삼아 특정한 연산을 적용합니다.
( 예를들어 Seed² = 95764…. 중에서 764만을 Output으로 삼고 이 Output을 다시 Seed값으로 활용하는 방법으로 난수를 생성합니다. )
여기엔 분명한 한계점이 존재하는데, 바로 컴퓨터의 연산단위인 워드(Word)의 크기에 의존한다는 점입니다.
(흔히들 32 / 64 bit컴퓨터를 사용하고 있을텐데, 이는 곧 컴퓨터의 Word의 Size를 나타냅니다.)
즉, Word의 Size는 유한하기때문에 언젠가(= 난수를 무지막지하게 생산하다보면) 처음 초기치(seed) 로 돌아온게 됩니다. 따라서 엄밀히 말하면 Pseudo 난수는 서로 아주 미세하게 상관관계가 존재(correlated)한다고 할 수 있습니다.
B. Random Number Generator
본격적으로 난수생성의 방법에 대해서 논의하고자 합니다.
전제가 한가지 필요한데 바로 Pseudo 난수 생성과정을 통해 Uniform(0,1)의 분포를 따르는 난수를 생성할 수 있음을 가정합니다.
이제부터 이 분포를 U라고 부르며 u는 Uniform(0,1)분포를 따른다고 가정하겠습니다.
Inverse Method
확률론에서 역분포를 찾을때 쓰는 방법을 활용하면 (전개 생략) 다음과 같은 결론을 얻게 됩니다.
여기서 CDF란 특정 분포의 누적확률분포를 말합니다. 자세한 설명은 생략합니다. 이 방식을 활용해서 Exponential Distn, Geometric Distn 등을 난수를 만들 수 있습니다.
1. Exponential Random Number
만약 Exp(1)을 따르는 난수 X를 생성하려면 어떻게 해야할까요?
그 방법은 다음과 같습니다.
Exp(2)와 같이 Scale이 조정되는 경우에는 lambda를 곱하여 스케일을 조정합니다.
2. Geometric Distribution
(1) 과 다르게 Geo(p)를 따르는 난수를 생성하기 위해서는 어떻게 해야할까요? 이 방법 또한 복잡하지 않습니다.
이 결과가 나오기 위해서는 몇가지 수식적인 전개가 필요합니다.
여기서는 생략하지만, EXP 난수의 CDF를 변환하고 치환하면 geometric 분포의 꼴을 하는것을 쉽게 찾을 수 있습니다.
Transformation Methods
이제는 앞서 구한 난수들을 몇개의 방식들을 활용해 새로운 분포를 따르는 난수로 변환하고자 합니다.
1. Normal Distribution : Box-Muller Transformation
정규분포를 따르는 서로 독립인 난수 2개를 생성하는 방법입니다.
방법 1)
방법 2)
각 방법을 참고하면 정규분포를 따르는 독립적인 난수 2개를 구할 수 있으며,
평균(mu)와 분산(sigma)의 Scale이 조정되는 경우, 아래와 같이 Normal(0,1)의 Z 분포의 스케일 업 변환이 필요합니다.
2. Beta Distribution
베타 분포를 따르는 난수를 생성하는 방법은 다음과 같습니다.
이 외에도 난수들을 생성하는 다른 방법론들이 있습니다. 이 글에 쏟아내기에는 방대하기에 여기까지만 소개하겠습니다.
2. Monte Carlo Integration
A. Monte Carlo Method
몬테카를로 방법은 난수를 이용하여 확률을 근사시켜 추정하는 알고리즘을 말합니다.
왜 몬테카를로냐 하면, 핵무기 개발 당시 개발한 알고리즘의 코드명으로, 당시 모나코에 있던 카지노의 이름을 빌려 왔기 때문이라고 하죠.
이 방식을 활용해서 아래 함수의 기대값을 추정합니다.
베이지안 통계학에서는 주로 Posterior의 추정치를 계산하기 위해서 사용합니다.
몬테카를로 알고리즘
이 방식은 굉장히 많은 n개의 수많은 난수를 뽑고 이에대한 평균과 분산을 구한것 뿐이죠.
수렴속도와 정확성(변동성) 에 있어서 약간 의심이 갑니다.
그리고 g라는 Posterior가 이미 알려지지 않은 구하기 어려운 분포라고 하면 몬테카를로 방식이 활용하기 어렵다는 단점이 생깁니다.
B. Importance Sampling
몬테카를로 방식이 홀로 안고있는 변동성을 조금이라도 줄이기 위해서 그리고 posterior에 근사하는 분포를 위해서 Importance Sampling 방식이 고안되었습니다.
그래서 우리는 여기서 pi 라는 분포를 가정합니다.
pi는 g의 support보다 넓고 샘플링이 용이한 분포를 선택합니다.
pi를 적용한 새로운 샘플링 알고리즘은 다음과 같습니다.
- Importance Sampling
이 방식은 g(x)와 f(x)의 적분상수를 모르는 경우 올바른 추정치를 낼 수 없습니다. (biased)
따라서 Importance Sampling의 3. 과정을 아래와 같이 바꾸어 bias를 제거할 수 있습니다.
C. Implementation
R에서 몬테카를로 방식을 이용한 방법을 소개합니다.
Montecarlo Method, Importance Sampling, Biased의 방식을 활용해서
N(0,1)을 따르는 X가 P( X > 3)일 확률을 구하는 code 입니다.
3. 마치며
몬테카를로는 베이지안 통계학의 깁스샘플링을 이해하기 위한 기본적인 개념입니다.
나아가 딥러닝 파라미터 학습 방법에도 유용한 상식이니 참고하면 큰 도움이 될 것 이라고 생각합니다.
참고
[1] http://mwultong.blogspot.com/2008/03/pseudo-random-uniform-random-number.html
[2] https://ko.wikipedia.org/wiki/%EB%AA%AC%ED%85%8C%EC%B9%B4%EB%A5%BC%EB%A1%9C_%EB%B0%A9%EB%B2%95
[3] https://namu.wiki/w/%EB%AA%AC%ED%85%8C%20%EC%B9%B4%EB%A5%BC%EB%A1%9C#s-1
