Find a topology by reinforcement learning. They use REINFORCE from [Williams 1992](http://www.shortscience.org/paper?bibtexKey=Williams:92).


## Ideas

* Structure and connectivity of a Neural Network can be represented by a variable-length string.
* The RNN controller in Neural Architecture Search is auto-regressive, which means it predicts hyperparameters one a time, conditioned on previous predictions
* policy gradient method to maximize the expected accuracy of the sampled architectures
* In our experiments, the process of generating an architecture stops if the number of layers exceeds
a certain value.

## Evaluation

* Computer Vision - **CIFAR-10**: 3.65% error (State of the art are Dense-Nets with 3.46% error)
* Language - **Penn Treebank**: a test set perplexity of 62.4 (3.6 perplexity better than the previous state-of-the-art)

They had a Control Experiment "Comparison against Random Search" in which they showed that they are much better than a random exploration of the data. However, the paper lacks details how exactly the random search was implemented.

## Related Work

* [Designing Neural Network Architectures using Reinforcement Learning](https://arxiv.org/pdf/1611.02167.pdf) ([summary](http://www.shortscience.org/paper?bibtexKey=journals/corr/1611.02167))

## Terms

* Classification: Assign one label to one image
* Localization: Many object, there might be multiple instances of the same class.
* Detection: One big dominant object which has to be found and to be classified. Pretty much first classification and then finding a bounding box for the class within the image

## Evaluation

* ILSVRC2013, localization task
* ILSVRC2013, detection task
* ILSVRC2013, classification task

## Implementations

* https://github.com/sermanet/OverFeat

They introduce the concept of counting in images by predicting a density map. Their training only requires dot annotations on the center of objects. Each dot is expanded to a gaussian to form a density. A model is trained to predict this density and then the total count is recovered by integrating over the resulting density map.

They create a function to produce the density based on quantized dense SIFT features \cite{lowe03distinctive} from every pixel in the image. A simple version of the definition of $F$ is shown below. Each pixel becomes an $x_p$ vector which is used to train and model to implement the function $F$.

$$\forall p \in I, \hspace{10pt } F(p|w) = wx_p $$

The obtained quantized dense SIFT features using the [VLFEAT](http://www.vlfeat.org/overview/dsift.html) library. The significant part of the code is shown below:

```
im = imread(['data/' num2str(j, '%03d') 'cell.png']);
im = im(:,:,3); %using the blue channel to compute data

disp('Computing dense SIFT...');
[f d] = vl_dsift(single(im)); %computing the dense sift descriptors centered at each pixel
%estimating the crop parameters where SIFTs were not computed:
minf = floor(min(f,[],2));
maxf = floor(max(f,[],2));
minx = minf(1);
miny = minf(2);
maxx = maxf(1);
maxy = maxf(2);   

%simple quantized dense SIFT, each image is encoded as MxNx1 numbers of
%dictionary entries numbers with weight 1 (see the NIPS paper):
disp('Quantizing SIFTs...');
features{j} = vl_ikmeanspush(uint8(d),Dict);
features{j} = reshape(features{j}, maxy-miny+1, maxx-minx+1);
weights{j} = ones(size(features{j}));   
```

The benchmark their algorithm using "Bacterial cells in fluorescence-light microscopy images". The heatmap to the right shows the predicted density.

https://i.imgur.com/Vz463nu.png

The evaluation is performed by training on $N$ images (with $N$ in a validation set) and the testing on 100 randomly picked images in a hold out set. They show that using more images results in less variance and higher accuracy.

https://i.imgur.com/hihfC8V.png

Paper website: http://www.robots.ox.ac.uk/~vgg/research/counting/index_org.html

## Headline Summary
The problem of vanishing or exploding gradients when training recurrent neural networks can be partially overcome by enforcing an orthogonality constraint on the weight matrices between consecutive hidden states. This paper explores the trade-off between enforced orthogonality and the rate of learning by slowly increasing the extent to which the weight matrices are allowed to deviate from orthogonality.  They find that a hard orthogonality constraint can be too restrictive and perseveres gradients at the cost of slowing learning.

### Why orthogonal matrices are likely to help with exploding gradients

For a  neural network  with N hidden layers we can write the gradient of the loss wrt to the weight matrix between hidden states $W_i$ as: 

$ \frac{\partial L}{\partial W_i} =  \frac{\partial a_i}{\partial w_i} \prod_j^N (\frac{\partial h_i}{\partial a_i} \frac{\partial a_i}{\partial h_i}) \frac{\partial L}{\partial a_{N+1}} = \frac{\partial a_i}{\partial w_i} \prod_j^N (D_i W_{j+1}) \frac{\partial L}{\partial a_{N+1}}$

where L is the loss function and D is the jacobian of the activation function. It's in this long chain of products that the gradient tends to either vanish or explode. This problem is particularly bad in recurrent nets where the chain is the length of the unrolled computation graph.

The norm of the derivative $\|\frac{\partial h_i}{\partial a_i} \frac{\partial a_i}{\partial h_i} \|= \|D_i W_{j+1}\| \leq  \|D_i \| \| W_{j+1}\| \leq \lambda_D \lambda_W$ 

where $\lambda_{D/W}$ is the largest singular value of the given matrix. Its clear that if $\lambda$ is less than or greater than 1, that the norm of the gradient will grow or decay exponentially with length of the chain of products given above.

Constraining the weight matrices to be orthogonal ensures that the singular values are 1 and so perseveres the gradient norm.

### How to enforce the orthogonality constraints

The set of all orthogonal matrices from a continuos manifold known as the stiefel manifold. One way to ensure that the weight matrices remain orthogonal is to initialise them to be orthogonal and then to perform gradient optimisation on this manifold. The orthogonality of the matrix can be preserved by a Caley transformation outlined in the paper. 

In order to allow the weight  matrix to deviate slightly from the stiefel manifold, the authors took the SVD of $W = USV^T $ and parameterised the singular values. They used geodesic gradient descent to maintain the orthogonality of $U$ and $V$. The singular values were restricted to between $ 1 ^+_- m$ where  $m$ is a margin by parameterisation with a sigmoid.

### Experiment Summary

They experiment on a number of synthetic and real data-sets with elman and factorial RNNs. The synthetic tasks are the hochrieter memory and addition tasks, classifying sequential mnist and the real task is a language modelling task using the Penn Tree Bank dataset.

In the synthetic memory tasks they found that pure othogonalisation hindered performance but that a small margin away from orthogonality was better than no orthogonal constraint.

On the mnist tasks, the LSTM outperformed all other versions of simple RNNs but the simple RNNs with orthogonal constraints did quite well. Orthonal initialisation outperformed identity and glorot initialisation.

On the language modelling task with short sentences, orthogonal constraints were detrimental but on the longer sentences beneficial. They did not compare to LSTM. They also found that orthogonal initialisation was almost as good as orthogonal constraints during learning suggesting that preserving gradient flow is most important early in learning.

### My Two Cents
This paper explores an interesting approach to learning long term dependencies even with very simple RNNs. However, as theoretically appealing as the results may be, they still fail to match the memory capacities of an LSTM so for the time being it doesn't seem that there are any major practical take aways.

Convolutional Neural Fabrics (CNFs) are a construction algorithm for CNN architectures.

> Instead of aiming to select a single optimal architecture, we propose a “fabric” that embeds an exponentially large number of architectures. The fabric consists of a 3D trellis that connects response maps at different layers, scales, and channels with a sparse homogeneous local connectivity pattern.

![Image](http://i.imgur.com/wlISXgo.png)

* **Pooling**: CNFs don't use pooling. However, this might not be necessary as they use strided convolution.
* **Filter size**: All convolutions use kernel size 3.
* **Output layer**: Scale $1 \times 1$, channels = nr of classes
* **Activation function**: Rectified linear units (ReLUs) are used at all nodes.

## Evaluation

* Part Labels dataset (face images from the LFW dataset): a super-pixel accuracy of 95.6%
* MNIST: 0.33% error (see [SotA](https://martin-thoma.com/sota/#image-classification); 0.21 %)
* CIFAR10: 7.43% error (see [SotA](https://martin-thoma.com/sota/#image-classification); 2.72 %)


## What I didn't understand

* "Activations are thus a linear function over multi-dimensional neighborhoods, i.e. a four dimensional
3×3×3×3 neighborhood when processing 2D images"
* "within the first layer, channel c at scale s receives input from channels c + {−1, 0, 1} from scale s − 1": Why does the scale change? Why doesn't the  first layer receive input from the same scale?