Resource-bounded Dimension in Computational Learning Theory

Details Resource-bounded Dimension in Computational Learning Theory Resource-bounded Dimension in Computational Learning Theory

2010-10-26

arxiv.org/abs/1010.5470v2

Computer Science

Computational Complexity

23 pages

Scientific paper

This paper focuses on the relation between computational learning theory and resource-bounded dimension. We intend to establish close connections between the learnability/nonlearnability of a concept class and its corresponding size in terms of effective dimension, which will allow the use of powerful dimension techniques in computational learning and viceversa, the import of learning results into complexity via dimension. Firstly, we obtain a tight result on the dimension of online mistake-bound learnable classes. Secondly, in relation with PAC learning, we show that the polynomial-space dimension of PAC learnable classes of concepts is zero. This provides a hypothesis on effective dimension that implies the inherent unpredictability of concept classes (the classes that verify this property are classes not efficiently PAC learnable using any hypothesis). Thirdly, in relation to space dimension of classes that are learnable by membership query algorithms, the main result proves that polynomial-space dimension of concept classes learnable by a membership-query algorithm is zero.

Affiliated with

Also associated with

No associations

Rating

Resource-bounded Dimension in Computational Learning Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Resource-bounded Dimension in Computational Learning Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Resource-bounded Dimension in Computational Learning Theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-160006