word_sense_disambiguation_pt2.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import nltk\n",
    "from nltk.corpus import wordnet as wn\n",
    "from nltk.corpus import stopwords\n",
    "from nltk.tokenize import RegexpTokenizer\n",
    "from nltk.util import ngrams\n",
    "import itertools\n",
    "from collections import Counter\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.metrics import accuracy_score\n",
    "import networkx as nx\n",
    "\n",
    "nltk.download('brown')\n",
    "nltk.download('punkt')\n",
    "nltk.download('stopwords')\n",
    "stopwords = stopwords.words('english')\n",
    "\n",
    "np.set_printoptions(suppress=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Word Sense Disambiguation - ML approaches\n",
    "\n",
    "In this notebook, we will look into following approaches for WSD: \n",
    "1. **Supervised:** Decision List algorithm\n",
    "2. **Semi-Supervised:** Yarowsky's Method\n",
    "3. **Unsupervised:** HyperLex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Supervised approach - Decision List Classifier\n",
    "\n",
    "We are interested in finding appropriate sense given a sentence. In this approach, we are given with labelled dataset with (sentence, sense) pairs. \n",
    "\n",
    "The steps for Decision List Classifier are as follows:\n",
    "1. We split the data into train and validation sets. \n",
    "2. Learn the Decision List on training set. We do this by computing log-likelihood ratio between two senses of ambiguous word given a collocation.\n",
    "3. Evaluate it on validation set.\n",
    "\n",
    "Here as an example, we are considering adjacent words (bigrams) as collocations. Data can be downloaded from the below link."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# !rm -rf public\n",
    "# !git clone https://github.com/myTomorrows-research/public.git"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_data(path):\n",
    "    df = pd.read_csv(path, sep='\\t')\n",
    "    df['Term'].replace({'Albumin':'Albumine', 'BBC':'BCC'}, inplace=True)\n",
    "    idx_map = {'ACS':1, 'Albumine':2, 'BCC':0}\n",
    "\n",
    "    for i in range(len(df)):\n",
    "        study = df.loc[i, 'ID_study']\n",
    "        term = df.loc[i, 'Term']\n",
    "        idx = idx_map[term]\n",
    "        study_path = f'public/HealthInf2021/{term}/{idx}_{study}.txt'\n",
    "        with open(study_path) as f:\n",
    "            data = f.read().splitlines()\n",
    "        try:\n",
    "            summary = data[data.index('brief_summary:') + 1].strip()\n",
    "            df.loc[i, 'summary'] = summary\n",
    "        except:\n",
    "            pass\n",
    "\n",
    "    # preprocessing\n",
    "    df.dropna(inplace=True)\n",
    "    df.drop(columns='ID_study', inplace=True)\n",
    "    df.rename(columns={'Final sense':'sense'}, inplace=True)\n",
    "    df.reset_index(drop=True, inplace=True)\n",
    "    df['Term'] = list(map(lambda x: x.strip(), df['Term']))\n",
    "    df['sense'] = list(map(lambda x: x.strip(), df['sense']))\n",
    "    return df\n",
    "\n",
    "def get_collocations(sentence, tokenizer, n_gram):\n",
    "    words = tokenizer.tokenize(sentence)\n",
    "    words = [word.lower() for word in words if word.isalnum() and word not in stopwords]\n",
    "    collocations = list(ngrams(words, n_gram))\n",
    "    return collocations    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(100, 25)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n_gram = 2\n",
    "path = 'public/HealthInf2021/benchmark_myT_WSD.txt'\n",
    "tokenizer = RegexpTokenizer(r'\\w+')\n",
    "\n",
    "# making data\n",
    "df = make_data(path)\n",
    "\n",
    "# splitting into train and validation sets\n",
    "train_df, val_df = train_test_split(df, test_size=0.2, random_state=0)\n",
    "train_df.reset_index(drop=True, inplace=True)\n",
    "val_df.reset_index(drop=True, inplace=True)\n",
    "len(train_df), len(val_df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_all_collocations(df):\n",
    "    corpus = df['summary'].values.tolist()\n",
    "    all_collocations = list(map(lambda sent: get_collocations(sent, tokenizer, n_gram), corpus))\n",
    "    flattened_all_collocations = list(itertools.chain(*all_collocations))\n",
    "    unique_collocations = list(set(flattened_all_collocations))\n",
    "    return unique_collocations, all_collocations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get collocation_sense_mapping\n",
    "def get_collocation_sense_map(df, unique_collocations, all_collocations):\n",
    "    collocation_sense_map = {}\n",
    "    for c in unique_collocations:\n",
    "        collocation_sense_map[c] = []\n",
    "        for idx in range(len(df)):\n",
    "            if c in all_collocations[idx]:\n",
    "                term = df.loc[idx,'Term']\n",
    "                sense = df.loc[idx,'sense']\n",
    "                collocation_sense_map[c].append(term + '-' + sense)\n",
    "    return collocation_sense_map\n",
    "\n",
    "# compute log-likelihood ratio and find sense for given collocation\n",
    "def get_sense_given_collocation(test_collocation, collocation_sense_map):\n",
    "    senses = collocation_sense_map[test_collocation]\n",
    "    senses = dict(Counter(senses))\n",
    "    cond_probs = {k:v/sum(senses.values()) for k,v in senses.items()}\n",
    "\n",
    "    max_llr = -float('inf')\n",
    "    sense = None\n",
    "    for iter_senseA, probA in cond_probs.items():\n",
    "        for iter_senseB, probB in cond_probs.items():\n",
    "            # log-likelihood ratio\n",
    "            llr = np.log(probA / probB)\n",
    "            if llr > max_llr:\n",
    "                max_llr = llr\n",
    "                sense = iter_senseA\n",
    "    return sense, max_llr\n",
    "\n",
    "# get final decision list\n",
    "def get_decision_list(collocation_sense_map):\n",
    "    decision_list = []\n",
    "    for test_collocation in collocation_sense_map.keys():\n",
    "        sense, max_llr = get_sense_given_collocation(test_collocation, collocation_sense_map)\n",
    "        decision_list.append([test_collocation, sense, max_llr])\n",
    "\n",
    "    decision_list = sorted(decision_list, key=lambda x: x[2], reverse=True)    \n",
    "    decision_list = pd.DataFrame(decision_list, columns=['collocations','sense','LLR'])\n",
    "    return decision_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of unique collocations: 3501\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>collocations</th>\n",
       "      <th>sense</th>\n",
       "      <th>LLR</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>(syndrome, acs)</td>\n",
       "      <td>ACS-Sense6</td>\n",
       "      <td>2.197225</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>(study, evaluate)</td>\n",
       "      <td>BCC-Sense3</td>\n",
       "      <td>1.609438</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>(the, aim)</td>\n",
       "      <td>Albumine-Sense2</td>\n",
       "      <td>1.609438</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>(the, purpose)</td>\n",
       "      <td>BCC-Sense3</td>\n",
       "      <td>1.203973</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>(purpose, study)</td>\n",
       "      <td>BCC-Sense3</td>\n",
       "      <td>1.203973</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>(septic, shock)</td>\n",
       "      <td>Albumine-Sense2</td>\n",
       "      <td>1.098612</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>(the, study)</td>\n",
       "      <td>ACS-Sense6</td>\n",
       "      <td>1.098612</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>(this, study)</td>\n",
       "      <td>Albumine-Sense2</td>\n",
       "      <td>1.098612</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>(standard, care)</td>\n",
       "      <td>Albumine-Sense2</td>\n",
       "      <td>1.098612</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>(coronary, artery)</td>\n",
       "      <td>ACS-Sense6</td>\n",
       "      <td>1.098612</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "         collocations            sense       LLR\n",
       "0     (syndrome, acs)       ACS-Sense6  2.197225\n",
       "1   (study, evaluate)       BCC-Sense3  1.609438\n",
       "2          (the, aim)  Albumine-Sense2  1.609438\n",
       "3      (the, purpose)       BCC-Sense3  1.203973\n",
       "4    (purpose, study)       BCC-Sense3  1.203973\n",
       "5     (septic, shock)  Albumine-Sense2  1.098612\n",
       "6        (the, study)       ACS-Sense6  1.098612\n",
       "7       (this, study)  Albumine-Sense2  1.098612\n",
       "8    (standard, care)  Albumine-Sense2  1.098612\n",
       "9  (coronary, artery)       ACS-Sense6  1.098612"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "unique_collocations, all_collocations = get_all_collocations(train_df)\n",
    "print('Number of unique collocations:', len(unique_collocations))\n",
    "\n",
    "collocation_sense_map = get_collocation_sense_map(train_df, unique_collocations, all_collocations)\n",
    "decision_list = get_decision_list(collocation_sense_map)\n",
    "decision_list.head(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_true_labels(val_df):\n",
    "    y_true = (val_df['Term'] + '-' + val_df['sense']).values\n",
    "    return np.array(y_true)\n",
    "\n",
    "def get_predictions(val_df, decision_list):\n",
    "    y_pred = []\n",
    "    val_corpus = val_df['summary'].values.tolist()\n",
    "    val_all_collocations = list(map(lambda sent: get_collocations(sent, tokenizer, n_gram), val_corpus))    \n",
    "    for val_collocations in val_all_collocations:\n",
    "        bool_found = 0\n",
    "        for idx in range(len(decision_list)):\n",
    "            colloc = decision_list.loc[idx,'collocations']\n",
    "            sense = decision_list.loc[idx,'sense']\n",
    "            if colloc in val_collocations:\n",
    "                bool_found = 1\n",
    "                break\n",
    "        if not bool_found:\n",
    "            sense = ''\n",
    "        y_pred.append(sense)\n",
    "    return np.array(y_pred)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.64"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# true labels\n",
    "y_val = get_true_labels(val_df)\n",
    "\n",
    "# prediction labels\n",
    "y_pred = get_predictions(val_df, decision_list)\n",
    "\n",
    "assert len(y_val) == len(y_pred)\n",
    "accuracy_score(y_val, y_pred)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Semi-Supervised approaches\n",
    "\n",
    "The problem with Supervised approaches is that you need labelled data. However, you may not have it all the time or you have only a small sample of it. Now, we will look into **Yarowsky's method** which is semi-supervised. \n",
    "\n",
    "It's based on the idea of bootstrapping. You start with some small sample of data with labels and progressively label remaining examples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def single_pass(bootstrap_df, oob_df):\n",
    "    unique_collocations, all_collocations = get_all_collocations(bootstrap_df)\n",
    "    collocation_sense_map = get_collocation_sense_map(bootstrap_df, unique_collocations, all_collocations)\n",
    "    decision_list = get_decision_list(collocation_sense_map)\n",
    "    decision_list = decision_list[decision_list['LLR']>0].reset_index(drop=True)    \n",
    "\n",
    "    y_val = get_true_labels(oob_df)\n",
    "    y_pred = get_predictions(oob_df, decision_list)\n",
    "    assert len(y_val) == len(y_pred)\n",
    "    acc_score = accuracy_score(y_val, y_pred)      \n",
    "\n",
    "    bootstrap_idx = np.where(y_pred!='')[0]\n",
    "    oob_idx = np.where(y_pred=='')[0]\n",
    "    bootstrap_df = pd.concat([bootstrap_df, oob_df.loc[bootstrap_idx]]).reset_index(drop=True)  \n",
    "    oob_df = oob_df.loc[oob_idx].reset_index(drop=True)\n",
    "    return bootstrap_df, oob_df, decision_list, acc_score\n",
    "\n",
    "def run_Yarowsky_algorithm(df, bootstrap_size, random_state, n_iters):\n",
    "    # splitting into two sets\n",
    "    oob_df, bootstrap_df = train_test_split(df, test_size=bootstrap_size, random_state = random_state)\n",
    "    oob_df.reset_index(drop=True, inplace=True)\n",
    "    bootstrap_df.reset_index(drop=True, inplace=True)\n",
    "\n",
    "    for iter in range(n_iters):\n",
    "        bootstrap_df, oob_df, decision_list, acc_score = single_pass(bootstrap_df, oob_df)\n",
    "        if acc_score==0:\n",
    "            print('\\nNo collocations matched between decision list and OOB sample..')\n",
    "            print('Terminating..')\n",
    "            break\n",
    "        else:\n",
    "            print(f'Iteration:{iter+1} | Decision List Length: {len(decision_list)} | Accuracy Score: {acc_score.round(3)}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration:1 | Decision List Length: 1 | Accuracy Score: 0.045\n",
      "Iteration:2 | Decision List Length: 10 | Accuracy Score: 0.202\n",
      "Iteration:3 | Decision List Length: 23 | Accuracy Score: 0.158\n",
      "Iteration:4 | Decision List Length: 34 | Accuracy Score: 0.103\n",
      "\n",
      "No collocations matched between decision list and OOB sample..\n",
      "Terminating..\n"
     ]
    }
   ],
   "source": [
    "n_gram = 2\n",
    "path = 'public/HealthInf2021/benchmark_myT_WSD.txt'\n",
    "tokenizer = RegexpTokenizer(r'\\w+')\n",
    "bootstrap_size = 0.1\n",
    "random_state = 0\n",
    "n_iters = 10\n",
    "\n",
    "# making data\n",
    "df = make_data(path)\n",
    "\n",
    "# running algorithm\n",
    "run_Yarowsky_algorithm(df, bootstrap_size, random_state, n_iters)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Unsupervised approach\n",
    "\n",
    "The limitation of the above semi-supervised approach is that the accuracy depends on how good your initial seed set is. \n",
    "\n",
    "#### Hyperlex\n",
    "Now, we will look into an approach which requires no labels at all. The idea is that for an ambiguous word, there will be many connections among context words within different senses but not many among context words between different senses. \n",
    "\n",
    "For example - context words for word run can be (government, politics, authority) and (walk, fast, speed). So, there will be connections among (government, politics, authority) and among (walk, fast, speed) but not between say government and fast.\n",
    "\n",
    "The steps are as follows:\n",
    "\n",
    "**Training:**\n",
    "\n",
    "1. Build the co-occurence graph $G$ based on statistics on your data \n",
    "2. Given a target ambiguous word and context, we build a spanning tree with:\n",
    "    1. Target word as the root node \n",
    "    2. Hubs as neighbours to target word in $G$\n",
    "\n",
    "**Run-time:**\n",
    "\n",
    "1. Now, we compute score vector of length k (one for each hub) for all context words\n",
    "2. Sum hub scores for all context words \n",
    "3. The hub with maximum score is the sense of ambiguous word being used in given context"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Processing sentences..\n",
      "\n",
      "Number of Sentences: 500\n",
      "Number of Tokens: 2493\n"
     ]
    }
   ],
   "source": [
    "n_sents = 500\n",
    "window_size = 5\n",
    "brown = nltk.corpus.brown\n",
    "sents = brown.sents()[:n_sents]\n",
    "\n",
    "print('Processing sentences..\\n')\n",
    "processed_sents = []\n",
    "for sent in sents:\n",
    "    processed_sents.append([word.lower() for word in sent if word.isalnum() and word not in stopwords])\n",
    "\n",
    "tokens = list(set(list(itertools.chain(*processed_sents))))   \n",
    "n_tokens = len(tokens)\n",
    "print('Number of Sentences:', len(sents)) \n",
    "print('Number of Tokens:', n_tokens)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_co_occurences(token, processed_sents, window_size):\n",
    "    co_occurences = []\n",
    "    for sent in processed_sents:\n",
    "        if len(sent):\n",
    "            for idx in (np.array(sent)==token).nonzero()[0]:\n",
    "                co_occurences.append(sent[max(0, idx-window_size):min(idx+window_size+1, len(sent))])\n",
    "\n",
    "    co_occurences = list(itertools.chain(*co_occurences))\n",
    "    co_occurence_idxs = list(map(lambda x: token2int[x], co_occurences))\n",
    "    co_occurence_dict = Counter(co_occurence_idxs)\n",
    "    co_occurence_dict = dict(sorted(co_occurence_dict.items()))\n",
    "    return co_occurence_dict\n",
    "\n",
    "def get_co_occurence_matrix(tokens, processed_sents, window_size):\n",
    "    for token in tokens:\n",
    "        token_idx = token2int[token]\n",
    "        co_occurence_dict = get_co_occurences(token, processed_sents, window_size)\n",
    "        co_occurence_matrix[token_idx, list(co_occurence_dict.keys())] = list(co_occurence_dict.values())\n",
    "        \n",
    "    np.fill_diagonal(co_occurence_matrix, 0)    \n",
    "    return co_occurence_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Building co-occurence matrix..\n",
      "Co-occurence matrix shape: (2493, 2493)\n"
     ]
    }
   ],
   "source": [
    "token2int = dict(zip(tokens, range(len(tokens))))\n",
    "int2token = {v:k for k,v in token2int.items()} \n",
    "\n",
    "print('Building co-occurence matrix..')\n",
    "co_occurence_matrix = np.zeros(shape=(len(tokens), len(tokens)), dtype='int')\n",
    "co_occurence_matrix = get_co_occurence_matrix(tokens, processed_sents, window_size)\n",
    "print('Co-occurence matrix shape:', co_occurence_matrix.shape)\n",
    "assert co_occurence_matrix.shape == (n_tokens, n_tokens)\n",
    "\n",
    "# co-occurence matrix is similar\n",
    "assert np.all(co_occurence_matrix.T == co_occurence_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# adding nodes\n",
    "def add_nodes(G, n_tokens):\n",
    "    nodes = range(n_tokens)\n",
    "    G.add_nodes_from(nodes)\n",
    "    return G\n",
    "\n",
    "def make_edges(co_occurence_matrix, row_idx):\n",
    "    row = co_occurence_matrix[row_idx]\n",
    "    idxs = np.where(row!=0)[0]\n",
    "\n",
    "    # weights as distance\n",
    "    weights = 1 - row[idxs]\n",
    "    edge_weights = list(zip(['weight'] * len(idxs), weights))\n",
    "    edge_weights = list(map(lambda x: {x[0]:x[1]}, edge_weights))\n",
    "    edges = list(tuple(zip([row_idx] * len(idxs), idxs, edge_weights)))\n",
    "    return edges\n",
    "\n",
    "def add_edges(co_occurence_matrix, n_tokens):\n",
    "    all_edges = list(map(lambda row_idx: make_edges(co_occurence_matrix, row_idx), range(n_tokens)))\n",
    "    all_edges = list(itertools.chain(*all_edges))\n",
    "    G.add_edges_from(all_edges)\n",
    "    return G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# removing isolated nodes\n",
    "# edges to/from removed nodes are removed as well\n",
    "def remove_isolated_nodes(G):\n",
    "    nodes = G.nodes()\n",
    "    for node in nodes:\n",
    "        if len(G.successors(node))==0 and len(G.predecessors(node))==0:\n",
    "            G.remove_node(node)   \n",
    "    return G \n",
    "\n",
    "# normalzing edge weights\n",
    "def normalize_edge_weights(G):\n",
    "    for node in G.nodes():\n",
    "        if len(G.successors(node)) > 0:\n",
    "            total_weight = 0\n",
    "            for neighbor in G.successors(node):\n",
    "                total_weight += G[node][neighbor]['weight']\n",
    "            if total_weight:\n",
    "                for neighbor in G.successors(node):\n",
    "                    G[node][neighbor]['weight']/= total_weight  \n",
    "    return G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Final number of nodes:  2492\n",
      "Final number of edges:  42648\n"
     ]
    }
   ],
   "source": [
    "G = nx.DiGraph()\n",
    "G = add_nodes(G, n_tokens)\n",
    "G = add_edges(co_occurence_matrix, n_tokens)\n",
    "G = remove_isolated_nodes(G)\n",
    "G = normalize_edge_weights(G)\n",
    "G_orig = G.copy()\n",
    "\n",
    "print('Final number of nodes: ', len(G.nodes()))\n",
    "print('Final number of edges: ', len(G.edges()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def step(node, G, G_new, dist_threshold, start_flag):\n",
    "    # filter edges based on threshold \n",
    "    edges = np.array(G.edges(node))\n",
    "    edge_weights_dict = np.array(list(G[node].values()))\n",
    "    if start_flag:\n",
    "        edge_weights = np.array([0] * len(edge_weights_dict))\n",
    "    else:\n",
    "        edge_weights = np.array(list(map(lambda x: list(x.values())[0], edge_weights_dict)))\n",
    "    chosen_idxs = np.where(edge_weights <= dist_threshold)[0]\n",
    "\n",
    "    if len(chosen_idxs):\n",
    "        # add edges in new graph\n",
    "        # nodes are automatically added \n",
    "        edges = edges[chosen_idxs]\n",
    "        edge_weights_dict = edge_weights_dict[chosen_idxs]\n",
    "        assert len(edges) == len(edge_weights_dict)\n",
    "        \n",
    "        from_nodes = np.array(edges)[:,0]\n",
    "        to_nodes = np.array(edges)[:,1]\n",
    "        new_edges = list(zip(from_nodes, to_nodes, edge_weights_dict))\n",
    "        G_new.add_edges_from(new_edges)\n",
    "\n",
    "        # remove edges from original graph\n",
    "        G.remove_edges_from(new_edges)\n",
    "    return G, G_new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tokens with most number of senses:\n",
      "[['cut' '70']\n",
      " ['run' '57']\n",
      " ['making' '52']\n",
      " ['running' '52']\n",
      " ['made' '52']]\n"
     ]
    }
   ],
   "source": [
    "num_senses = list(map(lambda x: len(wn.synsets(x)), tokens))\n",
    "token_senses = list(zip(tokens, num_senses))\n",
    "token_senses = list(map(lambda x: list(x), token_senses))\n",
    "token_senses = sorted(token_senses, key= lambda x: x[1], reverse=True)\n",
    "print('Tokens with most number of senses:')\n",
    "print(np.array(token_senses[:5]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def training(target_node, G, dist_threshold):\n",
    "    G_new = nx.DiGraph()\n",
    "    n_iter = 0\n",
    "\n",
    "    hubs = np.array(G.successors(target_node))\n",
    "    degrees = np.array(list(map(lambda x: G.degree(x), hubs)))\n",
    "    hubs = hubs[degrees.argsort()[::-1]].tolist()\n",
    "    nodes = [target_node] + hubs\n",
    "    \n",
    "    for node in nodes:\n",
    "        if node==target_node:\n",
    "            start_flag = 1\n",
    "        else:\n",
    "            start_flag = 0\n",
    "        G, G_new = step(node, G, G_new, dist_threshold, start_flag)  \n",
    "        n_iter += 1\n",
    "\n",
    "        if n_iter%5==0:\n",
    "            print(f'Iteration: {n_iter}')\n",
    "            print(f'Nodes in Original Tree: {len(G.nodes())} | Edges in Original Tree: {len(G.edges())}')\n",
    "            print(f'Nodes in Spanning Tree: {len(G_new.nodes())} | Edges in Spanning Tree: {len(G_new.edges())}')\n",
    "            print()\n",
    "    return G_new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of senses: 57 \n",
      "\n",
      "Iteration: 5\n",
      "Nodes in Original Tree: 2492 | Edges in Original Tree: 42010\n",
      "Nodes in Spanning Tree: 544 | Edges in Spanning Tree: 638\n",
      "\n",
      "Iteration: 10\n",
      "Nodes in Original Tree: 2492 | Edges in Original Tree: 41814\n",
      "Nodes in Spanning Tree: 634 | Edges in Spanning Tree: 834\n",
      "\n",
      "Iteration: 15\n",
      "Nodes in Original Tree: 2492 | Edges in Original Tree: 41725\n",
      "Nodes in Spanning Tree: 655 | Edges in Spanning Tree: 923\n",
      "\n"
     ]
    }
   ],
   "source": [
    "target_word = 'run'\n",
    "dist_threshold = 0\n",
    "\n",
    "target_node = token2int[target_word]\n",
    "senses = wn.synsets(target_word)\n",
    "print('Number of senses:',len(senses),'\\n')\n",
    "G_new = training(target_node, G, dist_threshold)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_path_length(G, path):\n",
    "    path_length = 0\n",
    "    for path_idx in range(len(path)-1):\n",
    "        start = path[path_idx]\n",
    "        end = path[path_idx+1]\n",
    "        path_length += list(G[start][end].values())[0]\n",
    "    return path_length\n",
    "\n",
    "def evaluation(G, hubs, present_context_nodes):\n",
    "    context_scores = []\n",
    "    for context_node in present_context_nodes:\n",
    "        scores = []\n",
    "        if context_node in G.nodes():\n",
    "            for hub in hubs:\n",
    "                if nx.has_path(G, hub, context_node):\n",
    "                    if hub==context_node:\n",
    "                        score = 1\n",
    "                    else:\n",
    "                        path = nx.shortest_path(G, hub, context_node)\n",
    "                        path_length = get_path_length(G, path)\n",
    "                        score = 1 / (1 + path_length)\n",
    "                else:\n",
    "                    score = 0\n",
    "                scores.append(score)        \n",
    "        else:\n",
    "            scores = [0] * len(hubs)\n",
    "        context_scores.append(scores)\n",
    "\n",
    "    context_scores = np.array(context_scores)\n",
    "    context_scores = np.sum(context_scores, axis=0)\n",
    "    return context_scores"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Context words: ['authorities', 'political', 'decisions', 'government', 'mayor', 'votes', 'gas', 'firms', 'federal']\n",
      "Number of hubs: 15\n",
      "Plausible senses: ['primary', 'announced', '1', 'hartsfield', 'mayor', 'reelection', 'would']\n"
     ]
    }
   ],
   "source": [
    "context = 'authorities political decisions government mayor votes gas firms federal'\n",
    "context_words = context.split(' ')\n",
    "\n",
    "present_context_words = []\n",
    "present_context_nodes = []\n",
    "for word in context_words:\n",
    "    if word in tokens:\n",
    "        node = token2int[word]\n",
    "        present_context_words.append(word)\n",
    "        present_context_nodes.append(node)\n",
    "hubs = G_new.successors(target_node)\n",
    "\n",
    "print('Context words:', present_context_words)\n",
    "print('Number of hubs:', len(hubs))\n",
    "\n",
    "context_scores = evaluation(G_new, hubs, present_context_nodes)\n",
    "sense_idxs = np.where(context_scores == max(context_scores))[0]\n",
    "senses = list(map(lambda x: int2token[hubs[x]], sense_idxs))\n",
    "print('Plausible senses:', senses)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "951daa5e1959839fcb325fff331f52e72634f7a1be998f6081ed7f433b63f1b3"
  },
  "kernelspec": {
   "display_name": "Python 3.8.11 64-bit ('base': conda)",
   "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.8.11"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}