rel_ext_01_task.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Relation extraction using distant supervision: Task definition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "__author__ = \"Bill MacCartney\"\n",
    "__version__ = \"CS224U, Stanford, Spring 2019\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Contents\n",
    "\n",
    "1. [Overview](#Overview)\n",
    "  1. [The task of relation extraction](#The-task-of-relation-extraction)\n",
    "  1. [Hand-built patterns](#Hand-built-patterns)\n",
    "  1. [Supervised learning](#Supervised-learning)\n",
    "  1. [Distant supervision](#Distant-supervision)\n",
    "1. [Set-up](#Set-up)\n",
    "1. [The corpus](#The-corpus)\n",
    "1. [The knowledge base](#The-knowledge-base)\n",
    "1. [Problem formulation](#Problem-formulation)\n",
    "  1. [Joining the corpus and the KB](#Joining-the-corpus-and-the-KB)\n",
    "  1. [Negative instances](#Negative-instances)\n",
    "  1. [Multi-label classification](#Multi-label-classification)\n",
    "  1. [Building datasets](#Building-datasets)\n",
    "1. [Evaluation](#Evaluation)\n",
    "  1. [Splitting the data](#Splitting-the-data)\n",
    "  1. [Choosing evaluation metrics](#Choosing-evaluation-metrics)\n",
    "  1. [Running evaluations](#Running-evaluations)\n",
    "  1. [Evaluating a random-guessing strategy](#Evaluating-a-random-guessing-strategy)\n",
    "1. [A simple baseline model](#A-simple-baseline-model)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview\n",
    "\n",
    "This notebook illustrates an approach to [relation extraction](http://deepdive.stanford.edu/relation_extraction) using [distant supervision](http://deepdive.stanford.edu/distant_supervision). It uses a simplified version of the approach taken by Mintz et al. in their 2009 paper, [Distant supervision for relation extraction without labeled data](https://www.aclweb.org/anthology/P09-1113). If you haven't yet read that paper, read it now! The rest of the notebook will make a lot more sense after you're familiar with it.\n",
    "\n",
    "### The task of relation extraction\n",
    "\n",
    "Relation extraction is the task of extracting from natural language text relational triples such as:\n",
    "\n",
    "```\n",
    "(founders, SpaceX, Elon_Musk)\n",
    "(has_spouse, Elon_Musk, Talulah_Riley)\n",
    "(worked_at, Elon_Musk, Tesla_Motors)\n",
    "```\n",
    "\n",
    "If we can accumulate a large knowledge base (KB) of relational triples, we can use it to power question answering and other applications. Building a KB manually is slow and expensive, but much of the knowledge we'd like to capture is already expressed in abundant text on the web. The aim of relation extraction, therefore, is to accelerate the construction of new KBs — and facilitate the ongoing curation of existing KBs — by extracting relational triples from natural language text.\n",
    "\n",
    "### Hand-built patterns\n",
    "\n",
    "An obvious way to start is to write down a few patterns which express each relation. For example, we can use the pattern \"X is the founder of Y\" to find new instances of the `founders` relation. If we search a large corpus, we may find the phrase \"Elon Musk is the founder of SpaceX\", which we can use as evidence for the relational triple `(founders, SpaceX, Elon_Musk)`.\n",
    "\n",
    "Unfortunately, this approach doesn't get us very far. The central challenge of relation extraction is the fantastic diversity of language, the multitude of possible ways to express a given relation. For example, each of the following sentences expressed the relational triple `(founders, SpaceX, Elon_Musk)`:\n",
    "\n",
    "- \"You may also be thinking of _Elon Musk_ (founder of _SpaceX_), who started PayPal.\"\n",
    "- \"Interesting Fact: _Elon Musk_, co-founder of PayPal, went on to establish _SpaceX_, one of the most promising space travel startups in the world.\"\n",
    "- \"If Space Exploration (_SpaceX_), founded by Paypal pioneer _Elon Musk_ succeeds, commercial advocates will gain credibility and more support in Congress.\"\n",
    "\n",
    "The patterns which connect \"Elon Musk\" with \"SpaceX\" in these examples are not ones we could have easily anticipated. To do relation extraction effectively, we need to go beyond hand-built patterns.\n",
    "\n",
    "### Supervised learning\n",
    "\n",
    "Effective relation extraction will require applying machine learning methods. The natural place to start is with supervised learning. This means training an extraction model from a dataset of examples which have been labeled with the target output. Sentences like the three examples above would be annotated with the `founders` relation, but we'd also have sentences which include \"Elon Musk\" and \"SpaceX\" but do not express the `founders` relation, such as:\n",
    "\n",
    "- \"Billionaire entrepreneur _Elon Musk_ announced the latest addition to the _SpaceX_ arsenal: the 'Big F---ing Rocket' (BFR)\".\n",
    "\n",
    "Such \"negative examples\" would be labeled as such, and the fully-supervised model would then be able to learn from both positive and negative examples the linguistic patterns that indicate each relation.\n",
    "\n",
    "The difficulty with the fully-supervised approach is the cost of generating training data. Because of the great diversity of linguistic expression, our model will need lots and lots of training data: at least tens of thousands of examples, although hundreds of thousands or millions would be much better. But labeling the examples is just as slow and expensive as building the KB by hand would be.\n",
    "\n",
    "### Distant supervision\n",
    "\n",
    "The goal of distant supervision is to capture the benefits of supervised learning without paying the cost of labeling training data. Instead of labeling extraction examples by hand, we use existing relational triples to automatically identify extraction examples in a large corpus. For example, if we already have in our KB the relational triple `(founders, SpaceX, Elon_Musk)`, we can search a large corpus for sentences in which \"SpaceX\" and \"Elon Musk\" co-occur, make the (unreliable!) assumption that all the sentences express the `founder` relation, and then use them as training data for a learned model to identify new instances of the `founder` relation — all without doing any manual labeling.\n",
    "\n",
    "This is a powerful idea, but it has two limitations. The first is that, inevitably, some of the sentences in which \"SpaceX\" and \"Elon Musk\" co-occur will not express the `founder` relation — like the BFR example above. By making the blind assumption that all such sentences do express the `founder` relation, we are essentially injecting noise into our training data, and making it harder for our learning algorithms to learn good models. Distant supervision is effective in spite of this problem because it makes it possible to leverage vastly greater quantities of training data, and the benefit of more data outweighs the harm of noisier data.\n",
    "\n",
    "The second limitation is that we need an existing KB to start from. We can only train a model to extract new instances of the `founders` relation if we already have many instances of the `founders` relation. Thus, while distant supervision is a great way to extend an existing KB, it's not useful for creating a KB containing new relations from scratch.\n",
    "\n",
    "\\[ [top](#Relation-extraction-using-distant-supervision) \\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Set-up\n",
    "\n",
    "*  Make sure your environment includes all the requirements for [the cs224u repository](https://github.com/cgpotts/cs224u).\n",
    "\n",
    "* If you haven't already, download [the course data](http://web.stanford.edu/class/cs224u/data/data.zip), unpack it, and place it in the directory containing the course repository – the same directory as this notebook. (If you want to put it somewhere else, change `rel_ext_data_home` below.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gzip\n",
    "import numpy as np\n",
    "import random\n",
    "import os\n",
    "\n",
    "from collections import Counter, defaultdict, namedtuple\n",
    "from sklearn.feature_extraction import DictVectorizer\n",
    "from sklearn.linear_model import LogisticRegression\n",
    "from sklearn.metrics import precision_recall_fscore_support\n",
    "from sklearn.model_selection import train_test_split\n",
    "\n",
    "import rel_ext"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "rel_ext_data_home = os.path.join('data', 'rel_ext_data')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\[ [top](#Relation-extraction-using-distant-supervision) \\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The corpus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As usual when we're doing NLP, we need to start with a _corpus_ — a large sample of natural language text. And because our goal is to do relation extraction with distant supervision, we need to be able to identify entities in the text and connect them to a knowledge base of relations between entities. So, we need a corpus in which entity mentions are annotated with _entity resolutions_ which map them to unique, unambiguous identifiers. Entity resolution serves two purposes:\n",
    "\n",
    "1. It ensures that if an entity mention could refer to two different entities, it is properly disambiguated. For example, \"New York\" could refer to the city or the state.\n",
    "1. It ensures that if two different entity mentions refer to the same entity, they are properly identified. For example, both \"New York City\" and \"The Big Apple\" refer to New York City.\n",
    "\n",
    "The corpus we'll use for this project is derived from the [Wikilinks dataset](https://code.google.com/archive/p/wiki-links/) [announced by Google in 2013](https://research.googleblog.com/2013/03/learning-from-big-data-40-million.html). This dataset contains over 40M mentions of 3M distinct entities spanning 10M webpages. It provides entity resolutions by mapping each entity mention to a Wikipedia URL.\n",
    "\n",
    "Now, in order to do relation extraction, we actually need _pairs_ of entity mentions, and it's important to have the context around and between the two mentions. Fortunately, UMass has provided an [expanded version of Wikilinks](http://www.iesl.cs.umass.edu/data/data-wiki-links) which includes the context around each entity mention. We've written code to stitch together pairs of entity mentions along with their contexts, and we've filtered the examples extensively. The result is a compact corpus suitable for our purposes.\n",
    "\n",
    "Because we're frequently going to want to retrieve corpus examples containing specific entities, it will be convenient to create a `Corpus` class which holds not only the examples themselves, but also a precomputed index. Let's take a closer look."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Read 331,696 examples\n"
     ]
    }
   ],
   "source": [
    "corpus = rel_ext.Corpus(os.path.join(rel_ext_data_home, 'corpus.tsv.gz'))\n",
    "\n",
    "print('Read {0:,} examples'.format(len(corpus)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great, that's a lot of examples! Let's take a closer look at one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Example(entity_1='New_Mexico', entity_2='Arizona', left='to all Spanish-occupied lands . The horno has a beehive shape and uses wood as the only heat source . The procedure still used in parts of', mention_1='New Mexico', middle='and', mention_2='Arizona', right='is to build a fire inside the Horno and , when the proper amount of time has passed , remove the embers and ashes and insert the', left_POS='to/TO all/DT Spanish-occupied/JJ lands/NNS ./. The/DT horno/NN has/VBZ a/DT beehive/NN shape/NN and/CC uses/VBZ wood/NN as/IN the/DT only/JJ heat/NN source/NN ./. The/DT procedure/NN still/RB used/VBN in/IN parts/NNS of/IN', mention_1_POS='New/NNP Mexico/NNP', middle_POS='and/CC', mention_2_POS='Arizona/NNP', right_POS='is/VBZ to/TO build/VB a/DT fire/NN inside/IN the/DT Horno/NNP and/CC ,/, when/WRB the/DT proper/JJ amount/NN of/IN time/NN has/VBZ passed/VBN ,/, remove/VB the/DT embers/NNS and/CC ashes/NNS and/CC insert/VB the/DT')\n"
     ]
    }
   ],
   "source": [
    "print(corpus.examples[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Every example represents a fragment of webpage text containing two entity mentions. The first two fields, `entity_1` and `entity_2`, contain unique identifiers for the two entities mentioned. We name entities using Wiki IDs, which you can think of as the last portion of a Wikipedia URL. Thus the Wiki ID `Barack_Obama` designates the entity described by [https://en.wikipedia.org/wiki/Barack_Obama](https://en.wikipedia.org/wiki/Barack_Obama).\n",
    "\n",
    "The next five fields represent the text surrounding the two mentions, divided into five chunks: `left` contains the text before the first mention, `mention_1` is the first mention itself, `middle` contains the text between the two mentions, `mention_2` is the second mention, and the field `right` contains the text after the second mention. Thus, we can reconstruct the context as a single string like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'to all Spanish-occupied lands . The horno has a beehive shape and uses wood as the only heat source . The procedure still used in parts of New Mexico and Arizona is to build a fire inside the Horno and , when the proper amount of time has passed , remove the embers and ashes and insert the'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ex = corpus.examples[1]\n",
    "\n",
    "' '.join((ex.left, ex.mention_1, ex.middle, ex.mention_2, ex.right))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The last five fields contain the same five chunks of text, but this time annotated with part-of-speech (POS) tags, which may turn out to be useful when we start building models for relation extraction.\n",
    "\n",
    "Let's look at the distribution of entities over the corpus. How many entities are there, and what are the most common ones?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The corpus contains 95909 entities\n",
      "The most common entities are:\n",
      "      8137 India\n",
      "      5240 England\n",
      "      4121 France\n",
      "      4040 Germany\n",
      "      3937 Australia\n",
      "      3779 Canada\n",
      "      3633 Italy\n",
      "      3138 California\n",
      "      2894 New_York_City\n",
      "      2745 Pakistan\n",
      "      2213 New_Zealand\n",
      "      2183 New_York\n",
      "      2148 United_Kingdom\n",
      "      2030 Spain\n",
      "      2005 Japan\n",
      "      1891 Russia\n",
      "      1806 Philippines\n",
      "      1748 Malaysia\n",
      "      1721 Indonesia\n",
      "      1670 China\n"
     ]
    }
   ],
   "source": [
    "counter = Counter()\n",
    "for example in corpus.examples:\n",
    "    counter[example.entity_1] += 1\n",
    "    counter[example.entity_2] += 1\n",
    "print('The corpus contains {} entities'.format(len(counter)))\n",
    "counts = sorted([(count, key) for key, count in counter.items()], reverse=True)\n",
    "print('The most common entities are:')\n",
    "for count, key in counts[:20]:\n",
    "    print('{:10d} {}'.format(count, key))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The main benefit we gain from the `Corpus` class is the ability to retrieve examples containing specific entities. Let's find examples containing `Elon_Musk` and `Tesla_Motors`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The first of 5 examples for Elon_Musk and Tesla_Motors is:\n",
      "Example(entity_1='Elon_Musk', entity_2='Tesla_Motors', left='space for a while , here ’ s what might be launching Americans into space in the next decade . Falcon 9 From sometimes Canadian , South African & American', mention_1='Elon Musk', middle='‘ s company Space X . Musk is a PayPal alumni and', mention_2='Tesla Motors', right='co-founder - remember that latter company name for future trivia questions and/or a remake of Back to the Future . After several successful launches on their Falcon', left_POS=\"space/NN for/IN a/DT while/NN ,/, here/RB '/'' s/VBZ what/WP might/MD be/VB launching/VBG Americans/NNPS into/IN space/NN in/IN the/DT next/JJ decade/NN ./. Falcon/NNP 9/CD From/IN sometimes/RB Canadian/JJ ,/, South/JJ African/NNP &/CC American/NNP\", mention_1_POS='Elon/NNP Musk/NNP', middle_POS='`/`` s/NNS company/NN Space/NN X/NN ./. Musk/NNP is/VBZ a/DT PayPal/NNP alumni/NNS and/CC', mention_2_POS='Tesla/NNP Motors/NNPS', right_POS='co-founder/NN -/: remember/VB that/DT latter/JJ company/NN name/NN for/IN future/JJ trivia/NNS questions/NNS and/or/CC a/DT remake/NN of/IN Back/RB to/TO the/DT Future/NNP ./. After/IN several/JJ successful/JJ launches/NNS on/IN their/PRP$ Falcon/NN')\n"
     ]
    }
   ],
   "source": [
    "corpus.show_examples_for_pair('Elon_Musk', 'Tesla_Motors')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Actually, this might not be all of the examples containing `Elon_Musk` and `Tesla_Motors`. It's only the examples where `Elon_Musk` was mentioned first and `Tesla_Motors` second. There may be additional examples that have them in the reverse order. Let's check."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The first of 2 examples for Tesla_Motors and Elon_Musk is:\n",
      "Example(entity_1='Tesla_Motors', entity_2='Elon_Musk', left='their factory in Hethel . If you want to see one in action , Robert Scoble got a ride in the first production model , driven by', mention_1='Tesla Motors', middle='chairman', mention_2='Elon Musk', right='. Needless to say he got the whole thing on video , and covers a lot of technical details about the car – this is the', left_POS='their/PRP$ factory/NN in/IN Hethel/NNP ./. If/IN you/PRP want/VBP to/TO see/VB one/CD in/IN action/NN ,/, Robert/NNP Scoble/NNP got/VBD a/DT ride/NN in/IN the/DT first/JJ production/NN model/NN ,/, driven/VBN by/IN', mention_1_POS='Tesla/NNP Motors/NNPS', middle_POS='chairman/NN', mention_2_POS='Elon/NNP Musk/NNP', right_POS='./. Needless/JJ to/TO say/VB he/PRP got/VBD the/DT whole/JJ thing/NN on/IN video/NN ,/, and/CC covers/VBZ a/DT lot/NN of/IN technical/JJ details/NNS about/IN the/DT car/NN --/: this/DT is/VBZ the/DT')\n"
     ]
    }
   ],
   "source": [
    "corpus.show_examples_for_pair('Tesla_Motors', 'Elon_Musk')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sure enough. Going forward, we'll have to remember to check both \"directions\" when we're looking for examples contains a specific pair of entities.\n",
    "\n",
    "This corpus is not without flaws. As you get more familiar with it, you will likely discover that it contains many examples that are nearly — but not exactly — duplicates. This seems to be a consequence of the web document sampling methodology that was used in the construction of the Wikilinks dataset. However, despite a few warts, it will serve our purposes.\n",
    "\n",
    "One thing this corpus does _not_ include is any annotation about relations. Thus, it could not be used for the fully-supervised approach to relation extraction, because the fully-supervised approach requires that each pair of entity mentions be annotated with the relation (if any) that holds between the two entities. In order to make any headway, we'll need to connect the corpus with an external source of knowledge about relations. We need a knowledge base.\n",
    "\n",
    "\\[ [top](#Relation-extraction-using-distant-supervision) \\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The knowledge base"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The data distribution for this unit includes a _knowledge base_ (KB) ultimately derived from [Freebase](https://en.wikipedia.org/wiki/Freebase). Unfortunately, Freebase was shut down in 2016, but the Freebase data is still available from various sources and in various forms. The KB included here was extracted from the [Freebase Easy data dump](http://freebase-easy.cs.uni-freiburg.de/dump/).\n",
    "\n",
    "The KB is a collection of _relational triples_, each consisting of a _relation_, a _subject_, and an _object_. For example, here are three triples from the KB:\n",
    "\n",
    "```\n",
    "(place_of_birth, Barack_Obama, Honolulu)\n",
    "(has_spouse, Barack_Obama, Michelle_Obama)\n",
    "(author, The_Audacity_of_Hope, Barack_Obama)\n",
    "```\n",
    "\n",
    "As you might guess:\n",
    "\n",
    "- The relation is one of a handful of predefined constants, such as `place_of_birth` or `has_spouse`.\n",
    "- The subject and object are entities represented by Wiki IDs (that is, suffixes of Wikipedia URLs).\n",
    "\n",
    "Let's write some code to read the KB so that we can take a closer look.\n",
    "\n",
    "Now, just as we did for the corpus, we'll create a `KB` class to store the KB triples and some associated indexes. We'll want to be able to look up KB triples both by relation and by entities, so we'll create indexes for both of those access patterns."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Read 45,884 KB triples\n"
     ]
    }
   ],
   "source": [
    "kb = rel_ext.KB(os.path.join(rel_ext_data_home, 'kb.tsv.gz'))\n",
    "\n",
    "print('Read {0:,} KB triples'.format(len(kb)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's get a sense of the high-level characteristics of this KB. Some questions we'd like to answer:\n",
    "\n",
    "- How many relations are there?\n",
    "- How big is each relation?\n",
    "- Examples of each relation.\n",
    "- How many unique entities does the KB include?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(kb.all_relations)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How big is each relation? That is, how many triples does each relation contain?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "        1702 adjoins\n",
      "        2671 author\n",
      "         522 capital\n",
      "       18681 contains\n",
      "        3947 film_performance\n",
      "        1960 founders\n",
      "         824 genre\n",
      "        2563 has_sibling\n",
      "        2994 has_spouse\n",
      "        2542 is_a\n",
      "        1598 nationality\n",
      "        1586 parents\n",
      "        1097 place_of_birth\n",
      "         831 place_of_death\n",
      "        1216 profession\n",
      "        1150 worked_at\n"
     ]
    }
   ],
   "source": [
    "for rel in kb.all_relations:\n",
    "    print('{:12d} {}'.format(len(kb.get_triples_for_relation(rel)), rel))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at one example from each relation, so that we can get a sense of what they mean."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('adjoins', 'France', 'Spain')\n",
      "('author', 'Uncle_Silas', 'Sheridan_Le_Fanu')\n",
      "('capital', 'Panama', 'Panama_City')\n",
      "('contains', 'Brickfields', 'Kuala_Lumpur_Sentral_railway_station')\n",
      "('film_performance', 'Colin_Hanks', 'The_Great_Buck_Howard')\n",
      "('founders', 'Lashkar-e-Taiba', 'Hafiz_Muhammad_Saeed')\n",
      "('genre', '8_Simple_Rules', 'Sitcom')\n",
      "('has_sibling', 'Ari_Emanuel', 'Rahm_Emanuel')\n",
      "('has_spouse', 'Percy_Bysshe_Shelley', 'Mary_Shelley')\n",
      "('is_a', 'Bhanu_Athaiya', 'Costume_designer')\n",
      "('nationality', 'Ruben_Rausing', 'Sweden')\n",
      "('parents', 'Rosanna_Davison', 'Chris_de_Burgh')\n",
      "('place_of_birth', 'William_Penny_Brookes', 'Much_Wenlock')\n",
      "('place_of_death', 'Jean_Drapeau', 'Montreal')\n",
      "('profession', 'Rufus_Wainwright', 'Actor')\n",
      "('worked_at', 'Brian_Greene', 'Columbia_University')\n"
     ]
    }
   ],
   "source": [
    "for rel in kb.all_relations:\n",
    "    print(tuple(kb.get_triples_for_relation(rel)[0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `kb.get_triples_for_entities()` method allows us to look up triples by the entities they contain. Let's use it to see what relation(s) hold between `France` and `Germany`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[KBTriple(rel='adjoins', sbj='France', obj='Germany')]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kb.get_triples_for_entities('France', 'Germany')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Relations like `adjoins` and `has_sibling` are intuitively symmetric — if the relation holds between _X_ and _Y_, then we expect it to hold between _Y_ and _X_ as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[KBTriple(rel='adjoins', sbj='Germany', obj='France')]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kb.get_triples_for_entities('Germany', 'France')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, there's no guarantee that all such inverse triples actually appear in the KB. (You could write some code to check.)\n",
    "\n",
    "Most relations, however, are intuitively asymmetric. Let's see what relation holds between `Tesla_Motors` and `Elon_Musk`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[KBTriple(rel='founders', sbj='Tesla_Motors', obj='Elon_Musk')]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kb.get_triples_for_entities('Tesla_Motors', 'Elon_Musk')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's a bit arbitrary that the KB includes a given asymmetric relation rather than its inverse. For example, instead of the `founders` relation with triple `(founders, Tesla_Motors, Elon_Musk)`, we might have had a `founder_of` relation with triple `(founder_of, Elon_Musk, Tesla_Motors)`. It doesn't really matter.\n",
    "\n",
    "Although we don't have a `founder_of` relation, there might still be a relation between `Elon_Musk` and `Tesla_Motors`. Let's check."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[KBTriple(rel='worked_at', sbj='Elon_Musk', obj='Tesla_Motors')]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kb.get_triples_for_entities('Elon_Musk', 'Tesla_Motors')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Aha, yes, that makes sense. So it can be the case that one relation holds between _X_ and _Y_, and a different relation holds between _Y_ and _X_.\n",
    "\n",
    "One more observation: there may be more than one relation that holds between a given pair of entities, even in one direction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[KBTriple(rel='has_sibling', sbj='Cleopatra', obj='Ptolemy_XIII_Theos_Philopator'),\n",
       " KBTriple(rel='has_spouse', sbj='Cleopatra', obj='Ptolemy_XIII_Theos_Philopator')]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kb.get_triples_for_entities('Cleopatra', 'Ptolemy_XIII_Theos_Philopator')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No! What? Yup, it's true — [Cleopatra](https://en.wikipedia.org/wiki/Cleopatra) married her younger brother, [Ptolemy XIII](https://en.wikipedia.org/wiki/Ptolemy_XIII_Theos_Philopator). Wait, it gets worse — she also married her _even younger_ brother, [Ptolemy XIV](https://en.wikipedia.org/wiki/Ptolemy_XIV_of_Egypt). Apparently this was normal behavior in ancient Egypt.\n",
    "\n",
    "Moving on ...\n",
    "\n",
    "Let's look at the distribution of entities in the KB. How many entities are there, and what are the most common ones?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The KB contains 40141 entities\n",
      "The most common entities are:\n",
      "       945 England\n",
      "       786 India\n",
      "       438 Italy\n",
      "       414 France\n",
      "       412 California\n",
      "       400 Germany\n",
      "       372 United_Kingdom\n",
      "       366 Canada\n",
      "       302 New_York_City\n",
      "       247 New_York\n",
      "       236 Australia\n",
      "       219 Philippines\n",
      "       215 Japan\n",
      "       212 Scotland\n",
      "       208 Russia\n",
      "       198 Actor\n",
      "       172 Pakistan\n",
      "       170 Ontario\n",
      "       169 Ireland\n",
      "       168 New_Zealand\n"
     ]
    }
   ],
   "source": [
    "counter = Counter()\n",
    "for kbt in kb.kb_triples:\n",
    "    counter[kbt.sbj] += 1\n",
    "    counter[kbt.obj] += 1\n",
    "print('The KB contains {} entities'.format(len(counter)))\n",
    "counts = sorted([(count, key) for key, count in counter.items()], reverse=True)\n",
    "print('The most common entities are:')\n",
    "for count, key in counts[:20]:\n",
    "    print('{:10d} {}'.format(count, key))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The number of entities in the KB is less than half the number of entities in the corpus! Evidently the corpus has much broader coverage than the KB.\n",
    "\n",
    "Note that there is no promise or expectation that this KB is _complete_. Not only does the KB contain no mention of many entities from the corpus — even for the entities it does include, there may be possible triples which are true in the world but are missing from the KB. As an example, these triples are in the KB:\n",
    "\n",
    "```\n",
    "(founders, SpaceX, Elon_Musk)\n",
    "(founders, Tesla_Motors, Elon_Musk)\n",
    "(worked_at, Elon_Musk, Tesla_Motors)\n",
    "```\n",
    "\n",
    "but this one is not:\n",
    "\n",
    "```\n",
    "(worked_at, Elon_Musk, SpaceX)\n",
    "```\n",
    "\n",
    "In fact, the whole point of developing methods for automatic relation extraction is to extend existing KBs (and build new ones) by identifying new relational triples from natural language text. If our KBs were complete, we wouldn't have anything to do.\n",
    "\n",
    "\\[ [top](#Relation-extraction-using-distant-supervision) \\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem formulation\n",
    "\n",
    "With our data assets in hand, it's time to provide a precise formulation of the prediction problem we aim to solve. We need to specify:\n",
    "\n",
    "- What is the input to the prediction?\n",
    "    - Is it a specific pair of entity _mentions_ in a specific context?\n",
    "    - Or is it a pair of _entities_, apart from any specific mentions?\n",
    "- What is the output of the prediction?\n",
    "    - Do we need to predict at most one relation label? (This is [multi-class classification](https://en.wikipedia.org/wiki/Multiclass_classification).)\n",
    "    - Or can we predict multiple relation labels? (This is [multi-label classification](https://en.wikipedia.org/wiki/Multi-label_classification).)\n",
    "\n",
    "### Joining the corpus and the KB\n",
    "\n",
    "In order to leverage the distant supervision paradigm, we'll need to connect information in the corpus with information in the KB. There are two possibilities, depending on how we formulate our prediction problem:\n",
    "\n",
    "- __Use the KB to generate labels for the corpus.__ If our problem is to classify a pair of entity _mentions_ in a specific example in the corpus, then we can use the KB to provide labels for training examples. Labeling specific examples is how the fully supervised paradigm works, so it's the obvious way to think about leveraging distant supervision as well. Although it can be made to work, it's not actually the preferred approach.\n",
    "- __Use the corpus to generate features for entity pairs.__ If instead our problem is to classify a pair of _entities_, then we can use all the examples from the corpus where those two entities co-occur to generate a feature representation describing the entity pair. This is the approach taken by [Mintz et al. 2009](https://www.aclweb.org/anthology/P09-1113), and it's the approach we'll pursue here.\n",
    "\n",
    "So we'll formulate our prediction problem such that the input is a pair of entities, and the goal is to predict what relation(s) the pair belongs to. The KB will provide the labels, and the corpus will provide the features."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = rel_ext.Dataset(corpus, kb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's determine how many examples we have for each triple in the KB. We'll compute averages per relation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                                             examples\n",
      "relation               examples    triples    /triple\n",
      "--------               --------    -------    -------\n",
      "adjoins                   58854       1702      34.58\n",
      "author                    11768       2671       4.41\n",
      "capital                    7443        522      14.26\n",
      "contains                  75952      18681       4.07\n",
      "film_performance           8994       3947       2.28\n",
      "founders                   5846       1960       2.98\n",
      "genre                      1576        824       1.91\n",
      "has_sibling                8525       2563       3.33\n",
      "has_spouse                12013       2994       4.01\n",
      "is_a                       5112       2542       2.01\n",
      "nationality                3403       1598       2.13\n",
      "parents                    3802       1586       2.40\n",
      "place_of_birth             1657       1097       1.51\n",
      "place_of_death             1523        831       1.83\n",
      "profession                 1851       1216       1.52\n",
      "worked_at                  3226       1150       2.81\n"
     ]
    }
   ],
   "source": [
    "dataset.count_examples()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For most relations, the total number of examples is fairly large, so we can be optimistic about learning what linguistic patterns express a given relation. However, for individual entity pairs, the number of examples is often quite low. Of course, more data would be better — much better! But more data could quickly become unwieldy to work with in a notebook like this."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Negative instances\n",
    "\n",
    "By joining the corpus to the KB, we can obtain abundant positive instances for each relation. But a classifier cannot be trained on positive instances alone. In order to apply the distant supervision paradigm, we will also need some negative instances — that is, entity pairs which do not belong to any known relation. If you like, you can think of these entity pairs as being assigned to a special relation called `NO_RELATION`. We can find plenty of such pairs by searching for examples in the corpus which contain two entities which do not belong to any relation in the KB."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found 247,405 unrelated pairs, including:\n",
      "    ('William_Randolph_Hearst', \"The_Cat's_Meow\")\n",
      "    ('Les_McCann', 'Bobby_Timmons')\n",
      "    ('Shatoy', 'Ibn_al-Khattab')\n",
      "    ('Sanrio', 'The_Rescuers_Down_Under')\n",
      "    ('Bishop', 'Demre')\n",
      "    ('Franschhoek', 'Constantia,_Cape_Town')\n",
      "    ('Rodriguez,_Rizal', 'Bulacan')\n",
      "    ('Devonport,_New_Zealand', 'Waiheke_Island')\n",
      "    ('Ottawa', 'North_York')\n",
      "    ('Confederate_States_of_America', 'Fort_Sumter')\n"
     ]
    }
   ],
   "source": [
    "unrelated_pairs = dataset.find_unrelated_pairs()\n",
    "print('Found {0:,} unrelated pairs, including:'.format(len(unrelated_pairs)))\n",
    "for pair in list(unrelated_pairs)[:10]:\n",
    "    print('   ', pair)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's a lot of negative instances! In fact, because these negative instances far outnumber our positive instances (that is, the triples in our KB), when we train models we'll wind up downsampling the negative instances substantially.\n",
    "\n",
    "Remember, though, that some of these supposedly negative instances may be false negatives. Our KB is not complete. A pair of entities might be related in real life even if they don't appear together in the KB."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Multi-label classification\n",
    "\n",
    "A given pair of entities can belong to more than one relation. In fact, this is quite common in our KB."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The most common relation combinations are:\n",
      "      1216 ('is_a', 'profession')\n",
      "       403 ('capital', 'contains')\n",
      "       143 ('place_of_birth', 'place_of_death')\n",
      "        61 ('nationality', 'place_of_birth')\n",
      "        11 ('adjoins', 'contains')\n",
      "         9 ('nationality', 'place_of_death')\n",
      "         7 ('has_sibling', 'has_spouse')\n",
      "         3 ('nationality', 'place_of_birth', 'place_of_death')\n",
      "         2 ('parents', 'worked_at')\n",
      "         1 ('nationality', 'worked_at')\n",
      "         1 ('has_spouse', 'parents')\n",
      "         1 ('author', 'founders')\n"
     ]
    }
   ],
   "source": [
    "dataset.count_relation_combinations()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While a few of those combinations look like data errors, most look natural and intuitive. Multiple relations per entity pair is a commonplace phenomenon.\n",
    "\n",
    "This observation strongly suggests formulating our prediction problem as [multi-label classification](https://en.wikipedia.org/wiki/Multi-label_classification). We could instead treat it as [multi-class classification](https://en.wikipedia.org/wiki/Multiclass_classification) — and indeed, [Mintz et al. 2009](https://www.aclweb.org/anthology/P09-1113) did so — but if we do, we'll be faced with the problem of assigning a single relation label to entity pairs which actually belong to multiple relations. It's not obvious how best to do this (and Mintz et al. 2009 did not make their method clear).\n",
    "\n",
    "There are a number of ways to approach multi-label classification, but the most obvious is the [binary relevance method](https://en.wikipedia.org/wiki/Multi-label_classification#Problem_transformation_methods), which just factors multi-label classification over _n_ labels into _n_ independent binary classification problems, one for each label. A disadvantage of this approach is that, by treating the binary classification problems as independent, it fails to exploit correlations between labels. But it has the great virtue of simplicity, and it will suffice for our purposes.\n",
    "\n",
    "So our problem will be to take as input an entity pair and a candidate relation (label), and to return a binary prediction as to whether the entity pair belongs to the relation. Since a KB triple is precisely a relation and a pair of entities, we could say equivalently that our prediction problem amounts to binary classification of KB triples. Given a candidate KB triple, do we predict that it is valid?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Building datasets\n",
    "\n",
    "We're now in a position to write a function to build datasets suitable for training and evaluating predictive models. These datasets will have the following characteristics:\n",
    "\n",
    "- Because we've formulated our problem as multi-label classification, and we'll be training separate models for each relation, we won't build a single dataset. Instead, we'll build a dataset for each relation, and our return value will be a map from relation names to datasets.\n",
    "- The dataset for each relation will consist of two parallel lists:\n",
    "  - A list of candidate `KBTriples` which combine the given relation with a pair of entities.\n",
    "  - A corresponding list of boolean labels indicating whether the given `KBTriple` belongs to the KB.\n",
    "- The dataset for each relation will include `KBTriples` derived from two sources:\n",
    "  - Positive instances will be drawn from the KB.\n",
    "  - Negative instances will be sampled from unrelated entity pairs, as described above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "kbts_by_rel, labels_by_rel = dataset.build_dataset(\n",
    "    include_positive=True, sampling_rate=0.1, seed=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "KBTriple(rel='adjoins', sbj='France', obj='Spain') True\n"
     ]
    }
   ],
   "source": [
    "print(kbts_by_rel['adjoins'][0], labels_by_rel['adjoins'][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "KBTriple(rel='capital', sbj='Wales', obj='Online_shopping') False\n"
     ]
    }
   ],
   "source": [
    "print(kbts_by_rel['capital'][637], labels_by_rel['capital'][637])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\\[ [top](#Relation-extraction-using-distant-supervision) \\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Evaluation\n",
    "\n",
    "Before we start building models, let's set up a test harness that allows us to measure a model's performance. This may seem backwards, but it's analogous to the software engineering paradigm of [test-driven development](https://en.wikipedia.org/wiki/Test-driven_development): first, define success; then, pursue it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Splitting the data\n",
    "\n",
    "Whenever building a model from data, it's good practice to partition the data into a multiple _splits_ — minimally, a training split on which to train the model, and a test split on which to evaluate it. In fact, we'll go a bit further, and define three splits:\n",
    "\n",
    "- __The `tiny` split (1%).__ It's often useful to carve out a tiny chunk of data to use in place of training or test data during development. Of course, any quantitative results obtained by evaluating on the `tiny` split are nearly meaningless, but because evaluations run extremely fast, using this split is a good way to flush out bugs during iterative cycles of code development.\n",
    "- __The `train` split (74%).__ We'll use the majority of our data for training models, both during development and at final evaluation. Experiments with the `train` split may take longer to run, but they'll have much greater statistical power.\n",
    "- __The `dev` split (25%).__ We'll use the `dev` split as test data for intermediate (formative) evaluations during development. During routine experiments, all evaluations should use the `dev` split.\n",
    "\n",
    "You could also carve out a `test` split for a final (summative) evaluation at the conclusion of your work. The bake-off will have its own test set, so you needn't do this, but this is an important step for projects without pre-defined test splits.\n",
    "\n",
    "Splitting our data assets is somewhat more complicated than in many other NLP problems, because we have both a corpus and KB. In order to minimize leakage of information from training data into test data, we'd like to split both the corpus and the KB. And in order to maximize the value of a finite quantity of data, we'd like to align the corpus splits and KB splits as closely as possible. In an ideal world, each split would have its own hermetically-sealed universe of entities, the corpus for that split would contain only examples mentioning those entities, and the KB for that split would contain only triples involving those entities. However, that ideal is not quite achievable in practice. In order to get as close as possible, we'll follow this plan:\n",
    "\n",
    "- First, we'll split the set of entities which appear as the subject in some KB triple.\n",
    "- Then, we'll split the set of KB triples based on their subject entity.\n",
    "- Finally, we'll split the set of corpus examples.\n",
    "  - If the first entity in the example has already been assigned to a split, we'll assign the example to the same split.\n",
    "  - Alternatively, if the second entity has already been assigned to a split, we'll assign the example to the same split.\n",
    "  - Otherwise, we'll assign the example to a split randomly.\n",
    "  \n",
    "<!-- \\[ TODO: figure out whether we actually need to split the _corpus_ -- any lift from testing on train corpus? \\] -->\n",
    "\n",
    "The `Dataset` method `build_splits` handles all of this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'tiny': Corpus with 3,474 examples; KB with 445 triples,\n",
       " 'train': Corpus with 249,003 examples; KB with 34,229 triples,\n",
       " 'dev': Corpus with 79,219 examples; KB with 11,210 triples,\n",
       " 'all': Corpus with 331,696 examples; KB with 45,884 triples}"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "splits = dataset.build_splits(\n",
    "    split_names=['tiny', 'train', 'dev'],\n",
    "    split_fracs=[0.01, 0.74, 0.25],\n",
    "    seed=1)\n",
    "\n",
    "splits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So now we can use `splits['train'].corpus` to refer to the training corpus, or `splits['dev'].kb` to refer to the dev KB."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Choosing evaluation metrics\n",
    "\n",
    "Because we've formulated our prediction problem as a family of binary classification problems, one for each relation (label), choosing evaluation metrics is pretty straightforward. The standard metrics for evaluating binary classification are [precision and recall](https://en.wikipedia.org/wiki/Precision_and_recall), which are more meaningful than simple accuracy, particularly in problems with a highly biased label distribution (like ours). We'll compute and report precision and recall separately for each relation (label). There are only two wrinkles:\n",
    "\n",
    "1. __How best to combine precision and recall into a single metric.__ Having two evaluation metrics is often inconvenient. If we're considering a change to our model which improves precision but degrades recall, should we take it? To drive an iterative development process, it's useful to have a single metric on which to hill-climb. For binary classification, the standard answer is the [F<sub>1</sub>-score](https://en.wikipedia.org/wiki/F1_score), which is the harmonic mean of precision and recall. However, the F<sub>1</sub>-score gives equal weight to precision and recall. For our purposes, precision is probably more important than recall. If we're extracting new relation triples from (massively abundant) text on the web in order to augment a knowledge base, it's probably more important that the triples we extract are correct (precision) than that we extract all the triples we could (recall). Accordingly, instead of the F<sub>1</sub>-score, we'll use the F<sub>0.5</sub>-score, which gives precision twice as much weight as recall.\n",
    "\n",
    "1. __How to aggregate metrics across relations (labels).__ Reporting metrics separately for each relation is great, but in order to drive iterative development, we'd also like to have summary metrics which aggregate across all relations. There are two possible ways to do it: _micro-averaging_ will give equal weight to all problem instances, and thus give greater weight to relations with more instances, while _macro-averaging_ will give equal weight to all relations, and thus give lesser weight to problem instances in relations with more instances. Because the number of problem instances per relation is, to some degree, an accident of our data collection methodology, we'll choose macro-averaging.\n",
    "\n",
    "Thus, while every evaluation will report lots of metrics, when we need a single metric on which to hill-climb, it will be the macro-averaged F<sub>0.5</sub>-score."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Running evaluations\n",
    "\n",
    "It's time to write some code to run evaluations and report results. This is now straightforward. The `rel_ext.evaluate()` function takes as inputs:\n",
    "\n",
    "- `splits`: a `dict` mapping split names to `Dataset` instances\n",
    "- `classifier`, which is just a function that takes a list of `KBTriples` and returns a list of boolean predictions\n",
    "- `test_split`, the split on which to evaluate the classifier, `dev` by default\n",
    "- `verbose`, a boolean indicating whether to print output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluating a random-guessing strategy\n",
    "\n",
    "In order to validate our evaluation framework, and to set a floor under expected results for future evaluations, let's implement and evaluate a random-guessing strategy. The random guesser is a classifier which completely ignores its input, and simply flips a coin."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lift(f):\n",
    "    return lambda xs: [f(x) for x in xs]\n",
    "\n",
    "def make_random_classifier(p=0.50):\n",
    "    def random_classify(kb_triple):\n",
    "        return random.random() < p\n",
    "    return lift(random_classify)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "relation              precision     recall    f-score    support       size\n",
      "------------------    ---------  ---------  ---------  ---------  ---------\n",
      "adjoins                   0.062      0.543      0.075        407       7057\n",
      "author                    0.095      0.519      0.113        657       7307\n",
      "capital                   0.019      0.508      0.023        126       6776\n",
      "contains                  0.402      0.501      0.419       4487      11137\n",
      "film_performance          0.127      0.494      0.149        984       7634\n",
      "founders                  0.064      0.484      0.078        469       7119\n",
      "genre                     0.031      0.507      0.038        205       6855\n",
      "has_sibling               0.085      0.494      0.102        625       7275\n",
      "has_spouse                0.098      0.481      0.116        754       7404\n",
      "is_a                      0.085      0.503      0.102        618       7268\n",
      "nationality               0.062      0.567      0.076        386       7036\n",
      "parents                   0.055      0.513      0.068        390       7040\n",
      "place_of_birth            0.045      0.550      0.055        282       6932\n",
      "place_of_death            0.030      0.502      0.037        209       6859\n",
      "profession                0.044      0.500      0.054        308       6958\n",
      "worked_at                 0.041      0.472      0.050        303       6953\n",
      "------------------    ---------  ---------  ---------  ---------  ---------\n",
      "macro-average             0.084      0.509      0.097      11210     117610\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.09720548338767715"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rel_ext.evaluate(splits, make_random_classifier())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The results are not too surprising. Recall is generally around 0.50, which makes sense: on any given example with label `True`, we are 50% likely to guess the right label. But precision is very poor, because most labels are not `True`, and because our classifier is completely ignorant of the features of specific problem instances. Accordingly, the F<sub>0.5</sub>-score is also very poor — first because even the equally-weighted F<sub>1</sub>-score is always closer to the lesser of precision and recall, and second because the F<sub>0.5</sub>-score weights precision twice as much as recall.\n",
    "\n",
    "Actually, the most remarkable result in this table is the comparatively good performance for the `contains` relation! What does this result tell us about the data?\n",
    "\n",
    "\\[ [top](#Relation-extraction-using-distant-supervision) \\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A simple baseline model\n",
    "\n",
    "It shouldn't be too hard to do better than random guessing. But for now, let's aim low — let's use the data we have in the easiest and most obvious way, and see how far that gets us.\n",
    "\n",
    "We start from the intuition that the words between two entity mentions frequently tell us how they're related. For example, in the phrase \"SpaceX was founded by Elon Musk\", the words \"was founded by\" indicate that the `founders` relation holds between the first entity mentioned and the second. Likewise, in the phrase \"Elon Musk established SpaceX\", the word \"established\" indicates the `founders` relation holds between the second entity mentioned and the first.\n",
    "\n",
    "So let's write some code to find the most common phrases that appear between the two entity mentions for each relation. As the examples illustrate, we need to make sure to consider both directions: that is, where the subject of the relation appears as the first mention, and where it appears as the second."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "adjoins              fwd         7667 ,\n",
      "adjoins              fwd         5134 and\n",
      "adjoins              fwd          903 , and\n",
      "adjoins              rev         4582 ,\n",
      "adjoins              rev         3000 and\n",
      "adjoins              rev          507 , and\n",
      "author               fwd         1007 by\n",
      "author               fwd          124 ,\n",
      "author               fwd          105 , by\n",
      "author               rev          816 's\n",
      "author               rev          210 ‘ s\n",
      "author               rev          142 ’ s\n",
      "capital              fwd           33 ,\n",
      "capital              fwd           17 , after\n",
      "capital              fwd           14 in\n",
      "capital              rev         2506 ,\n",
      "capital              rev          121 in\n",
      "capital              rev           73 , the capital of\n",
      "contains             fwd          319 's\n",
      "contains             fwd          296 ,\n",
      "contains             fwd          211 (\n",
      "contains             rev        18511 ,\n",
      "contains             rev         4160 in\n",
      "contains             rev          603 in the\n",
      "film_performance     fwd          283 in\n",
      "film_performance     fwd          151 's\n",
      "film_performance     fwd           96 film\n",
      "film_performance     rev          183 with\n",
      "film_performance     rev          128 , starring\n",
      "film_performance     rev           97 opposite\n",
      "founders             fwd           78 founder\n",
      "founders             fwd           56 co-founder\n",
      "founders             fwd           44 ,\n",
      "founders             rev          140 's\n",
      "founders             rev           66 ‘ s\n",
      "founders             rev           62 of the\n",
      "genre                fwd           20 , a\n",
      "genre                fwd           13 in 1994 , he became a central figure in the\n",
      "genre                fwd           11 is a\n",
      "genre                rev           98 ,\n",
      "genre                rev           60 series\n",
      "genre                rev           17 show\n",
      "has_sibling          fwd         1115 and\n",
      "has_sibling          fwd          545 ,\n",
      "has_sibling          fwd          125 , and\n",
      "has_sibling          rev          676 and\n",
      "has_sibling          rev          371 ,\n",
      "has_sibling          rev           68 , and\n",
      "has_spouse           fwd         1825 and\n",
      "has_spouse           fwd          379 ,\n",
      "has_spouse           fwd           97 and his wife\n",
      "has_spouse           rev         1183 and\n",
      "has_spouse           rev          225 ,\n",
      "has_spouse           rev           74 and his wife\n",
      "is_a                 fwd          100 ,\n",
      "is_a                 fwd           44 family ,\n",
      "is_a                 fwd           34 , a\n",
      "is_a                 rev          175 ,\n",
      "is_a                 rev           73 \n",
      "is_a                 rev           47 of\n",
      "nationality          fwd          264 of\n",
      "nationality          fwd           70 in\n",
      "nationality          fwd           27 from\n",
      "nationality          rev           51 ,\n",
      "nationality          rev           24 by\n",
      "nationality          rev           18 under\n",
      "parents              fwd           64 , son of\n",
      "parents              fwd           45 and\n",
      "parents              fwd           42 ,\n",
      "parents              rev          187 and\n",
      "parents              rev          151 ,\n",
      "parents              rev           42 and his son\n",
      "place_of_birth       fwd           85 of\n",
      "place_of_birth       fwd           50 was born in\n",
      "place_of_birth       fwd           35 in\n",
      "place_of_birth       rev           15 by\n",
      "place_of_birth       rev           15 ,\n",
      "place_of_birth       rev            9 -born Franciscan scholar\n",
      "place_of_death       fwd           65 in\n",
      "place_of_death       fwd           48 of\n",
      "place_of_death       fwd            9 at\n",
      "place_of_death       rev            9 ,\n",
      "place_of_death       rev            8 mayor\n",
      "place_of_death       rev            7 by\n",
      "profession           fwd           85 ,\n",
      "profession           fwd           27 , a\n",
      "profession           fwd           26 and\n",
      "profession           rev          101 ,\n",
      "profession           rev           67 \n",
      "profession           rev           24 and\n",
      "worked_at            fwd           94 of\n",
      "worked_at            fwd           57 at\n",
      "worked_at            fwd           57 's\n",
      "worked_at            rev           34 ,\n",
      "worked_at            rev           19 with\n",
      "worked_at            rev           18 co-founder\n"
     ]
    }
   ],
   "source": [
    "def find_common_middles(split, top_k=3, show_output=False):\n",
    "    corpus = split.corpus\n",
    "    kb = split.kb\n",
    "    mids_by_rel = {\n",
    "        'fwd': defaultdict(lambda: defaultdict(int)),\n",
    "        'rev': defaultdict(lambda: defaultdict(int))}\n",
    "    for rel in kb.all_relations:\n",
    "        for kbt in kb.get_triples_for_relation(rel):\n",
    "            for ex in corpus.get_examples_for_entities(kbt.sbj, kbt.obj):\n",
    "                mids_by_rel['fwd'][rel][ex.middle] += 1\n",
    "            for ex in corpus.get_examples_for_entities(kbt.obj, kbt.sbj):\n",
    "                mids_by_rel['rev'][rel][ex.middle] += 1\n",
    "    def most_frequent(mid_counter):\n",
    "        return sorted([(cnt, mid) for mid, cnt in mid_counter.items()], reverse=True)[:top_k]\n",
    "    for rel in kb.all_relations:\n",
    "        for dir in ['fwd', 'rev']:\n",
    "            top = most_frequent(mids_by_rel[dir][rel])\n",
    "            if show_output:\n",
    "                for cnt, mid in top:\n",
    "                    print('{:20s} {:5s} {:10d} {:s}'.format(rel, dir, cnt, mid))\n",
    "            mids_by_rel[dir][rel] = set([mid for cnt, mid in top])\n",
    "    return mids_by_rel\n",
    "\n",
    "_ = find_common_middles(splits['train'], show_output=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A few observations here:\n",
    "\n",
    "- Some of the most frequent middles are natural and intuitive. For example, \", son of\" indicates a forward `parents` relation, while \"and his son\" indicates a reverse `parents` relation.\n",
    "- Punctuation and stop words such as \"and\" and \"of\" are extremely common. Unlike some other NLP applications, it's probably a bad idea to throw these away — they carry lots of useful information.\n",
    "- However, punctuation and stop words tend to be highly ambiguous. For example, a bare comma is a likely middle for almost every relation in at least one direction.\n",
    "- A few of the results reflect quirks of the dataset. For example, the appearance of the phrase \"in 1994 , he became a central figure in the\" as a common middle for the `genre` relation reflects both the relative scarcity of examples for that relation, and an unfortunate tendency of the Wikilinks dataset to include duplicate or near-duplicate source documents. (That middle connects the entities [Ready to Die](https://en.wikipedia.org/wiki/Ready_to_Die) — the first studio album by the Notorious B.I.G. — and [East Coast hip hop](https://en.wikipedia.org/wiki/East_Coast_hip_hop).)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def train_top_k_middles_classifier(top_k=3):\n",
    "    split = splits['train']\n",
    "    corpus = split.corpus\n",
    "    top_k_mids_by_rel = find_common_middles(split=split, top_k=top_k)\n",
    "    def classify(kb_triple):\n",
    "        fwd_mids = top_k_mids_by_rel['fwd'][kb_triple.rel]\n",
    "        rev_mids = top_k_mids_by_rel['rev'][kb_triple.rel]\n",
    "        for ex in corpus.get_examples_for_entities(kb_triple.sbj, kb_triple.obj):\n",
    "            if ex.middle in fwd_mids:\n",
    "                return True\n",
    "        for ex in corpus.get_examples_for_entities(kb_triple.obj, kb_triple.sbj):\n",
    "            if ex.middle in rev_mids:\n",
    "                return True\n",
    "        return False\n",
    "    return lift(classify)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "relation              precision     recall    f-score    support       size\n",
      "------------------    ---------  ---------  ---------  ---------  ---------\n",
      "adjoins                   0.281      0.285      0.282        407       7057\n",
      "author                    0.327      0.078      0.199        657       7307\n",
      "capital                   0.102      0.159      0.110        126       6776\n",
      "contains                  0.614      0.064      0.225       4487      11137\n",
      "film_performance          0.417      0.005      0.024        984       7634\n",
      "founders                  0.150      0.038      0.095        469       7119\n",
      "genre                     0.000      0.000      0.000        205       6855\n",
      "has_sibling               0.270      0.176      0.244        625       7275\n",
      "has_spouse                0.361      0.211      0.316        754       7404\n",
      "is_a                      0.079      0.024      0.055        618       7268\n",
      "nationality               0.131      0.036      0.086        386       7036\n",
      "parents                   0.084      0.067      0.080        390       7040\n",
      "place_of_birth            0.021      0.007      0.015        282       6932\n",
      "place_of_death            0.031      0.014      0.025        209       6859\n",
      "profession                0.041      0.039      0.040        308       6958\n",
      "worked_at                 0.062      0.020      0.044        303       6953\n",
      "------------------    ---------  ---------  ---------  ---------  ---------\n",
      "macro-average             0.186      0.076      0.115      11210     117610\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.1149778794360431"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rel_ext.evaluate(splits, train_top_k_middles_classifier())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Not surprisingly, the performance of even this extremely simplistic model is noticeably better than random guessing. Of course, recall is much worse across the board, but precision and F<sub>0.5</sub>-score are sometimes much better. We observe big gains especially on `adjoins`, `author`, `has_sibling`, and `has_spouse`. Then again, at least one relation actually got worse. (Can you offer any explanation for that?)\n",
    "\n",
    "Admittedly, performance is still not great in absolute terms. However, we should have modest expectations for performance on this task — we are unlikely ever to get anywhere near perfect precision with perfect recall. Why?\n",
    "\n",
    "- High precision will be hard to achieve because the KB is incomplete: some entity pairs that are related in the world — and in the corpus — may simply be missing from the KB.\n",
    "- High recall will be hard to achieve because the corpus is finite: some entity pairs that are related in the KB may not have any examples in the corpus.\n",
    "\n",
    "Because of these unavoidable obstacles, what matters is not so much absolute performance, but relative performance of different approaches.\n",
    "\n",
    "__Question:__ What's the optimal value for `top_k`, the number of most frequent middles to consider? What choice maximizes our chosen figure of merit, the macro-averaged F<sub>0.5</sub>-score?\n",
    "\n",
    "\\[ [top](#Relation-extraction-using-distant-supervision) \\]"
   ]
  }
 ],
 "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.1"
  },
  "widgets": {
   "state": {},
   "version": "1.1.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}