Calculating the classification threshold efficiently

I have a multi-label classification problem, in which each input sample has a set of zero or more output labels.

I have a multi-class classifier which, for every input sample, returns a certain score for each of the output labels.

One way to use this multi-class classifier for multi-label classification is to calculate a threshold score, and select for the output all labels that get a score above the threshold.

My question is: what is the most efficient way to calculate the threshold score?

Currently we use the following scheme:

• Train the multi-class classifier on 90% of the training set.
• Run the base multi-class classifier on the remaining 10% of the training set (which we call "development set"). Keep all the scores in a large array.
• Create a set of all scores that are returned by the base multi-class classifier for any input and any label. Call the set $S$.
• For every score $s \in S$, and for every input sample in the development set, calculate the positive labels returned when the threshold is $s$. Compare to the gold-standard. Calculate the precision, recall and $F1$.
• Select the score $s_max$ that yielded the maximum $F1$.

This is not efficient because there are many different scores and the method is linear in the number of different scores.

We plotted the $F1$ against the scores and noticed that this is a concave function - it has a single maximum. So, we thought of using binary search to find the maximum point. But, we are not sure that the function will always be concave.

What advice do you have for making this process more efficient?

• Is there a reason to use a single global threshold that's the same for all labels, instead of one threshold per label (if the score for that label is above the threshold for that label, then include that label in the output set)? The latter permits easier training: you are just training $n$ boolean classifiers independently, and standard methods for training boolean classifiers suffice. – D.W. Dec 4 '13 at 18:17
• @D.W. That is interesting. Do you know of any studies that compared these different threshold calculation methods? – Erel Segal-Halevi Dec 8 '13 at 13:11
• Erel, alas, I do not. Using a separate boolean classifier per label is a standard technique for building a multi-label classifier, though (e.g., building a multi-label classifier out of SVMs, which are inherently boolean). If after a few days you still don't get any useful answers, it's possible you might have a better chance of getting a good answer if you flag your question and ask the moderators to migrate it to Statistics.SE. – D.W. Dec 8 '13 at 19:57