준몬테카를로

수치해석 통계 마지막 수정: 2026-08-04 04:14:25

1. 개요[편집]

준몬테카를로 Quasi-Monte Carlo (QMC)
아이디어	난수 대신 일부러 고르게 깔린 결정론적 점열을 쓴다
오차 지표	별 불일치 $D_N^{*}$ + 아디-크라우제 변동 $V_{HK}(f)$
수렴률	$O((\log N)^s/N)$ vs. MC의 $O(N^{-1/2})$
대표 점열	소볼, 홀턴, 니더라이터, 포르, 격자규칙
실무 필수	무작위화 QMC (스크램블링 · 무작위 이동)

난수가 좋은 이유는 편향이 없어서다. 난수가 나쁜 이유는 뭉치고 비어서다. QMC는 전자를 포기하고 후자를 고친다.

준몬테카를로(Quasi-Monte Carlo, QMC)는 몬테카를로 방법의 무작위 표본을 의도적으로 균일하게 배치된 결정론적 점열(저불일치 수열)로 바꿔 적분 수렴률을 끌어올리는 기법이다. 목표 적분

I = \int_{[0,1]^s} f(\mathbf{x})\, d\mathbf{x} \;\approx\; \frac{1}{N}\sum_{i=1}^{N} f(\mathbf{x}_i)

에서 추정식은 MC와 글자 그대로 똑같다. 다른 것은 $\mathbf{x}_i$ 를 어떻게 고르느냐뿐이다. 그런데 이 한 가지 차이로 오차 이론 전체가 확률론에서 수론과 조합론으로 갈아탄다.¹

MC의 오차는 중심극한정리가 지배하므로 표준오차 $\sigma/\sqrt{N}$ 이고, 차원 $s$ 와 무관하다는 것이 최대 미덕이다. 대신 $N$ 을 100배 늘려야 정확도가 10배 좋아진다. QMC는 이 $N^{-1/2}$ 벽을 거의 $N^{-1}$ 까지 밀어붙이는 대신, 차원 의존성과 오차 추정 능력을 대가로 내놓는다. 그리고 그 대가 중 후자는 무작위화 QMC로 되찾아올 수 있다.

2. 불일치와 코크스마-흘라브카[편집]

점 집합 $P = \{\mathbf{x}_1,\dots,\mathbf{x}_N\}$ 이 얼마나 고르게 깔렸는지를 재는 척도가 별 불일치(star discrepancy)다. 원점에 고정된 상자 $B = \prod_{j=1}^{s}[0, b_j)$ 들에 대해

D_N^{*}(P) = \sup_{B} \left| \frac{\#\{ i : \mathbf{x}_i \in B \}}{N} - \mathrm{vol}(B) \right|

즉 “어떤 상자에서 실제 점 비율과 부피가 최대 얼마나 어긋나는가”다. 무작위 점열은 $D_N^{*} \sim \sqrt{\log\log N / N}$ 정도로 감소하는데, 잘 설계된 결정론적 점열은 $O((\log N)^s / N)$ 까지 내려간다.

이 기하량을 적분 오차로 옮겨주는 다리가 코크스마-흘라브카 부등식이다.

\left| \frac{1}{N}\sum_{i=1}^{N} f(\mathbf{x}_i) - \int_{[0,1]^s} f \right| \;\le\; V_{HK}(f)\, D_N^{*}(P)

여기서 $V_{HK}$ 는 아디-크라우제 의미의 변동(variation in the sense of Hardy-Krause)이다. 오차가 적분함수의 성질과 점열의 성질로 완전히 분리된다는 점이 아름답고, 확률이 전혀 개입하지 않는 결정론적 상한이라는 점이 인상적이다.

그런데 실무에서 이 부등식은 거의 쓸모가 없다. 이유가 셋이다.

$V_{HK}(f)$ 를 계산할 수 있는 실제 문제가 거의 없다. 게다가 축에 나란하지 않은 불연속면이 하나만 있어도 $V_{HK} = \infty$ 라 상한이 무한대가 된다.
$D_N^{*}$ 자체를 정확히 계산하는 것이 차원에 대해 계산적으로 매우 비싸다(고차원에서 사실상 불가능).
상한이 극도로 비관적이다. 실측 오차보다 몇 자릿수 크게 나오는 것이 보통이다.

그래서 코크스마-흘라브카는 “QMC가 왜 원리적으로 되는가”의 설명으로 남고, 실제 오차 막대는 뒤에 나올 무작위화로 얻는다.

3. 저불일치 수열[편집]

$O((\log N)^s/N)$ 을 달성하는 수열을 저불일치 수열(low-discrepancy sequence)이라 부른다. 유한 점 집합으로 한정하면 지수가 하나 줄어 $O((\log N)^{s-1}/N)$ 이 된다(해머슬리 집합).

홀턴 수열. 각 차원에 서로 다른 소수 $p_j$ 를 배정하고 정수 $i$ 의 $p_j$ 진 전개를 소수점 아래로 뒤집는(radical inverse) 가장 소박한 구성. 구현이 열 줄이라 좋지만 차원이 커지면 큰 소수 축들 사이에 강한 상관 줄무늬가 생겨 실무에서는 뒤섞기(scrambled Halton)가 필수다.
소볼 수열. 기저 2의 디지털 수열로, GF(2) 위의 원시 다항식에서 유도한 방향수(direction numbers)와 비트 XOR만으로 점을 생성한다. 정수 연산만 쓰므로 매우 빠르고, 그레이 코드 순회를 쓰면 점당 XOR 한 번이다. 오늘날 QMC의 기본값.
포르·니더라이터 수열과 $(t,m,s)$ -네트. 니더라이터의 통합 이론에서 이들은 전부 디지털 네트의 특수한 경우로 정리된다. $(t,m,s)$ -네트는 부피 $b^{t-m}$ 인 모든 기본 구간에 정확히 $b^{t}$ 개의 점이 들어가도록 설계된 점 집합이고, 품질 지표 $t$ 는 작을수록 좋다( $t=0$ 이 이상적). 소볼 수열의 차원별 $t$ 값이 커지는 것이 고차원에서 성능이 떨어지는 이유이며, 조이·쿠오의 방향수 표 같은 것들이 이 $t$ 를 낮추려는 노력의 산물이다.
격자 규칙. 위와 결이 다른 계열로, 생성벡터 $\mathbf{z}$ 에 대해 $\mathbf{x}_i = \{ i\mathbf{z}/N \}$ (소수부)으로 정의되는 랭크 1 격자. 주기 매끄러운 함수에 대해서는 $O(N^{-\alpha})$ 같은 고차 수렴이 가능하며, 좋은 $\mathbf{z}$ 를 좌표별로 탐욕적으로 찾는 CBC 구성(component-by-component)이 표준이다. 고속 CBC는 $O(sN\log N)$ 에 끝난다.

수렴률 비교에서 함정은 $(\log N)^s$ 다. $s = 30$ 이면 이 인자가 $N$ 을 이기는 지점이 천문학적으로 커서, 점근적으로는 QMC가 MC보다 나쁘다고 결론 내릴 수도 있다. 그런데 실측은 정반대다. 이 모순을 설명하는 것이 다음 절이다.

4. 유효차원 — 고차원에서도 되는 이유[편집]

1995년 파스코프와 트라우브가 360차원 모기지 담보증권(CMO) 가격 계산에서 QMC가 MC보다 확연히 빠르게 수렴한다고 보고했을 때, 이론가들의 첫 반응은 “그럴 리 없다”였다. $(\log N)^{360}$ 이 어떤 우주적 $N$ 에서도 작아질 리 없기 때문이다.

해답은 유효차원(effective dimension)이었다. 함수를 ANOVA 분해

f(\mathbf{x}) = \sum_{u \subseteq \{1,\dots,s\}} f_u(\mathbf{x}_u), \qquad \sigma^2(f) = \sum_{u \neq \emptyset} \sigma_u^2

로 쪼개면, 분산이 어느 부분집합에 몰려 있는지를 볼 수 있다. 여기서 두 가지 유효차원을 정의한다.

절단 유효차원 $d_T$ — 처음 $d_T$ 개 좌표만으로 전체 분산의 99%가 설명되는 최소 $d_T$ .
중첩 유효차원 $d_S$ — 크기 $d_S$ 이하의 상호작용 항들만으로 분산의 99%가 설명되는 최소 $d_S$ .

명목 차원이 360이어도 $d_S$ 가 2~3이면, QMC는 사실상 저차원 문제를 풀고 있는 셈이다. 저불일치 수열의 저차원 사영이 좋다는 성질(소볼의 property A/A′ 같은 조건)이 여기서 결정적으로 작용한다. 게다가 금융에서 브라운 운동 경로를 만들 때 브라운 다리(Brownian bridge)나 주성분 분석 기반 구성으로 좌표 순서를 바꾸면, 분산을 앞쪽 몇 개 좌표에 몰아넣어 $d_T$ 를 인위적으로 낮출 수 있다. 같은 적분을 같은 점열로 푸는데 좌표 배치만 바꿔 수렴이 자릿수로 개선되는 현상이 실제로 일어난다.

이론적 뒷받침은 슬론과 보즈니아코프스키(1998)의 가중 공간(weighted space) 이론이다. 좌표 $j$ 의 중요도를 가중치 $\gamma_j$ 로 두고 $\sum_j \gamma_j < \infty$ 같은 조건을 걸면, 오차 상한에서 차원 의존성이 사라진다(다루기 쉬움, tractability). CBC 구성은 이 가중치를 입력으로 받아 그 공간에 최적화된 격자를 만들어 낸다.

5. 무작위화 QMC[편집]

결정론적 QMC의 진짜 아픈 곳은 수렴률이 아니라 오차 추정이 없다는 것이다. MC는 표본분산 하나로 신뢰구간을 주는데, QMC는 점열이 고정이라 “이 답이 얼마나 맞는지”를 말할 방법이 없다. 코크스마-흘라브카는 위에서 봤듯 실용성이 없다. 이 문제를 해결하는 것이 무작위화 QMC(RQMC)다.

핵심 요구조건은 두 가지다. (1) 무작위화된 각 점이 개별적으로는 $[0,1]^s$ 에 균일분포할 것 → 추정량이 불편(unbiased)이 된다. (2) 무작위화 후에도 점 집합 전체의 저불일치 구조가 유지될 것.

무작위 이동(Cranley-Patterson). 격자 규칙에 균일 난수 벡터 $\mathbf{u}$ 를 더하고 소수부를 취한다. 격자는 이동해도 격자다.
디지털 이동. 디지털 네트의 각 좌표 비트열에 난수 비트열을 XOR한다. 네트 구조가 보존된다.
오언 스크램블링(Owen, 1995). 각 좌표의 $b$ 진 자릿수를 재귀적·중첩적으로 무작위 치환한다. 가장 강력한 무작위화로, $(t,m,s)$ -네트 성질을 확률 1로 보존하면서 불편성을 준다. 매끄러운 $f$ 에 대해 분산이 $O(N^{-3}(\log N)^{s-1})$ , 즉 RMSE가 거의 $O(N^{-3/2})$ 로 떨어진다 — MC의 $N^{-1/2}$ 대비 세 배 빠른 지수다.

실무 절차는 간단하다. 서로 독립인 무작위화를 $R$ 개(보통 10~30) 만들고, 각각으로 QMC 추정값 $\hat I_1,\dots,\hat I_R$ 을 구한 뒤 이들의 표본평균과 표본분산으로 신뢰구간을 만든다. 총 표본 수는 $RN$ 이지만 얻는 것은 불편 추정 + 정직한 오차 막대 + QMC의 수렴률이다. 오늘날 “QMC를 쓴다”는 말은 사실상 RQMC를 쓴다는 뜻이다.

한계도 알아 둬야 한다. 적분함수에 축에 나란하지 않은 불연속이 있으면(디지털 옵션의 페이오프, 렌더링의 가시성 경계 등) 변동이 무한이 되어 이론 보증이 무너지고 실측 수렴률도 $N^{-1/2}$ 쪽으로 되돌아간다. 이때는 조건부 기대값으로 매끄럽게 만들기, 중요도 표본추출과의 결합, 문제가 되는 좌표만 무작위로 두는 패딩 같은 처방이 쓰인다. 응용은 금융 파생상품 가격, 불확실성 정량화와 민감도 해석, 물리 기반 렌더링의 경로 표본추출, 중성자 수송까지 폭넓다.²³

6. 관련 문서[편집]

“준(quasi)“이라는 접두사가 붙은 이유는 무작위성을 흉내만 낼 뿐 실제로는 결정론적이기 때문이다. 그래서 “난수 생성기 시드를 뭘로 하셨어요?”라는 질문에 “시드가 없는데요”라고 답하는 재미있는 상황이 생긴다. ↩
소볼 수열의 소볼과 소볼 지수의 소볼은 같은 사람(Ilya M. Sobol’)이다. 저불일치 수열도 만들고 전역 민감도 지표도 만들었으니, 이 바닥에서 이름이 두 번 나오는 몇 안 되는 인물이다. 참고로 두 업적을 잇는 공통 언어가 이 문서에도 나온 ANOVA 분해다. ↩
렌더러 개발자들이 “소볼 샘플러”를 켜고 노이즈가 줄어드는 걸 보며 감탄할 때, 실제로 일어나는 일은 4차원 사영(픽셀 2 + 렌즈 2)에서의 층화 개선인 경우가 많다. 경로 깊이가 깊어질수록 뒤쪽 차원의 품질은 급격히 떨어지므로, 실전 렌더러는 대개 앞 몇 차원만 QMC로 쓰고 나머지는 스크램블 난수로 패딩한다. ↩