The Theory behind UMAP?

이 논문은 2018 년 McInnes 등이 제안한 차원 축소 알고리즘 UMAP 의 이론적 기반이 된 Spivak 의 미분 실현 (metric realization) 관련 원고에 존재하는 오류들을 수정하고, 해당 함자 (functors) 와 UMAP 알고리즘의 유한 변형에 대한 완전한 유도 과정을 제시합니다.

핵심

이 논문은 데이터 과학 분야에서 매우 인기 있는 **'UMAP'**이라는 도구의 이론적 배경을 재검토하고, 원래의 설명에 있던 수학적 오류들을 수정하고 정리한 학술지입니다.

저자 데이비드 웨그만은 UMAP을 만든 McInnes 팀과 Spivak 교수의 원래 논문들이 가진 모호함과 계산 실수를 찾아내어, **"UMAP이 정말로 어떻게 작동하는지 수학적으로 완벽하게 증명하자"**고 주장합니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

🧱 1. UMAP 이 뭐예요? (데이터의 지도 만들기)

상상해 보세요. 거대한 우주에 별들이 무수히 흩어져 있습니다. 이 별들 (데이터) 은 100 차원이라는 아주 복잡한 공간에 있는데, 우리는 2 차원 (평면) 이나 3 차원 (입체) 지도로 그려서 보고 싶습니다.

• 목표: 복잡한 우주 (고차원 데이터) 를 평면 지도 (저차원) 로 옮기되, 가까운 별들은 여전히 가깝게, 먼 별들은 여전히 멀게 배치해야 합니다.
• UMAP 의 역할: 이 복잡한 우주 구조를 잘게 쪼개서 (국소적 그래프), 다시 하나의 거대한 지도로 이어 붙이는 마법 같은 도구입니다.

🧩 2. 원래 이론의 문제점: "누가 레시피를 잘못 적었나?"

UMAP 을 처음 소개한 논문 (McInnes 등) 은 이 도구가 수학적으로 매우 정교한 **'위상수학 (Topology)'**과 '퍼지 집합 (Fuzzy Sets)' 이론에 기반한다고 설명했습니다. 마치 "이 레시피는 고대 신비로운 요리법 [Spivak 의 논문] 을 따릅니다"라고 한 셈이죠.

하지만 저자는 이 레시피를 자세히 보니 치명적인 실수가 많았다고 말합니다.

• 실수 1: "0"이라는 숫자를 로그 (log) 함수에 넣으려다 계산이 터져버렸습니다. (로그 0 은 정의되지 않죠.)
• 실수 2: "거리"를 재는 자 (메트릭) 를 잘못 썼습니다. 마치 "직선 거리"를 재야 할 때 "구불구불한 산길"을 재는 것과 같습니다.
• 실수 3: 수학적 정의가 모호해서, "유한한 (Finite)"이라는 말이 정확히 무엇을 의미하는지 알 수 없었습니다.

저자는 **"이 레시피를 다시 써서, 오류 없이 완벽하게 만들자"**고 합니다.

🛠️ 3. 저자가 고친 점: "정교한 공구로 다시 다듬기"

저자는 UMAP 의 핵심인 **'메트릭 실라이제이션 (Metric Realization)'**이라는 개념을 다시 정의했습니다.

비유: "레고 블록과 접착제"

UMAP 은 데이터를 레고 블록으로 생각하고, 그 블록들을 접착제로 붙여 하나의 구조물을 만듭니다.

1. 블록의 크기 (Membership Strength):

   • 원래 이론: 블록의 크기를 결정하는 숫자가 0 이나 1 이 되면 계산이 꼬였습니다.
   • 수정 후: 저자는 블록의 크기를 **'노름 (Norm)'**이라는 개념으로 명확히 했습니다. 마치 "이 블록은 5cm 크기로 고정하자"라고 정한 것처럼, 계산이 항상 깔끔하게 되도록 만들었습니다.
   • 결과: 이제 0 이나 1 같은 극단적인 숫자에서도 시스템이 붕괴되지 않습니다.

2. 접착제 (거리 측정):

   • 원래 이론: 블록들을 붙일 때 '유클리드 거리 (직선 거리)'를 썼는데, 이는 UMAP 의 목적에 맞지 않았습니다.
   • 수정 후: **'맨해튼 거리 (L1 거리)'**를 사용하도록 고쳤습니다.
   • 비유: 유클리드 거리는 "대각선으로 날아다니는 새"처럼 움직이는 거라면, 맨해튼 거리는 "건물 사이를 빙빙 돌아가는 택시"처럼 움직이는 거리입니다. UMAP 은 이 '택시 거리'를 사용해야만 블록들이 올바르게 붙는다는 것을 증명했습니다.

3. 유한한 세계 (Finite Variant):

   • 컴퓨터는 무한한 세계를 다룰 수 없습니다. McInnes 팀은 "유한한 버전"을 만들었다고 했지만, 그게 정확히 무엇인지 정의가 모호했습니다.
   • 수정 후: 저자는 "유한하다"는 것을 **"데이터 포인트의 개수가 한정되어 있고, 그 크기가 일정 범위 안에 있다"**는 식으로 엄격하게 정의했습니다. 이제 이 이론이 실제 컴퓨터 프로그램으로 구현될 때 어떤 한계를 가지는지 명확해졌습니다.

🗺️ 4. UMAP 알고리즘이 실제로 하는 일 (간단한 요약)

수학적 정리를 거쳐 UMAP 이 실제로 데이터를 어떻게 처리하는지 다시 보면 다음과 같습니다.

1. 국소 지도 그리기: 각 데이터 포인트 주변에 작은 친구들 (이웃) 을 찾아 연결합니다. 이때 "친밀도"를 계산합니다. (예: 아주 가까우면 1, 멀면 0 에 가깝게)
2. 지도 합치기: 모든 작은 지도를 하나의 거대한 지도로 합칩니다. 이때 '확률적 합집합'이라는 특별한 접착제를 사용합니다. (두 사람이 서로를 친구로 생각하면, 그 관계는 더 강해집니다.)
3. 최적화: 이 거대한 지도를 2 차원 평면 위에 펼쳐놓습니다. 처음엔 무작위로 던져놓고, **경사 하강법 (Gradient Descent)**이라는 방법으로 "가까운 친구들은 더 가까이, 먼 친구들은 더 멀리" 배치되도록 수백 번을 반복해서 조정합니다.

💡 5. 결론: 왜 이 논문이 중요한가?

이 논문은 **"UMAP 은 정말로 위상수학의 신비로운 힘으로 작동한다"**는 원래의 주장을 **"아니, 사실은 이렇게 단순하고 명확한 수학 (노름 공간과 거리 함수) 으로 작동한다"**고 바로잡았습니다.

• 오류 수정: 원래 논문들의 계산 실수와 모호함을 제거했습니다.
• 명확성: "왜 UMAP 이 작동하는지"에 대한 수학적 근거를 더 단단하게 만들었습니다.
• 신뢰도: 이제 데이터 과학자들이 UMAP 을 사용할 때, 그 뒤에 숨겨진 수학이 얼마나 튼튼한지 알 수 있게 되었습니다.

한 줄 요약:

"UMAP 이라는 멋진 도구의 설계도가 원래는 구멍이 많고 계산이 틀려 있었는데, 이 논문이 그 구멍을 메우고 자를 다시 맞춰서 완벽한 설계도를 다시 그려냈습니다."

기술 요약

이 논문은 2018 년 McInnes 등이 제안한 차원 축소 알고리즘 UMAP의 이론적 배경이 되는 메트릭 실현 (Metric Realization) 이론에 존재하는 오류를 수정하고, Spivak 의 미공개 초안과 McInnes 등의 논문을 엄밀하게 재구성한 수학적 정립 작업입니다. 저자 David Wegmann 은 범주론 (Category Theory) 과 위상수학적 기법을 활용하여 UMAP 의 수학적 기초를 명확히 하고, 기존 문헌의 모호한 정의와 논리적 결함을 해결했습니다.

다음은 논문의 주요 내용을 요약한 것입니다.

1. 문제 제기 (Problem)

• UMAP 의 이론적 기반 부재: UMAP 알고리즘은 널리 사용되지만, 이를 뒷받침하는 수학적 이론 (Spivak 의 '메트릭 실현' 및 McInnes 등의 '유한 변형') 은 미공개 초안이나 불완전한 논문 [5, 9] 에 의존하고 있습니다.
• 문헌의 오류와 모호함: Spivak 의 초안 [9] 과 McInnes 등의 논문 [5] 은 여러 중요한 오류를 포함하고 있습니다.
  • 집합론적 오류: 퍼지 집합 (Fuzzy Sets) 의 정의, 위상 공간 $I=(0,1]$ 에 대한 정의 (공집합 누락), 로그 함수의 정의역 문제 ($\log(0)$) 등이 잘못 기술되었습니다.
  • 계산적 오류: 메트릭 심플렉스 (Metric Simplex) 의 크기 조정 인자 계산 시 $0$으로 나누는 오류가 발생하거나, 비확장성 (non-expansive) 조건이 만족되지 않는 경우가 존재합니다.
  • 범주론적 결함: Yoneda 임베딩을 통한 Kan 확장 (Kan Extension) 구성 시, 대상이 실제로 '층 (Sheaf)' 조건을 만족하는지 증명되지 않았습니다.
• 목표: 이러한 오류를 수정하고, Spivak 의 이론과 McInnes 의 유한 변형을 엄밀하게 유도하여 UMAP 알고리즘과 이론적 모델 간의 대응 관계를 명확히 하는 것입니다.

2. 방법론 (Methodology)

저자는 범주론, 특히 Kan 확장, 층 이론 (Sheaf Theory), 로컬 (Locale) 개념을 기반으로 다음과 같은 체계적인 재구성을 수행했습니다.

• 범주론적 배경 정립:
  • Currying (카리화): 함자 (Functor) 의 동치 관계를 명확히 하여, 퍼지 집합을 층 (Sheaf) 으로 해석하는 과정을 엄밀하게 정의했습니다.
  • 층 이론 적용: Barr 의 '가치 집합 (Valued Sets)' 이론을 기반으로 퍼지 집합을 층으로 재정의하고, 이를 통해 Spivak 의 모호한 정의를 엄밀한 수학적 구조로 대체했습니다.
• 메트릭 실현 (Metric Realization) 의 엄밀한 구성:
  • 확장 의사 거리 공간 (EPMet): 메트릭 공간의 범주가 완비적 (cocomplete)이지 않다는 문제를 해결하기 위해, 거리가 $0$이나$\infty$가 될 수 있는 '확장 의사 거리 공간' 범주를 사용했습니다.
  • 유사 거리 심플렉스: 기존 Spivak 의 정의 (로그 스케일링) 대신, **$\ell_1$ 거리 (Manhattan 거리)**를 사용하여 심플렉스의 크기를 조정하는 방식으로 재정의했습니다. 이는 degeneracy map(퇴화 사상) 이 비확장성 (non-expansive) 을 만족하도록 보장합니다.
  • Left Kan Extension: 메트릭 실현을 Yoneda 임베딩을 따른 Left Kan 확장으로 정의하여 그 존재성을 증명했습니다.
• 유한 변형 (Finite Variant) 의 정립:
  • McInnes 등이 제안한 '유한 메트릭 실현'에 대해, '유한성'과 '유계성 (boundedness)'에 대한 모호한 정의를 엄밀하게 해석했습니다.
  • 유한 확장 의사 거리 공간 범주 ($Fin\text{-}EPMet$) 와 유한 퍼지 심플리셜 집합 범주 ($Fin\text{-}USFuz$) 를 정의하고, 이 범주들 사이에서도 Kan 확장이 존재함을 증명했습니다.

3. 주요 기여 (Key Contributions)

1. 오류 수정 및 엄밀한 증명: Spivak 의 초안과 McInnes 논문의 모든 주요 오류 (로그 정의역, 비확장성 위반, 층 조건 부재 등) 를 식별하고 수정했습니다.
2. 명시적인 메트릭 실현 구성:
   • 고전적 관점 (Classical Perspective): 층 이론적 정의를 **고전적 노름 집합 (Classical Normed Sets)**으로 변환하여, UMAP 이 실제로 어떤 기하학적 구조를 생성하는지 직관적으로 이해할 수 있는 명시적인 공식을 유도했습니다.
   • 등가성 증명: 퍼지 집합 (Fuzzy Sets) 과 노름 집합 (Normed Sets) 사이의 범주 동치 (Equivalence of Categories) 를 두 방향으로의 함자와 자연 동형사상을 통해 완전히 증명했습니다.
3. UMAP 알고리즘과의 대응 관계 규명:
   • McInnes 등의 '유한 메트릭 실현'이 UMAP 알고리즘의 1 단계 (로컬 그래프 구성) 와 2 단계 (그래프 합집합) 에 수학적으로 정확히 대응됨을 보였습니다.
   • 특히, UMAP 에서 사용하는 가중치 (가중치 $w = e^{-d}$) 가 '유한 특이 신경 (Finite Singular Nerve)'을 통해 생성된 퍼지 집합의 소속도 (membership strength) 와 일치함을 증명했습니다.
4. 알고리즘의 이론적 한계 지적: UMAP 알고리즘이 데이터의 위상적 구조를 보존한다는 주장에 대해, 확률론적 해석 (가중치를 확률로 보는 것) 이나 위상적 보존에 대한 엄밀한 정리가 아직 부족함을 지적하고 향후 연구 과제를 제시했습니다.

4. 결과 (Results)

• 수학적 엄밀성 확보: UMAP 알고리즘의 이론적 배경이 되는 메트릭 실현이 잘 정의된 수학적 객체임을 증명했습니다.
• 알고리즘 - 이론 매핑: UMAP 알고리즘의 각 단계 (로컬 그래프 생성, 확률적 합집합, 스펙트럴 임베딩, 경사 하강법) 가 수학적 모델 (유한 메트릭 실현 및 그 쌍대인 유한 특이 신경) 과 어떻게 연결되는지를 명확히 했습니다.
  • 로컬 그래프 $G_i$는 유한 특이 신경 $Fin\text{-}Sing(X, d_i)$의 1-스켈레톤과 대응됩니다.
  • 그래프의 합집합 연산은 퍼지 집합의 합집합 (T-conorm 사용) 과 대응됩니다.
• 계산적 효율성: $\ell_1$ 거리를 사용한 새로운 정의가 기존 Spivak 의 정의보다 계산적으로 더 안정적이며, $0$으로 나누는 오류를 방지함을 보였습니다.

5. 의의 (Significance)

• 이론적 토대 강화: 데이터 과학 분야에서 널리 쓰이는 UMAP 알고리즘에 대해, 불완전했던 수학적 이론을 완전히 정립함으로써 알고리즘의 신뢰성을 높였습니다.
• 향후 연구의 길잡이: UMAP 의 성능이 왜 좋은지, 혹은 어떤 조건에서 위상적 구조가 보존되는지에 대한 엄밀한 정리가 필요함을 지적하며, 향후 연구 방향을 제시했습니다.
• 범주론적 접근의 실용성: 추상적인 범주론 (Kan 확장, 층 이론) 이 실제 머신러닝 알고리즘의 설계와 분석에 어떻게 적용될 수 있는지 보여주는 훌륭한 사례를 제공했습니다.

결론적으로, 이 논문은 UMAP 알고리즘이 단순한 휴리스틱이 아니라, 확장 의사 거리 공간에서의 메트릭 실현이라는 엄밀한 수학적 구조 위에 구축되어 있음을 증명하고, 기존 문헌의 오류를 수정하여 해당 분야의 이론적 완성도를 높인 중요한 작업입니다.