ﻢِ ﺴﺑِ ا ﻦِﻤﺣﺮﻟا ﻪﻠﻟا ِﻢِ · Make a Schedule of 24 Hours to get...

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

Machine LearningLecture 10 – Instance Based Learning

Dr. Rao Muhammad Adeel Nawab

Dr. Rao Muhammad Adeel Nawab 3

How to Work?

.کام ��ن﮲ا

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

﮲ی �

﮶و�

﮲� .

ی کام ��﮶و�

﮲ی �

﮶و�

﮲�ے �� ھ

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

�ك نعبد وا ��

تعين ا س��﮳�ه

﮴�ں﮵: � ے �ہ

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

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

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

اور �﮴


ی﮴��ں﮵ ہہاری

﮲ت﮴ ��﮳ی �

﮲. ��ب

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

﯀� و ��و

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

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

﮴عام � : �

﮲ے ا�

﮲� و

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

Power of Effort & Dua


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

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

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

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

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

Dua – Take Help from Allah Before Starting Any Task


Mainly get Excellence in two things

Course Focus

Become a great Human Being

Become a great Machine Learning Engineer


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


Balanced Life is Ideal Life


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.


Second - Spirituality

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

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


Second – Spirituality (Cont.)

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

تگا� ے

ا� جج

Introduction to Instance-based Learning


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


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


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


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


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


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.


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




Basic idea

Training Record

Test Record

Compute Distance



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


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


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



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

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

Compute distance between two points

Euclidean distance


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



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



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



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



Problem with Euclidean measure

Can produce counter-intuitive results

High dimensional data curse of dimensionality

Distance Measures


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

Distance Measures

Distance measure for strings

Edit distance

Example


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

ﻢِ ﺴﺑِ ا ﻦِﻤﺣﺮﻟا ﻪﻠﻟا ِﻢِ · Make a Schedule of 24 Hours to get...

Documents

Transcript of ﻢِ ﺴﺑِ ا ﻦِﻤﺣﺮﻟا ﻪﻠﻟا ِﻢِ · Make a Schedule of 24 Hours to get...