n-best tagging results

[usptact]

Is possible to return n the most likely predictions using CRF? If so, which place should be modified in the source code to get this behavior since I could not find any parameter that gives this.

Thank you.

[kmike]

Hey @usptact,

CRFsuite doesn't currently support n-best tagging.

It seems the relevant code is

crfsuite/lib/crf/src/crf1d_context.c

Line 466 in 5566039

floatval_t crf1dc_viterbi(crf1d_context_t* ctx, int *labels)

[usptact]

kmike,

Thank you a lot for a pointer! I read elsewhere that for Vitterbi based algorithms one needs to increase the beam size. I am not sure what it means.

[kmike]

Currently the function computes a single max_score, stores a single backward link at each j, and finds a single best label sequence using these backwads links.

If I'm not mistaken, for n-best parsing you need to keep top-n max_score values, n best backward links at each position j and use them to compute n best label sequences.

There are also more efficient algorithms for n-best decoding, see e.g. http://www.keerthis.com/P12-1064.pdf for an overview.

[kmike]

As a side not, Wapiti CRF toolkit supports n-best decoding.
Implementation is not optimal though (see Jekub/Wapiti#2).

[usptact]

Thank you very much, kmike! I am playing with Wapiti right now and trying to assess the top n-best results. Up to this moment I was always relying on the top-1 result which was not the best in all the cases. I am curios whether good tagging is in the n-best results list.