Generalized notions of mind change complexity
Arun Sharma, Frank Stephan, Yuri Ventsov · 1997
Speed of convergence in Gold's identification in the limit model can be measured by deriving bounds on the number of mind changes made by a learner before the onset of convergence. Two approaches to date are bounds given by constants (referred here as Type 1) and bounds expressed as constructive ordinals (referred as Type 2). The use of ordinals has recently been successfully employed to measure the mind change complexity of learning rich concept classes such as unions of pattern languages, elementary formal systems and logic programs. Motivated by these applications, the present work introduces two more general approaches to bounding mind changes. These are based on counting by going down in a linearly ordered set (Type 3) and on counting by going down in a partially ordered set (Type 4). In both cases the set must not contain infinite, descending, and computable sequences. These four types of mind changes yield a hierarchy and there are identifiable classes that cannot be learned wit...