k-Best Max-margin Approaches for Sequence Labeling

Dejan Mančev1 and Branimir Todorović1

  1. Faculty of Science and Mathematics, University of Niš
    Višegradska 33, 18000 Niš, Serbia
    dejan.mancev@pmf.edu.rs, braminirtodorovic@yahoo.com


Structured learning algorithms usually require inference during the training procedure. Due to their exponential size of output space, the parameter update is performed only on a relatively small collection built from the “best” structures. The k-best MIRA is an example of an online algorithm which seeks optimal parameters by making updates on k structures with the highest score at a time. Following the idea of using k-best structures during the learning process, in this paper we introduce four new k-best extensions of max-margin structured algorithms. We discuss their properties and connection, and evaluate all algorithms on two sequence labeling problems, the shallow parsing and named entity recognition. The experiments show how the proposed algorithms are affected by the changes of k in terms of the F-measure and computational time, and that the proposed algorithms can improve results in comparison to the single best case. Moreover, the restriction to the single best case produces a comparison of the existing algorithms.

Key words

structured learning, sequence labeling, k-best approach, max-margin training

Digital Object Identifier (DOI)


Publication information

Volume 12, Issue 2 (June 2015)
Year of Publication: 2015
ISSN: 1820-0214 (Print) 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Mančev, D., Todorović, B.: k-Best Max-margin Approaches for Sequence Labeling. Computer Science and Information Systems, Vol. 12, No. 2, 465-486. (2015)