Predicting {0,1}-Functions on Randomly Drawn Points (Extended Abstract)
David H. Haussler, Nick Littlestone, Manfred K. Warmuth · Foundations of Computer Science · 1988
Summary. We consider the problem of predicting (0,l)valued functions on R and smaller domains, based on their values on randomly drawn points. Our model is related to Valiant's learnability model, but does not require the hypotheses used for prediction to be represented in any specified form. First we disregard computational complexity and show how to construct prediction strategies that are optimal to within a constant factor for any reasonable class F of target functions. These prediction strategies use the 1-inclusion graph structure bom Non. Haussler and Welzl's work on geometric range queries to minimize the probability of incorrect prediction. We then turn to computationally efficient algorithms. For indicator functions of axis-parallel rectangles and halfspaces in R , we demonstrate how our techniques can be applied to construct computationally efficient prediction stxategies that are optimal to within a constant factor. Finally. we compare the general performance of prediction strategies derived by OUT method to those derived from existing methods in Valiant's learnability theory.