# A Categorical Representation Language and Computational System for
Knowledge-Based Robotic Task Planning

Angeline Aguinaldo1,2, Evan Patterson3, James Fairbanks4, William Regli1,
Jaime Ruiz4

###### Abstract

Classical planning representation languages based on first-order logic have
preliminarily been used to model and solve robotic task planning problems.
Wider adoption of these representation languages, however, is hindered by the
limitations present when managing implicit world changes with concise action
models. To address this problem, we propose an alternative approach to
representing and managing updates to world states during planning. Based on
the category-theoretic concepts of $\mathsf{C}$-sets and double-pushout
rewriting (DPO), our proposed representation can effectively handle structured
knowledge about world states that support domain abstractions at all levels.
It formalizes the semantics of predicates according to a user-provided
ontology and preserves the semantics when transitioning between world states.
This method provides a formal semantics for using knowledge graphs and
relational databases to model world states and updates in planning. In this
paper, we conceptually compare our category-theoretic representation with the
classical planning representation. We show that our proposed representation
has advantages over the classical representation in terms of handling implicit
preconditions and effects, and provides a more structured framework in which
to model and solve planning problems.

## Introduction

In robotic task planning, tracking all the implicit effects and relationships
in the world state can be very challenging, especially when working in complex
environments. As a result, planning systems often rely on heuristics and
simplifying assumptions, which can lead to suboptimal or even incorrect
solutions (Wilkins and DesJardins 2001; Gil 1990). To address these
challenges, researchers have sought to combine techniques from the fields of
knowledge representation and automated planning which has formed the subfield
called knowledge-based planning (Wilkins and DesJardins 2001). The goal of
this research is to develop more structured and efficient representations of
the world state that can capture the complex relationships and dependencies
that arise in real-world planning problems. For example, some approaches use
structured knowledge representations, such as ontologies (Kang and Choi 2009;
Beetz et al. 2018; Tenorth and Beetz 2017) and knowledge graphs (Amiri,
Chandan, and Zhang 2022; Galindo et al. 2008; Miao, Jia, and Sun 2023; Agia et
al. 2021), to model the world state. It is natural to conclude that knowledge-
based planning, as it stands, may be better suited to solve the problem of
tracking implicit preconditions and effects. On the contrary, knowledge-based
planning has not been widely adopted because it requires translating these
rich and complex representations into propositional facts so that they can be
interpreted using a classical planning languages like PDDL (Knoblock et al.
1998). Because of this, they become computationally intensive search problems
in the absence of search space reduction methods.

To address these concerns, we propose a world state representation based on
the category-theoretic concepts of $\mathsf{C}$-sets (Patterson, Lynch, and
Fairbanks 2021) and double-pushout (DPO) rewriting (Brown et al. 2021). Our
representation not only manages structured knowledge about the world state,
but also formalizes the semantics of predicates according to a user-provided
ontology, ensuring that the semantics of the world state are preserved and
implicit preconditions and effects are handled when transitioning between
states.

## Related Work

We foresee the nearest application of our approach as being robotic task
planning using scene graphs. Scene graphs are a specialized version of
knowledge graphs that restrict its elements, attributes, and relations to
facts obtained through vision-based perception and inference (Chang et al.
2023). In scene graphs, ontologies are often used to align scene data to class
hierarchies. In planning, these ontologies can be used to enrich facts in the
planning domain; however, these ontologies are often integrated in the
planning decisions in ad hoc ways. For example, Galindo et al present a two-
part knowledge representation system, which includes (i) spatial information
about the robot environment in the form of a scene graph, and (ii) an ontology
that describes the hierarchical relationships between concepts (Galindo et al.
2008). A function mapping elements in the scene graph to concepts in the
ontology is defined. Both facts obtained through the scene graph and facts
obtained from the ontology are translated into propositions in the domain.
This approach results in an explosion of facts that requires a pruning step in
order to be tractable for classical planning approaches.

This problem of scene graphs being too complex, with numerous vertices and
edges, is long standing. To mitigate this, planners can employ procedures that
determine which attributes of the scene are most relevant while also
preserving the semantics provided by the class hierarchy and item features. An
example of a planner designed for this purpose is the SCRUB planner (Agia et
al. 2021). SCRUB is a planner-agnostic procedure that prunes the state space
to include only the relevant facts within a scene graph. It is paired with
SEEK (Agia et al. 2021), a planner-agnostic procedure that scores items in the
scene based on an importance score produced by a graph neural network (Silver
et al. 2021). All elements that are ancestors to the relevant elements,
according to some threshold, are preserved as facts in the state. Both the
SCRUB and SEEK procedures dramatically reduce the number of facts needed to
characterize the world state. The facts in the world are translated into
binary predicates and passed to a classical planner. This provides a
heuristic-based measure for identifying relevant facts which can, like most
heuristics, produce inaccurate approximations. The combinatorial approach we
propose uses the existing semantic structure to determine relevance.

Miao et al take an alternate approach to using scene graphs to describe world
states and action models (Miao, Jia, and Sun 2023). In their approach, action
operators are specified in terms of an initial state subgraph, a final state
subgraph, and an intermediate subgraph. For each element and relation in these
subgraphs, the global scene graph is updated by adding elements into the scene
graph that are discussed in the action model. If elements are referenced in
the final state subgraph that are not present in the scene, they are
introduced as isolated vertices. These vertices are connected to the global
scene graph by consulting an external knowledge base that contains a type
hierarchy. Their procedure searches for a matching element type, identifies a
parent type that exists in the scene graph, and defines an edge from that
element to the existing type. This is a fragile approach to resolving changes
in the world state because it relies on an external knowledge base to be
correctly and completely instantiated in order for new information to be
properly integrated.

Overall, using scene graphs as a representation for world states during
planning has gained attention. These methods satisfy the need to support rich
and complex representations of the world using ontologies but still suffer in
their ability to integrate ontological information in a way that does not
cause a state explosion. In our approach, the ontology (schema) is an integral
part of the formalism and with it comes specialized tooling for manipulating
such data.

## Preliminaries

In this section, we explain the mathematical model for planning as a state
transition system and briefly discuss the use of category theory.

### Planning as a State Transition System

The state transition system model of planning is a formal representation of a
planning problem that describes the state space of the problem and the
possible actions that can be taken to move between states. In this model
(Ghallab, Nau, and Traverso 2004), a planning problem can be defined as a
tuple $P=\langle S,A,\gamma\rangle$, where:

  * •

The state space $S=\\{s_{0},s_{1},s_{2},...\\}$ is the set of all possible
states. A state $s\in S$ represents a snapshot of the world at a particular
point in time. It ideally includes all relevant information about the state of
the world, such as the location of items and their properties.

  * •

The action space $A=\\{a_{0},a_{1},a_{2},...\\}$ is the set of all possible
actions. An action represents a transition from one state to another state.

  * •

The transition function $\gamma:A\times S\rightarrow S$ is a partial function
that, where it is defined, maps an action and a state to the next state.

An action $a\in A$ is applicable at state $s\in S$ if $\gamma(a,s)$ is
defined. A plan, $\pi=\langle a_{1},a_{2},\dots,a_{n}\rangle,a_{i}\in A$, is
any sequence of actions. It is a solution to the planning problem if it
transitions from the initial state $s_{0}$ to the goal state $s_{g}$, i.e.,
$\gamma(a_{i},s_{i-1})=s_{i}$ for $i=1,\dots,n$ and $s_{n}=s_{g}$.

The state transition system model of planning provides a structured and formal
way to represent planning problems and reason about the possible sequences of
actions that can be taken to achieve a goal. The manner in which states,
actions, and transition functions are represented both classically and
categorically is the focus of this paper.

### Category Theory

Category theory is a mathematical framework that aids in understanding the
relationships between different mathematical structures. In recent years, it
has found important applications in systems engineering and design (Breiner,
Pollard, and Subrahmanian 2019; Breiner, Subrahmanian, and Sriram 2016; Censi
2016), robotics and planning (Aguinaldo et al. 2021; Aguinaldo and Regli 2021;
Master et al. 2020), and physics (Baez and Stay 2011; Abramsky and Coecke
2008). For the purposes of planning, category theory provides an alternative
mathematical language for representing world states and action models.

## Classical Representations

The literature on classical and neoclassical planning encompasses a variety of
approaches to modeling the state of the world. Among these, the most widely
employed domain-independent representations are the set-theoretic, classical,
and state-variable representations (Ghallab, Nau, and Traverso 2004).

#### Existing Representations for World States, $S$

The classical representation of world states is based on a restricted form of
first-order logic in which the world states are represented as a conjunction
of literals, where a literal is an atomic proposition or its negation. These
literals can encode facts such as the location of items, the state of various
sensors, and other relevant information. Logical operators such as AND, OR,
and NOT are used to combine these literals into more complex expressions that
can be used to describe the relationships between different parts of the world
state. World states can be lifted to abstract states consisting of a
conjunction of predicates, where predicates are $n$-ary relations between
variable symbols. For example, the predicate $\mathrm{on}(x,y)$ might
represent the fact that something represented by $x$ is on top of another
thing represented by $y$ or, equally plausible, the converse. It is important
to note that the semantics of the predicates must be established informally,
say through external documentation or word of mouth. A predicate becomes a
grounded literal when the variable symbols, like $x$ and $y$, are assigned to
symbols that are constant. For instance, the grounded literal
$\mathrm{on}(\mathrm{b_{1}},\mathrm{b_{2}})$ could represent a block called
$\mathrm{b_{1}}$ that is on top of a block called $\mathrm{b_{2}}$.

#### Existing Representations for Actions, $A$

The classical representation defines action schemas in terms of preconditions,
effects, and parameters. Preconditions describe the conditions that must be
true for the action to be applicable, while effects describe the changes that
the action makes to the state of the world. Preconditions and effects are
defined in terms of predicates where their variable symbols, also known as
parameters, can take on different values depending on the context in which the
action is used. The classical planning representation assumes that actions are
deterministic, meaning that their effects are completely specified and do not
depend on any probabilistic factors. Additionally, the classical
representation assumes that actions can be arranged in any order, allowing for
a wide variety of possible plans to be generated. In practice these action
schemas can be augmented with types; however, types are not a formal feature
of the logical system.

#### Applicability

In classical planning, the applicability of actions to a world state is
determined by a set of preconditions specified for each action. In the
classical representation, preconditions are represented as conjunctions of
literals. To check whether an action is applicable in a particular world
state, the planner examines whether the preconditions of the action are
satisfied by the current state. To do this, a planner typically uses logical
inference techniques within propositional logic, first-order logic, or other
logical formalisms. Once grounded, conjunction of predicates can be
represented as sets of ground literals. The planner can then check whether the
precondition is a subset of the world state, which means that the
preconditions are satisfied in the world state. It is possible to model
domain-specific implications, called derived predicates in PDDL (Thiébaux,
Hoffmann, and Nebel 2005), to incorporate implicit preconditions when
determining applicability of an action; however, derived predicates do not
make any changes to the world state.

#### Transition, $\gamma$

A state transition occurs when an action is applied to a world state, yielding
a new world state. Similar to the preconditions, the world state can be
interpreted as a set of literals. Therefore, when an action is applied, the
new state is identified by applying set operations to the set representing the
current world state. Positive effects add ground literals to the set and
negative effects, those prefixed with NOT, subtract ground literals from the
set to produce the new world state.

## Categorical Representation

To effectively manage world states during planning and plan execution, we
propose to adopt categorical logic as a logical formalism. An essential
feature of categorical logic is the ability to capture the relationship
between logical syntax (theories) and semantics (models) using functors,
through a paradigm known as functorial semantics. This differs from the
standard formalism of first order logic because it gives the syntax of the
language status as an algebraic object independent of its semantics.

### World States as $\mathsf{C}$-sets

In our approach, we assume world states in robot task planning domains can be
effectively modeled using scene graphs, which are structured representations
of the elements, attributes, and relations based on a domain-specific
ontology. Recall that scene graphs are a specialized form of knowledge graphs
that focus on the visual aspects of a scene, with nodes representing items and
edges representing the spatial relationships between them (Chang et al. 2023).
These graphs can be used to capture a wide range of information about a world
state, including the physical and semantic properties of items, their
interactions with each other, and the context in which they exist.

Our proposed representation provides a sort of denotational semantics for
scene graphs using the category $\mathsf{C}\text{-}\mathsf{Set}$. Let
$\mathsf{C}$ denote a small category, called a schema. A $\mathsf{C}$-set111A
$\mathsf{C}$-set also known as a copresheaf on $\mathsf{C}$. is a functor222We
direct the unfamiliar reader to (Leinster 2016) for the definitions of
categories, functors, natural transformations, limits, and colimits. from
$\mathsf{C}$ to the category $\mathsf{Set}$. The schema is a category whose
objects we interpret as types and whose morphisms describe “is-a” and other
functional relationships between types. The category $\mathsf{Set}$ is the
category of sets and functions. Thus, a $\mathsf{C}$-set is a functor that
sends types to sets and type relationships to functions. On this
interpretation, $\mathsf{C}$-sets are a simple but useful model of relational
databases (Spivak and Kent 2011).

A more formal definition is provided below.

######  Definition 0.1 (Category of $\mathsf{C}$-sets,
$\mathsf{C}\text{-}\mathsf{Set}$).

For a given schema $\mathsf{C}$, the category of $\mathsf{C}$-sets is the
functor category $\mathsf{C}\text{-}\mathsf{Set}:=\mathsf{Set}^{\mathsf{C}}$,
whose objects are functors from $\mathsf{C}$ to $\mathsf{Set}$ and whose
morphisms are natural transformations between those.

In practice, the schema is a category that is finitely presented by generators
and relations. As an example, let $\mathsf{Gr}=\\{E\rightrightarrows V\\}$ be
the category freely generated by two objects, $E$ and $V$, and two parallel
morphisms, $\text{src, tgt}:E\rightarrow V$. Then a $\mathsf{Gr}$-set is a
graph, which would be called by graph theorists a “directed multigraph.” So,
another interpretation of $\mathsf{C}$-sets is that they are a generalization
of graphs to a broad class of combinatorial data structures.

The category of elements (Riehl 2016) construction333The category of elements
construction of $X$ may be expressed using $\int X$ in other texts. of a
$\mathsf{C}$-set $X$ packages the data of $X$ into a category resembling a
knowledge graph. Specifically, a morphism in the category of elements can be
interpreted as a Resource Description Framework (RDF) triple (Patterson 2017),
which is a common text-based serialization format for knowledge and scene
graphs. A $\mathsf{C}$-set is shown in this style in Figure 1.

Figure 1: An example $\mathsf{C}$-set, $G$, that stores data about people’s
favorite pet. The category of elements contains triples analogous to RDF
triples.

### Actions as Spans in $\mathsf{C}\text{-}\mathsf{Set}$

Action rules are specified as spans in $\mathsf{C}\text{-}\mathsf{Set}$.
Action rules are made up of components similar to those of action schemas in
classical representation. Specifically, actions rules are spans
($I\hookleftarrow K\rightarrow O$) in $\mathsf{C}\text{-}\mathsf{Set}$ that
consists of the precondition, $I$, on the left-hand side, the effects, $O$, on
the right-hand side, and the glue, $K$, in the middle, which gives the data
that remains unchanged between the input and the output.

In our approach, we present spans of $\mathsf{C}$-sets as colimits of
representable functors. A (covariant) representable functor (MacLane 1971),
$\mathsf{C}(A,-)$, for a given category $\mathsf{C}$ and object
$A\in\mathsf{C}$ maps objects, $X\in\mathsf{C}$, to the set of morphisms that
go from from $A$ to $X$. In other words, for a given representable functor
pertaining to $A$, objects $X\in\mathsf{C}$ are mapped to the set of edges
that go from $A$ to $X$. A colimit taken across functors like these glues all
of the relevant structures together. This conversion ensures that implicit
substructure is taken into account when an object, such as $A$, is explicitly
identified.

The categorical rule specification differs from the classical one in that it
takes a declarative approach by not articulating what atoms should be added
and removed from the state, but rather discussing what should be in the state
and resolving conflicts using the double-pushout (DPO) rewriting procedure
which is discussed in a later section.

### Applicability Using Monomorphisms

Recall that in classical planning, a precondition is satisfied by a world
state when its literals are a subset of the world state or if there exists a
logical entailment between the precondition and the world state. In the
category-theoretic context, these notions are generalized via monomorphisms.

Monomorphisms generalize the concept of an injective function to arbitrary
categories. In $\mathsf{Set}$, monomorphisms are precisely injective
functions. In $\mathsf{C}\text{-}\mathsf{Set}$, monomorphisms are natural
transformations such that every component is an injective function, e.g., a
monomorphism between graphs is a graph homomorphism such that the vertex and
edge maps are both injective. More specifically, the monic condition of a
monomorphism checks that two entities in the precondition cannot be mapped to
the same entity in the world state.

### Transition Using Double-Pushout (DPO) Rewriting

The action rules are exactly double-pushout (DPO) rewriting rules. Double-
pushout (DPO) rewriting is a type of graph rewriting that is particularly
well-suited for algebraic approaches to graph transformation. In fact, DPO
rewriting generalizes directly from graph rewriting to $\mathsf{C}$-set
rewriting (Brown et al. 2021). The DPO method, described below, is used to
compute all possible matches of the preconditions, and to determine which
matches are compatible with the effects. The result is a set of transformation
steps that can be applied to the target graph.

DPO rewriting relies on the fundamental concept of a pushout. A pushout is a
colimit of a diagram having the shape of a span
($\bullet\leftarrow\bullet\rightarrow\bullet$). Given a span $X\leftarrow
Z\rightarrow Y$, a pushout produces an object that is the union of $X$ and $Y$
joined along $Z$, $(X\cup Y)/Z$. A pushout in $\mathsf{C}\text{-}\mathsf{Set}$
is computed by taking the disjoint union of the sets being pushed out, adding
the functions between sets based on $\mathsf{C}$, and quotienting by $Z$.

Pseudocode for the DPO rewriting procedure is given in Algorithm 1. The first
step is to find a monomorphism, $m$, that matches $I$ in $X$, as described in
the previous subsection. The pushout complement, $f$, is computed provided the
morphisms $l$ and $m$. A pushout complement is a map that manages the deletion
of entities that form the complement $K/I$. Because $i$ is a monomorphism and
we assume the identification and dangling conditions (Brown et al. 2021) are
met, the pushout complement exists and is unique up to isomorphism. Having
constructed the three sides of the square, $l,m,f$, the pushout square can be
completed by a unique map $g$. Then, to compute the new world state, the right
pushout square is computed provided $f$ and $r$.

${I}$${K}$${O}$${X}$${{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}Z}}$${{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y}}$$\scriptstyle{l}$$\scriptstyle{r}$$\scriptstyle{\definecolor[named]{.}{rgb}{.5,.5,.5}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}m}$$\scriptstyle{\definecolor[named]{.}{rgb}{.5,.5,.5}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}f}$$\scriptstyle{\definecolor[named]{.}{rgb}{.5,.5,.5}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}g}$$\scriptstyle{\definecolor[named]{.}{rgb}{.5,.5,.5}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\lrcorner}$$\scriptstyle{\definecolor[named]{.}{rgb}{.5,.5,.5}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
Algorithm 1 Double-Pushout (DPO) Rewriting

(action rule) $I\hookleftarrow K\rightarrow
O\in\mathsf{C}\text{-}\mathsf{Set}$

(world) $X\in\mathsf{C}\text{-}\mathsf{Set}$

$m$ = FindHomomorphism($I$,$X$)

$f$ = ComputePushoutComplement($l$, $m$)

$g$ = CompletePushout($l$, $f$, $m$)

$Y$ = ComputePushout($f$, $r$)

The time complexity of the FindHomomorphism() subroutine is $O(n^{k})$ where
$k$ is the size of $I$ and $n$ is the size of the relevant substructure in $X$
which is dictated by the objects in $I$ (Brown et al. 2021). The time
complexity of the remaining subroutines is the same as that of computing
pushouts in $\mathsf{Set}$ which is $O(p)$ where $p$ is the sum of the sizes
of the sets involved in the span.

Figure 2: An illustration of how DPO rewriting is executed on a
$\mathsf{C}$-set where $\mathsf{C}$ defines the shapes and the arrows between
them. Each shape in the figure is assigned to a color to help with
readability.

As an example, Figure 2 shows how an action rule changes the initial state to
the final state. In this figure, the rule states that the circle in the
initial state should be replaced by a trapezoid and the square and triangle
should persist. The initial state, bottom-left, satisfies the precondition
because it contains a matching pattern involving the square, triangle, and
circle. This means that a monomorphism can be identified from the precondition
to the initial state. The intermediate state is the result of identifying a
pattern that, when joined with the precondition along the glue, produces the
initial state. This removes the circle from the initial state. The final state
is then constructed by taking the pushout for the span
($\text{Intermediate}\leftarrow\text{Glue}\rightarrow\text{Effect}$). This
produces a pattern where a trapezoid is added in place of the original circle.
The example shown in Figure 2 demonstrates that rules can involve both the
creation and destruction of entities in the world if the precondition contains
an entity and the effect does not contain that entity. This allows for a non-
monotonicity in updates of the world state.

## Comparison

In this section, we discuss the conceptual differences between the classical
and the categorical representations. The comparison is summarized in Table 1.
We also walk through an example, shown in Figure 3, that highlights the
limitations of the classical representation in tracking implicit effects. In
this example domain, a bread loaf (bread loaf) and slices of the loaf
(slice_0, slice_1, slice_2) are on a countertop (countertop). The goal is to
move the bread loaf, and implicitly, all its slices, from the countertop to
the kitchen table (kitchentable).

Representation |  Categorical |  Classical
---|---|---
State, $S$ |  $\mathsf{C}$-set |  Conjunction of literals
Action, $A$ |  Spans in $\mathsf{C}\text{-}\mathsf{Set}$ containing: Preconditions, Glue, Effects |  Action model containing: Parameters, Preconditions, Effects
Applicability |  Monomorphisms in $\mathsf{C}\text{-}\mathsf{Set}$ |  Subset inclusion
Transition, $\gamma$ |  DPO rewriting |  Set-based addition and subtraction
Table 1: A summary of the differences between the classical representation and
the categorical representation aligned to the state transition system model
for planning. Figure 3: A comparison of states, actions, and inferences made
between the categorical representation and the classical representation for an
example that moves a loaf of bread from a countertop to a kitchen table. This
example illustrates a failure of the classical representation to preserve the
global semantics of the world when actions act on only a part of the world.
Using the double-pushout method of $\mathsf{C}$-set rewriting, the categorical
representation is able to do so.

### Handling Structured Knowledge

This example presents a few noteworthy semantic features. A planning
representation in this domain must be able to encode the following facts,
explicitly or implicitly, at different points in time:

  1. (a)

the bread slices are part of the bread loaf

  2. (b)

the bread loaf is on the countertop

  3. (c)

the bread slices are on the countertop

  4. (d)

the bread loaf is on the kitchen table

  5. (e)

the bread slices are on the kitchen table

In the case of the categorical representation, fact (a) is captured by the
morphism $\mathrm{is\ part\
of}:\mathrm{BreadSlices}\rightarrow\mathrm{BreadLoaf}$ in the schema. Fact (b)
about the bread loaf being on the countertop is reified through an abstract
type called $\mathrm{Object}$. This is done so that the morphism
$\mathrm{on}:\mathrm{Object}\to\mathrm{Object}$ can represent the general
notion of an item being on top of another item, instead of the more specific
relation of a bread loaf being on a countertop. Fact (c) is then captured by
the composite morphism $\mathrm{on}\circ\mathrm{is\ a}\circ\mathrm{is\ part\
of}:\mathrm{BreadSlices}\rightarrow\mathrm{Object}$ 444The operator $\circ$
represents a composite function which can be read as ”$f$ following $g$” or
$(f\circ g)(x)=f(g(x))$.. In the classical representation, fact (a) is
captured by the propositions partOf(slice_n, bread) for $n=0,1,2$. Fact (b)
and (d) are captured by the proposition on(bread, countertop) and on(bread,
kitchentable). Fact (c) and (e) are captured by the propositions on(slice_n,
countertop) and on(slice_n, kitchentable). Intuitively, because the bread loaf
is on the countertop, the slices that make up the loaf are also on the
countertop. In the categorical representation, this is captured using a
composite morphism. In the classical representation, this is done by
explicitly stating for each slice, that it is on the countertop.

### Handling Applicability of Actions

In the categorical representation, applicability of an action is determined by
the existence of a monomorphism in $\mathsf{C}\text{-}\mathsf{Set}$ from the
rule input to the world state. Recall that a representable functor maps an
object, $x\in\mathsf{C}$, to the set of morphisms that involve $x$. When you
present an action using colimits of representables, there are both explicit
conditions given by the representables and implicit conditions that appear
when the representable is computed. This provides a mechanism for having
implicit conditions represented in the action schemas. In this example, the
initial state satisfies the input of the action rule because it contains
$\mathrm{BreadLoaf}$, $\mathrm{Object}$, and $\mathrm{Countertop}$ and its
related morphisms. In the classical representation, applicability of the
action moveObj(bread, countertop, kitchentable) is determined by whether or
not the world state contains the element on(bread, countertop) in the set of
propositions.

### Handling Implicit Effects

Now that we have determined that this action is applicable in both
representations, we can apply the action. In the categorical representation,
this action is modeled by a span in $\mathsf{C}\text{-}\mathsf{Set}$ whose
left foot includes knowledge about the bread loaf being on the countertop and
whose right foot includes knowledge about the bread loaf being on the kitchen
table. The apex of the span states that the bread loaf itself is preserved
throughout this change. In the classical representation, the action schema
describes the generic action of moving items x from one location, s, to
another, t. The action operator is grounded by assigning x to the breadloaf, s
to the countertop, and t to the kitchentable. Once this action is applied, a
desirable outcome would be for the new state to account for the movement of
the bread slices from the countertop to the kitchen table because they are
part of the breadloaf. In the categorical representation, the same composite
morphism that existed in the initial state exists in the final state; however,
the target of the morphism has changed from the $\mathrm{countertop}$ to the
$\mathrm{kitchentable}$. This captures the implicit change that occurred to
the bread slice locations. In the classical representation, the new state
captures the fact that the breadloaf is on the kitchen table, but does not
capture the fact that the bread slices are on the kitchen table. This error
would likely cause a planner to instruct an agent to move each bread slice
individually due to an inconsistency in the world state.

## Conclusion

The limitations of classical planning representation languages in tracking
implicit preconditions and effects have motivated us to propose an alternative
world state representation based on the category-theoretic concepts of
$\mathsf{C}$-sets and DPO rewriting. Our categorical representation
accommodates structured knowledge about the world state and formalizes a model
of the application domain using a user-provided ontology. This method provides
formal semantics for using knowledge graphs and relational databases to model
world states and updates in planning. Our comparison between the classical and
categorical planning representation languages demonstrates that our proposed
representation is more structured and has advantages over the classical one in
handling complex planning scenarios. Future work include designing mechanisms
for transferring plans between domains and extending this system to handle
non-combinatorial data, such as numeric data. We believe that our proposed
representation has the potential to significantly enhance the effectiveness
and efficiency of planning systems in robotic task planning domains.

## Acknowledgments

This work was partially funded by the U.S. Defense Advanced Research Projects
Agency under contract #HR00112220004. Any opinions, findings, and conclusions
or recommendations expressed in this paper are those of the authors and do not
necessarily reflect these agencies’ views. We thank Kristopher Brown and Owen
Lynch from the Topos Institute for heavily contributing to the development of
DPO rewriting and $\mathsf{C}\text{-sets}$ in AlgebraicJulia. We also thank
the students of the Ruiz HCI Lab—Alexander Barquero, Rodrigo Calvo, Niriksha
Regmi, Daniel Delgado, Andrew Tompkins—who built the task guidance platform
that inspired the examples in this paper. Lastly, we thank Dana Nau for
valuable feedback about this paper.

## References

  * Abramsky and Coecke (2008) Abramsky, S.; and Coecke, B. 2008.  Categorical Quantum Mechanics.  _Handbook of Quantum Logic and Quantum Structures vol II_ , 1–63.
  * Agia et al. (2021) Agia, C.; Jatavallabhula, K. M.; Khodeir, M.; Miksik, O.; Vineet, V.; Mukadam, M.; Paull, L.; and Shkurti, F. 2021.  TASKOGRAPHY: Evaluating robot task planning over large 3D scene graphs.  _5th Conference on Robot Learning_ , 1–18.
  * Aguinaldo et al. (2021) Aguinaldo, A.; Bunker, J.; Pollard, B.; Shukla, A.; Canedo, A.; Quiros, G.; and Regli, W. 2021.  RoboCat: A Category Theoretic Framework for Robotic Interoperability Using Goal-Oriented Programming.  _IEEE Transactions on Automation Science and Engineering_ , 1–9.
  * Aguinaldo and Regli (2021) Aguinaldo, A.; and Regli, W. 2021.  A Graphical Model-Based Representation for PDDL Plans using Category Theory.  In _ICAPS 2021 Workshop XAIP_.
  * Amiri, Chandan, and Zhang (2022) Amiri, S.; Chandan, K.; and Zhang, S. 2022.  Reasoning with Scene Graphs for Robot Planning under Partial Observability.  _IEEE Robotics and Automation Letters_ , 7(2).
  * Baez and Stay (2011) Baez, J.; and Stay, M. 2011.  Physics, topology, logic and computation: A Rosetta Stone.  _Lecture Notes in Physics_ , 813: 95–172.
  * Beetz et al. (2018) Beetz, M.; Bessler, D.; Haidu, A.; Pomarlan, M.; Bozcuoglu, A. K.; and Bartels, G. 2018.  Know Rob 2.0 - A 2nd Generation Knowledge Processing Framework for Cognition-Enabled Robotic Agents.  _Proceedings - IEEE International Conference on Robotics and Automation_ , 512–519.
  * Breiner, Pollard, and Subrahmanian (2019) Breiner, S.; Pollard, B.; and Subrahmanian, E. 2019.  Functorial Model Management.  _Proceedings of the Design Society: International Conference on Engineering Design_ , 1(1): 1963–1972.
  * Breiner, Subrahmanian, and Sriram (2016) Breiner, S.; Subrahmanian, E.; and Sriram, R. D. 2016.  Modeling the Internet of Things: A foundational approach.  _ACM International Conference Proceeding Series_ , Part F1271: 38–41.
  * Brown et al. (2021) Brown, K.; Patterson, E.; Hanks, T.; and Fairbanks, J. 2021.  Computational category-theoretic rewriting.  _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_.
  * Censi (2016) Censi, A. 2016.  A Mathematical Theory of Co-Design.  Technical report, Laboratory for Information and Decision Systems, MIT.
  * Chang et al. (2023) Chang, X.; Ren, P.; Xu, P.; Li, Z.; Chen, X.; and Hauptmann, A. 2023.  A Comprehensive Survey of Scene Graphs: Generation and Application.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 45(1): 1–26.
  * Galindo et al. (2008) Galindo, C.; Fernández-Madrigal, J. A.; González, J.; and Saffiotti, A. 2008.  Robot task planning using semantic maps.  _Robotics and Autonomous Systems_ , 56(11): 955–966.
  * Ghallab, Nau, and Traverso (2004) Ghallab, M.; Nau, D.; and Traverso, P. 2004.  _Automated Planning: Theory and Practice_.  Morgan Kaufmann.  ISBN 9781558608566.
  * Gil (1990) Gil, Y. 1990.  Description Logics and Planning.  _AI Magazine_ , 26(2): 1.
  * Kang and Choi (2009) Kang, D.; and Choi, H.-j. 2009.  Hierarchical Planning through Operator and World Abstraction using ontology for home service robots.  _2009 11th International Conference on Advanced Communication Technology_ , 2209–2214.
  * Knoblock et al. (1998) Knoblock, C.; Barrett, A.; Christianson, D.; Friedman, M.; Kwok, C.; Golden, K.; Penberthy, S.; Smith, D. E.; Sun, Y.; and Weld, D. 1998.  PDDL — The Planning Domain Definition Language.  Technical report, Yale Center for Computational Vision and Control.
  * Leinster (2016) Leinster, T. 2016.  _Basic Category Theory_.  Cambridge University Press.
  * MacLane (1971) MacLane, S. 1971.  _Categories for the Working Mathematician_.  New York: Springer-Verlag.  Graduate Texts in Mathematics, Vol. 5.
  * Master et al. (2020) Master, J.; Patterson, E.; Yousfi, S.; and Canedo, A. 2020.  String Diagrams for Assembly Planning.  _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_.
  * Miao, Jia, and Sun (2023) Miao, R.; Jia, Q.; and Sun, F. 2023.  Long-term robot manipulation task planning with scene graph and semantic knowledge.  _Robotic Intelligence and Automation_.
  * Patterson (2017) Patterson, E. 2017.  Knowledge Representation in Bicategories of Relations.  _CoRR_ , abs/1706.00526.
  * Patterson, Lynch, and Fairbanks (2021) Patterson, E.; Lynch, O.; and Fairbanks, J. 2021.  Categorical Data Structures for Technical Computing.  _Compositionality_ , 4(5): 1–27.
  * Riehl (2016) Riehl, E. 2016.  _Category theory in context_.  ISBN 9780486809038.
  * Silver et al. (2021) Silver, T.; Chitnis, R.; Curtis, A.; Tenenbaum, J.; Lozano-Pérez, T.; and Kaelbling, L. P. 2021.  Planning with Learned Object Importance in Large Problem Instances using Graph Neural Networks.  _35th AAAI Conference on Artificial Intelligence, AAAI 2021_ , 13B: 11962–11971.
  * Spivak and Kent (2011) Spivak, D. I.; and Kent, R. E. 2011.  Ologs: a categorical framework for knowledge representation.  _PLOS ONE_.
  * Tenorth and Beetz (2017) Tenorth, M.; and Beetz, M. 2017.  Representations for robot knowledge in the KNOWROB framework.  _Artificial Intelligence_ , 247: 151–169.
  * Thiébaux, Hoffmann, and Nebel (2005) Thiébaux, S.; Hoffmann, J.; and Nebel, B. 2005.  In defense of PDDL axioms.  _Artificial Intelligence_ , 168(1-2): 38–69.
  * Wilkins and DesJardins (2001) Wilkins, D. E.; and DesJardins, M. 2001.  A call for knowledge-based planning.  _AI Magazine_ , 22(1): 99–115.


# Named Entity Recognition in Industrial Tables using
Tabular Language Models

Aneta Koleva1,2*, Martin Ringsquandl1*, Mark Buckley1, Rakebul Hasan 1 Volker
Tresp1,2
1Siemens AG, 2Ludwig-Maximilians University
<EMAIL_ADDRESS>
###### Abstract

Specialized transformer-based models for encoding tabular data have gained
interest in academia. Although tabular data is omnipresent in industry,
applications of table transformers are still missing. In this paper, we study
how these models can be applied to an industrial Named Entity Recognition
(NER) problem where the entities are mentioned in tabular-structured
spreadsheets. The highly technical nature of spreadsheets as well as the lack
of labeled data present major challenges for fine-tuning transformer-based
models. Therefore, we develop a dedicated table data augmentation strategy
based on available domain-specific knowledge graphs.

We show that this boosts performance in our low-resource scenario
considerably. Further, we investigate the benefits of tabular structure as
inductive bias compared to tables as linearized sequences. Our experiments
confirm that a table transformer outperforms other baselines and that its
tabular inductive bias is vital for convergence of transformer-based models.

††∗ Equal Contribution.

##  1 Introduction

There has been growing interest in developing special model designs intended
to capture tabular structure Deng et al. (2020); Yin et al. (2020); Herzig et
al. (2020); Wang et al. (2021). A recent survey named these models tabular
language models (TaLMs) and provided an overview of the different
architectures and pretraining objectives Dong et al. (2022). One of the
downstream tasks where TaLMs are applicable is table interpretation (TI) with
its sub-tasks: entity linking, column type annotation and relation extraction
Deng et al. (2020). Most TaLMs for TI use BERT as the backbone language model
(LM) for encoding the content of table cells and aggregate their
representations on different levels (cell, row or column) depending on the
task.

Although tabular data is omnipresent in industry, TaLMs such as table
transformers, have not found their way into industrial applications yet. One
reason being the nature of data stored in industrial tables which is different
and more dynamic than data in academic datasets where the schema of the table
is consistent and each cell contains a single entity of one type Cutrona et
al. (2020). As shown in Figure 1, industrial tables contain multiple sub-cell
entities from different types, hence the TaLMs which provide cell-level
aggregation are not sufficient. In this direction, we formulate the problem of
sub-cell named entity recognition (NER) in tables using TaLMs.

Another challenge is that tabular data in industry is often lacking labels,
especially labels reflecting the high variance across examples. Due to the
very technical and domain-specific nature only experts can effectively provide
such labels, which is – for most tasks – too expensive. These low-resource
scenarios are challenging for statistical NLP models and usually prohibit
fine-tuning of large-scale transformer-based models. A popular strategy to
remedy low-resource scenarios is data augmentation (DA) Simard et al. (1996),
which allows to increase data diversity without having to collect new
examples.

Figure 1: Example table from an industrial plant equipment spreadsheet. Boxes
represent NER annotations.

Common DA techniques in NLP range from using external knowledge such as
WordNet Zhang et al. (2015), machine-translation models for back-translation
Yaseen and Langer (2021) or mixing of examples inspired from computer vision
Yun et al. (2019). An empirical study by Longpre et al. (2020) showed that
applying off-the-shelf DA techniques Sennrich et al. (2016); Wei and Zou
(2019) for fine-tuning of LM like BERT or RoBERTa bring little to no
improvement and become even less beneficial in cross-domain settings Herzig et
al. (2020); Zhong et al. (2020). These studies emphasize the challenge of
developing domain-specific DA techniques which would help improve the existing
pretrained transformer models.

Although, there are no domain-specific DA techniques applicable to a tabular
dataset, in many industrial domains there exist external resources which can
be exploited for creating augmented tables. In this paper we study a DA
technique for industrial spreadsheet tables leveraging publicly available
resource based on an industrial standard. Specifically, the contributions of
this paper are the following:

  * •

We introduce a table transformer model for sub-cell NER, TabNER, and provide
an industrial use case as a motivation for this. To the best of our knowledge,
this is the first attempt to solve NER in tables with TaLMs.

  * •

We develop a novel DA technique for semantically consistent augmentation of
tables based on domain-specific knowledge graphs.

  * •

We empirically show that the inductive bias of TaLMs is valuable and combined
with our DA technique boosts the performance by 9% compared to a sequential
model.

##  2 Industry NER Use Case

As motivation for tabular NER in an industrial context, we describe a real-
world dataset from which information about industrial plant equipment, such as
actuators, sensors, vessels, etc. and their physical quantities should be
extracted. This information is typically collected and maintained by engineers
in spreadsheets. The spreadsheets are roughly organized in a tabular format,
as can be seen from the example table in Figure 1. In these spreadsheets, each
row typically represents information about one or multiple equipment
instances. Some columns represent relevant physical properties of these
equipments, while others are non-informative. However, the engineers do
neither comply to a fixed schema nor to unified spelling of equipment or
properties. The goal is to automatically extract relevant entities for
creating a structured specifications of the plant equipment. We phrase this
problem as NER task with the following types of entities. The type TAG refers
to a systematic identifier of an equipment. There are some conventions for
generating equipment tags (e.g. NORSOK, KKS), but most plant operators
customize them and some sheets do not contain identifiers at all. Type EQ is
for surface names of equipment types. The type QUANT refers to the physical
properties/quantities describing the functional specifications of equipment
and the type UoM stands for unit of measurement.

Dataset | $\mu_{\text{tok}}$ | $\sigma_{\text{tok}}$ | $K_{\text{tok}}$ | $\mu_{\text{col}}$ | $\sigma_{\text{col}}$ |
---|---|---|---|---|---|---
SemTab | 2 | 2.5 | 132.2 | 4.5 | 1.9 |
Plant | 2.6 | 3.7 | 585.3 | 16.3 | 21.6 |
Table 1: Dataset statistics: academic vs. industry. Figure 2: Input
modifications to vanilla transformer to encode tokens with tabular structure.

#### Table Statistics

It is not obvious why performing NER in tables would benefit from
sophisticated language models. In fact, looking at common tabular benchmark
datasets, such as the ones used in the SemTab challenge Cutrona et al. (2020),
detecting entities is usually very straightforward. Since all tokens in a cell
are assumed to represent a single entity, sub-cell NER is an unnecessary step
and we only need to perform entity/cell linking. Looking at the example table
in Figure 1, however, gives the impression that these industrial spreadsheets
are very differently structured from common benchmarks. There can be quite
some text and even multiple sub-cell entities in a single cell. Table 1
supports this impression with statistical evidence. The average number of
tokens per cell, $\mu_{\text{tok}}$, is 30% higher in our industrial dataset
compared to a dataset from SemTab. Further, its standard deviation
$\sigma_{\text{tok}}$ and the Kurtosis $K_{\text{tok}}$, show that there is
more variance due to the much longer tail of the distribution of number of
tokens in the plant tables. Even more obvious is the difference at the column
level where the tables in the SemTab challenge contain on average 4 times less
columns ($\mu{\text{col}}$) than the tables describing plant equipment
specification with much lower variance as well. This suggests that every token
in our NER task has a much broader intra- and inter-cell context.

##  3 Related Work

There has been some research focused on extracting entities and their
quantities from web tables. Ibrahim et al. Ibrahim et al. (2016) phrased this
problem as entity linking using a table-biased Markov random field and distant
supervision.

Wu et al. Wu et al. (2018) employed BiLSTM models to encode rich-format
documents (unstructured text, headings, tables) that mention electronic
components, quantities and units of measure. They used hand-crafted labeling
functions for collecting (weakly) labeled entities and relations which can be
used as weak supervision.

A recent work on table classification Koleva et al. (2021) compared TaLMs like
TaBERT Yin et al. (2020) versus non-contextual word embedding methods for
generating table vector representations. TURL Deng et al. (2020) uses a
Transformer Vaswani et al. (2017) with table-specific attention mechanism
which has been pre-trainined and fine-tuned towards solving the tasks of table
interpretation: column type annotation, entity linking and relation
extraction. However, this methods generates representations on a cell level
and therefore can not be applied for solving our NER problem.

We are not aware of any work that uses TaLMs for sub-cell table NER in an
industrial setting.

#### Data Augmentation

Recently, many different DA techniques have been proposed with the purpose to
solve low-resource issues in NLP by generating new examples from existing
datasets. For a comprehensive overview on the different DA techniques, we
refer the readers to the recent survey by Feng et al. Feng et al. (2021).

Several simple and effective DA techniques for NER are presented by Dai and
Adel (2020). However, these techniques are not directly applicable to the
industrial tabular data since they rely on domain-agnostic linguistic
resources like WordNet. Similarly, methods for sequence labeling, such as
backtranslation Yaseen and Langer (2021) can not be applied to tabular data
because the content of the tables are mostly facts and not full sentences.

##  4 Method

We now define the table NER problem and outline how we encode tokens in tables
using TaLMs.

We define a table as a tuple $T=(C,H)$, where $C=\\{c_{1,1},c_{1,2},\dots
c_{i,j},\dots,c_{n,m}\\}$ is the set of table body cells for $n$ rows and $m$
columns. Every cell
$c_{i,j}=\left(w_{c_{i,j},1},w_{c_{i,j},2},\dots,w_{c_{i,j},t}\right)$ is a
sequence of tokens of length $t$. The table header
$H=\\{h_{1},h_{2},\dots,h_{m}\\}$ is the set of corresponding $m$ column
header cells, where
$h_{j}=~{}\left(w_{{h_{j}},1},w_{{h_{j}},2},\dots,w_{{h_{j}},q}\right)$ is a
sequence of header tokens with length $q$. We use $T_{[i,:]}$ to refer to the
$i$-th row ($H=T_{[0,:]}$) and $T_{[:,j]}=\\{h_{j},c_{1,j},\dots,c_{n,j}\\}$
to refer to the $j$-th column of $T$.

Each labeled cell has an NER-tag sequence: $(y_{1},y_{2},\dots,y_{|cell|})$,
where each $y_{i}\in\mathcal{Y}$. We use IO tags, thus $\mathcal{Y}$ is
$\\{\textit{O}\\}\cup\\{\textit{I-ENT}\\}$, where
$\textit{ENT}\in\\{\textit{TAG},\textit{EQ},\textit{QUANT},\textit{UoM}\\}$.

###  4.1 TabNER Model

Compared to the existing TaLMs such as TaBERT Yin et al. (2020), TURL or TAPAS
Herzig et al. (2020) which generate cell-level representations, we propose a
simple modification to the vanilla transformer Vaswani et al. (2017) which
allows us to use almost any pre-trained transformer111huggingface.co token
classification models that take a custom 2D attention_mask to obtain a (sub-
cell) token-level representations for a table.

Our TabNER model consists of a token encoder layer Enc and a classification
layer. A conceptual architecture of the table token input encoding is shown in
Figure 2, where token vector representations for each token in the linearized
table are generated by aggregating the token embeddings, the segment
embeddings, and position embeddings. The segment indicates if a token is part
of the head or the body (instead of the 1st / 2nd sentence semantics) and the
position encoding is done on a cell-level, so it restarts from 0 for every
cell in body $C$ and header $H$:

$\displaystyle\textit{pos}(T)=$
$\displaystyle(\textit{pos}(h_{i}),\dots,\textit{pos}(c_{i,j}))$
$\displaystyle\textit{pos}(cell)=$ $\displaystyle(0,\dots,|cell|)$

Similarly as in TURL, we use a table attention mask (visibility matrix)
$\alpha_{i,j}$, but on token-level instead of cell-level. This mask allows
every token to attend exclusively to tokens which are either in the same row
or in the same column. $\alpha_{i,j}$ is a symmetric binary matrix defined as:

$\alpha_{i,j}=\begin{cases}1&\text{if
}\textit{col}(i)=\textit{col}(j)\lor\textit{row}(i)=\textit{row}(j),\\\
0&\text{otherwise},\end{cases}$

where $\textit{row }(\textit{col})$ are functions that map linearized token
indices back to row (column) indices in the table.

The output of the token encoder layer is a sequence of token representations:

$\displaystyle\mathbf{w}_{h_{1},1},\dots,\mathbf{w}_{h_{m},t},\mathbf{w}_{c_{1,1},1},\dots,\mathbf{w}_{c_{n,m},t}=\textsc{Enc}(T),$

which is then fed into a classification layer with a Softmax activation to
assign a score for each token to a class $y\in\mathcal{Y}$.

###  4.2 Data Augmentation

As mentioned above, existing DA techniques for NER, such as those presented in
Dai and Adel (2020), are not a good fit for tabular data, since they produce
augmented tables with inconsistent context. For example, the common label-wise
token replacement (LWTR) may replace the QUANT token nominal in Figure 1 with
height or the UoM bar with Celsius. This clearly introduces inconsistencies in
the context, since height pressure has no physical meaning and neither height
nor pressure are measured in Celsius. A visualization of such an inconsistent
table can be seen in the Appendix in Figure 5.

Figure 3: Example graph from POSC Caesar and resulting sets/dictionaries for
RDLTab.

To overcome this problem external domain-specific knowledge is needed. For
many industrial domains there exist resources (standardized vocabularies, data
models) that can be incorporated for DA. We propose a novel DA approach which
leverages existing industrial semantic data models to augment and to generate
tables with consistent context. In particular, we use the Reference Data
Library (RDL) of POSC Caesar (ISO-15926)222http://data.posccaesar.org/rdl/.
The RDL is a rich source of a domain-specific vocabulary and relations in the
process industry. For example, it defines taxonomies that represent specific
types of equipment (EQ), but also physical quantities (QUANT) that plant
equipment typically possess. Figure 3 shows a small excerpt of the RDL as
knowledge graph. We leverage this data in the process of augmenting existing
tables with consistent equipment, quantity and unit of measure (UoM) context
as follows.

First, we extract surface names (sfn) of all entities of type ENT into a
respective set $RDL_{ENT}=\left\\{\textit{sfn-ent}_{1},\textit{sfn-
ent}_{2},\dots\right\\}$, where
$\textit{ENT}\in\\{\textit{EQ},\textit{QUANT},\textit{UoM}\\}$. Additionally,
we extract a dictionary $RDL_{E2Q}:RDL_{\textit{EQ}}\rightarrow
RDL_{\textit{QUANT}}$ that holds a set of applicable quantities for every
equipment and a second dictionary $RDL_{Q2U}:RDL_{\textit{QUANT}}\rightarrow
RDL_{\textit{UoM}}$ that stores all applicable units of measure for a certain
quantity. The extracted sets for the example graph are also shown in Figure 3.

To ease notation we define a function $f_{ner}$ which returns the set of
entity types contained in the set of cells passed as arguments, e.g.,
$f_{ner}(T_{[:,2]})=\\{\textit{EQ}\\}$ means that the second column of table
$T$ contains entities of type EQ.

#### Augmentation procedure

Given a table $T$ we generate an augmented sample $T_{aug}$ as follows:

  1. 1.

Sample $k$ columns that contain no NER annotations as starting point for
augmentation, $T_{aug}\leftarrow\textit{sample}(\bigcup_{j}T_{[:,j]},k)$,
where $f_{ner}(T_{[:,j]})=\varnothing$.

  2. 2.

For every row $i$ in $T_{aug}$: An EQ entity surface name $\textit{sfn-
eq}_{i}$ is sampled uniformly at random from $RDL_{\textit{EQ}}$. The cells in
column $k+1$ hold the sampled names: $c_{i,k+1}\leftarrow\textit{sfn-eq}_{i}$.

  3. 3.

Sample a column header $h_{eq}$ from all training table columns that contain
at least one EQ annotation: $h_{k+1}\leftarrow h_{eq}$.

  4. 4.

For every sampled equipment $\textit{sfn-eq}_{i}$: a QUANT entity surface name
$\textit{sfn-quant}_{i}$ is sampled uniformly at random from
$RDL_{E2Q}(eq_{i})$. Each $\textit{sfn-quant}_{i}$ is a new column header in
$H_{aug}\leftarrow H_{aug}\cup\\{\textit{sfn-quant}_{i}\\}$. Fill the resp.
cells $c_{i,k+i+1}$ with a random numeric value and optionally a randomly
sampled UoM surface name from $RDL_{Q2U}(\textit{quant}_{i})$.

  5. 5.

Finally, generate a last column, where for every sampled equipment
$\textit{sfn-eq}_{i}$ an artificial TAG entity surface name $\textit{sfn-
tag}_{i}$ is generated. This column’s header is then sampled from all training
tables headers that contain at least one TAG annotation.

Artificial tags are generated by forming an acronym from the EQ entity name
and adding groups of random alphanumeric strings, optionally divided by the
dash ’-’ character (which is similar to tagging standards).

##  5 Experiments

In this section we empirically study the performance of TabNER compared
against several baselines as well as the benefits of our domain-specific table
DA technique.

###  5.1 Dataset

We extract 79 tables from a pool of real-world spreadsheets describing
industrial plant equipment. To get expert labels, we sub-sampled each table to
have a maximum of 5 rows. The labels were collected on a cell-by-cell basis
using the tool Prodigy333https://prodi.gy. The statistics of the dataset are
shown in Table 2; the mean number of NER-tags per table is 18, the other
columns show the absolute number of NER-tags for each entity type. All
experiments are carried out in a 5-fold cross validation where we use 10% of
each fold’s training data as validation set.

tables | $\mu_{ner}$ | TAG | EQ | QUANT | UoM
---|---|---|---|---|---
79 | 18 | 295 | 359 | 427 | 359
Table 2: Dataset used for experiments.

###  5.2 Baselines

We compare the performance of TabNER to multiple baselines. First, we design a
rule-based NER (RuleNER) based on spaCy’s
EntityRuler444https://spacy.io/api/entityruler using the same domain-specific
vocabularies from RDL as described in section 4.2 for matching. For detecting
entities of type TAG we employ a heuristic: find the column with most unique
body values which does not contain any known vocabulary terms. Then we mark
all alphanumeric tokens as TAG. The second baseline is a BiLSTM-CRF model that
uses word embeddings (pre-trained GloVe-6B-100d) as well as character
embeddings Ma and Hovy (2016). Here, we simply feed each table in linearized
form as input. Lastly, we fine-tune a vanilla sequential BERT, again with
linearized input tables, without any table structure encoding to study if the
tabular structure inductive bias is justified.

#### DA techniques

We refer to the DA method explained in section 4.2 as RDLTab and compare its
performance against LWTR. For both DA techniques, we experimented with $n=1,2$
number of augmented tables per original table in each epoch. In the case of
LWTR, we generate $n$ new tables by randomly replacing $m/2$ tokens, where $m$
is the total number of NER labels available for the table. When applying
RDLTab, we generate $n$ new tables for every table in the training set. The
best performance was achieved with $n=1$ sample of augmented tables.
Therefore, the presented results are with $n=1$ for both DA techniques and the
comparison with the performance when $n=2$ samples is discussed in the
Appendix.

##  6 Results and Analysis

#### Convergence

First, we analyze the progress of the training loss to study the convergence
of the different NER models, see Figure 4. The loss of vanilla BERT is quite
flat from the beginning and after a few epochs gets stuck at a bad local
optimum - hits early stopping based on validation. We argue that the global
attention and position encoding across the full table are blurring the NER
training signal for BERT and since we could not find a setting to make it
converge properly, we excluded it from further experiments. A more detailed
analysis can be found in the Appendix.

In contrast to BERT, the training loss for TabNER is converging quickly. Using
only the training data, without augmentation, has the least steepest decline,
which is due to observing less labels per epoch. LWTR shows a very steep
decline in the beginning which, however, flattens out sooner than RDLTab. Our
hypothesis here is that LWTR adds helpful variance in the labels at the
beginning, but has less variance to add in the long run, since it can only
sample from known training tables. RDLTab on the other hand produces a more
novel table context over time as the RDL has richer external vocabulary.

#### Table structure vs. sequential inductive bias

We present the final cross-validation F1 scores in Table 3. It can be seen
that TabNER outperforms the baselines in all DA settings, proving the benefits
of being biased towards tabular structure. Surprisingly, BiLSTM-CRF does not
suffer from the linearized global table context as much as BERT does and still
shows competitive performance. One reason might be that the sequential
attention in the BiLSTM is trained from scratch and can therefore learn to
only focus on very narrow context. While BERT is already pre-trained to take
long-range context into account.

#### Data Augmentation

The RDLTab DA boosts performance for both TabNER and BiLSTM-CRF. This shows
the added value of rich external vocabulary for industrial low-resource
problems. Interestingly, LWTR harms performance in both cases. We attribute
this to the problem of producing phrases that are non-meaningful physically
and inconsistent in a tabular context.

Figure 4: Convergence of the training loss. Model | NoAug | LWTR | RDLTab
---|---|---|---
RuleNER | 0.08 | - | -
BiLSTM-CRF | 0.53 | 0.46 | 0.55
TabNER | 0.54 | 0.52 | 0.58
Table 3: F1 scores with different DA techniques.

##  7 Conclusion

In this paper, we demonstrate the applicability of TaLMs to a novel NER
problem in industrial spreadsheets. Our experiments show that the tabular
inductive bias of TaLMs is not only beneficial for this problem, but may even
a necessary condition when relying on pre-trained transformer-based models. In
addition to that we present a DA technique leveraging publicly-available
industrial standard information models to produce augmented tables with
physically sound and consistent context. Compared to an off-the-shelve DA,
this technique shows improved NER performance.

Future work includes understanding how much tabular context is needed to make
training large-scale model more efficient. Another fruitful area is active
learning for tasks using TaLMs to reduce the time for collecting expert
labels.

## References

  * Cutrona et al. (2020) Vincenzo Cutrona, Federico Bianchi, Ernesto Jiménez-Ruiz, and Matteo Palmonari. 2020.  Tough Tables: Carefully Evaluating Entity Linking for Tabular Data.
  * Dai and Adel (2020) Xiang Dai and Heike Adel. 2020.  An analysis of simple data augmentation for named entity recognition.  In _Proceedings of the 28th International Conference on Computational Linguistics, COLING 2020, Barcelona, Spain (Online), December 8-13, 2020_ , pages 3861–3867. International Committee on Computational Linguistics.
  * Deng et al. (2020) Xiang Deng, Huan Sun, Alyssa Lees, You Wu, and Cong Yu. 2020.  Turl: Table understanding through representation learning.  _Proc. VLDB Endow._ , 14(3):307–319.
  * Dong et al. (2022) Haoyu Dong, Zhoujun Cheng, Xinyi He, Mengyu Zhou, Anda Zhou, Fan Zhou, Ao Liu, Shi Han, and Dongmei Zhang. 2022.  Table pre-training: A survey on model architectures, pre-training objectives, and downstream tasks.  In _IJCAI’2022 SURVEY TRACK_.
  * Feng et al. (2021) Steven Y. Feng, Varun Gangal, Jason Wei, Sarath Chandar, Soroush Vosoughi, Teruko Mitamura, and Eduard H. Hovy. 2021.  A survey of data augmentation approaches for NLP.  In _Findings of the Association for Computational Linguistics: ACL/IJCNLP 2021, Online Event, August 1-6, 2021_ , volume ACL/IJCNLP 2021 of _Findings of ACL_ , pages 968–988. Association for Computational Linguistics.
  * Herzig et al. (2020) Jonathan Herzig, Pawel Krzysztof Nowak, Thomas Müller, Francesco Piccinno, and Julian Martin Eisenschlos. 2020.  Tapas: Weakly supervised table parsing via pre-training.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020_ , pages 4320–4333. Association for Computational Linguistics.
  * Ibrahim et al. (2016) Yusra Ibrahim, Mirek Riedewald, and Gerhard Weikum. 2016.  Making sense of entities and quantities in web tables.  In _Proceedings of the 25th ACM International on Conference on Information and Knowledge Management_ , CIKM ’16, page 1703–1712.
  * Koleva et al. (2021) Aneta Koleva, Martin Ringsquandl, Mitchell Joblin, and Volker Tresp. 2021.  Generating table vector representations.  In _CEUR Workshop Proceedings - Deep Learning for Knowledge Graphs (DL4KG)_.
  * Longpre et al. (2020) Shayne Longpre, Yu Wang, and Chris DuBois. 2020.  How effective is task-agnostic data augmentation for pretrained transformers? In _Findings of the Association for Computational Linguistics: EMNLP 2020, Online Event, 16-20 November 2020_ , volume EMNLP 2020 of _Findings of ACL_ , pages 4401–4411. Association for Computational Linguistics.
  * Ma and Hovy (2016) Xuezhe Ma and Eduard Hovy. 2016.  End-to-end sequence labeling via bi-directional LSTM-CNNs-CRF.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1064–1074, Berlin, Germany. Association for Computational Linguistics.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016.  Improving neural machine translation models with monolingual data.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume 1: Long Papers_. The Association for Computer Linguistics.
  * Simard et al. (1996) Patrice Y. Simard, Yann LeCun, John S. Denker, and Bernard Victorri. 1996.  Transformation invariance in pattern recognition-tangent distance and tangent propagation.  In Genevieve B. Orr and Klaus-Robert Müller, editors, _Neural Networks: Tricks of the Trade_ , volume 1524 of _Lecture Notes in Computer Science_ , pages 239–27. Springer.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA_ , pages 5998–6008.
  * Wang et al. (2021) Zhiruo Wang, Haoyu Dong, Ran Jia, Jia Li, Zhiyi Fu, Shi Han, and Dongmei Zhang. 2021\.  TUTA: tree-based transformers for generally structured table pre-training.  In _KDD ’21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021_ , pages 1780–1790. ACM.
  * Wei and Zou (2019) Jason W. Wei and Kai Zou. 2019.  EDA: easy data augmentation techniques for boosting performance on text classification tasks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019, Hong Kong, China, November 3-7, 2019_ , pages 6381–6387. Association for Computational Linguistics.
  * Wu et al. (2018) Sen Wu, Luke Hsiao, Xiao Cheng, Braden Hancock, Theodoros Rekatsinas, Philip Levis, and Christopher Ré. 2018.  Fonduer: Knowledge base construction from richly formatted data.  In _Proceedings of the 2018 International Conference on Management of Data_ , SIGMOD ’18, page 1301–1316, New York, NY, USA. Association for Computing Machinery.
  * Yaseen and Langer (2021) Usama Yaseen and Stefan Langer. 2021.  Data augmentation for low-resource named entity recognition using backtranslation.  _CoRR_ , abs/2108.11703.
  * Yin et al. (2020) Pengcheng Yin, Graham Neubig, Wen-tau Yih, and Sebastian Riedel. 2020.  Tabert: Pretraining for joint understanding of textual and tabular data.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020_ , pages 8413–8426. Association for Computational Linguistics.
  * Yun et al. (2019) Sangdoo Yun, Dongyoon Han, Sanghyuk Chun, Seong Joon Oh, Youngjoon Yoo, and Junsuk Choe. 2019.  Cutmix: Regularization strategy to train strong classifiers with localizable features.  In _2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019, Seoul, Korea (South), October 27 - November 2, 2019_ , pages 6022–6031. IEEE.
  * Zhang et al. (2015) Xiang Zhang, Junbo Jake Zhao, and Yann LeCun. 2015.  Character-level convolutional networks for text classification.  In _Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada_ , pages 649–657.
  * Zhong et al. (2020) Victor Zhong, Mike Lewis, Sida I. Wang, and Luke Zettlemoyer. 2020.  Grounded adaptation for zero-shot executable semantic parsing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020_ , pages 6869–6882. Association for Computational Linguistics.

##  Appendix A Appendix

#### DA example

Figure 5 shows how tabular context becomes inconsistent when applying LWTR to
the table in Figure 1. The red tokens have been replaced with sampled tokens
from the training set.

Figure 5: LWTR introduces inconsistent tabular context. Red tokens have been
replaced in the original in Figure 1.

It can be seen that the QUANT entity height pressure is now physically
meaningless and neither height nor pressure are measured in Celsius.

#### Probing table context

(a) Two synthetic tables with small modifications. Top has random context,
bottom has consistent context.

(b) Unnormalized logits for token ’l’ in top and bottom table in 6(a).

Figure 6: TabNER token logits with synthetic consistent and randomized table
context.

To demonstrate the sensitivity of TabNER towards table context, we construct
two synthetic tables with slightly modified cell content. The table at the top
in Figure 6(a) has a column with header power (QUANT) with body cells having
random (inconsistent) UoM entities 8 celsius and 90 l. The bottom table’s
column with header capacity has consistent UoM context. We are interested in
how these two different contexts affect the classification of token ’l’, which
is hard to classify without context. In a column like capacity it likely
refers to the UoM entity ’liter’. However, in most other contexts ’l’ is not
part of any entity. Looking at the respective logits in Figure 6(b), we can
see that TabNER is sensitive to these context changes. The highest scoring
class for the random context is O, while in the consistent case it is the
class UoM. This is a beneficial property, since it prevents false positives
for highly ambiguous tokens such as ’l’, which only in very specific contexts
are likely to be entities.

#### Experiment Details

For fair comparison, both TabNER and BERT are based on the pre-trained ’bert-
base-uncased’ and we select the best hyperparameters from these ranges:
learning rate $\\{5e^{-5},1e^{-5},5e^{-4}\\}$, batch size $\\{2,4,8\\}$. The
learning follows a linearly decreasing schedule with a maximum of 20 epochs.
For the BiLSTM-CRF we use the NER hyperparmeters from Ma and Hovy (2016).

#### BERT Analysis

In our experiments, we observe that BERT almost exclusively fits to the O
token labels in the training set and does not pick up on the other NER
signals. Since it is an imbalanced problem, our hypothesis is that the global
attention and position encoding across the full table blurs tokens with less
frequent NER signals and BERT cannot properly fit them. More sophisticated
weighted loss functions could be tried to remedy this problem. In Figure 7 the
progress of the validation set F1 score is shown. Even though the training
loss is still slightly decreasing, the validation NER performance seems to
have already peaked. In all hyperparameter settings (even with much lower
learning rate $1e^{-7}$) we could not achieve a test F1 score higher than
0.03.

#### Class-wise F1 scores

Model | TAG | EQ | QUANT | UoM
---|---|---|---|---
RuleNER | 0.1 | 0.09 | 0.04 | 0.1
BiLSTM-CRF | 0.55 | 0.39 | 0.54 | 0.67
TabNER | 0.60 | 0.43 | 0.47 | 0.77
Table 4: Class-wise F1 scores.

As more fine-grained analysis, we present the class-wise F1 scores for each
model in Table 4. We can see that the TabNER is better in extracting entities
of types TAG, EQ and UoM, while the BiLSTM model is better at classifying
entities of type QUANT.

#### Data Augmentation Samples

We experiment with $n=1,2$ samples to evaluate if increasing the training set
by more then 100% will bring benefit to the TabNER model. Figure 7 shows the
validation set F1 score for the TabNER model with the two DA techniques, LWTR
and RDLTab, and the different $n=1,2$ samples. Consistently, for both
techniques, when $n=2$ the model converges much faster, after only $5$ epochs,
however the performance of the model is worse compared to when we use $n=1$.

Figure 7: F1 score on validation set during training.


* [10] B. Courcelle, C. Delhommé, The modular decomposition of countable graphs. Definition and construction in monadic second-order logic. _Theor. Comput. Sci._ 394 (2008) 1-38.
  * [11] B. Courcelle and J. Engelfriet, _Graph structure and monadic second-order logic, a language theoretic approach_ , Cambridge University Press, 2012.
  * [12] R. Fraïssé, _Theory of relations_ , Studies in Logic, Volume 145, North-Holland, 2000.
  * [13] P. Hlinený, S. Oum, D. Seese, G. Gottlob, Width parameters beyond tree-width and their applications. _Comput. J._ 51 (2008) 326-362.
  * [14] W. Hodges, _Model theory_ , Cambridge University Press, 1993.
  * [15] L. Libkin, _Elements of finite model theory_ , Springer, 2004.
  * [16] J. Lihova, Strict-order betweenness, _Acta Univ. M. Belii Ser. Math._ 8 (2000) 27-33. Available from https://actamath.savbb.sk/acta0804.shtml.
  * [17] S. Oum, P. Seymour, Approximating clique-width and branch-width. _J. Comb. Theory, Ser. B_ 96 (2006) 514-528.
  * [18] P. Parys: Extensions of the Caucal hierarchy,_Proceedings of LATA, Lec. Notes in Comp. Sci._ 11417, (2019) 368-380.
  * [19] W. Thomas, Constructing infinite graphs with a decidable MSO-theory. Mathematical Foundations of Computer Science 2003, Bratislava, Slovakia, _Lec. Notes in Comp. Sci_ 2747, (2003), pp. 113-124