Source-linked AI summary
Probabilistic Circuits as Reasoning Machines in Artificial Intelligence (Part I)
Robert Peharz
TL;DR
Probabilistic inference는 개념적으로 단순하지만, summation과 integration이 지수적으로 증가할 수 있어 일반적으로 계산적으로 다루기 어렵다. 이 논문은 재귀적이고 tractable한 conditioning 및 관련 reasoning 연산을 지원하는 구조적 제약 모델로서 probabilistic circuits를 연구하며, 이를 hierarchical mixture 및 deep-learning 구현과 연결한다.
문제
Probabilistic inference는 개념적으로 단순하지만, 문제의 차원에 따라 지수적으로 증가하는 summation 또는 integration을 일반적으로 요구한다.
방법
이 논문은 decomposable하고 smooth한 probabilistic circuits를 사용한다. 이 회로의 normalized node는 hierarchical mixture를 형성하며, conditionals는 재귀적으로 계산된다.
결과
Probabilistic circuits는 sum node와 product node를 통해 conditioning을 tractable한 input distribution으로 위임함으로써 재귀적 conditional distribution을 제공한다.
시사점 및 한계
Probabilistic circuits는 probabilistic structure와 deep-learning system에 대한 interface를 유지하면서 uncertainty 하에서 reasoning을 수행하기 위한 tractable framework를 제공한다.
시사점 및 한계
Continuous density에서는 most probable explanation이 real-valued state space에서 바람직한 decision에 대응하지 않을 수 있다.
Abstract
from arXiv · showhide
This cumulative habilitation thesis studies probabilistic circuits (PCs) as a powerful and tractable framework for reasoning and learning under uncertainty in artificial intelligence (AI). It first advocates for probability as a core language for AI, emphasizing its connections to logic and information theory; the conceptual simplicity of probabilistic reasoning---based primarily on the sum and product rules; the parallels between probabilistic inference and human cognition; and the role of probability in optimal decision making. However, probability also faces significant computational challenges, as probabilistic inference is NP-hard in almost all probabilistic models. PCs address these challenges through structural constraints that ensure exact computation of a wide range of inference queries in polynomial time, such as marginals, conditionals, most probable explanations, expectations, and more advanced inference tasks. This thesis synthesizes a decade of research across foundations, algorithmic developments, and empirical validation of PCs. Key contributions highlighted in this work are foundational theory of PCs, Bayesian approaches for learning PCs, scalable implementations and integration with deep learning, hybrid models that combine PCs with intractable models, and connections with symbolic machine learning paradigms. This is the first part of my Habilitation Thesis. The second part is omitted, as it comprises the cumulative part of the thesis and has been published at various venues (see Chapter 5).
확률적 추론과 AI · 서론
이 논문은 지식 표현, 추론, 학습을 중심으로 합리적 AI를 정립하고, 불확실성을 논리, 인간의 추론, 의사결정 이론, 정보 이론과 연결하는 개념적으로 단순한 언어로서 확률을 제안한다. Probabilistic circuits는 구조적 제약을 부과해 완전한 결합분포에 대한 tractable하고 유연한 추론을 가능하게 함으로써 확률의 계산적 어려움에 대응한다.
- 서론 · 1.1 AI란 무엇인가(대략적으로)?: 이 논문은 합리적 AI의 미니멀한 핵심인 지식 표현, 추론, 학습에 초점을 맞추며, 이를 인간 지향적 능력과 구분한다.추론은 저장된 정보에서 새로운 통찰을 도출하고, 학습은 시스템의 지식 표현을 적응적으로 수정하거나 확장한다.
- 단순성: 확률적 추론은 개념적으로 단순하지만, 합과 적분이 문제 차원에 따라 지수적으로 확장될 수 있어 계산적으로 어렵다.합 규칙은 알려지지 않은 사실을 주변화하고, 곱 규칙은 관측에 조건화하며, 추론은 이 규칙들을 연쇄적으로 적용해 관측에서 예측으로 정보를 전파한다.
- 의사결정 · 상식적 추론과의 정성적 유사성: 확률은 의사결정을 기대 손실 최소화 문제로 정의해 최적 의사결정을 지원하며, 비단조적 믿음 갱신과 explaining away를 자연스럽게 표현한다.이러한 특성은 확률적 추론을 의사결정 이론 및 Pearl 이 논의한 상식적 추론의 정성적 특성과 연결한다.
- 1.2 확률의 역할 · Bayesianism과 논리의 일관성 · 정보 이론: 확률은 개념적 단순성을 제공하고 불확실성을 표현하며 논리, 인간의 추론, 의사결정 이론, 정보 이론과 연결되므로 AI를 위한 탁월한 핵심 언어로 제안된다.그 기초에는 합 규칙과 곱 규칙이 있으며, 극단적 확률은 명제 논리를 복원하고 Bayesian learning은 사후 추론을 데이터가 주어졌을 때 매개변수에 대해 확률적으로 추론하는 과정으로 다룬다.
- 1.3 왜 Probabilistic Circuits인가?: 고전적 확률 모델은 영역을 정확하게 표현할 수 있지만 실행하기는 여전히 어렵다. probabilistic graphical models의 추론은 tree-width에 따라 지수적으로 확장될 수 있는 반면, 특정 과업에 맞춘 neural networks는 유연한 결합 추론을 제공하지 못한다.임의의 feature conditional을 예측하려면 완전한 결합분포에 대한 모델이 필요하며, deep generative models에서도 추론은 일반적으로 어렵다.
- 1.3 왜 Probabilistic Circuits인가?: Probabilistic circuits는 구조적 제약을 강제해 완전한 결합 확률 모델링과 유연하고 tractable한 추론을 결합하며, probabilistic graphical models와 neural networks의 혼합형을 이룬다.그 구조는 tractable한 추론 연산을 보장하며, variable elimination, junction trees [28], arithmetic circuits, sum-product networks, cutset networks, probabilistic sentential decision diagrams 에서 반복적으로 나타나는 패턴을 활용한다.
- 1.3 왜 Probabilistic Circuits인가?: PCs는 완전히 새로운 모델 클래스를 도입하기보다 공통 구문 아래 기존의 tractable한 확률 모델링 및 exact-inference 접근법을 통합한다.구조적 제약은 어떤 추론 연산이 tractable하게 유지되는지를 결정하고, 관련 접근법들 사이의 차이를 구분한다.
- 1.3 왜 Probabilistic Circuits인가?: Probabilistic circuits는 tractable한 추론을 위해 표현 효율성과 아키텍처의 자유도를 절충하므로, 근사 없이는 본질적으로 어려운 확률 문제를 쉽게 만들지 못한다.제약은 neural-network 구조의 선택을 제한하며, 따라서 표현 효율성에도 한계를 부과한다.
기초 확률 이론
이 절은 확률적 추론의 기초 형식론으로서 확률공간을 제시하며, 표본공간, 논리적으로 구조화된 사건들의 sigma-algebra, 확률측도를 결합한다. 이 틀이 확률을 정확히 규정하면서도 random variables와 같은 더 직관적인 표현을 동기화할 만큼 추상적이라는 점을 강조한다.
- 확률공간: 확률공간은 확률적 AI의 기초 계약이다. 모든 확률적 논증은 (Ω,Σ,P)로 환원되어야 하며, 그렇지 않다면 확률이 아니다.이는 추상적이고 복잡한 확률 모델에 대한 건전성 기준을 제공한다.
- 가측공간: 가측공간은 공집합이 아닌 표본공간 Ω와 사건을 모으면서 논리적 부정, 논리합, 논리곱을 부호화하는 sigma-algebra Σ로 구성된다.sigma-algebra는 여집합과 가산 합집합에 대해 닫혀 있으며, 결과적으로 가산 교집합에 대해서도 닫혀 있다.
- 사건과 추상화: sigma-algebra는 원자적 결과보다 더 거시적인 사건 표현을 제공할 수 있다. 이는 모든 singleton 결과를 포함하지 않고 선택된 사건을 포함하는 주사위 모델에서 확인된다.주사위의 경우 Σ는 {1}과 {2}를 포함하지만 {3}과 {4}는 포함하지 않는다.
- 확률공간: 확률공간은 사건에 확률을 할당하고, Ω에 확률 1을 부여하며, 서로소 사건들에 대해 가산가법적인 측도 P:Σ→[0,1]을 추가한다.이 정의는 또한 P(∅)=0 및 P(Ā)=1−P(A)를 함의한다.
- 직관과 표현: 확률공간의 정의는 정확하고 최소주의적이지만 직관은 제한적으로 제공하므로, Ω 위의 불확실성을 더 해석하기 쉬운 공간 X로 변환하는 random variables를 동기화한다.그 결과로 얻은 공간도 확률측도로 기술된다.
확률적 추론
확률적 추론은 분포 함수를 사용해 지식을 표현하고 개념적으로 단순한 계산법으로 질의에 답하지만, 유용한 많은 계산은 여전히 NP-hard다. 핵심 연산에는 marginalization, conditioning, optimization, 기대 손실에 기반한 의사결정이 포함된다.
- 기초: 분포 함수는 의존성과 불확실성을 표현하며, 추론은 표현된 지식에 관한 관심 질의에 답한다.
- 계산 범위: 추론은 기댓값과 optimization도 지원하지만, 확률 모델에서 이러한 질의는 일반적으로 NP-hard다.Probabilistic circuits는 이러한 질의를 tractable하게 계산하기 위한 framework로 도입된다.
- Marginalization: Marginalization은 변수 Z를 적분해 제거하여 부분집합 Y에 대한 exact distribution을 얻으며, 알려지지 않은 양을 무시하거나 고려하면서 추론할 수 있게 한다.이 연산은 일관적이다. 변수를 marginalization하는 순서가 달라도 동일한 marginal이 얻어진다.
- Conditioning: Conditioning은 Z=z라는 증거를 관측하거나 주입한 뒤 Y에 대한 분포를 업데이트하며, 연속형 Z에서는 pZ(z)가 0이 아니고 연속일 때 잘 정의된다.
- 의사결정: 기대 손실 최소화는 조건부 분포를 명시적 결정으로 변환한다. squared loss는 mean을 선택하는 반면 absolute loss는 median을 선택하며 이상치에 강건하다.이 결정 단계는 분포의 불확실성을 버리므로 이상적으로는 마지막에 수행한다. 최적성을 위해서는 적절한 loss, 실제 데이터 생성 분포, exact computation이 필요하다.
최신 연구 동향
불확실성을 표현해야 할 필요성이 분명해지면서, 초기에는 확률의 계산적 어려움에 대한 우려가 있었음에도 AI에서 확률적 접근법이 부상했다. Graphical models는 확률적 구조를 표현하는 직관적 언어를 제공하지만, exact inference는 일반적으로 어려워 tractable restriction과 대안적 deep model이 요구되었다.
- 최신 연구 동향: AI가 logic-based method에서 probabilistic approach로 전환한 것은 실제 세계의 시나리오에 uncertainty modeling이 필요하다는 인식이 커졌음을 반영했다.Probability는 계산상의 어려움과 실용성에 대한 의문으로 처음에는 비판받았지만, 점차 입지를 넓혔다.
- 최신 연구 동향: Graphical model, 특히 Bayesian networks는 conditional independence를 구조적으로 표현하고 tractable inference와 learning을 지원하기 때문에 probabilistic modeling의 초석이자 lingua franca로 남아 있다.Deep learning 시대에 그 위상은 다소 낮아졌지만, 시각적 표현은 model structure와 assumption을 명시하는 데 여전히 유용하다.
- 최신 연구 동향: Graphical model에서 exact marginalization은 일반적으로 NP-hard인 반면, bounded-treewidth model은 tractable exact inference를 허용한다.대부분의 probabilistic machine learning system은 구조와 assumption을 간결하게 표현하는 graphical model로 대응시킬 수 있다.
- 최신 연구 동향: Deep autoregressive model 은 shared neural network와 probability chain rule을 사용하며, 원칙적으로 모든 joint distribution을 표현할 수 있다.이는 fully connected Bayesian network로 볼 수 있으며, sampling과 density evaluation을 지원한다.
- 최신 연구 동향: Deep autoregressive model은 sampling과 density evaluation을 지원함에도 불구하고 marginals, conditionals, complex inference를 수행하는 데 여전히 remain challenging하다.이러한 한계는 이를 fully connected Bayesian network로 해석하는 데서 비롯된다.
46 최신 연구 동향
현대 probabilistic model은 표현력이 높은 generative representation을 우선하지만, 많은 모델이 approximate inference에 의존하거나 tractable density, marginal, conditional evaluation을 제공하지 못한다. 이는 불확실성하의 엄밀한 reasoning framework라는 probability의 이상과 대조된다.
- Neural generative model: VAEs 는 neural network를 사용해 단순한 latent distribution을 유연한 infinite-mixture model로 변환하며, amortized encoder는 ELBO objective를 통해 posterior를 근사한다.Exact inference는 어렵기 때문에 ELBO는 학습을 위한 log-likelihood의 lower bound를 제공한다.
- Neural generative model: GANs 는 likelihood bound를 최대화하는 대신 discriminator를 adversarial하게 학습해 realistic sampling을 가능하게 하지만, 일반적으로 density evaluation이나 tractable marginal 및 conditional inference는 제공하지 못한다.이들의 objective는 maximum likelihood 와 다른 probabilistic divergence를 최소화한다.
- Neural generative model: Normalizing Flows 는 bijective transformation을 통해 exact density computation과 sampling을 제공하지만, marginal과 conditional은 여전히 어렵다.이들은 단순한 distribution에서 시작해 change-of-variables formula를 사용하여 변환된 density를 계산한다.
- Energy- 및 score-based model: Energy-based model과 score-based model은 표현력이 매우 높지만, density evaluation, sampling, marginal, conditional은 일반적으로 intractable하거나 approximation-dependent하다.Score-Based Models 는 검증하기 어려운 근사에도 불구하고 diffusion 및 Langevin dynamics [61]와 결합될 때 현재 image generation의 state of the art를 이룬다.
- Probabilistic modeling landscape: Probabilistic Programming [69]은 유연한 model을 program으로 표현하며, posterior query는 일반적으로 variational inference 또는 Monte Carlo로 처리되어 분야 전반의 approximation 의존을 보여준다.Gaussian Processes 는 대표적인 예외 중심 probabilistic modeling framework로, Gaussianity를 통해 marginal computation을 지원하고 Bayesian modeling 및 optimization 에 응용된다.
확률 회로
Probabilistic circuits는 일부 표현 효율성을 희생하는 대신 정확한 polynomial-time inference를 가능하게 하는 구조적 제약을 부과함으로써 probabilistic reasoning을 tractable하게 만든다. 이 장에서는 Probabilistic circuits의 핵심 연산을 전개하고, PCs에 대한 foundational, algorithmic, learning 기여를 아우르는 십 년간의 연구를 요약한다.
- 동기와 범위: PC는 주변분포와 조건부 분포 같은 추론 과제를 다항 시간 내에 정확히 계산하므로, 근사 없이 확률적 추론을 유지한다.이러한 tractability는 smoothness, decomposability, determinism 및 관련 성질을 포함한 구조적 제약에서 비롯된다.
- 표현력과 정규화: PC의 tractability는 표현력의 대가로 얻어진다. 다른 확률 모델에서는 간결한 일부 분포가 PC로는 지수적으로 큰 표현을 요구하기 때문이다.정규화된 sum weight는 표현된 분포를 바꾸지 않고도 효율적으로 복원할 수 있으므로 모델링 능력을 향상시키지 않는다.
- 주변화: 입력 분포가 tractable한 주변분포 계산을 지원한다면, decomposability와 smoothness를 통해 선형 시간 주변화가 가능하다.그 결과로 얻은 marginal PC는 원래 PC의 정확한 주변분포를 표현한다.
- 조건화: 조건화는 sum node와 product node를 통해 재귀적으로 위임할 수 있으며, 이는 정확한 조건부 분포를 표현하는 conditional PC를 산출한다.product node에서는 조건부 연산이 조건부들의 곱에 대해 분배된다.
- 고차 추론: 동일한 구조적 성질은 vector 및 matrix 값 message passing을 통해 정확한 기댓값과 공분산 계산을 지원한다.root vector는 PC의 기댓값과 같고, 공분산 행렬은 입력 공분산으로부터 재귀적으로 계산된다.
- 응용과 기여: 이 장에서는 PC를 계층적 잠재변수 모델로도 전개하고, sampling, expectation-maximization, representation learning, semi-supervised classification 및 추가적인 확률 질의로 확장한다.또한 determinism은 빠른 전역 maximum-likelihood parameter 계산과 closed-form Bayesian structure score를 가능하게 한다.