inheritance_soln.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Inheritance\n",
    "\n",
    "This notebook demonstrates the use of inheritance to extend Python's `Counter` class to implement Multisets, PMFs, and suites of Bayesian hypotheses."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from __future__ import print_function, division\n",
    "\n",
    "from collections import Counter\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Counter\n",
    "\n",
    "A `Counter` is a map from values to their frequencies.  If you initialize a `Counter` with a string, you get a map from each letter to the number of times it appears.  If two words are anagrams, they yield equal Counters, so you can use Counters to test anagrams."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_anagram(word1, word2):\n",
    "    \"\"\"Checks whether the words are anagrams.\n",
    "\n",
    "    word1: string\n",
    "    word2: string\n",
    "\n",
    "    returns: boolean\n",
    "    \"\"\"\n",
    "    return Counter(word1) == Counter(word2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "is_anagram('tachymetric', 'mccarthyite')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "is_anagram('banana', 'peach')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** The `Counter` class inherits from `dict` so all methods and functions that work with a dictionary will also work with a `Counter`.\n",
    "\n",
    "Read [the documentation of Counter](https://docs.python.org/3/library/collections.html#collections.Counter), then use a `Counter` to find the three most common letters in the word \"pneumonoultramicroscopicsilicovolcanoconiosis\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution\n",
    "\n",
    "Counter('pneumonoultramicroscopicsilicovolcanoconiosis').most_common(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Multisets\n",
    "\n",
    "A `Counter` is a natural representation of a multiset, which is a set where the elements can appear more than once.\n",
    "You could use multisets for a game like Scrabble to see if a given set of tiles can be used to spell a given word.\n",
    "\n",
    "**Exercise:** Write a definition for a class called `Multiset` that inherits from `Counter` and defines an additional method called `is_subset`, which should take `self` and `other` as parameters, where `other` is another `Multiset`.\n",
    "\n",
    "It should check whether `self` is a subset of `other`; for multisets, that means that every element of `self` appears in `other` with at least the same frequency.  For example, `aa` is a subset of `aaab`, but `aabb` is not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Solution\n",
    "\n",
    "class Multiset(Counter):\n",
    "    \"\"\"A multiset is a set where elements can appear more than once.\"\"\"\n",
    "\n",
    "    def is_subset(self, other):\n",
    "        \"\"\"Checks whether self is a subset of other.\n",
    "\n",
    "        other: Multiset\n",
    "\n",
    "        returns: boolean\n",
    "        \"\"\"\n",
    "        for char, count in self.items():\n",
    "            if other[char] < count:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following function uses `Multiset.is_subset` to check whether a particular word can be spelled using a particular set of tiles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def can_spell(word, tiles):\n",
    "    \"\"\"Checks whether a set of tiles can spell a word.\n",
    "\n",
    "    word: string\n",
    "    tiles: string\n",
    "\n",
    "    returns: boolean\n",
    "    \"\"\"\n",
    "    return Multiset(word).is_subset(Multiset(tiles))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "can_spell('SYZYGY', 'AGSYYYZ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "can_spell('omelette', 'breaking a few eggs')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Optional Exercise:**  If you change the name of `is_subset` to `__le__`, you can use the `<=` operator to test whether one `Multiset` is a subset of another."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Probability Mass Functions\n",
    "\n",
    "You can also extend `Counter` to represent a probability mass function (PMF).  A PMF is a map from possible outcomes to their probabilities.  The probabilities in a PMF are \"normalized\" if they add up to 1 (and they are all non-negative).\n",
    "\n",
    "The following `PMF` class inherits from `Counter` and adds the following methods:\n",
    "\n",
    "* `normalize` computes the total of the frequencies and divides through, yielding probabilities that add to 1.\n",
    "\n",
    "* `__add__` enumerates all pairs of outcomes and returns a new Pmf that represents the distribution of the sum.\n",
    "\n",
    "* `render` returns the outcomes and probabilities in a form ready for plotting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Pmf(Counter):\n",
    "    \"\"\"A Counter with probabilities.\"\"\"\n",
    "\n",
    "    def normalize(self):\n",
    "        \"\"\"Normalizes the PMF so the probabilities add to 1.\"\"\"\n",
    "        total = sum(self.values())\n",
    "        for key in self:\n",
    "            self[key] /= total\n",
    "\n",
    "    def __add__(self, other):\n",
    "        \"\"\"Adds two distributions.\n",
    "\n",
    "        The result is the distribution of sums of outcomes from the\n",
    "        two distributions.\n",
    "        \n",
    "        Note that this method is only correct if the selections from\n",
    "        the two distributions are independent; that is, if the outcome\n",
    "        of the first selection does not affect the probabilities of\n",
    "        the outcomes for the second selection.\n",
    "\n",
    "        other: Pmf\n",
    "\n",
    "        returns: new Pmf\n",
    "        \"\"\"\n",
    "        pmf = Pmf()\n",
    "        for key1, prob1 in self.items():\n",
    "            for key2, prob2 in other.items():\n",
    "                pmf[key1 + key2] += prob1 * prob2\n",
    "        return pmf\n",
    "\n",
    "    def render(self):\n",
    "        \"\"\"Returns outcomes and their probabilities, suitable for plotting.\"\"\"\n",
    "        return zip(*sorted(self.items()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As an example, we can make a Pmf object that represents a 6-sided die."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d6 = Pmf([1,2,3,4,5,6])\n",
    "d6.normalize()\n",
    "d6.name = 'one die'\n",
    "print(d6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the add operator, we can compute the distribution for the sum of two dice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d6_twice = d6 + d6\n",
    "d6_twice.name = 'two dice'\n",
    "\n",
    "for key, prob in d6_twice.items():\n",
    "    print(key, prob)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using `sum` or `np.sum`, we can compute the distribution for the sum of three dice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# if we use the built-in sum we have to provide a Pmf additive identity\n",
    "pmf_ident = Pmf([0])\n",
    "d6_thrice = sum([d6]*3, pmf_ident)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# with np.sum, we don't need an identity\n",
    "d6_thrice = np.sum([d6]*3)\n",
    "d6_thrice.name = 'three dice'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And then plot the results (using Pmf.render)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for die in [d6, d6_twice, d6_thrice]:\n",
    "    xs, ys = die.render()\n",
    "    plt.plot(xs, ys, label=die.name, linewidth=3, alpha=0.5)\n",
    "    \n",
    "plt.xlabel('Total')\n",
    "plt.ylabel('Probability')\n",
    "plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Suppose you are fighting an orc who will die if he suffers 9 or more hit points of damage.  You attack successfully with [short sword](https://roll20.net/compendium/dnd5e/Shortsword#content) and [dagger](https://roll20.net/compendium/dnd5e/Dagger#content), so you can roll a d6 and a d4 for total damage.  What is the probability that you kill the orc?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution\n",
    "\n",
    "d4 = Pmf([1,2,3,4])\n",
    "d4.normalize()\n",
    "hp = d6 + d4\n",
    "hp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution\n",
    "\n",
    "hp[9] + hp[10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bayesian statistics\n",
    "\n",
    "A `Suite` is a `Pmf` that represents a set of hypotheses and their probabilities; it provides `bayesian_update`, which updates the probability of the hypotheses based on new data.\n",
    "\n",
    "`Suite` is an abstract parent class; child classes should provide a `likelihood` method that evaluates the likelihood of the data under a given hypothesis.  `update_bayesian` loops through the hypotheses, evaluates the likelihood of the data under each hypothesis, and updates the probabilities accordingly.  Then it re-normalizes the PMF."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Suite(Pmf):\n",
    "    \"\"\"Map from hypothesis to probability.\"\"\"\n",
    "\n",
    "    def bayesian_update(self, data):\n",
    "        \"\"\"Performs a Bayesian update.\n",
    "        \n",
    "        Note: called bayesian_update to avoid overriding dict.update\n",
    "\n",
    "        data: result of a die roll\n",
    "        \"\"\"\n",
    "        for hypo in self:\n",
    "            like = self.likelihood(data, hypo)\n",
    "            self[hypo] *= like\n",
    "\n",
    "        self.normalize()\n",
    "        \n",
    "    def print_probs(self):\n",
    "        for hypo in sorted(self):\n",
    "            print(hypo, self[hypo])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As an example, I'll use `Suite` to solve the \"Dice Problem,\" from Chapter 3 of <i>Think Bayes</i>.\n",
    "\n",
    "\"Suppose I have a box of dice that contains a 4-sided die, a 6-sided die, an 8-sided die, a 12-sided die, and a 20-sided die. If you have ever played Dungeons & Dragons, you know what I am talking about.  Suppose I select a die from the box at random, roll it, and get a 6. What is the probability that I rolled each die?\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'll start by defining `DiceSuite`, which inherits `bayesian_update` from Suite and provides `likelihood`.\n",
    "\n",
    "`data` is the observed die roll, 6 in the example.\n",
    "\n",
    "`hypo` is the hypothetical number of sides on the die.\n",
    "\n",
    "If `data > hypo`, that means the outcome exceeds the number of sides on the die; that's impossible, so it has probability 0.\n",
    "\n",
    "Otherwise, the probability of any outcome is `1/hypo`, where `hypo` is the number of sides on the die."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class DiceSuite(Suite):\n",
    "    \n",
    "    def likelihood(self, data, hypo):\n",
    "        \"\"\"Computes the likelihood of the data under the hypothesis.\n",
    "\n",
    "        data: result of a die roll\n",
    "        hypo: integer number of sides on the die\n",
    "        \"\"\"\n",
    "        if data > hypo:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1/hypo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can make a `DiceSuite` object that represents the possible number of sides on the die. By default, all dice have the same prior probability.\n",
    "\n",
    "Then I update the distribution with the given outcome and print the results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dice_suite = DiceSuite([4, 6, 8, 12, 20])\n",
    "dice_suite.normalize()\n",
    "\n",
    "dice_suite.print_probs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dice_suite.bayesian_update(6)\n",
    "\n",
    "dice_suite.print_probs()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected, the 4-sided die has been eliminated; it now has 0 probability.  The 6-sided die is the most likely, but the 8-sided die is still quite possible.\n",
    "\n",
    "Now suppose I roll the die again and get an 8.  We can update the Suite again with the new data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dice_suite.bayesian_update(8)\n",
    "\n",
    "dice_suite.print_probs()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now the 6-sided die has been eliminated, the 8-sided die is most likely, and there is less than a 10% chance that I am rolling a 20-sided die.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Draw a UML class diagram that shows the relationships among all classes in this notebook, plus `Counter` and `dict`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Suppose you know that up to 100 sequentially-numbered raffle tickets have been sold, and you think it is equally likely that the number sold is anywhere from 1 to 100.  You find a randomly discarded ticket that is number 37.  What is the probability that it is the winning ticket?\n",
    "\n",
    "Hint: Define a class named `TicketSuite` that inherits from `Suite` and provides an appropriate `likelihood` function.  It should also define a method that computes the average probability of winning, weighted by the probability of each outcome.\n",
    "\n",
    "Note: This exercise is pretty challenging if you are not familiar with Bayesian statistics.  But if it intrigues you, consider taking Computational Bayesian Statistics."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Solution\n",
    "\n",
    "class TicketSuite(Suite):\n",
    "    \n",
    "    def likelihood(self, data, hypo):\n",
    "        \"\"\"Computes the likelihood of the data under the hypothesis.\n",
    "\n",
    "        data: result of a die roll\n",
    "        hypo: integer number of sides on the die\n",
    "        \"\"\"\n",
    "        if data > hypo:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1/hypo\n",
    "        \n",
    "    def weighted_average(self):\n",
    "        \"\"\"Compute the probability of winning.\n",
    "        \n",
    "        If the number of tickets is hypo, the probability of\n",
    "        winning is 1/hypo.\n",
    "        \"\"\"\n",
    "        total = 0\n",
    "        for hypo, prob in self.items():\n",
    "            total += prob / hypo\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution\n",
    "\n",
    "ts = TicketSuite(range(1, 101))\n",
    "ts.bayesian_update(37)\n",
    "\n",
    "xs, ys = ts.render()\n",
    "plt.plot(xs, ys, linewidth=3, alpha=0.5)\n",
    "    \n",
    "plt.xlabel('Number of tickets')\n",
    "plt.ylabel('Probability')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution\n",
    "\n",
    "ts.weighted_average()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}