Introduction to Machine Learning

FS2026

Simplified diagram of machine learning

Supervised Learning - Definition

Learning with training data that contains inputs together with correct outputs (= labels). The Goal here ist to predict the correct output.

Unsupervised Learning - Definition

Learning with training data that contains only inputs and no labels. The Goal here is to discover useful structure in the data.

Examples of supervised learning:

Classification, Regression, Structured prediction

Examples of unsupervised learning

Clustering, Anomaly detection, Dimensionality reduction, Generative Modeling

Simplified diagram of supervised learning:

Prediction y can also be called y^, or f^(x)

Simplified diagram of unsupervised learning:

Goals of unsupervised Learning: 2 concepts

1) Describe new input x relative to training data (is it similar, is it an anomaly?, etc.)
2) Generate new data x’ that looks similar to training data (Generative modeling)

Machine Learning Pipeline for linear Regression

Linear Regression is always linear functions, squared loss, closed-form, no matter the dimension

Difference House Prices (Linear Regression) example between 1 Dimension and d Dimensions

1D: We only have one attribute x (x is 1D) → E.g. x = (size)
dD: We have d attributes → x is dD → E.g. x = (size, #bathrooms, …, years since construction)

How can the linear function class be represented in 1d?

Linear function equation:

f(x) = w0 + w1*x with w0: y-Achsenabschnitt, w1: Steigung

Linear Regression:

Function Class F: Linear Functions

Training Loss L: Squared Loss

Optimization: We can use closed Form solution

Characteristics of different Losses: Squared, Huber, Asymmetric

Squared Loss: Symmetric → Overestimation and Underestimation are treated equally, large penalty on outliers (because grows quadratically)

Huber Loss: Ignores outliers

Asymmetric Losses: Weigh over- and underestimation differently

Feature Vector x in 1D:

X = (x1, …, xn) mit x1, …, xn 1D

E.g. x_i = (size)

Feature Vector x in dD:

X = (x1, …, xn) mit x1, …, xn dD

E.g. x_i = (size, #bathrooms, …, years since construction)

Linear Regression Closed Form:

w = (X^TX)^(-1)X^Ty

What changes if we use nonlinear regression?

Function Class F: We can use nonlinear functions

Optimization: Gradient Descent can be used (it’s always used when there is no closed form or closed form is computationally expensive)

General Form of nonlinear functions in ML Pipeline:

Some ML models have fixed phi (linear regression, kernel regression, etc.), phi maps d dimensions (from input) to p dimensions

Nonlinear in x, linear in phi

Matrix notation of loss L(w) of nonlinear function (also squared loss)

Why can/can’t we use closed form for nonlinear functions?

We can use it, we only have to replace X matrix with Phi matrix.
Problem: Phi^TPhi can have a high computational cost to compute and there is a lack of generality for different losses (other than squared loss)

→ That’s why we need gradient descent

What do we use Gradient Descent for?

It’s a general iterative algorithm to minimize our loss L(w) and thus find out our weight vector w for our model f.

Gradient Descent in 1D: 1. In which direction do we move? 2. How far in that direction? 3. When should we stop?

1. In direction of sign of negative derivative at w_now

2. nü~ = nü*|L’(w_now)| → In direction of nü

3. Stop when it can’t improve much anymore, so for example when: |L(w_now) - L(w_previous)| <= epsilon

What changes when we execute Gradient Descent in nD than in 1D?

For minimizing L(w) we have multiple directions in which to go to. → We need gradient (because gradients point in direction of steepest descent)

Geometric Intuition of contour lines in relation with Gradient Descent:

• Steepest direction is orthogonal to contour lines

• Direction of steepest increase: ∇L(w)

• Direction of steepest decrease: -∇L(w)

What does hold on contour lines?

On those lines the loss has the same value.

Gradient Descent algorithm:

True or False: We can use machinery from linear regression to solve regression in nonlinear function spaces by just replacing the data matrix 𝑋 by the feature matrix Φ

True

How can we rewrite the Squared Loss in matrix notation?

Which of the following statements are true?
(A) All convex functions have only one local minimum that is a global minimum
(B) For convex functions, all stationary points are local minima
(C) For convex functions, all stationary points are global minima

(B) and (C) are true immediately if you plug in ∇𝐿 𝑤 = 0 in first order condition

Relation Convexity and global/local minima

Why does Gradient Descent work for linear Regression?

Because linear Regression with squared Loss is a convex problem. Convergence is only guaranteed for the convex case. (otherwise we can get stuck in local minima or diverge to infinity)

What holds for the 2 norm squared?

What is Conditioning?

It tells us how nicely shaped the loss landscape is. If the contour lines (= same loss values) are more spheres we have a well conditioned case, and if they are more ellipses we have an ill conditioned case.

Well-conditioned case of GD?

λmax ​≈ λmin​, contour lines are almost circles, loss equally steep in all directions, GD works

Ill-conditioned case for GD

λmax​ » λmin, contour lines are stretched ellipses, one direction very steep, the other flat → small stepsize: slow in flat direction, large stepsize: oscillations in steep direction
→ Solution for ill-conditioned case → use Momentum/accelerated methods​

Momentum/accelerated methods to find minima:

Momentum speeds up flat directions, speeds up GD (Gradient Descent)

Why SGD (Stochastic Gradient Descent)?

It uses a different loss than GD (not gradient over all points but only on a random subset of points, which is called mini batch with batch size |S|). This saves memory, when the batch size is smaller than n
→ works because minibatch gradient is correct on average (Expectation value)

Full batch GD, Original SGD, Minibatch SGD?

Full batch: |S| = n, Original: |S| = 1, Minibatch: 1 < |S| < n (Full batch = normal GD)

Effect on batch size in SGD?

|S| small → cheap but noisy, but this can sometimes also escape saddle points

|S| large → expensive but stable (closer to GD, can more and more get stuck in stationary points)

What is convexity? Explain with the 3 conditions.

Function is convex if it has a “bowl shape”.

0-th order condition: Real function always below linear connection of two random points.

1-st order condition: Tangent of two points always below function.

2-nd order condition: Curvature is always non-negative .

What is strong convexity?

Stronger than convexity. It holds: strong convex → unique global minimum, It means that the loss landscape is curved enough so that there is only one best solution.

Characterize the following functions:

Training Loss, Generalization Error and Estimation Error?

Training Loss: Measures error on trainings data D. L(f;D)

Generalization Error: Measures expected error on new data. L(f;P) (P is the joint distribution that we assume our test data is drawn from and our trainings data is randomly sampled from)

Estimation Error: Measures how far the learned model is from the ideal model f*.

Linear Regression, what underparametrized case, overparametrized case and n=d mean for the errors and amount of solutions for our problem.

Underparametrized n>d: More samples than parameters, if we increase n our model sees more data and thus the effect of noise gets averaged out, Estimation Error shrinks, usually unique solution

Overparametrized n<d: More parameters than samples, More DoFs than constraints from Data → infinitely many solutions, Training error can be zero, b.c. we can fit data perfectly

n=d: Possibly a unique solution

Main Message: More samples usually help, but in high dimensions (n<d) many different models can fit the training data perfectly, and not all of them generalize well.

Definition Model complexity

means how flexible the function class F is. F0 = constant functions, F1 = linear, F2 = quadratic, etc.

Higher model complexity → more flexible functions → Fit data better → Training error shrinks

Definition Underfitting

Model is too simple and can’t capture the true relationship.

Definition Overfitting:

Model is too complex and fits random noise in training data.

Overview: Relationship model complexity vs. Training/Generalization Error

Sources for generalization error:

Bias, Variance, Irreducible noise

→ Important: Generalization Error can exist without noise because of Bias and Variance, from not being able to fit the function (bias) and/or from seeing only few samples (Variance)

Bias-Variance tradeoff in choosing model complexity

Simple Models: High Bias, Low Variance

Complex Models: Low Bias, High Variance

Good Models: Balance

Definition Bias and Variance with pictures in mind

Bias: Distance between average over all different models for different data sets D1, D2, .. and ideal model f*

Variance: Summarized Distance between individual models fD and average over all models.

Behavior Model Complexity vs. Generalization Error, Variance, Bias

Training Loss and Generalization Error. Problem?

If we had access to joint distribution P, we could just compute generalization error (what we care about), but we only have data set D.

Problem: Training Error is too optimistic for estimating generalization error. Because model was explicitly chosen to minimize this error.

Main Idea to find a good model and a good estimate on generalization error of this model fD?

Split data into training data, for model training, and test data, to evaluate generalization error.

Definition Model Selection:

Which method M should we use to obtain a model that predicts well on unseen samples? Different models → different hyperparameters (= learning rate, batch size, polynomial degree, etc.)

Definition Model Evaluation:

Get sense for how well model f does in predicting unseen test samples.

For what is D_train, D_validation and D_test?

D_train: Used to fit model parameters

D_validation: Used to choose the best model bzw. the best hyperparameters

D_test: Used to estimate final generalization error

Which problem does cross validation solve?

When we have a too small dataset and its too wasteful to set aside both validation and test set.

How does k-fold cross validation work?

Given: Different Models, Amount of folds K, Dataset split into D_use and D_test

Goal: Find best Model

1) For each model: Split D_use into K folds, Use one fold as D_validation and other K-1 as D_train, Compute Validation Error for each fold → L_K(model), After all K folds, average the validation Error to get CV Error

2) In the end for each Model we have the CV Error

3) Choose Model with lowest CV Error

How can we control model complexity (such that we don’t overfit)?

Regularization

→ Smaller degree m

→ Smaller number of monomials active by limiting l1-norm (Lasso Regression)

→ Penalty on big weights by limiting l2-norm (Ridge Regression)

How does Bias and Variance change if we have stronger regularization (= bigger λ)

Comparison Lasso vs. Ridge Regularization:

Lasso: Limits L1 norm (= absolute value of w) → encourages sparsity, because l1 penalty can set coefficients exactly to zero. Removes features.

Ridge: Limits L2 norm (= Length of vector w) → shrinks coefficients smoothly but usually does not set them to zero. Shrinks features.

Labels in Regression vs. Labels in Classification:

Regression: Labels y are continuous in R

Classification: Labels y are discrete (Multiclass more than two labels options and binary = 2)

What is a Decision Boundary

In Linear Binary Classification, where f(x) = 0 and there is a transition to one label to the other

What properties do we need for losses such that they are good for training? Which Loss is not usable for training?

• Decreasing

• Convex in its arguments

• Differentiable
  → 0-1 Loss is not differentiable and not convex and therefore not suitable for training

Comparison Exponential Loss and Logistic Loss:

Exponential: Large penalty for mislabeled “outlier” points “far away” from boundary

Logistic: Less prone to noisy outliers

Is Training Loss with logistic loss convex?

Yes, but it depends if it has unique solution → Depends on if data linearly separable or not

What happens when GD minimizes logistic loss on linearly separable data?

The logistic loss can go closer and closer to zero by increasing ∥w∥.

GD does not converge to a finite w.
But it converges in the direction of the max margin solution

What is the max-margin classifier?

It chooses the separating hyperplane with the largest minimum distance to the training points.

What is the margin?

It measures the distance of the closest training point to the decision boundary.

Large margin means better separation.

What is hard-margin SVM?

Hard-margin SVM is for linearly separable data.

It finds a separating hyperplane with maximum margin.

What is soft-margin SVM?

Soft-margin SVM is for not linearly separable data.

It allows margin violations using slack variables.

Binary Classification

Logistic Loss

Solution is (B): Because in (A) the red line does not separate anything. Thus this cannot be one vs. rest

Multiclass Classification:How can we naively train a model that classifies K classes?

One vs. Rest: For each class k in K, relabel class k as one class and the rest as the other class, then train a binary classifier → Results in K binary classifiers for K classes

Multiclass Classification: How can we train a model that classifies K classes simultaneosly?

By choosing Cross-Entropy Loss (=L_CE) as our loss.
L_CE small → True class score f_y(x) much larger than all others → we found correct label y

L_CE large → Other class has larger score → We didn’t find correct label y

Cross-entropy Loss with K = 2 corresponds to what?

Logistic Loss

Which Losses do we often take in binary classification and which in multiclass classification?

Binary: Logistic Loss

Multiclass: Cross-entropy Loss

Statistical model for training and test data. How can we graphically represent the marginal distribution P_x, Conditional distribution P_Y|x and joint distribution P?

What holds for the best labeling function y*(x)?

What is a robust generalization?

Asks whether a classifier still performs well, when the test distribution changes and is not the same anymore as the train distribution.

What is a Distribution Shift?

When P_train is not equal to P_test anymore

What is worst-group generalization?

Instead of only asking “How good is the model on average?”, we ask “How good is the model on the group (=subset of data) where it performs worst?

What is an Asymmetric Loss?

A Loss in which not all classification errors are equally bad. Sometimes it is worse if we have many FP (= False Positives) or FN (= False Negatives).

What are the two approaches for introducing asymmetric Losses?

1. Weighted training loss: Train the model with different weights for different error types: L = c_FP*FPR + c_FN*FNR

2. Threshold Tuning: Train one model f(x), then choose a threshold τ. Depending on τ we have a different classifier: y = +1 if f(x) > τ, y = -1 else.
   Changing τ changes the tradeoff between FP and FN

What is ROC curve?

Curve that shows tradeoff between TPR and FPR for all thresholds τ.

Binary Classification Pipeline vs. Multiclass Classification Pipeline

Binary: K = 2 → Cross-Entropy Loss = Logistic Loss and we only have ONE model

Problem of feature maps ϕ and motivation for kernel trick:

We apply a transformation ϕ on x, if x is not linearly separable. With the transformation, we move it to a higher dimensional space, in which the data becomes linearly separable.
Problem with this is: For polynomial features in high dimensions, ϕ becomes enourmous and feature construction thus computationally impossible.

→ Solution: Kernel Trick

What is the Kernel Trick?

Key Insight: We only need dot products <ϕ(x),ϕ(y)> in feature space. We define Kernel Functions K(x,y) = <ϕ(x),ϕ(y)> that replaces computation in feature space.

What is the goal of the kernel trick?

To learn nonlinear models without explicitly computing huge nonlinear feature vectors

What is a kernel?

A kernel is a function:

k(x,z)

that computes an inner product in feature space:

k(x,z)=⟨ϕ(x),ϕ(z)⟩

without explicitly computing ϕ(x).

What is the kernel matrix?

The kernel matrix K contains all pairwise kernel values between training points:

Kij=k(xi,xj)

What are the three steps of kernelization?

Express model f with Kernel Matrix:

Before: f(x) = ∑​i=1,…,n α_i*​K(xi​,x)
Now: f(X) = Kα

Goals for nonlinear functions:

1. More expressivity: We want functions that can fit most data

2. Computational Efficiency: No explicit computation and storage of ϕ

3. Convex Optimization: Then optimization is easier and more reliable

Example Kernel Functions:

1. Linear Kernel: k(x,z) = x^Tz → corresponds to original feature space ϕ(x) = x

2. Polynomial Kernel: k(x,z) = (1 + x^Tz)^m → corresponds to polynomial features up to degree m

3. RBF/Gaussian Kernel: k(x,z) = exp(- (||x - z||²)/tau) → corresponds to a very rich, infinite dimensional feature space (tau = bandwidth parameter)

Nonlinear Regression vs. Kernelized Regression