Streaming algorithms for evaluating noisy judges on unlabeled data -- binary classification

Summary

The paper considers the problem of estimating the accuracy of noisy judges/classifiers in a streaming fashion, using only unlabeled data. Specifically, the goal is to compute the accuracy of each judge while processing items and the judge predictions for each item as part of a stream, without any associated labels for the items.

Strengths

1. The problem of evaluating noisy judges that is being explored by the paper is an interesting and important one.

Weaknesses

1. The main method presented in this paper (i.e., section 3) is not novel. For example, it can be seen as a special case of the approach presented in *Platanios, E. A., Blum A., and Mitchell T. "Estimating accuracy from unlabeled data" UAI (2014)*, which relaxes the independence assumption (though does not consider the streaming setting) and is also not cited in this paper. In fact, a lot of related work is missing including derivatives of the aforementioned paper (e.g., a direct follow-up in ICML 2016). 2. The premise of section 4 is weak. The idea that the method of section 3 is “self-alarming” because when you have dependent classifiers the accuracy estimates will be invalid is not completely correct. While this may capture some cases, there are still a lot of cases where you can have dependent classifiers, and where there exists a valid solution to the presented system of equations. Thus, I am not convinced by the main claim of this section. 3. The paper considers a streaming setting but it does not provide motivation for it. For example, it was not clear to me why we cannot store the predictions of the classifiers as items are processed in a database and then perform accuracy estimation periodically. If we have 8 classifiers and 2 possible labels, this would require 1MB per 1 million items, which does not seem expensive (and we can also perform random sampling if space becomes an issue). 4. The paper is presented in a manner that is hard to follow and could be significantly improved. I The whole paper would be presented in a simpler and more organized manner, but section 5 was particularly hard to follow without spending a significant amount of time to understand the argument that was being made. 5. The experimental evaluation is a bit lacking in that only toy datasets are being used, there is no explanation for what they are and why they are interesting, and there are very limited results being presented. Ideally, I’d like to see an “Experiments” section in the paper that describes the setup targeted at testing some hypotheses, the datasets, and the evaluation metrics, and then presents and discusses the evaluation results.

Questions

1. Regarding the majority vote estimator, I don’t understand why you need 2^n variables in your sketch. I think all you need is n+1 variables which are defined as follows: (i) the number of items that have been processed thus far, and (ii) for each classifier, the number of times its predicted label matches the majority vote label. Is my understanding correct or am I missing something? 2. I didn’t understand section 2.1 and I also disagree with the statement in lines 163-164. I can see decision being framed as inference and I am also confident that oftentimes making hard decisions as opposed to keeping soft values around (which I assume is what you are referring to as “decision”) can be helpful. Can you please elaborate and also provide some reference for this claim if I am mistaken? 3. I didn’t understand what you mean by the “principal/agent monitoring paradox”. Can you please explain what that is and also why it is a paradox?

Rating

2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

There is no discussion of limitations and potential negative social impact in this paper. One recommendation would be to try and think about what the implications could be for say voting systems, and also in situations where these methods are used to evaluate people whose income may depend on this evaluation (e.g., crowdworkers). In this case, the independence assumption being made by the paper may be too strong and yield in incorrect evaluations that could negatively and unfailrly affect the income of those people.

Summary

This paper introduces a new inferential evaluator for evaluating noisy binary classifiers on unlabeled data in a streaming manner. Specifically, compared to the evaluator based on majority votes, the new evaluator gives a more complete and reasonable modeling of the true label prevalence and each classifier’s accuracy. In addition, the property of the new evaluator is also mathematically discussed, and the relationship between error dependence and the evaluator estimate is empirically discovered through experiments.

Strengths

1. The paper addresses a significant problem in machine learning - evaluating the performance of binary classifiers on unlabeled data. 2. The proposed methods could have wide-ranging applications in various fields where machine learning is used, making the paper highly relevant. 3. The author provides mathematical proof to support the proposed methods and conducts empirical tests on several datasets. 4. The proposed generic framework that is based on algebraic geometry can cast a positive influence on evaluation methods on unlabeled data. 5. The new algebraic evaluation method bypasses the representation and OOD problems in ML.

Weaknesses

1. The paper is very hard to read and lacks the background to help the reviewer understand and improve the reading experience. Moreover, the supplement mentioned in lines 124, 171, 236, and 292 is missing from the paper. There are no detailed proofs for all the theorems. 2. The organization of the paper is confusing. The logic chain of the whole paper needs to be improved, better briefly introduce the outline and main content of each chapter at the beginning. 3. The aiming research problem needs to be explained formally in math language and to be explained clearly with intuitive explanations, better with a toy example or case study. 4. The current limitations of existing research, the proposed solutions (contributions of this paper), and the aiming experimental questions are not clearly listed, making it hard to catch the author's idea. 5. More experiments are needed. There are no experiments supporting that the performance of a majority vote-based evaluator is worse than that of the inferential one. And from the perspective of experiments, the advantage of the new evaluator is not made clear. 6. Only label prevalence is formalized in the paper, while there are no formulas for classifier accuracy. 7. The complexity of the concepts and the heavy use of mathematical proofs might affect their clarity. The author could consider providing more background information, intuitive explanations, or visual aids to improve the paper's accessibility. 8. The experiment part fails to show the superiority of the proposed method compared with other baselines. 9. The equations need to be carefully edited using formal math language. The space should be used for some meaningful and essential equations, not for simple ones such as summation or average operations. 10. Typos: In line 167, "it could have been a βitem, not an αone" should be "it could have been a β item, not an α one".

Questions

Is it possible to compare the proposed method to other baselines on the same datasets, in order to show the superiority and significance of the new method?

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

1 poor

Presentation

1 poor

Contribution

2 fair

Limitations

The paper concludes with a brief discussion of how algebraic stream evaluation can and cannot help when done for safety or economic reasons.

Summary

This paper considers the problem of evaluating noisy binary classifiers on unlabeled streaming data. It aims to estimate the prevalence of the labels and the accuracy of each classifier on them, given a data sketch of label predictions by the members of an ensemble of noisy binary classifiers. The authors propose two algebraic evaluators based on the assumption of error-independent classifiers: the first is based on an additional assumption of majority voting, and the second is fully inferential and is guaranteed to contain the true evaluation point.

Strengths

- The results of this paper seem to be well supported by the rigorous mathematical analysis as well as empirically demonstrated on three benchmark datasets.

Weaknesses

- The independence assumption may not be satisfied in practice, especially when the ensemble of classifiers consists of different models trained on the same or overlapping datasets, or even the same model but trained for different durations. - The significance of this paper is unclear. It would be better for the authors to provide some concrete real-world examples that fit the problem setting of this paper and explain the possible uses of the quantities desired to be estimated in these examples. - The proposed evaluators may be sensitive to noise or corruption in the data sketch. The solutions of the algebraic equations will change if the data sketch is not perfectly recorded, leading to mistakes in distinguishing between independent and correlated evaluations.

Questions

Please see Weaknesses.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The authors has discussed the limitations of this paper.

Summary

The paper addresses making decisions based on the outputs of three binary classifiers. More precisely, it focuses on evaluating the performances of noisy classifiers. It considers majority voting on one hand, and a proposed evaluation scheme based on the classifiers' accuracies. The paper establishes several theorems so as to demonstrate the superiority of the second (proposed) evaluation scheme. Then, experiments are conducted to test the ability of the proposal to avoid making decisions in problematic situations—e.g., correlated classifiers.

Strengths

I see no particular strength in the paper that would mitigate its flaws.

Weaknesses

The proposal suffers from several major flaws. First of all, it is badly written. The problem is not clearly stated. The mathematical objects (typically, the prevalence of the labels, and the label accuracies) are not properly introduced and defined. Some key notions (such as the "evaluation variety", the precise definition of correlated classifiers, among others) are also not defined. There are frequent references in the text to notions which have not been exposed yet (e.g., "the evaluators for binary classifiers" in the introduction, Theorems 1 and 2 in the introduction as well, Theorem 3 in Section 1.2). Besides, the paper ignores a large amount of literature. The problem addressed has connections with computational social choice (voting schemes), of which some works are mentioned. But it also relates to classifier combination (boosting, error-correcting output codes, weighted averaging, racing algorithms, etc): the problem of evaluating the performance of an ensemble has been addressed in a number of works which are ignored here. Last, but not least, the paper focuses on a very specific case—the ensemble has only three classifiers. This is very restrictive and such ensembles are hardly used in practice. Some claims are not supported—e.g., in Section 1.1, "Seemingly correct estimates are estimated values that seem to be correct because they have this real, integer ratio form. Estimates that do not have this form are obviously incorrect." This is not the case of the $F_\beta$ measure, for instance.

Questions

How would your approach compare to classifier combination techniques where classifiers are combined based on their accuracy (e.g. racing algorithms or boosting) ? How could the approach be generalized to more than 3 classifiers in the ensemble, or to multi-class classification problems ?

Rating

2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

1 poor

Contribution

1 poor

Limitations

The authors have addressed the limitations of their approach, but in my opinion only in a restricted way. They have not addressed the potential negative societal impact of their work, but I do not think that this is crucial here.

Summary

This paper considers the problem of evaluating an ensemble of binary classifiers on unlabeled data in a streaming setting. The authors first describe a baseline which treats the majority vote as the correct label and evaluate each classifier accordingly. Then they propose an evaluator based on an assumption that the classifiers are independent. The algebraic expression for this evaluator should return rational numbers if the assumption holds (as they should correspond to ratios of integer counts). Thus, this evaluator has failure modes that can be detected clearly unlike the majority-voting baseline that may return incorrect but seemingly sensible values.

Strengths

While I am not an expert in evaluation using unlabeled data and cannot speak definitively, the proposed algebraic evaluation and characterizing failure modes by algebraic failures seem creative and novel.

Weaknesses

I found the paper overall quite difficult to follow, and thus my assessment of its technical contributions may be limited. More thorough motivation and background on the problem setting (e.g. using real-world applications), as well as careful characterization of the proposed algebraic evaluator in contrast with existing approaches, would help make the paper much more approachable. I also had a hard time following most of Section 1 (especially 1.2) without the technical details in Section 3. The paper is also missing some related work discussion, and its contributions with respect to prior work is not very clear. I struggled to see the connection to the works mentioned in the first paragraph of Section 1.3. Another work that appears very relevant is [1]; how does this paper relate to their approach? Throughout the paper, only the setting with three binary classifiers is considered. A more general formulation may be helpful. As far as I can tell, this approach would scale exponentially in the number of classifiers which could limit its impact in practical settings. Empirical evaluation was limited only to analyzing the failure rates, and there were no experiments on how well the proposed approach performs as an evaluator (i.e., how close are the error rate estimates to the true error rates?). [1] Platanios, Emmanouil Antonios, Avrim Blum, and Tom Mitchell. "Estimating Accuracy from Unlabeled Data." 2014.

Questions

Please see above for the main questions and suggestions. As a minor suggestion, I think Theorem 1 would be very intuitive to see using probabilities. It involves the probability of true label being $\alpha$ and the conditional probabilities of each outcome given the true label being $\alpha$ or $\beta$; the independence assumption allows turning the probability of a joint outcome into a product of probabilities for each classifier’s outcome.

Rating

2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

1 poor

Contribution

2 fair

Limitations

Overall, yes. One limitation that was not discussed is that the approach seems to scale exponentially in the number of classifiers.

Reviewer supposed technical restrictions of the paper are not correct

The statement that this paper only applies to ensembles of three classifiers is incorrect. For one, marginalization of any group of classifiers with more than three classifiers is trivial. Given 4 classifiers, we can apply the independent solution to any 3 of them. Because two of the four major theorems in the paper concern arbitrarily correlated classifiers the assertion that we only consider independent classifiers is incorrect. In addition, we use the solution of the Groebner basis for three ARBITRARILY correlated classifiers to identify a sub-surface in the evaluation space that is universal - it applies to any ensemble of n classifiers whether they are correlated or not. It is this result that can be universally used by any other method to evaluate on unlabeled data since it reduces the uncertainty in evaluation space from 2*n+1 dimensions to n+1. There is no restriction to n=3 in that result. We just did not experimentally use anything other than 3 classifiers, that is it. Lastly, the independent solution itself is useful EVEN when the classifiers are actually correct since it has failure modes that signal high correlation between them. It acts as a check-engine light for any set of binary classifiers, correlated or not. This is a major thrust of the paper and its discussion of failure modes. To assert our results are not practical and only apply to three independent classifiers is a technically incorrect reading of the paper.

Correction to Platanios reference

Our apologies for the mispelling of Platanios' name. In addition, the reviewers are correct that it was an omission not to reference their work. In particular, Platanios earlier work where the focus is on the algebra of agreement rates. We should have included another section in the Supplement detailing the mathematical relationship between their approach and ours. The summary is that their equations for agreement rates are completely linear, thus avoiding the mathematical complexities of the quartic polynomials we considered. As one would expect, these the linear agreement equations of Platanios, carry less information than the full polynomials. One possible similarity between Platanios' agreement equations and our work could be the generating polynomials set for the (n+1) surface we identify that is universal since it involves a subset of polynomials that involve pairs of classifiers. But our equations are quadratic, still not linear as in Platanios' agreement equations. It is inevitable that any probabilistic approach, which is the route continued by Platanios, should contain algebraic constraints and equations similar to ours. What distinguishes our work is it strict adherence to only algebraic assumptions so as to pare down the assumptions necessary for empirical evaluation to a bare minimum, thus providing a different corroboration that an AI system is operating safely.

Platanios agreement equations are incorrect

As we were elaborating the similarities between our approach and Platanios' agreement equations, we discovered that the independent solution presented in his work with Tom Mitchell is mathematically incorrect. The agreement rate of independent classifiers ACROSS labels is not equal to the product of their individual error rates ACROSS labels. This is only true, INTRA label. We plan to update our supplement with an algebraic demonstration of their logical mistake as well as a numerical demonstration that the incorrect solution fails to predict the correct error rate for individual classifiers.