희소 격자

1. 개요[편집]

희소 격자(sparse grid)는 완전 텐서곱 격자에서 “모든 방향이 동시에 고해상도인” 점들을 솎아 내고, 정확도에 실제로 기여하는 점만 남긴 격자다. 다차원 적분·보간의 비용을 차원 $d$ 의 지수에서 거의 1차원 수준으로 끌어내리는 대신, 함수가 혼합 편미분이 유계일 만큼 매끄러울 것을 요구한다. 공짜 점심은 없고, 이 경우 값은 매끄러움으로 치른다.

이론적 뼈대는 소련 수학자 스몰략(S. A. Smolyak)이 1963년에 제시한 조합 공식이다.¹ 오늘날 불확실성 정량화에서 확률적 콜로케이션의 표준 표본 설계이며, 다항식 카오스 전개의 비침입형 계수를 구할 때 “가우스 구적의 텐서곱은 즉사하므로 희소격자를 쓴다”고 할 때의 바로 그것이다.

2. 텐서곱은 왜 즉사하는가[편집]

1차원 구적점이 $m$ 개인 규칙을 $d$ 차원으로 텐서곱하면 점이 $m^d$ 개다. 1차원 정확도가 $O(m^{-r})$ 라면 전체 점 수 $N = m^d$ 로 다시 쓴 정확도는 $O(N^{-r/d})$ — 차원이 올라갈수록 수렴 지수가 $d$ 로 나눠진다. 이것이 차원의 저주가 수치적분에 나타나는 얼굴이다. 그래서 $d$ 가 대여섯을 넘으면 사람들은 정확도 차수를 포기하고 차원에 무관한 $O(N^{-1/2})$ 의 몬테카를로 방법으로 갈아탄다.

희소 격자는 그 중간을 노린다. 매끄러운 함수라면 고차 정확도를 거의 유지하면서 점 수를 로그 인자만 남기고 줄일 수 있다는 것이 요지다.

3. 스몰략 조합 공식[편집]

1차원 연산자(구적 또는 보간) 계열 $U^1, U^2, \dots$ 을 준비하고 차분 연산자를 정의한다.

$$\Delta^{i} = U^{i} - U^{i-1}, \qquad U^{0} = 0$$

레벨 $n$ 의 완전 텐서곱은 $\|\mathbf{i}\|_\infty \le n$ 인 다중지표 전부, 즉 정육면체 모양의 지표 집합에 대해 $\Delta^{i_1} \otimes \cdots \otimes \Delta^{i_d}$ 를 더한 것이다. 스몰략 구성은 그 정육면체를 합이 작은 삼각형 모양으로 갈아 끼운다.

$$A(q,d) \;=\; \sum_{|\mathbf{i}|_1 \le q + d - 1} \Delta^{i_1} \otimes \cdots \otimes \Delta^{i_d}$$

이걸 원래 연산자로 되돌려 쓰면 부호가 번갈아 나오는 그 유명한 조합 형태가 된다.

$$A(q,d) = \sum_{q \le |\mathbf{i}|_1 \le q+d-1} (-1)^{\,q+d-1-|\mathbf{i}|_1}\binom{d-1}{\,q+d-1-|\mathbf{i}|_1\,}\; \big(U^{i_1} \otimes \cdots \otimes U^{i_d}\big)$$

읽는 법은 간단하다. “한 방향만 아주 곱게, 나머지는 거칠게” 짠 격자들을 여러 장 겹쳐 놓고, 중복해서 센 부분을 음의 계수로 빼는 것이다. 그리벨 등이 정리한 조합 기법(combination technique)이 정확히 이 해석이며, 각 항이 서로 독립인 값싼 텐서곱 문제라 병렬화가 자연스럽다는 실용적 장점도 여기서 나온다.

4. 계층적 기저와 잉여[편집]

같은 이야기를 보간 쪽에서 보면 훨씬 직관적이다. 1차원 구간을 이등분해 가며 계층적 기저(hierarchical basis)를 세우면, 레벨 $l$ 의 각 점에 붙는 계수는 함수값이 아니라 그 점에서 한 단계 거친 보간이 얼마나 틀렸는가, 즉 잉여(hierarchical surplus)가 된다. 조각선형 기저에서

$$\alpha_{l,i} = u(x_{l,i}) - \tfrac{1}{2}\big[u(x_{l,i}-h_l) + u(x_{l,i}+h_l)\big] = -\tfrac{h_l^2}{2}\,u''(\xi)$$

잉여는 $h_l^2$ 로 줄어들고, $d$ 차원에서는 각 방향으로 한 번씩 2차 차분을 때린 값이 되어 $\prod_{k=1}^{d} h_{l_k}^2$ 에 혼합 편도함수 $\partial^{2d} u / \partial x_1^2 \cdots \partial x_d^2$ 를 곱한 크기로 유계가 된다. 그래서 희소 격자의 전제조건이 “모든 방향으로 2계까지 섞어 미분한 것이 유계”($u \in H^2_{\text{mix}}$)인 것이다. 이 조건이 깨지면 솎아 낸 점들이 실제로 중요한 점이었다는 뜻이고, 희소 격자는 그대로 무너진다.

5. 얼마나 이기는가[편집]

메시 폭 $h_n = 2^{-n}$ 기준으로 정리하면 다음과 같다.

항목	완전 텐서곱	희소 격자
점 개수	$O(h_n^{-d})$	$O(h_n^{-1}(\log h_n^{-1})^{d-1})$
$L_2$ 보간 오차	$O(h_n^2)$	$O(h_n^2 (\log h_n^{-1})^{d-1})$

점 수는 $d$ 제곱에서 로그 거듭제곱으로 내려가고, 오차는 로그 인자만큼만 손해 본다. 클렌쇼-커티스 노드를 쓴 실제 점 개수를 보면 체감이 확실하다.

차원 $d$	레벨	완전 텐서곱	희소 격자
5	5	1,419,857	801
10	5	약 $2.0\times10^{12}$	8,801
20	4	약 $1.2\times10^{19}$	11,561

10차원에서 2조 개가 8,801개가 되는 장면이 희소 격자의 세일즈 포인트 전부다. 다만 표의 $(\log h^{-1})^{d-1}$ 은 차원에 대해 여전히 지수적이라는 점을 놓치면 안 된다. 희소 격자는 차원의 저주를 깨는 게 아니라 미루는 도구다. 차원이 수십을 넘어가면 상수가 다시 사람을 잡는다.

6. 중첩 노드가 왜 중요한가[편집]

조합 공식은 $\Delta^i = U^i - U^{i-1}$ 를 쓰므로, 레벨 $i$ 의 점집합이 레벨 $i-1$ 을 포함하면($U^{i-1}$ 의 점을 재사용할 수 있으면) 새로 평가할 함수값이 확 줄어든다. 이 성질을 중첩성(nestedness)이라 한다.

• 클렌쇼-커티스: 레벨 $i$ 에서 $2^{i-1}+1$ 개의 체비쇼프 극점을 쓰면 완벽히 중첩된다. 희소 격자의 기본값이 된 이유.
• 가우스-르장드르: 1차원 효율(점 $m$ 개로 차수 $2m-1$ 정확)은 최고지만 중첩되지 않아 레벨을 올릴 때마다 전부 새로 계산한다. 희소 격자에서는 이 손해가 1차원 이득을 잡아먹는 경우가 많다.
• 가우스-패터슨: 중첩성을 갖도록 점을 덧붙여 가는 절충안. 중간 차원에서 자주 이긴다.
• 가우스-에르미트/라게르: 입력이 정규·감마 분포일 때 필요하며, 중첩판을 따로 만들어 쓴다.

주의할 것 하나. 스몰략 구적은 조합 공식의 음수 계수 때문에 가중치가 음수가 될 수 있다. 양수 가중치가 주는 안정성(피적분함수 오차가 상쇄 없이 유계)이 사라지므로, 피적분함수가 거칠면 상쇄에 의한 정밀도 손실이 실제로 관측된다.²

7. 적응형 희소 격자[편집]

균등한 스몰략 격자는 “모든 차원이 똑같이 중요하다”고 가정한다. 현실의 모형은 대개 그렇지 않아서, 적응 전략이 두 갈래로 발전했다.

• 차원 적응형(dimension-adaptive). 게르스트너와 그리벨의 방식으로, 다중지표 $\mathbf{i}$ 를 하나씩 활성화하며 그때 얻은 $\Delta$ 항의 크기를 이득으로 보고 탐욕적으로 다음 지표를 고른다. 유효 차원이 낮은 문제(=소볼 지수가 몇 개 변수에 몰려 있는 문제)에서 압도적이다. 결과적으로 각 방향에 다른 해상도를 배정하며, 이는 각 변수에 가중치를 준 이방성 격자를 자동으로 찾아내는 것과 같다.
• 국소 적응형(locally adaptive). 잉여 $|\alpha_{l,i}|$ 가 문턱보다 큰 점에서만 자식 점을 낳는다. 잉여가 곧 국소 오차 지시자이므로 적응 격자 세분과 논리가 같다. 불연속이나 급격한 전이가 있는 응답면(예: 좌굴·상전이·수치 발산 경계)에 필수적이며, 이때는 조각선형 기저를 쓰는 편이 다항식 기저보다 안전하다.

8. 확률적 콜로케이션에서의 자리[편집]

입력 확률변수 $\boldsymbol{\xi}$ 를 받는 대리 모델을 세울 때, 희소 격자는 두 방식으로 쓰인다.

• 콜로케이션(보간): 희소 격자 점마다 솔버를 한 번 돌리고, 그 점들을 지나는 희소 격자 보간자를 응답면으로 삼는다. 솔버를 블랙박스로 두므로 상용 코드에도 붙는다. 통계량은 보간자 위에서 값싸게 뽑는다.
• 의사 스펙트럴 사영: 같은 점들을 구적점으로 써서 다항식 카오스 전개의 계수 $\mathbb{E}[Y\Psi_{\boldsymbol\alpha}]$ 를 적분한다. 이쪽은 계수만 나오면 평균·분산·소볼 지수가 딸려 나온다는 PCE의 장점을 그대로 승계한다.

둘의 관계는 “같은 점, 다른 후처리”에 가깝다. 다만 사영 쪽은 구적 정확도를 넘는 차수를 요구하면 에일리어싱(내부 상쇄 오류)이 생기므로, 격자 레벨과 절단 차수를 짝지어 올려야 한다.

경쟁 상대와의 자리 정리는 대략 이렇다. 저차원($d \lesssim 10$)에 매끄러운 응답 → 희소 격자, 중간 차원에 매끄러움이 의심스러움 → 준몬테카를로나 희소 회귀 PCE, 고차원이거나 응답이 거칢 → 몬테카를로 방법·라틴 하이퍼큐브 표본추출. 희소 격자를 매끄럽지 않은 데 쓰면 몬테카를로보다 못한 답이 나오는데, 게다가 오차 추정치가 없어서 얼마나 못한지도 모른다는 게 더 무섭다.

9. 한계[편집]

• 매끄러움 의존이 전부다. $H^2_{\text{mix}}$ 가정이 깨지면 이론적 우위가 통째로 사라진다. 응답면이 불연속이면 국소 적응이나 영역 분할이 필수.
• 점 수가 레벨 단위로 뛴다. 레벨을 하나 올리면 점이 몇 배로 늘어, “예산에 딱 맞춰 500점”같은 요구를 맞추기 어렵다. 차원 적응형이 이 문제를 상당 부분 해결한다.
• 정의역 밖의 노드. 정규분포처럼 무한 정의역이면 고레벨 노드가 꼬리 깊숙이 찍혀 솔버가 물리적으로 말이 안 되는 입력(음의 밀도, 음의 두께)을 받는다. 사전에 절단하거나 변환을 손봐야 한다.
• 경계 점의 과다. 클렌쇼-커티스는 경계를 포함하는데, $d$ 가 크면 격자 점의 대부분이 경계와 그 근처에 몰린다. 경계를 뺀 변형 기저를 쓰는 구현이 많은 이유다.

구현은 SG++, TASMANIAN, Dakota, UQLab 등이 있고, 대부분 클렌쇼-커티스 기본값에 차원 적응 옵션을 제공한다.³

10. 관련 문서[편집]

• 수치적분 · 직교 배치법 · 직교다항식
• 불확실성 정량화 · 다항식 카오스 전개 · 소볼 지수
• 몬테카를로 방법 · 준몬테카를로 · 라틴 하이퍼큐브 표본추출 · 소볼 수열
• 대리 모델 · 적응 격자 · 클렌쇼-커티스 구적법

11. Footnotes[편집]

1. 러시아어 이름 Смоляк 의 표기가 문헌마다 스몰략·스몰랴크·스무략으로 갈린다. 영어 논문에서 “Smolyak quadrature”만 보고 살면 평생 문제없지만, 한국어로 발표 자료를 만드는 순간 표기 싸움이 시작된다. 정작 본인은 경제학 쪽에서 더 많이 인용된다는 게 함정. ↩

2. 그래서 “적분값이 물리적으로 불가능한 음수가 나왔다”는 신고가 심심찮게 들어온다. 확률밀도의 적분이 음수로 나오면 격자를 의심하기 전에 가중치 부호부터 확인하는 게 빠르다. 양수 가중치를 보장하려면 정확도 차수를 좀 포기하고 설계된 규칙을 써야 한다. ↩

3. 실무에서 가장 흔한 사고는 “점 8,801개면 되겠네” 하고 각 점마다 3시간짜리 전산유체역학 해석을 걸어 버리는 것이다. 격자 점 수를 줄이는 데 성공했다고 총 비용이 감당 가능해지는 건 아니다. 차원 적응을 먼저 돌려 유효 차원을 확인하고, 그다음에 예산을 짜는 순서가 안전하다. ↩