Learning Half-Spaces and other Concept Classes in the Limit with Iterative Learners
This work addresses theoretical learning models for iterative algorithms, focusing on concept classes like half-spaces, but it is incremental as it builds on existing iterative learning frameworks.
The paper analyzes the relative learning power of different iterative learning settings, showing that strongly non-U-shaped learning is restrictive for iterative learning from informant, and provides a constructive iterative algorithm to learn the concept class of half-spaces from informant.
In order to model an efficient learning paradigm, iterative learning algorithms access data one by one, updating the current hypothesis without regress to past data. Past research on iterative learning analyzed for example many important additional requirements and their impact on iterative learners. In this paper, our results are twofold. First, we analyze the relative learning power of various settings of iterative learning, including learning from text and from informant, as well as various further restrictions, for example we show that strongly non-U-shaped learning is restrictive for iterative learning from informant. Second, we investigate the learnability of the concept class of half-spaces and provide a constructive iterative algorithm to learn the set of half-spaces from informant.