MaxUCB - Maximum Upper Confidence Bound

AI 모델을 학습시킬 때, 손실(loss)이 큰 데이터를 우선적으로 학습시키는 것은 상식적인 접근이다. 오답 노트처럼 틀린 문제를 다시 풀어보는 원리다. 하지만 오차가 가장 큰 데이터만 탐욕적으로(greedy) 고르면 부작용이 생긴다.

첫째, 예전에 학습해둔 쉬운 영역의 데이터를 까먹는 망각 현상이 발생한다.

둘째, 데이터 자체에 오류가 있거나 노이즈가 심한 경우, 오차가 영원히 줄어들지 않아 모델이 그 데이터에만 갇혀버린다.

이 문제를 해결하려면 '현재 오차가 큰 영역(활용)'과 '최근에 확인하지 않은 영역(탐색)' 사이의 균형이 필요하다. 이를 수학적으로 제어하는 방법이 UCB(Upper Confidence Bound) 알고리즘이다.

Max UCB의 개념

전체 데이터를 여러 구역으로 나눈 뒤, 각 구역마다 UCB 점수를 매긴다. 그리고 가장 점수가 높은(Max) 구역을 다음 학습 대상으로 고른다.

점수 공식의 뼈대는 다음과 같다.

UCB 점수 = 현재까지의 평균 오차 + 불확실성

평균 오차가 크면 점수가 높아지고, 해당 구역을 오랫동안 학습하지 않아 불확실성이 커져도 점수가 높아진다. UCB의 핵심은 이 불확실성을 수치화한 두 번째 항에 있다.

불확실성 수식의 수학적 도출

UCB의 불확실성 항은 통계학의 호에프딩 부등식(Hoeffding's Inequality)에서 도출된다.

어떤 구역의 실제 평균 오차를 $\mu$, 우리가 지금까지 관측한 표본 평균 오차를 $\bar{x}$라고 하자. 호에프딩 부등식은 우리가 관측한 $\bar{x}$가 실제 평균 $\mu$보다 특정 한계치 $u$ 이상 차이 날 확률이 지수적으로 감소한다는 것을 보여준다.

$$P(\mu \geq \bar{x} + u) \leq \exp(-2n_i u^2)$$

여기서 $n_i$는 해당 구역을 탐색(학습)한 횟수다.

우리는 이 오차가 한계치를 벗어날 확률을 아주 작은 값인 $p$로 통제하고 싶다. 부등식의 우변을 $p$라고 두면 다음과 같다.

$$\exp(-2n_i u^2) = p$$

이 식을 우리가 구하고자 하는 한계치(불확실성) $u$에 대해 정리한다. 양변에 자연로그를 취하면,

$$-2n_i u^2 = \ln p$$

$$u = \sqrt{\frac{-\ln p}{2n_i}}$$

여기서 알고리즘이 진행될수록 안 가본 구역에 대한 탐색 확률을 조금씩 높여주기 위해, $p$를 고정된 상수가 아니라 전체 탐색 횟수 $n$에 반비례하는 값으로 설정한다. 통상적으로 $p = n^{-4}$ 같은 다항식 붕괴 형태로 설정한다. $p$ 자리에 $n^{-4}$를 대입하면 식은 이렇게 변한다.

$$u = \sqrt{\frac{4 \ln n}{2n_i}}$$

여기서 상수 부분($\sqrt{4/2}$)을 하나의 조절 변수 $c$로 묶어내면 우리가 아는 최종 UCB 불확실성 항이 나온다.

$$u = c \sqrt{\frac{\ln n}{n_i}}$$

고손실 영역 샘플링에의 적용

최종적으로 도출된 UCB 공식을 고손실 구역 샘플링 모델에 적용하면 다음과 같은 형태가 된다.

$$UCB_i = L_i + c \sqrt{\frac{\ln n}{n_i}}$$

• $L_i$: $i$번째 구역의 현재 평균 손실

• $c$: 탐색 가중치

• $n$: 전체 학습 루프 횟수

• $n_i$: $i$번째 구역을 학습한 횟수

학습 루프가 돌 때마다 이 점수가 가장 큰 구역을 골라 학습을 진행한다.

특정 구역의 손실($L_i$)이 노이즈 때문에 줄어들지 않고 계속 높게 나오더라도, 그 구역을 반복해서 고르다 보면 분모인 $n_i$가 계속 커져 결국 UCB 점수가 낮아진다. 반면 그동안 방치되었던 다른 구역들은 분자의 $\ln n$이 커짐에 따라 불확실성 점수가 서서히 올라가서 결국 선택을 받게 된다.

결과적으로 데이터의 노이즈에 갇히는 문제를 막고, 구역 간 학습 빈도를 적절히 분배하여 망각 현상 없이 효율적으로 모델의 오차를 줄일 수 있다.