The authors propose a simplified version of LSTMs. Some non-linearities and weighted components are removed, in order to arrive at the recurrent additive network (RAN). The model is evaluated on 3 language modeling datasets: PTB, the billion word benchmark, and character-level Text8.

 The paper captures the story of how Facebook created a high-performing, distributed key-value store on top of Memcache (which was back then a simple, in-memory cache) and scaled it to support the world’s largest social network.

In Facebook’s context, users consume much more content than they create. So the workload is read intensive and caching help to reduce the workload.MORE ON IT. Facebook uses Memcache Clusters where each Memcache instance is a demand-filled, look-aside cache. This means if a client requests data from Memcache and data is not available, the client would fetch the data from the database and would populate the cache for further requests. Memcache, not being a loading cache, does not have to worry about the logic of retrieving data from the database and can be easily plugged with multiple databases. In case of write requests, the client issues an update command to the database and a delete command is sent to Memcache. Deletion, being idempotent, is preferred over updation. While the overview seems pretty simple, there are more details in actual implementation. Facebook considers and optimizes for 3 deployments scales — a single cluster of servers, data replication between different clusters and spreading clusters across the world.

#### A single cluster of servers
These are characterized by a highly read intensive workload with requests having a wide fan out. Around 44% of requests contact more than 20 Memcache servers. For popular pages, this number spans well over 100 distinct servers. One reason for this is that each request returns a very small amount of data. In case of get requests, UDP performs better than TCP and get errors are treated as cache miss though insertion is not performed. This design choice seems practical as only .25% of requests fail due to late/ dropped or out of order packets. Though the response size is very small, the variation is quite large with mean = 954 bytes and median = 135 bytes. Set and delete operations are still performed over TCP (for reliability) though the connections are coalesced to improve efficiency.

Within a cluster, data is distributed across hundreds of servers through consistent hashing. A very high request rate combined with large fanout leads to an all to all communication between Memcache servers and clients and even a single server can become a bottleneck for many requests. Clients construct a DAG representing the dependency between data so that more independent requests are fired concurrently. Facebook also provides a standalone proxy called mcrouter that acts as an interface to Memcache server interface and routes the requests/replies to/from other servers. Along with these, flow control mechanisms in the form of sliding window mechanism are provided to limit incast congestion.

#### Lease
Leases are used to address stale sets (when web server writes a stale value in the cache) and thundering herds (when a key undergoes heavy read and write operations). When a client experiences a cache-miss, Memcache gives it a lease (a 64-bit token bound to the requested key). This lease is verified by Memcache when client tries to set the value. If Memcache receives a delete request for the key, the lease is invalidated and the value can not be set. To mitigate thundering herds, Memcache returns a token only once every 10 seconds per key. If a read request comes within 10 seconds of a token issue, the client is notified to retry after a short time, by which the updated value is expected to be set in the cache. In situations where returning stale data is not much problem, the client does not have to wait and stale data (at most 10 second old) is returned.

#### Memcache Pools
Since different workloads can have different access patterns and requirements, Memcache clusters are partitioned into pools. The default pool is called wildcard and then there are separate pools for keys that can not reside in the wildcard pool. A small pool can be provisioned for keys for which cache miss is not expensive. Data is replicated within a pool when request rate is quite high and data can easily fit into a few machines. In Facebook’s context, replication seems to work better than sharding though it has the additional overhead of maintaining consistency.
In case a few Memcache servers fail, a small set of machines, called gutters, take over. In case of more widespread failures, requests are diverted to alternate clusters.
Regions

Multiple front end clusters (web and Memcache clusters) along with a storage cluster (database) defines a region. The storage cluster has the authoritative copy of the data which is replicated across the frontend clusters. To handle data modifications, invalidation daemons called mcsqueal are deployed on each database which parse the queries, extract and group delete statements and broadcast them to all the front end cluster in the region. The batched delete operations are sent to mcrouter instances in each frontend cluster, which then unpack the individual deletes and route them to the concerned Memcache server. As an optimisation, a web server which modifies its data also sends invalidations to its own cluster to ensure read-after-write semantics for a single user request.

#### Cold cluster Warmup
When a new cluster is brought online, it takes time to get populated and initially the cache hit rate is very low. So a technique called Cold Cluster Warmup is employed where a new cold cluster is populated with data from a warm cluster instead of the database cluster. This way the cold cluster comes to full capacity within few hours. But additional care is needed to account for race conditions. One example could be: a client in cold cluster makes an update and before this update reaches the warm cluster, another request for the same key is made by the cold cluster then the item in the cold cache would be indefinitely inconsistent. To avoid this, Memcache rejects add operations for 2 seconds (called holdoff time)once a delete operation is taken place. So if a value is updated in a cold cluster and a subsequent request is made within 2 seconds, the add operation would be rejected indicating that the data has been updated. 2 seconds is chosen as most updates seems to propagate within this time.

#### Across Region consistency
Clusters comprising a storage cluster and several front end clusters are deployed in different regions. Only one of the regions contains the master database and rest act as replicas. This adds the challenge of synchronisation.

Writes from a master region send invalidations only within the master region. Sending invalidations outside may lead to a race situation where deletes reach before data is replicated. Facebook uses mcsequal daemon helps to avoid that at the cost of serving stale data for some time.

'Writes from a non-master region are handled differently. Suppose a user updates his data from a non-master region with a large replication lag. A cache refill from a replica database is allowed only after the replication stream has caught up. A remote marker mechanism is used to minimise the probability if reading stale data. The presence of a marker indicates that data in the replica is stale and the query is redirected to the master region. When a webserver updates a key k, it sets a remote marker rk in the region, performs the write to the master database having key k and deletes k in the local cluster. When it tries to read k next time, it will experience a cache miss, will check if rk exists and will redirect its query to the master cluster. Had rk not been set, the query would have gone to the local cluster itself. Here latency is introduced to make sure most updated data is read.

#### Single Server Improvements
Facebook introduced many improvements for Memcache servers running as single instances as well. This includes extending Memcache to support automatic expansion of the hash table without the look-up time drifting to $O(n)$, making the server multi-threaded using a global lock and giving each thread its own UDP port to reduce contention.

Memcache uses an Adaptive Slab Allocator which organizes memory into slab classes — pre-allocated, uniformly sized chunks of memory. Items are stored in smallest possible slab class which can fit the data. Slab sizes start at 64 bytes and reach up to 1 Mb. Each slab class maintains a free-list of available chunks and requests more memory in 1MB in case the free-list is empty. If no more free memory can be allocated, eviction takes place in Least Recently Used (LR) fashion. The allocator periodically rebalances slab assignments to keep up with the workload. Memory is freed in less used slabs and given to more heavily used slabs.

Most of the items are evicted lazily from the memory though some are evicted as soon as they are expired. Short lived items are placed into a circular buffer of linked lists (indexed by seconds until expiration) — called Transient Item Cache — based on the expiration time of the item. Every second, all of the items in the bucket at the head of the buffer are evicted and the head advances by one. By adding a short expiration time to heavily used set of keys whose items with short useful lifespans, the proportion of Memcache pool used by this key family was reduced from 6% to 0.3% without affecting the hit rate.

#### Lessons Learnt
Memcache’s design decisions are driven by data and not just intuition. Facebooks seems to have experimented with a lot of configurations before arriving on decisions like using UDP for read operations and choosing the value for parameters like holdoff time. This is how it should be — data-driven decisions. In the entire process of developing Memcache, Facebook focused on optimizations which affect a good number of users and usecases instead of optimizing for each possbile use case.

Facebook separated caching layer from persistence layer which makes it easier to mould the 2 layers individually. By handling the cache insertion logic in the application itself, Facebook made it easier to plug Memcache with different data stores. By modeling the probability of reading the stale data as a parameter, they allowed the latency and hit rate on the persistence store to be configurable to some extent thus broadening the scope for Memcache. Facebook breaks down a single page load request into multiple requests, thereby allowing for different kind of stale data tolerance for each component. For example, the servers serving the profile picture can cache content longer than the servers serving messages. This helps to lower the response latency and reduce the load on the data layer.

Facebook’s Memcache is one of the many solutions aimed to solve a rather common problem — a scalable, distributed key-value store. Amazon’s Dynamo solves is well for a write-intensive workload for small data sizes and Facebook solves it for a read intensive workload. Other contenders in the list are Cassandra, Voldemort, Redis, Twitter’s Memcache and more. The sheer number of possible, well known solutions suggests that there are many dimensions to the problem, some of which are yet unknown and that we still do not have a single solution that can be used for all use cases.

Mean(input) = 0, var(input) =1 is good for learning. Independent input features are good for learning.
So:

1) Pre-Initialize network weights with (approximate) orthonormal matrices

2) Do forward pass with mini-batch

3) Divide layer weights by $\sqrt{var(Output)}$

4) PROFIT! 

TLDR; the authors present Recurrent Memory Network. These networks use an attention mechanism (memory bank, MB) to explicitly incorporate information about preceding into the predictions at each time step. The MB is a layer that can be incorporated into any RNN, and the authors evaluate a total of 8 model variants: Optionally stacking another LSTM layer on top of the MB, optionally including a temporal matrix in the attention calcuation, and using a gating vs. linear function for the MB  output. The authors apply the model to Language Modeling tasks, achieving state of the art performance, and demonstrating that inspecting the attention weights yields intuitive insights into what the network learns: Co-occurence statistics and dependency type information. The authors also evaluate the models on a sentence completion task, achieving new state of the art.


#### Key Points

- RM: LSTM with MB as the top layer. No "horizontal" connections from MB to MB.
- RMR:  LSTM with MB and another LSTM stacked on top.
- RM with gating typically outperforms RMR.
- Memory Bank (MB): Input is current hidden state, and n preceding inputs including the current one. Attention is then calculated over the inputs based on the hidden state. The Output is a new hidden state, which can be calculated with or without gating. Optionally apply temporal bias matrix to attention calculation.
- Experiments: Hidden states and embeddings all of size 128. Memory size 15. SGD 15 epochs, halved each epoch after the forth.
- Attention Analysis (Language Model): Obviously, most attention is given to current and recent words. But long-distance dependencies are also captured, e.g. separable verbs in German. Networks also discovers dependency types.


#### Notes/Questions

- This works seems related to "Alternative structures for character-level RNNs" where the authors feed n-grams from previous words into the classification layer. The idea is to relieve the network from having to memorize these. I wonder how the approaches compare. 
- No related work section? I don't know if I like the name memory bank and the reference to Memory Networks here. I think the main idea behind Memory Networks was to reason over multiple hops. The authors here only make one hop, which is essentially just a plain attention mechanism.
- I wonder why exactly the RMR performs worse than the RM. I can't easily find an intuitive explanation for why that would be. Maybe just not enough training data?
- How did the authors arrive at their hyperparameters (128 dimensions)? 128 seems small compared to other models.

## **Introduction**
This paper presents a generalized technique of matching a deformable model to an image through energy minimization. An active contour model called snakes has been proposed which is a continuous and deformable spline always minimizing its energy under the influence of image forces as well as internal energy of the spline and external constraint forces. Because of its dynamic nature, snakes can be applied to image segmentation tasks (edges, lines, and subjective contours) as well as to motion tracking and stereo matching.

## **Method**
A snake can be parametrically represented as
$$
    {v}(s) = (x(s), y(s))
$$

The energy functional of a snake consists of the internal and the external energy components.
$$
    E_{snake}(C) = \underbrace{E_{ext}(C)}_{\text{data term}} + \underbrace{E_{int}(C)}_{\text{regularization term}}
$$

This can be decomposed into the following components:
$$
    E^{*}_{snake} = \int_{0}^{1} \Big[\: E_{int}({v}(s)) + E_{image}({v}(s)) + E_{constr}({v}(s)) \:\Big] \: ds
$$

where the components represent the internal energy of the snake due to its shape and bending, the image forces, and the external constraint forces on the snake respectively.

The internal energy of the snake can be represented as 
$$
    E_{int} = \frac{1}{2} \{\alpha (s)\left | {v}_{s}(s) \right |^{2} \:+\: \beta (s)\left | {v}_{ss}(s) \right |^{2}\}
$$
where the first order term and the second order term represent the elastic length and the stiffness of the snake respectively. 

The energy minimization is a $O(n)$ technique in time using sparse matrix methods (semi-implicit Euler method), which is is much faster than a $O(n^{2})$ fully explicit method.

The energy due to the image forces is composed of three components:
$$
    E_{image} = w_{line}E_{line} + w_{edge}E_{edge} + w_{terminal}E_{terminal}
$$ where
$$E_{line} = -\big( G_{\sigma} * \nabla^{2}{I} \big)^{2},$$ $$ E_{edge} = -\left | \nabla {I}(x,y) \right |^{2},$$ $$E_{term} = \frac{\partial \theta}{\partial {n}_{\perp}} = \frac{C_{yy}C_{x}^{2} - 2C_{xy}C_{x}C_{y} + C_{xx}C_{x}^{2}}{(C_{y}^{2} + C_{x}^{2})^\frac{3}{2}}$$

* The minima of the $E_{line}$ energy functional define the edges of the image. Depending upon the sign of the $w_{line}$ term, the snake tries to align itself to the lightest or the darkest contour near it. Smoothening the image gradient with a Gaussian allows the snake to reach an equilibrium on a blurred energy functional, and when the blurring is slowly reduced, the snake stays in shape despite the small scale textural details because of its own smoothness constraint.
    
* Because of the $E_{edge}$ term, the snake is attracted to the contours corresponding to large image gradients.
    
* Consider $C(x,y)$ to be a slightly smoothened image obtained by applying a Gaussian filter to it. The $E_{terminal}$ represents the energy corresponding to the curvature of the level contours of $C(x,y)$, and can be calculated as the rate of change of the gradient angle $\theta$ along the direction of the outer unit normal to the curve. The combination of $E_{edge}$ and $E_{terminal}$ ensures that during the energy minimization, the snake is attracted to the edges and/or the terminations.

Snakes can also be applied to the problem of stereo matching by adding an additional constraint to the energy functional. The constraint is that the disparities in the human visual system do not change too rapidly with space, meaning the following disparity has to be minimized, where the ${v}^{L}(s)$ and the ${v}^{R}(s)$ represent the left and the right snake contours respectively.

$$
    E_{stereo} = \big( {v}^{L}_{s}(s) - {v}^{L}_{s}(s) \big)^{2}
$$

Similarly, snakes can also be applied to the problem of motion tracking since the snakes are able to "lock on" to salient visual features and can, therefore, track them accordingly across frames.

## **Discussion and Shortcomings**
The snakes were the first variational approach to the image segmentation task, and therefore this was a seminal paper in image processing. By introducing the gradient (edge strength) as an energy term, they improved on the shortcomings of the prior published works.

Because snakes are "active" and are therefore always minimizing their energy, they show hysteresis in response to moving input.

The energy minimization for the snakes is achieved through gradient descent, and since the energy functional is not convex, it can get stuck on local minima. Therefore, a prerequisite for the snakes is that the curve initialization must be done sufficiently close to the desired solution.

Moreover, because of numerical instabilities, as the control points move in time, the curve can have self-intersections which is undesired in image segmentation tasks.