Circuit representations are becoming the lingua franca to express and reason about tractable generative and discriminative models. In this paper, we show how complex inference scenarios for these models that commonly arise in machine learning---from computing the expectations of decision tree ensembles to information-theoretic divergences of sum-product networks---can be represented in terms of tractable modular operations over circuits. Specifically, we characterize the tractability of simple transformations---sums, products, quotients, powers, logarithms, and exponentials---in terms of sufficient structural constraints of the circuits they operate on, and present novel hardness results for the cases in which these properties are not satisfied. Building on these operations, we derive a unified framework for reasoning about tractable models that generalizes several results in the literature and opens up novel tractable inference scenarios.

A Compositional Atlas of Tractable Circuit Operations for Probabilistic Inference / Vergari, Antonio; Choi, Yoojung; Liu, Anji; Teso, Stefano; Van den Broeck, Guy. - ELETTRONICO. - (2021). (Intervento presentato al convegno NeurIPS tenutosi a online nel 6th Dec-14thDec 2021).

A Compositional Atlas of Tractable Circuit Operations for Probabilistic Inference

Teso, Stefano;
2021-01-01

Abstract

Circuit representations are becoming the lingua franca to express and reason about tractable generative and discriminative models. In this paper, we show how complex inference scenarios for these models that commonly arise in machine learning---from computing the expectations of decision tree ensembles to information-theoretic divergences of sum-product networks---can be represented in terms of tractable modular operations over circuits. Specifically, we characterize the tractability of simple transformations---sums, products, quotients, powers, logarithms, and exponentials---in terms of sufficient structural constraints of the circuits they operate on, and present novel hardness results for the cases in which these properties are not satisfied. Building on these operations, we derive a unified framework for reasoning about tractable models that generalizes several results in the literature and opens up novel tractable inference scenarios.
2021
Advances in neural information processing systems 34 (NeurIPS 2021)
San Diego, CA
NeurIPS foundation
9781713845393
Vergari, Antonio; Choi, Yoojung; Liu, Anji; Teso, Stefano; Van den Broeck, Guy
A Compositional Atlas of Tractable Circuit Operations for Probabilistic Inference / Vergari, Antonio; Choi, Yoojung; Liu, Anji; Teso, Stefano; Van den Broeck, Guy. - ELETTRONICO. - (2021). (Intervento presentato al convegno NeurIPS tenutosi a online nel 6th Dec-14thDec 2021).
File in questo prodotto:
File Dimensione Formato  
reno32_compositional_atlas.pdf

Solo gestori archivio

Tipologia: Pre-print non referato (Non-refereed preprint)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 718.54 kB
Formato Adobe PDF
718.54 kB Adobe PDF   Visualizza/Apri
NeurIPS-2021-a-compositional-atlas-of-tractable-circuit-operations-for-probabilistic-inference-Paper.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 546.34 kB
Formato Adobe PDF
546.34 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/323847
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 26
  • ???jsp.display-item.citation.isi??? 0
  • OpenAlex ND
social impact