Introduction to Deep Learning

1. Fundamental Definition of Machine Learning

Tom Mitchell (1997) provided a concise definition of machine learning:

A computer program is said to learn from experience E with respect to some task T and performance measure P, if its performance at task T, as measured by P, improves with experience E.

Illustrative Examples:

• Handwriting Recognition:

  • Task (T): Classify handwritten characters
  • Performance (P): Accuracy of classification
  • Experience (E): Database of labeled handwritten words

• Autonomous Driving:

  • Task (T): Navigate and control a vehicle
  • Performance (P): Distance traveled before human intervention
  • Experience (E): Recorded videos and steering commands

• Chess Playing:

  • Task (T): Play chess strategically
  • Performance (P): Win rate against opponents
  • Experience (E): Database of self-play games

Major Categories of Machine Learning Tasks:

• Supervised Learning:

  • Classification
  • Regression

• Unsupervised Learning:

  • Clustering
  • Dimensionality Reduction
  • Density Estimation

• Advanced Paradigms:

  • Self-supervised Learning
  • Reinforcement Learning

Deep Learning is a specialized subfield of machine learning that employs neural networks with multiple layers to solve complex tasks, particularly excelling in supervised learning scenarios.

2. Supervised Learning: Core Concepts

Supervised learning involves learning a function f: X → Y from labeled pairs (x, y).

• Input Space: X, typically represented as ℝ^D (D-dimensional real space)
• Output Space: Y (discrete for classification, continuous for regression)
• Goal: Develop a hypothesis h(x) that closely approximates f(x)

Primary Types:

Classification:

• Binary Classification: y ∈ {0,1} or {−1, +1}
• Multiclass Classification: y ∈ {1,2,…,C}
• Multilabel Classification: Categories not mutually exclusive

Regression:

• Output y ∈ ℝ (continuous values)

Real-World Applications:

• Iris Dataset Classification: Distinguishing between Setosa, Versicolor, and Virginica species
• Image Classification: Mapping RGB pixel arrays to categorical labels
• Rubik’s Cube Orientation: Regression problem for spatial positioning
• Medical Diagnostics: Melanoma detection using transfer learning techniques
• Protein Structure Prediction: AlphaFold’s approach combining deep CNNs with transformers

3. Unsupervised Learning: Discovering Hidden Patterns

The primary goal is to learn the underlying distribution of input data without explicit labels.

• Dataset Structure: D = {xₙ}, with no target values
• Evaluation: Performance measures guided by inherent biases (e.g., clustering structure)

Self-Supervised Learning:

A powerful approach that constructs pseudo-labels from the data itself, such as predicting the next word in a sentence.

Notable Examples:

• Generative Image Synthesis: Using Generative Adversarial Networks (GANs)
• Large Language Models: Systems like ChatGPT trained on massive text corpora using (context, next word) prediction pairs

4. Curve Fitting: A Fundamental Regression Example

Task Definition:

Predict target value t from scalar input x (e.g., sin(2πx) + noise)

Model Formulation:

Polynomial representation: y(x, w) = ∑ wⱼ x^ⱼ

• Linear with respect to parameters w
• Non-linear with respect to input x

Error Measurement:

Squared Loss Function: E(w) = ½ ∑ (y(xₙ, w) − tₙ)²

• Minimization yields a closed-form solution

Model Complexity Considerations:

• Underfitting: Models that are too simple (M = 0 or 1) fail to capture underlying patterns
• Overfitting: Excessively complex models (M = 9) memorize noise rather than learning generalizable patterns

Detecting Overfitting:

• Utilize a separate test set
• Calculate Root Mean Square Error (ERMS): ERMS = sqrt(1/N ∑ (y(xₙ) − tₙ)²)

Strategies for Controlling Overfitting:

• Data Augmentation: More training data leads to better generalization
• Regularization:
  • Modified error function: Ẽ(w) = E(w) + (λ/2) ||w||²
  • Penalizes large weight values
  • Regularization strength controlled by parameter λ

Model Selection Process:

• Hyperparameters: λ (regularization strength), M (model complexity)
• Selection Methods: Validation set or cross-validation
• Important Caution: Avoid direct optimization of λ and M on test data to prevent meta-overfitting

Probabilistic Framework

Motivation

ML models face uncertainty. Application of machine learning implies dealing with uncertainty. No machine learning model can achieve a perfect accuracy

• Epistemic uncertainty or systematic uncertainty. uncertainty due to observing finite size of datasets. This uncertainty can be reduced with more data.
• Aleatoric uncertainty or intrinsic uncertainty or stochastic uncertainty. uncertainty due to inherent randomness in the data. Happens because our observation can only capture partial information about the world.

Probability Theory

Probability Theory. Handling uncertainty requires the framework of probability theory

Frequentist view of probability. Probability is the proportion of the frequency of an event happening in the limit of an infinite number of trials.

• Suppose an unfair coin is tossed a large number of times such that 60% of the time, the head-side faces up, and 40% of the time, the tail-side faces up. Then the probability of getting a head is 0.6.

Bayesian View of Probability. Probability is the quantification of uncertainty.

• In the above example, we are not allowed to look at the coin and do not know which side is heads and which is tails. If asked to bet on whether the coin will land heads or tails, we would bet that the probability of seeing a head is 0.5.
• In the absence of additional information, the above is the rational choice — whether the heads or tails occur is not itself a repeatable event, it simply unknown.
• We simply assign a “score” indicating our belief about the event.
• Uncertainty of our belief can be lowered once we observe more data.

Joint Probability $P(X, Y)$. Probability of $X=x$ AND $Y=y$ denoted as $P(X=x, Y=y)=p_{X,Y}(x, y)$

Conditional probability $P(X\mid Y)$. Probability of $X=x$ given $Y=y$ denoted as $P(X=x\mid Y=y)=p_{X\mid Y}(x\mid y)$

Marginal probability $P(X)$ Probability of $X=x$ obtained via sum rule, denoted as $P(X=x)=p_X(x)=\sum_{y}p_{X,Y}(x, y)$ for discrete case or $\int_{-\infty}^\infty p_{X,Y}(x, y)dy$ in continuous case.

Product rule $P(X=x, Y=y)$. $P(X=x, Y=y)=p(Y=y\mid X=x)P(X=x)$.

Probability Distribution. A probability distribution for a random variable X is “complete specification of a way to compute probabilities of events about X.” It specify probability mass function (pmf) for discrete case and probability density function (pdf) for continuous case. Typically, pmf or pdf also depends on a set of parameters that governs the shape of pmf/pdf. Keep in mind that pmf/pdf must satisfy the requirement that they are nonnegative and normalized (their sum/integrate to 1 over all their support set). If a distribution is not normalized, it is called improper.

Bayes Theorem. The core principle in bayesian statistics, how do we measure belief after seeing some data (which is learning in some sense).

For those who confuse likelihood and probability, here are genius explanation from my bro ChatGPT.

Likelihood and probability look similar but are conceptually different depending on the context. Whether we call $P(X\mid Y)$ the likelihood depends on what is fixed and what is variable.

Independent Event.

If the posterior probability equal to prior probability (Additional information does not change the prior probability), then $X$ and $Y$ are independent.

Expectation. Expectation of some function $f(x)$ is the weighted average of $f$ under a probability distribution $p(x)$.

$\mathbb E_{p(x)}[f(x, y)]$ indicates expectation of a function over several variables, and the subscript $p(x)$ denotes the distribution under which the expected value of the function is computed. In this case, $\mathbb E_{p(x)}[f(x, y)]$ becomes a function of $y$.

Conditional Expectation. Conditional expectation is defined w.r.t. a conditional distribution $p(x\mid y)$.

Variance. Variance of $f(x)$ measures how much the value of $f$ varies over all possible values of $x$ under a certain $p(x)$.

Covariance. measure the extent to which the two variables vary together.

If x and y are two vectors of random variables, their covariance is a matrix

Note that $Cov(x, x) = Var(x)$

Example distributions

1. Uniform
2. Exponential
3. Laplace
4. Gaussian

Likelihood

Probability vs Likelihood. Probability is the chance that a particular outcome occurs based on the values of the distribution parameters. When calculating probability, we assume that the parameters are trustworthy. Likelihood is how well a sample/data provides support for particular values of the distribution parameter. When calculating likelihood, we’re trying to determine if we can trust the parameter values based on the data that we observe.

In continuous case, we use pdf $f$ which interpreted as density where in discrete case we use pmf $p$ which interpreted as true probability. The integral of the likelihood over all parameter values may not be equal to 1.

Computing Likelihood. Given dataset $\mathcal D={x_1,\dots, x_N}$ that is i.i.d (independent and identically distributed), the likelihood is computed as

Product/multiplication of large number of small numbers can be problematic. So we often work with log-likelihood.

Density estimation aka Parameter Estimation. Task of estimating the distribution, given a finite set of observations. Ill-posed because there are infinitely many distributions that could have generate the observed finite dataset.

One solution (among others) for density estimation is maximizing likelihood of the parameters with respect to the given dataset. Parameters obtained by likelihood maximization are usually called maximum likelihood estimators.

Information Theory

Shannon’s idea: relate information content to degree of surprise. It view that Surprise $\iff$ Rarity and Rarity $\iff$ Contains more information.

Measuring information. Suppose, for a discrete RV $X$, we observe that $X = x$ for a particular $x$, how much information do we receive? Let $h(x)$ be the measure of information.

1. h(x) should be additive. If two unrelated facts x, y occur at the same time, the surprise seeing both of them should be the sum of the individual surprises. So,

But, x and y are unrelated, hence also independent. So, $p(x, y) = p(x)p(y)$ and $h(x)$ should be logarithm of $p(x)$.

2. $h(x)$ should be monotonic in the opposite direction to $p(x)$. $h(x)$ increases iff $p(x)$ decreases.

We obtain,

Entropy: expected amount of information. Entropy H[x] of x: expected amount of information (i.e., amount of surprise) over all possible outcomes of x under distribution of x, which is p(x):

Entropy can also be understood as a measure of uncertainty of a system.

Minimum and Maximum Entropy Problem. The minimum of H[p] is H[p] = 0 that happens when there exists some $x_i$ such that $p(x_i) = 1$ while $p(x_j) = 0$ for the other $x_j$‘s. Its maximum however, is harder and more useful, choosing the most unbiased distribution given what you know.

• If you know nothing about a discrete variable, use uniform distribution (max entropy under no constraint).
• If you know mean and variance, Gaussian has max entropy among all distributions with that mean and variance.
• If you only know a positive support and expected value, Exponential distribution is max entropy.

Solving Maximum Entropy Problem using Langragian Contrained Optimization.

We aim to solve for $p(x_i)$ (discrete case) that maximize following objective

See that contrained $g(x)$ is to kept them under probability axiom (sum to 1). In the end, we would have something like $p(x_1)=p(x_2)=\dots=p(x_n)=\exp(\lambda-1)=1/K$. In other words, H[p] is maximum when p(x) is a uniform (discrete) distribution.

Entropy for continuous variable. We can extend entropy to continous variables as differential.

One can show using calculus of variations and Lagrange function that the distribution that maximizes the differential entropy is the Gaussian.

Cross Entropy. Cross-entropy measures the difference between two probability distributions: the true distribution $p(x)$ and the predicted distribution $q(x)$. It tells you how many “nats” or “bits” you need to encode data from $p(x)$ using the coding scheme designed for $q(x)$.

Note that we use parentheses for cross entropy instead of square brackets.

Expression above is the same as saying how many bits (or nats) you need to encode data from $q(x)$ using the coding scheme designed for $p(x)$. In machine learning, the message corresponds to the true (unknown) distribution of the prediction outcome, while the code corresponds to the approximating distribution of the prediction obtained by the model.

Kullback-Leibler (KL) Divergence. The average additional amount of information (in nats) needed to specify the value $x$ (using the approximating distribution $q(x)$), is given by:

KL divergence can be interpreted as a measure of dissimilarity between two distributions $p(x)$ and $q(x)$.

KL Divergence and Likelihood. If training data comes from the unknown distribution $p(x)$, we approximate $p(x)$ using some parametric distribution $q(x|\theta)$. $\theta$ can be determined by minimizing $\mathbb {KL}(p||q)$ but $p(x)$ is unknown. Since we have training data $\{x_i\}$ drawn from $p(x)$, we can estimate as a finite sum over these points.

log $p(x_i)$ is independent of $\theta$ and $q(x_|\theta)$ is negative log-likelihood. Therefore minimizing $\mathbb{KL}(p||q)$ is equivalent to maximizing log-likelihood $\theta$ of $q$. In deep learning, KL-divergence is usually used in variational autoencoders, generative adversarial networks, and diffusion models.

Linear Regression

Task. Predict continuous target t from input $x\in R^D$

Model.

Basis Function. Linear in weights, but not necessarily in inputs.

• Polynomial $\phi_j(x) = x^j$
• Gaussian $\phi_j(x) = \exp\left(-\frac{(x-\mu_j)^2}{2s^2}\right)$
• Sigmoid $\phi_j(x)=\sigma\left(\frac{x-\mu_j}{s}\right)$
• Fourier and Wavelet bases

Probabilistic Modeling. Assume noise in targets $t$ such that

Where

Probabilistically, we can write

Given a dataset of inputs $X=\{x_1,\dots, x_N\}$ with corresponding targets $t=(t_1,\dots,t_N)^T$ where data points are i.i.d. The likelihood of parameters $w, \sigma^2$ defined as

if $\sigma^2$ is assumed to be fixed/constant, maximizing the log-likelihood above is equivalent to minimzing the sum-of-squares error.

The maximization of the log-likelihood in previous equation is done with respect to two parameters: $w$ and $\sigma^2$, leading to solutions for both defined as:

Both are called maximum likelihood estimators for the model. For homoskedastic linear regression model, $\sigma^2$ is actually assumed to be constant, leading to $w_{MLE}$ as a least-square solution to the sum-of-squares error.

Design Matrix. Is a matrix $X\in R^{N\times D}$ for number of data $N$ and feature dimension $D$. The basis function $\phi: R^N\to R^M$ is applied to each row of $X$ to yield a (row) vector of length $M$. $\vec y=[y_i]_i$ is also commonly used together with Design Matrix.

Maximize log likelihood. We will try to solve this using gradient in a closed form style, make it equal to 0. We will solve it in design matrix form $\Phi \in$.

This is normal equation: $w_{mle} = (\Phi^T\Phi)^{-1}\Phi^T t$. Can lead to numerical difficulties when $\Phi^T\Phi$ is close to singular. Can be addressed using SVD or sequential or online stochastic gradient descent algorithms.

Regularized Least Square Solving for Overfitting Problem. We change the objective to minimize for

We use $\ell_2$ regularizer for $E_w$. This method also called as weight decay allowing our models to turning off some of the parameters $w$.

Multiple Regression. Conditional distribution of the $K$-dimensional target vector $\vec t$.

The above Gaussian has:

• a $K$-dimensional vector mean $\mu = W^T\phi(x)$,
• a K × K covariance matrix $\Sigma = \sigma^2 I$, required to be positive-semi definite — the notation $|\Sigma| = |\sigma^2 I|$ represents the determinant of $\Sigma$.

The Gaussian is assumed isotropic: equal variance in each dimension (thus equal density in every direction) and all dimensions are independence. So, the shape will be spherical and aligned at all axes.

Decision Theory

Approximating Distribution to Decision Probablistic model $p(t | x, w_{ML}, \sigma^2_{ML}) = N (t | y(x, w_{ML}), \sigma^2_{ML})$ is a predictive distribution expressing uncertanity over value of t for some new input x. But often we need to predict specific value for t, rather than returning the distribution, especially if we must take a specific action. Example, If our aim is to determine the optimal level of radiation to use for treating tumor and model predicts a probability distribution over radiation dose, then we need to use that distribution to determine the specific dose to be administered. We explain this formally using the notion of decision theory.

Formal Objective. Suppose we choose $f(x)$ for our prediction when the true value is $t$. Then, this choice incur a penalty/cost given by a loss function $L(t, f(x))$. We define the objective

Example of $L(t, f(x))$ is squared loss.

Choosing decision function f(x). Minimizing above expected loss using squared loss, using calculus of variations, we obtain.

$f^*(x) = \mathbb E_t[t\mid x]$ is called the regression function.

Which is just conditional expectation of $t$ given $x$. For Gaussian conditional distribution, this becomes the following.

Bias Variance Tradeoff

Derivation of Bias Variance Tradeoff.

Note that term $\mathbb E[t\mid x]$ is just one choice of the regression function. Second term is independent of $f(x)$ arises from intrinsic noise of the data – represents minimum value achievable for expected loss.

Consider the first integrand, done over a particular dataset $D$: $(f(x; D) - h(x))2$. We do experiments over the ensemble of datasets, so we can take the average of the above over many possible datasets. Consider we model $\mathbb E[t\mid x]=h(x)$.

There will be 3 terms with the last term will vanish. The first term is the squared bias of the model. Second term is variance of the

We will ended up with expected $loss =\text{ bias }^2 +\text{ variance }+\text{ irreducible noise}$.

Classification

Task. Predicting a class label $y\in\{1,\dots, K\}$ from input $x\in R^D$.

Three approaches to solve classification task.

1. Discriminant function: directly assigns $x$ to a specific class.
2. Discriminative probabilistic model: train the conditional distribution $p(C_k | x)$ directly using a training set, and then use the model to decide the class of $x$.
3. Generative probabilistic model: model the class-conditional density $p(x | C_k)$, and the class prior $p(C_k)$, then compute the posterior $p(C_k | x)$ via Bayes theorem; after that, use the posterior distribution to decide the class of $x$.

Maximum Likelihood on Classification Task. Likelihood is defined the same regardless of regression or classification. All that matters is our estimator definition. Suppose we model classification task as below.

where $f_c(x; w)$ is a parametric function. Likelihood is in the form of.

Linear discriminant function: Two-class case. Suppose we model

The decision to assign $x$ into class $\hat y$ is

Decision boundary corresponds to the $y(x)=0$, $D-1$ dimensional hyperplane within $D$ dimensional input space.

Decision boundary is orthogonal to w. Under the same model above, we could prove that for any vector $(x_0-x_1)$ such that $y(x_0) = y(x_1) = 0$ (they are on the same side of the decision boundary), they are orthogonal with $w$.

where $\langle \cdot, \cdot \rangle$ is the standard dot product. This property holds true for any two points $x_0, x_1$ on the decision boundary. This implies that the distance between any $x$ and the decision boundary is $r\frac{w}{\Vert w\Vert}, r\in R$.

Multiple classes. The trick above (Defining decision boundary $y_c(x)>0$) will draw a single line for single class $c$.

• One-versus-the-rest. When there are $C$ classes, we draw $C$ decision boundaries, but this will lead into ambiguous regions where both classes are predicted (problem in mutually exclusive classes).
• One-versus-one. When there are $C$ classes, we draw $C(C-1)$ decision boundaries, but this will lead into ambiguous regions where both classes are predicted (problem in mutually exclusive classes).
• Solution, use $K$ linear functions $f_1(x),\dots,f_K(x)$, then $\hat y = \arg\max_{k=1,\dots, K} f_k(x)$, i.e assign $x$ to the class $i$ with highest $f_i(x)$. Decision regions will be singly connected and convex.

Using Least Square to find $W$. For one hot vector $t_i\in R^K$ with prediction $w^T\phi(x_i)\in R^K$, we stack into the matrix form $T=[t_i]_i\in R^{N\times K}, X=[\phi(x_i)]_i\in R^{N\times D}, W=[w^T_i]_i \in R^{D\times K}$ (essentially just stacking vertically).

Decision Theory

Prediction and Action. Prediction in supervised learning is modeled probabilistically as a posterior distribution $p(y\mid x)$. Intuitively, our follow up action for prediction is to choose the value of $y$ that makes $p(y\mid x)$ the highest. But is this mathematically justified?

Mathematical Justification. We assume an agent / decision maker has set of possible action $a\in\mathcal A$. Each action $a$ has costs and benefits that depend on the state (hidden) of nature $y$. These dependencies can be modeled as a loss function $\ell(y, a)$ that gives the loss incurred if the agent takes action $a$ when the state of nature is $y$.

Posterior Expected Risk. We define the posterior expected risk as

Optimal Policy (Bayes Estimator). The optimal policy is the one that minimizes the posterior expected risk.

Alternative: Use utility function, Maximum Expected Utility Principle. Define $U(y, a)$ expressing desirability of each possible action and state then seek action that maximize expected utility.

Decision on Classification, Zero-one loss for Binary Classification. Assign loss 1 if action is wrong, 0 otherwise.

Posterior expected loss for each action $a$ is

Optimal policy is

Maximum a posteriori (MAP) estimate. This maximization decision rule is corresponds to the mode of the posterior distribution. Specifically for binary case:

Cost Sensitive Classification. Instead of zero-one loss, we may have the following cost matrix where $\ell_{ij}$ is the cost of predicting $j$ when true label is $i$.

Decision rule is to pick $a$ that minimizes the posterior expected loss:

Which turn into this decision rule

Reject Option Classification. Sometimes we want to say “I don’t know” instead of returning an answer (called the reject option). The loss will then become

The optimal decision rule that minimizes posterior risk is (prove as exervise)

Evaluation Matrix

Confusion Matrix. We can define the number of true positives (TP), false positive (FP), true negatives (TN), and false negatives (FN) with respect to the threshold $\tau$:

Thus we can define the following confusion matrix:

Metric from Confusion Matrix.

Metrics w.r.t. rowwise normalization (i.e., truths).

• True negative rate (TNR) or specificity

• False positive rate, false alarm rate, type I error rate, or fallout

• False negative rate, miss rate, or type II error rate

• True positive rate, sensitivity, recall, or hit rate

Metrics w.r.t. columnwise normalization (i.e., predictions).

• Negative predictive value

• False omission rate

• False discovery rate

• Precision or positive predictive value

Choosing from a number of different thresholds. With ROC curves, we can consider a set of different thresholds and compare the resulting performance. For each threshold $\tau$, we plot $FPR_\tau$ versus $TPR_\tau$ as a point and draw a curve connecting them. This gives the receiver operating characteristic (ROC) curve.

ROC curve is insensitive to changes in class distribution. Changes in the proportion of positive to negative instances in the (test) set do not cause change to the curve.

Precision-Recall (PR) curve.

F-scores. $F_\beta$ score is a combined statistics between precision (Prec) and recall (Rec).Useful for looking at a single threshold. F-score is affected by class distribution changes.

Classification Modeling

Three approaches for training and inference.

1. Generative Models. Train class conditional densities $p(x\mid C_k)$ for each class $C_k$ individually. Then use Bayes theorem to compute the posterior probabilities:

“Generative” because by sampling from them, it is possible to generate synthetic data points in the input space.

2. Deterministic Models. Train posterior class probabilities $p(C_k\mid x)$. Then, use decision theory to perform inference to assign each new $x$ to one of the classes.

3. Discriminative Models. Find a discriminant function $f(x)$ that maps each input $x$ directly onto a class label, e.g., for binary classification $f$ might be binary valued such that $f = 0$ represents class $C_1$ and $f = 1$ represents class $C_2$.

Why compute posterior instead of discriminant function directly?.

• Modular, For problems where loss matrix is revised from time to time, knowing posterior probabilities implies that we only need to modify minimum risk criterion without having to re-train the model.
• Reject option. Posterior probabilities allow us to determine a rejection criterion that minimizes the expected loss for a given fraction of rejected data points
• Can compensate different class priors. Model trained using one class prior can be adapted to new class prior
• Combining models. Different posterior probabilities can be combined.

Discriminative Classifiers, Logistic Regression. Intuitively, we classify

We assume the data is linearly separable using above equation. In another form, we could formulate $f(x)$ as a log-odds.

The aforementioned model is called (binary) logistic regression

MLE for Logistic Regression.