Here the author presents a way to retrieve similar images in O(distance) time (where distance can be termed as 100 - correlation in percentage between two images), but it uses O(2^n) memory (n is the number of bits in which we are encoding the image). Therefore this approach is independent of the size of database (Though the value of 'n' is very important, it is kind of precision measure for the correlation, if we choose very small 'n' the difference between similar images to given image can't be scored efficiently, while if we use very large 'n' the semantic similarity won't be captured efficiently enough).
(But this is only hashing, what is peculiar about this paper? It uses semantic hashing.)

For all the images, they are fed to autoencoder as input, a code is generated as output which is used for hashing. And then for the query image, again a code is generated and k-nearest images are retrieved from the output space.

But what is autoencoder? It is an artificial neural network with layers which are not intra-connected but inter-connected. They are comprised of two parts: encoder and decoder.

In the paper n is 28 that means the autoencoder will have 28 units in the middle layer.

*Training:*
1. The encoder training is done greedily one by one (layer by layer) using the way Restricted Boltzmann Machines are trained.
2. Then the decoder is just the inverse of the encoder layer (*Unsymmetrical auto-encoders generally give poor results.)
3. And then they are fine tuned using back-propagation, using the input image itself for calculating the loss.
(*Due to huge number of weights, the back-propagation training converges very slowly).

In short the encoder transforms the high dimensional input to low dimensional output. 
And then the decoder represents it back to high dimensional space.

In the paper this low dimensional output has been used as the code representation for the input image. (Note that these are rounded so that they are binary.) And these capture the semantic content of the image. The author has also written that this approach wont be useful if applied to words with respect to documents as words w.r.t. documents are much more semantically meaningful than pixels w.r.t. images.

Then they have used one more thing to tackle translation related variance. They have taken 81 patches of each of the image (regularly spaced patches), and have applied the above mentioned algorithm to compute the hashes. (*It is a kind of convolution except for the fact that we are not summing anything, just iterating over the bags to find their representation. It won't be much effective for tackling rotational variance.)

In the array of size 2^28, for the images whose code comes to be `a1,a2..a28` the value of `a1,a2..a28` is computed in decimal representation as 'i' and the image is stored at index 'i'.

Now for a query image, it is broken into 81 overlapping patches which are fed to the network and its code is computed. Then all the images at indexes whose difference is less than 3 bits are returned and given a score based on difference in bits. And then scores are summed for each of the image and then images are returned as per descending order of score.

The author has used two layer searching, where in first layer for the given input image, the output images are returned using the 28-bit codes, then the 256 bit code of input image and the previously returned output images are compared and based on the 256-bit codes a refined order is returned.

Though I recommend people to study A Practical Guide to Training Restricted Boltzmann Machines for a better understanding of the learning used in the training part above.

  * The paper describes a method to separate content and style from each other in an image.
  * The style can then be transfered to a new image.
  * Examples:
    * Let a photograph look like a painting of van Gogh.
    * Improve a dark beach photo by taking the style from a sunny beach photo.

### How
  * They use the pretrained 19-layer VGG net as their base network.
  * They assume that two images are provided: One with the *content*, one with the desired *style*.
  * They feed the content image through the VGG net and extract the activations of the last convolutional layer. These activations are called the *content representation*.
  * They feed the style image through the VGG net and extract the activations of all convolutional layers. They transform each layer to a *Gram Matrix* representation. These Gram Matrices are called the *style representation*.
  * How to calculate a *Gram Matrix*:
    * Take the activations of a layer. That layer will contain some convolution filters (e.g. 128), each one having its own activations.
    * Convert each filter's activations to a (1-dimensional) vector.
    * Pick all pairs of filters. Calculate the scalar product of both filter's vectors.
    * Add the scalar product result as an entry to a matrix of size `#filters x #filters` (e.g. 128x128).
    * Repeat that for every pair to get the Gram Matrix.
    * The Gram Matrix roughly represents the *texture* of the image.
  * Now you have the content representation (activations of a layer) and the style representation (Gram Matrices).
  * Create a new image of the size of the content image. Fill it with random white noise.
  * Feed that image through VGG to get its content representation and style representation. (This step will be repeated many times during the image creation.)
  * Make changes to the new image using gradient descent to optimize a loss function.
    * The loss function has two components:
      * The mean squared error between the new image's content representation and the previously extracted content representation.
      * The mean squared error between the new image's style representation and the previously extracted style representation.
    * Add up both components to get the total loss.
    * Give both components a weight to alter for more/less style matching (at the expense of content matching).


![Examples](https://raw.githubusercontent.com/aleju/papers/master/neural-nets/images/A_Neural_Algorithm_for_Artistic_Style__examples.jpg?raw=true "Examples")

*One example input image with different styles added to it.*

-------------------------

### Rough chapter-wise notes

* Page 1
  * A painted image can be decomposed in its content and its artistic style.
  * Here they use a neural network to separate content and style from each other (and to apply that style to an existing image).

* Page 2
  * Representations get more abstract as you go deeper in networks, hence they should more resemble the actual content (as opposed to the artistic style).
  * They call the feature responses in higher layers *content representation*.
  * To capture style information, they use a method that was originally designed to capture texture information.
  * They somehow build a feature space on top of the existing one, that is somehow dependent on correlations of features. That leads to a "stationary" (?) and multi-scale representation of the style.

* Page 3
  * They use VGG as their base CNN.

* Page 4
  * Based on the extracted style features, they can generate a new image, which has equal activations in these style features.
  * The new image should match the style (texture, color, localized structures) of the artistic image.
  * The style features become more and more abtstract with higher layers. They call that multi-scale the *style representation*.
  * The key contribution of the paper is a method to separate style and content representation from each other.
  * These representations can then be used to change the style of an existing image (by changing it so that its content representation stays the same, but its style representation matches the artwork).

* Page 6
  * The generated images look most appealing if all features from the style representation are used. (The lower layers tend to reflect small features, the higher layers tend to reflect larger features.)
  * Content and style can't be separated perfectly.
  * Their loss function has two terms, one for content matching and one for style matching.
  * The terms can be increased/decreased to match content or style more.

* Page 8
  * Previous techniques work only on limited or simple domains or used non-parametric approaches (see non-photorealistic rendering).
  * Previously neural networks have been used to classify the time period of paintings (based on their style).
  * They argue that separating content from style might be useful and many other domains (other than transfering style of paintings to images).

* Page 9
  * The style representation is gathered by measuring correlations between activations of neurons.
  * They argue that this is somehow similar to what "complex cells" in the primary visual system (V1) do.
  * They note that deep convnets seem to automatically learn to separate content from style, probably because it is helpful for style-invariant classification.

* Page 9, Methods
  * They use the 19 layer VGG net as their basis.
  * They use only its convolutional layers, not the linear ones.
  * They use average pooling instead of max pooling, as that produced slightly better results.

* Page 10, Methods
  * The information about the image that is contained in layers can be visualized. To do that, extract the features of a layer as the labels, then start with a white noise image and change it via gradient descent until the generated features have minimal distance (MSE) to the extracted features.
  * The build a style representation by calculating Gram Matrices for each layer.

* Page 11, Methods
  * The Gram Matrix is generated in the following way:
    * Convert each filter of a convolutional layer to a 1-dimensional vector.
    * For a pair of filters i, j calculate the value in the Gram Matrix by calculating the scalar product of the two vectors of the filters.
    * Do that for every pair of filters, generating a matrix of size #filters x #filters. That is the Gram Matrix.
  * Again, a white noise image can be changed with gradient descent to match the style of a given image (i.e. minimize MSE between two Gram Matrices).
  * That can be extended to match the style of several layers by measuring the MSE of the Gram Matrices of each layer and giving each layer a weighting.

* Page 12, Methods
  * To transfer the style of a painting to an existing image, proceed as follows:
    * Start with a white noise image.
    * Optimize that image with gradient descent so that it minimizes both the content loss (relative to the image) and the style loss (relative to the painting).
    * Each distance (content, style) can be weighted to have more or less influence on the loss function.

Sinha et al. introduce a variant of adversarial training based on distributional robust optimization. I strongly recommend reading the paper for understanding the introduced theoretical framework. The authors also provide guarantees on the obtained adversarial loss – and show experimentally that this guarantee is a realistic indicator. The adversarial training variant itself follows the general strategy of training on adversarially perturbed training samples in a min-max framework. In each iteration, an attacker crafts an adversarial examples which the network is trained on. In a nutshell, their approach differs from previous ones (apart from the theoretical framework) in the used attacker. Specifically, their attacker optimizes

$\arg\max_z l(\theta, z) - \gamma \|z – z^t\|_p^2$

where $z^t$ is a training sample chosen randomly during training.

On a side note, I also recommend reading the reviews of this paper: https://openreview.net/forum?id=Hk6kPgZA-

Also view this summary at [davidstutz.de](https://davidstutz.de/category/reading/).

Lee et al. propose a regularizer to increase the size of linear regions of rectified deep networks around training and test points. Specifically, they assume piece-wise linear networks, in its most simplistic form consisting of linear layers (fully connected layers, convolutional layers) and ReLU activation functions. In these networks, linear regions are determined by activation patterns, i.e., a pattern indicating which neurons have value greater than zero. Then, the goal is to compute, and later to increase, the size $\epsilon$ such that the $L_p$-ball of radius $\epsilon$ around a sample $x$, denoted $B_{\epsilon,p}(x)$ is contained within one linear region (corresponding to one activation pattern). Formally, letting $S(x)$ denote the set of feasible inputs $x$ for a given activation pattern, the task is to determine

$\hat{\epsilon}_{x,p} = \max_{\epsilon \geq 0, B_{\epsilon,p}(x) \subset S(x)} \epsilon$.

For $p = 1, 2, \infty$, the authors show how $\hat{\epsilon}_{x,p}$ can be computed efficiently. For $p = 2$, for example, it results in

$\hat{\epsilon}_{x,p} = \min_{(i,j) \in I} \frac{|z_j^i|}{\|\nabla_x z_j^i\|_2}$.

Here, $z_j^i$ corresponds to the $j$th neuron in the $i$th layer of a multi-layer perceptron with ReLU activations; and $I$ contains all the indices of hidden neurons. This analytical form can then used to add a regularizer to encourage the network to learn larger linear regions:

$\min_\theta \sum_{(x,y) \in D} \left[\mathcal{L}(f_\theta(x), y) - \lambda \min_{(i,j) \in I} \frac{|z_j^i|}{\|\nabla_x z_j^i\|_2}\right]$

where $f_\theta$ is the neural network with paramters $\theta$. In the remainder of the paper, the authors propose a relaxed version of this training procedure that resembles a max-margin formulation and discuss efficient computation of the involved derivatives $\nabla_x z_j^i$ without too many additional forward/backward passes.

https://i.imgur.com/jSc9zbw.jpg
Figure 1: Visualization of locally linear regions for three different models on toy 2D data.

On toy data and datasets such as MNIST and CalTech-256, it is shown that the training procedure is effective in the sense that larger linear regions around training and test points are learned. For example, on a 2D toy dataset, Figure 1 visualizes the linear regions for the optimal regularizer as well as the proposed relaxed version.

Also find this summary at [davidstutz.de](https://davidstutz.de/category/reading/).

## General stuff about face recognition

Face recognition has 4 main tasks:

* **Face detection**: Given an image, draw a rectangle around every face
* **Face alignment**: Transform a face to be in a canonical pose
* **Face representation**: Find a representation of a face which is suitable for follow-up tasks (small size, computationally cheap to compare, invariant to irrelevant changes)
* **Face verification**: Images of two faces are given. Decide if it is the same person or not.

The face verification task is sometimes (more simply) a face classification task (given a face, decide which of a fixed set of people it is).

Datasets being used are:

* **LFW** (Labeled Faces in the Wild): 97.35% accuracy; 13 323 web photos of 5 749 celebrities
* **YTF** (YouTube Faces): 3425 YouTube videos of 1 595 subjects
* **SFC** (Social Face Classification): 4.4 million labeled faces from 4030 people, each 800 to 1200 faces
* **USF** (Human-ID database): 3D scans of faces

## Ideas in this paper

This paper deals with face alignment and face representation.

**Face Alignment**

They made an average face with the USF dataset. Then, for each new face, they apply the following procedure:

* Find 6 points in a face (2 eyes, 1 nose tip, 2 corners of the lip, 1 middle point of the bottom lip)
* Crop according to those
* Find 67 points in the face / apply them to a normalized 3D model of a face
* Transform (=align) face to a normalized position

**Representation**

Train a neural network on 152x152 images of faces to classify 4030 celebrities. Remove the softmax output layer and use the output of the second-last layer as the transformed representation.

The network is:

* C1 (convolution): 32 filters of size $11 \times 11 \times 3$ (RGB-channels) (returns $142\times 142$ "images")
* M2 (max pooling): $3 \times 3$, stride of 2  (returns $71\times 71$ "images")
* C3 (convolution): 16 filters of size $9 \times 9 \times 16$ (returns $63\times 63$ "images")
* L4 (locally connected): $16\times9\times9\times16$ (returns $55\times 55$ "images")
* L5 (locally connected): $16\times7\times7\times16$ (returns $25\times 25$ "images")
* L6 (locally connected): $16\times5\times5\times16$ (returns $21\times 21$ "images")
* F7 (fully connected): ReLU, 4096 units
* F8 (fully connected): softmax layer with 4030 output neurons

The training was done with:

* Stochastic Gradient Descent (SGD)
* Momentum of 0.9
* Performance scheduling (LR starting at 0.01, ending at 0.0001)
* Weight initialization: $w \sim \mathcal{N}(\mu=0, \sigma=0.01)$, $b = 0.5$
* ~15 epochs ($\approx$ 3 days) of training


## Evaluation results

* **Quality**:
  * 97.35% accuracy (or mean accuracy?) with an Ensemble of DNNs for LFW
  * 91.4% accuracy with a single network on YTF
* **Speed**: DeepFace runs in 0.33 seconds per image (I'm not sure which size). This includes image decoding, face detection and alignment, **the** feed forward network (why only one? wasn't this the best performing Ensemble?) and final classification output

## See also

* Andrew Ng: [C4W4L03 Siamese Network](https://www.youtube.com/watch?v=6jfw8MuKwpI)