TCS -TR-B-05-01

TCS Technical Report

Course Notes on Theory and Practice of Algorithms –Part I: Algorithmic Learning

byThomas Zeugmann

Division of Computer Science
Report Series B
June 7, 2005

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

thomas@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-7684+81-011-706-7684

Abstract
This report contains the course notes of Part I of Theory and Practice of Algorithms.
Within this part we deal with algorithmic learning. Some learning algorithms for fundamental learning problems are studied. Furthermore, we focus our attention on the complexity theoretical issues involved.
In addition to the usual wort-case analysis, we also deal with the average-case behavior. Therefore, one lecture is devoted to introduce the subject of average-case analysis ofalgorithms.
Finally, after having gained a deeper understanding of what algorithmic learning reallyis, we exemplify the application of algorithmic learning to the field of data mining.

Contents
L ECTURE 1: A LGORITHMIC L EARNING

1

1.1. What is Learning? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.3. Specifying a Learning Model . . . . . . . . . . . . . . . . . . . . . . . . .

9

L ECTURE 2: L EARNING M ODELS

15

2.1. Modeling a Learning Task . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

Variant 1: On-line Prediction . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.2. Learning in the Limit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.2.1. Basic Notations and Definitions . . . . . . . . . . . . . . . . . . . .

20

L ECTURE 3: M ORE ABOUT L EARNING IN THE L IMIT

25

3.1. The Weakness of Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

3.2. The Pattern Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

3.2.1. Learning the Pattern Languages via Descriptive Patterns . . . . . . .

29

3.3. Learning Recursive Functions . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.4. Points of Concern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

3.5. Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

3.6. Total Learning Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

L ECTURE 4: AVERAGE -C ASE C OMPLEXITY

45

4.1. Introductory Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

4.2. Analyzing the Common Algorithm for Finding the Maximum . . . . . . . .

47

L ECTURE 5: AVERAGE -C ASE A NALYSIS II
5.1. Average-Case Analysis for Learning in the Limit from Positive Presentations

i

53
55

ii

Thomas Zeugmann

L ECTURE 6: S TOCHASTIC F INITE L EARNING AND PAC L EARNING

61

6.1. Stochastic Finite Learning . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

6.2. Learning Monomials from Informant . . . . . . . . . . . . . . . . . . . . .

63

6.3. PAC Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

6.3.1. PAC Learning - the Finite Case . . . . . . . . . . . . . . . . . . . .

69

L ECTURE 7: D ECISION T REE L EARNING

73

7.1. Decision Tree Representation . . . . . . . . . . . . . . . . . . . . . . . . .

74

7.2. The Basic Decision Tree Learning Algorithm . . . . . . . . . . . . . . . . .

76

7.3. Information, Entropy and Information Gain . . . . . . . . . . . . . . . . . .

81

7.4. ID3’s Hypothesis Space . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

7.5. Inductive Bias in Decision Tree Learning . . . . . . . . . . . . . . . . . . .

85

1“Everything should be made as simple as possible, but not simpler.”
Albert Einstein

L ECTURE 1: A LGORITHMIC L EARNING
This course is about algorithms. The history of algorithms goes back, approximately, tothe origins of mathematics at all. For thousands of years, in most cases, the solution of amathematical problem had been equivalent to the construction of an algorithm that solved
it. The ancient development of algorithms culminated in Euclid’s famous “Elements”. Unfortunately, after Euclid the design of algorithms faced roughly 2000 years of decline. It got
increasingly popular to prove the existence of mathematical objects by using the techniqueof reductio ad absurdum.
Modern computation theory starts with the question:
Which problems can be solved algorithmically ?
It was posed due to the fact that despite enormous efforts of numerous mathematicians several problems had remained unsolved yet, e.g., the construction of an algorithm deciding
whether a given Diophantine equation has an integral solution (Hilbert’s 10th problem). In
order to answer it, first of all, the intuitive notion of an algorithm has to be formalized mathematically. Starting from different points of view, Turing [16], Church [3], and Gödel [4]have given their formalizations (i.e., the Turing machine, the λ–calculus, the recursive functions). However, all these notions are equivalent, i.e., each computation in formalism-1 canbe simulated in formalism-2 and vice versa. Since then, many other proposals had been
made to fix the notion of an algorithm (e.g., by Post [10] and by Markov [7]). This led to
the well-known “Church Thesis,” i.e., “the intuitive computable functions are exactly theTuring machine computable ones.
After the theory explaining which problems can and cannot be solved algorithmically
had been well-developed, the attention has turned to the qualitative side, i.e., How “good” aproblem can be solved? First influential papers in this direction were written by Rabin [11]and [12], as well as by Hartmanis and Stearns [5]; the latter paper gave the field its title:computational complexity. The central topic studied here was to clarify what does itmean to say that a function f is more difficult to compute than a function g. The distinction
between problems solvable within a time bounded by a polynomial in the length of the
input (that is, problems having a feasible solution) and those not having this property, firstwas made by J. von Neumann (1953). Since then, the class of polynomial time-boundedalgorithms has been an object of intensive and continuing research. On the other hand, it is
not known whether many of the problems that are very important for numerous applications
can be solved in polynomial time.
Since this is a very large area, we have to select certain problems we wish to study.
Recently, the field of knowledge discovery has attracted enormous interest. Therefore, we

2

L ECTURE 1: A LGORITHMIC L EARNING

would like to focus our attention in the first part of this course to several aspects related tothis area. In particular, we shall deal with algorithmic learning. But also this area is much
too large to be covered within such a short amount of time. Throughout this course, weshall have a closer look at the developments within the field of algorithmic learning. We
shall study some learning algorithms for fundamental learning problems. Additionally, we
focus our attention on the complexity theoretical issues involved.
After having gained a deeper understanding of what algorithmic learning really is, weshall turn our attention to the application of algorithmic learning to the field of data mining.
The second part of this course is on efficient data structures for manipulating Booleanfunctions. This part will be covered in a separate report.
Next, we would like to motivate the subject of algorithmic learning. So, let us ask
Why do we dream about algorithmic learning?
After all, humans are excellent learners. As Bertrand Russell [14] already noted“How comes it that human beings, whose contacts with the world are brief andpersonal and limited, are nevertheless able to know as much as they do know?”
But nowadays, it becomes more and more difficult to know what is already known.
There are many learning tasks that are far too complex for humans, or solving them byhumans is quite expensive, and/or takes a huge amount of time, thus, the knowledge gained
may be out of data before it is even ready. So, it would be better, if computers could learn,
for instance, knowledge bases from examples. It would also be desirable to have computersthat can discover knowledge by their own.
This idea, however, is not as new as it may seem. Shortly after the first computers havebeen emerged, pioneering researchers formulated the goal to construct a machine which iscapable to learn. Allan Turing [17] considered the capability to learn as a major part ofintelligence.
Nevertheless, the problem reached a new dimension during the last decade. Nowadays,
across a wide variety of fields, data are being collected and accumulated at a dramatic pace.
For example, within the human genome project there are now billions of data available. But
researchers in this field are not mainly interested in the data themselves. Instead, they wantto find out, for example, which genes may cause a particular kind of cancer. So, there is anurgent need for a new generation of computational techniques and tools to assist humans in
extracting useful information (knowledge) from the rapidly growing volumes of data.
As Pieter Adriaans and Dolf Zantinge [1] put it:“We are confronted with the paradox of the growth of data, that more datameans less information. In the future, the ability to read and to interpret alone
will not be enough to sur vive as a professional, a scientist or a commercialorganization. The mechanical production and reproduction of data force us toadapt our strategies and develop mechanical methods of filtering, selecting, andinterpreting data.”

W HAT IS L EARNING ?

3

A similar viewpoint has been expressed by Richter et al. [13]“Moreover, nowadays the data collected in in various fields such as biology, finance, retail, astronomy, medicine are extremely rapidly growing, but our ability to discover useful knowledge from such huge data sets is still too limited.
Clearly, powerful learning systems would be an enormous help in automatically extracting new interrelations, knowledge, patterns and the like from thoseand other huge collections of data.”
Within the process of discovering knowledge from data bases, very often algorithmic
learning plays an important role. Therefore, we shortly introduce this subject here. Before
doing this, it is very useful to recall a point made by Donald Knuth [6] in his Turing Awardlecture.
“Science is knowledge that we understand so well that we can teach it to acomputer; and if don’t fully understand something, it is an art to deal with it.
. . . we should continually be striving to transform every art into science: in theprocess, we advance the art.”Thus it is only natural to ask whether learning is an art or a science.
1.1.

What is Learning?

Since humans are excellent learners, at first glance it should be easy to define what
learning is. So, let us continue by looking at some of the definitions proposed.
Simon [15] gave the following well-known definition;“Learning denotes changes in the system that . . . enable the system to do thesame task or tasks drawn from the same population more efficiently and more
effectively the next time.”
It is not hard to see that this definition also covers phenomena that are usually not considered as learning. For example, if we run the same program on a faster computer thenexecution will be faster. Please think about more examples along this line. On the other
hand, this definition does not cover all aspects of learning. For example you may study
a map before driving to destination unknown to you. Then just by knowing your way(because you learned it before starting your drive) you behave probably much better thansomeone who has not studied the map in advance. But you can do better the first time andnot only when driving the second time.
So, let us see what else has been proposed.
“Learning is making useful changes in our minds.”

4

L ECTURE 1: A LGORITHMIC L EARNING

This definition has been given by Marvin Minsky [9]. However, it may be require substantial effort to make it applicable to the construction of a learning computer.
Another famous definition is due to Michalski [8].
“Learning is constructing or modifying representations of what is being experienced.”
And sometimes we even find (cf. Adriaans and Zantinge [1])“We will not state what learning is.”So, we see it is by no means easy to arrive at a useful definition. The state of the art canbe characterized as follows (cf. Richter et al. [13]).
Numerous mathematical models of learning have been proposed during thelast three decades. Nevertheless, different models give vastly different results
concerning the learnability and non-learnability of objects one wants to learn.
Hence, finding an appropriate definition of learning which covers most aspectsof learning is also part of the goals aimed at in algorithmic learning theory.
For getting a first understanding of what we have to talk about, let us continue by looking
at some examples.
1.2.

ExamplesWe restrict ourselves here to inductive learning, i.e., to scenarios in which the learner, atevery stage, has access to a finite set of data, though it has possibly to generalize its findings
to an infinite set of data. Our first example is drawn from the area of function learning. A
teacher is providing input-output examples of the target function. So, let us assume that wehave received
f (0) = 0 and f (1) = 1 .
What function could it be? Since there is no need to introduce anything sophisticated at thispoint, most people would conjecture that the target function can be expressed as f (x) = x.
But the next example is destroying this conjecture, our teacher just suppliedf (3) = 720! ,where the factorial function n! is inductively defined as 0! = 1 and (n + 1)! = (n + 1)n!
for all n ≥ 0.
At this point we make the following observation.
f (3) = 720! = (6!)! = ((3!)!)! = 3!!!

E XAMPLES

5This suggests the following solution.
g(x, 0) = xg(x, n + 1) = g(x, n)!
f (x) = g(x, x) .
A quick check shows that we are correct, sincef (0) = g(0, 0) = 0
f (1) = g(1, 1) = g(1, 0 + 1) = g(1, 0)! = 1! = 1
f (3) = g(3, 3) = g(3, 2 + 1) = g(3, 2)! = g(3, 1 + 1)! = (g(3, 1)!)!
= (g(3, 0 + 1)!)! = ((g(3, 0)!)!)! = ((3!)!)!
As a matter of fact, for finding this solution we have applied a famous principle from the philosophy of science usually referred to as Occam’s Razor which was formulated around1320 by William of Occam as follows.
“Entities should not be multiplied unnecessarily.”The best reformulation of this principle for scientists is: When you have two competingtheories which make exactly the same predictions, the one that is simpler is the better.
Therefore, if we look at the examples as expressions of the form y = f (x) we had toexpress y in termini of x.
Furthermore, we made a couple of implicit assumptions which we would like to makeexplicitly right now. First, we have assumed that we have to learn a function. This targetfunction is chosen by the teacher from a set of functions. Additionally, we assumed thatthe function is defined over the set N of natural numbers. So, the domain is a class ofcomputable functions over the natural numbers.
Note that the assumption to have a computable function is essential in this context, sinceotherwise we cannot find a finite description for the target function. Moreover, we caninterpret our solution as a program computing f . Thus, our learner produced a sequence of
hypotheses and each hypothesis has been chosen from the set of all programs computing
functions over N. From now on, we shall refer to set of all allowed hypotheses as to the
hypothesis space.
Assuming that we indeed learned the target function, we see that the learning successoccurred only after a certain number of examples. So, in general we always have to definea criterion of success.
Last but not least, since we want to clarify what algorithmic learning is, we have assumed
the learner to be an algorithm. This learner may have searched for the simplest program
explaining the data.

6

L ECTURE 1: A LGORITHMIC L EARNING

Putting it all together, we can summarize our approach as follows.
domain:class of computable functions

Information source:

examples: (x, f (x))

hypothesis space:

all programs

Learning method:

searchSemantics of hypotheses:

programcorrect after finitely many examples
Success criterion:
Next, we look a problem that may serve as a typical example for many data mining tasks.
So, let us look at the following tiny data set called the weather data. Of course, this data set
is fictitious, but it serves its purpose to explain some typical features. The data concern theconditions for playing some unspecified game.
outlooksunny
sunny
overcast
rainy
rainy
rainy
overcast
sunny
sunny
rainy
sunny
overcast
overcast
rainy

temperature
hot
hot
hot
mild
cool
cool
cool
mild
cool
mild
mild
mild
hot
mild

humidity
high
high
high
high
normalnormalnormalhighnormalnormalnormalhighnormal
high

windy
false
true
false
false
false
true
true
false
false
false
true
true
false
true

play
no
no
yes
yes
yes
no
yes
no
yes
yes
yes
yes
yes
no

Figure 1.1: The Weather Data
In the table displayed above, we have four attributes, i.e., outlook, temperature,humidity, and windy. These attributes can take symbolic values rather than numericalvalues. The rightmost column shows the recommendation, that is whether or not one shouldplay.
outlooksunnytemperaturecool

humidity
high

windy
true

play
?

Figure 1.2: The data for tomorrow.

Next, we ask if there are any rules behind this table. This is the typical question asked indata mining. The typical problem is then to make predictions. For example, we are given
the following data for tomorrow (cf. Figure1.2).

7

E XAMPLES

So, what should we do, play or not play? Of course, this prediction should be be consistent with the table given above. Now, the idea is first to learn a decision tree from thetable above. Then, we apply it to the data for tomorrow. A decision tree explaining the data
above could look as follows.

outlooksunnyovercast

rainy

yes
humidity
high
no

windy
normal

false

yes

true

yes

no

Figure 1.3: Decision tree for the weather data.

In order to see that this decision tree explains the table, let us look at the following
example (the first data row of the table shown in Figure 1.1).
outlooksunnytemperaturehothumidity
high

windy
false

play
no

Figure 1.4: First entry of the weather data.

Using the decision tree above, we obtain the classification shown in Figure 1.4 by following the path determined by the values given for the attributes (cf. Figure 1.5).

outlooksunnyovercast

rainy

yes
humidity
high
no

windy
normal

yes

false
yes

true
no

Figure 1.5: Application of the decision tree to the data in Figure

The rest of the table is verified analogously.

8

L ECTURE 1: A LGORITHMIC L EARNING

Now, we can apply the decision tree from Figure 1.3 to make the desired prediction.
Since outlook is sunny and humidity is high we have to follow the same path as in
Figure 1.5 and obtain no. Thus, we obtain:
outlooksunnytemperaturecool

humidity
high

windy
true

play
no

Figure 1.6: The data for tomorrow completed.

Of course, you may wonder why the attribute temperature does not appear in ourdecision trees. Answering this question is closely related to the problem of how to constructdecision trees for tables such as the weather data. We shall deal with these questions in
Lecture 7.
Finally, we again summarize the approach undertaken in an analogous way as we didfor the function learning problem. Thus, we obtain the following.
domain:discrete functions

Information source:

positive and negative examples

hypothesis space:

all decision trees

Learning method:decision tree learner

Semantics of hypotheses:

classifiercorrect after finitely many examples
Success criterion:
Next, we take a look at a slightly different example. We wish to model learning tasks
such as “Learning of Data Structures” from examples. Data structures are used in many
applications. In order to keep the example simple, let us look at something familiar, i.e., alist of references.
G OLD , M.E. (1967), Language identification in the limit, Information and Control 10,447 – 474.
L ANGE , S. AND W IEHAGEN , R. (1991), Polynomial-time inference of arbitrary patternlanguages, New Generation Computing 8, 361 – 370.
Of course, this list is a very short one. Usually, one has large or even huge bibliographies.
These bibliographies may come from different sources and thus one may wish to unify
them. So, one could choose the liked best, learn its underlying data structure and apply the
result to the remaining ones.
Looking at the two examples given, the underlying data structure might have the following pattern:
AUTHORS, I NITIALS. (Year), Title, Journal Volume, number – number.
or more formally: x1 , x2 .(x3 ), x4 , x5 x6 , x7 − x8 .
Any pattern is a non-empty string over A ∪ X, where A is an alphabet, X is a countably
infinite set of variables and A ∩ X = ∅. Pattern define languages in a natural way. The

S PECIFYING A L EARNING M ODEL

9language generated by a pattern π is the set of all strings that can be obtained by substituting
all occurrences of variables by (non-empty) strings over A, where the same variables haveto be substituted by the same string. For example, the pattern xx generates the language
L = {ww w ∈ A+ }. We shall formally define patterns and pattern languages in Lecture 3.
So, in our example above, A consists of the Latin alphabet, the punctuation symbols,
the digits {0, 1, . . . , 9}, and the parentheses ( ).
Note, however, that the references given above could be already generated by the following pattern
x1 , x2 .(19x3 ), x4 , x5 x6 , x7 − x8 7x9 .
Summarizing in an analogous way as above, now we obtain:
domain:pattern languages

Information source:

positive examples

hypothesis space:

all patterns

Learning method:

string algorithms

Semantics of hypotheses:interpretation of patterns

Success criterion:

correct after finitely many examples

1.3.

Specifying a Learning Model

After having seen three examples, we continue by clarifying the subject of Algorithmic
Learning Theory. We focus our attention in partially answering of what machine learning is supposed to mean. Answering this question includes both developing mathematicalmodels of machine learning and deriving results within the models developed. Both parts
deserve special attention. In general, a model should capture at least significant applications. However, as already mentioned, the state of the art in modeling learning is still muchless satisfactory than in other areas of theoretical computer science.
For example, around 60 years ago computability theory emerged. Initially, many different models have been introduced, e.g., Turing machines, partial recursive functions,Markov algorithms, Church’ λ-calculus. Nevertheless, later on, all those models have been
proved to be equivalent. Subsequently, researchers focused their attention to obtaining results within the model.
Another example is the rapidly emerging field of parallel computation. Unlike sequential
algorithms, for which the above standard models exist, there are many contending models
on which parallel algorithms can be based. Different parallel computer models differ fromeach other in various ways, e.g., whether or not different instructions on different data canbe performed at one time, with respect to the geometrical arrangement of the processors
and their interconnection, etc. However, there is a huge amount of literature relating thesemodels to one another, and there is at least a universal interconnection pattern; i.e., the socalled parallel computation thesis (cf., e.g., Zeugmann [18] and the references therein).

10

L ECTURE 1: A LGORITHMIC L EARNING

The situation in algorithmic learning theory is however, quite different. Numerous mathematical models of learning have been proposed during the last three decades. Nevertheless, different models give vastly different results concerning the learnability and nonlearnability of objects one wants to learn. Hence, finding an appropriate definition of learning which covers most aspects of learning is also part of the goals aimed at in algorithmic
learning theory.
As we have seen above, every learning model has to specify several aspects. In thefollowing we provide a more detailed explanation of the main aspects to be modeled.
1. The Learner: Specifying the learner means answering the question “Who” is doing thelearning? The most general answer one may give in algorithmic learning is that thelearner is supposed to be an algorithm, i.e., a computer program. For example, thesubfield of inductive inference generally specifies the learner in this way (cf., e.g., Angluin and Smith [2]). 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 bealso restricted with respect to its available amount of space. Further restrictions are
possible, and we shall discuss them throughout this course.
2. The Domain: “What” is being learned? The answer to this question specifies the objects
the learner has to deal with. For example, we may request the learner to learn an
unknown concept, such as a table, a chair, a sofa. Then, the learning goal consists insynthesizing 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 chair (a table, a sofa) or as not being a chair(a table, a sofa). This type of learning is referred to as concept learning, and has beenstudied 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 acar), an unknown environment (e.g., a new building), an unknown family of similar
phenomena (e.g., voice recognition, face recognition, character recognition (handwritten or printed), an unknown graph, and many, many more.
3. The Information Source: 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 target object. There is a huge variety of ways
how this can happen. In the following we provide several examples that focus on
widely studied models.
(i) Examples: In this scenario, the learner is fed with examples of the object tobe learned. For example, when learning the concept of a chair, the learner isprovided particular instances that constitute or do not constitute a chair. When

S PECIFYING A L EARNING M ODEL

11

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 areclassified 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 chosenwith 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 isaiming 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 tofacilitate the learning process.
There is another important aspect that will be described later, i.e., the problem
how to describe the examples.
(ii) Queries: In this scenario, the learner is enabled to ask questions about thetarget 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 alanguage, 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 agrammar 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 ofquestion is referred to as equivalence queries, since the learner provides a ruleand asks if that rule is correct. There are further types of possible questions,e.g., subset queries, superset queries, and disjointness queries that have beenstudied intensively.
(iii) Experimentation: In this scenario, the learner may get information concerning
the object to be learned by actively experimenting with it. For example, thelearner 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.
When talking about the information source, another very important aspect has to beconsidered. This issue is whether or not the model can handle noisy or erroneous
information sources. As an example, consider a learner that aims to recognize zip
codes on letters. The learner is given examples provided by a post office employee.
However, sometimes the employee may misread the handwritten codes. This resultsin erroneous information.
4. 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

12

L ECTURE 1: A LGORITHMIC L EARNING

domain. Furthermore, the descriptions provided by the hypothesis space may beslightly different from those ones used in defining the objects to be learned in thelearning domain.
5. 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 andexpectations about the objects to be learned. Obviously, specifying the hypothesis
space already provides some prior knowledge. In particular, the learner knows thatthe 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 bya program having at most 100 instructions. However, such type of assumptions canbe 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 thatprior 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.
6. Success Criteria: Finally, one has to specify the criteria for successful learning. Thispart 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 analgorithm 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 haslearned something, i.e., the concept sofa. 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. Theinterested reader is referred to the references listed below for further information. In thefollowing lecture, we shall continue by exemplifying the general outline given above.

References[1] P. A DRIAANS AND D. Z ANTINGE (1997), Data Mining, Addison-Wesley Longman
Publishing Co, Boston, MA.
[2] D. A NGLUIN AND C.H. S MITH (1983), Inductive inference: theory and methods,
Computing Surveys 15, 237 - 269.
[3] A. C HURCH (1936), An unresolvable problem of elementary number theory, Am. J.
Math. 58, 345 – 365.
[4] K. G ÖDEL (1931), Über formal unentscheidbare Sätze der Principia Mathematica
und Verwandter Systeme, Monatshefte Mathematik Physik 38, 173 – 198.

S PECIFYING A L EARNING M ODEL

13[5] J. H ARTMANIS AND R.E. S TEARNS (1965), On the computational complexity ofalgorithms, Trans. Am. Math. Soc. 117, 285 – 306.
[6] D.E. K NUTH (1974), Computer Programming as an Art, Commun. ACM bf 17
No. 12, 667-673.
[7] A.A. M ARKOV (1954), Theoria Algorithmov, Akad. Nauk SSSR, Math. Inst. Trudy
42.
[8] R. M ICHALSKI (1986), Understanding the nature of learning: issues and research
directions, in (R.S. Michalski, J.G. Carbonell and T.M. Mitchell, eds.), “Machine
Learning: An Artificial Intelligence Approach, Vol. 2,” pp. 3 – 25, Morgan Kaufman,
Los Altos, Calif.
[9] M. M INSKY, The Society of Mind (1985), Simon & Schuster Inc., New York.
[10] E. P OST (1943), Formal Reductions of General Combinatorial Decision Problems,
Am. J. Math. 65, 197 – 215.
[11] M.O. R ABIN (1959), Speed of computation and classification of recursive sets, inThird Convention Sci. Soc., Israel, pp. 1 – 2.
[12] M.O. R ABIN (1960), Degrees of difficulty of computing a function and a partial
ordering of recursive sets, in Technical Report No. 1, University of Jerusalem.
[13] M.M. R ICHTER , C.H. S MITH R. W IEHAGEN AND T. Z EUGMANN (1998), Editors’
Introduction, in (M.M. Richter, C.H. Smith R. Wiehagen and T. Zeugmann, eds.),
Algorithmic Learning Theory, 9th International Conference, ALT ’98, Otzenhausen,
Germany, October 1998, Proceedings, Lecture Notes in Artificial Intelligence 1501,
pp. 1 – 10, Springer, Berlin.
[14] B. RUSSELL (1948), Human Knowledge: Its Scope and Limits, Simon and Shuster,
New York.
[15] H. S IMON (1983), Why should machines learn?, in (R.S. Michalski, J.G. Carbonell
and T.M. Mitchell, eds.), “Machine Learning: An Artificial Intelligence Approach,”
pp. 25–38, Tioga Publishing, Palo Alto, Calif.
[16] A.M. T URING (1936/1937), On computable numbers with an application to the
Entscheidungsproblem, Proc. London Math. Soc. 42, 230 – 265.
[17] A.M. T URING (1950), Computing Machinery and Intelligence, Mind 59, 433-460.
[18] T. Z EUGMANN (1990), Parallel Algorithms, Encyclopedia of Computer Science andTechnology Vol. 21, Supplement 6, Allen Kent and James G. Williams (eds.), pp. 223– 244, Marcel Dekker Inc. New York and Basel.

15

L ECTURE 2: L EARNING M ODELS
After having seen what one has to specify in order to arrive at a learning model, we aim
at defining some learning models.
2.1.

Modeling a Learning Task

Humans are able to distinguish between different “things,” e.g., chair, table, sofa, book,newspaper, car, airplane, a.s.o. Also, there is no doubt that humans have to learn how to
distinguish “things.” Therefore, we ask whether this particular learning problem allows analgorithmic solution, too. That is, we specify the learner to be an algorithm. Furthermore,
we may be tempted to specify the learning domain to be the set of all things. However, since
we aim to model learning, we have to convert “real things” into mathematical descriptionsof things. This can be done as follows. We fix some language to express a finite list of
properties. Afterwards, we decide which of these properties are relevant for the particularthings we want to deal with, and which of them have to be fulfilled or not to be fulfilled,respectively. For example, the list of properties may be fixed as follows:- possesses 4 legs, - possesses a rest, - has brown color, - possesses 4 wheels,- it needs fuel, - possesses a seat,- possesses wings, . . . , - has more than 100 pages.
Now, we can answer“What is a chair?”“What is a table?”by deciding which of the properties are relevant for the concept “chair,” and which ofthem have to be fulfilled or not to be fulfilled, respectively.
For chair, we obtain:

and fortable:

1. possesses 4 legs - yes- yes

2. possesses a rest - yes- no

3. has brown color - irrelevant- irrelevant

4. possesses 4 wheels - no

- no

5. it needs fuel - no

- no

6. possesses a seat - yes- no

7. possesses wings - no

- no

.

.

.

.

.

.

- no
n. has more than 100 pages - no
As you can see, there are two rows at which the entries differ, i.e., possesses a rest andpossesses a seat. Thus, by using our properties, we could distinguish chair and table.

16

L ECTURE 2: L EARNING M ODELS

Next, we denote the n properties by the variables x1 , . . . , xn , where range(xj ) ⊆ {0, 1}
for j = 1, . . . , n. The semantics is then obviously as follows. xj = 1 means property j isfulfilled, while xj = 0 refers to property j is not fulfilled.
Then chair: {0, 1}n → {0, 1}, where(1,
if x1 = x2 = x6 = 1, and x4 = x5 = x7 = . . . = xn = 0
chair(x1 , . . . , xn ) =0,otherwise
Now, setting Ln = {x1 , x̄1 , x2 , x̄2 . . . , xn , x̄n } (set of literals) we can express the concept “chair” by the monomial that contains precisely the relevant literals, i.e., chair =x1 x2 x̄4 x̄5 x6 x̄7 . . . x̄n . Note that x3 does not appear in the monomial “chair, ” since it isirrelevant.
Hence, we may redefine the learning domain to be the set X = {0, 1}n . We regard X
as the instance space consisting of instances described by bit vectors of length n. Then thecollection of objects to be learned is the set C of all concepts c: X → {0, 1} that are describable by a monomial over X . Thus, the concepts c classify each instance b as negative(if c(b) = 0) or positive (if c(b) = 1). Hence, we may identify the concept c with the setof all positive instances for it. That means, we regard c as a subset of X , and identify itwith its characteristic function. There are two constant characteristic functions, i.e., 1 and 0
referring to the concept “TRUE” and “FALSE,” respectively. “TRUE” can be represented
by the empty monomial, and “FALSE” can be represented by, e.g., x1 x̄1 . There is a conceptional difference between the class C of all concepts describable by a monomial and theset of all monomials itself. Namely, different monomials may describe the same concept.
For example, the concept “FALSE” can be represented by x1 x̄1 , x2 x̄2 , ..., x1 x̄1 . . . xn x̄n .
However, the concept “FALSE” is the only one allowing different descriptions. Therefore,
in the following we often identify the set of all monomials over Ln and the concept class C.
Note that n is fixed. Thus, C is finite.
Exercise 1. Determine card(C).
We still have to specify the source of information, the hypothesis space, the prior knowledge, and the criterion of success. There are several ways to do this, and we shall have alook at some variants. In all variants we are going to consider, the prior knowledge is thatthe target concept is a monomial.
Variant 1: On-line prediction
In this setting, the source of information is specified as follows. The learner will be
fed successively more and more labeled examples of the monomial to be learned. Thatis, the learner is given a sequence hb1 , m(b1 ), b2 , m(b2 ), . . .i, where the bj ∈ {0, 1}n , i.e.,
Boolean vectors, and m(bj ) ∈ {0, 1} denote the value of the target monomial under the
obvious assignment of the values provided in bj to its literals. The examples are picked up
arbitrarily, and are noise free.
We do not specify the hypothesis space explicitly. It is left to the learner to choose it.

VARIANT 1: O N - LINE P REDICTION

17

Finally, we have to specify the criterion of success. In this example, we consider online prediction. That is, the learner must predict each m(b), after having fed b. Then, it
receives the true value of m(b), and the next Boolean vector. We measure the performsof the learner by the number of prediction mistakes made. The learner has successfully
learned if it eventually reaches a point beyond which it always correctly predicts.
Obviously, there is a trivial solution. The learner simply keeps track of all examples
and their labels provided. If it is fed a vector b the label of which it has already seen, it
predicts the correct label. Otherwise, it predicts 0. After having seen all possible examples,
it surely can correctly predict. However, there are 2n Boolean vectors of length n. As aconsequence, this trivial algorithm may make many prediction errors.
Exercise 2. Determine the number of prediction errors made by the trivial algorithm inthe worst-case.
This number is terribly large. For any n of practical relevance, it may take centuries
before the algorithm has achieved its learning goal. Clearly, this is not acceptable. Hence,
we continue by asking whether we can do it better. The affirmative answer is provided by
the following theorem.
Theorem 2.1. On-line prediction of monomials over Ln can be done with at most n + 1
prediction errors.
Proof. For all i = 1, 2, . . . let bi = b1i b2i . . . bni denote the ith Boolean vector. First of all,we describe the prediction algorithm P.
Algorithm P: “On successive input hb1 , m(b1 ), b2 , m(b2 ), . . .i do the following:
Initialize h0 = x1 x̄1 . . . xn x̄n .
For i = 1, 2, . . . let hi−1 denote P’s internal prediction hypothesis produced before
receiving bi . After having received bi predict hi−1 (bi ). Then, read m(bi ).
If hi−1 (bi ) = m(bi ) then hi = hi−1 else
for j := 1 to n do
if bji = 1 then delete x̄j in hi−1 else delete xj in hi−1 .
Denote the result by hi . By convention, if all literals have been removed, then hi = ∅,and hi (b) = 1 for all b ∈ X .
end.”
Before analyzing the prediction algorithm P we illustrate it at the following example.
Let n = 7, and let m = x1 x̄2 x4 x7 be the target monomial. Suppose the input sequence tostart as follows: h1001111, 1, 0110110, 0, 1011101, 1, 1011001, 1, . . .i.
Then, P initially predicts h0 (1001111) = 0. However, the true value is 1, and thus
P executes the loop described above resulting in h1 = x1 x̄2 x̄3 x4 x5 x6 x7 . After having
read b2 = 0110110, P predicts h1 (0110110) = 0 which is true. Hence, h2 = h1 =x1 x̄2 x̄3 x4 x5 x6 x7 . Next, P reads 1011101, and predicts h2 (1011101) = 0 which is wrong.

18

L ECTURE 2: L EARNING M ODELS

Thus, P executes the loop, and computes h3 = x1 x̄2 x4 x5 x7 . Now, P reads 1011001 andpredicts 0 which is again wrong. Therefore, P executes the loop again, and computes
h4 = x1 x̄2 x4 x7 . Since this internal hypothesis equals the target monomial, P makes nomore prediction errors. Consequently, it does not change its internal hypothesis any further.
We proceed by proving the correctness of P. Since P computes all its internal hypotheses by possibly removing literals from h0 , it suffices to show that all the literals in the target
monomial survive and that every prediction error results in removing at least one literalfrom P’s actual internal hypothesis. This is done via the following claims.
Claim 1. No literal in the target concept m is ever removed from h0 .
Suppose the converse, i.e., there is a literal, say `i , in the target monomial m which
is sometimes removed from h0 . Let `i be the first such literal. Consequently, before thisliteral `i is removed, all literals in m are still contained in P’s internal hypothesis h. Thus,
every example b satisfying P’s internal hypothesis satisfies m, too, i.e., h(b) = 1 implies
m(b) = 1. Thus, the removal must happen on an example b such that m(b) = 1 but
h(b) = 0. However, while processing its loop P removes exclusively those literals `j forwhich `j (bj ) = 0. But for all literals `k in m we have `k (bk ) = 1, and hence they survive.
This contradiction proves Claim 1.
Claim 2. Prediction errors are exclusively made on positive examples.
By construction, P performs all of its predictions by its internal hypotheses which constitute monomials. The value of a monomial is 1 if and only if all its literals evaluate to
1. Hence, if m(b) = 0, then at least one of its literals must evaluate to 0. By Claim 1, allliterals contained in m are contained in all of P’s internal hypotheses, too. Thus, at least
one of the literals in P’s actual internal hypothesis also evaluates to 0 causing P to predict
0. Hence, no prediction error can occur on a negative example.
Claim 3. Each prediction error causes P to remove at least one literal from its actualinternal hypothesis.
Suppose the converse, i.e., after some prediction error no literal is removed. Thus, theexample on which the prediction error occurred must satisfy all literals in P’s actual internal
hypothesis, since otherwise at least one literal is removed. Consequently, P has predicted
1, but since we had a prediction error, the true value of the target must be 0. Therefore, theprediction error had to occur on a negative example. This contradicts Claim 2.
Finally, we have to prove that at most n + 1 prediction errors occur. Initially, P’s
internal hypothesis h0 contains 2n literals. However, for each example exactly n literals
evaluate to 1 and exactly n literals evaluate to 0. Hence, the first prediction error causes P
to remove precisely n literals from its actual internal hypothesis h = h0 . Now, the worstcase obviously occurs if all literals must be eliminated from h0 , i.e., if m is the constantmonomial 1 (= TRUE). Now, the assertion directly follows by Claim 3. This proves thetheorem.
Exercise 3. Construct a sequence of examples such that the worst-case bound stated in
Theorem 2.1 happens.

L EARNING IN THE L IMIT

19

You may test your sequence by using our implementation of Algorithm P (there called
Wholist Algorithm) at:
http://www-alg.ist.hokudai.ac.jp/ thomas/BOOLE/menue1.jhtml
As we have seen, when learning the class of all concepts describable by a monomial
over the domain {0, 1}n within the on-line prediction model, then n + 1 prediction errors
may occur in the worst-case.
It is also easy to see that two prediction errors are sufficient in the best-case.
Moreover, if we run our algorithm P in practice, we may just observe that usually muchless than n + 1 prediction errors occur. So, we may ask how many prediction errors do
occur during a “typical” run of algorithm P. Clearly, dealing with the latter question also
requires to define what is meant by “typical” run. This will directly lead us to the subjectof average-case analysis.
Note that it is often much more complicated to perform an average-case analysis than todetermine the worst-case and (or) best-case behavior of an algorithm. Therefore, we shallcome back to this point later. But in the meantime, you can perform some experiments withthe on-line prediction algorithms at:
http://www-alg.ist.hokudai.ac.jp/ thomas/BOOLE/menue2.jhtml
As a matter of fact, it is advantageous to introduce another learning model at this point.
2.2.

Learning in the Limit

As we have seen, the class of concepts describable by a monomial is learnable in theon-line prediction model. Of course, the class of concepts describable by a monomial is not
too difficult. Thus, it would be only natural to ask what other concept classes are learnable
within the prediction model. Instead of answering this question right now, we want totake a broader approach and continue with the fundamental notion of learning in the limit.
The corresponding theory, called inductive inference may be viewed as roughly as
computational theory is to complexity and analysis of algorithms. Thus, dealing with thispart of algorithmic learning theory will provide us a deeper understanding of what can beor cannot be expected from algorithmic learning in general.
Note that induction constitutes an important feature of learning. Inductive inference
may be characterized as the study of systems that map evidence on a target concept intohypotheses about it. Investigating scenarios in which the sequence of hypotheses stabilizes
to an accurate and finite description of the target concept is of particular interest. Precise
definitions of the notions evidence, stabilization, and accuracy go back to Gold [4] who
introduced the model of learning in the limit.
Next, we informally describe this model. The source of information are infinite sequences of examples. We distinguish learning from positive data and learning from positive
and negative data, synonymously called learning from text and informant, respectively.
A text for a target concept c is an infinite sequence of elements of c such that every elementfrom c appears eventually. Alternatively, an informant is an infinite sequence of elements

20

L ECTURE 2: L EARNING M ODELS

exhausting the underlying learning domain that are classified with respect to their containment in the target concept.
An algorithmic learner, henceforth called inductive inference machine (abbr. IIM), takes
as input larger and larger initial segments of a text (an informant) and outputs, from time totime, a hypothesis about the target concept. The set of all admissible hypotheses is called
hypothesis space. The sequence of all hypotheses output is required to converge to a ahypothesis correctly describing the target concept.
By the definition of convergence, only finitely many data about the target concept c havebeen observed by an IIM M at the (unknown) point of convergence. Hence, some formof learning must take place in order for M to learn the target concept c. For this reason,
hereafter the terms identify, learn and infer are used interchangeably.
So far we left it open what kind of convergence we are going to require. We shall distinguish between syntactical convergence, where the sequence of hypotheses has to stabilize.
That is, after some point the IIM always outputs one and the same hypothesis. The resulting
learning model is usually called learning in the limit.
Alternatively, we shall also consider semantical convergence, where the sequence of
hypotheses has to behave as follows. After some point, the IIM always outputs hypotheses
that are correct for the target concept, but which are not necessarily equal to one another.
For example, looking again at our class of concepts describable by a monomial, an IIM
which is supposed to infer the concept “FALSE” may output many different hypotheses forit, e.g., x1 x1 , x1 x2 x1 , x1 x2 · · · xn x1 · · · xn . Though the resulting learning model also learns
in the limit, one usually refers to it as behaviorally correct learning in order to distinguishit from the one where syntactical convergence is required.
We continue with a formal introduction of learning in the limit and behaviorally correct
learning.
2.2.1.

Basic Notations and Definitions

Let N = {0, 1, 2, . . .} be the set of all natural numbers and let N+ = N \ {0}.
Any recursively enumerable set X is called a learning domain. By ℘(X ) we denote thepower set of X . Let C ⊆ ℘(X ) and let c ∈ C. We refer to C and c as to a concept classand a concept, respectively. Sometimes, we will identify a concept c with its characteristic
function, i.e., we write c(x) = 1, if x ∈ c, and c(x) = 0, otherwise.
Within this course, we mainly study the learnability of indexable concept classes (cf.
Angluin [1]). A class of non-empty concepts C is said to be an indexable concept class iff
there are an effective enumeration (cj )j∈N of all and only the concepts in C and a recursivefunction f such that, for all j ∈ N and all x ∈ X , f (j, x) = cj (x) holds. By IC we denotethe collection of all indexable classes.
Next, we describe some well-known examples of indexable classes. Let Σ denote any
fixed finite alphabet of symbols, and let Σ∗ be the free monoid over Σ. We set Σ+ =
Σ∗ \ {ε}, where ε denotes the empty string. Then X = Σ∗ serves as the learning domain.

BASIC N OTATIONS AND D EFINITIONS

21

As usual, we refer to subsets L ⊆ Σ∗ as to languages (instead of concepts). Then, the setof all context sensitive languages, context free languages, regular languages, respectively,
form indexable classes.
Next, let Xn = {0, 1}n be the set of all n-bit Boolean vectors. We consider X =n≥1 Xn as learning domain. Then, the set of all concepts expressible as a monomial, ak-CNF, a k-DNF, and a k-decision list form indexable classes.
S

Angluin [1] started the systematic study of learning indexable concept classes. Thissetting attracted a lot of attention, since many natural concept classes are indexable (seeabove). For an overview we refer the interested reader to Zeugmann and Lange [6].
Let c ⊆ X be any concept, and let t = s0 , s1 , s2 , . . . be any infinite sequence suchthat range(t) = {sk k ∈ N} = c. Then t is said to be a text for c, or synonymously,
a positive presentation. By (c) we denote the set of all positive presentations of c.
S
Furthermore, for every indexable class C we set text(C) = c∈C (c).
Furthermore, let i = (s0 , c(s0 )), (s1 , c(s1 )), (s2 , c(s2 )), . . . be any infinite sequence suchthat range(i) = {sk k ∈ N} = X ; then we refer to i as an informant, or synonymously
as to positive and negative data. By info(c) we denote the set of all informants of c.
S
Furthermore, for every indexable class C we set Info(C) = c∈C info(c).
Moreover, let t, i be a text and an informant, respectively, and let x ∈ N. Then tx , ix
denote the initial segment of t and of i of length x + 1, respectively. Furthermore, we use−+t+
x to denote the range of tx , and ix and ix to denote the set of all positive and negative
instances in ix , respectively.
Furthermore, the learner is an algorithmic device which works as follows: It takes as its
input larger and larger initial segments of a text t (an informant i) and it either requests thenext input string (labeled input string), or first outputs a hypothesis, i.e., a number encoding
a certain computer program, and then it requests the next input string (the next labeled
example). Note that an IIM, when learning a target class C, is required to produce an output
on every initial segment of all texts in text(C).
It is common to refer to the learner as to an inductive inference machine (abbr.
IIM) in this setting. The hypotheses output by an IIM are interpreted with respect to asuitably chosen hypothesis space H = (hj )j∈N . When an IIM M outputs some number j,
we interpret it to mean that M hypothesizes hj .
When dealing with indexable concept classes, we usually require the hypothesis space
H to be an indexing of some possibly larger indexable concept class. Hence, in this case,membership is uniformly decidable in H, too. In general, however, we allow any mapping
h: X → {0, 1} such that the partial characteristic function of it is computable as hypothesis
and assume furthermore the set of all hypotheses to be recursively enumerable. So, as amost general hypothesis space one could choose any fixed Gödel numbering ϕ (sometimes
also called acceptable programming system) of the recursively enumerable sets over theunderlying learning domain.
Furthermore, we shall distinguish the following types of hypothesis spaces. Let C be
any concept class. A hypothesis space H is said to be class preserving for C iff each

22

L ECTURE 2: L EARNING M ODELS

concept c ∈ C possesses a description h in the hypothesis space, and each description
available in the hypothesis space corresponds to a concept in the target concept class. Moreformally, we can express the requirement for a hypothesis space to be class preserving byrange(C) = range(H). Next, we weaken this requirement to range(C) ⊆ range(H), i.e.,
we allow the hypothesis space to contain descriptions of sets not necessarily corresponding
to target concepts. We refer to such hypothesis spaces as to class comprising hypothesis
spaces. At first glance, it might seem useless to enlarge the hypothesis space, since any
hypothesis not describing a target concept is definitely wrong. However, as we shall see
later, sometimes it is unavoidable to allow class comprising hypothesis spaces in order toachieve superior learners.
Next, we specify the criterion of success. Let σ be a text or informant, respectively, andx ∈ N. Then we use M (σx ) to denote the last hypothesis produced by M when successively
fed σx . The sequence (M (σx ))x∈N is said to converge in the limit to the number j if
and only if either (M (σx ))x∈N is infinite and all but finitely many terms of it are equal to j,or (M (σx ))x∈N is non-empty and finite, and its last term is j. Now we are ready to define
learning in the limit.
Definition 1 (Gold [4]). Let C be a concept class, let c be a concept, and let H = (hj )j∈N
be a hypothesis space. An IIM M CLimTxt– [CLimInf ]–identifies c from text
[informant] with respect to H iff for every text t [informant i ] for c, there exists aj ∈ N such that the sequence (M (tx ))x∈N [(M (ix ))x∈N ] converges in the limit to j andc = hj .
Furthermore, M CLimTxt– [CLimInf ]–identifies C with respect to H iff, for each c ∈ C,
M CLimTxt– [CLimInf ]–identifies c with respect to H.
Finally, let CLimTxt [CLimInf ] denote the collection of all concept classes C forwhich there are an IIM M and a hypothesis space H such that M CLimTxt– [CLimInf ]–identifies C with respect to H.
In the above definition, Lim stands for limit and the C preceding it points to the factthat we allow class comprising hypothesis spaces. If we just write LimTxt then we additionally require H to be a class preserving hypothesis space. Moreover, we sometimes
write CLimTxt H to denote the fact that learning has to be performed with respect to the
hypothesis space H. We use these conventions for all learning types defined within thiscourse, unless otherwise stated.
Note that, in general, it is not decidable whether or not an IIM M has already inferred atarget concept c. Hence, when dealing with learning in the limit, we have a limiting effective
criterion of learning instead of an effective one. However, this scenario also reflects sometypical aspects of human learning. For example, when humans are learning their mothertongue, usually they are gradually improving their ability to speak and to understand it.
These intermediate stages may be viewed as the generation of a sequence of hypotheses
that eventually converges to a grammar that is (sufficiently) correct.
Figure 2.1 displays the basic features of the learning in the limit model.

BASIC N OTATIONS AND D EFINITIONS

23

Description at time t:OutIn

ht ←− M ←− dt , . . . , d0
M learns successfully in this model iff there is a point T such that hT is correct
for c and hT = hT +1 = hT +2 = hT +3 = . . . .
Figure 2.1: Learning in the Limit

The following exercise is intended to help you gaining a first understanding of learningin the limit.
Exercise 4. Prove or disprove.
(a) Let n ∈ N be arbitrarily fixed. The set Cn of all monomials over Ln can be CLimInf –identified with respect to the set of all monomials as hypothesis space. Does youranswer remain valid for CLimTxt?
SSS(b) Let X = n∈N {0, 1}n , let C = n∈N Cn be the set of all monomials over n∈N Ln .
Then C is CLimInf –identifiable with respect to C. Does your answer remain valid
for CLimTxt?
(c) Let X be any learning domain, let C be any concept class over X , and let H be any
hypothesis space for C such that each h ∈ H is recursive. Then,(α) C ∈ CLimInf implies that C is on-line predictable.
(β) If C is on-line predictable then C ∈ CLimInf .
Next, we formally define behaviorally correct learning. For the sake of presentation,
this is only done for learning from positive data.
Definition 2 (Bārzdiņš [2], Case and Lynes [3]). Let C be a concept class, let c be aconcept, and let H = (hj )j∈N be a hypothesis space. An IIM M CBcTxt–identifies cwith respect to H iff for every text t ∈ (c) and for all but finitely many y ∈ N, hM (ty ) = c.
Furthermore, M CBcTxt–identifies C with respect to H iff M CBcTxt–identifies eachc ∈ C with respect to H.
Finally, let CBcTxt denote the collection of all concept classes C for which there are an
IIM M and a hypothesis space H such that M CBcTxt–identifies C with respect to H.
If you compare Definitions 1 and 2 then you see that the only difference is the kind of
convergence required. That is, Definition 1 requires syntactical concergence while Definition 2 weakens this requirement to semantical convergence.
Exercise 5. Formally define behaviorally correct learning from informant.

24

L ECTURE 2: L EARNING M ODELS

Finally, we refer the interested reader to Osherson, Stob and Weinstein [5] for a comprehensive treatment of learning recursively enumerable languages in the limit. The learnability of language classes with uniformly decidable membership is surveyed in Zeugmann
and Lange [6].

References[1] D. A NGLUIN (1980), Inductive inference of formal languages from positive data,
Information and Control 45, No. 2, 117–135.
[2] J. B ĀRZDIŅ Š (1974), Two theorems on the limiting synthesis of functions, In Theory of Algorithms and Programs Vol. 1, pages 82–88, Latvian State University, (inRussian).
[3] J. C ASE AND C. LYNES (1982), Machine inductive inference and language identification, in Automata, Languages and Programming, 9th Colloquium, Proceedings,
volume 140 of Lecture Notes in Computer Science, pages 107–115. Springer-Verlag.
[4] E.M. G OLD (1967), Language identification in the limit, Information and Control
10, 447 – 474.
[5] D. O SHERSON , M. S TOB , AND S. W EINSTEIN (1986), Systems that Learn, An Introduction to Learning Theory for Cognitive and Computer Scientists, The MIT-Press,
Cambridge, MA.
[6] T. Z EUGMANN AND S. L ANGE (1995), A guided tour across the boundaries of learning recursive languages, in “Algorithmic Learning for Knowledge-Based Systems”(K.P. Jantke and S. Lange, eds.), Lecture Notes in Artificial Intelligence 961, pp. 190– 258, Springer-Verlag, Berlin.

25

L ECTURE 3: M ORE ABOUT L EARNING IN THE L IMIT
We finished the last lecture by introducing learning in the limit. As far as learning ofindexed families from informant is concerned, a very general result can be obtained which
we present here.
Theorem 3.1 (Gold [5]). C ∈ LimInf for all C ∈ IC.
Proof. Let X be the underlying learning domain. Since C ∈ IC, there are an indexing(cj )j∈N of all and only the concepts in C and a recursive function f such that f (j, x) = cj (x)for all j ∈ N and all x ∈ X . Now, let c ∈ C be any concept and let i = ((sk , c(sk )))k∈N ∈info(c) be any informant for c.
The desired IIM M learns by the so-called identification by enumeration principle which
is formally defined as follows.
Let y ∈ N. On input iy we set:
M (iy ) = “Search the least k ∈ N such that (sj , c(sj )) = f (k, sj ) for all j = 0, . . . , y.”Since c ∈ C and (cj )j∈N is an indexing for C with the above properties for f , we see thatthe test (sj , c(sj )) = f (k, sj ) is recursive for all k ∈ N and all j ∈ N. Furthermore, let k ∗be the least k ∈ N such that c = ck . Consequently, (sj , c(sj )) = f (k ∗ , sj ) for all j ∈ N andhence, the search performed by M will always terminate. That is, all hypotheses k output
by M satisfy k ≤ k ∗ . Moreover, c` 6= c for all ` < k ∗ . Therefore, for every ` < k ∗ there
must be a y` such that (sy` , c(sy` )) 6= f (`, sy` ). Hence, for y ≥ max{y` ` < k ∗ } the IIM
M cannot output any ` < k ∗ . Thus, for all y ≥ max{y` ` < k ∗ } it outputs k ∗ and thus
converges to k ∗ . Since c = ck∗ , M learns c as required.
Consequently, M LimInf –identifies C with respect to (cj )j∈N and we are done.
The learning method used by the IIM defined in the proof of Theorem 3.1, i.e., identification by enumeration, has some interesting and important properties which we want todiscuss shortly.
−
First, it is consistent. Here by consistency we mean that i+x ⊆ ck and ix ∩ ck = ∅whenever k is output by M . We shall discuss the consistency phenomenon in some detailbelow.

Second, any mind change performed by M is justified by a “provable misclassification”
of its previous guess. Here, by mind change we mean that M (iy ) 6= M (iy+1 ). Therefore,
M will never reject a guess that is correct for the concept to be learned. Hence, M issemantical finite.
Third, M is set-driven, too, i.e., its output exclusively depends on the range of its input(cf. Definition 5 below).
Finally, identification by enumeration is the most efficient learning method with respect
to learning time, i.e., the first time such that M outputs a correct guess that will be repeated

26

L ECTURE 3: M ORE ABOUT L EARNING IN THE L IMIT

in every subsequent learning step (cf. Gold 5). More precisely, Gold 5 proved that there
is no IIM M̂ inferring L which is uniformly faster than the IIM M described above withrespect to learning time. Hence, in the setting of learning indexed families identification by
enumeration is particularly tailored for learning from informant.
3.1.

The Weakness of Text

First, we present a very simple example for a concept class that is not in LimTxt.
Example 1. The following language class L cannot be learned in the limit from positive
data with respect to the hypothesis space L.
We define the language class L by the following enumeration of languages over thealphabet {a}. Let L = (Lj )j∈N where L0 = {a}+ and Lj = {am 1 ≤ m ≤ j} forall j ∈ N+ . We show that L is not learnable in the limit from positive data. Suppose theconverse, i.e., there is an IIM M which witnesses L ∈ CLimTxt with respect to L. Then,
M in particular has to identify the language L1 on its uniquely defined text t. Hence, there
exists an x ∈ N such that M (tx ) = 1. Obviously, it is possible to extend tx in order toobtain a text for the infinite language L0 . Namely, we may choose the text tx · t̂ where t̂ isthe lexicographically ordered text of L0 . That is, t̂ = a, aa, aaa, aaaa, . . .. Since M has toinfer L0 from this text, too, M is forced to change its mind to the hypothesis 0. Therefore,
there is a y ∈ N+ such that M (tx · t̂y ) = 0. But now we may conclude that tx · t̂y is an initial
segment of a text t̃ for the finite language Ly . Consequently, M has to perform one moremind change when successively fed t̃. By iterating this idea one may effectively constructa text for the infinite language L0 on which M has to change its mind infinitely often, acontradiction. Hence L ∈/ CLimTxt with respect to L.
Exercise 6. Prove or disprove: The language class C = range(L), where L is defined
as above, cannot be learned in the limit with respect to every hypothesis space H for it.
This negative result is mainly caused by the problem that both finite and infinite languages have to be simultaneously handled.
We continue with Gold’s [5] famous result.
Theorem 3.2 (Gold [5]). Let L be any class of languages containing all finite languages
and at least one infinite language L. Then L ∈/ CLimTxt.
Proof. Assume any hypothesis space H for L, and suppose there is an IIM M learning
L in the limit with respect to H. We are going to construct a text t for the infinite language
L on which M does not converge in the limit. First, consider any text t̂ = s0 , s1 , s2 , . . .
for L. Since we have M supposed to learn L, there must be an x such that j0 = M (tx )fulfills L = L(hj0 ). Set tx = t̂x . Clearly, t̂x is finite, and thus t̂x is an initial segment of
the finite language L1 = t̂+x . Since M has to learn the finite language L1 , too, the initial
segment t̂x can be extended by s0 , s0 s0 , . . . resulting in a text t̃ for L1 . Thus, there must
be a y such that j1 = M (t̃x+y ) satisfies L1 = L(hj1 ). Note that t̃x+y is an initial segment
extending t̂x such that t̃+
x+y ⊆ L. Thus, we may continue the definition of t by setting
tx+y = tx s0 , . . . , s0 .
| {z }
y timesT HE PATTERN L ANGUAGES

27

Now, we continue by extending t̃x+y by t̂. Again, there must be z > x + y such thatM , when fed t̃x+y · t̂z outputs a hypothesis j2 such that L = L(hj2 ). Thus, we continue
the definition of t as follows: tx+y+z = t̂x s0 , . . . , s0 t̂z . Noting that t+
x+y+z is again a finite| {z }
y timeslanguage, it is obvious how to iterate this procedure. The requirement z > x + y ensuresthat t will be indeed a text for L, and by construction, M changes its hypotheses infinitely
often when successively fed t, a contradiction.
The latter theorem allows the following corollary.
Corollary 3.3. Neither the class of all regular languages nor any superset thereof canbe learned in the limit from positive data.
Taking the latter corollary into account, many researchers thought that there is no interesting class of languages at all that can be learned from positive data. As a result, thestudy of learning from positive data faced more than a decade of decline after Gold’s [5]pioneering paper. In order to gain a better understanding why this has been the case, you
should solve the following exercise.
Exercise 7. Prove or disprove: Let L be any class of languages containing all finite
languages and at least one infinite language L. Then L ∈/ CBcTxt.
But the situation considerably changed when Angluin [1] showed that the pattern languages are learnable in the limit from text. Therefore, we continue with the pattern languages which we have already met in Lecture 1.
3.2.

The Pattern Languages

Patterns are a very natural way to define formal languages. Suppose you are interested
in the language of all strings over the alphabet A = {0, 1} starting with 11, ending with
010, and containing the substring 01011 somewhere, but may be otherwise arbitrary. Thus,
all strings in your language follow the pattern π1 = 11x0 01011x1 010, provided you arewilling to allow the variables x0 , x1 to be substituted by any string over {0, 1} including
the empty one. As for another example, consider the set of all strings having even length
2n such that the prefix of length n is identical to the suffix starting at position n + 1. In thatcase, the wanted language follows the pattern π2 = x0 x0 .
Though patterns have already been considered since the beginning of this century (cf.,e.g., Thue [15], and Bean et al. [3]), the formal introduction of patterns and pattern languages goes back to Angluin [1]. Since then, pattern languages and variations thereof havebeen widely investigated (cf., e.g., Salomaa [12, 13], and Shinohara and Arikawa [14] foran overview).
Following Angluin [1] we define patterns and pattern languages as follows. Let A ={0, 1, . . .} be any non-empty finite alphabet containing at least two elements. By A∗ wedenote the free monoid over A (cf. Hopcroft and Ullman [6]). The set of all finite non-null
strings of symbols from A is denoted by A+ , i.e., A+ = A∗ \ {}, where  denotes theempty string. By |A| we denote the cardinality of A. Furthermore, let X = {xi i ∈ N}

28

L ECTURE 3: M ORE ABOUT L EARNING IN THE L IMIT

be an infinite set of variables such that A ∩ X = ∅. Patterns are non-empty strings fromA ∪ X, e.g., 01, 0x0 111, 1x0 x0 0x1 x2 are patterns. The length of a string w and of apattern π is denoted by |w| and |π|, respectively. A pattern π is in canonical form provided
that if k is the number of different variables in π then the variables occurring in π are
precisely x0 , . . . , xk−1 . Moreover, for every j with 0 ≤ j < k − 1, the leftmost occurrenceof xj in π is left to the leftmost occurrence of xj+1 in π. The examples given above arepatterns in canonical form. In the sequel we assume, without loss of generality, that all
patterns are in canonical form. By Pat we denote the set of all patterns in canonical form.
Let π ∈ Pat, 1 ≤ i ≤ |π|; we use π(i) to denote the i-th symbol in π. If π(i) ∈ A,
then we refer to π(i) as to a constant; otherwise π(i) ∈ X, and we refer to π(i) as to avariable. By #var(π) we denote the number of different variables occurring in π, and by#xi (π) we denote the number of occurrences of variable xi in π. If #var(π) = k, thenwe refer to π as a k-variable pattern. Let k ∈ N, by Pat k we denote the set of all kvariable patterns. Furthermore, let π ∈ Pat k , and let u0 , . . . , uk−1 ∈ A+ ; then we denoteby π[x0 : u0 , . . . , xk−1 : uk−1 ] the string w ∈ A+ obtained by substituting uj for eachoccurrence of xj , j = 0, . . . , k − 1, in the pattern π. The tuple (u0 , . . . , uk−1 ) is called
substitution. Furthermore, if |u0 | = · · · = |uk−1 | = 1, then we refer to (u0 , . . . , uk−1 ) as
to a shortest substitution. Now, let π ∈ Pat k , and let S = {(u0 , . . . , uk−1 ) uj ∈ A+ , j =0, . . . , k − 1} be any finite set of substitutions. Then we set S(π) = {π[x0 : u0 , . . . , xk−1 :uk−1 ] (u0 , . . . , uk−1 ) ∈ S}, i.e., S(π) is the set of all strings obtained from pattern π byapplying all the substitutions from S to it. For every π ∈ Pat k we define the language
generated by pattern π by L(π) = {π[x0 : u0 , . . . , xk−1 : uk−1 ] u0 , . . . , uk−1 ∈ A+ }.
By PAT k we denote the set of all k-variable pattern languages. Finally, PAT =k∈N PAT k denotes the set of all pattern languages over A. Note that for every L ∈ PAT
there is precisely one pattern π ∈ Pat such that L = L(π) (cf. Angluin [1]).
S

If we take a look back to the patterns considered in Lecture 1, we that they have a peculiarity, i.e., each variable occurs at most once. Such pattern are called regular patterns.
the following exercise sheds some more light on this naming.
Exercise 8. Prove or disprove:(1) If π ∈ Pat is regular, then L(π) is a regular language.
(2) If π is not regular, then L(π) is necessarily a non-regular language.
The pattern languages constitute an indexable class. Clearly, one can recursively enumerate all canonical patterns, say by π0 , π1 , π2 , . . .. Moreover, given any pattern π and astring s it suffices to check all substitutions having a length not exceeding |s| until eithers is generated by π or all substitutions have been tested. Thus, (L(πj ))j∈N is indeed an
indexable class.
Angluin [1] showed that PAT is learnable from text with respect to the hypothesis space
Pat. The key idea of her proof was to observe that it suffices to find descriptive patterns
which we define next.
Definition 3. Let A be any finite alphabet.

L EARNING THE PATTERN L ANGUAGES VIA D ESCRIPTIVE PATTERNS

29(1) A finite set {s0 , s1 , . . . , sr } ⊆ A+ of strings is called a sample.
(2) A pattern π is consistent with a sample S if S ⊆ L(π).
(3) A pattern π is said to be descriptive for S if it is consistent and there is no otherconsistent pattern τ such that L(τ ) ⊂ L(π).
The following structural property of indexable classes is important with respect to theirlearnability from text. This property has been first observed for the class of all patternlanguages, but its importance justifies the following definition.
Definition 4. Let X be any learning domain and let C be any indexable class. C is said
to have finite thickness provided for each S ⊆ X the set {c S ⊆ c and c ∈ C} is offinite cardinality.
Now, let us check whether or not PAT indeed has finite thickness.
Lemma 3.4. PAT has finite thickness.
Proof. Let S ⊆ A∗ be any set, and let m = min{|s| s ∈ S}. Since we restricted
ourselves to nonempty substitutions, we can immediately conclude that for every patternπ ∈ Pat, |π| > m implies S 6⊆ L(π). But {π π ∈ Pat, |π| < m} is finite, and thus,{π π ∈ Pat, S ⊆ L(π)} must be finite, too.
Corollary 3.5. For every set S ⊆ A∗ there is always at least one descriptive pattern.
Proof. For every set S we have S ⊆ L(x0 ). Thus, the set of all consistent patterns for S
is always nonempty. Since PAT has finite thickness, the set of all consistent patterns for S isfinite, too. Consequently, there must be a minimal element (with respect to set-containment)in the set of all consistent patterns for S.
Next, we establish the learnability of the set of all pattern languages from text.
3.2.1.

Learning the Pattern Languages via Descriptive Patterns

We continue with the following important theorem.
Theorem 3.6. Assume any recursive subprocedure des computing descriptive patterns
for every set S ⊆ A∗ . Then, PAT ∈ CLimTxt.
Proof. Let L ∈ PAT , let t = (sj )j∈N ∈ text(L), and x ∈ N. We define the wanted IIM
as follows:
M (tx ) = “If x = 0 compute π =des({s0 }), and output it.
If x > 0, let τ = M (tx−1 ). If t+
x ⊆ L(τ ), output τ .
Otherwise, compute π =des(t+x ), and output it.”30

L ECTURE 3: M ORE ABOUT L EARNING IN THE L IMIT

Since the subprocedure des is recursive, M is indeed an IIM. It remains to show that M
infers L. Let π ∈ Pat be the unique pattern satisfying L = L(π). Clearly, π is consistent
with t+x for every x ∈ N. Now, consider any τ output by M . If τ = π we are done, since
π will be then output on tx+r for every r ≥ 0. Suppose, τ 6= π. Since τ is descriptive,
we already know that L(π) 6⊂ L(τ ). Hence, L(π) \ L(τ ) 6= ∅. But that means, there mustbe at least one string s ∈ L(π) \ L(τ ) which has to appear sometimes in t, say at position
x0 . Thus, M (tx0 ) 6= τ . Now, taking into account that there are only finitely many patterns
that are consistent with s0 , we see that every mind change does shrink the set of descriptive
patterns by at least one element. Since every descriptive pattern but π has to be abandoned
as shown above, M has to converge to π.
Thus, for establishing the learnability of all pattern languages from text, we finally haveto prove that there is a procedure des computing descriptive patterns. This is done next.
The main problem we have to handle is how to figure out whether or not L(π) ⊂ L(τ ) for
any two patterns π and τ that are consistent with some given sample S. For that purpose,
we need the following definitions and notations.
Let Hom be the set of all non-erasing homomorphism with respect to concatenationof Pat to itself. An element of Hom that is the identity when restricted to A is called
substitution. Next, we define a binary relation  over Pat by π  τ iff π = f (τ ) forsome substitution f . The intuitive meaning of  may be taken to be “is less general than.”Example. Let A = {0, 1}, and let π = x0 0x0 01 and τ = x1 x1 x0 . Then π  τ .
For seeing this, we define a substitution f by f (x0 ) = 1 and f (x1 ) = x0 0 (remember,f (0) = 0 as well as f (1) = 1). Thus f (τ ) = x0 0x0 01 = π.
Exercise 9. Prove that for all π, τ ∈ Pat,(1)  is transitive,(2) π  τ implies L(π) ⊆ L(τ ),(3) L(π) = L(τ ) iff π  τ and τ  π,(4)  is computable.
Now, we are ready to establish the following theorem.
Theorem 3.7. There is a recursive procedure des which, for every sample S given as
input, outputs a descriptive pattern π for S.
Proof. The procedure des is defined as follows. Let S be any sample, and let ` =min{|s| s ∈ S}. Enumerate the finitely many canonical patterns π satisfying |π| ≤ `.
For every pattern enumerated check whether or not S ⊆ L(π). Let C be the set of all
enumerated patterns successfully passing this test. Let m = max{|π| π ∈ C}, and let
Ĉ = {π π ∈ C, |π| = m}. Find and output any element π in Ĉ that is minimal withrespect to .

L EARNING THE PATTERN L ANGUAGES VIA D ESCRIPTIVE PATTERNS

31

We have to show that π is descriptive for S. Let τ be any consistent pattern for S. Then|τ | ≤ `, and if |τ | < |π|, then L(τ ) 6⊂ L(π), too. Now, assume |τ | = |π|. Consequently,τ ∈ Ĉ. By construction, either τ = π or τ 6 π. If τ = π, we are done. The proof is finishedby showing the following claim actually stating that the second case cannot happen.
Claim. Let π, τ ∈ Pat such that |π| = |τ |. Then L(τ ) ⊆ L(π) implies τ  π.
Let 0, 1 ∈ A be distinct. Consider the substitutions f0 (xi ) = 0, and f1 (xi ) = 1 for alli ∈ N as well as the substitutions gj defined for all i , j ∈ N as follows:0,
if i = j,gj (xi ) =1,otherwise.
Let S(π) consist of the set of all strings {f0 (π), f1 (π), g0 (π), g1 (π), g2 (π), . . .}, and define S(τ ) analogously. If #var(π) = 0, then S(π) = L(π) = {π}, and we are alreadydone. If #var(π) = 1, then S(π) = {f0 (π), f1 (π)}, and in the general case, i.e., if#var(π) = k ≥ 2, then |S(π)| = k + 2.
Furthermore, by construction we obtain: For all 1 ≤ m, n ≤ |π|:(1) if π(m) = c ∈ A, then s(m) = c, for all s ∈ S(π), and the same holds for τ ,(2) if π(m), π(n) ∈ X such that π(m) 6= π(n), then there is a string s ∈ S(π) such thats(m) 6= s(n), and again, the same holds for τ .
Now, taking into account that L(τ ) ⊆ L(π), for every s ∈ S(τ ) there exists a substitution
h such that s = h(π). But |s| = |τ | = |π|; thus h must map each variable in π intoa string of length one. Let 1 ≤ m, n ≤ |π|. If π(m) = c ∈ A, then s = h(π) must
fulfill s(m) = c, and since this holds for all s ∈ S(τ ), we already know τ (m) = c. If
π(m) = π(n) = xi ∈ X, then s = h(π) must satisfy s(m) = s(n) ∈ A, and since thisholds for all s ∈ S(τ ), we conclude τ (m) = τ (n). Thus, the set of positions of xi are all
occupied by the same symbol, say g(xi ), in τ . Hence, we may extend g to be a substitution
such that τ = g(π), and therefore, τ  π.
Now the principal learnability of all pattern languages in the limit from positive data has
been established.
Note that Angluin’s [1] learner M as described above has two additional properties.
First, it is consistent. Here consistency means that for all texts t of pattern languages,
and x ∈ N we have, if π = M (tx ), then t+x ⊆ L(π). Moreover, it is set-driven, where
set-drivenness is formally defined as follows:
Definition 5. Let L be any indexable class. An IIM is said to be set-driven withrespect to L iff its output depends only on the range of its input; that is, iff M (tx ) = M (t̂y )S+for all x, y ∈ N and all texts t, t̂ ∈ L∈L Text(L) provided t+
x = t̂y .
Note that in general one cannot expect to learn set-drivenly. For more information concerning this subject the reader is referred to Lange and Zeugmann [8].

32

L ECTURE 3: M ORE ABOUT L EARNING IN THE L IMIT

Actually, our proof for the learnability of the pattern languages from text was a bit more
complicated than necessary. The solution to the following exercise will establish an easier
proof.
Exercise 10. Let C ∈ IC such that C has finite thickness. Then C ∈ CLimTxt.
Of course, the next issue one should study is the complexity of learning the patternlanguages. Unfortunately, due to the lack of time, we have to skip this issue. Instead, wetake a short look at another branch of learning in the limit, i.e., function learning.
3.3.

Learning Recursive Functions

Next, we want to adapt our model to function learning. Here, the objects to be learned
are classes U of recursive functions. Following a general convention in recursion theory,by recursive functions we usually mean the total recursive functions synonymously called
general recursive functions.
The source of information are then growing sequences of the graph of the target function,i.e.,h(x0 , f (x0 )), (x1 , f (x1 )), (x2 , f (x2 )), . . .i
where we require {xn | n ∈ N} = N.
As hypothesis space we can choose all programs in a universal programming language(e.g. JAVA), or more formally natural numbers which are then interpreted as encodings ofsuch programs (recall a universal Turing machine, a universal RAM, . . . ). Alternatively, we
can also use any restricted programming language as long as we can we can write at least
one program for every function to be learned. Below, we shall formalize this idea by thenotion of numbering.
The sequence of all computed hypotheses has then to converge to a correct program forthe target function f .
Figure 3.1 displays the basic features of the function learning in the limit model.
Description at time t:OutIn

ht ←− M ←− h(xt , f (xt )), . . . , (x0 , f (x0 ))i
M learns successfully in this model iff there is a point T such that hT is correct for
f and hT = hT +1 = hT +2 = hT +3 = . . . .
Figure 3.1: Function Learning in the Limit

In order to arrive at a formal definition, some more notations are needed. We denotethe set of all finite sequences of natural numbers by N∗ . The classes of all partial recursive

L EARNING R ECURSIVE F UNCTIONS

33

and recursive functions of one, and two arguments over N are denoted by P, P 2 , R, andR2 , respectively. R0,1 denotes the set of all 0 − 1 valued recursive functions. Sometimes
it will be suitable to identify a recursive function with the sequence of its values, e.g., let
α = (a0 , ..., ak ) ∈ N∗ , j ∈ N, and p ∈ R0,1 ; then we write αjp to denote the function ffor which f (x) = ax , if x ≤ k, f (k + 1) = j, and f (x) = p(x − k − 2), if x ≥ k + 2.
Any function ψ ∈ P 2 is called a numbering. Moreover, let ψ ∈ P 2 , then we write ψiinstead of λxψ(i, x) and set Pψ = {ψi i ∈ N} as well as Rψ = Pψ ∩ R. Consequently,
if f ∈ Pψ , then there is a number i such that f = ψi . If f ∈ P and i ∈ N are suchthat ψi = f , then i is called a ψ–program for f . A numbering ϕ ∈ P 2 is called a Gödelnumbering (cf. Rogers [11]) iff Pϕ = P, and for any numbering ψ ∈ P 2 , there is a c ∈ Rsuch that ψi = ϕc(i) for all i ∈ N. Göd denotes the set of all Gödel numberings.
Using a fixed encoding h. . .i of N∗ onto N we write f n instead of h(f (0), . . . , f (n))i,for any n ∈ N, f ∈ R. Furthermore, the set of all permutations of N is denoted by Π(N).
Any element X ∈ Π(N) can be represented by a unique sequence (xn )n∈N that contains
each natural number precisely ones. Let X ∈ Π(N), f ∈ P and n ∈ N. Then we write f X,ninstead of h(x0 , f (x0 ), . . . , xn , f (xn ))i provided f (xk ) is defined for all k ≤ n. Finally, asequence (jn )j∈N of natural numbers is said to converge to the number j iff all but finitely
many numbers of it are equal to j.
Now we are ready to define learning in the limit for functions.
Definition 6 (Gold [5]). Let U ⊆ R and let ψ ∈ P 2 . The class U is said to belearnable in the limit with respect to ψ iff there is an IIM M ∈ P such that for eachfunction f ∈ U and every X ∈ Π(N)(1) for all n ∈ N, M (f X,n ) is defined,(2) there is a j ∈ N such that ψj = f and the sequence (M (f X,n ))n∈N converges to j.
If U is learnable in the limit with respect to ψ by an IIM M , we write U ∈ LIMψarb (M ). LetS
LIMψarb = {U U is learnable in the limit w.r.t. ψ}, and let LIM arb = ψ∈P 2 LIMψarb .
Some remarks are mandatory here. Let us start with the semantics of the hypotheses
produced by an IIM M . If M is defined on input f X,n , then we always interpret the number
M (f X,n ) as a ψ–number. This convention is adopted to all the definitions below.
Furthermore, note that LIMϕarb = LIM arb for every Gödel numbering ϕ. In the above
definition LIM stands for “limit.” Moreover, in accordance with the definition of convergence, only finitely many data of the graph of a function f were available to the IIM M up
to the unknown point of convergence. Therefore, some form of learning must have takenplace. Thus, the use of the term “learn” in the above definition is indeed justified.
Moreover, the arb in LIM arb points to the requirement to learn from arbitrary input.
That is, within Definition 6 we make no assumptions concerning the order in which input
data should be presented.
For the sake of illustration, let us look at the following example. Consider the class U of
all polynomials of one variable with coefficients from N. For constructing an appropriate

34

L ECTURE 3: M ORE ABOUT L EARNING IN THE L IMIT

hypothesis space ψ we can proceed by canonically enumerating for d = 0, 1, 2, . . . thefinite number of (d + 1) tuples of natural numbers in the range [0, d] and using them as thecoefficients of 1, x, x2 , . . . , xd . One such enumeration begins
0, 1 + x, x, 0, 1
2 + 2x + 2x2 , 2 + 2x + x2 , . . .
Then, one could learn the class U of all polynomials of one variable with coefficientsfrom N by using again the identification by enumeration principle. But there is anothermethod which is much more efficient (though not universally faster).
On inputh(x0 , f (x0 )), (x1 , f (x1 )), . . . , (xt , f (xt ))ione simply outputs the canonical index of the Lagrangian interpolation polynomial, i.e.,pt (x) =tXi=0f (xi )tYx − xkk=0
k6=ixi − xk

The fundamental theorem of algebra implies convergence.
Note that in the literature you will quite often find the following definition for learningin the limit for functions.
Definition 7 (Gold [5]). Let U ⊆ R and let ψ ∈ P 2 . The class U is said to belearnable in the limit with respect to ψ iff there is an IIM M ∈ P such that for eachfunction f ∈ U ,(1) for all n ∈ N, M (f n ) is defined,(2) there is a j ∈ N such that ψj = f and the sequence (M (f n ))n∈N converges to j.
If U is learnable in the limit with respect to ψ by an IIM M , we write U ∈ LIMψ (M ). LetS
LIMψ = {U U is learnable in the limit w.r.t. ψ}, and let LIM = ψ∈P 2 LIMψ .
The difference between Definitions 6 and 7 is that Definition 7 assumes the graph of thefunction to be presented in natural order while Definition 6 does not make any assumption
concerning the order in which the graph is presented. However, it is quite easy to show that
LIM = LIM arb (cf., e.g., Jantke and Beick [7]).
3.4.

Points of Concern

Next, we address some fundamental remarks concerning the definition of learning in thelimit. These remarks apply to both learning languages and functions.
Our learning model is not satisfactory with respect to the following points of concern.
– The limit learner has access to the whole initial segment of the data sequence provided.

C ONSISTENCY

35– The limit learner is only supposed to converge but one never knows whether or not it
already did so.
– We have not incorporated any complexity requirement. So, what is the right measureof complexity to be used here?
We shall address all these points in this and later lectures. Let us start with the problem
to define an appropriate measure of complexity for learning in the limit.
The first complexity measure we will consider is the mind change complexity. A
mind change occurs if
M (dj ) 6= M (dj+1 ) , where d is a text or an informant ,M (f n ) 6= M (f n+1 ) , where f is a recursive function .
Clearly, this measure is closely related to the number of prediction errors. Both complexity
measures say little about the total amount of data and time needed until a concept is guessed
correctly.
Therefore, one has also proposed to study the update-time. By update-time we mean
the time needed by a learner to compute its new hypothesis from the actual input. We
measure this time as a function of the length of the input. But this measure also has a serious
drawback. That is, one can always achieve linear update-time if no extra requirements are
made to the hypotheses. We leave it as an exercise to prove this statement formally.
3.5.

Consistency

In order to deal with this problem, the actual hypotheses are often required to be consistent. Intuitively speaking, a hypothesis is consistent if and only if all information obtainedso far about the unknown object is completely and correctly encoded in this hypothesis.
Otherwise, a hypothesis is said to be inconsistent. Consistency seems to be a very naturalrequirement. If we look at function learning then the function g computed by an inconsistent hypothesis produced on input f X,n has the following property. There must be an xi ,i ≤ n such that g(xi ) 6= f (xi ). Note that there are two possible reasons for g to differ
from f on argument xi ; namely, g(xi ) may be not defined, or the value g(xi ) is defined anddoes not equal f (xi ). Hence, if a hypothesis is inconsistent then it is not only wrong but itis wrong on an argument for which the IIM does already know the correct value. At firstglance we are tempted to totally exclude IIMs producing inconsistent hypotheses from ourconsiderations. It might seem that consistent IIMs, i.e., IIMs that produce always consistenthypotheses, are the only reasonable learning devices.
Surprisingly enough this is a misleading impression. As it turns out, in a sense learning
seems to be the art of knowing what to overlook. Since this phenomenon is of fundamental
importance, we shall deal with it in some more detail here. Interestingly enough, there arealso different ways to define consistency and these different definitions will also provide
some surprises. We start our investigations of consistent learning within the setting offunction learning.

36

L ECTURE 3: M ORE ABOUT L EARNING IN THE L IMIT

Next we formally define different models of consistent learning.
Definition 8 (Barzdin [2]). Let U ⊆ R and let ψ ∈ P 2 . The class U is called consistently learnable in the limit with respect to ψ iff there is an IIM M ∈ P such that
(1) U ∈ LIMψ (M ),(2) ψS(f n ) (x) = f (x) for all f ∈ U , n ∈ N and x ≤ n.
CONSψ (M ), CONSψ and CONS are defined analogously as above.
Intuitively, a consistent IIM does correctly reflect all the data it has already seen. If an
IIM does not always work consistently, we call it inconsistent.
Next, we add a requirement to the definition of the learning type CONSψ that is often implicitly assumed in applications, namely, that the strategy is defined on every input,
cf. Michalski et al. [9,10].
Definition 9 (Jantke and Beick [7]). Let U ⊆ R and let ψ ∈ P 2 . The class U is called
R–consistently learnable in the limit with respect to ψ iff there is an IIM M ∈ R suchthat U ∈ CONSψ (M ).
R-CONSψ (M ), R-CONSψ and R-CONS are defined analogously as above.
The latter definition has a peculiarity that should be mentioned. Although the strategy isrequired to be recursive, consistency is only demanded for inputs that correspond to somefunction f from the class to be learned. With the next definition we model the scenario
in which consistency is required on all inputs. In order to distinguish the resulting learning type from the latter defined one, we use the prefix T . Informally, T points to total
consistency.
Definition 10 (Wiehagen and Liepe [16). Let U ⊆ R and let ψ ∈ P 2 . The class
U is called T –consistently learnable in the limit with respect to ψ iff there is an IIM
M ∈ R such that
(1) U ∈ CONSψ (M ),(2) ψS(f n ) (x) = f (x) for all f ∈ R, n ∈ N and x ≤ n.
T -CONSψ (S ), T -CONSψ and T -CONS are defined in the same way as above.
Finally, looking at potential applications it is often highly desirable to make no assumptions concerning the order in which input data should be presented. Therefore, we sharpen
Definitions 8 through 10 by additionally demanding an IIM to behave consistently independently of the order of the input.
Definition 11 (Blum and Blum [4]). Let U ⊆ R and let ψ ∈ P 2 . U ∈ T -CONSψarb
iff there is an IIM S ∈ R such that(1) for all f ∈ U and every X ∈ Π(N), there is a j ∈ N such that ψj = f , and(M (f X,n ))n∈N converges to j,

C ONSISTENCY37(2) ψM (f X,n ) (xm ) = f (xm ) for every permutation X ∈ Π(N), f ∈ R, n ∈ N, andm ≤ n.
T -CONSψarb (M ) as well as T -CONS arb are defined in analogy to the above.
Furthermore, appropriately incorporating the requirement to learn from arbitrary input directly yields the learning types CONS arb , and R-CONS arb . Therefore, the formal definition of these learning models is omitted here. Note that for all learning types
LT ∈ {T -CONS , T -CONS arb , R-CONS , R-CONS arb , CONS , CONS arb } we haveLTϕ = LT for every Gödel numbering ϕ.
In the following we aim to compare the learning power of the different models of consistent learning to one another as well as to learning in the limit. Note that in the following⊆ denotes subset and ⊂ denotes proper subset. Finally, incomparability of sets is denotedby #.
As already mentioned, in machine learning it is often assumed that learning algorithms
are defined on all inputs. On the one hand, this requirement is partially justified by aresult of Gold [5]. He proved that learning in the limit is insensitive with respect to therequirement to learn exclusively with recursive IIMs, i.e., if U ∈ LIM (M ), then there isan IIM M̂ ∈ R such that U ∈ LIM (M̂ ). One the other hand, consistency is a common
requirement in machine learning. Therefore, it is natural to ask whether or not the powerof consistent learning algorithms further decreases if one restricts itself to recursive IIMs.
The answer to this question is provided by our next theorem.
Theorem 3.8.

T -CONS ⊂ R-CONS ⊂ CONS .

Proof. By definition, T -CONS ⊆ R-CONS ⊆ CONS . In order to show R-CONS \f ∈ R, ϕf (0) = f } where ϕ ∈ Göd. Obviously, U ∈T -CONS 6= ∅, let U = {fnR-CONSϕ (M ) by the IIM M (f ) = f (0) for all n ∈ N .
Now assume that U ∈ T -CONSϕ (M ) for some IIM M . Hence, by Definition 10,
M ∈ R and ϕM (f n ) (x) = f (x) for every f ∈ R, n ∈ N and x ≤ n. By an implicit use of
the Recursion Theorem, let f = ϕi be the following function.
f (0) = i,0, if M (f n 0) 6= M (f n )f (n + 1) =1, if M (f n 0) = M (f n ) and M (f n 1) 6= M (f n ).
Clearly, f ∈ U (note that one of the two cases in the definition of f must happen
for all n ≥ 1). On the other hand, M (f n ) 6= M (f n+1 ) for all n ∈ N, contradicting
U ∈ T -CONSϕ (M ). Hence U 6∈ T -CONS . This completes the proof of T -CONS ⊂R-CONS .
The proof of CONS \ R-CONS 6= ∅ can be done by using a class similar to the classabove, namely
U = {f f ∈ R, either ϕf (0) = f or ϕf (1) = f } .
Next, we show that U ∈ CONS . The wanted IIM M is defined as follows. Let f ∈ R andn ∈ N.

38

L ECTURE 3: M ORE ABOUT L EARNING IN THE L IMITM (f n ) = “Compute in parallel ϕf (0) (x) and ϕf (1) (x) for all x ≤ n until (A) or (B) happens.
(A) ϕf (0) (x) = f (x) for all x ≤ n.
(B) ϕf (1) (x) = f (x) for all x ≤ n.
If (A) happens first, then output f (0). If (B) happens first, then output f (1). If neither(A) nor (B) happens, then M (f n ) is not defined.”
By the definition of U , it is obvious that M (f n ) is defined for all f ∈ U and all n ∈ N.
Moreover, M is clearly consistent. Hence, it suffices to prove that (M (f n ))n∈N converges
for all f ∈ U . But this is also an immediate consequence of the definition of U , since either
ϕf (0) 6= f or ϕf (1) 6= f . Hence M cannot oscillate infinitely often between f (0) and f (1).
Consequently, U ∈ CONSϕ (M ).
Now, it is intuitively clear that U ∈/ R-CONS . The formal proof is done by using
Smullyan’s Recursion Theorem. We refer the interested reader to Wiehagen and Zeugmann [18].
Next, consider
U1 = {f ∈ R | ϕf (0) = f and f (x) > 0 for all x} ,U2 = {f ∈ R | ϕf (0) = f } , andU0 = {f ∈ R | f (x) = 0 for almost all x} .
Then, it is not hard to verify that U1 , U2 , U0 ∈ LIM . Moreover, using similar ideas asabove one can easily show the following exercise.
Exercise 11. U1 ∪ U0 ∈ LIM \ CONS .
Moreover, again using similar ideas it is not hard to see that the following theorem holds.
Theorem 3.9 (Barzdin [2]). U2 ∪ U0 ∈/ LIM .
The latter theorem directly implies that R ∈/ LIM . Therefore, the property of a function
class U to be learnable is not trivial. Furthermore, Theorem 3.9 also shows that it is notalways possible to combine two learners into a more powerful one. So, it is only natural to
ask whether or not the different consistent learning types LT are closed under union. Here,by closure under union we mean that for all classes U, V ∈ LT we also have U ∪ V ∈ LT .
The answer is provided by the following theorem.
Theorem 3.10.
(1) CONS , CONS arb , R-CONS and R-CONS arb are not closed under finite union.
(2) T -CONS and T -CONS arb are closed under recursively enumerable union.

C ONSISTENCY

39

Proof. For showing Assertion (1) we can use the classes U0 and U2 defined above. After a
bit of reflection, one easily sees that U0 , U2 ∈ R-CONS arb . Hence, we also have U0 , U2 ∈R-CONS as well as U0 , U2 ∈ CONS arb and U0 , U2 ∈ CONS . But by Theorem 3.9 wealready know U0 ∪ U2 ∈/ LIM .
In order to prove (2), we restate this assertion more formally. Let (Mi )i∈N be a recursive
enumeration of T –consistent IIMs. Then there exists an IIM M such that T -CONS (M ) =Si∈N T -CONS (Mi ).
Without loss of generality, we may assume that all the IIMs Mi output as hypotheses
programs in some fixed Gödel numbering ϕ. Let f ∈ R. Then two cases are possible.
Either there is an IIM Mi that learns f or all IIMs fail to learn it. However, in the lattercase each of the IIMs Mi has to change its mind infinitely often. On the other hand, if f islearned by some Mi then at least one IIM stabilizes its output. The wanted IIM M searches
for an enumerated machine that might learn f as follows.
The IIM M dovetails the computation of more and more outputs of the enumerated
IIMs. For each IIM Mi that is already included in its dovetailed computations, it counts
the number of equal outputs. This number is called weight. As long as an IIM repeats its
actual guess on the next input, the weight increments. If an IIM performs a mind change,
its weight reduces to zero. After having read the initial segment f k of the function f the
IIM M favors from the first k + 1 IIMs M0 , . . . , Mk that one which actually has the greatest
weight. In case there are two IIMs Mi and Mj taking the greatest weight the IIM M choosesthat one having the smallest index.
We formally define M as follows. Let f ∈ R, and let k ∈ N.
M (f k ) = “Compute in parallel
M0 (f 0 ), . . . , M0 (f k ),M1 (f 0 ), . . . , M1 (f k ),–––Mk (f 0 ), . . . , Mk (f k ),and assign to each IIM Mi , i ≤ k, its weight, i.e., the greatest number m ≤ k − isatisfying the condition that Mi (f k−i−m ) = Mi (f k−i−m+1 ) = · · · = Mi (f k−i ). Notethat we calculate the weights in a triangular fashion. This is necessary in order toachieve convergence of M . Choose w(k) to be the smallest i ≤ k such that the IIM
Mi has the greatest weight.
In case all considered IIMs have weight zero, output a ϕ–program of f (0) · · · f (k)0∞ .
If w(k) = w(k − 1), then output Mw(k) (f k ). Otherwise, output a ϕ–program off (0) · · · f (k)0∞ that is different from M (f k−1 ).”40

L ECTURE 3: M ORE ABOUT L EARNING IN THE L IMITS
It remains to show that T -CONSϕ (M ) = i∈N T -CONSϕ (Mi ). Obviously, M is consistent on any initial segment it is fed, since all of the IIMs Mi , i ∈ N, do so. Now, let
f ∈ R and suppose that f is learned by some IIM Mi . Consequently, there exists numbers
j, n0 such that Mi (f n ) = j for all n ≥ n0 , and ϕj = f . Hence, for any IIM that learns
f its weight increases after some point in each step of M ’s computation. Therefore, for all
but finitely many k the IIM M must favor exactly one of the IIMs Mi that learns f and,after some point, M outputs always Mi (f k ). Note that the computation of weights in atriangular fashion really ensures the desired convergence, since any new IIM included in
M ’s computation initially gets weight zero.
On the other hand, if none of the IIMs Mi , i ∈ N, learns f , then each IIM Mi has toperform infinitely many mind changes. This is ensured by our assumption that each Mi is
T –consistent. Hence, the case w(k) 6= w(k−1) occurs infinitely often. But each occurrenceof this case forces M to perform a mind change. Consequently, M cannot converge.
So far we have seen that the requirement to learn consistently may have serious consequences including the loss of learnability at all. Next, we outline that the requirement tolearn consistently may also seriously affect the complexity of learning. For doing this, welook again at the pattern languages. But this time we investigate their consistent learnability
from informant.
Definition 12. PAT is called consistently learnable in the limit from informant with respect to Pat (abbr. PAT ∈ CONS -INF ) iff there is an IIM M such that
(1) PAT ∈ LimInf w.r.t. Pat by M ,nn−(2) for all L ∈ PAT , i ∈ info(L) and n ∈ N, i+n ⊆ L(M (i )) and in ∩ L(M (i )) = ∅.

We add Poly if the time to compute M (in ) ≤ pol(length(in )), where pol is a fixedpolynomial.
Then, one can prove the following (cf. Wiehagen and Zeugmann [17]). Note that P
stands here for the set of all languages acceptable in deterministic polynomial time andN P denotes the set of all languages acceptable in nondeterministic polynomial time.
Theorem 3.11.
(1) PAT ∈ CONS -INF .
(2) PAT ∈/ Poly-CONS -INF , provided P =6 N P.
(3) PAT ∈ Poly-LimInf .
Summarizing, we may conclude the following interpretation.
If it comes to “reasonable” ideas, it is not a good a idea to trust the common sense.
Now, let us return to the problem of defining an appropriate measure of complexity forlearning in the limit.

T OTAL L EARNING T IME

3.6.

41

Total Learning TimeSo, as we have seen, it is not a good idea to introduce “natural” requirements such as
consistency. Instead, we shall study the total amount of data and time needed by a learner
until convergence.

The Total Learning Time                                                                          s0  $# $#    $#$# $#$# &%% &%%    $# $# &&% &&%      "! "! $#$# $#$# &%% &%%      "! "! $# $# &&% &&%      "!!" "!!" $##$ $##$ &%&% &%&%
      "!"! "!"! $#$# $#$# &%&% &%&%
      "!"! "!"! $#$# $#$# &%&% &%&%      "! "! $# $# &% &%s6('' ('' ('' (''((' ((' ((' ((' displays thetotal learning times
1070
stage of convergence

The learners’s behavior on input sequence 1

0/0/ 0/0/ 2121 2121 4343 4343 6565 6565 8787 8787.
.
+,+ +,+ .- .- /0 /0 12 12 34 34 56 56 78 78*)*) *)*) ,+, ,+, .-.- .-.- 0/0/ 0/0/ 2121 2121 4343 4343 6565 6565 8787 8787
s
0

 

:9:9 :9:9 <;<; <;<; >=>= >=>= @?@? @?@? BABA BABA DCDC DCDC FEFE FEFE HGHG HGHG
9:9 9:9 ;<; ;<; =>= =>= ?@? ?@? ABA ABA CDC CDC EFE EFE GHG GHG::9 ::9 <<; <<; >>= >>= @@? @@? BBA BBA DDC DDC FFE FFE HHG HHG

s
8

s
12987
stage of convergence

The learner’s behavior on input sequence 2
Figure 3.2: The total learning time
We define the total learning time as follows. Let M be any IIM that learns a concept
class C in the limit. Then, for c ∈ C and a text or informant d for c, letConv(M, d) =df the least number i ∈ N+ such that for all j ≥ i, M (dj ) = M (di )denote the stage of convergence of M on d. Moreover, by TM (dj ) we denote thenumber of steps to compute M (dj ). We measure this quantity as a function of the length of
the input and refer to it as the update time. Finally, the total learning time taken by the
IIM M on a sequence d is defined as
Conv (M,d)

T T (M, d) =df

X
j=1

TM (dj ) .

42

L ECTURE 3: M ORE ABOUT L EARNING IN THE L IMIT

Given a probability distribution D on the data sequences d, we like to evaluate the expectation of T T (M, d) with respect to D, the average total learning time.
Figure 3.11 displays the total learning time on different input sequences as the measure
under the curve until the stage of convergence happened. Looking at Figure 3.11 we see thefollowing. On different input sequences the amount of data needed until convergence may
considerably vary.
Still, there is a problem. What one usually likes to have is a learner that has a polynomial
total learning time. This could be easily said, however, we have to specify what is reallymeant, i.e., polynomial in what? Thus, the crucial point is the right definition of the problem
size. If one takes the sum of the length of all elements seen until convergence (and possibly
the length of target concept as additional parameter) then a learner could simply delay
convergence until sufficiently long examples have been appeared. On the other hand, if wetake the length of the shortest hypothesis describing the target concept as problem size then
the total learning time is usually unbounded in the worst-case. This is caused by the fact thatthe learner has to learn from all data sequences. Thus, taking a data sequence containing
as many repetitions as necessary of elements that do not suffice to learn the target, every
bound can be exceeded. See for example the learner’s behavior on input sequence 2 below.
On the other hand, such worst-case data sequences may be rare in practice if they occur
at all. Consequently, in order to arrive at a complexity measure that has much more practicalvalue than a worst-case analysis, one has to study the average-case behavior of a learner.
So, in the next lecture, we shall explain what an average-case analysis is by using a much
simpler example than learning in the limit.

References[1] D. A NGLUIN (1980), Finding patterns common to a set of strings, Journal of Computer and System Sciences 21, 46 – 62.
[2] J. BARZDIN (1974a), Inductive inference of automata, functions and programs, in“Proceedings International Congress of Math.,” Vancouver, pp. 455 – 460.
[3] D.R. B EAN , A. E HRENFEUCHT, AND G.F. M C N ULTY (1979), Avoidable patterns
in strings of symbols, Pacific J. of Mathematics 85, Vol. 2, 261 – 294.
[4] L. B LUM AND M. B LUM (1975), Toward a mathematical theory of inductive inference, Information and Control 28, 122 – 155.
[5] E.M. G OLD (1965), Limiting recursion, Journal of Symbolic Logic 30, 28 – 48.
[6] J.E. H OPCROFT AND J.D. U LLMAN (1969), Formal Languages and their Relation
to Automata, Addison-Wesley, Reading, Massachusetts.
[7] K.P. JANTKE AND H.R. B EICK (1981), Combining postulates of naturalness in inductive inference, Journal of Information Processing and Cybernetics (EIK) 8/9, 465– 484.

T OTAL L EARNING T IME

43[8] S. L ANGE AND T. Z EUGMANN (1996), Set-driven and rearrangement-independent
learning of recursive languages, Mathematical Systems Theory 29, No. 6, 599 – 634.
[9] R.S. M ICHALSKI , J.G. C ARBONELL , AND T.M. M ITCHELL (1984), “Machine
Learning, An Artificial Intelligence Approach,” Vol. 1, Springer-Verlag, Berlin.
[10] R.S. M ICHALSKI , J.G. C ARBONELL , AND T.M. M ITCHELL (1986), “Machine
Learning, An Artificial Intelligence Approach,” Vol. 2, Morgan Kaufmann Publishers
Inc., San Mateo.
[11] H.J R . ROGERS (1967), “Theory of Recursive Functions and Effective Computability,” McGraw–Hill, New York.
[12] A. S ALOMAA (1994), Patterns, (The Formal Language Theory Column). EATCS
Bulletin 54, 46 – 62.
[13] A. S ALOMAA (1994), Return to patterns (The Formal Language Theory Column),
EATCS Bulletin 55, 144 – 157.
[14] T. S HINOHARA AND S. A RIKAWA (1995), Pattern inference, in “Algorithmic Learning for Knowledge-Based Systems” (K.P. Jantke and S. Lange, eds.), Lecture Notes
in Artificial Intelligence 961, pp. 259 – 291, Springer-Verlag, Berlin.
[15] A. T HUE (1906), Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat.
Nat. Kl., Christiana No. 7, 1 – 22.
[16] R. W IEHAGEN AND W. L IEPE (1976), Charakteristische Eigenschaften von erkennbaren Klassen rekursiver Funktionen, Journal of Information Processing and Cybernetics (EIK) 12, 421 – 438.
[17] R. W IEHAGEN AND T. Z EUGMANN (1994), Ignoring data may be the only way tolearn efficiently, Journal of Theoretical and Experimental Artificial Intelligence 6,
131 – 144.
[18] R. W IEHAGEN AND T. Z EUGMANN (1995), Learning and Consistency, in “Algorithmic Learning for Knowledge-Based Systems” (K.P. Jantke and S. Lange, eds.),
Lecture Notes in Artificial Intelligence 961, pp. 1 – 24, Springer-Verlag, Berlin.

45

L ECTURE 4: AVERAGE -C ASE C OMPLEXITY
Within this lecture we exemplify the task to perform an average-case analysis of thecomplexity of a particular algorithm. When dealing with data mining, usually huge data
sets have to be analyzed. Thus, an excellent average-case behavior is often more important
than a good worst-case time complexity. However, performing an average-case analysisof the complexity of a given algorithm is often much more complicated than analyzing its
worst-case complexity. Due to the lack of time, therefore we shall often omit such averagecase studies throughout this course.
Before we can perform any average-case analysis, we have to understand what averagecase analysis is all about. For reaching this goal, we use this lecture to provide some easy
examples.
4.1.

Introductory Examples

We start with a very simple question. Let us assume all five digit numbers are equally
likely including 00000 (that is we also allow leading zeros). Now, we want to add 1 to sucha number. The question is
How many digits will be changed?
In the best-case, the last digit is not 9, and we have to change just one digit, i.e., the lastone.
In the worst-case, the number is 99999 and we have to change 6 digits, since
99999 + 1 = 100000
Now, we are interested in the expected number of digits that will be changed. Sayingthat all five digit numbers are equally likely is equivalent to the following. We chooseeach digit independently of the other digits and the probability to choose a digit from{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} is 1/10.
So, with probability 9/10 we do not choose 9 to be the last digit. That is, with probability
9/10 we only have to change the last digit.
What can be said about the probability that we have to change exactly two digits? This
event will happen if and only if the last digit is 9 and the second digit (from the right) is not
9. Furthermore, the probability for the last digit to be 9 is 1/10 and the probability for thesecond digit to be not 9 is 9/10. Thus, the probability to change exactly two digits is
9
1 9
·
=
.
10 10
100
For seeing the general pattern, we also calculate the probability that we have to change
exactly 3 digits. This event will happen if and only if the last digit is 9, the second digit is
9 and the third digit is not 9. Thus, the probability to change exactly three digits is
1 1 9
9
·
·
=
.
10 10 101000

46

L ECTURE 4: AVERAGE -C ASE C OMPLEXITY

Analogously, the probability to change exactly 4 digits is 9/104 and the probability tochange exactly 5 digits is 9/105 . Additionally, we need the probability to change exactly 6
digits. As shown above, this event will happen if the number is 99999, i.e., with probability
1/105 .
For completing our analysis, let R denote the random variable telling us how many digits
we have to change. Thus, R can take the values 1, 2, 3, 4, 5, 6. The formula for computing
the expection is
6
X
E[R] =
x · Pr(R = x) .
x=1

Thus, the expected number of digits to be changed is
E[R] =

5
X

x·

x=1

6
9
+ 5 = 1, 11111 .
x
10
10

Next, we look at the more general case of having an n digit number, where n ∈ N,n ≥ 1. Now, we denote the random variable by Rn and obviously the range of Rn is the set{1, . . . , n, n + 1}. Clearly, then we get
E[R] =

n
X
x=1

x·

n+1
9
+
10x
10n

(4.1)

How can we calculate the sum on the right hand side? Let us start from something weknow, i.e., the finite geometrical series. That is, we take into account thatf (q) =

n
X

qx =

x=0

1 − q n+1,
1−q

for all q 6= 1 .

Now, taking derivatives on both sides yields
0f (q) =nX

xq x−1 =x=0

1 − (n + 1)q n + nq n+1,(1 − q)2

q 6= 1 .

Consequently, we arrive atnX

xq x =

x=0

q − (n + 1)q n+1 + nq n+2,(1 − q)2

q 6= 1 .

This allows us to rewrite the expectation in (4.1) as follows.
 x
n
X
1
n+1
E[R] = 9 ·
+
x·
10
10n
x=1
(1/10) − (n + 1)(1/10)n+1 + n(1/10)n+2 n + 1+(1 − (1/10))2
10n
10
1
=
−
.
9
9 · 10n= 9·

A NALYZING THE C OMMON A LGORITHM FOR F INDING THE M AXIMUM

47

Thus, as n tends to infinity, the expected number of digits to be changed if you add 1 toan n digit number in decimal notation chosen uniformly at random is 10/9. So, this is very
close to the best-case (just one digit) and far from the worst case of n + 1 digits.
Exercise 12. Compute the expected number of bits to be changed if you add 1 to an n
bit number chosen uniformly at random.
4.2.

Analyzing the Common Algorithm for Finding the Maximum

Let us consider the following well-known algorithm for finding the maximum in a listof elements.
Algorithm Max
Input: n elements X[1], X[2], . . . , X[n] of a totally ordered set.
Output: Numbers m and j such that m = X[j] = max{X[k] 1 ≤ k ≤ n}.
Method:A1. (Initialize) j := n, k := n, m := X[n]A2. (All tested ?) Test whether k = 0.
If it is, output j, m, and stop.
Otherwise, execute A3.
A3. (Compare) If X[k] ≤ m, goto A5.
Otherwise, execute A4.
A4. (Change m) j := k, m := X[k]A5. (Decrease k) k := k − 1, goto A2.
Algorithm Max requires a fixed amount of storage. So, we shall analyze the timerequired to perform it. For doing this, we count the number of times each step is executed.
This is done Figure 4.1 below.
Instruction
A1
A2
A3
A4
A5

Number of executions
1
n
n−1
A
n−1

Figure 4.1: Counting the number of executions of A1 through A5Everything is clear except the quantity A. Therefore, we study the quantity A, only.
Before looking at the expectation of A, we look at the minimum and maximum of it.

48

L ECTURE 4: AVERAGE -C ASE C OMPLEXITY(1) The minimum value of A is zero; this happens iff X[n] = max{X[k] 1 ≤ k ≤ n}.
(2) The maximum value of A is n − 1; this happens iff X[1] > X[2] > · · · > X[n].
Thus, the best-case and worst-case behavior of Algorithm Max are clear and triviallyto obtain. But what can be said about the average?
To answer this question, we need to define what we mean by average. For doing that, wemust make some assumptions about the expected characteristics of the input data. Theseassumptions are:
(1) All X[k] are pairwise distinct.
(2) Without loss of generality we can assume that {1, 2, . . . , n} is the the range of the
input data.
(3) We assume all possible n! permutations of the input data {1, 2, . . . , n} to be equally
likely.
In particular, we made Assumption (3), since we do not have any reason here to assign
different probabilities to the different possible permutations. When dealing with particular
input data sets, things may change, however. In such cases one has to figure out the underlying probability distribution of the inputs. But for our goal and in many applications
Assumption (3) is reasonable.
Next, we introduce some notations. By pnk we denote the probability that A has value k.
Using the classical definition of probability, we can thus write
pnk =number of permutations of {1, 2, . . . , n} for which A = k.
n!

Then, the average (mean) value is defined by
E[A] = An =X

kpnk .

kMoreover, the variance Vn is defined as
X
X
Vn = E[(A − An )2 ] =(k − An )2 pnk =k 2 pnk − A2n .
kFurthermore, the standard deviation σn is defined to becompute An , Vn and σn . But how can we do this?

k√Vn . Thus, all we have to do is toApproach 1. Determine pnk .
1n−1
Claim 1. pnk = · p(n−1)(k−1) +· p(n−1)k , where p1k = δ0k , and pnk = 0 ifnn
k < 0.
Proof. If x1 = n, then the value of A is one higher than the value of A obtainedon {x2 , . . . , xn }. Moreover, if x1 6= n, then the value of A is the same as its value on{x2 , . . . , xn }.

A NALYZING THE C OMMON A LGORITHM FOR F INDING THE M AXIMUM

49

But how can we proceed? There is a very powerful tool, called generating functions
which seems appropriate to be used here. Therefore, we shortly recall the definition ofgenerating functions and an important theorem from calculus.
Let (an )n∈N be any sequence of real (or complex) numbers. Theng(z) =∞
X

an z nn=0

is called generating function of (an )n∈N . The following theorem is often applied togenerating functions.
Theorem 4.1. Let (an )n∈N and (bn )n∈N be any sequences such that their generating
functions have a radius r > 0 of convergence. Then∞X

an z n =n=0∞
Xbn z nn=0

iff an = bn for all n ∈ N.
Moreover, recall that power series can be differentiated by differentiating their summands. Thus, we also know thatg 0 (z) =∞Xn · an z n−1 .

n=0

For more information about generating functions the interested reader is referred to Graham, Knuth, and Patashnik [1]. Furthermore, you should consult my Additional Notes on
Counting and Probability which are available at
http://www-alg.ist.hokudai.ac.jp/ thomas/TCSTRB/tcstr 05 2/tcstr 05 2.ps.gz
So, let us try to apply generating functions for computing the pnk . We considerX
Gn (z) =pnk z k .
k≥0

In fact, Gn is even a polynomial but due to the convention made in Claim 1, we can write
it as a power series, which is technically more convenient for our purposes. Also, note that
G1 (z) = 1. Then, we obtain

X
X1
n−1
k
· p(n−1)(k−1) +· p(n−1)k · z kGn (z) =pnk z =
n
n
k≥0
k≥0
=

n−1X
zX
p(n−1)(k−1) z k−1 +p(n−1)k z k
n k≥0
n k≥0

=

z
n−1
z+n−1
Gn−1 (z) +Gn−1 (z) =Gn−1 (z) .
n
n
n

50

L ECTURE 4: AVERAGE -C ASE C OMPLEXITY

Hence, we arrive at
n−1
n−1
Y
1
1 Y
(z + n − i) =(z + n − i)Gn (z) =n! i=1(z + n)n! i=0




1
z+n
1
z+n
=
· n!
=
(z + n)n!
nz+nnThus, we have found a closed formula for Gn . Using Stirling numbers of the first kind∗ ,we get
n
n−1
n h i
Y
Y
X
n k
(z + n − i) =(z + i) =
z ,
k
i=0
i=0
k=1

and hence, we can concludenn
1 X hni k
1Y(z + n − i) =z(z + n − i) =z i=0
z k=1 k
i=0

n−1
Y

=

n h i
X
n

k

k=1

z

k−1

X n 
=
zk .
k
+
1
k≥0

Consequently, we can apply Theorem 4.1 and getn−1
X  1  n 
1 Y
(z + n − i) =zk ,Gn (z) =n! i=0
n!
k
+
1
k≥0

and therefore



n
1
.
pnk =
n! k + 1

However, it is not easy to compute An by using the formula just obtained. You are strongly
advised to try it as an exercise. We shall provide here an easier and even more general
method. Consider
X
G(z) =
qk z k ,k≥0where the qk are probabilities. Then
G(1) =

X

qk = 1 ,k≥0

and moreover
G0 (1) =X

kqk = E[G] .

k≥0

Analogously, one easily verifies
V (G) = G00 (1) + G0 (1) − (G0 (1))2 .
∗We use here the notation from [1] to denote Stirling numbers of the first kind.

A NALYZING THE C OMMON A LGORITHM FOR F INDING THE M AXIMUM

51

Thus, An = G0n (1) which can be computed as follows. Using the identity
Gn (z) =z+n−1
Gn−1 (z)nderived above, we directly obtain
G0n (z) =z+n−1 01
Gn−1 (z) +Gn−1 (z) .
nnConsequently,
1+ G0n−1 (1)
n
1
1
=
+
+ · · · + G01 (1) .
| {z }n n−1

G0n (1) ==0

P
Therefore, we can rewrite G0n (1) = nk=2 k1 and recalling that the nth Harmonic number isPdefined as Hn = nk=1 k1 we finally get
An = H n − 1 .
Furthermore, taking into account thatZ ndx
= ln n − ln 1 = ln nx1
it is easy to see that ln n < Hn < ln n + 1.
P
(2)
Now, letting Hn = nk=1 k12 and putting it all together, we finally get
V (An ) = Hn − Hn(2) .
Thus, the complete picture concerning A can be written as


q
(2)
A = min : 0, average: Hn − 1, max : n − 1, dev: Hn − Hn.
Hopefully, this easy example has provided you a basic idea of what average-case analysis
is all about and what basic techniques one might apply.

References[1] R.L. G RAHAM , D.E. K NUTH AND O. PATASHNIK (1989), Concrete Mathematics(Addison-Wesley, Reading, Massachusetts).

53

L ECTURE 5: AVERAGE -C ASE A NALYSIS II
Within this lecture, we want to perform an average-case analysis for a small variation of
Algorithm P, synonymously called Wholist Algorithm, introduced in Lecture 2.
Recall that our concept class Cn is the set of all concepts c ⊆ Xn = {0, 1}n describableby a monomial. For the concept class Cn the hypothesis space Hn will be chosen as the setof all monomials over Ln for the learners considered below.
This is a good place to address the issue of our points of concerns that a limit learnerhas always access to the whole initial segment of the data sequence provided. In contrast tothat we next define iterative IIMs.
An iterative IIM is only allowed to use its last guess and the next element in the data
presentation of the target concept for computing its actual guess. Conceptionally, an iterative IIM M defines a sequence (Mn )n∈N of machines each of which takes as its input theoutput of its predecessor. We use data(c) to denote the set of all data sequences for c. In
order to avoid misunderstandings it should be recalled that data sequences are either texts
or informants. Furthermore, if d = (dj )j∈N ∈ data(c) is any data sequence, then we use
here dj to denote the jth entry of it.
Definition 13 (Wiehagen [2]). Let C be a concept class, let c be a concept, and let
H = (hj )j∈N be a hypothesis space. An IIM M IT-infers c from data sequenced with respect to H iff for every d = (dj )j∈N ∈ data(c) the following conditions are
satisfied:(1) for all n ∈ N, Mn (d) is defined, where M0 (d) =df M (d0 ) and for all n ≥ 0:
Mn+1 (d) =df M (Mn (d), dn+1 ),(2) the sequence (Mn (d))n∈N converges to a number j such that c = hj .
Finally, M IT-infers C with respect to H iff, for each c ∈ C, M IT-infers c from data
sequence with respect to H.
In the latter definition Mn (d) denotes the (n + 1)th hypothesis output by M when successively fed the data sequence d.
When the data sequence are informants and texts, then we also say that M IT-infers Cfrom informant and text, respectively, with respect to the hypothesis space H considered.
For the sake of better understandability we first modify Algorithm P into an iterative
learner (cf. Algorithm IML). Again, we identify the target concept c and the monomial mdescribing it. The iterative learner is defined in stages, where Stage ` conceptually describesM` .
Algorithm IML: “Let c ∈ Cn , let i = (b0 , m(b0 )), (b1 , m(b1 )), . . . be any informant
for c. Go to Stage 0.

54

L ECTURE 5: AVERAGE -C ASE A NALYSIS II

Stage 0. IML receives as input (b0 , m(b0 )).
Initialize h0 = x1 x̄1 . . . xn x̄n .
If m(b0 ) = 0 then h0 remains unchanged; else
for j := 1 to n do
if bj0 = 1 then delete x̄j in h0 else delete xj in h0 .
Denote the result by h0 , output h0 and go to Stage 1.
Stage `, ` ≥ 1. IML receives as input h`−1 and the (` + 1)th element (b` , m(b` ))of i.
If m(b` ) = 0 then set h` = h`−1 ; else
for j := 1 to n do
if bj0 = 1 then delete x̄j in h`−1 else delete xj in h`−1 .
Denote the result by h` , output h` and go to Stage ` + 1.
By convention, if all literals have been removed, then h` = ∅, and h` (b) = 1 for allb ∈ Xn .
end.”
Now, we can directly state the following theorem.
Theorem 5.1. For every n ≥ 1 we have: IML IT-learns Cn from informant withrespect to the hypothesis space Hn .
Proof. Using the same arguments as in the proof of Theorem 2.1 one easily sees that
Algorithm IML IT-learns Cn from informant with respect to the hypothesis space Hn .
We omit the details.
Moreover, Algorithm IML can be easily adapted to learn from positive data only.
We have just to omit the tests whether or not m(b` ) = 0. We call the resulting algorithm
IMLP. Now, the following corollary is obvious.
Corollary 5.2. For every n ≥ 1 we have: IMLP IT-learns Cn from positive data onlywith respect to the hypothesis space Hn .
Also, it should be noted that Algorithm IMLP is a true limit learner, since its convergence is undecidable. You should prove this as an exercise. On the other hand, for
Algorithm IML convergence is decidable. This is due to the fact that {0, 1}n is finite for
all n ∈ N. However, deciding whether or not Algorithm IML has already converged ispractically infeasible for all n of practical relevance, since |{0, 1}n | = 2n .
Let us first take a quick look at the best and worst case complexity with respect to thenumber of prediction errors (mind changes) made. Algorithm P does not make any prediction errors and Algorithm IML does not make any mind change iff the initial hypothesis
h0 equals the target monomial, i.e., if the concept to be learned is “FALSE.” We call thisconcept minimal. The remaining concepts are said to be non-minimal.

AVERAGE -C ASE A NALYSIS FOR L EARNING IN THE L IMIT FROM P OSITIVE P RESENTATIONS

55

To study the general case, let us call the literals appearing in a non-minimal monomial mrelevant. All the other literals in Ln will be called irrelevant for m. There are 2n − #(m)irrelevant literals, where #(m) denotes the number of literals in monomial m. One can also
consider #(m) to be the length of monomial m.
We call bit i relevant for m if xi or x̄i is relevant for m and use
k =df k(m) =df n − #(m)throughout the rest of the lecture to denote the number of irrelevant bits.
Now we can expresses the best-case and worst-case number of prediction errors andmind changes made by Algorithm P and Algorithm IML as follows:
Theorem 5.3. If c is a non-minimal concept of Cn Algorithm P ( Algorithm IML )makes 2 prediction errors (mind changes) in the best-case and 1 + k(m) prediction errors(mind changes) in the worst-case.
Note that Theorem 5.3 remains valid for Algorithm IMLP. So, the gap between thebest-case and the worst-case can become quite large. But still, we have no idea about the
average. The situation changes even more, if we consider the total learning time. Since thehypotheses internally computed by Algorithm P or output by Algorithm IML can be calculated in linear time, it is easy to see that the best-case requires a total learning time O(n).
However, the worst case total learning time is unbounded, since every positive presentationand every informant may contain as many repetitions of data that do not possess enoughinformation to achieve the learning goal.
Hence, as far as learning in the limit and the complexity measure total learning time areconcerned, there is a huge gap between the best-case and the worst-case behavior. Therefore, we continue by studying the average-case behavior of the limit learner IML. We
start by restricting ourselves to learning from positive presentations only.
This restriction is also quite natural, since Algorithm IML does not learn anythingfrom negative examples and so does Algorithm P.
Note that one can also study further questions such as estimating the accuracy of ahypothesis after the Algorithm IML has seen ` many positive (or ` many positive andnegative) examples. You are encouraged to think about this question.
5.1.

Average-Case Analysis for Learning in the Limit from Positive Presentations

For the following average case analysis we assume that the data sequences are generated at random with respect to some probability distribution D taken from some class ofadmissible distributions D, which will be specified later.
We are interested in the average number of positive examples necessary to achieve convergence. Let d be a positive presentation of the concept c to be learned that is generated at
random according to D.

56

L ECTURE 5: AVERAGE -C ASE A NALYSIS II

If the concept to be learned is “FALSE” no examples are needed (and none exist). Otherwise, if the target concept contains precisely n literals then one positive example suffices(note that this one is unique). Thus, for these two cases everything is clear and the probability distributions D on the set of positive examples for c are trivial.
Thus it remains to analyze the nontrivial cases. Let c = L(m) ∈ Cn be a concept withVkmonomial m = #(m)j=1 `ij . Let k := k(m) = n − #(m) > 0. Note that there are 2 positive
examples for c.
We shall consider the class of binomial distributions, where in a random positive
example all entries corresponding to irrelevant bits are selected independently to one another. With some probability p this will be a 1, and with probability q =df 1 − p a 0. We
consider only nontrivial distributions where 0 < p < 1. Note that otherwise the data sequence does not contain all positive examples. The resulting data sequences are referred to
as to binomially distributed with parameter p.
We would like to compute the expected number of examples taken by IMLP untilconvergence.
The first example received forces IMLP to delete precisely n of the 2n literals in h0 .
Thus, this example always plays a special role.
Note that the resulting hypothesis h0 depends on b0 , but the number k of literals thatremain to be deleted from h0 until convergence is independent of b0 . It is therefore convenient to compute the expectation by considering IMLP’s behavior after having read thefirst example.
For the following analysis, we will denote by CON a random variable that counts thenumber of examples till the algorithm has converged to a correct hypothesis.
Theorem 5.4. Let c = L(m) be a non-minimal concept in Cn , and let the positive1, p1 } andexamples for c be binomially distributed with parameter p. Define ψ:= min{ 1−ppτ = max{ 1−p, 1−p}. Then the expected number of positive examples needed by algorithmp
IMLP until convergence can be bounded by
E[CON] ≤ dlogψ k(m)e + τ + 2 .

Proof. Let k := k(m). The first positive example contains ν times a 1 and k − ν many
0 with probability νk pν q k−ν at the positions not corresponding to a literal in the target
monomial m. Now, assuming any such vector, we easily see that h0 contains ν positive
irrelevant literals and k − ν negative literals. Therefore, in order to achieve convergence,
the algorithm IMLP now needs positive examples that contain at least one 0 for eachpositive irrelevant literal and at least one 1 for each negative irrelevant literal. Thus, theprobability that at least one irrelevant literal survives µ subsequent positive examples isbounded by νpµ + (k − ν)q µ . Therefore,
Pr(CON − 1 > µ) ≤

k  
X
k
ν=0

ν

pν q k−ν · (νpµ + (k − ν)q µ ) .

AVERAGE -C ASE A NALYSIS FOR L EARNING IN THE L IMIT FROM P OSITIVE P RESENTATIONS

Next, we derive a closed formula for the sum given above.
k  
k  
X
X
k ν k−νk ν k−ν
Claim 1.
p q
· ν = kp and
p q· (k − ν) = kq
ν
ν
ν=0
ν=0
The first equality can be shown as follows.
k  
X
k
ν=0

ν

ν k−ν

p q

·ν

k  
X
k

=

ν=1
k−1 
X

=

ν=0

ν

pν q k−ν · νkpν+1 q k−1−ν · (ν + 1)
ν+1

k−1
X


k − 1 ν+1 k−(ν+1)
k·
p q
ν
ν=0

k−1 
X
k − 1 ν (k−1)−ν
kp ·
p q
ν
ν=0

=

=



kp · (p + q)k−1 = kp .

=The other equality can be proved analogously, which yields Claim 1.
Now, proceeding as above, we obtain
E[CON − 1] =∞X

Pr(CON − 1 > µ)

µ=0

≤

λ+

k  
∞ X
X
k
µ=λ ν=0

=

λ+

∞ X
k  
X
k
µ=λ ν=0

=

λ+

ν

∞
X

µ

p ·

ν

=kp

=

λ + kp ·

∞
X
µ=λ



≤
≤

ν k−ν

p q

µ

µ

· νp +

∞ X
k  
X
k
µ=λ ν=0

k  
X
k

|ν=0

µ=λ

pν q k−ν · (νpµ + (k − ν)q µ )

ν

ν k−ν

p q

ν+

{z

}

∞
X

µ

q ·

µ=λ
by Claim 1

p + kq ·

∞
X

q

µ

µ=λ

p −λ qλ+k·· ψ + · ψ −λqp
λ + kψ −λ · (1 + τ ) .

ν

k  
X
k

|ν=0


= λ+k·pν q k−ν · (k − ν)q µνpν q k−ν · (k − ν)=kq

p λ q λ·p + ·qqpFinally, choosing λ = dlogψ ke gives the statement of the theorem.
As a corollary we get{z

by Claim 1



}

57

58

L ECTURE 5: AVERAGE -C ASE A NALYSIS II

Corollary 5.5. For every binomially distributed positive presentation with parameter0 < p < 1 the average total learning time of algorithm IMLP for concepts in Cn is at
most O(n log n). More precisely, a concept c = L(m) requires time O(n log(n−#(m)+2))
on the average.
The expectation alone does not provide complete information about the average case behavior of an algorithm. It is helpful to know larger moments, too, in particular the variance.
Then one can deduce bounds how often the algorithm exceeds the average considerably byapplying, for example, Chebyshev’s inequality. If the variance is not available, Markov’s
inequality provides us with worse tail bounds:
If X is any random variable taking only positive real values then
Pr(X ≥ t · E[X]) ≤1
for all k ≥ 1 .
tMarkov’s inequality is quite general but produces only weak bounds.
However, Algorithm IMLP possesses two favorable properties that simplify the analysis considerably, it is set-driven and conservative. They allow to establish goodbounds for the tail probabilities.
Set-driven means that the output depends only on the range of the input sequence. More+formally, for all c ∈ Cn all t, t̂ ∈ text(c) and all i, j ∈ N+ the equality t+
i = t̂j of the rangeof the two prefixes implies IMLP(ti ) = IMLP(t̂j ).
It is easy to see that Algorithm IMLP fulfills this property.
Furthermore, a learner is said to be conservative if every mind change is caused by aninconsistency with the data seen so far. Algorithm IMLP satisfies this condition, too, i.e.,
for all c ∈ Cn , all t ∈ text(c) and all i, j ∈ N+ it holds: if IMLP(ti ) 6= IMLP(ti+j )then t+i+j 6⊆ L(IMLP(ti )).
Now, we can apply the following theorem to obtain exponentially shrinking tail bounds
for the expected number of examples needed in order to achieve convergence.
Theorem 5.6 (Rossmanith and Zeugmann [1]). Let CON be the sample complexity ofa conservative and set-driven learning algorithm. Then for arbitrary t ∈ N it holds
Pr (CON > 2 t · E[CON] ) ≤ 2−t .

Since Theorem 5.6 is of central importance, we also provide a proof. First, recall thedefinition of median. If X is a random variable then µX is a median of X iff
Pr(X ≥ µX) ≥ 1/2 and Pr(X ≤ µX) ≥ 1/2.
A nonempty set of medians exists for each random variable and consists either of a single
real number or of a closed real interval. We will denote the smallest median of X by µX,
since this choice gives the best upper bounds. Now, we can show the following theorem.

AVERAGE -C ASE A NALYSIS FOR L EARNING IN THE L IMIT FROM P OSITIVE P RESENTATIONS

59

Theorem 5.7 (Rossmanith and Zeugmann [1]). Let X be the sample complexity ofa conservative and set-driven learning algorithm. Then Pr(X ≥ t · µX) ≤ 2−t for allt ∈ N.
Proof. We divide the data sequence d0 , d1 , . . . into blocks of length µX. The probability
that the algorithm converges after reading any of the blocks is then at least 1/2. Since thealgorithm is set-driven the order of the blocks does not matter and since the algorithm isconservative it does not change its hypothesis after computing once the right hypothesis.
Theorem 5.6 now follows by taking into account that µX ≤ 2E[X] for every positive
random variable X in accordance with the Markov inequality. Therefore,
Pr(X ≥ 2t · E[X]) ≤ 2−t

for every t ∈ N .

A simple calculation shows that in case of exponentially shrinking tail bounds the variance is bounded by O(E[CON]2 ).
So, the deviation from the average will be quite small due to our exponentially shrinking
tail bounds. In other words, Algorithm IMLP is a quite data efficient learning algorithm
on average. This should surprise you a bit, since it can be as inefficient as you like in theworst-case. Thus, for many practical problems, like the one exemplified in the last lectures,
analyzing the average-case behavior is of much more practical importance than studying
the worst case complexity.

References[1] P. ROSSMANITH AND T. Z EUGMANN, Stochastic Finite Learning of the Pattern Languages, Machine Learning 44, No. 1-2, 2001, 67–91.
[2] R. W IEHAGEN, Limes-Erkennung rekursiver Funktionen durch spezielle Strategien.
Journal of Information Processing and Cybernetics (EIK) 12, 1976, 93–99.

61

L ECTURE 6: S TOCHASTIC F INITE L EARNING AND PAC
L EARNING
6.1.

Stochastic Finite Learning

After having analyzed the average-case behavior of Algorithm IMLP we want toaddress our remaining point of concern. As pointed out in Lecture 3, a limit learner is only
supposed to converge in the limit, but never knows whether or not it already did so. Such an
uncertainty may be prohibitive in many applications of learning. So, how can we recover?
Of course, we cannot achieve certainty concerning convergence, since otherwise convergence would be decidable. But, as we have already mentioned a couple of times, convergence is undecidable in general. But even if convergence is decidable as in the case oflearning monomials from positive and negative data, it is practically infeasible to decide
whether or not the learner did already converge.
Therefore, we have to replace certainty concerning convergence by a weaker requirement. Again, recall that there are always optimistic, pessimistic and probabilistic people
around. So, if we suppose optimistic people to optimistically assume that the learner has
already converged and pessimistic people to pessimistically assume that the learner did not
yet converge, then it remains to explain what probabilistic people can do.
Looking at real life examples, we see that we quite often have a confidence in doing
something which is based on experience. Thus, we introduce a new parameter δ into ourlearning model called confidence parameter.
Then, in the following we always assume a class D of admissible probability distributions over the relevant learning domain. Ideally, this class should be parameterized. Furthermore, the data fed to learner are generated randomly with respect to one of the probability
distributions from the class D of underlying probability distributions.
Additionally, the learner takes the confidence parameter δ as input. But in contrast tolearning in the limit, the learner itself decides how many examples it wants to read. Then it
computes a hypothesis, outputs it and stops. The hypothesis output is correct for the target
with probability at least 1 − δ.
The explanation given so far explains how it works, but not why it does. Intuitively,
the stochastic finite learner simulates the limit learner until an upper bound for twice theexpected total number of examples needed until convergence has been met. Assuming thisto be true, by Markov’s inequality the limit learner has now converged with probability
1/2. All what is left, is to decrease the probability of failure. This is done by using thetail bounds for CON. Applying Theorem 5.6, one easily sees that increasing the sample
complexity by a factor of O(log 1δ ) results in a probability of 1 − δ for having reached thestage of convergence. If Theorem 5.6 is not applicable, one can still use Markov’s inequality
but then the sample complexity needed will increase by a factor of 1/δ.
It remains to explain how the stochastic finite learner can calculate the upper bound for
E[CON]. This is precisely the point where we need the parameterization of the class D of

62

L ECTURE 6: S TOCHASTIC F INITE L EARNING AND PAC L EARNING

underlying probability distributions. Since in general, it is not known which distribution
from D has been chosen, one has to assume a bit of prior knowledge or domain knowledge
provided by suitable upper and/or lower bounds for the parameters involved. A more serious difficulty is to incorporate the unknown target concept into this estimate. This step
depends on the concrete learning problem on hand, and requires some extra effort. We shallexemplify it below. Figure 6.2 displays the basic features of stochastic finite learning. You
should compare it to learning in the limit (cf. Figure 2.1 at Page 23).
Depicted when Learning finishes:OutInh ←− M ←− δ, d
. . , d}0
| t, . {zdrawn w.r.t.s. D∈Ddef

M learns (C, D) stochastically finite ⇔ for all δ ∈ (0, 1), after having read a finite
number of examples, M outputs a single hypothesis h ∈ H, and stops. With probability
at least 1 − δ (w.r.t. D) h has to be correct, i.e., L(h) = c. (Note that t may depend on δ.)
Figure 6.2: Stochastic Finite Learning
Now we are ready to formally define stochastic finite learning.
Definition 14 ([4, 5, 6]). Let D be a set of probability distributions on the learning
domain, C a concept class, H a hypothesis space for C, and δ ∈ (0, 1). (C, D) is said tobe stochastically finitely learnable with δ-confidence with respect to H iff there is an IIM
M that for every c ∈ C and every D ∈ D performs as follows. Given any random data
sequence θ for c generated according to D, M stops after having seen a finite number ofexamples and outputs a single hypothesis h ∈ H. With probability at least 1 − δ (withrespect to distribution D) h has to be correct, that is c = h.
If stochastic finite learning can be achieved with δ-confidence for every δ > 0 then we
say that (C, D) can be learned stochastically finite with high confidence.
Next, we turn our attention to the design of a stochastic finite learner for learning monomials from positive data. We study the case that the positive examples are binomiallydistributed with parameter p. But we do not require precise knowledge about the underlying distribution. Instead, we reasonably assume that prior knowledge is provided byparameters plow and pup such that plow ≤ p ≤ pup for the true parameter p. Binomial distributions fulfilling this requirement are called (plow , pup )–admissible distributions.
Let Dn [plow , pup ] denote the set of such distributions on Xn .
If bounds plow and pup are available, the Algorithm IMLP can be transformed into astochastic finite learner inferring all concepts from Cn with high confidence.
Theorem 6.1 (Reischuk and Zeugmann [4]). Let 0 < plow ≤ pup < 1 and ψ :=min{ 1−p1low , p1up }. Then (Cn , Dn [plow , pup ]) is stochastically finitely learnable with high

L EARNING M ONOMIALS FROM I NFORMANT

63


confidence from text. To achieve δ-confidence no more than O log2 1/δ · logψ n many
examples are necessary.
Proof. The stochastic finite learner is based on Algorithm IMLP and a counter for thenumber of examples already processed. We set
1 − plowpup
1 − pup
plow
,
,
,
.
τmax = max
1 − plowplow
1 − puppup
If Algorithm IMLP is run for ϑ := dlogψ ne + τmax + 2 many examples, Theorem 5.4
implies that ϑ is at least as large as the expected convergence stage E[CON].
In order to achieve the desired confidence, the learner sets γ := dlog 1δ e and runs Algorithm IMLP for a total of 2 γ · ϑ examples. This is the reason why we need a counterfor the number of examples processed. The algorithm outputs the last hypothesis h2 γ·ϑ
produced by Algorithm IMLP and stops thereafter. The reliability follows from the tailbounds established in Theorem 5.6.
So far, our results provide evidence that analyzing the average-case behavior of limit
learners with respect to their total learning time may be considered as a promising path
towards a new theory of efficient algorithmic learning. But what happens if we have tolearn monomials from both positive and negative examples? We shall address this questionin the following.
6.2.

Learning Monomials from Informant

Next, we ask how the results obtained so far translate to the case of learning from informant. Since Algorithm IML does not learn anything from negative examples, one may
expect that it behaves much poorer in this setting. First, we investigate the uniform distribution over Xn . Again, we have the trivial cases that the target concept is “FALSE” or m isa monomial without irrelevant bits. In the first case, no example is needed at all, while in
the latter one, there is only one positive example having probability 2−n . Thus the expected
number of examples needed until successful learning is 2n = 2#(m) .
Theorem 6.2. Let c = L(m) ∈ Cn be a nontrivial concept. If a data sequence for c isgenerated from the uniform distribution on the learning domain by independent draws the
expected number of examples needed by Algorithm IML until convergence is bounded by
E[CON] ≤ 2#(m) (dlog2 k(m)e + 3) .

Proof. Let CON+ be a random variable for the number of positive examples needed untilconvergence. Every positive example is preceded by a possibly empty block of negative
examples. Thus, we can partition the initial segment of any randomly drawn informant read
until convergence into CON+ many blocks Bj containing a certain number of negative
examples followed by precisely one positive example. Let Λj be a random variable for thelength of block Bj . Then CON = Λ1 + Λ2 + · · · + ΛCON+ , where the Λj are independently

64

L ECTURE 6: S TOCHASTIC F INITE L EARNING AND PAC L EARNING

identically distributed. In order to compute the distribution of Λj , it suffices to calculate
the probabilities to draw a negative and a positive example, respectively. Since the overall
number of positive examples for c is 2k with k = k(m), the probability to generate apositive example is 2k−n . Hence, the probability to draw a negative example is 1 − 2k−n .
Consequently,
µPr[Λj = µ + 1] = 1 − 2k−n · 2k−n .
Therefore,
E[CON] = E[Λ1 + Λ2 + · · · + ΛCON+ ]∞X=
E[Λ1 + Λ2 + · · · + Λζ | CON+ = ζ] · Pr[CON+ = ζ]
=

ζ=0
∞
X

ζ · E[Λ1 ] · Pr[CON+ = ζ]

ζ=0= E[CON+] · E[Λ1 ]By Markov’s inequality, we have E[CON+] ≤ dlog2 ke + 3, and thus it remains to estimate
E[Λ1 ]. A simple calculation shows
Lemma 6.3. For every 0 < a < 1 holds:∞X(µ + 1) · aµ = (1 − a)−2 .

µ=0

Using this estimation we can conclude
E[Λ1 ] =∞X(µ + 1) · Pr[Λ1 = µ + 1]µ=0

= 2k−n∞Xµ(µ + 1) · 1 − 2k−n
= 2n−k ,µ=0

and thus the theorem follows.
Hence, as long as the length of m is constant, and therefore k(m) = n − O(1), we stillachieve an expected total learning time of order n log n. But if #(m) grows linearly the
expected total learning becomes exponential. On the other hand, if there are many relevant
literals then even h0 may be considered as a not too bad approximation for c. Consequently,
it is natural at this point to introduce an error parameter ε ∈ (0, 1) as in the PAC model (seebelow), and to ask whether one can achieve an expected sample complexity for computing
an ε-approximation that is bounded by a function depending on log n and 1/ε.
To answer this question, let us formally define error m (hj ) = D(L(hj )4L(m)) to be theerror made by hypothesis hj with respect to monomial m. Here L(hj )4L(m) stands for thesymmetric difference of L(hj ) and L(m) and D for the underlying probability distribution
with respect to which the examples are drawn. Note that by construction of Algorithm
IML we can conclude error m (hj ) = D(L(m) \ L(hj )).

PAC L EARNING

65

We call hj an ε–approximation for m if error m (hj ) ≤ ε. Finally, we redefine the stageof convergence. Let m be any monomial, and let d = (dj )j∈N+ be an informant for L(m),thenCONε (d) =df the least number j such that error m (IML (di )) ≤ ε for all i ≥ j .
Note that once the Algorithm IML has reached an ε-approximate hypothesis all further
hypotheses will also be at least that close to the target monomial.
The following theorem gives an affirmative answer to the question posed above.
Theorem 6.4. Let c = L(m) ∈ Cn be a nontrivial concept. Assuming that examples
are drawn at random independently from the uniform distribution, the expected number ofexamples needed by Algorithm IML until converging to an ε–approximation for c can bebounded by
1
E[CONε ] ≤ · (dlog2 k(m)e + 3) .
ε
Proof. It holds error m (h0 ) = 2k(m)−n , since h0 misclassifies exactly the positive examples. Therefore, if error m (h0 ) ≤ ε, we are already done. Now suppose error m (h0 ) > ε.
Consequently, 1/ε > 2n−k(m) , and thus the bound stated in the theorem is larger than
2n−k(m) (dlog2 k(m)e + 3), which, by Theorem 6.2 is the expected number of examples
needed until convergence to a correct hypothesis.
Thus, additional knowledge concerning the underlying probability distribution pays off
again. Applying Theorem 5.6 and modifying the stochastic finite learner presented above
mutatis mutandis, we get a learner identifying ε-approximations for all concepts in Cn
stochastically with high confidence using O( 1ε · log 1δ · log n) many examples. Comparing
this bound with the sample complexity given in the PAC model, we see that it is reduced
exponentially, i.e., instead of a factor n now we have the factor log n (cf. Theorem 6.5
below).
So, let us continue with the PAC model. In contrast to our considerations above we do
not assume any prior knowledge concerning the underlying probability distribution.
6.3.

PAC Learning

PAC stands for probably approximately correct and the corresponding learning model
goes back to Valiant [6]. Comprehensive treatises of this topic include Anthony and Biggs[1], Kearns and Vazirani [2] as well as Natarajan [3]. We use our example, i.e., the set of
all concepts describable by a monomial over Ln to explain the basic ideas behind the PAC
approach. The main difference to the models considered so far starts with the source of information. We assume an unknown probability distribution D over the learning domain X .
There is a sampling oracle EX( ), which has no input. Whenever EX( ) is called, it draws
an element x ∈ X according to the distribution D and returns the element x together with anindication of whether or not x belongs to the target concept c. Thus, every example returned

66

L ECTURE 6: S TOCHASTIC F INITE L EARNING AND PAC L EARNING

by EX( ) may be written as (x, c(x)), where c(x) = 1 if x ∈ c and c(x) = 0 otherwise. If
we make s calls to the example EX( ) then the elements x1 , . . . xs are drawn independently
from one another. Thus, the resulting probability distribution over all s-tuples of elementsfrom X is the s-fold product distribution of D, i.e.,Pr(x1 , . . . , xs ) =sY

D(xi ).

i=1

In the following, we use Pr(A) to denote the probability of event A, where A is a set ofs-tuples over X , s ≥ 1. The actual s will be always clear from the context.
The criterion of success, i.e., probably approximately correct learning, is parameterizedwith respect to two quantities, the accuracy parameter ε, and the confidence parameter δ,
where ε, δ ∈ (0, 1]. Next, we define a notion of the difference between two sets c, c0 ⊆ X
with respect to the probability distribution D asX
d(c, c0 ) =D(x).
x∈c4c0A learning method A is said to probably approximately correctly identify a target
concept c with respect to a hypothesis space H, and with sample complexity s = s(ε, δ),if for all ε, δ ∈ (0, 1) it makes s calls to the oracle EX( ), and after having received theanswers produced by EX( ) (with respect to the target c), it always stops and outputs ahypothesis h ∈ H such that
Pr(d(c, h) ≤ ε) ≥ 1 − δ.

A learning method A is said to probably approximately correctly identify a target
concept class C with respect to a hypothesis space H and with sample complexity s =s(ε, δ), if it probably approximately correctly identifies every concept c ∈ C with respect toH, and with sample complexity s.
Finally, a learning method is said to be efficient with respect to sample complexity, if
there exists a polynomial pol such that s ≤ pol (1/ε, 1/δ).
O.k, this looks fairly complicated, and hence, some explanation is in order. First of all,the inequality
Pr(d(c, h) ≤ ε) ≥ 1 − δmeans that with high probability (quantified by δ) there is not too much difference (quantified by ε) between the conjectured concept (described by h) and the target concept c.
Formally, let A be any fixed learning method. Let s = s(ε, δ) for any fixed ε, δ ∈ (0, 1)
be the actual sample size. Furthermore, let c be any fixed target concept. Now, we haveto consider all possible outcomes of A when run on every labeled s-sample S(c, x̄) =(x1 , c(x1 ), . . . , xs , c(xs )) returned by EX( ). Let h(S(c, x̄)) denote the hypothesis produced by A when processing S(c, x̄). Then we have to consider the set W of all s-tuples
over X such that d(c, h(S(c, x̄))) ≤ ε. The condition Pr(d(c, h) ≤ ε) ≥ 1 − δ can now

PAC L EARNING

67

be formally rewritten as Pr(W ) ≥ 1 − δ. Clearly, one has to require that Pr(W ) is welldefined. This is obvious as long as X is finite.
In order to exemplify this approach, remember that our set of all concepts describableby a monomial over Ln actually refers to the set of all things. We consider a hypotheticallearner (e.g., a student, a robot) that has to learn the concept of a chair. Imagine that thelearner is told by some teacher whether or not particular things visible by the learner are
instances of a chair. Clearly, what things are visible depends on the environment the learneris in. The formal description of this dependence is provided by the unknown probability
distribution. For example, the learner might be led to a kitchen, a sitting room, a book shop,
a garage, a beach a.s.o. Clearly, it would be unfair to teach you the concept of a chair in abook shop, and then testing your learning success in a sitting room. Therefore, the learning
success is measured with respect to the same probability distribution D with respect towhich the sampling oracle has drawn its examples. However, the learner is required to learn
with respect to any probability distribution. That is, independently of whether the learneris led to a kitchen, a book shop, a sitting room, a garage, a beach a.s.o., it has to learn
with respect to the place it has been led to. The sample complexity refers to the amount of
information needed to ensure successful learning. Clearly, the smaller the required distanceof the hypothesis produced, and the higher the confidence desired, the more examples areusually needed. However, there might be atypical situations. To have an extreme example,
the kitchen the learner is led to turned out to be empty. Since the learner is required tolearn with respect to a typical kitchen (described by the probability distribution D) it may
well fail under this particular circumstance. Nevertheless, such failure has to be restricted toatypical situations. This requirement is expressed by demanding the learner to be successful
with confidence 1 − δ.
This corresponds well to real life situations. For example, a student who has attended acourse in probability theory might well suppose that he/she is examined in probability theory and not in graph theory. However, a good student, say in computer science, has to pass
all examinations successfully, independently of the particular course attended. That is, hemust successfully pass examinations in computability theory, complexity theory, cryptology, parallel algorithms, formal languages, recursion theory, learning theory, graph theory,
combinatorial algorithms, logic programming, a.s.o. Hence, he/she has to learn a wholeconcept class. The sample complexity refers to the time of interaction performed by thestudent and his/her teacher.
Now, we are ready to prove the PAC learnability of our concept class. We use the same
notation as above.
Theorem 6.5. The set of all monomials over Ln can be probably approximately correctly
learned with respect to the hypothesis space H and with sample complexity s = O(1/ε ·(n + ln(1/δ))).
Proof. As a matter of fact, we can again use a suitable modification of algorithm P
presented in Lecture 2.
Algorithm PA: “For all ε, δ ∈ (0, 1), call the oracle EX( ) s times, where s = O(1/ε ·68

L ECTURE 6: S TOCHASTIC F INITE L EARNING AND PAC L EARNING(n + ln(1/δ))). Let hb1 , m(b1 ), b2 , m(b2 ), . . . , bs , m(bs )i be the sequence returned byEX( ). Let bi = b1i b2i . . . bni denote the ith vector bi ∈ X returned.
Initialize h = x1 x̄1 . . . xn x̄n .
For i = 1, 2, . . . , s do
if m(bi ) = 1 thenfor j := 1 to n do
if bji = 1 then delete x̄j in h else delete xj in h.
Output h.
end.”
Let D be any probability distribution over X . Furthermore, let m be any target monomial. We have to show that the algorithm PA outputs with confidence at least 1 − δ ahypothesis h such that d(m, h) ≤ ε. We easily observe thatXd(m, h) =D(b) = D({b ∈ X m(b) 6= h(b)}).
b∈m4hSince the algorithm PA is essentially the same as Algorithm P we can exploit the proofof Theorem 2.1. First of all, for every target monomial m, if h is the hypothesis output by
PA then h(bi ) = m(bi ) for all i = 1, . . . , s. Recall that such hypotheses are said to beconsistent.
Now, suppose any particular hypothesis h ∈ H such that d(m, h) > ε. Any such
hypothesis will not be consistent with s randomly drawn examples unless all examples are
drawn outside the symmetric difference of m and h. Let b ∈ X be any randomly chosen
vector. Then we have: the probability that m(b) = h(b) is bounded by 1 − ε. Hence, if wehave s randomly and independently drawn vectors b1 , . . . , bs ∈ X , then the probability thatm(bi ) = h(bi ) for all i = 1, . . . , s is bounded by (1 − ε)s . Furthermore, (1 − ε)s < e−εs .
Additionally, there are card(H) many possible choices for h.
Thus, the overall probability that s randomly and independently drawn vectors do notbelong to m 4 h, for any h ∈ H, is bounded by card(H)e−εs .
Therefore, if s > 1/ε · ln card(H)we get:δcard(H)e−εs < card(H)e− lncard(H)δ= δ.

Consequently, since all hypotheses h output by PA are consistent, now we know that
Pr(d(m, h) > ε) < δ, and thusPr(d(m, h) ≤ ε) ≥ 1 − δ.
Finally, by Exercise 1 we know that card(H) = 3n + 1, hence the theorem follows.

PAC L EARNING - THE F INITE C ASE

69

Next, we consider disjunctions over Ln , i.e., all expressions f = `i1 ∨ . . . ∨ `ik , wherek ≤ n, i1 < . . . < ik , and all `ij ∈ LN for j = 1, . . . , k. Hence, disjunctions are the logicalduals of monomials. Additionally, we include f = x1 ∨ x̄1 ∨ . . . ∨ xn ∨ x̄n into the set of all
disjunctions over Ln to represent the concept “TRUE.” Furthermore, let b = b1 . . . bn ∈ X ,then f (b) = `i1 (bi1 ) ∨ . . . ∨ `ik (bik ), where `ij (bij ) = 1 iff `ij = xi for some i, and bij = 1
or `ij = x̄i for some i, and bij = 0. Otherwise, `ij (bij ) = 0. Then, if f is a disjunction over
Ln we set L(f ) = {b ∈ X f (b) = 1}. Finally, let C be the set of all concepts describableby a disjunction over Ln , and let Ĥ be the hypothesis space that consists of all disjunctions
as described above.
Exercise 13. Prove or disprove.
(a) The set of all disjunctions over Ln can be probably approximately correctly learned
with respect to the hypothesis space Ĥ and with sample complexity s = O(1/ε · (n +ln(1/δ))).
Next, we continue with a closer at probably approximately correct learning. So far in
our study we have only proved the class of concepts describable by a monomial to be PAC
learnable. Therefore, we are interested in gaining a better understanding of what finite
concept classes are PAC learnable. Furthermore, we aim to derive general bounds on thesample complexity needed to achieve successful PAC learning provided the concept classunder consideration is PAC identifiable at all.
Moreover, concept classes of infinite cardinality make up a large domain of importantlearning problems. Therefore, it is only natural to ask whether or not there are interesting
infinite concepts classes which are PAC learnable, too. The affirmative answer will be
provided in the following lectures. For the sake of presentation, we start with a general
analysis of PAC learnability for finite concept classes. Subsequently, we investigate thecase of infinite concept classes.
6.3.1.

PAC Learning - the Finite Case

Let X be any finite learning domain, let D be any probability distribution over X , and
let C ⊆ ℘(X ) be a concept class. Furthermore, we use H to denote any hypothesis spacefor C. Note that, in general, we do not require C ⊆ H. To simplify notation, we use |M |to denote the cardinality of any set M . Let m ∈ N, m ≥ 1; then we use X m to denotethe m-fold Cartesian product of X . Let x̄ ∈ X m , the we write x̄ = (x1 , . . . , xm ). Now,
let c ∈ C be any concept. The m-sample of c generated by x̄ is denoted by S(c, x̄) =hx1 , c(x1 ), . . . , xm , c(xm )i. A hypothesis h ∈ H is said to be consistent for an m-sample
S(c, x̄) iff h(xi ) = c(xi ) for all 1 ≤ i ≤ m.
The sample space Sc of a concept c is the set of all m-samples of c, i.e.,[ [Sc =S(c, x̄).
m≥1 x̄∈X m

70

L ECTURE 6: S TOCHASTIC F INITE L EARNING AND PAC L EARNING

The sample space S(C) of a concept class C is the union of over all Sc , c ∈ C. Then, alearner is any computable mapping from S(C) into H. A learner is said to be consistent
iff all its outputs are consistent hypotheses.
The formal definition of PAC learning has already been presented above. Moreover,
we showed the class of all monomials to be PAC learnable. The general idea behind thealgorithm given there can be described as follows:(1) Draw a sufficiently large sample from the oracle EX( ), say m examples.
(2) Find some h ∈ H that is consistent with all the examples drawn.
(3) Output h.
Therefore, it is only natural to ask whether or not this strategy may be successful in thegeneral finite case, too. Let us assume that we have a consistent learner. Let c ∈ C be
any concept, and let h be any hypothesis output by the learner on any m-sample S(c, x̄),
where x̄ has been drawn with respect to the unknown probability distribution D. Assume
h to be bad, i.e., d(c, h) > ε. Any such hypothesis will not be consistent with m randomly
drawn examples unless all examples are drawn outside the symmetric difference of c and h.
Hence, the probability that the particular bad hypothesis h survives m examples is at most
(1 − ε)m . Consequently, the probability that some bad hypothesis survives m examples is
at most |H|(1 − ε)m . Furthermore, we want P r(d(c, h) > ε) < δ. Hence, we must require:|H|(1 − ε)m ≤ δ.
Now, the latter requirement directly allows to lower bound m. Taking the natural logarithmof both sides, we obtain:ln |H| + m ln(1 − ε) ≤ ln δ.
Therefore, we have:m>ln δ − ln |H|
ln(1 − ε)Because of (1 − z1 )z < e−1 for all z > 0, we additionally obtain:(1 − ε) = ((1 − ε)1/ε )ε < e−ε ,and thusln(1 − ε) < −ε.
Putting it all together, we see that
1
m>
ε



1
ln |H| + ln
δ


=

1 |H|
ln
.
ε
δ

We summarize the insight obtained by the following theorem.
Theorem 6.6. Let X be any finite learning domain, let C ⊆ ℘(X ) be any concept class,and let H be any hypothesis space for C. Then every consistent learner PAC identifies Cwith respect to H with sample complexity m = 1ε ln |H|+ 1.
δPAC L EARNING - THE F INITE C ASE

71

The latter theorem delivers a first upper bound on the sample complexity needed toachieve efficient PAC learning. However, it does not say anything concerning the problem
to compute consistent hypotheses. Clearly, there is a trivial algorithm to achieve this goal.
We may just enumerate all hypotheses. Then we may simply search for the first consistent
one in the enumeration fixed. Nevertheless, taking into account that H might be huge, thismethod will usually take too much time. Hence, further effort is necessary to arrive atpractical learning algorithms.
The latter observation motivates us to strengthen our requirements concerning the efficiency of PAC learning. It might be not enough to bound the number of examples. Additionally, we shall demand the overall running time to be polynomial in the appropriate
parameters.
Definition 15. A concept class C is said to be efficiently PAC learnable withrespect to the hypothesis space H if C is PAC learnable with respect to H, and there
exists a PAC learning algorithm A for C that runs in time polynomial in 1/ε, 1/δ, n ( thesize of an instance in X ), and size(c) for all ε, δ ∈ (0, 1) and all c ∈ C.
Now, we are ready to establish the PAC learnability of a couple of important finite concept classes. A clause is a disjunction of literals. By k-CNF we denote the class of all
conjunctions such that each clause contains at most k literals. For example,(x1 ∨ x̄2 ∨ x̄3 ) ∧ (x̄1 ∨ x2 ∨ x3 )is a 3-CNF.
The overall number of clauses containing at most k literals is bounded by
2n + (2n)2 + . . . (2n)k < O(nk ) .
Hence, ln(|k-CNF|) = O(nk ). Therefore, we get the following general theorem.
Theorem 6.7. Let k ∈ N+ be arbitrarily fixed. The class of all concepts describable bya k-CNF formula is efficiently PAC learnable with respect to k-CNF.
Proof. On input ε, δ make m = O 1ε (nk + ln 1δ calls to the oracle EX( ). Let S(c, b̄) =hb1 , c(b1 ), . . . , bm , c(bm )i be the sample returned.
Initialize h as the conjunction of all clauses containing at most k literals.
For i = 1, 2, . . . m do
if c(bi ) = 1 then delete all clauses in h that do not contain a literal evaluating to 1 on theassignment given by bi .
Output h.
By construction, h is consistent. Hence, by Theorem 6.6 we know that the algorithm described above PAC learns k-CNF with respect to k-CNF. The running time of this algorithm
is obviously polynomially bounded in 1/ε, 1/δ, and nk .

72

L ECTURE 6: S TOCHASTIC F INITE L EARNING AND PAC L EARNING

Next, by k-DNF we denote the class of all disjunctions such that each monomial contains
contains at most k literals.
Exercise 14. Prove the following: Let k ∈ N+ be arbitrarily fixed. The class of allconcepts describable by a k-DNF formula is efficiently PAC learnable with respect to kDNF.

References[1] M. A NTHONY AND N. B IGGS (1992), “Computational Learning Theory,” Cambridge University Press, Cambridge.
[2] M.J. K EARNS AND U.V. VAZIRANI (1994), “An Introduction to Computational
Learning Theory,” MIT-Press.
[3] B.K. NATARAJAN (1991), “Machine Learning,” Morgan Kaufmann Publishers Inc.
[4] R. R EISCHUK AND T. Z EUGMANN, A Complete and Tight Average-Case Analysis
of Learning Monomials, in “Proceedings 16th International Symposium on Theoretical Aspects of Computer Science,” (C. Meinel and S. Tison, Eds.), Lecture Notes in
Computer Science, Vol. 1563, pp. 414–423, Springer-Verlag , Berlin 1999.
[5] R. R EISCHUK AND T. Z EUGMANN, An average-case optimal one-variable patternlanguage learner, Journal of Computer and System Sciences 60, No. 2, 2000, 302–
335.
[6] P. ROSSMANITH AND T. Z EUGMANN, Stochastic finite learning of the pattern languages, Machine Learning 44, No. 1-2, 2001, 67–91.
[6] L.G. VALIANT (1984), A theory of the learnable, Communications of the ACM 27,1134 – 1142

73

L ECTURE 7: D ECISION T REE L EARNING
So far, we have mainly studied the learnability of simple Boolean concepts. That is, we
looked at concepts describable by a monomial. However, over the learning domain {0, 1}nthere are only 3n + 1 many concepts that can be described by a monomial. In contrast, therenare 22 many Boolean functions. Since every Boolean function can be represented by adecision tree, we shall finish our tour on learning by learning at the learnability of decision
trees. As a matter of fact, decision tree learning is used quite often in practice. So, you
should know at least a bit about it. Also, we shall not restrict ourselves to the Boolean case.
For the sake of presentation, let us have a look at the whether data already used in
Lecture 1. Recall that this data set is fictitious, but it serves its purpose to explain sometypical features. The data concern the conditions for playing some unspecified game.
The Weather Data
outlooksunny
sunny
overcast
rainy
rainy
rainy
overcast
sunny
sunny
rainy
sunny
overcast
overcast
rainy

temperature
hot
hot
hot
mild
cool
cool
cool
mild
cool
mild
mild
mild
hot
mild

humidity
high
high
high
high
normalnormalnormalhighnormalnormalnormalhighnormal
high

windy
false
true
false
false
false
true
true
false
false
false
true
true
false
true

play
no
no
yes
yes
yes
no
yes
no
yes
yes
yes
yes
yes
no

In the table displayed above, we have four attributes, i.e., outlook, temperature, humidity, and windy. These attributes can take symbolic values rather than numerical values. The
rightmost column shows the recommendation, that is whether or not one should play. In
other words, the attributes are observable variables, and the recommendation is assumed
to be a function of the attributes. Let us assume that outlook can take the three values
sunny, overcast, rainy, that temperature can take the three values hot, mild, cool, that
humidity can take the two values high, normal and that windy can take the two values
true, false. Then, the complete table should have 36 entries. In contrast, the table given has
only 14 entries. This is quite a typical situation in many applications.
Next, we ask if there are any rules behind this table. This is the typical question asked
in data mining. Here the typical problem is again to make predictions. For example, we are
given the following data for tomorrow.

74

L ECTURE 7: D ECISION T REE L EARNING

outlooksunnytemperaturecool

humidity
high

windy
true

play
?

So, what should we do, play or not play?
Of course, there may be many different ways to express such rules and to find them.
Decision trees are one possibility.
Thus, let us first look at a decision tree for the weather data set given above.
outlooksunnyovercast

rainy

yes
humidity
high
no

windy
normal

yes

false
yes

true
no

Figure 7.1: Decision tree for the weather data.

Clearly, we have to ask what this decision tree is representing.
7.1.

Decision Tree Representation

Decision trees classify instances by sorting them down the tree from the root to someleaf. The label in the leaf provides the classification of the instance. Each node in the treethat is not a leaf specifies a test of some attribute of the instance by which it is labeled. Eachbranch descending from that node corresponds to some possible value for this attribute.
Any given instance is the classified by starting at the root, testing the attribute specified
there and then moving down the tree branch which corresponds to the value given. This
process is then recursively repeated for the subtree rooted at the new node. For example,
let (sunny, hot, high, false) from the weather data set be the given instance. First, we test
outlook, which is sunny. Thus, we move down the left branch of the tree shown in
Figure 7.1. Next, we test the attribute humidity which has value high. Thus, the instance(sunny, hot, high, false) is correctly classified by no.
In general, decision trees represent a disjunction of conjunctions of constraints on theattribute values of instances. For example, using the natural interpretation of yes as 1 thedecision tree given in Figure 7.1 corresponds to the disjunction(outlook = sunny ∧ humidity = normal)∨ (outlook = overcast)∨ (outlook = rainy ∧ windy = false)
Before we turn our attention to the problem of learning decision trees from examples wewould like to give a short characteristic of decision tree learning.

D ECISION T REE R EPRESENTATION

75

Generally speaking, decision tree learning is a method for approximating discrete-valued
target functions. The function learned is represented by a decision tree. Decision tree
learning is robust to noisy data and thus very popular. In fact, decision tree learning is oneof the most widely used and practical methods for inductive inference. There are several
decision tree learning methods around that differ to a certain extent with respect to theircapabilities and requirements. Nevertheless, all these algorithms also share many features.
In particular, it can be said that decision tree learning is best suited for problems having thefollowing characteristics.
1. Instances of the problem are represented by attribute-value pairs. The instances canbe described by a fixed set of attributes and their values. For example, in Lecture 7
we presented the weather data set. The attributes in this problem are outlook,temperature, humidity, and windy. Each attribute could take a small fixed
set values, e.g., for outlook the set of possible is {sunny, overcast, rainy} and fortemperature the set of values is {hot, mild, cool}. It should be noted, however, that suitable extensions to the basic algorithms allow handling of real-valued
attributes as well.
2. The target function has discrete output values. In our weather data set these output
values have been {yes, no} and in our data set from molecular biology {P, N}.
Of course, decision tree learning methods can also handle more than two possible
discrete output values. There are also decision tree learning algorithms around thatcan even handle target functions with real-valued outputs, but applications of decision
trees in such settings are less common.
3. Disjunctive descriptions may be required. As we shall see below, every function
described by a decision tree allows also a representation as disjunction.
4. The training data may contain errors. As already mentioned, decision tree learning
methods are robust to errors. The type of errors decision tree learning methods canhandle comprises errors in the classification (e.g., some of the protein sequences inour example from the last lecture may have erroneously been classified as positive by
the domain experts) as well as errors in the attribute values describing these examples(e.g., normal instead of high may have appeared erroneously in our weather data set
as value for humidity).
5. The training data may contain missing attribute values. For example, some attributes
in a true weather data set may be missing, since at some particular day it was impossible to measure the temperature because of a technical problem.
Since many practical problems have been found that fit the characteristics given above,
decision tree learning is often used. Examples comprise the classification of medical patients by their diseases, loan applicants by their likelihood of defaulting on payment andmany more.
Now, we are ready to deal with the problem how to learn decision trees.

76

L ECTURE 7: D ECISION T REE L EARNING

7.2.

The Basic Decision Tree Learning Algorithm

The material we are going to represent here is based on Quinlan’s (1986) ID3 algorithm
and its successor C4.5 (cf. Quinlan(1993)). These algorithms employ a top-down, greedy
search through the set of possible decision trees. Our exposition here roughly corresponds
to the ID3 algorithm. Intuitively, this algorithm first answers the question “which attributeshould be tested at the root of a decision tree?”For seeing how to answer this question, let us try the different attributes from the weather
data set first. Figure 7.2 shows the four possible choices for the root and the resulting tree
stumps for the weather data.
outlook

sunny
yes
yes
no
no
no

temperature

overcast
yes
yes
yes
yes

rainy
yes
yes
yes
no
no

hot
yes
yes
no
no

humidity

high
yes
yes
yes
no
no
no
no

mild
yes
yes
yes
yes
no
no

cool
yes
yes
yes
no

windy

normal
yes
yes
yes
yes
yes
yes
no

false
yes
yes
yes
yes
yes
yes
no
no

true
yes
yes
yes
no
no
no

Figure 7.2: Decision tree stumps for the weather data.

So, how did we obtain these decision tree stumps? First, we have selected the attributeto be put into the root, e.g., outlook, or temperature. There are five entries in theweather data set having the value sunny for outlook. Two of them classify yes andthree classify no. Moreover, there are four entries having the value overcast for outlook
and all of them classify yes. Finally, there are five entries having the value rainy foroutlook and three of them classify yes while two classify no. Thus, we get the tree

T HE BASIC D ECISION T REE L EARNING A LGORITHM

77

stump as drawn in Figure 7.2 when taking outlook as root. The remaining three stumps
are obtained analogously.
Our goal is to arrive at small decision trees. Any leaf with only one class – yes or no– will not have to be split further. This should happen as early as possible. But clearly, if aleaf has more than one class, we have to repeat the process recursively. Of course, we canthus generate all possible decision trees and then choose the smallest one from the set of
all decision trees obtained. But intuitively it is clear, that this approach is computationallyinfeasible, since the number of all trees to be generated will be exponential in the numberof attributes. So, how can we recover? The idea is to decide which of the decision tree
stumps is the best for further processing. Once we have made a choice, all other decision
tree stumps are abandoned and we recursively repeat the process only for the stump chosen.
Suppose we have a measure of purity for each node. Then we could choose the attributethat produces the purest daughter nodes. The measure of purity we are going to use is called
information and measured in bits. But unlike usual bits, our bits here can also be less thanone. We shall look at details of how to compute these bits later. These bits are then used tocompute another measure that will be actually used to decide which of the stumps is best.
This measure Quinlan (1986) has used and it is called information gain. The information
gain is a statistical property measuring how well a given attribute separates the training
examples according to their target classification. Thus, ID3 computes the information gain
for each of the tree stumps obtained and chooses one having the highest information gain.
So, let us assume that we can compute the bits mentioned above. Bits are computed forthe number of yes and no classes at the leaf nodes. For the decision tree stump having
outlook in its root, there are three leaf nodes, i.e., [2, 3], [4, 0], and [3, 2]. The information
values of these nodes areinfo([2, 3]) = 0.971bits
info([4, 0]) = 0.0bits
info([3, 2]) = 0.971bits .
Next, the average information value of these informations is calculated. Here we take thenumber of instances into account that go down each branch, i.e., five down the first, four
down the second and five down the third one. This gives a total of 14 instances, and thus
we obtain45
5· 0.971 +· 0.0 +
· 0.97114
14
14= 0.693bits .

info([2, 3], [4, 0], [3, 2]) =This calculation is also applied to the training examples corresponding just to the root.
There are 14 examples, nine of which are classified yes and five of which are classified
no. Using the still unknown formula we getinfo([9, 5]) = 0.940bits .

78

L ECTURE 7: D ECISION T REE L EARNING

The information gain is then just the difference, i.e.,gain(outlook) = info([9, 5]) − info([2, 3], [4, 0], [3, 2]) = 0.247bits .
Analogously, we can computegain(temperature) = 0.029bits
gain(humidity) = 0.152bits
gain(windy) = 0.048bits .
So, outlook has the highest information gain and is thus chosen.
Next, we continue recursively. Clearly, a further split on outlook will produce nothing
new, thus only the remaining three attributes are considered. Looking again at the weather
data set, we see that there are the following five examples having the value sunny.
outlook
sunny
sunny
sunny
sunny
sunny

temperature
hot
hot
mild
cool
mild

humidity
high
high
high
normalnormal

windy
false
true
false
false
true

play
no
no
no
yes
yes

So, we look at the possible roots temperature, humidity and windy for the subtree starting at the sunny branch (cf. Figure 7.3).
Then one gets the following values for the information gain
gain(temperature) = 0.571bits
gain(humidity) = 0.971bits
gain(windy) = 0.020bits .
Thus, at this point humidity is selected as splitting attribute. Then, we see that all remaining classes contain either yes or no. Thus, there is no need to split these nodes further
and the process terminates for this branch. Continued application of this idea finally leads
to the decision tree shown in Figure 7.1.
Ideally, the process finishes when all leaf nodes contain only one classification. But it
might be impossible to reach this situation if the training data contain two sets of attributeswith identical values but different classes. Thus, one stops when no further split is possible.
This explains the basic idea of the ID3 algorithm. We still have to provide the remaining
details. So, we continue by revealing the secret of how to compute the information gain.
For defining information gain precisely, we start from recalling the definition of a measure commonly used in information theory to measure in a precise way the amount of information in a source. This measure is called entropy. Since this measure is very important

T HE BASIC D ECISION T REE L EARNING A LGORITHM

outlooksunnyovercast

outlook

rainy

sunny

temperature

hot

mild
yes
no

no
no

79

overcast

rainy

humidity

cool

high
no
no
no

yes

normalyes
yes

outlooksunnyovercast

rainy

windy

false
yes
no
no

true
yes
no

Figure 7.3: Expanded decision tree stumps for the weather data.

in our context of decision tree learning and in other parts of data mining we shall describe
it here in some more detail.
For the sake of motivation, let us first assume that a contest is taking place. We have a
black box that emits source symbols from a source S with a source alphabet S = {s1 , s2 }.
99
1
The probability to see s1 is p1 = 100
and the probability to see s2 is p2 = 100. The winnerof the contest is the first one who can name both symbols in S. Thus, the winner is the first
who has full information about the set S. Of course, we assume that neither contestant has
seen the source symbols beforehand. Now, suppose that in the first round the first contestantgets source symbol s1 while the second one gets s2 . So, at this point, who is more likely to
win the contest?
1
Since the first contestant still has to receive s2 whose probability of occurrence is 100
99
while the second one has to wait seeing s1 whose probability of occurrence is 100, it isintuitively clear that the second contestant is more likely to win than the first.

Thus, in some sense, the second contestant has received more information about S fromthe source symbol s2 than did the first contestant. Therefore, it should be clear that, independently of how we define precisely the information obtained from a source symbol, the80

L ECTURE 7: D ECISION T REE L EARNING

less likely a source symbol is to occur, the more information we obtain from an occurrenceof that symbol, and conversely. Consequently, the information obtained from a source symbol cannot be a function of the symbol itself, but rather of the symbol’s probability p ofoccurrence. Thus, we shall use I(p) to denote the information obtained from a source symbol with probability p of occurrence. We shall make the following reasonable assumptions
about the function I(p), defined for all 0 < p ≤ 1.
Assumption 0. I(p) is not the constant 0 function.
Assumption 1. I(p) ≥ 0 for all p.
Assumption 2. I(p) is continuous.
Moreover, we usually assume that the events of seeing si and sj on different transmissions are independent. Thus, the information obtained from knowing that both si and sj
have occurred should be the sum I(pi ) + I(pj ). Since the probability of both events occurring is pi pj we shall make
Assumption 3. I(pi pj ) = I(pi ) + I(pj ).
Now, the remarkable fact about these four assumptions is that essentially one function
satisfies them. This is expressed by the following theorem.
Theorem 7.1. A function I(p) is satisfying Assumptions 0 through 3 made above if andonly if it has the form
1
I(p) = c log ,pwhere c > 0 is a constant and log is the logarithm to the base 2.
Proof. That the log function is satisfying Assumptions 1 through 3 is a well-known factfrom calculus. For the converse direction, we start from Assumption 3, and obtain
I(p2 ) = I(pp) = I(p) + I(p) = 2I(p) .
Now, it is easy to show by induction that
I(pn ) = nI(p) for all n ∈ N+ .

(7.1)

Taking into account that (7.1) holds for all p ∈ (0, 1] directly yields
111I(p) = I(p n ·n ) = I((p n )n ) = nI(p n )Consequently, we can conclude1

I(p n ) =1
I(p) .
n(7.2)

Since (7.1) and (7.2) are valid for all n ∈ N+ we additionally havenI(p m ) =n
I(p) for all n, m ∈ N+ .
m

But this means that
I(pr ) = rI(p) for all positive rational numbers q .

(7.3)

I NFORMATION , E NTROPY AND I NFORMATION G AIN

81Now, recalling that for every positive real number r there is a sequence (rn )n∈N of positive
rational numbers rn such that limn→∞ rn = r we get by the continuity of the power function
limn→∞ prn = pr . Hence, the continuity of function I (cf. Assumption 2) and (7.3) implythat
I(pr ) = I( lim prn ) = lim I(prn ) = I(p) lim rn = rI(p)
n→∞

n→∞

n→∞

for all positive real numbers r.
Now, let us fix any q with 0 < q ≤ 1. Since any p satisfying 0 < p ≤ 1 can be written
as p = q logq p and since I(p) ≥ 0 (cf. Assumption 1) as well as I(p) not constant 0 (cf.
Assumption 0), we haveI(p) = I(q logq p ) = I(q) logq p = c log

1pfor some constant c > 0.
As the proof of Theorem 7.1 shows, we additionally have I(1) = 0 nicely matching ourintuition. Moreover, the arbitrary multiplicative constant c can be absorbed in the units ofmeasurement of information.
7.3.

Information, Entropy and Information GainFirst, we define information. Using the facts presented above, we naturally arrive at thefollowing definition.
Definition 16. The information I(p) obtained from a source symbol s with probability p > 0 of occurrence is given by
I(p) = log

1.
p

The unit of measurement of information is the bit, as already said above. The connection
to the binary unit (also called bit) comes from the following observation. If the source is S
and has alphabet S = {0, 1} and both symbols are equally likely, i.e., p0 = p1 = 1/2, thenthe information given by either source symbol is I(1/2) = log 2 = 1. Thus, if the source
randomly emits one binary digit (bit), then the information obtained by a single emission is
one binary unit (bit).
Example. A PC monitor is capable of displaying pictures made up of pixels at a resolution of 1024 columns by 768 rows (or higher). Hence, if each pixel can be in any oneof 256 colors, there are a total of 28·1024·768 different pictures. If each of these pictures is
considered to be equally likely, the probability of a given picture is 2−6291456 . Thus, theinformation obtained from a single picture is
I = log 26291456 = 6291456 bits .
Next, consider a random speech of 1000 words from a 10 000 word vocabulary (whatwould be amazing for a politician). Then the probability of speaking any sequence of 1000

82

L ECTURE 7: D ECISION T REE L EARNING

words from such a vocabulary is 10000−1000 . Consequently, the amount of information
obtained from such a speech is
I = log 100001000 = 1000 log 10000 < 14000 bits .
This clearly shows that a picture is worth more than a thousand words.
Now, we are ready for defining the concept of entropy.
Definition 17. Let S = (S, P ) be a source with source alphabet S = {s1 , . . . , sq } andprobability distribution P = {p1 , . . . , pq }. The average information obtained from a single
sample from S isqX1
pi log pi .
pi log = −pi I(pi ) =H(S) =
pi
i=1
i=1
i=1
q
X

q
X

The quantity H(S) is called entropy of the source. For the sake of convenience, we
define in all calculations involving entropy 0 log 0 to be 0.
Now, given a collection S, containing positive and negative examples of some target
concept, the entropy of S relative to this boolean classification is
Entropy(S) = −p⊕ log p⊕ − p log p ,(7.4)

where p⊕ is the proportion of positive examples in S and p is the proportion of negative
examples in S.
Now, let S be a sample, let A be any attribute and let Values(A) be the set of all possible
values for attribute A. Furthermore, let Sv = {s s ∈ S and A(s) = v}. Then we formallydefine the information gain as follows.
Definition 18.
gain(S, A) = Entropy(S) −Xv∈Values(A)|Sv |· Entropy(Sv ) .
|S|

Here Entropy(S) is the original entropy of the sample and the second term is the expected
entropy after S has been partitioned using attribute A.
We continue by a having a closer look at Formula (7.4). First, let us assume that there
are no positive examples, i.e., p⊕ = 0. Consequently, all examples are negative and hence
p = 1. Then, recalling that we have defined 0 log 0 = 0, we get
Entropy(S) = −p⊕ log p⊕ − p log p= 0 log 0 − 1 log 1 = 0 .
Analogously, if all examples are positive, i.e., p⊕ = 1 and p = 0, we also obtain
Entropy(S) = −p⊕ log p⊕ − p log p= −1 log 1 − 0 log 0 = 0 .

83

I NFORMATION , E NTROPY AND I NFORMATION G AIN

Next, suppose that the sample contains an equal number of positive and negative examples, i.e., p⊕ = p = 1/2. Then,
Entropy(S) = −p⊕ log p⊕ − p log p
1
1 1
1= − log − log
2
2 2
2
1 1
=
+ =1.
2 2
Note that we always have p⊕ + p = 1. Thus, we have to study the function
f (x) = −x log x − (1 − x) log(1 − x)
for x ∈ (0, 1). Recalling a bit calculus, it is easy to see thatf 0 (x) = − log x + log(1 − x) ,and that f 0 (x) = 0 if and only if x = 1/2. Since f 0 (x) > 0 for all x < 1/2, we see that f (x)is monotonically increasing for all x ∈ (0, 1/2). Furthermore, f 0 (x) < 0 for all x > 1/2,
and thus f (x) is monotonically decreasing for all x ∈ (1/2, 1). Finally,


1
1
00
f (x) = −<0ln 2 x(1 − x)for all x ∈ (0, 1), and therefore f (x) is concave. Putting it all together, we get the graph ofthe entropy function displayed in Figure 7.4.

1

Entropy(S)

0.8
0.6
0.4
0.2
0

0

0.2

0.4

0.6

0.8

p⊕

Figure 7.4: Entropy function in dependence of p⊕ .

1

84

L ECTURE 7: D ECISION T REE L EARNING

Next, we illustrate the use of the entropy function and information gain as given in
Definition 18 by looking again at our weather data set S. We have a total of 14 examples
and 9 of them are positive and 5 of them are negative. Consequently, p⊕ = 9/14 andp = 5/14. So, we can compute Entropy(S) and obtain
Entropy(S) = −
=

9
5
5
9
· log
−
· log
14
14 14
14

1
[14 log 14 − 9 log 9 − 5 log 5] = 0.940bits ,14i.e., the value we have already provided at Page 77. Note that is computationally advantageous to perform the calculation as described above, i.e., without working out the fractions
and taking the logarithm of them.
Next, we compute the information gain for the attributes outlook, temperature,humidity and windy by using the formula provided in Definition 18. The attribute
outlook can take the three values sunny, overcast and rainy. Looking at the weather dataset, we directly get |Ssunny | = 5, |Sovercast | = 4 and |Srainy | = 5. Furthermore,
2 3
3
2
Entropy(Ssunny ) = − log − log = 0.971bits
5
5 5
5
Entropy(Sovercast ) = 0bits
3 2
2
3
Entropy(Srainy ) = − log − log = 0.971bits
5
5 5
5
Putting it all together, we thus obtaingain(S, outlook) = 0.940 −545· 0.971 −·0−· 0.971 = 0.246bits
14
14
14

and analogously
gain(S, temperature) = 0.029bits
gain(S, humidity) = 0.152bits
gain(S, windy) = 0.048bits ,i.e., again the values we already have provided at Page 77.
So far we have discussed entropy of a sample for the special case where the target classification is boolean. More generally, if the target attribute can take on c different values,
then the entropy relative to this c-wise classification is defined as
Entropy(S) = −cXpi log pi ,i=1where pi is the proportion of the sample S belonging to class i. Note that logarithm is stillto the base 2, because entropy is measured in bits. Also note that maximum is now log c.
This completes the description of the ID3 algorithm. So, what else can be said about theID3 algorithm? For answering this question, let us look at the hypothesis space used by theID3 algorithm.

ID3’ S H YPOTHESIS S PACE

7.4.

85

ID3’s Hypothesis Space

ID3’s hypothesis space is the set of all decision trees. Thus, it is a complete spaceof finite discrete-valued functions, relative to the available attributes. Since every finite
discrete-valued function can be represented by some decision tree, ID3 avoids one of the
major risks of methods that search incomplete hypotheses spaces: That the hypothesis space
might not contain a correct description of the target function.
Conceptually, we may think of ID3 as a learning algorithm that searches the hypothesis
space of all decision trees for one that correctly describes the training data. The search isguided by using the information gain measure.
ID3 maintains only a single current hypothesis as it searches through the space of decision trees. This contrast, for example, our pattern language learner presented in Lecture 6
which conceptually maintains the set of all patterns that are consistent with the text seen so
far in every learning step. From this set, it then chooses a descriptive pattern and outputs
it. Thus, ID3 does not have the ability to determine which alternative consistent hypotheses
are still available.
Moreover, ID3 in the form presented does not perform any backtracking in its search.
Once an attribute has been selected as root in the relevant subtree, this choice is neverreconsidered. While this improves the efficiency of the decision tree learner, it does notnecessarily guarantee that the learned decision tree is the smallest possible. In other words,
ID3 always selects the locally optimal solution and may thus converge to a locally optimal
solution. However, this locally optimal solution may be less desirable than the globally
optimal solution that would have been encountered along a different branch of the search.
ID3 uses all training examples at each step in the search to make a statistically based
decision (i.e., by using the information gain) regarding how to refine its current hypothesis.
The advantage of this approach is that the resulting search is much less sensitive to errors
in individual training data than other methods using individual training data for making
decisions.
Next, we turn our attention to another very important problem, i.e., the inductive bias
used by the ID3 algorithm.
7.5.

Inductive Bias in Decision Tree Learning

Roughly speaking the inductive bias is the set of assumptions that, together withthe training data, deductively justify the classification assigned by the learner to future
examples. For example, the weather data set contains 14 examples. However, there are 36
possible examples, and of course, besides explaining the training data, one is also interested
in decision trees that classify the still unseen data correctly. Since there may be many
possible decision trees that correctly explain the training data, every learner has to makea choice. The explicitely or implicitly made assumptions determining this choice are theinductive bias of the learner.

86

L ECTURE 7: D ECISION T REE L EARNING

The ID3 algorithm chooses the first acceptable tree it encounters in its search throughthe hypothesis space. Roughly speaking, the ID3 algorithm selects in favor of shorter trees
over longer ones, and selects the tree that places the attributes with highest information gain
closest to the root. So, there is a subtle interplay between the attribute selection heuristics
used by ID3 and the particular training examples it encounters .hus, it is difficult to characterize precisely the inductive bias used by ID3. Nevertheless, as a first approximation we
may say:
Shorter trees are preferred over larger trees. Trees that place high information gain
close to the root are preferred over those that do not.
Of course, one has also to answer the question whether or not this is a good or not so good
inductive bias. But it is beyond the scope of the introductory nature of our course to provide
a thorough study of this problem.

References[1] J.R. Q UINLAN (1986), Induction of decision trees, Machine Learning 1, No.1, 81 –106.
[2] J.R. Q UINLAN (1993), C4.5: Programs for Machine Learning, Morgan Kaufmann,
San Mateo, CA.