k-Nearest Neighbors

• k-Nearest Neighbors (k-NN): supervised machine learning algorithm used for classification (predicting a class label) and regression (predicting a numeric value)
  
  • supervised: an algorithm learns to map input data to a specific output based on example input-output pairs (unsupervised: model identifies patterns or structures in unlabeled datamodel identifies patterns or structures in unlabeled data)
    
  • intuitively: to classify a new point, look at the labels of the closest data points and assign the most common label
  • 1-nearest neighbor: given training data \mathcal D=\{(x_i,y_i)\}_{i=1}^N$\mathcal D=\{(x_i,y_i)\}_{i=1}^N$, where x_i \in \R^D$x_i \in \R^D$ is the feature vector and y_i$y_i$ are the labels...
    1. define distance metric (usually Euclidian distance)
    2. compute distance from new sample to all training samples
    3. select nearest neighbor
    4. assign its label to the new point
    • creates Voronoi tessellation; poor generalization
  • k-nearest neighbors: p(y=c|x,k)=\frac1k\sum_{i\in N_k(x)}I(y_i=c)$p(y=c|x,k)=\frac1k\sum_{i\in N_k(x)}I(y_i=c)$; \hat y=\argmax_c p(y=c|x,k)$\hat y=\argmax_c p(y=c|x,k)$ (among the k$k$ nearest neighbors of x$x$, how many belong to class c$c$?)
    • in other words: p(y=c|x,k)=\frac{\#\text{neighbors with class c}}k$p(y=c|x,k)=\frac{\#\text{neighbors with class c}}k$ (e.g. 3 setosa neigbors out of 5: \frac35$\frac35$)
    • x$x$: feature vector of the new data point we want to classify (e.g. if the features are petal width and length, then x=(5.1,1.8)$x=(5.1,1.8)$ represents a new flower)
    • y$y$: class label (target variable, e.g. y\in\{\text{setosa,versicolor,virginica}\}$y\in\{\text{setosa,versicolor,virginica}\}$)
    • c$c$: specific class label being evaluated (e.g. we compute p(y=\text{setosa}|x,k),p(y=\text{versicolor}|x,k),p(y=\text{virginica}|x,k)$p(y=\text{setosa}|x,k),p(y=\text{versicolor}|x,k),p(y=\text{virginica}|x,k)$)
    • k$k$: hyperparameter; number of nearest neighbors considered
    • N_k(x)$N_k(x)$: set of k$k$ nearest neighbors of x$x$ (indices of k$k$ closest training points to x$x$)
    • I(e)$I(e)$: indicator variable (1 if e$e$ is true, 0 else)
    • \hat y$\hat y$: predicted class label (class with highest probability)
    • weighted k-NN: p(y=c|x,k) = \frac1Z \sum_{i\in N_k(x)}\frac1{d(x,x_i)}I(y_i=c)$p(y=c|x,k) = \frac1Z \sum_{i\in N_k(x)}\frac1{d(x,x_i)}I(y_i=c)$ (closer points influence the prediction more strongly; weight is inversely proportional to the distance.)
    • Z=\sum_{i\in N_k(x)}\frac1{d(x,x_i)}$Z=\sum_{i\in N_k(x)}\frac1{d(x,x_i)}$: normalization constant
    • d(x,x_i)$d(x,x_i)$: distance measure
  • k-NN regression: \hat y= \frac1Z\sum_{i\in N_k(x)}\frac1{d(x,x_i)}y_i$\hat y= \frac1Z\sum_{i\in N_k(x)}\frac1{d(x,x_i)}y_i$ (predicted value = weighted average of neighbors' values; y_i$y_i$ real number here instead of categorical label)
  • choosing k: generalization (pick hyperparameter k$k$ that performs best on unseen data; targets / labels are known in dataset!)
    1. split dataset into training set, validation set, test set
    2. train model on training set
    3. evaluate different k$k$ values on validation set
    4. choose best k$k$
    5. report performance on test set (good practice)
    
  • measuring classification performance: confusion table
    • precision: fraction of relevant instances among the retrieved instances
    • recall: fraction of relevant instances that were retrieved
      - example: computer program that recognizes dogs (relevant element) in an image; upon processing an image with 10 cats and 12 dogs, the program identifies 8 dogs; of the elements identified as dogs, only 5 are actually dogs (TP), while the other 3 are cats (FP); 7 dogs were missed (FN), and 7 cats were correctly excluded (TN)
      • precision: \frac58$\frac58$ (true positives / selected elements)
      • recall: \frac5{12}$\frac5{12}$ (true positives / relevant elements)
    • often a trade-off between precision and recall; accuracy alone is misleading for imbalanced datasets
    • accuracy: \frac{TP+TN}{TP+TN+FP+FN}$\frac{TP+TN}{TP+TN+FP+FN}$
    • precision: \frac{TP}{TP+FP}$\frac{TP}{TP+FP}$
    • sensitivity / recall: \frac{TP}{TP+FN}$\frac{TP}{TP+FN}$
    • specificity: \frac{TN}{FP+TN}$\frac{TN}{FP+TN}$
    • false negative rate: \frac{FN}{TP+FN}$\frac{FN}{TP+FN}$
    • false positive rate: \frac{FP}{FP+TN}$\frac{FP}{FP+TN}$
    • F1 score: \frac{2\cdot prec \cdot rec}{prec+rec}$\frac{2\cdot prec \cdot rec}{prec+rec}$
      
  • distance measures: k-NN can be used with various distance measures d(u,v)$d(u,v)$...
    • L_2$L_2$ norm (Euclidian distance): \sqrt{\sum_i{(u_i-v_i)²}}$\sqrt{\sum_i{(u_i-v_i)²}}$ (straight-line distance)
    • L_1$L_1$ norm (Manhattan distance): \sum_i |u_i-v_i|$\sum_i |u_i-v_i|$ (distance measured in axis-aligned steps)
      • (!) L_2 \leq L_1$L_2 \leq L_1$
        
    • L_\infty$L_\infty$ norm (Chebyshev distance): \max_i |u_i-v_i|$\max_i |u_i-v_i|$ (like a king in chess; number of moves equals the largest coordinate difference) (how far apart are the points in the worst feature?)
    • cosine similarity: \cos \alpha = \frac{u^Tv}{||u||\,||v||}$\cos \alpha = \frac{u^Tv}{||u||\,||v||}$ (how similar is the direction of two vectors?; magnitude does not matter, only direction)
      • 1: vectors point in same direction
      • 0: orthogonal
      • -1: opposite directions
    • Mahalanobis distance: \sqrt{(u-v)^T\Sigma^{-1}(u-v)}$\sqrt{(u-v)^T\Sigma^{-1}(u-v)}$, where \Sigma$\Sigma$ is positive semidefinite and symmetric (distance that accounts for feature scale and feature correlations; equivalent to L2 distance after normalization)

• feature scaling: distance-based models are sensitive to feature scale (feature with larger magnitude dominates distance)
  • data standardization: x_{i,std} = \frac{x_i-\mu_i}{\sigma_i}$x_{i,std} = \frac{x_i-\mu_i}{\sigma_i}$ (scale each feature to zero mean and unit (1) variance)
  • use Mahalanobis distance, \Sigma=\begin{pmatrix}\sigma_1^2 & 0 & 0\\0 & \dots & 0 \\ 0 & 0 & \sigma_n²\end{pmatrix}$\Sigma=\begin{pmatrix}\sigma_1^2 & 0 & 0\\0 & \dots & 0 \\ 0 & 0 & \sigma_n²\end{pmatrix}$
    
• curse of dimensionality: as dimension d$d$ increases, data becomes sparse, nearest neighbors move far away, and we need exponentially more data (\to$\to$ k-NN works best for low or moderate dimensions)
• compuational complexity
  • training: O(1)$O(1)$ (just storing data)
  • predicition: O(N)$O(N)$ (distance to all training samples)
  • memory: O(N)$O(N)$ (need to keep all data)
    • acceleration: k-d$k-d$ tree, Ball tree, approximate NN search

Decision Trees

• decision tree: supervised learning model used for classification or regression

  • idea: model recursively splits the feature space using simple decision rules; each split corresponds to a test on a feature, the tree partitions the space into regions (leaves)
    • node: feature test (e.g. x_1 \leq 3$x_1 \leq 3$)
    • branch: test outcome (True / False)
    • leaf: final prediction or class distribution (e.g. how many of each class c_i$c_i$ are in the region, as an ordered list)
  • prediction: for a new sample x$x$...
    1. test attributes of x$x$ to find the region R$R$ that contains it and get the class distribution n_R=(n_{c_1,R},...,n_{c_k,R})$n_R=(n_{c_1,R},...,n_{c_k,R})$ for C=\{c_1,...c_k\}$C=\{c_1,...c_k\}$
    2. the probability that x\in R$x\in R$ should be classified belonging to a class c$c$ is p(y=c|R)=\frac{n_{c,R}}{\sum_{c_i \in C}n_{c_i,R}}$p(y=c|R)=\frac{n_{c,R}}{\sum_{c_i \in C}n_{c_i,R}}$ (number of elements of class c$c$ in region R$R$ divided by total number of elements in R$R$)
    3. x$x$ is given the label which is most common in its corresponding region: \hat y=\argmax_c p(y=c|x)=\argmax_c p(y=c|R) = \argmax_c n_{c,R}$\hat y=\argmax_c p(y=c|x)=\argmax_c p(y=c|R) = \argmax_c n_{c,R}$
       

• generalization: find decision tree that performs well on new, unseen data

  1. build tree from training set
  2. predict validation set labels \hat y_i$\hat y_i$ using the tree
  3. evaluate by comparing predictions \hat y_i$\hat y_i$ to true labels y_i$y_i$
  4. pick tree that performs best on validation set
  5. report final performance on test set (only touch the test set once at the end to report final performance!)
     

• building a decision tree (greedy): grow the tree top-down and choose the best split node-by-node using a greedy heuristic on the training data

  • misclassification rate: split the node if it improves the misclassification rate / error i_E$i_E$ at node t$t$
    • i_E(t)=1-\max_cp(y=c|t)$i_E(t)=1-\max_cp(y=c|t)$ (e.g. 40 reds, 60 blues, max prob. 0.6 for blues, i_E(t) = 0.4$i_E(t) = 0.4$)
    • pure node: 0 impurity
    • evenly mixed classes: high impurity
  • improvement for split s$s$ of t$t$ into t_R, t_L$t_R, t_L$: \Delta i(s,t) = i(t) - p_L \cdot i(t_L) - p_R \cdot i(t_R)$\Delta i(s,t) = i(t) - p_L \cdot i(t_L) - p_R \cdot i(t_R)$
    • i(t) = i_E(t)$i(t) = i_E(t)$
    • p_L, p_T$p_L, p_T$: fraction of samples in children (e.g. if, for a total of 100 elements in t$t$, 40 go to the left and 60 to the right, then p_L=\frac{40}{100}$p_L=\frac{40}{100}$ and p_R=\frac{60}{100}$p_R=\frac{60}{100}$)
  • repeated application: distribution of labels becomes more pure
    
    
  • problems: no split performed even though combining the two tests would result in perfect classification, no sensitivity to changes in class probability
    
    
  • criterion i(t)$i(t)$: measures how pure the class distribution at a node t$t$ is
    • maximum if all classes are evenly distributed
    • minimum (usually 0) if the node is pure
    • symmetric
    • let \pi_c = p(y=c|t)$\pi_c = p(y=c|t)$, then...
      • misclassification rate: i_E(t) = 1-\max_c\pi_c$i_E(t) = 1-\max_c\pi_c$
      • entropy: i_H(t) = -\sum_{c_i \in C}\pi_{c_i}\cdot\log_2(\pi_{c_i})$i_H(t) = -\sum_{c_i \in C}\pi_{c_i}\cdot\log_2(\pi_{c_i})$ (note: \lim_{x \to 0+}x\log(x)=0$\lim_{x \to 0+}x\log(x)=0$)
      • Gini index: i_G(t)=\sum_{c_i \in C}\pi_{c_i}(1-\pi_{c_i}) = 1-\sum_{c_i\in C}\pi_{c_i}²$i_G(t)=\sum_{c_i \in C}\pi_{c_i}(1-\pi_{c_i}) = 1-\sum_{c_i\in C}\pi_{c_i}²$
    • Shannon entropy: expected number of bits needed to encode a randomly drawn value from a distribution (under most efficient code)
      
  • Gini index: measures how often a randomly chosen instance would be misclassified if it was randomly classified according to the class distribution (+: no need to compute log vs. Shannon entropy); Entropy and Gini behave similarly (~98% identical choices)
    • i_G(t) = \sum_{c_i \in C} \underbrace{\pi_{c_i}}_{\substack{\text{probability of} \\ \text{picking element}}} \cdot \underbrace{(1 - \pi_{c_i})}_{\substack{\text{probability is} \\ \text{misclassified}}}$i_G(t) = \sum_{c_i \in C} \underbrace{\pi_{c_i}}_{\substack{\text{probability of} \\ \text{picking element}}} \cdot \underbrace{(1 - \pi_{c_i})}_{\substack{\text{probability is} \\ \text{misclassified}}}$

• overfitting: typically occurs when we try to model the training data perfectly \to$\to$ poor generalization

  • signs: low training error (possibly 0), validation error comparably high (validation performance tells us how well our model generalizes, not the training performance!)
    
    
  • double descent phenomenon: with increasing model size, data size, or training time, performance first improves, then gets worse, and then improves again

• K$K$-fold cross validation: alternative to a fixed validation set (typical: 10-fold)

  1. split data into K$K$ folds
  2. train on K-1$K-1$ folds
  3. validate on remaining fold
  4. repeat K$K$ times
  5. average results
  • extreme case: leave-one-out-cross validation (LOOCV), train on all but one sample (N$N$ samples \to$\to$ same as N$N$-fold cross-validation) (useful if we don't have a lot of data and we want to get as much training as possible, but we need to train our model N$N$ times)
    

• stopping criterion: pure branch distribution, maximum depth reached, number of samples in each branch below a certain threshold, benefit of splitting below a certain threshold, accuracy on validation set...

  • post-pruning a maximal tree: pruning T$T$ w.r.t. t$t$ means deleting all descendant nodes of t$t$ (but not t$t$ itself), denoting the pruned tree by T \backslash T_t$T \backslash T_t$
    1. use validation set to get an error estimate err_{D_V}(T)$err_{D_V}(T)$
    2. for each node t$t$ calculate err_{D_V}(T \backslash T_t)$err_{D_V}(T \backslash T_t)$
    3. prune tree at node that yields highest error reduction
    4. repeat until for all nodes t$t$: err_{D_V}(T)$err_{D_V}(T)$ <$<$ err_{D_V}(T \backslash T_t)$err_{D_V}(T \backslash T_t)$
       

• ensembles: aggregate the predictions of many (diverse) classifiers to improve the performance; reduces the variance of the model by averaging

  • bagging (bootstrap aggregating): create new datasets by sampling training set, train separate classifiers on each dataset, combine predictions (e.g. average, majority vote)
  • boosting: incrementally train (weak) classifiers that correct previous mistakes; focus (give higher weight) on hard (misclassified) examples
  • stacking: train a meta-classifier with the base classifiers' predictions as features

Probabilistic Inference

• example: coin flip (not known if fair or not!) sequence D=HTHHTHHHTH$D=HTHHTHHHTH$ (|H|=7, |T|=3$|H|=7, |T|=3$)
  • assume: iid (independent, identically distributed), \theta$\theta$ = probability of tails, F_i \sim Ber(\theta)$F_i \sim Ber(\theta)$
    • independent: p(HTHHTHHHTH|\theta)=\prod_{i=1}^{10}p(F_i=f_i\mid \theta) = \theta^{|T|}(1-\theta)^{|H|}= P(D\mid \theta) =: f(\theta)$p(HTHHTHHHTH|\theta)=\prod_{i=1}^{10}p(F_i=f_i\mid \theta) = \theta^{|T|}(1-\theta)^{|H|}= P(D\mid \theta) =: f(\theta)$
    • identically distributed: p_i(F_i=f_i \mid \theta_i) = p(F_i=f_i\mid \theta)$p_i(F_i=f_i \mid \theta_i) = p(F_i=f_i\mid \theta)$
• maximum likelihood estimation (MLE): choose \theta$\theta$ that maximizes the probability of the observed data
  • goal: \theta_{MLE}= \argmax_{\theta \in [0,1]}f(\theta) = \argmax_{\theta \in [0,1]}\log f(\theta)$\theta_{MLE}= \argmax_{\theta \in [0,1]}f(\theta) = \argmax_{\theta \in [0,1]}\log f(\theta)$ (example: maximize \theta³(1-\theta)⁷$\theta³(1-\theta)⁷$)
    0. take \log$\log$ of f(\theta)$f(\theta)$
    1. take derivative, set to 0, solve for \theta$\theta$
    2. check critical points using second derivative
  • coin flip MLE: \theta_{MLE} = \frac{|T|}{|T|+|H|}$\theta_{MLE} = \frac{|T|}{|T|+|H|}$
  • problem: MLE only represents empirical frequency and ignores prior knowledge (prior beliefs, e.g. coins don't usually land on heads all the time assuming a sequence HHH...$HHH...$); performs poorly if little data is available
• Bayesian inference: treat θ$θ$ as a random variable
  • prior: p(\theta)$p(\theta)$ (our beliefs before we observe any data)
    • must not depend on the data
    • p(\theta) \geq 0$p(\theta) \geq 0$ for all \theta$\theta$
    • \int p(\theta)d\theta = 1$\int p(\theta)d\theta = 1$
  • likelihood: p(D|\theta)$p(D|\theta)$
  • posterior: p(\theta\mid D)=\frac{p(D \mid \theta)p(\theta)}{p(D)}$p(\theta\mid D)=\frac{p(D \mid \theta)p(\theta)}{p(D)}$ (updated beliefs in the value of θ$θ$ after observing data)
    • posterior ∝$∝$ likelihood ·$·$ prior
      • p(\theta\mid D) ∝ p(D\mid\theta)\cdot p(\theta)$p(\theta\mid D) ∝ p(D\mid\theta)\cdot p(\theta)$
    • if p(\theta)=0$p(\theta)=0$, then p(\theta\mid D) = 0$p(\theta\mid D) = 0$ always for that particular \theta$\theta$, regardless of likelihood / data
  • evidence: p(D)$p(D)$ (normalizing constant that ensures that the posterior distribution integrates to 1)
    • p(D)=\int p(D,\theta)d\theta = \int p(D\mid\theta)p(\theta)d\theta$p(D)=\int p(D,\theta)d\theta = \int p(D\mid\theta)p(\theta)d\theta$
• maximum a posteriori estimation (MAP): maximize the posterior probability
  • goal: \theta_{MAP}=\argmax_\theta p(\theta\mid D) = \argmax_\theta p(D\mid \theta)p(\theta)$\theta_{MAP}=\argmax_\theta p(\theta\mid D) = \argmax_\theta p(D\mid \theta)p(\theta)$ (log trick also applies here) (ignoring normalization constant independent of \theta$\theta$)
    • p(D\mid \theta)$p(D\mid \theta)$ known beforehand (\theta^{|T|}(1-\theta)^{|H|}$\theta^{|T|}(1-\theta)^{|H|}$)
    • p(\theta)$p(\theta)$ chosen as Beta distribution: p(\theta)=Beta(\theta\mid a,b) = \frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}\theta^{a-1}(1-\theta)^{b-1}$p(\theta)=Beta(\theta\mid a,b) = \frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}\theta^{a-1}(1-\theta)^{b-1}$, \;\;\theta\in[0,1]$\;\;\theta\in[0,1]$
      • a,b$a,b$: distribution parameters (a>0,b>0$a>0,b>0$) (intuition: a = prior pseudo-count of tails, b = prior pseudo-count of heads)
      • \Gamma(n)=(n-1)!$\Gamma(n)=(n-1)!$: gamma function (n\in\N$n\in\N$)
    • so, p(\theta\mid D) ∝ \theta^{|T|+a-1}(1-\theta)^{|H|+b-1}$p(\theta\mid D) ∝ \theta^{|T|+a-1}(1-\theta)^{|H|+b-1}$ (unnormalized!)
      • \theta_{MAP}=\argmax_\theta \theta^{|T|+a-1}(1-\theta)^{|H|+b-1} = \argmax_\theta (|T|+a-1)\log\theta+(|H|+b-1)\log(1-\theta) = \frac{|T|+a-1}{|H|+|T|+a+b-2}$\theta_{MAP}=\argmax_\theta \theta^{|T|+a-1}(1-\theta)^{|H|+b-1} = \argmax_\theta (|T|+a-1)\log\theta+(|H|+b-1)\log(1-\theta) = \frac{|T|+a-1}{|H|+|T|+a+b-2}$ (equals MLE if a=b=1$a=b=1$)
  • coin flip, normalized posterior (fully Baesian): p(\theta\mid D)=Beta(\theta\mid a+ |T|, b + |H|)$p(\theta\mid D)=Beta(\theta\mid a+ |T|, b + |H|)$
    • \alpha = |T|+a, \beta=|H|+b$\alpha = |T|+a, \beta=|H|+b$, obtained via pattern matching with Beta distribution formula
    • +: it's a full distribution, not just a point estimate, so we can answer questions e.g. regarding expected values, variances, credible intervals...
  • conjugate prior: prior and posterior belong to the same distribution family (here: Beta distribution is a conjugate prior for the Bernoulli likelihood)
• predicting the next flip: three methods
  • MLE: P(T)=\theta_{MLE}=\frac{|T|}{|T|+|H|}$P(T)=\theta_{MLE}=\frac{|T|}{|T|+|H|}$
  • MAP: P(T)=\frac{|T|+a-1}{|H|+|T|+a+b-2}$P(T)=\frac{|T|+a-1}{|H|+|T|+a+b-2}$
  • Fully Bayesian: P(T\mid D)= \frac{|T|+a}{|T|+|H|+a+b}$P(T\mid D)= \frac{|T|+a}{|T|+|H|+a+b}$

Summary

Linear Regression

Regression Problem

• given: observations and targets...
  • observations: \mathbf{X}=\{\mathbf{x}_1,...,\mathbf{x}_N\}, \mathbf{x}_i \in \R^D$\mathbf{X}=\{\mathbf{x}_1,...,\mathbf{x}_N\}, \mathbf{x}_i \in \R^D$ (commonly represented as data matrix \mathbf{X} \in \R^{N \times D}$\mathbf{X} \in \R^{N \times D}$ where each row represents 1 sample, i.e. \mathbf{x}_i$\mathbf{x}_i$)
  • targets: \mathbf{y} = \{y_1,...y_N\}, y_i \in \R$\mathbf{y} = \{y_1,...y_N\}, y_i \in \R$
• find: mapping f(\cdot)$f(\cdot)$ from inputs to targets
  • y_i \approx f(\mathbf{x}_i)$y_i \approx f(\mathbf{x}_i)$
• linear model (bias absorbed): f_\mathbf{w}(\mathbf{x}) = \mathbf{w}^T\mathbf{x}$f_\mathbf{w}(\mathbf{x}) = \mathbf{w}^T\mathbf{x}$
  • \mathbf{w}=(w_0,w_1,...,w_D)^T$\mathbf{w}=(w_0,w_1,...,w_D)^T$
  • \mathbf{x}=(1,x_1,...,x_D)^T$\mathbf{x}=(1,x_1,...,x_D)^T$
• loss function: measures error between our model (parameterized by \mathbf{w}$\mathbf{w}$) and observed data \mathcal{D}=\{(\mathbf{x}_i,y_i)\}_{i=1}^N$\mathcal{D}=\{(\mathbf{x}_i,y_i)\}_{i=1}^N$
  • least squares: E_{LS}(\mathbf{w})=\frac12\sum_{i=1}^N(\mathbf{w}^T\mathbf{x}_i-y_i)²$E_{LS}(\mathbf{w})=\frac12\sum_{i=1}^N(\mathbf{w}^T\mathbf{x}_i-y_i)²$
    
  • objective: find optimal weight vector \mathbf{w}^*$\mathbf{w}^*$ that minimizes the error
    • \mathbf{w}^*=\argmin_{\mathbf{w}}E_{LS}(\mathbf{w})=\argmin_{\mathbf{w}} \frac12\sum_{i=1}^N(\mathbf{x}_i^T\mathbf{w}-y_i)²=\argmin_{\mathbf{w}}\frac12(\mathbf{Xw-y})^T(\mathbf{Xw-y})$\mathbf{w}^*=\argmin_{\mathbf{w}}E_{LS}(\mathbf{w})=\argmin_{\mathbf{w}} \frac12\sum_{i=1}^N(\mathbf{x}_i^T\mathbf{w}-y_i)²=\argmin_{\mathbf{w}}\frac12(\mathbf{Xw-y})^T(\mathbf{Xw-y})$
  • solution: to find the minimum of loss E(\mathbf{w})$E(\mathbf{w})$, compute the gradient \nabla_{\mathbf{w}}E(\mathbf{w})$\nabla_{\mathbf{w}}E(\mathbf{w})$, set it to 0 and solve for \mathbf{w}$\mathbf{w}$
    • \nabla_{\mathbf{w}}E_{LS}(\mathbf{w})=\mathbf{X}^T\mathbf{Xw}-\mathbf{X}^T\mathbf{y}$\nabla_{\mathbf{w}}E_{LS}(\mathbf{w})=\mathbf{X}^T\mathbf{Xw}-\mathbf{X}^T\mathbf{y}$
    • normal equation of LS: \mathbf{w}^*=(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}=\mathbf{X}^\dagger\mathbf{y}$\mathbf{w}^*=(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T\mathbf{y}=\mathbf{X}^\dagger\mathbf{y}$
• nonlinear dependencies (linear in \mathbf{w}$\mathbf{w}$, nonlinear in x$x$): polynomials
  • for 1-dimensional x$x$: f_{\mathbf{w}}(x)=w_0+\sum_{j=1}^Mw_jx^j=w_0+\sum_{j=1}^Mw_j\phi_j(x)=\mathbf{w}^T\mathbf{\phi}(x)$f_{\mathbf{w}}(x)=w_0+\sum_{j=1}^Mw_jx^j=w_0+\sum_{j=1}^Mw_j\phi_j(x)=\mathbf{w}^T\mathbf{\phi}(x)$
    • \phi_0=1$\phi_0=1$
  • for d$d$-dimensional \mathbf{x}$\mathbf{x}$: \phi_j:\R^d\to \R$\phi_j:\R^d\to \R$
    • f_{\mathbf{w}}(\mathbf{x})=w_0+\sum_{j=1}^Mw_j\phi_j(\mathbf{x})=\mathbf{w}^T\mathbf{\phi}(\mathbf{x})$f_{\mathbf{w}}(\mathbf{x})=w_0+\sum_{j=1}^Mw_j\phi_j(\mathbf{x})=\mathbf{w}^T\mathbf{\phi}(\mathbf{x})$
      • design matrix of \mathbf{\phi}$\mathbf{\phi}$: \mathbf{\Phi} = \begin{pmatrix} \phi_0(\mathbf{x}_1) & \phi_1(\mathbf{x}_1) & \dots & \phi_M(\mathbf{x}_1) \\ \phi_0(\mathbf{x}_2) & \phi_1(\mathbf{x}_2) & & \vdots \\ \vdots & \vdots & \ddots & \\ \phi_0(\mathbf{x}_N) & \phi_1(\mathbf{x}_N) & \dots & \phi_M(\mathbf{x}_N) \end{pmatrix} \in \mathbb{R}^{N \times (M+1)}$\mathbf{\Phi} = \begin{pmatrix} \phi_0(\mathbf{x}_1) & \phi_1(\mathbf{x}_1) & \dots & \phi_M(\mathbf{x}_1) \\ \phi_0(\mathbf{x}_2) & \phi_1(\mathbf{x}_2) & & \vdots \\ \vdots & \vdots & \ddots & \\ \phi_0(\mathbf{x}_N) & \phi_1(\mathbf{x}_N) & \dots & \phi_M(\mathbf{x}_N) \end{pmatrix} \in \mathbb{R}^{N \times (M+1)}$
      • E_{LS}(\mathbf{w})=\frac12\sum_{i=1}^N(\mathbf{w}^T\mathbf{\phi}(\mathbf{x}_i)-y_i)²=\frac12(\mathbf{\Phi w-y})^T(\mathbf{\Phi w-y})$E_{LS}(\mathbf{w})=\frac12\sum_{i=1}^N(\mathbf{w}^T\mathbf{\phi}(\mathbf{x}_i)-y_i)²=\frac12(\mathbf{\Phi w-y})^T(\mathbf{\Phi w-y})$
      • \mathbf{w}^* = (\mathbf{\Phi}^T\mathbf{\Phi})^{-1}\mathbf{\Phi y} = \mathbf{\Phi}^\dagger\mathbf{y}$\mathbf{w}^* = (\mathbf{\Phi}^T\mathbf{\Phi})^{-1}\mathbf{\Phi y} = \mathbf{\Phi}^\dagger\mathbf{y}$
  • choosing the degree M$M$ of the polynomial: use train-validation split; high degree \to$\to$ overfitting; low degree \to$\to$ underfitting
  • regularization (controlling overfitting): least-squares loss with L2 regularization (ridge regression)
    • E_{ridge}(\mathbf{w})=\frac12\sum_{i=1}^N[\mathbf{w}^T\mathbf{\phi}(\mathbf{x}_i)-y_i]²+\frac\lambda2||\mathbf{w}||_2²$E_{ridge}(\mathbf{w})=\frac12\sum_{i=1}^N[\mathbf{w}^T\mathbf{\phi}(\mathbf{x}_i)-y_i]²+\frac\lambda2||\mathbf{w}||_2²$
    • ||\mathbf{w}||_2²=\mathbf{w}^T\mathbf{w}=w_0²+w_1²+...+w_M²$||\mathbf{w}||_2²=\mathbf{w}^T\mathbf{w}=w_0²+w_1²+...+w_M²$ (squared L2 norm of \mathbf{w}$\mathbf{w}$)
    • \lambda$\lambda$: regularization strength (larger \lambda \to$\lambda \to$ smaller weights \mathbf{w}$\mathbf{w}$)
      
• bias: expected error due to model mismatch
  • high bias: model is too rigid to fit underlying data distribution (model misspecified or \lambda$\lambda$ too high)
    
• variance: variation due to randomness in training data
  • high variance: model is too flexible and captures noise in data (overfitting; model has high capacity, i.e. memorizes training data, or \lambda$\lambda$ too low)
    

Typical Basis Functions

Probabilistic Linear Regression

• y_i = f_{\mathbf{w}}(\mathbf{x}_i)+\epsilon_i$y_i = f_{\mathbf{w}}(\mathbf{x}_i)+\epsilon_i$
  • \epsilon_i \sim \mathcal{N}(0,\beta^{-1}) \implies y_i \sim \mathcal{N}(f_{\mathbf{w}}(\mathbf{x}_i), \beta^{-1})$\epsilon_i \sim \mathcal{N}(0,\beta^{-1}) \implies y_i \sim \mathcal{N}(f_{\mathbf{w}}(\mathbf{x}_i), \beta^{-1})$
• likelihood of a single sample: p(y_i\mid f_{\mathbf{w}}(\mathbf{x}_i), \beta) = \mathcal N (y_i\mid f_{\mathbf{w}}(\mathbf{x}_i), \beta^{-1})$p(y_i\mid f_{\mathbf{w}}(\mathbf{x}_i), \beta) = \mathcal N (y_i\mid f_{\mathbf{w}}(\mathbf{x}_i), \beta^{-1})$
• likelihood of entire dataset (assuming samples are drawn independently): p(\mathbf{y\mid X,w},\beta)=\prod_{i=1}^Np(y_i\mid f_{\mathbf{w}}(\mathbf{x}_i), \beta)$p(\mathbf{y\mid X,w},\beta)=\prod_{i=1}^Np(y_i\mid f_{\mathbf{w}}(\mathbf{x}_i), \beta)$
• maximum likelihood error function (to minimize): E_{ML}(\mathbf{w},\beta)=-\ln p(\mathbf{y\mid X,w},\beta) = \frac{\beta}{2} \sum_{i=1}^{N} (\mathbf{w}^T \mathbf{\phi}(\mathbf{x}_i) - y_i)^2 - \frac{N}{2} \ln \beta + \frac{N}{2} \ln 2\pi$E_{ML}(\mathbf{w},\beta)=-\ln p(\mathbf{y\mid X,w},\beta) = \frac{\beta}{2} \sum_{i=1}^{N} (\mathbf{w}^T \mathbf{\phi}(\mathbf{x}_i) - y_i)^2 - \frac{N}{2} \ln \beta + \frac{N}{2} \ln 2\pi$
  • maximizing likelihood is equivalent to minimizing least squares error function: \mathbf{w}_{ML}=\argmin_{\mathbf{w}}E_{LS}(\mathbf{w})=(\mathbf{\Phi}^T\mathbf{\Phi})^{-1}\mathbf{\Phi y} = \mathbf{\Phi}^\dagger\mathbf{y}$\mathbf{w}_{ML}=\argmin_{\mathbf{w}}E_{LS}(\mathbf{w})=(\mathbf{\Phi}^T\mathbf{\Phi})^{-1}\mathbf{\Phi y} = \mathbf{\Phi}^\dagger\mathbf{y}$
  • \frac{1}{\beta_{\text{ML}}} = \frac{1}{N} \sum_{i=1}^{N} (\mathbf{w}_{\text{ML}}^T \mathbf{\phi(x}_i) - y_i)^2$\frac{1}{\beta_{\text{ML}}} = \frac{1}{N} \sum_{i=1}^{N} (\mathbf{w}_{\text{ML}}^T \mathbf{\phi(x}_i) - y_i)^2$
• posterior distribution (avoid overfitting): p(\boldsymbol{w} \mid \boldsymbol{X}, \boldsymbol{y}, \beta, \cdot) = \frac{\overbrace{p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{w}, \beta)}^{\text{likelihood}} \cdot \overbrace{p(\boldsymbol{w} \mid \cdot)}^{\text{prior}}}{\underbrace{p(\boldsymbol{y} \mid \boldsymbol{X}, \beta, \cdot)}_{\text{normalizing constant}}} \propto p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{w}, \beta) \cdot p(\boldsymbol{w} \mid \cdot)$p(\boldsymbol{w} \mid \boldsymbol{X}, \boldsymbol{y}, \beta, \cdot) = \frac{\overbrace{p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{w}, \beta)}^{\text{likelihood}} \cdot \overbrace{p(\boldsymbol{w} \mid \cdot)}^{\text{prior}}}{\underbrace{p(\boldsymbol{y} \mid \boldsymbol{X}, \beta, \cdot)}_{\text{normalizing constant}}} \propto p(\boldsymbol{y} \mid \boldsymbol{X}, \boldsymbol{w}, \beta) \cdot p(\boldsymbol{w} \mid \cdot)$
  
• prior for \mathbf{w}$\mathbf{w}$: \text{p}(\boldsymbol{w} \mid \alpha) = \mathcal{N}(\boldsymbol{w} \mid \mathbf{0}, \alpha^{-1}\mathbf{I}) = \left( \frac{\alpha}{2\pi} \right)^{\frac{M}{2}} \exp \left( -\frac{\alpha}{2} \boldsymbol{w}^T \boldsymbol{w} \right)$\text{p}(\boldsymbol{w} \mid \alpha) = \mathcal{N}(\boldsymbol{w} \mid \mathbf{0}, \alpha^{-1}\mathbf{I}) = \left( \frac{\alpha}{2\pi} \right)^{\frac{M}{2}} \exp \left( -\frac{\alpha}{2} \boldsymbol{w}^T \boldsymbol{w} \right)$
  • \alpha$\alpha$: precision of distribution
  • M$M$: number of elements in vector \mathbf{w}$\mathbf{w}$
• MAP estimation with Gaussian prior is equivalent to ridge regression: E_{MAP}(\mathbf{w})\propto E_{ridge}(\mathbf{w})+\text{const}$E_{MAP}(\mathbf{w})\propto E_{ridge}(\mathbf{w})+\text{const}$ where \lambda=\frac\alpha\beta$\lambda=\frac\alpha\beta$
• full Bayesian: p(\mathbf{w}\mid\mathcal{D})=\mathcal{N}(\mathbf{w}\mid\mathbf{\mu,\Sigma})$p(\mathbf{w}\mid\mathcal{D})=\mathcal{N}(\mathbf{w}\mid\mathbf{\mu,\Sigma})$
  • \mathbf{\mu}=\beta\mathbf{\Sigma\Phi}^T\mathbf{y}$\mathbf{\mu}=\beta\mathbf{\Sigma\Phi}^T\mathbf{y}$
  • \mathbf{\Sigma}^{-1}=\alpha\mathbf{I}+\beta\mathbf{\Phi}^T\mathbf{\Phi}$\mathbf{\Sigma}^{-1}=\alpha\mathbf{I}+\beta\mathbf{\Phi}^T\mathbf{\Phi}$
  • observations
    • posterior is Gaussian, so its mode is the mean, and \mathbf{w}_{MAP}=\mathbf{\mu}$\mathbf{w}_{MAP}=\mathbf{\mu}$
    • in the limit of an infinitely broad prior α → 0$α → 0$, \mathbf{w}_{MAP}\to\mathbf{w}_{ML}$\mathbf{w}_{MAP}\to\mathbf{w}_{ML}$
    • N=0$N=0$ (no data points) \to$\to$ posterior = prior
• predictive distribution: make prediction \hat y_{new}$\hat y_{new}$ for new data \mathbf{x}_{new}$\mathbf{x}_{new}$
  • MLE (\mathbf{w}_{ML}, \beta_{ML}$\mathbf{w}_{ML}, \beta_{ML}$): \text{p}(\hat{y}_{new} \mid \boldsymbol{x}_{new}, \boldsymbol{w}_{\text{ML}}, \beta_{\text{ML}}) = \mathcal{N} (\hat{y}_{new} \mid \boldsymbol{w}_{\text{ML}}^T \phi(\boldsymbol{x}_{new}), \beta_{\text{ML}}^{-1})$\text{p}(\hat{y}_{new} \mid \boldsymbol{x}_{new}, \boldsymbol{w}_{\text{ML}}, \beta_{\text{ML}}) = \mathcal{N} (\hat{y}_{new} \mid \boldsymbol{w}_{\text{ML}}^T \phi(\boldsymbol{x}_{new}), \beta_{\text{ML}}^{-1})$
  • MAP (\mathbf{w}_{MAP}$\mathbf{w}_{MAP}$): \text{p}(\hat{y}_{new} \mid \boldsymbol{x}_{new}, \boldsymbol{w}_{\text{MAP}}, \beta) = \mathcal{N} (\hat{y}_{new} \mid \boldsymbol{w}_{\text{MAP}}^T \phi(\boldsymbol{x}_{new}), \beta^{-1})$\text{p}(\hat{y}_{new} \mid \boldsymbol{x}_{new}, \boldsymbol{w}_{\text{MAP}}, \beta) = \mathcal{N} (\hat{y}_{new} \mid \boldsymbol{w}_{\text{MAP}}^T \phi(\boldsymbol{x}_{new}), \beta^{-1})$
• posterior predictive distribution: p(\hat y_{new}\mid\mathbf{x}_{new},\mathcal{D})=\mathcal{N} \left( \hat{y}_{new} \mid \boldsymbol{\mu}^T \phi(\boldsymbol{x}_{new}), \beta^{-1} + \phi(\boldsymbol{x}_{new})^T \boldsymbol{\Sigma} \phi(\boldsymbol{x}_{new}) \right)$p(\hat y_{new}\mid\mathbf{x}_{new},\mathcal{D})=\mathcal{N} \left( \hat{y}_{new} \mid \boldsymbol{\mu}^T \phi(\boldsymbol{x}_{new}), \beta^{-1} + \phi(\boldsymbol{x}_{new})^T \boldsymbol{\Sigma} \phi(\boldsymbol{x}_{new}) \right)$

Linear Classification

Introduction to Linear Classification

• regression: output y$y$ is continuous, i.e. y\in\R$y\in\R$ (e.g. predict the price of a house given its area)
• classification: output y$y$ belongs to one of C$C$ predetermined classes, i.e. y\in\{1,...,C\}$y\in\{1,...,C\}$ (e.g. determine if a picture shows a cat or a dog)
  • given: observations and set of possible classes; labels
    • observations: \mathbf{X}=\{\mathbf{x}_1,...,\mathbf{x}_N\}, \mathbf{x}_i \in \R^D$\mathbf{X}=\{\mathbf{x}_1,...,\mathbf{x}_N\}, \mathbf{x}_i \in \R^D$ (or represented like before as a data matrix \mathbf{X}\in\R^{N\times D}$\mathbf{X}\in\R^{N\times D}$)
    • classes: \mathcal{C}=\{1,...,C\}$\mathcal{C}=\{1,...,C\}$
    • labels: \mathbf{y}=\{y_1,...,y_N\}, y_i\in\mathcal{C}$\mathbf{y}=\{y_1,...,y_N\}, y_i\in\mathcal{C}$
  • find: function f:\R^D\to\mathcal{C}$f:\R^D\to\mathcal{C}$ that maps observations \mathbf{x}_i$\mathbf{x}_i$ to class labels y_i$y_i$
    • y_i=f(\mathbf{x}_i)$y_i=f(\mathbf{x}_i)$ for i\in\{1,...,N\}$i\in\{1,...,N\}$
• zero-one loss: denotes the number of misspecified samples; for measuring the quality of a prediction \mathbf{\hat y}:=f(\mathbf{X})$\mathbf{\hat y}:=f(\mathbf{X})$
  • l_{01}(\mathbf{y,\hat y})=\sum_{i=1}^N\mathrm{I}(\hat y_i \neq y_i)$l_{01}(\mathbf{y,\hat y})=\sum_{i=1}^N\mathrm{I}(\hat y_i \neq y_i)$
• hyperplane: used for separating points from two classes for a 2-class problem (i.e. \mathcal{C}=\{0,1\}$\mathcal{C}=\{0,1\}$)
  • defined by a normal vector \mathbf{w}$\mathbf{w}$ and an offset w_0$w_0$
  • \mathbf{w}^T\mathbf{x}+w_0 \begin{cases}=0&\text{if }\mathbf{x}\text{ is on the plane}\\>0&\text{if }\mathbf{x}\text{ is on the normal's side}\\<0&\text{else}\end{cases}$\mathbf{w}^T\mathbf{x}+w_0 \begin{cases}=0&\text{if }\mathbf{x}\text{ is on the plane}\\>0&\text{if }\mathbf{x}\text{ is on the normal's side}\\<0&\text{else}\end{cases}$
  • \mathcal{D}=\{(\mathbf{x}_i,y_i)\}$\mathcal{D}=\{(\mathbf{x}_i,y_i)\}$ is linearly separable if there exists a hyperplane for which all \mathbf{x}_i$\mathbf{x}_i$ with y_i=0$y_i=0$ are on one side and all \mathbf{x}_i$\mathbf{x}_i$ with y_i=1$y_i=1$ are on the other side
    
• perceptron: uses a step function to make hard predictions based on whether a linear combination of inputs is positive or negative
  • \hat y=f(\mathbf{w}^T\mathbf{x}+w_0)$\hat y=f(\mathbf{w}^T\mathbf{x}+w_0)$, where f(t)=\begin{cases}1&\text{if t > 0}\\0 & \text{else}\end{cases}$f(t)=\begin{cases}1&\text{if t > 0}\\0 & \text{else}\end{cases}$
    
  • learning rule (finite number of steps to converge if a valid discrimination exists; but we cannot determine the number of steps it will take beforehand)
    1. initialize parameters to any value, e.g. zero (\mathbf{w}, w_0 \leftarrow 0$\mathbf{w}, w_0 \leftarrow 0$)
    2. for each misclassified sample \mathbf{x}_i$\mathbf{x}_i$ in the training set, update \mathbf{w} \leftarrow \begin{cases}\mathbf{w+x}_i&\text{if }y_i = 1\\\mathbf{w-x}_i&\text{if }y_i = 0\end{cases}$\mathbf{w} \leftarrow \begin{cases}\mathbf{w+x}_i&\text{if }y_i = 1\\\mathbf{w-x}_i&\text{if }y_i = 0\end{cases}$, w_0 \leftarrow \begin{cases}w_0+1&\text{if }y_i=1\\w_0-1&\text{if }y_i=0\end{cases}$w_0 \leftarrow \begin{cases}w_0+1&\text{if }y_i=1\\w_0-1&\text{if }y_i=0\end{cases}$ until all samples are classified correctly
• multiple classes: one-versus-rest classifier, one-versus-one classifier, multi-class discriminant
  • one-vs-rest: each hyperplane H_i$H_i$ decides \mathcal{C}_i \leftrightarrow \text{not } \mathcal{C}_i$\mathcal{C}_i \leftrightarrow \text{not } \mathcal{C}_i$
    
  • one-vs-one: hyperplane H_{ij}$H_{ij}$ makes a decision for each pair of classes \mathcal C_i \leftrightarrow \mathcal C_j$\mathcal C_i \leftrightarrow \mathcal C_j$, use majority vote to classify
    
  • multiclass discriminant: define C$C$ linear functions of the form f_c(\mathbf x) = \mathbf w_c^T \mathbf x + w_{0c}$f_c(\mathbf x) = \mathbf w_c^T \mathbf x + w_{0c}$ with the decision rule \hat y = \argmax_{c \in \mathcal C} f_c(\mathbf x)$\hat y = \argmax_{c \in \mathcal C} f_c(\mathbf x)$
    • in other words: assign \mathbf x$\mathbf x$ to the class c$c$ which produces the highest f_c(\mathbf x)$f_c(\mathbf x)$, dividing the domain into convex decision regions \mathcal R_i$\mathcal R_i$
      
• classes not linearly separable? apply nonlinear transformation \phi:\R^D\to\R^M$\phi:\R^D\to\R^M$ that maps samples to a space where they are linearly separable
  • example: \phi(\mathbf x)=(\theta,r)=(angle(\mathbf x), ||\mathbf x||_2)$\phi(\mathbf x)=(\theta,r)=(angle(\mathbf x), ||\mathbf x||_2)$
    
• limitations of hard-decision based classifiers: no measure of uncertainty, can't handle noisy data, poor generalization, difficult to optimize
  
• probabilistic model: model the distribution of the class label y$y$ given the data \mathbf x$\mathbf x$
  • p(y=c\mid\mathbf x) = \frac{p(\mathbf x\mid y =c) p(y=c)}{p(\mathbf x)}$p(y=c\mid\mathbf x) = \frac{p(\mathbf x\mid y =c) p(y=c)}{p(\mathbf x)}$
  • generative: model the joint distribution p(\mathbf x,y=c)=p(\mathbf x\mid y=c)p(y=c)$p(\mathbf x,y=c)=p(\mathbf x\mid y=c)p(y=c)$
  • discriminative: directly model the distribution p(y=c\mid \mathbf x)$p(y=c\mid \mathbf x)$

Probabilistic Generative Models for Linear Classification

• goal: obtain class posterior using Bayes' theorem; p(y=c\mid \mathbf x)\propto p(\mathbf x\mid y=c)p(y=c)$p(y=c\mid \mathbf x)\propto p(\mathbf x\mid y=c)p(y=c)$
  • p(\mathbf x\mid y=c)$p(\mathbf x\mid y=c)$: class conditional, probability of generating a point \mathbf x$\mathbf x$, given that it belongs to class c$c$
  • p(y=c)$p(y=c)$: class prior, a priori probability of a point belonging to a class c$c$
• applying:
  1. choose parametric model for the class conditional p(\mathbf x\mid y=c, \mathbf \psi)$p(\mathbf x\mid y=c, \mathbf \psi)$ and class prior p(y=c\mid \mathbf \theta)$p(y=c\mid \mathbf \theta)$
  2. learning: estimate parameters \psi,\theta$\psi,\theta$ from data \mathcal D$\mathcal D$ (e.g. using maximum likelihood)
  3. once fitted, perform inference; classify new \mathbf x$\mathbf x$ using Bayes' rule p(y=c\mid\mathbf{x,\hat \psi, \hat \theta})\propto p(\mathbf x\mid y=c, \hat\psi)p(y=c\mid\hat\theta)$p(y=c\mid\mathbf{x,\hat \psi, \hat \theta})\propto p(\mathbf x\mid y=c, \hat\psi)p(y=c\mid\hat\theta)$
  4. generate new data; sample class label y_{new}\sim p(y\mid \hat\theta)$y_{new}\sim p(y\mid \hat\theta)$, feature vec. \mathbf x_{new}\sim p(\mathbf x \mid y=y_{new}, \hat\psi)$\mathbf x_{new}\sim p(\mathbf x \mid y=y_{new}, \hat\psi)$
• choosing class prior p(y=c)$p(y=c)$: y\sim\text{Categorical}(\theta)$y\sim\text{Categorical}(\theta)$
  • \theta\in\R^C$\theta\in\R^C$: probability of each class
    • p(y=c)=\theta_c \;\equiv\;p(y)=\prod_{c=1}^C\theta_c^{I(y=c)}$p(y=c)=\theta_c \;\equiv\;p(y)=\prod_{c=1}^C\theta_c^{I(y=c)}$
    • 0\leq\theta_c\leq1$0\leq\theta_c\leq1$, \sum_{c=1}^C \theta_c=1$\sum_{c=1}^C \theta_c=1$
    • \theta_c^{MLE}=\frac1N\sum_{i=1}^NI(y_i=c)$\theta_c^{MLE}=\frac1N\sum_{i=1}^NI(y_i=c)$
• choosing class conditional p(\mathbf x \mid y =c)$p(\mathbf x \mid y =c)$: use a multivariate normal for each class
  • p(\mathbf x\mid y=c) = \mathcal N(\mathbf x \mid \mathbf{\mu_c,\Sigma})=\frac1{(2\pi)^{D/2}|\Sigma|^{1/2}}\exp\{-\frac12(\mathbf{x-\mu_c})^T\mathbf \Sigma^{-1}(\mathbf{x-\mu_c})\}$p(\mathbf x\mid y=c) = \mathcal N(\mathbf x \mid \mathbf{\mu_c,\Sigma})=\frac1{(2\pi)^{D/2}|\Sigma|^{1/2}}\exp\{-\frac12(\mathbf{x-\mu_c})^T\mathbf \Sigma^{-1}(\mathbf{x-\mu_c})\}$
• linear discriminant analysis (LDA): projects high-dimensional data onto a lower-dimensional space by maximizing the ratio of between-class variance to within-class variance, ensuring maximum separation between classes
  • (!) all classes share the same covariance matrix \mathbf \Sigma$\mathbf \Sigma$
  • 2 classes: p(y=1\mid \mathbf x)=\frac1{1+\exp(-(\mathbf w^T \mathbf x+w_0))}=\sigma(\mathbf w^T \mathbf x+w_0)$p(y=1\mid \mathbf x)=\frac1{1+\exp(-(\mathbf w^T \mathbf x+w_0))}=\sigma(\mathbf w^T \mathbf x+w_0)$
    • equivalently: y\mid\mathbf x\sim \text{Bernoulli}(\sigma(\mathbf w^T \mathbf x+w_0))$y\mid\mathbf x\sim \text{Bernoulli}(\sigma(\mathbf w^T \mathbf x+w_0))$ (i.e. p(y=0\mid\mathbf x) = 1-\sigma(\mathbf w^T \mathbf x+w_0)$p(y=0\mid\mathbf x) = 1-\sigma(\mathbf w^T \mathbf x+w_0)$)
    • \mathbf w = \mathbf \Sigma^{-1}(\mathbf \mu_1 - \mathbf\mu_0)$\mathbf w = \mathbf \Sigma^{-1}(\mathbf \mu_1 - \mathbf\mu_0)$
    • w_0 = -\frac12\mu_1^T\mathbf \Sigma^{-1}\mu_1+\frac12\mu_0^T\mathbf\Sigma^{-1}\mu_0+\log\frac{p(y=1)}{p(y=0)}$w_0 = -\frac12\mu_1^T\mathbf \Sigma^{-1}\mu_1+\frac12\mu_0^T\mathbf\Sigma^{-1}\mu_0+\log\frac{p(y=1)}{p(y=0)}$
      
  • more than 2 classes: p(y=c\mid \mathbf x)=\frac{p(\mathbf x\mid y=c)p(y=c)}{\sum_{c'=1}^Cp(\mathbf x\mid y=c')p(y=c')}=$p(y=c\mid \mathbf x)=\frac{p(\mathbf x\mid y=c)p(y=c)}{\sum_{c'=1}^Cp(\mathbf x\mid y=c')p(y=c')}=$
    • \mathbf w_c=\mathbf \Sigma^{-1}\mathbf \mu_c$\mathbf w_c=\mathbf \Sigma^{-1}\mathbf \mu_c$
    • w_{c0} = -\frac12\mu_c^T\mathbf\Sigma^{-1}\mu_c+\log p(y=c)$w_{c0} = -\frac12\mu_c^T\mathbf\Sigma^{-1}\mu_c+\log p(y=c)$
  • \to$\to$ linear decision boundary
• softmax (generalization of sigmoid to K$K$ dimensions): \sigma(\mathbf x)_i = \frac{\exp(x_i)}{\sum_{k=1}^K\exp(x_k)}$\sigma(\mathbf x)_i = \frac{\exp(x_i)}{\sum_{k=1}^K\exp(x_k)}$
• Naive Bayes: family of "probabilistic classifiers" which assumes that the features are conditionally independent, given the target class
  • (!) different covariance matrix \Sigma_c$\Sigma_c$ for each class c$c$
  • p(x_1,...,x_d\mid y=c)=\prod_{i=1}^dp(x_i\mid y=c)$p(x_1,...,x_d\mid y=c)=\prod_{i=1}^dp(x_i\mid y=c)$
  • continuous data, likelihood assumed normal distributed: p(\mathbf x\mid y=c) = \mathcal N(\mathbf x\mid\mathbf{\mu}_c,\mathbf{\Sigma}_c)$p(\mathbf x\mid y=c) = \mathcal N(\mathbf x\mid\mathbf{\mu}_c,\mathbf{\Sigma}_c)$
  • \to$\to$ quadratic decision boundary
    

Probabilistic Discriminative Models for Linear Classification

• goal: model posterior p(y\mid\mathbf x)$p(y\mid\mathbf x)$ directly
• logistic regression: y\mid\mathbf x\sim \text{Bernoulli}(\sigma(\mathbf w^T \mathbf x+w_0))$y\mid\mathbf x\sim \text{Bernoulli}(\sigma(\mathbf w^T \mathbf x+w_0))$, where \mathbf w, w_0$\mathbf w, w_0$ are free model parameters (i.e. they do not depend on class-conditionals \mu_0,\mu_1,\mathbf \Sigma$\mu_0,\mu_1,\mathbf \Sigma$)
  • \mathbf w^T\mathbf x:=w_0+w_1x_1+...+w_Dx_D$\mathbf w^T\mathbf x:=w_0+w_1x_1+...+w_Dx_D$ (bias absorbed)
  • likelihood: p(\mathbf y\mid \mathbf{w,X})=\prod_{i=1}^{N} \sigma(\boldsymbol{w}^T \boldsymbol{x}_i)^{y_i} (1 - \sigma(\boldsymbol{w}^T \boldsymbol{x}_i))^{1-y_i}$p(\mathbf y\mid \mathbf{w,X})=\prod_{i=1}^{N} \sigma(\boldsymbol{w}^T \boldsymbol{x}_i)^{y_i} (1 - \sigma(\boldsymbol{w}^T \boldsymbol{x}_i))^{1-y_i}$ (assuming iid samples)
  • negative log-likelihood loss / binary cross entropy loss: E(\mathbf w)=-\log p(\mathbf y\mid \mathbf{w,X}) =-\sum_{i=1}^{N} (y_i \log \sigma(\boldsymbol{w}^T \boldsymbol{x}_i) + (1 - y_i) \log(1 - \sigma(\boldsymbol{w}^T \boldsymbol{x}_i)))$E(\mathbf w)=-\log p(\mathbf y\mid \mathbf{w,X}) =-\sum_{i=1}^{N} (y_i \log \sigma(\boldsymbol{w}^T \boldsymbol{x}_i) + (1 - y_i) \log(1 - \sigma(\boldsymbol{w}^T \boldsymbol{x}_i)))$
    • MLE: \mathbf w^* = \argmin_w E(\mathbf w)$\mathbf w^* = \argmin_w E(\mathbf w)$ (no closed form!)
    • with weight regularization: E(\mathbf w) = -\log p(\mathbf y\mid \mathbf{w,X}) + \lambda ||\mathbf w||_q^q$E(\mathbf w) = -\log p(\mathbf y\mid \mathbf{w,X}) + \lambda ||\mathbf w||_q^q$
      • q=2\implies$q=2\implies$ MAP estimation with Gaussian prior on \mathbf w$\mathbf w$
        
• multiclass logistic regression: p(y=c\mid\mathbf x)= \frac{\exp(\mathbf w_c^T\mathbf x)}{\sum_{c'}\exp(\mathbf w_{c'}^T\mathbf x)}$p(y=c\mid\mathbf x)= \frac{\exp(\mathbf w_c^T\mathbf x)}{\sum_{c'}\exp(\mathbf w_{c'}^T\mathbf x)}$
  • cross entropy loss: E(\mathbf w) = -\log p(\mathbf Y \mid \mathbf{w,X}) = -\sum_{i=1}^{N} \sum_{c=1}^{C} y_{ic} \log \frac{\exp(\boldsymbol{w}_{c}^{T} \boldsymbol{x})}{\sum_{c'} \exp(\boldsymbol{w}_{c'}^{T} \boldsymbol{x})}$E(\mathbf w) = -\log p(\mathbf Y \mid \mathbf{w,X}) = -\sum_{i=1}^{N} \sum_{c=1}^{C} y_{ic} \log \frac{\exp(\boldsymbol{w}_{c}^{T} \boldsymbol{x})}{\sum_{c'} \exp(\boldsymbol{w}_{c'}^{T} \boldsymbol{x})}$
    • one-hot encoding: vector of categorical variables \mathbf y \in \mathcal C^N$\mathbf y \in \mathcal C^N$ encoded as binary matrix \mathbf Y \in \{0,1\}^{N\times C}$\mathbf Y \in \{0,1\}^{N\times C}$
      • y_{ic} = \begin{cases}1&\text{if sample i belongs to class c}\\0 & \text{else}\end{cases}$y_{ic} = \begin{cases}1&\text{if sample i belongs to class c}\\0 & \text{else}\end{cases}$

Optimization

• optimization: find solution to minimize a certain function

  • \theta$\theta$: variables / parameters of problem to learn (e.g. \theta = \mathbf w$\theta = \mathbf w$ in logistic regression)
  • \mathcal X$\mathcal X$: domain of \theta$\theta$ (e.g. set of real numbers)
  • f(\theta)$f(\theta)$: objective function (e.g. negative log likelihood)
  • goal: find \theta^* = \argmin_{\theta \in \mathcal X} f(\theta)$\theta^* = \argmin_{\theta \in \mathcal X} f(\theta)$ (global minimum of function f$f$; alternatively, maximum for some other problems)

• convex set: X$X$ convex \iff$\iff$ \forall x,y \in X, \lambda \in [0,1]: \lambda x+(1-\lambda)y \in X$\forall x,y \in X, \lambda \in [0,1]: \lambda x+(1-\lambda)y \in X$

  • in other words: a set X$X$ is convex if the line segment between any two points in X$X$ lies in X$X$
    

• convex function: f(\mathbf x)$f(\mathbf x)$ convex function on the convex set X$X$ \iff$\iff$ \forall \mathbf{x,y} \in X, \lambda \in [0,1]:\lambda f(\mathbf x) + (1-\lambda)f(\mathbf y) \geq f(\lambda \mathbf x + (1-\lambda)\mathbf y)$\forall \mathbf{x,y} \in X, \lambda \in [0,1]:\lambda f(\mathbf x) + (1-\lambda)f(\mathbf y) \geq f(\lambda \mathbf x + (1-\lambda)\mathbf y)$

  • in other words: a real-valued function f$f$ is called convex if the line segment between any two distinct points on the graph of the function lies above or on the graph of the function between the two points
    
  • (!) region above a convex function is convex
  • (!) every local minimum is a global minimum (zero gradient \implies$\implies$ minimum for convex functions)
    • f_0$f_0$ convex, \nabla f_0(\theta^*)=0 \implies \theta$\nabla f_0(\theta^*)=0 \implies \theta$ is a global minimum
  • first order convexity theorem: let f:X\to\R$f:X\to\R$ be a differentiable function, and X$X$ convex; then f$f$ is convex iff \forall \mathbf{x,y}\in X: f(\mathbf y) \geq f(\mathbf x) + (\mathbf y - \mathbf x)^T\nabla f(\mathbf x)$\forall \mathbf{x,y}\in X: f(\mathbf y) \geq f(\mathbf x) + (\mathbf y - \mathbf x)^T\nabla f(\mathbf x)$
  • verifying convexity of a function: proving definition (tedious), exploiting special results, showing that the function can be obtained from convex functions by operations that preserve convexity
    • special results: first order convexity theorem (e.g. a twice differentiable function of one variable is convex on an interval iff its second derivative is non-negative on this interval; more generally, a twice differentiable function of several variables is convex on a convex set if and only if its Hessian matrix is positive semidefinite on the set)
    • through convexity preserving operations: start with simple convex functions, then apply construction rules
      • convex functions
        • f(x)=c$f(x)=c$
        • f(x)=ax+b$f(x)=ax+b$
        • f(x)=x²$f(x)=x²$
        • f(x)=e^x$f(x)=e^x$
        • f(x_1,...,x_n)=\log(\sum_ie^{x_i})$f(x_1,...,x_n)=\log(\sum_ie^{x_i})$
        • f(x)=||x||$f(x)=||x||$
        • f(x)=|x|$f(x)=|x|$
        • f(x)=x^p$f(x)=x^p$ for p\geq 1, x \geq 0$p\geq 1, x \geq 0$ and p \leq 0, x > 0$p \leq 0, x > 0$
        • f(x)=-\log x$f(x)=-\log x$ for x>0$x>0$
      • concave functions
        • f(x)=c$f(x)=c$
        • f(x)=ax+b$f(x)=ax+b$
        • f(x)=-x²$f(x)=-x²$
        • f(x)=x^p$f(x)=x^p$ for 0 < p \leq 1, x \geq 0$0 < p \leq 1, x \geq 0$
        • f(x)=-x\log x$f(x)=-x\log x$ for x>0$x>0$
      • construction rules: let f_1:\R^d\to\R, f_2:\R^d\to\R$f_1:\R^d\to\R, f_2:\R^d\to\R$ be convex functions, and g:\R^d\to\R$g:\R^d\to\R$ be concave, then the following are convex...
        • h(\mathbf x)=f_1(\mathbf x)+f_2(\mathbf x)$h(\mathbf x)=f_1(\mathbf x)+f_2(\mathbf x)$
        • h(\mathbf x)=\max\{f_1(\mathbf x),f_2(\mathbf x)\}$h(\mathbf x)=\max\{f_1(\mathbf x),f_2(\mathbf x)\}$
        • h(\mathbf x)=c\cdot f_1(\mathbf x)$h(\mathbf x)=c\cdot f_1(\mathbf x)$ if c \geq 0$c \geq 0$
        • h(\mathbf x)=c\cdot g(\mathbf x)$h(\mathbf x)=c\cdot g(\mathbf x)$ if c \leq 0$c \leq 0$
        • h(\mathbf x)=f_1(\mathbf{Ax+b})$h(\mathbf x)=f_1(\mathbf{Ax+b})$
        • h(\mathbf x)=m(f_1(\mathbf x))$h(\mathbf x)=m(f_1(\mathbf x))$ if m:\R\to\R$m:\R\to\R$ covex and non-decreasing
  • verifying convexity of sets: prove definition (often easier than for functions), apply intersection rule
    • intersection rule: if A,B$A,B$ are convex sets, then A \cap B$A \cap B$ is a convex set

• first-order optimization techniques: only exploit information of the gradients (i.e. first order derivative)

• gradient descent: take repeated steps in the opposite direction of the gradient (or approximate gradient) of the function at the current point, because this is the direction of steepest descent; stepping in the direction of the gradient will lead to a trajectory that maximizes that function

  • given starting point \theta \in \text{Dom}(f)$\theta \in \text{Dom}(f)$, repeat until stopping criterion satisfied...
    1. \Delta \theta:=-\nabla f(\theta)$\Delta \theta:=-\nabla f(\theta)$
    2. choose t^* = \argmin_{t>0}f(\theta+t\cdot\Delta\theta)$t^* = \argmin_{t>0}f(\theta+t\cdot\Delta\theta)$
    3. update \theta := \theta + t^*\Delta\theta$\theta := \theta + t^*\Delta\theta$
    • convergence: strongly convex ⇒ linear (geometric) convergence in function value; iteration bounds scale logarithmically with target precision
      
  • faster: avoid line search (2), simply pick update \theta_{t+1} \leftarrow \theta_t - \tau \nabla f(\theta_t)$\theta_{t+1} \leftarrow \theta_t - \tau \nabla f(\theta_t)$
    • \tau$\tau$: learning rate (too small \to$\to$ slow convergence, might end up in local minima or saddle points; too high \to$\to$ algorithm might oscillate, so no convergence)
      
    • learning rate adaptation / schedule: let the learning rate be a decreasing function τ_t$τ_t$ of the iteration number t$t$ (first iterations cause large changes in the parameters; later do fine-tuning); convergence guaranteed if \lim_{t\to\infty}\tau_t = 0$\lim_{t\to\infty}\tau_t = 0$
      • example: \tau_{t+1} \leftarrow \alpha \cdot \tau_t$\tau_{t+1} \leftarrow \alpha \cdot \tau_t$ for 0 < \alpha < 1$0 < \alpha < 1$
    • alternatives: incorporate history of previous gradients
      • momentum: \mathbf m_t \to \tau \nabla f(\theta_t) + \gamma \mathbf m_{t-1};\;\;\;\theta_{t+1} \leftarrow \theta_t - \mathbf m_t$\mathbf m_t \to \tau \nabla f(\theta_t) + \gamma \mathbf m_{t-1};\;\;\;\theta_{t+1} \leftarrow \theta_t - \mathbf m_t$ (often \gamma=0.5$\gamma=0.5$, as long as gradients point to the same direction, the search accelerates)

• Newton method: higher order, fast local convergence, fewer passes through data, but O(d²)$O(d²)$ compute and O(d³)$O(d³)$ update

• stochastic gradient descent (SGD): replace full gradient by unbiased mini-batch estimate; update using sampled subset; much cheaper per update, higher variance; typical epoch = one pass through all data; for convex problems SGD converges almost surely

Deep Learning

• logistic regression (posterior, recap): y\mid\mathbf x \sim \text{Bernoulli}(\sigma(\mathbf w^T\mathbf x))$y\mid\mathbf x \sim \text{Bernoulli}(\sigma(\mathbf w^T\mathbf x))$
  • \mathbf w^T\mathbf x := w_0 + w_1x_1 + ... + w_Dx_D$\mathbf w^T\mathbf x := w_0 + w_1x_1 + ... + w_Dx_D$
  • \sigma(a) := \frac{1}{1+\exp(-a)}$\sigma(a) := \frac{1}{1+\exp(-a)}$
• graphically: each node is a scalar input; bottom to top
  1. multiply input with weight on edge: x_jw_j$x_jw_j$
  2. compute weighted sum of incoming edges: a_0=\sum_{j=0}^D x_jw_j$a_0=\sum_{j=0}^D x_jw_j$
  3. apply activation function: p(y=1\mid\mathbf w)=\sigma(a_0)=f(\mathbf x,\mathbf w)$p(y=1\mid\mathbf w)=\sigma(a_0)=f(\mathbf x,\mathbf w)$
• handling non-linearity (basis functions, recap): f(\mathbf x, \mathbf w)=\sigma(w_0+\sum_{j=1}^{M-1}w_j\phi_j(\mathbf x))=\sigma(\mathbf w^T\mathbf\phi(\mathbf x))$f(\mathbf x, \mathbf w)=\sigma(w_0+\sum_{j=1}^{M-1}w_j\phi_j(\mathbf x))=\sigma(\mathbf w^T\mathbf\phi(\mathbf x))$ (linear in \mathbf w$\mathbf w$)
  • \mathbf\phi$\mathbf\phi$: basis function (can be nonlinear), maps samples to new space where data is linearly separable
  • w_0$w_0$: bias (equivalent to defining \phi_0=1$\phi_0=1$)
    
• feed-forward neural network: instead of manually designing basis functions, learn it automatically (i.e. learn all w_{ijk}$w_{ijk}$, where i$i$ is the layer, j$j$ is the input node, and k$k$ is the output node)
  • multi-layered perceptron (MLP): "deep" neural network with more hidden layers
    • example: f(\mathbf{x,W,b})=\sigma_2(\mathbf W_2\sigma_1(\mathbf W_1 \sigma_0(\mathbf W_0 \mathbf x + \mathbf b_0)+ \mathbf b_1) + \mathbf b_2)$f(\mathbf{x,W,b})=\sigma_2(\mathbf W_2\sigma_1(\mathbf W_1 \sigma_0(\mathbf W_0 \mathbf x + \mathbf b_0)+ \mathbf b_1) + \mathbf b_2)$
      • \mathbf W=\{\mathbf W_0,...\}$\mathbf W=\{\mathbf W_0,...\}$: learnable weights
      • \mathbf b=\{\mathbf b_0, ...\}$\mathbf b=\{\mathbf b_0, ...\}$: learnable biases
        
  • activation functions: usually applied element-wise given a multi-dimensional input, notably except for Softmax
    
  • universal approximation theorem: an MLP with a linear output layer and one hidden layer can approximate any continuous function defined over a closed and bounded subset of \R^D$\R^D$, under mild assumptions on the activation function
    (‘squashing’ activation functions; e.g. sigmoid) and given the number of hidden units is large enough
    • discrete case: a neural network can approximate any function from a discrete space to another

Beyond Binary Classification

• binary classification: data \{\mathbf x_n, y_n\}_{n=1}^N$\{\mathbf x_n, y_n\}_{n=1}^N$ where y_n\in\{0,1\}$y_n\in\{0,1\}$
  • final layer activation: sigmoid; f(\mathbf{x,W})=\frac1{1+\exp(-a)}$f(\mathbf{x,W})=\frac1{1+\exp(-a)}$ where a$a$ is the output of the last layer before activation (logits)
  • conditional distribution: Bernoulli; p(y\mid\mathbf x) = \text{Bernoulli}(y\mid f(\mathbf{x,W}))$p(y\mid\mathbf x) = \text{Bernoulli}(y\mid f(\mathbf{x,W}))$
  • loss function: binary cross entropy; E(\boldsymbol{W}) = -\sum_{n=1}^{N} \log p(y_n \mid \boldsymbol{x}_n) = -\sum_{n=1}^{N} \Big( y_n \log f(\boldsymbol{x}_n, \boldsymbol{W}) + (1 - y_n) \log (1 - f(\boldsymbol{x}_n, \boldsymbol{W})) \Big)$E(\boldsymbol{W}) = -\sum_{n=1}^{N} \log p(y_n \mid \boldsymbol{x}_n) = -\sum_{n=1}^{N} \Big( y_n \log f(\boldsymbol{x}_n, \boldsymbol{W}) + (1 - y_n) \log (1 - f(\boldsymbol{x}_n, \boldsymbol{W})) \Big)$
• multi-class classification: data \{\mathbf x_n, \mathbf y_n\}_{n=1}^N$\{\mathbf x_n, \mathbf y_n\}_{n=1}^N$, where \mathbf y_n \in \{0,1\}^K$\mathbf y_n \in \{0,1\}^K$ and K$K$ is the number of classes
  • final layer activation: softmax; f_k(\mathbf{x,W}) = \frac{\exp(a_k)}{\sum_{j=1}^K\exp(a_j)}$f_k(\mathbf{x,W}) = \frac{\exp(a_k)}{\sum_{j=1}^K\exp(a_j)}$
  • conditional distribution: categorical; p(\mathbf y\mid\mathbf x) = \text{Categorical}(\mathbf y\mid f(\mathbf{x,W}))$p(\mathbf y\mid\mathbf x) = \text{Categorical}(\mathbf y\mid f(\mathbf{x,W}))$
  • loss function: categorical cross entropy; E(\mathbf{W}) = -\sum_{n=1}^{N} \log p(\boldsymbol{y}_n \mid \boldsymbol{x}_n) = -\sum_{n=1}^{N} \sum_{k=1}^{K} y_{nk} \log f_k(\boldsymbol{x}_n, \mathbf{W})$E(\mathbf{W}) = -\sum_{n=1}^{N} \log p(\boldsymbol{y}_n \mid \boldsymbol{x}_n) = -\sum_{n=1}^{N} \sum_{k=1}^{K} y_{nk} \log f_k(\boldsymbol{x}_n, \mathbf{W})$
• single-output regression: data \{\mathbf x_n, y_n\}_{n=1}^N$\{\mathbf x_n, y_n\}_{n=1}^N$ where y_n\in\R$y_n\in\R$
  • final layer activation: identity (no activation); f(\mathbf{x,W})=a$f(\mathbf{x,W})=a$
  • conditional distribution: Gaussian; p(y\mid\mathbf x)=\mathcal N(y\mid f(\mathbf{x,W}),1)$p(y\mid\mathbf x)=\mathcal N(y\mid f(\mathbf{x,W}),1)$
  • loss function: squared error / Gaussian cross-entropy;

Parameter Learning

• minimizing loss function (non-convex): gradient descent; \mathbf W^{(new)}=\mathbf W^{(old)}-\tau\nabla_{\mathbf W}E(\mathbf W^{(old)})$\mathbf W^{(new)}=\mathbf W^{(old)}-\tau\nabla_{\mathbf W}E(\mathbf W^{(old)})$
  
• backpropagation: automatic differentiation; method of computing gradient for gradient descent
  1. write f(x)$f(x)$ as a composition of modules (definition of a "module" depends on the task)
     
  2. work out the local derivative of each module symbolically
     
  3. do a forward pass for a given input x$x$ (i.e. compute f(x)$f(x)$ and remember the intermediate values for each module)
     
  4. compute the local derivatives for x$x$
     
  5. obtain the global derivative by multiplying the local derivatives
     

• Jacobian: let f:\R^n\to\R^m$f:\R^n\to\R^m$, let \mathbf a=f(\mathbf x)$\mathbf a=f(\mathbf x)$; the Jacobian is an m \times n$m \times n$ matrix of partial derivatives
  • \frac{\partial \mathbf{a}}{\partial \mathbf{x}} = \begin{bmatrix} \frac{\partial a_1}{\partial x_1} & \dots & \frac{\partial a_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial a_m}{\partial x_1} & \dots & \frac{\partial a_m}{\partial x_n} \end{bmatrix} \in \mathbb{R}^{m \times n}$\frac{\partial \mathbf{a}}{\partial \mathbf{x}} = \begin{bmatrix} \frac{\partial a_1}{\partial x_1} & \dots & \frac{\partial a_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial a_m}{\partial x_1} & \dots & \frac{\partial a_m}{\partial x_n} \end{bmatrix} \in \mathbb{R}^{m \times n}$
• gradient: let g:\R^m\to\R$g:\R^m\to\R$, let c=g(\mathbf a)$c=g(\mathbf a)$; the gradient \nabla_ac\in\R^m$\nabla_ac\in\R^m$ is the transpose of the Jacobian \frac{\partial c}{\partial \mathbf a}\in\R^{1\times m}$\frac{\partial c}{\partial \mathbf a}\in\R^{1\times m}$
  • \nabla_{\mathbf{a}} c = \left( \frac{\partial c}{\partial \mathbf{a}} \right)^T = \begin{bmatrix} \frac{\partial c}{\partial a_1} & \dots & \frac{\partial c}{\partial a_m} \end{bmatrix}^T$\nabla_{\mathbf{a}} c = \left( \frac{\partial c}{\partial \mathbf{a}} \right)^T = \begin{bmatrix} \frac{\partial c}{\partial a_1} & \dots & \frac{\partial c}{\partial a_m} \end{bmatrix}^T$
  • \nabla_{\mathbf{a}} c$\nabla_{\mathbf{a}} c$ has the same shape as \mathbf a$\mathbf a$
• chain rule: can be compactly represented using Jacobian matrices
  • summation: \frac{\partial c}{\partial x_{j}}=\sum_{i=1}^{m} \frac{\partial c}{\partial a_{i}} \frac{\partial a_{i}}{\partial x_{j}}$\frac{\partial c}{\partial x_{j}}=\sum_{i=1}^{m} \frac{\partial c}{\partial a_{i}} \frac{\partial a_{i}}{\partial x_{j}}$
  • matrix form: \underbrace{\frac{\partial c}{\partial \boldsymbol{x}}}_{\in \mathbb{R}^{1 \times n}} = \underbrace{\frac{\partial c}{\partial \boldsymbol{a}}}_{\in \mathbb{R}^{1 \times m}} \underbrace{\frac{\partial \boldsymbol{a}}{\partial \boldsymbol{x}}}_{\in \mathbb{R}^{m \times n}}, \quad \text{where } \left[\frac{\partial \boldsymbol{a}}{\partial \boldsymbol{x}}\right]_{i j} = \frac{\partial a_{i}}{\partial x_{j}} \in \mathbb{R}$\underbrace{\frac{\partial c}{\partial \boldsymbol{x}}}_{\in \mathbb{R}^{1 \times n}} = \underbrace{\frac{\partial c}{\partial \boldsymbol{a}}}_{\in \mathbb{R}^{1 \times m}} \underbrace{\frac{\partial \boldsymbol{a}}{\partial \boldsymbol{x}}}_{\in \mathbb{R}^{m \times n}}, \quad \text{where } \left[\frac{\partial \boldsymbol{a}}{\partial \boldsymbol{x}}\right]_{i j} = \frac{\partial a_{i}}{\partial x_{j}} \in \mathbb{R}$
  • gradient form: \underbrace{\nabla_{\boldsymbol{x}} c}_{\in \mathbb{R}^{n}} = \underbrace{\left(\frac{\partial \boldsymbol{a}}{\partial \boldsymbol{x}}\right)^{T}}_{\in \mathbb{R}^{n \times m}} \underbrace{\nabla_{\boldsymbol{a}} c}_{\in \mathbb{R}^{m}}$\underbrace{\nabla_{\boldsymbol{x}} c}_{\in \mathbb{R}^{n}} = \underbrace{\left(\frac{\partial \boldsymbol{a}}{\partial \boldsymbol{x}}\right)^{T}}_{\in \mathbb{R}^{n \times m}} \underbrace{\nabla_{\boldsymbol{a}} c}_{\in \mathbb{R}^{m}}$
• computational graph of a neural network: represent model as nodes (operations); each module defines forward(x) (compute output) and backward(dE/dy) (propagate gradient)
  

Structured Data

• different layers: there are many types of layers for specific tasks/data aside from stacked feed-forward layers...
  • convolution layer: typically used for images
  • recurrent layer: typically used for sequences
  • graph convolutional layers: typically used for graphs
• convolutional neural network (CNN): replace dense connections with convolutions →$→$ huge parameter reduction
  
  • convolution: weighted average of the input signal x$x$ using the weights (or kernel, filter) k$k$ at each point in time t$t$; acting on multiple channels
    • discrete convolution (for CNNs): (x * k)(t) = \sum_{\tau=-\infty}^\infty x(\tau)(t-\tau)$(x * k)(t) = \sum_{\tau=-\infty}^\infty x(\tau)(t-\tau)$
    • for images (2D): (x*k)(i,j)=\sum_l\sum_m x(l,m)k(i-l,j-m)$(x*k)(i,j)=\sum_l\sum_m x(l,m)k(i-l,j-m)$
    • cross-correlation (what is usually meant): \hat x(i,j)=\sum_{l=1}^L\sum_{m=1}^M x(i+l,j+m)k(l,m)$\hat x(i,j)=\sum_{l=1}^L\sum_{m=1}^M x(i+l,j+m)k(l,m)$
      
  • padding: what happens at the boundaries?
    • VALID: do not use padding, instead reduce size in output to D_{l+1}=(D_l-K)+1$D_{l+1}=(D_l-K)+1$
      • D_l$D_l$ input size along a dimension
      • K$K$ kernel width (of "receptive field")
    • SAME (half padding): add padding so that the input size is preserved, i.e. add P=\lfloor\frac K2\rfloor$P=\lfloor\frac K2\rfloor$ values on each side
    • FULL: add K-1$K-1$ values on each side, increasing the output size
      
    • stride: distance between positions the kernel is applied.
      • downsampling: S > 1$S > 1$
      • new output size: D_{l+1}=\lfloor\frac{D_l+2P-K}S\rfloor+1$D_{l+1}=\lfloor\frac{D_l+2P-K}S\rfloor+1$
        
  • pooling: calculates summary statistics in sliding window, introduces invariance to small movements
    

Training Deep Neural Networks

• bias-variance tradeoff: models with more parameters have lower bias, but higher variance; once model complexity passes a certain threshold, the variance dominates and the test error increases again
• empirical observation: deep neural networks can be trained to have very low training error, even if they have many more parameters than training examples
• double descent: a model's error rate on the test set initially decreases with the number of parameters, then peaks, then decreases again
  
• training a neural network: changing the weights of a neural network so that the loss on the training data is minimized, done by computing the gradient of the loss w.r.t. the weights and then updating the weights via a specific optimization method (e.g., SGD, Adam, AMSgrad, etc.)
• weight symmetry: if two hidden units have exactly the same bias and exactly the same incoming and outgoing weights, they will always get exactly the same gradient
  • problem: they can never learn to extract different features
  • solution: initialize weights to have small random values
• weight scale: if a hidden unit has a large fan-in (number of incoming weights or number of units in the previous layer), small changes on many of its incoming weights can make the unit saturate (e.g. sigmoid); if a hidden unit has a large fan-out (number of outgoing weights or number of units in the subsequent layer), the gradient can be large and cause large changes to the weights during the optimization step and / or cause large changes to the weights of the previous layer in the backward pass
  • problem: vanishing / exploding gradients
• Xavier Glorot initialization: keeps variance stable across layers, prevents gradient issues
  
  • weight matrices: zero mean, Var(\mathbf W) = \frac2{\text{fan-in}+\text{fan-out}}$Var(\mathbf W) = \frac2{\text{fan-in}+\text{fan-out}}$
    • example: \mathbf W \sim \text{Uniform}\left(-\sqrt{\frac{6}{\text{fan-in}+\text{fan-out}}}, \sqrt{\frac{6}{\text{fan-in}+\text{fan-out}}}\right)$\mathbf W \sim \text{Uniform}\left(-\sqrt{\frac{6}{\text{fan-in}+\text{fan-out}}}, \sqrt{\frac{6}{\text{fan-in}+\text{fan-out}}}\right)$
• vanishing / exploding gradients: network will take a long time to converge / computations become unstable
• regularization: prevents overfitting (e.g. dropout: randomly deactivate neurons during training)
• hyperparameter optimization: tune e.g. architecture, activation functions, optimizer / learning rate, preprocessing through random search, Bayesian optimization, meta-learning...
• frameworks: PyTorch, TensorFlow...
• batch normalization: normalization technique used to make training faster and more stable by adjusting the inputs to each layer; re-centering them around zero and re-scaling them to a standard size
• skip connections (residual learning): directly pass input to deeper layers

Support Vector Machines (SVMs)

• maximum margin classifier: find a hyperplane that separates both classes with the maximum margin
  • linear classifier with margin: add two more hyperplanes that are parallel to the original hyperplane and require that no training points must lie between those hyperplanes
    
• support vector machine (SVM): supervised max-margin models with associated learning algorithms that analyze data for classification and regression analysis; chooses the hyperplane with the largest margin
  • optimization problem (constrained optimization / quadratic programming): to find the separating hyperplane with maximum margin, find \{\mathbf w,b\}$\{\mathbf w,b\}$ that
    \text{minimize } f_0(\mathbf w, b)=\frac12\mathbf w^T\mathbf w\\\text{subject to } f_i(\mathbf w,b)=y_i(\mathbf w^T \mathbf x_i+b)-1 \geq 0 \text{ for }i=1,...,N$\text{minimize } f_0(\mathbf w, b)=\frac12\mathbf w^T\mathbf w\\\text{subject to } f_i(\mathbf w,b)=y_i(\mathbf w^T \mathbf x_i+b)-1 \geq 0 \text{ for }i=1,...,N$
• constrained optimization problem: given f_0:\R^d\to\R$f_0:\R^d\to\R$ and f_i:\R^d\to\R$f_i:\R^d\to\R$, minimize_\theta$_\theta$ f_0(\theta)$f_0(\theta)$ subject to f_i(\theta) \leq 0$f_i(\theta) \leq 0$ for i=1,...,M$i=1,...,M$
  • feasibility: a point \theta \in \R^d$\theta \in \R^d$ that satisfies the constraints of the optimization problem, i.e. f_i(\theta) \leq 0$f_i(\theta) \leq 0$ for all i \in \{1,...,M\}$i \in \{1,...,M\}$
  • minimum and minimizer: the minimum p^*$p^*$ is the optimal value; the minimizer \theta^*$\theta^*$ is the point where the minimum is obtained, i.e. p^* = f_0(\theta^*)$p^* = f_0(\theta^*)$
  • Lagrangian: L:\R^d \times \R^M \to \R,\;\;\;L(\theta,\alpha)=f_0(\theta)+\sum_{i=1}^M\alpha_if_i(\theta)$L:\R^d \times \R^M \to \R,\;\;\;L(\theta,\alpha)=f_0(\theta)+\sum_{i=1}^M\alpha_if_i(\theta)$
    • \alpha_i \geq 0$\alpha_i \geq 0$: Lagrange multiplier associated with the inequality constraint f_i(\theta)\leq 0$f_i(\theta)\leq 0$
  • Lagrange dual function: g:\R^M\to\R$g:\R^M\to\R$, maps \alpha$\alpha$ to the minimum of the Lagrangian over \theta$\theta$; possibly -\infty$-\infty$ for some values of \alpha$\alpha$; concave in \alpha$\alpha$
    • g(\alpha) = \min_{\theta\in\R^d} L(\theta,\alpha)=\min_{\theta\in\R^d}\left(f_0(\theta)+\sum_{i=1}^M\alpha_if_i(\theta)\right)$g(\alpha) = \min_{\theta\in\R^d} L(\theta,\alpha)=\min_{\theta\in\R^d}\left(f_0(\theta)+\sum_{i=1}^M\alpha_if_i(\theta)\right)$
    • interpretation: lower bound on the optimal value of the constrained problem
      • formally: \forall \alpha: f_0(\theta^*) \geq g(\alpha)$\forall \alpha: f_0(\theta^*) \geq g(\alpha)$
    • Lagrange dual problem: what is the best (highest) lower bound?
      • \text{maximize}_\alpha\;\;g(\alpha)\\\text{subject to } \;\;\alpha_i\geq0, i =1,...,m$\text{maximize}_\alpha\;\;g(\alpha)\\\text{subject to } \;\;\alpha_i\geq0, i =1,...,m$
      • d^*$d^*$: maximum of the Lagrange dual problem; best lower bound on p^*$p^*$ achieved by using the Lagrangian
      • note: g(\alpha) \neq -\infty$g(\alpha) \neq -\infty$ usually added as an additional constraint
      • \alpha$\alpha$ feasible \iff$\iff$ all \alpha_i \geq 0$\alpha_i \geq 0$ and L(\theta,\alpha)$L(\theta,\alpha)$ bounded from below for \theta\in\R^d$\theta\in\R^d$
      • weak duality (always): d^* \leq p^*$d^* \leq p^*$ (duality gap: p^*-d^* \geq 0$p^*-d^* \geq 0$)
      • strong duality (under certain conditions): d^*=p^*$d^*=p^*$, i.e. f_0(\theta^*)=g(\alpha^*)$f_0(\theta^*)=g(\alpha^*)$
        • complementary slackness: \forall i\geq 1: \alpha_i^*f_i(\theta^*)=0$\forall i\geq 1: \alpha_i^*f_i(\theta^*)=0$
  • SVM dual problem: recipe for solving the constrained optimization problem
    1. calculate Lagrangian: L(\mathbf w,b,\mathbf \alpha)=\frac12\mathbf w^T\mathbf w - \sum_{i=1}^N\alpha_i(y_i(\mathbf w^T\mathbf x_i + b)-1)$L(\mathbf w,b,\mathbf \alpha)=\frac12\mathbf w^T\mathbf w - \sum_{i=1}^N\alpha_i(y_i(\mathbf w^T\mathbf x_i + b)-1)$
    2. minimize Lagrangian w.r.t. \mathbf w$\mathbf w$ and b$b$: \nabla_{\mathbf w}L(\mathbf w,b,\alpha)=\mathbf w-\sum_{i=1}^N\alpha_iy_i\mathbf x_i\overset!=0,\;\;\;\frac{\partial L}{\partial b}=\sum_{i=1}^N\alpha_iy_i\overset!=0$\nabla_{\mathbf w}L(\mathbf w,b,\alpha)=\mathbf w-\sum_{i=1}^N\alpha_iy_i\mathbf x_i\overset!=0,\;\;\;\frac{\partial L}{\partial b}=\sum_{i=1}^N\alpha_iy_i\overset!=0$
       • thus, \mathbf w = \sum_{i=1}^N\alpha_iy_i\mathbf x_i$\mathbf w = \sum_{i=1}^N\alpha_iy_i\mathbf x_i$
       • \text{maximize } g(\boldsymbol{\alpha}) = \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} y_i y_j \alpha_i \alpha_j \boldsymbol{x_i}^T \boldsymbol{x_j}\\\text{subject to }\sum_{i=1}^N\alpha_iy_i=0, \alpha_i \geq 0, i=1,...,N$\text{maximize } g(\boldsymbol{\alpha}) = \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} y_i y_j \alpha_i \alpha_j \boldsymbol{x_i}^T \boldsymbol{x_j}\\\text{subject to }\sum_{i=1}^N\alpha_iy_i=0, \alpha_i \geq 0, i=1,...,N$
    3. solve the reformulated problem (e.g. sequential minimal optimization)
  • support vectors: lying on the margin, define the decision boundary, lead to sparse solution
    • formally: training sample \mathbf x_i$\mathbf x_i$ with \alpha_i \neq 0$\alpha_i \neq 0$
    • indices of all support vectors: \mathcal S=\{i\mid \alpha_i \neq 0\}$\mathcal S=\{i\mid \alpha_i \neq 0\}$
  • prediction: h(\mathbf x)=\text{sign}\left(\sum_{i\in\mathcal S}\alpha_iy_i\mathbf x_i^T\mathbf x+b\right)$h(\mathbf x)=\text{sign}\left(\sum_{i\in\mathcal S}\alpha_iy_i\mathbf x_i^T\mathbf x+b\right)$
    

Soft Margin Support Vector Machines

• problem: noisy data; a single outlier would cause the corresponding Lagrange multiplier \alpha_i$\alpha_i$ to go to infinity and destroy the solution
  
• slack variable: relax the constraints as much as necessary but punish the relaxation of a constraint
  • formally: introduce \xi_i \geq 0$\xi_i \geq 0$ for every training sample \mathbf x_i$\mathbf x_i$ giving the distance of how far the margin is violated by this training sample in units of ||\mathbf w||$||\mathbf w||$
  • \begin{aligned} & \text{minimize} & f_0(\boldsymbol{w}, b, \boldsymbol{\xi}) &= \frac{1}{2} \boldsymbol{w}^T \boldsymbol{w} + C \sum_{i=1}^N \xi_i \\ & \text{subject to} & y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) &- 1 + \xi_i \geq 0, & i=1, \dots, N, \\ & & \xi_i &\geq 0, & i=1, \dots, N. \end{aligned}$\begin{aligned} & \text{minimize} & f_0(\boldsymbol{w}, b, \boldsymbol{\xi}) &= \frac{1}{2} \boldsymbol{w}^T \boldsymbol{w} + C \sum_{i=1}^N \xi_i \\ & \text{subject to} & y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) &- 1 + \xi_i \geq 0, & i=1, \dots, N, \\ & & \xi_i &\geq 0, & i=1, \dots, N. \end{aligned}$
    • C >0$C >0$: determines how heavy a violation is punished; C \to \infty$C \to \infty$ recovers hard-margin SVM
  • \begin{aligned} & \text{maximize} \quad & g(\boldsymbol{\alpha}) &= \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N y_i y_j \alpha_i \alpha_j \boldsymbol{x}_i^T \boldsymbol{x}_j \\ & \text{subject to} \quad & \sum_{i=1}^N \alpha_i y_i &= 0 \\ & & 0 \leq \alpha_i &\leq {C} \qquad i=1, \dots, N. \end{aligned}$\begin{aligned} & \text{maximize} \quad & g(\boldsymbol{\alpha}) &= \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N y_i y_j \alpha_i \alpha_j \boldsymbol{x}_i^T \boldsymbol{x}_j \\ & \text{subject to} \quad & \sum_{i=1}^N \alpha_i y_i &= 0 \\ & & 0 \leq \alpha_i &\leq {C} \qquad i=1, \dots, N. \end{aligned}$
  • prediction: h(\boldsymbol{x}) = \text{sign} \left( \sum_{j \in \mathcal{S}} \alpha_j y_j \boldsymbol{x}_j^T \boldsymbol{x} + b \right)$h(\boldsymbol{x}) = \text{sign} \left( \sum_{j \in \mathcal{S}} \alpha_j y_j \boldsymbol{x}_j^T \boldsymbol{x} + b \right)$
    

Kernels

• problem: linear SVM cannot model nonlinear patterns
• kernel trick: define kernel function k:\R^D\times\R^D\to\R$k:\R^D\times\R^D\to\R$ and rewrite dual
  • k(\mathbf x_i, \mathbf x_j) := \phi(\mathbf x_i)^T\phi(\mathbf x_j)$k(\mathbf x_i, \mathbf x_j) := \phi(\mathbf x_i)^T\phi(\mathbf x_j)$
  • g(\boldsymbol{\alpha}) = \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} y_i y_j \alpha_i \alpha_j k(\boldsymbol{x}_i, \boldsymbol{x}_j)$g(\boldsymbol{\alpha}) = \sum_{i=1}^{N} \alpha_i - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} y_i y_j \alpha_i \alpha_j k(\boldsymbol{x}_i, \boldsymbol{x}_j)$
  • can be used in any model that can be formulated such that it only depends on the inner products \mathbf x^T_i \mathbf x_j$\mathbf x^T_i \mathbf x_j$ (e.g. linear regression, k-nearest neighbors)
  • prediction: h(\boldsymbol{x}) = \text{sign} \left( \sum_{j \in \mathcal{S}} \alpha_j y_j k(\boldsymbol{x}_j, \boldsymbol{x}) + b \right)$h(\boldsymbol{x}) = \text{sign} \left( \sum_{j \in \mathcal{S}} \alpha_j y_j k(\boldsymbol{x}_j, \boldsymbol{x}) + b \right)$
    
  • valid kernel: a kernel k$k$ is valid if it gives rise to a symmetric, positive semidefinite kernel / Gram matrix \mathbf K\in\R^{N \times N}$\mathbf K\in\R^{N \times N}$ for any input data \mathbf X$\mathbf X$
    • \boldsymbol{K} = \begin{pmatrix} k(\boldsymbol{x}_1, \boldsymbol{x}_1) & k(\boldsymbol{x}_1, \boldsymbol{x}_2) & \cdots & k(\boldsymbol{x}_1, \boldsymbol{x}_N) \\ k(\boldsymbol{x}_2, \boldsymbol{x}_1) & k(\boldsymbol{x}_2, \boldsymbol{x}_2) & \cdots & k(\boldsymbol{x}_2, \boldsymbol{x}_N) \\ \vdots & \vdots & \ddots & \vdots \\ k(\boldsymbol{x}_N, \boldsymbol{x}_1) & k(\boldsymbol{x}_N, \boldsymbol{x}_2) & \cdots & k(\boldsymbol{x}_N, \boldsymbol{x}_N) \end{pmatrix}$\boldsymbol{K} = \begin{pmatrix} k(\boldsymbol{x}_1, \boldsymbol{x}_1) & k(\boldsymbol{x}_1, \boldsymbol{x}_2) & \cdots & k(\boldsymbol{x}_1, \boldsymbol{x}_N) \\ k(\boldsymbol{x}_2, \boldsymbol{x}_1) & k(\boldsymbol{x}_2, \boldsymbol{x}_2) & \cdots & k(\boldsymbol{x}_2, \boldsymbol{x}_N) \\ \vdots & \vdots & \ddots & \vdots \\ k(\boldsymbol{x}_N, \boldsymbol{x}_1) & k(\boldsymbol{x}_N, \boldsymbol{x}_2) & \cdots & k(\boldsymbol{x}_N, \boldsymbol{x}_N) \end{pmatrix}$
      
    • examples of kernels: polynomial, Gaussian, Sigmoid
      • polynomial: k(\mathbf{a,b}) = (\mathbf{a}^T\mathbf b)^p$k(\mathbf{a,b}) = (\mathbf{a}^T\mathbf b)^p$ or k(\mathbf{a,b}) = (\mathbf{a}^T\mathbf b+1)^p$k(\mathbf{a,b}) = (\mathbf{a}^T\mathbf b+1)^p$
      • Gaussian: k(\mathbf{a,b}) = \exp\left(-\frac{||\mathbf{a-b}||^2}{2\sigma²}\right)$k(\mathbf{a,b}) = \exp\left(-\frac{||\mathbf{a-b}||^2}{2\sigma²}\right)$
      • Sigmoid (not PSD!): k(\mathbf{a,b})=\tanh(\kappa\mathbf{a}^T\mathbf b-\delta)$k(\mathbf{a,b})=\tanh(\kappa\mathbf{a}^T\mathbf b-\delta)$ for \kappa,\delta > 0$\kappa,\delta > 0$
• SVM for multiple classes: one-vs-rest, one-vs-one

Dimensionality Reduction

• unsupervised learning: trying to find the hidden / latent structure in the data (e.g. clustering, anomaly detection)
• dimensionality reduction: reduce the dimensionality while avoiding information loss (\to$\to$ computational / memory savings, uncovering intrinsic dimensionality of data)
• feature subselection: choose "good" dimensions using a-priori knowledge or appropriate heuristics (e.g. remove low variance dimensions); requires expert knowledge, prone to misjudgement, features may be correlated...
• linear transformations: change of basis, potentially discarding dimensions
  • formally: use orthonormal transformation matrix \mathbf F \in \R^{d \times k}$\mathbf F \in \R^{d \times k}$
    • (\mathbf x')^T = \mathbf x^T\mathbf F$(\mathbf x')^T = \mathbf x^T\mathbf F$: transformation of (column) vector \mathbf x$\mathbf x$ into the new coordinate system defined by \mathbf F$\mathbf F$
    • \mathbf X' = \mathbf X \mathbf F$\mathbf X' = \mathbf X \mathbf F$: matrix containing all the transformed points \mathbf x_i'$\mathbf x_i'$
    • \overline{\mathbf x}$\overline{\mathbf x}$: mean vector (row) in the original data space (transformed space: \overline{\mathbf x'}=\overline{\mathbf x}\mathbf F$\overline{\mathbf x'}=\overline{\mathbf x}\mathbf F$)
    • \mathbf\Sigma_{\mathbf X}$\mathbf\Sigma_{\mathbf X}$: covariance matrix in the original data space (transformed space: \mathbf\Sigma_{\mathbf X'}=\mathbf F^T\mathbf\Sigma_{\mathbf X}\mathbf F$\mathbf\Sigma_{\mathbf X'}=\mathbf F^T\mathbf\Sigma_{\mathbf X}\mathbf F$)
      
      

Principal Component Analysis

• optimality: approximate the data with few coefficients as well as possible
• principal component analysis (PCA): find a coordinate system in which the (possibly originally correlated) points are linearly uncorrelated (dimensions with no / low variance can be ignored) \to$\to$ finds the optimal transformation by deriving uncorrelated dimensions
  • goal: transform the data, such that the covariance between the new dimensions is 0
  • given: N$N$ data points \{\mathbf x_i\}_{i=1}^N, \mathbf x_i \in \R^d \forall i\in\{1,...,N\}$\{\mathbf x_i\}_{i=1}^N, \mathbf x_i \in \R^d \forall i\in\{1,...,N\}$
    • \mathbf X=\begin{pmatrix}x_{11} & ... & x_{1d} \\ \vdots & \ddots & \vdots \\ x_{N1} & ... & x_{Nd}\end{pmatrix}$\mathbf X=\begin{pmatrix}x_{11} & ... & x_{1d} \\ \vdots & \ddots & \vdots \\ x_{N1} & ... & x_{Nd}\end{pmatrix}$
    • row \mathbf x_i = \{x_{i1},...,x_{id}\}\in\R^d$\mathbf x_i = \{x_{i1},...,x_{id}\}\in\R^d$ denotes the i$i$-th point
    • column \mathbf X_{:,j}$\mathbf X_{:,j}$ denotes the vector containing all values from the j$j$-th dimension
  • approach: center data \to$\to$ compute covariance matrix \to$\to$ use eigenvector decomposition to transform coordinate system
    
• centering the data: shift points by their mean: \tilde{\mathbf x}_i=\mathbf x_i - \overline{\mathbf x}$\tilde{\mathbf x}_i=\mathbf x_i - \overline{\mathbf x}$
  
  • zero order statistic: number of points N$N$
  • first order statistic: mean of the N$N$ points: \overline{\mathbf x} = \begin{pmatrix}\overline x_1\\ \vdots \\ \overline x_d\end{pmatrix} = \frac1N\mathbf\cdot X^T\cdot\mathbf1_N$\overline{\mathbf x} = \begin{pmatrix}\overline x_1\\ \vdots \\ \overline x_d\end{pmatrix} = \frac1N\mathbf\cdot X^T\cdot\mathbf1_N$
    • \mathbf1_N$\mathbf1_N$: N$N$-dimensional vector of ones
• computing covariance matrix: determine variances Var(\tilde{\mathbf X}_j)$Var(\tilde{\mathbf X}_j)$ for each dimension j\in\{1,...,d\}$j\in\{1,...,d\}$; determine covariance Cov(\tilde{\mathbf X}_{j_1}, \tilde{\mathbf X}_{j_2})$Cov(\tilde{\mathbf X}_{j_1}, \tilde{\mathbf X}_{j_2})$ between dimensions {j_1}, {j_2}${j_1}, {j_2}$ for all {j_1} \neq {j_2} \in \{1,...,d\}${j_1} \neq {j_2} \in \{1,...,d\}$; create covariance matrix \mathbf\Sigma_{\tilde{\mathbf X}} \in \R^{d\times d}$\mathbf\Sigma_{\tilde{\mathbf X}} \in \R^{d\times d}$
  • \text{Var}(\boldsymbol{X}_j) = \frac{1}{N} \sum_{i=1}^{N} (\boldsymbol{x}_{ij} - \bar{\boldsymbol{x}}_j)^2 = \frac{1}{N} \cdot \boldsymbol{X}_j^T \boldsymbol{X}_j - \bar{\boldsymbol{x}}_j^2$\text{Var}(\boldsymbol{X}_j) = \frac{1}{N} \sum_{i=1}^{N} (\boldsymbol{x}_{ij} - \bar{\boldsymbol{x}}_j)^2 = \frac{1}{N} \cdot \boldsymbol{X}_j^T \boldsymbol{X}_j - \bar{\boldsymbol{x}}_j^2$
  • \text{Cov}(\boldsymbol{X}_{j_1}, \boldsymbol{X}_{j_2}) = \frac{1}{N} \sum_{i=1}^{N} (\boldsymbol{x}_{ij_1} - \bar{\boldsymbol{x}}_{j_1}) \cdot (\boldsymbol{x}_{ij_2} - \bar{\boldsymbol{x}}_{j_2}) = \frac{1}{N} \cdot \boldsymbol{X}_{j_1}^T \boldsymbol{X}_{j_2} - \bar{\boldsymbol{x}}_{j_1} \bar{\boldsymbol{x}}_{j_2}$\text{Cov}(\boldsymbol{X}_{j_1}, \boldsymbol{X}_{j_2}) = \frac{1}{N} \sum_{i=1}^{N} (\boldsymbol{x}_{ij_1} - \bar{\boldsymbol{x}}_{j_1}) \cdot (\boldsymbol{x}_{ij_2} - \bar{\boldsymbol{x}}_{j_2}) = \frac{1}{N} \cdot \boldsymbol{X}_{j_1}^T \boldsymbol{X}_{j_2} - \bar{\boldsymbol{x}}_{j_1} \bar{\boldsymbol{x}}_{j_2}$
  • \boldsymbol{\Sigma}_X = \begin{bmatrix} \text{Var}(\boldsymbol{X}_1) & \text{Cov}(\boldsymbol{X}_1, \boldsymbol{X}_2) & \dots & \text{Cov}(\boldsymbol{X}_1, \boldsymbol{X}_d) \\ \text{Cov}(\boldsymbol{X}_2, \boldsymbol{X}_1) & \text{Var}(\boldsymbol{X}_2) & & \\ \vdots & & \ddots & \vdots \\ \text{Cov}(\boldsymbol{X}_d, \boldsymbol{X}_1) & \dots & & \text{Var}(\boldsymbol{X}_d) \end{bmatrix} = \frac{1}{N} \boldsymbol{X}^T \boldsymbol{X} - \bar{\boldsymbol{x}} \bar{\boldsymbol{x}}^T$\boldsymbol{\Sigma}_X = \begin{bmatrix} \text{Var}(\boldsymbol{X}_1) & \text{Cov}(\boldsymbol{X}_1, \boldsymbol{X}_2) & \dots & \text{Cov}(\boldsymbol{X}_1, \boldsymbol{X}_d) \\ \text{Cov}(\boldsymbol{X}_2, \boldsymbol{X}_1) & \text{Var}(\boldsymbol{X}_2) & & \\ \vdots & & \ddots & \vdots \\ \text{Cov}(\boldsymbol{X}_d, \boldsymbol{X}_1) & \dots & & \text{Var}(\boldsymbol{X}_d) \end{bmatrix} = \frac{1}{N} \boldsymbol{X}^T \boldsymbol{X} - \bar{\boldsymbol{x}} \bar{\boldsymbol{x}}^T$
  • (!) covariance matrices are symmetric
• eigendecomposition of the covariance matrix: \boldsymbol{\Sigma}_{\widetilde{\boldsymbol{X}}} = \boldsymbol{\Gamma} \cdot \boldsymbol{\Lambda} \cdot \boldsymbol{\Gamma}^T$\boldsymbol{\Sigma}_{\widetilde{\boldsymbol{X}}} = \boldsymbol{\Gamma} \cdot \boldsymbol{\Lambda} \cdot \boldsymbol{\Gamma}^T$
  • \boldsymbol{\Gamma}$\boldsymbol{\Gamma}$ normalized eigenvectors, orthonormal (\boldsymbol{\Gamma}\boldsymbol{\Gamma}^T = \boldsymbol{\Gamma}^T\boldsymbol{\Gamma} = I$\boldsymbol{\Gamma}\boldsymbol{\Gamma}^T = \boldsymbol{\Gamma}^T\boldsymbol{\Gamma} = I$, \boldsymbol{\Gamma}^T=\boldsymbol{\Gamma}^{-1}$\boldsymbol{\Gamma}^T=\boldsymbol{\Gamma}^{-1}$)
  • \boldsymbol{\Lambda}$\boldsymbol{\Lambda}$: diagonal matrix with eigenvalues \lambda_i$\lambda_i$ as diagonal elements
  • principal components: eigenvectors of \boldsymbol{\Sigma}_{\widetilde{\boldsymbol{X}}}$\boldsymbol{\Sigma}_{\widetilde{\boldsymbol{X}}}$
  • new coordinate system: defined by eigenvectors \mathbf \gamma_i$\mathbf \gamma_i$
  • transformed data: \mathbf Y={\widetilde{\boldsymbol{X}}}\cdot\mathbf \Gamma$\mathbf Y={\widetilde{\boldsymbol{X}}}\cdot\mathbf \Gamma$
  • new covariance matrix: \boldsymbol{\Lambda}$\boldsymbol{\Lambda}$
    • interpretation: new system has variance \lambda_i$\lambda_i$ in dimension i$i$; \forall i_1 \neq i_2: Cov(\mathbf Y_{i_1}, \mathbf Y_{i_2})=0$\forall i_1 \neq i_2: Cov(\mathbf Y_{i_1}, \mathbf Y_{i_2})=0$
    • coordinates with low variance (low \lambda_i$\lambda_i$) can be ignored
  • truncation of \mathbf \Gamma$\mathbf \Gamma$: keep only columns (i.e. eigenvectors) of \mathbf Γ$\mathbf Γ$ corresponding to the largest k$k$ eigenvalues λ_1 , ... , λ_k$λ_1 , ... , λ_k$
    • \mathbf Y_{reduced}={\widetilde{\boldsymbol{X}}}\cdot\mathbf \Gamma_{reduced}$\mathbf Y_{reduced}={\widetilde{\boldsymbol{X}}}\cdot\mathbf \Gamma_{reduced}$
    • choosing k$k$: 90% rule (k$k$ variances should explain 90\%$90\%$ of the energy); k$k$ smallest value ensuring \sum_{i=1}^k \lambda_i \geq 0.9\sum_{i=1}^d\lambda_i$\sum_{i=1}^k \lambda_i \geq 0.9\sum_{i=1}^d\lambda_i$

Singular Value Decomposition

• low-dimensional manifold (intrinsic dimensionality): data often lies on a low-dimensional manifold embedded in higher dimensional space
  
• rank of a matrix (= dimensionality): number of linearly independent columns / rows of the matrix
  • example: M=\begin{pmatrix}1&2&1\\-2&-3&1\\3&5&0\end{pmatrix}$M=\begin{pmatrix}1&2&1\\-2&-3&1\\3&5&0\end{pmatrix}$ has rank r=2$r=2$ since the first row is equal to the sum of the second and third \implies$\implies$ assuming each row represents a point A,B,C$A,B,C$, we can use the new basis vectors (1,2,1),(-2,-3,1)$(1,2,1),(-2,-3,1)$ and write the points as A=(1,0), B=(0,1), C=(1,-1)$A=(1,0), B=(0,1), C=(1,-1)$, reducing the number of coordinates
• low rank approximation: approximate original data \mathbf A$\mathbf A$ by a low rank matrix \mathbf B$\mathbf B$
  • goal: given matrix \mathbf A \in \R^{n \times d}$\mathbf A \in \R^{n \times d}$, find \mathbf B\in\R^{n \times d}$\mathbf B\in\R^{n \times d}$ with rank(\mathbf B)=k$rank(\mathbf B)=k$ that minimizes ||\mathbf{A-B}||_F²=\sum_{i=1}^N\sum_{j=1}^D (a_{ij}-b_{ij})²$||\mathbf{A-B}||_F²=\sum_{i=1}^N\sum_{j=1}^D (a_{ij}-b_{ij})²$
    
• singular value decomposition (SVD): each real matrix \mathbf A\in\R^{n\times d}$\mathbf A\in\R^{n\times d}$ can be exactly decomposed into \mathbf A = \mathbf U \cdot \mathbf \Sigma \cdot \mathbf V^T$\mathbf A = \mathbf U \cdot \mathbf \Sigma \cdot \mathbf V^T$
  • \mathbf U \in \R^{n \times r}, \mathbf \Sigma \in \R^{r \times r}, \mathbf V \in \R^{d \times r}$\mathbf U \in \R^{n \times r}, \mathbf \Sigma \in \R^{r \times r}, \mathbf V \in \R^{d \times r}$
    • \mathbf U$\mathbf U$: left singular vectors, orthonormal columns, \mathbf U^T \mathbf U = \mathbf I$\mathbf U^T \mathbf U = \mathbf I$
    • \mathbf V$\mathbf V$: right singular vectors, orthonormal columns, \mathbf V^T \mathbf V = \mathbf I$\mathbf V^T \mathbf V = \mathbf I$
  • \mathbf \Sigma$\mathbf \Sigma$: diagonal, r$r$ rank of matrix \mathbf A$\mathbf A$, entries (singular values) \sigma_i$\sigma_i$ positive and sorted in decreasing order
  • low rank approximation: set smallest singular value(s) to zero, remove corresponding row(s) / column(s) in singular vector matrices
    
    
    

Matrix Factorization

• goal: find \mathbf Q \in \R^{n \times k}$\mathbf Q \in \R^{n \times k}$ and \mathbf P \in \R^{d\times k}$\mathbf P \in \R^{d\times k}$ optimizing \min_{\mathbf{P,Q}} \sum_{(u,i)\in S}(r_{ui}-\mathbf q_u \cdot \mathbf p_i^T)² =: \min_{\mathbf{P,Q}} f(\mathbf{P,Q})$\min_{\mathbf{P,Q}} \sum_{(u,i)\in S}(r_{ui}-\mathbf q_u \cdot \mathbf p_i^T)² =: \min_{\mathbf{P,Q}} f(\mathbf{P,Q})$
  • S$S$: set of tuples (u,i)$(u,i)$ of users u$u$ that have rated item i$i$ with a rating of r_{ui}$r_{ui}$
  • block coordinate optimization: pick initial values for \mathbf{P,Q}$\mathbf{P,Q}$; alternatingly keep one variable fixed and optimize for the other; repeat until convergence
    1. initialize \mathbf P^{(0)}, \mathbf Q^{(0)}, t=0$\mathbf P^{(0)}, \mathbf Q^{(0)}, t=0$
    2. \mathbf P^{(t+1)}=\argmin_{\mathbf P} f(\mathbf{P,Q}^{(t)})$\mathbf P^{(t+1)}=\argmin_{\mathbf P} f(\mathbf{P,Q}^{(t)})$
    3. \mathbf Q^{(t+1)}=\argmin_{\mathbf Q} f(\mathbf{P}^{(t+1)},\mathbf{Q})$\mathbf Q^{(t+1)}=\argmin_{\mathbf Q} f(\mathbf{P}^{(t+1)},\mathbf{Q})$
    4. t = t+1$t = t+1$
    5. goto 2 until convergence
       

Clustering

• unsupervised learning: given some unlabeled data \{\mathbf x_i\}$\{\mathbf x_i\}$ we want to discover latent structure in it
• clustering: group objects \mathbf x_i$\mathbf x_i$ into K$K$ groups (clusters) based on their similarity
  • given: collection of data points \mathbf X=\{\mathbf x_1,...,\mathbf x_N\}$\mathbf X=\{\mathbf x_1,...,\mathbf x_N\}$
    • goal: for each object \mathbf x_i$\mathbf x_i$, find the corresponding assignment z_i \in\{1,...,K\}$z_i \in\{1,...,K\}$ to one of the K$K$ clusters such that objects within the same group are similar to each other and objects between different groups are dissimilar to each other

K-means Algorithm

• distance-based clustering: minimize dissimilarity provided by a distance function d(\cdot,\cdot)$d(\cdot,\cdot)$
  • Manhattan distance: d(\boldsymbol{x}_i, \boldsymbol{x}_j) = \sum_d |\boldsymbol{x}_{id} - \boldsymbol{x}_{jd}| = ||\boldsymbol{x}_i - \boldsymbol{x}_j||_1$d(\boldsymbol{x}_i, \boldsymbol{x}_j) = \sum_d |\boldsymbol{x}_{id} - \boldsymbol{x}_{jd}| = ||\boldsymbol{x}_i - \boldsymbol{x}_j||_1$
  • Euclidian distance: d(\boldsymbol{x}_i, \boldsymbol{x}_j) = \sqrt{\sum_d (\boldsymbol{x}_{id} - \boldsymbol{x}_{jd})^2} = ||\boldsymbol{x}_i - \boldsymbol{x}_j||_2$d(\boldsymbol{x}_i, \boldsymbol{x}_j) = \sqrt{\sum_d (\boldsymbol{x}_{id} - \boldsymbol{x}_{jd})^2} = ||\boldsymbol{x}_i - \boldsymbol{x}_j||_2$
  • Mahalanobis distance: d(\boldsymbol{x}_i, \boldsymbol{x}_j) = \sqrt{(\boldsymbol{x}_i - \boldsymbol{x}_j)^T \boldsymbol{\Sigma}^{-1} (\boldsymbol{x}_i - \boldsymbol{x}_j)}$d(\boldsymbol{x}_i, \boldsymbol{x}_j) = \sqrt{(\boldsymbol{x}_i - \boldsymbol{x}_j)^T \boldsymbol{\Sigma}^{-1} (\boldsymbol{x}_i - \boldsymbol{x}_j)}$
• model: each of the K$K$ clusters is defined by its centroid \mu_k\in\R^d$\mu_k\in\R^d$
  
  • cluster indicator: z_i \in \{0,1\}^K, z_{ik}=1\iff x_i$z_i \in \{0,1\}^K, z_{ik}=1\iff x_i$ belongs to cluster k$k$ (one-hot encoding)
  • K$K$-means objective (distortion measure): J(\boldsymbol{X}, \boldsymbol{Z}, \boldsymbol{\mu}) = \sum_{i=1}^N \sum_{k=1}^K z_{ik} \|\boldsymbol{x}_i - \boldsymbol{\mu}_k\|_2^2$J(\boldsymbol{X}, \boldsymbol{Z}, \boldsymbol{\mu}) = \sum_{i=1}^N \sum_{k=1}^K z_{ik} \|\boldsymbol{x}_i - \boldsymbol{\mu}_k\|_2^2$
  • goal: find \boldsymbol{Z}^*, \boldsymbol{\mu}^* = \arg \min_{\boldsymbol{Z}, \boldsymbol{\mu}} J(\boldsymbol{X}, \boldsymbol{Z}, \boldsymbol{\mu})$\boldsymbol{Z}^*, \boldsymbol{\mu}^* = \arg \min_{\boldsymbol{Z}, \boldsymbol{\mu}} J(\boldsymbol{X}, \boldsymbol{Z}, \boldsymbol{\mu})$
    • alternating optimization (Lloyd's algorithm): joint minimization is difficult, so update \mathbf Z$\mathbf Z$ and \mu$\mu$ in turns
      1. initialize centroids \mu=\{\mu_1,...,\mu_K\}$\mu=\{\mu_1,...,\mu_K\}$
      2. update cluster indicators, i.e. solve \min_ZJ(\mathbf X,\mathbf Z,\mu)$\min_ZJ(\mathbf X,\mathbf Z,\mu)$: z_{ik}=\begin{cases}1&\text{if }k=\argmin_j||\mathbf x_i-\mu_j||²)\\0&\text{else}\end{cases}$z_{ik}=\begin{cases}1&\text{if }k=\argmin_j||\mathbf x_i-\mu_j||²)\\0&\text{else}\end{cases}$
      3. update centroids, i.e. solve \min_\mu J(\mathbf X,\mathbf Z,\mu)$\min_\mu J(\mathbf X,\mathbf Z,\mu)$: \boldsymbol{\mu}_k = \frac{1}{N_k} \sum_{i=1}^N z_{ik} \boldsymbol{x}_i \quad \text{where } N_k = \sum_{i=1}^N z_{ik}$\boldsymbol{\mu}_k = \frac{1}{N_k} \sum_{i=1}^N z_{ik} \boldsymbol{x}_i \quad \text{where } N_k = \sum_{i=1}^N z_{ik}$
      4. if J(\mathbf X,\mathbf Z,\mu)$J(\mathbf X,\mathbf Z,\mu)$ has not converged, go to step 2
  • centroid initialization: K$K$-means++ algorithm
    1. choose first centroid \mu_1$\mu_1$ uniformly at random among data points
    2. for each point \mathbf x_i$\mathbf x_i$, compute distance D_i²=||\mathbf x_i-\mu_i||_2²$D_i²=||\mathbf x_i-\mu_i||_2²$
    3. sample next centroid \mu_k$\mu_k$ from \{\mathbf x_i\}$\{\mathbf x_i\}$ with probability proportional to D_i²$D_i²$
    4. recompute D_i^2 = \min \{ \|\boldsymbol{x}_i - \boldsymbol{\mu}_1\|_2^2, \dots, \|\boldsymbol{x}_i - \boldsymbol{\mu}_k\|_2^2 \}.$D_i^2 = \min \{ \|\boldsymbol{x}_i - \boldsymbol{\mu}_1\|_2^2, \dots, \|\boldsymbol{x}_i - \boldsymbol{\mu}_k\|_2^2 \}.$
    5. continue 3. and 4. until K$K$ initial centroids have been chosen

Gaussian Mixture Model

• probabilistic unsupervised learning: design a probabilistic model for the data, p(\mathbf {x,z} \mid θ)$p(\mathbf {x,z} \mid θ)$, parametrized by θ$θ$ which we have to estimate (when doing clustering, we implicitly assume that each point \mathbf x$\mathbf x$ belongs to some cluster \mathbf z$\mathbf z$)
  • estimation (supervised): both \mathbf X \in \R^{N\times D}$\mathbf X \in \R^{N\times D}$ and \mathbf Z\in\{0,1\}^{N \times K}$\mathbf Z\in\{0,1\}^{N \times K}$ are known
    • MLE: \theta^* = \argmax_\theta p(\mathbf{X,Z}\mid\theta)$\theta^* = \argmax_\theta p(\mathbf{X,Z}\mid\theta)$
  • estimation (unsupervised): only \mathbf X \in \R^{N\times D}$\mathbf X \in \R^{N\times D}$ is known
    • Gaussian mixture model (GMM): p(x) = \sum_{k=1}^K \pi_k \mathcal{N}(x | \mu_k, \Sigma_k)$p(x) = \sum_{k=1}^K \pi_k \mathcal{N}(x | \mu_k, \Sigma_k)$