CS189 MT Notes

Lecture 1: 1/20/21

• Decision boundary has d-1 dimensions
• Training set error: Fraction of training images not classified correctly
• Test set error: Fraction of misclassified NEW images, not seen during training
• Outliers: points whose labels are atypical
• Overfitting: When test error deteroirates because classifier is sensitive to outliers
• Validation data is taken from training data
  • Train classifier with different hyperparams
• Training set: Used to learn model weights
• Validation set: Used to tune hyperparams
• Test set: Used as final evaluation of model
• Supervised learning:
  • Classification: Is this email spam?
  • Regression: How likely does this patient have cancer?
• Unsupervised learning:
  • Clustering: Which DNA sequences are similar?
  • Dimensionality reduction: What are common features of faces?

Lecture 2: 1/25/21

• Decision boundary: Boundary chosen by classifer to separate items
• Overfitting: When decision boundary fits sample points so well that it does not classify future points well
• Some classifiers work by computing a decision/predictor/discriminant function
  • A function that maps a pt x to a scalar st
    $f(x)>0⟹x\in C$ and vice versa. Pick one for the 0 case
  • Decision boundary is
    $\{x\in {\mathbb{R}}^d:f(x)=0\}$
  • This set is in
    $d-1$ dimensional space (isosurface of f, iso value = 0)
• Decision boundary is a linear plane (linear decision function)
  • $f(x)=w^{\mathrm{\top }}x+\alpha$,
  • Hyperplane:
    $H=\{x:w^{\mathrm{\top }}x=-\alpha \}$
  • $w$ is the normal vector of H (perpendicular to H)
  • If
    $w$ is unit vector,
    $w^{\mathrm{\top }}x+\alpha$ is the signed distance from x to H
  • Distance from H to origin is
    $\alpha$,
    $alpha=0⟷$ passes through origin
  • Coefficients in
    $w,\alpha$ are weights/params
• Linearly separable - if there exists a hyperplane that separates all sample pts in class C from all pts not in C

Math Review

• Vectors default to be column vectors
• Uppercase roman = matrix, RVs, sets
• Lowercase roman = vectors
• Greek = scalar
• Other scalars:
  • n = # of sample pts
  • d = # of features (per point) aka dimensionality
  • i, j, k are indices
• functions (ofen scalar):
  $f(\cdot )$

Centroid method

• Centroid method: compute mean
  ${\mu }_c$ of all pts in class C, mean
  ${\mu }_x$ of all pts not in C
• Use decision fn
  $f(x)=({\mu }_c-{\mu }_x{)}^{\mathrm{\top }}x-({\mu }_c-{\mu }_x)\frac{{\mu }_c+{\mu }_x}{2}$
  • $\alpha$ is such that
    $f(x)=0$ if it is the midpoint between
    ${\mu }_c,{\mu }_x$

Perceptron Algorithm

• Slow, but correct for linearly sep pts
• Numerical optimization algorithm - gradient descent
• For n sample pts
  $X_1,\dots X_n$ with labels
  $y_i\in \{-1,1\}$
• Consider decision boundary that passes through origin
• Goal: find weights w/ constraint:
  $y_i{X}_i^{\mathrm{\top }}w\ge 0$
  • $X_i^{\mathrm{\top }}w\ge 0$ if
    $y_i=1$
  • $X_i^{\mathrm{\top }}w\le 0$ if
    $y_i=-1$
• Objective/cost/risk function R:
  • positive if a constraint is violated
  • Use optimization to choose w that minimizes R
• Define loss function
  • $L(z,y_i)=\{\begin{array}{ll}0& y_{i}z\ge 0\\ -y_{i}z& \text{otherwise}\end{array}$
  • $z=X_i^{\mathrm{\top }}w$ is classifier prediction,
    $y_i$ is correct label
  • If
    $z$ has same sign as
    $y_i$, loss fn is zero
  • If z has wrong sign, loss fn is positive
• Risk/objective/cost fn:
  • $R(w)=\frac{1}{n}\sum _{i=1}^{n}L(X_i^{\mathrm{\top }}w,y_i)$
  • $R(w)=\frac{1}{n}\sum _{i\in V}-y_i{X}_i^{\mathrm{\top }}w$ with
    $V$ having all i st
    $y_i{X}_i^{\mathrm{\top }}w<0$
  • $R(w)=0$ if all X classified correctly, otherwise positive
• Goal: Find w that minimizes
  $R(w)$
  • $w=0$ is useless, don't want that

Lecture 3: 1/27/21

• Gradient descent: Find gradient of R wrt w, take step in opposite direction
• $\mathrm{\nabla }R(W)={\left[\begin{array}{ccc}\frac{\partial R}{\partial w_1}& \cdots & \frac{\partial R}{\partial w_d}\end{array}\right]}^{\mathrm{\top }}$
• ${\mathrm{\nabla }}_w(z^{\mathrm{\top }}w)=z$
• $\mathrm{\nabla }R(W)=-\sum _{i\in V}{y}_i{X}_i$
• Take step in
  $-\mathrm{\nabla }R(W)$ direction
• Algorithm:
• $w\leftarrow$ arbitrary nonzero vector (good choice is any
  $y_i{X}_i$)
• while
  $R(w)>0$:
  • $V\leftarrow$ set of indices that
    $y_i{X}_i^{\mathrm{\top }}w<0$
  • $w\leftarrow w+ϵ\sum _{i\in V}{y}_i{X}_i$
• return w
• $ϵ>0$ is the step size/learning rate
  • Chosen empirically
• Cons: Slow, each step takes
  $\mathcal{O}(nd)$ time - n dot product of vectors in
  ${\mathbb{R}}^n$
• Perceptron algorithm guarantees convergence no matter step size

Stochastic Gradient Descent

• Each step, pick 1 misclassified
  $X_i$
  • do gradient descent on loss fn
    $L(X_i^{\mathrm{\top }}w,y_i)$
• Known as the perceptron algorithm
• Each step takes
  $\mathcal{O}(d)$ time
• while
  $y_i{X}_i^{\mathrm{\top }}w<0$:
  • $w\leftarrow w+ϵy_i{X}_i$
• return w

Fictitious dimension

• If separating hyperplane does not pass origin, add a fictitious dimension
• $f(x)=w^{\mathrm{\top }}x+\alpha =\left[\begin{array}{ccc}{w}_1& w_2& \alpha \end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ 1\end{array}\right]$
• Sample pts in
  ${\mathbb{R}}^{d+1}$ all lying on hyerplane
  $x_{d+1}=1$
• Run perceptron algorithm in
  $d+1$ dimension

Hard-margin SVM

• Margin of a linear classifier is dist from deicision boundary to nearest sample pt
• Try to make margin as wide as possible
• If
  $||w||=1$, signed dist is
  $w^{\mathrm{\top }}{X}_i+\alpha$
  • Otherwise signed dist is
    ${\frac{w}{||w||}}^{\mathrm{\top }}{X}_i+\frac{\alpha }{||w||}$
• Hence the margin is
  $\underset{i}{min}\frac{1}{||w||}|w^{\mathrm{\top }}{X}_i+\alpha |\ge \frac{1}{||w||}$
• QP in
  $d+1$ dimensions,
  $n$ constraints
• Objective:
  $\underset{w,\alpha }{min}||w|{|}_2^2$
• Constraints:
  $y_i(w^{\mathrm{\top }}{x}_i+\alpha )\ge 1$ for
  $i=1\dots n$
  • Impossible for
    $w$ to be set to 0
• Has a unique solution (if any)
• Maximum margin classifier aka hard-margin SVM
• Margin =
  $\frac{1}{||w^{\ast }||}$
• Slab = 2*margin, margin is dist from boundary to nearest pt

Lecture 4: 2/1/21

Soft Margin SVM

• Margin is no longer dist from decision boundary to nearest pt
  • Just
    $\frac{1}{||w||}$
• Prevent abuse of slack by adding a loss term
• Objective: Find
  $w,\alpha ,{\xi }_i$ to
  $min||w|{|}^2+C\sum _{i=1}^n{\xi }_i$
• Constraints:
  $y_i(X_i^{\mathrm{\top }}w+\alpha )\ge 1-{\xi }_i$
  • ${\xi }_i\ge 0$
• QP in
  $d+n+1$ dimensional space and
  $2n$ constraints
• There is a tradeoff between C and
  $||w|{|}^2$
  • $C>0$ is a hyperparameter scalar

Column 1	Small C	Big C
Desire	Max margin $\frac{1}{|w|}$	Keep most slack variables 0 or small
Danger	Underfitting (misclassifies training data)	Overfitting (awesome training, awful test)
Outliers	Less sensitive	Very sensitive
Boundary	More "flat"	More sinuous/curvy

Features

• Make nonlinear features that lift points to a higher dimensional space
• High-d linear classifier <–> low-d nonlinear classifier
• Parabolic lifting map:
  $\mathrm{\Phi }:{\mathbb{R}}^d\to {\mathbb{R}}^{d+1}$
  • $\mathrm{\Phi }(x)=\left[\begin{array}{c}x\\ \Vert x{\Vert }^2\end{array}\right]$
  • Lifts x onto paraboloid
    $x_{d+1}=\Vert x{\Vert }^2$
  • Linear classifier in
    $\mathrm{\Phi }$ space induces a sphere classifier in
    $x$ space
• Theorem:
  $\mathrm{\Phi }(X_1),\dots \mathrm{\Phi }(X_n)$ are linearly separable iff
  $X_1,\dots X_n$ are separable by a hypersphere
• Proof: Consider hypersphere in
  ${\mathbb{R}}^d$ center c, radius
  $\rho$
• $\Vert x-c{\Vert }^2<{\rho }^2$
• $\Vert x{\Vert }^2-2c^{\mathrm{\top }}x+\Vert c{\Vert }^2<{\rho }^2$
• $\left[\begin{array}{cc}-2c^{\mathrm{\top }}& 1\end{array}\right]\left[\begin{array}{c}x\\ \Vert x{\Vert }^2\end{array}\right]<{\rho }^2-\Vert c{\Vert }^2$
• Normal vector in
  ${\mathbb{R}}^{d+1}$,
  $\mathrm{\Phi }(x)$
• Points inside sphere means same side of hyperplane in
  $\mathrm{\Phi }$ space

Axis-aligned ellipsoid/hyperboloid

• $\mathrm{\Phi }:{\mathbb{R}}^d\to {\mathbb{R}}^{2d}$
• $\mathrm{\Phi }(X)={\left[\begin{array}{ccccccccc}{x}_1^2& x_2^2& x_3^2& \dots & x_d^2& x_1& x_2& \dots & x_d\end{array}\right]}^{\mathrm{\top }}$
• 3D:
  $A{x}_1^2+B{x}_2^2+C{x}_3^2+D{x}_1+E{x}_2+F{x}_3+\alpha =0$
• Hyerplane is
  $w^{\mathrm{\top }}\mathrm{\Phi }(x)+\alpha =0$
  • $w=\left[\begin{array}{cccccc}A& B& C& D& E& F\end{array}\right]$

Ellipsoid/hyperboloid

• $\mathrm{\Phi }(x):{\mathbb{R}}^d\to {\mathbb{R}}^{(d^2+3d)/2}$
• 3D:
  $A{x}_1^2+B{x}_2^2+C{x}_3^2+D{x}_1{x}_2+E{x}_2{x}_3+F{x}_3{x}_1+G{x}_1+H{x}_2+I{x}_3+\alpha =0$
• Isosurface dfined by this equation is a quadric (2d: conic section)

Degree-p polynomial

• Ex. cubic in
  ${\mathbb{R}}^2$
• $\mathrm{\Phi }(x)={\left[\begin{array}{ccccccccc}{x}_1^3& x_1^2{x}_2& x_1{x}_2^2& x_2^3& x_1^2& x_1{x}_2& x_2^2& x_1& x_2\end{array}\right]}^{\mathrm{\top }}$
• $\mathrm{\Phi }(x):{\mathbb{R}}^d\to {\mathbb{R}}^{\mathcal{O}(d^p)}$
• Linear has smaller margin, higher degree gives wider margins
• Going to a dimension high enough makes it linearly separable, but could overfit

Edge Detection

• Edge detector: algorithm for approximating grayscale/color gradients in images
  • tap filter, sobel filter, oriented Gaussian derivative filter
• Compute gradients pretending it is a continuous field
• Collect line orientations in local histograms (each having 12 orientations), use histograms as features instead of raw pixels

Lecture 5: 2/3/21

ML Abstractions

• Application/data:
  • Is data labeled/classified?
  • Yes: Categorical (classification), quantitative(regression)
  • No: Similarity (clustering), positioning (dimensionality reduction)
• Model:
  • Decision functions: linear, polynomial, logistic
  • nearest neighbors, decision trees
  • Features
  • Low vs high capacity (linear has low, poly have high, neural nets have high): affect overfitting, underfitting, inference
  • Capacity - a measure of how complicated your model can get
• Optimization Problem
  • Variables, objective fn, constraints
    • Ex. unconstrainted, convex programs, least squares, PCA
• Optimization Algorithm
  • Gradient descent, simplex, SVD

Optimization Problems

• Unconstrained: Find w that minimizes a continuous objective fn
  $f(w)$, f is smooth if gradient is continuous too
• Global min:
  $f(w)\le f(v),\mathrm{\forall }v$
• Local min:
  $f(w)\le f(v),\mathrm{\forall }v$ in tiny ball centered at w
• Finding local min is easy, gloal min is hard
• Except for convex functions
  • Line segment connecting 2 points does not go below f
  • Perceptron risk fn is convex and nonsmooth
• A convex fn has either:
  • no min (goes to
    $-\mathrm{\infty }$)
  • just one local min which is the global min
  • Connected set of local min which are all global min
• Algorithms for smooth f
  • Gradient descent
    • blind : repeat
      $w\leftarrow w-ϵ\mathrm{\nabla }f(w)$
    • stochastic (just 1 training pt at a time):
      $w\leftarrow w-ϵL(y_i,z_i)$
    • line search
  • Newton's method (needs Hessian matrix)
  • Nonlinear conjugate gradient
• Algorithms for nonsmooth f
  • Gradient descent
  • BFGS
• These algs find local min
• Line search: Find local min along search direction by solving an optimization problem in 1D
  • Secant method (smooth only)
  • Newton-Raphson (smooth only, may need Hessian)
  • Direct line search (non smooth) like golden section search
• Constrained Optimization (smooth equality constraints)
  • Goal: Find w that minimizes
    $f(w)$ subject to
    $g(w)=0$ where g is smooth
  • Alg: Use lagrange multipliers
• Linear Program
  • Linear objective, linear ineq constraints
  • Goal: Find w that maximizes
    $c^{\mathrm{\top }}w$ subject to
    $Aw\le b$
    • $A_i^{\mathrm{\top }}w\le b_i$ for
      $i\in [1,n]$
• Feasible region: Set of pts that satisfy all constraints
  • LP feasible region is a polytope (not always bounded/finite)
• Point set P is convex if every pair of points' line segment lies fully in P
• Active constraints: constraints that achieve equality at optimum

Lecture 6: 2/8/21

• Decision theory/risk minimization
  • Multiple sample pts w/ diff classes can lie at same pt
  • Want a probabilistic classifier
• Example: 10% population has cancer, 90% doesn't
  
  
• Posterior probability:
  $P(Y=1|X)$
• Prior probability:
  $P(Y=1)$
• Loss function
  $L(z,y)$ where z is prediction, y is true label
  • Loss function specifies how bad it is if classifier predicts z but true class is y
  • 
  • 36% loss of 5 is worse than 64% loss of 1, so recommend further cancer screening
  • 0-1 loss function is 1 for incorrect, 0 for correct
  • Loss function does not need to be convex
• Risk for decision rule r is expected loss over all values of x,y
  • $R(r)=E[L(r(X),Y)]$
  • $\sum _x(L(r(x),1)P(Y=1|X=x)+L(r(x),-1)P(Y=-1|X=x))P(X=x)$
• Bayes decision rule/Bayes classifier is fn
  $r^{\ast }$ that minimizes functional
  $R(r)$

• If L is symmetric, pick the class with the biggest posterior probability
• Bayes risk/optimal risk is risk of Bayes classifier
• No decision rule that gives lower risk
• Deriving/using
  $r^{\ast }$ is called risk minimization
• Expected values of
  $g(X)=E[g(X)]=\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}g(x)f(x)dx$
• Mean:
  $\mu =\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}xf(x)dx$
• If L is 0-1 loss,
  $R(r)$ is probability that r(x) is wrong
  • Bayes optimal decision boundary is
    $\{x:P(Y=1|X=x)=0.5\}$

3 ways to build classifiers

• Generative models (ex. LDA: Linear Discriminant Analysis)
  • Assume sample pts come from probability distributions, different for each class
  • Guess form of distribution
  • For each class C, fit distribution params to class C pts, giving
    $f(X|Y=c)$
  • For each c, estimate
    $P(Y=c)$
  • Bayes thm gives
    $P(Y|X)$
  • If 0-1 loss, pick class C that maximizes
    $P(Y=c|X=x)$ equivalently maximizes
    $f(X=x|Y=c)P(Y=c)$
• Discriminative models (ex. Logistic regression)
  • Skip prior probabilities, model
    $P(Y|X)$ directly
• Find decision boundary (ex. SVM)
• Advantages of 1,2:
  $P(Y|X)$ tells you probability that your guess is wrong
• Advantage of 1: Diagnose outliers if P(X) is very small
• Disadvantage of 1: Often hard to estimate distributions correctly, real distributions rarely match standard ones

Lecture 7: 2/10/21

• Gaussian Discriminant Analysis (GDA): Each class comes from a normal distribution
• Isotropic normal dist:
  $X\sim N(\mu ,{\sigma }^2)$:
  $f(x)=\frac{1}{(\sqrt{2\pi }\sigma {)}^d}\exp (-\frac{\Vert x-\mu {\Vert }^2}{2{\sigma }^2})$
  • $\mu ,x$ are length d vectors,
    $\sigma$ is a scalar
  • For each class C, estimate mean
    ${\mu }_c$, variance
    ${\sigma }_c^2$, prior
    ${\pi }_c=P(Y=C)$
  • Given x, Bayes decision rule
    $r^{\ast }(x)$ predicts class C that maximizes
    $f(X=x|Y=C){\pi }_C$
• $Q_c(x)=\ln ((\sqrt{2\pi }{)}^d)f_c(x){\pi }_c)=-\frac{\Vert x-\mu {\Vert }^2}{2{\sigma }^2}-d\ln ({\sigma }_c)+\ln ({\pi }_c)$
  • Quadratic in x, easier to optimize
  • Find
    $\arg \underset{c}{max}{Q}_c(x)$
• Baye's decision boundary is where
  $Q_c(x)-Q_d(x)=0$
  • In 1D, may have 1 or 2 or 0 pts
    
    
• Use Bayes' to recover posterior probabilities in 2 clsas
  • $P(Y=C|X)=\frac{f(X|Y=C){\pi }_c}{f(X|Y=C){\pi }_c+f(X|Y=D){\pi }_d}$
  • $=s(Q_C(x)-Q_D(x))$
• Logistic/sigmoid function:
  $s(\gamma )=\frac{1}{1+e^{-\gamma }}$

Linear Discriminant Analysis (LDA)

• Variant of QDA that has linear decision boundaries
  • Less likely to overfit
  • Less true probabilistic estimation
  • Use validation of both methods to see which is better
• Assume that all gaussians have same variance
• $Q_C(x)-Q_D(x)={\left(\frac{({\mu }_C-{\mu }_D)}{{\sigma }^2}\right)}^{\mathrm{\top }}x+(-\frac{\Vert {\mu }_C{\Vert }^2-\Vert {\mu }_D{\Vert }^2}{2{\sigma }^2}-\ln ({\pi }_c)-\ln ({\pi }_d))$
• Choose C that maximizes linear discriminant fn
  • ${\left(\frac{{\mu }_C}{{\sigma }^2}\right)}^{\mathrm{\top }}x-\frac{\Vert {\mu }_C{\Vert }^2}{2{\sigma }^2}+\ln ({\pi }_c)$
• Generative model as opposed to discriminative model

Maximum Likelihood Estimation (MLE)

• Flip biased coin, heads with prob
  $p$ and tails with prob
  $1-p$
• Goal: estimate
  $p$
• num of heads are
  $X\sim B(n,p)$, binomial dist
• $\mathcal{L}$ is the likelihood fn
  • $\mathcal{L}(p)=P(X=8)=45p^8(1-p{)}^2$
  • Should be as a function of distribution parameters
• MLE is a method of estimating params of a statistical distribution by picking params that maximize
  $\mathcal{L}$
  • Is a method of density estimation: estimating PDF from data
  • Find p that maximizes
    $\mathcal{L}(p)$
• Likelihood of Gaussian
  • $\mathcal{L}(\mu ,\sigma ;X_1,X_2,\dots X_n)=f(X_1)f(X_2)\cdots f(X_n)$
  • $\mathcal{l}$ is
    $\ln$ likelihood of
    $\mathcal{L}$
  • Maximizing l and log likelihood are same
  • $\mathcal{l}(\mu ,\sigma ;X_1,X_2,\dots X_n)=\ln f(X_1)+\ln f(X_2)\cdots +\ln f(X_n)$
  • $=\sum _{i=1}^n\frac{\Vert X_i-\mu {\Vert }^2}{2{\sigma }^2}-d\ln \sqrt{2\pi }-d\ln \sigma )$
    • Which is a summation of ln of normal PDF
  • Want to set
    ${\mathrm{\nabla }}_{\mu }\mathcal{l}=0,\frac{\partial \mathcal{l}}{\partial \sigma }=0$
    • ${\mathrm{\nabla }}_{\mu }\mathcal{l}=0⟹\hat{\mu }=\frac{1}{n}\sum _{i=1}^n{X}_i$
    • $\frac{\partial \mathcal{l}}{\partial \sigma }=0⟹{\hat{\sigma }}^2=\frac{1}{dn}\sum _{i=1}^n\Vert X_i-\mu {\Vert }^2$
      • Use
        $\hat{\mu }$ for
        $\mu$
• Tells us to use sample mean and variance of pts in class C to estimate mean and variance of Gaussian for class C
• For QDA: estimate conditional mean
  $\widehat{{\mu }_c}$ and conditional variance
  ${\widehat{{\sigma }_c}}^2$ of each class C separately
  • $\widehat{{\pi }_c}=\frac{n_c}{\sum n_D}$
    • Denominator is total sample pts in all classes
• For LDA: SAme means and priors, 1 variance for all classes
  • Pooled within-class variance:
    ${\hat{\sigma }}^2=\frac{1}{dn}\sum _C\sum _{\{i:y_i=c\}}\Vert X_i-{\hat{\mu }}_c{\Vert }^2$

Lecture 8: 2/17/21

• For
  $v,\lambda ,A$, v is an evec of
  $A^k$ with
  ${\lambda }^k$
• If A is invertible,
  $A^{-1}$ has evec v with
  $\frac{1}{\lambda }$
• Spectral theorem: Every real symmetric nxn matrix has real eigenvalues and n mutually orthogonal evecs
• $\Vert A^{-1}x{\Vert }^2=1$ isan ellpisoid with axes
  $v_1,\dots v_n$ and radii
  ${\lambda }_1,\dots {\lambda }_n$
• Special case if A is diagonal, evecs are coordinate axes and ellipsoid is axis-aligned
• Symmetric matrix is:
  • PD: All pos eval
  • PSD: All nonneg evals
  • Indefinite matrix: has at least 1 pos eval and 1 neg eval
  • Invertible: Has no zero eigenvalue
• $x^{\mathrm{\top }}{A}^{-2}x$ will be PD bc evecs are squared
• Orthonormal matrix: acts like rotation or reflection
• Thm:
  $A=V\mathrm{\Lambda }{V}^{\mathrm{\top }}=\sum _{i=1}^n{\lambda }_i{v}_i{v}_i^{\mathrm{\top }}$

Lecture 8: 2/22/21

Anisotropic Gaussians

• Normal PDF:
  $f(x)=n(q(x))=\frac{1}{\sqrt{(2\pi {)}^d|\mathrm{\Sigma }|}}\exp (-\frac{1}{2}(x-\mu {)}^{\mathrm{\top }}{\mathrm{\Sigma }}^{-1}(x-\mu ))$
  • $n(q)=\frac{1}{\sqrt{(2\pi {)}^d|\mathrm{\Sigma }|}}{e}^{-q/2}$
    • $\mathbb{R}\to \mathbb{R}$ (exponential)
  • $q(x)=(x-\mu {)}^{\mathrm{\top }}{\mathrm{\Sigma }}^{-1}(x-\mu )$
    • ${\mathbb{R}}^d\to \mathbb{R}$ (quadratic)
• Covariance matrix:
  $\mathrm{\Sigma }=V\mathrm{\Gamma }{V}^{\mathrm{\top }}$
  • Eigenvalues of
    $\mathrm{\Sigma }$ are variances along evecs
    ${\mathrm{\Gamma }}_{ii}={\sigma }_i^2$
• ${\mathrm{\Sigma }}^{\frac{1}{2}}=V{\mathrm{\Gamma }}^{\frac{1}{2}}{V}^{\mathrm{\top }}$
  • Maps spheres to ellipsoids
  • Eigenvalues of
    ${\mathrm{\Sigma }}^{\frac{1}{2}}$ are stdev
    ${\mathrm{\Gamma }}_{ii}^{\frac{1}{2}}={\sigma }_i$ (Gaussian width/ellipsoid radii)

MLE for Anisotropic Gaussians

• Given sample pts and classes, find best-fit Gaussians
• QDA:
  ${\hat{\mathrm{\Sigma }}}_c=\frac{1}{n_c}\sum _{i:y_i=C}(X_i-{\hat{\mu }}_c)(X_i-{\hat{\mu }}_c{)}^{\mathrm{\top }}$
  • Conditional covariance (for pts in class C)
  • Outer product, dxd matrix
  • ${\hat{\pi }}_c,{\hat{\mu }}_c$ same as before
• sigmac always PSD but not always PD
• Choose C to maximize discriminant fn
  
  
• Decision fn is quadratic, may be indefinite
• LDA interpeted as projecting points on a line
• For 2 classes
  • LDA has d+1 parameters (w,
    $\alpha$)
  • QDA has
    $\frac{d(d+3)}{2}+1$ params
  • QDA more likely to overfit
  • With added features LDA gan give nonlinear, QDA nonquadratic
  • We don't get true optimum Bayes classifier (estimate distributions from finite data)
  • Changing priors/loss = adding constants to discriminant fns
  • Posteroir gives decision boundaries for 10% probability, 50%, 90%
    • Choosing isovalue = p same as
    • Choosing asymmetric loss p for false pos, 1-p for false neg OR
      ${\pi }_c=1-p,{\pi }_d=p$

Terminology

• Let X be n x d design matrix of sample pts
• Each row i of X is a sample pt
  $X_i^{\mathrm{\top }}$
• Centering X: Subtract
  ${\mu }^{\mathrm{\top }}$ from each row of X
  $X\to \dot{X}$
• Let R be uniform distribution on sample pts
• Sample cov matrix is
  $Var(R)=\frac{1}{n}{\dot{X}}^{\mathrm{\top }}\dot{X}$
• Decorrelating
  $\dot{X}$: Apply rotation
  $Z=\dot{X}V$
  • $Var(R)=V\mathrm{\Lambda }{V}^{\mathrm{\top }}$
  • $Var(Z)=\mathrm{\Lambda }$
  • Sphering
    $\dot{X}$:
    $W=\dot{X}Var(R{)}^{-1/2}$
• Whitening X: Centering + sphering
  • W has cov matrix I

Lecture 9: 2/24/21

• Regression: Fitting curves to data
• Classification: Given pt, predict its class
• Regression: Given pt, predict numerical value
• Choose form of regerssion fn
  $h(x;p)$ with parameter p
  • Like decision fn in classification
• Choose a cost fn (objective fn) to optimize
  • Usually based on a loss fn
• Regression fns:
  • 1. Linear:
       $h(x;w,\alpha )=w^{\mathrm{\top }}x+\alpha$
  • 2. Polynomial: Add features for linear
  • 3. Logistic:
       $h(x:w,\alpha )=s(w^{\mathrm{\top }}x+\alpha )$
    • $s(\gamma )=\frac{1}{1+e^{-\gamma }}$
• Loss fns: z is prediction
  $h(x)$, y is true label
  • A) Squared error:
    $L(z,y)=(z-y{)}^2$
  • B) Absolute error:
    $L(z,y)=|z-y|$
  • C) Logistic loss/cross-entropy:
    $L(z,y)=-y\ln (z)-(1-y)\ln (1-z)$
• Cost fns to minimize
  • a) Mean loss:
    $J(h)=\frac{1}{n}\sum _{i=1}^{n}L(h(X_i),y_i)$
  • b) Max loss:
    $J(h)=\underset{i=1\dots n}{max}L(h(X_i),y_i)$
  • c) Weighted sum:
    $J(h)=\sum _{i=1}^n{\omega }_{i}L(h(X_i),y_i)$
  • d)
    $l_2$ penalized/regularized:
    $J(h)=\dots +\lambda \Vert w{\Vert }_2^2$
    • $\dots$ is one of the previous options
  • e)
    $l_1$ penalized/regularized:
    $J(h)=\dots +\lambda \Vert w{\Vert }_1$
• Famous regression methods:
  • Least squares linear regression: 1Aa
    • Quadratic cost, min w/ calculus
  • Weighted least-squares linear: 1Ac
    • Quadratic cost, min w/ calculus
  • Ridge regression: 1Ad
    • Quadratic cost, min w/ calculus
  • LASSO: 1Ae
    • QP w/ exponential num of constraints
  • Logistic regression: 3Ca
    • Convex cost fn, min w/ gradient descent/Newton's
  • Least absolute deviations: 1Ba
    • LP
  • Chebyshev criterion: 1Bb
    • LP

Least Squares Linear Regression

• Linear regression fn (1) + squared loss fn (A) + cost fn (a)
• Optimization problem:
  $\underset{w,\alpha }{min}\sum _{i=1}^n(X_i^{\mathrm{\top }}w+\alpha -y_i{)}^2$
• X is n x d design matrix of sample pts
• y is n-vector of scalar labels
• $X_i^{\mathrm{\top }}$ transposes the column vector point
• Feature column:
  $X_{\ast j}$
• Usually
  $n>d$
• X is now n x (d+1) matrix, w is a (d+1) vector
• $\left[\begin{array}{ccc}{x}_1& x_2& 1\end{array}\right]\left[\begin{array}{c}{w}_1\\ w_2\\ \alpha \end{array}\right]$
• Residual sum of squares:
  $RSS(w)=\underset{w}{min}\Vert Xw-y{\Vert }^2$
• Optimize with calculus:
  • If
    $X^{\mathrm{\top }}X$ is singular, problem is unconstraind (all pts fall on hyperplane)
  • Never overconstrained
  • Linear solver to find
    $w^{\ast }=(X^{\mathrm{\top }}X{)}^{-1}{X}^{\mathrm{\top }}y$
  • Pseudoinverse (d+1, n):
    $X^{+}=(X^{\mathrm{\top }}X{)}^{-1}{X}^{\mathrm{\top }}$
  • Pseudoinverse is a left inverse:
    $X^{+}X=(X^{\mathrm{\top }}X{)}^{-1}{X}^{\mathrm{\top }}X=I$
  • Predicted values are
    $\hat{y}=Xw=X{X}^{+}y=Hy$
  • Hat matrix:
    $H=X{X}^{+}$ (n x n matrix)
• Advantage: Easy to compute, unique/stable solution
• Disadvantage: Very sensitive to outliers bc errors are squared, fails if
  $X^{\mathrm{\top }}X$ is singular

Logistic Regression

• Logistic regerssion fn (3) + logistic loss fn © + cost fn (a)
• Fits probabilities in range (0,1)
• Discriminative model (as opposed to QDA/LDA being generative models)
• $\underset{w}{min}J(w)=\underset{w}{min}\sum _{i=1}^{n}L(X_{i}w,y_i)=\underset{w}{min}-\sum _{i=1}^n(y_i\ln (X_{i}w)+(1-y_i)\ln (1-X_{i}w))$
• $J(w)$ is convex, solve by gradient descent
• $s^{\prime }(\gamma )=s(\gamma )(1-s(\gamma ))$
• $s_i=s(X_{i}w)$,
  ${\mathrm{\nabla }}_{w}J=-X^{\mathrm{\top }}(y-s(Xw))$, with
  $s(Xw)$ applied elementwise
• Gradient descent rule:
  $w\leftarrow w+ϵX^{\mathrm{\top }}(y-s(Xw))$
• SGD:
  $w\leftarrow w+ϵ(y_i-s(X_{i}w))X_i$
  • Shuffle pts into random order, process one by one
  • For large n, sometimes converges before visiting all pts
• Logistic regression always separates linearly separable pts
• ${\mathrm{\nabla }}_w^{2}J(w)=\sum _{i=1}^n{s}_i(1-s_i)X_i{X}_i^{\mathrm{\top }}=X^{\mathrm{\top }}\mathrm{\Omega }X$
  • $\mathrm{\Omega }=diag(s_i(1-s_i))\succ 0$ making it PD
  • So
    $X^{\mathrm{\top }}\mathrm{\Omega }X⪰0$ so
    $J(w)$ is convex
  • Find solution to
    $(X^{\mathrm{\top }}\mathrm{\Omega }X)e=X^{\mathrm{\top }}(y-s)$
  • Example of iteratively reweighted least squares
  • Misclassified points far from decision boundary have large influence
  • Points close to decision boundary also has medium to large influence
• LDA vs Logistic regression
• LDA Advantages:
  • For well separated classes LDA is stable, logreg is unstable
  • $>2$ classes easy and elegant, logreg needs modifications (softmax regression)
  • LDA slightly more accurate when classes nearly normal, esp if n is small
• Logreg advantages:
  • More emphasis on decision boundary, always separates linearly separable pts
  • More robust on some non-Gaussian distributions (w/ large skew)

Lecture 10: 3/1/21

Least Squares Polynomial Regression

• Replace each
  $X_i$ with feature vector
  $\mathrm{\Phi }(X_i)$
  • Ex.
    $\mathrm{\Phi }(X_i)=\left[\begin{array}{cccccc}{X}_{i1}^2& X_{i1}{X}_{i2}& X_{i2}^2& X_{i1}& X_{i2}& 1\end{array}\right]$
  • Can also use non polynomimal features
• Logistic regression + quadratic features = some form of posteriors like QDA
• Very easy to overfit

Weighted Least-Squares Regression

• Linear regression fn (1) + squared loss fn (A) + cost fn ©
• Assign each sample pt a weight
  ${\omega }_i$, create
  $\mathrm{\Omega }=diag({\omega }_i)$
  • Bigger
    ${\omega }_i$ means work harder to minimize
    $|{\hat{y}}_i-y_i{|}^2$
• $\underset{w}{min}(Xw-y{)}^{\mathrm{\top }}\mathrm{\Omega }(Xw-y)=\sum _{i=1}^n{\omega }_i(X_{i}w-y_i{)}^2$
  • $X^{\mathrm{\top }}\mathrm{\Omega }Xw=X^{\mathrm{\top }}\mathrm{\Omega }y$, solve for
    $w$

Newton's Method

• Iterative optimization method for smooth fn
  $J(w)$
• Often much faster than gradient descent
• Approximate
  $J(w)$ by quadratic fn
• $\mathrm{\nabla }J(w)=\mathrm{\nabla }J(v)+({\mathrm{\nabla }}^{2}J(v))(w-v)$
• $w=v-({\mathrm{\nabla }}^{2}J(v){)}^{-1}\mathrm{\nabla }J(v)$
• Repeat until convergence
• Warnings:
  • Doesn't know diff between minima, maxima, saddle pts
  • Starting pt must be close enough to desired critical point

Roc Curves

• For test sets to evaluate classifier
• Receiver Operator Characteristics
• Rate of FP vs TP for range of settings
• x-axis is False Positive rate = % of negative items incorrectly classified as pos
• y-axis is True positive rate = % of pos classified as pos
• Top right: always classify positive (
  $P\ge 0$)
• Bottom left: Always classify negative (
  $P>1$)
• Want high area under the curve (close to 1)
  
  

Lecture 11: 3/3/21

Statistical Justifications for Regression

• Sample pts come from unknown prob dist
  $X_i\sim D$
• y values are sum of unknown nonrandom fn + random noise
  • $y_i=g(X_i)+{ϵ}_i,ϵ\sim D^{\prime }$ with
    $D^{\prime }$ having mean 0
• Goal of regression: find h that estimates
  $g$
• Ideal approach: Choose
  $h(x)=E_Y[Y|X=x]=g(x)+E[ϵ]=g(x)$

Least Squares regression for MLE

• Suppose
  ${ϵ}_i\sim \mathcal{N}(0,{\sigma }^2)$
  • $y_i\sim \mathcal{N}(g(X_i),{\sigma }^2)$
• $l(g;X,y)=\ln (F(y_1)f(y_2)f(y_n))=-\frac{1}{2{\sigma }^2}\sum (y_i-g(X_i){)}^2-const$
  • MLE over g is minimizing sum of squared errors

Empirical Risk

• Risk for hypothesis h is xpected loss
  $R(h)=E[L]$
• Discriminative: Don't know X dist D
• Empirical distribution: discrete uniform distribution over the sample pts
• Empirical risk: Expected loss under empirical distribution
  • $\hat{R}(h)=\frac{1}{n}\sum _{i=1}^{n}L(h(X_i),y_i)$
  • So minimize sum of loss fns

Logistic Loss for MLE

• Actual probability pt
  $X_i$ is in class C is
  $y_i$, predicted prob is
  $h(X_i)$
• Imagine
  $\beta$ duplicate copies of
  $X_i$
  • $y_i\beta$ are in class c,
    $(q-y_i)\beta$ copies are not
  • $\mathcal{L}(h;X,y)=\prod h(X_i{)}^{y_i\beta }(1-h(X_i){)}^{(1-y_i)\beta }$
  • $minl(h)=-\beta \sum$ logistic loss fn
    $L(h(X_i),y_i)$
    • Logistic loss is
      $-y_i\ln (z_i)-(1-y_i)\ln (q-z_i)$
  • Max Likelihood –> Min sum of logistic loss fns

Bias-Variance Decomposition

• 2 source of error in hypothesis:
  • bias: Error due to inability of hypothesis to fit g perfectly
  • variance: Error due to random noise in data
• Model:
  $X_i\sim D,{ϵ}_i\sim D^{\prime },y_i=g(X_i)+{ϵ}_i$
  • Fit hypothesis h to X,y
  • h is a RV with random weights
• Consider arbitrary pt
  $z,\gamma =g(z)+ϵ$
  • $E[\gamma ]=g(z),var(\gamma )=var(ϵ)$
• Risk fn when loss = squared error:
  $r(h)=E[L(h(z),\gamma )]$
  • Taking expectation over all possible training sets X,y, values of
    $gamma$
  • $R(h)=E[(h(z)-\gamma {)}^2]$
  • $R(h)=(E[h(z)]-g(z){)}^2+Var(h(z))+Var(ϵ)$
    • First term: bias^2
    • Second term: variance of method
    • Third term: Irreducible error
• Underfitting = too much bias
• Most overfitting = too much variance
• Training error reflects bias but not variance
• Most dist var
  $\to 0$ as
  $n\to \mathrm{\infty }$
• If h can fit g exactly, many distributions bias
  $\to 0$ as
  $n\to \mathrm{\infty }$
• If h cannotfit g well, bias is large for most points
• Adding a good feature reduces bias, adding a bad feature rarely increases it
  • Good features reduce bias more than it increases variance
• Adding a feature usually increases variance
• Noise in test set affects only var(
  $ϵ$)
  • Noise in training set affects only bias and var of h
• Can't precisely measure bias and variance of real world data
• Can test learning algs by choosing g and making synthetic data

Lecture 12: 3/8/21

Ridge Regression

• 1 + A + d
  • l2 penalized mean loss
• $min\Vert Xw-y{\Vert }^2+\lambda \Vert w^{\prime }{\Vert }^2$
  • $w^{\prime }$ is
    $w$ with component
    $\alpha$ replaced by zero
  • Don't penalize
    $\alpha$
  • Regularization term/penality term for shrinkage
  • Small
    $\Vert w^{\prime }\Vert$ guarantees PD normal eqs
  • Reduces overfitting by reducing variance by penalizing large weights
  • Normal equations:
    $(X^{\mathrm{\top }}X+\lambda I^{\prime })w=X^{\mathrm{\top }}y$
    • $I^{\prime }\triangleq I$ with bottom right = 0
• Solve for w, return
  $h(z)=w^{\mathrm{\top }}z$
• Increasing
  $\lambda$ means more regularization
• For
  $y=Xv+e$, e being noise
  • Variance of RR is
    $var(z^{\mathrm{\top }}(X^{\mathrm{\top }}X+\lambda I^{\prime }{)}^{-1}{X}^{\mathrm{\top }}e)$

Bayesian Justification

• Prior probability:
  $w^{\prime }\sim N(0,{\sigma }^2)$
• Apply MLE
• Max log posterior:
  $\ln (L(w))+\ln (f(w^{\prime }))-const$
  • Min
    $min\Vert Xw-y{\Vert }^2+\lambda \Vert w^{\prime }{\Vert }^2$

Feature Subset Selection

• All features increase variance, not all features reduce bias
• Idea: Identify poorly predictive features, ignore them (weight 0)
  • Less overfitting, smaller test errors
  • 2nd motivation: inference
• Usually hard b/c features can partly encode same info
• Algorithm: Try all
  $2^d-1$ subsets of features
  • Slow, use cross validation
• Heuristic 1: Forward stepwise selection
  • Start with null model (0 features)
  • Repeatedly add best feature until validation error increases
  • Train
    $O(d^2)$ models
  • Not perfect, won't find best 2-features model if neither yields best 1-feature model
• Heuristic 2: Backward stepwise selection
  • Start with all d features, repeatedely remove features that give best reduction in val error
  • Trains
    $O(d^2)$ models

LASSO

• Regression w/ regularization: 1 + A + e
  • l1 penalized mean loss
  • $min\Vert Xw-y{\Vert }^2+\lambda \Vert w^{\prime }{\Vert }_1$
• Algs: subgradient descent, least-angle regression