Information Technology Reference
In-Depth Information
7.9 Computational Theories of Inductive Learning
Computational theories of learning mainly study sample and computation
complexity of learning algorithm. This section focuses on Gold learning theory
and Valiant learning theory.
Computational learning theory is very important for building a science of
machine learning, otherwise, it is difficult to recognize the scope of applicability
of a learning algorithm or analyze the learnability in different approaches.
Convergence, feasibility, and approximation are essential issues which require
computational learning theory to give a satisfying learning framework containing
reasonable restrictions. In computational learning theory early efforts along these
aspects are based primarily on Gold's framework (Gold, 1967). In context of
formulization linguistic learning, Gold introduces concept of convergence, which
handles the problem of learning from examples. Learning algorithm allows to
propose many assumptions without knowing when they are correct, only
determining the point where their computations are correct assumption. Because
of high complexity of Gold algorithm, this style is not applied in practical
learning.
Based on Gold's learning framework, Shapiro proposed model reasoning
algorithm to study the relation between formal language and its explanation, that
is, relation between grammar and semantics of formal language. Model theory
takes formula, sentence theory and their explanation - model as mathematic
object to study. Shapiro model reasoning algorithm can get a theory output only
need to input definite fact (Shapiro, 1981).
In 1984, Valiant proposed a new learning framework (Valiant, 1984), which
require high approximation with objective concept, and do not require accurate
identification of object concept. Kearns, Li, Pitt and Valiant gave some new
results to concept which can be represented as Boolean formula. Haussler applied
Valiant framework to analyze problems of version space and inductive bias, and
gave computing formula of computational complexity.
7.9.1
Gold's learning theory
The research of Gold's linguistic learning theory introduces two basic concepts,
i.e., limit identification and enumeration identification, which plays an important
role in early theory research of inductive reasoning (Gold, 1967).
Limit identification takes inductive reasoning as an infinitive procedure.
Ultimate or limit act can be seen as its successful standard. Assume
is an
inductive reasoning approach, which attempts to describe unknown rule R
correctly. Assuming
M
M
runs repeatedly, example set of R becomes more and
