Review: Order Matters: Sequence to Sequence for Sets

We now have good tooling for handling sequential inputs (e.g. RNNs).  But what about variable sized inputs that have no explicit ordering?  We can use a sequential model, but in what order do we feed our input?  The authors show empirical evidence that order matters, and describe a model which can be viewed as a simplified Neural Turing Machine for naturally handling sets as inputs.

Re-using the NTM tooling seems like a clever way to handle unordered inputs in a natural way.  It would have been great to see actual comparisons against existing models for all of the example problems: sure, a bi-directional LSTM isn’t the right way to handle an unordered input set, but how much am I losing by re-using my out of the box solution?  The authors demonstrate how some existing models change behavior if the input order is permuted, but I would have liked to see a side-by-side comparison against their proposal.

This paper continues the theme/direction of networks which get to take repeated looks at different parts of their input: i.e. they control what they look at, instead of being fed data and being forced to make do.  While in the NTM paper this felt like an interesting hack, it’s starting to seem more and more like a very reasonable way of solving real problems.

Review: Energy Based Generative Adversarial Networks

Link: https://arxiv.org/pdf/1609.03126v2.pdf

TLDR

  • Energy based framework makes for more robust models
  • An interesting bit: their model internally learns an auto-encoder.  But: it’s allowed to reconstruct total garbage for anything that’s not a valid image.
  • An exhaustive evaluation shows that EB-GANs are more robust to hyper-parameters than traditional GANs
  • They’re also really easy to understand!

Review:

I enjoyed this paper.  I would have liked if they had compressed/summarized the evaluation section, and provided instead some more background on how their model differs from a traditional GAN, but you can’t have everything.

The authors introduce energy-based generative adversarial networks (EB-GANs) for learning generative/discriminative models.  They argue that existing GAN models are difficult to train, as they can easily enter unstable regions.  The authors argue that the structure of EB-GANs makes them more robust to hyper-parameter settings.  This is primarily based on an argument (that I admittedly haven’t fully grasped) which shows that the decision problem faced by traditional GANs can be framed in an energy context.  In this context, the GAN is forced to learn a decision function with effectively an infinite margin, which the authors conjecture makes them difficult to train.  There’s a bit of hand-wavyness about this whole argument, but the results of the paper seem to bear it out.

The evaluation is exhaustive (and exhausting to read through), but the net result is clear: EB-GANs much more reliably achieve good training results.

Holographic Embeddings of Knowledge Graphs

http://arxiv.org/pdf/1510.04935v2.pdf

Review:

I really liked this paper.  The approach is refreshingly uncomplicated.  The use of circular correlation is well-argued, and the experimental results speak for themselves.

Synopsis:

Knowledge graph expansion is an active area of research.  If I know that

  • cats have fur
  • dogs have fur
  • mice have fur

It would be great if I could infer that “rabbits have fur”, even if it hasn’t been manually added.  In some sense, we can think of this as identifying a class of animals that are “furry”, assuming they share some other attributes.  We can represent a “fact” as a tuple: (relation, x, y), or for convenience relation(x, y).  In the case of our furry examples, we might write isFurry(cat).

The paper focuses on binary relations, e.g. bornIn(BarackObama, Hawaii).  When we consider expanding our knowledge graph, we’re interested in giving a probability that a given unknown relation R(a, b) is true.  The standard way to do this is to learn a representation for a and b, combine the representations in some manner, and compute a function p_r(a . b) to output a final probability.

The tricky part is how we combine our representations of a and b.  Many approaches first compute some distance function of the terms and and then apply a relationship specific adjustment.  Unfortunately, this fails to capture inter-dimensional relationships between terms and makes it difficult to learn relationship specific interactions.  Similar problems occur when we combine terms by projection or concatenation.

At the other end of the spectrum we can compute the tensor (outer) product of our representations.  Now we have every pair-wise interaction of a and b.  Unfortunately, we now need to learn d^2 parameters to make a prediction for each relation.

So what’s the way out?  The authors propose using circular correlation to combine the representations of and b.  

circular-correlation

This can be efficiently implemented using Fourier transforms.  The authors argue that this representation can be viewed as a compression of the full tensor product: we’re computing the interaction of each source term with various partitions of the target term.   These partitions correspond to requiring different parts of the target to be similar.

This operation is non-commutative so p_r(a, b) != p_r(b, a); it’s also dimension preserving, so we can still perform some interesting operations on the output before we emit our final probability.   Conveniently, the first dimension of the output is the dot product of a and b; if the overall similarity of the 2 vectors is important than this is trivially easy to make use of for a relation.

Finally, the authors note how this technique has many analogues to the idea of associative memory for neural networks.

A Deep Relevance Matching Model for Ad-hoc Retrieval

A Deep Relevance Matching Model for Ad-hoc Retrieval

Synopsis:

A lot of models have been proposed for using deep-learning for comparing text, but they don’t tend to work for the specific task of retrieval.  The paper makes the argument that this is because in relevance, we aren’t as interested in the very “soft” match between terms that typical NLP models would be.  Java and C++ are programming languages, but when I search for a “Java Tutorial”, I don’t want C++ tutorials instead (my example).

In particular, in relevance, we’re very interested in specific (query-term, document-term) interactions, as opposed to building some compressed model of the query and document, and computing a correlation.  While there are previous models (DeepMatch, MatchPyramid) that capture these local interactions, the authors argue that they don’t do enough to separate out the effect of exact matches vs. soft matches.

The main contribution of the paper appears to be the authors use of histogram features to capture a rich set of query-term, document-term interactions.  For each query term, they build a histogram of counts of distance(query-term, doc-term) term.  A separate bucket is maintained for exact matches.  (Terms are represented by their word2vec embeddings, trained on the input datasets).

Review:

I want to like this paper.  The histogram bucketing appears to be a clever technique to preserve local interactions without exploding the number of parameters a network has to work with.  Unfortunately, the evaluation seems weak, despite it’s apparent thoroughness: they didn’t evaluate one of the original claims of the paper (the importance of exact matches).  There also isn’t any evaluation of n-grams, which tend to be an extremely powerful ranking signal.  This makes it harder to compare against models which do try to handle n-grams (e.g. CNNs).  The small size of the training set would almost certainly require some pre-training step, but that could be interesting on it’s own.

Overall, I think the approach is interesting, and hopefully gets pushed on further; using NNs for relevance matching is still in it’s infancy; any reasonable ideas are worth investigating further.

Review: Named Entity Recognition with Bidirectional LSTM-CNNs

http://arxiv.org/pdf/1511.08308v5

Combining LSTMs with CNNs seems to a popular theme these days.  It makes sense: CNNs can be very fast to train for language recognition tasks, and are certainly easier to understand/debug for the most part.  This paper shows how to combine a word-level LSTM with a character level LSTM to effectively perform named-entity recognition.

The model closely follows the title.  A bi-directional LSTM is formed using input word embeddings (from GloVe, Google, or locally trained) and a few simple features that are useful for entity recognition: capitalization and a small set of lexicon features.  The lexicon features are simple but worth noting: effectively, they map a word to a BIOES annotation (begin, inside, outside, end, single) notation.  The entities used for the lexicon are primarily drawn from DBPedia.  The lexicon features are divided into 4 types: Location, Organization, Person and Misc.  This categorization seems rather arbitrary, but follows that specified by the dataset.

The detailed description of all of the hyper-parameters of the model was very nice to see.  While adaptive learning rate methods (e.g. AdaGrad) have made the learning rate less sensitive, it’s still useful to know the whole search space used for a model.  A note about the sensitivity of the model to the hyper-parameters would have been great as well.

It’s hard to quantify how much “deep learning” contributes to the results of this paper.  While the overall performance ends up being slightly better than previous work, it’s not by much.  As the authors suggest, the amount of manual feature engineering required does appear to be less for this model than in previous work: using the character level CNN effectively allows them to opt-out of engineering lexical features, and using LSTMs reduces the need to hunt for a way to identify a reasonable context.

Deep Neural Networks for YouTube Recommendations

https://research.google.com/pubs/archive/45530.pdf

This paper describes the system used for YouTube’s personalized recommendations.  It’s a somewhat typical “experience” paper, but notable in a few ways:

  • The scale is large: obviously YouTube has a huge number of users, and they are searching through a large recommendation space (~millions of videos).  They need to have high-performance models as a result, but they also have enough data to effectively train models with hundreds of millions of parameters.
  • They don’t use the now very popular recurrent models, instead relying on a standard feed-forward network with extensive feature engineering.
  • They don’t use an explicit matrix factorization model, which is quite common for this task.  There is an implicit factorization in the form of the embeddings learned as part of the network.
  • They find more evidence that hierarchical softmax isn’t as effective as negative sampling.

The overall model setup is refreshingly straightforward: a number of input features are fed as a single large vector; a number of fully connected layers with ReLUs is then applied before making a prediction.  Two different models are used: a “generative” model (not the standard usage of the term) is used to build a lookup vector to quickly identify related videos.  Then a more expensive model computes an individual score of each video.

The input features are roughly what you’d expect:

  • Video embedding: an embedding learned from  a users watch history.  To compact the embeddings into a fixed shape, they took the average over the input sequence.
  • Search embedding: an average of the embeddings of a users search queries.
  • Language embedding: not described well?  Some combination of a language model for the user (searches?) and that of the video.
  • Statistics on the last time the user watched, or was recommended/shown the video (e.g. last watch time, square(last watch time), sqrt(last watch time).
  • Population features: age, gender, geography.

The generator model uses the video and search embeddings, along with the population features to learn an embedding for each video.  This embedding can then be used with an approximate nearest neighbors lookup to select candidate videos for recommending.

The second model takes each of the videos from the generative and produces a score to order them.


Overall, I enjoyed reading the paper.  I would have liked the description of the features to be a bit more organized, but the approach used was refreshing in it’s pragmatism.  Seeing an effective use of deep learning at such large scale is interesting as well.

Review: Dark Silicon and the End of Multicore Scaling

Paper link: p365-esmaeilzadeh

Premise

Single core scaling stopped some number of years ago. But we’re okay, because we now have the “multi-core revolution” (I realllly hate that phrase). Or are we?

It turns out that another, very real wall is blocking future progress — power density. Already CPU designs strive mightily to shutdown or slowdown underutilized circuitry to save power. But we’re reaching the point where processors simply won’t ever be able to run “full-out”.

This paper explores the future of scaling by extrapolating based on a wide range of processors over time, and they find, rather compellingly, that we’re pretty much boned.

Details

The paper is pretty dense, but it boils down to the creation of a model parameterized by processor features:

  • number of cores
  • number of threads
  • CPU frequency
  • L1/L2/DRAM cache size, speed, miss rate
  • DRAM fetch width

and code features:

  • % code that is parallel
  • % read instructions

You can fit this model based on existing processors and their benchmark performance, as well as their power consumption and die area.

Once the model is created, now the fun starts — we can see how performance will scale with future process improvements (moving to 32, 22, 16…nm), or if we assume highly parallel code, we can see how to optimize our CPU design (lots of cores)!

The short of it

If we make optimistic assumptions for how power consumption drops with process scaling, we still end up with the sobering conclusion that we’re rapidly reaching the point where we won’t be able to power all of the parts of a chip. 128 cores aren’t as useful if we can’t keep them all running.

On the plus side, I can buy 1000 watt power supplies now, so I’m looking forward to my 16 processor, 16 core machine of the future. Welcome to the multiprocessor revolution!

Review: DThreads: Efficient Deterministic Multithreading

I’ve decided to try and be more pro-active about reading papers from the community. Since I tend to forget everything I read, it’s best I write down somewhere my thoughts for later reference — I’ve decided to post these reviews here in case they prove useful to others.

PDF of the paper

Overview:

This paper follows one of the latest fads in systems (NB: academics have fads just like fashionistas) — deterministic threading. The main idea behind all of these papers is to try and allow users to make use of multi-core/multi-threaded programming, but at the same time have it be deterministic. This is helpful as it ensures the behavior we see when testing is the same as what we see at runtime, and it also helps make it easier to recreate test failures.

This is a non-trivial problem, and it has a lot of work behind it already. The contribution with dthreads is that it, (a) claims high performance, and (b) provides a drop-in replacement for existing threads.

How does it work:

There’s a standard trick for d-threading, and DThreads uses it as well. It’s somewhat a kin to transactions in databases. First, split each thread into a separate world that can’t communicate with the other threads. Buffer all of the updates that would go to shared memory. Then, at a synchronization point (mutex lock, condition var, etc.), wait for all of the threads to finish their work, and then apply the shared memory changes in a deterministic fashion.

The DThreads way of handling this is to run each thread as a separate process. Whenever a commit point is reached, the processes determine which parts of memory they’ve changed, and commit them to shared memory at that time.

There are a number of things that need to be handled to make this all possible — you need to provide a deterministic malloc, you have to ensure threads are created and destroyed in a deterministic way, etc.

Why aren’t we using it today?

Two reasons, really.

Speed

DThreads is faster then previous work on the subject, but still can end up a lot slower then regular threading. This isn’t unexpected — you have to do more work, so you end up paying for it.

Correctness

DThreads, while being a drop-in replacement for pthreads, isn’t really a drop-in replacement for pthreads. Unfortunately for deterministic threading proponents, this type of code:

Thread 1:

while not done:
  sleep(0)

Thread 2:
... do some work ...
done = 1

where synchronization is handled outside the scope of the threading library is all too common in the wild. This forces the use of more expensive techniques then DThreads, which keeps determistic threading, for the moment, an academic exercise.

What did I think of the paper

It’s well written (which I expect of all SOSP papers), and presents a bunch of interesting tricks for improving performance and making things work. The fact that it requires all synchronization be performed through pthreads calls is on the face of it, reasonable, but sadly, it is far from realistic when it comes to running everyday applications.

Still, fun to read.