Notebook 4, Error Modelling Function.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Error Modelling Function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Most of the string similarity functions focus on similarity or \"overlap\". This notebook demonstrates how to build the graphical structure which draws mappings for unmatched segments.\n",
    "\n",
    "Firstly, we import some math functions and the shingle functions that we made in earlier notebooks.\n",
    "Then we initialize two dictionaries, `port_ro_cog` and `port_ro_noncog`. \n",
    "\n",
    "`port_ro_cog` means cognates which corresponds to Portuguese - Romanian cognates and `port_ro_noncog` corresponds to Portuguese - Romanian non-cognates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import ceil, floor\n",
    "from src.shingle import *\n",
    "\n",
    "port_ro_cog = dict()\n",
    "port_ro_noncog = dict()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graphical Model Algorithm\n",
    "\n",
    "This algorithm takes *top* and *bottom* as the parameters and returns a graph in a form of a tuple.\n",
    "\n",
    "It takes three steps which are illustrated in the code:\n",
    "1. Initialization of sets\n",
    "2. Equalization of the set cardinalities\n",
    "3. Inserting the mappings of the set members into the graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def graph_model(first, second):\n",
    "    ''' Constructs the graphical structure between two shingle sets. '''\n",
    "    \n",
    "    # Step 1: Initialization\n",
    "    # If the given sets first and second are empty, we initialize \n",
    "    # them by inserting an empty token, (nun), into those sets.\n",
    "    \n",
    "    if len(first) == 0:\n",
    "        first.append(\"nun\") #insert empty token if found empty\n",
    "    if len(second) == 0:\n",
    "        second.append(\"nun\") #insert empty token if found empty\n",
    "        \n",
    "    # Step 2: Equalization of the set cardinalities\n",
    "    # The cardinalities of the sets first and second made\n",
    "    # equal by inserting empty tokens (nun) into the\n",
    "    # middle of the sets.\n",
    "    \n",
    "    # While loops to equalize the sizes\n",
    "    while(len(first) < len(second)):\n",
    "        pos = ceil(len(first) / 2)\n",
    "        first.insert(pos, \"nun\")\n",
    "    \n",
    "    # While loops to equalize the sizes\n",
    "    while(len(first) > len(second)):\n",
    "        pos = floor(len(second) / 2)\n",
    "        second.insert(pos, \"nun\")\n",
    "        \n",
    "    # Step 3: Inserting the mappings of the set members into the graph\n",
    "    # The empty graph is initialized as graph = {}.\n",
    "    # The directed edges are generated, originating from every set member\n",
    "    # of first to every set member of second. This results in a complete \n",
    "    # directed bipartite graph between first and second sets.\n",
    "    \n",
    "    # Pairs in tuples\n",
    "    graph = set() #Graph in sets to avoid duplicates\n",
    "    \n",
    "    for i in range(len(first)):\n",
    "        pair = (first[i], second[i]) # One to one mapping with same index\n",
    "        graph.add(pair)\n",
    "    for i in range(len(first) - 1):\n",
    "        pair = (first[i], second[i + 1]) # One to one mapping with an index ahead\n",
    "        graph.add(pair)\n",
    "    if len(first) > 1:\n",
    "        for i in range(1, len(first)):\n",
    "            pair = (first[i], second[i - 1]) # One to one mapping with an index before\n",
    "            graph.add(pair)\n",
    "    return graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Two functions are defined. `common_elements` is similar to list intersection. `uncommon_elements` is similar to symmetric difference."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def common_elements(list1, list2):\n",
    "    return [element for element in list1 if element in list2]\n",
    "\n",
    "def uncommon_elements(list1, list2):\n",
    "    return [element for element in list1 if element not in list2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that all functions are defined, we will populate our dictionaries with the graphical results that we obtained!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def init_dict():\n",
    "    \n",
    "    # for cognates\n",
    "    cogs = open(\"data/portuguese/graph_cognates_freq.txt\", \"r+\")\n",
    "    for line in cogs:\n",
    "        splits = line.rstrip().split()\n",
    "        port_ro_cog[(splits[1], splits[2])] = int(splits[0])\n",
    "    cogs.close()\n",
    "    \n",
    "    # for non cognates\n",
    "    noncogs = open(\"data/portuguese/graph_noncognates_freq.txt\", \"r+\")\n",
    "    for line in noncogs:\n",
    "        splits = line.rstrip().split()\n",
    "        port_ro_noncog[(splits[1], splits[2])] = int(splits[0])\n",
    "    noncogs.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The error modelling function, pi, is defined as,\n",
    "\n",
    "<img src=\"utils/graph.png\" alt=\"tfidf\" width=\"400px\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pi(source, target, k = 1):\n",
    "    query = two_ends(source, 2) #Your query\n",
    "    document = two_ends(target, 2) #Your document\n",
    "    qd = common_elements(query, document) # q cap d\n",
    "    first = uncommon_elements(query, qd) # q - (q cap d)\n",
    "    second = uncommon_elements(document, qd) # d - (q cap d)\n",
    "    graph = graph_model(first,second)\n",
    "    res = sum([port_ro_cog[i]**k for i in graph]) # sum the frequencies in the dictionary\n",
    "    return res / len(graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the following examples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "init_dict()\n",
    "pi(\"aspirat\", \"aspirar\")"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}