Neural lang based LM will outperform N-gram models
Goal - learn high quality word vectors from huge data sets with billions of data
2 notions -
1) similar words will be closer to each other
2) words can have multiple degrees of similarity
Earlier work -
feedforward NN with → linear projection layer + non linear hidden layer
→ used to learn word vector representation
To estimate continuous representation of words, many different types of model architectures were proposed -
Latent Semantic Analysis(LSA) and Latent Dirichlet Allocation(LDA)
on distributed representations of words learned by neural networks, as it was
previously shown that they perform significantly better than LSA for preserving linear regularities
among words [20, 31]; LDA moreover becomes computationally very expensive on large data sets.
to compare different model architectures we define first the computational complexity of a model as the number of parameters that need to be accessed to fully train the model. Next,
we will try to maximize the accuracy, while minimizing the computational complexity
{ computational complexity of a model - no of parameters needed to fully train the model }
For all the following models, the training complexity is proportional to
O = E × T × Q
where E is number of the training epochs, T is the number of the words in the training set and Q is
defined further for each model architecture. Common choice is E = 3 − 50 and T up to one billion.
All models are trained using stochastic gradient descent and backpropagation2.1 Feedforward Neural Net Language Model (NNLM)
The probabilistic feedforward neural network language model has been proposed in [1]. It consists
of input, projection, hidden and output layers. At the input layer, N previous words are encoded
using 1-of-V coding, where V is size of the vocabulary. The input layer is then projected to a
projection layer P that has dimensionality N × D, using a shared projection matrix. As only N
inputs are active at any given time, composition of the projection layer is a relatively cheap operation.
The NNLM architecture becomes complex for computation between the projection and the hidden
layer, as values in the projection layer are dense. For a common choice of N = 10, the size of the
projection layer (P) might be 500 to 2000, while the hidden layer size H is typically 500 to 1000
units. Moreover, the hidden layer is used to compute probability distribution over all the words in the vocabulary, resulting in an output layer with dimensionality V . Thus, the computational complexity per each training example is
Q = N × D + N × D × H + H × V
where the dominating term is H × V . However, several practical solutions were proposed for
avoiding it; either using hierarchical versions of the softmax [25, 23, 18], or avoiding normalized
models completely by using models that are not normalized during training [4, 9]. With binary tree
representations of the vocabulary, the number of output units that need to be evaluated can go down to around log2(V ). Thus,
most of the complexity is caused by the term N × D × H.
In our models, we use hierarchical softmax where the vocabulary is represented as a Huffman binary tree. This follows previous observations that the frequency of words works well for obtaining classes in neural net language models [16]. Huffman trees assign short binary codes to frequent words, and this further reduces the number of output units that need to be evaluated: while balanced binary tree would require log2(V ) outputs to be evaluated, the Huffman tree based hierarchical softmax requires only about log2(Unigram perplexity(V )). For example when the vocabulary size is one million words, this results in about two times speedup in evaluation. While this is not crucial speedup for neural network LMs as the computational bottleneck is in the N ×D×H term, we will later propose architectures that do not have hidden layers and thus depend heavily on the efficiency of the softmax normalization.
{ huffman tree use binary codes for freq words, decreasing computation in log2(V) time further, 4 layers and there is some complexity thing associated }
2.2 Recurrent Neural Net Language Model (RNNLM)
Recurrent neural network based language model has been proposed to overcome certain limitations of the feedforward NNLM, such as the need to specify the context length (the order of the model N),
and because theoretically RNNs can efficiently represent more complex patterns than the shallow
neural networks [15, 2]. The RNN model does not have a projection layer; only input, hidden and
output layer. What is special for this type of model is the recurrent matrix that connects hidden
layer to itself, using time-delayed connections. This allows the recurrent model to form some kind
of short term memory, as information from the past can be represented by the hidden layer state that
gets updated based on the current input and the state of the hidden layer in the previous time step.
The complexity per training example of the RNN model is
Q = H × H + H × V, (3)
where the word representations D have the same dimensionality as the hidden layer H. Again, the
term H × V can be efficiently reduced to H × log2(V ) by using hierarchical softmax. Most of the
complexity then comes from H × H.{ there are some limitations of NNLM, like RNN is better at remembering more relations than NN, and something associated with context length)
The main observation from the previous
section was that
most of the complexity is caused by the non-linear hidden layer in the model.The new architectures directly follow those proposed in our earlier work [13, 14], where it was
found that neural network language model can be successfully trained in two steps: first, continuous
word vectors are learned using simple model, and then the N-gram NNLM is trained on top of these distributed representations of words
3.1 Continuous Bag-of-Words Model
The first proposed architecture is similar to the feedforward NNLM, where the non-linear hidden
layer is removed and the projection layer is shared for all words (not just the projection matrix);
thus, all words get projected into the same position (their vectors are averaged). We call this
architecture a bag-of-words model as the order of words in the history does not influence the projection.
Furthermore, we also use words from the future; we have obtained the best performance on the task
introduced in the next section by building a log-linear classifier with four future and four history
words at the input, where the training criterion is to correctly classify the current (middle) word.
Training complexity is then
Q = N × D + D × log2(V ). (4)
We denote this model further as CBOW, as unlike standard bag-of-words model, it uses continuous
distributed representation of the context. The model architecture is shown at Figure 1. Note that the weight matrix between the input and the projection layer is shared for all word positions in the same way as in the NNLM3.2 Continuous Skip-gram Model
The second architecture is similar to CBOW, but instead of predicting the current word based on the
context, it tries to
maximize classification of a word based on another word in the same sentence.
More precisely, we use each current word as an input to a log-linear classifier with continuous
projection layer, and predict words within a certain range before and after the current word. We
found that increasing the range improves quality of the resulting word vectors, but it also increases
the computational complexity. Since the more distant words are usually less related to the current
word than those close to it, we give less weight to the distant words by sampling less from those
words in our training examples.
The training complexity of this architecture is proportional to
Q = C × (D + D × log2(V )),where
C is the maximum distance of the words. Thus, if we choose C = 5, for each training word
we will select randomly a number R in range < 1; C >, and then use R words from history andR words from the future of the current word as correct labels. This will require us to do R × 2
word classifications, with the current word as input, and each of the R + R words as output. In the
following experiments, we use C = 10.
To find a word that is similar to small in the same sense as
biggest is similar to big, we can simply compute vector X = vector(”biggest”)−vector(”big”) +
vector(”small”). Then, we search in the vector space for the word closest to
X measured by cosine
distance, and use it as the answer to the question (we discard the input question words during this
search). When the word vectors are well trained, it is possible to find the correct answer (word
smallest) using this method.
For the experiments reported in Tables 2 and 4, we used three training epochs with stochastic gradient descent and backpropagation. We chose
starting learning rate 0.025 and decreased it linearly, so that it approaches zero at the end of the last training epoch.We observed that it is possible to train high
quality word vectors using very simple model architectures, compared to the popular neural network models (both feedforward and recurrent).
An interesting task where the word vectors have recently been shown to significantly outperform the
previous state of the art is the SemEval-2012 Task 2 [11]. The publicly available RNN vectors were
used together with other techniques to achieve over
50% increase in Spearman’s rank correlation over the previous best result