TLDR; The authors train a DQN on text-based games. The main difference is that their Q-Value functions embeds the state (textual context) and action (text-based choice) separately and then takes the dot product between them. The authors call this a Deep Reinforcement Learning Relevance network. Basically, just a different Q function implementation. Empirically, the authors show that their network can learn to solve "Saving John" and "Machine of Death" text games.

  * They describe a method to transfer image styles based on semantic classes.
  * This allows to:
    * (1) Transfer styles between images more accurately than with previous models. E.g. so that the background of an image does not receive the style of skin/hair/clothes/... seen in the style image. Skin in the synthesized image should receive the style of skin from the style image. Same for hair, clothes, etc.
    * (2) Turn simple doodles into artwork by treating the simplified areas in the doodle as semantic classes and annotating an artwork with these same semantic classes. (E.g. "this blob should receive the style from these trees.")

### How
  * Their method is based on [Combining Markov Random Fields and Convolutional Neural Networks for Image Synthesis](Combining_MRFs_and_CNNs_for_Image_Synthesis.md).
  * They use the same content loss and mostly the same MRF-based style loss. (Apparently they don't use the regularization loss.)
  * They change the input of the MRF-based style loss.
    * Usually that input would only be the activations of a VGG-layer (for the synthesized image or the style source image).
    * They add a semantic map with weighting `gamma` to the activation, i.e. `<representation of image> = <activation of specific layer for that image> || gamma * <semantic map>`.
    * The semantic map has N channels with 1s in a channel where a specific class is located (e.g. skin).
    * The semantic map has to be created by the user for both the content image and the style image.
    * As usually for the MRF loss, patches are then sampled from the representations. The semantic maps then influence the distance measure. I.e. patches are more likely to be sampled from the same semantic class.
    * Higher `gamma` values make it more likely to sample from the same semantic class (because the distance from patches from different classes gets larger).
  * One can create a small doodle with few colors, then use the colors as the semantic map. Then add a semantic map to an artwork and run the algorithm to transform the doodle into an artwork. 

### Results
  * More control over the transfered styles than previously.
  * Less sensitive to the style weighting, because of the additional `gamma` hyperparameter.
  * Easy transformation from doodle to artwork.

![Example](https://raw.githubusercontent.com/aleju/papers/master/neural-nets/images/Neural_Doodle__example.png?raw=true "Example")

*Turning a doodle into an artwork. Note that the doodle input image is also used as the semantic map of the input.*

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. 

#### Motivation:
+ When sampling a clinical time series, missing values become ubiquitous due to a variety of factors such as frequency of medical events (when a blood test is performed, for example).
+ Missing values ​​can be very informative about the label - *informative missingness*.
+ The goal of the paper is to propose a deep learning model that **exploits the missingness patterns** to enhance its performance.

#### Time series notation:

Multivariate time series with $D$ variables of length $T$: 
+ ${\bf X} = ({\bf x}_1, {\bf x}_2, \ldots, {\bf x}_T)^T \in \mathbb{R}^{T \times D}$.
+  ${\bf x}_t  \in \mathbb{R}^{D}$ is the $t$-th measurement of all variables. 
+ $x_t^d$ is the $d$-th component of  ${\bf x}_t$.

Missing value information is incorporated using *masking* and *time-interval* concepts.
 + Masking: says which of the entries are missing values.
  + Masking vector ${\bf m}_t \in \{0, 1\}^D$,  $m_t^d = 1$ if $x_t^d$ exists and $m_t^d = 0$ if $x_t^d$ is missing.
 + Time-interval: temporal pattern of 'no-missing' observations. Represented by time-stamps $s_t$ and time intervals $\delta_t$ (since its last observation).

Example: 
${\bf X}$: input time series with 2 variables, 
$$ {\bf X} = \begin{pmatrix}
47 & 49 & NA & 40 & NA & 43 & 55 \\ NA & 15 & 14 & NA & NA & NA & 15 
\end{pmatrix}
$$
with time-stamps
$${\bf s} =  \begin{pmatrix}
0 & 0.1 & 0.6 & 1.6 & 2.2 & 2.5 & 3.1
\end{pmatrix}
$$
The masking vectors  ${\bf m}_t$ and time intervals ${\delta}_t$ for each variable are computed and stacked forming the masking matrix ${\bf M}$ and time interval matrix ${\bf \Delta}$ :
$$ {\bf M} = \begin{pmatrix}
1 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 1 
\end{pmatrix}
$$
$$ {\bf \Delta} = \begin{pmatrix}
0 & 0.1 & 0.5 & 1.5 & 0.6 & 0.9 & 0.6 \\ 0 & 0.1 & 0.5 & 1.0 & 1.6 & 1.9 & 2.5 
\end{pmatrix}
$$

#### Proposed Architecture:
+ GRU (Gated Recurrent Units) with "trainable" decays:
 + Input decay: which causes the variable to converge to its empirical mean instead of simply filling with the last value of the variable. The decay of each input is treated independently
 + Hidden state decay: Attempts to capture richer information from missing patterns. In this case the hidden state of the network at the previous time step is decayed.


#### Dataset:
+ MIMIC III v1.4: https://mimic.physionet.org/
 + Input events, Output events, Lab events, Prescription events
+ PhysioNet Challenge 2012: https://physionet.org/challenge/2012/

|  	MIMIC III |	PhysioNet 2012 | 
-----------------------------------|--------------|---------------------
Number of samples ($N$) |	19714 |	4000
Number  of variables ($D$)	|99      |	33
Mean number of time steps	|35.89 |	68.91
Maximum number of time steps|150  |	155
Mean of variable missing rate 	|0.9621|	0.8225


#### Experiments and Results:
**Methodology**
+ Baselines:
 + Logistic Regression, SVM, Random Forest (PhysioNet sampled every 1h. MIMIC sampled every 2h). Forward / backfilling imputation. Masking vector is concatenated input to inform the models what inputs are imputed.
 + LSTM with mean imputation.
 + Variations of the proposed GRU model:
  + GRU-mean: impute average of the training set.
  + GRU-forward: impute last value.
  + GRU-simple: masking vectors and time interval are inputs. There is no imputation.
  + GRU-D: proposed model.
+ Batch normalization and dropout (p = 0.5) applied to the regression layer.
+ Normalized inputs to have a mean of 0 and standard deviation 1.
+ Parameter optimization: early stopping on validation set.

**Results**

Mortality Prediction (results in terms of AUC):
+ Proposed GRU-D outperforms other models on both datasets: 
 + AUC = 0.8527 $\pm$ 0.003 for MIMIC-III and 0.8424 $\pm$ 0.012 for PhysioNet
+ Random Forest and SVM are the best non-RNN baselines.
+ GRU-simple was the best RNN variant.

Multitask Prediction (results in terms of AUC):
+ PhysioNet: mortality, <3 days, surgery, cardiac condition.
+ MIMIC III: 20 diagnostic categories.
+ The proposed GRU-D outperforms other baseline models.

#### Positive Aspects:
+ Instead of performing simple mean imputation or using indicator functions, the paper exploits missing values and missing patterns in a novel way.
+ The paper performs lengthy comparisons against baselines.

#### Caveats:
+ Clinical mortality datasets usually have very high imbalance between classes. In such cases, AUC alone is not the best metric to evaluate. It would have been interesting to see the results in terms of precision/recall.

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.