### **Keyword**: RNN, serialized model; non-differentiable backpropogarion; action detection in video 


**Abstract**: This paper uses an end-to-end model which is a recurrent neural network trained by REINFORCE to directly predict the temporal bounds of actions. The intuition is that people will observe moments in video and decide where to look to predict when an action is occurring. After training, Serena et al manage to achieve the state-of-art result by only observing 2% of the video frames.

**Model**: In order to take a long video and output all the instances of given action, they use two parts including an observation network and recurrent network. 
* observation network:  encode the visual representation of video frames.
     * input:  $ln$ -- the normalized location of the frame + frame $v_{ln}$
     * network: fc7 feature of finetuned VGG16 network
     * output: $on$ of 1024 dimension indicate time and frame feature 
     
* recurrent network: sequentially process the visual representations and decide where to watch next and whether to emit detection.
##### for each timestep:
     * input:  $on$ -- the representation of the frame + previous state $h_{n-1}$
     * network: $d_n = f_d(h_n; \theta_d)$. $pn = fp(h_n,\theta_p)$,$fd$ is fc. $fp$ is fc+sigmoid  
     * output: $d_n = (s_n,e_n,c_n )$as the candidate detection, where $s_n$,$e_n$ is the start and end of the detection, $c_n$ is confidence level;  $p_n$ whether $d_n$ is a valid detection. $l_{n+1}$ where to observe next. all the parameter falls in [0,1]
https://i.imgur.com/SeFianV.png


**Training**: in order to learn the supervision annotation in long videos and handle the non-differentiable components, authors use BP to train $d_n$ while use REINFORCE to train $p_n$ and $l_{n+1}$
* for $d_n$: $L(D) = \sum_n L_{cls}(d_n) + \sum_n \sum_m 1[y_{mn} = 1] L_{loc}(d_n,g_m)$
* for $p_n,l_{n+1}$: reward $J(\theta) = \sum_{a\in A} p(a) r(a)$ p(a) is the distribution of action and r(a) is the reward for the action. so training needs to maximize this.


**Summary**:
This paper uses a serialized model which first extract the feature from each frame, then use the frame feature and previous state info to generate the next observation time, detection and detection indicator. Specifically, in order to use previous information, they use RNN to store information and use REINFORCE to train $p_n$ and $l_n$, where the goal is to maximize reward for an action sequence and use Monte-Carlo sampling to numerically calculate the gradient for high dimension function.

**questions**:
1. why  $p_n$ and $l_n$ are non-differentiable components?
2. if $p_n$ and $l_n$ are non-differentiable components indeed, how do we come up with REINFORCE to compute the gradient?
3. why don't we get $p_n$ from $p_n = f_p(h_n, \theta_p)$ directly but rather use fp as the parameter in bernoulli distribution, similar question can be applied to calculation for $l_{n+1}$ in trainning time.

 
  

I enjoyed reading this paper. However I have a problem with the core statement of the problem which is described by the following sentence. 

"However, our visual experience is not at all like this. We experience the world as fully
detailed and there is currently no scientific explanation of this."

Who says we experience the world this way? I don't feel that I do at all. Let's say I'm looking at a large picture made of random pixels each of which is white or black at random. I first perceive the fact that I am looking at something with no real information. I know there are white and black pixels everywhere but I don't actually store which are white and which are black because I see no information in it and don't think it would be useful. I can focus on any small part of it and truly record what the arrangement is. If I close my eyes I can probably remember a 3x3 block accurately enough which is only 9 bits of information. If I practice for a long while, I could probably get a somewhat larger block. But I doubt I could get much higher than a 5x5 block of pixels. 

If I look at the scene around me right now, I see my familiar living room scene. It's not random like before. Again I can focus on any part of it, say a book on my bookshelf, and read the title. And there are lots of books. I can do the same for any of them but not all of them at once. I know they are have titles but I am under no illusion that I see them all at once and record the information. I know my eye and brain is not taking a 64 Megapixel picture every second like a video recorder. 

The other things in the room that show up in my peripheral vision can be summarized easily. I know there is a piano. It's large and brown and to the left side of the room. I know there are lamps and a beer glass. I can close my eyes and answer questions about the things in the room. I've compressed the useful information into a model and ignored the rest just as a JPEG or Autoencoder reduces the size of an image but keeps most of the relevant information. Perhaps my brain has approximately memorized the whole picture at low resolution. But I'm under no illusion that I'm really seeing it all at once at high resolution. 

Whether my eyes are open or closed I have this reduced model of what I'm looking at. I know from experience that there is detail everywhere without seeing it all at once. Wherever I focus my gaze I do see the detail and so I come to believe there is indeed detail everywhere even if I can't see and store all of it at once. 

The point is that there is no scientific problem here. Our brain very likely does something like what artificial neural networks do. They identify summarizing features which characterize most things at low resolution keeping at most only a small part of the field in high focus. Our brain being active can choose to query any other part of this to get higher resolution on that part. When it does it overwrites whatever it is that we were focusing on before. 

So in summary, I think the problem arises only from a confusion between "knowing that a picture has high-resolution information everywhere" and "actually recording that information". I certainly don't see any need to propose a supernatural explanation of vision. We're only beginning to understand how the brain and other artificial neural networks process information and in the latter we are often surprised how well they can do. 

#### Introduction

* Large scale natural language understanding task - predict text values given a knowledge base.
* Accompanied by a large dataset generated using Wikipedia
* [Link to the paper](http://www.aclweb.org/anthology/P/P16/P16-1145.pdf)

#### Dataset

* WikiReading dataset built using Wikidata and Wikipedia.
* Wikidata consists of statements of the form (property, value) about different items
* 80M statements, 16M items and 884 properties.
* These statements are grouped by items to get (item, property, answer) tuples where the answer is a set of values.
* Items are further replaced by their Wikipedia documents to generate 18.58M statements of the form (document, property, answer).
* Task is to predict answer given document and property.
* Properties are divided into 2 classes:
    * **Categorical properties** - properties with a small number of possible answers. Eg gender.
    * **Relational properties** - properties with unique answers. Eg date of birth.
* This classification is done on the basis of the entropy of answer distribution.
* Properties with entropy less than 0.7 are classified as categorical properties.
* Answer distribution has a small number of very high-frequency answers (head) and a large number of answers with very small frequency (tail).
* 30% of the answers do not appear in the training set and must be inferred from the document.

#### Models

##### Answer Classification

* Consider WikiReading as classification task and treat each answer as a class label.

###### Baseline
    
* Linear model over Bag of Words (BoW) features.
* Two BoW vectors computed - one for the document and other for the property. These are concatenated into a single feature vector.

###### Neural Networks Method

* Encode property and document into a joint representation which is fed into a softmax layer.

* **Average Embeddings BoW**
    
    * Average the BoW embeddings for documents and property and concatenate to get joint representation.

* **Paragraph Vectors**
    
    * As a variant of the previous method, encode document as a paragraph vector.

* **LSTM Reader**

    * LSTM reads the property and document sequence, word-by-word, and uses the final state as joint representation.

* **Attentive Reader**

    * Use attention mechanism to focus on relevant parts of the document for a given property.

* **Memory Networks**

    * Maps a property p and list of sentences x<sub>1</sub>, x<sub>2</sub>, ...x<sub>n</sub> in a joint representation by attention over the sentences in the document.

##### Answer Extraction

* For relational properties, it makes more sense to model the problem as information extraction than classification.

* **RNNLabeler**
    
    * Use an RNN to read the sequence of words and estimate if a given word is part of the answer.

* **Basic SeqToSeq (Sequence to Sequence)**

    * Similar to LSTM Reader but augmented with a second RNN to decode answer as a sequence of words.

* **Placeholder SeqToSeq**
    
    * Extends Basic SeqToSeq to handle OOV (Out of Vocabulary) words by adding placeholders to the vocabulary.
    * OOV words in the document and answer are replaced by placeholders so that input and output sentences are a mixture of words and placeholders only.

* **Basic Character SeqToSeq**

    * Property encoder RNN reads the property, character-by-character and transforms it into a fixed length vector.
    * This becomes the initial hidden state for the second layer of a 2-layer document encoder RNN.
    * Final state of this RNN is used by answer decoder RNN to generate answer as a character sequence.

* **Character SeqToSeq with pretraining**

    * Train a character-level language model on input character sequence from the training set and use the weights to initiate the first layer of encoder and decoder.

#### Experiments

* Evaluation metric is F1 score (harmonic mean of precision and accuracy).
* All models perform well on categorical properties with neural models outperforming others.
* In the case of relational properties, SeqToSeq models have a clear edge.
* SeqToSeq models also show a great deal of balance between relational and categorical properties.
* Language model pretraining enhances the performance of character SeqToSeq approach.
* Results demonstrate that end-to-end SeqToSeq models are most promising for WikiReading like tasks.

In proteomics, a popular method to identify peptides is mass spectrometry. An experimental tandem mass spectrum consists of mass peaks that stem from fragmenting a peptide to fragment ions. 
To identify the peptide, that produced the experimental spectrum, all peptides that could produce the seen fragment ions must be analysed. Unfortunately, the space of possible peptides to search against is large.  The paper simplifies this problem by searching against a peptide database.

The approach describes a 4-step method:

- Data reduction: only the 200 most abundant peaks of the experimental spectrum are kept
- Search: peptides with a mass similar to the experimental spectrum's precursor are selected
- Scoring: the score for each selected peptide is based on the number of predicted fragment ions seen in the experimental spectrum.
- Cross-correlation: For the top 500 scoring peptides, theoretical spectra is constructed. These spectra are are evaluated by cross-correlation with the experimental spectrum. The top scoring peptide is considered the identified peptide.

Since a database of known peptides is needed for this approach, it can not be used for de-novo peptide identification, meaning identifying peptides for species where no sequenced genome or proteome is available.

## 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.