Source: Uploaded Machine Learning Textbook

1)Apply PCA and find the transformed data for the data points (\begin{pmatrix}2\6\end{pmatrix})
and (\begin{pmatrix}1\7\end{pmatrix}). Again, apply the inverse and prove that PCA works.

Solution
One can combine two vectors into a matrix as follows:
Mean vector
The mean vector can be computed as Eq. (2.53) as follows:
[
\mu=
\begin{pmatrix}
\dfrac{2+1}{2}\
\dfrac{6+7}{2}
\end{pmatrix}
\begin{pmatrix}
1.5\
6.5
\end{pmatrix}
]

As part of PCA, the mean must be subtracted from the data to get the adjusted data:
[
x_1=
\begin{pmatrix}
2-1.5\
6-6.5
\end{pmatrix}
\begin{pmatrix}
0.5\
-0.5
\end{pmatrix}
]
[
x_2=
\begin{pmatrix}
1-1.5\
7-6.5
\end{pmatrix}
\begin{pmatrix}
-0.5\
0.5
\end{pmatrix}
]

One can find the covariance for these data vectors. The covariance can be obtained using Eq. (2.54):
[
m_1=
\begin{pmatrix}
0.5\
-0.5
\end{pmatrix}
(0.5;;-0.5)
\begin{pmatrix}
0.25 & -0.25\
-0.25 & 0.25
\end{pmatrix}
]
[
m_2=
\begin{pmatrix}
-0.5\
0.5
\end{pmatrix}
(-0.5;;0.5)
\begin{pmatrix}
0.25 & -0.25\
-0.25 & 0.25
\end{pmatrix}
]
The final covariance matrix is obtained by adding these two matrices as:
[
C=
\begin{pmatrix}
0.5 & -0.5\
-0.5 & 0.5
\end{pmatrix}
]

The eigen values and eigen vectors of matrix (C) can be obtained as:
[
\lambda_1=1,\qquad \lambda_2=0
]
The eigen vectors are:
[
\begin{pmatrix}
-1\
1
\end{pmatrix}
\quad
\begin{pmatrix}
1\
1
\end{pmatrix}
]
The matrix (A) can be obtained by packing the eigen vector of these eigen values (after sorting it) of
matrix (C).
For this problem,
[
A=
\begin{pmatrix}
-1 & 1\
1&1
\end{pmatrix}
]
The transpose of (A),
[
A^T=
\begin{pmatrix}
-1 & 1\
1&1
\end{pmatrix}
]
is also the same matrix as it is an orthogonal matrix.
The matrix can be normalized by dividing each element of the vector, by the norm of the vector to
get:
[
A=
\begin{pmatrix}
-\frac{1}{\sqrt2} & \frac{1}{\sqrt2}\
\frac{1}{\sqrt2} & \frac{1}{\sqrt2}
\end{pmatrix}
]

One can check that the PCA matrix (A) is orthogonal.

A matrix is orthogonal if
[
A^{-1}=A
]
and
[
AA^{-1}=I
]
[
AA^T=
\begin{pmatrix}
-\frac{1}{\sqrt2} & \frac{1}{\sqrt2}\
\frac{1}{\sqrt2} & \frac{1}{\sqrt2}
\end{pmatrix}
\begin{pmatrix}
-\frac{1}{\sqrt2} & \frac{1}{\sqrt2}\
\frac{1}{\sqrt2} & \frac{1}{\sqrt2}
\end{pmatrix}
\begin{pmatrix}
1 & 0\
0&1
\end{pmatrix}
]

The transformed matrix (y) using Eq. (2.55) is given as:

[
y=A\times(x-m)
]
Recall that ((x-m)) is the adjusted matrix.
[
y=
\begin{pmatrix}
-\frac1{\sqrt2} & \frac1{\sqrt2}\
\frac1{\sqrt2} & \frac1{\sqrt2}
\end{pmatrix}
\begin{pmatrix}
0.5 & -0.5\
-0.5 & 0.5
\end{pmatrix}
]
[
\begin{pmatrix}
-\frac1{\sqrt2} & \frac1{\sqrt2}\
\frac1{\sqrt2} & \frac1{\sqrt2}
\end{pmatrix}
\begin{pmatrix}
\frac12 & -\frac12\
-\frac12 & \frac12
\end{pmatrix}
]
(for convenience (0.5=\frac12))
[
\begin{pmatrix}
-\frac1{\sqrt2} & \frac1{\sqrt2}\
0&0
\end{pmatrix}
]

One can check the original matrix can be retrieved from this matrix as:
[
x=(A)^T\times y+m
]
[
x=
\begin{pmatrix}
-\frac1{\sqrt2} & \frac1{\sqrt2}\
\frac1{\sqrt2} & \frac1{\sqrt2}
\end{pmatrix}
\begin{pmatrix}
-\frac1{\sqrt2} & \frac1{\sqrt2}\
0&0
\end{pmatrix}
+
\begin{pmatrix}
1.5\
6.5
\end{pmatrix}
]
[
\begin{pmatrix}
\frac12 & -\frac12\
-\frac12 & \frac12
\end{pmatrix}
+
\begin{pmatrix}
1.5\
6.5
\end{pmatrix}
]
[
\begin{pmatrix}
2 & 1\
6&7
\end{pmatrix}
]
Therefore,
One can infer the original is obtained without any loss of information.

Source: Uploaded Machine Learning Textbook

2)Explain Continuous and Discrete Probability Distribution
Probability Distributions
• A probability distribution of a variable, say X, summarizes the probability associated with X's
events.
• Distribution is a parameterized mathematical function.
• In other words, distribution is a function that describes the relationship between the
observations in a sample space.
• Consider a set of data.
• The data is said to follow a distribution if it obeys a mathematical function that
characterizes that distribution.
• The function can be used to calculate the probability of individual observations.
• Probability distributions are of two types:
1. Discrete probability distribution
2. Continuous probability distribution

Continuous Probability Distribution

• The relationships between the events for a continuous random variable and their
probabilities is called a continuous probability distribution.
• It is summarized as Probability Density Function (PDF).
• PDF calculates the probability of observing an instance.
 • The plot of PDF shows the shape of the distribution.

• Cumulative Distributive Function (CDF) computes the probability of an observation ≤ value.

• Both PDF and CDF are continuous values.
• The discrete equivalent of PDF in discrete distribution is called Probability Mass Function
(PMF).
• The probability of an event cannot be detected directly.
• It should be computed as the area under the curve for a small interval around the specific
outcome.
• This is defined as CDF.
Continuous Probability Distributions
The following fall under this category:
1. Normal Distribution
2. Rectangular Distribution
3. Exponential Distribution

1. Normal Distribution
• Normal distribution is a continuous probability distribution.
• This is also known as gaussian distribution or bell-shaped curve distribution.
• It is the most common distribution function.
• The shape of this distribution is a typical bell-shaped curve.
• In normal distribution, data tends to be around a central value with no bias on left or right.
• The heights of the students, blood pressure of a population, and marks scored in a class can
be approximated using normal distribution.

• Here, μ is mean and σ is the standard deviation.

• In normal distribution, mean, median and mode are same.

• The distribution extends from −∞ to +∞.

• Standard deviation is how the data is spread out.

2. Rectangular Distribution
• This is also known as uniform distribution.
• It has equal probabilities for all values in the range a, b.
3. Exponential Distribution
• This is a continuous uniform distribution.
• This probability distribution is used to describe the time between events in a Poisson
process.
• Exponential distribution is another special case of Gamma distribution with a fixed
parameter of 1.
• This distribution is helpful in modelling of time until an event occurs.

• Here, x is a random variable and λ is called rate parameter.

• The mean and standard deviation of exponential distribution is given as β, where

[
\beta=\frac{1}{\lambda}
]

Discrete Probability Distribution

Discrete Distributions
The following fall under this category:
1. Binomial Distribution
2. Poisson Distribution
3. Bernoulli Distribution

1. Binomial Distribution
• Binomial distribution is another distribution that is often encountered in machine learning.
• It has only two outcomes:
o Success
o Failure
• This is also called Bernoulli trial.
• The objective of this distribution is to find probability of getting success k out of n trials.
• Here,
o p is the probability of each choice
o k is the number of choices
o n is the total number of choices
• The mean of binomial distribution is:
[
\mu=n\times p
]
• The variance is:
[
\sigma^2=np(1-p)
]
• Hence, the standard deviation is:
[
\sigma=\sqrt{np(1-p)}
]

2. Poisson Distribution
• It is another important distribution that is quite useful.
• Given an interval of time, this distribution is used to model the probability of a given
number of events k.

• The mean rule λ is inclusive of previous events.

• Some of the examples of Poisson distribution are:
o Number of emails received
o Number of customers visiting a shop
o Number of phone calls received by the office
• Here,
o x is the number of times the event occurs

o λ is the mean number of times an event occurs

• The mean is the population mean at number of emails received and the standard deviation
is:
[
\sqrt{\lambda}
]

3. Bernoulli Distribution
• This distribution models an experiment whose outcome is binary.
• The outcome is positive with p and negative with 1 − p.
• The mean is p and variance is:
[
p(1-p)=q
]

3) Design a Learning System for Chess Game

A system that is built around a learning algorithm is called a learning system. The design of systems
focuses on these steps:
1. Choosing a training experience
2. Choosing a target function
3. Representation of a target function
4. Function approximation

1. Choosing a Training Experience

Training Experience
• Let us consider designing of a chess game.
• In direct experience, individual board states and correct moves of the chess game are given
directly.
• In indirect system, the move sequences and results are only given.
• The training experience also depends on the presence of a supervisor who can label all valid
moves for a board state.
• In the absence of a supervisor, the game agent plays against itself and learns the good
moves, if the training samples cover all scenarios, or in other words, distributed enough for
performance computation.
• If the training samples and testing samples have the same distribution, the results would be
good.

2. Choosing a Target Function

Determine the Target Function
• The next step is the determination of a target function.
• In this step, the type of knowledge that needs to be learnt is determined.
• In direct experience, a board move is selected and is determined whether it is a good move
or not against all other moves.
• If it is the best move, then it is chosen as:
B→M
where, B and M are legal moves.
• In indirect experience, all legal moves are accepted and a score is generated for each.
• The move with largest score is then chosen and executed.

3. Representation of a Target Function

Determine the Target Function Representation
• The representation of knowledge may be a table, collection of rules or a neural network.
• The linear combination of these factors can be coined as:
[
V = w_0 + w_1x_1 + w_2x_2 + w_3x_3
]
• (x_1, x_2) and (x_3) represent different board features.
• (w_0, w_1, w_2) and (w_3) represent weights.

4. Function Approximation
Choosing an Approximation Algorithm for the Target Function
• The focus is to choose weights and fit the given training samples effectively.
• The aim is to reduce the error given as:
[
E=\sum_{Training\ Samples}[V_{train}(b)-\hat{V}(b)]^2
]
• Here, b is the sample and (\hat{V}(b)) is the predicted hypothesis.
The approximation is carried out as:
• Computing the error as the difference between trained and expected hypothesis.
• Let error be error(b).
• Then, for every board feature (x_i), the weights are updated as:
[
w_i = w_i + \mu \times error(b) \times x_i
]
• Here, μ is the constant that moderates the size of the weight update.

Thus, the learning system has the following components:

• A Performance system to allow the game to play against itself.
 • A Critic system to generate the samples.
• A Generalizer system to generate a hypothesis based on samples.
• An Experimenter system to generate a new system based on the currently learnt function.
This is sent as input to the performance system.

4) Candidate Elimination Algorithm

Input:
Set of instances in the Training dataset
Output:
Hypothesis G and S
1. Initialize G, to the maximally general hypotheses.
2. Initialize S, to the maximally specific hypotheses.
• Generalize the initial hypothesis for the first positive instance.
3. For each subsequent new training instance,
If the instance is positive,
• Generalize S to include the positive instance.
o Check the attribute value of the positive instance and S.
▪ If the attribute value of positive instance and S are different, fill that field
value with ‘?’.
▪ If the attribute value of positive instance and S are same, then do no change.
• Prune G to exclude all inconsistent hypotheses in G with the positive instance.
If the instance is negative,
• Specialize G to exclude the negative instance.
o Add to G all minimal specializations to exclude the negative example and be
consistent with S.
▪ If the attribute value of S and the negative instance are different, then
update G and fill that attribute value with ‘?’.
▪ If the attribute value of S and the negative instance are same, no need to
update G and fill that attribute value with ‘?’.
• Remove from S all inconsistent hypotheses with the negative instance.

Applying Candidate Elimination Algorithm for the Given Dataset

Training Dataset

Example Sky Temp Humidity Wind Water Forecast Enjoy Sports

1 Sunny Warm Normal Strong Warm Same Yes

2 Sunny Warm High Strong Warm Same Yes

3 Rainy Cold High Strong Warm Change No

4 Sunny Warm High Strong Cool Change Yes

Step 1: Initialize G boundary to the maximally general hypotheses

G₀ =

Step 2: Initialize S boundary to the maximally specific hypothesis

S₀ = <ϕ, ϕ, ϕ, ϕ, ϕ, ϕ>

Iteration 1
Example 1 (Positive)

I₁ = <Sunny, Warm, Normal, Strong, Warm, Same>

Generalize S to include I₁

S₁ = <Sunny, Warm, Normal, Strong, Warm, Same>

G₁ =

Example 2 (Positive)

I₂ = <Sunny, Warm, High, Strong, Warm, Same>

Compare I₂ with S₁
Only Humidity differs
Replace mismatching attribute by '?'

S₂ = <Sunny, Warm, ?, Strong, Warm, Same>

Prune G₁
No inconsistency

G₂ =
Iteration 2
Example 3 (Negative)

I₃ = <Rainy, Cold, High, Strong, Warm, Change>

Specialize G₂ to exclude I₃ and remain consistent with S₂

Generated hypotheses:

G₃ = {
• <Sunny, ?, ?, ?, ?, ?>
•

• <?, ?, ?, ?, ?, Same>
}
S remains unchanged

S₃ = <Sunny, Warm, ?, Strong, Warm, Same>

Iteration 3
Example 4 (Positive)

I₄ = <Sunny, Warm, High, Strong, Cool, Change>

Compare I₄ with S₃

Water differs → ?

Forecast differs → ?

S₄ = <Sunny, Warm, ?, Strong, ?, ?>

Prune G₃
Check consistency:

<Sunny, ?, ?, ?, ?, ?> → Consistent

→ Consistent

<?, ?, ?, ?, ?, Same> → Inconsistent

Remove inconsistent hypothesis

Final General Boundary

G₄ = {
 • <Sunny, ?, ?, ?, ?, ?>
•

Final Specific Boundary

S₄ = <Sunny, Warm, ?, Strong, ?, ?>

Version Space (Consistent Hypotheses)

1. <Sunny, ?, ?, ?, ?, ?>
2.
3. <Sunny, Warm, ?, ?, ?, ?>
These are the hypotheses contained in the version space.

Regular Paper

1)Principal Component Analysis (PCA)

• The idea of the principal component analysis (PCA) or KL transform is to transform a given
set of measurements to a new set of features so that the features exhibit high information
packing properties.
• This leads to a reduced and compact set of features.
• Basically, this elimination is made possible because of the information redundancies.
• This compact representation is of a reduced dimension.
PCA Algorithm
1. The target dataset (x) is obtained.
2. The mean (m) is subtracted from the dataset. Let the mean be (m). Thus, the adjusted
dataset is:
[
X-m
]
• The objective of this process is to transform the dataset with zero mean.
3. The covariance of dataset (x) is obtained. Let it be (C).
4. Eigen values and eigen vectors of the covariance matrix are calculated.
 5. The eigen vector of the highest eigen value is the principal component of the dataset.
o The eigen values are arranged in a descending order.
o The feature vector is formed with these eigen vectors in its columns.
[
\text{Feature vector}
[eigen\ vector_1,\ eigen\ vector_2,\ ...,\ eigen\ vector_n]
]
6. Obtain the transpose of feature vector. Let it be (A).
7. PCA transform is:
[
y = A \times (x-m)
]
where:
• (x) is the input dataset,
• (m) is the mean,
• (A) is the transpose of the feature vector.
Original Data Retrieval
The original data can be retrieved using the formula:
[
Original\ data\ (f)=((A)^{-1}\times y)+m
]
[
=((A)^T \times y)+m
]
Result
• The new data is a dimensionally reduced matrix that represents the original data.
• Therefore, PCA is effective in removing the attributes that do not contribute.
• If the original data is required, it can be obtained with no loss of information.
• Scree plot is a visualization technique to visualize the principal components or variables that
play a more important role as compared to other attributes.
• Scree plot is a visualization technique to visualize the principal components visually.
• From Figure 2.15, one can infer the relevance of the attributes.
• The scree plot indicates that the first attribute is more important than all other attributes.
2) Yes.
For the university question:
"Apply Candidate Elimination Algorithm on the dataset given in Table to obtain the complete
Version Space."
The pages you uploaded already contain the complete worked-out answer from the textbook.
A complete answer should contain:
1. Initialization
• (G = )
• (S = <\phi, \phi, \phi, \phi, \phi, \phi>)

2. Iteration 1 (I₁ Positive)

• (S_1 = <\geq 9,\ Yes,\ Excellent,\ Good,\ Fast,\ Yes>)
• (G_1 = )

3. Iteration 2 (I₂ Positive)

• (S_2 = <\geq 9,\ Yes,\ ?,\ Good,\ Fast,\ Yes>)
• (G_2 = )

4. Iteration 3 (I₃ Negative)

• Generate (G_3)
[
G_3=
{
<\geq9, ?, ?, ?, ?, ?>,
Prune inconsistent hypothesis from (G_3)
[
G_4=
{
<\geq9, ?, ?, ?, ?, ?>,
}
]
6. Final Version Space
[
<\geq9,\ Yes,\ ?,\ ?,\ ?,\ ?>
]
[
<\geq9,\ ?,\ ?,\ Good,\ ?,\ ?>
]
[
]
7. Conclusion
• Using the two boundary sets, (S_4) and (G_4), the version space is converged to contain the
set of consistent hypotheses.
• Thus, the algorithm finds the version space to contain only those hypotheses that are most
general and most specific.
8. Figure 3.2 (Version Space Diagram)
Draw the diagram shown in Figure 3.2.

For a 10-mark VTU answer, writing the iterations + final version space + diagram is sufficient and
complete. The screenshots you uploaded essentially contain the full answer expected by the
examiner.

3) For
[
A=\begin{bmatrix}
1 & 2\
4&9
\end{bmatrix}
]
The Singular Value Decomposition is
[
A=U\Sigma V^T
]

Step 1: Compute (A^TA)

[
A^TA=
\begin{bmatrix}
1&4\
2&9
\end{bmatrix}
\begin{bmatrix}
1&2\
4&9
\end{bmatrix}
\begin{bmatrix}
17&38\
38&85
\end{bmatrix}
]

Step 2: Find Eigenvalues of (A^TA)

[
|A^TA-\lambda I|=0
]
[
\begin{vmatrix}
17-\lambda & 38\
38 & 85-\lambda
\end{vmatrix}=0
]
[
(17-\lambda)(85-\lambda)-38^2=0
]
[
\lambda^2-102\lambda+1=0
]
[
\lambda_1=51+10\sqrt{26}
]
[
\lambda_2=51-10\sqrt{26}
]

Step 3: Singular Values

[
\sigma_1=\sqrt{\lambda_1}
=\sqrt{51+10\sqrt{26}}
\approx 10.0990
]
[
\sigma_2=\sqrt{\lambda_2}
=\sqrt{51-10\sqrt{26}}
\approx 0.0990
]
Hence
[
\Sigma=
\begin{bmatrix}
10.0990 & 0\
0 & 0.0990
\end{bmatrix}
]

Step 4: Find (V)

Normalized eigenvectors of (A^TA):
For (\lambda_1),
[
v_1 \approx
\begin{bmatrix}
0.407\
0.913
\end{bmatrix}
]
For (\lambda_2),
[
v_2 \approx
\begin{bmatrix}
-0.913\
0.407
\end{bmatrix}
]
Thus
[
V=
\begin{bmatrix}
0.407 & -0.913\
0.913 & ;;0.407
\end{bmatrix}
]

Step 5: Find (U)

Using
[
u_i=\frac{Av_i}{\sigma_i}
]
[
u_1\approx
\begin{bmatrix}
0.221\
0.975
\end{bmatrix}
]
[
u_2\approx
\begin{bmatrix}
0.975\
-0.221
\end{bmatrix}
]
Hence
[
U=
\begin{bmatrix}
0.221 & 0.975\
0.975 & -0.221
\end{bmatrix}
]

Final SVD
[
A=
\begin{bmatrix}
0.221 & 0.975\
0.975 & -0.221
\end{bmatrix}
\begin{bmatrix}
10.099 & 0\
0 & 0.099
\end{bmatrix}
\begin{bmatrix}
0.407 & 0.913\
-0.913 & 0.407
\end{bmatrix}
]
Therefore,
[
\boxed{A=U\Sigma V^T}
]
with
[
U=
\begin{bmatrix}
0.221 & 0.975\
0.975 & -0.221
\end{bmatrix},
\quad
\Sigma=
\begin{bmatrix}
10.099 & 0\
0 & 0.099
\end{bmatrix},
\quad
V^T=
\begin{bmatrix}
0.407 & 0.913\
-0.913 & 0.407
\end{bmatrix}
]

4) Find-S Algorithm
Input:
Positive instances in the Training dataset
Output:
Hypothesis ‘h’
Step 1:
Initialize ‘h’ to the most specific hypothesis.
[
h=<\phi,\phi,\phi,\phi,\phi,\ldots>
]
Step 2:
Generalize the initial hypothesis for the first positive instance [Since ‘h’ is more specific].
Step 3:
For each subsequent instances:
If it is a positive instance,
• Check for each attribute value in the instance with the hypothesis ‘h’.
 o If the attribute value is the same as the hypothesis value, then do nothing.
o Else if the attribute value is different than the hypothesis value, change it to ‘?’ in ‘h’.
Else if it is a negative instance,
• Ignore it.

Applying Find-S Algorithm

Training Dataset

Example Sky Temp Humidity Wind Water Forecast Enjoy Sports

1 Sunny Warm Normal Strong Warm Same Yes

2 Sunny Warm High Strong Warm Same Yes

3 Rainy Cold High Strong Warm Change No

4 Sunny Warm High Strong Cool Change Yes

Step 1: Initialize h
[
h_0=<\phi,\phi,\phi,\phi,\phi,\phi>
]

Step 2: First Positive Instance

I₁
[
<Sunny,\ Warm,\ Normal,\ Strong,\ Warm,\ Same>
]
Generalize h to include the first positive instance.
[
h_1=<Sunny,\ Warm,\ Normal,\ Strong,\ Warm,\ Same>
]

Step 3: Scan I₂

I₂ (Positive)
[
<Sunny,\ Warm,\ High,\ Strong,\ Warm,\ Same>
]
Compare with (h_1)

• Sky → Same

• Temp → Same

• Humidity → Different → Replace by '?'

• Wind → Same

• Water → Same

• Forecast → Same
[
h_2=<Sunny,\ Warm,\ ?,\ Strong,\ Warm,\ Same>
]

Step 4: Scan I₃

I₃ (Negative)
[
<Rainy,\ Cold,\ High,\ Strong,\ Warm,\ Change>
]
Negative instance.
Ignore it.
[
h_3=<Sunny,\ Warm,\ ?,\ Strong,\ Warm,\ Same>
]

Step 5: Scan I₄

I₄ (Positive)
[
<Sunny,\ Warm,\ High,\ Strong,\ Cool,\ Change>
]
Compare with (h_3)

• Sky → Same

• Temp → Same

• Humidity → '?'

• Wind → Same

• Water → Different → '?'

 • Forecast → Different → '?'
[
h_4=<Sunny,\ Warm,\ ?,\ Strong,\ ?,\ ?>
]

Final Hypothesis
[
\boxed{
h=<Sunny,\ Warm,\ ?,\ Strong,\ ?,\ ?>
}
]
This is the hypothesis obtained using the Find-S Algorithm for the given dataset.
Yes. For a question like:
"Write Find-S algorithm. Apply the algorithm to obtain the hypothesis for the dataset given in the
table."
You should write both the theory (Find-S Algorithm) and the application on the dataset.

Find-S Algorithm
• Find-S algorithm is guaranteed to converge to the most specific hypothesis in (H) that is
consistent with the positive instances in the training dataset.
• Obviously, it will also be consistent with the negative instances.
• Thus, this algorithm considers only the positive instances and eliminates negative instances
while generating the hypothesis.
• It initially starts with the most specific hypothesis.
Algorithm 3.1: Find-S
Input:
Positive instances in the Training dataset
Output:
Hypothesis ‘h’
1. Initialize ‘h’ to the most specific hypothesis.
[
h=<\phi,\phi,\phi,\phi,\phi,\ldots>
]
2. Generalize the initial hypothesis for the first positive instance [Since ‘h’ is more specific].
3. For each subsequent instances:
If it is a positive instance,
• Check for each attribute value in the instance with the hypothesis ‘h’.
o If the attribute value is the same as the hypothesis value, then do nothing.
o Else if the attribute value is different than the hypothesis value, change it to ‘?’ in ‘h’.
Else if it is a negative instance,
• Ignore it.

Applying Find-S Algorithm

Step 1: Initialize h
[
h_0=<\phi,\phi,\phi,\phi,\phi,\phi>
]

Step 2: First Positive Instance

[
I_1=<Sunny,\ Warm,\ Normal,\ Strong,\ Warm,\ Same>
]
[
h_1=<Sunny,\ Warm,\ Normal,\ Strong,\ Warm,\ Same>
]

Step 3: Scan I₂ (Positive)

[
I_2=<Sunny,\ Warm,\ High,\ Strong,\ Warm,\ Same>
]
Humidity differs.
[
h_2=<Sunny,\ Warm,\ ?,\ Strong,\ Warm,\ Same>
]

Step 4: Scan I₃ (Negative)

[
I_3=<Rainy,\ Cold,\ High,\ Strong,\ Warm,\ Change>
]
Negative instance.
Ignored.
[
h_3=<Sunny,\ Warm,\ ?,\ Strong,\ Warm,\ Same>
]

Step 5: Scan I₄ (Positive)

[
I_4=<Sunny,\ Warm,\ High,\ Strong,\ Cool,\ Change>
]
Water and Forecast differ.
[
h_4=<Sunny,\ Warm,\ ?,\ Strong,\ ?,\ ?>
]

Final Hypothesis
[
\boxed{
h=<Sunny,\ Warm,\ ?,\ Strong,\ ?,\ ?>
}
]

Limitations of Find-S Algorithm

1. Find-S algorithm tries to find a hypothesis that is consistent with positive instances, ignoring
all negative instances. As long as the training dataset is consistent, the hypothesis found by
this algorithm may be consistent.
2. The algorithm finds only one unique hypothesis, wherein there may be many other
hypotheses that are consistent with the training dataset.
3. Many times, the training dataset may contain some errors; hence such inconsistent data
instances can mislead this algorithm in determining the consistent hypothesis since it
ignores negative instances.
4. Hence, it is necessary to find the set of hypotheses that are consistent with the training data
including the negative examples. To overcome the limitations of Find-S algorithm, Candidate
Elimination algorithm was proposed to output the set of all hypotheses consistent with the
training dataset.
This is the complete 5–10 mark exam answer from the provided content.

Important Questions
1) Source: Machine Learning – S. Sridhar, M. Vijayalakshmi
Bivariate Data and Multivariate Data
2.6 BIVARIATE DATA AND MULTIVARIATE DATA
• Bivariate Data involves two variables.
• Bivariate data deals with causes of relationships.
• The aim is to find relationships among data.
• Consider the following Table 2.3, which has data of the temperature
in a shop and sales sweets.
Table 2.3: Temperature in a Shop and Sales Data
Temperature (°C) Sales of Sweets (in thousands)
5 200
10 150
15 140
20 75
22 60
23 55
25 20
• Here, the aim of bivariate analysis is to find relationships among
variables.
• The relationships can then be used to comparisons, finding causes,
and in further explorations.
• To do that, graphical display of the data is necessary.
• One such graph method is called scatter plot.
Scatter Plot
• Scatter plot is used to visualize bivariate data.
 • It is useful to plot two variables with or without nominal variables, to
illustrate trends, and show differences.
• It is a plot between labels, category and response variables.
• It is a 2D graph showing the relationship between variables.
• The scatter plot indicates:
o strength,
o shape,
o direction,
o and the presence of Outliers.
• It is useful in exploratory data before calculating correlation
coefficient or fitting regression curve.
Multivariate Statistics
• In machine learning, almost all datasets are multivariable.
• Multivariate data is the analysis of more than two observable
variables and, often, thousands of multiple measurements need to be
conducted for one or more subjects.
• The multivariate data is like bivariate data but may have more than
two dependent variables.
• Some of the multivariate analysis are:
o regression analysis,
o principal component analysis,
o and path analysis.
• Multivariate data has three or more variables.
• The aim of the multivariate analysis is much more.
• They are regression analysis, factor analysis, and multivariate analysis
of variance that are explained in the subsequent chapters of this
book.
Covariance and Correlation with Suitable Examples
2.6.1 Bivariate Statistics
• Covariance and Correlation are examples of bivariate statistics.
• Covariance is a measure of joint probability of random variables, say
X and Y.
• Generally, random variables are represented in capital letters.
• It is defined as covariance for continuous random variables and is
used to measure variance between two dimensions.
Formula for Covariance
cov(X,Y)=\frac{1}{N}\sum (X-E(X))(Y-E(Y))
Where:
• X and Y are data values from X and Y.
• E(X) and E(Y) are the mean values of x and y.
• N is the number of given data.

Example 2.6
Find the covariance of data
• X = (1, 2, 3, 4, 5)
• Y = (1, 4, 9, 16, 25)
Solution
• Mean(X) = E(X) = 15/5 = 3
• Mean(Y) = E(Y) = 55/5 = 11
The covariance is computed using Eq. (2.17) as:
= ((1 − 3)(1 − 11) + (2 − 3)(4 − 11) + (3 − 3)(9 − 11) + (4 − 3)(16 − 11) + (5 −
3)(25 − 11)) / 5
= 12
• The covariance between X and Y is 12.
• It can be normalized to a value between −1 and +1.
• This is done by dividing it by the correlation of variables.
• This is called Pearson correlation coefficient.
• Sometimes N−1 can be used instead of N.
• In that case, the covariance is 60/4 = 15.

Correlation
• The Pearson correlation coefficient is the most common test for
determining any association between two phenomena.
• It measures the strength and direction of a linear relationship
between the x and y variables.
Important Information
• The correlation indicates the relationship between dimensions using
its sign.
• The sign is more important than the actual value.
Interpretation
1. If the value is positive, it indicates that the dimensions increase
together.
2. If the value is negative, it indicates that while one-dimension
increases, the other dimension decreases.
3. If the value is zero, it indicates that both the dimensions are
independent of each other.
• If the dimensions are correlated, then it is better to remove one
dimension as it is a redundant dimension.
Formula for Pearson Correlation Coefficient
r=\frac{cov(X,Y)}{\sigma_x\sigma_y}
where,
• σx, σy are the standard deviations of X and Y.

Example 2.7
Find the correlation coefficient of data
• X = (1, 2, 3, 4, 5)
• Y = (1, 4, 9, 16, 25)
Solution
• The mean values of X and Y are 15/5 = 3 and 55/5 = 11.
• The standard deviations of X and Y are 1.41 and 8.6486, respectively.
• Therefore, the correlation coefficient is given as ratio of covariance
(12 from the previous problem 2.5) and standard deviation of x and y
as per Eq. (2.18) as:
r = 12 / (1.41 × 8.6486)
= 0.984

2) Source: Machine Learning – S. Sridhar, M. Vijayalakshmi

Multivariate Statistics
• In machine learning, almost all datasets are multivariable.
• Multivariate data is the analysis of more than two observable
variables and, often, thousands of multiple measurements need to be
conducted for one or more subjects.
• The multivariate data is like bivariate data but may have more than
two dependent variables.
• Some of the multivariate analysis are:
o regression analysis,
 o principal component analysis,
o and path analysis.
• The mean of multivariate data is a mean vector and the mean of the
above three attributes is given as (2, 7.5, 1.33).
• The variance of multivariate data becomes the covariance matrix.
• The mean vector is called centroid and variance is called dispersion
matrix.
• This is discussed in the next section.
• Multivariate data has three or more variables.
• The aim of the multivariate analysis is much more.
• They are regression analysis, factor analysis and multivariate analysis
of variance that are explained in the subsequent chapters of this
book.

Heatmap
• Heatmap is a graphical representation of 2D matrix.
• It takes a matrix as input and colours it.
• The darker colours indicate very large values and lighter colours
indicate smaller values.
• The advantage of this method is that humans perceive colour well.
• So, by colour change, larger values can be perceived well.
• For example, in vehicle traffic data, heavy traffic regions can be
differentiated from low traffic regions through heatmap.
• In Figure 2.13, patient data highlighting weight and health status is
plotted.
• Here, X-axis is weights and Y-axis is patient counts.
 • The dark colour regions highlight patients' weights vs patient counts
in health status.

Pairplot
• Pairplot or scatter matrix is a data visualization technique for
multivariate data.
• A scatter matrix consists of several pair-wise scatter plots of variables
of the multivariate data.
• All the results are presented in a matrix format.
• By visual examination of the chart, one can easily find relationships
among the variables such as correlation between the variables.
• A random matrix of three columns is shown and the relationships
among the columns are plotted as a pairplot (or scattermatrix) as
shown below in Figure 2.14.
 •

4) 2.10 FEATURE ENGINEERING AND DIMENSIONALITY REDUCTION

TECHNIQUES
• Features are attributes.
• Feature engineering is about determining the subset of features that
form an important part of the input that improves the performance
of the model, be it classification or any other model in machine
learning.
• Feature engineering deals with two problems –
o Feature Transformation
o Feature Selection.
• Feature transformation is extraction of features and creating new
features that may be helpful in increasing performance.
• For example, the height and weight may give a new attribute called
Body Mass Index (BMI).
• Feature subset selection is another important aspect of feature
engineering that focuses on selection of features to reduce the time
but not at the cost of reliability.
 • The subset selection reduces the dataset size by removing irrelevant
features and constructs a minimum set of attributes for machine
learning.
• If the dataset has n attributes, then time complexity is extremely high
as n dimensions need to be processed for the given dataset.
• For n attributes, there are 2ⁿ possible subsets.
• If the value of n is high, the problem becomes intractable.
• This is called ‘curse of dimensionality’.
• Since, as the number of dimensions increases, the time complexity
increases.
• The remedy is that some of the components that do not contribute
much can be deleted.
• This results in the reduction of dimensionality.
• Choosing optimal attributes becomes a graph search problem.
• Typically, the feature subset selection problem uses greedy approach
by looking for the best choice at the time using locally optimal choice
while hoping that it would lead to global optimal solutions.

Feature Transformation
• Feature transformation is extraction of features and creating new
features that may be helpful in increasing performance.
• For example, the height and weight may give a new attribute called
Body Mass Index (BMI).

Feature Selection
• Feature subset selection is another important aspect of feature
engineering that focuses on selection of features to reduce the time
but not at the cost of reliability.
 • The subset selection reduces the dataset size by removing irrelevant
features and constructs a minimum set of attributes for machine
learning.
The features can be removed based on two aspects:
1. Feature relevancy
• Some features contribute more for classification than other features.
• For example, a mole on the face can help in face detection than
common features like nose.
• In simple words, the features should be relevant.
• The relevancy of the features can be determined based on
information measures such as:
o mutual information,
o correlation-based features like correlation coefficient,
o and distance measures.
• Distance measures are discussed in Chapter 13 of this book.
2. Feature redundancy
• Some features are redundant.
• For example, when a database table has a field called Date of birth,
then age field is not relevant as age can be computed easily from
date of birth.
• This helps in removing the column age that leads to reduction of
dimension one.

Procedure for Feature Selection

1. Generate all possible subsets.
2. Evaluate the subsets and model performance.
3. Evaluate the results for optimal feature selection.
Filter-based Selection
• Filter-based selection uses statistical measures for assessing features.
• In this approach, no learning algorithm is used.
• Correlation and information gain measures like mutual information
and entropy are all examples of this approach.

Wrapper-based Methods
• Wrapper-based methods use classifiers to identify the best features.
• These are selected and evaluated by the learning algorithms.
• This procedure is computationally intensive but has superior
performance.

Dimensionality Reduction Techniques

• The subset selection reduces the dataset size by removing irrelevant
features and constructs a minimum set of attributes for machine
learning.
• If the dataset has n attributes, then time complexity is extremely high
as n dimensions need to be processed for the given dataset.
• For n attributes, there are 2ⁿ possible subsets.
• If the value of n is high, the problem becomes intractable.
• This is called ‘curse of dimensionality’.
• Since, as the number of dimensions increases, the time complexity
increases.
• The remedy is that some of the components that do not contribute
much can be deleted.
• This results in the reduction of dimensionality.
5) The image you uploaded contains only the application/advantage part of
SVD, not the definition or procedure/steps of SVD.
So, following your instructions and using only the provided content:
Application of Singular Value Decomposition (SVD)
• The main advantage of SVD is compression.
• A matrix, say an image, can be decomposed and selectively only
certain components can be retained by making all other elements
zero.
• This reduces the contents of image while retaining the quality of the
image.
• SVD is useful in data reduction too.

8) Concept Learning
• Concept learning is a learning strategy of acquiring abstract
knowledge or inferring a general concept or deriving a category from
the given training samples.
• It is a process of abstraction and generalization from the data.
• Concept learning helps to classify an object that has a set of
common, relevant features.
• Thus, it helps a learner compare and contrast categories based on the
similarity and association of positive and negative instances in the
training data to classify an object.
• The learner tries to simplify by observing the common features from
the training samples and then apply this simplified model to the
future samples.
• This task is also known as learning from experience.
• Each concept or category obtained by learning is a Boolean valued
function which takes a true or false value.
 • For example, humans can identify different kinds of animals based on
common relevant features and categorize all animals based on
specific sets of features.
• The special features that distinguish one animal from another can be
called as a concept.
• This way of learning categories for object and to recognize new
instances of those categories is called as concept learning.
• It is formally defined as inferring a Boolean valued function by
processing training instances.
Concept learning requires three things:
1. Input
• Training dataset which is a set of training instances, each labeled
with the name of a concept or category to which it belongs.
• Use this past experience to train and build the model.
2. Output
• Target concept or Target function f.
• It is a mapping function f(x) from input x to output y.
• It is to determine the specific features or common features to
identify an object.
• In other words, it is to find the hypothesis to determine the target
concept.
• For e.g., the specific set of features to identify an elephant from all
animals.
3. Test
• New instances to test the learned model.

Hypothesis
 • A hypothesis ‘h’ approximates a target function ‘f’ to represent the
relationship between the independent attributes and the dependent
attribute of the training instances.
• The hypothesis is the predicted approximate model that best maps
the inputs to outputs.
• Each hypothesis is represented as a conjunction of attribute
conditions in the antecedent part.
Example
• (Tail = Short) ∧ (Color = Black)
• The set of hypothesis in the search space is called as hypotheses.
• Hypotheses are the plural form of hypothesis.
• Generally ‘H’ is used to represent the hypotheses and ‘h’ is used to
represent a candidate hypothesis.
Attribute conditions
• Each attribute condition is the constraint on the attribute which is
represented as attribute-value pair.
• In the antecedent of an attribute condition of a hypothesis, each
attribute can take value as either ‘?’ or ‘φ’ or can hold a single value.
?
• “?” denotes that the attribute can take any value.
• Example: Color = ?
φ
• “φ” denotes that the attribute cannot take any value, i.e., it
represents a null value.
• Example: Horns = φ
Single value
• Single value denotes a specific single value from acceptable values of
the attribute.
 • Example: Tail = Short

Hypothesis Space
• Hypothesis space is the set of all possible hypotheses that
approximates the target function f.
• In other words, the set of all possible approximations of the target
function can be defined as hypothesis space.
• From this set of hypotheses in the hypothesis space, a machine
learning algorithm would determine the best possible hypothesis that
would best describe the target function or best fit the outputs.
• Generally, a hypothesis representation language represents a larger
hypothesis space.
• Every machine learning algorithm would represent the hypothesis
space in a different manner about the function that maps the input
variables to output variables.
• For example, a regression algorithm represents the hypothesis space
as a linear function whereas a decision tree algorithm represents the
hypothesis space as a tree.
• The set of hypotheses that can be generated by a learning algorithm
can be further reduced by specifying a language bias.

Version Space
• The subset of hypothesis space that is consistent with all-observed
training instances is called as Version Space.
• Version space represents the only hypotheses that are used for the
classification.
• The version space contains the subset of hypotheses from the
hypothesis space that is consistent with all training instances in the
training dataset.
Generalization and Specialization
• In order to understand about how we construct this concept
hierarchy, let us apply this general principle of
generalization/specialization relation.
• By generalization of the most specific hypothesis and by
specialization of the most general hypothesis, the hypothesis space
can be searched for an approximate hypothesis that matches all
positive instances but does not match any negative instance.
Searching the Hypothesis Space
There are two ways of learning the hypothesis, consistent with all training
instances from the large hypothesis space.
1. Specialization
• General to Specific learning.
2. Generalization
• Specific to General learning.

Generalization – Specific to General Learning

• This learning methodology will search through the hypothesis space
for an approximate hypothesis by generalizing the most specific
hypothesis.
Solution
• We will start from all false or the most specific hypothesis to
determine the most restrictive specialization.
• Consider only the positive instances and generalize the most specific
hypothesis.
• Ignore the negative instance.
Specialization – General to Specific Learning
• This learning methodology will search through the hypothesis space
for an approximate hypothesis by specializing the most general
hypothesis.

List-Then-Eliminate Algorithm (Version Space)

Principle
• The principle idea of this learning algorithm is to initialize the
version space to contain all hypotheses and then eliminate any
hypothesis that is found inconsistent with any training instances.
• Initially, the algorithm starts with a version space to contain all
hypotheses scanning each training instance.
• The hypotheses that are inconsistent with the training instance are
eliminated.
• Finally, the algorithm outputs the list of remaining hypotheses that
are all consistent.
Input
• Version Space – a list of all hypotheses.
Output
• Set of consistent hypotheses.
Algorithm
1. Initialize the version space with a list of hypotheses.
2. For each training instance,
o remove from version space any hypothesis that is inconsistent.
Note
• This algorithm works fine if the hypothesis space is finite but
practically it is difficult to deploy this algorithm.
 • Hence, a variation of this idea is introduced in the Candidate
Elimination algorithm.
12) Example 2.9: Find LU decomposition of the given matrix
Given:
[
A=
\begin{pmatrix}
1 & 2 & 4\
3 & 3 & 2\
3&4&2
\end{pmatrix}
]
Solution
• First, augment an identity matrix and apply Gaussian elimination.
Initial Matrix
[
\left[
\begin{array}{ccc|ccc}
1&0&0&1&2&4\
0&1&0&3&3&2\
0&0&1&3&4&2
\end{array}
\right]
]

Apply
[
R_2 = R_2 - 3R_1
]
[
\left[
\begin{array}{ccc|ccc}
1&0&0&1&2&4\
3&1&0&0&-3&-10\
0&0&1&3&4&2
\end{array}
\right]
]

Apply
[
R_3 = R_3 - 3R_1
]
[
\left[
\begin{array}{ccc|ccc}
1&0&0&1&2&4\
3&1&0&0&-3&-10\
3&0&1&0&-2&-10
\end{array}
\right]
]

Apply
[
R_3 = R_3 - \frac{2}{3}R_2
]
[
\left[
\begin{array}{ccc|ccc}
1&0&0&1&2&4\
3&1&0&0&-3&-10\
3&\frac{2}{3}&1&0&0&-\frac{10}{3}
\end{array}
\right]
]

Observation
• Now, it can be observed that the first matrix is L as it is the lower
triangular matrix whose values are the determiners used in the
reduction of equations above such as 3, 3 and 2/3.
• The second matrix is U, the upper triangular matrix whose values are
the values of the reduced matrix because of Gaussian elimination.
L Matrix
[
L=
\begin{pmatrix}
1&0&0\
3&1&0\
3&\frac{2}{3}&1
\end{pmatrix}
]
U Matrix
[
U=
\begin{pmatrix}
1&2&4\
0&-3&-10\
0&0&-\frac{10}{3}
\end{pmatrix}
]

Applications of LU Decomposition
 • It can be cross verified that the multiplication of LU yields the
original matrix A.
• Some of the applications are:
o finding matrix inverses
o determinant
• If the order of the matrix is large, then this method can be used.

11) Example 2.8: Solve the following set of equations using Gaussian
Elimination method
Given:
[
2x_1 + 4x_2 = 6
]
[
4x_1 + 3x_2 = 7
]
Solution
Rewrite this in matrix form as follows:
[
\begin{pmatrix}
2 & 4 \mid 6 \
4 & 3 \mid 7
\end{pmatrix}
]
[
\sim
\begin{pmatrix}
2 & 4 \mid 6 \
4 & 3 \mid 7
\end{pmatrix}
\qquad
R_1=\frac{R_1}{2}
]
Apply the transformation by dividing the row 1 by 2.
[
\sim
\begin{pmatrix}
1 & 2 \mid 3 \
4 & 3 \mid 7
\end{pmatrix}
\qquad
R_2=R_2-4R_1
]
[
\sim
\begin{pmatrix}
1 & 2 \mid 3 \
0 & -5 \mid -5
\end{pmatrix}
\qquad
R_2=\frac{R_2}{-5}
]
[
\sim
\begin{pmatrix}
1 & 2 \mid 3 \
0 & 1 \mid 1
\end{pmatrix}
\qquad
R_1=R_1-2R_2
]
[
\sim
\begin{pmatrix}
1 & 0 \mid 1 \
0 & 1 \mid 1
\end{pmatrix}
]
Therefore, in the reduced echelon form, it can be observed that:
[
x_2 = 1
]
[
x_1 = 1
]
Answer
• (x_1 = 1)
• (x_2 = 1)