On Weak LearningUniversity of California, Santa Cruz, Computer Research Laboratory, 1992 - 37 Seiten Abstract: "An algorithm is a weak learning algorithm if with some small probability it outputs a hypothesis with error slightly below 50%. This paper presents relationships between weak learning, weak prediction (where the probability of being correct is slightly larger than 50%), and consistency oracles (which decide whether or not a given set of examples is consistent with a concept in the class). Our main result is a simple polynomial prediction algorithm which makes only a single query to a consistency oracle and whose predictions have a polynomial edge over random guessing. We compare this prediction algorithm with several of the standard prediction techniques, deriving an improved worst case bound on Gibbs Algorithm in the process. We use our algorithm to show that a concept class is polynomially learnable if and only if there is a polynomial probabilistic consistency oracle for the class. Since strong learning algorithms can be built from weak learning algorithms, our results also characterizes [sic] strong learnability." |
Häufige Begriffe und Wortgruppen
1-inclusion graph algorithm for F Algorithm Q Algorithms Gibbs answers yes bitstrings class F Computer concept class Corollary 6.6 denote domain EyeU(x f(xt ƒ E F Haussler Hn,s hypercube hypothesis class hypothesis h hypothesis output Inequality last instance Lemma lg VP lookahead algorithm Lookahead Conversion Lookahead Prediction Algorithm M(Gibbs Manfred K maxdensƑ(x number of mistakes Occam-style algorithm one-sided consistency oracle oracle answers oracle for F outputs a hypothesis p₁(n parameterized parameters pi(n polynomial probabilistic consistency polynomial restricted data polynomial weak learning polynomial weak prediction polynomially evaluatable probabilistic consistency oracle Proof Query Lookahead Prediction random bits random number randomized algorithm restricted data interpolator samƒ(x<m sample samƒ(x Section strong learning algorithm subgraph targets ƒ Theorem 9.3 total bit length Un Xn uniform distribution upper bound VC dimension volume prediction algorithm VP samf(x VP(S weak learning algorithm weak Occam algorithm weak prediction algorithm