헤지 알고리즘

최적설계 통계 수치해석 마지막 수정: 2026-08-16 04:47:19

1. 개요[편집]

헤지 알고리즘 Hedge Algorithm
제안	Freund & Schapire (1997) — 부스팅과 같은 논문
선행 연구	Littlestone & Warmuth, 가중 다수결 (1994)
갱신식	$w_i \leftarrow w_i \exp(-\eta\,\ell_i)$ 후 정규화
후회 상한	$R_T \le \sqrt{T\ln N/2}$ ($\eta=\sqrt{8\ln N/T}$)
증명 도구	퍼텐셜 $\Phi_t = \ln\sum_i w_{t,i}$ + 회프딩 보조정리
다른 이름	지수 가중 · 곱셈 가중치 갱신(MWU)
밴딧 확장	EXP3 — $O(\sqrt{TN\log N})$

헤지 알고리즘(Hedge)은 $N$ 개의 후보(전문가)에 확률 가중치를 두고, 매 라운드 각 후보가 낸 손실만큼 그 가중치를 지수적으로 깎아 나가는 온라인 학습 알고리즘이다. 갱신식은 한 줄뿐이다.

w_{t+1,i} \;=\; w_{t,i}\,\exp\bigl(-\eta\,\ell_{t,i}\bigr), \qquad p_{t,i} \;=\; \frac{w_{t,i}}{\sum_{j} w_{t,j}}

$\eta > 0$ 은 학습률, $\ell_{t,i} \in [0,1]$ 은 라운드 $t$ 에 후보 $i$ 가 낸 손실이며, 학습자는 $p_t$ 에 따라 후보를 뽑거나 그 가중 평균을 쓴다. 프로인트와 샤파이어가 1997년 논문에서 제시했고, 같은 논문의 후반부가 AdaBoost다. 즉 온라인 학습의 지수 가중과 부스팅은 태생부터 한 몸이다.¹

이 알고리즘이 유명한 이유는 성능 보장의 형태다. 상대가 학습자의 알고리즘을 다 알고 최악의 손실을 골라도, 사후 최선의 고정 후보 대비 누적 손실 초과분(후회)이

R_T \;\le\; \sqrt{\tfrac{1}{2}\,T\ln N}

으로 묶인다. 후보 수에 로그로만 의존한다. 라운드당 평균으로는 $O(\sqrt{\ln N / T})$ 이므로 후보를 백만 개 넣어도 손해가 $\sqrt{\ln 10^6}\approx 3.7$ 배에 그친다. 이 문서는 알고리즘의 증명·변형·응용을 다룬다. 후회라는 척도의 정의와 온라인 볼록 최적화 전반의 틀은 온라인 볼록 최적화, 이 갱신이 왜 심플렉스 위의 자연스러운 기하인지는 미러 하강에 있으므로 여기서 반복하지 않는다.

2. 가중 다수결에서 헤지까지[편집]

계보의 출발점은 리틀스톤과 워머스의 가중 다수결(weighted majority, 1994)이다. 이진 예측 문제에서 각 전문가에 가중치를 주고 다수결로 예측하되, 틀린 전문가의 가중치에 $\beta < 1$ 을 곱해 깎는다. 보장은 실수 횟수 형태로 나온다 — 학습자의 총 실수는 **최선 전문가의 실수 횟수의 상수배 + $O(\log N)$ **을 넘지 않는다. 상수배가 붙는다는 점이 아쉬운데, 결정적(deterministic) 다수결이라면 이 상수를 없앨 수 없다는 하한도 함께 알려져 있다.

헤지는 두 가지를 바꿔 이 상수를 걷어낸다.

무작위화. 다수결로 하나를 정하지 않고 $p_t$ 에서 뽑는다(또는 손실이 선형이면 그냥 가중 평균한다). 기댓값으로 논증하면 결정적 알고리즘의 하한을 우회할 수 있다.
손실을 실수값으로. 0/1 실수 여부가 아니라 $[0,1]$ 범위의 손실을 그대로 지수에 넣는다. 덕분에 회귀·비용 등 임의의 유계 손실에 그대로 쓸 수 있다.

결과가 위의 $\sqrt{T\ln N/2}$ 이며, 이 차수는 하한과 상수까지 거의 맞아떨어진다. 즉 더 나은 알고리즘은 사실상 없다.

3. 퍼텐셜 함수 증명[편집]

증명이 짧고 재사용성이 높아서 온라인 학습 강의의 첫 번째 정리로 늘 등장한다. 퍼텐셜을

\Phi_t \;=\; \ln \sum_{i=1}^{N} w_{t,i}

로 두고 한 라운드의 변화를 본다. $w_1 = \mathbf{1}$ 로 시작하면 $\Phi_1 = \ln N$ 이다.

위에서 누른다. $w_{t+1,i} = w_{t,i}e^{-\eta \ell_{t,i}}$ 이므로

\Phi_{t+1} - \Phi_t = \ln \sum_i p_{t,i}\, e^{-\eta \ell_{t,i}} \;\le\; -\eta\,\langle p_t, \ell_t\rangle + \frac{\eta^2}{8}

마지막 부등호가 회프딩 보조정리다. 확률변수가 폭 1인 구간에 갇혀 있으면 로그 적률생성함수가 $s\mathbb E[X] + s^2/8$ 을 넘지 못한다는 사실이며, $\ell_{t,i}\in[0,1]$ 이라는 가정이 여기서 정확히 소비된다. $t=1,\dots,T$ 로 더하면

\Phi_{T+1} - \ln N \;\le\; -\eta\, L_{\text{alg}} + \frac{T\eta^2}{8}, \qquad L_{\text{alg}} = \sum_t \langle p_t,\ell_t\rangle

아래에서 받친다. 합은 항 하나보다 크므로, 최선 후보 $i^\star$ 에 대해

\Phi_{T+1} \;\ge\; \ln w_{T+1,i^\star} \;=\; -\eta\, L_{i^\star}

두 부등식을 합쳐 $\eta$ 로 나누면

L_{\text{alg}} - L_{i^\star} \;\le\; \frac{\ln N}{\eta} + \frac{\eta T}{8}

가 나온다. 우변을 $\eta$ 에 대해 최소화하면 $\eta^\star = \sqrt{8\ln N / T}$ 에서 $\sqrt{T\ln N / 2}$ 다.

이 증명이 가르쳐 주는 것은 $\eta$ 의 역할이 명시적인 교환관계라는 점이다. $\ln N/\eta$ 는 초기 무지의 대가이고 $\eta T/8$ 은 매 라운드 과잉 반응의 대가다. $\eta$ 를 키우면 최선 후보를 빨리 찾지만 잡음에 흔들리고, 줄이면 안정적이지만 굼뜨다. $\sqrt{T}$ 라는 숫자는 이 둘이 균형을 이루는 지점에서 나온다.

한계도 같이 읽어야 한다. $\eta^\star$ 가 $T$ 를 알아야 계산된다. 그리고 $\ell \in [0,1]$ 이 아니라 $[0,M]$ 이면 상한이 $M$ 배로 늘어나므로, 손실 정규화를 대충 하면 이론상의 우아함이 실무에서 그대로 날아간다.²

4. 학습률을 모를 때 — 두 배 트릭과 적응형[편집]

$T$ 를 미리 모르는 것이 보통이다. 두 가지 표준 처방이 있다.

두 배 트릭(doubling trick). $T = 1, 2, 4, 8, \dots$ 인 구간으로 시간을 쪼개고, 각 구간을 그 길이에 맞춘 $\eta$ 로 완전히 새로 시작한다. 구간별 후회가 $\sqrt{2^k \ln N/2}$ 이므로 총합은 등비급수가 되어 $\sqrt{2}/(\sqrt2 - 1) \approx 3.41$ 배 안에 들어온다. 차수는 그대로 $O(\sqrt{T\ln N})$ . 무식하지만 어떤 온라인 알고리즘에도 그대로 얹을 수 있다는 것이 장점이다.

시간 가변 학습률. $\eta_t = \sqrt{8\ln N / t}$ 처럼 매 라운드 줄여 나가면 재시작 없이 대략 2배 상수로 같은 차수를 얻는다. 가중치를 버리지 않으므로 실전에서는 이쪽이 낫다.

데이터 적응형. 최악경우 상한은 실제 문제가 쉬울 때도 똑같이 보수적이다. 후보들의 손실이 거의 같다면 아무거나 골라도 손해가 없는데도 $\sqrt{T\ln N}$ 을 지불할 이유가 없다. AdaHedge 계열은 매 라운드의 실제 혼합 간극(mixability gap, 위 증명에서 $-\eta\langle p_t,\ell_t\rangle$ 와 실제 $\Phi$ 증가의 차이)을 누적해 $\eta$ 를 자동 조절한다. 문제가 쉬우면 후회가 상수로 떨어지고 어려우면 최악경우 상한으로 부드럽게 복귀한다. 튜닝 파라미터를 없앤다는 점에서 실무 채택률이 높다.

환경이 변할 때. 헤지의 비교 대상은 “고정된 후보 하나”다. 최선 후보가 중간에 바뀌는 상황에서는 이 벤치마크 자체가 나쁘다. 처방은 매 라운드 가중치의 일부 $\alpha$ 를 균등분포에 섞어 죽은 후보를 되살리는 fixed-share이며, 비교 대상을 “ $k$ 번 바뀌는 후보열”로 넓힌 이동 후회(shifting regret) 상한을 준다. 비정상 시계열에 지수 가중을 쓰겠다면 이 변형이 사실상 필수다.

5. 부스팅 — 같은 알고리즘의 쌍대 실행[편집]

프로인트-샤파이어 논문의 후반부가 왜 부스팅인지가 이 알고리즘의 가장 우아한 지점이다. 헤지를 역할을 뒤집어 돌리면 AdaBoost가 나온다.

헤지에서 학습자는 후보들에 대한 분포를 유지하고, 상대가 손실을 고른다.
부스팅에서 부스터는 훈련 표본들에 대한 분포 $D_t$ 를 유지하고, 약한 학습기가 그 분포에서 오차 $\varepsilon_t < \tfrac12$ 인 가설 $h_t$ 를 돌려준다.

즉 “전문가” 자리에 훈련 표본이 앉고, “손실” 자리에 그 표본을 맞혔는지 여부가 앉는다. 맞힌 표본의 가중치는 깎고 틀린 표본은 살려 두므로, 다음 라운드의 약한 학습기는 지금까지 어려웠던 표본에 집중하게 된다. 갱신은 그대로 곱셈 형태다.

D_{t+1}(i) \;\propto\; D_t(i)\exp\bigl(-\alpha_t\, y_i h_t(x_i)\bigr), \qquad \alpha_t = \frac{1}{2}\ln\frac{1-\varepsilon_t}{\varepsilon_t}

그리고 헤지의 퍼텐셜 논증을 그대로 돌리면 최종 가설 $H = \mathrm{sign}(\sum_t \alpha_t h_t)$ 의 훈련 오차가

\prod_{t} 2\sqrt{\varepsilon_t(1-\varepsilon_t)} \;=\;\prod_t \sqrt{1-4\gamma_t^2} \;\le\; \exp\Bigl(-2\sum_t \gamma_t^2\Bigr), \qquad \gamma_t = \tfrac12 - \varepsilon_t

로 지수적으로 감소한다. “동전 던지기보다 아주 조금만 나은 학습기를 모으면 임의로 정확한 분류기를 만들 수 있는가”라는 칸스-발리언트의 물음에 대한 답이 이렇게 나왔다. 헤지의 후회 상한과 AdaBoost의 오차 상한이 같은 세 줄 증명이라는 것이 핵심이다. 두 사람이 이후 정리한 대로, 부스팅과 온라인 학습은 하나의 영합 게임을 원 문제 쪽과 쌍대 쪽에서 각각 푸는 것으로 볼 수 있다. 자세한 알고리즘은 AdaBoost 참고. 지식 증류처럼 여러 모델을 하나로 합치는 다른 계열과는 목적함수부터 다르다는 점은 유의.

6. 곱셈 가중치 갱신이라는 메타 알고리즘[편집]

같은 갱신식이 학습이론·게임이론·근사알고리즘·양자정보에서 각각 독립적으로 발견됐고, 아로라-하잔-케일의 서베이가 이를 곱셈 가중치 갱신(MWU)이라는 하나의 메타 알고리즘으로 정리했다. 대표 사례만 꼽으면 다음과 같다.

영합 게임의 균형. 두 플레이어가 서로에게 무후회 알고리즘으로 대응하면 평균 전략쌍이 미니맥스 균형으로 수렴한다. $\varepsilon$ -균형까지 $O(\log N/\varepsilon^2)$ 라운드면 되고, 이는 폰 노이만 미니맥스 정리의 구성적 증명이 된다. 게임 이론과 쌍대성의 연결 고리.
선형계획 근사해. 덮개·채우기(covering/packing) 형태의 선형계획법 문제에서 제약을 “전문가”, 위반량을 “손실”로 두면 MWU가 $\varepsilon$ -실행가능해를 준다. 다중상품 흐름, 분수 네트워크 흐름 근사, 스케줄링 완화 문제의 고속 해법이 전부 이 틀이다.
반정부호 계획법. 가중치를 스칼라에서 행렬로 올린 행렬 지수 갱신 $W \leftarrow \exp(-\eta \sum_s A_s)$ 이 SDP의 원-쌍대 근사 해법을 만든다. 희소 절단(sparsest cut) 근사에서 내부점법보다 빠른 알고리즘이 여기서 나왔다.
근사 알고리즘 일반. 집합 덮개의 무작위 반올림, 하드코어 보조정리 같은 결과들이 같은 논법을 쓴다.

MWU를 쓸 때 반드시 확인해야 하는 양이 폭(width) $\rho$ — 손실을 $[0,1]$ 로 정규화하려면 원 문제의 값 범위를 $\rho$ 로 나눠야 하고, 그러면 반복 횟수가 $O(\rho^2\log N/\varepsilon^2)$ 로 $\rho$ 의 제곱에 비례해 폭발한다. 논문에서 “MWU로 다항시간에 풀린다”고 할 때 실전 성능을 결정하는 것은 거의 항상 이 폭이다. 폭을 줄이는 문제별 기교(제약 재정식화, 스케일링)가 사실상 이 계열 논문의 본론인 경우가 많다.³

7. 밴딧 확장 — EXP3[편집]

헤지는 매 라운드 모든 후보의 손실을 본다고 가정한다. 실제로는 고른 하나의 결과만 관측되는 경우가 많다. 이 설정이 다중 슬롯머신 문제이고, 표준 해법이 EXP3(Exponential-weight algorithm for Exploration and Exploitation)다.

발상은 중요도 가중 추정이다. 라운드 $t$ 에 $I_t \sim p_t$ 를 뽑아 손실 $\ell_{t,I_t}$ 만 관측했다면

\hat\ell_{t,i} \;=\; \frac{\ell_{t,i}}{p_{t,i}}\,\mathbf 1\{i = I_t\}

로 두면 $\mathbb E[\hat\ell_{t,i}] = \ell_{t,i}$ — 관측 못 한 후보에 0을 넣고 관측한 후보를 뽑힐 확률로 나눠 부풀리면 불편추정량이 된다. 이 $\hat\ell$ 을 헤지에 그대로 먹이고, 확률이 0에 붙어 추정값이 폭발하지 않도록 균등분포를 $\gamma$ 만큼 섞는다. 결과는

\mathbb E[R_T] \;=\; O\bigl(\sqrt{T N \log N}\bigr)

전체 정보 설정의 $\sqrt{T\log N}$ 에 비해 $\sqrt{N}$ 이 곱해진다. 후보 수에 로그가 아니라 제곱근으로 의존한다는 것이 정보 부족의 대가이며, 하한 $\Omega(\sqrt{TN})$ 이 알려져 있어 로그 인자를 제외하면 최적이다. 손실이 적대적이지 않고 고정 분포에서 나온다고 믿을 수 있으면 UCB나 톰슨 샘플링 쪽이 훨씬 나은 상수를 낸다 — 적대적 가정을 살 필요가 없으면 사지 않는 것이 이득이라는 점은 이 분야의 일반 원칙이다.

8. 실무에서[편집]

로그 영역에서 계산한다. $\exp(-\eta \ell)$ 을 곧이곧대로 곱하면 몇백 라운드 만에 언더플로로 가중치가 전부 0이 된다. 누적 손실 $L_i$ 를 유지하고 필요할 때 log-sum-exp로 정규화하는 것이 표준이다(소프트맥스 함수와 같은 구현 이슈).
$\eta$ 가 크면 한 후보만 남는다. 초반에 운 나쁘게 손실이 큰 후보가 영구 배제되고, 뒤늦게 그 후보가 최선으로 밝혀져도 회복이 안 된다. 위의 fixed-share 혼합이 보험이다.
손실 범위를 반드시 정규화한다. 상한의 모든 상수가 $[0,1]$ 가정 위에 서 있다. 스케일이 다른 지표를 섞어 넣으면 큰 지표 하나가 사실상 알고리즘을 독차지한다.
후회는 누적 척도다. 부분선형 후회는 “장기적으로 최선 고정 후보만큼 한다”일 뿐, 초반 손실이 실제 비용인 시스템(제어, 입찰)에서는 그 초반이 사고다.

응용은 후보가 여럿이고 정답을 미리 못 고르는 자리라면 어디든 있다. 여러 예측 모델을 온라인으로 결합하는 앙상블 예보식 모델 결합(전력 수요·기상 분야에서 실제 운용된다), 여러 전처리기·솔버 설정 중 어느 것이 이 문제에 잘 듣는지를 온라인으로 고르는 알고리즘 선택, 불완전 정보 게임에서 정보집합마다 후회 최소화기를 두는 CFR 계열 해법(몬테카를로 트리 탐색의 사촌), 그리고 강화 학습의 소프트맥스 정책 갱신 — 최대 엔트로피 강화 학습의 정책 개선 단계는 형태상 헤지 갱신 그 자체다. 알고리즘 하나가 이렇게 여러 분야에서 따로 발견된 데에는 이유가 있다.

9. 관련 문서[편집]

논문 제목이 A decision-theoretic generalization of on-line learning and an application to boosting이다. 제목의 뒷부분이 앞부분보다 훨씬 유명해진 드문 사례. 저자들은 이 논문으로 2003년 괴델상을 받았는데, 수상 사유에서 더 크게 다뤄진 쪽도 부스팅이다. ↩
손실 범위를 안 맞추고 헤지를 돌린 뒤 “이론대로 안 나온다”고 하는 사례가 꾸준히 있다. 상한의 $\eta T/8$ 항에서 8이라는 숫자는 폭 1인 구간의 회프딩 상수이고, 폭이 $M$ 이면 그 자리에 $M^2$ 이 붙는다. 로그 손실처럼 위로 유계가 아닌 손실은 아예 다른 분석(보브크의 집계 알고리즘 계열)이 필요하며, 그쪽에서는 혼합 가능(mixable) 손실에 대해 $T$ 에 무관한 상수 후회까지 나온다. ↩
폭을 무시하고 반복 횟수만 세면 MWU는 만능처럼 보인다. 실제로는 $\varepsilon^{-2}$ 의존성 때문에 정밀도 요구가 조금만 올라가도 반복이 폭발해서, 중간 정밀도로 충분한 근사 문제에만 쓴다. 정확한 최적해가 필요하면 내부점법이나 심플렉스를 쓰는 게 맞다. “빠른 근사 vs 느린 정확”, 수치해석의 오래된 그 선택이 여기서도 똑같이 반복된다. ↩