ML17/homeworks-practice/homework-practice-04/homework-practice-04.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Машинное обучение, ВМК МГУ\n",
    "\n",
    "## Практическое задание 4\n",
    "\n",
    "### Общая информация\n",
    "Дата выдачи: 10.03.2018\n",
    "\n",
    "Мягкий дедлайн: 25.03.2018 (за каждый день просрочки снимается 1 балл)\n",
    "\n",
    "Жесткий дедлайн: 01.04.2018"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### О задании\n",
    "\n",
    "__Первая часть__ задания посвящена реализации различных слоёв нейронной сети.\n",
    "\n",
    "__Вторая часть__ задания посвящена реализации алгоритма обратного распространения ошибки и обучение нейросети на задаче распознавания рукописных цифр MNIST.\n",
    "\n",
    "__Бонусная часть__ задания посвящена реализации сверточного слоя и пулинга для улучшения решения задачи классификации из предыдущего пункта.\n",
    "\n",
    "\n",
    "### Оценивание и штрафы\n",
    "Каждая из задач имеет определенную «стоимость» (указана в скобках около задачи). Максимально допустимая оценка за основную часть работы — 10 баллов.\n",
    "\n",
    "Сдавать задание после указанного срока сдачи нельзя. При выставлении неполного балла за задание в связи с наличием ошибок на усмотрение проверяющего предусмотрена возможность исправить работу на указанных в ответном письме условиях.\n",
    "\n",
    "Задание выполняется самостоятельно. «Похожие» решения считаются плагиатом и все задействованные студенты (в том числе те, у кого списали) не могут получить за него больше 0 баллов (подробнее о плагиате см. на странице курса). Если вы нашли решение какого-то из заданий (или его часть) в открытом источнике, необходимо указать ссылку на этот источник в отдельном блоке в конце Вашей работы (скорее всего вы будете не единственным, кто это нашел, поэтому чтобы исключить подозрение в плагиате, необходима ссылка на источник).\n",
    "\n",
    "Неэффективная реализация кода может негативно отразиться на оценке.\n",
    "\n",
    "\n",
    "### Формат сдачи\n",
    "Для сдачи задания переименуйте получившийся файл *.ipynb в соответствии со следующим форматом: homework-practice-04-Username.ipynb, где Username — Ваша фамилия и имя на латинице именно в таком порядке (например, homework-practice-04-IvanovIvan.ipynb). Модуль с кодом layers.py нужно отправить в Яндекс.Контест, а также ноутбук и layers.py в anytask.\n",
    "\n",
    "Для удобства проверки самостоятельно посчитайте свою максимальную оценку (исходя из набора решенных задач) и укажите ниже.\n",
    "\n",
    "Ссылка на яндекс.контест:\n",
    "\n",
    "1. МГУ: https://contest.yandex.ru/contest/7700/problems/\n",
    "2. ВШЭ: https://official.contest.yandex.ru/contest/7700/problems/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Оценка:** ...\n",
    "\n",
    "**Номер посылки в контесте:** ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Часть 1. Реализация слоёв графа вычислений\n",
    "\n",
    "В этом задании мы реализуем граф вычислений для задачи распознавания изображений рукописных цифр на примере датасета [MNIST](http://yann.lecun.com/exdb/mnist/) — в частности, эта часть посвящена реализации всех требующихся для построения графа слоёв.\n",
    "\n",
    "Указанная задача является задачей классификации на $K = 10$ классов, поэтому будем строить граф вычислений, выходной слой которого будет содержать 10 нейронов, $k$-ый из которых вычисляет оценку принадлежности объекта $k$-ому классу. В качестве функционала качества в данной задаче будем использовать **кросс-энтропию**:\n",
    "\n",
    "$$Q(a, X) = -\\frac{1}{l}\\sum_{i=1}^l \\sum_{k=1}^K [y_i = k] \\log a_k(x_i),$$\n",
    "где\n",
    "\n",
    "$X = \\{ (x_i, y_i)\\}_{i=1}^l, \\, y_i \\in \\{1, \\dots, K\\},$ — обучающая выборка,\n",
    "\n",
    "$a(x) = (a_k(x))_{k=1}^K \\in \\mathbb{R}^K$ — прогноз графа вычислений для объекта $x$, состоящий из выходов $K$ нейронов выходного слоя (т.е. $a_k(x)$ — оценка принадлежности объекта $x$ классу $k$, построенная при помощи заданного графа вычислений).\n",
    "\n",
    "Нейрнонные сети обучаются с использованием стохастических методов оптимизации, однако для ускорения обучения и большей стабильности за один проход параметры оптимизируются по батчу — набору из нескольких тренировочных примеров, так же batch_size является дополнительной размерностью для входящих в слой тензоров.\n",
    "\n",
    "Для начала определим класс Layer, реализующий тождественный слой, который будет являться базовым классом для всех последующих."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 1 (1 балл).**\n",
    "\n",
    "Используя приведенные прототипы, реализуйте слой, применяющий функцию активации ReLU (Rectified Linear Unit) поэлементно к каждому из входов слоя:\n",
    "$$\\text{ReLU}(z) = \\max (0, z)$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 2 (1 балл).**\n",
    "\n",
    "Используя указанные прототипы, реализуйте полносвязный слой, выход которого вычисляется следующим образом (подробнее в соответствующей [лекции](https://github.com/esokolov/ml-course-hse/blob/master/2017-fall/lecture-notes/lecture11-dl.pdf)):\n",
    "\n",
    "$$f(v; W, b)= Wv + b, $$\n",
    "\n",
    "где\n",
    "* v — выход предыдущего слоя (вектор размера num_inputs);\n",
    "* W — матрица весов [num_inputs, num_outputs];\n",
    "* b — столбец свободных членов (вектор размера num_outputs).\n",
    "\n",
    "При создании полносвязного слоя веса $W, \\; b$ необходимо проинициализировать веса с помощью GLOROT (какой именно вариант неважно). Про GLOROT можно прочитать здесь:\n",
    "1. Простой пост: http://andyljones.tumblr.com/post/110998971763/an-explanation-of-xavier-initialization\n",
    "2. Статья с математикой: http://proceedings.mlr.press/v9/glorot10a/glorot10a.pdf\n",
    "\n",
    "При каждом вызове backward() необходимо расчитать градиенты по выходу, используя chain-rule, и сделать один шаг градиентного спуска."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 3 (1 балл).**\n",
    "\n",
    "Как было сказано ранее, в качестве функционала качества в данной задаче мы будем использовать кросс-энтропию. Используя прототипы ниже, реализуйте вычисление данного функционала и его градиента по выходам графа вычислений.\n",
    "\n",
    "Кросс-энтропия предполагает, что модель для каждого объекта выдает вероятности принадлежности к каждому из $K$ классов, т.е. что для одного объекта все $K$ вероятностей неотрицательны и суммируются в 1. В нашем же случае в построении графа участвуют только полносвязный и ReLU слои, а потому выходы графа не являются вероятностями — как правило, в этом случае прогноз $a(x)$ модели нормируется при помощи функции softmax следующим образом:\n",
    "\n",
    "$$\\text{softmax}(a_k(x)) = \\frac{\\exp(a_k(x))}{\\sum_{k=1}^K \\exp(a_k(x))}.$$\n",
    "\n",
    "При реализации указанных функций предполагается, что переданные в качестве параметров оценки принадлежности объектов классам не являются нормированными (их еще называют логитами), но при вычислении указанных величин используйте указанное выше преобразование для приведения этих оценок к корректному виду."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Часть 2. Реализация и применение графа вычислений"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В этой части мы научимся объединять слои в единый граф вычислений, а также использовать его для прямого прохода (вычисления прогнозов на объектах) и обратного прохода (обновление обучаемых параметров графа), после чего у нас появится возможность обучить граф. Для простоты реализации будем считать, что в нашем случае граф вычислений задается как список (python list) слоёв из числа реализованных ранее."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ниже приведен код для скачивания датасета MNIST с официального сайта. Датасет делится на тренировочную и тестовую части. Тренировочная дополнительно разбивается на тренировочную и валидационную."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "import os\n",
    "import time\n",
    "import gzip\n",
    "from urllib.request import urlretrieve\n",
    "\n",
    "def load_mnist(flatten=False):\n",
    "    \"\"\"taken from https://github.com/Lasagne/Lasagne/blob/master/examples/mnist.py\"\"\"\n",
    "    # We first define a download function, supporting both Python 2 and 3.\n",
    "\n",
    "    def download(filename, source='http://yann.lecun.com/exdb/mnist/'):\n",
    "        print(\"Downloading %s\" % filename)\n",
    "        urlretrieve(source + filename, filename)\n",
    "\n",
    "    # We then define functions for loading MNIST images and labels.\n",
    "    # For convenience, they also download the requested files if needed.\n",
    "\n",
    "    def load_mnist_images(filename):\n",
    "        if not os.path.exists(filename):\n",
    "            download(filename)\n",
    "        # Read the inputs in Yann LeCun's binary format.\n",
    "        with gzip.open(filename, 'rb') as f:\n",
    "            data = np.frombuffer(f.read(), np.uint8, offset=16)\n",
    "        # The inputs are vectors now, we reshape them to monochrome 2D images,\n",
    "        # following the shape convention: (examples, channels, rows, columns)\n",
    "        data = data.reshape(-1, 1, 28, 28)\n",
    "        # The inputs come as bytes, we convert them to float32 in range [0,1].\n",
    "        # (Actually to range [0, 255/256], for compatibility to the version\n",
    "        # provided at http://deeplearning.net/data/mnist/mnist.pkl.gz.)\n",
    "        return data / np.float32(256)\n",
    "\n",
    "    def load_mnist_labels(filename):\n",
    "        if not os.path.exists(filename):\n",
    "            download(filename)\n",
    "        # Read the labels in Yann LeCun's binary format.\n",
    "        with gzip.open(filename, 'rb') as f:\n",
    "            data = np.frombuffer(f.read(), np.uint8, offset=8)\n",
    "        # The labels are vectors of integers now, that's exactly what we want.\n",
    "        return data\n",
    "\n",
    "    # We can now download and read the training and test set images and labels.\n",
    "    X_train = load_mnist_images('train-images-idx3-ubyte.gz')\n",
    "    y_train = load_mnist_labels('train-labels-idx1-ubyte.gz')\n",
    "    X_test = load_mnist_images('t10k-images-idx3-ubyte.gz')\n",
    "    y_test = load_mnist_labels('t10k-labels-idx1-ubyte.gz')\n",
    "\n",
    "    # We reserve the last 10000 training examples for validation.\n",
    "    X_train, X_val = X_train[:-10000], X_train[-10000:]\n",
    "    y_train, y_val = y_train[:-10000], y_train[-10000:]\n",
    "    \n",
    "    if flatten:\n",
    "        X_train = X_train.reshape([X_train.shape[0], -1])\n",
    "        X_val = X_val.reshape([X_val.shape[0], -1])\n",
    "        X_test = X_test.reshape([X_test.shape[0], -1])\n",
    "\n",
    "    # We just return all the arrays in order, as expected in main().\n",
    "    # (It doesn't matter how we do this as long as we can read them again.)\n",
    "    return X_train, y_train, X_val, y_val, X_test, y_test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посмотрим на несколько объектов из этого датасета."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "X_train, y_train, X_val, y_val, X_test, y_test = load_mnist(flatten=True)\n",
    "\n",
    "plt.figure(figsize=[6, 6])\n",
    "for i in range(4):\n",
    "    plt.subplot(2, 2, i+1)\n",
    "    plt.title(\"Label: %i\"%y_train[i])\n",
    "    plt.imshow(X_train[i].reshape([28, 28]),cmap='gray');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 4 (2 балла).**\n",
    "\n",
    "Используя прототип ниже, реализуйте прямой и обратный проход по графу вычислений и функцию для получения предсказаний метки класса."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class NeuralNetwork:\n",
    "    def __init__(self, layers):\n",
    "        \"\"\"\n",
    "        layers — list of Layer objects\n",
    "        \"\"\"\n",
    "        \n",
    "        this.layers = layers\n",
    "        \n",
    "    def forward(self, X):\n",
    "        \"\"\"\n",
    "        Compute activations of all network layers by applying them sequentially.\n",
    "        Return a list of activations for each layer. \n",
    "        Make sure last activation corresponds to network logits.\n",
    "        \"\"\"\n",
    "        \n",
    "        activations = []\n",
    "        input = X\n",
    "\n",
    "        raise NotImplementedError(\"Implement me plz ;(\")\n",
    "\n",
    "        assert len(activations) == len(self.layers)\n",
    "        return activations\n",
    "\n",
    "    def predict(self, X):\n",
    "        \"\"\"\n",
    "        Use network to predict the most likely class for each sample.\n",
    "        \"\"\"\n",
    "        \n",
    "        raise NotImplementedError(\"Implement me plz ;(\")\n",
    "        \n",
    "    def backward(self, X, y):\n",
    "        \"\"\"\n",
    "        Train your network on a given batch of X and y.\n",
    "        You first need to run forward to get all layer activations.\n",
    "        Then you can run layer.backward going from last to first layer.\n",
    "\n",
    "        After you called backward for all layers, all Dense layers have already made one gradient step.\n",
    "        \"\"\"\n",
    "\n",
    "        # Get the layer activations\n",
    "        layer_activations = self.forward(X)\n",
    "        layer_inputs = [X] + layer_activations  # layer_input[i] is an input for network[i]\n",
    "        logits = layer_activations[-1]\n",
    "\n",
    "        # Compute the loss and the initial gradient\n",
    "        loss = softmax_crossentropy_with_logits(logits, y)\n",
    "        loss_grad = grad_softmax_crossentropy_with_logits(logits, y)\n",
    "\n",
    "        # propagate gradients through network layers using .backward\n",
    "        # hint: start from last layer and move to earlier layers\n",
    "        raise NotImplementedError(\"Implement me plz ;(\")\n",
    "\n",
    "        return np.mean(loss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "layers = []\n",
    "hidden_layers_size = 40\n",
    "layers.append(Dense(X_train.shape[1], hidden_layers_size))\n",
    "layers.append(ReLU())\n",
    "layers.append(Dense(hidden_layers_size, hidden_layers_size))\n",
    "layers.append(ReLU())\n",
    "layers.append(Dense(hidden_layers_size, 10))\n",
    "\n",
    "model = NeuralNetwork(layers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Все готово для запуска обучения. Если все реализовано корректно, то точность классификации на валидационном множестве должна превысить 97%. \n",
    "\n",
    "Ниже определена функции для итерации по батчам, принимающая на вход картинки, матки классов, а также размер батча и флаг отвечающий за перемешивание примеров."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from tqdm import trange\n",
    "\n",
    "def iterate_minibatches(inputs, targets, batchsize, shuffle=False, seed=1234):\n",
    "    assert len(inputs) == len(targets)\n",
    "    \n",
    "    indices = np.arange(len(inputs)).astype(np.int32)\n",
    "    if shuffle:\n",
    "        np.random.seed(seed)\n",
    "        np.random.shuffle(indices)\n",
    "    \n",
    "    for start_idx in trange(0, len(inputs) - batchsize + 1, batchsize):\n",
    "        batch = indices[start_idx:start_idx + batchsize]\n",
    "        \n",
    "        yield inputs[batch], targets[batch]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ниже приведены функции для обучения модели и отслеживания значения loss на тренироворочной части и на валидации."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from IPython.display import clear_output\n",
    "train_log = []\n",
    "val_log = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for epoch in range(15):\n",
    "    for x_batch, y_batch in iterate_minibatches(X_train, y_train, batchsize=32, shuffle=True):\n",
    "        model.backward(x_batch, y_batch)\n",
    "    \n",
    "    train_log.append(np.mean(model.predict(X_train) == y_train))\n",
    "    val_log.append(np.mean(model.predict(X_val) == y_val))\n",
    "    \n",
    "    clear_output()\n",
    "    print(\"Epoch\", epoch)\n",
    "    print(\"Train accuracy:\", train_log[-1])\n",
    "    print(\"Val accuracy:\", val_log[-1])\n",
    "    plt.plot(train_log, label='train accuracy')\n",
    "    plt.plot(val_log, label='val accuracy')\n",
    "    plt.legend(loc='best')\n",
    "    plt.grid()\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Часть 3. Дополнительные слои"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В этой части предлагается реализовать сверточный слой и слой maxpooling, а также разработать свою архитектуру графа вычислений с их использованием для повышения качества на валидационной выборке.\n",
    "\n",
    "**Задание 6 (2 балла).** Реализуйте сверточный слой.\n",
    "\n",
    "Рассмотрим один сверточный слой. Пусть на вход поступает изображение $X^l$ с $channels$ каналами, а сверточный слой $W$ имеет размер $k_1 \\times k_2 \\times channels$. Тогда применение слоя можно выразить следующим образом:\n",
    "\n",
    "$$x_{ij}^{l} = \\sum_{m=0}^{k_1 - 1} \\sum_{n=0}^{k_2 - 1} \\sum_{c=0}^{channels} w_{m, n, c}^{l} x_{i+m, j+n, c}^{l-1}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 7 (1 балл).** Реализуйте слой макспулинга.\n",
    "\n",
    "Ниже, на картинке, можно увидеть пример применения операции макспулинга с ядром размера 2x2 (слой применяется раздельно для каждого канала изображения).\n",
    "\n",
    "<img src=\"https://cambridgespark.com/content/tutorials/convolutional-neural-networks-with-keras/figures/pool.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 8 (1 балл).** Реализуйте слой для перевода n-мерного тензора в матрицу. Данный слой понадобится вам после использования сверточных слоев для перевода четырехмерного тензора в матрицу и дальнейшего использования результата в полносвязном слое для предсказания ненормированных вероятностей классов."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 9 (1 балл).** Подберите архитектуру сети, используя сверточные слои и слои макспулинга и превзойдите качество полносвязной сети."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "layers = []\n",
    "model = NeuralNetwork(layers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from IPython.display import clear_output\n",
    "train_log = []\n",
    "val_log = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for epoch in range(15):\n",
    "    for x_batch,y_batch in iterate_minibatches(X_train, y_train, batchsize=32, shuffle=True):\n",
    "        model.backward(x_batch.reshape((-1, 1, 28, 28)), y_batch)\n",
    "    \n",
    "    train_log.append(np.mean(model.predict(X_train) == y_train))\n",
    "    val_log.append(np.mean(model.predict(X_val) == y_val))\n",
    "    \n",
    "    clear_output()\n",
    "    print(\"Epoch\", epoch)\n",
    "    print(\"Train accuracy:\", train_log[-1])\n",
    "    print(\"Val accuracy:\", val_log[-1])\n",
    "    plt.plot(train_log, label='train accuracy')\n",
    "    plt.plot(val_log, label='val accuracy')\n",
    "    plt.legend(loc='best')\n",
    "    plt.grid()\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Часть 4. Мемы"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 10 (0.2 балла).** Какой мем из уже прошедшего 2k17 года вам запомнился больше всего? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 11 (0.2 балла).** А какой из появившихся в 2k!8 вам понравился больше всего?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Задание 12 (0.2 балла).** А здесь напишите фидбек по заданию :)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}