{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:09:38Z","timestamp":1757617778882,"version":"3.44.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T00:00:00Z","timestamp":1745452800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T00:00:00Z","timestamp":1745452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["2020.09139.BD","UIDP\/00048\/2020"],"award-info":[{"award-number":["2020.09139.BD","UIDP\/00048\/2020"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005727","name":"Universidade de Coimbra","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005727","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Probabilistic models with tractable marginalization are those in which evidence queries involving marginalization of variables are guaranteed to be computable in polynomial time in the size of the model. The tractability of marginalization of current classes of tractable probabilistic models is achieved through structural properties imposed over the functions they decompose to and it is an open question whether there are more general classes of probabilistic models with tractable marginalization than the current ones. That question is settled in this paper by the usage of boolean circuits to express them. On one hand, bounds on the number of simple and local operations required by a circuit to solve a problem are used as measures of complexity and on the other the circuit value problem is guaranteed to have complexity bounded by a polynomial function on the number of its gates. It is shown that choices of the definitions of the variables to use have an impact on the circuit description length as they are paramount to definitions of simplicity and locality. The framework that is put forward builds on a construction of a circuit representation of a dataset and on the definition of problems that take that circuit as an input such that the answers of the problems correspond to values of interest. Based on that, a set of circuit value problems are defined so that given inputs that identify queries of interest, the corresponding output values are obtained as a result of evaluation of those circuits. This approach is more general than current ones, in that, for any algorithm that runs in polynomial time over a model there is a circuit with number of gates bounded by a polynomial function of the time that the algorithm takes to be executed.<\/jats:p>","DOI":"10.1007\/s10618-025-01101-x","type":"journal-article","created":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T15:27:35Z","timestamp":1745508455000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tractable probabilistic models and computational complexity"],"prefix":"10.1007","volume":"39","author":[{"given":"David","family":"Cruz","sequence":"first","affiliation":[]},{"given":"Jorge","family":"Batista","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,4,24]]},"reference":[{"key":"1101_CR1","unstructured":"Affandi RH, Fox E, Adams R, Taskar B (2014) Learning the parameters of determinantal point process kernels. In: International conference on machine learning, pp. 1224\u20131232 . PMLR"},{"key":"1101_CR2","unstructured":"Bilmes J (2022) Submodularity in machine learning and artificial intelligence. arXiv preprint arXiv:2202.00132"},{"issue":"6\u20137","key":"1101_CR3","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1016\/j.artint.2007.11.002","volume":"172","author":"M Chavira","year":"2008","unstructured":"Chavira M, Darwiche A (2008) On probabilistic inference by weighted model counting. Artif Intell 172(6\u20137):772\u2013799","journal-title":"Artif Intell"},{"issue":"6\u20137","key":"1101_CR4","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1016\/j.artint.2007.11.002","volume":"172","author":"M Chavira","year":"2008","unstructured":"Chavira M, Darwiche A (2008) On probabilistic inference by weighted model counting. Artif Intell 172(6\u20137):772\u2013799","journal-title":"Artif Intell"},{"key":"1101_CR5","unstructured":"Chavira M, Darwiche A (2007) Compiling bayesian networks using variable elimination. In: IJCAI, vol. 2443 . Citeseer"},{"key":"1101_CR6","unstructured":"Choi A, Broeck G, Darwiche A (2015a) Tractable learning for structured probability spaces: A case study in learning preference distributions. In: Twenty-fourth international joint conference on artificial intelligence"},{"key":"1101_CR7","unstructured":"Choi A, Broeck G, Darwiche A (2015b) Probability distributions over structured spaces. In: 2015 AAAI spring symposium series"},{"key":"1101_CR8","unstructured":"Choi A, Darwiche A (2017) On relaxing determinism in arithmetic circuits. In: Proceedings of the 34th international conference on machine learning-volume 70, pp. 825\u2013833 . JMLR. org"},{"key":"1101_CR9","unstructured":"Darwiche A (2002) A logical approach to factoring belief networks. KR 2, 409\u2013420"},{"key":"1101_CR10","unstructured":"Darwiche A (2011) Sdd: A new canonical representation of propositional knowledge bases. In: Twenty-second international joint conference on artificial intelligence"},{"key":"1101_CR11","unstructured":"Grigorescu E, Juba B, Wimmer K, Xie N (2022) Hardness of maximum likelihood learning of dpps. In: Conference on learning theory, pp. 3800\u20133819 . PMLR"},{"key":"1101_CR12","unstructured":"Harviainen J, Ramaswamy VP, Koivisto M (2023) On inference and learning with probabilistic generating circuits. In: Uncertainty in artificial intelligence, pp. 829\u2013838 . PMLR"},{"key":"1101_CR13","unstructured":"Kisa D, Broeck G, Choi A, Darwiche A (2014) Probabilistic sentential decision diagrams. In: Fourteenth international conference on the principles of knowledge representation and reasoning"},{"key":"1101_CR14","volume-title":"Probabilistic graphical models: Principles and techniques","author":"D Koller","year":"2009","unstructured":"Koller D, Friedman N (2009) Probabilistic graphical models: Principles and techniques. MIT Press, USA"},{"issue":"1","key":"1101_CR15","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"RE Ladner","year":"1975","unstructured":"Ladner RE (1975) The circuit value problem is log space complete for p. ACM Sigact News 7(1):18\u201320","journal-title":"ACM Sigact News"},{"key":"1101_CR16","doi-asserted-by":"crossref","unstructured":"Poon H, Domingos P (2011) Sum-product networks: A new deep architecture. In: 2011 IEEE international conference on computer vision workshops (ICCV Workshops), pp. 689\u2013690 . IEEE","DOI":"10.1109\/ICCVW.2011.6130310"},{"key":"1101_CR17","doi-asserted-by":"crossref","unstructured":"Shen Y, Choi A, Darwiche A (2018) Conditional psdds: Modeling and learning with modular knowledge. In: Proceedings of the AAAI conference on artificial intelligence, vol. 32","DOI":"10.1609\/aaai.v32i1.12119"},{"key":"1101_CR18","doi-asserted-by":"crossref","unstructured":"Shen Y, Goyanka A, Darwiche A, Choi A (2019) Structured bayesian networks: From inference to learning with routes. In: Proceedings of the AAAI conference on artificial intelligence, vol. 33, pp. 7957\u20137965","DOI":"10.1609\/aaai.v33i01.33017957"},{"key":"1101_CR19","doi-asserted-by":"publisher","unstructured":"Valiant LG (1979a) Completeness classes in algebra. In: Proceedings of the eleventh annual ACM symposium on theory of computing. STOC \u201979, pp. 249\u2013261. Association for Computing Machinery, New York, NY, USA . https:\/\/doi.org\/10.1145\/800135.804419","DOI":"10.1145\/800135.804419"},{"issue":"3","key":"1101_CR20","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant LG (1979) The complexity of enumeration and reliability problems. SIAM J Comp 8(3):410\u2013421","journal-title":"SIAM J Comp"},{"issue":"2","key":"1101_CR21","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant LG (1979b) The complexity of computing the permanent. Theor Comp Sci 8(2):189\u2013201","journal-title":"Theor Comp Sci"},{"key":"1101_CR22","first-page":"13189","volume":"34","author":"A Vergari","year":"2021","unstructured":"Vergari A, Choi Y, Liu A, Teso S, Broeck G (2021) A compositional atlas of tractable circuit operations for probabilistic inference. Adv Neural Inf Process Syst 34:13189\u201313201","journal-title":"Adv Neural Inf Process Syst"},{"key":"1101_CR23","doi-asserted-by":"publisher","DOI":"10.2307\/j.ctvckq7xb","volume-title":"Mathematics and computation: A theory revolutionizing technology and science","author":"A Wigderson","year":"2019","unstructured":"Wigderson A (2019) Mathematics and computation: A theory revolutionizing technology and science. Princeton University Press, USA"},{"key":"1101_CR24","unstructured":"Zhang H, Holtzen S, Broeck G (2020) On the relationship between probabilistic circuits and determinantal point processes. In: Conference on uncertainty in artificial intelligence, pp. 1188\u20131197 . PMLR"},{"key":"1101_CR25","unstructured":"Zhang H, Juba B, Broeck G (2021) Probabilistic generating circuits. In: International conference on machine learning, pp. 12447\u201312457 . PMLR"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-025-01101-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-025-01101-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-025-01101-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T11:55:03Z","timestamp":1757159703000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-025-01101-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,24]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["1101"],"URL":"https:\/\/doi.org\/10.1007\/s10618-025-01101-x","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"type":"print","value":"1384-5810"},{"type":"electronic","value":"1573-756X"}],"subject":[],"published":{"date-parts":[[2025,4,24]]},"assertion":[{"value":"14 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"29"}}