The Hong Kong University of Science and Technology · FACULTY OF COMPUTER SCIENCE

MAIE5421 Chap.4 Logistic Regression, k-NN and Naive Bayes

- one subject, every graph, every model, every mark
8 Chapters4-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 4 of 10 · MAIE5421

Logistic Regression, k-NN and Naive Bayes

Logistic regression: a linear score made into a probability

Logistic regression is the lecture's first classifier for a binary target. It passes a score through the logistic function, an S-shaped curve controlled by a location parameter, where the output crosses one half, and a scale parameter, which sets how steeply it climbs.

The output always lies between 0 and 1 and is read as the probability of the positive class. The lecture points out that the parameters cannot be estimated by ordinary least squares; maximum likelihood estimation is used instead.

A threshold on the probability then turns it into a class decision.

k-nearest neighbours: prediction by local vote

k-NN keeps the whole training set and labels a new sample by a majority vote among the k training samples closest to it. It is described as simple, non-parametric and lazy, because no model is fitted before prediction.

A small k follows individual points and is sensitive to noise; a large k smooths the decision but can admit voters from other classes, and cross-validation is the recommended way to choose. Euclidean distance, Manhattan distance and cosine similarity are the measures taught.

Its drawbacks are the cost of comparing each new sample with every stored one and its inability to distinguish relevant features from irrelevant ones.

Naive Bayes: evidence combined through Bayes' theorem

Bayes' theorem gives the posterior probability of a class from the likelihood of the data under that class, the prior probability of the class and the marginal probability of the data.

The lecture's medical-test example shows how a prior of 2%, a true-positive rate of 99% and a marginal positive rate of 2.01% combine into a posterior of 98.5%. Computing the joint likelihood of many features is hard, so naive Bayes assumes the features are independent given the class and multiplies one likelihood per feature.

Priors come from counting labels, and continuous likelihoods come from parametric models such as the Gaussian, which means the resulting class scores are densities and need not sum to one.

In this chapter

What this chapter covers

  • 01

    Five typical supervised classifiers

  • 02

    The logistic function, its location and scale

  • 03

    Maximum likelihood rather than least squares

  • 04

    The k-NN algorithm and majority voting

  • 05

    Choosing k and the effect of smoothing

  • 06

    Euclidean, Manhattan and cosine measures

  • 07

    Bayes' theorem: prior, likelihood, marginal and posterior

  • 08

    The naive independence assumption and Gaussian likelihoods

Worked example · free

Read probabilities and decisions off a logistic curve

Q [7 marks]. AskSia-authored practice. A logistic model has location parameter 2 and scale parameter 0.5. Compute the probability of class 1 at inputs 1, 2, 2.5 and 3, classify each input with a threshold of one half, and say what happens to the curve if the scale is reduced to 0.25. The marks shown are an AskSia study allocation and are not the University's marking scheme.
The logistic curve with location 2 and scale 0.5.The logistic curve with location 2 and scale 0.5. The probability is exactly one half at the location parameter, and the green and red points show that inputs one unit either side give 0.88 and 0.12.p(3) = 0.88p(1) = 0.12p(μ) = 0.510Input score xProbability of class 1
The logistic curve with location 2 and scale 0.5. The probability is exactly one half at the location parameter, and the green and red points show that inputs one unit either side give 0.88 and 0.12.
  • 2At x = 1 the exponent is -(1 - 2) / 0.5 = 2, so p = 1 / (1 + e^2) = 0.119.
  • 3At x = 2 the exponent is 0, so p = 1 / 2 = 0.500; at x = 2.5, p = 1 / (1 + e^-1) = 0.731; at x = 3, p = 1 / (1 + e^-2) = 0.881.
  • 1Classify: x = 1 gives class 0; x = 2.5 and x = 3 give class 1; x = 2 sits exactly on the boundary.
  • 1Halving the scale doubles the steepness, so the curve switches from near 0 to near 1 over half the distance.
The probabilities are 0.119, 0.500, 0.731 and 0.881. With a threshold of one half, the input of 1 is class 0, the inputs of 2.5 and 3 are class 1, and the input of 2 lies on the decision boundary, which for a single input always sits at the location parameter. The values at 1 and 3 add to exactly one, as they must for points equally far either side of the location. With a scale of 0.25 the same inputs give 0.018 at 1 and 0.982 at 3, a much sharper switch.
Sia tip — Check any logistic answer with symmetry: probabilities at equal distances either side of the location parameter must add to one.
Glossary

Key terms

Logistic Function
The S-shaped function that maps any real score to a value between 0 and 1, used to output a class probability.
Location Parameter
The input value at which a logistic curve crosses one half, which is the decision boundary at the usual threshold.
Maximum Likelihood
Estimation that chooses the parameters under which the observed data are most probable, used to fit logistic regression.
Lazy Learning
Learning that builds no model in advance and does its work at prediction time, as k-NN does by searching the stored samples.
Manhattan Distance
The sum of absolute differences between two vectors, also called the L1 norm of their difference.
Cosine Similarity
The cosine of the angle between two vectors, which compares their directions and ignores their lengths.
Prior Probability
The probability of a class before any evidence about the sample is seen.
Posterior Probability
The probability of a class after the evidence is taken into account, given by Bayes' theorem.
FAQ

Logistic Regression, k-NN and Naive Bayes FAQ

Why can logistic regression not be fitted by least squares?

Because its output is a probability passed through a non-linear curve and its targets are class labels, so squared error is not the natural measure of fit and does not give a convenient closed-form solution. The lecture states that maximum likelihood estimation is used instead, choosing the parameters under which the observed labels are most probable, and leaves the details to advanced courses.

How should I choose k in k-nearest neighbours?

Treat it as a tuning parameter and choose it by cross-validation, as the lecture recommends. A very small k reacts to individual points, so noise and mislabelled samples change predictions. A very large k averages over a wide neighbourhood and starts counting votes from other classes. For two classes, an odd k also avoids tied votes.

Why is naive Bayes called naive?

Because it assumes every feature is independent of every other feature once the class is known. That assumption is rarely exactly true, for example neighbouring pixels are strongly related, but it turns one hard joint likelihood into a product of simple per-feature likelihoods. The simplification is what lets naive Bayes work with small training sets and compute quickly.

Study strategy

Assessment move

Work one problem with each method on the same tiny dataset: compute a logistic probability, a k-NN vote at two values of k and a naive Bayes posterior. Seeing three different answers to one question makes the assumptions behind each method concrete, and it is the comparison an assignment is most likely to ask you to explain in words.

Working through Logistic Regression, k-NN and Naive Bayes in MAIE5421? Sia is AskSia’s AI Computer Science tutor — ask any MAIE5421 Logistic Regression, k-NN and Naive Bayes question and get a clear, step-by-step explanation grounded in how MAIE5421 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.

A+Everything unlocked
Unlocks this Bible + all 13 of your subjects at The Hong Kong University of Science and Technology, plus 1,000+ more Bibles across the AskSia library.
Sia - your MAIE5421 tutor, unlimited, worked the way the exam marks it
The full 4-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works