Maximum margin classifiers

• Also known as optimal separating hyperplane
• Margin is the distance between hyperplane and closest training data point
• We want to select a hyperplane for which this distance is maximum
• Once we identify optimal separating hyper plane there can be many equidistance training points with the shortest distance from hyperplane
• Such point are called support vectors
  • These points support the hyperplane in a sense that if they are moved slightly optimal hyperplane will also move

Training

• Equation 9.10 ensures that left hand side of equation 9.11 gives perpendicular distance from the hyperplane
• Equation assumes y has two values (+1) and (-1)

Support Vector classifier

• Maximum margin classifier does not work when supporting hyperplane does not exist.
• Support vector classifier relaxes optimization objective to get that work
• Unlike maximum margin classifier this one is less prone to overfit as well
  • The formal one is very sensitive to change in single observation
• Also know as soft margin classifier

• ε variable allows training point to be on wrong side of margin
  • If ε > 0 it is on the wrong side of margin
  • If ε > 1 it is on the wrong side of hyperplane
• Parameter C is the budget that constraints how many points are allowed on wrong side of hyperplane
• C is selected with cross validation and controls bias variance trade off
• Point that lies directly on the margin or on the wrong side of margin for their class are called support vectors
  • Because these points affects the choice of hyperplane
  • And this is the property which makes it robust to outliers
    • LDA calculates mean of all the observation
    • However LR is less sensitivity to outliers
• Computation note – when we try to solve above optimization problem with lagrange multiplier we found that it depends on dot product of training samples
  • This will be very important when we discuss support vector machine in next section
  • Dot product is only with support vector, both while training and while solving [1]

Support vector machine

• Above two classifier does not work when desired decision boundary is not linear

• One solution is to create polynomial features (as we generally do for LR)
• But fundamental problem with this approach is that how many and which terms you should create
• Also creating large number of feature raises computational problem

• For the case of SVM, that fact that it involved only dot product of observation allows us to perform kernel trick.
• Kernel acts as similarity function
• Above equation makes it clear that we are not calculating(and storing) higher order polynomial still taking the advantage of it
• Second one is polynomial kernel and last one is radial kernel
• This video shows visualization of kernel trick

Multiclass SVM

• One vs all and one vs rest is used for multiclass classification using SVM

 Hinge Loss

• Loss is 0 for w*x which are not support vectors
• Look at equation 9.14 and 9.15 above
  • Looking at its property episilon, it relates to hinge loss
  • Yet to check it in SVM lagrange solution though
• In hinge loss also we would predict +1 if w*x > 0 else -1
• Why not keep boundary at 0
  • This can make w a zero to make positive training example right
  • Zero parameter vector would mean while prediction we would always get 0
    • Because prediction is w*x
    • This makes it difficult to assign labels during prediction
  • We keep boundary away from 0 to make zero we don’t get 0 parameter vector

References

[0] : An Introduction to Statistical Learning – http://www-bcf.usc.edu/~gareth/ISL/

[1] : https://towardsdatascience.com/understanding-support-vector-machine-part-2-kernel-trick-mercers-theorem-e1e6848c6c4d

Few Points:

• LR model probability with logistic function
• LDA models probability with multivariate Gaussian function
• LR find maximum likelihood solution
• LDA find maximum a posterior using Bayes’ formula

When classes are well separated

When the classes are well-separated, the parameter estimates for logistic regression are surprisingly unstable. Coefficients may go to infinity. LDA doesn’t suffer from this problem.

LR gets unstable in the case of perfect separation

If there are covariate values that can predict the binary outcome perfectly then the algorithm of logistic regression, i.e. Fisher scoring, does not even converge.

If you are using R or SAS you will get a warning that probabilities of zero and one were computed and that the algorithm has crashed.

This is the extreme case of perfect separation but even if the data are only separated to a great degree and not perfectly, the maximum likelihood estimator might not exist and even if it does exist, the estimates are not reliable.

The resulting fit is not good at all.

Math behind LR

For example suppose y = 0 for x=0 and y=1 for x = 1. To maximize the likelihood of the observed data, the “S”-shaped logistic regression curve has to model h(Θ) as 0 and 1. This will lead β to reach infinite, which causes the instability.

Few terms:

Complete Separation – when x completely predicts both zero and 1

Quasi-Complete separation – when x completely predicts either 0 or 1

When can LDA fail

It can fail if either the between or within covariance matrix(Sigma) is singular but that is a rather rare instance.

In fact, If there is complete or quasi-complete separation then all the better because the discriminant is more likely to be successful.

LDA is popular when we have more than two response classes, because it also provides low-dimensional views of the data.

In the post on LDA, QDA we had said that LDA is generalization of Fisher’s discriminant analysis (which involves project data on lower dimension to that achieves maximum separation).

LDA may result in information loss

The low-dimensional representation has a problem that it can result in loss of information. This is less of a problem when the data are linearly separable but if they are not the loss of information might be substantial and the classifier will perform poorly

Another assumption of LDA that it assumes equal covariance matrix for all classes, in which case we might go for QDA. Blog post on LDA, QDA list more consideration about the same.

References

https://stats.stackexchange.com/questions/188416/discriminant-analysis-vs-logistic-regression#

Click to access separation.pdf

Click to access Classification_HDD.pdf

{In practice it is used more for classification than for regression}

This resemble gaussian mixture models in that you git one gaussian for each class. 
Don't forget one important difference though. LDA is supervised, Mixture models are unsupervised.

Linear Discriminant Analysis (LDA)

In logistic regression (LR), we estimate the posterior probability directly. In LDA we estimate likelihood and then use Bayes theorem. Calculating posterior using bayes theorem is easy in case of classification because hypothesis space is limited.

Equation 2 computes probability of class k given x. This is a posterior instead of just point estimates.

Equation 4 is derived from equation 3 only. Probability(k) would be highest for the class for which Delta(k) will be highest.

LDA estimates mean and variance from data and uses equation 4 for classification.

We also need to estimate π_k, which I think would be n_k/N.

Assumptions made:

• f(x) is normal
• Variance(sigma) is same for all classes

When more than one predictor, we go for multivariate gaussian

Some comparisons

• Compare this with mixture models, where there is a responsibility vector for each sample
  • There labels are not available (unsupervised learning) and hence is solved by EM (Expectation Maximization)
• Compare this with naive bayes, there assumption is each feature is independent
  • Here we have parameter for each (class, feature), there we have parameter for each feature
  • Also here f captures probability of class (k) given x, there after bayes rules we calculate probability of x given class k
  • Hence the name naive bayes
  • Here we have joint distribution (multivariate gaussian, there it is independent distribution for each features)
  • Both LDA and navie bayes try to calculate posterior while logistic regression maximizes likelihood function

Quadratic Descriminant Analysis (QDA)

Unlike LDA, QDA assumes that each class has its own covariance matrix. It is called quadratic because below function is quadratic of x.

When to use LDA, QDA

• This is related to bias variance trade-off
• For p predict and k classes
  • LDA estimates k*p parameters
  • QDA estimates additional k*p*(p+1)/2 parameters
• So LDA has much lower variance and classifier built can suffer from high bias
• LDA should be used when number of training sample are less, because we want to avoid high variance problem
• QDA has high variance, so it should be used when number of training samples are more
  • Another scenario would the case when common covariance matrix among K classes is untenable

A note on Fisher’s Linear Discriminant Analysis

• It is simply LDA in case of two classes.
• We can derive this similarity mathematically.
• In literature we found it from the perspective that it project data on a line which achieves maximum separation
• We can state without loss of generality that LDA also provides low dimensional view on data

Math

• We want to project 2-D data on a line which
  • maximizes the difference between projected mean
  • minimizes within class variance
• Such a direction can be found by maximizing fisher criterion (J)

Edit : Extended post is available here

TLDR

• Accuracy does not help with class imbalance
  • Use precision / recall based on use case, needs threshold tuning
• Two types of AUC
  • ROC-AUC for balanced dataset
  • PR-AUC for imbalanced dataset
• Used because its threshold independent
  • model selection
  • threshold selection
  • drift detection ( calculate AUC from production log and track )
• F score to balance both precision and recall
  • Again at some threshold
  • In multi class we have
    • Macro F1 score – PR for each class -> F1 for each -> average
      • When you care about minority classes
      • E commerce customer support classification – general / refund / legal
      • Medical diagnosis – rare disease 1, rare disease 2, general disease
    • Micro F1 score – Get TP, FP for each class and sum to fill the metrics
      • We are going at micros level -> TP, FP for each class
      • overall dataset accuracy is main priority
      • classifier to predict user’s genre for book e-commerce – fiction, fitness, aviation
        • Goal is overall CTR
    • Weighted F1 manly assigns weight to each individual F1
      • Macro assigns same weight by taking average
• Normalized entropy
  • When business needs calibrated probabilities ( uses cross entropy )
  • normalized by true CTR (0,1) range easy to compare
  • Threshold independent

Some Scenarios

• In finance default is failure to meet the legal obligation of loan. Given some data we want to classify whether the person will be defaulter or not.
  • Suppose our training data-set is imbalanced. Out of 10k samples only 300 are defaulters. (3%)
  • Classifier in the following table is good at classifying non defaulters but not good at classifying defaulters (which is more important for credit card company)
  • Assume what if out of 300 defaulters 250 are classified as non defaulters and given the credit card
• Doctors want to conduct a test whether a patient has cancer or not.
  • Popular terms in medical field are sensitivity and specificity
  • Instead of trying to classify person as defaulter, here we classify if patient has cancer.
  • Sensitivity = 81/333 = 24 %
  • Specificity = 9644/9667 = 99 %
  • Every medical test thrives to achieve 100% in both sensitivity and specificity.
• In information retriever we want to know how many % of relevant pages we were able to retrieve.
  • TP = 81
  • FP = 23
  • TN = 9644
  • FN = 252
  • Precision = 81/104= 77%
  • Recall = 81/333= sensitivity = 24%

Example

• Formulas:
  • Precision = TP/(TP+FP)
  • Recall = TP/(TP+FN)
  • Sensitivity = TP/(TP+FN)
  • Specificity = TN/(TN+FP)
  • Recall and sensitivity are same

Solution is to change the threshold

• Earlier we were assigning person to default if probability is more than 50%
• Now we want to assign more person as defaulter
• So we will assign them to defaulter when probability is more than 20%
• This will incorrectly classify non-defaulters to defaulters but that is less concerned compared to assigning defaulter to non-defaulter
  • This will also increase the overall error rate, which is still okay

ROC-AUC

• We can always increase sensitivity by classifying all samples as positive
• We can increase specificity by classifying all samples as negative
• ROC plot (sensitivity) vs (1-specificity)
  • That is TP vs FP
  • And also precision vs recall
• ROC = Receiver operating characteristic
• It is good to have ROC curve on top left
  • Better classifier
  • Accurate test
• And ROC curve close to 45 degree represents less accurate test
• AUC = Area Under Curve
  • Area under ROC curve
• Ideal value for AUC is 1
• AUC of 0.5 (45 degree line) represents a random classifier
• AUC = P(score of a random positive > score of a random negative )
  • 0.5 => random, 1 => perfect seperation
  • Its scale invariance
    • Any monotonic transform ( multiply by 1.4, log ) preserves parities comparison

How to plot ROC?

• Change the probability threshold from 0 to 1 and measure sensitivity and specificity. If specificity keeps on decreasing ((100-specificity) keeps on increasing) as sensitivity increase it is a bad classifier.
• For random classifier ROC is 45 degree line
  • You draw random number between (0, 1)
  • Classify it based on threshold
  • So threshold is there
  • But while building classifier we want to do better than drawing random probability between (0, 1). We also want to consider features into account while drawing between (0, 1)
• Can AUC be less than 0.5? I don’t think so.
  • Complementing the output will bring it to other side of line anyway.
• What if I classified all of them as positive?
  • That means you are taking all 1. You can not plot ROC with that.

Threshold selection

• Unless there is special business requirement (as in credit card defaulters) we want to select a threshold which maximizes TP while minimizing FP
• There are two methods to do that:
  • Point which is closest to (0, 1) in ROC curve
  • Youden Index
    • Point which maximizes vertical distance from line of equality (45 degree line)
    • We can derive that this is the point which maximizes (sensitivity + specificity)

AUC vs overall accuracy as comparison metric

• AUC helps us understand how much our classifier is away from random guess, which accuracy can not tell
• Accuracy is measured at particular threshold while AUC requires moving threshold from 0 to 1

PR-AUC

PR-AUC (Precision-Recall Area Under the Curve) summarizes a classifier’s performance by plotting Precision against Recall across all thresholds. You should use it when your data has a severe class imbalance (e.g., < 5% positive class) and your primary goal is to minimize False Positives and False Negatives within that rare target group

• While training on the model, you can take a look at PR-ROC. Once you have found your best model, you can pick up any point based on the business needs.
• A random classifier always gives ROC AUC to be 0.5.
  • Our ROC would be the percentage of positive samples.
  • This helps with the cases where there is highly class imbalance and we have more negative samples.

F score

• We know that recall and sensitivity are same, but precision and specificity are not same
• While medical field is more concerned about specificity, information retrieval is more concerned about precision
• So they came up with F score which is harmonic mean of precision and recall
• AUC helps us maximizing sensitivity and specificity simultaneously while F score helps us maximizing precision and recall simultaneously
• Beta in f score helps providing weight to precision and recall.
• Harmonic mean can not be made arbitrarily large while changing some values to bigger one and leaving at least one unchanged. It is maximizes when all elements are increased.
  • x = 0, y = 1 will give 0.5 in arithmetic mean but is zero for harmonic mean

Micro and Macro F1 Score

The Core Difference

When dealing with multi-class classification (predicting three or more categories, like Cat, Dog, or Bird), you calculate an F1-score for each individual class. To get a single final score for the whole model, you must aggregate them:

• Macro F1 treats all classes equally. It calculates the F1-score for each class independently and takes the unweighted average. It is excellent for flagging if a model performs poorly on a rare, minor class.
  • We can also cut on domain dimension like
    • head/tail query
    • Video popularity decile
    • Matrix of trigger popularity decile x video popularity decile
• Micro F1 treats all samples equally. It pools the True Positives (TP), False Positives (FP), and False Negatives (FN) from all classes together, then computes a global F1-score. It is heavily influenced by the performance of the majority class.

Step-by-Step Example

Let’s say we have an image classification model evaluating 100 test images across three categories. The dataset is highly imbalanced:

• Cat: 80 images
• Dog: 15 images
• Bird: 5 images

After running our model, we track the True Positives (TP), False Positives (FP), and False Negatives (FN) for each class:

(Note: Our model does great on Cats, decent on Dogs, but terrible on Birds because Birds are rare.)

1. Calculating Macro F1

Macro F1 is simply the straightforward average of the individual class F1-scores.

• Why it matters: The score drops to 0.61 because it treats the Bird class with the exact same weight as the Catclass, exposing the model’s failure on rare data.

2. Calculating Micro F1

Micro F1 aggregates the counts of all raw outcomes across the entire dataset first.

• Total TP = 75 + 10 + 1 = 86
• Total FP = 10 + 5 + 2 = 17
• Total FN = 5 + 5 + 4 = 14

Using these global metrics, we calculate overall Precision and Recall:

• Why it matters: The score is a high 0.85 because the model correctly classified most of the dataset (the 80 Cats), effectively masking the fact that it completely failed at identifying Birds.

Summary Guideline

• Use Macro F1 when you care about minority classes and want to ensure the model performs well across every single category equally.
• Use Micro F1 when overall dataset accuracy is your main priority, and you are comfortable with minor classes having a negligible impact on the final score.

Normalized Entropy

To understand Normalized Entropy (NE), let’s use a simple example of a model predicting whether a user will click an ad.

In this metric, lower values are better. A score of 1.0 means your model is no better than a random guess based on the background average, while 0.0 means perfect predictions.

Step 1: The Dataset (20 Rows)

Suppose we have 20 ad impressions. 5 resulted in a click (1), and 15 did not (0).

• Actual outcome (y_true): [1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0]
• Background Click Rate (p): 5 clicks out of 20 = 0.25 (25%)

Step 2: The Core Calculations

We need to calculate two things using the standard Cross-Entropy formula:
entropy = -sum(y log y + (1-y) log (1-y`) ) / N

1. Baseline Entropy (The Naive Guess)

If we didn’t have a machine learning model, our safest guess for every single row would just be the background average (0.25).

• Calculating entropy using $\hat{y} = 0.25$ for all 20 rows yields a Baseline Entropy of 0.5623.

2. Model Entropy (Our Actual Predictions)

Now, let’s look at what our actual ML model predicted (y_pred) for those same 20 rows:

• [0.60, 0.10, 0.20, 0.10, 0.70, 0.30, 0.10, 0.40, 0.20, 0.10, 0.05, 0.10, 0.80, 0.20, 0.10, 0.30, 0.10, 0.20, 0.50, 0.10]
• Notice how it assigns higher probabilities to the actual clicks (like 0.60, 0.70, 0.80).
• Calculating entropy using these specific predictions yields a Model Entropy of 0.2600.

Step 3: Normalizing the Score

To find the Normalized Entropy, we divide the model’s entropy by the baseline entropy:

NE = (model entropy) / ( baseline entropy ) = 0.2600 / 0.5623 = 0.4624

What does this result mean?

• 0.4624 is less than 1, which proves the model is actively adding value.
• By subtracting this from 1 ($1 – 0.4624 = 0.5376$), we can conclude that our model reduces uncertainty by roughly 53.8% compared to a naive baseline guess.

import numpy as np
# Let's simulate a dataset of 20 rows (between 10 and 50)
# Binary classification context (e.g., Click vs No Click)
# Let's assume a background positive rate (p) of 0.25 (5 clicks out of 20)
np.random.seed(42)
y_true = np.array([1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0]) # 5 ones, 15 zeros
# Let's create some predicted probabilities from a dummy model
y_pred = np.array([0.6, 0.1, 0.2, 0.1, 0.7, 0.3, 0.1, 0.4, 0.2, 0.1, 0.05, 0.1, 0.8, 0.2, 0.1, 0.3, 0.1, 0.2, 0.5, 0.1])
# Calculate Cross Entropy (CE) of the model
# CE = -1/N * sum(y*log(p) + (1-y)*log(1-p))
def cross_entropy(y_true, y_pred):
    epsilon = 1e-15
    y_pred = np.clip(y_pred, epsilon, 1 - epsilon)
    return -np.mean(y_true * np.log(y_pred) + (1 - y_true) * np.log(1 - y_pred))
ce_model = cross_entropy(y_true, y_pred)
# Background/baseline prediction (average of y_true)
p_baseline = np.mean(y_true)
y_baseline = np.zeros_like(y_true) + p_baseline
ce_baseline = cross_entropy(y_true, y_baseline)
# Normalized Entropy (NE) = CE_model / CE_baseline
ne = ce_model / ce_baseline
print(f"p_baseline: {p_baseline}")
print(f"CE model: {ce_model:.4f}")
print(f"CE baseline: {ce_baseline:.4f}")
print(f"NE: {ne:.4f}")

References

Assessing and Comparing Classifier Performance with ROC Curves

Click to access roccurve.pdf

https://www.medcalc.org/manual/roc-curves.php

https://en.wikipedia.org/wiki/F1_score

An Introduction to Statistical Learning – http://www-bcf.usc.edu/~gareth/ISL/

https://stats.stackexchange.com/questions/221997/why-f-beta-score-define-beta-like-that

https://en.wikipedia.org/wiki/Harmonic_mean

Hypothesis

We want a hypothesis that is bounded between zero and one, regression hypothesis line extends beyond this limits. Hypothesis here also represents probability of observing an outcome.

Hypothesis by ISLR and Andrew N.G :

Odds and log-odds/logit

Log of odd is also called logit. So above is logit(p(x)) = b0 + b1X.

In terms of GLM we call it a logic link function. Logit has a property of broadcasting [0,1] range to [-inf, inf]. Log does not have that property.

In regression beta1 given average change in y for unit change in x. But here it says unit increase in x changes log-odds by beta1. It multiplies odds by exp(beta1) and hence depends on current value of odds and therefor is not linear.

Cost Function

For ISLR perspective it is likelihood that we want to maximize.

Andre N.G looks it from the perspective of modifying cost function of linear regression.

As we can see that Andrew N.G cost function is same as maximizing log likelihood of ISLR.

Least square in case of linear regression is special case of maximum likelihood. We know that derivation where we assume likelihood to be gaussian.

Logistic Regression For well separated classes

MLE estimation becomes unstable when classes are well separated. While this is acceptable for classification tasks, it is not ideal for risk estimation. Regularization techniques can help avoid this instability. Support Vector Machines (SVM) also perform well for well-separated classes. As shown in figure below[1], the intercept of the sigmoid function reaches -inf, and the slope reaches inf. This allows the slope to come from an infinitely weighted feature.

Why Can’t we use square loss ?

• Labels (+1, and -1)
• Prediction : +1 when w*x > 0 else -1
• Consider scenario [2]
  • label +1
  • w*x = 100
  • Prediction is correct
  • Still we add it to loss (100-1)^2
• Solutions are hinge loss and logistic loss

• Why is not logistic loss not 0 for correct prediction ?
  • There are more training samples. We want to find parameter such that it balances all of them
  • If we make it 0 positive examples would no longer contribute to loss (like SVM)
    • That’s why hinge loss create support vectors. More about that on SVM’s blog post
  • Also this is the property which will make coefficient higher for well separated classes
    • To control that we use regularisation
    • Regularisation is while training, not while prediction, we are just changing loss function
    • Predict is still +1 is w*x > 0 else -1

Why can’t we use step loss ?

• When we are incurring loss, we also want to know which direction to go to reduce loss.
• Gradient/slope is what provide this information. [2]
• Step loss (0-1) has zero gradient

Reference

[1] https://stats.stackexchange.com/questions/254124/why-does-logistic-regression-become-unstable-when-classes-are-well-separated

[2] Notes of different loss function is taken from Mike Galbart’s course – https://github.com/UBC-CS/cpsc340/blob/master/lectures/L19demo.ipynb