\documentclass[11pt]{article}
\usepackage{calc,fancyhdr,lastpage}
\usepackage[normalem]{ulem}
\usepackage[hmargin=.75in,vmargin=1in,
            footskip=.55in,headsep=.55in-\headheight]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{url}

% Formats, symbols, abbreviations.
\let\altemph\textsl
\let\strong\textbf
\let\code\texttt
\let\latinabb\emph
\newcommand*{\etc}{\latinabb{etc}}
\newcommand*{\eg}{\latinabb{e.g.}}
\newcommand*{\ie}{\latinabb{i.e.}}
% To get proper-looking symbols in \texttt.
\newcommand*{\txtbksl} {\symbol{"5C}}% \
\newcommand*{\txtcaret}{\symbol{"5E}}% ^
\newcommand*{\txtunder}{\symbol{"5F}}% _
\newcommand*{\txtlcurl}{\symbol{"7B}}% {
\newcommand*{\txtrcurl}{\symbol{"7D}}% }
\newcommand*{\txttilde}{\symbol{"7E}}% ~

% Commands \question[marks]{title} and \subquestion[marks]{title}.
\newcounter{questionnumber}
\newcommand*{\question}[2][]
   {\refstepcounter{questionnumber}\section*
    {Question \thequestionnumber.\quad
        \ifx\empty#1\empty\else[#1 marks]\quad\fi#2}}
\newcounter{subquestionnumber}[questionnumber]
\renewcommand*{\thesubquestionnumber}{\alph{subquestionnumber}}
\newcommand*{\subquestion}[2][]
   {\refstepcounter{subquestionnumber}\subsubsection*
    {Part (\thesubquestionnumber)\quad
       \ifx\empty#1\empty\else[#1 marks]\quad\fi#2}}

% Redefine `enumerate' to use less vertical space.
\let\etaremune\enumerate
\let\etaremunedne\endenumerate
\renewenvironment{enumerate}
   {\etaremune
    \setlength{\topsep}{.25ex plus .125ex minus .1825ex}%
    \setlength{\itemsep}{\topsep}\setlength{\parsep}{0ex}%
    \setlength{\leftmargin}{1.75em}\setlength{\labelsep}{.5em}%
    \setlength{\labelwidth}{1.75em}\ignorespaces}
   {\etaremunedne}

% Redefine `itemize' to use less vertical space.
\let\ezimeti\itemize
\let\ezimetidne\enditemize
\renewenvironment{itemize}
   {\ezimeti
    \setlength{\topsep}{.25ex plus .125ex minus .1825ex}%
    \setlength{\itemsep}{\topsep}\setlength{\parsep}{0ex}%
    \setlength{\leftmargin}{1.75em}\setlength{\labelsep}{.5em}%
    \setlength{\labelwidth}{1.75em}\ignorespaces}
   {\ezimetidne}

%% A heading in the instructions.
\newcommand*{\heading}[1]{\subsubsection*{#1}}

% Headings.
\pagestyle{fancy}
\let\headrule\empty
\let\footrule\empty
\lhead{{\bfseries CSC\,180\,H1F}}
\chead{{\bfseries\large Assignment \#\,2
    --- General Instructions}}
\rhead{{\bfseries Fall 2014}}
\lfoot{{Engineering Science, University of Toronto}}
\cfoot{{}}
\rfoot{{Page \thepage\ of \pageref{LastPage}}}


\begin{document}
\chead{{\bfseries\large Assignment \#\,2 --- Semantic Similarity}}

\noindent
One type of question encountered in the Test of English as a Foreign 
Language (TOEFL) is the ``Synonym Question'', where students are asked to 
pick a synonym of a word out of a list of alternatives.  For example:
\begin{verbatim}
     1. vexed                                                  (Answer: (a) annoyed)
    (a) annoyed
    (b) amused
    (c) frightened
    (d) excited
\end{verbatim}
For this assignment, you will build an intelligent system that can learn to 
answer questions like this one.  In order to do that, the system will 
approximate the \emph{semantic similarity} of any pair of words.  The 
semantic similarity between two words is the measure of the closeness of 
their meanings.  For example, the semantic similarity between ``car'' and 
``vehicle'' is high, while that between ``car'' and ``flower'' is low.

{}  In order to answer the TOEFL question, you will compute the semantic 
similarity between the word you are given and all the possible answers, and 
pick the answer with the highest semantic similarity to the given word.  
More precisely, given a word $w$ and a list of potential synonyms $s_1$, 
$s_2$, $s_3$, $s_4$, we compute the similarities of $(w,s_1)$, $(w,s_2)$, 
$(w,s_3)$, $(w,s_4)$ and choose the word whose similarity to $w$ is the 
highest.

{}  We will measure the semantic similarity of pairs of words by first 
computing a \emph{semantic descriptor vector} of each of the words, and 
then taking the similarity measure to be the \emph{cosine similarity} 
between the two vectors.

{}  Given a text with $n$ words denoted by ($w_1, w_2, ..., w_n$) and a word $w$, let $desc_w$ be the semantic descriptor vector of $w$ computed using the text. $desc_w$ is an $n$-dimensional vector. The $i$-th coordinate of $desc_{w}$ is the number of sentences in which both $w$ and $w_i$ occur.  For efficiency's sake, we will store the semantic 
descriptor vector as a dictionary, not storing the zeros that correspond to 
words which don't co-occur with $w$.  For example, suppose we are given the 
following text (the opening of \emph{Notes from the Underground} by Fyodor 
Dostoyevsky, translated by Constance Garnett):
\begin{quote}
    I am a sick man.  I am a spiteful man.  I am an unattractive man.  I 
    believe my liver is diseased.  However, I know nothing at all about my 
    disease, and do not know for certain what ails me.
\end{quote}
The word ``man'' only appears in the first three sentences.  Its semantic 
descriptor vector would be:
\begin{verbatim}
    {"i": 3, "am": 3, "a": 2, "sick": 1, "spiteful": 1, "an": 1, "unattractive": 1}
\end{verbatim}
The word ``liver'' only occurs in the second sentence, so its semantic 
descriptor vector is:
\begin{verbatim}
    {"i": 1, "believe": 1, "my": 1, "is": 1, "diseased": 1}
\end{verbatim}
We store all words in all-lowercase, since we don't consider, for example, 
``Man'' and ``man'' to be different words.  We do, however, consider, \eg, 
``believe'' and ``believes'', or ``am'' and ``is'' to be different words.  
We discard all punctuation.

{}  The cosine similarity between two vectors $u = \{u_1,u_2,\dots,u_N\}$ 
and $v = \{v_1,v_2,\dots,v_N\}$ is defined as:
\[
    \operatorname{sim}(u, v)
      = \frac{u \cdot v}{|u||v|}
      = \frac{\sum_{i = 1}^N u_i v_i}
             {\sqrt{\left(\sum_{i = 1}^N u_i^2\right)
                    \left(\sum_{i = 1}^N v_i^2\right)}}
\]
We cannot apply the formula directly to our semantic descriptors since we 
do not store the entries which are equal to zero.  However, we can still 
compute the cosine similarity between vectors by only considering the 
positive entries.  See the starter code for how this can be accomplished.

{}  For example, the cosine similarity of ``man'' and ``liver'', given the 
semantic descriptors above, is
\[
    \frac{3 \cdot 1 \text{ (for the word \code{"i"})}}
         {\sqrt{(3^2+3^2+2^2+1^2+1^2+1^2+1^2)(1^2+1^2+1^2+1^2+1^2)}}
      = 3 / \sqrt{130} = 0.2631\dots
\]


\question{}

Implement the following functions in \code{synonyms.py}.  Note that the 
names of the functions are case-sensitive and must not be changed.  You are 
not allowed to change the number of input parameters, nor to add any global 
variables.  Doing so will cause your code to fail when run with our testing 
programs, so that you will not get any marks for functionality.  We provide 
you with a starter version of \code{synonyms.py}

\subquestion
   {\code{get\txtunder sentence\txtunder lists(text)}}

This function takes in a string \code{text}, and returns a list which 
contains lists of strings, one list for each sentence (as defined below) in 
the string \code{text}.  A list representing a sentence is a list of the 
individual words in the sentence, each one in all-lowercase.

{}  For our purposes, sentences are separated by one of the strings 
\code{"."}, \code{"?"}, or \code{"!"}.  We ignore the possibility of other 
punctuation separating sentences.  We also assume that every period 
separates sentences.  For example, the string
\begin{verbatim}
    "The St. Bernard is a friendly dog!"
\end{verbatim}
is considered to be two sentences: \verb|"The St"| and
\verb|"Bernard is a friendly dog"|.

{}  The words in the list that represents the sentence must be in the order 
in which they appear in the sentence, and must not begin or end with 
punctuation.

{}  You should assume that only the following punctuation signs are present 
in the text file: \code{","}, \code{"-"}, \code{"--"}, \code{":"}, 
\code{";"}, \code{"!"}, \code{"?"}, \code{"."}, the single quote, or the double quote. That the single quote is considered punctuation means that, for example, ``don't" is considered to be two words, ``don" and ``t". The possesive form ``School's'' is also considered to be two words, ``School" and ``s".


\noindent
For example, if the text file contains the following (and nothing else):
\begin{verbatim}
    Hello, Jack.  How is it going?  Not bad; pretty good, actually...  Very very
    good, in fact.
\end{verbatim}
then the function should return the following list:
\begin{verbatim}
    [['hello', 'jack'],
     ['how', 'is', 'it', 'going'],
     ['not', 'bad', 'pretty', 'good', 'actually'],
     ['very', 'very', 'good', 'in', 'fact']]
\end{verbatim}

\subquestion
   {\code{get\txtunder sentence\txtunder lists\txtunder from\txtunder
    files(filenames)}}

This function takes in a list of strings \code{filenames}, each one the 
name of a text file, and returns the list of every sentence contained in 
all the text files in \code{filenames}, in order. The list is in the same format as in Part a, but with the files rather than a string serving as the source of the text..

\subquestion
   {\code{build\txtunder semantic\txtunder descriptors(sentences)}}

This function takes in a list \code{sentences} which contains lists of 
strings representing sentences, and returns a dictionary \code{d} such that 
for every word \code{w} that appears in at least one of the sentences, 
\code{d[w]} is itself a dictionary which represents the semantic descriptor 
of \code{w} (note: the variable names here are arbitrary).  For example, if 
\code{sentences} represents the opening of \emph{Notes from the 
Underground} as above, part of the dictionary returned would be:
\begin{verbatim}
    { 'man': {'i': 3, 'am': 3, 'a': 2, 'sick': 1, 'spiteful': 1, 'an': 1,
              'unattractive': 1},
      'liver': {'i': 1, 'believe': 1, 'my': 1, 'is': 1, 'diseased': 1},
      ... }
\end{verbatim}
with as many keys as there are distinct words in the passage.

\subquestion
   {\code{most\txtunder similar\txtunder word(word, choices,
    semantic\txtunder descriptors)}}

This function takes in a string \code{word}, a list of strings 
\code{choices}, and a dictionary \code{semantic\txtunder descriptors} which 
is built according to the requirements for \code{build\txtunder 
semantic\txtunder descriptors}, and returns the element of \code{choices} 
which has the largest semantic similarity to \code{word}, with the semantic 
similarity computed using the data in \code{semantic\txtunder descriptors}.  
If the semantic similarity between two words cannot be computed, it is 
considered to be $-1$.  In case of a tie between several elements in 
\code{choices}, the one with the smallest index in \code{choices} should be 
returned (\eg, if there is a tie between \code{choices[5]} and 
\code{choices[7]}, \code{choices[5]} is returned).

\subquestion
   {\code{run\txtunder similarity\txtunder test(filename,
    semantic\txtunder descriptors)}}

This function takes in a string \code{filename} which is a file in the same 
format as \code{test.txt}, and returns the percentage of questions on which 
\code{most\txtunder similar\txtunder word()} guesses the answer correctly 
using the semantic descriptors stored in \code{semantic\txtunder 
descriptors}.

The format of \code{test.txt} is as follows.  On each line, we are given a 
word (all-lowercase), the correct answer, and the choices.  For example, 
the line:
\begin{verbatim}
    feline cat dog cat horse
\end{verbatim}
represents the question:
\begin{verbatim}
    feline:
    (a) cat
    (b) dog
    (c) horse
\end{verbatim}
and indicates that the correct answer is ``\code{cat}''.


\question{}

Add code to test each of the functions in 1a-1d  You are encouraged to test 
your helper functions, but that will not be graded.  You should submit all 
the files needed for the testing of your functions, so that we can run the 
tests if we so choose.


\question{}

Download the novels \emph{Swann's Way} by Marcel Proust, and \emph{War and 
Peace} by Leo Tolstoy from Project Gutenberg, and 
use them to build a semantic descriptors dictionary.  Report how well the 
program performs on the questions in \code{test.txt}, using those two 
novels at the same time.  Note: the program may take several minutes to 
run (or more, if the implementation is inefficient). Include the code used to generate the results you report.  The novels are available at the following URLs:

    \url{http://www.gutenberg.org/cache/epub/7178/pg7178.txt}

    \url{http://www.gutenberg.org/cache/epub/2600/pg2600.txt}


\end{document}
