| Abstract: |
In 1988 Littlestone introduced the optimal mistake-bound
learning model to learning theory. In this model the difficulty of
learning a concept from a concept class is measured by the K-dimension
of the concept class, which is a purely combinatorial notion. This is
similar to the situation in PAC-learning, where the difficulty of
learning can be measured by the Vapnik-Cervonenkis dimension.We show
that determining the K-dimension of a concept class is a PSPACE-complete
problem where the concept class is given as a circuit. This also
implies that any optimal learner (making the least number of mistakes)
that works on all concept classes over finite universes has to be
PSPACE-hard.
|