Fast Information Value for Graphical Models
Brigham Anderson, Andrew Moore · 2005
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. 1