Random Algorithm

무작위 알고리즘은 크게 2가지 종류가 있습니다. 하나는 몬테카를로 알고리즘이고, 다른 하나는 라스베가스 알고리즘입니다. 라스베가스 알고리즘은 항상 정확한 답을 주거나, 아니면 아예 답을 찾지 못합니다. 반대로 몬테카를로 알고리즘은 항상 정확한 답을 주지는 않지만, 어느 정도의 자원 투입이 보장되면 상당한 수준으로 원하는 답을 근사해낼 수 있습니다.

머신러닝으로 풀고자 하는 문제 대부분이 정확한 답을 구하기 어렵기 때문에, 라스베가스 방법보다는 몬테카를로 방법을 사용하는 것이 더 적합하다고 할 수 있습니다.

몬테카를로 방법 Monte Carlo Method

기본적으로 몬테카를로 방법은 무작위로 난수를 생성하고, 특정 연산에 입력값으로 넣어 결과를 추출합니다. 이런 과정을 여러 번 반복하면 연산의 파라미터값을 추정할 수 있습니다.

쉽게 말해서, 수많은 데이터를 때려박고 오차를 통해 파라미터를 추정하는 방법의 대표적인 케이스가 바로 몬테카를로 방법입니다. 머신러닝에서 모델이 학습하는 방법과 동일하죠.

대표적인 예시로 원주율을 추정하는 방법을 살펴보겠습니다.

원의 넓이를 구하는 공식은 $S=\pi r^2$ 이죠? 이걸 $\pi$가 파라미터인 방정식으로 볼 수 있습니다. 즉, $S=f_\pi(r)$인 셈입니다. 이 때 최적의 파라미터 $\pi$를 추정하기 위해 다음과 같은 방법을 사용합니다.

(1) [0, 1], [1, 0] 범위에서 무작위 난수를 추출합니다.
(2) $x^2+y^2\leq1$를 만족하는지 판별합니다.
(3) (1)과 (2)를 충분히 반복합니다.

위 그림에서 $\pi\simeq 3.14159...$로 근사되는 것을 볼 수 있습니다. 이 과정에서 별도의 모듈을 통해 이 방법이 얼마나 정확한지를 평가할 수도 있습니다. 대표적으로 Mean Squared Error(MSE), Evidence of Lower BOund(ELBO) 등을 손실함수로 사용하면 내가 만든 모델이 어느 정도의 오차를 보이는지 알 수 있습니다.

참고문헌

1. Deep Learning (Goodfellow, 2016)
2. 위키백과 - 몬테카를로 방법