Feedforward Neural Net Language Model - computational complexity (word2vec)

Question

While reading this paper on word2vec, I came around the following description of a feedforward Neural Net Language model (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-dimesnional 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 and this SO post where the workings of the projection layer are explained in more detail.

Perhaps I have misunderstood what is meant by "training complexity".

Answer 1

The SO post you reference contains the clue to answering this - in the last paragraph, starting "In practice you wouldn't even bother with the matrix multiplication". While the mapping matrix is $V\times D$ in size, as each one-hot encoded vector has 1 value set to 1 and all the other positions set to 0, there is no need to do the full matrix multiplication. Instead, each training example only uses $N\times D$ elements in the matrix. As the computational complexity is given per training example, the first term is $N\times D$.