Learning Max-margin Tree Predictors

Ofer Meshi, Elad Eban, Gal Elidan, Amir Globerson
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:520-529, 2013.

Abstract

Structured prediction is a powerful frame- work for coping with joint prediction of interacting outputs. A central difficulty in using this framework is that often the correct label dependence structure is unknown. At the same time, we would like to avoid an overly complex structure that will lead to intractable prediction. In this work we ad- dress the challenge of learning tree structured predictive models that achieve high accuracy while at the same time facilitate efficient (linear time) inference. We start by proving that this task is in general NP-hard, and then suggest an approximate alternative. Our CRANK approach relies on a novel Circuit- RANK regularizer that penalizes non-tree structures and can be optimized using a convex-concave procedure. We demonstrate the effectiveness of our approach on several domains and show that its accuracy matches that of fully connected models, while per- forming prediction substantially faster.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-meshi13a, title = {Learning Max-margin Tree Predictors}, author = {Meshi, Ofer and Eban, Elad and Elidan, Gal and Globerson, Amir}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {520--529}, 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/meshi13a/meshi13a.pdf}, url = {https://proceedings.mlr.press/r11/meshi13a.html}, abstract = {Structured prediction is a powerful frame- work for coping with joint prediction of interacting outputs. A central difficulty in using this framework is that often the correct label dependence structure is unknown. At the same time, we would like to avoid an overly complex structure that will lead to intractable prediction. In this work we ad- dress the challenge of learning tree structured predictive models that achieve high accuracy while at the same time facilitate efficient (linear time) inference. We start by proving that this task is in general NP-hard, and then suggest an approximate alternative. Our CRANK approach relies on a novel Circuit- RANK regularizer that penalizes non-tree structures and can be optimized using a convex-concave procedure. We demonstrate the effectiveness of our approach on several domains and show that its accuracy matches that of fully connected models, while per- forming prediction substantially faster.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Learning Max-margin Tree Predictors %A Ofer Meshi %A Elad Eban %A Gal Elidan %A Amir Globerson %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-meshi13a %I PMLR %P 520--529 %U https://proceedings.mlr.press/r11/meshi13a.html %V R11 %X Structured prediction is a powerful frame- work for coping with joint prediction of interacting outputs. A central difficulty in using this framework is that often the correct label dependence structure is unknown. At the same time, we would like to avoid an overly complex structure that will lead to intractable prediction. In this work we ad- dress the challenge of learning tree structured predictive models that achieve high accuracy while at the same time facilitate efficient (linear time) inference. We start by proving that this task is in general NP-hard, and then suggest an approximate alternative. Our CRANK approach relies on a novel Circuit- RANK regularizer that penalizes non-tree structures and can be optimized using a convex-concave procedure. We demonstrate the effectiveness of our approach on several domains and show that its accuracy matches that of fully connected models, while per- forming prediction substantially faster. %Z Reissued by PMLR on 04 October 2026.
APA
Meshi, O., Eban, E., Elidan, G. & Globerson, A.. (2013). Learning Max-margin Tree Predictors. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:520-529 Available from https://proceedings.mlr.press/r11/meshi13a.html. Reissued by PMLR on 04 October 2026.

Related Material