Learning Maximum Margin Markov Networks from examples with missing labels

Vojtech Franc, Andrii Yermakov
Proceedings of The 13th Asian Conference on Machine Learning, PMLR 157:1691-1706, 2021.

Abstract

Structured output classifiers based on the framework of Markov Networks provide a transparent way to model statistical dependencies between output labels. The Markov Network (MN) classifier can be efficiently learned by the maximum margin method, which however requires expensive completely annotated examples. We extend the maximum margin algorithm for learning of unrestricted MN classifiers from examples with partially missing annotation of labels. The proposed algorithm translates learning into minimization of a novel loss function which is convex, has a clear connection with the supervised margin-rescaling loss, and can be efficiently optimized by first-order methods. We demonstrate the efficacy of the proposed algorithm on a challenging structured output classification problem where it beats deep neural network models trained from a much higher number of completely annotated examples, while the proposed method used only partial annotations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v157-franc21a, title = {Learning Maximum Margin Markov Networks from examples with missing labels}, author = {Franc, Vojtech and Yermakov, Andrii}, booktitle = {Proceedings of The 13th Asian Conference on Machine Learning}, pages = {1691--1706}, year = {2021}, editor = {Balasubramanian, Vineeth N. and Tsang, Ivor}, volume = {157}, series = {Proceedings of Machine Learning Research}, month = {17--19 Nov}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v157/franc21a/franc21a.pdf}, url = {https://proceedings.mlr.press/v157/franc21a.html}, abstract = {Structured output classifiers based on the framework of Markov Networks provide a transparent way to model statistical dependencies between output labels. The Markov Network (MN) classifier can be efficiently learned by the maximum margin method, which however requires expensive completely annotated examples. We extend the maximum margin algorithm for learning of unrestricted MN classifiers from examples with partially missing annotation of labels. The proposed algorithm translates learning into minimization of a novel loss function which is convex, has a clear connection with the supervised margin-rescaling loss, and can be efficiently optimized by first-order methods. We demonstrate the efficacy of the proposed algorithm on a challenging structured output classification problem where it beats deep neural network models trained from a much higher number of completely annotated examples, while the proposed method used only partial annotations.} }
Endnote
%0 Conference Paper %T Learning Maximum Margin Markov Networks from examples with missing labels %A Vojtech Franc %A Andrii Yermakov %B Proceedings of The 13th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Vineeth N. Balasubramanian %E Ivor Tsang %F pmlr-v157-franc21a %I PMLR %P 1691--1706 %U https://proceedings.mlr.press/v157/franc21a.html %V 157 %X Structured output classifiers based on the framework of Markov Networks provide a transparent way to model statistical dependencies between output labels. The Markov Network (MN) classifier can be efficiently learned by the maximum margin method, which however requires expensive completely annotated examples. We extend the maximum margin algorithm for learning of unrestricted MN classifiers from examples with partially missing annotation of labels. The proposed algorithm translates learning into minimization of a novel loss function which is convex, has a clear connection with the supervised margin-rescaling loss, and can be efficiently optimized by first-order methods. We demonstrate the efficacy of the proposed algorithm on a challenging structured output classification problem where it beats deep neural network models trained from a much higher number of completely annotated examples, while the proposed method used only partial annotations.
APA
Franc, V. & Yermakov, A.. (2021). Learning Maximum Margin Markov Networks from examples with missing labels. Proceedings of The 13th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 157:1691-1706 Available from https://proceedings.mlr.press/v157/franc21a.html.

Related Material