Word2Vec

Ok, first blog post after a loooooooong time and the first one after baby #2. Have been wanting to catch up on readings for so long and what a better way than to write it and explain it myself. Lets begin with the model which has perhaps been beaten to death in the past few years. Word2Vec is a popular algorithm to generate word embeddings. The original algorithm by Mikolov, et al. has been proposed in the following references (1 and 2).

There are two key pieces of the model:

The Skip-gram model: In this model, we are given a corpus of word and its context (context for example is nearby word within a window size). The goal is to train a NN to predict the probability of every word in the vocabulary given the input word (hopefully the probability of context words would be much higher).
We thus need to find the parameters that maximize the probability: 
argmax Π p(c|w;θ)
where c is the set of contexts for the word w in the corpus
The conditional probability is usually parameterized using softmax as predicting the word probability is like multi-class classification. evc*vw Σevc'*vw where vw and vc represent the vector representation for the word and the context respectively and vc' ∈ C the set of all possible contexts .The intuition is to set the parameters such that the dot product is maximized which means that the vector representation for the word and the context should be as close as possible.

Negative Sampling: The next important intuition is that of negative sampling. If we examine the above eqn carefully, the computation of the denominator for softmax is expensive because the set of possible contexts can be very large. The idea of negative sampling is based upon the idea of noise-contrastive estimation. NCE converts the problem of multi class classification into binary classification. The training data comprises of the pairs of word and context as the positive class and random pairs of words as the negative class. Thus p(D=1|w, c; θ) represents the probability that the pair (w,c) came from the training data and p(D=0|w, c; θ) represents the probability that the pair did not belong to the training data. The binary classification objective can thus be written as 1 1 + e-vc'*vw
In word2vec, a small number of negative samples are selected from a unigram distribution such that frequent words are more likely to be selected as negative samples.

Here is the code snippet for word2vec using tensorflow taken from here: 
# Construct the variables for the NCE loss
nce_weights = tf.Variable(
        tf.truncated_normal([vocabulary_size, embedding_size],
                            stddev=1.0 / math.sqrt(embedding_size)))
nce_biases = tf.Variable(tf.zeros([vocabulary_size]))

nce_loss = tf.reduce_mean(
        tf.nn.nce_loss(weights=nce_weights,
                       biases=nce_biases,
                       labels=train_context,
                       inputs=embed,
                       num_sampled=num_sampled,
                       num_classes=vocabulary_size))

optimizer = tf.train.GradientDescentOptimizer(1.0).minimize(nce_loss)
Additional Resources:
word2vec Explained by Yoav Goldberg and Omer Levy
Chris McCormick's blog
word2vec code

PS1: #2 is such a charmer, kills me with the smile everyday :)
PS2: I am a guilty mom today as the #1 was not happy with me for rushing her in the morning, just want to hug her now :(

Comments

Post a Comment

Popular posts from this blog

MinHash, Bloom Filters and LSH

Lets talk about some large scale algorithms widely used in the document world. MinHash: Minhash is a really cute algorithm to determine how does a document compare to another. One simple way to compute document similarity is to compute the jaccard similarity between them. The jaccard similarity between the documents is computed as follows: def jaccard_similarity(set1: set, set2: set): if len(set1) == 0 or len(set2) == 0: return 0.0 common = len(set1.intersection(set2)) if common == 0: return 0.0 union = len(set1.union(set2)) return common / union One problem with Jaccard similarity is that it can take a lot of time to compute especially for large scale documents. The idea behind minhashing is to first operate on the space of document shingles. Shingles are basically any combination of k consecutive words of the document. For example, for the sentence "hi i am jaya" the possible 3 shingles are "hi i am" and "i am jaya&quo
Read more

Perceptron Algorithm

Image
The perceptron algorithm is a linear classifier using a linear function (w'x + b) to classify the points into two classes. The loss function for the perceptron algorithm just counts the points misclassified and then incrementally adjusts the weight vector and thus the decision boundary to appropriately classify the two classes. Perhaps this is the simplest algorithm one can think of to update the weight vector and is shown as follows: w(k+1) = w(k) + yt*xt if yt ≠ f(xt; w) i.e. we cycle through the training points and adjust the weight vector only if the points are misclassified. Note that our class labels are -1 and 1 and hence if the points are misclassified then y_t* f(xt; w) will be negative. In order to understand why the seemingly simple update rule works and leads to a convergence, lets closely examine it. One of the underlying assumption in the perceptron model is that the points are linearly separated hence there exists an w* such that y_t * f(xt; w*) ≥ γ for all t=1, 2
Read more

Logistic Regression

The logistic regression method even though called regression has a unique ability to give posterior probability values for a data point to belong to a particular class and hence serve as a discriminative function useful for classification. The idea is simple, to use the logistic sigmoid function on the linear function of feature vector. p(y = 1| x) = σ(w'x +b) The likelihood function can be written as p(t|w) = Π y_i^t_i*(1 - y_i)^(1 - t_i) ln p(t|w) = Σ t_i*ln(y_i) + (1 - t_i)*ln(1 - y_i) The error function is computed by taking the negative of the log likelihood function and is computed as follows: E(w) = -ln p(t|w) Now, ∇E(w) is computed as follows: y = 1 / (1 + exp(-w'x) Taking derivative of both sides, ∇y/∇w = exp(-w'x)(x)/(1 + exp(-w'x))^2 ∇y/∇w = xy(1-y) Substituting the value in ∇E(w), we get ∇ E(w) = Σ (y_i - t_i)*x_i The derivative of the error function is similar to the least squares problem, although we cannot obtain a closed form solution for it
Read more