Consistency of weighted majority votes
We revisit from a statistical learning perspective the classical decision-theoretic problem of weighted expert voting. In particular, we examine the consistency (both asymptotic and finitary) of the optimal Nitzan-Paroush weighted majority and related rules. In the case of known expert competence levels, we give sharp error estimates for the optimal rule. When the competence levels are unknown, they must be empirically estimated. We provide frequentist and Bayesian analyses for this situation. Some of our proof techniques are non-standard and may be of independent interest. The bounds we derive are nearly optimal, and several challenging open problems are posed.
This paper analyzes the Nitzan-Paroush strategy for assigning weights to conditionally (on the outcome) independent experts, which is optimal in expectation. The authors provide exponential concentration inequalities (both upper and lower bounds on probabilities) for the error of this optimal rule. The upper bounds are sharp and derived based on the Kearns-Saul inequality. They continue to analyze the situation where the quality of the experts is not given and must be estimated from data, giving frequentist procedures (which are analyzed) and Bayesian procedures (which are not analyzed). QUALITYThe results are interesting,  nontrivial and appear correct, as far as I checked. I was struck with the use of the Kearns-Saul inequality, which (although I have seen it before and know it was designed for other goals) seems almost magically suitable for application in this problem. The exponential bound Theorem 1(i) is quite strong, being linear in the nr of experts who are correct with probability > 1/2 + epsilon, for fixed epsilon > 0. I do have some questions/small issues about the estimators, both the frequentist and the Bayesian ones. First, as a very minor point, I'd rather call 'adaptive' 'fully empirical'  and 'nonadaptive' 'oracle' by the way, that seems to more correctly describe the difference.Second:Theorem 7: adaptive, high-confidence, frequentist case: This theorem is only useful if the authors can show that the event R will hold with large probability for sufficiently large sample sizes. (Otherwise it may be that we always have to refrain from making a high-confidence decision, making the results useless).The authors should say some more about the sample sizes when we can expect R to hold, given the (oracle, nonadaptive) probabilities(so that 'if we are lucky about the real probabilities, then with high probability we get a situation in which the adaptive bound is useful') About the Bayesian method: this seems to be based on using the standard, unconditional Naive Bayes model in which the experts opinions are viewed as X-data and the outcome as Y. But I guess that most Bayesians would condition on the X's and use conditional likelihood - and then Naive Bayes becomes logistic regression, which often works better anyway. The authors should say something about this additional possibility. Is there any reason why they have not considered it? Why naive Bayes and not logistic regression approach?CLARITYThe paper is quite well-written; I am not an expert in the probabilistic weighted-majority analysis but had no trouble following the paper. ORIGINALITYThe results are somewhat original, the *proof techniques* are very original.  SIGNIFICANCEReasonably high, esp. given the use of the Kearns-Saul inequality.