Multiclass classification when class distribution is known

Question

What is an example of an algorithm that, when i have a known distribution across discrete groups and I have some sort of model score that a person is in each group, assigns persons to groups such that the sum of the group scores are maximized, or some other objective criteria is met and we honor the known class distribution.

I have some code that assigns classified units to the group associated with the max score for the unit one by one until a group is "full". It starts with the highest scoring units, which creates an issue, as groups with a higher class probability in the predictions than the known end up being dominated by predictive units that generate a lot of data (e.g. long documents).

Has anyone else run into this or considered this before in classification problems?

Answer 1

Specifically, it sounds like an N-armed bandit problem. And you have a score-based allocation strategy in your code. It appears to differ a bit from the classic set up because you claim to know rather have to estimate 'arm' (class) probabilities, but I can't quite tell from the description.

As Ludo suggests, this sounds near enough to classic OR territory. The machine learning literature is also interested in this sort of problem, particularly those into adversarial or worst case online learning procedures.

I'd guess your 'issue' stems from the discrepancy between your assumed and the actual scoring function / class distribution. Or perhaps from your greedy allocation strategy. Both might be clarified by being a bit clearer about what is estimated, what is known, and what the allocation code is supposed to be doing.

In any case, this is guesswork in the absence of an example. Even a toy one would be helpful.

Answer 2

The completely other way to look at is as a situation where marginal category probabilities are known but the classification mechanism needs to be informed by them, e.g. when the training regime would not naturally reflect these probabilities and something needs to be reweighted, e.g. in a rare events design.

We'd then have two cases:

1. the known category probabilities refer to a larger population. Then some form of case weighting are needed to prevent bias. Assigned category marginals need not then exactly respect these population margins, but will be reasonably close to them if a random sample is classified. King and Zheng, 2001 is an example.

2. the known category probabilities are for the sample (i.e. the sample is the population). In this case you would seem to have what the computer scientists call a packing or knapsack problem. They tend to be hard because assigned category marginals must exactly respect the known ones. (Or perhaps there is a Lagrange approach available - I'm not familiar with this sort of thing).

Answer 3

Isn't this a problem similar to the assignment problems dealt with in operations research. You want to allocate people to groups such that (a) the sum of group scores -- according to allocation -- is maximized, but (b) while staying within the capacity limits of the groups.