Prototype Selection Using Topological Data Analysis

기술 요약: 위상적 데이터 분석을 이용한 프로토타입 선택

문제 정의
현대적인 분류 파이프라인은 종종 단일 예측 비용보다는 훈련 세트의 크기가 추론 시간에 지배적인 영향을 미치는 병목 현상에 직면한다. 파라미터 모델(예: SVM, Random Forest)은 부담을 훈련 시간으로 전이시키지만, 이들 역시 훈련 인스턴스의 수에 따라 규모가 결정된다. 프로토타입 선택은 훈련 세트를 작고 대표적인 하위 집합으로 압축함으로써 이 문제를 해결한다. 응축(condensation), 편집(edition), 하이브리드(hybrid), 역량 기반(competence-based), 최적화 기반(optimization-based), 클러스터링 기반(clustering-based) 패밀리를 포함한 기존의 프로토타입 선택 분류 체계는 데이터의 위상적 구조를 명시적인 표현 없이 운용한다. 결과적으로, 여러 공간적 척도에 걸쳐 복잡한 구조를 보일 수 있는 클래스 간 결정 경계의 기하학적 구조는 암묵적으로만 포착된다. 본 논문은 데이터의 다중 척도 위상 구조를 프로토타입 선택의 직접적인 기준으로 활용하는 격차를 다룬다.

방법론
저자들은 지속적 호몰로지(persistent homology)라는 위상적 데이터 분석(TDA)의 핵심 도구를 사용하여 프로토타입을 식별하고 유지하는 두 가지 변형된 위상적 프로토타입 선택기(TPS)를 소개한다. 두 방법 모두 Rips 필트레이션(Rips filtration)에 의존하지만, 경계 정보를 인코딩하는 방식에서 차이가 있다.

1. 경계 인식 위상적 프로토타입 선택기 (BoundaryTPS):

   • 메커니즘: 이는 정점 가중치(vertex-weighted) Rips 필트레이션을 사용하는 단일 단계 방법이다. 타겟 클래스 점들에 대해 비타겟 클래스와의 근접성(구체적으로 $k$개의 최근접 비타겟 이웃까지의 거리 합)을 기반으로 가중치를 할당한다.
   • 과정: 경계 지역에 가까운 점들은 낮은 가중치를 받아 필트레이션에 조기에 진입하며, 내부 점들은 높은 가중치를 받아 지연된다. 이를 통해 경계 영역의 위상이 더 미세한 척도에서 해소되도록 보장한다.
   • 선택: 프로토타입은 수명 분포(lifetime distribution)의 특정 분위수를 기준으로 지속성 특징(persistence features)을 식별함으로써 선택된다. 허용 오차 매개변수 $\tau$를 통해 타겟 분위수 주변의 특징 윈도우를 선택함으로써 견고성을 개선할 수 있다.

2. 위상적 프로토타입 선택기 (TPS):

   • 메커니즘: 이는 타겟 및 비타겟 관측치를 모두 포함하는 혼합 포인트 클라우드를 구축함으로써 경계 정보를 암묵적으로 인코딩하는 2단계 방법이다.
   • 1단계 (경계-이웃): 클래스 간 위상 구조를 포착하기 위해 혼합 클라우드에 표준 Rips 필트레이션을 구축한다. 특징은 수명 분포의 분위수를 기준으로 선택되며, 생존한 타겟 클래스 점들이 유지된다.
   • 2단계 (내부): 1단계의 생존자들을 대상으로 내부 위상을 포착하기 위해 두 번째 Rips 필트레이션을 구축한다. 특징은 내부 전형적 샘플을 유지하기 위해 평균 수명을 기준으로 선택된다.
   • 결과: 최종 세트는 1단계의 경계 관련 점들과 2단계의 내부 지원 점들을 결합한다.

주요 기여

• 새로운 기준: 본 논문은 지속적 호몰로지를 프로토타입 선택 기준으로 도입하였으며, 이는 이 분야에서 이전에 활용되지 않았던 능력이다.
• 이중 구현: 혼합 클래스 필트레이션(TPS)을 통한 경계 정보 인코딩과 정점 가중치(BoundaryTPS) 방식이 경험적으로 서로 다른 특성화를 유도함을 보여줌으로써 TPS와 BoundaryTPS를 제시한다.
• 포괄적인 벤치마킹: 두 방법은 15개의 실제 데이터셋과 6개의 다운스트림 분류기에 대해 중첩 교차 검증(nested cross-validation) 하에서 7개의 고전적 베이스라인(CNN, CNN+ENN, DROP3, ICF, IB3, KMeans, SPOTGreedy)과 비교 평가되었다.
• 위상 보존: 본 연구는 위상적 방법들이 밀도 기반 또는 연쇄 결정(chained-decision) 베이스라인보다 $H_1$ 지속성 다이어그램 구조를 훨씬 더 잘 보존함을 입증한다.
• 안정성: 두 방법 모두 테스트된 모든 연쇄 결정 선택기보다 높은 선택 안정성(fold-to-fold Jaccard 유사도로 측정)을 보인다.
• 클래스 불균형: 이 방법들은 레이블 인지 메커니즘을 요구하지 않고 소스 세트의 클래스 비율을 상속받는다.

결과

• 위상적 충실도: BoundaryTPS는 $H_1$ Wasserstein-1 거리에 대해 가장 낮은 평균 Friedman 순위(2.00)를 달 기록하며, 7개 베이스라인 중 5개를 유의미하게 앞질렀다. TPS는 3위(3.60)를 차지했다. 두 방법 모두 루프 구조($H_1$)를 보존하는 성능 스펙트럼의 최상단에 위치하는 반면, 고전적 방법들은 이러한 특징들을 흔히 평탄화시킨다.
• 선택 안정성: TPS는 폴드 간 평균 Jaccard 유사도(0.225)에서 가장 높았고, 그 뒤를 BoundaryTPS(0.202)가 이었다. 두 방법 모두 CNN+ENN(0.057) 및 DROP3(0.080)와 같은 연쇄 결정 방식보다 유의미하게 안정적이었다.
• 분류 성능: 총합 기하 평균(G-Mean) 측면에서 위상적 방법들은 경쟁력이 있으나 선두를 달리는 수준은 아니다. SPOTGreedy와 KMeans가 가장 높은 총합 G-Mean(0.84)을 달성했다. TPS와 BoundaryTPS는 각각 0.79와 0.76을 기록했다. 본 논문은 위상적 방법이 원시 분류 정확도를 압도하지는 않더라도, 구조적 보존과 안정성 측면에서 독특한 설계 지점(design point)을 제공한다고 언급한다.
• 확장성: 경험적으로 두 방법 모두 샘플 크기에 대해 하위 이차(sub-quadratic) 규모로 확장된다.

의의 및 주장
본 논문의 주요 의의는 프로토타입 선택의 패러다임을 순수 기하학적 또는 통계적 휴리스틱에서 다중 척도 위상 불변성에 기초한 프레임워크로 전환하는 데 있다고 주장한다. 저자들은 기존 방법들이 경계 근접성 원리를 암묵적으로 가정하고 있지만, 결정 경계의 복잡한 다중 척도 구조를 해소하는 데는 실패한다고 주장한다. 제안된 방법들은 지속적 호몰로지를 명시적으로 활용함으로써, 밀도 기반 축소 과정에서 흔히 손실되는 루프 및 경계와 같은 데이터의 위상적 "형태"를 정의하는 점들을 유지하는 원칙적인 방법을 제공한다.

저자들은 결과를 겸손하게 평가한다. 즉, 위상적 방법이 다운스트림 분류 정확도(G-Mean)에서 보편적으로 기존 베이스라인을 능가하는 것은 아니지만, 위상적 보존과 선택 안정성 측면에서 우월한 성능을 보임으로써 독특하고 가치 있는 설계 영역을 점유한다는 것이다. 이 연구는 결정 경계의 구조적 무결성이나 선택 과정의 재현성이 매우 중요한 응용 분야에서 위상적 기준이 고전적 접근 방식에 대한 차별화되고 효과적인 대안이 될 수 있음을 시사한다.