On Metric Entropy, Vapnik-Chervonenkis Dimension, and Learnability for a Class of Distributions

Abstract

A formal framework for distribution-free concept known as Valiant's learning framework has generated a great deal of interest. A fundamental result regarding this framework characterizes those concept classes which are learnable in terms of their Vapnik-Chervonenkis (VC) dimension. More recently, learnability in this case was shown. Also a conjecture regarding learnability for a class of distributions was stated. In this report, we first point out that the condition for learnability for a fixed distribution is equivalent to the notion of finite metric entropy (which has been studied in other contexts). Some relationships between the VC dimension of a concept class and its metric entropy with respect to various distributions are then discussed. Finally, we prove some indication of when the set of learnable concept classes is enlarged by requiring learnability for only a class of distributions.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 14, 1989
Accession Number
ADA217331

Entities

People

  • Sanjeev R. Kulkarni

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Availability
  • Discrete Distribution
  • Errors
  • Learning
  • Military Research
  • Probability
  • Probability Distributions
  • Random Variables
  • Statistical Samples
  • Theorems
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Neural Network Machine Learning.
  • Regression Analysis.
  • Theoretical Analysis.