DD1420

exchange

Course Information §

Name：Foundations of Machine Learning

Lecture Notes

---

Lesson 2 §

---

Linear Regression with RANSAC

---

Root mean squared error

---

Algebraic Linear Regression

Uses matrix algebra to solve for $w$ and $b$ directly, minimizing the least squares error:

$$L=\frac{1}{n}\sum (y_i-{\hat{y}}_i{)}^2$$

---

Logistic Regression

The sigmoid function maps $z=w^{T}x+b$ to a probability between 0 and 1 for classification:

$$\sigma (z)=\frac{1}{1+e^{-z}}$$

---

Support Vector Machine

Finds a hyperplane maximizing the margin between classes, controlled by the hyperparameter $C$ (trade-off between margin size and classification error).

• Large C: Narrow margin, fewer misclassifications.

• Small 𝐶: Wider margin, more slack (misclassifications allowed).

---

K-Medoids Clustering

Clusters data by selecting actual data points as medoids, iteratively assigning points to the nearest medoid and updating medoids to minimize total distance.

---

Lesson 5 §

---

Dimensionality reduction

將數據的維度降低，複雜度降低，我們能更容易的分析數據，當資料的維度降低到只剩下幾個抽象特徵時，可以加快模型的訓練速度和大小，且當維度降低至2或3維時，也能更直觀的視覺化數據。

---

Principal Component Analysis, PCA

主成份分析，一種經典的線性降維方法，目標是尋找一個最佳的線性正交投影 $\pi$，將一組 $d$ 維的數據降到 $k$ 維，$d>k$，使得投影後的數據在低維子空間中能夠保有最大的變異性。

這個子空間有 $k$ 維，由 $k$ 個正交的特徵向量 $u_1,\dots ,u_k\in {\mathbb{R}}^n$ 張成，這些向量稱為主成分，滿足以下條件：

1. 正交：$u_i^T{u}_j=0,i\ne j$，確保這些向量不會有重複的資訊，每個向量表示不同的方向。

2. 單位長度：$u_i^t{u}_i=\Vert u_i{\Vert }^2=1$，確保數據在投影後不會因為基底向量的長度變化而被放大或縮小。

變異性代表數據的分散程度，如果數據在某方向上的變異性較大，代表這個方向上的變化較多，不同的數據點有顯著區別，表示資訊較多、較豐富。

PCA有三個步驟：

1. 計算數據的協方差矩陣 covariance matrix

2. 計算協方差矩陣中的特徵值和特徵向量，最大的特徵值對應的特徵向量就是第一主成分，第二大的特徵值對應的特徵向量就是第二主成分。

3. 將數據投影到這些主成分上，得到降維後的數據。

---

Multidimensional Scaling, MDS

---

Lesson 6 §

Kernel Methods

Kernel methods are the methods to make linear models (like linear regression and SVMs) handle non-linear data.

The idea is to mapping data into a higher-dimensional space where a linear model can be applied. However, the mapping is not actually performed, instead, they use kernel functions to compute the inner product directly in the higher-dimensional space.

---

Linear Regression

The linear regression model tries to fit a linear function (a straight line) to the data, which minimizes the sum of squared errors between the predicted value and the true value.

The equation of the line is $y={\theta }_0+{\theta }_{1}x$, and for each data point $(x_i,y_i)$, the model predicts ${\hat{y}}_i={\theta }_0+{\theta }_1{x}_i$.

The error for each data point is $e_i=y_i-{\hat{y}}_i$, and the sum of squared errors is

$$\begin{array}{rl}E& ={\Sigma }_{i=1}^n(y_i-{\hat{y}}_i{)}^2\\ & ={\Sigma }_{i=1}^n(y_i-{\theta }_0-{\theta }_1{x}_i{)}^2\\ & ={\Sigma }_{i=1}^n(y_i-{\theta }^t{x}_i{)}^2\end{array}$$

The reason to use the squared error is that it avoid the cancellation of positive and negative errors and also penalize large errors more compare to the small errors.

---

Ridge Regression

When trying to minimize the loss, we might meet the degenerate case: the solution is not unique because of too less data points, or too many features.

Ridge Regression can solve this by adding a regularization term to the loss function, which is the sum of squared weights, encouraging the weights to be small at the same time minimize the loss to prevent overfitting.

$$E={\Sigma }_{i=1}^n(y_i-{\theta }^t{x}_i{)}^2+\lambda ||\theta |{|}^2$$

Also because of this term, we can always get a unique solution even if the data is not enough.

---

Primal Solution

Primal and dual solutions are two different ways to solve the same problem. The primal solution focuses on finding the weights $\theta$ directly.

$$E={\Sigma }_{i=1}^n(y_i-{\theta }^t{x}_i{)}^2+\lambda ||\theta |{|}^2$$

Derive the loss function with respect to $\theta$ and set it to zero, we can get the optimal weights

$$\theta =(X^{t}X+\lambda I_k{)}^{-1}{X}^{t}y$$

• $X$ is the data matrix, $n\times k$

• $n$ is the number of samples, $k$ is the number of features.

• $X^{t}X$ is a $k\times k$ matrix.

• The inverse matrix $(X^{t}X+\lambda I_k{)}^{-1}$ is a $k\times k$ matrix with computational time complexity $O(k^3)$.

• The solution $\theta$ is a $k\times 1$ vector, which is in the feature space.

---

Dual Solution

If the dimensional of the data is very large (a lot of features), it will be very slow to calculate the inverse of the matrix in the primal solution. We use the dual solution to solve this problem.

The dual solution focuses on finding the Lagrange multipliers $\alpha$, which is the weight of each data point.

$$\theta =X^t\alpha$$

Bring this into the original ridge regression loss function, we can get the best $\alpha$.

$$\begin{gathered} \alpha =(K+\lambda I_n{)}^{-1}y \\ ⟹\theta =X^t(K+\lambda I_n{)}^{-1}y \end{gathered}$$

• $K=X{X}^t$, the Gram matrix, is a $n\times n$ matrix.

• The inverse matrix is a $n\times n$ matrix with computational time complexity $O(n^3)$.

• The solution $\alpha$ is a $n\times 1$ vector, which is in the sample space.

| Formulation | Primal Solution | Dual Solution |

| --- | --- | --- |

| Solution | $\theta =(X^{t}X+\lambda I_k{)}^{-1}{X}^{t}y$ | $\theta =X^t(K+\lambda I_n{)}^{-1}y$ |

| Space | Feature space | Sample space |

| Computational Complexity | $O(k^3)$ | $O(n^3)$ |

| Kernel Methods | Not practical in high-dimensional data | Yes |

---

Polynomial Regression

In previous linear regression, we assume the relationship between the input and output is linear. However, in some cases, the relationship is not linear, but polynomial.

It first maps the input $x$ to a higher-dimensional space, using $x\to \varphi (x)$, then apply the linear regression in this space.

If we apply this to the primal and dual solution, they become:

$$\begin{gathered} Primal:\theta =({\Phi }^t\Phi +\lambda I_k{)}^{-1}{\Phi }^{t}y \\ Dual:\theta ={\Phi }^t(\Phi {\Phi }^t+\lambda I_n{)}^{-1}y \end{gathered}$$

---

Kernel Functions

Kernel function: $k(x,y)=<\varphi (x),\varphi (y)>$

It is defined as the inner product of the mapped data in the transformed space.

Kernel Trick

It will be very expensive to calculate the $\Phi$ when the data is very high-dimensional. Instead of calculating the $\Phi$ directly, we can calculate the kernel function $k(x,y)$ to get the inner product of the mapped data in the transformed space without actually mapping the data.

Polynomial Kernel

$$k(x,y)=(x^{t}y+c{)}^d$$

Gaussian Kernel

$$k(x,y)=\exp (-\frac{||x-y|{|}^2}{2{\sigma }^2})$$

which maps the data to an infinite-dimensional space.

Periodic Kernel

Lesson 7, Probability §

Probabilistic Model

It is a probability distribution defined by the model family and parameters, it assigns probabilities to different outcomes.

• Model family: Specifies the functional form of the distribution.

• Parameters: Controls the distribution’s specific characteristics.

---

Likelihood

It’s a function (not distribution) of $\theta$ for fixed data $X$, describes how probable is the data $X$ under the specific $\theta$, according to the model.

$$L(\theta )=p_X(X;\theta )$$

It’s not a PDF for $\theta$ and it doesn’t integrate to 1 with respect to $\theta$. Because it’s not a probability distribution over $\theta$.

---

Log-Likelihood

$$L(\theta )=\log L(\theta )=\sum _{i=1}^n\log p_{\mathbf{x}}(x_i;\theta )$$

It is used for numerical stability and computational efficiency, because the product is replaced with a sum in log space.

---

Maximum Likelihood Principle

The best parameters $\theta$ for a model are those that maximize the likelihood of observing the given data $X$.

---

Maximum Likelihood Estimation

The process of applying the maximum likelihood principle to find the specific parameter values that maximize the likelihood for a given dataset and model.

To find the maximum-likelihood parameter estimate ${\hat{\theta }}_{\text{ML}}$, solve directly for the maximum of the likelihood function by setting its derivative to zero:

$$\begin{array}{rl}& \mathcal{L}(\theta )=\log L(\theta )=\sum _{i=1}^n\left[x_i\log \theta +(1-x_i)\log (1-\theta )\right]\\ ⟹& \frac{d}{d\theta }\mathcal{L}(\theta )=\frac{d}{d\theta }\left[\sum _{i=1}^n{x}_i\log \theta +(1-x_i)\log (1-\theta )\right]=\sum _{i=1}^n\left[\frac{x_i}{\theta }-\frac{1-x_i}{1-\theta }\right]=0\end{array}$$

Solving this yields:

$${\hat{\theta }}_{\text{ML}}=\frac{{\sum }_{i=1}^n{x}_i}{n}$$

Limitation: It is optimal with infinite data but may overfit with small samples and can be constrained by shrinking the parameter space or using prior knowledge.

---

Bayes’ Law

$$p_{\theta \mid \mathcal{X}}(\theta \mid \mathcal{X})=\frac{p_{\mathcal{X}\mid \theta }(\mathcal{X}|\theta )\cdot p_{\theta }(\theta )}{p_{\mathcal{X}}(\mathcal{X})}$$

• Prior: $p_{\theta }(\theta )$, the initial belief about the parameter $\theta$ before seeing the data.

• Likelihood: $p_{\mathcal{X}\mid \theta }(\mathcal{X}\mid \theta )$, the probability of observing the data $\mathcal{X}$ given a specific value of $\theta$.

• Evidence: $p_{\mathcal{X}}(\mathcal{X})$, This is the total probability of the data $\mathcal{X}$ across all possible $\theta$ values.

• Posterior: $p_{\theta \mid \mathcal{X}}(\theta \mid \mathcal{X})$, the updated probability distribution of $\theta$ after observing the data $\mathcal{X}$. It combines our prior belief with the evidence from the data.

General form of Bayes' Law

$$P(A\mid B)=\frac{P(B\mid A)\cdot P(A)}{P(B)}$$

• $P(A\mid B)$: The probability of event A given that event B has occurred (called the posterior).

• $P(B\mid A)$: The probability of B given A (called the likelihood).

• $P(A)$: The probability of A before considering B (called the prior).

• $P(B)$: The probability of B, acting as a normalizing constant (called the evidence).

Example of Bayes' Law

• A: You have the disease.

• B: You test positive for the disease.

• $P(A\mid B)$: The probability that you actually have the disease given that you tested positive. This is the posterior.

• $P(B\mid A)$: The probability of testing positive given that you have the disease. This is the likelihood.

• $P(A)$: The probability that you have the disease before knowing anything about the test result. This is the prior.

• $P(B)$: The probability of testing positive, which acts as the normalizing constant.

---

Maximum A Posteriori Principle

We should pick the $\theta$ that maximizes the posterior $p_{\theta \mid \mathcal{X}}(\theta \mid \mathcal{X})$ for $\theta$ to best balances what the data tells us (via the likelihood) with what we already believe (via the prior).

---

Maximum A Posteriori Estimation

MAP estimation is the practical process of applying the MAP principle to compute the specific parameter estimate ${\hat{\theta }}_{\text{MAP}}$ that maximizes the posterior for a given dataset $\mathcal{X}$ and prior.

$$\begin{array}{rl}{\hat{\theta }}_{\text{MAP}}& =\arg \underset{\theta }{\max }{p}_{\theta |\mathcal{X}}(\theta |\mathcal{X})\\ & =\arg \underset{\theta }{\max }\left[p_{\mathcal{X}|\theta }(\mathcal{X}|\theta )\cdot p_{\theta }(\theta )\right]\\ & =\arg \underset{\theta }{\max }\left[L(\theta |\mathcal{X})+\log p_{\theta }(\theta )\right]\end{array}$$

Then take the derivative and set it to be zero.

---

MLE v.s. MAP

MLE maximizes only the likelihood $p(X\mid \theta )$, ignoring prior knowledge. MAP adds the prior $p(\theta )$, constraining the estimate to avoid overfitting (e.g., a coin with 3 heads doesn’t force $P(\text{tails})=0$).

The estimated parameters of MAP are somewhere between where the prior thought they would be, and the parameter estimates we would have gotten.

---

Mixture Models

They combine multiple simple distributions into a more flexible, multi-modal distribution. The density is a weighted sum:

$$p(x)=\sum _{j=1}^m{\pi }_j{p}^{(j)}(x)$$

where ${\pi }_j$ are weights satisfying:

$$\sum {\pi }_j=1,{\pi }_j\ge 0$$

Each data point is assumed to come from one of the component distributions, but the identity of the component is unobserved (latent variable).

---

Latent Variables

The component assignment of each data point is a latent variable, meaning it is not directly observed.

---

Gaussian Mixture Models (GMMs):

A specific case of mixture models where components are Gaussian distributions. Each component has its own mean vector and covariance matrix.

Maximum likelihood estimation (MLE) for GMMs lacks a closed-form solution. The log-likelihood involves a sum inside a logarithm, making direct optimization difficult.

---

Expectation-Maximisation Algorithm

In GMMs, There’s observed data $D=\{x_i\}$, unknown parameters $\theta$, and hidden latent variables $\{z_i\}$. Neither can be solved directly without knowing the other.

EM uses alternating optimization:

• If $\theta$ were known, $z_i$ could be inferred using Bayes’ law.

• If $z_i$ were known, $\theta$ could be estimated via standard MLE.

EM iterates between guessing one and refining the other until convergence.

---

Jensen’s Inequality

$$f\left(\sum _{i=1}^n{w}_i{x}_i\right)\le \sum _{i=1}^n{w}_{i}f(x_i)$$

For a concave function like $\log$,

$$\log \left(\sum w_i{x}_i\right)\ge \sum w_i\log (x_i)(\text{with}\sum w_i=1)$$

This helps transform the tricky log-likelihood:

$$\log p(x_i;\theta )=\log \sum _{j}p(x_i,z_i=j;\theta )$$

into a manageable lower bound.

---

Evidence Lower Bound (ELBO)

By introducing an arbitrary distribution $Q(z_i)$, the log-likelihood is bounded as:

$$\log p(x_i;\theta )\ge \sum _{j}Q(z_i=j)\log \frac{p(x_i,z_i=j;\theta )}{Q(z_i=j)}$$

This ELBO is easier to optimize than the original likelihood.

---

EM Algorithm Steps

1. Initialization: Start with a guess for $\theta$ or responsibilities ${\gamma }_{ij}$ (probability that $x_i$ belongs to component $j$).

2. E-Step (Expectation): Using the current value of $\theta$ to compute the ELBO by setting $Q(z_i)=p(z_i\mid x_i;\theta )$. This result in responsibilities ${\gamma }_{ij}=P(z_i=j\mid x_i;\theta )$.

3. M-Step (Maximization): Update $\theta$ by maximiz the ELBO, improving the likelihood.

$${\hat{\theta }}_{\text{n}ew}=\arg \underset{\tilde{\theta }}{\max }{\text{ELBO}}_{\gamma (\hat{\theta })}(\tilde{\theta },\mathcal{X})$$

4. Repeat: Alternate E and M steps until a stopping criterion (e.g., small likelihood increase) is met.

• EM finds local maxima.

• The ELBO equals the likelihood when $Q(z_i)=p(z_i\mid x_i;\theta )$ ensuring each iteration improves or maintains the likelihood.

---

Nonparametric Density Estimation

---

Empirical Density Estimation

---

Naive Density Estimation

---

Kernel Density Estimation (KDE)

• Places a kernel (small PDF) around each data point and aggregates them.

• Formula: sum of kernel functions centered at each observation, divided by sample size.

$$p(x)=\frac{1}{nh}\sum _{i=1}^{n}K\left(\frac{x-x_i}{h}\right)$$

where $K$ is a kernel (e.g., Gaussian) and $h$ is the bandwidth.

• Bandwidth (h), similar to window width in histograms, controls the width of each kernel.

• Small h

• Narrow kernels, tightly hugging each data point.

• A spiky, jagged density with lots of detail.

• Large h:

• Wide kernels, spreading probability far from each point

• A smooth, overly flattened density that might miss details.

---

Histograms

Divides data domain into bins of equal width

Counts data points in each bin and normalizes to create a PDF

• Bin width (w), which controls detail level

• Trade-off: too few bins (high bias) vs. too many bins (high variance)

---

Lesson 8 §

---

Information Content

Also known as Shannon information, measures how surprising an event is (the uncertainty).

$$I(x)=lo{g}_2\frac{1}{P(x)}=-lo{g}_{2}P(x)$$

Why $lo{g}_2$?

• Monotonic

• $P(x)=1⟹I(x)=0$

when the event will definitely happen, the information content is 0, meaning that it is not surprising at all.

• $I(x,y)=I(x)+I(y)$

---

Entropy

The expected information content of a random variable $X$, it describes the expected uncertainty in a probability mass function.

$$H(X)={\mathbb{E}}_{x\sim P_X}[I(x)]=-\sum _{x\in \Omega }{P}_X(x)lo{g}_2{P}_X(x)$$

The unit of entropy is bit or dits if using $lo{g}_{10}$ or nats if using $lo{g}_e$.

---

Perplexity

Perplexity is another way to express the entropy (the uncertainty).

The amount of surprise of the model when predicting a sample.

$$PP(X)=2^{H(x)}$$

---

Cross Entropy

The expected information content of a probability mass function $Q_X$ with respect to another probability mass function $P_X$.

$$\begin{array}{rl}H(P_X,Q_X)& ={\mathbb{E}}_{x\sim P_X}[I(x,Q_X)]\\ & =-\sum _{x\in \Omega }{P}_X(x)\log Q_X(x)\end{array}$$

---

Kullback-Leibler Divergence

The KLD is a measure of how much one probability distribution differs from another.

It compares the true distribution (the data $P_X$) with the approximate distribution (the model $Q_X$) by calculating the difference between the cross entropy and the entropy.

$$\begin{array}{rl}{D}_{\text{KL}}(P_x\Vert Q_x)& =H(P_X,Q_X)-H(P_X)\\ & ={\mathbb{E}}_{x\sim {\mathcal{P}}_x}\left[\log \frac{P_x(x)}{Q_x(x)}\right]\\ & =\sum _{x\in \Omega }{P}_x(x)\log \frac{P_x(x)}{Q_x(x)}\end{array}$$

• $D_{\text{KL}}(P_x\Vert Q_x)\ge 0\forall P_x,Q_x$

• $D_{\text{KL}}(P_x\Vert Q_x)=0⟺P_x=Q_x$

Why it is not a distance?

• Not symmetric:

$D_{\text{KL}}(P_x\Vert Q_x)\ne D_{\text{KL}}(Q_x\Vert P_x)$

• Not triangle inequality:

$D_{\text{KL}}(P_x\Vert Q_x)+D_{\text{KL}}(Q_x\Vert R_x)\ngeqq D_{\text{KL}}(P_x\Vert R_x)$

Forward KL: $D_{\text{KL}}(P\parallel Q)$

• Approximates $P$ with $Q$

• Penalizes: $Q$ heavily if it assigns low probability to regions where $P$ has high probability ($\log \frac{P(x)}{Q(x)}$ becomes very large).

• Behavior: Mass-covering, $Q$ can’t be too small in any region where $P$ supports, $Q$ spreads probability mass to cover all regions where $P$ exists.

Reverse KL: $D_{\text{KL}}(Q\parallel P)$

• Approximates $Q$ with $P$

• Penalizes: $Q$ if it assigns high probability to regions where $P$ has low probability ($\log \frac{Q(x)}{P(x)}$ becomes very large).

• Behavior: Mode-seeking, $Q$ focuses on matching a single mode (peak) of $P$, it needs to be small in regions where $P$ is small.

---

Decision Tree

---

What is the difference between information gain and Gini impurity as splitting criteria?

• Information gain measures the reduction in Shannon entropy (uncertainty) after a split, favoring splits that maximize the difference in entropy before and after.

• Gini impurity measures the probability of misclassifying a randomly labeled point in a subset, favoring splits that minimize this impurity.

• Gini is computationally simpler (no logarithms) and less sensitive to rare events, while information gain aligns with information theory principles.

• Gini impurity might be preferred because it’s computationally faster (uses squared probabilities instead of logarithms) and less sensitive to small probability changes, making it more robust in noisy datasets.

---

How does setting a max_depth limit help prevent overfitting in decision trees?

Setting a max_depth limit stops the tree from growing too deep, preventing it from creating overly specific splits that capture noise in the training data. This reduces variance (overfitting) by enforcing simpler models

---

Excerise 9 §

---

Summary

• Simple Gaussian Model: A basic generative model assumes each pixel is independently Gaussian-distributed. Maximum likelihood estimation (MLE) computes pixel-wise means and standard deviations, but samples are noisy due to ignored pixel correlations.

• PCA-Based Gaussian Model: To address correlations, Principal Component Analysis (PCA) with 250 components transforms the data into uncorrelated coefficients. A Gaussian model is fitted to these coefficients, and inverse PCA reconstructs images, reducing noise by capturing pixel covariances implicitly.

• Temperature Adjustment: Reducing the “temperature” (scaling standard deviation) lowers entropy, concentrating samples around likely outcomes, improving perceived quality.

• As T increasing from 0 to 0.25, the feature of the faces become more obvious and recognizable. However when T increases to 1, the shape become distorted, likely due to excessive variation in pixel values.

• Gaussian Mixture Model (GMM): A non-Gaussian approach uses GMMs (25 and 250 components) on PCA coefficients, capturing multimodal distributions and further enhancing sample quality by modeling data clusters.

• It can better capture the structure of the data by assigning different Gaussian components to different regions of the distribution, allowing the generated samples to retain more detailed features and become more sharper.

---