chapter_9.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "38e6802f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import nltk\n",
    "from nltk.corpus import *\n",
    "import re\n",
    "from collections import defaultdict, Counter "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "192f1990",
   "metadata": {},
   "source": [
    "__☼ Write a function subsumes() which holds of two feature structures fs1 and fs2 just in case fs1 subsumes fs2.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "050f158e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def subsumes(fs1, fs2):\n",
    "    \"\"\"\n",
    "    Returns: True if fs1 subsumes fs2\n",
    "             False otherwise\n",
    "    \"\"\"\n",
    "    \n",
    "    def add_dict(fs):\n",
    "        dict_fs = defaultdict()\n",
    "        for k, v in fs.items():\n",
    "            if v == nltk.featstruct.FeatDict:\n",
    "                add_dict(v)\n",
    "            elif v == str:\n",
    "                dict_fs[k] == v\n",
    "        return dict_fs\n",
    "                    \n",
    "    fs1_dict = add_dict(fs1)  \n",
    "    fs2_dict = add_dict(fs2)\n",
    "    \n",
    "    if fs1.unify(fs2) == fs2 and (all(elem in list(fs1_dict.keys()) for elem in list(fs2_dict.keys()))):     \n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "fdc20205",
   "metadata": {},
   "outputs": [],
   "source": [
    "fs_1 = nltk.FeatStruct(\"[NUMBER = 74]\")\n",
    "\n",
    "fs_2 = nltk.FeatStruct(NUMBER = 74, STREET = \"rue Pascal\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "cf2129a0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "subsumes(fs_2, fs_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "cae38781",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "subsumes(fs_1, fs_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "df548bfe",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "# sanity check with nltk's function subsumes\n",
    "print(nltk.featstruct.subsumes(fs_1, fs_2))\n",
    "print(nltk.featstruct.subsumes(fs_2, fs_1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e8c9644",
   "metadata": {},
   "source": [
    "__◑ Develop a feature based grammar that will correctly describe the following Spanish noun phrases:__\n",
    "\n",
    "    un cuadro hermos-o\n",
    "    un-os cuadro-s hermos-os\n",
    "    un-a cortina hermos-a\n",
    "    un-as cortina-s hermos-as"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "3dbe3636",
   "metadata": {},
   "outputs": [],
   "source": [
    "fcfg_spanish = nltk.grammar.FeatureGrammar.fromstring(\"\"\"\n",
    "    % start NP\n",
    "    NP[AGR=?a] -> DET[AGR=?a] N[AGR=?a] Adj[AGR=?a]\n",
    "    DET[AGR=[NUM=sg, GEN=f]] -> \"una\" | \"Una\"\n",
    "    DET[AGR=[NUM=sg, GEN=m]] -> \"un\" | \"Un\"\n",
    "    DET[AGR=[NUM=pl, GEN=f]] -> \"unas\" | \"Unas\"\n",
    "    DET[AGR=[NUM=pl, GEN=m]] -> \"unos\" | \"Unos\"\n",
    "    N[AGR=[NUM=sg, GEN=f]] -> \"casa\" | \"cortina\"\n",
    "    N[AGR=[NUM=sg, GEN=m]] -> \"cuadro\" | \"chico\"\n",
    "    N[AGR=[NUM=pl, GEN=f]] -> \"casas\" | \"cortinas\"\n",
    "    N[AGR=[NUM=pl, GEN=m]] -> \"cuadros\" | \"chicos\"    \n",
    "    Adj[AGR=[NUM=pl, GEN=f]] -> \"hermosas\" | \"bonitas\" | \"pequenas\"\n",
    "    Adj[AGR=[NUM=sg, GEN=m]] -> \"hermoso\" | \"bonito\" | \"pequeno\"\n",
    "    Adj[AGR=[NUM=sg, GEN=f]] -> \"hermosa\" | \"bonita\" | \"pequena\"\n",
    "    Adj[AGR=[NUM=pl, GEN=m]] -> \"hermosos\" | \"bonitos\" | \"pequenos\"\n",
    "    \"\"\")\n",
    "    \n",
    "parser = nltk.parse.FeatureEarleyChartParser(fcfg_spanish)\n",
    "sent = \"Unos cuadros hermosos\"\n",
    "sent2 = \"Un chico pequeno\"\n",
    "sent3 = \"Una chico bonita\"  # incorrect agreement, will not be parsed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "c968df82",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(NP[AGR=[GEN='m', NUM='pl']]\n",
      "  (DET[AGR=[GEN='m', NUM='pl']] Unos)\n",
      "  (N[AGR=[GEN='m', NUM='pl']] cuadros)\n",
      "  (Adj[AGR=[GEN='m', NUM='pl']] hermosos))\n",
      "\n",
      "(NP[AGR=[GEN='m', NUM='sg']]\n",
      "  (DET[AGR=[GEN='m', NUM='sg']] Un)\n",
      "  (N[AGR=[GEN='m', NUM='sg']] chico)\n",
      "  (Adj[AGR=[GEN='m', NUM='sg']] pequeno))\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for s in [sent, sent2, sent3]:\n",
    "    for parse in parser.parse(s.split()):\n",
    "        print(parse, end = \"\\n\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98fffb6a",
   "metadata": {},
   "source": [
    "__◑ Develop your own version of the EarleyChartParser which only prints a trace if the input sequence fails to parse.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "78ecee35",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "037b5bef",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "bfca4305",
   "metadata": {},
   "source": [
    "__◑ Consider the feature structures shown in 6.1.__\n",
    "\n",
    "Work out on paper what the result is of the following unifications. (Hint: you might find it useful to draw the graph structures.)\n",
    "\n",
    "    fs1 and fs2\n",
    "    fs1 and fs3\n",
    "    fs4 and fs5\n",
    "    fs5 and fs6\n",
    "    fs5 and fs7\n",
    "    fs8 and fs9\n",
    "    fs8 and fs10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "fd27e37f",
   "metadata": {},
   "outputs": [],
   "source": [
    "fs1 = nltk.FeatStruct(\"[A = ?x, B= [C = ?x]]\")\n",
    "fs2 = nltk.FeatStruct(\"[B = [D = d]]\")\n",
    "fs3 = nltk.FeatStruct(\"[B = [C = d]]\")\n",
    "fs4 = nltk.FeatStruct(\"[A = (1)[B = b], C->(1)]\")\n",
    "fs5 = nltk.FeatStruct(\"[A = (1)[D = ?x], C = [E -> (1), F = ?x] ]\")\n",
    "fs6 = nltk.FeatStruct(\"[A = [D = d]]\")\n",
    "fs7 = nltk.FeatStruct(\"[A = [D = d], C = [F = [D = d]]]\")\n",
    "fs8 = nltk.FeatStruct(\"[A = (1)[D = ?x, G = ?x], C = [B = ?x, E -> (1)] ]\")\n",
    "fs9 = nltk.FeatStruct(\"[A = [B = b], C = [E = [G = e]]]\")\n",
    "fs10 = nltk.FeatStruct(\"[A = (1)[B = b], C -> (1)]\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "50c9c203",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "FS1 and FS2\n",
      "[ A = ?x          ]\n",
      "[                 ]\n",
      "[ B = [ C = ?x  ] ]\n",
      "[     [ D = 'd' ] ]\n",
      "\n",
      "\n",
      "FS1 and FS3\n",
      "[ A = 'd'         ]\n",
      "[                 ]\n",
      "[ B = [ C = 'd' ] ]\n",
      "\n",
      "\n",
      "FS4 and FS5\n",
      "[         [ B = 'b'  ] ]\n",
      "[ A = (1) [ D = ?x   ] ]\n",
      "[         [ E -> (1) ] ]\n",
      "[         [ F = ?x   ] ]\n",
      "[                      ]\n",
      "[ C -> (1)             ]\n",
      "\n",
      "\n",
      "FS5 and FS6\n",
      "[ A = (1) [ D = 'd' ] ]\n",
      "[                     ]\n",
      "[ C = [ E -> (1) ]    ]\n",
      "[     [ F = 'd'  ]    ]\n",
      "\n",
      "\n",
      "FS5 and FS7\n",
      "None\n",
      "\n",
      "\n",
      "FS8 and FS9\n",
      "[         [ B = 'b' ] ]\n",
      "[ A = (1) [ D = 'e' ] ]\n",
      "[         [ G = 'e' ] ]\n",
      "[                     ]\n",
      "[ C = [ B = 'e'  ]    ]\n",
      "[     [ E -> (1) ]    ]\n",
      "\n",
      "\n",
      "FS8 and FS10\n",
      "[         [ B = 'b'  ] ]\n",
      "[ A = (1) [ D = 'b'  ] ]\n",
      "[         [ E -> (1) ] ]\n",
      "[         [ G = 'b'  ] ]\n",
      "[                      ]\n",
      "[ C -> (1)             ]\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(\"FS1 and FS2\\n{}\\n\\n\".format(fs1.unify(fs2)))\n",
    "print(\"FS1 and FS3\\n{}\\n\\n\".format(fs1.unify(fs3)))\n",
    "print(\"FS4 and FS5\\n{}\\n\\n\".format(fs4.unify(fs5)))\n",
    "print(\"FS5 and FS6\\n{}\\n\\n\".format(fs5.unify(fs6)))\n",
    "print(\"FS5 and FS7\\n{}\\n\\n\".format(fs5.unify(fs7)))\n",
    "print(\"FS8 and FS9\\n{}\\n\\n\".format(fs8.unify(fs9)))\n",
    "print(\"FS8 and FS10\\n{}\\n\\n\".format(fs8.unify(fs10)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80fee9b1",
   "metadata": {},
   "source": [
    "__◑ List two feature structures that subsume [A=?x, B=?x].__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "f858b8f8",
   "metadata": {},
   "outputs": [],
   "source": [
    "f1 = nltk.FeatStruct(\"[A=?x, B=?x]\")\n",
    "f0 = nltk.FeatStruct(\"[A = Linguistics]\")\n",
    "f0_2 = nltk.FeatStruct(\"[B = Physics]\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d51edcf5",
   "metadata": {},
   "source": [
    "__◑ Ignoring structure sharing, give an informal algorithm for unifying two feature structures.__"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f060b2d9",
   "metadata": {},
   "source": [
    "The source code to unify is here https://www.nltk.org/_modules/nltk/featstruct.html#subsumes . I guess that is what they are easking to do..."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6fe7a446",
   "metadata": {},
   "source": [
    "__◑ Seemingly synonymous verbs have slightly different syntactic properties (Levin, 1993). Consider the patterns of grammaticality for the verbs loaded, filled, and dumped below. Can you write grammar productions to handle such data?__\n",
    "\t\t\t\n",
    "    The farmer loaded the cart with sand\t\t\n",
    "    The farmer loaded sand into the cart\t\t\n",
    "    The farmer filled the cart with sand.\n",
    "    The farmer dumped sand into the cart\n",
    "    \n",
    "    *The farmer filled sand into the cart\t\n",
    "    *The farmer dumped the cart with sand\t\t\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "fe9c9b7e",
   "metadata": {},
   "outputs": [],
   "source": [
    "fcfg_verbs = nltk.grammar.FeatureGrammar.fromstring(\"\"\"\n",
    "    % start S\n",
    "    S -> NP VP\n",
    "    NP -> DET N | N\n",
    "    VP -> V[ID = ?i] NP PP[ID = ?i]\n",
    "    PP[ID = ?i] -> P[ID = ?i] NP\n",
    "    V[ID = t1] -> \"filled\"\n",
    "    V[ID = t2] -> \"dumped\"\n",
    "    V -> \"loaded\"\n",
    "    DET -> \"the\"\n",
    "    N -> \"farmer\" | \"cart\" | \"sand\"\n",
    "    P[ID = t2] -> \"into\"\n",
    "    P[ID = t1] -> \"with\"\n",
    "   \n",
    "    \"\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "68cccbf9",
   "metadata": {},
   "outputs": [],
   "source": [
    "parser_vb = nltk.parse.FeatureEarleyChartParser(fcfg_verbs)\n",
    "sent_1 = \"the farmer filled sand into the cart\" # ungrammatical\n",
    "sent_2 = \"the farmer dumped the cart with sand\" # ungrammatical\n",
    "sent_3 = \"the farmer filled the cart with sand\"\n",
    "sent_4 = \"the farmer loaded sand into the cart\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "58ca32d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "for p in parser_vb.parse(sent_1.split()):  # no parses available\n",
    "    print(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "35f755f3",
   "metadata": {},
   "outputs": [],
   "source": [
    "for p in parser_vb.parse(sent_2.split()):  # no parses available\n",
    "    print(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "086b4a2a",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(S[]\n",
      "  (NP[] (DET[] the) (N[] farmer))\n",
      "  (VP[]\n",
      "    (V[ID='t1'] filled)\n",
      "    (NP[] (DET[] the) (N[] cart))\n",
      "    (PP[ID='t1'] (P[ID='t1'] with) (NP[] (N[] sand)))))\n"
     ]
    }
   ],
   "source": [
    "for p in parser_vb.parse(sent_3.split()):\n",
    "    print(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "bd1561c3",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(S[]\n",
      "  (NP[] (DET[] the) (N[] farmer))\n",
      "  (VP[]\n",
      "    (V[] loaded)\n",
      "    (NP[] (N[] sand))\n",
      "    (PP[ID='t2'] (P[ID='t2'] into) (NP[] (DET[] the) (N[] cart)))))\n"
     ]
    }
   ],
   "source": [
    "for p in parser_vb.parse(sent_4.split()):  # no parses available\n",
    "    print(p)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75364bf0",
   "metadata": {},
   "source": [
    "__★ Morphological paradigms are rarely completely regular, in the sense of every cell in the matrix having a different realization. For example, the present tense conjugation of the lexeme walk only has two distinct forms: walks for the 3rd person singular, and walk for all other combinations of person and number. A successful analysis should not require redundantly specifying that 5 out of the 6 possible morphological combinations have the same realization. Propose and implement a method for dealing with this.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f3edbaab",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e97b4da",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "0f7e364b",
   "metadata": {},
   "source": [
    "__★ So-called head features are shared between the parent node and head child. For example, TENSE is a head feature that is shared between a VP and its head V child. See (Gazdar, Klein, & and, 1985) for more details. Most of the features we have looked at are head features — exceptions are SUBCAT and SLASH. Since the sharing of head features is predictable, it should not need to be stated explicitly in the grammar productions. Develop an approach that automatically accounts for this regular behavior of head features.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "72686198",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58fe2349",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8e188d28",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}