Properties of the Lovász-Bregman Divergence with applications to rank aggregation and clustering

Jeff Bilmes, Rishabh Iyer
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:35-44, 2013.

Abstract

We extend the recently introduced theory of Lovász Bregman (LB) divergences [19] in several ways. We show that they represent a distortion between a “score” and an “ordering”, thus providing a new view of rank aggregation and order based clustering with interesting connections to web ranking. We show how the LB divergences have a number of properties akin to many permutation based metrics, and in fact have as special cases forms very similar to the Kendall-$\tau$ metric. We also show how the LB divergences subsume a number of commonly used ranking measures in information retrieval, like NDCG [22] and AUC [35]. Unlike the traditional permutation based metrics, however, the LB divergence naturally captures a notion of “confidence” in the orderings, thus providing a new represen- tation to applications involving aggregating scores as opposed to just orderings. We show how a number of recently used web ranking models are forms of Lovász Bregman rank aggregation and also observe that a natural form of Mallow’s model using the LB diver- gence has been used as conditional ranking models for the “Learning to Rank” problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-bilmes13a, title = {Properties of the Lovász-Bregman Divergence with applications to rank aggregation and clustering}, author = {Bilmes, Jeff and Iyer, Rishabh}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {35--44}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/bilmes13a/bilmes13a.pdf}, url = {https://proceedings.mlr.press/r11/bilmes13a.html}, abstract = {We extend the recently introduced theory of Lovász Bregman (LB) divergences [19] in several ways. We show that they represent a distortion between a “score” and an “ordering”, thus providing a new view of rank aggregation and order based clustering with interesting connections to web ranking. We show how the LB divergences have a number of properties akin to many permutation based metrics, and in fact have as special cases forms very similar to the Kendall-$\tau$ metric. We also show how the LB divergences subsume a number of commonly used ranking measures in information retrieval, like NDCG [22] and AUC [35]. Unlike the traditional permutation based metrics, however, the LB divergence naturally captures a notion of “confidence” in the orderings, thus providing a new represen- tation to applications involving aggregating scores as opposed to just orderings. We show how a number of recently used web ranking models are forms of Lovász Bregman rank aggregation and also observe that a natural form of Mallow’s model using the LB diver- gence has been used as conditional ranking models for the “Learning to Rank” problem.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Properties of the Lovász-Bregman Divergence with applications to rank aggregation and clustering %A Jeff Bilmes %A Rishabh Iyer %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-bilmes13a %I PMLR %P 35--44 %U https://proceedings.mlr.press/r11/bilmes13a.html %V R11 %X We extend the recently introduced theory of Lovász Bregman (LB) divergences [19] in several ways. We show that they represent a distortion between a “score” and an “ordering”, thus providing a new view of rank aggregation and order based clustering with interesting connections to web ranking. We show how the LB divergences have a number of properties akin to many permutation based metrics, and in fact have as special cases forms very similar to the Kendall-$\tau$ metric. We also show how the LB divergences subsume a number of commonly used ranking measures in information retrieval, like NDCG [22] and AUC [35]. Unlike the traditional permutation based metrics, however, the LB divergence naturally captures a notion of “confidence” in the orderings, thus providing a new represen- tation to applications involving aggregating scores as opposed to just orderings. We show how a number of recently used web ranking models are forms of Lovász Bregman rank aggregation and also observe that a natural form of Mallow’s model using the LB diver- gence has been used as conditional ranking models for the “Learning to Rank” problem. %Z Reissued by PMLR on 04 October 2026.
APA
Bilmes, J. & Iyer, R.. (2013). Properties of the Lovász-Bregman Divergence with applications to rank aggregation and clustering. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:35-44 Available from https://proceedings.mlr.press/r11/bilmes13a.html. Reissued by PMLR on 04 October 2026.

Related Material