Geometry-Aware Probabilistic Circuits via Voronoi Tessellations

이 논문은 확률적 회로 (PC) 의 데이터 매니폴드 국소 기하학적 구조를 포착하기 위해 보로노이 테셀레이션을 도입하되, 이로 인한 계산 복잡성 문제를 해결하기 위해 근사 추론 프레임워크와 정확한 추론이 가능한 구조적 조건을 제안하고 미분 가능한 완화 기법을 통해 학습을 가능하게 합니다.

핵심

1. 기존 모델의 문제점: "고정된 지도"

기존의 확률 회로 (PC) 는 데이터를 학습할 때 전 세계에 똑같은 규칙을 적용합니다.

• 비유: imagine you are a delivery driver. You have a map where every neighborhood is treated the same. You always deliver packages using the exact same route, regardless of whether the area is a busy city center or a quiet countryside.
• 문제: 실제 세상 (데이터) 은 지역마다 다릅니다. 어떤 곳은 산이 많고, 어떤 곳은 평지입니다. 그런데 모든 지역에 똑같은 길만 고집하면, 복잡한 지형 (데이터의 국소적 구조) 을 제대로 이해하지 못해 비효율적이 됩니다.

2. 새로운 아이디어: "보로노이 테셀레이션 (Voronoi Tessellations)"

저자들은 데이터의 모양에 따라 지역을 나누는 **'보로노이 테셀레이션'**이라는 기하학적 도구를 도입했습니다.

• 비유: 도시를 여러 개의 구역으로 나눌 때, 각 구역의 중심 (센트roids) 을 정하고, 그 중심에 가장 가까운 집들은 그 구역에 속하게 하는 방식입니다. 마치 우편배달 구역이나 경찰서 관할 구역을 정할 때 "가장 가까운 관서"를 기준으로 나누는 것과 같습니다.
• 장점: 이렇게 하면 데이터가 모여 있는 모양 (예: 나선형, 원형, 뭉쳐진 덩어리) 에 맞춰 지역을 유연하게 나눌 수 있어 훨씬 정교한 예측이 가능합니다.

3. 핵심 갈등: "정확함 vs 계산의 어려움"

하지만 여기서 큰 문제가 생깁니다.

• 문제: 보로노이 구역은 비스듬하게 기울어진 경계선을 가집니다. 컴퓨터가 이런 비스듬한 경계를 가진 구역을 계산하려면, 수학적으로 매우 복잡한 계산을 해야 합니다. 기존 모델은 "빠르고 정확한 계산"을 위해 단순한 직사각형 구역을 썼는데, 갑자기 비스듬한 구역을 쓰면 계산이 너무 느려져서 (실제 불가능해져서) 쓸모가 없어집니다.
• 핵심: "예쁘고 정확한 구역 (기하학적 구조)"을 만들면 "계산이 너무 어렵고", "계산이 쉬운 구역"을 쓰면 "데이터 모양을 못 따라갑니다."

4. 저자들의 해결책: 두 가지 전략

저자들은 이 딜레마를 해결하기 위해 두 가지 방법을 제시했습니다.

전략 1: "안전한 추측" (Certified Approximate Inference)

정확한 계산을 포기하되, 오류 범위를 гаранти하는 추측을 합니다.

• 비유: 비스듬한 다각형 모양의 땅을 정확히 재기 어렵다면, 그 땅을 포함하는 큰 직사각형과 그 땅을 포함하는 작은 직사각형을 그려보세요.
  • "이 땅의 넓이는 최소 이만큼, 최대 이만큼이다"라고 하한과 상한을 알려주는 것입니다.
  • 완벽하게 정확한 수는 아니지만, "이 범위 안에 틀림없다"는 **보증 (Certificate)**을 받기 때문에 신뢰할 수 있습니다.

전략 2: "맞춤형 구역" (Hierarchical Factorized Voronoi)

계산이 가능하도록 구역의 모양을 모델의 구조에 맞춰서 설계합니다.

• 비유: 비스듬한 경계선을 만들지 않고, 모델이 계산하기 좋은 직사각형 블록으로만 지역을 나눕니다. 마치 레고 블록을 쌓듯이, 각 블록이 서로 독립적으로 계산되도록 설계한 것입니다.
  • 이렇게 하면 계산 속도는 빠르지만, 데이터 모양을 완벽하게 따라가는 것은 조금 제한될 수 있습니다. 하지만 정확한 계산이 가능합니다.

5. 학습 방법: "부드러운 시작, 단단한 마무리"

컴퓨터가 학습할 때, 갑자기 딱딱한 경계선을 만들면 수학적으로 계산이 안 됩니다 (미분이 안 됨).

• 해결책: 처음에는 부드러운 점토처럼 경계선을 흐리게 만듭니다 (Soft Gating). 학습이 진행될수록 점토가 굳어지듯 단단한 경계선으로 바뀝니다 (Annealing).
• 결과: 학습 때는 유연하게 움직여 최적의 모양을 찾고, 최종적으로는 딱딱한 규칙으로 돌아와서 빠르고 정확한 계산을 수행합니다.

6. 실험 결과

저자들은 이 방법을 다양한 모양 (나선형, 매듭, 교차된 원 등) 을 가진 가상의 데이터로 테스트했습니다.

• 결과: 기존 모델들은 이런 복잡한 모양을 잘 이해하지 못했지만, 이 새로운 방법들은 데이터의 모양을 잘 파악하여 훨씬 더 정확한 예측을 했습니다. 특히 "안전한 추측" 방식은 계산이 어렵더라도 신뢰할 수 있는 결과를 주었고, "맞춤형 구역" 방식은 빠르고 정확한 계산을 가능하게 했습니다.

---

요약

이 논문은 **"데이터의 복잡한 모양을 이해하려면, 지역을 유연하게 나누는 게 좋지만, 그렇게 하면 계산이 너무 어려워진다"**는 문제를 해결했습니다.

저자들은 **"정확한 계산을 위해 구역을 단순화하거나 (전략 2), 계산이 어렵더라도 오류 범위를 보장하는 안전한 추측을 한다 (전략 1)"**는 두 가지 길을 제시했습니다. 마치 정교한 지도를 그리되, 계산기에서 바로 계산할 수 있도록 최적화하거나, 혹은 "이 정도는 틀리지 않는다"는 보장을 받는 방법을 찾아낸 것입니다. 이는 인공지능이 복잡한 현실 세계를 더 잘 이해하고 신뢰할 수 있게 만드는 중요한 발전입니다.

기술 요약

1. 문제 정의 (Problem)

확률 회로 (Probabilistic Circuits, PCs) 는 복잡한 데이터 분포를 학습하고 불확실성 하에서 추론을 수행할 수 있는 강력한 생성 모델입니다. PCs 는 구조적 속성 (정합성, 분해 가능성 등) 을 강제함으로써 정확한 (exact) 이산 시간 추론을 가능하게 하여 밀도 추정, 이상치 탐지, 인과 추론 등 다양한 분야에서 활용됩니다.

그러나 기존 PCs 아키텍처의 주요 한계는 합 (Sum) 노드의 혼합 가중치 (mixture weights) 가 데이터와 무관하게 고정되어 있다는 점입니다. 이는 회로 내 라우팅 결정이 전역적으로 고정되어 개별 입력에 따라 적응하지 못함을 의미합니다. 많은 실제 세계 분포는 입력 공간의 영역마다 다른 기하학적 구조 (국소성, 조각별 행동) 를 가지는데, 전역적으로 공유되는 가중치로는 이러한 데이터 매니폴드의 국소 기하학적 구조를 포착하는 데 한계가 있습니다.

핵심 질문: PCs 에 기하학적 인식을 갖춘 입력 의존적 라우팅을 도입하면서도 추론의 계산적 tractability(실용성) 를 유지할 수 있는가?

2. 방법론 (Methodology)

저자들은 보로노이 테셀레이션 (Voronoi Tessellations, VT) 을 PCs 의 합 노드에 통합하여 입력을 학습된 중심점 (centroids) 에 기반한 국소 전문가 (local experts) 로 라우팅하는 방식을 제안합니다. 그러나 보로노이 셀은 경계가 비축방향 (oblique) 인 반공간 (half-space) 의 교차로 정의되므로, 이를 단순히 도입하면 PCs 의 분해 가능성 (decomposability) 을 깨뜨려 추론이 #P-난해 (intractable) 해집니다.

이러한 모순을 해결하기 위해 두 가지 상보적인 전략을 개발했습니다.

A. 인증된 근사 추론 프레임워크 (Certified Approximate Inference)

정확한 추론이 불가능한 일반 VT-PCs 에 대해, 신뢰할 수 있는 하한 및 상한을 제공하는 근사 추론을 제안합니다.

• 박스 근사 (Box Approximation): 복잡한 보로노이 셀을 계산 가능한 축방향 정사각형 (axis-aligned boxes) 으로 근사화합니다.
  • 내부 박스 ($B^-$): 보로노이 셀 내부에 완전히 포함되는 박스 (하한 제공).
  • 외부 박스 ($B^+$): 보로노이 셀을 완전히 포함하는 박스 (상한 제공).
• 적응형 정제 (Adaptive Refinement): 초기 박스 근사가 느슨할 경우, 재귀적으로 박스를 분할하고 보로노이 셀과의 교차 관계를 재분류하여 오차 범위를 줄이는 알고리즘을 적용합니다.
• 결과: 분할 함수 (partition function), 주변 분포 (marginals), 조건부 확률에 대해 수학적으로 증명된 하한과 상한을 보장합니다.

B. 위계적 분해 보로노이 (Hierarchical Factorized Voronoi, HFV)

정확한 추론을 회복하기 위해 기하학적 구조를 회로의 분해 구조와 정렬 (alignment) 시킵니다.

• 구조적 조건: 보로노이 중심점과 셀을 회로의 변수 분할 (variable partition) 과 일치하도록 분해합니다. 즉, 각 합 노드에서 보로노이 셀이 독립적인 변수 집합에 대한 저차원 보로노이 셀의 카테시안 곱 (Cartesian product) 으로 정의되도록 제한합니다.
• 효과: 이 구조는 HFV-PC를 생성하며, 이는 보로노이 가팅과 전문가 분포가 동일한 분해 패턴을 공유하므로, Fubini 정리를 적용하여 고차원 적분을 저차원 적분의 곱으로 분해할 수 있게 합니다.
• 결과: 정확한 (exact) tractable 추론이 회복됩니다.

C. 학습을 위한 소프트 게이팅 (Soft Gating for Learning)

하드 라우팅 (하드 보로노이 할당) 은 미분 불가능하여 경사 기반 학습이 어렵습니다. 이를 해결하기 위해:

• 소프트 보로노이 게이트: 온도가 조절된 소프트맥스 (temperature-scaled softmax) 를 사용하여 거리를 가중치로 변환합니다.
  $$w_k(u; \alpha) = \frac{\exp(-\alpha \|u - c_k\|^2)}{\sum_j \exp(-\alpha \|u - c_j\|^2)}$$
• 어닐링 (Annealing): 학습 초기에는 낮은 온도 ($\alpha$) 로 부드러운 라우팅을 통해 미분 가능하게 학습하고, 학습이 진행됨에 따라 온도를 높여 하드 보로노이 할당으로 수렴시킵니다.
• 수렴 보장: $\alpha \to \infty$일 때 소프트 게이트가 하드 게이트로 지수적으로 빠르게 수렴함을 증명했습니다.

3. 주요 기여 (Key Contributions)

1. 보로노이 기반 PCs 의 최초 제안: PCs 에 기하학적 인식을 도입하기 위해 보로노이 테셀레이션을 기반으로 한 최초의 학습 프레임워크를 제시했습니다.
2. 불일치성 형식화 및 해결: 보로노이 기반 라우팅과 tractable 추론 사이의 근본적인 불일치를 수학적으로 증명하고, 이를 해결하기 위한 두 가지 전략 (인증된 근사 추론과 위계적 분해) 을 제시했습니다.
3. 이론적 분석: 두 접근법 모두에 대해 알고리즘의 속성 (수렴성, 복잡도, 경계 조건) 을 이론적으로 분석하고 잠재적 한계 (차원의 저주 등) 를 규명했습니다.
4. 실험적 검증: 합성 2D 및 3D 데이터셋 (스파이럴, 핀휠, 매듭 등) 에서 제안된 방법 (VT-PC, HFV-PC) 이 기존 베이스라인 (EinsumNet, HCLT) 보다 우수한 성능을 보임을 입증했습니다.

4. 실험 결과 (Results)

• 데이터셋: 2D(문자, 체커보드, 핀휠, 나선) 및 3D(왜곡된 리사주 곡선, 서로 걸린 원, 매듭 등) 의 8 가지 합성 데이터셋을 사용했습니다.
• 성능 비교:
  • VT-PC (인증된 하한): 제약 없는 기하학적 라우팅을 통해 베이스라인의 정확한 로그-가능도 (log-likelihood) 를 능가하는 성능을 보였습니다. 이는 국소 구조를 잘 포착했음을 의미하며, 보수적인 박스 근사에도 불구하고 유효한 하한을 제공했습니다.
  • HFV-PC (정확한 추론): 베이스라인과 유사한 성능을 보였으며, 정확성 (tractability) 을 유지하면서 기하학적 해석 가능성을 제공했습니다.
• 학습 곡선: 온도 어닐링을 통한 소프트 게이트 학습이 안정적으로 수행되었으며, 학습이 진행됨에 따라 하한이 점진적으로 증가하고 신뢰 구간이 수렴하는 것을 확인했습니다.
• 시각화: 핀휠 데이터셋에서 VT-PC 는 데이터의 팔 (arm) 구조에 맞춰 보로노이 셀이 적응하는 것을 보여주었고, HFV-PC 는 축방향으로 정렬된 계층적 분할을 보여주었습니다.

5. 의의 및 결론 (Significance & Conclusion)

이 논문은 기하학적 인식 (Geometry-Awareness) 을 PCs 에 도입함으로써 모델의 표현력 (expressivity) 을 크게 향상시키면서도 추론의 신뢰성을 유지하는 새로운 패러다임을 제시했습니다.

• 해석 가능성: 명시적인 책임 영역 (regions of responsibility) 을 통해 모델의 의사결정 과정을 해석할 수 있게 되었습니다.
• 적용 가능성: 온라인 학습, continual learning, 지식 통합, 이상치 탐지 등 국소적 적응이 필요한 작업에 매우 적합합니다.
• 미래 방향: 학습된 임베딩으로의 확장, 고차원 데이터에 대한 더 강력한 인증 (certification) 기법 개발, 그리고 제어된 생성 (controlled generation) 등으로의 확장이 기대됩니다.

요약하자면, 이 연구는 보로노이 테셀레이션이라는 강력한 기하학적 도구를 확률 회로에 통합하여, 정확한 추론과 국소적 기하학적 구조 모델링이라는 상충되는 목표를 동시에 달성할 수 있는 이론적 기반과 실용적 알고리즘을 제시했다는 점에서 의의가 큽니다.