Classification: Perceptron

Classification

• Categorizing data into predefined classes or categories based on input features

​

• Examples
• Spam detection: Classifying emails as either spam or not spam
• Image recognition: Identifying objects, animals, or faces in images
• Medical diagnosis: Predicting whether a patient has a particular condition based on diagnostic data

​

2

Classification

3

Classification

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

​

​

• To find a classification boundary

​

​

4

Classification

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

​

​

• To find a classification boundary

​

​

5

Classification

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

​

​

• To find a classification boundary

​

​

6

Perceptron

7

Perceptron

8

Classification Boundary

9

Learning a Hyperplane for Classification

10

Learning a Hyperplane for Classification

11

Learning a Hyperplane for Classification

12

Perceptron Algorithm

• The perceptron implements

​

• Given the training set

​

1. pick a misclassified point

​

• and update the weight vector

13

Perceptron Algorithm: Illustration

14

Perceptron Algorithm: Illustration

15

Perceptron Algorithm: Illustration

16

Perceptron Algorithm: Illustration

17

Perceptron Algorithm: Illustration

18

Perceptron Algorithm: Illustration

19

Why Perceptron Updates Work ?

20

Diagram of Perceptron

• Perceptron can be viewed as a simple neuron in an Artificial Neural Network (ANN)

​

​

​

​

​

​

​

​

​

• Perceptron Update Rule (discrete version):

​

• Gradient Descent Update Rule (continuous version):

​

21

Loss Function for Perceptron

22

Perceptron in Python

23

Perceptron in Python

24

Perceptron in Python

25

Perceptron in Python

26

Scikit-Learn for Perceptron

27

The Best Hyperplane Separator?

• Limitations
• The Perceptron identifies a separating hyperplane if the data is linearly separable.
• However, it merely finds one of the possible solutions.

​

28

The Best Hyperplane Separator?

• Improvements
• Identifying the best hyperplane requires an optimization framework.

​

• Utilize distance information
• Support Vector Machines (SVM) and Logistic Regression

​

29

Support Vector Machine

Distance from a Line

• To build the foundation for understanding SVMs, we will first examine how to compute the distance from a point to a line.

​

31

32

33

34

35

Distance between Two Parallel Lines (1/2)

36

Distance between Two Parallel Lines (2/2)

37

Illustrative Example

38

Decision Making

39

The Key Insight in SVM: Introducing a Margin

40

Scaling to Simplify the Problem

41

Data Generation for Classification

42

Optimization Formulation 1

43

The First Attempt

​

​

​

​

​

​

​

​

​

​

​

• These constraints ensure that all correctly classified points lie outside the margin boundaries, establishing a buffer zone that enhances the classifier's robustness.
• However, the appropriate objective function to be minimized has not yet been determined.

44

CVXPY 1

45

CVXPY 1

46

Outliers

• May fail to produce a valid boundary when the data is not linearly separable

​

• In real-world scenarios, datasets often contain noise, errors, or outliers that deviate from the true underlying patterns
• Linearly non-separable case
• No feasible solution

​

​

​

47

Outliers

​

​

​

​

​

​

​

• No solutions (hyperplane) exist

​

​

• Allowing Misclassifications
• Some training examples are allowed to be misclassified.
• However, the goal remains to minimize the number of misclassified points or, more formally, to minimize the total deviation from the margin constraints

48

The Second Attempt

49

The Second Attempt

• The optimization problem for the non-separable case

50

The Second Attempt

51

Expressed in a Matrix Form

52

CVXPY 2

53

Further Improvement

• Can we do better when there are noise data or outliers?
• Yes, but this makes a buffer zone highly sensitive to noise or extreme points.
• Notice that hyperplane is not as accurately represent the division due to the outlier

​

​

​

​

​

​

​

​

​

• Idea: large margin not only separates the data effectively but also improves the model's generalization on unseen data.

54

Maximize Margin

55

Support Vector Machine

56

In a More Compact Form

57

Scikit-learn

58

Lesson from SVM

• Throughout the development of SVM, we encourage you to recognize the continuous improvement process
• We began with a straightforward linear classifier designed to separate clean, linearly separable data.
• Upon encountering non-separable data due to noise, errors, or outliers, we introduced slack variables to relax the margin conditions, enhancing the model’s robustness.
• To further improve generalization on unseen data, we adopted the concept of a large margin, which maximizes the distance between the decision boundary and the closest data points, making the model more resilient to noise and improving overall performance.

​

• This step-by-step refinement mirrors the natural progression of real-world problem-solving
• Starting with a basic concept, confronting obstacles, and evolving the model to achieve better performance and broader applicability.

59

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

61

Using Distances

62

Using Distances

63

Using Distances

64

Using Distances

65

Using all Distances

66

Using all Distances

67

Using all Distances with Outliers

• SVM vs. Logistic Regression

68

SVM

Logistic Regression

Sigmoid Function

69

Perceptron

SVM

Logistic regression

Sigmoid Function

70

Distance

71

Distance

• Perceptron

72

Distance

• SVM

73

Distance

• Logistic Regression

74

Sigmoid Function

75

Goal: We Need to Fit 𝜔 to Data

76

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

77

Logistic Regression using GD

78

Gradient Descent

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

​

​

​

​

​

​

• We need to compute

​

​

79

Gradient Descent

80

Gradient Descent for Logistic Regression

​

​

​

​

​

​

​

​

​

​

​

​

• Maximization problem
• Be careful on matrix shape

81

Python Implementation

82

Python Implementation

83

Logistic Regression using CVXPY

84

Probabilistic Approach (or MLE)

85

Probabilistic Approach (or MLE)

86

CVXPY Implementation

​

​

​

​

​

​

​

​

87

In a More Compact Form

88

CVXPY Implementation

89

Logistic Regression using Scikit-Learn

90

Logistic Regression using Scikit-Learn

91

Cross-Entropy

92

Multiclass Classification

93

Multiclass Classification: One vs. One

• Generalization to more than 2 classes is straightforward

​

• one vs. one
• For three classes (C₀, C₁, C₂)
• Classifier 1: Distinguishes C₀ vs. C₁
• Classifier 2: Distinguishes C₀ vs. C₂
• Classifier 3: Distinguishes C₁ vs. C₂

​

​

94

Multiclass Classification: One vs. All (One vs. Rest)

• Generalization to more than 2 classes is straightforward

​

• one vs. all (one vs. rest)
• For three classes (C₀, C₁, C₂)
• Classifier 1: Distinguishes C₀ from C₁ and C₂.
• Classifier 2: Distinguishes C₁ from C₀ and C₂.
• Classifier 3: Distinguishes C₂ from C₀ and C₁.

​

​

95

Multiclass Classification: Softmax

96

One-Hot Encoding

97

Non-linear Classification

98

Classifying Non-linear Separable Data

99

Classifying Non-linear Separable Data

100

Classifying Non-linear Separable Data

101

Nonlinear Classification

102

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

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

​

103

Selecting the Appropriate Kernel

• Applying the right kernel enables linear classification to handle nonlinearly distributed data
• But, we have not yet addressed the process of selecting this optimal kernel

​

• Throughout our previous discussions, we assumed that the kernel function was predefined.
• Identifying the suitable kernel for a given dataset remains a non-trivial challenge, but we will not explore this topic further.

​

• The primary reason for this decision is that in deep learning, the model architecture inherently learns effective feature transformations directly from the data.
• Unlike traditional kernel methods, modern deep learning frameworks are capable of automatically discovering complex and data-driven feature mappings, eliminating the need for manually selecting or designing an optimal kernel.

​

104

Classifying Non-linear Separable Data

105

Classifying Non-linear Separable Data

106

Classifying Non-linear Separable Data

107

Non-linear Classification

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

​

108

Explicit Kernel

109

Non-linear Classification

110