Classification: Perceptron

Classification

2

Classification

• We will learn
• Perceptron
• Support vector machine (SVM)
• Logistic regression

​

​

• To find

a classification boundary

​

​

3

Perceptron

4

Perceptron

5

Perceptron

6

Distance from a Line

7

8

9

10

Sign

• Sign with respect to a line

​

​

​

​

11

12

Perceptron Algorithm

• The perceptron implements

​

• Given the training set

​

1. pick a misclassified point

​

• and update the weight vector

13

Perceptron Algorithm

14

Iterations of Perceptron

15

Diagram of Perceptron

16

Perceptron Loss Function

17

Perceptron Algorithm in Python

18

Perceptron Algorithm in Python

19

Perceptron Algorithm in Python

20

Perceptron Algorithm in Python

21

Perceptron Algorithm in Python

22

Perceptron Algorithm in Python

23

Scikit-Learn for Perceptron

24

The Best Hyperplane Separator?

• Perceptron finds one of the many possible hyperplanes separating the data if one exists
• Of the many possible choices, which one is the best?

​

• Utilize distance information
• Intuitively we want the hyperplane having the maximum margin
• Large margin leads to good generalization on the test data
• we will see this formally when we discuss Support Vector Machine (SVM)

​

• Utilize distance information from all data samples
• We will see this formally when we discuss the logistic regression

​

• Perceptron will be shown to be a basic unit for neural networks and deep learning later

25

Support Vector Machine

Classification (Linear)

• Autonomously figure out which category (or class) an unknown item should be categorized into

​

• Number of categories / classes
• Binary: 2 different classes
• Multiclass: more than 2 classes

​

• Feature
• The measurable parts that make up the unknown item (or the information you have available to categorize)

27

Distance from a Line

28

29

30

31

32

33

Illustrative Example

34

Hyperplane

35

Decision Making

36

Decision Boundary or Band

37

Data Generation for Classification

38

Optimization Formulation 1

39

Optimization Formulation 1

40

CVXPY 1

41

CVXPY 1

42

Linear Classification: Outlier

• Note that in the real world, you may have noise, errors, or outliers that do not accurately represent the actual phenomena

​

• Linearly non-separable case

​

​

​

43

Outliers

​

​

​

​

​

​

​

• No solutions (hyperplane) exist

​

• We have to allow some training examples to be misclassified !
• but we want their number to be minimized

44

Optimization Formulation 2

45

Optimization Formulation 2

• The optimization problem for the non-separable case

46

Expressed in a Matrix Form

47

CVXPY 2

48

Further Improvement

• Notice that hyperplane is not as accurately represent the division due to the outlier

​

​

​

​

​

​

​

​

​

• Can we do better when there are noise data or outliers?
• Yes, but we need to look beyond linear programming

​

• Idea: large margin leads to good generalization on the test data���

49

Maximize Margin

50

Support Vector Machine

51

Support Vector Machine

• In a more compact form

52

Scikit-learn

53

Classifying Non-linear Separable Data

54

Classifying Non-linear Separable Data

55

Classifying Non-linear Separable Data

56

Kernel

• Often we want to capture nonlinear patterns in the data
• nonlinear regression: input and output relationship may not be linear
• nonlinear classification: classes may note be separable by a linear boundary

​

• Linear models (e.g. linear regression, linear SVM) are not just rich enough
• by mapping data to higher dimensions where it exhibits linear patterns
• apply the linear model in the new input feature space
• mapping = changing the feature representation

​

• Kernels: make linear model work in nonlinear settings

​

57

Nonlinear Classification

58

https://www.youtube.com/watch?v=3liCbRZPrZA

Classifying Non-linear Separable Data

59

Classifying Non-linear Separable Data

60

Classifying Non-linear Separable Data

61

Logistic Regression

Linear Classification: Logistic Regression

• Logistic regression is a classification algorithm
• don't be confused

​

• Perceptron: make use of sign of data

​

• SVM: make use of margin (minimum distance)
• Distance from two closest data points

​

• We want to use distance information of all data points
• logistic regression

63

Using Distances

64

Using Distances

65

Using Distances

66

Using Distances

67

Using all Distances

68

Using all Distances

69

Using all Distances with Outliers

• SVM vs. Logistic Regression

70

SVM

Logistic Regression

Sigmoid Function

71

Step function

Sigmoid Function

72

Sigmoid Function

73

Goal: We Need to Fit 𝜔 to Data

74

Goal: We Need to Fit 𝜔 to Data

​

​

​

​

​

​

• It would be easier to work on the log likelihood.

​

​

​

• The logistic regression problem can be solved as a (convex) optimization problem:

​

​

• Again, it is an optimization problem

75

Logistic Regression using GD

76

Gradient Descent

• To use the gradient descent method, we need to find the derivative of it

​

​

​

​

​

​

• We need to compute

​

​

77

Gradient Descent

78

Gradient Descent for Logistic Regression

​

​

​

​

​

​

​

​

​

​

​

​

• Maximization problem
• Be careful on matrix shape

79

Python Implementation

80

Python Implementation

81

Logistic Regression using CVXPY

82

Probabilistic Approach (or MLE)

83

Probabilistic Approach (or MLE)

84

CVXPY Implementation

​

​

​

​

​

​

​

​

85

In a More Compact Form

86

CVXPY Implementation

87

Logistic Regression using Scikit-Learn

88

Logistic Regression using Scikit-Learn

89

Non-linear Classification

90

Non-linear Classification

• Same idea as non-linear regression: non-linear features
• Explicit or implicit Kernel

​

91

Explicit Kernel

92

Non-linear Classification

93

Multiclass Classification

94

Multiclass Classification

• Generalization to more than 2 classes is straightforward
• one vs. all (one vs. rest)
• one vs. one

​

95

Multiclass Classification

96