Open Information Extraction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Open Information Extraction\n",
    "* Goal: finding any kind of (not predefined) relations between entities\n",
    "* In practice these relations are usually triples (entity1, relation, entity2)\n",
    "* Existing methods vary on how the relation (or lack of it) is discovered\n",
    "* Many systems rely on finding relation phrases between the entities\n",
    "    * Lets have a look: http://openie.allenai.org/\n",
    "* Simple solution:\n",
    "    * Train a classifier (for instance CRF) to tag relation phrases between entities\n",
    "    * How do we get training data for any type of relation?\n",
    "        * No practical way of manually annotating enough data\n",
    "        * Lets use heuristics:\n",
    "            * Find all co-occuring entity pairs and look at their shortest dependency paths\n",
    "            * If the path matches certain criteria (e.g. not too long) assume the pair to be positive example\n",
    "            * Otherwise assume the pair to be negative, i.e. there is no relation between them\n",
    "    * If we do not use lexical features the classifier will hopefully generalize to any type of relation\n",
    "        * POS tags, chunking, dependencies are still valid features\n",
    "* Issues with OpenIE\n",
    "    * Relations are based on the detected phrases, they have to be identical to aggregate the information (we have learned to measure the similarities between phrases, so this is not strictly true)\n",
    "    * Many of the relations are completely irrelevant:\n",
    "        * [http://openie.allenai.org/search?arg1=Othello&rel=&arg2=Shakespeare&corpora=](http://openie.allenai.org/search?arg1=Othello&rel=&arg2=Shakespeare&corpora=)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Aggregating information: relational clustering\n",
    "* Sometimes we know that a pair of entities co-occurs multiple times, could we use all this information to decide the relation?\n",
    "* We can surely try...\n",
    "* In the next example we are interested in location entities (countries, cities etc.)\n",
    "* Lets gather all **surface patterns** of the relations for our entity pairs\n",
    "    * In this example we've chosen lexicalized dependency paths, e.g. *&lt;nmod sijaita >nmod* (sijaita = located in)\n",
    "    * Bag-of-words might do the trick just as well.\n",
    "* If we fill a matrix with this data we end up with entity pairs as rows and surface patterns as columns\n",
    "    * If a pair of entities occurs in a given pattern, that cell in the matrix will have value 1 (or frequency etc.)\n",
    "    * What we end up with is basically a feature matrix for each pair -> lets cluster them\n",
    "* Now our relations are based on the aggregated information of all surface patterns, we can't pinpoint a single textual mention explicitly describing the relation (it might not even exist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We already know how to extract named entities (NER lectures) and we also know how to find the surface patterns (feature generation for supervised relation extraction). Here we have it all pulled together:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Reading data\n",
      "Unique relations: 2163262\n",
      "Unique pairs: 2681141\n",
      "Pairs total: 3985380\n",
      "Eurooppa Afrikka <nmod:poss maa <dobj muuttaa >xcomp kaltainen >nmod:poss maa >nmod:poss\n",
      "Afrikka Eurooppa <nmod:poss maa <nmod:poss kaltainen <xcomp muuttaa >dobj maa >nmod:poss\n",
      "Tampere Pohjois-Satakunnan <nmod:poss markkina-alue <nmod:poss paikallis#radio >nmod radio >appos oy >compound:nn viestintä >nmod:poss\n",
      "Pohjois-Satakunnan Tampere <nmod:poss viestintä <compound:nn oy <appos radio <nmod paikallis#radio >nmod:poss markkina-alue >nmod:poss\n",
      "Pori Oulu <nmod tulla >nmod\n",
      "Oulu Pori <nmod tulla >nmod\n",
      "Slovakia Puola <nmod pitää >nmod\n",
      "Puola Slovakia <nmod pitää >nmod\n",
      "Suomi Japani <nmod olla >nmod\n",
      "Japani Suomi <nmod olla >nmod\n"
     ]
    }
   ],
   "source": [
    "import pickle\n",
    "import numpy as np\n",
    "\n",
    "from collections import Counter, defaultdict\n",
    "\n",
    "from sklearn.cluster import MiniBatchKMeans\n",
    "from sklearn.feature_extraction import DictVectorizer\n",
    "from sklearn.preprocessing import normalize\n",
    "\n",
    "print \"Reading data\"\n",
    "pairs = pickle.load(open('pairs.pkl'))\n",
    "\n",
    "rel_counter = Counter([p[2] for p in pairs])\n",
    "pair_counter = Counter([(p[0][3], p[1][3]) for p in pairs])\n",
    "\n",
    "print \"Unique relations: %s\" % len(rel_counter.keys())\n",
    "print \"Unique pairs: %s\" % len(pair_counter.keys())\n",
    "print \"Pairs total: %s\" % len(pairs)\n",
    "\n",
    "loc_pairs = [p for p in pairs if p[0][1] == 'loc' and p[1][1] == 'loc' and rel_counter[p[2]] >= 10\n",
    "             and pair_counter[(p[0][3], p[1][3])] >= 10 and 'conj' not in p[2] and len(p[2].split(' ')) >= 3]\n",
    "\n",
    "for pair in loc_pairs[:10]:\n",
    "    print pair[0][3].decode('utf-8'), pair[1][3].decode('utf-8'), pair[2].decode('utf-8')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* *loc_pairs* is a filtered list of entity pairs collected from a large text corpus (Thanks Jenna!):\n",
    "    * only location entities are included\n",
    "    * only surface patterns and entity pairs which occur at least 10 times are included\n",
    "    * only surface patterns with one or more words between the entities are included\n",
    "    * No conjunction surface forms are included\n",
    "* These filterings are arbitrary results of trial and error!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Clustering...\n",
      "Feature matrix shape: 1268, 764\n",
      "Done!\n"
     ]
    }
   ],
   "source": [
    "print \"Clustering...\"\n",
    "pair_dict = defaultdict(dict)\n",
    "\n",
    "for p in loc_pairs:\n",
    "    pair_dict[(p[0][3], p[1][3])][p[2]]=1\n",
    "\n",
    "pair_list = pair_dict.keys()\n",
    "vectorizer = DictVectorizer()\n",
    "features = normalize(vectorizer.fit_transform(pair_dict.values()))\n",
    "\n",
    "print \"Feature matrix shape: %s, %s\" % features.shape\n",
    "\n",
    "n_clusters = 20\n",
    "c = MiniBatchKMeans(n_clusters=n_clusters)\n",
    "\n",
    "clusters = c.fit_predict(features)\n",
    "\n",
    "print \"Done!\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(10, 20)\n",
      "************** 0 ***********\n",
      ">>  762 >>  Lappeenranta \tHelsinki\n",
      ">>  265 >>  Espanja \tRanska\n",
      ">>  654 >>  Oulu \tRaahe\n",
      ">>  286 >>  Rovaniemi \tKajaani\n",
      ">>  758 >>  Helsinki \tLappeenranta\n",
      ">>  387 >>  Yhdysvalta \tRanska\n",
      ">>  1113 >>  Hämeenlinna \tKuopio\n",
      ">>  554 >>  Japani \tRuotsi\n",
      ">>  250 >>  Ranska \tEspanja\n",
      ">>  1110 >>  Espoo \tVaasa\n",
      "************** 1 ***********\n",
      ">>  558 >>  vannas#joki \tHelsinki\n",
      ">>  44 >>  Helsinki \tKonala\n",
      ">>  182 >>  Punkaharju \tSavonlinna\n",
      ">>  432 >>  Tansania \tSambia\n",
      ">>  47 >>  Helsinki \tvannas#joki\n",
      ">>  1258 >>  Valko-Venäjällä \tSuomi\n",
      ">>  413 >>  Pori \tJyväskylä\n",
      ">>  631 >>  Islanti \tGrönlanti\n",
      ">>  193 >>  Sambia \tTansania\n",
      ">>  752 >>  Helsinki \tPohjanmaa\n",
      "************** 2 ***********\n",
      ">>  197 >>  Tampere \tHämeenlinna\n",
      ">>  887 >>  Mikkeli \tSavonlinna\n",
      ">>  180 >>  Jyväskylä \tEspoo\n",
      ">>  468 >>  Yhdysvalta \tBoston\n",
      ">>  729 >>  Hämeenlinna \tTampere\n",
      ">>  1048 >>  Boston \tYhdysvalta\n",
      ">>  375 >>  Syyria \tEgypti\n",
      ">>  666 >>  Espoo \tJyväskylä\n",
      ">>  842 >>  Helsinki \tArabia\n",
      ">>  479 >>  Arabia \tHelsinki\n",
      "************** 3 ***********\n",
      ">>  875 >>  Helsinki \tLahti\n",
      ">>  1034 >>  Helsinki \tPorvoo\n",
      ">>  1014 >>  itä#valta \tRanska\n",
      ">>  323 >>  Lahti \tHelsinki\n",
      ">>  469 >>  Tanska \titä#valta\n",
      ">>  492 >>  Ranska \tTanska\n",
      ">>  1234 >>  Porvoo \tHelsinki\n",
      ">>  522 >>  Suomi \tTammisaari\n",
      ">>  628 >>  Ranska \titä#valta\n",
      ">>  653 >>  Suomi \tTansania\n",
      "************** 4 ***********\n",
      ">>  681 >>  USA \tSyyria\n",
      ">>  1095 >>  Venäjä \tIsrael\n",
      ">>  939 >>  Venäjä \tTshetshenia\n",
      ">>  614 >>  Venäjä \tAfganistan\n",
      ">>  1050 >>  Israel \tIran\n",
      ">>  1052 >>  Venäjä \tGeorgia\n",
      ">>  954 >>  Afganistan \tVenäjä\n",
      ">>  865 >>  Israel \tSyyria\n",
      ">>  1159 >>  USA \tAfganistan\n",
      ">>  726 >>  Tshetshenia \tVenäjä\n",
      "************** 5 ***********\n",
      ">>  458 >>  Amerikka \tKiina\n",
      ">>  254 >>  Kiina \tViro\n",
      ">>  1122 >>  pohjois#maa \tIslanti\n",
      ">>  202 >>  Japani \tRanska\n",
      ">>  988 >>  Islanti \tpohjois#maa\n",
      ">>  1016 >>  Viro \tKiina\n",
      ">>  798 >>  Ranska \tJapani\n",
      ">>  777 >>  Kiina \tAmerikka\n",
      ">>  515 >>  Ranska \tBelgia\n",
      ">>  913 >>  Belgia \tRanska\n",
      "************** 6 ***********\n",
      ">>  506 >>  Englanti \tAmerikka\n",
      ">>  1036 >>  Britannia \tRanska\n",
      ">>  732 >>  Englanti \tEnglanti\n",
      ">>  333 >>  Japani \tAfrikka\n",
      ">>  1011 >>  Oulu \tPori\n",
      ">>  268 >>  Ranska \tBritannia\n",
      ">>  360 >>  Tsekki \tEurooppa\n",
      ">>  263 >>  Seelanti \tUSA\n",
      ">>  814 >>  Amerikka \tEnglanti\n",
      ">>  855 >>  Pori \tOulu\n",
      "************** 7 ***********\n",
      ">>  567 >>  Suomi \tHamina\n",
      ">>  289 >>  Naantali \tRymättylä\n",
      ">>  803 >>  Rymättylä \tNaantali\n",
      ">>  663 >>  Islanti \tIrlanti\n",
      ">>  352 >>  Kolumbia \tArgentiina\n",
      ">>  419 >>  Kolumbia \tYhdysvalta\n",
      ">>  439 >>  Irlanti \tIslanti\n",
      ">>  114 >>  Argentiina \tKolumbia\n",
      ">>  1086 >>  Yhdysvalta \tArgentiina\n",
      ">>  947 >>  Argentiina \tYhdysvalta\n",
      "************** 8 ***********\n",
      ">>  113 >>  Tanska \tIslanti\n",
      ">>  1185 >>  Katariina \tSuomi\n",
      ">>  185 >>  Japani \tSaksa\n",
      ">>  593 >>  Irlanti \tUSA\n",
      ">>  679 >>  Aasia \tPohjois-Amerikassa\n",
      ">>  818 >>  Lappeenranta \tLappeenranta\n",
      ">>  1112 >>  keski \tSuomi\n",
      ">>  70 >>  Oulu \tVantaa\n",
      ">>  1151 >>  Kashmir \tIntia\n",
      ">>  1229 >>  Ukraina \tKiovassa\n",
      "************** 9 ***********\n",
      ">>  365 >>  Australia \tSeelanti\n",
      ">>  216 >>  Helsinki \tPori\n",
      ">>  721 >>  Helsinki \tVenäjä\n",
      ">>  498 >>  Maarianhamina \tTurku\n",
      ">>  583 >>  Turku \tMaarianhamina\n",
      ">>  760 >>  Pori \tHelsinki\n",
      ">>  775 >>  Singapore \tMalesia\n",
      ">>  978 >>  Amerikka \tHelsinki\n",
      ">>  298 >>  Venezuela \tSuomi\n",
      ">>  404 >>  Seelanti \tAustralia\n",
      "************** 10 ***********\n",
      ">>  620 >>  Espanja \tItalia\n",
      ">>  993 >>  unioni \tSuomi\n",
      ">>  1231 >>  Savo \tSuomi\n",
      ">>  691 >>  Suomi \tOulu\n",
      ">>  73 >>  Iran \tSuomi\n",
      ">>  971 >>  Pakistan \tYhdysvalta\n",
      ">>  511 >>  Kuopio \tMaaninka\n",
      ">>  656 >>  Niinistö \tSuomi\n",
      ">>  636 >>  USA \tVenäjä\n",
      ">>  273 >>  Espoo \tKauniainen\n",
      "************** 11 ***********\n",
      ">>  378 >>  kuola \tSuomi\n",
      ">>  1076 >>  Intia \tJapani\n",
      ">>  353 >>  Skandinavia \tVenäjä\n",
      ">>  984 >>  Britannia \tTanska\n",
      ">>  1242 >>  Suomi \tpohja#lahti\n",
      ">>  1101 >>  Venäjä \tSkandinavia\n",
      ">>  399 >>  Japani \tIntia\n",
      ">>  74 >>  Tanska \tBritannia\n",
      ">>  119 >>  pohja#lahti \tSuomi\n",
      ">>  1129 >>  Suomi \tkuola\n",
      "************** 12 ***********\n",
      ">>  526 >>  Saksa \tBritannia\n",
      ">>  183 >>  Lappi \tEurooppa\n",
      ">>  422 >>  Australia \tIso-Britanniassa\n",
      ">>  340 >>  Britannia \tSaksa\n",
      ">>  809 >>  Anttila \tSuomi\n",
      ">>  771 >>  Eurooppa \tLappi\n",
      ">>  795 >>  Heinola \tHelsinki\n",
      ">>  1157 >>  Iso-Britanniassa \tAustralia\n",
      ">>  319 >>  Helsinki \tHeinola\n",
      ">>  77 >>  Suomi \tAnttila\n",
      "************** 13 ***********\n",
      ">>  913 >>  Belgia \tRanska\n",
      ">>  458 >>  Amerikka \tKiina\n",
      ">>  988 >>  Islanti \tpohjois#maa\n",
      ">>  202 >>  Japani \tRanska\n",
      ">>  445 >>  Luxemburg \tSuomi\n",
      ">>  254 >>  Kiina \tViro\n",
      ">>  1016 >>  Viro \tKiina\n",
      ">>  515 >>  Ranska \tBelgia\n",
      ">>  777 >>  Kiina \tAmerikka\n",
      ">>  798 >>  Ranska \tJapani\n",
      "************** 14 ***********\n",
      ">>  828 >>  Ruotsi \tViro\n",
      ">>  1096 >>  Moskova \tPetroskoi\n",
      ">>  898 >>  Italia \tSaksa\n",
      ">>  1035 >>  Berliini \tPariisi\n",
      ">>  571 >>  Viro \tRuotsi\n",
      ">>  623 >>  Petroskoi \tMoskova\n",
      ">>  781 >>  Ruotsi \tPortugali\n",
      ">>  883 >>  Saksa \tItalia\n",
      ">>  1057 >>  Meksiko \tEspanja\n",
      ">>  165 >>  Pariisi \tBerliini\n",
      "************** 15 ***********\n",
      ">>  1186 >>  Slovakia \tPuola\n",
      ">>  892 >>  Suomi \tMurmansk\n",
      ">>  1161 >>  Puola \tSlovakia\n",
      ">>  128 >>  Aasia \tHelsinki\n",
      ">>  1116 >>  Helsinki \tLontoo\n",
      ">>  482 >>  Murmansk \tSuomi\n",
      ">>  280 >>  Skotlanti \tSaksa\n",
      ">>  754 >>  Eurooppa \tNew York\n",
      ">>  1120 >>  Helsinki \tAasia\n",
      ">>  594 >>  Saksa \tSkotlanti\n",
      "************** 16 ***********\n",
      ">>  106 >>  Kiina \tAfganistan\n",
      ">>  980 >>  Venäjä \tNorja\n",
      ">>  306 >>  Suomi \tIi\n",
      ">>  987 >>  Islanti \tNorja\n",
      ">>  43 >>  Pohjanmaa \tHelsinki\n",
      ">>  44 >>  Helsinki \tKonala\n",
      ">>  437 >>  Jyväskylä \tPori\n",
      ">>  47 >>  Helsinki \tvannas#joki\n",
      ">>  1232 >>  Konala \tHelsinki\n",
      ">>  432 >>  Tansania \tSambia\n",
      "************** 17 ***********\n",
      ">>  260 >>  Latvia \tViro\n",
      ">>  819 >>  Viro \tPuola\n",
      ">>  886 >>  Latvia \tPuola\n",
      ">>  424 >>  Puola \tViro\n",
      ">>  1235 >>  Tanska \tViro\n",
      ">>  683 >>  Ruotsi \tLatvia\n",
      ">>  1069 >>  Viro \tTanska\n",
      ">>  794 >>  Latvia \tTanska\n",
      ">>  295 >>  Puola \tNorja\n",
      ">>  500 >>  Latvia \tNorja\n",
      "************** 18 ***********\n",
      ">>  978 >>  Amerikka \tHelsinki\n",
      ">>  216 >>  Helsinki \tPori\n",
      ">>  365 >>  Australia \tSeelanti\n",
      ">>  775 >>  Singapore \tMalesia\n",
      ">>  498 >>  Maarianhamina \tTurku\n",
      ">>  514 >>  Malesia \tSingapore\n",
      ">>  298 >>  Venezuela \tSuomi\n",
      ">>  404 >>  Seelanti \tAustralia\n",
      ">>  760 >>  Pori \tHelsinki\n",
      ">>  583 >>  Turku \tMaarianhamina\n",
      "************** 19 ***********\n",
      ">>  760 >>  Pori \tHelsinki\n",
      ">>  583 >>  Turku \tMaarianhamina\n",
      ">>  514 >>  Malesia \tSingapore\n",
      ">>  978 >>  Amerikka \tHelsinki\n",
      ">>  498 >>  Maarianhamina \tTurku\n",
      ">>  60 >>  Suomi \tVenezuela\n",
      ">>  216 >>  Helsinki \tPori\n",
      ">>  775 >>  Singapore \tMalesia\n",
      ">>  298 >>  Venezuela \tSuomi\n",
      ">>  404 >>  Seelanti \tAustralia\n"
     ]
    }
   ],
   "source": [
    "distances=c.transform(features)\n",
    "nearest=np.argpartition(distances,10,axis=0)[:10]\n",
    "\n",
    "print nearest.shape\n",
    "\n",
    "for cluster_num,cluster in enumerate(nearest.T):\n",
    "    print \"**************\", cluster_num,\"***********\"\n",
    "    for pair_id in cluster:\n",
    "        print \">> \",pair_id,\">> \", pair_list[pair_id][0], '\\t', pair_list[pair_id][1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How do we make any sense out of these clusters? Lets look at the feature weights of the cluster centers like before."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Important features:\n",
      "************** 0 ***********\n",
      "<nmod olla >nmod\n",
      "<nmod suunnata >nmod\n",
      "<nmod alue >nmod:poss\n",
      "<nmod:poss alue >nmod\n",
      "<nmod sijaita >nmod\n",
      "************** 1 ***********\n",
      "<nmod mukana >nmod\n",
      "<nmod juontaa >nmod\n",
      "<nmod osa >nmod\n",
      "<nsubj miehittää >dobj\n",
      "<appos pää#kaupunki >nmod:poss\n",
      "************** 2 ***********\n",
      "<nmod siirtyä >nmod\n",
      "<nmod sijaita >nmod\n",
      "<nmod:poss raja >nmod\n",
      "<nmod pelata >nmod\n",
      "<appos pää#kaupunki >nmod:poss\n",
      "************** 3 ***********\n",
      "<nmod:poss mestari >nmod:poss\n",
      "<nmod tutkia >nmod\n",
      "<dobj kohdata >nsubj\n",
      "<nmod mennä >nsubj\n",
      "<nmod suuntautua >nmod\n",
      "************** 4 ***********\n",
      "<nsubj tulla >nmod\n",
      "<nmod ilmestyä >nmod\n",
      "<appos maa#kunta >nmod:poss\n",
      ">nsubj:cop kaupunki >nmod:poss\n",
      "<dobj liittää >nmod\n",
      "************** 5 ***********\n",
      "<nmod jatkua >nmod\n",
      "<appos ESB >appos\n",
      "<nmod:poss suur#lähetystö >appos\n",
      "<nmod:poss suur#lähetystö >nmod\n",
      "<nmod:poss suur#lähetystö >nmod:poss\n",
      "************** 6 ***********\n",
      "<name Tanska >name\n",
      "<nmod pitää >dobj\n",
      "<dobj pitää >nmod\n",
      "<nsubj olla >nmod\n",
      "<nsubj tarjota >nmod\n",
      "************** 7 ***********\n",
      "<nsubj olla >nmod\n",
      "<appos maa >nmod:poss\n",
      "<nmod esiintyä >nmod\n",
      "<nmod maa >nmod:poss\n",
      "<nmod pitää >nmod\n",
      "************** 8 ***********\n",
      "<nmod muuttaa >nmod\n",
      "<nmod:poss suur#lähetystö >nmod:poss\n",
      "<nmod tulla >nmod\n",
      "<nmod pitää >nmod\n",
      "<nmod:poss suur#lähettiläs >nmod:poss\n",
      "************** 9 ***********\n",
      "<nmod järjestää >nmod\n",
      "<nmod lähteä >nmod\n",
      "<nmod olla >nsubj\n",
      "<nmod suur#lähetystö >nmod:poss\n",
      "<nmod päästä >nmod\n",
      "************** 10 ***********\n",
      "<nmod toimia >nmod\n",
      "<nmod siirtää >nmod\n",
      "<nmod tuoda >nmod\n",
      "<nmod käydä >nmod\n",
      "<nmod ottaa >nmod\n",
      "************** 11 ***********\n",
      "<nmod prosentti >nmod\n",
      "<nmod voittaa >nmod\n",
      "<nmod kokeilla >nmod\n",
      "<nsubj vaatia >nmod\n",
      "<nmod olla >nmod\n",
      "************** 12 ***********\n",
      "<nmod siirtää >nsubj\n",
      "<nsubj löytyä >nmod\n",
      "<nmod matkata >nmod\n",
      "<dobj laskea >nmod\n",
      "<nmod:poss yli#opisto >nmod\n",
      "************** 13 ***********\n",
      "<nmod ajaa >nmod\n",
      "<nmod:poss maa >appos\n",
      "<nsubj hyökätä >nmod\n",
      "<nmod saapua >nmod\n",
      "<nmod:poss maa >nmod\n",
      "************** 14 ***********\n",
      "<nmod tulla >nmod\n",
      "<nmod lentää >nmod\n",
      "<nmod päästä >nmod\n",
      "<nmod matka >nmod\n",
      "<appos suur#kaupunki >nmod:poss\n",
      "************** 15 ***********\n",
      "<nmod asua >nmod\n",
      "<nmod sijaita >nmod\n",
      "<nmod muuttaa >nmod\n",
      "<nmod:poss pää#konttori <nsubj olla >nmod\n",
      "<nmod:poss kaupunki >appos\n",
      "************** 16 ***********\n",
      "<nmod kulkea >nmod\n",
      "<nmod lähteä >nmod\n",
      "<nmod olla >nmod\n",
      "<nmod laskea >nmod\n",
      "<nmod tulla >nsubj\n",
      "************** 17 ***********\n",
      "<nmod olla >nmod\n",
      "<nmod opiskella >nmod\n",
      "<nmod kokoontua >nmod\n",
      "<nmod työskennellä >nmod\n",
      "<nmod tehdä >nmod\n",
      "************** 18 ***********\n",
      "<nmod alkaa >nmod\n",
      "<nmod:poss taide#museo >nmod\n",
      "<nsubj kehittää >nmod\n",
      ">acl:relcl lähteä >nmod\n",
      "<nmod osa >nsubj:cop\n",
      "************** 19 ***********\n",
      "<nmod tehdä >nmod\n",
      "<nmod ulottua >nmod\n",
      "<nmod saada >nmod\n",
      "<nsubj kilpailla >nmod\n",
      "<nmod tuottaa >nmod\n"
     ]
    }
   ],
   "source": [
    "print \"Important features:\"\n",
    "\n",
    "for i in range(n_clusters):\n",
    "    print \"**************\", i,\"***********\"\n",
    "    for ii in np.argsort(-c.cluster_centers_[i])[:5]:\n",
    "        print vectorizer.get_feature_names()[ii]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These surface patterns should then be used to decide a relation type for each cluster\n",
    "\n",
    "Issues:\n",
    "* Like always, we don't really know the optimal number of clusters\n",
    "* Clusters are mutually exclusive, i.e. an entity pair can have only one relation between them"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A step further: distant supervision\n",
    "* In many cases we have an existing knowledge base of relations:\n",
    "    * Wikipedia/wikidata: https://www.wikidata.org/wiki/Wikidata:Main_Page\n",
    "    * Freebase: https://www.freebase.com/\n",
    "* However, we have no connection between these known relations and their textual mentions\n",
    "* Distant supervision: any attempt of aligning these two sources of information"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Latent feature model\n",
    "* Lets consider similar matrix as in the relational cluster\n",
    "* Adding relation data from existing knowledge bases is trivial: we create a new column for each known relation (in addition to the surface pattern columns)\n",
    "* Naturally these knowledge bases are not exhaustive, otherwise there would be no point in trying to find related entity pairs\n",
    "* Thus the goal is to create a model to fill in the blanks in our matrix\n",
    "* One way to achieve this is with a latent feature model where we learn a feature vector for each entity tuple and for each relation. We can then use these feature vectors to model the probability of a single cell in the matrix being equal to 1, i.e. a relation existing for a given entity pair, by taking dot product of these latent feature vectors and using the result as an input for a logistic function.\n",
    "* Side note: the logistic function aside this is actually a matrix factorization M = AV, where M is our original matrix, A is the latent feature matrix for relations and V for entity pairs.\n",
    "* Since the model is forced to use the dot product, a pair having relations X and Y will force these relations to have similar feature vectors and vice versa.\n",
    "* How do we train a model like this then?\n",
    "    * Naive approach is to use the known relations as positives and unknown as negatives\n",
    "        * This is obviously unrealistic as a missing relation doesn't mean it doesn't exist\n",
    "        * Gives us still a working model, but training may be sensitive to the proportion of sampled negatives etc.\n",
    "    * State-of-the-art systems use ranking objectives instead, i.e. a known relation should have a higher predicted probability than an unknown one."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Enough theory, this is how it is done in practice\n",
    "* We have again similar data matrix as before, with text corpora focusing on Hitler\n",
    "* This time we add a new column *friends_with* and initialize it with a subset of Hitler's inner circle\n",
    "    * These known pairs will have the value for this relation set to 1, others 0 like before\n",
    "* Lets build the model in Keras"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lets import all we need + something we don't"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "import codecs\n",
    "import os\n",
    "import sys\n",
    "import cPickle as pickle\n",
    "import random\n",
    "\n",
    "import numpy as np\n",
    "np.random.seed(1337)  # for reproducibility\n",
    "\n",
    "from keras.preprocessing import sequence\n",
    "from keras.utils import np_utils\n",
    "from keras.models import Sequential, Graph\n",
    "from keras.layers.core import Dense, Dropout, Activation, TimeDistributedDense\n",
    "from keras.layers.embeddings import Embedding\n",
    "from keras.layers.recurrent import LSTM\n",
    "from keras.models import model_from_json\n",
    "\n",
    "from collections import defaultdict, Counter\n",
    "\n",
    "from sklearn.metrics.pairwise import cosine_similarity\n",
    "from sklearn.feature_extraction import DictVectorizer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Loading data\n",
      "\n",
      "Unique pairs: 1472, unique relations: 255\n"
     ]
    }
   ],
   "source": [
    "print \"Loading data\"\n",
    "train_data = pickle.load(open('./hitler_distant_train_data.pkl', 'rb'))\n",
    "pair_count, rel_count, pair_ids, rel_ids, distant_pairs, train_data = train_data\n",
    "reverse_pair_ids = {i: p for p, i in pair_ids.items()}\n",
    "\n",
    "print ''\n",
    "print \"Unique pairs: %s, unique relations: %s\" % (len(pair_ids), len(rel_ids))\n",
    "#print \"Distant pairs in final set: %s\"  % len(set(pair_ids.keys()).intersection(set([(p[0][3], p[1][3] ) for p in distant_pairs])))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Down below is our model implemented in Keras."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Building model\n",
      "Done!\n"
     ]
    }
   ],
   "source": [
    "model = Graph()\n",
    "        \n",
    "model.add_input(name='e1', input_shape=(1, ), dtype='int')\n",
    "model.add_input(name='e2', input_shape=(1, ), dtype='int')\n",
    "\n",
    "model.add_node(Embedding(pair_count, 50, input_length=1, trainable=True), input='e1', name='e1e')\n",
    "model.add_node(Embedding(rel_count, 50, input_length=1, trainable=True), input='e2', name='e2e')\n",
    "\n",
    "model.add_node(TimeDistributedDense(1, activation='sigmoid'), name='outd', inputs=['e1e', 'e2e'], merge_mode='dot', concat_axis=-1)\n",
    "\n",
    "model.add_output(name='out', input='outd')\n",
    "\n",
    "print \"Building model\"\n",
    "model.compile(loss={'out':'binary_crossentropy',},\n",
    "              optimizer='adam')\n",
    "print \"Done!\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Time to train it!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Training\n",
      "Train on 800160 samples, validate on 200040 samples\n",
      "Epoch 1/6\n",
      "800160/800160 [==============================] - 4s - loss: 0.2484 - val_loss: 0.0906\n",
      "Epoch 2/6\n",
      "800160/800160 [==============================] - 4s - loss: 0.0241 - val_loss: 0.0289\n",
      "Epoch 3/6\n",
      "800160/800160 [==============================] - 4s - loss: 0.0084 - val_loss: 0.0158\n",
      "Epoch 4/6\n",
      "800160/800160 [==============================] - 4s - loss: 0.0039 - val_loss: 0.0101\n",
      "Epoch 5/6\n",
      "800160/800160 [==============================] - 4s - loss: 0.0019 - val_loss: 0.0071\n",
      "Epoch 6/6\n",
      "800160/800160 [==============================] - 4s - loss: 9.0935e-04 - val_loss: 0.0056\n",
      "Done!\n"
     ]
    }
   ],
   "source": [
    "print \"Training\"\n",
    "model.fit(train_data, verbose=1, nb_epoch=6, batch_size=1024, validation_split=0.2)\n",
    "print \"Done!\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Did we actually learn something? Lets get some predictions!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Predicting\n",
      "Done!\n",
      "Top hits with training pairs included (***):\n",
      "Hitler Hewel ***\n",
      "Hitler Schröder ***\n",
      "Hitler Jodl ***\n",
      "Hitler Speer ***\n",
      "Hitler Göring ***\n",
      "Hitler Junge ***\n",
      "Hitler Braun ***\n",
      "Hitler Wagner ***\n",
      "Hitler Goebbels ***\n",
      "Hitler Britannia \n",
      "Hitler minä Fuhrer \n",
      "Hitler From Darwin \n",
      "Hitler Leyn \n",
      "Hitler Neville Chamberlain \n",
      "Hitler Mussolini \n",
      "Hitler Prescott Bush \n",
      "Hitler Ranska \n",
      "Hitler '“From Darwin \n",
      "Hitler kevät \n",
      "Hitler Mao Zedong \n",
      "Hitler Tarja Halonen \n",
      "Hitler minä Kampfissa \n",
      "Hitler Franco \n",
      "Hitler :Kun \n",
      "Hitler The Producers \n",
      "Hitler Mel Brooks \n",
      "Hitler '4: Hitler \n",
      "Hitler veitikka \n",
      "Hitler Muammar Gaddafi \n",
      "Hitler euroopassa \n",
      "Hitler Stalin \n",
      "Hitler Winston Churchill \n",
      "Hitler Paavali \n",
      "Hitler Neuvostoliitto \n",
      "Hitler Tšekkoslovakia \n",
      "Hitler Osama bin Laden \n",
      "Hitler Erkki tuomi#oja \n",
      "Hitler Robert Carlyle \n",
      "Hitler Ed Wood \n",
      "Hitler Risto Ryti \n"
     ]
    }
   ],
   "source": [
    "print \"Predicting\"\n",
    "test_pairs = np.asarray([[i] for p, i in pair_ids.items() if p[0] == 'Hitler' ])\n",
    "test_rels = np.asarray([[rel_ids['FRIENDS_WITH']]*test_pairs.shape[0]]).T\n",
    "\n",
    "pred = model.predict({'e1': test_pairs, 'e2':test_rels})\n",
    "pred_list = pred['out'][:,0,0]\n",
    "\n",
    "dis_pairs = set([(d[0][3], d[1][3]) for d in distant_pairs])\n",
    "res = [reverse_pair_ids[test_pairs[i][0]] for i in np.argsort(-pred_list)]\n",
    "print \"Done!\"\n",
    "\n",
    "print \"Top hits with training pairs included (***):\"\n",
    "\n",
    "for r in res[:40]:\n",
    "    if r in dis_pairs:\n",
    "        in_train = '***'\n",
    "    else:\n",
    "        in_train = ''\n",
    "    print r[0], r[1].decode('utf-8'), in_train"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Aaaaand we are done!**"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}