Persistence Images

 

 

안녕하세요. 톡발이입니다.

 

오늘은 지난 시간에 설명했던 TDA를 복습하고 그 중에서도 Persistence Images에 대해서 중점적으로 설명해보려고 합니다. 이를 위해서 "Persistence Images: A Stable Vector Representation of Persistent Homology"라는 논문에 대해서 리뷰를 해보려고 합니다.

TDA에 관한 설명은 지난 글을 참고해주세요!

2023.10.25 - [분류 전체보기] - Topological Data Analysis 1

Topological Data Analysis 1

 

2023.10.30 - [분류 전체보기] - Topological Data Analysis 2

Topological Data Analysis 2

그럼 TDA에 대해서 다시 한 번 자세하고 알아보고 Persistence Image (PI)에 대해서 설명해 보겠습니다.

Introduction

최근 몇 년 동안, 위상 수학의 분야는 컴퓨터를 활용하는 다양한 tools를 포함하게 되었죠. 기본적인 tools 중 하나는 persistence homology입니다. 이는 topological features가 중첩된 topological spaces에서 어떻게 나타나고 사라지는지 추적한다고 배웠습니다. 이 multiscale 정보는 persistence diagram (PD)로 나타낼 수 있으며, 각 점 (x, y)는 scale x에서 나타나고 scale y에서 사라지는 topological feature에 해당합니다. 이를 해당 feature가 y - x의 persistence 값을 가진다고 합니다.

PD의 space는 metric 구조(bottleneck 또는 Wasserstein)로 제공될 수 있으며, 이러한 metric은 PD가 요약한 데이터에 perturbation이 있을 때 PD의 stability를 나타내어줍니다. 이로써 PD를 데이터 집합을 clustering하기 위한 통계량으로 사용하여 다양한 ML 기술을 수행하는 것이 가능합니다. 그러나 이 자체만으로는 ML에 직접적으로 가져다 쓰기는 부족합니다. 게다가, diagram의 대각선이 아닌 점들의 개수가 증가함에 따라 bottleneck 또는 Wasserstein distance를 계산하는 비용이 빠르게 증가합니다. 이러한 문제를 해결하기 위해, PD를 다른 ML tools에 적합한 spaces으로 mapping하기 위한 상당한 노력이 기울여졌는데요. 각 접근 방식은 장단점을 가지고 있다. 이를 고려해 논문은 다음과 같은 질문을 제기했습니다.

Problem Statement

어떻게 하면 persistence diagram을 다음과 같이 효과적으로 나타낼 수 있을까?

1. Representation의 output은 $\mathbb{R}^n$의 벡터
2. Representation은 input noise에 대해 stable
3. Representation은 계산이 효율적
4. Representation은 원본 PD와 interpretable한 연결을 유지
5. Representation은 PD의 다른 영역의 점들의 상대적 중요성 조절 가능

기준 1은 PI를 개발하는 이 논문의 주요 동기입니다. 이미 $\mathbb{R}^n$ 공간에서 데이터를 다루기 위한 다양한 ML 기법과 통계 tools(평균과 분산)가 존재하죠. 게다가, 이러한 표현은 다양한 거리 측정 방법(p-norms와 angle based metric) 및 (비)유사성의 다른 측정 방법을 활용할 수 있게 해줍니다. Problem statement의 나머지 기준 (2~5)는 이 표현의 유용성을 확보해줍니다.

 

Persistence Images (PI)란 PD의 finite-dimensional-vector 표현입니다. 우선, persistence diagram B를 적분 가능한 함수 $ρ_B : \mathbb{R}^2 \rightarrow \mathbb{R}$ 로 mapping하며, 이를 persistence surface이라고 부릅니다. Surface $ρ_B$는 PD의 각 점을 중심으로 하는 Gaussian 함수(또는 더 일반적으로, 확률 밀도 함수)의 가중합으로 정의합니다. Persistence surface의 아이디어는 persistence homology의 개발 이전에도 이미 나타났습니다. $ρ_B$의 subdomain을 이산화하는 것으로 grid를 정의합니다. Persistence image, 즉 픽셀 값의 행렬은 각 grid box에서 $ρ_B$의 적분을 계산하여 생성할 수 있습니다. 이 PI는 PD의 "벡터화" (vectorization)이며, 앞서 언급한 문제에 대한 해결책을 제공합니다.

 

기준5가 필요로 하는 유연성은 PI를 Gaussian의 가중합으로 구성함으로써 달성됩니다. 이때 가중치는 다양한 가중치 함수 class에서 선택할 수 있습니다. 예를 들어, 일반적으로 PD에서 지속성이 높은 점들이 낮은 지속성의 점들(이는 noise에 해당할 수 있다)보다 중요하다는 해석이 일반적입니다. 따라서 가중치 함수가 각 PD 점의 지속성 값에 대해 각각 non-decreasing한 Gaussian의 가중합으로 PI를 구축할 수 있습니다. 그러나, 어떤 상황에서는 사람들이 다른 중요성 측정 방법을 선호할 수 있죠. 실제로, Bendich 및 동료들(2015)은 그들의 regression 작업에서 인간 뇌의 동맥 기하학으로부터 나이를 식별하는 작업에서 높은 지속성이 아닌 중간 지속성의 점들이 데이터를 가장 잘 구별하는 것을 발견했습니다. 이러한 상황에서는 중간 지속성을 가진 점들에 가장 큰 값을 갖도록 가중치 함수를 선택할 수 있습니다. 기준5의 단점은 선택을 필요로 한다는 것입니다. 그러나 개별 문제에 대한 사전 지식은 그 선택에 도움이 될 수 있습니다. 게다가, 논문에서 제시한 예시는 지속성 값에 따라 non-decreasing하는 가중치 함수의 효과성을 보여줍니다.

Related Work

PD의 space는 bottleneck 또는 Wasserstein metric으로 설명할 수 있으며, PD를 사용하는 하나의 이유는 이러한 metirc이 입력 값의 perturbation에 대해 안정적이기 때문입니다. 그러나 metirc space의 구조만으로는 많은 ML 기술에는 충분하지 않으며, 최근에는 topology data analysis 커뮤니티에서 관심을 끌고 있는 분야는 지속성의 적용 범위를 확장하기 위해 PD를 인코딩하는 방법입니다.

 

Bubenik은 PD의 stable한 기능적 표현인 persistence landscape 개념을 개발하였고 이 표현은 Banach space (complete normed space) 내에 존재합니다. Persistence Landscape (PL)는 함수 $λ: \mathbb{N}×\mathbb{R} → [−\infty, \infty]$로, 이 함수는 동등하게 $λ_k : \mathbb{R} → [−\infty, \infty]$ 함수의 sequence로 생각할 수 있습니다. $1 ≤ p ≤ \infty$ 범위에서 두 landscapes $λ$과 $λ'$ 사이의 p-landscape distance는 $||λ − λ'||_p$로 정의됩니다. 여기서 $\infty$-landscape distance는 PD 상의 bottleneck distance에 대해 stable 하며, p-landscape distance는 PD 상의 p-Wasserestein distance에 대해 연속성을 가집니다. Persistence landscape를 정의하는 동기 중 하나는, PD의 $\text{Fr}\acute{e}\text{chet}$ 평균 (여러 데이터 포인트의 집합에서 중심 위치를 나타내는 기하학적인 개념)이 반드시 unique하지 않을 수 있다는 점에 비해, persistence landscape의 집합은 unique한 평균을 갖는다는 것입니다. Unique한 평균은 또한 PI의 feature인데 이는 이들이 벡터 표현이기 때문입니다. PL의 장점 중 하나는 PD에서 PL로의 mapping이 쉽게 invertible이 가능하다는 것입니다. PL에 비해 PI의 장점 중 하나는 PI가 Euclidean space에 속하므로 더 다양한 ML 기법에 적용 가능하다는 것입니다.

 

PD의 벡터 표현은 Carrière 등(2015)에 의해 제안 됐고, 이는 PD 내의 점들 간의 거리 행렬의 항목들을 재배열하여 얻을 수 있습니다. 그들의 정리에서, 그들은 결과 벡터들 간의 $L^{\infty}$ 및 $L^2$ norm이 PD 상의 bottleneck distance에 대해 stable한 것을 증명합니다. 그들은 $L^{\infty}$ norm은 nearest-neighbor classifiers에 유용하며, $L^2$ norm은 SVM과 같은 더 복잡한 알고리즘에 적용할 수 있다고 언급합니다. 그러나, $L^{/infty}$ norm에 대한 stability 결과는 잘 작동하지만, $L^2$ norm의 경우에는 그들의 상수가 PD 내의 데이터 포인트 수에 불필요하게 크게 scaling된다는 문제가 있습니다. 저자들은 이것을 이 논문의 Theorem 4의 동기로 제시합니다. 이 정리에서는 PI 벡터의 $L^{/infty}$, $L^1$ 및 $L^2$ norm이 PD 간의 1-Wasserstein distance에 대해 stable한 것을 증명하며, 이 중 어느 것도 PD 내의 데이터 포인트 수에 의존하지 않습니다.

 

Bendich 등은 PD 위에 grid를 겹쳐 놓고 각 칸(bin)에 있는 topological feature의 개수를 세어 feature vector representation을 만들었습니다. 이 접근 방식의 장점은 output이 다른 더 복잡한 표현보다 해석하기 쉽다는 것이지만, 단점은 벡터가 두 가지 이유 때문에 stable하지 않다는 것입니다.

1. PD 내의 한 점이 미세하게 움직여도 그 점이 다른 칸으로 이동할 수 있다.
2. 대각선에서 나타난 PD의 점은 불연속적인 변화를 만들어낼 수 있다.

Instability의 원인인 1은 PD를 먼저 surface로 smoothing함으로써 개선될 수 있습니다. Persistent Homology의 개발 이전에도, Donatini 등과 Ferri 등은 size functions를 surfaces로 변환하기 위해 diagram 내 각 점을 중심으로 하는 Gaussian 함수의 합을 취하는 방식을 사용했었습니다. 그런데 이 변환은 2로 인해 stable하지 않습니다. 저자들은 그들의 작업을 이러한 surface들의 연구의 연장선으로 여기며, 이제 더 높은 homological dimension에서도 이러한 surface들을 다루게 되었는데, 이를 위해 weighting function을 도입하여 2를 해결하고 stable을 확보하고자 합니다. (논문의 weighting function은 연속적이며 지속성이 0인 지점, 즉 대각선 상의 지점에 대해 값이 0이다)

 

저자들은 독립적으로 개발한 surface를 제안하며, 이는 다음과 같은 잠재적인 이점을 가진 stable한 PD의 대체 표현입니다.

첫째, 논문의 non-negatively weighted Gaussian의 합은 negative Gaussian을 포함하는 합보다 해석하기 쉬울 수 있습니다.

둘째, stability한 경계를 가진 surface에서 벡터를 생성한다. 이는 linear SVM과 같은 벡터 기반 학습 방법을 사용할 수 있게 해줍니다. 사실, Zeppelzauer 등은 Reininghaus 등의 kernel이 nonlinear SVM과 함께 사용될 수 있지만, 실제로는 이것이 훈련 벡터의 수가 많아질수록 비효율적이라고 합니다. 왜냐하면 전체 kernel 행렬을 계산해야 하기 때문입니다.

셋째, Reininghaus 등의 surface는 대각선으로부터 더 멀리 떨어진 지속성 점들에 대해 더 높은 가중치를 부여하지만, 다른 가중치를 선호하는 상황도 있을 수 있습니다. 따라서, 대각선에서 멀어질수록 가중치가 non-increasing하거나 decreasing하는 지속성 점들에 대한 가중치를 원할 수 있으며, 이러한 선택지는 논문의 접근 방식에서 가능합니다.

 

저자들은 각 점을 중심으로 하는 Gaussian의 가중합으로 persistence surface를 PD에서 생성합니다. 저자들은 grid 위에서 논문의 surfaces를 적분하여 벡터 또는 PI를 생성하며, 이를 통해 finite-dimensional vector spaces에 대한 ML 기법을 PD에 적용할 수 있게 됩니다. 논문의 PI는 stable하며, 서로 다른 homology 차원은 하나의 벡터로 연결되어 동시에 분석될 수 있습니다.

Background on Persistent Homology

Homology는 대략적으로 말하면 space 내의 hole을 묘사하는 algebraic topological invariant입니다. Topological space $X$의 k-dimensional hole(connected components, loops, trapped volumes (void) 등)은 $X$의 k-th homology group $H_k(X)$라고 불리는 대수적 구조로 인코딩됩니다. 이 group의 rank는 k-th Betti number $β_k$로 불리며, 독립적인 k-dimensioanl holes의 개수를 계산합니다.

 

Topological spaces의 nested sequence $X_1 ⊆ X_2 ⊆ . . . ⊆ X_n$이 주어지면, $i ≤ i'$인 경우에 $X_i ⊆ X_{i'}$의 포함이 대응되어 해당 k-th homology의 linear map $H_k(X_i) → H_k(X_{i'})$이 모든 $k ≥ 0$에 대해 유도됩니다. Persistent homology의 아이디어는 스케일(또는 "시간") 파라미터 $i$가 증가함에 따라 $H_k(X_i)$의 요소를 추적하는 것입니다. Persistent homology 정보를 표현하는 표준 방법은 persistence diagram (PD)으로, 이는 Cartesian plane $\mathbb{R}^2$의 점들로 이루어진 다중 집합입니다. 고정된 homology 차원 k의 선택에 대해서, 각 homological feature는 점 (x, y)로 표현되며, 이 때의 birth indices x와 death indices y는 해당 feature가 처음으로 나타나고 사라지는 스케일 파라미터입니다. 모든 topological features는 탄생한 후에 사라지므로, 필연적으로 각 점은 $y = x$ 대각선 선에 나타나거나 그 위에 위치하겠죠. PD는 이러한 점들의 다중 집합입니다. 서로 다른 topological features가 동일한 birth와 death 좌표를 가질 수 있기 때문입니다. 대각선에 가까운 점들은 종종 noise로 간주되며, 대각선으로부터 더 멀리 떨어진 점들은 더 robust한 topological features를 나타냅니다.

 

논문에서는 두 가지 다른 유형의 입력 데이터에서 PD를 생성합니다.

1. 데이터가 어떤 sapce에서 점의 유한한 집합인 point cloud인 경우, Vietoris–Rips filtration을 사용하여 PD를 생성
2. 데이터가 rael-valued finction인 경우, sublevel set filtration을 사용하여 PD를 생성  

(1은 2의 특수 케이스)
1의 경우, point cloud 데이터는 종종 metric이나 내부 유사성의 측정값과 함께 제공되며, 잠재적인 기하학적 내용을 풍부하게 가지고 있습니다. 데이터에서 기하학적인 형태를 식별하는 하나의 방법은 dataset을 simplicial complex의 virtices로 간주하고, 지정된 크기의 스케일보다 작은 직경(diameter)을 가진 경우에는 edges, triangles, tetrahedra 및 higher-dimensional simplices를 추가하는 것입니다. 이러한 topological space를 Vietoris–Rips simplicial complex라고 합니다. Vietoris-Rips complex의 homology는 스케일의 선택에 중요하게 의존하지만, pesistent homology는 여러 스케일에서 homology를 계산하여 이 선택의 필요성을 제거합니다.

2에서 입력은 domain $X$에서 정의된 real valued function $f : X → \mathbb{R}$입니다. Map $f$의 동작을 이해하는 한 가지 방법은 그의 sublevel set $f^{−1}((−∞, \epsilon])$의 위상을 이해하는 것입니다. $\epsilon$를 증가 시킴으로써, sublevel set filtration이라고 불리는 증가하는 sequence의 topological space를 얻을 수 있습니다. 

두 가지 설정 모두에서 persistent homology 계산은 데이터의 다양한 스케일에 걸쳐 homological features를 인코딩하는 PDs의 모음입니다. $\mathcal{D}$를 모든 PD의 잡합이라고 합시다. 두 PD $B$와 $B'$ 간에 p-Wasserstein distance는 다음과 같이 주어집니다.
$$W_p(B,B') = \inf\limits_{\gamma : B\rightarrow B'}(\sum\limits_{u \in B}||u-\gamma(u)||_{\infty}^p)^{1/p}$$
$1 \leq p \leq \infty$이고 $\gamma$는 $B$와 $B'$ 사이의 bijections입니다. 다른 표준적인 diagram 간 거리 선택은
$$W_∞(B, B') = \inf\limits_{γ:B→B'} \sup\limits_{u\in B} ||u − γ(u)||_{\infty}$$
로 정의됩니다. 이것은 bottleneck distance로 알려져 있습니다. 이러한 metric은 두 dataset 간의 homological characteristic의 유사성(또는 비유사성)을 측정하는 데 사용됩니다.

Persistence Images

PI 변환 과정

논문은 원래의 PD와의 interpretable한 연결을 유지하면서 PD를 벡터로 변환하는 방법을 제안합니다. 위 그림은 혈액 순환 종양 세포의 면역 형광 이미지에서 $\mathbb{R}^5$의 파장 및 공간 정보로 시작하는 데이터에서 PI로의 pipeline을 보여줍니다.

정확하게 말하자면, B를 birth-death 좌표에서의 PD라고 하고, (무한한 persistence를 가지는 features와 관련된 점들은 생략. 예를 들어, 전체 simplicial complex의 연결성과 관련된 $H_0$ feature) $T: \mathbb{R}^2 → \mathbb{R}^2$를 선형 변환으로 정의하면 $T(x, y) = (x, y - x)$이며, $T(B)$는 birth-persistence 좌표에서의 변환된 다중집합이라고 합시다. 여기서 각 점 $(x, y) ∈ B$는 $(x, y - x) ∈ T(B)$에 해당합니다. $\phi_u: \mathbb{R}^2 → \mathbb{R}$은 평균이 $u = (u_x, u_y) \in \mathbb{R}^2$인 미분 가능한 확률 분포라고 할 때, 논문의 모든 applications에서는 이 분포를 평균 $u$와 분산 $σ^2$인 normalized symmetric Gaussian $\phi_u = g_u$로 선택하며 다음과 같이 정의됩니다.
$$g_u(x,y) = \frac{1}{2\pi \sigma^2}e^{-[(x-u_x)^2+(y-u_y)^2]/2\sigma^2}$$

 

수평 축을 따라 0이고, 연속적이며, 구간별 미분가능한 nonnegative weighting function $f: \mathbb{R}^2 → \mathbb{R}$을 고정합니다. 이러한 구성 요소를 사용하여 PD를 평면 상의 스칼라 함수로 변환합니다.

Definition 1

PD B에 대해서, 해당 persistence surface $\rho_B : \mathbb{R}^2 → \mathbb{R}$은 다음과 같은 함수입니다.
$$\rho_B(z) = \sum\limits_{u \in T(B)}f(u)\phi_u(z)$$
Weighting function $f$는 PD에서 persistence surface로의 변환을 stable하게 보장하기 위한 중요한 역할을 합니다.

마지막으로, surface $ρ_B(z)$는 관련 있는 subdomain을 이산화하고 각 영역에서 $ρ_B(z)$를 적분하여 finite-dimensional 벡터로 축소됩니다. 특히, 평면 상에 n개의 박스(픽셀)로 구성된 grid를 고정하고 각 영역에 대해 $ρ_B$의 적분을 할당합니다.

Definition 2

PD B에 대해서, B의 persistence image는 pixels $I(\rho_B)_p = \int\int_p\rho_B dxdy$ 의 모음입니다.

PIs는 서로 다른 homological dimension의 PDs를 하나의 개체로 편리하게 결합하는 방법을 제공합니다. 실제로 실험에서 $H_0, H_1, ..., H_k$의 PDs가 계산되었다고 가정해봅시다. $H_0, H_1, ..., H_k$에 대한 PI 벡터를 연결하여 동시에 모든 homological 차원을 나타내는 단일 벡터로 만들고, 이 연결된 벡터를 ML 알고리즘의 입력으로 사용할 수 있습니다.

PI를 생성할 때 사용자가 만드는 선택 사항은 세 가지입니다. resolution, 분포 (및 관련 매개변수), 그리고 weighting function이다.

Resolution of the images

PI의 resolution은 grid가 PD 위에 겹쳐지는 것에 해당합니다. PI framework에서의 분류 정확도는 resolution 선택에 상당히 robust하고 이는 나중에 실험 결과에서 보여집니다.

The distribution

논문의 방법은 PD의 각 점과 관련된 확률 분포를 선택해야 합니다. 이 논문의 예시는 각 점을 중심으로 한 Gaussian을 사용하지만, 다른 분포도 사용할 수 있습니다. Gaussian 분포는 분산 선택에 따라 달라집니다. 하지만 논문의 실험 결과에서는 분산 선택에 대한 민감도가 낮음을 보여줍니다.

The weighting function

논문의 stability 결과가 성립하려면 weighting finction $f: \mathbb{R}^2 → \mathbb{R}$은 수평 축을 따라(birth-persistence 좌표의 대각선에 해당) 0이어야 하며, 연속적이고, 구간별로 미분 가능해야 합니다. 간단한 선택으로는 weighting function을 수직 persistence 좌표 $y$에만 의존하는 것입니다. 더 높은 persistence를 가진 지점을 더 중요하게 가중시키기 위해 $y$에 대해 증가하는 함수들, 예를 들어 sigmoid 함수와 같은 함수들이 자연스러운 선택입니다. 그러나 특정 applications에서는 작거나 중간 정도의 persistence를 가진 지점들이 ML 작업에 가장 적합할 수 있습니다. 따라서 더 일반적인 weighting function을 사용할 수도 있죠. 논문의 실험에서는, persistence 좌표 $y$에만 의존하는 piecewise linear weighting function $f : \mathbb{R}^2 → \mathbb{R}$를 사용합니다. $b > 0$에 대해서 $w_b:\mathbb{R} → \mathbb{R}$를 다음과 같이 정의합니다.

$$w_b(t)=\begin{cases}0&\text{if } t\leq0\\ \frac{t}{b}&\text{if } 0<t<b, \text{and}\\1&\text{if }t\ge b\end{cases}$$

논문은 $f(x, y) = w_b(y)$를 사용합니다. 여기서 $b$는 실험의 모든 시행에서 가장 persistent가 높은 feature의 persistence 값입니다.

만약 PD의 모든 점에 대해 birth 좌표가 0인 경우 (이는 $H_0$의 경우에 종종 해당), 1차원 분포를 사용하여 (2차원 대신) 1차원 PI를 생성할 수 있습니다. 논문은 이러한 접근 방식을 채택하였습니다.

Stability of Persistence Surfaces and Images

Noise나 측정 오차의 불가피한 존재로 인해 데이터 분석 도구는 input의 perturbation에 대해 stable해야 합니다. 사실, topological data analysis에서 PD의 인기가 높은 이유 중 하나는 데이터 집합을 PD로 변환하는 과정이 bottleneck metric에 대해 안정적이며, 또한 underlying 데이터에 대한 일부 조건을 만족하는 경우 Wasserstein metric에 대해서도 안정적임에 있습니다. 논문에서 이 절에서는 persistence surface와 image가 PD 간의 1-Wasserstein 거리에 대해 안정적이고 그 다음엔 Gaussian 분포를 사용하여 PI를 구성하는 경우 개선된 상수를 사용하여 stability를 증명하는데요. 여기서는 그 내용이 길어 생략하겠습니다. 궁금하신 분들은 논문에서 증명 방법을 찾아 보시길 바랍니다.

Experiments

논문의 PD 벡터 표현의 가치를 평가하기 위해, 저자들은 PD, PL, 그리고 PI의 성능을 비교합니다. 이 비교는 합성 데이터 집합에 대한 분류 작업을 통해 이루어집니다. 이 데이터 집합은 여섯 가지 다른 topological space에서 sampling된 point cloud로 구성되어 있습니다. 비교는 K-medoids 알고리즘을 사용하여 이루어지며, 이는 각 위상 데이터 description의 internal dissimilarity만을 활용하여 분류를 수행합니다. 저자들은 PI가 일관되게 높은 분류 정확도를 제공하며, 더욱이 PI의 계산 시간이 PD들 간의 bottleneck이나 Wasserstein 거리를 계산하는 시간보다 현저히 빠르다는 것을 발견했습니다. 그리고 나서 논문의 PI를 결정하는 매개변수 선택이 분류 정확도에 미치는 영향을 조사할 것입니다. 저자들은 PI resolution과 분포 분산의 특정 선택이 정확도에 미치는 영향이 민감하지 않음을 발견했습니다.

Comparison of PDs, PLs, and PIs using K-medoids Classification

논문의 합성 dataset은 여섯 가지 shape class로 이루어져 있습니다. solid cube (안이 채워진 정육면체), 원, 구, 세 개의 clusters, 세 개의 clusters 내에 세 개의 clusters, torus입니다. 주어진 Gaussian random noise의 수준에 따라 6개의 shape 각각에서 무작위로 sampling된 500개의 noisy point로 구성된 25개의 point cloud를 생성합니다. 이를 통해 총 150개의 point cloud가 생성됩니다. 그런 다음 각 point cloud에 대해 Vietoris–Rips filtration을 사용하여 $\mathbb{R}^3$의 ambient (mbient space: 공간을 둘러싸는 공간) Euclidean metric을 가진 $H_0$ 및 $H_1$ PDs를 계산합니다.

 

논문의 목표는 PDs를 거리 행렬로 변환하는 다양한 방법을 비교하여 데이터에서 추출된 topological features의 근접성을 확인하는 것입니다. 논문은 3가지 representation (PDs, PLs, PIs), 3가지 metric ($L^1, L^2, L^\infty$) (PDs에서 $L^1, L^2, L^\infin$는 1-Wasserstein, 2-Wasserstein, bottleneck 거리로 더 잘 알려져 있다), 2가지 Gaussian noise ($\eta = 0.05,0.1$), 2가지 homological dimensions ($H_0, H_1$)을 사용해 150 x 150 크기의 $3^2\cdot 2^2=36$가지 거리 행렬을 만들었습니다. 이 실험에서는 PIs를 사용할 때, 분산 $σ = 0.1$, resolution 20 × 20 및 앞에서 정의한 weighting function을 사용합니다.

우선, 저자들은 이러한 거리 행렬을 K-medoids clustering을 통해 얼마나 잘 random point cloud를 모양 classes로 분류하는지에 따라 비교합니다. K-medoids는 metric space를 K개의 clusters로 분할하는 알고리즘으로, dataset에서 K개의 points를 선택하여 medoids라고 부르며, 각 metirc space point를 가장 가까운 medoid에 할당합니다. 이런 clustering의 점수는 각 point에서 가장 가까운 medoid까지의 거리의 합입니다. K-medoids가 원하는 출력은 clustering 점수가 최소인 clustering입니다. 이 실험에서는 각 거리 행렬마다 K = 6 (6개 shape classes가 있기 때문에) medoids를 1,000번 random하게 initial하고, Voronoi iteration 방법을 사용하여 각 medoids 선택을 개선하며, 가장 낮은 분류 점수를 가진 clustering을 반환합니다. 각 K-medoids clustering에는 같은 shape class의 medoid에 식별된 random point cloud의 백분율과 동일한 정확도를 할당합니다. 아래 표에서는 각 거리 행렬에 대해 최소 clustering 점수를 가진 K-medoids clustering의 분류 정확도를 보여줍니다.

결과

저자들이 거리 행렬을 생성하는 방법을 비교하는 두 번째 기준은 계산 효율성입니다. 위 표에서는 150개의 사전 계산된 PD를 입력으로 사용하여 각 거리 행렬을 생성하는 데 필요한 시간을 보여줍니다. PL 및 PI의 경우 이 시간에는 각 PD를 대체 표현으로 변환하는 중간 단계와 pairwise 거리 행렬을 계산하는 단계가 포함됩니다.

위 표에서 확인할 수 있듯이, PI 거리 행렬은 거의 모든 PL 거리 행렬보다 더 높은 분류 정확도를 가지며, PD 거리 행렬보다 절반의 시도에서 더 높은 분류 정확도를 가지고 있습니다. 더욱이, PI 거리 행렬의 계산 시간은 bottleneck 또는 p-Wasserstein metrics를 사용하여 PD 거리 행렬을 생성하는 데 필요한 시간보다 훨씬 낮습니다. 이 실험에서, persistence images는 persistent diagrams의 표현을 제공하며 분류 작업에 유용하면서도 계산상 효율적입니다.

Effect of PI Parameter Choice

저자들은 위에서 설명한 shape dataset을 사용하여 생성된 PI의 parameter space를 조사하고 매개변수의 함수로 K-medoids 분류 정확도를 측정합니다. 저자들은 20개의 다른 resolution을 조사하고 (5 × 5에서 100 × 100까지 5의 간격으로 범위 조절), 20개의 다른 분산을 선택하여 Gaussian 함수를 사용한다 (0.01에서 0.2까지 0.01의 간격으로 범위 조절), 그리고 앞 절에서 설명한 weighting function을 사용합니다. 각 매개변수 집합에 대해, 저자들은 homology 차원 $H_0$ 및 $H_1$에 대한 두 집합의 noise level에 대한 최소 clustering 점수로 K-medoids clustering의 분류 정확도를 계산합니다. 저자들은 분류 정확도가 resolution과 분산의 선택에 둔감함을 관찰했습니다. 아래의 그래프는 저자들이 테스트한 분산 및 resolution 범위의 모든 매개변수 조합에 대한 2차원 정확도 표면의 특성입니다. 나중에 다른 연구에서 PIs가 resolution과 분산의 선택에 대해 유사한 robustness를 갖는것을 발견했다고 하네요.

매개변수 선택에 따른 결과

 

여기까지 TDA와 PI의 개념과 유용함을 알아보았습니다. 이제 다음시간에서는 PI를 활용하여 Wafer map defect 패턴을 분류하는 작업을 실제로 적용해보는 방법을 알아보겠습니다.

 

그럼 긴 글 읽어주셔서 감사합니다!