On the Smallest Possible Dimension and the Largest Possible Margin of Linear Arrangements Representing Given Concept Classes Uniform Distribution.
Jürgen ForsterHans Ulrich SimonPublished in: ALT (2002)
Keyphrases
- half spaces
- uniform distribution
- concept classes
- pac learning
- target concept
- concept class
- membership queries
- boolean functions
- decision lists
- instance space
- learning theory
- agnostic learning
- mistake bound
- target function
- dnf formulas
- efficient learning
- term dnf
- vc dimension
- upper bound
- decision trees
- pac model
- classification noise
- learning dnf
- statistical queries
- learning models
- np hard
- active learning
- pairwise