Online Multi-Class Gradient Boost. × → → In addition to the training data, the OMCGB algorithm requires three different parameters as input: a fixed number M of weak learners, a loss function 4 : , and an agree- ment function a : C ℾ , which quantifies the amount of agreement between a class label prediction f (xn) and the corresponding ground truth label yn. After initialization of the weak classifiers, the algorithm loops over all training data points and updates all weak classifiers for every new training sample (xn, yn). This online behaviour of the algorithm is very attractive for our active learning framework, because it avoids a recomputation of the underlying representation whenever a new ground truth label is queried from the user and added to the existing training set. As in o ine boosting methods, every training sample xn has an assigned weight wn, which is first initialized to 1. Then, every weak classifier is first updated with the new sample, its weight wn and its ground truth label yn. Note that the weak learner itself also must be an online algorithm, because otherwise the overall boosting method would not be online. In our experiments we used online random forests as weak classifiers. The next step (line 7) is to obtain a label prediction pnm for the new training sample. Then, the agreement with the ground truth label is computed. In standard OMCGB, this is defined as nm ag(pnm, yn) = p(yn ) – 1/C, (5) i.e. it is directly related to the prediction for class yn, here denoted as an upper index into the prediction vector pnm. The resulting agreement αnm is then accumulated, and a new weight wn is computed for the sample from the negative gradient of the loss function of the sum of agreements. In [4], This means, that we measure agreement by the amount of confidence, which is equal to one minus uncertainty. In case of a correct classification, i.e. when ( = 0, the agreement simply amounts to the confidence of the current weak classifier fm. However, if the classification is incorrect, we actually have a disagreement, and we express this with the – – – slightly modified – negative confidence. Our modification is the term (C 1), by which we divide the uncertainty. This has empirically shown to improve the classification results substantially. To summarize, our agreement function is high if the classification is correct and certain, and it is low if we have an incorrect, but certain classification. Also note that if the uncertainty is zero, i.e. when we completely trust the classi...
