기술 요약: 기대 지속성 다이어그램의 적응형 벡터화를 위한 보로노이 히스토그램 (Voronoi Histograms for Adaptive Vectorization of Expected Persistence Diagrams)

1. 문제 정의

위상 데이터 분석(TDA)은 점 구름(point clouds)의 위상적 특징을 포착하기 위해 지속성 호몰로지(Persistent Homology, PH)를 활용하며, 이는 지속성 다이어그램(Persistence Diagrams, PD)으로 인코딩된다. PD는 $(b, d)$ 형태의 점들을 개방된 반평면 $\Omega$에 나타내며, 여기서 $b$와 $d$는 각각 탄생(birth) 및 소멸(death) 시간을 의미한다. 그러나 PD는 표준 머신러닝 알고리즘의 입력으로 직접 사용할 수 없으므로, 벡터화 과정이 필수적이다.

PD를 사용하는 데 있어 주요 병목 현상은 높은 계산 복잡도이다. PD를 얻는 과정은 $O(m^3)$ 또는 1차원 특징의 경우 심지어 $O(|X|^9)$에 달할 수 있다. 이를 완화하기 위해 **기대 지속성 다이어그램(Expected Persistence Diagram, EPD)**이 개발되었다. EPD는 점 구름의 여러 하위 샘플 집합으로부터 얻은 PD들을 평균하여 도출된 위상적 특징의 분포이다. EPD는 시간 비용을 줄여주지만, 기존의 EPD 벡터화 방법들(Persistence Images, Persistence Silhouettes, Persistence Landscapes 등)은 사전 정의된 연속적인 점 변환 함수(예: 가우시안 커널 또는 랜드스케이프 함수)와 고정된 이산화 그리드에 의존한다. 이러한 방식은 매끄러움(smoothness), 대역폭(bandwidth), 그리드 해상도에 관한 설계 선택을 강요하며, 이는 $(birth, death)$ 평면에서의 국소적 질량 차이를 흐리게 하거나 최적이 아닌 영역을 강조할 수 있다.

본 논문은 명시적인 매끄러운 점 변환 모델을 피하고, 대신 **적응형, 데이터 의존적 분할(adaptive, data-dependent partitioning)**을 사용하여 EPD 분포를 표현하는 대안적인 벡터화 방법을 다룬다.

2. 방법론: 보로노이 기반 표현 (Vrep)

저자들은 경험적 EPD를 위상적 특징의 분포로 취급하고, **보로노이 다이어그램(Voronoi Diagrams)**을 기반으로 한 히스토그램을 사용하여 이를 표현하는 벡터화 방법인 Vrep를 제안한다.

핵심 메커니즘

1. 코드북 샘플링(Codebook Sampling): 고정된 그리드 대신, Vrep는 무작위 코드북 $S$의 집합을 구축한다. 각 코드북 $C = \{c_1, ..., c_k\}$는 EPD의 지지 집합(support)에서 샘플링된 점들로 구성된다.
2. 보로노이 분할(Voronoi Partitioning): 주어진 코드북 $C$에 대해, 개방된 반평면 $\Omega$는 보로노이 셀 $V(c_i)$로 분할된다. 각 셀은 다른 $c_j$보다 $c_i$에 더 가까운 점들을 포함한다.
3. 히스토그램 구축: 표현식 $\Phi(\bar{\mu}, C)$는 각 보로노이 셀에 떨어지는 EPD $\bar{\mu}$의 정규화된 질량의 벡터로 정의된다:
   $$\Phi(\bar{\mu}, C) = [\bar{\mu}(V(c_1)), \bar{\mu}(V(c_2)), ..., \bar{\mu}(V(c_k))]$$
4. 집계(Aggregation): 최종 표현식 $\hat{\Phi}(\bar{\mu})$를 형성하기 위해, 데이터셋에서 샘플링된 여러 코드북으로부터 생성된 히스토그램을 결합한다.
5. 대각선 인식 변형(Diagonal-Aware Variant, Vrepd): 특정 변형인 Vrepd는 대각선 $\partial\Omega$ (즉, $b=d$인 지점)를 중심으로 하는 보로노이 셀을 포함한다. 이는 노이즈(대각선 근처의 특징)를 유의미한 위상적 특징과 분리하는 데 매우 중요하다.

코드북 샘플링 전략

논문은 코드북 내의 점을 샘플링하는 세 가지 전략을 평가한다:

• Default (기본): EPD 지지 집합으로부터 균일하게 샘플링.
• Persistence-Weighted (지속성 가중치): 지속성($d-b$)에 따라 가중치를 두어 샘플링하며, 유의미한 특징을 우선시함.
• Uniform (균일): 대각선 상단의 고정된 직사각형 영역에서 샘플링 (EPD와 무관함).

정규화

방법론은 EPD를 단위 $l_1$-노름으로 정규화한다 ($\bar{\mu} \leftarrow \bar{\mu}/\bar{\mu}(\Omega)$). 이는 EPD를 확률 분포로 취급하여 모든 EPD가 동일한 질량을 갖도록 보장하며, 이를 통해 안정성 분석 및 유사도 측정을 위해 Wasserstein 거리를 직접 사용할 수 있게 한다. 이는 Optimal Partial Transport 메트릭을 사용할 필요를 없애준다.

3. 이론적 기여

본 논문은 특정 조건 하에서 Vrep의 안정성과 표현 능력에 대한 이론적 보증을 확립한다:

• 안정성 경계(Stability Bounds): 저자들은 EPD의 섭동(perturbation)에 대해 Vrep가 안정적임을 증명한다. 구체적으로, EPD가 $\Delta$-섭동(Dirac 질량의 미세한 이동)을 겪을 때, Vrep 표현의 변화는 $\Delta$에 대해 립시츠 연속(Lipschitz continuous)이다. 오차 경계는 코드북 크기 $k$와 데이터셋의 특성에 따라 달라진다.
• Wasserstein 관련 경계: 논문은 두 Vrep 벡터 사이의 $l_1$ 거리와 밑바탕이 되는 EPD 간의 Wasserstein 거리($W_1$) 사이의 조건부 하한을 제공한다.
  $$\|\Phi(\bar{\mu}, C) - \Phi(\bar{\nu}, C)\|_1 \geq \frac{W_1(\bar{\mu}, \bar{\nu}) - \text{approximation errors}}{d_{max}(C)}$$
  이 결과는 코드북이 "잘 분해되어 있을 때"(즉, 근사 오차가 분포 간의 분리보다 작을 때) Vrep가 Wasserstein 규모의 변화를 효과적으로 보존한다는 점을 명확히 한다. 이는 일반적인 단조적 보존 보장이 아니라 조건부 일관성 진술이다.

4. 실험 결과

저자들은 지도 학습 기반 점 구름 분류 및 비지도 학습 기반 차원 축소 작업에서 Vrep와 Vrepd를 Persistence Image (PI), Persistence Silhouettes (PS), Persistence Landscape (PL), 그리고 엔드 투 엔드 네트워크인 PointNet과 비교하여 평가하였다.

분류 성능

• 데이터셋: 단백질 구조, CAD 기계 부품, 시계열 데이터(time-delay embedding을 통해 점 구름으로 변환됨)를 포함한 다양한 데이터셋에서 실험을 수행하였다.
• 결과: Vrep와 Vrepd는 대부분의 위상 민감 데이터셋에서 PI, PS, PL에 비해 높거나 대등한 분류 정확도(Random Forest 분류기 사용)를 일관되게 달성하였다.
  • Protein 데이터셋에서 Vrep는 98.5%의 정확도를 달성하였다 (PI의 95.5% 대비).
  • CAD 데이터셋에서 Vrep와 Vrepd는 다른 비지도 방법들보다 우수한 성능을 보였으나, 일부 노이즈 환경에서는 PI도 경쟁력 있는 결과를 보였다.
• 코드북 민감도: Persistence-weighted 코드북 샘플링 전략은 특히 노이즈가 많은 환경에서 가장 좋은 결과를 자주 보여주었는데, 이는 유의미한 위상적 특징에 표현을 집중시키기 때문이다.

안정성 및 확장성

• 섭동 안정성: 3D 동역학 시스템 데이터셋을 이용한 실험에서 Vrep는 가우시안 노이즈 섭동에 대해 안정적임을 보였다. 흥로도, 대각선 셀을 포함한 Vrepd가 Vrep보다 약간 더 높은 안정성을 보였는데, 이는 대각선 근처의 노이즈를 더 잘 분리하기 때문인 것으로 보인다.
• 시간 복잡도:
  • Vrep의 시간 복잡도는 데이터셋 크기가 $m$일 때 $O(m^2tk)$이며, 여기서 $t$는 코드북의 수, $k$는 코드북의 크기이다. 이는 데이터셋 크기에 대해 이차적(quadratic)이다.
  • 그러나 실제 실행 시간 측면에서 Vrep는 PL 및 PS보다 빠르며, 샘플링된 PD의 수($n$)에 따라 더 잘 확장된다. 이는 PI/PS/PL이 모든 샘플된 PD를 개별적으로 처리해야 하는 반면, Vrep는 EPD 지지 집합을 고정된 크기로 하위 샘플링하기 때문이다.
  • PointNet(지도 학습)이 높은 정확도를 달로 달성했지만, Vrep는 차원 축소와 같은 비지도 작업에서 적용 가능한 경쟁력 있는 대안을 제공한다.

비지도 차원 축소

동역학 시스템 데이터셋에 대한 t-SNE 시각화 작업에서, Vrep는 PI(569)와 PL(1655)보다 더 높은 Calinski-Harabasz (CH) 지수(1751)를 가진 클러스터를 생성하였으며, 이는 더 우수한 클러스터 분리 능력을 나타낸다.

5. 의의 및 주장

본 논문은 Vrep를 기존 방법들의 보편적인 대체제가 아닌 보완적인 표현 방식으로 위치시킨다.

• 적응형 vs. 매끄러운 방식: 주요 기여는 매끄러운 커널 기반 함수 근사에서 적응형, 데이터 의존적 카운팅으로의 전환이다. Vrep는 데이터 자체에 의해 정의된 셀 위에 질량을 집계하며, 이는 EPD의 경험적 질량 할당을 잠재적으로 더 충실하게 반영한다.
• 트레이드오프: 저자들은 명시적으로 트레이드오프를 인정한다: Vrep는 **거친 질량 할당(coarse mass allocation)**을 효율적으로 요약하지만, 보로노이 셀 내부의 **미세한 기하학적 구조(fine-grained geometry)**에 대해서는 본질적으로 손실이 발생한다. 따라서 매끄러운 방법(PI나 커널 방법 등)은 셀 내부의 미세한 국소적 변화나 형상 변화가 중요한 위상적 변동을 다룰 때 Vrep보다 더 나은 성능을 보일 수 있다.
• 비지도 유용성: Vrep의 핵심적인 의의는 비지도 학습 작업에 대한 적용 가능성이다. PointNet이나 PersLay와 같은 지도 학습 기반 딥러닝 접근 방식과 달리, Vrep는 특징 추출을 위해 레이블을 요구하지 않으므로 차원 축소 및 클러스터링 작업에 적합하다.
• 겸허한 주장: 저자들은 Vrep가 모든 벡터화 방법을 압도한다고 주장하지 않는다. 특정 데이터셋(예: CAD)에서는 커널 방법(PWGK, SWK)이 Vrep보다 뛰어날 수 있지만, 훨씬 더 높은 계산 비용이 든다는 점을 언급한다. 결론적으로, Vrep는 샘플링된 PD의 수에 따라 유리한 확장성을 제공하며, 위상 민감 분류에 적합한 독특한 근사 편향(approximation bias)을 가진 경쟁력 있는 적응형 대안이다.