Machine Learning Assignment Solutions
1) Choosing a Representation for the Target Function
The choice of representation for the target function is critical in machine learning. It must balance
expressiveness, efficiency, interpretability, and availability of domain knowledge. - Representation
must be rich enough to capture the target concept but not too complex to cause overfitting. - The
chosen representation imposes an inductive bias, limiting which hypotheses are learnable. -
Efficiency of search and evaluation is important. - Human interpretability is often desirable. -
Domain knowledge should be leveraged where available. Examples include conjunctive concepts,
decision trees, linear separators, and first-order logic rules.
2) Final Design of the Checkers Learning System
Mitchell's checkers system learns an evaluation function for board states: - Representation: Linear
combination of board features (piece counts, kings, mobility, etc.). - Training data: Positions labeled
through self-play or expert play. - Learning method: Error-driven updates (gradient
descent/perceptron-style) to improve evaluation. - Search: Minimax with the learned evaluation
guides move selection. Final design shows the importance of feature engineering and the
interaction between evaluation quality and search depth.
3) Maximally Specific Hypothesis using Find-S
Training Examples: 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 Result: Final maximally specific hypothesis:
4) Version Spaces
A Version Space VS(H,D) is the subset of hypotheses in hypothesis space H consistent with data
D. - S boundary: maximally specific hypotheses. - G boundary: maximally general hypotheses. - All
hypotheses lie between S and G. Candidate-Elimination updates S and G on each example.
Version spaces give an exact characterization of all consistent hypotheses but may collapse in
noisy or incomplete domains.
5) Candidate-Elimination on Table-1
Initial: S = <ϕ,ϕ,ϕ,ϕ,ϕ,ϕ>, G = After 1st positive: S = After 2nd positive: S = After 3rd negative: G =
{,,} After 4th positive: S = Final G = {,} Final Version Space: S = {} G = {,}
6) Learn-One-Rule Algorithm
Learn-One-Rule constructs rules greedily: 1. Start with empty rule body. 2. Add conditions that
maximize accuracy until no negatives are covered. 3. Add rule to hypothesis set and remove
covered positives. 4. Repeat until all positives are covered. It is a greedy, sequential covering
algorithm that learns one rule at a time.
7) FOIL Algorithm
FOIL (First Order Inductive Learner) learns first-order Horn clauses: 1. While positives remain: -
Start with empty rule body. - Add literals that maximize FOIL-gain until no negatives are covered. -
Add rule to rule set and remove covered positives. 2. FOIL-gain guides greedy specialization: Gain
= t * (log2(p1/p0)) FOIL combines rule learning with first-order representations.
8) Remarks on Explanation-Based Learning (EBL)
Explanation-Based Learning generalizes from single examples using a domain theory. - Steps:
Prove example using domain theory, extract essential conditions, generalize proof, store
generalized rule. - Advantages: Efficient runtime, needs few examples, produces precise rules. -
Disadvantages: Needs correct domain theory, brittle if theory is wrong, less data-driven. EBL is
powerful where strong background knowledge exists.