Learning Algebraic Structures from Text Using Semantical Knowledge

Authors: Frank Stephan and Yuri Ventsov

Source: Lecture Notes in Artificial Intelligence Vol. 1501, 1998, 321 - 335.

Abstract. The present work investigates to which extent semantical knowledge can support the learning of basic mathematical concepts. The considered learning criteria are learning characteristic or enumerable indices for languages from positive data where the learner has to converge either syntactically (Ex) or semantically (BC). The considered classes are the classes of all monoids of a given group, all ideals of a given ring or all subspaces of a given vector space. The following is shown:

(a) Learnability depends much on the amount of semantic knowledge given at the synthesis of the learner where this knowledge is represented by programs for the algebraic operations, codes for prominent elements of the algebraic structure (like 0 and 1 in fields) and certain parameters (like the dimension of finite dimensional vector spaces). For several natural examples, good knowledge of the semantics may enable to keep ordinal mind change bounds while restricted knowledge may either allow only BC-convergence or even not permit learnability at all.

(b) A recursive commutative ring is Noetherian iff the class of its ideals is BC-learnable. Such a BC-learner can be synthesized from programs for addition and multiplication. In many Noetherian rings, one can Ex-learn characteristic indices for the ideals with an ordinal bound on the number of mind changes, But there are also some Noetherian rings where it is impossible to Ex-learn the ideals or to learn the characteristic indices for them.

©Copyright 1998 Springer