Week 05/Week_05_RNNs_Intro.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Week 05 - RNNs Intro.ipynb",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "accelerator": "GPU"
  },
  "cells": [
    {
      "metadata": {
        "id": "YfeVtEQwRmsR",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "!pip3 -qq install torch==0.4.1\n",
        "!pip install -qq bokeh==0.13.0\n",
        "!wget -O surnames.txt -qq --no-check-certificate \"https://drive.google.com/uc?export=download&id=1ji7dhr9FojPeV51dDlKRERIqr3vdZfhu\""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "YKoTq9xW-PdW",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "import numpy as np\n",
        "\n",
        "import torch\n",
        "import torch.nn as nn\n",
        "import torch.nn.functional as F\n",
        "import torch.optim as optim\n",
        "\n",
        "\n",
        "if torch.cuda.is_available():\n",
        "    from torch.cuda import FloatTensor, LongTensor\n",
        "else:\n",
        "    from torch import FloatTensor, LongTensor\n",
        "\n",
        "np.random.seed(42)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "_Q5wMjxQMeQS",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Рекуррентные нейронные сети, часть 1"
      ]
    },
    {
      "metadata": {
        "id": "NY5-j_RsRzxa",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Классификация фамилий\n",
        "\n",
        "Теперь - по языкам:"
      ]
    },
    {
      "metadata": {
        "id": "TPPJoWEpSN_B",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "data, labels = [], []\n",
        "with open('surnames.txt') as f:\n",
        "    for line in f:\n",
        "        surname, lang = line.strip().split('\\t')\n",
        "        data.append(surname)\n",
        "        labels.append(lang)\n",
        "\n",
        "for i in np.random.randint(0, len(data), 10):\n",
        "    print(data[i], labels[i])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "6bVJlxzYhWuf",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Разминка\n",
        "\n",
        "Проверьте свои знания - попробуйте самостоятельно предсказать, к какому языку относится фамилия :)"
      ]
    },
    {
      "metadata": {
        "id": "G7JquuckaAGb",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "from sklearn.utils.class_weight import compute_class_weight\n",
        "\n",
        "def test_generator():\n",
        "    classes = np.unique(labels)\n",
        "    weights = compute_class_weight('balanced', classes, labels)\n",
        "    classes = {label: ind for ind, label in enumerate(classes)}\n",
        "\n",
        "    probs = np.array([weights[classes[label]] for label in labels])\n",
        "    probs /= probs.sum()\n",
        "\n",
        "    ind = np.random.choice(np.arange(len(data)), p=probs)\n",
        "    yield data[ind]\n",
        "    \n",
        "    while True:\n",
        "        new_ind = np.random.choice(np.arange(len(data)), p=probs)\n",
        "        yield labels[ind], data[new_ind]\n",
        "        ind = new_ind\n",
        "        \n",
        "gen = test_generator()\n",
        "question = next(gen)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "1KNeNxm1hsKs",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Запускайте, смотрите на фамилию, которая выведется - и выбирайте язык в выпадающем списке."
      ]
    },
    {
      "metadata": {
        "id": "-Q3OSXpAY8BS",
        "colab_type": "code",
        "cellView": "form",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "#@title Проверим себя (или адекватность данных) { run: \"auto\" }\n",
        "answer = \"Vietnamese\" #@param [\"Arabic\", \"Chinese\", \"Czech\", \"Dutch\", \"English\", \"French\", \"German\", \"Greek\", \"Irish\", \"Italian\", \"Japanese\", \"Korean\", \"Polish\", \"Portuguese\", \"Russian\", \"Scottish\", \"Spanish\", \"Vietnamese\"]\n",
        "\n",
        "correct_answer, question = next(gen)\n",
        "\n",
        "if 'correct_count' not in globals():\n",
        "    correct_count = 0\n",
        "    total_count = 0\n",
        "else:\n",
        "    if answer == correct_answer:\n",
        "        print('You are correct', end=' ')\n",
        "        correct_count += 1\n",
        "    else:\n",
        "        print(\"No, it's\", correct_answer, end=' ')\n",
        "\n",
        "    total_count += 1\n",
        "    print('({} / {})'.format(correct_count, total_count))\n",
        "    \n",
        "print('Next surname:', question)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "5Yz20u6dhll0",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Разбиение данных"
      ]
    },
    {
      "metadata": {
        "id": "LfP4Sb68TWlY",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Для начала нужно построить сплит данных на трейн/тест. Сложность в том, что классы распределены неравномерны, а отрезать нужно от каждого класса пропорциональное количество данных на тест. Для этого нужно использовать `stratify` параметр функции `train_test_split` (либо `StratifiedShuffleSplit`, либо, при большом желании, `GroupShuffleSplit`)."
      ]
    },
    {
      "metadata": {
        "id": "1eE-s7q7RmAM",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "from sklearn.model_selection import train_test_split\n",
        "\n",
        "data_train, data_test, labels_train, labels_test = train_test_split(\n",
        "    data, labels, test_size=0.3, stratify=labels, random_state=42\n",
        ")"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "uzX5zHobUHc0",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "import matplotlib.pyplot as plt\n",
        "%matplotlib inline\n",
        "\n",
        "from collections import Counter\n",
        "\n",
        "langs = set(labels)\n",
        "\n",
        "train_distribution = Counter(labels_train)\n",
        "train_distribution = [train_distribution[lang] for lang in langs]\n",
        "\n",
        "test_distribution = Counter(labels_test)\n",
        "test_distribution = [test_distribution[lang] for lang in langs]\n",
        "\n",
        "plt.figure(figsize=(17, 5))\n",
        "\n",
        "bar_width = 0.35\n",
        "plt.bar(np.arange(len(langs)), train_distribution, bar_width, align='center', alpha=0.5, label='train')\n",
        "plt.bar(np.arange(len(langs)) + bar_width, test_distribution, bar_width, align='center', alpha=0.5, label='test')\n",
        "plt.xticks(np.arange(len(langs)) + bar_width / 2, langs)\n",
        "plt.legend()\n",
        "    \n",
        "plt.show()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "MgmDagAq5-mm",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "### Бейзлайн"
      ]
    },
    {
      "metadata": {
        "id": "pDgB4iVCWbNE",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Всегда надо начинать с бейзлайна - воспользуемся нашей любимой парой vectorizer-logistic regression:"
      ]
    },
    {
      "metadata": {
        "id": "PLxUE4thXyV2",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "from sklearn.feature_extraction.text import CountVectorizer\n",
        "from sklearn.linear_model import LogisticRegression\n",
        "from sklearn.pipeline import Pipeline\n",
        "\n",
        "model = Pipeline([\n",
        "    ('vectorizer', CountVectorizer(analyzer='char', ngram_range=(1, 4))),\n",
        "    ('log_regression', LogisticRegression())\n",
        "])\n",
        "\n",
        "model.fit(data_train, labels_train)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "wz9ngs_lWn3p",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Какие метрики будем считать? Тут многоклассовая классификация, поэтому всё очень неоднозначно.\n",
        "\n",
        "Имеет смысл посмотреть на accuracy и на F1-score'ы для каждого класса."
      ]
    },
    {
      "metadata": {
        "id": "OJZt8sKM6zEA",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "from sklearn.metrics import accuracy_score, confusion_matrix, classification_report\n",
        "\n",
        "preds = model.predict(data_test)\n",
        "\n",
        "print('Accuracy = {:.2%}'.format(accuracy_score(labels_test, preds)))\n",
        "print('Classification report:')\n",
        "print(classification_report(labels_test, preds))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "VNRhUTNaW45M",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "F1-score'ы можно агрегировать разными способами:\n",
        "- weighted - это как посчитал classification_report - если нам важнее предсказывать хорошо более частотные фамилии\n",
        "- macro - простое усреднение - если важно предсказывать все, независимо от того, сколько каждого класса в тестовой выборке\n",
        "- micro - обычный подсчет F1-score по суммам всех true positive, false positive и false negative\n",
        "\n",
        "Weighted и micro - две метрики, учитывающие дисбаланс классов. Но в нашем случае неочевидно, есть ли дисбаланс, да?"
      ]
    },
    {
      "metadata": {
        "id": "I0SwCbWN8ZQd",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "import matplotlib.ticker as ticker\n",
        "\n",
        "label_names = list(set(labels_test))\n",
        "confusion = confusion_matrix(labels_test, preds, labels=label_names).astype(np.float)\n",
        "confusion /= confusion.sum(axis=-1, keepdims=True)\n",
        "\n",
        "fig = plt.figure(figsize=(9, 9))\n",
        "ax = fig.add_subplot(111)\n",
        "cax = ax.matshow(confusion, cmap='Reds')\n",
        "fig.colorbar(cax)\n",
        "\n",
        "ax.set_xticklabels([''] + label_names, rotation=45)\n",
        "ax.set_yticklabels([''] + label_names)\n",
        "\n",
        "ax.xaxis.set_major_locator(ticker.MultipleLocator(1))\n",
        "ax.yaxis.set_major_locator(ticker.MultipleLocator(1))\n",
        "\n",
        "plt.show()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "qo0lsnzV-i-P",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Simple RNN"
      ]
    },
    {
      "metadata": {
        "id": "Hb4_VaBIMVFD",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Основная прелесть RNN - расшаренные параметры. Посмотрите на картинку:\n",
        "\n",
        "![RNN types](http:https://karpathy.github.io/assets/rnn/diags.jpeg =x250)\n",
        "\n",
        "*From [(The Unreasonable Effectiveness of Recurrent Neural Networks)](http:https://karpathy.github.io/2015/05/21/rnn-effectiveness/)*\n",
        "\n",
        "Первый пример - это обычная полносвязная сеть. Каждый следующий демонстрирует обработку некоторой последовательности произвольной длины (красные прямоугольнички) и генерацию выходной последовательности, также произвольной длины (синие прямоугольники).\n",
        "\n",
        "При этом зеленые прямоугольники в каждом рисунке - это одни и те же веса. Получается, мы, с одной стороны, обучаем очень-очень глубокую сеть (если посмотреть на неё перевернутую), а с другой - строго ограниченное количество параметров.\n",
        "\n",
        "---\n",
        "Напишем сразу простую RNN!\n",
        "\n",
        "Напомню, делает она примерно вот это:\n",
        "\n",
        "![rnn-unrolled](http:https://colah.github.io/posts/2015-08-Understanding-LSTMs/img/RNN-unrolled.png =x220)\n",
        "\n",
        "*From [(Understanding LSTM Networks)](http:https://colah.github.io/posts/2015-08-Understanding-LSTMs)*\n",
        "\n",
        "Вообще говоря, можно придумать много вариаций на тему такой реализации. В нашем случае, обработка будет такой:\n",
        "$$h_t = tanh(W_h [h_{t-1}; x_t] + b_h)$$\n",
        "\n",
        "$h_{t-1}$ - скрытое состояние, полученное на предыдущем шаге, $x_t$ - входной вектор. $[h_{t-1}; x_t]$ - простая конкатенация векторов. Всё как на картинке!\n",
        "\n",
        "Проверим нашу сеть на очень простой задаче: заставим её говорить индекс первого элемента в последовательности.\n",
        "\n",
        "Т.е. для последовательности `[1, 2, 1, 3]` сеть должна предсказывать `1`.\n",
        "\n",
        "Начнем с генерации батча."
      ]
    },
    {
      "metadata": {
        "id": "yOI4JGgHT-z3",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "def generate_data(batch_size=128, seq_len=5):\n",
        "    data = torch.randint(0, 10, size=(seq_len, batch_size), dtype=torch.long)\n",
        "    return data, data[0]\n",
        "\n",
        "X_val, y_val = generate_data()\n",
        "X_val, y_val"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "EQ0Gsr4SFNtB",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Обратите внимание, что батч имеет размерность `(sequence_length, batch_size, input_size)`. Все `RNN` в pytorch работают с таким форматом по умолчанию.\n",
        "\n",
        "Сделано это из соображений производительности, но при желании можно поменять такое поведение с помощью аргумента `batch_first`."
      ]
    },
    {
      "metadata": {
        "id": "PqS7HPRhZSBC",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "**Задание** Реализуйте класс `SimpleRNN`, выполняющий рассчеты по формуле выше."
      ]
    },
    {
      "metadata": {
        "id": "ed1b2TUvZRs0",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "class SimpleRNN(nn.Module):\n",
        "    def __init__(self, input_size, hidden_size):\n",
        "        super().__init__()\n",
        "\n",
        "        self._hidden_size = hidden_size\n",
        "        <create Linear layer>\n",
        "\n",
        "    def forward(self, inputs, hidden=None):\n",
        "        seq_len, batch_size = inputs.shape[:2]\n",
        "        if hidden is None:\n",
        "            hidden = inputs.new_zeros((batch_size, self._hidden_size))\n",
        "         \n",
        "        for i in range(seq_len):\n",
        "            <apply linear layer to concatenation of current input (inputs[i]) and hidden>\n",
        "\n",
        "        return hidden"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "KS2xw2YIZ_EU",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Должно стать понятно, почему полезно иметь первой размерностью seq_len - нужно уметь брать `inputs[i]` - подбатч, относящийся к данному таймстемпу. Если бы данные были расположены по-другому, эта операция была бы сильно дороже.\n",
        "\n",
        "**Задание** Реализуйте класс `MemorizerModel`, с последовательностью операций `Embedding -> SimpleRNN -> Linear`. Можно использовать `nn.Sequential`\n",
        "\n",
        "Чтобы сделать эмбеддинги, можно воспользоваться `nn.Embedding.from_pretrained`. Для простоты будем делать one-hot-encoding представление - для этого нужно просто инициализировать сеть единичной матрицей `torch.eye(N)`."
      ]
    },
    {
      "metadata": {
        "id": "aEUr4Xa9Z81I",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# u can use nn.Sequential too\n",
        "class MemorizerModel(nn.Module):\n",
        "    def __init__(self, hidden_size):\n",
        "        super().__init__()\n",
        "\n",
        "        <create layers>\n",
        "\n",
        "    def forward(self, inputs):\n",
        "        <apply 'em>"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "eiDRoQWDawaW",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Запустим обучение:"
      ]
    },
    {
      "metadata": {
        "id": "IbVk7zUjUQ_v",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "rnn = MemorizerModel(hidden_size=32)\n",
        "\n",
        "criterion = nn.CrossEntropyLoss()\n",
        "optimizer = torch.optim.Adam(rnn.parameters())\n",
        "\n",
        "total_loss = 0\n",
        "epochs_count = 1000\n",
        "for epoch_ind in range(epochs_count):\n",
        "    X_train, y_train = generate_data(seq_len=25)\n",
        "    \n",
        "    optimizer.zero_grad()\n",
        "    rnn.train()\n",
        "    \n",
        "    logits = rnn(X_train)\n",
        "\n",
        "    loss = criterion(logits, y_train)\n",
        "    loss.backward()\n",
        "    optimizer.step()\n",
        "    \n",
        "    total_loss += loss.item()\n",
        "    \n",
        "    if (epoch_ind + 1) % 100 == 0:\n",
        "        rnn.eval()\n",
        "        \n",
        "        with torch.no_grad():\n",
        "            logits = rnn(X_val)\n",
        "            val_loss = criterion(logits, y_val)\n",
        "            print('[{}/{}] Train: {:.3f} Val: {:.3f}'.format(epoch_ind + 1, epochs_count, \n",
        "                                                             total_loss / 100, val_loss.item()))\n",
        "            total_loss = 0"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "dQJg3FROIq4v",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "**Задание** Посмотрите на то, как влияет длина последовательности на работу сети. \n",
        "\n",
        "Во-первых, посмотрите, с какой длиной сеть в состоянии учиться. Во-вторых, попробуйте обучить сеть с небольшой длиной последовательности, а потом применять её к более длинным.\n",
        "\n",
        "**Задание** Утверждается, что `relu` подходит для RNN лучше. Попробуйте и её."
      ]
    },
    {
      "metadata": {
        "id": "nSHNuT5b61Ky",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Обучение RNN'ок\n",
        "\n",
        "![bptt](https://image.ibb.co/cEYkw9/rnn_bptt_with_gradients.png =x400)  \n",
        "*From [Recurrent Neural Networks Tutorial, Part 3 – Backpropagation Through Time and Vanishing Gradients](http:https://www.wildml.com/2015/10/recurrent-neural-networks-tutorial-part-3-backpropagation-through-time-and-vanishing-gradients/)*\n",
        "\n",
        "Если всё пошло по плану, мы должны были посмотреть на то, как RNN'ки забывают. \n",
        "\n",
        "Чтобы понять причину, стоит вспомнить, как именно происходит обучение RNN, например, здесь: [Backpropagation Through Time and Vanishing Gradients](http:https://www.wildml.com/2015/10/recurrent-neural-networks-tutorial-part-3-backpropagation-through-time-and-vanishing-gradients/) или здесь - [Vanishing Gradients & LSTMs](http:https://harinisuresh.com/2016/10/09/lstms/).\n",
        "\n",
        "Если кратко, одна из проблем обучения рекуррентных сетей - *взрыв градиентов*. Она проявляется, когда матрица весов такова, что увеличивает норму вектора градиента при обратном проходе. В результате норма градиента экспоненциально растет и он \"взрывается\". \n",
        "\n",
        "Эту проблему можно решить с помощью клипинга градиентов: `nn.utils.clip_grad_norm_(rnn.parameters(), 1.)`."
      ]
    },
    {
      "metadata": {
        "id": "13x5erUgTjDC",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## LSTM и GRU\n",
        "\n"
      ]
    },
    {
      "metadata": {
        "id": "PAjZh9YkYAMH",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "\n",
        "\n",
        "Другая проблема - *затухание градиентов*. Она связана наоборот - с экспоненциальным затуханием градиентов. И вот её решают уже более сложными способами. \n",
        "\n",
        "А именно - используют gate'овые архитектуры.\n",
        "\n",
        "Идея gate'а простая, но важная, используются они далеко не только в рекуррентных сетях.\n",
        "\n",
        "Если посмотреть на то, как работает наша SimpleRNN, можно заметить, что каждый раз память (т.е. $h_t$) перезаписывается. Хочется иметь возможность сделать эту перезапись контролируемой: не отбрасывать какую-то важную инфомацию из вектора.\n",
        "\n",
        "Заведем для этого вектор $g \\in \\{0,1\\}^n$, который будет говорить, какие ячейки $h_{t-1}$ хорошие, а вместо каких стоит подставить новые значения:\n",
        "$$h_t = g \\odot f(x_t, h_{t-1}) + (1 - g) \\odot h_{t-1}.$$\n",
        "\n",
        "Например:\n",
        "$$\n",
        " \\begin{bmatrix}\n",
        "  8 \\\\\n",
        "  11 \\\\\n",
        "  3 \\\\\n",
        "  7\n",
        " \\end{bmatrix} =\n",
        " \\begin{bmatrix}\n",
        "  0 \\\\\n",
        "  1 \\\\\n",
        "  0 \\\\\n",
        "  0\n",
        " \\end{bmatrix}\n",
        " \\odot\n",
        "  \\begin{bmatrix}\n",
        "  7 \\\\\n",
        "  11 \\\\\n",
        "  6 \\\\\n",
        "  5\n",
        " \\end{bmatrix}\n",
        " +\n",
        "  \\begin{bmatrix}\n",
        "  1 \\\\\n",
        "  0 \\\\\n",
        "  1 \\\\\n",
        "  1\n",
        " \\end{bmatrix}\n",
        " \\odot\n",
        "  \\begin{bmatrix}\n",
        "  8 \\\\\n",
        "  5 \\\\\n",
        "  3 \\\\\n",
        "  7\n",
        " \\end{bmatrix}\n",
        "$$\n",
        "\n",
        "Чтобы добиться дифференцируемости, будем использовать сигмоиду: $\\sigma(f(x_t, h_{t-1}))$.\n",
        "\n",
        "В результате сеть будет сама, глядя на входы, решать, какие ячейки своей памяти и насколько стоит перезаписывать.\n",
        "\n",
        "### LSTM\n",
        "\n",
        "Кажется, первой архитектурой, применившей данной механизм, стал LSTM (Long Short-Term Memory).\n",
        "\n",
        "В ней у нас к $h_{t-1}$ добавляется ещё и $c_{t-1}$: $h_{t-1}$ - это всё то же скрытое состояния полученное на предыдущем шаге, а $c_{t-1}$ - это вектор памяти.\n",
        "\n",
        "Схематично - как-то так:\n",
        "![](http:https://colah.github.io/posts/2015-08-Understanding-LSTMs/img/LSTM3-chain.png =x250)  \n",
        "*From [(Understanding LSTM Networks)](http:https://colah.github.io/posts/2015-08-Understanding-LSTMs)*\n",
        "\n",
        "\n",
        "Для начала мы можем точно так же, как и раньше посчитать новое скрытое состояние (обозначим его $\\tilde c_{t}$):\n",
        "$$\\tilde c_{t} = tanh(W_h [h_{t-1}; x_t] + b_h)$$\n",
        "\n",
        "В обычных RNN мы бы просто перезаписали этим значением сторое скрытое состояние. А теперь мы хотим понять, насколько нам нужна информация из $c_{t-1}$ и из $\\tilde c_{t}$. \n",
        "\n",
        "Оценим её сигмоидами:\n",
        "$$f = \\sigma(W_f [h_{t-1}; x_t] + b_f),$$\n",
        "$$i = \\sigma(W_i [h_{t-1}; x_t] + b_i).$$\n",
        "\n",
        "Первая - про то, насколько хочется забыть старую информацию. Вторая - насколько интересна новая. Тогда\n",
        "$$c_t = f \\odot c_{t-1} + i \\odot \\tilde c_t.$$\n",
        "\n",
        "Новое скрытое состояние мы также взвесим:\n",
        "$$o = \\sigma(W_o [h_{t-1}; x_t] + b_o),$$\n",
        "$$h_t = o \\odot tanh(c_t).$$\n",
        "\n",
        "Еще одна картинка:\n",
        "![](https://image.ibb.co/e6HQUU/details.png)  \n",
        "*From [Vanishing Gradients & LSTMs](http:https://harinisuresh.com/2016/10/09/lstms/)*\n",
        "\n",
        "Почему проблема затухающих градиентов решается? Потому что посмотрите на производную $\\frac{\\partial c_t}{\\partial c_{t-1}}$. Она пропорциональна гейту $f$. Если $f=1$ - градиенты текут без изменений. Иначе - ну, сеть сама учится, когда ей хочется что-то забыть.\n",
        "\n",
        "Настоятельно рекомендуется почитать статью: [Understanding LSTM Networks](http:https://colah.github.io/posts/2015-08-Understanding-LSTMs/) для более подробного ознакомления и прикольных картинок.\n",
        "\n",
        "Зачем я выписал эти формулы? Главное - чтобы показать, насколько больше параметров нужно учить в LSTM по сравнению с обычным RNN. В четыре раза больше!\n",
        "\n",
        "Для тех, кто заснул - [видео, как забывает RNN (нижняя часть)](https://www.youtube.com/watch?v=mLxsbWAYIpw)"
      ]
    },
    {
      "metadata": {
        "id": "_9KWgbwQMatn",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Предобработка данных"
      ]
    },
    {
      "metadata": {
        "id": "q7-fQPwJUKtV",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "symbols = set(symb for word in data_train for symb in word)\n",
        "char2ind = {symb: ind + 1 for ind, symb in enumerate(symbols)}\n",
        "char2ind[''] = 0\n",
        "\n",
        "lang2ind = {lang: ind for ind, lang in enumerate(set(labels_train))}"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "dcFgEy7YeFw0",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Сконвертируем датасет.\n",
        "\n",
        "**Задание** Напишите генератор батчей, который будет на лету выбирать случайный набор слов и конвертировать их в матрицы."
      ]
    },
    {
      "metadata": {
        "id": "BWWClVsTRVuA",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "def iterate_batches(data, labels, char2ind, lang2ind, batch_size):\n",
        "    # let's do the conversion part first\n",
        "    labels = np.array([lang2ind[label] for label in labels])\n",
        "    data = [[char2ind.get(symb, 0) for symb in word] for word in data]\n",
        "    \n",
        "    indices = np.arange(len(data))\n",
        "    np.random.shuffle(indices)\n",
        "    \n",
        "    for start in range(0, len(data), batch_size):\n",
        "        end = min(start + batch_size, len(data))\n",
        "        \n",
        "        batch_indices = indices[start: end]\n",
        "        \n",
        "        max_word_len = max(len(data[ind]) for ind in batch_indices)\n",
        "        X = np.zeros((max_word_len, len(batch_indices)))\n",
        "        <fill X>\n",
        "            \n",
        "        yield X, labels[batch_indices]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "CfeR4B_hbH9P",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Лень передавать `char2ind, lang2ind`:"
      ]
    },
    {
      "metadata": {
        "id": "uA-_jRNdaCM3",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "from functools import partial\n",
        "\n",
        "iterate_batches = partial(iterate_batches, char2ind=char2ind, lang2ind=lang2ind)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "HD5i7WmTVlGk",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "next(iterate_batches(data, labels, batch_size=8))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "dnkAUetgs6Tr",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "**Задание** Реализуйте простую модель на `SimpleRNN`."
      ]
    },
    {
      "metadata": {
        "id": "Zk3OSidVS_px",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "class SurnamesClassifier(nn.Module):\n",
        "    def __init__(self, vocab_size, emb_dim, lstm_hidden_dim, classes_count):\n",
        "        super().__init__()\n",
        "        \n",
        "        <set layers>\n",
        "            \n",
        "    def forward(self, inputs):\n",
        "        'embed(inputs) -> prediction'\n",
        "        <implement it>\n",
        "    \n",
        "    def embed(self, inputs):\n",
        "        'inputs -> word embedding'\n",
        "        <and it> "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "1vXN-QIrZs95",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "import math\n",
        "import time\n",
        "\n",
        "def do_epoch(model, criterion, data, batch_size, optimizer=None):  \n",
        "    epoch_loss = 0.\n",
        "    \n",
        "    is_train = not optimizer is None\n",
        "    model.train(is_train)\n",
        "    \n",
        "    data, labels = data\n",
        "    batchs_count = math.ceil(len(data) / batch_size)\n",
        "    \n",
        "    with torch.autograd.set_grad_enabled(is_train):\n",
        "        for i, (X_batch, y_batch) in enumerate(iterate_batches(data, labels, batch_size=batch_size)):\n",
        "            X_batch, y_batch = LongTensor(X_batch), LongTensor(y_batch)\n",
        "\n",
        "            logits = model(X_batch)\n",
        "            loss = criterion(logits, y_batch)\n",
        "            epoch_loss += loss.item()\n",
        "\n",
        "            if is_train:\n",
        "                optimizer.zero_grad()\n",
        "                loss.backward()\n",
        "                nn.utils.clip_grad_norm_(model.parameters(), 1.)\n",
        "                optimizer.step()\n",
        "\n",
        "            print('\\r[{} / {}]: Loss = {:.4f}'.format(i, batchs_count, loss.item()), end='')\n",
        "                \n",
        "    return epoch_loss / batchs_count\n",
        "\n",
        "def fit(model, criterion, optimizer, train_data, epochs_count=1, \n",
        "        batch_size=32, val_data=None, val_batch_size=None):\n",
        "    if not val_data is None and val_batch_size is None:\n",
        "        val_batch_size = batch_size\n",
        "        \n",
        "    for epoch in range(epochs_count):\n",
        "        start_time = time.time()\n",
        "        train_loss = do_epoch(model, criterion, train_data, batch_size, optimizer)\n",
        "        \n",
        "        output_info = '\\rEpoch {} / {}, Epoch Time = {:.2f}s: Train Loss = {:.4f}'\n",
        "        if not val_data is None:\n",
        "            val_loss = do_epoch(model, criterion, val_data, val_batch_size, None)\n",
        "            \n",
        "            epoch_time = time.time() - start_time\n",
        "            output_info += ', Val Loss = {:.4f}'\n",
        "            print(output_info.format(epoch+1, epochs_count, epoch_time, train_loss, val_loss))\n",
        "        else:\n",
        "            epoch_time = time.time() - start_time\n",
        "            print(output_info.format(epoch+1, epochs_count, epoch_time, train_loss))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "x9vBDF2gbypR",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "model = SurnamesClassifier(vocab_size=len(char2ind), emb_dim=16, lstm_hidden_dim=64, classes_count=len(lang2ind)).cuda()\n",
        "\n",
        "criterion = nn.CrossEntropyLoss().cuda()\n",
        "optimizer = optim.Adam(model.parameters())\n",
        "\n",
        "fit(model, criterion, optimizer, epochs_count=50, batch_size=128, train_data=(data_train, labels_train),\n",
        "    val_data=(data_test, labels_test), val_batch_size=512)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "jC76XyGjigFx",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "**Задание** Напишите функцию для тестирования полученной сети: пусть она принимает слово и говорит, в каком языке с какой вероятностью это может быть фамилией."
      ]
    },
    {
      "metadata": {
        "id": "gsGNbpBVJ3xO",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "aWqOPgdbIYcl",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "**Задание** Оцените качество модели."
      ]
    },
    {
      "metadata": {
        "id": "dT2QE6IycXo9",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "model.eval()\n",
        "\n",
        "y_test, y_pred = [], []\n",
        "<calc 'em>\n",
        "\n",
        "print('Accuracy = {:.2%}'.format(accuracy_score(y_test, y_pred)))\n",
        "print('Classification report:')\n",
        "print(classification_report(y_test, y_pred, \n",
        "                            target_names=[lang for lang, _ in sorted(lang2ind.items(), key=lambda x: x[1])]))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "B_FZ9x0NInft",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Визуализация эмбеддингов"
      ]
    },
    {
      "metadata": {
        "id": "bJkyBV2bAK05",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "import bokeh.models as bm, bokeh.plotting as pl\n",
        "from bokeh.colors import RGB\n",
        "from bokeh.io import output_notebook\n",
        "\n",
        "from sklearn.manifold import TSNE\n",
        "from sklearn.preprocessing import scale\n",
        "\n",
        "\n",
        "def draw_vectors(x, y, radius=10, alpha=0.25, color='blue',\n",
        "                 width=600, height=400, show=True, **kwargs):\n",
        "    \"\"\" draws an interactive plot for data points with auxilirary info on hover \"\"\"\n",
        "    output_notebook()\n",
        "    \n",
        "    if isinstance(color, str): \n",
        "        color = [color] * len(x)\n",
        "    if isinstance(color, np.ndarray):\n",
        "        color = [RGB(*x[:3]) for x in color]\n",
        "    print(color)\n",
        "    data_source = bm.ColumnDataSource({ 'x' : x, 'y' : y, 'color': color, **kwargs })\n",
        "\n",
        "    fig = pl.figure(active_scroll='wheel_zoom', width=width, height=height)\n",
        "    fig.scatter('x', 'y', size=radius, color='color', alpha=alpha, source=data_source)\n",
        "\n",
        "    fig.add_tools(bm.HoverTool(tooltips=[(key, \"@\" + key) for key in kwargs.keys()]))\n",
        "    if show: \n",
        "        pl.show(fig)\n",
        "    return fig\n",
        "\n",
        "\n",
        "def get_tsne_projection(word_vectors):\n",
        "    tsne = TSNE(n_components=2, verbose=100)\n",
        "    return scale(tsne.fit_transform(word_vectors))\n",
        "    \n",
        "    \n",
        "def visualize_embeddings(embeddings, token, colors):\n",
        "    tsne = get_tsne_projection(embeddings)\n",
        "    draw_vectors(tsne[:, 0], tsne[:, 1], color=colors, token=token)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "1u-74cv7IrH9",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "Мы опять получили эмбеддинги - символьного уровня теперь.\n",
        "\n",
        "Хочется на них посмотреть\n",
        "\n",
        "**Задание** Посчитайте векторы для случайных слов и выведите их."
      ]
    },
    {
      "metadata": {
        "id": "jt6LsI0NAPAm",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "word_indices = np.random.choice(np.arange(len(data_test)), 1000, replace=False)\n",
        "words = [data_test[ind] for ind in word_indices]\n",
        "word_labels = [labels_test[ind] for ind in word_indices]\n",
        "\n",
        "model.eval()\n",
        "X_batch, y_batch = next(iterate_batches(words, word_labels, batch_size=1000))\n",
        "embeddings = <calc me>\n",
        "\n",
        "colors = plt.cm.tab20(y_batch) * 255\n",
        "\n",
        "visualize_embeddings(embeddings, words, colors)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "UnQMDFTgKCY0",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Визуализация работы сети\n",
        "\n",
        "На каждом шаге RNN выдает какой-то вектор. Полносвязный слой применяется только к последнему выходу. Но можно же посмотреть и на промежуточные состояния - как менялось мнение сети о том, к чему относится это слово.\n",
        "\n",
        "**Задание** Напишите свой визуализатор."
      ]
    },
    {
      "metadata": {
        "id": "86lffPwLKmqt",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "DickfCNwJZFT",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "## Улучшение сети\n",
        "\n",
        "**Задание** Замените SimpleRNN на LSTM. Сравните качества.\n",
        "\n",
        "**Задание** Добавьте Dropout до LSTM (а можно и после). Адекватным будет значение порядка 0.3.\n",
        "\n",
        "**Задание** Важным видом RNN является Bidirectional RNN. По сути это две RNN, одна обходит последовательность слева направо, вторая - наоборот. \n",
        "\n",
        "В результате для каждого момента времени у нас есть вектор $h_t = [f_t; b_t]$ - конкатенация (или какая-то ещё функция от $f_t$ и $b_t$) состояний $f_t$ и $b_t$ - прямого и обратного прохода последовательности. В сумме они покрывают весь контекст.\n",
        "\n",
        "В нашей задаче Bidirectional вариант может помочь тем, что сеть будет меньше забывать, с чего начиналась последовательность. То есть нам нужно будет взять $f_N$ и $b_N$ состояния: первое - последнее состояние в проходе слева направо, т.е. выход от последнего символа. Второе - последнее состояние при обратно проходе, т.е. выход для первого символа.\n",
        "\n",
        "Реализуйте Bidirectional классификатор. Для этого в `LSTM` есть параметр `bidirectional`."
      ]
    },
    {
      "metadata": {
        "id": "ukwXJppHrDwS",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Дополнительные материалы\n",
        "\n",
        "## Почитать\n",
        "\n",
        "### Блоги\n",
        "[The Unreasonable Effectiveness of Recurrent Neural Networks, Andrej Karpathy](http:https://karpathy.github.io/2015/05/21/rnn-effectiveness/)  \n",
        "[Understanding LSTM Networks, Christopher Olah](http:https://colah.github.io/posts/2015-08-Understanding-LSTMs/)  \n",
        "[Recurrent Neural Networks Tutorial, Denny Britz](http:https://www.wildml.com/2015/09/recurrent-neural-networks-tutorial-part-1-introduction-to-rnns/)  \n",
        "[Vanishing Gradients & LSTMs, Harini Suresh](http:https://harinisuresh.com/2016/10/09/lstms/)\n",
        "\n",
        "### Разное\n",
        "[Non-Zero Initial States for Recurrent Neural Networks](https://r2rt.com/non-zero-initial-states-for-recurrent-neural-networks.html)\n",
        "\n",
        "[Explaining and illustrating orthogonal initialization for recurrent neural networks, Stephen Merity](http:https://smerity.com/articles/2016/orthogonal_init.html)\n",
        "\n",
        "[Comparative Study of CNN and RNN for Natural Language Processing, Yin, 2017](https://arxiv.org/abs/1702.01923)\n",
        "\n",
        "## Посмотреть\n",
        "[cs224n \"Lecture 8: Recurrent Neural Networks and Language Models\"](https://www.youtube.com/watch?v=Keqep_PKrY8)"
      ]
    },
    {
      "metadata": {
        "id": "gdMatMdGKq9X",
        "colab_type": "text"
      },
      "cell_type": "markdown",
      "source": [
        "# Сдача задания\n",
        "\n",
        "[Опрос](https://goo.gl/forms/6d04Bkk36mVpBYt32)"
      ]
    }
  ]
}