SparseMAP: Differentiable Sparse Structured Inference

Vlad Niculae, Andre Martins, Mathieu Blondel, Claire Cardie
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:3799-3808, 2018.

Abstract

Structured prediction requires searching over a combinatorial number of structures. To tackle it, we introduce SparseMAP, a new method for sparse structured inference, together with corresponding loss functions. SparseMAP inference is able to automatically select only a few global structures: it is situated between MAP inference, which picks a single structure, and marginal inference, which assigns probability mass to all structures, including implausible ones. Importantly, SparseMAP can be computed using only calls to a MAP oracle, hence it is applicable even to problems where marginal inference is intractable, such as linear assignment. Moreover, thanks to the solution sparsity, gradient backpropagation is efficient regardless of the structure. SparseMAP thus enables us to augment deep neural networks with generic and sparse structured hidden layers. Experiments in dependency parsing and natural language inference reveal competitive accuracy, improved interpretability, and the ability to capture natural language ambiguities, which is attractive for pipeline systems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-niculae18a, title = {{S}parse{MAP}: Differentiable Sparse Structured Inference}, author = {Niculae, Vlad and Martins, Andre and Blondel, Mathieu and Cardie, Claire}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {3799--3808}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/niculae18a/niculae18a.pdf}, url = {https://proceedings.mlr.press/v80/niculae18a.html}, abstract = {Structured prediction requires searching over a combinatorial number of structures. To tackle it, we introduce SparseMAP, a new method for sparse structured inference, together with corresponding loss functions. SparseMAP inference is able to automatically select only a few global structures: it is situated between MAP inference, which picks a single structure, and marginal inference, which assigns probability mass to all structures, including implausible ones. Importantly, SparseMAP can be computed using only calls to a MAP oracle, hence it is applicable even to problems where marginal inference is intractable, such as linear assignment. Moreover, thanks to the solution sparsity, gradient backpropagation is efficient regardless of the structure. SparseMAP thus enables us to augment deep neural networks with generic and sparse structured hidden layers. Experiments in dependency parsing and natural language inference reveal competitive accuracy, improved interpretability, and the ability to capture natural language ambiguities, which is attractive for pipeline systems.} }
Endnote
%0 Conference Paper %T SparseMAP: Differentiable Sparse Structured Inference %A Vlad Niculae %A Andre Martins %A Mathieu Blondel %A Claire Cardie %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-niculae18a %I PMLR %P 3799--3808 %U https://proceedings.mlr.press/v80/niculae18a.html %V 80 %X Structured prediction requires searching over a combinatorial number of structures. To tackle it, we introduce SparseMAP, a new method for sparse structured inference, together with corresponding loss functions. SparseMAP inference is able to automatically select only a few global structures: it is situated between MAP inference, which picks a single structure, and marginal inference, which assigns probability mass to all structures, including implausible ones. Importantly, SparseMAP can be computed using only calls to a MAP oracle, hence it is applicable even to problems where marginal inference is intractable, such as linear assignment. Moreover, thanks to the solution sparsity, gradient backpropagation is efficient regardless of the structure. SparseMAP thus enables us to augment deep neural networks with generic and sparse structured hidden layers. Experiments in dependency parsing and natural language inference reveal competitive accuracy, improved interpretability, and the ability to capture natural language ambiguities, which is attractive for pipeline systems.
APA
Niculae, V., Martins, A., Blondel, M. & Cardie, C.. (2018). SparseMAP: Differentiable Sparse Structured Inference. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:3799-3808 Available from https://proceedings.mlr.press/v80/niculae18a.html.

Related Material