Task04_1_Transformer.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_he9lhbo",
    "id": "B4FB8FF6BA054AE9ABB9FB6650847729",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "# Transformer\n",
    "\n",
    "在之前的章节中，我们已经介绍了主流的神经网络架构如卷积神经网络（CNNs）和循环神经网络（RNNs）。让我们进行一些回顾：\n",
    "\n",
    "- CNNs 易于并行化，却不适合捕捉变长序列内的依赖关系。\n",
    "- RNNs 适合捕捉长距离变长序列的依赖，但是却难以实现并行化处理序列。\n",
    "\n",
    "为了整合CNN和RNN的优势，[\\[Vaswani et al., 2017\\]](https://d2l.ai/chapter_references/zreferences.html#vaswani-shazeer-parmar-ea-2017) 创新性地使用注意力机制设计了Transformer模型。该模型利用attention机制实现了并行化捕捉序列依赖，并且同时处理序列的每个位置的tokens，上述优势使得Transformer模型在性能优异的同时大大减少了训练时间。\n",
    "\n",
    "图10.3.1展示了Transformer模型的架构，与9.7节的seq2seq模型相似，Transformer同样基于编码器-解码器架构，其区别主要在于以下三点：\n",
    "1. Transformer blocks：将seq2seq模型重的循环网络替换为了Transformer Blocks，该模块包含一个多头注意力层（Multi-head Attention Layers）以及两个position-wise feed-forward networks（FFN）。对于解码器来说，另一个多头注意力层被用于接受编码器的隐藏状态。\n",
    "2. Add and norm：多头注意力层和前馈网络的输出被送到两个“add and norm”层进行处理，该层包含残差结构以及层归一化。\n",
    "3. Position encoding：由于自注意力层并没有区分元素的顺序，所以一个位置编码层被用于向序列元素里添加位置信息。\n",
    "\n",
    "![Fig. 10.3.1 The Transformer architecture.](https://cdn.kesci.com/upload/image/q5kpbj2cj5.png?imageView2/0/w/960/h/960)\n",
    "\n",
    "$$\n",
    "Fig.10.3.1\\ Transformer 架构.\n",
    "$$\n",
    "\n",
    "\n",
    "在接下来的部分，我们将会带领大家实现Transformer里全新的子结构，并且构建一个神经机器翻译模型用以训练和测试。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:38:54.542251Z",
     "start_time": "2020-02-18T04:38:53.952311Z"
    },
    "graffitiCellId": "id_lyizjfl",
    "id": "27895557063B415E88AE1B50D61591EE",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "import os\n",
    "import math\n",
    "import numpy as np\n",
    "import torch \n",
    "import torch.nn as nn\n",
    "import torch.nn.functional as F\n",
    "import sys\n",
    "# sys.path.append('/home/kesci/input/d2len9900')\n",
    "import utils as d2l\n",
    "import seq\n",
    "\n",
    "from IPython.core.interactiveshell import InteractiveShell\n",
    "InteractiveShell.ast_node_interactivity = \"all\" \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_qh897q7",
    "id": "EBA491AE83684E379EFC443D6ECD02AD",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "以下是复制了上一小节中 masked softmax 实现，这里就不再赘述了。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:10.033533Z",
     "start_time": "2020-02-18T04:39:10.010445Z"
    },
    "graffitiCellId": "id_qrh3n7g",
    "id": "FC8FDB3160A948EA87012C0479714887",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def SequenceMask(X, X_len,value=-1e6):  # (24,4), (24)\n",
    "    maxlen = X.size(1)  # 4\n",
    "    X_len = X_len.to(X.device)\n",
    "#     print('X_len:', X_len.shape, X_len)  # (24)\n",
    "    #print(X.size(),torch.arange((maxlen),dtype=torch.float)[None, :],'\\n',X_len[:, None] )\n",
    "    mask = torch.arange((maxlen), dtype=torch.float, device=X.device)\n",
    "    mask = mask[None, :] < X_len[:, None]  # \n",
    "#     print('mask.shape:', mask.shape)  # (24,4)\n",
    "    X[~mask]=value\n",
    "#     print('X.shape:', X.shape)  # (24,4)\n",
    "    return X\n",
    "\n",
    "def masked_softmax(X, valid_length):  # (2*3,4,4), (6)\n",
    "    # X: 3-D tensor, valid_length: 1-D or 2-D tensor\n",
    "    softmax = nn.Softmax(dim=-1)\n",
    "    if valid_length is None:\n",
    "        return softmax(X)\n",
    "    else:\n",
    "        shape = X.shape  # (2*3,4,4)\n",
    "        if valid_length.dim() == 1:\n",
    "            try:\n",
    "                # (6) -> (24)\n",
    "                valid_length = torch.FloatTensor(valid_length.numpy().repeat(shape[1], axis=0))#[2,2,3,3]   \n",
    "            except:\n",
    "                valid_length = torch.FloatTensor(valid_length.cpu().numpy().repeat(shape[1], axis=0))#[2,2,3,3]\n",
    "        else:\n",
    "            valid_length = valid_length.reshape((-1,))\n",
    "#         print('valid_length.shape:', valid_length.shape)  # (24)\n",
    "        \n",
    "        # fill masked elements with a large negative, whose exp is 0\n",
    "        # X:(2*3,4,4), valid_length:(24) \n",
    "        X = SequenceMask(X.reshape((-1, shape[-1])), valid_length)  # (24,4), (24) -> (24,4)\n",
    "#         print(X.shape)\n",
    "        return softmax(X).reshape(shape)  # (2*3,4,4)\n",
    "\n",
    "# Save to the d2l package.\n",
    "class DotProductAttention(nn.Module): \n",
    "    def __init__(self, dropout, **kwargs):\n",
    "        super(DotProductAttention, self).__init__(**kwargs)\n",
    "        self.dropout = nn.Dropout(dropout)\n",
    "\n",
    "    # query: (batch_size, #queries, d)\n",
    "    # key: (batch_size, #kv_pairs, d)\n",
    "    # value: (batch_size, #kv_pairs, dim_v)\n",
    "    # valid_length: either (batch_size, ) or (batch_size, xx)\n",
    "    def forward(self, query, key, value, valid_length=None):  # output = self.attention(...), (2*3,4,9), (2*3,4,9), (2*3,4,9), (3)\n",
    "        d = query.shape[-1]  # 9\n",
    "        # set transpose_b=True to swap the last two dimensions of key\n",
    "        scores = torch.bmm(query, key.transpose(1,2)) / math.sqrt(d)  # (2*3,4,4)\n",
    "        \n",
    "#         print('scores.shape:', scores.shape)  # (6,4,4)\n",
    "#         print('valid_length.shape:', valid_length.shape)  # (6)\n",
    "        attention_weights = self.dropout(masked_softmax(scores, valid_length))  # (2*3,4,4), (6) -> (2*3,4,4)\n",
    "        return torch.bmm(attention_weights, value)  # (2*3,4,4), (2*3,4,9) -> (2*3,4,9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:10.678760Z",
     "start_time": "2020-02-18T04:39:10.664444Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([6, 4, 4])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = torch.rand(6,4,4)\n",
    "valid = torch.rand(6)\n",
    "b = masked_softmax(a, valid)\n",
    "b.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:11.904244Z",
     "start_time": "2020-02-18T04:39:11.893238Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([24])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# import random\n",
    "valid_length = torch.rand(6)\n",
    "# if valid_length.ndim == 1:\n",
    "#     valid_length = torch.FloatTensor(np.tile(valid_length, 3))\n",
    "valid_length = torch.FloatTensor(valid_length.numpy().repeat(4, axis=0))\n",
    "valid_length.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_bimjldk",
    "id": "DC958EB387A046F9861833718978DDBE",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## 多头注意力层\n",
    "\n",
    "在我们讨论多头注意力层之前，先来迅速理解以下自注意力（self-attention）的结构。自注意力模型是一个正规的注意力模型，序列的每一个元素对应的key，value，query是完全一致的。如图10.3.2 自注意力输出了一个与输入长度相同的表征序列，与循环神经网络相比，自注意力对每个元素输出的计算是并行的，所以我们可以高效的实现这个模块。\n",
    "\n",
    "![Fig. 10.3.2 自注意力结构](https://cdn.kesci.com/upload/image/q5kpckv38q.png?imageView2/0/w/320/h/320)\n",
    "\n",
    "$$\n",
    "Fig.10.3.2\\ 自注意力结构\n",
    "$$\n",
    "\n",
    "\n",
    "多头注意力层包含$h$个并行的自注意力层，每一个这种层被成为一个head。对每个头来说，在进行注意力计算之前，我们会将query、key和value用三个现行层进行映射，这$h$个注意力头的输出将会被拼接之后输入最后一个线性层进行整合。\n",
    "\n",
    "![Image Name](https://cdn.kesci.com/upload/image/q5kpcsozid.png?imageView2/0/w/640/h/640)\n",
    "\n",
    "$$\n",
    "Fig.10.3.3\\ 多头注意力\n",
    "$$\n",
    "\n",
    "\n",
    "假设query，key和value的维度分别是$d_q$、$d_k$和$d_v$。那么对于每一个头$i=1,\\ldots,h$，我们可以训练相应的模型权重$W_q^{(i)} \\in \\mathbb{R}^{p_q\\times d_q}$、$W_k^{(i)} \\in \\mathbb{R}^{p_k\\times d_k}$和$W_v^{(i)} \\in \\mathbb{R}^{p_v\\times d_v}$，以得到每个头的输出：\n",
    "\n",
    "\n",
    "$$\n",
    "o^{(i)} = attention(W_q^{(i)}q, W_k^{(i)}k, W_v^{(i)}v)\n",
    "$$\n",
    "\n",
    "\n",
    "这里的attention可以是任意的attention function，比如前一节介绍的dot-product attention以及MLP attention。之后我们将所有head对应的输出拼接起来，送入最后一个线性层进行整合，这个层的权重可以表示为$W_o\\in \\mathbb{R}^{d_0 \\times hp_v}$\n",
    "\n",
    "\n",
    "$$\n",
    "o = W_o[o^{(1)}, \\ldots, o^{(h)}]\n",
    "$$\n",
    "\n",
    "\n",
    "接下来我们就可以来实现多头注意力了，假设我们有h个头，隐藏层权重 $hidden\\_size = p_q = p_k = p_v$ 与query，key，value的维度一致。除此之外，因为多头注意力层保持输入与输出张量的维度不变，所以输出feature的维度也设置为 $d_0 = hidden\\_size$。"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![image.png](attachment::image.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:15.673908Z",
     "start_time": "2020-02-18T04:39:15.650784Z"
    },
    "graffitiCellId": "id_39i6msf",
    "id": "77DA0FFB2D2E4A7C83FBCEEE64D69DE4",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# cell = MultiHeadAttention(5, 9, 3, 0.5)\n",
    "# X = torch.ones((2, 4, 5))\n",
    "# valid_length = torch.FloatTensor([2, 3])\n",
    "# cell(X, X, X, valid_length).shape\n",
    "\n",
    "class MultiHeadAttention(nn.Module):\n",
    "    def __init__(self, input_size, hidden_size, num_heads, dropout, **kwargs):\n",
    "        super(MultiHeadAttention, self).__init__(**kwargs)\n",
    "        self.num_heads = num_heads  # 3\n",
    "        self.attention = DotProductAttention(dropout)  # 0.5\n",
    "        self.W_q = nn.Linear(input_size, hidden_size, bias=False)  # 5, 9\n",
    "        self.W_k = nn.Linear(input_size, hidden_size, bias=False)\n",
    "        self.W_v = nn.Linear(input_size, hidden_size, bias=False)\n",
    "        self.W_o = nn.Linear(hidden_size, hidden_size, bias=False)\n",
    "    \n",
    "    def forward(self, query, key, value, valid_length):  # (2, 4, 5)，(2, 4, 5)，(2, 4, 5)， [2, 3]\n",
    "        # query, key, and value shape: (batch_size, seq_len, dim),  2句话，4个词，5维词向量\n",
    "        # where seq_len is the length of input sequence\n",
    "        # valid_length shape is either (batch_size, )\n",
    "        # or (batch_size, seq_len).\n",
    "\n",
    "        # Project and transpose query, key, and value \n",
    "        # from (batch_size, seq_len, hidden_size * num_heads)    2句话，4个词，9维词向量*3头注意力\n",
    "        # to   (batch_size * num_heads, seq_len, hidden_size).   2句话*3头注意力，4个词，9维词向量\n",
    "        \n",
    "        # query:(2,4,5)\n",
    "        query = transpose_qkv(self.W_q(query), self.num_heads)  # (2,4,9),3 -> (6,4,9)\n",
    "        key = transpose_qkv(self.W_k(key), self.num_heads)\n",
    "        value = transpose_qkv(self.W_v(value), self.num_heads)\n",
    "        \n",
    "        if valid_length is not None:\n",
    "            # Copy valid_length by num_heads times\n",
    "            device = valid_length.device\n",
    "            valid_length = valid_length.cpu().numpy() if valid_length.is_cuda else valid_length.numpy()\n",
    "            if valid_length.ndim == 1:  # 共1维\n",
    "                # 将valid_length沿着X轴扩大3倍。如果扩大倍数只有一个，默认为X轴\n",
    "                valid_length = torch.FloatTensor(np.tile(valid_length, self.num_heads))  # (1) -> (3)\n",
    "#                 print('valid_length.shape:', valid_length.shape) \n",
    "            else:\n",
    "                # 第一个参数为Y轴扩大倍数，第二个为X轴扩大倍数\n",
    "                valid_length = torch.FloatTensor(np.tile(valid_length, (self.num_heads,1)))  # \n",
    "            valid_length = valid_length.to(device)\n",
    "            \n",
    "        output = self.attention(query, key, value, valid_length)  # (6,4,9), (6,4,9), (6,4,9), (3) -> (6,4,3)!!!!!!!!!!!!!!!!\n",
    "                                                                  # 2句话*3头注意力, 4个词, 9维词向量\n",
    "#         print('output.shape:', output.shape)  # (6,4,3)\n",
    "        output_concat = transpose_output(output, self.num_heads)  # (6,4,9), 3 -> # (2,4,9)!!!!!!!!!!!!!!!!\n",
    "#         print('output_concat.shape:', output_concat.shape)  # (2,4,9)\n",
    "        return self.W_o(output_concat)  # (2,4,9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:16.364078Z",
     "start_time": "2020-02-18T04:39:16.349893Z"
    },
    "graffitiCellId": "id_mlvtr3b",
    "id": "E5580A1C9FFB434094200A8CBF1F31F6",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def transpose_qkv(X, num_heads):  # (2,4,9), 3\n",
    "#     print('X.shape:', X.shape)\n",
    "    # Original X shape: (batch_size, seq_len, hidden_size * num_heads),  (2,4,3*3)  2句话，4个词，3维词向量*3头注意力\n",
    "    # -1 means inferring its value, after first reshape, X shape:\n",
    "    # (batch_size, seq_len, num_heads, hidden_size)                      (2,4,3,3)  2句话，4个词，3头注意力, 3维词向量\n",
    "    X = X.view(X.shape[0], X.shape[1], num_heads, -1)  # (2,4,3,3)\n",
    "\n",
    "    # After transpose, X shape: (batch_size, num_heads, seq_len, hidden_size)   (2,3,4,3)  2句话，3头注意力, 4个词, 9维词向量\n",
    "    X = X.transpose(2, 1).contiguous()\n",
    "\n",
    "    # Merge the first two dimensions. Use reverse=True to infer shape from\n",
    "    # right to left.\n",
    "    # output shape: (batch_size * num_heads, seq_len, hidden_size)      (6,4,3)  2句话*3头注意力, 4个词, 9维词向量\n",
    "    output = X.view(-1, X.shape[2], X.shape[3])\n",
    "    \n",
    "    return output  # (2,4,9), 3 -> (6,4,3) \n",
    "\n",
    "\n",
    "# Saved in the d2l package for later use\n",
    "def transpose_output(X, num_heads):  # (6,4, 3)=(batch_size*h,seq_len,hidden_size), 3\n",
    "    # A reversed version of transpose_qkv\n",
    "#     print('X.shape:', X.shape)\n",
    "    X = X.view(-1, num_heads, X.shape[1], X.shape[2])  # (2,3,4, 3)\n",
    "#     print('X.shape:', X.shape)\n",
    "    X = X.transpose(2, 1).contiguous()  # (2,4,3, 3)\n",
    "#     print('X.shape:', X.shape)\n",
    "    return X.view(X.shape[0], X.shape[1], -1)  # (2,4,9)=(batch_size,seq_len,hidden_size*h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:17.106007Z",
     "start_time": "2020-02-18T04:39:17.089436Z"
    },
    "graffitiCellId": "id_gjfsirw",
    "id": "165195251F95481C87506682632ECAA0",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([2, 4, 9])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# batch_size = 2, seq_len = 4, dim = 5\n",
    "# input_size = 5, hidden_size = 9, num_heads = 3注意力机制\n",
    "# valid_length = torch.FloatTensor([2, 3])\n",
    "\n",
    "X = torch.ones((2, 4, 5))\n",
    "cell = MultiHeadAttention(5, 9, 3, 0.5)\n",
    "valid_length = torch.FloatTensor([2, 3])\n",
    "cell(X, X, X, valid_length).shape\n",
    "\n",
    "# l = nn.Linear(5, 9, bias=False)\n",
    "# l(X).shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_5l05rc9",
    "id": "81A5959A3ED0424CA0B4670CBDFF9E9D",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "# 基于位置的前馈网络\n",
    "\n",
    "Transformer 模块另一个非常重要的部分就是基于位置的前馈网络（FFN），它接受一个形状为（batch_size，seq_length, feature_size）的三维张量。Position-wise FFN由两个全连接层组成，他们作用在最后一维上。因为序列的每个位置的状态都会被单独地更新，所以我们称他为position-wise，这等效于一个1x1的卷积。\n",
    "\n",
    "下面我们来实现PositionWiseFFN："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:18.800657Z",
     "start_time": "2020-02-18T04:39:18.789222Z"
    },
    "graffitiCellId": "id_qpr6dwm",
    "id": "7D631C416175432C8E15C0949EEAADD8",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Save to the d2l package.\n",
    "class PositionWiseFFN(nn.Module):\n",
    "    def __init__(self, input_size, ffn_hidden_size, hidden_size_out, **kwargs):\n",
    "        super(PositionWiseFFN, self).__init__(**kwargs)\n",
    "        self.ffn_1 = nn.Linear(input_size, ffn_hidden_size)\n",
    "        self.ffn_2 = nn.Linear(ffn_hidden_size, hidden_size_out)\n",
    "        \n",
    "        \n",
    "    def forward(self, X):\n",
    "        return self.ffn_2(F.relu(self.ffn_1(X)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_sy1n984",
    "id": "77B18910C4A84157888CA6AAD1CDA7F2",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "与多头注意力层相似，FFN层同样只会对最后一维的大小进行改变；除此之外，对于两个完全相同的输入，FFN层的输出也将相等。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:20.020748Z",
     "start_time": "2020-02-18T04:39:20.008214Z"
    },
    "graffitiCellId": "id_rt2wg6w",
    "id": "342DB0217414477AA49EAE019D18A40B",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tensor([[[ 0.3590, -0.7684, -0.2128,  0.2230, -0.0943,  0.2775,  0.5660,\n",
      "          -0.3555],\n",
      "         [ 0.3590, -0.7684, -0.2128,  0.2230, -0.0943,  0.2775,  0.5660,\n",
      "          -0.3555],\n",
      "         [ 0.3590, -0.7684, -0.2128,  0.2230, -0.0943,  0.2775,  0.5660,\n",
      "          -0.3555]],\n",
      "\n",
      "        [[ 0.3590, -0.7684, -0.2128,  0.2230, -0.0943,  0.2775,  0.5660,\n",
      "          -0.3555],\n",
      "         [ 0.3590, -0.7684, -0.2128,  0.2230, -0.0943,  0.2775,  0.5660,\n",
      "          -0.3555],\n",
      "         [ 0.3590, -0.7684, -0.2128,  0.2230, -0.0943,  0.2775,  0.5660,\n",
      "          -0.3555]]], grad_fn=<AddBackward0>) torch.Size([2, 3, 8])\n"
     ]
    }
   ],
   "source": [
    "ffn = PositionWiseFFN(4, 4, 8)\n",
    "out = ffn(torch.ones((2,3,4)))\n",
    "\n",
    "print(out, out.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_vqmu7c7",
    "id": "A4F17C69EF4B40E885CAD7B3E537952E",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## Add and Norm\n",
    "\n",
    "除了上面两个模块之外，Transformer还有一个重要的相加归一化层，它可以平滑地整合输入和其他层的输出，因此我们在每个多头注意力层和FFN层后面都添加一个含残差连接的Layer Norm层。这里 Layer Norm 与7.5小节的Batch Norm很相似，唯一的区别在于Batch Norm是对于batch size这个维度进行计算均值和方差的，而Layer Norm则是对最后一维进行计算。层归一化可以防止层内的数值变化过大，从而有利于加快训练速度并且提高泛化性能。 [(ref)](https://zhuanlan.zhihu.com/p/54530247)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:21.467871Z",
     "start_time": "2020-02-18T04:39:21.451369Z"
    },
    "graffitiCellId": "id_5aer6fc",
    "id": "9EA6172929A949B0ADDF5D3C9AA4DD26",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "layer norm: tensor([[-1.0000,  1.0000],\n",
      "        [-1.0000,  1.0000]], grad_fn=<AddcmulBackward>)\n",
      "batch norm: tensor([[-0.4728, -0.0259],\n",
      "        [ 0.4728,  0.0259]], grad_fn=<NativeBatchNormBackward>)\n"
     ]
    }
   ],
   "source": [
    "layernorm = nn.LayerNorm(normalized_shape=2, elementwise_affine=True)\n",
    "batchnorm = nn.BatchNorm1d(num_features=2, affine=True)\n",
    "X = torch.FloatTensor([[1,2], [3,4]])\n",
    "print('layer norm:', layernorm(X))\n",
    "print('batch norm:', batchnorm(X))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:21.932550Z",
     "start_time": "2020-02-18T04:39:21.921879Z"
    },
    "graffitiCellId": "id_2pmvrcv",
    "id": "F613FA3D7F634598832BFA21F4BE23F4",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Save to the d2l package.\n",
    "class AddNorm(nn.Module):\n",
    "    def __init__(self, hidden_size, dropout, **kwargs):\n",
    "        super(AddNorm, self).__init__(**kwargs)\n",
    "        self.dropout = nn.Dropout(dropout)\n",
    "        self.norm = nn.LayerNorm(hidden_size)\n",
    "    \n",
    "    def forward(self, X, Y):\n",
    "        return self.norm(self.dropout(Y) + X)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_o2cxg9q",
    "id": "6B61136E6BD445BC994009529C93D75B",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "由于残差连接，X和Y需要有相同的维度。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:22.779285Z",
     "start_time": "2020-02-18T04:39:22.766868Z"
    },
    "graffitiCellId": "id_ji2koe2",
    "id": "1031B32CEFB344F28BA2505954195AD3",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([2, 3, 4])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "add_norm = AddNorm(4, 0.5)\n",
    "add_norm(torch.ones((2,3,4)), torch.ones((2,3,4))).shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_qqem3ml",
    "id": "438B44D7FE7540F589AF4833D148F58A",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "## 位置编码\n",
    "\n",
    "与循环神经网络不同，无论是多头注意力网络还是前馈神经网络都是独立地对每个位置的元素进行更新，这种特性帮助我们实现了高效的并行，却丢失了重要的序列顺序的信息。为了更好的捕捉序列信息，Transformer模型引入了位置编码去保持输入序列元素的位置。\n",
    "\n",
    "假设输入序列的嵌入表示 $X\\in \\mathbb{R}^{l\\times d}$, 序列长度为$l$嵌入向量维度为$d$，则其位置编码为$P \\in \\mathbb{R}^{l\\times d}$ ，输出的向量就是二者相加 $X + P$。\n",
    "\n",
    "位置编码是一个二维的矩阵，i对应着序列中的顺序，j对应其embedding vector内部的维度索引。我们可以通过以下等式计算位置编码：\n",
    "\n",
    "$$\n",
    "P_{i,2j} = sin(i/10000^{2j/d})\n",
    "$$\n",
    "\n",
    "\n",
    "$$\n",
    "P_{i,2j+1} = cos(i/10000^{2j/d})\n",
    "$$\n",
    "\n",
    "$$\n",
    "for\\ i=0,\\ldots, l-1\\ and\\ j=0,\\ldots,\\lfloor (d-1)/2 \\rfloor\n",
    "$$\n",
    "\n",
    "\n",
    "![Image Name](https://cdn.kesci.com/upload/image/q5kpe0lu38.png?imageView2/0/w/640/h/640)\n",
    "\n",
    "$$\n",
    "Fig. 10.3.4\\ 位置编码\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:24.343322Z",
     "start_time": "2020-02-18T04:39:24.326313Z"
    },
    "graffitiCellId": "id_xbbsd1x",
    "id": "A3322BF25A5446FEA39FEDBB230A60FD",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class PositionalEncoding(nn.Module):\n",
    "    def __init__(self, embedding_size, dropout, max_len=1000):\n",
    "        super(PositionalEncoding, self).__init__()\n",
    "        self.dropout = nn.Dropout(dropout)\n",
    "        self.P = np.zeros((1, max_len, embedding_size))\n",
    "        X = np.arange(0, max_len).reshape(-1, 1) / np.power(\n",
    "            10000, np.arange(0, embedding_size, 2)/embedding_size)\n",
    "        self.P[:, :, 0::2] = np.sin(X)\n",
    "        self.P[:, :, 1::2] = np.cos(X)\n",
    "        self.P = torch.FloatTensor(self.P)\n",
    "    \n",
    "    def forward(self, X):\n",
    "        if X.is_cuda and not self.P.is_cuda:\n",
    "            self.P = self.P.cuda()\n",
    "        X = X + self.P[:, :X.shape[1], :]\n",
    "        return self.dropout(X)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_9bq3vbt",
    "id": "ADDEE760DA9B414E82922FF417DC4ACC",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "### 测试\n",
    "\n",
    "下面我们用PositionalEncoding这个类进行一个小测试，取其中的四个维度进行可视化。 我们可以看到，第4维和第5维有相同的频率但偏置不同。第6维和第7维具有更低的频率；因此positional encoding对于不同维度具有可区分性。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:26.072666Z",
     "start_time": "2020-02-18T04:39:25.869301Z"
    },
    "graffitiCellId": "id_kn0kaqb",
    "id": "CDB21A80016E43A284D08F0D93E562F4",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "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",
       "<!-- Created with matplotlib (https://matplotlib.org/) -->\n",
       "<svg height=\"166.978125pt\" version=\"1.1\" viewBox=\"0 0 882.682813 166.978125\" width=\"882.682813pt\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       " <defs>\n",
       "  <style type=\"text/css\">\n",
       "*{stroke-linecap:butt;stroke-linejoin:round;}\n",
       "  </style>\n",
       " </defs>\n",
       " <g id=\"figure_1\">\n",
       "  <g id=\"patch_1\">\n",
       "   <path d=\"M 0 166.978125 \n",
       "L 882.682813 166.978125 \n",
       "L 882.682813 0 \n",
       "L 0 0 \n",
       "z\n",
       "\" style=\"fill:none;\"/>\n",
       "  </g>\n",
       "  <g id=\"axes_1\">\n",
       "   <g id=\"patch_2\">\n",
       "    <path d=\"M 38.482813 143.1 \n",
       "L 875.482813 143.1 \n",
       "L 875.482813 7.2 \n",
       "L 38.482813 7.2 \n",
       "z\n",
       "\" style=\"fill:#ffffff;\"/>\n",
       "   </g>\n",
       "   <g id=\"matplotlib.axis_1\">\n",
       "    <g id=\"xtick_1\">\n",
       "     <g id=\"line2d_1\">\n",
       "      <path clip-path=\"url(#pb3157f7082)\" d=\"M 76.528267 143.1 \n",
       "L 76.528267 7.2 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_2\">\n",
       "      <defs>\n",
       "       <path d=\"M 0 0 \n",
       "L 0 3.5 \n",
       "\" id=\"m09854dd102\" style=\"stroke:#000000;stroke-width:0.8;\"/>\n",
       "      </defs>\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"76.528267\" xlink:href=\"#m09854dd102\" y=\"143.1\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_1\">\n",
       "      <!-- 0 -->\n",
       "      <defs>\n",
       "       <path d=\"M 31.78125 66.40625 \n",
       "Q 24.171875 66.40625 20.328125 58.90625 \n",
       "Q 16.5 51.421875 16.5 36.375 \n",
       "Q 16.5 21.390625 20.328125 13.890625 \n",
       "Q 24.171875 6.390625 31.78125 6.390625 \n",
       "Q 39.453125 6.390625 43.28125 13.890625 \n",
       "Q 47.125 21.390625 47.125 36.375 \n",
       "Q 47.125 51.421875 43.28125 58.90625 \n",
       "Q 39.453125 66.40625 31.78125 66.40625 \n",
       "z\n",
       "M 31.78125 74.21875 \n",
       "Q 44.046875 74.21875 50.515625 64.515625 \n",
       "Q 56.984375 54.828125 56.984375 36.375 \n",
       "Q 56.984375 17.96875 50.515625 8.265625 \n",
       "Q 44.046875 -1.421875 31.78125 -1.421875 \n",
       "Q 19.53125 -1.421875 13.0625 8.265625 \n",
       "Q 6.59375 17.96875 6.59375 36.375 \n",
       "Q 6.59375 54.828125 13.0625 64.515625 \n",
       "Q 19.53125 74.21875 31.78125 74.21875 \n",
       "z\n",
       "\" id=\"DejaVuSans-48\"/>\n",
       "      </defs>\n",
       "      <g transform=\"translate(73.347017 157.698438)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-48\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_2\">\n",
       "     <g id=\"line2d_3\">\n",
       "      <path clip-path=\"url(#pb3157f7082)\" d=\"M 230.247275 143.1 \n",
       "L 230.247275 7.2 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_4\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"230.247275\" xlink:href=\"#m09854dd102\" y=\"143.1\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_2\">\n",
       "      <!-- 20 -->\n",
       "      <defs>\n",
       "       <path d=\"M 19.1875 8.296875 \n",
       "L 53.609375 8.296875 \n",
       "L 53.609375 0 \n",
       "L 7.328125 0 \n",
       "L 7.328125 8.296875 \n",
       "Q 12.9375 14.109375 22.625 23.890625 \n",
       "Q 32.328125 33.6875 34.8125 36.53125 \n",
       "Q 39.546875 41.84375 41.421875 45.53125 \n",
       "Q 43.3125 49.21875 43.3125 52.78125 \n",
       "Q 43.3125 58.59375 39.234375 62.25 \n",
       "Q 35.15625 65.921875 28.609375 65.921875 \n",
       "Q 23.96875 65.921875 18.8125 64.3125 \n",
       "Q 13.671875 62.703125 7.8125 59.421875 \n",
       "L 7.8125 69.390625 \n",
       "Q 13.765625 71.78125 18.9375 73 \n",
       "Q 24.125 74.21875 28.421875 74.21875 \n",
       "Q 39.75 74.21875 46.484375 68.546875 \n",
       "Q 53.21875 62.890625 53.21875 53.421875 \n",
       "Q 53.21875 48.921875 51.53125 44.890625 \n",
       "Q 49.859375 40.875 45.40625 35.40625 \n",
       "Q 44.1875 33.984375 37.640625 27.21875 \n",
       "Q 31.109375 20.453125 19.1875 8.296875 \n",
       "z\n",
       "\" id=\"DejaVuSans-50\"/>\n",
       "      </defs>\n",
       "      <g transform=\"translate(223.884775 157.698438)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-50\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-48\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_3\">\n",
       "     <g id=\"line2d_5\">\n",
       "      <path clip-path=\"url(#pb3157f7082)\" d=\"M 383.966284 143.1 \n",
       "L 383.966284 7.2 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_6\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"383.966284\" xlink:href=\"#m09854dd102\" y=\"143.1\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_3\">\n",
       "      <!-- 40 -->\n",
       "      <defs>\n",
       "       <path d=\"M 37.796875 64.3125 \n",
       "L 12.890625 25.390625 \n",
       "L 37.796875 25.390625 \n",
       "z\n",
       "M 35.203125 72.90625 \n",
       "L 47.609375 72.90625 \n",
       "L 47.609375 25.390625 \n",
       "L 58.015625 25.390625 \n",
       "L 58.015625 17.1875 \n",
       "L 47.609375 17.1875 \n",
       "L 47.609375 0 \n",
       "L 37.796875 0 \n",
       "L 37.796875 17.1875 \n",
       "L 4.890625 17.1875 \n",
       "L 4.890625 26.703125 \n",
       "z\n",
       "\" id=\"DejaVuSans-52\"/>\n",
       "      </defs>\n",
       "      <g transform=\"translate(377.603784 157.698438)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-52\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-48\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_4\">\n",
       "     <g id=\"line2d_7\">\n",
       "      <path clip-path=\"url(#pb3157f7082)\" d=\"M 537.685292 143.1 \n",
       "L 537.685292 7.2 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_8\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"537.685292\" xlink:href=\"#m09854dd102\" y=\"143.1\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_4\">\n",
       "      <!-- 60 -->\n",
       "      <defs>\n",
       "       <path d=\"M 33.015625 40.375 \n",
       "Q 26.375 40.375 22.484375 35.828125 \n",
       "Q 18.609375 31.296875 18.609375 23.390625 \n",
       "Q 18.609375 15.53125 22.484375 10.953125 \n",
       "Q 26.375 6.390625 33.015625 6.390625 \n",
       "Q 39.65625 6.390625 43.53125 10.953125 \n",
       "Q 47.40625 15.53125 47.40625 23.390625 \n",
       "Q 47.40625 31.296875 43.53125 35.828125 \n",
       "Q 39.65625 40.375 33.015625 40.375 \n",
       "z\n",
       "M 52.59375 71.296875 \n",
       "L 52.59375 62.3125 \n",
       "Q 48.875 64.0625 45.09375 64.984375 \n",
       "Q 41.3125 65.921875 37.59375 65.921875 \n",
       "Q 27.828125 65.921875 22.671875 59.328125 \n",
       "Q 17.53125 52.734375 16.796875 39.40625 \n",
       "Q 19.671875 43.65625 24.015625 45.921875 \n",
       "Q 28.375 48.1875 33.59375 48.1875 \n",
       "Q 44.578125 48.1875 50.953125 41.515625 \n",
       "Q 57.328125 34.859375 57.328125 23.390625 \n",
       "Q 57.328125 12.15625 50.6875 5.359375 \n",
       "Q 44.046875 -1.421875 33.015625 -1.421875 \n",
       "Q 20.359375 -1.421875 13.671875 8.265625 \n",
       "Q 6.984375 17.96875 6.984375 36.375 \n",
       "Q 6.984375 53.65625 15.1875 63.9375 \n",
       "Q 23.390625 74.21875 37.203125 74.21875 \n",
       "Q 40.921875 74.21875 44.703125 73.484375 \n",
       "Q 48.484375 72.75 52.59375 71.296875 \n",
       "z\n",
       "\" id=\"DejaVuSans-54\"/>\n",
       "      </defs>\n",
       "      <g transform=\"translate(531.322792 157.698438)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-54\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-48\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_5\">\n",
       "     <g id=\"line2d_9\">\n",
       "      <path clip-path=\"url(#pb3157f7082)\" d=\"M 691.4043 143.1 \n",
       "L 691.4043 7.2 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_10\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"691.4043\" xlink:href=\"#m09854dd102\" y=\"143.1\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_5\">\n",
       "      <!-- 80 -->\n",
       "      <defs>\n",
       "       <path d=\"M 31.78125 34.625 \n",
       "Q 24.75 34.625 20.71875 30.859375 \n",
       "Q 16.703125 27.09375 16.703125 20.515625 \n",
       "Q 16.703125 13.921875 20.71875 10.15625 \n",
       "Q 24.75 6.390625 31.78125 6.390625 \n",
       "Q 38.8125 6.390625 42.859375 10.171875 \n",
       "Q 46.921875 13.96875 46.921875 20.515625 \n",
       "Q 46.921875 27.09375 42.890625 30.859375 \n",
       "Q 38.875 34.625 31.78125 34.625 \n",
       "z\n",
       "M 21.921875 38.8125 \n",
       "Q 15.578125 40.375 12.03125 44.71875 \n",
       "Q 8.5 49.078125 8.5 55.328125 \n",
       "Q 8.5 64.0625 14.71875 69.140625 \n",
       "Q 20.953125 74.21875 31.78125 74.21875 \n",
       "Q 42.671875 74.21875 48.875 69.140625 \n",
       "Q 55.078125 64.0625 55.078125 55.328125 \n",
       "Q 55.078125 49.078125 51.53125 44.71875 \n",
       "Q 48 40.375 41.703125 38.8125 \n",
       "Q 48.828125 37.15625 52.796875 32.3125 \n",
       "Q 56.78125 27.484375 56.78125 20.515625 \n",
       "Q 56.78125 9.90625 50.3125 4.234375 \n",
       "Q 43.84375 -1.421875 31.78125 -1.421875 \n",
       "Q 19.734375 -1.421875 13.25 4.234375 \n",
       "Q 6.78125 9.90625 6.78125 20.515625 \n",
       "Q 6.78125 27.484375 10.78125 32.3125 \n",
       "Q 14.796875 37.15625 21.921875 38.8125 \n",
       "z\n",
       "M 18.3125 54.390625 \n",
       "Q 18.3125 48.734375 21.84375 45.5625 \n",
       "Q 25.390625 42.390625 31.78125 42.390625 \n",
       "Q 38.140625 42.390625 41.71875 45.5625 \n",
       "Q 45.3125 48.734375 45.3125 54.390625 \n",
       "Q 45.3125 60.0625 41.71875 63.234375 \n",
       "Q 38.140625 66.40625 31.78125 66.40625 \n",
       "Q 25.390625 66.40625 21.84375 63.234375 \n",
       "Q 18.3125 60.0625 18.3125 54.390625 \n",
       "z\n",
       "\" id=\"DejaVuSans-56\"/>\n",
       "      </defs>\n",
       "      <g transform=\"translate(685.0418 157.698438)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-56\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-48\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"xtick_6\">\n",
       "     <g id=\"line2d_11\">\n",
       "      <path clip-path=\"url(#pb3157f7082)\" d=\"M 845.123308 143.1 \n",
       "L 845.123308 7.2 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_12\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"845.123308\" xlink:href=\"#m09854dd102\" y=\"143.1\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_6\">\n",
       "      <!-- 100 -->\n",
       "      <defs>\n",
       "       <path d=\"M 12.40625 8.296875 \n",
       "L 28.515625 8.296875 \n",
       "L 28.515625 63.921875 \n",
       "L 10.984375 60.40625 \n",
       "L 10.984375 69.390625 \n",
       "L 28.421875 72.90625 \n",
       "L 38.28125 72.90625 \n",
       "L 38.28125 8.296875 \n",
       "L 54.390625 8.296875 \n",
       "L 54.390625 0 \n",
       "L 12.40625 0 \n",
       "z\n",
       "\" id=\"DejaVuSans-49\"/>\n",
       "      </defs>\n",
       "      <g transform=\"translate(835.579558 157.698438)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-49\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-48\"/>\n",
       "       <use x=\"127.246094\" xlink:href=\"#DejaVuSans-48\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"matplotlib.axis_2\">\n",
       "    <g id=\"ytick_1\">\n",
       "     <g id=\"line2d_13\">\n",
       "      <path clip-path=\"url(#pb3157f7082)\" d=\"M 38.482813 136.92508 \n",
       "L 875.482813 136.92508 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_14\">\n",
       "      <defs>\n",
       "       <path d=\"M 0 0 \n",
       "L -3.5 0 \n",
       "\" id=\"me52ac7fd2b\" style=\"stroke:#000000;stroke-width:0.8;\"/>\n",
       "      </defs>\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"38.482813\" xlink:href=\"#me52ac7fd2b\" y=\"136.92508\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_7\">\n",
       "      <!-- −1.0 -->\n",
       "      <defs>\n",
       "       <path d=\"M 10.59375 35.5 \n",
       "L 73.1875 35.5 \n",
       "L 73.1875 27.203125 \n",
       "L 10.59375 27.203125 \n",
       "z\n",
       "\" id=\"DejaVuSans-8722\"/>\n",
       "       <path d=\"M 10.6875 12.40625 \n",
       "L 21 12.40625 \n",
       "L 21 0 \n",
       "L 10.6875 0 \n",
       "z\n",
       "\" id=\"DejaVuSans-46\"/>\n",
       "      </defs>\n",
       "      <g transform=\"translate(7.2 140.724299)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-8722\"/>\n",
       "       <use x=\"83.789062\" xlink:href=\"#DejaVuSans-49\"/>\n",
       "       <use x=\"147.412109\" xlink:href=\"#DejaVuSans-46\"/>\n",
       "       <use x=\"179.199219\" xlink:href=\"#DejaVuSans-48\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_2\">\n",
       "     <g id=\"line2d_15\">\n",
       "      <path clip-path=\"url(#pb3157f7082)\" d=\"M 38.482813 106.038128 \n",
       "L 875.482813 106.038128 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_16\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"38.482813\" xlink:href=\"#me52ac7fd2b\" y=\"106.038128\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_8\">\n",
       "      <!-- −0.5 -->\n",
       "      <defs>\n",
       "       <path d=\"M 10.796875 72.90625 \n",
       "L 49.515625 72.90625 \n",
       "L 49.515625 64.59375 \n",
       "L 19.828125 64.59375 \n",
       "L 19.828125 46.734375 \n",
       "Q 21.96875 47.46875 24.109375 47.828125 \n",
       "Q 26.265625 48.1875 28.421875 48.1875 \n",
       "Q 40.625 48.1875 47.75 41.5 \n",
       "Q 54.890625 34.8125 54.890625 23.390625 \n",
       "Q 54.890625 11.625 47.5625 5.09375 \n",
       "Q 40.234375 -1.421875 26.90625 -1.421875 \n",
       "Q 22.3125 -1.421875 17.546875 -0.640625 \n",
       "Q 12.796875 0.140625 7.71875 1.703125 \n",
       "L 7.71875 11.625 \n",
       "Q 12.109375 9.234375 16.796875 8.0625 \n",
       "Q 21.484375 6.890625 26.703125 6.890625 \n",
       "Q 35.15625 6.890625 40.078125 11.328125 \n",
       "Q 45.015625 15.765625 45.015625 23.390625 \n",
       "Q 45.015625 31 40.078125 35.4375 \n",
       "Q 35.15625 39.890625 26.703125 39.890625 \n",
       "Q 22.75 39.890625 18.8125 39.015625 \n",
       "Q 14.890625 38.140625 10.796875 36.28125 \n",
       "z\n",
       "\" id=\"DejaVuSans-53\"/>\n",
       "      </defs>\n",
       "      <g transform=\"translate(7.2 109.837347)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-8722\"/>\n",
       "       <use x=\"83.789062\" xlink:href=\"#DejaVuSans-48\"/>\n",
       "       <use x=\"147.412109\" xlink:href=\"#DejaVuSans-46\"/>\n",
       "       <use x=\"179.199219\" xlink:href=\"#DejaVuSans-53\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_3\">\n",
       "     <g id=\"line2d_17\">\n",
       "      <path clip-path=\"url(#pb3157f7082)\" d=\"M 38.482813 75.151176 \n",
       "L 875.482813 75.151176 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_18\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"38.482813\" xlink:href=\"#me52ac7fd2b\" y=\"75.151176\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_9\">\n",
       "      <!-- 0.0 -->\n",
       "      <g transform=\"translate(15.579688 78.950395)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-48\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-46\"/>\n",
       "       <use x=\"95.410156\" xlink:href=\"#DejaVuSans-48\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_4\">\n",
       "     <g id=\"line2d_19\">\n",
       "      <path clip-path=\"url(#pb3157f7082)\" d=\"M 38.482813 44.264225 \n",
       "L 875.482813 44.264225 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_20\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"38.482813\" xlink:href=\"#me52ac7fd2b\" y=\"44.264225\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_10\">\n",
       "      <!-- 0.5 -->\n",
       "      <g transform=\"translate(15.579688 48.063443)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-48\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-46\"/>\n",
       "       <use x=\"95.410156\" xlink:href=\"#DejaVuSans-53\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"ytick_5\">\n",
       "     <g id=\"line2d_21\">\n",
       "      <path clip-path=\"url(#pb3157f7082)\" d=\"M 38.482813 13.377273 \n",
       "L 875.482813 13.377273 \n",
       "\" style=\"fill:none;stroke:#b0b0b0;stroke-linecap:square;stroke-width:0.8;\"/>\n",
       "     </g>\n",
       "     <g id=\"line2d_22\">\n",
       "      <g>\n",
       "       <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"38.482813\" xlink:href=\"#me52ac7fd2b\" y=\"13.377273\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "     <g id=\"text_11\">\n",
       "      <!-- 1.0 -->\n",
       "      <g transform=\"translate(15.579688 17.176491)scale(0.1 -0.1)\">\n",
       "       <use xlink:href=\"#DejaVuSans-49\"/>\n",
       "       <use x=\"63.623047\" xlink:href=\"#DejaVuSans-46\"/>\n",
       "       <use x=\"95.410156\" xlink:href=\"#DejaVuSans-48\"/>\n",
       "      </g>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "   <g id=\"line2d_23\">\n",
       "    <path clip-path=\"url(#pb3157f7082)\" d=\"M 76.528267 75.151176 \n",
       "L 84.214217 51.203025 \n",
       "L 91.900168 31.000536 \n",
       "L 99.586118 17.703519 \n",
       "L 107.272069 13.391725 \n",
       "L 114.958019 18.739548 \n",
       "L 122.64397 32.91055 \n",
       "L 130.32992 53.688287 \n",
       "L 138.01587 77.822973 \n",
       "L 145.701821 101.539771 \n",
       "L 153.387771 121.129203 \n",
       "L 161.073722 133.527346 \n",
       "L 168.759672 136.795042 \n",
       "L 176.445622 130.421197 \n",
       "L 184.131573 115.402732 \n",
       "L 191.817523 94.088633 \n",
       "L 199.503474 69.812584 \n",
       "L 207.189424 46.371528 \n",
       "L 214.875374 27.431813 \n",
       "L 222.561325 15.955749 \n",
       "L 230.247275 13.738265 \n",
       "L 237.933226 21.126202 \n",
       "L 245.619176 36.964025 \n",
       "L 253.305127 58.774592 \n",
       "L 260.991077 83.146573 \n",
       "L 268.677027 106.268018 \n",
       "L 276.362978 124.522566 \n",
       "L 284.048928 135.055078 \n",
       "L 291.734879 136.218196 \n",
       "L 299.420829 127.829996 \n",
       "L 307.106779 111.202455 \n",
       "L 314.79273 88.936237 \n",
       "L 322.47868 64.513939 \n",
       "L 330.164631 41.755379 \n",
       "L 337.850581 24.22016 \n",
       "L 345.536532 14.650914 \n",
       "L 353.222482 14.544338 \n",
       "L 360.908432 23.917105 \n",
       "L 368.594383 41.303243 \n",
       "L 376.280333 63.983437 \n",
       "L 383.966284 88.410347 \n",
       "L 391.652234 110.763427 \n",
       "L 399.338184 127.546499 \n",
       "L 407.024135 136.134571 \n",
       "L 414.710085 135.184405 \n",
       "L 422.396036 124.844614 \n",
       "L 430.081986 106.732419 \n",
       "L 437.767936 83.680692 \n",
       "L 445.453887 59.294888 \n",
       "L 453.139837 37.389121 \n",
       "L 460.825788 21.389606 \n",
       "L 468.511738 13.798786 \n",
       "L 476.197689 15.803914 \n",
       "L 483.883639 27.091374 \n",
       "L 491.569589 45.895731 \n",
       "L 499.25554 69.275847 \n",
       "L 506.94149 93.574907 \n",
       "L 514.627441 114.992364 \n",
       "L 522.313391 130.178376 \n",
       "L 529.999341 136.757744 \n",
       "L 537.685292 133.701405 \n",
       "L 545.371242 121.487396 \n",
       "L 553.057193 102.026072 \n",
       "L 560.743143 78.361323 \n",
       "L 568.429093 54.194485 \n",
       "L 576.115044 33.305424 \n",
       "L 583.800994 18.961334 \n",
       "L 591.486945 13.405735 \n",
       "L 599.172895 17.507562 \n",
       "L 606.858846 30.625262 \n",
       "L 614.544796 50.707128 \n",
       "L 622.230746 74.61222 \n",
       "L 629.916697 98.601608 \n",
       "L 637.602647 118.923181 \n",
       "L 645.288598 132.398503 \n",
       "L 652.974548 136.919933 \n",
       "L 660.660498 131.780294 \n",
       "L 668.346449 117.783458 \n",
       "L 676.032399 97.118628 \n",
       "L 683.71835 73.017934 \n",
       "L 691.4043 49.250894 \n",
       "L 699.090251 29.534842 \n",
       "L 706.776201 16.953511 \n",
       "L 714.462151 13.474706 \n",
       "L 722.148102 19.642539 \n",
       "L 729.834052 34.49232 \n",
       "L 737.520003 55.701434 \n",
       "L 745.205953 79.952625 \n",
       "L 752.891903 103.452837 \n",
       "L 760.577854 122.526467 \n",
       "L 768.263804 134.190266 \n",
       "L 775.949755 136.61993 \n",
       "L 783.635705 129.435445 \n",
       "L 791.321655 113.760514 \n",
       "L 799.007606 92.04681 \n",
       "L 806.693556 67.690507 \n",
       "L 814.379507 44.501107 \n",
       "L 822.065457 26.105593 \n",
       "L 829.751408 15.38116 \n",
       "L 837.437358 14.005181 \n",
       "\" style=\"fill:none;stroke:#1f77b4;stroke-linecap:square;stroke-width:1.5;\"/>\n",
       "   </g>\n",
       "   <g id=\"line2d_24\">\n",
       "    <path clip-path=\"url(#pb3157f7082)\" d=\"M 76.528267 13.377273 \n",
       "L 84.214217 18.208212 \n",
       "L 91.900168 31.945436 \n",
       "L 99.586118 52.440343 \n",
       "L 107.272069 76.487387 \n",
       "L 114.958019 100.325438 \n",
       "L 122.64397 120.226057 \n",
       "L 130.32992 133.076642 \n",
       "L 138.01587 136.867272 \n",
       "L 145.701821 131.005068 \n",
       "L 153.387771 116.40692 \n",
       "L 161.073722 95.356077 \n",
       "L 168.759672 71.145045 \n",
       "L 176.445622 47.560601 \n",
       "L 184.131573 28.291518 \n",
       "L 191.817523 16.35162 \n",
       "L 199.503474 13.608389 \n",
       "L 207.189424 20.49089 \n",
       "L 214.875374 35.922646 \n",
       "L 222.561325 57.490023 \n",
       "L 230.247275 81.819731 \n",
       "L 237.933226 105.10643 \n",
       "L 245.619176 123.707914 \n",
       "L 253.305127 134.71478 \n",
       "L 260.991077 136.405471 \n",
       "L 268.677027 128.515561 \n",
       "L 276.362978 112.279079 \n",
       "L 284.048928 90.235528 \n",
       "L 291.734879 65.832679 \n",
       "L 299.420829 42.887307 \n",
       "L 307.106779 24.988239 \n",
       "L 314.79273 14.935007 \n",
       "L 322.47868 14.300011 \n",
       "L 330.164631 23.182573 \n",
       "L 337.850581 40.193393 \n",
       "L 345.536532 62.671857 \n",
       "L 353.222482 87.102177 \n",
       "L 360.908432 109.663275 \n",
       "L 368.594383 126.826438 \n",
       "L 376.280333 135.907221 \n",
       "L 383.966284 135.485325 \n",
       "L 391.652234 125.626743 \n",
       "L 399.338184 107.87342 \n",
       "L 407.024135 85.002108 \n",
       "L 414.710085 60.59004 \n",
       "L 422.396036 38.455435 \n",
       "L 430.081986 22.060307 \n",
       "L 437.767936 13.968968 \n",
       "L 445.453887 15.446961 \n",
       "L 453.139837 26.263117 \n",
       "L 460.825788 44.725713 \n",
       "L 468.511738 67.947069 \n",
       "L 476.197689 92.295197 \n",
       "L 483.883639 113.96188 \n",
       "L 491.569589 129.558292 \n",
       "L 499.25554 136.645045 \n",
       "L 506.94149 134.113717 \n",
       "L 514.627441 122.360232 \n",
       "L 522.313391 103.222916 \n",
       "L 529.999341 79.694978 \n",
       "L 537.685292 55.456358 \n",
       "L 545.371242 34.298146 \n",
       "L 553.057193 19.529642 \n",
       "L 560.743143 13.46074 \n",
       "L 568.429093 17.040657 \n",
       "L 576.115044 29.709476 \n",
       "L 583.800994 49.4857 \n",
       "L 591.486945 73.276186 \n",
       "L 599.172895 97.359934 \n",
       "L 606.858846 117.970073 \n",
       "L 614.544796 131.883033 \n",
       "L 622.230746 136.922727 \n",
       "L 629.916697 132.300912 \n",
       "L 637.602647 118.740472 \n",
       "L 645.288598 98.362357 \n",
       "L 652.974548 74.353847 \n",
       "L 660.660498 50.470045 \n",
       "L 668.346449 30.446548 \n",
       "L 676.032399 17.415173 \n",
       "L 683.71835 13.414119 \n",
       "L 691.4043 19.069177 \n",
       "L 699.090251 33.495861 \n",
       "L 706.776201 54.437733 \n",
       "L 714.462151 78.619334 \n",
       "L 722.148102 102.25849 \n",
       "L 729.834052 121.657869 \n",
       "L 737.520003 133.783271 \n",
       "L 745.205953 136.7382 \n",
       "L 752.891903 130.060478 \n",
       "L 760.577854 114.794548 \n",
       "L 768.263804 93.328117 \n",
       "L 775.949755 69.018682 \n",
       "L 783.635705 45.668413 \n",
       "L 791.321655 26.929458 \n",
       "L 799.007606 15.732722 \n",
       "L 806.693556 13.829453 \n",
       "L 814.379507 21.517339 \n",
       "L 822.065457 37.59394 \n",
       "L 829.751408 59.544757 \n",
       "L 837.437358 83.936531 \n",
       "\" style=\"fill:none;stroke:#ff7f0e;stroke-linecap:square;stroke-width:1.5;\"/>\n",
       "   </g>\n",
       "   <g id=\"line2d_25\">\n",
       "    <path clip-path=\"url(#pb3157f7082)\" d=\"M 76.528267 75.151176 \n",
       "L 84.214217 65.401608 \n",
       "L 91.900168 55.896426 \n",
       "L 99.586118 46.873891 \n",
       "L 107.272069 38.560163 \n",
       "L 114.958019 31.163638 \n",
       "L 122.64397 24.869718 \n",
       "L 130.32992 19.836169 \n",
       "L 138.01587 16.189166 \n",
       "L 145.701821 14.020122 \n",
       "L 153.387771 13.383411 \n",
       "L 161.073722 14.294988 \n",
       "L 168.759672 16.732009 \n",
       "L 176.445622 20.633384 \n",
       "L 184.131573 25.901318 \n",
       "L 191.817523 32.403769 \n",
       "L 199.503474 39.977737 \n",
       "L 207.189424 48.433375 \n",
       "L 214.875374 57.558731 \n",
       "L 222.561325 67.125064 \n",
       "L 230.247275 76.892583 \n",
       "L 237.933226 86.616451 \n",
       "L 245.619176 96.052925 \n",
       "L 253.305127 104.965472 \n",
       "L 260.991077 113.13068 \n",
       "L 268.677027 120.343885 \n",
       "L 276.362978 126.424274 \n",
       "L 284.048928 131.219435 \n",
       "L 291.734879 134.609168 \n",
       "L 299.420829 136.508508 \n",
       "L 307.106779 136.869846 \n",
       "L 314.79273 135.684124 \n",
       "L 322.47868 132.981064 \n",
       "L 330.164631 128.828421 \n",
       "L 337.850581 123.330283 \n",
       "L 345.536532 116.624475 \n",
       "L 353.222482 108.879084 \n",
       "L 360.908432 100.288257 \n",
       "L 368.594383 91.067334 \n",
       "L 376.280333 81.447454 \n",
       "L 383.966284 71.669748 \n",
       "L 391.652234 61.979309 \n",
       "L 399.338184 52.61904 \n",
       "L 407.024135 43.823569 \n",
       "L 414.710085 35.813367 \n",
       "L 422.396036 28.78922 \n",
       "L 430.081986 22.927196 \n",
       "L 437.767936 18.374234 \n",
       "L 445.453887 15.244465 \n",
       "L 453.139837 13.616335 \n",
       "L 460.825788 13.530658 \n",
       "L 468.511738 14.989581 \n",
       "L 476.197689 17.956532 \n",
       "L 483.883639 22.357147 \n",
       "L 491.569589 28.08111 \n",
       "L 499.25554 34.984952 \n",
       "L 506.94149 42.89561 \n",
       "L 514.627441 51.614797 \n",
       "L 522.313391 60.923956 \n",
       "L 529.999341 70.589738 \n",
       "L 537.685292 80.369859 \n",
       "L 545.371242 90.019167 \n",
       "L 553.057193 99.295789 \n",
       "L 560.743143 107.967193 \n",
       "L 568.429093 115.816023 \n",
       "L 576.115044 122.645532 \n",
       "L 583.800994 128.284533 \n",
       "L 591.486945 132.591673 \n",
       "L 599.172895 135.458995 \n",
       "L 606.858846 136.81462 \n",
       "L 614.544796 136.624565 \n",
       "L 622.230746 134.893604 \n",
       "L 629.916697 131.665117 \n",
       "L 637.602647 127.020031 \n",
       "L 645.288598 121.074786 \n",
       "L 652.974548 113.978405 \n",
       "L 660.660498 105.908764 \n",
       "L 668.346449 97.068146 \n",
       "L 676.032399 87.678151 \n",
       "L 683.71835 77.974149 \n",
       "L 691.4043 68.199387 \n",
       "L 699.090251 58.598879 \n",
       "L 706.776201 49.413278 \n",
       "L 714.462151 40.87283 \n",
       "L 722.148102 33.191617 \n",
       "L 729.834052 26.562173 \n",
       "L 737.520003 21.150677 \n",
       "L 745.205953 17.09278 \n",
       "L 752.891903 14.490187 \n",
       "L 760.577854 13.408146 \n",
       "L 768.263804 13.873777 \n",
       "L 775.949755 15.875407 \n",
       "L 783.635705 19.362861 \n",
       "L 791.321655 24.248725 \n",
       "L 799.007606 30.410523 \n",
       "L 806.693556 37.693811 \n",
       "L 814.379507 45.916014 \n",
       "L 822.065457 54.871034 \n",
       "L 829.751408 64.334405 \n",
       "L 837.437358 74.068912 \n",
       "\" style=\"fill:none;stroke:#2ca02c;stroke-linecap:square;stroke-width:1.5;\"/>\n",
       "   </g>\n",
       "   <g id=\"line2d_26\">\n",
       "    <path clip-path=\"url(#pb3157f7082)\" d=\"M 76.528267 13.377273 \n",
       "L 84.214217 14.151497 \n",
       "L 91.900168 16.454757 \n",
       "L 99.586118 20.22932 \n",
       "L 107.272069 25.380575 \n",
       "L 114.958019 31.779392 \n",
       "L 122.64397 39.265386 \n",
       "L 130.32992 47.6509 \n",
       "L 138.01587 56.725748 \n",
       "L 145.701821 66.262453 \n",
       "L 153.387771 76.021966 \n",
       "L 161.073722 85.759651 \n",
       "L 168.759672 95.231421 \n",
       "L 176.445622 104.199853 \n",
       "L 184.131573 112.440141 \n",
       "L 191.817523 119.745731 \n",
       "L 199.503474 125.933499 \n",
       "L 207.189424 130.848343 \n",
       "L 214.875374 134.367061 \n",
       "L 222.561325 136.401454 \n",
       "L 230.247275 136.900528 \n",
       "L 237.933226 135.851774 \n",
       "L 245.619176 133.281479 \n",
       "L 253.305127 129.254069 \n",
       "L 260.991077 123.870501 \n",
       "L 268.677027 117.265716 \n",
       "L 276.362978 109.605272 \n",
       "L 284.048928 101.081193 \n",
       "L 291.734879 91.907144 \n",
       "L 299.420829 82.313083 \n",
       "L 307.106779 72.5395 \n",
       "L 314.79273 62.831382 \n",
       "L 322.47868 53.432076 \n",
       "L 330.164631 44.577188 \n",
       "L 337.850581 36.488678 \n",
       "L 345.536532 29.369295 \n",
       "L 353.222482 23.397495 \n",
       "L 360.908432 18.722972 \n",
       "L 368.594383 15.462893 \n",
       "L 376.280333 13.698985 \n",
       "L 383.966284 13.475454 \n",
       "L 391.652234 14.797907 \n",
       "L 399.338184 17.633196 \n",
       "L 407.024135 21.91025 \n",
       "L 414.710085 27.521856 \n",
       "L 422.396036 34.327359 \n",
       "L 430.081986 42.156162 \n",
       "L 437.767936 50.812029 \n",
       "L 445.453887 60.077989 \n",
       "L 453.139837 69.721779 \n",
       "L 460.825788 79.501664 \n",
       "L 468.511738 89.172498 \n",
       "L 476.197689 98.491869 \n",
       "L 483.883639 107.226173 \n",
       "L 491.569589 115.156479 \n",
       "L 499.25554 122.083996 \n",
       "L 506.94149 127.835081 \n",
       "L 514.627441 132.265572 \n",
       "L 522.313391 135.264416 \n",
       "L 529.999341 136.75644 \n",
       "L 537.685292 136.704248 \n",
       "L 545.371242 135.109145 \n",
       "L 553.057193 132.011119 \n",
       "L 560.743143 127.487819 \n",
       "L 568.429093 121.652634 \n",
       "L 576.115044 114.651826 \n",
       "L 583.800994 106.660885 \n",
       "L 591.486945 97.880109 \n",
       "L 599.172895 88.529603 \n",
       "L 606.858846 78.843749 \n",
       "L 614.544796 69.065335 \n",
       "L 622.230746 59.439471 \n",
       "L 629.916697 50.207442 \n",
       "L 637.602647 41.600661 \n",
       "L 645.288598 33.834868 \n",
       "L 652.974548 27.104725 \n",
       "L 660.660498 21.578928 \n",
       "L 668.346449 17.39599 \n",
       "L 676.032399 14.660763 \n",
       "L 683.71835 13.441811 \n",
       "L 691.4043 13.769683 \n",
       "L 699.090251 15.636165 \n",
       "L 706.776201 18.994469 \n",
       "L 714.462151 23.760417 \n",
       "L 722.148102 29.814542 \n",
       "L 729.834052 37.005091 \n",
       "L 737.520003 45.151819 \n",
       "L 745.205953 54.050523 \n",
       "L 752.891903 63.478144 \n",
       "L 760.577854 73.198364 \n",
       "L 768.263804 82.967534 \n",
       "L 775.949755 92.540776 \n",
       "L 783.635705 101.678126 \n",
       "L 791.321655 110.150541 \n",
       "L 799.007606 117.745651 \n",
       "L 806.693556 124.273073 \n",
       "L 814.379507 129.56919 \n",
       "L 822.065457 133.501251 \n",
       "L 829.751408 135.970684 \n",
       "L 837.437358 136.915599 \n",
       "\" style=\"fill:none;stroke:#d62728;stroke-linecap:square;stroke-width:1.5;\"/>\n",
       "   </g>\n",
       "   <g id=\"line2d_27\">\n",
       "    <path clip-path=\"url(#pb3157f7082)\" d=\"M 76.528267 75.151176 \n",
       "L 84.214217 71.256092 \n",
       "L 91.900168 67.37651 \n",
       "L 99.586118 63.527868 \n",
       "L 107.272069 59.725485 \n",
       "L 114.958019 55.984491 \n",
       "L 122.64397 52.319777 \n",
       "L 130.32992 48.745925 \n",
       "L 138.01587 45.277161 \n",
       "L 145.701821 41.927285 \n",
       "L 153.387771 38.709634 \n",
       "L 161.073722 35.637014 \n",
       "L 168.759672 32.721648 \n",
       "L 176.445622 29.97514 \n",
       "L 184.131573 27.408421 \n",
       "L 191.817523 25.031708 \n",
       "L 199.503474 22.854458 \n",
       "L 207.189424 20.885336 \n",
       "L 214.875374 19.132176 \n",
       "L 222.561325 17.601961 \n",
       "L 230.247275 16.300775 \n",
       "L 237.933226 15.233802 \n",
       "L 245.619176 14.405283 \n",
       "L 253.305127 13.818518 \n",
       "L 260.991077 13.47584 \n",
       "L 268.677027 13.378617 \n",
       "L 276.362978 13.527234 \n",
       "L 284.048928 13.921095 \n",
       "L 291.734879 14.558639 \n",
       "L 299.420829 15.437329 \n",
       "L 307.106779 16.553659 \n",
       "L 314.79273 17.903198 \n",
       "L 322.47868 19.480568 \n",
       "L 330.164631 21.279492 \n",
       "L 337.850581 23.292812 \n",
       "L 345.536532 25.512516 \n",
       "L 353.222482 27.929772 \n",
       "L 360.908432 30.534953 \n",
       "L 368.594383 33.3177 \n",
       "L 376.280333 36.266929 \n",
       "L 383.966284 39.370912 \n",
       "L 391.652234 42.617287 \n",
       "L 399.338184 45.993143 \n",
       "L 407.024135 49.485039 \n",
       "L 414.710085 53.07908 \n",
       "L 422.396036 56.760963 \n",
       "L 430.081986 60.516033 \n",
       "L 437.767936 64.329348 \n",
       "L 445.453887 68.185731 \n",
       "L 453.139837 72.069835 \n",
       "L 460.825788 75.966202 \n",
       "L 468.511738 79.859325 \n",
       "L 476.197689 83.733712 \n",
       "L 483.883639 87.573941 \n",
       "L 491.569589 91.364732 \n",
       "L 499.25554 95.090996 \n",
       "L 506.94149 98.737905 \n",
       "L 514.627441 102.290943 \n",
       "L 522.313391 105.735973 \n",
       "L 529.999341 109.059285 \n",
       "L 537.685292 112.247649 \n",
       "L 545.371242 115.288376 \n",
       "L 553.057193 118.16937 \n",
       "L 560.743143 120.879164 \n",
       "L 568.429093 123.406969 \n",
       "L 576.115044 125.74273 \n",
       "L 583.800994 127.877148 \n",
       "L 591.486945 129.801728 \n",
       "L 599.172895 131.508815 \n",
       "L 606.858846 132.991609 \n",
       "L 614.544796 134.244218 \n",
       "L 622.230746 135.261647 \n",
       "L 629.916697 136.039855 \n",
       "L 637.602647 136.575738 \n",
       "L 645.288598 136.867166 \n",
       "L 652.974548 136.912981 \n",
       "L 660.660498 136.713 \n",
       "L 668.346449 136.268018 \n",
       "L 676.032399 135.579806 \n",
       "L 683.71835 134.651103 \n",
       "L 691.4043 133.485606 \n",
       "L 699.090251 132.087952 \n",
       "L 706.776201 130.463706 \n",
       "L 714.462151 128.619327 \n",
       "L 722.148102 126.562158 \n",
       "L 729.834052 124.300387 \n",
       "L 737.520003 121.843012 \n",
       "L 745.205953 119.199817 \n",
       "L 752.891903 116.381322 \n",
       "L 760.577854 113.398738 \n",
       "L 768.263804 110.26394 \n",
       "L 775.949755 106.989398 \n",
       "L 783.635705 103.588153 \n",
       "L 791.321655 100.073733 \n",
       "L 799.007606 96.460128 \n",
       "L 806.693556 92.761719 \n",
       "L 814.379507 88.993224 \n",
       "L 822.065457 85.169642 \n",
       "L 829.751408 81.306188 \n",
       "L 837.437358 77.418239 \n",
       "\" style=\"fill:none;stroke:#9467bd;stroke-linecap:square;stroke-width:1.5;\"/>\n",
       "   </g>\n",
       "   <g id=\"line2d_28\">\n",
       "    <path clip-path=\"url(#pb3157f7082)\" d=\"M 76.528267 13.377273 \n",
       "L 84.214217 13.500197 \n",
       "L 91.900168 13.868471 \n",
       "L 99.586118 14.480643 \n",
       "L 107.272069 15.334262 \n",
       "L 114.958019 16.425941 \n",
       "L 122.64397 17.751329 \n",
       "L 130.32992 19.305157 \n",
       "L 138.01587 21.081238 \n",
       "L 145.701821 23.072503 \n",
       "L 153.387771 25.271028 \n",
       "L 161.073722 27.668062 \n",
       "L 168.759672 30.254071 \n",
       "L 176.445622 33.018757 \n",
       "L 184.131573 35.951119 \n",
       "L 191.817523 39.039487 \n",
       "L 199.503474 42.271571 \n",
       "L 207.189424 45.634509 \n",
       "L 214.875374 49.114916 \n",
       "L 222.561325 52.69894 \n",
       "L 230.247275 56.372317 \n",
       "L 237.933226 60.120432 \n",
       "L 245.619176 63.928364 \n",
       "L 253.305127 67.78096 \n",
       "L 260.991077 71.662888 \n",
       "L 268.677027 75.558698 \n",
       "L 276.362978 79.452887 \n",
       "L 284.048928 83.329955 \n",
       "L 291.734879 87.174475 \n",
       "L 299.420829 90.971144 \n",
       "L 307.106779 94.704854 \n",
       "L 314.79273 98.360746 \n",
       "L 322.47868 101.924268 \n",
       "L 330.164631 105.381241 \n",
       "L 337.850581 108.717907 \n",
       "L 345.536532 111.920981 \n",
       "L 353.222482 114.977725 \n",
       "L 360.908432 117.875969 \n",
       "L 368.594383 120.604177 \n",
       "L 376.280333 123.151496 \n",
       "L 383.966284 125.507781 \n",
       "L 391.652234 127.663665 \n",
       "L 399.338184 129.610558 \n",
       "L 407.024135 131.340717 \n",
       "L 414.710085 132.847256 \n",
       "L 422.396036 134.124181 \n",
       "L 430.081986 135.166404 \n",
       "L 437.767936 135.969786 \n",
       "L 445.453887 136.531123 \n",
       "L 453.139837 136.848181 \n",
       "L 460.825788 136.919704 \n",
       "L 468.511738 136.745402 \n",
       "L 476.197689 136.325969 \n",
       "L 483.883639 135.663078 \n",
       "L 491.569589 134.759361 \n",
       "L 499.25554 133.61842 \n",
       "L 506.94149 132.244798 \n",
       "L 514.627441 130.643951 \n",
       "L 522.313391 128.822261 \n",
       "L 529.999341 126.78697 \n",
       "L 537.685292 124.546187 \n",
       "L 545.371242 122.10882 \n",
       "L 553.057193 119.484573 \n",
       "L 560.743143 116.683892 \n",
       "L 568.429093 113.717921 \n",
       "L 576.115044 110.598462 \n",
       "L 583.800994 107.337934 \n",
       "L 591.486945 103.949308 \n",
       "L 599.172895 100.446075 \n",
       "L 606.858846 96.842174 \n",
       "L 614.544796 93.151947 \n",
       "L 622.230746 89.390082 \n",
       "L 629.916697 85.57155 \n",
       "L 637.602647 81.711548 \n",
       "L 645.288598 77.825437 \n",
       "L 652.974548 73.928683 \n",
       "L 660.660498 70.036794 \n",
       "L 668.346449 66.165259 \n",
       "L 676.032399 62.329486 \n",
       "L 683.71835 58.544741 \n",
       "L 691.4043 54.826084 \n",
       "L 699.090251 51.188315 \n",
       "L 706.776201 47.645915 \n",
       "L 714.462151 44.212978 \n",
       "L 722.148102 40.903167 \n",
       "L 729.834052 37.729652 \n",
       "L 737.520003 34.705071 \n",
       "L 745.205953 31.841453 \n",
       "L 752.891903 29.150193 \n",
       "L 760.577854 26.64201 \n",
       "L 768.263804 24.326879 \n",
       "L 775.949755 22.21402 \n",
       "L 783.635705 20.311833 \n",
       "L 791.321655 18.627895 \n",
       "L 799.007606 17.168905 \n",
       "L 806.693556 15.940671 \n",
       "L 814.379507 14.948078 \n",
       "L 822.065457 14.195081 \n",
       "L 829.751408 13.684673 \n",
       "L 837.437358 13.418887 \n",
       "\" style=\"fill:none;stroke:#8c564b;stroke-linecap:square;stroke-width:1.5;\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_3\">\n",
       "    <path d=\"M 38.482813 143.1 \n",
       "L 38.482813 7.2 \n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:square;stroke-linejoin:miter;stroke-width:0.8;\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_4\">\n",
       "    <path d=\"M 875.482813 143.1 \n",
       "L 875.482813 7.2 \n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:square;stroke-linejoin:miter;stroke-width:0.8;\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_5\">\n",
       "    <path d=\"M 38.482813 143.1 \n",
       "L 875.482813 143.1 \n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:square;stroke-linejoin:miter;stroke-width:0.8;\"/>\n",
       "   </g>\n",
       "   <g id=\"patch_6\">\n",
       "    <path d=\"M 38.482813 7.2 \n",
       "L 875.482813 7.2 \n",
       "\" style=\"fill:none;stroke:#000000;stroke-linecap:square;stroke-linejoin:miter;stroke-width:0.8;\"/>\n",
       "   </g>\n",
       "   <g id=\"legend_1\">\n",
       "    <g id=\"patch_7\">\n",
       "     <path d=\"M 45.482813 138.1 \n",
       "L 105.890625 138.1 \n",
       "Q 107.890625 138.1 107.890625 136.1 \n",
       "L 107.890625 49.03125 \n",
       "Q 107.890625 47.03125 105.890625 47.03125 \n",
       "L 45.482813 47.03125 \n",
       "Q 43.482813 47.03125 43.482813 49.03125 \n",
       "L 43.482813 136.1 \n",
       "Q 43.482813 138.1 45.482813 138.1 \n",
       "z\n",
       "\" style=\"fill:#ffffff;opacity:0.8;stroke:#cccccc;stroke-linejoin:miter;\"/>\n",
       "    </g>\n",
       "    <g id=\"line2d_29\">\n",
       "     <path d=\"M 47.482813 55.129688 \n",
       "L 67.482813 55.129688 \n",
       "\" style=\"fill:none;stroke:#1f77b4;stroke-linecap:square;stroke-width:1.5;\"/>\n",
       "    </g>\n",
       "    <g id=\"line2d_30\"/>\n",
       "    <g id=\"text_12\">\n",
       "     <!-- dim 2 -->\n",
       "     <defs>\n",
       "      <path d=\"M 45.40625 46.390625 \n",
       "L 45.40625 75.984375 \n",
       "L 54.390625 75.984375 \n",
       "L 54.390625 0 \n",
       "L 45.40625 0 \n",
       "L 45.40625 8.203125 \n",
       "Q 42.578125 3.328125 38.25 0.953125 \n",
       "Q 33.9375 -1.421875 27.875 -1.421875 \n",
       "Q 17.96875 -1.421875 11.734375 6.484375 \n",
       "Q 5.515625 14.40625 5.515625 27.296875 \n",
       "Q 5.515625 40.1875 11.734375 48.09375 \n",
       "Q 17.96875 56 27.875 56 \n",
       "Q 33.9375 56 38.25 53.625 \n",
       "Q 42.578125 51.265625 45.40625 46.390625 \n",
       "z\n",
       "M 14.796875 27.296875 \n",
       "Q 14.796875 17.390625 18.875 11.75 \n",
       "Q 22.953125 6.109375 30.078125 6.109375 \n",
       "Q 37.203125 6.109375 41.296875 11.75 \n",
       "Q 45.40625 17.390625 45.40625 27.296875 \n",
       "Q 45.40625 37.203125 41.296875 42.84375 \n",
       "Q 37.203125 48.484375 30.078125 48.484375 \n",
       "Q 22.953125 48.484375 18.875 42.84375 \n",
       "Q 14.796875 37.203125 14.796875 27.296875 \n",
       "z\n",
       "\" id=\"DejaVuSans-100\"/>\n",
       "      <path d=\"M 9.421875 54.6875 \n",
       "L 18.40625 54.6875 \n",
       "L 18.40625 0 \n",
       "L 9.421875 0 \n",
       "z\n",
       "M 9.421875 75.984375 \n",
       "L 18.40625 75.984375 \n",
       "L 18.40625 64.59375 \n",
       "L 9.421875 64.59375 \n",
       "z\n",
       "\" id=\"DejaVuSans-105\"/>\n",
       "      <path d=\"M 52 44.1875 \n",
       "Q 55.375 50.25 60.0625 53.125 \n",
       "Q 64.75 56 71.09375 56 \n",
       "Q 79.640625 56 84.28125 50.015625 \n",
       "Q 88.921875 44.046875 88.921875 33.015625 \n",
       "L 88.921875 0 \n",
       "L 79.890625 0 \n",
       "L 79.890625 32.71875 \n",
       "Q 79.890625 40.578125 77.09375 44.375 \n",
       "Q 74.3125 48.1875 68.609375 48.1875 \n",
       "Q 61.625 48.1875 57.5625 43.546875 \n",
       "Q 53.515625 38.921875 53.515625 30.90625 \n",
       "L 53.515625 0 \n",
       "L 44.484375 0 \n",
       "L 44.484375 32.71875 \n",
       "Q 44.484375 40.625 41.703125 44.40625 \n",
       "Q 38.921875 48.1875 33.109375 48.1875 \n",
       "Q 26.21875 48.1875 22.15625 43.53125 \n",
       "Q 18.109375 38.875 18.109375 30.90625 \n",
       "L 18.109375 0 \n",
       "L 9.078125 0 \n",
       "L 9.078125 54.6875 \n",
       "L 18.109375 54.6875 \n",
       "L 18.109375 46.1875 \n",
       "Q 21.1875 51.21875 25.484375 53.609375 \n",
       "Q 29.78125 56 35.6875 56 \n",
       "Q 41.65625 56 45.828125 52.96875 \n",
       "Q 50 49.953125 52 44.1875 \n",
       "z\n",
       "\" id=\"DejaVuSans-109\"/>\n",
       "      <path id=\"DejaVuSans-32\"/>\n",
       "     </defs>\n",
       "     <g transform=\"translate(75.482813 58.629688)scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-100\"/>\n",
       "      <use x=\"63.476562\" xlink:href=\"#DejaVuSans-105\"/>\n",
       "      <use x=\"91.259766\" xlink:href=\"#DejaVuSans-109\"/>\n",
       "      <use x=\"188.671875\" xlink:href=\"#DejaVuSans-32\"/>\n",
       "      <use x=\"220.458984\" xlink:href=\"#DejaVuSans-50\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"line2d_31\">\n",
       "     <path d=\"M 47.482813 69.807813 \n",
       "L 67.482813 69.807813 \n",
       "\" style=\"fill:none;stroke:#ff7f0e;stroke-linecap:square;stroke-width:1.5;\"/>\n",
       "    </g>\n",
       "    <g id=\"line2d_32\"/>\n",
       "    <g id=\"text_13\">\n",
       "     <!-- dim 3 -->\n",
       "     <defs>\n",
       "      <path d=\"M 40.578125 39.3125 \n",
       "Q 47.65625 37.796875 51.625 33 \n",
       "Q 55.609375 28.21875 55.609375 21.1875 \n",
       "Q 55.609375 10.40625 48.1875 4.484375 \n",
       "Q 40.765625 -1.421875 27.09375 -1.421875 \n",
       "Q 22.515625 -1.421875 17.65625 -0.515625 \n",
       "Q 12.796875 0.390625 7.625 2.203125 \n",
       "L 7.625 11.71875 \n",
       "Q 11.71875 9.328125 16.59375 8.109375 \n",
       "Q 21.484375 6.890625 26.8125 6.890625 \n",
       "Q 36.078125 6.890625 40.9375 10.546875 \n",
       "Q 45.796875 14.203125 45.796875 21.1875 \n",
       "Q 45.796875 27.640625 41.28125 31.265625 \n",
       "Q 36.765625 34.90625 28.71875 34.90625 \n",
       "L 20.21875 34.90625 \n",
       "L 20.21875 43.015625 \n",
       "L 29.109375 43.015625 \n",
       "Q 36.375 43.015625 40.234375 45.921875 \n",
       "Q 44.09375 48.828125 44.09375 54.296875 \n",
       "Q 44.09375 59.90625 40.109375 62.90625 \n",
       "Q 36.140625 65.921875 28.71875 65.921875 \n",
       "Q 24.65625 65.921875 20.015625 65.03125 \n",
       "Q 15.375 64.15625 9.8125 62.3125 \n",
       "L 9.8125 71.09375 \n",
       "Q 15.4375 72.65625 20.34375 73.4375 \n",
       "Q 25.25 74.21875 29.59375 74.21875 \n",
       "Q 40.828125 74.21875 47.359375 69.109375 \n",
       "Q 53.90625 64.015625 53.90625 55.328125 \n",
       "Q 53.90625 49.265625 50.4375 45.09375 \n",
       "Q 46.96875 40.921875 40.578125 39.3125 \n",
       "z\n",
       "\" id=\"DejaVuSans-51\"/>\n",
       "     </defs>\n",
       "     <g transform=\"translate(75.482813 73.307813)scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-100\"/>\n",
       "      <use x=\"63.476562\" xlink:href=\"#DejaVuSans-105\"/>\n",
       "      <use x=\"91.259766\" xlink:href=\"#DejaVuSans-109\"/>\n",
       "      <use x=\"188.671875\" xlink:href=\"#DejaVuSans-32\"/>\n",
       "      <use x=\"220.458984\" xlink:href=\"#DejaVuSans-51\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"line2d_33\">\n",
       "     <path d=\"M 47.482813 84.485938 \n",
       "L 67.482813 84.485938 \n",
       "\" style=\"fill:none;stroke:#2ca02c;stroke-linecap:square;stroke-width:1.5;\"/>\n",
       "    </g>\n",
       "    <g id=\"line2d_34\"/>\n",
       "    <g id=\"text_14\">\n",
       "     <!-- dim 4 -->\n",
       "     <g transform=\"translate(75.482813 87.985938)scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-100\"/>\n",
       "      <use x=\"63.476562\" xlink:href=\"#DejaVuSans-105\"/>\n",
       "      <use x=\"91.259766\" xlink:href=\"#DejaVuSans-109\"/>\n",
       "      <use x=\"188.671875\" xlink:href=\"#DejaVuSans-32\"/>\n",
       "      <use x=\"220.458984\" xlink:href=\"#DejaVuSans-52\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"line2d_35\">\n",
       "     <path d=\"M 47.482813 99.164063 \n",
       "L 67.482813 99.164063 \n",
       "\" style=\"fill:none;stroke:#d62728;stroke-linecap:square;stroke-width:1.5;\"/>\n",
       "    </g>\n",
       "    <g id=\"line2d_36\"/>\n",
       "    <g id=\"text_15\">\n",
       "     <!-- dim 5 -->\n",
       "     <g transform=\"translate(75.482813 102.664063)scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-100\"/>\n",
       "      <use x=\"63.476562\" xlink:href=\"#DejaVuSans-105\"/>\n",
       "      <use x=\"91.259766\" xlink:href=\"#DejaVuSans-109\"/>\n",
       "      <use x=\"188.671875\" xlink:href=\"#DejaVuSans-32\"/>\n",
       "      <use x=\"220.458984\" xlink:href=\"#DejaVuSans-53\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"line2d_37\">\n",
       "     <path d=\"M 47.482813 113.842188 \n",
       "L 67.482813 113.842188 \n",
       "\" style=\"fill:none;stroke:#9467bd;stroke-linecap:square;stroke-width:1.5;\"/>\n",
       "    </g>\n",
       "    <g id=\"line2d_38\"/>\n",
       "    <g id=\"text_16\">\n",
       "     <!-- dim 6 -->\n",
       "     <g transform=\"translate(75.482813 117.342188)scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-100\"/>\n",
       "      <use x=\"63.476562\" xlink:href=\"#DejaVuSans-105\"/>\n",
       "      <use x=\"91.259766\" xlink:href=\"#DejaVuSans-109\"/>\n",
       "      <use x=\"188.671875\" xlink:href=\"#DejaVuSans-32\"/>\n",
       "      <use x=\"220.458984\" xlink:href=\"#DejaVuSans-54\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "    <g id=\"line2d_39\">\n",
       "     <path d=\"M 47.482813 128.520313 \n",
       "L 67.482813 128.520313 \n",
       "\" style=\"fill:none;stroke:#8c564b;stroke-linecap:square;stroke-width:1.5;\"/>\n",
       "    </g>\n",
       "    <g id=\"line2d_40\"/>\n",
       "    <g id=\"text_17\">\n",
       "     <!-- dim 7 -->\n",
       "     <defs>\n",
       "      <path d=\"M 8.203125 72.90625 \n",
       "L 55.078125 72.90625 \n",
       "L 55.078125 68.703125 \n",
       "L 28.609375 0 \n",
       "L 18.3125 0 \n",
       "L 43.21875 64.59375 \n",
       "L 8.203125 64.59375 \n",
       "z\n",
       "\" id=\"DejaVuSans-55\"/>\n",
       "     </defs>\n",
       "     <g transform=\"translate(75.482813 132.020313)scale(0.1 -0.1)\">\n",
       "      <use xlink:href=\"#DejaVuSans-100\"/>\n",
       "      <use x=\"63.476562\" xlink:href=\"#DejaVuSans-105\"/>\n",
       "      <use x=\"91.259766\" xlink:href=\"#DejaVuSans-109\"/>\n",
       "      <use x=\"188.671875\" xlink:href=\"#DejaVuSans-32\"/>\n",
       "      <use x=\"220.458984\" xlink:href=\"#DejaVuSans-55\"/>\n",
       "     </g>\n",
       "    </g>\n",
       "   </g>\n",
       "  </g>\n",
       " </g>\n",
       " <defs>\n",
       "  <clipPath id=\"pb3157f7082\">\n",
       "   <rect height=\"135.9\" width=\"837\" x=\"38.482813\" y=\"7.2\"/>\n",
       "  </clipPath>\n",
       " </defs>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<Figure size 1080x180 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "pe = PositionalEncoding(20, 0)\n",
    "Y = pe(torch.zeros((1, 100, 20))).numpy()\n",
    "seq.plot(np.arange(100), Y[0, :, 2:8].T, figsize=(15, 2.5),\n",
    "         legend=[\"dim %d\" % p for p in [2, 3, 4, 5, 6, 7]])  # sin、cos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_knvpqhj",
    "id": "561622A8895741218D8E531708111761",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "# 编码器\n",
    "\n",
    "我们已经有了组成Transformer的各个模块，现在我们可以开始搭建了！编码器包含一个多头注意力层，一个position-wise FFN，和两个 Add and Norm层。对于attention模型以及FFN模型，我们的输出维度都是与embedding维度一致的，这也是由于残差连接天生的特性导致的，因为我们要将前一层的输出与原始输入相加并归一化。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:27.569589Z",
     "start_time": "2020-02-18T04:39:27.556683Z"
    },
    "graffitiCellId": "id_x22v188",
    "id": "D783201E79D043439F3E7C10D0F5003C",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class EncoderBlock(nn.Module):\n",
    "    def __init__(self, embedding_size, ffn_hidden_size, num_heads, dropout, **kwargs):\n",
    "        super(EncoderBlock, self).__init__(**kwargs)\n",
    "        self.attention = MultiHeadAttention(embedding_size, embedding_size, num_heads, dropout)\n",
    "        self.addnorm_1 = AddNorm(embedding_size, dropout)\n",
    "        self.ffn = PositionWiseFFN(embedding_size, ffn_hidden_size, embedding_size)\n",
    "        self.addnorm_2 = AddNorm(embedding_size, dropout)\n",
    "\n",
    "    def forward(self, X, valid_length):\n",
    "        Y = self.addnorm_1(X, self.attention(X, X, X, valid_length))\n",
    "        return self.addnorm_2(Y, self.ffn(Y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:44:27.799333Z",
     "start_time": "2020-02-18T04:44:27.774406Z"
    },
    "graffitiCellId": "id_j3zhyr4",
    "id": "8071DC6CEC654D2A9061D83C13505F36",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([2, 100, 24])"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# # dim==embedding_size, batch_size==valid_length.shape[0]\n",
    "# # batch_size = 2, seq_len = 100, dim = 24\n",
    "# # embedding_size = 24, ffn_hidden_size = 48, num_heads = 8, dropout = 0.5\n",
    "\n",
    "# valid_length = torch.FloatTensor([2, 3])\n",
    "# X = torch.ones((2, 100, 24))\n",
    "# encoder_blk = EncoderBlock(24, 48, 8, 0.5)\n",
    "# encoder_blk(X, valid_length).shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:48:15.925686Z",
     "start_time": "2020-02-18T04:48:15.900195Z"
    },
    "graffitiCellId": "id_j3zhyr4",
    "id": "8071DC6CEC654D2A9061D83C13505F36",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([4, 111, 16])"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# # dim==embedding_size, batch_size==valid_length.shape[0]\n",
    "# # batch_size = 4, seq_len = 111, dim = 16\n",
    "# # embedding_size = 16, ffn_hidden_size = 47, num_heads = 8, dropout = 0.5\n",
    "\n",
    "#  query = transpose_qkv(self.W_q(query), self.num_heads)  # (2,4,9),3 -> (6,4,9)\n",
    "valid_length = torch.FloatTensor([2, 3, 4, 5])\n",
    "X = torch.ones((4, 111, 16))  # \n",
    "encoder_blk = EncoderBlock(16, 47, 8, 0.5)  # 16能整除8，dim能整除num_heads\n",
    "encoder_blk(X, valid_length).shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Fig. 10.3.1 The Transformer architecture.](https://cdn.kesci.com/upload/image/q5kpbj2cj5.png?imageView2/0/w/960/h/960)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_nfzu463",
    "id": "979499A856FB4FB5AA491F56C6D901C1",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "现在我们来实现整个Transformer 编码器模型，整个编码器由n个刚刚定义的Encoder Block堆叠而成，因为残差连接的缘故，中间状态的维度始终与嵌入向量的维度d一致；同时注意到我们把嵌入向量乘以 $\\sqrt{d}$ 以防止其值过小。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:39:30.507302Z",
     "start_time": "2020-02-18T04:39:30.491946Z"
    },
    "graffitiCellId": "id_zbq9tjf",
    "id": "22138781EF594DAD80EB068E33A0B292",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class TransformerEncoder(d2l.Encoder):\n",
    "    #                      200            24             48              8           2         0.5\n",
    "    def __init__(self, vocab_size, embedding_size, ffn_hidden_size, num_heads, num_layers, dropout, **kwargs):\n",
    "        super(TransformerEncoder, self).__init__(**kwargs)\n",
    "        self.embedding_size = embedding_size\n",
    "        self.embed = nn.Embedding(vocab_size, embedding_size)\n",
    "        self.pos_encoding = PositionalEncoding(embedding_size, dropout)\n",
    "        self.blks = nn.ModuleList()\n",
    "        for i in range(num_layers):  # EncoderBlock前后维度不变\n",
    "            #                                    24              48             8         0.5\n",
    "            self.blks.append(EncoderBlock(embedding_size, ffn_hidden_size, num_heads, dropout))  \n",
    "\n",
    "    def forward(self, X, valid_length, *args):  # (2,100), (2)\n",
    "        X = self.pos_encoding(self.embed(X) * math.sqrt(self.embedding_size))\n",
    "        for blk in self.blks:\n",
    "            X = blk(X, valid_length)\n",
    "        return X"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## EncoderBlock"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:46:34.811169Z",
     "start_time": "2020-02-18T04:46:34.782560Z"
    },
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([4, 111, 16])"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# # dim==embedding_size, batch_size==valid_length.shape[0]\n",
    "# # batch_size = 4, seq_len = 111, dim = 16\n",
    "# # embedding_size = 16, ffn_hidden_size = 47, num_heads = 8, dropout = 0.5\n",
    "\n",
    "#  query = transpose_qkv(self.W_q(query), self.num_heads)  # (2,4,9),3 -> (6,4,9)\n",
    "valid_length = torch.FloatTensor([2, 3, 4, 5])\n",
    "\n",
    "X = torch.ones((4, 111, 16))  # \n",
    "encoder_blk = EncoderBlock(16, 47, 8, 0.5)  # 16能整除8，dim能整除num_heads\n",
    "encoder_blk(X, valid_length).shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## TransformerEncoder"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:54:56.807659Z",
     "start_time": "2020-02-18T04:54:56.760589Z"
    },
    "graffitiCellId": "id_vx2hsaf",
    "id": "2D50EE7D0CC24C3C9562EBAA5C51FF08",
    "jupyter": {},
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([4, 111, 16])"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# # test encoder\n",
    "# # batch_size = 4, seq_len = 111\n",
    "# # vocab_size = 200, \n",
    "# # embedding_size = 16, ffn_hidden_size = 47, num_heads = 8, num_layers, dropout\n",
    "# # valid_length = torch.FloatTensor([2, 3, 4, 5])\n",
    "XX = torch.ones((4, 111))  # valid_length没变，所以需要=4\n",
    "encoder = TransformerEncoder(200, 16, 47, 8, 2, 0.5)\n",
    "encoder(XX.long(), valid_length).shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_9iqru6k",
    "id": "44C56AEAA91F4798913D0445EC5970C4",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "# 解码器\n",
    "Transformer 模型的解码器与编码器结构类似，然而，除了之前介绍的几个模块之外，编码器部分有另一个子模块。该模块也是多头注意力层，接受编码器的输出作为key和value，decoder的状态作为query。与编码器部分相类似，解码器同样是使用了add and norm机制，用残差和层归一化将各个子层的输出相连。\n",
    "\n",
    "仔细来讲，在第t个时间步，当前输入$x_t$是query，那么self attention接受了第t步以及前t-1步的所有输入$x_1,\\ldots, x_{t-1}$。在训练时，由于第t位置的输入可以观测到全部的序列，这与预测阶段的情形项矛盾，所以我们要通过将第t个时间步所对应的可观测长度设置为t，以消除不需要看到的未来的信息。\n",
    "\n",
    "\n",
    "![Image Name](https://cdn.kesci.com/upload/image/q5kpefhcyg.png?imageView2/0/w/800/h/800)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T04:53:21.795764Z",
     "start_time": "2020-02-18T04:53:21.774289Z"
    },
    "graffitiCellId": "id_ao2mjn9",
    "id": "B5D8DE77B835470B8ABB16FD9093CBB2",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class DecoderBlock(nn.Module):\n",
    "    def __init__(self, embedding_size, ffn_hidden_size, num_heads,dropout,i,**kwargs):\n",
    "        super(DecoderBlock, self).__init__(**kwargs)\n",
    "        self.i = i\n",
    "        self.attention_1 = MultiHeadAttention(embedding_size, embedding_size, num_heads, dropout)\n",
    "        self.addnorm_1 = AddNorm(embedding_size, dropout)\n",
    "        self.attention_2 = MultiHeadAttention(embedding_size, embedding_size, num_heads, dropout)\n",
    "        self.addnorm_2 = AddNorm(embedding_size, dropout)\n",
    "        self.ffn = PositionWiseFFN(embedding_size, ffn_hidden_size, embedding_size)\n",
    "        self.addnorm_3 = AddNorm(embedding_size, dropout)\n",
    "    \n",
    "    def forward(self, X, state):\n",
    "        enc_outputs, enc_valid_length = state[0], state[1]\n",
    "        \n",
    "        # state[2][self.i] stores all the previous t-1 query state of layer-i\n",
    "        # len(state[2]) = num_layers\n",
    "        \n",
    "        # If training:\n",
    "        #     state[2] is useless.\n",
    "        # If predicting:\n",
    "        #     In the t-th timestep:\n",
    "        #         state[2][self.i].shape = (batch_size, t-1, hidden_size)\n",
    "        # Demo:\n",
    "        # love dogs ! [EOS]\n",
    "        #  |    |   |   |\n",
    "        #   Transformer \n",
    "        #    Decoder\n",
    "        #  |   |   |   |\n",
    "        #  I love dogs !\n",
    "        \n",
    "        if state[2][self.i] is None:\n",
    "            key_values = X\n",
    "        else:\n",
    "            # shape of key_values = (batch_size, t, hidden_size)\n",
    "            key_values = torch.cat((state[2][self.i], X), dim=1) \n",
    "        state[2][self.i] = key_values\n",
    "        \n",
    "        if self.training:\n",
    "            batch_size, seq_len, _ = X.shape\n",
    "            # Shape: (batch_size, seq_len), the values in the j-th column are j+1\n",
    "            valid_length = torch.FloatTensor(np.tile(np.arange(1, seq_len+1), (batch_size, 1))) \n",
    "            valid_length = valid_length.to(X.device)\n",
    "        else:\n",
    "            valid_length = None\n",
    "\n",
    "        X2 = self.attention_1(X, key_values, key_values, valid_length)  # multi-head attention\n",
    "        Y = self.addnorm_1(X, X2)\n",
    "        Y2 = self.attention_2(Y, enc_outputs, enc_outputs, enc_valid_length)  # multi-head attention\n",
    "        Z = self.addnorm_2(Y, Y2)\n",
    "        return self.addnorm_3(Z, self.ffn(Z)), state  # position wise FFN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_pnkw93o",
    "id": "CAF049F759654BEBAA71A76F17AF3D1C",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "对于Transformer解码器来说，构造方式与编码器一样，除了最后一层添加一个dense layer以获得输出的置信度分数。下面让我们来实现一下Transformer Decoder，除了常规的超参数例如vocab_size embedding_size 之外，解码器还需要编码器的输出 enc_outputs 和句子有效长度 enc_valid_length。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Image Name](https://cdn.kesci.com/upload/image/q5kpefhcyg.png?imageView2/0/w/800/h/800)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T05:02:48.314749Z",
     "start_time": "2020-02-18T05:02:48.296092Z"
    },
    "graffitiCellId": "id_uwit5bq",
    "id": "A08D05D6E69648E2851DC6CD464241CB",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class TransformerDecoder(d2l.Decoder):\n",
    "    def __init__(self, vocab_size, embedding_size, ffn_hidden_size, num_heads, num_layers, dropout, **kwargs):\n",
    "        super(TransformerDecoder, self).__init__(**kwargs)\n",
    "        self.embedding_size = embedding_size\n",
    "        self.num_layers = num_layers\n",
    "        self.embed = nn.Embedding(vocab_size, embedding_size)\n",
    "        self.pos_encoding = PositionalEncoding(embedding_size, dropout)\n",
    "        self.blks = nn.ModuleList()\n",
    "        for i in range(num_layers):\n",
    "            self.blks.append(\n",
    "                DecoderBlock(embedding_size, ffn_hidden_size, num_heads, dropout, i))\n",
    "        self.dense = nn.Linear(embedding_size, vocab_size)\n",
    "\n",
    "    def init_state(self, enc_outputs, enc_valid_length, *args):\n",
    "        return [enc_outputs, enc_valid_length, [None]*self.num_layers]\n",
    "\n",
    "    def forward(self, X, state):\n",
    "        X = self.pos_encoding(self.embed(X) * math.sqrt(self.embedding_size))  # embedding -> postional encoding\n",
    "        for blk in self.blks:\n",
    "            X, state = blk(X, state)  # decoderblock\n",
    "        return self.dense(X), state  # dense"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DecoderBlock"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T05:08:11.884441Z",
     "start_time": "2020-02-18T05:08:11.834672Z"
    },
    "graffitiCellId": "id_5mxi0su",
    "id": "A9BA1A943DE64FDC8A51022121BBF25D",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "torch.Size([4, 111, 16])"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# # batch_size = 4, seq_len = 111, dim = 16\n",
    "# # embedding_size = 16, ffn_hidden_size = 47, num_heads = 8, dropout = 0.5, i = 0\n",
    "# # valid_length = torch.FloatTensor([2, 3, 4, 5])\n",
    "\n",
    "X = torch.ones((4, 111, 16))\n",
    "decoder_blk = DecoderBlock(16, 47, 8, 0.5, 0)\n",
    "state = [encoder_blk(X, valid_length), valid_length, [None]]\n",
    "decoder_blk(X, state)[0].shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## TransformerDecoder"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T07:57:23.972574Z",
     "start_time": "2020-02-18T07:57:23.967435Z"
    },
    "deletable": false,
    "editable": false,
    "graffitiCellId": "id_vx2hsaf",
    "id": "2D50EE7D0CC24C3C9562EBAA5C51FF08",
    "jupyter": {},
    "run_control": {
     "frozen": true
    },
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# # test decoder\n",
    "# # batch_size = 4, seq_len = 111\n",
    "# # vocab_size = 200, \n",
    "# # embedding_size = 16, ffn_hidden_size = 47, num_heads = 8, num_layers, dropout\n",
    "# # valid_length = torch.FloatTensor([2, 3, 4, 5])\n",
    "XX = torch.ones((4, 111))  # valid_length没变，所以需要=4\n",
    "decoder = TransformerDecoder(200, 16, 47, 8, 2, 0.5)\n",
    "state = [encoder_blk(X, valid_length), valid_length, [None]]\n",
    "decoder(XX.long(), state)[0].shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "graffitiCellId": "id_rhka3y7",
    "id": "B5FF9984A72D4A3085C58FB3A368E3EA",
    "jupyter": {},
    "mdEditEnable": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "source": [
    "# 训练"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T05:09:18.257151Z",
     "start_time": "2020-02-18T05:09:18.252169Z"
    }
   },
   "outputs": [],
   "source": [
    "def try_gpu():\n",
    "    \"\"\"If GPU is available, return torch.device as cuda:0; else return torch.device as cpu.\"\"\"\n",
    "    if torch.cuda.is_available():\n",
    "        device = torch.device('cuda:0')\n",
    "    else:\n",
    "        device = torch.device('cpu')\n",
    "    return device"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T08:05:03.102513Z",
     "start_time": "2020-02-18T08:05:03.082755Z"
    }
   },
   "outputs": [],
   "source": [
    "import torch.optim as optim\n",
    "import time\n",
    "def train_s2s_ch9(model, data_iter, lr, num_epochs, device):  # Saved in d2l\n",
    "    model.to(device)\n",
    "    optimizer = optim.Adam(model.parameters(), lr=lr)\n",
    "    loss = seq.MaskedSoftmaxCELoss()\n",
    "    tic = time.time()\n",
    "    for epoch in range(1, num_epochs+1):\n",
    "        l_sum, num_tokens_sum = 0.0, 0.0\n",
    "        for batch in data_iter:\n",
    "            optimizer.zero_grad()\n",
    "            X, X_vlen, Y, Y_vlen = [x.to(device) for x in batch]\n",
    "            Y_input, Y_label, Y_vlen = Y[:,:-1], Y[:,1:], Y_vlen-1\n",
    "            \n",
    "            Y_hat, _ = model(X, Y_input, X_vlen, Y_vlen)\n",
    "            l = loss(Y_hat, Y_label, Y_vlen).sum()\n",
    "            l.backward()\n",
    "\n",
    "            with torch.no_grad():\n",
    "                seq.grad_clipping_nn(model, 5, device)\n",
    "            num_tokens = Y_vlen.sum().item()\n",
    "            optimizer.step()\n",
    "            l_sum += l.sum().item()\n",
    "            num_tokens_sum += num_tokens\n",
    "        if epoch % 50 == 0:\n",
    "            print(\"epoch {0:4d},loss {1:.3f}, time {2:.1f} sec\".format( \n",
    "                  epoch, (l_sum/num_tokens_sum), time.time()-tic))\n",
    "            tic = time.time()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T08:03:45.371275Z",
     "start_time": "2020-02-18T08:03:43.449550Z"
    },
    "graffitiCellId": "id_ejtd65n",
    "id": "CF24003818D24C8EB13D73526386F6DA",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "cuda:0\n"
     ]
    }
   ],
   "source": [
    "import seq\n",
    "# 平台暂时不支持gpu，现在会自动使用cpu训练，gpu可以用了之后会使用gpu来训练\n",
    "# os.environ[\"CUDA_VISIBLE_DEVICES\"] = \"1\"\n",
    "\n",
    "embed_size, embedding_size, num_layers, dropout = 32, 32, 2, 0.05\n",
    "batch_size, num_steps = 64, 10\n",
    "lr, num_epochs, ctx = 0.005, 200, seq.try_gpu()\n",
    "print(ctx)\n",
    "# device = torch.device(\"cuda:0\" if torch.cuda.is_available() else \"cpu\")\n",
    "# print(device)\n",
    "num_hiddens, num_heads = 64, 4\n",
    "\n",
    "src_vocab, tgt_vocab, train_iter = load_data_nmt(batch_size, num_steps)\n",
    "\n",
    "encoder = TransformerEncoder(len(src_vocab), embedding_size, num_hiddens, num_heads, num_layers, dropout)\n",
    "decoder = TransformerDecoder(len(src_vocab), embedding_size, num_hiddens, num_heads, num_layers, dropout)\n",
    "model = seq.EncoderDecoder(encoder, decoder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T08:08:05.665226Z",
     "start_time": "2020-02-18T08:05:04.689053Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "epoch   50,loss 0.046, time 36.3 sec\n",
      "epoch  100,loss 0.039, time 35.9 sec\n",
      "epoch  150,loss 0.035, time 36.5 sec\n",
      "epoch  200,loss 0.034, time 36.2 sec\n",
      "epoch  250,loss 0.032, time 36.1 sec\n"
     ]
    }
   ],
   "source": [
    "train_s2s_ch9(model, train_iter, lr, num_epochs, ctx)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 测试"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T08:08:15.178077Z",
     "start_time": "2020-02-18T08:08:15.160651Z"
    }
   },
   "outputs": [],
   "source": [
    "def predict_s2s_ch9(model, src_sentence, src_vocab, tgt_vocab, max_len, device):\n",
    "    model.to(device)\n",
    "    src_tokens = src_vocab[src_sentence.lower().split(' ')]\n",
    "    src_len = len(src_tokens)\n",
    "    if src_len < max_len:\n",
    "        src_tokens += [src_vocab.pad] * (max_len - src_len)\n",
    "    enc_X = torch.tensor(src_tokens, device=device)\n",
    "    enc_valid_length = torch.tensor([src_len], device=device)\n",
    "    # use expand_dim to add the batch_size dimension.\n",
    "    enc_outputs = model.encoder(enc_X.unsqueeze(dim=0), enc_valid_length)\n",
    "    dec_state = model.decoder.init_state(enc_outputs, enc_valid_length)\n",
    "    dec_X = torch.tensor([tgt_vocab.bos], device=device).unsqueeze(dim=0)\n",
    "    predict_tokens = []\n",
    "    for _ in range(max_len):\n",
    "        Y, dec_state = model.decoder(dec_X, dec_state)\n",
    "        # The token with highest score is used as the next time step input.\n",
    "        dec_X = Y.argmax(dim=2)\n",
    "        py = dec_X.squeeze(dim=0).int().item()\n",
    "        if py == tgt_vocab.eos:\n",
    "            break\n",
    "        predict_tokens.append(py)\n",
    "    return ' '.join(tgt_vocab.to_tokens(predict_tokens))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T08:08:16.102545Z",
     "start_time": "2020-02-18T08:08:16.090137Z"
    },
    "collapsed": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "EncoderDecoder(\n",
       "  (encoder): TransformerEncoder(\n",
       "    (embed): Embedding(184, 32)\n",
       "    (pos_encoding): PositionalEncoding(\n",
       "      (dropout): Dropout(p=0.05)\n",
       "    )\n",
       "    (blks): ModuleList(\n",
       "      (0): EncoderBlock(\n",
       "        (attention): MultiHeadAttention(\n",
       "          (attention): DotProductAttention(\n",
       "            (dropout): Dropout(p=0.05)\n",
       "          )\n",
       "          (W_q): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_k): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_v): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_o): Linear(in_features=32, out_features=32, bias=False)\n",
       "        )\n",
       "        (addnorm_1): AddNorm(\n",
       "          (dropout): Dropout(p=0.05)\n",
       "          (norm): LayerNorm(torch.Size([32]), eps=1e-05, elementwise_affine=True)\n",
       "        )\n",
       "        (ffn): PositionWiseFFN(\n",
       "          (ffn_1): Linear(in_features=32, out_features=64, bias=True)\n",
       "          (ffn_2): Linear(in_features=64, out_features=32, bias=True)\n",
       "        )\n",
       "        (addnorm_2): AddNorm(\n",
       "          (dropout): Dropout(p=0.05)\n",
       "          (norm): LayerNorm(torch.Size([32]), eps=1e-05, elementwise_affine=True)\n",
       "        )\n",
       "      )\n",
       "      (1): EncoderBlock(\n",
       "        (attention): MultiHeadAttention(\n",
       "          (attention): DotProductAttention(\n",
       "            (dropout): Dropout(p=0.05)\n",
       "          )\n",
       "          (W_q): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_k): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_v): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_o): Linear(in_features=32, out_features=32, bias=False)\n",
       "        )\n",
       "        (addnorm_1): AddNorm(\n",
       "          (dropout): Dropout(p=0.05)\n",
       "          (norm): LayerNorm(torch.Size([32]), eps=1e-05, elementwise_affine=True)\n",
       "        )\n",
       "        (ffn): PositionWiseFFN(\n",
       "          (ffn_1): Linear(in_features=32, out_features=64, bias=True)\n",
       "          (ffn_2): Linear(in_features=64, out_features=32, bias=True)\n",
       "        )\n",
       "        (addnorm_2): AddNorm(\n",
       "          (dropout): Dropout(p=0.05)\n",
       "          (norm): LayerNorm(torch.Size([32]), eps=1e-05, elementwise_affine=True)\n",
       "        )\n",
       "      )\n",
       "    )\n",
       "  )\n",
       "  (decoder): TransformerDecoder(\n",
       "    (embed): Embedding(184, 32)\n",
       "    (pos_encoding): PositionalEncoding(\n",
       "      (dropout): Dropout(p=0.05)\n",
       "    )\n",
       "    (blks): ModuleList(\n",
       "      (0): DecoderBlock(\n",
       "        (attention_1): MultiHeadAttention(\n",
       "          (attention): DotProductAttention(\n",
       "            (dropout): Dropout(p=0.05)\n",
       "          )\n",
       "          (W_q): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_k): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_v): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_o): Linear(in_features=32, out_features=32, bias=False)\n",
       "        )\n",
       "        (addnorm_1): AddNorm(\n",
       "          (dropout): Dropout(p=0.05)\n",
       "          (norm): LayerNorm(torch.Size([32]), eps=1e-05, elementwise_affine=True)\n",
       "        )\n",
       "        (attention_2): MultiHeadAttention(\n",
       "          (attention): DotProductAttention(\n",
       "            (dropout): Dropout(p=0.05)\n",
       "          )\n",
       "          (W_q): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_k): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_v): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_o): Linear(in_features=32, out_features=32, bias=False)\n",
       "        )\n",
       "        (addnorm_2): AddNorm(\n",
       "          (dropout): Dropout(p=0.05)\n",
       "          (norm): LayerNorm(torch.Size([32]), eps=1e-05, elementwise_affine=True)\n",
       "        )\n",
       "        (ffn): PositionWiseFFN(\n",
       "          (ffn_1): Linear(in_features=32, out_features=64, bias=True)\n",
       "          (ffn_2): Linear(in_features=64, out_features=32, bias=True)\n",
       "        )\n",
       "        (addnorm_3): AddNorm(\n",
       "          (dropout): Dropout(p=0.05)\n",
       "          (norm): LayerNorm(torch.Size([32]), eps=1e-05, elementwise_affine=True)\n",
       "        )\n",
       "      )\n",
       "      (1): DecoderBlock(\n",
       "        (attention_1): MultiHeadAttention(\n",
       "          (attention): DotProductAttention(\n",
       "            (dropout): Dropout(p=0.05)\n",
       "          )\n",
       "          (W_q): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_k): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_v): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_o): Linear(in_features=32, out_features=32, bias=False)\n",
       "        )\n",
       "        (addnorm_1): AddNorm(\n",
       "          (dropout): Dropout(p=0.05)\n",
       "          (norm): LayerNorm(torch.Size([32]), eps=1e-05, elementwise_affine=True)\n",
       "        )\n",
       "        (attention_2): MultiHeadAttention(\n",
       "          (attention): DotProductAttention(\n",
       "            (dropout): Dropout(p=0.05)\n",
       "          )\n",
       "          (W_q): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_k): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_v): Linear(in_features=32, out_features=32, bias=False)\n",
       "          (W_o): Linear(in_features=32, out_features=32, bias=False)\n",
       "        )\n",
       "        (addnorm_2): AddNorm(\n",
       "          (dropout): Dropout(p=0.05)\n",
       "          (norm): LayerNorm(torch.Size([32]), eps=1e-05, elementwise_affine=True)\n",
       "        )\n",
       "        (ffn): PositionWiseFFN(\n",
       "          (ffn_1): Linear(in_features=32, out_features=64, bias=True)\n",
       "          (ffn_2): Linear(in_features=64, out_features=32, bias=True)\n",
       "        )\n",
       "        (addnorm_3): AddNorm(\n",
       "          (dropout): Dropout(p=0.05)\n",
       "          (norm): LayerNorm(torch.Size([32]), eps=1e-05, elementwise_affine=True)\n",
       "        )\n",
       "      )\n",
       "    )\n",
       "    (dense): Linear(in_features=32, out_features=184, bias=True)\n",
       "  )\n",
       ")"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "model.eval()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-18T08:08:19.929968Z",
     "start_time": "2020-02-18T08:08:19.806126Z"
    },
    "graffitiCellId": "id_j2p7osp",
    "id": "5499C9F770424B3D8EE5F8CBAC59731C",
    "jupyter": {},
    "scrolled": false,
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Go . => va !\n",
      "Wow ! =>  le  à  !\n",
      "I'm OK . => je vais bien .\n",
      "I won ! => je l'ai emporté !\n"
     ]
    }
   ],
   "source": [
    "for sentence in ['Go .', 'Wow !', \"I'm OK .\", 'I won !']:\n",
    "    print(sentence + ' => ' + predict_s2s_ch9(model, sentence, src_vocab, tgt_vocab, num_steps, ctx))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "graffitiCellId": "id_1glxxfk",
    "id": "94E865681BF5401C9E5EA47615ABCA30",
    "jupyter": {},
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": []
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "hide_input": false,
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "592.5px",
    "left": "106px",
    "top": "162.964px",
    "width": "165px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}