How exactly does word2vec work? - 1-4-5.net

1 How exactly does word2vec work ?David 31, 20161 IntroductionThe word2vec model [4] and its applications have recently attracted a great deal of attentionfrom the machine learning community. Thesedense vector representationsof words learnedby word2vec have remarkably been shown to carry semantic meanings and are useful ina wide range of use cases ranging from natural language processing to network flow the most amazing property of these word embeddings is that somehow these vectorencodings effectively capture the semantic meanings of the words. The question one mightask is how or why? The answer is that because the vectors adhere surprisingly well to ourintuition. For instance, words that we know to be synonyms tend to have similar vectorsin terms of cosine similarity and antonyms tend to have dissimilar vectors.

2 Even moresurprisingly, word vectors tend to obey the laws of analogy. For example, consider theanalogy Woman is to queen as man is to king . It turns out thatvqueen vwoman+vman vkingwherevqueen,vwoman,vmanandvkingare the word vectors for queen, woman, man, andking respectively. These observations strongly suggest that word vectors encode valuablesemantic information about the words that they that there are two main word2vec models: Continuous Bag of Words (CBOW) andSkip-Gram. In the CBOW model, we predict a word given a context (a context can besomething like a sentence). Skip-Gram is the opposite: predict the context given an inputword. Each of these models is examined document contains my notes on the word2vec .

3 NB: there are probably lots of mistakesin 1: Simple CBOW Model2 Continuous Bag-of-Words ModelThe simplest version of the continuous bag-of-word model (CBOW) is a single contextword version [3]. This is shown in Figure 1. Here we assume that there is only one wordconsidered per context, which means the model will predict one target word given onecontext word (which is similar to a bi-gram language model).In the scenario depicted in Figure 1,Vis the vocabulary size and the hyper-parameterNis the hidden layer size. The input vectorx={x1,x2,..,xV}is one-hot encoded, that is,that somexk= 1 and all otherxk = 0 fork6=k .The weights between between the input layer and the hidden layer can be represented bytheV NmatrixW.

4 Each row ofWis theN-dimensional vector representationvwof theassociated wordwin the input layer. Give a context (here a single word), and assumingagainxk= 1 andxk = 0 fork6=k (one-hot encoding), thenh=xTW=W(k,.):=vwI(1)This essentially copies thek-th row ofWtoh(this is due to the one-hot encoding ofx).HerevwIis the vector representation of the input wordwI. Note that this implies thatthe link (aka activation) function of the hidden units is linear (g(x) =x). Recall thatWV N= wVN (2)and2x= (3)so thath=xTW=[ xV] wVN (4)=[ xkwkN]# forxk= 1,xk = 0 fork6=k (5)=[ wkN]#k-th row ofW(6)=W(k,.)(7):=vWI(8)From the hidden layer to the output layer there is a different weight matrixW ={w i,j}which is aN Vmatrix.

5 Using this we can compute a score for each word in the vocabulary:uj=v wjT h(9)wherev wjis thej-th column of the matrixW . Note that the scoreujis a measure of thematch between the context and the next word1and is computed by taking the dot productbetween the predicted representation (v wj) and the representation of the candidate targetword (h=vwI).Now you can use a softmax (log linear) classification model to obtain the posterior distri-bution of words (turns out to be multinomial distribution):p(wj|wI) =yj=exp(uj)V j =1exp(uj )(10)1 Though almost all statistical language models predict the next word, it is also possible to model thedistribution of the word preceding the context or surrounded by the the output of thej-th unit of the output layer.

6 Substituting Equations 1 and9 into Equation 10 we getp(wj|wI) =exp(v woTvwI)V j =1exp(v w jTvwI)(11)Notes Both the input vectorxand the outputyare one-hot encoded vwandv ware two representations of the input wordw vwcomes from the rows ofW v wcomes from the columns ofW vwis usually called theinput vector v wis usually called theoutput Updating Weights: hidden layer to output layerThe training objective (for one training sample) is to maximize Equation 11, the conditionalprobability of observing the actual output wordwO(denote its index in the output layerasj ) given the input context wordwI(and with regard to the weights). That is,maxp(wO|wI) = maxyj (12)= max logyj (13)=uj logV j =1exp(uj ) := E(14)whereE= logp(wO|wI) is our loss function (which we want to minimize), andj isthe index of the actual output word (in the output layer).

7 Note (again) that this lossfunction can be understood as a special case of the cross-entropy measurement betweentwo probabilistic next step is to derive the update equation of the weights between hidden and outputlayers. Take the derivative ofEwith respect toj-th unit s net inputuj, we obtain4 E uj=yj tj:=ej(15)wheretj=1(j=j ), the indicator function, ,tjwill be 1 when thej-th unit is theactual output word, otherwisetj= 0 . Interestingly this derivative is simply the predictionerrorejof the output next step is to take the derivative onw ijto obtain the gradient on the hidden outputweights which (by the chain rule) is E w ij= E uj uj w ij=ej hi(16)since (sketch of the proof) E uj= (uj logV j =1exp(uj )) uj (17)= uj uj (logV j =1exp(uj )) uj(18)=tj exp(uj)V j =1exp(uj )(19)=tj yj# by Equations 10 and 15(20)Now, using stochastic gradient descent, we obtain the weight updating equation for hidden output weights.

8 W ij(new)=w ij(old) ej hi(21)and/orv wj(new)=v wj(old) ej h(22)where >0 is the learning rate (standard SGD),ej=yj tj(Equation 15),hiis thei-thunit in the hidden layer, andv wjis the output vector for Updating Weights: Input to hidden layersNow that we have the update equations forW , we an look atW. Here we take thederivative forEon the output of the hidden layer: E hi=V j=1 E uj uj hi(23)=V j=1ej w ij(24):= EHi(25)wherehiis the output of thei-th unit in the hidden layer,ujis defined in Equation 9 (theinput of thej-th unit to the output layer), andej=yj tjis the prediction error of thej-th word in the output layer. EH is anN-dimensional vector is the sum of the outputvectors of all words in the vocabulary, weighted by their prediction next job is to take the derivative ofEwith respect toW.

9 So first recall that thehidden layer performs a linear computation on the values from the input layer, specificallyhi=V k=1xk wki# see Equation 1(26)Now we can use the chain rule to get the derivative ofEwith respect toW, as follows(chain rule again): E wki= E hi hi wki(27)= EHi xk(28)and so (vector form) E W= EH x(29)From this we obain anV Nmatrix. Notice that since only one component ofxis non-zero, only one row of E Wis non-zero, and the value of that row is EH (an 1 Ndimensionalvector).Now we can write the update equation forWasv wI(new)=v wI(old) EH(30)HerevwIis a row ofW(namely the input vector of the (only) context word), and becauseof the one-hot encoding it is the only row ofWwhose derivative is 2: General CBOW Model3 General Continuous Bag-of-Words Model4 Skip-Gram ModelThe Skip-Gram model was introduced in Mikolov [3] and is depicted in Figure 3.

10 As youcan see, Skip-Gram is the opposite of CBOW; in Skip-Gram we predict the contextCgivenand input word, where is in CBOW we predict the word fromC. Basically the trainingobjective of the Skip-Gram model is to learn word vector representations that are good atpredicting nearby words in the associated context(s).For the Skip-Gram model we continue to usewwito denote the input vector of the onlyword on the input layer, and as a result have the same definition of the hidden-layer outputshas in Equation 1 (again this meanshcopies a row from the input hidden weight matrixWassociated with input wordwI). Recall that the definition ofhwash=W(k,.):=vwI(31)Now, at the output layer, instead of outputting one multinomial distribution, we outputCmultinomial distributions.