Linear Classifiers

The focus shifts from regression, which predicts continuous values, to classification, which predicts discrete or categorical outcomes.

• Regression: Predicts continuous numerical outputs such as house prices or temperatures.
• Classification: Predicts labels or categories such as spam vs. not spam, or disease present vs. absent.

Classification is a supervised learning task that requires a labeled dataset where each input has a corresponding class label.

Examples of Classification Problems

• Binary (2-Class) Classification
  - Binary classification forms the foundation for most classification concepts and algorithms.
  - Involves predicting one of two possible categories. Like:
  - Spam vs. Not Spam
  - Fraudulent vs. Legitimate Transaction
  - COVID Positive vs. Negative
• Multi-Class (k-Class) Classification
  - Many multi-class methods are generalizations of binary classification techniques.
  - Extends binary classification to multiple possible outcomes. Like:
  - Image Recognition → “Car,” “Plane,” “Cat,” or “Dog”
  - Sentiment Analysis → Predicting review ratings from 1 to 5 stars
  - Handwritten Digit Recognition → Classifying digits 0–9 (e.g., MNIST dataset)

Key Challenges in Classification

• Imbalanced Datasets: In many real-world cases, one class heavily outweighs others (e.g., 99.9% negative, 0.1% positive). A model that predicts only the majority class may appear accurate, but it fails at the core objective of detecting rare, critical cases.
• Irrelevant Features: Models can mistakenly focus on features that do not truly influence the outcome (e.g., background patterns in images instead of the actual object), reducing generalization and performance on unseen data.
• Bias in Data: Training on biased or unrepresentative data can lead to unfair or inaccurate predictions, reinforcing existing societal or sampling biases.

History of the Perceptron

The Perceptron was introduced by Frank Rosenblatt in 1958 and is considered the first artificial neural network. It’s a simple binary classifier that sorts inputs into one of two categories: 0 or 1.

A biological neuron inspires the model:

1. Inputs: Dendrites receive multiple input signals (x₁, x₂, ...)
2. Processing: The neuron’s cell body aggregates these signals. Each input has a “weight” (w) determining its importance.
3. Output: If the total, aggregated signal is strong enough, meaning it crosses a certain threshold, the neuron fires, sending an “on” signal (output = 1). If not, it stays “off” (output = 0).

The perceptron

The Mathematical Model

The Perceptron follows this same two-step process:

1. Calculate the Weighted Sum (Aggregation): First, it computes a linear combination of all the input features xᵢ, each multiplied by its corresponding weight wᵢ. A separate bias term (w₀) is also added. This bias isn’t tied to any input; it’s a fixed value that shifts the decision boundary.

D represents the number of input features. If the input vector is x = [x₁, x₂, …, x_D], then D is the total number of these features. Each feature xᵢ has a corresponding weight wᵢ.

xᵢ represents an attribute of the input, wᵢ the corresponding weights and b (often denoted as w₀) the bias term

2. Apply the Step Function (Activation): The summation z is then passed to an activation function to determine the output. It applies a simple rule based on a threshold T:
- If z > T, the model outputs 1.
- Else, the model outputs 0.

Simplifying the Bias and Threshold

The threshold T can be absorbed into the bias term, eliminating the need for a separate threshold.

Original rule

Shift T to the left side:

Define a new bias: b = w₀ − T. The decision rule now becomes:

This simplification makes the model cleaner: the bias alone controls the offset of the decision boundary, and the weighted sum is directly compared to zero.

The perceptron: A neural network with a single neuron.

The Hyperplane is the decision boundary, the line that separates the 0s from the 1s — it is the exact point where the output flips. This happens when the sum is exactly zero:

This equation defines a hyperplane.

• In 2D (like x, y coordinates): The equation w₀ + w₁x₁ + w₂x₂ = 0 is a line.
• In 3D: The equation w₀ + w₁x₁ + w₂x₂ + w₃x₃ = 0 is a plane (Example: 3 + 4x + 5y = 0).
• In D dimensions: A D-dimensional “flat surface” is called a hyperplane.

What does the Hyperplane do?
The perceptron’s only job is to find the one single hyperplane that best separates the data.
This hyperplane cuts the entire feature space into two regions:

1. Positive Region (z > 0): All points on this side of the hyperplane are classified as 1.
2. Negative Region (z < 0): All points on this side are classified as 0.

Therefore, the Perceptron is a linear classifier because it finds a linear boundary (a hyperplane) to make its decisions. The perceptron learns the weights and bias to position this hyperplane optimally, effectively separating the classes in the feature space.

The perceptron laid the foundation for modern neural networks and deep learning. It is simply a neural netwok with a single neuron.

Limitation
The perceptron can only classify data that is linearly separable; it cannot solve problems where classes are not separable by a straight line or hyperplane.

Activation Function

The activation function is a crucial part of a neuron (or perceptron). Its job is to take the “aggregated” or weighted sum (z) of all the inputs and “trigger” a final output.

The activation function, let’s call it f(z), processes this z value to produce the neuron’s final prediction.

Common Activation Functions

1. Step Function (The “Hard” Classifier)
   This was the original activation function used by the Perceptron.
   - It outputs 1 if the input z is greater than or equal to 0, and 0 (or -1) otherwise.
   - This is a “linear classifier” and a “non-probabilistic” classifier. The output is a single, definite decision (“yes” or “no”), with no sense of uncertainty.
2. Sigmoid Function (The “Probabilistic” Classifier)
   This function provides a more nuanced, probabilistic view, which is a key concept in modern machine learning.

e is Euler’s number, the base of the natural logarithm. It is the famous mathematical constant, approximately equal to 2.71828.

The sigmoid function “squashes” the entire range of z (from -∞ to +∞) into a smooth curve that is always between 0 and 1.

• As z → +∞ (positive infinity): The e⁻ᶻ term goes to e⁻∞, which is 0. The formula simplifies to 1 /(1 + 0), so the output approaches 1.
• As z → -∞ (negative infinity): The e⁻ᶻ term goes to e^∞, which is an infinitely large number. The formula becomes 1 / (1 + ∞), so the output approaches 0.
• At z = 0: The e⁻ᶻ term becomes e⁰ = 1. The formula simplifies to 1 /(1 + 1), so the output is exactly 0.5.

3. ReLU (Rectified Linear Unit)
- This is the most popular activation function used in modern deep neural networks. It is computationally very fast and helps solve problems that can occur when training deep networks, making it the standard choice for hidden layers.
- Outputs max(0, z)
- If z is negative (e.g., -5), the output is 0.
- If z is positive (e.g., 5), the output is just 5.

Relu funciton. This is only applicable if we interconnected neurons.

Even though the core of the model is always the same linear equation (z = wᵀx + b), changing the activation function transforms what the model does:
→ Step Function: Produces a hard decision (0 or 1) → classic linear classifier.
→ Sigmoid Function: Produces a probability (0 to 1) → probabilistic classifier.
→ ReLU (max⁡(0,z)): Introduces non-linearity → key building block for deep learning.

Key Insight: Changing the activation function transforms how the same linear core behaves.

We have a model (a single neuron or perceptron) that does two things:

• Aggregates: It computes a weighted sum: z = wᵀx + b
• Activates: It passes this sum through an activation function (like a Step Function or a Sigmoid) to get a final prediction, y_pred.

This leaves us with the most important question: How do we find the best weights w and bias b?

This is where the loss function becomes essential.

Loss Function

Classification of Loss Function

0/1 Loss (Misclassification Loss)

The 0/1 Loss, also known as Misclassification Loss, is the simplest and most intuitive way to measure error for a classification task.

Loss function

It follows a “pass/fail” logic:

• Loss = 0 (Pass): If the prediction (ŷ) is the same as the true label (y).
• Loss = 1 (Fail): If the prediction (ŷ) is not the same as the true label (y).

To get the total loss for the entire dataset, we simply count the total number of misclassifications.
If the model gets 15 predictions wrong, the total loss is 15.

The problem with 0/1 Loss is that it doesn’t tell us how to modify the weights (w) or bias (b) to improve. This is because the function is not differentiable.

Because of this, 0/1 Loss cannot be used with modern optimization methods like gradient descent. This is why Rosenblatt’s Perceptron, which was designed for this loss, had to use its own discrete update rule instead of a “learning” process based on optimization.

Rosenblatt’s Classification Algorithm: Linearly Separable Case (Discrete Classification Algorithm)

It is the discrete classifiaction algorithm

This is the first linear classifier algorithm (the first training algorithm for a neural network). It’s a simple, discrete algorithm for finding the weights (w) of the hyperplane that separates a linearly separable dataset.

The Core Idea: Learn From Mistakes

The algorithm is iterative. It starts with an “initial guess” for the hyperplane (i.e., the weights w) and loops through the data points one by one, “punishing” the model only when it makes a mistake.

The weight vector w is the normal vector of the hyperplane. This vector always points in the direction the model considers “positive.”

The Update Rule

This is the most important part. When the model is wrong, we “nudge” or “tilt” the hyperplane (the normal vector w) to correct its mistake.

Case 1: False Negative (Point is Positive, but we predicted Negative)
- The point is on the wrong side of our line. We need to “pull” the line towards it.
- The Rule: We add the point’s vector to the normal vector.
- w_new = w_old + xₙ (This “tilts” the positive-pointing w vector to be more like xₙ).

Case 2: False Positive (Point is Negative, but we predicted Positive)
- The point is on the wrong side of our line. We need to “push” the line away from it.
- The Rule: We subtract the point’s vector from the normal vector.
- w_new = w_old — xₙ (This “tilts” the positive-pointing w vector away from xₙ).

Perceptron Convergence Theorem

The algorithm keeps looping through all the data points until it can make a full pass without a single misclassification.

The Perceptron Convergence Theorem proves that if the data is linearly separable, this simple algorithm is guaranteed to eventually find a hyperplane that perfectly separates it.

Get Prajun Trital’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

But if the data is not linearly separable, Rosenblatt’s algorithm fails.

Mean Squared Error (MSE) Loss

We need a way to measure how “wrong” our model is. Instead of the 0/1 “pass/fail” loss, the Delta Rule uses Mean Squared Error (MSE).

Mean Squared Error (MSE)

Here,

• ŷₙ is the predicted output for the n-th example. (e.g., z = wxₙ)
• yₙ is the true target value.
• (ŷₙ — yₙ) is the error. Unlike a 0/1 loss, this gives us a continuous error. An answer of 0.8 when the target is 1 is “less wrong” (error = 0.2) than an answer of -0.5 (error = 1.5).
• The factor of 1/2 simplifies the gradient computation.

The goal is to find the weights w that make this total loss L as small as possible.

The Method: The Delta Rule (Widrow-Hoff Rule): Weight Update

The Delta Rule is the process for minimizing the MSE. It uses an algorithm called gradient descent.

Here,

• η is the learning rate, controlling the step size.
• The term (ŷₙ — yₙ) represents the error for the n-th example.
• The update adjusts weights wᵢ in the direction that reduces this error.

The Prediction:
After we have used the Delta Rule to “learn” the best weights w, we can use it to classify new, unseen data. When we do the prediction, we take the sign.

1. Calculate Raw Score: z = wᵀx
2. Classify: ŷ = sign(z) (If the score is positive, predict +1. If it’s negative, predict -1)

Difference between Rosenblatt’s Perceptron (0/1 Loss) and Delta Rule (MSE Loss)

Rosenblatt’s Perceptron (0/1 Loss)
- Discrete loss. Prediction is either correct (0) or wrong (1). “Almost right” counts the same as “completely wrong.”
- 0/1 loss is non-differentiable. Uses discrete update: if wrong, adjust weights abruptly w_new = w_old ± xₙ​

Delta Rule (MSE Loss)
- Continuous loss. Compares raw output ŷₙ = wᵀx​ to true label yₙ​. Squared error gives a smooth signal indicating the magnitude of the error.
- Continuous and differentiable. Uses gradient descent. Updates are proportional to the error, taking small steps to reduce it.

Hinge Loss

Hinge Loss is a “maximum margin” loss function used for binary classification, most famously as the core of Support Vector Machines (SVMs).

The goal isn’t just to be “correct” (like 0/1 Loss); the goal is to be “confidently correct.”

Here,

• y: The true label, which must be -1 or +1 (SVMs require binary labels in this format).
• f(x): The “raw score” from the linear model (f(x) = wᵀx + b). This is not a probability; it’s the raw number before any activation function.

The Core Idea: The “Safety Margin”

The Problem: In a simple linear classifier, the decision boundary is at z=0. A prediction of f(x) = 0.01 would be classified as "+1". While technically correct, it's "too risky" and very close to being wrong.

The Hinge Loss Solution: Hinge Loss introduces a “safety margin” of 1 on either side of the boundary. It’s not enough to be on the right side of 0; you must be on the right side of 1 or -1.

The Goal: Finding the Best Decision Boundary

For any dataset that can be separated by a line (linearly separable), there are infinitely many possible lines that can do it.

• The Perceptron Algorithm (using 0/1 Loss) finds any of those lines. It might be dangerously close to the data.
• The Hinge Loss (used by SVMs) finds the one best line.

The figure on the left illustrates that for any linearly separable dataset, there are infinitely many possible decision boundaries (black lines) that can perfectly separate the two classes (blue and purple points). The figure on the right, however, shows the goal of a maximum margin classifier like an SVM, which is not to find just any line, but to find the single best one. This optimal boundary is the line that is as far as possible from the closest points of both classes, creating the largest “margin” and leading to a more robust model.

This figure illustrates the optimal solution to the problem of infinite boundaries: the maximum margin classifier. A Support Vector Machine (SVM) finds the one unique decision boundary (solid line) that maximizes the “margin” (the region between the dashed lines). This margin is defined by the closest points from each class, known as the “support vectors” (indicated by the arrows), creating the widest possible “street” to separate the data and ensure the most robust classification.

Fisher’s Discriminant Analysis (FDA)

FDA, also known as Linear Discriminant Analysis (LDA), is a classic linear classifier. Its primary goal is to find a way to reduce the dimensionality of the data (e.g., squashing 2D, 3D, or higher-dimensional data onto a single 1D line) in a way that makes the classes as “separate” as possible.

The Core Idea: Optimal Projection

Imagine a 2D scatter plot with two classes of data. FDA finds the perfect “angle” to project or “squash” all these points onto a single line.

The “best” line is the one that achieves two goals at the same time:

1. Maximizes Between-Class Distance: It pushes the centers (means) of the two classes as far apart from each other as possible.
2. Minimizes Within-Class Spread: It tries to make the “clump” or “spread” (variance) of each individual class as tight and narrow as possible.

This image visualizes Fisher’s Discriminant Analysis (FDA), a linear classifier that works by performing dimensionality reduction. It takes the 2D data (the scattered blue and red dots) and projects, or “squashes,” every point onto a single, optimally chosen 1D line (the dashed black line). This line is specifically chosen to maximize the separation between the two classes by maximizing the distance between the projected class means (the centers of the red and blue histograms) while simultaneously minimizing the variance, or spread, within each class (making each histogram as narrow as possible). If we were to project the data onto a different, sub-optimal line (like a vertical one), the two projected histograms would significantly overlap, making it impossible to separate them. This optimal projection, however, transforms the 2D problem into a simple 1D problem where a single threshold can easily separate the two classes.

Once we define these two goals, the task of finding the best projection vector w becomes a formal optimization problem. The challenge is to combine these two competing objectives (maximizing one thing while minimizing another) into a single mathematical function that we can then solve.

Lagrange multipliers are a standard method used to solve the optimization problem in Fisher’s Discriminant Analysis (FDA). Lagrange multipliers are a technique for finding the maximum or minimum of a function subject to one or more constraints.

Class Means and Scatter Matrices

Class Means and Scatter Matrices

This figure illustrates the concepts of class means and scatter matrices for a multi-class scenario, essential for methods like FDA. The points μ₁, μ₂, μ₃ represent the means or centroids of the three distinct classes (red, green, blue). The ellipses and arrows labeled S_{W1}, S_{W2}, and S_{W3} depict the within-class scatter for each group, measuring how spread out the data points are within their respective classes around their own mean. Conversely, the arrows labeled S_{B1}, S_{B2}, and S_{B3} represent the between-class scatter, indicating how far apart each individual class mean is from the overall global mean (μ) of all data points, thus measuring the separation between the classes.

Mean Vectors (m₁, m₂): These are simply the center points (average positions) of all the data points belonging to Class 1 (C₁) and Class 2 (C₂), respectively. Think of them as the “middle” of each cluster.

Scatter Matrices (S₁, S₂):

• S₁ measures how spread out the points in Class 1 are around their own center (m₁).
• S₂ measures how spread out the points in Class 2 are around their own center (m₂).

Essentially, these matrices capture the size and shape of the data cloud for each class. A large scatter matrix means the points in that class are widely dispersed, while a small scatter matrix means they are tightly clustered together. In the FDA, the goal is to find a projection that makes this within-class scatter as small as possible. ✨

Finding the Optimal Projection for FDA

1. Defining the “Scatter” (How Spread Out the Data Is)

Within-Class Scatter (S_W): This measures how spread out the data points are within their own class.

• We first calculate S₁ and S₂, which measure the spread of Class 1 around its mean (m₁) and Class 2 around its mean (m₂).
• The total within-class scatter is just the sum: S_{W} = S₁ + S₂
• Goal: We want this to be small when projected. Tight clusters are good.

Between-Class Scatter (S_B): This measures how far apart the centers (means) of the two classes are from each other.

• It’s calculated based only on the means: S_B = (m₁ — m₂)(m₁ — m₂)ᵀ.
• Goal: We want this to be large when projected. Far-apart centers are good

2. Measuring Scatter Along the Projection (w)

Now, we see how these scatter measures look when projected onto our chosen direction, w.

Projected Between-Class Scatter (wᵀ S_B w): This single number tells us how far apart the projected means of the two classes are along the line w. We want to maximize this.

Projected Between-Class Scatter

Projected Within-Class Scatter (wᵀ S_W w): This single number tells us the total spread (sum of variances) of the projected points within each class along the line w. We want to minimize this.

Projected Within-Class Scatter

3. The Objective Function: Fisher Criterion J(w)

To achieve both goals simultaneously, we create a single objective function, the Fisher Criterion J(w), which is a ratio:

Our goal is to find the direction w that maximizes this ratio J(w). Maximizing this ratio means we are finding a projection that makes the classes far apart (wᵀS_B w is large) relative to how spread out they are (wᵀS_W w is small).

4. Finding the Maximum: Using the Gradient

To find the w that maximizes J(w), we use calculus:

1. Take the gradient (derivative) of J(w) with respect to w. This tells us the “slope” of the function.
2. Set the gradient equal to zero (∇_w J(w) = 0). The point where the slope is zero is the maximum (or minimum).

Setting the gradient to zero to maximize J(w).
Note that, (wᵀ S_W w) and (wᵀ S_B w) are both numbers.
We obtain

Where λ is related to the value of J(w) at the maximum.

5. Solving for w: The Generalized Eigenvalue Problem

The equation S_B w = λ S_W w is called a generalized eigenvalue problem. We need to solve it for w.

We can rearrange it (assuming S_W is invertible):

This equation tells us something amazing:

• The optimal direction w is an eigenvector of the matrix S⁻¹_W S_B.
• The value λ is the corresponding eigenvalue.

6. The Final Solution and Intuition

For the two-class case, the matrix S_B has only rank 1 (it’s based only on the difference between two means). This simplifies the problem significantly.

🔙 Back to all notes
𝕏 Let’s Connect

Backlinks:
Machine Learning