Temporal Information Extraction for Question Answering\\ Using Syntactic Dependencies in an LSTM-based Architecture
Yuanliang Meng
Anna Rumshisky
Alexey Romanov
{\tt\small \{ymeng
arum
aromanov\
In this paper, we propose to use a set of simple, uniform in architecture LSTM-based models to recover different kinds of temporal relations from text. Using the shortest dependency path between entities as input, the same architecture is implemented to extract intra-sentence, cross-sentence, and document creation time relations. A ``double-checking'' technique reverses entity pairs in classification, boosting the recall of positive cases and reducing misclassifications between opposite classes. An efficient pruning algorithm resolves conflicts globally. Evaluated on QA-TempEval (SemEval2015 Task 5), our proposed technique outperforms state-of-the-art methods by a large margin. We also conduct intrinsic evaluation and post state-of-the-art results on Timebank-Dense. %Although our model is not optimized on TimeBank-Dense dataset, which uses different methods for annotation and evaluation, it obtains new state-of-the-art results on this corpus as well. %It uses a relatively simple LSTM-based architect, and relies on shortest dependency paths in sentences. A ``double-checking" technique reverses entity pairs in classification, boosting the recall of positive cases and reducing misclassifications between opposite classes. An efficient pruning algorithm resolves conflicts globally. Running on SemEval2015 Task 5, our proposed method outperforms state-of-the-art methods by a large margin. % This paper proposes a method to annotate temporal relations from text documents. It uses a relatively simple LSTM-based architect, and relies on shortest dependency paths in sentences. A ``double-checking" technique reverses entity pairs in classification, boosting the recall of positive cases and reducing misclassifications between opposite classes. An efficient pruning algorithm resolves conflicts globally. Running on SemEval2015 Task 5, our proposed method outperforms state-of-the-art methods by a large margin.
emnlp2017.tex
%\title{emnlp 2017 instructions}
% File emnlp2017.tex
%

\documentclass[11pt,letterpaper]{article}
\usepackage{emnlp2017}
\usepackage{times}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[]{algorithm2e}
\usepackage{url}

\usepackage[font=small]{caption}

% Uncomment this line for the final submission:
\emnlpfinalcopy

%  Enter the EMNLP Paper ID here:
\def\emnlppaperid{1419}

% To expand the titlebox for more authors, uncomment
% below and set accordingly.
% \addtolength\titlebox{.5in}    

\newcommand\BibTeX{B{\sc ib}\TeX}


\title{Temporal Information Extraction for Question Answering\\ 
Using Syntactic Dependencies in an LSTM-based Architecture}

\author{Yuanliang Meng, Anna Rumshisky, Alexey Romanov \\
        {\tt\small \{ymeng,arum,aromanov\}@cs.uml.edu} \\
        Department of Computer Science \\
        University of Massachusetts Lowell \\
        Lowell, MA 01854
}

\date{}

\begin{document}
\maketitle
\begin{abstract}

  In this paper, we propose to use a set of simple, uniform in architecture LSTM-based models to recover different kinds of temporal relations from text. Using the shortest dependency path between entities as input, the same architecture is implemented to extract intra-sentence, cross-sentence, and document creation time relations. A ``double-checking'' technique reverses entity pairs in classification, boosting the recall of positive cases and reducing misclassifications between opposite classes. An efficient pruning algorithm resolves conflicts globally. Evaluated on QA-TempEval (SemEval2015 Task 5), our proposed technique outperforms state-of-the-art methods by a large margin. We also conduct intrinsic evaluation and post state-of-the-art results on Timebank-Dense.
  
  %Although our model is not optimized on TimeBank-Dense dataset, which uses different methods for annotation and evaluation, it obtains new state-of-the-art results on this corpus as well.

  
  %It uses a relatively simple LSTM-based architect, and relies on shortest dependency paths in sentences. A ``double-checking" technique reverses entity pairs in classification, boosting the recall of positive cases and reducing misclassifications between opposite classes. An efficient pruning algorithm resolves conflicts globally. Running on SemEval2015 Task 5, our proposed method outperforms state-of-the-art methods by a large margin.


%  This paper proposes a method to annotate temporal relations from text documents. It uses a relatively simple LSTM-based architect, and relies on shortest dependency paths in sentences. A ``double-checking" technique reverses entity pairs in classification, boosting the recall of positive cases and reducing misclassifications between opposite classes. An efficient pruning algorithm resolves conflicts globally. Running on SemEval2015 Task 5, our proposed method outperforms state-of-the-art methods by a large margin.

\end{abstract}

\section{Introduction}
%Despite the recent advances in automated processing of natural language, approaching general human-level understanding of text in many cases still remains challenging. This paper addresses one such challenge: automatically extracting and understanding the order and timing of events described in natural language text.

Recovering temporal information from text is essential to many text processing tasks that require deep language understanding, such as answering questions about the timeline of events or automatically producing text summaries. This work presents intermediate results of an effort to build a temporal reasoning framework with contemporary deep learning techniques.

Until recently, there has been remarkably few attempts to evaluate temporal information extraction (TemporalIE) methods in context of downstream applications that require reasoning over the temporal representation.  One recent effort to conduct such evaluation was SemEval2015 Task 5, a.k.a. QA-TempEval \cite{Llorens2015:TempEval}, which used question answering (QA) as the target application.  QA-TempEval evaluated systems producing TimeML \cite{Pustejovsky03timeml:robust} annotation based on how well their output could be used in QA.  We believe that 
application-based evaluation of TemporalIE should eventually completely replace the intrinsic evaluation if we are to make progress, and therefore we evaluated our techniques mainly using QA-TempEval setup.  

Despite the recent advances produced by multi-layer neural network architectures in a variety of areas, the research community is still struggling to make neural architectures work for linguistic tasks that require long-distance dependencies (such as discourse parsing or coreference resolution).  Our goal was to see if a relatively simple architecture with minimal capacity for retaining information was able to incorporate the information required to identify temporal relations in text.  

Specifically, we use several simple LSTM-based components to recover ordering relations between temporally relevant entities (events and temporal expressions).  These components are fairly uniform in their architecture, relying on dependency relations recovered with a very small number of mature, widely available processing tools, and require minimal engineering otherwise. 
%
To our knowledge, this is the first attempt to apply such simplified techniques to the TemporalIE task, and we  demonstrate this streamlined architecture is able to outperform state-of-the-art results on a temporal QA task with a large margin.  

%conduct intrinsic evaluation on 
% we also evaluate it intrinsically using
In order to demonstrate generalizability of our proposed architecture, we also evaluate it intrinsically using TimeBank-Dense\footnote{\url{https://www.usna.edu/Users/cs/nchamber/caevo/##corpus}} \cite{chambers2014dense}.  TimeBank-Dense annotation aims to approximate a complete temporal relation graph by including all intra-sentential relations, all relations between adjacent sentences, and all relations with document creation time.  Although our system was not optimized for such a paradigm, and this data is quite different in terms of both the annotation scheme and the evaluation method, we obtain state-of-the-art results on this corpus as well.

%both the TimeBank-Dense annotation scheme and the evaluation method are quite different
%to fit the characteristics of such a paradigm. 

%there are quite different from QA-TempEval, and our system is not designed to fit the characteristics of such a paradigm. In fact we consider the intrinsic evaluation often inadequate given the poor inter-annotator agreement. Nevertheless it is helpful to compare our performance with existing systems.  \textsc{tlink} density and annotation methods

% Lesha:
% The TimeBank-Dense dataset is quite different from QA-TempEval in terms of both annotation scheme and evaluaion method. Nevertheless, the propsoed system establishes a new state-of-the art on the TimeBank-Dense as well.
% Note that we consider the intrinsic evaluation often inadequate given the poor inter-annotator agreement.

%In order to show the technique is generic, we also used the TimeBank-Dense\footnote{\url{https://www.usna.edu/Users/cs/nchamber/caevo/##corpus}} \cite{chambers2014dense} dataset to run our experiments. The annotation of training data and the evaluation method there are quite different from QA-TempEval, and our system is not designed to fit the characteristics of such a paradigm. In fact we consider the intrinsic evaluation often inadequate given the poor inter-annotator agreement. Nevertheless it is helpful to compare our performance with existing systems.

%%%%%%%%%%%

%The main contributions of this paper is to demonstrate this streamlined architecture is able to outperform state-of-the-art results on a temporal QA task.  To our knowledge, this is the first attempt to apply 


%When classifying relations between entities, we do not use any specialized attributes from the entities, instead we only collect the words.

%The main contributions of this paper are to propose ... and to show that ... % what?

%AR: we need a punchline here.  what's our punchline?  what's our main discovery / discoveries / contributions?
% maybe a model with simple input format can achieve better-than-stota results? no explicit complex representations, but distributed representations and unified models
% what do you mean by distributed representations?


%is a follow-up of the TempEval series in SemEval. TempEval always calls for systems to annotate events, time expressions (\textsc{timex}es) as well as their temporal relations (\textsc{tlink}s) from text documents, as defined in the TimeML standard \cite{Pustejovsky03timeml:robust}. 
%QA TempEval is unique in its evaluation methodology. The predicted annotations are not compared against the gold labels, as conventionally done in the series. Instead, based on the content of the documents, they constructed a set of yes-no questions and utilize a QA toolkit to find answers from the predicted annotations. A system's level of success then depends on the number of correct answers it can deliver.

%QA is a natural and convincing way to evaluate language understanding. 
%Every one of us who took reading comprehension exams in English class should agree. 
%On our way to build a temporal reasoning framework with contemporary deep learning techniques, we decided to run this task and compare our results against previous participants'. Our system utilizes a very small number of mature, widely available processing tools, such as tokenizers, parsers and \textsc{timex} annotators, and then use minimum




\section{Related Work}

A multitude of TemporalIE systems have been developed over the past decade both in response to the series of shared tasks organized by the community \cite{verhagen2007semeval,verhagen2010semeval,uzzaman2012tempeval,sun2013evaluating,bethard2015semeval,llorenssemeval,minardsemeval} and in standalone efforts \cite{chambers2014dense,DBLP:journals/corr/Mirza16}.
%
% have been influential inspirations of temporal reasoning research. These challenges asked participants to annotate temporal relations in different conditions, and evaluate the results with gold files. 
%

The best methods used by TemporalIE systems to date tend to rely on highly engineered task-specific models using traditional statistical learning, typically used in succession \cite{sun2013evaluating,chambers2014dense}.  For example, in a recent QA-TempEval shared task, the participants routinely used a series of classifiers (such as support vector machine (SVM) or  hidden Markov chain SVM) or hybrid methods combining hand crafted rules and SVM, as was used by the top system in that challenge \cite{hlt-fbk}.
%
While our method also relies on decomposing the temporal relation extraction task into subtasks, we use essentially the same simple LSTM-based architecture for different components, that consume a highly simplified representation of the input.

%For example, the FLT-FBK sytems, the winner of QA TempEval, used a hybrid of SVM classifiers and preprocessing rules \cite{hlt-fbk}.  

Although there has not been much work applying deep learning techniques to TemporalIE,  some relevant work has been done on a similar (but typically more local) task of relation extraction.  Convolutional neural networks \cite{Zeng:2014} and recurrent neural networks both have been used for argument relation classification and similar tasks \cite{DBLP:journals/corr/ZhangW15a,Xu2015,DBLP:journals/corr/VuAGS16}.  We take inspiration from some of this work, including specifically the approach proposed by \newcite{Xu2015} which uses syntactic dependencies.

%Finally, [move pruning lit. review here?]

%To our knowledge, however, there have not been many proposals of deep learning framework for temporal relations. This paper serves as an example in this direction. 

%Long short term memory (LSTM) \cite{Hochreiter:LSTM} is a popular RNN architecture to process time series. It has gating mechanisms to control forgetting, remembering and outputting values in memory, and has achieved the best results in many tasks. 

%The RNN models mentioned above all use LSTM. Our TEA system has LSTM units as essential components too.

\section{Dataset}

\iffalse
\begin{table*}
\begin{minted}[breaklines, breakanywhere, breaksymbolleft=, fontsize=\scriptsize]{xml}
Director of the U.S. Federal Bureau of Investigation (FBI) Louis Freeh <EVENT eid="e1" class="REPORTING">said</EVENT> here <\textsc{timex}3 tid="t2" type="\textsc{date}" value="1998-08-21" temporalFunction="false" functionInDocument="NONE">Friday</\textsc{timex}3> that U.S. air <EVENT eid="e45" class="OCCURRENCE">raid</EVENT> on Afghanistan and Sudan is not directly <EVENT eid="e2" class="OCCURRENCE">linked</EVENT> with the <EVENT eid="e46" class="OCCURRENCE">probe</EVENT> into the <\textsc{timex}3 tid="t3" type="\textsc{date}" value="1998-08-07" temporalFunction="false" functionInDocument="NONE">August 7</\textsc{timex}3> <EVENT eid="e47" class="OCCURRENCE">bombings</EVENT> in east Africa. 
...
<MAKEINSTANCE eventID="e1" eiid="ei1" tense="PAST" aspect="NONE" polarity="POS" pos="UNKNOWN"/> 
<MAKEINSTANCE eventID="e45" eiid="ei45" tense="NONE" aspect="NONE" polarity="POS" pos="NOUN"/> 
...
<\textsc{tlink} lid="l14" relType="\textsc{is_included}" eventInstanceID="ei1" relatedToTime="t2" origin="USER"/> 
<\textsc{tlink} lid="l19" relType="\textsc{after}" eventInstanceID="ei1" relatedToEventInstance="ei45" origin="USER"/> 
\end{minted}
\caption{An example of \textsc{timex} and event annotation in TimeML standard. The \textsc{tlink} lables show $e1$ ``said" is temporally included in $t2$ ``Friday", and after $e45$ ``raid".}
\label{tags}
\end{table*}

\fi

We used QA-TempEval (SemEval 2015 Task 5)\footnote{\url{http://alt.qcri.org/semeval2015/task5/}} data and evaluation methods in our experiments. The training set contains 276 annotated TimeML files, mostly news articles from major agencies or Wikinews %, all in English language and dated 
from late 1990s to early 2000s. %Table \ref{tags} shows an example of tagged text. Eventually we need to generate such tags from raw text files.
This data contains annotations for events, temporal expressions (referred to as \textsc{timex}es), and temporal relations (referred to as \textsc{tlink}s).
%
The test set contains unannotated files in three genres: 10 news articles composed in 2014, 10 Wikipedia articles about world history, and 8 blogs entries from early 2000s. 

%In QA-TempEval, evaluation is done via a QA toolkit which contains yes/no questions about event-event or event-temporal expression (event-\textsc{timex}) pairs. %If the annotations of time expressions, events, and 

In QA-TempEval, evaluation is done via a QA toolkit which contains yes/no questions about temporal relations between two events or an event and a temporal expression. 
%
QA evaluation is not available for most of the training data except for 25 files, for which 79 questions are available.  We used used this subset of the training data for validation.
%
%If the annotations of time expressions, events, and \textsc{tlink}s are correct, 
%If the annotations of time expressions, events, and \textsc{tlink}s are correct, we should be able to answer the questions. 
The test set contains unannotated files, so QA is the only way to measure the performance. The total of 294 questions is available for the test data, see Table~\ref{test-data}. 
%
%For the test data and QA set statistics, see Table~\ref{test-data}. 
%
%QA evaluation is not available for most of the training data except for 25 files, which we used as our validation set. 
%All the model selection, hyper-parameter selection and so on are based on results from this set. After fully developing the models, we performed evaluations on the test set.
%

We also use TimeBank-Dense dataset, which contains  
%The documents in TimeBank-Dense dataset are 
a subset of the documents in QA-TempEval. In TimeBank-Dense, all entity pairs in the same sentence or in consecutive sentences are labeled. If there is no information about the relation between two entities, it is labeled as ``vague''. We follow the experimental setup in \cite{chambers2014dense}, which splits the corpus into training/validation/test sets of 22, 5, and 9 documents, respectively.
%in which the TimeBank-Dense corpus is split into a 22 document training set, a 5 document validation set and a 9 document test set. 

\begin{figure*}[ht]

\begin{center}
% \includegraphics[width=0.8\linewidth, clip, trim= 1cm 4.5cm 4cm 6cm]{system2.pdf}
% \fbox{
\includegraphics[width=0.8\linewidth, clip, trim=0.5cm 0cm 0.5cm 0.8cm]{system2_v2.pdf}
% }
\end{center}
\vspace{-1.5em}
\caption{System overview for our temporal extraction annotator (TEA) system}

\label{fig:system}

\end{figure*}

%\subsection{Intra-Sentence Model}
%\label{sect:within}

\section{\textsc{Timex} and Event Extraction}

The first task in our TemporalIE pipeline (TEA) is to identify time expressions (\textsc{timex}es) and events in text. We utilized the HeidelTime package \cite{StroetgenGertz2013:LREjournal} to identify \textsc{timex}es.
%
%Results of \textsc{timex} tagging on the validation set are summarized in Table \ref{entity-tags}.
%
\iffalse
\subsection{\textsc{timex} Extraction}
\textsc{timex} extraction has been well studied and we believe some publicly available tools sufficiently suit our purpose for now. We utilized the HeidelTime package \cite{StroetgenGertz2013:LREjournal} to annotate \textsc{timex} tags. HeidelTime can also perform time normalization with respect to document creation time. \textsc{timex} tags belong to three major classes: \textsc{date}, \textsc{time} and \textsc{duration}, and the majority in our training data belong to the \textsc{date} class. We evaluate the result of \textsc{timex} tagging on the validation set, and the results are summarized in Table \ref{entity-tags}. Since we did not develop the \textsc{timex} annotator, the evaluation serves to check the quality of the HeidelTime toolkit.
\fi
%
%\subsection{Event Extraction}
%
%\label{sect:event}
%
We trained a neural network model to identify event mentions.  
Contrary to common practice in TemporalIE, our models do not rely on event attributes, and thus we did not attempt to identify them.
%are not used in our \textsc{tlink} model

%In order to extract event entities from text, we trained a neural network model. Our purpose is to identify where the words describing the events (event mentions) are, so the \textsc{tlink} classification model can get correct input. Besides their locations in the text, we do not use any specific attributes from the event mentions in later processes. However, we do need some preprocessing to generate features to feed in the event extraction model.

\begin{table}[ht]
\begin{center}
\resizebox{\hsize}{!}{
\begin{tabular}{|l|l|}
\hline \bf Feature & \bf Explanation \\ \hline
is\_main\_verb & whether the token is the main verb of a sentence \\
is\_predicate & whether the token is the predicate of a phrase \\
is\_verb & whether the token is a verb \\
is\_noun & whether the token is a noun \\
\hline
\end{tabular}
}
\end{center}
\vspace{-1em}
\caption{\label{token-features} Token features for event extraction }
\end{table}

We perform tokenization, part-of-speech tagging, and dependency parsing using  NewsReader \cite{Agerri2014:newsreader}. Every token is represented with a set of features derived from preprocessing. 
%
Syntactic dependencies are not used for event extraction, but are used later in the pipeline for \textsc{tlink} classification.
%
The features used to identify events are listed in Table \ref{token-features}. 
% Lesha rewrite
% Event extractor does not use syntactic dependencies, but they are used later in \textsc{tlink} classification. 
 %In the dataset, temporal relations are called \textsc{tlink}s.

%TEA’s preprocessing is implemented with NewsReader \cite{Agerri2014:newsreader}. The IXA-pipelines perform tokenization, part of speech tagging, and dependency tree parsing. After that, a dependency tree is constructed for every sentence. Every token is also represented with a set of features. Some of these features are used to identify events. TEA's event extractor does not depend on syntactic structures, but the parsed trees are useful in later processes of \textsc{tlink} classification. 

%The extraction model has two components. One part is an LSTM layer which takes word embeddings as input and generates output to a hidden layer. The other component takes 4 token-level features as input, and generates output to a hidden layer. The two hidden layers are concatenated, and jointly connected to an output layer which performs binary classification. The specifics of the system is discussed later. 

The event extraction model uses long short-term memory (LSTM) \cite{Hochreiter:LSTM}, an RNN architecture well-suited for sequential data. %It has gating mechanisms to control forgetting, remembering and outputting values in memory, and has achieved the best results in many tasks. 
%
The extraction model has two components, as shown on the right of Figure \ref{fig:rnn_model}. One component is an LSTM layer which takes word embeddings as input. The other component takes 4 token-level features as input. These components produce hidden representations which are concatenated, and fed into an output layer which performs binary classification. %The specifics of the system is discussed later. 
%
For each token, we use four tokens on each side to represent the surrounding context. The resulting sequence of nine word embeddings is then used as input to an LSTM layer. If a word is near the edge of a sentence, zero padding is applied.
%to maintain the dimensionality of input. 
We only use the token-level features of the target token, and ignore those from the context words. The 4 features are all binary, as shown in Table \ref{token-features}.
%
Since the vast majority of event mentions in the training data are single words, we only mark single words as event mentions. 

%The results are also evaluated on the validation dataset. Section \ref{experiments} has more details. 


%The results are also evaluated on the validation dataset. Section \ref{experiments} has more details. Currently, we only mark single words as event mentions. In the training data and validation data, the vast majority event mentions are single words too.

\section{\textsc{Tlink} Classification}
\label{sec:tlink-classification}

Our temporal relation (\textsc{tlink}) classifier consists of four components: an LSTM-based model for intra-sentence entity relations, an LSTM-based model for cross-sentence relations, another LSTM-based model for relations with document creation time, and a rule-based component for \textsc{timex} pairs. The four models perform \textsc{tlink} classifications independently, and the combined results are fed into a pruning module to remove the conflicting \textsc{tlink}s. 
%
The three LSTM-based components use the same streamlined architecture over token sequences recovered from shortest dependency paths between entity pairs.

\begin{figure}[ht]
\begin{center}
%\fbox{
\includegraphics[width=1.0\linewidth, clip, trim=1.5cm 1.3cm 2.3cm 1cm]{system1.pdf}
%}
\end{center}
\vspace{-1.5em}
%\caption{Architectures of neural network model. Left: intra-sentence and cross-sentence model. Right: Event extraction model.}
\caption{Model architecture. Left: intra-sentence and cross-sentence model. Right: Event extraction model.}
\label{fig:rnn_model}
\end{figure}

\subsection{Intra-Sentence Model}
\label{sect:within}
%Often times, the temporal relation between two entities is unambiguously expressed in a sentence, and is interpretable by readers without knowing any external context. Based on this assumption, we design a model to classify the \textsc{tlink}s involving (event, event) pairs and (event, \textsc{timex}) pairs within the same sentence. The \textsc{timex} pairs (\textsc{timex}, \textsc{timex}) are not included here, because they will be handled separately.

%Natural language has regular patterns to indicate temporal relations. Such a pattern can be phrases with temporal prepositions, or clauses with certain conjunctions, and so forth. A successful NLP model should be able to recognize such patterns, by identifying crucial lexical items and/or the syntactic structures. %Such an intuition suggests that encoding the syntactic relations between entities can be helpful.

%%%%%%%%%%% REMOVE THIS PARA if needed
%A \textsc{tlink} extraction model should be able learn the patterns that indicate temporal relations, such as  phrases with temporal prepositions or clauses with specific conjunctions.  This intuition suggests that such models may benefit from encoding syntactic relations, rather than a linear sequences of lexical items.

A \textsc{tlink} extraction model should be able to learn the patterns that correspond to specific temporal relations, such as specific temporal prepositional phrases and clauses with temporal conjunctions.  This suggests such models may benefit from encoding syntactic relations, rather than linear sequences of lexical items.

%Following other work in relation extraction, 
We use the shortest path between entities in a dependency tree to capture the essential context.  Using the NewsReader pipeline, we identify the shortest path, and use the word embeddings for all tokens in the path as input to a neural network.  
%
Similar to previous work in relation extraction \cite{Xu2015}, we use two branches, where the left branch processes the path from the source entity to the least common ancestor (LCA), and the right branch processes the path from the target entity to the LCA.
%
However, our \textsc{tlink} extraction model uses only word embeddings as input, not POS tags, grammatical relations themselves, or WordNet hypernyms.

For example, for the sentence ``Their marriage ended before the war'', given an event pair ({\em marriage}, {\em war}), the left branch of the model will receive the sequence ({\em marriage, ended}), while the right branch will receive ({\em war, before, ended}).   
%
The LSTM layer processes the appropriate sequence of word embeddings in each branch.  This is followed by a separate max pooling layer for each branch, so for each LSTM unit, the maximum value over the time steps is used, not the final step value.
%This is followed by a max pooling layer on top of each branch. The max pooling goes through the time steps of a sequence, and obtains the maximum value from each LSTM unit, as opposed to use the value in the final step. 
%Max pooling is used in \cite{Xu2015} as well, and our experiment also shows it improves the results.
During the early stages of model design, we observed that this max pooling approach (also used in \newcite{Xu2015}) resulted in a slight improvement in performance.
%
Finally, the results from the max pooling layers of both branches are concatenated and fed to a hidden layer, followed by a softmax to yield a probability distribution over the classes.
The model architecture is shown in Figure \ref{fig:rnn_model} (left).
%
We also augment the training data by flipping every pair, 
% Lesha rewrite
% i.e. if $(e_1, e_2)~\rightarrow$~\textsc{before}, it is guaranteed that $(e_2, e_1)~\rightarrow$~\textsc{after} is also present. 
i.e. if $(e_1, e_2)~\rightarrow$~\textsc{before}, $(e_2, e_1)~\rightarrow$~\textsc{after} 
%will be also present. 
is also included.


%The entity pairs in \textsc{tlink}S from training data are not constructed in any particular order. For instance, if $e_1$ and $e_2$ map to a certain relation, we do not know whether $e_1$ or $e_2$ appears first in the training file. This seems to add some randomness to the system, especially if the distributions of the two orders are unbalanced. However, in our implementation, the training data is augmented so that every pair is flipped. If we have $(e_1, e_2)\rightarrow$ \textsc{before}, it is guaranteed that $(e_2, e_1)\rightarrow$ \textsc{after} is also in the training instances. 






%The resulting model is shown in Figure \ref{fig:rnn_model} (left).


%syntactic relations. In their model, they construct a dependency tree for each sentence, and the shortest path connecting two entities represents the argument structure. %For example, given the sentence ``a trillion gallons of water have been poured into an empty region of outer space", suppose we want to know the relation between $water$ and $region$. After parsing the sentence, we can find their common root is the word $poured$. The path from $water$ to $poured$ is $water\rightarrow of\rightarrow gallons\rightarrow poured$, and the path from $region$ to $poured$ is $region\rightarrow into\rightarrow poured$. With these two paths, hopefully, a model can be trained to tell their semantic relation is \textsf{Entity-Destination}.   
%We assume the strategy can extent to temporal relations, too. After finding the paths, the word embeddings of all tokens on the paths are employed as input to a neural network. Again, we utilized NewsReader pipelines to parse text. Table \ref{pair-examples} shows some examples. 



%The neural network model here is also similar to the one in \cite{Xu2015}. However, we simplified it and only used word embeddings, not other ``channels" mentioned in the article. 

%The system has two branches. The left branch processes the path from the source entity to the root, while the right branch processes the path from the target entity to the root. A root is not necessarily the root of a sentence, but is the lowest common ancestor. %For example, if both entities are in the same preposition phrase, then the root could be the preposition heading the phrase. 

%Again, we utilized NewsReader pipelines to parse text. 
%Table \ref{pair-examples} shows some examples. 


%The neural network model here is also similar to the one in \cite{Xu2015}. However, we simplified it and only used word embeddings, not other ``channels" mentioned in the article. The system has two branches. The left branch processes the path from the source entity to the root, while the right branch processes the path from the target entity to the root. A root is not necessarily the root of a sentence, but is the lowest common ancestor. %For example, if both entities are in the same preposition phrase, then the root could be the preposition heading the phrase. 


\iffalse

\begin{table}
\begin{minted}[breaklines, breakanywhere, breaksymbolleft=, fontsize=\scriptsize]{xml}
In <EVENT eid="e5">speeches</EVENT> before the signing <EVENT eid="e6">ceremony</EVENT>, the ministers <EVENT eid="e7">said</EVENT> their countries <EVENT eid="e8">saw</EVENT> NATO membership as an assurance of security and recognition of their rightful place in Europe. 
Kavan <EVENT eid="e9">said</EVENT> the Czech Republic would no longer <EVENT eid="e10">become</EVENT> "the powerless victim of a foreign invasion."
\end{minted}
\footnotesize
Left and right paths between entities: \\
$(e_5, e_6)$: speeches before ceremony, ceremony \\
$(e_5, e_7)$: speeches In said, said \\
$(e_6, e_{10})$: ceremony before speeches In said, become would said \\
$(e_7, e_{10})$: said, become would said
\caption{Examples of shortest paths on dependency tree. Top two are intra-sentence pairs and the rest are cross-sentence pairs. The commas separate left branches from right branches. The paths are bottom-up, and do not follow natural word order.}
\label{pair-examples}
\end{table}
\fi 


\subsection{Cross-Sentence Model}
\label{sect:cross}

\textsc{Tlink}s between the entities in consecutive sentences can often be identified without any external context or prior knowledge. For example, the order of events may be indicated by discourse connectives, or the events may follow natural order, potentially encoded in their word embeddings. 

%Sometimes, it is also possible to figure out the temporal relations between two entities in consecutive sentences without any external context or prior knowledge. English has certain adverbs and conjunctions to signify such relations.
%, such as $consequently$, $then$, $meanwhile$. 
%In addition, some events follow natural orders, and their word embeddings may have encoded it. Therefore, we also build a neural network to model cross-sentence entities.

To recover such relations, we use a model similar to the one used for intra-sentence relations, as described in Section\ref{sect:within}. 
%
Since there is no common root between entities in different sentences, we use the path between an entity and the sentence root to construct input data. A sentence root is often the main verb, or a conjunction. 

%However, there is no common root between entities in different sentences, and thus there is no shortest path either. Instead, we use the path between an entity and the sentence root to construct input data. A sentence root is often the main verb, or some conjunction word. 
%Table \ref{pair-examples} has an example.

%It should be noted that most of the time, the temporal relations between cross-sentence entities are vague without knowing the broader context.  On the one hand, we should use sufficient negative instances (\textsc{no-link} relations) for training; and on the other hand, it is helpful to purge weak results at the end, which we will discuss later.

\subsection{Relations to DCT}
\label{dct}
%Every narrative refers to a time as its ``current time", and events are more or less organized around it. 
The document creation time (DCT) naturally serves as the ``current time''. In this section, we discuss how to identify temporal relations between an event and DCT. The assumption here is that an event mention and its local context can often suffice for DCT \textsc{tlink}s. For example, English 
%requires verbs to be 
has inflected verbs for tense in finite clauses, and uses auxiliaries to express aspects. %These are all strong indicators of DCT relations.

%Identifying DCT and linking it with events and time expressions in the text is a major step of understanding the content, and for our purpose, it is also a component of \textsc{tlink} classification. 

%The relation between DCT and other time expressions is just a special case of \textsc{timex} \textsc{tlink} classification, which has been discussed in Section\ref{sect:\textsc{timex}}. 

%show its relation to 
%From a linguistics point of view, this is largely true. 
The model we use is again similar to the one in Section\ref{sect:cross}. %We find the path from every event mention to its sentence root, and use the word embeddings on this path as input. On top of the input layer, there is an LSTM layer, which connects to a hidden layer. At the end, a softmax layer generates output. 
%but only one branch should be enough because only one entity is mentioned in text. However 
Although one branch would suffice in this case, we use two branches in our implementation. One branch processes the path from a given entity to the sentence root, and the other branch processes the same path in reverse, from the root to the  entity. %Again, we found the training files usually do not contain many \textsc{tlink}s between events and DCT, even if the temporal relations are clear. 
%In spite of that, we hope the patterns are relatively easy to learn even if training data does not appear to be abundant. %When misclassification occurs, most likely the confusion involves \textsc{no-link}, which is less harmful than confusing \textsc{before} with \textsc{after} or \textsc{simultaneous}, for example. 

%Besides using the path from a dependency tree, we also tried a moving window like in Section\ref{sect:event}. The results are very similar.

\subsection{Relations between \textsc{timex}es}
\label{sect:timex}
Time expressions explicitly signify a time point or an interval of time. Without the \textsc{timex} entities serving as ``hubs'', many events would be isolated from each other.  We use rule-based techniques to identify temporal relations between \textsc{timex} pairs that have been identified and normalized by HeidelTime.  
%Once labeled, the temporal relations between \textsc{timex} pairs can be identified using rule-based techniques. 
The relation between the DCT and other time expressions is just a special case of \textsc{timex}-to-\textsc{timex} \textsc{tlink} and is handled with rules as well. %and do not demand sophisticated NLP techniques. %However, it is crucial to find the relations in order to figure out the relations between events in a document. As described above, we have intra-sentence and cross-sentence models to link each time expression with its surrounding events. If we can link all the \textsc{timex} entities, regardless of their distances in the text, we will be able to build \textsc{tlink}s between events that have long distances in the text. 

%\iffalse
\begin{table}[h]
\begin{center}
%\footnotesize
\resizebox{\columnwidth}{!}{
\begin{tabular}{|l|l|l|}
\hline \bf \textsc{date} value & \bf Calculation & \bf Representation\\ \hline
%2016-08 & START = $2016+7/12$ & (2016.583, 2016.665)\\
%        & $=2016.583$ & \\
%           & END = $2016+7/12+30/365$ & \\
%        & $=2016.665$ & \\    \hline
2017-08-04 & START = $2017+7/12+3/365$ & (2017.591, 2017.591)\\
        & $=2017.591$ & \\ 
           & END = START & \\ \hline
%2016-Q3 & START = $2016+6/12=2016.5$ & (2016.5, 2016.75)\\
%          & END = $2016+9/12=2016.75$ & \\ \hline
2017-SU & START = $2017+5/12=2017.416$ & (2017.416, 2017.666)\\
(Summer 2017)  & END = $2017+8/12=2017.666$ & \\ \hline
%BC221 & START = $-221$ & (-221, -220.003)\\
%           & END = $-221+364/356$ & \\ 
%           & $=-220.003$ & \\ 
%\hline
\end{tabular}
}
\end{center}
\caption{\label{tab:data-values} Examples of \textsc{date} values and their tuple representations }
\end{table}
%\fi

In the present implementation, we focus on the \textsc{date} class of \textsc{timex} tags, which is prevalent in the newswire text. The \textsc{time} class tags which contain more information are converted to \textsc{date}. Every \textsc{date} value is mapped to a tuple of real values (\textit{start}, \textit{end}). The ``value'' attribute of \textsc{timex} tags follows the ISO-8601 standard, so the mapping is straightforward. Table \ref{tab:data-values} provides some examples. 
We set the minimum time interval to be a day.
%, so any time intervals smaller than a day will be ignored. We use the beginning of the day to represent a specific date. 
Practically, such a treatment suffices for our data.  After mapping \textsc{date} values to tuples of real numbers, we can define 5 relations between \textsc{timex} entities $T_1=(start_1, end_1)$ and $T_2=(start_2, end_2)$ as follows:

\begin{equation}\label{timex-relations}
\resizebox{0.8\hsize}{!}{$
    T_1\times T_2\rightarrow
    \begin{cases}
        \text{\textsc{before} }  & \text{if } end_1<start_2 \\
        \text{\textsc{after} }  & \text{if } start_1>end_2 \\
        \text{\textsc{includes} }  & \text{if } start_1<start_2 \\
                            & \text{ and } end_1>end_2 \\
        \text{\textsc{is\_included} }  & \text{if } start_1>start_2 \\
                            & \text{ and } end_1<end_2 \\
        \text{\textsc{simultaneous} }  & \text{if } start_1=start_2 \\
                            & \text{ and } end_1=end_2
    \end{cases} $
    }
\end{equation}

The \textsc{tlink}s from training data contain more types of relations than the five described in Equation  \ref{timex-relations}. 
However relations such as \textsc{ibefore} (``immediately before"), \textsc{iafter}(``immediately after") and \textsc{identity} are only used on event pairs, not \textsc{timex} pairs. The QA system also does not target questions on \textsc{timex} pairs. The purpose here is to use the \textsc{timex} relations to link the otherwise isolated events.  


%For example, there are \textsc{ibefore} (``immediately before"), \textsc{iafter}(``immediately after") and \textsc{identity}. However, these relations are generally used on event pairs, not \textsc{timex} pairs. The QA system does not contain questions on \textsc{timex} pairs either. The purpose here is to use the \textsc{timex} relations to link the otherwise isolated events.  



\section{Double-checking}
A major difficulty we have is that the \textsc{tlink}s for intra-sentence, cross-sentence, and DCT relations in the training data are not comprehensive. Often, the temporal relation between two entities is clear, but the training data provides no \textsc{tlink} annotation.
%
We downsampled the \textsc{no-link} class in training in order to address both the class imbalance and the fact that TimeML-style annotation is de-facto sparse, with only a fraction of positive instances annotated.

In addition to that, we introduce a technique to boost the recall of positive classes (not \textsc{no-link}) and to reduce the misclassification between the opposite classes.  Since entity pairs are always classified in both orders, if both orders produce a \textsc{tlink} relation, rather than \textsc{no-link}, we adopt the label with a higher probability score, as assigned by the softmax classifier. We call this technique ``double-checking". It serves to reduce the errors that are fundamentally harmful (e.g. \textsc{before} misclassified as \textsc{after}, and vice versa). 
%
We also allow a positive class to have the ``veto power'' against \textsc{no-link} class. 
%For instance, if our model predicts $(e_1, e_2)\rightarrow \text{\textsc{no-link}}$ but $(e_2, e_1)\rightarrow \text{\textsc{after}}$, then we adopt the result $(e_2, e_1)\rightarrow \text{\textsc{after}}$. 
For instance, if our model predicts $(e_1, e_2)\rightarrow \text{\textsc{after}}$ but \textsc{no-link} reversely, we adopt the former.

%We introduce a technique to boost the recall of positive classes and reducing misclassifications among opposite classes.  The goal is to reduce the errors that are fundamentally harmful e.g. \textsc{before} misclassifed as \textsc{after}, and vice versa. we also allow a positive class to have the ``veto power" against \textsc{no-link} class. For instance, if our model predicts $(e_1, e_2)\rightarrow \textsc{no-link}$ but $(e_2, e_1)\rightarrow \textsc{after}$, then we adopt the result $(e_2, e_1)\rightarrow \textsc{after}$. Entity pairs are always classified in both orders, and if both results are positive (not \textsc{no-link}), we adopt the one with a higher probability score, which is delivered by the softmax classifier. We call this technique ``double-check". 

\begin{table}[h]
\begin{center}
% \resizebox*{\hsize}{2cm}{
\resizebox{\columnwidth}{!}{
\begin{tabular}{|@{} l|l|l|l|l @{}|}
\hline 
\bf \textsc{no-link} ratio & \bf Recall & \bf Recall & \bf \textsc{before} & \bf \textsc{after} \\
\bf               & \bf \textsc{before} & \bf \textsc{after} & \bf  as \textsc{after} & \bf as \textsc{before}\\
\hline
0.5  & 0.451 & 0.445 & 0.075 & 0.092\\
0.1  & 0.643 & 0.666 & 0.145 & 0.159\\
% 0.1 \textsc{no-link} ratio &       &       &       &      \\
0.1 + double-check & 0.721 & 0.721 & 0.125 & 0.125\\
\hline
\end{tabular}
}
\end{center}
\vspace{-1em}
\caption{\label{witin-exp} 
Effects of downsampling and double-checking on intra-sentence results. 0.5 \textsc{no-link} ratio means that \textsc{no-link}s are downsampled to a half of the number of all positive instances combined. \textsc{Before} as \textsc{after} shows the fraction of \textsc{before} misclassified as \textsc{after}, and vice versa.}

\end{table}

Table \ref{witin-exp} shows the effects of double-checking and downsampling the \textsc{no-link} cases on the intra-sentence model.  
%Both downsampling the \textsc{no-link} cases boosts the recall of positive classes. 
Double-checking technique not only further boosts recall, but also reduces the misclassification between the opposite classes. 



\section{Pruning \textsc{Tlink}s}
\label{pruning}
The four \textsc{tlink} classification models in Section \ref{sec:tlink-classification} deal with different kinds of \textsc{tlink}s, so their output does not overlap. Nevertheless temporal relations are transitive in nature, so the deduced relations from given \textsc{tlink}s can be in conflict.% to each other. % Since our neural network models are essentially bottom-up, ignoring the bigger context when drawing pairwise relations, there must be a way to globally resolve the low-level errors in order to yield a well-formed result.

Most conflicts arise from two types of relations, namely \textsc{before}/\textsc{after} and \textsc{includes}/\textsc{is\_included}. Naturally, we can convert \textsc{tlink}s of opposite relations and put them all together. If we use a directed graph to represent the \textsc{before} relations between all entities, it should be acyclic.
%there should not is not supposed to be any cycle. %Therefore, the problem can be reduced to removing edges in a directed graph, according to some criterion of optimality, to yield a directed acyclic graph. 
Sun \shortcite{Sun:2014} proposed a strategy that ``prefers the edges that can be inferred by other edges in the graph and remove the ones that are least so". %Basically, if there is a edge between nodes $A$ and $B$, a score 1 is assigned. If there is another path $A\rightarrow C \rightarrow B$, then an additional score 1/2 is assigned. It is divided by 2 because the length of that path is 2. 
Another strategy is to use the results from separate classifiers or ``sieves'' to rank \textsc{tlink}s according to their confidence \cite{mani2007three,chambers2014dense}. High-ranking results overwrite low-ranking ones.

%We also share the intuition to purge weak \textsc{tlink}s and retain strong ones. Since the softmax layer can provide, a probability score for each classification, we can use that score to represent the strength of a link. \textsc{tlink}s between \textsc{timex} pairs are generated by rules, and thus we can assume they are very reliable and assign a value 1 to each of them. 

We follow the same idea of purging the weak \textsc{tlink}s. Given a directed graph, our approach is to remove the edges to break cycles, so that the sum of weights from the removed edges is minimal. %This problem is formulated as follows: given a directed weighted graph, find the maximum acyclic subgraph. 
This problem is actually an extension of the minimum feedback arc set problem and is NP-hard \cite{Karp:1972}.
%
We therefore adopt a heuristic-based approach, applied separately to the graphs induced by \textsc{before}/\textsc{after} and \textsc{includes}/\textsc{is\_included} relations.\footnote{We found that \textsc{ends} and \textsc{begins} \textsc{tlink}s are too infrequent to warrant a separate treatment.} 
%
The softmax layer provides a probability score for each relation class, which represents the strength of a link. \textsc{Tlink}s between \textsc{timex} pairs are generated by rules, so we assume them to be reliable and assign them a score of 1. 
%
Although \textsc{includes}/\textsc{is\_included} edges can generate conflicts in a \textsc{before}/\textsc{after} graph as well, we currently do not resolve such conflicts because they are relatively rare. We also do not use \textsc{simultaneous/identity} relations to merge nodes, because we found that it leads to very unstable results.
%It is even unclear whether a human writer or reader always maintains perfect time graphs. 
%The softmax layer provides a probability score for each relation class, which represents the strength of a link. \textsc{Tlink}s between \textsc{timex} pairs are generated by rules, so we assume them to be reliable and assign them a score of 1. 

\begin{algorithm}[ht!] 
\footnotesize
 $X\gets$ EVENTS\; $V\gets$ TIMEXes\; $E\gets$ TIMEX pairs\;
 Initialize $G\gets <V, E>$\;
  \For{x$\in$ X}{
    $V'\gets V+\{x\}$\;
    $C \gets \{(x,v) \cup (v,x) | v\in V\}$ \;
    $E'\gets E\cup C$ \;
    $G'\gets <V',E'>$ \;
    %$G\gets G\cup C$\;
    \If{cycle$\_$exists(G')}{
    \For{$C_i \in \pi(C)$}{
      $score_i=0$\; 
     \While{$C_i\neq \phi \text{ \& } cycle\_exists(G\cup C_i)$}{
    $c\gets C_i.pop()$\;
    $score_i +=weight(c)$\;
    }
    }
       }
    $G\gets G\cup C_i$ s.t. $i=argmin(score_i)$\;
  }
  \caption{\small Algorithm to prune edges. $\pi(C)$ denotes some permutations of $C$, where $C$ is a list of weighted edges.} % (candidates).} %We also guarantee that a list sorted in ascending order of weights is in the permutations.}
  \label{alg:pruning}
\end{algorithm}


For a given relation (e.g., \textsc{before}), we incrementally build a directed graph with all edges representing that relation.  We first initialize the graph with  \textsc{timex}-to-\textsc{timex} relations.
%
Event vertices are then added to this graph in a random order.
%
For each event, we add all edges associated with it. If this creates a cycle, the edges are removed one by one until there is no cycle, keeping track of the sum of the scores associated with removed edges.  We choose the order in which the edges are removed to minimize that value.\footnote{By removing an edge, we mean resetting the relation to \textsc{no-link}. Another possibility may be to set the relation associated with the edge to the one with the second highest probability score, however this may create additional cycles.}  The algorithm is shown above.
%Please see Algorithm \ref{alg:pruning} above.


%For simplicity we just reset it to \textsc{no-link}.

%Another consideration is the order in which events are added to the graph.  We have attempted several strategies: adding the events in the narrative order, adding the events that are associated with the most \textsc{tlink}s first, and the random order.  We find that these strategies do not improve performance over the random-order strategy.

%AR: REALLY, TO CLAIM THIS, WE NEED A TABLE SHOWING IT

%we generate all permutations of edges in that cycle, and then try removing the edges in the order corresponding to each %permutation.
%until there is no the cycle, 
%The edges are removed in a random order, keeping track of the sum of their scores. 
%then if necessary, drop the edge(s) 
%to make sure the graph remains acyclic.  The edges are dropped 
%The edges are removed in a random order, keeping track of the sum of their scores. 
%randomly select the order in which edges are removed, 
%keeping track of the softmax-generated score for each removed edge, summing the scores.  The set of edges associated with the %smallest overall score is then dropped.  
%

%In each step, the candidates to be dropped are the new edge we just added, as well as its neighboring edges in the growing graph. The candidates are removed one by one, until there is no cycle. As a randomized approach, we randomly permute the order of the candidates in $N\times (N-1)$ ways, but make sure the permutation corresponding to the greedy approach is included. In other words, besides other possible ways, we will always try the case in which the weakest edge is removed first, and so on. The algorithm is described in below

%resolves the conflict is then removed from the graph.
 
 
%The heuristic we adopt is a combination of greedy and randomized algorithms. Taking \textsc{before} relation as an example, we incrementally build a directed graph with all edges representing \textsc{before} relation. In each step, when necessary, we drop edge(s) to make sure the graph remains acyclic. In each step, the candidates to be dropped are the new edge we just added, as well as its neighboring edges in the growing graph. The candidates are removed one by one, until there is no cycle. As a randomized approach, we randomly permute the order of the candidates in $N\times (N-1)$ ways, but make sure the permutation corresponding to the greedy approach is included. In other words, besides other possible ways, we will always try the case in which the weakest edge is removed first, and so on. The algorithm is described in below.


%Note that in many cases the greedy approach which would first attempt to drop the edges with the smallest weights suffices, however, in our experiments, we found that attempting more permutations produces better overall performance. 
In practice, the vertices do not have a high degree for a given relation, so permuting the candidates $N\times(N-1)$ times (i.e., not fully), where $N$ is the number of candidates, 
%(not a full permutation) 
produces only a negligible slowdown. We also make sure to try the greedy approach, dropping the edges with the smallest weights first.

%We add the events to the graph in a random order, but first initialize the graph with all \textsc{timex} relations (each with weight 1.0).  
%
%In preliminary experiments, we found no evidence that adding events in the narrative order or adding the events associated with the most \textsc{tlink}s first produces an improvement over the random-order strategy.

%In this algorithm, the events to be added in the graph follow no particular order, except that we initialize the graph with all \textsc{timex} relations (each with weight 1.0). Intuitively, it might be a good idea to add events in narrative order, following their order in the text. Another seemingly good idea is to add events with the highest number of \textsc{tlink}s first. We still need more experiments to draw a conclusion, but currently we have not found a particular order has any deterministic effect on the results.  



%\section{Experiments}
\section{Model Settings}
\label{experiments}
%AR: REMOVED
%Each model involves a number of hyperparameters. It is impossible to perform a full grid search, but we refer to previous research as starting points, and vary the hyperparameters to see the effects. 

%Our major goal is to deliver a new technique to solve the problem and outperform the status quo, so finding the exact optimal configuration is of less consideration for now.

In this section, we describe the model settings used in our experiments.
%
All models requiring word embeddings use 300-dimensional word2vec vectors trained on Google News corpus (3 billion running words).\footnote{\url{https://github.com/mmihaltz/word2vec-GoogleNews-vectors}} 
%for all models requiring word embeddings. It was pre-trained on Google News corpus (3 billion running words), with the word2vec model. 
%It contains 3 million English words and each word vector has a dimensionality of 300. 
Our models are written in Keras on top of Theano. 
%To save space, 
%We report all model hyperparameters
%in the supplementary materials.
%, and trained and tested using GTX1080 GPU.
%Our neural network models are written in Keras on top of Theano, Training and testing run on a GPU-enabled work station. 

% AR: REMOVED 
%This section will describe our experiments on the QA-TempEval first, and then describe two other baselines to compare with. One is on the same task but using flat context as input, and the other is on TimeBank-Dense. 

% AR: MOVE IT SOMEWHERE?
%We first report our system's performance on the QA-TempEval, and compare it against the baseline that uses flat context as input.  We then report our system's performance on TimeBank-Dense.  

\paragraph{\textsc{Timex} and Event Annotation}
%\subsection{\textsc{timex} and Event Annotation}
%We used the HeidelTime package without any modification. 

%we remove the \textsc{timex} tags from the validation files, and then annotate them with HeidelTime. The results are then compared with the true tags. When comparing results, we only judge whether the same \textsc{timex} tag is put in the same position, and the tag attributes are ignored. Partial overlap is considered wrong. The evaluation result is shown in Table \ref{entity-tags}. 


%\subsection{Event Annotation}
The LSTM layer of the event extraction model contains 128 LSTM units. The hidden layer on top of that has 30 neurons. The input layer corresponding to the 4 token features is connected with a hidden layer with 3 neurons. The combined hidden layer is then connected with a single-neuron output layer. We set a dropout rate 0.5 on input layer, and another drop out rate 0.5 on the hidden layer before output. 
%

As mentioned earlier, we do not attempt to tag event attributes.
%No attribute tagging is attempted.
%The evaluation is also shown in Table \ref{entity-tags}. 
Since the vast majority of tokens are outside of event mention boundaries, we set higher weights for the positive class. 
%
In order to answer questions about temporal relations, it is not particularly harmful to introduce spurious events, but missing an event makes it impossible to answer any question related to it. 
%
Therefore we intentionally boost the recall while sacrificing precision. 
%
Table \ref{entity-tags} shows the performance of our event extraction, as well as the performance of HeidelTime \textsc{timex} tagging. For events, partial overlap of mention boundaries is considered an error. 

\begin{table}[h!]
\begin{center}
\resizebox*{0.7\hsize}{!}{
\begin{tabular}{|l|l|l|l|}
\hline \bf Annotation & \bf Prec & \bf Rec & \bf F1\\ \hline
\textsc{timex} & 0.838 & 0.850 & 0.844\\
Event & 0.729 & 0.963 & 0.830\\
\hline
\end{tabular}
}
\end{center}
\vspace{-1em}
\caption{\label{entity-tags} \textsc{timex} and event evaluation on validation set. }
%\textsc{timex} and event annotations on validation set. }
\end{table}

%\subsection{Intra-Sentence Model}
\paragraph{Intra-Sentence Model}
We identify 12 classes of temporal relations, plus a \textsc{no-link} class. For training, we downsampled \textsc{no-link} class to 10\% of the number of positive instances.
%The 12 classes basically follow what the training data has, but we combined \textsc{simultaneous} and \textsc{identity}. 
Our system does not attempt to resolve coreference.  For the purpose of identifying temporal relations, \textsc{simultaneous} and \textsc{identity} links capture the same relation of simultaneity, which allowed us to combine them.
%Since we have not addressed event coreference, \textsc{simultaneous} and \textsc{identity} links are combined. 
%The \textsc{after} and \textsc{iafter} (immediately after) are semantically similar, so are \textsc{before} and \textsc{ibefore}. However, we noticed some questions in the QA toolkit specifically targets \textsc{iafter} and \textsc{ibefore}, so we still separate them.
%
%A major difficulty we have is that the instances for intra-sentence relations from training data are incomplete. Oftentimes, we can determine the temporal relations between two events after reading a sentence, but the training data provides no \textsc{tlink} annotation. %Moreover, several training files do not even contain any \textsc{tlink}s between event pairs at all, but only those between event and \textsc{timex} pairs. 
%As a result, if we want to compare the \textsc{tlink}s to the ``gold" \textsc{tlink}s directly, we cannot merely rely on the F1 scores. 
%
%For training, we downsampled \textsc{no-link} class to 10\% of the number of positive instances. 
% Lesha rewrite
%In addition to the class imbalance issues, it addresses the fact that TimeML-style annotation is de-facto sparse, with only a fraction of positive instances annotated.
%
%AR: REMOVED (was it moved to supplementary materials?)
The LSTM layer of the intra-sentence model contains 256 LSTM units on each branch. The hidden layer on top of that has 100 neurons. We set a dropout rate 0.6 on input layer, and another drop out rate 0.5 on the hidden layer before output. 
%In our case, dropout is necessary to reduce overfitting.
%


\iffalse
\subsubsection{Inadequacy of Training Data}
A major difficulty we have is that the instances for intra-sentence relations from training data is incomplete. Often times, we can determine the temporal relations between two events after reading a sentence, but the training data provides no \textsc{tlink} annotation. %Moreover, several training files do not even contain any \textsc{tlink}s between event pairs at all, but only those between event and \textsc{timex} pairs. 
As a result, if we want to compare the \textsc{tlink}s to the ``gold" \textsc{tlink}s directly, we cannot merely rely on the F1 scores. Otherwise we will mistakenly conclude too many false positive labels are generated. To tackle this issue, we need to use some special techniques in both evaluation and training. 

For training, we downsampled \textsc{no-link} cases. We tried to make the number of \textsc{no-link} instances as many as 10\%, 50\%, and 100\% of the number of positive instances, respectively. Then we checked the recall values (based on \textsc{tlink} comparison) of each class, especially the five major classes. On the other hand, we always check the performance with the QA tool, which is supposedly immune to the false-neg problem, in terms of evaluation. 
\fi  


\paragraph{Cross-Sentence Model}
%\subsection{Cross-Sentence Model}
%The LSTM layer of the cross-sentence model contains 256 LSTM units on each branch. The hidden layer on top of that has 100 neurons. We set a dropout rate 0.6 on input layer, and another drop out rate 0.5 on the hidden layer before output.

The training and evaluation procedures are very similar to what we did for intra-sentence models, and the hyperparameters for the neural networks are the same. Now the vast majority of entity pairs have no \textsc{tlink}s explicitly marked in training data. Unlike the intra-sentence scenario, however, a \textsc{no-link} label is truly adequate in most cases. %From the two sentences alone, it is often true that a reader cannot interpret the temporal relations between the entities across sentence boundary. That being said, there are still many false negatives and it is not feasible to evaluate the systems in any straightforward way. 
We found that downsampling \textsc{no-link} instances to match the number of all positive instances (ratio=1) yields desirable results. Since positive instances are very sparse in both the training and validation data, the ratio should not be too low, so as not to risk overfitting.
%otherwise overfitting would be a concern.

\paragraph{DCT Model}
%\subsection{DCT Model}
We use the same hyperparameters for the DCT model as for the intra-sentence and cross-sentence models. %The hyperparameters are the same too.
%
Again, the training files do not sufficiently annotate \textsc{tlink}s with DCT even if the relations are clear, so there are many false negatives. We downsample the \textsc{no-link} instances so that they are 4 times the number of positive instances.

\begin{table}[h]
\begin{center}
\resizebox*{\hsize}{!}{
\begin{tabular}{|l|c|c|c|c|c|c|c|}
\hline 
\bf system	&\bf coverage &\bf prec &\bf rec &\bf f1 \\ \hline
human-fold1-original		&0.43	&0.91	&0.38	&0.54 \\
human-fold1-timlinks		&0.52	&0.93	&0.47	&\bf 0.62 \\
TIPSem-fold1-original		&0.35	&0.57	&0.22	&0.32\\
TIPSem-fold1-timex		&0.53	&0.69	&0.38	&0.50\\ \hline
orig. validation data		&0.37	&\bf 0.93	&0.34	&0.50\\
orig. tags TEA tlinks		&0.81	&0.58	&0.47	&0.52\\
TEA-initial	&0.78	&0.60	&0.47	&0.52\\
TEA-double-check		&\bf 0.89	&0.60	&\bf 0.53	&0.56\\
TEA-prune		&0.82	&0.58	&0.48	&0.53\\ \hline
TEA-flat		&0.81	&0.44	& 0.35	& 0.39\\
TEA-Dense   &0.68	&0.70	& 0.48	& 0.57\\ \hline
TEA-final		&0.84	&0.64	&\bf 0.53	&\bf 0.58\\
\hline
\end{tabular}
}
\end{center}
\vspace{-1em}
\caption{\label{results-val} QA results on validation data. There are $\mathbf{79}$ questions in total. The 4 systems on the top of the table are provided with the toolkit. The systems starting with ``human-" are annotated by human experts. TEA-final 
%is our final model, which 
utilizes both double-check and pruning. TEA-flat 
uses the
%is the model with 
flat context. TEA-Dense is trained on TimeBank-Dense.}
\end{table}

\iffalse
\subsection{Double-checking}
We introduce a technique to boost the recall of positive classes and reduce misclassification introduced by confusion of the  opposite classes.  Since entity pairs are always classified in both orders, if both results are positive (not \textsc{no-link}), we adopt the label with a higher probability score, as assigned by the softmax classifier. We call this technique ``double-checking". In particular, it serves to reduce the errors that are fundamentally harmful e.g. \textsc{before} misclassified as \textsc{after}, and vice versa. 
%
In addition to that, we allow a positive class to have the ``veto power" against \textsc{no-link} class. 
%For instance, if our model predicts $(e_1, e_2)\rightarrow \text{\textsc{no-link}}$ but $(e_2, e_1)\rightarrow \text{\textsc{after}}$, then we adopt the result $(e_2, e_1)\rightarrow \text{\textsc{after}}$. 
For instance, if our model predicts $(e_1, e_2)\rightarrow \text{\textsc{after}}$ but \textsc{no-link} reversely, we adopt the former.

%We introduce a technique to boost the recall of positive classes and reducing misclassifications among opposite classes.  The goal is to reduce the errors that are fundamentally harmful e.g. \textsc{before} misclassifed as \textsc{after}, and vice versa. we also allow a positive class to have the ``veto power" against \textsc{no-link} class. For instance, if our model predicts $(e_1, e_2)\rightarrow \textsc{no-link}$ but $(e_2, e_1)\rightarrow \textsc{after}$, then we adopt the result $(e_2, e_1)\rightarrow \textsc{after}$. Entity pairs are always classified in both orders, and if both results are positive (not \textsc{no-link}), we adopt the one with a higher probability score, which is delivered by the softmax classifier. We call this technique ``double-check". 

\begin{table}[h]
\begin{center}
% \resizebox*{\hsize}{2cm}{
\resizebox{\columnwidth}{!}{
\begin{tabular}{|@{} l|l|l|l|l @{}|}
\hline 
\bf \textsc{no-link} ratio & \bf Recall & \bf Recall & \bf \textsc{before} & \bf \textsc{after} \\
\bf               & \bf \textsc{before} & \bf \textsc{after} & \bf  as \textsc{after} & \bf as \textsc{before}\\
\hline
0.5  & 0.451 & 0.445 & 0.075 & 0.092\\
0.1  & 0.643 & 0.666 & 0.145 & 0.159\\
% 0.1 \textsc{no-link} ratio &       &       &       &      \\
0.1 + double-check & 0.721 & 0.721 & 0.125 & 0.125\\
\hline
\end{tabular}
}
\end{center}
\vspace{-1em}
\caption{\label{witin-exp} 
Effects of downsampling and double-checking on intra-sentence results. 0.5 \textsc{no-link} ratio means that \textsc{no-link}s are downsampled to a half of the number of all positive instances combined. \textsc{Before} as \textsc{after} shows the fraction of \textsc{before} misclassified as \textsc{after}, and vice versa.}
\end{table}

As illustrated in Table \ref{witin-exp}, downsampling the \textsc{no-link} cases boosts the recall of positive classes. Double-checking technique not only further boost recalls, but also reduces the misclassifications between opposite classes. 
%This is not the final checkpoint for conflicting classifications. As described in Section\ref{pruning}, we have a pruning algorithm to resolve conflicts at the end. 
%Results these configurations produce in the QA-based evaluation will be shown in the next section.
\fi

\iffalse
\section{Baseline models}
\subsection{Flat Context}
 In order to validate the choice of the dependency path-based context, we also experimented with a conventional flat context window, using the same hyperparameters. 
%Instead of using the dependency paths, we also tried using the ``flat context" as input to the neural network models. 
Every entity is represented by a 11-word window, with the entity mention in the middle.
If two entities are near each other, their windows are cut short before reaching the other entity.
%to the other entity, also not include any words further apart. 
%We use the same hyperparameters and evaluation method as before. The purpose is to provide another baseline to justify our choice of the dependency path approach.

\subsection{TimeBank-Dense}
We ran the same system on TimeBank-Dense to see how it performs on a similar task with a different set of labels and another method of evaluation. In this experiment, we used the event and \textsc{timex} tags from test data, as \newcite{CATENA}.

%Some necessary changes are made. 
Since all the \textsc{no-link} (vague) relations are labeled, downsampling is not applied. We still use double-checking in final conflict resolution, but do not give positive cases the veto power over \textsc{no-link}. Since \textsc{no-link} relations dominate, especially for cross-sentence pairs, we set class weights inversely proportional to the frequencies of the classes during training. This is a commonly used strategy in supervised learning when the classes are heavily unbalanced. We also reduce input batch size to counteract class imbalance.
%Finally, we change the input batch size from 100 to 32. When the batch size is big, the imbalance of classes seems to be more harmful.

We ran two sets of experiments. One used the uniform configurations for all the neural network models, similar to our experiments with QA-TempEval. The other tuned the hyperparameters for each component model (number of neurons, dropout rates, and early stop) separately. %Both results will be reported.


\fi

%\section{Results and Discussion}
\section{Experiments}
\label{results}

In this section, we first describe the model selection experiments on QA-TempEval validation data, selectively highlighting results of interest.  We then present the results obtained with the optimized model on the QA-TempEval task and on TimeBank-Dense.

\iffalse
In this section, we 
%discuss model selection, 
selectively highlight model selection results that are of interest.
We then discuss the results of the optimized model on QA-TempEval and TimeBank-Dense.
%We will first present the results from validation data, with different model configurations, then the results on test data with the optimized model. At last we will show results on TimeBank-Dense data.
\fi

\subsection{Model Selection Experiments}
%In this section, we selectively highlight model selection results that are of interest.
%
% AR: replaced
%The objective of the evaluation here is model selection. It is impossible to show all the intermediate results, so we will selectively highlight the ones of interest. 
%
%First of all, it should be noted that the QA toolkit has some bugs, as shown in below.
%\begin{quote}
%\footnotesize
%34$\vert$ APW19980219.0476.tml$\vert$ IS ei48 \textsc{after} ei47$\vert$ Did Howes flee from Cambodia after the coup d'etat? (YES)$\vert$ yes
%\end{quote}
%should be:
%\begin{quote}
%\footnotesize
%34$|$APW19980219.0476.tml$|$IS ei47 \textsc{after} ei48$|$Did Howes flee from Cambodia after the coup d'etat? (YES)$|$yes
%\end{quote}
%And
%\begin{quote}
%\footnotesize
%24$|$XIE19980821.0077.tml$|$IS ei8 \textsc{before} ei9$|$Was Freeh at a conference before returning home? (YES)$|$is
%\end{quote}
%should be:
%\begin{quote}
%\footnotesize
%24$|$XIE19980821.0077.tml$|$IS ei8 \textsc{before} ei9$|$Was Freeh at a conference before returning home? (YES)$|$yes
%\end{quote}
%
%First of all, it should be noted that the released QA toolkit for validation data contains some errors. Question 24 from \textsf{XIE19980821.0077.tml} should be answered with ``yes", but the key is a typo ``is". Question 34 from \textsf{APW19980219.0476.tml} has \textsc{before} that should be replaced with \textsc{after}. Question 29 from \textsf{XIE19980821.0077.tml} has ``unknown" as the key, but after reading the article, we believe the correct answer is ``no". 
%
As mentioned before, ``gold'' \textsc{tlink}s are sparse, so we cannot merely rely on the F1 scores on validation data to do model selection. Instead, we used the QA toolkit. 
%
The toolkit contains 79 yes-no questions about temporal relations between entities in the validation data. Originally, only 6 questions have ``no" as the correct answer, and 1 question is listed as ``unknown".  After investigating the questions and answers, however, we found some errors and typos\footnote{Question 24 from \textsf{XIE19980821.0077.tml} should be answered with ``yes", but the answer key contains a typo ``is". Question 34 from \textsf{APW19980219.0476.tml} has \textsc{before} that should be replaced with \textsc{after}. Question 29 from \textsf{XIE19980821.0077.tml} has ``unknown" in the answer key, but after reading the article, we believe the correct answer is ``no".}. After fixing the errors, there are 7 no-questions and 72 yes-questions in total. All evaluations are performed on the fixed data.
%after fixing the bugs. %We report results in two decimal digits because the previous publication \cite{Llorens2015:TempEval}  did so. 

The evaluation tool draws answers from the annotations only. If an entity (event or \textsc{timex}) involved in a question is not annotated, or the \textsc{tlink} cannot be found, the question will then be counted as not answered. There is no way for participants to give an answer directly, other than delivering the annotations. The program generates Timegraphs to infer relations from the annotated \textsc{tlink}s. As a result, relations without explicit \textsc{tlink} labels can still be used if they can be inferred from the annotations. The QA toolkit uses the following evaluation measures: 
%are defined in below:
\begin{description}
% \vspace{-1.0em}
\item \small coverage = \normalsize $\frac{\# \text{answered}}{\# \text{questions}}$, \small precision = \normalsize $\frac{\# \text{correct}}{\# \text{answered}}$
\item \small recall = \normalsize $\frac{\# \text{correct}}{\# \text{questions}}$, \small f1 = \normalsize $\frac{2\times \text{precision}\times \text{recall}}{\text{precision}+\text{recall}}$
% \vspace{-0.2em}
\end{description}

Table \ref{results-val} shows the results produced by different models on the validation data. The results of the four systems above the first horizontal line are provided by the task organizer. Among them, the top two use annotations provided by human experts. As we can see, the precision is very high, both above 0.90. Our models cannot reach that precision. In spite of the lower precision, automated systems can have much higher coverages i.e. answer a lot more questions. %To answer more questions, a system has to deal with more complicated situations, and thus is more likely to make mistakes. 

As a starting point, we evaluated the validation files in their original form, and the results are shown as ``orig. validation data" of Table \ref{results-val}. The precision was good, but with very low coverage. This supports our claim that the \textsc{tlink}s provided by the training/validation files are not complete. We also tried using the event and \textsc{timex} tags from the validation data, but performing \textsc{tlink} classification with our system. As shown with ``orig. tags TEA tlinks" in the table, now the coverage rises to 64 (or 0.81), and the overall F1 score reaches 0.52. The TEA-initial system uses our own annotators. The performance is similar, with a slight improvement in precision. This result shows our event and \textsc{timex} tags work well, and are not inferior to the ones provided by the training data. 

The double-checking technique boosts the coverage a lot, probably because we allow positive results to veto \textsc{no-link}s. Combining double-checking with the pruning technique yields the best results, with F1 score 0.58, answering 42 out of 79 questions correctly.

In order to validate the choice of the dependency path-based context, we also experimented with a conventional flat context window, using the same hyperparameters. Every entity is represented by a 11-word window, with the entity mention in the middle. If two entities are near each other, their windows are cut short before reaching the other entity. Using the flat context instead of dependency paths yields a much weaker performance. This confirms our hypothesis that syntactic dependencies represent temporal relations better than word windows. However, it should be noted that we did not separately optimize the models for the flat context setting. %after seeing it is not the promising way to go.
The large performance drop we saw from switching to flat context did not warrant performing a separate parameter search.

We also wanted to check whether a comprehensive annotation of \textsc{tlink}s in the training data can improve model performance on the QA task.
%
We therefore trained our model on TimeBank-Dense data and evaluated it with QA (see the TEA-Dense line in Table \ref{results-val}).
%
Interestingly, the performance is nearly as good as our top model, although TimeBank-Dense only uses five major classes of relations. For one thing, it shows that our system may perform equally after being trained on sparsely labeled data and on densely labeled data, judged from the QA evaluation tool. If this is true, excessively annotated data may not be necessary in some tasks.

\begin{table}[h!]
\begin{center}
\resizebox*{0.9\hsize}{!}{
\begin{tabular}{|c|c|c|c|c|c|c|c|}
 \hline 
	&\bf doc &\bf words &\bf quest &\bf yes &\bf no &\bf dist- &\bf dist+ \\ \hline
 news	&10	&6920	&99	&93	&6	&40	&59 \\
 wiki	&10	&14842	&130	&117	&13	&58	&72 \\
 blogs	&8	&2053	&65	&65	&0	&30	&35 \\ \hline
 total	&28	&23815	&294	&275	&19	&128	&166 \\
\hline
\end{tabular}
}
\end{center}
\vspace{-1em}
\caption{Test data statistics. Adapted from Table 1 in  \newcite{Llorens2015:TempEval}.}
\label{test-data}
\end{table}

%\subsection{Evaluation on Test Data}
% AR: REMOVE
%We will show the detailed evaluation results on QA-TempEval task first, and then show the results on TimeBank-Dense data.

\subsection{QA-TempEval Experiments}

We use the QA toolkit provided by the QA-TempEval organizers to 
evaluate our system on the test data. 
%We annotated test files, and then run the evaluation script over the annotated files. 
The documents in test data are not annotated at all, so the event tags, \textsc{timex} tags, and \textsc{tlink}s are all created by our system. 
% AR: add if adding back table 5 with test data stats

Table \ref{test-data} shows the the statistics of test data. 
As we can see, the vast majority of the questions in the test set should be answered with $yes$. Generally speaking, it is much more difficult to validate a specific relation (answer $yes$) than to reject it (answer $no$) when we have as many as 12 types of relations in addition to the vague \textsc{no-link} class. \textbf{dist-} means questions involving entities that are in the same sentence or in consecutive sentences. \textbf{dist+} means the entities are farther away.

The QA-TempEval task organizers used two evaluation methods. The first method is exactly the same as the one we used on validation data. The second method used a so-called Time Expression Reasoner (TREFL) to add relations between \textsc{timex}es, and evaluated the augmented results. The goal of such an extra run is to ``analyze how a general time expression reasoner could improve results". Our  model already includes a component to handle \textsc{timex} relations, so we will compare our results with other systems' in both methods.

\begin{table}[h!]
\begin{center}
\resizebox*{\hsize}{!}{
\begin{tabular}{|l|c|c|c||c|c|}

\multicolumn{6}{c}{News Genre (99 questions)} \\
\hline 
\bf system	&\bf prec &\bf rec &\bf f1 &\bf \% answd &\bf \# correct   \\ \hline
hlt-fbk-ev1-trel1 &0.59	&0.17	&0.27   &29 &17 \\
hlt-fbk-ev1-trel2 &0.43	&0.23	&0.30   &55 &23 \\
hlt-fbk-ev2-trel1 &0.56	&0.20	&0.30   &36 &20 \\
hlt-fbk-ev2-trel2 &0.43	&0.29	&0.35   &69 &29 \\
ClearTK &0.60	&0.06	&0.11   &10 &6 \\
CAEVO &0.59	&0.17	&0.27   &29 &17 \\
TIPSemB &0.50	&0.16	&0.24   &32 &16 \\
TIPSem & 0.52	&0.11	&0.18   &21 &11 \\ \hline
TEA &\bf 0.61	&\bf 0.44	&\bf 0.51   &\bf 73 &\bf 44 \\
\hline
\end{tabular}
}
\newline
\vspace*{0.15cm}
\resizebox*{\hsize}{!}{
\begin{tabular}{|l|c|c|c||c|c|}

\multicolumn{6}{c}{Wikipedia Genre (130 questions)} \\
\hline 
\bf system	&\bf prec &\bf rec &\bf f1 &\bf \% answd &\bf \# correct   \\ \hline
hlt-fbk-ev1-trel1 &0.55	&0.16	&0.25   &29 &21 \\
hlt-fbk-ev1-trel2 &0.52	&0.22	&0.35   &50 &34 \\
hlt-fbk-ev2-trel1 &0.58	&0.17	&0.26   &29 &22 \\
hlt-fbk-ev2-trel2 &0.62	&0.36	&0.46   &58 &47 \\
ClearTK &0.60	&0.05	&0.09   &8 &6 \\
CAEVO &0.59	&0.17	&0.26   &28 &22 \\
TIPSemB &0.52	&0.13	&0.21   &25 &17 \\
TIPSem &\bf 0.74	&0.19	&0.30   &26 &25 \\ \hline
TEA &0.62	&\bf 0.44	&\bf 0.51  &\bf 71 &\bf 57 \\
\hline
\end{tabular}
}
\newline
\vspace*{0.15 cm}
\resizebox*{\hsize}{!}{
\begin{tabular}{|l|c|c|c||c|c|}

\multicolumn{6}{c}{Blog Genre (65 questions)} \\
\hline 
\bf system	&\bf prec &\bf rec &\bf f1 &\bf \% answd &\bf \# correct   \\ \hline
hlt-fbk-ev1-trel1 &\bf 0.57	&0.18	&\bf 0.28   &32 &12 \\
hlt-fbk-ev1-trel2 &0.43	&0.18	&0.26   &43 &12 \\
hlt-fbk-ev2-trel1 &0.47	&0.14	&0.21   &29 &9 \\
hlt-fbk-ev2-trel2 &0.34	&\bf 0.20	&0.25   &\bf 58 &\bf 13 \\
ClearTK &0.56	&0.08	&0.14   &14 &5 \\
CAEVO &0.48	    &0.18	&0.27   &38 &12 \\
TIPSemB &0.31	&0.08	&0.12   &25 &5 \\
TIPSem & 0.45	&0.14	&0.21   &31 &9 \\ \hline
TEA &0.43	&\bf 0.20	&0.27  & 46 &\bf 13 \\
\hline
\end{tabular}
}
\end{center}
\vspace{-1em}
\caption{QA evaluation on test data without TREFL}
\label{results-test}
\end{table}

%\subsection{Evaluation without TREFL}
The results are shown in Table \ref{results-test}. We give the results for the hlt-fbk systems that were submitted by the top team.
%participants with top performance. 
Among them, hlt-fbk-ev2-trel2 was the overall winner of TempEval task in 2015. ClearTK, CAEVO, TIPSEMB and TIPSem were some off-the-shelf systems provided by the task organizers for reference. These systems were not optimized for the task \cite{Llorens2015:TempEval}. 

For news and Wikipedia genres, our system outperforms all other systems by a large margin. %In both cases, TEA answered 44\% questions correctly, a significant edge over others. TEA's coverages are also a lot higher than others'. 73\% and 71\% questions were answered, respectively.
For blogs genre, however, the advantage of our system is unclear. 
%TEA and hlt-fbk-ev2-trel2 tied for the first place with respect to recall values, while another system  hlt-fbk-ev1-trel1 has the best f1. CAEVO, which has much lower performances on news and Wikipedia data, now has results close to the best. 
Recall that our training set contains news articles only. While the trained model works well on Wikipedia dataset too, blog dataset is fundamentally different in the following ways: (1) each blog article is very short, (2) the style of writing in blogs is much more informal, with non-standard spelling and punctuation, and (3) blogs are written in first person, and the content is usually personal stories and feelings. 

Interestingly, the comparison between different hlt-fbk submissions suggests that resolving event coreference (implemented by hlt-fbk-ev2-trel2) substantially improves system performance for the news and Wikipedia genres.  However, although our system does not attempt to handle event coreference explicitly, it easily outperforms the hlt-fbk-ev2-trel2 system in the genres where coreference seems to matter the most.  %This suggests that 
%
%It is therefore interesting to note that although our system does not attempt to handle event coreference, it does outperform the hlt-fbk-ev2-trel2 system which does implement it.
%The hlt-fbk-ev2-trel2 system implements event coreference, which seems to contribute to their relatively good performance. Our model does not attempt to handle event coreference, yet performs better. 
% AR: REMOVE
%It is possible that the deep learning mechanisms capture elements of co-references.
%
\paragraph*{Evaluation with TREFL}
The extra evaluation with TREFL has a post-processing step that adds \textsc{tlink}s between \textsc{timex} entities. Our model already employs such a strategy, so this post-processing does not help. In fact, it drags down the scores a little. %For other models, nonetheless, it improves the results significantly. 
%
\begin{table}
\resizebox*{\hsize}{!}{
\begin{tabular}{|l|c|c|c||c|c|}
\multicolumn{6}{c}{All Genres (294 questions)} \\
\hline 
\bf system	&\bf prec &\bf rec &\bf f1 &\bf \% awd &\bf \# corr   \\ \hline
hlt-fbk-ev2-trel2   &0.49	&0.30	&0.37	&62	&89 \\
hlt-fbk-ev2-trel2-TREFL &0.51	&0.34	&0.40   &\bf 67 &99 \\\hline 
TEA &\bf 0.59	&\bf 0.39	&\bf 0.47   &66 &\bf 114 \\
TEA-TREFL &0.58	&0.38	&0.46   &66 &111 \\
\hline
\end{tabular}
}
\vspace{-1em}
\caption{Test results over all genres. 
%The suffix -TREFL means the Time Expression Reasoner is implemented to augment annotations.
}
\label{results-all}
\end{table}
%
Table \ref{results-all} summarizes the results over all genres before and after applying TREFL. 
%To save space, we only 
For comparison, we include the top 2015 system, hlt-fbk-ev2-trel2. As we can see, TEA generally shows substantially 
%better performance.
higher scores.
%than others. 
%In total, TEA answered 194 out of 294 questions, or 66\%. Among them 114 answers are correct, which is 39\% of all questions. %
%As mentioned before, the performance is largely dragged down by the blog dataset.
% AR: REMOVED TO ADD ACKNOWLEDGEMENTS
%The performance would be much better without the blog dataset, which is very different from the training data. 
%
%is largely dragged down by 
% AR: REMOVE
%If we only consider news and Wikipedia datasets, which are more appropriate for the trained models, TEA actually answered 101 out of 229 questions correctly, which is 44\% in percentage.

\subsection{TimeBank-Dense Experiments}
We trained and evaluated the same system on TimeBank-Dense to see how it performs on a similar task with a different set of labels and another method of evaluation. In this experiment, we used the event and \textsc{timex} tags from test data, as \newcite{CATENA}.

%Some necessary changes are made. 
Since all the \textsc{no-link} (vague) relations are labeled, downsampling was not necessary. We did use double-checking in the final conflict resolution, but without giving positive cases the veto power over \textsc{no-link}. Because \textsc{no-link} relations dominate, especially for cross-sentence pairs, we set class weights to be inversely proportional to the class frequencies during training. 
% AR cut for space from final version
%This is a commonly used strategy in supervised learning when the classes are heavily imbalanced. 
We also reduced input batch size to counteract class imbalance.
%Finally, we change the input batch size from 100 to 32. When the batch size is big, the imbalance of classes seems to be more harmful.

We ran two sets of experiments. One used the uniform configurations for all the neural network models, similar to our experiments with QA-TempEval. The other tuned the hyperparameters for each component model (number of neurons, dropout rates, and early stop) separately. %Both results will be reported.

The results from TimeBank-Dense are shown in Talble~\ref{results-dense}. 
%We did not find detailed descriptions of how the score is calculated in the published paper, but it is mentioned that precision, recall, and F1 are all the same because all edges are labeled, so we suppose it is equivalent to calculating the accuracy of all labeled edges. 
Even though TimeBank-Dense has 
a very different methodology for both annotation and evaluation,
%a very different methodology of labeling data and evaluating results, 
our ``out-of-the-box'' model which uses uniform configurations across different components obtains F1 0.505, compared to the best F1 of 0.511 in previous work.  Our best result of 0.519 is obtained by tuning hyperparameters on intra-sentence, cross-sentence, and DCT models independently.

%the result 0.505 from uniformly-configured (``out-of-the-box") models here, which parallels what we did in QA-TempEval.

% OLD
%We include two results here. The best result 0.519 is obtained when we tune hyperparameters on intra-sentence, cross-sentence, and dct models independently. Since we use uniform neural network configurations over the models in QA-TempEval, we also include the result 0.505 from uniformly-configured (``out-of-the-box") models here, which parallels what we did in QA-TempEval.

%In any case, the performance is comparable to the state of the art, even though TimeBank-Dense has a very different methodology of labeling data and evaluating results. 

For the QA-TempEval task, we intentionally tagged a lot of events, and let the pruning algorithm resolve potential conflicts. In the TimeBank-Dense experiment, however, we only used the provided event tags, which are sparser than what we have in QA-TempEval. The system may have lost some leverage that way. 


\begin{table}
\resizebox*{\hsize}{!}{
\begin{tabular}{|l||c|c|c|c|c|c|}
\hline 
\bf system	&\bf ClearTK &\bf NavyT &\bf CAEVO &\bf CATENA & \multicolumn{2}{|c|}{\bf TEA-Dense}   \\ \hline
\bf  &  &  &  & &\bf uniform & \bf tuned   \\ %\hline
F1   &0.447	&0.453	&0.507	&0.511	&0.505 & 0.519 \\
\hline
\end{tabular}
}
\vspace{-1em}
%\caption{Test results on TimeBank-Dense. TEA-Dense is our system 0.519 is from the fine tuned systems, and 0.505 is from the out-of-the-box systems. ClearTK and NavyT results are the best ones from \cite{chambers2014dense}. CAEVO result is also from the same article. CATENA result is from \cite{CATENA} }
\caption{TEA results on TimeBank-Dense.
%TEA-Dense is our system 0.519 is from the fine tuned systems, and 0.505 is from the out-of-the-box systems.  
ClearTK, NavyT, and CAEVO are systems from \newcite{chambers2014dense}.  CATENA is from \newcite{CATENA} }
\label{results-dense}
\end{table}

\section{Conclusion}
\label{conclusion}

%We have proposed a new method for extraction of temporal relations, which uses shortest dependency paths as input to a relatively simple LSTM-based architecture.  The same architecture is then re-deployed in a set of subtasks needed for temporal relation extraction.
%We have proposed a new method for extraction of temporal relations which takes a relatively simple LSTM-based architecture, using shortest dependency paths as input, and re-deploys it in a set of subtasks needed for extraction of temporal relations from text.

We have proposed a new method for extraction of temporal relations which takes a relatively simple LSTM-based architecture, using shortest dependency paths as input, and re-deploys it in a set of subtasks needed for extraction of temporal relations from text. We also introduce two techniques that leverage confidence scores produced by different system components to substantially improve the results of \textsc{tlink} classification:
(1) a ``double-checking'' technique which reverses pairs in classification, thus boosting the recall of positives and reducing misclassifications among opposite classes and (2) an efficient pruning algorithm to resolve \textsc{tlink} conflicts.
%Unlike other existing approaches, we have not addressed event coreference.  
%Our proposed method outperforms state-of-the-art in a QA-based evaluation by a large margin.
%
In a QA-based evaluation, our proposed method 
%which does not address event coreference explicitly
outperforms state-of-the-art methods by a large margin.
%which do address it
We also obtain state-of-the art results in an intrinsic evaluation on a very different TimeBank-Dense dataset, proving generalizability of the proposed model.



%This paper proposes a system to annotate events, \textsc{timex}es, as well as \textsc{tlink}s on text documents. We extend the shortest dependency path approach to build \textsc{tlink}s between entities within a sentence, or in consecutive sentences. We use a similar LSTM model to build relations between events and document creation time. A rule-based model links \textsc{timex}es. Then a pruning algorithm resolves conflicts in the combined results. %\textsc{timex} annotation is performed by an external package HeidelTime, and the event annotator makes use of NewsReader parser. 

%When training our models, we found identifiable relations are not always labeled in training data. We introduced a double-check technique to boost recalls of positive cases, and reduce mislcassifications among opposite classes.

%TEA outperforms previous systems, even without co-reference resolution. However, we should point out that we did the project with less time pressure than the previous participants, and we used external packages in the pipeline. Our goal is to develop a new approach that can improve the performance on this type of tasks.

\section*{Acknowledgments}
This project is funded in part by an NSF CAREER Award to Anna Rumshisky (IIS-1652742). We would like to thank Connor Cooper and Kevin Wacome for their contributions to the early stages of this work.


\bibliography{emnlp2017}
\bibliographystyle{emnlp_natbib}



\end{document}

emnlp2017.bbl
\begin{thebibliography}{23}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi

\bibitem[{Agerri et~al.(2014)Agerri, Bermudez, and
  Rigau}]{Agerri2014:newsreader}
Rodrigo Agerri, Josu Bermudez, and German Rigau. 2014.
\newblock \href {http://ixa2.si.ehu.es/ixa-pipes/papers/ixa-pipes-lrec2014.pdf}
  {Ixa pipeline: Efficient and ready to use multilingual nlp tools}.
\newblock In \emph{Proc. of the 9th Language Resources and Evaluation
  Conference (LREC2014)}, pages 26–--31.

\bibitem[{Bethard et~al.(2015)Bethard, Derczynski, Pustejovsky, and
  Verhagen}]{bethard2015semeval}
Steven Bethard, Leon Derczynski, James Pustejovsky, and Marc Verhagen. 2015.
\newblock Semeval-2015 task 6: Clinical tempeval.
\newblock In \emph{Proc. of the 9th International Workshop on Semantic
  Evaluation (SemEval 2015). Association for Computational Linguistics}.

\bibitem[{Chambers et~al.(2014)Chambers, Cassidy, McDowell, and
  Bethard}]{chambers2014dense}
Nathanael Chambers, Taylor Cassidy, Bill McDowell, and Steven Bethard. 2014.
\newblock Dense event ordering with a multi-pass architecture.
\newblock \emph{Transactions of the Association for Computational Linguistics},
  2:273--284.

\bibitem[{Hochreiter and Schmidhuber(1997)}]{Hochreiter:LSTM}
Sepp Hochreiter and J\"{u}rgen Schmidhuber. 1997.
\newblock Long short-term memory.
\newblock \emph{Neural Computation}, 9(8):1735--1780.

\bibitem[{Karp(1972)}]{Karp:1972}
Richard Karp. 1972.
\newblock Reducibility among combinatorial problems.
\newblock In \emph{Complexity of Computer Computations, Proc. Sympos.}, pages
  85--103.

\bibitem[{Llorens et~al.(2015{\natexlab{a}})Llorens, Chambers, UzZaman,
  Mostafazadeh, Allen, and Pustejovsky}]{Llorens2015:TempEval}
Hector Llorens, Nathanael Chambers, Naushad UzZaman, Nasrin Mostafazadeh, James
  Allen, and James Pustejovsky. 2015{\natexlab{a}}.
\newblock Semeval-2015 task 5: Qa tempeval - evaluating temporal information
  understanding with question answering.
\newblock In \emph{Proc. of the 9th International Workshop on Semantic
  Evaluation}, pages 46–--54. Association for Computational Linguistics.

\bibitem[{Llorens et~al.(2015{\natexlab{b}})Llorens, Chambers, UzZaman,
  Mostafazadeh, Allen, and Pustejovsky}]{llorenssemeval}
Hector Llorens, Nathanael Chambers, Naushad UzZaman, Nasrin Mostafazadeh, James
  Allen, and James Pustejovsky. 2015{\natexlab{b}}.
\newblock Semeval-2015 task 5: Qa tempeval-evaluating temporal information
  understanding with question answering.
\newblock In \emph{Proc. of the International Workshop on Semantic Evaluation
  (SemEval-2015)}.

\bibitem[{Mani et~al.(2007)Mani, Wellner, Verhagen, and
  Pustejovsky}]{mani2007three}
Inderjeet Mani, Ben Wellner, Marc Verhagen, and James Pustejovsky. 2007.
\newblock Three approaches to learning tlinks in timeml.
\newblock \emph{Technical Report CS-07--268, Computer Science Department}.

\bibitem[{Minard et~al.(2015)Minard, Speranza, Agirre, Aldabe, van Erp,
  Magnini, Rigau, Urizar, and Kessler}]{minardsemeval}
Anne-Lyse Minard, Manuela Speranza, Eneko Agirre, Itziar Aldabe, Marieke van
  Erp, Bernardo Magnini, German Rigau, Rub{\'e}n Urizar, and Fondazione~Bruno
  Kessler. 2015.
\newblock Semeval-2015 task 4: Timeline: Cross-document event ordering.
\newblock In \emph{Proc. of the International Workshop on Semantic Evaluation
  (SemEval-2015)}.

\bibitem[{Mirza and Tonelli(2016)}]{CATENA}
P~Mirza and S~Tonelli. 2016.
\newblock Catena: Causal and temporal relation extraction from natural language
  texts.
\newblock In \emph{The 26th International Conference on Computational
  Linguistics}, pages 64--75. Association for Computational Linguistics.

\bibitem[{Mirza(2016)}]{DBLP:journals/corr/Mirza16}
Paramita Mirza. 2016.
\newblock \href {http://arxiv.org/abs/1604.08120} {Extracting temporal and
  causal relations between events}.
\newblock \emph{CoRR}, abs/1604.08120.

\bibitem[{Mirza and Minard(2015)}]{hlt-fbk}
Paramita Mirza and Anne-Lyse Minard. 2015.
\newblock Hlt-fbk: a complete temporal processing system for qa tempeval.
\newblock In \emph{Proc. of the 9th International Workshop on Semantic
  Evaluation (SemEval 2015)}, pages 801--805. Association for Computational
  Linguistics.

\bibitem[{Pustejovsky et~al.(2003)Pustejovsky, Casta{\~n}o, Ingria, Saur{\`i},
  Gaizauskas, Setzer, and Katz}]{Pustejovsky03timeml:robust}
James Pustejovsky, Jos{\'e} Casta{\~n}o, Robert Ingria, Roser Saur{\`i}, Robert
  Gaizauskas, Andrea Setzer, and Graham Katz. 2003.
\newblock Time{ML}: Robust specification of event and temporal expressions in
  text.
\newblock In \emph{in Fifth International Workshop on Computational Semantics
  (IWCS-5)}.

\bibitem[{Str\"{o}tgen and Gertz(2013)}]{StroetgenGertz2013:LREjournal}
Jannik Str\"{o}tgen and Michael Gertz. 2013.
\newblock \href {https://doi.org/10.1007/s10579-012-9179-y} {Multilingual and
  cross-domain temporal tagging}.
\newblock \emph{Language Resources and Evaluation}, 47(2):269--298.

\bibitem[{Sun(2014)}]{Sun:2014}
Weiyi Sun. 2014.
\newblock \emph{Time Well Tell: Temporal Reasoning in Clinical Narratives}.
\newblock PhD dissertation. Department of Informatics, University at Albany,
  SUNY.

\bibitem[{Sun et~al.(2013)Sun, Rumshisky, and Uzuner}]{sun2013evaluating}
Weiyi Sun, Anna Rumshisky, and Ozlem Uzuner. 2013.
\newblock Evaluating temporal relations in clinical text: 2012 i2b2 challenge.
\newblock \emph{Journal of the American Medical Informatics Association},
  20(5):806--813.

\bibitem[{UzZaman et~al.(2012)UzZaman, Llorens, Allen, Derczynski, Verhagen,
  and Pustejovsky}]{uzzaman2012tempeval}
Naushad UzZaman, Hector Llorens, James Allen, Leon Derczynski, Marc Verhagen,
  and James Pustejovsky. 2012.
\newblock Tempeval-3: Evaluating events, time expressions, and temporal
  relations.
\newblock \emph{arXiv preprint arXiv:1206.5333}.

\bibitem[{Verhagen et~al.(2007)Verhagen, Gaizauskas, Schilder, Hepple, Katz,
  and Pustejovsky}]{verhagen2007semeval}
Marc Verhagen, Robert Gaizauskas, Frank Schilder, Mark Hepple, Graham Katz, and
  James Pustejovsky. 2007.
\newblock Semeval-2007 task 15: Tempeval temporal relation identification.
\newblock In \emph{Proc. of the 4th International Workshop on Semantic
  Evaluations}, pages 75--80. Association for Computational Linguistics.

\bibitem[{Verhagen et~al.(2010)Verhagen, Sauri, Caselli, and
  Pustejovsky}]{verhagen2010semeval}
Marc Verhagen, Roser Sauri, Tommaso Caselli, and James Pustejovsky. 2010.
\newblock Semeval-2010 task 13: Tempeval-2.
\newblock In \emph{Proc. of the 5th international workshop on semantic
  evaluation}, pages 57--62. Association for Computational Linguistics.

\bibitem[{Vu et~al.(2016)Vu, Adel, Gupta, and
  Sch{\"{u}}tze}]{DBLP:journals/corr/VuAGS16}
Ngoc~Thang Vu, Heike Adel, Pankaj Gupta, and Hinrich Sch{\"{u}}tze. 2016.
\newblock \href {http://arxiv.org/abs/1605.07333} {Combining recurrent and
  convolutional neural networks for relation classification}.
\newblock \emph{CoRR}, abs/1605.07333.

\bibitem[{Xu et~al.(2015)Xu, Mou, Li, Chen, Peng, and Jin}]{Xu2015}
Yan Xu, Lili Mou, Ge~Li, Yunchuan Chen, Hao Peng, and Zhi Jin. 2015.
\newblock Classifying relations via long short term memory networks along
  shortest dependency paths.
\newblock In \emph{Proc. of EMNLP 2015}, pages 1785--1794. Association for
  Computational Linguistics.

\bibitem[{Zeng et~al.(2014)Zeng, Liu, Lai, Zhou, and Zhao}]{Zeng:2014}
Daojian Zeng, Kang Liu, Siwei Lai, Guangyou Zhou, and Jun Zhao. 2014.
\newblock Relation classification via convolutional deep neural network.
\newblock In \emph{Proc. of COLING 2014}, pages 2335--2344.

\bibitem[{Zhang and Wang(2015)}]{DBLP:journals/corr/ZhangW15a}
Dongxu Zhang and Dong Wang. 2015.
\newblock \href {http://arxiv.org/abs/1508.01006} {Relation classification via
  recurrent neural network}.
\newblock \emph{CoRR}, abs/1508.01006.

\end{thebibliography}
