An official website of the United States government
Boosting is a celebrated machine learning approach which is based on the idea of combining weak and moderately inaccurate hypotheses to a strong and accurate one. We study boosting under the assumption that the weak hypotheses belong to a class of bounded capacity. This assumption is inspired by the common convention that weak hypotheses are “rules-of-thumbs” from an “easy-to-learn class”. (Schapire and Freund ’12, Shalev-Shwartz and Ben-David ’14.) Formally, we assume the class of weak hypotheses has a bounded VC dimension. We focus on two main questions: (i) Oracle Complexity: How many weak hypotheses are needed in order to produce an accurate hypothesis? We design a novel boosting algorithm and demonstrate that it circumvents a classical lower bound by Freund and Schapire (’95, ’12). Whereas the lower bound shows that Ω(1/γ2) weak hypotheses with γ-margin are sometimes necessary, our new method requires only Õ(1/γ) weak hypothesis, provided that they belong to a class of bounded VC dimension. Unlike previous boosting algorithms which aggregate the weak hypotheses by majority votes, the new boosting algorithm uses more complex (“deeper”) aggregation rules. We complement this result by showing that complex aggregation rules are in fact necessary to circumvent the aforementioned lower bound. (ii) Expressivity: Which tasks can be learned by boosting weak hypotheses from a bounded VC class? Can complex concepts that are “far away” from the class be learned? Towards answering the first question we identify a combinatorial-geometric parameter which captures the expressivity of base-classes in boosting. As a corollary we provide an affirmative answer to the second question for many well-studied classes, including half-spaces and decision stumps. Along the way, we establish and exploit connections with Discrepancy Theory.
more »
« less
Self-training Converts Weak Learners to Strong Learners in Mixture Models
More Like this
-
-
null (Ed.)Abstract The majority of user models in gamification are based on user’s gamer personality. However, the motivations driving individuals’ learning behavior differ from their motivations when playing. There is no evidence that learners’ experiences in gamified activities are described by these models. Thus, an alternative model capturing learners’ motivational experiences and relating them to the motivational mechanisms of gamification design is needed. To fill this gap we propose a context-specific typology which groups learners based on their type of motivation and perceived ability associated with a learning activity. The purpose of this proposal is to provide a framework for connecting each learner’s type to a set of motivational affordances to which that type is susceptible. Facilitating the task of selecting motivational affordances matching learner’s type aids the design of customized gamified learning.more » « less
-
null (Ed.)Quantum computing is poised to revolutionize some critical intractable computing problems; but to fully take advantage of this computation, computer scientists will need to learn to program in a new way, with new constraints. The challenge in developing a quantum computing curriculum for younger learners is that two dominant approaches, teaching via the underlying quantum physical phenomenon or the mathematical operations that emerge from those phenomenon, require extensive technical knowledge. Our goal is to extract some of the essential insights in the principles of quantum computing and present them in contexts that a broad audience can understand. In this study, we explore how to teach the concept of quantum reversibility. Our interdisciplinary science, science education, computer science education, and computer science team is co-creating quantum computing (QC) learning trajectories (LT), educational materials, and activities for young learners. We present a draft LT for reversibility, the materials that both influenced it and were influenced by it, as well as an analysis of student work and a revised LT. We find that for clear cases, many 8-9 year old students understand reversibility in ways that align with quantum computation. However, when there are less clear-cut cases, students show a level of sophistication in their argumentation that aligns with the rules of reversibility for quantum computing even when their decisions do not match. In particular, students did not utilize the idea of a closed system, analyzing the effects to every item in the system. This blurred the distinction between between reversing (undoing) an action, recycling to reproduce identical items with some of the same materials, or replacing used items with new ones. In addition, some students allowed for not restoring all aspects of the original items, just the ones critical to their core functionality. We then present a revised learning trajectory that incorporates these concepts.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
