Answers.Body: <p>Yes. Technically your understanding is correct; i.e. if all input neurons are active, the computational complexity would be like you said: Q = V<span class="math-container">$\times$</span>D + N<span class="math-container">$\times$</span>D<span class="math-container">$\times$</span>H + H<span class="math-container">$\times$</span>V.</p>
  <p>So, if there are V words, the input, of course, will be a 1 of V one-hot vector.
  And since there are N words in the input, the input matrix will be of size N<span class="math-container">$\times$</span>V. If D is the dimensionality of the embedded vector, the projection matrix will be of size V<span class="math-container">$\times$</span>D.
  The product of the input matrix and the projection matrix will then have dimensions (N<span class="math-container">$\times$</span>V)<span class="math-container">$\cdot$</span>(V<span class="math-container">$\times$</span>D) = N<span class="math-container">$\times$</span>D.</p>
  <p>But remember that this is a time series problem and not all input words are available at any given time. For a N-gram model, only N inputs are active at any given time. Hence, of the total V matrix elements in the projection matrix, only N elements corresponding to the input one-hot vector are referenced/updated at any given time. The remaining elements are referenced/updated at a different time.</p>
  <p>As a result, at any given time, the input matrix will have dimension N<span class="math-container">$\times$</span>N, and the projection matrix will only have to be N<span class="math-container">$\times$</span>D. The product of these two matrices (N<span class="math-container">$\times$</span>N)<span class="math-container">$\cdot$</span>(N<span class="math-container">$\times$</span>D) will still have dimensions N<span class="math-container">$\times$</span>D. Hence the total complexity is Q = N<span class="math-container">$\times$</span>D + N<span class="math-container">$\times$</span>D<span class="math-container">$\times$</span>H + H<span class="math-container">$\times$</span>V.</p>
  <p>But in practice, this is implemented as a look up table rather than a matrix multiplication, as mentioned <a href="https://stackoverflow.com/questions/37889914/what-is-a-projection-layer-in-the-context-of-neural-networks">here</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-16T14:12:30.600Z
Answers.LastActivityDate: 2022-10-16T14:19:17.293Z
Answers.LastEditDate: 2022-10-16T14:19:17.293Z
Answers.UserDisplayName: shibonsk
Body: <p>I was reading <a href="https://arxiv.org/abs/1301.3781" rel="nofollow noreferrer">this paper</a> on word2vec, and came around the following description of a feedforward NNLM:</p>
  <blockquote>
  <p>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.</p>
  </blockquote>
  <p>The following expression is given for the computational complexity per training example:</p>
  <blockquote>
  <p>Q = N×D + N×D×H + H×V.</p>
  </blockquote>
  <p>The last two terms make sense to me: N×D×H is roughly the amount of parameters in a dense layer from the N×D-dimensional projection layer to the H hidden neurons, analogous for H×V. The first term, however, I expected to be V×D since the mapping from a one-hot encoded word to a D-dimensional vector is done via a V×D dimensional matrix. I came to that conclusion after reading <a href="https://www.jmlr.org/papers/volume3/bengio03a/bengio03a.pdf" rel="nofollow noreferrer">this referenced paper</a> and <a href="https://stackoverflow.com/a/37937675/7952998">this SO post</a> where the workings of the projection layer are explained in more detail.</p>
  <p>Perhaps I have misunderstood what is meant by &quot;training complexity&quot;.</p>
  
Tags: <neural-networks><word-embedding><word2vec><computational-complexity>
Title: How is the training comlexity of NNLM word2vec calculated?
UserDisplayName: MDescamps
ThreadText: # How is the training comlexity of NNLM word2vec calculated?
  
  (Asked by: username_0 on 2022-04-15)
  
  I was reading [this paper](https://arxiv.org/abs/1301.3781) on word2vec, and came around the following description of a feedforward NNLM:
  
  > 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 following expression is given for the computational complexity per training example:
  
  > Q = N×D + N×D×H + H×V.
  
  The last two terms make sense to me: N×D×H is roughly the amount of parameters in a dense layer from the N×D-dimensional projection layer to the H hidden neurons, analogous for H×V. The first term, however, I expected to be V×D since the mapping from a one-hot encoded word to a D-dimensional vector is done via a V×D dimensional matrix. I came to that conclusion after reading [this referenced paper](https://www.jmlr.org/papers/volume3/bengio03a/bengio03a.pdf) and [this SO post](https://stackoverflow.com/a/37937675/7952998) where the workings of the projection layer are explained in more detail.
  
  Perhaps I have misunderstood what is meant by "training complexity".
  
  **Tags:** neural-networks, word-embedding, word2vec, computational-complexity
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-10-16. Score: 0 | Accepted answer
  
  Yes. Technically your understanding is correct; i.e. if all input neurons are active, the computational complexity would be like you said: Q = V$\times$D + N$\times$D$\times$H + H$\times$V.
  
  So, if there are V words, the input, of course, will be a 1 of V one-hot vector.
  And since there are N words in the input, the input matrix will be of size N$\times$V. If D is the dimensionality of the embedded vector, the projection matrix will be of size V$\times$D.
  The product of the input matrix and the projection matrix will then have dimensions (N$\times$V)$\cdot$(V$\times$D) = N$\times$D.
  
  But remember that this is a time series problem and not all input words are available at any given time. For a N-gram model, only N inputs are active at any given time. Hence, of the total V matrix elements in the projection matrix, only N elements corresponding to the input one-hot vector are referenced/updated at any given time. The remaining elements are referenced/updated at a different time.
  
  As a result, at any given time, the input matrix will have dimension N$\times$N, and the projection matrix will only have to be N$\times$D. The product of these two matrices (N$\times$N)$\cdot$(N$\times$D) will still have dimensions N$\times$D. Hence the total complexity is Q = N$\times$D + N$\times$D$\times$H + H$\times$V.
  
  But in practice, this is implemented as a look up table rather than a matrix multiplication, as mentioned [here](https://stackoverflow.com/questions/37889914/what-is-a-projection-layer-in-the-context-of-neural-networks).
  
  
  ---
  
  