기술 요약: 비아르키메데스 폴디스크 공간과 최적화에 대한 응용

1. 문제 정의

계층적 데이터 분석은 계통 발생학 및 유전체학에서 언어학, 사회학에 이르기까지 다양한 분야에서 보편적으로 나타납니다. 계층 구조는 자연스럽게 비아르키메데스 기하학적 구조(종종 메트릭 트리로 시각화됨)를 유도하지만, 이러한 구조를 실수($\mathbb{R}$) 상에서 충실하게 포착하는 것은 어렵습니다. 이러한 데이터를 $\mathbb{R}^n$에 임베딩하는 것은 종종 고차원 공간이나 쌍곡 기하학을 요구하며, 이는 고유한 울트라메트릭(ultrametric) 속성을 보존하지 못할 수 있습니다.

반대로, 비아르메데스 체(예: $p$-진수 $\mathbb{Q}_p$) 위에서 직접 작업하는 것은 계층 구조를 보존하지만 최적화 측면에서 상당한 어려움을 초래합니다. 이들 체의 위상은 완전 불연결(totally disconnected)되어 있어, 경사 하강법(gradient descent)과 같은 표준 연속 최적화 기법의 사용을 금지합니다. 결과적으로, 비아르키메데스 공간에서의 최적화 문제는 빈번하게 계산 비용이 많이 드는 조합 탐색으로 귀결됩니다.

본 논문이 다루는 핵심 문제는 다음과 같은 특성을 동시에 갖춘 기하학적 프레임워크의 부재입니다:

1. 비아르키메데스 기하학을 통해 계층적 데이터를 충실하게 표현함.
2. 표준 최적화 기법(예: 측지선, 볼록성, 기울기)에 적합한 연속적이고 경로 연결된(path-connected) 도메인을 제공함.

2. 방법론 및 프레임워크

저자들은 베르코비치 기하학(Berkovich geometry)에서 영감을 얻어, 최적화의 도메인으로서 폴디스크 공간(polydisc spaces, $B^n$ 및 $H^n$)을 도입하는 새로운 프레임워크를 제안합니다.

2.1 폴디스크 공간

저자들은 비아르키메데스 체 $K^n$에서 직접 작업하는 대신, 폴디스크 공간을 비아르키메데스 체(예: $\mathbb{Q}_p$ 또는 로랑 급수체의 필드) 위의 닫힌 볼(closed balls)의 곱으로 정의합니다.

• 구조: $B^n$은 절대 반지름(absolute radius)을 갖는 폴디스크 $B_B(a, r)$ 또는 가치 반지름(valuative radius)을 갖는 폴디스크 $B_H(a, v)$로 구성됩니다.
• 기하학: 이 공간은 $K^n$에 결여된 다음과 같은 바람직한 기하학적 특징들을 유지하면서도 $K^n$의 엄격한 계층적 구조(중첩되지 않는 중첩된 집합)를 보유합니다:
  • 경로 연결성: 공간은 측지선(geodesics)을 통해 연결됩니다.
  • 측지선: 공간은 유일하게 측지선적(uniquely geodesic)입니다(단, $n=1$ 또는 $1 < p < \infty$인 경우). 이를 통해 임의의 두 점 사이의 경로를 정의할 수 있습니다.
  • 볼록성: 측지선에 기반하여 볼록 껍질(convex hull)의 개념이 정의됩니다.
  • 접 방향(Tangent Directions): 한 점으로부터 뻗어 나오는 측지선들의 동치류로 정의되는 접 방향을 통해 미분 가능한 계산 구조가 도입됩니다. 이를 통해 방향 도함수(directional derivatives)를 정의할 수 있습니다.

2.2 함수 이론

저자들은 절대 다항식(absolute polynomials) 및 **가치 다항식(valuation polynomials)**이라 불리는 실수 값 함수 클래스를 도입합니다.

• 정의: 폴디스크 상의 계수를 가진 다항식 $f$가 주어졌을 때, 이 함수는 폴디스크 $B$ 내의 $z \in B$에 대해 $|f(z)|$(또는 $val(f(z))$)의 상한(supremum)을 매핑합니다.
• 특성: 이 함수들은 명시적인 평가 공식을 가집니다. 결정적으로, 이들은 측지선을 따라 조각별 다항식(절대값의 경우) 또는 조각별 선형/트로피컬(가치값의 경우) 형태를 띱니다.
• 보편 근사(Universal Approximation): 저자들은 절대 다항식의 선형 결합이 $B^n$의 컴팩트 부분 집합 상의 임의의 연속 함수를 근사할 수 있음을 보여주는 보편 근사 정리(정리 45)를 증명합니다.

2.3 메트릭 트리 임베딩

본 논문은 메트릭 트리가 쌍곡 폴디스크 공간 $H^1$에 자연스럽고 흔히 등거리적으로(isometrically) 임베딩될 수 있음을 확립합니다.

• 기준: 트리 정점의 최대 차수가 $|K| + 1$에 의해 제한되고 에지 길이가 $K$의 가치 군(valuation group)의 값에 대응하는 경우 등거리 임베딩이 존재합니다.
• 체 확장: 이러한 조건이 충족되지 않을 경우, 프레임워크는 이전에 임베딩된 서브트리를 수정하지 않고도 임베딩을 가능하게 하기 위해 기본 체 $K$를 확장(가치 군 또는 잔여체를 확장)하는 구성적 절차를 제공합니다.

2.4 최적화 이론

본 논문은 $\ell = \sum a_i |f_i|$ (여기서 $a_i > 0$ 이고 $f_i$는 다항식) 형태의 함수를 최소화하기 위한 이론을 개발합니다.

• 최소화 존재성: 정리 52와 55는 특정 기하학적 조건 하에서 전역 최솟값이 존재함을 입증합니다. 구체적으로, 다항식의 영점 집합(zero loci)의 사영 폐쇄(projective closures)가 아핀 공간 $K^n$ 내에서 교차하거나, 혹은 전혀 교차하지 않는 경우 전역 최솟값이 존재합니다.
• 국소화(Localization): 단변량의 경우, 모든 전역 최솟값은 다항식의 계수에 의해 결정되는 유계 영역 내에 국한됩니다(정리 62).
• 알고리즘: 저자들은 폴디스크 환경에 맞춰 여러 최적화 전략을 적용합니다:
  • 최선 우선 하강법(Best-First Descent): 폴디스크의 탐욕적 정제(greedy refinement).
  • 최선 우선 경사 하강법(Best-First Gradient Descent): 방향 도함수를 사용하여 가장 가파른 하강 방향의 브랜치를 선택합니다.
  • 결정론적 낙관적 최적화(Deterministic Optimistic Optimisation, DOO): 함수의 립시츠(Lipschitz) 성질로부터 유도된 상한 신뢰 구간을 사용하여 탐색(exploration)과 활용(exploitation)의 균형을 맞춥니다.
  • 몬테카를로 트리 탐색(MCTS): 노드가 여러 부모를 가질 수 있는 고차원 폴디스크의 유향 비순환 그래프(DAG) 구조를 처리하기 위해 DAG-MCTS 변형을 포함하여 폴디스크 공간에 MCTS를 적응시킵니다.

3. 주요 기여

1. 기하학적 프레임워크: 계층적 데이터(임베딩된 트리)의 자연스러운 표현이자 최적화의 도메인(측지선 및 기울기)으로서, 계산 가능한 경로 연결된 도메인인 폴디스크 공간($B^n, H^n$)을 도입하여 이 둘 사이의 간극을 메웁니다.
2. 함수 클래스: 절대 다항식과 가치 다항식을 정의하고, 이들의 측지선 상의 조각별 구조와 보편 근사 능력을 증명합니다.
3. 최적화 이론: 영점 집합의 기하학적 조건에 따른 절대 다항식의 양의 선형 결합에 대한 전역 최솟값 존재성을 입증하고, 단변량의 경우 최솟값에 대한 명시적 경계를 도출합니다.
4. 알고리즘 적응: 폴디스크 공간의 계층적, 분기적 기하학에 맞춤화된 최적화 알고리즘(Best-First, Gradient Descent, DOO, MCTS)을 공식화합니다.
5. 소프트웨어 구현: 기하학적 객체, 함수 클래스 및 최적화 알고리즘을 구현한 오픈 소스 줄리아(Julia) 라이브러리인 NonArchimedeanMachineLearning.jl을 개발하여 공개합니다.

4. 결과 및 실험적 발견

저자들은 이론적 프레임워크를 검증하기 위해 자신들의 줄리아 라이브러리를 사용하여 계산 실험을 수행했습니다:

• 다항식 근 찾기: 알고리즘은 $\mathbb{Q}_p$ 상의 다항식 근으로 성공적으로 수렴했습니다. 단순 근 찾기 작업에서는 MCTS와 Best-First 방법이 DOO보다 빠른 수렴 속도를 보였습니다.
• 절대 다항식 합 최소화: 알고리즘은 절대값 다항식의 합을 최소화하는 데 테스트되었습니다. M-C-T-S와 DAG-MCTS는 특히 더 복잡한 손실 지형을 가진 시나리오에서 탐욕적 방법보다 최종 손실 측면에서 일반적으로 더 우수한 성능을 보였으나, 계산 비용은 더 높았습니다.
• 다항식 보간(Interpolation): 프레임워크는 주어진 점들을 지나는 다항식의 계수를 찾는(제곱 오차 손실을 최소화하는) 보간 문제를 성공적으로 해결했습니다.
• 함수 학습: 저자들은 절대 다항식을 가설 클래스로 사용하여 함수(이진 레이블 근사)를 학습하는 능력을 입증했습니다.
• 성능: MCTS 기반 방법은 다양한 작업에서 가장 좋은 평균 순위를 달립지만, 탐욕적 하강법에 비해 더 많은 함수 호출과 실행 시간을 필요로 했습니다. 실험을 통해 MCTS의 시뮬레이션 횟수를 늘리면 성능이 향상됨을 확인했습니다.

5. 의의 및 주장

본 논문은 비아르키메데스 공간에서의 최적화 및 머신러닝을 위한 수학적 및 계산적 토대를 제공한다고 주장합니다. 그 의의는 다음과 같습니다:

• 표현과 최적화의 통합: 계층적 데이터의 자연스러운 표현(임베딩된 트리)이자 최적화의 도메인(측지선 및 기울기)으로서 하나의 공간($B^n$)을 제공합니다.
• 위상적 장벽 극복: 완전히 불연결된 체 $K^n$에서 경로 연결된 폴디스크 공간 $B^n$으로 이동함으로써, 기존에는 적용할 수 없었던 경사 기반 및 트리 탐색법의 사용을 가능하게 합니다.
• 실질적 실행 가능성: NonArchimedeanMachineLearning.jl 라이브러리 개발은 이러한 이론적 구조가 계산적으로 실행 가능하다는 것을 보여주며, 비아르키메데스 기하학, 최적화, 머신러닝의 접점에서 향후 연구를 위한 도구를 제공합니다.

저자들은 현재 프레임워크가 절대 다항식에 집중하고 있지만, 이 접근 방식은 모듈형이며 더 넓은 함수 클래스로 확장될 수 있다고 언급했습니다. 이들은 본 작업을 기존의 쌍곡 또는 고차원 유클리드 접근 방식과는 구별되는, 계층적 데이터를 다루기 위한 새로운 패러다임의 개념 증명(proof-of-concept)으로 위치시킵니다.