# Resource Augmentation Analysis of the Greedy Algorithm for the Online
Transportation Problem

Stephen Arndt Computer Science Department, University of Pittsburgh,
Pittsburgh PA, 15260<EMAIL_ADDRESS>Josh Ascher Computer Science Department,
University of Pittsburgh, Pittsburgh PA, 15260<EMAIL_ADDRESS>Kirk Pruhs
Computer Science Department, University of Pittsburgh, Pittsburgh PA, 15260.
<EMAIL_ADDRESS>
Supported in part by NSF grants CCF-1907673, CCF-2036077, CCF-2209654 and an
IBM Faculty Award.

###### Abstract

We consider the online transportation problem set in a metric space containing
parking garages of various capacities. Cars arrive over time, and must be
assigned to an unfull parking garage upon their arrival. The objective is to
minimize the aggregate distance that cars have to travel to their assigned
parking garage. We show that the natural greedy algorithm, augmented with
garages of $k\geq 3$ times the capacity, is
$\left(1+\frac{2}{k-2}\right)$-competitive.

KEYWORDS
Online Algorithms, Weighted Bipartite Matching, Competitive Analysis

##  1 Introduction

We consider the natural online version of the classical transportation problem
[1, 2]. The setting is a metric space $\mathcal{M}$ that contains a collection
$S=\\{s_{1},s_{2},\dots,s_{m}\\}$ of server sites at various locations in
$\mathcal{M}$. Each server site $s_{j}$ has a positive integer capacity
$a_{j}$. Conceptually think of each server site $s_{j}$ as a parking garage
with $a_{j}$ parking spaces. Over time, a sequence of requests
$R=\\{r_{1},r_{2},\dots,r_{n}\\}$ arrive at various locations in the metric
space. Think of the requests as cars that are looking for a space to park.
Upon the arrival of each request $r_{i}$ the online algorithm $\mathcal{A}$
must assign $r_{i}$ to an unfull server site $s_{\sigma(i)}$, that is one
where the number of previous requests assigned to $s_{\sigma(i)}$ is less than
$a_{\sigma(i)}$. The cost incurred by such an assignment is the distance
$d(s_{\sigma(i)},r_{i})$ between the location of $s_{\sigma(i)}$ and the
location where $r_{i}$ arrived in $\mathcal{M}$. The objective is to minimize
$\sum_{i=1}^{n}d(s_{\sigma(i)},r_{i})$, the total cost to service the
requests. So in our parking application, the objective would be to minimize
the aggregate distance that the cars have to travel to reach their assigned
parking space. In this setting, one standard performance metric of an online
algorithm is the competitive ratio. An online algorithm $\mathcal{A}$ is
$c$-competitive if for all instances $I$ it is the case that
$\mathcal{A}(I)\leq c\cdot\mathrm{OPT}(I)$, where $\mathcal{A}(I)$ is the
objective value attained by the online algorithm $\mathcal{A}$ on instance $I$
and $\mathrm{OPT}(I)$ is the optimal objective value for instance $I$.

###  1.1 The Essential Story So Far

An important special case of the online transportation problem is the online
metrical matching problem, which is when each $a_{i}=1$. In [3, 4] it was
shown that the optimal competitive ratio for online metrical matching is
$(2n-1)$-competitive. For online metrical matching the best known competitive
ratio for a randomized algorithm against an oblivious adversary is
$O(\log^{2}n)$ [5, 6], which is obtained by an algorithm that uses a greedy
algorithm on the embedding of the metric space into a hierarchically separated
tree (HST), and the best known lower bound for the competitiveness of a
randomized algorithm against an oblivious adversary is $\Omega(\log n)$. Thus
for online transportation no deterministic algorithm can be better than $2n-1$
competitive, and no randomized algorithm can be $o(\log n)$-competitive.

The most natural algorithm for the online transportation problem is the greedy
algorithm $\mathrm{GREEDY}$ that assigns each request to the nearest unfull
server site. So understanding the performance of $\mathrm{GREEDY}$, when it
performs well and when it performs poorly, is of some interest. In [3] it was
shown that the competitive ratio of $\mathrm{GREEDY}$ is $2^{n}-1$, even for
online metrical matching in a line metric.

One way to get around this strong worst-case lower bound for $\mathrm{GREEDY}$
is to use resource augmentation analysis. In this setting, this means assuming
that for the online algorithm the capacity $c_{j}$ of each server site $s_{j}$
is $c_{j}=k\cdot a_{j}$, where $k$ is an integer strictly greater than one,
while still assuming that in the benchmark optimal matching the capacity of
the garage is $a_{j}$. [7] showed that for all instances $I$,

$\mathrm{GREEDY}_{2}(I)\leq O\left(\min(n,\log C)\cdot\mathrm{OPT}(I)\right)$

where $\mathrm{GREEDY}_{2}(I)$ is the objective value for $\mathrm{GREEDY}$
assuming that each server site $s_{j}$ has capacity $c_{j}=2a_{j}$, and
$C=\sum_{j=1}^{n}c_{j}$ is the aggregate server capacity. Further [7] showed
how to modify the greedy algorithm, by artificially increasing the distances
to garages that are more than half full by a constant multiplicative factor,
to obtain an algorithm M$\mathrm{GREEDY}$, and showed that

$\mathrm{M}\mathrm{GREEDY}_{2}(I)\leq O\left(\mathrm{OPT}(I)\right)$

That is, this modified greedy has a constant competitive ratio if the capacity
of its server sites is doubled. [8] shows how to obtain an
$O(\log^{3}n)$-competitive randomized algorithm using HST’s and resource
augmentation of an additional one server per site.

Another way to get around the strong worst-case lower bound for
$\mathrm{GREEDY}$ is to use average-case analysis. [9] analyzes the average-
case performance of $\mathrm{GREEDY}$ for online metrical matching in several
natural metric spaces. For example [9] shows that if the locations of the
requests and servers are uniformly and independently drawn from a Euclidean
circle then in the limit as $n$ grows,

$E[\mathrm{GREEDY}(I)]\leq 2.3\sqrt{n}\cdot E[\mathrm{OPT}(I)]$

As best as we can tell there are not results in the literature on average-case
analysis of $\mathrm{GREEDY}$ for online metric matching or transportation in
a general metric.

There are a significant number of papers that contain (both average-case and
worst-case) results for online metrical matching and online transportation in
metrics of special interest, most notably a line metric. As our interests lie
with general metric spaces, we will not survey these results here.

###  1.2 Our Results

Our main contribution is to extend the results in [7] to show that the
algorithm $\mathrm{GREEDY}$ is constant competitive with resource augmentation
$k\geq 3$. More specifically we show that

######  Theorem 1.1.

For $k\geq 3$,
$\mathrm{GREEDY}_{k}(I)\leq\left(1+\frac{2}{k-2}\right)\mathrm{OPT}(I)$.

Further we show that this bound is essentially tight by giving an instance
where this lower bound is obtained in the limit. So one possible
interpretation of this result is that $\mathrm{GREEDY}$ should perform
reasonably well (have bounded relative error) on instances where tripling the
capacity of the garages wouldn’t change the optimal cost by more than a
constant factor (so intuitively the load on the parking system is not too
high). It wouldn’t be totally unreasonable to argue that this result provides
a more convincing explanation of when $\mathrm{GREEDY}$ should perform
reasonably, and why it performs reasonably in these instances, than do prior
results. For example, this result guarantees bounded competitiveness, and even
competitiveness approaching one as the resource augmentation increases. In
fairness, let us acknowledge the best counterargument, which is probably that
a factor of three resource augmentation is significant.

Not surprisingly, our proof of Theorem 1.1 builds on the foundation
established in [7]. However, it is important to note that if one naively
applies the analysis of $\mathrm{GREEDY}$ in [7] with $k\geq 3$ (instead of
$k=2$), then one just obtains $\log_{k}C$ competitiveness (instead of the
original $\log_{2}C$ competitiveness result). Thus we had to develop a new
method to bound certain costs for the $\mathrm{GREEDY}$ algorithm. The main
technical innovation was the introduction of what we call the the weighted
tree cost. Informally, the weighted tree cost bounds certain costs for the
$\mathrm{GREEDY}$ algorithm by a particular weighted sum of the cost of
certain edges in the optimal solution (instead of directly bounding these
costs by the entirety of the optimal cost).

##  2 Algorithm Analysis

We begin with the simplifying assumption that $c_{i}=k$ and $a_{i}=1$ for all
$1\leq i\leq n$. We assume the adversary services $r_{i}$ with $s_{i}$, and
that the online algorithm services $r_{i}$ with $s_{\sigma(i)}$. By
convention, we represent adversary edges by listing the request first (e.g.
$(r_{i},s_{i})$) and online edges by listing the server first (e.g.
$(s_{\sigma(i)},r_{i})$).

###  2.1 Defining the Response Graph and Response Trees

We start as in [7] by defining the response graph, noting that it is almost
acyclic, and then decomposing its edges into what we call response trees. An
example of a response graph and one possible decomposition into response trees
can be seen in Figure 1(a) and Figure 1(b).

######  Definition 2.1 (Response Graph).

Let $E_{\mathrm{OPT}}=\bigcup_{i=1}^{n}(r_{i},s_{i})$ be the set of all
adversary edges, $E_{ON}=\bigcup_{i=1}^{n}(s_{\sigma(i)},r_{i})$ be the set of
all online edges, and $E=E_{\mathrm{OPT}}\ \cup\ E_{ON}$. Then the response
graph is $\mathcal{G}=(S\cup R,E)$, where each edge has a weight that is the
distance in the underlying metric space $\mathcal{M}$ between the endpoints of
$e$.

(a) An Example Connected Component of the Response Graph for $k=3$.

(b) One possible tree decomposition (roots are highest node)

######  Lemma 2.2.

[7] Assume that request $r_{i}$ is in a cycle in $\mathcal{G}$. Then the
connected component of $\mathcal{G}-(s_{\sigma(i)},r_{i})$ that contains
$r_{i}$ is a tree.

######  Definition 2.3 (Tree Decomposition).

We define a tree decomposition of the response graph $\mathcal{G}$ to be a
collection of response trees where:

  * •

Each response tree $\mathcal{T}$ is a rooted tree that is rooted at some
request $r_{i}$.

  * •

Each response tree $\mathcal{T}$ is a subgraph of $\mathcal{G}$.

  * •

Every edge in $\mathcal{G}$ is either contained in a unique response tree, or
is the online edge $(s_{\sigma(i)},r_{i})$ incident to the root $r_{i}$ of
some response tree $\mathcal{T}$, but not both (so an online edge incident to
a root of a response tree is not in any response tree).

[7] then shows how to decompose the response graph into response trees, where
each response tree $\mathcal{T}$ has the following additional properties:

  * •

For each request $r_{j}\in\mathcal{T}$, $r_{j}$ has one child, namely $s_{j}$.

  * •

Each leaf in $\mathcal{T}$ is a server site $s_{j}$ with parent $r_{j}$.

  * •

Each nonleaf server site $s_{i}$ in $\mathcal{T}$ has $k$ incident online
edges in $\mathcal{T}$, which are the children of $s_{i}$ in $\mathcal{T}$.

  * •

For each request $r_{j}\in\mathcal{T}$ and for each leaf $s_{q}\in\mathcal{T}$
it is the case that the algorithm $\mathrm{GREEDY}$ had an unused server
available at $s_{q}$ when request $r_{j}$ arrived.

Intuitively, [7] accomplishes this by iteratively breaking up each connected
component $\mathcal{C}$ as follows. Let $r_{i}$ be the most recent request in
$\mathcal{C}$. First the online edge $(s_{\sigma(i)},r_{i})$ is deleted. Let
$\mathcal{C}^{\prime}$ be the resulting connected component containing $r_{i}$
(note $\mathcal{C}^{\prime}$ is a tree by Lemma 2.2). A response tree rooted
at $r_{i}$ is then created by including all vertices reachable from $r_{i}$ in
$\mathcal{C}^{\prime}$ by a path that does not contain an unfull server site
as an internal server site on the path (in this context, unfull means that at
the time of $r_{i}$, the greedy algorithm had not used all of the servers at
that server site). Or alternatively, the leaves of $\mathcal{T}$ are unfull
server sites reachable from $r_{i}$ in $\mathcal{C}^{\prime}$ without passing
through another unfull server site. The edges and request vertices of
$\mathcal{T}$ are then removed from $\mathcal{C}$. We now fix a particular
such decomposition of $\mathcal{G}$ into response trees for the rest of the
paper.

Finally, we give the following useful definitions related to response trees.

######  Definition 2.4 (Adversary Cost of $\mathcal{T}$).

For a response tree $\mathcal{T}$, let $\mathrm{OPT}(\mathcal{T})$ be defined
as the sum of the costs of all adversary edges in $\mathcal{T}$. Thus,
$\mathrm{OPT}(\mathcal{T})=\sum_{(r_{j},s_{j})\in\mathcal{T}}d(r_{j},s_{j})$.

######  Definition 2.5 (Online Cost of $\mathcal{T}$).

For a response tree $\mathcal{T}$, let $\mathrm{ON}(\mathcal{T})$ be defined
as the sum of the costs of all online edges in
$\mathcal{T}\cup\\{(s_{\sigma(i)},r_{i})\\}$. Thus,
$\mathrm{ON}(\mathcal{T})=\sum_{r_{j}\in\mathcal{T}}d(s_{\sigma(j)},r_{j})$.

######  Definition 2.6 (Leaf Distance in $\mathcal{T}$).

Let $\mathcal{T}$ be a response tree rooted at a request $r_{i}$. For all
vertices $x\in\mathcal{T}$, let $\mathcal{T}(x)$ be the subtree of
$\mathcal{T}$ rooted at $x$. Define $ld(x)$, the leaf distance of $x$, as the
minimum distance in $\mathcal{T}$ (not in $\mathcal{M}$) from $x$ to a leaf of
$\mathcal{T}(x)$. Further, define $ld(s_{\sigma(i)})$ to be
$d(s_{\sigma(i)},r_{i})+ld(r_{i})$.

######  Definition 2.7 (Weighted Tree Cost).

Let $\mathcal{T}$ be a response tree rooted at a request $r_{i}$. Let $r_{j}$
be a request in $\mathcal{T}$, with child $s_{j}$ and grandchildren
$r_{\delta(1)},\ldots r_{\delta(k)}$. We then recursively define the weighted
tree cost of $r_{j}$ to be

$\displaystyle
W(r_{j})=d(r_{j},s_{j})+\frac{2}{k}\left(\sum_{h=1}^{k}W(r_{\delta(h)})\right)$

If $s_{j}$ is a leaf, then $W(r_{j})=d(r_{j},s_{j})$.

###  2.2 Analysis of $\mathrm{GREEDY}$

In Lemma 2.8 and Lemma 2.9, we show that the Weighted Tree Cost provides a
useful upper bound on leaf distances of $\mathcal{T}$ and by extension online
edges in $\mathcal{T}$. In Lemma 2.11, we use this result to directly bound
$\mathrm{ON}(\mathcal{T})$ in terms of $\mathrm{OPT}(\mathcal{T})$. Finally,
in Lemma 2.12, we extend this bound on trees $\mathcal{T}$ to the entire
response graph $\mathcal{G}$, and finally prove the main result, Theorem 1.1.

######  Lemma 2.8.

Let $\mathcal{T}$ be an arbitrary response tree. For each request
$r_{j}\in\mathcal{T}$, $d(s_{\sigma(j)},r_{j})\leq ld(r_{j})$.

###### Proof.

Let $s_{q}$ be a leaf in the subtree of $\mathcal{T}$ rooted at $r_{j}$ that
is closest to $r_{j}$ in $\mathcal{T}$. By the triangle inequality, we know
that $d(s_{q},r_{j})\leq ld(r_{j})$. Further we know that $\mathrm{GREEDY}$
had an unused server at $s_{q}$ at the time that $r_{j}$ arrived. Thus by the
definition of $\mathrm{GREEDY}$, it must be the case that
$d(s_{\sigma(j)},r_{j})\leq d(s_{q},r_{j})$. Thus by transitivity we can
conclude that $d(s_{\sigma(j)},r_{j})\leq ld(r_{j})$. ∎

######  Lemma 2.9.

Let $\mathcal{T}$ be an arbitrary response tree. For each request
$r_{j}\in\mathcal{T}$, $ld(r_{j})\leq W(r_{j})$.

###### Proof.

We proceed by induction on the height $h$ of the induced tree
$\mathcal{T}(r_{j})$ (the subtree of $\mathcal{T}$ rooted at $r_{j}$). If
$h=1$, the induced tree contains one request, $r_{j}$, which the adversary
services using $s_{j}$. Thus, $ld(r_{j})=d(r_{j},s_{j})=W(r_{j})$.

Now suppose $h>1$. Then, $s_{j}$ has $k$ children:
$r_{b_{1}},r_{b_{2}},\dots,r_{b_{k}}$. This gives

$\displaystyle ld(r_{j})$ $\displaystyle=d(r_{j},s_{j})+\min_{p=1\dots
k}\left[d(s_{j},r_{b_{p}})+ld(r_{b_{p}})\right]$ $\displaystyle\leq
d(r_{j},s_{j})+\min_{p=1\dots k}\left[ld(r_{b_{p}})+ld(r_{b_{p}})\right]$
$\displaystyle=d(r_{j},s_{j})+2\left(\min_{p=1\dots
k}\left[ld(r_{b_{p}})\right]\right)$ $\displaystyle\leq
d(r_{j},s_{j})+2\left(\min_{p=1\dots k}\left[W(r_{b_{p}})\right]\right)$
$\displaystyle\leq
d(r_{j},s_{j})+\frac{2}{k}\left(\sum_{p=1}^{k}W(r_{b_{p}})\right)$
$\displaystyle=W(r_{j})$

The first inequality follows from Lemma 2.8. The second inequality follows
from induction. The third inequality follows from the fact that the average
has to be larger than the minimum. The last equality follows from the
definition of $W(r_{j})$. ∎

Lemma 2.9 is the main technical extension relative to [7]. In [7] the term
$ld(r_{j})$ is merely upper bounded by the optimal cost. If we used that upper
bound on $ld(r_{j})$ in our analysis, our upper bound on the competitive ratio
would not be $O(1)$.

######  Lemma 2.10.

Let $\mathcal{T}$ be an arbitrary response tree rooted at $r_{i}$ of height
$h$. Let $D_{\ell}$ be the collection of adversary edges $(r_{j},s_{j})$ in
$\mathcal{T}$ where the path from $r_{i}$ to $s_{j}$ in $\mathcal{T}$ passes
through $l$ adversary edges. Then

$\displaystyle
W(r_{i})=\sum_{\ell=1}^{h}\left(\frac{2}{k}\right)^{l-1}\sum_{(r_{j},s_{j})\in
D_{\ell}}d(r_{j},s_{j})$

###### Proof.

We prove this by induction on $h$. For $h=1$, we simply have
$W(r_{i})=d(r_{i},s_{i})$. For $h>1$, suppose $s_{i}$ has $k$ incident online
edges $(s_{i},r_{a_{1}}),(s_{i},r_{a_{2}})$, …, $(s_{i},r_{a_{k}})$. Then
$D_{2}=\\{(r_{a_{1}},s_{a_{1}}),(r_{a_{2}},s_{a_{2}}),\dots,(r_{a_{k}},s_{a_{k}})\\}$.
Further, for all $2\leq\ell\leq h$, define $D_{\ell}^{a_{1}}\subseteq
D_{\ell}$ s.t. $D_{\ell}^{a_{1}}$ contains all adversary edges in $D_{\ell}$
within the subtree $\mathcal{T}(r_{a_{1}})$. Define
$D_{\ell}^{a_{2}},D_{\ell}^{a_{3}},\dots,D_{\ell}^{a_{k}}$ similarly. Thus,
$D_{\ell}=\bigcup_{p=1}^{k}D_{\ell}^{a_{p}}$ where
$D_{\ell}^{a_{1}},D_{\ell}^{a_{2}},\dots,D_{\ell}^{a_{k}}$ are pairwise
disjoint. Then we have

$\displaystyle W(r_{i})$
$\displaystyle=d(r_{i},s_{i})+\frac{2}{k}\left(\sum_{p=1}^{k}W(r_{a_{p}})\right)$
$\displaystyle=d(r_{i},s_{i})+\frac{2}{k}\left(\sum_{p=1}^{k}\left(\sum_{l=1}^{h-1}\left(\frac{2}{k}\right)^{l-1}\sum_{(r_{j},s_{j})\in
D_{l+1}^{a_{p}}}d(r_{j},s_{j})\right)\right)$
$\displaystyle=d(r_{i},s_{i})+\frac{2}{k}\left(\sum_{l=1}^{h-1}\left(\frac{2}{k}\right)^{l-1}\left(\sum_{p=1}^{k}\sum_{(r_{j},s_{j})\in
D_{l+1}^{a_{p}}}d(r_{j},s_{j})\right)\right)$
$\displaystyle=d(r_{i},s_{i})+\frac{2}{k}\left(\sum_{l=1}^{h-1}\left(\frac{2}{k}\right)^{l-1}\sum_{(r_{j},s_{j})\in
D_{l+1}}d(r_{j},s_{j})\right)$
$\displaystyle=d(r_{i},s_{i})+\sum_{l=2}^{h}\left(\frac{2}{k}\right)^{l-1}\sum_{(r_{j},s_{j})\in
D_{\ell}}d(r_{j},s_{j})$
$\displaystyle=\sum_{l=1}^{h}\left(\frac{2}{k}\right)^{l-1}\sum_{(r_{j},s_{j})\in
D_{\ell}}d(r_{j},s_{j})$

∎

######  Lemma 2.11.

Let $\mathcal{T}$ be an arbitrary response tree. Then
$\mathrm{ON}(\mathcal{T})\leq\left(1+\frac{2}{k-2}\right)\mathrm{OPT}(\mathcal{T})$.

###### Proof.

Using Lemma 2.8 and Lemma 2.9, we can bound $\mathrm{ON}(\mathcal{T})$ as
follows:

$\mathrm{ON}(\mathcal{T})=\sum_{r_{j}\in\mathcal{T}}d(s_{\sigma(j)},r_{j})\leq\sum_{r_{j}\in\mathcal{T}}ld(r_{j})\leq\sum_{r_{j}\in\mathcal{T}}W(r_{j})$

Note by applying Lemma 2.10 one can view $\sum_{r_{j}\in\mathcal{T}}W(r_{j})$
as a linear combination of costs of adversary edges. Consider an arbitrary
adversary edge $(r_{q},s_{q})\in\mathcal{T}$. Note again by Lemma 2.10 that
$d(r_{q},s_{q})$ will be included in $W(r_{j})$ with coefficient
$\left(\frac{2}{k}\right)^{b-1}$ only when the following two conditions hold:
$r_{j}$ is an ancestor of $r_{q}$, and the simple path from $r_{j}$ to $s_{q}$
in $\mathcal{T}$ passes through $b$ adversary edges. Further, clearly an
ancestor $r_{j}$ which satisfies these conditions is unique. Thus the
coefficient associated with the cost of $(r_{q},s_{q})$ in
$\sum_{r_{j}\in\mathcal{T}}W(r_{j})$ is at most
$1+\left(\frac{2}{k}\right)+\left(\frac{2}{k}\right)^{2}+\dots=\frac{1}{1-\frac{2}{k}}=\frac{k}{k-2}=1+\frac{2}{k-2}$.
Thus, we have

$\sum_{r_{j}\in\mathcal{T}}W(r_{j})\leq\left(1+\frac{2}{k-2}\right)\sum_{(r_{q},s_{q})\in\mathcal{T}}d(r_{q},s_{q})=\left(1+\frac{2}{k-2}\right)\mathrm{OPT}(\mathcal{T})$

∎

######  Lemma 2.12.

$\mathrm{GREEDY}_{k}(I)\leq\left(1+\frac{2}{k-2}\right)\mathrm{OPT}(I)$ under
the assumption that each server site $s_{i}$ has $k\geq 3$ online servers and
one adversary server.

###### Proof.

Note that $\mathrm{GREEDY}_{k}(I)$ is equal to the total cost of the online
edges in the response graph, $\mathcal{G}$. Via our tree decomposition, this
cost is

$\mathrm{GREEDY}_{k}(I)=\sum_{\mathcal{T}\in\mathcal{G}}\mathrm{ON}(\mathcal{T})\leq\left(1+\frac{2}{k-2}\right)\sum_{\mathcal{T}\in\mathcal{G}}\mathrm{OPT}(\mathcal{T})=\left(1+\frac{2}{k-2}\right)\mathrm{OPT}(I)$

∎

###### Proof of Theorem 1.1.

Split each server site with online capacity $c_{i}=ka_{i}$ and adversary
capacity $a_{i}$ into $a_{i}$ server sites with online capacity $k$ and
adversary capacity 1. Clearly the optimal cost is the same because the
underlying server locations have not changed. Further, $\mathrm{GREEDY}_{k}$
assigns requests identically on both instances for the same reason, and so the
online cost is the same as well. Thus Lemma 2.12 directly gives the desired
result.

∎

###  2.3 Algorithm Lower Bound

Lastly, we show the competitiveness bound of $1+\frac{2}{k-2}$ for
$\mathrm{GREEDY}_{k}$ is essentially tight.

######  Theorem 2.13.

$\forall\ \epsilon>0$, there is an instance $I_{\epsilon}$ where
$\mathrm{GREEDY}_{k}(I_{\epsilon})>\left(1+\frac{2}{k-2}-\epsilon\right)\mathrm{OPT}(I_{\epsilon})$.

###### Proof.

We embed $m$ server sites on the real line. The server site $s_{1}$ is located
at the point $-1$. For $2\leq i\leq m$, the server site $s_{i}$ is located at
$2^{i-1}-1$. The online algorithm has $c_{i}=k^{m-i+1}$ servers at site
$s_{i}$, and the adversary has $a_{i}=k^{m-i}$ servers at site $s_{i}$. The
requests occur in $m$ batches. The first batch consists of $k^{m-1}$ requests
at 0. For $2\leq i\leq m$, the $i$-th batch consists of $k^{m-i}$ requests at
$s_{i}=2^{i-1}-1$. $\mathrm{GREEDY}_{k}$ responds to batch $i\ (1\leq i<m)$ by
answering each request in batch $i$ with server site $s_{i+1}$, thus depleting
$s_{i+1}$. $\mathrm{GREEDY}_{k}$ responds to batch $m$ by answering the sole
request with site $s_{1}$.

For batch 1, $\mathrm{GREEDY}_{k}$ services $k^{m-1}$ requests, each of which
requires a cost of $s_{2}-0=1$. For batch $i$, $1<i<m$, $\mathrm{GREEDY}_{k}$
services $k^{m-i}$ requests, each of which requires a cost of
$s_{i+1}-s_{i}=(2^{i}-1)-(2^{i-1}-1)=2^{i-1}$. For batch $m$,
$\mathrm{GREEDY}_{k}$ services 1 request, which requires a cost of
$s_{m}-s_{1}=(2^{m-1}-1)-(-1)=2^{m-1}$. Thus $\mathrm{GREEDY}_{k}$ incurs a
total cost of

$\displaystyle\mathrm{GREEDY}_{k}(I_{\epsilon})=k^{m-1}\cdot
1+\sum_{i=2}^{m-1}k^{m-i}\cdot 2^{i-1}+1\cdot 2^{m-1}$
$\displaystyle=\sum_{i=1}^{m}k^{m-i}\cdot 2^{i-1}$
$\displaystyle=k^{m-1}\sum_{i=1}^{m}\frac{2^{i-1}}{k^{i-1}}$
$\displaystyle=k^{m-1}\sum_{i=1}^{m}\left(\frac{2}{k}\right)^{i-1}$
$\displaystyle=k^{m-1}\left(\frac{1-\left(\frac{2}{k}\right)^{m}}{1-\frac{2}{k}}\right)$
$\displaystyle=k^{m-1}\cdot\frac{k}{k-2}\left(1-\left(\frac{2}{k}\right)^{m}\right)$
$\displaystyle=k^{m-1}\cdot\left(1+\frac{2}{k-2}\right)\left(1-\left(\frac{2}{k}\right)^{m}\right)$

The adversary could respond to the requests by servicing batch $i$ with server
site $s_{i}$. The adversary would incur a cost of $k^{m-1}$ for batch 1, and a
cost of 0 for batches $i$, $2\leq i\leq m$. Then the adversary can achieve a
total cost of $\mathrm{OPT}(I_{\epsilon})\leq k^{m-1}$. Thus, we have

$\frac{\mathrm{GREEDY}_{k}(I_{\epsilon})}{\mathrm{OPT}(I_{\epsilon})}\geq\frac{k^{m-1}\cdot\left(1+\frac{2}{k-2}\right)\left(1-\left(\frac{2}{k}\right)^{m}\right)}{k^{m-1}}=\left(1+\frac{2}{k-2}\right)\left(1-\left(\frac{2}{k}\right)^{m}\right)$

For any $\epsilon>0$, for sufficiently large $m$,
$\left(\frac{2}{k}\right)^{m}<\left(\frac{k-2}{k}\right)\epsilon$ giving

$\left(1+\frac{2}{k-2}\right)\left(1-\left(\frac{2}{k}\right)^{m}\right)>\left(1+\frac{2}{k-2}\right)\left(1-\left(\frac{k-2}{k}\right)\epsilon\right)=1+\frac{2}{k-2}-\epsilon$

Thus for sufficiently large $m$,

$\mathrm{GREEDY}_{k}(I_{\epsilon})>\left(1+\frac{2}{k-2}-\epsilon\right)\mathrm{OPT}(I_{\epsilon})$

∎

## References

  * [1] J. Kennington, R. Helgason, Algorithms for Network Programming, John Wiley and Sons, 1980.  arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.3230120107.
  * [2] E. Lawler, Combinatorial Optimization: Networks and Matroids, Sanders College Publishing, 1976.
  * [3] B. Kalyanasundaram, K. Pruhs, Online weighted matching, Journal of Algorithms 14 (3) (1993) 478–488.
  * [4] S. Khuller, S. G. Mitchell, V. V. Vazirani, On-line algorithms for weighted matching and stable marriages, Tech. rep., Cornell University (1994).
  * [5] A. Meyerson, A. Nanavati, L. Poplawski, Randomized online algorithms for minimum metric bipartite matching, in: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA ’06, Society for Industrial and Applied Mathematics, USA, 2006, p. 954–959.
  * [6] N. Bansal, N. Buchbinder, A. Gupta, J. S. Naor, An o(log2k)-competitive algorithm for metric bipartite matching, in: L. Arge, M. Hoffmann, E. Welzl (Eds.), Algorithms – ESA 2007, Springer Berlin Heidelberg, Berlin, Heidelberg, 2007, pp. 522–533.
  * [7] B. Kalyanasundaram, K. R. Pruhs, The online transportation problem, SIAM Journal on Discrete Mathematics 13 (3) (2000) 370–383.
  * [8] C. Chung, K. Pruhs, P. Uthaisombut, The online transportation problem: On the exponential boost of one extra server, in: E. S. Laber, C. Bornstein, L. T. Nogueira, L. Faria (Eds.), LATIN 2008: Theoretical Informatics, Springer Berlin Heidelberg, Berlin, Heidelberg, 2008, pp. 228–239.
  * [9] Y. The Tsai, C. Yi Tang, Y. Yen Chen, Average performance of a greedy algorithm for the on-line minimum matching problem on euclidean space, Information Processing Letters 51 (6) (1994) 275–282.


CHAPTER: RESUMÉ

En væsentlig kilde til bekymring i forskning om maskinlæringsmodeller er modellernes uigennemskuelighed. Sådanne modeller benyttes i stigende grad til
anvendelser, hvor de opererer som “black boxes” som ikke forklarer deres forudsigelser eller beslutninger. Blandt de potentielle farer knyttet til mangel på forståelse for modellernes rationaler er krænkelser af privatlivet, fjendtlig  manipulation og uretfærdig forskelsbehandling. Som følge heraf er ansvarlighed (en. accountability) og gennemskuelighed (en. transparency) for maskinlæringsmodeller blevet foreslået som kritisk vigtige designkriterier af forskning i politik, jura, filosofi og datalogi.

I datalogi er maskinlæringsmodellers beslutningsprocesser blevet undersøgt ved udvikling af metoder for ansvarlighed og gennemskuelighed. Flere metoder for undersøgelse af ansvarlighed, herunder brugen af fjendtlige angreb og diagnostiske datasæt, har påvist eksistensen af sårbarhed for modeller, og at sådanne sårbarheder kan føre til ondsindet manipulation af resultater, eller systematiske fejl i modellernes forudsigelser. For at imødegå dette, er det nødvendigt, at metoder til at sikre gennemskuelighed tillige opfylder en række krav for ansvarlighed, f.eks. at udvise robusthed og være tro mod de underliggende rationaler i modellerne.

Denne afhandling fremlægger min forskning, som udvider den samlede viden inden for ansvarlighed og gennemskuelighed for maskinlæringsmodeller, som er udviklet til at løse opgaver, der involverer komplekst ræsonnement om tekstdata. For det første bidrager afhandlingen med to ny metoder for ansvarlige maskinlæringsmodeller, herunder skabelsen fjendtlige input og et diagnostisk datasæt, som påviser væsentlige sårbarheder i modeller, og foreslår metoder til at afhjælpe disse sårbarheder. Inden for gennemskuelighed af maskinlæringsmodeller, bidrager afhandlingen med metoder til automatisk skabelse af forklaringer på skriftform, som yderligere forbedres til at benytte flydende sprog, er letlæselige og indeholder logisk sammenhængende argumentationskæder. Sluttelig bidrager afhandlingen til diagnostik af metoder til forklarlighed af maskinlæringsmodellers forudsigelser ved at definere en række egenskaber med hvilke allerede eksisterende forklarlighedsmetoder - og metoder til forbedring af sådanne - kan evalueres. All afhandlingens bidrag er eksperimentelt afprøvet på problemer, som involverer komplekst ræsonnement om tekstdata, herunder faktatjek, automatisk besvarelse af spørgsmål, og følgeslutninger i naturligt sprog.

CHAPTER: PUBLICATIONS

This thesis includes the following papers as chapters, listed in the order of their appearance ($^*$ denotes equal contribution):

* <cit.> Pepa Atanasova, Jakob Grue Simonsen, Christina Lioma, and Isabelle Augenstein. Fact Checking with Insufficient Evidence. 2022. Transactions of the Association for Computational Linguistics, pages 746–763.

* <cit.> Pepa Atanasova$^*$, Dustin Wright$^*$, and Isabelle Augenstein. Generating Label Cohesive and Well-Formed Adversarial Claims. 2020. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 3168–3177, Online. Association for Computational Linguistics.

* <cit.> Pepa Atanasova, Jakob Grue Simonsen, Christina Lioma, and Isabelle Augenstein. Generating Fact Checking Explanations. 2020. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7352–7364, Online. Association for Computational Linguistics.

* <cit.> Shailza Jolly, Pepa Atanasova, and Isabelle Augenstein. Generating Fluent Fact Checking Explanations with Unsupervised Post-Editing. 2022. In Information, Special Issue on Advances in Explainable Artificial Intelligence.

* <cit.> Ostrowski, Wojciech, Arnav Arora, Pepa Atanasova, and Isabelle Augenstein. Multi-hop fact checking of political claims. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, pages 3892-3898, Montreal, Canada.

* <cit.> Pepa Atanasova, Jakob Grue Simonsen, Christina Lioma, and Isabelle Augenstein. A Diagnostic Study of Explainability Techniques for Text Classification. 2020. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 3256–3274, Online. Association for Computational Linguistics.

* <cit.> Pepa Atanasova, Jakob Grue Simonsen, Christina Lioma, and Isabelle Augenstein. Diagnostics-Guided Explanation Generation. 2022. Proceedings of the AAAI Conference on Artificial Intelligence 36 (10), pages 10445-10453.

The following list of papers were also published during my Ph.D. studies. As they are unrelated to the topic of the thesis, they are not included in it. The topics of these publications include: dealing with limited labelled data (1), offensive language identification (2-3), fact checking and check-worthiness detection (4-6), dialogue system evaluation (7).

* <cit.> Luna De Bruyne, Pepa Atanasova, and Isabelle Augenstein. Joint emotion label space modeling for affect lexica. 2022. Computer Speech & Language 71, pages: 101257.

* <cit.> Marcos Zampieri, Preslav Nakov, Sara Rosenthal, Pepa Atanasova, Georgi Karadzhov, Hamdy Mubarak, Leon Derczynski, Zeses Pitenis, and Çağrı Çöltekin. SemEval-2020 Task 12: Multilingual Offensive Language Identification in Social Media (OffensEval 2020). 2020. In Proceedings of the Fourteenth Workshop on Semantic Evaluation, pages 1425–1447, Barcelona (online).

* <cit.> Sara Rosenthal, Pepa Atanasova, Georgi Karadzhov, Marcos Zampieri, and Preslav Nakov. SOLID: A Large-Scale Semi-Supervised Dataset for Offensive Language Identification. 2021. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 915–928, Online. Association for Computational Linguistics.

* <cit.> Pepa Atanasova, Preslav Nakov, Georgi Karadzhov, Mitra Mohtarami, and Giovanni Da San Martino. Overview of the CLEF-2019 CheckThat! Lab: Automatic Identification and Verification of Claims. Task 1: Check-Worthiness. 2019. International Conference of the Cross-Language Evaluation Forum for European Languages. Springer, Cham.

* <cit.> Slavena Vasileva, Pepa Atanasova, Lluís Màrquez, Alberto Barrón-Cedeño, and Preslav Nakov. It Takes Nine to Smell a Rat: Neural Multi-Task Learning for Check-Worthiness Prediction. 2019. In Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP 2019), pages 1229–1239, Varna, Bulgaria.

* <cit.> Pepa Atanasova, Preslav Nakov, Lluís Màrquez, Alberto Barrón-Cedeño, Georgi Karadzhov, Tsvetomila Mihaylova, Mitra Mohtarami, and James Glass. Automatic Fact-Checking Using Context and Discourse Information. 2019. J. Data and Information Quality 11, 3, Article 12 (September 2019), 27 pages.

* <cit.> Pepa Atanasova, Georgi Karadzhov, Yasen Kiprov, Preslav Nakov, and Fabrizio Sebastiani. Evaluating Variable-Length Multiple-Option Lists in Chatbots and Mobile Search. 2019. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR'19). Association for Computing Machinery, New York, NY, USA, pages: 997–1000.

Executive Summary

Accountability for Complex Reasoning Tasks over Text

Explainability for Complex Reasoning Tasks over Text

CHAPTER: MULTI-HOP FACT CHECKING OF POLITICAL CLAIMS

§ INTRODUCTION

An illustration of multiple hops over an instance from . Each instance consists of a claim, a speaker
, a veracity label, and a PolitiFact article the annotated evidence sentences. The highlighted sentences represent the evidence sentences a model needs to connect to arrive at the correct veracity prediction.

Recent progress in machine learning has seen interest in automating complex reasoning, where a conclusion can be reached only after following logically connected arguments.
To this end, multi-hop datasets and models have been introduced, which learn to combine information from several sentences to arrive at an answer. While most of them concentrate on question answering, fact checking is another task that often requires a combination of multiple evidence pieces to predict a claim's veracity.

Existing fact checking models usually optimize only the veracity prediction objective and assume that the task requires a single inference step. Such models ignore that often several linked evidence chunks have to be explicitly retrieved and combined to make the correct veracity prediction. Moreover, they do not provide explanations of their decision-making, which is an essential part of fact checking.

<cit.> note the importance of providing explanations for fact checking verdicts, and propose an extractive summarization model, which optimizes a ROUGE score metric w.r.t. a gold explanation.
Gold explanations for this are obtained from the LIAR-PLUS <cit.> dataset, which is constructed from PolitiFact[<https://www.politifact.com/>] articles written by professional fact checking journalists.
However, the dataset does not provide guidance on the several relevant evidence pieces that have to be linked and assume that the explanation requires a single reasoning step. FEVER <cit.> is another fact checking dataset, which contains annotations of evidence sentences from Wikipedia pages. However, it consists of manually augmented claims, which require limited reasoning capabilities for verification as the evidence mostly consists of one or two sentences.

To provide guidance for the multi-hop reasoning process of a claim's verification and facilitate progress on explainable fact checking, we introduce , a dataset of 500 real-world claims with manual annotations of sets of interlinked evidence chunks from PolitiFact articles needed to predict the claims' labels. We provide insights from the annotation process, indicating that fact checking real-world claims is an elaborate process requiring multiple hops over evidence chunks, where multiple evidence sets are also possible.

To assess the difficulty of the task, we conduct experiments with lexical baselines, as well as a single-inference step model – BERT <cit.>, and a multi-hop model – Transformer-XH <cit.>. Transformer-XH allows for the sharing of information between sentences located anywhere in the document by eXtra Hop attention and achieves the best performance.

We further study whether multi-hop reasoning learned with Transformer-XH can be transferred to . We find that the model cannot leverage any reasoning skills from training on FEVER, while training on LIAR-PLUS improves the performance on . We hypothesize that this is partly due to a domain discrepancy, as FEVER is constructed from Wikipedia and consists of claims requiring only one or two hops for verification. In contrast, LIAR-PLUS is based on PolitiFact, same as .

Finally, we perform a detailed error analysis to understand the models' shortcomings and recognize possible areas for improvement. We find that the models perform worse when the gold evidence sets are larger and that, surprisingly, named entity (NE) overlap between evidence and non-evidence sentences does not have a negative effect on either evidence retrieval or label prediction. The best results for Transformer-XH on the dev and test sets are for a different number of hops – 2 and 6, indicating that having a fixed parameter for the number of hops is a downside of Transformer-XH; this should instead be learned for each claim. Overall, our experiments constitute a solid basis to be used for future developments.

To summarise, our contributions are as follows:

* We document the first study on multi-hop fact checking of political claims.

* We create a dataset, , for the task.

* We study whether reasoning skills learned with a multi-hop model on similar datasets can be transferred to .

* We analyze to what degree existing multi-hop reasoning methods are suitable for the task.

§ MULTI-HOP FACT CHECKING

A multi-hop fact checking model $f(X)$ receives as an input $X=\{(claim_i, document_i)\\| i\in[1,|X|]\}$, where $document_i = [sentence_{ij}|j \in [1, |document_i|]]$ is the corresponding PolitiFact article for $claim_i$ and consists of a list of sentences. During the training process, the model learns to (i) select which sentences from the input contain evidence needed for the veracity prediction $y_i^S = [y_{ij}^S \in \{0, 1\}|j \in [1, |document_i|]]$ (sentence selection task), where 1 indicates that the sentence is selected as an evidence sentence; and (ii) predict the veracity label of the claim $y_i^L \in \{True, False, Half-True\}$, based on the extracted evidence (veracity prediction task). The sentences selected by the model as evidence provide sufficient explanation, which allows to verify the corresponding claim efficiently instead of reading the whole article. Each evidence set consists of $k$ sentences, where $k \in [1, max_{i\in[1,|X|]}(|document_i|)]$ is a hyper-parameter of the model. Figure <ref> illustrates the process of multi-hop fact checking, where multiple evidence sentences provide different information, which needs to be connected in logical order to reach the final veracity verdict.

Statistic     Test     Train

#Words per article     569 (280.8)     573 (269.1)

#Sent. per article     28 (12.8)     28 (12.8)

#Evidence sent. per article     11.75 (5.56)     6.33 (2.98)

#Evidence sent. per set     2.88 (1.43)     2.59 (1.51)

#Sets per article     4.08 (1.83)     2.44 (1.28)

3cLabel Distribution

False     149     216

Half-true     30     47

True     21     37

dataset statistics. Test set statistics are calculated for a union of two annotators; train instances are annotated by one annotator only, which makes some measures different across splits. We report the mean and standard deviation (in parentheses).

§.§ Dataset

We present , the first dataset for multi-hop fact checking of real-world claims. It consists of 500 manually annotated claims in written English, split into a training (300 instances) and a test set (200 instances). For each claim, the corresponding PolitiFact article was retrieved, which consists of a discussion of each claim and its veracity, written by a professional fact checker. The annotators then selected sufficient sets of evidence sentences from said articles.

As sometimes more than one set can be found to describe a reason behind the veracity of a claim independently, we further take each set in the training split as a separate instance, resulting in 733 training examples.
Each training example is annotated by one annotator, whereas each test example is annotated by two. We split the training data into train and dev datasets, where the former has 592 examples and the latter – 141. For veracity prediction, we arrived at Krippendorf's $\alpha$ and Fleiss' $\kappa$ agreement values of 0.638 and 0.637, respectively. By comparison, <cit.> reported Fleiss' $\kappa$ of 0.684 on FEVER. For the sentence prediction, we attain Krippendorf's $\alpha$ of 0.437. A more in-depth description of the annotation process can be found in the appendix.

Table <ref> presents statistics of the dataset.

The average number of evidence sentences per set is above 2, which already indicates that the task is more complex than the FEVER dataset. In FEVER, 83.2% of the claims require one sentence, whereas in , only 24.8% require one sentence.

§ MODELS

We compare the performance of five different models to measure the difficulty of automating the task.

Label prediction only. The majority baseline labels all claims as false.

We pick a random number $k \in [1, 10]$ and then randomly choose $k$ sentences from the document as evidence. For label prediction, we randomly pick one of the labels.

For each instance $x_i$ we construct a vector $v_i^C=[v_{il}^C| l \in [0, |N^C|]]$ with TF-IDF scores $v_{il}^C$ for all n-grams $N^C$ found in all of the claims; and one vector $v_i^D=[v_{im}^D| m \in [0, |N^D|]]$ with TF-IDF scores $v_{im}^D$ for all n-grams $N^D$ found in all of the documents, where $n \in [2, 3]$. We then train a Naive Bayes model $g(V)$, where $V = \{v_i = (v_i^C \cdot v_i^D) | i \in [0, |X|]\}$ is the concatenation of the two feature vectors.

We first train a Transformer model <cit.>, which does not include a multi-hop mechanism, but applies a single inference step to both the evidence retrieval and the label prediction tasks. We employ BERT <cit.> with the base pre-trained weights. Each sentence from a fact checking document is encoded separately, combined with the claim and the author of the claim. We refer to the encoded triple as node $\tau$. The tokens of one node $x_{\tau} = \{x_{\tau, j} | j \in [1, |x_{\tau}|]\}$ are encoded with the BERT model into contextualized distributed representations: $h_{\tau} = \{h_{\tau,j} | j \in [1, |x_{\tau}|\}$. The encoded representations of all nodes are passed through two feed-forward layers:

\begin{gather}
\small
p(y^{L}|\tau) = softmax(Linear(h_{\tau,0})) \label{eq:lone}\\
p(y^{S}|\tau) = softmax(Linear(h_{\tau,0})) \label{eq:ltwo}\\
p(y^{L}|X) = \sum_{\tau}p(y^{L}|\tau)p(y^{S}|\tau) \label{eq:final}
\end{gather}

The first layer predicts the veracity of the claim given a particular node $\tau$ by using the contextual representation of the “[CLS]” token, located at the first position (Eq. <ref>). The second feed-forward layer learns the importance of each node in the graph (Eq. <ref>). The outputs of these two layers are combined for the final label prediction (Eq. <ref>).
For evidence prediction, we choose $k$ most important sentences, as ranked by the second linear layer. In our experiments, we set $k=6$ since this is the average number of evidence sentences selected by a single annotator.
The implementation of the feed-forward prediction layers is the same as in Transformer-XH, described below, and can be viewed as an ablation of Transformer-XH removing the eXtra Hop attention layers.

Transformer-XH is a good candidate for a multi-hop model for our setup as it has previously achieved the best multi-hop evidence retrieval results on FEVER. It is also inspired by and improves over other multi-hop architectures <cit.>, and we conjecture that the results should be generalisable for its predecessors as well. Not least, its architecture allows for ablation studies of the multi-hop mechanism.
Following previous work on applying Transformer-XH to FEVER <cit.>, we encode node representations as with the BERT model and construct a fully connected graph with them. Transformer-XH uses eXtra hop attention layers to enable information sharing between the nodes.
An eXtra hop attention layer is a Graph Attention layer (GAT) <cit.>, which receives as input a graph $\{X, E\}$ of all evidence nodes $X$ and the edges between them $E$, where the edges encode the attention between two nodes in the graph. Each eXtra hop layer computes the attention between a node and its neighbors, which corresponds to one hop of reasoning across nodes.
Transformer-XH applies L eXtra hop layers to the BERT node encodings $H_0$, which results in new representations $H_L$ that encode the information shared between the nodes, unlike BERT, which encodes each input sentence separately.
We use three eXtra hop layers as in <cit.>, which corresponds to three-hop reasoning, and we experiment with varying the number of hops.
The representations $H_L$ are passed to the final two linear layers for label and evidence prediction as in BERT. The final prediction of the veracity label $p(y^{L}|\{X, E\})$ now can also leverage information exchanged in multiple hops between the nodes through the edges $E$ between them.

§ EXPERIMENTS

We address the following research questions:

* Can multi-hop architectures successfully reason over evidence sets on ?

* How do multi-hop vs. single inference architectures fare in an adversarial evaluation, where named entities (NE) in evidence and non-evidence sentences overlap?

* Does pre-training on related small in-domain or large out-of-domain datasets improve model performance?

We further perform ablation studies to investigate the influence of different factors on performance (see Section <ref>).

§.§ Experimental Setup

Metrics. We use macro $F_1$ score and accuracy for the veracity prediction task and $F_1$ and precision for the evidence retrieval task. To calculate the performance on both tasks jointly, we use the FEVER score <cit.>, where the model has to retrieve at least one full evidence set and predict the veracity label correctly for the label prediction to count as correct. We consider a single evidence set to be sufficient for correct label prediction. As each example from train and dev sets in , and every example from LIAR-PLUS, has one evidence set, all evidence sentences need to be retrieved for these. The employed measures for evidence retrieval allow for comparison to related work and for relaxing the requirements on the models. We consider the FEVER score to be the best for evaluating explainable fact checking.

Dataset settings.
We consider three settings: $\mathtt{adversarial}$, $\mathtt{full}$ article, and $\mathtt{even}$ $\mathtt{split}$.
For $\mathtt{full}$, the whole article for each claim is given as input.

For $\mathtt{even}$ $\mathtt{split}$, we pick all sentences from the same article, but restrict the number of non-evidence sentences to be at most equal to the number of evidence sentences. Non-evidence sentences are picked randomly.
This results in a roughly even split between evidence and non-evidence sentences for the test set.
Since we divide train and dev datasets into one evidence set per example, but keep all non-evidence for each, the number of non-evidence sentences for instances in these splits is usually 2-3 times larger than the number of evidence sentences. To examine if the investigated multi-hop models overfit on named entity (NE) overlaps, we further construct an $\mathtt{adversarial}$ dataset from the even split dataset by changing each non-evidence sentence to a random sentence from any PolitiFact article, which contains at least one NE present in the original evidence sentences. While such sentences can share information about a relevant NE, they are irrelevant for the claim. We argue that this is a good testbed to understand if a fact checking model can successfully reason over evidence sets and identify non-evidence sentences, even if they contain relevant NEs, which are rather surface features not indicating whether the sentence is relevant to the claim.

Training settings. We perform transfer learning, training on in-domain data (LIAR-PLUS, ), out-of-domain data (FEVER), or a combination thereof. See the appendix for details on training regimes and hyper-parameters.

Note that the measures do not consider the order of the sentences in the evidence set, and the systems do not predict that as well. We believe other measures and models that take that into account should be explored in future work. Here we consider them to appear in the same order as in the document. This also corresponds to the way they were annotated.

<EMAIL_ADDRESS>0.05inDev     5cTest

L-$\mathbf{F_1}$     L-Acc     E-$\mathbf{F_1}$     E-Prec     FEVER
L-$\mathbf{F_1}$     L-Acc     E-$\mathbf{F_1}$     E-Prec     FEVER

Random     34.1     38.5     22.9     30.2     4.5
24.2     27.7     14.7     12.2     0.7

Majority     27.3     69.5     -     -     -     28.6     75.0     -     -     -

Annotator     -     -     -     -     -     76.3     -     52.4     49.2     -

TF-IDF     34.4     69.5     -     -     -     34.0     76.0     -     -     -

11cLIAR-PLUS full articles dataset

BERT     45.4     70.9     18.4     13.7     14.9
57.0     76.0     32.9     38.9     13.0

Transformer-XH     56.2     74.5     17.1     12.8     14.2
56.3     79.5     30.3     35.8     12.0

11cPolitiHop full articles dataset

BERT     54.7     69.5     32.0     23.6     31.9
44.8     76.0     47.0     54.2     24.5

Transformer-XH     61.1     76.6     30.4     22.3     34.8
43.3     75.5     44.7     51.7     23.5

11cLIAR-PLUS and PolitiHop full articles

BERT     64.4     75.9     29.6     21.7     28.4
57.8     79.5     45.1     52.2     23.5

Transformer-XH     64.6     78.7     32.4     23.8     38.3
57.3     80.5     47.2     54.5     24.5

results for label (L), evidence (E) and joint (FEVER) performance in the $\mathtt{full}$ setting. Best results with a particular training dataset (LIAR-PLUS/PolitiHop/LIAR-PLUS and PolitiHop) are emboldened and the best results across all set-ups are underlined.

§ RESULTS

Full article setting. From the results

in Table <ref>, we can observe that both BERT and Transformer-XH greatly outperform the Random and TF-IDF baselines.
Out of BERT and Transformer-XH, neither model clearly outperforms the other on our dataset. This is surprising as Transformer-XH outperforms the BERT baselines by a significant margin on both FEVER and the multi-hop dataset HotpotQA <cit.>.
However, we observe that the best performance is achieved with Transformer-XH trained on LIAR-PLUS, then fine-tuned on . It also achieves the highest FEVER scores on  in that setting.
Further, very low FEVER scores of both Transformer-XH and BERT indicate how challenging it is to retrieve the whole evidence set.

Adversarial setting.

We train the Transformer-XH models on the $\mathtt{even}$ $\mathtt{split}$ setting, then evaluate it on both  $\mathtt{adversarial}$ and $\mathtt{even}$ $\mathtt{split}$ datasets (see Table <ref>).
The model performs similarly in both settings. When compared on test sets, it achieves a higher FEVER score on the $\mathtt{adversarial}$, but the dev set's FEVER score is higher on the $\mathtt{even}$ $\mathtt{split}$ setting. Overall, the results show Transformer-XH is robust towards NE overlap.

<EMAIL_ADDRESS>0.05inDev     5cTest

L-$\mathbf{F_1}$     L-Acc     E-$\mathbf{F_1}$     E-Prec     FEVER
L-$\mathbf{F_1}$     L-Acc     E-$\mathbf{F_1}$     E-Prec     FEVER

even split     58.1     71.6     47.7     35.5     52.5
62.9     82.0     58.2     66.7     31.0

adversarial     56.5     70.9     49.9     38.7     46.8
56.4     77.0     63.6     76.0     33.5

$\mathtt{adversarial}$ vs $\mathtt{even}$ $\mathtt{split}$ dataset results for label (L), evidence (E) and joint (FEVER) performance for Transformer-XH trained on LIAR-PLUS and  on the $\mathtt{even}$ $\mathtt{split}$ setting. Best result emboldened.

Out-of-domain pre-training on FEVER.
In this experiment, we examine whether pre-training Transformer-XH on the large, but out-of-domain dataset FEVER, followed by fine-tuning on LIAR-PLUS, then on   improves results on .
As can be seen from Table <ref>, it does not have a positive effect on performance in the $\mathtt{full}$ setting, unlike pre-training on LIAR-PLUS. We hypothesize that the benefits of using a larger dataset are outweighed by the downsides of it being out-of-domain.
We further quantify the domain differences between datasets. We use Jensen-Shannon divergence <cit.>, commonly employed for this purpose <cit.>. The divergence between FEVER and  is 0.278, while between LIAR-PLUS and  is 0.063, which further corroborates our hypothesis.
Another reason might be that  has several times more input sentences compared to FEVER.
Labelling difference might matter as well: FEVER uses `true', `false' and `not enough info', while  uses `true', `false' and `half-true'.

<EMAIL_ADDRESS>0.05inDev     5cTest

L-$\mathbf{F_1}$     L-Acc     E-$\mathbf{F_1}$     E-Prec     FEVER
L-$\mathbf{F_1}$     L-Acc     E-$\mathbf{F_1}$     E-Prec     FEVER

+    48.6     70.2     30.5     22.2     32.6
59.9     83.0     45.1     52.7     21.5

+    64.6     78.7     32.4     23.8     38.3
57.3     80.5     47.2     54.5     24.5

$\mathtt{full}$ results for label (L), evidence (E) and joint (FEVER) performance for Transformer-XH trained on different datasets. Best model emboldened.

§ ANALYSIS AND DISCUSSION

In Section <ref>, we documented experimental results on multi-hop fact checking of political claims. Overall, we found that multi-hop training on Transformer-XH gives small improvements over BERT, that pre-training on in-domain data helps, and that Transformer-XH deals well with an adversarial test setting.
Below, we aim to further understand the impact of modeling multi-hop reasoning explicitly with a number of ablation studies:

* How the evidence set size affects performance;

* Varying the hops' number in Transformer-XH;

* The impact of evidence set size on performance;

* How NE overlap affects performance;

* To what extent Transformer-XH pays attention to relevant evidence sentences.

Further ablation studies can be found in the appendix, namely on: impact of varying the number of evidence sentences on evidence retrieval; how to weigh the different loss functions (for label vs. evidence prediction); if providing supervision for evidence sentence positions impacts performance; and to what degree high label confidence is an indication of high performance.

Varying the number of hops in Transformer-XH.
We train Transformer-XH with a varying number of hops to see if there is any pattern in how many hops result in the best performance. <cit.> perform a similar experiment and find that 3 hops are best, similar for 2-5 hops, while the decrease in performance is noticeable for 1 and 6 hops.

We experiment with hops between 1 and 7 (see Table <ref>). Evidence retrieval performance is quite similar in each case. There are some differences for the label prediction task: 1 and 2 hops have slightly worse performance, the 4-hop model has the highest test score and the lowest dev score, while the exact opposite holds for the 5-hop model. Therefore, no clear pattern can be found. One reason for this could be the high variance of the annotated evidence sentences in .

<EMAIL_ADDRESS>0.05inDev     5cTest

L-$\mathbf{F_1}$     L-Acc     E-$\mathbf{F_1}$     E-Prec     FEVER
L-$\mathbf{F_1}$     L-Acc     E-$\mathbf{F_1}$     E-Prec     FEVER

1     54.0     75.2     47.1     35.2     52.5
58.9     79.5     58.7     67.6     33.0

2     56.1     73.0     47.5     35.4     53.9
59.8     78.5     58.1     66.7     32.5

3     58.1     71.6     47.7     35.5     52.5
62.9     82.0     58.2     66.7     31.0

4     53.3     70.9     47.0     34.9     50.4
65.0     82.0     58.9     67.6     33.0

5     59.6     73.0     47.7     35.5     51.8
55.3     76.5     58.7     67.3     32.0

6     56.5     73.0     45.9     34.2     50.4
64.9     81.5     57.5     66.0     35.0

7     56.3     71.6     46.4     34.6     50.4
62.8     81.5     57.9     66.4     33.0

Transformer-XH results for label (L), evidence (E) and joint (FEVER) performance for training on the LIAR-PLUS +  $\mathtt{even}$ $\mathtt{split}$ datasets with a varying number of hop layers. Best sentence number emboldened.

Evidence set size vs. performance.

Not surprisingly, larger number of evidence sentences leads to higher precision and lower recall, resulting in a lower FEVER score. This is true for both models, as Table <ref> (top) indicates. We also notice that the smaller the number, the smaller the ratio of evidence to non-evidence sentences.

For instance, if a claim has two sets of evidence, one of size 1 and the other of size 3, then after splitting into one example per set, there are 4 non-evidence sentences in each of the two examples, but the one with set of size 1 has only one evidence sentence – which decreases the evidence to non-evidence ratio and makes it more difficult to achieve high precision.

<EMAIL_ADDRESS>0.05inTransformer-XH     5cBERT

L-$\mathbf{F_1}$     L-Acc     E-$\mathbf{F_1}$     E-Prec     FEVER
L-$\mathbf{F_1}$     L-Acc     E-$\mathbf{F_1}$     E-Prec     FEVER

1 or 2 evidence
sentences     63.9     76.8     43.7     29.2     74.4
53.5     72.0     41.3     27.5     62.2

3+ evidence
sentences     60.9     66.1     67.5     56.2     42.4
57.8     66.1     65.8     54.8     40.7

$<$  40% NE overlap     62.5     77.0     59.1     46.2     62.3
62.0     75.4     57.7     45.1     59.0

$\geq$ 40% NE overlap     63.6     71.0     48.5     35.5     60.9
47.5     66.7     46.2     33.8     49.3

$\mathtt{adversarial}$ dev set performance vs. (top) evidence set size and (bottom) NE overlap between evidence and non-evidence sentences for label (L), evidence (E) and joint (FEVER) performance. Better model emboldened.

Named entity overlap vs. performance.
To measure the effect of having the same NEs in evidence and non-evidence sentences, we computed NE overlap – a measure of the degree to which evidence and non evidence sentences share NEs. We compute the overlap as $|E \cap N|/|E \cup N|$; E and N are sets of NEs in evidence and non-evidence sentences, respectively.
Table <ref> (bottom) shows that a higher NE overlap results in more confusion when retrieving evidence sentences, but it does not have a significant influence on label prediction in the case of Transformer-XH. For BERT, higher NE overlap leads to a bigger, negative effect on both tasks. This suggests Transformer-XH is more robust to NE overlaps.

ev $\rightarrow$ non-ev     ev $\rightarrow$ ev     non-ev $\rightarrow$ non-ev     non-ev $\rightarrow$ ev

1.085     1.076     0.966     0.964

Attention weights in the last eXtra hop layer of Transformer-XH. The numbers are the average ratios of the actual attention weights to average attention weight of the given graph.

Attention over evidence sentences.
We investigate what attention patterns Transformer-XH learns.
Ideally, attention flowing from evidence sentences should be higher than from non-evidence ones since this determines how much they contribute to the final representations of each sentence. To do this, we inspect the weights in the final eXtra hop layer. We normalize results by measuring the ratio of the given attention to the average attention for the given graph: 1 means average, over/under 1 means more/less than average.
Table <ref> shows average ratios for evidence vs. non-evidence sentences. One notable finding is that attention weights from evidence sentences are higher than average, and attention from non-evidence sentences is lower. The Welch t-test indicates that the difference is significant with a $p$-value lower than 10$^{-30}$. So, attention weights get more importance on average, but the magnitude of this effect is quite limited. This shows the limitations of using Transformer-XH for this task.

§ RELATED WORK

Fact checking.

Several datasets have been released

to assist in automating fact checking.
<cit.> present a dataset with 106 political claim-verdict pairs.

The FakeNewsChallenge [<http://www.fakenewschallenge.org/>], provides 50K headline-article pairs and formulates the task of fact checking as stance detection between the headline and the body of the article. The relationship between these two tasks is further explored in <cit.>.
<cit.> extract 12.8K claims from PolitiFact constituting the LIAR dataset.
<cit.> introduce the LIAR-PLUS dataset extending the latter with automatically extracted summaries from PolitiFact articles. These are, however, high-level explanations that omit evidence details. LIAR-PLUS also does not provide annotation of particular evidence sentences from the article leading to the final verdict and the possible different evidence sets.
<cit.> present a real-world dataset constructed from 26 fact checking portals, including PolitiFact, consisting of 35k claims paired with crawled evidence documents.
<cit.> present the FEVER dataset, consisting of 185K claims produced by manually re-writing Wikipedia sentences.

Furthermore, <cit.> from the FEVER'2019 shared task <cit.> and <cit.> use adversarial attacks to show the vulnerability of models trained on the FEVER dataset to claims that require more than one inference step.
Unlike prior work, we construct a dataset with annotations of the different reasoning sets and the multiple hops that constitute them.

Multi-hop datasets.

Multi-hop reasoning has been mostly studied in the context of Question Answering (QA).
<cit.> introduce HotpotQA with Wikipedia-based question-answer pairs requiring reasoning over multiple documents and provide gold labels for sentences supporting the answer.

<cit.> introduce MedHop and WikiHop datasets for reasoning over multiple documents. These are constructed using Wikipedia and DrugBank as Knowledge Bases (KB), and are limited to entities and relations existing in the KB. This, in turn, limits the type of questions that can be generated. TriviaQA <cit.> and SearchQA <cit.> contain multiple documents for question-answer pairs but have few examples where reasoning over multiple paragraphs from different documents is necessary.

Multi-hop models. <cit.> observe that models without multi-hop reasoning are still able to perform well on a large portion of the test dataset. <cit.> employ a pointer-based architecture, which re-ranks documents related to a claim and jointly predicts the sequence of evidence sentences and their stance to the claim. <cit.>

sequentially extract paragraphs from the reasoning path conditioning on the documents extracted on the previous step. CogQA <cit.>

detect spans and entities of interest and then run a BERT-based Graph Convolutional Network for ranking. <cit.>

perform semantic retrieval of relevant paragraphs followed by span prediction in the case of QA and 3-way classification for fact checking. <cit.>, <cit.>, and <cit.> model documents as a graph and apply attention networks across the nodes of the graph. We use <cit.>'s model due to its strong performance in multi-hop QA on the HotpotQA dataset, in evidence-based fact checking on FEVER, and to evaluate its performance on real-world claim evidence reasoning.

§ CONCLUSIONS

In this paper, we studied the novel task of multi-hop reasoning for fact checking of real-world political claims, which encompasses both evidence retrieval and claim veracity prediction.
We presented , the first political fact checking dataset with annotated evidence sentences.
We compared several models on  and found that the multi-hop architecture Transformer-XH slightly outperforms BERT in most of the settings, especially in terms of evidence retrieval, where BERT is easily fooled by named entity overlaps between the claim and evidence sentences.
The performance of Transformer-XH is further improved when retrieving more than two evidence sentences and the number of hops larger than one, which corroborates the assumption of the multi-hop nature of the task.

§ APPENDICES

§.§ Annotation Process

§.§.§ Annotation Pipeline

We used the PolitiFact API to retrieve the articles, along with the source pages used in the article, the claim and the author of the claim. For each article we performed the annotation process as follows:

* Reading the claim and the article.

* Picking the evidence sentences from the corresponding PolitiFact article. These sentences should sum up the whole article while providing as much evidence as possible.

* Deciding on the veracity label.

* Going to each relevant url and checking whether it contains the equivalent textual evidence.

In Step 2, we retrieved evidence sentences sentences, where each sentence follows from the previous one and together they constitute enough evidence to verify the claim and provide an explanation for it.

In Step 4, we wanted to examine how often the evidence can be retrieved from external sources, i.e. not relying on PolitiFact articles. However, we have not gathered enough data to carry out a reliable evaluation of this and thus left the idea for future work.

Originally, following <cit.>, we wanted to have a `not enough evidence' label, but due to a small frequency of this label in the annotations, as well as due to a significant disagreement between annotators on that label, we decided to discard it and re-label it with one of the remaining labels (false, half-true or true).
In case of conflicting label annotations, a third annotator was asked to resolve the conflict.

§.§.§ Inter-Annotator Agreement

We report Inter-Annotator Agreement (IAA) agreement on the test set, where we had two annotators annotating each instance. For the veracity prediction task, annotators’ Krippendorf's $\alpha$ and Fleiss' $\kappa$ are equal to 0.638 and 0.637 respectively. By comparison, <cit.> reported Fleiss' $\kappa$ of 0.684 on the veracity label prediction, which is the another indication of the increased complexity when predicting veracity of claims occurring naturally. For the sentence prediction task, when treating each ruling article as a separate dataset and averaging over all articles, annotators achieve 0.437 Fleiss' $\kappa$ and 0.437 Krippendorff's $\alpha$ (we also compute IAA when treating all sentences from all articles as one dataset, where both IAA measures drop to 0.400). Figure <ref> confirms the intuition that annotators tend to agree more on the shorter articles, which are easier to annotate as they contain fewer sets and fewer hops per set.

Article length vs. inter-annotator agreement.

§.§ Training Details

We used LIAR-PLUS and  for training in three different settings:

1. Training on LIAR-PLUS only.

2. Training on  only.

3. Pre-training on LIAR-PLUS and fine-tuning on .

4. Pre-training on FEVER, then fine-tuning on LIAR-PLUS and .

In the first setting, the models are trained for 4 epochs on LIAR-PLUS. In the second setting, the models are trained for 8 epochs on . In the third setting, models are trained for 4 epochs on LIAR-PLUS, followed by 4 epochs on . In every setting, models are evaluated on the dev set and the model with the best label prediction macro $F_1$ score is saved, which enables early stopping.
For the fourth setting, we pre-train the model for 2 epochs on the FEVER dataset, followed by 4 epochs on LIAR-PLUS, the fine-tune on  for 4 epochs.

The models have been trained and evaluated using one NVIDIA TITAN RTX.
We report the results based on a single run with a random seed fixed to 42.

Both BERT and Transformer-XH are trained with the same hyperparameters as in <cit.>: BERT 12 layers' with the hidden size of 768, 3 GAT layers with the hidden size of 64. Optimized with Adam with the learning rate of 1e-5. For the TF-IDF baseline, we also remove English stop words using the built-in list in the Scikit-learn library <cit.>.

Some of the experiments are ablation studies of the number of GAT layers and the number of retrieved evidence sentences. The former varies between 1 and 7 while the latter varies between 1 and 10.

§.§ Additional Results

Number of evidence sentences vs. evidence retrieval performance. One of the challenges of generating fact checking explanations is deciding on the length of the explanation. By design, the explanations should be short, ideally just a few sentences. On the other hand, they have to provide a comprehensive motivation of the fact checking verdict. Transformer-XH handles evidence retrieval by ranking the importance of each input sentence.
We, therefore, pick the most highly ranked sentences, according to the model. By default for all experiments in Section <ref>, the top 6 sentences are used, as it is the average length of an annotation in the  test set.

<EMAIL_ADDRESS>0.05inTest     3cDev

#S.    $\mathbf{F_1}$    Recall    Precision    $\mathbf{F_1}$     Recall     Precision

1     15.9     9.7     62.0     17.3     13.5

2     27.6     19.4     61.0     27.8     28.9

3     36.2     28.5     61.2     31.8     39.4

4     41.3     35.5     59.1     32.3     47.0

5     44.0     41.0     55.8     31.6     52.9

6     47.2     47.2     54.5     32.4     60.9

7     49.2     52.5     52.9     31.8     65.8

8     50.3     56.9     51.0     31.2     70.5

9     50.8     60.7     49.0     30.5     74.7

10     51.0     64.1     47.3     29.1     76.4

evidence retrieval results for a model trained on LIAR-PLUS $\mathtt{full}$, then fine-tuned on  $\mathtt{full}$, with a varying number of top sentences retrieved as evidence. Best number of sentences emboldened.

Table <ref> shows how recall trades off against precision and improves as an increasing number of sentences is selected.

Test set $F_1$ grows as the number of sentences grows, while the best train set $F_1$ is the highest for 3 sentences and it gets worse as the number of sentences increases. $F_1$ on dev set is much more even for different numbers, but it peaks at 6 sentences. Generally, 6 sentences gives the best trade-off between the performance on test and dev sets, while being short enough to be considered as short summary of the whole article.

<EMAIL_ADDRESS>0.05inDev     3cTest

Lab     Evi     Joint
Lab     Evi     Joint

BERT     72.2     43.7     11.3
72.0     43.5     14.5

TXH     73.7     44.4     12.1
72.6     44.6     13.4

LIAR-PLUS results when trained on the LIAR-PLUS full articles dataset. Best model emboldened. The Lab(el) and Evi(dence) results are $F_1$ scores, and Joint is measured with FEVER score.

LIAR-PLUS. Here, we investigate training then testing on LIAR-PLUS. As Table <ref> shows, Transformer-XH outperforms BERT by a small margin. This confirms the results in <cit.> that Transformer-XH generally performs well in multi-hop settings.

Loss function comparison. In this experiment we compare BERT and Transformer-XH performance on the  full article setting when trained with three different loss functions. The default loss function is the sum of evidence prediction loss and label prediction loss. The EVI setting uses evidence loss only and saves the model with the highest validation set evidence $F_1$ score. The LAB setting uses label prediction loss only and saves the model with the highest macro $F_1$ score on validation data label prediction, just like in the default setting.

Table <ref> shows the best performance with the joint loss for BERT. EVI setting hurts the label prediction while LAB setting hurts the evidence prediction, without providing a clear boost in the second metric over the joint model. Transformer-XH performs much worse on evidence prediction when trained using label prediction loss only. Interestingly, there is no clear performance difference between EVI and default settings.

<EMAIL_ADDRESS>0.05inDev     5cTest

<EMAIL_ADDRESS>0.05inLabel<EMAIL_ADDRESS>0.05inEvidence     Joint
<EMAIL_ADDRESS>0.05inLabel<EMAIL_ADDRESS>0.05inEvidence     Joint

$\mathbf{F_1}$     Acc     $\mathbf{F_1}$     Prec     FEVER
$\mathbf{F_1}$     Acc     $\mathbf{F_1}$     Prec     FEVER

BERT     64.4     75.9     29.6     21.7     28.4
57.8     79.5     45.1     52.2     23.5

Transformer-XH     64.6     78.7     32.4     23.8     38.3
57.3     80.5     47.2     54.5     24.5

BERT-EVI     34.0     51.1     31.8     23.4     26.2
40.7     63.5     45.7     52.8     21.5

Trans-XH-EVI     56.0     68.1     34.4     25.2     33.3
59.9     75.5     46.7     54.2     21.5

BERT-LAB     59.4     72.3     19.9     14.8     14.9
60.3     77.5     33.8     40.1     13.5

Trans-XH-LAB     62.0     75.2     18.2     13.5     14.9
60.6     81.5     32.4     38.8     13.0

Random     24.2     27.7     14.7     12.2     0.7
34.1     38.5     22.9     30.2     4.5

results trained on LIAR-PLUS +  full articles datasets. EVI means the model was trained with loss on the evidence prediction task only. LAB means the loss on the label prediction only. The default loss was the sum of both. Best model emboldened.

Adding sentence IDs to sentence encodings.
The main goal of this experiment was to see whether providing the information about the positions of the sentences in articles can be leveraged to improve the performance of BERT and Transformer-XH models.

We took the models pre-trained on LIAR-PLUS without sentence positions and fine-tuned the model on  with sentence positions, by prepending each sentence's encoding with the token [unusedN], where $N=$ sentence position.
Table <ref> shows a significant performance boost for Transformer-XH label prediction, but not for evidence retrieval. BERT does not exhibit any improvement, which is to be expected as it considers each sentence in isolation, it doesn't learn any interactions between sentences.

<EMAIL_ADDRESS>0.05inDev     5cTest

<EMAIL_ADDRESS>0.05inLabel<EMAIL_ADDRESS>0.05inEvidence     Joint
<EMAIL_ADDRESS>0.05inLabel<EMAIL_ADDRESS>0.05inEvidence     Joint

$\mathbf{F_1}$     Acc     $\mathbf{F_1}$     Prec     FEVER
$\mathbf{F_1}$     Acc     $\mathbf{F_1}$     Prec     FEVER

BERT     62.4     75.2     27.7     20.3     24.1
57.4     79.0     42.9     49.2     21.5

Transformer-XH     65.2     78.0     32.2     23.6     38.3
66.5     84.0     47.2     54.9     26.5

results for training on LIAR-PLUS $\mathtt{full}$, then fine-tuning on  $\mathtt{full}$ with sentence ID encodings. Best model emboldened.

Label confidence vs. performance.
The goal here was to measure how confident the models are in their label predictions and to see if higher confidence means better performance. The results are presented in Table <ref>.

Transformer-XH is usually sure of its predictions, so not much can be observed based on that - it does indeed have higher $F_1$ score when it is more confident, but there are too few instances where it is not confident to make any conclusions - apart from the one that it's often sure but makes a mistake anyway. Besides, NE overlap was not particularly high for the instances where the model got confused.

The effect is even stronger with BERT to the point where having less than 95% confidence usually results in a bad prediction.

<EMAIL_ADDRESS>0.05inTransformer-XH     5cBERT

<EMAIL_ADDRESS>0.05inLabel<EMAIL_ADDRESS>0.05inEvidence     Joint
<EMAIL_ADDRESS>0.05inLabel<EMAIL_ADDRESS>0.05inEvidence     Joint

$\mathbf{F_1}$    Acc    $\mathbf{F_1}$    Prec    FEVER    $\mathbf{F_1}$     Acc    $\mathbf{F_1}$    Prec    FEVER

$<$ 90%     45.5     46.2     51.6     39.7     34.6
30.9     32.6     52.9     41.6     20.9

$\geq$ 90%     67.2     78.3     54.1     40.7     67.0
72.5     85.7     50.9     37.8     67.3

adversarial dev set performance vs. label confidence.

§.§ PolitiHop Example

Table <ref> shows an example from the proposed  dataset.

Claim: Claim: Says 20 million Chinese converted to Islam after it’s proven that the coronavirus doesn’t affect Muslims.

Speaker: Viral image

Label: false

Ruling Comments:

[1] Amid fears about the coronavirus disease , a YouTube video offers a novel way to inoculate yourself: convert to Islam. [2] “20m Chinese gets converted to Islam after it is proven that corona virus did not affect the Muslims,” reads the title of a video posted online Feb. 18 (...) [5] That’s because the footage is from at least as far back as May 26, 2019, when it was posted on Facebook with this caption:
“Alhamdulillah welcome to our brothers in faith.” [6] On Nov. 7, 2019, it was posted on YouTube with this title: “MashaaAllah hundreds converted to Islam in Philippines.” [7] Both posts appeared online before the current outbreak of the new coronavirus, COVID-19, was first reported in Wuhan, China, on Dec. 31, 2019. [8] But even if the footage followed the outbreak, Muslims are not immune to COVID-19, as the Facebook post claims. [9] After China, Iran has emerged as the second focal point for the spread of COVID-19, the New York Times reported on Feb. 24 . [10]
“The Middle East is in many ways the perfect place to spawn a pandemic, experts say, with the constant circulation of both Muslim pilgrims and itinerant workers who might carry the virus.” [11] On Feb. 18, Newsweek reported that coronavirus “poses a serious risk to millions of inmates in China’s Muslim prison camps.”

An example from the  dataset. Each example consists of a claim, a speaker (author of the claim), a veracity label and a PolitiFact article with the annotated evidence sentences. One of the evidence sets is in bold, and the other in italics.

Diagnostic Explainability Methods