\section{Introduction to Neural Networks} This chapter is based on \textcite[Chapter~6]{Goodfellow} and \textcite{Haykin}. Neural Networks are a mathematical construct inspired by the structure of brains in mammals. They consist of an array of neurons that receive inputs and compute an accumulated output. These neurons are arranged in layers, with one input and output layer and an arbitrary amount of hidden layers between them. The number of neurons in the in- and output layers correspond to the desired dimensions of in- and outputs of the model. In conventional neural networks, the information is fed forward from the input layer towards the output layer, hence they are often called feed forward networks. Each neuron in a layer has the outputs of all neurons in the preceding layer as input and computes an accumulated value from these (fully connected). % An illustration of an example neural network is given in % Figure~\ref{fig:nn} and one of a neuron in Figure~\ref{fig:neuron}. Illustrations of a neural network and the structure of a neuron are given in Figure~\ref{fig:nn} and Figure~\ref{fig:neuron}. \tikzset{% every neuron/.style={ circle, draw, minimum size=1cm }, neuron missing/.style={ draw=none, scale=1.5, text height=0.333cm, execute at begin node=\color{black}$\vdots$ }, } \begin{figure}[h!] \center % \fbox{ \resizebox{\textwidth}{!}{% \begin{tikzpicture}[x=1.75cm, y=1.75cm, >=stealth] \tikzset{myptr/.style={decoration={markings,mark=at position 1 with % {\arrow[scale=1.5,>=stealth]{>}}},postaction={decorate}}} \foreach \m/\l [count=\y] in {1,2,3,missing,4} \node [every neuron/.try, neuron \m/.try] (input-\m) at (0,2.55-\y*0.85) {}; \foreach \m [count=\y] in {1,missing,2} \node [every neuron/.try, neuron \m/.try ] (hidden1-\m) at (2.5,2.5-\y*1.25) {}; \foreach \m [count=\y] in {1,missing,2} \node [every neuron/.try, neuron \m/.try ] (hidden2-\m) at (5,2.5-\y*1.25) {}; \foreach \m [count=\y] in {1,missing,2} \node [every neuron/.try, neuron \m/.try ] (output-\m) at (7,1.5-\y*0.75) {}; \foreach \l [count=\i] in {1,2,3,d_i} \draw [myptr] (input-\i)+(-1,0) -- (input-\i) node [above, midway] {$x_{\l}$}; \foreach \l [count=\i] in {1,n_1} \node [above] at (hidden1-\i.north) {$\mathcal{N}_{1,\l}$}; \foreach \l [count=\i] in {1,n_l} \node [above] at (hidden2-\i.north) {$\mathcal{N}_{l,\l}$}; \foreach \l [count=\i] in {1,d_o} \draw [myptr] (output-\i) -- ++(1,0) node [above, midway] {$O_{\l}$}; \foreach \i in {1,...,4} \foreach \j in {1,...,2} \draw [myptr] (input-\i) -- (hidden1-\j); \foreach \i in {1,...,2} \foreach \j in {1,...,2} \draw [myptr] (hidden1-\i) -- (hidden2-\j); \foreach \i in {1,...,2} \foreach \j in {1,...,2} \draw [myptr] (hidden2-\i) -- (output-\j); \node [align=center, above] at (0,2) {Input\\layer}; \node [align=center, above] at (2,2) {Hidden \\layer $1$}; \node [align=center, above] at (5,2) {Hidden \\layer $l$}; \node [align=center, above] at (7,2) {Output \\layer}; \node[fill=white,scale=1.5,inner xsep=10pt,inner ysep=10mm] at ($(hidden1-1)!.5!(hidden2-2)$) {$\dots$}; \end{tikzpicture}}%} \caption[Illustration of a Neural Network]{Illustration of a neural network with $d_i$ inputs, $l$ hidden layers with $n_{\cdot}$ nodes in each layer, as well as $d_o$ outputs. } \label{fig:nn} \end{figure} \subsection{Nonlinearity of Neural Networks} The arguably most important feature of neural networks which sets them apart from linear models is the activation function implemented in the neurons. As illustrated in Figure~\ref{fig:neuron} on the weighted sum of the inputs an activation function $\sigma$ is applied resulting in the output of the $k$-th neuron in a layer $l$ with $m$ nodes in layer $l-1$ being given by \begin{align*} o_{l,k} = \sigma\left(b_{l,k} + \sum_{j=1}^{m} w_{l,k,j} o_{l-1,j}\right), \end{align*} for weights $w_{l,k,j}$ and biases $b_{l,k}$. For a network with $L$ hidden layers and inputs $o_{0}$ the final outputs of the network are thus given by $o_{L+1}$. The activation function is usually chosen nonlinear (a linear one would result in the entire network collapsing into a linear model) which allows it to better model data where the relation of in- and output is of nonlinear nature. There are two types of activation functions, saturating and non-saturating ones. Popular examples for the former are sigmoid functions where most commonly the standard logistic function or tangens hyperbolicus are used as they have easy to compute derivatives which is desirable for gradient-based optimization algorithms. The standard logistic function (often simply referred to as sigmoid function) is given by \[ f(x) = \frac{1}{1+e^{-x}} \] and has a realm of $[0,1]$. The tangens hyperbolicus is given by \[ \tanh(x) = \frac{2}{e^{2x}+1} \] and has a realm of $[-1,1]$. Both functions result in neurons that are close to inactive until a certain threshold is reached where they grow until saturation. The downside of these saturating activation functions is, that their derivatives are close to zero on most of their realm, only assuming larger values in proximity to zero. This can hinder the progress of gradient-based methods. The non-saturating activation functions commonly used are the rectified linear unit (ReLU) or the leaky ReLU. The ReLU is given by \begin{equation} r(x) = \max\left\{0, x\right\}. \label{eq:relu} \end{equation} This has the benefit of having a constant derivative for values larger than zero. However, the derivative being zero for negative values has the same downside for fitting the model with gradient-based methods. The leaky ReLU is an attempt to counteract this problem by assigning a small constant derivative to all values smaller than zero and for a scalar $\alpha$ is given by \[ l(x) = \max\left\{0, x\right\} + \alpha \min \left\{0, x\right\}. \] In Figure~\ref{fig:activation} visualizations of these functions are given. %In order to illustrate these functions plots of them are given in Figure~\ref{fig:activation}. \begin{figure} \begin{tikzpicture}[x=1.5cm, y=1.5cm, >=stealth] \tikzset{myptr/.style={decoration={markings,mark=at position 1 with % {\arrow[scale=1.5,>=stealth]{>}}},postaction={decorate}}} \node [circle, draw, fill=black, inner sep = 0pt, minimum size = 1.5mm, left] (i_1) at (0, 2.5) {}; \node [align=left, left] at (-0.125, 2.5) {\(i_1\)}; \node [circle, draw, fill=black, inner sep = 0pt, minimum size = 1.5mm] (i_2) at (0, 1.25) {}; \node [align=left, left] at (-0.125, 1.25) {\(i_2\)}; \node [neuron missing] (i_3) at (0, 0) {}; \node [circle, draw, fill=black, inner sep = 0pt, minimum size = 1.5mm] (i_4) at (0, -1.25) {}; \node [align=left, left] at (-0.125, -1.25) {\(i_m\)}; \draw[decoration={calligraphic brace,amplitude=5pt, mirror}, decorate, line width=1.25pt] (-0.6,2.7) -- (-0.6,-1.45) node [black, midway, xshift=-0.6cm, left] {Inputs}; \node [align = center, above] at (1.25, 3) {Synaptic\\weights}; \node [every neuron] (w_1) at (1.25, 2.5) {\(w_{k, 1}\)}; \node [every neuron] (w_2) at (1.25, 1.25) {\(w_{k, 2}\)}; \node [neuron missing] (w_3) at (1.25, 0) {}; \node [every neuron] (w_4) at (1.25, -1.25) {\(w_{k, m}\)}; \node [circle, draw] (sig) at (3, 0.625) {\Large\(\sum\)}; \node [align = center, below] at (3, 0) {Summing \\junction}; \node [draw, minimum size = 1.25cm] (act) at (4.5, 0.625) {\(\sigma(.)\)}; \node [align = center, above] at (4.5, 1.25) {Activation \\function}; \node [circle, draw, fill=black, inner sep = 0pt, minimum size = 1.5mm] (b) at (3, 2.5) {}; \node [align = center, above] at (3, 2.75) {Bias \\\(b_k\)}; \node [align = center] (out) at (6, 0.625) {Output \\\(o_k\)}; \draw [myptr] (i_1) -- (w_1); \draw [myptr] (i_2) -- (w_2); \draw [myptr] (i_4) -- (w_4); \draw [myptr] (w_1) -- (sig); \draw [myptr] (w_2) -- (sig); \draw [myptr] (w_4) -- (sig); \draw [myptr] (b) -- (sig); \draw [myptr] (sig) -- (act); \draw [myptr] (act) -- (out); % \foreach \m [count=\y] in {1,2,missing,3,4} % \node [every neuron/.try, neuron \m/.try ] (hidden-\m) at (1.25,3.25-\y*1.25) {\(w_{k,\y}\)}; % \foreach \m [count=\y] in {1} % \node [every neuron/.try, neuron \m/.try ] (output-\m) at (2.5,0.5-\y) {}; % \foreach \l [count=\i] in {1} % \draw [<-] (input-\i) -- ++(-1,0) % node [above, midway] {$x$}; % \foreach \l [count=\i] in {1,2,n-1,n} % \node [above] at (hidden-\i.north) {$\mathcal{N}_{\l}$}; % \foreach \l [count=\i] in {1,n_l} % \node [above] at (output-\i.north) {}; % \foreach \l [count=\i] in {1} % \draw [->] (output-\i) -- ++(1,0) % node [above, midway] {$y$}; % \foreach \i in {1} % \foreach \j in {1,2,...,3,4} % \draw [->] (input-\i) -- (hidden-\j); % \foreach \i in {1,2,...,3,4} % \foreach \j in {1} % \draw [->] (hidden-\i) -- (output-\j); \end{tikzpicture} \caption[Structure of a Single Neuron]{Structure of a single neuron.} \label{fig:neuron} \end{figure} \begin{figure} \centering \begin{subfigure}{.45\linewidth} \centering \begin{tikzpicture} \begin{axis}[enlargelimits=false, ymin=0, ymax = 1, width=\textwidth] \addplot [domain=-5:5, samples=101,unbounded coords=jump]{1/(1+exp(-x)}; \end{axis} \end{tikzpicture} \caption{Standard Logistic Function} \end{subfigure} \begin{subfigure}{.45\linewidth} \centering \begin{tikzpicture} \begin{axis}[enlargelimits=false, width=\textwidth] \addplot[domain=-5:5, samples=100]{tanh(x)}; \end{axis} \end{tikzpicture} \caption{Tangens Hyperbolicus} \end{subfigure} \begin{subfigure}{.45\linewidth} \centering \begin{tikzpicture} \begin{axis}[enlargelimits=false, width=\textwidth, ytick={0,2,4},yticklabels={\hphantom{4.}0,2,4}, ymin=-1] \addplot[domain=-5:5, samples=100]{max(0,x)}; \end{axis} \end{tikzpicture} \caption{ReLU} \end{subfigure} \begin{subfigure}{.45\linewidth} \centering \begin{tikzpicture} \begin{axis}[enlargelimits=false, width=\textwidth, ymin=-1, ytick={0,2,4},yticklabels={$\hphantom{-5.}0$,2,4}] \addplot[domain=-5:5, samples=100]{max(0,x)+ 0.1*min(0,x)}; \end{axis} \end{tikzpicture} \caption{Leaky ReLU, $\alpha = 0.1$} \end{subfigure} \caption[Plots of the Activation Functions]{Plots of the activation functions.} \label{fig:activation} \end{figure} \clearpage \subsection{Training Neural Networks} As neural networks are parametric models we need to fit the parameters to the input data to get meaningful predictions from the network. In order to accomplish this we need to discuss how we interpret the output of the neural network and assess the quality of predictions. % After a neural network model is designed, like most statistical models % it has to be fit to the data. In the machine learning context this is % often called ``training'' as due to the complexity and amount of % variables in these models they are fitted iteratively to the data, % ``learing'' the properties of the data better with each iteration. % There are two main categories of machine learning models, being % supervised and unsupervised learners. Unsupervised learners learn % structure in the data without guidance form outside (as labeling data % beforehand for training) popular examples of this are clustering % algorithms\todo{quelle}. Supervised learners on the other hand are as % the name suggest supervised during learning. This generally amounts to % using data with the expected response (label) attached to each % data-point in fitting the model, where usually some distance between % the model output and the labels is minimized. \subsubsection{Nonlinearity in the Last Layer} Given the nature of the neural net, the outputs of the last layer are real numbers. For regression tasks, this is desirable, for classification problems however some transformations might be necessary. As the goal in the latter is to predict a certain class or classes for an object, the output needs to be of a form that allows this interpretation. Commonly the nodes in the output layer each correspond to a class and the class chosen as prediction is the one with the highest value at the corresponding output node. This can be modeled as a transformation of the output vector $o \in \mathbb{R}^n$ into a one-hot vector \[ \text{pred}_i = \begin{cases} 1,& \text{if } o_i = \max_j o_j \\ 0,& \text{else}. \end{cases} \] This however makes training the model with gradient-based methods impossible, as the derivative of the transformation is either zero or undefined. An continuous transformation that is close to argmax is given by softmax \begin{equation} \text{softmax}(o)_i = \frac{e^{o_i}}{\sum_j e^{o_j}}. \label{eq:softmax} \end{equation} The softmax function transforms the realm of the output to the interval $[0,1]$ and the individual values sum to one, thus the output can be interpreted as a probability for each class conditioned on the input. Additionally, to being differentiable this allows to evaluate the certainty of a prediction, rather than just whether it is accurate. A similar effect is obtained when for a binary or two-class problem the sigmoid function \[ f(x) = \frac{1}{1 + e^{-x}} \] is used and the output $f(x)$ is interpreted as the probability for the first class and $1-f(x)$ for the second class. % Another property that makes softmax attractive is the invariance to addition % \[ % \text{sofmax}(o) = \text{softmax}(o + c % \] % In order to properly interpret the output of a neural network and % training it, depending on the problem it might be advantageous to % transform the output form the last layer. Given the nature of the % neural network the value at each output node is a real number. This is % desirable for applications where the desired output is a real numbered % vector (e.g. steering inputs for a autonomous car), however for % classification problems it is desirable to transform this % output. Often classification problems are modeled in such a way that % each output node corresponds to a class. Then the output vector needs % to be normalized in order to give a prediction. The naive approach is % to transform the output vector $o$ into a one-hot vector $p$ % corresponding to a $0$ % entry for all classes except one, which is the predicted class. % \[ % p_i = % \begin{cases} % 1,& i < j, \forall i,j \in \text{arg}\max o_i, \\ % 0,& \text{else.} % \end{cases} % \]\todo{besser formulieren} % However this imposes difficulties in training the network as with this % addition the model is no longer differentiable which imitates the % ways the model can be trained. Additionally information about the % ``certainty'' for each class in the prediction gets lost. A popular % way to circumvent this problem is to normalize the output vector is % such a way that the entries add up to one, this allows for the % interpretation of probabilities assigned to each class. \clearpage \subsubsection{Error Measurement} In order to train the network we need to be able to assess the quality of predictions using some error measure. The choice of the error function is highly dependent on the type of problem. For regression problems, a commonly used error measure is the mean squared error (MSE) which for a function $f$ and data $(x_i,y_i), i \in \left\{1,\dots,n\right\}$ is given by \[ MSE(f) = \frac{1}{n} \sum_i^n \left(f(x_i) - y_i\right)^2. \] However, depending on the problem error measures with different properties might be needed. For example in some contexts it is required to consider a proportional rather than absolute error. As discussed above the output of a neural network for a classification problem can be interpreted as a probability distribution over the classes conditioned on the input. In this case, it is desirable to use error functions designed to compare probability distributions. A widespread error function for this use case is the categorical cross entropy (\textcite{PRML}), which for two discrete distributions $p, q$ with the same realm $C$ is given by \[ H(p, q) = \sum_{c \in C} p(c) \ln\left(\frac{1}{q(c)}\right), \] comparing $q$ to a target density $p$. For a data set $(x_i,y_i), i \in \left\{1,\dots,n\right\}$ where each $y_{i,c}$ corresponds to the probability of class $c$ given $x_i$ and a predictor $f$ we get the loss function \begin{equation} CE(f) = \sum_{i=1}^n H(y_i, f(x_i)). \label{eq:cross_entropy} \end{equation} % \todo{Den satz einbauen} % -Maximum Likelihood % -Ableitung mit softmax pseudo linear -> fast improvemtns possible \subsubsection{Gradient Descent Algorithm} Trying to find the optimal parameter for fitting the model to the data can be a hard problem. Given the complex nature of a neural network with many layers and neurons, it is hard to predict the impact of single parameters on the accuracy of the output. Thus using numeric optimization algorithms is the only feasible way to fit the model. An attractive algorithm for training neural networks is gradient descent. Here all parameters are initialized with certain values (often random or close to zero) and then iteratively updated. The updates are made in the direction of the gradient regarding the error with a step size $\gamma$ until a specified stopping criterion is hit. % This mostly either being a fixed % number of iterations or a desired upper limit for the error measure. % For a function $f_\theta$ with parameters $\theta \in \mathbb{R}^n$ % and a error function $L(f_\theta)$ the gradient descent algorithm is % given in \ref{alg:gd}. \begin{algorithm}[H] \SetAlgoLined \KwInput{function $f_\theta$ with parameters $\theta \in \mathbb{R}^n$ \newline step size $\gamma$} initialize $\theta^0$\; $i \leftarrow 1$\; \While{While termination condition is not met}{ $\nabla \leftarrow \frac{\mathrm{d}f_\theta}{\mathrm{d} \theta}\vert_{\theta^{i-1}}$\; $\theta^i \leftarrow \theta^{i-1} - \gamma \nabla $\; $i \leftarrow i +1$\; } \caption{Gradient Descent} \label{alg:gd} \end{algorithm} The algorithm for gradient descent is given in Algorithm~\ref{alg:gd}. In the context of fitting a neural network $f_\theta$ corresponds to an error measurement of a neural network $\mathcal{NN}_{\theta}$ where $\theta$ is a vector containing all the weights and biases of the network. As can be seen, this requires computing the derivative of the network with regard to each variable. With the number of variables getting large in networks with multiple layers of high neuron count naively computing the derivatives can get quite memory and computational expensive. By using the chain rule and exploiting the layered structure we can compute the parameter update much more efficiently. This practice is called backpropagation and was introduced for use in neural networks by \textcite{backprop}. The algorithm for one data point is given in Algorithm~\ref{alg:backprop}, but for all error functions that are sums of errors for single data points (MSE, cross entropy) backpropagation works analogously for larger training data. % \subsubsection{Backpropagation} % As with an increasing amount of layers the derivative of a loss % function with respect to a certain variable becomes more intensive to % compute there have been efforts in increasing the efficiency of % computing these derivatives. Today the BACKPROPAGATION algorithm is % widely used to compute the derivatives needed for the optimization % algorithms. Here instead of naively calculating the derivative for % each variable, the chain rule is used in order to compute derivatives % for each layer from output layer towards the first layer while only % needing to .... \begin{algorithm}[H] \SetAlgoLined \KwInput{Inputs $o_0$, neural network with $L$ hidden layers, weights $w$, and biases $b$ for $n_l$ nodes as well as an activation function $\sigma_l$ in layer $l$ and loss function $\tilde{L}$.} Forward Propagation: \For{$l \in \left\{1, \dots, L+1\right\}$}{ Compute values for layer $l$: $z_{l,k} \leftarrow b_{l,k} + w_{l,k}^{\mathrm{T}} o_{l-1}, k \in \left\{1,\dots,n_l\right\}$\; $o_{l,k} \leftarrow \sigma_l(z_{l,k}), k \in \left\{1,\dots,n_l\right\}$ \; } Calculate derivative for output layer: $\delta_{L+1, k} \leftarrow \frac{\partial\tilde{L}(o_{L+1})}{\partial o_{L+1,k}} \sigma_{L+1}'(z_{L+1,k})$\; Back propagate the error: \For{$l \in \left\{L,\dots,1\right\}$}{ $\delta_{l,k} \leftarrow w_{l+1,k}^{\mathrm{T}} \delta_{l+1} \sigma_{l}'(z_{l,k}), k=1,\dots,n_k$ } Calculate gradients: $\frac{\partial\tilde{L}}{\partial w_{l,k,j}} = \delta_{l,k}o_{l-1,j}$, $\frac{\partial\tilde{L}}{\partial b_{l,k}} = \delta_{l,k}$\; \caption{Backpropagation for one data point} \label{alg:backprop} \end{algorithm} %%% Local Variables: %%% mode: latex %%% TeX-master: "main" %%% End: