Machine Learning

Module V

Handouts for Lecture - 39

INTRODUCTION TO CLUSTERING APPROACHES

Cluster analysis is the fundamental task of unsupervised learning. Unsupervised learning

involves exploring the given dataset. Cluster analysis is a technique of partitioning a
collection of unlabelled objects that have many attributes into meaningful disjoint groups or
clusters. This is done using a trial and error approach as there are no supervisors available as
in classification. The characteristic of clustering is that the objects in the clusters or groups
are similar to each other within the clusters while differ from the objects in other clusters
significantly.

Figure 13.1 a) Data samples b) Clusters’ Description

The input for cluster analysis is examples or samples. These are known as objects,
data points or data instances. All these terms are same and used interchangeably in this
chapter. All the samples or objects with no labels associated with them are called unlabelled.
The output is the set of clusters (or groups) of similar data if it exists in the input. For
example, the following Figure 13.1(a) shows data points or samples with two features shown

CEC, Benjanapadavu, Bantwal Page 1

 Machine Learning

in different shaded samples and Figure 13.1(b) shows the manually drawn ellipse to indicate
the clusters formed.

Visual identification of clusters in this case is easy as the examples have only two features.
But, when examples have more features, say 100, then clustering cannot be done manually
and automatic clustering algorithms are required. Also, automating the clustering process is
desirable as these tasks are considered difficult by humans and almost impossible. All
clusters are represented by centroids.

Example: For example, if the input examples or data is (3, 3), (2, 6) and (7, 9), then the
centroid is given as.

The clusters should not overlap, and every cluster should represent only one class. Therefore,
clustering algorithms use trial and error method to form clusters that can be converted to
labels.

Difference between Clustering & Classification

CEC, Benjanapadavu, Bantwal Page 2

 Machine Learning

Applications of Clustering

Challenges of Clustering Algorithms:

High-Dimensional Data: As the number of features increases, clustering becomes difficult.

Scalability Issue: Some algorithms perform well for small datasets but fail for large-scale
data.

Unit Inconsistency: Different measurement units (e.g., kg vs. pounds) can create problems.

Proximity Measure Design: Choosing an appropriate distance metric is crucial for accurate
clustering.

Advantages and Disadvantages of Clustering Algorithms:

Sl. Advantages Disadvantages

No.
1 Cluster analysis algorithms can handle Cluster analysis algorithms are sensitive to
missing data and outliers. initialization and order of the input data.
2 Can help classifiers in labelling the unlabelled Often, the number of clusters present in the
data. Semi supervised algorithms use cluster data have to be specified by the user.
analysis algorithms to label the unlabelled
data and then use classifiers to classify them.
3 It is easy to explain the cluster analysis Scaling is the problem
algorithms and to implement them.
4 Clustering is the oldest technique in statistics, Designing a proximity measure for the

CEC, Benjanapadavu, Bantwal Page 3

 Machine Learning

and it is easy to explain. It is relatively easy to given data is an issue.

implement.

Questions:

1. What is clustering?
2. What are the applications of clustering?
3. List the advantages and disadvantages of clustering?
4. What are the challenges in clustering?
5. List the differences between clustering and classification.

CEC, Benjanapadavu, Bantwal Page 4

 Machine Learning

Handouts for Lecture - 40

13.2 PROXIMITY MEASURES

Proximity measures determine similarity or dissimilarity among objects. Distance measures

(dissimilarity) indicate how different objects are. Similarity measures indicate how alike
objects are. property: More distance → Less similarity, and vice versa.

The distance between two objects, say i and j , is denoted by the symbol Dij.

If all of these conditions are satisfied, then the distance measure is called a metric. Based on
the data types of attributes of an objects, the distance measures vary.

Proximity measures:

Quantitative variables: These are used when data is continuous or numerical.

1. Euclidean Distance: It is one of the most important and common distance measures.
It is also called as L2 norm. It can be defined as the square root of the squared
differences between the coordinates of a pair of objects.
The Euclidean distance between objects x1 and x2 with k features is given as follows:

The advantage of Euclidean Distance is that distance does not change with the
addition of new objects. But the disadvantage is that if the units change, the resulting
Euclidean or squared Euclidean changes drastically. Another disadvantage is that as

CEC, Benjanapadavu, Bantwal Page 5

 Machine Learning

the Euclidean Distance involves a square root and a square, the computational
complexity is high for implementing the distance for millions or billions of operations
involved.
2. City block Distance: City block distance is known as Manhattan distance. This is
also known as boxcar, absolute value distance , Taxicab or L1 norm. The formula for
finding the distance is as follows:

3. Chebyshev Distance: Chebyshev distance is known as maximum value distance.

This is the absolute magnitude of the differences between the coordinates of a pair of
objects. This distance is called supermum distance or Lmax or L . The formula for
computing Chebyshev distance is as follows:

4. Minkowski Distance: In general, all the above distance measures can be generalized
as

This is called Miskowski distance. ere, r is a parameter. en t e val e o r is , t e

distance meas re is called city bloc distance, en t e r val e is t e distance
meas re is clidean distance. en r is , t en t is is ebys ev distance.

CEC, Benjanapadavu, Bantwal Page 6

 Machine Learning

Binary attributes: Binary attributes have only two values. Distance measures discussed
above cannot be applied to find the distance between objects that have binary attributes. For
finding the distance among objects with binary objects, the contingency table shown below
can be used.

Let x,y be the objects consisting of N-binary objects. Then, the contingency table can be
constructed by counting the number of matching transitions, 0-0, 0-1, 1-0 and 1-1. In other
ords, ‘a’ is t e n mber o attrib tes ere x attrib te is 0 and y attribute is 0. b is the
number of attributes where 𝑥 attribute is 0 and 𝑦 attribute is 1 and so on.

1. Simple Matching Coefficient (SMC): SMC is a simple distance measure and is

defined as the ratio of number of matching attributes and number of attributes. The
formula is given as,

2. Jaccard Coefficient: Jaccard Coefficient is another useful measure for and is given
as follows:

CEC, Benjanapadavu, Bantwal Page 7

 Machine Learning

3. Hamming Distance: It is another useful measure that can be used for knowing the
sequence of characters or binary values. It indicates the number of positions at which
characters or binary bits are different.
For example, the hamming distance between x=( 1 0 1) and y=(1 1 0) is 2 as x and y
differ in two positions.

Categorical variables: In many cases, categorical values are used. It is just a code or symbol
to represent the values. For example, for the attribute Gender, a code 1 can be given to female
and 0 can be given to male.

To calculate the distance between two objects represented by two variables, we need to find
only whether they are equal or not. This is given as,

Ordinal variables: Ordinal variables are categorical values but with an inherent order. For
example, designation is an ordinal variable. If job designation is 1 or 2 or 3, it means 1 is
higher than 2, code 2 is higher than 3. It is ranked as 1>2>3.

Let us assume the designations of office employees are clerk, supervisor, manager and
general manager. These can be designated as clerk=1, supervisor=2, manager=3 and general
manager=4. Then , the distance between employee X who is clerk and Y who is a manager is
obtained as,

CEC, Benjanapadavu, Bantwal Page 8

 Machine Learning

Vector type Distance measures: For text classifications, vectors are normally used. Cosine
similarity is a metric used to measure how the similar documents are irrespective of their size.
Cosine similarity measures the cosine of the angle between the two vectors projected in a
multi-dimensional space. The similarity function for vector objects can be defined as:

Questions:

1. Which are the distance metrics that can be used for numerical features?
2. List the distance metric to be used for binary attributes?
3. How do you find the difference between two categorical variables?
4. How do you find the difference between two vector type features?

CEC, Benjanapadavu, Bantwal Page 9

 Machine Learning

Handouts for Lecture - 41

4.3 HIERARCHICAL CLUSTERING ALGORITHMS

Hierarchical methods produce a nested partition of objects with hierarchical relationships

among objects. Often, the hierarchy relationship is shown in the form of dendrogram.
Hierarchical methods include categories, agglomerative methods and divisive methods. In
agglomerative methods, initially all individual samples are considered as a cluster, that is a
cluster with a single element. Then, they are merged and the process is continue to get a
single cluster. Divisive methods use another kind of philosophy, where a single cluster of all
the samples of the dataset taken initially is chosen and then partitioned. This is continued
until the cluster is split into smaller clusters.

The procedure of Agglomerative clustering is given as follows:

All the clusters that are produced by the hierarchical algorithms have equal diameters. The
main disadvantage of this approach is once the cluster if formed, it is an irreversible decision.

Single Linkage or MIN algorithm:

Hierarchical clustering algorithms produce nested clusters, which can be visualized as a

hierarchical tree or dendrogram. The idea behind this approach is proximity among clusters.
In single linkage algorithm, the smallest distance (x, y), where x is from one cluster and y is
from another cluster, is the distance between all possible pairs of the two groups or clusters
(or simply the smallest distance of two points where points are in different clusters) and is

CEC, Benjanapadavu, Bantwal Page 10

 Machine Learning

used for merging the clusters. This corresponds to finding of minimum spanning tree (MST)
of a graph.

The distance measures between individual samples or data points is already demonstrated in
the previous section.

CEC, Benjanapadavu, Bantwal Page 11

 Machine Learning

CEC, Benjanapadavu, Bantwal Page 12

 Machine Learning

Complete Linkage or MAX or Clique: In complete linkage algorithm, the distance (x,y ), (
where x is from one cluster and y is from another cluster), is the largest distance between all
possible pairs of the two groups or clusters ( or simply the largest distance of two points
where points are in different clusters) as given below. It is used for merging the clusters.

Average Linkage: In case of an average linkage algorithm, the average distance of all pairs
of points across the clusters is used to form clusters. The average value computed between
clusters ci and cj is given as follows:

CEC, Benjanapadavu, Bantwal Page 13

 Machine Learning

It is the general probability of an uncertain event before an observation is seen or some

evidence is collected. It is the initial probability that is believed before any new information
is collected.

Mean shift Clustering Algorithm

Mean-shift is a non-parametric and hierarchical clustering algorithm. This algorithm is also

known as mode seeking algorithm or sliding window algorithm. It has many applications in
image processing and computer vision. There is no need for any prior knowledge of clusters
or shape of the clusters present in the dataset. The algorithm slowly moves from its initial
position towards the dense regions.

The algorithm uses a window, which is basically a weighting function. Gaussian window is a
good example of a window. The radius of the kernel is called bandwidth. The entire window
is called a kernel. The window is based on the concept of kernel density function and its aim
is to find the underlying data distribution. The method of calculation is dependent on the
choice of windows. If a Gaussian window is chosen, then every point is assigned a weight
that decreases as the distance from the kernel center increases. The algorithm is given below.

CEC, Benjanapadavu, Bantwal Page 14

 Machine Learning

Advantages:

 No model assumptions
 Suitable for all non-convex shapes
 Only one parameter of the window, that is bandwidth is required.
 Robust to noise
 No issues of local minima or premature termination
Disadvantages:
 Selecting the bandwidth is the challenging task. If it is larger, then many clusters are
missed. If it is small, then many points are missed, and convergence occurs is the
problem.
 The number of clusters cannot be specified and user has no control over the
parameter.

PARTITIONAL CLUSTERING ALGORITHM

K-means is the straight forward iterative partitional algorithm. Here k stands for the user
specified number of clusters as users are not aware of the number of clusters present in the
dataset. The k-means algorithm assumes that the clusters do not overlap. Therefore, a sample
of data point can belong to only one cluster in the end. Also this algorithm can detect clusters
of shapes like spherical or circular.

CEC, Benjanapadavu, Bantwal Page 15

 Machine Learning

Initially, the algorithm needs to be initialized. The algorithm can select k data points
randomly or use the prior knowledge of the data. In most cases, in k-means algorithm setup,
prior knowledge is absent. The composition of the cluster is based on the initial condition;
therefore, initialization is an important task. The sample or data points need to be normalized
for better performance.

The core process of the k-mean algorithm is assigning a sample to a cluster, that is, assigning
each sample or data point to the k cluster centres based on its distance and the centroid of the
clusters. This distance should be minimum. As a new sample is added, new computation of
mean vectors of the points for that cluster to which sample is assigned is required. Therefore,
this iterative process is continued until no change of instances to clusters is noticed. This
algorithm then terminates, and the termination is guaranteed.

k-means can also be viewed as greedy algorithm as it involves partitioning n samples to k

clusters to minimize Sum of Squared Error (SSE). SSE is a metric that is a measure of error
that gives the sum of the squared Euclidean distances of each data to its closest centroid. It is
given as:

Here, cₙ is the centroid of the ith cluster, x is the sample or data point and dist is the Euclidean
distance. The aim of the k-means algorithm is to minimize SSE.

Advantages:

1. Simple

CEC, Benjanapadavu, Bantwal Page 16

 Machine Learning

2. Easy to implement

Disadvantages:

1. It is sensitive to initialization process as change of initial points leads to different

clusters.
2. If the samples are large, then the algorithm takes a lot of time.

How to choose value of k?

k is a user-defined number of clusters. There are no strict rules for selecting it. Typically, k-
means is run with various k values, and the within-group variance is plotted as an Elbow
curve. The optimal k is found where the curve flattens.

Complexity: The k-means algorit m as a complexity o Θ(nkld), where n is the number of

samples, k is the number of clusters, I is the number of iterations, and d is the number of
attributes. Overall, the complexity is O(n²).

CEC, Benjanapadavu, Bantwal Page 17

 Machine Learning

CEC, Benjanapadavu, Bantwal Page 18

 Machine Learning

CEC, Benjanapadavu, Bantwal Page 19

 Machine Learning

Questions

1. What is the difference between agglomerative and divisive clustering algorithms?

2. What is the formula to find the difference between the clusters in Single Linkage?
3. What is the formula to find the difference between the clusters in Complete Linkage?
4. What is the formula to find the difference between the clusters in Average Linkage?
5. Explain the working of Mean-shift clustering?
6. Explain the working of K-means algorithm?

CEC, Benjanapadavu, Bantwal Page 20

 Machine Learning

Handouts for Lecture - 42

DENSITY BASED METHODS

Density-based spatial clustering of applications with noise (DBSCAN) is one of the density-
based algorithms. Density of a region represents the region where many points above the
specified threshold are present. In a density-based approach, the clusters are regarded as
dense regions of objects that are separated by regions of low density such as noise. This is
same as a man’s int itive ay o observing cl sters.

The concept of density and connectivity is based on the local distance of neighbours. The
nctioning o t is algorit m is based on t o parameters, t e size o t e neig bo r ood (ε)
and the minimum number of points (m).

1. Core point – A point is called a core point if it has more than specified number of
points (m) it in ε-neighbourhood.

2. Border point – A point is called a border point if it has fewer than 'm' points but is a
neighbour of a core point.

3. Noise point – A point that is neither a core point nor border point.

The main idea is that every data point or sample should have at least a minimum number of
neig bo rs in a neig bo r ood. T e neig bo r ood o radi s ε s o ld ave at least m points.
The notion of density connectedness determines the quality of the algorithm.

The following connectedness measures are used for this algorithm.

1. Direct density reachable – The point X is directly reachable from Y, if:

o (a) X is t e ε-neighbourhood of Y

o (b) Y is a core point

2. Densely reachable – The point X is densely reachable from Y, if there is a set of core
points that leads from Y to X.

3. Density connected – X and Y are densely connected if Z is a core point and thus
points X and Y are densely reachable from Z.

CEC, Benjanapadavu, Bantwal Page 21

 Machine Learning

Advantages:

1. No need for specifying the number of clusters beforehand

2. The algorithm can detect clusters of any shape
3. Robust to noise
4. Few parameters are needed

Complexity of this algorithm is O(n log n)

Questions

1. What do you mean by density based clustering?

2. Explain DBSCAN algorithm
3. What are the advantages of DBSCAN algorithm?
4. What is the time complexity of DBSCAN algorithm?

CEC, Benjanapadavu, Bantwal Page 22

 Machine Learning

Handouts for Lecture - 43

GRID BASED APPROACH

Grid based approach is a space based approach. It partitions space into cells, the given data is
fitted on the cells for cluster information. There are three important concepts that need to be
mastered for understanding the grid based schemes. They are

1. Subspace clustering
2. Concept of dense cells
3. Monotonicity property

Subspace clustering

Grid-based algorithms help cluster high-dimensional data with many attributes. Often, only a
subset of attributes is needed for clustering, depending on the application (e.g., age may
matter for disease profiling, but not address).

Finding subspaces is challenging as N dimensions can ave ⁿ⁻¹ s bspaces. To andle t is,
CLIQUE (Clustering in Quest) is used. It is a grid-based method using a multiresolution grid
to find clusters in subspaces.

Concept of Dense Cells:

CLIQUE partitions each dimension into several overlapping intervals and intervals it into
cells. Then, the algorithm determines whether the cell is dense or sparse. The cell is
considered dense i it exceeds a t res old val e, say τ. Density is de ined as t e ratio o
number of points and volume of the region. In one pass, the algorithm finds the number of
cells, number of points, etc. and then combines the dense cells. For that, the algorithm uses
the contiguous intervals and a set of dense cells.

CEC, Benjanapadavu, Bantwal Page 23

 Machine Learning

CLIQUE uses anti-monotonicity property or apriori property of the famous apriori algorithm.
It means that all the subsets of a frequent item should be frequent. Similarly, if the subset is
infrequent, then all its supersets are infrequent as well. Based on the apriori property, one can
conclude that a k-dimensional cell has r points if and only if every (k - 1) dimensional
projections of this cell have at least r points. So like association rule mining that uses apriori
rule, the candidate dense cells are generated for higher dimensions. The algorithm works in
two stages as shown below.

Advantages of CLIQUE:

CEC, Benjanapadavu, Bantwal Page 24

 Machine Learning

1. Insensitive to input order of objects

2. No assumptions of underlying

Disadvantages:

The disadvantage of CLIQUE is that tuning of grid parameters, such as grid size, and finding
optimal threshold for finding whether the cell is dense or not is a challenge.

Questions:

1. What is Subspace clustering?

2. What is Monotonicity property?
3. Explain CLIQUE algorithm.
4. List the advantages and disadvantages of CLIQUE.

CEC, Benjanapadavu, Bantwal Page 25

 Machine Learning

Handouts for Lecture - 44

OVERVIEW OF REINFORCEMENT LEARNING

Reinforcement learning (RL) mimics human beings and is a branch of machine learning.
Humans observe the environment through senses such as eye and ear. The inputs are
processed by brain. The brain then suggests the actions and acts voluntarily or involuntarily.

In humans, learning happens in a real world called environment. Take a kid for an example.
How does the kid learn? The kid interacts with the environment and gains valuable
experience. Experience leads to learning. For example, when a kid accidently burns his hand
in fire, he learns to stay away from it in the future and be careful. Similarly, the kid learns to
do good things repeatedly by the encouragement or gifts given by parents or teachers.
Awards can be positive or negative. Awarding a kid is a positive reinforcement and scolding
is a negative reward or deterrent as shown in Figure below. Thus, kids gain experience and
learn many things through rewards and punishments (negative rewards).

In computers, these scenarios can be simulated in many ways. As a kid executes many
actions and receives a mix of positive and negative rewards that lead to gaining experience
and learning, a computer program or robot can learn through experiences of simulated
scenarios. Thus, reinforcement learning is a mathematical framework for learning. There are
two types of reinforcement learning – positive and negative. Positive reinforcement learning
is a recurrence of behaviour due to positive rewards. Rewards increase strength and the
frequency of a specific behaviour. This encourages to execute similar actions that yield
maximum reward. Similarly, in negative reinforcement learning, negative rewards are used as
a deterrent to weaken the behaviour and to avoid it. In a maze game, there may a danger spot
that may lead to loss. Negative rewards can be designed for such spots so that the agent does

CEC, Benjanapadavu, Bantwal Page 26

 Machine Learning

not visit that spot. Positive and negative rewards are simulated in reinforcement learning, say
+10 for positive reward and -10 for some danger or negative reward.

Reinforcement learning is an example of semi-supervised learning technique and is used to

model sequential decision-making process.

SCOPE OF REINFORCEMENT LEARNING

What are the situations where reinforcement learning can be used? Consider the following
grid game shown in Figure 14.2, where a robot can move. Assume the starting node is E and
goal node is G, the game is about finding the shortest path from starting to goal state.

Consider another grid game as shown in Figure 14.3. In this grid game, the grey tile indicates
the danger, black is a block and the tile with diagonal lines is the goal. The aim is to start, say
from bottom-left grid, using the actions left, right, top and bottom to reach the goal state.

Reinforcement learning is highly suitable for solving problems like this, especially ones with
uncertainty. Reinforcement learning is not suitable for environments where complete
information is available. For example, problems like object detection can be better solved by
classifiers than reinforcement.

Characteristics of Reinforcement Learning

1. Sequential decision making – Consider the Figure 14.3. It can be seen the path from
start to goal is not done in one step. It is a sequence of decisions that leads to the goal.
One wrong move may result in a failure. This is the main characteristic of
reinforcement learning.

2. Delayed feedback – Often, rewards are not immediate. One must spend many moves
to get final success or failure. Feedback in terms of reward is often delayed.

CEC, Benjanapadavu, Bantwal Page 27

 Machine Learning

3. The agent actions are interdependent as any action affects the subsequent actions. For
example, one wrong move of an agent may lead to failure.

4. Time related – All actions are associated with time stamps inherently as all actions
are ordered as per the timeline inherently.

Challenges of Reinforcement Learning

1. Reward design is a big challenge as in many games, as determining the rewards and
its value is a challenge.

2. Absence of a model is a challenge – Games like chess have fixed board and rules.
But, many games do not have any fixed environment or rules. There is no underlying
model as well. So, simulation must be done to gather experience.

3. Partial observability of states – Many states are fully observable. Imagine a scenario
in a weather forecasting where the uncertainty or partial observability exists as
complete information about the state is simply not available.

4. Time consuming operations – More state spaces and possible actions may
complicate the scenarios, resulting in more time consumption.

5. Complexity – Many games like GO are complicated with much larger board
configuration and many possibilities of actions. So, labelled data is simply not
available. This adds more complexity to the design of reinforcement algorithms.

Applications of Reinforcement Learning

There are many applications of RL. Some of the application domains where reinforcement
learning is used are listed below:

 Industrial automation

 Resource management applications to allocate resource

 Traffic light controller to reduce congestion of traffic

 Personalized recommendation systems like news

 Bidding for advertisement

CEC, Benjanapadavu, Bantwal Page 28

 Machine Learning

 Customized applications

 Driverless cars

 Along with deep learning games like Chess and GO

 Deep mind applications like to generate programs and images

Questions:

1. What is Reinforcement Learning, and how does it differ from other types of machine
learning?
2. Describe the roles of the agent, environment, actions, and rewards in the context of
Reinforcement Learning.
3. How does the learning process in Reinforcement Learning mimic the way humans
learn from their environment?
4. What are positive and negative reinforcement in the context of RL? Can you provide
examples of each?
5. Explain the significance of sequential decision-making in Reinforcement Learning.
Why is it a crucial characteristic?

CEC, Benjanapadavu, Bantwal Page 29

 Machine Learning

Handouts for Lecture - 45

REINFORCEMENT LEARNING AS MACHINE LEARNING

In supervised learning, there is a supervisor but in reinforcement learning the supervisor is

absent. Supervised learning learns using labelled data. It maps the input to fixed, pre-defined
output. Supervised learning has a luxury of labelled data. In reinforcement learning, there is
no labelled data. Instead, the labels are generated by the interaction of the agent with the
environment. The agent may be a human or a computer program such as a chatbot. It can be
obvious that games like Chess and GO cannot be solved using supervised learning as training
dataset of these games cannot be generated. In the absence of the training set, the only option
left is reinforced learning where the agent can interact with the environment and learns by
trial and error.

Thus, one can observe the difficulties faced by reinforcement learning when compared with
other machine learning algorithms. In supervised classifiers, the choice is one-shot, say
cancer or not cancer. But in reinforcement learning, it is a sequential decision making, say
finding the path from start to goal state. One must wait for more moves to see success or
failure. The reason behind success and failure is found by observing the patterns over a long
time and these decisions have longer consequences. For example, in a game, one wrong move
may result in failure.

Reinforcement learning is different from supervised learning. The difference between

reinforcement learning and supervised learning are as follows.

The difference between reinforcement learning and unsupervised learning are as follows:

CEC, Benjanapadavu, Bantwal Page 30

 Machine Learning

Questions:

1. What is Reinforcement learning?

2. How is Reinforcement learning related to machine learning?
3. What are the differences between Reinforcement learning and Unsupervised learning?

CEC, Benjanapadavu, Bantwal Page 31

 Machine Learning

Handouts for Lecture - 46

COMPONENTS OF REINFORCEMENT LEARNING

The components of reinforcement learning are shown in figure below. These are
environment, agent , actions and rewards.

Reinforcement Problems

There are two types of problems in reinforcement learning – Learning and Planning.

In learning problems, the environment is unknown and the agent learns by trial and error. The
agent interacts with the environment to improve policy.

Planning is another problem where the environment is known and the agent computes with
the model and improves policy.

Environment and Agent

Environment is the world where all actions take place. It is the framework, where the input,
output and reward are specified. The environment describes the state or state variables or
simply as state. Initially, the environment is in a state called initial state.

For example, in a car system, the maps, game rules and obstructions in the road are described
in the environment.

An agent is an autonomous body that looks at the environment and takes an action. It can be
any human or another computer program such as a robot or chatbot.

CEC, Benjanapadavu, Bantwal Page 32

 Machine Learning

States and Actions

The input for reinforced learning is called a state and the output is action.

Consider the following graph in Figure 14.5 generated by two actions, up and down, by an
agent.

In Figure 14.5, the states are A, B, C, D, E, F, G, H and I. These states can be cities of a
shortest path problem or any other state encountered by a robot navigation. Let A be the
starting state and G t e goal or target state to be reac ed. T e symbol ‘S’ is sed to denote t e
general state and ‘s’ t e speci ic state. ‘sₜ’ is sed to denote a state at time ‘t’.

Other important nodes are:

1. GOAL node – This is also known as terminal node and absorbing state. It is the goal
and the agent aims to get as it is the highest discounted cumulative node.

2. Non-terminal node – All other nodes are called non-terminal nodes.

3. Start – The initial state.

Actions are transitions between states, say the path between A and B is caused by UP action.
Then, the agent collects the rewards. In the game shown in Figure 14.5, the actions are UP
and DOWN only. Symbol A is used to denote the general actions – UP and DOWN. The
symbol ‘a’ is sed to speci y t e speci ic action and ‘aₜ’ is sed to denote t e action at time
‘t’.

CEC, Benjanapadavu, Bantwal Page 33

 Machine Learning

‘ pisodes’ is t e n mber o steps necessary to reac t e goal state from start state. For
example, in Figure 14.5, the aim is to find optimal path between A and G. There are two
types of episodes.

One is called episodic and another is called continuous. In episodic tasks, there is a well-
defined starting state and end state. End state is called as terminal state or goal state. An
episode is one which consists of states, actions, and rewards. For example, all the paths from
A to G, such as

A -> B -> D -> F -> G

A -> B -> E -> G

are all examples of episodes. An episode is one that starts from a starting state and reaches
the goal state. So, a successful episode would be E-F-C-B-A-D-G.

Sometimes, there may not be any goal node. A continuous task has no terminal state, that is,
no designated goal states.

Policies

The role of algorithms is called a policy in reinforced learning and policy maps states to
actions. In short, a policy takes the input states, processes it and suggests an action. Policies
characterize the agent behaviour function. There are two types of policies – deterministic and
stochastic.

The deterministic policy function is given as:

a = π(s)
(14.1)
A deterministic policy states that a given state always returns the same action, i.e.,
premapped.

The stochastic policy function is given as:

π(a | s) = Pr[aₜ = a | sₜ = s] (14.2)

It is t e probability o ta ing an action ‘a’ ile in state ‘s’. T e aim o t e agent is to learn
policy function so that the best actions are selected.

CEC, Benjanapadavu, Bantwal Page 34

 Machine Learning

Given multiple policies, how to decide a better policy? There are many policies. A better
policy is the one that has better cumulative expected reward over other policies. More
formally, the value of the state is higher for the best action if the policy is optimal.

Rewards

The system performance is measured by reward system. A reward is something that the
environment produces to the agent. In short, it maps a set of states to a real number. The
symbol ‘r’ is sed or re ard, ic depends on c rrent state ‘s’, action ‘a’ and next state
‘s′’.

Immediate Reward
The environment immediately delivers a reward after the execution of action and the total
reward is associated with the episode. This is the sum of all rewards that come from the first
move to the last mode. The total reward is also called as return or goal.

It can be observed that every game has states. It then selects an action and transits to another
state. As a result of the transition, it collects the rewards too. This continues till the terminal
state. The return is given as:

Gₜ = rₜ₊₁ + rₜ₊₂ + rₜ₊₃ + ⋯ + r_T (14.3)

ere, Gₜ is t e ret rn and r_T is t e terminal or inal state.

Long-term Reward
Unlike immediate rewards, long-time rewards are given after the end like the objective of the
game.

The total future re ard is t e s m o t e c rrent move re ard and all ot er moves’ re ards
till the end of the episode. For example, if there are 9 moves in an episode, the total future
reward of the third move will be the sum of reward of that move and rewards of move 4 to
move 9 present in that episode.

More often, the iteration can be without terminal state too. In other words, it is a continuous
tas . To comp te t re re ards or tility, one can introd ce a actor γ called disco nt actor:

CEC, Benjanapadavu, Bantwal Page 35

 Machine Learning

Gt is called return or utility or total reward. It is a value that indicates the closeness of the
goal state.

Its value ranges from 0 to 1. It gives more value for the immediate return. The
unpredictability can be tackled by discount factor, which is the sum of the immediate reward
and all ot er s bseq ent re ards m ltiplied by a actor o γ.

en γ is , t e disco nt actor is close to t e total re ard. en γ is zero, only immediate

reward matters and virtually all future actions are not taken into account. Often, the value of γ
is chosen as 0.8 or 0.9.

Example 14.1:

Let s ass me t at at t e i t step, t e re ard is + . I t e disco nted actor γ is 0.7, at is

t e disco nted re ard or tility? Ass me t at t e previo s steps’ re ards till t e i t step are
zero.

The reward at 5th step is 1. Therefore, the discounted reward using the Eq. (14.4) is given as:

(0.7)^5 \times 1 = 0.16807

Broadly stated, reinforcement algorithms are classified as model-based and model-free

methods based on the availability of models for the given problem. Certain real-world
problems can be solved by constructing models using Markov decision process.

Questions:

1. What are the primary components of Reinforcement Learning, and how do they
interact with each other?
2. Differentiate between learning problems and planning problems in Reinforcement
Learning.
3. How is the environment defined in the context of Reinforcement Learning, and what
role does it play?

CEC, Benjanapadavu, Bantwal Page 36

 Machine Learning

4. In what ways can the agent be characterized in Reinforcement Learning?

5. What are states and actions in Reinforcement Learning, and how do they relate to
each other?
6. Define what is meant by a "goal node" in the context of an RL problem. What is its
significance?

Handouts for Lecture - 47

MARKOV DECISION PROCESS:

CEC, Benjanapadavu, Bantwal Page 37

 Machine Learning

CEC, Benjanapadavu, Bantwal Page 38

 Machine Learning

CEC, Benjanapadavu, Bantwal Page 39

 Machine Learning

If rewards are added to markov chain, the markov decision process is obtained where edges
are associated with probability as well as reward.

The components of MDP are,

1. A set of states
2. A set of actions
3. Reward function R
4. Policy π
5. Value V

The simplest structure of MDP is Markov chain where the environment is modelled as a
graph. The nodes of graph represent states and edges represent transitions. Each edge is
associated with static probability.

Markov assumption holds good for reinforcement learning. Markovian property states that
the probability of reaching a state sts_tst and getting the reward rtr_trt depends solely on the
preceding states st− s_{t- }st− and rt− r_{t- }rt− . All other previous states are not
important. This is called Markov assumption.

A state is Markov if and only if:

Here, s′ and s are ne and old states and 'a' is t e action, and 'r' is t e re ard.

MDP performs the following actions:

The aim of the agent is always to maximize the total rewards accumulated over time. The
movement of one state to another is called a transition. The agent manipulates the
environment from one state to another.

CEC, Benjanapadavu, Bantwal Page 40

 Machine Learning

The state transition probability is given as follows:

It indicates t e moving rom states to s′ a ter ta ing an action 'a'. In ot er ords, given a state
's', it is the probability of t e occ rrence o next state 's′. One can also represent it as a matrix
called state transition matrix where each row indicates the transition probability from one
state to another. The expected value of the reward is given as:

Training and Testing of RL systems:

Once the MDP is modeled, the next stage is called training and inference. The agent tries to
accomplish goal repeatedly and modify its parameter over time. This is called learning. Once
the trained model is available, it is put to use and this process is called inference. At
deployment level, training and inference go together and when environment is changed,
training is done again. This is to improve the system.

MULTI-ARM BANDIT PROBLEM AND REINFORCEMENT PROBLEM TYPES

Reinforcement learning uses trial and error to learn a series of actions that maximize the total
reward. There are two sub-problems in the reinforcement problem.

1. The main problem is the prediction of total reward or return. This is called prediction,
policy evaluation or value estimation. It requires a formulation of a function called
state-value function. The problem of estimating the state value function can be done
using temporal differencing or TD-Learning.

2. The second problem is finding actions that maximize the returns. It is called policy
improvement. Both these things can be combined as policy iteration which
alternatively uses the above to find optimal policy.

Assume a robotic arm in a hypothetical casino that when activated through a lever returns
money in the range, say, $1 to $10. A multi-arm bandit problem can have N levers. The

CEC, Benjanapadavu, Bantwal Page 41

 Machine Learning

important issue is that the arm randomly returns the money in the range $1-$10. This is called
a reward. Given a limited chance, the aim of the user is to get as much money as possible.

Let us introduce a problem that is encountered in reinforcement learning very often called
multi-arm (or N-arm) bandit problem. A 5-armed slot machine is shown in Figure 14.7.

The point is which lever is the best one to activate to get maximum profit. A possible answer
to this question is: the lever that returns average return more than other levers is the best slot
machine. Let us formalize the problem: Given k number of chances to access N-arm slot
machine, with actions of pulling the lever with associated rewards, r1,r2,…,rk, the expected
reward given is given as:

This function is called action-value function or Q function. This indicates the value of taking
a particular action 'a'.

The best action is the action that returns the highest average return and is the indicator of the
action quality.

CEC, Benjanapadavu, Bantwal Page 42

 Machine Learning

Exploration vs Exploitation and Selection Policies

The selection of actions may be based on the concept of exploration and exploitation.

Exploration: the method explores all actions even if it results in sub-optimal decisions. It is
considered to be an adventurous method. In games, it works by exploring all actions and
observing rewards.

Exploitation: It is a naïve approach that uses current knowledge and keeps exercising those
options repeatedly. Its aim is to choose only one action based on experience and always get
the same reward. This is not adventurous and is mostly sub optimal.

There must be a balance between exploration and exploitation for selection. Based on these
principles, selection policies can be designed.

Greedy method:

In the absence of knowledge, the best action is chosen using the greedy method, based on
exploitation. In a multi-arm bandit problem, the agent tries all levers, notes down the rewards,
and repeatedly selects the lever giving the highest reward. This is called greedy approach,
where there's no exploration, only exploitation of known maximum rewards.

Greedy approach is an algorithm design technique for optimization problems, aiming to

maximize or minimize an objective function by selecting the best local option at each step. It
assumes optimal substructure, meaning a problem contains optimal solutions to its
subproblems.

Two key properties:

 Optimal substructure: Optimal solutions to subproblems help solve the overall

problem.

 Greedy choice property: Making locally optimal choices leads to a global optimal
solution.

CEC, Benjanapadavu, Bantwal Page 43

 Machine Learning

Reinforcement Agent Types:

An agent can be characterized using these methods:

1. Value based approaches: The aim of value-based approaches is to optimize V(s).

Here, V(s) is a function that returns the maximum expected future reward the agent
ill get at eac state disco nted by a disco nt actor γ. This value is then used to
select the state for the agent. A large value is chosen by the agent to pick the state.
2. Policy based approaches: T e aim is to ind an optimal policy. A policy π is a
strategy. A policy is a function that maps a state to a probability distribution of all
possible actions in that strategy. It aims to find the optimal policy to map each state to
the best action.
3. Hybrid methods: These are hybrid methods combining both value-based and policy-
based methods.
4. Model-based approaches: First, the model is constructed for the environment as it is
available. Markov Decision Process is one way of modelling the given problem.
5. Model free methods: Here, models are not available and hence some methods are
used to simulate the model virtually. Techniques like temporal differencing and
Monte Carlo methods are generally used to simulate such models.

Reinforcement Algorithm Selection:

Reinforcement agent algorithms are decided based on the criteria of availability of

models, environment and nature of updates.

CEC, Benjanapadavu, Bantwal Page 44

 Machine Learning

Questions:

1. What is a Markov Chain and what property does it satisfy?

2. How is the transition matrix ( P ) defined and what does it represent in a Markov
Chain?
3. What are the key components of a Markov Decision Process (MDP)?
4. What actions does an agent perform in an MDP to maximize total rewards?
5. What are the two sub-problems in reinforcement learning mentioned in the context of
maximizing total rewards?
6. What are the characteristics of value-based and policy-based approaches in
reinforcement learning?

CEC, Benjanapadavu, Bantwal Page 45

 Machine Learning

Handouts for Lecture - 48

MODEL BASED LEARNING(PASSIVE LEARNING)

Passive Learning means model-based environment, which is based on known environment.

By known environment, it means that for any state, the next state and action, the probability
distribution is known. Markov Decision Process (MDP) and dynamic programming are
excellent tools for solving reinforcement problems.

The mathematical framework required for passive learning is provided by Markov Decision
Process. These model-based reinforcement problems can be solved using dynamic
programming after the construction of the model using MDP.

In reinforcement learning, the focus is to take action a to transit from the current state to the
end state. The aim is to get rewards for the actions. They can be positive or negative.

The objective is to maximize the rewards by choosing the optimal policy.

Max E ( rₜ | r, sₜ ) for all possible val es o ‘sₜ’ at time ‘t’.

There are multiple courses of actions for a given state. The agent can prefer any course of
action. So, the behaviour of the agent needs to be understood. The algorithm to do that is
called a policy. A policy is the distribution of all actions with the probability of choosing
these actions. Different actions can have different rewards. It is necessary to find the total
reward. This is possible only if the reward is quantified. It is done using value functions.

State Value Notation

Let v represent a value of the state. The state-value function is defined as follows:

It implies that state-val e nction o an MDP is t e expected ret rn rom state ‘s’ or a
policy.
ere, Vπ(s) adds up all expected rewards, possibly discounted rewards. It also indicates how
good the state is! The subscript π indicates that the value depends on policy π.

CEC, Benjanapadavu, Bantwal Page 46

 Machine Learning

The value function quantifies the amount of reward for an action or state. It gives the
expected sum of future rewards for a given state under policy π.

The optimal state-value function is denoted as:

In other words, it is the maximum value function over all policies.

Dynamic programming is used to solve this problem. As discussed in Box 14.2, dynamic
programming requires the recursive formulation of the given problem. This recursive
formulation for solving the state-value problem is called Bellman equation and is given as:

Action Value Function

Apart from value function, one more function called Q function is introduced. This function
returns a real value. It is a function that indicates the total reward by the agent in state s and
pic s an action ‘a’ and follows a policy π. It indicates how good the action is in the state. It is
denoted as follows:

This shows the policy π as t e probability o c oosing an action ‘a’ en in state ‘s’.

vₛ is t e maxim m total re ard en starting rom state ‘s’. It ill be a maxim m o Q(s, a)
over all possible actions. Therefore,

If Q is known, then the best action to take optimally can be given as:

Also, one can write Qₚ in terms of vₚ as follows:

CEC, Benjanapadavu, Bantwal Page 47

 Machine Learning

Algorithms for solving Reinforcement Problems using Conventional Methods

After defining the state value and action value functions, one can define the algorithms to
solve reinforcement problems. There are two types of algorithms

1. Value Iteration
2. Policy Iteration

Value Iteration: value iteration estimates v in terms of steps as:

Policy Iteration: The second algorithm is policy iteration. The task of finding an optimal
policy consists of two steps:

 Policy Evaluation
 Policy Improvement

Policy Evaluation:

Initially, for a given policy, the algorithm starts with value v1v_1v1 function as zero. There is
no reward. The Bellman equation is used to obtain value of v2v_2v2. Then, the value of
v3v_3v3 is obtained from v2v_2v2. This process is continued till the optimal policy
vπv_{\pi}vπ is obtained. In other words, at each iteration, all the state values are updated
using the previous iteration value.

CEC, Benjanapadavu, Bantwal Page 48

 Machine Learning

Policy eval ation estimates vπv_{\pi}vπ in terms of steps:

and policy improvement is possible i t e ne policy π′>π\pi' > \piπ′>π.

The improvement is done using greedy approach.

The algorithm for policy evaluation is given as follows:

Policy Improvement
The policy improvement can be done as follows:

1. val ate t e policy π\piπ it policy eval ation.

2. Solve t e Bellman eq ations or t e given policy to get vπv_{\pi}vπ.

3. Improve t e policy by applying t e greedy approac or policy vπv_{\pi}vπ so that

t e policy becomes π′\pi'π′.

4. Repeat t e process till vπv_{\pi}vπ policy converges to optimal policy v∗v_*v∗.

The algorithm is given as follows:

CEC, Benjanapadavu, Bantwal Page 49

 Machine Learning

Questions:

1. What is passive learning in the context of reinforcement learning, and how is it

different from active learning?
2. How does a Markov Decision Process (MDP) contribute to solving reinforcement
learning problems?
3. What does the term "known environment" imply in a model-based reinforcement
learning context?
4. What is the role of a policy in reinforcement learning, and how is it mathematically
represented?

CEC, Benjanapadavu, Bantwal Page 50

 Machine Learning

Handouts for Lecture - 49

MODEL FREE METHODS:

In model free methods, there is no complete knowledge of the environment. So, how to
determine the rewards then?

The simplest way to determine rewards is to play the game. If the game ends in win, then all
actions that are encountered in the episode are given a reward, say +1. If the game is lost,
then all actions are given a value of –1. The only problem is that the game may be lost due to
the last bad move while all other actions may be good.

The second method is the continuous formulation. Here, the reward is determined after the
action. For example, in multi-arm bandit problem, the immediate reward of $1 – $10 can be
an example of continuous formulation. If the actual value is not known, then it can be
estimated.

The third formulation is the discounted returns. The discounted return computed as the long-
term reward can be one solution.

Some of these techniques are used in these model-free techniques such as:

1. Monte Carlo (MC) methods

2. Temporal Difference Learning

One of the simplest ways of simulating a model is by using Monte-Carlo methods. This is
discussed in the subsequent section.

Monte-Carlo Methods

Monte Carlo (MC) methods do not assume any model. Therefore, complete knowledge of the
environment is not available. This is similar to human and animal experience where the
knowledge is gained by experience, and experience is gained from the interaction with the
environment. MC uses the methods of experience as well as simulation to gain knowledge of
the environment.

CEC, Benjanapadavu, Bantwal Page 51

 Machine Learning

The experience is divided into many episodes. An episode, as discussed earlier, is a sequence
of states from starting state to goal state. MC makes the following assumptions:

1. All episodes should terminate. No matter from where we start, the episode should end.
2. MC methods use value-action functions. These values are computed only after the
completion of the episode. So, MC methods are incremental methods.

The MC method collects the reward at the end of the episode. Then, it is used to find
maximum expected future reward. This method does not use expected return. Instead, it uses
the empirical mean as return. The total return over many episodes divided by the number of
episodes gives the average, alternative way to count every time a state is encountered and
reward until termination. Since the problem is non-stationary, the value function is computed
for fixed policy. Then, the policy is revised using dynamic programming.

The mean value is computed as:

Thus, the incremental Monte-Carlo update at the end of the episode using the approach -
incremental every-visit Monte-Carlo is given as:

ere, α\alp aα is called learning rate. The algorithm for MC methods is as follows:

4.8.2 Temporal Difference Learning

Temporal Difference (TD) learning is an alternative to the Monte Carlo method. It is model-
free. It learns from the environment based on experience and interaction, as MC methods are
based on the principle of bootstrapping. TD is called a bootstrapping method because the
update is based on the existing estimate and future reward. The difference is the updated new
estimate. In the TD method, at every step, an estimate of the final reward is calculated at each
state. Then, immediately the state-action is updated for every step.

CEC, Benjanapadavu, Bantwal Page 52

 Machine Learning

Unlike the Monte Carlo method that computes the rewards at the end of the episode, TD
Learning computes the rewards at every step. The difference is listed in the following Table
14.4.

Differences Between Monte-Carlo Method and TD Learning Method

The temporal differencing (TD) target is given as:

In TD(0), the update towards the estimated return is given as:

Here, αα is a constant parameter, rtrt is the reward after time 't', and stst is the state visited at
time 't'.

TD Learning can be accelerated through eligibility traces as future rewards may be

distributed across one-to-many nodes. As soon as it receives an input, it uses a table so that
the previous prediction is updated. Eligibility traces provide an alternative short-term
memory where all previous predictions are noted in the table. This leads to a family of
algorithms known as TD(λ).

 Here, λ is called the decay parameter, whose value ranges between 0 and 1.

 If λ = 0, then only the previous prediction is updated.

 If λ = 1, then all the predictions are updated.

The algorithm for TD learning is given as follows.

CEC, Benjanapadavu, Bantwal Page 53

 Machine Learning

Questions:

1. What distinguishes model-free methods from model-based methods in reinforcement

learning?
2. In the episodic formulation of model-free learning, how are rewards typically
assigned to actions within an episode?
3. What is the key assumption made by Monte Carlo (MC) methods regarding episodes?
4. How does the Monte Carlo method estimate the value function for a given policy?

CEC, Benjanapadavu, Bantwal Page 54

 Machine Learning

Handouts for Lecture - 50

Q-LEARNING

Q-Learning is an off-policy method because Q is updated based on policies that are implicit
to Q and is better guaranteed for maximum returns. Q indicates Quality.

What is Q-value?

Q(s, a) is a numerical value assigned to a state-action pair. It represents the value of the
action that is performed in state 's'.

The main objective is to find the Q-value, which is the immediate reward plus the future
rewards—collectively known as the total return reward. To compute this, the following
information is necessary:

1. Starting state

2. Action

3. Reward

4. New state

Initially, a table called the Q-table is constructed and filled with random initial values. Q-
learning involves two policies:

 Learning policy

 Update policy

Q-learning is implemented using methods like greedy, softmax, or softmax plus.

The agent's next move will be the action with the highest reward, i.e., the cell with
the highest Q-value. Since decisions are based on Q-values, their computation and
updating are [Link] Q-value update is done using the Temporal-Difference (TD)
method (as mentioned in section 14.8.2). This update blends the new and old values using a
parameter α, When α = 0, the value does not [Link] α = 1, the new value completely

CEC, Benjanapadavu, Bantwal Page 55

 Machine Learning

replaces the old one. Here, α is known as the learning rate. The discount factor (γ) is also
used in the update. Blending is done using temporal difference learning.

The updation procedure of Q-value is given as follows:

1. Perform any random action on state stst

2. Get a new state, st+1st+1

3. Get the reward r(st,at)r(st,at)

The temporal difference at time 't' is done using the update:

Here, r(st,at)r(st,at) is the reward obtained by performing action atat, and Q(st+1,a)Q(st+1
,a) is the estimate of the best action at state st+1st+1, i.e., s′s′, and Q(st,a)Q(st,a) is the Q-
value of the action aiai at state sisi. The best action performed at future states, discounted by
the discount factor γγ, is:

If TD is high, then it is a 'surprise factor' and denotes the highest reward. If TD is less, it
represents the 'frustration' factor and denotes a lesser reward. In other words, TD is a sort of
'reward'. It is initially high and slowly gets minimized as it reaches the end of training and the
final goal.

The update is carried out using the Temporal Difference learning (TD) Bellman equation.
The Bellman equation used to update value is given as follows:

The Q-Learning algorithm is given as follows:

CEC, Benjanapadavu, Bantwal Page 56

 Machine Learning

SARSA LEARNING

SARSA is based on episodic formulation and discount factor. Its name is derived from the
function Q(s,a,r,s′,a′)Q(s,a,r,s′,a′), ere:

Actions aa are chosen based on the ε-greedy approach.

SARSA is an on-policy method because each action atat is based on QQ, and QQ is updated
based on the actions taken. SARSA converges to the optimal policy, provided all state-action
pairs are visited infinitely often.

The major difference between SARSA and Q-learning is that SARSA does not necessarily
use the maximum reward to update the Q-value. Instead, it is based on estimates, making
SARSA an online method.

SARSA is based on the estimated optimal action:

CEC, Benjanapadavu, Bantwal Page 57

 Machine Learning

The ideal rule for updating Q:

This can also be written in terms of reward as:

Where:

 αα is the learning rate

 γγ is the discount factor

The SARSA algorithm is given below.

The parameters of the SARSA algorithm as same as the Q-learning algorithm, that is,
learning rate and discount factor.

Questions:

1. Why is Q-learning considered an off-policy method?

2. What are the four key elements required to compute the Q-value?

CEC, Benjanapadavu, Bantwal Page 58

 Machine Learning

3. at is t e role o t e disco nt actor γ\gammaγ in Q-learning and SARSA?

4. What is the main difference between SARSA and Q-learning in terms of
policy and update?

CEC, Benjanapadavu, Bantwal Page 59