The Bregman Variational Dual-Tree Framework

Saeed Amizadeh, Bo Thiesson, Milos Hauskrecht
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:262-271, 2013.

Abstract

Graph-based methods provide a powerful tool set for many non-parametric frameworks in Machine Learning. In general, the mem- ory and computational complexity of these methods is quadratic in the number of exam- ples in the data which makes them quickly in- feasible for moderate to large scale datasets. A significant effort to find more efficient so- lutions to the problem has been made in the literature. One of the state-of-the-art methods that has been recently introduced is the Variational Dual-Tree (VDT) frame- work. Despite some of its unique features, VDT is currently restricted only to Euclidean spaces where the Euclidean distance quan- tifies the similarity. In this paper, we ex- tend the VDT framework beyond the Eu- clidean distance to more general Bregman di- vergences that include the Euclidean distance as a special case. By exploiting the properties of the general Bregman divergence, we show how the new framework can maintain all the pivotal features of the VDT framework and yet significantly improve its performance in non-Euclidean domains. We apply the pro- posed framework to different text categoriza- tion problems and demonstrate its benefits over the original VDT.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-amizadeh13a, title = {The Bregman Variational Dual-Tree Framework}, author = {Amizadeh, Saeed and Thiesson, Bo and Hauskrecht, Milos}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {262--271}, 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/amizadeh13a/amizadeh13a.pdf}, url = {https://proceedings.mlr.press/r11/amizadeh13a.html}, abstract = {Graph-based methods provide a powerful tool set for many non-parametric frameworks in Machine Learning. In general, the mem- ory and computational complexity of these methods is quadratic in the number of exam- ples in the data which makes them quickly in- feasible for moderate to large scale datasets. A significant effort to find more efficient so- lutions to the problem has been made in the literature. One of the state-of-the-art methods that has been recently introduced is the Variational Dual-Tree (VDT) frame- work. Despite some of its unique features, VDT is currently restricted only to Euclidean spaces where the Euclidean distance quan- tifies the similarity. In this paper, we ex- tend the VDT framework beyond the Eu- clidean distance to more general Bregman di- vergences that include the Euclidean distance as a special case. By exploiting the properties of the general Bregman divergence, we show how the new framework can maintain all the pivotal features of the VDT framework and yet significantly improve its performance in non-Euclidean domains. We apply the pro- posed framework to different text categoriza- tion problems and demonstrate its benefits over the original VDT.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T The Bregman Variational Dual-Tree Framework %A Saeed Amizadeh %A Bo Thiesson %A Milos Hauskrecht %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-amizadeh13a %I PMLR %P 262--271 %U https://proceedings.mlr.press/r11/amizadeh13a.html %V R11 %X Graph-based methods provide a powerful tool set for many non-parametric frameworks in Machine Learning. In general, the mem- ory and computational complexity of these methods is quadratic in the number of exam- ples in the data which makes them quickly in- feasible for moderate to large scale datasets. A significant effort to find more efficient so- lutions to the problem has been made in the literature. One of the state-of-the-art methods that has been recently introduced is the Variational Dual-Tree (VDT) frame- work. Despite some of its unique features, VDT is currently restricted only to Euclidean spaces where the Euclidean distance quan- tifies the similarity. In this paper, we ex- tend the VDT framework beyond the Eu- clidean distance to more general Bregman di- vergences that include the Euclidean distance as a special case. By exploiting the properties of the general Bregman divergence, we show how the new framework can maintain all the pivotal features of the VDT framework and yet significantly improve its performance in non-Euclidean domains. We apply the pro- posed framework to different text categoriza- tion problems and demonstrate its benefits over the original VDT. %Z Reissued by PMLR on 04 October 2026.
APA
Amizadeh, S., Thiesson, B. & Hauskrecht, M.. (2013). The Bregman Variational Dual-Tree Framework. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:262-271 Available from https://proceedings.mlr.press/r11/amizadeh13a.html. Reissued by PMLR on 04 October 2026.

Related Material