Boosting for Bounding the Worst-class Error

This paper tackles the problem of the worstclass error rate, instead of the standard error rate averaged over all classes. For example, a three-class classification task with class-wise error rates of 10%, 10%, and 40% has a worst-class error rate of 40%, whereas the average is 20% under the class-balanced condition. The worst-class error is important in many applications. For example, in a medical image classification task, it would not be acceptable for the malignant tumor class to have a 40% error rate, while the benign and healthy classes have 10% error rates. We propose a boosting algorithm that guarantees an upper bound of the worst-class training error Figure 1: A toy example showing the average error and derive its generalization bound. Experimental minimization results in the case of a high worst-class results show that the algorithm lowers error. Note that all five classes have the same number worst-class test error rates while avoiding of instances, and thus, there is no class imbalance.