1993 · 132 citations · 34 references
ManagementKnowledge ManagementDecision Support SystemsExpertise ManagementKnowledge CaptureCitation PracticesExpertise ProfilingKnowledge ElicitationAdvice TakingExpert ProfilingReliance On Expert Advice
The paper studies algorithms that combine predictions from multiple experts to forecast a binary outcome. The analysis considers worst‑case bit sequences, evaluating algorithms by the expected excess mistakes over the best expert, and compares this to a log‑loss framework. They prove that the excess mistake rate can be bounded by a constant times the square root of the best expert’s mistakes, provide efficient algorithms attaining this bound, and show that the results yield pattern‑recognition methods with superior guarantees.
We analyze algorithms that predict a binary value by combining the predictions of several prediction strategies, called experts . Our analysis is for worst-case situations, i.e., we make no assumptions about the way the sequence of bits to be predicted is generated. We measure the performance of the algorithm by the difference between the expected number of mistakes it makes on the bit sequence and the expected number of mistakes made by the best expert on this sequence, where the expectation is taken with respect to the randomization in the predictins. We show that the minimum achievable difference is on the order of the square root of the number of mistakes of the best expert, and we give efficient algorithms that achieve this. Our upper and lower bounds have matching leading constants in most cases. We then show how this leads to certain kinds of pattern recognition/learning algorithms with performance bounds that improve on the best results currently know in this context. We also compare our analysis to the case in which log loss is used instead of the expected number of mistakes.
34
Modeling by shortest data description
J. Rissanen · Automatica · 1978 · 6K citations
Leslie G. Valiant · 1984 · 4.2K citations
The Weighted Majority Algorithm
N. Littlestone, Manfred K. Warmuth · Information and Computation · 1994 · 2K citations
Learnability and the Vapnik-Chervonenkis dimension
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler et al. · Journal of the ACM · 1989 · 1.9K citations · Full text
The Asymptotic Theory of Extreme Order Statistics
John E. Angus, János Galambos · Technometrics · 1990 · 1.8K citations