Deep Learning Summary

The activation function of a neuron depends on its activation value:

In this activation value it’s taken into account also the bias. The bias is $x_0$ with value -1 and the corresponding weight is $w_{j0}=1$.

The most common used activation function are:

• Sigmoid Function: continuous approximation of a step function.

  $$sigm=g_j\left(z_j\right)=\frac{1}{1+e^{-z_j}}$$

  This is between 0 and 1.

• Hyperbolic Tangent: continuous approximation of a sign function.

  $$\tanh =g_j\left(z_j\right)=\frac{e^{z_j}-e^{-z_j}}{e^{zj}+e^{-z_j}}$$

• Linear Function: the unit with linear function is called also Relu (Rectified Linear Unit).

  $$g_j\left(z_j\right)=z_j$$

• Sign Function: the usual sign function.

We can view perceptron as representing hyperplane decision surface in the n-dimensional space of instances (points). The perceptron outputs 1 for instances lying on one side of the hyperplane and -1 for instances lying on the other side. The equation for this decision hyperplane is $\overrightarrow{w}\cdot \overrightarrow{x}=0$. Some sets of positive and negative examples cannot be separated by any hyperplane. Those that can be separated are called linearly separable sets.

Perceptron can represent all the primitive boolean function AND, OR, NAND and NOR. Some boolean functions cannot be represented by a single perceptron, such as XOR function. Ability of perceptron to represent the primitive function is important because every boolean function can be represented by some network of interconnected units based on them.

The strength of a synapses increases according to the simultaneous activation of the relative input and the desired target.

In this way the next neuron learns that when the previous neuron fires, it has to fire. This is modeled with the increased strength of a synapse.

The weight change according to a delta function.

The weight’s change is applied only when the output doesn’t correspond to the target. Formally there should be ($t-o$) instead of t.

The delta function depends on:

• $\eta$: learning rate. The role of $\eta$ ($>0$) is to moderate the degree to which weights are changed at each step.

• t: target value.

• $x_i$: Input value of i-th input.

The product between the target and the i-th input selects the direction in which the weight should go. If they are both positive this means that there is a direct dependence between them, so the weight must increase.

This learning procedure can be proven to converge within a finite number of applications of the perceptron training rule to a weight vector that correctly classified all training examples, provided the training example are linearly separable and provided sufficiently small $\eta$ is used.

Hebbian Learning is not suited for multilayer perceptron. It’s difficult to know the input of hidden layers and the expected output of them because we do not know it.

The universal approximation theorem states that a feed forward neural network with a single hidden layer containing a finite number of neurons can approximate continuous function (also non linear) on compact subsets of $R^n$ with any desired non-zero error. The only assumption is that the activation function must be s-shaped.

It is not the specific choice of the activation function, but rather the multilayer feedforward architecture itself which gives neural networks the potential of being universal approximators. The output units are always assumed to be linear.

The UAT (Universal Approximation Theorem) means that reagrdless of what function we are trying to learn, we know that a large multi-layer FFNN will be able to represent this function. However we are not guaranteed that the training algorithm will be able to learn that function.

Training algorithm can fail for two reasons:

• The optimization algorithm used for training may be not able to find the value of parameters that correspond to the desired function.

• The training algorithm might choose the wrong function due to overfitting.

The no free lunch theorem shows that there no universally superior machine learning algorithm.

In summary, a feedforward network with a single layer is sufficient to represent any function, but the layer may be infeasibly large and may fail to learn and generalize correctly. In many circumstances, using deeper models can reduce the number of units required to represent the desired function and can reduce the amount of generalization error.

The perceptron rule fails to converge if the examples are not linearly separable.

The delta rule instead converges toward a best-fit approximation to the target concept.

The key idea is to use gradient descent to search the hypothesis space of possible weight vectors to find weights that best fit the training examples. This rule is important because gradient descent can serve as the basis for the backpropagation algorithm.

Learning can be summarized in this way:

Where

So we move in the opposite direction wrt the gradient of the Error function wrt the weight. In this way we try to search a local minima.

To overcome the problem of local optima we can restart the problem multiple time.

Which type of activation function should we use in a multilayer NN?

Multiple layers of cascaded linear units still produce only linear functions and we prefer networks capable of representing highly non-linear functions. What we need is a unit whose output in a non linear function of inputs but whose output is also a differentiable function of its input. One solution is the sigmoid unit, based on a smoothed, differentiable threshold function.

The backpropagation algorithm learns the weights for a multilayer network, given a network with a fixed set of units and interconnections. It employs gradient descent to attempt to minimize the squared error between the network output values and the target values for these outputs.

The goal is to approximate a target function t given a set of N observations.

We want to minimize the error E:

Where $o_n$ is the output of the net given the n-th example.

In Machine Learning we are often interested in determining the best hypothesis from some space H, given the observed data D. We demand the most probable hypothesis given the data plus any initial knowledge about the prior probabilities of the various hypothesis in H. Bayes theorem provides a way to calculate the probability of an hypothesis based on its prior probability, the probability of observing various data given the hypothesis and the observed data itself.

$P\left(h\right)$ is the prior probability of h and reflect any background knowledge we have about the chance that h is a correct hypothesis. It is the probability that h holds before seeing the training data.

If we do not have a prior knowledge we assign the same probability to each candidate.

$P\left(D\right)$ denotes the prior probability that training data D will be observed.

In Machine Learning we are interested in the probability $P\left(h|D\right)$ that h holds given the observed data. This is called posterior probability of $h$. The posterior probability reflect the influence of the training data $D$, in contrast to the prior probability $P\left(h\right)$ which is independent of D.

As one might intuitively expect, $P\left(h|D\right)$ increases with $P\left(h\right)$ and with $P\left(D|h\right)$ according to Bayes theorem. It is also reasonable to see that $P\left(h|D\right)$ decreases as $P\left(D\right)$ increases, because the more probable it is that D will be observed independent of h, the less evidence D provides in support of h.

In Machine Learning the learner considers some set of candidate hypothesis H and is interested in finding the most probable hypothesis h given the observed data D. Any such maximally hypothesis is called a maximum a posteriori (MAP).

Notice that we can remove P(D) because it’s independent from h.

If we assume every hypothesis is equally probable we obtain the likelihood estimation: $P\left(D|h\right)$. This is called maximum likelihood hypothesis:

Is the least square error function a good error function for classification?

The goal is to approximate a target function $t$ given a finite set of observation N.

We assume the target function $t_n$ being affected by a white noise, otherwise it’s possible to approximate it by simply passing through all samples.

We assume the mean of the target function being the output of the net $y_n$ because in the ML approach the hypothesis is assumed to be true:

We have to learn w in such a way to maximize the probability $P\left(t|w\right)$.

Learning as estimating parameters of distribution $t_n$. The strange thing here is that the mean is a function that depends on the current value.

Applying likelihood and loglikehood the result is that the least square error is a good choice for error function for the Noise Model and regression problems.

In case of classification problems the result is that the cross entropy function is good error function.

After having modeled the target function as a Bernulli:

When training large models with sufficient representational capacity to overfit the task, we observe that training error decreases steadily over time but validation set error begins to rise again.

When validation error increases this means we are loss generalization and we begin to overfit.

At this point is convenient to stop training and maintain the parameter setting at the point in time with the lowest validation set error. We run the algorithm for learning until the error on the validation set has not improved for some amount of time.

Early stopping is usually a good method to find out how many neurons we need in the hidden layer: compare different topologies wrt the validation error.

In the first phase of the training minimizing error is minimizing validation error. The network is learning common phenomenon between training and test.

In the second phase the net is learning something not related to the model. It is learning the noise inside the model and reducing its capability of generalization.

Cross Validation: Algorithm might be sensitive with respect to the split. It is possible to have 5 sets. Using 1 set for validation and the other for training. Train different model and take them all averaging the result.

Problem is when you do not have enough data, because you can’t split.

The technique of regularization encourages smoother network mappings by adding a penalty term to the error function to give:

Here E is one of the standard error functions and the parameter $\nu$ controls the extent to which the penalty term $\Omega$ influences the form of the solution. Training is performed by minimizing the total error function. The resulting error mapping is a compromise between fitting the data and minimizing $\Omega$.

In weight decay:

We know that to produce an over-fitted mapping with regions of large curvature requires relatively large values for weights. For small values the function is approximately linear. By using this type of regularizer the weights are encouraged to be small.

Let’s study the behavior of weights in time:

Supposing the term E is absent.

By solving this equation the function of weights in time is given by:

and so all weights decay exponentially to zero.

Bagging (bootstrap aggregation) is a technique for reducing generalization error by combining several models.

Idea: train several models separately, then have all of the models vote on the output for test examples. Strategy of model averaging. Techniques ensemble methods.

Reason is that different models will usually not make the same errors on the test set.

- Create k different independent set by sampling from the original dataset. The datasets will have some shared examples and some unique examples. This helps in having independent errors.

- Train different models

- Average all models

Result: on average the result of averaged model will be better than any of those.

Begging is this: average independent classifier.

With independent errors the resulting error of the averaged model is less than any of its member. If the error are perfectly correlated the resulting error remains the same.

Let’s suppose errors are a multivariate Gaussian with 0 mean, v variance and c covariance.

The expected squared error of the ensemble is:

So, if the error are uncorrelated ($c=0$) the expected squared error is $\frac{1}{k}v$, so it decreases linearly with the numbers of models. If the errors are perfectly correlated ($c=v$) and the expected error is only v (remains the same).

This underlie the importance of having independent errors and so the importance of having different datasets.

Dropout provides a computationally inexpensive but powerful method of regularizing a broad family of models.

Dropout can be thought of as a method of making bagging practical for ensembles of very many large neural networks. Bagging involves training multiple models and evaluating them on each test examples. This is impractical when NN are large. Dropout provides an inexpensive approximation to training and evaluating a bagged ensemble of exponentially many neural network.

Dropout trains the ensemble consisting of all subnetworks that can be formed by removing non-output units from an underlying base network.

The term dropout refers to dropping out units (hidden and visible) in a neural network. By dropping out a unit, we mean temporarily removing it from the network, along with all its incoming and outgoing connections. Applying dropout to a network is like sampling a thinned network from it. A NN with n units can be seen as a collection of $2^n$ possible thinned NNs. These networks all share weights so that the total number of parameters is still the same of one NN.

For each presentation of each training case, a new thinned network is sampled and trained. So training a NN with dropout can be seen as training a collection of thinned NNs with extensive weight sharing, where each thinned network gets trained very rarely.

At test time is used a single NN without dropout. The weights of this NN are a scaled-down version of the trained weights. If a input unit is retained with probability p at test time, the outgoing weights of that unit are multiplied by p at test time. By doing this scaling, $2^n$ networks can be combined into a single NN to be used at test time.

Convolution is an operation on two functions of a real valued argument.

In CNN the first argument (the function x) is the input while the second argument (the function w) is the kernel. The output is the feature map.

If we transfer the idea from a continuos dominion to a discrete dominion we obtain the 5.

The input is usually a multidimensional array of data and the kernel is usually a multidimensional array of parameters adapted by the learning algorithm.

Notice that the learning algorithm will learn the appropriate values of the kernel in the appropriate place.

Since the input image is a matrix, the convolution operation is 2D:

Notice how the convolution depends on two parameters i,j.

I,J are the dimensions of the input image, while M,N are dimensions of the Kernel.

Commutative property of convolution arises because we’ve flipped the Kernel relative to the input, but there is not this need in Machine Learning. So we do convolution without kernel flipping:

The convolution layer performs the following:

• A Kernel slides over input feature map.

• At each kernel position, element-wise product is computed between the kernel and the overlapped input set.

• Result is summed up and constitute the output feature map.

In a CNN each layer has a depth, in the sense that multiple filters are applied to the same image.

Each filter is responsible for extracting a particular feature of the input.

Each neuron in the hidden layer is connected to a small region of the input neuron, its receptive field. For each local receptive field there is an hidden neuron in the first hidden layer.

It’s important to notice that, even if there are multiple hidden neurons, the weights are shared across all neurons. In this way neurons extract the same features.

Convolution is fundamental for three concepts that can improve a machine learning system.

A pooling function replaces the output of the net at a certain location with a summary statistics of the nearby outputs. Example of pooling function are max-pooling or average.

Pooling helps to make the representation become approximately invariant to small translations of the input. Invariance to local translation can be a very useful property if we care more about the existence of a property (feature) instead of the exact position of it. Because pooling summarizes the response over a whole neighborhood, it is possible to use fewer pooling units than detector units.

Pooling over spatial regions produces invariance to translation, but if we pool over the outputs of separately parametrized convolutions, the features can learn which transformations to become invariant to.

Pooling progressively reduces the spatial size of the image and helps to obtain invariance wrt rotation, scaling and other transformation.

Elman network is a NN with some context units. Context units are used to memorize the previous activations of the hidden units and can be considered to function as one-step time delays.

At a specific time k, the previous activations of the hidden units at time k-1 and the current input at time k are used as inputs to the network. Theoretically an Elman network is able to model a nth-order dynamic system.

To train this net is possible to use the backpropagation through time (BTT). This is a simple algorithm based on network unfolding:

1. Perform network unfolding (using U unwrapping steps) and obtain a NN with weights depending on time. Notice that the same weight must have the same value over time.

2. Train the network like a simple feed forward NN:

   $$\frac{\delta E}{\delta w_{jb}}=\sum _u^U\frac{\delta E}{\delta w_{jb}(t-u)}$$

3. Update all the weights with the formula above. In this way the weights are constrained to be the same over time.

We need to specify the initial activity state of all hidden units: we can treat the initial states as parameters to be learned.

Recurrent Neural Network are Neural Network with cell with recurrent arcs. In practice the output of some cells depends on the previous output, in this way NN can perform sequence prediction.

In a RNN the hidden state is:

In this way the current state $h_t$ depends both on the previous state end on the current input.

In this way the output of the net depends on the current state but since it depends on the previous state it can learn sequences. The important thing here is that the self recurrent weight $W_{hh}$ does not depend on time, so it’s shared among all periods.

Like leaky units, gated RNNs are based on the idea of creating paths through time that have derivatives that neither vanish nor explode.

Leaky units did this with connection weights that were either manually chosen constants or were parameters. Gated RNNs generalize this to connection weights that may change at each time step.

Leaky units allow the network to accumulate information (such as evidence for a particular feature or category) over a long duration. However, once that information has been used, it might be useful for the neural network to forget the old state. For example, if a sequence is made of sub-sequences and we want a leaky unit to accumulate evidence inside each sub subsequence, we need a mechanism to forget the old state by setting it to zero. Instead of manually deciding when to clear the state, we want the neural network to learn to decide when to do it. This is what gated RNNs do.

We know that Elman RNN suffers of vanishing or exploding gradient. LSTM is a new architecture for RNN enforcing constant error flow through internal states of special units.

To enforce constant error flow:

This can be achieved by using identity function for $f_j$ and by setting the weight equals to 1.

The gate unit have been introduced in order to overcome the problem of weight conflict.