Official code: https://github.com/anewell/pose-hg-train

  * They suggest a new model architecture for human pose estimation (i.e. "lay a skeleton over a person").
  * Their architecture is based progressive pooling followed by progressive upsampling, creating an hourglass form.
  * Input are images showing a person's body.
  * Outputs are K heatmaps (for K body joints), with each heatmap showing the likely position of a single joint on the person (e.g. "akle", "wrist", "left hand", ...).

### How
  * *Basic building block*
    * They use residuals as their basic building block.
    * Each residual has three layers: One 1x1 convolution for dimensionality reduction (from 256 to 128 channels), a 3x3 convolution, a 1x1 convolution for dimensionality increase (back to 256).
    * Visualized:
      * ![Building Block](https://raw.githubusercontent.com/aleju/papers/master/neural-nets/images/Stacked_Hourglass_Networks_for_Human_Pose_Estimation__building_block.jpg?raw=true "Building Block")
  * *Architecture*
    * Their architecture starts with one standard 7x7 convolutions that has strides of (2, 2).
    * They use MaxPooling (2x2, strides of (2, 2)) to downsample the images/feature maps.
    * They use Nearest Neighbour upsampling (factor 2) to upsample the images/feature maps.
    * After every pooling step they add three of their basic building blocks.
    * Before each pooling step they branch off the current feature map as a minor branch and apply three basic building blocks to it. Then they add it back to the main branch after that one has been upsampeled again to the original size.
    * The feature maps between each basic building block have (usually) 256 channels.
    * Their HourGlass ends in two 1x1 convolutions that create the heatmaps.
    * They stack two of their HourGlass networks after each other. Between them they place an intermediate loss. That way, the second network can learn to improve the predictions of the first network.
    * Architecture visualized:
      * ![Architecture](https://raw.githubusercontent.com/aleju/papers/master/neural-nets/images/Stacked_Hourglass_Networks_for_Human_Pose_Estimation__architecture.jpg?raw=true "Architecture")
  * *Heatmaps*
    * The output generated by the network are heatmaps, one per joint.
    * Each ground truth heatmap has a small gaussian peak at the correct position of a joint, everything else has value 0.
    * If a joint isn't visible, the ground truth heatmap for that joint is all zeros.
  * *Other stuff*
    * They use batch normalization.
    * Activation functions are ReLUs.
    * They use RMSprob as their optimizer.
    * Implemented in Torch.

### Results
  * They train and test on FLIC (only one HourGlass) and MPII (two stacked HourGlass networks).
  * Training is done with augmentations (horizontal flip, up to 30 degress rotation, scaling, no translation to keep the body of interest in the center of the image).
  * Evaluation is done via PCK@0.2 (i.e. percentage of predicted keypoints that are within 0.2 head sizes of their ground truth annotation (head size of the specific body)).
  * Results on FLIC are at >95%.
  * Results on MPII are between 80.6% (ankle) and 97.6% (head). Average is 89.4%.
  * Using two stacked HourGlass networks performs around 3% better than one HourGlass network (even when adjusting for parameters).
  * Training time was 5 days on a Titan X (9xx generation).

Current medical imaging modalities like Computed Tomography (CT), Magnetic Resonance Imaging (MRI) or Positron Emission Tomography (PET) has allowed minimally-invasive imaging of internal organs. Rapid advancement in these technologies have lead to an influx of data, which, along with rising clinical need, has lead towards a need for quantitative image interpretation in routine practice. Some of the applications include volumetric measurements of regions of the brain, surgery or radiotherapy planning using CT/MRI images.

This influx of data have opened up avenues for using multi-modality images for making decisions. However this is not always straightforward as the imaging parameters, scanner types, patient movement, or anatomical movement make the images miss-aligned against each other, making direct comparison between, say, as CT and MRI image tricky. This is formally known as the problem of image registration, and to this end, numerous computational methods have been proposed, which this paper surveys. 

Out of the methods proposed for both inter- and intra-patient modality registration, Mutual Information based objective maximization strategy has been extremely successful at computing the registration between 3D multi-modal medical images of various organs from the images. Mutual Information (MI) stems from the field of information theory, pioneered by Shannon, which when applied in the context of medical image registration, postulates that the MI between two images (say CT and MRI) is maximum when the images are aligned. 

The basic formulation of a MI based registration algorithm is as follows: Let $\mathcal{A}$ and $\mathcal{B}$ be two images which are geometrically related according to a transformation $T_\alpha$, such that voxels $p$ in $\mathcal{A}$ with intensity $a$ physically correspond to voxels $T_\alpha(p)$ in $\mathcal{B}$ with intensity $b$. The relationship between $p_{AB}(a,b)$ between $a$ and $b$, and hence their MI depends on $T_\alpha$. The MI criterian postulates that the MI for images that are geometrically aligned is maximum:

\begin{equation}
    \alpha^* = argmax_{\alpha} I(A,B)
\end{equation}

Where $A$ and $B$ are two discrete random variables, and $I(A,B) = \sum_{a,b}p_{AB}(a,b) log \frac{p_{AB}(a,b)}{p_A(a).p_B(b)}$. 

An optimization algorithm is utilized to find a parameter set $\alpha^*$ that maximizes the MI between $A$ and $B$. Classically, Powell's multidimensional direction set method is used to otipimize the objective function, but other methods do exist as well. 

Although the formulation of MI criterion suggests that spatial dependence of image intensities are not taken into account, is in fact essential for the criterion to be well-behaved around the registration solution. MI does not rely on pure intensity values to measure correspondence between images, but rather on their joint distribution and the relationship of occurrence. It also does not impose any modality specific constraints which makes it general enough to be applied to any problem formulation (inter- or intra modality). 

Some of the areas where MI based image registration may fail is when there is insufficient information in images due to low resolution, low number of images, images not spatially invariant, images with shading artifacts. In some of these cases, MI based criterion will have multiple local optimals. 

This paper is a clever but conceptually simple idea to improve the vectors learned for individual words. In this proposed approach, instead of learning a distinct vector per word in the word, the model instead views a word as being composed of overlapping n-grams, which are combined to make the full word. 

Recall: in the canonical skipgram approach to learning word embeddings, each word is represented by a single vector. The word might be tokenized first (for example, de-pluralized), but, fundamentally, there isn’t any way for the network to share information about the meanings of “liberty” and “liberation”; even though a human could see that they share root structure, for a skipgram model, they are two totally distinct concepts that need to be separately learned. The premise of this paper is that this approach leaves valuable information on the table, and that by learning vectors for subcomponents of words, and combining them to represent the whole word, we can more easily identify and capture shared patterns. 

On a technical level, this is done by: 
- For each n value in the range selected (typically 3-6 inclusive), representing each input word as a set of overlapping windows of that n, with special characters for Start and End. For example, if n=3, and the word is “where”, it could be represented as [“<wh”, “whe”, “her”, “ere>”] 
- In addition to the set of ngrams, additionally representing each word through its full-word representation of “<where>”, to “catch” any leftover meaning not captured in the smaller ngrams. 
- When you’re calculating loss, representing each word as simply being the sum of all of its component ngrams 


https://i.imgur.com/NP5qFEV.png
This has some interesting consequences. First off, the perplexity of the model, which you can think of as a measure of unsupervised goodness of fit, is equivalent or improved by this approach relative to baselines on all but one model. Intriguingly, and predictably once you think about it, the advantage of the subword approach is much stronger for languages like German, Russian, and Arabic, which have strong re-use and aggregation of root words, and also strong patterns of morphological mutation of words. Additionally, the authors found that the subword model got to its minimum loss value using much less data than the canonical approach. This makes decent sense if you think about the fact that subcomponent re-use means there are fewer meaningful word subcomponents than their are unique words, and seeing a subcomponent used across many words means that you need fewer words to learn the patterns it corresponds to. 

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

A lot of the benefit of this approach seems to be through better representation of syntax; when tested on an analogy task, embeddings trained with subword information did meaningfully better on syntactic analogies (“swim is to swum as ran is to <>”) but equivalent or worse on semantic analogies (“mother is to girl as father is to <>”). One theory about this is that focusing on the subword elements does a better job of more quickly getting the representation of the word to be close to it’s exact meaning, but has a harder time learning precise semantics, relative to a full-word model. 

This paper introduces the B-link tree: a variant of a B+ tree (the paper says B* tree, but they mean B+ tree) which allows for concurrent searches, insertions, and deletions. Operations on a B-link tree lock at most three nodes at any given time, and searches are completely lock free.

#### Storage Model

We assume that every node of a B+ tree or B-link tree is stored on disk. Threads read nodes from disk into memory, modify them in memory, and then write them back to disk. Threads can also lock a specific node which will block other threads trying to acquire a lock on the same node. However, we'll also see that threads performing a search will not acquire locks at all and may read a node which is locked by another thread.

#### Concurrent B+ Trees

Let's see what goes wrong when we concurrently search and insert into a B+ tree without any form of concurrency control. Consider a fragment of a B+ tree shown below with two nodes x and y. Imagine a thread is searching for the value 2 and reads the pointer to y from x.

```
            +-------+
          x | 5 |   |
            +-------+
           /    |
  +-------+    ...
y | 1 | 2 |
  +-------+
```

Then, another thread inserts the value 3 which reorganizes the tree like this:

```
            +-------+
          x | 2 | 5 |
            +-------+
           /    |    \
  +-------+ +-------+ ...
y | 1 |   | | 2 | 3 |
  +-------+ +-------+
```

Next, the searching thread reads from y but cannot find the value 2!

Clearly, concurrently searching and inserting into a B+ tree requires some sort of locking. There are already a number of locking protocols:

 - The simplest protocol requires searches and insertions to lock every node along their path from root to leaf. This protocol is correct, but limits concurrency.
 - Smarter protocols have insertions place write intention locks along a path and upgrade those locks to exclusive locks when performing a write. Searches can read nodes with write intention locks on them but not with exclusive locks on them.
 - Even smarter protocols lock a subsection of the tree and bubble this subsection upwards through the tree. B-link trees will do something similar but will guarantee that at most three nodes are locked at any given point in time.

#### B-link Trees

 - Typically, an internal node in a B+ tree with $n$ keys has $n + 1$ pointers. For example, if an internal node has keys $(5, 10, 15)$, then it has four pointers for values in the range $[-\infty, 5)$, $[5, 10)$, $[10, 15)$, and $[15, \infty)$. Internal nodes in a B-link tree with $n$ keys have $n$ pointers where the last key is known as the <strong>high key</strong>. For example, if an internal node has keys $(5, 10, 15)$ then it has three pointers for values in the range $[-\infty, 5)$, $[5, 10)$, and $[10, 15)$.
 - In a B+ tree, leaves are linked together, but internal nodes are not. In a B-link tree, all sibling nodes (internal nodes and leaves) are linked together left to right.

#### Search Algorithm

The search algorithm for a B-link tree is very similar to the search algorithm for a B+ tree. To search for a key $k$, we traverse the tree from root to leaf. At every internal node, we compare $k$ against the internal node's keys to determine which child to visit next.

However, unlike with a B+ tree, we might have to walk rightward along the B-link tree to find the correct child pointer. For example, imagine we are searching for the key $20$ at an internal node $(5, 10, 15)$. Because $20 \gt 15$, we have to walk rightward to the next internal node which might have keys $(22, 27, 35)$. We do something similar at leaves as well to find the correct value.

Note that searching does not acquire any locks.

#### Insertion Algorithm

To insert a key $k$ into a B-link tree, we begin by traversing the tree from root to leaf in exactly the same way as we did for the search algorithm. We walk downwards and rightwards and do not acquire locks. One difference is that we maintain a stack of the rightmost visited node in each level of the tree. Later, we'll use the stack to walk backwards up the tree.

One we reach a leaf node, we acquire a lock on it and crab rightward until we reach the correct leaf node $a$. If $a$ is not full, then we insert $k$ and unlock $a$. If $a$ is full, then we split it into $a'$ (previously $a$) and $b'$ (freshly allocated). We flush $b'$ to disk and then flush $a'$ to disk. Next, we have to adjust the parent of $a'$ (formerly $a'$). We acquire a lock on the parent node and then crab rightward until we reach the correct parent node. At this point, we repeat our procedure upwards through the tree.

At worst, we hold three locks at a time.

#### Correctness Proof

To prove that the B-link tree works as we intend, we have to prove three things:

 - First, we have to prove that multiple threads operating on a B-link tree cannot deadlock. This is straightforward. If we totally order nodes bottom-to-top and left-to-right, then threads always acquire locks according to this total order.
 - Second, we have to prove that whenever a node modifies a B-link tree, the B-link tree still appears like a valid tree to all nodes except the modifying thread. Again, this is straightforward. The insertion procedure only makes three writes to disk.
   - Writing to a node that is not full clearly does not invalidate the tree.
   - Writing a newly allocated $b'$ node does not affect the tree because there are not any pointers to it.
   - Writing $a'$ atomically transitions the tree from one legal state to another.
 - Finally, we have to ensure that concurrently executing operations do not interfere with one another. See paper for proof (it's complicated).

#### Deletion
B-link trees punt on deletion. They simply let leaf nodes get underfull and periodically lock the whole tree and reorganize it if things get too sparse.

TLDR; The authors train an Generative Adversarial Network where the generator is an RNN producing discrete tokens. The discriminator is used to provide a reward for each generated sequence (episode) and to train the generator network via via Policy Gradients. The discriminator network is a CNN in the experiments. The authors evaluate their model on a synthetic language modeling task and 3 real world tasks: Chinese poem generation, speech generation and music generation. Seq-GAN outperforms competing approaches (MLE, Schedule Sampling, PG-BLEU) on the synthetic task and outperforms MLE on the real world task based on a BLEU evaluation metric.

#### Key Points

- Code: https://github.com/LantaoYu/SeqGAN
- RL Problem setup: State is already generated partial sequence. Action space is the space of possible tokens to output at the current step. Each episode is a fully generated sequence of fixed length T.
- Exposure Bias in the Maximum Likelihood approach: During decoding the model generates the next token based on a series previously generated tokens that it may never have seen during training leading to compounding errors.
- A discriminator can provide a reward when no task-specific reward (e.g. BLEU score) is available or when it is expensive to obtain such a reward (e.g. human eval).
- The reward is provided by the discriminator at the end of each episode, i.e. when the full sequence is generated. To provide feedback at intermediate steps the rest of the sequence is sampled via Monte Carlo search.
- Generator and discriminator are trained alternatively and strategy is defined by hyperparameters g-steps (# of Steps to train generator), d-steps (number of steps to train discriminator with newly generated data) and k (number of epochs to train discriminator with same set of generated data).
- Synthetic task: Randomly initialized LSTM as oracle for a language modeling task. 10,000 sequences of length 20.
- Hyperparameters g-steps, d-steps and k have a huge impact on training stability and final model performance. Bad settings lead to a model that is barely better than the MLE baseline.

#### My notes:

- Great paper overall. I also really like the synethtic task idea, I think it's a neat way to compare models.
- For the real-world tasks I would've liked to see a comparison to PG-BLEU as they do in the synthetic task. The authors evaluate on BLEU score so I wonder how much difference a direct optimization of the evaluation metric makes.
- It seems like SeqGAN outperforms MLE significantly only on the poem generation task, not the other tasks. What about the other baselines on the other tasks? What is it about the poem generation that makes SeqGAN perform so well?