교차 엔트로피 방법

1. 개요[편집]

교차 엔트로피 방법(cross-entropy method, CEM)은 표본을 뽑고, 성적이 좋은 상위 몇 %(엘리트)만 남기고, 그 엘리트를 가장 잘 설명하는 방향으로 표본분포의 파라미터를 갱신하는 과정을 반복하는 알고리즘이다. 갱신의 기준이 엘리트 분포와 파라메트릭 분포족 사이의 교차 엔트로피(동등하게 쿨백-라이블러 발산) 최소화라서 이 이름이 붙었다.

출발점은 최적화가 아니라 희귀사건 확률 추정이었다. 루빈스타인(Rubinstein)이 1997년 통신망의 버퍼 넘침 확률을 구하려고 중요도 표본추출의 제안분포를 분산 최소화로 자동 조율하는 방법을 냈고, 1999년에 그 기준을 교차 엔트로피로 갈아 끼우면서 지금 형태가 됐다. 그리고 곧 “희귀사건을 잘 뽑는 분포를 찾는 절차는, 사실 좋은 해를 잘 뽑는 분포를 찾는 절차와 같다”는 것이 드러나면서 최적화 알고리즘으로 팔자가 바뀌었다.¹

2. 희귀사건 — 직접 몬테카를로가 망하는 지점[편집]

성능함수 $S(\mathbf{x})$ 와 임계값 $\gamma$ 에 대해 다음 확률을 구한다고 하자.

$$\ell = \mathbb{P}_{f}\big(S(\mathbf{X}) \ge \gamma\big) = \mathbb{E}_{f}\big[\mathbb{1}\{S(\mathbf{X}) \ge \gamma\}\big]$$

몬테카를로 방법으로 그냥 $N$ 개 뽑아 세면 추정량의 상대오차가 $\sqrt{(1-\ell)/(N\ell)}$ 이다. 상대오차 10%를 원하면 $N \approx 100/\ell$ 이 필요하고, $\ell = 10^{-6}$ 이면 1억 번 돌려야 한다는 뜻이다. 신뢰성 해석에서 파손확률이 $10^{-6}$ 급이라는 걸 생각하면 이건 그냥 못 하는 것이다.

처방은 중요도 표본추출이다. 다른 밀도 $g$ 에서 뽑고 우도비로 보정한다.

$$\ell = \mathbb{E}_{g}\!\left[\mathbb{1}\{S(\mathbf{X}) \ge \gamma\}\, \frac{f(\mathbf{X})}{g(\mathbf{X})}\right]$$

이론적으로 분산이 정확히 0이 되는 최적 밀도는 $g^*(\mathbf{x}) \propto \mathbb{1}\{S(\mathbf{x}) \ge \gamma\} f(\mathbf{x})$ 인데, 이걸 쓰려면 정규화 상수로 $\ell$ 이 필요하다. 답을 알아야 답을 구할 수 있다는 순환이라 그대로는 쓸모가 없다.

CE의 발상은 $g^*$ 를 다루기 쉬운 분포족 $\{f(\cdot\,;\mathbf{v})\}$ 안에서 가장 가깝게 흉내 내자는 것이다. 거리는 KL 발산으로 재고, $g^*$ 쪽 항은 $\mathbf{v}$ 와 무관하므로 최소화는 곧 교차 엔트로피 항의 최대화가 된다.

$$\mathbf{v}^* = \arg\max_{\mathbf{v}} \ \mathbb{E}_{\mathbf{u}}\!\left[\mathbb{1}\{S(\mathbf{X}) \ge \gamma\}\, W(\mathbf{X};\mathbf{u},\mathbf{w})\, \ln f(\mathbf{X};\mathbf{v})\right]$$

여기서 $W$ 는 우도비다. 형태를 보면 가중 최대우도 추정이다. “사건을 일으킨 표본들에 가중치를 달아 놓고, 그 표본을 가장 잘 설명하는 파라미터를 찾는다”는 것이 전부다.

3. 반복 CE — 엘리트 표본과 닫힌 형태 갱신[편집]

문제가 하나 남았다. $\gamma$ 가 희귀하면 처음 뽑은 $N$ 개 중 지시함수가 1인 표본이 0개라서 갱신식의 우변이 통째로 0이 된다. 그래서 CE는 임계값을 한 번에 올리지 않고 사다리를 놓는다.

1. 현재 파라미터 $\mathbf{v}_t$ 로 표본 $\mathbf{X}_1, \dots, \mathbf{X}_N$ 을 뽑는다.
2. 성능값 $S(\mathbf{X}_i)$ 를 정렬해 상위 $\rho$ 분위수를 임시 임계값 $\hat{\gamma}_t$ 로 잡는다. 보통 $\rho = 0.01 \sim 0.1$, 즉 상위 1~10%가 엘리트다.
3. 엘리트 표본에 대해서만 위 최대우도 문제를 풀어 $\mathbf{v}_{t+1}$ 을 얻는다.
4. $\hat{\gamma}_t$ 가 목표 $\gamma$ 에 도달할 때까지 반복.

여기서 CE가 대중화된 결정적 이유가 나온다. 분포족이 지수족이면 3단계가 닫힌 형태로 풀린다. 지수족 밀도를 충분통계량 $T(\mathbf{x})$ 로 쓰면 로그우도의 그래디언트가 $T(\mathbf{x}) - \mathbb{E}_{\mathbf{v}}[T]$ 꼴이라, 정류 조건이 곧 적률 맞추기가 된다.

$$\mathbb{E}_{\mathbf{v}_{t+1}}[T(\mathbf{X})] = \frac{\sum_{i \in \mathcal{E}} w_i\, T(\mathbf{X}_i)}{\sum_{i \in \mathcal{E}} w_i}$$

평균 파라미터화에서는 좌변이 그냥 파라미터이므로, 갱신식이 엘리트 표본의 가중평균이 된다. 구체적으로 보면 허무할 정도다.

분포족	갱신되는 파라미터	갱신식
베르누이	성공확률 $p_j$	엘리트에서 $j$ 번째 비트가 1인 비율
정규	평균 $\mu_j$, 분산 $\sigma_j^2$	엘리트의 표본평균, 표본분산
지수	율 $\lambda_j$	엘리트 표본평균의 역수
범주형	전이확률 $p_{jk}$	엘리트 경로에서 $j \to k$ 이동 빈도

미분도, 헤세 행렬도, 라인서치도 없다. 정렬하고 평균 내는 것이 알고리즘의 전부다.²

4. 최적화 알고리즘으로의 변신[편집]

$\max_{\mathbf{x}} S(\mathbf{x})$ 라는 결정론적 최적화 문제도 같은 틀에 밀어 넣을 수 있다. $\gamma$ 를 최댓값 근처로 잡은 희귀사건 문제 $\mathbb{P}(S(\mathbf{X}) \ge \gamma)$ 를 연관 확률문제로 두면, 이 확률을 잘 추정하는 분포는 곧 좋은 해 근처에 질량을 몰아둔 분포이기 때문이다.

실제 구현은 더 간단해진다. 참조분포를 매 반복 $\mathbf{v}_t$ 로 갱신해 버리면 우도비 $W$ 가 1이 되어 사라진다. 남는 것은 뽑고 → 정렬하고 → 엘리트 평균으로 갱신의 세 줄이다. 연속 최적화에서 대각 정규분포를 쓰면

$$\mu_j^{(t+1)} = \frac{1}{|\mathcal{E}|}\sum_{i \in \mathcal{E}} X_{ij}, \qquad \big(\sigma_j^{(t+1)}\big)^2 = \frac{1}{|\mathcal{E}|}\sum_{i \in \mathcal{E}} \big(X_{ij} - \mu_j^{(t+1)}\big)^2$$

가 전부고, 분산이 0으로 수축하면 종료다. 목적함수가 미분 불가능하든, 불연속이든, 잡음이 섞였든 상관하지 않는다는 점에서 유전 알고리즘이나 입자 군집 최적화와 같은 무미분 최적화 계열이지만, “개체군”이 아니라 분포를 상태로 들고 다닌다는 점이 다르다. 조합 문제에서도 마찬가지다. 외판원 문제면 도시 전이확률 행렬을, 배낭 문제면 아이템별 포함확률 벡터를 파라미터로 두면 그만이다.

5. 조기 수렴과 처방[편집]

가장 흔한 실패 모드는 분산이 너무 빨리 죽는 것이다. 초반 엘리트가 우연히 한 골짜기에 몰리면 $\sigma$ 가 그 근처로 수축하고, 그 뒤로는 그 골짜기 밖 표본이 아예 안 나와 지역 최적해에 굳는다. 표준 처방은 셋이다.

• 평활화(smoothing). 갱신을 그대로 받지 않고 섞는다. $\mathbf{v}_{t+1} = \alpha \hat{\mathbf{v}}_{t+1} + (1-\alpha)\mathbf{v}_t$, 보통 $\alpha = 0.7 \sim 0.9$. 분산에는 더 강한 평활을 따로 걸거나, 반복이 진행되며 감쇠하는 동적 평활 $\beta_t = \beta - \beta(1 - 1/t)^q$ 를 쓴다. 코스타 등(2007)의 수렴 해석이 다루는 것이 이 감쇠형 평활이다.
• 분산 주입. 매 반복 $\sigma^2 \leftarrow \sigma^2 + \varepsilon_t$ 로 바닥을 깔아준다. 담금질 모사의 온도를 완전히 0으로 내리지 않는 것과 같은 취지다.
• 엘리트 수 하한과 재시작. $\rho N$ 이 너무 작으면 표본분산 추정 자체가 요동친다. 엘리트 개수를 최소 10~20개로 보장하고, 수축이 끝나면 넓은 분산으로 재시작해 여러 번 돌린다.

이론적 보장은 정직하게 말해 약하다. 적절한 평활 조건 아래 파라미터열이 확률 1로 퇴화 분포에 수렴한다는 결과는 있지만, 그 극한이 전역 최적해라는 것은 추가 가정 없이는 보장되지 않는다. CEM은 이론이 강해서가 아니라 구현이 30줄이고 병렬화가 자명해서 살아남은 알고리즘이다.

6. 사촌들 — CMA-ES, 담금질 IS, MPPI[편집]

• CMA-ES. 순위 기반 엘리트로 가우시안을 갱신한다는 뼈대가 같다. 차이는 CMA-ES가 (a) 전체 공분산 행렬을 학습해 좌표 회전에 불변하고, (b) 진화 경로를 누적해 스텝 크기를 따로 제어하며, (c) 가중 재조합을 쓴다는 것. CEM의 대각 정규 갱신은 경로 누적과 스텝 제어를 뺀 특수한 경우로 읽을 수 있다. 두 알고리즘 모두 정보기하 관점에서는 기대 성능에 대한 자연 그래디언트 상승의 한 사례로 통합된다.
• 담금질 중요도 표본추출·부분집합 시뮬레이션. 중간 임계값 사다리 $\gamma_1 < \gamma_2 < \cdots < \gamma$ 를 놓고 조금씩 분포를 기울인다는 발상이 똑같다. 다만 부분집합 시뮬레이션은 각 층에서 파라메트릭 분포를 적합하는 대신 마르코프 연쇄 몬테카를로로 조건부 표본을 뽑는다. 고차원에서 파라메트릭 제안분포가 무너질 때(우도비 분산 폭발) 그쪽이 강한 이유다.
• MPPI(모델 예측 경로적분 제어). 최적 제어의 경로적분 이론에서 최적 제어 분포가 $\exp(-S/\lambda)$ 로 기울어진 분포임을 유도한 뒤, 제어열 표본들을 그 지수 가중으로 평균 내 갱신한다. 구조를 나란히 놓으면 CEM과 하드 컷오프 대 소프트맥스 가중의 차이뿐이다. 실제로 모델 예측 제어의 비선형·비볼록 버전에서는 CEM-MPC와 MPPI가 같은 자리를 놓고 경쟁하고, 모델 기반 강화 학습의 계획 단계도 대개 이 둘 중 하나다.³

응용 스펙트럼도 넓다. 통신망 버퍼 넘침과 보험 파산확률 같은 고전적 희귀사건, 대리 모델과 결합한 구조 신뢰성 해석, 조합 최적화, 그리고 로봇 제어의 온라인 계획까지. 공통점은 목적함수를 블랙박스로만 볼 수 있고 표본 하나가 비싸지 않은 상황이라는 것이다. 반대로 표본 하나가 CFD 해석 한 판인 상황에서는 표본 효율이 훨씬 높은 베이지안 최적화 쪽이 맞다.⁴

7. 관련 문서[편집]

• 중요도 표본추출 · 몬테카를로 방법
• 신뢰성 해석 · 부분집합 시뮬레이션 · 극값 통계
• 담금질 모사 · 유전 알고리즘 · 입자 군집 최적화
• 모델 예측 제어 · 최적 제어 · 강화 학습
• 베이지안 최적화 · 대리 모델
• 조합 최적화 · 외판원 문제 · 배낭 문제
• 기댓값 최대화 알고리즘 · 변분 추론
• CMA-ES · 쿨백-라이블러 발산

8. Footnotes[편집]

1. 희귀사건 추정용으로 만든 도구가 최적화 알고리즘이 되는 전개는 생각보다 자연스럽다. “확률이 $10^{-9}$ 인 사건을 잘 뽑아라”와 “10억 개 중 제일 좋은 걸 찾아라”는 결국 같은 요구다. 다만 논문 제목이 바뀌면서 인용 수가 한 자릿수 늘어난 건 별개의 현상이다. ↩

2. 처음 구현해 보면 “이게 되네?” 소리가 나온다. 그래디언트도 없고 하이퍼파라미터도 $N$, $\rho$, $\alpha$ 셋뿐인데 로젠브록 함수가 풀린다. 대신 차원이 수백 이상으로 가면 표본 수 요구가 급격히 늘어 순식간에 못 쓰게 되므로, 첫인상을 너무 믿지 않는 것도 중요하다. ↩

3. 유도 경로는 완전히 다른데(한쪽은 KL 최소화, 다른 쪽은 확률적 HJB의 선형화) 코드가 거의 같아지는 대표적 사례다. 실무자 입장에서 진짜 차이는 “상위 $k$개만 쓸까, 전부 가중해서 쓸까”와 온도 $\lambda$ 를 어떻게 잡을까 정도로 좁혀진다. ↩

4. “무미분이라 아무 데나 된다”는 말은 “함수 평가가 싸다면”이라는 조건이 생략된 것이다. 해석 한 번에 6시간 걸리는 문제에 표본 500개짜리 CEM을 20세대 돌리겠다는 계획서는 대략 7년짜리 프로젝트다. ↩