1 of 53

CSE 5523: �Nearest Neighbor

2 of 53

Important for this week

  • Register: If you were on the waitlist but have not been enrolled, please talk to me after the class
  • Register for the class on piazza: our platform for discussion and communication
    • https://piazza.com/osu/autumn2024/cse5523_chao (please use name.#@osu.edu)
    • Access code: osu-cse-5523-AU24-chao
  • Math review/self-diagnostic: do Homework #0 and suggested materials on the website --- extremely important to check your readiness for the course

​

  • Decision: stay or drop

​

  • Office hours: start this Thursday
    • Mine: Tuesday 11 am - 12 pm, Thursday 6 pm - 7 pm (DL 587)
    • TA (Tai-Yu Pan): Monday 11 am - 12 pm, Friday 4 pm - 5 pm (BE406, #12 and #13)

2

3 of 53

Interested in the growing field of Autonomous Vehicles (AV)? Want to transform a Chevy Bolt into a fully autonomous vehicle?

​

We have opportunities for CSE, MAE and ECE Students!

​

Gain hands-on technical skills while also networking with industry professionals at SAE & GM!

Website

Interest Survey

Interest in the Buckeye AutoDrive Team?

4 of 53

Today

​

Review

  • ML problem solving
  • Training, validation, testing

​

Nearest neighbor

  • Basic and variants
  • Properties
  • Curse of dimensionality
  • Bayes optimal classifier

​

​

​

5 of 53

 

  •  

5

6 of 53

 

  •  

6

7 of 53

Empirical risk minimization (ERM)

  •  

7

8 of 53

Questions?

9 of 53

Today

​

Review

  • ML problem solving
  • Training, validation, testing

​

Nearest neighbor

  • Basic and variants
  • Properties
  • Curse of dimensionality
  • Bayes optimal classifier

​

​

​

10 of 53

Nearest neighbor

10

 

 

Which COLOR?

Why?

11 of 53

Nearest neighbor

11

 

 

Which COLOR?

Why?

12 of 53

Nearest neighbor

12

 

 

Which COLOR?

Why?

13 of 53

Nearest neighbor

13

 

 

Which COLOR?

Why?

14 of 53

Nearest neighbor

14

 

 

Which COLOR?

Why?

15 of 53

Nearest neighbor

  •  

15

16 of 53

Nearest neighbor

16

 

 

17 of 53

Nearest neighbor

  •  

17

18 of 53

Distance

  • Nearest neighbor classifiers rely on a distance metric
  • The better that metric reflects label similarity, the better the classifier is.

​

​

    • L2 distance�(Euclidean):

​

    • L1 distance:

​

​

    • Lp norm:

​

18

 

 

 

 

19 of 53

Nearest neighbor (Euclidean distance)

19

 

 

 

20 of 53

Nearest neighbor (Manhattan distance)

20

 

 

 

21 of 53

Nearest neighbor

21

 

 

 

22 of 53

Nearest neighbor (Euclidean distance)

22

 

 

 

 

23 of 53

Questions?

24 of 53

K-Nearest neighbors (KNN)

  •  

24

25 of 53

KNN (Euclidean distance)

25

 

 

 

K=1

26 of 53

KNN (Euclidean distance)

26

 

 

 

K=3

27 of 53

KNN (Euclidean distance)

27

 

 

 

K=5

28 of 53

KNN (Euclidean distance)

28

 

 

 

K=N

 

29 of 53

KNN

  •  

29

30 of 53

Question

  • How to resolve the case of a tie?

​

​

​

  • Applicable to binary classification only or not?

30

31 of 53

KNN (Euclidean distance) for multiple classes

31

 

 

K=5

32 of 53

KNN (Euclidean distance) for multiple classes

32

 

 

K=3

33 of 53

Variants of KNN: Rules

  •  

33

 

 

34 of 53

Variants of KNN: Distances

  •  

34

35 of 53

Variants of KNN: Distances

  • What does Mahalanobis distance mean? How to set M?

35

a

b

 

 

  • Long-standing statistical problem. Can estimate M or A from covariance

​

  • Distance metric learning to learn M or A

36 of 53

Commonly-used tricks for pre-processing

  •  

36

37 of 53

Today

​

Review

  • ML problem solving
  • Training, validation, testing

​

Nearest neighbor

  • Basic and variants
  • Properties
  • Curse of dimensionality
  • Bayes optimal classifier

​

​

​

38 of 53

Properties

  •  

38

Assuming no duplicated data input!

39 of 53

Properties

  •  

 

 

40 of 53

Properties

  •  

40

41 of 53

What is the effect of K?

41

42 of 53

What is the effect of K?

42

43 of 53

How to choose K?

43

44 of 53

Leave-one-out Cross-validation

  •  

44

 

 

45 of 53

Pros and Cons

  • Pros
    • Easy to implement (and have theoretical guarantee)
    • No training, suitable for “dynamically” changing training data
    • Suitable for “unknown” number of classes
    • Suitable for not well-defined classes (e.g., image retrieval, Google image search)

​

​

  • Cons
    • Need to carry all the training data to testing
    • O(NxD) test time (speed-up by KD-tree or hashing)
    • Become less effective in high-dimensional space: Curse of dimensionality
    • Popular distance metrics may not be good enough

45

Okapi un animal misterios Okapia johnstoni - zooland.ro

46 of 53

Questions?

47 of 53

Curse of dimensionality

  • In high-dimensional space
    • Hard to find training data that are close to the test data

47

Higher dimension, hard to find neighbors!

Most uniformly distributed data are outside the circle

 

 

48 of 53

Curse of dimensionality

  • In high-dimensional space
    • Every training data seem to be equally far away from the test data

48

 

 

 

A

B

49 of 53

Feature learning, dimensionality reduction

49

 

50 of 53

Questions?

51 of 53

Theoretical guarantee: Loss lower bound

  •  

51

52 of 53

Theoretical guarantee: NN vs. Bayes optimal

  •  

52

53 of 53

Summary

  • KNN classifiers are lazy learning methods
  • The same algorithm works for binary and multi-class classification
  • Assumptions: similar inputs, similar outputs

​

  • Different hypothesis classes are governed by (1) K, (2) distance metric
  • “Leave-One-Out” (LOO) cross-validation

​

  • Pros: Easy to implement, “no training”, theoretical guarantee
  • Cons: test time, (training) data memory, curse of dimensionality

53