word_sense_disambiguation_pt1.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import nltk\n",
    "from nltk.corpus import wordnet as wn\n",
    "from nltk.corpus import brown, stopwords\n",
    "from nltk.tokenize import RegexpTokenizer\n",
    "from nltk.util import ngrams\n",
    "import itertools\n",
    "import networkx as nx\n",
    "from collections import Counter\n",
    "import json\n",
    "\n",
    "nltk.download('punkt')\n",
    "nltk.download('brown')\n",
    "nltk.download('wordnet')\n",
    "nltk.download('stopwords')\n",
    "stopwords = stopwords.words('english')\n",
    "\n",
    "np.set_printoptions(suppress=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Word Sense Disambiguation\n",
    "\n",
    "The problem of Word Sense Disambiguation (WSD) is identifying the correct sense of word being used in a sentence. In English Language, there can be multiple senses of the same word. \n",
    "\n",
    "For example - Apple in a sentence can be used as a fruit or as the name of company."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Word: ash\n",
      "Number of senses: 4\n",
      "\n",
      "Sense 1: the residue that remains when something is burned\n",
      "Sense 2: any of various deciduous pinnate-leaved ornamental or timber trees of the genus Fraxinus\n",
      "Sense 3: strong elastic wood of any of various ash trees; used for furniture and tool handles and sporting goods such as baseball bats\n",
      "Sense 4: convert into ashes\n"
     ]
    }
   ],
   "source": [
    "ambiguous_word = 'ash'\n",
    "word_senses = wn.synsets(ambiguous_word)\n",
    "print('Word:', ambiguous_word)\n",
    "print('Number of senses:', len(word_senses))\n",
    "print()\n",
    "for i, word_sense in enumerate(word_senses):\n",
    "    print(f'Sense {i+1}:', word_sense.definition())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Basic Algorithm\n",
    "\n",
    "Given a sentence and an ambiguous word in it, we are interested in finding the sense of that word. So, we create **sense bags** which is collection of features (hyponyms/hypernyms/definitions or others) for each sense of ambiguous word and a **context bag** which is collection of features for all the words in sentence excluding ambiguous word.\n",
    "\n",
    "We calculate overlap between context bag and various sense bags (one for each sense). We consider that sense which has maximum overlap.\n",
    "\n",
    "1. Hyponyms are words of more specific meaning than given word. Example - Apple is hyponym of fruit.\n",
    "2. Hypernyms are words of broader meaning than given word. Example - Fruit is hypernym of Apple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_sense_context_bag(sample_sentence, ambiguous_word, feature):\n",
    "    words = sample_sentence.split(' ')\n",
    "    words = [w.lower() for w in words]\n",
    "    words.remove(ambiguous_word)\n",
    "\n",
    "    sense_bag = []\n",
    "    context_bag = []\n",
    "    for word in words:\n",
    "        word_senses = wn.synsets(word)\n",
    "\n",
    "        if feature == 'hyponym':\n",
    "            word_hyponyms = list(itertools.chain(*map(lambda x: x.hyponyms(), word_senses)))\n",
    "            context_bag += word_hyponyms\n",
    "        if feature == 'hypernym':\n",
    "            word_hypernyms = list(itertools.chain(*map(lambda x: x.hypernyms(), word_senses)))\n",
    "            context_bag += word_hypernyms\n",
    "\n",
    "    ambiguous_word_senses = wn.synsets(ambiguous_word)\n",
    "    if feature=='hyponym':\n",
    "        sense_bag = list(map(lambda x: x.hyponyms(), ambiguous_word_senses))\n",
    "    if feature=='hypernym':\n",
    "        sense_bag = list(map(lambda x: x.hypernyms(), ambiguous_word_senses))\n",
    "    return sense_bag, set(context_bag)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_sense(sample_sentence, ambiguous_word, feature):\n",
    "    sense_bag, context_bag = get_sense_context_bag(sample_sentence, ambiguous_word, feature)\n",
    "\n",
    "    # count overlap between context bag and various sense bags, one for each sense\n",
    "    count_overlap = list(map(lambda x: len(set(x) and context_bag), sense_bag))\n",
    "    sense_idx = count_overlap.index(max(count_overlap))\n",
    "    sense_dfn = wn.synsets(ambiguous_word)[sense_idx].definition()\n",
    "    return sense_dfn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ambiguous word: apple\n",
      "Definition: fruit with red or yellow or green skin and sweet to tart crisp whitish flesh\n"
     ]
    }
   ],
   "source": [
    "sample_sentence = 'I am eating apple'\n",
    "ambiguous_word = 'apple'\n",
    "feature = 'hyponym'\n",
    "sense_dfn = get_sense(sample_sentence, ambiguous_word, feature) \n",
    "print('Ambiguous word:', ambiguous_word)   \n",
    "print('Definition:', sense_dfn)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Lesk's Algorithm\n",
    "\n",
    "Creating sense bags and context bag based on definition of words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def preprocess(sense):\n",
    "    words = sense.definition().split()\n",
    "    words = [word.lower() for word in words if word.isalnum() and word not in stopwords]\n",
    "    return words\n",
    "\n",
    "def Lesk_algorithm(ambiguous_word, context):\n",
    "    sense_bag = list(map(lambda x: preprocess(x), wn.synsets(ambiguous_word)))\n",
    "\n",
    "    context_words = context.strip().split(' ')\n",
    "    context_bag = []\n",
    "    for context_word in context_words:\n",
    "        context_bag += list(itertools.chain(*map(lambda x: preprocess(x), wn.synsets(context_word))))\n",
    "    context_bag = set(context_bag)\n",
    "    \n",
    "    count_overlap = list(map(lambda x: len(set(x) and context_bag), sense_bag))\n",
    "    sense_idx = count_overlap.index(max(count_overlap))\n",
    "    sense_dfn = wn.synsets(ambiguous_word)[sense_idx].definition()\n",
    "    return sense_dfn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ambiguous word: ash\n",
      "Definition: the residue that remains when something is burned\n"
     ]
    }
   ],
   "source": [
    "ambiguous_word = 'ash'\n",
    "context = 'coal'\n",
    "sense_dfn = Lesk_algorithm(ambiguous_word, context)\n",
    "print('Ambiguous word:', ambiguous_word)   \n",
    "print('Definition:', sense_dfn)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Walker's Algorithm\n",
    "\n",
    "Creating sense bags and context bag based on thesaurus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ambiguous word: burn\n",
      "Number of overlaps: [0, 0, 2, 0, 1, 2, 1, 3, 1, 2, 0, 0, 0, 0, 1, 0, 0, 1, 0, 2]\n",
      "Definition: undergo combustion\n"
     ]
    }
   ],
   "source": [
    "def get_thesaurus(sense):\n",
    "    return list(set(itertools.chain(*map(lambda x: x.lemma_names(), sense.hypernyms() + sense.hyponyms()))))\n",
    "\n",
    "def Walker_algorithm(ambiguous_word, context):\n",
    "    thesaurus_senses = list(map(lambda x: get_thesaurus(x), wn.synsets(ambiguous_word)))\n",
    "    assert len(thesaurus_senses) == len(wn.synsets(ambiguous_word))\n",
    "\n",
    "    context_words = context.strip().split(' ')\n",
    "    thesaurus_contexts = []\n",
    "    for context_word in context_words:\n",
    "        thesaurus_contexts += [list(set(itertools.chain(*map(lambda x: get_thesaurus(x), wn.synsets(context_word)))))]\n",
    "    assert len(thesaurus_contexts) == len(context_words)\n",
    "\n",
    "    count_overlaps = []\n",
    "    for thesaurus_sense in thesaurus_senses:\n",
    "        count_overlap = 0\n",
    "        for thesaurus_context in thesaurus_contexts:\n",
    "            if len(set(thesaurus_sense).intersection(set(thesaurus_context))) > 0:\n",
    "                count_overlap +=1\n",
    "        count_overlaps.append(count_overlap)\n",
    "        \n",
    "    print('Number of overlaps:', count_overlaps)\n",
    "    sense_idx = count_overlaps.index(max(count_overlaps))\n",
    "    sense_dfn = wn.synsets(ambiguous_word)[sense_idx].definition()\n",
    "    return sense_dfn\n",
    "\n",
    "ambiguous_word = 'burn'\n",
    "context = 'coal fire flame residue wood combust'\n",
    "\n",
    "print('Ambiguous word:', ambiguous_word)  \n",
    "sense_dfn = Walker_algorithm(ambiguous_word, context)\n",
    "print('Definition:', sense_dfn)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### WSD using Random Walk algorithm\n",
    "\n",
    "The problem with the above approaches is that we are assuming that the words in context are not ambiguous i.e. context words are capturing the right sense. However, it's possible that there are multiple ambiguous words in a sentence which we need to disambiguate all together.\n",
    "\n",
    "For this, we use Random Walk approach to calculate **PageRank importances**. The idea is that in a sentence some senses of ambiguous words correlate together and they all will contribute to each other in getting higher PageRank importance. Once we reach convergence according to PageRank criteria (limiting distribution of Markov Chain), for each ambiguous word, we consider sense with highest importance and assume it to be the right sense given sentence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get senses for words in sentence\n",
    "def get_senses(sentence):\n",
    "    words = sentence.split(' ')\n",
    "    senses = []\n",
    "    word_sense_labels = []\n",
    "    for word in words:\n",
    "        senses.append(wn.synsets(word))\n",
    "        word_sense_labels += list(map(lambda x: word + '-' + x.name(), wn.synsets(word)))\n",
    "    senses = list(set(itertools.chain(*senses)))\n",
    "\n",
    "    assert len(word_sense_labels) == len(senses)\n",
    "    sense2node = dict(zip(senses, range(len(senses))))\n",
    "    node2sense = {v:k for k,v in sense2node.items()}\n",
    "    return senses, word_sense_labels, sense2node, node2sense\n",
    "\n",
    "# adding nodes\n",
    "def add_nodes(G, senses):\n",
    "    nodes = range(len(senses))\n",
    "    G.add_nodes_from(nodes)\n",
    "    return G\n",
    "\n",
    "# adding edges\n",
    "def add_edges(G, senses, sense2node):\n",
    "    for sense1 in senses:\n",
    "        for sense2 in senses:\n",
    "            if sense1!=sense2:\n",
    "                def1 = set(preprocess(sense1))\n",
    "                def2 = set(preprocess(sense2))\n",
    "                similarity = len(def1.intersection(def2))\n",
    "                \n",
    "                node1 = sense2node[sense1]\n",
    "                node2 = sense2node[sense2]\n",
    "                G.add_edge(node1, node2, weight=similarity)\n",
    "    return G\n",
    "\n",
    "# normalizing 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!=0:\n",
    "                for neighbor in G.successors(node):\n",
    "                    G[node][neighbor]['weight']/= total_weight\n",
    "    return G\n",
    "\n",
    "# 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                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_pagerank_matrix(G, alpha):\n",
    "    n_nodes = len(G.nodes())\n",
    "\n",
    "    # building adjacent matrix\n",
    "    adj_matrix = np.zeros(shape=(n_nodes, n_nodes))\n",
    "    for edge in G.edges():\n",
    "        adj_matrix[edge[0], edge[1]] = 1\n",
    "\n",
    "    # building transition probability matrix\n",
    "    tran_matrix = adj_matrix / np.sum(adj_matrix, axis=1).reshape(-1,1)\n",
    "\n",
    "    # building random surfer matrix\n",
    "    random_surf = np.ones(shape = (n_nodes, n_nodes)) / n_nodes    \n",
    "\n",
    "    # building transition matrix for absorbing nodes\n",
    "    absorbing_nodes = np.zeros(shape = (n_nodes,))\n",
    "    for node in G.nodes():\n",
    "        if len(G.successors(node))==0:\n",
    "            absorbing_nodes[node] = 1\n",
    "    absorbing_node_matrix = np.outer(absorbing_nodes, np.ones(shape = (n_nodes,))) / n_nodes\n",
    "\n",
    "    # stochastic matrix\n",
    "    stochastic_matrix = tran_matrix + absorbing_node_matrix\n",
    "\n",
    "    # pagerank matrix\n",
    "    pagerank_matrix = alpha * stochastic_matrix + (1-alpha) * random_surf\n",
    "    return pagerank_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_walk(G, alpha, n_iter):\n",
    "    n_nodes = len(G.nodes())\n",
    "    initial_state = np.ones(shape=(n_nodes,)) / n_nodes\n",
    "    pagerank_matrix = make_pagerank_matrix(G, alpha)\n",
    "\n",
    "    new_initial_state = initial_state\n",
    "    print('Running random walk..')\n",
    "    NORM = []\n",
    "    for i in range(n_iter):\n",
    "        final_state = np.dot(np.transpose(pagerank_matrix), new_initial_state)\n",
    "        \n",
    "        prev_initial_state = new_initial_state\n",
    "        new_initial_state = final_state\n",
    "        L2 = np.linalg.norm(new_initial_state-prev_initial_state)\n",
    "        NORM.append(L2)\n",
    "        if np.allclose(new_initial_state, prev_initial_state):\n",
    "            break\n",
    "    print('Complete','\\n')\n",
    "    return final_state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_final_senses(sentence, pagerank_importances, word_sense_labels):\n",
    "    word_senses = np.array(list(map(lambda x: x.split('-'), word_sense_labels)))\n",
    "    words = word_senses[:, 0]\n",
    "    senses = word_senses[:, 1]\n",
    "\n",
    "    for word in sentence.split(' '):\n",
    "        idxs = np.where(words==word)[0]\n",
    "        word_pr = pagerank_importances[idxs]\n",
    "        sense_idx = np.where(word_pr == max(word_pr))[0][0]\n",
    "        sense_names = senses[idxs][sense_idx]\n",
    "        print(f'Senses for word - {word}:', sense_names)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def run(sentence, alpha, n_iter):\n",
    "    senses, word_sense_labels, sense2node, node2sense = get_senses(sentence)\n",
    "    G = nx.DiGraph()\n",
    "\n",
    "    # adding nodes\n",
    "    G = add_nodes(G, senses)\n",
    "\n",
    "    # adding edges\n",
    "    G = add_edges(G, senses, sense2node)\n",
    "\n",
    "    print('Number of nodes:', len(G.nodes()))\n",
    "    print('Number of edges:', len(G.edges()))\n",
    "    print() \n",
    "    \n",
    "    # remove nodes with no edges\n",
    "    G = remove_isolated_nodes(G)\n",
    "\n",
    "    # normalizing edge weights\n",
    "    G = normalize_edge_weights(G)\n",
    "\n",
    "    # running Random Walk\n",
    "    pagerank_importances = random_walk(G, alpha, n_iter)\n",
    "\n",
    "    # get final senses\n",
    "    get_final_senses(sentence, pagerank_importances, word_sense_labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of nodes: 99\n",
      "Number of edges: 9702\n",
      "\n",
      "Running random walk..\n",
      "Complete \n",
      "\n",
      "Senses for word - run: run.n.13\n",
      "Senses for word - walk: walk.n.01\n",
      "Senses for word - fast: fast.n.01\n",
      "Senses for word - speed: travel_rapidly.v.01\n"
     ]
    }
   ],
   "source": [
    "alpha = 0.1\n",
    "n_iter = 1000\n",
    "\n",
    "sentence = 'run walk fast speed'\n",
    "run(sentence, alpha, n_iter)"
   ]
  },
  {
   "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
}