Cumulative distribution networks and the derivative-sum-product algorithm

Jim C. Huang, Brendan J. Frey
Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, PMLR R6:290-297, 2008.

Abstract

We introduce a new type of graphical model called a ’cumulative distribution network’ (CDN), which expresses a joint cumulative distribution as a product of local functions. Each local function can be viewed as providing evidence about possible orderings, or rankings, of variables. Interestingly, we find that the conditional independence properties of CDNs are quite different from other graphical models. We also describe a message-passing algorithm that efficiently computes conditional cumulative distributions. Due to the unique independence properties of the CDN, these messages do not in general have a one-to-one correspondence with messages exchanged in standard algorithms, such as belief propagation. We demonstrate the application of CDNs for structured ranking learning using a previously-studied multi-player gaming dataset.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR6-huang08a, title = {Cumulative distribution networks and the derivative-sum-product algorithm}, author = {Huang, Jim C. and Frey, Brendan J.}, booktitle = {Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence}, pages = {290--297}, year = {2008}, editor = {McAllester, David A. and Myllymäki, Petri}, volume = {R6}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r6/main/assets/huang08a/huang08a.pdf}, url = {https://proceedings.mlr.press/r6/huang08a.html}, abstract = {We introduce a new type of graphical model called a ’cumulative distribution network’ (CDN), which expresses a joint cumulative distribution as a product of local functions. Each local function can be viewed as providing evidence about possible orderings, or rankings, of variables. Interestingly, we find that the conditional independence properties of CDNs are quite different from other graphical models. We also describe a message-passing algorithm that efficiently computes conditional cumulative distributions. Due to the unique independence properties of the CDN, these messages do not in general have a one-to-one correspondence with messages exchanged in standard algorithms, such as belief propagation. We demonstrate the application of CDNs for structured ranking learning using a previously-studied multi-player gaming dataset.}, note = {Reissued by PMLR on 09 October 2024.} }
Endnote
%0 Conference Paper %T Cumulative distribution networks and the derivative-sum-product algorithm %A Jim C. Huang %A Brendan J. Frey %B Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2008 %E David A. McAllester %E Petri Myllymäki %F pmlr-vR6-huang08a %I PMLR %P 290--297 %U https://proceedings.mlr.press/r6/huang08a.html %V R6 %X We introduce a new type of graphical model called a ’cumulative distribution network’ (CDN), which expresses a joint cumulative distribution as a product of local functions. Each local function can be viewed as providing evidence about possible orderings, or rankings, of variables. Interestingly, we find that the conditional independence properties of CDNs are quite different from other graphical models. We also describe a message-passing algorithm that efficiently computes conditional cumulative distributions. Due to the unique independence properties of the CDN, these messages do not in general have a one-to-one correspondence with messages exchanged in standard algorithms, such as belief propagation. We demonstrate the application of CDNs for structured ranking learning using a previously-studied multi-player gaming dataset. %Z Reissued by PMLR on 09 October 2024.
APA
Huang, J.C. & Frey, B.J.. (2008). Cumulative distribution networks and the derivative-sum-product algorithm. Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R6:290-297 Available from https://proceedings.mlr.press/r6/huang08a.html. Reissued by PMLR on 09 October 2024.

Related Material