Machine Learning Assignment - Detailed Answers (VTU Style)

Detailed, exam-ready answers with stepwise Find-S and Candidate-Elimination (referencing Tom M. Mitchell)

Q1) Explain choosing a representation for the target function. (8 marks)

Answer: The representation of the target function defines the hypothesis space H from which the learning
algorithm selects hypotheses. Mitchell emphasises that representation choice is fundamental because it
determines expressiveness, inductive bias, computational tractability, and interpretability. Below are the
main considerations and trade-offs a practitioner should document during design:
1. Expressiveness and adequacy:
• The representation must be rich enough to express the actual target concept. For example, Boolean
conjunctions cannot represent arbitrary disjunctions. If the true concept lies outside H, no learning
algorithm restricted to H can identify it. Thus, examine domain knowledge to choose an appropriate
class (conjunctions, DNF, decision trees, linear functions, neural nets, first-order rules).
2. Inductive bias and prior knowledge:
• Choice of representation implicitly defines an inductive bias—preferences among hypotheses. A
stronger bias (smaller H) reduces sample complexity when bias matches the problem, but risks biasing
away the correct concept if wrong. Preferred practice: align representation bias with background
knowledge about independence, attribute relevance, and expected functional form.
3. Generality ordering and search:
• The representation should allow a partial order (more-general-than) to support algorithms like Find-S
and Candidate-Elimination, and to facilitate incremental generalization/specialization. Hypothesis
spaces with clear neighborhood relations (minimal generalizations/specializations) enable efficient,
structured search.
4. Computational tractability:
• Consider hypothesis space size and whether search is feasible. Although very expressive
representations (e.g., arbitrary boolean formulas) are powerful, they often make exact search NP-hard.
Practical learners use greedy heuristics (decision trees) or restricted languages to remain tractable.
5. Interpretability and human-readability:
• For many applications (diagnosis, rule extraction, grading), interpretable forms (short rules, trees) are
preferred. Representation should balance predictive power with the need to explain decisions to
stakeholders.
6. Handling real-valued, missing, and relational data:
• Choose representations that naturally handle the attribute types encountered (continuous attributes
-> thresholds/linear models; relational structures -> first-order logic). Also plan strategies for missing
values (treat as special value, probabilistic handling, or instance weighting).
Conclusion: Select a representation that is adequately expressive, provides a reasonable inductive bias,
supports efficient search or learning, and meets interpretability and data-type requirements. Documenting
these choices and their trade-offs aligns with Mitchell's recommendations and is useful for VTU exam
answers.
Q2) Explain the final design of the Decision-Tree learning algorithm. (10 marks)
Answer: Decision-tree learning (e.g., ID3 and its descendants) constructs a tree where internal nodes test
attribute values and leaves assign class labels. The final practical design integrates attribute-selection
heuristics, handling of numeric/missing data, and pruning to control overfitting. Key components:
1. Data representation and input:
• Instances described by fixed attributes (categorical or discretized numeric). The goal is to partition
the input space into regions with (ideally) pure class labels.
2. Recursive greedy induction (divide-and-conquer):
• At each node, choose the attribute that best splits the training set according to a purity measure
 Machine Learning Assignment - Detailed Answers (VTU Style)

(information gain, gain ratio, or Gini index). Create child nodes for each attrib
the corresponding subset. Stop splitting when subsets are pure or when furt
3. Attribute selection criteria:
• Information Gain (entropy reduction): Measures reduction in class uncertainty. Gain ratio normalizes
information gain to prefer attributes with fewer values. Gini index is another impurity measure used in
CART.
4. Handling continuous attributes and missing values:
• Continuous attributes are split using thresholds (test candidate splits at midpoints between sorted
values). Missing attribute values can be handled by distributing instances probabilistically among
children, using surrogate splits, or treating 'missing' as a special value.
5. Stopping criteria and leaf labeling:
• Create a leaf when all examples in a node have the same label, or when no attributes remain, or
when the set of examples is too small. Label leaves by majority class or by probabilistic class
distribution to support confidence estimates.
6. Overfitting and pruning:
• Trees fit training data closely and can overfit noise. Practical design includes pruning: pre-pruning
(stop early using statistical tests) and post-pruning (grow full tree then prune subtrees that don't
improve validation performance). Complexity measures (minimal description length) and
cross-validation guide pruning.
7. Efficiency and heuristics:
• The greedy split selection avoids exponential search. Practical enhancements include handling
attributes with many values (use gain ratio), using fast sorting for numeric splits, and parallel
evaluation.
8. Interpretability and rule extraction:
• Paths from root to leaves correspond to human-readable decision rules. Post-processing can convert
trees into a compact rule set for easier interpretation.
Summary: The final design is a balance between a greedy, efficient split-selection procedure and pragmatic
mechanisms (thresholding, handling missing data, pruning) to ensure good generalization while retaining
interpretability.
Q3) Find the maximally specific hypothesis using Find-S algorithm (use Table-1). (6 marks)
Answer: Find-S finds the maximally specific hypothesis consistent with all positive examples (it ignores
negatives). We apply it step-by-step to the provided Table-1 which has six attributes: Sky, Temperature,
Humidity, Wind, Water, Forecast.
Training examples (from the provided scanned table):
1) Sunny, Warm, Normal, Strong, Warm, Same → Yes
2) Sunny, Warm, High, Strong, Warm, Same → Yes
3) Rainy, Cold, High, Strong, Warm, Change → No
4) Sunny, Warm, High, Strong, Cool, Change → Yes
Find-S steps:
• Initialize S to the most specific hypothesis: S = <ϕ, ϕ, ϕ, ϕ, ϕ, ϕ>.
• Process Example 1 (positive): set S to the example values → S = <Sunny, Warm, Normal, Strong,
Warm, Same>.
• Process Example 2 (positive): compare to S; Humidity differs (Normal vs High), so generalize that
 Machine Learning Assignment - Detailed Answers (VTU Style)

attribute to '?’ → S = <Sunny, Warm, ?, Strong, Warm, Same>.

• Example 3 is negative: ignored by Find-S.
• Process Example 4 (positive): Water (Warm vs Cool) and Forecast (Same vs Change) differ →
generalize those to '?’; Humidity already '?' → S = <Sunny, Warm, ?, Strong, ?, ?>.
Final Find-S hypothesis (maximally specific consistent with positives):
S = <Sky = Sunny, Temperature = Warm, Humidity = ?, Wind = Strong, Water = ?, Forecast = ?>.
Interpretation: Any instance with Sky=Sunny, Temperature=Warm and Wind=Strong is predicted positive
by this hypothesis, regardless of the other attributes. Caveat: Because Find-S ignores negatives, it can be
overly specific and may fail if missing positive examples or noise exist.
Q4) Explain the Version Space in detail. (8 marks)
Answer: The Version Space is the set of all hypotheses in hypothesis space H that are consistent with the
training data D. It formalizes the remaining uncertainty about the target concept after observing D and is
useful for reasoning about learnability and hypothesis uncertainty.
Representation with S and G boundaries:
• S (specific boundary): set of maximally specific hypotheses in VS. G (general boundary): set of
maximally general hypotheses in VS. Every hypothesis h in VS satisfies ∃s∈S, g∈G with g ≥ h ≥ s
under the generality ordering.
Incremental updating:
• For a positive example: remove G members that don't cover the example; minimally generalize S
members so they cover it, and prune dominated S members. • For a negative example: remove S
members that cover it; minimally specialize G members so they do not cover it, and prune dominated
G members.
Properties and significance:
• Version spaces make explicit which hypotheses remain plausible given data. They help quantify
uncertainty and guide further data collection (e.g., choose queries that maximally reduce the version
space). If S and G converge to the same hypothesis, the learner has identified the target (relative to H
and D).
Limitations:
• Maintaining full VS is infeasible for large or infinite H. The method is sensitive to noise: inconsistent
or mislabeled examples can make VS empty. Practical learners approximate this idea using boundary
maintenance or probabilistic analogues.
Q5) Candidate-Elimination algorithm applied stepwise to Table-1 (10 marks)
Answer: We explicitly track S and G after each example. Initial settings for six-attribute hypotheses:
Initial: S = <ϕ,ϕ,ϕ,ϕ,ϕ,ϕ> (most specific); G = <?,?,?,?,?,?> (most general).
Example 1: Sunny, Warm, Normal, Strong, Warm, Same → Positive
• Update S: minimally generalize to match example → S = <Sunny, Warm, Normal, Strong, Warm,
Same>
• Update G: remove any hypotheses inconsistent with the positive example (none removed because G
was completely general).
Example 2: Sunny, Warm, High, Strong, Warm, Same → Positive
• S differs in Humidity (Normal vs High) → generalize the humidity attribute to '?'. New S = <Sunny,
Warm, ?, Strong, Warm, Same>
• G remains <?,?,?,?,?,?> (still all-general).
Example 3: Rainy, Cold, High, Strong, Warm, Change → Negative
• Remove any S hypotheses covering the negative example (S does not cover it, so no change to S).
• G must be specialized to exclude this negative example. Minimal specializations of <?,?,?,?,?,?> that
 Machine Learning Assignment - Detailed Answers (VTU Style)

exclude this example while remaining consistent with S are:

g1 = <Sky=Sunny, ?, ?, ?, ?, ?> (exclude Rainy by fixing Sky=Sunny)
g2 = <?, Temperature=Warm, ?, ?, ?, ?> (exclude Cold by fixing Temperature=Warm)
g3 = <?, ?, ?, ?, ?, Forecast=Same> (exclude Change by fixing Forecast=Same)
So G becomes {g1, g2, g3}. Note they must remain more general than S; all three are more general
than current S.
Example 4: Sunny, Warm, High, Strong, Cool, Change → Positive
• Generalize S minimally where it conflicts with the positive: Water (Warm vs Cool) → '?'; Forecast
(Same vs Change) → '?'. New S = <Sunny, Warm, ?, Strong, ?, ?>
• Remove any members of G that do not cover this positive example. Evaluate g1,g2,g3:
- g1 = <Sunny,?,?,?,?,?> covers the example (Sky=Sunny) → keep.
- g2 = <?,Warm,?,?,?,?,?> covers the example (Temperature=Warm) → keep.
- g3 = <?,?,?,?,?,Same> does NOT cover the example (forecast is Change) → remove.
Final boundaries after all examples:
S = { <Sunny, Warm, ?, Strong, ?, ?> }
G = { <Sunny,?,?,?,?,?>, <?,Warm,?,?,?,?,?> }
Interpretation: The version space contains hypotheses requiring Sky=Sunny and Temperature=Warm (in
various combinations) but we have not narrowed to a single hypothesis. Additional informative examples
(e.g., negatives that distinguish Sky vs Temperature importance) are needed to shrink G further.
Q6) Explain Learn-One-Rule algorithm. (6 marks)
Answer: Learn-One-Rule is a covering algorithm used for rule induction. It learns a single rule that covers
some positive examples with few negatives, then removes those positives and repeats. The algorithm
balances precision and coverage using greedy specialization.
Detailed steps:
1. Start with an empty (maximally general) rule R: Body = ∅ → covers all instances.
2. While R covers any negative examples, generate candidate literals (attribute=value tests or
inequalities). For each candidate literal, evaluate a heuristic (information gain, FOIL gain, or accuracy
improvement) when it is added to R.
3. Select the literal with the best heuristic value and conjoin it to R (specialize). Repeat until R covers
no negatives (or meets minimum thresholds).
4. Optionally prune R to remove redundant conditions that don't reduce accuracy on a validation set.
5. Add R to the rule set, remove covered positive examples from training data, and repeat
Learn-One-Rule until no positives remain.
Properties and use-cases:
• Greedy and efficient; produces high-precision rules but may require many rules to achieve high
recall. Common in propositional and first-order rule learners.
Q7) Write the classification steps involved in the FOIL algorithm. (8 marks)
Answer: FOIL (First-Order Inductive Learner) extends the Learn-One-Rule idea to relational (first-order)
domains, producing Horn clauses. It searches for literals to add to a clause using the FOIL gain heuristic.
Detailed FOIL steps:
1. Input: Pos (positive examples), Neg (negative examples), and background relations (domain theory).
Initialize learned rule set H=∅.
2. Outer loop: While Pos is not empty, create a new clause C with head = target predicate and empty
 Machine Learning Assignment - Detailed Answers (VTU Style)

body (very general).

3. Inner loop (specialize C): While C still covers negative examples, generate candidate literals
(relations possibly introducing new variables) and compute FOIL gain for each candidate. FOIL gain
balances the number of positive examples retained vs negatives removed.
4. Select the literal with maximum FOIL gain and add to the body of C. Update which examples are
covered.
5. When the clause covers no negatives (or meets stopping criteria), add C to H and remove positive
examples it covers from Pos.
6. Repeat until Pos is empty. Optionally prune and simplify rules using validation data.
Notes on FOIL gain (intuition):
• FOIL gain measures informational utility of adding a literal: it increases when many positives still
match while many negatives are excluded. It prefers literals that substantially increase the precision of
the clause.
Q8) Comments on Explanation-Based Learning (EBL). (8 marks)
Answer: Explanation-Based Learning transforms domain knowledge plus an example into generalized rules
via deduction. Instead of purely statistical generalization, EBL constructs a proof that an example satisfies
the concept and then abstracts the proof to obtain a rule.
Key components:
1. Background theory: A correct and sufficiently powerful domain theory used to derive
proofs/explanations for examples.
2. Explanation construction: Given a positive example, derive a proof that the example meets the
concept specification using the background theory.
3. Analysis and generalization: Identify which steps and conditions in the proof are essential; replace
instance-specific constants with variables to generalize the explanation into a rule.
4. Rule storage and reuse: The generalized rule is added to the knowledge base and used for future
classification, often improving efficiency.
Advantages:
• Very data-efficient: a single explained example can generate a broadly-applicable rule. • Produces
precise, human-understandable rules when the domain theory is correct.
Limitations:
• Requires a correct and expressive domain theory; errors or omissions lead to incorrect or incomplete
generalizations. • Risk of over-specialization if incidental details of the proof are retained. •
Computational cost: constructing and analyzing proofs can be expensive.
Conclusion: EBL is powerful in domains where strong background knowledge exists (physics, program
analysis), but is less applicable where such knowledge is unavailable. It complements inductive methods
and is discussed by Mitchell as a hybrid approach.

Prepared with reference to Tom M. Mitchell, 'Machine Learning'. Answers expanded for VTU exam style.