Arbitrary & Random

Photo by Jonathan Petersson on Unsplash

이번 주제는 'arbitrary'와 'random'입니다. 우리말로 번역하면 '임의의 & 무작위의' 정도가 되겠는데 이렇게 제목을 지어버리면 뭔가 제가 의도한 방향대로 읽히지가 않겠더군요. 제목을 영어로 짓기 싫었는데 어쩔 수 없었습니다.

 

컴퓨터과학을 전공하신다면 아마 두 단어를 많이 접하셨으리라고 생각합니다. 그만큼 많이 사용되는 단어인데 제대로 아시는 분은 그리 많지 않을 겁니다. 당장에 저만 하더라도 대학교 졸업할 때까지 둘의 차이를 명확하게 알지 못하였습니다. 대학원에 들어오고 나서야 둘의 차이를 구분할 수 있게 되었죠. 이렇게 헷갈리는데 우리말로 이를 제대로 설명한 글은 찾기가 힘들더군요.

 

우리말로 'arbitrary'는 '임의의'로, 'random'은 '무작위의' 정도로 번역이 되겠습니다. (영한 사전에서 그대로 긁어 왔습니다.) 뭔가 비스무리하게 들어맞는 것 같기는 하지만 이것만 가지고는 알기가 어려우니 영영 사전에서는 어떻게 나오는지 검색해 보았습니다. 먼저 'random'을 구글에 검색해 보면 다음과 같이 나옵니다.

random (adj.) made, done, happening, or chosen without method or conscious decision

이번에는 'arbitrary'입니다.

arbitrary (adj.) based on random choice or personal whim, rather than any reason or system

솔직히 말씀드리자면, 일상 영어에서는 둘의 구분이 별로 없다는 점에서 충격을 받았습니다. 전공 공부를 처음 하실 때 두 용어를 잘 몰라서 찾았다가는 난처한 상황에 빠질 수도 있겠네요.

 

결론부터 말씀드리면 컴퓨터과학에서 두 용어는 완전히 다릅니다. (아마 수학, 통계학에서도 동일하지 않을까 생각합니다만, 뭔가 다를 수 있으니 확신은 못하겠네요.) 사용되는 맥락 자체가 다릅니다. 이제부터 하나씩 차근히 설명드리도록 하겠습니다.

무엇을 선택해도 상관이 없을 때, arbitrary

먼저 'arbitrary'부터 시작하겠습니다. 절 제목에서처럼 'arbitrary'는 대상이 되는 것들 중에서 무엇을 선택해도 성능, 비용 등에 영향을 주지 않는 경우에 사용합니다. 영어에서 '아무'의 의미를 가진 'any'와 동일하다고 생각하면 편합니다.

 

예를 들어보죠. 자료구조를 수강하셨다면 minimum spanning tree(MST)에 대해서 아실 것입니다. 어떤 그래프와 간선 위의 비용이 주어졌을 때 비용이 가장 적은 spanning tree를 찾는 문제죠. 이 문제를 해결하는 다양한 알고리즘 중에서 Kruskal's algorithm을 가지고 오겠습니다.

Kruskal's algorithm

---

입력: 그래프 \(G = (V,E)\), 비용 \(c : E \rightarrow \mathbb{Q}\)

출력: \(G\)에서 비용이 가장 적은 spanning tree

 

1. \(T \gets \emptyset \)
2. \(E\)를 \(c\)의 오름차순으로 정렬한다.
3. \(T\)가 \(G\)를 spanning할 때까지 다음을 반복한다.
   
   1. 고려하지 않은 간선 중 가장 비용이 작은 간선 \(e\)를 가지고 온다.
   2. \(e\)가 \(T\)에 cycle을 만들지 않을 때만 \(T\)에 넣는다.
4. \(T\)를 반환한다.

여기서 3-i 단계를 잘 보시기 바랍니다. 고려하지 않은 간선 중에서 비용이 가장 작은 것을 택하는 단계입니다. 만약 비용이 가장 작은 간선이 두 개 이상이 있는 경우에는 무엇을 골라야 할까요? 네, 아무거나 골라도 됩니다. 여기서 무엇을 고르냐에 따라서 결과가 달라질 수는 있겠지만 그 비용은 항상 동일하다는 것을 증명하셨을 것입니다. 그러니 아무 상관이 없는 것이죠. 이런 경우에 사용하는 것이 바로 'arbitrary'인 것입니다.

어떤 분포에 따라 기댓값을 구할 때, random

그렇다면 'random'은 무엇일까요? 이는 완전히 다른 맥락에서 이해를 해야합니다. 다음 문제를 생각해 보죠.

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

만약 여러분이 첫 번째 카드를 뽑는다고 가정을 해보겠습니다. 여러분이 찾고자 하는 것은 숫자 3이 적힌 카드일 것입니다. 운이 좋으면 3을 뽑을 수도 있겠지만, 운이 나쁘면 1을 뽑을 수도 있습니다. 따라서 이 알고리즘은 최악의 경우 1을 뽑는 알고리즘인 것이죠.

 

여기서 주의하실 점은 우리는 입력에 대해서 전혀 모른다는 것입니다. 혹여나 첫 번째 카드에 1이 있을 확률이 \( \frac{1}{3} \), 2가 있을 확률이 \( \frac{1}{3} \), 3이 있을 확률이 \( \frac{1}{3} \)이라고 생각하시고 위 알고리즘이 2를 기대할 수 있는 것 아니냐고 말씀하신다면 이는 큰 오산입니다. 우리에게는 그러한 정보가 전혀 주어지지 않았습니다. 어쩌면 첫 번째 카드에 1만 적혀 있는 입력일 수도 있습니다. 그렇다면 빼도 박도 못하고 위 알고리즘은 1만 반환할 것입니다. 그러한 정보가 있다는 것만으로도 알고리즘의 성능이 확연히 달라지게 됩니다. 이는 나중에 다루어 보도록 하겠습니다.

 

입력이 어떻게 들어오는지 전혀 모르는 지금, 과연 더 잘할 수 있을까요? 여기서 'random'이 힘을 발휘하게 됩니다. 각각 \(\frac{1}{3}\)의 확률로 카드를 뽑는 알고리즘을 생각해 봅시다. 여러분이 뽑은 카드의 숫자를 \(X\)라고 하고, 첫 번째 카드에 적힌 숫자를 \(x_A\), 두 번째는 \(x_B\), 세 번째는 \(x_C\)라고 하겠습니다. 여기서 \(x_A\), \(x_B\), \(x_C\) 각각이 정확히 무슨 값인지는 모르지만 1 하나, 2 하나, 3 하나가 있다는 것은 알고 있습니다. 따라서 우리는 \(X\)가 다음의 값을 가질 것을 기대할 수 있습니다.

\[\mathbb{E}[X] = \frac{x_A}{3} + \frac{x_B}{3} + \frac{x_C}{3} = 2\]

이는 어떤 상황에서도 항상 성립하는 것이므로, 최악의 경우에 대해서도 성립한다고 말할 수 있습니다. 그러니 이 알고리즘이 앞서 소개한 첫 번째 카드를 고르는 알고리즘보다는 좋다고 말할 수 있는 거죠.

 

여기서 카드를 고르는 행동이 바로 'random'입니다. 우리가 무엇을 고르느냐에 따라서 결과가 달라지는 경우 선택을 확률적으로 진행하여 결과의 기댓값을 취하는 것이죠. 여기서 중요한 것은 'random'에는 반드시 확률 분포(probability distribution)가 정의되어야 한다는 점입니다. 앞의 예시에서 각 카드를 \( \frac{1}{3} \)의 확률로 뽑는 것이 바로 이 분포를 정의한 것이었습니다. 분포가 달라지면 자연스럽게 결과의 기댓값도 달라지게 되겠죠.

 

참고로 무엇을 고르냐에 따라서 결과가 달라지는 이러한 상황에서 'arbitrary'를 썼다면 이는 최악의 경우를 상정하는 것이라고 봐도 무방합니다. 어떤 것을 골라도 항상 이것보다는 좋아진다는 의미로 해석하면 되겠습니다. 예를 들어 이 문제에서는 어떤 알고리즘도 뽑기만 한다면 1보다는 크거나 같은 카드를 가질 것이므로 'arbitrary'하게 고르는 알고리즘의 성능은 최악의 경우 1이 되겠지요.

마치며

이것으로 'arbitrary'와 'random'의 차이점에 대한 설명을 마치도록 하겠습니다. 정리를 하자면 'arbitrary'는 말 그대로 아무 것이나 고르는 것을 의미하며, 이때 어떠한 것을 골라도 성능에 변화가 없거나 아무리 못해도 어떤 기준보다 못하지 않는 경우에 사용합니다. 반대로 'random'은 어떠한 확률 분포에 따라서 고르는 것을 의미하며, 이 분포에 따른 결과의 기댓값을 분석하고 싶을 때 사용합니다. 이제 두 단어의 차이가 명확히 보이시나요?

 

혹여나 MST를 모르시는 분이 읽으실까봐 'arbitrary'를 설명할 때 그것을 예시로 들고 싶지는 않았습니다. 그런데, 딱히 그것 말고는 이렇다 할 좋은 예시가 떠오르지가 않더군요. 혹시 MST를 잘 모르신다면 송구할 따름입니다. 기회가 되면 학부 자료구조, 알고리즘 쪽으로도 포스팅을 해보도록 하겠습니다.

 

만일 'random' 절을 다 읽어보셨다면 아마도 다음과 같은 질문이 자연스럽게(?) 떠오르실 겁니다. 과연 2를 기대하는 알고리즘보다 더 좋은 알고리즘을 구현할 수 있을까요? 우리가 조절할 수 있는 것은 각각의 카드를 뽑는 확률 분포가 되겠죠. 예를 들면 첫 번째, 두 번째, 세 번째를 각각 20%, 40%, 40%로 뽑는다든지 말이죠.

 

어느 정도 예상하셨겠지만, 더 이상 좋아질 수 없습니다. 이를 어떻게 증명할 수 있을까요? 바로 야오의 법칙(Yao's principle)을 통해서 보일 수 있습니다. 이 법칙은 randomized algorithm의 성능을 분석할 때 가장 중요한 법칙 중 하나입니다. 다음 포스트에서는 이 법칙에 대해서 알아보도록 하죠.

 

고맙습니다.