ARTIFICIAL INTELLIGENCE

AND MACHINE LEARNING

18CS71
Manasa Sandeep
Asst. Prof.
Dept. of CSE, DSATM
Module 3

Decision Tree Learning: Introduction, Decision tree

representation, Appropriate problems, ID3 algorithm.
Artificial Neural Network: Introduction, NN
representation, Appropriate problems, Perceptrons,
Backpropagation algorithm.
Texbook1: Chapter 3 (3.1-3.4), Chapter 4 (4.1-4.5)
 Decision tree learning
• Decision tree learning is one of the most widely used and
practical methods for inductive inference and for concept
learning
• It is a method for approximating discrete-valued functions that is
robust to noisy data and capable of learning disjunctive
expressions
• The ID3 family of algorithms infers decision trees by growing
them from the root downward, greedily selecting the next best
attribute for each new decision branch added to the tree.
• Learned trees can also be re-represented as sets of if-then rules
to improve human readability
 DECISION TREE REPRESENTATION

a. Training examples for the target concept Play Tennis

b. A decision tree for the concept Play Tennis.
• Decision trees classify instances by sorting them down the tree from
the root to some leaf node, which provides the classification of the
instance.
• Each node in the tree specifies a test of some attribute of the
instance, and each branch descending from that node corresponds
to one of the possible values for this attribute.
• An instance is classified by starting at the root node of the tree,
testing the attribute specified by this node, then moving down the
tree branch corresponding to the value of the attribute in the given
example. This process is then repeated for the subtree rooted at the
new node.
• Decision trees represent a disjunction of conjunctions of
constraints on the attribute values of instances
• Each path from the tree root to a leaf corresponds to a
conjunction of attribute tests, and the tree itself to a disjunction
of these conjunctions
A B ~B A ^ ~B
0 0 1 0
0 1 0 0
1 0 1 1
1 1 0 0
A B C B ^C AV [B ^ C]
0 0 0 0 0
0 0 1 0 0
0 1 0 0 0
0 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
A B A XOR B
F F F
F T T
T F T
T T F
A B C D A^ B C^D [A^ B ] V [C^D]

DO IT YOURSELF
 APPROPRIATE PROBLEMS FOR DECISION TREE
LEARNING
• Decision tree learning is generally best suited to problems with the
following characteristics
• Decision tree learning has been applied to classification problems
• The problems in which, the task is to classify examples into one
of a discrete set of possible categories, are referred to as
classification problems.
Examples:
➢Classifying medical patients by their disease
➢Equipment malfunctions by their cause
➢Loan applicants by their likelihood of defaulting on
payments.
1 For the transaction shown in the table compute the following:

a. What is the entropy of this collection of training examples

•. with respect to the target Function classification?
b. What is the information gain of a2 relative to these training
examples?
Instance 1 2 3 4 5 6 7 8 9

A1 T T T F F F F T F

A2 T T F F T T F F T

Target + + - + - - - + -
Class
13
Instance 1 2 3 4 5 6 7 8 9 a. Entropy of the collection of training
A1 T T T F F F F T F examples with respect to the target
Function classification is :
A2 T T F F T T F F T

Target + + - + - - - + -
Class
Entropy(S) = - (4/9) log2 (4/9) - (5/9) log2 (5/9)
= 0.528 + 0.47 = 0.998
b. What is the information gain of a2 relative to these training examples
Attribute: A2, Values: (T, F)
Entropy(T): [2+, 3-] = - (2/5) log2 (2/5) - (3/5) log2 (3/5)
= 0.528 + 0.442 = 0.97
Entropy(F): [2+, 2-] = 1

Gain(S, A2) = Entropy(S) – [(5/9) * (0.97) + (4/9)* (1)]

= 0.998 – (0.538 + 0.44) = 0.998- 0.978 = 0.02
2
THE BASIC DECISION TREE LEARNING
ALGORITHM
Which Attribute Is the Best Classifier?

➢The central choice in the ID3 algorithm is selecting which

attribute to test at each node in the tree.

➢A statistical property, called information gain measures how

well a given attribute separates the training examples according
to their target classification.

➢ID3 uses this information gain measure to select among the

candidate attributes at each step while growing the tree.
ENTROPY MEASURES HOMOGENEITY OF
EXAMPLES
 INFORMATION GAIN MEASURES THE
EXPECTED REDUCTION IN ENTROPY
• Information
gain, is the expected reduction in entropy
caused by partitioning the examples according to this
attribute.
• Theinformation gain, Gain(S, A) of an attribute A, relative
to a collection of examples S, is defined as

22
Example: Information gain

Let, Values(Wind) = {Weak, Strong}

S = [9+, 5−]
SWeak = [6+, 2−]
SStrong = [3+, 3−]

Information gain of attribute Wind:

Gain(S, Wind) = Entropy(S) − 8/14 Entropy (SWeak) − 6/14 Entropy (SStrong)

= 0.94 – (8/14)* 0.811 – (6/14) *1.00
= 0.048

23
Day Outlook Temperature Humidity Wind PlayTennis
D1 Sunny Hot High Weak No
Attribute: Outlook
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Strong Yes
D8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak Yes
D10 Rain Mild Normal Weak Yes
D11 Sunny Mild Normal Strong Yes
D12 Overcast Mild High Strong Yes

D13 Overcast Hot Normal Weak Yes

D14 Rain Mild High Strong No

24
Day Outlook Temperature Humidity Wind PlayTennis
Attribute: Temp
D1 Sunny Hot High Weak No

D2 Sunny Hot High Strong No

D3 Overcast Hot High Weak Yes

D4 Rain Mild High Weak Yes

D5 Rain Cool Normal Weak Yes

D6 Rain Cool Normal Strong No

D7 Overcast Cool Normal Strong Yes

D8 Sunny Mild High Weak No

D9 Sunny Cool Normal Weak Yes

D10 Rain Mild Normal Weak Yes

D11 Sunny Mild Normal Strong Yes

D12 Overcast Mild High Strong Yes

D13 Overcast Hot Normal Weak Yes

D14 Rain Mild High Strong No

= 0.94 – (4/14) * (1.0) – (6/14) * (0.9183) – (4/14) * (0.8113)

= 0.0289
Day Outlook Temperature Humidity Wind PlayTennis

D1 Sunny Hot High Weak No

Attribute: Humidity
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes

D4 Rain Mild High Weak Yes

D5 Rain Cool Normal Weak Yes

D6 Rain Cool Normal Strong No

D7 Overcast Cool Normal Strong Yes

D8 Sunny Mild High Weak No

D9 Sunny Cool Normal Weak Yes

D10 Rain Mild Normal Weak Yes

D11 Sunny Mild Normal Strong Yes

D12 Overcast Mild High Strong Yes

D13 Overcast Hot Normal Weak Yes

D14 Rain Mild High Strong No

Day Outlook Temperature Humidity Wind PlayTennis

D1 Sunny Hot High Weak No

Attribute: Wind
D2 Sunny Hot High Strong No
D3 Overcast Hot High Weak Yes

D4 Rain Mild High Weak Yes

D5 Rain Cool Normal Weak Yes

D6 Rain Cool Normal Strong No

D7 Overcast Cool Normal Strong Yes

D8 Sunny Mild High Weak No

D9 Sunny Cool Normal Weak Yes

D10 Rain Mild Normal Weak Yes

D11 Sunny Mild Normal Strong Yes

D12 Overcast Mild High Strong Yes

D13 Overcast Hot Normal Weak Yes

D14 Rain Mild High Strong No

Day Outlook Temperature Humidity Wind PlayTennis

D1 Sunny Hot High Weak No Gain(S, Outlook)= 0.2464

D2 Sunny Hot High Strong No Gain(S, Temperature)= 0.0289
D3 Overcast Hot High Weak Yes
Gain(S, Humidity)= 0.1516
D4 Rain Mild High Weak Yes

D5 Rain Cool Normal Weak Yes

Gain(S, Wind)= 0.0478
D6 Rain Cool Normal Strong No

D7 Overcast Cool Normal Strong Yes Outlook has maximum gain, hence outlook becomes the
D8 Sunny Mild High Weak No
root node
D9 Sunny Cool Normal Weak Yes

D10 Rain Mild Normal Weak Yes

D11 Sunny Mild Normal Strong Yes

D12 Overcast Mild High Strong Yes

D13 Overcast Hot Normal Weak Yes

D14 Rain Mild High Strong No

For Sunny Attribute: Temp
Attribute: Humidity
Gain(Ssunny, Temperature)= 0.570
Gain(Ssunny, Humidity)= 0.97
Gain(Ssunny, Wind)= 0.0192

Humidity has maximum gain, hence it becomes the next

node
For Rainy
 Day A1 A2 A3 Classifi

21 True Hot High

cation
No
S[5+, 5-] = 1
2 True Hot High No
Gain of Attribute: A1
3 False Hot High Yes Values: True, False
4 False Cool Normal Yes Entropy(True): [1+, 4-] = - (1/5)log2(1/5) - (4/5)log2(4/5)
= 0.46 + 0.25 = 0.71
5 False Cool Normal Yes
Entropy(False): [4+, 1-] = - (4/5)log2(4/5) - (1/5)log2(1/5)
6 True Cool High No = 0.25 + 0.46 = 0.71
7 True Hot High No
Gain(S, A1) =
8 True Hot Normal Yes = 1- [(5/10) * (0.71) + (5/10) * (0.71)]
9 False Cool Normal Yes = 1 – 0.781 = 0.29
10 False Cool High No
Day A1 A2 A3 Classifi
cation
1 True Hot High No
S[5+, 5-] = 1
2 True Hot High No
Gain of Attribute: A2
3 False Hot High Yes Values: Hot, Cool
4 False Cool Normal Yes Entropy(Hot): [2+, 3-] = - (2/5)log2(2/5) - (3/5)log2(3/5)
= 0.528 + 0.442 = 0.97
5 False Cool Normal Yes
Entropy(Cool): [3+, 2-] = - (3/5)log2(3/5) - (2/5)log2(2/5)
6 True Cool High No = 0.442 + 0.528 = 0.97
7 True Hot High No
Gain(S, A2) =
8 True Hot Normal Yes = 1- [(5/10) * (0.97) + (5/10) * (0.97)]
9 False Cool Normal Yes = 1 – 0.97 = 0.03
10 False Cool High No
Day A1 A2 A3 Classifi
cation
1 True Hot High No
S[5+, 5-] = 1
2 True Hot High No
Gain of Attribute: A3
3 False Hot High Yes Values: High, Normal
4 False Cool Normal Yes Entropy(High): [1+, 5-] = - (1/6)log2(1/6) - (5/6)log2(5/6)
= 0.430 + 0.219= 0.649
5 False Cool Normal Yes
Entropy(Normal): [4+, 0-] = 0
6 True Cool High No
7 True Hot High No
Gain(S, A3) =
8 True Hot Normal Yes = 1- [(6/10) * (0.649) + (4/10) * 0]
9 False Cool Normal Yes = 1 – 0.3894= 0.6106
10 False Cool High No
Gain(S, A1) = 0.29
Gain(S, A2) = 0.03
Gain(S, A3) = 0.6106
Since Gain of A3 is more, A3 is selected as root node
Day A1 A2 A3 Classifi
cation
1 True Hot High No
A3
2 True Hot High No
High Normal
3 False Hot High Yes
4 False Cool Normal Yes
5 False Cool Normal Yes
??? Yes
6 True Cool High No
7 True Hot High No
8 True Hot Normal Yes
9 False Cool Normal Yes
10 False Cool High No
Day A1 A2 A3 Classifi
cation
For Value High:
1 True Hot High No Attribute : A1, Values: True, False
2 True Hot High No
3 False Hot High Yes
4 True Cool High No Gain of Attribute: A1
5 True Hot High No Values: True, False
Entropy(True): [1+, 4-] = - (1/5)log2(1/5) - (4/5)log2(4/5)
6 False Cool High No
= 0.46 + 0.25 = 0.71
Entropy(False): [4+, 1-] = - (4/5)log2(4/5) - (1/5)log2(1/5)
= 0.25 + 0.46 = 0.71

Gain(S, A1) =
= 1- [(5/10) * (0.71) + (5/10) * (0.71)]
= 1 – 0.781 = 0.29
Day A1 A2 A3 Classifi
cation
For Value High:
1 True Hot High No Attribute : A2, Values: Hot, Cool
2 True Hot High No
3 False Hot High Yes
4 True Cool High No Gain of Attribute: A2
5 True Hot High No Values: Hot, Cool
Entropy(Hot): [1+, 3-] = - (1/4)log2(1/4) - (3/4)log2(3/4)
6 False Cool High No
= 0.811
Entropy(Cool): [0+, 2-] = 0

Gain(S, A1) =
= 1- [(4/6) * (0.811) + 0]
= 0.109
Day A1 A2 A3 Classifi
cation
1 True Hot High No
A3
2 True Hot High No
High Normal
3 False Hot High Yes
4 False Cool Normal Yes
5 False Cool Normal Yes
A1 Yes
6 True Cool High No
7 True Hot High No
True False
8 True Hot Normal Yes
9 False Cool Normal Yes
No A2
10 False Cool High No
Cool
Hot

Yes No
3
 INTRODUCTION

Artificial neural networks (ANNs) provide a general, practical method

for learning real-valued, discrete-valued, and vector-valued
target functions from examples.

44
 Biological Motivation
• The study of artificial neural networks (ANNs) has been
inspired by the observation that biological learning systems are built
of very complex webs of interconnected Neurons

• Human information processing system consists of brain neuron:

basic building block cell that communicates information to and
from various parts of body

• Simplest model of a neuron: considered as a threshold unit –a

processing element (PE)

• Collects inputs & produces output if the sum of the input 45

exceeds an internal threshold value

 Facts of Human Neurobiology

• Number of neurons ~ 1011

• Connection per neuron ~ 10 4 – 5
• Neuron switching time ~ 0.001 second or 10 -3
• Scene recognition time ~ 0.1 second
• 100 inference steps doesn’t seem like enough
• Highly parallel computation based on distributed
representation
46
 Properties of Neural Networks

• Many neuron-like threshold switching units

• Many weighted interconnections among units
• Highly parallel, distributed process
• Emphasis on tuning weights automatically
• Input is a high-dimensional discrete or real-valued (e.g, sensor
input)

47
 When to consider Neural Networks ?
• Input is a high-dimensional discrete or real-valued (e.g., sensor input)
• Output is discrete or real-valued
• Output is a vector of values
• Possibly noisy data
• Form of target function is unknown
• Human readability of result is unimportant
Examples:
• Speech phoneme recognition
• Image classification 48

• Financial perdition
 NEURAL NETWORK
REPRESENTATIONS- ALVINN

49
50
• A prototypical example of ANN learning is provided by
Pomerleau's (1993) system ALVINN (An Autonomous Land Vehicle
in Neural Network), which uses a learned ANN to steer an
autonomous vehicle driving at normal speeds on public highways.

• The input to the neural network is a 30x32 grid of pixel intensities

obtained from a forward-pointed camera mounted on the vehicle.

• The network output is the direction in which the vehicle is steered.

20
• Figure illustrates the neural network representation.
• The network is shown on the left side of the figure, with the input camera image
depicted below it.
• Each node (i.e., circle) in the network diagram corresponds to the output
of a
single network unit, and the lines entering the node from below are its inputs.
• There are four units that receive inputs directly from all of the 30 x 32 pixels in
the image. These are called "hidden" units because their output is available only
within the network and is not available as part of the global network output. Each
of these four hidden units computes a single real-valued output based on a
weighted combination of its 960 inputs
• These hidden unit outputs are then used as inputs to a second layer of 30 "output"
units.
• Each output unit corresponds to a particular steering direction, and the
output values of these units determine which steering direction is52
recommended most strongly.
• The diagrams on the right side of the figure depict the learned weight values
associated with one of the four hidden units in this ANN.
• The large matrix of black and white boxes on the lower right depicts the weights
from the 30 x 32 pixel inputs into the hidden unit. Here, a white box indicates a
positive weight, a black box a negative weight, and the size of the box indicates
the weight magnitude.
• The smaller rectangular diagram directly above the large matrix shows the
weights from this hidden unit to each of the 30 output units.

53
 APPROPRIATE PROBLEMS FOR
NEURAL NETWORK LEARNING
ANN is appropriate for problems with the following characteristics :
•Instances are represented by many attribute-value pairs.
•The target function output may be discrete-valued, real-valued, or a
vector of several real- or discrete-valued attributes.
•The training examples may contain errors.
•Long training times are acceptable.
•Fast evaluation of the learned target function may be required
•The ability of humans to understand the learned target function is not important
54
 Architectures of Artificial Neural Networks
An artificial neural network can be divided into three parts (layers), which are
known as:
•Input layer: This layer is responsible for receiving information (data),
signals, features, or measurements from the external environment. These inputs are
usually normalized within the limit values produced by activation functions
•Hidden, intermediate, or invisible layers: These layers are composed of neurons
which are responsible for extracting patterns associated with the process or system
being analysed. These layers perform most of the internal processing from a
network.
•Output layer : This layer is also composed of neurons, and thus is responsible for
producing and presenting the final network outputs, which result from the
processing performed by the neurons in the previous layers.
55
 PERCEPTRONS
• Perceptron is a single layer neural network.
• A perceptron takes a vector of real-valued inputs, calculates a linear combination
of these inputs, then outputs a 1 if the result is greater than some threshold and -1
otherwise
• Given inputs x1 through xn, the output O(x1, . . . , xn) computed by the
perceptron is

• where each wi is a real-valued constant, or weight, that determines the

contribution
of input xi to the perceptron output.
• -w0 is a threshold that the weighted combination of inputs w1x1 + . . . + wnxn must
surpass in order for the perceptron to output a 1.
30
 Sometimes, the perceptron function is written as,

Learning a perceptron involves choosing values for the weights w0 , . . . , wn .

Therefore, the space H of candidate hypotheses considered in perceptron learning is
the set of all possible real-valued weight vectors
Why do we need Weights and Bias?
Weights shows the strength of the particular node.
A bias value allows you to shift the activation function curve up or down

57
58
59
Representational Power of
Perceptrons
*The perceptron can be
viewed as representing
a hyperplane decision
surface in the n-
dimensional space of
instances.
*The perceptron outputs a
1 for instances lying on one
side of the hyperplane
and outputs a -1 for
instances lying on the other
side

60
 A single perceptron can be used to represent many Boolean functions
AND function

X0=1, W0= -0.8, w1=0.5, w2=0.5

• If A=0 & B=0 → 1 * (-0.8) + 0*0.5 + 0*0.5 = -0.8
This is not greater than the threshold of 0, so the output = 0.
• If A=0 & B=1 → 1 * (-0.8) + 0*0.5 + 1*0.5 = -0.3.
This is not greater than the threshold (0), so the output = 0.
• If A=1 & B=0 → 1 * (-0.8) + 1*0.5 + 0*0.5 = -0.3.
This is not greater than the threshold (0), so the output = 0.
• If A=1 & B=1 → 1 * (-0.8) + 1*0.5 + 1*0.5 = 0.2. 61

This exceeds the threshold (0), so the output = 1.

 A single perceptron can be used to represent many Boolean functions
AND function
A B AV B
0 0 0
0 1 1
1 0 1
1 1 1

X0=1, W0= -0.3, w1=0.5, w2=0.5

• If A=0 & B=0 → 1 * (-0.3) + 0*0.5 + 0*0.5 = -0.3
This is not greater than the threshold of 0, so the output = 0.
• If A=0 & B=1 → 1 * (-0.3) + 0*0.5 + 1*0.5 = 0.2
This is greater than the threshold (0), so the output = 1.
• If A=1 & B=0 → 1 * (-0.3) + 1*0.5 + 0*0.5 = 0.2
This is greater than the threshold (0), so the output = 1.
• If A=1 & B=1 → 1 * (-0.3) + 1*0.5 + 1*0.5 = 0.7 62

This exceeds the threshold (0), so the output = 1.

 The Perceptron Training Rule
The learning problem is to determine a weight vector that causes the
perceptron to produce the correct + 1 or - 1 output for each of the given
training examples.
To learn an acceptable weight vector
•Begin with random weights, then iteratively apply the perceptron to
each training example, modifying the perceptron weights whenever it
misclassifies an example.
•This process is repeated, iterating through the training examples as
many times as needed until the perceptron classifies all training examples
correctly.
•Weights are modified at each step according to the perceptron training
rule, which revises the weight wi associated with input xi according to the
rule. 63
• The role of the learning rate is to moderate the degree to
which weights are changed at each step. It is usually set to some
small value (e.g., 0.1) and is sometimes made to decay as the
number of weight-tuning iterations increases
64
The perceptron weight update rule converge toward successful
weight values.
Suppose the training example is correctly classified already by the
perceptron. In this case, (t - o) is zero, making Δwi zero, so that no
weights are updated.
If perceptron output→ -1 and target output → +1 :
we should increase w*x, if x>o, increasing wi will increase w*x
If perceptron output→ +1 and target output → -1 :
we should decrease w*x, if x>o, decreasing wi will decrease w*x

Drawback: The perceptron rule finds a successful weight vector

when the training examples are linearly separable, it can fail to
converge if the examples are not linearly separable. 65
 Gradient Descent and Delta Rule
Delta Rule

• W.K.T perceptron rule fails to converge if the examples are not linearly
separable.
• Delta rule is designed to overcome this difficulty
• If the training examples are not linearly separable, the delta rule converges
toward a best-fit approximation to the target concept
• To understand the Delta training rule, consider the task of training a linear
unit (liner unit = unthresholded perceptron)
• The output o for this linear unit is given by

• Thus, a linear unit corresponds to the first stage of a perceptron, without the
threshold.
• The training error of a hypothesis (weight vector) is measured by simply
halving the squared difference between the target output td and the linear
unit output od, summed over all training examples.

• where D is the set of training examples

• d is one training example in the set D
• td is the target output for training example ‘d’
• od is the output of the linear unit for training example ‘d’
 Gradient Descent
• Delta rule uses gradient descent to search the hypothesis space of possible
weight vectors to find the weights that best fit the training examples.
VISUALIZING THE HYPOTHESIS SPACE
• In the figure a. axes wo and wl represent possible values for the two weights of
a simple linear unit.
• The wo, wl plane therefore represents the entire hypothesis space.
• The vertical axis indicates the error E relative to some fixed set of training
examples.
• The error surface shown in the figure thus summarizes the desirability of every
weight vector in the hypothesis space (we desire a hypothesis with minimum
error).
• The arrow shows the negated gradient at one particular point, indicating the
direction in the wo, wl plane producing steepest descent along the error surface
• Given the way in which we chose to define E, for linear units this error surface
must always be parabolic with a single global minimum
• Gradient descent search determines a weight vector that minimizes E by
starting with an arbitrary initial weight vector, then repeatedly modifying it
in small steps. At each step, the weight vector is altered in the direction that
produces the steepest descent along the error surface. This process
continues until the global minimum error is reached.
 DERIVATION OF THE GRADIENT DESCENT RULE
• The direction of steepest descent along the error surface can be found by
computing the derivative of E with respect to each component of the vector
• This vector derivative is called the gradient of E
with respect to

• The training rule for gradient descent is given by:

•Here η is a positive constant called the learning rate, which determines the
step size in the gradient descent search.
•The negative sign is present because we want to move the weight vector in the
direction that decreases E
 • The training rule can also be written in its component form

𝜕𝐸
Calculate the gradient at each step. The vector of 𝜕𝑤
derivatives that form the gradient can be obtained by
differentiating E from Equation (2), as

71
GRADIENT DESCENT algorithm for training a linear unit

50
The gradient descent algorithm for training linear units is as follows:

➢ Pick an initial random weight vector.

➢ Apply the linear unit to all training examples
➢ Compute Δwi for each weight using Equation.

➢ Update each weight wi by adding Δwi, then repeat this process.

➢ If a small learning rate (η) is used, this algorithm will converge to a weight
vector with minimum error
➢ If η is too large, the gradient descent search runs the risk of overstepping the
minimum in the error surface rather than settling into it.
➢ For this reason, one common modification to the algorithm is to gradually
reduce the value of η as the number of gradient descent steps grows.
 Features of Gradient Descent Algorithm
Gradient descent is an important general paradigm for learning. It is a strategy for
searching through a large or infinite hypothesis space that can be applied
whenever

➢ The hypothesis space contains continuously parameterized hypotheses

➢ The error can be differentiated with respect to these hypothesis parameters

The key practical difficulties in applying gradient descent are

➢ Converging to a local minimum can sometimes be quite slow
➢ If there are multiple local minima in the error surface, then there is no guarantee
that the procedure will find the global minimum
74
 STOCHASTIC APPROXIMATION TO GRADIENT DESCENT
• The stochastic gradient descent approximates the gradient descent search by
updating weights incrementally, following the calculation of the error for
each individual example

where t, o, and xi are the target value, unit output, and ith input for the training
example in question
76
The key differences between standard gradient descent and stochastic
gradient descent are

➢ In standard gradient descent, the error is summed over all examples

before updating weights, whereas in stochastic gradient descent weights are
updated upon examining each training example.

➢ Summing over multiple examples in standard gradient descent requires

more computation per weight update step. On the other hand, because it
uses the true gradient, standard gradient descent is often used with a larger
step size per weight update than stochastic gradient descent.

➢ In cases where there are multiple local minima with respect to stochastic
gradient descent can sometimes avoid falling into these local minima
because it uses the various 𝛻Ed ( w ) rather than 𝛻E ( w ) to guide its search
77