# On the Effects of Low-Quality Training Data
on Information Extraction from Clinical Reports

DIEGO MARCHEGGIANI FABRIZIO SEBASTIANI  Consiglio Nazionale delle Ricerche
Qatar Computing Research Institute

###### Abstract

In the last five years there has been a flurry of work on information
extraction from clinical documents, i.e., on algorithms capable of extracting,
from the informal and unstructured texts that are generated during everyday
clinical practice, mentions of concepts relevant to such
practice00footnotetext: Fabrizio Sebastiani is currently on leave from
Consiglio Nazionale delle Ricerche, Italy.. Most of this literature is about
methods based on supervised learning, i.e., methods for training an
information extraction system from manually annotated examples. While a lot of
work has been devoted to devising learning methods that generate more and more
accurate information extractors, no work has been devoted to investigating the
effect of the quality of training data on the learning process. Low quality in
training data often derives from the fact that the person who has annotated
the data is different from the one against whose judgment the automatically
annotated data must be evaluated. In this paper we test the impact of such
data quality issues on the accuracy of information extraction systems as
applied to the clinical domain. We do this by comparing the accuracy deriving
from training data annotated by the authoritative coder (i.e., the one who has
also annotated the test data, and by whose judgment we must abide), with the
accuracy deriving from training data annotated by a different coder. The
results indicate that, although the disagreement between the two coders (as
measured on the training set) is substantial, the difference is (surprisingly
enough) not always statistically significant.

###### category:

Information systems Information retrieval Retrieval tasks and goals

###### keywords:

Clustering and Classification

###### category:

Computing methodologies Machine learning Learning paradigms

###### keywords:

Supervised learning

###### keywords:

Information Extraction, Annotation quality, Radiology Reports, Medical
Reports, Clinical Narratives, Machine Learning

††terms: Algorithm, Design, Experimentation, Measurements

Diego Marcheggiani and Fabrizio Sebastiani, 2015. On the Effects of Low-
Quality Training Data on Information Extraction from Clinical Reports.

Author’s addresses: Diego Marcheggiani, Istituto di Scienza e Tecnologie
dell’Informazione, Consiglio Nazionale delle Ricerche, 56124 Pisa, Italy;
Fabrizio Sebastiani, Qatar Computing Research Institute, Qatar Foundation, PO
Box 5825, Doha, Qatar. Fabrizio Sebastiani is currently on leave from
Consiglio Nazionale delle Ricerche, Italy. The order in which the authors are
listed is purely alphabetical; each author has given an equally important
contribution to this work.

##  1 Introduction

In the last five years there has been a flurry of work (see e.g., [Kelly et
al. (2014), Pradhan et al. (2014), Sun et al. (2013), Suominen et al. (2013),
Uzuner et al. (2012), Uzuner et al. (2011)]) on information extraction from
clinical documents, i.e., on algorithms capable of extracting, from the
informal and unstructured texts that are generated during everyday clinical
practice (e.g., admission reports, radiological reports, discharge summaries,
clinical notes), mentions of concepts relevant to such practice. Most of this
literature is about methods based on supervised learning, i.e., methods for
training an information extraction system from manually annotated examples.
While a lot of work has been devoted to devising text representation methods
and variants of the aforementioned supervised learning methods that generate
more and more accurate information extractors, no work has been devoted to
investigating the effects of the quality of training data on the learning
process. Issues of quality in the training data may arise for different
reasons:

  1. 1.

In several organizations it is often the case that the original annotation is
performed by coders (a.k.a. “annotators”, or “assessors”) as a part of a daily
routine in which fast turnaround, rather than annotation quality, is the main
goal of the coders and/or of the organization. An example is the (increasingly
frequent) case in which annotation is performed via crowdsourcing using
instruments such as, e.g., Mechanical Turk, CrowdFlower,
etc.111https://www.mturk.com/, http://crowdflower.com/ [Grady and Lease
(2010), Snow et al. (2008)].

  2. 2.

In many organizations it is also the case that annotation work is usually
carried out by junior staff (e.g., interns), since having it accomplished by
senior employees would make costs soar.

  3. 3.

It is often the case that the coders entrusted with the annotation work were
not originally involved in designing the tagset (i.e., the set of concepts
whose mentions are sought in the documents). As a result, the coders may have
a suboptimal understanding of the true meaning of these concepts, or of how
their mentions are meant to look like, which may negatively affect the quality
of their annotation.

  4. 4.

The data used for training the system may sometimes be old or outdated, with
the annotations not reflecting the current meaning of the concepts anymore.
This is an example of a phenomenon, called _concept drift_ [Quiñonero-Candela
et al. (2009), Sammut and Harries (2011)], which is well known in machine
learning.

We may summarize all the cases mentioned above by saying that, should the
training data be independently re-annotated by an _authoritative coder_
(hereafter indicated as $C_{\alpha}$), the resulting annotations would be, to
a certain extent, more reliable. We would also be able to precisely measure
this difference in reliability, by measuring the _intercoder agreement_ (via
measures such as Cohen’s kappa – see e.g., [Artstein and Poesio (2008), Di
Eugenio and Glass (2004)]) between the training data $Tr$ as coded by
$C_{\alpha}$ and the training data as coded by whoever else originally
annotated them (whom we will call, for simplicity, the _non-authoritative
coder_ – hereafter indicated as $C_{\beta}$). In the rest of this paper we
will take the authoritative coder $C_{\alpha}$ to be _the coder whose
annotations are to be taken as correct_ , i.e., considered as the “gold
standard”. As a consequence we may assume that $C_{\alpha}$ is the coder who,
once the system is trained and deployed, has also the authority to evaluate
the accuracy of the automatic annotation (i.e., decide which annotations are
correct and which are not)222In some organizations this authoritative coder
may well be a fictional entity, e.g., several coders may be equally
experienced and thus equally authoritative. However, without loss of
generality we will hereafter assume that $C_{\alpha}$ exists and is unique..
In this case, intercoder (dis)agreement measures the amount of noise that is
introduced in the training data by having them annotated by a coder
$C_{\beta}$ different from the authoritative coder $C_{\alpha}$.

It is natural to expect the accuracy of an information extraction system to be
lower if the training data have been annotated by a non-authoritative coder
$C_{\beta}$, and higher if they have been annotated by $C_{\alpha}$ herself.
However, note that this is _not_ a consequence of the fact that $C_{\alpha}$
is more experienced, or senior, or reliable, than $C_{\beta}$. Rather, it is a
consequence of the fact that standard supervised learning algorithms are based
on the assumption that the training set and the test set are identically and
independently distributed (the so-called _i.i.d. assumption_), i.e., that both
sets are randomly drawn from the _same_ distribution. As a result, these
algorithms learn to replicate the subjective annotation style of their
supervisors, i.e., of those who have annotated the training data. This means
that we may expect accuracy to be higher simply when the coder of the training
set and the coder of the test set are the _same_ person, and to be lower when
the two coders are different, irrespective of how experienced, or senior, or
reliable, they are. In other words, the very fact that a coder is entrusted
with the task of evaluating the automatic annotations (i.e., of annotating the
test set) makes this coder _authoritative by definition_. For this reason, the
authoritative coder $C_{\alpha}$ may equivalently be defined as “the coder who
has annotated the test set” (or: “the coder whose judgments we adhere to when
evaluating the accuracy of the system”), and the non-authoritative coder
$C_{\beta}$ may equivalently be defined as “a coder different from the
authoritative coder”.

The above arguments point to the fact that the impact of training data quality
– under its many facets discussed in items (1)-(4) above – on the accuracy of
information extraction systems may be measured by

  1. 1.

evaluating the accuracy of the system in an _authoritative_ setting (i.e.,
both training and test sets annotated by the authoritative coder
$C_{\alpha}$), and then

  2. 2.

evaluating the loss in accuracy, with respect to the authoritative setting,
that derives from working instead in a _non-authoritative_ setting (i.e., test
set annotated by $C_{\alpha}$ and training set annotated by a non-
authoritative coder $C_{\beta}$)333In the domain of classification the
authoritative and non-authoritative settings have also been called _self-
classification_ and _cross-classification_ , respectively [Webber and Pickens
(2013)]. We depart from this terminology in order to avoid any confusion with
_self-learning_ (which refers to retraining a classifier by using, as
additional training examples, examples the classifier itself has classified)
and _cross-lingual classification_ (which denotes a variant of text
classification which exploits synergies between training data expressed in
different languages)..

###  1.1 Our contribution

In this paper we test the impact of training data quality on the accuracy of
information extraction systems as applied to the clinical domain. We do this
by testing the accuracy of two state-of the-art systems on a dataset of
radiology reports (originally discussed in [Esuli et al. (2013)]) in which a
portion of the data has independently been annotated by two different experts.
In other words, we try to answer the question: “What is the consequence of the
fact that my training data are not sterling quality? that the coders who
produced them are not entirely dependable? How much am I going to lose in
terms of accuracy of the trained system?”

In these experiments we not only test the “pure” authoritative and non-
authoritative settings described above, but we also test _partially
authoritative_ settings, in which increasingly large portions of the training
data as annotated by $C_{\alpha}$ are replaced with the corresponding portions
as annotated by $C_{\beta}$, thus simulating the presence of incrementally
higher amounts of noise. For each setting we compute the intercoder agreement
between the two training sets; this allows us to study the relative loss in
extraction accuracy as a function of the agreement between authoritative and
non-authoritative assessor as measured on the training set. Since in many
practical situations it is easy to compute (or estimate) the intercoder
disagreement between (a) the coder to whom we would ideally entrust the
annotation task (e.g., a senior expert in the organization), and (b) the coder
to whom we can indeed entrust it given time and cost constraints (e.g., a
junior member of staff), this will give the reader a sense of how much
intercoder disagreement generates how much loss in extraction accuracy.

The rest of the paper is organized as follows. Section 2 reviews related work
on information extraction from clinical documents, and on establishing the
relations between training data quality and extraction accuracy. In Sections 3
and 4 we describe experiments that attempt to quantify the degradation in
extraction accuracy that derives from low-quality training data, with Section
3 devoted to spelling out the experimental setting and Section 4 devoted
instead to presenting and discussing the results. Section 5 concludes,
discussing avenues for further research.

##  2 Related Work

###  2.1 Information extraction from clinical documents

Most works on information extraction from clinical documents rely on methods
based on supervised learning, i.e., methods for training an information
extraction system from manually annotated examples. Support vector machines
(SVMs – [Jiang et al. (2011), Li et al. (2008), Sibanda et al. (2006)]),
hidden Markov models (HMMs – [Li et al. (2010)]), and (especially) conditional
random fields (CRFs – [Esuli et al. (2013), Gupta et al. (2014), Jiang et al.
(2011), Jonnalagadda et al. (2012), Li et al. (2008), Patrick and Li (2010),
Torii et al. (2011), Wang and Patrick (2009)]) have been the learners of
choice in this field, due to their good performance and to the existence of
publicly available implementations.

In recent years, research on the analysis of clinical texts has been further
boosted by the existence of “shared tasks” on this topic, such as the seminal
i2b2 series (“Informatics for Integrating Biology and the Bedside” – [Sun et
al. (2013), Uzuner et al. (2012), Uzuner et al. (2011)]), the 2013 [Suominen
et al. (2013)] and 2014 [Kelly et al. (2014)] editions of ShARe/CLEF eHealth,
and the Semeval-2014 Task 7 “Analysis of Clinical Text” [Pradhan et al.
(2014)]. In these shared tasks the goal is to competitively evaluate
information extraction tools that recognise mentions of various concepts of
interest (e.g., mentions of diseases and disorders) as appearing in discharge
summaries, and in electrocardiogram reports, echocardiograph reports, and
radiology reports.

###  2.2 Low-quality training data and prediction accuracy

The literature on the effects of suboptimal training data quality on
prediction accuracy is extremely scarce, even within the machine learning
literature at large. An early such study is [Rossin and Klein (1999)], which
looks at these issues in the context of learning to predict prices of mutual
funds from economic indicators. Differently from us, the authors work with
noise artificially inserted in the training set, and not with naturally
occurring noise. From experiments run with a linear regression model they
reach the bizarre conclusion that “the predictive accuracy (…) is better when
errors exist in training data than when training data are free of errors”,
while the opposite conclusion is (somehow more expectedly) reached from
experiments run with a neural networks model. A similar study, in which the
context is predicting the average air temperature in distributed heating
systems, was carried out in [Jassar et al. (2009)]; yet another study, in
which the goal was predicting the production levels of palm oil via a neural
network, is [Khamis et al. (2005)].

In the context of a biomedical information extraction task444Biomedical IE is
different from clinical IE, in that the latter (unlike the former) is usually
characterized by idiosyncratic abbreviations, ungrammatical sentences, and
sloppy language in general. See [Meystre et al. (2008), p. 129] for a
discussion of this point. Haddow and Alex 2008 examined the situation in which
training data annotated by two different coders are available, and they found
that higher accuracy is obtained by using both versions at the same time than
by attempting to reconcile them or using just one of them. Their use case is
different from ours, since in the case we discuss we assume that only one set
of annotations, those of the non-authoritative coder, are available as
training data. Note also that training data independently annotated by more
than one coder are rarely available in practice.

Closer to our application context, Esuli and Sebastiani 2013 have thoroughly
studied the effect of suboptimal training data quality in text classification.
However, in their case the degradation in the quality of the training data is
obtained, for mere experimental purposes, via the insertion of artificial
noise, due to the fact that their datasets did not contain data annotated by
more than one coder. As a result, it is not clear how well the type of noise
they introduce models naturally occurring noise. Webber and Pickens 2013 also
address the text classification task (in the context of e-discovery from legal
texts), but differently from Esuli and Sebastiani (2013) they work with
naturally occurring noise; differently from the present work, the multiply-
coded training data they use were coded by one coder known to be an expert
coder and another coder known to be a junior coder. Our work instead (a)
focuses on information extraction, and (2) does not make any assumption on the
relative level of expertise of the two coders.

##  3 Experimental setting

###  3.1 Basic notation and terminology

Let us fix some basic notation and terminology. Let $\mathbf{X}$ be a set of
texts, where we view each text $\mathbf{x}\in\mathbf{X}$ as a sequence
$\mathbf{x}=\langle x_{1},\ldots,x_{|\mathbf{x}|}\rangle$ of _textual units_
(or simply _t-units_), such that odd-numbered t-units are _tokens_ (i.e., word
occurrences) and even-numbered t-units are _separators_ (i.e., sequences of
blanks and punctuation symbols), and such that $x_{t_{1}}$ occurs before
$x_{t_{2}}$ in the text (noted $x_{t_{1}}\preceq x_{t_{2}}$) if and only if
$t_{1}\leq t_{2}$. We dub $|\mathbf{x}|$ the _length_ of the text. Let
$C=\\{c_{1},\ldots,c_{m}\\}$ be a predefined set of _concepts_ (a.k.a.  _tags_
, or _markables_), or _tagset_. We take _information extraction_ (IE) to be
the task of determining, for each $\mathbf{x}\in\mathbf{X}$ and for each
$c_{r}\in C$, a sequence $\mathbf{y}_{r}=\langle
y_{r1},\ldots,y_{r|\mathbf{x}|}\rangle$ of _labels_
$y_{rt}\in\\{c_{r},\overline{c}_{r}\\}$, which indicates which t-units in the
text are labelled with tag $c_{r}$ and which are not. Since each $c_{r}\in C$
is dealt with independently of the other concepts in $C$, we hereafter drop
the $r$ subscript and, without loss of generality, treat IE as the _binary_
task of determining, given text $\mathbf{x}$ and concept $c$, a sequence
$\mathbf{y}=\langle y_{1},\ldots,y_{|\mathbf{x}|}\rangle$ of labels
$y_{t}\in\\{c,\overline{c}\\}$.

T-units labelled with a concept $c$ usually come in coherent sequences, or
“mentions”. Hereafter, a _mention_ $\sigma$ of text $\mathbf{x}$ for concept
$c$ will be a pair $(x_{t_{1}},x_{t_{2}})$ consisting of a start token
$x_{t_{1}}$ and an end token $x_{t_{2}}$ such that (i) $x_{t_{1}}\preceq
x_{t_{2}}$, (ii) all t-units $x_{t_{1}}\preceq x_{t}\preceq x_{t_{2}}$ are
labelled with concept $c$, and (iii) the token that immediately precedes
$x_{t_{1}}$ and the one that immediately follows $x_{t_{2}}$ are _not_
labelled with concept $c$. In general, a text $\mathbf{x}$ may contain zero,
one, or several mentions for concept $c$.

In the above definitions we consider separators to be also the object of
tagging in order for the IE system to correctly identify consecutive mentions.
For instance, given the expression “Barack Obama, Hillary Clinton” the perfect
IE system will attribute the PersonName tag to the tokens “Barack”, “Obama”,
“Hillary”, “Clinton”, and to the separators (in this case: blank spaces)
between “Barack” and “Obama” and between “Hillary” and “Clinton”, but _not_ to
the separator “, ” between “Obama” and “Hillary”. If the IE system does so,
this means that it has correctly identified the boundaries of the two mentions
“Barack Obama” and “Hillary Clinton”555Note that the above notation is not
able to represent “discontiguous mentions”, i.e., mentions containing gaps,
and “overlapping mentions”, i.e., multiple mentions sharing one or more
tokens. This is not a serious limitation for our research, since the above
notation can be easily extended to deal with both phenomena (e.g., by
introducing unique mention identifiers and having each t-unit be associated
with zero, one, or several such identifiers), and since the dataset we use for
our experimentation contains neither discontinuous nor overlapping mentions.
We prefer to keep the notation simple, since the issue we focus on in this
paper (the consequences on extraction accuracy of suboptimal training data
quality) can be considered largely independent of the expressive power of the
markup language..

###  3.2 Dataset

The dataset we have used to test the ideas discussed in the previous sections
is the UmbertoI(RadRep) dataset first presented in Esuli et al. (2013),
consisting of a set of 500 free-text mammography reports written (in Italian)
by medical personnel of the Istituto di Radiologia of Policlinico Umberto I,
Roma, IT. The dataset is annotated according to 9 concepts relevant to the
field of radiology and mammography: BIR (“Outcome of the BIRADS test”), ITE
(“Technical Info”), IES (“Indications obtained from the Exam”), TFU (“Followup
Therapies”), DEE (“Description of Enhancement”), PAE (“Presence/Absence of
Enhancements”), ECH (“Outcomes of Surgery”), DEP (“Prosthesis Description”),
and LLO (“Locoregional Lymph Nodes”). Note that we had no control on the
design of the concept set, on its range, and on its granularity, since the
choice of the concepts was entirely under the responsibility of Policlinico
Umberto I. We thus take both the concept set and the dataset as given.

Mentions of these concepts are present in the reports according to fairly
irregular patterns. In particular, a given concept (a) need not be
instantiated in all reports, and (b) may be instantiated more than once (i.e.,
by more than one mention) in the same report. Mentions instantiating different
concepts may overlap, and the order of presentation of the different concepts
varies across the reports. On average, there are 0.87 mentions for each
concept in a given report, and the average mention length is 17.33 words.

The reports were annotated by two equally expert radiologists, Coder1 and
Coder2; 191 reports were annotated by Coder1 only, 190 reports were annotated
by Coder2 only, and 119 reports were annotated independently by Coder1 and
Coder2. From now on we will call these sets 1-only, 2-only and Both,
respectively; Both(1) will identify the Both set as annotated by Coder1, and
Both(2) will identify the Both set as annotated by Coder2. The annotation
activity was preceded by an alignment phase, in which Coder1 and Coder2
jointly annotated 20 reports (not included in this dataset) in order to align
their understanding of the meaning of the concepts.

Table 3.2 reports the distribution of annotations across concepts, at token
and mention level, for the two coders; see (Esuli et al., 2013, Section 4.2)
for a more detailed description of the UmbertoI(RadRep) dataset that includes
additional stats666No other dataset is used in this paper since we were not
able to locate another dataset of annotated clinical texts that contains
reports annotated by more than one coder and is at the same time publicly
available..

The distribution of annotations across concepts, at token and mention level,
for each coder. DEE IES ITE ECH LLO TFU DEP BIR PAE Total Tokens annotated by
Coder1 4819 1529 7410 237 1811 1672 585 466 1723 18529 Tokens annotated by
Coder2 7351 1723 7630 1329 2544 2670 1127 448 3495 24822 Mentions annotated by
Coder1 204 140 190 51 164 149 19 128 344 1045 Mentions annotated by Coder2 282
145 188 102 193 171 26 103 399 1210

###  3.3 Learning algorithms

As the learning algorithms we have tested both _linear-chain conditional
random fields_ (LC-CRFs - Lafferty et al. (2001); Sutton and McCallum (2007,
2012)), in Charles Sutton’s GRMM
implementation777http://mallet.cs.umass.edu/grmm/, and _hidden Markov support
vector machines_ (HM-SVMs - Altun et al. (2003)), in Thorsten Joachims’s
$SVM^{hmm}$
implementation888http://www.cs.cornell.edu/people/tj/svm_light/svm_hmm.html.
Both are supervised learning algorithms explicitly devised for _sequence
labelling_ , i.e., for learning to label (i.e., to annotate) items that
naturally occur in sequences and such that the label of an item may depend on
the features and/or on the labels of other items that precede or follow it in
the sequence (which is indeed the case for the tokens in a text)999Note that
only tokens, and not separators, are explicitly labelled. The reason is that
both LC-CRFs and HM-SVMs actually use the so-called IOB labelling scheme,
according to which, for each concept $c_{r}\in C$, a token can be labelled as
$B_{r}$ (the beginning token of a mention of $c_{r}$), $I_{r}$ (a token which
is inside a mention of $c_{r}$ but is not its beginning token), and $O_{r}$ (a
token that is outside any mention of $c_{r}$). As a result, a separator is
(implicitly) labelled with concept $c_{r}$ if and only if it precedes a token
labelled with $I_{r}$. We may think of the notation of Section 3.1 as an
abstract markup language, and of the IOB notation as a concrete markup
language, in the sense that the notation of Section 3.1 is easier to
understand (and will also make the evaluation measure discussed in Section
3.4.1 easier to understand) while IOB is actually used by the learning
algorithms. The two notations are equivalent in expressive power.. LC-CRFs are
members of the class of _graphical models_ , a family of probability
distributions that factorize according to an underlying graph Wainwright and
Jordan (2008); see Sutton and McCallum (2012) for a full mathematical
explanation of LC-CRFs. HM-SVMs are an instantiation of “SVMs for structured
output prediction” ($SVM^{struct}$) Tsochantaridis et al. (2005) for the
sequence labelling task, and have already been used in clinical information
extraction (see e.g., Tang et al. (2012); Zhang et al. (2014)). In HM-SVMs the
learning procedure is based on a large-margin approach typical of SVMs, which,
differently from LC-CRFs, can learn non-linear discriminant functions via
kernel functions.

Both learners need each token $x_{t}$ to be represented by a vector
$\mathbf{x}_{t}$ of features101010Note that only tokens, and not separators,
are explicitly represented in vectorial form, the reasons being the same
already discussed in Footnote 9.. In this work we have used a set of features
which includes one feature representing the word of which the token is an
instance, one feature representing its stem, one feature representing its part
of speech, eight features representing its prefixes and suffixes (the first
and the last $n$ characters of the token, with $n=1,2,3,4$), one feature
representing information on token capitalization (i.e., whether the token is
all uppercase, all lowercase, first letter uppercase, or mixed case), and 4
“positional” features (Esuli et al., 2013, Section 3.3) that indicate in which
half, 3rd, 4th, or 5th, respectively, of the text the token occurs in.

###  3.4 Evaluation measures

####  3.4.1 Classification accuracy

As a measure of classification accuracy we use, similarly to Esuli et al.
(2013), the token-and-separator variant (proposed in Esuli and Sebastiani
(2010)) of the well-known $F_{1}$ measure, according to which an information
extraction system is evaluated on an event space consisting of all the t-units
in the text. In other words, each t-unit $x_{t}$ (rather than each _mention_ ,
as in the traditional “segmentation F-score” model Suzuki et al. (2006))
counts as a true positive, true negative, false positive, or false negative
for a given concept $c_{r}$, depending on whether $x_{t}$ belongs to $c_{r}$
or not in the predicted annotation and in the true annotation. This model has
the advantage that it credits a system for partial success (i.e., degree of
overlap between a predicted mention and a true mention for the same concept),
and that it penalizes both overannotation and underannotation.

As is well-known, $F_{1}$ is the harmonic mean of _precision_
($\pi=\frac{TP}{TP+FN}$) and _recall_ ($\rho=\frac{TP}{TP+FP}$), and is
defined as

$F_{1}=\displaystyle\frac{2\pi\rho}{\pi+\rho}{{\color[rgb]{0,0,0}=\displaystyle\frac{2\cdot\displaystyle\frac{TP}{TP+FN}\cdot\displaystyle\frac{TP}{TP+FP}}{\displaystyle\frac{TP}{TP+FN}+\displaystyle\frac{TP}{TP+FP}}}}=\displaystyle\frac{2TP}{2TP+FP+FN}$
(1)

where $TP$, $FP$, and $FN$ stand for the numbers of true positives, false
positives, and false negatives, respectively. It is easy to observe that
$F_{1}$ is equivalent to $TP$ divided by the arithmetic mean of the actual
positives and the predicted positives (or, alternatively, the product of $\pi$
and $\rho$ divided by their arithmetic mean). Note that $F_{1}$ is undefined
when $TP=FP=FN=0$; in this case we take $F_{1}$ to equal $1$, since the system
has correctly annotated all t-units as negative.

We compute $F_{1}$ across the entire test set, i.e., we generate a single
contingency table by putting together all t-units in the test set,
irrespectively of the document they belong to. We then compute both
_microaveraged_ $F_{1}$ (denoted by $F_{1}^{\mu}$) and _macroaveraged_ $F_{1}$
($F_{1}^{M}$). $F_{1}^{\mu}$ is obtained by (i) computing the concept-specific
values $TP_{r}$, $FP_{r}$ and $FN_{r}$, (ii) obtaining $TP$ as the sum of the
$TP_{r}$’s (same for $FP$ and $FN$), and then (iii) applying Equation 1.
$F_{1}^{M}$ is obtained by first computing the concept-specific $F_{1}$ values
and then averaging them across the $c_{r}$’s.

####  3.4.2 Intercoder agreement

_Intercoder agreement_ (ICA), or the lack thereof (_intercoder disagreement_),
has been widely studied for over a century (see e.g., Krippendorff (2004) for
an introduction). As a phenomenon, disagreement among coders naturally occurs
when units of content need to be annotated by humans according to their
semantics (i.e., when the occurrences of specific concepts need to be
recognized within these units of content). Such disagreement derives from the
fact that semantic content is a highly subjective notion: different coders
might disagree with each other as to what the semantics of, say, a given piece
of text is, and it is even the case that the same coder might at times
disagree with herself (i.e., return different codes when coding the same unit
of content at different times).

ICA may be measured by the relative frequency of the units of content on which
coders agree, usually normalized by the probability of chance agreement. Many
metrics for ICA have been proposed over the years, “Cohen’s kappa” probably
being the most famous and widely used (“Scott’s pi” and “Krippendorff’s alpha”
are others); sometimes (see e.g., Chapman and Dowling (2006); Esuli et al.
(2013)) functions that were not explicitly developed for measuring ICA (such
as $F_{1}$, that was developed for measuring binary classification accuracy)
are used. The levels of ICA that are recorded in actual experiments vary a lot
across experiments, types of content, and types of concepts that are to be
recognized in the units of content under investigation. This extreme variance
depends on factors such as “annotation domain, number of categories in a
coding scheme, number of annotators in a project, whether annotators received
training, the intensity of annotator training, the annotation purpose, and the
method used for the calculation of percentage agreements” Bayerl and Paul
(2011). The actual meaning of the concepts the coders are asked to recognize
is a factor of special importance, to the extent that a concept on which very
low levels of ICA are reached may be deemed, because of this very fact, ill-
defined.

For measuring intercoder agreement we use Cohen’s kappa (noted $\kappa$),
defined as

$\displaystyle\kappa$ $\displaystyle=$ $\displaystyle\frac{P(A)-P(E)}{1-P(E)}$
$\displaystyle=$
$\displaystyle{{\color[rgb]{0,0,0}\frac{(P(p=t=c)+P(p=t=\overline{c}))-(P(p=c)P(t=c)+P(p=\overline{c})P(t=\overline{c}))}{1-(P(p=c)P(t=c)+P(p=\overline{c})P(t=\overline{c}))}}}$
$\displaystyle=$
$\displaystyle{{\color[rgb]{0,0,0}\frac{\displaystyle\frac{TP+TN}{n}-((\frac{TP+FP}{n})(\frac{TP+FN}{n})+(\frac{FN+TN}{n})(\frac{FP+TN}{n}))}{1-((\displaystyle\frac{TP+FP}{n})(\frac{TP+FN}{n})+(\frac{FN+TN}{n})(\frac{FP+TN}{n}))}}}$

where $P(A)$ denotes the probability (i.e., relative frequency) of agreement,
$P(E)$ denotes the probability of chance agreement, and $n$ is the total
number of examples (see Artstein and Poesio (2008); Di Eugenio and Glass
(2004) for details); here, we use the shorthand $p=c$ (resp., $t=c$) to mean
that the predicted label (resp., true label) is $c$ (analogously for
$\overline{c}$). We opt for kappa since it is the most widely known, and best
understood, measure of ICA. For Cohen’s kappa too we work at the t-unit level,
i.e., for each t-unit $x_{t}$ we record whether the two coders agree on
whether $x_{t}$ is labelled or not with the concept $c$ of interest.

Incidentally, note that (as observed in Esuli and Sebastiani (2010)) we can
compute Cohen’s kappa only thanks to the fact that (as discussed in Section
3.4.1) we conduct our evaluation at the t-unit level (rather at the mention
level). Those who conduct their evaluation at the mention level (e.g., Chapman
and Dowling (2006)) find that they are unable to do so, since in order to be
defined kappa needs the notion of a true negative to be also defined, and this
is undefined at the mention level. Evaluation at the mention level thus
prevents the use of kappa and leaves $F_{1}$ as the only choice.

##  4 Results

###  4.1 Experimental protocol

In Esuli et al. (2013), experiments on the UmbertoI(RadRep) dataset were run
using either 1-only and/or 2-only (i.e., the portions of the data that only
one coder had annotated) as training data and Both(1) and/or Both(2) (i.e.,
the portion of the data that both coders had annotated, in both versions) as
test data.

In this paper we switch the roles of training set and test set, i.e., use
Both(1) or Both(2) as training set (since for the purpose of this paper we
need _training_ data with multiple, alternative annotations) and 1-only or
2-only as test set. Specifically, we run two batches of experiments, Batch1
and Batch2. In Batch1 Coder1 plays the role of the authoritative coder
($C_{\alpha}$) and Coder2 plays the role of the non-authoritative coder
($C_{\beta}$), while in Batch2 Coder2 plays the role of $C_{\alpha}$ and
Coder1 plays the role of $C_{\beta}$.

Each of the two batches of experiments is composed of:

  1. 1.

An experiment using the authoritative setting, i.e., both training and test
data are annotated by $C_{\alpha}$. This means training on Both(1) and testing
on 1-only (Batch1) and training on Both(2) and testing on 2-only (Batch2).

  2. 2.

An experiment using the non-authoritative setting, i.e., training data
annotated by $C_{\beta}$ and test data annotated by $C_{\alpha}$. This means
training on Both(2) and testing on 1-only (Batch1) and training on Both(1) and
testing on 2-only (Batch2).

  3. 3.

Experiments using the partially authoritative setting, i.e., test data
annotated by $C_{\alpha}$, and training data annotated in part by $C_{\beta}$
($\lambda\%$ of the training documents, chosen at random) and in part by
$C_{\alpha}$ (the remaining $(100-\lambda)\%$ of the training documents). We
call $\lambda$ the _corruption ratio_ of the training set; $\lambda=0$
obviously corresponds to the fully authoritative setting while $\lambda=100$
corresponds to the non-authoritative setting.

We run experiments for each $\lambda\in\\{10,20,...,80,90\\}$ by monotonically
adding, for increasing values of $\lambda$, new randomly chosen elements (10%
at a time) to the set of training documents annotated by $C_{\beta}$. Since
the choice of training data annotated by $C_{\beta}$ is random, we repeat the
experiment 10 times for each value of $\lambda\in\\{10,20,...,80,90\\}$, each
time with a different random such choice.

For each of the above train-and test experiment we compute the intercoder
agreement $\kappa(Tr,corr_{\lambda}(Tr))$ between the non-corrupted version of
the training set $Tr$ and the (partially or fully) corrupted version
$corr_{\lambda}(Tr)$ for a given value of $\lambda$. We then take the average
among the 10 values of $\kappa(Tr,corr_{\lambda}(Tr))$ deriving from the 10
different experiments run for a given value of $\lambda$ and denote it as
$\kappa(\lambda)$; this value indicates the average intercoder agreement that
derives by “corrupting” $\lambda\%$ of the documents in the training set,
i.e., by using for them the annotations performed by the non-authoritative
coder.

For each of the above train-and test experiment we also compute the extraction
accuracy (via both $F_{1}^{\mu}$ and $F_{1}^{M}$) and the relative loss in
extraction accuracy that results from the given corruption ratio.

###  4.2 Results and discussion

Extraction accuracy for the authoritative setting ($\lambda=0$) and non-
authoritative setting ($\lambda=100$), for the LC-CRFs and HM-SVMs learners,
for both batches of experiments (and for the average across the two batches),
along with the resulting intercoder agreement values expressed as
$\kappa(\lambda)$. Percentages indicate the loss in extraction accuracy
resulting from moving from $\lambda=0$ to $\lambda=100$.  LC-CRFs HM-SVMs
$\lambda$ $\kappa(\lambda)$ $F_{1}^{\mu}$ $F_{1}^{M}$ $F_{1}^{\mu}$
$F_{1}^{M}$ Batch1 0 1.000 0.783 0.674 0.820 0.693 100 0.742 0.765 (-2.35%)
0.668 (-0.90%) 0.786 (-4.33%) 0.688 (-0.73%) Batch2 0 1.000 0.808 0.752 0.817
0.754 100 0.742 0.733 (-10.23%) 0.654 (-14.98%) 0.733 (-11.46%) 0.625
(-20.64%) Average 0 1.000 0.795 0.713 0.819 0.724 100 0.742 0.749 (-6.14%)
0.661 (-7.87%) 0.760 (-7.76%) 0.657 (-10.20%)

Table 4.2 reports extraction accuracy figures for the authoritative and non-
authoritative settings, for both learners, both batches of experiments, and
along with the resulting intercoder agreement values. Figure 1 illustrates the
results of our experiments by plotting $F_{1}$ as a function of the corruption
ratio $\lambda$, using LC-CRFs and HM-SVMs as the learning algorithm,
respectively; for each value of $\lambda$, the corresponding level of
interannotator agreement $\kappa(\lambda)$ (as averaged across the two
batches) is also indicated. Figure 2 plots instead precision and recall as a
function of $\lambda$ for the LC-CRFs experiments, while Figure 3 does the
same for the HM-SVMs experiments.

Figure 1: Microaveraged $F_{1}$ (left) and macroaveraged $F_{1}$ (right) as a
function of the fraction $\lambda$ of the training set that is annotated by
$C_{\beta}$ instead of $C_{\alpha}$ (“corruption ratio”), using LC-CRFs (top)
and HM-SVMs (bottom) as learning algorithms. The dashed line represents the
experiments in Batch1, the dotted line represents those in Batch2, and the
solid one represents the average between the two batches. The vertical bars
indicate, for each $\lambda\in\\{10,20,...,80,90\\}$, the standard deviation
across the 10 runs deriving from the 10 random choices of
$corr_{\lambda}(Tr)$.

####  4.2.1 Macroaveraged values are lower than microaveraged ones

A first fact to be observed is that macroaveraged ($F_{1}^{M}$) results are
always lower than the corresponding microaveraged ($F_{1}^{\mu}$) results.
This is unsurprising, and conforms to a well-known pattern. In fact,
microaveraged effectiveness scores are heavily influenced by the accuracy
obtained on the concepts most frequent in the test set (i.e., on the ones that
label many test t-units); for these concepts accuracy tends to be higher,
since these concepts also tend to be more frequent in the training set.
Conversely, in macroaveraged effectiveness measures, each concept counts the
same, which means that the low-frequency concepts (which tend to be the low-
performing ones too) have as much of an impact as the high-frequency ones. See
(Debole and Sebastiani, 2005, pp. 591–593) for a thorough discussion of this
point in a text classification context.

Figure 2: Microaveraged (left) and macroaveraged (right) precision (top) and
recall (bottom) as a function of the fraction $\lambda$ of the training set
that is annotated by $C_{\beta}$ instead of $C_{\alpha}$ (“corruption ratio”),
using LC-CRFs as a learning algorithm.

Figure 3: Microaveraged (left) and macroaveraged (right) precision (top) and
recall (bottom) as a function of the fraction $\lambda$ of the training set
that is annotated by $C_{\beta}$ instead of $C_{\alpha}$ (“corruption ratio”),
using HM-SVMs as a learning algorithm.

####  4.2.2 HM-SVMs outperform LC-CRFs

A second fact that emerges is that HM-SVMs outperform LC-CRFs, on both
batches, both settings (authoritative and non-authoritative), and both
evaluation measures ($F_{1}^{\mu}$ and $F_{1}^{M}$); e.g., on the
authoritative setting, and as an average across the two batches, HM-SVMs
obtain $F_{1}^{\mu}=0.819$ (while LC-CRFs obtain 0.795) and $F_{1}^{M}=0.724$
(while LC-CRFs obtain 0.713). Aside from their different levels of
effectiveness, the two learners behave in a qualitatively similar way as a
function of $\lambda$, as evident from a comparison of Figures 2 and 3.
However, we will not dwell on this fact any further since the relative
performance of the learning algorithms is not the main focus of the present
study; as will be evident in the discussion that follows, most insights
obtained from the LC-CRFs experiments are qualitatively confirmed by the HM-
SVMs experiments, and vice versa.

####  4.2.3 Coder1 generates less accuracy than Coder2

A third fact that may be noted (from Table 4.2) is that, for $\lambda=0$,
there is a substantive difference in accuracy values between the two coders,
with Coder2 usually generating higher accuracy than Coder1. This fact can be
especially appreciated at the macroaveraged level (where for LC-CRFs we have
$F_{1}^{M}=0.674$ for Coder1 and $F_{1}^{M}=0.752$ for Coder2, and for HM-SVMs
we have $F_{1}^{M}=0.693$ for Coder1 and $F_{1}^{M}=0.754$ for Coder2), while
the difference is less clearcut at the microaveraged level (where for LC-CRFs
we have $F_{1}^{M}=.0.783$ for Coder1 and $F_{1}^{M}=0.808$ for Coder2, and
for HM-SVMs we have $F_{1}^{M}=0.820$ for Coder1 and $F_{1}^{M}=0.817$ for
Coder2); this indicates that the codes where Coder2 especially shines are the
low-frequency ones.

In principle, there might be several reasons for this difference in accuracy
values between the two coders. The documents in 2-only might be “easier” to
code automatically than those in 1-only; or the distributions of Both(1) and
1-only might be less similar to each other than the distributions of Both(2)
and 2-only, thus verifying the i.i.d. assumption to a higher degree; or Coder2
might simply be more self-consistent in her annotation style than Coder1.

In order to check whether the last of these three hypotheses is true we have
performed four $k$-fold cross-validation ($k$-FCV) experiments (for Both(1)
and Both(2), and for LC-CRFs and HM-SVMs, in all combinations), using $k=20$.
Intuitively, a higher accuracy value resulting from a $k$-FCV test means a
higher level of self-consistency, since if the same coding style is
consistently used to label a dataset, a system tends to encounter in the
testing phase the same labelling patterns it has encountered in the training
phase, which is conducive to higher accuracy. Of course, the results of such a
test are difficult to interpret if the goal is to assess the self-consistency
of a coder in _absolute_ terms (since we do not know what values of $F_{1}$
correspond to what levels of self-consistency), but they are not if the goal
is simply to establish which of the two is the more self-consistent, since the
two experiments are run on the same documents. The results of our two $k$-FCV
experiments are reported in Table 4.2.3. From this table we can see that the
accuracy on Both(2) is substantially higher than the one obtained on Both(1),
thus indicating that Coder2 is indeed more self-consistent than Coder1. This
is thus the likely explanation of the higher levels of accuracy obtained on
the dataset annotated, for both training and test, by Coder2.

Results of the 20-fold cross-validation tests on Both(1) and Both(2), for LC-
CRFs and HM-SVMs.  LC-CRFs HM-SVMs $F_{1}^{\mu}$ $F_{1}^{M}$ $F_{1}^{\mu}$
$F_{1}^{M}$ Both(1) 0.829 0.735 0.842 0.737 Both(2) 0.838 0.771 0.850 0.787

####  4.2.4 Overannotation and underannotation

A fourth, even more interesting fact we may observe is that accuracy as a
function of the corruption ratio varies much less for Batch1 than for Batch2,
since for this latter we witness a much more substantial drop in going from
$\lambda=0$ to $\lambda=100$. We conjecture that this may be due to the
different annotation style of the two coders; the rest of this subsection will
be devoted to explaining the rationale of this conjecture.

As evident from Table 3.2, Coder2 annotates, as instances of the concepts of
interest, more mentions (+15.7%) and also more tokens per mention (+15.6%)
than Coder1; relatively to each other, Coder1 is thus an _underannotator_
while Coder2 is an _overannotator_. Since, as noted in Section 1, learning
algorithms learn to replicate the subjective annotation style of their
supervisors, a system trained on data annotated by an overannotator will
itself tend to overannotate; conversely, a system trained by an underannotator
will itself tend to underannotate.

Overannotation results in more true positives and more false positives. The
plots in Figures 2 and 3 show that when, as a consequence of increased values
of $\lambda$, the number of training documents annotated by an overannotator
increases (as is the case of Batch1), precision suffers somehow (due to the
fact that, along with more true positives, there are also more false
positives), but this is compensated by an increase in recall (due to an
increased number of true positives); as a result, as shown in Figure 1 (and in
Table 4.2 too), the drop in $F_{1}$ resulting from moving to $\lambda=0$ to
$\lambda=100$ is very limited. Figures 2 and 3 instead show that when, as a
consequence of increased values of $\lambda$, the number of training documents
annotated by an underannotator increases (as is the case for Batch2), recall
drops substantially (due to the decreased number of true positives), and this
drop is not compensated by the stability of precision (which is due to the
combined effect of a decrease in true positives and a decrease in false
positives); as a result, as shown in Figure 1 (see also Table 4.2), the drop
in $F_{1}$ resulting from moving to $\lambda=0$ to $\lambda=100$ is much more
substantial than for Batch1.

In order to check whether the decreases in accuracy between the $\lambda=0$
and the $\lambda=100$ settings is statistically significant we have performed
an _approximate randomization test_ (ART) Chinchor et al. (1993). In this test
the difference is considered statistically significant if the resulting $p$
value is $<0.05$. Two advantages of the ART are that

  1. 1.

unlike the t-test, the ART does not require the data to be normally
distributed;

  2. 2.

unlike the Wilcoxon signed-rank test, the ART can be applied to multivariate
non-linear evaluation measures such as $F_{1}$ Yeh (2000).

The results of our statistical significance tests are reported in Table 4.2.4.
These results essentially confirm the observations above, i.e., that _in
Batch2 the drop in performance resulting from having the training set
annotated by the non-authoritative coder (instead of the authoritative one) is
not statistically significant_ , while (with the exception of the
$F_{1}^{\mu}$ results for HM-SVMs) it is statistically significant for Batch1.

Results of the approximate randomization test, measuring the statistical
significance of the difference between the accuracy of the system trained at
$\lambda=0$ and the accuracy of the system trained at $\lambda=100$. Results
are reported for both learners (LC-CRFs and HM-SVMs), both batches, and both
evaluation measures ($F_{1}^{\mu}$ and $F_{1}^{M}$).  LC-CRFs HM-SVMs
$F_{1}^{\mu}$ $F_{1}^{M}$ $F_{1}^{\mu}$ $F_{1}^{M}$ Batch1 0.0859 0.6207
0.0001 0.5040 Batch2 0.0001 0.0001 0.0001 0.0001

####  4.2.5 Caveats

The experiments discussed in this paper do not allow us to reach hard
conclusions about the robustness of information extraction systems to
imperfect training data quality, for several reasons:

  1. 1.

The results obtained should be confirmed by additional experiments carried out
on other datasets; unfortunately, as noted in Footnote 6, we were not able to
locate any other publicly available dataset with the required characteristics
(that is, containing at least some doubly annotated documents).

  2. 2.

The dataset used here is representative of only a specific type of imperfect
training data quality, i.e., the one deriving from the fact that the training
data were annotated by a coder different (albeit equally expert) from the one
who annotated the test set. Other types do exist, however, as noted in the
introduction.

  3. 3.

Even the results reported here are somehow contradictory, since a
statistically significant drop in performance was observed in Batch1 while no
such statistically significant drop was observed in Batch2.

However, one interesting fact that has emerged from the present study (and
that will need to be confirmed by additional experiments, should other
datasets become available) is that, as argued in detail in Section 4.2.4, the
lack of a statistically significant drop in performance observed in Batch2
seems to be due to the fact that the non-authoritative coder who annotated the
training set had an _overannotating_ behaviour. This _might_ suggest (emphasis
meaning that prudence should be exercised) that, should there be a need for
having a training set annotated by someone different from the authoritative
coder, underannotation should be discouraged much more than overannotation.

##  5 Conclusions

Few researchers have investigated the loss in accuracy that occurs when a
supervised learning algorithm is fed with training data of suboptimal quality.
We have done this for the first time in the case of information extraction
systems (trained via supervised learning) as applied to the detection of
mentions of concepts of interest in medical notes. Specifically, we have
tested to what extent extraction accuracy suffers when the person who has
annotated the test data (the “authoritative coder”), whom we must assume to be
the person to whose judgment we conform irrespectively of her level of
expertise, is different from the person who has labelled the training data
(the “non-authoritative coder”). Our experimental results, that we have
obtained on a dataset of 500 mammography reports annotated according to 9
concepts of interest, are somehow surprising, since they indicate that the
resulting drop in accuracy is not always statistically significant. In our
experiments, no statistically significant drop was observed when the non-
authoritative coder had a tendency to overannotate, while a substantial,
statistically significant drop was observed when the non-authoritative coder
was an underannotator; however, experiments on more doubly (or even multiply)
annotated datasets will be needed to confirm or disconfirm these initial
findings. Since labelling cost is an important issue in the generation of
training data (with senior coders costing much more than junior ones, and with
internal coders costing much more than “mechanical turkers”), results of this
kind may give important indications as to the cost-effectiveness of low-cost
annotation work.

This paper is a first attempt to investigate the impact of less-than-sterling
training data quality on the accuracy of medical concept extraction systems,
and more work is needed to validate the conjectures that we have made based on
our experimental results. As repeatedly mentioned in this paper, one limit of
the present work is the fact that only one dataset was used for the
experiments. This was due to the unfortunate lack of other publicly available
medical datasets that contain (at least a subset of) textual records
independently labelled by two different coders; datasets with these
characteristics have been used in the past in published research but are not
made available to the rest of the scientific community. We hope that the
increasing importance of text mining applications in clinical practice, and
the importance of shared datasets for fostering advances in this field, will
generate a new kind of awareness on the need to make more datasets available
to the scientific community.

## References

  * (1)
  * Altun et al. (2003) Yasemin Altun, Ioannis Tsochantaridis, and Thomas Hofmann. 2003.  Hidden Markov Support Vector Machines. In Proceedings of the 20th International Conference on Machine Learning (ICML 2003). Washington DC, USA, 3–10.
  * Artstein and Poesio (2008) Ron Artstein and Massimo Poesio. 2008.  Inter-Coder Agreement for Computational Linguistics.  Computational Linguistics 34, 4 (2008), 555–596.
  * Bayerl and Paul (2011) Petra S. Bayerl and Karsten I. Paul. 2011.  What Determines Inter-Coder Agreement in Manual Annotations? A Meta-Analytic Investigation.  Computational Linguistics 37, 4 (2011), 699–725.
  * Chapman and Dowling (2006) Wendy W. Chapman and John N. Dowling. 2006.  Inductive creation of an annotation schema for manually indexing clinical conditions from emergency department reports.  Journal of Biomedical Informatics 39, 2 (2006), 196–208.
  * Chinchor et al. (1993) Nancy Chinchor, David D. Lewis, and Lynette Hirschman. 1993.  Evaluating message understanding systems: An analysis of the third message understanding conference (MUC-3).  Computational Linguistics 19, 3 (1993), 409–449.
  * Debole and Sebastiani (2005) Franca Debole and Fabrizio Sebastiani. 2005.  An Analysis of the Relative Hardness of Reuters-21578 Subsets.  Journal of the American Society for Information Science and Technology 56, 6 (2005), 584–596.
  * Di Eugenio and Glass (2004) Barbara Di Eugenio and Michael Glass. 2004.  The kappa statistic: A second look.  Computational Linguistics 30, 1 (2004), 95–101.
  * Esuli et al. (2013) Andrea Esuli, Diego Marcheggiani, and Fabrizio Sebastiani. 2013.  An Enhanced CRFs-based System for Information Extraction from Radiology Reports.  Journal of Biomedical Informatics 46, 3 (2013), 425–435.
  * Esuli and Sebastiani (2010) Andrea Esuli and Fabrizio Sebastiani. 2010.  Evaluating Information Extraction. In Proceedings of the Conference on Multilingual and Multimodal Information Access Evaluation (CLEF 2010). Padova, IT, 100–111.
  * Esuli and Sebastiani (2013) Andrea Esuli and Fabrizio Sebastiani. 2013.  Training Data Cleaning for Text Classification.  ACM Transactions on Information Systems 31, 4 (2013).
  * Grady and Lease (2010) Catherine Grady and Matthew Lease. 2010.  Crowdsourcing document relevance assessment with Mechanical Turk. In Proceedings of the NAACL HLT 2010 Workshop on Creating Speech and Language Data with Amazon’s Mechanical Turk. Los Angeles, US, 172–179.
  * Gupta et al. (2014) Sonal Gupta, Diana L. MacLean, Jeffrey Heer, and Christopher D Manning. 2014.  Induced lexico-syntactic patterns improve information extraction from online medical forums.  Journal of the American Medical Informatics Association 21, 5 (2014), 902–909.
  * Haddow and Alex (2008) Barry Haddow and Beatrice Alex. 2008.  Exploiting Multiply Annotated Corpora in Biomedical Information Extraction Tasks. In Proceedings of the 6th Conference on Language Resources and Evaluation (LREC 2008). Marrakech, MA.
  * Jassar et al. (2009) Surinder Jassar, Zaiyi Liao, and Lian Zhao. 2009.  Impact of Data Quality on Predictive Accuracy of ANFIS-based Soft Sensor Models. In Proceedings of the 2009 IEEE World Congress on Engineering and Computer Science (WCECS 2009), Vol. II. San Francisco, US.
  * Jiang et al. (2011) Min Jiang, Yukun Chen, Mei Liu, S. Trent Rosenbloom, Subramani Mani, Joshua C. Denny, and Hua Xu. 2011.  A study of machine-learning-based approaches to extract clinical entities and their assertions from discharge summaries.  Journal of the American Medical Informatics Association 18, 5 (2011), 601–606.
  * Jonnalagadda et al. (2012) Siddhartha Jonnalagadda, Trevor Cohen, Stephen Wu, and Graciela Gonzalez. 2012.  Enhancing clinical concept extraction with distributional semantics.  Journal of Biomedical Informatics 45, 1 (2012), 129–140.
  * Kelly et al. (2014) Liadh Kelly, Lorraine Goeuriot, Hanna Suominen, Tobias Schreck, Gondy Leroy, Danielle L. Mowery, Sumithra Velupillai, Wendy W. Chapman, David Martínez, Guido Zuccon, and João R. M. Palotti. 2014\.  Overview of the ShARe/CLEF eHealth Evaluation Lab 2014\. In Proceedings of the 5th International Conference of the CLEF Initiative (CLEF 2014). Sheffield, UK, 172–191.
  * Khamis et al. (2005) Azme Khamis, Zuhaimy Ismail, Khalid Haron, and Ahmad T. Mohammed. 2005\.  The effects of outliers data on neural network performance.  Journal of Applied Sciences 5, 8 (2005), 1394–1398.
  * Krippendorff (2004) Klaus Krippendorff. 2004.  Content analysis: An introduction to its methodology.  Sage, Thousand Oaks, US.
  * Lafferty et al. (2001) John Lafferty, Andrew McCallum, and Fernando Pereira. 2001.  Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. In Proceedings of the 18th International Conference on Machine Learning (ICML 2001). Williamstown, US, 282–289.
  * Li et al. (2008) Dingcheng Li, Karin Kipper-Schuler, and Guergana Savova. 2008.  Conditional Random Fields and Support Vector Machines for Disorder Named Entity Recognition in Clinical Texts. In Proceedings of the ACL Workshop on Current Trends in Biomedical Natural Language Processing (BioNLP 2008). Columbus, US, 94–95.
  * Li et al. (2010) Ying Li, Sharon Lipsky Gorman, and Noémie Elhadad. 2010.  Section classification in clinical notes using supervised hidden Markov model. In Proceedings of the 2nd ACM International Health Informatics Symposium. Arlington, US, 744–750.
  * Meystre et al. (2008) Stephane M. Meystre, Guerguana K. Savova, Karin C. Kipper-Schuler, and John F. Hurdle. 2008.  Extracting Information from Textual Documents in the Electronic Health Record: A Review of Recent Research.  In IMIA Yearbook of Medical Informatics, A. Geissbuhler and C. Kulikowski (Eds.). Schattauer Publishers, Stuttgart, DE, 128–144.
  * Patrick and Li (2010) Jon Patrick and Ming Li. 2010.  High accuracy information extraction of medication information from clinical notes: 2009 i2b2 medication extraction challenge.  Journal of the American Medical Informatics Association 17 (2010), 524–527.
  * Pradhan et al. (2014) Sameer Pradhan, Noémie Elhadad, Wendy Chapman, Suresh Manandhar, and Guergana Savova. 2014.  SemEval-2014 Task 7: Analysis of Clinical Text. In Proceedings of the 8th International Workshop on Semantic Evaluation (SemEval 2014). Dublin, IE, 54–62.
  * Quiñonero-Candela et al. (2009) Joaquin Quiñonero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D. Lawrence (Eds.). 2009.  Dataset shift in machine learning.  The MIT Press, Cambridge, US.
  * Rossin and Klein (1999) Donald F. Rossin and Barbara D. Klein. 1999.  Data Errors in Neural Network and Linear Regression Models: An Experimental Comparison.  Data Quality Journal 5, 1 (1999).
  * Sammut and Harries (2011) Claude Sammut and Michael Harries. 2011.  Concept drift.  In Encyclopedia of Machine Learning, Claude Sammut and Geoffrey I. Webb (Eds.). Springer, Heidelberg, DE, 202–205.
  * Sibanda et al. (2006) Tawanda Sibanda, Tian He, Peter Szolovits, and Özlem Uzuner. 2006\.  Syntactically-informed semantic category recognition in discharge summaries. In Proceedings of the Annual Symposium of the American Medical Informatics Association (AMIA 2006). Washington, US, 714–718.
  * Snow et al. (2008) Rion Snow, Brendan O’Connor, Daniel Jurafsky, and Andrew Y. Ng. 2008.  Cheap and Fast - But is it Good? Evaluating Non-Expert Annotations for Natural Language Tasks. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing (EMNLP 2008). Honolulu, US, 254–263.
  * Sun et al. (2013) Weiyi Sun, Anna Rumshisky, and Özlem Uzuner. 2013.  Evaluating temporal relations in clinical text: 2012 i2b2 Challenge.  Journal of the American Medical Informatics Association 20, 5 (2013), 806–813.
  * Suominen et al. (2013) Hanna Suominen, Sanna Salanterä, Sumithra Velupillai, Wendy W. Chapman, Guergana Savova, Noemie Elhadad, Sameer Pradhan, Brett R. South, Danielle L. Mowery, Gareth J. Jones, Johannes Leveling, Liadh Kelly, Lorraine Goeuriot, David Martinez, and Guido Zuccon. 2013.  Overview of the ShARe/CLEF eHealth Evaluation Lab 2013\. In Proceedings of the 4th International Conference of the CLEF Initiative (CLEF 2013). Valencia, ES, 212–231.
  * Sutton and McCallum (2007) Charles Sutton and Andrew McCallum. 2007.  An Introduction to Conditional Random Fields for Relational Learning.  In Introduction to Statistical Relational Learning, Lise Getoor and Ben Taskar (Eds.). The MIT Press, Cambridge, US, 93–127.
  * Sutton and McCallum (2012) Charles Sutton and Andrew McCallum. 2012.  An Introduction to Conditional Random Fields.  Foundations and Trends in Machine Learning 4, 4 (2012), 267–373.
  * Suzuki et al. (2006) Jun Suzuki, Erik McDermott, and Hideki Isozaki. 2006.  Training Conditional Random Fields with Multivariate Evaluation Measures. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL (ACL/COLING 2006). Sydney, AU, 217–224.
  * Tang et al. (2012) Buzhou Tang, Hongxin Cao, Yonghui Wu, Min Jiang, and Hua Xu. 2012.  Clinical entity recognition using structural support vector machines with rich features. In Proceedings of the 6th ACM International Workshop on Data and Text Mining in Biomedical Informatics (DTMBIO 2012). Maui, US, 13–20.
  * Torii et al. (2011) Manabu Torii, Kavishwar Wagholikar, and Hongfang Liu. 2011.  Using machine learning for concept extraction on clinical documents from multiple data sources.  Journal of the American Medical Informatics Association 18, 5 (2011), 580–587.
  * Tsochantaridis et al. (2005) Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann, and Yasemin Altun. 2005.  Large Margin Methods for Structured and Interdependent Output Variables.  Journal of Machine Learning Research 6 (2005), 1453–1484.
  * Uzuner et al. (2012) Özlem Uzuner, Andreea Bodnari, Shuying Shen, Tyler Forbush, John Pestian, and Brett R. South. 2012.  Evaluating the state of the art in coreference resolution for electronic medical records.  Journal of the American Medical Informatics Association 19, 5 (2012), 786–791.
  * Uzuner et al. (2011) Özlem Uzuner, Brett R. South, Shuying Shen, and Scott L. DuVall. 2011.  2010 i2b2/VA challenge on concepts, assertions, and relations in clinical text.  Journal of the American Medical Informatics Association 18, 5 (2011), 552–556.
  * Wainwright and Jordan (2008) Martin J. Wainwright and Michael I. Jordan. 2008.  Graphical Models, Exponential Families, and Variational Inference.  Foundations and Trends in Machine Learning 1, 1/2 (2008), 1–305.
  * Wang and Patrick (2009) Yefeng Wang and Jon Patrick. 2009.  Cascading classifiers for named entity recognition in clinical notes. In Proceedings of the RANLP 2009 Workshop on Biomedical Information Extraction. Borovets, BG, 42–49.
  * Webber and Pickens (2013) William Webber and Jeremy Pickens. 2013.  Assessor disagreement and text classifier accuracy. In Proceedings of the 36th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2013). Dublin, IE, 929–932.
  * Yeh (2000) Alexander S. Yeh. 2000.  More accurate tests for the statistical significance of result differences. In Proceedings of the 18th International Conference on Computational Linguistics (COLING 2000). Saarbrücken, DE, 947–953.
  * Zhang et al. (2014) Yaoyun Zhang, Jingqi Wang, Buzhou Tang, Yonghui Wu, Min Jiang, Yukun Chen, and Hua Xu. 2014.  UTH_CCB: A report for SemEval 2014 – Task 7 Analysis of Clinical Text. In Proceedings of the 8th International Workshop on Semantic Evaluation (SemEval 2014). Dublin, IE, 802–806.


# All Connected Quivers Have An Unrestricted Red Size of $n-1$ Or $n$

Tucker J. Ervin  Department of Mathematics, University of Alabama, Tuscaloosa,
AL 35487, U.S.A<EMAIL_ADDRESS>
###### Abstract.

The unrestricted red size of a quiver is the maximal number of red vertices in
its framed quiver after any given mutation sequence. In a 2023 paper by E.
Bucher and J. Machacek, it was shown that connected, mutation-finite quivers
either have an unrestricted red size of $n-1$ or $n$, where $n$ is the number
of vertices in the quiver. We prove here that the same holds for the
connected, mutation-infinite case using forks. As such, the unrestricted red
size for any quiver equals $n-c$, where $c$ is the number of connected
components of the quiver that do not admit a reddening sequence.

##  1\. Introduction

Maximal green sequences were formally announced in a 2010 talk by B. Keller,
which was later compiled into a series of lecture notes [7]. Both maximal
green sequences and reddening sequences are special sequences of mutations
that end in quivers with all red vertices, and they have powerful implications
for the cluster algebras and Donald-Thompson invariants associated to quivers
that admit them [5]. Not every quiver admits a maximal green sequence or a
reddening sequence, and in 2020 Ahmad and Li created a measure, the red size
Red, which counts the maximal number of red vertices in a quiver after
mutating only at a green vertices [1]. In 2023, Bucher and Machacek
generalized this to reddening sequences with the unrestricted red size uRed,
which counts the maximal number of red vertices after any given mutation
sequence [3]. Naturally, for a quiver $Q$ on $n$ vertices that admits a
reddening sequence, we have that $\text{uRed}(Q)=n$. The question then
becomes: what is the unrestricted red size of $Q$ when it does not admit a
reddening sequence?

Bucher and Machacek conjectured the following for the case of connected
quivers.

######  Conjecture 1.1.

[3] For any connected quiver $Q$ on $n$ vertices which does not admit a
reddening sequence

  1. (1)

We have $\text{Red}(Q)=n-1$.

  2. (2)

We have $\text{Red}(Q)=n-1$ and every vertex of $Q$ is the last remaining
green vertex after the application of some general maximal green sequence.

  3. (3)

We have $\text{uRed}(Q)=n-1$.

  4. (4)

We have $\text{uRed}(Q)=n-1$ and every vertex of $Q$ is the last remaining
green vertex after the application of some general reddening sequence.

Answering any part of Conjecture 1.1 affirmatively would naturally imply their
other conjecture —a generalization of the mutation-invariance of admitting a
reddening sequence.

######  Conjecture 1.2.

[3] The unrestricted red size is a mutation-invariant.

Conjecture 1.1 was proven for the connected, mutation-finite case. Using a
special type of quiver called a fork, we extend their results to the
connected, mutation-infinite case. This proves part (3) of Conjecture 1.1;
however, the stronger variations of Conjecture 1.1 remain unresolved.

######  Corollary 1.3.

Every connected, mutation-infinite quiver $Q$ on $n$ vertices has $uRed(Q)\geq
n-1$. Furthermore, if $Q$ is any quiver on $n$ vertices, then
$\text{uRed}(Q)=n-c$, where $c$ is the number of connected components of $Q$
that do not admit reddening sequences.

As for the structure of the paper, we list the necessary preliminary material
in Section 2. Section 3 develops the information on acyclic orderings that we
need for Section 4, where we prove our main result.

###  1.1. Acknowledgements

I would like to thank Eric Bucher and John Machacek for their discussions
about this topic. I would also like to thank my advisor, Kyungyong Lee, for
his guidance, support, and help revising this paper.

##  2\. Preliminaries

###  2.1. Quivers & Mutation

We begin with some definitions concerning quivers and quiver mutation.

######  Definition 2.1.

A quiver $Q$ is defined as a tuple $(Q_{0},Q_{1},s,t)$, where $Q_{0}$ is a set
of vertices, $Q_{1}$ is a set of arrows, and maps $s,t:Q_{1}\to Q_{0}$ taking
any arrow $a\in Q_{1}$ to its starting vertex $s(a)$ and its terminal vertex
$t(a)$, i.e., $s(a)\to t(a)$ is the arrow $a$ in $Q$. We further restrict our
definition so that $s(a)\neq t(a)$ (no loops) for all $a\in Q_{1}$ and that
there is no pair of arrows $a,b\in Q_{1}$ where $s(a)=t(b)$ and $t(a)=s(b)$
(no 2-cycles). This naturally forces all arrows between two vertices to point
in the same direction. For example, Figure 1 demonstrates two distinct
quivers.

${i}$${j}$ and ${i}$${j}$ Figure 1. Two Distinct Quivers

Additionally, whenever we have multiple arrows between the same two vertices,
we write the multiplicity, say $m$, above or below the arrow, i.e, as in
Figure 2.

${i}$${j}$$\scriptstyle{m}$ Figure 2. Notation for Arrows With Multiplicity
$m$

  * •

A vertex that only has arrows leaving (entering) is referred to as a source
(sink).

  * •

A quiver is called acyclic if there exists no (nonempty) directed path of
arrows beginning and ending at the same vertex.

  * •

A quiver is said to be abundant if there are at least two arrows between every
pair of vertices.

  * •

A quiver is connected if there exists a sequence of edges (considered without
their directions) connecting any two pairs of vertices.

  * •

A quiver $Q=(Q_{0},Q_{1},s,t)$ is called a full subquiver (often called an
induced subquiver) of a quiver $P=(P_{0},P_{1},s^{\prime},t^{\prime})$ if
$Q_{0}\subset P_{0}$, if $Q_{1}\subseteq P_{1}$, if the maps $s$ and $t$ are
restrictions of $s^{\prime}$ and $t^{\prime}$ to the set $Q_{1}$, and if
$s(a),t(a)\in Q_{0}$ implies that $a\in Q_{1}$ for any arrow $a\in P_{1}$. For
ease of use, the notation $P\setminus V$ will refer to the full subquiver
induced by the vertex set $P_{0}\setminus V$ for some set $V$.

Furthermore, we finish with a small matter of notation. Fix a quiver, denoted
by a capital letter, say $Q$. Then the number of arrows between vertex $i$ and
$j$ in $Q$ is denoted by the lowercase letter indexed by the vertices,
$q_{ij}$, which is positive if $i\to j$ and negative if $j\to i$.

######  Definition 2.2.

Quiver mutation is defined for every quiver $Q$ and vertex $v$ in $Q_{0}$ by
the following:

  * •

For every path of the form $a\to v\to b$ in $Q$, add an arrow from $a$ to $b$;

  * •

Flip the direction of every arrow touching $v$;

  * •

Finally, if any 2-cycles were formed (paths of length two that begin and end
at the same vertex), remove them.

This process will always mutate a quiver into another quiver, and we denote
the mutation of $Q$ at vertex $v$ by $\mu_{v}(Q)$. If we have a sequence of
vertices, ${\boldsymbol{w}}=[i_{1},i_{2},i_{3},\dots,i_{n}]$, then we use

$\mu_{\boldsymbol{w}}(Q)=\mu_{i_{n}}(\mu_{[i_{1},i_{2},\dots,i_{n-1}]}(Q))$

to denote the result of mutating $Q$ at each vertex $i_{j}$ in order. We call
${\boldsymbol{w}}$ a mutation sequence. If we are always mutating at sources,
then we call ${\boldsymbol{w}}$ a source mutation sequence. Additionally, we
assume that all of our mutation sequences are reduced, i.e., we never see
mutation at a vertex and then another immediate mutation at that same vertex.
Mutation is an involution, so two mutations at the same vertex can be safely
replaced by not mutating in the first place.

######  Definition 2.3.

Two quivers are said to be mutation-equivalent if there exists a sequence of
mutations taking one to the other. The collection of all quivers mutation-
equivalent to a quiver $Q$ is denoted $[Q]$, and it is called the labelled
mutation class of $Q$. If $[Q]$ is a finite (infinite) set, then $Q$ is said
to be mutation-finite (mutation-infinite).

######  Definition 2.4.

A vertex of a quiver is said to be frozen if we do not allow mutation at that
vertex. Any non-frozen vertex is mutable, and quivers with frozen vertices are
called ice quivers when a distinction needs to be made. A mutable vertex $i$
in a quiver $Q$ is said to be red (green) if $|q_{ji}|\neq 0$ implies that
$q_{ji}>0$ ($q_{ij}>0$) for all frozen vertices $j$. If $q_{ji}=0$ for all
frozen vertices $j$, we say that $i$ is blue.

We may then describe framed quivers, which are the objects of study that
Conjecture 1.1 is concerned with.

######  Definition 2.5.

We may form a framed quiver $\widehat{Q}$ from a quiver $Q$ in the following
manner. Add a frozen vertex $i^{\prime}$ to $Q$ for each vertex $i$, where a
single arrow points from $i$ to $i^{\prime}$. For example, if $Q$ was the
quiver $i\to j$, then the framed quiver $\widehat{Q}$ would be given in Figure
3.

${i^{\prime}}$${j^{\prime}}$${i}$${j}$ Figure 3. Example of Framed Quiver

Similarly, we may form the coframed quiver $\widecheck{Q}$ by adding a frozen
vertex $i^{\prime}$ to $Q$ for each vertex $i$, where a single arrow points
from $i^{\prime}$ to $i$. For example, if $Q$ was $i\to j$, then the coframed
$\widecheck{Q}$ would be given in Figure 4.

${i^{\prime}}$${j^{\prime}}$${i}$${j}$ Figure 4. Example of Coframed Quiver

The reason why we focus on framed and coframed quivers instead of truly
arbitrary ice quivers comes from the sign-coherence theorem, which controls
the colors of vertices in the labelled mutation class of $\widehat{Q}$ and
$\widecheck{Q}$.

######  Theorem 2.6.

[6] Let $Q$ be any quiver. If $P$ is mutation-equivalent to $\widehat{Q}$,
then every mutable vertex of $P$ is either red or green. Similarly, if $P$ is
mutation-equivalent to $\widecheck{Q}$, then every mutable vertex of $P$ is
either red or green.

We can then define the mutation sequences that we wish to study.

######  Definition 2.7.

A mutation sequence ${\boldsymbol{w}}$ is said to be a reddening sequence for
an ice quiver $Q$ if $P=\mu_{\boldsymbol{w}}(Q)$ has $n$ red vertices, where
$n$ is the number of mutable vertices in $Q$. If we only mutated at green
vertices along ${\boldsymbol{w}}$, the sequence is instead called a maximal
green sequence. Bucher and Machacek generalized reddening sequences to general
reddening sequences, which requires that $P$ have a maximal number, $uRed(Q)$,
of red vertices. We say that $uRed(Q)$ is the unrestricted red size of $Q$
[3].

If $Q$ has only mutable vertices, we will say that $Q$ has a reddening
sequence, maximal green sequence, a general reddening sequence, etc. whenever
the framed quiver, $\widehat{Q}$, does.

###  2.2. Forks

First introduced in a 2014 dissertation by M. Warkentin [8], forks are a
special type of quiver with many useful properties. Most notably, any
connected, mutation-infinite quiver is mutation-equivalent to a fork. We shall
use this property in Section 4 to prove our main result, but we list the
relevant definition and results here.

######  Definition 2.8.

[8, Definition 2.1] A fork is an abundant quiver $F$, where $F$ is not acyclic
and where there exists a vertex $r$, called the point of return, such that

  * •

For all $i\in F^{-}(r)$ and $j\in F^{+}(r)$ we have $f_{ji}>f_{ir}$ and
$f_{ji}>f_{rj}$, where $F^{-}(r)$ is the set of vertices with arrows pointing
towards $r$ and $F^{+}(r)$ is the set of vertices with arrows coming from $r$.

  * •

The full subquivers induced by $F^{-}(r)$ and $F^{+}(r)$ are acyclic.

An example of a fork is given in Figure 5, where $r$ is the point of return.

${r}$${i}$${j}$$\scriptstyle{3}$$\scriptstyle{4}$$\scriptstyle{5}$ Figure 5.
Example of a Fork With Point of Return $r$

######  Lemma 2.9.

[8, Lemma 2.4] Let $F$ be a fork with point of return $r$. Then a full
subquiver $Q$ of $F$ is either abundant acyclic or a fork with the same point
of return $r$.

######  Lemma 2.10.

[8, Lemma 2.5] Let $F$ be either a fork with point of return $r$ or an
abundant acyclic quiver. If $k$ is a vertex in $F$ that is not the point of
return, not a source, or not a sink, then $\mu_{k}(F)$ is a fork with point of
return $k$. Additionally, the total number of arrows contained in $\mu_{k}(F)$
is strictly greater than the total number of arrows in $F$.

######  Theorem 2.11.

[8, Theorem 3.2] A connected quiver is mutation-infinite if and only if it is
mutation-equivalent to a fork.

##  3\. Acyclic Orderings

In order to keep track of the color of vertices in a fork, we will first need
some results on the acyclic orderings arising from abundant acyclic quivers
and forks.

######  Definition 3.1.

[2] Let $Q$ be a quiver on $n$ vertices. Then we say that an ordering
$v_{1}\prec v_{2}\prec\dots\prec v_{n}$ on the vertices is acyclic if whenever
there exists an arrow $v_{i}\to v_{j}$ then $v_{i}\prec v_{j}$.

######  Proposition 3.2.

[2, Proposition 3.1.2] Let $Q$ be an acyclic quiver. Then there exists an
acyclic ordering of its vertices.

Naturally, if a quiver is abundant and acyclic, its acyclic ordering must be
unique. We can then track the acyclic orderings of every acyclic quiver in its
source mutation cycle.

######  Lemma 3.3.

Let $Q$ be an abundant acyclic quiver, where $v_{1}\prec v_{2}\prec\dots\prec
v_{n}$ is its unique acyclic ordering. Then the mutation sequence
${\boldsymbol{w}}_{i}=[v_{1},v_{2},\dots,v_{j}]$ is a source mutation sequence
such that $Q^{j}=\mu_{{\boldsymbol{w}}_{j}}(Q)$ has the unique acyclic
ordering $v_{j+1}\prec\dots\prec v_{n}\prec v_{1}\prec\dots\prec v_{j-1}\prec
v_{j}$ for all $j\leq n$.

###### Proof.

Mutating $Q$ at $v_{1}$ will give us the quiver $Q^{1}$ with unique acyclic
ordering $v_{2}\prec v_{3}\prec\dots\prec v_{n}\prec v_{1}$, as the source of
$Q$ will become the sink of $Q^{1}$, affecting no other arrows. As such, if we
keep mutating along ${\boldsymbol{w}}_{i}$, we cycle through the acyclic
ordering. Thus $Q^{i}=\mu_{{\boldsymbol{w}}_{i}}(Q)$ has the unique acyclic
ordering $v_{i+1}\prec v_{i+2}\prec\dots\prec v_{n}\prec v_{1}\prec\dots\prec
v_{i-1}\prec v_{i}$ for all $i<n$. If $i=n$, then we have arrived back at our
original $Q$. ∎

As removing the point of a return from a fork produces an abundant acyclic
quiver, we can also examine the acyclic ordering produced by subquivers of a
fork after mutation not at the point of return.

######  Lemma 3.4.

Let $F$ be a fork with point of return $r$, where $v_{1}\prec
v_{2}\prec\dots\prec v_{n-1}$ is the unique acyclic ordering on
$F\setminus\\{r\\}$. For some vertex $v_{j}$, let $F^{\prime}=\mu_{v_{j}}(F)$.
Then $F^{\prime}\setminus\\{v_{j}\\}$ has unique acyclic ordering $r\prec
v_{1}\prec\dots\prec v_{j-1}\prec v_{j+1}\prec\dots\prec v_{n-1}$ if $r\to
v_{j}$ in $F$ and $v_{1}\prec\dots\prec v_{j-1}\prec v_{j+1}\prec\dots\prec
v_{n-1}\prec r$ if $v_{j}\to r$ in $F$.

###### Proof.

First, note that the direction of arrows in $F\setminus\\{r,v_{j}\\}$ is
completely unchanged after mutation at $v_{j}$, as $F\setminus\\{r\\}$ is
abundant acyclic. Thus the unique acyclic ordering of
$F^{\prime}\setminus\\{r,v_{j}\\}$ is $v_{1}\prec\dots\prec v_{j-1}\prec
v_{j+1}\prec\dots\prec v_{n-1}$. As $F^{\prime}\setminus\\{v_{j}\\}$ is
abundant acyclic, we need only add $r$ into the ordering.

Before doing so, note that $r\to v_{1}$ and $v_{n}\to r$ in $F$, as forks do
not have sources or sinks. Now suppose that $r\to v_{j}$ in $F$. Then $r\to
v_{1}$ in $F^{\prime}$, and the unique acyclic ordering of
$F^{\prime}\setminus\\{v_{j}\\}$ is $r\prec v_{1}\prec\dots\prec v_{j-1}\prec
v_{j+1}\prec\dots\prec v_{n-1}$. If instead $v_{j}\to r$ in $F$, then
$v_{n}\to r$ in $F^{\prime}$, and the unique acyclic ordering of
$F^{\prime}\setminus\\{v_{j}\\}$ is $v_{1}\prec\dots\prec v_{j-1}\prec
v_{j+1}\prec\dots\prec v_{n-1}\prec r$. ∎

Lemmata 3.3 and 3.4 combine to give us a thorough understanding of the two
acyclic orderings that can be found by performing source mutations on
$F\setminus\\{r\\}$.

######  Lemma 3.5.

Let $F$ be a fork with point of return $r$, where $v_{1}\prec
v_{2}\prec\dots\prec v_{n-1}$ is the unique acyclic ordering on
$F\setminus\\{r\\}$. If ${\boldsymbol{w}}_{j}=[v_{1},v_{2},\dots,v_{j}]$ for
$j\leq n-1$, let $F^{j}=\mu_{{\boldsymbol{w}}_{j}}(F)$. Then
$F^{j}\setminus\\{v_{j}\\}$ has unique acyclic ordering $r\prec
v_{j+1}\prec\dots\prec v_{n-1}\prec v_{1}\prec\dots\prec v_{j-1}$ and
$F^{j}\setminus\\{r\\}$ has unique acyclic ordering $v_{j+1}\prec\dots\prec
v_{n-1}\prec v_{1}\prec\dots\prec v_{j-1}\prec v_{j}$.

###### Proof.

Lemma 3.3 proves the desired result for the acyclic ordering on
$F^{j}\setminus\\{r\\}$, as $F\setminus\\{r\\}$ is abundant acyclic and
${\boldsymbol{w}}_{j}$ is a source mutation sequence. We will then show that
$r$ is the source of $F^{j}\setminus\\{v_{j}\\}$ by induction. As $r\to v_{1}$
in $F$, we know that $F^{1}\setminus\\{v_{1}\\}$ must have acyclic ordering
$r\prec v_{2}\prec v_{3}\prec\dots\prec v_{n-1}$ by Lemma 3.4, completing the
base case.

Assume then that $F^{j}\setminus\\{v_{j}\\}$ has acyclic ordering $r\prec
v_{j+1}\prec\dots\prec v_{n-1}\prec v_{1}\prec\dots\prec v_{j-1}$. As
$F^{j}\setminus\\{r\\}$ has unique acyclic ordering $v_{j+1}\prec\dots\prec
v_{n-1}\prec v_{1}\prec\dots\prec v_{j-1}\prec v_{j}$, this forces $v_{j+1}\to
v_{j}$ in $F^{j}$. Thus, Lemma 3.4 tells us that
$F^{j+1}\setminus\\{v_{j+1}\\}$ has unique acyclic ordering $r\prec
v_{j+2}\prec\dots\prec v_{n-1}\prec v_{1}\prec\dots\prec v_{j-1}\prec v_{j}$,
completing the inductive case. ∎

######  Corollary 3.6.

Let $F$ be a fork with point of return $r$, where $v_{1}\prec
v_{2}\prec\dots\prec v_{n-1}$ is the unique acyclic ordering on
$F\setminus\\{r\\}$. If ${\boldsymbol{w}}=[v_{1},v_{2},\dots,v_{j},r]$ for
$j\leq n-1$, let $F^{\prime}=\mu_{{\boldsymbol{w}}}(F)$. Then
$F^{\prime}\setminus\\{v_{j}\\}$ has unique acyclic ordering
$v_{j+1}\prec\dots\prec v_{n-1}\prec v_{1}\prec\dots\prec v_{j-1}\prec r$ and
$F^{\prime}\setminus\\{r\\}$ has unique acyclic ordering $v_{j}\prec
v_{j+1}\prec\dots\prec v_{n-1}\prec v_{1}\prec\dots\prec v_{j-1}$.

##  4\. Sign-coherent Quivers

We now give a definition of two different types of sign-coherent quivers,
where the name uniformly sign-coherent comes from the term “uniform column
sign-coherent” given by Cao and Li [4].

######  Definition 4.1.

An ice quiver is said to be uniformly sign-coherent if every quiver in its
mutation class has every vertex red, green, or blue. In this paper, we assume
that not every vertex of a uniformly sign-coherent quiver is blue. If we do
use such a quiver, we will refer to it as a trivially sign-coherent quiver.
Finally, if every quiver in a mutation class has every vertex exclusively red
or green, we say it is strictly sign-coherent.

Introducing strictly sign-coherent quivers allows us to speak about ice
quivers that are mutation equivalent to a framed or coframed quiver. The sign-
coherence theorem forces all such quivers to be strictly sign-coherent. We
will prove some of our results for the more general uniformly sign-coherent
case, but the strictly sign-coherent case is all we need, beginning with a
result that accounts for color in abundant acyclic and uniformly sign-coherent
quivers.

######  Lemma 4.2.

Let $Q$ be an abundant acyclic and uniformly sign-coherent quiver, where
$v_{1}\prec v_{2}\prec\dots\prec v_{n}$ is its unique acyclic ordering. Pick a
vertex $v_{j}$ of $Q$ for $j\in[n]$, and let
$Q^{j}=\mu_{{\boldsymbol{w}}_{j}}(Q)$ for
${\boldsymbol{w}}_{j}=[v_{1},v_{2},\dots,v_{j}]$. If $v_{j}$ is red in $Q$,
then $v_{1},v_{2},\dots,v_{j-1}$ are red vertices and $v_{j}$ is a green
vertex in $Q^{j}$.

###### Proof.

As ${\boldsymbol{w}}_{i}$ is a source mutation sequence for all $i$ such that
$1\leq i<j\leq n$, we know that $v_{i}$ is a source in $Q^{i-1}$, where
$Q^{0}=Q$. If $v_{i}$ is green or blue in $Q^{i-1}$, then mutating at $v_{i}$
does nothing but flip the arrows —even the arrows between $v_{i}$ and frozen
vertices— touching it. This would make $v_{i}$ red or blue in $Q^{i}$. If
$v_{i}$ is red in $Q^{i-1}$, then mutation at $v_{i}$ adds arrows from frozen
vertices to every mutable vertex. As such, all blue vertices in $Q^{i-1}$
become red vertices in $Q^{i}$. Let $w$ be a frozen vertex touching $v_{i}$ in
$Q^{i-1}$. If $v_{k}$ is a red vertex of $Q^{i-1}$ for some $k\neq i$, then
the subquiver given in Figure 6 exists in $Q^{i-1}$ for $a\geq 2$, $b\geq 1$,
and $c\geq 0$.

${w}$${v_{i}}$${v_{k}}$$\scriptstyle{b}$$\scriptstyle{a}$$\scriptstyle{c}$
Figure 6. Subquiver of $Q^{i-1}$ Induced by $\\{v_{i},v_{k},w\\}$

After mutation at $i$, we have $c+ab$ arrows between $w$ and $v_{k}$, where
$c+ab>b$ as $a\geq 2$. This shows that any red vertices in $Q^{i-1}$ other
than $v_{i}$ remain red in $Q^{i}$ and that the number of arrows between a
frozen vertex and red vertex in $Q^{i-1}$ increases after mutation at a red
$v_{i}$. Applying this concept to $v_{j}$ shows that $v_{j}$ is red in
$Q^{j-1}$. Additionally, if $v_{i}$ is green in $Q^{j-1}$ for any $i<j$ and
$w$ is a frozen vertex touching $v_{i}$, then $v_{i}$ was a red vertex
touching $w$ in $Q^{i-1}$. Our previous argument then shows that the quiver
given in Figure 7 is a subquiver of $Q^{j-1}$ where $a\geq 2$ and $b<c$. Thus
mutating at $v_{j}$ forces $v_{i}$ to be red in $Q^{j}$. The result then
follows.

${w}$${v_{i}}$${v_{j}}$$\scriptstyle{b}$$\scriptstyle{a}$$\scriptstyle{c}$
Figure 7. Subquiver of $Q^{j-1}$ Induced by $\\{v_{i},v_{j},w\\}$

∎

If the sink of $Q$ is red, then we get the following corollary.

######  Corollary 4.3.

Let $Q$ be an abundant acyclic and uniformly sign-coherent quiver, where
$v_{1}\prec v_{2}\prec\dots\prec v_{n}$ is its unique acyclic ordering. If
$v_{n}$ is red in $Q$, then $\mu_{{\boldsymbol{w}}_{n}}(Q)$ has $n-1$ red
vertices and one green vertex $v_{n}$ for
${\boldsymbol{w}}_{n}=[v_{1},v_{2},\dots,v_{n}]$.

Lemma 4.2 combines with Lemma 3.5 to control the color of $r$ in $F^{j}$.

######  Corollary 4.4.

Let $F$ be a uniformly sign-coherent fork with point of return $r$, where
$v_{1}\prec v_{2}\prec\dots\prec v_{n-1}$ is the unique acyclic ordering on
$F\setminus\\{r\\}$. Additionally, let $F^{j}=\mu_{{\boldsymbol{w}}_{j}}(F)$
for ${\boldsymbol{w}}_{j}=[v_{1},v_{2},\dots,v_{j}]$ whenever $j\leq n-1$. If
$r$ is red, then it can be any color in $F^{j}$. If $r$ is green, then it
remains green in $F^{j}$. If $r$ is blue, then it is only blue in $F^{j}$ if
no vertex $v_{i}$ is green in $F^{i-1}$ for all $i\leq j$. Otherwise, it will
become green in $F^{j}$. Furthermore, if $v_{n-1}$ is red in $F$, then it is
both green in $F^{n-1}$ and the only non-red vertex in
$F^{n-1}\setminus\\{r\\}$.

From Corollary 4.4, if the sink of $F\setminus\\{r\\}$ is red, then we can
readily mutate to a fork with at most 2 green vertices. However, we do not
need this restriction, as any color will do.

######  Lemma 4.5.

Let $F$ be a uniformly sign-coherent fork with point of return $r$, where
$v_{1}\prec v_{2}\prec\dots\prec v_{n-1}$ is the unique acyclic ordering on
$F\setminus\\{r\\}$. Then there is a mutation sequence of length at most $n+4$
ending in a fork with a green point of return, at most one other green vertex,
and at least $n-2$ red vertices.

###### Proof.

Suppose first that $v_{n-1}$ is red. If $r$ is red or blue, mutate at
$v_{n-1}$. This will produce a fork $F^{\prime}$ with a green point of return
$v_{n-1}$ and a red sink $r$ in $F^{\prime}\setminus\\{v_{n-1}\\}$ by Lemma
3.4. If $r$ is instead green, we already have a fork with a green point of
return and a red sink. We may then apply Corollary 4.4 to get the desired
result in at most $n$ mutations in both cases.

Assume now that $v_{n-1}$ is green. If $r$ is red, then mutate at $v_{n-1}$.
This will produce a fork $F^{\prime}$ with a red point of return $v_{n-1}$ and
a red sink $r$ in $F^{\prime}\setminus\\{v_{n-1}\\}$. If $r$ is green or blue,
then mutating $F$ along $[v_{n-1},r]$ will produce another fork $F^{*}$ with a
red or blue point of return $r$ and a red sink $v_{n-1}$ in
$F^{*}\setminus\\{r\\}$. Both of these reduce to our previous case, netting a
max of $n+2$ total mutations.

Assume that $v_{n-1}$ is blue. If $r$ is red or green, mutate at $v_{n-1}$.
This will produce a fork $F^{\prime}$ with a blue point of return $v_{n-1}$
and a red or green sink $r$ in $F^{\prime}\setminus\\{v_{n-1}\\}$. Either
situation reduces to one of our previous cases, giving us a max of $n+3$ total
mutations.

Finally, if $r$ and $v_{n-1}$ are both blue, there must be some other vertex
$v_{j}\prec v_{n-1}$ in $F$ that is not blue by our assumption on uniformly
sign-coherent quivers. Mutate at $v_{j}$. Let $F^{*}$ be the fork obtained
after mutating at $v_{j}$. Then $F^{*}$ has a red or green point of return and
one of $v_{n-1}$ or $r$ is the sink of $F^{*}\setminus\\{v_{j}\\}$ by Lemma
3.4. This gives us one of the three previous cases, so we have arrived at a
max of $n+4$ total mutations. ∎

As we only need strictly sign-coherent, we have the following corollary.

######  Corollary 4.6.

Let $F$ be a strictly sign-coherent fork with point of return $r$, where
$v_{1}\prec v_{2}\prec\dots\prec v_{n-1}$ is the unique acyclic ordering on
$F\setminus\\{r\\}$. Then there is a mutation sequence of length at most $n+2$
ending in a fork with a green point of return, at most one other green vertex,
and at least $n-2$ red vertices.

Given an arbitrary fork $F$, Corollary 4.6 shows $\text{uRed}(F)\geq n-2$. All
that remains is to chip away at one of remaining green vertices.

######  Lemma 4.7.

Let $F$ be a strictly sign-coherent fork with point of return $r$, where
$v_{1}\prec v_{2}\prec\dots\prec v_{n-1}$ is the unique acyclic ordering on
$F\setminus\\{r\\}$. If $r$ and $v_{j}$ are the only two green vertices of
$F$, then $F$ has a mutation sequence —of length at most $j+2$— ending in a
fork with at least $n-1$ red vertices.

###### Proof.

If $j=1$, then mutate at $v_{1}$ to arrive at a fork with a single green
vertex $r$. Suppose then that $j>1$. Since $v_{j}$ was the first green vertex
in the acyclic ordering of $F\setminus\\{r\\}$, we know that $v_{j-1}$ is red
in $F$. By Corollaries 4.3 and 4.4, we know that the vertices $v_{j-1}$,
$v_{j}$, and $r$ are the only possibly green vertices of
$F^{j-1}=\mu_{{\boldsymbol{w}}_{j-1}}(F)$. As $r$ is green, mutating at $r$
produces a fork $F^{\prime}$ with red point of return $r$ and green $v_{j-1}$.
Since $r$ was a source in $F^{j-1}\setminus\\{v_{j-1}\\}$, we know that
$v_{j-1}$ and $v_{j}$ are the only two possibly green vertices in
$F^{\prime}$. If $v_{j}$ is red, then we have arrived at the general reddening
sequence ${\boldsymbol{w}}_{j-1}[r]$, as $v_{j-1}$ must still be green. If
$v_{j}$ is green, then mutate at $v_{j-1}$. Let
$\tilde{F}=\mu_{v_{j-1}}(F^{\prime})$. As the acyclic ordering of
$F^{\prime}\setminus\\{r\\}$ is $v_{j-1}\prec v_{j}\prec\dots\prec
v_{n-1}\prec v_{1}\prec\dots\prec v_{j-2}$ by Corollary 3.6, this will make
$v_{j}$ a green source of $\tilde{F}\setminus\\{r\\}$. Mutation at $v_{j-1}$
will also swap $r$ from red to green and $v_{j-1}$ from green to red, meaning
$r$ and $v_{j}$ are the only green vertices.

${w}$${r}$${v_{j-1}}$$\scriptstyle{b}$$\scriptstyle{a}$$\scriptstyle{c}$
Figure 8. Subquiver of $F^{j-1}$ Induced by $\\{r,v_{j-1},w\\}$

To see why, observe the subquiver of $F^{j-1}$ given in Figure 8 for some
frozen vertex $w$ that touches $r$, $a\geq 2$, $b\geq 1$, and $c\geq 0$.
Mutation at $r$ produces the subquiver of $F^{\prime}$ given in Figure 9. As
$a>1$, further mutation at $v_{j-1}$ gives the subquiver of $\tilde{F}$ given
in Figure 10, where $a^{2}b+ac-b>0$. Hence, the vertex $r$ must be green and
$v_{j-1}$ must be red in $\tilde{F}$.

${w}$${r}$${v_{j-1}}$$\scriptstyle{b}$$\scriptstyle{a}$$\scriptstyle{ab+c}$
Figure 9. Subquiver of $F^{\prime}$ Induced by $\\{r,v_{j-1},w\\}$

Finally, as $v_{j}$ is a green source of $\tilde{F}\setminus\\{r\\}$, we
mutate at $v_{j}$ to arrive at a fork with a singular green vertex $r$. This
completes the mutation sequence of length at most $j+2$.

${w}$${r}$${v_{j-1}}$$\scriptstyle{a^{2}b+ac-b}$$\scriptstyle{a}$$\scriptstyle{ab+c}$
Figure 10. Subquiver of $\tilde{F}$ Induced by $\\{r,v_{j-1},w\\}$

∎

We may then prove our main theorem.

######  Theorem 4.8.

Let $F$ be a strictly sign-coherent fork on $n$ vertices. Then there exists a
mutation sequence of length at most $2n+3$ ending in a fork with at least
$n-1$ red vertices.

###### Proof.

By Corollary 4.6, it takes at most $n+2$ mutations to arrive at a fork with a
green point of return and at most one other green vertex. By Lemma 4.7, once
we have arrived at such a fork, it takes at most $n+1$ mutations to find a
fork with $n-1$ red vertices and $1$ green vertex. As such, there exists a
mutation sequence of length at most $2n+3$ ending in a fork with at least
$n-1$ red vertices for every strictly sign-coherent fork on $n$ vertices. ∎

Now, if we have a connected, mutation-infinite quiver $Q$ that is framed, then
Theorem 2.11 tells us that we can mutate to a strictly sign-coherent fork.
That gives us our main result as the following corollary.

######  Corollary 4.9.

Every connected, mutation-infinite quiver $Q$ on $n$ vertices has $uRed(Q)\geq
n-1$. Furthermore, if $Q$ is any quiver on $n$ vertices, then
$\text{uRed}(Q)=n-c$, where $c$ is the number of connected components of $Q$
that do not admit reddening sequences.

## References

  * [1] Diana Ahmad and Fang Li.  Orbit-maximal green sequences and general-maximal green sequences.  Italian Journal of Pure And Applied Mathematics, 44:483–498, July 2020.
  * [2] Jørgen Bang-Jensen and Gregory Gutin, editors.  Classes of Directed Graphs.  Springer Monographs in Mathematics. Springer International Publishing, Cham, 2018.
  * [3] Eric Bucher and John Machacek.  Red Sizes of Quivers.  Arnold Mathematical Journal, March 2023.
  * [4] Peigen Cao and Fang Li.  Uniform column sign-coherence and the existence of maximal green sequences.  Journal of Algebraic Combinatorics, 50(4):403–417, December 2019\.
  * [5] Laurent Demonet and Bernhard Keller.  A survey on maximal green sequences, December 2020.  arXiv:1904.09247 [math].
  * [6] Harm Derksen, Jerzy Weyman, and Andrei Zelevinsky.  Quivers with potentials and their representations II: Applications to cluster algebras.  Journal of the American Mathematical Society, 23(3):749–790, July 2010.
  * [7] Bernhard Keller.  On cluster theory and quantum dilogarithm identities, September 2011.  ISBN: 9783037191019 9783037196014 ISSN: 2523-515X, 2523-5168 Pages: 85-116.
  * [8] Matthias Warkentin.  Exchange Graphs via Quiver Mutation.  Dissertation, page 103, January 2014.