Home Page

Papers

Submissions

News

Editorial Board

Proceedings

Open Source Software

Search

Statistics

Login

Frequently Asked Questions

Contact Us



RSS Feed

On Solving Probabilistic Linear Diophantine Equations

Patrick Kreitzberg, Oliver Serang; 22(87):1−24, 2021.

Abstract

Multiple methods exist for computing marginals involving a linear Diophantine constraint on random variables. Each of these extant methods has some limitation on the dimension and support or on the type of marginal computed (e.g., sum-product inference, max-product inference, maximum a posteriori, etc.). Here, we introduce the "trimmed $p$-convolution tree'" an approach that generalizes the applicability of the existing methods and achieves a runtime within a $\log$-factor or better compared to the best existing methods. A second form of trimming we call underflow/overflow trimming is introduced which aggregates events which land outside the supports for a random variable into the nearest support. Trimmed $p$-convolution trees with and without underflow/overflow trimming are used in different protein inference models. Then two different methods of approximating max-convolution using Cartesian product trees are introduced.

[abs][pdf][bib]        [code]
© JMLR 2021. (edit, beta)