0
$\begingroup$

I read the following claim in this paper https://arxiv.org/pdf/1803.06305.pdf:

In one gate/cell, $W_{∗x} x_t + W_{∗r} y_{t−1}$ can be combined/fused in one matrix-vector multiplication by concatenating the matrix and vector as $W_{∗(x r)}[x_t, y_{t−1}]$ (page 3).

How is this the case? I would have thought since $W_{∗x}$ and $W_{∗r}$ are different matrices, the computations would have to be done separately? And does this combination (if it's really possible) save computational time?

$\endgroup$

1 Answer 1

3
$\begingroup$

It's a usual trick in deep learning. Matrix multiplications can be done in parallel:

$$ (A.B)_{ij} = \sum_{k} A_{ik} B_{kj} $$

since you have to do this sum for each component, then you can divide your computing time by the number of processes you use - i.e. compute these components several at a time rather than one by one. Assuming you use a naive matrix computation then you have a $O(\dfrac{n^3}{K})$ with K number of processes. That's why GPUs are so much better for deep learning (usually have hundreds if not thousands of cores) which allows you to divide by a factor of several 100s at worst the time to compute the matrix multiplication.

In this particular case, you can use block matrix multiplications (we expend the rules of matrix multiplications to matrices):

$$ \mathbf{𝑊}_{∗(𝑥𝑟)}[𝑥_𝑡,𝑦_{𝑡−1}]= \begin{bmatrix} \mathbf{𝑊}_{∗𝑥} & \mathbf{0} \\ \mathbf{0} & \mathbf{𝑊}_{∗y} \end{bmatrix}[𝑥_𝑡,𝑦_{𝑡−1}] $$

if you apply the traditional matrix multiplications (keeping in mind matrix sizes), you get:

$$ \mathbf{𝑊}_{∗(𝑥𝑟)}[𝑥_𝑡,𝑦_{𝑡−1}]=\mathbf{𝑊}_{∗𝑥}𝑥_𝑡 + \mathbf{0} * 𝑦_{𝑡−1} + \mathbf{0} * 𝑥_𝑡 + \mathbf{𝑊}_{∗y} * 𝑦_{𝑡−1} =\mathbf{𝑊}_{∗𝑥}𝑥_𝑡 + \mathbf{𝑊}_{∗y} * 𝑦_{𝑡−1} $$

$\endgroup$
2
  • $\begingroup$ Thank you. You've clearly explained how the computations are combined. Can you go into a bit more detail on the time complexity, i.e. is it O(n^3/2) for the case where you put them together compared to O(n^3) for the separate additions? (Also, what's n?) $\endgroup$ Commented Sep 3, 2020 at 17:46
  • $\begingroup$ hi, anything on this? $\endgroup$ Commented Sep 3, 2020 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.