Part of Advances in Neural Information Processing Systems 18 (NIPS 2005)
Brigham S. Anderson, Andrew W. Moore
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.