# VRDSynth: Synthesizing Programs for Multilingual Visually Rich Document
Information Extraction

Dat Nguyen  University of MelbourneMelbourneVICAustralia
<EMAIL_ADDRESS>,  Tung Do-Viet  Cinnamon AIHo Chi Minh
CityVietnam<EMAIL_ADDRESS>,  Hung Nguyen-Duy  Independent
ResearcherHanoiVietnam<EMAIL_ADDRESS>,  Tuan-Hai Luu  Cinnamon AIHo Chi
Minh CityVietnam<EMAIL_ADDRESS>,  Hung Le  Deakin
UniversityGeelongVICAustralia<EMAIL_ADDRESS>,  Bach Le  University of
MelbourneMelbourneVICAustralia<EMAIL_ADDRESS>and  Patanamon (Pick)
Thongtanunam  University of MelbourneMelbourneVICAustralia
<EMAIL_ADDRESS>
(Date: July. 2024)

###### Abstract.

Businesses often need to query visually rich documents (VRDs), e.g., purchase
receipts, medical records, and insurance forms, among many other forms from
multiple vendors, to make informed decisions. As such, several techniques have
been proposed to automatically extract independent entities of interest from
VRDs such as extracting price tags from purchase receipts, etc. However, for
extracting semantically linked entities, such as finding corresponding price
tags for each item, these techniques either have limited capability in
handling new layouts, e.g., template-based approaches, or require extensive
amounts of pre-training data and do not perform well, e.g., deep-learning
approaches.

In this work, we introduce a program synthesis method, namely VRDSynth, to
automatically generate programs to extract entity relations from multilingual
VRDs. Two key novelties, which empower VRDSynth to tackle flexible layouts
while requiring no pre-training data for extracting entity relations, include:
(1) a new domain-specific language (DSL) to effectively capture the spatial
and textual relations between document entities, and (2) a novel synthesis
algorithm that makes use of frequent spatial relations between entities to
construct initial programs, equivalent reduction to prune the search space,
and a combination of positive, negative, and mutually exclusive programs to
improve the coverage of programs.

We experiment on two popular VRD understanding benchmarks, namely FUNSD and
XFUND, on the semantic entity linking task, consisting of 1,592 forms in 8
different languages. VRDSynth, despite having no prior pre-training data,
outperforms the state-of-the-art pre-trained deep-learning approaches -
LayoutXLM, $\text{InfoXLM}_{Base}$ and $\text{XLMRoberta}_{Base}$ in 5, 6 and
7 out of 8 languages, respectively. Noticeably, in English, VRDSynth improves
42% of F1 score over LayoutXLM while being complementary to LayoutXLM in 7/8
languages. We further extend VRDSynth with automated table recognition, namely
$\textsc{VRDSynth}{}_{Table}$, and compare with $\text{InfoXLM}_{Large}$ and
$\text{XLMRoberta}_{Large}$. $\textsc{VRDSynth}{}_{Table}$ outperforms these
baselines on 4 out of 8 languages and in terms of average F1 score. VRDSynth
significantly improves the memory footprint required for program storage and
inference over all baselines (1M and 380MB versus that of 1.48GB and 3GB
required by LayoutXLM), while maintaining similar time efficiency despite the
speed differences between the languages used for implementation (Python vs
C++).

††conference: ACM SIGSOFT International Symposium on Software Testing and
Analysis; 16-20 September, 2024; Vienna, Austria

##  1\. Introduction

Businesses often have to collect and store information from various sources
for administrative tasks: from medical records, bills, purchase receipts, and
insurance forms to technical reports from different vendors. These
administrative documents often have various layouts with different visual
elements such as images, graphics, tables, diagrams, etc, and hence, they are
also called visually-rich documents (VRDs) (Iyer, ). A massive amount of data
today is stored in the form of VRDs as a way for business enterprises to
retain and exchange information. Often, businesses need to query this data to
make informed decisions, e.g., enterprises need to extract prices for sold
items from purchase receipts to claim credits for goods and services tax
(GST). This motivates several recent approaches that can automatically extract
useful information from VRDs (xu2019layoutlm, ; xu2021layoutlmv2, ;
huang2022layoutlmv3, ; Liu2019, ; Lohani2019, ; Sunder2019, ; Madashi2019, ;
dang2020msaupaf, ; Katti2018, ; Palm2018, ;
doctemplate_comp_blocks_HanchuanPeng2000, ;
doctemplate_comp_block_prj_Peng2001, ).

Information extraction from VRDs consists of two phases: recognition of
semantic entities and extraction of relations between entities (Jaume2019, ).
Semantic entity recognition consists of identifying which entity belongs to
which category while relation extraction identifies which value belongs to
which key. As an example, Figure 1 depicts the joint output of the two tasks:
given the set of entities (text and corresponding bounding box), semantic
entity recognition identifies which entity is header, key, or value (annotated
in yellow, blue and green bounding boxes, respectively), while relation
extraction links corresponding keys and value together. Both steps are
necessary to organize the extracted information. While the distinctive layouts
and visual features provide sufficient information for state-of-the-art
techniques such as (huang2022layoutlmv3, ; Xu2020LayoutXLMMP, ; Liu2019, ;
xu2019layoutlm, ; xu2021layoutlmv2, ; huang2022layoutlmv3, ; zhang2023reading,
) to perform reasonably in semantic entity recognition, semantic entity
linking between these key-and-values is still largely unaddressed (Jaume2019,
). On FUNSD (Jaume2019, ), BERT-based entity linking approach (Jaume2019, ),
which uses only textual features, achieved an F1 score, recall, and precision
of only 0.04, 0.99, and 0.02. This means that the approach can identify most
of the links, but the majority of them are false positives. On the
multilingual dataset, a state-of-the-art technique based on a large language
model, namely, LayoutXLM (Xu2020LayoutXLMMP, ) performs reasonably well on
key-value linking (0.6 to 0.7 for F1 score) but requires an extensive amount
of training data and memory footprint for storage and inference
(Xu2020LayoutXLMMP, ; Rogge2023, ). Furthermore, when reproduced in our
experiments on header-key linking, LayoutXLM performs worse.

On the other hand, program synthesis techniques, which make use of domain-
specific constraints provided by human experts, are capable of synthesizing
highly precise programs in data wrangling and information extraction, given a
limited amount of data (Gulwani2017, ; Gulwani2011FlashFill, ; Nye2019a, ;
Iyer, ). However, the VRD domain is different from the existing synthesis
works that operate on spreadsheets (Gulwani2011FlashFill, ; Gulwani2017, ;
Cambronero2023, ), sequence of text (Iyer, ), or semi-structured web pages or
pre-defined forms (Parthasarathy2022lrsyn, ). In general, VRDs are often
scanned, e.g., scanned purchase receipts, and thus, they are often noisy (see
Figure 1) due to the varying quality of the scanned versions. Because of this,
VRDs are considered much more challenging than the types of data that program
synthesis techniques can handle as mentioned above.

In this paper, we aim to develop a program synthesis technique, namely,
VRDSynth, to automatically extract semantic links from entities of interest
from VRDs. There are two key novelties that empower VRDSynth to tackle
flexible layouts while requiring no pre-training data in this entity-relation
extraction task, including (1) a new domain-specific language (DSL) to
effectively capture the spatial and textual relations between document
entities, and (2) a novel synthesis algorithm that efficiently and effectively
navigates through the search space to find high-quality candidate programs. To
achieve this, we represent each visually rich document as a collection of
entities and spatial relations between them. Each entity consists of a
bounding box location, the entity’s label (e.g., header, question, answer),
and its textual content. Note that the entity label can be obtained by any
entity recognizer, e.g., (Xu2020LayoutXLMMP, ; Qasim2019, ;
huang2022layoutlmv3, ). Next, spatial entity relations are built based on
spatial alignment (top, down, left, right) between the entities. We propose an
expressive DSL, which is a context-free grammar, that can effectively
represent these spatial and textual relations between entities while
maintaining the tractability of searching for programs that correctly locate
all pairs of linkable entities.

To synthesize such programs, we construct the specifications that describe
examples of pairs of related and unrelated entities obtained from the training
data, for which we use FUNSD and XFUND (Jaume2019, ; xu-etal-2022-xfund, ). We
note that this training data is different from the pre-training data used by
LayoutXLM for representation learning (Xu2020LayoutXLMMP, ). While both
LayoutXLM and VRDSynth require a training dataset, LayoutXLM also requires an
additional pre-training dataset, consisting of a large number of forms
annotated with bounding box and textual content but without either semantic
entity recognition or relation extraction labeling for representation
learning.

Finally, we propose a novel program synthesis algorithm for VRDSynth to
synthesize programs consistent with the DSL and the example-based
specifications extracted via the training data in the previous step. The
algorithm works in two phases: identifying initial programs and iteratively
refining programs. In the first stage, VRDSynth mines the frequent relations
between semantically linked entities from the training documents and uses
these frequent relations to construct initial programs that filter out
potential pairs of semantically linkable entities. Since these programs can
still be imprecise, VRDSynth further refines these programs by searching for
textual, label, position, or relation constraints that result in more precise
programs. During this search, VRDSynth makes use of equivalent reduction
(smith2019equivalentreduction, ) to prune the search space. At the end of each
iterative refinement step, VRDSynth combines positive, negative, and mutually
exclusive programs to produce more precise programs.

Figure 1. Example output of VRDSynth’s synthesized programs in different
layout: (a) List of key-value group, (b) key and long value, (c) list of key-
value (flat) (d) table and (e) header and key-value table. The programs
collectively link each corresponding key (e.g., names, fax) to corresponding
values or headers to corresponding keys. Note that we show the original images
to also demonstrate the problem of varying quality of scanned VRDs.

We evaluate VRDSynth on the semantic entity linking benchmark from FUNSD and
XFUND (Jaume2019, ; xu-etal-2022-xfund, ). These two datasets together consist
of 1,592 forms in 8 languages - English, German, French, Italian, Japanese,
Portuguese, and Chinese. On this benchmark, we show that even when requiring
no prior pre-training data, VRDSynth synthesized programs that outperform
LayoutXLM (Xu2020LayoutXLMMP, ), $\text{InfoXLM}_{Base}$ (chi-
etal-2021-infoxlm, ) and $~{}\text{XLMRoberta}_{Base}$ (conneau-
etal-2020-unsupervised, ) in terms of F1 score on 5, 6, and 7 out of 8
languages, respectively. In detail, these programs have consistently higher
precision than the all pre-trained models (0.732 versus 0.534 of the best
average precision baseline-LayoutXLM). Notably, in English, the F1 score of
VRDSynth is 42% higher than the the best baseline - LayoutXLM. To evaluate the
extensibility of VRDSynth for table relations, we further extended VRDSynth
with automated table recognition module TATR (smock2021tabletransformer, ),
resulting in $\textsc{VRDSynth}{}_{Table}$. We compare
$\textsc{VRDSynth}{}_{Table}$ with $\text{InfoXLM}_{Large}$ and
$\text{XLMRoberta}_{Large}$, which are the extensions of the base models.
Experiment results show that $\textsc{VRDSynth}{}_{Table}$ outperforms both
baselines in 4 out of 8 languages and in terms of average F1 score. In terms
of efficiency, VRDSynth requires significantly less memory than all baselines
to store and for inference. to store (1MB vs 1.48GB) and to run (380MB vs
3.04GB). VRDSynth achieve similar time efficiency to LayoutXLM despite being
implemented in Python instead of C++. We summarize the main contributions as
follows:

  * •

We present the VRDSynth framework that bridges the gap between deep learning
and program language for synthesizing programs to extract semantic entity
relations from visually rich documents.

  * •

We propose a novel domain-specific language (DSL) and a novel synthesis
algorithm that efficiently navigates the DSL’s program space by pruning and
sketching, in which sketches are obtained by mining patterns from training
data and pruning is achieved by equivalence reduction and combinations of
negative and mutually-exclusive programs.

  * •

We perform extensive evaluation and show that VRDSynth’s synthesized programs
outperform the pre-trained language model while being more efficient in terms
of memory footprints required.

##  2\. Related Works

To automatically extract information from documents with varied layouts, there
are three main directions: rule-based approach, deep learning-based approach,
and program synthesis.

Rule-based and template-based approach Traditional approaches in document
image processing makes use of heuristic rules
(doctemplate_comp_blocks_HanchuanPeng2000, ; Bukhari2009, ; Bukhari2011, ;
Ahn2017, ). These rules rely on carefully designed feature engineering, e.g.,
projection profile alignments (doctemplate_comp_blocks_HanchuanPeng2000, ),
similar words and box size and distances (Ahn2017, ; Bukhari2011, ) to
identify the desired document entities (ciravegna2001adaptive, ). Based on
these alignments, researchers (yujian2007normalized, ; Bukhari2011, ) have
shown that a template can also be built for each document form
(field_extraction_document_images_Rusinol2013, ). After building the template,
visual and textual features can be used to calculate the similarity between a
given template and a target document image, e.g., (chum2008near, ;
yujian2007normalized, ). Additionally, (d2018field, ) proposes a finer-grained
template using the combinations of TF-IDF, angle, and distance between
entities. While the rule-based and template-based methods perform well for a
fixed set of document formats, when there exist more varied document formats
from different business vendors, the management of these templates can become
intractable. Additionally, template-based approaches are also prone to varying
visual quality of documents, i.e., document images with low visual quality may
unduly be classified as new templates, rendering template-based approaches
imprecise. We aim to automatically aid developers in developing information
extraction rules by automatically synthesizing programs based on example input
document annotation. The synthesized rules can be seen as a matching template
for each entity.

Deep Learning-based Information Extraction More recently, deep learning has
also been applied for information extraction from visually rich documents.
(Palm2018, ) uses a recurrent neural network (RNN) to extract entities based
on their textual features. They ignored the contribution of image and layout
features and relied on the left-to-right reading order. (Katti2018, ) proposed
a new chargrid representation and used a convolutional neural network (CNN) to
segment the regions containing desired entities in the chargrid. Nevertheless,
2D chargrid or segmentation-based IE methods usually do not work in the case
of dense documents with little space between entities. Graph Convolution
Network (GCN) (kipf2016semi, ; hamilton2017inductive, ; dat2019towardsgnn, )
have also been applied for visually-rich document information extraction by
converting the input document into a document graph (Peng2017, ; song2018n, ;
Liu2019, ; Qasim, ; Qasim2019, ; Wang2019, ) and uses graph neural networks
for entity recognition by formulating the problem into node classification, in
which each entity is a node. For relation extraction, LayoutLMv2
(xu2021layoutlmv2, ) and LayoutLMv3 (huang2022layoutlmv3, ) are language-
specific versions that work only in English. Since we focus on multi-lingual
relation extraction, we use the state-of-the-art multi-lingual relation
extraction-LayoutXLM (Xu2020LayoutXLMMP, ) as the baseline. TPP
(zhang2023reading, ) re-formulate entity linking as token reading order and
utilizes transformers to predict these reading orders. While TPP is a
promising method for entity linking, it requires additional annotations, which
are not available and are not consistent with existing baselines and datasets.
Our work relies on the output of semantic entity recognition and the document
graph used by Qasim et al. (Qasim2019, ). However, we propose a new DSL along
with a synthesis algorithm for this domain.

Program Synthesis for Information Extraction Program synthesis has long been
used for different scenarios, ranging from programs handling primitive
operations (lezama2008sketch, ; Nye2019a, ), extracting information from
spreadsheets (Gulwani2011FlashFill, ; Gulwani2017, ; Cambronero2023, ),
sequences (Iyer, ), web data, PDF documents (mohamad2020, ; Sunder2019, ;
Parthasarathy2022lrsyn, ) and manipulating images (barnaby2023imageeye, ).
These works generally propose either a new domain-specific language or a new
technique for efficiently navigating the search space in synthesizing
programs. The closest works to ours are that of (Sunder2019, ; Iyer, ;
Parthasarathy2022lrsyn, ) and (barnaby2023imageeye, ). (Sunder2019, ) and
(Parthasarathy2022lrsyn, ) propose the usage of a transition system to extract
the desired entity from a starting entity that matches specific conditions
such as containing a word or lying on the left or right of a specific block.
(barnaby2023imageeye, ) proposed using a new DSL that involves the relation
between entities to localize the desired image regions. Our domain-specific
language also contains elements specifying the spatial relation between
entities as well as textual constraint (containing specific text or specific
character) like (Sunder2019, ; Parthasarathy2022lrsyn, ). However, we also
allow a more flexible scheme in specifying structural constraints between
elements. Particularly, while (Sunder2019, ) and (Parthasarathy2022lrsyn, )
only allow specifying a path, we allow specifying a graph as a relation
constraint between entities. Our DSL also allows interaction between programs
by union and exclusion of synthesized programs.

##  3\. Problem Definition

We give a brief definition of a symbolic representation of a document $D_{V}$
below, following Liu et al. (Liu2019, ).

###### Definition 0 (Symbolic Visually Rich Document)).

A document $D_{V}$ is conceptualized as an ensemble of entities denoted by
$D_{V}=\\{e_{1},e_{2},\ldots e_{N}\\}$, where $N$ is the total number of
entities in the documents. Each entity $e_{i}$ is a tuple of
$(e_{i}.\textbf{text},e_{i}.\textbf{pos},e_{i}.\textbf{lbl})$ where
$e_{i}.\textbf{text}$ is the textual content of the entity,
$e_{i}.\textbf{pos}$ is characterized by coordinates
$(e_{i}.\textbf{x}_{0},e_{i}.\textbf{y}_{0},e_{i}.\textbf{x}_{1},e_{i}.\textbf{y}_{1})$
denotes the rectangular bounds of the entity, originating from the starting
coordinate $(e_{i}.\textbf{x}_{0},e_{i}.\textbf{y}_{0})$ to its conclusive
boundary at $(e_{i}.\textbf{x}_{1},e_{i}.\textbf{y}_{1})$ and
$e_{i}.\textbf{lbl}$ is the predicted label of each entity from semantic
entity recognition task.

To facilitate the ground for synthesizing relational rules on these visually
rich documents, we use $e_{i}.\textbf{center}$ to denote the center
$(\frac{e_{i}.\textbf{x}_{0}+e_{i}.\textbf{x}_{1}}{2},\frac{e_{i}.\textbf{y}_{0}+e_{i}.\textbf{y}_{1}}{2})$.
We also build a set of relations $D_{R}=\\{(r_{ij})\\}$ following Qasim
(Qasim2019, ). Each relation $r_{ij}$ is a directed spatial relation between
two entities $e_{i}=r_{ij}\textbf{.from}$ and $e_{j}=r_{ij}.\textbf{to}$ in
$D_{V}$ along with a relation type $r_{ij}.\textbf{lbl}$ that is either top,
down, left, right, denoting the spatial alignments between entities.

Given this definition of symbolic visually rich document, we define the task
of semantic entity linking in Definition 3.2.

###### Definition 0 (Semantic Entity Linking).

Given a Symbolic VRD $D_{V}$ as defined in Definition 3.1, the Semantic Entity
Linking outputs a set of connections, $\mathcal{L}$, between pairs of elements
$(e_{i},e_{j})\in D_{V}\times D_{V}$ such that $e_{j}$ has semantic
connections (i.e., is key, value or subheader of) $e_{i}$.

In the context of visually rich documents, the “connection” in semantic entity
linking refers to the relational information embedded within the document
elements. These connections are not spatial or sequential linkages but are
semantic associations that define the hierarchy of information in the
document.

For instance, consider a form in Figure 3: the two entities “Event Name” and
“The USQ Spring Festival” have a semantic association: The former is the
question (i.e., key) while the latter is the answer. Similarly, in the same
form, a section titled “Special Event Information Sheet” has associations with
its sub-sections (e.g., “General Information” and “Hours”), which are
semantically linked as they elaborate on the broader “Special Event
Information Sheet” category. The problem of identifying these relationships is
called semantic entity linking.

To formulate the input and output of program synthesis, we present a
formalization for semantic entity linking in the context of program synthesis.
Suppose we have a dataset consisting of instances of symbolic visually rich
documents, each represented as $D_{i}$ where $D_{i}=\\{e_{1},e_{2},\ldots
e_{N}\\}$ are elements defined in Definition 3.1, alongside with these
documents, we are provided with the semantic link between $L_{i}$ existing
elements, where each semantic link $(e_{j},e_{k})\in L_{i}$ is an ordered pair
of entities from $D_{i}$, indicating a directional relationship from one
element to another (i.e., $L_{i}\subseteq D_{i}\times D_{i}$). Semantic entity
linking aims to a synthesize program $P$, that can accurately identify the
relationships between different elements within these documents. The program
synthesis task can be formally expressed as follows:

(1) $\text{ Find }P\text{ s.t.
}\bigwedge\left\\{\begin{array}[]{l}\forall((e_{1},e_{2})\in
L_{i}),(e_{1},e_{2})\in P(D_{i})\\\ \forall((e_{1},e_{2})\not\in
L_{i}),(e_{1},e_{2})\not\in P(D_{i})\\\ \end{array}\right.$

Each synthesized program $P$ is a specific program that can output the
semantically linkable pairs, given a document $D_{i}$ as input.

In actual implementation, we encode the specifications in the form of a list
of pairs that are linked towards each other $M_{i}=\\{(e_{1},e_{2})\\}$.
$M_{i}$ would consist of all pairs of question-answer or header-
question/header-sub headers. Note that the specifications only made use of the
symbolic visually rich documents, while the relation between elements in the
document will later be used for the domain-specific language programs.

##  4\. Domain Specific Language

In this section, we explain in detail our proposed DSL - a context-free
grammar - that is specifically used to describe the search space of the
program synthesis task. In the domain of symbolic visually-rich documents, our
proposed grammar is engineered to be sufficiently expressive to enable
sophisticated operations and queries while maintaining the tractability of the
search space.

###  4.1. Grammar

We propose a DSL in Figure 2 and describe the syntax of the DSL below.

Programs and Sub-programs($P$): At the highest level, programs are either
Find, Union, or Exclude programs. To describe in a bottom-up manner, each Find
program can be regarded as a single query that returns linkable pairs. All
three types of programs return linkable pairs. Union programs aggregate
results from multiple sub-programs, and Exclude programs filter out results of
a specific program (first argument) from another program (second argument).

$\displaystyle\begin{array}[]{lcl}P&\coloneq&\emptyset\,|\,\textbf{Union}(\\{P\\})\,|\,\textbf{Exclude}(P,P)\,|\\\
&&\textbf{Find}(\\{V_{set}\\},\\{R_{set}\\},C,\\{V_{set}\\})\\\
C&\coloneq&\textbf{And}(C,C)\,|\,\textbf{Not}(C)\,|\,PC\\\
PC&::=&\textbf{Rel}(V,R,V)\,|\,LblC\,|\,StrC\,|\,FloatC\,|\,\textbf{True}\,|\,\textbf{False}\\\
LblC&::=&VLabel==VLabel\,|\,RLabel==RLabel\\\
StrC&::=&\textbf{Eq}(Str,Str)\,|\,\textbf{Contain}(Str,Str)\\\
FloatC&::=&F<F\,|\,F>F\\\
VLbl&::=&V\textbf{.label}\,|\,\textbf{Header}\,|\,\textbf{Question}\,|\,\textbf{Answer}\\\
RLbl&::=&R\textbf{.label}\,|\,\textbf{Left}\,|\,\textbf{Right}\,|\,\textbf{Top}\,|\,\textbf{Down}\\\
Str&::=&V.\textbf{text}\,|\,\textbf{``.''}\,|\,\textbf{``/''}\,|\,\textbf{``:''}\,|\,\textbf{``-''}\\\
F&::=&RFloatProp\,|\,VFloatProp\,|\,FConst\\\ RFloatProp&::=&R.\textbf{mag}\\\
VFloatProp&::=&V.\textbf{x0}\,|\,V.\textbf{x1}\,|\,V.\textbf{y0}\,|\,V.\textbf{y1}\\\
V_{set}&::=&V\,|\,V,V_{set}\\\ R_{set}&::=&R\,|\,R,R_{set}\\\
V&::=&v_{0}\,|\,v_{1}\,|\,\dots\,|\,v_{10}\\\
R&::=&r_{0}\,|\,r_{2}\,|\,\dots\,|\,r_{10}\\\
F&::=&\mathbf{0}\,|\,\mathbf{0.1}\,|\,\mathbf{0.2}\,|\,\dots\,|\,\mathbf{1.0}\\\
\end{array}$ Figure 2. VRDSynth’s proposed DSL

As an atomic program among these three, each Find program takes as input 4
arguments: The list of symbolic entity variables (i.e., first $V_{set}$), the
list of relation variables (i.e., the first $R_{set}$), the condition to
filter these $C$, and the return set (i.e., the second $V_{set}$ or we would
call $V_{set\\_return}$). Given sets of potential variables set $V_{set}$ and
relation variable set $R_{set}$ define the space of possible entities and
relations that can be queried: each variable $v\in V_{set}$ can be bound to
any entity and each relation variable $r\in R_{set}$ can be bound to any
relation. Among all the possible entities and relations in the input document,
Find programs filter out the entities and relations that do not match the
input condition $C$. Finally, in the matched set of relations and entities,
Find programs return linkable pairs. These pairs are constructed by taking the
binding of $v_{0}$ (a special variable that is always in $V_{set}$) and all
entities that can be bound to any variable in $V_{set\\_return}$. Here is a
stepwise breakdown of the process:

  * •

Binding Exploration Initially, the Find program performs a comprehensive
search where it explores all possible bindings of elements from $V_{set}$ and
relationships from $R_{set}$ within the entire space of the document. The
result of binding exploration is the set of all possible binding $B$.

  * •

Condition Verification Among the found set, Find filters the unique cases
where the condition $C$ holds true.

  * •

Resulting Set Accumulation Finally, among these bindings Find collects the
valuations of variables that belong to $V_{set\\_return}$.

Thus, Find programs return a set of linkable pairs.

Conditions $C$ are recursively defined, grounding on base cases ($PC$) and
complex constructs involving logical operations (And, Not) and property
comparisons within elements and their relationships, such as Rel for
relationship properties, or direct comparisons of labels, strings, and
numerical attributes using $LblC$, $StrC$, and $FloatC$, respectively.

The label constraints $LblC$ make use of either the predicted word labels or
relation labels to filter the possible valuation of entities $V$ and relations
$R$. These constraints dictate which label each binding entity should have.

The float constraints $FloatC$ perform comparisons between float properties of
entities and relations. These constraints are mainly used to incorporate
layout features into the synthesized programs.

The string constraints, $StrC$, focus on the textual content within the
visually rich documents. These constraints allow for direct comparison of text
strings, encompassing operations like checking equality or verifying if a
particular substring is contained within an element’s text. This part of the
DSL is particularly crucial for searching for elements containing certain
keywords, phrases, or syntactic patterns.

The $V$ and $R$ variables represent entities and relationships in the
document, respectively. Each entity can be associated with various properties,
including labels ($VLbl$), textual content ($Str$), and numerical attributes
($F$), enabling a wide range of queries and operations based on these
characteristics. Relationships, denoted by $R$, describe the connections or
relative orientations between different entities, providing crucial context
for understanding the document’s structure and semantics.

The DSL also specifies sets of these entities and relationships ($V_{set}$ and
$R_{set}$), allowing operations to be performed over groups of items. These
sets enable batch processing of elements, such as selecting multiple entities
that meet certain criteria or applying transformations to several related
elements simultaneously.

Extension of VRDSynth’s grammar for handling tables One of the key advantages
in program synthesis is the flexibility to leverage domain-knowledge and tools
via an extension of the DSL. We note that datasets used in our experiments
contain tables that have varying forms. To deal with this, we extended
VRDSynth by using a domain-specific module, namely, the table recognition
module from TATR (smock2021tabletransformer, ). We name this variant
$\textsc{VRDSynth}{}_{Table}$. This extension can easily be adopted by
extending one grammar rule from the DSL from Figure 2:

(2)
$RLbl::=R\textbf{.label}\,|\,\textbf{Left}\,|\,\textbf{Right}\,|\,\textbf{Top}\,|\,\textbf{Down}\,|\,\textbf{Row}\,|\,\textbf{Col}$

Here, Row and Col are literals denoting the same row and same column
relations. We construct these relations by using the output of TATR
(smock2021tabletransformer, ).

###  4.2. Denotational Semantics of the DSL

In this Section, we describe the denotational semantics of our DSL. We first
describe the semantic domains of the DSL, followed by describing each
evaluation rule in a bottom-up manner.

Semantic Domains The denotational semantics of the DSL uses the following
domains: (1) $D_{P}$ is the domain of all possible programs, (2) $D_{C}$ is
the domain of conditions (3) $D_{V}$ is the domain of visual elements in a
document, (4) $D_{R}$ is the domain of relationships between visual elements,
(5) $D_{Set}$ is the domain of sets of visual elements and (6) $D_{Bool}$ is
the domain of boolean values {true, false}.

Semantic Rules for Programs The interpretation of programs is defined
recursively based on the program’s structure. Below we denote the semantics of
the DSL programs. The semantic of Find relies on evaluating the potential
bindings of (e.g., possible elements that can be assigned to) each relation
and variable. Thus, we define valuation function pair $\langle
b_{v},b_{r}\rangle$ as a function that assigns values to variables and
relationships:

(3) $b_{v}:V\to D_{V}\quad b_{r}:R\to D_{R}$

We denote the valuation of $v$ given binding $b$ as $[\\![v]\\!]_{b}$ and
valuation of $r$ given binding $b$ as $[\\![r]\\!]_{b}$:

(4) $\displaystyle[\\![V]\\!]_{b}=b_{v}(V)$
$\displaystyle[\\![R]\\!]_{b}=b_{r}(R)$ (5)
$\displaystyle[\\![V.\textbf{text}]\\!]_{b}=[\\![V]\\!]_{b}.\textbf{text}$
$\displaystyle[\\![V.\textbf{lbl}]\\!]_{b}=[\\![V]\\!]_{b}.\textbf{lbl}$ (6)
$\displaystyle[\\![V.\textbf{x}_{0}]\\!]_{b}=[\\![V]\\!]_{b}.\textbf{x}_{0}$
$\displaystyle[\\![V.\textbf{x}_{1}]\\!]_{b}=[\\![V]\\!]_{b}.\textbf{x}_{1}$
(7)
$\displaystyle[\\![V.\textbf{y}_{0}]\\!]_{b}=[\\![V]\\!]_{b}.\textbf{y}_{0}$
$\displaystyle[\\![V.\textbf{y}_{1}]\\!]_{b}=[\\![V]\\!]_{b}.\textbf{y}_{1}$
(8) $\displaystyle[\\![R.\textbf{lbl}]\\!]_{b}=[\\![R]\\!]_{b}.\textbf{lbl}$
(9)
$\displaystyle[\\![R.\textbf{mag}]\\!]_{b}=\left\|[\\![R]\\!]_{b}.\textbf{from}.\textbf{center}-[\\![R]\\!]_{b}.\textbf{to}.\textbf{center}\right\|_{1}$

Where $\|\cdot\|$ is the $L_{1}$ norm between two positions. The semantic
function $[\\![\cdot]\\!]_{b}$ maps syntactic constructs (e.g., conditions) to
their semantic (e.g., truth values) under a binding $b$. For a condition $C$,
$[\\![C]\\!]_{b}$ is true or false depending on whether $C$ holds under $b$.
We describe the semantics of evaluating conditions in a bottom-up manner
below:

(10) $\displaystyle[\\![\textbf{And}(C_{1},C_{2})]\\!]_{b}$
$\displaystyle=[\\![C_{1}]\\!]_{b}\land[\\![C_{2}]\\!]_{b}$ (11)
$\displaystyle[\\![\textbf{Not}(C)]\\!]_{b}$
$\displaystyle=\textbf{not}([\\![C]\\!]]_{b})$ (12)
$\displaystyle[\\![\textbf{Rel}(V_{1},R,V_{2})]\\!]_{b}$
$\displaystyle=([\\![V_{1}]\\!]_{b},[\\![V_{2}]\\!]_{b})==[\\![R]\\!]_{b}$
(13) $\displaystyle[\\![VLabel_{1}==VLabel_{2}]\\!]_{b}$
$\displaystyle=([\\![VLabel_{1}]\\!]_{b}==[\\![VLabel_{2}]\\!]_{b})$ (14)
$\displaystyle[\\![RLabel_{1}==RLabel_{2}]\\!]_{b}$
$\displaystyle=([\\![RLabel_{1}]\\!]_{b}==[\\![RLabel_{2}]\\!]_{b})$ (15)
$\displaystyle[\\![F_{1}<F_{2}]\\!]_{b}$
$\displaystyle=([\\![F_{1}]\\!]_{b}<\\![F_{2}]\\!]_{b})$ (16)
$\displaystyle[\\![Str_{1}==Str_{2}]\\!]_{b}$
$\displaystyle=[\\![Str_{1}]\\!]_{b}==[\\![Str_{2}]\\!]_{b}$ (17)
$\displaystyle[\\![\textbf{Contains}(Str_{1},Str_{2})]_{b}$
$\displaystyle=[\\![Str_{1}]\\!]_{b}\supseteq[\\![Str_{2}]\\!]_{b}$

Finally, let $B$ be the obtained set of all possible bindings from the binding
exploration step, where a single binding $b=\langle b_{v},b_{r}\rangle$ is a
function pair that assigns every variable in $V$ or relation in $R$ to a
corresponding value or relation, such that for each $v\in V$ and $r\in R$,
$b_{v}(v)\in D_{V}$ and $b_{r}(r)\in D_{R}$. Given that the inner components
of the Find programs are defined, the semantic of Find program can be defined
over this set of all possible bindings $B$:

(18)
$[\\![\textbf{Find}(V_{set},R_{set},C,V_{set\\_return})]\\!]=\bigcup\left\\{\begin{array}[]{l}\textbf{result}(b,C,V_{set\\_return})\\\
|b\in B\end{array}\right\\}$

Where $\textbf{result}(b)$ is the set of values computed by applying the
constraint $C$ in the Find operation within the context of specific binding
$b$:

(19)
$\textbf{result}(b,C,V_{set\\_return})=\left\\{([\\![v_{0}]\\!]_{b},[\\![v]\\!]_{b})\left|\begin{array}[]{l}[\\![C]\\!]_{b}=\texttt{true}\\\
v\in V_{set\\_return}\end{array}\right.\right\\}$

Intuitively, each result is a linking pair between the binding of $v_{0}$ and
all variable $v$ in the return set $V_{set\\_return}$. The notation
$[\\![C]\\!]_{b}$ represents the evaluation of condition $C$ given $b$ as the
binding defined above. Intuitively, a Find program would gather all possible
bindings of each variable and relations in $V_{set}$ and $R_{set}$ and
identify the bindings that match the condition $C$. After obtaining the set of
valid bindings, Find aggregates the valuation of variables belonging to the
$V_{set\\_return}$.

Finally, given the semantics definition of the non-recursive Find program,
Union and Exclude programs can be recursively defined as below:

(20)
$\displaystyle[\\![\textbf{Union}(P1,P2)]\\!]=[\\![P1]\\!]\cup[\\![P2]\\!]$
(21)
$\displaystyle[\\![\textbf{Exclude}(P1,P2)]\\!]=[\\![P1]\\!]\setminus[\\![P2]\\!]$

In which $P_{1}$ and $P_{2}$ can be either a Find program or recursively,
Union and Exclude programs themselves. In Section 5, we give an example of an
actual program in this DSL.

##  5\. Motivating Example

Figure 3. An example of a synthesized program that links (1) header to
subheader, (2) header to keys, and (3) key to value.

This section presents a motivating example that uses a specific program in the
DSL to link entities. Consider the event organization form in Figure 3, where
each entity is assigned with a corresponding label:“Special Event Information
Sheet” is the header, “General Information” is also a header, and under this
header there exists three keys and three values. We aim to link each header to
the corresponding subheaders, each subheader to the corresponding keys, and
each key to the corresponding values.

To provide a clear understanding of how one might tackle this challenge
programmatically, we introduce a program depicted in Figure 3b. This program
links all pairs that satisfy either one of the three sub-programs. The first
Find sub-program links between header and subheader, the second program links
between header and corresponding keys, and the final program links between
keys and value. The results of these programs are combined to get the final
results.

All the three programs shares the variable set $\\{v_{0},v_{1}\\}$ and
relation variable set $\\{r_{0}\\}$. Each variable can be mapped to a
corresponding entity, i.e., $e\in D_{V}$, and each relation variable can be
mapped to corresponding relations, i.e., $(e_{i},e_{j})\in D_{R}$, in
Definition 1. Initially, without any constraint, all variables and relation
variables can be bound to any entity and relations. With added constraints,
such as $v_{0}.\textbf{lbl}==\textbf{Header}$ (variable $v_{0}$ has to have
label Header), the space of possible binding $B$ is pruned. In our case, the
third argument of the Find program is the constraint to prune this search
space. For header linking programs, this condition prunes the possible
bindings of variables and relations. In detail, it requires four sub-
conditions: there must exist a relation between the valuation of $v_{0}$ and
$v_{1}$ (i.e., entities that bind to variable $v_{0}$ and $v_{1}$).
Furthermore, this relation has to have the label Down. The entities that can
be bound to $v_{0}$ and $v_{1}$ must have label Header. Furthermore, $v_{0}$’s
text must not contain a colon while $v_{1}$ does to avoid linking headers of
the same levels. We specifically save $v_{0}$ as the initial entity to be
linked with. This means that for every found binding, $v_{0}$ is the starting
entity in which we want to link every valuation of the $V_{set\\_return}$
with. In this case, for every binding, we would link the valuation of $v_{0}$
and $v_{1}$. In this example, “Special Event Information Sheet” is linked to
“General Information” and “Hours”.

For header-question (header to key), we have an Exclude program, specifying
that we want to find a set of links that satisfies the first program but avoid
the links that model the second program: The first Find program dictates that
header-linking should link two entities $v_{0}$, $v_{1}$ corresponding to
Header and Question (Key) label, but avoid the keys that belong to the other
headers in the program. “General Information” can be linked towards “Event
Name”, “Event Location” and “Event Dates” but not towards “Monday-Friday” and
“Saturday-Sunday” since they already belong to another header (Hour). Since
the first program’s results cannot include the second program, we call the
second Find program mutually exclusive program of the first find program.

Finally, the third program links corresponding keys and values. Particularly,
it links each key to the value on the right of it, given that the distance is
sufficiently small ($r_{0}.\textbf{mag}<0.2$), where $0.2$ is the ratio on the
page’s maximum dimension (width or height).

##  6\. Synthesizing Programs for VRD Information Extraction

Taking as input the set of documents $\\{D\\}$ along with the corresponding
specifications $\\{M\\}$, our goal is to synthesize a single final that
precisely links the entities following the specifications. For this, we first
construct a relation set $D_{R}$ for each document $D$, in which $D_{R}$
consists of all relations between entities in $D$. We construct a document
graph $G=\langle D,D_{R}\rangle$ for each document to represent the relations
between entities. Our synthesis algorithm, listed in Algorithm 1, takes these
graphs as input along with the corresponding specifications and synthesizes a
set of positive programs (i.e., programs that output correct link) and
negative programs (i.e., programs that output incorrect links and should be
avoided) and combine them to create the final program.

Due to the expressive power of our designed DSL, the search space for
candidate programs may be large. Our synthesis algorithm effectively navigates
the search space by (1) _sketching_ in which we start with a set of initial
programs, (2) _iterative refinement_ via equivalence reduction with term-
rewriting to avoid searching for equivalent programs, and mutually exclusive
programs to increase accuracy and recall. We describe these steps in detail
below.

Result: Synthesized programs based on the specified grammar

Input: Graph dataset $\\{G\\}$, Specs $\\{M\\}$, Grammar $grammar$

Output: List of synthesized positive programs $PP$ and negative programs $NP$

$P\leftarrow$ GetInitialPrograms$(\\{G\\},\\{M\\})$ (Algorithm 2);

$VS\leftarrow$ CreateVersionSpace($P$, $\\{G\\},\\{M\\}$);

$PP,NP\leftarrow\\{\\},\\{\\}$;

for  _$i=1$ to $maxIterations$_ do

$VS,PP^{*},NP^{*}\leftarrow$ RefinePrograms($VS$) (Algorithm 3);

$PP\leftarrow PP\cup PP^{*}$ $NP\leftarrow NP\cup NP^{*}$;

return _$PP,NP$_ ;

Algorithm 1 Overall Program Synthesis

###  6.1. Construction of Initial Programs

Recall that the search space can be large due to the expressive power of our
DSL, and thus, our goal is to effectively restrict the search space by
automatically constructing a set of initial programs, from which our synthesis
procedure mutates and evolves to find high-quality candidate programs
consistent with the provided specifications. These initial programs provide
useful clues for our synthesis procedure to start the search in a more
effective way.

Result: List of initial find programs

Input: List of document graph $\\{G\\}$ and corresponding list of
specifications $\\{M\\}$

Output: List of synthesized programs $P$

$\text{Initialize an empty list of programs }P\leftarrow\\{\\}$;

$\text{Initialize an empty list of paths }\Pi\leftarrow\\{\\}$;

foreach  _$G_{i},M_{i}\in\\{G\\},\\{M\\}$_ do

foreach  _$e_{j},e_{k}\in M_{i}$_ do

$\Pi\leftarrow\Pi\cup\textsc{GetAllPaths}(G_{i},e_{j},e_{k},2))$;

foreach  _$\pi\in\Pi$_ do

$V_{set},R_{set},Rel_{set},V_{map}\leftarrow\\{\\},\\{\\},\\{\\},\\{\\}$;

$rcnt$, $vcnt$, $\textbf{v}_{last}\leftarrow 0,0,\textbf{v}_{0}$;

foreach  _$(e_{i},e_{j})\in\pi$_ do

if  _$e_{i}\not\in V_{map}$_ then

$V_{map}[e_{i}]\leftarrow\textbf{v}_{vcnt}$;

$V_{set}\leftarrow V_{set}\cup\\{\textbf{v}_{vcnt}\\}$, $vcnt\leftarrow
vcnt+1$;

if  _$e_{j}\not\in V_{map}$_ then

$V_{map}[e_{j}]\leftarrow\textbf{v}_{vcnt}$;

$V_{set}\leftarrow V_{set}\cup\\{\textbf{v}_{vcnt}\\}$, $vcnt\leftarrow
vcnt+1$;

$R_{set}\leftarrow R_{set}\cup\\{\textbf{r}_{rcnt}\\}$;

$Rel_{set}\leftarrow
Rel_{set}\cup\\{\textbf{Rel}(V_{map}[e_{i}],\textbf{r}_{rcnt},V_{map}[e_{j}])\\}$;

$rcnt\leftarrow rcnt+1$, $\textbf{v}_{last}\leftarrow V_{map}[e_{j}]$;

$RelC\leftarrow\textsc{ConstructRelationConstraint}(Rel_{set})$;

$P\leftarrow
P\cup\\{\textbf{Find}(V_{set},R_{set},RelC,\\{\textbf{v}_{last}\\})\\}$;

Algorithm 2 Constructing Initial Find Programs

Our key intuition in automatically constructing the initial programs is that
these programs should cover as much as possible all the links between entities
specified in the specifications. To achieve this, we extract the common set of
relationships from the document dataset $\\{G\\}$ as a set of paths between
all pairs of entities and create the initial programs from these paths. Note
that these paths over-approximate the relationships between entities, i.e., a
path from one entity to another does not necessarily mean there is a
relationship between them. Despite false positives potentially induced by
these paths, initial programs constructed from the paths provide a good
starting point for our synthesis algorithm to later on iteratively refine. We
provide a formal definition of path in Definition 6.1. For all collected
paths, we construct the corresponding Find programs from these paths (See
Algorithm 2).

###### Definition 0.

Let $G=\\{(D_{V},D_{R})\\}$ be a document graph where $D_{V}$ is a symbolic
visually rich document defined in Definition 3.1 and $D_{R}$ is the spatial
relation set between $D_{V}$’s entities. A path $\pi$ from a starting entity
$s$ to an ending entity $t$ is a sequence of $\\{e_{1},e_{2},\ldots,e_{n}\\}$,
where $e_{1}=s$ and $e_{n}=t$, and each consecutive pair $(e_{i},e_{i+1})$
forms an edge in $D_{R}$.

After this step, we obtain the set of initial Find programs consisting of only
variables, relational variables, and relation constraints between the
variables. While these programs can cover a large amount of linking between
entities, they are not precise (i.e., they might link wrong entities) since
the conditions have yet to be refined. Next, based on these programs, we
systematically refine programs with respect to the specifications.

###  6.2. Iterative Refinement of Programs

The initial programs can be imprecise since they lack additional structural
and textual constraints. In this step, we iteratively refine the programs to
find high-quality candidates. The refinement algorithm is defined in Algorithm
3. Each iteration starts with the current set of programs and the search is
performed by first converting the current condition $C$ in the Find program
into a conjunction of $C$ and an unknown condition $\textbf{And}(C,\square)$.
We enumerate possible candidates to fill in the hole while making use of
equivalence reduction to avoid enumerating redundant programs. Among the
enumerated candidates, we keep three types of programs: the more precise
programs for the next iterations, the perfect positive programs (that output
all correct pairs), and the negative programs (that output all pairs of
entities that should not be linked). At the end of each iteration, we also
extend the set of positive programs by combining positive, negative, and
mutually exclusive programs. Below, we describe in detail each component.

Equivalence reduction with term rewriting. To prune the space of possible
programs in the enumeration phase, we leverage equivalent reduction
(smith2019equivalentreduction, ) in the form of term rewriting rules below.
These rules are applied in a bottom-up manner to all the enumerated programs
and help filter out redundant candidates.

$\displaystyle\textbf{And}(A,A)\leadsto A\quad\textbf{And}(A,\textbf{False})$
$\displaystyle\leadsto\textbf{False}\quad\textbf{And}(A,\textbf{True})\leadsto
A$ $\displaystyle F<F\leadsto\textbf{False}$ $\displaystyle\quad
F>F\leadsto\textbf{False}$
$\displaystyle\textbf{Contains}(S,S)\leadsto\textbf{True}$
$\displaystyle\quad\textbf{Equal}(S,S)\leadsto\textbf{True}$ $\displaystyle
V\textbf{.label}==V\textbf{.label}\leadsto\textbf{True}$ $\displaystyle\quad
R\textbf{.label}==R\textbf{.label}\leadsto\textbf{True}$ $\displaystyle
V\textbf{.x0}<V\textbf{.x1}\leadsto\textbf{True}$ $\displaystyle\quad
V\textbf{.x1}<V\textbf{.x0}\leadsto\textbf{False}$ $\displaystyle
V\textbf{.y0}<V\textbf{.y1}\leadsto\textbf{True}$ $\displaystyle\quad
V\textbf{.y1}<V\textbf{.y0}\leadsto\textbf{False}$

Precision-oriented program selection. The ultimate goal of our approach is to
synthesize programs that can precisely capture the semantic relationship
between entities as stated in Section 3. We formalize this goal and our
detailed refinement process below.

Given a graph dataset $\\{G\\}$ and a specification $\\{M\\}$ on this graph
dataset, for each program $p$, we collect the set of all possible bindings
that satisfy the condition of $p$ as $B_{p}$. Among all bindings in $B_{p}$,
we further divide them into two sets $B_{p}^{+}$ and $B_{p}^{-}$. $B_{p}^{+}$
denotes the set of bindings that models the original specifications (i.e.,
$\forall b\in B_{p}^{+},\forall\textbf{v}_{ret}\in
V_{set\\_return},(b[\textbf{v}_{0}],b[\textbf{v}_{ret}])\in M$), and
$B_{p}^{-}$ denotes the set of bindings that do not model the specifications.
We can calculate the precision of the program by counting all the linked
entities within $B_{p}^{+}$ and $B_{p}^{-}$:

(22) $prec(B_{p}^{+},B_{p}^{-})=|B_{p}^{+}|/(|B_{p}^{+}|+|B_{p}^{-}|)$

Our observation is that, given an initial And constraint, any additional
constraints will reduce either or both $B_{p}^{+}$ and $B_{p}^{-}$. Thus, we
keep adding the constraints that improve the precision of the program. For
every Find program $p$, let $\\{C\\}$ be the set of constraints that has yet
to appear in $p$ and is valid towards $p$.

To keep track of programs performing similarly, we keep version spaces of
programs that have similar $B_{p}^{+}$ and $B_{p}^{-}$ (i.e.,
$VS:\langle\mathcal{P}(B),\mathcal{P}(B)\rangle\to\mathcal{P}(D_{P})$), where
$\mathcal{P}$ denotes power sets). To further avoid synthesizing redundant
programs, we keep track of the set of covered specifications (i.e.,
$\bigcup_{p}B_{p}^{+}$) and only accept candidates that cover a yet-covered
part of specifications for further extension.

Generating additional positive programs by using mutually exclusive programs.
While enumerating, we also keep track of perfect-positive programs (that only
output correct pairs of linked entities) and perfect-negative programs (only
output pairs of entities that should not be linked). At the end of each
iteration, we collect additional perfect program set $PP^{*}$, the set of
perfect negative programs $NP^{*}$ (programs that only give examples that do
not match the specification), and the set of new version space with improved
precision. These positive programs and negative programs cover the perfect set
$PCover$ and $NCover$, respectively. In practice, we also observe the mutually
exclusive property between certain entities. For example, in Figure 3, in the
header-key linking, we can express the rule “find the key below target header,
but does not belong to another header” as an exclude program of two Find
programs.

Result: Refined Program and Version Spaces

Input: Version spaces $VS$

Output: List of perfect programs $PP^{*}$, perfect negative programs $NP^{*}$
and version spaces $VS^{*}$

$Cover,PCover,NCover=\\{\\},\\{\\},\\{\\}$;

$VS^{*},PP^{*},NP^{*}\leftarrow\\{\\},\\{\\},\\{\\}$;

foreach  _$B_{p}^{+},B_{p}^{-},p\in VS$_ do

if  _$B_{p}^{+}\setminus Cover=\emptyset$_ then

continue;

foreach  _condition $C$ based on grammar_ do

$B_{p}^{+*},B_{p}^{-*}\leftarrow\textsc{Filter}(B_{p}^{+},C),\textsc{Filter}(B_{p}^{-},C)$;

$p^{*}\leftarrow\textsc{AddConstraint}(p,C)$;

if  _$B_{p}^{+*}\setminus PCover\neq\emptyset$ and $B_{p}^{-*}=\emptyset$_
then

$PP^{*}\leftarrow PP^{*}\cup\\{p^{*}\\}$;

$PCover\leftarrow PCover\cup B_{p}^{+*}$;

$Cover\leftarrow Cover\cup B_{p}^{+*}$;

continue;

if  _$B_{p}^{+*}\setminus Cover\neq\emptyset$ and
$prec(B_{p}^{+*},B_{p}^{-*}>prec(B_{p}^{+},B_{p}^{-}$_ then

$Cover\leftarrow Cover\cup B_{p}^{+*}$;

$VS^{*}[B_{p}^{+}*,B_{p}^{-}*]\leftarrow
VS^{*}[B_{p}^{+}*,B_{p}^{-}*]\cup\\{p^{*}\\}$;

if  _$B_{p}^{+*}=\emptyset\text{ and }B_{p}^{-*}\setminus
NCover\neq\emptyset$_ then

$NP^{*}\leftarrow NP^{*}\cup\\{p^{*}\\}$;

$NCover\leftarrow NCover\cup B_{p}^{-*}$;

$EPCover\leftarrow\\{\\}$;

$p_{u}\leftarrow\textbf{Union}(\\{PP*\\}\cup\\{NP*\\})$;

foreach  _$B_{p}^{+},B_{p}^{-},p\in VS$_ do

if  _$B_{p}^{-}\setminus(PCover\cup NCover)$ and $B_{p}^{+}\setminus
PCover\not\eq\emptyset$_ then

$PP^{*}\leftarrow PP^{*}\cup\textbf{Exclude}(p,p_{u})$;

$EPCover\leftarrow EPCover\cup B_{p}^{+}$;

$PCover\leftarrow EPCover\cup PCover$;

foreach  _$B_{p}^{+},B_{p}^{-},p\in VS^{*}$_ do

if  _$B_{p}^{+}\setminus PCover=\emptyset$_ then

$VS^{*}\leftarrow VS^{*}\setminus\\{(B_{p}^{+},B_{p}^{-},p)\\}$;

Algorithm 3 Refine Programs

Finally, to construct the final program, we perform union on all of these
positive sub-programs $PP$ and exclude the union of all negative sub-programs
$NP$:

$p_{final}:=\textbf{Exclude}(\textbf{Union}(pp\in PP),\textbf{Union}(np\in
NP))$

##  7\. Experiment

We implement VRDSynth in Python with over 7,000 lines of code. The experiments
are performed on a computer equipped with AMD Ryzen Threadripper PRO 3995WX,
with 128 GB of RAM and with RTX 4090 GPU with 24GB of VRAM. We set the maximum
synthesis time of VRDSynth to be 2 hours on all tasks. Since the programs can
be synthesized offline, this can be seen as analogous to training time for
machine learning models.

Benchmark. We evaluate VRDSynth on semantic entity linking task on the FUNSD
(Jaume2019, ) and XFUND (xu-etal-2022-xfund, ) datasets. These two datasets
contain 1,592 forms in 8 languages: English (en), German (de), French (fr),
Spanish (es), Italian (it), Japanese (ja), Portuguese (pt), and Chinese (zh).
For each language, this benchmark consists of 199 scanned and annotated forms
from various domains, in which $149$ forms are used for training and $50$
forms for testing.

Baselines. We compare VRDSynth with three state-of-the-art pre-trained
multilingual document understanding models: LayoutXLM (Xu2020LayoutXLMMP, ),
InfoXLM (chi-etal-2021-infoxlm, ), and XLMRoberta (conneau-
etal-2020-unsupervised, ). These are the best-performing models in extracting
question-answer relations from multilingual visually rich documents on FUNSD
and XFUND benchmarks. Since the original evaluation (Xu2020LayoutXLMMP, ) only
focuses on question-answer linking, to allow these models to support the full
benchmark consisting of both header-question and question-answer, we needed to
extend the original data processing step to also include the header-question
relations for finetuning and evaluation111As reflected in our replication
package, the relevant code is found in the file layoutlm_re/xfund/xfund.py,
lines 225–239. The rest of the code is unchanged.. The released models are
only pre-trained models (layoutxlm-base-pretrained, ; infoxlm-base-pretrained,
; xlm-roberta-base-pretrained, ; infoxlm-large-pretrained, ; xlm-roberta-
large-pretrained, ) (i.e., only producing the probability of each word
appearing in the document). Thus, a fine-tuning process is required to use
them for semantic entity linking. We fine-tuned the baselines following the
reported settings in (GitHubIssue5862023, ) and set the number of optimization
steps to 40,000. We obtained comparable results to the original benchmark (See
Table 1).

We do not compare VRDSynth with any program synthesis baselines because, to
the best of our knowledge, there exists no prior work on program synthesis
that can be directly applied in this domain and problem settings.

Comparisons of $\textsc{VRDSynth}{}_{Table}$ with extended baselines. We
compare $\textsc{VRDSynth}{}_{Table}$, which is the extension of VRDSynth for
handling tables (described in Section 4), with the extended versions of the
baselines, namely $\text{InfoXLM}_{Large}$ and $\text{XLMRoberta}_{Large}$.
These large models extend their base counterparts by doubling the number of
layers.

Accuracy Evaluation. The dataset provides all documents with semantic
relations between entities. We measure the accuracy of our approach and the
baseline using precision, recall, and F1-score. We consider the identified
relation to be correct if it is specified in the benchmark dataset and
incorrect otherwise.

Replication Package:  To support reproducibility, we provide the open-source
code, documentation, and running scripts for all experiments with
aforementioned settings at https://doi.org/10.5281/zenodo.10386861

###  7.1. RQ1: Effectiveness of VRDSynth and its Extension

Table 1. Comparison of Performance between VRDSynth and LayoutXLM, Prec., Rec. are abbreviations for precision and recall. EN, DE, ES, FR, IT, JA, PT, and ZH stand for English, German, Spanish, French, Italian, Japanese, Portuguese, and Chinese respectively. VRDSynth+LayoutXLM is using VRDSynth in conjunction with LayoutXLM Method | Metrics | EN | DE | ES | FR | IT | JA | PT | ZH | Avg.
---|---|---|---|---|---|---|---|---|---|---
| Prec | 0.712 | 0.728 | 0.705 | 0.755 | 0.738 | 0.637 | 0.752 | 0.829 | 0.732
VRDSynth | Rec | 0.539 | 0.552 | 0.456 | 0.698 | 0.567 | 0.275 | 0.513 | 0.589 | 0.523
| F1 | 0.614 | 0.628 | 0.554 | 0.727 | 0.641 | 0.384 | 0.61 | 0.689 | 0.606
| Prec | 0.428 | 0.491 | 0.592 | 0.556 | 0.610 | 0.586 | 0.431 | 0.592 | 0.534
LayoutXLM | Rec | 0.438 | 0.715 | 0.788 | 0.745 | 0.765 | 0.747 | 0.742 | 0.796 | 0.717
| F1 | 0.433 | 0.582 | 0.676 | 0.637 | 0.679 | 0.656 | 0.545 | 0.679 | 0.610
| Prec | 0.193 | 0.442 | 0.458 | 0.414 | 0.542 | 0.585 | 0.296 | 0.559 | 0.436
$\text{InfoXLM}_{Base}$ | Rec | 0.150 | 0.642 | 0.715 | 0.681 | 0.681 | 0.694 | 0.608 | 0.641 | 0.602
| F1 | 0.169 | 0.532 | 0.558 | 0.515 | 0.604 | 0.635 | 0.399 | 0.597 | 0.501
| Prec | 0.240 | 0.407 | 0.422 | 0.367 | 0.470 | 0.515 | 0.208 | 0.476 | 0.388
$\text{XLMRoberta}_{Base}$ | Rec | 0.223 | 0.635 | 0.662 | 0.673 | 0.669 | 0.662 | 0.553 | 0.638 | 0.589
| F1 | 0.234 | 0.496 | 0.515 | 0.475 | 0.552 | 0.579 | 0.302 | 0.515 | 0.459
VRDSynth | Prec | 0.473 | 0.476 | 0.554 | 0.528 | 0.563 | 0.553 | 0.431 | 0.57 | 0.519
+LayoutXLM | Rec | 0.689 | 0.834 | 0.867 | 0.881 | 0.863 | 0.786 | 0.843 | 0.863 | 0.829
F1 | 0.562 | 0.606 | 0.677 | 0.66 | 0.682 | 0.649 | 0.571 | 0.687 | 0.637
| Prec | 0.735 | 0.757 | 0.716 | 0.748 | 0.740 | 0.665 | 0.749 | 0.829 | 0.742
$\textsc{VRDSynth}{}_{Table}$ | Rec | 0.593 | 0.577 | 0.449 | 0.718 | 0.563 | 0.292 | 0.511 | 0.605 | 0.539
| F1 | 0.657 | 0.655 | 0.552 | 0.733 | 0.640 | 0.405 | 0.607 | 0.700 | 0.619
| Prec | 0.355 | 0.615 | 0.626 | 0.601 | 0.629 | 0.582 | 0.466 | 0.709 | 0.573
$\text{InfoXLM}_{Large}$ | Rec | 0.298 | 0.679 | 0.737 | 0.713 | 0.732 | 0.732 | 0.636 | 0.716 | 0.655
| F1 | 0.324 | 0.646 | 0.677 | 0.652 | 0.677 | 0.645 | 0.537 | 0.712 | 0.609
| Prec | 0.375 | 0.602 | 0.594 | 0.540 | 0.628 | 0.615 | 0.431 | 0.686 | 0.559
$\text{XLM-Roberta}_{Large}$ | Rec | 0.272 | 0.681 | 0.743 | 0.660 | 0.726 | 0.742 | 0.622 | 0.712 | 0.645
| F1 | 0.315 | 0.639 | 0.661 | 0.594 | 0.674 | 0.673 | 0.510 | 0.699 | 0.596

We use the DSL defined in Section 4 for the base version of VRDSynth and
expand the relation label grammar rule as in equation 2 for
$\textsc{VRDSynth}{}_{Table}$ for all forms across 8 languages. For each
language, we use the training documents to synthesize a program and evaluate
the synthesized program on the test set. For LayoutXLM (Xu2020LayoutXLMMP, ),
InfoXLM (chi-etal-2021-infoxlm, ) and XLM-Roberta (conneau-
etal-2020-unsupervised, ), we use the training documents for fine-tuning the
pre-trained model and evaluate the fine-tuned model on the language’s test
set. Table 1 presents the precision, recall, and F1 score for both VRDSynth’s
synthesized program and pretrained models (Xu2020LayoutXLMMP, ; chi-
etal-2021-infoxlm, ; conneau-etal-2020-unsupervised, ).

Regarding the F1 score, VRDSynth outperforms LayoutXLM,
$\text{InfoXLM}_{Base}$ and $\text{XLMRoberta}_{Base}$ in 5, 6 and 7 out of 8
languages respectively. In all 8 languages, VRDSynth achieves better
precisions than the pre-trained language models. Among all languages, VRDSynth
achieved the highest F1 score (0.727) in French forms. Additionally, for
English forms, VRDSynth achieved 41.89%, 263.31% and 162.39% higher F1 score
than LayoutXLM, $\text{InfoXLM}_{Base}$ and $\text{XLMRoberta}_{Base}$,
respectively.

Using the table module to extend VRDSynth to $\textsc{VRDSynth}{}_{Table}$
further improves the performance of the synthesized programs in 5 languages:
English, Germany, French, Japanese, and Chinese. Additionally,
$\textsc{VRDSynth}{}_{Table}$ outperforms LayoutXLM, $\text{InfoXLM}_{Base}$
and $\text{XLMRoberta}_{Base}$ in 7 out of 8 languages. In comparison with
large models, $\textsc{VRDSynth}{}_{Table}$ achieved better average F1 score
and outperforms $\text{InfoXLM}_{Large}$ and $\text{XLMRoberta}_{Large}$ in 4
out of 8 languages.

We also explore a combination of the techniques that have highest precision
(VRDSynth) and highest recall (LayoutXLM). Particularly, we combine the
outputs of VRDSynth and LayoutXLM and exclude the negative programs of
VRDSynth, i.e., $(RE_{VRDSynth}\cup RE_{LayoutXLM})\setminus
RE_{VRDSynth\\_Neg}$, where: $RE_{LayoutXLM}=\\{(e_{i},e_{j})\\}$ indicating
$e_{i}$ should be semantically linked to $e_{j}$ by LayoutXLM.
$RE_{VRDSynth}=\\{(e_{i},e_{j})\\}$ indicating $e_{i}$ should be semantically
linked to $e_{j}$ by VRDSynth and $RE_{VRDSynth\\_Neg}=\\{(e_{i},e_{j})\\}$
indicating that $e_{i}$ and $e_{j}$ should not be linked together by VRDSynth.

Table 1 also presents the precision, recall, and F1 score of the combined
approach (VRDSynth \+ LayoutXLM) for each language. (VRDSynth+LayoutXLM)
achieves higher recall and F1 but lower precision than the individual
approaches. When we combine the outputs of two methods in this manner, since
the number of ground truth relations remains the same, the recall always
increases given the combined true positives (TP) from two methods. The
combined precision, however, may decrease with the increased false positives
(FP). As an example, in the case of Spanish (Es): VRDSynth’s TP, FP, and FN
(False Negatives) relations are: 483, 202, and 576 respectively with a
precision 0.705 and LayoutXLM’s TP, FP, and FN relations are: 815, 575, and
224 respectively with a precision 0.592. The combination VRDSynth+LayoutXLM’s
number of TP, FP, and FN relations are 918, 740 and 141 respectively with a
precision 0.554. This means that while LayoutXLM complements VRDSynth (hence,
the increased TP), it also adds more false negatives due to low precision
(large FP), resulting in the dropped precision. However, given the increased
recall, in terms of overall F1 score, this combination still outperforms both
VRDSynth and pre-trained language model baselines, and achieved the highest
average F1 score of 0.637.

RQ1 Conclusion: VRDSynth, without requiring pre-trained data or pre-training
procedure, achieved significantly higher average precision than all baselines
and outperformed LayoutXLM on 5 out of 8 languages in terms of F1 score.
$\textsc{VRDSynth}{}_{Table}$ improved VRDSynth’s performance in 5 languages,
outperformed all the base variants of pre-trained models in 7 out of 8
languages and large variants of pre-trained models on 4 out of 8 languages.

###  7.2. RQ2: Contribution of negative and mutually-exclusive sub-programs

VRDSynth makes use of both positive and negative sub-programs in the synthesis
procedure. To measure the contribution of negative programs, we perform a
comparison of synthesized programs’ performance before and after adding
negative/mutually exclusive programs in terms of F1 score in Figure 4.

Figure 4. Comparison between VRDSynth with
($\textsc{VRDSynth}{}\\_\text{Full}$) and without
($\textsc{VRDSynth}{}\\_\text{Pos}$) the usage of negative and mutually
exclusive sub-programs.

Results show a consistent improvement of the F1 score of VRDSynth in all
languages. In detail, we can see improvements of 2%, 5%, 9%, 1%, 7%, 6%, 8%,
3% on en, de, es, fr, it, ja, pt, and zh respectively. This constitutes an
overall improvement of 5% in terms of F1 score.

RQ2 conclusion: Joining programs give an overall improvement of 5% in F1
score. The highest improvement is 9% in Spanish.

Table 2. Inference time comparison of VRDSynth’s variants and baselines, all measurements are in seconds. Lang | $\textsc{VRDSynth}{}_{full}$ | $\textsc{VRDSynth}{}_{pos}$ | $\textsc{VRDSynth}{}_{Table}$ | LayoutXLM | $\text{InfoXLM}_{Large}$ | $\text{XLMRoberta}_{Large}$
---|---|---|---|---|---|---
Mean | Std. | Mean | Std. | Mean | Std. | Mean | Std. | Mean | Std. | Mean | Std.
En | 1.68 | 1.27 | 0.64 | 0.495 | 4.49 | 8.28 | 1.88 | 0.41 | 4.56 | 1.01 | 3.07 | 0.68
De | 3.71 | 2.96 | 0.86 | 0.69 | 19.81 | 47.53 | 2.45 | 0.85 | 5.54 | 2.00 | 3.67 | 1.33
Es | 5.23 | 2.57 | 1.27 | 0.63 | 10.59 | 23.65 | 2.80 | 1.02 | 6.28 | 2.43 | 4.18 | 1.63
Fr | 3.91 | 3.45 | 0.80 | 0.56 | 8.13 | 28.44 | 2.68 | 1.17 | 6.17 | 2.57 | 4.13 | 1.73
It | 4.99 | 3.30 | 1.12 | 0.75 | 20.82 | 64.92 | 3.42 | 1.33 | 7.94 | 3.15 | 5.32 | 2.12
Ja | 2.87 | 2.71 | 1.07 | 1.02 | 5.77 | 8.64 | 4.99 | 2.46 | 6.03 | 2.23 | 4.03 | 1.51
Pt | 5.76 | 6.23 | 1.34 | 1.42 | 24.38 | 47.17 | 3.20 | 1.19 | 7.24 | 2.56 | 4.84 | 1.72
Zh | 5.06 | 2.434 | 1.13 | 0.54 | 42.61 | 59.22 | 4.35 | 1.99 | 5.94 | 2.34 | 3.93 | 1.56
Avg. | 4.15 | 2.95 | 1.03 | 0.76 | 17.08 | 35.98 | 3.22 | 1.30 | 6.21 | 2.29 | 4.14 | 1.54
Table 3. Storage and memory efficiency of VRDSynth’s variants and pre-trained language models | $\textsc{VRDSynth}{}_{full}$ | $\textsc{VRDSynth}{}_{pos}$ | $\textsc{VRDSynth}{}_{Table}$ | LayoutXLM | $\text{InfoXLM}_{Large}$ | $\text{XLMRoberta}_{Large}$
---|---|---|---|---|---|---
Storage | 1020 KB | 424 KB | 2.68 MB | 1.48 GB | 2.24 GB | 2.24 GB
Memory | 380 MB | 378 MB | 1.20 GB | 3.04 GB | 5.40 GB | 4.34 GB

###  7.3. RQ3: Efficiency of VRDSynth

We measure the inference time and memory usage of VRDSynth’s variants -
$\textsc{VRDSynth}{}_{pos}$ and $\textsc{VRDSynth}{}_{full}$ (using only
positive programs and all programs, respectively) along with LayoutXLM. To
provide a precise comparison, we set the number of available CPU cores to 1
and do not use GPU.

####  7.3.1. RQ3.1. Inference time efficiency

We note down the mean and standard deviation of runtimes of the synthesized
programs generated by different variants of VRDSynth versus the baselines in
Table 2. VRDSynth inference time is 4.15 seconds on average, this speed is
better than $\text{InfoXLM}_{Large}$, while being comparable with
$\text{XLMRoberta}_{Large}$ and is slightly less efficient than LayoutXLM. The
positive-program-only version of VRDSynth is much more efficient, running on
an average of only 1 second per document. $\textsc{VRDSynth}{}_{full}$ is more
efficient than its extension, $\textsc{VRDSynth}{}_{Table}$ which takes on
average of 17.08 seconds for each form, due to additional same rows and
columns relations detected by the table module.

We note that VRDSynth’s inference is implemented in Python, while the
baselines are based on Pytorch, which is implemented in C++, thus, in future
implementation, it would be interesting to see the improvement in using C++
for executing VRDSynth’s synthesized programs.

####  7.3.2. RQ3.2. Memory efficiency

Table 3 summarizes efficiency of all techniques. VRDSynth requires only 1 MB
of storage and 380 MB of memory for inference, significantly lower than
LayoutXLM at 1.48GB for storage and 3.04GB for memory inference.
$\textsc{VRDSynth}{}_{Table}$, despite requiring more memory than VRDSynth, is
still significantly more efficient than all pre-trained model baselines and
requires only $2.68$ MB and $1.2$GB for storage and inference respectively,
versus 2.24 GB and 5.40 GB of the best baseline - $\text{InfoXLM}_{Large}$.

RQ3 Conclusion: VRDSynth has an average inference time comparable with pre-
trained models, despite being implemented in Python instead of C++. The
positive-program-only variant of VRDSynth \- $\textsc{VRDSynth}{}_{pos}$
runsthree times faster than LayoutXLM. The table variant
$\textsc{VRDSynth}{}_{Table}$, while performed the best, is less efficient
than the baselines. For memory efficiency, all variants of VRDSynth are more
efficient than the baselines.

##  8\. Threats to Validity

Threats to internal validity Relate to possible errors in our implementation
and experiments. We have rechecked our implementation and experiments and
fixed the errors that we have found. Still, there could be additional errors
that we did not notice. We have carefully constructed a replication package
and ensured that the exact commands and hyperparameters used for reproducing
the experiments are included.

Threats to external validity Correspond to the generalizability of our
findings. VRDSynth consists of two components: the DSL and the synthesis
algorithm. The DSL is designed based on various kinds of documents with
various languages so it should cover various structures, still, it is possible
that there exists specific documents where structures are not represented by
the DSL. Furthermore, the synthesis algorithm works by identifying subgraphs
from document graphs that match specific patterns in terms of structure and
properties. These patterns are initially mined from the dataset and then
iteratively extended. Thus, in the presence of long-distance and rare
relations, it will be hard to either discover this relationship with mining or
iterative refinement of programs. This problem is difficult for any approach
handling VRDs. We tried mitigating the threat on the generalizability of both
DSL and synthesis algorithm by experimenting on datasets containing varied
real-world documents such as FUNSD and XFUND. To further mitigate the former
threat, we also experimented with the extensibility of VRDSynth’s DSL to adopt
a domain-specific module to tackle table structures, namely,
$\textsc{VRDSynth}{}_{Table}$ without changing the synthesis algorithm,
however, it is still possible that the DSL might need to be extended again to
tackle even more challenging domains.

Threats to construct validity Correspond to the suitability of our evaluation
metrics. For RQ1 and RQ2, we measured the performance of all baselines using
well-known metrics- precision, recall and F1 score. For RQ3.1, we measured
both the mean and standard deviation of inference time in seconds for each
language and baseline. For RQ3.2, we measured both the maximum storage and
runtime memory of all baselines.

##  9\. Conclusion and Future Works

We introduced a synthesis-based approach towards visually rich document
understanding. In detail, we proposed a new expressive DSL enabling us to
represent programs that link entities based on spatial and textual
constraints. Using this DSL, we proposed a novel synthesis algorithm, VRDSynth
that efficiently synthesizes programs based on the DSL. The synthesized
programs outperformed LayoutXLM, the state-of-the-art in multi-language
document understanding, in 5 out of 8 languages in the joint benchmark of
FUNSD and XFUND. Our evaluation further shows that the technique of joining
and mutually excluding negative programs gives a boost in terms of synthesized
program effectiveness and that they are memory and computationally efficient.

In future works, we plan to leverage semantic embeddings for synthesizing more
concise programs.

## References

  * [1] Arun Iyer, Manohar Jonnalagedda, Suresh Parthasarathy, and Sriram Rajamani.  Synthesis and Machine Learning for Heterogeneous Extraction.
  * [2] Yiheng Xu, Minghao Li, Lei Cui, Shaohan Huang, Furu Wei, and Ming Zhou.  Layoutlm: Pre-training of text and layout for document image understanding, 2019.
  * [3] Yang Xu, Yiheng Xu, Tengchao Lv, Lei Cui, Furu Wei, Guoxin Wang, Yijuan Lu, Dinei Florencio, Cha Zhang, Wanxiang Che, Min Zhang, and Lidong Zhou.  LayoutLMv2: Multi-modal pre-training for visually-rich document understanding.  In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 2579–2591, Online, August 2021. Association for Computational Linguistics.
  * [4] Yupan Huang, Tengchao Lv, Lei Cui, Yutong Lu, and Furu Wei.  Layoutlmv3: Pre-training for document ai with unified text and image masking.  In Proceedings of the 30th ACM International Conference on Multimedia, 2022.
  * [5] Xiaojing Liu, Feiyu Gao, Qiong Zhang, and Huasha Zhao.  Graph Convolution for Multimodal Information Extraction from Visually Rich Documents.  2019\.
  * [6] D. Lohani, A. Belaïd, and Y. Belaïd.  An Invoice Reading System Using a Graph Convolutional Network.  pages 144–158. 2019.
  * [7] Vishal Sunder, Ashwin Srinivasan, Lovekesh Vig, Gautam Shroff, and Rohit Rahul.  One-shot Information Extraction from Document Images using Neuro-Deductive Program Synthesis.  jun 2019.
  * [8] Nguyen Dang Tuan Anh and Nguyen Thanh Dat.  End-to-End Information Extraction by Character-Level Embedding and Multi-Stage.  British Machine Vision Conference (BMVC), pages 1–12, 2019.
  * [9] Tuan Anh Nguyen Dang, Duc Thanh Hoang, Quang Bach Tran, Chih-Wei Pan, and Thanh Dat Nguyen.  End-to-end hierarchical relation extraction for generic form understanding.  In 2020 25th International Conference on Pattern Recognition (ICPR), pages 5238–5245, 2021.
  * [10] Anoop Raveendra Katti, Christian Reisswig, Cordula Guder, Sebastian Brarda, Steffen Bickel, Johannes Höhne, and Jean Baptiste Faddoul.  Chargrid: Towards Understanding 2D Documents.  2018\.
  * [11] Rasmus Berg Palm, Ole Winther, and Florian Laws.  CloudScan - A Configuration-Free Invoice Analysis System Using Recurrent Neural Networks.  In Proceedings of the International Conference on Document Analysis and Recognition, ICDAR, 2018.
  * [12] Hanchuan Peng, Fuhui Long, Wan-Chi Siu, Zheru Chi, and David Dagan Feng.  Document image matching based on component blocks.  In Proceedings 2000 International Conference on Image Processing (Cat. No.00CH37101), volume 22, pages 601–604 vol.2. IEEE, 2000.
  * [13] Hanchuan Peng, Fuhui Long, and Zheru Chi.  Document image recognition based on template matching of component block projections.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(9):1188–1192, sep 2003.
  * [14] Guillaume Jaume, Hazim Kemal Ekenel, and Jean-Philippe Thiran.  FUNSD: A Dataset for Form Understanding in Noisy Scanned Documents.  may 2019.
  * [15] Yiheng Xu, Tengchao Lv, Lei Cui, Guoxin Wang, Yijuan Lu, Dinei Florencio, Cha Zhang, and Furu Wei.  Layoutxlm: Multimodal pre-training for multilingual visually-rich document understanding.  2021\.
  * [16] Chong Zhang, Ya Guo, Yi Tu, Huan Chen, Jinyang Tang, Huijia Zhu, Qi Zhang, and Tao Gui.  Reading order matters: Information extraction from visually-rich documents by token path prediction.  arXiv preprint arXiv:2310.11016, 2023.
  * [17] Niels Rogge.  Fine-tune layoutxlm on xfund (relation extraction).  https://github.com/NielsRogge/Transformers-Tutorials/blob/master/LayoutXLM/Fine_tune_LayoutXLM_on_XFUND_(relation_extraction).ipynb, 2023\.  Accessed: 2023-12.
  * [18] Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, and Boston Delft.  Program Synthesis.  2017\.
  * [19] Sumit Gulwani.  Automating string processing in spreadsheets using input-output examples.  SIGPLAN Not., 46(1):317–330, jan 2011.
  * [20] Maxwell Nye, Luke Hewitt, Joshua Tenenbaum, and Armando Solar-Lezama.  Learning to Infer Program Sketches.  feb 2019.
  * [21] José Cambronero, Sumit Gulwani, Vu Le, Daniel Perelman, Arjun Radhakrishna, Clint Simon, and Ashish Tiwari.  Flashfill++: Scaling programming by example by cutting to the chase.  Proceedings of the ACM on Programming Languages, 7(POPL):952–981, January 2023.
  * [22] Suresh Parthasarathy, Lincy Pattanaik, Anirudh Khatry, Arun Iyer, Arjun Radhakrishna, Sriram K. Rajamani, and Mohammad Raza.  Landmarks and regions: a robust approach to data extraction.  In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation. ACM, June 2022\.
  * [23] Shah Rukh Qasim, Hassan Mahmood, and Faisal Shafait.  Rethinking Table Recognition using Graph Neural Networks.  may 2019.
  * [24] Yiheng Xu, Tengchao Lv, Lei Cui, Guoxin Wang, Yijuan Lu, Dinei Florencio, Cha Zhang, and Furu Wei.  XFUND: A benchmark dataset for multilingual visually rich form understanding.  In Findings of the Association for Computational Linguistics: ACL 2022, pages 3214–3224, Dublin, Ireland, May 2022. Association for Computational Linguistics.
  * [25] Calvin Smith and Aws Albarghouthi.  Program synthesis with equivalence reduction.  In Constantin Enea and Ruzica Piskac, editors, Verification, Model Checking, and Abstract Interpretation, pages 24–47, Cham, 2019. Springer International Publishing.
  * [26] Zewen Chi, Li Dong, Furu Wei, Nan Yang, Saksham Singhal, Wenhui Wang, Xia Song, Xian-Ling Mao, Heyan Huang, and Ming Zhou.  InfoXLM: An information-theoretic framework for cross-lingual language model pre-training.  In Kristina Toutanova, Anna Rumshisky, Luke Zettlemoyer, Dilek Hakkani-Tur, Iz Beltagy, Steven Bethard, Ryan Cotterell, Tanmoy Chakraborty, and Yichao Zhou, editors, Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 3576–3588, Online, June 2021. Association for Computational Linguistics.
  * [27] Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov.  Unsupervised cross-lingual representation learning at scale.  In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel Tetreault, editors, Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 8440–8451, Online, July 2020. Association for Computational Linguistics.
  * [28] Brandon Smock and Rohith Pesala.  Table Transformer, 06 2021.
  * [29] Syed Saqib Bukhari, Faisal Shafait, and Thomas Breuel.  Coupled Snakelet Model for Curled Textline Segmentation of Camera-Captured Document Images.  Proceedings of the 10th International Conference on Document Analysis and Recognition. International Conference on Document Analysis and Recognition (ICDAR-09), July 26-29, Barcelona, Spain, pages 61–65, 2009.
  * [30] Syed Saqib Bukhari, Faisal Shafait, and Thomas M Breuel.  High Performance Layout Analysis of Arabic and Urdu Document Images.  Icdar, pages 1275–1279, 2011.
  * [31] Byeongyong Ahn, Jewoong Ryu, Hyung Il Koo, and Nam Ik Cho.  Textline detection in degraded historical document images.  Eurasip Journal on Image and Video Processing, 2017(1), 2017.
  * [32] Dr Ciravegna et al.  Adaptive information extraction from text by rule induction and generalisation.  2001\.
  * [33] Li Yujian and Liu Bo.  A normalized levenshtein distance metric.  IEEE transactions on pattern analysis and machine intelligence, 29(6):1091–1095, 2007.
  * [34] Marcal Rusinol, Tayeb Benkhelfallah, and Vincent Poulain Dandecy.  Field extraction from administrative documents by incremental structural templates.  Proceedings of the International Conference on Document Analysis and Recognition, ICDAR, pages 1100–1104, 2013.
  * [35] Ondrej Chum, James Philbin, Andrew Zisserman, et al.  Near duplicate image detection: min-hash and tf-idf weighting.  In BMVC, volume 810, pages 812–815, 2008.
  * [36] Vincent Poulain d’Andecy, Emmanuel Hartmann, and Marçal Rusinol.  Field extraction by hybrid incremental and a-priori structural templates.  In 2018 13th IAPR International Workshop on Document Analysis Systems (DAS), pages 251–256. IEEE, 2018.
  * [37] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [38] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In Advances in neural information processing systems, pages 1024–1034, 2017.
  * [39] Thanh-Dat Nguyen, Thanh Le-Cong, ThanhVu H. Nguyen, Xuan-Bach D. Le, and Quyet-Thang Huynh.  Toward the analysis of graph neural networks.  In Proceedings of the ACM/IEEE 44th International Conference on Software Engineering: New Ideas and Emerging Results, ICSE-NIER ’22, page 116–120, New York, NY, USA, 2022. Association for Computing Machinery.
  * [40] Haoyuan Peng, Lu Liu, Yi Zhou, Junying Zhou, and Xiaoqing Zheng.  Attention-based Belief or Disbelief Feature Extraction for Dependency Parsing.  AAAI, (Zheng), 2018.
  * [41] Linfeng Song, Yue Zhang, Zhiguo Wang, and Daniel Gildea.  N-ary relation extraction using graph state lstm.  arXiv preprint arXiv:1808.09101, 2018.
  * [42] Shah Rukh Qasim, Hassan Mahmood, and Faisal Shafait.  Rethinking Table Parsing using Graph Neural Networks.  may 2019.
  * [43] Wenlin Wang, Zhe Gan, Hongteng Xu, Ruiyi Zhang, Guoyin Wang, Dinghan Shen, Changyou Chen, and Lawrence Carin.  Topic-Guided Variational Autoencoders for Text Generation.  mar 2019.
  * [44] Armando Solar-Lezama.  Program Synthesis by Sketching.  PhD thesis, USA, 2008.  AAI3353225.
  * [45] Mohammad Raza and Sumit Gulwani.  Web data extraction using hybrid program synthesis: A combination of top-down and bottom-up inference.  In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD ’20, page 1967–1978, New York, NY, USA, 2020\. Association for Computing Machinery.
  * [46] Celeste Barnaby, Qiaochu Chen, Roopsha Samanta, and Işıl Dillig.  Imageeye: Batch image processing using program synthesis.  Proc. ACM Program. Lang., 7(PLDI), jun 2023.
  * [47] Microsoft.  Layoutxlm-base.  https://huggingface.co/microsoft/layoutxlm-base.  Accessed: 2024-03-25.
  * [48] Microsoft.  Infoxlm-base.  https://huggingface.co/microsoft/infoxlm-base.  Accessed: 2024-03-25.
  * [49] FacebookAI.  Xlm-roberta-base.  https://huggingface.co/FacebookAI/xlm-roberta-base.  Accessed: 2024-03-25.
  * [50] Microsoft.  Infoxlm-large.  https://huggingface.co/microsoft/infoxlm-large.  Accessed: 2024-03-25.
  * [51] FacebookAI.  Xlm-roberta-large.  https://huggingface.co/FacebookAI/xlm-roberta-large.  Accessed: 2024-03-25.
  * [52] https://github.com/microsoft/unilm/issues/586, 2023.  Accessed: 2023-12.


and the orthogonal complement to the orbit consists of matrices of the form

$\begin{pmatrix}\lambda_{1}&0\\\ \lambda_{2}&\lambda_{1}\end{pmatrix}$

This means that there is a neighbourhood of $A$ such that any matrix can be
taken back to the normal form

$\begin{pmatrix}\lambda_{1}&1\\\ \lambda_{2}&\lambda_{1}\end{pmatrix}$

###  5.3. The Lie iteration in the homogeneous case

The classical Heron iteration for finding surds and Newton’s more general
root-finding iteration are quadratically convergent. The basic technical tool
we will introduce now is an iteration scheme similar (but different) to the
Newton iteration in the context of a Lie group action. To distinguish it from
the Newton iteration, we call it the Lie iteration. Its efficiency relies on
the following two facts:

  1. (1)

The Lie group and the Lie algebra agree at first order.

  2. (2)

The tangent space to the Lie group is isomorphic to the Lie algebra.

As we shall see, (1) implies that our iteration is quadratic, like for the
Newton method and (2) implies that we only need to linearise the map at the
identity, unlike the Newton method which requires global construction of
inverses.

Let us first assume that $V$ is infinitesimally $G$-homogeneous at a point
$a\in V$. This means that the infinitesimal action of the Lie algebra at $a$

$\rho:=d\sigma_{a}:\mathfrak{g}\longrightarrow V,\ \xi\mapsto\xi(a)$

is surjective. In this case the implicit function theorem tells us that $V$ is
locally $G$-homogeneous: for any $b\in V$ small enough, there exists $g\in G$
such that

$g(a)=a+b.$

The following iteration produces a sequence of elements in $G$ which converges
rapidly to $g$. It is determined by the choice of a linear map

$j:V\longrightarrow\mathfrak{g}$

that is a right inverse to the infinitesimal action, i.e

$\rho\circ j={\rm Id\,}.$

and the local isomorphism determined by the exponential map

$\textup{exp}:\mathfrak{g}\longrightarrow G,\;\;\;\xi\mapsto e^{\xi}\,.$

We start our iteration with:

$b_{0}:=b$

and define

$\xi_{0}:=j(b_{0}).$

The element

$e^{\xi_{0}}a$

is close to $a+b$ or equivalently

$e^{-\xi_{0}}(a+b)$

is close to $a$. The error of this approximation is

$b_{1}=e^{-\xi_{0}}(a+b)-a$

We set $\xi_{1}:=j(b_{1})$ and repeat the process. In this way we get
sequences $(b_{n}),(\xi_{n})$ which define the Lie iteration scheme in the
homogeneous case:

$\begin{matrix}\xi_{n}&=&j(b_{n})\\\
b_{n+1}&=&e^{-\xi_{n}}(a+b_{n})-a\end{matrix}$

Note that

$a+b_{n+1}=e^{-\xi_{n}}(a+b_{n})=e^{-\xi_{n}}e^{-\xi_{n-1}}(a+b_{n-1})=\dots=\prod_{i\geq
0}^{n}e^{-\xi_{i}}(a+b_{0}).$

and

$\xi_{n}(a)=d\rho_{a}(\xi_{n})=d\rho_{a}(j(b_{n}))=b_{n}$

###  5.4. Quadratic convergence of the Lie iteration

We want to control the rate of convergence of this iteration. To do this we
use the operator norm:

$\|\xi\|:=\sup_{x\in\mathbb{R}^{n}}\frac{\|\xi(x)\|}{\|x\|}.$

and observe that

$\log\|\prod_{i\geq 0}e^{\xi_{i}}\|\leq\log\prod_{i\geq
0}e^{\|\xi_{i}\|}=\sum_{i\geq 0}\|\xi_{i}\|.$

In particular:

######  Lemma 5.6.

Let $(\xi_{i})$ be a sequence of operators of a Banach algebra. The infinite
product $\prod_{i\geq 0}e^{\xi_{i}}$ is converges in the operator norm
provided that the sequence $(\|\xi_{i}\|)$ is summable.

The generalisation of this lemma to a more general situation will play a key
role in KAM theory. We want to apply the lemma, so we must evaluate the rate
of convergence of the sequence $(\xi_{n})$. As

$\displaystyle b_{n}$ $\displaystyle=\xi_{n}(a),$ $\displaystyle b_{n+1}$
$\displaystyle=e^{-\xi_{n}}(a+b_{n})-a,$

we obtain:

$b_{n+1}=e^{-\xi_{n}}(a+\xi_{n}(a))-a.$

or equivalently:

$b_{n+1}=(e^{-\xi_{n}}({\rm Id\,}+\xi_{n})-{\rm Id\,})(a).$

Thus the sequence $(\xi_{n})$ is obtained by iteration of the function:

$F=j\circ f,\ f(x)=e^{-x}(1+x)-1.$

Note that $f$ has a critical point at the origin:

$f(x)=(1-x)(1+x)-1+o(x^{2})=-x^{2}+o(x^{2}).$

In particular, by Taylor’s formula, there exists a neighbourhood of the origin
and a constant $C>0$ such that:

$\|f(\xi)\|\leq C\|\xi\|^{2}.$

We are in the classical situation of a quadratic iteration: If

$\|f(x)\|\leq C\|x\|^{2}$

then

$\|f(f(x))\|\leq C\|f(x)\|^{2}\leq C\cdot C^{2}\|x\|^{4}$ $\|f(f(f(x)))\|\leq
C\|f(f(x))\|^{2}\leq C\cdot C^{2}\cdot C^{4}\|x\|^{8}$

so that in general

$\|f^{(n)}(x)\|\leq C^{2^{n}-1}\|x\|^{2^{n}}=\frac{1}{C}(C\|x\|)^{2^{n}}$

and where $f^{(n)}$ denotes the $n$-th iterate of $f$.

So we see:

######  Theorem 5.7.

If $\|f(x)\|\leq C\|x\|^{2}$ and $\|x_{0}\|<1/C$, then the sequence of
iterates

$x_{n}:=f^{(n)}(x)$

converges rapidly to zero:

$\|x_{n}\|\leq\frac{1}{C}\rho^{2^{n}},\;\;\rho:=C\|x_{0}\|<1.$

######  Theorem 5.8.

Let $V$ be a finite dimensional vector space, $G\subset GL(V)$ a group acting
linearly on $V$ and $\mathfrak{g}$ its Lie-algebra, $a\in V$ a point. Assume
that the map

$\rho=d\sigma_{a}:\mathfrak{g}\longrightarrow V,\xi\mapsto\xi(a)$

admits an inverse $j$.

Then, for any $b\in V$ small enough, the Lie-iteration produces a rapidly
convergent sequence $(\xi_{n})$ of elements in $\mathfrak{g}$ such that

$a=\prod_{i\geq 0}e^{-\xi_{i}}(a+b).$

The classical Heron-Newton iteration is also quadratic, but it requires the
computation of a inverse to the differential at every new step. In the context
of a group action, we need only a single inverse $j$ to the infinitesimal
action. Also note that the quadraticity of the iteration scheme stems from the
fact that the Lie-group $G$ and the Lie-algebra $\mathfrak{g}$ ’agree up to
first order’. But it is also important to be aware of the fact that the Lie
iteration does neither require the group $G$, nor the fact that $\mathfrak{g}$
is its full Lie-algebra. This is especially important for the applications of
the iteration in infinite dimensional situations, as it is not necessary to
construct the complete group as an infinite dimensional manifold with tangent
space $\mathfrak{g}$.

###  5.5. The Lie iteration in the general case

We adapt our previous iteration to non-transitive actions. So let $G\subset
GL(V)$ be a Lie group acting naturally on the vector space $V$. Let $F$ be an
$\mathfrak{g}$-transversal at some point $a\in V$. By the implicit function
theorem, it is also a $G$-transversal.

Given $b\in V$, we want to find $g\in G$ and $\alpha\in F$ such that

$g(a+\alpha)=a+b$

To do so, we extend the infinitesimal action

$\rho:\mathfrak{g}\longrightarrow V,\;\;\;\xi\mapsto\xi(a)$

to a surjective map

$\rho_{a}:F\times\mathfrak{g}\longrightarrow
V,\;\;\;(\alpha,\xi)\mapsto\xi(a)+\alpha$

Let

$j_{a}:V\longrightarrow F\times\mathfrak{g}$

be a right inverse to $\rho_{a}$. We also put

$j:(a+F)\times V\longrightarrow F\times\mathfrak{g},\;\;\;(a+\alpha,b)\mapsto
j_{a+\alpha}(b)$

Our problem is now the following: given $b\in V$, we want to find $g\in G$ and
$\alpha\in F$ such that

$g(a+\alpha)=a+b$

To do so, we will modify the original iteration as follows. First we set
$b_{0}:=b$, $a_{0}:=a$ and then consider
$j(a_{0},b_{0})=(\alpha_{0},\xi_{0})$. Then $\alpha_{0}\in F$ and
$\xi_{0}\in\mathfrak{g}$ are elements such that

$b_{0}=\xi_{0}(a_{0})+\alpha_{0}$

Now the element $e^{\xi_{0}}(a_{0}+\alpha_{0})$ will be close to $a_{0}+b_{0}$
and we put

$\displaystyle a_{1}:=$ $\displaystyle a_{0}+\alpha_{0},$ $\displaystyle
b_{1}:=$ $\displaystyle e^{-\xi_{0}}(a_{0}+b_{0})-a_{1},$

We now can iterate this procedure and obtain sequences
$a_{n},b_{n},\alpha_{n},\xi_{n}$ defining the Lie iteration in the general
case:

$\begin{matrix}a_{n+1}:=&a_{n}+\alpha_{n},\\\
b_{n+1}:=&e^{-\xi_{n}}(a_{n}+b_{n})-a_{n+1},\\\
(\alpha_{n+1},\xi_{n+1}):=&j(a_{n+1},b_{n+1})\\\ \end{matrix}$

The last equation expresses the fact that at each step we have the
decomposition

$b_{n+1}=\xi_{n+1}(a_{n+1})+\alpha_{n+1}\;.$

Note that, just as in the iteration for the homogeneous case, one has

$a_{n+1}+b_{n+1}=e^{-\xi_{n}}(a_{n}+b_{n})=e^{-\xi_{n}}e^{-\xi_{n-1}}(a_{n-1}+b_{n-1})=\dots=\prod_{i\geq
0}^{n}e^{-\xi_{i}}(a+b)$

Let us now rewrite this as the iteration of a mapping. If we substitute the
relation

$b_{n}=\xi_{n}(a_{n})+\alpha_{n}\;.$

in

$b_{n+1}=e^{-\xi_{n}}(a_{n}+b_{n})-a_{n+1},$

we obtain:

$b_{n+1}=e^{-\xi_{n}}(a_{n}+\xi_{n}(a_{n})+\alpha_{n})-a_{n}-\alpha_{n}=\left(e^{-\xi_{n}}(a_{n}+\xi_{n}(a_{n}))-a_{n}\right)+\left(e^{-\xi_{n}}\alpha_{n})-\alpha_{n}\right).$

which can be written as

$b_{n+1}=A(\xi_{n},a_{n})+B(\xi_{n},\alpha_{n})$

where

$A(\xi,a)=(e^{-\xi}({\rm Id\,}+\xi)-{\rm Id\,})(a),\
B(\xi,\alpha)=(e^{-\xi}-{\rm Id\,})(\alpha)\;.$

Note that, for fixed $a$, both $A$ and $B$ have a quadratic singularity at
$\xi=0,\ \alpha=0$. From this we find

$(\alpha_{n+1},\xi_{n+1})=j(a_{n}+\alpha_{n},A(\xi_{n},a_{n})+B(\xi_{n},\alpha_{n}))$

The right hand side still involves $a_{n}$, so we write:

$(a_{n+1},(\alpha_{n+1},\xi_{n+1}))=(a_{n}+\alpha_{n},j(a_{n}+\alpha_{n},A(\xi_{n},a_{n})+B(\xi_{n},\alpha_{n})))$

The formula is a bit involved, but the only important point is that it is of
the form

$(x_{n+1},y_{n+1})=(x_{n}+Ly_{n},f(x_{n},y_{n}))$

where $L$ is a linear map and $f(x,-)$ is quadratic. In our situation, we have
$x_{n}=a_{n},y_{n}=(\alpha_{n},\xi_{n}),Ly_{n}=\alpha_{n}$, and, as we
observed:

$y\mapsto f(x,y)=j(x+Ly,A(x,y)+B(y))$

is quadratic.

We may adapt the fixed point theorem to this situation:

######  Theorem 5.9.

Let $E,F$ be Banach space and let

$F:B_{E}\times B_{F}\longrightarrow E\times F,\ (x,y)\mapsto(x+Ly,f(x,y))$

be such that there exists a constant $C$ with

$\|f(x,y)\|\leq C\|y\|^{2}$

for any $x\in B_{E}$. Let $y_{0}\in B_{F}$ be such that

$C\|y_{0}\|\leq 1\ {\rm\ and\ }\frac{\|L\|}{C}\sum_{n\geq
0}(C\|y_{0}\|)^{2^{n}}<1$

Then the sequence

$(x_{n},y_{n})=F^{n}(x,y),\ x_{0}=0$

converges to a limit $(l,0)$ and

$\|y_{n}\|\leq\rho^{2^{n}},\
\|x_{n}\|\leq\frac{\|L\|}{C}\sum_{i=1}^{n-1}\rho^{2^{i}}$

with $\rho=C\|y_{0}\|$.

###### Proof.

The proof is a small variation to the non-parametric case. As

$\|f(x,y)\|\leq C\|y\|^{2}$

we get that:

$\|y_{n}\|=\|f^{(n)}(x_{0},y_{0})\|\leq
C^{2^{n}-1}\|y_{0}\|^{2^{n}}=\frac{1}{C}(C\|y_{0}\|)^{2^{n}}$

and

$\displaystyle\|x_{n}\|$ $\displaystyle\leq\|L\|\,\|y_{n-1}\|+\|x_{n-1}\|$
$\displaystyle\leq\|L\|\,\|y_{n-1}\|+\|L\|\,\|y_{n-2}\|+\|x_{n-2}\|$
$\displaystyle\leq\dots$ $\displaystyle\leq\|L\|\sum_{i=1}^{n-1}\|y_{i}\|.$

∎

The main point of difference between the homogeneous and the parametric
iteration is that in the first case we need only a single right inverse to the
infinitesimal action at $a$. In the parametric situation one needs such a
right inverse at the complete sequence of points $a=a_{0},a_{1},\ldots$ lying
in the transversal slice. In practise this transversal consists of simple
modification of our initial problem and is well under control.

###  5.6. Bibliographical Notes

In his lectures on singularity theory, Arnold used Lie groups actions as a
preliminary step to the study of hypersurface singularities and their
deformations. The study of $GL(n,\mathbb{R})$ orbits was studied in:

Arnold V.I., On matrices depending on parameters, Russian Mathematical Surveys
26(2), 29-43, (1971).

Inspired by Kolmogorov’s invariant tori paper, the Lie iteration was
formulated by Moser in the absolute case in:

J. Moser, A rapidly convergent iteration method and non-linear partial
differential equations II, Ann. Scuola Norm Sup. Pisa - Classe di Scienze Sér.
3,20(3), 499-535, (1966).

see also:

J. Féjoz, J. and M. Garay., Un théorème sur les actions de groupes de
dimension infinie, Comptes Rendus à l’Académie des Sciences, 348, 427-430,
(2010).
M. Garay, An Abstract KAM Theorem, Moscow Math. Journal, Volume 14, Number 4,
p.745-772, (2014).

Moser does not treat normal forms as an application of his implicit function
theorems (now called Nash-Moser theorems). On the contrary, Moser noticed that
the requirement of these theorems are in general not fulfilled. When possible
application of implicit function theorems in the presence of small
denominators remains a non trivial problem. For instance, following an idea of
Herman this has been done by Bost for the case of the Kolmogorov theorem in:

J.-B. Bost, Tores invariants des systèmes dynamiques hamiltoniens, Sém.
Bourbaki 639, Astérisque, 133-134, p. 113- 157 (1986).

## Photo Credits

J. Moser by Konrad Jacobs, Erlangen (1969).