Restricted set classification (RSC)

Restricted set classification (RSC)

RSC is about assigning labels to multiple objects presented together in a set. Denote the possible classes by 1, 2, ..., c. The catch is that we know that within X, there may be at most k_i objects form class i (i = 1,...,c).

Who-is-who?
Have you ever wondered how a team filming a documentary about a group of wild animals recognise each individual animal in the group? The animals are so alike that it is nearly impossible to tell them apart! An automatic classifier will likely make a lot of mistakes. But if you try to recognise the animals from a single photo, you have extra information! There can only be one of each in the group. In other words, if your classifiers returns two Georges and no Peter, you know that it is wrong. Can we improve the accuracy by taking the extra information on board? Oh, yes. (See [1])
Who-is-missing?
Now suppose that, this morning, only some of the animals are there. We need to know who is missing. Will our classifier benefit again from trying to recognise the animals in the photo? Yes, it will! (See [2])

Notice that here we still assume that we are recognising each animal as an individual.
Who-is-there?
What if we are monitoring similar species and, for a particular animal in the photo, we only need to know which species it belongs to. Say there are fish in a tank and would like to monitor the behaviour of each species. Our classifier will only need to recognise the species. But in this case we know more: there are 11 guppy, 8 tetra and 9 zebra fish (not in the photo). We are observing either all 28 fish or only a subset of them. If we classify them together, and our classifier returns 10 zebra fish, we know that something is wrong. We wouldn’t notice this error if each fish was classified independently! (See [3])

And here is an interesting application example. Viewers of live chess matches can take a snapshot of the board with their phone camera, and our restricted set classifier will recognise and position the pieces on the board. (Eh, one day, maybe. We are not ready to sell this yet.) This is the perfect example of the who-is-there task. Pieces may be missing. There are 8 pawns of each colour, two bishops, two rooks, etc. Our research verified the success of the idea of RSC. (See [4])



References