#### Introduction

* Problem: Building an expressive, tractable and scalable image model which can be used in downstream tasks like image generation, reconstruction, compression etc.
* [Link to the paper](https://arxiv.org/abs/1601.06759)

#### Model

* Scan the image, one row at a time and one pixel at a time (within each row).
* Given the scanned content, predict the distribution over the possible values for the next pixel.
* Joint distribution over the pixel values is factorised into a product of conditional distributions thus causing the problem as a sequence problem.
* Parameters used in prediction are shared across all the pixel positions.
* Since each pixel is jointly determined by 3 values (3 colour channels), each channel may be conditioned on other channels as well.

##### Pixel as discrete value

* The conditional distributions are multinomial (with channel variable taking 1 of 256 discrete values).
* This discrete representation is simpler and easier to learn.

#### Pixel RNN

##### Row LSTM

* Undirectional layer that processed image row by row.
* Uses one-dimensional convolution (kernel of size kx1, k>=3).
* Refer image 2 in the [paper](https://arxiv.org/abs/1601.06759).
* Weight sharing in convolution ensures translation invariance of computed feature along each row.
* For LSTM, the input-to-state component is computed for the entire 2-d input map and then is masked to include only the valid context.
* For equations related to state-to-state component, refer to equation 3 in the [paper](https://arxiv.org/abs/1601.06759)

##### Diagonal BiLSTM

* Bidirectional layer that processes the image in the diagonal fashion.
* Input map skewed by offsetting each row of the image by one position with respect to the previous row.
* Refer image 3 in the [paper](https://arxiv.org/abs/1601.06759)
* For both directions, the input-to-state component is a 1 x 1 convolution while the state-to-state recurrent component is computed with column wise convolution using kernel size 2x1.
* Kernel size of 2x1 processes minimal information yielding a highly non-linear computation.
* Output map is skewed back by removing the offset positions.
* To prevent layers from seeing further pixels, the right output map is shifted down by one row and added to left output map.

##### Residual Connections

* Residual connections (or skip connections) are used to increase convergence speed and to propagate signals more explicitly.
* Refer image 4 in the [paper](https://arxiv.org/abs/1601.06759)

##### Masked Convolutions

* Masks are used to enforce certain restrictions on the connections in the network (eg when predicting values for R channel, values of B channel can not be used).
* Mask A is applied to first convolution layer and restricts connections to only those neighbouring pixels and colour channels that have already been seen.
* Mask B is applied to all subsequent input-to-state convolution transactions and allows connections from a colour channel to itself.
* Refer image 4 in the [paper](https://arxiv.org/abs/1601.06759)

##### PixelCNN

* Uses multiple convolution layers that preserve spatial resolution.
* Makes receptive field large but not unbounded.
* Mask used to avoid seeing the future context.
* Faster that PixelRNN at training or evaluation time (as convolutions can be parallelized easily).

##### Multi-Scale PixelRNN

* Composed of one unconditional PixelRNN and multiple conditional PixelRNNs.
* Unconditional network generates a smaller s x s image which is fed as input to the conditional PixelRNN. (n is a multiple of s)
* Conditional PixelRNN is a standard PixelRNN with layers biased with an upsampled version of the s x s image.
* For upsampling, a convolution network with deconvolution layers constructs an enlarged feature map of size c x n x n.
* For biasing, the c x n x n map is mapped to 4hxnxn map (using 1x1 unmasked convolution) and added to input-to-state map.

#### Training and Evaluation

* Pixel values are dequantized using real-valued noise and log likelihood of continuous and discrete models are compared.
* Update rule - RMSProp
* Batch size - 16 for MNIST and CIFAR 10 and 32(or 64) for IMAGENET.
* Residual connections are as effective as Skip connections, in fact, the 2 can be used together as well.
* PixelRNN outperforms other models for Binary MNIST and CIFAR10.
* For CIFAR10, Diagonal BiLSTM > Row LSTM > PixelCNN. This is also the order of receptive field for the 3 architectures and the observation underlines the importance of having a large receptive field.
* The paper also provides new benchmarks for generative image modelling on IMAGENET dataset.

#### Introduction

* The paper presents gradient computation based techniques to visualise image classification models.
* [Link to the paper](https://arxiv.org/abs/1312.6034)

#### Experimental Setup

* Single deep convNet trained on ILSVRC-2013 dataset (1.2M training images and 1000 classes).
* Weight layer configuration is: conv64-conv256-conv256-conv256-conv256-full4096-full4096-full1000.

#### Class Model Visualisation

* Given a learnt ConvNet and a class (of interest), start with the zero image and perform optimisation by back propagating with respect to the input image (keeping the ConvNet weights constant).
* Add the mean image (for training set) to the resulting image.
* The paper used unnormalised class scores so that optimisation focuses on increasing the score of target class and not decreasing the score of other classes.

#### Image-Specific Class Saliency Visualisation

* Given an image, class of interest, and trained ConvNet, rank the pixels of the input image based on their influence on class scores.
* Derivative of the class score with respect to image gives an estimate of the importance of different pixels for the class.
* The magnitude of derivative also indicated how much each pixel needs to be changed to improve the class score.

##### Class Saliency Extraction

* Find the derivative of the class score with respect with respect to the input image.
* This would result in one single saliency map per colour channel.
* To obtain a single saliency map, take the maximum magnitude of derivative across all colour channels.

##### Weakly Supervised Object Localisation

* The saliency map for an image provides a rough encoding of the location of the object of the class of interest. 
* Given an image and its saliency map, an object segmentation map can be computed using GraphCut colour segmentation.
* Color continuity cues are needed as saliency maps might capture only the most dominant part of the object in the image.
* This weakly supervised approach achieves 46.4% top-5 error on the test set of ILSVRC-2013.

#### Relation to Deconvolutional Networks

* DeconvNet-based reconstruction of the $n^{th}$ layer input is similar to computing the gradient of the visualised neuron activity $f$ with respect to the input layer.
* One difference is in the way RELU neurons are treated: 
    * In DeconvNet, the sign indicator (for the derivative of RELU) is computed on output reconstruction while in this paper, the sign indicator is computed on the layer input.

#### Introduction

* Introduces fastText, a simple and highly efficient approach for text classification.
* At par with deep learning models in terms of accuracy though an order of magnitude faster in performance. 
* [Link to the paper](http://arxiv.org/abs/1607.01759v3)
* [Link to code](https://github.com/facebookresearch/fastText)

#### Architecture

* Built on top of linear models with a rank constraint and a fast loss approximation.
* Start with word representations that are averaged into text representation and feed them to a linear classifier.
* Think of text representation as a hidden state that can be shared among features and classes.
* Softmax layer to obtain a probability distribution over pre-defined classes.
* High computational complexity $O(kh)$, $k$ is the number of classes and $h$ is dimension of text representation.

##### Hierarchial Softmax

* Based on Huffman Coding Tree
* Used to reduce complexity to $O(hlog(k))$
* Top T results (from the tree) can be computed efficiently $O(logT)$ using a binary heap.

##### N-gram Features

* Instead of explicitly using word order, uses a bag of n-grams to maintain efficiency without losing on accuracy.
* Uses [hashing trick](https://arxiv.org/pdf/0902.2206.pdf) to maintain fast and memory efficient mapping of the n-grams.

#### Experiments

##### Sentiment Analysis

* fastText benefits by using bigrams.
* Outperforms [char-CNN](http://arxiv.org/abs/1502.01710v5) and [char-CRNN](http://arxiv.org/abs/1602.00367v1) and performs a bit worse than [VDCNN](http://arxiv.org/abs/1606.01781v1).
* Order of magnitudes faster in terms of training time.
* Note: fastText does not use pre-trained word embeddings.

##### Tag Prediction

* fastText with bigrams outperforms [Tagspace](http://emnlp2014.org/papers/pdf/EMNLP2014194.pdf).
* fastText performs upto 600 times faster at test time.

#### Introduction

* Introduces a new global log-bilinear regression model which combines the benefits of both global matrix factorization and local context window methods.


#### Global Matrix Factorization Methods

* Decompose large matrices into low-rank approximations.
* eg - Latent Semantic Analysis (LSA)

##### Limitations

* Poor performance on word analogy task
* Frequent words contribute disproportionately high to the similarity measure.

#### Shallow, Local Context-Based Window Methods

* Learn word representations using adjacent words.
* eg - Continous bag-of-words (CBOW) model and skip-gram model.

##### Limitations

* Since they do not operate directly on the global co-occurrence counts, they can not utilise the statistics of the corpus effectively.


#### GloVe Model

* To capture the relationship between words $i$ and $j$, word vector models should use ratios of co-occurene probabilites (with other words $k$) instead of using raw probabilites themselves.
* In most general form:
     * $F(w_{i}, w_{j}, w_{k}^{~} ) = P_{ik}/P_{jk}$
* We want $F$ to encode information in the vector space (which have a linear structure), so we can restrict to the difference of $w_{i}$ and $w_{j}$
    * $F(w_{i} - w_{j}, w_{k}^{~} ) = P_{ik}/P_{jk}$
* Since right hand side is a scalar and left hand side is a vector, we take dot product of the arguments.
    * $F( (w_{i} - w_{j})^{T}, w_{k}^{~} ) = P_{ik}/P_{jk}$
* *F* should be invariant to order of the word pair $i$ and $j$.
    * $F(w_{i}^{T}w_{k}^{~}) = P_{ik}$
* Doing further simplifications and optimisations (refer paper), we get cost function, 
    * $J = \sum_{\text{over all i, j pairs in the vocabulary}}[w_{i}^{T}w_{k}^{~} + b_{i} + b_{k}^{~} - log(X_{ik})]^{2}$
    * $f$ is a weighing function.
    * $f(x) = min((x/x_{max})^{\alpha}, 1)$
    * Typical values, $x_{\max} = 100$ and $\alpha = 3/4$
    * *b* are the bias terms.

##### Complexity

* Depends on a number of non-zero elements in the input matrix.
* Upper bound by the square of vocabulary size
* Since for shallow window-based approaches, complexity depends on $|C|$ (size of the corpus), tighter bounds are needed.
* By modelling number of co-occurrences of words as power law function of frequency rank, the complexity can be shown to be proportional to $|C|^{0.8}$

#### Evaluation

##### Tasks

* Word Analogies
    * a is to b as c is to ___?
    * Both semantic and syntactic pairs
    * Find closest d to $w_{b} - w_{c} + w_{a}$ (using cosine similarity)

* Word Similarity
* Named Entity Recognition

##### Datasets

* Wikipedia Dumps - 2010 and 2014
* Gigaword5
* Combination of Gigaword5 and Wikipedia2014
* CommonCrawl
* 400,000 most frequent words considered from the corpus.

##### Hyperparameters

* Size of context window.
* Whether to distinguish left context from right context.
* $f$ - Word pairs that are $d$ words apart contribute $1/d$ to the total count.
* $xmax = 100$
* $\alpha = 3/4$
* AdaGrad update

##### Models Compared With

* Singular Value Decomposition
* Continous Bag-Of-Words
* Skip-Gram

##### Results

* Glove outperforms all other models significantly.
* Diminishing returns for vectors larger than 200 dimensions.
* Small and asymmetric context windows (context window only to the left) works better for syntactic tasks.
* Long and symmetric context windows (context window to both the sides) works better for semantic tasks.
* Syntactic task benefited from larger corpus though semantic task performed better with Wikipedia instead of Gigaword5 probably due to the comprehensiveness of Wikipedia and slightly outdated nature of Gigaword5.
* Word2vec’s performance decreases if the number of negative samples increases beyond about 10.
* For the same corpus, vocabulary, and window size GloVe consistently achieves better results, faster.

#### Introduction

* Algorithm to derive similarity between 2 nodes of a graph (or graphical model derived from any other kind of dataset).
* [Link to the paper](http://dl.acm.org/citation.cfm?id=775126)

#### SimRank

* Input: A directed graph $G = (V, E)$ where $V$ represents vertices and $E$ represents edges.
* SimRank defines similarity between 2 vertices (or nodes) $i$ and $j$ as the average of the similarity between their in-neighbours decayed by a constant factor $C$.
* Any node is maximally similar to itself (with similarity = 1).
* PageRank analyses the individual vertices of the graph with respect to the global structure, while SimRank analyses the relationship between a pair of vertices (edges).
* SimRank scores are symmetric and can be defined between all pair of vertices.
* $G^{2}$ is defined as the node pair graph such that each node in *G^{2}* corresponds to an ordered pair of nodes of $G$ and there exists an edge between node pair (a, b) and (c, d) if there exists an edge between (a, c) and (b, d).
* In $G^{2}$, similarity flows from node to node with singleton nodes (nodes of the form (a, a)) as the source of similarity.

#### Variants

##### Minimax Variant

* Defines similarity of nodes $i$ and $j$ as the minimum of maximum similarity between $i$ and any in-neighbour of $j$ and between $j$ and any in-neighbour of $i$.

#### Computing SimRank

* A naive solution can be obtained by iteration to a fixed point.
* Space complexity is $O(n^{2})$ and time complexity is $O(kn^{2}d)$ where $k$ is the number of iterations, $n$ is the number of vertices and $d$ is the average of product of indegrees of pair of vertices.
* Optimisations can be made by setting the similarity between far off nodes as 0 and considering only nearby nodes for an update.

#### Different Interpretations

##### Co-citation Score

* The first iteration of SimRank produces results same as co-citation score between a pair of vertices.
* Successive iterations improve these initial scores.

##### Random Surfer-Pairs Model

* SimRank $s(a, b)$ can be interpreted as the measure of how soon two random surfers are expected to meet at the same node if they start at nodes a and b and walk the graph backwards.
* Expected Meeting Distance (EMD) between 2 nodes a and b is the expected number of steps required before 2 surfers (starting at a and b) would meet if they walked randomly in locked step.
* Surfers are allowed to teleport with a small probability - to circumvent the infinite EMD problem.
* Expected-f Meeting Distance (EMD) - Given length l of a tour, compute f(l) (where f is a non-negative monotonic function) to bound the expected distance to a finite interval.
* Common choice for f is $f(z) = C^{z}$ where $C  \in (0, 1)$
* The SimRank score for two nodes, with parameter $C$, is the expected-f meeting distance travelling back-edges with $f(z) = C^{z}$

#### Evaluation

* Experiments on 2 datasets:
    * Corpus of scientific research papers from ResearchIndex.
    * Transcripts of undergrad students at Stanford.
* Domain specific properties used to measure similarity and compared with SimRank scores.
* Results show improvement over co-citation scores.