ن احم حيم بسم الله الر لر

Machine LearningLecture 10 – Instance Based Learning

Dr. Rao Muhammad Adeel Nawab

Dr. Rao Muhammad Adeel Nawab 3

How to Work?

.کام ��ن﮲ا

ی کام ��ن﮲ا﮶و�

﮲ی �

﮶و�

﮲� .

ی کام ��﮶و�

﮲ی �

﮶و�

﮲�ے ��� ھ 

﮴ .ن﮲اال�ه �و سا�ت﮵ت ﮴ :آ ك � ��

�ك نعبد وا �� �

تعين ا س���﮳�ه

﮴�ں﮵: � ے �ہ

﮴� ی �با﮳دت �� �ر﮵ی �ہ

﮴م � ﮵ا ال�ه �ہ . ن

�ں﮵  ے �ہ﮴�﮲�� �ے �د د ما ی  �﮳ھ �ہ

اور �﮴

Dr. Rao Muhammad Adeel Nawab 4

ی﮴��ں﮵ ہہاری

﮲ت﮴ ���﮳ی �

﮲. ��ب

�ں﮵ ے �ہ﮴� ��ے ��﮳ی �ل﮷ جا﮳ ے 

﯀� و ��و

﮴وں � �ں﮵ �ہ .دعائ

�ط : دعا تقيم صر �ط ٱٱلمس� مٱٱهد� ٱٱلصر �ن ٱ�نعمت �ليه ٱٱ����﮳�ه

﮴عام � : �

﮲ے ا�

﮲� و 

﮴��ں﮵ ��د﮵�ی راه د�ھا ان �و�وں �ی راه �﮳ں﮲ ��﮷ � ﮵ا�ہ . ب

Power of Effort & Dua

Dr. Rao Muhammad Adeel Nawab 5

�هم� خر لي وا�تر لي الل�متنا لا� ما �ل

�ب�انك لا �لم لنا ا س�

�ك ٱ�نت العليم الحكيم ن�ا

ح لي صدري رب اشر لي امري و�سر

وا�لل عقدة من لساني یفقهوا قولي

Dua – Take Help from Allah Before Starting Any Task

Dr. Rao Muhammad Adeel Nawab 6

Mainly get Excellence in two things

Course Focus

Become a great Human Being

Become a great Machine Learning Engineer

Dr. Rao Muhammad Adeel Nawab 7

Introduction to Instance-based LearningNearest Neighbor ClassificationDistance Measures

ReadingChapter 8 of MitchellChapter 5 ”Memory-based Learning Algorithms” in W. Daelemans, J. Zavrel, K. van der

Lecture Outline

Dr. Rao Muhammad Adeel Nawab 8

Balanced Life is Ideal Life

Dr. Rao Muhammad Adeel Nawab 9

Make a Schedule

BEGINNER INTERMEDIATE EXPERT EXCELLENCE

Make a Schedule of 24 Hours to get EXCELLENCE in 5 thingsA Journey from

You must have a combination of five things with different variations. However, aggregate will be same.

Dr. Rao Muhammad Adeel Nawab 10

Second - Spirituality

ذا�ہ �� غغ کا ذ�� روح ےالله

Read Quran-e-Pak dailyRead Durood Sharif / Istighfar / any other Zikar at least 300 times dailyOffer 5 prayers daily

Dr. Rao Muhammad Adeel Nawab 11

Second – Spirituality (Cont.)

Excellence in Spiritualityھ ا�ت ے ہہ �ی � ےدغا �ے �ی � ھا وا�ٹ کام �ہ و

تگا� ے

ا� جج

Introduction to Instance-based Learning

Dr. Rao Muhammad Adeel Nawab 13

The machine learning algorithms we have examined so far

FIND-S algorithm

Candidate Elimination algorithm

Decision Tree Learning algorithm (ID3)

Artificial Neural Networks

Deep Learning algorithms

Bayesian Learning algorithm (Naïve Bayes)

Instance-based Learning - Introduction

Dr. Rao Muhammad Adeel Nawab 14

Constructan explicit representation of the target function(approximated target function)from a

Set of training examplesSet of hypotheses

approximated target function is applied, and thetarget classification returned

Instance-based Learning - Introduction

To classify a new (or unseen) instance

Dr. Rao Muhammad Adeel Nawab 15

Instance-based Learning – Introduction (cont…)

In contrast, instance-based algorithms

simply store the training examples

To classify a new (or unseen) instance

It is compared to the stored examples

Depending on its relationship to training examples

It is assigned a target classification

Dr. Rao Muhammad Adeel Nawab 16

Lazy Methods vs Eager Methods

Because instance-based methods defer processing until a new instance must be classified, they are called lazy methods

Lazy Methods

Methods which build representations of the target function as training examples are presented are called eager methods

Eager Methods

Nearest Neighbor Classification

Dr. Rao Muhammad Adeel Nawab 18

k-Nearest Neighbor Learning

Instances Representation

Generally, assumes instances are represented as n-tuples of real-values, i.e. as points in n-dimensional space

Distance between Instances

Distance between any two instances is defined in terms of theEuclidean distance

k-NN is the “grand-daddy” of instance-based methods

Dr. Rao Muhammad Adeel Nawab 19

Instance-Based Classifiers

Atr 1 … … … Atr N ClasssABBCACB

Atr 1 … … … Atr N

Set of Stored Cases

Unseen Cases

Store the training records.Use training records topredict the class label ofunseen cases.

Dr. Rao Muhammad Adeel Nawab 20

If there is long hair like a female, covered head with scarflike a female, then it’s probably a female

Nearest Neighbor Classifiers

Training Record

Test Record

Basic idea

Dr. Rao Muhammad Adeel Nawab 21

If there is long hair like a female, covered head with scarflike a female, then it’s probably a female

Nearest Neighbor Classifiers

Basic idea

Training Record

Test Record

Compute Distance

Dr. Rao Muhammad Adeel Nawab 22

If there is long hair like a female, covered head with scarflike a female, then it’s probably a female

Nearest Neighbor Classifiers

Basic idea

Training Record

Test Record

Compute Distance

Dr. Rao Muhammad Adeel Nawab 23

Nearest Neighbor Classifiers

Unknown record

The set of stored recordsDistance Metric to compute distance between recordsThe value of k, the number of nearest neighbors to retrieve

1

2

3

Requires three things

Dr. Rao Muhammad Adeel Nawab 24

Nearest Neighbor Classifiers (cont…)

Unknown record

Compute distance to other training recordsIdentify k nearest neighbors Use class labels of nearest neighbors to determine the class label of unknown record (e.g., by taking majority vote)

To classify an unknown record

Dr. Rao Muhammad Adeel Nawab 25

K-nearest neighbors of a record x are data points that have the k smallest distance to x

Definition of Nearest Neighbor

X X X

(a) 1-nearest neighbor (b) 2-nearest neighbor (c) 3-nearest neighbor

Dr. Rao Muhammad Adeel Nawab 26

Nearest Neighbor Classification

𝒅𝒅(𝒑𝒑,𝒒𝒒) = �𝒊𝒊

(𝒑𝒑𝒊𝒊 − 𝒒𝒒𝒊𝒊)𝟐𝟐

Compute distance between two points

Euclidean distance

Dr. Rao Muhammad Adeel Nawab 27

Nearest Neighbor Classification (cont...)

Determine the class from nearest neighbor list

Take the majority vote of class labels among the k-nearest neighbors

Weigh the vote according to distance

weight factor, w = 1 / d2

Dr. Rao Muhammad Adeel Nawab 28

Nearest Neighbor Classification

If k is too small, sensitive to noise pointsIf k is too large, neighborhood may include points from other classes

X

Choosing the value of K

Dr. Rao Muhammad Adeel Nawab 29

Nearest Neighbor Classification

Height of a person may vary from 1.5m to 1.8mWeight of a person may vary from 90lb to 300lbIncome of a person may vary from $10K to $1M

Example

Attributes may have to be scaled to prevent distance measures from being dominated by one of the attributes

Scaling issues

Dr. Rao Muhammad Adeel Nawab 30

Nearest Neighbor Classification

k-NN classifiers are lazy learners

It does not build models explicitly

Unlike eager learners such as decision tree induction and rule-based systems

Classifying unknown records are relativelyexpensive

Dr. Rao Muhammad Adeel Nawab 31

Nearest Neighbor Classification

Problem with Euclidean measure

Can produce counter-intuitive results

High dimensional data curse of dimensionality

Distance Measures

Dr. Rao Muhammad Adeel Nawab 33

Choosing the correct distance function is essentialEucledian, MinkowskiSimple Matching CoefficientJaccard measureCosine Measure

Distance Measures

Distance measure for strings

Edit distance

Example

Dr. Rao Muhammad Adeel Nawab 34

Distance between two strings: minimal number of operations to transform one into another

Insert a characterDelete a characterReplace a character with another

Edit Distance

Hello Jello distance = 1

Good Goodbye distance = 3

Example