일전에 유명한 온라인 문제 중 하나인 online bipartite matching을 다룬 적이 있었습니다. 당시에는 제 지식이 그렇게 깊지 않아서 제대로 설명하지 못했을뿐더러 잘못 전달한 내용도 있었습니다. 최근 개인적으로 온라인 알고리즘을 다시 공부하기 시작했는데, 겸사로 기존의 포스트를 내리고 다시 글을 적어보고자 합니다. 기존의 포스트는 더욱 보강하여 다시 올리도록 하겠습니다.
들어가기
일반적으로 알고리즘을 설계할 때 우리는 온전한 입력을 가정합니다. 예를 들어, 두 지점 사이의 최단 경로를 구하기 위해서는 해당 지점 및 경유할 수 있는 지점, 그리고 지점 사이의 거리가 입력으로 몽땅 주어집니다. 하지만 컴퓨터가 다루어야 하는 모든 문제들이 위 특성을 가지는 것은 아닙니다. 어떤 경우에는 처음에 입력의 일부만 주어지고 나머지는 시간이 지나면서 조금씩 주어질 수 있습니다. 만약 시간의 제약이 없다면, 모든 입력이 들어올 때까지 기다린 후에 알고리즘을 수행하면 될 것입니다. 그렇지만 세상이 그렇게 만만하지만은 않습니다.
예를 들어보죠. 여러분은 어떤 회사에 취직을 했습니다. 아쉽게도 아직 자그마한 기업이라서 여러분에게 출퇴근 비용을 보전해주지는 못합니다만, 언젠간 회사의 사정이 나아지면 반드시 출퇴근 비용 전액을 지원하겠다고 합니다.(그냥 둘러대는 말이 아니라 진짜로 그렇다고 합시다.) 그 때문에 그동안 출퇴근할 방법을 찾아야 하는데, 걷기에는 너무 멀고 택시를 타기에는 돈이 부족해서 여러분은 자전거를 타기로 결정했습니다. 여러분에게는 두 가지 선택지가 있습니다. 하나는 하루 대여료 1,000 원으로 자전거를 대여하는 것입니다. 다른 하나는 100,000 원짜리 자전거를 구매하는 것입니다. 다만 자전거를 구매하면 이를 되팔 수 없다고 가정하겠습니다. 여기서 여러분의 목표는 당연히 회사 사정이 나아질 때까지 최소의 금액으로 회사에 출퇴근하는 것입니다.
만약 그때가 언제인지 확실히 알 수 있다면 이 문제는 쉽습니다. 회사가 100 일 전에 지원해주면 자전거를 대여하면 되고, 100 일보다 나중이라면 구매하는 것이 이득입니다. 하지만 우리는 미래를 알 방법이 없습니다.(물론 예측할 수야 있겠지만, 그렇다고 "확실하게" 아는 것은 아닙니다.) 자전거를 계속 대여해서 다니기로 결정했는데 한도 끝도 없이 회사의 사정이 나아지는 때가 오지 않을 수도 있고요, 반대로 자전거를 샀는데 당장 내일부터 출퇴근 비용 전액을 보전해줄 수도 있습니다. 현재의 과학 기술로는 미래에 가서 언제부터 금액 보전을 해주는지 알아 오는 것도 불가능합니다. 그렇다고 어떻게 얻은 직장인데 출근을 안 할 수도 없습니다. 과연 어떻게 하는 것이 좋은 선택일까요? 사실 이 문제는 기초적인 온라인 문제 중 하나인 스키 대여 문제(ski rental problem)입니다. 이는 다음 포스트에서 좀 더 자세히 다루어 보도록 하겠습니다.
비단 위 문제뿐 아니라 생각보다 많은 경우에 이러한 특성을 갖는 문제를 마주할 수 있습니다. 당장에 운영체제가 프로세스를 계획(schedule)할 때 운영체제의 입장에서는 어떤 프로세스가 언제 입력될지 모릅니다. 그렇다고 모든 프로세스가 들어올 때까지 기다릴 수도 없죠. 그렇게 했다가는 아무도 그 운영체제를 구입하지 않을 것입니다.
또, 컴퓨터는 CPU-메모리 통신을 줄이고 처리 능률을 높이기 위해 자주 사용되는 자료를 캐시(cache)에 둡니다. 여기서도 똑같은 문제가 발생합니다. 우리는 미래를 모르기 때문에 어떤 자료가 나중에 가장 많이 쓰일지 모른다는 것입니다. 물론 적은 수의 데이터가 독보적으로 많이 참조된다는 "reference locality"라는 법칙이 있지만, 이것이 항상 통한다는 법은 또 없죠. 진짜 최악의 경우에는 어느 시점을 기준으로 앞에서 가장 자주 등장한 데이터가 그 시점 이후에는 전혀 참조되지 않을 수 있습니다.
시스템 분야를 벗어나더라도 이러한 특성을 고려하는 것은 여전히 중요합니다. 유명한 예시를 들어보겠습니다. 네이버나 다음과 같은 포탈 회사들은 광고를 통해 수익을 창출합니다. 여러 광고가 있겠지만 가장 전통적인 방식 중 하나는 사용자가 특정한 검색어를 입력했을 때 그에 관련된 광고를 결과 페이지에 끼워서 보여주는 것입니다. 광고주들은 자신들과 관련된 특정 검색어를 미리 정하고 자신들의 광고가 게재되면 광고비를 포탈 회사에 지불합니다. 그런데 예를 들어 "가젤"이라는 검색어에 100 개의 기업이 경쟁하고 있다고 해보죠.(흠흠.) 여러분이 어떤 포탈에 "가젤"이라는 단어를 쳤는데 광고가 100 개가 나온다면 여러분은 그 포탈을 이용하실 건가요? 아무래도 좀 그렇겠죠? 때문에 포탈 회사는 사용자가 검색어를 입력했을 때 관련 회사의 광고 중 몇 개만을 보여줄 것입니다. 여기서 함께 고려해야 할 점은 회사마다 광고 예산이 정해져 있어서 자신들의 광고를 무제한 게재할 수도 없다는 점입니다.
여기서 포탈 회사는 비슷한 상황에 직면하게 됩니다. 포탈 회사는 미래에 어떤 검색어가 입력될지 모릅니다. 광고주들은 예산이 한정되어 있습니다. 따라서 광고를 아무렇게나 게재했다가는 어떤 광고주는 예산이 아직 많이 남아 있는데 다른 어떤 광고주의 여윳돈은 부족해질 수 있습니다. 그러면 나중에 들어온 검색어에 대해서 관련된 광고주들의 예산이 부족해서 광고를 싣지 못할 수도 있습니다.(무상으로 게재하는 일은 없다고 합시다.) 그렇다고 사용자가 검색했을 당시보다 나중에 광고를 보여줄 수도 없는 노릇입니다. 이미 사용자는 결과 페이지를 떠났을 가능성이 다분하기 때문이죠. 따라서 어떤 검색어가 들어왔을 때 가능한 광고 중 어떤 것을 게재하는지가 회사의 수익에 큰 영향을 주게 됩니다. 당연히 포탈 회사는 수익을 최대화하는 방향을 찾을 것입니다. 이 문제는 online bipartite matching의 변종 중 하나인 애드워즈 문제(Adwords problem)를 나타낸 것입니다. 이것도 나중에 기회가 되면 다루어 보도록 하겠습니다.
개념 정의
위에서 살펴본 대로 맨 처음에 모든 입력이 아닌 일부만 주어지고 시간이 지나면서 새로운 입력이 부분 부분 차례로 주어지는 문제를 온라인 문제(online problem)라고 하며, 새 입력이 도착할 때마다 매번 결과를 출력하는 알고리즘을 온라인 알고리즘(online algorithm)이라고 부릅니다. 대개의 경우 온라인 알고리즘은 이전 시간에 결정한 사항을 번복할 수 없습니다. 위의 자전거 대여/구매 예시에서 한번 자전거를 구매하면 다시 되팔 수 없는 것처럼 말이죠. 이러한 비번복성(irrevocability)은 애드워즈 문제에서도 두드러지게 드러납니다. 사용자가 어떤 검색어를 입력하면 그에 맞는 광고가 그때 딱 나타나야 합니다. 이를 나중에 번복할 수는 없습니다. 과거에 이미 게재한 광고를 내리고 다른 광고를 띄우는 것은 어불성설입니다.
그러면 온라인 알고리즘의 성능은 어떻게 판단할까요? 어떤 알고리즘이 좋은 알고리즘일까요? 당연히 최적값에 근사하는 값을 갖는 solution을 출력하는 알고리즘이 좋은 알고리즘이 될 것입니다. 하지만, 알고리즘의 입장에서는 언제 입력이 끝나는지 알기 어렵습니다. 또한, 어느 시점까지 받은 입력이 동일하다고 하여 그 이후에도 동일한 입력이 들어올 것이라는 보장도 없습니다. 따라서 알고리즘은 가능한 모든 시나리오에 대해서 좋은 "근삿값"을 갖는 solution을 출력해야 할 것입니다. 이를 온라인 알고리즘의 경쟁성(competitiveness)이라고 하며, 그 성능은 다음과 같은 정의로 규정합니다.
정의 1. \(\rho\)-competitive algorithm
어떤 online minimization[ㄱ] problem에 대하여, 어떤 입력 \(I\)의 최적값을 \(\mathsf{OPT}(I)\)라고 하자. 임의의 모든 입력 \(I\)에 대해 \[\rho \mathsf{OPT}(I) + c\]를 넘지 않는 값의 solution을 출력하는 알고리즘을 \(\rho\)-competitive algorithm이라고 부르며 \(\rho\)는 알고리즘의 경쟁비(competitive ratio)라고 부른다. 이때, \(c\)는 입력 \(I\)와는 무관한 고정된 상수이며, \(c = 0\)인 경우에는 알고리즘이 strictly \(\rho\)-competitive 하다고 부른다.
온라인 문제에서 임의의 입력은 강력한 의미를 지닙니다. 새로운 입력이 들어오는 때마다 가능한 입력 중 하나가 되기 때문입니다. 앞에서 본 자전거 대여/구매 예시에서 알고리즘이 9 일째에 대여를 할지 구매를 할지 결정해야 할 때, 다음날인 10 일째에 회사의 지원이 시작될지 아니면 한참 뒤인 150 일째부터 시작될지 9 일째에는 알 수 없습니다. 전자는 그동안 대여를 하는 것이 이득이며, 후자는 첫날 구매를 하는 것이 이득이지만, 두 경우 모두 가능한 입력이기 때문에 알고리즘은 두 경우 모두에 대해서 "경쟁적인" solution을 출력해야 합니다. 따라서 위 competitive algorithm의 정의가 곧 새 입력이 들어오는 때마다 좋은 solution을 유지한다는 의미를 내포합니다.
상대방 상정하기
온라인 문제 및 알고리즘의 특성을 통해 우리는 알고리즘의 경쟁성을 분석하는 것을 상대방(adversary)을 상정한 일종의 "게임"으로 생각할 수 있습니다. 여러분은 알고리즘의 편이라고 하겠습니다. 새로운 입력이 들어올 때마다 매번 여러분과 상대방 모두 feasible solution을 출력해야 합니다. 다만 안타깝게도 이 게임은 매우 "불공평"한 게임입니다. 상대방은 어떤 입력이 들어올지 이미 모두 알고 있습니다. 따라서 입력이 모두 들어왔을 때, 상대방은 항상 optimal solution을 출력할 것입니다. 하지만 여러분은 상대방이 어떤 선택을 했는지 모릅니다. 여러분의 목표는 이런 상대방에 맞서 상대방이 출력하는 solution에 최대한 경쟁적인 solution을 출력하는 것입니다.
이렇게 불공평한 상대방을 상정하는 이유는 이것을 통하여 온라인 알고리즘의 경쟁성을 보일 수 있기 때문입니다. 만약 임의의 상대방에 대해서 그 상대방이 최종적으로 출력한 solution의 값을 \(\mathsf{ADV}\)라고 했을 때, 여러분의 알고리즘이 \(\rho \mathsf{ADV} + c\) 이내의 값을 갖는 solution을 출력한다면 이 알고리즘은 \(\rho\)-competitive algorithm이 됩니다. 왜냐하면 상대방은 항상 optimal solution을 출력할 것이고, 여러분은 상상할 수 있는 모든 상대방에 대해 그 상대방이 출력하는 solution에 크게 뒤처지지 않는 solution을 제시하기 때문입니다.
이미 여기까지만 생각해도 충분히 불공평하다고 느끼시겠지만, 우리가 상정하는 상대방에도 급이 나뉩니다. 가장 부조리한 상대방은 바로 여러분이 어떤 선택을 했는지를 훔쳐보는 상대방입니다. 여러분은 상대방이 어떤 선택을 하는지 보지 못하는데도 말입니다! 한 술 더 떠서 이 상대방은 이후의 입력도 자신이 직접 만들어 냅니다. 이 정도면 심판을 매수한 격이라고 할 수 있겠네요. 이러한 상대방을 우리는 적응형 상대방(adaptive adversary)[ㄴ]이라고 부릅니다.
반면, 이보다는 양심적인(?) 상대방도 있습니다. 이 상대방은 이미 주어진 입력에 대해서 그저 optimal solution을 출력하기만 합니다. 게다가 이 상대방은 여러분이 어떤 선택을 하는지 보지 못합니다. 적응형 상대방에 비해서는 매우 양반이라고 할 수 있겠죠. 우리는 이러한 상대방을 무지각형 상대방(oblivious adversary)이라고 말합니다. 참고로 적응형/무지각형 상대방은 제가 임의로 번역한 것임을 알립니다.
이렇게 상대방의 급을 나눈 이유는 무엇일까요? 딱 보아도 무지각형 상대방보다 적응형 상대방이 훨씬 강력할 것 같습니다. 반대로 여러분의 입장에서 얘기하면 무지각형 상대방보다 적응형 상대방을 상대할 때 여러분의 입지가 훨씬 줄어든다는 것을 의미합니다. 이는 여러분의 알고리즘이 deterministic이냐 아니면 randomized냐에 따라서 두드러지게 차이가 나게 됩니다. 참고로 deterministic algorithm과 randomized algorithm에 관해서는 아래 포스트에서 자세히 다루었습니다.
2019/08/12 - [수학적 도구/Randomness] - 야오의 법칙 (Yao's Principle)
야오의 법칙 (Yao's Principle)
이번에는 Yao's principle에 대해서 알아보도록 하겠습니다. 이 글은 이전 포스트에서 이어지는 내용이 많으므로 이를 먼저 읽어 보시는 것을 추천드립니다. 또한 확률에 대한 기본적인 내용을 숙지하셨다는 가정..
gazelle-and-cs.tistory.com
쉽게 설명하면 deterministic algorithm은 동일한 입력에 대해서 동일한 결과를 출력하는 알고리즘이며, 반대로 randomized algorithm은 내부에 특정한 확률 분포가 있어 확률 시행에 따라 결과가 달라지는 알고리즘을 의미합니다. 이때 어떤 randomized online algorithm이 \(\rho\)-competitive 하다는 의미는 임의의 상대방에 대하여 알고리즘이 출력하는 solution의 기댓값이 \(\rho \mathsf{ADV} + c\) 이하라는 뜻입니다.[ㄷ]
먼저 여러분의 알고리즘이 deterministic algorithm인 경우부터 살펴보도록 하겠습니다. 만약 여러분의 알고리즘이 임의의 적응형 상대방에 대항하여 \(\rho\)-competitive 하다고 가정해 보겠습니다. 먼저 모든 무지각형 상대방은 일종의 적응형 상대방으로 볼 수 있으므로 여러분의 알고리즘은 임의의 무지각형 알고리즘에 대항해서 최소한 \(\rho\)의 경쟁비를 가지는 알고리즘임을 알 수 있습니다. 자 이제 아무 적응형 상대방을 가지고 와서 여러분의 알고리즘에 대해 똑같이 동작하는 무지각형 상대방을 만들어 봅시다. 여러분의 알고리즘은 deterministic 하므로 이 무지각형 상대방에 대항해서도 동일한 경쟁비의 solution을 출력할 것입니다. 따라서 우리는 쉽게 다음을 이끌어낼 수 있습니다.
정리 1. Deterministic algorithms against adversaries
만약 어떤 deterministic online algorithm이 임의의 적응형 상대방에 대항하여 \(\rho\)-competitive 하면, 그 알고리즘은 임의의 무지각형 상대방에 대항하여 \(\rho\)-competitive 하다.
이것이 의미하는 바는 우리가 어떤 deterministic algorithm의 경쟁성을 분석할 때는 적응형 상대방을 상정하여도 무지각형 상대방에 대항하였을 때와 동일한 경쟁비를 얻을 수 있다는 점입니다.
반대로 여러분이 randomized algorithm을 구현한 경우에는 어떤 상대방이냐에 따라서 차이가 납니다. 어느 정도 눈치는 채셨겠지만, 적응형 상대방에 대항해서는 randomized algorithm도 별 힘을 쓰지 못합니다. 왜냐하면 적응형 상대방은 알고리즘의 시행에 맞추어 입력을 바꿀 수 있기 때문입니다. 증명은 훨씬 복잡하지만, 다음 정리가 알려져 있습니다.[1]
정리 2. Randomized algorithms against adaptive adversaries
어떤 문제에 대해, 만약 임의의 적응형 상대방에 대항하여 \(\rho\)-competitive randomized algorithm이 존재하면, 그 문제에 대해 임의의 적응형 상대방에 대항하여 \(\rho\)-competitive deterministic algorithm도 존재한다.
하지만 무지각형 상대방에 대항해서는 다릅니다. 이 상대방은 알고리즘이 어떻게 동작하는지 전혀 모르기 때문에 알고리즘의 랜덤성에 대응할 수 없습니다. 따라서 어떤 온라인 문제에 대해, 그 문제를 해결하는 임의의 deterministic algorithm이 아무 무지각형 상대방에 대항해 \(\rho\)보다 좋은 경쟁비를 가질 수 없다는 것을 증명하였다고 한들, 그 문제를 푸는 임의의 randomized algorithm에 대해서도 \(\rho\)보다 좋은 경쟁비를 가질 수 없다는 것을 말해주지는 않습니다.
마치며
이번 포스트에서는 온라인 문제와 온라인 알고리즘에 대한 개괄적인 내용을 다루어 보았습니다. 가볍게(?) 정리하면, 다음과 같습니다.
- 온라인 문제(online problem)는 처음에 모든 입력이 아닌 일부만 주어지고 시간이 흐름에 따라서 새로운 입력이 조금씩 들어오는 문제를 일컬으며 온라인 알고리즘(online algorithm)은 새로운 입력이 들어올 때마다 feasible solution을 출력하는 알고리즘을 말합니다.
- 온라인 알고리즘의 성능을 평가하는 척도는 경쟁성(competitiveness)이며, 이는 매번 새로운 입력이 주어졌을 때 알고리즘이 (현재 입력의) 최적해의 (상수 오차를 포함한) 일정 배수 이내의 값을 갖는 solution을 출력하는 것으로 나타내어집니다.
- 온라인 알고리즘의 경쟁성을 분석하기 위해서 최적해를 출력하는 상대방을 상정하는 경우가 많으며, 상대방의 힘에 따라 크게는 알고리즘의 동작을 모두 관찰하고 이후의 입력을 원하는 대로 조정할 수 있는 적응형 상대방(adaptive adversary)과 알고리즘이 어떻게 동작하는지 모르고 주어진 고정된 입력에 대해 최적해를 출력하는 무지각형 상대방(oblivious adversary)으로 나뉩니다.
- 어떤 deterministic online algorithm을 분석할 때는 적응형 상대방을 상정하여도 무지각형 상대방에 대해서 동일한 경쟁비를 얻을 수 있지만, 어떤 randomized online algorithm을 분석할 때는 무지각형 상대방을 상정하는 것이 일반적입니다.
모두 쓰고 나니 꽤 긴 글이 되어버렸군요. 이렇게 길어질 것이라고는 예상하지 못하였습니다. 더구나 이번 포스트에는 그림 설명이 없고 몽땅 글로만 설명이 되어 있어서 더욱 지루할 수도 있겠다 생각합니다. 하지만 반대로 얘기하면 이 분야가 그만큼 깊고도 잘 연구된 학문이라는 방증이라고 생각합니다. 또 이러한 분야를 얕게 공부하고 섣불리 글을 게재한 스스로가 부끄럽기도 합니다. 지금 이 포스트에서도 여전히 제가 잘못 이해하고 있는 것이 있을 수 있습니다. 혹시 그러한 부분이 있으면 언제든지 댓글로 알려주시기 바랍니다. 고맙습니다.
참조 문헌
[1] Shai Ben-David, Allan Borodin, Richard Karp, Gabor Tardos, and Avi Wigderson. On the power of randomization in on-line algorithms. Algorithmica 11(1):2-14, 1994.
[2] Niv Buchbinder and Joseph (Seffi) Naor. The design of competitive online algorithms via a primal–dual approach. Foundations and Trends® in Theoretical Computer Science 3(2–3):93-263, 2009.
주석
[ㄱ] 당연히 maximization problem에 대해서도 비슷한 정의를 내릴 수 있습니다. 임의의 모든 입력 \(I\)에 대해서 알고리즘이 \(\rho \mathsf{OPT}(I) - c\)보다 크거나 같은 값을 갖는 solution을 출력하면 이를 \(\rho\)-competitive algorithm이라고 부릅니다. 이때, \(c\)는 똑같이 입력과는 관련이 없는 음이 아닌 고정된 상수입니다. 논문에 따라서는 \(\frac{\mathsf{OPT}(I)}{\rho} - c\)를 \(\rho\)-competitive algorithm으로 정의하기도 합니다. 이때 첫 번째 정의에서는 \(\rho \leq 1\)이 되며, 두 번째에서는 \(\rho \geq 1\)이 됩니다. 예를 들어 첫 번째 정의를 따르면 \(\frac{1}{2}\)의 경쟁비를 갖는 알고리즘은 두 번째 정의에 따르면 \(2\)의 경쟁비를 갖습니다.
[ㄴ] 사실 본문에서 소개한 적응형 상대방은 adaptive offline adversary입니다. 이 상대방은 알고리즘이 지금까지 어떻게 동작하였는지 모두 참조할 수 있으며, 이에 맞추어 이후의 입력을 만들어 냅니다. 게다가 이 상대방이 동작하는 방식은 입력이 끝나지 않는 동안에는 아무것도 출력하지 않고 마지막에 최종 입력의 optimal solution을 출력하고 끝납니다. 별개로 이 상대방보다 약간 약한 adaptive online adversary도 있습니다. 이 상대방도 알고리즘이 지금껏 어떻게 동작하였는지를 참조할 수 있고 이에 따라서 이후의 입력을 만들어 냅니다. 다만, 위 상대방과 다른 점은 매 순간 알고리즘처럼 적절한 solution을 출력하여야 합니다. 게다가 매 순간 이 상대방도 출력해야 하므로 최종 solution의 값 \(\mathsf{ADV}\)가 최종적으로 만들어진 입력 \(I\)의 최적값 \(\mathsf{OPT}(I)\)와 다를 수도 있습니다. 자세한 사항은 Ben-David et al.[1]을 참조하시기 바랍니다.
[ㄷ] 무지각형 상대방의 경우에는 randomized algorithm의 시행에 영향을 받지 않으므로 기댓값을 취할 필요 없이 \(\mathsf{ADV}\)가 그대로 유지됩니다. 하지만 적응형 상대방의 경우에는 확률 시행에 따라 만들어지는 입력에 영향을 받게 됩니다. 따라서, 엄밀히 정의하면 임의의 적응형 상대방에 대항하여 solution의 기댓값이 \(\rho \cdot \mathbb{E}[\mathsf{ADV}] + c\)를 넘지 않을 때 비로소 임의의 적응형 상대방에 대항해 \(\rho\)-competitive 하다고 말할 수 있습니다. 정리 2에 따르면 adaptive offline adversary에 대항해서는 randomness가 도움이 되지 않습니다. 하지만, adaptive online adversary에 대항해서는 여전히 유효하므로 위 정의가 가치가 없지는 않습니다.
'온라인 알고리즘 > Basic' 카테고리의 다른 글
| 동적, 스트리밍, 온라인 알고리즘 비교 (Dynamic, Streaming, and Online Algorithm) (0) | 2021.01.16 |
|---|
