This post is about an open problem in learning reductions.<\/p>\n
Background<\/strong> A reduction might transform a a multiclass prediction problem where there are k<\/em> possible labels into a binary learning problem where there are only 2 possible labels. On this induced binary problem we might learn a binary classifier with some error rate e<\/em>. After subtracting the minimum possible (Bayes) error rate b<\/em>, we get a regret r = e – b<\/em>. The PECOC<\/a>(Probabilistic Error Correcting Output Code) reduction has the property that binary regret r<\/em> implies multiclass regret at most 4r0.5<\/sup><\/em>.<\/p>\n The problem<\/strong> This is not the “rightest” answer. Consider the k=2<\/em> case, where we reduce binary to binary. There exists a reduction (the identity) with the property that regret r<\/em> implies regret r<\/em>. This is substantially superior to the transform given by the PECOC reduction, which suggests that a better reduction may exist for general k<\/em>. For example, we can not rule out the possibility that a reduction R<\/em> exists with regret transform guaranteeing binary regret r<\/em> implies at most multiclass regret c(k) r<\/em> where c(k)<\/em> is a k<\/em> dependent constant between 1 and 4.<\/p>\n Difficulty<\/strong> I believe this is a solvable problem, given some serious thought.<\/p>\n Impact<\/strong> The use of some reduction from multiclass to binary is common practice, so a good solution could be widely useful. One thing to be aware of is that there is a common and reasonable concern about the ‘naturalness’ of induced problems. There seems to be no way to address this concern other than via empirical testing. On the theoretical side, a better reduction may help us understand whether classification or l2<\/sub><\/em> regression is the more natural primitive for reduction. The PECOC reduction essentially first turns a binary classifier into an l2<\/sub><\/em> regressor and then uses the regressor repeatedly to make multiclass predictions.<\/p>\n Some background material which may help:<\/p>\n This post is about an open problem in learning reductions. Background A reduction might transform a a multiclass prediction problem where there are k possible labels into a binary learning problem where there are only 2 possible labels. On this induced binary problem we might learn a binary classifier with some error rate e. After … <\/p>\n\n