Online 알고리즘 (4) - Randomized Online Algorithms (1)

이번 포스팅에서는 온라인 알고리즘을 푸는데 있어서 randomness가 어떻게 영향을 끼치는지 정리해보도록 하겠습니다. 우선 randomized 온라인 알고리즘을 정리하려면 기존 deterministic 온라인 알고리즘에서 다음과 같은 몇가지 확장이 필요합니다. 

 

• competitive ratio
• type of adversaries and relationship

Randomized 온라인 알고리즘에서는 competitve ratio를 측정하는 것은 Randomness가 3가지의 adversaries를 허용하기 때문에 deterministc 온라인 알고리즘과 상이합니다. Randomness 온라인 알고리즘에서 adversary는 3가지 유형으로 oblivious(망각형), adaptive online (적응형-온라인) 그리고 adaptive offline (적응형-오프라인) 입니다. 그리고 이 유형들의 관계와 competitve ratio들을 다뤄보도록 하겠습니다.

 

Randomized 온라인 알고리즘의 기본적인 템플릿을 정리해보도록 하겠습니다. 우선 randomness와 관련된 표기를 정의하겠습니다. 랜덤변수는 대문자로 하고 소문자입니다. 예를 들어, 파라미터 $p$의 확률로 1의 값을 갖는 베르누이 분포 $B$라고 한다면, $b$는 베르누이 분포에서 샘플링된 결과값이고 $b \in \{0,1\}$를 만족하겠습니다.

 

Randomized 온라인 알고리즘은 랜덤을 통해서 determinstic 온라인 알고리즘과 달라집니다. 다시 말해, randomized 알고리즘은 일련의 인풋 $x_i$를 받고 특정한 랜덤한 결정을 합니다. 이 때, 이전에 들어온 모든 인풋 $x_1, ..., x_i$와 랜덤 bit $R_i \in \{0, 1\}, i\ge 1$에 기반한 결정을 내리게 됩니다. 랜덤 R은 Gaussian, Binomial, Bernoulli, exponential등 합리적인 random variable 모델이 될 수 있습니다. 하지만 우리가 분석을 하면서 특정한 랜덤 변수를 샘플링하는 디테일은 스킵을 할 것입니다. 결국, $R$이 고정이 고정된 바이너리 문자열인 $r\in {\{0,1\}}^N$이라면 결정 $D$는 deterministic이 될 것입니다. 결국 우리는 randmonized 알고리즘 $ALG$는 determinstic 알고리즘 $ALG_r$의 분포라고 할 수 있습니다. 

 

Types of Adversaries

온라인 알고리즘을 실행하는 과정은 상대방(adversary)와의 게임이라는 관점으로 바라볼 수 있습니다. 

각각의 deterministic 케이스에서는 adversary는 한 종류만 있었습니다. 하지만 randomized 케이스에서는 우리는 앞서 언급했다시피 adversary가 다음 input을 만드는데 필요한 정보의 범위에 따라서 다음 3가지 타입으로 나타낼 수 있습니다.

 

망각형 adversary

이 경우가 가장 쉬운 adversary입니다. 오로지 알고리즘대로만 작동하며, 어떠한 randomness의 영향도 받지 않습니다. 말하자면 일련의 인풋 $x_1,...,x_n$ 만을 생성하고 랜덤분포 $D_1,D_2,...D_n$을 알고 있지만 온라인 알고리즘이 만들어 내는 결정들에 대한 학습은 존재하지 않습니다. 목적함수가 $OBJ(x_1,...x_n,d_1,...d_n)$이라고 합시다. 그렇다면 알고리즘의 퍼포먼스는 목표함수의 기대값들과 오프라인 최적해의 비로 다음과 같이 나타낼 수 있습니다.

$$ \frac{E_{D_1,...D_n}(OBJ(x_1,...x_n,d1,...d_n)}{OPT(x1,...x_n)}$$

 

적응형-오프라인 adversary

가장 강력한 adversary 타입입니다. 알고리즘과 online 결정들을 이용하여 다음 인풋을 생성합니다. 다음과 같이 재귀적인 연쇄작용을 통해서 $x_i = x_i(x_1,d_1,...,x_{i-1},d_{i-1})$을 생성합니다. 알고리즘의 퍼포먼스는 모든 결정들의 최적해의 기대값과의 비율로 정의할 수 있습니다.

$$ \frac{E_{D_1,...D_n}(OBJ(x_1,...x_n,d1,...d_n)}{E_{D_1,...D_n}(OPT(x1,...x_n))}$$

 

적응형-온라인 adversary

중간등급의 adversary입니다.  이 타입은 $x_1$ 인풋을 생성하고 그것에 대한 자기 자신의 결정 $ \dot{d}_1$를 합니다. 그리고 알고리즘이 랜덤한 결정 $D_1$을 하고 결과 $d_1$을 adversary에게 알려줍니다. 그리고 adversary는 $x_2$와 자기 자신의 결정 $ \dot{d}_2$를 합니다. 이런식으로 계속 반복되게 됩니다. 우리는 적응형-온라인 adversary가 알고리즘의 전 결정에 기반하여 다음 인풋을 만든다고 할 수 있지만, 사실 input은 온라인으로 바로 만들어져야합니다. 즉, adversary 또한 최적의 퍼포먼스를 보여주는 것은 아니죠. 그러므로 알고리즘의 퍼포먼스는 adversary가 온라인으로 생성한 목적함수의 값과 알고리즘의 목적함수의 값의 비와 같습니다.

$$ \frac{E_{D_1,...D_n}(OBJ(x_1,...x_n,d1,...d_n)}{E_{D_1,...D_n}(OBJ(x1,...x_n,\dot{d}_1,...\dot{d}_n))}$$

 

가장 대표적인 adversary를 망각형 adversary입니다. 우리가 radomized 온라인 알고리즘을 분석할 때에도 대부분 망각형 adversary를 산정한다고 가정합니다. 이유는 가장 실용적인 관점으로 접근할 수 있기 때문입니다. 예를 들어, ski-rental 문제같은 경우에서는 randomness가 상관이 없듯이 많은 여러 문제에서도 영향을 끼치지 않는 경우가 많습니다. 하지만, 알고리즘이 미래의 인풋에 영향을 끼치는 결정을 하는 문제들도 있습니다. 대표적으로 페이징 문제입니다. 이는 차후의 포스팅에서 정리해보도록 하겠습니다. 다음 포스팅에는 randomness가 알고리즘 분석에 어떻게 영향을 끼치는지 정리하도록 하겠습니다.