{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=multihead-attention-md-1 fw=all -->\n",
    "\n",
    "# Multi-Head and Cross-Attention\n",
    "\n",
    "Scaled dot product attention, as built in that section,\n",
    "gives each query exactly one probability distribution over the keys, and\n",
    "returns the correspondingly weighted average of the values. One distribution\n",
    "per query is a real restriction: a token in a sentence participates in several\n",
    "relations at once — it agrees with a verb, refers back to an entity, sits\n",
    "inside a phrase — and a single weighted average must blend all of them into\n",
    "one vector. This section first makes the restriction precise: we construct a\n",
    "task on which a single attention head provably loses half of what it is asked\n",
    "to report, however it allocates its weights, and we verify the bound\n",
    "numerically. *Multi-head attention* [@Vaswani.Shazeer.Parmar.ea.2017]\n",
    "removes the restriction at essentially no extra cost, and we implement it\n",
    "with one batched matrix multiplication for all heads — a common\n",
    "implementation strategy (fused attention kernels keep an explicit head axis\n",
    "instead). Finally we separate what is often conflated: the attention\n",
    "*function* is one piece of code, and *self-attention* and *cross-attention*\n",
    "are merely two ways of wiring its inputs."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multihead-attention-multi-head-and-cross-attention"
   },
   "source": [
    "%matplotlib inline\n",
    "from d2l import torch as d2l\n",
    "import torch\n",
    "from torch import nn"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=multihead-attention-md-2 fw=all -->\n",
    "\n",
    "## One Head Must Average\n",
    "\n",
    "Here is the smallest task that defeats a single head. Two source positions\n",
    "hold value vectors $\\mathbf{v}_1, \\mathbf{v}_2 \\in \\mathbb{R}^d$, drawn\n",
    "independently at random for every example; their keys mark only the\n",
    "*positions*, not the content. A query must report **both** values: the target\n",
    "is the concatenation $\\mathbf{t} = [\\mathbf{v}_1; \\mathbf{v}_2] \\in\n",
    "\\mathbb{R}^{2d}$. Think of a pronoun that must simultaneously retrieve its\n",
    "antecedent and its governing verb.\n",
    "\n",
    "A single head can only produce, for this query, softmax weights\n",
    "$(\\alpha_1, \\alpha_2)$ with $\\alpha_1 + \\alpha_2 = 1$, the mixture\n",
    "$\\mathbf{m} = \\alpha_1 \\mathbf{v}_1 + \\alpha_2 \\mathbf{v}_2$, and then a\n",
    "linear readout $\\mathbf{W}_o \\mathbf{m}$. Since the keys are fixed position\n",
    "markers, the weights cannot depend on the values: whatever the head learns,\n",
    "it applies the *same* mixture to every example. How well can it do?\n",
    "\n",
    "**Proposition.** For independent isotropic Gaussian values, the best\n",
    "achievable relative squared error of a single head on the copy-both task is\n",
    "$1/2$ — for *every* choice of $(\\alpha_1, \\alpha_2)$.\n",
    "\n",
    "**Proof.** Given the mixture $\\mathbf{m} = \\alpha_1 \\mathbf{v}_1 + \\alpha_2\n",
    "\\mathbf{v}_2$, the best estimate of $\\mathbf{v}_1$ is the conditional mean\n",
    "$\\mathbb{E}[\\mathbf{v}_1 \\mid \\mathbf{m}] = \\tfrac{\\alpha_1}{\\alpha_1^2 +\n",
    "\\alpha_2^2}\\, \\mathbf{m}$, which is linear, so a linear readout attains it.\n",
    "Its per-dimension error variance is $1 - \\tfrac{\\alpha_1^2}{\\alpha_1^2 +\n",
    "\\alpha_2^2} = \\tfrac{\\alpha_2^2}{\\alpha_1^2 + \\alpha_2^2}$; the error for\n",
    "$\\mathbf{v}_2$ is $\\tfrac{\\alpha_1^2}{\\alpha_1^2 + \\alpha_2^2}$. The two\n",
    "add to exactly $1$ per dimension, against the target's total of $2$: half\n",
    "the variance is gone, no matter how the head splits its attention.\n",
    "$\\blacksquare$\n",
    "\n",
    "The knob that softmax controls — where to put the weight — cannot help,\n",
    "because the failure is structural: one head hands the readout a *single*\n",
    "mixture of the values, and the task needs two. Let's watch the bound hold."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multihead-attention-one-head-must-average-1"
   },
   "source": [
    "torch.manual_seed(0)\n",
    "N, d = 10000, 16\n",
    "V1, V2 = torch.randn(N, d), torch.randn(N, d)\n",
    "target = torch.cat([V1, V2], dim=1)\n",
    "\n",
    "def readout_error(M, target):\n",
    "    \"\"\"Best linear readout of target from M, relative error.\"\"\"\n",
    "    W = torch.linalg.lstsq(M, target).solution\n",
    "    return ((M @ W - target).norm() / target.norm()).item()\n",
    "\n",
    "for a in (0.5, 0.7, 0.9, 1.0):\n",
    "    M = a * V1 + (1 - a) * V2\n",
    "    print(f'single head, weights ({a:.1f}, {1 - a:.1f}): '\n",
    "          f'relative error {readout_error(M, target):.3f}')\n",
    "print(f'theory: sqrt(1/2) = {0.5 ** 0.5:.3f}')"
   ],
   "execution_count": 2,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "single head, weights (0.5, 0.5): relative error 0.706\nsingle head, weights (0.7, 0.3): relative error 0.706\nsingle head, weights (0.9, 0.1): relative error 0.706\nsingle head, weights (1.0, 0.0): relative error 0.707\ntheory: sqrt(1/2) = 0.707\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=multihead-attention-md-3 fw=all -->\n",
    "\n",
    "The error sits at $\\sqrt{1/2} \\approx 0.707$ across the whole range, exactly\n",
    "as computed. Now give the model a second head: two sets of attention weights,\n",
    "their outputs concatenated before the readout."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multihead-attention-one-head-must-average-2"
   },
   "source": [
    "for a in (1.0, 0.88):\n",
    "    M2 = torch.cat([a * V1 + (1 - a) * V2,\n",
    "                    (1 - a) * V1 + a * V2], dim=1)\n",
    "    print(f'two heads, weights ({a:.2f}, {1 - a:.2f}) and '\n",
    "          f'({1 - a:.2f}, {a:.2f}): '\n",
    "          f'relative error {readout_error(M2, target):.1e}')"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "two heads, weights (1.00, 0.00) and (0.00, 1.00): relative error 1.4e-06\ntwo heads, weights (0.88, 0.12) and (0.12, 0.88): relative error 6.0e-07\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=multihead-attention-md-4 fw=all -->\n",
    "\n",
    "Two heads collapse the error by orders of magnitude, down to the\n",
    "least-squares solver's floating-point noise — and note that the second row\n",
    "does it with *soft* attention, weights $(0.88, 0.12)$. Sharpness is not\n",
    "the point. The two heads supply two different mixtures, the readout inverts\n",
    "the $2 \\times 2$ mixing matrix, and both values come out exactly (the\n",
    "inversion is well conditioned as long as the heads differ appreciably; the\n",
    "exercises probe what happens as they collapse toward each other).\n",
    "the figure summarizes the geometry.\n",
    "\n",
    "![One distribution per query versus several. A single head must serve the copy-both task with one softmax weighting, so its output blends the two requested values; two heads supply two different weightings, and a linear readout recovers both values exactly.](../img/mdl-attention-one-head-averages.svg)\n",
    "\n",
    "This is the design brief for multi-head attention: give each query several\n",
    "independently parametrized attention distributions — several *views* of the\n",
    "same key–value set — and let a learned output projection recombine them.\n",
    "\n",
    "## Multi-Head Attention\n",
    "\n",
    "### From One Head to $h$ Heads\n",
    "\n",
    "Rather than hand-designing the heads as above, we learn them. Given a query\n",
    "$\\mathbf{q} \\in \\mathbb{R}^{d}$, keys $\\mathbf{k} \\in \\mathbb{R}^{d}$, and\n",
    "values $\\mathbf{v} \\in \\mathbb{R}^{d}$, head $i$ ($i = 1, \\ldots, h$) first\n",
    "projects them into its own subspace and then runs ordinary scaled dot product\n",
    "attention $f$ from that section:\n",
    "\n",
    "$$\n",
    "\\mathbf{h}_i = f\\big(\\mathbf W_i^{(q)}\\mathbf q,\\; \\mathbf W_i^{(k)}\\mathbf k,\\; \\mathbf W_i^{(v)}\\mathbf v\\big) \\in \\mathbb R^{p},\n",
    "$$\n",
    "\n",
    "with learnable $\\mathbf W_i^{(q)}, \\mathbf W_i^{(k)}, \\mathbf W_i^{(v)} \\in\n",
    "\\mathbb R^{p \\times d}$. Because each head scores with its own projected\n",
    "queries and keys, each head attends according to its own notion of relevance,\n",
    "and each moves its own projection of the values — the two independent\n",
    "mixtures of the construction above, now learned and generalized to $h$. The\n",
    "output is a learned linear recombination of the concatenated heads:\n",
    "\n",
    "$$\n",
    "\\mathbf W_o \\begin{bmatrix}\\mathbf h_1\\\\\\vdots\\\\\\mathbf h_h\\end{bmatrix} \\in \\mathbb{R}^{d}, \\qquad \\mathbf W_o \\in \\mathbb R^{d \\times hp}.\n",
    "$$\n",
    "\n",
    "the figure shows the layout.\n",
    "\n",
    "![Multi-head attention: each head projects queries, keys, and values into its own subspace and attends there; the head outputs are concatenated and linearly recombined.](../img/multi-head-attention.svg)\n",
    "\n",
    "### Same FLOPs, More Views\n",
    "\n",
    "The standard dimension choice makes the heads collectively no more expensive\n",
    "than one big head: set the per-head width to $p = d/h$, so the $h$ heads\n",
    "together produce $hp = d$ numbers per token, exactly what a single head of\n",
    "width $d$ would. For a sequence of $n$ tokens the cost is then\n",
    "\n",
    "$$\n",
    "\\underbrace{8nd^2}_{\\textrm{projections}} \\;+\\; \\underbrace{4n^2 d}_{\\textrm{scores and mixing}} \\quad \\textrm{FLOPs,} \\qquad 4d^2 \\ \\textrm{parameters,}\n",
    "$$\n",
    "\n",
    "*independent of $h$*: the four projection matrices are $d \\times d$\n",
    "regardless of how their outputs are sliced into heads, and each head's score\n",
    "and mixing matmuls shrink by the factor $h$ that their count grows by\n",
    "(counting one multiply–add as two FLOPs). In this arithmetic the number of\n",
    "heads is a free dial that buys representational diversity, not extra\n",
    "compute — realized cost is not quite as flat, since more heads mean more,\n",
    "smaller matmuls and softmaxes for the kernels to keep efficient. What *does*\n",
    "change with $h$ is the shape of the attention map — $h$ distributions of $n$\n",
    "weights per query instead of one.\n",
    "\n",
    "### Implementation\n",
    "\n",
    "The per-head dimension choice also yields a standard implementation trick:\n",
    "compute *one* query projection of width $d$, then\n",
    "*reshape* it into $h$ heads of width $d/h$, and fold the head axis into the\n",
    "batch axis. The attention code from that section\n",
    "then runs all heads of all sequences as one big batched matrix\n",
    "multiplication, with no loop over heads. Within the forward pass, `valid_lens`\n",
    "is repeated $h$ times so that each head of a sequence sees that sequence's\n",
    "mask."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multihead-attention-implementation-1"
   },
   "source": [
    "class MultiHeadAttention(d2l.Module):\n",
    "    \"\"\"Multi-head attention.\"\"\"\n",
    "    def __init__(self, num_hiddens, num_heads, dropout, bias=False, **kwargs):\n",
    "        super().__init__()\n",
    "        assert num_hiddens % num_heads == 0, 'heads must divide num_hiddens'\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",
    "        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)"
   ],
   "execution_count": 4,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=multihead-attention-md-5 fw=all -->\n",
    "\n",
    "The two transpositions do the head bookkeeping: `transpose_qkv` moves from\n",
    "`(batch, length, num_hiddens)` to `(batch * num_heads, length,\n",
    "num_hiddens / num_heads)`, and `transpose_output` reverses it after the\n",
    "attention call."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multihead-attention-implementation-2"
   },
   "source": [
    "@d2l.add_to_class(MultiHeadAttention)\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)\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)"
   ],
   "execution_count": 5,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=multihead-attention-md-6 fw=all -->\n",
    "\n",
    "A shape check: with 5 heads and 100 hidden units, batches of 2 sequences with\n",
    "4 queries against 6 key–value pairs come back as\n",
    "(`batch_size`, `num_queries`, `num_hiddens`), and the per-sequence\n",
    "`valid_lens` masking flows through unchanged."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multihead-attention-implementation-3"
   },
   "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 = d2l.tensor([3, 2])\n",
    "X = d2l.ones((batch_size, num_queries, num_hiddens))\n",
    "Y = d2l.ones((batch_size, num_kvpairs, num_hiddens))\n",
    "d2l.check_shape(attention(X, Y, Y, valid_lens),\n",
    "                (batch_size, num_queries, num_hiddens))"
   ],
   "execution_count": 6,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=multihead-attention-md-7 fw=all -->\n",
    "\n",
    "And the accounting of the equation in the flesh: the parameter\n",
    "count does not move as the head count sweeps from 1 to 8."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multihead-attention-implementation-4"
   },
   "source": [
    "X = d2l.ones((2, 10, 256))\n",
    "for num_heads in (1, 2, 4, 8):\n",
    "    attention = MultiHeadAttention(num_hiddens=256, num_heads=num_heads,\n",
    "                                   dropout=0)\n",
    "    attention(X, X, X, None)  # Materialize the lazily initialized layers\n",
    "    print(f'{num_heads} heads: '\n",
    "          f'{sum(p.numel() for p in attention.parameters())} parameters')"
   ],
   "execution_count": 7,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "1 heads: 262144 parameters\n2 heads: 262144 parameters\n4 heads: 262144 parameters\n8 heads: 262144 parameters\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=multihead-attention-md-8 fw=all -->\n",
    "\n",
    "## Self-Attention and Cross-Attention\n",
    "\n",
    "`MultiHeadAttention` takes three sequence arguments — queries, keys, values —\n",
    "and nothing in its code cares where they come from. The two wirings that\n",
    "dominate practice differ only in what we pass.\n",
    "\n",
    "### One Sequence Querying Itself\n",
    "\n",
    "In *self-attention* [@Lin.Feng.Santos.ea.2017; @Vaswani.Shazeer.Parmar.ea.2017],\n",
    "one sequence supplies all three arguments: every token emits a query against\n",
    "every token's key, and each output position is a value mixture from the same\n",
    "sequence. Given inputs $\\mathbf{x}_1, \\ldots, \\mathbf{x}_n \\in \\mathbb{R}^d$,\n",
    "the layer returns an equally long sequence $\\mathbf{y}_1, \\ldots,\n",
    "\\mathbf{y}_n$ with\n",
    "\n",
    "$$\n",
    "\\mathbf{y}_i = f\\big(\\mathbf{x}_i,\\; (\\mathbf{x}_1, \\mathbf{x}_1), \\ldots, (\\mathbf{x}_n, \\mathbf{x}_n)\\big) \\in \\mathbb{R}^d,\n",
    "$$\n",
    "\n",
    "where $f$ is multi-head attention pooling. Each token's new representation is\n",
    "assembled from the whole sequence in a single step — this is the layer that\n",
    "transformers stack, and its output shape equals its input shape, which is\n",
    "what makes stacking possible."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multihead-attention-one-sequence-querying-itself"
   },
   "source": [
    "num_hiddens, num_heads = 100, 5\n",
    "attention = MultiHeadAttention(num_hiddens, num_heads, 0.5)\n",
    "batch_size, num_queries, valid_lens = 2, 4, d2l.tensor([3, 2])\n",
    "X = d2l.ones((batch_size, num_queries, num_hiddens))\n",
    "d2l.check_shape(attention(X, X, X, valid_lens),\n",
    "                (batch_size, num_queries, num_hiddens))"
   ],
   "execution_count": 8,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=multihead-attention-md-9 fw=all -->\n",
    "\n",
    "### One Sequence Querying Another\n",
    "\n",
    "In *cross-attention*, one sequence asks and another answers: the queries come\n",
    "from sequence $\\mathbf{A}$, while keys and values come from sequence\n",
    "$\\mathbf{B}$. The output has the length of $\\mathbf{A}$ (one answer per\n",
    "question) and the information of $\\mathbf{B}$. This is the wiring of the\n",
    "original encoder–decoder transformer, where each target-language position\n",
    "queries the source sentence; of a vision–language model, where text tokens\n",
    "query image patches; and of the historical alignment models that attention\n",
    "grew out of (that section). Same function, one\n",
    "changed argument:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multihead-attention-one-sequence-querying-another"
   },
   "source": [
    "A = d2l.ones((batch_size, 4, num_hiddens))\n",
    "B = d2l.ones((batch_size, 9, num_hiddens))\n",
    "d2l.check_shape(attention(A, B, B, None),\n",
    "                (batch_size, 4, num_hiddens))"
   ],
   "execution_count": 9,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=multihead-attention-md-10 fw=all -->\n",
    "\n",
    "### An Alignment You Can Read\n",
    "\n",
    "To see cross-attention *doing* something rather than merely reshaping, we\n",
    "strip it to its core. Assign every letter of the alphabet a random embedding,\n",
    "and let the letters of one word query the letters of another through plain\n",
    "scaled dot product attention — no learned projections. Matching letters\n",
    "share an embedding, so their score concentrates near $\\sqrt{d}$ after\n",
    "scaling, while unrelated pairs score near zero; softmax turns this gap into\n",
    "a readable alignment."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "multihead-attention-an-alignment-you-can-read"
   },
   "source": [
    "words = 'attention', 'translation'\n",
    "letters = sorted(set(''.join(words)))\n",
    "torch.manual_seed(0)\n",
    "emb = torch.randn(len(letters), 32)\n",
    "queries, keys = (emb[[letters.index(c) for c in w]][None] for w in words)\n",
    "attention = d2l.DotProductAttention(dropout=0)\n",
    "attention(queries, keys, keys, None)\n",
    "d2l.show_heatmaps(attention.attention_weights[None],\n",
    "                  xlabel='keys:  t  r  a  n  s  l  a  t  i  o  n',\n",
    "                  ylabel='queries:  a  t  t  e  n  t  i  o  n',\n",
    "                  figsize=(4, 3.5), cmap='Blues')"
   ],
   "execution_count": 10,
   "outputs": [
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"259.88495pt\" height=\"190.850795pt\" viewBox=\"0 0 259.88495 190.850795\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-19T13:39:58.698700</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M 0 190.850795 \nL 259.88495 190.850795 \nL 259.88495 0 \nL 0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 34.240625 153.294545 \nL 212.800625 153.294545 \nL 212.800625 7.2 \nL 34.240625 7.2 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g clip-path=\"url(#p3d8a582d59)\">\n    <image xlink:href=\"data:image/png;base64,\niVBORw0KGgoAAAANSUhEUgAAAPgAAADLCAYAAABDP14IAAAD6UlEQVR4nO3cv4pUdxjH4d+ZyZJ67yB2Jr2Ft2AkFyJJk4DXIAG7YOFNBMLeg0g6Cy21CKTLHwuX7DozKSSFZYoX2Q/PcwFfhsP5zOne7e3l4bQGbNvE6gfHkV/8wdPnb0Z2H9y9NbK71tyzvp55NdZaaw2+HmP2u5lf/eTZ65HdtdbajS0Dn5zAIUzgECZwCBM4hAkcwgQOYQKHMIFDmMAhTOAQJnAIEziECRzCBA5hAocwgUOYwCFM4BAmcAgTOIQJHMK2d1eTR4hnnAZ/8dQJ4smn/P5wHNk928/9/089523wXvf5149Hdv+4+H5kdy1fcEgTOIQJHMIEDmEChzCBQ5jAIUzgECZwCBM4hAkcwgQOYQKHMIFDmMAhTOAQJnAIEziECRzCBA5hAoew7fJ68kYp/zkNPubJS6I3zfmdb8e2//z1p7HtKb7gECZwCBM4hAkcwgQOYQKHMIFDmMAhTOAQJnAIEziECRzCBA5hAocwgUOYwCFM4BAmcAgTOIQJHMIEDmECh7DPHl68Ghl+dO/2yO5aa+12c2eCp84bO238san37iaeNp48qe0LDmEChzCBQ5jAIUzgECZwCBM4hAkcwgQOYQKHMIFDmMAhTOAQJnAIEziECRzCBA5hAocwgUOYwCFM4BC2vb08jJx0nDwiepw7QrmePn8zsvvg7q2R3bXmnvX1zKux1lrrJt6Y3Q9d833y7PXI7lq+4JAmcAgTOIQJHMIEDmEChzCBQ5jAIUzgECZwCBM4hAkcwgQOYQKHMIFDmMAhTOAQJnAIEziECRzCBA5hAoew7fe//hm5jXu2n/vvOJ7mzvlOLb/47e+h5bXufHE+snv1/jiyu9Zah6Hb1++uDiO7a631+dl+ZPdsP3dE2hccwgQOYQKHMIFDmMAhTOAQJnAIEziECRzCBA5hAocwgUOYwCFM4BAmcAgTOIQJHMIEDmEChzCBQ5jAIWz77ueXI+ctH927PTG71lprt5u7Qnkauti6bXO/+SZ6ePFqZPfH+1+O7E6aeufW8gWHNIFDmMAhTOAQJnAIEziECRzCBA5hAocwgUOYwCFM4BAmcAgTOIQJHMIEDmEChzCBQ5jAIUzgECZwCBM4hAkcwgQOYQKHMIFDmMAhTOAQJnAIEziECRzCBA5hAocwgUOYwCFM4BAmcAgTOIQJHMIEDmEChzCBQ5jAIUzgELZdXp9On/pH/F8//PJybPvxN1+N7B6Pc495t9tGdm/ic+ZjvuAQJnAIEziECRzCBA5hAocwgUOYwCFM4BAmcAgTOIQJHMIEDmEChzCBQ5jAIUzgECZwCBM4hAkcwgQOYQKHsH8BJ11wujVv8TgAAAAASUVORK5CYII=\" id=\"image26af33be29\" transform=\"scale(1 -1) translate(0 -146.16)\" x=\"34.240625\" y=\"-7.134545\" width=\"178.56\" height=\"146.16\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <defs>\n       <path id=\"m864b4eec7d\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m864b4eec7d\" x=\"42.356989\" y=\"153.294545\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- 0.0 -->\n      <g transform=\"translate(34.405426 167.892983) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-2e\" d=\"M 684 794 \nL 1344 794 \nL 1344 0 \nL 684 0 \nL 684 794 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_2\">\n      <g>\n       <use xlink:href=\"#m864b4eec7d\" x=\"82.938807\" y=\"153.294545\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 2.5 -->\n      <g transform=\"translate(74.987244 167.892983) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-35\" d=\"M 691 4666 \nL 3169 4666 \nL 3169 4134 \nL 1269 4134 \nL 1269 2991 \nQ 1406 3038 1543 3061 \nQ 1681 3084 1819 3084 \nQ 2600 3084 3056 2656 \nQ 3513 2228 3513 1497 \nQ 3513 744 3044 326 \nQ 2575 -91 1722 -91 \nQ 1428 -91 1123 -41 \nQ 819 9 494 109 \nL 494 744 \nQ 775 591 1075 516 \nQ 1375 441 1709 441 \nQ 2250 441 2565 725 \nQ 2881 1009 2881 1497 \nQ 2881 1984 2565 2268 \nQ 2250 2553 1709 2553 \nQ 1456 2553 1204 2497 \nQ 953 2441 691 2322 \nL 691 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_3\">\n      <g>\n       <use xlink:href=\"#m864b4eec7d\" x=\"123.520625\" y=\"153.294545\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 5.0 -->\n      <g transform=\"translate(115.569063 167.892983) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-35\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#m864b4eec7d\" x=\"164.102443\" y=\"153.294545\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 7.5 -->\n      <g transform=\"translate(156.150881 167.892983) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-37\" d=\"M 525 4666 \nL 3525 4666 \nL 3525 4397 \nL 1831 0 \nL 1172 0 \nL 2766 4134 \nL 525 4134 \nL 525 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-37\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_5\">\n     <g id=\"line2d_5\">\n      <g>\n       <use xlink:href=\"#m864b4eec7d\" x=\"204.684261\" y=\"153.294545\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- 10.0 -->\n      <g transform=\"translate(193.551449 167.892983) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(127.246094 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(159.033203 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_6\">\n     <!-- keys:  t  r  a  n  s  l  a  t  i  o  n -->\n     <g transform=\"translate(48.638594 181.571108) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-6b\" d=\"M 581 4863 \nL 1159 4863 \nL 1159 1991 \nL 2875 3500 \nL 3609 3500 \nL 1753 1863 \nL 3688 0 \nL 2938 0 \nL 1159 1709 \nL 1159 0 \nL 581 0 \nL 581 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-65\" d=\"M 3597 1894 \nL 3597 1613 \nL 953 1613 \nQ 991 1019 1311 708 \nQ 1631 397 2203 397 \nQ 2534 397 2845 478 \nQ 3156 559 3463 722 \nL 3463 178 \nQ 3153 47 2828 -22 \nQ 2503 -91 2169 -91 \nQ 1331 -91 842 396 \nQ 353 884 353 1716 \nQ 353 2575 817 3079 \nQ 1281 3584 2069 3584 \nQ 2775 3584 3186 3129 \nQ 3597 2675 3597 1894 \nz\nM 3022 2063 \nQ 3016 2534 2758 2815 \nQ 2500 3097 2075 3097 \nQ 1594 3097 1305 2825 \nQ 1016 2553 972 2059 \nL 3022 2063 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-79\" d=\"M 2059 -325 \nQ 1816 -950 1584 -1140 \nQ 1353 -1331 966 -1331 \nL 506 -1331 \nL 506 -850 \nL 844 -850 \nQ 1081 -850 1212 -737 \nQ 1344 -625 1503 -206 \nL 1606 56 \nL 191 3500 \nL 800 3500 \nL 1894 763 \nL 2988 3500 \nL 3597 3500 \nL 2059 -325 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-3a\" d=\"M 750 794 \nL 1409 794 \nL 1409 0 \nL 750 0 \nL 750 794 \nz\nM 750 3309 \nL 1409 3309 \nL 1409 2516 \nL 750 2516 \nL 750 3309 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-72\" d=\"M 2631 2963 \nQ 2534 3019 2420 3045 \nQ 2306 3072 2169 3072 \nQ 1681 3072 1420 2755 \nQ 1159 2438 1159 1844 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1341 3275 1631 3429 \nQ 1922 3584 2338 3584 \nQ 2397 3584 2469 3576 \nQ 2541 3569 2628 3553 \nL 2631 2963 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6e\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6c\" d=\"M 603 4863 \nL 1178 4863 \nL 1178 0 \nL 603 0 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-69\" d=\"M 603 3500 \nL 1178 3500 \nL 1178 0 \nL 603 0 \nL 603 3500 \nz\nM 603 4863 \nL 1178 4863 \nL 1178 4134 \nL 603 4134 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \nQ 1497 3097 1228 2736 \nQ 959 2375 959 1747 \nQ 959 1119 1226 758 \nQ 1494 397 1959 397 \nQ 2419 397 2687 759 \nQ 2956 1122 2956 1747 \nQ 2956 2369 2687 2733 \nQ 2419 3097 1959 3097 \nz\nM 1959 3584 \nQ 2709 3584 3137 3096 \nQ 3566 2609 3566 1747 \nQ 3566 888 3137 398 \nQ 2709 -91 1959 -91 \nQ 1206 -91 779 398 \nQ 353 888 353 1747 \nQ 353 2609 779 3096 \nQ 1206 3584 1959 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-6b\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(54.285156 0)\"/>\n      <use xlink:href=\"#DejaVuSans-79\" transform=\"translate(115.808594 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(174.988281 0)\"/>\n      <use xlink:href=\"#DejaVuSans-3a\" transform=\"translate(227.087891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(260.779297 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(292.566406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(324.353516 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(363.5625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(395.349609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(427.136719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(468.25 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(500.037109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(531.824219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(593.103516 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(624.890625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(656.677734 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(720.056641 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(751.84375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(783.630859 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(835.730469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(867.517578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(899.304688 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(927.087891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(958.875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(990.662109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1051.941406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1083.728516 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(1115.515625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1154.724609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1186.511719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(1218.298828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1246.082031 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1277.869141 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(1309.65625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1370.837891 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1402.625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(1434.412109 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_6\">\n      <defs>\n       <path id=\"m80da7983a2\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m80da7983a2\" x=\"34.240625\" y=\"15.316364\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- 0 -->\n      <g transform=\"translate(20.878125 19.115582) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#m80da7983a2\" x=\"34.240625\" y=\"47.781818\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- 2 -->\n      <g transform=\"translate(20.878125 51.581037) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#m80da7983a2\" x=\"34.240625\" y=\"80.247273\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- 4 -->\n      <g transform=\"translate(20.878125 84.046491) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \nL 825 1625 \nL 2419 1625 \nL 2419 4116 \nz\nM 2253 4666 \nL 3047 4666 \nL 3047 1625 \nL 3713 1625 \nL 3713 1100 \nL 3047 1100 \nL 3047 0 \nL 2419 0 \nL 2419 1100 \nL 313 1100 \nL 313 1709 \nL 2253 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-34\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#m80da7983a2\" x=\"34.240625\" y=\"112.712727\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- 6 -->\n      <g transform=\"translate(20.878125 116.511946) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-36\" d=\"M 2113 2584 \nQ 1688 2584 1439 2293 \nQ 1191 2003 1191 1497 \nQ 1191 994 1439 701 \nQ 1688 409 2113 409 \nQ 2538 409 2786 701 \nQ 3034 994 3034 1497 \nQ 3034 2003 2786 2293 \nQ 2538 2584 2113 2584 \nz\nM 3366 4563 \nL 3366 3988 \nQ 3128 4100 2886 4159 \nQ 2644 4219 2406 4219 \nQ 1781 4219 1451 3797 \nQ 1122 3375 1075 2522 \nQ 1259 2794 1537 2939 \nQ 1816 3084 2150 3084 \nQ 2853 3084 3261 2657 \nQ 3669 2231 3669 1497 \nQ 3669 778 3244 343 \nQ 2819 -91 2113 -91 \nQ 1303 -91 875 529 \nQ 447 1150 447 2328 \nQ 447 3434 972 4092 \nQ 1497 4750 2381 4750 \nQ 2619 4750 2861 4703 \nQ 3103 4656 3366 4563 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-36\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#m80da7983a2\" x=\"34.240625\" y=\"145.178182\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_11\">\n      <!-- 8 -->\n      <g transform=\"translate(20.878125 148.977401) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-38\" d=\"M 2034 2216 \nQ 1584 2216 1326 1975 \nQ 1069 1734 1069 1313 \nQ 1069 891 1326 650 \nQ 1584 409 2034 409 \nQ 2484 409 2743 651 \nQ 3003 894 3003 1313 \nQ 3003 1734 2745 1975 \nQ 2488 2216 2034 2216 \nz\nM 1403 2484 \nQ 997 2584 770 2862 \nQ 544 3141 544 3541 \nQ 544 4100 942 4425 \nQ 1341 4750 2034 4750 \nQ 2731 4750 3128 4425 \nQ 3525 4100 3525 3541 \nQ 3525 3141 3298 2862 \nQ 3072 2584 2669 2484 \nQ 3125 2378 3379 2068 \nQ 3634 1759 3634 1313 \nQ 3634 634 3220 271 \nQ 2806 -91 2034 -91 \nQ 1263 -91 848 271 \nQ 434 634 434 1313 \nQ 434 1759 690 2068 \nQ 947 2378 1403 2484 \nz\nM 1172 3481 \nQ 1172 3119 1398 2916 \nQ 1625 2713 2034 2713 \nQ 2441 2713 2670 2916 \nQ 2900 3119 2900 3481 \nQ 2900 3844 2670 4047 \nQ 2441 4250 2034 4250 \nQ 1625 4250 1398 4047 \nQ 1172 3844 1172 3481 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-38\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_12\">\n     <!-- queries:  a  t  t  e  n  t  i  o  n -->\n     <g transform=\"translate(14.798438 151.887116) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-71\" d=\"M 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \nz\nM 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nL 2906 3500 \nL 3481 3500 \nL 3481 -1331 \nL 2906 -1331 \nL 2906 525 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-75\" d=\"M 544 1381 \nL 544 3500 \nL 1119 3500 \nL 1119 1403 \nQ 1119 906 1312 657 \nQ 1506 409 1894 409 \nQ 2359 409 2629 706 \nQ 2900 1003 2900 1516 \nL 2900 3500 \nL 3475 3500 \nL 3475 0 \nL 2900 0 \nL 2900 538 \nQ 2691 219 2414 64 \nQ 2138 -91 1772 -91 \nQ 1169 -91 856 284 \nQ 544 659 544 1381 \nz\nM 1991 3584 \nL 1991 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-71\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(63.476562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(126.855469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(188.378906 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(229.492188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(257.275391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(318.798828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-3a\" transform=\"translate(370.898438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(404.589844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(436.376953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(468.164062 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(529.443359 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(561.230469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(593.017578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(632.226562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(664.013672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(695.800781 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(735.009766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(766.796875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(798.583984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(860.107422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(891.894531 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(923.681641 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(987.060547 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1018.847656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(1050.634766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1089.84375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1121.630859 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(1153.417969 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1181.201172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1212.988281 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(1244.775391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1305.957031 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(1337.744141 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(1369.53125 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 34.240625 153.294545 \nL 34.240625 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 212.800625 153.294545 \nL 212.800625 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 34.240625 153.294545 \nL 212.800625 153.294545 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 34.240625 7.2 \nL 212.800625 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n  </g>\n  <g id=\"axes_2\">\n   <g id=\"patch_7\">\n    <path d=\"M 223.960625 138.459273 \nL 229.781825 138.459273 \nL 229.781825 22.035273 \nL 223.960625 22.035273 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <image xlink:href=\"data:image/png;base64,\niVBORw0KGgoAAAANSUhEUgAAAAgAAAChCAYAAAD6HP6tAAAA5UlEQVR4nO2XQQ7DIAwEXYn/P7eHCEwPuXuQ1kYgtdc49uyuocrn+8xpwa9NC59bi99fK4ARjh3qIZ0goUGGTFB5BqQeN0KizAWjoOAP+RYkQMpn8wrIgVnoHQgSjUIfsIMukyFZJoxYgJSdjBGsOVDy2UQVCStHkLwPYARDcpoMWd+BfSiHxDS7HBaeiy532LG08lYnXKTEsBB3/VWsG4Uy6+Nmo+SF0Z3kf5z6DlfI3OJk+NzaGBfInAlGxbd5wogdkDIDjuDviwMgN2Qx2Sgq8KEW6CPwc/IESArLvBPDDTJVyB9zG4821kc01AAAAABJRU5ErkJggg==\" id=\"image573324773c\" transform=\"scale(1 -1) translate(0 -115.92)\" x=\"223.92\" y=\"-22.32\" width=\"5.76\" height=\"115.92\"/>\n   <g id=\"matplotlib.axis_3\"/>\n   <g id=\"matplotlib.axis_4\">\n    <g id=\"ytick_6\">\n     <g id=\"line2d_11\">\n      <defs>\n       <path id=\"mfd1a63bfd6\" d=\"M 0 0 \nL 3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mfd1a63bfd6\" x=\"229.781825\" y=\"114.70336\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_13\">\n      <!-- 0.2 -->\n      <g transform=\"translate(236.781825 118.502579) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_7\">\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#mfd1a63bfd6\" x=\"229.781825\" y=\"90.910375\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_14\">\n      <!-- 0.4 -->\n      <g transform=\"translate(236.781825 94.709593) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-34\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_8\">\n     <g id=\"line2d_13\">\n      <g>\n       <use xlink:href=\"#mfd1a63bfd6\" x=\"229.781825\" y=\"67.117389\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_15\">\n      <!-- 0.6 -->\n      <g transform=\"translate(236.781825 70.916608) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-36\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_9\">\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#mfd1a63bfd6\" x=\"229.781825\" y=\"43.324404\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_16\">\n      <!-- 0.8 -->\n      <g transform=\"translate(236.781825 47.123623) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-38\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"LineCollection_1\"/>\n   <g id=\"patch_8\">\n    <path d=\"M 223.960625 138.459273 \nL 226.871225 138.459273 \nL 229.781825 138.459273 \nL 229.781825 22.035273 \nL 226.871225 22.035273 \nL 223.960625 22.035273 \nL 223.960625 138.459273 \nz\n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p3d8a582d59\">\n   <rect x=\"34.240625\" y=\"7.2\" width=\"178.56\" height=\"146.094545\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=multihead-attention-md-11 fw=all -->\n",
    "\n",
    "Read the map row by row (queries are the letters of \"attention\", keys the\n",
    "letters of \"translation\"). Three regimes appear. The `i` and `o` queries find\n",
    "their unique partners and attend sharply. The `a`, `t`, and `n` queries find\n",
    "*two* copies each and split their weight: a single head cannot choose\n",
    "between identical keys, the averaging of the first section in miniature.\n",
    "And the `e` query, whose letter does not occur in \"translation\" at all,\n",
    "spreads its weight diffusely: softmax must hand out probability mass\n",
    "somewhere even when nothing matches. Trained models show all three regimes\n",
    "too, which is one reason reading attention maps as explanations requires\n",
    "care — a diffuse row may mean \"nothing relevant\", not \"everything relevant\".\n",
    "\n",
    "## Summary\n",
    "\n",
    "A single attention head gives each query one softmax distribution over the\n",
    "keys and hence one convex mixture of the values; on a task that asks one\n",
    "query to report two values through position-only keys — so the weights\n",
    "cannot adapt to the values — any single head loses half the target\n",
    "variance, however it allocates its weights. Multi-head attention fixes this by running\n",
    "$h$ independently projected attention heads and linearly recombining their\n",
    "concatenated outputs. With the per-head width set to $d/h$, parameters and\n",
    "FLOPs are independent of $h$ — heads buy diversity of views, not extra\n",
    "compute — and the implementation folds the head axis into the batch axis so\n",
    "that all heads run as one batched matmul. The attention function is\n",
    "indifferent to where its arguments come from: self-attention feeds one\n",
    "sequence as queries, keys, and values alike (output length = input length,\n",
    "the stackable case), while cross-attention lets one sequence query another\n",
    "(output length = query length), which is the encoder–decoder and\n",
    "multimodal wiring.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. In the copy-both construction, the best *linear* readout loses half the\n",
    "   variance. Does a nonlinear readout help? For Gaussian values the\n",
    "   conditional mean is linear, so it cannot; check this numerically by\n",
    "   training a small MLP readout on $\\mathbf{m}$ with weights $(0.5, 0.5)$.\n",
    "   Then repeat with values drawn uniformly from $\\{-1, +1\\}^d$ — explain\n",
    "   what changes and why.\n",
    "2. Two heads with weights $(0.5 + \\epsilon, 0.5 - \\epsilon)$ and\n",
    "   $(0.5 - \\epsilon, 0.5 + \\epsilon)$ still invert exactly in theory. Add\n",
    "   Gaussian noise of standard deviation $0.01$ to the mixtures and measure\n",
    "   the readout error as $\\epsilon \\to 0$. Relate what you see to the\n",
    "   condition number of the $2 \\times 2$ mixing matrix.\n",
    "3. Feed the letter-alignment example through a freshly initialized\n",
    "   `MultiHeadAttention` with 4 heads instead of plain dot product attention,\n",
    "   and plot each head's attention map. Are the maps still readable? What\n",
    "   does this suggest about interpreting the attention maps of a network\n",
    "   whose projections you have not inspected?\n",
    "4. Derive the equation by counting the matrix\n",
    "   multiplications in `MultiHeadAttention`. For $d = 512$, at which sequence\n",
    "   length $n$ does the quadratic score-and-mix term overtake the projection\n",
    "   term? Later sections of this chapter take this crossover as their\n",
    "   starting point.\n",
    "5. Multi-query attention shares a single key and value head across all $h$\n",
    "   query heads, and grouped-query attention shares them within groups. How\n",
    "   do the parameter count and the FLOPs count of\n",
    "   the equation change under each scheme? Why is the saving\n",
    "   most valuable during autoregressive generation?\n",
    "6. Suppose you want to prune the least important heads of a trained\n",
    "   multi-head attention layer to speed up inference. Design an experiment to\n",
    "   measure how much each head matters. How would you guard against two\n",
    "   heads that are individually prunable but not jointly?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-pytorch",
   "display_name": "d2l (PyTorch)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
