13.

a) Given the following dataset of points with two features, apply the k-Means algorithm (k = 2) to
perform one full iteration (assignment and update steps). Show all intermediate calculations and the updated
cluster centroids. Data points: (2, 10), (2, 5),(8, 4), (5, 8), (7, 5), (6, 4) Initial centroids: C₁ = (2, 10), C₂ =
(5, 8).

ANSWER :

K-MEANS CLUSTERING (k = 2) — TWO ITERATIONS

Data Points:
(2,10), (2,5), (8,4), (5,8), (7,5), (6,4)

Initial Centroids:
C1 = (2,10)
C2 = (5,8)

ITERATION 1

Table 1: Distances and Assignments (Iteration 1)

Point datapoints C1 C2 new Cluster

P1 (2,10) 0.000 3.606 C1

P2 (2,5) 5.000 4.243 C2

P3 (8,4) 8.485 5.000 C2

P4 (5,8) 3.606 0.000 C2

P5 (7,5) 7.071 3.606 C2

P6 (6,4) 7.211 4.123 C2

Cluster Membership After Iteration 1

Cluster 1: (2,10)
Cluster 2: (2,5), (8,4), (5,8), (7,5), (6,4)

Table 2: Updated Centroids (Iteration 1)

Cluster Member Points

C1 (2,10)

C2 (2,5), (8,4), (5,8), (7,5), (6,4) (5.6, 5.2)

Updated Centroids:
C1 = (2,10)
C2 = (5.6, 5.2)

ITERATION 2
Table 3: Distances and Assignments (Iteration 2)

Centroids used:
C1 = (2,10)
C2 = (5.6, 5.2)

Point Data points C1 C2 new Cluster

P1 (2,10) 0.000 6.004 C1

P2 (2,5) 5.000 3.604 C2

P3 (8,4) 8.485 2.601 C2

P4 (5,8) 3.606 2.820 C2

P5 (7,5) 7.071 1.407 C2

P6 (6,4) 7.211 1.216 C2

Cluster Membership After Iteration 2

Cluster 1: (2,10)
Cluster 2: (2,5), (8,4), (5,8), (7,5), (6,4)

Clusters did NOT change

Table 4: Updated Centroids (Iteration 2)

Cluster Centroid

C1 (2,10)

C2 (5.6, 5.2)

FINAL RESULT AFTER TWO ITERATIONS

Clusters:
Cluster 1: (2,10)
Cluster 2: (2,5), (8,4), (5,8), (7,5), (6,4)

Centroids:
C1 = (2,10)
C2 = (5.6, 5.2)

K-Means converged after the second iteration.

(OR)

b) Using the Backpropagation Algorithm, compute the updated weights for a simple neural network with
one input neuron, one hidden neuron, and one output neuron. Assume:
• Input = 0.5
• Target output = 0.8
• Initial weights = 0.4 (input to hidden), 0.3 (hidden to output)
• Learning rate = 0.2
• Activation function = sigmoid
Show all steps of forward propagation, error calculation, and weight updates.

ANSWER :

Backpropagation — Updated Weights for a 1 → 1 → 1 Network

Given:
Input: x = 0.5
Target: t = 0.8
Initial weights:
• w₁ (input→hidden) = 0.4
• w₂ (hidden→output) = 0.3
Learning rate: η = 0.2
Activation: sigmoid σ(z) = 1 / (1 + e⁻ᶻ)

1. Forward Pass

Hidden layer

net_h = x · w₁
= 0.5 · 0.4
= 0.20

h = σ(0.20) ≈ 0.549834

Output layer

net_o = h · w₂
= 0.549834 · 0.3
≈ 0.164950

o = σ(0.164950) ≈ 0.541144

Network output: o ≈ 0.54114

Error (t − o) ≈ 0.25886

2. Compute Deltas

Output delta

o(1 − o) = 0.541144 · 0.458856 ≈ 0.248371

delta_o = (t − o) · o(1 − o)
= 0.258856 · 0.248371
≈ 0.064276

Hidden delta

h(1 − h) = 0.549834 · 0.450166 ≈ 0.247374

delta_h = delta_o · w₂ · h(1 − h)
= 0.064276 · 0.3 · 0.247374
≈ 0.004773
3. Weight Updates

Hidden → Output

w₂_new = w₂ + η · delta_o · h
= 0.3 + 0.2 · 0.064276 · 0.549834
= 0.3 + 0.007068
≈ 0.30707

Input → Hidden

w₁_new = w₁ + η · delta_h · x
= 0.4 + 0.2 · 0.004773 · 0.5
= 0.4 + 0.000477
≈ 0.40048

Final Updated Weights

w₁ (input→hidden): 0.40048
w₂ (hidden→output): 0.30707

14. a) Describe the concept of Instance-Based Learning and explain its key methods—Locally Weighted
Regression, Radial Basis Functions, and Case-Based Reasoning.

ANSWER :

Instance-Based Learning (IBL)

Definition:
Instance-Based Learning is a lazy learning method where the system stores all training examples and makes
predictions by comparing new inputs with stored instances using a similarity measure.

Working:

1. Store all training samples.

2. For a new query:
– Compute similarity/distance to stored examples.
– Select nearest instances.
– Predict based on these instances.

Similarity Measures:
Euclidean distance, Manhattan distance, cosine similarity.

Characteristics:

 No explicit model built.

 Computation occurs only during prediction.
 Time complexity: O(n) per query.

Examples:
k-Nearest Neighbors (k-NN), Locally Weighted Regression (LWR), Kernel Regression.
Advantages:

 Simple to implement
 Handles non-linear boundaries
 No training time

Limitations:

 Slow during prediction

 High memory usage
 Affected by irrelevant features

Radial Basis Function (RBF) Networks

Definition:
An RBF Network is a three-layer neural network (input, hidden, output) that uses radial basis functions
(usually Gaussian) in the hidden layer for classification or regression.

Architecture:

1. Input Layer – Passes input directly.

2. Hidden Layer – Each neuron has a center and spread (σ). Computes distance from input and applies
Gaussian RBF.
3. Output Layer – Weighted sum of hidden activations.

Working:

1. Compute distance from each center.

2. Apply Gaussian RBF.
3. Output layer combines these responses to form prediction.

Training Steps:

1. Choose centers (randomly or by k-means).

2. Select spreads (fixed or based on distance between centers).
3. Train output weights using linear regression or pseudo-inverse.

Characteristics:

 Fast training
 Smooth decision boundaries
 Good for non-linear problems

Locally Weighted Linear Regression (LWLR / LWR)

Definition:
Locally Weighted Linear Regression builds a separate linear model for each query point, giving higher
weights to nearby data points and lower weights to far points.

Working:

1. Compute weights for each point:

w(i) = exp( − (x(i) − x)² / (2τ²) )
2. Form weighted cost function:
J(θ) = Σ w(i)(θᵀx(i) − y(i))²
 3. Solve using weighted least squares:
θ = (XᵀWX)⁻¹ XᵀWy
4. Predict:
ŷ = θᵀx

Characteristics:

 Non-parametric
 Fits different local models for each query
 Good for non-linear data

Case-Based Reasoning (CBR)

Definition:
Case-Based Reasoning solves new problems by retrieving similar past cases and adapting their solutions.
Introduced by Roger Schank.

CBR Cycle:

1. Retrieve the most similar past case.

2. Reuse/Adapt its solution for the new problem.
3. Revise the solution if necessary.
4. Retain the new case by storing it in the case base.

Basis of CBR:

 Regularity – Similar actions give similar outcomes.

 Typicality – Many situations recur.
 Consistency – Small differences need small solution changes.
 Adaptability – Solutions can be modified when needed.

Types of Knowledge Used:

Type Description
Vocabulary Knowledge Features describing cases
Case Features Properties used for retrieval
Similarity Estimation Knowledge Rules for choosing similar cases
Modification Knowledge How to adapt old solutions
Cases Stored problem–solution pairs

Advantages:

 Learns from experience

 Improves over time
 Easy to update

Limitations:

 Case base can grow large

 Needs reliable similarity measures
 Poor adaptation may give poor solutions
 (OR)

b)Explain the working of Reinforcement Learning with the help of a Diagram of a learning agent.

ANSWER :

Reinforcement Learning

Reinforcement Learning (RL) is a branch of machine learning that focuses on how agents can learn to make
decisions through trial and error to maximize cumulative rewards. RL allows machines to learn by
interacting with an environment and receiving feedback based on their actions. This feedback comes in the
form of rewards or penalties.
Reinforcement Learning revolves around the idea that an agent (the learner or decision-maker) interacts with
an environment to achieve a goal. The agent performs actions and receives feedback to optimize its
decision-making over time.

Agent: The decision-maker that performs actions.

Environment: The world or system in which the agent operates.
State: The situation or condition the agent is currently in.
Action: The possible moves or decisions the agent can make.
Reward: The feedback or result from the environment based on the agent’s action.

Core Components

1. Policy

Defines the agent’s behavior i.e maps states for [Link] be simple rules or complex computations.
Example: An autonomous car maps pedestrian detection to make necessary stops.

2. Reward Signal

Represents the goal of the RL problem. Guides the agent by providing feedback (positive/negative rewards).
Example: For self-driving cars rewards can be fewer collisions, shorter travel time, lane discipline.

3. Value Function

Evaluates long-term benefits, not just immediate rewards. Measures desirability of a state considering future
outcomes.
Example: A vehicle may avoid reckless maneuvers (short-term gain) to maximize overall safety and
efficiency.

4. Model
Simulates the environment to predict outcomes of actions. Enables planning and foresight.
Example: Predicting other vehicles’ movements to plan safer routes.

Working of Reinforcement Learning

The agent interacts iteratively with its environment in a feedback loop:

 The agent observes the current state of the environment.

 It chooses and performs an action based on its policy.
 The environment responds by transitioning to a new state and providing a reward (or penalty).
 The agent updates its knowledge (policy, value function) based on the reward received and the new
state.

This cycle repeats with the agent balancing exploration (trying new actions) and exploitation (using known
good actions) to maximize the cumulative reward over time.

This process is mathematically framed as a Markov Decision Process (MDP) where future states depend
only on the current state and action, not on the prior sequence of events.
Reinforcement Learning methods also commonly use:

 Q-Learning: An off-policy RL algorithm that learns the optimal action-value function.

 SARSA: An on-policy RL algorithm that updates values based on the action actually taken.
 Markov Decision Processes (MDP): The mathematical framework underlying RL, defining states,
actions, rewards, and transitions.

15. a) Discuss with examples the concepts of genetic programming, models of evolution and learning, and
parallelizing genetic algorithms.

ANSWER :

[Link] Programming (GP)

Genetic Programming is an extension of Genetic Algorithms where the solution itself is a program (not just
a fixed-length chromosome).

Definition:

Genetic Programming automatically creates computer programs to solve a problem by evolving them over
generations.

Representation (Chromosomes in GP):

 Programs are represented as tree structures

o Internal nodes → Functions (e.g., +, -, *, /)
o Leaf nodes → Inputs/operands (e.g., variables x, constants)

Example:

To evolve a mathematical expression for predicting output y:

A GP tree might look like:

+
 /\

x 3

This represents x + 3.

Over generations, GP creates better trees/programs using:

 Crossover: Swapping subtrees between parent programs

 Mutation: Randomly modifying a node or branch
 Fitness Function: Measures how accurately the program solves the task (e.g., prediction error)

Applications:

 Symbolic regression
 Automated program generation
 Game strategies
 Robot control

2. Models of Evolution and Learning

Evolutionary algorithms use different learning models based on how solutions change and improve.
The main models include:

(i) Evolutionary Programming (EP)

 Focuses on evolving the behaviour of a program, not the structure.

 Mutation is the primary operator.
Example:
Evolving a finite-state machine for pattern recognition.

(ii) Genetic Algorithms (GA) Model

GA uses components such as:

 Population: Collection of candidate solutions

 Chromosomes: Binary/real strings representing solutions
 Fitness Function: Evaluates quality
 Selection: Roulette Wheel, Rank, Tournament
 Crossover: Single-point, Two-point, Uniform
 Mutation: Flipping bits or modifying genes

Example:
Solving the Travelling Salesman Problem (TSP) by encoding city sequences as chromosomes.

3. Parallelizing Genetic Algorithms

Parallel Genetic Algorithms (PGA) speed up computation and improve search quality by distributing work
across multiple processors.

Why Parallelize?

 GA involves heavy computation

 Fitness evaluation for large populations is slow
 Parallel models offer:
 o Faster execution
o Better diversity
o Less chance of getting stuck in local optimum

Parallel GA Models:

(i) Coarse-Grained GA

 Population divided into multiple sub-populations (islands)

 Each island runs its own GA
 Occasionally individuals migrate between islands
Benefits:
 Very high diversity, avoids premature convergence
Example:
Four islands each solve TSP locally → best individuals migrate → global improvement.

(ii) Fine-Grained Model (Cellular GA)

 Each individual interacts with only nearby neighbours

 Suitable for GPU-like architectures
Example:
Chromosomes placed in a 2D grid; crossover happens only locally → smoother evolution.

4. Example of Genetic Algorithm Workflow

1. Initialize Population – random solutions

2. Evaluate Fitness
3. Select Best Parents – using roulette wheel/tournament
4. Crossover – combine parents
5. Mutation – flip bits to add diversity
6. Generate New Population
7. Repeat until best solution or fixed generations

Genetic Algorithm – Example

Problem:

Maximize the number of 1s in a 6-bit binary string (goal = 111111).

Step 1: Encoding

Each chromosome = 6-bit string.

Initial population:
A = 010110
B = 111000
C = 001111
D = 100101

Step 2: Fitness Function

Fitness = number of 1s.

 010110 → 3
 111000 → 3
  001111 → 4 (best)
 100101 → 3

Step 3: Selection

Using roulette wheel → choose fitter parents:

P1 = 001111
P2 = 010110

Step 4: Crossover

Single-point at position 3:

Child1 = 001110
Child2 = 010111

Step 5: Mutation

Flip bit with small probability:

Child1 before = 001110

After mutation = 001010
Child2 unchanged = 010111

Step 6: New Population

New generation contains:

001010
010111
001111 (kept)
100101

Step 7: Repeat Until Convergence

After several generations, best chromosome becomes:

111111 (fitness = 6)

(OR)

(b) (i) How are learning sets of rules performed in Machine Learning?

ANSWER :

Learning a set of rules in Machine Learning refers to the process of discovering IF–THEN rules from data
that can classify, predict, or describe patterns. Rule-based learning algorithms aim to represent knowledge in
an interpretable form that closely resembles human reasoning.

1. Representing Knowledge as Rules

A rule generally looks like:

IF (conditions) THEN (class label)

Example:
IF Outlook = Sunny AND Humidity = High THEN Play = No

Each rule captures a pattern in the dataset.

2. Learning One Rule at a Time (Sequential Covering)

The system repeatedly performs these steps:

1. Start with all positive examples

2. Grow a rule by adding conditions that best discriminate between positive and negative examples
3. Evaluate the rule using metrics like accuracy, coverage, and information gain
4. Prune the rule to avoid overfitting
5. Remove covered examples from the dataset
6. Repeat until all positives are covered

This is how popular rule learners like RIPPER, CN2, FOIL learn rules.

3. Search Through Hypothesis Space

Rule learners search a large space of possible rules.

They use:

 Greedy search: Add the best condition at each step

 Heuristics: Information gain, entropy, coverage
 Stopping criteria: Rule accuracy stops improving

4. General-to-Specific or Specific-to-General

Rules can be learned by:

 General → Specific: Start with a general rule, then add conditions

 Specific → General: Start with a very specific rule, then remove unnecessary conditions

5. Pruning to Avoid Overfitting

After learning a rule, the algorithm removes overly specific parts using:

 Reduced-error pruning
 Statistical pruning
 MDL principle

This ensures that the rule generalizes well on unseen data.

6. Final Rule Set

The final output is a set of human-interpretable rules that can classify new examples.

(b) (ii) What is meant by induction as inverted deduction in Machine Learning, and how is it used to derive
general rules from specific examples?

ANSWER :
Induction as inverted deduction means that Machine Learning works in the opposite direction of classical
logical deduction.

Deduction (Normal Logic Flow)

 Starts with general rules

 Applies them to get specific conclusions

Example:
Rule: All birds fly
Fact: Sparrow is a bird
Conclusion: Sparrow flies

Induction (Opposite of Deduction → Inverted Deduction)

 Starts with specific examples

 Uses them to infer a general rule

Because induction reconstructs the rule that could explain the examples, it is called “inverted deduction.”

Why It Is Important in ML

Machine learning algorithms do not know the rules beforehand.

They must discover rules by observing patterns in the training data.

How Induction Works to Derive General Rules

ML performs inverted deduction in the following steps:

1. Collect Specific Examples

Training examples such as:

 (Email contains “discount”) → Spam

 (Email contains “offer”) → Spam

These represent observations.

2. Search for Patterns

Algorithms identify common features that appear frequently in similar examples.

In GeeksforGeeks terms, this involves

 Feature selection
 Attribute tests
 Measuring consistency with positive and negative examples

3. Form a General Hypothesis (Rule)

From the above examples, ML derives a rule like:

IF email contains promotional keywords THEN it is spam.

This general rule explains all observed examples.

4. Use Background Knowledge (Optional)

In some systems (e.g., FOIL, ILP), the learner uses:

 domain knowledge
 logical predicates
 constraints

It constructs rules that, together with background knowledge, logically entail the examples.

This inversion of entailment is why it’s called inverted deduction.

5. Test and Refine the Rule

The rule is tested on:

 unseen examples
 validation data

The rule is refined if it fails, making it more accurate.

6. Produce a General Theory

Finally, the system outputs a generalized rule that predicts new cases.

PART – C

16. a) Consider a simple Markov Decision Process with three states S₁, S₂, and S₃ and one action available
in each state. The transition probabilities and rewards are given below:

From State To State Transition Probability Reward

S₁ S₂ 0.8 +5
S₁ S₃ 0.2 +2
S₂ S₁ 0.6 +3
S₂ S₃ 0.4 +4
S₃ S₁ 1.0 +1

Let the discount factor (γ) = 0.9.

Assume initial value estimates:

V(S₁) = 0, V(S₂) = 0, V(S₃) = 0

Perform one iteration of Value Iteration to compute the updated values V(S₁), V(S₂), and V(S₃). Show all
steps and intermediate calculations clearly.

ANSWER :

Value Iteration – Iteration 1

We are given a Markov Decision Process (MDP) with three states: S₁, S₂, S₃, and one action per state.
Initial Values:
V₀(S₁) = 0
V₀(S₂) = 0
V₀(S₃) = 0

Discount Factor:
γ = 0.9

Since there is only one action per state, the Value Iteration update becomes:

V1(s)=∑s′P(s′∣s)[R(s→s′)+γV0(s′)]

Because all initial values are zero:

γV0(s′)=0

Thus, the first iteration reduces to computing expected immediate rewards.

Transition Table

From State To State Probability Reward

S₁ S₂ 0.8 +5
S₁ S₃ 0.2 +2
S₂ S₁ 0.6 +3
S₂ S₃ 0.4 +4
S₃ S₁ 1.0 +1

Step 1: Compute V₁(S₁)

V1(S1)=0.8(5)+0.2(2)

V1(S1)=4.0+0.4=4.4

Step 2: Compute V₁(S₂)

V1(S2)=0.6(3)+0.4(4)

V1(S2)=1.8+1.6=3.4V

Step 3: Compute V₁(S₃)

V1(S3)=1.0(1)

V1(S3)=1.0V

Final Values After One Iteration

 V₁(S₁) = 4.4
 V₁(S₂) = 3.4
 V₁(S₃) = 1.0

(OR)
b)i. How does the Random Forest algorithm work in machine learning?
ii. Explain its working principle, advantages over a single decision tree, and typical applications with
suitable examples.

ANSWER :

A Random Forest is a machine learning algorithm that builds many decision trees and combines their
outputs to make a stronger prediction.
Its working involves four main steps:

1. Create Many Decision Trees:

The algorithm constructs multiple decision trees, and each tree is trained on a random part of the
data, so every tree becomes slightly different.
2. Pick Random Features:
When each tree splits the data, it chooses a random subset of features (columns) instead of looking
at all features.
This randomness keeps the trees diverse and prevents them from becoming similar.
3. Each Tree Makes a Prediction:
Every tree gives its own prediction based on the part of the data it learned from.
4. Combine the Predictions:
o Classification: The final answer is the class that most trees vote for (majority voting).
o Regression: The final answer is the average of predictions made by all the trees.

Because many trees work together, Random Forest is known as an ensemble learning technique.
Advantages Over a Single Decision Tree

1. Higher Accuracy:
Since multiple trees contribute to the final decision, the combined prediction is more accurate than
relying on a single tree.
2. Reduced Errors:
Voting (for classification) or averaging (for regression) reduces individual tree mistakes and gives
more stable results.
3. Faster Than a Single Large Tree:
Each tree in a Random Forest is built using only a random subset of features and data, so trees are
smaller and faster to train than one deep, complex tree.
4. Readable and Easy to Understand:
Although the forest has many trees, the concept is simple—many small decision trees working
together—making it easier for beginners to understand.

Typical Applications of Random Forest

 Spam detection
 Customer clustering / customer behavior prediction
 Weather forecasting
 Price prediction
 Disease prediction
 Credit risk scoring