ALT Page 2 back to the 
Algorithmic Learning Theory Page

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.

Valid HTML 4.0!