Loading [MathJax]/jax/output/CommonHTML/jax.js
본문 바로가기

알고리즘/online algorithm

Online 알고리즘 (5) - Randomized Online Algorithms (MBG 문제)

이번 포스팅에서는 Modified Bit Guessing Problem (이하 MBG 문제) 에 대하여 randomness가 deterministic 알고리즘에 어떤 영향을 끼치는지 알아보도록 하겠습니다. MBG 문제는 다음과 같이 정의할 수 있습니다. 

 

2명의 사람이 게임을 한다고 합시다. 한 사람이 n개의 비트의 나열 패턴을 정합니다. 그리고 다른 한 사람은 그 비트를 하나씩 들으면서 다음에 어떤 비트가 올 지 맞추는 게임입니다. 즉, 다음 비트가 0일지 1일지 과거 비트의 패턴을 보고 맞춰야 합니다. 목표는 하나라도 맞추는 것입니다. 맞춘다면 점수를 g(n)/(11/2n1)를 얻고 모두 틀린다면 1 만큼 점수를 얻습니다. 

 

우선 직관적으로 이 게임에 대해서 해석해봅시다. 만약 비트의 나열 패턴을 정하는 사람이 맞추는 사람의 정답을 듣고 다음 비트를 정하면 어떻게 될까요? 당연히 아무것도 못맞추도록 할 수 있습니다. 그저 0을 말하면 1을 말하면 되고 1을 말하면 0을 말하면 그만입니다. 이러한 상황은 deterministic 알고리즘에 대해 간단한 알고리즘만으로 adversary가 대응할 수 있다고 할 수 있습니다. 하지만 만약 응답에 상관없이 정해둔 패턴을 말하는 양심적인 사람(?)이라면 어떻게 될까요? 총 n1번의 매칭에서 적어도 한번은 맞출 확률이 11/2n1이므로 g(n)/(11/2n1)(11/2n1)=g(n)  점수를 얻을 것을 기대할 수 있습니다. 이는 randomized 알고리즘에 대해서 망각형 adversary는 대응할 수 없음을 알 수 있습니다. 그리고 이를 봤을 때, 우리는 randomness가 adversary와의 일종의 게임에서 더 유리해질 수 있음을 직관적으로 알 수 있습니다. 그렇다면 Proportional Knapsack 문제에 대한 분석을 정리해보도록 하겠습니다.

 

W만큼 담을 수 있는 배낭이 있고 w1,...,wn의 무게를 가지고 있는 n개의 보석이 있습니다. 그리고 무게를 하나씩 듣고 그 보석을 배낭에 담을지 안담을지 결정합니다. 즉, ni=1ziwi<=W의 최대값을 만족하는 z1,...,zn,zi{0,1}을 구하면 됩니다. 다만 주의할 것은 절대로 총 무게W를 초과하면 안됩니다. 

 

배낭은 가장 큰 것을 챙기도록 합시다

우선 이 문제가 deterministic 알고리즘으로 상수의 competitive ratio를 구할 수 없다는 걸 봐야합니다. 

ρ(ALG)ϵ1ϵ,ϵ>0

 

우선 adversary의 전략을 생각해봅시다. W=n일 경우, 알고리즘이 처음으로 배낭에 챙기는 보석의 무게를 ϵn이라고 합시다. 만약 알고리즘이 하나도 안챙기면 총 보석은 0입니다. 챙긴다면 OPTϵn으로 competitve는 매우 커집니다. 만약 알고리즘이 wi=ϵn을 배낭에 챙긴다고 하면, adversary를 wi+1=n(1ϵ)+ϵ을 다음 보석으로 제시하고 다음부터는 다 0으로 제시합니다. 그렇다면 i+1번째 보석을 챙기면 무게를 초과하게 되므로 ALG=ϵn,OPT=n(1ϵ)+ϵ이므로 위 competitive ratio를 만족합니다.

 

그럼 randomized 알고리즘을 살펴봅시다. 간단하게 1 bit의 랜덤을 통해 competitive ratio 4의 알고리즘을 설계할 수 있습니다. 이 알고리즘은 2가지 모드의 동작으로 이루어져있습니다. 하나는 greedy하게 새로운 보석이 제시되면 알고리즘은 여유공간이 있는지 확인하고 배낭에 챙깁니다. 두번째 모드는 무게가 W/2인 보석을 제시받을 때까지 기다립니다. 만약 그런 보석을 제시받으면 배낭에 챙깁니다. 랜덤을 통해 이 2가지 모드 중 하나를 동작하는 알고리즘입니다. 

 

그럼 다음을 2가지 모드를 나누어 각각 증명을 해보도록 하겠습니다. 

 

OPT4E(ALGsimple)

 

첫번째 경우는 모든 보석의 무게가 wi<W/2인 경우입니다. ni=1ziwi<=W라고 하면 절반의 확률로 첫번째 모드를 실행하고 알고리즘은 모든 보석을 챙길 것 입니다. 따라서 E(ALGsimple)1/2wi입니다. 결국  OPT2E(ALGsimple) 를만족합니다. 만약 ni=1ziwi>W일 경우에는 첫번째 모드에서 챙기지 못하는 보석들이 있을 수 있습니다. wi를 챙기지 못하는 보석 중 첫번째라고 하고 wi<W/2라고 한다면 이 알고리즘은 적어도 W/2만큼은 배낭에 챙긴거라고 할 수 있습니다.

결국 E(ALGsimple)(1/2)(w/2)이므로 OPT4E(ALGsimple)를 만족합니다.

 

두번째 경우는 보석의 무게가 wiW/2인 보석이 있는 경우입니다. 2번째 모드는 wiW/2일 때, 보석을 배낭에 챙길 것이고 그러면 E(ALGsimple)(1/2)(w/2)이므로 OPT4E(ALGsimple)를 만족합니다. 이로써 우리는 모든 경우의 competitive ratio가 4임을 알 수 있습니다.

 

이번 포스팅에서는 randomness가 알고리즘에 어떤식으로 영향을 끼치는지 살펴보았습니다. randomness는 deterministic 알고리즘으로 풀 수 없는 어려운 문제에 대해서 좋은 radomized 알고리즘을 만들 수 있게 해줍니다. 하지만 사실 randomness는 실제로 굉장히 비싼 자원입니다. 완벽에 가까운, 패턴이 전혀 없는랜덤한 비트는 간단하게 만들 수 없습니다. 그래서 randomness에 대한 의존성을 없애려고 합니다. 이를 "derandomized"라고 하며, computational 모델에 따라 derandomized가 가능한지 결정할 수 있습니다. 예를 들어, 망각형 adversary를 상대로는 불가능하지만(물론 특정 constraint의 문제에 대해서는 가능할 수 있습니다) 적응형-오프라인 adversary에게는 가능합니다. 이는 어떤 경우가 있는지 아직 모르는 미지의 영역이기 때문에 나중에 알게되면 다루도록 하겠습니다.