Concept learning as bidirectional search through a lattice of hypotheses: the covers relation, the general to specific ordering, Find-S and its failure modes, and the S and G update procedure that keeps every solution alive at once.
Printed copy: every task answer and every model answer below is revealed. On screen they sit behind a click, which is how you should meet them first.
the theory exam... tests both for factual knowledge as well as for synthetic knowledge... we also want to see that you can uh bring things across different chapters uh together because as you know by now uh the course is largely incremental.(Lecturer, T9). The links above are examinable content, not decoration. This Part also feeds forward: Part 13 reuses this lattice and these two borders under new names.
Deck p.2 is the scope slide for the last technical block of the course. It lists the techniques that make up machine learning and data mining, "decision trees, neural networks, probabilistic graphical models, support vector machines, reinforcement learning, etc.", and then sends each of them somewhere else: "See 'Machine Learning and Inductive Inference'" and "'Artifical Neural Networks and Deep Learning'" (the spelling is the slide's). What stays in this course is the sentence underneath: This part: applications of search methods, with two of them, "Today: Version spaces (bidirectional search)" and "Next week: Pattern mining".
So read this Part as a search chapter that happens to be about learning. The state space is a lattice of concept descriptions, the successor relation is "make this description one step more specific" (or one step more general), and the search runs from both ends at once.
The lecturer opened with the same framing and added why the descriptions are worth having: these are symbolic methods, meaning that the solution is itself a description you can read, and at the end of the worked trace he reads the learned concept aloud as an ordinary English sentence (T11, paraphrased). A version space returns something interpretable; a trained neural network does not.
The running example is a student recording whether a meal produced an allergic reaction. Four input attributes and one label:
Write the five rows as labelled examples, and say how many of the five are positive. Then, using the attribute domains given on p.5 (3 restaurants, 3 meals, 7 days, 2 costs), say how many possible examples exist in total and how many of them the table leaves unlabelled.
Positives: <Alma 3, Breakfast, Friday, Cheap> and <Alma 3, Lunch, Saturday, Cheap>. Negatives: <De Moete, Lunch, Friday, Expensive>, <Sedes, Breakfast, Sunday, Cheap>, <Alma 3, Breakfast, Sunday, Expensive>. Two positive, three negative.
Total examples: 3 × 3 × 7 × 2 = 126 (the multiplication is printed on p.5). The table labels 5 of them, so 121 are unlabelled. That ratio is the entire point: the concept has to be guessed from 5 observations and then applied to the other 121.
Deck p.5 states the general shape: a set of all possible examples X, a Boolean function defined on it (here Reaction: Restaurant × Meal × Day × Cost → Bool), values known for some examples only, and the instruction "Find an inductive 'guess' of the concept, that covers all the examples!".
The slide draws one closed curve inside the set of all possible examples. Write the two conditions it satisfies, in terms of the word "covers", and say which of the two the unlabelled points constrain.
(1) It covers every positive example. (2) It covers no negative example. Neither condition says anything about the unlabelled points: they are free, which is exactly why many different curves qualify. That freedom is the subject of the next slide.
The slide asks "How to chose?" (the typo is the slide's). Say in one sentence why several curves are all consistent with the data, and what version spaces will do about it instead of choosing.
The data is incomplete: only 5 of 126 examples carry a label, so every curve that separates those 5 correctly is consistent, no matter how it treats the other 121. Version spaces refuse to pick one. They keep the whole set of consistent hypotheses, represented by its two borders. The lecturer's phrasing for that policy is quote 32, in section 19 below.
Pages 8 to 11 kill the two obvious answers. The first is to accept exactly the positives: the concept becomes (Alma 3 and Breakfast and Friday and Cheap) or (Alma 3 and Lunch and Saturday and Cheap), which the slide labels "Does NOT generalise any examples!". The second is its mirror image, accept everything except the negatives.
Under the "memorise the positives" concept, what does the model predict for <Alma 3, Lunch, Monday, Cheap>, and what would it predict for any of the 121 unlabelled examples?
Negative, and negative for all 121. The concept covers exactly two examples, so every example outside the training positives is rejected. Its training accuracy is perfect and its generalisation is nil, which is why the slide calls it a bad choice.
This concept is not(De Moete and Lunch and Friday and Expensive) and not(Sedes and Breakfast and Sunday and Cheap) and not(Alma 3 and Breakfast and Sunday and Expensive). It is consistent with all five labelled rows. Why is it still useless, and which later section of the deck brings this exact expression back?
It predicts positive for all 121 unlabelled examples, so it has generalised nothing either: it has only restated the negatives. It comes back on p.64, where allowing negation and disjunction into the hypothesis language makes the version space collapse into exactly this pair of restatements, G as the conjunction of negated negatives and S as the disjunction of positives. That is the inductive bias argument in section 23.
Deck p.12 gives the fix: "We introduce a fixed language of concept descriptions: = hypothesis space". The concept "can only be identified as being one of the hypotheses in this language", which "avoids the problem of having 'useless' conclusions" and "forces some generalization/induction to cover more than just the given examples".
For the allergy problem the language is 4-tuples, one slot per attribute, where a slot holds either a value or the wildcard ? meaning "this attribute does not matter":
Counting ? as one extra value per attribute, how many hypotheses does this language contain, including ⊥? Compare that with the 2126 of p.62. Then say which single hypothesis covers exactly 126 examples and which covers exactly 0.
(3+1) × (3+1) × (7+1) × (2+1) = 4 × 4 × 8 × 3 = 384 tuples, plus ⊥, so 385 hypotheses. Against the 2126 subsets of X that a fully expressive language could name (deck p.62), 385 is a violent restriction, and that restriction is precisely the inductive bias that makes generalisation possible.
[?, ?, ?, ?] covers all 126 examples; ⊥ covers 0.
Two definitions carry the whole Part. Deck p.15 states them:
Read the second one slowly, because the containment runs the opposite way to the intuition of the word "general". The more general hypothesis is the one whose covered set is larger. So [?, Lunch, ?, ?] is more general than [?, Lunch, ?, Cheap]: replacing a value by a wildcard can only add examples.
The slide gives x1 = <Alma 3, Lunch, Monday, Expensive>, x2 = <Sedes, Lunch, Sunday, Cheap>, and h1 = [?, Lunch, Monday, ?], h2 = [?, Lunch, ?, Cheap], h3 = [?, Lunch, ?, ?]. For each of the six pairs say whether the hypothesis covers the example, then order h1, h2, h3 by generality.
h1 covers x1 (Lunch and Monday both match), h1 does not cover x2 (Sunday is not Monday). h2 does not cover x1 (Expensive is not Cheap), h2 covers x2 (Lunch and Cheap match). h3 covers both (only Lunch is required).
Ordering: h3 is more general than both h1 and h2. h1 and h2 are not comparable: neither covered set contains the other, since h1 catches expensive Monday lunches and h2 catches cheap Sunday lunches. Incomparability is normal in this lattice and it is why G and S are sets rather than single hypotheses.
A student writes "h1 is more general than h2 if h1 has more question marks than h2". Give a pair of hypotheses from the allergy language where that rule gives the wrong answer.
Take h1 = [?, ?, Monday, ?] (three wildcards) and h2 = [Alma 3, ?, Friday, Cheap] (one wildcard). Counting wildcards says h1 is more general. But covers(h2) is not a subset of covers(h1): h2 covers Friday examples that h1 rejects. The two are incomparable. Counting wildcards only works when the two tuples agree on every slot where both hold a value; the definition to apply is always the subset one.
Constructed, in the sample paper's format (2023 theory exam, part 1 style)
In a hypothesis language, hypothesis h1 is more general than hypothesis h2 if and only if covers(h1) is a subset of covers(h2).
Deck p.16 translates the tuple notation into logic: a tuple is a conjunction of explicit, individual properties. [?, lunch, Monday, ?] means Meal = Lunch ∧ Day = Monday. The two special hypotheses become the two truth values: [?, ?, ?, ?] is TRUE and ⊥ is FALSE.
Write [De Moete, ?, ?, Expensive] as a conjunction, and write "the meal was a dinner on a Sunday" as a tuple. Then say which logical connective this language cannot express, and where in the deck that limitation bites.
[De Moete, ?, ?, Expensive] is Restaurant = De Moete ∧ Cost = Expensive. "Dinner on a Sunday" is [?, Dinner, Sunday, ?].
The language has no disjunction (and no negation). That bites on p.55, where the target concept [Alma 3, Breakfast, ?, Cheap] ∨ [Alma 3, Lunch, ?, Cheap] cannot be represented, so the version space collapses to empty, and again on pp.61 to 64 where adding disjunction destroys learning altogether.
Page 17 gives the special case where every attribute is Boolean. Then an example is just the set of items that are true, a hypothesis is also a set of items, and the two relations become set inclusion:
Items are {Blue, Red, Green, Yellow, Brown, AI}. The first customer bought {Blue, Red, Green}. Does the hypothesis {Blue, Green} cover that example? Is {Blue} more general or more specific than {Blue, Green}? Explain why the two subset signs face the same way but mean opposite things.
Yes: {Blue, Green} ⊆ {Blue, Red, Green}, so the hypothesis covers the example (a hypothesis is a list of demands, and the basket meets them). {Blue} is more general than {Blue, Green}, because {Blue} ⊆ {Blue, Green} and it makes fewer demands, so it covers more baskets.
The two statements read the same way once you notice that adding an item to a hypothesis always shrinks the covered set. This exact reversal is what Part 13 formalises as anti-monotonicity, and the 2023 theory MC 1.5 is a true or false question about it.
This is the section that makes the rest of the Part necessary, so do not treat it as optional colour. In the allergy language each attribute is flat: a value or a wildcard, nothing in between. A taxonomy (a concept hierarchy) adds the middle layers. Deck p.18 uses colour: any_color at the top, then mono_color and poly_color, then the individual colours, then ⊥.
The examples are red +, purple −, blue +. The slide says mono_color is a correct description. Verify both conditions, and then explain the slide's justification "there is no path from mono color to purple" in terms of covers.
covers(mono_color) = {red, blue, green}. It contains both positives (red, blue) and does not contain the negative (purple), so both conditions hold. "No path down from mono_color to purple" is exactly the statement purple ∉ covers(mono_color): in a taxonomy, covers(v) is the set of leaves reachable downward from v.
The damage a taxonomy does is this: the minimal generalisation of a hypothesis and an example need not be unique. In a flat conjunction language, generalising to cover a new example means replacing every disagreeing value by ?, and there is exactly one way to do that. In a taxonomy you may have two incomparable common ancestors, and there is no principled reason to prefer either. Deck p.26 draws the counterexample and section 9 below works it through.
The rules are: h covers e iff h is a substring of e; h1 is more general than h2 iff h1 is a substring of h2. Given examples dabbcdefgm and xxabbcdez, is abbcde a valid hypothesis covering both? Is bbcd more or less general than abbcde? Why does "substring" mean consecutive positions here?
Yes: abbcde occurs inside both strings, so it covers both. bbcd is a substring of abbcde, so bbcd is more general: shorter demands, more examples matched. The slide states the consecutiveness explicitly, "the first string occurs on consecutive positions in the second", so abde would not count as covering abbcde.
The drawn lattice runs from the empty string at the top through a, b, then aa, ab, ba, bb, then the three-letter strings. Give the minimal specialisations of ab, and say what makes this search space different from every other one in this Part.
The minimal specialisations of ab are the strings that contain it with one extra letter: aab, bab, aba, abb. Each is one step less general.
The difference: the space is infinite, since strings have no maximum length (T11, paraphrased). That is why the shift-of-bias idea on p.65 is stated for strings: cap the length at 10, then 15, then 20 (section 23).
Exercise session 9, question 1 (warm-up: colours), verbatim setup
Consider the colour concept hierarchy: ? over mono and poly; mono over blue, green, red; poly over orange, purple. Apply the Version-Space algorithm with the following examples: red: +, purple: −, blue: +.
Initialise G = {[?]}, S = {[⊥]}.
S and G now hold the same hypothesis, so the version space has converged to [mono], and the solution deck marks that slide "Convergence".
What earns the marks: showing that [poly] was expanded rather than discarded (a negative example does not simply delete a branch, you descend it until the negative falls out), and showing why [orange] died, namely the S-side check, not the negative example.
The same sheet contrasts this with the two naive algorithms: Find-S on the same data gives [red] then [mono]; Dual Find-S must choose between [mono] and [orange] and "commits to a single one". Version spaces keep both alive until the data kills one.
Deck p.21 states concept learning in the Given/Find form the course uses for every problem type:
Note that the coverage relation is part of the input, not an afterthought: itemsets, taxonomies and strings are all "H plus a covers relation", and changing the relation changes the problem.
Page 22 then states the inductive learning hypothesis: "If a hypothesis approximates the target function well over a sufficiently large number of examples, then the hypothesis will also approximate the target function well on other unobserved examples." This is the assumption that makes induction worth doing, and it is not proved anywhere in the course.
hypothesis here is used with a different meaning than the one that we have used uh until now.(Lecturer, T11, quote 30). Two different meanings, one word. Everywhere else in this Part a hypothesis is an element of H, a concept description like [Alma 3, ?, ?, Cheap]. In the phrase "inductive learning hypothesis" it means an assumption about the world, namely that fitting the sample transfers to unseen data. If an exam sentence uses the word, check which of the two it means before answering.
Find-S is the S-side of the version space method, run alone. Start at ⊥, walk through the positive examples only, and whenever the current hypothesis fails to cover the next positive, replace it by the minimal generalisation that does.
After example 1 the hypothesis is [Alma 3, Breakfast, Friday, Cheap]. The next positive example is <Alma 3, Lunch, Saturday, Cheap>. Compute the new hypothesis, then say what Find-S does with the three negative rows sitting between them in the table.
Compare slot by slot and wildcard every disagreement: Restaurant agrees (Alma 3), Meal disagrees (Breakfast versus Lunch) so ?, Day disagrees (Friday versus Saturday) so ?, Cost agrees (Cheap). New hypothesis: [Alma 3, ?, ?, Cheap]. This is verified against the deck's own trace and reproduced by executing the algorithm in Python.
Find-S skips the negatives entirely. It never looks at them, which is the property the next section is about. On this particular table the answer happens to be consistent with the negatives, which is luck, not a guarantee.
Deck p.25 states what Find-S buys you, and the precondition it needs: "For itemsets and simple conjunctions (without taxonomies): the minimally generalisation of a hypothesis and an example is unique", and then "find-S yields a unique concept that covers all positives and no negatives, it is the minimally general generalisation of the + examples".
Page 29 adds the one genuinely nice property, and it is worth keeping because version spaces inherit it: Find-S does not have to remember the previous examples. "If the previous h already covered all previous examples, then a minimal generalization h' will too!" Generalising can only add coverage, so the work already done cannot be undone.
Three failures, all on the same small taxonomy. In it, Hacker covers {Beth, Jo}, Scientist covers {Beth, Jo, Alex}, and Football player covers {Alex}.
The current hypothesis is [Beth] and a new positive example Jo arrives. List every hypothesis that covers both, then list the minimal ones. Which word in the Find-S pseudocode is now unjustified?
Covering both: Hacker, Scientist, and the top of the hierarchy. Minimal among those: Hacker and Scientist, and they are incomparable, since neither covered set contains the other ({Beth, Jo} versus {Beth, Jo, Alex}).
The unjustified word is "the" in "the minimal generalisation". With two minima the algorithm has to choose, and nothing in the data tells it how.
this Find-S assumes that this minimal generalization is unique(Lecturer, T11, quote 31, on the word "the" in the pseudocode). He also states the other half of the same quote plainly:
It is oblivious to the negative examples in your data set.These two sentences are the reason version spaces exist. If an exam asks what version spaces improve on Find-S, these are the two answers; noise is not one of them (see section 18).
Data: Beth +, Alex −, Jo +. Find-S generalises [Beth] to include Jo and happens to pick Scientist. Why is the result wrong, and would the other choice have been wrong too? What does that tell you about the recovery options?
Scientist covers Alex, which is labelled negative, so the returned concept is inconsistent with the data. The other choice, Hacker, covers only {Beth, Jo} and is a perfectly good solution. So a correct answer existed and the algorithm missed it purely by choosing badly.
Recovery options: none, because Find-S keeps a single hypothesis and never revisits. Version spaces solve it by refusing to choose, keeping both Hacker and Scientist in S until a negative example kills one.
In the second hierarchy on this slide, Scientist is the only node above Beth, Jo and Alex. With D = {Beth +, Alex −, Jo +}, what does Find-S return, and is the trouble noise or an impoverished language? How would you tell the two apart from the output alone?
Find-S must generalise [Beth] to cover Jo, and the only node available is Scientist, which also covers the negative Alex. It returns Scientist and reports nothing wrong.
Here the cause is the language: no hypothesis in H separates {Beth, Jo} from {Alex}, because the hierarchy offers no such node. Noise would mean the labels themselves conflict. You cannot tell them apart from Find-S's output, because the output is the same silent, wrong hypothesis. Version spaces at least signal the problem by collapsing to an empty S or G (deck p.55, section 19).
Everything in this Part is dual. Dual Find-S starts at the top instead of the bottom, walks the negative examples instead of the positives, and specialises instead of generalising:
The slide's trace specialises the top hypothesis using the first negative <De Moete, Lunch, Friday, Expensive> by choosing [?, Breakfast, ?, ?]. Name another single-attribute specialisation that also excludes that negative, and say what the existence of your alternative proves about Dual Find-S.
Any of these excludes it: [Alma 3, ?, ?, ?], [Sedes, ?, ?, ?], [?, Dinner, ?, ?], [?, ?, Monday, ?] through [?, ?, Thursday, ?], [?, ?, Saturday, ?], [?, ?, Sunday, ?], [?, ?, ?, Cheap]. Eleven of the fifteen one-step specialisations of the top exclude this example (the eleventh is the slide's own [?, Breakfast, ?, ?]; the four that do not exclude it are De Moete, Lunch, Friday and Expensive, exactly the negative's own values).
It proves that Dual Find-S faces the same non-uniqueness problem as Find-S, but immediately and in the flat language too: the minimal specialisation is essentially never unique. The lecturer makes the same point in T11 (paraphrased): the minimal specialisation is not unique, you may pick the right one, and if you pick the wrong one you run into trouble.
Deck p.32 states the construction in four lines:
The two frontiers get names. S is the set of maximally specific hypotheses consistent with the data so far; G is the set of maximally general ones. Everything between them, in the more-general-than ordering, is still a candidate solution. That set is the version space.
Deck p.2 calls this bidirectional search. Match the three parts: what plays the role of the forward frontier, the backward frontier, and the meeting test? Then name the one thing that is different from Part 4's bidirectional search.
S is the frontier growing upward from ⊥, G is the frontier moving downward from the top, and the meeting test is "do S and G share an element" (deck p.43). See Part 4 pp.68 to 73.
The difference: in Part 4 both searches explore the same graph and are driven by the same operators, and one path is the answer. Here the two frontiers are driven by different data, positives push S up and negatives push G down, and the answer is not a path but the whole region between the frontiers.
You are given a problem with three taxonomic attributes. Write the initialisation of S and G, and say how many hypotheses the version space contains at that moment.
G = {[?, ?, ?]} and S = {⊥}. At that moment the version space contains every hypothesis in H: nothing has been ruled out, because no example has been seen. Both sets are singletons; they only grow into genuine sets once a negative (for G) or a positive (for S) forces a branch.
The words "version space" appear in both exams, and they call for completely different answers.
The failure mode is answering one paper with the other paper's machinery. On 20 August, one sentence. On 18 August, the trace.
Constructed, in the sample paper's format (2023 theory exam, part 1 style)
The Version Spaces algorithm initialises S to the set of all training examples that are labelled positive.
Deck pp.34 to 37 give the rules twice: once for the very first example, where G and S are still singletons, and once in the general form, where they are sets. Learn the general form; the first is a special case of it.
Replace all hypotheses in G that cover the negative example by ALL minimal specialisations that do NOT cover it.
Invariant: only hypotheses more specific than the ones of G are still possible, because they do not cover the negative example.
Replace all hypotheses in S that do not cover the positive example by ALL minimal generalisations that DO cover it.
Invariant: only hypotheses more general than the ones of S are still possible, because they do cover the positive example.
Three details decide whether your trace is right.
First, "all" is not decoration. Find-S and Dual Find-S choose one and can choose wrong (section 9). Version spaces branch instead. On a negative example a single G element typically explodes into several; on the allergy example the top hypothesis has fifteen one-step specialisations and three of them survive (section 16).
Second, minimal is defined by the ordering, not by the number of steps. A minimal specialisation of h that excludes the negative is a maximal element of the set of hypotheses strictly below h that do not cover it. Usually that is one step down a taxonomy. But if a one-step child still covers the negative, that child is not a candidate and you must keep descending under it until the negative falls out. The session 9 sheet says this in as many words for the colour hierarchy: "we can either specialize towards [mono] or alternatively we can descend into [poly] (which still covers purple) towards [orange]".
Third, the two searches constrain each other immediately, through the checks in section 13, and the newest example prunes the opposite border, through the checks in section 14. A specialisation that survives the negative example can still die on the spot because no S element sits below it.
A student processes the negative <De Moete, Lunch, Friday, Expensive> against G = {[?, ?, ?, ?]} and writes G = {[Alma 3, ?, ?, ?]}, arguing that this excludes the negative and is minimal. Give two reasons the answer loses marks, and give the corrected G assuming S = {[Alma 3, Breakfast, Friday, Cheap]}.
Reason 1: it selected one minimal specialisation. The rule says all of them, which is the only difference between version spaces and Dual Find-S. Reason 2: the student did not show the filter, so there is no evidence the other candidates were considered and rejected for a stated reason.
Corrected: of the fifteen one-step specialisations, four cover the negative ([De Moete, ?, ?, ?], [?, Lunch, ?, ?], [?, ?, Friday, ?], [?, ?, ?, Expensive]) and are excluded, and eight of the remaining eleven fail the S-side check. G = {[Alma 3, ?, ?, ?], [?, Breakfast, ?, ?], [?, ?, ?, Cheap]}, which is deck p.46. Verified by executing the update in Python over the allergy language.
Constructed, in the sample paper's format (2023 theory exam, part 1 style)
When the Version Spaces algorithm processes a negative example, it replaces every G-hypothesis that covers the example by one minimal specialisation that does not cover it.
Both new hypotheses have to pass a test on the opposite border before they are allowed into the set.
S = {[Alma 3, Breakfast, Friday, Cheap]}. Of the eleven one-step specialisations of the top that exclude <De Moete, Lunch, Friday, Expensive>, which three pass this filter, and state the general rule you used in one sentence.
[Alma 3, ?, ?, ?], [?, Breakfast, ?, ?] and [?, ?, ?, Cheap]. Each holds a value that the S element also holds, so each covers the S element.
Rule: a candidate g survives only if some s in S has covers(s) ⊆ covers(g). Equivalently, in a tuple language, every non-wildcard slot of g must be an ancestor-or-equal of the corresponding slot of s. Anything else, for example [Sedes, ?, ?, ?] or [?, ?, Monday, ?], cannot possibly cover all the positive examples, so it is deleted immediately rather than carried along.
Write the p.39 rule as a formal condition on a candidate s and the set G. Then answer: if you forgot both checks, would the algorithm return the wrong answer, or just work harder?
Condition: a candidate s survives only if some g in G has covers(s) ⊆ covers(g).
Both are pruning rules justified by the invariants, so they never delete a hypothesis that could still be a solution: a candidate they delete already fails to be consistent with the examples seen so far. Skipping them therefore leaves the final answer unchanged while carrying dead hypotheses through every later step. In an exam, though, carrying them is how a trace becomes unmanageable by example three, and the sets you write down will not match the model answer at the intermediate steps, which is where the marks are.
Sections 12 and 13 update one border and filter it against the other. Two more prunes act on the border that was not updated, and a third removes elements that have become redundant within a border.
"The new negative example can also be used to prune all the S-hypotheses that cover the negative example." The slide adds the reason the check is needed at all: "Invariant: only works for the previous examples, not the last one!" The invariant guarantees that S is consistent with everything seen before, so only the newest example can break it, and it must be checked explicitly. An S element that covers a negative example is dead, because every generalisation of it will keep covering that negative.
"The new positive example can also be used to prune all the G-hypotheses that do not cover the positive example." A G element that misses a positive cannot be repaired: specialising it further only loses more examples.
"If a hypothesis from G is more specific than another hypothesis from G: eliminate it!" with the reason "Invariant acts as a wave front: anything above G is not allowed. The most general elements of G define the real boundary", and the reminder "Obviously also for S!" (there, remove any S element that is more general than another S element).
Write both halves of the redundancy rule, for G and for S, using the words "more general" and "more specific" correctly. Then say whether this rule is required for correctness, quoting what the lecturer says about it.
For G: remove any hypothesis that is more specific than another hypothesis in G. For S: remove any hypothesis that is more general than another hypothesis in S. Both keep the border extreme: G as general as possible, S as specific as possible.
Not required for correctness. The lecturer says the step is strictly speaking redundant: without it the algorithm still returns the correct result, it merely costs extra effort, and the invariant that G holds the maximally general consistent hypotheses and S the maximally specific ones no longer holds (T11, paraphrased). So the answer stays right but the sets stop being borders, and an exam answer that reports a non-extreme G will not match the model answer.
Constructed, in the sample paper's format (2023 theory exam, part 1 style)
In the Version Spaces algorithm, a hypothesis is removed from G whenever it is more general than another hypothesis in G.
Deck p.43: if G and S get a common element, the version space has converged to a solution, and "Remaining examples need to be verified for the solution."
The lecturer spells out the choice this leaves you (T11, paraphrased): if you are willing to assume that a solution exists inside the hypothesis space, you may stop at convergence; if you are not, you must process the remaining examples, and if one of them contradicts the surviving hypothesis then no solution exists in that space at all.
Case A: S = G = {[Alma 3, ?, ?, Cheap]}. Case B: S = {[Alma 3, ?, Monday, Cheap]} and G = {[Alma 3, ?, ?, ?], [?, ?, Monday, ?]} and the data has run out. Which is convergence, which is termination, and how many solutions does each report?
Case A is convergence: the borders meet, so exactly one hypothesis remains and it is the unique solution consistent with the data. Case B is termination by running out of examples (deck p.54): the borders have not met, and every hypothesis between them, six of them in that particular example, is still a correct description. Reporting only S, or only G, or only one hypothesis in Case B loses the marks, because the answer to "what did you learn" is the whole interval.
Five examples, in the order the table gives them. Follow the two borders, and at each step ask the four questions in order: does the border need updating, what are all the minimal moves, which survive the opposite-border filter, and what has become redundant.
Write the two sets, and say how many of the 126 possible examples the version space currently classifies as positive with certainty.
G = {[?, ?, ?, ?]}, S = {⊥}. Zero examples are classified positive with certainty: an example counts as certainly positive only when every S element covers it (deck p.57), and ⊥ covers nothing. Symmetrically, zero are certainly negative, since the top covers everything.
Why is the minimal generalisation of ⊥ that covers this example the example itself, and what would S look like after two positives arriving in the other order?
Because ⊥ covers nothing, the smallest hypothesis covering one example is the fully specified tuple for that example: any wildcard would cover more. So S = {[Alma 3, Breakfast, Friday, Cheap]}.
Order does not matter here: after both positives S = {[Alma 3, ?, ?, Cheap]} either way, since minimal generalisation over a flat conjunction language is commutative. That is a useful sanity check, but be careful: with taxonomies the intermediate sets can differ, even though the final version space does not.
Count the fifteen one-step specialisations of [?, ?, ?, ?] and split them into three groups: those excluded because they match the negative example, those excluded because they do not generalise the specific model, and those that remain. Give the sizes and the survivors.
Fifteen = 3 restaurants + 3 meals + 7 days + 2 costs. Excluded for matching the negative: 4 ([De Moete, ?, ?, ?], [?, Lunch, ?, ?], [?, ?, Friday, ?], [?, ?, ?, Expensive]), which are exactly the negative example's own four values. Excluded for not generalising S = {[Alma 3, Breakfast, Friday, Cheap]}: 8 (Sedes, Dinner, and the six non-Friday days). Remaining: 3, namely [Alma 3, ?, ?, ?], [?, Breakfast, ?, ?], [?, ?, ?, Cheap].
4 + 8 + 3 = 15. Note that Friday is doubly disqualified: it is the negative's value, so it appears with the red cross on the slide. Verified by executing the update in Python.
The lecturer checks three properties of this picture before moving on. State them and verify each for G = {[Alma 3, ?, ?, ?], [?, Breakfast, ?, ?], [?, ?, ?, Cheap]}, S = {[Alma 3, Breakfast, Friday, Cheap]}.
(1) No G element is more general than another, so none is redundant: the three cover genuinely different sets (an expensive Alma 3 dinner is covered only by the first, an expensive De Moete breakfast only by the second, a cheap Sedes lunch only by the third). (2) None of them covers the negative <De Moete, Lunch, Friday, Expensive>. (3) All of them cover the positive <Alma 3, Breakfast, Friday, Cheap>, which is the S element. He walks through these three in exactly this order on the recording (T11, paraphrased), and they are the same three sanity checks worth writing at the end of every exam step.
Compute the new S, then say which G element is removed and by which rule. Also note the wording on the slide itself and say what it should read.
New S = {[Alma 3, ?, ?, Cheap]}: the minimal generalisation of [Alma 3, Breakfast, Friday, Cheap] that covers the new positive, wildcarding Meal and Day.
[?, Breakfast, ?, ?] is removed from G, by the cross-prune of section 14: the new positive example is a Lunch, so that G element does not cover it and can never be repaired. Two distinct rules fire in one step, one on each border.
The slide's own label reads "Positive example: minimal specialization of [Alma 3, Breakfast, Friday, Cheap]". The operation performed is the minimal generalisation: positives generalise S. The lecturer describes it correctly in the recording. Do not copy the slide's word into an exam answer.
G = {[Alma 3, ?, ?, ?], [?, ?, ?, Cheap]}, S = {[Alma 3, ?, ?, Cheap]}. Process the negative <Sedes, Breakfast, Sunday, Cheap>: which G element must change, what is the only surviving specialisation, and why does it not enter G?
[Alma 3, ?, ?, ?] does not cover the negative (the restaurant is Sedes), so it stays. [?, ?, ?, Cheap] does cover it and must be specialised. Of its one-step specialisations, only [Alma 3, ?, ?, Cheap] both excludes the negative and still generalises S: choices on Meal or Day never generalise S, and De Moete or Sedes do not either.
It does not enter G because it is more specific than [Alma 3, ?, ?, ?], which is already in G: the redundancy rule of p.42. So G shrinks to {[Alma 3, ?, ?, ?]}. Verified in Python; this reproduces the slide's note that "The only specialization that is introduced is pruned, because it is more specific than another general hypothesis".
Process the last negative against G = {[Alma 3, ?, ?, ?]}, S = {[Alma 3, ?, ?, Cheap]}. Then state the learned concept, and state precisely what the algorithm has and has not proved.
[Alma 3, ?, ?, ?] covers the negative, so it is specialised. Meal and Day choices do not generalise S; restaurant choices either cover the negative (Alma 3) or do not generalise S (De Moete, Sedes); the surviving specialisation is [Alma 3, ?, ?, Cheap], which is exactly the S element. G = S = {[Alma 3, ?, ?, Cheap]}: convergence.
Proved: this is the only hypothesis in this language consistent with all five examples. Not proved: that it is true. Five examples out of 126 and a language restricted to conjunctions are both assumptions, and the inductive learning hypothesis of p.22 is what licenses the leap.
Exercise session 9, question 2 (playing cards), verbatim setup
Playing cards have two characteristics, "value" (7, 8, 9, 10, Jack (J), Queen (Q), King (K), Ace) and "kind" (Hearts, Diamonds, Spades, Clubs), organised in two hierarchies: value has ? over Number (1, 7, 8, 9, 10), Picture (J, Q, K) and Ace; kind has ? over Red (Diamonds, Hearts) and Black (Clubs, Spades). Examples, in order: 7 of Diamonds: +, Ace of Clubs: −, Queen of Hearts: −, 9 of Hearts: +, 8 of Clubs: −. Apply the Version-Space algorithm.
The three steps that carry the marks:
Final answer: the concept is [Number, Red], a red number card, and the version space has converged, so there is nothing else consistent with the five examples.
Two pages, one per example type. They are duals of each other: swap G with S, specialisation with generalisation, and more general with more specific, and one becomes the other.
The page reads: 1 G := {T}; 2 S := {⊥}; 3 for each new positive p; 4 remove from G any hypothesis inconsistent with p; 5 for each s in S not consistent with p; 6 remove s from S; 7 add to S all minimal generalisations h of s such that 8 h is consistent with p and 9 some member of G is more general than h; 11 remove from S any hypothesis more general than another hypothesis in S. Say which section above each of lines 4, 7, 9 and 11 corresponds to, and what "consistent with p" means for a positive example.
Line 4 is the positive cross-prune of section 14 (deck p.41). Line 7 is the positive update rule of section 12 (p.35 and p.37), with the word "all". Line 9 is the optimisation of section 13 (p.39). Line 11 is the redundancy rule of section 14 (p.42), in its S form.
For a positive example, "consistent with p" means covers p. For a negative example on the next page it means the opposite, does not cover n. The single word "consistent" flips meaning with the label, which is the most common misreading of these two pages.
Without looking, write the negative-example loop by dualising the positive one, then check it against the slide. Which four substitutions do you make?
Substitutions: G for S and S for G; specialisation for generalisation; "more specific" for "more general"; negative for positive. The result is the slide: remove from S any hypothesis inconsistent with n; for each g in G not consistent with n, remove g and add all minimal specialisations h of g such that h is consistent with n and some member of S is more specific than h; finally remove from G any hypothesis more specific than another hypothesis in G.
This duality is the first property listed on p.53, and it halves what you have to memorise: learn one page and a transformation, not two pages.
It's also important that you can execute and simulate these algorithms in a pen and paper uh version on a small scale.(Lecturer, T4, quote item 8, said of the search algorithms and applying verbatim here). The exercise half of the exam has asked for exactly this on version spaces once already, in 2023 (section 21). Practise the two pseudocode pages by running them, not by reading them.
Deck p.53 lists three properties. Two are good news, one is the single most examinable sentence in the Part.
Explain how one mislabelled example destroys the answer, in terms of the update rules. Then say what the algorithm reports when it happens, and why the report is ambiguous.
Suppose the true concept is c and one example that c covers is labelled negative. Processing that example specialises away every G element that covers it, and c is one of them, so c is removed from the version space and can never come back: the updates only ever shrink the space. The lecturer calls the end state a collapsing version space: an example arrives that the unique remaining hypothesis does not treat correctly, which empties the space (T11, paraphrased).
What you see is S or G becoming empty. That report is ambiguous because deck p.55 gives it two possible causes: the data is inconsistent (noise), or the target concept cannot be expressed in H. The algorithm cannot tell you which.
2023 sample theory exam, part 1, MC 1.6, verbatim
The Version Spaces algorithm improves upon the simple Find-S algorithm, allowing it to deal with noisy examples.
The borders have not met, and the data has run out. The slide draws the state G = {[Alma 3, ?, ?, ?], [?, ?, Monday, ?]} and S = {[Alma 3, ?, Monday, Cheap]}, and says: "Then all these hypotheses and all intermediate hypotheses are still correct descriptions covering the test data. VS makes NO unnecessary choices!"
Given G = {[Alma 3, ?, ?, ?], [?, ?, Monday, ?]} and S = {[Alma 3, ?, Monday, Cheap]}, list every hypothesis that lies between them, and confirm the total.
Six in total: the two G elements, the one S element, and the three intermediates [Alma 3, ?, ?, Cheap], [Alma 3, ?, Monday, ?], [?, ?, Monday, Cheap]. Verified by enumerating all 384 tuples of the allergy language in Python and keeping those below some G element and above the S element: exactly these six.
This is why "the answer" to a version space question is a pair of sets rather than one hypothesis. Anything strictly between the borders is equally consistent with the data.
version spaces will end up with all the possible solutions and will not make any unnecessary choices... you never make a choice unless it is strictly necessary.(Lecturer, T11, quote 32). This is the one-sentence answer to "what do version spaces give you that Find-S does not", and it is the property that makes the two borders meaningful: the algorithm commits only when the data forces it.
"Then either: the data is inconsistent (noise?)" or "the target concept cannot be represented in the hypothesis-language H". The slide's example of the second cause: the target is [Alma 3, Breakfast, ?, Cheap] ∨ [Alma 3, Lunch, ?, Cheap], and with examples <Alma 3, Dinner, Sunday, Cheap> −, <Alma 3, Breakfast, Sunday, Cheap> +, <Alma 3, Lunch, Sunday, Cheap> −, "This cannot be learned in our language H".
Take the slide's three examples in the printed order. Track S only, and show why it dies. Then say why the disjunction is the culprit.
The first example is negative, so S stays {⊥}. The second is positive, so S becomes {[Alma 3, Breakfast, Sunday, Cheap]}. The third is negative, <Alma 3, Lunch, Sunday, Cheap>, and the S element does not cover it, so S survives this step. G, however, is now squeezed: it must exclude both an Alma 3 Sunday Dinner and an Alma 3 Sunday Lunch while still covering an Alma 3 Sunday Breakfast, which in a conjunction language forces Meal = Breakfast; and any hypothesis with Meal = Breakfast will fail as soon as the language is asked to also accept the Lunch positives that the true concept contains.
The culprit is that the target is a disjunction of two conjunctions. A single tuple can say "Breakfast" or "Lunch" or "any meal", never "Breakfast or Lunch". No element of H equals the target, so consistency with enough examples becomes impossible and a border empties.
With six hypotheses alive, some questions are worth asking and some are not. The slide: <Alma 3, Lunch, Monday, Expensive> is "Classified negative by 3 hypotheses, Classified positive by 3 hypotheses, Is the most informative new example". A query whose answer is the same under every surviving hypothesis teaches you nothing; a query that splits the survivors in half removes half of them whatever the answer is.
Using the six hypotheses of p.54, rank these by informativeness: <Alma 3, Lunch, Monday, Cheap>, <Sedes, Lunch, Sunday, Cheap>, <Alma 3, Lunch, Monday, Expensive>. Give the split for each.
<Alma 3, Lunch, Monday, Cheap>: covered by 6 of 6, so the answer is known in advance under the assumption that a solution exists, and learning it removes nothing. <Sedes, Lunch, Sunday, Cheap>: covered by 0 of 6, equally uninformative. <Alma 3, Lunch, Monday, Expensive>: 3 of 6, so whichever label comes back, three hypotheses die. Ranking: the third is the most informative, the other two are worthless. All three counts were computed by evaluating the six hypotheses in Python and they match the slides.
Constructed, in the sample paper's format (2023 theory exam, part 1 style)
If the Version Spaces algorithm terminates with an empty G-set, the training data must contain noise.
You do not need convergence to classify. With the six hypotheses of p.54 still alive, deck pp.57 to 60 give four cases, and two shortcuts that make the check cheap.
The slide says "It is enough to check that it is covered by the hypothesis in S! (all others generalise these)". Prove the shortcut in one line, and say how many coverage tests it saves here.
Every hypothesis in the version space is more general than some element of S, and more general means covering a superset. So if every S element covers x, every hypothesis in the space covers x. One test per S element instead of one per hypothesis: here 1 instead of 6, and in a real trace S is usually tiny while the interior is large.
State the negative-side shortcut, then verify it on <Sedes, Lunch, Sunday, Cheap> against G = {[Alma 3, ?, ?, ?], [?, ?, Monday, ?]}.
"It is enough to check that it is not covered by any hypothesis in G (all others specialize these)." Check: [Alma 3, ?, ?, ?] fails on Sedes, [?, ?, Monday, ?] fails on Sunday. Neither covers it, so nothing in the space covers it, so the example is certainly negative.
Which three of the six cover <Alma 3, Lunch, Monday, Expensive>, and what single attribute value decides the split? What is the exam-safe wording for this verdict?
The three that do not mention Cost: [Alma 3, ?, ?, ?], [?, ?, Monday, ?], [Alma 3, ?, Monday, ?]. The three that require Cheap all fail, because the example is Expensive. Verified in Python: 3 of 6.
Exam-safe wording: "cannot be decided" or "undecided", and say why, namely that the surviving hypotheses disagree. The session 9 solution deck writes it as Maybe. Do not invent a majority vote.
Which single hypothesis covers this example? Is 1/6 a probability? Say what the deck claims for it.
Only [?, ?, Monday, ?] covers it: the example is at Sedes, so the three Alma 3 hypotheses fail, and it is Expensive, so [?, ?, Monday, Cheap] fails. Verified in Python: 1 of 6.
The slide's claim is deliberately weak: "Can only be classified with a certain degree of precision" and "Probably does not belong to the concept: Ratio = 1/6". It is a count of surviving hypotheses, not a probability: it assumes every surviving hypothesis is equally likely, which nothing in the method justifies. Both cases 3 and 4 are the same verdict, undecided, with case 4 leaning.
Exercise session 9, question 3 (in search of a drummer), verbatim setup and questions
A rock band selects 5 candidates from 900 applicants and labels them. Hierarchies (as printed in the session 9 solutions): Hobby ? over Cool and Boring; Cool over Super-cool and Dancing; Super-cool over Music-Only and Stage-Diving; Boring over Fishing and Reading. Music ? over Useful (Hardrock, New-wave) and Not-Useful (Jazz, Hiphop). Age ? over Very Young (0 to 16), Young (17 to 29), Old (30 to 80). Photo ? over Handsome, Neutral, Ugly.
Examples in order: [Fishing, Hiphop, 16, Handsome] −; [Stage-diving, New-wave, 18, Neutral] +; [Dancing, Hardrock, 32, Ugly] −; [Music-only, Hardrock, 25, Handsome] +; [Stage-diving, Jazz, 29, Ugly] −. "Apply the Version Space algorithm on this example. Indicate per example how the spaces G and S evolve. Clearly indicate which hypotheses are pruned away, and why. What is (or what are) the concept(s) that are deducted?" Then classify [Music-only, Hardrock, 32, Handsome], [Stage-diving, Hiphop, 18, Neutral], [Dancing, New-wave, 22, Ugly].
Step by step, with the prunes named:
Concepts deduced: S = {[Super-cool, Useful, Young, ?]}, G = {[Super-cool, Useful, ?, ?], [?, Useful, Young, ?]}, so the band should interview candidates who are super-cool and like useful music, with young age either required or not depending on which hypothesis is right.
The three CVs: [MO,HR,32,Ha] is Maybe (more specific than [SC,Us,?,?], not more specific than S). [SD,HH,18,Ne] is No (Hiphop is Not-Useful, so no G element covers it). [Da,NW,22,Ug] is Maybe (more specific than [?,Us,Yo,?], but Dancing is not Super-cool so it fails S).
2023 sample exercise exam, question 3 (2 points), verbatim
You're tasked to learn a model capable of determining under which circumstances (after participating in some sport training) an athlete experiences muscle strain. You have access to the taxonomic hierarchies specified in Figure 1, 2, 3, and 4. The hypothesis space thus consists of 4-tuples, representing the month of the event, the day of the week or weekend, the duration of the event in minutes, and the kind of sport they participated in. You already have a partially learned version spaces model:
Refine this model by integrating the following two examples (in order). The first example is a negative example: [August, Saturday, 60, Running]. Determine the new values for G and S after processing this example. The second example is a positive example [July, Monday, 45, Biking]. Once again, specify the G-set and S-set after taking this example into account.
The printed question sets the clause "after participating in some sport training" off with dashes; this pack renders them as parentheses, since the pack uses no dashes. Nothing else is changed.
Month. ? over Winter, Spring, Summer, Autumn. Winter covers December, January, February, March. Spring covers March, April, May, June. Summer covers June, July, August, September. Autumn covers September, October, November, December. The four boundary months each have two parents, so this is a lattice, not a partition: the printed figure shows the crossing edge from Autumn down to December, and the edge counts confirm it (16 edges for 12 months, that is 4 months with two parents).
Day. ? over Week (Monday to Friday) and Weekend (Saturday, Sunday). An ordinary tree.
Duration. ? over Short (15, 30, 45), Average (45, 60, 75), Long (75, 90, 105, 120). Again overlapping at the boundaries: 45 and 75 have two parents each (10 edges for 8 values).
Sport. ? over Indoor (Swimming, Table tennis, Basketball, Gym) and Outdoor (Ball games, Biking, Running), with Ball games further over Soccer, Rugby, Tennis. A tree, three levels deep on one branch.
Why the overlap matters, and how to check it in the exam room: the given G-set contains [Spring, ?, ?, ?] while the given S-set is [June, Week, Long, Ball games]. The version space invariant requires every G element to be more general than some S element. That only holds if June is under Spring, which is exactly what the crossing edges say. If you read the month figure as a clean three-month partition, the model you were handed would already be inconsistent. Use the invariant to check your reading of any hierarchy you are given.
First, S. A negative example prunes any S element that covers it. [June, Week, Long, Ball games] does not cover it (June is not August, Week does not contain Saturday, Long does not contain 60, Ball games does not contain Running: any one failure is enough). S is unchanged.
Then G, element by element.
Finally, redundancy elimination inside G. One survivor still has to go: [June, ?, ?, ?] is more specific than [Spring, ?, ?, ?], because June sits under Spring in the lattice, and [Spring, ?, ?, ?] is still in G. It is removed.
First, G. A positive example deletes every G element that does not cover it.
Then S. [June, Week, Long, Ball games] does not cover the positive, so replace it by all minimal generalisations that do. Attribute by attribute, take the least general common ancestors:
Each attribute has exactly one minimal common ancestor, so the minimal generalisation is unique: [Summer, Week, ?, Outdoor]. It must be more specific than some G element, and it is, namely both of them. Nothing to prune inside S, which has one element.
Sanity checks worth writing on the exam paper: no G element and no S element covers [August, Saturday, 60, Running] (all three require Week, and Saturday is Weekend); all three cover [July, Monday, 45, Biking]; and S is strictly below both G elements. So the version space has not converged. Enumerating the whole tuple space in Python gives exactly three surviving hypotheses: the two G elements and the S element itself, with nothing strictly between them.
Where the marks are: showing the two filters (does it exclude the negative, does it still bracket S) for each candidate, showing the redundancy deletion of [June, ?, ?, ?], and getting the second step's G deletions right. Answers that report only the final sets without the reasoning throw away most of the 2 points, and the printed instruction "Indicate per example how the spaces G and S evolve. Clearly indicate which hypotheses are pruned away, and why" from the exercise session says as much.
Robustness note: if you read the month hierarchy as a clean partition (Spring = March, April, May), the only change is that [June, ?, ?, ?] would stay in G after step 1, since it would no longer be more specific than [Spring, ?, ?, ?]. It would then be deleted anyway at step 2, because June does not cover July. The final answer is identical under both readings.
The 2023 paper puts version spaces in the exercise part, which is open book: "an open book exercise examination in which you again can bring everything related to the course on paper. So your course notes, possible textbooks" (Lecturer, T1, quote item 11). So do not memorise the two pseudocode pages, bring them. What you cannot bring is speed, and speed here comes from a fixed order of operations. Use this checklist per example:
Also note the answer-box discipline: "the boxes also give an indication of the expected length given a regular written font size" (Lecturer, T9, quote item 13). A whole page of enumeration will not fit, so write the candidate lists as short crossed-out columns like deck p.46 rather than as prose. The interactive drill for this is viz-versionspaces.html.
Everything so far had hypotheses that were tuples over taxonomies. Nothing in the algorithm requires that. It requires only three things: a covers relation, the resulting more-general-than ordering, and the ability to enumerate minimal moves in both directions. Session 9's fourth exercise replaces the tuple with a geometric object to prove the point.
Exercise session 9, question 4 (primitive visual display), verbatim setup
A square screen of 36 pixels, locations (x, y) with 0 ≤ x, y < 6. A coloured square is written [((x, y), n), colour], where (x, y) is the bottom-left corner and n is the side length, so the corners are (x, y), (x, y+n), (x+n, y), (x+n, y+n). Squares are closed, so they include their border, and a point is not a square, so n > 0. The colour comes from a hierarchy with white at the top over yellow, violet and cyan; yellow over red and green; violet over red and blue; cyan over green and blue; and ⊥ at the bottom. "Use the Version Spaces algorithm to determine which coloured square could be shown on the screen after these five examples", processed in the printed order: (0,1) red: no, (3,2) red: yes, (1,4) green: yes, (4,5) red: no, (4,0) green: no. Then: can you determine whether [(3,2), green], [(2,4), red] and [(3,5), blue] will be lit?
Initialise G = {[((0,0),5), white]}, the largest square in the largest colour, and S = {⊥}.
The moves that make this exercise instructive:
The three queries: [(3,2), green] is Yes (inside the S square, and yellow covers green). [(2,4), red] is Yes (inside the S square, yellow covers red). [(3,5), blue] is Maybe: it is outside the S square, so it is not certainly lit, but it is inside [((0,2),3), white], one of the two G elements, so it is not certainly dark either.
Note how the last verdict uses the two shortcuts from section 20 with no modification: covered by every S element means yes, covered by no G element means no, anything else is undecided.
Before running the algorithm on this language, you had to define three things that the tuple case gave you for free. Name them, and say which one carries the n > 0 restriction.
(1) The covers relation: a hypothesis covers an example when the point lies in the closed square and the hypothesis colour is an ancestor-or-equal of the example colour. (2) The ordering that follows from it: square containment plus colour ancestry, both required. (3) The minimal moves in each direction: shrink a square by one unit in one of four ways, or step one level down the colour lattice, and dually for growing.
The n > 0 restriction belongs to the third: a side-1 square has no minimal specialisation on the geometry axis, because a point is not a legal hypothesis, so the only way down from it is the colour axis.
Deck p.61 poses the question honestly: the language of conjunctions fails on the disjunctive concept of p.55, so why not use a more expressive language? Assume H' that allows conjunctions as before, plus disjunction and negation, for example (Restaurant = Alma 3) ∨ not(Day = Monday).
Where does 126 come from, where does 2126 come from, and how does 2126 compare with the 384 tuples of the restricted language from section 3?
126 = 3 restaurants × 3 meals × 7 days × 2 costs, the number of possible examples. 2126 is the number of subsets of that set, and a language with conjunction, disjunction and negation can name every one of them, so the hypothesis space becomes the full power set.
384 against 2126, which is about 8.5 × 1037. The restricted language throws away almost everything, and that discarded remainder is exactly what makes generalisation possible.
Run S mentally under H'. After the two positive examples, what is the single most specific hypothesis in H' that covers both, and why is it unique now when it was not before?
The disjunction of the two positives: [Alma 3, Breakfast, Friday, Cheap] ∨ [Alma 3, Lunch, Saturday, Cheap]. It is unique because H' contains it, and nothing smaller covers both: in the power set, the smallest set containing two points is the pair itself. Under the conjunctive language there was no such element, so S had to move up to [Alma 3, ?, ?, Cheap], which is where the generalisation came from.
Compare G and S here with the two "obvious, but bad" choices of pp.8 and 10. Then state the inductive bias the course adopts, in the deck's own words, and say what it costs.
They are the same two objects. S is the "memorise the positives" concept of p.8, and G is the "everything except the negatives" concept of p.10. A maximally expressive language does not learn; it stores. Every unlabelled example falls strictly between the borders, so every single one is undecided.
The bias the course adopts is printed on p.64: "The desired concept CAN be described as a conjunction of features". Its cost is p.55: concepts outside the language, such as a disjunction of two conjunctions, cannot be learned at all, and the version space collapses instead of warning you politely.
Deck p.65 gives the practical compromise, shift of bias: "Start VS with a very weak hypothesis language. If the concept is learned: OK. Else: Refine your language and restart VS." The slide's own summary of why this is attractive: it "Avoids the choice" and "Gives the most general concept that can be learned". The lecturer's example is the string language, allow length up to 10, then 15, then 20, and he names the analogy explicitly: this is iterative deepening applied to the hypothesis space rather than to the search depth (T11, paraphrased). Compare Part 4.
if you run the algorithm with 100% frequency on the positives and 0% frequency on the negatives, you get the same solution as the ones that are characterized by version spaces.(Lecturer, T12, quote 34). If you can state that sentence, you have the cross-chapter link the theory exam looks for.
| Term | Precise definition | Plain paraphrase | Exam phrasing |
|---|---|---|---|
| Concept learning | Given X, an unknown c: X → {−, +}, a language H with a covers relation, and labelled D ⊆ X, find h in H such that for all x in D, x is covered by h if and only if c(x) = + (p.21). | Guess the rule that says yes to the plus rows and no to the minus rows. | "Find an inductive 'guess' of the concept, that covers all the examples!" (p.5) |
| Hypothesis space H, and the inductive bias | The fixed language of concept descriptions; only its members can be returned (p.12). Choosing it is the inductive bias, the assumption that makes learning possible (p.64). | The set of shapes of answer you allow yourself, chosen before you see the data. | "In order to be able to learn, we need an Inductive Bias (= assumption)" (p.64) |
| covers(h) | The set of examples covered by h (p.15). For tuples, every attribute of the example is at or below the hypothesis value; for itemsets, h ⊆ e; for strings, h is a substring of e; for the screen exercise, the point lies in the closed square and the colour is below the hypothesis colour. | Which examples this description accepts. | "hypothesis h covers example e if and only if h ⊆ e" (p.17) |
| More general than | h1 is more general than h2 if and only if covers(h2) ⊆ covers(h1) (p.15). A partial order: many pairs are incomparable. | Accepts everything the other one accepts, and possibly more. | "h1 is more general than h2 if and only if h1 ⊆ h2" (p.17, itemset form) |
| Top and bottom | T = [?, ?, ..., ?] covers every example, and is written TRUE in the logical reading; ⊥ covers nothing and is written FALSE (pp.13, 16). | The "anything goes" description and the "nothing at all" description. | "Most general hypothesis: [?, ?, ?, ?] → T (representing the Top of the lattice)" (p.13) |
| Taxonomy | An attribute whose values form a hierarchy, so a hypothesis slot can hold an intermediate node. Coverage is descent in the hierarchy. Nodes may have several parents, which is what breaks uniqueness of minimal moves (pp.18, 26). | An attribute with in-between values, like Summer between July and "any month". | "You have access to the taxonomic hierarchies specified in Figure 1, 2, 3, and 4" (2023 exercise exam Q3) |
| Find-S | Start at ⊥, process positives only, and replace h by the minimal generalisation covering each uncovered positive (pp.23 to 24). Correct only when that minimal generalisation is unique, which holds for itemsets and plain conjunctions but not for taxonomies or strings (pp.25 to 27). | Climb from nothing, one positive at a time, and never look at the negatives. | "The Find-S algorithm finds the most specific hypothesis that captures all positive examples" (session 9 sheet) |
| Dual Find-S | The mirror: start at T, process negatives only, and take a minimal specialisation that excludes each covered negative (pp.30 to 31). Must choose among many, so it can also choose wrong. | Descend from "anything goes", one negative at a time. | "Both [mono] and [orange] are acceptable hypotheses, though Dual Find-S commits to a single one" (session 9 sheet) |
| Version space, S and G | The set of all hypotheses consistent with the data so far, represented by two borders: S, the maximally specific consistent hypotheses, and G, the maximally general ones. Everything between them, in the more-general-than order, is also consistent (pp.32, 54). | Two fences with all the surviving answers between them. | "G-set = {[Spring, ?, ?, ?], ...} S-set = {[June, Week, Long, Ball games]}" (2023 exercise exam Q3) |
| Minimal generalisation | On a positive example p and s in S that misses p: every h above s that covers p and is minimal in that set. All of them enter S, filtered to those below some G element (pp.35, 37, 39). | The smallest stretches of a description that let the new positive in. | "Add to S all minimal generalizations h of s such that h is consistent with p and some member of G is more general than h" (p.51) |
| Minimal specialisation | On a negative example n and g in G that covers n: every h below g that excludes n and is maximal in that set. If a one-step child still covers n you descend under it. All survivors enter G, filtered to those above some S element (pp.34, 36, 38). | The smallest tightenings of a description that shut the new negative out. | "Add to G all minimal specializations h of g such that h is consistent with n and some member of S is more specific than h" (p.52) |
| Redundancy elimination | Remove from G any hypothesis more specific than another in G, and from S any hypothesis more general than another in S (p.42). Not needed for correctness, but without it the sets stop being borders. | Keep only the outermost fence posts. | "If a hypothesis from G is more specific than another hypothesis from G: eliminate it!" (p.42) |
| Collapsing version space | S or G becomes empty. Two possible causes and no way to tell them apart: inconsistent data (noise), or a target concept not representable in H (pp.53, 55). | The fences cross, so nothing is left; either the data lies or the language is too poor. | "VS cannot deal with noise! If a positive example is given to be negative then VS eliminates the desired hypothesis from the Version Space G!" (p.53) |
| Partially learned concept | Classification before convergence: positive if every S element covers the example, negative if no G element covers it, otherwise undecided, optionally reported as a ratio of covering to non-covering hypotheses (pp.57 to 60). | Answer only when all survivors agree; otherwise say you cannot tell. | "Cannot be classified. Is covered by 3 and not covered by 3 hypotheses. No Conclusion!" (p.59); "Maybe" (session 9 solutions) |
| Shift of bias | Start with a weak hypothesis language; if the version space collapses, enlarge the language and restart (p.65). The lecturer likens it to iterative deepening. | Try the simplest kind of answer first, and only allow richer answers when the simple ones run out. | "Start VS with a very weak hypothesis language... Else: Refine your language and restart VS" (p.65) |
Machine Learning and Inductive Inference past paper, 12/01/2018 Q1, matching item, quoted in the pack's cross-course notes
Which single sentence is the expected answer on the ML paper (20 August) for "version space learners"?
Chapter index: index.html · Previous: Part 11, Planning · Next: Part 13, Pattern Mining · Drill: viz-versionspaces.html · Search by question: question-index.html