Technical Reports
Display by Author: A
| B
| C
| D
| E
| F
| G
| H
| I
| J
| K
| L
| M
| N
| O
| P
| Q
| R
| S
| T
| U
| V
| W
| X
| Y
| Z
|
TR-2004-6
Complexity Parameters for First Order Classes |
|
| Authors: | Arias, Marta; Khardon, Roni |
| Date: | July 2004 |
| Pages: | 24 |
| Download Formats: | [PDF] |
We study several complexity parameters for first order formulas and their suitability for first order learning models. We show that the standard notion of size is not captured by sets of parameters that are used in the literature and thus they cannot give a complete characterization in terms of learnability with polynomial resources. We then identify an alternative notion of size and a simple set of parameters that are useful in this sense. Matching lower bounds derived using the Vapnik Chervonenkis dimension complete the picture showing that these parameters are indeed crucial. |
|
Faculty: for help posting a technical report please visit the User Guide.