ift6135.tex

\documentclass[]{article}
\usepackage[margin = 1.5in]{geometry}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{color}
\usepackage{multicol}
\usepackage{float}
\usepackage{enumitem}
\usepackage[lined]{algorithm2e}
\usepackage{hyperref}

%\usepackage[T1]{fontenc}
%\usepackage{mathtools}
%\usepackage{listings}

\setlength{\marginparwidth}{1.5in}
\setlength{\parindent}{0in}

\definecolor{darkish-blue}{RGB}{25,103,185}
\hypersetup{
    colorlinks,
    citecolor=darkish-blue,
    filecolor=darkish-blue,
    linkcolor=darkish-blue,
    urlcolor=darkish-blue
}

\DeclareMathOperator*{\argmax}{\arg\!\max}
\DeclareMathOperator*{\argmin}{\arg\!\min}

%\definecolor{dkgreen}{rgb}{0,0.6,0}
%\definecolor{gray}{rgb}{0.5,0.5,0.5}
%\definecolor{mauve}{rgb}{0.58,0,0.82}
%\lstset{
%language=C,
%aboveskip=3mm,
%belowskip=3mm,
%showstringspaces=false,
%columns=flexible,
%basicstyle={\small\ttfamily},
%numbers=none,
%numberstyle=\tiny\color{gray},
%keywordstyle=\color{blue},
%commentstyle=\color{dkgreen},
%stringstyle=\color{mauve},
%breaklines=true,
%breakatwhitespace=true,
%tabsize=4
%}

%\DeclarePairedDelimiter{\set}{\lbrace}{\rbrace}
%\newcommand{\lecture}[1]{\marginpar{{\footnotesize $\leftarrow$ \underline{#1}}}}


%\makeatletter
%\def\blfootnote{\gdef\@thefnmark{}\@footnotetext}
%\makeatother

\begin{document}

\title{\bf{IFT 6135: Representation Learning}}
\date{Winter 2019 \\ \center Notes written from Aaron Courville's lectures.}
\author{Michael Noukhovitch}

\maketitle
\newpage
\tableofcontents
\newpage

\section{Neural Networks}%
\label{sec:neural_networks}

\subsection{Artificial Neuron}%
\label{sub:artificial_neuron}

$g(b + w^Tx)$
\begin{description}
    \item[pre-activation] $b + w^Tx$
    \item[connection weights] $w$
    \item[neuron bias] $b$
    \item[activation function] $g$
\end{description}

\subsection{Activation Functions}%
\label{sub:activation_functions}

\begin{description}
    \item[linear] $a$
    \item[sigmoid] $\frac{1}{1 + \exp(-a)}$
    \item[tanh] $\frac{\exp{a} - \exp{-a}}{\exp(a) + \exp(-a)}$
    \item[ReLU] $\max(0,a)$
    \item[maxout] $\max_{j \in [1,k]} a_j$
    \item[softmax] $\frac{\exp(a_i)}{\sum_c \exp(a_c)} \forall i$
\end{description}

\subsection{Neural Networks}%
\label{sub:single_layer_neural_network}

\subsubsection{Single Layer}%
\label{ssub:single_layer}

\begin{description}
    \item[neuron capacity] a single neuron can do binary classification iff linearly separable
    \item[universal approximation theorem] (Hornik, 1991)
        a single-layer NN can approximate any continuous function given enough hidden units
\end{description}

\subsubsection{Multi Layer}%
\label{ssub:multi_layer}

\begin{description}
    \item[input] $h^{(0)} = x$
    \item[hidden layer pre] $a^{(k)} (x) = b^{(k)} + W^{(k)} h^{(k-1)}(x)$
    \item[hidden layer activation] $h^{(k)} = g(a^{(k)}(x))$
    \item[output] $h^{(L+1)}(x) = o(a^{(L+1)}(x))$
\end{description}

\subsection{Biological Inspiration}%
\label{sub:biological_inspiration}


\section{Training Neural Networks}%
\label{sec:training_neural_networks}

\subsection{Empirical Risk Minimization}%
\label{sub:empirical_risk_minimization}
learning as optimization
\begin{equation*}
    \argmin_\theta \frac{1}{T} \sum_t l(f(x^{(t)};\theta), y^{(t)}) + \lambda \Omega(\theta)
\end{equation*}

\begin{description}
    \item[loss function] $l$ is a surrogate for what we truly want (upper bound)
    \item[regularizer] $\Omega$ penalizes certain values of $\theta$
\end{description}

\subsection{Stochastic Gradient Descent}%
\label{sub:stochastic_gradient_descent}

\begin{algorithm}[H]
    \DontPrintSemicolon
    initialize $\theta$ \;
    \For{$n$ \textup{epochs}}{
        \ForEach{\textup{training example} $x^{(t)}, y^{(t)}$}{
            $\Delta \gets -\nabla_\theta l(f(x^{(t)};\theta), y^{(t)}) - \lambda \nabla_\theta \Omega(\theta)$ \;
            $\theta \gets \theta + \alpha \Delta$ \;
        }
    }
\end{algorithm}
\begin{description}
    \item[gradient] $\nabla$
    \item[learning rate] $\alpha$
\end{description}
this requires:
\begin{itemize}
    \item a loss function
    \item gradient computation \ref{sub:gradient_computation}
    \item a regularizer \ref{sub:regularization}
    \item initialization \ref{sub:initialization}
\end{itemize}

\subsection{Gradient Computation}%
\label{sub:gradient_computation}

\subsubsection{Manual}%
\label{ssub:manual}


given a categorical output with classes $c$, let softmax output be $f(x)_c = p(y = c|x)$

\begin{align*}
    \intertext{gradients for output}
    \frac{\partial}{\partial f(x)_c} - \log f(x)_y &= \frac{-1_{(y=c)}}{f(x)_y} \\
    \nabla_{f(x)} - \log f(x)_y &= \frac{-1}{f(x)_y} \begin{bmatrix} 1_{(y=0)} \\ \dots \\ 1_{(y=C-1)} \end{bmatrix} \\
    &= \frac{-e(y)}{f(x)_y}
    \intertext{gradients for pre-activation}
    \frac{\partial}{\partial a^{(L+1)}(x)} - \log \sigma(a^{(L+1)}(x))_y &= -(1_{(y=c)} - f(x)_y) \\
    \nabla_{f(x)} - \log f(x)_y &= -(e(y) - f(x))
\end{align*}

where $e(y)$ gives the one-hot vector of length $C$ with 1 at index $y$, and $\sigma$ is the sigmoid function


\subsubsection{Backpropogation}%
\label{ssub:backpropogation}

To simplify things, use the chain rule to rewrite gradients in terms of in terms of the layers above them

\begin{algorithm}[H]
    \BlankLine
    \DontPrintSemicolon
    compute output gradient $\nabla_{a^{(L+1)}(x)} - \log f(x)_y = -(e(y) - f(x))$ \;
    \For{$k = L+1 \to 1$}{
        hidden layer weights \;
        \Indp $\nabla_{W^{(k)}(x)} - \log f(x)_y = (\nabla_{a^{(k)}(x)} - \log f(x)_y) h^{(k-1)}(x)^T$ \;
        \Indm hidden layer biases \;
        \Indp $\nabla_{b^{(k)}(x)} - \log f(x)_y = \nabla_{a^{(k)}(x)} - \log f(x)_y$ \;
        \Indm output below \;
        \Indp $\nabla_{h^{(k-1)}(x)} - \log f(x)_y = {W^{(k)}}^T (\nabla_{a^{(k)}(x)} - \log f(x)_y)$ \;
        \Indm pre-activation below \;
        \Indp $\nabla_{a^{(k-1)}(x)} - \log f(x)_y = (\nabla_{h^{(k-1)}(x)} - \log f(x)_y) \bigodot [\dots, g'(a^{(k-1)}(x)_j, \dots] $
    }
\end{algorithm}

\subsubsection{Flow Graph}%
\label{ssub:flow_graph}
represent execution as a modular, acyclic flow graph of boxes with
\begin{itemize}
    \item method \texttt{fprop} children $\to$ parents
    \item method \texttt{bprop} parents $\to$ children
\end{itemize}
debug with \textbf{finite difference approximation}
\begin{equation*}
    \frac{\partial f(x)}{\partial x} \approx \frac{f(x - \epsilon) - f(x + \epsilon)}{2\epsilon}
\end{equation*}

\subsection{Regularization}%
\label{sub:regularization}

\subsubsection{Methods}%
\label{ssub:methods}

\begin{description}
    \item[L2] $\sum_{k,i,j} (W_{i,j}^{(k)})^2$
        \begin{itemize}
            \item gradient $2 W^{(k)}$
            \item like a gaussian prior
        \end{itemize}
    \item[L1] $\sum_{k,i,j} | W_{i,j}^{(k)} |$
        \begin{itemize}
            \item gradient $\text{sign}(W^{(k)})$
            \item laplacian prior, pushes weights to be 0
        \end{itemize}
    \item[early stopping] stop training when validation error increases (with lookahead)
\end{description}

\subsubsection{Bias-Variance Tradeoff}%
\label{ssub:bias_variance_tradeoff}

for a learning algorithm:
\begin{description}
    \item[variance] variance between using different training sets
    \item[bias] difference between average model and true solution
\end{description}


\subsection{Initialization}%
\label{sub:initialization}

\begin{itemize}
    \item bias $\to 0$
    \item weights $\sim$ \texttt{uniform}$(-b,b), \ \ b = \frac{\sqrt{6}}{\sqrt{H_k + H_{k-1}}}$
        \begin{itemize}
            \item 0 doesn't work for $\tanh$
            \item same value makes everything behave same
        \end{itemize}
\end{itemize}

\subsection{Model Selection}%
\label{sub:model_selection}

\begin{description}
    \item[training set] train the model
    \item[validation set] select hyperparameters
    \item[test set] estimate generalization error
    \item[grid search] try all hyperparameters
    \item[random search] sample distribution of hyperparameters
\end{description}

\subsection{First-Order Optimization}%
\label{sub:optimization}

\subsubsection{SGD}%
\label{ssub:sgd}

stochastic gradient descent
\begin{enumerate}
    \item sample a minibatch of $m$ examples
    \item gradient estimate $\hat h \gets \frac{1}{m} \nabla_\theta \sum_i L(x_i, y_i; \theta)$
    \item apply update $\theta \gets \theta - \epsilon \hat h$
\end{enumerate}

properties
\begin{itemize}
    \item \textbf{non-convex} because there isn't a global optimum
    \item convergence if $\sum_{t=1}^\infty \alpha_t = \infty$ and $\sum_{t=1}^\infty \alpha_t^2 < \infty$
\end{itemize}

tricks
\begin{description}
    \item[decaying learning rate] e.g. $ \frac{\alpha}{1 + \delta t}$
    \item[mini-batching] using $>1$ example for gradient computation
    \item[exponentially decaying] average of previous gradients
\end{description}

\subsubsection{Momentum}

keep momentum of previous updates,
\begin{enumerate}
    \item[0.] momentum parameter $\alpha$
    \item gradient estimate $h$
    \item velocity update $v \gets \alpha v - \epsilon h$
    \item update $\theta \gets \theta + v$
\end{enumerate}

properties
\begin{itemize}
    \item accelerate learning with small, consistent gradients
    \item gradients that are consistently seen will accumulate
    \item max step size (``terminal velocity'') $\frac{1}{1-\alpha} \epsilon ||g||$
\end{itemize}

\subsubsection{Nesterov Momentum}%
\label{ssub:nesterov_momentum}

Sutskever et al (2013) evaluate the gradient after an interim velocity update
\begin{enumerate}
    \item[0.] momentum parameter $\alpha$
    \item apply interim velocity update $\tilde \theta \gets \theta + \alpha v$
    \item gradient estimate $h$ at interim using $\tilde \theta$
    \item velocity update $v \gets \alpha v - \epsilon h$
    \item update $\theta \gets \theta + v$
\end{enumerate}

intuition
\begin{itemize}
    \item first make a big jump in previously accumulated gradient
    \item measure gradient where you end up
    \item make a correction jump
\end{itemize}

\subsubsection{Adagrad}%
\label{ssub:adagrad}

Duchi et al (2010) adapt the learning rate per parameter proportional to sum of squares of that gradient
\begin{enumerate}
    \item[0.] numerical stability const $\delta$
    \item[0.] initialize gradient accumulation $r = 0$
    \item gradient estimate $h$
    \item accumulate squared gradient $r \gets r + h \odot h$
    \item per-parameter update $\Delta \theta \gets - \frac{\epsilon}{\delta + \sqrt{r}} \odot h$
    \item update $\theta \gets \theta + \Delta \theta$
\end{enumerate}


adapted learning rates
\begin{enumerate}
    \item makes later learning very slow
    \item great for convex, not so much for NN
\end{enumerate}

\subsubsection{RMSProp}%
\label{ssub:rmsprop}

Hinton (2012?) modifies AdaGrad accumulation into exponentially moving average
\begin{enumerate}
    \item[0.] decay rate $\rho$, numerical stability const $\delta$
    \item[0.] initialize gradient accumulation $r = 0$
    \item gradient estimate $h$
    \item accumulate squared gradient $r \gets \rho r + (1 - \rho) h \odot h$
    \item per-parameter update $\Delta \theta \gets - \frac{\epsilon}{\delta + \sqrt{r}} \odot h$
    \item update $\theta \gets \theta + \Delta \theta$
\end{enumerate}

you can add nesterov momentum $v \gets \alpha v - \frac{\epsilon}{\sqrt{r}} \odot h$ \hfill

\vspace{1em}

generally better with NNs
\begin{itemize}
    \item performs better in non-convex setting
    \item decay $\rho$ allows control of length scale of EMA
    \item effective with NNs but can be difficult to tune hyperparams
\end{itemize}

\subsubsection{Adam}%
\label{ssub:adam}

''Adaptive Moments'' (Kingma et al, 2014)
\begin{enumerate}
    \item[0.] step size $\epsilon$, default 0.001
    \item[0.] decay rates for moment estimates $\rho_1, \rho_2$ defaults $0.9, 0.999$
    \item[0.] numerical stability const $\delta$
    \item[0.] initialize 1st and 2nd moment variables $s = 0, r = 0$
    \item gradient estimate $h$
    \item update biased 1st moment estimate $s \gets \rho_1 s + (1 - \rho_1) h$
    \item update biased 2nd moment estimate $r \gets \rho_2 r + (1 - \rho_r) h \odot h$
    \item correct bias in 1st moment $\hat s \gets \frac{s}{1 - \rho_1^t}$
    \item correct bias in 2nd moment $\hat r \gets \frac{r}{1 - \rho_2^t}$
    \item per-parameter update $\Delta \theta \gets - \epsilon \frac{\hat s}{\delta + \sqrt{\hat r}} \odot h$
    \item update $\theta \gets \theta + \Delta \theta$
\end{enumerate}


variant of RMSProp + momentum with corrections
\begin{itemize}
    \item momentum incorporated directly as estimate of first order moment (with exponential weighting) of the gradient
    \item bias corrections to estimates of first-order momentum (momentum) and second-order moment to account for init at origin
\end{itemize}

\subsubsection{AdamW}%
\label{ssub:adamw}

Loschilov and Hutter (2019) decouple weight decay from optimization wrt loss function
\begin{enumerate}
    \item
\end{enumerate}

in SGD, reparametrizing $L_2$ hyperparam $\lambda$ based on learning rate can make it equivalent to weight decay
\begin{align*}
    L_2 &= \frac{\lambda'}{2} || \theta ||^2_2 \\
    \theta &\gets \theta - \epsilon \nabla_\theta (L + L_2) \\
           &\gets \theta - \epsilon \nabla_\theta L - \epsilon \lambda' \theta \\
           \intertext{set $\lambda' = \frac{\lambda}{\epsilon}$ }
           &\gets (1 - \lambda) \theta - \epsilon \nabla_\theta L \text{ which is weight decay}
\end{align*}

but this equivalence may not work
\begin{itemize}
    \item it doesn't hold for adaptive methods like Adam
    \item it requires you to set $\lambda' = \frac{\lambda}{\epsilon}$ which might not be the best
\end{itemize}

\subsection{Second-Order Optimization}%
\label{sub:second-optimization}

\subsubsection{Newton's Method}%
\label{ssub:newton_s_method}
approximate loss $J(\theta)$ near some point $\theta_0$ using Taylor Expansion
\begin{align*}
    J(\theta) &\approx J(\theta_0) + (\theta - \theta_0)^T \nabla_\theta J(\theta_0) + \frac{1}{2} (\theta - \theta_0)^T H(\theta - \theta_0)
    \intertext{taking the gradient}
    \nabla_\theta J(\theta) &\approx \nabla_\theta J(\theta_0) + H(\theta - \theta_0)
    \intertext{and solving for the critical point $\nabla_\theta J(\theta) = 0$ }
    \theta^* &= \theta_0 - H^{-1} \nabla_\theta J(\theta_0)
\end{align*}
this jumps directly to the minimum in a quadratic convex problem but as long as $H$ is positive definite, can be applied iteratively in non-quadratic.

\begin{enumerate}
    \item comute gradient $g$
    \item compute Hessian $H$
    \item compute inverse Hessian $H^{-1}$
    \item apply update $\theta \gets \theta - H^{-1} g$
\end{enumerate}
but inverting is $O(n^3)$, memory is $O(n^2)$ and models are too large 

\subsubsection{Conjugate Gradient}
just use 2nd order info to find directions conjugate to previous using $\beta_t$, not undo progress

\begin{enumerate}
    \item comute gradient $g_t$
    \item compute $\beta_t = \frac{(g_t - g_{t-1})^T g_t}{g_{t-1}^Tg_{t-1}} $
    \item compute search direction $\rho_t = -g_t + \beta_t \rho_{t-1}$
    \item perform line search and find $\epsilon^* = \argmin_\epsilon J(\theta_t + \epsilon \rho_t)$
    \item apply update $\theta \gets \theta - \epsilon^* \rho_t$
\end{enumerate}

\end{document}