📂위상데이터분석

조모로디안의 알고리즘 유도

개요

조모로디안^zomorodian과 칼슨^Carlsson의 논문 ‘Computing Persistent Homology’에서 소개된 알고리즘의 유도과정을 설명한다¹. 추상 심플리셜 컴플렉스로 만들어진 필터드 컴플렉스를 받아 $\mathcal{P}$-인터벌을 리턴하며, 컴퓨터로 다루기 어려운 퍼시스턴트 모듈 구축을 생략하고 행렬의 리덕션으로 지속성 호몰로지를 계산한다.

유도

Part 0. 사전조사

알고리즘의 본격적인 유도에 앞서 위와 같은 그림으로 묘사되는 퍼시스턴스 컴플렉스가 수식적으로 어떤 형태인지부터 살펴보자. 이 과정을 확실하게 다져놓지 않으면 논문 읽기가 몹시 괴로울 것이다.

• 우선 하단에 있는 숫자를 $\deg$ 라 하며, 이것이 $0$부터 $5$까지 증가하며 다음과 같이 필터드 컴플렉스를 이룬다. $$ \left\{ a,b \right\} = K_{0} \subset K_{1} \subset K_{2} \subset K_{3} \subset K_{4} \subset \left( K_{4} \cup \left\{ acd \right\} \right) = K_{5} $$
• $\deg$ 와 상관 없이 $K$ 은 $2$-심플렉스로써, 호몰로지을 고려한다는 맥락에서 다음과 같은 체인 컴플렉스를 이룬다. $$ \mathsf{C}_{2} \overset{\partial_{2}}{\longrightarrow} \mathsf{C}_{1} \overset{\partial_{1}}{\longrightarrow} \mathsf{C}_{0} $$

알고리즘의 목표는 이러한 $\partial_{2}$ 와 $\partial_{1}$ 이 데이터에 대해 주는 대수위상적 정보, 이를테면 베티 수 $\beta_{k}$ 와 같은 것들이 어떤 $\deg$ 에 생겨나서 언제 $\deg$ 에 사라지는지 다음과 같이 계산하는 것이다. $$ \begin{align*} L_{0} =& \left\{ \left( 0, \infty \right) , \left( 0,1 \right) , \left( 1,1 \right) , \left( 1,2 \right) \right\} \\ L_{1} =& \left\{ \left( 2,5 \right) , \left( 3,4 \right) \right\} \end{align*} $$

$L_{0}$ 는 $\beta_{0}$ 에 해당하는 정보, 즉 컴포넌트가 언제 생겨나고 사라지는를 보여주는 $\mathcal{P}$-인터벌들로 이루어져 있으며 $L_{1}$ 는 $\beta_{1}$ 에 해당하는 정보, 즉 공간에서 ‘구멍’이라고 할 것들이 언제 생겨나고 사라지는 $\mathcal{P}$-인터벌들로 이루어져 있다.

---

Part 1. $\partial_{1}$

논문에서 저자들은 그를 위한 계산이 모든 필드에서 가능하다고 주장하는데, 간단히 등급모듈인 $\mathbb{Z}_{2} [t]$-모듈에서 어떤 계산이 이루어지는지를 살펴보도록 하자. 이제 $\mathsf{C}_{k}$ 의 동질적^homogeneous 기저를 $\left\{ e_{j} \right\}$, $\mathsf{C}_{k-1}$ 의 동질적 기저를 $\left\{ \hat{e}_{i} \right\}$ 이라 표기하도록 하자. 여기서 동질적이라는 것은 $\mathsf{C}_{k}$ 를 등급모듈로 보았을 때 항이 하나밖에 없다는 뜻으로 받아들여도, 즉 $t^{2} + t$ 같은 게 아니라 $t^{4}$ 같이 단항꼴의 모양이라고 간주해도 무방하다는 말이다.

$$ \deg M_{k} (i,j) = \deg e_{j} - \deg \hat{e}_{i} $$ 호몰로지 대수에 어느정도 익숙하다면 이제 $\partial_{k}$ 에 대응하는 바운더리 행렬 $M_{k}$ 를 위 테이블과 방정식에 맞게 구성하고 그 스미스 노멀 폼 $\tilde{M}_{1}$ 을 구하러 갈 것이라는 느낌이 올 것이다. 우선 $k=1$ 인 경우를 생각해보면, 앞서 행렬의 기저들이 동질적이라 했으므로 다음과 같이 유일한 $M_{1}$ 를 얻을 수 있다.

이렇게 기저를 가지고 행렬을 구성하는 것은 $\partial_{k}$ 의 역할 중 하나가 $t^{n}$ 을 곱하는 것(그룹액션을 취함으로써 등급모듈에서 차수가 올라간 것)을 반대로 행하는 것이라 보면 된다. 감을 잡기 위해 딱 세번만 직접 계산해보자. $$ \begin{align*} \deg M_{1} (2,5) =& \deg ac - \deg c = 3 - 1 = 2 = \deg t^{2} \\ \deg M_{1} (4,5) =& \deg ac - \deg a = 3 - 0 = 3 = \deg t^{3} \\ \deg M_{1} (2,2) =& \deg bc - \deg c = 1 - 1 = 0 = \deg t^{0} = \deg 1 \end{align*} $$

앞서 말했던 것처럼 이제 이것의 에쉘론 폼, 특히 칼럼-에쉘론 폼을 만들면 다음과 같다.

학부때 배웠던 선형대수를 복기해보면, 각 칼럼에서 가장 위에 있으면서 $0$ 아닌, 그림에서처럼 사각형을 쳐놓은 부분 같은 것들을 피벗이라 불렀었다. 여기서 다음의 두가지 보조정리를 소개한다.

• (1): 칼럼-에쉘론 폼의 대각성분은 스미스 노멀 폼의 대각성분과 같다.
• (2): $\tilde{M}_{k}$ 의 $i$행의 피벗이 $\tilde{M}_{k} (i,j) = t^{n}$ 이면 호몰로지그룹 $H_{k-1}$ 의 $\sum^{\deg \hat{e}_{i}} F[t] / t^{n}$ 에 해당하는 것이고, 그 외에는 $H_{k-1}$ 의 $\sum^{\deg \hat{e}_{i}} F[t]$ 에 해당하는 것이다. 이는 $L_{k-1}$ 가 $\left( \deg \hat{e}_{i} , \deg \hat{e}_{i} + n \right)$ 과 $\left( \deg \hat{e}_{i} , \infty \right)$ 로 이루어지는 것과 동치다.

다시 말해,

• 보조정리 (1)에 따라 지속성 호몰로지를 계산할 땐 행연산이 필요 없고 열연산만 있으면 된다.
• 보조정리 (2)에 따라 $L_{k-1}$ 는 $\left( \deg \hat{e}_{i} , \deg \hat{e}_{i} + n \right)$ 과 $\left( \deg \hat{e}_{i} , \infty \right)$ 로 이루어진다.
  • 첫번째 행의 피벗이 $t^{1}$ 이고 $\deg d = 1$ 이므로 $(1,1+1)$ 를 얻는다.
  • 두번째 행의 피벗이 $t^{0}$ 이고 $\deg c = 1$ 이므로 $(1,1+0)$ 를 얻는다.
  • 세번째 행의 피벗이 $t^{1}$ 이고 $\deg b = 0$ 이므로 $(0,0+1)$ 를 얻는다.
  • 네번째 행의 피벗이 없고 $\deg a = 0$ 이므로 $(0,\infty)$ 를 얻는다.

이는 알고리즘을 유도하기 전에 언급했던 $L_{0}$ 과 정확히 일치한다. $$ L_{0} = \left\{ \left( 0, \infty \right) , \left( 0,1 \right) , \left( 1,1 \right) , \left( 1,2 \right) \right\} $$

---

Part 2. $\partial_{2}$

$L_{1}$ 을 구하기 위한 $\partial_{2}$ 의 행렬꼴 $M_{2}$ 는 위와 같다. 그런데 여기서 다음의 보조정리로 계산을 줄이고 쉽게 갈 수 있다.

• (3): $\mathsf{C}_{k+1}$ 의 표준기저와 $\mathsf{Z}_{k}$ 에 대한 $\partial_{k+1}$ 를 표현하기 위해서는 $\tilde{M}_{k}$ 에 대응되는 행을 $M_{k+1}$ 에서 그냥 제거해도 된다.

말이 좀 어려워보이는데, 지금 우리의 구체적인 상황에서는 $\tilde{M}_{1}$ 의 $1$-심플렉스 $ab,bc,cd,ad,ac$ 중에서 $cd,bc,ab$ 의 피벗만 남았으니 이걸 그냥 $M_{2}$ 에서 삭제해도 된다는 것이다. 직관적으로 생각해보자면 이들이 이미 $k$차원에서 쓰였으니 $k+1$에서는 볼 필요도 없다는 정도로 받아들여도 무방하다. 이렇게 칼럼-에쉘론 폼 $\tilde{M}_{2}$ 를 직접 구하는 과정을 생략하고 그 세 개의 행을 삭제해보면 다음과 같이 밑이 잘린 $\check{M}_{2}$ 를 얻는다.

$$ \begin{align*} z_{2} =& ac - bc - ab \\ z_{1} =& ad - bc - cd - ab \end{align*} $$

다시 보조정리 (2)에 따라 계산해보자.

• 첫번째 행의 피벗이 $t^{1}$ 이고 $$ \deg z_{2} = \deg \left( ac - bc - ab \right) = \max \deg \left\{ ac , bc , ab \right\} = 3 $$ 이므로 $(3,3+1)$ 를 얻는다.
• 두번째 행의 피벗이 $t^{3}$ 이고 $$ \deg z_{1} = \deg \left( ad - bc - cd - ab \right) = \max \deg \left\{ ad , bc , cd , ab \right\} = 2 $$ 이므로 $(2,2+3)$ 을 얻는다.

이는 알고리즘을 유도하기 전에 언급했던 $L_{1}$ 과 정확히 일치한다. $$ L_{1} = \left\{ \left( 2,5 \right) , \left( 3,4 \right) \right\} $$

이와 같은 과정을 컴플렉스 $K$ 의 차원 $\dim K$ 만큼 반복하면 우리가 원하던 알고리즘을 얻는다. 행렬의 좌우크기는 $\partial_{k}$ 를 따라서, 그 성분들은 $\deg$ 를 따라서 채운다고 생각하면 조금 덜 헷갈릴 것이다.

■

한편 보조정리 (1)에서 열연산만으로 충분하다는 것은 딱히 지금까지의 유도에서 본 것처럼 행렬 표현을 고집할 이유가 없다는 뜻이기도 하다. 또한 보조정리 (3)에 따라 ‘과거에 이미 계산이 끝난’ 부분에 대해서 과감하게 행을 버리는 식의 효율적인 프로시저가 포함되어 있는데, 이를 위해 피벗이 아닌 칼럼을 ‘마킹’하는 능력 등이 필요하다. 결과적으로 실제 알고리즘의 의사코드^{pseudo Code}는 행렬을 그대로 사용하는 게 아니라 조금 더 고수준의 자료형, 딕셔너리 혹은 데이터프레임 같은 것으로 설명하게 된다. 이게 직접 겪어보면 무척 당황스럽고 어렵다.

구현

• 조모로디안의 알고리즘 구현: 과학계에 종사한다면 누구라도 읽기 편한 줄리아 언어를 통해 논문의 의사코드를 거의 문학적으로 옮긴 구현을 소개한다.