Created by Yunhao Cao (Github@ToiletCommander) in Spring 2022 for UC Berkeley CS189.

Reference Notice: Material highly and mostly derived from Prof Shewchuk's lecture notes, some ideas were borrowed from wikipedia & Stanford CS231N & Andrew Ng’s Intro to ML Course@Stanford.

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License

Last Update: 2022-05-13 21:46 PST ⇒ After final release

Machine Learning Abstraction

Classifiers

Suppose we have Bayes Optimal Classifier $r(x)$, that is $r(x)$ will output the prediction y that minimizes Bayesian Risk $R(r(x))$.

3 ways to build classifiers

1. Generative Models(e.g. LDA)
   1. Assume sample points come from probability distributions, different for each class.
   2. Guess form of distributions
   3. For each class C, fit distribution parameters to class C points, giving $f(X|Y=C)$
   4. For each class C, estimate $P(Y=C)$
   5. Baye’s Theorem gives $P(Y|X)$
   6. If 0-1 loss, pick class C that maximizes
      1. $P(Y=C|X=x)=f(X=x|Y=C)P(Y=C)$

2. Discriminative Models (e.g. logistic regression)
   1. Model $P(Y|X)$ directly.

3. Decision Boundary
   1. Model $r(x)$ directly

ROC Curve (Receiver Operating Characteristics)

X axis - False Positive Rate (FP) - Predictor predicts + but actually is -

Y axis - Sensitivity / True Positive Rate (TP) - Predictor predicts + and right

1 - x ⇒ Specificity / True Negative Rate (TN) - Predictor predicts - and right

1 - y ⇒ False Negative Rate (FN) - Predictor predicts - but actually is +

We want to minimize x and (1-y)

Data Cleaning

Centering

Decorrelating

Let $R$ be uniform distribution on sample points,

We want to perform a linear transformation that maps sample points to axis-aligned distribution

We will apply rotation $Z = \dot{X}V$, where $Var(R)=V\Lambda V^{\top}$.

Then $Var(Z) = \frac1n Z^{\top}Z = \frac1n V^{\top}\dot{X}^{\top}\dot{X}V=V^{\top}Var(R)V=V^{\top}V\Lambda V^{\top}V = \Lambda$

Sphering

Apply transform $W = \dot{X}Var(R)^{-1/2}$

Recall that $\Sigma^{-1/2}$ maps ellipsoids to spheres.

Whitening

Centering + Sphering

$X \rightarrow W$

Ideas

Feature Lifting (Kernel)

Suppose we have data point $X_i$, the lifted data point is $\Phi(X_i)$.

Parabolic Lifting Map

p-degree polynomial

Polynomial Kernel:

where $\Phi(x)$ contains every monomial in $x$ of degree $0, \dots, p$

Demonstration of d=2, p=2

Saves tons of computing power since we only need to compute the inner product of the original data point instead of adding the polynomial features.

Gaussian Kernel (RBF - Radial Basis Function Kernel)

An infinite vector, and $\Phi(x) \cdot \Phi(z)$ is a series that converges to $k(x,z)$

RBF Kernel Function:

Choose $\sigma$ by cross-validation. Larger $\sigma$ meas wider Gaussians and smoother h, but more bias and less variance

Transformation of Space in finding weights

In lots of ML algorithms we want to find a decision function that usually took form of a geometric shape like hyperplane / isocontour / isosurface in the original data space (x-space). However, in doing the optimization we usually want to find a vector(point) of weight $\vec{w}$ in the w-spaace that represents the geometric shape in the x-space. Therefore we have implicitly performed a transformation of space from x-space to w-space

Transformation to w-space in perceptron algorithm

For the perceptron algorithm, the transformation is performed below:

Since we want to force inequality $x \cdot w \ge 0$ (for $y_i = 1$, then

1. in x-space, $x$ points for $y_i = 1$ should be on the same side of $\{z : w \cdot z = 0\}$ as $w$

2. in w-space, $w$ should be on the same side of $\{ z : w \cdot z = 0\}$ as $x$ that have $y_i=1$

(Batch) Gradient Descent (GD / BGD)

With a risk function $R(w)$, calculate:

Then for each propagating step, run the following:

Where $\epsilon$ is the learning rate.

Stochastic Gradient Descent (SGD)

With a cost function $L(w,X_i)$, calculate:

Then for each propagating step, run the following:

Where $\epsilon$ is the learning rate.

Quadratic Form

A way to visualize symmetric matrices. Shows how applying the matrix affects the length of a vector.

If a symmetric matrix is diagonal:

1. eigenvectors are coordinate axes

2. ellipsoids are axis-aligned

A symmetric matrix $M$ is:

1. Positive Definite (PD)
   1. if $\forall w \ne 0, w^{\top}Mw > 0$
   2. or all eigenvalues positive

2. Positive Semi-Definite (PSD)
   1. if $\forall w, w^{\top}Mw \ge 0$
   2. or all eigenvalues non-negative

3. Indefinite
   1. if both positive eigenvalue and negative eigenvalue exists

4. Invertible(non-singular)
   1. if has no eigenvalue of 0

By eigendecomposition, we see that any real symmetric matrix has:

Where $\Lambda$ is a diagonal matrix containing the eigenvalues of $A$ and $V$ is a orthonormal matrix which each column is the eigenvector of $A$.

Note that $||A^{-1}x|| = 1 \text{ or } x^{\top}A^{-2}x = 1$ will have ellipsoid with axes and radii specified by the eigenvector and eigenvalues.

Neton’s Method

Iterative optimization method for smooth function $J(w)$

Taylor’s series of cost function around point v:

Where $\nabla^2 J(w) \bigg\rvert_{w=v}$ is the Hessian of $J$ evaluated at point $v$

We will have further exapsnsions like $\nabla^3 J(w)\bigg\rvert_{w=v}$but those are simplified to $O(||w-v||^2)$ since we are only approximating with quadratic function.

By setting $\nabla J(w) = 0$, we find

Note that we don’t want to compute a matrix inverse directly. It is faster to solve a linear system of equations, by Cholesky factorization or the conjugate gradient method.

We set $e=-(\nabla^2 J(v))^{-1}\nabla J(v)$, then we just need to solve

Therefore, in conclusion, the whole process of Newton’s method:

1. Pick starting point $w$

2. Repeat until Converge
   1. $e \leftarrow \text{ solution to linear system } (\nabla^2 J(w))e = -\nabla J(w)$
   2. $w \leftarrow w + e$

Bias-Variance Decomposition

For each model, we have

Note that $D’$ has mean $0$.

We want fit hypothesis $h$ to $X, y$, where $h$ is a random variable (weights)

If we take any arbitraty point(not necessarily a sample point, just any point from the real ground-truth distribution) $z \in \mathbb{R}^d$ and $\gamma = g(z)+\epsilon, \epsilon \in D’$

Then the risk function when loss = sqaured error:

The first term is $bias^2$, second term is $var$ and third term is $\text{irreducible error}$ of the method.

$\gamma$ and $h(z)$ are independent since $h(z)$ only depends on training data and $\gamma$ only on label of z.

1. For many distributions, $variance \rightarrow 0 \text{ as } n \rightarrow \infin$

2. If $h$ can fit $g$ exactly, then $bias \rightarrow 0 \text{ as } n \rightarrow \infin$

3. Adding a good feature reduces bias; adding a bad feature rarely increases it.

4. Adding a feature usually increases variance (added dimension).

5. Noise in test set only affects $Var(\epsilon)$

6. Noise in training set only affects $bias \& Var(h)$

7. We can test learning algorithms by choosing $g$ and making synthetic data

Feature Selection

We want to identify poorly predictive features and ignore them so that we can:

1. enjoy better inference speed

2. less variance

Best Subset Selection

Forward Stepwise Selection

1. Start with null model (0 features)

2. repeatedly add best feature until validation errors start increasing
   1. At each outer iteration, inner loop tries every feature and chooses the best by validation

3. Requires training $O(d^2)$ modules instead of $O(2^d)$

4. But
   1. won’t find the best 2-feature model if neither one of those features yields the best 1-feature model.

Backward stepwise selection

1. Start with all d features

2. repeatedly remove feature whose removal gives best reduction in validation error

3. Also trains $O(d^2)$ models

4. Additional heuristic: only try to remove features with small weights
   1. Small relative to the variance of least-square regression
   2. Variance of least sqaure regression is proportional to $\sigma^2 (X^{\top}X)^{-1}$
   3. z-score of weight $w_i$ is $z_i = \frac{w_i}{\sigma\sqrt{v_i}}$ where $v_i$ is the ith diagonal entry of $(X^{\top}X)^{-1}$
   4. Small z-score hint that the “true” $w_i$ could be zero.

Ensemble Learning 集成学习

Idea: take an average answer of a bunch of decision trees

Bagging

Same learning algoirthm on many random subsamples of one training set.

Works well on most learning algorithms, maybe not k-nearest neighbours?

If $n=n'$ then around 63.2% are chosen.

Different Learning Algorithms

Different hypothesis can help reduce variance

Random Forests

Discussed in the “Algorithms” section

Adaboost

Similar to Random Forests, but different and more powerful.

Discussed in the “Algorithms” section

Kernel Trick

Kernel Trick is developed from the fact that in many algorithms,

1. weights can be written as a linear combination of sample points
   1. Therefore we can write $w = \sum_{i=1}^n a_i X_i = X^{\top} a, a \in \mathbb{R}^n$

2. we can use inner products of $\Phi(x)$ only instead of directly computing $\Phi(x)$.
   1. We will define the kernel function $k(x,z) = \Phi(x) \cdot \Phi(z)$
   2. Note that we can use different kernel function can be substituted to use different kernels.
   3. The real magic happens when we can compute $k(x,z)$ really quickly.

Kernel Ridge Regression

Remember in Ridge Regression,

To dualize ridge regression, we need the weights to be a linear combination of the sample points, but that would not happen unless we penalize the bias term $w_{d+1}=\alpha$.

Therefore we want to center $X$ and $y$ so that the “expected” value of bias is zero

Now we have

Suppose $a$ is the solution to the following:

Then we see that

Since the First term(LHS) the above equation matches the RHS of the original ridge regression, and that the term $X^{\top}a$ of the RHS of the above equation matches the $w$ term in the original ridge regression solution

Therefore we want to find $a$, the dual solution that minimizes the dual form of ridge regression (obtained by substituting in $w=X^{\top}a$)

Therefore the entire algorithm:

We will define $K=XX^{\top}$ where $K_{ij}=k(X_i,X_j)$

$K$ is singular if $n > d+1$ (and sometimes even its not) ⇒ we have to choose a positive $\lambda$.

Training:

Optimized:

Testing:

Comparison between dual and primal

Therefore we prefer dual when $d > n$ (when we add a lot of polynomial / rbf ... features)

Kernel Perceptrons

Featurized(Primal) Perceptron Algorithm:

Training

Testing

We will Dualize the problem with $w = \Phi(X)^{\top}a$

Same as before, Let $K$ be $\Phi(X)\Phi(X)^{\top}$, so $K_{i,j} = k(X_i,X_j)$

Training:

Testing:

Same as kernelized ridge regression,

Kernel Logistic Regression

Training:

Our starting point would be zero.

SGD:

GD:

Testing:

High-Dimensional Data

Distribution of random points

Suppose we have a random point $p \sim N(0,I) \in \mathbb{R}^d$

The vast majority of the random points are at approximately the same distance from the mean, laying in a thin shell. (Think about chi-sqaure distribution)

Angles between random points

Therefore as d becomes larger, $\theta$ becomes more and more likely to be very close to 90 deg!

Learning Theory

Range Space(Set System) $A$: a pair $(P,H)$ where

$P$ is the set of all possible test/training points

$H$ is the set of hypotheses(ranges/classifiers), each hypothesis states which subset of P ($h \sube P$) are in class $C$

Examples of classifiers:

1. Power set classifier: $P$ is a set of $k$ numbers, $H$ is the power set of P, containing all $2^k$ subsets of $P$
   1. This classifier cannot generalize at all because if given any subset of $P$ as training data, it can fit a lot of classifiers and we wouldn’t know which classfier would be good generalization of the other data we haven’t seen unless we see the other data.

2. Linear classifier: $P = \mathbb{R}^d$, $H$ is the set of all halfspaces: $\{\forall w, \alpha, \text{list of }\{x: w \cdot x \ge -\alpha\}\}$

A great question to ask about a certain class of hypotheses would be:

Let all training points and test points drawn independently from probability distribution $D$ defined on domain $P$, then

Suppose our hypothesis is $h \in H$,

the risk / generalization error $R(h)$ of $h$, is the probability that $h$ misclassifies a random point $x$ drawn from $D$ ⇒ average test error

the empirical risk / training error $\hat{R}(h)$ is the percentage of training data points misclassified by $h$

Hoeffding’s inequality tells us probability of bad estimate:

“How likely that a number drawn from a binomial distribution will be far from its mean”

So...we want to choose $\hat{h} \in H$ that minimizes $\hat{R}(\hat{h})$, a technique called empirical risk minimization

however, its computationally infeasible to pick the best hypothesis ⇒ SVM find a linear classifier with zero training error when the training data is linearly separable, but when it isn’t SVM try to find a linear classifier with low training error, not minimum.

Dichotomies

A dichotomy of $X$ is $X \cap h$, where $h \in H$

It picks out the training points that h predicts are in class C

Up to $O(2^n)$ dichotomies. The more dichotomies, the more likely it is that one of them will get lucky and have misleading low empirical risk

Given $\Pi$ dichotomies,

Therefore, the smaller we make $\Pi$ and the bigger we make $n$, the more accurate we can predict the risk based on the empirical risk

Suppose we chose $\hat{h}$ as our hypothesis, then with probability $\ge 1 - \delta$,

Where

and $h^*$ being the optimal hypothesis in the class $H$

Therefore, with enough training data and a limit on the number of dichotomies, empirical risk minimization usually chooses a classifier close to the best one in the hypothesis class.

After choosing $\delta$ and $\epsilon$,

the sample complexity is the number of training points needed to achieve this $\epsilon$ with probability $\ge 1-\delta$:

Shatter Function

number of dichotomies: $\Pi_H(X) = |\{X \cap h: h \in H\}| \quad \in [1,2^{n}] \text{ where } n = |X|$

shatter function: $\Pi_H(n) = \max_{|X|=n, X \sube P} \Pi_H(X)$ ⇒ max number of dichotomies of any training set of size n

Its called a shatter function because $H$ shatters aset $X$ of n points if $\Pi_H(X)=2^n$.

e.g. Linear classifiers in plane, $H$ = set of all halfplanes, $\Pi_H(3)=8$

Fact: for all range spaces, either $\Pi_H(n)$ is $O(n^p)$ or $O(2^n)$

Cover’s theorem

linear classifiers in $\mathbb{R}^d$ allow up to $\Pi_H(n)=2\sum_{i=0}^d {n-1 \choose i}$ dichotomies of n points

For $n \le d+1$, $\Pi_H(n)=2^n$

For $n \ge d+1$, $\Pi_H(n) \le 2{e(n-1) \choose d}^d \quad \Longleftarrow \text{polynomial in n with exponent d}$

VC Dimension (Vapnik-Chervonenkis Dimension)

VC dimension is the bound for polynomial shatter function

Theorem:

Therefore,

Also: $O(VC(H))$ training points suffice for accuracy (hidden constant is big though)

Algorithms

Perceptron Algorithm

Label

Goal:

Find weights $w$ such that

Loss Function:

Cost/Risk Function

If w classifies all $X_1, \dots, X_n$ correctly, then $R(w) = 0$.

Optimizer:

1. Gradient Descent, SGD.
   1. Both guarenteed to work if linear seperable
   2. Guarenteed to classfy all data in at most $O(r^2/\gamma^2)$ iteratinos, where $r=\max ||X_i||$ is the radius of the data and $\gamma$ is the maximum margin (defined in Max-Margin Classifier).

Hard-Margin Support Vector Machine (Hard-Margin SVM)

The problem with perceptron algorihtm is that we can fit infinitely many hyperplanes to the data since it does not constrain the weight vector, just asking it to be correct on classifying data (it can fit training data 100% but it may not generalize well to validation or test set). This may lead to increased variane.

We will enforce the constraints:

Note that the RHS is a 1, and it is makes impossible for the weight vector $w$ to get set to zero.

Therefore the optimization problem:

Its a quadratic program in $d+1$ dimensions and $n$ constraints, and has a unique solution (if points are linearly seperable).

The reason that we don’t want to use $||w||$ is because it is not smooth at $w=0$, whereas $||w||^2$ is smooth everywhere, making it easier to optimize.

Soft-Margin SVM

Idea: Allow some points to violate the margin with slack variables $\xi_i \ge 0$.

Now we re-define the margin to be $1/||w||$, since the margin is no longer the distance from the decision boundary to the nearest sample point.

Therefore the optimization prblem:

$C>0$ is a scalar regularization hyperparameter that trades off

Gaussian Discriminant Analysis(GDA)

Isotropic Gaussians

Anisotropic Gaussians(Different variances along different directions)

Where $\Sigma$ is $d \times d$ Semi Positive Definite Covariance Matrix.

Semi Positive Definite: $\forall \vec{w}, \vec{w}^{\top}\Sigma \vec{w} \ge 0$

And $\Sigma^{-1}$ is $d \times d$ SPD precision matrix.

Let $q(x) = (x-\mu)^{\top}\Sigma^{-1}(x-\mu)$, therefore $f(x) = n(q(x))$ where $n(\cdot)$ is a sample, monotonic, convex function that is an exponential of the negative of its argument. $n(\cdot)$ does not affect the isosurfaces.

$q(x)$ is the squared distance from $\Sigma^{-1/2}x$ to $\Sigma^{-1/2}\mu$.

$d(x,\mu)=||\Sigma^{-1/2}x-\Sigma^{-1/2}\mu||=\sqrt{(x-\mu)^{\top}\Sigma^{-1}(x-\mu)}=\sqrt{q(x)}$

Important fact: if you understands isosurface of quadratic form then you can understand isosurface of Gaussian, only difference is that the max isovalue is at the mean of the Gaussian.

Suppose only two classes C, D Bayes decision rule $r^*(x)$ predicts class C that maximizes $P(Y=C|X=x)=P(X=x|Y=C)\pi_C$

Since $\ln(\omega)$ is monotonically increasing for $\omega > 0$, so

MLE for Isotropic Gaussian

For isotropic Gaussian, use the following MLE: