A parameter server is more or less a distributed key-value store optimized for training machine learning models. For example, imagine we're learning a weight vector $w = (w_1, w_2, w_3)$ using logistic regression. We can distribute $w$ across two shards of the parameter server where one shard stores $(1, w_1)$ and the other stores $(2, w_2)$ and $(3, w_3)$. Worker nodes can then read parts of the weight vector, perform some computation, and write back parts of the weight vector.

This paper presents an optimized parameter server with the following features:

1. Efficient communication.
2. Flexible consistency models.
3. Elastic scalability.
4. Fault tolerance and durability.
5. Ease of use.

#### Machine Learning

Many machine learning algorithms try to find a weight vector $w \in \mathbb{R}^d$ that minimizes a regularized cost function of the following form:

$$ F(w) = \Omega(w) + \sum_{i=1}^n l(x_i, y_i, w) $$

When $n$ and $d$ get really big, it becomes intractable to run these algorithms on a single machine. Instead, we have to parallelize the algorithm across multiple machines.

As an example, consider how to perform distributed batch gradient descent across $m$ workers. We initialize $w$ and store it in a parameter server. Concurrently, each worker begins by reading $\frac{1}{m}$ of the training data. Then, every worker reads $w$ from the parameter server and computes a gradient with respect to its local training data (actually, it only needs to read the relevant parts of $w$). Then, it pushes its gradient to the parameter server. Once the server receives gradients from every worker, it aggregates them together and updates $w$. Finally, workers pull the updated $w$ and loop.

#### Architecture

A parameter server consists of a bunch of servers that store weights and a bunch of workers that perform computations with the weights (e.g. compute gradients). Servers are organized into a server group managed by a server manager. Workers are organized into multiple worker groups, and each worker group is managed by a task scheduler. The server manager manages which data is assigned to which server. The task scheduler assigns tasks to workers and monitors progress.

Parameters are stores as key-value pairs. For example, a weight vector $w \in \mathbb{R}^d$ can be stored as a set of pairs $(i, w_i)$ for $1 \leq 1 \leq d$. To store sparse vectors more efficiently, only non-zero entries of $w$ must be explicitly stored. If a pair $(i, w_i)$ is missing, the parameter server assumes $w_i = 0$.

Most machine learning algorithms do not update individual entries of a weight vector at a time. Instead, they typically update part of a matrix or part of a vector. To take advantage of this workload pattern, the parameter server allows workers to read and write ranges of values instead of single values at a time. This reduces network overhead.

In addition to pushing and pulling entries of  $w$, workers can also register user-defined functions to run at a server. For example, a server can compute the gradient of a regularization term.

By default, the parameter server runs tasks asynchronously. That is, if a worker issues a pull or push request, it does not block. However, the parameter server also allows workers to explicitly mark dependencies between different requests which forces them to serialize.

Some algorithms are robust to weir inconsistencies. These algorithms can often run faster with weaker consistency. The parameter server provides three levels of consistency:

1. Sequential consistency in which every request is totally serialized.
2. Eventual consistency in which requests are run whenever they please.
3. Bounded delay in which a request is delayed until all tasks that began τ time ago have completed.

Users can also specify that a certain consistency model only apply to a certain subset of key-value pairs as specified by a filter.

#### Implementation

Data is partitioned across servers using consistent hashing, and the server manager records the assignment of key ranges to machines. When a new server joins:

1. The server manager assigns a new key range to the server.
2. The server fetches its data from other servers.
3. The server manager broadcasts the update to the other servers who relinquish data they no longer own.

The parameter server uses chain replication to replicate data. Each node forms a chain with the $k$ previous nodes in the hashing ring. Workers send updates to the master which is chain replicated to the next $k$ servers.

Logically, the parameter server tags each key-value pair with a vector clock (though honestly, I'm not exactly sure I understand why). Physically, each range of key-value pairs is associated with a vector clock. This range-based vector clock avoids storing redundant vector clock information.

Messages sent from workers to servers are compressed with Snappy. Moreover, servers cache parts of messages, and workers can send a hash instead of a whole message if they the think a server has it cached.

#### About APAD ####
_This summer I've been Interning at an AI lab at BCM, working under
Ankit Patel in his incredible Neuroscience-meets-Deep-Learning group. 
This field is moving faster than anything else out there. Keeping intro short, 
so full post + inline pictures are on my [blog](http://rayraycano.github.io/data%20science/tech/2017/07/31/A-Paper-a-Day-GEM.html)_

## Basics ##
* __Paper__: [Gradient Episodic Memory for Continuum Learning][GED]
* __Authors__: David Lopez-Paz, Marc'Aurelio Ranzato 
* __Organizaitons__: Facebook AI Research (FAIR)
* __Topic__: Coninuum Learning
* __In One Senetence__: _Paz and Ranzato define sorely needed metrics to the
subfield of Continual Learning while developing a gradient-inspired update rule 
that avoids catastrophic forgetting_

### Background ###

Paz and Ranzato's continuum learning targets a more general problem of 
_catastrophic forgetting_, which the authors describe as "the poor ability of models to
quickly solve new problems, without forgetting previously acquired knowledge."
Recently this has been a hot topic in AI recently, as a flurry of 
papers in early summer were released discussing this topic ([Elastic Weight Consolidation][EWC],
[PathNet][PathNet], [iCaRL][iCARL], [Sluice Network][Sluice Network], [Intelligent Synapses][Intelligent Synapses]).
Avoiding catastrophic forgetting and achieving nontrivial _backwards transfer_ (BT) and _forward transfer_ (FT) are major goals for
continual learning models, and in addition, general AI. 

__Analogy Alert!__ _As Ankit explained to me originally: 
If you know how to play tennis, your experience 
*should* aid your ability to pick up ping pong (FT). 
In addition, when you return to tennis, your aptitude
in tennis shouldn't decrease (some atheletes argue that they get better
at their primary sport because they've played secondary sports, i.e. BT)._ 
 
## Paper Accomplishments ##

1. Of the 5 papers mentioned above, 0 of them formally define metrics for a
continual learner. 
2. The gradient-aligning update rule is quite clever and pretty cool.

### The Metrics ###
First, let's take a look at their formal definitions for FT and BT. 
They're displayed below. The notation is a bit confusing, so I've done my
 best to parse it.
 
[Backward And Forward Transfer LaTeX](https://www.dropbox.com/s/qrj6sxkfruj42uk/Screen%20Shot%202017-07-31%20at%204.56.05%20PM.png?dl=1)

T is the total number of tasks, enumerated from 1 to T. The bi vector is the random initialization for each task. I've omitted accuracy from this discussion because it seem too novel in the context of this paper

* Assume a fixed sequence of tasks (Numbered 1 through T)
* Forward transfer is the average accuracy of some task, task _i_, after each 
task in the sequence preceding _i_ is completed. 
    * Record the score for task _i_ upon random initialization
    * Learn task 1, record your score for task _i_. Learn task 2, record your
     score for task _i_, etc., up until task _i-1_.
    * Subtract from their score upon initialization and average these scores.
* Backwards Transfer is the average accuracy change for task _i_ after each 
task afterwards has been completed
    * Record the score for task _i_ after learning it
    * Learn task _i+1_. Now record the score for task _i_. Learn task _i+2_. Record the
    score for task _i_, etc.
    * For each score of task _i_ that recorded after completeing _i_, subtract from the first
    score for task _i_. Average these Scores

    
#### Gripes about the Metrics ####
In my opinion, these metrics don't generalize well. Continuum Learning (which I presume
is less general than _Continual_ Learning) specifies a sequence of tasks,
 meaning it is sensitive to the order of tasks. In their experiments section, 
 they use tasks that theoretically don't depend on the order in which they're learned, so in the 
 scheme of their paper this point is moot. However, Continual Learning in general
has no specification on order. Other papers concerning this topic have not discussed
task curriculums at all, while this paper glosses over it. 

__A metric I prefer: randomly sample from a pool of tasks
_n_ times. Learn these _n_ tasks in an arbitrary order. Lastly, evaluate accuracy on _i_ (for forward transfer).__ 
(This can be done over multiple trials to get a robust average)

### Gradient-Aligned Updates ###

For those new to Machine Learning, much of Deep Learning is powered by the 
[__backpropagation algorithm__][backprop]. This algorithm calculates an update that
will improve the accuracy for the problem based on an error metric. It does this by calculating what's 
called a gradient. 

__Analogy Alert!__ : _You shoot a dart at a board. You shot low by some distance __d__. 
You correct your mechanics, backwards reasoning from the missed distance, to your 
release point, and from there perhaps your throwing velocity. 
You can think of these corrections as the gradient, and the linked modification of
all the preceding components as an implementation
of the [chain rule][chainrule]. Disclaimer: 
 There is no evidence that the brain implements backpropagation_

So what does Gradient Episodic Memory (GEM) do exactly? Let's start with the Memory
part and go from there

* _Memory_: Recall those sequence of tasks we mentioned earlier? Well for each of those
tasks, let's make sure we don't forget them. We'll keep a portion of them in memory. 

* _Episodic_: Let's replay these memories to make sure we're not damaging our accuracy
on these tasks when we learn new ones. By playing them over again, we're basically going through an episode

* _Gradient_: When we look at the episode again, let's make sure the gradient doesn't
go the wrong way. What this means is: let's not unlearn what we learned on the 
previous task. 

### So How is it Done? ###

[Gradient Update Equation][Gradient Update Equation]

g is the gradient for the current task, while gk is the gradient for each previous task, calculated over the episodes in memory (Mk). The big < > notation is a dot product operator

Dot Products! In order for a gradient update to take place, they compute the dot product
of the current learning task with all the previous tasks in memory. The update is allowed
to take place if the gradient is greater than or equal to 0 for all the episodes. This translates
into constraining your update for one task to not conflict with an update for the previous task.

What if the gradient is going the wrong way? Paz and Ronzato take this gradient update
and project it to the closest possible vector that doesn't go the wrong way 
(The proof is in the pudding, eqn. 8 - 13 in the paper. It formulates the optimization as a projection
on to a cone).
 
[Gradient Update Projection Example][Gradient Update Projection Example]

 Above shows the graphical representation of the gradient update conditions, with the blue
    line being the update for the first task, while the red line is the gradient update for the current task. The right side
    shows an approximation of the optimized projection for the gradient when the dot product is negative.

### Does it work? ###
Yes. Well, kind of. 

The focus of this paper was to minimize Backwards Loss (aka
maximize Backwards Transfer). In this sense, they appear to succeed. However, 
the small improvements lack error bars, making an unconvincing case (#DLNeedsErrorBars). 
Forward Transfer is negligible on all but one experiment (there were three total).

[Results from Paper]

The plots above show performance. The right hand side demonstrates
the accuracy on the first task as the consequent tasks are learned, which each different
colored bar indicating a start to learning for a new task.

#### Knitpicking ####

* The experiments compare against Elastic Weight Consolidation (EWC). However, 
EWC was tested and optimized for Reinforcement Learning and Atari Games. I wonder
if an earnest job of optimizing EWC for the tasks at hand was done. 

* There is still no metric for parameter conservation as a result of continual/shared learning. 
A curve showing the change in accuracy across a set of tasks while increasing 
the size of the overall network would be nice. It would be interesting to compare 
all the papers on this metric. You could also evaluate the similarity of tasks
(or how well a network learns similarities in tasks) through this method.

### Summary ###
Cool Method.  Nice Paper. Less than satisfying results. But in general a
solid step forward for continual learning/overcoming catastrophic
forgetting. 


[EWC]: https://arxiv.org/pdf/1612.00796.pdf
[PathNet]: https://arxiv.org/pdf/1701.08734.pdf
[iCARL]: https://arxiv.org/pdf/1611.07725.pdf
[Sluice Network]: https://arxiv.org/pdf/1705.08142.pdf
[Intelligent Synapses]: https://openreview.net/pdf?id=rJzabxSFg
[Metrics]: https://www.dropbox.com/s/qrj6sxkfruj42uk/Screen%20Shot%202017-07-31%20at%204.56.05%20PM.png?dl=0
[Gradient]: https://www.dropbox.com/s/jye3b3mco5fs277/Screen%20Shot%202017-07-31%20at%204.55.52%20PM.png?dl=0
[Results]: https://www.dropbox.com/s/qvr95xydhtlnijw/Screen%20Shot%202017-07-31%20at%204.55.41%20PM.png?dl=0
[GED]: https://arxiv.org/pdf/1706.08840.pdf
[backprop]:https://en.wikipedia.org/wiki/Backpropagation
[chainrule]:https://en.wikipedia.org/wiki/Chain_rule
[Gradient Update Equation]:https://www.dropbox.com/s/jye3b3mco5fs277/Screen%20Shot%202017-07-31%20at%204.55.52%20PM.png?dl=1
[Gradient Update Projection Example]: https://www.dropbox.com/s/jkdkk8bmz6btl77/Screen%20Shot%202017-07-31%20at%207.36.14%20PM.png?dl=1 "Projection Update"
[Results from Paper]:https://www.dropbox.com/s/qvr95xydhtlnijw/Screen%20Shot%202017-07-31%20at%204.55.41%20PM.png?dl=1

 
 

TLDR; Authors apply 6-layer and 9-layer (+3 affine) convolutional nets to character-level input and evaluate their models on Sentiment Analysis and Categorization tasks using (new) large-scale data sets. The authors don't use pre-trained word-embeddings, or any notion of words, and instead learn directly from character-level input with characters being encoded as one-hot vetors. This means the same model can be applied to any language (provided the vocabulary is small enough). The models presented in this paper beat BoW and word2vec baseline models.

### Data and model performance

Because existing ones were too small the authors collected several new datasets that don't have standard benchmarks. 

- DBpedia Ontology Classification: 560k training, 70k test.
- Amazon Reviews 5-class: 3M train, 650k test
- Amazon Reviews polar: 3.6M train, 400k test
- Yahoo! Answer topics 10-class: 1.4M train, 60k test
- AG news classification 4-class: 120k train, 1.9k test
- Sogou Chinese News 5-class: 450k train, 60k test

Model accuracy for small and large models:

- DBpedia: 98.02 / 98.27
- Amazon 5-class: 59.47 / 58.69
- Amazon 2-class: 94.50 / 94.49
- Yahoo 10-class: 70.16 / 70.45
- AG 4-class: 84.35 / 87.18
- Chinese 5-class: 91.35 / 95.12

#### Key Takeaways

- Pretty Standard CNN architecture applied to characters. Conv, ReLU, Maxppol, fully-connected. Filter sizes of 7 and 3. See paper for parameter details.
- Training takes a long time, presumably due to the size of the data. The authors quote 5 days per epoch on the large Amazon data set and large model.
- Authors can't handle large vocabularies, they romanize Chinese. 
- Authors experiment with randomly replacing words with synonyms, seems to give a small improvements:


#### Notes / Questions

- The authors claim to do "text understanding" and learn representations, but all experiments are on simple classification tasks. There is no evidence that the network actually learns meaningful high-level representations, and doesn't just memorize n-grams for example.
- These data sets are large, and the authors claim that they need large data sets, but there are no experiments in the paper that show this. How does performance vary with data size?
- The comparision with other models is lacking. I would have liked to see some of the other state-of-the-art model being compared, e.g. Kim's CNN. Comparing with BoW doesn't show much. As these models are openly available the comparison should have been easy.
- The romanization of Chinese is an ugly "hack" that goes against what the authors claim: Being language-independent and learning "from scratch".
- It's strange that the authors use a thesaurus as a means for training example augmentation, as a theraus is word-level and language-specific, something that the authors explicitly argue against in this paper. Perhaps could have used word (character-level) dropout instead.
- Are there any hyperparameters that were optimized? Authors don't mention any dev sets.
- Have the datasets been made publicly available? The authors complain that "the unfortunate fact in literature is that there are no large openly accessible datasets", but fail to publish their own.
- I'd expect the confustion matrix for the 5-star Amazon reviews to show mistakes coming from negations, but it doesn't, which suggests that the model really learns meaningful representations (such as negation).

#### Problem addressed: 
A new type of activation function

#### Summary: 
This paper propose a new activation function that computes a Lp norm from multiple projections on an input vector. The p value can be learned from training example, and can also be different for each hidden unit. The intuition is that 1) for different datasets there may exist different optimal p-values, so it make more sense to make p tunable; 2) allowing different unit take different p-values can potentially make the approximation of decision boundaries more efficient and more flexible. The empirical results support these two intuitions, and achieved comparable results on three datasets.

#### Novelty:
A generalization of pooling but applied through channels, when the data and weight vector dot product plus bias is constrained to non-negative case, the $L_\infty$ is equivalent to maxout unit.

#### Drawbacks:
Empirical performance is not very impressive, although evidence of supporting the intuition occurs.

#### Datasets:
MNIST, TFD, Pentomino

#### Resources:
http://arxiv.org/abs/1311.1780

#### Presenter:
Yingbo Zhou

Network training is very sensitive to learning rate and initialization factors. Each layer output distribution is different than its input distribution (called covariate shift) which implies that layers have to permanently adapt to new input distribution. In this paper the author introduce batch normalization, a new layer to reduce covariate shift.

_Dataset:_ [MNIST](http://yann.lecun.com/exdb/mnist/), [ImageNet](www.image-net.org/).

#### Inner workings:

Batch normalization fixes the means and variances of layer inputs for a training batch by computing the following normalization on each batch.  
[![screen shot 2017-04-13 at 10 21 39 am](https://cloud.githubusercontent.com/assets/17261080/24996464/4027fbba-2033-11e7-966a-2db3c0f1389d.png)](https://cloud.githubusercontent.com/assets/17261080/24996464/4027fbba-2033-11e7-966a-2db3c0f1389d.png)  
The parameters Gamma and Beta are then learned with a gradient descent.  
During inference the statistics are computed using unbiased estimators of the whole dataset (and not just the batch).

#### Results:

Batch normalization provides several advantages:

1.  Use of a higher learning rate without risk of divergence by stabilizing the gradient scale.
2.  Regularizes the model.
3.  Reduces the need for dropout.
4.  Avoid the network to get stuck when using saturating nonlinearities.

#### What to do?

1.  Add batch norm layer before activation layers.
2.  Increase the learning rate.
3.  Remove dropout.
4.  Reduce L2 weight regularization.
5.  Accelerate learning rate decay.
6.  Reduce picture distorsion for data augmentation.