Trial and error |
| |
| Authors: | Foued Ameur Paul Fischer Klaus -U Höffgen Friedhelm Meyer auf der Heide |
| |
| Affiliation: | 1. Heinz Nixdorf Institute and Department of Mathematics and Computer Science, University of Paderborn, Pohlweg 47-49, D-33095, Paderborn, Germany
2. Lehrstuhl Informatik II, Universit?t Dortmund, D-44221, Dortmund, Germany
|
| |
| Abstract: | A pac-learning algorithm isd-space bounded, if it stores at mostd examples from the sample at any time. We characterize thed-space learnable concept classes. For this purpose we introduce the compression parameter of a concept classb and design our Trial and Error Learning Algorithm. We show: b isd-space learnable if and only if the compression parameter ofb is at mostd. This learning algorithm does not produce a hypothesis consistent with the whole sample as previous approaches e.g. by Floyd, who presents consistent space bounded learning algorithms, but has to restrict herself to very special concept classes. On the other hand our algorithm needs large samples; the compression parameter appears as exponent in the sample size. We present several examples of polynomial time space bounded learnable concept classes: - all intersection closed concept classes with finite VC-dimension. - convexn-gons in ?2. - halfspaces in ?n. - unions of triangles in ?2. We further relate the compression parameter to the VC-dimension, and discuss variants of this parameter. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
