arXiv:2608.31120v1 cs.LG

간결하게 인코딩된 조건부 분포의 호환성 문제 복잡도

On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions

Guy Emerson

제출 2026-08-31

한국어 초록

본 논문의 동기는 기계학습에서 사용되는 확률 모델에 내재된 트레이드오프를 조사하는 것이다. 모델은 종종 조건부 확률의 형태로 예측을 수행하는 데 사용된다. 그러나 조건부 분포 p(x|y)와 p(y|x)의 한 쌍이 어떤 결합 분포 p(x,y)와도 호환되지 않을 수 있다. 이러한 두 조건부가 주어졌을 때 호환 가능한 결합이 존재하는지 판별하는 문제를 호환성 문제(compatibility problem)라 한다. 이산 확률변수의 경우, 조건부가 확률 테이블로 인코딩되면 호환성 문제에는 알려진 해법이 있으며 계산적으로 다루기 쉽다(tractable)다. 본 논문에서는 조건부 분포를 산술 회로(arithmetic circuits)로 인코딩하는 문제의 간결(succinct) 버전을 형식화하고 연구한다. 이는 신경망 모델을 포함하여 고차원 설정에서의 확률 모델링 실용 응용에 해당한다. 우리는 조건부의 간결한 회로 표현에 대해 호환성 문제가 다루기 어렵다(intractable)는 것을 보인다. 모든 확률이 0이 아닌 경우 문제는 co-NP-complete이다. 확률이 0일 수 있는 경우, 여러 호환성 개념이 구별될 수 있음을 보이는 예를 제시하고, 문제의 여러 버전이 PSPACE-complete임을 증명한다. 더 나아가, 다항식 계층(polynomial hierarchy)이 붕괴하지 않는다고 가정하면, 결합을 간결하게 표현할 수 없는 호환 가능한 간결 조건부가 존재함을 보인다. 확률 모델링 및 기계학습에 대한 이러한 결과의 함의를 논의한다.

원문 초록

The motivation for this paper is the investigation of the trade-offs implicit in probabilistic models used in machine learning. Models are often used to make predictions in the form of conditional probabilities. However, a pair of conditional distributions p(x|y) and p(y|x) may not be compatible with any joint distribution p(x,y). Given two such conditionals, determining if there exists a compatible joint is known as the compatibility problem. For discrete random variables, when the conditionals are encoded as probability tables, the compatibility problem has a known solution, which is computationally tractable. In this paper, we formalise and study a succinct version of the problem, encoding conditional distributions as arithmetic circuits. This is applicable to practical applications of probabilistic modelling in high-dimensional settings, including neural network models. We show that, for succinct circuit representations of conditionals, the compatibility problem is intractable. In the case that all probabilities are non-zero, the problem is co-NP-complete. In the case that probabilities can be zero, we give examples to demonstrate that several notions of compatibility can be distinguished, and we prove that multiple versions of the problem are PSPACE-complete. Furthermore, we show that, assuming the polynomial hierarchy does not collapse, there exist compatible succinct conditionals whose joint cannot be expressed succinctly. Implications of these results for probabilistic modelling and machine learning are discussed.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2608.31120v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.