|
Specifying a Learning Model
|
Whenever one aims to model learning, several things have to be specified.
In the following we provide a list of the main aspects to be modeled.
- The Learner
Specifying the learner means answering the question “Who” is
doing the learning? The most general answer one may give in algorithmic
learning is that the learner is supposed to be an algorithm, i.e.,
a computer program. For example, the subfield of inductive inference
generally specifies the learner in this way.
However, the learner may be restricted in one way or
another. One may require the learner to be time efficient, i.e.,
to use an amount of time that is uniformly bounded by a polynomial
in the length of its inputs. The learner may be also restricted with respect
to its available amount of space, or the number of example it is allowed to
process for computing its actual hypothesis. Further restrictions are
possible and we shall come back to this point later.
- The Learning Domain
Specifying the learning domains means to define the set of objects
the learner has to deal with. For examples, we may request the
learner to learn an unknown concept, such as a car, a train,
a plane. Then, the learning goal consists in synthesizing
a “rule” to separate positive examples from negative ones.
That means, after having finished its learning task, the learner must
be able to correctly classify an object presented to him either as being
a car (a train, a plane) or as not being a car (a train, a plane).
This type of learning is referred to as concept learning, and
has been studied extensively.
However, there are many other objects the learnability of which
has been extensively studied, too. For example, the object to be
learned may be an unknown function, an unknown language, an unknown
device, an unknown technique (e.g., how to drive a car), an unknown
environment (e.g., a new building), an unknown family of
similar phenomena (e.g., voice recognition, face recognition,
character recognition (hand written or printed), an unknown graph,
and many, many more.
- The Source of Information
This part of the specification deals with the question from
“what” information the learner should perform its task. That
means, one has to clarify how the learner is informed about
the learning domain. There is a huge variety of ways how this can
happen. In the following we provide several examples that focus
on widely studied models.
- Examples.
In this scenario, the learner is fed
with examples of the object to be learned. For example,
when learning the concept of a chair, the learner is provided
particular instances that constitute or do not constitute
a chair. When learning an unknown function f,
the learner is provided input-output examples, i.e.,
(x0, f(x0)),
(x1, f(x1)),
(x2, f(x2)),... .
When learning a language, the learner
may be fed arbitrary strings over the underlying alphabet
that are classified with respect to their containment
in the target language. Alternatively, the learner may be also
requested to learn from positive examples, only.
Moreover, examples can be chosen in very different ways.
They might be chosen with respect to some underlying but
unknown (or known) probability distribution. Furthermore,
they might be chosen
arbitrarily, they can be chosen systematically, they can be
chosen maliciously (this is of special interest if one is
aiming to study the worst-case behavior of a learning algorithm).
On the other hand, the examples can be chosen carefully, too,
e.g., by a teacher who wants to facilitate the learning process.
Finally, one has also to specify how to describe the examples.
- Queries
In this scenario, the learner is enabled
to ask questions about the target object to a teacher.
For example, when learning the concept of a car, the learner
may ask “Is an Audi an example of a car?”
Or, when learning a language, it may ask “Is w a word
of the target language?” This type of question is usually
referred to as membership query. Alternatively, it may
ask “Is G a grammar for the target language?”
When learning an unknown environment, it may ask
“Is this a correct floor plan of the ground floor?”
The latter type of question is referred to as
equivalence queries, since the learner provides
a rule and asks if that rule is correct. There are
further types of possible questions, e.g.,
subset queries, superset queries, and disjointness
queries that have been studied intensively.
- Experiments.
In this scenario, the learner
may get information concerning the object to be learned
by actively experimenting with it. For example, the learner
may learn a new environment by walking through it. Again,
different walking strategies are imaginable, e.g., a random
walk, a nondeterministic walk, a systematic walk, a.s.o.
- The Hypothesis Space
Generally, a learner is supposed to map
evidence (e.g., examples) on the object to be learned into a hypotheses
about it. Therefore, one has to choose a set of possible descriptions.
Clearly, each rule contained in the learning domain has to possess at
least one description in the hypothesis space. However, the hypothesis
space may additionally contain descriptions not describing any object
in the learning domain. Furthermore, the descriptions provided by the
hypothesis space may be slightly different from those ones used
in defining the objects to be learned in the learning domain.
- Prior Knowledge
Here, one has to specify what does the learner
know about the domain initially? This generally restricts the learner's
uncertainty and/or biases and expectations about the objects to be learned.
Obviously, specifying the hypothesis space already provides some prior
knowledge. In particular, the learner knows that the target object
is representable in a certain way, e.g., as a graph having at most
1000 nodes, as a language acceptable by a finite automaton, or as function
computable by a program having at most 100 instructions. However, such
type of assumptions can be very unrealistic in practice. Furthermore,
prior knowledge my also be provided by “telling” the learner that
“simple” answers are preferable to more “complex” hypotheses.
Finally, looking at important applications one has to take into
account that prior knowledge may be “incorrect.” Thus, when developing
advance learning techniques one has to deal with the problem how
to combine or trade-off prior versus new information.
- The Criterion of Success
Finally, one has to specify the criteria for successful learning.
This part of the specification must cover at least some aspects
of our intuitive understanding of learning. For example, an automatic
camera may record everything around it, but it is intuitively obvious
that it does not learn. On the other hand, if we have an algorithm
which, after having been provided a set of examples for the concept
sofa, can label objects as either being a sofa or not being a sofa,
we may agree that it has learned something, i.e., the concept sofa.
When learning an unknown language, the criterion of success may
be specified to be grammar that generates precisely the strings in
the target language.
In particular, we have to deal with questions like:
“How do we know whether, or how well, the learner has learned?”
“How does the learner demonstrate that it has learned something?”
Each specification of the six items described above leads to a model
of learning. Next, we continue by exemplifying
the general outline given above.
Continue to the next page.
|
