몬테카를로 방법(Monte Carlo method)
무작위 점을 많이 뿌려 그중 조건을 만족하는 비율로 넓이(area), 적분(integral), 확률(probability)을 어림하는 방법. 정사각형 속 사분원으로 π를 잴 수 있다.
한 변이 1인 정사각형에 점을 아무렇게나
점 하나는 "사분원 안인가?"라는 동전 던지기 한 번과 같습니다. 성공 확률이
같은 방법으로 어떤 모양의 넓이든, 어떤 함수(function)의 적분이든 어림할 수 있습니다. "점이 곡선 아래에 떨어진 비율 × 상자의 넓이"면 됩니다. 규칙적인 격자에 점을 찍는 리만 합(Riemann sum)은 매끄러운 함수라면 1차원에서 훨씬 정확하지만, 차원이 10, 100으로 올라가면 격자 점의 수가 폭발합니다. 축마다 10개씩만 찍어도 10차원이면
이 방법은 1946년 무렵 미국 로스앨러모스 연구소에서 태어났습니다. 폴란드 출신 수학자 스타니스와프 울람이 병에서 회복하던 중 카드놀이 솔리테어에서 이길 확률을 계산하다가, 식으로 푸는 대신 여러 번 해 보고 세는 편이 빠르다는 것을 깨달은 것이 시작이라고 그 자신이 회고했습니다. 울람과 폰 노이만은 이 생각을 핵분열 장치 속 중성자의 움직임을 계산하는 데 썼고, 동료 니컬러스 메트로폴리스가 울람의 삼촌이 드나들던 모나코의 카지노 이름을 따 '몬테카를로'라는 암호명을 붙였습니다.
이 개념이 나오는 긴 글
이 개념을 언급하는 페이지
- 단위원과 라디안
… 법칙⟧). 따라서 그 비율로 π를 어림할 수 있습니다. 이런 식으로 무작위 표본을 세어 값을 구하는 방법이몬테카를로 방법입니다. 원주율은 원을 그리지 않고도 나타납니다. 18세기 프랑스의 박물학자 뷔퐁이 제시한 문제처럼, …
- 리만 합
… 하나가 상쇄되지 않고 남기 때문입니다. 막대를 격자처럼 세우는 대신 무작위로 점을 뿌려 넓이를 재는 방법이몬테카를로 방법이고, 변수가 많은 고차원에서는 이쪽이 낫습니다. 격자는 한 축을 10조각 내면 d차원에서 10^d …
- 확률
… 전형적인 크기는 점 개수의 제곱근에 반비례해 줄어듭니다), 이 방식으로 넓이나 적분을 계산하는 것이몬테카를로 방법입니다. 결과가 연속적이면(과녁의 한 점, 대기 시간) 확률은 개수의 비가 아니라 넓이, 곧 …
- 큰 수의 법칙
… 이 법칙 덕분에 확률을 실험으로 잴 수 있습니다. 무작위 점을 많이 뿌려 넓이나 π를 구하는몬테카를로 방법이 바로 이 법칙 위에 서 있습니다. 신경망을 학습시키는 확률적 경사 하강법도 마찬가지입니다. 무작위로 …
- 뷔퐁의 바늘
… 아니었고, 이렇게 π를 어림할 수 있다고 짚은 사람은 1812년의 라플라스입니다. 그래서 이 실험은몬테카를로 방법의 먼 조상으로 꼽힙니다. π는 원에서 태어났지만, 원이 보이지 않는 곳에서도 "고르게 퍼진 방향"이 …
- 울람 나선
1963년 스타니스와프 울람(폴란드 출신 미국 수학자로,몬테카를로 방법을 함께 고안했습니다)은 지루한 학회 발표를 듣다가 공책에 1부터 나선으로 수를 적고 소수에만 …
- 측도 0
… 불가능한 것은 아닙니다. 확률 0과 불가능은 다른 말입니다. 무작위 점으로 길이와 넓이를 재는 이 셈법이몬테카를로 방법입니다. 거꾸로, 측도 0이면 셀 수 있을까요? 아닙니다. 그림을 로 바꿔 보세요. 칸토어 집합은 깊이 …
- 혼돈
… 그 가운데 비가 온 예보의 비율로 강수 확률을 냅니다. 무작위로 흔든 여러 계산으로 답을 어림하는몬테카를로 방법과 같은 생각입니다. 이어지는 곳. 혼돈은 천체 역학에서 먼저 보였습니다. 1890년 무렵 푸앵카레는 …
- 로렌츠 끌개
… 여러 번 돌리고, 결과가 얼마나 퍼지는지로 불확실성을 잽니다. 무작위로 흔든 여러 계산으로 답을 어림하는몬테카를로방식입니다.
- 무작위 대조 시험
… 가지라서(파스칼의 삼각형에서 맨 위를 0번째 줄로 셀 때 20번째 줄의 가운데 수), 보통은몬테카를로 방법으로 일부만 뽑아 봅니다. 무작위 배정은 1920~30년대 로널드 피셔가 영국 로담스테드 농업 …
- 차원의 저주
… 맞게 들어간 반지름 1인 공은 d = 2에서 넓이의 π/4 ≈ 79%를 차지하고(무작위 점으로 π를 구하는몬테카를로 방법의 그 비율), d = 3에서 52%, d = 10에서 0.25%입니다. d = 이면 입니다. 부피는 거의 …
- 지프의 법칙
… 견해와, 실제 언어의 세부 모양은 무작위 타자와 분명히 다르다는 반론이 함께 있습니다. 원숭이 실험은몬테카를로모의실험의 작은 예입니다. 이어지는 곳. 도시 인구, 웹 페이지가 받는 링크 수, 소득의 윗부분도 멱법칙에 …
- 교란순열
… 번에 성공할 확률이 바로 D_n/n! \approx 1/e 입니다. 시뮬레이션으로 1/e를 어림하는 것은몬테카를로 방법이고, 돌린 횟수가 늘수록 비율이 1/e에 모이는 것은 큰 수의 법칙입니다. 무작위 대응에서 직관과 …
- 확률적 방법
… 증명에 쓰던 무작위성을 계산에 쓰면 무작위 알고리즘이 됩니다. 위에서 500번 칠해 평균을 낸 실험은몬테카를로 방법이고, 칠한 횟수가 늘수록 그 평균이 기댓값에 모이는 것은 큰 수의 법칙입니다. 반 데르 바르던 …
- 무작위 알고리즘
… RSA에 쓸 수백 자리 소수를 이렇게 찾습니다. '몬테카를로'라는 이름은 넓이를 무작위 점으로 어림하는몬테카를로 방법에서 빌려 왔습니다. 둘 다 운에 따라 답이 조금 어긋날 수 있다는 점이 같습니다. 이어지는 곳. ⟦해시 …
- 콜모고로프 복잡도
… 씨앗(난수 생성기에 처음 넣는 수) 하나에서 정해진 계산으로 나오니 K가 작습니다(무작위 알고리즘,몬테카를로 방법). '모형을 적는 길이 + 그 모형으로 데이터를 적는 길이'가 가장 짧은 모형을 고르라는 최소 기술 길이 …
- 최대 엔트로피 원리
… 분포에 대한 KL 발산이 줄어들고, 볼츠만 분포를 정상 분포로 삼는 연쇄를 만들어 표본을 뽑는 것이몬테카를로 방법의 한 갈래인 메트로폴리스 알고리즘(1953년 니컬러스 메트로폴리스 등)입니다. 특징들의 평균을 맞추는 …
- 통계학
… 늘 따져야 합니다. 컴퓨터가 나오자 계산이 이론을 대신하기 시작했습니다. 난수로 분포를 흉내 내는몬테카를로 방법이 그 하나이고, 1979년 브래들리 에프런이 내놓은 붓스트랩(표본에서 다시 표본을 뽑아 흩어짐을 재는 …
- 확률적 경사 하강법과 Adam
… 모드, 신경망에서는 역전파가 계산합니다. 미니배치 기울기는 전체 평균을 무작위 표본의 평균으로 어림하는몬테카를로 방법의 한 예이고, 학습률이 일정할 때 바닥 근처에서 맴도는 θ는 한 걸음이 지금 자리에만 달린 ⟦마르코프 …
- 강화 학습
… V(s') - V(s)\,\bigr] 기댓값을 계산하는 대신 실제로 한 번 일어난 일로 어림하는 것이니,몬테카를로방법처럼 표본으로 평균을 대신하는 셈입니다. α(알파)는 한 번에 얼마나 고칠지 정하는 학습률입니다. …
- 게임 트리 탐색: 미니맥스와 몬테카를로 트리 탐색
… 무작위로 두는 대국(플레이아웃)을 여러 번 해서 이긴 비율을 세면 그것이 그 국면의 거친 평가가 됩니다(몬테카를로 방법). 큰 수의 법칙에 따라 대국 수 n을 늘릴수록 이 비율은 그 국면에서 무작위로 두었을 때의 승률에 …
- 확산 모델
… 공간으로 줄여 계산을 아끼는 부분은 오토인코더가 맡고, 무작위로 뽑은 표본으로 분포를 다루는 생각은몬테카를로 방법과 무작위성에서 이어집니다. 같은 생성 모델이지만 한 토큰씩 차례로 뽑는 방식은 언어 모델입니다.
- 디코딩: 온도, top-p, 빔 탐색
… 엔트로피 원리⟧이고, 분포가 얼마나 퍼졌는지는 엔트로피로 잽니다. 무작위로 뽑아 문장을 만드는 것은몬테카를로 방법처럼 분포에서 표본을 얻는 일이고, 정확한 최선을 찾는 길이 막힌 이유는 동적 계획법이 기대는 겹치는 …
- 모나드
… 조건부 확률과 마르코프 연쇄를 한 가지 합성으로 보게 하고, 씨앗을 넘겨 가며 난수를 만드는 방법은몬테카를로 방법에서 같은 실험을 그대로 다시 돌릴 수 있게 해 줍니다. 순수한 계산과 효과를 타입으로 나누는 설계는 …
- 추론 모델과 테스트 시점 계산
… 그대로 두고 흩어짐만 줄인다는 것은 기댓값과 분산의 성질이고, 표본으로 기댓값을 어림하는 일은몬테카를로 방법입니다. 답을 확인하기가 찾기보다 쉬운 문제에서 이 방법이 잘 듣는다는 점은 P 대 NP 문제의 직관과 …