$p$-adic Principal Component Analysis

이 논문은 행렬 분해에 대한 $p$-adic 최적화 문제를 제시하고, 이를 해결하기 위한 주성분 분석 (PCA) 과 유사한 휴리스틱 방법을 연구합니다.

핵심

이 논문은 "p-진수 (p-adic numbers)"라는 낯선 수학적 세계를 이용해, 기존 데이터 분석 방법인 '주성분 분석 (PCA)'을 새로운 방식으로 재해석한 연구입니다.

일반적인 PCA 는 "복잡한 데이터를 가장 잘 설명하는 핵심적인 방향 (주성분) 을 찾아서 데이터를 줄이는" 기술입니다. 예를 들어, 수만 개의 변수로 된 데이터를 2~3 개의 핵심 변수로 요약해서 시각화하거나 이상치를 찾는 데 쓰이죠.

하지만 이 논문은 **"만약 우리가 실수 (Real numbers) 가 아니라 'p-진수'라는 완전히 다른 규칙이 적용되는 세계에서 데이터를 분석한다면 어떨까?"**라는 질문에서 시작합니다.

이 복잡한 내용을 일상적인 비유로 쉽게 풀어서 설명해 드리겠습니다.

---

1. 배경: 왜 'p-진수'라는 새로운 세계가 필요한가?

비유: "지도의 종류를 바꾸다"
우리가 보통 데이터를 분석할 때는 **실수 (Real numbers)**라는 '연속적인 지도'를 사용합니다. 여기서 두 점 사이의 거리는 우리가 아는 일반적인 거리 (유클리드 거리) 입니다. 하지만 이 논문은 **p-진수 (p-adic numbers)**라는 **'이산적이고 갈라진 (disconnected) 지도'**를 사용합니다.

• 실수 세계: 1 과 1.0001 은 아주 가깝습니다. (연속적)
• p-진수 세계: 1 과 1.0001 은 서로 아주 멀고, 1 과 1+p 는 오히려 아주 가깝습니다. (이산적, 소수 p 를 기준으로 '떨어짐'을 정의)

왜 이런 이상한 지도를 쓸까요?

• 이유: 우리가 다루는 데이터가 '0 과 1' 같은 이진수 (Boolean) 나 '나눗셈의 나머지' 같은 알고리즘적/대수적 구조를 가진 경우가 많습니다. 이런 데이터는 실수 지도에 억지로 끼워 맞추기보다, p-진수 지도에 담는 것이 데이터의 본질을 더 잘 보존합니다.

2. 문제: 기존 PCA 는 여기서 통하지 않는다

비유: "나침반이 고장 난 등산"
기존 PCA 는 데이터를 분석할 때 '공분산 행렬 (Covariance Matrix)'을 대각화하는 수학적 기법을 씁니다. 이는 마치 등산할 때 "가장 높은 봉우리 (주성분) 를 찾아라"라고 나침반을 믿고 가는 것과 같습니다.

하지만 p-진수 세계에서는 이 나침반이 고장 납니다.

• 문제점 1: p-진수에서는 대각화라는 작업이 항상 가능한 게 아닙니다.
• 문제점 2: p-진수에서는 '가장 가까운 점'을 찾는 방식이 실수와 다릅니다. (예: 0.999...와 1 의 관계가 다름)
• 문제점 3: '미분 (Gradient)'이라는 개념이 통하지 않아, "어느 방향으로 조금씩 움직여야 손실이 줄어드는가?"를 계산할 수 없습니다.

즉, **"기존의 등산 장비 (실수 기반 PCA) 를 들고 p-진수 산에 가면 길이 막혀서 갈 수 없다"**는 것입니다.

3. 해결책: "가장 가까운 이웃"을 찾는 새로운 등산법

저자는 이 문제를 해결하기 위해 **새로운 등산법 (p-진수 PCA)**을 고안했습니다.

핵심 아이디어: "수직이 아니라 '가장 가까운 점'으로 정의하자"

기존 PCA 는 "두 벡터가 수직 (Orthogonal) 하면 서로 독립적이다"라고 봅니다. 하지만 p-진수 세계에서는 수직이라는 개념이 애매합니다.

• 새로운 정의: "어떤 점 $A$에서 직선 $B$ 위에 있는 점들 중 가장 가까운 점을 찾아서, 그 차이 (오차) 를 '수직 성분'으로 간주하자."
• 비유: 산에서 어떤 지점 ($A$) 에서 산등성이 ($B$) 를 바라볼 때, "수직으로 떨어지는 것"이 아니라 **"등성이까지 걸어가는 가장 짧은 경로"**를 찾아 그 거리를 기준으로 삼는 것입니다.

알고리즘의 작동 원리 (간단히)

1. 트리 (Trie) 구조 활용: p-진수는 숫자를 소수 p 의 거듭제곱으로 쪼개어 표현합니다. 저자는 이를 마치 전화번호부나 트라이 (Trie) 트리처럼 구조화하여, "어떤 숫자를 곱하면 데이터가 가장 잘 설명되는가?"를 빠르게 계산합니다.
2. 반복적인 정제 (Orthogonalisation): 한 번에 완벽한 방향을 찾기 어렵기 때문에, "가장 가까운 이웃"을 찾아서 데이터를 정제하고, 그 과정을 반복합니다. 마치 안개 낀 산에서 한 걸음씩 나아가며 방향을 수정하는 것과 같습니다.

4. 두 가지 전략: "즉흥적" vs "준비된"

논문은 이 새로운 PCA 를 구현하는 두 가지 방법을 제시합니다.

1. 비축소형 (Non-reduced PCA):
   • 비유: "즉흥 탐험가"
   • 데이터를 하나씩 보며 "지금 보이는 데이터가 가장 핵심적인가?"라고 즉흥적으로 판단합니다. 계산이 빠르지만, 데이터 순서에 따라 결과가 달라질 수 있습니다.
2. 축소형 (Reduced PCA):
   • 비유: "철저한 사전 조사관"
   • 먼저 모든 데이터를 한 번 훑어보고, 서로 겹치지 않는 (직교하는) 핵심 방향들을 미리 정리해 둡니다. 그 다음에 분석을 시작합니다. 계산은 무겁지만, 훨씬 더 정확하고 안정적인 결과를 줍니다.

5. 실험 결과: "이상 탐지 (Anomaly Detection)"에서의 승리

이 새로운 방법이 실제로 쓸모있는지 확인하기 위해 '이상 탐지' 실험을 했습니다. (정상 데이터와 이상 데이터를 구분하는 것)

• 상황: 정상 데이터는 특정 규칙 (구름 같은 모양) 을 따르고, 이상 데이터는 그 규칙에서 벗어납니다.
• 결과:
  • 기존 방법 (Smith Normal Form 등): 이상 데이터가 '크다'는 사실만 보고 판단하려다 실패했습니다. (p-진수 세계에서는 '크다'는 개념이 애매하기 때문)
  • 새로운 방법 (RPCA, 즉 축소형): 압도적인 성공!
    • 정상 데이터는 잘 묶고, 이상 데이터는 명확하게 찾아냈습니다.
    • 특히, 기존 방법으로는 불가능했던 "정상 데이터보다 이상 데이터의 크기가 더 작은 경우"에서도 성공했습니다.

6. 결론: 왜 이 연구가 중요한가?

이 논문은 **"데이터 분석의 지평을 넓혔다"**고 할 수 있습니다.

• 기존의 한계 극복: 실수 (Real numbers) 에만 의존하던 데이터 분석이, 이산적이고 대수적인 구조를 가진 데이터 (예: 암호학, 네트워크 트래픽, 이진 데이터 등) 에도 적용 가능해졌습니다.
• 새로운 도구: "미분"이나 "대각화"가 불가능한 환경에서도, '가장 가까운 이웃'을 찾는 논리와 트리 알고리즘을 통해 최적의 해를 찾을 수 있음을 증명했습니다.

한 줄 요약:

"기존의 등산 장비 (실수 기반 PCA) 가 통하지 않는 낯선 산 (p-진수 세계) 에서, '가장 가까운 길'을 찾아내는 새로운 나침반을 개발하여, 복잡한 데이터 속의 숨은 패턴과 이상치를 찾아내는 데 성공했습니다."

이 연구는 수학적 이론의 깊이를 유지하면서도, 실제 데이터 과학 분야에서 새로운 가능성을 열어주는 중요한 시도로 평가받습니다.

기술 요약

p-진수 주성분 분석 (p-adic PCA) 기술 요약

이 문서는 토모키 미하라 (Tomoki Mihara) 가 저술한 "p-adic Principal Component Analysis" 논문의 핵심 내용을 바탕으로 작성된 기술 요약입니다. 이 연구는 실수 ($\mathbb{R}$) 기반의 주성분 분석 (PCA) 을 p-진수 ($\mathbb{Q}_p$) 및 p-진 정수 ($\mathbb{Z}_p$) 공간으로 확장하여, 이산적이고 대수적 구조를 가진 범주형 데이터의 차원 축소 및 이상치 탐지 문제를 해결하는 새로운 방법을 제시합니다.

---

1. 연구 배경 및 문제 정의 (Problem)

• 기존 PCA 의 한계: 기존 PCA 는 실수 공간 ($\mathbb{R}^D$) 에서의 선형 대수에 기반하여 연속 변수를 분석합니다. 이를 범주형 데이터 (Categorical Data) 에 적용할 때, 데이터를 유클리드 공간에 임베딩하면 원래 데이터가 가진 이산적 대수적 구조 (예: 부울 연산, 모듈로 연산) 가 손실되거나 왜곡될 수 있습니다.
• p-진수 최적화의 난제: p-진수 공간에서는 실수 최적화에서 사용되는 그라디언트 (Gradient) 기반의 방법이 적용되지 않습니다.
  • p-진수 절대값 함수는 $0$ 에서 불연속이며, 손실 함수 (Loss Function) 가 국소적으로 상수인 경우가 많아 미분 개념을 통한 최적화가 어렵습니다.
  • 대칭 행렬이 p-진수 환경에서 항상 대각화 (Diagonalization) 되지 않기 때문에, 공분산 행렬의 고유값 분해에 기반한 기존 PCA 기법이 작동하지 않습니다.
  • p-진수 내적 (Inner Product) 은 비퇴화성 (Non-degeneracy) 을 만족하지 않아 상관관계를 내적과 연결하는 것이 어렵습니다.
• 목표: p-진수 공간 ($\mathbb{Q}_p^D$ 또는 $\mathbb{Z}_p^D$) 에서 유효한 차원 축소 및 저차원 근사 (Low Rank Approximation) 기법을 개발하여, 특히 이상치 탐지 (Anomaly Detection) 와 같은 비지도 학습 작업에 적용 가능한 알고리즘을 제시하는 것입니다.

2. 방법론 (Methodology)

이 논문은 p-진수 환경에 적합한 새로운 수학적 정의와 알고리즘을 제안합니다.

2.1 p-진수 직교성 (p-adic Orthogonality)

• 정의: 실수의 직교성 (내적이 0) 대신, **가장 가까운 점 (Nearest Point)**의 관계를 기반으로 직교성을 정의합니다. 벡터 $\vec{v}_0$가 $\vec{v}_1$에 직교한다는 것은 $\vec{v}_0$가 $\vec{v}_1$로 생성된 1 차원 부분공간에서 $\vec{v}_0$와 가장 가까운 점 (0) 일 때를 의미합니다.
• 특징: 이 직교성은 실수 공간과 달리 대칭적이지 않으며, 벡터들의 집합이 선형 부분공간을 형성하지 않을 수 있습니다.

2.2 1 차원 투영 및 직교화 알고리즘

• 1 차원 투영: 주어진 벡터 $\vec{v}_0$를 다른 벡터 $\vec{v}_1$ 방향으로 투영하여 오차를 최소화하는 계수 $c$를 찾는 문제 ($\min \| \vec{v}_0 - c\vec{v}_1 \|$) 를 해결합니다.
• 트리 트리 (Trie Tree) 알고리즘: p-진수의 특성 (유한한 $\pi$-진 전개) 을 활용하여, 계수 $c$를 찾는 최적화 문제를 효율적으로 해결하기 위해 Trie Tree 구조를 사용합니다. 이는 깊이 우선 탐색 (DFS) 을 통해 근사 최적해를 빠르게 찾습니다.
• 반복 직교화 (Iterated Orthogonalisation): p-진수 직교성의 비대칭성으로 인해, 한 번의 직교화 과정만으로는 모든 벡터가 직교하는 시스템을 보장할 수 없습니다. 따라서 반복적인 직교화 과정을 통해 시스템이 안정화될 때까지 벡터들을 정제합니다.

2.3 p-진수 PCA 알고리즘

논문은 두 가지 주요 PCA 변형을 제안합니다:

1. 비축소 p-진수 PCA (Non-reduced PCA, NRPCA):
   • 데이터 중 첫 번째로 등장하는 0 이 아닌 벡터를 주성분 후보로 선택합니다.
   • 재귀적으로 데이터를 투영하고 오차를 업데이트합니다.
   • 계산이 가볍지만, 생성된 좌표계가 직교하지 않을 수 있어 최적성이 보장되지 않습니다.
2. 축소 p-진수 PCA (Reduced PCA, RPCA):
   • 먼저 전체 데이터에 대해 **반복 직교화 (Iterated Orthogonalisation)**를 수행하여 대략적으로 직교하는 좌표계 (Z) 를 사전에 생성합니다.
   • 생성된 Z 에서 노름 (Norm) 이 큰 순서대로 주성분을 선택하여 PCA 를 수행합니다.
   • 사전 계산 비용은 높지만, 생성된 좌표계가 직교성에 가까워 더 정확한 저차원 근사를 제공합니다.

2.4 손실 함수 및 노름

• $\ell_\infty$-노름 대신 $\ell_q$-노름 ($q \in [1, \infty)$) 을 사용합니다.
• $\ell_\infty$-노름은 p-진수 환경에서 값이 희소하게 분포하여 이상치 탐지에 부적합할 수 있으나, $\ell_q$-노름은 이상치와 정상 데이터 간의 노름 차이를 더 잘 포착하여 이상치 탐지 성능을 향상시킵니다.

3. 주요 기여 (Key Contributions)

1. p-진수 최적화 프레임워크 구축: 그라디언트가 없는 p-진수 공간에서 행렬 분해를 통한 차원 축소 문제를 공식화하고, 이를 해결하기 위한 휴리스틱 알고리즘을 제시했습니다.
2. 새로운 직교성 개념 도입: 내적 기반이 아닌 '최근접 점' 기반의 p-진수 직교성 정의를 통해, 대각화가 불가능한 p-진수 행렬에 대한 PCA 를 가능하게 했습니다.
3. 효율적인 알고리즘 설계: Trie Tree 와 DFS 를 활용한 계수 탐색 알고리즘을 개발하여 p-진수 최적화 문제를 정수 연산으로 효율적으로 처리할 수 있게 했습니다.
4. 이상치 탐지 성능 입증: Smith 정규형 (Smith Normal Form) 기반의 기존 방법론이 실패하는 시나리오 (이상치의 $\ell_\infty$-노름이 정상 데이터보다 작을 수 있는 경우) 에서도 RPCA 가 우수한 성능을 보임을 실험을 통해 증명했습니다.

4. 실험 결과 (Results)

실험은 $p=7$, 차원 $D=100$, 데이터 수 10,000 개를 기준으로 수행되었으며, 두 가지 시나리오 (Open Balls, Affine Subspace) 에서 NRPCA 와 RPCA 를 비교했습니다.

• Open Balls 실험:
  • 정상 데이터가 서로 겹치지 않는 여러 공 (Ball) 에 분포하고, 이상치가 섞여 있는 상황입니다.
  • RPCA는 NRPCA에 비해 **True Positive Ratio (이상치 탐지율)**가 현저히 높았습니다 (예: $B=10, r=10$일 때 RPCA 는 0.99, NRPCA 는 0.35).
  • RPCA 는 사전 직교화를 통해 손실을 크게 줄여, 이상치를 정상 데이터와 명확히 구분했습니다.
  • NRPCA 는 False Positive Ratio (정상 데이터를 이상치로 오인) 가 낮아, 위양성 (False Positive) 을 최소화해야 하는 경우에 유용할 수 있음을 보였습니다.
• Affine Subspace 실험:
  • 정상 데이터가 특정 아핀 부분공간에 존재하고 노이즈가 섞인 상황입니다.
  • RPCA 는 차원 축소 목표치 ($D_-$) 가 실제 데이터의 차원 ($D'$) 보다 큰 경우뿐만 아니라, $D' > D_-$인 경우에도 매우 높은 이상치 탐지율 (0.96~0.99) 을 보였습니다.
  • 이는 Smith 정규형이나 유한체 ($\mathbb{F}_p$) 위의 가우스 소거법과 같은 기존 선형 대수적 방법론으로는 달성하기 어려운 성능입니다.

5. 의의 및 결론 (Significance)

• 대수적 구조 보존: p-진수 PCA 는 데이터의 이산적이고 대수적인 구조 (예: 부울 값, 모듈로 연산) 를 보존하면서 차원 축소를 수행할 수 있어, 기존 실수 기반 PCA 의 한계를 극복합니다.
• 새로운 최적화 패러다임: 미분 불가능한 p-진수 공간에서 Trie Tree 기반의 탐색 알고리즘을 통해 최적화 문제를 해결하는 새로운 접근법을 제시했습니다.
• 실용적 응용: 특히 이상치 탐지 (Anomaly Detection) 분야에서, 노름의 크기가 아닌 데이터의 구조적 특성을 기반으로 이상을 탐지할 수 있어, 금융 사기 탐지, 사이버 보안 등 다양한 분야에서 응용 가능성이 높습니다.
• 이론적 확장: p-진수 힐베르트 공간의 제한적인 조건 (정규성 등) 을 우회하여, 일반적인 p-진수 벡터 공간에서도 유효한 통계적 분석 도구를 제공했습니다.

결론적으로, 이 논문은 p-진수 이론을 머신러닝 및 데이터 과학 분야에 성공적으로 접목한 선구적인 연구로, 이산적 대수 구조를 가진 데이터 분석을 위한 강력한 새로운 도구를 제공합니다.