📄 Dynamic n-best Selection and Its Application in Dialog Act Detection

Summary

Dialog system modules usually hand the next stage an n-best list of fixed length, even though the right number of candidates changes from input to input. Hu, Morbini, Weng and Liu propose n*-best: sort a classifier's output probabilities in descending order and cut the list where the gap between two neighbouring probabilities is largest. They argue that this cutoff approximates the point of maximal negative curvature of the cumulative probability curve, though the proof is omitted. The method is tested on a dialog-act classifier that uses parse-tree features. A downstream decision step either accepts the classifier's result or replies "I don't understand" and stores the utterance for later retraining, which the authors frame as active learning. Rather than error rate, they evaluate with ROC curves and ROC area, which capture the balance between wrong answers and needless rejections. On two hand-labelled datasets, n*-best had the largest ROC area of all methods, beating every fixed n from 1 to 6. The work matters because it gives a simple, principled way to size candidate lists for any module that produces n-best output.

Key points

• Selection rule: n* = argmax over n of (p_n − p_{n+1}), applied to probabilities sorted from highest to lowest. The cumulative probability curve is then concave, and the rule is claimed to match maximizing −P”(n+1) as the number of classes grows.
• Data: two hand-labelled sets of 1178 and 471 user utterances covering 30 possible dialog acts. A single utterance may carry several acts, for example Query:restaurant, Answer and Revision.
• Two setups were tested: Case 1 trains on a large set and tests on a small one, and Case 2 does the reverse. All ROC curves in Case 2 sit closer to the no-discrimination line.
• Baselines were fixed n = 1…6. The confidence threshold h was swept from 0.1 to 1 in steps of 0.05 to trace each ROC curve.
• n*-best gave better ROC curves in most scenarios and the largest ROC area in both cases.

Interesting ideas

• I1. Instead of a fixed top-k, keep candidates down to the steepest fall in the sorted probabilities, so confident inputs yield one answer and ambiguous ones yield several.
• I2. When the system is unsure, it should decline to answer and save the input as training material, turning abstention into a source of new labels in the spirit of active learning.
• I3. Sweep the acceptance threshold and compare methods by ROC area rather than raw error rate, so the cost of false answers and the cost of over-rejection are both visible.
• I4. Treat an utterance as carrying a set of speech acts rather than exactly one, and let the classifier return as many as the probability profile supports.
• I5. Check a method under two opposite data regimes, plenty of training data versus scarce training data, to show that its advantage is not an artefact of one split.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

• I1 (tokens): the tagger and lemmatizer could pass along a variable-size set of POS or lemma readings, cut at the largest drop, so later stages see real ambiguity only where it exists.
• I2 (learn): sentences where the confidence gap is weak could be routed automatically to the LLM teacher tiers or witness-parser voting, instead of being silently guessed.
• I3 (learn): evaluation of abstaining readers or repair rules could report ROC area across thresholds, making the trade-off explicit next to negative controls.
• I4 (frames): the speech-act layer in prag could output multiple acts per utterance (e.g., answer plus revision), with the max-drop rule deciding how many to keep.
• I5 (learn): new parser or tagger tweaks could be evaluated both with full silver data and with a deliberately small training slice before being adopted.