I'm familiar with using tools like SVMs and decision trees for discrete classification problems. But one detail that I have not encountered in that domain is: what do you do if your classifier must conserve some quantity when it is predicting outcomes for new input data?

For example, suppose that you took all teams in the NFL and broke them into quintiles (20% buckets) based on their rushing yards per game (or say you took teams from the EPL and broke them down into quintiles based on their time-of-possession or some other statistic). Further let's say you are doing this on a weekly basis, so every week you collect your stats and then rank the teams 1 to N, chop them into quintiles, and each team's "class label" is its quintile.

Now let's say you build a bunch of features for each team that you think will predict the team's quintile for next week. It could be the team's historical quintile, coaching changes, injuries to key players, whatever. But the point is you can make a feature vector for each team and you want to train a classifier that will predict which class label (1 to 5) to assign based on the features.

What are some common or empirically effective ways to constrain the classifier so that the output makes sense? That is to say, it should only be possible to classify 20% of the teams in any particular quintile, and the classifier should not be able to logically contradict itself by putting more teams in a quintile than 20% of the total. (That is, the theory behind the classifier ought to demonstrate how we can know in advance that the classifier won't make contradictions).

I'm not looking for post-hoc hacky ways to do rounding or anything, and I am also specifically trying to avoid the situation where you build a regression model of the underlying continuous quantity and then just predict the quantity and manually assign quintiles yourself. I want the classifier to discretely choose quintiles for each feature vector while respecting external constraints on the class labels.

More generically you could wonder, how do you train an SVM-like classifier such that it has internal rules like "Only M of the N objects can receive label L, and I need to take that into account all the time for every other label that I assign too..."

Some thoughts:

(1) Use something like simulated annealing to shuffle the boundary points for the quintile after prediction. That is, use the trained classifier to classify every team's quintile. Use the distance from the margin as the "energy function" to be minimized, and then start randomly shuffling members of over-populated quintiles to nearby under-populated quintiles. You either accept or reject such a shuffling based on the extent to which it worsens the overall distance from the margin.

I don't like this solution because it probably would be computationally inefficient after you already solve the SVM optimization problem. Also, it feels like you're actually just using the margin distance as a continuous quantity to determine the classification, at which point you might as well try to derive a more model-driven or physically plausible continuous quantity and just do regression or something and chop the predicted output into quintiles at the end, which is something I wanted to avoid.

  • $\begingroup$ Estimating a Markovian transition matrix? $\endgroup$ – DWin Aug 23 '13 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.