lab2_answered.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Simulating Language, Lab 2, Word learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are going to start with a very simple model, of a Bayesian learner learning the meaning of a single word. This model is a simplification of the model in Tenenbaum (2000), which is a simpler version of the model in Xu & Tenenbaum (2007): in other words, it's pretty simple, but allows us to illustrate some of the same principles. It's also our first Bayesian model, so if you haven't seen one of these before then starting with a relatively simple one will help!\n",
    "\n",
    "## Representing word meanings\n",
    "\n",
    "We are going to assume that the meaning of a word is the set of things that word refers to, and to make things even easier for ourselves, we are going to model \"things that words refer to\" as numbers. So a word meaning is just a set of numbers, representing the set of entities that the word can be used to refer to. \n",
    "\n",
    "Python gives us some handy notation for dealing with sets: sets look a bit like lists, but they are enclosed in curly brackets, they are unordered, and they can't contain duplicates. So the following code represents (in python) the meaning of a word which can be used to refer to three things, entities 1, 2 and 7. \n",
    "\n",
    "```python\n",
    "word_meaning = {1,2,7}\n",
    "```\n",
    "You'll have to use your imagination to decide what entities 1, 2 and 7 are! Maybe this word is a noun and these are the objects in the world it can refer to, or maybe it's a verb and these are actions it can be used to describe. \n",
    "\n",
    "Using this notation, how would you represent a word with a very specific meaning, referring only to entity 99? How would you represent the meaning of a word that refers to entities 0, 1, 2, 3, and 4? What happens if you try to create a word meaning that contains a duplicate entity?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0, 1, 2}"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "specific_meaning = {99}\n",
    "other_meaning = {0,1,2,3,4}\n",
    "meaning_with_duplicate = {0,2,1,2}\n",
    "meaning_with_duplicate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Main thing to note here is that when you try to define a set that contains a duplicate, it just ignores and removes the duplicate. Note that the order of the items in `meaning_with_duplicate` is different from what I entered - order matters for lists but not for sets.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The code\n",
    "\n",
    "Now we've introduced the notation we are going to be using to represent word meanings we can get on and build the model. We'll start by loading the `prod` function from the numpy library (we will use it for multiplying a list of numbers, it saves us writing our own function). We also have to load the plotting library and set up inline plots. Every model we look at will start with a block of code like this, that loads some libraries and sets up plotting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from numpy import prod\n",
    "\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "from IPython.display import set_matplotlib_formats\n",
    "set_matplotlib_formats('svg', 'pdf')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A useful function for normalizing with probabilities\n",
    "\n",
    "We are also going to define a utility function, `normalize_probs`, which takes a list of numbers and normalizes them for us (i.e. scales them so they sum to 1) - we are going to use this at various points to make sure the numbers we are dealing with are genuine probabilities and behave nicely. This function is used elsewhere in the code, but it is not particularly important that you understand exactly how it works so you can skip over it if you want."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def normalize_probs(probs):\n",
    "    total = sum(probs) #calculates the summed probabilities\n",
    "    normedprobs = []\n",
    "    for p in probs:\n",
    "        normedprobs.append(p / total) #normalise - divide by summed probs\n",
    "    return normedprobs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The hypothesis space\n",
    "As outlined above, word meanings are sets. Our learner is going to receive some data, some examples of the word they are trying to learn being used to refer to entities in the world. Then they will use Bayesian inference to infer the word's meaning, the set of entities the word can be used to refer to.\n",
    "\n",
    "To make this model work, we have to lay out the candidate word meanings our learner considers: this is the *hypothesis space*. Our learner will consider each of the hypotheses (candidate word meanings) in the hypothesis space and calculate its posterior probability given the data they have seen.\n",
    "\n",
    "The hypothesis space is therefore a collection of word meanings that the learner considers when learning. We'll represent the hypothesis space in python as a list of word meanings. So here's how we represent the hypothesis space for a learner who thinks there are two candidate meanings for the word they are learning: either it refers to entity 0 and entitiy 1, or it refers to entity 2.\n",
    "\n",
    "```python\n",
    "toy_hypothesis_space = [{0,1},{2}]\n",
    "```\n",
    "\n",
    "How would you represent the following hypothesis space: \"either the word refers to entity 0, or it refers to entities 2 through 4, or it refers to entity 5\"?  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "another_toy_space = [{0},{2,3,4},{5}]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You could make the set of entities and the list of possible hypotheses as complex as you want, but for this model we are going to start out by making things fairly small (and just big enough to illustrate the things we want to illustrate). \n",
    "- We'll assume there are 11 possible entities in the world, numbered 0 to 11.\n",
    "- We'll assume that the word refers to between 1 and 6 entities (i.e. it doesn't refer to the empty set, it doesn't refer to everything).\n",
    "- We'll assume that words refer to entities that are clustered in the space of possible entities, as represented by consecutive numbers. This is a bit arbitrary and we'll return to this assumption below!\n",
    "\n",
    "Under those assumptions, this is our hypothesis space:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_hypotheses = [{0},{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},\n",
    "         {0,1},{1,2},{2,3},{3,4},{4,5},{5,6},{6,7},{7,8},{8,9},{9,10},\n",
    "         {0,1,2},{1,2,3},{2,3,4},{3,4,5},{4,5,6},{5,6,7},{6,7,8},{7,8,9},{8,9,10},\n",
    "         {0,1,2,3},{1,2,3,4},{2,3,4,5},{3,4,5,6},{4,5,6,7},{5,6,7,8},{6,7,8,9},{7,8,9,10},\n",
    "         {0,1,2,3,4},{1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7},{4,5,6,7,8},{5,6,7,8,9},{6,7,8,9,10},\n",
    "         {0,1,2,3,4,5},{1,2,3,4,5,6},{2,3,4,5,6,7},{3,4,5,6,7,8},{4,5,6,7,8,9},{5,6,7,8,9,10}]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that we are just enumerating the hypotheses by hand, rather than writing a function to generate this list for us. Let's have a look at these hypotheses, by typing `all_hypotheses` in the cell below. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{0},\n",
       " {1},\n",
       " {2},\n",
       " {3},\n",
       " {4},\n",
       " {5},\n",
       " {6},\n",
       " {7},\n",
       " {8},\n",
       " {9},\n",
       " {10},\n",
       " {0, 1},\n",
       " {1, 2},\n",
       " {2, 3},\n",
       " {3, 4},\n",
       " {4, 5},\n",
       " {5, 6},\n",
       " {6, 7},\n",
       " {7, 8},\n",
       " {8, 9},\n",
       " {9, 10},\n",
       " {0, 1, 2},\n",
       " {1, 2, 3},\n",
       " {2, 3, 4},\n",
       " {3, 4, 5},\n",
       " {4, 5, 6},\n",
       " {5, 6, 7},\n",
       " {6, 7, 8},\n",
       " {7, 8, 9},\n",
       " {8, 9, 10},\n",
       " {0, 1, 2, 3},\n",
       " {1, 2, 3, 4},\n",
       " {2, 3, 4, 5},\n",
       " {3, 4, 5, 6},\n",
       " {4, 5, 6, 7},\n",
       " {5, 6, 7, 8},\n",
       " {6, 7, 8, 9},\n",
       " {7, 8, 9, 10},\n",
       " {0, 1, 2, 3, 4},\n",
       " {1, 2, 3, 4, 5},\n",
       " {2, 3, 4, 5, 6},\n",
       " {3, 4, 5, 6, 7},\n",
       " {4, 5, 6, 7, 8},\n",
       " {5, 6, 7, 8, 9},\n",
       " {6, 7, 8, 9, 10},\n",
       " {0, 1, 2, 3, 4, 5},\n",
       " {1, 2, 3, 4, 5, 6},\n",
       " {2, 3, 4, 5, 6, 7},\n",
       " {3, 4, 5, 6, 7, 8},\n",
       " {4, 5, 6, 7, 8, 9},\n",
       " {5, 6, 7, 8, 9, 10}]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_hypotheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can you see the hypotheses that have specific meanings? How many are there? How many candidate word meanings have the broadest, most general meaning? If this is our hypothesis space, would a learner ever consider the possibility that a word had a meaning like \"this word refers to entity 0 or entity 5, but nothing else\"?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*The first ten hypotheses it spits out (`{0}`, `{1}` etc) have very specific meanings, each referring to exactly one entity. Then there are 6 hypotheses with the broadest possible meaning (the last 6 in the list), each picking out 6 entities. A hypothesis like `{0,5}` (\"this word refers to entity 0 or entity 5, but nothing else\") is **not** included in our hypothesis space as it currently stands, so our model learner would never consider it and will therefore never learn this as a word meaning, no matter how much data we give them.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The prior\n",
    "Now we have our space of hypotheses the word learner is going to consider, we need to specify two quantities to do Bayesian inference: \n",
    "- the prior probability of each hypothesis (i.e. before I have seen any data, how likely is it that the word will have this meaning?)\n",
    "- the likelihood of the data given each hypothesis (i.e. if this candidate word meaning was the word's *true* meaning, how likely would it be to generate the data I saw?). \n",
    "\n",
    "We'll do the prior first, since it's very simple: we'll just assume that all word meanings are *a priori* equally likely. In other words, our learner is going to assume, before they have seen any data, that every candidate word meaning in their hypothesis space is an equally good candidate, an equally likely possible word meaning. \n",
    "\n",
    "The way we are doing this in python is to write a function, `calculate_prior`, which works through a list of hypotheses and assigns each hypothesis equal weight: it just returns a list of prior probabilities, one per hypothesis. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_prior(possible_hypotheses):\n",
    "    prior = [] #going to put our prior probabilities here\n",
    "    for h in possible_hypotheses: #for each hypothesis\n",
    "        prior.append(1/len(possible_hypotheses))#assign it 1/number-of-hypotheses prior probability\n",
    "    return prior #return the list when finished"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Inspect the prior over our hypothesis space (by running `calculate_prior(all_hypotheses)`). Do the numbers you see there make sense? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549,\n",
       " 0.0196078431372549]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate_prior(all_hypotheses)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*This big list of the same number is the prior - the first entry gives the prior for the first hypothesis in our hypothesis space, `{0}`, the second number gives the prior for the second hypothesis in our space, and so on. The numbers are all equal because we are assuming a uniform prior, where every hypothesis is equally likely before you have seen any data. The reason the prior for each hypothesis is 0.0196078431372549 is that this is 1/51, which is 1 / the number of hypotheses in our space (51).*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0196078431372549\n",
      "0.0196078431372549\n"
     ]
    }
   ],
   "source": [
    "print(1/len(all_hypotheses))\n",
    "print(1/51)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The likelihood\n",
    "Next up, the likelihood: for each candidate word meaning, how likely is it to generate a particular sample of data? In our case we are learning a single word, so our data consists of a sequence of labelling events, where on each labelling event we see the word being used to refer to an entity. We'll represent those sequences of labelling events as a list of numbers, where each element in the list is the entity that the word was referring to on a given labelling event. So for example, if I see the word being used to refer to entity 3 then entity 0 my data looks like this:\n",
    "```python\n",
    "my_data = [3,0]\n",
    "```\n",
    "And if I see the word being used to label entity 7 five times in a row then entity 9 once my data will look like this:\n",
    "```python\n",
    "my_other_data = [7,7,7,7,7,9]\n",
    "```\n",
    "How would the following sequence of exposures be represented? I see the word being used to refer to entity 0, then entity 3, then entity 1, then entity 0 again."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 3, 1, 0]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[0,3,1,0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we have a way of representing data we can calculate the likelihood of a given set of data (a sequence of labellings) given a particular hypothesis about the word's meaning. We'll make two assumptions about labelling:\n",
    "- We'll assume that words can only be used to label entities included in the word meaning (i.e. the word with meaning `{0,1}` can only be used to label entities 0 and 1, never entity 2, 3 etc)\n",
    "- We'll assume that the word is equally likely to be used to label any entitity included in its meaning (i.e. the word with meaning `{0, 1}` is equally likely to be used to label entity 0 and entity 1; there is no priveledged meaning that it's most likely to be used for). \n",
    "\n",
    "Again, these are assumptions - we could build the model differently, to embody a different set of assumptions encapsulating a different theory of how words work!\n",
    "\n",
    "Under those assumptions, `likelihood` calculates the likelihood of some data (a sequence of observations of labellings) for a specific hypothesis: it works through a list of data, calculating the probability of each labelling event, then the overall likelihood of the sequence of exposures is just the product of those probabilities (i.e. we multiply all the individual probabilities)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def likelihood(data,hypothesis):\n",
    "    likelihoods = [] #going to store the probability of each observation here\n",
    "    for data_item in data: #work through the data\n",
    "        if data_item in hypothesis: #if that labelling can be generated under this candidate word meaning\n",
    "            likelihood_this_item = 1/len(hypothesis) #its probability is 1/length-of-the-hypothesis\n",
    "        else: #if that labelling *cannot* be generated under this candidate word meaning\n",
    "            likelihood_this_item = 0 #its probability is 0\n",
    "        likelihoods.append(likelihood_this_item)\n",
    "    return prod(likelihoods) #when you have all the individual likelihoods, multiply them all together"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What's the likelihood of observing the word being used to label entity 0 once if the word's meaning is `{0,1}`? Hint: you can calculate this using `likelihood([0],{0,1})`. What's the likelihood of seeing the word being used to label entity 0 twice and entity 1 once, if the word's meaning is `{0,1}`? What's the likelihood of that same data if the word's meaning is `{0,1,2,3}`? Why the difference?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "likelihood([0],{0,1})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.125"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "likelihood([0,0,1],{0,1})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.015625"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "likelihood([0,0,1],{0,1,2,3})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*The reason `likelihood([0,0,1],{0,1})` and `likelihood([0,0,1],{0,1,2,3})` are different is that under the more general hypothesis, it's relatively surprising if you sample three labelling episodes and only see entities 0 and 1 being labelled - there's a 1 in 4 chance every time this word is used that it's used to label entities 2 and 3, that didn't happen in this data. In contrast, for hypothesis `{0,1}`, it's less surprising to see this precise series of labellings.*\n",
    "\n",
    "*Note that `likelihood([0,0,1],{0,1})` is 1/2 x 1/2 x 1/2, and `likelihood([0,0,1],{0,1,2,3})` is 1/4 x 1/4 x 1/4. There's no fancy maths going on here, we are just multiplying the probability of each individual labelling event to get the overall likelihood.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The posterior\n",
    "Finally we are in a position to be able to calculate the posterior: our learner receives some data, we work through our hypothesis space (our set of candidate word meanings) and calculate the posterior probability of each hypothesis given that data. We do this by applying Bayes' Rule: the posterior probability of hypothesis $h$ given data $d$ is proportional to the likelihood of $d$ given $h$ times the prior probability of $h$. Or, in maths, $p(h|d)\\propto p(d|h) p(h)$. We have already defined our prior and the likelihood, so all we have to do is work through the hypothesis space and calculate this product for each hypothesis; then, at the end, we normalise these numbers, which turns them into probabilities (this is the equivalent of calculating $p(d)$, which is the denominator of Bayes' Rule). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def posterior(data,possible_hypotheses,prior):\n",
    "    posteriors = [] #this will hold the posterior distribution\n",
    "    for i in range(len(possible_hypotheses)): #consider each possible hypothesis in turn\n",
    "        h = possible_hypotheses[i] #look up the hypothesis \n",
    "        prior_h = prior[i] #look up its prior \n",
    "        likelihood_h = likelihood(data,h) #calculate likelihood of data given this hypothesis\n",
    "        posterior_h = prior_h * likelihood_h #multiply prior x likelihood\n",
    "        posteriors.append(posterior_h) #add it to the growing list\n",
    "    return normalize_probs(posteriors) #finally, normalise to turn these numbers into a probability distribution\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use the `posterior` function to calculate the posterior probability of all hypotheses (the posterior probability distribution) given the data `[0,0,1]`. You can achieve this using the following little chunk of code.\n",
    "\n",
    "```python\n",
    "my_prior = calculate_prior(all_hypotheses)\n",
    "posterior([0,0,1],all_hypotheses,my_prior)\n",
    "```\n",
    "If that's a bit hard to look at, you can print out a nice list with each hypotheis and its posterior probability using a `for` loop, like this:\n",
    "```python\n",
    "my_posterior = posterior([0,0,1],all_hypotheses,my_prior)\n",
    "for i in range(len(all_hypotheses)):\n",
    "    print(all_hypotheses[i],my_posterior[i])\n",
    "```\n",
    "Which hypotheses (candidate word meanings) have posterior probability 0? Why? Which hypotheses have non-zero posterior probability? Which hypothesis has the highest posterior probability, and why?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0} 0.0\n",
      "{1} 0.0\n",
      "{2} 0.0\n",
      "{3} 0.0\n",
      "{4} 0.0\n",
      "{5} 0.0\n",
      "{6} 0.0\n",
      "{7} 0.0\n",
      "{8} 0.0\n",
      "{9} 0.0\n",
      "{10} 0.0\n",
      "{0, 1} 0.6568863586599518\n",
      "{1, 2} 0.0\n",
      "{2, 3} 0.0\n",
      "{3, 4} 0.0\n",
      "{4, 5} 0.0\n",
      "{5, 6} 0.0\n",
      "{6, 7} 0.0\n",
      "{8, 7} 0.0\n",
      "{8, 9} 0.0\n",
      "{9, 10} 0.0\n",
      "{0, 1, 2} 0.19463299515850427\n",
      "{1, 2, 3} 0.0\n",
      "{2, 3, 4} 0.0\n",
      "{3, 4, 5} 0.0\n",
      "{4, 5, 6} 0.0\n",
      "{5, 6, 7} 0.0\n",
      "{8, 6, 7} 0.0\n",
      "{8, 9, 7} 0.0\n",
      "{8, 9, 10} 0.0\n",
      "{0, 1, 2, 3} 0.08211079483249398\n",
      "{1, 2, 3, 4} 0.0\n",
      "{2, 3, 4, 5} 0.0\n",
      "{3, 4, 5, 6} 0.0\n",
      "{4, 5, 6, 7} 0.0\n",
      "{8, 5, 6, 7} 0.0\n",
      "{8, 9, 6, 7} 0.0\n",
      "{8, 9, 10, 7} 0.0\n",
      "{0, 1, 2, 3, 4} 0.042040726954236926\n",
      "{1, 2, 3, 4, 5} 0.0\n",
      "{2, 3, 4, 5, 6} 0.0\n",
      "{3, 4, 5, 6, 7} 0.0\n",
      "{4, 5, 6, 7, 8} 0.0\n",
      "{5, 6, 7, 8, 9} 0.0\n",
      "{6, 7, 8, 9, 10} 0.0\n",
      "{0, 1, 2, 3, 4, 5} 0.024329124394813034\n",
      "{1, 2, 3, 4, 5, 6} 0.0\n",
      "{2, 3, 4, 5, 6, 7} 0.0\n",
      "{3, 4, 5, 6, 7, 8} 0.0\n",
      "{4, 5, 6, 7, 8, 9} 0.0\n",
      "{5, 6, 7, 8, 9, 10} 0.0\n"
     ]
    }
   ],
   "source": [
    "my_prior = calculate_prior(all_hypotheses)\n",
    "my_posterior = posterior([0,0,1],all_hypotheses,my_prior)\n",
    "for i in range(len(all_hypotheses)):\n",
    "    print(all_hypotheses[i],my_posterior[i])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*There are a bunch of hypotheses in there that have posterior probability 0, which are all the hypotheses that say that this word cannot be used to refer to entities 0 and 1 - e.g. the hypothesis `{0}` has posterior probability 0 because it says the word can't be used to label entity 1 and we saw that happen in our data, the hypothesis `{1, 2, 3, 4, 5, 6}` has posterior probability 0 because it says the word can't be used to label entity 0 and we saw that happen in our data.*\n",
    "\n",
    "*All the hypotheses which include entities 0 and 1 in the word's meaning have non-zero posterior probability, because they are all consistent with seeing the word being used to label entities 0 and 1.*\n",
    "\n",
    "*The hypothesis `{0,1}` has the highest posterior probability. This is an example of the size principle or an example of the suspicious coincidence phenomenon - while other hypotheses are consistent with the data we have seen (e.g. the very general hypothesis `{0, 1, 2, 3, 4, 5}`), the data we saw is most likely under the most specific hypothesis that's consistent with our data, i.e. `{0,1}`. The data we saw has lower likelihood under the more general hypotheses (as we worked out above), and since the posterior is the product of the likelihood and the prior and all the hypotheses have equal priors, this means that the more general hypotheses have lower posterior probability. To put it another way, if the word's true meaning was more general, it would be a suspicious coincidence that we only saw entities 0 and 1 being labelled using this word.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Questions\n",
    "The priority for this worksheet is to work through the in-text questions above: understanding what a hypothesis looks like in this model and how we lay out the hypothesis space, checking that the prior and likelihood functions makes sense to you, and verifying that you can compute a posterior distribution. Once you are happy with that, and if you have time left over, try these questions:\n",
    "1. How does the amount of data influence the posterior distribution? For instance, is the posterior the same after seeing the data `[0,0,1]` and the data `[0,0,1,0,0,1]`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The more data you get, the more sharply peaked the posterior becomes on the most specific hypothesis consistent with that data. We can see that by just looking at the two posterior distributions for the two data sets suggested in the question.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "POSTERIOR FOR [0,0,1]\n",
      "{0} 0.0\n",
      "{1} 0.0\n",
      "{2} 0.0\n",
      "{3} 0.0\n",
      "{4} 0.0\n",
      "{5} 0.0\n",
      "{6} 0.0\n",
      "{7} 0.0\n",
      "{8} 0.0\n",
      "{9} 0.0\n",
      "{10} 0.0\n",
      "{0, 1} 0.6568863586599518\n",
      "{1, 2} 0.0\n",
      "{2, 3} 0.0\n",
      "{3, 4} 0.0\n",
      "{4, 5} 0.0\n",
      "{5, 6} 0.0\n",
      "{6, 7} 0.0\n",
      "{8, 7} 0.0\n",
      "{8, 9} 0.0\n",
      "{9, 10} 0.0\n",
      "{0, 1, 2} 0.19463299515850427\n",
      "{1, 2, 3} 0.0\n",
      "{2, 3, 4} 0.0\n",
      "{3, 4, 5} 0.0\n",
      "{4, 5, 6} 0.0\n",
      "{5, 6, 7} 0.0\n",
      "{8, 6, 7} 0.0\n",
      "{8, 9, 7} 0.0\n",
      "{8, 9, 10} 0.0\n",
      "{0, 1, 2, 3} 0.08211079483249398\n",
      "{1, 2, 3, 4} 0.0\n",
      "{2, 3, 4, 5} 0.0\n",
      "{3, 4, 5, 6} 0.0\n",
      "{4, 5, 6, 7} 0.0\n",
      "{8, 5, 6, 7} 0.0\n",
      "{8, 9, 6, 7} 0.0\n",
      "{8, 9, 10, 7} 0.0\n",
      "{0, 1, 2, 3, 4} 0.042040726954236926\n",
      "{1, 2, 3, 4, 5} 0.0\n",
      "{2, 3, 4, 5, 6} 0.0\n",
      "{3, 4, 5, 6, 7} 0.0\n",
      "{4, 5, 6, 7, 8} 0.0\n",
      "{5, 6, 7, 8, 9} 0.0\n",
      "{6, 7, 8, 9, 10} 0.0\n",
      "{0, 1, 2, 3, 4, 5} 0.024329124394813034\n",
      "{1, 2, 3, 4, 5, 6} 0.0\n",
      "{2, 3, 4, 5, 6, 7} 0.0\n",
      "{3, 4, 5, 6, 7, 8} 0.0\n",
      "{4, 5, 6, 7, 8, 9} 0.0\n",
      "{5, 6, 7, 8, 9, 10} 0.0\n",
      "POSTERIOR FOR [0,0,1,0,0,1]\n",
      "{0} 0.0\n",
      "{1} 0.0\n",
      "{2} 0.0\n",
      "{3} 0.0\n",
      "{4} 0.0\n",
      "{5} 0.0\n",
      "{6} 0.0\n",
      "{7} 0.0\n",
      "{8} 0.0\n",
      "{9} 0.0\n",
      "{10} 0.0\n",
      "{0, 1} 0.9018073901245205\n",
      "{1, 2} 0.0\n",
      "{2, 3} 0.0\n",
      "{3, 4} 0.0\n",
      "{4, 5} 0.0\n",
      "{5, 6} 0.0\n",
      "{6, 7} 0.0\n",
      "{8, 7} 0.0\n",
      "{8, 9} 0.0\n",
      "{9, 10} 0.0\n",
      "{0, 1, 2} 0.07917101916045172\n",
      "{1, 2, 3} 0.0\n",
      "{2, 3, 4} 0.0\n",
      "{3, 4, 5} 0.0\n",
      "{4, 5, 6} 0.0\n",
      "{5, 6, 7} 0.0\n",
      "{8, 6, 7} 0.0\n",
      "{8, 9, 7} 0.0\n",
      "{8, 9, 10} 0.0\n",
      "{0, 1, 2, 3} 0.014090740470695633\n",
      "{1, 2, 3, 4} 0.0\n",
      "{2, 3, 4, 5} 0.0\n",
      "{3, 4, 5, 6} 0.0\n",
      "{4, 5, 6, 7} 0.0\n",
      "{8, 5, 6, 7} 0.0\n",
      "{8, 9, 6, 7} 0.0\n",
      "{8, 9, 10, 7} 0.0\n",
      "{0, 1, 2, 3, 4} 0.0036938030699500374\n",
      "{1, 2, 3, 4, 5} 0.0\n",
      "{2, 3, 4, 5, 6} 0.0\n",
      "{3, 4, 5, 6, 7} 0.0\n",
      "{4, 5, 6, 7, 8} 0.0\n",
      "{5, 6, 7, 8, 9} 0.0\n",
      "{6, 7, 8, 9, 10} 0.0\n",
      "{0, 1, 2, 3, 4, 5} 0.001237047174382058\n",
      "{1, 2, 3, 4, 5, 6} 0.0\n",
      "{2, 3, 4, 5, 6, 7} 0.0\n",
      "{3, 4, 5, 6, 7, 8} 0.0\n",
      "{4, 5, 6, 7, 8, 9} 0.0\n",
      "{5, 6, 7, 8, 9, 10} 0.0\n"
     ]
    }
   ],
   "source": [
    "posterior1 = posterior([0,0,1],all_hypotheses,my_prior)\n",
    "posterior2 = posterior([0,0,1,0,0,1],all_hypotheses,my_prior)\n",
    "print('POSTERIOR FOR [0,0,1]')\n",
    "for i in range(len(all_hypotheses)):\n",
    "    print(all_hypotheses[i],posterior1[i])\n",
    "print('POSTERIOR FOR [0,0,1,0,0,1]')\n",
    "for i in range(len(all_hypotheses)):\n",
    "    print(all_hypotheses[i],posterior2[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*So if you compare the posterior for `{0,1}` in those two distributions, you'll see it's higher in `posterior2` (and all the more general hypotheses have correspondingly lower posterior probability). It's another example of the suspicious coincidence phenomenon - seeing only entities 0 and 1 labelled using the word when the word's meaning is more general than that becomes increasingly surprising the more data we get.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. When are more specific word meanings preferred? When are more general word meanings preferred?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Because of the size principle / suspicious coincidence thing, the most specific meaning that includes the observed data is **always** preferred. The way to force the learner to acquire a more general hypothesis is to show them labelling events that cannot be explained under a too-restructive hypothesis.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. This code calculates a probability distribution over possible hypotheses given some data. If you had to commit to a *single* hypothesis, how would you choose one? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*There are a couple of obvious options. You could pick the hypothesis with the highest posterior probability - this is known as the MAP hypothesis, the Maximum A Posteriori hypothesis. Or you could pick a random hypothesis, but select proportional to posterior probability - so you are more likely to select hypotheses with higher posterior probability, but you might select a less likely one sometimes.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. Do we have any kind *innateness* in our model? Are there word meanings that our model learner could never learn, no matter what kind of data we gave them? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*If \"innateness\" means \"stuff that the learner brings to the learning task before they have seen any data\", then yes. There's the prior - in this model it's not very interesting since it's uniform, but it's still an assumption the learner makes before they encounter any data, so in that sense it could represent an innate bias. There's also the hypothesis space: a hypothesis that's not included in this space is never considered by the learner, so it can't be learned no matter how much data the learner gets. Again, in this model that's something that's in place before the learner has encountered any data, so you could imagine it's a model of a particular kind of innateness. There's also the likelihood function - for every hypothesis in the hypothesis space, the learner knows how that hypothesis would lead to labelling behaviour, and uses that knowledge (the likelihood) when evaluating hypotheses in the light of data. Again, in our model we just assume that's in place from the start. So actually in this model quite a lot of stuff is assumed to be in place before the learner has encountered any data!*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. [Harder] We are assuming that candidate word meanings are nice and neat: a word refers to a set of entities that are contiguous in some sense (as represented by consecutive integers: i.e. our hypothesis space includes `{3,4,5}` but not `{3,5}` as a candidate meaning). Calculate the posterior probability distribution using the standard hypothesis space and the data `[3,5]`. Which hypothesis has the highest posterior probability? Now add a \"hypothesis with a hole in it\", `{3,5}` to the hypothesis space and recalculate the posterior. Which hypothesis has the highest posterior probability now, and why? Is there a potential problem here if we are trying to model learning? How would we change the model to disfavour this kind of \"hypothesis with a hole in it\"?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Because our learner always favours the most specific hypothesis that is consistent with the data they see (because of the size principle / suspicious coincindences), for data `[3,5]` hypothesis `{3,4,5}` will have the highest prior in the default `all_hypotheses` space - even though they have no direct evidence that the word meaning includes entity 4, the learner will generalize the word to cover that entity. Generalization is a nice feature of the model, since generalization is an inherent feature of the way we learn (you don't need to see **every** dog labelled as a dog to know they fall under that word's denotation).*\n",
    "\n",
    "*However, if we add a hypothesis-with-a-hole, `{3,5}`, to our hypothesis space, that now becomes the hypothesis with the highest posterior probability - it's the most specific hypothesis that covers the data we saw, so the likelihood of the data is higher under the `{3,5}` hypothesis than the `{3,4,5}` hypothesis, so if we select `{3,5}` as the outcome of learning we will not generalize beyond the data we saw. That's a problem, because for the reasons outlined above we want to model learners who generalize!*\n",
    "\n",
    "*There are two ways to fix this (plus see the answer to Q6). One is to shape the hypothesis space such that generalization is inevitable - that's what I did in the `all_hypotheses` space, where there are no hypotheses-with-a-hole included. Another way to go is to allow those hypotheses to be included in the space, but to fix the prior to disprefer them (i.e. they have lower prior probability), so the learner will tend to generalize by default unless they get very convincing evidence they shouldn't (i.e. they'd generalize to `{3,4,5}` based on data `[3,5]`, but probably not from data `[3,5,3,5,3,5,3,5,3,5,...]`).*\n",
    "\n",
    "*If you are ambitious you could add this kind of contiguity-favouring prior to the model, by creating a new version of the calculate_prior function.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6. [Harder] We are assuming (in the `likelihood` function) that all meanings of a word are equally likely to be encountered. What other kinds of assumptions might you make? How could you model those?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*This is a pretty open question, but one possibility is that each word meaning has a prototype example and then some more fringe cases - so for example, for the word meaning `{3,4,5}`, maybe most of the time it is used to label entity 4 and only ocasionally to label entities 3 and 5. The way this could be included in the model is to change the likelihood function so that, instead of all entities from a word meaning being equally likely to be sampled, it's the \"middle\" one that's most likely. That would change the likelihood so it would change the posterior - for example, I suspect it would make the learner more likely to infer e.g. `{3,4,5}` based on data like `[4,4,4]`, because it's just less surprising to get that data if the true word meaning is `{3,4,5}` with a preference for 4. This would be another way to build a model that's more prone to generalize - in this case our learner wouldn't be generalizing to \"fill in\" holes in the hypothesis, but rather they'd be generalizing from the prototype central member to more peripheral parts of the word meaning.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "Tenenbaum, J. B. (2000). Bayesian modeling of human concept learning. In S. Solla, T. Leen, & K. R. Muller (Eds.), *Advances in Neural Information Processing Systems 12* (pp 59–65). Cambridge, MA: MIT Press.\n",
    "\n",
    "Xu, F., & Tenenbaum, J. B. (2007). Word learning as Bayesian inference. *Psychological Review, 114,* 245-272."
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}