Rademacher-Oriented Theories of Formal Learning
Abstract
When developing new technologies, it is crucial to have an understanding of the edges of its applicability. Knowing where the boundaries lie points the way for us to use the technology in the broadest array of possible settings and to steer away from uses that are problematic or self defeating. Analysis of limitations requires careful statements of assumptions, which can highlight possible targets for future development. Machine learning is an exceptionally exciting technology, with recent breakthroughs providing solutions to longstanding problems ranging from general speech recognition to highly specialized strategic game play. In the rush to bring this technology to bear on the important challenges we face, however, it is essential that we proceed armed with knowledge of its fundamental strengths and weaknesses. The pioneering work of Vapnik and VC (Vapnik-Chervonenkis) dimension, and later, the PAC (probably approximately correct) learning paradigm, highlight the intrinsic relationship in supervised learning between the complexity of the hypothesis class that a learner employs and the amount of data needed to generalize effectively. The basic tension is that of the bias--variance dilemma---highly expressive hypothesis classes will exhibit lower bias (they are more likely to be able to accurately capture a target concept), but higher variance (they are more likely to require prohibitive amounts of data to get close to the right answer). Recently, the concept of Rademacher complexity has emerged as a powerful approach for characterizing learnability. A fundamental result shows that the generalization error in learning the concept class C from the sample S is bounded by twice the Rademacher measure RF(C,S). An advantage of the Rademacher complexity approach over previous measures is that it depends on the distribution of the training data and therefore can give tighter bounds than the VC-dimension and related measures that depend only on the combinatorial structure of the hypothesis set. In this 18-month project, we seek to apply Rademacher-oriented concepts to several central problems in machine learning, providing mathematical and computational tools that should make it possible to characterize the difficulty of learning problems and provide guidance for what approaches are most likely to lead to successful systems.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 11, 2018
- Source ID
- W911NF1610553
Entities
People
- Michael L. Littman
Organizations
- Army Contracting Command
- Brown University
- Defense Advanced Research Projects Agency