Before reading this post, I very recommend to read:
- Orignal GloVe paper
- Jon Gauthier’s post, which provides detailed explanation of python implementation. This post helps me a lot with C++ implementation.
After Tomas Mikolov et al. released word2vec tool, there was a boom of articles about words vector representations. One of the greatest is GloVe, which did a big thing while explaining how such algorithms work and refolmulating word2vec optimizations as special kind of factoriazation for word cooccurences matrix.
This post will consists of two main parts:
- Very brief introduction into GloVe algorithm.
- Details of implementation. I will show how to write fast, parallel asynchronous SGD with RcppParallel with adaptive learning rate in C++ using Intel TBB and RcppParallel.
Introduction to GloVe algorithm
GloVe algorithm consists of following steps:
- Collect word cooccurence statistics in a form of word coocurence matrix . Each element of such matrix represents measure of how often word i appears in context of word j. Usually we scan our corpus in followinf manner: for each term we look for context terms withing some area – window_size before and window_size after. Also we give less weight for more distand words (usually ).
- Define soft constraint for each word pair: . Here – vector for main word, – vector for context word, , – scalar biases for main and context words.
- Define cost function . Here is a weighting function which help us to prevent learning only from exremly common word pairs. GloVe authors choose following fucntion:
Main challenges I faced during implementation:
- Efficient cooccurence matrix creation.
- Implementation of efficient SGD for objective cost function minimization.
Cooccurence matrix creation
There are a few main issues with term cooccurence matrix (tcm):
- tcm should be sparse. We should be able to construct tcm for large vocabularies ( > 100k words).
- Fast lookups/inserts.
To meet requirement of sparsity we need to store data in associative array.
unordered_map is good candidate because of lookups/inserts complexity. I ended with
std::unordered_map< std::pair<uint32_t, uint32_t>, T > as container for sparse matrix in triplet form. Performance of
unordered_map heavily depends on underlying hash fucntion. Fortunately, we can pack
pair<uint32_t, uint32_t> into single
uint64_t in a determenistic way without any collisions.
Hash function for
std::pair<uint32_t, uint32_t> will look like:
Also note, that our cooccurence matrix is symmetrical, so internally we will store only elements above main diagonal.
Stochastic gradient descent
Now we should implement efficient parallel asynchronous stochastic gradient descent for word cooccurence matrix factorization, which is proposed in GloVe paper. Interesting thing - SGD inherently is serial algoritms, but when your problem is sparse, you can do asynchronous updates without any locks and achieve speedup proportional to number of cores on your machine! If you didn’t read HOGWILD!, I recomment to do that.
Let me remind formulation of SGD. We try to move parameters in a minimizing direction, given by with a learning rate :
So, we have to calculate gradients for our cost function:
We will use modification of SGD - AdaGrad algoritm. It automaticaly determines per-feature learning rate by tracking historical gradients, so that frequently occurring features in the gradients get small learning rates and infrequent features get higher ones. For AdaGrad implementation deteails see excellents Notes on AdaGrad by Chris Dyer.
Formulation of AdaGrad step and feature is following:
As we can see, at each iteration we need to keep track of sum over all historical gradients.
Parallel asynchronous AdaGrad
Actually we will use modification of AdaGrad - HOGWILD-style asynchronous AdaGrad 🙂 Main idea of HOGWILD! algorithm is very simple - don’t use any syncronizations. If your problem is sparse, allow threads to overwrite each other! This works and works fine. Again, see HOGWILD! paper for details and theoretical proof.
Now lets put all into the code.
As seen from analysis above,
GloveFit class should consists following parameters:
- word vecvors
w_j(for main and context words).
- word vectors square gradients
grad_sq_w_jfor adaptive learning rates.
- word biases square gradients
grad_sq_b_jfor adaptive learning rates.
max_costand other scalar model parameters.
Now we should to initialize parameters and perform iteration of SGD:
For actual text2vec code (with a few tricks) check this loop.
As discussed above, all these steps can be performed in parallel loop (over all non-zero word-coocurence scores). This can be easily done via OpenMP
parallel for and reduction:
#pragma omp parallel for reduction(+:global_cost). But there is one significant issue with this approach - it is very hard to make portable R-package with OpenMP support. By default it will work only on linux distributions, because:
clangon OS X don’t support OpenMP (of course you can install
gccfrom brew, but this also could be tricky).
- Rtools begins support of OpenMP on Windows only in 2015. But even modern realization has substantial overheads.
For more details see OpenMP-support section of Writing R Extensions manual.
Luckily we have a better alternative - Intel Thread Building Blocks library and RcppParallel package which provides
RMatrix wrapper classes for safe and convenient access to R data structures in a multi-threaded environment! Moreover it “just works” on main platforms - OS X, Windows, Linux. Have very positive experience with this library, thanks to Rcpp Core team and especially to JJ Allaire.
Using TBB is little bit trickier, then writing simple OpenMP
#pragma directives. You should implement functor which operates on a chunk of data and call
parallelFor on entire data collection. You can find useful (and simple) examples at RcppParallel examples section.
Putting all together
For now suppose, we have
partial_fit method in
GloveFit class with following signature (see actual code here):
- tcm in sparse triplet form
<x_irow, x_icol, x_val>
endpointers for a range on which we want to perform our SDG.
And performs SGD steps over this range - updates word vectors, gradients, etc. At the end it retruns value of accumulated cost function. Note, that internally this method modifies values members of the class.
Also note, that signature of
partial_fit is very similar to what we have to implement in our TBB functor. Now we are ready to write it:
As you can see, it is very similar to example form RcppParallel site. One diffrence - it has side-effects. By calling
partial_fit it modifies internal state of the input instance of
GloveFit class (which actually contains our GloVe model).
Now lets write
GloveFitter class, which will be callable from R via
Rcpp-modules. It will act as interface for fitting our model and take all input model parameters such as vocabulary size, desired word vectors size, initial AdaGrad learning rate, etc. Also we want to track cost between iterations and want to be able to perform some early stopping strategy between SGD iterations. For that purpose we keep our model in C++ class, so we can modify it “in place” at each SGD iteration (which can be problematic in R)
And create wrapper with
Now we can use
GloveFitter class from R: