ME5990

�

Seminar: Historical Terms� in Machine Learning (pattern recognition)

Outline

• Supervised Learning
• K-nearest neighbors
• Principal Component Analysis
• Perceptron
• Support Vector Machine
• Ensemble Methods

​

K-nearest neighborhood

• Non-parametric classification
• First developed in 1951 by Evelyn Fix and Joseph Hodges 
• Can my neighbor vote?

https://brilliantmaps.com/2020-county-election-map/

Problem for Start

• If we were given a dataset with 2 classes:

​

​

​

​

​

​

• Can we propose a voting mechanism to determine which class the green dot belongs to?

​

(0,1)

?

?

K: number of neighbors

(0,1)

(-1,2)

d

Some other distances

​

​

K: number of neighbors

(0,1)

(-1,2)

d

K: number of neighbors

• K-Neighbor: K-closest point

​

​

​

​

​

​

​

• The green point belongs to red class because among 3 neighbors:
• 3 out of 3 are red
• 0 out of 3 are blue

​

​

​

​

​

​

​

​

(0,1)

(-1,2)

d

K: number of neighbors

• K-Neighbor: K-closest point

​

​

​

​

​

​

​

• The green point belongs to blue class because among 3 neighbors:
• 1 out of 3 are red
• 2 out of 3 are blue

​

​

​

​

​

​

​

​

(0,1)

(-1,2)

d

Number of K matters

• For different K, the classification may be different

​

Decision Boundary

• Decision boundary

https://www.analyticsvidhya.com/blog/2018/03/introduction-k-neighbours-algorithm-clustering/

K-nearest Neighbor

• If you are near red, you are red
• If you are near blue, you are blue

​

​

• The people who you surround yourself with matters

Outline

• Supervised Learning
• K-nearest neighbors
• Naïve Bayes Classifier
• Principal Component Analysis
• Perceptron
• Support Vector Machine
• Ensemble Methods

​

Outline

• Supervised Learning
• K-nearest neighbors
• Naïve Bayes Classifier
• Principal Component Analysis
• Perceptron
• Support Vector Machine
• Ensemble Methods

​

Principal Component Analysis

• Which feature is more important?

​

​

​

​

​

​

​

​

• The direction “spread most” is most important
• Looks like it is the “lucky color code”

​

PCA

• The original features can be projected to another set feature with widest spread

PCA technique

• Max principal Stress?

​

PCA

• You probably were taught to solve the problem by Mohr’s circle

PCA

PCA

PCA cookbook (via eigenvector decoupling)

Demonstration of PCA

(-1,-1)

(1,1)

(3,3)

Demonstration of PCA

(-1,-1)

(1,1)

(3,3)

Demonstration of PCA

(-1,-1)

(1,1)

(3,3)

Demonstration of PCA

(-1,-1)

(1,1)

(3,3)

(0,0.2)

PCA

• Too many features and you don’t know which one is most important? Do principal component analysis!
• PCA has the same concept as max principal stress problem
• Don’t use Mohr’s circle anymore, use Eigenvalue and eigenvectors!!

(https://amesweb.info/StressStrainTransformations/PlaneStressPrincipalStressCal/PrincipalStressCalculator.aspx)

(https://www.emathhelp.net/en/calculators/linear-algebra/eigenvalue-and-eigenvector-calculator/?i=%5B%5B100%2C40%5D%2C%5B40%2C70%5D%5D)

​

Outline

• Supervised Learning
• K-nearest neighbors
• Naïve Bayes Classifier
• Principal Component Analysis
• Perceptron
• Support Vector Machine
• Ensemble Methods

​

Perceptron

• One of the oldest classifier
• Invented in 1943, before computer is invented

Mark I perceptron machine, from wikipedia

Decision boundary for LDF

Image from: https://www.csd.uwo.ca/~oveksler/Courses/CS434a_541a/Lecture9.pdf

LDF for 2 classes

(0,1)

(1,0)

Hyperplane

(0,1)

(1,0)

LDF: augmented feature vector

LDF: Augmented feature vector

Demonstration of “augmented feature vector”

Summary

• Traditionally, perceptron is a linear discriminator for binary classification. The data are encoded with (+1, -1).
• We have a new name of perceptron: fully connected layer
• Multi-layer perceptron: a feedforward network made with multiple fully connected layer
• Proposed on top of perceptron in 1960s
• Training method was only invented in 1970s

​

​

​

Outline

• Supervised Learning
• K-nearest neighbors
• Naïve Bayes Classifier
• Principal Component Analysis
• Perceptron
• Support Vector Machine
• Ensemble Methods

​

Support Vector Machine

• Another powerful linear classifier
• Can be used to classify multiple classes

​

Support

Support vector machine

• We want our line to be at “center” of these two classes
• What is “center”?
• We define margin by expanding the line till hit a point
• We wish the margin to be as large as possible

Support vector machine

• What is support vector?

​

​

​

​

​

​

​

​

• What does “we want the margin as large as possible” mean?
• We want the length of support vector to the boundary as large as possible!

Support vector

Support vector machine: some maths

m

One-to-one, one-to-rest

• One-to-one

​

One-to-one, one-to-rest

• One-to-rest

​

https://www.baeldung.com/cs/svm-multiclass-classification

Support Vector Machine

• A really powerful linear discriminant method
• Reported good at solving hand-writing problem, in bar with LeNET

​

​

​

Outline

• Supervised Learning
• K-nearest neighbors
• Principal Component Analysis
• Perceptron
• Support Vector Machine
• Ensemble Methods

​

Ensemble methods

• Bagging (Breiman 1994,...): Bootstrap aggregating
• Random forests (Breiman 2001,...)
• Boosting (Freund and Schapire 1995, Friedman et al. 1998,...)

​

Predict class label for unseen data by aggregating a set of predictions (classifiers learned from the training data)

General Idea

Ensemble methods

All ensemble methods consist of:

• Step 1: Generate multiple sub-dataset via various re-sampling technique
• Bootstrapping
• Pasting
• …
• Step 2: Train classifiers on each sub-dataset
• Use same model for each sub-dataset (e.g. SVM, Naïve Bayes)
• Step 3: Aggregate (combine) all classifier
• Voting for classification questions is the most popular way
• Find average of models (especially for regression problem)

​

Summary on Bagging

• If majority’s voting is correct, we will be destined to choose the correct one
• If majority’s voting is wrong, we will be destined to choose the wrong one