Robust and fast detection of anatomical structures is a prerequisite for both diagnostic and interventional medical image analysis. Current solutions for anatomy detection are typically based on machine learning techniques that exploit large annotated image databases in order to learn the appearance of the captured anatomy. These solutions are subject to several limitations, including the use of suboptimal feature engineering techniques and most importantly the use of computationally suboptimal search-schemes for anatomy detection. To address these issues, we propose a method that follows a new paradigm by reformulating the detection problem
as a behavior learning task for an artificial agent.

To this end, Ghesu et al. reformulate the problem of landmark detection as a reinforcement learning task, where an agent is trained to navigate the 3D image space in an efficient way in order to find the landmark as spatially closely as possible. This paper marks the first time that RL has been used for a specific problem like this. 

The authors use Deep Q-Learning (DQN) algorithm as their framework to build the agent. The DQN algorithm uses a Convolutional Neural Network to parameterize the Q* function in a non-linear way. Also, in order to ensure that the agent always finds an object of interest regardless of the size, the authors proposed to use multi-scale search strategy, in which a different CNN works on an image of a different scale. 

The authors also some other interesting techniques like $\epsilon-$greedy approach, which uses a randomized strategy to choose the actions in every iteration. They also use experience replay where an experience buffer is maintained that records the trajectory of the agent. This buffer is then used to fine-tune the Q network. 

The authors test their method on an internal data set of CT scans, with a few different metrics. The most important metric was failure percentage rate, that was defined if the agent is x mm close to the landmark. The method achieved 0\% failure percentage rate on detecting landmarks in CT scans. 

Active Shape Models brought with them the ability to intelligentally deform to various intra-shape variations according to a labelled training set of landmark points. However the dependence of such methods on a low-noise training set marked manually poses challenges due to inter-observer differences which becomes even more pronounced in higher-dimensions (3D). To this end, the authors propose a method that addresses this problem, but introducing automatic shape modelling. 

The method is based upon the idea of Occam's Razor, or more formally, The minimum description length (MDL). It is the principle formalization of Occam's razor in which the best hypothesis (a model and its parameters) for a given set of data is the one that leads to the best compression of the data. This essentially means that the MDL characteristic can be used to learn from a set of data points, the best hypothesis that fully describes the training data set, but in a compressed form. The authors use a simple two-part coding formulation of MDL, which although does not guarantee a minimum coding length,but does provide a computationally simple functional form to evaluate which is suitable to be used as an objective function for numerical optimization. 

The proposes objective function is as follows:

$F = \sum_{p=1}^{n_g}D^{(1)}\left(\hat{Y}^p, R, \delta \right) + \sum_{q=n_g + 1}^{n_g + n_{min}}D^{2}\left(\hat{Y}^q, R, \delta \right)$
 
 The algorithm proceeds by first parameterizing a single shape using a recursive algorithm. Once the recursive parameterization is complete, optimization of the objective function presented above proceeds. The algorithm first generates a parameterization for each shape recursively, to the same level. Then shapes are sampled according to the correspondence defined by the parameterization. Once this is done, a model is built automatically from the above sampled shapes. This model is then used to calculate the objective function.
 The parameterization is changed as to converge to an optimal value for the objective function. 
 
 In order to change the parameterization of the model to converge to an optimal value of objective function, a ``reference" shape is chosen in order to avoid having the points converge to a bad a local minima (all points collapse to single part of the boundary). Due to the non-convex nature of the objective function, optimization is performed using genetic algorithm. 
 
 The method was tested both qualitatively and quantitatively on several sets of outlines of 2-D biomedical objects. Multiple anatomical sites in human body were chosen to test the model to provide an idea of how the method performs in a variety of shape settings. Quantitatively the models were shown to be highly compact in terms of the MDL. Qualitatively, the models were able to generate shapes that respected the overall shape of the training set, while still maintaining a good amount of deformation without going haywire. 

Assume you have both label and reward (some flexibility in accepting the output) as is the case for hamming distance and negative edit distance.

Assume the output space is discrete, it can be a quantized n-dim space.

Assume that given an input and a set of labels, computing the probability of the labels is $O(L)$, meaning that most of the computation is independent of the label. (not sure about this! You certainly don't want to sample from the network)

Suppose that you want to maximize an approximate objective which is a tradeoff between optimizing the reward or the label and you control this tradeoff by one parameter $\tau$ which you fix beforehand. This actually only directly affects the reward.

Then you can compute the loss, by sampling from each discrete value of reward and then sampling from those labels that have such reward.

Therefore, you can quickly approximate the loss and the gradient through sampling. And the samples are independent of the output of the network, but rather fixed given $\tau$ and ground-truth. This is as opposed to sampling the network and sampling around the predicted label.

#### 2.2 Sampling from the exponentiated payoff distribution

Note that $q$ should be defined such that the entropy is fixed given $\tau$. The paper notes that given the ground-truth label, if the loss is hamming distance or negative edit distance, then samples can be put into buckets of same loss (loss is discrete). Then One possible family of distributions controlled by $\tau$ is given by a normalized count reweighted by $\exp\{e/\tau\}$ for each bucket. By varying $\tau$, you can go from uniform distribution ($\tau=\infty$) to delta ($\tau=0$). Eq. 11 shows the simplified count for each bucket to be used for normalization and further sampling. As noted above the equation, edge cases like repetitions is ignored in this count to make the computation easy.

Given a fixed entropy $q$, then you can compute the RML loss by sampling from $q$ by first selecting an edit distance, and then sampling from the corresponding bucket.

#### Footnotes
I was not satisfied with the results. I didn't quite follow section 3.

The [Pregel paper](https://kowshik.github.io/JPregel/pregel_paper.pdf) introduces a vertex-centric, large-scale graph computational model. Interestingly, the name Pregel comes from the name of the river which the Seven Bridges of Königsberg spanned. 

### Computational Model

The system takes as input a directed graph with properties assigned to both vertices and edges. The computation consists of a sequence of iterations, called supersteps. In each superstep, a user-defined function is invoked on each vertex in parallel. This function essentially implements the algorithm by specifying the behaviour of a single vertex V during a single superstep S. The function can read messages sent to the vertex V during the previous superstep (S-1), change the state of the vertex or its out-going edges', mutate the graph topology by adding/removing vertices or edges and by sending messages to other vertices that would be received in the next superstep (S+1). Since all computation during a superstep is performed locally, the model is well suited for distributed computing and synchronization is needed only between supersteps.

The computation terminates when every vertex is in the deactivated state. When computation starts, all vertices are in active state. A vertex deactivates itself by voting to halt and once deactivated, it does not take part in subsequent supersteps. But any time a deactivated vertex receives a message, it becomes activated again and takes part in subsequent supersteps. The resulting state machine is shown below:

![Vertex State Machine](https://db.tt/Pdm1Rl6A)

The output of the computation is the set of values produced by the vertices.

Pregel adopts a pure message passing model that eliminates the need of shared memory and remote reads. Messages can be delivered asynchronously thereby reducing the latency. Graph Algorithms can also be expressed as a sequence of MapReduce jobs, but that requires passing the entire state of the graph from one stage to another. It also requires coordinating the various steps of chained MapReduce. In contrast, Pregel keeps vertices and out-going edges on machine performing the computation and only messages are transferred across. Though Pregel is similar in concept to MapReduce, it comes with a natural graph API and efficient support for running iterative algorithms over the graph.

### API

1. Pregel programs are written by subclassing the vertex class.
2. The programmer overrides the compute() method. This is the user-defined function that is invoked on each vertex.
3. Within compute(), the programmer can modify the value of vertex or out-going edges' properties and these changes are reflected immediately. These are the only per-vertex state that persists throughout each superstep.
4. All messages sent to vertex V during superstep S are available via an iterator in superstep S+1. While it is guaranteed that each message would be delivered exactly once, there is no guarantee on the order of delivery.
5. User defined handlers are invoked when destination vertex does not exist.
6. Combiners are used to reduce the number of messages to be transferred by aggregating messages from different vertices (all of which are on the same machine) which have the same destination vertex. Since there is no guarantee about which messages will be aggregated and in what order, only commutative and associative operations can be used.
7. Aggregators can be used for capturing the global state of the graph where each vertex provides a value to the aggregator during each superstep and these values are combined by the system using a reduce operation (which should be associative and commutative). The aggregated value is then available to all the vertices in the next superstep.


### Topology Mutation

Since compute() method allows the graph topology to be modified, conflicting requests can be made in the same superstep. Two mechanisms are used to handles the conflicts:

* Within a super step, following order is followed when resolving conflicting operations:
  *   Edge removal
  *   Vertex removal
  *   Vertex addition
  *   Edge addition.
*   User defined handlers are used for conflicts that can not be resolved by partial ordering alone. This would include scenarios where there are multiple requests to create a vertex with different initial values. In these cases, the user defines how to resolve the conflict.

The coordination mechanism is lazy in the sense that global mutations do not require coordination until the point they are applied.


### Execution Steps

* Several instances of the user program start executing on a cluster of machines. One of the instances becomes the master and the rest are the workers. 
* The master partitions the graph based on vertex id with each partition consisting of a set of vertices and its out-going edges. 
* These partitions are assigned to workers. Each worker executes the compute method on all its vertices and manages messages to and from other vertices.
* The master instructs each worker to perform a superstep. The workers run the computer method on each vertex and tell the master how many vertices would be active in the next superstep. This continues as long as even one vertex is active.
* Once all the vertices become deactivated, the master may ask the workers to save their portion of the graph.


### Fault Tolerance

Fault tolerance is achieved through checkpointing where the master instructs the workers to save the state of computation to persistent storage. Master issues regular "ping" messages to workers and if a worker does not receive a message from the master in a specified time interval, the worker terminates itself. If the master does not hear back from the worker, the worker is marked as failed. In this case, the graph partitions assigned to the failed worker are reassigned to the active workers. All the active workers then load the computation state from the last checkpoint and may repeat some supersteps.

An alternate to this would be confined recovery where along with basic checkpointing, the workers log out-going messages from their assigned partitions during graph loading and subsequent supersteps. This way, lost partitions can be recomputed from log messages and the entire system does not have to perform a rollback. 

### Worker Implementation

A worker contains a mapping of vertex id to vertex state for its portion of the complete graph. The vertex state would comprise of its current value, its put-going edges, the queue containing incoming messages and a flag marking whether it is in the active state. Two copies of queue and flag are maintained, one for the current superstep and one for the next superstep.

While sending a message to another vertex, the worker checks if the destination vertex is on the same machine. If yes, it places the message directly on the receiver's queue instead of sending it via the network. In case the vertex lies on the remote machine, the messages are buffered and sent to destination worker as a single network message.

If a combiner is specified, it is applied to both the message being added to the outgoing message queue and to the message received at the incoming message queue.

### Master Implementation

The master coordinates the workers by maintaining a list of currently alive workers, their addressing information and the information on the portion of graph assigned to them. The size of master's data structure depends on the number of partitions and a single master can be used for a very large graph.

The master sends the computation task to workers and waits for a response. If any worker fails, the master enters recovery mode as discussed in the section on fault tolerance. Otherwise, it proceeds to the next superstep. It also runs an internal hHTTP server to serve statistics about the graph and the state of the computation.

### Aggregators

Workers combine all the values supplied to an aggregator, by all the vertices in a superstep, into a single local value. At the end of the superstep, the workers perform the tree-based reduction on the local value and deliver the global values to the master. The tree-based reduction is better than pipelining with a chain of workers as it allows fro more parallelization.

### Applications/Experiments

The paper has described how to implement PageRank, ShortestPath, Bipartite Matching and Semi Clustering algorithm on top of Pregel. The emphasis is on showing how to think of these algorithms in a vertex-centric manner and not on how to implement them on Pregel in the best possible way.

The experiments were conducted with the single-source shortest paths algorithm with input as binary trees and log-normal graphs. Default partitioning strategy and naive implementation of the algorithms was used to show that satisfactory performance can be achieved with little coding effort. The runtime increases approximately linearly in the graph size.

### Limitations

One obvious limitation is that the entire computation state resides in main memory. Secondly, Pregel is designed around sparse graphs and performance will take a hit in case of dense graphs where a lot of communication takes place between vertices. The paper counters this by arguing that realistic dense graphs and algorithms with dense computation are rare. Moreover, communication in such dense networks can be reduced by using aggregators and combiners. An add-on would be to support dynamic partitioning of graph based on message traffic to minimize communication over the network.


Pregel's open-source implementation, called [Giraph](http://giraph.apache.org/), adds several features beyond the basic Pregel model, including out-of-core computation, and edge-oriented input which does take away some of the original limitations. Facebook is using Giraph to analyze its social network and has [scaled it to a trillion edges](https://code.facebook.com/posts/509727595776839/scaling-apache-giraph-to-a-trillion-edges/) showing the scalability of the Pregel model itself.    

Find a topology by reinforcement learning. They use REINFORCE from [Williams 1992](http://www.shortscience.org/paper?bibtexKey=Williams:92).


## Ideas

* Structure and connectivity of a Neural Network can be represented by a variable-length string.
* The RNN controller in Neural Architecture Search is auto-regressive, which means it predicts hyperparameters one a time, conditioned on previous predictions
* policy gradient method to maximize the expected accuracy of the sampled architectures
* In our experiments, the process of generating an architecture stops if the number of layers exceeds
a certain value.

## Evaluation

* Computer Vision - **CIFAR-10**: 3.65% error (State of the art are Dense-Nets with 3.46% error)
* Language - **Penn Treebank**: a test set perplexity of 62.4 (3.6 perplexity better than the previous state-of-the-art)

They had a Control Experiment "Comparison against Random Search" in which they showed that they are much better than a random exploration of the data. However, the paper lacks details how exactly the random search was implemented.

## Related Work

* [Designing Neural Network Architectures using Reinforcement Learning](https://arxiv.org/pdf/1611.02167.pdf) ([summary](http://www.shortscience.org/paper?bibtexKey=journals/corr/1611.02167))