Loading...
Please wait, while we are loading the content...
Similar Documents
September 1989 LIDS-P-1910 On Metric Entropy , Vapnik-Chervonenkis Dimension , and Learnability for a Class of Distributions 1
| Content Provider | Semantic Scholar |
|---|---|
| Author | Kulkarni, Sanjeev R. |
| Copyright Year | 1989 |
| Abstract | In [23], Valiant proposed a formal framework for distribution-free concept learning which has generated a great deal of interest. A fundamental result regarding this framework was proved by Blumer et al. [6] characterizing those concept classes which are learnable in terms of their Vapnik-Chervonenkis (VC) dimension. More recently, Benedek and Itai [4] studied learnability with respect to a fixed probability distribution (a variant of the original distribution-free framework) and proved an analogous result characterizing learnability in this case. They also stated a conjecture regarding learnability for a class of distributions. In this report, we first point out that the condition for learnability obtained in [4] is equivalent to the notion of finite metric entropy (which has been studied in other contexts). Some relationships, in addition to those shown in [4], between the VC dimension of a concept class and its metric entropy with respect to various distributions are then discussed. Finally, we prove some partial results regarding learnability for a class of distributions. 1 Supported by the U.S. Army Research Office contract DAAL03-86-K-0171 (Center for Intelligent Control Systems) and by the Department of the Navy for SDIO. 2 Center for Intelligent Control Systems, M.I.T., 77 Massachusetts Ave., 35-423, Cambridge, MA, 02139 and M.I.T. Lincoln Laboratory, 244 Wood St., Lexington, MA 02173. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://dspace.mit.edu/bitstream/handle/1721.1/3155/P-1910-20783043.pdf?sequence=1 |
| Alternate Webpage(s) | http://dspace.mit.edu/bitstream/1721.1/3155/1/P-1910-20783043.pdf |
| Alternate Webpage(s) | http://dspace.mit.edu/bitstream/handle/1721.1/3155/P-1910-20783043.pdf?sequence=1 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
