asr_lab3_solutions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lab 3 solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import observation_model\n",
    "import math\n",
    "import openfst_python as fst\n",
    "\n",
    "class MyViterbiDecoder:\n",
    "    \n",
    "    NLL_ZERO = 1e10  # define a constant representing -log(0).  This is really infinite, but approximate\n",
    "                     # it here with a very large number\n",
    "    \n",
    "    def __init__(self, f, audio_file_name):\n",
    "        \"\"\"Set up the decoder class with an audio file and WFST f\n",
    "        \"\"\"\n",
    "        self.om = observation_model.ObservationModel()\n",
    "        self.f = f\n",
    "        \n",
    "        if audio_file_name:\n",
    "            self.om.load_audio(audio_file_name)\n",
    "        else:\n",
    "            self.om.load_dummy_audio()\n",
    "        \n",
    "        self.initialise_decoding()\n",
    "\n",
    "        \n",
    "    def initialise_decoding(self):\n",
    "        \"\"\"set up the values for V_j(0) (as negative log-likelihoods)\n",
    "        \n",
    "        \"\"\"\n",
    "        \n",
    "        self.V = []   # stores likelihood along best path reaching state j\n",
    "        self.B = []   # stores identity of best previous state reaching state j\n",
    "        self.W = []   # stores output labels sequence along arc reaching j - this removes need for \n",
    "                      # extra code to read the output sequence along the best path\n",
    "        \n",
    "        for t in range(self.om.observation_length()+1):\n",
    "            self.V.append([self.NLL_ZERO]*self.f.num_states())\n",
    "            self.B.append([-1]*self.f.num_states())\n",
    "            self.W.append([[] for i in range(self.f.num_states())])  #  multiplying the empty list doesn't make multiple\n",
    "        \n",
    "        # The above code means that self.V[t][j] for t = 0, ... T gives the Viterbi cost\n",
    "        # of state j, time t (in negative log-likelihood form)\n",
    "        # Initialising the costs to NLL_ZERO effectively means zero probability    \n",
    "        \n",
    "        # give the WFST start state a probability of 1.0   (NLL = 0.0)\n",
    "        self.V[0][self.f.start()] = 0.0\n",
    "        \n",
    "        # some WFSTs might have arcs with epsilon on the input (you might have already created \n",
    "        # examples of these in earlier labs) these correspond to non-emitting states, \n",
    "        # which means that we need to process them without stepping forward in time.  \n",
    "        # Don't worry too much about this!  \n",
    "        self.traverse_epsilon_arcs(0)        \n",
    "        \n",
    "    def traverse_epsilon_arcs(self, t):\n",
    "        \"\"\"Traverse arcs with <eps> on the input at time t\n",
    "        \n",
    "        These correspond to transitions that don't emit an observation\n",
    "        \n",
    "        We've implemented this function for you as it's slightly trickier than\n",
    "        the normal case.  You might like to look at it to see what's going on, but\n",
    "        don't worry if you can't fully follow it.\n",
    "        \n",
    "        \"\"\"\n",
    "        \n",
    "        states_to_traverse = list(self.f.states()) # traverse all states\n",
    "        while states_to_traverse:\n",
    "            \n",
    "            # Set i to the ID of the current state, the first \n",
    "            # item in the list (and remove it from the list)\n",
    "            i = states_to_traverse.pop(0)   \n",
    "        \n",
    "            # don't bother traversing states which have zero probability\n",
    "            if self.V[t][i] == self.NLL_ZERO:\n",
    "                    continue\n",
    "        \n",
    "            for arc in self.f.arcs(i):\n",
    "                \n",
    "                if arc.ilabel == 0:     # if <eps> transition\n",
    "                  \n",
    "                    j = arc.nextstate   # ID of next state  \n",
    "                \n",
    "                    if self.V[t][j] > self.V[t][i] + float(arc.weight):\n",
    "                        \n",
    "                        # this means we've found a lower-cost path to\n",
    "                        # state j at time t.  We might need to add it\n",
    "                        # back to the processing queue.\n",
    "                        self.V[t][j] = self.V[t][i] + float(arc.weight)\n",
    "                        \n",
    "                        # save backtrace information.  In the case of an epsilon transition, \n",
    "                        # we save the identity of the best state at t-1.  This means we may not\n",
    "                        # be able to fully recover the best path, but to do otherwise would\n",
    "                        # require a more complicated way of storing backtrace information\n",
    "                        self.B[t][j] = self.B[t][i] \n",
    "                        \n",
    "                        # and save the output labels encountered - this is a list, because\n",
    "                        # there could be multiple output labels (in the case of <eps> arcs)\n",
    "                        if arc.olabel != 0:\n",
    "                            self.W[t][j] = self.W[t][i] + [arc.olabel]\n",
    "                        else:\n",
    "                            self.W[t][j] = self.W[t][i]\n",
    "                        \n",
    "                        if j not in states_to_traverse:\n",
    "                            states_to_traverse.append(j)\n",
    "\n",
    "    \n",
    "    def forward_step(self, t):\n",
    "          \n",
    "        for i in self.f.states():\n",
    "            \n",
    "            if not self.V[t-1][i] == self.NLL_ZERO:   # no point in propagating states with zero probability\n",
    "                \n",
    "                for arc in self.f.arcs(i):\n",
    "                    \n",
    "                    if arc.ilabel != 0: # <eps> transitions don't emit an observation\n",
    "                        j = arc.nextstate\n",
    "                        tp = float(arc.weight)  # transition prob\n",
    "                        ep = -self.om.log_observation_probability(self.f.input_symbols().find(arc.ilabel), t)  # emission negative log prob\n",
    "                        prob = tp + ep + self.V[t-1][i] # they're logs\n",
    "                        if prob < self.V[t][j]:\n",
    "                            self.V[t][j] = prob\n",
    "                            self.B[t][j] = i\n",
    "                            \n",
    "                            # store the output labels encountered too\n",
    "                            if arc.olabel !=0:\n",
    "                                self.W[t][j] = [arc.olabel]\n",
    "                            else:\n",
    "                                self.W[t][j] = []\n",
    "                            \n",
    "    \n",
    "    def finalise_decoding(self):\n",
    "        \"\"\" this incorporates the probability of terminating at each state\n",
    "        \"\"\"\n",
    "        \n",
    "        for state in self.f.states():\n",
    "            final_weight = float(self.f.final(state))\n",
    "            if self.V[-1][state] != self.NLL_ZERO:\n",
    "                if final_weight == math.inf:\n",
    "                    self.V[-1][state] = self.NLL_ZERO  # effectively says that we can't end in this state\n",
    "                else:\n",
    "                    self.V[-1][state] += final_weight\n",
    "                    \n",
    "        # get a list of all states where there was a path ending with non-zero probability\n",
    "        finished = [x for x in self.V[-1] if x < self.NLL_ZERO]\n",
    "        if not finished:  # if empty\n",
    "            print(\"No path got to the end of the observations.\")\n",
    "        \n",
    "        \n",
    "    def decode(self):\n",
    "        self.initialise_decoding()\n",
    "        t = 1\n",
    "        while t <= self.om.observation_length():\n",
    "            self.forward_step(t)\n",
    "            self.traverse_epsilon_arcs(t)\n",
    "            t += 1\n",
    "        self.finalise_decoding()\n",
    "    \n",
    "    def backtrace(self):\n",
    "        \n",
    "        # TODO - exercise \n",
    "        \n",
    "        # complete code to trace back through the\n",
    "        # best state sequence\n",
    "        \n",
    "        # You'll need to create a structure B_j(t) to store the \n",
    "        # back-pointers (see lectures), and amend the functions above to fill it.\n",
    "        best_state_sequence = []\n",
    "        return best_state_sequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.30.1 (20200930.0103)\n",
       " -->\n",
       "<!-- Title: FST Pages: 1 -->\n",
       "<svg width=\"612pt\" height=\"19pt\"\n",
       " viewBox=\"0.00 0.00 612.00 19.45\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.234303 0.234303) rotate(0) translate(4 79)\">\n",
       "<title>FST</title>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"-4,5 -4,-79 2609,-79 2609,5 -4,5\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\"><title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" stroke-width=\"2\" cx=\"50\" cy=\"-23\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"50\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;0 -->\n",
       "<g id=\"edge1\" class=\"edge\"><title>0&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M36.7449,-35.5448C30.2965,-46.8696 34.7148,-59 50,-59 60.8668,-59 66.2412,-52.8689 66.1231,-45.255\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"69.4444,-44.1438 63.2551,-35.5448 62.7311,-46.1267 69.4444,-44.1438\"/>\n",
       "<text text-anchor=\"middle\" x=\"50\" y=\"-62.8\" font-family=\"Times,serif\" font-size=\"14.00\">p_1:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\"><title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"224\" cy=\"-23\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"224\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge2\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M68.1208,-23C97.9989,-23 159.887,-23 195.726,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"195.948,-26.5001 205.948,-23 195.948,-19.5001 195.948,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"137\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">p_1:&lt;eps&gt;/0.10536</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;1 -->\n",
       "<g id=\"edge3\" class=\"edge\"><title>1&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M210.745,-35.5448C204.296,-46.8696 208.715,-59 224,-59 234.867,-59 240.241,-52.8689 240.123,-45.255\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"243.444,-44.1438 237.255,-35.5448 236.731,-46.1267 243.444,-44.1438\"/>\n",
       "<text text-anchor=\"middle\" x=\"224\" y=\"-62.8\" font-family=\"Times,serif\" font-size=\"14.00\">p_2:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\"><title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"398\" cy=\"-23\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"398\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge4\" class=\"edge\"><title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M242.121,-23C271.999,-23 333.887,-23 369.726,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"369.948,-26.5001 379.948,-23 369.948,-19.5001 369.948,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"311\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">p_2:&lt;eps&gt;/0.10536</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;2 -->\n",
       "<g id=\"edge5\" class=\"edge\"><title>2&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M386.244,-37.0417C381.847,-47.9126 385.766,-59 398,-59 406.411,-59 410.892,-53.7595 411.442,-46.9516\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"414.884,-46.3132 409.756,-37.0417 407.983,-47.4871 414.884,-46.3132\"/>\n",
       "<text text-anchor=\"middle\" x=\"398\" y=\"-62.8\" font-family=\"Times,serif\" font-size=\"14.00\">p_3:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node4\" class=\"node\"><title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"544\" cy=\"-23\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"544\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge6\" class=\"edge\"><title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M416.084,-23C440.659,-23 486.247,-23 515.573,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"515.938,-26.5001 525.938,-23 515.938,-19.5001 515.938,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"471\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">p_3:p/0.10536</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;3 -->\n",
       "<g id=\"edge7\" class=\"edge\"><title>3&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M532.244,-37.0417C527.847,-47.9126 531.766,-59 544,-59 552.411,-59 556.892,-53.7595 557.442,-46.9516\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"560.884,-46.3132 555.756,-37.0417 553.983,-47.4871 560.884,-46.3132\"/>\n",
       "<text text-anchor=\"middle\" x=\"544\" y=\"-62.8\" font-family=\"Times,serif\" font-size=\"14.00\">eh_1:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\"><title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"724\" cy=\"-23\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"724\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge8\" class=\"edge\"><title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M562.067,-23C593.034,-23 658.701,-23 695.871,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"695.984,-26.5001 705.984,-23 695.984,-19.5001 695.984,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"634\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">eh_1:&lt;eps&gt;/0.10536</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;4 -->\n",
       "<g id=\"edge9\" class=\"edge\"><title>4&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M710.355,-35.1718C703.28,-46.6016 707.828,-59 724,-59 735.624,-59 741.242,-52.5949 740.856,-44.7481\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"744.143,-43.54 737.645,-35.1718 737.506,-45.7657 744.143,-43.54\"/>\n",
       "<text text-anchor=\"middle\" x=\"724\" y=\"-62.8\" font-family=\"Times,serif\" font-size=\"14.00\">eh_2:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\"><title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"904\" cy=\"-23\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"904\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge10\" class=\"edge\"><title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M742.067,-23C773.034,-23 838.701,-23 875.871,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"875.984,-26.5001 885.984,-23 875.984,-19.5001 875.984,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"814\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">eh_2:&lt;eps&gt;/0.10536</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;5 -->\n",
       "<g id=\"edge11\" class=\"edge\"><title>5&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M891.607,-36.2925C886.31,-47.397 890.441,-59 904,-59 913.322,-59 918.187,-53.5158 918.597,-46.4797\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"921.928,-45.3266 916.393,-36.2925 915.087,-46.8064 921.928,-45.3266\"/>\n",
       "<text text-anchor=\"middle\" x=\"904\" y=\"-62.8\" font-family=\"Times,serif\" font-size=\"14.00\">eh_3:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\"><title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1062\" cy=\"-23\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"1062\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge12\" class=\"edge\"><title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M922.291,-23C949.232,-23 1001.46,-23 1033.58,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1033.63,-26.5001 1043.63,-23 1033.63,-19.5001 1033.63,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"983\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">eh_3:eh/0.10536</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;6 -->\n",
       "<g id=\"edge13\" class=\"edge\"><title>6&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1049.61,-36.2925C1044.31,-47.397 1048.44,-59 1062,-59 1071.32,-59 1076.19,-53.5158 1076.6,-46.4797\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1079.93,-45.3266 1074.39,-36.2925 1073.09,-46.8064 1079.93,-45.3266\"/>\n",
       "<text text-anchor=\"middle\" x=\"1062\" y=\"-62.8\" font-family=\"Times,serif\" font-size=\"14.00\">p_1:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\"><title>7</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1236\" cy=\"-23\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"1236\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">7</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;7 -->\n",
       "<g id=\"edge14\" class=\"edge\"><title>6&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1080.12,-23C1110,-23 1171.89,-23 1207.73,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1207.95,-26.5001 1217.95,-23 1207.95,-19.5001 1207.95,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"1149\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">p_1:&lt;eps&gt;/0.10536</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;7 -->\n",
       "<g id=\"edge15\" class=\"edge\"><title>7&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1222.74,-35.5448C1216.3,-46.8696 1220.71,-59 1236,-59 1246.87,-59 1252.24,-52.8689 1252.12,-45.255\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1255.44,-44.1438 1249.26,-35.5448 1248.73,-46.1267 1255.44,-44.1438\"/>\n",
       "<text text-anchor=\"middle\" x=\"1236\" y=\"-62.8\" font-family=\"Times,serif\" font-size=\"14.00\">p_2:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\"><title>8</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1410\" cy=\"-23\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"1410\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">8</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge16\" class=\"edge\"><title>7&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1254.12,-23C1284,-23 1345.89,-23 1381.73,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1381.95,-26.5001 1391.95,-23 1381.95,-19.5001 1381.95,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"1323\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">p_2:&lt;eps&gt;/0.10536</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;8 -->\n",
       "<g id=\"edge17\" class=\"edge\"><title>8&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1398.24,-37.0417C1393.85,-47.9126 1397.77,-59 1410,-59 1418.41,-59 1422.89,-53.7595 1423.44,-46.9516\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1426.88,-46.3132 1421.76,-37.0417 1419.98,-47.4871 1426.88,-46.3132\"/>\n",
       "<text text-anchor=\"middle\" x=\"1410\" y=\"-62.8\" font-family=\"Times,serif\" font-size=\"14.00\">p_3:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\"><title>9</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1556\" cy=\"-23\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"1556\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">9</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge18\" class=\"edge\"><title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1428.08,-23C1452.66,-23 1498.25,-23 1527.57,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1527.94,-26.5001 1537.94,-23 1527.94,-19.5001 1527.94,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"1483\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">p_3:p/0.10536</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;9 -->\n",
       "<g id=\"edge19\" class=\"edge\"><title>9&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1544.24,-37.0417C1539.85,-47.9126 1543.77,-59 1556,-59 1564.41,-59 1568.89,-53.7595 1569.44,-46.9516\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1572.88,-46.3132 1567.76,-37.0417 1565.98,-47.4871 1572.88,-46.3132\"/>\n",
       "<text text-anchor=\"middle\" x=\"1556\" y=\"-62.8\" font-family=\"Times,serif\" font-size=\"14.00\">er_1:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\"><title>10</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1736\" cy=\"-23\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"1736\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">10</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;10 -->\n",
       "<g id=\"edge20\" class=\"edge\"><title>9&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1574.07,-23C1604.56,-23 1668.69,-23 1706.14,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1706.39,-26.5001 1716.39,-23 1706.39,-19.5001 1706.39,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"1645\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">er_1:&lt;eps&gt;/0.10536</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;10 -->\n",
       "<g id=\"edge21\" class=\"edge\"><title>10&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1721.7,-36.6617C1715.59,-48.0747 1720.36,-60 1736,-60 1747.12,-60 1752.75,-53.9726 1752.87,-46.3869\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1756.24,-45.434 1750.3,-36.6617 1749.47,-47.2243 1756.24,-45.434\"/>\n",
       "<text text-anchor=\"middle\" x=\"1736\" y=\"-63.8\" font-family=\"Times,serif\" font-size=\"14.00\">er_2:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node12\" class=\"node\"><title>11</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"1918\" cy=\"-23\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"1918\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">11</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;11 -->\n",
       "<g id=\"edge22\" class=\"edge\"><title>10&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1755.59,-23C1786.98,-23 1850.73,-23 1888.03,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1888.25,-26.5001 1898.25,-23 1888.25,-19.5001 1888.25,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"1827\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">er_2:&lt;eps&gt;/0.10536</text>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;11 -->\n",
       "<g id=\"edge23\" class=\"edge\"><title>11&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1905.1,-37.8171C1900.6,-48.8651 1904.9,-60 1918,-60 1927.01,-60 1931.85,-54.737 1932.54,-47.8576\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"1935.97,-47.1205 1930.9,-37.8171 1929.06,-48.2512 1935.97,-47.1205\"/>\n",
       "<text text-anchor=\"middle\" x=\"1918\" y=\"-63.8\" font-family=\"Times,serif\" font-size=\"14.00\">er_3:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node13\" class=\"node\"><title>12</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2076\" cy=\"-23\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"2076\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">12</text>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;12 -->\n",
       "<g id=\"edge24\" class=\"edge\"><title>11&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M1937.51,-23C1964.34,-23 2014.29,-23 2046.02,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2046.03,-26.5001 2056.03,-23 2046.03,-19.5001 2046.03,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"1997\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">er_3:er/0.10536</text>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;12 -->\n",
       "<g id=\"edge25\" class=\"edge\"><title>12&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2063.1,-37.8171C2058.6,-48.8651 2062.9,-60 2076,-60 2085.01,-60 2089.85,-54.737 2090.54,-47.8576\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2093.97,-47.1205 2088.9,-37.8171 2087.06,-48.2512 2093.97,-47.1205\"/>\n",
       "<text text-anchor=\"middle\" x=\"2076\" y=\"-63.8\" font-family=\"Times,serif\" font-size=\"14.00\">z_1:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node14\" class=\"node\"><title>13</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2252\" cy=\"-23\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"2252\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">13</text>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;13 -->\n",
       "<g id=\"edge26\" class=\"edge\"><title>12&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2095.62,-23C2125.89,-23 2186,-23 2221.93,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2222.25,-26.5001 2232.25,-23 2222.25,-19.5001 2222.25,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"2164\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">z_1:&lt;eps&gt;/0.10536</text>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;13 -->\n",
       "<g id=\"edge27\" class=\"edge\"><title>13&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2238.02,-36.6617C2232.04,-48.0747 2236.7,-60 2252,-60 2262.88,-60 2268.37,-53.9726 2268.5,-46.3869\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2271.88,-45.4666 2265.98,-36.6617 2265.1,-47.2196 2271.88,-45.4666\"/>\n",
       "<text text-anchor=\"middle\" x=\"2252\" y=\"-63.8\" font-family=\"Times,serif\" font-size=\"14.00\">z_2:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node15\" class=\"node\"><title>14</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2428\" cy=\"-23\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"2428\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">14</text>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;14 -->\n",
       "<g id=\"edge28\" class=\"edge\"><title>13&#45;&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2271.62,-23C2301.89,-23 2362,-23 2397.93,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2398.25,-26.5001 2408.25,-23 2398.25,-19.5001 2398.25,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"2340\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">z_2:&lt;eps&gt;/0.10536</text>\n",
       "</g>\n",
       "<!-- 14&#45;&gt;14 -->\n",
       "<g id=\"edge29\" class=\"edge\"><title>14&#45;&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2415.62,-38.2025C2411.59,-49.1225 2415.71,-60 2428,-60 2436.25,-60 2440.83,-55.0897 2441.71,-48.5554\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2445.13,-47.6737 2440.38,-38.2025 2438.19,-48.5677 2445.13,-47.6737\"/>\n",
       "<text text-anchor=\"middle\" x=\"2428\" y=\"-63.8\" font-family=\"Times,serif\" font-size=\"14.00\">z_3:&lt;eps&gt;/2.3026</text>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node16\" class=\"node\"><title>15</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2580\" cy=\"-23\" rx=\"19.4968\" ry=\"19.4968\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"2580\" cy=\"-23\" rx=\"23.4965\" ry=\"23.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"2580\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">15</text>\n",
       "</g>\n",
       "<!-- 14&#45;&gt;15 -->\n",
       "<g id=\"edge30\" class=\"edge\"><title>14&#45;&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M2447.69,-23C2472.35,-23 2516.15,-23 2546.34,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"2546.39,-26.5001 2556.39,-23 2546.39,-19.5001 2546.39,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"2502\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">z_3:z/0.10536</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<vector Fst at 0x7f872206bbf0>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Copied from asr_lab2_solutions.ipynb\n",
    "\n",
    "def parse_lexicon(lex_file):\n",
    "    \"\"\"\n",
    "    Parse the lexicon file and return it in dictionary form.\n",
    "    \n",
    "    Args:\n",
    "        lex_file (str): filename of lexicon file with structure '<word> <phone1> <phone2>...'\n",
    "                        eg. peppers p eh p er z\n",
    "\n",
    "    Returns:\n",
    "        lex (dict): dictionary mapping words to list of phones\n",
    "    \"\"\"\n",
    "    \n",
    "    lex = {}  # create a dictionary for the lexicon entries (this could be a problem with larger lexica)\n",
    "    with open(lex_file, 'r') as f:\n",
    "        for line in f:\n",
    "            line = line.split()  # split at each space\n",
    "            lex[line[0]] = line[1:]  # first field the word, the rest is the phones\n",
    "    return lex\n",
    "\n",
    "def generate_symbol_tables(lexicon, n=3):\n",
    "    '''\n",
    "    Return word, phone and state symbol tables based on the supplied lexicon\n",
    "        \n",
    "    Args:\n",
    "        lexicon (dict): lexicon to use, created from the parse_lexicon() function\n",
    "        n (int): number of states for each phone HMM\n",
    "        \n",
    "    Returns:\n",
    "        word_table (fst.SymbolTable): table of words\n",
    "        phone_table (fst.SymbolTable): table of phones\n",
    "        state_table (fst.SymbolTable): table of HMM phone-state IDs\n",
    "    '''\n",
    "    \n",
    "    state_table = fst.SymbolTable()\n",
    "    phone_table = fst.SymbolTable()\n",
    "    word_table = fst.SymbolTable()\n",
    "    \n",
    "    # add empty <eps> symbol to all tables\n",
    "    state_table.add_symbol('<eps>')\n",
    "    phone_table.add_symbol('<eps>')\n",
    "    word_table.add_symbol('<eps>')\n",
    "    \n",
    "    for word, phones  in lexicon.items():\n",
    "        \n",
    "        word_table.add_symbol(word)\n",
    "        \n",
    "        for p in phones: # for each phone\n",
    "            \n",
    "            phone_table.add_symbol(p)\n",
    "            for i in range(1,n+1): # for each state 1 to n\n",
    "                state_table.add_symbol('{}_{}'.format(p, i))\n",
    "            \n",
    "    return word_table, phone_table, state_table\n",
    "\n",
    "\n",
    "# call these two functions\n",
    "lex = parse_lexicon('lexicon.txt')\n",
    "word_table, phone_table, state_table = generate_symbol_tables(lex)\n",
    "\n",
    "def generate_phone_wfst(f, start_state, phone, n):\n",
    "    \"\"\"\n",
    "    Generate a WFST representating an n-state left-to-right phone HMM\n",
    "    \n",
    "    Args:\n",
    "        f (fst.Fst()): an FST object, assumed to exist already\n",
    "        start_state (int): the index of the first state, assmed to exist already\n",
    "        phone (str): the phone label \n",
    "        n (int): number of states for each phone HMM\n",
    "        \n",
    "    Returns:\n",
    "        the final state of the FST\n",
    "    \"\"\"\n",
    "    \n",
    "    current_state = start_state\n",
    "    \n",
    "    for i in range(1, n+1):\n",
    "        \n",
    "        in_label = state_table.find('{}_{}'.format(phone, i))\n",
    "        \n",
    "        sl_weight = fst.Weight('log', -math.log(0.1))  # weight for self-loop\n",
    "        # self-loop back to current state\n",
    "        f.add_arc(current_state, fst.Arc(in_label, 0, sl_weight, current_state))\n",
    "        \n",
    "        # transition to next state\n",
    "        \n",
    "        # we want to output the phone label on the final state\n",
    "        # note: if outputting words instead this code should be modified\n",
    "        if i == n:\n",
    "            out_label = phone_table.find(phone)\n",
    "        else:\n",
    "            out_label = 0   # output empty <eps> label\n",
    "            \n",
    "        next_state = f.add_state()\n",
    "        next_weight = fst.Weight('log', -math.log(0.9)) # weight to next state\n",
    "        f.add_arc(current_state, fst.Arc(in_label, out_label, next_weight, next_state))    \n",
    "       \n",
    "        current_state = next_state\n",
    "        \n",
    "    return current_state\n",
    "\n",
    "def generate_word_wfst(word):\n",
    "    \"\"\" Generate a WFST for any word in the lexicon, composed of 3-state phone WFSTs.\n",
    "        This will currently output word labels.  \n",
    "        Exercise: could you modify this function and the one above to output a single phone label instead?\n",
    "    \n",
    "    Args:\n",
    "        word (str): the word to generate\n",
    "        \n",
    "    Returns:\n",
    "        the constructed WFST\n",
    "    \n",
    "    \"\"\"\n",
    "    f = fst.Fst('log')\n",
    "    \n",
    "    # create the start state\n",
    "    start_state = f.add_state()\n",
    "    f.set_start(start_state)\n",
    "    \n",
    "    current_state = start_state\n",
    "    \n",
    "    # iterate over all the phones in the word\n",
    "    for phone in lex[word]:   # will raise an exception if word is not in the lexicon\n",
    "        \n",
    "        current_state = generate_phone_wfst(f, current_state, phone, 3)\n",
    "    \n",
    "        # note: new current_state is now set to the final state of the previous phone WFST\n",
    "        \n",
    "    f.set_final(current_state)\n",
    "    \n",
    "    return f\n",
    "\n",
    "# example\n",
    "f = generate_word_wfst('peppers')\n",
    "f.set_input_symbols(state_table)\n",
    "f.set_output_symbols(phone_table)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10000000000.0, 10000000000.0, 10000000000.0, 10000000000.0, 10000000000.0, 10000000000.0, 10000000000.0, 10000000000.0, 10000000000.0, 10000000000.0, 10000000000.0, 10000000000.0, 10000000000.0, 10000000000.0, 10000000000.0, 71.71724553457089]\n"
     ]
    }
   ],
   "source": [
    "# To call the decoder (in a dummy example)\n",
    "# f is the WFST generated with the code from asr_lab2_solutions.ipynb\n",
    "decoder = MyViterbiDecoder(f, '')   # empty string '' just means use dummy probabilities for testing\n",
    "decoder.decode()\n",
    "# Check the last time step\n",
    "print(decoder.V[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}