[공지사항]을 빙자한 안부와 근황 
Show more

Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

The Limits of Tractable Marginalization

Created by
  • Haebom

Author

Oliver Broadrick, Sanyam Agarwal, Guy Van den Broeck, Markus Blaser

Outline

This paper deals with the computational complexity of the marginalization problem, that is, computing the sum over all assignments to some input of a function. Although it is generally computationally hard, there are classes of functions for which marginalization is easy to compute, such as functions that compute multivariable polynomials that can be expressed in polynomial-sized arithmetic circuits (e.g., probabilistic models). This paper presents a negative answer to the question of whether all functions that have a marginalization algorithm in polynomial time can be concisely expressed in such circuits. Assuming $\textsf{FP}\neq \textsf{P}$ (which implies $\textsf{P} \neq \textsf{NP}$), we show that there are simple functions that have traceable marginalization but cannot be efficiently represented in a known model. To this end, we present a hierarchy of complexity classes corresponding to strong forms of marginalization, which are shown to be efficiently computed in a known circuit model. Finally, we present completeness results showing that when there exists an efficient real RAM that performs a virtual proof marginalization of the function, there exists a compact circuit for the multivariable polynomial representation of that function.

Takeaways, Limitations

Takeaways: Deepened the understanding of the computational complexity of the marginalization problem by showing that functions that can be marginalized in polynomial time are not always efficiently represented by polynomial-sized arithmetic circuits. In addition, presented a complexity hierarchy for strong forms of marginalization, and revealed the relationship between real RAMs and circuit representations.
Limitations: Relies on the assumption that $\textsf{FP}\neq \textsf{P}$. Further research is needed to see whether the result holds under more general conditions. Further analysis is needed to see how often the simple functions presented appear in real applications. More comprehensive studies on various types of marginalization problems are needed.
👍