CS M146 Midterm Cheatsheet

Misc

• $\Vert \vec{x}{\Vert }_p={\left(\sum _i|x_i{|}^p\right)}^{\frac{1}{p}}$
• $L_{\text{ridge}}=\lambda \Vert \theta {\Vert }_2$, circular
• $\nabla b^{{}^{\top }}x=b$
• $\nabla x^{T}Ax=2Ax$

Validation

• $CV(\text{Model})=\frac{1}{K}\sum _{i=1}^{K}L({\hat{f}}_{C_{-i}}(C_i))$

  • $K=$ number of chunks
  • ${\hat{f}}_{C_{-i}}=$ model fitted to the training set of all chunks that aren’t $C_i$, the validation set

Decision Trees

• $\Delta H=H_{\text{parent}}-\sum _i{p}_i{H}_{\text{children}}$
• $H(X)\equiv -\mathbb{E}[\log p(X)]$
• $g=1-\sum _i{p}_i^2$

K-Nearest Neighbors

• ${\text{nn}}_k(x)={\text{argmin}}_{n\in \left([N]-{\sum }_{i=1}^{k-1}{\text{nn}}_i(x)\right)}\Vert x-x_n{\Vert }_2^2$
  • Gives the index in $[N]$ of the $k$th nearest neighbor of $x$, or the data point we’re interested in classifying
  • $[N]$ is an array of indices for each data sample point
  • We use the square of the L2 norm here to calculate distance but other measures could work
• $\text{knn}(x)=\left\{{\text{nn}}_1(x),{\text{nn}}_2(x),\dots ,{\text{nn}}_K(x)\right\}$
  • Gives the set of indices of the $K$ nearest neighbors to $x$
• $v_c=\sum _{n\in \text{knn}(x)}\mathbb{I}(y_n==c)\forall c\in [C]$
  • Gives the number of “votes” for a particular class/label $c$
  • We iterate over each of the $K$-nearest neighbors and increment by one every time the neighbor equals the class of interest

• $y=h(x)={\text{argmax}}_{c\in [C]}{v}_c$

  • The prediction is the class $c$ that maximizes the number of votes

Steps To Classify

1. Initialize
   1. Place the data point in a feature space
2. Calculate Distance
   2. Find the Euclidean distance from the data point with all other labeled data
   3. May have to normalize data point values along different coordinates to be Z-scores for each coordinate
3. Sort Distance
   1. Sort distances of the data point with other labeled data points in increasing order
   2. For classification, the most common class of $k$-nearest neighbors determines the data point class
   3. For regression, use the average of the $k$-nearest neighbors’ labels

Perceptron

• $H=\left\{h|h:\mathbb{X}\to \mathbb{Y},h(\mathbf{x})=\text{sign}(a)\right\}$

• $$\displaystyle \text{Margin}(\mathcal{D},w)=\begin{cases}

\text{min}{(x,y)\in \mathcal{D}} \frac{1}{\left\lVert w\right\rVert}y{n}w^{T}x_{n} & \text{for separating hyperplane }w \
-\infty & \text{else}
\end{cases}$$

• $\text{Margin}(\mathcal{D})={\text{max}}_w\text{Margin}(\mathcal{D},w)$
• $a=\sum _{d=1}^D{w}_d{x}_d+b=w^{T}x+b$

Mistake Bound Theorem

• For a dataset $\left\{(x_1,y_1),\dots ,(x_N,y_N)\right\}$ with $R\ge \Vert x_n{\Vert }_2$ and labels $y_n\in \left\{-1,1\right\}$
• Suppose $\exists u\in {\mathbb{R}}^D:\exists \gamma >0\wedge \gamma \le y_n{u}^{{}^{\top }}{x}_n$
  • $u$ can be thought of as a $w$ of a candidate for the margin of the dataset
• Then the PerceptronTrainingAlgorithm will make $\le \frac{R^2}{{\gamma }^2}$ mistakes on the training sequence
• Proof Preliminaries: $w_0=0,\Vert x_n\Vert \le R,y_n{u}^T{x}_n\ge \gamma$
• Proof (1/3): After $t$ mistakes, $u^T{w}_t\ge t\gamma$ by induction from $w_0=0$ and using $u^T{w}_{t+1}=u^T(w_t+y_n{x}_n)$
• Proof (2/3): After $t$ mistakes, ${\Vert w_t\Vert }^2\le t{R}^2$
• Proof (3/3): $R\sqrt{t}\ge \Vert w_t\Vert \ge u^T{w}_t\ge t\gamma$

Logistic Regression

• $J(\theta )=-\sum _n\left\{y_n\log h_{\theta }(x_n)+(1-y_n)\log [1-h_{\theta }(x_n)]\right\}$
• $h_{\theta }(x)=P(y=1|x;\theta )=\sigma (a)=\frac{1}{1+e^{-a}}$
• $\frac{\partial J(\theta )}{\partial \theta }=\sum _n\left\{h_{\theta }(x_n)-y_n\right\}{x}_n$

Convexity

• $f(\lambda a+(1-\lambda )b)\le \lambda f(a)+(1-\lambda )f(b),\lambda \in [0,1]\to f(x)$ is convex
• $f(x)$ is convex $\to f^{\prime \prime }(x)>0\forall x$
• ${\mathbf{H}}_f⪰0\to f$ is convex
• $x^{\top }Ax\ge 0\to A⪰0$
• ${\mathbf{H}}_f={\nabla }_x^{2}f(x)\in {\mathbb{R}}^{n\times n}:({\nabla }_x^{2}f(x){)}_{ij}={\partial }_{x_i,x_j}f(x)$

Linear Regression

• $\hat{Y}={\hat{\beta }}_{1}X+{\hat{\beta }}_0+\epsilon$
• $\epsilon =\eta \sim \mathcal{N}(0,{\sigma }^2)$
• $J(\mathbf{\theta })=\sum _n[y_n-({\theta }_{1}X+{\theta }_0{)}^2]={\Vert \mathbf{y}-\mathbf{X\theta }\Vert }_2^2$
  • The loss function for simple linear regression
  • Minimizing this by varying ${\beta }_0$/${\beta }_1$ or $\mathbf{\theta }$ gives the linear model that best fits with the data $\mathbf{y}$
  • $\mathbf{y}$ is the target vector
• ${\theta }_1=\frac{{\sum }_i(x_i-\bar{x})(y_i-\bar{y})}{{\sum }_i(x_i-\bar{x}{)}^2}$
• ${\theta }_0=\bar{y}-{\theta }_1\bar{x}$
• $\text{MSE}(\beta )=\frac{1}{n}\Vert \mathbf{Y}-\mathbf{X}\theta {\Vert }^2$
• $\theta =\underset{\beta }{\mathrm{argmin}}\text{MSE}(\beta )=({\mathbf{X}}^{\top }\mathbf{X}{)}^{-1}{\mathbf{X}}^{\top }\mathbf{Y}$
• ${\sigma }^2=\sum \frac{(\hat{f}(x)-y_i{)}^2}{n}$

Regularized

• $\hat{\theta }=({\mathbf{X}}^{{}^{\top }}\mathbf{X}+\lambda \mathbf{I}{)}^{-1}{\mathbf{X}}^{{}^{\top }}\mathbf{y}$
• $\nabla J(\mathbf{w})=2({\mathbf{X}}^{{}^{\top }}\mathbf{Xw}-{\mathbf{X}}^{{}^{\top }}\mathbf{y}+\lambda \mathbf{w})$

Run Times

Algorithm	Training Time Complexity	Test Time Complexity
Decision Tree	$O(n\log (n))$ to $O(n^2)$ (depends on splitting strategy)	$O(\log (n))$ (balanced) or $O(n)$ (unbalanced)
K-Nearest Neighbors (KNN)	$O(1)$ (no training, just storing data)	$O(nd)$ (linear search) or $O(\log (n))$ (KD-tree, low dimensions)
Perceptron	$O(nd)$ per epoch	$O(d)$
Logistic Regression	$O(nd)$ per iteration (gradient-based)	$O(d)$
Linear Regression (Analytical - Normal Equation)	$O(d^3+n{d}^2)$ (matrix inversion)	$O(d)$
Linear Regression (Gradient Descent)	$O(ndk)$ (depends on iterations $k$)	$O(d)$
Full Batch Gradient Descent	$O(ndk)$	$O(d)$
Stochastic Gradient Descent (SGD)	$O(dk)$	$O(d)$
Mini-Batch Gradient Descent	$O\left(\frac{n}{b}dk\right)$ (where $b$ is batch size)	$O(d)$

• $n$ = number of training samples
• $d$ = number of features (dimensions)
• $k$ = number of iterations in gradient-based methods
• $b$ = batch size for mini-batch gradient descent

Algorithms