\documentclass{article} \usepackage[margin=1in]{geometry} \usepackage{amsmath, amsfonts} \usepackage{enumerate} \usepackage{enumitem} \usepackage{graphicx} \usepackage{titling} \usepackage{url} \usepackage{xcolor} \usepackage{etoolbox, environ} \usepackage{xfrac} \usepackage[colorlinks=true,urlcolor=blue]{hyperref} % \usepackage{minted} \usepackage{tikz} \usepackage{bbm} \usepackage{amssymb} \usepackage{subcaption} \captionsetup{compatibility=false} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Commands for customizing the assignment % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand \outdate {November 22, 2016} \newcommand \duedate {5:30 p.m. Monday, December 5, 2016} \title{ Homework 7: Graphical Models; Active Learning \\ \vspace{0.2cm} \large { 10-601B: Machine Learning (Fall 2016) \\ Out \outdate{} \\ Due \duedate{} } } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Useful commands for typesetting the questions % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newtoggle{solutions} \toggletrue{solutions} %\togglefalse{solutions} \NewEnviron{solution}{% \iftoggle{solutions}{% \color{blue} {\bf Solution:} \BODY% }{}% } \newcommand \expect {\mathbb{E}} \newcommand \mle [1]{{\hat #1}^{\rm MLE}} \newcommand \map [1]{{\hat #1}^{\rm MAP}} \newcommand \argmax {\operatorname*{argmax}} \newcommand \argmin {\operatorname*{argmin}} \newcommand \code [1]{{\tt #1}} \newcommand \datacount [1]{\#\{#1\}} \newcommand \ind [1]{\mathbb{I}\{#1\}} \newcommand \norm [1]{\Vert#1\Vert} \newcommand \reals {\mathbb{R}} %%%%%%%%%%%%%%%%%%%%%%%%%% % Document configuration % %%%%%%%%%%%%%%%%%%%%%%%%%% % Don't display a date in the title and remove the white space \predate{} \postdate{} \date{} % Don't display an author and remove the white space %\preauthor{} %\postauthor{} \author{TAs: Fish Tung, Tianshu Ren, Sriram Vasudevan} %%%%%%%%%%%%%%%%%% % Begin Document % %%%%%%%%%%%%%%%%%% \begin{document} \maketitle \section*{Instructions} \begin{itemize} \item {\bf Late homework policy:} Homework is worth full credit if submitted before the due date, half credit during the next 48 hours, and zero credit after that. \item {\bf Submission:} You must submit your code for problem 3 on time electronically by submitting to autolab by \duedate{}. On the Homework 7 autolab page, you can click on the ``download handout'' link to download the submission template, which is a tar archive containing a Octave \code{.m} file for each programming question. Replace each of these files with your solutions for the corresponding problem, create a new tar archive of the top-level directory, and submit your archived solutions online by clicking the ``Submit File'' button. \textbf{\emph{DO NOT}} change the name of any of the files or folders in the submission template. In other words, your submitted files should have exactly the same names as those in the submission template. Do not modify the directory structure. For write-up questions, submit your written answers on Gradescope. \item \textbf{Collaboration policy}: Please read the policy on the course webpage: \url{http://www.cs.cmu.edu/~mgormley/courses/10601b-f16/about.html} \end{itemize} \section*{Problem 1: Disagreement-based Active Learning [30 pts]} \subsection*{\textbf{T} or \textbf{F} [12 pts]} Answer the following questions. If your answer is \textbf{T}, provide 1-2 sentences of justification. If your answer is \textbf{F}, give a counter-example if possible. Recall from the lecture notes that a classification problem is \textbf{realizable} if the true labeling function $h^*$ is in our hypothesis class $H$. Given a set of labeled examples $\{(x_t, y_t)\}_{t=1}^n$, where $y_t = h^*(x_t), \forall t = 1,\ldots, n$, the version space $H'\subseteq H$ is a subset of $H$ in which the hypotheses are consistent with the labels seen so far. The region of disagreement with respect to a version space $H'$, denoted as $\text{DIS}(H')$, is defined to be the part of data space about which there is still some uncertainty. More specifically, $\text{DIS}(H') = \{x \in X \,:\, \exists h_1, h_2\in H', h_1(x)\neq h_2(x)\}$. \begin{enumerate}[label=(\alph*)] \item Assume in the agnostic case, given a concept class $H$ and a sequence of training instances $\{(x_t, y_t)\}_{t=1}^n$. Let $H_t\subseteq H$ be the version space after the learner has received the $t$-th instance. Then $H_t\neq\varnothing$, $\forall t = 1,\ldots, n$. \begin{solution} \end{solution} \item Assume the problem is realizable. Given a concept class $H$ and a sequence of training instances $\{(x_t, y_t)\}_{t=1}^n$. Let $H_t\subseteq H$ be the version space after the learner has received the $t$-th instance. After all $n$ examples have been observed we have $|H_n| \geq 1$. \begin{solution} \end{solution} \item Let $X = \{(x_t, y_t)\}_{t=1}^n$ be a set of $n$ training instances and $H$ be the hypothesis space. Assume our current version space is $H'$. Pick $x_0\in \text{DIS}(H')$. Let $\hat{H}$ be the version space of $X$ after querying $x_0$, i.e., the version space of $X \cup\{(x_0, y_0)\}$, where $y_0$ is provided by the true labeling function, then it must be that $\hat{H} \subset H'$. \begin{solution} \end{solution} % \item Assume the problem is realizable. Let $X = \{(x_t, y_t)\}_{t=1}^n$ be a set of $n$ training instances and $H$ be the hypothesis space. Assume our current version space is $H'$. If $\text{DIS}(H') = \varnothing$, then $\forall h\in H'$, $h$ is the ERM minimizer of the empirical risk function $\ell(h) = \frac{1}{n}\sum_{i=1}^n \mathbb{I}[h(x_i)\neq y_i]$. % % \begin{solution} % \textbf{T}. Since the problem is realizable we know that the true labeling function $h^*\in H'$, it follows that $h^*$ is the ERM minimizer of the above risk function. However, since $\textbf{DIS}(H') = \varnothing$, then all $h\in H'$ have the same labeling on $X$ as $h^*$, which implies every $h\in H'$ is an ERM minimizer on $X$. % \end{solution} \end{enumerate} \subsection*{An Example [18 pts; 3pts for each question]} Consider a binary classification problem where the sample space is $\Omega = \{(\mathbf{x}, y): x \in \mathbb{R}, y \in \{+1, -1\}\}$. Let the concept class $H = \{(a,b), a \leq b\}$, where the decision rule is given by: $$ h_\mathbf{(a,b)}(\mathbf{x}) = \begin{cases} +1 & a < x < b, \\ -1 & otherwise \end{cases} $$ In this problem we assume that $H$ is realizable. Suppose after receiving a sequence of training instances (2.0, +1), (2.5, +1), (-1.0, -1), (0.0, -1) (4.0, -1). \begin{enumerate}[resume*] \item Draw the given sample and explicitly write down the version space $H_1\subseteq H$ that is consistent with all the instances. \begin{solution} \end{solution} \item Write down the region of disagreement for space $H_1,$ i.e, $\text{DIS}(H_1).$ \begin{solution} \end{solution} \item Suppose we receive a new instance (0.5, +1). Does this sample lie in the disagreement region $\text{DIS}(H_1)$? Write down the new version space $H_2\subseteq H$ that is consistent with all the instances including the new instance. \begin{solution} \end{solution} \item This time another new instance (3.0, -1). Does this sample lie in the disagreement region $\text{DIS}(H_2)$? Write down the new version space $H_3\subseteq H$ that is consistent with all the instances including the two new instances. \begin{solution} \end{solution} \item Write down the region of disagreement for space $H_3,$ i.e, $\text{DIS}(H_3).$ \begin{solution} \end{solution} \item Comparing $H_1,$ $H_2$ and $H_2$, $H_3.$ Does it satisfy the answer you have in Problem 1(c)? \end{enumerate} %\section*{Problem 1: Co-training Doesn't Like Groupthink [30 pt]} %Consider the data set in figure \ref{fig:hw7_3}. Each data point has two features. Circled data points are unlabeled points where the true label (shown inside the circle) is invisible to the learning algorithm. %We will use this dataset to co-train two threshold based classifiers $C_1$ and $C_2$ where $C_i$ is trained using feature $i$ %and produces a decision threshold on feature $i$ that maximizes the margin between training examples and the threshold. The "confidence" of a classifier for a new data points is measured by how far away it is from the threshold. %In particular, the farther away the point is %from the decision boundary, the more confident the classifier is. %We will run iterative co-training such that, in each iteration, each classifier adds the unlabeled example it is most confident about to the training data. %Assume that co-training halts when, for each classifier, the unlabeled point that is farthest from the threshold (i.e. most confident) is between the largest known negative example and the smallest known positive example (at that point, the algorithm deems the unlabeled examples too uncertain to label for the other classifier). % %\begin{figure}[h!] %\centering %\includegraphics[scale=0.6]{figures/hwfigure.pdf} %\caption{Data set for problem 3.} %\label{fig:hw7_3} %\end{figure} % %\begin{enumerate} %\item \label{ct2} [10 pt] %Explain what happens in a single iteration of co-training. %Specifically, illustrate: %\begin{itemize} %\item The initial thresholds produced by $C_1$ and $C_2$ given labeled examples. %\item The new labeled example (coordinates and label) that will be provided to $C_2$ by $C_1$ and vice versa. %\item The new thresholds after incorporating the new examples. %\item The number of data points misclassified by $C_1$ using the initial and updated thresholds. %\end{itemize} % %\item \label{ct3} [15 pt] Now assume that we train both $C_1$ and $C_2$ using feature 1. Therefore they share the same view of the data. What happens %if we run co-training to completion ? What are the initial thresholds, which unlabeled example will be added in each iteration at what are the final thresholds ? % %\item \label{ct4} [5 pt] Based on your observations of parts \ref{ct2} and \ref{ct3}, %provide an intuitive explanation (in no more than two lines) for why having %features that satisfy independence given the label helps co-training to be %successful. %\end{enumerate} \section*{Problem 2: Bayesian Network [20 pts]} Figure \ref{figure:BN} shows a Bayesian Network that encodes the dependencies between the following variables: Course ($C$), Assignment ($A$), Exam ($E$), Interview ($I$), Sleep ($S$) and Healthy ($H$). \begin{figure}[h!] \centering \includegraphics[width=0.7\textwidth]{figures/601_7} \caption{Bayesian Network that represents the joint distribution over the variables used to predict park usage. } \label{figure:BN} \end{figure} \vspace{5mm} \begin{enumerate}[label=(\alph*)] \item \relax{[10 pts]} Using the graphical model depicted in Figure \ref{figure:BN} state whether the following independence statements are True or False. \begin{enumerate}[label=\arabic*.] \item $A \perp E$ \begin{solution} \end{solution} \item $C \perp H$ \begin{solution} \end{solution} \item $I \perp C$ \begin{solution} \end{solution} \item $I \perp H$ \begin{solution} \end{solution} \item $ C \perp H \mid S $ \begin{solution} \end{solution} \item $I \perp C \mid S $ \begin{solution} \end{solution} \item $A \perp E \mid C $ \begin{solution} \end{solution} \item $A \perp H \mid C, E $ \begin{solution} \end{solution} \item $S \perp C \mid E, I, A $ \begin{solution} \end{solution} \item $A \perp E \perp I \perp H \mid C, S $ \begin{solution} \end{solution} \end{enumerate} \item \relax{[6 pts]} D-separation. For the following questions provide your answer and a brief justification. \begin{enumerate}[label=\arabic*.] \item Which variables are d-separated from $H$? \begin{solution} \end{solution} \item Which variables are d-separated from $A$ given $C$? \begin{solution} \end{solution} \item Which variable(s) do you need to condition on so that $C$ and $H$ are d-separated? \begin{solution} \end{solution} \end{enumerate} \vspace{0.2in} \item \relax{[4 pts]} Write down the factorized form of the joint distribution over all the variables represented in Figure \ref{figure:BN}, $P(C,A,E,I,S,H)$. \begin{solution} \end{solution} \end{enumerate} \section*{Problem 3: Hidden Markov Models [50 pts]} A HMM defines a joint probability distribution over sequences of state-observation pairs. %We will consider HMMs where both states and observations take a %finite number of possible values. Let \\ $\mathcal{Y} = \{1, \ldots, n, n+1, n+2\}$ denote the set of $n + 2$ possible states and $\mathcal{X} = \{1, \ldots, m\}$ denote the set of $m$ possible observations. Note that state $n+1$ is define to be the state "start", and state $n+2$ is defined to be the state of "stop." For simplicity, we define two constant $\text{START} = n+1$ and $\text{STOP} = n+2.$ %Furthermore, define two special states: \textit{start} and \textit{stop}. %Every state sequence begins with $\textit{start}$ and ends %with $\textit{stop}$. %There are no observations associated with these states, %and they only occur, respectively, at the beginning and the end of state sequences. % %Note that the states %$\textit{start}$ and $\textit{stop}$ are normal states in much the same %way as the states in $\mathcal{S}$, but because it is impossible to transition %back into start and to transition out of stop, it is convenient to single %them out in this way. A HMM is determined by two types of parameters: emission parameters $A \in \mathbb{R}^{n \times m}$ and state transition parameters $B \in \mathbb{R}^{(n + 2)\times (n+2)}.$ For a sequence of length $T,$ for $k = \{ 1, 2, \cdots, T \},$ $A_{ij} = P(X_k = j| Y_k = i)$ and $B_{ij} = P(Y_k = j| Y_{k-1} = i).$ Assume $P(Y_0) = \text{START}$ with probability 1 and $P(Y_{T+1})= \text{STOP}$ with probability 1 at both train and test time. The transition parameter from the initial state to time step $1$ is the $(n+1)$-th row of $B$, i.e., $B_{\text{START}, j} = P(Y_1 = j | Y_0 = \text{START})$ and the transition from $T$ to $T+1$ is the $(n+2)$-th column of $B$, i.e., $B_{i, \text{STOP}} = P(Y_{T + 1} = \text{STOP} | Y_T = i) \in \mathbb{R}^{n}$ The state transition and state observation parameters are the same across all time steps and all sequences. It is said that the HMM is homogeneous. Given the above definition of a HMM, a sequence of state-observation pairs of length $T$ has probability \begin{equation} P(Y_{0:T+1}, X_{1:T}; B, A) =P(Y_0) \prod_{t = 1}^{T + 1} P(Y_t | Y_{t - 1}; B) \prod_{t = 1}^T P(X_t | Y_t; A) , \label{eq:prob_fact} \end{equation} where $Y_t \in \mathcal{Y}$ for $t \in \{0, \ldots, T+1\}$, and $X_t \in \mathcal{X}$, for $t \in \{1, \ldots, T\}$. From now on, we will use a simplified notation where we omit the parameters and subscripts when the meaning is clear from context. \subsection*{Structure [8 pts]} \begin{enumerate}[label=(\alph*)] \item \relax{[2 pts]} Draw the graphical model corresponding to HMM model for a sequence of state-observation pairs with length $T=3$. \begin{solution} \end{solution} \item \relax{[3 pts]} Briefly describe how samples are generated from HMM. \begin{solution} \end{solution} \item \relax{[3 pts]} List two types of conditional independence statements from the HMM graphical model structure. \begin{solution} \end{solution} \end{enumerate} \subsection*{Estimation [8 pts]} We will now derive maximum likelihood estimator for the HMM parameters given a set of fully observed $N$ training examples $\mathcal{D} = \{ (y_{1:T_1}^{(1)}, x_{1:T_1}^{(1)}), \ldots, (y_{1:T_N}^{(N)}, x_{1:T_N}^{(N)}) \}$, with lengths $T_1, \ldots, T_N$. Note that using the assumption that $P(Y_0) = \text{START}$ with probability 1 and $P(Y_{T+1})= \text{STOP}$ with probability 1 at both train and test time, $y_0^{(k)} = START$ and $y_{T+1}^{(k)} = STOP$ for all examples in $\mathcal{D}.$ It is convenient to remember that for a categorical random variable $X$ over $K$ different events with parameters $\beta_1, \ldots, \beta_K$ with $\sum_{k = 1}^K \beta_k = 1$, the probability of event $x \in \{1, \ldots, K\}$ can be written as \begin{equation*} P_X(x) = \prod_{k = 1}^K \beta_{k}^{ \mathbbm{1}[x = k]}, \end{equation*} where $\mathbbm{1}[\cdot]$ is the indicator function. This can be similar to what you have done in previous homeworks to write the likelihood under a Bernoulli model, which is just a categorical distribution with $K = 2$. \begin{enumerate}[label=(\alph*), resume*] \item \relax{[2 pts]} Write the log likelihood $\ell(B, A)$ for the training set $\mathcal{D}$. \begin{solution} \end{solution} \item \relax{[6 pts]} Show that the log likelihood $\ell(B, A)$ can be written as a separable function of the parameters $B_{\text{START},j}$, and $B_{i, :}, B_{i, \text{STOP}}, A_{i, :}$ for all $i \in \mathcal{Y}$, i.e., $\ell(B, A) = \ell(B_{\text{START},j}) + \sum_{i = 1}^n \ell(B_{i, :}) + \ell(B_{i, :}, B_{i, \text{STOP}}) + \ell(A_{i, :})$. What are the statistics of the training data needed to evaluate the log likelihood? \begin{solution} \end{solution} \end{enumerate} The maximum likelihood solution for the log-likelihood cannot just be computed by differentiating and equating to zero. This is because of the normalization constraints for the distributions, i.e., $\sum_{j = 1}^n B_{\text{START}, j} = 1$, and $\sum_{j = 1}^{|\mathcal{Y}|} B_{i, j} = 1$, and $\sum_{j = 1}^m A_{i, j} = 1$, for all $i \in \mathcal{X}$. The problem can be solved by introducing Lagrange multipliers for the constraints. We get the following natural estimators: \begin{align*} \hat{B}_{ij} &= \frac{c_{\text{trans}}(i, j)}{c(i)}, \\ \hat{A}_{i,j} &= \frac{c_{\text{obs}}(i, j)}{c(i)}, \end{align*} where \begin{align*} c_{\text{trans}}(i, j) &= \sum_{k = 1}^N \sum_{t = 1}^{T_k} \mathbbm{1}[y^{(k)}_{t} = i, y^{(k)}_{t + 1} = j], \\ % c(i) &= \sum_{j = 1}^{|\mathcal{Y}|} c_{\text{trans}}(i, j) \\ % c_{\text{obs}}(i, j) &= \sum_{k = 1}^N \sum_{t = 1}^{T_k} \mathbbm{1}[y^{(k)}_{t} = i, x^{(k)}_{t} = j]. \\ \end{align*} Estimating the parameters of a HMM from labelled data reduces to counting and normalizing. \subsection*{Inference [12 pts]} Given a fixed HMM, i.e., a HMM with fixed parameters, $B$ and $A$, there are various queries that we may want to answer. For example, we could want to know what is the probability of a sequence of observations $X_{1:T}$, i.e, $P(X_{1:T})$. Evaluating this requires marginalizing over all possible sequences of states that may have generated $x_{1:T}$, i.e., \begin{equation} P(X_{1:T} = x_{1:T}) = \sum_{Y_{1:T} \in \mathcal{Y}^T} P( Y_{1:T}, X_{1:T} = x_{1:T}) . \label{eq:prob} \end{equation} Doing the summation naively is intractable. An efficient approach will exploit the HMM structure. A more common query is given a sequence of observations $x_{1:T}$, what is the most likely sequence of states $Y_{1:T}$ that gave rise to $x_{1:T}$. This is called MAP or Viterbi decoding and it is written as \begin{equation} \label{eq:viterbi_dec} \hat{Y}_{1:T} = \argmax_{Y_{1:T}} P(Y_{1:T} | X_{1:T} = x_{1:T}). \end{equation} Another common way of decoding predicts the most likely state for each position in the sequence, given the sequence of observations $x_{1:T}$ and marginalizing out all the other state random variables. This is called marginal decoding and it is written as \begin{equation} \hat{Y}_{t} = \argmax_{Y_{t}} P(Y_{t} | X_{1:T} = x_{1:T}), \label{eq:marginal_dec} \end{equation} for $t = 1, \ldots, T$. The marginal over $Y_t$ can be computed naively as \begin{equation*} P(Y_{t} | X_{1:T} = x_{1:T}) = \sum_{Y_{-t} \in \mathcal{Y}^{T - 1}} P(Y_{1:T} | X_{1:T} = x_{1:T}), \end{equation*} where $Y_{-t}$ denotes a state assignment to all state variables except $Y_t$. \begin{enumerate}[label=(\alph*), resume*] \item \label{eq:viterbi_equiv} \relax{[2 pts]} Show that the decoding rule \ref{eq:viterbi_dec} is equivalent to $\argmax_{Y_{1:T}} P(Y_{1:T}, X_{1:T} = x_{1:T})$. \begin{solution} \end{solution} \item \relax{[2 pts]} What is the time complexity of doing Viterbi decoding naively in terms of the number of states $n$, the number of observations $m$, and the length of the sequence $T$ (i.e. evaluating $\hat{Y}_{1:T} = \argmax_{Y_{1:T}} P(Y_{1:T}, X_{1:T} = x_{1:T})$)? \begin{solution} \end{solution} \end{enumerate} We will now show how the factorization \ref{eq:prob} can be used to derive an efficient algorithm for Viterbi decoding. The derivation is similar to the one for Forward-Backward algorithm found in the Bishop textbook. \begin{enumerate}[label=(\alph*), resume*] \item \relax{[6 pts]} Derive an efficient algorithm to do Viterbi decoding. Hint: Start with the equivalent definition given in \ref{eq:viterbi_equiv}, substitute the definition of the joint, use the fact that not all terms in the product depend on all the variables. Consider defining the following recursion $\alpha_0(\text{START} ) = 1,$ $\alpha_0(i) = 0$ for $\forall i \neq \text{START},$ and $\alpha_{t + 1}(j) = \max_{i \in \mathcal{Y}} \alpha_{t}(i) P(Y_{t+1}=j| Y_{t}= i)P(X_{t + 1} = x_{t+1}| Y_{t+1} = j)$, for $t = 1, \ldots, T - 1$. The term $\alpha_t(j)$ can be interpreted as the maximum score for a partial state assignment ending at state $j$ at step $t$. \begin{solution} \end{solution} \item \relax{[2 pts]} What is the computational complexity of Viterbi decoding using the algorithm derived in the previous exercise? \begin{solution} \end{solution} \end{enumerate} %For each position you need to keep not only the score, but also the %a backpointer that keep track for each position and each state, what was the %previous \subsection*{Implementation [18 pts]} We will now train a HMM for a Natural Language Processing task: Named Entity Recognition (NER). In what follows we interchangeably talk of states as tags or labels and observations as words. We will learn the parameters from labelled data, implement Viterbi decoding and compare it to a simple baseline that does independent predictions for each label in the sequence. Named Entity Recognition is a sequence labelling task that seeks to identify elements in text from specific categories. The labels have a BIO specifiers (\textit{begin, inside}, and \textit{outside}). In our case, there are four categories: \textit{Person, Organization, Location} and \textit{Miscellaneous}. There are nine labels total: eight for the cross-product of the four categories with the \textit{begin} and \textit{inside} specifiers; one for the \textit{outside} specifier. An example sentence from the dataset is shown below: \begin{center} {\tt \begin{tabular}{cccccccc} B-LOC & O & B-PER & O & B-LOC & O & B-PER & O \\ Iraq & 's & Saddam & meets & Russia & 's & Zhirinovsky & . \end{tabular} } \end{center} There are structural constraints in the tagging scheme: a label of type \textit{inside} has to be preceded by a label of type \textit{begin} of the same category. A NER dataset from the CoNNL 2003 shared task has been provided in \textit{data.mat}. Both the train and test datasets have been preprocessed, and both tags and words have been indexed and substituted by integers. The file \textit{data.mat} contains: \begin{itemize} \item \textit{train}: Structure with the training data. \begin{itemize} \item \textit{word\_seqs}: Cell array with the word sequences. \item \textit{tag\_seqs}: Cell array with the tag sequences. Matching dimensions to \textit{word\_seqs}. \end{itemize} \item \textit{test} Test dataset. Same structure as the training dataset. \item \textit{index\_to\_word}: Contains the mapping from integers to words used to preprocess the data. Words that were not in the vocabulary were mapped to \textit{OOV}. Can be used with the function \textit{map\_to\_readable} to get back the (preprocessed) readable sequences. \item \textit{index\_to\_tag}: Same as \textit{index\_to\_word}, but for tags. For tags there is no \textit{OOV} equivalent. \end{itemize} For the implementation questions, you will be asked to complete parts of the code provided. The naming convention used in the code follows in part the notation in the writeup. We briefly describe the structure of the code provided. \begin{itemize} \item \textit{baseline\_train.m}: Contains the function {\tt [baseline\_params] = baseline\_train(state\_seqs, obs\_seqs, n, m)}. Used to train a model that does independent prediction for each of the labels just based on the observation of that position. The statistics that you will need to collect here are the same as the observation statistics for the HMM. \item \textit{baseline\_decode.m}: Contains the function \texttt{[pred\_state\_seqs] = baseline\_decode(baseline\_params, obs\_seqs)} You will need to do baseline decoding using the parameters computed in \texttt{baseline\_train}, i.e., for each word in each of the sentences, predict the tag that occurred most frequently with that word. % NOTE: say that this is what they will have to do. \item \textit{hmm\_train.m}: Contains the function \texttt{[hmm\_params] = hmm\_train(state\_seqs, obs\_seqs, n, m, alpha\_obs, alpha\_trans}. You will have to collect the statistics from the training data that are necessary to evaluate the estimators for the parameters of the HMM. \item \textit{hmm\_decode.m}: Contains the function \texttt{[pred\_state\_seqs] = hmm\_decode(hmm\_params, obs\_seqs)}. You will have to implement the Viterbi decoding here. \item \textit{map\_to\_readable.m}: Used to map sequences back to a readable format. \item \textit{main.m}: Code for training the model and running all the experiments. After the functions have been completed, these can be used to obtain test and train results. \end{itemize} \begin{enumerate}[label=(\alph*), resume*] \item \relax{[1 pts]} What is j = $\argmax_j B_{\text{START}, j}$, where $B$ is the MLE? (example answer: the least frequent words.) \item \relax{[1 pts]} What is i = $\argmax_i B_{i, \text{STOP}}$, where $B$ is the MLE? \item \relax{[1 pts]} What is $B_{\text{STOP}, j}$, where $B$ is the MLE and $j \neq \text{STOP}$? \item \relax{[3 pts]} Complete the function {\tt [baseline\_params] = baseline\_train(state\_seqs, obs\_seqs, n, m)}. Compute the co-occurrence counts of state-observation pairs. \item \relax{[2 pts]} Complete the function {\tt [pred\_state\_seqs] = baseline\_decode(baseline\_params, obs\_seqs)}. For each observation, you will predict the label that occurred most frequently with it. \item \relax{[5 pts]} Complete the function {\tt [hmm\_params] = hmm\_train(state\_seqs, obs\_seqs, n, m, alpha\_obs, alpha\_trans) }. You will need to collect the statistics from the training data according to the expressions computed in the estimation section. The arguments {\tt alpha\_obs} and {\tt alpha\_trans} are parameters for add-$k$ smoothing for the state observation probabilities and the state transition probabilities. \item \relax{[5 pts]} Complete the function {\tt [pred\_state\_seqs] = hmm\_decode(hmm\_params, obs\_seqs)}. You will need to implement the computation of the Viterbi messages and the backpointers to recover the most probable label sequence. Note: you will work in log-probabilities, rather than directly with probabilities, to avoid numeric underflow. This does not change the maximum probability labelling of the sequence. \end{enumerate} \subsection*{Analysis [4 pts]} \begin{enumerate}[label=(\alph*), resume*] \item \relax{[2 pts]} Run the code with {\tt alpha\_obs = 0.1} and {\tt alpha\_trans = 0}. What are the results that you get? How do you justify the difference in accuracy between the baseline and Viterbi decoding? \begin{solution} \end{solution} \item \relax{[2 pts]} Run the code with {\tt alpha\_obs = 0} and {\tt alpha\_trans = 0}. Are the results for Viterbi better or worse that in the previous exercise? How do you justify the difference? \begin{solution} \end{solution} \end{enumerate} \section*{Submission Instructions} To submit your work through Autolab, put the following files in a folder named \textit{hw7}, compress it, and submit the resulting tar file: \textit{hw7.tar}. Please, do not include the data file \textit{data.mat} in the tar file, as this will exceed the current submission size limit. \begin{itemize} \item \textit{baseline\_train.m} \item \textit{baseline\_decode.m} \item \textit{hmm\_train.m} \item \textit{hmm\_decode.m} \item \textit{written\_solutions.pdf} \end{itemize} \end{document}