Information-Extraction-using-Python-and-spaCy.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## spaCy’s Rule-Based Matching\n",
    "\n",
    "Before we get started, let’s talk about Marti Hearst. She is a computational linguistics researcher and a professor in the School of Information at the University of California, Berkeley. How does she fit into this article? I can sense you wondering.\n",
    "\n",
    "> Professor Marti has actually done extensive research on the topic of information extraction. One of her most interesting studies focuses on building a set of text-patterns that can be employed to extract meaningful information from text. **These patterns are popularly known as “Hearst Patterns”**.\n",
    "\n",
    "Let’s look at the example below:\n",
    "![](https://i2.wp.com/s3-ap-south-1.amazonaws.com/av-blog-media/wp-content/uploads/2019/09/example_1.png?resize=703%2C127&ssl=1)\n",
    "\n",
    "We can infer that “Gelidium” is a type of “red algae” just by looking at the structure of the sentence.\n",
    "\n",
    "> In linguistics terms, we will call “red algae” as Hypernym and “Gelidium” as its Hyponym.\n",
    "\n",
    "We can formalize this pattern as “X such as Y”, where X is the hypernym and Y is the hyponym. This was one of the many patterns from the Hearst Patterns. Here’s a list to give you an intuition behind the idea:\n",
    "\n",
    "![hearst patterns](https://i0.wp.com/s3-ap-south-1.amazonaws.com/av-blog-media/wp-content/uploads/2019/09/hearst_patterns.png?resize=566%2C321&ssl=1)\n",
    "\n",
    "\n",
    "\n",
    "Now let’s try to extract hypernym-hyponym pairs by using these patterns/rules. We will use spaCy’s rule-based matcher to perform this task.\n",
    "\n",
    "First, we will import the required libraries:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re \n",
    "import string \n",
    "import nltk \n",
    "import spacy \n",
    "import pandas as pd \n",
    "import numpy as np \n",
    "import math \n",
    "from tqdm import tqdm \n",
    "\n",
    "from spacy.matcher import Matcher \n",
    "from spacy.tokens import Span \n",
    "from spacy import displacy \n",
    "\n",
    "pd.set_option('display.max_colwidth', 200)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, load a spaCy model:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# load spaCy model\n",
    "nlp = spacy.load(\"en_core_web_sm\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are all set to mine information from text based on these Hearst Patterns.\n",
    "\n",
    "- __Pattern: X such as Y__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# sample text \n",
    "text = \"GDP in developing countries such as Vietnam will continue growing at a high rate.\" \n",
    "\n",
    "# create a spaCy object \n",
    "doc = nlp(text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To be able to pull out the desired information from the above sentence, it is really important to understand its syntactic structure – things like the subject, object, modifiers, and parts-of-speech (POS) in the sentence.\n",
    "\n",
    "We can easily explore these syntactic details in the sentence by using spaCy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "GDP --> nsubj --> NOUN\n",
      "in --> prep --> ADP\n",
      "developing --> amod --> VERB\n",
      "countries --> pobj --> NOUN\n",
      "such --> amod --> ADJ\n",
      "as --> prep --> ADP\n",
      "Vietnam --> pobj --> PROPN\n",
      "will --> aux --> VERB\n",
      "continue --> ROOT --> VERB\n",
      "growing --> xcomp --> VERB\n",
      "at --> prep --> ADP\n",
      "a --> det --> DET\n",
      "high --> amod --> ADJ\n",
      "rate --> pobj --> NOUN\n",
      ". --> punct --> PUNCT\n"
     ]
    }
   ],
   "source": [
    "# print token, dependency, POS tag \n",
    "for tok in doc: \n",
    "    print(tok.text, \"-->\",tok.dep_,\"-->\", tok.pos_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Have a look around the terms “such” and “as” . They are followed by a noun (“countries”). And after them, we have a proper noun (“Vietnam”) that acts as a hyponym.\n",
    "\n",
    "So, let’s create the required pattern using the dependency tags and the POS tags:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#define the pattern \n",
    "pattern = [{'POS':'NOUN'}, \n",
    "           {'LOWER': 'such'}, \n",
    "           {'LOWER': 'as'}, \n",
    "           {'POS': 'PROPN'} ] #proper noun"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let’s extract the pattern from the text:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "countries such as Vietnam\n"
     ]
    }
   ],
   "source": [
    "# Matcher class object \n",
    "matcher = Matcher(nlp.vocab) \n",
    "matcher.add(\"matching_1\", None, pattern) \n",
    "\n",
    "matches = matcher(doc) \n",
    "span = doc[matches[0][1]:matches[0][2]] \n",
    "\n",
    "print(span.text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nice! It works perfectly. However, if we could get “developing countries” instead of just “countries”, then the output would make more sense.\n",
    "\n",
    "So, we will now also capture the modifier of the noun just before “such as” by using the code below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "developing countries such as Vietnam\n"
     ]
    }
   ],
   "source": [
    "# Matcher class object\n",
    "matcher = Matcher(nlp.vocab)\n",
    "\n",
    "#define the pattern\n",
    "pattern = [{'DEP':'amod', 'OP':\"?\"}, # adjectival modifier\n",
    "           {'POS':'NOUN'},\n",
    "           {'LOWER': 'such'},\n",
    "           {'LOWER': 'as'},\n",
    "           {'POS': 'PROPN'}]\n",
    "\n",
    "matcher.add(\"matching_1\", None, pattern)\n",
    "matches = matcher(doc)\n",
    "\n",
    "span = doc[matches[0][1]:matches[0][2]]\n",
    "print(span.text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, “developing countries” is the hypernym and “Vietnam” is the hyponym. Both of them are semantically related.\n",
    "\n",
    "> _Note: The key ‘OP’: ‘?’ in the pattern above means that the modifier (‘amod’) can occur once or not at all._\n",
    "\n",
    "In a similar manner, we can get several pairs from any piece of text:\n",
    "\n",
    "**Fruits** such as **apples**\n",
    "**Cars** such as **Ferrari**\n",
    "**Flowers** such as **rose**\n",
    "\n",
    "Now let’s use some other Hearst Patterns to extract more hypernyms and hyponyms.\n",
    "\n",
    "- **Pattern: X and/or Y**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Here --> advmod --> ADV\n",
      "is --> ROOT --> VERB\n",
      "how --> advmod --> ADV\n",
      "you --> nsubj --> PRON\n",
      "can --> aux --> VERB\n",
      "keep --> csubj --> VERB\n",
      "your --> poss --> ADJ\n",
      "car --> dobj --> NOUN\n",
      "and --> cc --> CCONJ\n",
      "other --> amod --> ADJ\n",
      "vehicles --> conj --> NOUN\n",
      "clean --> oprd --> ADJ\n",
      ". --> punct --> PUNCT\n"
     ]
    }
   ],
   "source": [
    "doc = nlp(\"Here is how you can keep your car and other vehicles clean.\") \n",
    "\n",
    "# print dependency tags and POS tags\n",
    "for tok in doc: \n",
    "    print(tok.text, \"-->\",tok.dep_, \"-->\",tok.pos_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "car and other vehicles\n"
     ]
    }
   ],
   "source": [
    "# Matcher class object \n",
    "matcher = Matcher(nlp.vocab) \n",
    "\n",
    "#define the pattern \n",
    "pattern = [{'DEP':'amod', 'OP':\"?\"}, \n",
    "           {'POS':'NOUN'}, \n",
    "           {'LOWER': 'and', 'OP':\"?\"}, \n",
    "           {'LOWER': 'or', 'OP':\"?\"}, \n",
    "           {'LOWER': 'other'}, \n",
    "           {'POS': 'NOUN'}] \n",
    "           \n",
    "matcher.add(\"matching_1\", None, pattern) \n",
    "\n",
    "matches = matcher(doc) \n",
    "span = doc[matches[0][1]:matches[0][2]] \n",
    "print(span.text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let’s try out the same code to capture the “X or Y” pattern:\n",
    "\n",
    "The rest of the code will remain the same:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "car or other vehicles\n"
     ]
    }
   ],
   "source": [
    "# replaced 'and' with 'or'\n",
    "doc = nlp(\"Here is how you can keep your car or other vehicles clean.\")\n",
    "\n",
    "# Matcher class object \n",
    "matcher = Matcher(nlp.vocab) \n",
    "\n",
    "#define the pattern \n",
    "pattern = [{'DEP':'amod', 'OP':\"?\"}, \n",
    "           {'POS':'NOUN'}, \n",
    "           {'LOWER': 'and', 'OP':\"?\"}, \n",
    "           {'LOWER': 'or', 'OP':\"?\"}, \n",
    "           {'LOWER': 'other'}, \n",
    "           {'POS': 'NOUN'}] \n",
    "           \n",
    "matcher.add(\"matching_1\", None, pattern) \n",
    "\n",
    "matches = matcher(doc) \n",
    "span = doc[matches[0][1]:matches[0][2]] \n",
    "print(span.text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Excellent – it works!\n",
    "\n",
    "- **Pattern: X, including Y**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Eight --> nummod --> NUM\n",
      "people --> nsubjpass --> NOUN\n",
      ", --> punct --> PUNCT\n",
      "including --> prep --> VERB\n",
      "two --> nummod --> NUM\n",
      "children --> pobj --> NOUN\n",
      ", --> punct --> PUNCT\n",
      "were --> auxpass --> VERB\n",
      "injured --> ROOT --> VERB\n",
      "in --> prep --> ADP\n",
      "the --> det --> DET\n",
      "explosion --> pobj --> NOUN\n"
     ]
    }
   ],
   "source": [
    "doc = nlp(\"Eight people, including two children, were injured in the explosion\") \n",
    "\n",
    "for tok in doc: \n",
    "    print(tok.text, \"-->\",tok.dep_, \"-->\",tok.pos_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Eight people, including two children\n"
     ]
    }
   ],
   "source": [
    "# Matcher class object \n",
    "matcher = Matcher(nlp.vocab) \n",
    "\n",
    "#define the pattern \n",
    "pattern = [{'DEP':'nummod','OP':\"?\"}, # numeric modifier \n",
    "           {'DEP':'amod','OP':\"?\"}, # adjectival modifier \n",
    "           {'POS':'NOUN'}, \n",
    "           {'IS_PUNCT': True}, \n",
    "           {'LOWER': 'including'}, \n",
    "           {'DEP':'nummod','OP':\"?\"}, \n",
    "           {'DEP':'amod','OP':\"?\"}, \n",
    "           {'POS':'NOUN'}]            \n",
    "\n",
    "matcher.add(\"matching_1\", None, pattern) \n",
    "\n",
    "matches = matcher(doc) \n",
    "span = doc[matches[0][1]:matches[0][2]] \n",
    "print(span.text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Pattern: X, especially Y**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A --> det --> DET\n",
      "healthy --> amod --> ADJ\n",
      "eating --> compound --> NOUN\n",
      "pattern --> nsubj --> NOUN\n",
      "includes --> ROOT --> VERB\n",
      "fruits --> dobj --> NOUN\n",
      ", --> punct --> PUNCT\n",
      "especially --> advmod --> ADV\n",
      "whole --> amod --> ADJ\n",
      "fruits --> appos --> NOUN\n",
      ". --> punct --> PUNCT\n"
     ]
    }
   ],
   "source": [
    "doc = nlp(\"A healthy eating pattern includes fruits, especially whole fruits.\") \n",
    "\n",
    "for tok in doc: \n",
    "    print(tok.text, \"-->\",tok.dep_, \"-->\",tok.pos_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fruits, especially whole fruits\n"
     ]
    }
   ],
   "source": [
    "# Matcher class object \n",
    "matcher = Matcher(nlp.vocab) \n",
    "\n",
    "#define the pattern \n",
    "pattern = [\n",
    "           {'DEP':'nummod','OP':\"?\"}, \n",
    "           {'DEP':'amod','OP':\"?\"}, \n",
    "           {'POS':'NOUN'}, \n",
    "           {'IS_PUNCT': True}, \n",
    "           {'LOWER': 'especially'}, \n",
    "           {'DEP':'nummod','OP':\"?\"}, \n",
    "           {'DEP':'amod','OP':\"?\"}, \n",
    "           {'POS':'NOUN'}]            \n",
    "\n",
    "matcher.add(\"matching_1\", None, pattern) \n",
    "\n",
    "matches = matcher(doc) \n",
    "span = doc[matches[0][1]:matches[0][2]] \n",
    "print(span.text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Subtree Matching for Relation Extraction\n",
    "The simple rule-based methods work well for information extraction tasks. However, they have a few drawbacks and shortcomings.\n",
    "\n",
    "We have to be extremely creative to come up with new rules to capture different patterns. It is difficult to build patterns that generalize well across different sentences.\n",
    "\n",
    "To enhance the rule-based methods for relation/information extraction, we should try to understand the dependency structure of the sentences at hand.\n",
    "\n",
    "Let’s take a sample text and build its dependency graphing tree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" id=\"0\" class=\"displacy\" width=\"1100\" height=\"399.5\" style=\"max-width: none; height: 399.5px; color: #000000; background: #ffffff; font-family: Arial\">\n",
       "<text class=\"displacy-token\" fill=\"currentColor\" text-anchor=\"middle\" y=\"309.5\">\n",
       "    <tspan class=\"displacy-word\" fill=\"currentColor\" x=\"50\">Tableau</tspan>\n",
       "    <tspan class=\"displacy-tag\" dy=\"2em\" fill=\"currentColor\" x=\"50\">PROPN</tspan>\n",
       "</text>\n",
       "\n",
       "<text class=\"displacy-token\" fill=\"currentColor\" text-anchor=\"middle\" y=\"309.5\">\n",
       "    <tspan class=\"displacy-word\" fill=\"currentColor\" x=\"225\">was</tspan>\n",
       "    <tspan class=\"displacy-tag\" dy=\"2em\" fill=\"currentColor\" x=\"225\">VERB</tspan>\n",
       "</text>\n",
       "\n",
       "<text class=\"displacy-token\" fill=\"currentColor\" text-anchor=\"middle\" y=\"309.5\">\n",
       "    <tspan class=\"displacy-word\" fill=\"currentColor\" x=\"400\">recently</tspan>\n",
       "    <tspan class=\"displacy-tag\" dy=\"2em\" fill=\"currentColor\" x=\"400\">ADV</tspan>\n",
       "</text>\n",
       "\n",
       "<text class=\"displacy-token\" fill=\"currentColor\" text-anchor=\"middle\" y=\"309.5\">\n",
       "    <tspan class=\"displacy-word\" fill=\"currentColor\" x=\"575\">acquired</tspan>\n",
       "    <tspan class=\"displacy-tag\" dy=\"2em\" fill=\"currentColor\" x=\"575\">VERB</tspan>\n",
       "</text>\n",
       "\n",
       "<text class=\"displacy-token\" fill=\"currentColor\" text-anchor=\"middle\" y=\"309.5\">\n",
       "    <tspan class=\"displacy-word\" fill=\"currentColor\" x=\"750\">by</tspan>\n",
       "    <tspan class=\"displacy-tag\" dy=\"2em\" fill=\"currentColor\" x=\"750\">ADP</tspan>\n",
       "</text>\n",
       "\n",
       "<text class=\"displacy-token\" fill=\"currentColor\" text-anchor=\"middle\" y=\"309.5\">\n",
       "    <tspan class=\"displacy-word\" fill=\"currentColor\" x=\"925\">Salesforce.</tspan>\n",
       "    <tspan class=\"displacy-tag\" dy=\"2em\" fill=\"currentColor\" x=\"925\">PROPN</tspan>\n",
       "</text>\n",
       "\n",
       "<g class=\"displacy-arrow\">\n",
       "    <path class=\"displacy-arc\" id=\"arrow-0-0\" stroke-width=\"2px\" d=\"M70,264.5 C70,2.0 575.0,2.0 575.0,264.5\" fill=\"none\" stroke=\"currentColor\"/>\n",
       "    <text dy=\"1.25em\" style=\"font-size: 0.8em; letter-spacing: 1px\">\n",
       "        <textPath xlink:href=\"#arrow-0-0\" class=\"displacy-label\" startOffset=\"50%\" fill=\"currentColor\" text-anchor=\"middle\">nsubjpass</textPath>\n",
       "    </text>\n",
       "    <path class=\"displacy-arrowhead\" d=\"M70,266.5 L62,254.5 78,254.5\" fill=\"currentColor\"/>\n",
       "</g>\n",
       "\n",
       "<g class=\"displacy-arrow\">\n",
       "    <path class=\"displacy-arc\" id=\"arrow-0-1\" stroke-width=\"2px\" d=\"M245,264.5 C245,89.5 570.0,89.5 570.0,264.5\" fill=\"none\" stroke=\"currentColor\"/>\n",
       "    <text dy=\"1.25em\" style=\"font-size: 0.8em; letter-spacing: 1px\">\n",
       "        <textPath xlink:href=\"#arrow-0-1\" class=\"displacy-label\" startOffset=\"50%\" fill=\"currentColor\" text-anchor=\"middle\">auxpass</textPath>\n",
       "    </text>\n",
       "    <path class=\"displacy-arrowhead\" d=\"M245,266.5 L237,254.5 253,254.5\" fill=\"currentColor\"/>\n",
       "</g>\n",
       "\n",
       "<g class=\"displacy-arrow\">\n",
       "    <path class=\"displacy-arc\" id=\"arrow-0-2\" stroke-width=\"2px\" d=\"M420,264.5 C420,177.0 565.0,177.0 565.0,264.5\" fill=\"none\" stroke=\"currentColor\"/>\n",
       "    <text dy=\"1.25em\" style=\"font-size: 0.8em; letter-spacing: 1px\">\n",
       "        <textPath xlink:href=\"#arrow-0-2\" class=\"displacy-label\" startOffset=\"50%\" fill=\"currentColor\" text-anchor=\"middle\">advmod</textPath>\n",
       "    </text>\n",
       "    <path class=\"displacy-arrowhead\" d=\"M420,266.5 L412,254.5 428,254.5\" fill=\"currentColor\"/>\n",
       "</g>\n",
       "\n",
       "<g class=\"displacy-arrow\">\n",
       "    <path class=\"displacy-arc\" id=\"arrow-0-3\" stroke-width=\"2px\" d=\"M595,264.5 C595,177.0 740.0,177.0 740.0,264.5\" fill=\"none\" stroke=\"currentColor\"/>\n",
       "    <text dy=\"1.25em\" style=\"font-size: 0.8em; letter-spacing: 1px\">\n",
       "        <textPath xlink:href=\"#arrow-0-3\" class=\"displacy-label\" startOffset=\"50%\" fill=\"currentColor\" text-anchor=\"middle\">agent</textPath>\n",
       "    </text>\n",
       "    <path class=\"displacy-arrowhead\" d=\"M740.0,266.5 L748.0,254.5 732.0,254.5\" fill=\"currentColor\"/>\n",
       "</g>\n",
       "\n",
       "<g class=\"displacy-arrow\">\n",
       "    <path class=\"displacy-arc\" id=\"arrow-0-4\" stroke-width=\"2px\" d=\"M770,264.5 C770,177.0 915.0,177.0 915.0,264.5\" fill=\"none\" stroke=\"currentColor\"/>\n",
       "    <text dy=\"1.25em\" style=\"font-size: 0.8em; letter-spacing: 1px\">\n",
       "        <textPath xlink:href=\"#arrow-0-4\" class=\"displacy-label\" startOffset=\"50%\" fill=\"currentColor\" text-anchor=\"middle\">pobj</textPath>\n",
       "    </text>\n",
       "    <path class=\"displacy-arrowhead\" d=\"M915.0,266.5 L923.0,254.5 907.0,254.5\" fill=\"currentColor\"/>\n",
       "</g>\n",
       "</svg>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "text = \"Tableau was recently acquired by Salesforce.\" \n",
    "\n",
    "# Plot the dependency graph \n",
    "doc = nlp(text) \n",
    "displacy.render(doc, style='dep', jupyter=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can you find any interesting relation in this sentence?\n",
    "\n",
    "If you look at the entities in the sentence – Tableau and Salesforce – they are related by the term ‘acquired’. So, the pattern I can extract from this sentence is either “Salesforce acquired Tableau” or “X acquired Y”.\n",
    "\n",
    "Now consider this statement: “Careem, a ride-hailing major in the middle east, was acquired by Uber.”\n",
    "\n",
    "Its dependency graph will look something like this:\n",
    "\n",
    "![dependency tree nlp](https://i1.wp.com/s3-ap-south-1.amazonaws.com/av-blog-media/wp-content/uploads/2019/09/DG_2.png?resize=679%2C191&ssl=1)\n",
    "\n",
    "Pretty scary, right?\n",
    "\n",
    "Don’t worry! All we have to check is which dependency paths are common between multiple sentences. This method is known as Subtree matching.\n",
    "\n",
    "For instance, if we compare this statement with the previous one:\n",
    "![information extraction](https://i0.wp.com/s3-ap-south-1.amazonaws.com/av-blog-media/wp-content/uploads/2019/09/DG_3.png?resize=675%2C193&ssl=1)\n",
    "\n",
    "\n",
    "![information extraction](https://i2.wp.com/s3-ap-south-1.amazonaws.com/av-blog-media/wp-content/uploads/2019/09/DG_4.png?resize=531%2C170&ssl=1)\n",
    "\n",
    "We will just consider the common dependency paths and extract the entities and the relation (acquired) between them. Hence, the relations extracted from these sentences are:\n",
    "\n",
    "- **Salesforce acquired Tableau**\n",
    "- **Uber acquired Careem**\n",
    "\n",
    "Let’s try to implement this technique in Python. We will again use spaCy as it makes it pretty easy to traverse a dependency tree.\n",
    "\n",
    "We will start by taking a look at the dependency tags and POS tags of the words in the sentence:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tableau --> nsubjpass --> PROPN\n",
      "was --> auxpass --> VERB\n",
      "recently --> advmod --> ADV\n",
      "acquired --> ROOT --> VERB\n",
      "by --> agent --> ADP\n",
      "Salesforce --> pobj --> PROPN\n",
      ". --> punct --> PUNCT\n"
     ]
    }
   ],
   "source": [
    "text = \"Tableau was recently acquired by Salesforce.\" \n",
    "doc = nlp(text) \n",
    "\n",
    "for tok in doc: \n",
    "    print(tok.text,\"-->\",tok.dep_,\"-->\",tok.pos_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, the dependency tag for “Tableau” is _nsubjpass_ which stands for a passive subject (as it is a passive sentence). The other entity “Salesforce” is the _object_ in this sentence and the term “acquired” is the ROOT of the sentence which means it somehow connects the object and the subject.\n",
    "\n",
    "Let’s define a function to perform subtree matching:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "def subtree_matcher(doc): \n",
    "    x = '' \n",
    "    y = '' \n",
    "\n",
    "    # iterate through all the tokens in the input sentence \n",
    "    for i,tok in enumerate(doc): \n",
    "        # extract subject \n",
    "        if tok.dep_.find(\"subjpass\") == True: \n",
    "            y = tok.text \n",
    "\n",
    "        # extract object \n",
    "        if tok.dep_.endswith(\"obj\") == True: \n",
    "            x = tok.text \n",
    "\n",
    "    return x,y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this case, we just have to find all those sentences that:\n",
    "\n",
    "- Have two entities, and\n",
    "- The term “acquired” as the only ROOT in the sentence\n",
    "\n",
    "We can then capture the subject and the object from the sentences. Let’s call the above function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('Salesforce', 'Tableau')"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "subtree_matcher(doc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, the subject is the acquirer and the object is the entity that is getting acquired. Let’s use the same function, subtree_matcher( ), to extract entities related by the same relation (“acquired”):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('Uber', 'Careem')"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text_2 = \"Careem, a ride hailing major in middle east, was acquired by Uber.\" \n",
    "\n",
    "doc_2 = nlp(text_2) \n",
    "subtree_matcher(doc_2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Did you see what happened here? This sentence had more words and punctuation marks but still, our logic worked and successfully extracted the related entities.\n",
    "\n",
    "But wait – what if I change the sentence from passive to active voice? Will our logic still work?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('Tableau', '')"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text_3 = \"Salesforce recently acquired Tableau.\" \n",
    "doc_3 = nlp(text_3) \n",
    "subtree_matcher(doc_3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That’s not quite what we expected. The function has failed to capture ‘Salesforce’ and wrongly returned ‘Tableau’ as the acquirer.\n",
    "\n",
    "So, what could go wrong? Let’s understand the dependency tree of this sentence:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Salesforce --> nsubj --> PROPN\n",
      "recently --> advmod --> ADV\n",
      "acquired --> ROOT --> VERB\n",
      "Tableau --> dobj --> PROPN\n",
      ". --> punct --> PUNCT\n"
     ]
    }
   ],
   "source": [
    "for tok in doc_3:    \n",
    "    print(tok.text, \"-->\",tok.dep_, \"-->\",tok.pos_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It turns out that the grammatical functions (subject and object) of the terms ‘Salesforce’ and ‘Tableau’ have been interchanged in the active voice. However, now the dependency tag for the subject has changed to ‘nsubj’ from ‘nsubjpass’. This tag indicates that the sentence is in the active voice.\n",
    "\n",
    "We can use this property to modify our subtree matching function. Given below is the new function for subtree matching:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def new_subtree_matcher(doc):\n",
    "    subjpass = 0\n",
    "\n",
    "    for i,tok in enumerate(doc):\n",
    "    # find dependency tag that contains the text \"subjpass\"    \n",
    "        if tok.dep_.find(\"subjpass\") == True:\n",
    "            subjpass = 1\n",
    "\n",
    "    x = ''\n",
    "    y = ''\n",
    "\n",
    "    # if subjpass == 1 then sentence is passive\n",
    "    if subjpass == 1:\n",
    "        for i,tok in enumerate(doc):\n",
    "            if tok.dep_.find(\"subjpass\") == True:\n",
    "                y = tok.text\n",
    "\n",
    "            if tok.dep_.endswith(\"obj\") == True:\n",
    "                x = tok.text\n",
    "\n",
    "    # if subjpass == 0 then sentence is not passive\n",
    "    else:\n",
    "        for i,tok in enumerate(doc):\n",
    "            if tok.dep_.endswith(\"subj\") == True:\n",
    "                x = tok.text\n",
    "\n",
    "            if tok.dep_.endswith(\"obj\") == True:\n",
    "                y = tok.text\n",
    "\n",
    "    return x,y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let’s try this new function on the active voice sentence:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('Salesforce', 'Tableau')"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "new_subtree_matcher(doc_3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great! The output is correct. Let’s pass the previous passive sentence to this function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('Salesforce', 'Tableau')"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "new_subtree_matcher(nlp(\"Tableau was recently acquired by Salesforce.\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That’s exactly what we were looking for. We have made the function slightly more general. I would urge you to deep dive into the grammatical structure of different types of sentences and try to make this function more flexible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}