# On the validity of bootstrap uncertainty estimates in the Mallows-Binomial
model

Michael Pearce
Department of Statistics
University of Washington
Seattle, WA
<EMAIL_ADDRESS>
&Elena A. Erosheva
Department of Statistics, School of Social Work, and the Center for
Statistics and the Social Sciences
University of Washington
Seattle, WA
<EMAIL_ADDRESS>

###### Abstract

The Mallows-Binomial distribution is the first joint statistical model for
rankings and ratings [12]. Because frequentist estimation of the model
parameters and their uncertainty is challenging, it is natural to consider the
nonparametric bootstrap. However, it is not clear that the nonparametric
bootstrap is asymptotically valid in this setting. This is because the
Mallows-Binomial model is parameterized by continuous quantities whose
discrete order affects the likelihood. In this note, we demonstrate that
bootstrap uncertainty of the maximum likelihood estimates in the Mallows-
Binomial model are asymptotically valid.

_K_ eywords preference learning $\cdot$ rankings and ratings $\cdot$ bootstrap
validity $\cdot$ asymptotic theory $\cdot$ uncertainty quantification

##  1 Introduction

Rankings and ratings are two types of preference data, which are primarily
studied separately in the literature. Rankings may be modeled via a variety of
specialized distributions, such as the Mallows [8], Plackett-Luce [13], and
Bradley-Terry [2]. Ratings are not commonly modeled using statistical methods,
but are instead studied using simple summary statistics such as the mean or
median [6, 16, 10]. In recent years, a growing body of work suggests that
modeling rankings and ratings jointly may improve the accuracy of preference
modeling and preference aggregation [11, 15, 7]. The Mallows-Binomial is the
first joint statistical model for rankings and ratings [12].

[12] estimated the Mallows-Binomial model in the frequentist setting via the
method of maximum likelihood. Similar to the standard Mallows model,
estimation of the Mallows-Binomial is provably an NP-hard problem [9].
However, exact calculation of the MLE is possible when a relatively small
number of objects are assessed via an exact tree-search algorithm based on A∗,
and approximate algorithms can be used otherwise [12]. Still, analytic
standard error results are challenging for the Mallows-Binomial and led the
authors to propose using the nonparametric bootstrap for uncertainty
quantification.

The bootstrap is a very general tool for uncertainty quantification that was
first proposed in [3]. The nonparametric bootstrap is used to estimate the
inherent uncertainty of an estimator without making assumptions on its
distributional form. Given $n$ i.i.d. observations, $X=(X_{1},\dots,X_{n})$,
the nonparametric bootstrap is performed using the following steps:

  1. 1.

Re-sample $n$ observations with replacement from the original dataset $B$
times, for large $B$. Denote each bootstrap sample $X^{b}$, $b=1,\dots,B$.

  2. 2.

Estimate the unknown statistic(s) of interest, $\theta$, separately using each
bootstrap sample. Denote the estimates from each bootstrap sample
$\hat{\theta}^{b}$, $b=1,\dots,B$.

  3. 3.

Form an empirical distribution for $\hat{\theta}$ using the values
$\hat{\theta}^{b}$, $b=1,\dots,B$.

Quantiles from the empirical distribution of the unknown statistic(s) of
interest may be used for the purpose of creating confidence regions.

Despite its wide applicability, the nonparametric bootstrap does not always
yield asymptotically valid confidence intervals. A canonical example in which
the bootstrap fails is the estimation of the unknown parameter $\theta$ given
i.i.d. samples from a Uniform$(0,\theta)$ distribution. Here, the MLE of
$\theta$ is the maximum order statistic, which has a limiting exponential
distribution. The bootstrap empirical distribution, however, will not be able
to replicate the asymptotic distribution given the fixed sample, in which the
bootstrap estimates of $\theta$ will always be less than or equal to the full-
sample maximum order statistic [1]. Another canonical example in which the
bootstrap fails is in estimating the location parameter of a Cauchy
distribution. In this setting, the MLE is the sample mean which is itself
Cauchy distributed and therefore has infinite variance. As a result, the
bootstrap estimator behaves poorly even given large samples [14].

The Mallows-Binomial likelihood has an unusual form that makes the asymptotic
validity of bootstrap uncertainty for the MLE unclear. Specifically, the model
is parameterized by continuous parameters whose discrete order impacts the
likelihood. That is, the likelihood contains both continuous and discrete
components; discontinuities may exist whenever the order of certain parameters
change. Thus, frequentist estimation of the Mallows-Binomial model is both a
continuous and discrete problem. In the absence of theoretical results
regarding the asymptotic distribution of the maximum likelihood estimators,
the validity of the nonparametric bootstrap is unclear.

In this note, we demonstrate that the nonparametric bootstrap is an
asymptotically valid method of uncertainty quantification for maximum
likelihood estimates in the Mallows-Binomial model. The rest of the paper is
organized as follows: In Section 2, we provide preliminaries regarding
notation and a formal model statement. Main asymptotic results are provided in
Section 3, followed by a conclusion in Section 4 that summarizes our work and
suggests directions for future study.

##  2 Preliminaries

###  2.1 Notation

Suppose there exists a collection of $J$ objects which will be assessed by $I$
judges. Each judge rates each object using the integers $\\{0,1,\dots,M\\}$,
where $M$ is a fixed and known maximum rating. Smaller ratings are better;
higher ratings are worse. We let $X_{ij}$ represent the rating that judge $i$
assigns to object $j$. Additionally, each judge provides a ranking of their
most-preferred objects. For simplicity, we assume each judge provides a
ranking of all the objects. We let $\Pi_{i}$ denote judge $i$’s ranking.

Furthermore, suppose that each object $j\in\\{1,\dots,J\\}$ has a true
underlying quality $p_{0j}\in(0,1)$. The vector of true underlying qualities
is written as $p_{0}=[p_{01}\ p_{02}\ \dots p_{0J}]^{T}$, such that
$p_{0}\in(0,1)^{J}$. Given a vector $p\in(0,1)^{J}$, we let $\pi_{p}$ denote
its order from least to greatest. For example, if $p=[0.3\ 0.2\ 0.1]^{T}$,
then $\pi_{p}=3\prec 2\prec 1$ (read as “object 3 is preferred to object 2,
which is preferred to object 1"). We call $\pi_{p_{0}}$ the true consensus
ranking of the objects. Additionally, we assume there is a true
$\theta_{0}>0$, which represents the strength of population ranking consensus.
$\theta_{0}$ is defined identically to that from a traditional Mallows $\phi$
model.

###  2.2 Mallows-Binomial

The Mallows-Binomial model is a joint distribution for rankings and ratings
that is designed to capture the above situation. Let $(X,\Pi)_{I}$ denote an
i.i.d. sample of size $I$ from a Mallows-Binomial($p_{0},\theta_{0}$)
distribution. Their joint likelihood can be written:

$\displaystyle\mathcal{L}\Big{(}(X,\Pi)_{I}|p_{0},\theta_{0}\Big{)}$
$\displaystyle=\prod_{i=1}^{I}\Bigg{(}\frac{e^{-\theta_{0}d(\pi_{i},\pi_{p_{0}})}}{\psi(\theta_{0})}\times\prod_{j=1}^{J}{M\choose
x_{ij}}p_{0j}^{x_{ij}}(1-p_{0j})^{M-x_{ij}}\Bigg{)}$ (1)
$\displaystyle=\frac{e^{-\theta_{0}\sum_{i=1}^{I}d(\pi_{i},\pi_{p_{0}})}}{\psi(\theta_{0})^{I}}\times\prod_{j=1}^{J}\Bigg{(}\prod_{i=1}^{I}{M\choose
x_{ij}}\Bigg{)}p_{0j}^{\sum_{i=1}^{I}x_{ij}}(1-p_{0j})^{IM-\sum_{i=1}^{I}x_{ij}},$
(2)

where $d(\cdot,\cdot)$ is the Kendall’s $\tau$ distance between the two
rankings and

$\psi(\theta)=\prod_{j=1}^{J}\frac{1-e^{-j\theta}}{1-e^{-\theta}}$ (3)

is the normalizing function of a Mallows model. As can be seen from Equation
1, the likelihood of each observation corresponds to the product of a Mallows
$\phi$ ranking distribution with $J$ Binomial rating distributions.

Next, we provide a preliminary expression for the MLE,
$(\hat{p},\hat{\theta})$:

$\displaystyle(\hat{p},\hat{\theta})$
$\displaystyle=\underset{p,\theta}{\arg\max}\Bigg{[}-\theta\sum_{i=1}^{I}d(\pi_{i},\pi_{p})-I\log\psi(\theta)$
(4) $\displaystyle\hskip
65.0pt+\sum_{j=1}^{J}(\sum_{i=1}^{I}x_{ij})\log(p_{j})+(IM-\sum_{i=1}^{I}x_{ij})\log(1-p_{j})\Bigg{]}$
$\displaystyle=\underset{p,\theta}{\arg\max}\Bigg{[}-\theta\bar{D}(\pi,\pi_{p})-\log\psi(\theta)+\sum_{j=1}^{J}\Big{(}\bar{x_{j}}\log(p_{j})+(M-\bar{x_{j}})\log(1-p_{j})\Big{)}\Bigg{]}$
(5)
$\displaystyle\equiv\underset{p,\theta}{\arg\max}\Bigg{[}f_{(X,\Pi)_{I}}(p,\theta)\Bigg{]},$
(6)

where

$\bar{D}(\pi,\pi_{p})=I^{-1}\sum_{i}d(\pi_{i},\pi_{p}),$ (7)

and

$\bar{x}_{j}=I^{-1}\sum_{i}x_{ij}.$ (8)

There is no closed-form solution for the MLE. However, computationally-
efficient frequentist estimation is possible via a tree-search method based on
the A∗ algorithm [12].

In the remainder of this work, we will assume that in $p_{0}$, $p_{0j}\neq
p_{0k}$ whenever $j\neq k$. Furthermore, we assume that each
$p_{0j}\in(a,b)\subset[0,1]$, and that $\theta\in(c,d)\subset[0,\infty)$.
Under these conditions, [12] proved that the maximum likelihood estimator
$(\hat{p},\hat{\theta})$ is consistent for $(p_{0},\theta_{0})$ as the number
of judges, $I$, grows to infinity.

##  3 Asymptotic Bootstrap Validity

We would like to show that bootstrap uncertainty estimates are asymptotically
valid for the MLE in the Mallows-Binomial model. A sufficient condition for
bootstrap validity is local asymptotic normality of the MLE [5, 1]. As such,
we show in the following subsections that the $(J+1)$-dimensional MLE
$(\hat{p},\hat{\theta})$ is coordinate-wise, locally asymptotically normal.

###  3.1 Local Asymptotic Normality of $\hat{p}_{j}$

We begin by considering each $\hat{p}_{j}$, $j=1,\dots,J$. Note that
$\hat{p}_{j}$ is the solution to the following equation:

$\displaystyle 0$ $\displaystyle=\frac{\partial}{\partial
p_{j}}f_{(X,\Pi)_{I}}(p,\theta)$ (9)
$\displaystyle=-\theta\Big{[}\frac{\partial}{\partial
p_{j}}\bar{D}(\pi,\pi_{p})\Big{]}+\frac{\bar{x}_{j}}{p_{j}}-\frac{M-\bar{x}_{j}}{1-p_{j}}$
(10)

A key challenge in calculating $\hat{p}_{j}$ is the derivative
$\frac{\partial}{\partial p_{j}}\bar{D}(\pi,\pi_{p})$, which is a function of
the $J$-dimensional vector $p$. However, as long as each $p_{k}\neq p_{j}$
whenever $k\neq j$, then $\pi_{p}$ will remain constant in small perturbations
around $p_{j}$ and the derivative in $p_{j}$ will thus be 0.

Generalizing from $p_{j}$ to $p$, we require there to exist an $\epsilon$-ball
around the J-dimensional vector $p$ such that $\text{Order}(p)=\pi_{p}$
remains constant for all $p^{\prime}$ in the ball. In such cases, we have
$\frac{\partial}{\partial p_{j}}\bar{D}(\pi,\pi_{p})=0$ and thus $\hat{p}_{j}$
is defined by the standard Binomial MLE, $\bar{x}_{j}/M$, which is
asymptotically normal as it is a function of the mean of i.i.d. random
variables.

Specifically, this means that in a local region defined by the order of
$\hat{p}$, we have the standard Binomial result,

$\displaystyle\sqrt{I}\Big{(}\hat{p}_{j}-p_{0j}\Big{)}\overset{d}{\to}N\Big{(}0,\frac{p_{0j}(1-p_{0j})}{M}\Big{)},$
(11)

which establishes the coordinate-wise local asymptotic normality of
$\hat{p}_{j}$, $j=1,\dots,J$.

###  3.2 Local Asymptotic Normality of $\hat{\theta}$

We now show that $\hat{\theta}$ is coordinate-wise a locally asymptotically
normal estimator of $\theta_{0}$. Note that $\hat{\theta}$ is the solution to
the following equation:

$\displaystyle 0$
$\displaystyle=\frac{\partial}{\partial\theta}f_{(X,\Pi)_{I}}(p,\theta)$ (12)
$\displaystyle=-\bar{D}(\pi,\pi_{p})-\frac{\psi^{\prime}(\theta)}{\psi(\theta)}$
(13) $\displaystyle\implies\bar{D}(\pi,\pi_{p})$
$\displaystyle=-\frac{\psi^{\prime}(\theta)}{\psi(\theta)}.$ (14)

For simplicity, we define
$\kappa(\theta)=-\psi^{\prime}(\theta)/\psi(\theta)$. Thus, we have

$\displaystyle\hat{\theta}$ $\displaystyle=\kappa^{-1}(\bar{D}(\pi,\pi_{p})).$
(15)

No simple expression for $\kappa^{-1}$ exists. However, it can be seen from
Equation 3 that when $J\geq 2$ and for any $\theta>0$, $\psi$ is a continuous
and positive function with a continuous and strictly negative first derivative
and a continuous and strictly positive second derivative. Thus,
$\kappa(\cdot)$ is a smooth and positive function. Furthermore, $\kappa$ is
monotone decreasing [4]. As a result, its inverse $\kappa^{-1}(\cdot)$ is
well-defined and so is $\hat{\theta}$ given $\bar{D}(\pi,\pi_{p})$.

For reasons which will be made clear later, we also write out an expression
for $\kappa(\theta)$:

$\displaystyle\kappa(\theta)=-\frac{\psi^{\prime}(\theta)}{\psi(\theta)}$
$\displaystyle=-\frac{\frac{(1-e^{-\theta})^{J}(\frac{\partial}{\partial\theta}\prod_{j=1}^{J}1-e^{-j\theta})-(\prod_{j=1}^{J}1-e^{-j\theta})Je^{-\theta}(1-e^{-\theta})^{J-1}}{(1-e^{-\theta})^{2J}}}{\frac{\prod_{j=1}^{J}1-e^{-j\theta}}{(1-e^{-\theta})^{J}}}$
(16)
$\displaystyle=-\frac{(\frac{\partial}{\partial\theta}\prod_{j=1}^{J}1-e^{-j\theta})-(\prod_{j=1}^{J}1-e^{-j\theta})Je^{-\theta}/(1-e^{-\theta})}{\prod_{j=1}^{J}1-e^{-j\theta}}$
(17)
$\displaystyle=\frac{Je^{-\theta}}{1-e^{-\theta}}-\frac{(\frac{\partial}{\partial\theta}\prod_{j=1}^{J}1-e^{-j\theta})}{\prod_{j=1}^{J}1-e^{-j\theta}}$
(18)
$\displaystyle=\frac{Je^{-\theta}}{1-e^{-\theta}}-\frac{\partial}{\partial\theta}\log(\prod_{j=1}^{J}1-e^{-j\theta})$
(19)
$\displaystyle=\frac{Je^{-\theta}}{1-e^{-\theta}}-\sum_{j=1}^{J}\frac{je^{-j\theta}}{1-e^{-j\theta}}$
(20)

Next, note that $\bar{D}(\pi,\pi)$ is a random variable given a fixed
consensus ranking $\pi$, due to the randomness in the collection of rankings
$\pi$. According to [4], $\bar{D}(\pi,\pi_{p_{0}})$ is asymptotically normal
with mean and variance depending on the true $\theta_{0}$. Specifically,

$\displaystyle\mu_{\theta_{0}}$ $\displaystyle\equiv
E_{\theta_{0}}[D(\pi_{i},\pi_{p_{0}})]=\frac{Je^{-\theta_{0}}}{1-e^{-\theta_{0}}}-\sum_{j=1}^{J}\frac{je^{-j\theta_{0}}}{1-e^{-j\theta_{0}}}$
(21) $\displaystyle\sigma^{2}_{\theta_{0}}$ $\displaystyle\equiv
Var_{\theta_{0}}[D(\pi_{i},\pi_{p_{0}})]=\frac{Je^{-\theta_{0}}}{(1-e^{-\theta_{0}})^{2}}-\sum_{j=1}^{J}\frac{j^{2}e^{-j\theta_{0}}}{(1-e^{-j\theta_{0}})^{2}}$
(22)
$\displaystyle\implies\sqrt{I}(\bar{D}(\pi,\pi_{p_{0}})-\mu_{\theta_{0}})\overset{d}{\to}N(0,\sigma^{2}_{\theta_{0}})$
(23)

Interestingly, we see from comparing Equations 20 and 21 that
$\mu_{\theta_{0}}=\kappa(\theta_{0})$, which implies
$\kappa^{-1}(\mu_{\theta_{0}})=\theta_{0}$. Since $\kappa^{-1\prime}$ is a
real-valued function that does not equal 0, by the Delta method,

$\displaystyle\sqrt{I}\Big{(}\kappa^{-1}(\bar{D}(\pi,\pi_{p_{0}}))-\kappa^{-1}(\mu_{\theta_{0}})\Big{)}$
$\displaystyle\overset{d}{\to}N\Big{(}0,\sigma^{2}_{\theta_{0}}[\kappa^{-1\prime}(\mu_{\theta_{0}})]^{2}\Big{)}$
(24) $\displaystyle\implies\sqrt{I}\Big{(}\hat{\theta}-\theta_{0}\Big{)}$
$\displaystyle\overset{d}{\to}N\Big{(}0,\sigma^{2}_{\theta_{0}}[\kappa^{-1\prime}(\mu_{\theta_{0}})]^{2}\Big{)}$
(25)

Although the asymptotic variance cannot be written in closed-form expression,
it is positive and finite. Therefore, in a local area of $\pi_{p_{0}}$,
$\hat{\theta}$ is coordinate-wise an asymptotically normal estimator of
$\theta$.

###  3.3 Asymptotic Normality of $(\hat{p},\hat{\theta})$

We showed in Sections 3.1 and 3.2 that in a local neighborhood of the true
consensus ranking $\pi_{p_{0}}$, the estimators $\hat{p}_{j}$, $j=1,\dots,J$
and $\hat{\theta}$ are coordinate-wise asymptotically normal. We add that the
MLE $(\hat{p},\hat{\theta})$ is consistent as the number of observations, $I$,
grows to infinity [12]. Thus, $\hat{p}\overset{p}{\to}p_{0}$ and
$\hat{\theta}\overset{p}{\to}\theta_{0}$. As a result, as $I\to\infty$ the MLE
$\pi_{\hat{p}}$ will be in a local neighborhood of the true $\pi_{p_{0}}$ with
probability tending to 1, and the MLE $(\hat{p},\hat{\theta})$ will be
coordinate-wise an asymptotically normal estimator of $(p_{0},\theta_{0})$ in
that local neighborhood. This satisfies a sufficient condition for asymptotic
bootstrap validity [5, 1].

##  4 Conclusion

In this note, we demonstrate that bootstrap uncertainty estimates are
asymptotically valid for the MLE in the Mallows-Binomial distribution. Our
work only proves coordinate-wise, local asymptotic normality of the vector-
valued MLE. This result technically guarantees only asymptotically accurate
marginal coverage. As a result, the confidence intervals may be conservative
when applied jointly. To understand why this is true, we can think of the
marginal confidence intervals jointly creating a confidence region that is a
$(J+1)$-dimensional hypercube, as opposed to a $(J+1)$-dimensional confidence
ellipse that could be created via a true joint analysis. However, the present
results do not preclude the possibility that bootstrap uncertainty estimates
provide asymptotically correct coverage in the joint setting. In fact, we find
no evidence to suggest asymptotically correct joint intervals are invalid.
Further research may demonstrate proper coverage in the joint setting by
establishing joint asymptotic normality of the $(J+1)$-dimensional MLE in a
local neighborhood of $\pi_{p_{0}}$.

The present work does not address the computational challenges of frequentist
estimation of the Mallows-Binomial model, which is an NP-hard problem [12, 9].
As a result, forming an appropriate empirical distribution of the MLE
$(\hat{p},\hat{\theta})$ via repeated estimation of bootstrap samples may be
intractably slow. Bayesian estimation presents a natural alternative for
estimating uncertainty in a unified framework, which may ultimately speed up
the process of parameter estimation and inference and make moot the question
of bootstrap validity.

## Acknowledgements

The authors would like to thank Yen-Chi Chen for his helpful feedback and
advice while assembling this work. This work was funded by NSF Grant No.
2019901.

## References

  * [1] Peter J Bickel and David A Freedman  “Some asymptotic theory for the bootstrap”  In _The Annals of Statistics_ 9.6 Institute of Mathematical Statistics, 1981, pp. 1196–1217
  * [2] Ralph Allan Bradley and Milton E Terry  “Rank analysis of incomplete block designs: I. The method of paired comparisons”  In _Biometrika_ 39.3/4 JSTOR, 1952, pp. 324–345
  * [3] B. Efron  “Bootstrap Methods: Another Look at the Jackknife”  In _The Annals of Statistics_ 7.1 Institute of Mathematical Statistics, 1979, pp. 1–26
  * [4] Michael A Fligner and Joseph S Verducci  “Distance based ranking models”  In _Journal of the Royal Statistical Society: Series B (Methodological)_ 48.3 Wiley Online Library, 1986, pp. 359–369
  * [5] Peter Hall  “The Bootstrap and Edgeworth Expansion”  Springer Science & Business Media, 2013
  * [6] Carole J Lee, Cassidy R Sugimoto, Guo Zhang and Blaise Cronin  “Bias in peer review”  In _Journal of the American Society for Information Science and Technology_ 64.1 Wiley Online Library, 2013, pp. 2–17
  * [7] Yusha Liu, Yichong Xu, Nihar B Shah and Aarti Singh  “Integrating Rankings into Quantized Scores in Peer Review”  In _arXiv preprint arXiv:2204.03505_ , 2022
  * [8] Colin L Mallows  “Non-null ranking models. I”  In _Biometrika_ 44.1/2 JSTOR, 1957, pp. 114–130
  * [9] Marina Meila, Kapil Phadnis, Arthur Patterson and Jeff A Bilmes  “Consensus ranking under the exponential model”  In _arXiv preprint arXiv:1206.5265_ , 2012
  * [10] National Institutes of Health  “Peer Review”, 2021  URL: https://grants.nih.gov/grants/peer-review.htm
  * [11] Seth Ovadia  “Ratings and rankings: Reconsidering the structure of values and their measurement”  In _International Journal of Social Research Methodology_ 7.5 Taylor & Francis, 2004, pp. 403–414
  * [12] Michael Pearce and Elena A Erosheva  “A Unified Statistical Learning Model for Rankings and Scores with Application to Grant Panel Review”  In _arXiv preprint arXiv:2201.02539_ , 2022
  * [13] Robin L Plackett  “The analysis of permutations”  In _Journal of the Royal Statistical Society: Series C (Applied Statistics)_ 24.2 Wiley Online Library, 1975, pp. 193–202
  * [14] Dimitris N Politis  “Computer-intensive methods in statistical analysis”  In _IEEE signal processing magazine_ 15.1 IEEE, 1998, pp. 39–55
  * [15] Nihar B Shah et al.  “Design and analysis of the NIPS 2016 review process”  In _Journal of Machine Learning Research_ , 2018
  * [16] Wenyi Tay, Xiuzhen Zhang and Sarvnaz Karimi  “Beyond mean rating: Probabilistic aggregation of star ratings based on helpfulness”  In _Journal of the Association for Information Science and Technology_ 71.7 Wiley Online Library, 2020, pp. 784–799


11institutetext: Computer Vision Center, UAB, Spain
11email: {rperez, dimos<EMAIL_ADDRESS>
# Document Collection Visual Question Answering

Rubèn Tito  Dimosthenis Karatzas  Ernest Valveny

###### Abstract

Current tasks and methods in Document Understanding aims to process documents
as single elements. However, documents are usually organized in collections
(historical records, purchase invoices), that provide context useful for their
interpretation. To address this problem, we introduce Document Collection
Visual Question Answering (DocCVQA) a new dataset and related task, where
questions are posed over a whole collection of document images and the goal is
not only to provide the answer to the given question, but also to retrieve the
set of documents that contain the information needed to infer the answer.
Along with the dataset we propose a new evaluation metric and baselines which
provide further insights to the new dataset and task.

###### Keywords:

Document collection Visual Question Answering

##  1 Introduction

Documents are essential for humans since they have been used to store
knowledge and information over the history. For this reason there has been a
strong research effort on improving the machine understanding of documents.
The research field of Document Analysis and Recognition (DAR) aims at the
automatic extraction of information presented on paper, initially addressed to
human comprehension. Some of the most widely known applications of DAR involve
processing office documents by recognizing text [14], tables and forms layout
[8], mathematical expressions [25] and visual information like figures and
graphics [30]. However, even though all these research fields have progressed
immensely during the last decades, they have been agnostic to the end purpose
they can be used for. Moreover, despite the fact that document collections are
as ancient as documents themselves, the research in this scope has been
limited to document retrieval by lexical content in word spotting [22, 27],
blind to the semantics and ignoring the task of extracting higher level
information from those collections.

On the other hand, over the past few years Visual Question Answering (VQA) has
been one of the major relevant tasks as a link between vision and language.
Even though the works of [6] and [31] start considering text in VQA by
requiring the methods to read the text in the images to answer the questions,
they constrained the problem to natural scenes. It was [24] who first
introduced VQA on documents. However, none of those previous works consider
the image collection perspective, neither from real scenes nor documents.

In this regard, we present Document Collection Visual Question Answering
(DocCVQA) as a step towards better understanding document collections and
going beyond word spotting. The objective of DocCVQA is to extract information
from a document image collection by asking questions and expecting the methods
to provide the answers. Nevertheless, to ensure that those answers have been
inferred using the documents that contain the necessary information, the
methods must also provide the IDs of the documents used to obtain the answer
in the form of a confidence list as answer evidence. Hence, we design this
task as a retrieval-answering task, for which the methods should be trained
initially on other datasets and consequently, we pose only a set of 20
questions over this document collection. In addition, most of the answers in
this task are actually a set of words extracted from different documents for
which the order is not relevant, as we can observe in the question example in
Figure 1. Therefore, we define a new evaluation metric based on the Average
Normalized Levenshtein Similarity (ANLS) to evaluate the answering performance
of the methods in this task. Finally, we propose two baseline methods from
very different perspectives which provide some insights on this task and
dataset.

The dataset, the baselines code and the performance evaluation scripts with an
online evaluation service are available in https://docvqa.org.

|
---|---
Q: In which years did Anna M. Rivers run for the State senator office?
A: [2016, 2020]
E: [454, 10901]
Figure 1: Top: Partial visualization of sample documents in DocCVQA. The left
document corresponds to the document with ID 454, which is one of the relevant
documents to answer the question below. Bottom: Example question from the
sample set, its answer and their evidences. In DocCVQA the evidences are the
documents where the answer can be inferred from. In this example, the correct
answer are the years 2016 and 2020, and the evidences are the document images
with ids 454 and 10901 which corresponds to the forms where Anna M. Rivers
presented as a candidate for the State senator office.

##  2 Related Work

###  2.1 Document understanding

Document understanding has been largely investigated within the document
analysis community with the final goal of automatically extracting relevant
information from documents. Most works have focused on structured or semi-
structured documents such as forms, invoices, receipts, passports or ID cards,
e-mails, contracts, etc. Earlier works [9, 29] were based on a predefined set
of rules that required the definition of specific templates for each new type
of document. Later on, learning-based methods [8, 26] allowed to automatically
classify the type of document and identify relevant fields of information
without predefined templates. Recent advances on deep learning [20, 36, 37]
leverage natural language processing, visual feature extraction and graph-
based representations in order to have a more global view of the document that
take into account word semantics and visual layout in the process of
information extraction.

All these methods mainly focus on extracting key-value pairs, following a
bottom-up approach, from the document features to the relevant semantic
information. The task proposed in this work takes a different top-down
approach, using the visual question answering paradigm, where the goal drives
the search of information in the document.

###  2.2 Document retrieval

Providing tools for searching relevant information in large collections of
documents has been the focus of document retrieval. Most works have addressed
this task from the perspective of word spotting [27], i.e., searching for
specific query words in the document collection without relying on explicit
noisy OCR. Current state-of-the-art on word spotting is based on similarity
search in an common embedding space [1] where both the query string and word
images can be projected using deep networks [17, 32] In order to search for
the whole collection, these representations are combined with standard deep
learning architectures for object detection in order to find all instances of
a given word in the document [17, 34].

Word spotting only allows to search for the specific instances of a given word
in the collection without taking into account the semantic context where that
word appears. On the contrary, the task proposed in this work does not aim to
find specific isolated words, but to make a semantic retrieval of documents
based on the query question.

###  2.3 Visual Question Answering

Visual Question Answering (VQA) is the task where given an image and a natural
language question about that image, the objective is to provide an accurate
natural language answer. It was initially introduced in [21, 28] and [3]
proposed the first large scale dataset for this task. All the images from
those works are real scenes and the questions mainly refer to objects present
in the images. Nonetheless, the field became very popular and several new
datasets were released exploring new challenges like ST-VQA [6] and TextVQA
[31], which were the first datasets that considered the text in the scene. In
the former dataset, the answers are always contained within the text found in
the image while the latter requires to read the text, but the answer might not
be a direct transcription of the recognized text. The incorporation of text in
VQA posed two main challenges. First, the number of classes as possible
answers grew exponentially and second, the methods had to deal with a lot of
out of vocabulary (OOV) words both as answers or as input recognized text. To
address the problem of OOV words, embeddings such as Fasttext [7] and PHOC [1]
became more popular, while in order to predict an answer, along with the
standard fixed vocabulary with the most common answers a copy mechanism was
introduced by [31] which allowed to propose an OCR token as an answer. Later
[13] changed the classification output to a decoder that outputs a word from
the fixed vocabulary or from the recognized text at each timestep, and
provided more flexibility in complex and longer answers.

Concerning documents, FigureQA [16] and DVQA [15] focused on complex figures
and data representation like different kinds of charts and plots by proposing
synthetic datasets and corresponding questions and answers over those figures.
More recently, [23] proposed DocVQA, the first VQA dataset over document
images, where the questions also refer to figures, forms or tables but also
text in complex layouts. Along with the dataset they proposed some baselines
based on NLP and scene text VQA models. In this sense, we go a step further
extending this work for document collections.

Finally, one of the most relevant works for this paper is ISVQA [4] where the
questions are asked over a small set of images which consist of different
perspectives of the same scene. Notice that even though the set up might seem
similar, the methods to tackle this dataset and the one we propose are very
different. For ISVQA all the images share the same context, which implies that
finding some information in one of the images can be useful for the other
images in the set. In addition, the image sets are always small sets of $6$
images, in contrast to the whole collection of DocCVQA and finally, the images
are about real scenes which don’t even consider the text. As an example, the
baselines they propose are based on the HME-VideoQA [11] and standard VQA
methods stitching all the images, or the images features. Which are not
suitable to our problem.

##  3 DocCVQA Dataset

In this section we describe the process for collecting images, questions and
answers, an analysis of the collected data and finally, we describe the metric
used for the evaluation of this task.

###  3.1 Data Collection

####  3.1.1 Images:

The DocCVQA dataset comprises $14,362$ document images sourced from the Open
Data portal of the Public Disclosure Commission (PDC), an agency that aims to
provide public access to information about the financing of political
campaigns, lobbyist expenditures, and the financial affairs of public
officials and candidates. We got the documents from this source for various
reasons. First, it’s a live repository that is updated periodically and
therefore, the dataset can be increased in size in the future if it’s
considered necessary or beneficial for the research. In addition, it contains
a type of documents in terms of layout and content that makes sense and can be
interesting to reason about an entire collection. Moreover, along with the
documents, they provide their transcriptions in the form of CSV files which
allows us to pose a set of questions and get their answers without the costly
process of annotation. From the original collection of document images, we
discarded all the multi-page documents and documents for which the
transcriptions were partially missing or ambiguous. Thus, all documents that
were finally included in the dataset were sourced from the same document
template, the US Candidate Registration form, with slight design differences
due to changes over the time. However, these documents still pose some
challenges since the proposed methods will need to understand its complex
layout, as well as handwritten and typewritten text at the same time. We
provide some document examples in Figure 1.

####  3.1.2 Questions and Answers:

Considering that DocCVQA dataset is set up as a retrieval-answering task and
documents are relatively similar we pose only a set of $20$ natural language
questions over this collection. To gather the questions and answers, we first
analyzed which are the most important fields in the document form in terms of
complexity (numbers, dates, candidate’s names, checkboxes and different form
field layouts) and variability (see section 3.2). We also defined different
types of constraints for the types of questions since limiting the questions
to find a specific value would place this in a standard word spotting
scenario. Thus, we defined different constraints depending on the type of
field related to the question: for dates, the questions will refer to the
document before, after and between specific dates, or specific years. For
other textual fields the questions refer to documents with specific values
(candidates from party $P$), to documents that do not contain specific values
(candidates which do not represent the party $P$), or that contains a value
from a set of possibilities (candidates from parties $P$, $Q$ or $R$). For
checkboxes we defined constraints regarding if a value is checked or not.
Finally, according to the fields and constraints defined we posed the
questions in natural language referring to the whole collection, and asking
for particular values instead of the document itself. We provide the full list
of questions in the test set in table 1.

ID |  Question
---|---
8 |  Which candidates in 2008 were from the Republican party?
9 |  Which candidates ran for the State Representative office between 06/01/2012 and 12/31/2012?
10 |  In which legislative counties did Gary L. Schoessler run for County Commissioner?
11 |  For which candidates was Danielle Westbrook the treasurer?
12 |  Which candidates ran for election in North Bonneville who were from neither the Republican nor Democrat parties?
13 |  Did Valerie I. Quill select the full reporting option when she ran for the 11/03/2015 elections?
14 |  Which candidates from the Libertarian, Independent, or Green parties ran for election in Seattle?
15 |  Did Suzanne G. Skaar ever run for City Council member?
16 |  In which election year did Stanley J Rumbaugh run for Superior Court Judge?
17 |  In which years did Dean A. Takko run for the State Representative office?
18 |  Which candidates running after 06/15/2017 were from the Libertarian party?
19 |  Which reporting option did Douglas J. Fair select when he ran for district court judge in Edmonds? Mini or full?
Table 1: Questions in test set.

Once we had the question, we got the answer from the annotations downloaded
along with the images. Then, we manually checked that those answers were
correct and unambiguous, since some original annotations were wrong. Finally,
we divided the questions into two different splits; the sample set with $8$
questions and the test set with the remaining $12$. Given the low variability
of the documents layout, we ensured that in the test set there were questions
which refer to document form fields or that had some constraints that were not
seen in the sample set. In addition, as depicted in figure 2 the number of
relevant documents is quite variable among the questions, which poses another
challenge that methods will have to deal with.

Figure 2: Number of relevant documents in ground truth for each question in
the sample set (blue) and the test set (red).

###  3.2 Statistics and Analysis

We provide in table 2 a brief description of the document forms fields used to
perform the questions and expected answers with a brief analysis of their
variability showing the number of values and unique values in their
annotations.

###  3.3 Evaluation metrics

The ultimate goal of this task is the extraction of information from a
collection of documents. However, as previously demonstrated, and especially
in unbalanced datasets, models can learn that specific answers are more common
to specific questions. One of the clearest cases is the answer _Yes_ , to
questions that are answered with _Yes_ or _No_. To prevent this, we not only
evaluate the answer to the question, but also if the answer has been reasoned
from the document that contains the information to answer the question, which
we consider as evidence. Therefore, we have two different evaluations, one for
the evidence which is based on retrieval performance, and the other for the
answer, based on text VQA performance.

Field | Type | # Values | # Unique values
---|---|---|---
Candidate name | Text | 14362 | 9309
Party | Text | 14161 | 10
Office | Text | 14362 | 43
Candidate city | Text | 14361 | 476
Candidate county | Text | 14343 | 39
Election date | Date | 14362 | 27
Reporting option | Checkbox | 14357 | 2
Treasurer name | Text | 14362 | 10197
Table 2: Description of the document forms fields with a brief analysis of
their variability showing the number of values and unique values in their
annotations.

####  3.3.1 Evidences:

Following standard retrieval tasks [19] we use the Mean Average Precision
(MAP) to assess the correctness of the positive evidences provided by the
methods. We consider as positive evidences the documents in which the answer
to the question can be found.

####  3.3.2 Answers:

Following other text based VQA tasks [5, 6] we use the Average Normalized
Levenshtein Similarity (ANLS) which captures the model’s reasoning capability
while smoothly penalizing OCR recognition errors. However, in our case the
answers are a set of items for which the order is not relevant, in contrast to
common VQA tasks where the answer is a string. Thus, we need to adapt this
metric to make it suitable to our problem. We name this adaptation as Average
Normalized Levenshtein Similarity for Lists (ANLSL), formally described in
equation 1. Given a question $Q$, the ground truth list of answers
$G=\\{g_{1},g_{2}\dots g_{M}\\}$ and a model’s list predicted answers
$P=\\{p_{1},p_{2}\dots p_{N}\\}$, the ANLSL performs the Hungarian matching
algorithm to obtain a $k$ number of pairs $U=\\{u_{1},u_{2}\dots u_{K}\\}$
where $K$ is the minimum between the ground truth and the predicted answer
lists lengths. The Hungarian matching ($\Psi$) is performed according to the
Normalized Levenshtein Similarity ($NLS$) between each ground truth element
$g_{j}\in G$ and each prediction $p_{i}\in P$. Once the matching is performed,
all the NLS scores of the $u_{z}\in U$ pairs are summed and divided for the
maximum length of both ground truth and predicted answer lists. Therefore, if
there are more or less ground truth answers than the ones predicted, the
method is penalized.

$\displaystyle U={\Psi}(NLS(G,P))$ (1) $\displaystyle
ANLSL=\frac{1}{\max(M,N)}\sum_{z=1}^{K}NLS(u_{z})$

##  4 Baselines

This section describes the two baselines that are employed in the experiments.
Both baselines breakdown the task into two different stages. First, they rank
the documents according to the confidence of containing the information to
answer a given a question and then, they get the answers from the documents
with the highest confidence. The first baseline combines methods from the word
spotting and NLP Question Answering fields to retrieve the relevant documents
and answer the questions. We name this baseline as _Text spotting + QA_. In
contrast, the second baseline is an ad-hoc method specially designed for this
task and data, which consist on extracting the information from the documents
and map it in the format of key-value relations. In this sense it represents
the collection similar as databases do, for which we name this baseline as
_Database_. These baselines allows to appreciate the performance of two very
different approaches.

###  4.1 Text spotting + QA

The objective of this baseline is to set a starting performance result from
the combination of two simple but generic methods that will allow to assess
the improvement of future proposed methods.

####  4.1.1 Evidence retrieval:

To retrieve the relevant documents we apply a text spotting approach, which
consist on ranking the documents according to a confidence given a query,
which in our case is the question. To obtain this confidence, we first run a
Part Of Speech (POS) tagger over the question to identify the most relevant
words in it by keeping only nouns and digits, and ignore the rest of the
words. Then, as described in equation 2, given a question $Q$, for each
relevant word in the question $qw_{i}\in Q$ we get the minimum Normalized
Levenshtein Distance ($NLD$) [18], between all recognized words $rw_{j}$
extracted through an OCR in the document and the question word. Then, we
average over all the distances and use the result as the confidence $c$ for
which the document $d$ is relevant to the question.

$c_{d}=\frac{1}{|Q|}\sum_{i=1}^{|Q|}\min_{j=1}^{|OCR|}\\{NLD(qw_{i},rw_{j})\\}$
(2)

Notice that removing only stopwords is not enough, like in the question
depicted in figure 1, where the verb _run_ is not considered as stopword, but
can’t be found in the document and consequently would be counterproductive.

####  4.1.2 Answering:

Once the documents are ranked, to answer the given questions we make use of
BERT [10] question answering model. BERT is a task agnostic language
representation based on transformers [33] that can be afterwards used in other
downstream tasks. In our case, we use extractive question answering BERT
models which consist on predicting the answer as a text span from a context,
usually a passage or paragraph by predicting the start and end indices on that
context. Nonetheless, there is no such context in the DocCVQA documents that
encompasses all the textual information. Therefore, we follow the approach of
[23] to build this context by serializing the recognized OCR tokens on the
document images to a single string separated by spaces following a top-left to
bottom-right order. Then, following the original implementation of [10] we
introduce a start vector $S\in\mathbb{R}^{H}$ and end vector
$E\in\mathbb{R}^{H}$. The probability of a word $i$ being the start of the
answer span is obtained as the dot product between the BERT word embedding
hidden vector $T_{i}$ and $S$ followed by a softmax over all the words in the
paragraph. The same formula is applied to compute if the word $i$ is the end
token by replacing the start vector $S$ with the end vector $E$. Finally, the
score of a candidate span from position $i$ to position $j$ is defined as
$S\cdot T_{i}+E\cdot T_{j}$, and the maximum scoring span where $j\geq i$ is
used as a prediction.

###  4.2 Database approach

The objective of proposing this baseline is to showcase which is the
performance of an ad-hoc method using heuristics and commercial software to
achieve the best possible performance. Since obtaining a human performance
analysis is near impossible because it would mean that the people involved in
the experiment should check more than $14k$ documents for each question, we
see this baseline as a performance to beat in a medium-long term.

This approach also breakdown the task in the same retrieval and answering
stages. However, in this case the ranking of the results is binary rather
indicating if a document is relevant or not. For that, we first run a
commercial OCR over the document collection, extracting not only the
recognized text, but also the key-value relationship between the field names
and their values, including checkboxes. This is followed by a process to
correct possible OCR recognition errors for the fields with low variability
(field names, parties and reporting options) and normalize all the dates by
parsing them to the same format. Finally, we map the key-value pairs into a
database like data structure. At the time of answering a question, the fields
in the query are compared with those in the stored records. If all the
constraints are met, that document is considered relevant and is given a
confidence of $1$, while otherwise it is given a confidence of $0$. Finally,
the requested value in the question is extracted from the records of the
relevant documents.

It is very important to consider two relevant aspects on this baseline. First,
it is a very rigid method that does not allow any modification in the data and
therefore, is not generalizable at all. Moreover, it requires a preprocessing
that is currently done manually to parse the query from Natural Language to a
Structured Query Language (SQL).

##  5 Results

###  5.1 Evidences

To initially assess the retrieval performance of the methods, we first compare
two different commercial OCR systems that we are going to use for text
spotting, Google OCR [12] and Amazon Textract [2]. As reported in table 3 the
performance on text spotting with the latter OCR is better than Google OCR,
and is the only one capable of extracting the key-value relations for the
database approach. For this reason we use this as the standard OCR for the
rest of the text spotting baselines.

Retrieval method | MAP
---|---
Text spotting (google) | 71.62
Text spotting (textract) | 72.84
Database | 71.06
Table 3: Performance of different retrieval methods.

Compared to text spotting, the database retrieval average performance is
similar. However, as depicted in figure 3 we can appreciate that performs
better for all the questions but the number $11$ where it gets a MAP of $0$.
This is the result from the fact that the key-value pair extractor is not able
to capture the relation between some of the forms fields, in this case the
treasurer name, and consequently it catastrophically fails at retrieving
documents with specific values on those fields, one of the main drawbacks of
such rigid methods. On the other hand, the questions where the database
approach shows a greater performance gap are those where in order to find the
relevant documents the methods must search not only documents with a
particular value, but understand more complex constraints such as the ones
described in section 3.1.2, which are finding documents between two dates
(question 9), after a date (question 18), documents that do not contain a
particular value (question 12), or where several values are considered as
correct (question 14).

Figure 3: Evidence retrieval performance of the different methods reported by
each question in the test set.

###  5.2 Answers

For the BERT QA method we use the pretrained weights bert-large-uncased-whole-
wordmasking-finetuned-squad from the Transformers library [35]. This is a
pretrained model finetuned on SQuAD 1.1 question answering task consisting on
more than $100,000$ questions over $23,215$ paragraphs. Then, we finetune it
again on the DocVQA dataset for 2 epochs following [23] to teach the model
reason about document concepts as well as adapting the new context style
format. Finally, we perform a third finetunning phase on the DocCVQA sample
set for $6$ epochs. Notice that the sample set is specially small and during
these $6$ epochs the model only see around $80$ samples. Nonetheless, this is
sufficient to improve the answering performance without harming the previous
knowledge.

Given the collection nature of DocCVQA, the answer to the question usually
consists on a list of texts found in different documents considered as
relevants. In our case, we consider a document as relevant when the confidence
provided for the retrieval method on that document is greater than a
threshold. For the text spotting methods we have fixed the threshold through
an empirical study where we have found that the best threshold is 0.9. In the
case of the database approach, given that the confidence provided is either 0
or 1, we consider relevant all positive documents.

In the experiments we use the BERT answering baseline to answer the questions
over the ranked documents from the text spotting and the database retrieval
methods. But we only use the database method to answer the ranked documents
from the same retrieval approach. As reported in table 4 the latter is the one
that performs the best. The main reason for this is that the wrong retrieval
of the documents prevents the answering methods to find the necessary
information to provide the correct answers. Nevertheless, the fact of having
the key-value relations allows the database method to directly output the
value for the requested field as an answer while BERT needs to learn to
extract it from a context that has partially lost the spatial information of
the recognized text when at the time of being created, the value of a field
might not be close to the field name, losing the semantic connection between
the key-value pair. To showcase the answering performance upper bounds of the
answering methods we also provide their performance regardless of the
retrieval system, where the documents are ranked according to the test ground
truth.

Retrieval | Answering | MAP | ANLSL
---|---|---|---
method | method
Text spotting | BERT | 72.84 | 0.4513
Database | BERT | 71.06 | 0.5411
Database | Database | 71.06 | 0.7068
GT | BERT | 100.00 | 0.5818
GT | Database | 100.00 | 0.8473
Table 4: Baselines results comparison.

As depicted in figure 4, BERT does not perform well when the answer are
candidate’s names (questions 8, 9, 11, 14 and 18). However, it has a better
performance when asking about dates (questions 16 and 17) or legislative
counties (question 10). On the other hand, the database approach is able to
provide the required answer, usually depending solely on whether the text and
the key-value relationships have been correctly recognized.

The most interesting question is the number 13, where none of the methods are
able to answer the question regardless of a correct retrieval. This question
asks if a candidate selected a specific checkbox value. The difference here is
that the answer is _No_ , in contrast to the sample question number 3. Then,
BERT can’t answer because it lacks of a document collection point of view, and
moreover, since it is an extractive QA method, it would require to have a _No_
in the document surrounded with some context that could help to identify that
word as an answer. On the other hand, the database method fails because of its
logical structure. If there is a relevant document for that question, it will
find the field for which the query is asking for, or will answer ’ _Yes_ ’ if
the question is a Yes/No type.

Figure 4: Answering performance of the different methods reported by each
question in the test set.

##  6 Conclusions and Future Work

This work introduces a new and challenging task to both the VQA and DAR
research fields. We presented the DocCVQA that aims to provide a new
perspective to Document understanding and highlight the importance and
difficulty of contemplating a whole collection of documents. We have shown the
performance of two different approaches. On one hand, a text spotting with an
extractive QA baseline that, although it has lower generic performance it is
more generic and could achieve similar performance in other types of
documents. And on the other hand, a baseline that represents the documents by
their key-value relations that despite achieving quite good performance, is
still far from being perfect and because of its design is very limited and
can’t generalize at all when processing other types of documents. In this
regard, we believe that the next steps are to propose a method that can reason
about the whole collection in a single stage, being able to provide the answer
and the positive evidences.

## Acknowledgements

This work has been supported by the UAB PIF scholarship B18P0070 and the
Consolidated Research Group 2017-SGR-1783 from the Research and University
Department of the Catalan Government.

## References

  * [1] Almazán, J., Gordo, A., Fornés, A., Valveny, E.: Word spotting and recognition with embedded attributes. IEEE transactions on pattern analysis and machine intelligence 36(12), 2552–2566 (2014)
  * [2] Amazon: Amazon textract (2021), https://aws.amazon.com/es/textract/, accessed on Jan 11, 2021
  * [3] Antol, S., Agrawal, A., Lu, J., Mitchell, M., Batra, D., Zitnick, C.L., Parikh, D.: Vqa: Visual question answering. In: Proceedings of the IEEE international conference on computer vision. pp. 2425–2433 (2015)
  * [4] Bansal, A., Zhang, Y., Chellappa, R.: Visual question answering on image sets. In: European Conference on Computer Vision. pp. 51–67. Springer (2020)
  * [5] Biten, A.F., Tito, R., Mafla, A., Gomez, L., Rusinol, M., Mathew, M., Jawahar, C., Valveny, E., Karatzas, D.: Icdar 2019 competition on scene text visual question answering. In: 2019 International Conference on Document Analysis and Recognition (ICDAR). pp. 1563–1570. IEEE (2019)
  * [6] Biten, A.F., Tito, R., Mafla, A., Gomez, L., Rusinol, M., Valveny, E., Jawahar, C., Karatzas, D.: Scene text visual question answering. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 4291–4301 (2019)
  * [7] Bojanowski, P., Grave, E., Joulin, A., Mikolov, T.: Enriching word vectors with subword information. Transactions of the Association for Computational Linguistics 5, 135–146 (2017)
  * [8] Coüasnon, B., Lemaitre, A.: Recognition of tables and forms (2014)
  * [9] Dengel, A.R., Klein, B.: smartfix: A requirements-driven system for document analysis and understanding. In: Lopresti, D., Hu, J., Kashi, R. (eds.) Document Analysis Systems V. pp. 433–444. Springer Berlin Heidelberg (2002)
  * [10] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidirectional transformers for language understanding. ACL (2019)
  * [11] Fan, C., Zhang, X., Zhang, S., Wang, W., Zhang, C., Huang, H.: Heterogeneous memory enhanced multimodal attention model for video question answering. In: Proceedings of the IEEE/CVF Conference on CVPR. pp. 1999–2007 (2019)
  * [12] Google: Google ocr (2020), https://cloud.google.com/solutions/document-ai, accessed on Dec 10, 2020
  * [13] Hu, R., Singh, A., Darrell, T., Rohrbach, M.: Iterative answer prediction with pointer-augmented multimodal transformers for textvqa. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (2020)
  * [14] Hull, J.J.: A database for handwritten text recognition research. IEEE Transactions on pattern analysis and machine intelligence 16(5), 550–554 (1994)
  * [15] Kafle, K., Price, B., Cohen, S., Kanan, C.: Dvqa: Understanding data visualizations via question answering. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 5648–5656 (2018)
  * [16] Kahou, S.E., Michalski, V., Atkinson, A., Kádár, Á., Trischler, A., Bengio, Y.: Figureqa: An annotated figure dataset for visual reasoning. arXiv preprint arXiv:1710.07300 (2017)
  * [17] Krishnan, P., Dutta, K., Jawahar, C.V.: Word spotting and recognition using deep embedding. In: 2018 13th IAPR International Workshop on Document Analysis Systems (DAS). pp. 1–6 (2018)
  * [18] Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. In: Soviet physics doklady. pp. 707–710. Soviet Union (1966)
  * [19] Liu, T.Y.: Learning to rank for information retrieval. Foundations and Trends in Information Retrieval 3(3), 225–331 (2009)
  * [20] Liu, X., Gao, F., Zhang, Q., Zhao, H.: Graph convolution for multimodal information extraction from visually rich documents. In: Proceedings of the 2019 Conference of the North American Chapter on Computational Linguistics. pp. 32–39
  * [21] Malinowski, M., Fritz, M.: A multi-world approach to question answering about real-world scenes based on uncertain input. arXiv preprint arXiv:1410.0210 (2014)
  * [22] Manmatha, R., Croft, W.: Word spotting: Indexing handwritten archives. Intelligent Multimedia Information Retrieval Collection pp. 43–64 (1997)
  * [23] Mathew, M., Karatzas, D., Jawahar, C.: Docvqa: A dataset for vqa on document images. In: Proceedings of the IEEE/CVF WACV. pp. 2200–2209 (2021)
  * [24] Mathew, M., Tito, R., Karatzas, D., Manmatha, R., Jawahar, C.: Document visual question answering challenge 2020. arXiv e-prints pp. arXiv–2008 (2020)
  * [25] Mouchère, H., Viard-Gaudin, C., Zanibbi, R., Garain, U.: Icfhr2016 crohme: Competition on recognition of online handwritten mathematical expressions. In: 2016 15th International Conference on Frontiers in Handwriting Recognition (ICFHR)
  * [26] Palm, R.B., Winther, O., Laws, F.: Cloudscan - a configuration-free invoice analysis system using recurrent neural networks. In: 2017 14th IAPR International Conference on Document Analysis and Recognition (ICDAR). pp. 406–413
  * [27] Rath, T.M., Manmatha, R.: Word image matching using dynamic time warping. In: 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings. vol. 2, pp. II–II. IEEE (2003)
  * [28] Ren, M., Kiros, R., Zemel, R.: Exploring models and data for image question answering. arXiv preprint arXiv:1505.02074 (2015)
  * [29] Schuster, D., et al.: Intellix – end-user trained information extraction for document archiving. In: 2013 12th ICDAR
  * [30] Siegel, N., Horvitz, Z., Levin, R., Divvala, S., Farhadi, A.: Figureseer: Parsing result-figures in research papers. In: ECCV. pp. 664–680. Springer (2016)
  * [31] Singh, A., Natarajan, V., Shah, M., Jiang, Y., Chen, X., Batra, D., Parikh, D., Rohrbach, M.: Towards vqa models that can read. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition
  * [32] Sudholt, S., Fink, G.A.: Evaluating word string embeddings and loss functions for cnn-based word spotting. In: 2017 14th IAPR International Conference on Document Analysis and Recognition (ICDAR). vol. 01, pp. 493–498 (2017)
  * [33] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, L., Polosukhin, I.: Attention is all you need. In: NIPS (2017)
  * [34] Wilkinson, T., Lindström, J., Brun, A.: Neural ctrl-f: Segmentation-free query-by-string word spotting in handwritten manuscript collections. In: 2017 IEEE International Conference on Computer Vision (ICCV). pp. 4443–4452 (2017)
  * [35] Wolf, T., et al.: Transformers: State-of-the-art natural language processing. In: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations. Association for Computational Linguistics
  * [36] Xu, Y., Li, M., Cui, L., Huang, S., Wei, F., Zhou, M.: Layoutlm: Pre-training of text and layout for document image understanding. p. 1192–1200. KDD ’20 (2020)
  * [37] Zhang, P., et al.: TRIE: End-to-End Text Reading and Information Extraction for Document Understanding, p. 1413–1422 (2020)