* They present a hierarchical method for reinforcement learning.
  * The method combines "long"-term goals with short-term action choices.

### How
  * They have two components:
    * Meta-Controller:
      * Responsible for the "long"-term goals.
      * Is trained to pick goals (based on the current state) that maximize (extrinsic) rewards, just like you would usually optimize to maximize rewards by picking good actions.
      * The Meta-Controller only picks goals when the Controller terminates or achieved the goal.
    * Controller:
      * Receives the current state and the current goal.
      * Has to pick a reward maximizing action based on those, just as the agent would usually do (only the goal is added here).
      * The reward is intrinsic. It comes from the Critic. The Critic gives reward whenever the current goal is reached.
  * For Montezuma's Revenge:
    * A goal is to reach a specific object.
    * The goal is encoded via a bitmask (as big as the game screen). The mask contains 1s wherever the object is.
    * They hand-extract the location of a few specific objects.
    * So basically:
      * The Meta-Controller picks the next object to reach via a Q-value function.
      * It receives extrinsic reward when objects have been reached in a specific sequence.
      * The Controller picks actions that lead to reaching the object based on a Q-value function. It iterates action-choosing until it terminates or reached the goal-object.
      * The Critic awards intrinsic reward to the Controller whenever the goal-object was reached.
    * They use CNNs for the Meta-Controller and the Controller, similar in architecture to the Atari-DQN paper (shallow CNNs).
    * They use two replay memories, one for the Meta-Controller (size 40k) and one for the Controller (size 1M).
    * Both follow an epsilon-greedy policy (for picking goals/actions). Epsilon starts at 1.0 and is annealed down to 0.1.
    * They use a discount factor / gamma of 0.9.
    * They train with SGD. 

### Results
  * Learns to play Montezuma's Revenge.
  * Learns to act well in a more abstract MDP with delayed rewards and where simple Q-learning failed.

--------------------

# Rough chapter-wise notes


* (1) Introduction
  * Basic problem: Learn goal directed behaviour from sparse feedbacks.
  * Challenges:
    * Explore state space efficiently
    * Create multiple levels of spatio-temporal abstractions
  * Their method: Combines deep reinforcement learning with hierarchical value functions.
  * Their agent is motivated to solve specific intrinsic goals.
  * Goals are defined in the space of entities and relations, which constraints the search space.
  * They define their value function as V(s, g) where s is the state and g is a goal.
  * First, their agent learns to solve intrinsically generated goals. Then it learns to chain these goals together.
  * Their model has two hiearchy levels:
    * Meta-Controller: Selects the current goal based on the current state.
    * Controller: Takes state s and goal g, then selects a good action based on s and g. The controller operates until g is achieved, then the meta-controller picks the next goal.
  * Meta-Controller gets extrinsic rewards, controller gets intrinsic rewards.
  * They use SGD to optimize the whole system (with respect to reward maximization).

* (3) Model
  * Basic setting: Action a out of all actions A, state s out of S, transition function T(s,a)->s', reward by state F(s)->R.
  * epsilon-greedy is good for local exploration, but it's not good at exploring very different areas of the state space.
  * They use intrinsically motivated goals to better explore the state space.
  * Sequences of goals are arranged to maximize the received extrinsic reward.
  * The agent learns one policy per goal.
  * Meta-Controller: Receives current state, chooses goal.
  * Controller: Receives current state and current goal, chooses action. Keeps choosing actions until goal is achieved or a terminal state is reached. Has the optimization target of maximizing cumulative reward.
  * Critic: Checks if current goal is achieved and if so provides intrinsic reward.
  * They use deep Q learning to train their model.
  * There are two Q-value functions. One for the controller and one for the meta-controller.
  * Both formulas are extended by the last chosen goal g.
  * The Q-value function of the meta-controller does not depend on the chosen action.
  * The Q-value function of the controller receives only intrinsic direct reward, not extrinsic direct reward.
  * Both Q-value functions are reprsented with DQNs.
  * Both are optimized to minimize MSE losses.
  * They use separate replay memories for the controller and meta-controller.
  * A memory is added for the meta-controller whenever the controller terminates.
  * Each new goal is picked by the meta-controller epsilon-greedy (based on the current state).
  * The controller picks actions epsilon-greedy (based on the current state and goal).
  * Both epsilons are annealed down.

* (4) Experiments
  * (4.1) Discrete MDP with delayed rewards
    * Basic MDP setting, following roughly: Several states (s1 to s6) organized in a chain. The agent can move left or right. It gets high reward if it moves to state s6 and then back to s1, otherwise it gets small reward per reached state.
    * They use their hierarchical method, but without neural nets.
    * Baseline is Q-learning without a hierarchy/intrinsic rewards.
    * Their method performs significantly better than the baseline.
  * (4.2) ATARI game with delayed rewards
    * They play Montezuma's Revenge with their method, because that game has very delayed rewards.
    * They use CNNs for the controller and meta-controller (architecture similar to the Atari-DQN paper).
    * The critic reacts to (entity1, relation, entity2) relationships. The entities are just objects visible in the game. The relation is (apparently ?) always "reached", i.e. whether object1 arrived at object2.
    * They extract the objects manually, i.e. assume the existance of a perfect unsupervised object detector.
    * They encode the goals apparently not as vectors, but instead just use a bitmask (game screen heightand width), which has 1s at the pixels that show the object.
    * Replay memory sizes: 1M for controller, 50k for meta-controller.
    * gamma=0.99
    * They first only train the controller (i.e. meta-controller completely random) and only then train both jointly.
    * Their method successfully learns to perform actions which lead to rewards with long delays.
    * It starts with easier goals and then learns harder goals.

#### Introduction

* Automated Theorem Proving (ATP) - Attempting to prove mathematical theorems automatically.
* Bottlenecks in ATP:
    * **Autoformalization** - Semantic or formal parsing of informal proofs.
    * **Automated Reasoning** - Reasoning about already formalised proofs.
* Paper evaluates the effectiveness of neural sequence models for premise selection (related to automated reasoning) without using hand engineered features.
* [Link to the paper](https://arxiv.org/abs/1606.04442)

#### Premise Selection

* Given a large set of premises P, an ATP system A with given resource limits, and a new conjecture C, predict those premises from P that will most likely lead to an automatically constructed proof of C by A

#### Dataset

* Mizar Mathematical Library (MML) used as the formal corpus.
* The premise length varies from 5 to 84299 characters and over 60% if the words occur fewer than 10 times (rare word problem).

#### Approach

* The model predicts the probability that a given axiom is useful for proving a given conjecture.
* Conjecture and axiom sequences are separately embedded into fixed length real vectors, then concatenated and passed to a third network with few fully connected layers and logistic loss.
* The two embedding networks and the joint predictor path are trained jointly.

##### Stage 1: Character-level Models

* Treat premises on character level using an 80-dimensional one hot encoding vector.
* Architectures for embedding:
    * pure recurrent LSTM and GRU Network
    * CNN (with max pooling)
    * Recurrent-convolutional network that shortens the sequence using convolutional layer before feeding it to LSTM.

##### Stage 2: Word-level Models

* MML dataset contains both implicit and explicit definitions.
* To avoid manually encoding the implicit definitions, the entire statement defining an identifier is embedded and the definition embeddings are used as word level embeddings.
* This is better than recursively expanding and embedding the word definition as the definition chains can be very deep.
* Once word level embeddings are obtained, the architecture from Character-level models can be reused.

#### Experiments

##### Metrics

* For each conjecture, the model ranks the possible premises.
* Primary metric is the number of conjectures proved from top-k premises.
* Average Max Relative Rank (AMMR) is  more sophisticated measure based on the motivation that conjectures are easier to prove if all their dependencies occur earlier in ranking.
* Since it is very costly to rank all axioms for a conjecture, an approximation is made and a fixed number of random false dependencies are used for evaluating AMMR.

##### Network Training

* Asynchronous distributed stochastic gradient descent using Adam optimizer.
* Clipped vs Non-clipped Gradients.
* Max Sequence length of 2048 for character-level sequences and 500 for word-level sequences.

##### Results

* Best Selection Pipeline - Stage 1 character-level CNN which produces word-level embeddings for the next stage.
* Best models use simple CNNs followed by max pooling and two-stage definition-based def-CNN outperforms naive word-CNN (where word embeddings are learnt in a single pass).

In the face of latency, partitions, and failures, application sometimes turn to weak consistency for improved performance. However, strong consistency cannot always be avoided, so some data stores (e.g. Cassandra, Riak) allow applications to operate on some data with weak consistency and on other data with strong consistency. However, it is difficult to ensure that data read with weak consistency does not leak into the strongly consistent data.

For example, imagine a ticketing application that displays the number of remaining tickets for an upcoming movie. To improve performance, an application may choose to read the data using weak consistency; it's okay if the displayed number is slightly erroneous. However, now imagine that we want to increase the price of the last 10 tickets. If we used the same weakly consistent value to determine the price of a ticket, we may make less money that we expect. Weak and strong consistency cannot be carelessly mixed.

The Inconsistent, Performance-bound, Approximate (IPA) storage system uses a type system of consistency types to ensure consistency safety: the guarantee that weakly consistent data does not leak into strongly consistent data. They also introduce error-bounded consistency which allows a runtime to dynamically choose the strongest consistency that satisfies certain constraints (e.g. latency or accuracy).

Programming Model. The IPA programming model involves three components: abstract data types, consistency policies, and consistency types. Users annotate ADTs with consistency policies which determines the consistency types returned by the ADT's methods.

1. ADTs. IPA is bundled with a set of common ADTs (e.g. sets, maps, lists) that can be implemented with any number of backing stores (e.g. Cassandra, Riak, Redis). The collection of ADTs is also extensible; users can add their own ADTs.
2. Consistency Policies. ADT instances (or their methods) are annotated with consistency policies which designate the level of consistency the user desires. Static policies, like strong consistency, are fixed throughout the lifetime of the ADT. Dynamic policies allow the runtime to dynamically choose the consistency of the system to meet some constraint. For example, a user can set a policy LatencyBound(x), and the system will choose the strongest consistency that can be served and still satisfy the latency bound. Or, a user can set a ErrorTolerance(x) allowing the system to return approximate results with weaker consistency.
3. Consistency Types. Consistency types are parameterized on a type T and are partially ordered

```
          Consistent[T]
          /     |     \
Interval[T] Rushed[T] ...
          \     |     /
         Inconsistent[T]
```

Users can explicitly endorse, or upcast, weak types to stronger types. Rushed types are produced by ADTs with LatencyBound policies and are a sum of other consistency types. Interval types are a numeric interval which are guaranteed to contain the correct value.

Enforcing Consistency Policies. Static consistency policies are easy to enforce. The ADT operations simply set flags that are used by the underlying store. Dynamic policies are trickier to implement.

- Latency bounds. To service a read with a latency bound of x milliseconds, for example, a read is issued at every single consistency level. The strongest to return in less that x milliseconds is used. This naive approach can put unwanted load on a system, so IPA can also monitor and predict the strongest consistency model for a given latency bound in order to issue only a couple of reads.

- Error bounds. Error bounds are enforced using a reservation scheme similar to the one used by bounded CRDTs. For example, imagine a counter with value 10 should be concurrently decremented but never drop below 0. We can allocate 10 decrement tokens and distribute them to nodes. A node can decrement so long as it has enough tokens. IPA involves reservation servers which are assigned tokens. A node can return an approximate read by knowing the number of outstanding tokens. For example, given a value of 100 and knowing there are 10 outstanding increment tokens, the true value is somewhere in the range [100, 110]. The more outstanding tokens there are, the weaker the error bounds. To avoid unnecessarily granting tokens, IPA uses an allocation table which maps reservation servers to tokens. Tokens are only allocated when necessary.

Implementaton. IPA is implemented in Scala on top of Cassandra with some middleware for the reservation servers. Type checking is done by leveraging Scala's type system.

Over the last five years, artificial creative generation powered by ML has blossomed. We can now imagine buildings based off of a sketch, peer into the dog-tiled “dreams” of a convolutional net, and, as of 2017, turn images of horses into ones of zebras. This last problem - typically termed image-to-image translation- is the one that CycleGAN focuses on. The kinds of transformations that can full under this category is pretty conceptually broad: zebras to horses, summer scenes to winter ones, images to Monet paintings. (Note: I switch between using horse/zebra as my explanatory example, and using summer/winter. Both have advantages for explaining different conceptual poinfts) However, the idea is the same: you start with image a, which belongs to set A, and you want to generate a mapping of that image into set B, where the only salient change is that it’s now in set B. As a clarifying example: if you started out with a horse, and your goal was to translate it into a zebra, you would hope that the animal is in the same size, relative position, and pose, and that the only element that changed was changing the quality of “horseness” for the quality of “zebraness”. 

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

The real trick of CycleGAN is the fact that, unlike prior attempts to solve this problem, they didn’t use paired data. This is understandable, given the prior example: while it’s possible to take a picture of a scene in both summer and winter, you obviously can’t convert a horse into a zebra so that you can take a “paired” picture of it in both forms. When you have paired data, this is a reasonably well-defined problem: you want to learn some mathematical transformation to turn a specific summer image into a specific winter one, and you can use the ground truth winter image as explicit supervision. Since they lack this per-image cross-domain ground truth, the authors of this paper take what would be one question (“is the winter version of this image that the network generated close to the actual known winter version of this image”) and decompose it into two: 
Does the winter version of this original summer image looks like it belongs to the set of winter images? This is enforced by a GAN-style discriminator, which takes in outputs of the summer->winter generator, and true images of winter, and tries to tell them apart. This loss component pushes generated winter images to have the quality of “winterness”. This is the “Adversarial Loss” 
Does the winter version of this image contain enough information about this specific original summer image to accurately reconstruct it with an inverted (winter -> summer) generator? This constraint pushes the generator to actually translate aspects of this specific image between summer and winter. Without it, as the authors of the paper showed, the model has no incentive to actually do translation, and instead just generates winter images that have nothing to do with the summer image (and, frequently experience mode collapse: only generating a single winter image over and over again). This is termed the “Cycle Consistency Loss” 

It’s actually the case that there are two versions of both of the above networks; that’s what puts the “cycle” in CycleGAN. In addition to a loss ensuring you can map summer -> winter -> summer, there’s another one ensuring the other direction, winter -> summer -> winter holds as well. And, for both of those directions, we use the adversarial loss on the middle “translated” image, and a cycle consistency loss on the last “reconstructed” image. A key point here is that, because of the inherent structure of this loss function requires mapping networks going in both directions, training a winter->summer generator gets you a summer-> winter one for free. 

(Note: this is a totally different model architecture than most of the “style transfer” applications you likely previously seen, though when applied to photograph -> painting translation, it can have similar results) 

## __Background__
RNN language models are composed of:
1. Embedding layer
2. Recurrent layer(s) (RNN/LSTM/GRU/...)
3. Softmax layer (linear transformation + softmax operation)

The embedding matrix and the matrix of the linear transformation just before the softmax operation are of the same size (size_of_vocab * recurrent_state_size) . 
They both contain one representation for each word in the vocabulary. 

## __Weight Tying__
This paper shows, that by using the same matrix as both the input embedding and the pre-softmax linear transformation (the output embedding), the performance of a wide variety of language models is improved while the number of parameters is massively reduced. 
In weight tied models each word has just one representation that is used in both the input and output embedding.

## __Why does weight tying work?__
1. In the paper we show that in un-tied language models, the output embedding contains much better word representations that the input embedding. We show that when the embedding matrices are tied, the quality of the shared embeddings is comparable to that of the output embedding in the un-tied model. So in the tied model the quality of the input and output embeddings is superior to the quality of those embeddings in the un-tied model. 
2. In most language modeling tasks because of the small size of the datasets the models tend to overfit. When the number of parameters is reduced in a way that makes sense there is less overfitting because of the reduction in the capacity of the network.

## __Can I tie the input and output embeddings of the decoder of an translation model?__
Yes, we show that this reduces the model's size while not hurting its performance. 
In addition, we show that if you preprocess your data using BPE, because of the large overlap between the subword vocabularies of the source and target language, __Three-Way Weight Tying__ can be used. In Three-Way Weight Tying, we tie the input embedding in the encoder to the input and output embeddings of the decoder (so each word has one representation which is used across three matrices).

[This](http://ofir.io/Neural-Language-Modeling-From-Scratch/) blog post contains more details about the weight tying method.