확률 가중 다수결 알고리즘 (Randomized Weighted Majority Algorithm)

Photo by Headway on Unsplash

지난 시간에 함께 공부한 문제는 다음과 같습니다. 여러분은 다음날 어떤 회사의 주식이 오를지 내릴지 관심이 있습니다.(등락의 폭은 상관하지 않습니다.) 아무 정보도 없이 무턱대고 예상을 하는 것은 너무 멍청하다고 생각한 여러분은 총 \(n\) 명의 전문가를 초빙합니다. 매일 각 전문가는 다음날 회사의 주식이 오를 것인지 내릴 것인지에 대해서 예측합니다. 전문가들도 예측에 실패할 수 있습니다. 여러분의 목표는 가장 적중률이 좋은 전문가에 필적하는 정도의 예측을 하는 것입니다.

 

다음은 지난 포스트에서 같이 알아본 내용을 간략히 정리한 것입니다.

• 만약 (누구인지는 모르지만) 전문가 집단 중 매번 예측을 맞추는 달인이 존재하면, \( \log_2 n \) 번 안에 해당 달인을 찾아낼 수 있습니다.
• 일반적인 경우 어떤 작은 \( 0 < \varepsilon < 1 \)에 대해 \(T\) 번째 날까지 가장 적중률이 좋은 전문가가 예측에 실패한 횟수를 \(m\) 번이라고 할 때, 아무리 못해도 \( \frac{2}{1 - \varepsilon} m + \frac{2}{\varepsilon}  \ln n\) 번만 실패하며 예측하는 방법이 존재합니다. 이는 \( \varepsilon \)이 적당히 작고, \(T\)가 충분히 크다는 전제 하에서는 최고의 전문가가 실패하는 횟수의 약 두 배 정도로 실패하는 수준이 됩니다.

좀더 자세한 내용이 궁금하시면 이전 글을 참조하세요.

2020/05/30 - [온라인 알고리즘/Prediction] - 어떤 전문가의 말을 들어야 할까? (Prediction with Expert Advice)

어떤 전문가의 말을 들어야 할까? (Prediction with Expert Advice)

이번 시간에는 이전 글에서 두 번째로 소개한 알고리즘인 가중 다수결 알고리즘(weighted majority algorithm)을 좀더 발전시켜보도록 하겠습니다.(번역은 제가 직접 한 것입니다. 인터넷에 찾아 봤는데 적당한 우리말이 없는 것 같아 지었습니다.) 어떻게 하면 알고리즘을 발전시킬 수 있을까요? 바로 확률을 이용하는 것입니다. 이전에 소개한 알고리즘은 결정론적(deterministic)이었습니다. 즉, 동일한 입력에 대해서는 동일한 출력을 내는 알고리즘이라는 뜻이죠. 하지만 알고리즘에 확률을 도입하면 같은 입력에 대해서도 다른 결과를 도출할 수 있기 때문에 경우에 따라서는 더 좋은 결과를 "기대"할 수 있게 됩니다. 놀랍게도 이 알고리즘에 확률이라는 조미료로 약간만 양념을 치면 적중률이 가장 좋은 전문가에 준하는 예측 방법을 기대할 수 있게 됩니다.

 

들어가기에 앞서 지난 시간에 요긴하게 사용한 부등식을 가지고 오겠습니다. 증명은 이전 글에서 확인할 수 있습니다.

정리 1. 유용한 부등식 1

---

\(x > -1\)인 모든 실수에 대해 \( \ln(1 + x) \leq x \)이다.

정리 2. 유용한 부등식 2

---

임의의 \(y \in (0, 1) \)에 대해서, \[ \frac{1}{y} \ln \left( \frac{1}{1 - y} \right) \leq \frac{1}{1-y} \]이다.

모델 정의

알고리즘을 소개하기 앞서 이번 시간에 공부할 문제의 모델을 적확히 짚고 넘어가도록 하겠습니다. 온라인 문제(online problem)에서는 대개 불공평한 상대방(adversary)을 상정하여 문제를 구성합니다. 이 문제에서도 비슷하게 상대방이 존재합니다. 하지만 약간 다른 점도 있습니다. 바로 전문가들이 문제의 한 축을 담당한다는 것이죠.

 

여기서 전문가의 위치가 약간 애매합니다. 완전히 제삼자의 위치에 있을지, 아니면 상대방의 편에서 우리를 완전 망치려고 드는 사람들일지 결정할 필요가 있습니다. 이 글에서는 상대방과는 완전 무관한 제삼자의 위치에 있다고 가정합니다. 그렇지만 전문가들이 상대방과 모종의 "커넥션"이 있는 경우라도 아래의 알고리즘은 동일한 성능을 가집니다. 다만 전자든 후자든 반드시 만족시켜야 하는 한 가지 조건이 있는데, 바로 전문가가 모두 정직하다는 점입니다. 다시 말해, 전문가가 대외적으로는 오른다고 설쳐 놓고 속으로는 내려간다고 투표하는 경우는 없다는 것이죠.

 

사실 정직한 전문가를 가정한 경우라면, 상대방도 무지각형 상대방(oblivious adversary)이든 적응형 상대방(adaptive adversary)이든 상관이 없습니다. 어차피 우리의 목표는 가장 높은 적중률을 보인 전문가에 필적하도록 예측하는 것이니까요. 이 글에서는 무지각형 상대방을 가정하겠습니다. 즉, 모든 날의 오를지 내려갈지에 대한 답을 미리 정해두고, 매일 정해 놓은 답을 차례로 보여주는 상대방입니다. 

 

위 논의를 기초로 하여 문제의 모델이 다음과 같은 순서대로 진행한다고 정의하겠습니다.

1. 매일 모든 전문가들은 지금까지 알려진 정보를 토대로 오늘 주식이 오를지 내려갈지에 대한 예측을 내놓습니다.
2. 우리도 지금까지 알려진 정보를 토대로 오를지 내릴지를 예측합니다.
3. 마지막으로 상대방은 오늘의 결과를 발표합니다.

여기서 지금까지 알려진 정보라 함은 지금껏 세 번째 단계에서 밝혀진 모든 결과를 비롯하여 전문가들이 지금까지 어떻게 예측을 했는지 등 매일 시작할 때 얻을 수 있는 모든 정보를 총칭합니다. 거기에다 오늘 전문가들의 예측이 어떤지에 대한 정보까지 두 번째 단계에서 우리는 알 수 있습니다.

알고리즘 및 분석

이제 가중 다수결 알고리즘에 확률을 섞어보도록 하죠.

알고리즘 1. Randomized weighted majority algorithm

---

초기 입력: 전문가 집합 \(E\), 상수 \(\varepsilon \in (0, 1)\)

출력: 매번 당일 예측 결과

 

1. 모든 \(i \in E\)에 대해 \(w_{i, 1} \gets 1\)
2. 매 \(t = 1, 2, \cdots \) 번째 날에 다음을 수행한다.
   1. \(W_t \gets \sum_{i \in E} w_{i, t}\)
   2. 전문가 \(i_t\)를 \( \frac{w_{i_t, t}}{W_t} \)의 확률로 선택한 후 \(i_t\)와 동일한 선택을 내린다.
   3. (\(t\) 번째 날 결과 발표)
   4. 잘못된 예측을 한 전문가의 집합 \(E_\times \)라고 했을 때, 모든 \( i \in E_\times \)에 대해, \(w_{i, t + 1} \gets (1 - \varepsilon) w_{i, t}\)

이 알고리즘이 예측에 실패한 횟수의 기댓값이 가장 예측을 잘한 전문가의 그것과 비슷한 수준이 된다는 점을 분석하겠습니다.

정리 3. 알고리즘 1의 성능

---

임의의 \(T\) 번째 날이 시작할 때까지 알고리즘 1이 예측에 실패한 횟수를 \(M\), 전문가 \(i\)가 실패한 횟수를 \(m_i\)라고 할 때, \[ \mathbb{E}[M] \leq \frac{1}{1 - \varepsilon} \mathbb{E} \left[ \min_{i \in E} m_i \right] + \frac{1}{\varepsilon} \ln n \]을 만족한다.

[증명] 임의의 \(t = 1, \cdots, T - 1\)에 대해 \(X_t\)를 \(t\) 번째 날에 예측이 틀린 경우 \( 1 \)의 값, 그렇지 않으면 \(0\)의 값을 갖는 확률 변수(random variable)로 정의하겠습니다. \(M\)은 알고리즘이 예측에 실패한 총 횟수이므로 \( M = \sum_{t = 1}^{T - 1} X_t \)가 되며, 양변에 기댓값을 취하면 기댓값의 선형성(linearity of expectation)에 의해 \[\mathbb{E}[M] = \mathbb{E} \left[\sum_{t = 1}^{T - 1} X_t \right] = \sum_{t = 1}^{T - 1} \mathbb{E}[X_t] \tag{1} \]를 얻을 수 있습니다.

 

(어떻게 그렇게 됐는지는 상관 없이) \(t\) 번째 날이 시작할 때 알고리즘이 갖는 가중치가 정확히 \( \mathbb{w}_t = (w_{1, t}, \cdots, w_{n, t}) \)이고, 이 날 틀린 예측을 한 전문가 집합은 정확히 \( E^t_\times \)라고 하겠습니다. 그러면 이러한 조건 하에서 \(X_t\)의 기댓값을 다음과 같이 구할 수 있습니다.

\[ \mathbb{E}[X_t | \mathbb{w}_t, E^t_\times ] = \sum_{i \in E^t_\times} Pr[ i = i_t | \mathbb{w}_t, E^t_\times]  = \sum_{i \in E^t_\times} \frac{w_{i, t}}{W_t} \tag{2} \]

첫 번째 등식은 \(X_t\)의 정의에서 쉽게 유추할 수 있습니다. 알고리즘이 고른 전문가가 하필 \( E^t_\times \)에 들어가야 \(X_t = 1\)이고 그외의 경우에는 모두 \( X_t = 0 \)이기 때문입니다. 마지막 등식은 \( \mathbb{w}_t \)가 주어졌을 때, 알고리즘이 전문가 \(i\)를 뽑는 확률은 (\(E^t_\times\)에 상관 없이) \( \frac{w_{i, t}}{W_t} \)라는 사실에서 유도할 수 있습니다.

 

이번에는 \(W_t\)와 \(W_{t + 1}\)의 관계를 살펴보도록 하겠습니다. 알고리즘의 단계 2-d에서 우리는 \[ W_{t + 1} = \sum_{i \in E \setminus E^t_\times} w_{i, t} + \sum_{i \in E^t_\times} (1 - \varepsilon) w_{i, t} = W_t \left( 1 - \varepsilon \sum_{i \in E^t_\times} \frac{w_{i, t}}{W_t} \right) \]을 이끌어낼 수 있습니다. 우변의 곱셈은 나중에 다루기 까다로워 양변에 자연 로그를 취해 주도록 합시다. 그렇게 해도 괜찮은 이유는 \( W_{t} > 0 \), \( W_{t + 1} > 0 \), \( \varepsilon < 1 \), 마지막으로 \( \sum_{i \in E^t_\times} \frac{w_{i, t}}{W_t} \leq 1 \)이기 때문에 좌변과 우변 모두 \(0\)보다 크다는 사실을 알 수 있어서 가능합니다. 그러면 \[ \ln W_{t + 1} = \ln W_t + \ln \left( 1 - \varepsilon \sum_{i \in E^t_\times} \frac{w_{i, t}}{W_t} \right) \leq \ln W_t - \varepsilon \sum_{i \in E^t_\times} \frac{w_{i, t}}{W_t} \tag{3} \]라는 식을 얻을 수 있게 됩니다. 여기서 마지막 부등식은 정리 1로부터 유도할 수 있습니다.

 

그러므로 \( \mathbb{w}_t \)와 \(E^t_\times\)가 주어졌을 때, 식 3에 식 2를 적용하면 \[ \mathbb{E}[\ln W_{t + 1} | \mathbb{w}_t, E^t_\times] \leq \mathbb{E}[\ln W_t | \mathbb{w}_t, E^t_\times ] - \varepsilon \mathbb{E}[X_t | \mathbb{w}_t, E^t_\times] \]를 이끌어낼 수 있습니다. 임의의 모든 \( \mathbb{w}_t, E^t_\times \)에 대해서 위 부등식이 성립하기 때문에 아무 조건이 없는 기댓값들에 대해서도 여전히 같은 부등식이 성립합니다. 여기서 항들을 약간 조정하면, \[ \mathbb{E}[X_t]  \leq \frac{1}{\varepsilon}\mathbb{E}[\ln W_t] - \frac{1}{\varepsilon}\mathbb{E}[\ln W_{t + 1}] \]을 이끌어낼 수 있습니다. 이를 모든 \(t = 1, \cdots, T - 1\)에 대해 더하면 \[ \mathbb{E}[M] = \sum_{t = 1}^{T - 1} \mathbb{E}[X_t] \leq \frac{1}{\varepsilon} \mathbb{E}[\ln W_1] - \frac{1}{\varepsilon} \mathbb{E}[\ln W_T] \tag{4} \]를 얻게됩니다.

 

먼저 알고리즘의 1번 단계에 의해 \( W_1 = \sum_{i \in E} w_{i, 1} = n \)이라는 사실을 쉽게 알 수 있습니다. 다음으로 \(T\) 번째 날이 시작할 때, 가장 적중률이 좋은 전문가가 예측에 실패한 횟수를 \(m := \min_{i \in E} m_i\)라고 하겠습니다. 그러면 그 전문가의 가중치는 \( (1 - \varepsilon)^m \)이 될 것이고, 따라서 \( W_T \geq (1 - \varepsilon)^m \)이라는 사실도 쉽게 이끌어낼 수 있습니다. 이를 식 4에 적용하면 \[ \begin{array}{rcl} \mathbb{E}[M] & \leq & \displaystyle \frac{1}{\varepsilon} \ln n - \frac{1}{\epsilon} \mathbb{E}[m \ln (1-\varepsilon)] \\ & =  & \displaystyle \frac{1}{\epsilon} \ln n + \frac{1}{\varepsilon} \ln \frac{1}{1 - \varepsilon} \mathbb{E}[m] \\ & \leq & \displaystyle \frac{1}{\varepsilon} \ln n + \frac{1}{1 - \varepsilon} \mathbb{E}[m] \end{array} \]이 됩니다. 여기서 마지막 부등식은 정리 2를 통해서 얻은 결과입니다. □

마치며

이것으로 가중 다수결 알고리즘에 확률을 도입하여 최고의 전문가의 예측 능력에 준하는 예측 방법을 기대할 수 있는 알고리즘이 있다는 것을 모두 살펴보았습니다. 사실 이 알고리즘을 약간만 수정하면 일반적인 비용 함수가 주어진 상황에서도 비슷한 결과를 출력하는 알고리즘으로 만들 수 있습니다. 좀더 엄밀하게 문제의 모델을 설명해 보겠습니다. 전문가의 집합을 \(E\)라고 하겠습니다.(단, \(n := |E|\)) 매 \(t\) 번째 날이 시작할 때, 우리는 전문가 \(i_t \in E\)를 하나 선정해야 합니다. 그후 \(t\) 번째 날의 비용 함수 \(c_t : E \rightarrow \mathbb{Q}_+\)가 주어집니다. 즉, \(t\) 번째 날에 우린 \(c_t(i_t)\)의 비용을 지불해야 하는 것이죠. 우리의 목표는 지불하는 비용이 각 전문가가 지불한 비용 중 가장 적은 값에 준하도록 선택하는 것이죠. 위에서 본 알고리즘을 수정하면 다음의 정리를 얻을 수 있다는 것이 잘 알려져 있습니다.

정리 4. 일반화된 모델에서의 예측 성능

---

위 모델에서 임의의 \(T > 0\)에 대해, \[ \mathbb{E} \left[ \sum_{t = 1}^T c_t(i_t) \right] \leq \frac{1}{1 - \varepsilon} \mathbb{E} \left[ \min_{i \in E} \sum_{t = 1}^T c_t(i) \right] + \frac{1}{\varepsilon} \ln n\]을 만족하는 \(i_1, i_2, \cdots, i_T\)를 출력하는 알고리즘이 존재한다.

이 모델이 위 문제를 표현할 수 있다는 점은 쉽게 파악할 수 있습니다. 잘못된 예측을 한 전문가 \(i\)에 대해 \(c_t(i) = 1\)을 주고 나머지는 \(0\)을 주면 되겠죠. 기회가 된다면 위 정리도 다루어 보도록 하겠습니다.

 

궁금하신 점이 있으시면 알려주시기 바랍니다. 읽어 주셔서 고맙습니다.

참조

[1] 전체적인 내용 : www.cs.cornell.edu/courses/cs683/2007sp/lecnotes/week1.pdf