Fast Information Value for Graphical Models

Calculations that quantify the dependencies between variables are vital to many operations with graphical models, e. g. , active learning and sen- sitivity analysis. Previously, pairwise information gain calculation has involved a cost quadratic in network size. In this work, we show how to perform a similar computation with cost linear in network size. The loss function that allows this is of a form amenable to computation by dynamic programming. The message-passing algorithm that results is described and empirical results demonstrate large speedups without de- crease in accuracy. In the cost-sensitive domains examined, superior ac- curacy is achieved.

Authors

• Brigham Anderson
• Andrew Moore

Keywords

No keywords are indexed for this paper.