Data Science Stack Exchange is a question and answer site for Data science professionals, Machine Learning specialists, and those interested in learning more about the field. It only takes a minute to sign up.
Sign up to join this community
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?
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} $$
