Machine Learning – Summer 2006 – Exercises
Steffen Hölldobler and Axel Großmann
Sheet 1: Introduction,
Concept Learning and the General-to-Specific Ordering
Solutions not to be handed in
Exercise 1
Exercise 1.3 in Mitchell’s book.
Exercise 2
Consider a learning world where each object (example) is described by a list of of n attributes, each
of which can take k possible discrete values.
(a) What is the size of the instance space, i.e., how many distinct instances can there be in this
world?
(b) How many different concepts are potentially possible in this world, i.e., what is size of the
concept space?
(c) What is the size of the hypothesis space in the following concept representation languages:
(i) Purely conjunctive expressions of conditions ‘attribute=value’ where only those conditions
appear that are required, i.e., attributes irrelevant to the concept are omitted. Examples
are:
C ↔ (A2 = small) ∧ (A5 = high)
C ↔ (A1 = low) ∧ (A2 = big) ∧ (A7 = short)
(ii) Purely conjunctive expressions of conditions ‘attribute in set’. Examples are:
C ↔ (A2 ∈ {small, medium}) ∧ (A6 ∈ {red, blue, yellow})
(iii) Unrestricted disjunctive normal form (DNF), i.e., a disjunction of conjunctive expressions.
Exercise 3
Exercise 2.2 in Mitchell’s book.
Exercise 4
Exercise 2.4 in Mitchell’s book.
Steffen Hölldobler and Axel Großmann
Sheet 1: Introduction,
Concept Learning and the General-to-Specific Ordering
Solutions not to be handed in
Exercise 1
Exercise 1.3 in Mitchell’s book.
Exercise 2
Consider a learning world where each object (example) is described by a list of of n attributes, each
of which can take k possible discrete values.
(a) What is the size of the instance space, i.e., how many distinct instances can there be in this
world?
(b) How many different concepts are potentially possible in this world, i.e., what is size of the
concept space?
(c) What is the size of the hypothesis space in the following concept representation languages:
(i) Purely conjunctive expressions of conditions ‘attribute=value’ where only those conditions
appear that are required, i.e., attributes irrelevant to the concept are omitted. Examples
are:
C ↔ (A2 = small) ∧ (A5 = high)
C ↔ (A1 = low) ∧ (A2 = big) ∧ (A7 = short)
(ii) Purely conjunctive expressions of conditions ‘attribute in set’. Examples are:
C ↔ (A2 ∈ {small, medium}) ∧ (A6 ∈ {red, blue, yellow})
(iii) Unrestricted disjunctive normal form (DNF), i.e., a disjunction of conjunctive expressions.
Exercise 3
Exercise 2.2 in Mitchell’s book.
Exercise 4
Exercise 2.4 in Mitchell’s book.
