Thesis.tex

\documentclass[
12pt, % The default document font size, options: 10pt, 11pt, 12pt
%oneside, % Two side (alternating margins) for binding by default, uncomment to switch to one side
english, % ngerman for German
% singlespacing % Single line spacing, alternatives: onehalfspacing or 
%onehalfspacing
doublespacing
,
%draft, % Uncomment to enable draft mode (no pictures, no links, overfull hboxes indicated)
nolistspacing, % If the document is onehalfspacing or doublespacing, uncomment this to set spacing in lists to single
%liststotoc, % Uncomment to add the list of figures/tables/etc to the table of contents
toctotoc, % Uncomment to add the main table of contents to the table of contents
parskip, % Uncomment to add space between paragraphs
%nohyperref, % Uncomment to not load the hyperref package
headsepline, % Uncomment to get a line under the header
%chapterinoneline, % Uncomment to place the chapter title next to the number on one line
%consistentlayout, % Uncomment to change the layout of the declaration, abstract and acknowledgements pages to match the default layout
]{MastersDoctoralThesis} % The class file specifying the document structure

%\usepackage[round]{natbib}

\usepackage{mathtools}
\usepackage{setspace} 
\usepackage{dsfont}
\usepackage{amsfonts}
\usepackage{subcaption}
\usepackage{paralist}
%\usepackage{subfig}
\usepackage{times}
\usepackage{latexsym}
\usepackage{graphicx}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{url}
\usepackage{pgfplotstable}
\usepackage{titlesec}
\usepackage{color}
\usepackage{lipsum,adjustbox}
\usepackage[font={small}]{caption}
\usetikzlibrary{positioning}
\usepackage{bbm}

%template additions
\usepackage[utf8]{inputenc} % Required for inputting international characters
\usepackage[T1]{fontenc} % Output font encoding for international characters

\usepackage{palatino} % Use the Palatino font by default

\usepackage[backend=bibtex,style=authoryear,natbib=true]{biblatex} % Use the bibtex backend with the authoryear citation style (which resembles APA)

\addbibresource{propose.bib} % The filename of the bibliography

\usepackage[autostyle=true]{csquotes} % Required to generate language-dependent quotes in the bibliography


\graphicspath{{./plots/}}
\newcommand{\com}[1]{}
%\newcommand{\oa}[1]{}
%\newcommand{\lc}[1]{}
\newcommand{\oa}[1]{\footnote{\color{red}OA: #1}}
\newcommand{\lc}[1]{\footnote{\color{blue}LC: #1}}
\newcommand{\newcite}[1]{\citeauthor{#1} (\citeyear{#1})}
\newcommand{\justcite}[1]{ (\cite{#1})}
\com{
	\makeatletter
	\newcommand{\@BIBLABEL}{\@emptybiblabel}
	\newcommand{\@emptybiblabel}[1]{}
	%\makeatother
	\usepackage[hidelinks]{hyperref}
}

\newenvironment{myequation}{
 \begin{equation}
}{
 \end{equation}
}
\newenvironment{myequation*}{
	\begin{equation*}
}{
\end{equation*}
}

%----------------------------------------------------------------------------------------
%	MARGIN SETTINGS
%----------------------------------------------------------------------------------------

\geometry{
	paper=a4paper, % Change to letterpaper for US letter
	inner=2.5cm, % Inner margin
	outer=3.8cm, % Outer margin
	bindingoffset=.5cm, % Binding offset
	top=1.5cm, % Top margin
	bottom=1.5cm, % Bottom margin
	%showframe, % Uncomment to show how the type block is set on the page
}

%----------------------------------------------------------------------------------------
%	THESIS INFORMATION
%----------------------------------------------------------------------------------------

\thesistitle{Conservatism and Over-conservatism in Grammatical Error Correction} % Your thesis title, this is used in the title and abstract, print it elsewhere with \ttitle
\supervisor{Dr. Omri \textsc{Abend}} % Your supervisor's name, this is used in the title page, print it elsewhere with \supname
\examiner{} % Your examiner's name, this is not currently used anywhere in the template, print it elsewhere with \examname
\degree{Master's degree} % Your degree name, this is used in the title page and abstract, print it elsewhere with \degreename
\author{Leshem \textsc{Choshen}} % Your name, this is used in the title page and abstract, print it elsewhere with \authorname
\addresses{} % Your address, this is not currently used anywhere in the template, print it elsewhere with \addressname

\subject{Natural Language Processing} % Your subject area, this is not currently used anywhere in the template, print it elsewhere with \subjectname
\keywords{} % Keywords for your thesis, this is not currently used anywhere in the template, print it elsewhere with \keywordnames
\university{\href{http://new.huji.ac.il/en}{Hebrew University}} % Your university's name and URL, this is used in the title page and abstract, print it elsewhere with \univname
\department{\href{http://en.cognitive.huji.ac.il/}{Department of cognitive sciences}} % Your department's name and URL, this is used in the title page and abstract, print it elsewhere with \deptname
\group{The huji NLP lab} % Your research group's name and URL, this is used in the title page, print it elsewhere with \groupname
\faculty{\href{http://www.hum.huji.ac.il/english/}{Faculty Of Humanities}} % Your faculty's name and URL, this is used in the title page and abstract, print it elsewhere with \facname

\AtBeginDocument{
	\hypersetup{pdftitle=\ttitle} % Set the PDF's title to your title
	\hypersetup{pdfauthor=\authorname} % Set the PDF's author to your name
	\hypersetup{pdfkeywords=\keywordnames} % Set the PDF's keywords to your keywords
}

\begin{document}
\frontmatter
\pagestyle{plain}
%\title{Thesis: Conservatism and Over-conservatism in Grammatical Error Correction}
%\author{
%  Leshem Choshen\textsuperscript{1} and Omri Abend\textsuperscript{2} \\
%  \textsuperscript{1}School of Computer Science and Engineering,
%  \textsuperscript{2} Department of Cognitive Sciences \\
%  The Hebrew University of Jerusalem \\
%  \texttt{leshem.choshen@mail.huji.ac.il, oabend@cs.huji.ac.il}\\
%}


%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\begin{titlepage}
	\begin{center}
		
		\vspace*{.06\textheight}
		{\scshape\LARGE \univname\par}\vspace{1.5cm} % University name
		\textsc{\Large Master's Thesis}\\[0.5cm] % Thesis type
		
		\HRule \\[0.4cm] % Horizontal line
		{\LARGE \bfseries \ttitle\par}\vspace{0.4cm} % Thesis title
		\HRule \\[1.5cm] % Horizontal line
		
		\begin{minipage}[t]{0.4\textwidth}
			\begin{flushleft} \large
				\emph{Author:}\\
				\authorname % Author name - remove the \href bracket to remove the link
			\end{flushleft}
		\end{minipage}
		\begin{minipage}[t]{0.4\textwidth}
			\begin{flushright} \large
				\emph{Supervisor:} \\
				\href{http://www.cs.huji.ac.il/~oabend/}{\supname} % Supervisor name - remove the \href bracket to remove the link  
			\end{flushright}
		\end{minipage}\\[0.5cm]
		
		\vfill
		
		\large \textit{A thesis submitted in fulfillment of the requirements\\ for the degree of \degreename} % University requirement text
		\textit{in the}\\[0.4cm]
		\groupname\\\deptname\\[1cm] % Research group name and department name
		
		\vfill
		
		{\large \today}\\[1cm] % Date
		%\includegraphics{Logo} % University/department logo - uncomment to place it
		
		\vfill
	\end{center}
\end{titlepage}

%----------------------------------------------------------------------------------------
%	DECLARATION PAGE
%----------------------------------------------------------------------------------------

\begin{declaration}
	\addchaptertocentry{\authorshipname} % Add the declaration to the table of contents
	\noindent I, \authorname, declare that this thesis titled, \enquote{\ttitle} and the work presented in it are my own. I confirm that:
	
	\begin{itemize} 
		\item This work was done wholly or mainly while in candidature for a research degree at this University.
		\item Where any part of this thesis has previously been submitted for a degree or any other qualification at this University or any other institution, this has been clearly stated.
		\item Where I have consulted the published work of others, this is always clearly attributed.
		\item Where I have quoted from the work of others, the source is always given. With the exception of such quotations, this thesis is entirely my own work.
		\item I have acknowledged all main sources of help.
		\item Where the thesis is based on work done by myself jointly with others, I have made clear exactly what was done by others and what I have contributed myself.\\
	\end{itemize}
	\com{
	\noindent Signed:\\
	\rule[0.5em]{25em}{0.5pt} % This prints a line for the signature
	
	\noindent Date:\\
	\rule[0.5em]{25em}{0.5pt} % This prints a line to write the date
}
\end{declaration}

\cleardoublepage
\com{
%----------------------------------------------------------------------------------------
%	QUOTATION PAGE
%----------------------------------------------------------------------------------------

\vspace*{0.2\textheight}

\noindent\enquote{\itshape Thanks to my solid academic training, today I can write hundreds of words on virtually any topic without possessing a shred of information, which is how I got a good job in journalism.}\bigbreak

\hfill Dave Barry
}
%----------------------------------------------------------------------------------------
%	ABSTRACT PAGE
%----------------------------------------------------------------------------------------

\begin{abstract}
	\addchaptertocentry{\abstractname} % Add the abstract to the table of contents
	Grammatical Error Correction systems (henceforth, {\it correctors}) aim to correct ungrammatical text,
	while changing it as little as possible. However, whereas such conservatism is a virtue for correctors,
	we find that state-of-the-art systems make substantially less changes to the source sentences than needed.
	Analyzing the distribution of possible corrections for a given sentence,   
	we show that this over-conservatism likely stems from
	the inability of a handful of reference corrections to account for the full variation of valid
	corrections for a given sentence. This results in undue penalization of valid corrections,
	thus disincentivizing correctors to make changes.
	We also show that simply increasing the number of references is unlikely to resolve this problem,
	and conclude by presenting an alternative reference-less approach based on semantic similarity.
\end{abstract}
\com{
%----------------------------------------------------------------------------------------
%	ACKNOWLEDGEMENTS
%----------------------------------------------------------------------------------------

\begin{acknowledgements}
	\addchaptertocentry{\acknowledgementname} % Add the acknowledgements to the table of contents
	The acknowledgments and the people to thank go here, don't forget to include your project advisor\ldots
\end{acknowledgements}
}
%----------------------------------------------------------------------------------------
%	LIST OF CONTENTS/FIGURES/TABLES PAGES
%----------------------------------------------------------------------------------------

\tableofcontents % Prints the main table of contents

\listoffigures % Prints the list of figures

\listoftables % Prints the list of tables

\mainmatter % Begin numeric (1,2,3...) page numbering

\pagestyle{thesis}
\chapter{Introduction}

% Error correction 
% evaluation in error correction and its centrality
% faithfulness to the source meaning is important, and this has been noted but prev work, and evaluation is geared towards it
% gap in evaluation: however, steps taken to ensure conservativeness in fact push towards formal conservativism by their definition (theoretical claim about the measure)
% this may result in systems that make few changes. indeed we find that this is the case (empirical claim about systems)
%
% we pursue two approaches to overcome this bias.
%
% 1. increasing the number of references. this has been proposed before and pursued with m=2, but no assessment of its sufficiency or its added value over m=1 has been made. In order to address this gap we first charachterize the distribution of possible corrections for a sentence. We leverage this characterization to characterize the distribution of the scores as a function of $m$, and consequently assess the biases introduced by taking $m=1,2$ as with previous approaches. 
% We find that taking these values of $m$ drammatically under-estimate the system scores. 
% We back our analysis of these biases with an analysis of the variance of these estimators.
% We analyze the two commonly used scores, the M2 score often used for evalauted, and the accuracy score commonly used in training.
%
% 2. we note that in fact the important factor is semantic conservativism and explore means to directly assess how semantically conservative systems here through the use of semantic annotation. 
% We use the UCCA scheme as a test case, motivated by HUME.
% First question: is it well-defined on learner language. it is.
% Second question: are corrections in fact semantically conservate? to show that, we need to verify that the corrections make few (if any) semantic changes. our results indicate that this is the case: we show that the corrections are similar in (UCCA) structure to the source.
%
% conclusion (not in intro): we tried to use semantic similarity to improve systems.
% this is difficult due to semantic conservatism. we expect this will be in issue once evaluation is improved.
% future work.
% also future work: use multiple references in training (did people do that?)
%
% sections:
% 1. Introduction
% 2. Formal conservativism in GEC
% 3. First approach: Multiple References
% 3.1. A Distribution of Corrections
% 3.2. Scores (M2, accuracy index, accuracy exact)
% 3.3. Data
% 3.4. Bias of the Scores (setup + results)
% 3.5. Variance of the Scores (setup + results)
% 4. Second approach: Semantic Similarity
% 4.1. Semantic Annotation of Learner Language (prev work)
% 4.2. UCCA Scheme (see HUME)
% 4.3. Similarity Measures (including prev work of elior)
% 4.4. Empirical Validation: IAA, semantic conservativism vs. gold std
% 5. Conclusion
%
% is a challenging research field, which interfaces with many
%other areas of linguistics and NLP. The field
Grammatical Error Correction (GEC) is receiving considerable
interest recently, notably through the GEC-HOO \justcite{dale2011helping,dale2012hoo} and
CoNLL shared tasks \justcite{kao2013conll,ng2014conll}.
Within GEC, considerable effort has been placed on evaluation
\justcite{tetreault2008native,madnani2011they,felice2015towards,napoles2015ground},
a notoriously difficult challenge, in part due to the many valid corrections each learner's language (LL) sentence may
have \justcite{chodorow2012problems}.

An important criterion in the evaluation of correctors during training validation and test times
is their ability to generate corrections that are faithful to the meaning of the source.
In fact, many would prefer a somewhat cumbersome or even an occasionally ungrammatical
correction over a correction that alters the meaning of the source \justcite{brockett2006correcting}.
As a result, often when compiling gold standard corrections for the task,
annotators are instructed to be conservative in their corrections
(e.g., in the Treebank of Learner English \justcite{nicholls2003cambridge}).
There were different attempts to formally capture this precision/recall asymmetry such as the standardized use of $F_{0.5}$ over $F_{1}$ \justcite{dahlmeier2012better} and the choices of weights in I-measure \justcite{felice2015towards}.

However, in development and training penalizing over-correction more harshly than under-correction
may lead to reluctance of correctors to
make any changes (henceforth, {\it over-conservatism}).
Using one or two reference corrections, a common practice in GEC,
compounds this problem, as correctors are not only harshly penalized for making incorrect changes,
but are often penalized for making {\bf correct} changes not found in the reference.

Indeed, we show that current state of the art systems suffer from over-conservatism.
Evaluating the output of 12 recent correctors, we find that all of them
substantially under-predict corrections relative to the gold standard (\S \ref{sec:formal_conservatism}).

We first assess whether the undue penalization of valid corrections can be resolved by increasing the number
of references, which we denote with $M$ (\S \ref{sec:increase-reference}).
We start by estimating the number and frequency distribution of the valid corrections per sentence,
arriving at a mean estimate of over 1000 corrections for sentences of no more than 15 tokens.
We then consider two representative reference-based measures (henceforth, {\it RBMs}) for
assessing the validity of a proposed correction relative to a set of references
and characterize the distribution of their scores as a function of $M$. 
Our results show that both measures substantially under-estimate the true performance of
the correctors. Moreover, they show that increasing $M$ only partially addresses
the incurred bias, as both RBMs approach saturation for $M$ values of 10--20,
indicating that a prohibitively large $M$ may be required for reliable estimation.

Our findings echo the results of \newcite{bryant2015far}, who study the effect of $M$
on evaluation with $F$-score, the most commonly used measure for GEC. Their work focused on
obtaining a more reliable estimate of correctors' performance, and proposed to do so
by normalizing corrector's estimated performance with the performance of a human corrector. However, while such normalization may yield more realistic performance estimates,
it has no effect on the training and tuning of correctors. 

We conclude by proposing an alternative reference-less semantic evaluation approach which assesses the extent to which
a correction faithfully represents the semantics of the source, by measuring the similarity of their semantic structures (\S \ref{sec:Semantics}).
This approach can be combined with a reference-less measure of grammaticality, based on automatic error detection, as
proposed by \newcite{napoles-sakaguchi-tetreault:2016:EMNLP2016}.
Our experiments support the feasibility of the proposed approach,
by showing that (1) semantic structural annotation can be consistently applied to LL, and (2) that the proposed measure is less prone to unduly penalize valid corrections.
%
%
%We define a measure, using the UCCA scheme \justcite{abend2013universal} as a
%test case, motivated by its recent use for machine translation
%evaluation \justcite{birch2016hume}.
%We annotate a section of the NUCLE parallel corpus \justcite{dahlmeier2013building},
%
%The two approaches address the insufficiency of using too few references from
%complementary angles. The first attempts to cover more of the probability
%mass of valid corrections by taking a larger $M$, 
%while the second uses semantic instead of string similarity, in order
%to abstract away from some of the formal variation between different valid corrections.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Over-Conservativism in GEC Systems}\label{sec:formal_conservatism}
%The field of GEC was always thriving or conservatism in its corrections, with the prominent example of using
%$F_{0.5}$ emphasizing precision over recall \justcite{ng2014conll}. we wish to highlight the problem that
%arises from pursuing this conservatism as done today.
%Then, we wished to be conservative, and we achieved that, why shouldn't we rejoice just yet? Theoretically, we might be progressing towards not correcting at all, instead of progressing towards correcting more accurately. 
%
%Manual analysis showed excessive formal conservatism and under correction.
%Albeit important, manual analysis is not enough and we aimed for generating some quantitative measures. 
%
We demonstrate that current correctors
suffer from over-conservatism: they tend to make too few changes to the source.
\section{Notation}
We assume each source sentence $x$ has a set of valid corrections $Correct_x$,
and a discrete distribution $\mathcal{D}_x$ over them, where $P_{\mathcal{D}_x}(y)$
for $y \in Correct_x$ is the probability a human annotator would correct $x$ as $y$.

Let $X$ be the evaluated set of source LL sentences where $X$ consists of the sentences $x_{1}\ldots x_N$, each independently sampled from some distribution $\mathcal{L}$ over LL sentences and denote $\mathcal{D}_{i}\coloneqq \mathcal{D}_{x_i}$.
Each $x_i$ is paired with $M$ corrections $Y_i = \left\{y_{i}^{1},\ldots, y_{i}^{M}\right\}$,
which are independently sampled from $\mathcal{D}_{i}$.\footnote{Our analysis assumes $M$
	is fixed across source sentences. Generalizing the analysis to sentence-dependent $M$
	values is straightforward.}
We define the {\it coverage} of $M$ references for a sentence $x_i$ to be
$P(y \in Y_i|y \in Correct_i)$ for $Y_i$ of size $M$, and $y$ sampled
according to $\mathcal{D}_i$.

A corrector $C$ is a function from LL sentences to proposed corrections (strings).
An assessment measure is a function from $X$, $Y$ and $C$ to
a real number. We use the term ``true measure'' to refer to the measure's output where the references include all possible corrections, i.e., $Y_i=Correct_i$ for every $i$.

\subsection{Experimental Setup.}\label{par:experimental_setup}
We conduct all experiments on the NUCLE dataset,
a parallel corpus of LL essays and their corrected versions,
which is the de facto standard in GEC.
The corpus contains 1,414 essays in LL, each of about 500 words.

We evaluate all participating systems in the CoNLL 2014 shared task,
in addition to two of the best performing systems on this dataset.
The particiapting systems and their abbreviations are: Adam Mickiewicz University (AMU),
University of Cambridge (CAMB), Columbia University and the University of Illinois at Urbana-Champaign (CUUI),
Indian Institute of Technology, Bombay (IITB), Instituto Politecnico Nacional (IPN),
National Tsing Hua University (NTHU), Peking University (PKU), Pohang University of Science and Technology (POST),
Research Institute for Artificial Intelligence, Romanian Academy (RAC), Shanghai Jiao Tong University (SJTU),
University of Franche Comt\'{e} (UFC), University of Macau (UMC), \newcite{rozovskaya2016grammatical}(RoRo), \newcite{xie2016neural} (char).
All are trained and tested on the NUCLE corpus.

We compare the prevalence of changes made to the source by the correctors,
relative to their prevalence in the NUCLE reference.
In order to focus on the more substantial changes, we exclude from our evaluation
all non-alphanumeric characters, both within tokens or as tokens of their own.
%
%In order to have better evaluation of the real goal of corrections we also
%compute all of the measures on ,
%based on the Cambridge First Certificate in English
%(FCE) \justcite{yannakoudakis2011new},
%a new large parallel corpus containing only ungrammatical sentences of learners
%native of different languages.\oa{I didn't understand this sentence; how do we use this corpus?}

\subsection{Measures of Conservatism.}
We consider three types of divergences between the source and the reference.
First, we measure to what extent \emph{words} were changed: altered, deleted or added.
To do so, we compute word alignment between the source and the reference, casting it
as a weighted bipartite matching problem, between the source's words and the correction's. 
Edge weights are assigned to be the edit distances
between the tokens.
We note that aligning words in GEC is much simpler than in machine translation,
as most of the words are kept unchanged, deleted fully, added, or changed slightly.
Following word alignment, we define the {\sc WordChange} measure
as the number of unaligned words and aligned words that were changed in any way.

Second, we quantify word \emph{order} differences using
Spearman's $\rho$ between the order of the words in the source sentence,
and the order of their corresponding words in the correction according to the word alignment.
$\rho=0$ where the word order is uncorrelated, and $\rho=1$ where the orders exactly match. We report the average $\rho$ over all source sentences pairs. 

Third, we report how many source sentences were split and how many 
\begin{figure}
  \centering
  \begin{subfigure}[]{0.4\textwidth}
    \includegraphics[width = \textwidth]{words_differences_heat}
  \end{subfigure}
  \begin{subfigure}[]{0.4\textwidth}
    \includegraphics[width = \textwidth]{aligned}
  \end{subfigure}
  \begin{subfigure}[]{0.4\textwidth}
    \includegraphics[width = \textwidth]{spearman_ecdf}
  \end{subfigure}
  \caption{The prevalence of changes}{\label{fig:over-conservatism}
    The prevalence of changes of different types in correctors' output and in the NUCLE references.
    The top figure presents the number of sentence pairs (heat) for each number of word changes
    (x-axis; measured by {\sc WordChange}) for each of the different systems and the references (y-axis).
    The middle figure presents the number of source sentences (y-axis) concatenated (right bars) or split (left bars) in the references (striped column) and in the correctors' output (colored columns).
    The bottom figure presents the percentage of sentence pairs (y-axis) where the
    Spearman $\rho$ values do not exceed a certain threshold (x-axis).
    See \S \ref{par:experimental_setup} for a legend of the correctors.
    The three figures show that under all measures, the gold standard references make
    substantially more changes to the source sentences than any of the correctors,
    in some cases an order of magnitude more.
  }
\end{figure}
\subsection{Results.}
Figure \ref{fig:over-conservatism} presents the outcome of the three measures. 
%In \ref{fig:split} the amount of sentences each corrector has done is presented. In \ref{fig:words_changed} the accumulated sum of sentences by the words changed in each sentence of each of the correctors is presented. In \ref{fig:rho} the cumulative probability distribution of rho values out of all the sentences.
Results show that the reference corrections make changes to considerably more source sentences than any of the correctors, and within each changed sentence changes more words and makes more word order changes, often an order of magnitude more. For example, the reference has 36 sentences with 6 word changes, where the most sentences with 6 word changes by any corrector is 5.

For completeness, we measured the prevalence of changes in
another corpus, the TreeBank of Learner English \justcite{yannakoudakis2011new},
and the results were similar to those obtained on NUCLE if not more extreme. Being a bit more extreme is not surprising as the two corpora differ in that the TreeBank consists solely of ungrammatical language and NUCLE consists of paragraph (of which $89.6\%$ require corrections).
%While $89.6\%$ of NUCLE sentences need corrections,
%The prevalence of FCE consists only of ungrammatical sentences.
%As expected, FCE is a bit less conservative than NUCLE by our measures.
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Multi-Reference Measures}\label{sec:increase-reference}
%
In this section we argue that the observed over-conservatism of correctors likely stems
from them being developed to optimize RBMs that suffer from low-coverage.
We begin with a motivating analysis of the relation between low-coverage and over-conservatism (\S \ref{subsec:motivating_analysis}).We then continue with an empirical assessment of the distribution of corrections for a given sentence (\S \ref{subsec:corrections_distribution})
and the effect of $M$ on commonly used RBMs (\S \ref{subsec:Assessment-values}).
We discuss the implications of our results, concluding that RBMs may only partially address over-conservatism (\S \ref{subsec:mult_discussion}).
%
\section{Motivating Analysis}\label{subsec:motivating_analysis}
%
The relation between coverage and over-conservatism requires some explanation.
We abstract away from the details of the training procedure, and assume that correctors attempt to maximize an objective function, over some training or development data.

Before moving on, it is important to pay attention to the emphasis here on evaluation \emph{not} for testing. While testing, one would only care whether one system is significantly better than another and would not be able to change anything, hence the test would not affect the behaviour of the model. This was a main interest in recent years and some solutions to problems in that aspect can be found in the work of \newcite{bryant2015far}. Today, there is practically no test set, as public test sets are being used as a benchmark and hence imply which system will get published and which will be further improved or abandoned. This should count as a development set and hence regarded as suffering from the problems we describe below.

Assume the corrector is faced with a phrase which it predicts to be ungrammatical. Assume $p_{detect}$ is the probability that this prediction is correct.
Assume $p_{correct}$ is the probability it is able to predict
a valid correction for this phrase (including correctly identifying it as erroneous).
Finally, assume that the corrector is evaluated
against $M$ references for which the coverage of the phrase is $p_{coverage}$,
namely the probability that
a valid correction will be found among $M$ randomly sampled references.

We will now assume that the corrector may either choose to correct with the correction it finds the most likely or not at all. If it selected not to correct, its probability of being rewarded (i.e., its output is in the reference set $Y$) is $(1-p_{detect})$. Otherwise, its probability
of being rewarded is $p_{correct} \cdot p_{coverage}$.
In cases where

\begin{myequation}
  \label{eq:reward}
  p_{correct} \cdot p_{coverage} < 1-p_{detect} 
\end{myequation}

a corrector is disincentivized from altering the phrase.
We expect Condition \ref{eq:reward} to frequently hold in cases that
require non-trivial changes, which are characterized both by low $p_{coverage}$ (as non-trivial
changes can often be made in numerous ways), and by lower expected performance by the corrector.

Moreover, asymmetric measures (e.g., $F_{0.5}$) penalize invalidly correcting more
harshly than not correcting an ungrammatical sentence.
In these cases, Condition \ref{eq:reward} should be rephrased as

  \begin{myequation*}
    p_{correct} \cdot p_{coverage} - \left(1-p_{correct}p_{coverage}\right) \alpha < 1-p_{detect} 
  \end{myequation*}

where $\alpha$ is the ratio between the penalty for introducing a wrong correction and the reward for a valid correction. 
The condition is much more likely to hold in these cases.

This analysis shows that low coverage is a possible cause for over-conservatism. It remains to see empirically to what extent  over-conservatism is caused by the low coverage. To see that one needs to vary the coverage (M) a system trains on and to assess the levels of conservatism. As the largest corpus we are aware of with a substantial amount of references \justcite{bryant2015far} is NUCLE-test we simulate small-scale training in the following manner:
Using 12 references and a 100-best list \footnote{special thanks to \newcite{rozovskaya2016grammatical} for being the only one to send it to us.} we select the candidates maximizing F-Score given different sizes of M.

\com{Ideally, in order to validate this empirically, we should re-train correctors using multiple references, and re-examine their conservatism. However, corpora annotated with more than one correction are scarce. 
As a proof of concept, we simulate a re-ranking procedure over the corpora of \newcite{bryant2015far}, which provide additional 10 references for each of sentence in the NUCLE test set. In order to abstract away from implementation details and from artefacts that may result from the small dataset available, we explore an oracle re-ranking setting, where the correction with the best Micro F-score taken from the 100-best list of the RoRo state-of-the-art corrector (see Section 2) is selected. The F-score is computed with varying numbers of references (M).}
Our results show a consistent decrease in conservatism in word changes with the increase in coverage and no significant change in word order, clearly, as we only rerank sentences, sentence conservatism was not changed.
\begin{figure}
	\centering
	\includegraphics[width=8cm]{words_differences_hist_reranking}
	\caption{conservatism after oracle reranking}{Amount of sentences changed (y-axis) by the amount of words changed per sentence (x-axis) after oracle reranking over different M values (column colors). 
	}
\end{figure}

\section{Data}
%
Our analysis assumes that we have a reliable estimate for the distribution of corrections
$\mathcal{D}_x$ for the source sentences we evaluate.
Our experiments in the following section are run on a random sample of 52 sentences with a
maximum length of 15 from the NUCLE test data.
Through the length restriction we avoid introducing too many independent
errors that may drastically increase the number of annotations variants (as every combination of corrections for these errors is possible), thus resulting in an unreliable estimation for $\mathcal{D}_x$.
Sentences with less than 6 words were discarded, as they were mostly a result of sentence segmentation errors.

Crowdsourcing has proven effective in GEC evaluation \justcite{madnani2011they,napoles2015ground} and in
related tasks such as machine translation \justcite{zaidan2011crowdsourcing,post2012constructing}. We thus
use crowdsourcing for obtaining a sample from $\mathcal{D}_x$. Specifically, for each of the 52 source
sentences, we elicited 50 corrections from Amazon Mechanical Turk workers.
%allowing for a reliable estimation of the distributions.
Aiming to judge grammaticality rather than fluency, we asked the workers to
correct only when necessary, not for styling.
4 sentences did not require any correction according to almost half the workers and were hence discarded.
%
\section{Estimating The Distribution of Corrections}\label{subsec:corrections_distribution}
%
We begin by estimating $\mathcal{D}_x$ for each sentence, using the crowdsourced corrections.
We use {\sc UnseenEst} \justcite{zou2015quantifying}, a non-parametric algorithm that
estimates a multinomial distribution,
in which the individual values do not matter, only the distribution of probabilities
across values.%\footnote{\href{https://github.com/borgr/unseenest}{UnseenEst}} 
{\sc UnseenEst} was originally developed for assessing how many
variants a gene might have, including undiscovered ones,
and their relative frequencies.
This is a similar setting to the one tackled here.
Our manual tests of {\sc UnseenEst} with small artificially created frequencies
showed satisfactory results.\footnote{All data we collected, along with the estimated distributions will be made publicly available}

By the estimates from {\sc UnseenEst}, most source sentences have a large number of
corrections with low probability accounting for the bulk of the probability mass
and a rather small number of frequent corrections.
%The estimated distributions tend to have steps, with many corrections with the same (low) frequency.
Table \ref{tab:corrections_dist} presents the mean numbers of different corrections with frequency at least
$\gamma$ (for different values of $\gamma$), and their total probability mass.
For instance, on average 74.34 corrections account for 75\% of the total probability mass of the corrections, each
occurring with a frequency of 0.1\% or higher.

\begin{table}[h!]
  \centering
  \singlespacing
  \begin{tabular}{c|c|c|c|c|}
    %\cline{2-5} 
    & \multicolumn{4}{c|}{Frequency Threshold ($\gamma$)}\\ 
    %\cline{2-5} 
    & \multicolumn{1}{c}{0} & \multicolumn{1}{c}{0.001} & \multicolumn{1}{c}{0.01} & \multicolumn{1}{c|}{0.1}
    \\
    \hline
    Variants & 1351.24 & 74.34 & 8.72 & 1.35
    \\
    Mass & 1 & 0.75 & 0.58 & 0.37\\
    \hline
  \end{tabular}
  \caption{Corrections distribution - mass and number of variants}{\label{tab:corrections_dist}
    Estimating the distribution of corrections $\mathcal{D}_x$.
    The table presents the mean number of corrections per sentence with probability of more than
    $\gamma$ (top row), as well as their total probability mass (bottom row).
  }
\end{table}

The overwhelming number of rare corrections raises the question whether these can be regarded as noise. To check that we asked crowdsource annotators for 3 judgments on each proposed correction, asking whether it is a correction the original. We calculated the mean inter-annotator agreement (IAA) of sentences by their frequency in the proposed corrections (empirical distribution), expecting to see a steep decrease of the less frequent ones if most of them are noise. The results show this is not the case, showing even the rarest ones have a high mean IAA of $0.78$.
\begin{figure}
	\centering
	\includegraphics[width=8cm]{IAA_confirmation_frequency}
	\caption{IAA of corrections}{mean IAA of corrections by their frequency in the empirical distribution.
	} \label{fig:accuracy_vals}
\end{figure}

\section{Under-estimation as a function of M} \label{subsec:Assessment-values}
In the previous section we presented empirical assessment of the distribution of corrections to a sentence. We turn to estimate the resulting bias, the under-estimation of RBMs, for different $M$ values. 

We discuss two similarity measures. One is the sentence-level accuracy
(also called ``Exact Match'') and the other is the GEC $F$-score.

\subsection{Sentence-level Accuracy.}
Sentence-level accuracy (also ``Exact Match'') is the percentage of corrections that
exactly match one of the references.
Accuracy is a basic, interpretable measure, used in GEC by, e.g. \newcite{rozovskaya2010annotating}.
It is closely related to the 0-1 loss function commonly used
for training statistical correctors \justcite{chodorow2012problems,rozovskaya2013joint}. 

Formally, given test sentences $X=\{x_1,\ldots,x_N\}$,
their references $Y_1,\ldots,Y_N$, and a corrector $C$,
we define $C$'s accuracy to be

\begin{myequation}\label{eq:acc_def}
Acc\left(C;X,Y\right) = \frac{1}{N} \sum_{i=1}^N \mathds{1}_{C(x_i) \in Y_i}.
\end{myequation}

Note that $C$'s accuracy is in fact an estimate of $C$'s probability to produce
a valid correction for a sentence, or $C$'s {\it true accuracy}. Formally:

\begin{myequation*}
 TrueAcc\left(C\right) = P_{x\sim{L}}\left(C\left(x\right)\in Correct_x\right).
\end{myequation*}
%
%We estimate $C$s quality by sampling a set of source sentences
%$x_1,\ldots,x_N \sim \mathcal{L}$, and evaluate the quality of $C(x_1),\ldots,C(x_N)$ relative
%to the source. 

The bias of $Acc\left(C;X,Y\right)$ for a sample of $N$ sentences, each paired with $M$ references
is then

\begin{flalign}
&TrueAcc\left(C\right) - \mathbb{E}_{X,Y}\left[Acc\left(C;X,Y\right)\right] = &\\
&TrueAcc\left(C\right) - P\left(C\left(x\right) \in Y\right)  = &\\
&Pr\left(C\left(x\right) \in Correct_x\right)  \cdot 
\label{eq:bias} \left(1 - Pr\left(C\left(x\right) \in Y \vert C\left(x\right) \in Correct_x\right) \right)&\\
\end{flalign}

We observe that the bias, denoted $b_M$, is not affected by $N$, only by $M$.
As $M$ grows, $Y$ approximates $Correct_x$ better, and $b_M$ tends to 0.

In order to gain insight into the evaluation measure and the GEC task
(and not the idiosyncrasies of specific systems), we consider an idealized learner,
which, when correct, produces a valid correction with the same
distribution as a human annotator (i.e., according to $\mathcal{D}_x$).
Formally, we assume that, if $C(x) \in Correct_x$ then $C(x) \sim \mathcal{D}_x$.
Hence the bias $b_M$ (Equation \ref{eq:bias}) can be re-written as

\begin{myequation*}
  \centering
  P(C(x) \in Correct_x) \cdot (1 - P_{Y \sim \mathcal{D}_i^M,y\sim \mathcal{D}_x}(y \in Y))
\end{myequation*}

We will henceforth assume that $C$ is perfect (i.e., its true accuracy $Pr\left(C(x) \in Correct_x\right)$ is 1).
Note that assuming any other value for $C$'s true accuracy
would simply scale $b_M$ by that accuracy.
Similarly, assuming only a fraction $p$ of the sentences require correction scales $b_M$ by $p$.
%
%Denote the bias of a perfect corrector with $b_M$. To recap:
%\begin{equation*}
%  b_M = 1 - P_{x \sim L, Y \in \mathcal{D}_x^M, y \sim \mathcal{D}_x}\left(y \in Y\right)
%\end{equation*}
%
%We turn to estimating $b_M$ empirically. We note that $Acc(C;X,Y)$
%is a sum of Bernoulli variables (i.e., a Poisson Binomial distribution), 
%with probabilities $p_i = P_{y \sim \mathcal{D}_i}\left(y \in Y_i\right)$.

We estimate $b_M$ empirically using its empirical mean on our experimental corpus:

\begin{myequation*}
\hat{b}_M = 1 - \frac{1}{N}\sum_{i=1}^N P_{Y \sim \mathcal{D}_i^M, y \sim \mathcal{D}_i}\left(y \in Y\right)
\end{myequation*}

Using the {\sc UnseenEst} estimations of $\mathcal{D}_i$, we can compute $\hat{b}_M$
for any size of $Y_i$ (value of $M$). 
However, as this is highly computationally demanding, we estimate it using
sampling. Specifically, for every $M = 1,...,20$ and $x_i$, we sample $Y_i$ 1000 times
(with replacement), and estimate $P\left(y \in Y_i\right)$ as the covered probability mass
$P_{\mathcal{D}_i}\{y: y \in Y_i\}$.

We repeated all our experiments where $Y_i$ is sampled without replacement,
in order to simulate a case where reference corrections are collected by a single
annotator, and are thus not repeated. We find similar trends with faster increase
in accuracy reaching above $0.47$ with $M=10$.

%
%The resulting estimates for $p_i$ 
%define the estimate for the distribution of $Acc(C;X,Y)$.
%Given a set of LL sentences $x_1,...,x_N$ and their corresponding references
%$Y_1,...,Y_N$, we define the coverage of the reference set $Y_i$ for the sentence $x_i$ to be
%
%\begin{equation*}
%Cov\left(x_i,Y_i\right)=.
%\end{equation*}
%
%In order to gain insight into the accuracy measure, we need to know something about the distribution from which the given corrector chooses valid corrections. As each corrector might have its own biases, the most appealing choice would be to evaluate a corrector in which this distribution is the same as the one from which corrections for the gold standard are being drawn from. Formally, if $C\left(x_i\right) \in Correct_i$ then $C\left(x_i\right) \sim \mathcal{D}_i$. 
%
%Thus, the second term in Equation \ref{eq:correction-in-gs} is $p_i = \mathbb{E}_{Y_i}[Cov(x_i,Y_i)]$. 
%Therefore $Acc(C;X,Y)$ is distributed as
%a Poisson Binomial random variable (divided by $N$), with probabilities $\{p_i \cdot CP\}_{i=1}^N$. \footnote{A Poisson Binomial random 
%variable is a sum of Bernoulli variables with different success probabilities.} We also assume our corrector is always 
%correct (so $CP=1$), but as noted earlier any other value for $CP$ would only scale the results by $CP$.

\begin{figure}
  \centering
  \includegraphics[width=8cm]{noSig_repeat_1000_accuracy}
  \caption{Changes in accuracy with M}{Accuracy and Exact Index Match values for a perfect corrector (y-axis)
    as a function of the number of references $M$ (x-axis).
    %Each data point is paired with a confidence interval ($p=.95$).     
  } \label{fig:accuracy_vals}
\end{figure}

Figure \ref{fig:accuracy_vals} presents the expected accuracy values for our perfect
corrector (i.e., 1-$\hat{b}_M$) for different values of $M$. 
Results show that even for values of $M$ which are much larger than those considered in the GEC literature (e.g., $M=20$),
the expected accuracy is only about 0.5. As $M$ increases the contribution of each additional correction
  gets smaller to the point it contributes little to the accuracy (the slope is about 0.004 around $M=20$).

We also experiment with a more relaxed measure, {\it Exact Index Match}, which is only sensitive
to the identity of the changed words and not to what they were changed to. 
Formally, two corrections $c$ and $c'$ over a source sentence $x$ match
if for their word alignments with the source (computed as above) $a:\{1,...,\left|x\right|\} \rightarrow \{1,...,\left|c\right|,Null\}$
and $a':\{1,...,\left|x\right|\} \rightarrow \{1,...,\left|c'\right|,Null\}$, it holds that $c_{a\left(i\right)} \neq x_{i}$ iff $c'_{a'\left(i\right)} \neq x_{i}$, where $c_{Null}=c'_{Null}$.

Figure \ref{fig:accuracy_vals} also presents the expected accuracy in this case
for different values of $M$, which indicate that while scores of a perfect corrector are somewhat higher,
still with $M=10$ is 0.54.
As Exact Index Match can be interpreted as an accuracy measure for error detection (rather than correction),
our results indicate that error detection systems may suffer from similar difficulties.

The analytic tools ws have developed support the computation of the entire distribution of the accuracy,
and not only its expected values. From Equation \ref{eq:acc_def} we see that Accuracy has a Poisson Binominal distribution (i.e., it is a sum of independent Bernoulli variables with different success probabilities), whose success probabilities are $P_{y,Y \sim \mathcal{D}_i}(y \in Y)$, which can be computed, as before, using {\sc UnseenEst}'s estimate for $\mathcal{D}_i$. Estimating the density function allows for the straightforward definition of significance tests for the measure, and can be performed efficiently \justcite{hong2013computing}.\footnote{An implementation of this method and the estimated density functions will be released publicly.}
\lc{read until here}
\subsection{$F$-Score.}
While accuracy is commonly used as a loss function for training GEC systems,
the $F_\alpha$ score is standard when reporting system performance (and consequently in hyper-parameter
tuning).

Computing $F$-score for GEC is not at all straightforward.
The score is computed in terms of {\it edit} matches between a correction and the references,
where edits are sub-strings of the source that are replaced in the correction/reference.
HOO shared task used an earlier version of $F$-score, which required that the proposed corrections include edits explicitly.
Later on, relieving correctors from the need to produce edits, $F$-score was redefined optimistically, maximizing
over all possible annotations that generate the correction from the source.\footnote{Since our crowdsourced corrections
	do not include an explicit annotation of edits, we produce edits heuristically.}
$M^2$ \justcite{dahlmeier2012better} was designated to compute this $F$ score and is the standard evaluation for GEC.

The complexity of the measure prohibits an analytic approach, and
we instead use a bootstrapping approach to estimate the bias incurred
by not being able to exhaustively enumerate the set of valid corrections.
%In short, bootstrapping methods sample with repetition from the empirical
%distribution of the observed data to estimate properties (e.g. confidence-interval)
%of the statistic (e.g. $F$-score) over the distribution. 
As with accuracy,
in order to avoid confounding our results with system-specific biases,
we assume the evaluated corrector is perfect and samples its corrections from the human distribution of corrections $\mathcal{D}_x$.
This experiment is very similar to that of \newcite{bryant2015far},
who also compared the $F$-score of a human correction against an increasing number of references, although they exclusively addressed $F$-score and did not attempt to estimate the distribution of correction as we do here.

Concretely, given a value for $M$ and for $N$, we uniformly sample from our experimental
corpus source sentences $x_1,...,x_N$, and $M$ corrections for each $Y_1,...,Y_N$ (with replacement).
Setting a realistic value for $N$ in our experiments is important
for obtaining comparable results to those obtained on the NUCLE corpus (see below), 
as the expected value of $F$-score may depend on $N$ (unlike Accuracy, it is not additive).
In accordance with the NUCLE's test set,
we set $N=1312$ and assume that 136 of the sentences require no correction.
The latter reduces the overall bias by their frequency in the corpus,
and are thus important to include for obtaining realistic results.

The bootstrapping procedure is carried out by the
accelerated bootstrap procedure \justcite{efron1987better}, with 1000 iterations.
We also report confidence intervals ($p=.95$), computed using the same procedure.\footnote{We
  use Python scikits.bootstrap implementation.}
%
%For each sentence which had at least one error according to the NUCLE gold standard
%we sample $M$ sentences uniformly from the
%gathered empirical data to replace it. We leave sentences that do not need
%corrections untouched. This results in reference texts accounting for the
%variability in different choices of corrections while approximating the reduction of variability
%of a big $N$ by consisting of $N$ sentences overall.

% our results
Figure \ref{fig:F_Ms} presents the results of this procedure, which
further indicate the insufficiency of commonly used $M$ values for training and development (1 or 2)
for obtaining a reliable estimation of a corrector's performance.
For instance, the $F_{0.5}$ score for our perfect corrector, whose true $F$-score is 1,
is only 0.42 with $M=2$.
Moreover, the saturation effect observed for accuracy is even more pronounced with our experiments on $F$-score.
Similar results were obtained by \newcite{bryant2015far}.
%
%\subsection{}
%While our experiments focus on the accuracy and $F$-score measures, we expect
%our results to generalize to other RBMs (see Section \ref{sec:prev_work}).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Significance of Real-World Correctors}\label{sec:real_world}
The bootstrapping method for computing the significance of the $F$-score can also
be useful for assessing the significance of the differences in corrector's performance
reported in the literature.
We report results with the bootstrapping protocol (\S \ref{subsec:Assessment-values})
to compute the confidence interval of different correctors with the current NUCLE
test data ($M=2$).
\begin{figure}
	\centering
  \includegraphics[width=8cm]{$F_{0.5}$_Ms_significance}
  \caption{Changes of $F_{0.5}$ by M}{
    $F_{0.5}$ values for a perfect corrector (y-axis) as a function of the number of references $M$ (x-axis).
    Each data point is paired with a confidence interval ($p=.95$).\label{fig:F_Ms}}
\end{figure}

\begin{figure}
	\centering
  \includegraphics[width=8cm]{$F_{0.5}$_significance}
  \caption{Evaluation of current systems}{$F_{0.5}$ values for different correctors, including confidence interval ($p=.95$).
    The left-most column (``source'') presents the $F$-score of a corrector that doesn't make any
    changes to the source sentences.
    See \S \ref{par:experimental_setup} for a legend of the correctors.\label{fig:F_correctors}}
\end{figure}

Figure \ref{fig:F_correctors} shows our results, which present a mixed picture: some
of the differences between previously reported $F$-scores are indeed significant and some are not.
For example, the best performing corrector is significantly better than the second, but the latter
is not significantly better than the third and fourth.

%Nevertheless, it seems that $M=2$ value taken in NUCLE is sufficiently high
%to generally obtain statistically significant ranking of the different correctors.

\section{Discussion}\label{subsec:mult_discussion}
% -- we saw that we have dramatic under-estimation
% -- but is this a problem? for instance, in the last section we saw we can get statistical significance between systems by increasing
%    N even with a low M
% -- balancing $N$ and $M$ is important;
%      other people have looked at similar things (not to re-label or not to re-label). we stress that
%      while for statistical significance increasing $N$ is sufficient, this would not solve this problem:
% -- low coverage entails other problems: it incentivizes systems not to correct, even if they can perfectly predict valid corrections.
% -- mathematical argument
% -- indeed, we see RoRo > Perfect and other systems are close to Perfect. it could be that they are better taylored to
%    those corrections produced by the NUCLE annotators. however in section 2 we saw that they are not.
%    we hypothesize that this is the reason.
%

Our empirical results show that the number of corrections needed for reliable reference-based measures may
be prohibitively large in practice.
Results suggest that there are hundreds of valid corrections with low probability, whose total probability mass
is substantial. RBMs such as accuracy and $F$-score thus show diminishing returns from increasing the value of $M$ over values of about 10.
%
%All these findings suggest that it is too costly to increase $M$ in development data to the extent asymmetric evaluation will not lead to over-conservatism. The exact index match analysis also suggests $M=1,2$ coverage is also low for detection. When detection is separate from correction this might result in over-conservatism. 
%
%about a quarter of the probability mass of valid corrections (\S \ref{subsec:Assessment-values}).
%
%The factors controlling significance are two. Variation across sentences themselves (different $D_x$)
%which is reduced with $N$ and the variation across choices of corrections which might be reduced with
%either $M$ or $N$. One can rightly deduce that large $N$ is sufficient for variation, but it will not
%solve the other problems: under-estimation of true performance,
%over-conservatism, possible issues when training systems, and might be more costly than annotating
%a larger $M$ without acquiring more sentences and also annotating them.
%Choosing how to balance is dependent on the goals of the one collecting data, and affects over
%the mean value as well, as discussed in \ref{subsec:Assessment-values}. Thus, we bring supporting data and
%leave the decision to the reader. We just point out that such balancing questions have been studied in
%various fields such as genetics \justcite{ionita2010optimal}.\oa{}

Returning to condition \ref{eq:reward}(\S \ref{subsec:motivating_analysis}), we find that the coverage
(which is equal to the accuracy depicted in Figure \ref{fig:accuracy_vals})
is lower than 0.5 for $M=2$ on average (for short sentences). For cases of non-trivial
changes, we expect it might be even lower, suggesting that condition \ref{eq:reward} often
holds in practice, incentivizing over-conservatism.

Considering the $F$-score of the best performing systems in Figure \ref{fig:F_correctors}, and
comparing them to the $F$-score of a perfect corrector with $M=2$, we find that their scores are comparable,
where RoRo in fact surpasses a perfect corrector's $F$-score.
While it is possible that these correctors outperform the perfect corrector by learning how to
correct a sentence in the same way as one of the NUCLE annotators did, we view this possibility
as unlikely as our results (\S\ref{sec:formal_conservatism}) show that
the output of these systems considerably diverges from NUCLE's references.
A more likely possibility is that these systems' high performance relative to a perfect corrector's
is due to these correctors having learned to predict when not to correct.

Two recent RBMS have been proposed.
One is {\sc I-measure} \justcite{felice2015towards}
which introduces novel features to GEC evaluation, such as distinguishing
different quality levels of ungrammatical corrections (e.g., some improve the quality of
the source, while others degrade it), and restricting edits to only consist of single words,
rather than phrases. The other is GLEU \justcite{napoles2015ground} (an adaptation of BLEU) that has
been shown to correlate well with human rankings. We expect that our findings, that RBMs substantially under-estimate the
performance of correctors, to generalize to these RBMs, as they all
apply string similarity measures relative to a fairly small number of references.
These measures thus address orthogonal gaps in GEC evaluation from the ones presented here.
Following the proposal of \newcite{sakaguchi2016reassessing}, to emphasize fluency over grammaticality
in reference corrections, only compounds this problem, as it results in a larger number of valid corrections.

%Also, changing from grammatical corrections to fluency ones results in more possible corrections, and consequently a larger bias.

Finally, note that addressing under-estimation by comparing to
a human expected score (in our terms, a perfect corrector) with the same $M$ \justcite{bryant2015far} does not address over-conservatism, as it only
scales the original measure. Moreover, as seen above, a human correction's score
is not necessarily an upper bound, as an over-conservative corrector may surpass a perfect corrector in performance.

%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Semantic Faithfulness Measure}\label{sec:Semantics}
%
%
%Conservatism is considered an important trait for a corrector, reflected for example
%in the selection of $F_{0.5}$, which emphasizes precision over recall, as the
%standard evaluation measure in GEC.
%In the previous section we followed the common approach in GEC evaluation and evaluated
%
%The thought that stands behind such emphasis is that a user
%would be understanding towards errors he did, of which he is probably
%not even aware, not being corrected, but would not be so understanding
%of corrections altering what he meant to say, in a way he perceives as wrong.
%

In this section we propose new measures that eschews the use
of reference corrections, instead measuring the semantic faithfulness of the proposed
correction to the source.
Concretely, we propose to measure the semantic similarity of the source and the proposed correction
through the graph similarity of their representations.
Such a measure has to be complemented with an
error detection procedure, as it only captures faithfulness, the extent to which
the meaning of the source is preserved in the correction,
and not its grammaticality.
See \newcite{napoles-sakaguchi-tetreault:2016:EMNLP2016}
for a proposal of a complementary measure based
on automatic error detection.

A similar approach was also taken in the field of machine translation, after showing multiple references are better for evaluation, but costly\justcite{albrecht-hwa:2008:WMT,turian2006evaluation}. Several ways to capture semantics (adequacy) and to achieve reference-less machine translation evaluation were proposed and shown to be at least as reliable the reference based ones.\justcite{reeder2006measuring,albrecht2007regression,specia2009estimating,specia2010machine} Perhaps most similar is the work of \newcite{banchs2015adequacy}, combining a semantic and grammatical measures.


As a test case, we use the UCCA scheme to define semantic structures \justcite{abend2013universal},
motivated by its recent use in semantic machine translation evaluation \justcite{birch2016hume}.

We conduct some experiments supporting the feasibility of our approach.
We show that semantic annotation can be consistently applied to LL,
through inter-annotator agreement (IAA) experiments and that a perfect corrector scores high on this measure.

%As semantic structures represent an abstraction over different realizations
%of a similar meaning,  In fact, $M$ plays no role in this approach, as the measure
%is defined not relative to a refernce but relative to the source sentence.
%
%as LL consists of many grammatical mistakes that makes syntactic
%analysis ill-defined for the task. We show evidence that this is the case, by having
%two annotators annotate a sub-corpus from the NUCLE dataset, and by measuring their
%inter-annotator agreement.
%%%Second, we ask whether corrections for a sentence indeed need to be faithful to the source. We seek to answer this question by measuring
%the semantic similarity between the source and the reference. We show support for an affirmative answer to this question 
%by annotating the references provided for the NUCLE dataset,
%and detecting high semantic similarity between the corresponding sentences on both sides. 
%
%\section{Background}
%
%Reliable assessment by a gold standard might be hard to obtain (see
%\ref{sec:increase-reference}), and human annotation for each output
%is great \justcite{madnani2011they} but costly, especially considering the 
%development process. Under these conditions,
%%given a reliable semantic annotation we can enhance the reliability of our assessment. A simple way to do it is to somehow account in the assessment score for semantic changes. 
%Another, more ambitious way to do that might be to decouple the meaning
%from the structure. We propose a broad idea for a reduction from grammatical
%error detection and a comparable semantics annotation to grammatical
%error correction assessment. Lets assume we have both a reliable error
%detection tool and a good way to measure semantic changes. Then, we
%can transform assessment to a 3 steps assessment. 
%Step one, detect errors in the original text. Assess the amount of needed corrections, and the percentage of which that were changed.
%Step two, assess how much did the semantics change.
% Give a negative score for changing semantics.
%Last step, use
%the error detection again to assess how many errors exist in the correction
%output, whether uncorrected by the corrector or new errors presented
%by the correction process itself. 
%
%This assessment was partially inspired by the WAS evaluation scheme \justcite{chodorow2012problems},
%in short it states we should account in the assessment for 5 types,
%not only the True\textbackslash{}False Positive\textbackslash{}Negative
%but also for the case where the annotation calls for a correction,
%and the corrector did a correction, but one that is unlike the annotation's
%one. With the proposed assessment we can measure how many of the corrections
%were corrected correctly (First + Second), and how many errors do
%we have eventually (Third) and combine them to get something similar
%to the Precision Recall that is widely used. We can also account for
%the places where the error was detected and check if it was corrected
%in a way that makes it grammatical and did not change semantics, the
%fifth type. We do that without getting a human to confirm this is
%indeed a correction.
%
%This system would be even more informative than the current one. Allowing assessment of
%what subtask exactly did the corrector fail to perform. Answering questions
%like: was the corrector too conservative and did not make enough corrections?
%Was it making changes in the right places but not correcting grammar successfully?
% as the corrector correcting grammar but changing things
%it was not supposed to? etc.
%
%Semantic structures were used for LL tasks \justcite{king2013shallow}, but so far not to GEC. Some syntactic representations were suggested for this task, and as they are popular for structural representation we devote the next section to discuss them. Specifically we explain, why, apart from not being based on semantics, syntactic representation is not a good fit for LL and in particular not for enhancing the evaluation without enlarging reference number.
%
\section{Structural Representation in LL}
%
%The usefulness of syntactic parsing in NLP has encouraged a number of previous
%projects to define syntactic annotation for LL.
While linguistic theories propose that each learner makes consistent use of syntax \justcite{huebner1985system,tarone1983variability}, this use may not conform to the syntax of the learned language, or of any other known language. This entails difficulties in defining syntactic annotation for LL, as, on the face of it, the language of each learner has to be annotated in its own terms.

LL resources annotate syntactic errors in different ways.
\newcite{berzak2016universal} and \newcite{ragheb2012defining}
annotate according to the syntax used
by the learner, even if this use is not grammatical.
Such annotation may be unreliable as a source of semantic information, as semantically similar sentences, formulated by different learners, may have considerably different structures. \newcite{nagataphrase} take an opposite approach, and attempt
to be faithful to the syntax intended by the learner. However, such an approach faces difficulties due to the multitude of different syntactic structures that can be used to express a similar meaning.
%
%Syntactic representation is very popular and useful in many NLP tasks 
%\justcite{mesfar2007named,ng2002improving,zollmann2006syntax}.
%Thus, one thought that comes to mind is to use grammar annotation 
%for LL.
%While not useless, grammatical approach is not well
%defined, and unclear both practically and theoretically.

In this section, we use semantic annotation to structurally
represent LL text. Semantic structures are faithful to the intended
meaning of the sentence, and not to its formal realization, and thus face
less conflicts where the syntactic structure used diverges from
the one intended. We are not aware of any previous attempts to semantically
annotate LL text.

\subsection{UCCA.}\label{sec:ucca}
UCCA is a semantic annotation scheme that builds on
typological and cognitive linguistic theories.
The scheme's aims are to provide a coarse-grained, cross-linguistically
applicable representation.
Importantly, UCCA's categories directly reflect semantic, rather than
distributional distinctions.
For instance, UCCA is not sensitive to POS distinctions:
a Scene's main relation can be a verb but also an adjective
(``He is {\bf thin}'') or a noun (``John's {\bf decision}'').
Indeed, \newcite{sulem2015conceptual} have found that UCCA structures are
preserved remarkably well across English-French translations. 

UCCA structures are directed acyclic graphs, where the words in the text 
correspond to (a sub-set of) their leaves.
The nodes of the graphs, called {\it units}, are either leaves or several elements jointly
viewed as a single entity according to some semantic or cognitive consideration.
The edges bear one or more categories, indicating the role of 
the sub-unit in the relation that the parent represents.

UCCA views the text as a collection of {\it Scenes} and relations between them.
A Scene, the most basic notion of this layer, describes a movement, 
an action or a state which is persistent in time.
Every Scene contains one main relation, 
zero or more {\it Participants}, 
which are interpreted in a broad sense, 
and include locations, destinations and complement clauses,
and {\it Adverbials}, such as temporal descriptions.

\section{Experimental Setup}
We employ two annotators, and trained them by annotating both LL and standard English
passages, until a high enough agreement has been reached (a total of 6 hours of training).
Training passages were excluded from the evaluation.
We use UCCA's annotation guidelines\footnote{\url{http://www.cs.huji.ac.il/~oabend/ucca.html}} without any adaptations.

We experiment on 7 essays and their corrections from NUCLE, each of about 500 tokens.
In order to measure IAA, we assigned 4 of these essays to both annotators
and compute their agreement.
In order to measure the faithfulness score for a perfect corrector, we annotate both the source and the corrected version for 6 essays, some of which were annotated by both annotators.
%
%For the different experiments 20 paragraphs were annotated, a table with the full
%information can be found in the appendix \ref{tab:annotated-paragraphs}.Overall, 2 LL
%and 2 corrected paragraphs were annotated by both annotators, 9 parallel paragraphs were
%annotated by the same annotator and 6 by different annotators.
%
%We see that as enough to be a proof that UCCA can be applied to LL, especially considering those numbers
%are a bit higher than the IAA originally reported
%for native English .
%We explain the rise in agreement by the fact that the guidelines and
%procedures were refined since UCCA was first introduced and not to
%superiority of UCCA for annotating LL. A similar F1
%score for IAA (0.849) over corrected paragraphs
%suggests the same.
%
%At least theoretically, semantics are well defined even on ungrammatical
%text. With the right tools we might capture at least some of the semantics
%of sentences and use them for the same purposes of grammatical annotation.
%In this work we will use Universal Conceptual Cognitive
%Annotation (UCCA)\justcite{abend2013universal}, we will show that practically
%there are semantic annotation schemes that can be used for the purposes discussed.
%
%
\section{Semantic Similarity Measures}
\subsection{IAA Measure.} We define a similarity measure over UCCA annotations 
$G_1$ and $G_2$ over the same set of leaves (tokens) $W$.
For a node $v$ in either graph, define its yield $yield(v) \subseteq W$ as its
set of leaf descendants.
Define a pair of edges $(v_1,u_1) \in G_1$ and $(v_2,u_2) \in G_2$ to be matching
if $yield(u_1) = yield(u_2)$ and they have the same label.
Labeled precision and recall are defined by dividing the number of matching edges
in $G_1$ and $G_2$ by $|E_1|$ and $|E_2|$, respectively, and
the {\it DAG $F$-score} is their harmonic mean.
We note that the measure collapses to the common parsing $F$-score if $G_1$ and $G_2$ are trees.

Computing a faithfulness
measure is slightly more involved, as the source sentence graph $G_s$ and its
correction $G_c$ do not share the same set of leaves. As no such a measure was previously suggested for UCCA similarity we created several such measures. We also considered standard graph similarity measures such as graph kernels but this direction was abandoned being more directed towards much larger graphs.

%Giving a more accurate
%measure than the upper bound suggested by \justcite{sulem2015conceptual} for
%comparing two parallel texts in different languages, while keeping
%the essence of comparing how many of the aligned nodes conserve meaning and tag. For that we may think for a moment on GEC as
%translation from LL to Proper English, and a good translation
%would be a translation which keeps the meaning but has the syntax
%of English. Considering that, just like in translation, we can align words from the LL to the corresponding words in English
%and keep record of how many of those nodes kept their labels.
%
%As comparing labels is trivial, and done before us. We should focus on how we propose to align nodes. 
%First, note that comparison should not be at
%the token level, as we want to allow tokens to be corrected - replaced or removed -
%as long as the higher structures convey the same meaning. We thus
%prune the labels above the leaves, the tokens of the sentence. To
%define an alignment of the nodes, we suggest some possible ways, all
%based on first aligning the words in order to give order to the DAG and then comparing the structure in one way or another.
%
% fully aligned
\subsection{IAA Semantic Faithfulness Measure}
We assume a (possibly partial, possibly many-to-1) alignment between $G_s$ and $G_c$,
$A \subset V_s \times V_c$. An edge $(v_1,v_2) \in E_c$ is said to match an edge
$(u_1,u_2) \in E_s$ if they have the same label and $(v_2,u_2) \in A$. Recall (Precision)
is defined as the ratio of edges in $E_s$ ($E_c$) that have a match in $E_c$ ($E_s$) respectively, and
$F$-score is their harmonic mean. We note that this measure indeed collapses to the
DAG $F$-score discussed above where $A$ includes all pairs of nodes in $E_s$ and $E_c$ that have
the same yield.

In order to define full alignment between $V_s$ and $V_c$, we begin by aligning the leaves
(tokens) in $V_s$ and $V_c$ using the same method detailed in \S \ref{sec:formal_conservatism}.
Denote the resulting leaf alignment with $A_l \subset Leaves_s \times Leaves_c$.
We now extend $A_l$ to define the node alignment $A$, aligning each non-leaf $v \in V_s$
with the node $u \in V_c$ that maximizes

\begin{myequation*}
w\left(v,u\right) = \frac{\vert A_l \cap \left(yield\left(u\right) \times yield\left(v\right)\right)\vert}{\vert yield\left(u\right) \vert}.
\end{myequation*}

%We cast the problem of finding a node alignment as a maximum weighted bipartite matching problem between
%the set of nodes $V_s$ and the set $V_c$, where the weight of an edge $(u,v) \in V_s \times V_c$ is
%defined to be 
%$A$ is defined to be the maximum weighted matching, excluding edges
%with weight 0.\oa{why do we use many-to-1? {\bf this doesn't make sense because it favors
%nodes up the tree. better to normalize}}
We exclude from $A$ pairs $v,u$ such that $w(v,u)=0$.
The resulting $F$-score measure, using the resulting $A$ is called UCCA Similarity ({\sc UCCASim}).
As the resulting alignment may differ when aligning nodes from $V_c$ to $V_s$
and the other way around, we report the resulting $F$-score in both directions.

Note that {\sc UCCASim} is somewhat more relaxed than DAG $F$-score defined above,
as it also aligns nodes whose yields are not in perfect alignment with one another,
unlike DAG $F$-score which requires a perfect match.
While this relaxation is necessary, given that corrections often add
or remove nodes, thus eliminating the possibility of a perfect alignment,
in order to obtain comparable IAA scores, we report IAA using {\sc UCCASim} as well. This measure, is the most similar to the IAA Measure. Hence, it was the measure of choice for the following experiments. In the future, it might be useful to compare different measures according to the tasks at hand.

\subsection{Top down \label{pa:top-down}}
Top down measure is the maximum cut of matched nodes having all their parents matched as well. To compute, we start with the passages, the DAGs' heads inside $U$, the list of unchecked candidates and $S$ the cut empty. For each node pair $v_1, v_2$ in $U$ we align using the children as $V_s$ and $V_c$, add $v_1, v_2$ to $S$ and all children that have an alignment to $U$.

\subsection{Token similarity based}
\newcite{sulem2015conceptual} suggested some of the relations in UCCA are better defined than others. Thus, it suggests looking mainly at those (scenes, adverbial, participant, state, process), we computed this relaxed similarity with full alignment used by UCCASim, top-down and bottom up alignments.

Bottom up alignment is done by taking all nodes which have terminals as children to be $V_s$ and $V_c$, aligning them, and then doing the same with their parents if possible.

\subsection{Tree distance}
We use the same relaxed alignment as above, but in order to create two ordered labeled trees, we apply it recursively, top-down, quite similarly to \ref{pa:top-down}. Starting from the two passage nodes, an alignment of all the children is done. All children are added to the tree keeping the order induced by the alignment. The unaligned nodes are added with their subtree\footnote{Each node actually has a sub-DAG and so some parts of the DAG are replicated to get a tree}, while the aligned nodes are added by themselves. For each node that had an aligned node attached to it, the children are again aligned in the manner described above.

After creating the trees we use as a measure the ordered labeled tree distance using \newcite{zhang1989simple} techniques. It might be interesting to consider unordered labeled tree distance methods\justcite{zhang1992editing} as well, allowing to skip the alignment step and more natural for the UCCA structure. As this was not the main aim of the work and we did not proceed with pursuing questions in the spirit of "which distance measure is most suitable for X", we make do with this method.

%
%Then for each node in $v \in V_s$, we compute its descendent leaves $yield(v) \subset Leaves_s$ as before,
%and compute their projection $yield'(v) = \{u \in Leaves_c:(v,u) \in A_l\}$.
%We now define the node alignment to be $A = \{(u,v) \in V_s \times V_c : yield'(u) = yield(v) \}$.
%We note that $A_l \subset A$ and that if $V_s$ and $V_c$ share the same tokens,
%this computation again reduces to DAG $F$-score.

\section{Token similarity}
For completeness, we replicate the protocol used by \newcite{sulem2015conceptual}
for comparing the UCCA annotations of English-French translations, which we call
Distributional Similarity ({\sc DistSim}).
For a given UCCA label $l$, $c_i(l)$ is the number of $l$-labeled UCCA edges
in the i-th source sentence, and $d_i(l)$ is the number of $l$-labeled UCCA edges
in its corresponding correction. We define {\sc DistSim}(l) between these
sentences to be $\frac{1}{N}\sum_{i=1}^N \vert c_i(l) - d_i(l) \vert$, where
$N$ is the total number of sentence pairs.
%
%A first and most straightforward approach would be to compare all
%pairs of nodes in parallel paragraphs and to each node from one paragraph
%assign the one most similar node, span wise from the other. That approach
%is quite similar to the IAA aligning, but it
%has three drawbacks; it is asymmetric; it may be over optimistic aligning
%nodes without considering the DAG structure; and it might be
%slow for many nodes. Being asymmetric is not much of a problem. If we thrive for symmetry
%we can compute the measure twice and use the results mean,
%that would also be the case for other asymmetric methods we suggest.
%In order to address the other drawbacks we propose different aligning methods.
%
%A second method driven by the assumption that nodes higher in the
%hierarchy are more important to the semantic representation is measuring
%the largest cut in which nodes are aligned (top down) to each other
%and have the same labels. This is a harsher lower similarity
%score but one of which might be more representative of the semantics
%that are kept and hopefully more informative for tasks that will use it.
%
%A third type of methods were token similarity methods, these methods
%use one kind of aligning (top down, bottom up or pairwise) and only
%compare the meaningful nodes. This was called upon by \justcite{sulem2015conceptual}. 
%This approach makes sense due to the fact that some labels
%are well defined and thought upon while others are still vague and
%call for future work on refining or adjusting them, moreover, some
%labels are more semantic while other labels are currently just a place
%holder as each node must get a level, and the semantic role is not
%always clearly defined (e.g., the word ``is'' in ``he is walking''
%seem to be more syntactically related than semantically. In UCCA it is tagged as a \textit{function} word.). The unused
%labels are center, elaborator, function, relation, linker, ground
%and connector.
%
%A bit different way than all the others is to compute the labeled
%tree edit distance\justcite{zhang1989simple}, for that we first needed
%the trees to be ordered, we did that in a top down fashion. An interesting
%future work would be to use unordered tree edit distance methods\justcite{zhang1992editing}.
%
%We see that measurements for symmetry that are similar to the inter
%annotator agreement measure also suggest high stability, achieving
%scores not much lower than the one different annotators get for the
%same paragraph. This result is quite strong as an inter annotator
%agreement is the upper bound being the score of comparing a paragraph to itself. 
%Most importantly we learn from it all that even when correcting grammatical errors,
%the semantic structure (as represented by UCCA at least) is hardly changed and thus
%can be used as a tool to avoid introducing semantic changes when trying to only change grammar. 
%The symmetry measures we introduce can be used to enforce semantic conservatism.
%In conclusion, we have shown some direct ways to measure
%semantic faithfulness. Such ways will allow correctors to be less formally conservative
%while controlling semantic conservatism. Thus, focusing on what users - and hence we - are more interested in.
%
%
\section{The Faithfulness of a Perfect Corrector}
We obtain an IAA DAG $F$-score of 0.845
(Precision 0.834, Recall 0.857), which
is comparable to the IAA reported for English Wikipedia texts by \justcite{abend2013universal}.
As another point of comparison, we doubly annotated 3 corrected
NUCLE passages, obtaining a similar IAA.

These results suggest that annotating LL with UCCA does not degrade IAA, and can be applied as consistently to LL as to standard English.

Table \ref{tab:Distances} (left)
presents the {\sc UCCASim} scores obtained by comparing the NUCLE references and the source
sentences, or equivalently the score of a perfect corrector.
To control for differences between the annotators, we explore both
a setting where both sides were annotated by the same annotator,
and a setting where they were annotated by different ones.
As an upper bound on the score of a perfect corrector (using different annotators),
we also report the IAA on source sentences, computed using {\sc UCCASim}. The full table with all the newly proposed distance measures is found in the appendix \ref{sec:all distances}.

Our results indicate that a perfect corrector obtains a score comparable
to the IAA, which indicates that {\sc UCCASim} is indeed
insensitive to the surface divergence between a source sentence and its valid corrections.
We note that more work is required to establish whether the converse holds, namely
that the measure is sensitive enough
to unfaithfulness by a proposed correction.
This, of course, depends on the scope of distinctions covered by the semantic annotation.
In UCCA's case, it is predicate-argument structures, the inter-relations between them,
as well as the semantic heads of complex arguments. These relations are not only linguistically justified they include the main relations considered today in NLP as capturing the broad semantics of a sentence. Thus, negative results showing UCCA structures does not change when the semantic IS changed will be very surprising and require rethinking the foundations of current semantic studies.

Our attempts to conduct experiments determining empirically {\sc UCCASim}'s sensitivity to errors introduced by the correctors were unsuccessful, as these systems make only very few structural (rather than word-level) corrections (see Figure \ref{fig:over-conservatism}).
We expect that once the over-conservatism of existing correctors is resolved,
such evaluation will be more informative.
%
%Finally, we present as a control measure and a bound on the best score
%we can expect to get in such comparison the scores of paragraphs
%in which we compare two annotations for the same paragraph using all
%the similarity measures discussed, it can be thought of as a different
%way to defining IAA. Note that a similarity
%of 1 and distance of 0 is indeed reached when comparing an annotation with itself.

Finally, the right-hand side of Table \ref{tab:Distances} presents {\sc DistSim}
between the source and reference sentences.
Our results are similar to the ones obtained by \newcite{sulem2015conceptual},
who compared standard English sentences and their French translations.

\begin{table}
	\centering
	\singlespacing
	\begin{tabular}{c|c|c|c||c|c|}
		\cline{2-6} 
		& \multicolumn{3}{c||}{\sc UCCASim} & \multicolumn{2}{c|}{\sc DistSim}\\ \cline{2-6}
		& s$\rightarrow$r & r$\rightarrow$s & Avg & A+D & Scene\
		\\
		\hline
		Different & 0.85 & 0.83 & 0.84 & 0.96 & 0.93
		\\
		Same & 0.92 & 0.91 & 0.92 & 0.97 & 0.96
		\\
		\hline
		\hline
		IAA & 0.85 & 0.81 & 0.83 & - & -
		\\
		\hline
		SAR15 & - & - & - & 0.95 & 0.96 \\
		\hline
	\end{tabular}
	\caption{The faithfulness of a perfect corrector}{\label{tab:Distances}
		The left-hand side presents {\sc UCCASim}
		where the alignment is computed from the source to the reference (s$\rightarrow$r), the opposite direction
		(r$\rightarrow$s), and their average (Avg).
		%The direction of the alignment evidentally has little impact on the results.
		The right-hand side presents {\sc DistSim} for the UCCA categories Participants and Adverbials
		together (A+D), and Scene (Scene), as reported by \newcite{sulem2015conceptual}.
		The rows indicate whether the same annotator annotated the source and reference or not. As an upper bound, we report IAA computed using {\sc UCCASim} (IAA row).
		Results show that the perfect corrector's faithfulness is comparable with IAA.
		The bottom row presents the results reported by Sulem et al. (SAR15) on English-French
		translations, which are comparable to ours.}
\end{table}

\subsection{Automatic measures}
After showing corrections are indeed similar to the source semantically, more or less in agreement like IAA, one would justifiably wonder if this can be captured in an automatic way. We used TUPA \justcite{hershcovich2017transition}, a UCCA parser to conduct an exact duplicate of the experiment above changing only the human annotators with an automatic, off the shelf, trained parser. 

The results, as shown in table \ref{tab:parser}, shows a high agreement between the reference (in standard English) and the source (in LL) even when an automatic parser is used. We note that the parser was not trained again in order to capture LL. Still, the amount of agreement is more or less the score the parser gets. Those results suggest that there is no need to wait for further improvements in parsing abilities before using UCCASim, if comparable at all it seems that this score is higher than the coverage we expect to achieve in the foreseen future. The results also suggest an improvement in parsing abilities might further improve those scores.

\begin{table}
	\centering
	\singlespacing
	\begin{tabular}{c|c|c|c|}
		\cline{2-4} 
		& \multicolumn{3}{c|}{\sc UCCASim} \\
		\cline{2-4}
		& s$\rightarrow$r & r$\rightarrow$s & Avg\
		\\
		\hline
		TUPA & 0.7 & 0.7 & 0.7
		\\
		\hline
		\hline
		Different & 0.85 & 0.83 & 0.84
		\\
		\hline
	\end{tabular}
	\caption{{\sc UCCASim} parser meaning conservation}{\label{tab:parser} The table presents {\sc UCCASim}
		where the alignment is computed from the source to the reference (s$\rightarrow$r), the opposite direction
		(r$\rightarrow$s), and their average (Avg).
		
		In the first row we see the results using TUPA parser \justcite{hershcovich2017transition}. In the second row we see the results of one annotator for the source and another for the reference.
		The results show that the perfect corrector's faithfulness is captured quite well with the automatic parsing, around the parser reported accuracy and standard English.}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%was shown to have some wanted attributes that the $M^2$ scorer lacks.
%For example, it scales from -1 to 1 providing a way to know if a correction is an improvement over the
%source. I-measure expects the same input as $M^2$ but its score differs as it is based on token-level
%edits accuracy score. 
%
%Addressing the need to improve automatic GEC evaluation, three sophisticated measures have been proposed,
%all of them are reference based. 
%$M^2$ was introduced for CoNLL2013, providing a way to compute phrase-level edits $F$-Score. As an
%input $M^2$ expects a source sentence, a correction and a set of edits for each reference in the
%gold standard.
%It uses an edit lattice to optimistically choose edits for the reference that
%will best match those of the references. Since it was introduced $M^2$ is the standard scorer for GEC.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Conclusion}

This paper addresses the shortcomings of existing RBMs in GEC.
We present evidence that state of the art correctors suffer from over-conservatism and
argue that this over-conservatism results from training them against measures that
not only more harshly penalize over-correction than under-correction,
but also often penalize correctors for proposing perfectly valid corrections.
In fact, our results indicate that systems are often more likely to be penalized for a valid correction
than to receive credit for it, due to the small number of references taken into account.

Estimating the distribution of valid corrections for a sentence, we find
that increasing the number of references is beneficial only up to a point, after which
the heavy tail of the corrections distribution entails only minor improvements to the coverage
with every increase in $M$.

We thus propose a measure for the semantic faithfulness of the correction to the source,
thereby avoiding the pitfalls of reference-based evaluation. We argue that using reference-less
measures in conjunction with reference-based measures in the training and development of GEC
systems will better address the challenge of over-conservatism.


%
% In many of the uses for correction, the user does know his grammar is not perfect and
% would accept a change in grammar when needed.
% Because of this approval we also hypothesis, and it may call for a user study to prove or disprove this hypothesis, that users might accept a correct text unit of theirs being corrected to another correct text unit with the same meaning.
% This would be an example of being faithful but not conservative.
%Maybe even more importantly, we aim to have as many correct sentences as possible, but as neither the grammar is fully correct in the first place, nor is the user's understanding of it, failing to correct grammar is acceptable. Changing meaning will be totally unacceptable, and also surely detectable by the user. In other words, the users do expect the corrector to be active and not too conservative, but only as long as it is faithful. 
%
%Moreover, as correctors are based on statistics, they might even
%just correct to a more common way of saying the same thing. Such unnecessary
%correction is not conservative, and at GEC maybe be unwanted, but not strictly unwanted as overall
%it is still faithful. Additionally, some may even
%consider such correction a needed one because it has a better grammar considering
%Fuzzy Grammar\justcite{lakoff1973fuzzy,madnani2011they} or a more fluent
%way to say the exact same thing. The latter was recently suggested as a necessary
%shift in the goals of GEC\justcite{sakaguchi2016reassessing}.
%Considering all this, we propose that next generation correctors and evaluation will be focused on faithfulness
%when possible rather than on conservatism. Of course that with the evaluation comes the development
%and it all suggests that it might be beneficial to incorporate faithfulness not only for assessment
%but also as a feature for correctors. 
%

Future work will assess the relative importance, ascribed by users of GEC systems,
to different evaluation criteria of the output. We believe that in terms of conservatism,
end users will be tolerant to changes in the sentence structure, i.e.,
violation of conservatism, but much less tolerant to changes in the sentence's meaning,
i.e., violation of faithfulness. A better understanding of how these interact
may lead to improved semantic evaluation, that will alleviate the need
for a high number of references.


%\bibliographystyle{acl2012}
%\bibliography{propose}

\appendix
\chapter{Annotated paragraphs}
\begin{table}[]
	\centering
	\begin{tabular}{lll}
		Annotator-id & NUCLE-id & type      \\
		1         & 2  & corrected \\
		2         & 2  & corrected \\
		1         & 2  & learner   \\
		2         & 2  & learner   \\
		1         & 3  & corrected \\
		2         & 3  & corrected \\
		1         & 3  & learner   \\
		2         & 3  & learner   \\
		1         & 5  & corrected \\
		2         & 5  & corrected \\
		1         & 5  & learner   \\
		2         & 5  & learner   \\
		1         & 6  & learner   \\
		2         & 6  & learner   \\
		2         & 7  & corrected \\
		2         & 7  & learner   \\
		1         & 8  & corrected \\
		1         & 8  & learner   \\
		1         & 10 & corrected \\
		1         & 10 & learner  
	\end{tabular}
	\caption{Annotated paragraphs}{The list of paragraphs annotated, showing which annotator annotated it, which type of language is used in it and the corresponding id in the NUCLE corpus. Note that parallel paragraphs have the same id.\label{tab:annotated-paragraphs}}
\end{table}
\chapter{all distances \label{sec:all distances}}
\begin{table}[]
	\centering
	\begin{tabular}{l|l|l|l|l|l|l|}
		&                                    &                              &                               & \multicolumn{3}{c|}{token\_distance}                                                          \\ \cline{2-7} 
		& \multicolumn{1}{c|}{tree distance} & \multicolumn{1}{c|}{UCCASim} & \multicolumn{1}{c|}{top down} & \multicolumn{1}{c|}{bottom up} & \multicolumn{1}{c|}{top down} & \multicolumn{1}{c|}{UCCASim} \\ \cline{2-7} 
		Different                 & 324.57                             & 0.83                         & 0.75                          & 0.74                           & 0.72                          & 0.83                         \\
		Same                      & 211.50                             & 0.88                         & 0.85                          & 0.83                           & 0.79                          & 0.88                         \\ \hline
		\multicolumn{1}{|l|}{IAA} & 285.69                             & 0.88                         & 0.78                          & 0.80                           & 0.75                          & 0.87                         \\ \hline
	\end{tabular}
	
	\caption{All distance measures}{The table shows the different scores of the measures with harmonic mean between the results of the two directions(reference to source and source to reference). Note there are slight changes from the main table due to small changes in the word alignment method, still it shows that although word alignment matters, the main finding that corrections doesn't change the source much stays.}
\end{table}


\printbibliography[heading=bibintoc]
\end{document}