Optimizing Multidimensional Scaling in Gini Metric Spaces

기술 요약: 지니 거리 공간에서의 다차원 척도법 최적화

문제 제기
다차원 척도법 (MDS) 은 고차원 데이터를 저차원 기하 공간 (일반적으로 2 차원 또는 3 차원) 에 표현하여 임베딩 내의 쌍별 거리가 원래의 비유사성을 근사하도록 하는 차원 축소 표준 기법입니다. 그러나 고전적 MDS 는 노이즈, 이상치, 그리고 두꺼운 꼬리 분포에 매우 민감한 유클리드 거리에 의존합니다. 데이터가 오염되었거나 극단적 값에 의해 잠재적 구조가 가려진 실제 응용 분야에서는 유클리드 MDS 가 종종 진정한 기하학적 구조를 보존하지 못합니다. 또한, 표준 구현 (예: sklearn 내) 은 대규모 데이터셋에 대해 계산적으로 비효율적일 수 있으며, 기존 강건한 MDS 변형들은 특정 데이터 분포에 적응할 수 있는 조정 가능한 메커니즘이 부족한 경우가 많습니다.

방법론
본 논문은 유클리드 거리를 일반화된 지니 의사거리 (Generalized Gini Pseudo-Distance) 로 대체함으로써 고전적 MDS 를 확장한 지니 다차원 척도법 (Gini MDS) 프레임워크를 제안합니다.

1. 일반화된 지니 의사거리 ($D_{G,\nu}$):

   • 순위나 값에만 의존하는 표준 지니 거리와 달리, 이 의사거리는 둘 다를 통합합니다. 이는 민코프스키 $p$-노름 개념에 기반하지만 순위 정보를 포함하도록 적응되었습니다.
   • 핵심 혁신은 조정 가능한 하이퍼파라미터 $\nu$ ($\nu > 1$) 의 도입입니다. 이 매개변수는 분포의 꼬리 가중치를 조절합니다:
     • $\nu = 2$는 잔차의 지니 지수를 최소화하는 것 (중앙값 회귀와 유사) 에 해당합니다.
     • $\nu \in (1, 2)$는 분포의 상단 부분에 더 많은 가중치를 둡니다.
     • $\nu > 2$는 분포의 하단 부분에 더 많은 가중치를 둡니다.
   • 이 거리는 의사거리의 속성 (대칭성, 비부정성, 삼각부등식) 을 만족하도록 대칭화되었으나, "영 (null)" 속성은 동일 점뿐만 아니라 평등 분포 ($x = c\mathbf{1}$) 에 대해서도 성립한다는 점이 지적됩니다.
   • 이 구조는 순위 간격과 값 간격에 의존하므로 본질적으로 이상치에 강건합니다.

2. 최적화 알고리즘:

   • 이 프레임워크는 최적 잠재 공간을 찾기 위해 스트레스 최소화 접근법 (크루스칼의 스트레스) 을 사용합니다.
   • 알고리즘 1은 $\nu$ 값의 범위 (예: 1.1 에서 5) 를 반복합니다. 각 $\nu$에 대해 지니 의사거리 행렬을 계산하고, MDS 를 수행하여 임베딩을 생성한 후 스트레스 점수를 계산합니다.
   • 최적의 $\nu^*$는 교차 검증 폴드에서의 평균 스트레스를 최소화하는 것으로 선택됩니다.
   • 구현은 GPU 가속을 활용하기 위해 텐서 기반 연산을 사용하는 PyTorch를 활용하여 표준 CPU 기반 라이브러리 대비 상당한 속도 개선을 제공합니다.

주요 기여

1. 새로운 거리: 조정 가능한 하이퍼파라미터 $\nu$를 사용하여 값과 순위를 결합한 지니 의사거리 도입으로 잠재적 구성의 유연한 탐색을 가능하게 함.
2. 강건성: 극단적 값의 영향을 완화하는 순위 차이에 의존함으로써 지니 의사거리가 노이즈와 이상치에 강건함을 입증.
3. 최적화된 프레임워크: 관찰된 비유사성을 맞추기 위해 최적 하이퍼파라미터를 자동으로 선택하는 "최적화된 지니 MDS"를 위한 완전한 알고리즘으로, 정적 유클리드 접근법보다 우수한 성능 발휘.
4. 효율적인 구현: 표준 sklearn MDS 에 비해 계산 시간을 크게 단축하는 PyTorch 기반의 GPU 가속 텐서 구현.
5. 포괄적 평가: 이상치 유무가 포함된 16 개 UCI 데이터셋, 가우시안 노이즈가 추가된 MNIST 이미지 데이터, 그리고 두꺼운 꼬리 분포에 대한 시뮬레이션에 대한 광범위한 실험.

실험 결과

• UCI 데이터셋 (이상치 오염):
  • 2% 및 5% 오염이 포함된 16 개 데이터셋에서 지니 MDS 는 신뢰도 (Trustworthiness, 지역 구조 보존) 및 최근접 이웃 (Nearest Neighbor) 지표 측면에서 유클리드 MDS 와 세 가지 최적화된 유클리드 변형 (Huber, Sammon, SMACOF) 일관되게 우위를 점했습니다.
  • 유클리드 방법은 깨끗한 데이터에서 때때로 더 높은 실루엣 점수 (Silhouette scores, 글로벌 클러스터링) 를 달성하기도 했으나, 지니 MDS 는 데이터가 오염되었을 때 지역 이웃을 보존하는 데 있어 우수한 성능을 보였습니다.
• MNIST 분류 (노이즈):
  • 가우시안 노이즈가 추가된 상태에서 숫자 5 와 6 을 구분하는 분류 작업에서, 단일 임베딩 구성 요소를 사용할 때 지니 MDS 가 유클리드 MDS 보다 우위를 점했습니다.
  • 결과는 지니 MDS 가 노이즈 조건에서 첫 번째 구성 요소에 더 많은 관련 정보를 포착하는 더 높은 "압축 능력"을 가짐을 시사합니다.
• 두꺼운 꼬리 시뮬레이션:
  • 두꺼운 꼬리 분포에 대해 비선형 방법 (t-SNE, Isomap, UMAP) 과 비교했을 때, 지니 MDS 는 원본과 임베딩된 거리 행렬 간의 피어슨 및 스피어만 상관관계에서 가장 높은 수치를 달성했습니다.
  • 이는 지니 MDS 가 두꺼운 꼬리를 가진 데이터의 글로벌 기하학적 구조 (쌍별 거리 관계) 를 보존하는 데 특히 효과적이며, 다른 방법들은 지역 이웃 보존에 더 중점을 두었음을 나타냅니다.
• 성능:
  • PyTorch 구현은 sklearn 보다 훨씬 빨랐습니다 (예: 1,372 개의 인스턴스를 가진 은행권 데이터셋의 경우 46 초 대비 9 초).

의의 및 주장
본 논문은 지니 MDS 가 노이즈가 있거나 이상치를 포함하는 실제 응용 분야를 위해 고전적 MDS 에 대한 강건한 대안을 제공한다고 주장합니다. 지니 통계의 속성 (순위와 값의 통합) 을 활용하고 하이퍼파라미터 $\nu$를 최적화함으로써, 이 방법은 다음과 같은 이점을 제공합니다:

• 향상된 강건성: 유클리드 거리 대비 이상치 및 두꺼운 꼬리 분포 처리 능력 우수.
• 구조 보존: 임베딩 공간에서 지역 구조 (신뢰도를 통해) 와 글로벌 기하학적 관계 (거리 상관관계를 통해) 를 모두 유지할 수 있는 능력.
• 실용적 효율성: 대규모 데이터셋에 대한 강건한 차원 축소를 가능하게 하는 확장 가능하고 GPU 준비가 된 구현.

저자들은 깨끗한 데이터에서는 유클리드 MDS 가 여전히 효과적이지만, 데이터 오염이 포함된 시나리오에서는 지니 MDS 프레임워크가 우월한 선택이며, 잠재적 구조 발견을 위한 유연하고 계산적으로 효율적인 도구라고 결론지었습니다.