notebook_non-neural-version.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "45f41fdc-8c69-4448-9ad8-04c1874e1725",
   "metadata": {},
   "source": [
    "---\n",
    "### **<p style=\"text-align: center; text-decoration: underline;\">Natural Language Processing</p>**\n",
    "# **<p style=\"text-align: center;\">Practical: A bit of Morphological Warm up</p>**\n",
    "---\n",
    "\n",
    "> Realized by: *Zakaria Boulkhir* & *Omar Iken*.\n",
    "\n",
    "> Master 2, Data Science, Lille University.\n",
    "\n",
    "---\n",
    "\n",
    "### ■ __Overview__\n",
    "In this notebook, we will propose models for the shared-task task 0 problem. To do so, we will use the development data to design two models (a neural and a non neural) that given a lemma and a set of morphological attributes return the corresponding form.\n",
    "\n",
    "### ■ **<a name=\"content\">Contents</a>**\n",
    "\n",
    "- [1. Dataset](#section1)\n",
    "\n",
    "- [2. First Approach: Bag Of Words](#section2)\n",
    "\n",
    "- [3. Second Approach: Prefix-Suffix-based approach](#section3)\n",
    "\n",
    "- [4. Third Approach: Beyond Suffix-Prefix](#section4)\n",
    "\n",
    "- [5. Forth Approach: Clustering](#section5)\n",
    "\n",
    "\n",
    "### ■ **Libraries**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "be7a0775-1e53-4c08-bf31-bc8e23cdd395",
   "metadata": {},
   "outputs": [],
   "source": [
    "## numpy to handle arrays & matices\n",
    "import numpy as np\n",
    "\n",
    "## matplotlib & Seaborn to plot figures\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "\n",
    "## pandas to handle dataframes\n",
    "import pandas as pd\n",
    "from scipy import stats\n",
    "from tqdm import tqdm\n",
    "import codecs\n",
    "import os\n",
    "from utils.utils import *\n",
    "from utils.eval import *\n",
    "import unidecode\n",
    "\n",
    "## sklearn dependencies\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.metrics import mean_absolute_error, mean_absolute_error\n",
    "from sklearn.preprocessing import OneHotEncoder\n",
    "from sklearn.feature_extraction.text import CountVectorizer\n",
    "from sklearn.feature_extraction.text import TfidfTransformer\n",
    "from sklearn.naive_bayes import MultinomialNB\n",
    "\n",
    "from sklearn.ensemble import RandomForestClassifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e89771db-6da9-4372-a65d-c762f0c13f4a",
   "metadata": {},
   "outputs": [],
   "source": [
    "#-----------< Setting >------------#\n",
    "## set plots text font size & style\n",
    "sns.set(font_scale=1.2, style='whitegrid')\n",
    "plt.rcParams['figure.figsize'] = (12, 8)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7bfeed2f-02e6-492e-9986-4124a0a62325",
   "metadata": {},
   "source": [
    "### ■ **<a name=\"warmup\">1. Dataset</a>** [(&#8593;)](#content)\n",
    "The objective of this section is to write down a very simple system that predict morphological attributes. To do so, we will use the data available [here](https://github.com/sigmorphon2020/task0-data). Then, we will pick a language we do not speak, for instance *Akan (aka)*, and we explore the data. Of course our models should be applicable to other languages.\n",
    "\n",
    ">**Note:**  The choice of the language *Akan* is due to the fact that it covers most of the cases we will deal with in this notebook. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "3eef3190-ac67-40a2-9675-c5655e3d613f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of training samples: 3374\n",
      "Number of testing samples : 910\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>lemma</th>\n",
       "      <th>form</th>\n",
       "      <th>attributes</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>piga</td>\n",
       "      <td>amepiga</td>\n",
       "      <td>V;PRF;FIN;IND;SG;3;PST</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>kamilisha</td>\n",
       "      <td>wangekamilisha</td>\n",
       "      <td>V;FIN;COND;PL;3;PRS</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>fuata</td>\n",
       "      <td>walifuata</td>\n",
       "      <td>V;FIN;IND;PL;3;PST</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>tengeneza</td>\n",
       "      <td>nitatengeneza</td>\n",
       "      <td>V;FIN;IND;SG;1;FUT</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>uwa</td>\n",
       "      <td>anauwa</td>\n",
       "      <td>V;DEF;FIN;IND;SG;3;PRS</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "       lemma            form              attributes\n",
       "0       piga         amepiga  V;PRF;FIN;IND;SG;3;PST\n",
       "1  kamilisha  wangekamilisha     V;FIN;COND;PL;3;PRS\n",
       "2      fuata       walifuata      V;FIN;IND;PL;3;PST\n",
       "3  tengeneza   nitatengeneza      V;FIN;IND;SG;1;FUT\n",
       "4        uwa          anauwa  V;DEF;FIN;IND;SG;3;PRS"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## file path\n",
    "train_file = 'data/DEVELOPMENT-LANGUAGES/niger-congo/swa.trn'\n",
    "test_file = 'data/GOLD-TEST/swa.tst'\n",
    "\n",
    "## dataframe\n",
    "df_train = read_file(train_file)\n",
    "df_test = read_file(test_file)\n",
    "\n",
    "## number of training & testing samples\n",
    "n_train = df_train.shape[0]\n",
    "n_test = df_test.shape[0]\n",
    "print(f'Number of training samples: {n_train}')\n",
    "print(f'Number of testing samples : {n_test}')\n",
    "\n",
    "## dispaly some samples\n",
    "df_train.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5f38e05-5936-4c53-b126-af5117890a8f",
   "metadata": {},
   "source": [
    "**Unique Characters:** Get the unique the characters of the language."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f6fa0fe2-ad89-4460-9e22-7364e5ffc5d1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> Number of unique characters: 24\n",
      "> Characters: a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, r, s, t, u, v, w, y, z\n"
     ]
    }
   ],
   "source": [
    "## get the number of unique characters\n",
    "text = ''.join(df_train[['lemma', 'form']].to_numpy().flatten())\n",
    "\n",
    "## get (number of) unique characters\n",
    "unique_chars = sorted(set(text))\n",
    "n_chars = len(unique_chars)\n",
    "\n",
    "print(f\"> Number of unique characters: {n_chars}\\n> Characters: {', '.join(unique_chars)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f1cb2368-1c9f-48e4-a921-eee51aca90f5",
   "metadata": {},
   "source": [
    "**Morphological attributes:** histogram of different attributes, this will allow us to see which one is dominating."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d73fca13-83fd-40a8-8f58-da71b84270c9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> Number of unique morphological attributes: 16\n",
      "> Morphological attributes: 1, 2, 3, COND, DEF, FIN, FUT, HAB, IND, INDF, PL, PRF, PRS, PST, SG, V\n"
     ]
    }
   ],
   "source": [
    "## get unique morphological attributes\n",
    "morph_attrs = ';'.join(df_train['attributes'].to_list()).split(';')\n",
    "morph_attrs = np.asarray(morph_attrs)\n",
    "unique_attrs = sorted(set(morph_attrs)) ## sort to keep same order\n",
    "n_attrs = len(unique_attrs)\n",
    "\n",
    "print(f\"> Number of unique morphological attributes: {n_attrs}\\n> Morphological attributes: {', '.join(unique_attrs)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "533f6876-cc9e-43b0-858a-422ac945775d",
   "metadata": {},
   "source": [
    "### ■ **<a name=\"section2\">2. First Approach: Bag of words (Characters)</a>** [(&#8593;)](#content)\n",
    "For this first simple approach, we use the bag-of-words method.\n",
    "The particularity of our proposed method is that we will use the bag-of-words method on characters instead of words (bag-of-characters)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff431d84-567a-44e4-afd9-77795ce9cc0d",
   "metadata": {},
   "source": [
    "#### **2.1. Modeling the data**\n",
    "Bag-of-characters will allow us to have a feature space of fixed size, since the number of characters in each language is fixed unlike its set of words.\n",
    "Also, unlike the bag-of-words on words method, this method will allow us to capture all words, even on the test set.\n",
    "Therefore, an important step of this method consists of bringing all lemmas and forms to a fixed size (number of characters), in fact, in our case we compute the maximum possible number of characters for a lemma for a given language and we map all other words to that maximum value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "0692cddd-4360-4ccc-9993-1e88aa0bb023",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'1': 1,\n",
       " '2': 2,\n",
       " '3': 3,\n",
       " 'COND': 4,\n",
       " 'DEF': 5,\n",
       " 'FIN': 6,\n",
       " 'FUT': 7,\n",
       " 'HAB': 8,\n",
       " 'IND': 9,\n",
       " 'INDF': 10,\n",
       " 'PL': 11,\n",
       " 'PRF': 12,\n",
       " 'PRS': 13,\n",
       " 'PST': 14,\n",
       " 'SG': 15,\n",
       " 'V': 16}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## bag of words for characters\n",
    "char_dict = dict(zip(unique_chars, range(1, len(unique_chars)+1)))\n",
    "inv_char_dict = {n:char for char, n in char_dict.items()}\n",
    "\n",
    "## bag of words for attributes\n",
    "attr_dict = {attr:i for i, attr in enumerate(unique_attrs, start=1)}\n",
    "attr_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d46815aa-b449-460a-a22d-5461f0dd31c9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The maximum possible number of character in a lemma: 9\n",
      "The maximum possible number of character in a form : 16\n",
      "The maximum possible number of attributes for a given lemma & form: 7\n"
     ]
    }
   ],
   "source": [
    "## compute maximum possible characters in a lemma and a form\n",
    "max_lemma_length = df_train['lemma'].apply(list).apply(len).max()\n",
    "max_form_length = df_train['form'].apply(lambda x: len(list(x))).max()\n",
    "\n",
    "## compute maximum possible number of attributes\n",
    "max_n_attrs = df_train['attributes'].apply(lambda x: len(x.split(';'))).max()\n",
    "\n",
    "## \n",
    "print(f'The maximum possible number of character in a lemma: {max_lemma_length}')\n",
    "print(f'The maximum possible number of character in a form : {max_form_length}')\n",
    "print(f'The maximum possible number of attributes for a given lemma & form: {max_n_attrs}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "c2e48765-42c4-40b2-a2f2-9745eda8bda2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pad(array, n, val):\n",
    "    \"\"\"to pad a given vector to size n with value val\"\"\"\n",
    "    return np.append(array, np.full(n - len(array), val))\n",
    "\n",
    "def vect2word(vect, char_dict):\n",
    "    word = ''.join([char_dict[i] for i in vect if i])\n",
    "    return word\n",
    "\n",
    "def create_trainset(lemmas, forms, attributes, max_lemma, max_form, max_attrs):\n",
    "    \"\"\"create a bag of words training set\"\"\"\n",
    "    ## create X and y train\n",
    "    X_train, y_train = [], []\n",
    "    for lemma, form, set_attrs in zip(lemmas, forms, attributes):\n",
    "        x, y = [], []\n",
    "        \n",
    "        l = []\n",
    "        for char in lemma:\n",
    "            l.append(char_dict[char])\n",
    "            \n",
    "        for char in form:\n",
    "            y.append(char_dict[char])\n",
    "\n",
    "        at = []\n",
    "        for attr in set_attrs:\n",
    "            at.append(attr_dict[attr])\n",
    "\n",
    "\n",
    "        x = np.append(pad(l, max_lemma, 0), pad(at, max_attrs, 0))\n",
    "        X_train.append(x)\n",
    "        y_train.append(pad(y, max_form, 0))\n",
    "        \n",
    "    return np.array(X_train), np.array(y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "f50cd0b4-ed53-482b-aa36-fccde9e42ef9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3374, 16)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## get training & test set\n",
    "X_train, y_train = create_trainset(df_train['lemma'].values,\n",
    "                                   df_train['form'].values, \n",
    "                                   df_train['attributes'].apply(lambda x:x.split(';')).values,\n",
    "                                   max_lemma_length, max_form_length, max_n_attrs)\n",
    "\n",
    "X_test, y_test = create_trainset(df_test['lemma'].values, \n",
    "                                 df_test['form'].values,\n",
    "                                 df_test['attributes'].apply(lambda x:x.split(';')).values, \n",
    "                                 max_lemma_length, max_form_length, max_n_attrs)\n",
    "\n",
    "X_train.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92631bfb-5f99-4c41-a7d8-768cd0696122",
   "metadata": {},
   "source": [
    "#### **2.2. Train & Evaluate the model**\n",
    "We mainly rely on Random Forest algorithms because they have shown promising results and we think they are suitable for our case, since we are working on a classification problem of sorts. Another interesting and very useful fact about Random Forests is their ability to perform multi-class classification on several features at the same time, i.e. we predict several features using a single model."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b47695a-5299-4129-aa0e-7c6390484013",
   "metadata": {},
   "source": [
    "**Training**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "ed365f70-758d-4661-8b0f-f688fd7a359c",
   "metadata": {},
   "outputs": [
    {
     "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>true</th>\n",
       "      <th>predicted</th>\n",
       "      <th>Lanvenshtein distance</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>nitakamilisha</td>\n",
       "      <td>tttaamiiiiha</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>nilifagia</td>\n",
       "      <td>nilifacha</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>wanaponda</td>\n",
       "      <td>wanaponda</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>tungalimwita</td>\n",
       "      <td>tungalinunua</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>ameondoa</td>\n",
       "      <td>ameongea</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "            true     predicted Lanvenshtein distance\n",
       "0  nitakamilisha  tttaamiiiiha                     5\n",
       "1      nilifagia     nilifacha                     2\n",
       "2      wanaponda     wanaponda                     0\n",
       "3   tungalimwita  tungalinunua                     4\n",
       "4       ameondoa      ameongea                     2"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## create & fit an RF model\n",
    "clf = RandomForestClassifier(random_state=0)\n",
    "clf.fit(X_train, y_train)\n",
    "\n",
    "## make predictions\n",
    "y_pred = clf.predict(X_test)\n",
    "\n",
    "## vects to words\n",
    "words_prediction = [vect2word(vect, inv_char_dict) for vect in y_pred]\n",
    "words_test = [vect2word(vect, inv_char_dict) for vect in y_test]\n",
    "\n",
    "## compute Lanvenshtein distance\n",
    "dist = [distance(word1, word2) for word1, word2 in zip(words_test, words_prediction)]\n",
    "df_pred = pd.DataFrame([words_test, words_prediction, dist], \n",
    "                       index=['true', 'predicted', 'Lanvenshtein distance']).T\n",
    "df_pred.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b8c382f0-b2aa-41c1-9601-3e66faf8db20",
   "metadata": {},
   "source": [
    "**Evaluation**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "0ce7cf39-0222-44a9-9e45-773b59bbdbde",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "- The word by word accuracy          : 0.22637362637362637\n",
      "- The character by character accuracy: 0.8314361830951804\n"
     ]
    }
   ],
   "source": [
    "print(f'- The word by word accuracy          : {word_accuracy(words_prediction, words_test)}')\n",
    "print(f'- The character by character accuracy: {character_accuracy(words_prediction, words_test)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e895fd79-f1c8-4fb3-bf98-52f02710f904",
   "metadata": {},
   "source": [
    ">**Comments:**\n",
    "> - The model was able to learn the prefixes of most forms.\n",
    "> - The model is not as accurate on the body of the lemma.\n",
    "> - An interesting idea is to create a model that predicts the prefixes and suffixes of the form, and then put them together with the lamma to get the actual form."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "344d7806-1893-4a66-8ded-a6235f7ed2cc",
   "metadata": {},
   "source": [
    "### ■ **<a name=\"section3\">3. Second Approach: Prefix-suffix-based approach</a>** [(&#8593;)](#content)\n",
    "For this second approach, we proposed a new method that attempts to predict the prefix and suffix of a given lemma and, by combining them with the lemma, obtain the actual form.\n",
    "To do this, we extract both the prefix and suffix of each form from the given lemma, and then associate with each prefix and suffix a number that will be predicted by the model."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13eb36dc-6ed9-46ff-8dd6-47593b4d3899",
   "metadata": {},
   "source": [
    "#### **3.1. Modeling the data**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "8983c364-2d3f-4504-b58c-efb2cf43ca30",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_prefix(form, lemma):\n",
    "    \"\"\"return the prefix from the given form and lemma\"\"\"\n",
    "    if lemma in form:\n",
    "        idx = form.index(lemma)\n",
    "        return form[:idx]\n",
    "    return ''\n",
    "\n",
    "def get_suffix(form, lemma):\n",
    "    \"\"\"return the suffix from the given lemma and form\"\"\"\n",
    "    if lemma in form:\n",
    "        idx = form.index(lemma)\n",
    "        return form[idx + len(lemma):]\n",
    "    return ''\n",
    "\n",
    "def remove_prefix(form, prefix):\n",
    "    \"\"\"remove the prefix from the form\"\"\"\n",
    "    if form.startswith(prefix):\n",
    "        return form[len(prefix):]\n",
    "    return form\n",
    "\n",
    "def remove_suffix(form, suffix):\n",
    "    \"\"\"remove the suffix from the form\"\"\"\n",
    "    if suffix and form.endswith(suffix):\n",
    "        return form[:-len(suffix)]\n",
    "    return form\n",
    "\n",
    "def get_lemma(form, prefix, suffix):\n",
    "    \"\"\"return the lemma from the form given the prefix and the suffix\"\"\"\n",
    "    lemma = remove_suffix(form, suffix)\n",
    "    lemma = remove_prefix(lemma, prefix)\n",
    "    return lemma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "0b16a1af-55f4-4007-8875-3f9b77479eaa",
   "metadata": {},
   "outputs": [
    {
     "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>lemma</th>\n",
       "      <th>form</th>\n",
       "      <th>attributes</th>\n",
       "      <th>prefix</th>\n",
       "      <th>suffix</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>piga</td>\n",
       "      <td>amepiga</td>\n",
       "      <td>V;PRF;FIN;IND;SG;3;PST</td>\n",
       "      <td>ame</td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>kamilisha</td>\n",
       "      <td>wangekamilisha</td>\n",
       "      <td>V;FIN;COND;PL;3;PRS</td>\n",
       "      <td>wange</td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>fuata</td>\n",
       "      <td>walifuata</td>\n",
       "      <td>V;FIN;IND;PL;3;PST</td>\n",
       "      <td>wali</td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>tengeneza</td>\n",
       "      <td>nitatengeneza</td>\n",
       "      <td>V;FIN;IND;SG;1;FUT</td>\n",
       "      <td>nita</td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>uwa</td>\n",
       "      <td>anauwa</td>\n",
       "      <td>V;DEF;FIN;IND;SG;3;PRS</td>\n",
       "      <td>ana</td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "       lemma            form              attributes prefix suffix\n",
       "0       piga         amepiga  V;PRF;FIN;IND;SG;3;PST    ame       \n",
       "1  kamilisha  wangekamilisha     V;FIN;COND;PL;3;PRS  wange       \n",
       "2      fuata       walifuata      V;FIN;IND;PL;3;PST   wali       \n",
       "3  tengeneza   nitatengeneza      V;FIN;IND;SG;1;FUT   nita       \n",
       "4        uwa          anauwa  V;DEF;FIN;IND;SG;3;PRS    ana       "
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_train['prefix'] = df_train.apply(lambda col: get_prefix(col.form, col.lemma), axis=1)\n",
    "df_train['suffix'] = df_train.apply(lambda col: get_suffix(col.form, col.lemma), axis=1)\n",
    "df_train.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "b0b5cdd7-9b32-4ba7-b23c-b37118419d28",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3374, 2)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## create target array\n",
    "y_train = df_train[['prefix', 'suffix']].to_numpy()\n",
    "y_train.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1bfb623e-f174-4873-a717-40986c4dd2cb",
   "metadata": {},
   "source": [
    "#### **3.2. Training & Evaluating the model**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "834951dd-3f35-4eb4-b44f-050fe23b73fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "## create & fit an RF model\n",
    "clf = RandomForestClassifier(random_state=0)\n",
    "clf.fit(X_train, y_train)\n",
    "\n",
    "## make predictions\n",
    "y_pred = clf.predict(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "ab8835bc-cfc1-4d75-8579-925e1e56fe23",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_predictions(X_test, y_pred):\n",
    "    pred_forms = []\n",
    "    for lemma, y in zip(X_test, y_pred):\n",
    "        prefix, suffix = y\n",
    "        form = prefix + lemma + suffix\n",
    "        pred_forms.append(form)\n",
    "    return pred_forms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "4a5a527d-03a5-4c31-9979-7f8d9f12759b",
   "metadata": {},
   "outputs": [
    {
     "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>true</th>\n",
       "      <th>predicted</th>\n",
       "      <th>Lanvenshtein distance</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>nitakamilisha</td>\n",
       "      <td>nitakamilisha</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>nilifagia</td>\n",
       "      <td>nilifagia</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>wanaponda</td>\n",
       "      <td>wanaponda</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>tungalimwita</td>\n",
       "      <td>tungalimwita</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>ameondoa</td>\n",
       "      <td>ameondoa</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "            true      predicted Lanvenshtein distance\n",
       "0  nitakamilisha  nitakamilisha                     0\n",
       "1      nilifagia      nilifagia                     0\n",
       "2      wanaponda      wanaponda                     0\n",
       "3   tungalimwita   tungalimwita                     0\n",
       "4       ameondoa       ameondoa                     0"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## vector to word\n",
    "words_test = [vect2word(vect, inv_char_dict) for vect in y_test]\n",
    "words_prediction = get_predictions(df_test['lemma'].to_numpy(), y_pred)\n",
    "\n",
    "## compute Lanvenshtein distance\n",
    "dist = [distance(word1, word2) for word1, word2 in zip(words_test, words_prediction)]\n",
    "df_pred = pd.DataFrame([words_test, words_prediction, dist], \n",
    "                       index=['true', 'predicted', 'Lanvenshtein distance']).T\n",
    "df_pred.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "a89f3e24-b04a-4f5b-81a3-cd8f0a32a259",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "- The word by word accuracy          : 0.9989010989010989\n",
      "- The character by character accuracy: 0.9997573404513468\n"
     ]
    }
   ],
   "source": [
    "print(f'- The word by word accuracy          : {word_accuracy(words_prediction, words_test)}')\n",
    "print(f'- The character by character accuracy: {character_accuracy(words_prediction, words_test)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed47efdb-7d5b-4b55-8267-a560b23a9c3d",
   "metadata": {},
   "source": [
    "#### **3.3. Improving further**\n",
    "\n",
    "**Encode attributes**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "b2fd402a-737b-45da-ab8b-83f5ef1cc108",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "encoded attributes shape: (3374, 16)\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>1</th>\n",
       "      <th>2</th>\n",
       "      <th>3</th>\n",
       "      <th>COND</th>\n",
       "      <th>DEF</th>\n",
       "      <th>FIN</th>\n",
       "      <th>FUT</th>\n",
       "      <th>HAB</th>\n",
       "      <th>IND</th>\n",
       "      <th>INDF</th>\n",
       "      <th>PL</th>\n",
       "      <th>PRF</th>\n",
       "      <th>PRS</th>\n",
       "      <th>PST</th>\n",
       "      <th>SG</th>\n",
       "      <th>V</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   1  2  3  COND  DEF  FIN  FUT  HAB  IND  INDF  PL  PRF  PRS  PST  SG  V\n",
       "0  0  0  1     0    0    1    0    0    1     0   0    1    0    1   1  1\n",
       "1  0  0  1     1    0    1    0    0    0     0   1    0    1    0   0  1\n",
       "2  0  0  1     0    0    1    0    0    1     0   1    0    0    1   0  1\n",
       "3  1  0  0     0    0    1    1    0    1     0   0    0    0    0   1  1\n",
       "4  0  0  1     0    1    1    0    0    1     0   0    0    1    0   1  1"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## bag of words for attributes\n",
    "attributes_dict = dict(zip(unique_attrs, range(n_attrs)))\n",
    "\n",
    "def encode_attributes(attributes, max_n_attrs, attributes_dict):\n",
    "    \"\"\"(multi-)onehot encoding for attributes\"\"\"\n",
    "    encoded = np.zeros(len(attributes_dict))\n",
    "    encoded[[attributes_dict[attr] for attr in attributes]] = 1\n",
    "    return encoded\n",
    "    \n",
    "## encode attributes   \n",
    "encoded_attributes = np.array([encode_attributes(attrs.split(';'), max_n_attrs, attributes_dict) for attrs in df_train['attributes'].to_list()])\n",
    "encoded_test_attributes = np.array([encode_attributes(attrs.split(';'), max_n_attrs, attributes_dict) for attrs in df_test['attributes'].to_list()])\n",
    "print(f'encoded attributes shape: {encoded_attributes.shape}')\n",
    "\n",
    "pd.DataFrame(encoded_attributes, columns=unique_attrs).astype('int').head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "64535b48-9dea-4c0e-9bf4-31b5ad546781",
   "metadata": {},
   "source": [
    "**Create new training data**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "90a48116-eb53-4e20-8565-6321fe66e965",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3374, 25)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## new training data\n",
    "new_X_train = np.concatenate((X_train[:, :max_lemma_length], encoded_attributes), axis=1)\n",
    "new_X_test = np.concatenate((X_test[:, :max_lemma_length], encoded_test_attributes), axis=1)\n",
    "new_X_train.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d654236-8ce8-4055-a9bb-18b9383486e6",
   "metadata": {},
   "source": [
    "**Training**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "f08cdf7d-a1f2-4c13-87bc-4715fa4e8fe7",
   "metadata": {},
   "outputs": [
    {
     "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>true</th>\n",
       "      <th>predicted</th>\n",
       "      <th>Lanvenshtein distance</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>nitakamilisha</td>\n",
       "      <td>nitakamilisha</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>nilifagia</td>\n",
       "      <td>nilifagia</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>wanaponda</td>\n",
       "      <td>wanaponda</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>tungalimwita</td>\n",
       "      <td>tungalimwita</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>ameondoa</td>\n",
       "      <td>ameondoa</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "            true      predicted Lanvenshtein distance\n",
       "0  nitakamilisha  nitakamilisha                     0\n",
       "1      nilifagia      nilifagia                     0\n",
       "2      wanaponda      wanaponda                     0\n",
       "3   tungalimwita   tungalimwita                     0\n",
       "4       ameondoa       ameondoa                     0"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## create & fit an RF model\n",
    "clf = RandomForestClassifier(random_state=0)\n",
    "clf.fit(new_X_train, y_train)\n",
    "\n",
    "## make predictions\n",
    "y_pred = clf.predict(new_X_test)\n",
    "\n",
    "## vects to words\n",
    "words_prediction = get_predictions(df_test['lemma'].to_numpy(), y_pred)\n",
    "words_test = [vect2word(vect, inv_char_dict) for vect in y_test]\n",
    "\n",
    "## compute Lanvenshtein distance\n",
    "dist = [distance(word1, word2) for word1, word2 in zip(words_test, words_prediction)]\n",
    "df_pred = pd.DataFrame([words_test, words_prediction, dist], \n",
    "                       index=['true', 'predicted', 'Lanvenshtein distance']).T\n",
    "df_pred.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "41b1536a-8e75-49fd-a880-4564079ea13e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "- The word by word accuracy          : 1.0\n",
      "- The character by character accuracy: 1.0\n"
     ]
    }
   ],
   "source": [
    "print(f'- The word by word accuracy          : {word_accuracy(words_prediction, words_test)}')\n",
    "print(f'- The character by character accuracy: {character_accuracy(words_prediction, words_test)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f56d709-e168-4877-a59a-ae34e40f036d",
   "metadata": {},
   "source": [
    ">**Comments:**\n",
    "- The improved version works pretty well...\n",
    "- BUT, what about languages or forms where there is a change in the whole lemma to a get a form, for instance a `lemma=waba` and `form=wada`.\n",
    "- We need a model that can capture this kind of information. It will allow us to predict the form of a lemma even if there structure is different."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6496105-7a96-4fc3-9231-bb06361f72b7",
   "metadata": {},
   "source": [
    "### ■ **<a name=\"section4\">4. Third Approach: Beyond Prefix & Suffix</a>** [(&#8593;)](#content)\n",
    "The previously proposed method suffers when the lemma is not part of the body of the form. \n",
    "To solve this problem, we propose a new approach, which is in a way an improvement of the previous one.\n",
    "This new approach takes into account the root of a given lemma and form and tries to capture what changes between the two representations (lemma and form).\n",
    "\n",
    "#### **4.1. Modeling of the data**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "097fdfcd-33c8-4c89-818f-87bf67149eb4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_root(string_1, string_2):\n",
    "    \"\"\"return the root intersection of two strings\"\"\"\n",
    "    \n",
    "    if len(string_1) > len(string_2):\n",
    "        larger_s = string_1 \n",
    "        smaller_s = string_2\n",
    "    else:\n",
    "        larger_s = string_2\n",
    "        smaller_s = string_1\n",
    "        \n",
    "    inter = ''\n",
    "    for i in range(len(larger_s)):\n",
    "        for j in range(i, len(larger_s)+1):\n",
    "            if j - i < len(inter):\n",
    "                continue\n",
    "            part = larger_s[i:j]\n",
    "            \n",
    "            if part in smaller_s and len(part) > len(inter):\n",
    "                inter = part\n",
    "        \n",
    "    return inter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "d52391e0-1805-43fc-9bd6-039af9935049",
   "metadata": {},
   "outputs": [
    {
     "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>lemma</th>\n",
       "      <th>form</th>\n",
       "      <th>attributes</th>\n",
       "      <th>prefix</th>\n",
       "      <th>suffix</th>\n",
       "      <th>root</th>\n",
       "      <th>lemma_prefix</th>\n",
       "      <th>form_prefix</th>\n",
       "      <th>lemma_suffix</th>\n",
       "      <th>form_suffix</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>piga</td>\n",
       "      <td>amepiga</td>\n",
       "      <td>V;PRF;FIN;IND;SG;3;PST</td>\n",
       "      <td>ame</td>\n",
       "      <td></td>\n",
       "      <td>piga</td>\n",
       "      <td></td>\n",
       "      <td>ame</td>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>kamilisha</td>\n",
       "      <td>wangekamilisha</td>\n",
       "      <td>V;FIN;COND;PL;3;PRS</td>\n",
       "      <td>wange</td>\n",
       "      <td></td>\n",
       "      <td>kamilisha</td>\n",
       "      <td></td>\n",
       "      <td>wange</td>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>fuata</td>\n",
       "      <td>walifuata</td>\n",
       "      <td>V;FIN;IND;PL;3;PST</td>\n",
       "      <td>wali</td>\n",
       "      <td></td>\n",
       "      <td>fuata</td>\n",
       "      <td></td>\n",
       "      <td>wali</td>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>tengeneza</td>\n",
       "      <td>nitatengeneza</td>\n",
       "      <td>V;FIN;IND;SG;1;FUT</td>\n",
       "      <td>nita</td>\n",
       "      <td></td>\n",
       "      <td>tengeneza</td>\n",
       "      <td></td>\n",
       "      <td>nita</td>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>uwa</td>\n",
       "      <td>anauwa</td>\n",
       "      <td>V;DEF;FIN;IND;SG;3;PRS</td>\n",
       "      <td>ana</td>\n",
       "      <td></td>\n",
       "      <td>uwa</td>\n",
       "      <td></td>\n",
       "      <td>ana</td>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "       lemma            form              attributes prefix suffix       root  \\\n",
       "0       piga         amepiga  V;PRF;FIN;IND;SG;3;PST    ame              piga   \n",
       "1  kamilisha  wangekamilisha     V;FIN;COND;PL;3;PRS  wange         kamilisha   \n",
       "2      fuata       walifuata      V;FIN;IND;PL;3;PST   wali             fuata   \n",
       "3  tengeneza   nitatengeneza      V;FIN;IND;SG;1;FUT   nita         tengeneza   \n",
       "4        uwa          anauwa  V;DEF;FIN;IND;SG;3;PRS    ana               uwa   \n",
       "\n",
       "  lemma_prefix form_prefix lemma_suffix form_suffix  \n",
       "0                      ame                           \n",
       "1                    wange                           \n",
       "2                     wali                           \n",
       "3                     nita                           \n",
       "4                      ana                           "
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## extract root\n",
    "df_train['root'] = df_train.apply(lambda col: get_root(col.lemma, col.form), axis=1)\n",
    "\n",
    "## extract prefixes\n",
    "df_train['lemma_prefix'] = df_train.apply(lambda col: get_prefix(col.lemma, col.root), axis=1)\n",
    "df_train['form_prefix'] = df_train.apply(lambda col: get_prefix(col.form, col.root), axis=1)\n",
    "\n",
    "## extract suffixes\n",
    "df_train['lemma_suffix'] = df_train.apply(lambda col: get_suffix(col.lemma, col.root), axis=1)\n",
    "df_train['form_suffix'] = df_train.apply(lambda col: get_suffix(col.form, col.root), axis=1)\n",
    "\n",
    "df_train.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "2b667272-6aa8-42a0-9d0b-669d85ed520e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3374, 9)"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def bag_of_chars(lemmas, max_lemma):\n",
    "    \"\"\"create a bag of words training set\"\"\"\n",
    "    ## create X and y train\n",
    "    X_train = []\n",
    "    for lemma in lemmas:\n",
    "        \n",
    "        x = []\n",
    "        for char in lemma:\n",
    "            x.append(char_dict[char])\n",
    "            \n",
    "        X_train.append(pad(x, max_lemma, 0))\n",
    "        \n",
    "    return np.array(X_train)\n",
    "\n",
    "## get training & test set\n",
    "X_train = bag_of_chars(df_train['lemma'].to_numpy(), max_lemma_length)\n",
    "X_test  = bag_of_chars(df_test['lemma'].to_numpy(), max_lemma_length)\n",
    "X_train.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "9bb80ab7-683e-4a8d-b650-9e85e5cbac4d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3374, 11)"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## bag of words\n",
    "form_prefix_dict  = dict(zip(df_train['form_prefix'].unique(), range(1, len(df_train['form_prefix'].unique())+1)))\n",
    "form_suffix_dict  = dict(zip(df_train['form_suffix'].unique(), range(1, len(df_train['form_suffix'].unique())+1)))\n",
    "\n",
    "inv_form_pref_dict = {n:pref for pref, n in form_prefix_dict.items()}\n",
    "inv_form_suff_dict = {n:suff for suff, n in form_suffix_dict.items()}\n",
    "\n",
    "## encode roots, suffixes & prefixes\n",
    "max_length_root = df_train['root'].apply(len).max()\n",
    "encoded_roots = bag_of_chars(df_train['root'].to_list(), max_length_root)\n",
    "encoded_form_suffix  = df_train['form_suffix'].apply(form_suffix_dict.get).to_numpy().reshape(-1, 1)\n",
    "encoded_form_prefix  = df_train['form_prefix'].apply(form_prefix_dict.get).to_numpy().reshape(-1, 1)\n",
    "\n",
    "## create target labels\n",
    "y_train = np.concatenate((encoded_roots, encoded_form_prefix, encoded_form_suffix), axis=1)\n",
    "y_train.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "3c006afc-6e99-404c-8353-6800901a0bf2",
   "metadata": {},
   "outputs": [],
   "source": [
    "## create & fit the model\n",
    "clf = RandomForestClassifier()\n",
    "clf.fit(X_train, y_train)\n",
    "\n",
    "## make predictions\n",
    "y_pred = clf.predict(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "b7331b46-3855-480b-9495-28323521734f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_predictions(X_test, y_pred):\n",
    "    \n",
    "    predictions = []\n",
    "    for x, y in zip(X_test, y_pred):\n",
    "        root, form_pref, form_suff = y[:max_length_root], *y[max_length_root:]\n",
    "        pref = inv_form_pref_dict[form_pref] \n",
    "        suff = inv_form_suff_dict[form_suff]\n",
    "        form = pref + vect2word(root, inv_char_dict) + suff\n",
    "        predictions.append(form)\n",
    "    return predictions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "023013b2-f197-4ea2-b489-109e79ce5977",
   "metadata": {},
   "outputs": [
    {
     "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>true</th>\n",
       "      <th>predicted</th>\n",
       "      <th>Lanvenshtein distance</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>nitakamilisha</td>\n",
       "      <td>ulikamilisha</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>nilifagia</td>\n",
       "      <td>ningefagia</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>wanaponda</td>\n",
       "      <td>uhuponda</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>tungalimwita</td>\n",
       "      <td>nimemwita</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>ameondoa</td>\n",
       "      <td>mnaondoa</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "            true     predicted Lanvenshtein distance\n",
       "0  nitakamilisha  ulikamilisha                     4\n",
       "1      nilifagia    ningefagia                     3\n",
       "2      wanaponda      uhuponda                     4\n",
       "3   tungalimwita     nimemwita                     6\n",
       "4       ameondoa      mnaondoa                     3"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## vects to words\n",
    "words_prediction = get_predictions(X_test, y_pred)\n",
    "words_test = [vect2word(vect, inv_char_dict) for vect in y_test]\n",
    "\n",
    "## compute Lanvenshtein distance\n",
    "dist = [distance(word1, word2) for word1, word2 in zip(words_test, words_prediction)]\n",
    "df_pred = pd.DataFrame([words_test, words_prediction, dist], \n",
    "                       index=['true', 'predicted', 'Lanvenshtein distance']).T\n",
    "df_pred.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "1dcbba7e-de5b-4e22-896a-808e655edb50",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "- The word by word accuracy          : 0.0\n",
      "- The character by character accuracy: 0.6369723104857014\n"
     ]
    }
   ],
   "source": [
    "print(f'- The word by word accuracy          : {word_accuracy(words_prediction, words_test)}')\n",
    "print(f'- The character by character accuracy: {character_accuracy(words_prediction, words_test)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "199c2297-e8fb-4063-a083-90e204eaf0b4",
   "metadata": {},
   "source": [
    "### ■ **<a name=\"section5\">5. Forth Approach: Clustering</a>** [(&#8593;)](#content)\n",
    "\n",
    "#### **5.1. Modeling of the data**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "d916ec90-49dd-4188-94fb-7d69365c7abe",
   "metadata": {},
   "outputs": [
    {
     "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>lemma</th>\n",
       "      <th>form</th>\n",
       "      <th>attributes</th>\n",
       "      <th>prefix</th>\n",
       "      <th>suffix</th>\n",
       "      <th>root</th>\n",
       "      <th>lemma_prefix</th>\n",
       "      <th>form_prefix</th>\n",
       "      <th>lemma_suffix</th>\n",
       "      <th>form_suffix</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>piga</td>\n",
       "      <td>amepiga</td>\n",
       "      <td>V;PRF;FIN;IND;SG;3;PST</td>\n",
       "      <td>ame</td>\n",
       "      <td></td>\n",
       "      <td>piga</td>\n",
       "      <td></td>\n",
       "      <td>ame</td>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>kamilisha</td>\n",
       "      <td>wangekamilisha</td>\n",
       "      <td>V;FIN;COND;PL;3;PRS</td>\n",
       "      <td>wange</td>\n",
       "      <td></td>\n",
       "      <td>kamilisha</td>\n",
       "      <td></td>\n",
       "      <td>wange</td>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>fuata</td>\n",
       "      <td>walifuata</td>\n",
       "      <td>V;FIN;IND;PL;3;PST</td>\n",
       "      <td>wali</td>\n",
       "      <td></td>\n",
       "      <td>fuata</td>\n",
       "      <td></td>\n",
       "      <td>wali</td>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>tengeneza</td>\n",
       "      <td>nitatengeneza</td>\n",
       "      <td>V;FIN;IND;SG;1;FUT</td>\n",
       "      <td>nita</td>\n",
       "      <td></td>\n",
       "      <td>tengeneza</td>\n",
       "      <td></td>\n",
       "      <td>nita</td>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>uwa</td>\n",
       "      <td>anauwa</td>\n",
       "      <td>V;DEF;FIN;IND;SG;3;PRS</td>\n",
       "      <td>ana</td>\n",
       "      <td></td>\n",
       "      <td>uwa</td>\n",
       "      <td></td>\n",
       "      <td>ana</td>\n",
       "      <td></td>\n",
       "      <td></td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "       lemma            form              attributes prefix suffix       root  \\\n",
       "0       piga         amepiga  V;PRF;FIN;IND;SG;3;PST    ame              piga   \n",
       "1  kamilisha  wangekamilisha     V;FIN;COND;PL;3;PRS  wange         kamilisha   \n",
       "2      fuata       walifuata      V;FIN;IND;PL;3;PST   wali             fuata   \n",
       "3  tengeneza   nitatengeneza      V;FIN;IND;SG;1;FUT   nita         tengeneza   \n",
       "4        uwa          anauwa  V;DEF;FIN;IND;SG;3;PRS    ana               uwa   \n",
       "\n",
       "  lemma_prefix form_prefix lemma_suffix form_suffix  \n",
       "0                      ame                           \n",
       "1                    wange                           \n",
       "2                     wali                           \n",
       "3                     nita                           \n",
       "4                      ana                           "
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df_train.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "3ff3e154-af6f-44fd-8e33-09e4e37a4012",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[array(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',\n",
       "        'n', 'o', 'p', 'r', 's', 't', 'u', 'v', 'w', 'y', 'z'], dtype='<U1')]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def encode_root(root, max_root_length, chars_order):\n",
    "    \"\"\"\"\"\"\n",
    "    encoded_root = np.zeros(max_root_length)\n",
    "    \n",
    "    for e, char in enumerate(root, start=1):\n",
    "        \n",
    "        order = chars_order[char]\n",
    "        encoded_root[order] = e\n",
    "        \n",
    "    return encoded_root    \n",
    "\n",
    "def encode_word(word, max_word_length, n_chars):\n",
    "    \"\"\"\"\"\"\n",
    "    encoded_word = np.zeros((max_word_length, n_chars))\n",
    "    for e, char in enumerate(word):\n",
    "        encoded_word[e, :] = encoder.transform([[char]]).toarray()\n",
    "        \n",
    "    return encoded_word\n",
    "\n",
    "\n",
    "## create & fit a onehot encoder \n",
    "encoder = OneHotEncoder()\n",
    "encoder.fit(np.array(unique_chars).reshape(-1, 1))\n",
    "encoder.categories_"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33437b7e-2832-4f2d-a2c1-b1b6d19477cf",
   "metadata": {},
   "source": [
    "### ■ **<a name=\"section6\">6. Fifth Approach: N-Grams</a>** [(&#8593;)](#content)\n",
    "\n",
    "#### **6.1. Modeling of the data**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "f55a2ba2-1c8e-48b4-a2e1-a5cdd71488b6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "min_lemma_len = df_train['lemma'].apply(len).min()\n",
    "min_lemma_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "3affe784-2996-4912-8650-e3854506583e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ngrams(word, n):\n",
    "    \n",
    "    if n > len(word):\n",
    "        raise Exception('n should be less than the length of the word WTF !')\n",
    "    word = list(word)\n",
    "    output = []\n",
    "    for i in range(len(word)-n+1):\n",
    "        output.append(word[i:i+n])\n",
    "    return output\n",
    "\n",
    "def encoded_ngrams(word, n, char_dict):\n",
    "    if n > len(word):\n",
    "        raise Exception('n should be less than the length of the word WTF !')\n",
    "    word = list(word)\n",
    "    output = []\n",
    "    for i in range(len(word)-n+1):\n",
    "        ngram = word[i:i+n]\n",
    "        encoded = [char_dict[char] for char in ngram]\n",
    "        output.append(encoded)\n",
    "            \n",
    "    return output\n",
    "\n",
    "\n",
    "def create_data(array):\n",
    "    output = []\n",
    "    \n",
    "    min_chars = min([len(word) for word in array])\n",
    "    \n",
    "    for n in range(1, min_chars+1):\n",
    "        encoded = []\n",
    "        for word in array:\n",
    "            encoded.append(pad(encoded_ngrams(word, n, char_dict),  max_lemma_length, 0))\n",
    "        output.append(encoded)\n",
    "    print(np.array(output[2]).shape)\n",
    "    output = np.concatenate(output, axis=1)\n",
    "        \n",
    "    return output"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fcbbdb0d-9230-478a-8241-ac31a66c08a5",
   "metadata": {},
   "source": [
    "**Neural Network**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "8b203dbf-f2e4-41cc-a0bc-75145b5115d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import keras\n",
    "from keras.models import Sequential\n",
    "from keras.layers import Dense, LSTM, Dropout, Activation\n",
    "from tensorflow.keras.optimizers import RMSprop, Adam\n",
    "from keras.callbacks import ModelCheckpoint\n",
    "from keras.utils import np_utils"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "2556dc5e-fef9-46a6-b92c-eea422fe4683",
   "metadata": {},
   "outputs": [],
   "source": [
    "def buildmodel(VOCABULARY):\n",
    "    model = Sequential()\n",
    "    model.add(LSTM(256, input_shape = (max_lemma_length, 1), return_sequences = True))\n",
    "    model.add(Dropout(0.2))\n",
    "    model.add(LSTM(256))\n",
    "    model.add(Dropout(0.2))\n",
    "    model.add(Dense(VOCABULARY, activation = 'softmax'))\n",
    "    model.compile(loss = 'categorical_crossentropy', optimizer = 'adam')\n",
    "    return model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "841bef77-67f8-4b2b-8829-74e81464dfb1",
   "metadata": {},
   "outputs": [],
   "source": [
    "char_to_int = dict((c, i) for i, c in enumerate(unique_chars))\n",
    "input_strings = []\n",
    "output_strings = []\n",
    "\n",
    "for i in range(df_train.shape[0]):\n",
    "    X_text = df_train.loc[i, 'lemma']\n",
    "    X = [char_to_int[char] for char in X_text]\n",
    "    input_strings.append(X)    \n",
    "    Y = [char_to_int[char] for char in df_train.loc[i, 'form']]\n",
    "    output_strings.append(Y)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc61fca1-1148-4455-8837-fd0d5a8763b5",
   "metadata": {},
   "source": [
    "### **References** \n",
    "@article{vylomova2020sigmorphon, title={SIGMORPHON 2020 Shared Task 0: Typologically Diverse Morphological Inflection}, author={Vylomova, Ekaterina and White, Jennifer and Salesky, Elizabeth and Mielke, Sabrina J and Wu, Shijie and Ponti, Edoardo and Maudslay, Rowan Hall and Zmigrod, Ran and Valvoda, Josef and Toldova, Svetlana and others}, journal={SIGMORPHON 2020}, pages={1}, year={2020} }"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e60003da-2427-461a-96de-870555fa362e",
   "metadata": {},
   "source": [
    "---\n",
    "<p style=\"text-align: center;\">Copyright © 2021 Omar Ikne & Zakaria Boulkhir</p>"
   ]
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}