ADVANCED MACHINE LEARNING AND DEEP LEARNING
Syllabus
Introduction to Machine Learning: Introduction, Training, Rote Learning, Learning
Concepts, General-to-Specific, Ordering, Version Spaces, Candidate Elimination,
Inductive Bias, Decision-Tree Induction, The Problem of Overfitting, The Nearest
Neighbor Algorithm, Learning Neural Networks, Supervised Learning, Unsupervised
Learning, Reinforcement Learning.
Books
1. Artificial Intelligence Illuminated - Ben Coppin
2. Deep Learning - Ian Goodfellow, Yoshua Bengio, Aaron Courville
3. Fundamentals of Deep Learning – Nikhil Budama
4. Neural Networks and Deep Learning – Charu Aggarwal
5. Hands-on Deep Learning Algorithms with Python – Sudharsan Ravichandran
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
1
Introduction to Machine Learning
Modulue-1
Dr. Veerabhadrappa S T
Associate Professor
Department of Electronics & Communication,
JSS Academy of Technical Education, Bengaluru
veerabhadrappast@[Link]
Introduction
Learning and intelligence are intimately related to each other. It is
usually agreed that a system capable of learning deserves to be called
intelligent; and conversely, a system being considered as intelligent is,
among other things, usually expected to be able to learn. Learning
always has to do with the self improvement of future behaviour based
on past experience.
—Sandip Sen and Gerhard Weiss, Learning in Multiagent Systems
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
What is Machine Learning?
•Definition: Machine learning is a branch of artificial intelligence (AI)
that allows computers to learn from data and make decisions without
being explicitly programmed.
•Key Idea: Machines improve their performance as they are exposed
to more data over time.
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
ML Model Training Overview
•Training Process: The process of teaching a machine learning algorithm to recognize
patterns in data.
• Data Collection: Gathering relevant data.
• Model Selection: Choosing an appropriate algorithm (e.g., decision tree, neural
network).
• Training: Feeding data into the model and adjusting parameters to learn from the
data.
• Evaluation: Testing model accuracy on unseen data.
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Training
➢ Learning to classify unseen data clearly assumes that there is some relationship between
the data and the classifications—in other words, some function
f can be generated such that if a piece of data x belongs in classification y, then f(x) = y
➢ Most real-world problems are not so simple, and producing a function that
approximates the correct mapping is one of the main challenges of
machine learning.
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Training
For example, let us consider a system that is to learn how to evaluate static
chess positions.
First, we will consider a number of variables:
x 1: Number of white pieces on the board
x2 : Number of black pieces on the board
x3 : Number of black pieces threatened by white pieces
x4: Number of white pieces threatened by black pieces
x5: Can white checkmate on the next go?
X6 : Can black checkmate on the next go?
X7 : Number of different moves white can make
x8 : Number of different moves black can make
f(x1, x2, x3, x4, x5, x6, x7, x8) =w1x1 + w2x2 + w3x3 + w4x4 + w5x5 + w6x6 + w7x7 + w8x8
An item of training data might be
f(10, 2, 1, 0, true, false, 10, 1) = 100
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Rote Learning in AI in AI
•Rote learning in AI refers to a form of memorization where a model simply memorizes information without
truly understanding its context.
•Rote Learning is a learning process where the AI system stores and reproduces data or patterns without the
ability to generalize and apply knowledge effectively.
•
Features of Rote Learning in AI
•Rote learning in AI learns by memorizing specific examples. For example, Rote learning might memorize a
large dataset of text or images without understanding the context.
•Limited Generalization: Rote learning systems struggle to generalize their knowledge to new, unseen
situations. They may perform well on tasks similar to what they've memorized but poorly on tasks outside
their narrow scope.
•Lack of Adaptability: These systems typically do not adapt well to changes in data or environment because
they lack the ability to reason or adapt their knowledge.
•Limited Problem-Solving: Rote learning systems are not effective at problem-solving or making decisions
based on the information they've memorized.
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Learning Concepts
Learning by Taking Advice: Expert Guidance
•Learning by taking advice involves seeking guidance from experts or mentors.
•This approach enables learners to tap into the experiences and insights of those who
have already mastered the subject matter.
•This method is particularly beneficial in fields that require practical skills and
knowledge, as it bridges the gap between theory and application.
Learning in Problem-Solving: Navigating Challenges
•Learning through problem-solving is a dynamic approach that encourages critical
thinking and creativity.
•This method places learners in scenarios where they must analyze, strategize, and find
solutions.
•Problem-solving learning enhances analytical skills, adaptability, and the ability to
approach complex issues with confidence.
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Learning from Examples
•Induction is a learning approach where general principles are inferred from specific
examples.
•It's about recognizing patterns and making educated predictions based on observed
instances.
•Inductive learning is foundational in subjects like mathematics and science, where
hypotheses are formed through observation and experimentation.
Explanation-based Learning: Understanding the "Why“
• Explanation-based learning involves comprehending the underlying principles
behind concepts.
• Instead of memorizing isolated facts, learners grasp the rationale and mechanisms.
• This method promotes a deep understanding of subjects and fosters the ability to
apply learned knowledge in various contexts.
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Inductive Learning / Concept Learning
• Task:
• Learn (to imitate) a function f: X → Y
• Training Examples:
• Learning algorithm is given the correct value of the function for particular inputs →
training examples
• An example is a pair (x, f(x)), where x is the input and f(x) is the output of the
function applied to x.
• Goal:
• Learn a function h: X → Y that approximates
f: X → Y as well as possible.
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Inductive Learning Example
Food Chat Fast Price Bar BigTip
(3) (2) (2) (3) (2)
great yes yes normal no yes
great no yes normal no yes
mediocre yes no high no no
great yes yes normal yes yes
• Instance Space X: Set of all possible objects described by attributes (often
called features).
• Target Function f: Mapping from Attributes to Target Feature
(often called label) (f is unknown)
• Hypothesis Space H: Set of all classification rules hi we allow.
• Training Data D: Set of instances labeled with Target Feature
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Inductive Learning Algorithm
• Task:
• Given: collection of examples
• Return: a function h (hypothesis) that approximates f
• Inductive Learning Hypothesis:
Any hypothesis found to approximate the target function well over a sufficiently
large set of training examples will also approximate the target function well over
any other unobserved examples.
• Assumptions of Inductive Learning:
• The training sample represents the population
• The input features permit discrimination
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Inductive Learning Setting
New examples
h: X → Y
• Task:
• Learner (or inducer) induces a general rule h from a set of observed examples that classifies new
examples accurately. An algorithm that takes as input specific instances and produces a model
that generalizes beyond these instances.
• Classifier - A mapping from unlabeled instances to (discrete) classes.
• Classifiers have a form (e.g., decision tree) plus an interpretation procedure (including how to
handle unknowns, etc.)
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Inductive learning method
• Fitting a function of a single variable to some data points
• Examples are (x, f(x) pairs;
• Hypothesis space H – set of hypotheses we will consider for
function f, in this case polynomials of degree at most k
• Construct/adjust h to agree with f on training set
• (h is consistent if it agrees with f on all examples)
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Example
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Version Spaces
➢ A version space is a collection of
hypotheses that are consistent with
a set of training examples.
➢ Version space learning is a machine
learning technique that uses
version spaces to learn binary
classification.
➢ A version space is a hierarchial
representation of knowledge that
enables you to keep track of all the
useful information supplied by a
sequence of learning examples
without remembering any of the
examples.
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Candidate Elimination
The candidate elimination method stores not just a single hypothesis, but two sets of hypotheses.
Version Space Method Learning Algorithm: Candidate-Elimination
The version space method handles positive and negative examples symmetrically.
Given:
•A representation language.
•A set of positive and negative examples expressed in that language.
Compute: a concept description that is consistent with all the positive examples and none of the negative
examples.
Method:
•Initialize G, the set of maximally general hypotheses, to contain one element: the null description (all
features are variables).
•Initialize S, the set of maximally specific hypotheses, to contain one element: the first positive example.
•Accept a new training example.
• If the example is positive:
• Generalize all the specific models to match the positive example, but ensure the following:
• The new specific models involve minimal changes.
• Each new specific model is a specialization of some general model.
• No new specific model is a generalization of some other specific model.
• Prune away all Sthe
Veerabhadrappa general models
T, Department that &fail
of Electronics to match the
Communication, JSSpositive
Academy example.
of Technical Education, Bengaluru
Candidate Elimination
• If the example is negative:
• Specialize all general models to prevent match with the negative example, but ensure the
following:
• The new general models involve minimal changes.
• Each new general model is a generalization of some specific model.
• No new general model is a specialization of some other general model.
• Prune away all the specific models that match the negative example.
• If S and G are both singleton sets, then:
• if they are identical, output their value and halt.
• if they are different, the training cases were inconsistent. Output this result and halt.
• else continue accepting new training examples.
The algorithm stops when:
[Link] runs out of data.
[Link] number of hypotheses remaining is:
1. 0 - no consistent description for the data in the language.
2. 1 - answer (version space converges).
3. 2+ - all descriptions in the language are implicitly included.
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Candidate Elimination
➢ The method operates as follows: Two sets are maintained of hypotheses, hs and hg: hs
is initialized as {<∅, ∅, ∅, ∅, ∅, ∅, ∅, ∅>} and hg is initialized as {<?, ?, ?, ?, ?, ?, ?, ?>}.
➢ When a positive training example is encountered, it is compared with the
hypotheses contained in hg.
➢ If any of these hypotheses does not match thetraining example, it is removed from hg.
➢ The positive training data are then compared with the hypotheses contained in hs.
➢ If one of these hypotheses does not match the training data, it is replaced by the set of
slightly more general hypotheses that are consistent with the data, and such that
there is at least one hypothesis in hg that is more general.
➢ This method is applied in reverse for negative training data. By applying
this method to each item of training data, the sets hg and hs move closer to
each other and eventually between them contain the full version space of
hypotheses that match all the training data.
➢
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Inductive Bias
✓ All learning methods have an inductive bias. Inductive bias refers to the restrictions that are imposed by the assumptions
made in the learning method.
✓ For example, in the above discussions we have been assuming that the solution to the problem of road safety can be
expressed as a conjunction of a set of eight concepts.
✓ This does not allow for more complex expressions that cannot be expressed as a conjunction.
✓ This inductive bias means that there are some potential solutions that we cannot explore, and which are, therefore, not
contained within the version space. we examine. This may seem like an unfortunate limitation, but in fact inductive bias is
essential for learning. In order to have an unbiased learner, the version space would have to contain every possible
hypothesis that could possibly be expressed.
✓ This would impose a severe limitation: the solution that the learner produced could never be any more general than the
complete set of training data.
✓ In other words, it would be able to classify data that it had previously seen (as the rote learner could) but would be unable to
generalize in order to classify new, unseen data.
✓ The inductive bias of the candidate elimination algorithm is that it is only able to classify a new piece of data if all the
hypotheses contained within its version space give the data the same classification. Hence, the inductive bias does impose a
limitation on the learning method.
✓ In the 14th century, William of Occam proposed his famous “Occam’s razor,” which simply states that it is best to choose the
simplest hypothesis to explain any phenomenon.
✓ We can consider this to be a form of inductive bias, which states that the best hypothesis to fit a set of training data is the
simplest hypothesis. e will see later how this inductive bias can be useful in learning decision trees.
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Decision-Tree Induction
➢ A variation of this kind of tree, where the leaf nodes are all Boolean values is called a decision tree. A decision tree takes
in a set of attribute values and outputs a Boolean decision.
➢ A decision tree is a flowchart-like tree structure, where each internal node denotes a test on an attribute, each branch
represents an outcome of the test, and each leaf node holds a class label.
➢ The best-known decision tree induction algorithm is ID3, which was developed by Quinlan in the 1980s.
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Decision-Tree Induction:
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Decision-Tree Induction: Example
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Decision Tree Induction Algorithm
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Decision-Tree Induction: Example
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Decision-Tree Induction: Example
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Decision-Tree Induction: Example
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Decision-Tree Induction: Example
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Decision-Tree Induction: Example
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Decision-Tree Induction: Example
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Decision-Tree Induction: Example
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Decision-Tree Induction: Example
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Decision-Tree Induction: Example
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Decision-Tree Induction: Example
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Design Issues of Decision Tree Induction
How should training examples be split?
– Method for specifying test condition (Splitting Criterion)
• depending on attribute types
– Measure for evaluating the goodness of a test condition (Selecting Best Attribute)
• information gain, gain ratio, Gini index, misclassification error, statistical test, …
• How should the splitting procedure stop?
– Stop splitting if all the examples belong to the same class
– Early termination depending on the results of a statistical test.
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
Methods for Expressing Test Conditions
Splitting Criterion
• Depends on attribute types
– Binary
– Nominal
– Ordinal
– Continuous
• Depends on number of ways to split
– 2-way split (Binary split)
– Multi-way split
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru
How to Determine the Best Split
• There are 9 positive examples and 5 negative examples.
• Which test condition (attribute) is the best?
[9+,5-] [9+,5-]
age income
30 31..40 >40 low medium high
[2+,3-] [4+,0-] [3+,2-] [3+,1-] [4+,2-] [2+,2-]
[9+,5-] [9+,5-]
student credit
rating
no yes fair excellent
[3+,4-] [6+,1-] [6+,2-] [3+,3-]
Data Mining 25
How to Determine the Best Split
• Greedy approach:
– Nodes with homogeneous (purer) class distribution are preferred
• Need a measure of node impurity:
[5+,5-] [9+,1-]
Non-homogeneous Homogeneous
High degree of impurity Low degree of impurity
• Measures of Node Impurity:
– entropy, Gini index, misclassification error, …
Data Mining 26
Finding the Best Split
1. Compute impurity measure (P) before splitting
2. Compute impurity measure (M) after splitting
• Compute impurity measure of each child node
• M is the weighted impurity of children
3. Choose the attribute test condition that produces the highest gain
Gain = P - M
or equivalently, lowest impurity measure after splitting (M)
Data Mining 27
Attribute Selection Measures
• An attribute selection measure is a heuristic for selecting the splitting criterion that
best separates a given data set D of class-labeled training tuples into individual
classes.
– to split D into smaller partitions according to the outcomes of the splitting criterion, ideally
each partition would be pure (i.e., all of the tuples that fall into a given partition would
belong to the same class).
• The attribute having the best score for the measure is chosen as the splitting
attribute for the given tuples.
• Three popular attribute selection measures:
information gain, gain ratio, and gini index.
Data Mining 28
Measure of Impurity: Entropy
• Given a collection S, containing positive and negative examples of some target
concept, the entropy of S relative to this boolean classification is:
Entropy(S) = -p+ log2p+ - p- log2p-
• S is a sample of training examples
• p+ is the proportion of positive examples
• p- is the proportion of negative examples
Data Mining 29
Measure of Impurity: Entropy
Entropy([12+,5-] =
– (12/17) log2(12/17) – (5/17) log2(5/17) = 0.874
Entropy([8+,8-] =
– (8/16) log2(8/16) – (8/16) log2(8/16) = 1.0
Entropy([8+,0-] =
– (8/8) log2(8/8) – (0/8) log2(0/8) = 0.0
– It is assumed that log2(0) is 0
Data Mining 30
Entropy – Non-Boolean Target Classification
• If the target attribute can take on c different values, then the entropy of S relative to
this c-wise classification is defined as
• pi is the proportion of S belonging to class i.
• The logarithm is still base 2 because entropy is a measure of the expected encoding
length measured in bits.
• If the target attribute can take on c possible values, the entropy can be as large as
log2c.
Data Mining 31
Entropy – Informaton Theory
• Entropy(S) = expected number of bits needed to encode class (+ or -) of randomly
drawn members of S (under the optimal, shortest length-code)
– if p+ is 1, the receiver knows the drawn example will be positive, so no message need be
sent, and the entropy is zero.
– if p+ is 0.5, one bit is required to indicate whether the drawn example is positive or
negative.
– if p+ is 0.8, then a collection of messages can be encoded using on average less than 1 bit
per message by assigning shorter codes to collections of positive examples and longer
codes to less likely negative examples.
• Information theory optimal length code assign –log2p bits to messages having
probability p.
• So the expected number of bits to encode (+ or -) of random member of S:
- p+ log2 p+ - p- log2p-
Data Mining 32
Attribute Selection Measure:
Information Gain
• Select the attribute with the highest information gain
• Let pi be the probability that an arbitrary tuple in D belongs to class Ci,
estimated by |Ci,D|/|D|
• Expected information (entropy) needed to classify a tuple in D:
• Information needed (after using A to split D into v partitions) to classify D:
• Information gained by branching on attribute A
Data Mining 33
Attribute Selection Measure:
Information Gain
• There are 9 positive examples and 5 negative examples.
D: [9+,5-]
Info(D) = Entropy(D) =
– (9/14) log2(9/14) – (5/14) log2(5/14) = 0.940
[9+,5-] Infoage(D) = 5/14 * Info([2+,3-]) +
age 4/14 * Info([4+,0-]) +
5/14 * Info([3+,2-])
30 31..40 >40
= (5/14)*0.971 + (4/14)*0.0 + (5/14)*0.971
= 0.694
[2+,3-] [4+,0-] [3+,2-]
Gain(age) = Info(D) - Infoage(D)
= 0.940 – 0.694 = 0.246
Data Mining 34
Attribute Selection Measure:
Information Gain
Info(D) = – (9/14) log2(9/14) – (5/14) log2(5/14) = 0.940
Infoincome(D) = 4/14 * Info([3+,1-]) +
6/14 * Info([4+,2-]) +
[9+,5-]
4/14 * Info([2+,2-])
income
= (4/14)*0.811+ (6/14)*0.911 + (4/14)*1.0
= 0.911
low medium high
[3+,1-] [4+,2-] [2+,2-] Gain(income) = Info(D) - Infoincome(D)
= 0.940 – 0.911 = 0.029
Data Mining 35
Attribute Selection Measure:
Information Gain
Info(D) = – (9/14) log2(9/14) – (5/14) log2(5/14) = 0.940
[9+,5-] Infostudent(D) = 7/14 * Info([3+,4-]) +
student 7/14 * Info([6+,1-])
= (7/14)*0.985+ (7/14)*0.592 = 0.789
no yes
Gain(student) = Info(D) - Infostudent(D)
[3+,4-] [6+,1-]
= 0.940 – 0.789 = 0.151
[9+,5-] Infocr (D) = 8/14 * Info([6+,2-]) +
credit 6/14 * Info([3+,3-])
rating
= (8/14)*0.811+ (6/14)*1.0 = 0.892
fair excellent
[6+,2-] [3+,3-] Gain(cr) = Info(D) - Infocr(D)
= 0.940 – 0.892 = 0.048
Data Mining 36
Gain Ratio for Attribute Selection
• Information gain measure is biased towards attributes with a large number of values
• Some decision tree induction algorithms (such as C4.5) uses gain ratio to overcome
the problem (normalization to information gain)
GainRatio(A) = Gain(A) / SplitInfoA(D)
• Ex.
GainRatio(income) = 0.029 / 1.557 = 0.019
• The attribute with the maximum gain ratio is selected as the splitting attribute
Data Mining 39
Information Gain
➢ The method used by ID3 to determine which features to use at each stage of the
decision tree is to select, at each stage, the feature that provides the greatest
information gain.
➢ Information gain is defined as the reduction in entropy. The entropy of a set of training
data, S, is defined as H(S) = -p1 log2 p1 - p0 log2 p0
➢ where p1 is defined as the proportion of the training data that includes
positive examples, and p0 is defined as the proportion that includes negative examples.
➢ The entropy of S is zero when all the examples are positive, or when all the examples
are negative.
➢ The entropy reaches its maximum value of 1 when exactly half of the examples are
positive and half are negative.
Veerabhadrappa S T, Department of Electronics & Communication, JSS Academy of Technical Education, Bengaluru