# Implicit Knowledge in Argumentative Texts: An Annotated Corpus

Maria Becker, Katharina Korfhage, Anette Frank
Institute of Computational Linguistics Heidelberg University
<EMAIL_ADDRESS>

###### Abstract

When speaking or writing, people omit information that seems clear and
evident, such that only part of the message is expressed in words. Especially
in argumentative texts it is very common that (important) parts of the
argument are implied and omitted. We hypothesize that for argument analysis it
will be beneficial to reconstruct this implied information. As a starting
point for filling such knowledge gaps, we build a corpus consisting of high-
quality human annotations of missing and implied information in argumentative
texts. To learn more about the characteristics of both the argumentative texts
and the added information, we further annotate the data with semantic clause
types and commonsense knowledge relations. The outcome of our work is a
carefully designed and richly annotated dataset, for which we then provide an
in-depth analysis by investigating characteristic distributions and
correlations of the assigned labels. We reveal interesting patterns and
intersections between the annotation categories and properties of our dataset,
which enable insights into the characteristics of both argumentative texts and
implicit knowledge in terms of structural features and semantic information.
The results of our analysis can help to assist automated argument analysis and
can guide the process of revealing implicit information in argumentative texts
automatically.

##  1 Introduction

In everyday communication as well as in written texts people omit information
that seems clear and evident, such that only part of the message needs to be
expressed in words Grice (1975). While this information can easily be filled
in by the hearer, a computational system typically does not possess
commonsense or domain-specific knowledge that is needed to reconstruct the
implied information. Especially in argumentative texts it is very common that
(important) parts of the argument such as warrants are implied and omitted
Rajendran et al. (2016); Becker et al. (2017b); Hulpus et al. (2019). This
leads us to the assumption that the logic of an argument is in general not
fully recoverable from what is explicitly said, and that for argument analysis
it will be beneficial to reconstruct such implied information.
We aim to fill such gaps by identifying and inserting knowledge that connects
given statements. To perform this, we want to learn from human-generated data
of missing and implied information. This motivates the current work, in which
we gather high-quality annotations of implied knowledge in the form of simple
natural language sentences. The annotations are performed on pairs of
argumentative units from the Microtexts Corpus Peldszus and Stede (2015), a
very concise and focused argumentation dataset which is already annotated with
argumentative components and relations such as support, rebuttal or undercut.
For all unit pairs they are presented with, annotators are asked to add the
information that makes the connection between the units explicit, using short
and simple sentences. To learn more about the nature and characteristics of
both the argumentative texts and the added information, we further annotate
the data with two specific semantic information types: semantic clause types
Friedrich and Palmer (2014) and ConceptNet knowledge relations Speer and
Havasi (2012); Havasi et al. (2009), which were both found to be
characteristic for argumentative texts Becker et al. (2016a, 2017b). The
outcome of our work is a carefully designed and richly annotated dataset, for
which we provide an in-depth analysis by investigating characteristic
distributions and correlations between the assigned labels.

The contributions of this work are: (i) high-quality annotations of implicit
knowledge on the argumentative Microtext corpus, (ii) characterization of the
argumentative units from the Microtext corpus and the inserted sentences in
terms of semantic clause types and commonsense knowledge relations; and (iii)
an in-depth study of properties and correlations of the assigned labels. The
dataset will be made public as an extension to the Microtext corpus Peldszus
and Stede (2015) to support further research in argument analysis.

##  2 Related Work

Finding and Adding Implicit Knowledge in Arguments. Relatively little
attention has been devoted so far to the task of finding and adding implicit
knowledge in arguments, which is closely related to the task of enthymeme
reconstruction. Enthymemes – arguments with missing propositions – are common
in natural language and particularly in argumentative texts Rajendran et al.
(2016). Razuvayevskaya and Teufel (2016) present a feasibility study on the
automatic detection of enthymemes in real-world texts and find that specific
discourse markers (e.g. let alone, because) can signal enthymemes. Using these
as trigger words, they reconstruct enthymemes from the local context, while
Rajendran et al. (2016) retrieve and fill missing propositions in arguments
from similar or related arguments.
Becker et al. (2016a) and Becker et al. (2016b) show that argumentative texts
are rich in generic and generalizing sentences, which are semantic clause
types Friedrich and Palmer (2014) that often express commonsense knowledge. We
will show that large portions of implied knowledge in argumentative texts are
naturally stated using these clause types.
In their attempt to reconstruct implicit knowledge, Boltuzic and Snajder
(2016) find that the claims that users make in online debate platforms often
build on implicit knowledge. They show that the amount of implicitness is
dependent on genre and register and point out that the reconstruction of
implicit premises can be helpful for claim detection.
Recently, Hulpus et al. (2019) point out the relevance of reconstructing
implicit knowledge for understanding arguments in a computational setting, by
proposing the task of argument explicitation, which they define as a task that
makes explicit both (i) the structure of a natural language argument, as well
as (ii) the background knowledge the argument is built on, in the form of
implicit premises or contextual knowledge.

These studies reinforce the view that a substantial amount of knowledge is
needed for the correct interpretation and analysis of argumentative texts, and
thus filling knowledge gaps in argumentative texts will be beneficial for
argument analysis.

Related Datasets. Boltuzic and Snajder (2016) release a small dataset with
human-provided implicit premises based on data from online debate platforms,
consisting of 125 claim pairs annotated with the premises that connect them.
In contrast to our approach they asked the annotators to provide the premises
that bridge the gap between the two claims without giving any further
instructions, resulting in a substantial variance in both the wording and the
average number of premises.

Becker et al. (2017b) design a process for obtaining high-quality implied
knowledge annotations for German argumentative microtexts Peldszus and Stede
(2015), in the form of simple natural language statements which are then
further characterized with semantic clause types and commonsense knowledge
relations. Since the decision of what exactly is missing and how detailed such
information should be can be subjective, they propose several steps to promote
agreement among the annotators and monitor its evolution using textual
similarity computation. The implicit knowledge annotations we present in this
paper are also based on argumentative microtexts Peldszus and Stede (2015),
thus our corpus can be seen as an extension of the corpus published by Becker
et al. (2017b). The main differences are that (i) our data is in English (as
opposed to German), (ii) the semantic clause types and commonsense knowledge
relations are not only annotated for the inserted sentences, but are also
available for the argumentative texts themselves, (iii) our corpus includes
more annotated unit pairs, and that (iv) in our corpus all annotations are
conducted by expert annotators.

Habernal et al. (2018) present the argument reasoning comprehension task,
where given an argument with a claim and a premise, the goal is to choose the
correct implicit warrant from two options. Both warrants are plausible and
lexically close, but lead to contradicting claims. They provide a dataset
where Amazon Turkers added warrants for 2k arguments from news comments. As
opposed to our dataset, the annotators were only supposed to fill in the gap
between a pair of claim and premise, while we consider larger arguments
consisting of a claim and several premises. Furthermore, we annotate implicit
information not only between claim and premises, but between all adjacent
argument units and all argument units that stand in a direct argumentative
relation (cf. Sec. 3.2). The second major difference is that in Habernal et
al. (2018) the annotators were only asked to add one warrant (one sentence)
per argument, while we assume that more than one sentence might be needed to
fill a knowledge gap in an argument.

##  3 Enriching Argumentative Texts with Implicit Knowledge

###  3.1 General Annotation Procedure

The main goal of our annotation project is to uncover and characterize
implicit knowledge that connects a given pair of argumentative units. This
overall objective is subdivided into two consecutive annotation tasks:

i.

First, we ask the annotators to detect missing knowledge that connects a pair
of argumentative units, and to express this knowledge in terms of simple
natural language statements.

ii.

In the next step (cf. Sec. 4), the annotators are tasked with labeling both
the inserted sentences and the given argumentative text units with
characterizing semantic information. The annotation types that we select are
semantic clause types Friedrich and Palmer (2014) and commonsense knowledge
relations, following the ConceptNet relation inventory Havasi et al. (2009).

###  3.2 The Microtext Corpus

Figure 1: Example of a microtext (argument graph).

As basis for our annotations we use the argumentative Microtext corpus
Peldszus and Stede (2015), which consists of 112 microtexts. The corpus was
created in German and has been translated to English. In this work we use only
the English version (for annotations on the German version, cf. Becker et al.
(2017b)). Each microtext is a short, dense argument consisting of roughly five
elementary units of argumentation, so called argumentative units Peldszus and
Stede (2015). The texts are written in response to a question on a potentially
controversial issue (e.g. Should there be a cap on rent increases for a change
of tenant?). Writers were asked to include a direct statement of their main
claim as well as at least one objection to that claim. The generated arguments
were then manually annotated with argumentation graphs (one graph per
microtext, cf. Fig. 1 for an example) according to a scheme based on Freeman’s
theory of the macro-structure of argumentation Freeman (2011). The nodes in
the graph are argumentative units and the edges are argumentative relations
between them. The most frequent relations are support (premise which supports
a conclusion or another premise), rebuttal (premise that attacks a conclusion
or premise by challenging its acceptability), or undercut (premise which
attacks the acceptability of an argumentative relation between two
propositions).
For our work we extract pairs of argumentative units that either stand in a
direct argumentative relation (that means units that are directly connected in
the argument graph), or units that are adjacent to each other, or both. In sum
we extract 719 pairs of argumentative units which we then provide to our
annotators to perform several different annotation tasks that we describe in
the following sections.

###  3.3 Annotating Implicit Knowledge

We asked our annotators to detect whether the connection between the pair of
units is made fully explicit by the text, and if this is not the case, to
explain the missing connection by providing one or more sentences that make
this connection explicit. Our annotators were supposed to add as few sentences
as possible and to make these sentences very simple (if possible one fact per
sentence) in order to retrieve the minimal amount of information that is
needed to connect the two units and to avoid too detailed explanations. Since
some unit pairs only make sense with a larger context, for every pair we also
displayed the full microtext. Figure 2 shows two examples of the annotations,
where in the first one the main claim _1-a_ is attacked by statement _1-b_ ,
while in the second one the premise _2-b_ supports the main claim _2-a_. The
knowledge underlying the connection between the main claim and the premise in
both cases is made explicit in _c_ respectively, whereby for the first example
one and for the second example two sentences have been inserted.

(1-a) BER should be re-conceptualized from scratch
(1-b) even if billions of Euros have already been invested
in the existing airport project.
(1-c) BER is an airport.

(2-a) Capital punishment is not a solution
(2-b) as it cannot be ruled out that the judicial process
may make mistakes.
(2-c-I) In a judicial process it is decided about capital
punishment.
(2-c-II) Mistakes don’t lead to solutions.

Figure 2: Example annotations for explicating implicit knowledge (c) that
connects argumentative units (a&b).

The difficulty of eliciting such implicit knowledge in an annotation task is
that intuitions about which knowledge exactly is missing may be different
between annotators, and even if their intuitions match, the phrasing may be
different, structurally or in terms of lexical choice. In order to enforce
agreement and to assess the quality of the annotations, Becker et al. (2017b)
design a multi-step annotation process where annotators are asked to review
and revise each other’s annotations, whereby the evolution of agreement during
this process is monitored using computational measures of semantic textual
similarity. Becker et al. (2017b) use five annotators for each argumentative
unit pair, while we train two expert annotators with a linguistic background
who produce two versions of the implicit knowledge, which then serve as the
basis for the final gold standard produced by another expert annotator (one of
the authors). This final adjudicated corpus provides the basis for the second
annotation step (Sec. 4) and our analyses in Sec. 5.

###  3.4 Annotation Statistics

Annotator Agreement. Building on the insights of Becker et al. (2017b), we
calculate the semantic similarity of the two initial annotations in order to
evaluate the agreement between the annotators and compare it to the similarity
scores reported in Becker et al. (2017b). Following Becker et al. (2017b), we
quantify the distance between the annotations using the Word Mover’s Distance
Kusner et al. (2015) as implemented in
gensim111https://radimrehurek.com/gensim. The Word Mover’s Distance (WMD)
measures the dissimilarity between two documents as the aggregated minimum
distance in an embedding space that the (non-stopword) words of one document
need to “travel” to reach the (non-stopword) word of another document. As
embeddings, we use 300-dimensional skip-gram word2vec embeddings trained on
part of the Google News dataset (100 billion words, Mikolov et al. (2013)).
We compare the complete annotation for each argumentative unit pair (as
opposed to sentence by sentence) and measure a WMD distance score of 1.97.
Becker et al. (2017b) compare distance scores between implicit knowledge
annotations produced in early vs. later stages of their multi-step annotation
procedure. In their first two rounds of annotations which include initial
annotations and mutual editing and correcting, they compute a WMD of 2.2 and
3.08, and in the third round where the corrected annotations are merged by new
annotators, the WMD decreases to 1.89, demonstrating the evolution of
annotator agreement. Our score of 1.97 is closest to the score reported for
the third round, which we interpret as sufficient agreement between the
annotators.

##  4 Annotating Argumentative Texts and Implicit Knowledge with Additional
Information

Learning from Human Annotations. We hypothesize that the more we know about
the knowledge that is needed to establish links between (argumentative)
sentences, the easier it will be to reconstruct them automatically. All of the
following tasks are therefore designed with the ultimate goal of learning more
about the properties of the sentences that were stated by our annotators to
make the missing information explicit, within their surrounding explicit
context.
We expect semantic clause types to be useful features for characterizing
argumentative texts, implicit knowledge and their interaction, since clause
types have shown to be relevant for interpreting semantics at the clause level
and discourse structure (cf. Friedrich and Palmer (2014)). Furthermore, Becker
et al. (2016b) showed that the distribution of these clause types is
distinctive for argumentative texts compared to other genres in terms of
particularly high ratios of generic and generalizing sentences.
We furthermore expect ConceptNet Speer and Havasi (2012) to be a useful
resource for finding and characterizing implicit sentences, since implied
information is usually commonsense knowledge that seems clear and evident and
is for that reason omitted. ConceptNet provides exactly that kind of
information, since it contains commonsense facts about the world and everyday
life (cf. Sec. 4.2). Also, the relation inventory of ConceptNet is targeted
for capturing commonsense knowledge, and we therefore expect it to be
appropriate for labeling and characterizing implicit knowledge.

What additionally makes clause types and commonsense relations attractive
features for analyzing and characterizing argumentative texts and implicit
knowledge is that recently for both – semantic clause types (Becker et al.
(2017a)) and commonsense relations (Becker et al. (2019)) – automated
classification models have been published, which can be used for pre-labeling
the given texts and therefore facilitate the automatic analysis of arguments
and implicit knowledge.

###  4.1 Annotating Semantic Clause Types

Inventory and Annotation Process. We asked the annotators to characterize both
the argumentative units from the microtexts and the gold standard of the
inserted sentences by labeling them with Semantic Clause Types. For the
inventory we adopt the most frequent types in Friedrich and Palmer (2014) and
give examples from our dataset:

States

(STA) describe specific properties of individuals:
The Mayor of Berlin has an interest in Berlin’s coffers.

Events

(EVT) are things that happen or have happened:
Edward Snowden revealed information.

Generic Sentences

(GEN) are predicates over classes or kinds: Supermarkets should open on
Sundays.

Generalizing Sentences

(GNZ) describe regularly occurring events/habits: Germany produces much
rubbish.

The annotations are performed independently by two trained annotators who
assign labels at the clause level, whereby one sentence may contain more than
one clause.

Statistics. We measure a fair annotator agreement of 34.02% (Cohen’s Kappa)
and produce a gold standard done by an expert annotator (one of the authors)
that provides the basis of our final analysis. Table 1 displays the
distribution of semantic clause types within the implicit information
annotations and the argumentative units from the microtexts, which we then
compare to the numbers reported for other genres Becker et al. (2016b). We
find a high proportion of Generics within the Microtexts (64%) and an even
higher amount within he implicit information annotations (84%), while the
other genres (reports, speeches, fiction) rather contain mostly States and
Events. This indicates the relevance of knowledge captured by Generic
Sentences within the added implicit information, and we can use this finding
for acquiring such missing information automatically.

Genre |  GEN |  GNZ |  STA |  EVT
---|---|---|---|---
Impl. Information |  0.84 |  0.02 |  0.13 |  0.01
Microtexts |  0.64 |  0.05 |  0.24 |  0.02
Report |  0.03 |  0.04 |  0.54 |  0.39
TED Talk |  0.12 |  0.03 |  0.49 |  0.36
Fiction |  0.02 |  0.05 |  0.39 |  0.54
Table 1: Distribution of the most frequent Semantic Clause Types among
different genres (expressed as percentages)

###  4.2 Annotating Commonsense Knowledge Relations

Inventory and Annotation Process. In addition to clause types we annotate the
argumentative units and the inserted sentences with ConceptNet relation types.
ConceptNet Havasi et al. (2009); Speer and Havasi (2012) is a semantic network
that contains commonsense facts about the world collected from volunteers over
the Internet. Nodes in the network represent concepts in the form of words or
phrases, and edges the knowledge relations holding between them (e.g., health
insurance CapableOf cover ambulance transportation). The inventory covers 37
relations, some of which are commonly used in other resources like WordNet
(e.g., IsA, PartOf) while most others are targeted for capturing commonsense
knowledge and as such are particular to ConceptNet (e.g., HasPrerequisite,
MotivatedByGoal).
The annotation was performed by two annotators in parallel who were asked to
label all argumentative units and inserted sentences with ConceptNet relations
(irrespective of whether or not the relation instance is covered in
ConceptNet). The annotators labeled the complete relation triple by (I)
selecting and marking two concepts (from the same argumentative unit/inserted
sentence), and (II) the ConceptNet relation that they judge to hold between
them. Two examples from our dataset are given in Fig. 4. Note that we didn’t
mark the concepts beforehand, but let our annotators label both: the concepts
and the relation between them.222This sometimes led to disagreements between
annotators regarding the span they selected for the same concept, e.g. for the
sentence Sophisticated programmes should be financed by the licence fee, A
annotated the triple sophisticated programme, financed by licence fee
(ReceivesAction), and B sophisticated programme, financed (ReceivesAction).
This disagreement was harmonized in the gold version by the expert annotator.

Figure 3: Distribution of ConceptNet relations within Microtexts and Implicit
Information Annotations (in %)

In preliminary annotation experiments we observed that in many cases several
relations can be suitable for the same sentence (cf. example 2 in Fig. 4),
therefore we allowed for more than one relation per sentence/argumentative
unit. If none of the relations covered by the ConceptNet relation inventory
was fitting, our annotators inserted NONE and collected suggestions for
additional relations (such as Requires). We release these suggestions along
with examples from our data together with our dataset.

(I) Fees result in longer durations of studies.
Annotation: fees, longer durations of studies (Causes)

(II) Dog dirt is disgusting and a hygiene problem.
Annotation: dog dirt, disgusting (HasProperty)/
dog dirt, hygiene problem (IsA)

Figure 4: Sentences from our dataset annotated with ConceptNet relations.

Statistics. Our annotators used 25 relations from the inventory of 37 relation
types provided by ConceptNet to label the argumentative units from the
Microtexts and the inserted sentences. We measure annotator agreement for (I)
the marked concepts in order to evaluate if our annotators agree on the spans
of texts selected as concepts, and for (II) the assigned relations
(separately). (I) we measure in terms of word overlap and obtain high averaged
word overlap scores of 76.98% (Jaccard) and 84.87% (Dice), indicating solid
agreement between the selected concepts. (II) we measure in terms of Cohen’s
Kappa and achieve a moderate agreement of 45.05%. We produce a gold standard
done by an expert annotator (one of the authors) which provides the basis of
our final analysis. In this gold standard, on average 3.58 relation triples
were assigned per argumentative unit and 3.01 relation triples per inserted
sentence. The distribution of the 10 most frequent relation types is shown in
Fig. 3.

The most frequently occurring relation is CapableOf (19% within argumentative
units and 20% within inserted sentences) followed by HasProperty (16/12%) and
Causes (12/16%). The largest differences between relations assigned to
argumentative unit vs. inserted sentence we observe for HasProperty (4.6pp)
and ReceivesAction (2.8pp), both more prominent in microtexts, and Causes
(4.4pp), more prominent in implicit knowledge annotations. We find that only 9
of 576 argumentative units (1.56%) and 24 of 1295 inserted sentences (1.85%)
were identified as cases where none of the relations covered by the relation
inventory fits, which points to the fact that knowledge repositories such as
ConceptNet can play an important role in argument analysis and the retrieval
of implicit knowledge.

##  5 Analysis of the Annotations: Visualizing Correlations

In this section, we analyse correlations between the labels and properties
annotated for our dataset. In addition to the analysis of the statistics and
distribution of the labels annotated in our corpus (cf. Sec. 4), we want to
reveal patterns and intersections between the annotation categories and
properties of our dataset, with the goal of learning more about the
characteristics of both argumentative texts and implicit knowledge in terms of
structural features and semantic information. We expect the results of our
analysis to be helpful for guiding and enhancing the process of automated
argument analysis as well as of the automatic reconstruction of implicit
knowledge in argumentative texts.

###  5.1 Number of Hops

Hops - Adjacency and Relatedness of Argument Units. The gold version of our
dataset contains 719 pairs of argumentative units. 1295 sentences were
inserted, that is on average 1.8 sentences per argument pair. The pairs of
argumentative units either stand in a direct argumentative relation, which
means that they are directly connected in the argument graph (like e1 and e2
in Fig. 1), or the units are adjacent to each other (e1 and e2, e2 and e3 …),
or both (e1 and e2). We expect that more inserted sentences are needed to
connect argument pairs that stand in an argumentative relation but are are not
adjacent, since the missing information could be included in the intermediate
argument units (e.g., what is missing between e1 and e5 in Fig. 1 could be
expressed in e2, e3 or e4). We also hypothesize that more implicit information
is needed to connect argument pairs that don’t stand in a direct argumentative
relation, since argument units that aren’t related can come from different
chains of the argument and might therefore require more explications than
directly related argument units (cf. Fig. 1, e4 and e5). Since – by our
annotation design – the inserted sentences contain the minimal amount of
information that makes the connection between two argumentative units
explicit, we interpret each inserted sentence as one hop that is needed to
connect the given argument pair.
We find only a relatively small difference in the average number of sentences
inserted between adjacent (1.9) and non-adjacent units (1.62) (cf. Table 2),
indicating that it is not the case that more hops (inserted sentences) are
needed when units are not adjacent. Interestingly, on the other hand we
observe a remarkable difference between the number of sentences inserted
between argumentatively related (1.6, Table 3) and non-related units (2.14,
Table 3). This indicates that more hops are needed when there is no direct
argumentative relation between the argument units.

| adjacent | not adjacent
---|---|---
nb. of pairs | 464 | 255
percentage | 0.65 | 0.35
nb. of inserted sentences | 881 | 414
inserted sentences (avg) | 1.9 | 1.62
Table 2: Adjacency of argument pairs and number of inserted sentences, Gold.

Hops - Argumentative Relations. After revealing that more hops are required
for connecting non-related argumentative units, we are also interested whether
there are argumentative relations for which more hops are needed then for
others. Our dataset contains 5 argumentative relations, with support being the
most frequent one (37%) followed by rebuttal (15%) and undercut (8%) (cf.
Table 3). We find that for the undercut relation, most sentences are inserted
on average (1.84). This makes sense since undercuts challenge the
acceptability of an inference between two propositions (cf. Peldszus and Stede
(2015)) and can therefore be seen as a very complex relation that requires
more explications than others. The least sentences are inserted on average for
example relations (1.11 avg.), indicating that these are relations that
usually don’t need multi-hop connections of implicit knowledge.

| argument relation | inserted sentences
---|---|---
| total | percentage | total | per relation
support | 263 | 37 | 423 | 1.61
rebuttal | 108 | 15 | 165 | 1.53
undercut | 61 | 8 | 112 | 1.84
addition | 21 | 3 | 34 | 1.62
example | 9 | 1 | 10 | 1.11
relations total | 462 | 100 | 744 | 1.6
non-related units | 257 | 36 | 551 | 2.14
TOTAL | 719 | 100 | 1295 | 1.8
Table 3: Correlation between argumentative relations and number of hops
(inserted sentences).

Hops - Commonsense Relations. Next, we are interested whether there are co-
occurrences between the number of hops and commonsense relation types. We want
to investigate whether specific commonsense relation types appear more often
in single (one inserted sentence) vs. multiple hops (more than one inserted
sentence). Therefore, for all commonsense relations within inserted sentences,
we count how often they occur in one hop connections (when one sentence was
inserted as missing information), in two hop connections and so on. The
resulting heatmap is displayed in Fig. 5. We observe that all relations occur
most often within a set of two inserted sentences, which corresponds to the
average number of inserted sentences (1.8, cf. Table 3). Interestingly,
HasProperty and AtLocation are relations which occur only rarely within one
hop connections, the latter being most often used in sets of three inserted
sentences. Those relations seem to mark information units that require other
pieces of information to connect an argument pair.

Figure 5: Distribution of commonsense relations within inserted sentences
among hops, rel. freq. by relation type, with total number of hops given on
the left side.

Hops - Semantic Clause Types. Similarly, we want to investigate co-occurrences
between the number of hops and semantic clause types. Again, for all clause
types within inserted sentences, we count how often they occur in each set of
inserted sentences (1-5), Fig. 6 shows the resulting heatmap. We find that
States, Events and Generic Sentences occur most often within two hop
connections, while Generalizing Sentences are most often used within sets of
three inserted sentences and rarely when only one sentence was inserted.
Generalizing Sentences therefore can be interpreted as markers of information
units that stand-alone are not able to connect argument pairs, but rather co-
occur with other pieces of information for filling knowledge gaps in
argumentative texts.

Figure 6: Distribution of Semantic Clause Types among hops, relative frequency
by clause type.

###  5.2 Adjacency and Argumentative Relatedness

When filling knowledge gaps in argumentative texts automatically, it might be
useful to leverage the structure of an argument and to determine which type of
knowledge exactly is missing for which pair of argument units. Knowing the
semantic properties of the knowledge that is needed to connect argument units
that are – for example – adjacent vs. those that are not, can guide the
process of extracting knowledge for filling these gaps. Therefore, we want to
investigate whether the distribution of the semantic properties we annotated
for the inserted sentences – commonsense relation types and semantic clause
types – respectively differs depending on the internal structure of an
argument, in our case this is whether (i) the arguments from a given pair are
adjacent or not, and/or whether (ii) the arguments from a given pair are
argumentatively related or not.

Commonsense Relations. Fig. 7 (blue/orange bars) shows that the distribution
of commonsense relation types only slightly differs between adjacent and non-
adjacent units. We find that IsA (75%), AtLocation and HasProperty (both 72%)
occur most often within sentences inserted between adjacent units, while HasA
and CapableOf are relations that occur more often in sentences inserted
between non-adjacent units (36% and 35%). We also observe only slight
variations regarding the distribution of commonsense relations between units
that are argumentatively related and those that are not (Fig. 7, green/yellow
bars). While Causes (64%), CapableOf (61%) and HasA (61%) are often assigned
to sentences inserted between related units and therefore can be interpreted
as argumentatively relevant, IsA and AtLocation are typical labels for
implicit information between units that don’t stand in an direct argumentative
relation (51% and 49% for not related units).

Figure 7: Adjacency and Argumentative Relatedness for Commonsense Relations
(in %).

Semantic Clause Types. We also want to investigate whether the distribution of
Semantic Clause Types differs between adjacent and not adjacent units, and/or
between argumentatively related and not related units. Fig. 8 (blue/orange
bars) shows that States occur most often between units that are adjacent
(73%), while Events show the lowest proportion for adjacent units (56%).
Regarding the distribution of semantic clause types assigned to sentences
between argumentatively related and not related units (Fig. 8, green/yellow
bars), we find a large difference for Events (78% between related and 22%
between not related units) and Generalizing Sentences (71%/29%), while States
(53%/47%) and Generic Sentences (58%/42%) are more equally distributed.

Figure 8: Adjacency and Argumentative Relatedness for Semantic Clause Types
(in %).

###  5.3 Correlations between Assigned Labels

In this section, we analyse correlations between argumentative relations,
commonsense relations and semantic clause types. We want to reveal patterns
and intersections between the annotation categories in order to learn more
about the structural features and semantic properties of both argumentative
texts and implicit knowledge. For all analyses reported in this section, we
measure correlations using the Matthews correlation coefficient (MCC) Matthews
(1975), which assigns correlation coefficient values between -1 and +1 to
pairs of labels (here e.g. support and Causes). A coefficient of +1 represents
a perfect correlation, 0 an average random prediction, and -1 an inverse
correlation.

Argumentative Relation - Commonsense Relation. First, we look at correlations
between argumentative relations and commonsense relations. We want to
investigate if specific commonsense relations express specific argumentative
relations, and if specific argumentative relations are more characteristic for
specific commonsense relations than others. Fig. 10 shows that the relation
Causes is very dominant within sentences inserted between argument units that
stand in a support relation, which reveals the importance of causal
explanations for filling knowledge gaps between supporting argument units. An
example of our dataset is given in Fig. 9. The relations ReceivesAction and
HasA correlate negatively with support but positively with rebuttals,
underlining the difference in distributions of commonsense relation types
between these two contrary argumentative relations. We also observe that
rebuttals correlate negatively with Causes, indicating that causal
explanations are not typical for connecting argument units that rebut each
other.

(e2) The developments in that conflict should not be left
to former Cold War opponents alone,
(e3) for that course can only lead to escalation in some form.
——————————————————————–
Implicit Information: A conflict may lead to escalation.
Commonsense Relation: conflict, escalation (Causes)

Figure 9: Example of a causal explication for a support relation (e3 supports
e2). Figure 10: Correlations between Argumentative Relations and Commonsense
Relations, MCC correlation matrix. Bright colours indicate positive and dark
colours negative correlation from a scale between +1 and -1.

Argumentative Relation - Semantic Clause Type. Next, we are interested in the
correlations between argumentative relations and semantic clause types. We
analyse if specific argumentative relations are more characteristic for
specific clause types, and vice versa, if specific clause types correlate with
specific argumentative relations. Fig. 10 shows that examples differ from the
rest of argumentative relations regarding the correlations with clause types:
while we find high positive correlations with States and Events, Generics very
infrequently co-occur with examples. This makes sense since examples usually
express knowledge about individuals rather then generic knowledge (cf. Becker
et al. (2016a)). Our correlation analysis also reveals interesting patterns
regarding the support relation: here we find a negative correlation with
States and a positive correlation with Generic Sentences, indicating the
importance of generic knowledge for sentences that connect two argument units
which support each other. Interestingly, when looking at the correlations
between Generic Sentences and argument relations, we find that this is the
only positive correlation, while all others are negative. This underlines the
finding that Generics can be seen as an important feature of sentences
inserted between supporting argument units.

Figure 11: Correlations between Argumentative Relations and Semantic Clause
Types, MCC correlation matrix.

Commonsense Relation - Semantic Clause Type. There are also some interesting
correlations between commonsense relations and semantic clause types which we
display in Fig. 12. We aim to discover whether (i) specific clause types are
indicators for certain commonsense relations or vice versa, and whether (ii)
the distribution of clause types among certain commonsense relations differs
between microtexts and inserted sentences. Fig. 12 (left) shows that within
the microtexts, Generic Sentences correlate negatively with IsA, AtLocation
and PartOf, and positively with ReceivesAction and HasPrerequisite. For the
three relations IsA, AtLocation and PartOf we find a positive correlation with
States and Events and a negative correlation with Generic Sentences,
indicating that these relations typically express individual rather than
generic knowledge. Fig. 12 (right) shows that the correlations within the
inserted sentences are not as strong as in the microtexts, but still we can
see that similar to the microtexts, Generic Sentences correlate negatively
with IsA and PartOf, while we can’t observe a strong positive correlation
between States and any commonsense relation. The only high positive
correlation we find is between IsA and States, indicating that within the
inserted sentences (as well as within the microtexts), IsA relations typically
describe specific properties of individuals (cf. Sec. 4.1).

Figure 12: Correlations between Commonsense Relations and Semantic Clause
Types in Microtexts (left) vs. Inserted Sentences (right), MCC correlation
matrix.

##  6 Conclusion and Outlook

In this paper, we presented a carefully designed dataset consisting of high-
quality human annotations of implicit knowledge in argumentative texts. To
learn more about the characteristics of both the argumentative texts and the
added information, we further annotated the data with semantic clause types
and commonsense knowledge relations. We then provided an in-depth analysis of
our annotated dataset with the goal of revealing characteristic distributions
and correlations, co-occurring patterns and intersections between the
annotation categories. This helped us to gain insights into the properties of
both argumentative texts and implicit knowledge in terms of structural
features and semantic information: We found for example that Generic Sentences
play a dominant role within the inserted sentences, indicating the relevance
of generic knowledge within implicit information. Almost all sentences in our
dataset – from both the microtexts and the inserted information – could be
mapped to commonsense knowledge relations, pointing to the fact that knowledge
repositories such as ConceptNet can play an important role in argument
analysis and are an important source for the retrieval of implicit knowledge.
When analyzing correlations between the labels and structural properties of
our dataset, we could furthermore reveal patterns and intersections between
the annotation categories and structures of our dataset: We found for example
that more inserted sentences are needed when there is no direct argumentative
relation between the argumentative units, and that complex argumentative
relations such as undercut require more explications than other relations. Our
correlation analysis further demonstrated the benefit of leveraging the
structure of an argument and the characterization of the type of knowledge
that is needed to connect argument pairs. We investigated whether the
distribution of the semantic properties we annotated for the inserted
sentences differs depending on the internal structure of an argument and
revealed for example that States occur most often between units that are
adjacent, while Events are frequently used for connecting argumentatively
related units.
Finally, when investigating correlations between argumentative relations,
commonsense relations and semantic clause types, we could for example reveal
the importance of causal explanations (as expressed by the relation Causes)
for filling knowledge gaps between supporting argument units. Generics also
turned out to be a important feature of sentences inserted between supporting
argument units.

The knowledge we gained about the properties of argumentative texts and
implicit knowledge, and our observations on their interaction can assist
automated argument analysis, e.g., it can be beneficial for assessing the
strength of an argument, apart from the benefit of making the underlying
logics of the argument transparent for both humans and computational systems.
The results from our in-depth analysis can furthermore guide the process of
revealing implicit information in argumentative texts automatically, e.g. by
utilizing the revealed properties of implicit information and the observed
relations between implicit information and the surrounding argument units.

We release our dataset as an extension to the Microtext corpus. We expect it
to be a useful starting point for automatically filling knowledge gaps in
arguments, and we hope that it will inspire future research on argument
analysis and implicit knowledge acquisition.

## References

  * Becker et al. (2017a) Maria Becker, Michael Staniek, Vivi Nastase, Alexis Palmer, and Anette Frank. 2017a.  Classifying Semantic Clause Types: Modeling Context and Genre Characteristics with Recurrent Neural Networks and Attention.  In _Proceedings of *SEM (Joint Conference on Lexical and Computational Semantics)_.
  * Becker et al. (2016a) Maria Becker, Alexis Palmer, and Anette Frank. 2016a.  Argumentative texts and clause types.  In _Proceedings of the 3rd Workshop on Argument Mining (ArgMining2016)_ , pages 21–30, Berlin, Germany.
  * Becker et al. (2016b) Maria Becker, Alexis Palmer, and Anette Frank. 2016b.  Clause Types and Modality in Argumentative Microtexts.  In _Workshop on Foundations of the Language of Argumentation (in conjunction with COMMA)_ , pages 1–9, Potsdam, Germany.
  * Becker et al. (2017b) Maria Becker, Michael Staniek, Vivi Nastase, and Anette Frank. 2017b.  Enriching Argumentative Texts with Implicit Knowledge.  In _Applications of Natural Language to Data Bases (NLDB) - Natural Language Processing and Information Systems_ , Lecture Notes in Computer Science. Springer.
  * Becker et al. (2019) Maria Becker, Michael Staniek, Vivi Nastase, and Anette Frank. 2019.  Assessing the Difficulty of Classifying ConceptNet Relations in a Multi-Label Classification Setting.  In _RELATIONS - Workshop on meaning relations between phrases and sentences (co-located with IWCS)_.
  * Boltuzic and Snajder (2016) Filip Boltuzic and Jan Snajder. 2016.  Fill the Gap! Analyzing Implicit Premises between Claims from Online Debates.  In _Proceedings of the 3rd Workshop on Argument Mining_ , pages 124–133.
  * Freeman (2011) James B. Freeman. 2011.  _Argument Structure: Representation and Theory_ , volume 18 of _Argumentation Library_.  Springer.
  * Friedrich and Palmer (2014) Annemarie Friedrich and Alexis Palmer. 2014.  Automatic prediction of aspectual class of verbs in context.  In _Proceedings of the ACL 2014_.
  * Grice (1975) H Paul Grice. 1975.  Logic and conversation.  _1975_ , pages 41–58.
  * Habernal et al. (2018) Ivan Habernal, Henning Wachsmuth, Iryna Gurevych, and Benno Stein. 2018.  The argument reasoning comprehension task: Identification and reconstruction of implicit warrants.  In _Proceedings of the 16th Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1930–1940.
  * Havasi et al. (2009) C. Havasi, R. Speer, J. Pustejovsky, and H. Lieberman. 2009.  Digital intuition: Applying common sense using dimensionality reduction.  _IEEE Intelligent systems_ , 4(24):24–35.
  * Hulpus et al. (2019) Ioana Hulpus, Juri Opitz Graeme Hirst Christian Meilicke Vivi Nastase Heiner Stuckenschmidt Jonathan Kobbe, Maria Becker, and Anette Frank. 2019.  Towards Explaining Natural Language Arguments with Background Knowledge.  In _Proceedings of the 1st Workshop on Semantic Explainability – co-located with the 18th International Semantic Web Conference (ISWC 2019)_.
  * Kusner et al. (2015) Matt J. Kusner, Yu Sun, Nicholas I. Kolkin, and Kilian Q. Weinberger. 2015.  From Word Embeddings To Document Distances.  In _Proceedings of the 32nd International Conference on Machine Learning (ICML)_ , pages 957–966.
  * Matthews (1975) B. W. Matthews. 1975.  Comparison of the predicted and observed secondary structure of t4 phage lysozyme.  _Biochimica et Biophysica Acta (BBA) - Protein Structure_ , 2(405):442––451.
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013.  Distributed representations of words and phrases and their compositionality.  In _Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2_ , NIPS’13, pages 3111–3119, USA. Curran Associates Inc.
  * Peldszus and Stede (2015) Andreas Peldszus and Manfred Stede. 2015.  An annotated corpus of argumentative microtexts.  In _Proceedings of the First European Conference on Argumentation_.
  * Rajendran et al. (2016) P. Rajendran, B. Bollegala, and S. Parsons. 2016.  Contextual stance classification of opinions: A step towards enthymeme reconstruction in online reviews.  In _Proceedings of the 3rd Workshop on Argument Mining_.
  * Razuvayevskaya and Teufel (2016) O. Razuvayevskaya and S. Teufel. 2016.  Recognising enthymemes in real-world texts: a feasibility study.  In _Workshop on Foundations of the Language of Argumentation (in conjunction with COMMA)_.
  * Speer and Havasi (2012) R. Speer and C. Havasi. 2012.  Representing General Relational Knowledge in ConceptNet.  In _Proceedings of LREC_.


# General formula to solve quintic equation

Rodrigo José Martinelli Biglia Andrade
Administration Department
Methodist University of Piracicaba
Piracicaba, SP, Brazil
<EMAIL_ADDRESS>

###### Abstract

There are many papers about the proof of Abel-Ruffini theorem, but, in this
paper, we will show a way to solve any quintic equation by radicals which will
be a outstandig result because of work the mathematicians Abel and Ruffini who
showed that there is no formula to quintic equation. We need to mention the
mathematician Évariste Galois that also showed the same conclusion of Abel and
Ruffini using permutations,group theory etc. However, in this article we will
present a method to split any quintic equation into two equation (one of
degree 3 and another of degree 2) where both equations can be solved by
radicais using the quadratic and the cubic formula.

##  1 Introduction

This paper contributes to a new way to solve quintic equation using a
polynomial (Martinelli’s polynomial) that can be proved using some simple
steps. Since the 1500’s when the cubic and quartic formula was discovered the
world waited centuries for the next step: to find a method or general formula
to solve the quintic equation. Although Abel and Ruffini showed the
impossibility of a closed formula to solve general quintic equation the search
for a formula to solve quintic equation ends. But the mathematician Joseph-
Louis Lagrange proved the inversion theorem that could solve specific cases of
the quintic equation and higher degree. However using hypergeometric function
will be possible to solve any quintic equation if reducing the general quintic
equation to the Bring-Jerrard form (but it is a very complex process to
transform the general quintic equation to that form). At the end of this paper
there is an example that checks if the method that will be presented works.
Finally, to end the abstract we will not proof or talk about the Lagrange
inversion theorem and Bring-Jerrard form to get more understanding this paper.

##  2 About Galois theory and Abel-Ruffini theorem

We will see some concepts about Galois’ theory and Abel-Ruffini’s theorem. The
theorem, in a succinct way, consists of the proof that there is no "closed"
formula for all equations of degree greater or equal to 5. That is, there is
no way to algebraically arrive at a formula for those equations greater or
equal to 5. As Zoladek (2000) reported, "A general algebraic equation of
degree $\geq$ 5 cannot be solved in radicals. This means that there does not
exist any formula which would express the roots of such equation as functions
of the coefficients by means of the algebraic operations and roots of natural
degrees." (p. 254).

Thus, Galois theory comes to confirm, through the study of the relationship of
the roots that it is impossible to solve, algebraically, equations of degree
equal to or greater than 5. In its most basic form, the theorem states that
given a E / F field extension which is finite and Galois, there is a one-to-
one correspondence between its intermediate fields and subgroups of its Galois
group. (Intermediate fields are K fields that satisfy $F\subseteq K\subseteq
E$; they are also called sub-extensions of E / F.).

So, according to Abel-Ruffini’s theorem and Galois theory, there are cases
where equations of degree 5 or higher are solvable by radicals or
algebraically.

##  3 Proof of Martinelli’s polynomial

To demonstrate the Martinelli’s Polynomial it is necessary to consider the
roots of any fifth degree equation. Each root must be associated with a single
other root. We have then that the combination of the roots of a fifth degree
equation is ten (due that the polynomial is tenth degree). Let us then
consider the following equations:

$(x^{2}-kx+n)(x^{3}+kx^{2}+kx+m)=0.$ (1) $(x^{2}-kx+n)(x^{3}+kx^{2}+lx+m)=0.$
(2)

Equation (1) have a relation with equation (2). If we expand both equations
(1) and (2), each corresponding term can be factorized. Let put those terms
into a table:

Table 1: Equation (1) expanded $x^{3}$ | $x^{2}$ | $x$ | Term Independent
---|---|---|---
$k+n-k^{2}=C_{2}$ | $-k^{2}+kn+m=D_{2}$ | $kn-km=E_{2}$ | $mn=F$
Table 2: Equation (2) expanded $x^{3}$ | $x^{2}$ | $x$ | Term Independent
---|---|---|---
$l+n-k^{2}=C$ | $nk-lk+m=D$ | $nl-km=E$ | $mn=F$

Andrade (2019) consider the follow equation to better understand the proof of
Martinelli’s Polynomial:

$x^{2}+3x+2=0$ (3)

If we plug in x the sum of the roots of equation (3) we have 2=0, that would
be absurd, but with that idea, we can create a second degree equation using
the terms $C,C_{2},D,D_{2},E$ e $E_{2}$ as shown in Tables 1 and 2 above.
Matching the equation that will be created with $(-k^{2}+n+k-C)n$ we will
have, on the right side of the equation, the same thing $E_{2}-E$, because
$E_{2}$ is the same as $kn-km$ and $-E$ is the same as $-nl+km$. The sum of
$E_{2}-E$ will result $kn-nl$ then $l=C-n+k^{2}$. So we have $kn-n(C-n+k^{2})$
that is the same as $(-k^{2}+n+k-C)n$.

To create a second degree equation where one of the solutions of the equation
will be the sum of two solutions of a fifth degree equation we must follow
this logic: We have the general form of the second degree equation that is
$ax^{2}+bx+c=0$, the coefficients of the second degree equation that will be
created will be $a=C_{2}-C$, $b=D_{2}-D$, $c=E_{2}-E$ and on the right side of
the equation we have to add $(-k^{2}+n+k-C)n$ because on the left side of the
equation will remain $E_{2}-E$.

This idea will give us the possibility to know n from equation (2). The goal
is to form a tenth degree equation with the unknown k. So $a=C_{2}-C$ and
$b=D_{2}-D$ according to tables 1 and 2, it follows that $a=k+n-k^{2}-C$,
$b=-k^{2}+kn+m-D$, $c=nk-km-E$ and the right side of the equation will be
$(-k^{2}+n+k-C)n$. Thus, making the substitutions in $ak^{2}+bk+c=0$ we will
have:

$\displaystyle(-k^{2}+n+k-C)k^{2}+(-k^{2}+nk+m-D)k+nk-km-E$
$\displaystyle=(-k^{2}+n+k-C)n.$
$\displaystyle(-k^{4}+nk^{2}+k^{3}-Ck^{2})+(-k^{3}+nk^{2}+km-Dk)+nk-km-E$
$\displaystyle=(-k^{2}+n+k-C)n.$ $\displaystyle-k^{4}+2nk^{2}-Ck^{2}-Dk+nk-E$
$\displaystyle=-nk^{2}+n^{2}+nk-nC.$ $\displaystyle-k^{4}-Ck^{2}-Dk-E$
$\displaystyle=-3nk^{2}+n^{2}-nC.$

Putting n on the left side of the equation, we have:

$n=\frac{k^{4}+Ck^{2}+Dk+E}{3k^{2}-n+C}.$ (4)

Since k is the sum of two roots of a fifth degree equation, C, D, E and F the
coefficients of a fifth degree equation and n is the product of the roots of a
second degree equation, so to arrive at Martinelli’s polynomial, we have to
replace the variable n with the use of an algebraic manipulation. This
algebraic manipulation consists of taking the equality referring to the term D
in table (2). Thus:

$nk-(k^{2}-n+C)k+\frac{F}{n}=D.$ (5)

$n^{2}=\frac{nk^{3}+Cnk-F+Dn}{2k}.$ (6)

Now just replace $n^{2}$ in equation (4) and get n:

$n=\frac{k^{4}+Ck^{2}+Dk+E}{3k^{2}-n+C}.$
$-n^{2}+3nk^{2}+Cn=k^{4}+Ck^{2}+Dk+E.$
$\frac{-nk^{3}-Cnk+F-Dn}{2k}+3nk^{2}+Cn=k^{4}+Ck^{2}+Dk+E.$
$n=\frac{2(k^{5}+Ck^{3}+Dk^{2}+Ek)-F}{5k^{3}+Ck-D}.$ (7)

If we have n, then we can create the Martinelli’s polynomial that will be very
important to solve any quintic equation

$\frac{2(k^{5}+Ck^{3}+Dk^{2}+Ek)-F}{5k^{3}+Ck-D}=\frac{k^{4}+Ck^{2}+Dk+E}{3k^{2}-\frac{2(k^{5}+Ck^{3}+Dk^{2}+Ek)-F}{5k^{3}+Ck-D}+C}.$

Arranging the equation on both sides and equaling 0 we arrive at the
Martinelli’s polynomial:

$\displaystyle{(2(k^{5}+Ck^{3}+Dk^{2}+Ek)-F)(13k^{5}+6Ck^{3}-5Dk^{2}+(-2E+C^{2})k+F-DC)}$
$-(k^{4}+Ck^{2}+Dk+E)(5k^{3}+Ck-D)^{2}=0.$ (8)

##  4 Martinelli’s Polynomial expanded

$k^{10}+3Ck^{8}+Dk^{7}+(3C^{2}-3E)k^{6}+(2DC-11F)k^{5}+(C^{3}-D^{2}-2CE)k^{4}+(DC^{2}-4DE-4CF)k^{3}$
$+(7DF-CD^{2}-4E^{2}+EC^{2})k^{2}+(4EF-FC^{2}-D^{3})k-F^{2}+FDC-D^{2}E=0.$ (9)

##  5 Solving a quintic equation as an example

Let’s begin with the quintic equation:

$x^{5}+x+3=0$ (10)

Using the Martinelli’s Polynomial (9) we get the follow polynomial:

$k^{10}-3k^{6}-33k^{5}-4k^{2}+12k-9=0$ (11)

The roots of the equation (11) are the combination of the sums of the equation
(10). So, wouldn’t be necessary to know all roots of the equation (11). But,
solving the equation (10) we will see that the sum of the complex roots give
us one of the real root: 2.0837590792241645736… that is represented using
hypergeometric function as follows:

$k=\sqrt{2}{}_{4}F_{3}{\left[\genfrac{.}{.}{0.0pt}{}{-\frac{1}{20}{\mathchar
44\relax}\mskip 8.0mu\frac{3}{20}{\mathchar 44\relax}\mskip
8.0mu\frac{7}{20}{\mathchar 44\relax}\mskip
8.0mu\frac{11}{20}}{\frac{1}{4}{\mathchar 44\relax}\mskip
8.0mu\frac{1}{2}{\mathchar 44\relax}\mskip
8.0mu\frac{3}{4}};-\frac{253125}{256}\right]}-\frac{45{}_{4}F_{3}{\left[\genfrac{.}{.}{0.0pt}{}{-\frac{9}{20}{\mathchar
44\relax}\mskip 8.0mu\frac{13}{20}{\mathchar 44\relax}\mskip
8.0mu\frac{17}{20}{\mathchar 44\relax}\mskip
8.0mu\frac{21}{20}}{\frac{3}{4}{\mathchar 44\relax}\mskip
8.0mu\frac{5}{4}{\mathchar 44\relax}\mskip
8.0mu\frac{3}{2}};-\frac{253125}{256}\right]}}{16\sqrt{2}}+\frac{3}{2}{}_{4}F_{3}{\left[\genfrac{.}{.}{0.0pt}{}{\frac{1}{5}{\mathchar
44\relax}\mskip 8.0mu\frac{2}{5}{\mathchar 44\relax}\mskip
8.0mu\frac{3}{5}{\mathchar 44\relax}\mskip
8.0mu\frac{4}{5}}{\frac{1}{2}{\mathchar 44\relax}\mskip
8.0mu\frac{3}{4}{\mathchar 44\relax}\mskip
8.0mu\frac{5}{4}};-\frac{253125}{256}\right]}$ (12)

$\Bigg{(}x^{2}-kx+\frac{2(k^{5}+k)-3)}{5k^{3}}\Bigg{)}\Bigg{(}x^{3}+kx^{2}+\Bigg{(}k^{2}-\frac{2(k^{5}+k)-3)}{5k^{3}}\Bigg{)}x+\frac{15k^{3}}{2(k^{5}+k)-3}\Bigg{)}=0$
(13)

Now, plugging the k root, represented by hypergeometric function (12), we will
have the equation (10), but, in this case, the equation (10) was factorized
into two equations of degree 2 and another of degree 3. Using the quadratic
and cubic formula we will able to solve in terms of radicals the equation (13)
which it is the same as the equation (10).

##  6 Remark

As seen the Martinelli’s polynomial provides the sum of two roots of any
quintic equation and this is very important to split a quintic equation into
two smaller degree equations. This method solves quintic equation using
quadratic and cubic formulas but in the most cases it is necessary to use the
hypergeometric function to represent the variable that splits the equation.
However, a general method has been achieved to solve any quintic equation.
But, it’s no make sense, because we need to know one of the real root of the
Martinelli’s polynomial once that is the sum of quintic roots equation. We
need to know before the roots of the quintic equation in the Bring-Jerrard
form to split the fifth degree equation and solve in terms of radicals. So,
Abel-Ruffini theorem and Galois theory didn’t give us a clear answer about
this way to solve quintic equation in terms of radicals and in the Bring-
Jerrard form. Maybe it’s a new discussion about equations theory field.

## References

  * [1]

ZOLADEK, H. The topological proof of Abel-Ruffini theorem. Topological Methods
in Nonlinear Analysis.v. 16, n.2, pp. 253-265, 2000.

  * [2]

NICKALLS, R. W. D. A new approach to solving the cubic: Cardan’s solution
revealed. The mathematical Gazette, v. 77, n. 480, pp. 354-359, 1993.

  * [3]

ANDRADE, R. J. M. B. Resolução de uma equação do quinto grau. C.Q.D - Revista
Eletrônica Paulista de Matemática, v. 16, pp. 196-205, dez. 2019. Retrieved
from https://www.fc.unesp.br/#!/departamentos/matematica/revista-cqd/.


11institutetext: Cooperative Medianet Innovation Center, Shanghai Jiao Tong
University 11email: {fengshixiang, zhouyuhang, xm99sjtu,
<EMAIL_ADDRESS>
# MS-KD: Multi-Organ Segmentation with
Multiple Binary-Labeled Datasets

Shixiang Feng  Yuhang Zhou  Xiaoman Zhang  Ya Zhang  Yanfeng Wang

###### Abstract

Annotating multiple organs in 3D medical images is time-consuming and costly.
Meanwhile, there exist many single-organ datasets with one specific organ
annotated. This paper investigates how to learn a multi-organ segmentation
model leveraging a set of binary-labeled datasets. A novel Multi-teacher
Single-student Knowledge Distillation (MS-KD) framework is proposed, where the
teacher models are pre-trained single-organ segmentation networks, and the
student model is a multi-organ segmentation network. Considering that each
teacher focuses on different organs, a region-based supervision method,
consisting of logits-wise supervision and feature-wise supervision, is
proposed. Each teacher supervises the student in two regions, the organ region
where the teacher is considered as an expert and the back-ground region where
all teachers agrees. Extensive experiments on three public single-organ
datasets and a multi-organ dataset have demonstrated the effectiveness of the
proposed MS-KD framework.

###### Keywords:

Multi-organ segmentation Teacher-student model Multiple teachers Knowledge
distillation.

##  1 Introduction

Multi-organ segmentation is an important step towards many clinical
applications such as disease diagnosis. However, due to the considerable
annotating cost for 3D medical images segmentation, most benchmark datasets
only provide segmentation mask of a single organ. To address this problem,
several recent studies propose to leverage multiple single organ datasets to
train a multi-organ segmentation model. Condition-based methods [1, 11] encode
each segmentation task as task-aware prior to guide the network to segment the
task-related organ. Several ways of conditioning the network are proposed,
such as incorporating organ class information into the intermediate activation
signal [1], or incorporating the task-aware prior to generate dynamic
convolution filters with a dynamic on-demand network (DoDNet) [11]. However,
the above condition-based methods require several rounds of inference to get
the final segmentation, which is computationally inefficient. Pseudo-label
based methods [12, 4] use a pre-trained single-organ model to generate pseudo
labels for un-annotated organs in each dataset, and then constructs a pseudo
multi-organ dataset which is used to train the multi-oragn segmentation model.
Since the quality of pseudo labels is essential, a penalty that regularizes
the organ size distribution of pseudo labels is introduced in [12], and a pair
of weight-averaged model is proposed in [4] in which each model is trained
with the outputs of the other model to get more reliable pseudo labels. Most
of the existing pseudo label based methods only utilize the binary outputs of
the multiple pre-trained single-organ models. Learning from soft pseudo labels
via consistency loss has been proved to be more effective than learning from
hard labels [13].

Figure 1: (a) Typical knowledge distillation framework (b) Pseudo label based
method (c) MS-KD: Multi-teacher Single-student Knowledge Distillation
framework.

In this paper, we attempt to explore a knowledge distillation framework for
learning to segment multiple organs combining a set of single-organ datasets.
In particular, we employ teacher-student models [3], widely used for knowledge
distillation for image classification [8] and segmentation [9] tasks, which
utilizes the soft pseudo labels or intermediate features from the teacher
model [10, 5] to train the student model. In our case, we have multiple
teacher models, each of which is a single-organ segmentation model. It should
be noted that the above setting is different from a typical teacher-student
model not only in the number of teachers, but also in that each of the teacher
networks is for a different single organ segmentation task and they jointly
teach the student to segment multiple organs (Fig 1). The classical
consistency learning used by teacher-student framework thus can not be
directly applied.

To tackle the above challenge, We propose a Multi-teacher Single-student
Knowledge Distillation (MS-KD) framework, to distillate the teacher models
into a single student model for multi-organ segmentation. A region-based
supervision is proposed to enable the student to learn each task from the
respective teacher. The student learns segmenting an organ from the respective
teacher and learn segmenting background from all the teachers, so each teacher
supervises the student in two regions, the organ region predicted by the
teacher and the background region where all teachers agree. Specifically,
logits-wise and feature-wise supervision are employed for each region. As the
logits of the teacher networks and the student network are of different
dimention, _i.e.,_ two vs. $K+1$ where $K$ is the number of organs, for
logits-wise supervision, a simple dimension transfer is applied to the logits
outputs of teacher, and the transferred outputs are used to constrain the
student. For feature-wise supervision, the distribution of the student
intermediate features is constrained according to the teachers intermediate
features. We evaluate the proposed method in four public datasets, including
three single-organ datasets for both training and test, and one multi-organ
datasets only for test. Experimental results shows that the MS-KD has the
capacity to enable student to learn from and surpass the multiple teachers.

The contributions of this paper are summarized as follows. (1) We propose a
novel Multi-Teacher Single-Student Knowledge Distillation (MS-KD) framework to
train a multi-organ segmentation network from multiple single-organ
segmentation networks. (2) Region-based supervision methods, including logits-
wise supervision and feature-wise supervision, are proposed to enable student
model to learn from multiple task-different teachers.

##  2 Methodology

Figure 2: Overview of MS-KD framework. The framework uses the union of images
from the $K$ single-organ datasets ($K=2$ here). The framework consists of $K$
pre-trained single-organ segmentation networks as teacher models, and a multi-
organ segmentation network as student model. The student is trained using
region-based logits-wise supervision and feature-wise supervision.

Given a set of single organ datasets $\\{D_{1},...,D_{K}\\}$, where the
dataset for the $k$-th organ $D_{k}$ contains a set of input images
$X^{k}=\\{x_{i}^{k}\\}_{i=1}^{N_{k}}$ and the corresponding set of binary
segmentation masks $Y^{k}=\\{y_{i}^{k}\\}_{i=1}^{N_{k}}$. The label of each
pixel is binary, _i.e.,_ 0 for background and 1 for organ-$k$. The goal is to
train a $K$-organ segmentation model with the above single organ datasets.

###  2.1 Multi-Teacher Single-Student Knowledge Distillation (MS-KD)

The overall framework of the MS-KD framework is illustrated in Fig 2,
consisting of $K$ single-organ segmentation model as the teachers and one
multi-organ segmentation model as the student.

The $K$ single-organ segmentation teacher networks
$\\{f_{T_{1}},f_{T_{2}},...,f_{T_{K}}\\}$ are trained on the corresponding
single organ datasets, each with the loss function

$\min_{\theta_{k}}\sum_{i=1}^{N_{k}}\mathcal{L}(f_{k}(x_{i}^{k};\theta_{k}),y_{i}^{k}),$
(1)

where $\theta_{k}$ denotes the network parameters of teacher-$k$ and the loss
function $\mathcal{L}$ is the combination of dice loss and cross-entropy loss.
The teachers are frozen when training the student. The student has the same
architecture as the teachers, except for the dimension of outputs (2 vs.
$K+1$). Different from existing Teacher-student models, not only the proposed
framework has more than one teachers, but also the task of student is
different from the task of any teacher, which means the classical consistency
learning method are not directly applicable.

###  2.2 Region-based Supervision

Here each teacher model is specialized in segmenting one individual organ. For
an image $x$, denote $M^{k}(x)$ as its binary predictions from the
teacher-$k$:

$M^{k}(x_{i})=\left\\{\begin{aligned} &1,\text{pixel $i$ with organ-k
predictions}\\\ &0,\text{pixel $i$ with background
predictions}.\end{aligned}\right.$ (2)

As each teacher model predicts the corresponding task-irrelevant organs as
background, the background predictions of the teacher-$k$ is actually the
union of true background region and $K-1$ irrelevant organ regions. So for
each teacher, we can only trust its prediction of the corresponding organ
regions. Considering that the organs are expected to occupy mutually exclusive
regions, a region-based supervision strategy is proposed to tackle this
challenge. Before we go to the details, we first define two sets of regions.

  * •

Organ-$k$ region: the pixels $\\{x_{i}|\forall x_{i}\in x,M^{k}(x_{i})=1$}. By
supervising in this region, student learns to segment organ-$k$ from the
teacher-$k$.

  * •

True background region: The true background region is thus obtained by
intersecting the background regions of all teachers. Let
$M^{B}=(1-M^{1})\cap(1-M^{2})...\cap(1-M^{K})$. The background region is thus
the pixels $\\{x_{i}|\forall x_{i}\in x,M^{B}(x_{i})=1$}.

The set of organ-$k$ regions represent the specific regions that the
teacher-$k$ is an expert, while the true background region represents where
the collective intelligence from all teachers are located. The dentition of
the above regions enable us to limit the teacher’s influence on the student to
the regions that the teachers are more likely to be right. The student model
then learns to segment multiple organs combing supervisions from set of non-
overlapping specialized teachers.

####  2.2.1 Region-based logits-wise supervision

The dimensions of the teachers’ logits outputs of are different from that of
the student, _i.e.,_ two vs. $K+1$. To deal with such situations, we propose a
simple but effective logits dimension transferring method. Suppose $q_{c}^{k}$
is the classification probability of class $c$ of the teacher-$k$, computed by
softmax function
$q_{c}^{k}=\frac{f_{k}(x_{i}^{k};\theta_{k})_{c}}{\sum_{c}exp(f_{k}(x_{i}^{k};\theta_{k})_{c})}$,
where $c\in\\{0,1\\}$. To transfer $q^{k}\in R^{2}$ to the same dimension as
the student’s logits, we map the supervision signal from the teacher-$k$ to
$\hat{q}^{k}\in R^{K}$ as follows

$\hat{q}_{c}^{k}=\left\\{\begin{aligned} &q_{0}^{k},&\text{if}~{}c=0\\\
&q_{1}^{k},&\text{if}~{}c=k\\\
&0,&\text{if}~{}c\not\in\\{0,k\\}\end{aligned}\right.\ \ \ \forall
c\in\\{0,...,K\\}.$ (3)

In this way, the supervision signal for the organ-$k$ region is generated only
from the outputs of the teacher-$k$. The student’s logits outputs in the
organ-$k$ region is constrained with $\hat{q}_{c}^{k}$ in region $M_{i}^{k}=1$
. The logits-wise loss for the organ-$k$ is thus defined as

$L_{\text{logit}}^{k}=\frac{1}{W\times
H}\sum_{i\in\mathcal{R}}KL(\hat{q}_{i}^{k},q_{i}^{S})\cdot M^{k}_{i},$ (4)

where $i$ denotes the $i$th pixel, $\mathcal{R}=\\{1,2,...,W\times H\\}$
denotes all the pixels, $q^{S}$ is the classification probability of the
student, and $KL(\cdot)$ is the Kullback-Leibler divergence. For the true
background region, the supervision signal is generated from classification
probabilities of all teachers,

$\hat{q}^{B}=(\hat{q}^{1}+\hat{q}^{2}+...+\hat{q}^{K})/K.$ (5)

The logits-wise loss for background region $M_{i}^{B}=1$ can be formulated as

$L_{\text{logit}}^{B}=\frac{1}{W\times
H}\sum_{i\in\mathcal{R}}KL(\hat{q}_{i}^{B},q_{i}^{S})\cdot M^{B}_{i}.$ (6)

####  2.2.2 Region-based feature-wise supervision

For region-based supervision in each intermediate layer, we denote $M^{k,l}$
as the binary mask for intermediate layer of teacher-$k$, generated by down-
sampling $M^{k}$ for $l$ times. We hypothesis that in organ-$k$ region
($M^{k,l}=1)$ of features, features distribution of teacher-$k$ and that of
student should be similar. Since the teachers are trained separately, the
permutations of features are different within these teachers, thus we can not
directly constrain features between teachers and student. We sort the features
for each pixel along the channel dimension and then supervise in the organ
regions only. For the layer corresponding to $M^{k,l}$, the feature-wise loss
is computed as,

$L_{\text{feature}}^{k,l}=\frac{1}{(W/2^{l})\times(H/2^{l})}\sum_{i\in\mathcal{R}^{l}}KL(\text{sort}(F^{k,l}_{i}),\text{sort}(F^{S,l}_{i}))\cdot
M^{k,l}_{i},$ (7)

where $F^{k,l}$ and $F^{S,l}$ are the features after softmax of the
teacher-$k$ and the student, respectively, and
$\mathcal{R}^{l}=\\{1,2,...,(W/2^{l})\times(H/2^{l})\\}$.

####  2.2.3 Overall segmentation loss

The total loss is formulated as follows,

$L=\sum_{k=1}^{K}L_{\text{logit}}^{k}+\lambda_{1}L_{\text{logit}}^{B}+\lambda_{2}\sum_{k=1}^{K}L_{\text{feature}}^{k,l},$
(8)

where $\lambda_{1}$ and $\lambda_{2}$ are the respective weights of the loss.

##  3 Experiments

###  3.1 Datasets and impelmentation details

To evaluate the proposed framework, our work utilizes three single-organ
datasets, MSD-Spleen [7] with spleen annotations, KiTS [2] with kidney
annotations, NIH-Pancreas [6] with pancreas annotations, and a multi-organ
dataset, BTCV. BTCV is a multi-organ dataset with 30 scans. It provides
segmentation masks for all abdominal organs except the duodenum. All single-
organ datasets are divided into training and test sets with 4:1 ratio and the
BTCV dataset is used only for test. We use Dice-Score-Coefficient (DSC) and
Hausdorff Distance (HD) as the evaluation metrics.

For data preprocessing, we truncted the HU values in each scan to the range
$[-325,325]$ to have a better contrast on the abdominal organs and linearly
normalized to $[-1,+1]$. We choose 2D-UNet as our segmentation backbone and
input patch size is $512\times 512$. During training, we use batch size 4 and
train 250 iterations per epoch. The maximum epoch is 1000. The proportion of
patches that contain foreground in each batch is set to be 33%. Adam is used
for optimizer and the initial learning rate of the network is 3e-4. When the
loss reduction is less than 1e-3, the learning rate decays by 20%. We
empirically choose the features from decoder and $l=1$, and the hyper-
parameter $\lambda_{1}$ is 1, $\lambda_{2}$ is 10. To ensure a fair
comparison, the same training strategies are applied to all competing methods.

###  3.2 Ablation study

Table 1: Performance comparison between MS-KD and competing methods in single-organ datasets. The best result for each column is marked in bold. | DSC(%) | HD(mm)
---|---|---
Method | Spleen | Kidney | Pancreas | Avg | Spleen | Kidney | Pancreas | Avg
Individual | 95.86 | 96.06 | 78.99 | 90.30 | 9.90 | 14.39 | 18.43 | 14.24
LW | 95.97 | 96.55 | 80.76 | 91.10 | 9.86 | 12.42 | 17.12 | 13.13
MS-KD (LW+FW) | 96.16 | 96.21 | 81.59 | 91.32 | 8.81 | 13.43 | 16.85 | 13.03
Co-training [4] | 96.11 | 95.81 | 80.76 | 90.89 | 10.57 | 13.09 | 18.33 | 14.00
DoDNet [11] | 96.00 | 96.04 | 79.11 | 90.42 | 9.84 | 13.07 | 19.44 | 14.12

We first train three single-organ segmentation models separately for each
organ, denoted as “Individual” in Table 1. It achieves $95.86\%$, $96.06\%$,
$78.99\%$ DSC for spleen, kidney, and pancreas, respectively, and an average
DSC of 90.30%. We then use the individual models as teachers to train the
student model. After applying the region-based logits-wise supervision,
denoted as “LW”, the MS-KD framework gets a remarkable improvement of $0.80\%$
in terms of average DSC ($91.10\%$ vs $90.30\%$). Specifically, the average
performance improvement is mainly obtained by the more challenging organ,
pancreas ($80.76\%$ vs $78.99\%$). And the other two organs get slightly
better performance compared to individual model, which demonstrates the
effectiveness of the region-based logits-wise supervision to enable student
model to learn from all the teachers. The region-based feature-wise
supervision, denoted as “FW”, further boosts the performance of MS-KD
framework. The average DSC increases by $0.22\%$ ($91.32\%$ vs $91.10\%$). We
also conduct experiments on BTCV dataset to evaluate the generalization
ability of MS-KD framework, shown in Table 2. The model is trained on single-
organ datasets and test on BTCV dataset. MS-KD gets a remarkable improvement
1.32% for average DSC compared to individual models. It demonstrates that
training with union of binary-labeled datasets can obtain much better
performance on generalization.

Table 2: Performance comparison between MS-KD and competing methods in BTCV dataset. The best result for each column is marked in bold. | DSC(%) | HD(mm)
---|---|---
Method | Spleen | Kidney | Pancreas | Avg | Spleen | Kidney | Pancreas | Avg
Individual | 91.90 | 88.11 | 70.51 | 83.51 | 10.66 | 20.85 | 22.43 | 17.98
LW | 92.29 | 88.78 | 72.64 | 84.57 | 10.05 | 17.87 | 19.20 | 15.71
MS-KD (LW+FW) | 92.43 | 88.77 | 73.29 | 84.83 | 9.61 | 17.52 | 19.32 | 15.48
Co-training [4] | 92.10 | 88.57 | 72.53 | 84.40 | 10.29 | 18.58 | 19.30 | 16.06
DoDNet [11] | 91.93 | 88.51 | 71.67 | 84.03 | 10.61 | 19.11 | 21.72 | 17.14
Figure 3: Ground truth and uncertainty region of single-organ teacher. Darker
color means the teacher is more uncertain in the region.

###  3.3 Comparison with state-of-the-art methods

We also compare the proposed framework with two recently-developed partially-
supervised segmentation networks. The Co-training refers to the work by Huang
et al. [4] which collaboratively trains a pair of networks and let the two
networks generate pseudo labels to teach each other. The DoDNet refers to the
work by Zhang et al. [11] which generates dynamic head conditioned on both
task and input image. It shows that (1) Co-training achieves better
performance than individual networks, which demonstrates that using more
partially labeled training data can increase the segmentation performance; (2)
pseudo-label based method performs better than condition-based method. We
suspect that it is because the former utilized the unlabeled organs in other
datasets for training via generated pseudo labels while the latter not. (3)
MS-KD outperforms these two methods by a considerate gain 0.43% (91.32% vs
90.89%). As shown in Fig 3, the most uncertain region is the edge of the
organ. Using smooth supervision signal produced by logits outputs of teachers
other than using binary pseudo labels, can better utilize the pre-trained
models. In addition, it should be noticed that the Co-training method needs to
train a pair of networks simultaneously, which means its parameters number is
nearly twice as much as ours, and the DoDNet needs to generate segmentation
head dynamically and inference $K$ times to get the final segmentation
results. The proposed MS-KD framework gets better performance without any
additional computation cost for both training and inference. To make a
qualitative comparison on all the three organs, we visualized the segmentation
results obtained by four methods on BTCV datasets in Fig 4.

Figure 4: Visualization of segmentation results obtained by different methods.
The organs are annotated in color: red for spleen, green for kidney, blue for
pancreas. The DSC for each slice is shown in parenthesis.

##  4 Conclusion

We propose Multiple-Teacher Single-Student Knowledge Distillation (MS-KD)
framework for multi-organ segmentation with several single-organ datasets.
Teacher models are single-organ segmentation models pre-trained with single-
organ datasets, respectively. To enable the student learns from multiple task-
different teachers, the novel region-based logits-wise supervision and
feature-wise supervision methods are developed. We demonstrate the
effectiveness of our framework in four public datasets and surpass the
recently-developed methods.

## References

  * [1] Dmitriev, K., Kaufman, A.E.: Learning multi-class segmentations from single-class datasets. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 9501–9511 (2019)
  * [2] Heller, N., Sathianathen, N., Kalapara, A., Walczak, E., Moore, K., Kaluzniak, H., Rosenberg, J., Blake, P., Rengel, Z., Oestreich, M., et al.: The kits19 challenge data: 300 kidney tumor cases with clinical context, ct semantic segmentations, and surgical outcomes. arXiv preprint arXiv:1904.00445 (2019)
  * [3] Hinton, G., Vinyals, O., Dean, J.: Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531 (2015)
  * [4] Huang, R., Zheng, Y., Hu, Z., Zhang, S., Li, H.: Multi-organ segmentation via co-training weight-averaged models from few-organ datasets. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 146–155. Springer (2020)
  * [5] Liu, Y., Chen, K., Liu, C., Qin, Z., Luo, Z., Wang, J.: Structured knowledge distillation for semantic segmentation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 2604–2613 (2019)
  * [6] Roth, H.R., Farag, A., Turkbey, E.B., Lu, L., Liu, J., Summers, R.M.: Data from pancreas-ct. The cancer imaging archive (2016)
  * [7] Simpson, A.L., Antonelli, M., Bakas, S., Bilello, M., Farahani, K., Van Ginneken, B., Kopp-Schneider, A., Landman, B.A., Litjens, G., Menze, B., et al.: A large annotated medical image dataset for the development and evaluation of segmentation algorithms. arXiv preprint arXiv:1902.09063 (2019)
  * [8] Urban, G., Geras, K.J., Kahou, S.E., Wang, O.A.S., Caruana, R., Mohamed, A., Philipose, M., Richardson, M.: Do deep convolutional nets really need to be deep (or even convolutional)? (2016)
  * [9] Xie, J., Shuai, B., Hu, J.F., Lin, J., Zheng, W.S.: Improving fast segmentation with teacher-student learning. arXiv preprint arXiv:1810.08476 (2018)
  * [10] Zagoruyko, S., Komodakis, N.: Paying more attention to attention: Improving the performance of convolutional neural networks via attention transfer. arXiv preprint arXiv:1612.03928 (2016)
  * [11] Zhang, J., Xie, Y., Xia, Y., Shen, C.: Dodnet: Learning to segment multi-organ and tumors from multiple partially labeled datasets. arXiv preprint arXiv:2011.10217 (2020)
  * [12] Zhou, Y., Li, Z., Bai, S., Wang, C., Chen, X., Han, M., Fishman, E., Yuille, A.L.: Prior-aware neural network for partially-supervised multi-organ segmentation. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 10672–10681 (2019)
  * [13] Zou, Y., Zhang, Z., Zhang, H., Li, C.L., Bian, X., Huang, J.B., Pfister, T.: Pseudoseg: Designing pseudo labels for semantic segmentation (2020)


# IMAP: Individual huMAn mobility Patterns visualizing platform

Yisheng Alison Zheng  The University of SydneySydney Australia
<EMAIL_ADDRESS>0000-0003-1192-6434 ,  Amani Abusafia  The
University of SydneySydney Australia<EMAIL_ADDRESS>0000-0001-9159-6214 ,  Abdallah Lakhdari  The University of SydneySydney
Australia<EMAIL_ADDRESS>0000-0001-8005-1534 ,  Shing Tai
Tony Lui  The University of SydneySydney Australia<EMAIL_ADDRESS>0000-0001-9698-4697 and  Athman Bouguettaya  The University of SydneySydney
Australia<EMAIL_ADDRESS>0000-0003-1254-8092

(2022)

###### Abstract.

Understanding human mobility is essential for the development of smart cities
and social behavior research. Human mobility models may be used in numerous
applications, including pandemic control, urban planning, and traffic
management. The existing models’ accuracy in predicting users’ mobility
patterns is less than 25%. The low accuracy may be justified by the flexible
nature of human movement. Indeed, humans are not rigid in their daily
movement. In addition, the rigid mobility models may result in missing the
hidden regularities in users’ records. Thus, we propose a novel perspective to
study and analyze human mobility patterns and capture their flexibility.
Typically, the mobility patterns are represented by a sequence of locations.
We propose to define the mobility patterns by abstracting these locations into
a set of places. Labeling these locations will allow us to detect close-to-
reality hidden patterns. We present IMAP, an Individual huMAn mobility
Patterns visualizing platform. Our platform enables users to visualize a graph
of the places they visited based on their history records. In addition, our
platform displays the most frequent mobility patterns computed using a
modified PrefixSpan approach.

Human Mobility, Mobility Pattern, Social Networks, Flexible Pattern

††journalyear: 2022††copyright: rightsretained††conference: The 28th Annual
International Conference on Mobile Computing and Networking; October 17–21,
2022; Sydney, NSW, Australia††booktitle: The 28th Annual International
Conference on Mobile Computing and Networking (ACM MobiCom ’22), October
17–21, 2022, Sydney, NSW, Australia††price: 15.00††doi:
10.1145/3495243.3558759††isbn: 978-1-4503-9181-8/22/10††ccs: Information
systems Presentation of retrieval results††ccs: Human-centered computing
Visualization application domains††ccs: Human-centered computing Scientific
visualization††ccs: Human-centered computing Visual analytics

##  1\. Introduction

Human Mobility patterns refers to the sequences of frequently visited
locations by a user (gonzalez2008understanding, ). Detecting the mobility
patterns of individuals is essential in a wide range of applications,
including pandemic prevention (eubank2004modelling, ; wang2019urban, ), urban
planning (xia2018exploring, ; Amani2022QoE, ) crowd management
(solmaz2019toward, ; zhou2020understanding, ; lakhdari2021fairness, ), and
location-based services (karamshuk2011human, ; lakhdari2016link, ;
yao2022wireless, ). Several research studies have found that human mobility is
highly predictable (gonzalez2008understanding, ; song2010limits, ). This
predictability can be related to the regularity of our daily routines
(yang2014modeling, ; zhou2018understanding, ; lakhdari2021proactive, ).
Acquiring the human mobility patterns mainly focuses on analyzing the spatio-
temporal attributes and potential regularities hidden in individual, and
population movement trajectories (wang2019urban, ; solmaz2019toward, ).
Several studies proposed models to represent and predict the human mobility
patterns (haifeng2021human, ). The availability of heterogeneous location-
based data through social networks provides an unprecedented opportunity for a
more in-depth exploration of human mobility patterns from a quantitative and
microscopic perspective (wang2019urban, ).

Detecting individuals’ mobility patterns requires mining their history of
visited places. A mainstream of approaches that detect users’ mobility
patterns focus on using deep learning techniques to predict users’ next
possible location (luca2021survey, ; haifeng2021human, ). However, these
approaches’ accuracy is usually low and ranges between 8 - 25%. Indeed,
detecting a rigid mobility pattern for a user is not feasible due to the
flexible nature of the human movement (gonzalez2008understanding, ;
wang2019urban, ; song2010limits, ). Indeed, humans don’t have rigid behavior
in their daily movements. For example, let us assume a user has daily lunch
between 12:00 and 13:00 and enjoys Thai cuisine. However, they may go to a
different Thai restaurant every day, e.g., Caysorn Thai restaurant on the
first day, Seasoning Thai restaurant on the second day, and a Thai Pothong
restaurant on the third day. Even though this user eats out regularly, it is
challenging to detect that pattern since these venues have different
locations. Therefore, we propose to label these locations by their place type
to define the users’ mobility patterns accurately. For instance, given the
previous example, if we label the three Thai restaurants as ”Thai restaurant”.
A close-to-reality hidden pattern will be detected.

We propose to demonstrate the new approach of labeling users’ locations by
implementing a platform that visualizes users’ records and patterns. The
platform takes the users’ records after labeling the locations and draws a
graph of the places they visited (see Fig.2). In addition, it visualise the
detected frequent mobility patterns using a modified PrefixSpan algorithm
(pei2004mining, ).

##  2\. Overview

Our platform allows users to visualize an individual user’s mobility graph and
patterns. Users may select the default dataset or upload their history of
check-in places using a social network platform, e.g., Foursquare. In this
demo, we used the Foursquare dataset as our default dataset (yang2014modeling,
). The Foursquare dataset is a geo-tagged social media (GTSM) dataset where
users check in to venues they have visited. We used the New York dataset,
which has 227,428 check-in records. The platform involves three main steps
(see Fig.1):

Figure 1. System overview Figure 2. Example of a user mobility graph and
patterns using IMAP

  1. (1)

Update user records: The user records of visited places will be relabeled by
the name of the places. For instance, all Thai restaurants will be labeled as
”Thai restaurant”. The labeling rules can be decided by domain experts based
on the purpose of the pattern mining.

  2. (2)

Detect mobility patterns: After updating the users’ rec-ords, a modified
PrefixSpan algorithm is used to detect the frequent mobility patterns of the
user (pei2004mining, ).

  3. (3)

Visualize the mobility graph and patterns: In this step, we visualize the user
mobility graph and patterns using their relabelled records and mobility
patterns (see Fig.2). The thickness of the edges represents the frequency of
the pattern between two nodes. In Addition, the size of the nodes represents
the times a place has been visited.

##  3\. Demo Setup

Our demonstration will exhibit the IMAP web application features.
Additionally, we will display a recorded video of the entire process of using
the platform to present and interact with one of the default user’s users
records in real-time. The video can be found at this link:
https://youtu.be/94bHbmBLXTs. To demonstrate the efficiency of our platform,
we will also run our framework using the Foursquare public dataset on a laptop
(yang2014modeling, ). Visitors of our booth can choose from a list of
available users to visualize their network and their mobility patterns. They
can also interact with the network by visualizing statistics about the
displayed mobility patterns. If any of the audience is willing to share their
history, we may upload it to the platform and visualize their patterns.

## Acknowledgment

This research was partly made possible by LE220100078 and LE180100158 grants
from the Australian Research Council. The statements made herein are solely
the responsibility of the authors.

## References

  * [1] Marta C Gonzalez, Cesar A Hidalgo, and Albert-Laszlo Barabasi.  Understanding individual human mobility patterns.  nature, 453(7196):779–782, 2008.
  * [2] Stephen Eubank, Hasan Guclu, VS Anil Kumar, Madhav V Marathe, Aravind Srinivasan, Zoltan Toroczkai, and Nan Wang.  Modelling disease outbreaks in realistic urban social networks.  Nature, 429(6988):180–184, 2004.
  * [3] Jinzhong Wang, Xiangjie Kong, Feng Xia, and Lijun Sun.  Urban human mobility: Data-driven modeling and prediction.  Acm Sigkdd Explorations Newsletter, 21(1):1–19, 2019.
  * [4] Feng Xia, Jinzhong Wang, Xiangjie Kong, Zhibo Wang, Jianxin Li, and Chengfei Liu.  Exploring human mobility patterns in urban scenarios: A trajectory data perspective.  IEEE Communications Magazine, 56(3):142–149, 2018.
  * [5] Amani Abusafia and et al.  Quality of experience optimization in iot energy services.  In 2022 IEEE International Conference on Web Services (ICWS). IEEE, 2022.
  * [6] Gurkan Solmaz, Fang-Jing Wu, Flavio Cirillo, Erno Kovacs, Juan Ramon Santana, Luis Sánchez, Pablo Sotres, and Luis Munoz.  Toward understanding crowd mobility in smart cities through the internet of things.  IEEE Communications Magazine, 57(4):40–46, 2019.
  * [7] Yuren Zhou, Billy Pik Lik Lau, Zann Koh, Chau Yuen, and Benny Kai Kiat Ng.  Understanding crowd behaviors in a social event by passive wifi sensing and data mining.  IEEE Internet of Things Journal, 7(5):4442–4454, 2020.
  * [8] Abdallah Lakhdari and Athman Bouguettaya.  Fairness-aware crowdsourcing of iot energy services.  In International Conference on Service-Oriented Computing, pages 351–367. Springer, 2021.
  * [9] Dmytro Karamshuk, Chiara Boldrini, Marco Conti, and Andrea Passarella.  Human mobility models for opportunistic networks.  IEEE Communications Magazine, 49(12):157–165, 2011.
  * [10] Abdallah Lakhdari and et al.  A link strength based label propagation algorithm for community detection.  In 2016 IEEE International Conferences on Big Data and Cloud Computing (BDCloud), Social Computing and Networking (SocialCom), Sustainable Computing and Communications (SustainCom)(BDCloud-SocialCom-SustainCom), pages 362–369. IEEE, 2016.
  * [11] Jessica Yao and et al.  Wireless iot energy sharing platform.  In 2022 IEEE International Conference on Pervasive Computing and Communications Workshops and other Affiliated Events (PerCom Workshops), pages 118–120. IEEE, 2022.
  * [12] Chaoming Song, Zehui Qu, Nicholas Blumm, and Albert-László Barabási.  Limits of predictability in human mobility.  Science, 327(5968):1018–1021, 2010.
  * [13] Dingqi Yang, Daqing Zhang, Vincent W Zheng, and Zhiyong Yu.  Modeling user activity preference by leveraging user spatial temporal characteristics in lbsns.  IEEE Transactions on Systems, Man, and Cybernetics: Systems, 45(1):129–142, 2014.
  * [14] Yuren Zhou, Billy Pik Lik Lau, Chau Yuen, Bige Tunçer, and Erik Wilhelm.  Understanding urban human mobility through crowdsensed data.  IEEE Communications Magazine, 56(11):52–59, 2018.
  * [15] Abdallah Lakhdari and Athman Bouguettaya.  Proactive composition of mobile iot energy services.  In 2021 IEEE International Conference on Web Services (ICWS), pages 192–197. IEEE, 2021.
  * [16] Zheng Haifeng, Yan Yajie, and Zhang Ningbo.  Human mobility prediction based on dbscan and rnn.  In 2021 IEEE 4th International Conference on Computer and Communication Engineering Technology (CCET), pages 146–152. IEEE, 2021.
  * [17] Massimiliano Luca, Gianni Barlacchi, Bruno Lepri, and Luca Pappalardo.  A survey on deep learning for human mobility.  ACM Computing Surveys (CSUR), 55(1):1–44, 2021.
  * [18] Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Jianyong Wang, Helen Pinto, Qiming Chen, Umeshwar Dayal, and Mei-Chun Hsu.  Mining sequential patterns by pattern-growth: The prefixspan approach.  IEEE Transactions on knowledge and data engineering, 16(11):1424–1440, 2004.