Supervised Learning
Design a learning system
Step 1: Choosing the Training Experience (Training Data)
This is the first and most important step.
You must choose the right training data to give to the ML algorithm. Why is it important?
Because good data → good model,
and bad data → bad model.
Things that affect success:
Feedback:
The data should help the model learn what is right or wrong.
Example: In chess, the system learns that “this move fails” or “that move wins.”
Control over examples:
The model should improve as it plays more and more.
Example: Accuracy is low in the beginning, but improves as it plays repeatedly.
Variety of examples:
The model should see many different cases to learn well.
Example: More chess game situations → more learning → better performance.
Step 2: Choosing the Target Function
This means deciding what you want the model to learn. Example: In chess, the target function
can be “NextMove,”
which tells the model which legal move to make to get a better chance of winning.
Step 3: Choosing How to Represent the Target Function
Once the model knows the possible moves,
we must choose how to represent the decision-making.
It can use:
Linear equations
Graphs
Tables
Any simple form that helps
Example: If there are 4 possible chess moves, the machine picks the one with the highest
success chance using the chosen representation.
X1: the number of black pieces on the board x2: the number of red pieces on the board x3: the
number of black kings on the board x4: the number of red kings on the board x5: the number of
black pieces threatened by red (i.e., which can be captured on red's next turn) X6: the number
of red pieces threatened by blac
Step 4: Choosing the Function Approximation Algorithm
The model cannot become perfect just from raw training data.
It needs an algorithm that allows it to learn from many examples and improve.
Example:
While learning chess, the model will make mistakes and sometimes win.
From each mistake or win, it updates its understanding:
“Next time, this move works better.”
This process helps it guess the best move over time.
Step 5: Final Design
After going through:
Many examples
Many failures
Many successes
Many corrections
…the final ML model is ready.
Example:
Deep Blue, a chess-playing computer, learned from huge amounts of data
and became so good that it defeated world champion Garry Kasparov.
1. Critic
The Critic looks at the history of the game (the full trace of moves).
From this, it creates training examples.
Each training example has:
o A game state (what the board looked like at some moment)
o A value estimate (V_train), which tells how good that state was
→ good chance to win or bad chance to lose.
Simple meaning:
Critic = “This is the position you were in, and this is how good that position was.”
2. Generalizer
It takes the training examples from the Critic.
It then creates a hypothesis, which is basically its best guess of the target function.
It tries to learn a general rule that works not only for the examples it saw,
but also for new, unseen board positions.
Simple meaning:
Generalizer = “From all the examples you gave me, I think this is the rule to decide how good a
board position is.”
3. Experiment Generator
It takes the current learned hypothesis (the current best rule).
Using that rule, it creates a new problem for the Performance System —
usually a new starting board state.
The point is to give the system new practice situations so it can learn more.
Experiment Generator = “Based on what you learned, here is a new board setup. Try playing
from here and learn more.”
Perspectives and Issues in Machine Learning
1. Perspective: Machine Learning as a Search Problem
A simple way to understand machine learning is:
ML = searching a huge space of possible answers (hypotheses)
The learner tries many possible hypotheses.
It picks the one that best matches:
o the training data
o any prior knowledge the learner already has
Example: Checkers Learning
In the checkers example:
The hypothesis space = all the evaluation functions the system could create
These evaluation functions depend on weights w₀ to w₆
Each different set of weights = one possible hypothesis
So, the learner's job is to search through all possible weight settings to find the best one.
How LMS Helps
The LMS (Least Mean Squares) algorithm improves the weights step-by-step:
It checks if the current prediction is different from the training value
If different → it adjusts each weight slightly
By repeating this many times, it slowly moves toward a better hypothesis
Easy meaning:
LMS = “If I made a mistake, I will correct my weights a little and try again.”
This method works well only when the hypothesis space is continuous (weights can be changed
smoothly.
2. Issues in Machine Learning
Machine learning raises several important questions:
Issue 1: Which Learning Algorithm Should We Use?
Many algorithms exist.
We need to know:
o Which one fits what kind of problem?
o Which one is fastest?
o Which one learns best?
Issue 2: How Much Training Data Is Enough?
We must ask:
o How many examples do we need to trust the result?
o Does more data always help?
o How does the size of the hypothesis space affect confidence?
Issue 3: How to Use Prior Knowledge?
Prior knowledge means information we already know before learning.
Questions:
o When should we use it?
o Can it help even if it's not perfectly correct?
Issue 4: What Training Examples Should We Choose Next?
Learning becomes easier if we choose useful examples.
Example: Choosing the next board state in checkers for better practice.
The strategy of choosing examples affects how fast the model learns
Issue 5: How to Break Down the Learning Problem?
Many ML problems can be divided into smaller tasks.
Question:
o Which functions should be learned?
o Can we automate this process?
Issue 6: How Can the Learner Improve Its Own Representation?
A learner should sometimes change:
o How it stores knowledge
o How it represents examples
Example: Using a better model structure to improve performance.
Concept Learning
Concept learning means teaching a machine to understand a rule or pattern from examples.
It is like showing a machine many examples of something (like cats, spam emails, or good
customers) and helping it learn what makes them belong to that concept.
Key Terms
Target Concept
The rule or pattern the machine must learn.
Example: “What is a cat?” or “Who will buy the product?”
Training Data
Examples used to teach the machine.
Each example has:
Input (image, text, numbers)
Label (cat/not cat, buy/not buy)
hypothesis
A proposed rule or function or The machine’s guess of the rule.
It is the model’s idea of the concept after learning.
Generalization
The ability of the model to correctly identify new, unseen examples.
How Concept Learning Works
1. Data Preparation
We collect and clean good examples that correctly represent the concept.
2. Choose a Model
We pick a suitable algorithm like:
Decision trees
SVM
Neural networks
3. Training
The model learns from the labeled examples.
It keeps adjusting its parameters to reduce mistakes.
4. Evaluation
We test the model on new data (test set) to see how well it learned.
We use measures like:
Accuracy
Precision
Recall
5. Refinement
If the model is not good enough, we: Improve data, Change the model, Retrain it
The FIND-S algorithm is like starting with the most specific guess and slowly relaxing it until it
fits all the examples.
Example: Imagine you're trying to figure out what kind of weather makes you enjoy playing a
sport, using this data:
Start with the most specific rule: h=(?, ?, ?, ?, ?, ?), which means "no conditions are set
yet."
Look at the first positive example: (Sunny, Warm, Normal, Strong, Warm, Same)
Rule becomes: h=(Sunny, Warm, Normal, Strong, Warm, Same)
Look at the second positive example: (Sunny, Warm, High, Strong, Warm, Same)
Update the rule to match both examples: h=(Sunny, Warm, ?, Strong, Warm, Same)
Ignore the negative example.
Look at the fourth positive example: (Sunny, Warm, High, Strong, Cool, Change)
Update the rule again: h=(Sunny, Warm, ?, Strong, ?, ?)
Final rule: (Sunny, Warm, ?, Strong, ?, ?).
This means you enjoy playing sports if it’s sunny, warm, and windy, regardless of the
other conditions.
Properties of FIND-S 1.
Guarantees a Maximally Specific Hypothesis: In conjunction-based hypothesis spaces
like EnjoySport, FIND-S always gives the most specific consistent hypothesis.
Focus on Positive Examples: Negative examples are ignored unless they conflict with the
current hypothesis, which is unlikely if the hypothesis space contains the true target
concept.
Limitations of FIND-S 1.
Uncertainty About the Target Concept
Preference for Specific Hypotheses.
Sensitivity to Errors
Multiple Maximally Specific Hypotheses
requiring modifications to FIND-S to handle backtracking or branching.
No Accommodation for Non-Conjunctive Hypothesis Spaces
Candidate Elimination
We keep two sets:
G (General set):
Contains the most general hypotheses.
S (Specific set):
Contains the most specific hypotheses.
We update S and G for every training example.
Algorithm
1. Initialization
Set S = { ⌀ } (fully specific hypothesis)
Set G = { ? , ?, ?, ... } (fully general hypothesis)
2. For every training example d:
Case 1: If d is a POSITIVE example
We want hypotheses that accept this example.
Step A: Update G
Remove any hypothesis in G inconsistent with d
Step B: Update S
For every hypothesis in S inconsistent with d:
o Remove it from S.
o Replace it with its minimal generalizations that:
fit the positive example
are not more general than any hypothesis in G
Remove any hypothesis from S that is more general than another one in S.
Case 2: If d is a NEGATIVE example
We want hypotheses that reject this example.
Step A: Update S
Remove any hypothesis in S inconsistent with d
Step B: Update G
For every hypothesis g in G inconsistent with d:
o Remove it from G
o Replace it with its minimal specializations that:
reject the negative example
are not more specific than any hypothesis in S
Remove any hypothesis in G that is more specific than another one in G.