야오의 법칙 (Yao's Principle)

Photo by dylan nolte on Unsplash

이번에는 Yao's principle에 대해서 알아보도록 하겠습니다. 이 글은 이전 포스트에서 이어지는 내용이 많으므로 이를 먼저 읽어 보시는 것을 추천드립니다. 또한 확률에 대한 기본적인 내용을 숙지하셨다는 가정 아래 글이 작성되었다는 점도 밝힙니다.

2019/08/11 - [수학적 도구/Randomness] - Arbitrary & Random

Arbitrary & Random

지난 시간 'random'을 설명하기 위해서 같이 고민했던 문제를 다시 가지고 오겠습니다.

여러분 앞에 카드 세 장이 뒤집힌 채로 놓여있습니다. 여러분은 카드의 뒷면에 각각 1, 2, 3이 적혀있는 것을 알지만, 어느 카드에 어떤 숫자가 적혀있는지는 모릅니다. 여러분은 이제 카드 한 장을 선택할 것입니다. 목표는 최대한 큰 숫자를 뽑는 것이죠. 과연 여러분이 뽑은 카드에는 무엇이 적혀있을까요?

이 문제를 좀 더 엄밀하게 적어보겠습니다. 우리에게 숫자 \(x_1\), \(x_2\), \(x_3\)가 주어집니다. 각각이 어떤 숫자인지는 모르지만 1이 하나, 2가 하나, 그리고 3이 하나씩 있는 것은 알고 있습니다. 다시 말해,

\[\{ x_1, x_2, x_3 \} = \{ 1, 2, 3\} \tag{1} \]

인 것이죠. 우리는 이 중에서 하나를 뽑을 텐데 최대한 큰 숫자를 뽑고자 합니다. 즉, 우리가 뽑은 수를 \(x\)라고 한다면, \(x\)를 최대화하는 문제인 셈이죠. 당연히 optimal value는 3이 될 것입니다.

 

이 문제를 푸는 알고리즘은 무엇이 있을까요? 네, 다음과 같이 총 세 가지가 있을 것입니다.

1. \(x_1\)을 선택하는 알고리즘
2. \(x_2\)를 선택하는 알고리즘
3. \(x_3\)를 선택하는 알고리즘

너무 당연한 것 아니냐고요? 흠흠, 뭐 아무튼 여러분들도 이것말고는 할 수 있는 방법이 없다는 점에 동의하실 겁니다. 그렇다면 여기에 나열된 알고리즘들의 성능은 어떻게 될까요? 모든 알고리즘이 최악의 경우 \(x = 1\)을 반환한다는 사실을 쉽게 보일 수 있습니다.

 

컴퓨터과학도라면 귀에 딱지가 앉도록 이 질문을 떠올리실 겁니다. 과연 더 잘할 수 있을까요? 지난 포스트에서도 말씀드린대로 그냥은 안 되겠지만 기대는 해봄직합니다. 바로 각각을 \( \frac{1}{3} \)의 확률로 선택하는 것이죠. 이때 알고리즘이 반환하는 결과 \(x\)에 대한 확률변수(random variable)를 \(X\)라고 한다면, 우리는 \(X\)의 기댓값을 다음과 같이 구할 수 있습니다.

\[ \mathbb{E} [X] = \frac{x_1}{3} + \frac{x_2}{3} + \frac{x_3}{3} = 2 \tag{2} \]

여기서 두 번째 등식이 성립하는 이유는 조건 1 덕분입니다. 이는 어떤 입력에 대해서도 성립하기 때문에 이 알고리즘은 최악의 경우에도 2를 반환한다는 것을 기대할 수 있습니다. 이것이 제가 '그냥은 안 되겠지만, 기대는 해봄직하다'고 말씀드린 이유입니다.

 

여기서 먼저 나온 \(x_1\)을 선택하는 알고리즘과 같이 어떤 입력이 주어졌을 때 이에 대한 결과가 일관되는 알고리즘을 deterministic algorithm이라고 하며, 나중에 소개한 알고리즘과 같이 알고리즘 내부에서 확률에 기반하여 알고리즘의 결과가 달라지게 되는 것들을 randomized algorithm이라고 합니다.¹ 전자는 입력이 정해지면 항상 동일한 결과를 반환하므로 최악의 결과값을 주는 입력이 알고리즘의 성능을 결정하게 됩니다. 반면에 후자의 경우 같은 입력이 주어져도 알고리즘 내부의 '시행'에 의해서 결과가 달라질 수 있습니다. 따라서 결과의 기댓값을 최소화시키는 입력으로 성능을 결정하게 되는 것이죠.

 

자, 그렇다면 앞에서 제시한 randomized algorithm보다 더 좋은 성능을 가진 알고리즘을 만들 수 있을까요? 결론부터 말하자면, 불가능합니다. 왜냐하면 이 문제에서는 우리가 어떤 randomized algorithm을 만들어도 최악의 경우 2보다 더 좋은 기댓값을 가질 수 없다는 것을 증명할 수 있기 때문입니다. 바로 오늘의 주제인 Yao's principle 덕분이죠.

Yao's principle

서론이 길었군요. 이제 Yao's principle에 대해서 설명을 드리도록 하겠습니다. 이전 글들을 보면 대개 직관적으로 이해하는 부분이 있고 그 다음에 주된 내용을 설명하곤 하였습니다만, 이번에는 약간 변화를 주어 먼저 어려운 내용부터 들어가보겠습니다. 그 다음에 이 법칙을 어떻게 위 문제에 적용할 수 있을지를 따져보도록 하죠.

 

우리가 어떤 문제를 푼다는 것은 어떤 알고리즘에 어떤 입력을 넣어서 결과를 얻는다는 것을 의미합니다. 이를 수학적으로 나타내보자면, 어떤 문제를 푸는 알고리즘 \(a\)가 주어지고 입력 \(i\)가 주어졌을 때 결과값 \(w(a, i)\)를 얻는다는 것이죠. 여기서 알고리즘은 deterministic algorithm입니다. 따라서 \( w(a, i)\)는 항상 같은 값으로 정해진다는 것을 알 수 있습니다.

 

이제 이 문제의 모든 deterministic algorithm의 집합을 \(\mathcal{A}\)라고 하고, 모든 입력의 집합을 \(\mathcal{I}\)라고 하겠습니다. 그렇다면 randomized algorithm은 무엇일까요? 네, 바로 \(\mathcal{A}\)에서 정의되는 확률변수 \(A\)라고 볼 수 있습니다. 즉, \(A\)가 내부의 모든 확률적인 시행을 끝낸 후 결과를 반환했을 때 역으로 각 시행마다 어떤 것을 선택했는지를 추적하면 결국 \(\mathcal{A}\) 안의 어떤 deterministic algorithm과 동일할 것입니다. 이는 확률변수 \(A\)의 realization인 것이죠. 이 알고리즘의 성능은 이 알고리즘이 반환하는 결과의 기댓값을 최소화시키는 것이므로

\[\min_{i \in \mathcal{I}} \mathbb{E} [ w(A, i) ] \tag{3} \]

라고 쓸 수 있습니다. 이 내용은 약간 어려울 수 있습니다. 하지만 이를 잘 이해하셔야 다음 단계를 수월히 이해할 수 있을 것입니다.

 

우리의 목표는 식 3의 상한을 찾는 것입니다. 그것이 바로 Yao's priniciple입니다.

Yao's principle

---

어떤 maximization² problem의 모든 deterministic algorithm의 집합을 \(\mathcal{A}\), 모든 입력의 집합을 \(\mathcal{I}\), 한 deterministic algorithm \(a \in \mathcal{A}\)에 입력 \(i \in \mathcal{I}\)를 수행했을 때 반환되는 결과값을 \(w(a, i)\)라고 하자. 이때, \(\mathcal{A}\)에서 정의된 임의의 확률변수 \(A\)와 \(\mathcal{I}\) 위의 임의의 확률변수 \(I\)에 대해 다음이 성립한다.

\[  \min_{i \in \mathcal{I}} \mathbb{E} [ w(A, i) ] \leq \max_{a \in \mathcal{A}} \mathbb{E} [ w(a, I) ] \tag{4} \]

당연하지만, 위 부등식에서 좌변의 기댓값은 \(A\)에 대한 것이고 우변의 기댓값은 \(I\)에 대한 것입니다.

 

증명은 생각보다 단순합니다. 어떤 확률변수 \(X\)가 주어졌을 때 \(X\)의 기댓값은 \(X\)가 가질 수 있는 최솟값보다는 크거나 같을 것이고 반대로 \(X\)가 가질 수 있는 최댓값보다는 작거나 같을 것입니다. 즉,

\[ \min X \leq \mathbb{E}[X] \leq \max X \tag{5} \]

라는 의미죠. 이를 활용하면 쉽게 식 4를 이끌어낼 수 있습니다.

\[ \begin{array}{rl} \displaystyle \min_{i \in \mathcal{I}} \mathbb{E} [ w(A, i) ] & = & \displaystyle \min_{i \in \mathcal{I}} \sum_{a \in \mathcal{A}} Pr[ A = a ] w(a, i) \\ & \leq & \displaystyle \sum_{i \in \mathcal{I}} Pr[I = i] \left( \sum_{a \in \mathcal{A}} Pr[ A = a ] w(a, i) \right) \\ & = & \displaystyle \sum_{a \in \mathcal{A}} Pr[ A = a ] \left( \sum_{i \in \mathcal{I}} Pr[I = i] w(a, i) \right) \\ & \leq & \displaystyle \max_{a \in \mathcal{A}} \sum_{i \in \mathcal{I}} Pr[I = i] w(a, i) \\ & = & \displaystyle \max_{a \in \mathcal{A}} \mathbb{E} [ w(a, I) ] \end{array} \]

이때, 첫 번째와 마지막 등식은 기댓값의 정의에 따른 것이고 두 번째 등식은 합의 순서를 바꾼 것입니다. 위 식에 나타난 두 부등식은 모두 부등식 5를 활용하여 이끌어낼 수 있습니다.

활용

이 법칙을 활용하여 앞의 문제에서 2의 기댓값을 갖는 randomized algorithm이 가장 좋은 알고리즘이라는 사실을 알아봅시다. 부등식 4의 좌변이 알고리즘의 성능이라는 점은 앞에서 말씀드렸습니다. 따라서, 우리가

\[ \max_{a \in \mathcal{A}} \mathbb{E} [ w(a, I) ] = 2 \tag{6} \]

를 만족하는 확률변수 \(I\)를 찾는다면 어떤 randomized algorithm도 2보다 좋은 기댓값을 가질 수 없을 것이며, 이는 우리가 앞서 구한 알고리즘이 최적이라는 점을 방증합니다.

 

그런데 도대체 \(I\)는 무엇일까요? 바로 알고리즘 입력에 대한 확률변수입니다. 그렇다면 우리 문제의 입력은 어떤 것들이 있을까요? 다음과 같이 총 6개의 경우가 있습니다.

\(x_1\)	\(x_2\)	\(x_3\)
1	2	3
1	3	2
2	1	3
2	3	1
3	1	2
3	2	1

이때 \(I\)에서 각각의 입력이 선택될 확률을 \(\frac{1}{6}\)이라고 정하겠습니다. 그러면 우리는 임의의 deterministic algorithm \(a\)에 대해서

\[ \mathbb{E} [w(a, I)] = 2\]

라는 사실을 증명할 수 있습니다. 간단합니다. 분명 deterministic algorithm은 다음 중 하나일 것입니다.

1. \(x_1\)을 선택하는 알고리즘
2. \(x_2\)를 선택하는 알고리즘
3. \(x_3\)를 선택하는 알고리즘

만약 \(a\)가 \(x_1\)을 선택하는 알고리즘이라면 \(\frac{1}{3}\)의 확률로 1이 될 것이고, \(\frac{1}{3}\)의 확률로 2, 또 같은 확률로 3이될 것입니다. 나머지 두 알고리즘에 대해서도 동일한 확률 분포를 얻을 수 있을 것입니다. 그러므로 이것의 기댓값은 자명하게 2가 되겠죠. 모든 알고리즘에 대해서 보였으니 식 6은 당연히 성립하게 됩니다.

마치며

이번 포스트에서는 Yao's principle에 대해 알아보았습니다. 어떤 문제를 풀 때 알고리즘 자체에 불확실성을 가미한다면 대체로 성능이 좋아지게 됩니다. Deterministic algorithm은 같은 입력에 대해서 동일한 결과를 주기 때문에 어떤 입력이 그 알고리즘을 망칠 수 있을 것인지가 (대개) 훤히 보이지만 randomized algorithm은 저번에 멍청한 결과를 뱉었다고 이번에도 멍청한 결과를 뱉을 것이라고 함부로 단정할 수 없습니다. 내부에서 어떻게 동작할지 가늠이 잡히지 않기 때문이죠.

 

성능이 좋아지는 것은 고무적인 일이지만 문제는 분석하기도 훨씬 까다로워진다는 점입니다. 뭐든지 확률이 들어오면 아주 골 때리는 것이죠. 하지만 Yao's principle은 이러한 총체적 난국에 한 줄기 빛과도 같습니다. 어떤 randomized algorithm도 어느 수준보다는 좋아질 수 없다는 것을 증명하기 때문이죠. 물론 이 증명도 그리 간단하지만은 않습니다. 이제는 입력의 분포를 찾아야하기 때문이죠. 그래도 이렇게 bound를 줄 수 있다는 것이 얼마나 고마운 일인가요.

 

이것으로 글을 마치도록 하겠습니다. 읽어주셔서 고맙습니다.

각주

1. 사실 randomized algorithm은 크게, 옳은 답을 반환하지만 수행시간이 변하는 Las Vegas algorithm과 수행시간은 보장되나 잘못된 답을 출력할 수도 있는 Monte Carlo algorithm으로 나뉩니다. 다만 이번 포스트에서 다루는 알고리즘은 수행시간도 보장되지만 3을 찾지 못할 수도 있으니 Monte Carlo algorithm이라고 생각할 수도 있겠습니다만, 그렇지 않습니다. 위 문제의 목표는 3을 찾는 것이 아닌 결과 \(x\)를 최대화시키는 것입니다. 따라서 하나 고른 것 자체가 feasible solution이 되며 \(x\)는 가중치라고 생각해야 합니다. 그러므로 이 알고리즘은 (수행시간은 보장되지만) 옳은 답을 반환하되 알고리즘의 확률적인 선택에 따라 결과값이 달라지는 알고리즘인 것이죠. 이러한 알고리즘도 Las Vegas algorithm이라고 부르나 봅니다.

 

2. 이 법칙은 minimization problem에도 동일하게 적용할 수 있습니다. 그 경우, 알고리즘의 성능은 \( \max_{i \in \mathcal{I}} \mathbb{E} [ w(A, i) ] \)로 결정되며 본문의 분석 방법을 유사하게 적용하면 \( \max_{i \in \mathcal{I}} \mathbb{E} [ w(A, i) ] \geq \min_{a \in \mathcal{A}} \mathbb{E} [ w(a, I) ] \) 임을 이끌어 낼 수 있습니다.