Lecture 1: Introduction

Motivating Question: Dog Breed Classifier

Given a photo → output the breed (Corgi, Black Lab, Pomeranian, Tibetan Mastiff…)
Writing rules by hand is hard → if fur_color == black: if has_floppy_ears: ... never ends
ML approach → show the algorithm lots of labeled photos, it learns from feedback

Key Ideas in ML

ML models map inputs → outputs
- Image pixels → object in the image
- Speech signal → word
- Text → prediction about the text
Models are learned rather than designed
- Traditional AI / science → hand-designed models
- ML → models learned from data
Ideal for problems with a lot of data and little theory
Applications → phones (speech recognition, face/fingerprint unlock, autocomplete), cars, government (building footprints from aerial images), counting trees, medicine, generation (ChatGPT poems, “oil painting of a cat in a wizard hat”)

ML vs Classical AI

Classical AI → knowledge representation, logic, rule bases, reasoning → learning from data was just one piece
- 30 years ago, AI research was only ~10% ML
1990s–2000s → rule-based AI was hard to scale (building big knowledge bases by hand is painful) → Google, Microsoft etc. switched to ML
2026 → ~99% of AI activity is ML-based, especially on problems with large datasets

ML vs Statistics

Similar → many ML models (logistic models, trees) came from stats, learning theory is often statistical, lots of statisticians do ML
Differences:
- ML → more inputs, bigger datasets
- ML → focuses on prediction; stats → more on interpreting the model
- ML → algorithm/software focused; stats → more mathematical

ML Errors + Ethics

Adversarial examples → add tiny noise to a pig image → model now says “airplane”
Pedestrian detection mistakes → vertical structures, traffic lights, car parts, tree leaves flagged as people
- Tesla recalled ~363,000 cars over “Full Self-Driving” software
Algorithmic fairness → is the algorithm fair to all individuals?
- Loan model biased against certain zip codes
- Diagnosis model less accurate for some age groups
- Face recognition less accurate for some racial groups
Bias usually comes from the data the model was trained on

Course Organization

Prereqs

ML = math + stats + programming
- Calculus → derivatives, integrals, optimization, partial derivatives
- Probability/stats → random variables, rules of probability
- Linear algebra → vectors, matrices, matrix inversion
- Python for all assignments
HW1 is out now → start early

Schedule (tentative, Canvas is the real version)

#	Date	Topic
1	Thu Sep 24	Course Intro
2	Tue Sep 29	Data + Linear Regression
3	Thu Oct 1	Gradient Descent + Nonlinear Regression
4	Tue Oct 6	Regularization and Classification
5	Thu Oct 8	Classification
6	Tue Oct 13	Nearest Neighbors
7	Thu Oct 15	KNNs, Complexity, Probabilities
8	Tue Oct 20	Logistic Classifier 1
9	Thu Oct 22	Logistic Classifiers 2
10	Tue Oct 27	Neural Networks 1
11	Thu Oct 29	MIDTERM (in class)
12	Tue Nov 3	Neural Networks 2
13	Thu Nov 5	Neural Networks 3
14	Tue Nov 10	CNNs and Decision Trees
15	Thu Nov 12	Decision Trees
16	Tue Nov 17	Ensemble Methods
17	Thu Nov 19	Boosting and Unsupervised Learning
18	Tue Nov 24	KMeans + Hierarchical Clustering
—	Thu Nov 26	No class (Thanksgiving)
19	Tue Dec 1	Generative AI 1
20	Thu Dec 3	Generative AI 2

Final → Fri Dec 11, 10:30a–12:30p
Lectures → PSLH 100; Discussions → Fri 10:00–10:50a, HSLH 100A (starts week 1)
HW due → HW1 Fri Oct 9 · HW2 Fri Oct 23 · HW3 Fri Nov 13 · HW4 Tue Nov 24 · HW5 Fri Dec 4
Project → teams due Thu Nov 12, report due Fri Dec 11

People + Contact

Prof. Stephan Mandt → office hours by appointment (mainly personal matters/logistics)
TAs → Tuan Pham, Jan Groeneveld, Farrin Sofian, Kushagra Pandey, Rajat Bhattacharjya → each has own office hours (see Canvas)
Questions → Piazza, not email
- Post to “all” if it helps everyone, answering others’ questions is encouraged
- Private messages to TAs + instructor if needed

Grading

Component	Weight
Homework (5, lowest dropped, mostly Python)	25%
Midterm	25%
Final	30%
Project (4-person teams)	15%
Participation (Piazza + good behavior in class)	5%

Exams in-person, in the lecture hall
Project → weeks ~4–10, two deadlines: team formation + dataset selection (20%), final submission (80%)
In-person only, no remote option

Academic Integrity

Can discuss assignments verbally with classmates
Can’t look at or copy anyone else’s written notes, solutions, or code → everything you submit must be written by you
Projects → all report text/figures written by your team; code can be yours + publicly available code

Reading (no single textbook)

Intro → A Course in Machine Learning (Daumé), An Introduction to Statistical Learning (James et al.), Patterns, Predictions, and Actions (Hardt & Recht)
Advanced, optional → Mathematics for Machine Learning (Deisenroth et al.), Probabilistic Machine Learning (Murphy), Elements of Statistical Learning (Hastie et al.)

Supervised Learning

Types of ML

Supervised → training gives ⟨x, y⟩ pairs
- Classification → y is categorical
- Regression → y is real-valued
Unsupervised → only x’s, no y’s → clustering, dimension reduction
Active / Reinforcement → algorithm picks which x’s to get y values for
Other → semi-supervised, online learning…

The Setup

x ──► [ Model (learned from data) ] ──► y
input                                    output
("feature vector",                       (prediction)
 usually real numbers)

Classification → y takes one of K values
- K = 2 → y ∈ {0, 1}
- K = 10 → y ∈ {1, 2, …, 10}
Regression → y is real-valued → any real number, or y > 0, or y ∈ [a, b]

Classification Examples

Input x	Output y
Email text	Spam or not (K = 2)
Image pixels	Type of animal (K = 500+)
Speech signal	English word (K = 100,000+)
Loan application	Grant loan or not (K = 2)
Medical data	Diagnosis (K = 2+)

Loan example → each person = 2D point [age, monthly income], blue = good loan, red = bad loan
- Goal → find a good boundary between them
- Hard part → doing this in 100-dimensional spaces
ImageNet → benchmark with 1000 classes, 14 million images → error rate dropped hard once deep neural nets showed up

Regression Examples

Input x	Output y
Financial data	Stock value tomorrow (y > 0)
Laser signals	Distance from object to vehicle (y > 0)
Medical data	Time to survival (y > 0)
Customer click data	Profit/loss from customer
Go board positions	Quality of next move

Two Phases of Supervised Learning

Learn the model → give the algorithm training data (⟨x, y⟩ pairs), it learns a model → most of the quarter is about this step
Predict → given a new x where y is unknown → use the model to predict y

Intermediate phases in practice:
- Validation data → tune the learning algorithm’s hyperparameters
- Test data → check how good the final model is

Data Exploration

Key Aspects of ML

Aspect	What it involves
Data analysis	Visualization, understanding, domain knowledge
Mathematics	Linear algebra, calculus, conditional probability
Algorithms	Optimization, programming, time/space complexity
Evaluation	Error analysis, diagnosis
Application	Is it fair? Will users trust it? Is it interpretable?

Tools

Python → main language here
- NumPy → fast arrays + linear algebra
- SciPy → broader numerical algorithms (e.g. optimization)
- Pandas → tabular data exploration, built on NumPy, uses DataFrames
- Matplotlib / pyplot / seaborn → plotting → HWs use pyplot
- scikit-learn (sklearn) → standard ML library, basis for most HWs, no deep learning
- TensorFlow / PyTorch → deep learning (not used in this class)
Others → Matlab (commercial), R (mostly stats), C/C++ (speed, callable from Python)

Exploratory Data Analysis (EDA)

Before modeling → understand x and y with plots + summary statistics
Helps see how x and y relate, catch problems (e.g. missing values)
Not always practical for huge high-dimensional datasets

Penguin Dataset

344 penguins, 3 classes → Adelie, Chinstrap, Gentoo
4 real-valued features → bill length, bill depth, flipper length, body mass
- Also gender, year, island
Stored as a 344 × 4 table (rows = penguins, columns = features) + a 344 × 1 column of class labels
NaN = “not a number” → standard notation for missing data
penguins.describe() (Pandas) → summary stats: count, mean, std, min, 25%, 50%, 75%, max
- Count is 342, not 344 → 2 penguins have missing values

Histograms + Density

Histogram → split a variable’s range into B bins, count points per bin
- B too small (5) → hides the shape; B too big (50) → noisy
Kernel density estimation (KDE) → smooth curve over the histogram → estimate of the pdf P(x), controlled by a smoothing parameter
Unimodal → one peak; multimodal → several peaks
- Multimodal often means mixed groups → splitting body mass / flipper length by species explains the extra peaks

import seaborn as sns
sns.set_theme()
penguins = sns.load_dataset("penguins")
 
sns.displot(data=penguins, x="body_mass_g")            # auto bins
sns.displot(data=penguins, x="body_mass_g", bins=5)
sns.displot(data=penguins, x="body_mass_g", bins=50)
sns.displot(data=penguins, x="bill_length_mm", kde=True)   # + density curve
sns.displot(data=penguins, x="body_mass_g", col="species", kde=True)  # split by class

Lecture 2: Linear Regression

HW1 → after this lecture you can do Problem 1 (NumPy + visualization) and Problem 2 (linear regression via gradient descent)
- Expect to read the numpy/matplotlib docs, tutorial linked on the Canvas calendar

Notation

Feature vector x = (x₁, x₂, …, x_d) → a point in d-dimensional space, d = number of features
- Patient → x = (21.4, 6.1, 200) = (age, height, weight)
- Loan applicant → x = (21.4, 92697, 65k, 7.5k) = (age, zip code, income, debt)
- Features might not capture everything important about the problem
Many feature vectors → xᵢ = the i-th one (i = 1..n), xᵢⱼ = feature j of example i
Data matrix X → n × d
- Row i = feature vector xᵢ (one person/object)
- Column j = one feature
Target vector y → n × 1, one target per row
- Classification → yᵢ ∈ {0, 1} or {1, …, C} (e.g. y₁ = 0 → no disease)
- Regression → yᵢ real (e.g. y₁ = 121 → blood pressure)
Conventions → bold capital X = matrix, bold lowercase x = feature vector (row), j indexes features (columns), i indexes examples (rows)

Regression Applications

Area	Target y	Features x
Finance	Stock value tomorrow	Market + economic data up to today
Health	Time until cancer recurrence	Medical tests, patient info
Real estate	House selling price	Size, bedrooms, neighborhood
E-commerce	Future customer spending	Income, browsing, past spending

Linear Regression

Goal → predict y for an x_new we haven’t seen → find the line of best fit
1D model → f(x | θ) = θ₀ + θ₁x
- θ₀ = bias (intercept), θ₁ = slope
- θ = (θ₀, θ₁)ᵀ is unknown → learned from data
- Predict → ŷ = θ₀ + θ₁ · x_new
2D → a plane → f(x | θ) = θ₀ + θ₁x₁ + θ₂x₂
d dimensions → f(x | θ) = θ₀ + θ₁x₁ + … + θ_d x_d = Σ₍ⱼ₌₀₎ᵈ θⱼxⱼ = θᵀx
- Trick → add a fake feature x₀ = 1 so the bias θ₀ fits into the dot product

Loss Function: Mean Squared Error

Key idea → pick the θ that makes prediction error on the training data as small as possible
Error for point i → eᵢ = yᵢ − f(xᵢ | θ) (the vertical gap between the point and the line)
Square it → always ≥ 0, big misses count more
L(θ) = (1/n) · Σ₍ᵢ₌₁₎ⁿ (yᵢ − f(xᵢ | θ))² → average squared error over all training points
Lower MSE = better fit
Plotting L over (θ₀, θ₁) → a bowl shape, the bottom is the best line

Gradient Descent

How do we find the θ that minimizes L(θ)? → walk downhill
Foggy mountain analogy → you can’t see the whole landscape, but you can feel which way is downhill right where you stand → take a step that way, repeat
Gradient ∇L(θ) → multi-dimensional derivative, points in the steepest uphill direction → so step the opposite way
At a minimum → ∇L(θ) = 0
Update rule → θ_new = θ_old − λ · ∇L(θ_old)
- λ = learning rate (step size)
- Theory → converges to at least a local minimum if λ is small enough
Algorithm:
1. Initialize θ randomly
2. Compute the gradient at θ
3. Converged? (e.g. ‖∇L‖ < ε) → return θ
4. Otherwise → update θ with the rule above, go back to step 2
Heuristic local search → widely used in ML

Gradient for MSE + Linear Model

Need ∂L/∂θₖ for every k = 0, 1, …, d
eᵢ = yᵢ − Σ₍ⱼ₌₀₎ᵈ θⱼxᵢⱼ
Chain rule → ∂L/∂θₖ = (1/n) · Σᵢ 2eᵢ · ∂eᵢ/∂θₖ, and ∂eᵢ/∂θₖ = −xᵢₖ
→ ∂L/∂θₖ = −(2/n) · Σ₍ᵢ₌₁₎ⁿ eᵢ · xᵢₖ
- Intuition → each point pushes θₖ in proportion to its error × its value of feature k
Gradient vector → ∇L(θ) = (∂L/∂θ₀, ∂L/∂θ₁, …, ∂L/∂θ_d)
MSE + linear model is convex → one global minimum, so gradient descent can’t get stuck in a bad local min
Demo → the line starts random, and after 1 → 10 → 30 → 90 iterations it swings into place as the errors shrink

Alternative: Analytical Solution (flagged as advanced on the slide)

Skip gradient descent, solve directly with matrix algebra → θ = yᵀ · X · (Xᵀ · X)⁻¹
- Same thing written the usual way (as a column vector) → θ = (XᵀX)⁻¹Xᵀy, the “normal equation”
- y → n × 1 targets, X → n × (d + 1) features (with the x₀ = 1 column), XᵀX → (d + 1) × (d + 1)
- Gives the d + 1 values of θ that minimize MSE

Example: Diabetes Dataset

442 patients, 10 features, 1 real-valued target → features scaled to the same standard deviation
Linear model fit on 50% of the data (221 patients) → coefficients θⱼ (÷ 100):

Feature	θⱼ / 100
Age	−0.7
Gender	−2.8
Body Mass Index	6.3
Average Blood Pressure	2.2
Total Serum Cholesterol	−9.5
Low Density Lipid Proteins	5.2
High Density Lipid Proteins	2.1
Total Cholesterol	4.0
Serum Triglycerides	5.6
Blood Sugar Level	1.3

Features are on the same scale → you can compare coefficient sizes → bigger |θⱼ| = more influence on the prediction

Summary

Linear regression → f(x | θ) = θ₀ + θ₁x₁ + … + θ_d x_d, with unknown θ = (θ₀, …, θ_d)ᵀ
Learning → find the θ that minimizes MSE, L(θ) = (1/n) Σ (yᵢ − f(xᵢ | θ))²
How → gradient descent (or the closed-form solution)
Next lecture → choosing the step size, improving gradient descent, nonlinear regression

Discussion 1: Setup + NumPy Arrays

Conda

Conda → open-source package + environment manager for Python
- Separate environments per project → different packages or versions (e.g. Python 2.7 for one project, 3.10 for another)
- Like pip, but also manages environments
Miniconda → minimal install (Python + Conda); Anaconda → Conda + lots of data science packages preinstalled → either works, the discussion uses Miniconda

Setting Up the cs178 Environment

conda --version                              # check the install worked
conda create --name cs178 python=3.10        # make the env
conda activate cs178                         # use it (conda deactivate to leave)
conda config --env --add channels conda-forge
conda install matplotlib pandas jupyterlab
conda install 'scikit-learn>=1.1'            # needs >= 1.1 for HW1
conda list                                   # see everything installed
conda env list                               # forgot the env name?

Jupyter Notebooks

jupyter lab (from the folder you want, with cs178 active) → opens in the browser
Notebook = list of cells → each is Markdown or code, and you run cells one at a time
Markdown cells support LaTeX → inline $a^2 + b^2 = c^2$ , display $$...$$ → optional for this class

VSCode (optional, recommended)

Install the Python (ms-python.python) and Jupyter (ms-toolsai.jupyter) extensions → Cmd+Shift+X
Open the .ipynb → kernel picker (top right) → Python Environments… → cs178
- No conda activate needed → VSCode switches environments per notebook
Export to PDF (some assignments want the PDF with outputs):
1. Cmd+Shift+P → Jupyter: Export to HTML
2. Open the .html in a browser → Print → Save as PDF (turn on “Background graphics”)
- Terminal alternative → jupyter nbconvert --to html your_notebook.ipynb, then print to PDF

NumPy Arrays (Iris dataset)

import numpy as np
from sklearn.datasets import load_iris
iris = load_iris()
X = iris.data      # features
y = iris.target    # labels (0, 1, 2)
X.shape            # (150, 4) → 150 rows (flowers), 4 columns (features)
y.shape            # (150,)  → 1D, 150 entries

Indexing (zero-indexed!)

Type	Example	Gets
Basic	`X[1, 2]`	Row 1, column 2
Basic	`X[0, :]` or `X[0]`	First row → shape (4,)
Basic	`X[:, 0]`	First column
Set a value	`y[6] = 1`	Overwrites entry 6
Slicing	`X[:3, :]`	First 3 rows
Slicing	`X[5:8, 1:3]`	Rows 5–7, columns 1–2 → end is excluded
Negative	`X[-1, :]`	Last row
Negative	`X[-2:, :]`	Last 2 rows
Negative	`X[:, :-1]`	Every column except the last
Integer array	`X[[1, 5, 9], :]`	Rows 1, 5, 9 (in that order)
Integer array	`X[:, [0, -1]]`	First + last column
Logical	`Z[Z > 0.5]`	Only entries > 0.5

Logical indexing → Z > 0.5 makes a boolean array the same shape as Z → indexing with it keeps the True spots
Integer array indexing → picks elements in the order you list them
np.random.rand(10) → 10 random numbers in [0, 1)

Lecture 3: Gradient Descent + Nonlinear Regression

HW1 Problem 3 → nonlinear regression (this lecture)
Recordings on Yuja (via Canvas)

Recap: Linear Regression + MSE

Model → f(x | θ) = θ₀ + θ₁x₁ + … + θ_d x_d = θᵀx
xᵢⱼ = value of feature j for feature vector xᵢ
Gradient → ∂L/∂θₖ = −(2/n) · Σᵢ eᵢ · xᵢₖ for k = 0, 1, …, d (derived in Lecture 2)

Nonlinear Regression

The Problem

What if the data isn’t (approximately) linear? → even the best (lowest MSE) line is a bad fit

Polynomial Feature Expansions

One feature x₁:
- Linear → f(x | θ) = θ₀ + θ₁x₁ → only straight lines
- Quadratic → f(x | θ) = θ₀ + θ₁x₁ + θ₂x₁² → “parabola of best fit”
- Degree p → f(x | θ) = θ₀ + θ₁x₁ + θ₂x₁² + … + θ_p x₁ᵖ → even more flexible
Demo fits → p = 1 (line), p = 2 (curve), p = 5 (wigglier), p = 15 (wild, goes through every point)
Degree p is a hyperparameter

Feature Map φ (d features)

Degree 2 expansion → z = φ₂(x) = (1, x₁, x₂, …, x_d, x₁², x₂², …, x_d², x₁x₂, x₁x₃, …, x₂x₃, …)
- New feature vector z with all first and second-degree feature interactions
Degree p → all possible feature combinations of degree ≤ p
Example → d = 3, x = (1, x₁, x₂, x₃):
- φ₂(x) = (1, x₁, x₂, x₃, x₁², x₂², x₃², x₁x₂, x₁x₃, x₂x₃)
- Check your understanding → compute φ₃(x) (adds x₁³, x₂³, x₃³, x₁²x₂, x₁²x₃, x₂²x₁, x₂²x₃, x₃²x₁, x₃²x₂, x₁x₂x₃)

Polynomial Regression = Linear Regression with New Features

z = φ_p(x) = (1, x₁, x₁², …, x₁ᵖ) = (z₀, z₁, …, z_p)
f(z | θ) = θ₀ + θ₁z₁ + … + θ_p z_p = Σ₍ⱼ₌₀₎ᵖ θⱼzⱼ → still linear in θ
Key idea → polynomial regression is just linear regression on transformed features
Fitting:
1. Fix a degree p
2. Compute zᵢ = φ_p(xᵢ) for every data point
3. Fit ordinary linear regression on the zᵢ

Other Feature Maps

Not limited to polynomials → e.g. periodic data → z = φ_trig(x) = (1, x₁, sin x₁, cos x₁, sin 2x₁, cos 2x₁, …)
Example → bike-share demand by hour (cyclical) → sklearn cyclical feature engineering demo
Designing feature maps = feature engineering

Model Selection

Overfitting vs Underfitting

Model complexity should match data complexity
Underfitting → model too simple to capture the data (p = 1 on curvy data)
Overfitting → model too complex, fits training data too well, can’t generalize to new data (p = 15)
Blue dots = training data (used to fit), red dots = validation data (only seen after training, like real-world deployment)

Degree p	Train MSE	Validation MSE
1	0.2258	0.2375
2	0.0296	0.0808
5	0.0109	0.0170
15	0.0049	0.1465

p = 15 → train MSE keeps dropping but validation MSE jumps → overfitting
p = 5 → best validation MSE here

Train / Validation / Test Splits

Split	Size	Use
Train	≈ 70%	Train many models (different hyperparameters → λ, degree p, …)
Validation (“dev”)	≈ 15%	Evaluate each model, check overfitting, pick the best
Test	≈ 15%	After picking the final model → estimate performance on unseen data

Percentages are heuristics → huge datasets can use smaller val/test %
No overlap between splits → overlap = data leakage → overly optimistic evaluation
Val/test need to be big enough → too few points = noisy, unreliable error estimates
Shuffle first → some datasets come sorted (e.g. by y)
Why a test set if we have validation? → picking a model based on validation = “peeking” → can overfit to the validation set
- Test set is fully unseen → simulates post-deployment data

Diagnosing Over/Underfitting (heuristic)

	High Train Error	Low Train Error
High Val Error	Underfitting	Overfitting
Low Val Error	Bug in your code 🙂 (or train/val mismatch)	Appropriate fit

Classic plot → x-axis = model complexity, y-axis = error
- Training error keeps going down as complexity ↑
- Validation error is U-shaped → down, then back up
- Ideal complexity = bottom of the validation U

Evaluation Beyond MSE

MSE on each split → most straightforward
R² = 1 − MSE / Var(y) → fraction of the variation in y the model captures
How fast does it train? (retraining on new data)
How fast is prediction? (real-time → self-driving cars)
How much memory?
Is it fair?

Cross-Validation

K-Fold Cross-Validation

Large validation set → easy. But small dataset (n = 20 or 100)? → can’t spare 15%
Use multiple validation sets and average:
1. Randomly split data into K disjoint folds (e.g. 5 folds, 20% each)
2. For each fold → train on the other 80%, compute validation error on that 20%
3. CV error = average of the K validation errors
Works with any model (regression or classification)
Cost → train K different models

indices:   1  2  3  4 ...... n-1  n
shuffle → 31 22  6  2 ......  5  41
Fold 1: [VAL ][ train  train  train  train ]
Fold 2: [train][ VAL ][ train  train  train ]
Fold 3: [train  train][ VAL ][ train  train ]
Fold 4: [train  train  train][ VAL ][ train ]
Fold 5: [train  train  train  train][ VAL  ]

Example: 3-Fold CV, 9 Points, m = 1 vs m = 3

xᵢ	88	32	27	68	7	20	53	17	87
yᵢ	79	−2	30	73	−16	43	77	16	94

Model	Split 1 MSE	Split 2 MSE	Split 3 MSE	3-Fold CV MSE
Linear (m = 1)	331.8	361.2	669.8	464.1 (slide; the three average to ≈ 454.3)
Cubic (m = 3)	280.5	3081.3	1640.1	1667.3

→ linear wins → cubic overfits badly on tiny data

Leave-One-Out CV (LOOCV)

Folds = number of data points → train on n − 1, test on 1, repeat n times
Good for very small datasets → trains on as much data as possible
Too expensive for large datasets

Bootstrapping

Make M train/val sets:
1. Train set → sample n points from the data with replacement (some repeat, some left out)
2. Val set → every point not picked for the train set
Fit on each train set, evaluate on its val set, average
Bootstrap vs CV:
- Both widely used → bootstrap more popular in stats, CV more popular in ML
- CV trains on datasets smaller than the original → can underestimate performance
- CV ≈ bootstrapping without replacement
Bootstrapping comes back later for ensemble methods

Summary

Gradient descent → learning rates (fixed, decaying), convexity, convergence checks
Nonlinear regression → feature expansions (polynomial, trig, …) = linear regression on new features
Model selection → over/underfitting, train/val/test splits, cross-validation, bootstrapping

Discussion 2: Matplotlib + Scikit-Learn

Matplotlib Basics

import matplotlib.pyplot as plt
x = np.linspace(0, 2*np.pi, 50)    # 50 evenly spaced points in [0, 2π]
y = np.sin(x)                       # applies sin to every element, no loop
z = np.cos(x)
 
fig, axes = plt.subplots()          # figure (can hold many subplots) + one axes
axes.plot(x, y, color='red', label='sin(x)')   # line plot
axes.plot(x, z, color='blue', label='cos(x)')
axes.set_xlabel('x', fontsize=16)
axes.set_ylabel('$f_1(x)$', fontsize=16)       # LaTeX works in labels
axes.set_title('Fancier Line Plot', fontsize=24)
axes.set_xlim(0, 4*np.pi)                      # manual axis limits
axes.legend(loc='upper right');                # 'best' = auto placement

Trailing ; → stops Jupyter from printing the axes object
axes.scatter(x, y) → scatter plot instead of line
Shorthand format strings → 'r--' = red dashed, 'b:' = blue dotted, 'ro' = red circles
plot just draws points in order and connects neighbors with straight lines → dense points look smooth
HW → use default plot settings unless told otherwise

Subplots

fig, axes = plt.subplots(2, 2)      # 2×2 grid
axes[0, 0].plot(x, y)               # top left → axes[row, col]
axes[1, 1].scatter(x, z)            # bottom right
fig.suptitle('2x2 Subplot Grid')    # title for the whole figure
fig.tight_layout()                  # fix overlapping subplots

Diabetes Dataset (sklearn)

442 patients, 10 baseline features → target = disease progression 1 year later
Features → age, sex, BMI, avg blood pressure, total serum cholesterol, LDL, HDL, total chol / HDL, log serum triglycerides, blood sugar
Discussion only uses 2 → blood pressure (col 3) and blood sugar (col 9) → so it’s plottable

from sklearn.datasets import load_diabetes
all_X, y = load_diabetes(return_X_y=True, scaled=True)
X = all_X[:, [3, 9]]                 # just 2 features
r = axes.scatter(X[:, 0], X[:, 1], c=y, cmap="viridis")   # color = target
fig.colorbar(r, ax=axes, label="Disease Progression")

3D → fig.add_subplot(1, 3, 1, projection='3d'), then axes.scatter(f0, f1, y); axes.view_init(30, angle) rotates the view
Histograms → axes.hist(feature, edgecolor='black')
Interactive plots → pip install ipympl + %matplotlib widget

Train/Test Split + Linear Regression

from sklearn.model_selection import train_test_split
from sklearn.linear_model import LinearRegression
from sklearn.metrics import mean_squared_error, median_absolute_error
 
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25, random_state=seed)
model = LinearRegression()
model.fit(X_train, y_train)
y_pred_test = model.predict(X_test)
mean_squared_error(y_test, y_pred_test)      # MSE
median_absolute_error(y_test, y_pred_test)   # easier to interpret (same units as y)

random_state → fixed seed = reproducible split
MSE units are squared → hard to interpret → median absolute error helps
Visualizing a 2-feature model → build a grid with np.meshgrid, predict on every grid point, draw with axes.plot_surface(...) → a flat plane

Polynomial Features in sklearn

from sklearn.preprocessing import PolynomialFeatures
quad = PolynomialFeatures(degree=2, include_bias=False)
quad_model = LinearRegression()
quad_model.fit(quad.fit_transform(X_train), y_train)
quad_model.predict(quad.fit_transform(X_test))   # transform test data too!

Quadratic → lower test MSE + median AE than linear → prediction surface is now curved
How high a degree? → HW1 covers one way to choose

Braking Distance Example

Speed (mph) vs braking distance (ft) → clearly not linear, grows way faster at high speeds
Make a new feature v² → plot distance vs v² → looks linear!
Fit linear regression on v² → d ≈ slope · v² + intercept
- Physics check → doubling speed ≈ quadruples stopping distance
sklearn needs 2D input → speeds_squared.reshape(-1, 1)

Terminology

Feature expansion / augmentation → add new features derived from existing ones (more dimensions)
Feature engineering → umbrella term → any manual add/remove/modify of features
Polynomial features → add v², v³, … and cross terms v₁ · v₂
Basis expansion → general math idea → re-express inputs in a new basis (polynomials, logs, …)
Shared insight → model stays linear in its parameters, transformed inputs capture nonlinear patterns

Lecture 4: Regularization + Classification

HW1 due Fri 10/9, 11:59 PM → no late submissions, PDF via Gradescope, make sure all code/answers are visible
HW2 Problem 1 → nearest centroids on MNIST

Regularization

Motivation

Overfitting = model “too complex” → can we measure complexity using θ?
Polynomial regression example:
- Simple fit → many small (or zero) coefficients
- Overfit wiggly curve → many large, non-zero coefficients
→ make the model prefer smaller and/or sparser coefficients

Regularized Loss

Measure complexity with a function R(θ) → higher R = more complex
L_R(θ) = L(θ) + α · R(θ) → MSE + complexity penalty
- α > 0 = regularization strength (hyperparameter → needs tuning, big effect on performance)
Minimizing L_R → balance training error vs model complexity
As long as R(θ) is differentiable → still use gradient descent

Norms

Norm ‖v‖ → takes a vector, returns a non-negative number = its “size”/magnitude
L2 (Euclidean) norm → ‖v‖₂ = √(v₁² + v₂² + … + v_d²) → usual “length” (Pythagorean theorem)
L1 norm → ‖v‖₁ = |v₁| + |v₂| + … + |v_d| → add up the lengths of each component
Lp norm (p > 0) → ‖v‖_p = (Σⱼ |vⱼ|ᵖ)^(1/p)
L∞ → ‖θ‖_∞ = max |θⱼ| → not differentiable

Ridge vs LASSO

Use the norm of θ as the complexity → R(θ) = ‖θ‖_p
p = 1 → LASSO
p = 2 → Ridge
sklearn → Ridge(alpha=...), Lasso(alpha=...) → alpha = α

Example: 8th-Order Polynomial on Sine + Noise (n = 30, 10-fold CV)

Coefficient	No Regularization	L2, α = 0.01	L1, α = 0.01
θ₁	133.9	−3.54	−3.04
θ₂	−1628.0	0.98	−0.00
θ₃	9589.3	0.76	0.00
θ₄	−31725.5	1.30	0.00
θ₅	61479.8	1.14	0.00
θ₆	−69079.0	0.68	2.14
θ₇	41604.9	0.14	0.00
θ₈	−10373.6	−0.38	0.00

No regularization → insane coefficients (tens of thousands) → overfit
L2 → all coefficients small
L1 → most coefficients exactly zero → why?

Why L1 Gives Zeros (Sparsity)

Rewrite as a constrained problem → minimize MSE subject to ‖θ‖_p ≤ some budget
Solution must lie inside the unit ball of the norm
- L2 ball → circle → loss contours touch it anywhere
- L1 ball → diamond with corners on the axes → contours usually hit a corner → corner = some θⱼ = 0
→ L1 is “sparsity inducing”

   L1 ball (diamond)                L2 ball (circle)
         θ₂                               θ₂
         *  <- corner: θ₁ = 0           .-'-.
        / \                            /     \
   ----*---*---- θ₁               ----|-------|---- θ₁
        \ /                            \     /
         *                              '-.-'

p < 1 → even more sparsity, but the problem becomes nonconvex
1 ≤ p < ∞ → loss L_R stays convex

Model Selection Summary

Model selection = choosing hyperparameters (and later, which model)
Best practices → train/val/test splits, CV or bootstrapping for small data, use train vs val error to diagnose over/underfitting
Regularization → penalize complexity → L1 (Lasso), L2 (Ridge)

Classification

Supervised Learning Recap

Data comes in (x, y) pairs → x = features (input), y = target (output)
Regression → y is real-valued (any real, y > 0, y ∈ [a, b])
Classification → y takes one of a finite set of K values → K = 2 → y ∈ {0, 1}, K = 10 → y ∈ {1, …, 10}

Class Labels

Labels like {“cat”, “dog”, “other”} → index them as y ∈ {1, 2, …, K}
Exception → binary (K = 2) uses {0, 1}
y = c → “the label is c”

Input x	Output y
Email text	Spam or not (K = 2)
Image pixels	Animal type (K = 500+)
Speech signal	English word (K = 100,000+)
Loan application	Grant or not (K = 2)
Medical data	Diagnosis (K = 2+)

Penguin Dataset

344 penguins, 4 real-valued features → bill length, bill depth, flipper length, body mass
- Also gender, year, island
3 classes → Adelie, Chinstrap, Gentoo
Data matrix 344 × 4 + a 344 × 1 column of labels

Decision Regions + Boundaries

Each point = [feature 1, feature 2, class label]
Classifier = mapping from d-dimensional feature space → one of K labels → ŷ (hat = prediction, not the true y)
Smooth mapping → nearby x get the same label → decision regions (each class “claims” part of the space)
Decision boundary → the edges between regions → points on it are equally likely to be either class
- Can be linear (straight lines) or nonlinear (curvy)
Dimensionality = number of features
- 2D → just draw the boundary
- Real problems → 100s, 1000s, even 1 million features (text) → can’t plot it
- This is where ML shines → searching high-dimensional spaces for good boundaries

Feature Means + Distances

Means + Centroids

Mean of feature j → x̄ⱼ = (1/n) · Σ₍ᵢ₌₁₎ⁿ xᵢⱼ → average down column j
Mean feature vector = centroid → x̄ = (1/n) · Σᵢ xᵢ → average of all n row vectors
Python → np.mean(X, axis=0)
Penguins → 1 centroid for all 344, or 3 centroids, one per species

Euclidean Distance

dist_E(x, z) = √(Σ₍ⱼ₌₁₎ᵈ (xⱼ − zⱼ)²) → straight-line distance, works in any d dimensions

x  = np.array([1, 2, 5])
z1 = np.array([3, 3, 7])
z2 = np.array([5, 3, 10])
np.sqrt(np.sum((x - z1)**2, axis=0))   # 3.0
np.sqrt(np.sum((x - z2)**2, axis=0))   # 6.48
np.linalg.norm(x - z1)                 # same thing

General Lp Distances

‖x − z‖_p = (Σⱼ |xⱼ − zⱼ|ᵖ)^(1/p)
p = 1 → absolute (Manhattan) distance → Σ |xⱼ − zⱼ|
p = 2 → Euclidean distance

Units + Scale Matter

Penguins with body mass in grams → dist(x₁, x₂) = 50.3, dist(x₁, x₃) = 500.2 → x₃ is 10× farther
Same penguins with body mass in kilograms → dist(x₁, x₂) = 5.2, dist(x₁, x₃) = 14.1 → x₂ still closer, but by a way smaller factor
→ a feature’s units change how much it counts in the distance

Geometric Thinking

Feature vectors = points in d-dimensional space → distances, clusters/clouds of points, separating boundaries (lines, planes)

Nearest Centroid Classifier

Idea

Compute the centroid of each class
New point → predict the class whose centroid is closest (Euclidean)
Simple but plausible → each class is represented by one “template” (its centroid)

Training (pseudocode)

NC_Training(X, y):
    C = length(unique(y))           # number of classes
    for c = 1..C:
        index_c = find(y == c)      # rows with label c
        X_c = X[index_c, :]
        Centroid_c = mean(X_c)      # centroid for class c
    return Centroid_1, ..., Centroid_C

Prediction

NC_Prediction(x, centroids):
    min_distance = infinity
    for c = 1..C:
        d_c = distE(x, Centroid_c)
        if d_c < min_distance:
            yhat = c
            min_distance = d_c
    return yhat                     # class with the closest centroid

Plotting Decision Regions

Solve for the boundary mathematically → only possible for simple classifiers
Make a dense 2D grid of points, run the classifier on each → color by prediction (used in lecture + DecisionBoundaryDisplay)

Evaluating Classifiers

Accuracy

One example → Acc = I(ŷ, y) → indicator function = 1 if equal, 0 otherwise
Test set with N_test examples → Acc = (1/N_test) · Σᵢ I(ŷᵢ, yᵢ)
Example → 4 test points, correct on 3 → Acc = ¼(1 + 0 + 1 + 1) = 0.75
Error rate → Err = 1 − Acc (fraction or percent)

Penguins: Nearest Centroid

Train on 200, test on 133 → 2 features (flipper length, bill length)
Raw features → 13.5% test error
Problem → flipper range ≈ 50, bill length range ≈ 25 → flipper gets ~2× the weight in distances
Min-max scaling → x’ = (x − min(x)) / (max(x) − min(x)) → every feature in [0, 1]
Scaled → 5.3% error (about half)
All 4 scaled features → 1.5% error
Different feature pair → 36.8% → 31.6% after scaling

MNIST

70,000 handwritten digits, 28 × 28 grayscale pixels → classic ML dataset (Yann LeCun, 1998, Turing Award winner)
Each m × m image → flattened into a vector of length d = m² → d = 28² = 784
10 classes → y ∈ {0, 1, …, 9}
Centroids per class look blurry → they’re averages of many differently-written digits
Nearest centroid (fit on 20%) → ~80% accuracy on both train and test

Summary

Classification → predict a discrete label (vs regression → real number)
Geometry → data = points, norms, distances, centroids
Nearest centroid → predict the label of the closest class centroid

Lecture 5: Nearest Centroids (Part 2) + kNN

HW2 → Problem 1 nearest centroids on MNIST, Problem 2 kNN

Nearest Centroid Recap (Penguins)

200 train / 133 test, 2 features, scaled to [0, 1]
Training = computing 3 centroids → the centroids are the classifier
Centroids implicitly define the decision boundaries + regions (blue, orange, green)
Test → 6 errors / 133 = 4.5% error (error = point lands in the wrong region)
Workflow:
1. Build → labeled data → compute centroids → that’s the classifier
2. Use → new unlabeled point → predict a label
MNIST in HW2 → 75% train; digit classes aren’t perfectly balanced

Nearest Centroid Has Linear Boundaries (Proof, C = 2, d = 2)

Centroids μ₁, μ₂ → x is on the boundary ⟺ ‖x − μ₁‖ = ‖x − μ₂‖

Plug into Euclidean distance → √((x₁ − μ₁₁)² + (x₂ − μ₁₂)²) = √((x₁ − μ₂₁)² + (x₂ − μ₂₂)²)
Square both sides + expand → x₁², x₂² cancel on both sides
Move x₂ terms left, x₁ terms right → 2(μ₂₂ − μ₁₂) · x₂ = −2(μ₂₁ − μ₁₁) · x₁ + (‖μ₂‖² − ‖μ₁‖²)
Solve for x₂ → x₂ = a · x₁ + b → a line

General form → 2(μ₂ − μ₁) · x = ‖μ₂‖² − ‖μ₁‖² → linear in x
Boundary = perpendicular bisector of the segment between the two centroids
More classes → piecewise linear boundaries

Limitations

If the ideal classifier needs 2 separate regions for one class → nearest centroid can’t do it → one region per class only
Strengths → simple to code, easy to explain, doesn’t need much training data
Weakness → too simple for complex boundaries

Classifier Evaluation

Confusion Matrix

C × C matrix → rows = true class, columns = predicted class
Entry (r, c) → # of examples with true class r predicted as c
Build it → start at all zeros, for each (true, predicted) pair add 1 to that cell

Example (C = 3)

Pairs → (1,1) (2,1) (2,2) (3,3) (3,3) (3,1) (1,1) (2,2) (1,2) (2,2) (2,2)

True \ Pred	1	2	3
1	2	1	0
2	1	4	0
3	1	0	2

n = sum of all counts = 11
Accuracy = (sum of diagonal) / n = 8/11 = 0.73 → diagonal = correct
Error = (sum off-diagonal) / n = 3/11 = 0.27 → off-diagonal = “confusions”

MNIST Confusion Matrix (Nearest Centroid)

Some pairs rarely confused → “1” vs “0”, “4” vs “3”
Others confused a lot → “5” vs “3”, “4” vs “9”
- e.g. 60 test examples that were really “9” got predicted as “4”

Binary Confusion Matrix

y = 0 → negative class (no disease), y = 1 → positive class (disease)

True \ Pred	0	1
0	TN (true negative)	FP (false positive)
1	FN (false negative)	TP (true positive)

Recall = TP / (TP + FN) → of the truly positive points, how many did we catch?
- “If a patient has the disease, how good are we at detecting it?”
Precision = TP / (TP + FP) → of the points we predicted positive, how many really are?
- “If we say a patient has the disease, how likely are we to be right?”

Example

True \ Pred	0	1
0	12	2
1	6	18

Accuracy = (12 + 18) / 38 = 0.789
Recall = 18 / (18 + 6) = 0.75
Precision = 18 / (18 + 2) = 0.9

k Nearest Neighbors (kNN)

From Centroids to Neighbors

Extension idea → represent each class with multiple points instead of one
- But how many? Which ones?
Nearest neighbor takes it to the extreme → every training point represents its class

1-Nearest Neighbor

Given → training data X, y
Predict for x → find the training point xᵢ closest to x → predict its label yᵢ
Memory-based prediction → no real training, just store the data
Decision boundaries are piecewise linear → more complex than nearest centroid

k-Nearest Neighbors

Find the k closest training points → predict the majority label
- Neighbors’ labels {1, 3, 3, 1, 3} → predict 3
1-NN = special case k = 1
Example → k = 1 predicts blue, k = 3 and k = 5 predict red (same point!)

Details

Distance → Euclidean by default, but any distance works (e.g. edit distance for strings)
Ties:
- Type 1 → two+ points equally far from x
- Type 2 → after picking k labels, no single majority
- Both → break ties randomly
- Binary problems → pick odd k (1, 3, 5, …) to avoid Type 2 ties
kNN can model disjoint decision regions (two separate red regions) → nearest centroid can’t

Wine Dataset

178 Italian wines, 13 features, 3 classes
Lecture uses the first 2 → alcohol content, malic acid

from sklearn.datasets import load_wine
wine_X, wine_y = load_wine(return_X_y=True)

Small k → complex, jagged regions; larger k → smoother, more compact regions (always piecewise linear)

Voronoi Diagrams

1-NN regions = a Voronoi diagram (Georgy Voronoy) → each training point owns the area closer to it than to any other point
- Used in spatial analysis → “where’s the nearest Starbucks to every location?”
Distance choice changes the shape → L2 gives straight-edged cells, L1 gives blockier ones

Choosing k

k too small → predictions too noisy
k too large → uses points too far from x
Happy medium in between → k is a hyperparameter → tune with a validation set
Error vs k plot (75/25 split) → test error > training error, test error varies with k

Complexity vs k

k = 1 → memorizes every example perfectly → too complex
k = n → always predicts the majority class → too simple
1 < k ≪ n → usually best (depends on dataset)
This error-vs-complexity tradeoff shows up all over ML

error
  |  \                                   /
  |   \  test                          /
  |    \____                       ___/
  |         \______________ ______/
  |  train ___-------------
  |____/________________________________ k
     k=1 (too complex)        k=n (too simple)

kNN on MNIST

10,000 train / 1,000 test (to save compute)
Baseline error = 90% → 10 equally common classes → always guessing one class (or random) is right only 10% of the time
kNN error is much lower than nearest centroid (~20%) → k = 1 is best here (varies by dataset/training size)

Distances + Dimensionality

NC + kNN rely on distances → unreliable in high dimensions:
- Poorly scaled features dominate the distance
- Noisy, irrelevant features add junk to the distance
These methods can’t pick out relevant features → overfit when there are many noisy ones
- Decision trees (later) handle this better
Experiment → add pure-noise features to Wine (n_train = 20, k = 1) and MNIST (n_train = 2000) → error goes up as noise features are added

kNN Summary

Small k → complex boundaries; large k → smoother
Strengths → simple, only one hyperparameter, can be quite accurate
Weaknesses → must store all training data (memory + speed), loses accuracy as d grows

Time + Space Complexity

Setup

n = # examples, d = # features, C = # classes, k = # neighbors → assume n ≫ k and n ≫ C
Big O → worst-case scaling → O(nd) = linear in n and d; O(dn² + Cn) = quadratic in n
Care about time + space, for training + prediction

Why It Matters

Training → n can be millions, d = 100,000 → avoid super-linear (O(n²), O(d³)); O(nd) is fine and common
- May train 1000s of models for hyperparameter search, or retrain several times a day
- Memory-limited GPUs
Prediction → often need < milliseconds (mobile, web)
- Billion-weight models may not fit on a phone (memory + battery)

Nearest Centroid

Training time → O(nd) → n vectors summed, each addition O(d)
Training space → O(nd + n + Cd) → data + labels + centroids ≈ O(nd)
Prediction time (per x) → O(Cd) → distance to C centroids, O(d) each, + find the min
Prediction space → O(Cd) → store C centroids

kNN

Training → basically none
Prediction space → O(nd) → must keep all training data
Prediction time → distances to all n points = O(nd) + find the k smallest:
- Option 1 → sort all n distances → O(nd + n log n)
- Option 2 → keep a sorted list of the k best so far, insert/evict as you go → O(k) per distance → O(nd + nk)
- Option 2 usually faster since k is typically < log n
- If d ≫ k → the O(nd) term dominates anyway
- Majority vote at the end is negligible
sklearn timing experiments → kNN prediction time grows linearly in n and linearly in d

Summary

Nearest centroid → closest class centroid, piecewise linear boundaries, simple but limited
Evaluation → accuracy, confusion matrices, precision, recall
kNN → majority label of the k nearest training points

Discussion 3: Feature Vectors, Centroids, Decision Regions

Big Idea

Very different raw data (2D points, images, text) → convert to vectors → then compute centroids, train models, etc.

Part 1: Moons (already 2D)

from sklearn.datasets import make_moons
from sklearn.neighbors import NearestCentroid
from sklearn.inspection import DecisionBoundaryDisplay
 
moon_X, moon_y = make_moons(n_samples=1000, noise=0.3, random_state=seed)
X_train, X_test, y_train, y_test = train_test_split(moon_X, moon_y, test_size=0.25, random_state=seed)
 
# one centroid per class → average of that class's rows
moon_centroids = np.vstack([X_train[y_train == label].mean(axis=0)
                            for label in np.unique(y_train)])
 
clf = NearestCentroid().fit(X_train, y_train)
DecisionBoundaryDisplay.from_estimator(clf, X_train, response_method='predict', alpha=0.35, ax=ax)

Each row = one point, each column = one feature
2D → can directly see the points, the centroids (big X markers), and the decision regions
This geometric intuition gets way harder in 100s or 1000s of dimensions

Part 2: MNIST (images → 784-D vectors)

from sklearn.datasets import fetch_openml
mnist_X, mnist_y = fetch_openml('mnist_784', as_frame=False, return_X_y=True, parser='auto')
mnist_y = mnist_y.astype(int)
img = mnist_X_tr[0].reshape(28, 28)    # vector → image
plt.imshow(img, cmap='gray')

Same point, two views → 28 × 28 grid (for humans) or 784-dim vector (for the model)
Mean of all digits → a blob that doesn’t look like any digit → class-wise centroids are more meaningful
Per-digit centroids → reshape to 28 × 28 → an “average 0”, “average 1”, … → class prototypes
784 dims → can’t draw decision regions → centroids are the interpretable summary instead

Part 3: Yelp Reviews (text → bag-of-words)

Bag-of-words → build a vocabulary, one feature per term, each document = counts of each term
- High-dimensional + most entries are 0 → sparse
Labels → stars ≥ 4 → positive (1), stars ≤ 2 → negative (0), 3 stars → dropped

from sklearn.feature_extraction.text import CountVectorizer
vectorizer = CountVectorizer(stop_words='english', min_df=0.02, ngram_range=(1, 1))
X = vectorizer.fit_transform(text)          # sparse matrix (n_reviews × vocab size)
vectorizer.vocabulary_                      # term → column index
vectorizer.get_feature_names_out()          # column index → term
X[i].nnz                                    # number of non-zero entries in review i
X[i].toarray()                              # dense view

stop_words='english' → drop “the”, “and”, …; min_df=0.02 → keep words in ≥ 2% of reviews
Text centroids → average bag-of-words vector over positive vs negative reviews → look at the top-weighted terms

pos_centroid = np.asarray(X[y == 1].mean(axis=0)).ravel()
idx = np.argsort(pos_centroid)[::-1][:15]   # 15 biggest

Image centroid = average picture; text centroid = average word-usage pattern

Takeaways

Moons → already 2D → plot points, centroids, regions directly
MNIST → 784-D vectors → centroids act like prototype digits
Yelp → sparse bag-of-words vectors → centroids summarize typical word usage per class

Lecture 6: kNN Recap, Curse of Dimensionality, Probability Review

All written communication → Piazza only (no email, no Canvas messages)
Regrade requests → open for 1 week on Gradescope, only if we made a grading mistake → they may regrade the whole assignment (score can go up or down)
HW2 posted → start early

kNN Recap

Fix k → for an unlabeled x:
1. Compute d(x, xᵢ) for every training point → take the labels of the k closest
2. Predict the majority vote (e.g. {1, 3, 3, 2, 1, 3} → 3), break ties randomly
Piecewise linear boundaries, can make disjoint regions (nearest centroid → only one region per class)
Small k → complex regions; larger k → smoother
Test error > training error; test error varies with k
k = 1 → memorizes (too complex), k = n → majority class (too simple)
MNIST → baseline error 90%, kNN way better than nearest centroid (~20%), k = 1 best on that data
Weaknesses → stores all training data, worse as d grows (scaling + irrelevant features mess up distances)

The Curse of Dimensionality

Classifiers that rely on distance or density can perform poorly in high dimensions
Already saw → distance-based error goes up as you add dimensions
New angle → density of data points

The Binning Classifier (illustration, not a real classifier)

Bin each feature into B bins (e.g. equal-width bins over the range) → 2 features = B × B grid of cells
Train → in each cell, store the majority class of the training points there
Predict → look up which cell x falls in → predict that cell’s label
Big B → very complex boundaries

Wine data, B × B grid → each cell's majority label = the classifier
       R       R
   W W     R   R   R   B
 W W   R   R   R   R   B
 W W W     R   B   R   B
 W W W     W   B   B   B  B
 W W W W W

Why It Breaks

d dimensions → Bᵈ cells → grows exponentially in d
- B = 10 → B² = 100, B⁵ = 10⁵, B²⁰ = 10²⁰
- Even B = 2 → 2²⁰ ≈ 1 million, 2⁴⁰ ≈ 1 trillion
Problem 1 → memory
Problem 2 → almost every cell is empty
- 2⁴⁰ ≈ 1 trillion cells, n = 1 million points → at best 1 in a million cells has any data
- → never enough data to fill the cells as d grows
This is the curse of dimensionality → distance-based methods are especially sensitive

Probability in ML

Why Probability?

Real world is full of uncertainty → randomness, overwhelming complexity, lack of knowledge
Often not enough to predict a label → need how confident you are (e.g. disease diagnosis)
Probability gives → a quantitative framework for uncertainty, rules for manipulating it, tools to build algorithms that use randomness

Basic Probability

S = sample space → all possible outcomes
Event A = a subset of S
- Flip a coin 5 times → S = all H/T strings of length 5 → A could be “HTTHT”, “heads on the first flip”, “more heads than tails”
Pr[A] → if I pick a random element of S, how likely is it to be in A?
- Pr[heads on first flip] = 1/2
- Think of it as the “area” of A inside S (S has area 1)

Axioms

0 ≤ Pr[A] ≤ 1
Pr[S] = 1
Pr[{}] = 0 → probability of no outcome is zero
Pr[A ∪ B] = Pr[A] + Pr[B] − Pr[A ∩ B] → subtract the overlap because it got counted twice

Discrete Random Variables

X → outcome of an experiment, takes values in a finite set S = {a₁, …, a_d}
- Values are disjoint + exhaustive → X takes exactly one value
PMF (probability mass function) → Pr[X = aᵢ] for each value
- 0 ≤ Pr[X = aᵢ] ≤ 1 and Σᵢ Pr[X = aᵢ] = 1
- Probability of a subset A → Pr[X ∈ A] = Σ₍ₐᵢ ∈ A₎ Pr[X = aᵢ]

Common Discrete Distributions

Distribution	Story
Bernoulli(p)	One coin toss → X ∈ {0, 1}
Binomial(p, n)	Toss the coin n times, count heads
Categorical / Discrete(d)	Roll a d-sided die once
Multinomial(d, n)	Roll the die n times, count each outcome

Bernoulli PMF as a function → p(x) = pˣ(1 − p)¹⁻ˣ → x = 1 gives p, x = 0 gives 1 − p
- Function form is handy later → take derivatives, fit to data (→ logistic regression loss!)

Joint Distributions

p(x, y) = Pr[X = x, Y = y] → probability both happen → a table that sums to 1
Law of total probability (marginalizing) → p(x) = Σ_y p(x, y) → some y happened, we don’t know which, so sum over all
- Binary y → p(x) = p(x, y = 0) + p(x, y = 1)

Dentist Example (Russell & Norvig) → T = toothache, D = probe catches, C = cavity

T	D	C	P(T, D, C)
0	0	0	0.576
0	0	1	0.008
0	1	0	0.144
0	1	1	0.072
1	0	0	0.064
1	0	1	0.012
1	1	0	0.016
1	1	1	0.108

Marginal → P(C = 1) = Σ over T, D = 0.008 + 0.072 + 0.012 + 0.108 = 0.20

Conditional Probability

p(y | x) = p(x, y) / p(x) (if p(x) > 0) → distribution of Y once we know X = x
Chain rule → p(x, y) = p(y | x) · p(x) → e.g. p(rain, cloudy) = p(rain | cloudy) · p(cloudy)
- More generally → p(x₁, x₂, …, xₙ) = p(x₁) · p(x₂ | x₁) · p(x₃ | x₁, x₂) ⋯

Effect of Evidence (dentist)

Prior → P(C = 1) = 0.20
See D = 0, T = 0 → P(C = 1 | D = 0, T = 0) = 0.008 / (0.576 + 0.008) ≈ 0.014 (slide writes 0.012) → belief drops
See D = 1, T = 1 → P(C = 1 | D = 1, T = 1) = 0.108 / (0.016 + 0.108) = 0.871 → belief jumps
These are posterior probabilities
Toothache only → P(C = 1 | T = 1) = (0.012 + 0.108) / (0.064 + 0.012 + 0.016 + 0.108) = 0.12 / 0.20 = 0.60
- Denominator P(T = 1) = 0.20 = probability of the evidence

Bayes’ Rule

From the chain rule → p(y | x) = p(x | y) · p(y) / p(x), where p(x) = Σ_y p(x | y) p(y)
Lets you flip a conditional → compute the posterior from the evidence
Flu example → F = flu, H = headache
- P(F = 1) = 0.05, P(H = 1 | F = 1) = 0.50, P(H = 1 | F = 0) = 0.20
- P(F = 1 | H = 1) = (0.50 · 0.05) / (0.50 · 0.05 + 0.20 · 0.95) = 0.025 / 0.215 = 0.116
- → a headache only bumps flu from 5% to ~12%

Continuous Random Variables

e.g. X = temperature → Pr[X = x] doesn’t make sense (can’t sum over infinitely many values to get 1)
CDF → F(x) = Pr[X ≤ x] → well-defined
PDF → p(x) = d/dx F(x)
- Like “probability that X = x” but not quite → Pr[X ≤ x] ∈ [0, 1], but p(x) can be > 1
- Integrate the pdf to get probabilities → Pr[a ≤ X ≤ b] = ∫ₐᵇ p(x) dx
Uniform(a, b) → p(x) = 1/(b − a) for a ≤ x ≤ b, 0 otherwise → flat
Gaussian / Normal → classic bell curve → p(x) = (1/√(2πσ²)) · exp(−(x − μ)² / (2σ²))
Free probability-for-ML resource linked on Canvas → good probability knowledge is one of the most useful skills in advanced ML

Lecture 7: Logistic Classifiers

HW2 Problem 3 → doable after this lecture

Midterm: Thursday, Oct 29 → in class, normal lecture time, no electronic devices (no calculator, no phone)

Sample exam + solutions on Canvas → some problems may be outdated (e.g. SVMs) → focus on what was covered in lecture
Study → lecture slides, HWs, discussions
- Be able to reproduce every derivation from lecture
- Be able to run every algorithm by hand → fit models, make predictions

Class Project

Teams of 4 → forming a team on time is worth 10% of the project grade (team spreadsheet on Canvas)
Pick a dataset → all classification → options: a tabular dataset, image datasets, a text dataset
At least 4 classifiers → 3 required: kNN, logistic, feedforward neural network → 4th is your pick (random forests, bigger NN, CNNs for images, RNNs for text, …)
Goal → insight + understanding of strengths/weaknesses, not the world’s most accurate classifier
Dates → team formation 11/12, project due 12/11 (after the final)
Ideas:
- Metrics beyond accuracy → confusion matrices, AUC, precision → error analysis (what kinds of mistakes?)
- Learning curves → accuracy vs training set size (subsample your data) → classifier rankings can flip as n changes
- Complexity vs error plots → x = model complexity, y = train + test error
- Interpretability → drop features one at a time and measure the change; visualize NN hidden units

Logistic Classifiers

Why Probabilities?

Want p(y = 1 | x) → and p(y = 0 | x) = 1 − p(y = 1 | x), so modeling p(y = 1 | x) is enough
kNN + nearest centroid only output labels, not probabilities → need a new model

Intuition

For each x → compute a real-valued score f(x | θ)
- High score → y = 1 more likely, low → y = 0 more likely
Turn the score into a probability → squash it into [0, 1]

Why Not Just Linear Regression on 0/1 Labels?

Fit f(x | θ) = θ₀ + θ₁x, then threshold:
- ŷ = T(x | θ) = 1 if f > 0.5, 0 if f < 0.5, ? if f = 0.5 (on the boundary)
Train by minimizing MSE of (yᵢ − T(xᵢ | θ))² → problem → the threshold function T is flat → derivative is 0 everywhere → gradient descent can’t learn anything
Fix → a soft threshold that’s differentiable → the sigmoid / logistic curve
- Bonus → outputs can be read as probabilities; used everywhere (neural nets)

The Model (a.k.a. logistic regression, even though it’s a classifier)

z(x | θ) = θ₀ + θ₁x₁ + … + θ_d x_d = θᵀx → same linear score as linear regression
f(x | θ) = σ(z) = 1 / (1 + e^(−z)) → the sigmoid
- z → +∞ ⟹ f → 1; z → −∞ ⟹ f → 0; z = 0 ⟹ f = 0.5
f(x | θ) ≈ p(y = 1 | x)
Predict → ŷ = 1 if f(x | θ) > 0.5, else 0
Decision boundary → f = 0.5 ⟺ z = θᵀx = 0 → a line (2D) / hyperplane → linear boundary

inputs      weights
  x₁ ──θ₁──┐
  x₂ ──θ₂──┤
  x₃ ──θ₃──┼──► Σ  ──► z(x;θ) ──► σ(z) ──► f(x;θ) = P(y=1|x)
  +1 ──θ₀──┘      (weighted sum)  (sigmoid)
 (bias)

Probabilities = Confidence

f changes smoothly with x
Far from the boundary → near 0 or 1 (confident); near the boundary → near 0.5 (unsure)
Contour plot of f over 2D Iris data → bands of equal probability parallel to the boundary
Why useful:
- Report confidence like a human → self-driving, medical imaging
- Ranking → search (most relevant URLs), finance (loans most likely repaid)
- Neural nets output class probabilities too
- Getting calibrated probabilities is still a research problem → ML systems that “know what they don’t know”

Binary Cross-Entropy Loss

Recipe to Train Any Model

Define the model f(x | θ) → logistic model
Define a loss function
Work out the gradients (everything’s differentiable → just calculus)
Run gradient descent

Deriving the Loss (a.k.a. log-loss)

n training points (xᵢ, yᵢ) → model predicts pᵢ = f(xᵢ | θ) = estimate of p(y = 1 | xᵢ)
Want pᵢ near 1 when yᵢ = 1, near 0 when yᵢ = 0
Probability the model gives the correct class → pᵢ^yᵢ · (1 − pᵢ)^(1 − yᵢ) → a Bernoulli PMF
- yᵢ = 1 → pᵢ; yᵢ = 0 → 1 − pᵢ
Take the log (numerical stability) → yᵢ log pᵢ + (1 − yᵢ) log(1 − pᵢ)
Maximize this over the whole dataset ⟺ minimize:

L_BCE(θ) = Σ₍ᵢ₌₁₎ⁿ [ −yᵢ log pᵢ − (1 − yᵢ) log(1 − pᵢ) ]

= Σᵢ [ −yᵢ log f(xᵢ | θ) − (1 − yᵢ) log(1 − f(xᵢ | θ)) ]
Same loss works for neural nets; multi-class version comes later

Visualizing the Loss

yᵢ = 1 → loss = log(1/pᵢ) → 0 when pᵢ = 1, shoots to ∞ as pᵢ → 0
yᵢ = 0 → loss = log(1/(1 − pᵢ)) → 0 when pᵢ = 0, shoots to ∞ as pᵢ → 1
→ confident wrong predictions get punished hard

Gradient for Logistic Classifiers

Step 1: Log rule + chain rule

∂L/∂θⱼ = Σᵢ [ −(yᵢ / pᵢ) + (1 − yᵢ)/(1 − pᵢ) ] · ∂pᵢ/∂θⱼ

Step 2: Sigmoid derivative

σ’(z) = σ(z) · (1 − σ(z)) → check it yourself with ordinary calculus
Chain rule → ∂f(xᵢ | θ)/∂θⱼ = σ(z(xᵢ | θ)) · (1 − σ(z(xᵢ | θ))) · ∂z(xᵢ | θ)/∂θⱼ

Step 3: z is linear

z(xᵢ | θ) = θ₀ + Σⱼ xᵢⱼθⱼ → ∂z/∂θⱼ = xᵢⱼ (with xᵢ₀ = 1 for the bias)
So ∂pᵢ/∂θⱼ = pᵢ(1 − pᵢ) · xᵢⱼ

Step 4: Plug in + simplify → the ugly stuff cancels:

[ −yᵢ(1 − pᵢ) + (1 − yᵢ)pᵢ ] · xᵢⱼ = (pᵢ − yᵢ) · xᵢⱼ

∂L_BCE/∂θⱼ = Σ₍ᵢ₌₁₎ⁿ (pᵢ − yᵢ) · xᵢⱼ

Intuition → (prediction − truth) × feature value → same shape as the linear regression gradient
Update → θⱼ ← θⱼ − λ · Σᵢ (pᵢ − yᵢ) xᵢⱼ

Time Complexity of One Gradient

Predict every training point (O(d) each) and subtract yᵢ → O(nd) → vector of length n
For each θⱼ → multiply by column xᵢⱼ and sum over n → O(nd)

Total → O(nd) per gradient
Use vectorization (NumPy, no Python for-loops) → still O(nd), but each op is way faster
Full gradient descent → O(nd · I), I = iterations to converge (unknown in advance)

Summary

f(x | θ) = σ(θᵀx) → model’s belief in p(y = 1 | x)
Train by minimizing binary cross-entropy with gradient descent

Additional Topics in Logistic Models

Regularization

L_R(θ) = L(θ) + α · R(θ) → α > 0 = regularization weight
- L2 (squared) → R(θ) = Σⱼ θⱼ²
- L1 (Lasso) → R(θ) = Σⱼ |θⱼ|
Unlike kNN / nearest centroid → logistic models can be regularized
α = 0 → no regularization; α too big → all weights → 0, model ignores the data
α is a hyperparameter → vary it, keep the value with the best validation accuracy (HW2 Problem 3)
Yelp example → accuracy vs 1/α (increasing regularization) → there’s a sweet spot

HW2: Logistic Classifier on Yelp Text

Binary labels → y = 1 if stars ≥ 4, y = 0 if stars < 2 (see Discussion 3 notebook)
Bag-of-words with the 404 most common English words → d = 404, each entry = count of that word in the review

Review	great	excellent	tasty	expensive	slow	bad	Label
d1	3	1	4	0	0	1	1
d2	2	2	1	0	1	0	1
d6	1	0	0	1	3	1	0
d7	0	0	1	4	1	0	0

Logistic Regression in sklearn

from sklearn.linear_model import LogisticRegression
model = LogisticRegression(penalty='l2', C=1.0)   # C = 1/α → smaller C = MORE regularization
model.fit(X_train, y_train)                        # X: n_samples × n_features
model.predict(X_test)                              # labels
model.predict_proba(X_test)                        # class probabilities
model.coef_, model.intercept_                      # d weights + bias

Output → d + 1 weights (one per term + intercept)
“fit” → runs a gradient-based optimizer to learn θ

Interpreting Weights

Assume features are non-negative → hold everything fixed, increase x₁:
- θ₁ > 0 → z goes up → P(y = 1 | x) goes up (bigger θ₁ = faster)
- θ₁ < 0 → z goes down → P(y = 1 | x) goes down
- θ₁ = 0 → classifier ignores x₁
Sign → direction of the effect; magnitude → how strong

Most Positive	Weight	Most Negative	Weight
pleased	2.357	worst	−3.068
excellent	2.276	horrible	−2.640
amazing	2.269	soggy	−2.406
delicious	2.114	terrible	−2.364
generous	2.033	disappointing	−2.112
fantastic	2.019	bland	−2.095
awesome	1.949	waste	−2.028
gem	1.658	excited	−1.987
perfect	1.581	rude	−1.891
enjoyed	1.565	dry	−1.762

“excited” is negative → probably “I was so excited… but” reviews 💀

Strengths + Weaknesses

Strengths → models probabilities, interpretable weights, easy to regularize, fast predictions O(d) (one dot product + sigmoid)
Weaknesses → linear decision boundary only; needs gradient descent training (slow on big data) vs kNN/NC with little or no training

K > 2 Classes (Multiclass Logistic)

One weight vector per class → zₖ = θₖᵀx for k = 1, …, K
Softmax → P(y = k | x) = e^(zₖ) / Σ₍ⱼ₌₁₎ᴷ e^(zⱼ)
- e^(zₖ) → makes every score positive
- Dividing by the sum → probabilities add to 1
- Generalizes the sigmoid (K = 2), also used in neural nets

	z₁	z₂	z₃	z₄
Scores z	2.1	−1.4	1.2	0.3
e^z	8.17	0.25	3.32	1.35
softmax(z)	0.62	0.02	0.25	0.10

Training → gradient descent, each loss term = −log P(yᵢ = k | xᵢ) where k is the true label of point i
Notation → “K” for number of classes now (was C, to avoid clashing with kNN’s k)

Nonlinear Boundaries?

Add higher-order features → x₁², x₂², x₁x₂, … → same as polynomial regression
- Still train the same way (they’re just extra precomputed features)
- Boundary is still linear in the new features but curvy (e.g. quadratic) in the original (x₁, x₂) space
Problems → which features do you add? more features = slower + more memory → (Lecture 8 → neural nets learn the features)

Summary

Logistic model = linear weighted sum + sigmoid that maps to [0, 1]
Outputs = class probabilities
K classes → one weight vector per class + softmax
Train with log-loss + gradient descent
Strengths → easy to fit (convex loss, simple gradient), easy to interpret (one weight per feature)
Weakness → linear boundary may not be enough

Discussion 4: Logistic Regression on MNIST + Decision Boundaries

Setup: 0 vs 8

from sklearn.linear_model import LogisticRegression
from sklearn.metrics import accuracy_score, recall_score, precision_score, confusion_matrix, ConfusionMatrixDisplay
 
wanted = np.isin(mnist_y, [8, 0])                  # keep only 0s and 8s
X_sub, y_sub = mnist_X[wanted, :], mnist_y[wanted]
X_tr, X_te, y_tr, y_te = train_test_split(X_sub, y_sub, test_size=0.25, random_state=seed, shuffle=True)

Pixel values → integers from 0 (black) to 255 (white)
Labels → y = 1 if the digit is “0”, y = 0 if “8” → model output = P(image is a 0)

is_zero_y_tr = (y_tr == 0).astype(float)

Scaling Inputs

Logistic regression is more stable with normalized inputs
Standard (mean/std) scaling → x’ = (x − μ) / σ
Min-max scaling → x’ = (x − x_min) / (x_max − x_min)

X_mean, X_std = X_tr.mean(axis=0), X_tr.std(axis=0)     # compute stats on TRAIN only!
X_min, X_max = X_tr.min(axis=0), X_tr.max(axis=0)
 
mm_X_tr = (X_tr - X_min) / (X_max - X_min + 1e-4)       # + 1e-4 avoids divide-by-zero
mm_X_te = (X_te - X_min) / (X_max - X_min + 1e-4)       # apply the SAME transform to test
ms_X_tr = (X_tr - X_mean) / (X_std + 1e-4)
ms_X_te = (X_te - X_mean) / (X_std + 1e-4)

Border pixels are always 0 → std/range = 0 → that’s why the tiny 1e-4 is there
Never compute scaling stats on test data → leakage

Grid Search: Scaling × Penalty × C

def fit_model(train_X, train_y, test_X, test_y, penalty, c):
    model = LogisticRegression(penalty=penalty, C=c, solver="liblinear")
    model.fit(train_X, train_y)
    pred = model.predict(test_X)
    return model, accuracy_score(test_y, pred), recall_score(test_y, pred), precision_score(test_y, pred)

Tried {min-max, mean-std} × {L1, L2} × C ∈ {0.02, 0.1, 1, 10, 50} → ~30 s to run
Results:
- Best accuracy + recall → min-max, L1, C = 1
- Best precision → mean-std, L2, C = 0.02

Visualizing Coefficients

model.coef_.reshape(28, 28) → plot as an image (blue = pushes toward “0”, red = pushes toward “8”)
Bright pixel in the very middle → strongly says “8” → makes sense, a 0 has a hole there
L1 model → most coefficients exactly zero (sparse) → L1 prefers few non-zero weights

Decision Boundaries on Blobs

from sklearn.datasets import make_blobs
X, y = make_blobs(n_samples=1000, n_features=2, centers=2, random_state=1)
lr = LogisticRegression(fit_intercept=True, penalty=None)   # bias, no regularization
lr.fit(Xtr, ytr)
lr.score(Xtr, ytr), lr.score(Xte, yte)                      # mean accuracy
 
DecisionBoundaryDisplay.from_estimator(lr, Xtr, response_method="predict", ...)        # hard boundary
DecisionBoundaryDisplay.from_estimator(lr, Xtr, response_method="predict_proba", ...)  # soft (probabilities)
lr.coef_, lr.intercept_

Hard boundary → two flat colors split by a straight line
Soft boundary → color fades near the line → probabilities near 0.5 there
More overlapping blobs (cluster_std=2, then 3) → lower accuracy, wider fuzzy band around the boundary → the line is still the best a linear model can do

Lecture 8: Logistic Classifiers 2 + Intro to Neural Networks

HW2 due Fri 10/23
Start forming project groups of 4

Story So Far

Predict binary y → model p(y = 1 | x) (p(y = 0 | x) = 1 − that, so no need to model it separately)
Logistic → z = θᵀx (unnormalized score) → pᵢ = σ(z)
Train → minimize L_BCE = Σᵢ −yᵢ log pᵢ − (1 − yᵢ) log(1 − pᵢ) → push the correct-class probability up
Gradient → ∂L/∂θⱼ = Σᵢ (pᵢ − yᵢ) xᵢⱼ
Sigmoid plot’s x-axis = the weighted sum z, not any single feature
Decision boundary → f = 0.5 ⟺ z = 0

Interpreting Logistic Classifiers

1-Feature Examples (how θ changes the curve)

f(x) = σ(θ₀ + θ₁x)

θ₀	θ₁	Effect
1	1	Normal S-curve, boundary at x = −1
0.3	0.3	Flatter → small θ = gradual, less confident
8	8	Steep, nearly a step → big θ = very confident
−40	8	Steep, boundary shifted to x = 5 (θ₀ moves it)
1	−1	Flipped → decreasing curve (negative θ₁)

Boundary for 1 feature → x = −θ₀/θ₁
|θ| → steepness/confidence; sign of θ₁ → direction; θ₀ → where the boundary sits

2-Feature Examples

Boundary → θ₀ + θ₁x₁ + θ₂x₂ = 0 → a straight line in (x₁, x₂)
Example 1 → overlapping classes → 74% accuracy
Example 2 → mostly separable → 96%
Example 3 → classes need a curved/circular boundary → 64% → linear model can’t do it

Weight Interpretation → same as Lecture 7 → sign = direction, magnitude = strength (Yelp words: “pleased”, “excellent” vs “worst”, “horrible”)

Comparing Classifiers

Baseline: Majority Classifier

Always predict the most common label (assume train/test label frequencies match)
Error = 1 − maxP (maxP = frequency of the most common label)
Not a real classifier, but a baseline → anything you build should beat it
- P(class 1) = 0.95 → majority classifier already has only 5% error
Example → 100 points: 60 class 1, 30 class 2, 10 class 3 → accuracy 0.6, error 0.4
C equally likely classes → error = 1 − 1/C = (C − 1)/C → 90% for MNIST, 66% for Wine

Classifiers So Far

Majority → baseline, high error
Binned → baseline, impractical for d > 10 or 20
Nearest centroid → simple boundaries
kNN → complex boundaries (depending on k)
Logistic → linear boundaries (so far)

	Majority	Binned	Nearest Centroid	kNN	Logistic
Prediction space	O(1)	O(Bᵈ)	O(Cd)	O(nd)	O(d)
Prediction time	O(1)	O(1)	O(Cd)	O(nd)	O(Cd)
Decision boundaries	None	Complex	Simple	Complex (small k)	Linear
Distance-based?	No	No	Yes	Yes	No
MNIST error	90%	?	~20%	~3%	~8%

Learning Curves

kNN → error keeps dropping toward 0 as you add data → it can approximate the optimal boundary better and better
Nearest centroid → flattens out at a high error → only simple boundaries no matter how much data

Extensions

K > 2 Classes → softmax over K scores (see Lecture 7) → loss term −log P(yᵢ = k | xᵢ)

Nonlinear Boundaries via Feature Expansion

Add x₁², x₂², x₁x₂, … → quadratic boundaries in the original space, same training
Problems:
- Which features do you add?
- More features → slower training/prediction, more memory
→ neural networks learn the features

Strengths / Weaknesses Recap

Strengths → easy to fit (convex loss, simple gradient), easy to interpret (one weight per feature)
Weakness → linear decision boundary

Neural Networks (Intro)

A Little History

Phase 1 (1950s–70s) → logistic-like models, no hidden units → enthusiasm died out
Phase 2 (1980s–2000s) → backpropagation invented → can train models with hidden units → but training slow, data scarce → died out again
Phase 3 (2010s–now) → deep learning works → (re)invention of stochastic gradient → commercial success, huge hype
ImageNet → benchmark with 10M+ images, 1000 classes → deep nets crushed it
Loosely inspired by neuron circuits in the brain

Building a Network from Sigmoids

One logistic unit = weighted sum + sigmoid → a computational unit
Two sigmoid units on the same input → two different “soft step” functions
Feed their outputs into another logistic unit → a simple neural network

x₁ ─┐      ┌─► h₁ = σ(w₁ᵀx) ─┐
    ├──────┤                 ├─► σ(b₀ + b₁h₁ + b₂h₂) ─► f(x)
x₂ ─┘      └─► h₂ = σ(w₂ᵀx) ─┘
  inputs     hidden units          output unit

Hidden Units

Hidden units = nonlinear functions of the inputs (not inputs, not outputs → “hidden”)
The nonlinearity (sigmoid here) = activation function (other options exist)
Hidden values get combined to make the output
→ neural nets = logistic functions stacked hierarchically

Wrapup

Logistic → extends to K classes; feature expansions give nonlinear boundaries, but how to pick features?
Neural networks → extension of logistic models that learns feature representations automatically

Lecture 9: Neural Networks

Midterm → covers up to logistic regression (no neural networks)

Study → lectures, HWs + solutions, discussions → exam tests understanding
In person, regular lecture hall + time, 50 minutes, starts once everyone’s seated
Pen/pencil only → closed book, no notes, no calculators/phones
Assigned seating by UCINetID → check Piazza
HW3 → released this week, shorter (because of the exam), all about neural nets

Basics of Neural Networks

What Can a Network Represent?

Single logistic with no weight on the 2nd feature → one soft step along x
2 hidden units combined → a bump (step up, then step down)
More hidden units → more bumps → approximate any shape
Universal approximation → as # hidden units → ∞, a single-hidden-layer network can represent any smooth function

As a Classifier

Nonlinear mapping: x (feature vector) → f(x | θ) (a number)
Output in [0, 1] via sigmoid → read as P(y = 1 | x)
Decision boundaries are nonlinear → more hidden units = more complex boundaries

Single Hidden Layer Network (a.k.a. feedforward network, multilayer perceptron / MLP)

d inputs → first layer of weights → M hidden units → second layer of weights → output
The extra 1’s → bias terms
θ = all weights from all layers → count = (d + 1) · M + (M + 1) = O(dM)
In NN-land, “parameters” are called weights

Example: 2 Inputs, 2 Hidden Units

       w₁₁
  x₁ ──────► h₁(x) ──b₁──┐
     \ w₁₂ /             │
      \   /              │
       \ / w₂₁           ├──► f(x;θ)   (output)
       / \               │
  x₂ ──────► h₂(x) ──b₂──┤
       w₂₂               │
  1 ── w₀₁, w₀₂          1 ──b₀──┘
  (input→hidden weights)  (output weights)

h₁(x) = σ(w₀₁ + w₁₁x₁ + w₂₁x₂)
h₂(x) = σ(w₀₂ + w₁₂x₁ + w₂₂x₂)
f(x | θ) = σ(b₀ + b₁h₁(x) + b₂h₂(x))
Computing any node:
1. Weighted linear combination of the previous layer (each node has its own weights)
2. Apply the nonlinearity (e.g. sigmoid)

Matrix Notation

x̃ = (1, x₁, …, x_d)ᵀ → (d + 1) × 1 column (augmented with the bias 1)
W = first-layer weight matrix → M rows × (d + 1) columns → row m = weights into hidden unit m
Wx̃ → vector of M weighted sums, one per hidden unit
h = g(Wx̃) → apply activation g element-wise → M hidden values
h̃ = (1, h₁, …, h_M) → augment with a 1 for the output bias
b = second layer as a row vector → f(x | θ) = σ(b · h̃)
Whole network → f(x) = σ(b · [1, g(Wx̃)])

More Complex Networks

Multiple Hidden Layers

2 layers → x →(W₁)→ h₁ →(W₂)→ h₂ →(b)→ output
Each layer can have a different number of hidden units
L layers, any width each → “deep” network = multiple hidden layers

Multiple Outputs (K classes)

Final layer has K outputs → normalize with softmax (same as K-way logistic) → kth output = P(y = k | x)

General Equations (L layers, K outputs)

First layer → h₁ = g(W₁x̃)
Each next layer → h_l = g(W_l h̃_(l−1)) for l = 2, …, L (recursive)
Output → zₖ = bₖ · h̃_L, then P(y = k | x) = softmax(z)ₖ

Examples

TensorFlow Playground → 2D input, 2 hidden layers → output heatmap over input space (try it → playground.tensorflow.org)
MNIST → K = 10, 784-dim input, 200 hidden units per layer
- Hidden unit weights (reshaped to 28 × 28) look like stroke/edge detectors; logistic weights look like blurry digit templates
Face recognition deep net → layers learn edges → face parts → whole faces
Before deep learning → humans hand-designed features, then trained a simple classifier on top → now the network learns the features

Network Architectures

Feedforward nets = layers of matrix-vector ops + nonlinearities → perfect for GPUs (built for linear algebra)
Real nets are fancier → residual connections, convolutions, attention, …

Network	Year	Size	Notes
AlexNet	2012	650k units, 60M parameters	ImageNet, 5 conv + 3 dense layers, 224×224×3 → 1000 classes, 1M images, 1 week on GPUs
GoogLeNet	2015	27 layers, ~4M parameters	Much deeper, “Inception” modules → fewer parameters
GPT-3	2020	175B parameters	Transformers / attention → ~800 GB just to store

Networks keep getting bigger and better

Number of Parameters (L layers, M units each, ignore biases)

p ≈ dM + (L − 1)M² + MK
- dM → input → first hidden layer
- (L − 1)M² → hidden → hidden
- MK → last hidden → K outputs
Example → d = 100 × 100 = 10⁴ pixels, M = 300, K = 1000, L = 10:
- 300 · 10⁴ + 9 · 300² + 300 · 1000 = 3,000,000 + 810,000 + 300,000 ≈ 4 million

Activation Functions

Output layer → usually softmax for classifiers
Hidden layers → modern default = ReLU (rectified linear unit) instead of sigmoid
- g(z) = max(0, z) → z > 0 → z; z ≤ 0 → 0
- Why popular → behaves better for gradient descent than sigmoid; fast + sparse to compute
Why need activations at all? → without them every layer is linear → a stack of linear layers is still linear → no better than one linear layer
- With them → hidden units learn nonlinear representations
Many others exist (tanh, leaky ReLU, …) → choosing is very empirical → run experiments

Training Neural Networks

Loss: Cross-Entropy (log-loss)

L(θ) = (1/n) · Σᵢ −log fₖ(xᵢ; θ) where k = true label yᵢ
Minimizing −log P pushes P → 1 → push the network toward probability 1 on the correct class for every training point

Gradient Descent Again

θ_new = θ − λ · ∇L(θ)
f is now a whole network → partial derivatives are way messier than logistic
…but it’s just the chain rule applied over and over

Backpropagation

Forward propagation → compute the output f(xᵢ; θ) for every training point with current θ
Backward propagation → use outputs + yᵢ to push gradient info back layer by layer to every weight (uses the network structure)

Backprop = an efficient way to compute all the partial derivatives → “backprop = gradient descent for a neural network”
Details next lecture

Convexity

Logistic + log-loss → convex → one global minimum
Neural nets → non-convex, even with a single hidden unit → local minima → price of a more complex model
In practice → large datasets (n ≥ 10⁵) → gradient descent works remarkably well; small datasets (n < 10⁴) → local minima matter more

Cost of a Gradient Update

Forward pass per data point → at least O(p) (each parameter is in at least one multiplication)
Over all n points → O(np) for one update
n = 1M images, p = millions, 100s–1000s of updates → plain gradient descent is very slow

Stochastic Gradient Descent (SGD)

Full gradient → ∇L(θ) = (1/n) · Σ₍ᵢ₌₁₎ⁿ ∇(−log fₖ(xᵢ; θ))
Idea → replace the full sum with a much smaller, noisier sum over a random (mini)batch of b examples:
- ∇L_b(θ) = (1/b) · Σ₍ⱼ₌₁₎ᵇ ∇(−log fₖ(xⱼ; θ)), with b ≪ n (e.g. b = 1, 10, 100)
Advantage → each update costs O(bp) instead of O(np) → way faster
Disadvantage → not the exact gradient → a noisy (stochastic) approximation
In practice → works very well; theory → still converges to a local minimum like regular GD
SGD = the default way to train neural networks
Contour picture → GD takes a few big, smooth steps; SGD takes many cheap, zig-zaggy steps that still head downhill

SGD in Practice

Same algorithm as GD, only the gradient computation changes
Random batches matter → shuffle the n points once, then walk through them b at a time
Batch size b → heuristic, or tune it as a hyperparameter on validation data
Works with any gradient-based model, but shines with large n and large p (small n/p → plain GD may be better)
Terms:
- Batch / minibatch size b → examples per update
- Epoch → one full pass through all n examples
- n = 1000, b = 100 → 10 updates per epoch
- “Train for 3 epochs” = go through the dataset 3 times

SGD vs GD on MNIST (n = 60k, d = 784, M = 256, K = 10, p ≈ 203,000)

b = 4 and b = 64 → SGD’s loss drops way faster in wall-clock time; GD hasn’t even finished its first update by the time SGD has made big progress
Loss curves for SGD are noisy (small b = noisy gradients) but clearly trend downhill
Same story for a plain logistic classifier on MNIST, and for a huge text problem (d = 47k word features, n = 781k docs)

Hyperparameters vs Parameters

Parameters θ → weights/coefficients the model learns
Hyperparameters → settings we control:
- k in kNN
- Regularization weight α + type (L1, L2, …)
- Batch size b
- Architecture → # layers, layer sizes, activation type
- Learning rate
Tuning → by hand (intuition, experience) or use data:
- Train → fit θ for a given hyperparameter setting
- Validation → compare settings
- Test → final accuracy
- Grid search on validation data is common but computationally expensive

Complexity + Overfitting

Fundamental tradeoff → more complex models fit training data perfectly but can do worse on new data
For NNs → more parameters = more complex
Same U-shaped picture → training error keeps falling, test error falls then rises → ideal complexity in between
Spectrum → logistic regression (simplest) → “shallow” neural nets → large deep nets (most complex)

Wrapup

NNs = feature extractors → internal representations learned from data
Tons of parameters → 10s of millions in 2012 (AlexNet) → ~100 billion now
Tons of hyperparameters → # hidden units, # layers, activations, + more
Next → backprop + SGD in detail

Ivan's CS Notes

Explorer

ICS_178

Lecture 1: Introduction

Course Organization

Supervised Learning

Data Exploration

Lecture 2: Linear Regression

Discussion 1: Setup + NumPy Arrays

Lecture 3: Gradient Descent + Nonlinear Regression

More on Gradient Descent

Nonlinear Regression

Model Selection

Cross-Validation

Discussion 2: Matplotlib + Scikit-Learn

Lecture 4: Regularization + Classification

Regularization

Classification

Feature Means + Distances

Nearest Centroid Classifier

Evaluating Classifiers

Lecture 5: Nearest Centroids (Part 2) + kNN

Classifier Evaluation

k Nearest Neighbors (kNN)

Time + Space Complexity

Discussion 3: Feature Vectors, Centroids, Decision Regions

Lecture 6: kNN Recap, Curse of Dimensionality, Probability Review

The Curse of Dimensionality

Probability in ML

Lecture 7: Logistic Classifiers

Logistic Classifiers

Binary Cross-Entropy Loss

Gradient for Logistic Classifiers

Additional Topics in Logistic Models

Discussion 4: Logistic Regression on MNIST + Decision Boundaries

Lecture 8: Logistic Classifiers 2 + Intro to Neural Networks

Interpreting Logistic Classifiers

Comparing Classifiers

Extensions

Neural Networks (Intro)

Lecture 9: Neural Networks

Basics of Neural Networks

More Complex Networks

Network Architectures

Training Neural Networks

Complexity + Overfitting

Graph View

Table of Contents

Backlinks