온라인 문제(online problem)의 대표격인 스키 대여 문제(ski rental problem)는 지난 수십 년간 깊이 그리고 널리 연구되어 온 매우 유서 깊은 문제입니다. 제 블로그에서도 비중 있게 다룬 적이 있는데요. 문제는 다음과 같이 정의됩니다. 우리는 스키장이 문을 닫을 때까지 스키를 타고 싶어 합니다. 스키를 타는 방법은 두 가지로, 하나는 1 원으로 스키를 하루 대여하는 것이고, 다른 하나는 \(B\) 원으로 스키를 구매하는 것입니다. 당연히 언젠가 스키를 대여하면 다음날에는 또 스키를 대여하든지 구매하든지 하여야 하며, 언젠가 스키를 구매하면 더 이상 그런 고민을 할 필요가 없어집니다. 이때 최소의 비용으로 스키장이 문을 닫을 때까지 스키를 타는 것이 문제의 목표입니다.
만약 스키장이 언제 닫는지를 알면 우리는 쉽게 문제를 해결할 수 있습니다. 폐장하는 때가 \(B\) 번째 날보다 이전이라면 매번 대여를 하는 것이 최선입니다. 반대로 그보다 이후라면 첫 날에 스키를 구매하는 것이 최선이죠. 하지만 이 문제가 어려운 이유는 언제 스키장이 닫는지 사전에 알 수 없다는 것에 있습니다. 오래 탈 수 있을 것 같아서 첫 날에 덜컥 스키를 구매하였는데 며칠 지나지 않아 폐장할 수도 있습니다. 그 걱정에 스키를 계속 대여를 하자니 하염없이 계속 개장할 수도 있습니다.
그러므로 모든 상황에 대비하기 위해서는 처음 며칠 간은 빌리다가 언젠가 구매를 하는 것이 합리적인 전략이 될 것입니다. 실제로 이전 포스트에서 우리는 \(B\) 번째 날이 오기 전까지는 대여를 하다가 \(B\) 번째 날에 구매를 하는 방법이 스키장이 언제 폐장하든지 간에 항상 최적 비용의 최대 두 배만 부과한다는 사실을 배웠습니다. 추가적으로 우리는 이 방법이 결정론적 알고리즘(deterministic algorithm)으로 얻을 수 있는 최선(best possible)의 결과라는 사실도 공부하였습니다. 관련 내용이 궁금하시면 이전 포스트를 참고하시기 바랍니다.
[스키 대여 문제 / Ski Rental Problem] 문제 정의 & Break-Even Algorithm
이번 포스트에서는 기초적인 온라인 문제 중 하나인 스키 대여 문제(ski rental problem)를 다루어 보도록 하겠습니다. 온라인 문제 및 온라인 알고리즘이 무엇인지는 이전 글을 참조해 주시기 바랍
gazelle-and-cs.tistory.com
어떤 상황에서도 좋은 경쟁비로 문제를 해결할 수 있다는 것은 매우 고무적인 일이지만, 최악의 경우에는 그보다 좋은 경쟁비를 가질 수 없다는 사실은 아쉬운 일입니다. 하지만 그러한 부정적인 결과는 알고리즘이 스키장이 언제 폐장하는지 전혀 모른다는 가정을 악용하여 얻은 것으로써 현실성이 지극히 떨어지는 일입니다. 일기 예보를 생각해 봅시다. 우리는 과거의 기상 데이터를 토대로 미래의 날씨를 완벽하지는 않지만 합리적인 수준으로 예측해 냅니다. 이와 같이 많은 경우 우리는 완전히 믿을 수는 없지만 어느 정도는 신뢰할 만한 예측치를 생성할 수 있는 능력이 있습니다. 이 논의를 스키 대여 문제에 적용하면 우리는 다음과 같은 질문을 떠올릴 수 있습니다.
완전히 믿을 수는 없지만 예상 폐장일이 주어졌을 때 더 좋은 경쟁비로 문제를 해결할 수 있는가?
예상 폐장일이 주어졌을 때 문제를 어떻게 풀 수 있을지 생각해 봅시다. 먼저 예상 폐장일이 정말로 실제 폐장일과 동일할 수 있습니다. 다시 말해, 오차가 전혀 없는 상황인 것이죠. 이때 우리가 처음부터 예상 폐장일을 믿는다면 기존의 경쟁비보다 더 좋은 경쟁비의 알고리즘을 얻을 수 있을 것입니다. 반면 예상 폐장일이 실제 폐장일을 전혀 반영하지 못해 오차가 큰 상황도 발생할 수 있습니다. 이때 예상 폐장일을 너무 믿었다가는 조악한 결과를 얻겠죠. 따라서 우리의 알고리즘은 다음 두 상황에 적절히 균형을 유지하면서 동작해야 합니다.
- 예측이 매우 정확한 경우에는 좋은 품질의 답을 출력해야 한다.
- 예측이 부정확한 경우에도 합리적인 수준의 답은 보장해야 한다.
과연 어떻게 하면 예측치를 활용하여 위 상황에서 모두 경쟁적으로 동작하는 알고리즘을 얻을 수 있을까요? 이번 포스트에서는 이에 대해서 공부해 보도록 하겠습니다.
문제 정의
이번 글에서 해결하려는 문제를 엄밀하게 정의하여 보겠습니다. 우리는 어떤 스키장에 스키를 타러 왔습니다. 스키를 타는 방법은 두 가지로 하나는 1의 비용으로 하루 대여하는 것이고, 다른 하나는 \(B\)의 비용으로 구매하는 것입니다. 스키장 폐장일은 \(t^\circ\) 번째 날이지만, 이는 우리가 모르는 값입니다. 대신 우리는 \(\bar{t}\) 번째 날에 스키장이 닫을 것이라는 예보를 들었습니다. 우리의 목표는 예상 폐장일을 활용하여 최대한 적은 비용으로 실제로 스키장이 폐장할 때까지 스키를 대여 혹은 구매하여 스키를 타는 것입니다.
알고리즘의 성능은 어떻게 표현할 수 있을까요? 앞에서 우리는 알고리즘이 상반되는 두 상황에 대해 균형을 유지해야 한다고 논의했습니다. 이를 위해서는 오차를 정의해야 합니다. 오차는 실제 폐장일과 예상 폐장일의 차이로 정의하겠습니다. 기호로는 \(\eta := \left| t^\circ - \bar{t} \right|\)라고 쓰겠습니다. 그러면 알고리즘의 성능을 다음의 두 기준으로 나타낼 수 있습니다.
- 일관성(consistency): 만약 \(\eta = 0\)일 때 알고리즘이 최적해의 \(\alpha\) 배 이내의 비용을 내는 답을 출력한다면, 이 알고리즘을 \(\alpha\)-일관(consistent) 알고리즘이라 부른다.
- 강건성(robustness): 임의의 \(\eta\)에 대해 알고리즘이 최적해의 \(\beta\) 배 이내의 비용을 내는 답을 출력한다면, 이 알고리즘을 \(\beta\)-강건(robust) 알고리즘이라 부른다.
참고로 이전 포스트에서 공부한 \(B\) 번째 날까지는 빌리고 그 다음 구매하는 2-경쟁(competitive) 알고리즘은 예상 폐장일에 상관 없이 임의의 \(\eta\)에 대해 항상 최적해의 두 배 이내의 비용의 답을 출력하므로 2-일관, 2-강건 알고리즘이라고 말할 수 있습니다.
강건비 \(\beta\)는 임의의 \(\eta\)에 대해 성립해야 하므로 기존의 경쟁비보다 좋을 수 없습니다. 따라서 결정론적 알고리즘으로는 2의 강건비를 갖는 것이 최선입니다. 하지만 일관성의 입장에서는 다릅니다. 정의 상 \(\eta = 0\)에 대해서만 좋은 결과를 내면 되므로 2보다 좋은 일관비 \(\alpha\)를 기대할 수 있습니다. 그러므로 우리의 목표는 2보다 더 좋은 일관비를 가지지만 강건비가 그렇게 나빠지지는 않는 알고리즘을 구하는 것입니다.
1-일관, \(\infty\)-강건 알고리즘
본 내용으로 바로 들어가기 앞서 다음의 간단한 알고리즘을 한번 생각해 봅시다.
만약 \(\bar{t} < B\)이면 끝날 때까지 스키를 빌리기만 한다. 반대로 \(\bar{t} \geq B\)이면 스키를 구매한다.
사실 이 알고리즘은 예측치 \(\bar{t}\)를 완전히 믿는 방법입니다. 실지로 오차가 없는 경우, 곧 \(\eta = 0\)이라면, 이 알고리즘은 최적해를 출력합니다. 하지만 예측치가 정확하지 않다면 어떻게 될까요? 다음과 같이 분석할 수 있겠습니다.
정리 1. 위 알고리즘의 비강건성
위 알고리즘은 최대 \(\mathsf{OPT} + \eta\)의 비용을 갖는 답을 출력한다.
[증명] 만약 \(\bar{t} < B, t^\circ < B\)이거나 \(\bar{t} \geq B, t^\circ \geq B\)라면, 알고리즘의 출력과 최적해가 동일합니다. 따라서 아래의 나머지 경우들에 대해서 위 명제가 성립함을 보이면 됩니다. 아래에서 알고리즘이 내는 비용을 \(\mathsf{SOL}\), 최적해의 비용을 \(\mathsf{OPT}\)라고 하겠습니다.
경우 1. \(\bar{t} < B, t^\circ \geq B\). 알고리즘은 끝날 때까지 스키를 빌리므로 \(\mathsf{SOL} = t^\circ\)임을 알 수 있습니다. 반면 \(\mathsf{OPT} = B\)입니다. \(\bar{t} < B\)라고 하였으므로, \( t^\circ + \bar{t} < t^\circ + B \)임을 압니다. 좌변의 \(\bar{t}\)를 우변으로 넘겨 정리하면, \[ \mathsf{SOL} = t^\circ < B + t^\circ - \bar{t} = \mathsf{OPT} + \eta \]를 이끌어 낼 수 있습니다.
경우 2. \(\bar{t} \geq B, t^\circ < B\). 알고리즘은 첫 날에 스키를 구매하므로 \(\mathsf{SOL} = B\)가 되지만 최적해는 매번 스키를 대여하는 것이므로 \(\mathsf{OPT} = t^\circ\)입니다. \(\bar{t} \geq B\)라고 하였으므로, \[ \mathsf{SOL} = B \leq \bar{t} + t^\circ - t^\circ = \mathsf{OPT} + \eta \]임을 이끌어낼 수 있습니다. ■
정리 1의 식을 통해 우리는 이 알고리즘이 오차가 매우 작은 경우, 예컨대 \(\eta \leq c \mathsf{OPT}\)인 경우에는 최적해의 \(1 + c\) 배 이내의 적은 비용을 갖는 해를 출력한다는 것을 알 수 있습니다. 하지만 오차가 매우 큰 경우에는 한도 없이 나쁜 답을 출력하게 됩니다. 따라서 이 알고리즘은 강건하다고 말할 수 없습니다.
\((1 + \lambda)\)-일관, \((1 + \frac{1}{\lambda})\)-강건 알고리즘
이전 절에서 소개한 알고리즘이 강건하지 못한 이유는 예상 폐장일을 너무 믿었다는 데에 있습니다. 예상 폐장일이 거의 올바른 경우에는 거의 최적해의 답을 출력했지만, 예측이 완전히 잘못된 경우에는 너무 많은 비용을 내야 했죠. 따라서 우리는 예측을 어느 정도까지는 믿다가 어느 때부터는 믿지 말아야 강건한 알고리즘을 얻을 수 있습니다. 이 아이디어를 확장하여 다음의 알고리즘을 생각해 보겠습니다. 이 알고리즘은 0과 1 사이의 어떤 \( \lambda \)에 의존합니다.
만약 \(\bar{t} < B\)라면, \(\left\lfloor \frac{B}{\lambda} \right\rfloor\) 번째 날까지 빌린 후 그다음 날에도 여전히 스키장이 열면 스키를 구매한다.
만약 \(\bar{t} \geq B\)라면, \(\left\lfloor \lambda B \right\rfloor\) 번째 날까지 빌린 후 그다음 날에도 여전히 개장하면 스키를 구매한다.
직관적으로 말해 \(\lambda\)는 예상 폐장일을 얼마나 믿을지에 대한 믿음의 정도를 나타냅니다. 만약 \(\lambda = 0\)이라면 이 알고리즘은 이전 절에서 살펴본 1-일관 알고리즘과 동일합니다. 반대로 \(\lambda = 1\)이라면 이 알고리즘은 곧 이전 포스트에서 공부한 2-경쟁 알고리즘과 동일합니다. 따라서 \(\lambda\)의 값이 작을수록 예측값을 더 믿겠다는 의미입니다.
이제 이 알고리즘을 분석해 보겠습니다. 먼저 이 알고리즘이 일관적이라는 것부터 보이겠습니다.
정리 2. 위 알고리즘의 일관성
위 알고리즘은 최대 \((1 + \lambda) \cdot (\mathsf{OPT} + \eta)\)의 비용을 갖는 답을 출력한다.
[증명] 정리 1의 증명에서와 마찬가지로 이 알고리즘의 출력의 비용을 \(\mathsf{SOL}\), 최적해의 비용을 \(\mathsf{OPT}\)라고 부르겠습니다. 만약 \(\bar{t} < B, t^\circ < B\)라면, 이 알고리즘은 최적해를 출력합니다. 또한 만약 \(\bar{t} \geq B, t^\circ \geq B\)라면, \(\mathsf{SOL} = \left\lfloor \lambda B \right\rfloor + B\)이고 \(\mathsf{OPT} = B\)이므로 정리의 명제가 쉽게 성립함을 알 수 있습니다. 나머지 두 경우는 따로 보이겠습니다.
경우 1. \(\bar{t} < B, t^\circ \geq B\). 이때 \(\mathsf{OPT} = B\)입니다. 먼저 \( B \leq t^\circ \leq \left\lfloor \frac{B}{\lambda} \right\rfloor \)인 때를 생각해 봅시다. 그러면 알고리즘은 빌리기만 하고 끝나므로 \(\mathsf{SOL} = t^\circ \)를 만족합니다. \(\bar{t} < B\)라고 하였으므로 \( t^\circ + \bar{t} < t^\circ + B \)임을 이끌어 낼 수 있습니다. \(\bar{t}\)를 우변으로 넘겨 정리하면 \[ \mathsf{SOL} = t^\circ < B + t^\circ - \bar{t} = \mathsf{OPT} + \eta \]가 됩니다.
이제 \(t^\circ > \left\lfloor \frac{B}{\lambda} \right\rfloor\)일 때를 생각해 봅시다. 알고리즘이 내는 비용은 \( \mathsf{SOL} \leq \frac{B}{\lambda} + B \)를 만족함을 쉽게 알 수 있습니다. 또한 \(t^\circ\)가 자연수라는 사실과 버림의 성질에 의해 \( t^\circ \geq \frac{B}{\lambda} \)임을 압니다. 이 사실에 \(\bar{t} < B \)를 엮으면 \[ \frac{B}{\lambda} < t^\circ +B - \bar{t} = \mathsf{OPT} + \eta \]를 이끌어 낼 수 있습니다. 양 변에 \(1 + \lambda\)를 곱하면 앞의 \(\mathsf{SOL}\)에 대한 식과 함께 \[ \mathsf{SOL} \leq \frac{B}{\lambda} + B = (1 + \lambda) \frac{B}{\lambda} < (1 + \lambda) \cdot (\mathsf{OPT} + \eta) \]를 얻습니다.
경우 2. \(\bar{t} \geq B, t^\circ < B\). 이 경우 \(\mathsf{OPT} = t^\circ\)입니다. 만약 \(t^\circ \leq \left\lfloor \lambda B \right\rfloor \)를 만족한다면 알고리즘은 최적해를 출력합니다. 남은 경우는 \(\left\lfloor \lambda B \right\rfloor < t^\circ < B\)인 때입니다. 알고리즘의 동작을 통해 우리는 \[ \begin{array}{rl} \mathsf{SOL} & \leq (1 + \lambda) B \\ & = (1 + \lambda) \cdot (B - t^\circ + t^\circ) \\ & \leq (1 + \lambda) \cdot (\bar{t} - t^\circ + t^\circ) \\ & = (1 + \lambda) \cdot (\mathsf{OPT} + \eta) \end{array} \]을 유도할 수 있습니다. 여기서 두 번째 부등식은 \(\bar{t} \geq B\)에서 얻을 수 있습니다. ■
정리 2를 통해 만약 예측치의 오차가 매우 작다면 이 알고리즘은 최적해의 거의 \((1 + \lambda)\) 배의 비용을 내는 답을 반환한다는 사실을 알 수 있습니다. 이번에는 반대로 알고리즘이 강건함을 보이겠습니다.
정리 3. 위 알고리즘의 강건성
위 알고리즘은 최대 \(\left( 1 + \frac{1}{\lambda} \right) \mathsf{OPT}\)의 비용을 갖는 답을 출력한다.
[증명] 여기서도 \(\mathsf{SOL}\)을 알고리즘이 반환하는 답의 비용, \(\mathsf{OPT}\)를 최적해의 비용이라고 하겠습니다. 만약 \(\bar{t} < B, t^\circ < B\)인 경우 위 알고리즘은 최적해를 반환합니다. 만약 \(\bar{t} \geq B, t^\circ \geq B\)인 경우에는 정리 2의 증명에서 \[\mathsf{SOL} \leq (1 + \lambda) \mathsf{OPT} \leq \left(1 + \frac{1}{\lambda} \right) \mathsf{OPT}\]가 된다는 것을 확인할 수 있습니다. 만약 \(\bar{t} < B, t^\circ \geq B\)라면 \[\mathsf{SOL} \leq \left( 1 + \frac{1}{\lambda} \right) B = \left( 1 + \frac{1}{\lambda} \right) \mathsf{OPT}\]임을 유도할 수 있습니다.
마지막으로 \(\bar{t} \geq B, t^\circ < B\)인 경우를 생각하겠습니다. 만약 \(t^\circ \leq \left\lfloor \lambda B \right\rfloor\)라면, 알고리즘은 최적해를 반환합니다. 그렇지 않은 경우, 알고리즘의 동작에 의해 \(\mathsf{SOL} \leq (\lambda + 1) B\)를 알 수 있고, \(t^\circ\)가 정수라는 사실과 버림의 성질에 의해 \(\mathsf{OPT} = t^\circ \geq \lambda B\)를 알 수 있습니다. 이를 통해 \[ \mathsf{SOL} \leq (1 + \lambda) B = \left(1 + \frac{1}{\lambda} \right) (\lambda B) \leq \left( 1 + \frac{1}{\lambda} \right) \mathsf{OPT}\]임을 이끌어 낼 수 있습니다. ■
이로써 이 알고리즘은 오차 \(\eta\)가 어떤 값을 갖더라도 최적해의 \((1 + \frac{1}{\lambda})\) 배 이내의 비용을 갖는 답을 출력하므로 강건한 알고리즘입니다.
\(\lambda\)에 따른 알고리즘의 성능을 그래프로 나타내면 아래와 같습니다. 빨간색 점선은 2-경쟁 알고리즘이 이루는 성능을 나타냅니다. 파란색 실선은 이 알고리즘의 일관성을 초록색 실선은 이 알고리즘의 강건성을 나타냅니다.
마치며
이것으로 스키 대여 문제에서 예상 폐장일이 입력으로 주어지는 경우 이를 활용하여 더 좋은 성능의 알고리즘을 얻는 방법에 대해 알아 보았습니다. 이러한 알고리즘은 예측이 정확할 때의 성능인 일관성과 예측이 틀렸을 때 보장해 주는 성능인 강건성 등 두 가지 척도로 분석할 수 있었습니다. 마지막으로 예측을 완전히 믿는 1-일관 알고리즘과 전혀 믿지 않는 2-경쟁 알고리즘을 잘 섞어 \((1+\lambda)\)-일관, \((1+\frac{1}{\lambda})\)-강건 알고리즘을 함께 공부하였습니다.
지난 몇 년 사이 인공 지능(artificial intelligence) 및 기계 학습(machine learning)은 컴퓨터 과학의 지평을 획기적으로 확장시켰습니다. 이론적인 아이디어에 불과했던 이 개념들은 컴퓨터 시스템의 성능이 비약적으로 향상되면서 산업적인 활용성이 입증되었으며, 이제는 컴퓨터 과학을 넘어 여러 이공 계열 학문은 물론 인문 계열 분야에서도 인공 지능과 기계 학습을 활용 및 연구하고 있습니다.
이러한 흐름은 이론 컴퓨터 과학(theoretical computer science)에서도 이어지나 봅니다. 특히 캐싱(caching)을 필두로 여러 온라인 문제에 기계 학습으로 얻은 예측치를 엮어 분석하는 연구가 지난 사오 년 전부터 폭발적으로 진행되었습니다. 제가 한창 대학원 생활을 시작할 무렵이더군요. 최근에서야 이러한 흐름을 알게 되어 약간은 아쉬운 마음이 있습니다만, 최근 이와 관련하여 몇 가지 흥미로운 결과를 얻은 것 같아 기쁘기도 합니다. 다른 온라인 문제에 대해서도 일관성, 강건성 분석을 어떻게 하는지 공부해야겠습니다. 공유할 만한 결과를 알게 되면 포스팅하도록 하겠습니다.
읽어 주셔서 고맙습니다.
참고 문헌
[1] Manish Purohit, Zoya Svitkina, and Ravi Kumar. "Improving online algorithms via ML predictions." Advances in Neural Information Processing Systems 31 (2018).
