Manifold Dimension Estimation via Local Graph Structure

데이터의 거대하고 지저분한 더미를 상상해 보세요. 머신러닝 세계에서는 이 데이터가 종종 거대하고 고차원적인 방 (아마도 100 차원 이상) 안에 존재하는 것처럼 보입니다. 하지만 이 논문의 저자들은 데이터가 실제로 그 방 전체를 채우고 있지 않다고 의심합니다. 대신 그들은 데이터가 그 방 안에 떠 있는 얇고 구겨진 종이 위에 숨어 있다고 생각합니다.

이 "종이"를 **다양체 (manifold)**라고 부릅니다. 그 종이 위에서 떨어지지 않고 이동할 수 있는 방향의 수가 바로 **내재 차원 (intrinsic dimension)**입니다. 만약 그 종이가 평평한 종이 조각이라면 차원은 2 입니다. 만약 종이가 구겨진 공 모양이라면, 3 차원 방에 떠 있더라도 차원은 여전히 2 입니다.

큰 문제는 무엇일까요? 우리는 그 종이가 실제로 몇 차원인지 모릅니다. 대부분의 기존 도구들은 종이가 작은 지역 (neighborhood) 에서 완벽하게 평평하다고 가정하고 추측하려 합니다. 하지만 종이가 구겨져 있다면 (곡면이라면), 이러한 도구들은 혼란을 겪고 잘못된 답을 내놓습니다.

새로운 아이디어: "지역 그래프" 탐정

저자들은 이 퍼즐을 해결하는 새로운 방법을 제안합니다. 단순히 데이터를 보고 "평평해 보인다"라고 말하는 대신, 지역적 이웃을 살펴봄으로써 숨겨진 물체의 모양을 파악하려는 탐정처럼 문제를 접근합니다.

다음은 그들의 창의적인 접근법입니다:

1. 이웃 (Neighborhood): 데이터 종이의 한 점을 선택합니다. 그 점의 즉각적인 이웃 (가장 가까운 점들) 을 살펴봅니다.
2. 지도 (PCA): PCA 라는 표준 도구를 사용하여 지역적 지도를 그립니다. 이 지도는 그 한 점에서 종이에 닿는 "접평면 (tangent plane)"—평평한 표면—을 생성합니다. 이는 구불구불한 언덕 위에 평평한 판자를 올려놓는 것과 같습니다. 한 지점에서 닿지만 곡선을 완벽하게 따라가지는 않습니다.
3. 빠진 조각 (그래프): 저자들은 평평한 판자와 실제 구불구불한 언덕 사이의 차이가 핵심임을 깨달았습니다. 그들은 이 차이를 "지역 그래프 (local graph)"라고 부릅니다. 이는 평평한 판자에서 실제 곡선까지 올라가기 위해 필요한 추가 높이를 쌓는 것과 같습니다.
4. 회귀 테스트 (Regression Test): 그들은 수학적 모델을 사용하여 이 "추가 높이"를 예측해 봅니다.
   • 그들은 묻습니다: "평평한 판자 위의 점의 위치를 안다면, 그 점이 판자에서 얼마나 떨어져 있는지 (높이) 예측할 수 있을까?"
   • 그들은 서로 다른 차원 수로 이를 시도해 봅니다.
   • "아하!" 순간: 만약 그들이 차원을 너무 낮게 추측하면 예측이 실패합니다 (모델이 모양을 설명하지 못함). 차원을 너무 높게 추측하면 모델은 단순히 노이즈를 추측하는 것입니다. 하지만 그들이 올바른 차원을 추측할 때, 모델은 갑자기 곡선을 예측하는 데 매우 능숙해집니다. 마치 마침내 자물쇠에 맞는 올바른 열쇠를 찾은 것과 같습니다.

두 가지 새로운 도구

이 논문은 이 작업을 수행하기 위한 두 가지 구체적인 도구 (추정기) 를 소개합니다:

• QE (Quadratic Embedding, 2 차 임베딩): 이 도구는 표준 수학적 기법 (일반 최소제곱법) 을 사용하여 데이터에 곡선 (2 차 모델) 을 적합시킵니다. 이는 데이터 점들에 매끄러운 곡선 경사로를 맞추려는 것과 같습니다. 올바른 수의 차원을 추가했을 때 "적합도 (fit)"가 유의미하게 개선되는지 확인함으로써 작동합니다.
• TLS (Total Least Squares, 총체적 최소제곱법): 이는 더 신중한 버전입니다. 표준 수학적 도구들은 보통 "입력" (평평한 지도) 이 완벽하고 "출력" (높이) 에만 오차가 있다고 가정합니다. 하지만 현실에서는 지도 자체가 약간 흐릿하거나 노이즈가 있을 수 있습니다. TLS 는 두 방향 모두의 오차를 고려합니다. 이는 자자가 약간 휘어졌을 수도 있고 측정값이 흔들릴 수도 있음을 인정하고 둘 모두를 보정하는 것과 같습니다.

왜 이것이 중요한가 (논문에 따르면)

저자들은 이 도구들을 두 가지 유형의 데이터로 테스트했습니다:

1. 합성 데이터: 구, 꼬인 리본, 변형된 공과 같이 알려진 모양 위에 가짜 데이터를 생성하여 도구들이 진정한 차원을 찾을 수 있는지 확인했습니다.
2. 실제 데이터: 손으로 쓴 숫자 (MNIST), 얼굴, 센서 읽기 값과 같은 실제 데이터셋으로 테스트했습니다.

결과:

• 구식 도구 능가: 구식 도구들은 데이터가 매우 구불구불하거나 "방"이 "종이"보다 훨씬 클 때 종종 실패합니다. 새로운 도구들 (QE 와 TLS) 은 이러한 까다롭고 구겨진 모양을 훨씬 더 잘 처리했습니다.
• 노이즈 처리: 실제 데이터는 지저분합니다. 새로운 도구들은 많은 기존 방법들보다 노이즈 (무작위 오차) 에 대해 더 강건했습니다.
• "과대평가" 수정: 구식 도구들의 일반적인 문제는 방이 크기 때문에 차원이 거대하다고 추측한다는 점입니다 (예: 평평한 종이가 100 차원이라고 추측). 새로운 도구들은 빈 공간을 무시하고 종이의 진정한 더 작은 차원을 찾는 데 훨씬 더 뛰어납니다.

함정 (한계점)

이 논문은 이러한 도구들이 어디서 어려움을 겪는지 솔직하게 밝힙니다:

• 너무 단순한 모양: 데이터가 완벽하게 평평한 표면이나 복잡한 곡선이 없는 단순한 공 위에 있다면, 도구들은 종종 혼란을 겪습니다. 이는 도구들이 특별히 곡선을 찾기 위해 설계되었기 때문입니다.
• 데이터 갈망: 그들은 복잡한 곡선 (2 차 수학을 사용) 을 찾기 때문에, 각 이웃에서 제대로 작동하려면 상당량의 데이터가 필요합니다. 이웃이 너무 작으면 수학이 불안정해집니다.
• 속도: 계산이 가장 간단한 방법들보다 다소 무겁지만, 저자들은 이를 관리 가능한 수준으로 최적화했습니다.

요약하자면

이 논문은 이렇게 말합니다: "세상이 평평하다고 가정하는 것을 멈추세요. 대신 데이터의 미세한 곡선들을 살펴보세요. 이러한 곡선들을 수학적으로 예측해 보함으로써, 데이터가 거대하고 노이즈가 많은 방에 숨어 있더라도 데이터가 실제로 몇 차원에 존재하는지 정확히 파악할 수 있습니다."

이 논문에서 그들은 이것이 직접적으로 질병을 치료하거나 자율주행차를 만들 것이라고 주장하지 않았습니다. 그들은 단순히 그들의 새로운 "곡선 탐지" 수학이 우리가 지금까지 사용해 온 것보다 데이터 모양의 복잡성을 측정하는 더 정확한 방법임을 증명했을 뿐입니다.