KL_divergence.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Table of Contents\n",
    "1. [Definition Kullback Leibler divergence](#definition)\n",
    "2. [Illustrated Example](#visual-example)\n",
    "3. [KL divergence in machine learning](#kl-in-ml)\n",
    "4. [Interpreting the Kullback Leibler divergence](#interpreting-the-kullback-leibler-divergence)     \n",
    "    4.1. Expected value of a function     \n",
    "    4.2. Ratio p(x)/q(x)     \n",
    "    4.3. Log ratio  \n",
    "    4.4. Example calculation\n",
    "    4.5. Log ratio vs. KL divergence\n",
    "5. [Why is the KL divergence always non-negative?](#non-negativity)\n",
    "6. [Which type of logarithm should be used?](#log-type)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Definition <a class=\"anchor\" id=\"definition\"></a>\n",
    "\n",
    "\n",
    "The KL-divergence is a measure of how similar (or different) two probablity distributions are. When having a discrete probability distribution $P$ and another probability distribution $Q$ the KL-divergence for a set of points $X$ is defined as:\n",
    "\n",
    "$D_{KL}(P \\,|| \\,Q) = \\sum_{x \\in X} P(x) \\log \\big( \\frac{P(x)}{Q(x)} \\big)$\n",
    "\n",
    "For probability distributions over continuous variables the sum turns into an integral:\n",
    "\n",
    "$ D_{KL}(P \\,|| \\,Q) = \\int_{-\\infty}^{\\infty} p(x) \\log \\big( \\frac{p(x)}{q(x)} \\big) dx$\n",
    "\n",
    "where $p$ and $q$ denote the probability density functions of $P$ and $Q$.\n",
    "\n",
    "[Source](https://en.wikipedia.org/wiki/Kullback_Leibler_divergence)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visual example <a class=\"anchor\" id=\"visual-example\"></a>\n",
    "\n",
    "The [Wikipedia entry](https://en.wikipedia.org/wiki/Kullback–Leibler_divergence) on the KL divergence contains a nice illustration:\n",
    "\n",
    "<img src=\"kl_divergence.png\" width=\"700\" />\n",
    "\n",
    "On the left hand side we can see two Gaussian probability density functions $p(x)$ and $q(x)$. The right hand side show the area that is integrated when computing the KL divergence from $p$ to $q$. We know that:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "D_{KL}(P \\,|| \\,Q) &= \\int_{-\\infty}^{\\infty} p(x) \\log \\big( \\frac{p(x)}{q(x)} \\big) dx \\\\\n",
    "&= \\int_{-\\infty}^{\\infty} p(x) \\big( \\log p(x) - \\log q(x) \\big) dx\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "So for each point $x_i$ on the x-axis, we compute $\\log p(x_i) - \\log q(x_i)$ and multiply the result by $p(x_i)$. We then plot the resulting y-value in the right hand plot. This is how we get to the curve given in the right hand plot. The KL divergence is now defined as the *area under the graph*, which is shaded."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## KL divergence in machine learning <a class=\"anchor\" id=\"kl-in-ml\"></a>\n",
    "\n",
    "In most cases in machine learning we are given a dataset $X$ which was generated by some unknown probability distribution $P$. In this approach $P$ is considered to be the *target distribution* (that is, the 'true' distribution) which we are trying to approximate using a distribution $Q$. We can evaluate candidate distributions $Q$ using the KL-divergence from $P$ to $Q$. In many cases, for example in variational inference, the KL divergence is used as an optimization criterion which is minimized in order to find the best candidate/approximation $Q$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interpreting the Kullback Leibler divergence <a class=\"anchor\" id=\"interpreting-the-kullback-leibler-divergence\"></a>\n",
    "\n",
    "Note: Several different intepretations of the KL divergence exist. This interpretation describes a probabilistic perspective which is often useful for machine learning.\n",
    "\n",
    "### Expected value\n",
    "In order to understand how the KL divergence works, remember the formula for the **expected value of a function**. Given a function $f$ with $x$ being a discrete variable, the expected value of $f(x)$ is defined as    \n",
    "     \n",
    "$\\mathbb{E}\\big[f(x)\\big] = \\sum_x f(x) p(x)$\n",
    "\n",
    "where $p(x)$ is the probability density function of the variable $x$. For the continuous case we have\n",
    "\n",
    "$\\mathbb{E}\\big[f(x)\\big] = \\int_{-\\infty}^{\\infty}f(x) p(x) dx$.\n",
    "\n",
    "\n",
    "> **Example:** Suppose you made a very good deal and bought three pairs of the best headphones for a reduced price of \\$200 each. You want to sell them for \\$350 each. We define the probability of selling $X=0, X=1, X=2, X=3$ headphones as follows:     \n",
    "   \n",
    "> $p(X=0) = 0.1, \\, p(X=1) = 0.2, \\, p(X=3) = 0.3, \\, p(X=4) = 0.4$.     \n",
    "\n",
    "> We further define a function that measures profit: $f(x) = revenue - cost = 350*X - 200*X$. For example, when selling two pairs of headphones you will make: $f(X=2) = 700 - 400 = \\$300$.\n",
    "\n",
    "> So what's our expected profit? We can compute it using the formula for the expected value:    \n",
    "$$\n",
    "\\begin{align}\n",
    "\\mathbb{E}\\big[f(x)\\big] &= p(X=0)*f(X=0) + p(X=1)*f(X=1) + p(X=2)*f(X=2) + p(X=3)*f(X=3) \\\\    \n",
    "&= 0.1 * 0 + 0.2 * 150 + 0.3 * 300 + 0.4 * 450 \\\\     \n",
    "&= \\$ 300      \n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ratio of p(x) / q(x)\n",
    "\n",
    "Looking back at the definition of the KL divergence we can see that it's quite similar to the definition of the expected value. When setting $f(x) = \\log \\big(\\frac{p(x)}{q(x)}\\big)$ we can see that: \n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\mathbb{E}\\big[f(x)\\big] &= \\mathbb{E}_{x \\sim p(x)}\\big[\\log \\big(\\frac{p(x)}{q(x)}\\big) \\big] \\\\\n",
    "&= \\int_{-\\infty}^{\\infty} p(x) \\log \\big( \\frac{p(x)}{q(x)} \\big) dx \\\\\n",
    "&= D_{KL}(P \\,|| \\,Q)\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "But what does that mean? Let's start by looking at the quantity $\\frac{p(x)}{q(x)}$. When having some probability density function $p$ and another probability density function $q$ we can compare the two by looking at the ratio of the two densities:\n",
    "\n",
    "$ratio = \\frac{p(x)}{q(x)}$\n",
    "\n",
    "> **<span style=\"color:green\"> Insight</span>:** We can compare two probability density functions by means of the ratio.\n",
    "\n",
    "Because both $p(x)$ and $q(x)$ are probability densities they output values between $0$ and $1$. When $q$ is similar to $p$, $q(x)$ should output values close to $p(x)$ for any input $x$.  \n",
    "\n",
    "> ***Example:*** For some input $x_i$, $p(x_i)$ might be 0.78, i.e. $p(x_i) = 0.78$. Let's look at different densities $q$:    \n",
    "\n",
    "> a) If $q$ and $p$ are identical, $q(x)$ would output the same value and the resulting ratio would be one:   \n",
    "$ratio = \\frac{p(x)}{q(x)} = \\frac{0.78}{0.78} = 1$   \n",
    "     \n",
    "> b) When $q(x)$ assigns a lower probability to the input $x$ than $p(x)$, the resulting ratio will be larger than one:   \n",
    "$ratio = \\frac{p(x)}{q(x)} = \\frac{0.78}{0.2} = 3.9$    \n",
    "\n",
    "> c) When $q(x)$ assigns a higher probability to the input $x$ than $p(x)$, the resulting ratio will be smaller than one:    \n",
    "$ratio = \\frac{p(x)}{q(x)} = \\frac{0.78}{0.9} \\approx 0.86$\n",
    "\n",
    "The example provides an important insight:\n",
    "> **<span style=\"color:green\"> Insight</span>:** For any input $x$ the value of the ratio tells us how much more likely $x$ is to occur under $p(x)$ compared to $q(x)$. A value of the ratio larger than 1 indicates that $p(x)$ is the more likely model. A value smaller than 1 indicates that $q$ is the more likely model."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ratio for entire dataset\n",
    "If we have a whole dataset $X = x_1, ..., x_n$ we can compute the ratio of the entire set by taking the product over the individual ratios. Note: this only holds if the examples $x_i$ are independent of each other.\n",
    "\n",
    "$ratio = \\prod_{i=1}^n \\frac{p(x_i)}{q(x_i)}$\n",
    "\n",
    "To make the computation easier we can take the logarithm:\n",
    "\n",
    "$\\text{log_ratio} = \\sum_{i=1}^n \\log \\big( \\frac{p(x_i)}{q(x_i)} \\big)$\n",
    "\n",
    "When taking the logarithm, a log ratio value of 0 indicates that both models fit the data equally well. Values larger than 0 indicate that $p$ is the better model, that is, it fits the data better. Values smaller than 0 indicate that $q$ is the better model:\n",
    "\n",
    "<img src=\"new_log_ratio.jpg\" width=\"700\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example calculation\n",
    "\n",
    "Let's calculate the KL divergence for our headphone example. We already have specified a distribution $P$ over the possible outcomes. Let's define another distribution $Q$ which expresses our belief that it's very likely that we sell all three pairs of headphones and less likely that we don't sell all of them (or none).\n",
    "\n",
    "|  Distribution |  $X = 0 \\quad$ | $X=1 \\quad$ |$X=2 \\quad$ |$X=3 \\quad$ |   \n",
    "| :-----------: |:-----------:| :-----------:|:-----------:|:-----------:|\n",
    "| $P(X)$        | 0.1         | 0.2   | 0.3   | 0.4   |\n",
    "| $Q(X)$        | 0.1         |   0.1 | 0.1   | 0.7   |\n",
    "\n",
    "\n",
    "How similar are $P$ and $Q$? Let's compute the KL divergence:\n",
    "$$\n",
    "\\begin{align}\n",
    "D_{KL}(P \\,|| \\,Q) &= \\sum_{x \\in X} P(x) \\log \\big( \\frac{P(x)}{Q(x)} \\big)\\\\      \n",
    "&= 0.1 * \\log \\big( \\frac{0.1}{0.1} \\big) + 0.2 * \\log \\big( \\frac{0.2}{0.1} \\big) + 0.3 * \\log \\big( \\frac{0.3}{0.1} \\big) + 0.4 * \\log \\big( \\frac{0.4}{0.7} \\big)\\\\     \n",
    "&\\approx 0.244\n",
    "\\end{align}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ratio vs. KL-divergence\n",
    "\n",
    "We discovered that the log-ratio can be used to compare two probabilty densities $p$ and $q$. The KL divergence is nothing else than the expected value of the log-ratio. When setting $f(x) = \\log \\big(\\frac{p(x)}{q(x)}\\big)$ we receive:\n",
    "\n",
    "$\\mathbb{E}\\big[f(x)\\big] = \\mathbb{E}_{x \\sim p(x)}\\big[\\log \\big(\\frac{p(x)}{q(x)}\\big) \\big] = \\int_{-\\infty}^{\\infty} p(x) \\log \\big( \\frac{p(x)}{q(x)} \\big) dx = D_{KL}(P \\,|| \\,Q)$\n",
    "\n",
    "> **<span style=\"color:green\"> Insight</span>:** The KL divergence is simply the expected value of the log-ratio of the entire dataset."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Why is the KL divergence always non-negative? <a class=\"anchor\" id=\"non-negativity\"></a>\n",
    "\n",
    "An important property of the KL divergence is that it's always non-negative, i.e. $D_{KL}(P \\, || \\, Q) \\ge 0$ for any valid $P, Q$. We can prove this using [Jensen's inequality](https://en.wikipedia.org/wiki/Jensen%27s_inequality).\n",
    "\n",
    "Jensen's inequality states that, if a function $f(x)$ is convex, then   \n",
    "\n",
    "$\\mathbb{E}[f(x)] \\ge f(\\mathbb{E}[x])$\n",
    "     \n",
    "     \n",
    "    \n",
    "To show that $D_{KL}(P \\, || \\, Q) \\ge 0$ we first make use of the expected value:\n",
    "\n",
    "$D_{KL}(P \\,|| \\,Q) = \\int_{-\\infty}^{\\infty} p(x) \\log \\big( \\frac{p(x)}{q(x)} \\big) dx = \\mathbb{E}_{x \\sim p(x)}\\big[\\log \\big(\\frac{p(x)}{q(x)}\\big) \\big] = - \\mathbb{E}_{x \\sim p(x)}\\big[\\log \\big(\\frac{q(x)}{p(x)}\\big) \\big]$\n",
    "\n",
    "Because $-\\log(x)$ is a convex function we can apply Jensen's inequality:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "- \\mathbb{E}_{x \\sim p(x)}\\big[\\log \\big(\\frac{q(x)}{p(x)}\\big) \\big] &\\ge - \\log \\big( \\mathbb{E}_{x \\sim p(x)}\\big[\\frac{q(x)}{p(x)} \\big] \\big)\\\\    \n",
    "&= - \\log \\big( \\int_{-\\infty}^{\\infty} p(x) \\frac{q(x)}{p(x)} dx \\big) \\\\   \n",
    "&= - \\log \\big( \\int_{-\\infty}^{\\infty} q(x) dx \\big)\\\\     \n",
    "&= - \\log(1) \\\\\n",
    "&= 0\n",
    "\\end{align}\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Which type of logarithm to use <a class=\"anchor\" id=\"log-type\"></a>\n",
    "\n",
    "It's interesting to note that we can use different bases for the logarithm in the definition of the KL divergence, depending on the interpretation. For example, when using the natural logarithm the result of the KL divergence is measured in so called 'nats'. When using the logarithm to base 2 the result is measured in bits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}