130-recurrent-networks.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Populating the interactive namespace from numpy and matplotlib\n"
     ]
    }
   ],
   "source": [
    "%pylab inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "lines_to_next_cell": 2,
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import torch\n",
    "from torch import nn\n",
    "from torchmore import layers, flex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# SEQUENCE MODELING AND RECURRENT NETWORKS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Recurrent Networks\n",
    "\n",
    "Consider a sequence of samples: $x_t$ for $t \\in \\{0...n\\}$\n",
    "Want to produce an output sequence $y_t$\n",
    "\n",
    "Convolutional/TDNN models: \n",
    "\n",
    "$$y_t = f(x_{t},...,x_{t-k})$$\n",
    "\n",
    "Recurrent Models:\n",
    "\n",
    "$$y_t = f(x_t, y_{t-1})$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Recurrent Networks vs Linear Filters\n",
    "\n",
    "Recurrent neural networks are generalizations of IIR linear filters.\n",
    "\n",
    "Finite Impulse Response Filter\n",
    "\n",
    "$$ y_i = L(x_{i}, ..., x_{i-k})$$\n",
    "\n",
    "Infinite Impulse Response Filter\n",
    "\n",
    "$$ y_i = L(x_{i-1}, x_i) $$\n",
    "\n",
    "$L$: linear function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Simple Recurrent Model\n",
    "\n",
    "<img src=\"figs/simple-recurrent.png\" style=\"height: 5in\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Unrolling and Vanishing Gradient\n",
    "\n",
    "<img src=\"figs/simple-recurrent-unrolling.png\" style=\"height: 5in\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# LSTM as Memory Cell\n",
    "\n",
    "![lstm motivation](figs/lstm-motivation.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# LSTM Networks\n",
    "\n",
    "LSTMs are a particular form of recurrent neural network.\n",
    "\n",
    "Output computation ($L_s$ uses $\\tanh$):\n",
    "\n",
    "state: $s_t = f_t \\odot s_{t-1} + i_t \\odot L_s(x_t, y_{t-1})$\n",
    "\n",
    "output: $y_t = o_t \\odot s_t$\n",
    "\n",
    "$f_t$, $i_t$, and $o_t$ are gates (linear layers, sigmoidal output), $L_s$ is a linear layer with $\\tanh$ output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Bidirectional LSTM\n",
    "\n",
    "![bidirectional lsmt](figs/bdlstm.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# LSTM for OCR (simple)\n",
    "\n",
    "<img src=\"figs/breuel-lstm-scan.png\" style=\"height: 3in\" />\n",
    "\n",
    "Simple approach to OCR with LSTM:\n",
    "- assume a W x H x 1 input image\n",
    "- consider this a sequence of W vectors of dimension H\n",
    "- use these vectors as input to a (BD)LSTM\n",
    "- perform CTC alignment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# LSTM for OCR (simple)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "lines_to_next_cell": 2
   },
   "outputs": [],
   "source": [
    "def make_model():\n",
    "    return nn.Sequential(\n",
    "        layers.Input(\"BDHW\", sizes=[None, 1, 48, None]),\n",
    "        layers.Reshape(0, [1, 2], 3),\n",
    "        layers.Reorder(\"BDL\", \"LBD\"),\n",
    "        layers.LSTM(100)\n",
    "    )\n",
    "\n",
    "def train_batch(input, target):\n",
    "    optimizer.zero_grad()\n",
    "    output = model(input)\n",
    "    loss = ctc_loss(output, target)\n",
    "    loss.backward()\n",
    "    optimizer.step()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# LSTM for OCR (simple)\n",
    "\n",
    "- does not work for unconstrained inputs\n",
    "- works well for size and position normalized inputs\n",
    "- works much like an HMM model for OCR\n",
    "\n",
    "Breuel, Thomas M., et al. \"High-performance OCR for printed English and Fraktur using LSTM networks.\" 2013 12th International Conference on Document Analysis and Recognition. IEEE, 2013."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Size/Position Normalization for LSTM OCR\n",
    "\n",
    "![normalization example](figs/normalization-example.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Size/Position Normalization\n",
    "\n",
    "For binary word images:\n",
    "\n",
    "- pick a target image height $h$\n",
    "- find the centroid $\\mu$ and the covariance matrix $\\Sigma$ of the pixels\n",
    "- compute an affine transform that:\n",
    "  - moves $\\mu_y$ to $h/2$\n",
    "  - scales $\\Sigma_{yy}^{1/2}$ to $h/2$\n",
    "\n",
    "More complex:\n",
    "- grayscale images $\\rightarrow$ simple thresholding first\n",
    "- long lines $\\rightarrow$ compute $\\mu_y$ and $\\Sigma_{yy}$ in overlapping windows for each $x$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Word/Line Recognition with Size Normalization\n",
    "\n",
    "Word image normalization can go into the dataloader's data transformations (or be precomputed):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "transforms = [\n",
    "    lambda image: size_normalize(image),\n",
    "    lambda transcript: encode_text(transcript)\n",
    "]\n",
    "\n",
    "def make_loader():\n",
    "    return DataLoader(WebDataset(..., transforms=transforms))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "\n",
    "# Combining Convolutional Nets with LSTM\n",
    "\n",
    "\n",
    "We can easily combine convolutional layers with LSTM:\n",
    "\n",
    "- 2D convolutional network for preprocessing\\\n",
    "- reduction to 1D sequence\n",
    "- 1D LSTM modeling\n",
    "\n",
    "Breuel, Thomas M., et al. \"High-performance OCR for printed English and Fraktur using LSTM networks.\" 2013 12th International Conference on Document Analysis and Recognition. IEEE, 2013."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Combining Convolutional Nets with LSTM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "lines_to_next_cell": 2,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "def make_model():\n",
    "    return nn.Sequential(\n",
    "        *convnet_layers(),\n",
    "        layers.Fun(\"lambda x: x.sum(2)\"), # BDHW -> BDW\n",
    "        layers.Reorder(\"BDL\", \"LBD\"),\n",
    "        flex.LSTM(d, bidirectional=True, num_layers=num_layers),\n",
    "        layers.Reorder(\"LBD\", \"BDL\"),\n",
    "        flex.Conv1d(noutput, 1),\n",
    "        layers.Reorder(\"BDL\", \"BLD\")\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "Breuel, Thomas M. \"High performance text recognition using a hybrid convolutional-lstm implementation.\" 2017 14th IAPR International Conference on Document Analysis and Recognition (ICDAR). Vol. 1. IEEE, 2017."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Projection Options\n",
    "\n",
    "Going from \"BDHW\" image to \"BDL\" sequence, we have several options:\n",
    "\n",
    "- `x.sum(2), x.max(2)`\n",
    "    - position/scale independent\n",
    "- `Reshape(0, [1, 2], 3)`\n",
    "    - position dependent, after normalization\n",
    "- `BDHW_to_BDL_LSTM`\n",
    "    - trainable reduction, works either position dependent or independent\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lines_to_next_cell": 0,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Reduction with LSTM\n",
    "\n",
    "Reduction with LSTM is similar to seq2seq models: it reduces an entire sequence (pixel rows or columns in this case) to a final state vector."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "lines_to_next_cell": 2,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "class BDHW_to_BDL_LSTM(nn.Module):\n",
    "    ...\n",
    "    def forward(self, img):\n",
    "        b, d, h, w = img.size()\n",
    "        seq = layers.reorder(img, \"BDHW\", \"WBHD\").view(w, b*h, d)\n",
    "        out, (_, final) = self.lstm(seq)\n",
    "        return layers.reorder(final.view(b, h, noutput), \"BHD\", \"BDH\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Chinese Menu Style Text Recognition\n",
    "\n",
    "- **input**: normalized, word normalized, line normalized\n",
    "- **convolutional** layers: VGG-like, Resnet-like, FMP, U-net-like\n",
    "- **scaling layers**: none, interpolation, transposed convolution\n",
    "- **reduction**: sum, max, concat/reshape, LSTM\n",
    "- **sequence modeling**: none, LSTM, 2D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# What should you use?\n",
    "\n",
    "Some rules of thumbs:\n",
    "\n",
    "- sum/max/LSTM reduction with unnormalized, concat/LSTM with normalized\n",
    "- normalized + convolution + LSTM: good for printed Western OCR\n",
    "- unnormalized + convolution + LSTM: scene text, handwriting\n",
    "- unnormalized + convolution: faster scene text, lower performance\n",
    "\n",
    "Large literature trying many different combinations of these."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Which is \"best\"?\n",
    "\n",
    "Results depend on many factors:\n",
    "\n",
    "- character set: #classes, fonts, etc.\n",
    "- dataset: noise/degradation, distortions, etc.\n",
    "- training set size and variability\n",
    "- available training and inference hardware\n",
    "- precise architecture choice\n",
    "- training schedule and method\n",
    "- best method depends on application"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "jupytext": {
   "cell_metadata_filter": "-all",
   "formats": "ipynb",
   "main_language": "python"
  },
  "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}