Tighter bounds lead to improved classifiers
The standard approach to supervised classification involves the minimization of a log-loss as an upper bound to the classification error. While this is a tight bound early on in the optimization, it overemphasizes the influence of incorrectly classified examples far from the decision boundary. Updating the upper bound during the optimization leads to improved classification rates while transforming the learning into a sequence of minimization problems. In addition, in the context where the classifier is part of a larger system, this modification makes it possible to link the performance of the classifier to that of the whole system, allowing the seamless introduction of external constraints.
The paper proposes new bounds on the misclassification error. The bounds lead to training classifiers with an adaptive loss function, and the algorithm operates in successive steps: the parameters are trained by minimizing the log-loss weighted by the probability of the observed class as given by the parameters of the previous steps. The bound improves on standard log-likelihood when outliers/underfitting prevents the learning algorithm to properly optimize the true classification error. Experiments are performed to confirm the therotical intuition and motivation. They show different cases where the new algorithm leads to improved classification error because underfitting occurs when using standard log-loss, and other cases where the new bounds do not lead to any improvement because the log-loss is sufficient to fit the dataset. The paper also discusses the relationship between the proposed idea and reinforcement learning, as well as with classifiers that have an *uncertain* label. While the paper is easy to read and well-written overall, in a second read I found it difficult to fully understand because two problems are somewhat mixed together (here considering only binary classification for simplicity): (a) the optimization of the classification error of a *randomized* classifier, which predicts 1 with probability P(1|x, theta), and (b) the optimization of the deterministic classifier, which predicts sign(P(1|x, theta) - 0.5), in a way that is robust to outliers/underfitting. The reason why I am confused is that *The standard approach to supervised classification*, as is mentioned in the abstract, is to use deterministic classifiers at test time, and the log-loss (up to constants) is an upper bound on the classification error of the deterministic classifier. However, the bounds discussed in the paper only concern the randomized classifier. === question: In the experiments, what kind of classifier is used? The randomized one (as would the sentence in the first page suggest *Assuming the class is chosen according to p(y|X, ?)*), or the more standard deterministic classifier argmax_y P(y|x, theta) ? As far as I can see, there are two cases: either (i) the paper deals with learning randomized classifiers, in which case it should compare the performances with the deterministic counterparts that people use in practice, or (ii) the paper makes sense as soon as we accept that the optimization of criterion (a) is a good surrogate for (b). In both cases, I think the write-up should be made clearer (because in case (ii) the algorithm does not minimize an upper bound on the classification error, and in case (i) what is done does not correspond to what is usually done in binary classification). === comments: - The section *allowing uncertainty in the decision* may be improved by adding some references, e.g. Bartlett & Wegkamp (2008) *Classification with a Reject Option using a Hinge Loss* or Sayedi et al. (2010) *Trading off Mistakes and Don’t Know Predictions*. - there seems to be a *-* sign missing in the P(1|x, theta) in L(theta, lambda) in Section 3. - The idea presented in the paper is interesting and original. While I give a relatively low score for now, I am willing to increase this score if the clarifications are made. Final comments: I think the paper is clear enough in its current form, even though there should still be improvement in the justification of why and to what extent the error of the randomized classifier is a good surrogate for the error of the true classifier. While the *smoothed* version of the 0/1 loss is an acceptable explanation in the standard classification setup, it is less clear in the section dealing with an additional *uncertain* label. I increase my score from 5 to 6.
You are a member of the scientific community tasked with peer review. Review the following paper title and abstract.
### Title + Abstract
Tighter bounds lead to improved classifiers
The standard approach to supervised classification involves the minimization of a log-loss as an upper bound to the classification error. While this is a tight bound early on in the optimization, it overemphasizes the influence of incorrectly classified examples far from the decision boundary. Updating the upper bound during the optimization leads to improved classification rates while transforming the learning into a sequence of minimization problems. In addition, in the context where the classifier is part of a larger system, this modification makes it possible to link the performance of the classifier to that of the whole system, allowing the seamless introduction of external constraints.
user
<think>Okay, to do a decent peer review, I should start with summarizing what the work is about. This includes novelty, contributions, clarity, and impact. I might include suggestions to issues that I find critical to the usefulness of the work. Starting with novelty, there are different types of novelty. The first aspect of novelty is scope and scale. Is the work covering a broader perspective than previous works? The second aspect is methodology. Is the proposed methodology novel compared to previous methods? Do they provide any significant advantage over previous methodologies? The third aspect is results. Are the results different compared previous work? Does this lead to any novel theories or an extension of current theories? Next is clarity, I will be reading the work in depth and analyze if any sentences can be potentially ambiguous or misleading. If any sentences are ambiguous, I will state them and give a suggestion on how to rephrase such sentence or how to make more clear to the audience. Lastly, impact is important. I will attempt to predict how such work will impact the scientific community. This might include the applications of such work and how the work might transform the way we study a certain topic. Finally, I will might only mention issues that are critical. This is to keep the review as concise and helpful as possible.</think>



The paper proposes new bounds on the misclassification error. The bounds lead to training classifiers with an adaptive loss function, and the algorithm operates in successive steps: the parameters are trained by minimizing the log-loss weighted by the probability of the observed class as given by the parameters of the previous steps. The bound improves on standard log-likelihood when outliers/underfitting prevents the learning algorithm to properly optimize the true classification error. Experiments are performed to confirm the therotical intuition and motivation. They show different cases where the new algorithm leads to improved classification error because underfitting occurs when using standard log-loss, and other cases where the new bounds do not lead to any improvement because the log-loss is sufficient to fit the dataset. The paper also discusses the relationship between the proposed idea and reinforcement learning, as well as with classifiers that have an *uncertain* label. While the paper is easy to read and well-written overall, in a second read I found it difficult to fully understand because two problems are somewhat mixed together (here considering only binary classification for simplicity): (a) the optimization of the classification error of a *randomized* classifier, which predicts 1 with probability P(1|x, theta), and (b) the optimization of the deterministic classifier, which predicts sign(P(1|x, theta) - 0.5), in a way that is robust to outliers/underfitting. The reason why I am confused is that *The standard approach to supervised classification*, as is mentioned in the abstract, is to use deterministic classifiers at test time, and the log-loss (up to constants) is an upper bound on the classification error of the deterministic classifier. However, the bounds discussed in the paper only concern the randomized classifier. === question: In the experiments, what kind of classifier is used? The randomized one (as would the sentence in the first page suggest *Assuming the class is chosen according to p(y|X, ?)*), or the more standard deterministic classifier argmax_y P(y|x, theta) ? As far as I can see, there are two cases: either (i) the paper deals with learning randomized classifiers, in which case it should compare the performances with the deterministic counterparts that people use in practice, or (ii) the paper makes sense as soon as we accept that the optimization of criterion (a) is a good surrogate for (b). In both cases, I think the write-up should be made clearer (because in case (ii) the algorithm does not minimize an upper bound on the classification error, and in case (i) what is done does not correspond to what is usually done in binary classification). === comments: - The section *allowing uncertainty in the decision* may be improved by adding some references, e.g. Bartlett & Wegkamp (2008) *Classification with a Reject Option using a Hinge Loss* or Sayedi et al. (2010) *Trading off Mistakes and Don’t Know Predictions*. - there seems to be a *-* sign missing in the P(1|x, theta) in L(theta, lambda) in Section 3. - The idea presented in the paper is interesting and original. While I give a relatively low score for now, I am willing to increase this score if the clarifications are made. Final comments: I think the paper is clear enough in its current form, even though there should still be improvement in the justification of why and to what extent the error of the randomized classifier is a good surrogate for the error of the true classifier. While the *smoothed* version of the 0/1 loss is an acceptable explanation in the standard classification setup, it is less clear in the section dealing with an additional *uncertain* label. I increase my score from 5 to 6.
assistant
The paper proposes new bounds on the misclassification error. The bounds lead to training classifiers with an adaptive loss function, and the algorithm operates in successive steps: the parameters are trained by minimizing the log-loss weighted by the probability of the observed class as given by the parameters of the previous steps. The bound improves on standard log-likelihood when outliers/underfitting prevents the learning algorithm to properly optimize the true classification error. Experiments are performed to confirm the therotical intuition and motivation. They show different cases where the new algorithm leads to improved classification error because underfitting occurs when using standard log-loss, and other cases where the new bounds do not lead to any improvement because the log-loss is sufficient to fit the dataset. The paper also discusses the relationship between the proposed idea and reinforcement learning, as well as with classifiers that have an *uncertain* label. While the paper is easy to read and well-written overall, in a second read I found it difficult to fully understand because two problems are somewhat mixed together (here considering only binary classification for simplicity): (a) the optimization of the classification error of a *randomized* classifier, which predicts 1 with probability P(1|x, theta), and (b) the optimization of the deterministic classifier, which predicts sign(P(1|x, theta) - 0.5), in a way that is robust to outliers/underfitting. The reason why I am confused is that *The standard approach to supervised classification*, as is mentioned in the abstract, is to use deterministic classifiers at test time, and the log-loss (up to constants) is an upper bound on the classification error of the deterministic classifier. However, the bounds discussed in the paper only concern the randomized classifier. === question: In the experiments, what kind of classifier is used? The randomized one (as would the sentence in the first page suggest *Assuming the class is chosen according to p(y|X, ? )*), or the more standard deterministic classifier argmax_y P(y|x, theta) ? As far as I can see, there are two cases: either (i) the paper deals with learning randomized classifiers, in which case it should compare the performances with the deterministic counterparts that people use in practice, or (ii) the paper makes sense as soon as we accept that the optimization of criterion (a) is a good surrogate for (b). In both cases, I think the write-up should be made clearer (because in case (ii) the algorithm does not minimize an upper bound on the classification error, and in case (i) what is done does not correspond to what is usually done in binary classification). === comments: - The section *allowing uncertainty in the decision* may be improved by adding some references, e.g. Bartlett & Wegkamp (2008) *Classification with a Reject Option using a Hinge Loss* or Sayedi et al. (2010) *Trading off Mistakes and Don’t Know Predictions*. - there seems to be a *-* sign missing in the P(1|x, theta) in L(theta, lambda) in Section 3. - The idea presented in the paper is interesting and original. While I give a relatively low score for now, I am willing to increase this score if the clarifications are made. Final comments: I think the paper is clear enough in its current form, even though there should still be improvement in the justification of why and to what extent the error of the randomized classifier is a good surrogate for the error of the true classifier. While the *smoothed* version of the 0/1 loss is an acceptable explanation in the standard classification setup, it is less clear in the section dealing with an additional *uncertain* label. I increase my score from 5 to 6.