Unreduced Persistence Diagrams for Topological Machine Learning

본 논문은 축약되지 않은 지속성 다이어그램(unreduced persistence diagrams)에서 유도된 위상적 특징을 활용하는 머신러닝 파이프라인이 완전히 축약된 다이어그램을 사용하는 것과 대등하거나 더 나은 성능을 달성할 수 있는 동시에, 계산 비용과 메모리 효율성 측면에서 상당한 이점을 제공한다는 것을 입증한다.

핵심

당신이 컴퓨터에게 원, 구(sphere), 도넛(torus)의 차이를 구별하는 법을 가르치려 한다고 상상해 보십시오. 이를 위해 수학자들은 **지속성 호몰로지(Persistent Homology)**라는 도구를 사용합니다. 이것은 점들의 구름(cloud of points)을 보고 "구멍이 어디에 있는가? 루프는 어디에 있는가?"라고 묻는 '위상학적 스캐너'와 같습니다.

이 스캐너는 **지속성 다이어그램(Persistence Diagram, PD)**이라는 보고서를 생성합니다. 이 보고서는 특징(예: 구멍) 하나하나가 나타나서 사라지기 전까지 얼마나 오랫동안 "지속"되었는지를 보여주는 점들의 목록입니다.

문제점: 비용이 많이 드는 보고서

전통적으로, 이 보고서를 얻기 위해서는 컴퓨터가 "축약(reduction)"이라는 엄청난 양의 힘든 작업을 수행해야 합니다. 이는 마치 사서가 중복을 제거하고 완벽한 요약본을 찾기 위해 모든 책을 다른 모든 책과 일일이 대조하며 도서관을 정리하는 것과 같습니다. 이 과정은 다음과 같은 특징을 가집니다:

1. 느림: 시간이 매우 많이 걸립니다.
2. 메모리 집약적: 엄청난 양의 컴퓨터 RAM(메모리)을 요구합니다.
3. 낭비적: 저자들은 이상한 점을 발견했습니다. 이 상세한 보고서들을 머신러닝 모델에 입력했을 때, 모델들이 대부분의 정보를 무시한다는 사실이었습니다. 그것은 마치 사서가 이야기를 이해하기 위해 단 세 문장만 필요함에도 불구하고, 500페이지짜리 요약본을 쓰기 위해 몇 시간을 허비한 것과 같았습니다.

해결책: "축약되지 않은" 스케치

저자들은 단순한 질문을 던졌습니다. 만약 우리가 이 무거운 편집 과정을 통째로 건너뛴다면 어떻게 될까?

완벽하고 최종적인 보고서를 얻기 위해 전체 "축약" 과정을 거치는 대신, 그들은 **축약되지 않은 지속성 다이어그램(Unreduced Persistence Diagrams)**을 사용하는 것을 제안합니다.

• 비유: 당신이 얼굴을 스케치한다고 상상해 보십시오. "축약된" 방식은 전문 화가가 선 하나하나를 다듬고, 실수를 지우고, 명암을 완벽하게 조절하며 그림을 완성하는 데 몇 시간을 쓰는 것과 같습니다. "축약되지 않은" 방식은 정교하게 다듬거나 지우는 과정 없이, 원시 데이터로부터 눈, 코, 입 같은 주요 특징들을 빠르게 스케치하는 것과 같습니다.
• 결과: 놀랍게도, 컴퓨터(머신러닝 모델)는 완벽한 걸작보다 이 빠른 스케치만으로도 얼굴을 똑같이 잘 인식할 수 있는 경우가 많았습니다.

그들이 한 일

팀은 이 무거운 편집 과정을 건너뛰는 새로운 버전의 소프트웨어(인기 있는 도구인 Ripser를 기반으로 함)를 구축했습니다. 이 소프트웨어는 전체 보고서를 만드는 대신, 이러한 "스케치"(그들은 이를 Unreduced Diagrams 또는 Low-Ones, Quasi-Apparent Pairs와 같은 특정 유형이라 부릅니다)를 생성합니다.

그들은 세 가지 도전 과제를 통해 이를 테스트했습니다:

1. 형태 인식: 노이즈가 섞인 데이터에서 원, 구, 도넛을 구별하기.
2. 이미지 분류: 패션-MNIST 데이터셋을 사용하여 의류 아이템(예: 샌들 vs 운동화) 식별하기.
3. 뇌 스캔 회귀: 뇌 혈관의 구조를 바탕으로 사람의 연령 예측하기.

연구 결과

1. 성능: 거의 모든 테스트에서, "스케치"(축약되지 않은 다이어그램)로 학습된 모델은 "정교한 보고서"(완전히 축약된 다이어그램)로 학습된 모델만큼 성능이 좋았거나, 때로는 오히려 더 나은 성능을 보였습니다.
2. 속도 및 메모리: 이것이 가장 큰 승리입니다. 무거운 편집 과정을 건너뛰었기 때문에:
   • 새로운 방식은 현저히 적은 메모리(때로는 최대 13배 적게)를 사용했습니다.
   • 특히 여러 컴퓨터 코어를 동시에 사용하는 병렬 처리 시 훨씬 빠르게 작동했습니다.
   • 한 극단적인 사례에서는 기존 방식은 메모리가 부족하여 충돌(crash)이 발생했지만, 새로운 방식은 작업을 성공적으로 마쳤습니다.

주의점 (안정성)

저자들은 이러한 "스케치"가 "정교한 보고서"보다 노이즈에 조금 더 민감하다는 점을 인정합니다. 데이터를 너무 심하게 흔들면, 정교한 보고서보다 스케치의 형태가 더 급격하게 변할 수 있습니다. 하지만 현실적인 수준의 노이즈가 있는 실험 환경에서, 이 스케치들은 충분히 유용할 만큼 안정적이었습니다.

결론

이 논문은 토폴로지컬 머신러닝(Topological Machine Learning)의 세계에서, 우리가 데이터 보고서를 "완벽하게" 만들기 위해 너무 많은 시간과 컴퓨터 자원을 낭비하고 있을지도 모른다는 점을 시사합니다. 축약되지 않은 지속성 다이어그램을 사용함으로써, 우리는 훨씬 빠르고 적은 메모리로 "충분히 좋은" 요약본을 얻을 수 있으며, 컴퓨터는 그것으로부터 똑같이 효과적으로 학습할 수 있습니다. 이것은 트레이드오프(trade-off)입니다. 약간 거친 스케치를 얻는 대신, 속도와 효율성에서 막대한 이득을 얻는 것입니다.

기술 요약

기술 요약: 위상적 머신러닝을 위한 비축소 지속성 다이어그램 (Unreduced Persistence Diagrams)

문제 정의

위상적 데이터 분석(TDA)과 지도 학습 기반 머신러닝(ML)의 결합은 생물학, 신경과학, 재료 과학 등 다양한 분야에서 복잡한 데이터를 분석하는 표준적인 접근 방식이 되었습니다. 표준 파이프라인은 지속성 호몰로지(Persistent Homology, PH)를 계산하여 지속성 다이어그램(Persistence Diagrams, PDs)을 생성하고, 이 다이어그램을 벡터화한 후 ML 모델을 학습시키는 과정을 포함합니다.

그러나 이 파이프라인에서 두 가지 결정적인 비효율성이 관찰되었습니다:

1. 정보 중복성: 경험적 증거에 따르면, ML 모델은 벡터화된 PD에 포함된 정보의 상당 부분을 무시하는 경향이 있습니다. 예를 들어, 회귀 작업에서는 28번째로 지속성이 높은 점의 지속성만 사용하더라도 "최적에 가까운" 성능을 보였으며, 벤치마크 결과에 따르면 단순한 통계적 벡터화가 복잡한 벡터화만큼이나 성능이 좋다는 것이 밝혀졌습니다.
2. 계산 비용: 완전히 축소된(fully reduced) PD를 계산하는 것은 파이프라인에서 가장 많은 메모리와 시간을 요구하는 단계이며, 특히 대규모 데이터셋의 경우 매우 까다롭습니다.

본 연구의 핵심 가설은 만약 ML 모델이 정보를 버리는 방식의 벡터화로도 충분히 좋은 성능을 낼 수 있다면, PH의 전체 계산 과정(특히 경계 행렬의 축소 과정)이 불필요한 계산 비용일 수 있다는 것입니다. 저자들은 경계 행렬의 완전한 축소 과정을 거치지 않고, 비축소 경계 행렬(unreduced boundary matrices)로부터 직접 유도된 **비축소 지속성 다이어그램(unreduced persistence diagrams)**을 활용함으로써 이를 해결할 것을 제안합니다.

방법론

이론적 프레임데워크

저자들은 표준적인 열 단위 축소 알고리즘(column-wise reduction algorithm)을 수행하지 않고 경계 행렬 $M$으로부터 구성되는 여러 유형의 **비축소 지속성 다이어그램(PD)**을 정의합니다. 이들은 행렬 열의 특성에 따라 다음과 같이 정의됩니다:

• Apparent Pair (AP) PD: $(low(M_j), j)$ 쌍들로, 열 $j$의 가장 낮은 비제로(non-zero) 항목이 왼쪽의 유일한 비제로 항목인 경우(축소 없이도 나타나는 특정 패턴)를 의미합니다.
• Lower Quasi-Apparent Pair (qAP↓) PD: $\beta(M_j) \neq -1$인 $(low(M_j), j)$ 쌍들입니다.
• Upper Quasi-Apparent Pair (qAP↑) PD: $\beta(M_j) \neq -1$인 $(\beta(M_j), j)$ 쌍들입니다. 여기서 $\beta(M_j)$는 축소에 의해 제거될 수 없는 열 $j$의 가장 높은 행 인덱스입니다.
• Low-Ones (L1) PD: $low(M_j) \neq -1$인 모든 열에 대한 쌍 $(low(M_j), j)$의 멀티셋(multiset)입니다.

L1과 qAP↑ 구성 방식은 특히 Vietoris-Rips(VR) 복합체에 대해 강조되는데, 다른 비축소 유형들은 이러한 여과(filtration) 방식에서 고차원 호몰로지에 대해 덧없는 쌍(ephemeral pairs, 지속성이 0인 쌍)만을 생성할 수 있기 때문입니다.

안정성 분석 (Stability Analysis)

본 논문은 이러한 변환들이 보틀넥 거리($d_B$)에 대해 리프시츠 안정성(Lipschitz stability)을 갖는지 조사합니다.

• 이론적 결과: 완전히 축소된(FR) PD 변환은 리프시츠 상수 $C=1$을 갖는 전역적 안정성을 가집니다. 반면, 비축소 PD(AP, qAP)는 일반적으로 전역적으로 안정적이지 않습니다. 여과 함수(filtration function)의 미세한 섭동(perturbation)이 경계 행렬의 열 순서를 변경하여, 나타나는 쌍(apparent pairs)의 출현이나 소멸을 초래함으로써 조합론적 불안정성을 일으킬 수 있습니다.
• 국소적 안정성: 저자들은 비축소 PD가 국소적으로 리프시츠 안정성을 가짐을 증명합니다. 섭동이 심플렉스의 순서를 유지할 만큼(구체적으로 인접한 여과 값 사이의 최소 간격보다 작을 만큼) 충분히 작다면, 변환은 안정적으로 유지됩니다.
• 실험적 안정성: 섭동된 점 구름(point clouds)에 대한 계산 실험 결과, 다이어그램 내 점의 개수가 변하는 큰 불안정성 스파이크가 발생하기는 하지만 이는 드문 현상이었습니다. 대부분의 섭동은 완전히 축소된 경우와 비슷하거나 더 나은 수준의 안정성 비율을 보였습니다.

계산 구현

계산적 이점을 벤치마킹하기 위해, 저자들은 VR 복합체에 대한 qAP↑ 다이어그램을 계산하는 수정된 Ripser 알고리즘을 구현했습니다.

• 병렬화: 열을 순차적으로(왼쪽에서 오른쪽으로) 처리하는 표준 축소 알고리즘과 달리, qAP↑ 다이어그램 계산은 여과 코바운더리(coboundary) 행렬의 열들을 독립적으로 탐색함으로써 병렬화가 가능합니다.
• 메모리 효율성: 이 구현 방식은 축소를 위해 필요한 전체 경계 행렬과 작업 경계(working boundaries)를 저장하는 것을 피합니다. 해시 맵(hash map)을 사용하여 쌍을 저장하고, "제로 어피어런트 페어(zero apparent pairs, 덧없는 쌍)"를 조기에 건너뜁니다.

주요 결과

계산 성능

32코어 AMD Ryzen Threadripper PRO 시스템에서 표준 Ripser와 비교한 벤치마킹 결과, 상당한 이점이 확인되었습니다:

• 실행 시간(Wall Time): 병렬화된 qAP↑ 계산은 완전한 지속성 계산에 비해 평균 20배 빠른 속도를 달 기록했습니다.
• 메모리: 비축소 방식은 임계값(thresholded)이 설정되지 않은 예제의 경우 Ripser 대비 약 1/13, 임계값이 설정된 예제의 경우 약 1/1.86의 메모리만을 사용했습니다.
• 확장성: 저자들은 Ripser가 메모리 제한(300GB 이상의 RAM 필요)으로 인해 실패했던 torus4 데이터셋(50,000개 점)에 대해 비축소 다이어그램을 성공적으로 계산했습니다. cyclo-octane 데이터셋의 경우, qAP↑ 계산은 Ripser보다 454배 적은 메모리와 59.5배 적은 실행 시간을 사용했습니다.

머신 러닝 성능

저자들은 비축소 PD(L1, qAP, AP)의 벡터화에 대해 훈련된 랜덤 포레스트 분류기 및 회귀 모델의 성능을 세 가지 작업에 대해 완전히 축소된(FR) PD와 비교 평가했습니다:

1. 합성 도형 분류: 다양한 노이즈 수준을 가진 점 구름(원, 구, 토러스 등) 분류.
2. Fashion-MNIST 분류: 입방 복합체(cubical complexes)를 이용한 의류 이미지 분류.
3. 뇌 동맥 트리 회귀: 3D 뇌 스캔 데이터를 통한 피험자 연령 예측.

발견 사항:

• 대등함 및 개선: 모든 실험에서 적어도 하나의 비축소 PD 유형이 완전히 축소된 PD와 대등하거나 더 나은 성능을 보였습니다.
• L1의 우수성: L1 다이어그램은 일관되게 FR 다이어그램과 대등하거나 이를 능가하는 성능을 보였습니다. Fashion-MNIST 작업에서 L1 다이어그램은 FR 다이어그램보다 평균 정밀도(average precision) 면에서 최소 10 퍼센트 포인트 더 높은 성능을 보였습니다.
• 강건성: 이러한 결과는 다양한 여과 유형(Alpha, Rips), 벡터화 방법(Persistence Images, Adcock-Carlsson coordinates), 그리고 노이즈 수준에 걸쳐서도 견고하게 나타났습니다.
• 특징 중요도: Fashion-MNIST 작업에 대한 분석 결과, L1과 FR 모델은 지속성 이미지 공간의 서로 다른 영역에 의존한다는 것이 밝혀졌습니다. L1 모델의 가장 중요한 특징들은 $H_0$(연결 성분)에 집중되어 있었던 반면, FR 모델은 $H_0$와 $H_1$ 모두의 특징을 더 균등하게 활용했습니다. 이는 비축소 다이어그램이 완전한 축소 과정에서 버려지는, 잠재적으로 유용한 독특한 정보를 인코딩하고 있음을 시사합니다.

의의 및 주장

본 논문은 비축소 지속성 다이어그램이 지속성 머신 러닝 파이프라인에서 완전히 축소된 다이어그램의 효과적인 대체제가 될 수 있음을 결론짓습니다.

• 계산 효율성: 축소 단계를 피함으로써 실무자들은 메모리 사용량과 계산 시간을 크게 줄일 수 있으며, 이를 통해 기존의 표준 PH 방식으로는 다루기 힘들었던 데이터셋을 분석할 수 있게 됩니다.
• 성능: 축소가 품질을 위해 필수적이라는 가정과 달리, 저자들은 축소 과정에서 버려지는 정보가 다운스트림 ML 성능에 결정적이지 않을 수 있으며, 오히려 비축소 다이어그램이 독특하고 유익한 특징을 포착할 수 있음을 입증했습니다.
• 향 향후 연구 방향: 저자들은 비축소 다이어그램이 계산 시간은 절약하지만, 점의 개수가 많아져 벡터화 과정이 더 느려질 수 있다고 언급했습니다. 따라서 향후 연구는 모든 쌍을 명시적으로 저장하지 않고 비축소 행렬로부터 직접 벡터화를 계산하는 알고리즘을 설계하여 파이프라인을 더욱 최적화하는 데 집중해야 한다고 제안합니다.

이 연구는 PH-ML 파이프라인을 구축할 때, 수학적 완전성(완전히 축소된 다이어그램)보다는 계산 효율성과 "가공되지 않은(raw)" 위상적 특징의 보존을 우선시하는 방향으로의 전환 가능성을 제시하며 신중하게 결론을 맺고 있습니다.