\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*
    {Part \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*
    {Subpart (\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 Project \#\,3
    --- General Instructions}}
\rhead{{\bfseries Fall 2015}}
\lfoot{{Engineering Science, University of Toronto}}
\cfoot{{}}
\rfoot{{Page \thepage\ of \pageref{LastPage}}}


\begin{document}

\chead{{\bfseries\large Project \#\,3 --- 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. 

{}  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{cosine\txtunder similarity(vec1, vec2)} (10\%)}
This function returns the cosine similarity between the sparse vectors \verb;vec1; and \verb;vec2;,  stored as dictionaries. For example, 
\begin{verbatim}
cosine_similarity({"a": 1, "b": 2, "c": 3}, {"b": 4, "c": 5, "d": 6})
\end{verbatim}

should return approximately $0.70$.



\subquestion
   {\code{build\txtunder semantic\txtunder descriptors(sentences)} \label{subpart:builddesc} (35\%)}

This function takes in a list \code{sentences} which contains  lists of 
strings (words) 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}  above: 
\begin{verbatim}
[['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{verbatim}
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{build\txtunder semantic\txtunder descriptors\txtunder from\txtunder files(filenames)} \label{subpart:fromfiles} (20\%)}

This function takes a list of \verb;filenames; of strings, which contains the names of files (the first one can be opened using \verb;open(filenames[0], "r", encoding="utf-8");), and returns the a dictionary of the semantic descriptors of all the words in the files \verb;filenames;, with the files treated as a single text.

You should assume that the following punctuation always separates sentences: \verb;".";, \verb;"!";, \verb;"?";, and that is the only punctuation that separates sentences. You should also assume that that is the only punctuation that separates sentences. You should assume that the only the following punctuation is present in the texts: 
\begin{verbatim}
	[',', '-', '--', ':', ';', '"', "'"]

\end{verbatim}


\subquestion
   {\code{most\txtunder similar\txtunder word(word, choices,
    semantic\txtunder descriptors, similarity\txtunder fn)} (15\%)}

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} and the similarity function \verb;similarity_fn;.  The similarity function is a function which takes in two sparse vectors stored as dictionaries and returns a \verb;float;. An example of such a function is \verb;cosine_similarity;.
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,  similarity\txtunder fn)} (10\%)}

This function takes in a string \code{filename} which is the name of a  file in the same 
format as \code{test.txt}, and returns the percentage (i.e., \verb;float; between \verb;0.0; and \verb;100.0;) of questions on which 
\code{most\txtunder similar\txtunder word()} guesses the answer correctly 
using the semantic descriptors stored in \code{semantic\txtunder 
descriptors}, using the similarity function \verb;similariy_fn;.

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) dog
    (b) cat
    (c) horse
\end{verbatim}
and indicates that the correct answer is ``\code{cat}''.



\subquestion{Efficiency}

You will receive at most 90\% of the available marks for Subpart \ref{subpart:builddesc} and \ref{subpart:fromfiles} and   if 

\code{build\txtunder semantic\txtunder descriptors\txtunder from\txtunder files(filenames)} takes over $120$ seconds to run on an  ECF workstation when the files are the novels specified in Part 
\ref{part:exp}.

\question{\label{part:exp} }

For this part, a detailed report is \textit{not} required. One-sentence  answers and (clearly-labelled) graphs are sufficient.

\subquestion{Experimenting on a large corpus of text (4\%) }

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 (using the cosine similarity similarity function) 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). In your report, 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}

If your program takes too long to run, report the results on a shorter text. 

\subquestion{Experimenting with alternative similarity measures (3\%) }

Two alternative similarity measures between two vectors are:  the negative distance in Euclidean space between the vectors, and the negative distances in Euclidean space between the normalized versions of the vectors:

$$sim_{euc} (v_1, v_2) = -||  v_1 -  v_2 ||$$.
$$sim_{euc_{norm}} (v_1, v_2) = -||  v_1/|v_1| -  v_2/|v_2| ||$$.

Report the performance of the algorithm using the text of the two novels on \verb;text.txt; using these two similarity measures.

\subquestion{Experimenting with smaller corpora of text: efficiency and performance (3\%)}

Plot the performance on \verb;test.txt; and the runtime of the algorithm (including the time to build the descriptor dictionary) on $10\%, 20\%, ...., 90\%, 100\%$ of the text of the two novels, using the cosine similarity measure. Clearly label the axes of your graphs. The runtime can be measured on any computer you like, not necessarily on ECF.

\end{document}
