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

Photo by M. B. M. on Unsplash

우리는 미래를 모릅니다. 하지만 알고 싶어 합니다. 당장 한 달 후에 어떤 회사의 주식이 급등할지, 일 년 후에 어느 부지에 국가 사업이 진행될지, 십 년 후에 어떤 나라가 투자 가치가 높은 나라가 될지 궁금해 합니다. 미래를 정확히 예측한다면 부의 축적에 직결되는 경우가 많기 때문입니다. 그렇지만 혼자서 이 모든 것들을 예측한다는 것은 부담스러운 일입니다. 정보의 양과 질, 모든 측면에서 부족할 가능성이 높기 때문이죠.

 

따라서 우리는 여러 전문가의 조언에 귀를 기울입니다. TV나 유튜브 등을 통해 우리는 어떤 주식이 대박이 날 것인지 예측하는 "전문가"들을 많이 볼 수 있습니다. 저는 잘 모르지만, 약간의 혹은 상당한 금액을 지불하면 미래 예측에 대한 양질의 정보를 알려주는 매체도 있을 것입니다. 여하튼 이러한 전문가들은 대체로 "이 주식을 지금 사지 않으면 반드시 후회합니다!"와 같이 매우 자극적인 문구로 사람들에게 홍보합니다. 여기서 우리는 새로운 고민에 맞닥뜨리게 됩니다. 그 말을 믿을 수 있을까요?

 

오늘의 주제는 바로 전문가의 조언을 토대로 미래를 예측하는 방법입니다. 물론 아래에서 소개할 문제는 현실의 문제를 모두 반영하기에는 턱없이 부족한 심히 단순한 문제이기는 합니다. 하지만, 미래를 예측하는 방법에 대한 수학적 결과물이 있다는 것이 놀라워 함께 공유하고자 정리했습니다.

문제 정의

여러분은 어떤 회사의 주식에 큰 관심을 갖고 있습니다. 따라서 다음날 주식이 오를 것인지 내려갈 것인지 매번 예측하고자 합니다. 이때 얼마큼 오르고 내려갈지에 대해서는 관심이 없다고 하죠. 오른다고 예측하면 왕창 사놓고, 내려간다고 예측하면 왕창 팔아버리면 되니까요.

 

혼자서는 힘들 것 같아서 여러분은 전문가의 도움을 구하고자 합니다. 총 \(n\) 명의 전문가는 각자 다음날 주식이 오를지 내릴지에 대해 예측을 내놓습니다. 여러분의 목표는 전문가들의 조언을 바탕으로 최대한 예측에 실패하는 횟수를 최소화하는 것입니다.

예측의 달인이 있는 경우

여러분이 고려하는 전문가 중에 예측의 달인이 있다고 가정해 보겠습니다. 이 달인은 다음날 주식이 오르면 반드시 오른다고 예측하고, 주식이 내려가면 반드시 내려간다고 예측하는 전문가입니다. 따라서 달인이 예측하는 대로 따라가기만 한다면 여러분은 목표를 이루고 떼돈을 벌 수 있을 것입니다. 문제는 어떤 전문가가 달인인지 모른다는 것이죠. 이는 다음의 알고리즘을 통해 예측 실패를 적게 하면서 해결할 수 있습니다.

알고리즘 1. Binary prediction with expert advice where an oracle exists

---

초기 입력: 달인이 포함된 전문가 집합 \(E\)

출력: 매번 다음날 예측한 결과

 

1. 매번 현재 \(E\)의 조언 중 다수결에 따라 결정한다.(동률인 경우 아무거나 결정한다.)
2. 만약 다음날 예측에 실패하면 다음을 수행한다.
   1. 예측에 실패한 전문가 집합을 \(E_\mathsf{wrong}\)라고 하자.
   2. \(E \gets E \setminus E_\mathsf{wrong}\)

이 알고리즘이 동작하는 원리는 간단합니다. (누구인지는 모르나) 달인이 존재한다는 것을 안다면 해당 달인을 찾는 것이 우리의 목표가 됩니다. 매번 다수결에 따라 결정하기 때문에, 예측에 실패한 경우에는 현재 고려하는 전문가 중 절반 이상이 달인이 아니라는 것을 알 수 있습니다. 따라서 더이상 그들의 조언은 신경 쓸 필요가 없는 것이죠. 이를 통해 우리는 다음과 같은 사실을 알 수 있게 됩니다.

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

---

다음날 주식이 오를지 내려갈지 항상 정확하게 예측하는 전문가가 존재한다면 알고리즘 1은 최대 \(\log_2 n\) 번 예측에 실패한다.

[증명] 알고리즘 1이 총 \(M\) 번 예측에 실패하였다고 하죠. \(E_\mathsf{init}\)을 처음 주어지는 전문가 집합, \( E_\mathsf{last} \)를 최종적으로 갖고 있는 전문가 집합이라고 부르겠습니다. 먼저, 정의에 의해 \( |E_\mathsf{init}| = n, \) 정확히 예측하는 전문가는 반드시 포함하고 있으므로 \( |E_\mathsf{last}| \geq 1 \)임을 알 수 있습니다. 알고리즘의 동작을 잘 살펴보면 한 번 틀릴 때마다 최소 절반 이상은 고려 대상에서 제외되므로 \[ 1 \leq |E_\mathsf{last}| \leq \frac{|E_\mathsf{init}|}{2^M} = \frac{n}{2^M} \]이라는 사실도 얻을 수 있습니다. 이를 정리하면 \( M \leq \log_2 n \)을 이끌어 낼 수 있습니다. ■

일반적인 경우

매번 정확한 예측을 한다는 것은 신기에 가까운 일이죠. 그러니 이번에는 좀더 일반적인 경우에 대해서 고민해 보도록 하겠습니다. 일단 이 경우에는 틀린 예측을 하는 횟수 자체를 최소화하는 것은 무리가 따릅니다. 예를 들어, 모든 전문가가 매번 주식이 오른다고 예측하는데 반해 실제로는 계속 주식이 떨어지기만 하는 상황을 생각해 보죠. 전문가의 말을 듣기만 한다면 결국 매번 예측 실패만 하게될 겁니다. 그렇다고 전문가의 조언을 고려하지 않자니 모든 전문가가 매번 예측을 맞추는 반대의 경우도 무시할 수 없습니다.

 

따라서 약간 다른 기준으로 알고리즘의 성능을 평가하고자 합니다. 바로 전문가가 예측에 실패한 횟수와 비교하는 것입니다. 즉, 고려하는 전문가 중에서 가장 예측을 잘한 전문가가 실패한 횟수에 비슷한 횟수로 예측에 실패하는 알고리즘을 만들 수 있겠냐는 겁니다. 그러면 전문가가 벌어들이는 수익의 최댓값에 준하는 수익을 올릴 수 있겠죠. 놀랍게도 알고리즘 1의 아이디어를 확장하면 가능합니다.

 

알고리즘 1을 일반적인 경우에 바로 적용하기 어려운 가장 큰 이유는 한 번 예측에 실패하면 바로 고려 대상에서 삭제하기 때문입니다. 모든 전문가가 실패할 가능성이 있기 때문에 이번에는 예측을 실패했다고 곧장 열외로 이어져서는 안됩니다. 

 

그렇다고 아무것도 안 할 수는 없으니, 대신 페널티를 부여하고자 합니다. 무슨 말이냐면, 각 전문가마다 가중치를 부여하여 그 가중치에 비례하여 조언을 수렴하여 결정한 후에, 만약 예측이 잘못되었으면 잘못된 예측을 한 전문가의 가중치를 깎는 방식으로 동작하는 것입니다. 그러면 종국적으로 적은 횟수로 예측에 실패한 전문가의 조언을 더 많이 듣고, 많이 틀린 전문가의 조언은 잘 듣지 않게 되겠죠. 이 아이디어를 정형화하면 다음 알고리즘을 얻을 수 있습니다.

알고리즘 2. Weighted majority algorithm

---

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

출력: 매번 다음날 예측한 결과

 

1. 모든 \(i \in E\)에 대해 \(w_i \gets 1\)
2. 매번 다음을 수행한다.
   1. 주식이 오른다고 예측한 전문가의 집합을 \(E_\mathsf{up}\), 내려간다고 예측한 전문가의 집합을 \(E_\mathsf{down}\)이라고 하자.
   2. 만약 \( \sum_{i \in E_\mathsf{up}} w_i > \sum_{i \in E_\mathsf{down}} w_i \)이면, 오른다고 예측한다. 그렇지 않으면 내려간다고 예측한다.
   3. 잘못된 예측을 한 전문가의 집합 \(E_\mathsf{wrong}\)라고 했을 때, 모든 \( i \in E_\mathsf{wrong}\)에 대해, \(w_i \gets (1 - \epsilon) w_i\)

유용한 부등식

이 알고리즘을 분석할 때 유용하게 사용되는 부등식을 정리하겠습니다.

정리 2. 유용한 부등식 1

---

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

[증명] 먼저, 모든 실수 \(x\)에 대해 \( 1+x \leq e^x \)입니다. 왜냐하면 \(y = e^x\)는 아래로 볼록하고, \(y = e^x\)의 \( (0, 1) \)에서의 접선의 방정식이 \(y = x + 1\)이기 때문입니다. 양변에 자연로그를 취하면 원하는 부등식을 얻을 수 있습니다. ■

정리 3. 유용한 부등식 2

---

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

[증명] 정리 2에 \(x = \frac{y}{1-y}\)를 대입하면 \[ \ln \left( \frac{1}{1-y} \right) \leq \frac{y}{1 - y} \]를 얻을 수 있습니다. 양변을 \(y\)로 나누면 구하고자 하는 부등식을 이끌어낼 수 있습니다. ■

분석

이제 알고리즘이 우리가 원하는 대로 동작한다는 것을 보이도록 하죠.

정리 4. 알고리즘 2의 성능

---

임의의 \(T\) 번째 날이 시작할 때까지 알고리즘 2가 예측에 실패한 횟수를 \(M\), 전문가 중 예측에 실패한 횟수의 최솟값을 \(m\)이라고 할 때, \[ M < \frac{2}{1 - \epsilon} m + \frac{2}{\epsilon} \ln n\]을 항상 만족한다.

[증명] 매 \(t\) 번째 날이 시작할 때 알고리즘이 각 전문가에 대해 유지하는 \(w_i\)를 \(w_{i,t}\)라고 하겠습니다. 그리고 이를 모두 합한 값을 \(W_t\)라고 부르겠습니다. 즉, \(W_t = \sum_{i \in E} w_{i,t}\)입니다.

 

만약 \(t\) 번째 날에 알고리즘의 예측이 틀렸다면 그때의 \(E_\mathsf{wrong}\)에 대해서, \[ \sum_{i \in E_\mathsf{wrong}} w_{i, t} \geq \frac{W_t}{2} \]라는 뜻입니다. 한편, 알고리즘의 동작에 의해 \[ W_{t + 1} = \sum_{i \in E_\mathsf{wrong}} (1 - \epsilon) w_{i, t} + \sum_{i \notin E_\mathsf{wrong}} w_{i, t} = \sum_{i \in E} w_{i, t} - \epsilon \sum_{i \in E_\mathsf{wrong}}w_{i, t}\]라는 사실을 알 수 있으며, 이 두 식을 조합하면 \(t\) 번째 날에 예측이 틀린 경우 \[ W_{t + 1} \leq \left( 1 - \frac{\epsilon}{2}\right) W_t \tag{1} \]라는 사실을 얻을 수 있습니다.

 

\(T\) 번째 날에 대해서 \(m\) 번 예측에 실패한 전문가를 \(i^\star \in E\)라고 하면 \( w_{i^\star, T} = (1 - \epsilon)^m \)임을 알 수 있습니다. 이는 자연스럽게 \[ W_T > w_{i^\star, T} \geq (1 - \epsilon)^m \tag{2} \]이라는 사실을 유도하게 됩니다.

 

반대로 \(T\) 번째 날까지 알고리즘은 \(M\) 번 예측에 실패하므로 식 1을 실패할 때마다 적용하면, \[ W_T \leq \left( 1 - \frac{\epsilon}{2} \right)^M W_1 = n \left( 1 - \frac{\epsilon}{2} \right)^M \tag{3}\]임을 얻을 수 있습니다. 이때 마지막 등식은 모든 전문가에 대해 알고리즘의 초기 \(w_{i, 1} = 1\)이어서 \(W_1 = n\)이 되어 성립합니다.

 

식 2와 3을 합친 후 정리하면, \[ \left( 1 - \frac{\epsilon}{2} \right)^M > \frac{(1 - \epsilon)^m}{n} \]가 됩니다. 양변에 자연로그를 취하면 \[ M \ln \left( 1 - \frac{\epsilon}{2} \right) > m \ln (1-\epsilon) - \ln n, \] 여기서 좌변에 정리 2를 \( x := -\frac{\epsilon}{2} \)에 대해 적용하면 \[ - \frac{\epsilon}{2} M > m \ln (1 - \epsilon) - \ln n \]를 얻을 수 있습니다. 여기서 양변을 \( - \frac{\epsilon}{2} \)로 나누면, \[ M < \frac{2}{\epsilon} m \ln \left( \frac{1}{1 - \epsilon} \right) + \frac{2}{\epsilon} \ln n \]을 이끌어낼 수 있고, 우변에 정리 3을 \( y := \epsilon\)에 대해 적용하면 \[ M < \frac{2}{1 - \epsilon} m + \frac{2}{\epsilon} \ln n \]이 되어 정리의 부등식을 보일 수 있습니다. ■

마치며

이것으로 여러 전문가들이 조언을 해주는 상황에서 다음날 주식이 올라갈지 내려갈지 예측하는 간단한 문제를 해결하는 방법을 알아보았습니다. 알고리즘 2에서 \(\epsilon\)을 적당히 작은 값으로 정하면 전문가가 예측을 틀린 횟수의 최솟값 \(m\)에 대해 최대 \(2m + O(\log n)\) 번 정도 예측에 실패하게 될 것입니다. 시간이 충분히 흐른 후에는 대개 \(m \gg n\)일 것이므로 전문가의 예측에 근접한 예측 결과를 얻게 됩니다.

 

이러한 의사 결정 기법을 multiplicative weight update method라고 부르기도 합니다. 흥미롭게도 이 기법은 게임 이론, 기계학습, 최적화 분야를 넘어 컴퓨터과학 전반에 걸쳐 많은 영향을 준 기법이라고 합니다. 논문을 읽는 중 우연한 계기로 이 분야에 대해서 알게 되었는데, 매우 흥미로워서 개인적으로 좀더 공부를 해보고자 합니다.

 

다음번에는 이 문제를 좀더 일반적인 경우로 발전시키고, 이를 해결하는 방법에 대해서 알아보도록 하겠습니다. 특히 이번 시간에 소개한 두 알고리즘은 모두 deterministic algorithm인데, 다음에는 randomized algorithm을 가지고 오도록 하겠습니다. 과연 randomized algorithm은 얼마큼 성능이 좋아지게 될까요?

 

잘못된 점이 있거나 궁금하신 부분이 있으시면 알려주시기 바랍니다. 고맙습니다. :)

참조

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

 

[2] Multiplicative weight update method 내용 : https://en.wikipedia.org/wiki/Multiplicative_weight_update_method