Answers.Body: <p>Say you have 3-dimensional tensors Q &amp; K of shape <code>(B, T, C)</code> (for Batch, Time, and Channels).</p>
  <ol>
  <li>K is transposed. 'Transposing' a 3-d tensor in this case means switching around the last two dimensions. Hence <code>shape(K.T) = (B, C, T)</code>.</li>
  <li>Q and K.T are matrix multiplied. Matrix multiplication is done on a per-sample basis. Logically, samples are not mixed. Hence we get <code>matmul(Q, K.T)</code> gives the matrix multiplication <code>(B, T, C) matmul (B, C, T) -&gt; (B, T, T)</code>
  <ul>
  <li>Think of it like this. Take the batch apart into individual samples, and simply matrix-multiply the individual samples.</li>
  </ul>
  </li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-18T00:44:00.007Z
Answers.Text: I was hoping there'd be an Eigen equivalent of numpy and TF's einsum, specifically something like "abc,adc->abd". They have a merge request open for it (https://gitlab.com/libeigen/eigen/-/merge_requests/52/commits?commit_id=3b1dcc4a15b7e60b2f4d991719950b8027c1adc2) but it's a big feature and, according to discussion, they're putting it off util after version 3.4.
Answers.UserDisplayName: rkuang25
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-18T06:02:44.377Z
Answers.Text: I cant help you with imementations in Eigen unfortunately. I can pnly describe the theoretical answer to your question, which i hope I have done. For implementation questions, the DS SE is a better place to start.
Answers.UserDisplayName: Robin van Hoorn
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-18T06:05:31.583Z
Answers.Text: The theoretical portion is simple, it's just the implementation in Eigen that I'm having difficulty. I have opted for a for-loop with omp parallel instead. For large enough tensors, I found that a for-loop with omp parallel and chip/slice is also nearly as fast.
Answers.UserDisplayName: rkuang25
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-18T06:54:42.673Z
Answers.Text: The question "How Does Self-Attention Query and Key Multiplication Work For Batched Inputs?" and i get the idea that that is answered. If you'd want advice on implementation the [DSSE](https://datascience.stackexchange.com/) is a better place to open up a question.
Answers.UserDisplayName: Robin van Hoorn
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-18T07:12:02.007Z
Answers.Text: Thank you Robin. I have arrived at a solution already.
Answers.UserDisplayName: rkuang25
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-18T07:15:10.327Z
Answers.Text: Great! Please guve the answer a checkmark & upvote if its helped solve the question, then future visitors wil have a better time finding what they are looking for
Answers.UserDisplayName: Robin van Hoorn
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-17T18:31:30.813Z
Answers.LastActivityDate: 2023-05-17T18:31:30.813Z
Answers.UserDisplayName: Robin van Hoorn
Body: <p>I don't understand how self-attention works with batched values for the <span class="math-container">$Q \times K^T $</span> step. According to the diagram below (assume 1 head), once we get past the first 3 linear steps, we arrive at the equation. <span class="math-container">$$softmax(\frac{Q \, K^T}{\sqrt{d_k}})V$$</span>
  Assuming Q and K have dimensions <span class="math-container">$[\text{batch}, \text{sequence}, \text{key_dim}]$</span>, if the tensor contraction goes like <span class="math-container">$$Q \, K^T = [\text{batch}_q, \text{sequence}_q, \text{query_dim}_q] \times [\text{batch}_k, \text{key_dim}_k, \text{sequence}_k] = [\text{batch}_q, \text{batch}_k, \text{query_dim}_q, \text{key_dim}_k]$$</span>
  there is an extra batch dimension in the result.</p>
  <p>I can avoid this extra batch dimension by doing a for-loop over the batch dimension and compute the formula 1-to-1 for each query and key. But one of the benefits of self-attention is that it's parallelizable so there must be a way to do this without a for-loop. How do I achieve this?</p>
  <p><a href="https://i.sstatic.net/xBov2.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/xBov2.png" alt="enter image description here" /></a></p>
  <p>With Eigen Tensor I have these incorrect duplicate results</p>
  <pre><code>Eigen::Tensor&lt;double, 3&gt; query(2, 2, 3);
  query.setValues({{
                           {1, 6, 9},
                           {8, 7, 11}},
  
                   {       {1, 6, 9},
                           {8, 7, 11}}});
  
  Eigen::Tensor&lt;double, 3&gt; key(2, 2, 3);
  key.setValues({{
                           {4, 5, 0},
                           {10, 15, 7}},
  
                   {       {4, 5, 0},
                           {10, 15, 7}}});
  
  // contract along last dim of query and key
  Eigen::array&lt;Eigen::IndexPair&lt;int&gt;, 1&gt; matmul{Eigen::IndexPair&lt;int&gt;(2, 2)};
  
  Eigen::Tensor&lt;double, 4&gt; qk_t = query.contract(key, matmul);
  
  std::cout &lt;&lt; &quot;QxK_T: dimensions&quot; &lt;&lt; qk_t.dimensions() &lt;&lt; &quot;\n&quot; &lt;&lt; qk_t &lt;&lt; &quot;\n&quot;;
  
  QxK_T: [2, 2, 2, 2]
  [[[[ 34, 163],
     [ 34, 163]],
  
    [[ 67, 262],
     [ 67, 262]]],
  
  
   [[[ 34, 163],
     [ 34, 163]],
  
    [[ 67, 262],
     [ 67, 262]]]]
  </code></pre>
  
Tags: <neural-networks><natural-language-processing><attention><linear-algebra>
Title: How Does The Scaled Dot Product's Dimensions Work Out In Mult-Head Attention?
UserDisplayName: rkuang25
ThreadText: # How Does The Scaled Dot Product's Dimensions Work Out In Mult-Head Attention?
  
  (Asked by: username_0 on 2023-05-11)
  
  I don't understand how self-attention works with batched values for the $Q \times K^T $ step. According to the diagram below (assume 1 head), once we get past the first 3 linear steps, we arrive at the equation. $$softmax(\frac{Q \, K^T}{\sqrt{d_k}})V$$
  Assuming Q and K have dimensions $[\text{batch}, \text{sequence}, \text{key_dim}]$, if the tensor contraction goes like $$Q \, K^T = [\text{batch}_q, \text{sequence}_q, \text{query_dim}_q] \times [\text{batch}_k, \text{key_dim}_k, \text{sequence}_k] = [\text{batch}_q, \text{batch}_k, \text{query_dim}_q, \text{key_dim}_k]$$
  there is an extra batch dimension in the result.
  I can avoid this extra batch dimension by doing a for-loop over the batch dimension and compute the formula 1-to-1 for each query and key. But one of the benefits of self-attention is that it's parallelizable so there must be a way to do this without a for-loop. How do I achieve this?
  
  With Eigen Tensor I have these incorrect duplicate results
  Eigen::Tensor query(2, 2, 3);
  query.setValues({{
                           {1, 6, 9},
                           {8, 7, 11}},
  
                   {       {1, 6, 9},
                           {8, 7, 11}}});
  
  Eigen::Tensor key(2, 2, 3);
  key.setValues({{
                           {4, 5, 0},
                           {10, 15, 7}},
  
                   {       {4, 5, 0},
                           {10, 15, 7}}});
  
  // contract along last dim of query and key
  Eigen::array, 1> matmul{Eigen::IndexPair(2, 2)};
  
  Eigen::Tensor qk_t = query.contract(key, matmul);
  
  std::cout << "QxK_T: dimensions" << qk_t.dimensions() << "\n" << qk_t << "\n";
  
  QxK_T: [2, 2, 2, 2]
  [[[[ 34, 163],
     [ 34, 163]],
  
    [[ 67, 262],
     [ 67, 262]]],
  
  
   [[[ 34, 163],
     [ 34, 163]],
  
    [[ 67, 262],
     [ 67, 262]]]]
  
  **Tags:** neural-networks, natural-language-processing, attention, linear-algebra
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-05-17. Score: 1
  
  Say you have 3-dimensional tensors Q & K of shape `(B, T, C)` (for Batch, Time, and Channels).
  
  1. K is transposed. 'Transposing' a 3-d tensor in this case means switching around the last two dimensions. Hence `shape(K.T) = (B, C, T)`.
  2. Q and K.T are matrix multiplied. Matrix multiplication is done on a per-sample basis. Logically, samples are not mixed. Hence we get `matmul(Q, K.T)` gives the matrix multiplication `(B, T, C) matmul (B, C, T) -> (B, T, T)`
     * Think of it like this. Take the batch apart into individual samples, and simply matrix-multiply the individual samples.
  
  > **Comments:**
  > **username_0**: I was hoping there'd be an Eigen equivalent of numpy and TF's einsum, specifically something like "abc,adc->abd". They have a merge request open for it (https://gitlab.com/libeigen/eigen/-/merge_requests/52/commits?commit_id=3b1dcc4a15b7e60b2f4d991719950b8027c1adc2) but it's a big feature and, according to discussion, they're putting it off util after version 3.4.  
  > **username_1**: I cant help you with imementations in Eigen unfortunately. I can pnly describe the theoretical answer to your question, which i hope I have done. For implementation questions, the DS SE is a better place to start.  
  > **username_0**: The theoretical portion is simple, it's just the implementation in Eigen that I'm having difficulty. I have opted for a for-loop with omp parallel instead. For large enough tensors, I found that a for-loop with omp parallel and chip/slice is also nearly as fast.  
  > **username_1**: The question "How Does Self-Attention Query and Key Multiplication Work For Batched Inputs?" and i get the idea that that is answered. If you'd want advice on implementation the [DSSE](https://datascience.stackexchange.com/) is a better place to open up a question.  
  > **username_0**: Thank you Robin. I have arrived at a solution already.  
  > **username_1**: Great! Please guve the answer a checkmark & upvote if its helped solve the question, then future visitors wil have a better time finding what they are looking for  
  
  ---
  
  