Identification In The Limit

Name	Identification In The Limit
Description	The scenario: A learner is supplied by a (infinite) stream of input data, generated according to a theory / language / function of a given representation class. The learning problem is to identify a hypothesis that explains the data stream, which means that the hypothesis is consistent with all of the data within the stream. In every iteration step the learner reads another piece of data and outputs a hypothesis of a given hypothesis language. The main questions addressed by the Identification In The Limit scenario: For which representation classes exist algorithms which identify a correct hypothesis at some point in time (in the limit) for any instance of the representation class, and just output syntactical variants of the result from that point on? Does a specific algorithm identify any / one specific instance of a representation class in the limit? The learner is not asked to realize that a correct hypothesis has been found! The questions can be refined: Is there a specific point in time for a specific learner, from where on the outputs are just variants of a correct result? Does the quality of the hypotheses increase every iteration step or may the quality decrease before a correct hypothesis is found?
Dm Step	Syntax/Grammar/Automata - Learning