Optimal Brain Surgeon (OBS) is about pruning neural networks to minimize the amount of parameters, training time and overfitting. It is very similar to [Optimal Brain Damage](http://www.shortscience.org/paper?bibtexKey=conf/nips/CunDS89#martinthoma), but claims to choose better weights. However, it does require to compute the inverse hessian. The hessian matrix of a neural network is a $n \times n$ matrix, where $n$ is the number of parameters of the network. Typically, $n > 10^6$. This makes the approach unusable.

Normally, a Deep Convolutional Network (DCN) has a conditional probabilistic model where we have some parameterised function $f_{\theta}$, and some distribution over the targets to define the loss function (categorical for classification or Gaussian for regression). But, that conditional function is treated as a black box (probabilistically speaking, it's just fit by maximum likelihood). This paper breaks the entire network up into a number of latent factors.

The latent factors are designed to represent familiar parts of DCNs; for example, max-pooling selects from a set of activations and we can model the uncertainty in this selection with a categorical random variable. To recreate every pixel you can imagine selecting a set of paths backwards through the network to reproduce that pixel activation. That's not how their model is parameterised, all I can do is point you to the paper for the real DRMM model definition.

# Inference

The big trick of this paper is that they have designed the probabilistic model so that max-sum-product message passing (also introduced in this paper) inference equates to the forward prop in a DCN. What does that mean? Well, since the network structure is now a hierarchical probabilistic model we can hope to throw better learning algorithms at it, which is what they do.

# Learning

Using this probabilistic formulation, you can define a loss function that includes a reconstruction loss generating the image from responsibilities you can estimate during the forward pass. Then, you can have reconstruction gradients _and_ gradients wrt your target loss, so you can train semi-supervised or unsupervised but still work with what is practically a DCN.

In addition, it's possible to derive a full EM algorithm in this case, and the M-step corresponds to just solving a generalised Least Squares problem. Which means gradient-free and better principled training of neural networks.

# Experimental Results

Not all of the theory presented in this paper is covered in the experiments. They do demonstrate their method working well on MNIST and CIFAR-10 semi-supervised (SOTA with additional variational tweaks). But, there are not yet any experiments using the full EM algorithm they describe (only reporting that results _appear promising_); all experiments use gradient optimisation. They report that their network will train 2-3x faster, but only demonstrate this on MNIST (and what about variation in the chosen optimizer?).

Also, the model can be sampled from, but we don't have any visualisations of the kind of images we would get.

Here the authors present a model which projects queries and documents into a low dimensional space, where you can fetch relevant documents by computing distance, *here cosine is used*, between the query vector and the document vectors.

### Model Description

#### Word Hashing Layer
They have used bag of tri-grams for representing words(office -> #office# -> {#of, off, ffi, fic, ice, ce#}). This is able to generalize unseen words and maps morphological variation of same words to points which are close in n-gram space.

#### Context Window Vector
Then for representing a sentence they are taking a `Window Size` around a word and appending them to form a context window vector. If we take `Window Size` = 3: 

(He is going to Office -> { [vec of 'he', vec of 'is', vec of 'going'], [vec of 'is', vec of 'going', vec of 'to'], [vec of 'going', vec of 'to', vec of 'Office'] }

#### Convolutional Layer and Max-Pool layer

Run a convolutional layer over each of the context window vector (for an intuition these are local features). Max pool over the resulting features to get global features. The output dimension is taken here to be 300.

#### Semantic Layer

Use a fully connected layer and project the 300-D vector to a 128-D vector.


They have used two different networks, one for queries and other for documents. Now for each query and document (we are given labeled documents, one of them is positive and rest are negative) they compute the cosine similarity of the 128-D output vector. And then they learn the weights of convolutional filters and the fully connected layer by maximizing conditional likelihood of positive documents. 

My thinking is that they have used two different networks as their is significant difference between Query length and Document Length.
 

# Improving Word Representations via Global Context and Multiple Word Prototypes

## Introduction

* This paper pre-dated papers like Glove and Word2Vec and proposed an architecture that
    * combines local and global context while learning word embeddings to capture the word semantics.
    * learns multiple embeddings per word to account for homonymy and polysemy.
* [Link to the paper](http://www.aclweb.org/anthology/P12-1092)

## Global Context-Aware Neural Language Model

### Training Objective

* Given a word sequence *s* (local context) and a document *d* in which the sequence occurs (global context), learn word representations while learning to discriminate the last correct word in *s* from other words.
* *g(s, d)* - scoring function giving liklihood of correct sequence.
* *g(s<sup>w</sup>, d)* - scoring function giving liklihood of last word in *s* repalced by a word *w*.
* Objective - *g(s, d)* > *g(s<sup>w</sup>, d)* + 1 for any other word *w*.

### Architecture

* Two scoring components (neural networks) to capture:
    
    * Local Context
        * Map word sequence *s* into an ordered list of vectors *x = [x<sub>1</sub>, ..., x<sub>m</sub>]*.
        * *x<sub>i</sub>* - embedding corresponding to *i<sup>th</sup>* word in the sequence.
        * Compute local score *score<sub>l</sub>* by using a neural network (with one hidden layer) over *x*.
        * Preserves word order and syntactic information.
    * Global Context
        * Map document *d* to an ordered list of word embeddings, *d = (d<sub>1</sub>, ..., d<sub>k</sub>)*.
        * Compute *c*, the weighted average of all word vectors in document.
        * The paper uses *idf* score for weighting the documents.
        * *x = * concatenation of *c* and vector of the last word in *s*.
        * Compute global score *score<sub>g</sub>* by using a neural network (with two hidden layers) over *x*.
        * Similar to bag-of-words features.
    *score = score<sub>l</sub> + score<sub>g</sub>*
    * Train the weights of the hidden layers and the word embeddings.

### Multi-Prototype Neural Language Model

* Words can have different meanings in different contexts which are difficult to capture when we train only one vector per word.
* Solution - train multiple vectors per word to capture the different meanings.
* Approach
    
    * Gather all the fixed-sized context windows for all occurrences of a given word.
    * Find the context vector by performing weighted averaging of all the words in the context window.
    * Cluster the context vectors using spherical k-means.
    * Each word occurrence in the corpus is re-labeled to its associated cluster.
    * To find similarity between a pair of words *(w, w')*:
        * For each possible cluster of *i* and *j* corresponding to the words *w* and *w'*, find distance between cluster centers for *i* and *j* and weight them by the product of probabilities of *w* belonging to *i* and *w'* belonging to *j* given their respective contexts.
        * Average the value over the *k<sup>2</sup>* pairs.

## Training
    
* Dataset
  * Wikipedia corpus

* Parameters
  * 10-word windows
  * 100 hidden units
  * No weight regularization
  * 10 different word embeddings learnt for words having multiple meanings.

## Evaluation

* Dataset
  * WordSim-353 
      * 353 pairs of nouns
      * words represented without context
      * contains human similarity judgements on pair of words
  * The paper contributed a new dataset
      * captures human similarity judgements on pair of words in the context of a sentence
      * consists of verbs and adjectives along with nouns
      * for details on how the dataset is constructed, refer the paper

* Performance
  * Proposed model achieves higher correlation to human scores than models using only the local or global context.
  * Performance can be improved by removing the stop words.
  * Using multi-prototype approach (multiple vectors for the same word) benefits the model on the tasks where the context is also given.

## Comments

* This work predated the more general word embedding models like [Word2Vec](https://gist.github.com/shagunsodhani/176a283e2c158a75a0a6) and [Glove](https://gist.github.com/shagunsodhani/efea5a42d17e0fcf18374df8e3e4b3e8). While this model performs good at intrinsic evaluation tasks like word similarity, it is outperformed by the more general and recent models on downstream tasks like NER. 

Spatial Pyramid Pooling (SPP) is a technique which allows Convolutional Neural Networks (CNNs) to use input images of any size, not only $224\text{px} \times 224\text{px}$ as most architectures do. (However, there is a lower bound for the size of the input image).

## Idea

* Convolutional layers operate on any size, but fully connected layers need fixed-size inputs
* Solution:
  * Add a new SPP layer on top of the last convolutional layer, before the fully connected layer
  * Use an approach similar to bag of words (BoW), but maintain the spatial information. The BoW approach is used for text classification, where the order of the words is discarded and only the number of occurences is kept.
  * The SPP layer operates on each feature map independently.
  * The output of the SPP layer is of dimension $k \cdot M$, where $k$ is the number of feature maps the SPP layer got as input and $M$ is the number of bins.

Example: We could use spatial pyramid pooling with 21 bins:

* 1 bin which is the max of the complete feature map
* 4 bins which divide the image into 4 regions of equal size (depending on the input size) and rectangular shape. Each bin gets the max of its region.
* 16 bins which divide the image into 4 regions of equal size (depending on the input size) and rectangular shape. Each bin gets the max of its region.

## Evaluation

* Pascal VOC 2007, Caltech101: state-of-the-art, without finetuning
* ImageNet 2012: Boosts accuracy for various CNN architectures
* ImageNet Large Scale Visual Recognition Challenge (ILSVRC) 2014: Rank #2


## Code

The paper claims that the code is [here](http://research.microsoft.com/en-us/um/people/kahe/), but this seems not to be the case any more.

People have tried to implement it with Tensorflow ([1](http://stackoverflow.com/q/40913794/562769), [2](https://github.com/fchollet/keras/issues/2080), [3](https://github.com/tensorflow/tensorflow/issues/6011)), but by now no public working implementation is available.


## Related papers

* [Atrous Convolution](https://arxiv.org/abs/1606.00915)