When One Point Is Not Enough: Addressing Ambiguous Instances in Dimensionality Reduction by Splitting

기술적 요약: 차원 축소에서 모호한 인스턴스를 분할하여 해결하기

문제 정의
차원 축소 (DR) 는 고차원 데이터를 시각화하는 핵심 도구이지만, 본질적으로 정보 손실이 발생하는 과정입니다. 기존 문헌은 매니폴드 찢어짐과 같은 다양한 왜곡을 분류해 왔으나, 본 논문은 시각적 아티팩트의 새로운 원인인 모호한 인스턴스를 처음으로 지적합니다. 이는 고차원 공간에서 서로 다른 여러 이웃과 매우 유사한 데이터 포인트들을 의미합니다.

기존의 표준 DR 방법은 각 데이터 인스턴스를 시각 공간의 단일 점으로 매핑합니다. 따라서 모호한 인스턴스는 여러 개의 서로 다른 이웃에 대한 소속을 동시에 정직하게 표현할 수 없습니다. 이는 단일 위치로 강제됨으로써 부분적 이웃 임베딩을 초래합니다. 이러한 상태에서 인스턴스는 오직 하나의 이웃 (또는 아예 어느 이웃에도) 에 속하는 것처럼 보이며, 다른 불유사 그룹들과의 진정한 관계를 가립니다. 이 아티팩트는 정확한 이웃 구조를 이해하는 것이 필수적인 설명 가능한 AI(XAI) 나 단일 세포 생물학과 같은 인스턴스 수준의 분석에 특히 문제가 됩니다. 신뢰도 (trustworthiness) 와 연속성 (continuity) 과 같은 기존 지표들은 근본적인 데이터 모호성에 접근하지 못한 채 최종 임베딩만을 기반으로 작동하므로, 부분적 이웃 임베딩을 다른 왜곡과 구별하지 못합니다.

방법론
저자들은 모호한 인스턴스를 "분할"하여 각각의 이웃 내에 배치함으로써 이러한 모호성을 식별하고 해결하는 그래프 기반 접근법을 제안합니다. 이 방법론은 Paulovich 등이 소개한 관계 및 매핑의 2 단계 DR 프레임워크를 따릅니다:

1. 그래프 구성 및 희소화:

   • 고차원 관계는 무방향 가중 그래프 $G$로 모델링됩니다.
   • 의미 있는 이웃 구조를 드러내고 우발적 근접성으로 인한 중복 간선을 제거하기 위해, 저자들은 Spielman-Srivastava 알고리즘을 사용한 스펙트럴 희소화를 적용합니다. 이는 원래 그래프의 구조적 및 대수적 속성을 유지하면서 약한 연결을 제거한 축소된 그래프 $\bar{G}$를 생성합니다.

2. 모호한 인스턴스 식별:

   • 모호성은 위상학적으로 정의됩니다. 저자들은 국소 아티큘레이션 포인트 (LAPs) 개념을 적용합니다. 정점 $v$를 제거했을 때 국소 $r$-단계 유도 이웃 내의 연결 성분 수가 증가하면, 해당 정점은 LAP 로 간주됩니다.
   • 인스턴스가 희소화된 그래프 $\bar{G}$에서 LAP 일 경우, 해당 인스턴스는 모호한 것으로 간주됩니다. 이는 그렇지 않으면 분리되었을 서로 다른 이웃들을 연결하고 있음을 나타냅니다.
   • Lemma 3.1 은 계산을 최적화하는 데 활용됩니다: 특정 반경 $r$에서 정점이 LAP 가 아니라면, 더 큰 반경 $r' > r$에서도 LAP 가 될 수 없습니다.

3. 정점 분할 및 결정 규칙:

   • 모호한 정점 $v_i$가 식별되면, $v_i$가 국소 이웃에서 제거된 후 남는 연결 성분의 수에 해당하는 $K$개의 복사본으로 분할됩니다.
   • 결정 규칙: 모든 잠재적 분할이 실행되는 것은 아닙니다. 이 접근법은 다음을 필터링합니다:
     • LAP-LAP 연결: 두 이웃을 연결하는 간선의 양쪽 끝점이 모두 LAP 인 경우, 인위적인 고립을 방지하기 위해 분할을 억제합니다.
     • 약한 연결: 사용자 정의 임계값 $\tau_w$(연결 강도와 가장 강한 성분 간의 비율) 는 이웃과의 연결이 의미 있을 정도로 충분히 강하지 않은 분할을 필터링합니다. 이는 불충분한 인력 힘으로 인해 시각적으로 고립된 점들이 생성되는 것을 방지합니다.

4. 매핑 및 시각화:

   • 분할된 정점을 포함하는 수정된 그래프는 표준 국소 DR 기법 (예: UMAP 또는 ForceAtlas2) 을 사용하여 시각 공간으로 투영됩니다.
   • 시각 인코딩: 분할된 인스턴스는 원래 위치나 서로를 연결하는 점선으로 연결된 별개의 마커 (예: 십자 표시) 로 렌더링되어, 분석가가 단일 데이터 포인트의 여러 이웃 소속을 추적할 수 있도록 합니다.

주요 기여

• 부분적 이웃 임베딩의 정의: 본 논문은 모호한 인스턴스로부터 발생하는 특정 아티팩트를 공식적으로 도입하고 정의하여 일반적인 DR 왜곡과 구별합니다.
• 그래프 이론적 탐지: 희소화된 이웃 그래프上的 국소 아티큘레이션 포인트를 사용하여 모호한 인스턴스를 식별하는 방법을 제시합니다.
• 분할 메커니즘: 저자들은 모호한 인스턴스를 분할하여 투영에서 여러 이웃 소속을 반영하는 구체적이고 거의 선형 시간 복잡도를 가진 접근법을 제안합니다.
• 실증적 검증: 이 접근법은 다양한 데이터셋 (SVHN, MNIST, 텍스트 코퍼스, 단일 세포 RNA 시퀀싱) 에서 입증되었으며, 표준 투영에서는 보이지 않는 숨겨진 이웃 소속을 드러냄을 보여줍니다.

결과

• 정성적 통찰: SVHN 데이터셋에서 표준 UMAP 에서는 '7'로 잘못 분류된 숫자 '1'이 오직 '7' 이웃에만 속하는 것으로 나타났습니다. 제안된 접근법은 해당 인스턴스를 분할하여 '1' 이웃과의 동시 유사성을 드러냄으로써 분류기 오류의 모호성을 설명했습니다. 마찬가지로 텍스트 데이터에서 "독성학용 ILP 지원 모델"에 관한 논문은 ILP 및 사례 기반 추론 (CBR) 클러스터 모두에 속하는 것으로 나타났으며, 이는 표준 투영에서는 가려진 이중성이었습니다.
• 정량적 분석:
  • 희소화 영향: 보존된 $k$-최근접 이웃 ($k$NN) 을 측정한 실험 결과, 스펙트럴 희소화는 대부분의 데이터셋에서 비율이 1 에 가까울 정도로 원본 그래프와 비교 가능한 국소 이웃 구조를 유지하지만, 고내재차원 단일 세포 데이터에서는 일부 변동이 관찰되었습니다.
  • 지표의 한계: 신뢰도와 연속성과 같은 표준 지표는 모호한 인스턴스를 식별하는 데 비효율적인 것으로 나타났는데, 이러한 점들은 지표 분포 전체에 걸쳐 모호하지 않은 점들과 유사하게 분포하기 때문입니다.
  • 매개변수 민감도: 초기 그래프의 이웃 수를 늘리면 일반적으로 탐지된 분할 수가 감소했는데, 이는 증가된 연결성이 그렇지 않으면 분리되어 보일 이웃들을 연결하기 때문입니다.

의의 및 주장
본 논문은 DR 에서 미세한 국소 구조를 해석하기 위해 모호성을 인식하는 것이 필수적이라고 주장합니다. 저자들은 모호한 인스턴스를 고려하지 않으면 인스턴스 수준의 맥락이 중요한 XAI 및 생물학과 같은 분야에서 불완전하거나 잘못된 해석으로 이어질 수 있다고 주장합니다. 이러한 인스턴스를 분할함으로써 이 방법은 데이터의 고차원 위상에 대한 더 정직한 표현을 제공하며, "이전에 숨겨졌던 이웃 소속"을 드러냅니다. 이 연구는 현재 DR 품질 지표가 이러한 특정 유형의 아티팩트에는 부적절하며, 향후 평가 프레임워크는 매핑으로 인한 불안정성뿐만 아니라 데이터 기반 모호성도 고려해야 함을 시사합니다.