machine learning

press esc to navigate slides

Section	Topic
general	intro, linear algebra, gaussian, parameter estimation, bias-variance
regression	lin reg, LS, kernels, sparsity
dim reduction	dim reduction
classification	discr. vs. generative, nearest neighbor, DNNs, log. regression, lda/qda, decision trees, svms
optimization	problems, algorithms, duality, boosting, em

linear algebra review

matrix properties

nonsingular = invertible = nonzero determinant = null space of zero square
- $⟹$ rank = dimension
- ill-conditioned matrix - close to being singular - very small determinant

vector norms

$L_{p} -$ norms: $| | x | |_{p} = (\sum_{i} | x_{i} |^{p})^{1 / p}$
usually means
- $| | x | |^{2} = x^{T} x$

matrix norms

nuclear norm: $| | X | |_{*} = \sum_{i} σ_{i}$
frobenius norm = euclidean norm: $| | X | |_{F}^{2} = \sqrt{\sum_{i} σ_{i}^{2}}$
spectral norm = $L_{2}$ -norm: $| | X | |_{2} = \underset{max}{σ} (X)$

cauchy-shwartz inequality

$| x^{T} y | \leq | | x | |_{2} | | y | |_{2}$

equivalent to the triangle inequality $| | x + y | |_{2}^{2} \leq (| | x | |_{2} + | | y | |_{2})^{2}$

jensen's inequality

$f (E [X]) \leq E [f (X)]$ for convex f

eigenvalues

eigenvalue eqn:
- $det (A - λ I) = 0$ yields characteristic polynomial

evd

diagonalization = eigenvalue decomposition = spectral decomposition
assume A (nxn) is symmetric
- $A = Q Λ Q^{T}$
- Q := eigenvectors as columns, Q is orthonormal
- $Λ$ diagonal

svd

nxp matrix: $X = U Σ V^{T}$

cols of U (nxn) are eigenvectors of $X X^{T}$
cols of V (pxp) are eigenvectors of $X^{T} X$
r singular values on diagonal of (nxp)
- square roots of nonzero eigenvalues of both $X X^{T}$ and $X^{T} X$

eigen stuff

expressions when
- $det (A) = \prod_{i} λ_{i}$
- $t r (A) = \sum_{i} λ_{i}$
- $\underset{max}{λ} (A) = sup_{x \neq 0} \frac{x^{T} A x}{x^{T} x}$
- $\underset{min}{λ} (A) = inf_{x \neq 0} \frac{x^{T} A x}{x^{T} x}$

positive semi-definite (psd)

defn 1: all eigenvalues are nonnegative
defn 2: $x^{T} A x \geq 0 \forall x \in R^{n}$

psd notation

vectors: $x ⪯ y$ means x is less than y elementwise
matrices: means is PSD
- $v^{T} X v \leq v^{T} Y v \forall v$

matrix calculus

gradient vector $\nabla_{x} f (x)$ - partial derivatives with respect to each element of function

jacobian

function f: $R^{n} \to R^{m}$ Jacobian matrix :

J = [\begin{matrix} \frac{\partial f}{\partial x_{1}} & \dots & \frac{\partial f}{\partial x_{n}} \end{matrix}]

= [\begin{matrix} \frac{\partial f_{1}}{\partial x_{1}} & \dots & \frac{\partial f_{1}}{\partial x_{n}} \\ ⋮ & ⋱ & ⋮ \\ \frac{\partial f_{m}}{\partial x_{1}} & \dots & \frac{\partial f_{m}}{\partial x_{n}} \end{matrix}]

hessian

function f: $R^{n} \to R$

H = \nabla^{2} f (x)_{i j} = \frac{\partial^{2} f (x)}{\partial x_{i} \partial x_{j}}

 $= [\begin{matrix} \frac{\partial^{2} f}{\partial x_{1}^{2}} & \frac{\partial^{2} f}{\partial x_{1} \partial x_{2}} & \dots & \frac{\partial^{2} f}{\partial x_{1} \partial x_{n}} \\ \frac{\partial^{2} f}{\partial x_{2} \partial x_{1}} & \frac{\partial^{2} f}{\partial x_{2}^{2}} & \dots & \frac{\partial^{2} f}{\partial x_{2} \partial x_{n}} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ \frac{\partial^{2} f}{\partial x_{n} \partial x_{1}} & \frac{\partial^{2} f}{\partial x_{n} \partial x_{2}} & \dots & \frac{\partial^{2} f}{\partial x_{n}^{2}} \end{matrix}]$

nifty tricks

$x^{T} A x = t r (x x^{T} A) = \sum_{i, j} x_{i} A_{i, j} x_{j}$
$t r (A B)$ = sum of elementwise-products
if X, Y symmetric, $t r (Y X) = t r (Y \sum λ_{i} q_{i} q_{i}^{T})$
$A = U D V^{T} = \sum_{i} σ_{i} u_{i} v_{i}^{T} ⟹ A^{- 1} = V D^{- 1} U^{T}$

feature engineering

what is x?
what is y?
$ϕ (x)$ can be treated like $x$

lin. regression setup

n = number of data points

d = dimension of each data point

n {\underset{1}{\underset{⏟}{[\begin{matrix} ⋮ \\ y \\ ⋮ \end{matrix}]}} = n {\underset{d}{\underset{⏟}{[\begin{matrix} ⋮ \\ \dots X \dots \\ ⋮ \end{matrix}]}} \underset{1}{\underset{⏟}{[\begin{matrix} ⋮ \\ w \\ ⋮ \end{matrix}]}}} d

regularization

$\hat{y} = X \hat{w}$

Model	Loss
OLS	$\| \| y - \hat{y} \| \|^{2}$
Ridge	$\| \| y - \hat{y} \| \|^{2} + λ \| \| \hat{w} \| \|_{2}^{2}$
Lasso	$\| \| y - \hat{y} \| \|^{2} + λ \| \| \hat{w} \| \|_{1}$
Elastic Net	$\| \| y - \hat{y} \| \|^{2} + λ_{1} \| \| \hat{w} \| \|_{1} + λ_{2} \| \| \hat{w} \| \|_{2}^{2}$

ols solution

${\hat{w}}_{O L S} = (X^{T} X)^{- 1} X^{T} y$
2 derivations: least squares, orthogonal projection

ridge regression intuition

${\hat{w}}_{R I D G E} = (X^{T} X + λ I)^{- 1} X^{T} y$ 1d8XV

probabilistic model

assume a true underlying model
ex. $Y_{i} \sim N (θ^{T} X_{i}, σ^{2})$
this is equivalent to $P (Y_{i} | X_{i}; θ) = N (θ^{T} X_{i}, σ^{2})$

bayes rule

$\overset{posterior}{\overset{⏞}{p (θ | x)}} = \frac{\overset{likelihood}{\overset{⏞}{p (x | θ)}} \overset{prior}{\overset{⏞}{p (θ)}}}{p (x)}$ bayes2

likelihood

$L = p (d a t a | θ)$ ~ product over all n examples

$p (x | θ)$ ?
$p (y | x; θ)$ ?
$p (x, y | θ)$ ?
$\to$ depends on the problem + model

mle - maximum likelihood estimation

${\hat{θ}}_{M L E} = \underset{θ}{argmax} L$
associated with frequentist school of thought

map - maximum a posteriori

- $p (x)$ disappears because it doesn't depend on $θ$
associated with bayesian school of thought

mle vs. map

${\hat{θ}}_{M L E} = \underset{θ}{a r g m a x} \overset{likelihood}{\overset{⏞}{p (x | θ)}}$
- ${\hat{θ}}_{Bayes} = E_{θ} p (θ | x)$

bias

bias of a model:
- expectation over drawing new training sets from same distr.
could also have bias of a point estimate: $E [\hat{θ} - θ]$

variance

"estimation error"
variance of a model:
- expectation over training sets with fixed x

bias-variance trade-off

mean-squared error of model:
- = bias $^{2}$ + variance
- = $E [\hat{f} (x) - f (x)]^{2}$ + $E [(\hat{f (x)} - E [\hat{f (x)}])^{2}]$

biasvariance

definitions

- $μ$ is mean vector
- $Σ$ is covariance matrix

MultivariateNormal

mle gaussian estimation

$\hat{μ}, \hat{Σ} = a r g m a x P (x_{1}, . . ., x_{n} | μ, Σ)$
$\hat{μ} = \frac{1}{n} \sum x_{i}$
$\hat{Σ} = \frac{1}{n} \sum (x_{i} - \hat{μ}) (x_{i} - \hat{μ})^{T}$

weighted least squares

weight certain points more $ω_{i}$
${\hat{w}}_{wls} = a r g m i n (\sum ω_{i} (y_{i} - x_{i}^{T} w)^{2})$
$= (X^{T} Ω X)^{- 1} X^{T} Ω y$

total LS solution

- here, $σ$ is last singular value of $[X y]$

pca in python

X -= np.mean(X, axis=0) #zero-center data (nxd) 
cov = np.dot(X.T, X) / X.shape[0] #get cov. matrix (dxd) 
U, D, V = np.linalg.svd(cov) #compute svd, (all dxd) 
X_2d = np.dot(X, U[:, :2]) #project in 2d (nx2)

pca in practice

eigenvalue represents prop. of explained variance: $\sum λ_{i} = t r (Σ) = \sum V a r (X_{i})$
use svd
adaptive PCA is faster (sequential)

ex. ridge regression

reformulate the problem to be computationally efficient + nonlinear
- matrix inversion is ~ $O (d i m^{3})$
$\hat{w} = (\underset{d x d}{\underset{⏟}{X^{T} X}} + λ I)^{- 1} X^{T} y$ ~ faster when $d << n$
$\hat{w} = X^{T} (\underset{n x n}{\underset{⏟}{X X^{T}}} + λ I)^{- 1} y$ ~ faster when $n << d$

kernels

Screen Shot 2018-06-24 at 9.53.55 PM

$ϕ_{i}^{T} ϕ_{j} = ϕ (x_{i})^{T} ϕ (x_{j})$

ex. kernel ridge regression

linear kernel: $\hat{w} = X^{T} (X X^{T} + λ I)^{- 1} y$
generic kernel:
- at test time, $\hat{y} (x) = ϕ (x) ϕ^{T} (ϕ ϕ^{T} + λ I)^{- 1} y$
- only requires kernel products!

kernel trick ex.

$x = [x_{1}, x_{2}]$
$ϕ (x) = {[\begin{matrix} x_{1}^{2} & x_{2}^{2} & \sqrt{2} x_{1} x_{2} & \sqrt{2} x_{1} & \sqrt{2} x_{2} & 1 \end{matrix}]}^{T}$

$k (x, z) = \underset{O(augmented feature space)}{\underset{⏟}{ϕ (x)^{T} ϕ (z)}} = \underset{O(original feature space + log(degree))}{\underset{⏟}{(x^{T} z + 1)^{2}}}$

another ex. rbf kernel: $k (x, z) = \exp (- γ | | x - z | |^{2})$

overview

minimizing things
ex. $\underset{θ}{a r g m i n} \sum (y_{i} - f (x_{i}; θ))^{2}$

loss_surfaces

convexity

Hessian $\nabla^{2} f (x) ⪰ 0 \forall x$
$f (x_{2}) \geq f (x_{1}) + \nabla f (x_{1}) (x_{2} - x_{1})$

convexity continued

$t f (x_{1}) + (1 - t) f (x_{2}) \geq f (t x_{1} + (1 - t) x_{2})$

strong convexity + smoothness

$0 ⪯ \underset{strong convexity}{m I} ⪯ \nabla^{2} f (x) ⪯ \underset{smoothness}{M I}$

bounds

smoothness

M-smooth = Lipschitz continuous gradient: $| | \nabla f (x_{2}) - \nabla f (x_{1}) | | \leq M | | x_{2} - x_{1} | | \forall x_{1}, x_{2}$

Lipschitz continuous f	M-smooth

momentum demo

$θ^{(t + 1)} = θ^{(t)} - α_{t} \nabla f (θ^{(t)}) + \underset{momentum}{β_{t} (f (θ^{(t)}) - f (θ^{(t - 1)}))}$

newton-raphson

slide_8

apply to find roots of f'(x): $θ^{(t + 1)} = θ^{(t)} - \nabla^{2} f (θ^{(t)})^{- 1} \nabla f (θ^{(t)})$

gauss-newton

modify newton's method assuming we are minimizing nonlinear least squares
$θ^{(t + 1)} = θ^{(t)} - \nabla^{2} f (θ^{(t)})^{- 1} \nabla f (θ^{(t)})$
$θ^{(t + 1)} = θ^{(t)} + {(J^{T} J)}^{- 1} J^{T} Δ y$ $J$ is the Jacobian

training a perceptron

loss function: $L (x, y; w) = (\hat{y} - y)^{2}$
goal: $\frac{\partial L}{\partial w_{i}}$ for all weights
calculate efficiently with backprop

coding DNNs in numpy

from numpy import exp, array, random
X = array([[0, 0, 1], [1, 1, 1], [1, 0, 1], [0, 1, 1]])
Y = array([[0, 1, 1, 0]]).T
w = 2 * random.random((3, 1)) - 1
for iteration in range(10000):
    Yhat = 1 / (1 + exp(-(X @ w)))
    w += X.T @ (Y - Yhat) * Yhat * (1 - Yhat)
print(1 / (1 + exp(-(array([1, 0, 0] @ w))))

coding DNNs in advanced numpy

import tensorflow as tf
import torch

definitions

discriminative_vs_generative

discriminative: $p (y | x)$
generative: $p (x, y) = p (x | y) p (y)$

bayes classifier

risk: $E_{(X, Y)} [L (f (x), y)] = \sum_{x} p (x) \sum_{y} L (f (x), y) p (y | x)$
bayes classifier:
- given x, pick y that minimizes risk

bayes classifier example

with 0-1 error:
- let y be sentiment (positive or negative)
- let x be words

definitions

Exam_pass_logistic_curve

$σ (z) = \frac{1}{1 + e^{- z}}$
- threshold to predict
- not really regression

loss functions

log-loss = cross-entropy:
- $p (x)$ true $y$
- $q (x)$ predicted probability of y
corresponds to MLE for Bernoulli

Screen Shot 2018-07-02 at 11.26.42 AM

multiclass

one-hot encoding: $[1, 0, 0]$ , $[0, 1, 0]$ , $[0, 0, 1]$
softmax function: $σ (z)_{i} = \frac{\exp (z_{i})}{\sum_{j} \exp z_{j}}$
loss function still cross-entropy

multihierarchy

training

no closed form, but convex loss convex optimization!
- minimize loss on cross-entropy (where p(x) is modelled by sigmoid)
- or maximize likelihood

assumptions

- $P (x | y) \sim N (μ_{y}, Σ_{y})$ : there are |Y| of these
- $p (y) = \frac{n_{y}}{n}$ : 1 of these

EM

want to maximize complete log-likelihood $l (θ; x, z) = l o g p (x, z | θ)$ but don't know latent z

expectation step - values of z filled in
maximization step - parameters are adjusted based on z

simplifying the math

$x$ : observed vars, $z$ : latent vars, $q$ : assignments to z

E:
- lower bound on complete log-likelihood (pf: Jensen's inequality)
M: $θ^{(t + 1)} = \underset{θ}{a r g m i n} D (q^{(t + 1)} | | θ)$

how far are points?

decision boundary: { $x : w^{T} x - b = 0$ }

$D = \frac{| w^{T} (z - x_{0}) |}{| | w | |_{2}} = \frac{| w^{T} z - b |}{| | w | |_{2}}$

svm_proj

hard margin formulation

let $m = 1 / | | w | |_{2} ⟹$ unique soln

$min_{w, b} \frac{1}{2} | | w | |_{2}^{2} s . t . y_{i} (w^{T} x_{i} - b) \geq 1 \forall i$

$soft$ margin

$\begin{aligned} min_{w, b, ξ} & \frac{1}{2} | | w | |_{2}^{2} + C \sum_{i} ξ_{i} \\ s . t . & y_{i} (w^{T} x_{i} + b) \geq 1 - ξ_{i} \forall i \\ ξ_{i} \geq 0 \forall i \end{aligned}$

errs

binary classification

can rewrite by absorbing $ξ$ constraints

$min_{w, b} \frac{1}{2} | | w | |^{2} + C \sum_{i} max (1 - y_{i} (w^{T} x_{i} - b), 0)$

binary classification

Model	$\hat{θ}$ objective (minimize)
Perceptron	$\sum_{i} max (0, - y_{i} \cdot θ^{T} x_{i})$
Linear SVM	$θ^{T} θ + C \sum_{i} max (0, 1 - y_{i} \cdot θ^{T} x_{i})$
Logistic regression	$θ^{T} θ + C \sum_{i} \log [1 + \exp (- y_{i} \cdot θ^{T} x_{i})]$

problem

primal

$p^{*} = min f_{0} (x) s . t . f_{i} (x) \leq 0 h_{i} (x) = 0$

dual

 $d^{*} = max_{λ, ν} \overset{dual function g (λ, ν)}{\overset{⏞}{inf_{x} \underset{Lagrangian L (x, λ, ν)}{\underset{⏟}{f_{0} (x) + \sum λ_{i} f_{i} (x) + \sum ν_{i} h_{i} (x)}}}} s . t . λ ⪰ 0$