Generalized Sorting with Predictions

이 글에서는 Pinyan Lu 외 3인의 논문 “Generalized Sorting with Predictions”에 대해 소개합니다. (글이 발행된 이후에 koosaga님의 project_tcs에 영상 및 자료가 올라갈 예정입니다.)

1. Generalized Sorting Problem

1.1. 문제의 정의

어떤 object들을 정렬하는 것은 컴퓨터 과학에 있어 매우 중요한 문제입니다. 일반적으로 우리가 (comparison-based) 정렬을 한다고 할 때, 우리는 임의의 원소 간의 “비교”가 가능한 상황을 상정합니다.

Generalized sorting problem에서는 이 상황을 보다 일반화하여 일부 원소들 사이에는 비교 연산을 이용할 수 없는, 즉 일부 원소들 간의 비교만 가능한 상황을 가정합니다. 이러한 상황에서, 우리는 최소 횟수의 비교 연산만을 이용하여 원소들을 정렬하는 데에 관심이 있습니다.

이 문제를 그래프 이론의 용어로 나타내면 조금 더 명확해집니다. 먼저, 정렬을 그래프 이론의 관점에서 한 번 바라봐봅시다. $n$개의 원소 $A_1, A_2, \cdots, A_n$ 이 있다고 합시다. $(i, j)$ 가 비교 가능하고, $A_i < A_j$ 이면, $i \to j$ 의 간선을 이은 그래프(DAG) $\vec G$를 생각합시다. 원소들의 “정렬”이란 $\vec G$ 에서의 해밀턴 경로에 대응될 것입니다.

이제, 우리는 무방향 그래프 $G$ 가 주어지는데, $(i, j)$가 비교 가능하면 $i-j$ 간선이 존재한다고 합시다. 이 그래프는 generalized sorting problem에서 우리가 사전에 알고 있는 정보와 정확히 같습니다. ($G$ 뒤에 “숨겨진” 그래프로는 $\vec G$ 가 있을 것이고, 우리는 $\vec G$ 가 어떻게 생겼는지는 모르지만, DAG이고 해밀턴 경로가 있다는 사실은 알고 있습니다.) 저희는 $\vec G$ 에서 해밀턴 경로를 포함하는 $\vec E’ \subset \vec E$ 를 찾아나가는데, $ij$에 대응되는 $\vec G$ 의 간선을 $\vec E’$에 추가할 때, $i \to j$ 인지 혹은 $j \to i$ 인지 간선의 방향을 알게됩니다.

Generalized sorting problem에서 알고리즘의 성능은 “보는” 간선의 (점근적인) 개수, 즉, $\lvert \vec E’\rvert$ 으로 평가됩니다.

1.2. 예시

예시 1. 가장 일반적인 경우로, 임의의 원소간에 비교가 가능한 경우를 생각해봅시다. 이 경우에는, $G$ 가 완전 그래프가 될 것이고, $\Theta (n \log n)$ 번의 비교 이내에 정렬 가능함 및 최소 $\Theta(n \log n)$ 회의 비교가 필요함, 즉 optimal 한 경우 $\lvert\vec E’\rvert = \Theta (n \log n)$ 임이 널리 알려져 있습니다.

예시 2. $n$ 쌍의 (서로 끼리만 잘 맞는) 볼트와 너트가 있고, 볼트 간에/너트 간에 비교가 금지된 상황 을 생각해봅시다. (사족: 이 상황은 여러 기업이나 학교의 인터뷰에도 자주 나오고, 알고리즘 연습 문제로도 자주 쓰이는 상황 세팅이기도 합니다.) 이 상황에서 서로 짝이 맞는 볼트-너트 쌍들을 찾으려 한다고 합시다.

이 경우에는, $G$ 가 왼쪽 정점으로 볼트들의 정점이 있고, 오른쪽 정점으로 너트들의 정점이 있는 완전 이분 그래프가 될 것입니다. (왜냐하면, 임의의 볼트-너트 사이에는 비교가 가능하지만, 볼트끼리 그리고 너트끼리는 비교가 불가능하기 때문입니다.) 그리고 퀵소트 알고리즘을 이용하여 평균적으로 $\lvert \vec E’\rvert = O(n \log n)$ 이게 정렬하는 방법이 널리 알려져 있습니다. (실제로 이 경우에도 optimal 한 경우 $\lvert \vec E’\rvert = \Theta(n \log n)$ 임이 알려져 있으나, 이 글의 범위를 벗어나 자세한 설명은 담지 않았습니다.)

2. Predictions

2.1. Prediction이란?

근래 머신러닝 기술이 연구되면서, 전통적인 알고리즘 분야에 prediction이라는 개념이 도입되기 시작했습니다. 이 패러다임에서는 머신러닝이 “예측”해주는 값을 이용하면 더 효율적인 알고리즘을 만들 수 있을 것이라 가정합니다. 구체적으로는, 예측 값이 “좋은” 경우에는 예측 값을 이용하지 않는 경우보다 더 잘 작동하고, 예측 값이 나쁜 경우에도 예측 값을 이용하지 않는 경우 만큼의 성능은 내는 알고리즘에 대해 연구가 이루어지고 있습니다.

2.2. Generalized Sorting with Predictions

앞서 우리는 generalized sorting 문제가 어떻게 정의되는지에 대해 살펴보았습니다. 이제, 여기에 prediction을 얹은, generalized sorting with predictions 문제의 정의에 대해 살펴보겠습니다.

먼저, 문제에 관련된 변수로는 $V, E, \vec E, \vec P$ 이렇게 4 가지가 있는데, 각각 다음을 의미합니다:

$V$: 정점 집합 (원소들의 집합)
$\vec E$: 그래프 $\vec G = (V, \vec E)$ 는 해밀턴 경로를 포함하는 DAG (비교 연산의 결과를 나타냄)
$E$: 그래프 $G = (V, E)$ 는 $\vec G$ 에 대응되는 무향 그래프 (비교 가능한 원소들 간에 간선이 있음)
$\vec P$: $E$ 에 orientation을 준(, 즉, 임의의 $uv \in E $ 에 대해 $(u, v)$ 와 $(v, u)$ 중 하나만이 $\vec P$ 에 속함) 집합으로 각 edge의 “예측된(predicted)” orientation을 나타냄.

이 글에서 $n = \lvert V \rvert$ 를 의미할 것이고, $w$ 는 예측이 틀린 정도, 즉, $w = \lvert \vec P - \vec E \rvert $ 를 의미할 것입니다.

이제 이 문제를 정의하자면, 앞에서와 같이

입력: $V, E, \vec P$ 이 되고,
출력: $\vec G$ 에서의 해밀턴 경로가 됩니다.

그런데, 여기에서는 $\vec P$ 라는 새로운 요소가 있는 만큼, $\lvert \vec E’\rvert $ (이는 앞에서와 같이 정의됩니다) 의 $n, w$ 에 대한 점근적인 식으로 성능을 평가합니다.

이 논문에서는 generalized sorting with predictions 문제를 다음 개수 만큼의 “간선을 까보며” 푸는 두 가지 (다항시간) 알고리즘을 제시했습니다:

$O(n \log n + w)$ randomized algorithm
$O(nw)$ deterministic algorithm

2.3. Some Notations

알고리즘의 본격적인 설명에 앞서 몇 가지를 정의하고 갑시다.

$\vec E’ \subseteq \vec E$ 에 대해 $V$ 상에서의 partial order $<_{\vec E’}$ 는 $u <_{\vec E’} v \iff $ $u$ 에서 $v$ 로의 $\vec E’$ 상의 경로가 존재함으로 정의됩니다.
$V’ \subseteq V$ 에 대해 $V’$ 상에서의 partial order $<_{V’}$ 은 $u <_{V’}v \iff $ $u$ 에서 $v$ 로의 $\vec E$ 상의 간선 및 $V’ $ 상의 정점만을 거치는 경로가 존재함으로 정의됩니다.
$\mathcal{N}_{in} (G_{\vec{P}}, u)$ 를 $\vec{P}$ 상에서 $u$ 로 들어오는 간선의 반대쪽 끝점들(in-neighbor)의 집합으로 정의합니다.
$S_u$ 를 $\mathcal{N}_{in} (G_{\vec{P}}, u)$ 에서 실제로 $u$ 로 들어오는 간선의 반대쪽 끝점들의 집합으로 정의합니다.
어떤 시점에서의 $T_u$ 는 $\mathcal{N}_{in} (G_{\vec{P}}, u)$ 의 원소 가운데 현재까지 모순이 발견되지 않은 (즉, 예측한 간선의 방향이 틀렸음이 아직 확인되지 않은) 것들의 집합으로 정의합니다.

3. Algorithms

3.1. Randomized $O(n \log n + w)$ Algorithm

집합 $A$ 를 $\mathcal{N}_{in} ( G_{\vec{P}}, u)$ 의 원소와 $u$ 사이를 잇는 간선들의 방향을 전부 아는 $u$ 들의 집합이라 합시다. 소개할 알고리즘은 $A = \emptyset$ 에서 시작하여 반복적인 과정을 거쳐 $A=V$ 까지 확장해나가며 작동합니다. ($A=V$ 이면, 모든 간선의 방향을 아는, 즉, 정렬이 완료된 상태입니다.)

Ideal Vertex

어떤 시점에서 후술할 알고리즘이 $A$ 에 추가하게 되는 정점을 ideal vertex라 부를 것입니다. 어떤 정점 $u$ 가 ideal vertex 임은 $T_u \subseteq A$ 이고, $T_u$ 상에서 $<_A$ 가 total order를 이룸으로 정의됩니다.

어떤 ideal vertex $u$ 를 $A$에 추가하기 위해서는 ($A$의 정의에 의해) $\mathcal{N}_{in}(G_{\vec{P}}, u)$ 와 $u$ 사이 간선의 방향이 전부 결정되어야 하는데, ($\mathcal{N}_{in} ( G_{\vec{P}}, u) - T_u$ 원소들과 $u$ 사이 간선의 방향은 예측한 것이 틀렸음이 확인되었으므로) $T_u$의 원소들과 $u$를 잇는 간선들의 방향만 더 결정해주면 됩니다. $T_u$의 $<_A$ 기준으로 최대 원소 $x$와 $u$를 잇는 간선을 까봤다고 합시다.

Case 1 - $xu $ 간선의 방향에 대한 예측이 옳았을 경우: 이 경우에는 $T_u$ 상에서 $<_A$가 total order를 이루므로, 모든 $T_u$의 원소들은 $u$로 들어오는 간선을 가진다는 사실을 알 수 있고, 이제 $u$를 $A$에 추가해주면 끝납니다.
Case 2 - 그렇지 않은 경우: $T_u := T_u - x$ 를 해주고 이 작업을 더 반복해주면 됩니다.

결국, ideal vertex들을 어떤 방법으로든 계속 찾아낸다고 한다면, 그 이후 이들을 $A$에 추가하는데는 어쨌든 총 $O(n + w)$ 개 정도의 간선을 까보면 충분합니다. 하지만, 항상 ideal vertex를 우리가 알고 있다는 보장이 없고, 실제로 그렇지 못할 수도 있습니다. 그래서 우리는 ideal vertex 보다는 조금 더 느슨한 가정을 가지는 대상을 다룹니다.

Active Vertex

어떤 정점 $u \in V$ 가 active vertex 임은 $S_u \subseteq A$ 이고, $S_u$ 상에서 partial order $<_A$ 가 total order임으로 정의됩니다. $S_u \subseteq T_u$ 이므로, 모든 ideal vertex는 active vertex 이기도 합니다. Active vertex와 ideal vertex의 큰 차이점은 active vertex가 항상 존재함이 보장된다는 것입니다.

Lemma. $V - A \neq \emptyset$ 이면, active vertex가 최소 하나 존재한다.

Proof. $\vec G$ 위의 해밀턴 경로 $v_1 \to v_2 \to \cdots \to v_n$ 에서 현재 시점에 $A$ 에 추가되지 않은 최소 인덱스 $k$ 를 잡자. 그러면, $S_{v_k} \subseteq {v_1, \cdots, v_{k-1}} \subseteq A$ 가 되며, 당연히, $ <_A$ 는 $S_{v_k}$ 상에서 total order가 됩니다. $\square$

우리가 어떤 active vertex를 하나 알고 있다고 할 때, 이 vertex를 ideal vertex로 만들기 위해서는 $T_u - S_u$ 의 원소들을 잘 찾아내야 합니다. 하지만, $S_u$ 는 우리가 모르는 무언가라는 치명적인 문제점이 있습니다. 그러니, 우리가 아는 무언가들로 정의된 ideal vertex를 다시금 살펴봅시다.

Certificate

어떤 정점 $u$가 ideal vertex가 아니라면 다음 두 가지 사실을 만족합니다.

$v \not \in A$ 인 $v \in T_u$ 가 존재
$A$ 상의 정점들로 이루어진 경로가 없는 $v_1, v_2 \in T_u$ 가 존재

$u$가 active vertex인 경우를 생각해봅시다. 만약 1을 만족하는 $v$가 존재한다면, $(v, u) \in \vec P - \vec E$, 즉, $(v, u)$ 는 틀린 예측일 것입니다. 만약 2를 만족하는 $v_1, v_2$가 있다면, $(v_1, u)$ 와 $(v_2, u)$ 중 틀린 예측이 있을 것입니다. 즉, $u$가 active vertex 이면서 ideal vertex가 아니라면, $(v, u)$ 및 $(v_1, u)$와 $(v_2, u)$ 를 계속 까보는 것으로 ideal vertex로 만들기에 충분합니다.

이제, $u$가 inactive vertex인 경우를 살펴봅시다. 이 경우에는 1을 만족하는 $(v, u)$를 까보니 실제 예측과 일치할 수도 있고, 2를 만족하는 $(v_1, u), (v_2, u)$의 경우에도 동일합니다. 따라서, 정점 $u$에 대해 type-1 certificate와 type-2 certificate를 다음과 같이 정의하면, certificate의 존재는 $u$가 active가 아님을 간접적으로 확인시켜줍니다.

Type-1 certificate: $v \in S_u$ 이고 $v \not \in A$ 인 정점 $v$
Type-2 certificate: $v_1, v_2 \in A$ 이고 $v_1$과 $v_2$ 사이에 $A$ 상의 정점들로 이루어진 경로가 없는 정점 쌍 $(v_1, v_2)$

이제, 정점 $u$에 대한 certificate를 발견했다면, $A$가 업데이트 되어 certificate가 더 이상 유효하지 않게 되는 시점 까지는 추가적으로 $u$로 들어오는 간선들을 볼 필요가 없습니다. 각 경우에 대해 이 시점은 다음과 같습니다.

Type-1 certificate $v$의 경우: $v$가 $A$에 추가되는 시점
Type-2 certificate $(v_1, v_2)$의 경우: $A$가 업데이트 되며 $v_1$과 $v_2$ 사이를 잇는 $G[A]$의 경로가 생기는 경우

Algorithm

논문에서 제시하는 알고리즘은 $A = \emptyset$ 으로 부터 시작해 $A = V$가 될 때 까지 valid한 certificate가 없는 정점 $u$를 반복적으로 살펴보며 동작합니다. (tie-breaking은 정점의 인덱스 순으로 이루어집니다.)

$u$가 ideal vertex인 경우:

이 경우에는 ideal vertex 부분에서 언급한 전략을 사용합니다. 구체적으로는, $T_u$의 $<_A$ 에 대한 최대 원소 $x$를 잡고, $x$와 $u$를 잇는 간선을 까보는 과정을 반복하면서, $(x, u)$ 간선에 대한 예측이 들어맞는 최초의 $x$를 찾으면, $u$를 $A$에 추가합니다.
그렇지 않은 경우:

이 경우에는 $v \not \in A$ 인 $v \in T_u$ 가 존재하거나, $A$ 상의 정점들로 이루어진 경로가 없는 $v_1, v_2 \in T_u$ 가 존재합니다. 다음을 수행합니다.
- 첫 번째 경우에는, 랜덤한 $v \in T_u - A$ 를 잡고, $(v, u)$를 까봅니다.
- 두 번째 경우에는, $A$ 상의 정점들로 이루어진 경로가 없는 $v_1, v_2 \in T_u$ 를 랜덤하게 뽑고, $(v_1, u)$와 $(v_2, u)$를 까봅니다.

2번 케이스에서 간선을 까다가 운이 안 좋으면 매우 많은 간선을 까보게 되는데, 이 경우의 발생을 방지하기 위해 우리는 랜덤한 순서대로 간선을 까보게 됩니다.

이제, 우리는 이 알고리즘에 대해 분석해볼 것입니다. 크게 두 가지의 사실을 확인해야 합니다:

알고리즘이 유한한 시간 안에 수행된다.
알고리즘이 충분히 높은 확률로 $O(n \log n + w)$ 만큼의 간선을 까본다.

먼저, 알고리즘이 유한한 시간 안에 수행됨을 확인해봅시다. 일단, $V \neq A$ 인 이상, 항상 active vertex가 존재하므로 certifcate가 없는 vertex 또한 존재합니다. 그리고 위의 1번 경우에서 하는 $u$를 $A$에 추가하는 행위와 2번 경우에서 하는 간선(들)을 까보는 행위 모두 무한히 많이 반복할 수는 없습니다. 고로, 알고리즘이 유한한 시간 만에 수행되고, 종료됨은 확인할 수 있습니다.

Performance

알고리즘의 performance, 즉, 까보는 간선의 점근적인 개수를 살펴보기 위해서는, 알고리즘의 한 가지 성질을 짚고 넘어가야 합니다. 바로, 알고리즘이 비록 랜덤을 사용하지만, $A$에 정점들이 추가되는 순서는 고정되어 있습니다.

그 이유를 살펴보자면, 어떤 정점이 active(certifcate가 없는) vertex인지의 여부는 $A$에만 의존하며, $A$에 추가되는 정점은 항상 active vertex입니다. 그런데, 정점의 인덱스 순으로 tie-breaking을 해줬으므로, 결국, 가장 인덱스가 작은 active vertex가 반복적으로 $A$에 추가되게 되고, 따라서, $A$에 정점들이 추가되는 순서가 고정되어 있음을 확인할 수 있습니다.

한 가지 확률론적인 사실 또한 알고리즘의 분석에 필요한데, 이는 증명 없이 사용하도록 하겠습니다.

Proposition. $[n]$ 의 random permutation $Y_1, \cdots, Y_n$에 대해 $Y_i = \max(Y_1, Y_2, \cdots, Y_i)$인 $i$의 수는 $1 - {1 \over 2n^2}$ 이상의 확률로 $6 \ln n+ 6$을 넘지 않는다.

Theorem. 높은 확률로 알고리즘은 $O(n \log n + w)$ 이내 횟수 만큼 간선을 까본다.

Proof. 알고리즘이 반복해서 수행하는 루틴에서는 다음 세 가지 경우 중 정확히 하나만이 나타납니다.

Case 1: 현재 valid한 certificate가 없는 $u$에 대한 certificate를 찾는다.
Case 2: 잘못 예측한 간선을 찾는다.
Case 3: 정점 $u$를 $A$에 추가한다.

각 경우에 대해서 우리는 최대 2개의 간선만을 까보기 때문에, 각 경우가 몇 번 나타나는지 세 주는 것으로 충분합니다. Case 3은 최대 $n$번, Case 2는 최대 $w$번 나타남을 알 수 있습니다.

정점 $u$를 고정해놓고, Case 1에 대해 살펴봅시다. $A$에 정점들이 추가되는 순서는 고정되어 있으므로, $u$의 type-1 certificate들 또한 어떤 고정된 순서로 더 이상 유효하지 않게 됩니다. 이제, $u$의 type-1 certificate들에 발견된 순서들에 따라 1 부터 $\lvert S_u\rvert$ 까지의 번호를 붙여두고, 알고리즘이 진행됨에 따라 유효해지지 않는 과정을 $\lvert S_u\rvert $ 상의 순열 $Y_{u, 1}, \cdots, Y_{u, \lvert S_u\rvert }$로 나타내어 볼 수 있습니다. (type-1 certificate $i$는 $Y_{u, i}$ 번째로 유효하지 않게 됩니다.) 그러면, $Y_{u, i} \le \max_{j, i} Y_{u, j}$ 임이 type-1 certificate $i$를 valid한 상태로 발견할 필요충분조건이 됩니다.

여기에서, type-1 certificate에 붙는 번호들은 균등하게 랜덤한 순열이 되고, 고로 $Y_{u, 1}, \cdots, Y_{u, \lvert S_u\rvert }$ 또한 같은 분포을 확인할 수 있습니다. 따라서, Proposition에 의해, ${1 - {1 \over 2n^2}}$ 이상의 확률로 $6 \ln n + 6$개 이내의 valid한 $u$에 대한 type-1 certificate를 발견하게 됩니다. 여기에, union bound를 적용하면, type-1 certificate를 $1 - {1 \over 2n}$ 이상의 확률로 총 $6n \ln n + 6n$ 개 이내로 발견하게 됨을 알 수 있습니다. 비슷한 논증을 type-2 certificate에 대해서도 적용해줄 수 있고, 그러면 type-2 certificate를 $1 - {1 \over 2n}$ 이상의 확률로 최대 $12 n \ln n + 6n$ 개만 발견하게 됨을 알 수 있습니다.

따라서, 알고리즘은 $1 - {1 \over n}$ 이상의 확률로 $O(n \log n + w)$ 개의 간선만을 까보게 됩니다. $\square$

3.2. Deterministic $O(n w)$ Algorithm

논문에서는 deterministic 하게 $O(nw)$만의 간선을 까보는 알고리즘도 제시했습니다. 이를 위한 접근 전략은 단순한데, $O(n)$개의 간선만을 까보면서 잘못 예측된 간선 하나를 찾아서 “바로잡는” 것입니다. 알고리즘이 수행되고 있는 특정한 시점을 고정하고 생각해봅시다. 현재까지 까본 간선들의 집합 $\vec E’$ 이 있을 것입니다. 이 $\vec E’$ 으로 부터 우리는 현재까지 바로잡힌 그래프 $\vec {G}_C = (V, \vec P_C)$ 를 생각합니다. 여기에서, $\vec P_C$ 는 예측된 간선들을 현재까지 바로잡은 결과로, $\vec P_C = { (v, u) \in \vec P : (u, v) \not \in \vec E’} \cup \vec E’$ 으로 정의됩니다.

이 그래프 $\vec G_C$ 를 관리하며 문제를 해결하는 과정을 상상해봅시다. $\vec G_C$로 부터 틀리게 예측된 간선 하나를 찾을 수 있는 상황은 어떤 경우일까요? $\vec G_C$에 사이클이 있는 상황과 없는 상황으로 나누어 생각해봅시다:

$\vec G_C$에 사이클이 있는 경우: $\vec G$는 acyclic이므로, $\vec G_C$의 사이클의 간선 중에 잘못 예측한 간선이 있음이 확실합니다. 따라서, 사이클의 간선들(최대 $O(n)$개가 사이클 상에 있습니다)을 “잘못 발견한 간선”을 발견할 때 까지 까보면, 총 $O(n)$ 시간에 잘못 예측한 간선 하나를 고칠 수 있습니다.
$\vec G_C$에 사이클이 없는 경우: $\vec G_C$도 DAG이므로, 위상정렬을 시켜볼 수 있습니다. 위상 정렬 순서대로 정점을 적은 것이 $a_1, a_2, \cdots, a_n$ 이라 합시다.
- 만약, in-degree가 0인 정점이 단 하나만 있다면, 간선 $(a_i, a_{i+1})$들을 전부 까봅시다. 만약 틀린 것이 없다면, 우리는 해밀턴 경로를 찾은 것이므로 알고리즘을 종료해도 됩니다. 아니라면, 틀린 간선들을 찾았으므로, 목표를 달성했습니다. 이 과정에서도 역시 $O(n)$개 이내의 간선만 추가적으로 까보게 됩니다.
- 아닌 경우에는, 일단, in-degree가 0인 정점이 여러개 (그 중 2개 $v_1, v_2$를 잡자) 있습니다. 이 경우에는 명백히 틀리게 예측한 간선이 있고, 이 간선은 중에는 $v_1, v_2$ 중 하나에 인접한 간선이 있을 것입니다. 고로, 역시 $O(n)$개 이내의 간선만 까보면 됩니다.

결국, 이 전략을 사용하면 deterministic하게 $O(nw)$개의 간선만을 까보며 문제를 해결할 수 있습니다. 심지어, $w = O(1)$로 매우 정확한 예측을 한 상황을 가정해보면, 문제를 $O(n)$에 해결할 수도 있게 되는 것입니다.

Written on April 15, 2021