{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6e0727ae",
   "metadata": {
    "origin_pos": 1
   },
   "source": [
    "# Multi-Head Attention\n",
    ":label:`sec_multihead-attention`\n",
    "\n",
    "\n",
    "In practice, given the same set of queries, keys, and values we may want our model to combine knowledge from\n",
    "different behaviors of the same attention mechanism,\n",
    "such as capturing dependencies of various ranges\n",
    "(e.g., shorter-range vs. longer-range) within a sequence.\n",
    "Thus, it may be beneficial to allow our attention mechanism to jointly use different representation subspaces of queries, keys, and values.\n",
    "\n",
    "\n",
    "To this end, instead of performing \n",
    "a single attention pooling,\n",
    "queries, keys, and values\n",
    "can be transformed\n",
    "with $h$ independently learned linear projections.\n",
    "Then these $h$ projected queries, keys, and values\n",
    "are fed into attention pooling in parallel.\n",
    "In the end,\n",
    "$h$ attention-pooling outputs\n",
    "are concatenated and \n",
    "transformed with another learned linear projection\n",
    "to produce the final output.\n",
    "This design\n",
    "is called *multi-head attention*,\n",
    "where each of the $h$ attention pooling outputs\n",
    "is a *head* :cite:`Vaswani.Shazeer.Parmar.ea.2017`.\n",
    "Using fully connected layers\n",
    "to perform learnable linear transformations,\n",
    ":numref:`fig_multi-head-attention`\n",
    "describes multi-head attention.\n",
    "\n",
    "![Multi-head attention, where multiple heads are concatenated then linearly transformed.](../img/multi-head-attention.svg)\n",
    ":label:`fig_multi-head-attention`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "3cf184a4",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-08-18T19:42:05.720112Z",
     "iopub.status.busy": "2023-08-18T19:42:05.719157Z",
     "iopub.status.idle": "2023-08-18T19:42:08.696163Z",
     "shell.execute_reply": "2023-08-18T19:42:08.694248Z"
    },
    "origin_pos": 3,
    "tab": [
     "pytorch"
    ]
   },
   "outputs": [],
   "source": [
    "import math\n",
    "import torch\n",
    "from torch import nn\n",
    "from d2l import torch as d2l"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "683faf27",
   "metadata": {
    "origin_pos": 6
   },
   "source": [
    "## Model\n",
    "\n",
    "Before providing the implementation of multi-head attention,\n",
    "let's formalize this model mathematically.\n",
    "Given a query $\\mathbf{q} \\in \\mathbb{R}^{d_q}$,\n",
    "a key $\\mathbf{k} \\in \\mathbb{R}^{d_k}$,\n",
    "and a value $\\mathbf{v} \\in \\mathbb{R}^{d_v}$,\n",
    "each attention head $\\mathbf{h}_i$  ($i = 1, \\ldots, h$)\n",
    "is computed as\n",
    "\n",
    "$$\\mathbf{h}_i = f(\\mathbf W_i^{(q)}\\mathbf q, \\mathbf W_i^{(k)}\\mathbf k,\\mathbf W_i^{(v)}\\mathbf v) \\in \\mathbb R^{p_v},$$\n",
    "\n",
    "where \n",
    "$\\mathbf W_i^{(q)}\\in\\mathbb R^{p_q\\times d_q}$,\n",
    "$\\mathbf W_i^{(k)}\\in\\mathbb R^{p_k\\times d_k}$,\n",
    "and $\\mathbf W_i^{(v)}\\in\\mathbb R^{p_v\\times d_v}$\n",
    "are learnable parameters and\n",
    "$f$ is attention pooling,\n",
    "such as\n",
    "additive attention and scaled dot product attention\n",
    "in :numref:`sec_attention-scoring-functions`.\n",
    "The multi-head attention output\n",
    "is another linear transformation via \n",
    "learnable parameters\n",
    "$\\mathbf W_o\\in\\mathbb R^{p_o\\times h p_v}$\n",
    "of the concatenation of $h$ heads:\n",
    "\n",
    "$$\\mathbf W_o \\begin{bmatrix}\\mathbf h_1\\\\\\vdots\\\\\\mathbf h_h\\end{bmatrix} \\in \\mathbb{R}^{p_o}.$$\n",
    "\n",
    "Based on this design, each head may attend\n",
    "to different parts of the input.\n",
    "More sophisticated functions \n",
    "than the simple weighted average can be expressed.\n",
    "\n",
    "## Implementation\n",
    "\n",
    "In our implementation,\n",
    "we [**choose the scaled dot product attention\n",
    "for each head**] of the multi-head attention.\n",
    "To avoid significant growth of computational cost and parametrization cost,\n",
    "we set $p_q = p_k = p_v = p_o / h$.\n",
    "Note that $h$ heads can be computed in parallel\n",
    "if we set the number of outputs \n",
    "of linear transformations\n",
    "for the query, key, and value\n",
    "to $p_q h = p_k h = p_v h = p_o$.\n",
    "In the following implementation,\n",
    "$p_o$ is specified via the argument `num_hiddens`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "bdc6ec21",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-08-18T19:42:08.702133Z",
     "iopub.status.busy": "2023-08-18T19:42:08.701108Z",
     "iopub.status.idle": "2023-08-18T19:42:08.710324Z",
     "shell.execute_reply": "2023-08-18T19:42:08.709226Z"
    },
    "origin_pos": 8,
    "tab": [
     "pytorch"
    ]
   },
   "outputs": [],
   "source": [
    "class MultiHeadAttention(d2l.Module):  #@save\n",
    "    \"\"\"Multi-head attention.\"\"\"\n",
    "    def __init__(self, num_hiddens, num_heads, dropout, bias=False, **kwargs):\n",
    "        super().__init__()\n",
    "        self.num_heads = num_heads\n",
    "        self.attention = d2l.DotProductAttention(dropout)\n",
    "        self.W_q = nn.LazyLinear(num_hiddens, bias=bias)\n",
    "        self.W_k = nn.LazyLinear(num_hiddens, bias=bias)\n",
    "        self.W_v = nn.LazyLinear(num_hiddens, bias=bias)\n",
    "        self.W_o = nn.LazyLinear(num_hiddens, bias=bias)\n",
    "\n",
    "    def forward(self, queries, keys, values, valid_lens):\n",
    "        # Shape of queries, keys, or values:\n",
    "        # (batch_size, no. of queries or key-value pairs, num_hiddens)\n",
    "        # Shape of valid_lens: (batch_size,) or (batch_size, no. of queries)\n",
    "        # After transposing, shape of output queries, keys, or values:\n",
    "        # (batch_size * num_heads, no. of queries or key-value pairs,\n",
    "        # num_hiddens / num_heads)\n",
    "        queries = self.transpose_qkv(self.W_q(queries))\n",
    "        keys = self.transpose_qkv(self.W_k(keys))\n",
    "        values = self.transpose_qkv(self.W_v(values))\n",
    "\n",
    "        if valid_lens is not None:\n",
    "            # On axis 0, copy the first item (scalar or vector) for num_heads\n",
    "            # times, then copy the next item, and so on\n",
    "            valid_lens = torch.repeat_interleave(\n",
    "                valid_lens, repeats=self.num_heads, dim=0)\n",
    "\n",
    "        # Shape of output: (batch_size * num_heads, no. of queries,\n",
    "        # num_hiddens / num_heads)\n",
    "        output = self.attention(queries, keys, values, valid_lens)\n",
    "        # Shape of output_concat: (batch_size, no. of queries, num_hiddens)\n",
    "        output_concat = self.transpose_output(output)\n",
    "        return self.W_o(output_concat)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27562ce8",
   "metadata": {
    "origin_pos": 11
   },
   "source": [
    "To allow for [**parallel computation of multiple heads**],\n",
    "the above `MultiHeadAttention` class uses two transposition methods as defined below.\n",
    "Specifically,\n",
    "the `transpose_output` method reverses the operation\n",
    "of the `transpose_qkv` method.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4da9ac2c",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-08-18T19:42:08.714864Z",
     "iopub.status.busy": "2023-08-18T19:42:08.714207Z",
     "iopub.status.idle": "2023-08-18T19:42:08.723031Z",
     "shell.execute_reply": "2023-08-18T19:42:08.722024Z"
    },
    "origin_pos": 13,
    "tab": [
     "pytorch"
    ]
   },
   "outputs": [],
   "source": [
    "@d2l.add_to_class(MultiHeadAttention)  #@save\n",
    "def transpose_qkv(self, X):\n",
    "    \"\"\"Transposition for parallel computation of multiple attention heads.\"\"\"\n",
    "    # Shape of input X: (batch_size, no. of queries or key-value pairs,\n",
    "    # num_hiddens). Shape of output X: (batch_size, no. of queries or\n",
    "    # key-value pairs, num_heads, num_hiddens / num_heads)\n",
    "    X = X.reshape(X.shape[0], X.shape[1], self.num_heads, -1)\n",
    "    # Shape of output X: (batch_size, num_heads, no. of queries or key-value\n",
    "    # pairs, num_hiddens / num_heads)\n",
    "    X = X.permute(0, 2, 1, 3)\n",
    "    # Shape of output: (batch_size * num_heads, no. of queries or key-value\n",
    "    # pairs, num_hiddens / num_heads)\n",
    "    return X.reshape(-1, X.shape[2], X.shape[3])\n",
    "\n",
    "@d2l.add_to_class(MultiHeadAttention)  #@save\n",
    "def transpose_output(self, X):\n",
    "    \"\"\"Reverse the operation of transpose_qkv.\"\"\"\n",
    "    X = X.reshape(-1, self.num_heads, X.shape[1], X.shape[2])\n",
    "    X = X.permute(0, 2, 1, 3)\n",
    "    return X.reshape(X.shape[0], X.shape[1], -1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8ceb26d",
   "metadata": {
    "origin_pos": 16
   },
   "source": [
    "Let's [**test our implemented**] `MultiHeadAttention` class\n",
    "using a toy example where keys and values are the same.\n",
    "As a result,\n",
    "the shape of the multi-head attention output\n",
    "is (`batch_size`, `num_queries`, `num_hiddens`).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "18451bc5",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2023-08-18T19:42:08.726610Z",
     "iopub.status.busy": "2023-08-18T19:42:08.726042Z",
     "iopub.status.idle": "2023-08-18T19:42:08.759713Z",
     "shell.execute_reply": "2023-08-18T19:42:08.758787Z"
    },
    "origin_pos": 17,
    "tab": [
     "pytorch"
    ]
   },
   "outputs": [],
   "source": [
    "num_hiddens, num_heads = 100, 5\n",
    "attention = MultiHeadAttention(num_hiddens, num_heads, 0.5)\n",
    "batch_size, num_queries, num_kvpairs = 2, 4, 6\n",
    "valid_lens = torch.tensor([3, 2])\n",
    "X = torch.ones((batch_size, num_queries, num_hiddens))\n",
    "Y = torch.ones((batch_size, num_kvpairs, num_hiddens))\n",
    "d2l.check_shape(attention(X, Y, Y, valid_lens),\n",
    "                (batch_size, num_queries, num_hiddens))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0a4e536",
   "metadata": {
    "origin_pos": 24
   },
   "source": [
    "## Summary\n",
    "\n",
    "Multi-head attention combines knowledge of the same attention pooling \n",
    "via different representation subspaces of queries, keys, and values.\n",
    "To compute multiple heads of multi-head attention in parallel, \n",
    "proper tensor manipulation is needed.\n",
    "\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Visualize attention weights of multiple heads in this experiment.\n",
    "1. Suppose that we have a trained model based on multi-head attention and we want to prune less important attention heads to increase the prediction speed. How can we design experiments to measure the importance of an attention head?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "08c502f7",
   "metadata": {
    "origin_pos": 26,
    "tab": [
     "pytorch"
    ]
   },
   "source": [
    "[Discussions](https://discuss.d2l.ai/t/1635)\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  },
  "required_libs": []
 },
 "nbformat": 4,
 "nbformat_minor": 5
}