# Towards Interoperability of Open and Permissionless Blockchains: A Cross-
Chain Query Language ††thanks: This work is partially supported by the Swiss
National Science Foundation project Domain-Specific Conceptual Modeling for
Distributed Ledger Technologies [196889].

Felix Härer  Digitalization and Information Systems Group
University of Fribourg
Fribourg, Switzerland
E-Mail<EMAIL_ADDRESS>
###### Abstract

The rise of open and permissionless blockchains has introduced novel platforms
for applications based on distributed data storage. At the application and
business levels, long-established query languages such as SQL provide
interoperability that can be complemented by blockchain-based data storage
today, enabling permissionless and verifiable data storage along with
decentralized execution across tens of thousands of nodes. However, when
accessing one or more blockchains, interoperability is not provided today,
posing challenges such as inhomogeneous data access in addition to different
features and trade-offs, e.g. in data and distribution, scalability, and
security. Towards interoperability in data access among the increasing number
of blockchain platforms, this paper introduces a cross-chain query language
for data access across blockchains. Similar to SQL, the language abstracts
from implementation based on a data model compatible with the largest open and
permissionless blockchains (OPB) today. The language, data model, and
processing architecture are demonstrated and evaluated with an implemented
prototype, aiming to contribute to the discussion on blockchain
interoperability among OPB.

###### Index Terms:

Query Languages, Distributed Systems, Blockchains, Data Models,
Interoperability

##  I Introduction

In August 2022, at least 22 well-known openly accessible blockchains exist
with a significant number of active participants, processing their
transactions over internet protocols111https://messari.io/screener/active-
adresses-15D9AE99. These systems are, in their nature, open platforms for
distributed data and applications, allowing applications of businesses or
individuals to transact through a shared ledger without centralized
coordination based on algorithmic consensus in the network [1]. Open systems
with these components - blockchain data, network, consensus protocol - are
verifiable in their operation and data by all participants, enabling novel
decentralized applications such as programmable money or contracts [2]. In
contrast to distributed systems of past decades, hundreds to thousands of
nodes establish open and permissionless platforms. Estimations based on the
connections of participating nodes count about 15000 nodes operating
Bitcoin222https://bitnodes.io/, 6000 operating
Ethereum333https://ethernodes.org/, and 3000 operating
Cardano444https://adastat.net/pools/; without accounting for additional nodes
not visible due to their configuration or placement behind routers and
firewalls. With the growing adoption, the increasing number of open and
permissionless blockchains, and the vast amounts of openly available data,
future relevance of these platforms for verifiable data storage and execution
is assumed as a premise of this paper. Applications accessing the platforms
include payments and currency, e-commerce, timestamping, and the attestation
of data and links on the web [3, 4, 5].

_Problem Statement._ Software accessing data across open and permissionless
blockchains (OPB) today faces challenges due to interoperability:

  1. 1.

Inhomogeneous access to data due to various OPB implementations.

  2. 2.

Different OPB data models and features exist.

  3. 3.

Different OPB trade-offs exist, notably regarding scalability, security, and
decentralization.

_Research Objective and Contribution._ The objective of this research is to
address the three challenges towards higher interoperability between OPB. In
the discussion on this topic, the paper contributes a cross-chain query
language by specifying a common data model, a standardized syntax, and a
processing architecture. For answering query statements written by users or
applications, data is read from multiple blockchain nodes, integrated in the
common data model, and processed according to the statements. Given the state-
of-the-art of conceptual models and query languages suggested before, such as
[6] and [7], the language design is derived abstract from implementation for
several of the largest OPB today. The proof-of-concept implementation
demonstrates feasibility and the potential for software to utilize OPB as part
of their architecture.

_Application Example._ Several e-commerce websites might take part in commonly
operated loyalty programs that issue reward points for customer purchases.
Among other industries, these programs can be found for airlines working
together555E.g. https://www.miles-and-more.com/ch/en.html. Given a cross-chain
query language, business-level applications of different airlines could re-use
and standardize data access, the underlying blockchain could be changed, and
multiple blockchains of several loyalty programs could be used from individual
applications.

The remainder of this paper is structured as follows. Section II introduces
foundations and related work. Section III discusses OPB with their properties
for the derivation of a data model. Subsequently, the data model, a grammar of
the language syntax, and a processing architecture are derived. This approach
is evaluated in Section IV with a prototype implementation utilizing multiple
OPB. Section V concludes.

##  II Foundations and Related Work

Blockchain foundations are introduced first, followed by open and permissioned
blockchains and interoperability.

###  II-A Blockchains

Following the initial publication of the Bitcoin whitepaper and software in
2008 and 2009, respectively [8, 9], the term _blockchain_ has been introduced
as a generalization of its technical architecture. The main components of (1.)
a data structure of backward-linked blocks, (2.) a peer-to-peer network for
data distribution, and (3.) a consensus protocol allow for novel properties.
Notably, coordinating and validating all operations without centralized
control, open access to all data and operations, and permissionless access
where data and operations are not restricted to specific participants [10, 2].
Ethereum, and other blockchains following it, extended the capabilities with
smart contracts as quasi Turing-complete programs [11, 12]. In addition to
payments and money, smart contracts enable e-commerce, sales contracts,
timestamping, and attestations, among other applications [13, 3, 5].

###  II-B Open and Permissionless Blockchains

Growing development and adoption originating from Bitcoin and Ethereum have
resulted in OPB with various properties. Table I lists five well-known OPB in
order of their public number of network nodes, characterized by the properties
of their data structure, network, and consensus protocols, as well as features
related to smart contracts.

TABLE I: Properties of well-known open and permissionless blockchains.

Blockchain | Data Structure |  | Network
---
Consensus Protocol |  | Smart Contract
---
Features
[1] Bitcoin666[18], https://bitnodes.io/ |  | Blocks, UTXO
---
data model
| Bitcoin, approx.
---
15000 nodes
| Nakamoto Consensus,
---
Proof-of-Work
| Stack-based script
---
execution, monetary
transactions
[2] Ethereum777[29], https://ethereum.org/en/developers/docs/, https://ethernodes.org/ |  | Blocks, account
---
state storage in tree
data structures
| Ethereum Mainnet,
---
approx.
6000 nodes
| Ethash, memory-hard
---
Proof-of-Work
| Ethereum Virtual
---
Machine, general-
purpose programs
[3] Cardano888[15], https://adastat.net/pools/ |  | Blocks, extended
---
UTXO model
| Cardano,
---
approx.
3000 nodes
| Ouroboros,
---
Proof-of-Stake
| General-purpose
---
programs,
functional
[4] Solana999[30], https://docs.solana.com, https://solanabeach.io/validators/ |  | Block and graph
---
data structures over
different time spans
| Solana Mainnet Beta,
---
approx.
1600 nodes
| Graph-based (proof-
---
-of-history), Proof-of-
Stake
| General-purpose
---
programs
[5] Avalanche101010[23], https://stats.avax.network/dashboard/network-status/ |  | Block and graph
---
data structures over
different networks
| Platform/Exchange/
---
Contract (P/X/C)
chain, approx.
1300 nodes
| Avalanche (P Chain)
---
Snowman (X/C Chain),
Proof-of-Stake
| Ethereum Virtual
---
Machine (C Chain),
general-purpose
programs

_Data Structures._ The initial design of backward-linked blocks in Bitcoin is
combined in most other OPB with additional trees or graphs. In addition to
transaction data from blocks, further queries must be carried out for non-
transactional data or older data that has been pruned. For example, separate
tree structures are present for state storage in Ethereum, where balances and
smart contract variables can be retrieved [6].

_Networks._ Major OPB networks consist of approximately 1300 to 15000 nodes.
Due to algorithmic operation and validation, higher node counts increase
security, e.g. related to 51% attacks and selfish mining [14, 15] frequently
observed in small Proof-of-Work systems such as _Bitcoin Gold_ [15].

_Consensus Protocols._ In the protocols initially created between 2008 and
2022, a shift away from Proof-of-Work to Proof-of-Stake can be observed,
introducing several trade-offs. While established blockchains such as Bitcoin
and Ethereum have been emphasizing security and decentralization over the past
years, efforts to improve efficiency and scalability are made in Cardano [16],
Avalanche [17], and Solana [18]. The tendency is reflected in work on novel
consensus protocols by the three blockchains, mostly based on Proof-of-Stake
[19, 20] with higher efficiency and advantages to environmental impact.
Avalanche and especially Solana emphasize scalability. In Solana, however,
temporary protocol failures can be observed frequently, resulting in non-
availability [21].

_Smart Contract Features._ For data queries and software applications, smart
contract features are required. In this area, Bitcoin possesses a limited
scripting language used for programmable monetary transactions and the
scalable _lightning_ overlay network [22]. The introduction of general-purpose
programming in Ethereum and others introduces greater features and complexity.
At present, most implementations are written and compiled for the Ethereum
Virtual Machine, present in Ethereum and Avalanche. Cardano and Solana possess
their own architectures with support for general-purpose programs.

###  II-C Blockchain Interoperability

Interoperability is broadly recognized for transactions across blockchains in
cross-chain swaps and similar concepts found in practice in so-called
_bridges_. In addition, standardization efforts related to inhomogeneous data
are beginning, not limited to query languages.

_Cross-Chain Swaps._ Swaps are commonly initiated through a protocol on an
initial blockchain, where tokens or arbitrary data are locked to prevent
further transfer in the beginning. A counterparty transaction is issued on a
second blockchain to the initiator of the cross-chain swap, i.e., often
another party pays for the tokens with another asset on the second chain. This
transaction includes a cryptographic proof with a secret that unlocks the
tokens on the initial chain. Finally, the counterparty withdraws tokens from
the initial chain. Various protocols on this basis and variants exist [23,
24]. In atomic cross-chain swaps [25, 26], atomicity is provided for all
transfers involved in a cross-chain swap. Implementations in bridges may, in
practice, exhibit differing properties and assurances, not necessarily
providing atomicity or other guarantees for the completion of the exchange.
Bridges exist mainly for cryptocurrency exchange, e.g.
Anyswap111111https://anyswap.exchange/ and
Connext121212https://bridge.connext.network/ allow for cross-chain swaps
between Ethereum, Avalanche, and others. Cross-chain swaps and bridges are not
standardized and do not provide homogeneous access or queries.

_Inhomogeneous Data._ Standardization efforts address inhomogeneous data with
few prior works related to inhomogeneous access. For Ethereum, [6] discusses a
conceptual schema derived from the main data structures of the blockchain. [7]
propose a query language for the content of blocks and transactions. The
language design is based on SQL in its syntax and supports concepts such as
projection and selection within Ethereum. For data analysis, a framework and
implementation based on Scala has been proposed [27], where SQL or NoSQL is
used with aggregation functions and similar analysis methods. The analysis
approach [28] describes a data warehouse and ETL process for analyzing
Ethereum data using standard SQL with a multi-dimensional data model for
queries of dimension attributes and data aggregation support. This work and
similar works might connect to multiple blockchains, however, they do not
provide homogeneous data access, queries, or simultaneous access to data of
multiple blockchains. Other works based on SQL include [29], using multiple
blockchains for populating a standard MySQL database with the third-party
service Google BigQuery. The use of third-party services as data sources
presents another problem often observed in prior work, where validation of
blockchain data is not possible or severely limited. Further approaches
include public connectors between blockchains, blockchains that integrate with
others, and hybrid approaches [30].

_Limitations of Prior Work._ In conclusion, present solutions are limited
regarding (L1.) homogeneous data access, (L2.) standardized queries, (L3.)
simultaneous access to multiple blockchains, or (L4.) blockchain data
validation. Currently, the focus is on cross-chain swaps and siloed data
analysis rather than data integration. The proposed query language addresses
these limitations by suggesting a common data model (L1.), a standardized
syntax (L2.), and a processing architecture (L3.) supporting local nodes (L4.)
of multiple blockchains.

##  III Query Language

The two following subsections describe (A.) the data model and (B.) the syntax
and processing architecture of the language. Query statements are processed
according to the architecture in subsection (B.), resulting in instances of
data model classes using data provided by APIs of local blockchain nodes.

###  III-A Data Model

The language design is based on a data model integrating the main data
structures and attributes of the OPB introduced in Section II-B. Based on
prior work and existing tools discussed in Section II-C, classes and
attributes of the five OPB have been identified, generalized, and integrated
in a common data model. Figure 1 lays out the complete data model as UML class
diagram. Table II lists the main model classes grouped into four packages for
representing the chain, block, account, and transaction concepts of the OPB.
For formulating queries, the syntax is introduced in subsection III-B.
Statements are written in terms of the classes and attributes by specifying
the source data with class and attribute names of the data model.

Figure 1: Data model of the cross-chain query language as UML class diagram.
TABLE II: Data model classes supporting the concepts of the OPB.

Chain classes | Block classes | Account classes | Transaction classes
---|---|---|---
Bitcoin chain | Blocks of transactions | - | Values (Bitcoin), UTXO
Ethereum chain | Blocks of transactions | Data storage, balances | Values (Ether),
|  |  | data incl. tokens
Cardano chain | Epochs, slots with | Addresses, data | Values, assets,
| blocks for transactions |  | data, UTXO
Solana chain | Epochs, slots for transactions | Data storage | Data incl. tokens
Avalanche P/X/C chain | P/X: transaction DAG | P/X: - | X: values, assets, UTXO
| C: blocks of transactions | C: Data storage, balances | C: Data incl. tokens

In the table and data model, the concepts of the OPB are represented by the
following classes. The chain classes represent one main network and blockchain
for Bitcoin, Ethereum, Cardano, and Solana, by the classes Chain, Network, and
ChainDescriptor of the data model. Additional test networks with their
separate blockchains, e.g. Ropsten and Görli in Ethereum, are represented by
Network and ChainDescriptor. In Avalanche, the Network class encompasses one
primary network, the first of potentially many _subnets_ , with separate
ChainDescriptor instances for the three P/X/C blockchains.

The Block and BlockDescriptor classes represent blocks with separate classes
for the status of the block, the block validation through the consensus
protocol, and the validators involved. Conceptually, blocks are described by
an ID in the form of a hash value in all blockchains, with metadata such as
timestamp and a height denoting the block number under the assumption no
changes occur to non-final blocks. For example, in Bitcoin, multiple blocks
could be found as the successor to a given block; however, only one block will
be included in the chain while the others will be discarded with _orphan_
status. In contrast, the same case is handled in Ethereum by keeping one block
in the main chain and keeping the other blocks at the same level with _ommer_
status. Blocks are not explicitly finalized in Proof-of-Work chains, allowing
for the declaration of _orphan_ or _ommer_ status for blocks found in parallel
to prior blocks of the chain. However, the probability of existing blocks
being replaced in this way decreases over time since multiple successive
parallel blocks with greater cumulative work are required. An explicit
finalization of blocks, preventing the occurrence of multiple successors, can
be found in more recent Proof-of-Stake blockchains such as Solana.

Regarding data structure, blocks are linked to one or more existing blocks of
the linkDescriptor attribute of the Block class, establishing either backward-
linked blocks or a graph, such as a directed acyclic graph (DAG) in the
Avalanche C chain. Blocks either contain transactions directly or are grouped
into time-based slots and epochs for validation purposes with Proof-of-Stake.
When appending a block, validation is carried out for each block or slot,
requiring the participation of validators. In the ValidationDescriptor class,
the creator of a block for Bitcoin and Ethereum provides validation for a
linked block by the hashValue attribute. For the other Proof-of-Stake
blockchains, proposers are recorded in the corresponding attributes with
attestations, referencing the class ValidatorDescriptor. Each instance
references any number of appointed validators attesting the correctness of the
block by means of their vote and signature. In this way, the concept of
multiple groups of validators performing attestations is represented. When
storing the transaction of a DAG, one or more transactions in a block can be
linked to one or more transactions from a preceding block, indicated by the
linkedBlockedDescriptor attribute in Block and the dagSupport attribute in
BlockDescriptor that are set _true_ in this case.

Accounts are a concept present in Ethereum, Solana, and Avalanche. Blocks
contain accounts for the storage of assets, tokens, or data used for smart
contracts. Notably, data might be used for the representation of assets or
tokens directly, such as in Solana. Each account is described by an ID with
the concept of an address being present in all blockchains. In an account, the
storage of assets or tokens can refer to custom assets, such as in Cardano, or
tokens represented by data in the general case. For tokens, token standards
such as ERC-20 in Ethereum are represented by Token class attributes. Storing
data uses binary large objects or key-value stores, utilized in hash-based
mapping data structures.

Transaction concepts in Bitcoin and Cardano differ due to the lack of accounts
in these blockchains. For this reason, transactions contain a reference to
unspent transaction outputs (UTXOs) of previous transactions. In this model, a
UTXO is included together with the transferred value and a script describing
locking conditions or containing data. While the inclusion of data is implicit
in Bitcoin, Cardano explicitly supports data in transactions and its storage
linked to an address for smart contract functionality. In the case of
Ethereum, Solana, and the Avalanche C chain, transactions are stored for the
transfer of values, data, assets, or tokens between accounts. In the Avalanche
X chain, the transfer of native assets is supported through the UTXO concept.
In the data model, the attributes of Transaction and TransactionDescriptor
allow for transfers between addresses by utilization of the attributes
corresponding to the aforementioned concepts.

###  III-B Language Syntax and Processing Architecture

The language syntax is based on established concepts of data query languages,
in particular the Structured Query Language (SQL). On the one hand, the syntax
of SQL and similar languages allow the representation of queries in a
formalized way through relational algebra. On the other hand, queries and
their articulation are accessible to domain experts without detailed knowledge
of the underlying concepts. The SQL syntax is centered around the _SELECT-
FROM-WHERE_ block (SFW block). Based on English-language commands, the
_SELECT_ clause will perform a projection in the underlying relational model,
semantically corresponding to columns, followed by the source of the relations
in the _FROM_ clause and the selection of tuples using conditions in the
_WHERE_ clause. In the relational model, set operations, and notably the
Cartesian product, are the basis for all queries. For a cross-chain data
language, these concepts are applied as follows.

_Query Requirements._ The syntax of query statements consists of query (Q),
source (S), and filter (F) clauses:

  * Q

Query attributes are any attributes of the data model classes. Each attribute
must be specified together with its class, determining one column of the query
result for each source.

  * S

Sources specify blockchains and networks, optionally together with blocks,
transactions, and accounts with assets, tokens, and data. In terms of the data
model, each source must be specified by the attribute values of the
identifying attributes of the Chain, Network, and ChainDescriptor classes.
Optionally, an additional class, attribute, and attribute value of an
identifying attribute from the classes Block, Transaction, Account, Asset,
Token, or Data can be specified.

  * F

Filters are optional conditions filtering the query results by query
attributes and sources. Each filter must be specified by a filter function for
comparisons with two inputs using query attributes. On the result values from
the query attributes, specified filters are applied in sequence.

Figure 2: Architecture for processing queries within an application.

_Grammar._ According to these requirements, Listing 1 partially shows the
syntax definition131313Complete grammar:
https://github.com/fhaer/CCQL/tree/main/grammar. In the grammar excerpt, the
query statement syntax is described using the W3C variant of the Extended
Backus Naur Form (EBNF) [31]. The query, source, and filter clauses specify
projections, source data, and selections, respectively. In each clause, the
specification of multiple values entails processing multiple result sets, in
the case of SourceSpec for triggering the retrieval of data from multiple
blockchains. Additionally, sources specify a chain, network, and chain
descriptor with an optional block, transaction, or account according to the
data model and requirements. Accounts storing assets, tokens, or data are
accessed by the respective classes shown in the data model. The source and
filter specifications are further detailed with the full EBNF grammar
specification in the implementation.

⬇

1QueryStatement ::=

2 QueryAttrClause

3 SourceClause

4 FilterClause? ";"

5QueryAttrClause ::=

6 ’Q ’ AttrSpec ( ’, ’ AttrSpec )*

7SourceClause ::=

8 ’S ’ SourceSpec ( ’, ’ SourceSpec )*

9FilterClause ::=

10 ’F ’ FilterSpec ( ’, ’ FilterSpec )*

11AttrSpec ::=

12 CCQLClass ’.’ AttrName

13SourceSpec ::=

14 BlockchainI ’:’ NetI ’:’ ChainDescI

15 (’:’ ( BlockI | TxI | AccI ) )?

16FilterSpec ::=

17 CCQLClass ’.’ AttrName ComparisonFunction IValue

Listing 1: EBNF excerpt. Attr: Attribute, Spec: Specification, Val: Value,
Desc: Descriptor, I: Instance, Net: Network, Tx: Transaction, Acc: Account.

_Processing Architecture._ The processing of queries within the architecture
is described in Figure 2. In an application connected to local nodes of
blockchain platforms, query statements are issued to the parser component.
After building the clauses, the query processing component first iterates the
source clause, issuing for each SourceSpec and for each attribute API calls to
the blockchain nodes. According to the classes and attributes, instances are
created in the data model. Second, the query clause iterates each AttrSpec by
selecting the corresponding classes from the model and producing columns in
the result table. For the objects of the classes, rows are appended. Third,
the filter clause applies each filter function. Finally, the result table
contains the query result.

##  IV Evaluation of Feasibility

The aim of this section is a demonstration of feasibility for the query
language, its data model, and the processing architecture. For this purpose,
an implementation compatible to the introduced OBP has been developed,
consisting of a formal language grammar and a prototype
application141414Available at https://github.com/fhaer/CCQL/tree/main. The
grammar is realized with the Eclipse Modeling Framework and
Xtext151515https://www.eclipse.org/Xtext to establish an external domain-
specific language (DSL) based on it. In principle, the grammar is
implementation independent and might be re-used in further applications. The
language is implemented in a prototype command-line application together with
the data model according to the proposed architecture, involving node access
to the selected OPB for query execution. The prototype is written in Python
3.9 and utilizes the web3.py library for OPB
access161616https://web3py.readthedocs.io/en/stable/.

###  IV-A Software Setup

Setting up the application involved the following blockchain nodes with a
configuration that fully validates all blocks:

  * •

Bitcoin node: Bitcoin Core, version 22.0171717https://bitcoin.org/de/download.
Initial data synchronization completed after 4 days.

  * •

Ethereum node: go ethereum (geth181818https://geth.ethereum.org/downloads/),
version 1.10.510 with tracing and indexing of all transactions, and pruning of
ancient block data. Initial data synchronization completed after approximately
12 weeks.

  * •

Cardano node: Cardano node, version 1.34191919https://github.com/input-output-
hk/cardano-node. Initial data synchronization completed after approximately 2
days.

  * •

Avalanche node: AvalancheGo, version 1.77202020https://github.com/ava-
labs/avalanchego/releases. Initial data synchronization completed after
approximately 4 days.

Figure 3: Query example 1. Figure 4: Query example 2.

The synchronizations were made on a PC with a AMD 3700X CPU, 32 GB RAM, and
Samsung 980 Pro NVMe SSD, behind a 1 Gbit/s fiber internet connection. After
the synchronizations, nodes and data were transferred to a typical end-user
device, a laptop with AMD 5700U CPU, 16 GB RAM, and SK Hynix BC711 NVMe SSD.
Both machines were running Ubuntu 21.10.

In order to demonstrate feasibility, query statements were evaluated with the
prototype, as discussed in the following section. Each statement was executed
on the laptop device, with local data retrieval from the blockchain node
software according to the processing architecture. Given the local and fully-
validating configuration of the node software, query results can be produced
without network access. Query performance, therefore, does not depend on
network latency and is limited only by local CPU and IO performance.

###  IV-B Prototype Operation

The architecture of the prototype is represented in Figure 2 and generally
explained in Section III-B, _Processing Architecture_. In the following, two
example queries are discussed.

The common task of locating transactions in a block is shown in Figure 3. The
query attributes specify Block and BlockDescriptor (BlockDesc) classes with
attributes of the block ID, Height, Timestamp, and transactions. Ethereum, its
main network, chain 1, and block follow as source clause. Finally, a filter
with a timestamp is applied. In the query results, data model classes and
attributes such as Block.id and Block.height can be seen with their
corresponding values, e.g. 0xfb2e[...] and 14505661, respectively.

With similar classes and attributes, the second example in Figure 4 shows a
query common in a cross-chain swap scenario, retrieving transaction data from
Ethereum and Avalanche. The query results show the attributes prefixed by the
number of the source with instance-level data from the data model with
corresponding values, with blocks and transaction identifiers as hexadecimal
hash values.

###  IV-C Discussion

The prototype implements homogeneous data access to OPB, e.g. retrieving asset
and data transfers from multiple blockchains. According to the grammar, data
access is standardized and allows for statements involving one or more
blockchains. For utilizing blockchain properties in a meaningful way, running
blockchain nodes locally is required, involving substantial time and cost for
initial synchronizations. The data model architecture follows a data
integration approach, where data can be stored according to today’s major OPB
by populating relevant classes. In contrast, an approach of multiple
individual data models alone would not address the problem at hand. General
limitations of the prototype in its current stage are limited support for
advanced concepts of the OPB, e.g. the calculation of transaction fees
involving further utility tokens is outside the model. In terms of
functionality, the queries with filters are limited in the prototype, only
allowing for inner joins and equality comparisons.

##  V Conclusion

In this paper, a cross-chain query language grammar, data model, and
processing architecture are introduced for homogeneous data access across
multiple blockchains. The approach supports homogeneous data access,
standardization of queries, addressing of multiple blockchains in individual
queries, and local validation of blockchain data. Prior research only covered
these aspects partially. The feasibility of the approach could be positively
evaluated with a prototype, despite functional limitations present in the
implementation. In principle, software applications can utilize such an
integrated approach for storing data on open and permissionless blockchains,
independent of their implementation and openly available. Future research will
further evaluate and extend the language design, data model, and architecture
toward execution capabilities.

## References

  * [1] M. Belotti, N. Bozic, G. Pujolle, and S. Secci, “A Vademecum on Blockchain Technologies: When, Which, and How,” _IEEE Communications Surveys & Tutorials_, vol. 21, no. 4, pp. 3796–3838, 2019, 10.1109/COMST.2019.2928178.
  * [2] A. M. Antonopoulos and G. Wood, _Mastering Ethereum: Building Smart Contracts and DApps_. O’Reilly Media, 2019.
  * [3] A. Narayanan and J. Clark, “Bitcoin’s academic pedigree,” _Communications of the ACM_ , vol. 60, no. 12, pp. 36–45, 2017, 10.1145/3132259.
  * [4] I. Weber and M. Staples, “Programmable money: Next-generation conditional payments using blockchain,” in _11th International Conference on Cloud Computing and Services Science - CLOSER,_ , INSTICC. SciTePress, 2021, pp. 7–14, 10.5220/0010535800070014.
  * [5] F. Härer and H.-G. Fill, “Decentralized attestation and distribution of information using blockchains and multi-protocol storage,” _IEEE Access_ , vol. 10, pp. 18 035–18 054, 2022, 10.1109/ACCESS.2022.3150356.
  * [6] A. Olivé, “The Conceptual Schema of Ethereum,” in _Conceptual Modeling_ , G. Dobbie, U. Frank, G. Kappel, S. W. Liddle, and H. C. Mayr, Eds. Cham: Springer International Publishing, 2020, pp. 418–428, 10.1007/978-3-030-62522-1_31.
  * [7] S. Bragagnolo, H. Rocha, M. Denker, and S. Ducasse, “Ethereum query language,” in _1st International Workshop on Emerging Trends in Software Engineering for Blockchain_. ACM, 2018, 10.1145/3194113.3194114.
  * [8] S. Nakamoto, “Bitcoin: A Peer-to-Peer Electronic Cash System,” Tech. Rep., 2008. [Online]. Available: https://bitcoin.org/bitcoin.pdf
  * [9] ——, “Bitcoin - A software-based online payment system,” 2009. [Online]. Available: https://sourceforge.net/p/bitcoin/news/
  * [10] J. Garay, A. Kiayias, and N. Leonardos, “The Bitcoin Backbone Protocol: Analysis and Applications,” in _EUROCRYPT 2015_. Springer, 2015, 10.1007/978-3-662-46803-6.
  * [11] G. Wood, “Ethereum: A secure decentralised generalised transaction ledger,” Ethereum, Tech. Rep., 2022. [Online]. Available: https://ethereum.github.io/yellowpaper/paper.pdf
  * [12] V. Buterin, “Ethereum: A Next-Generation Smart Contract and Decentralized Application Platform,” Tech. Rep., 2014. [Online]. Available: https://ethereum.org/en/whitepaper/
  * [13] J. Ladleif and M. Weske, “A Unifying Model of Legal Smart Contracts,” in _Conceptual Modeling_. Cham: Springer International Publishing, 2019, pp. 323–337, 10.1007/978-3-030-33223-5_27.
  * [14] M. K. Shrivas, T. Y. Dean, and S. S. Brunda, “The Disruptive Blockchain Security Threats and Threat Categorization,” in _2020 First International Conference on Power, Control and Computing Technologies (ICPC2T)_. Raipur, India: IEEE, 2020, 10.1109/ICPC2T48082.2020.9071475.
  * [15] M. Saad, J. Spaulding, L. Njilla, C. Kamhoua, S. Shetty, D. Nyang, and D. Mohaisen, “Exploring the Attack Surface of Blockchain: A Comprehensive Survey,” _IEEE Communications Surveys & Tutorials_, vol. 22, no. 3, 2020, 10.1109/COMST.2020.2975999.
  * [16] A. Kiayias, A. Russell, B. David, and R. Oliynykov, “Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol,” Tech. Rep. 889, 2016. [Online]. Available: https://eprint.iacr.org/2016/889
  * [17] T. Rocket, M. Yin, K. Sekniqi, R. van Renesse, and E. G. Sirer, “Scalable and Probabilistic Leaderless BFT Consensus through Metastability,” _arXiv:1906.08936 [cs]_ , 2020, 10.48550/arXiv.1906.08936.
  * [18] A. Yakovenko, “Solana: A new architecture for a high performance blockchain v0.8.14,” Solana, Tech. Rep., 2018. [Online]. Available: https://github.com/solana-labs/whitepaper/blob/master/solana-whitepaper-en.pdf
  * [19] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich, “Algorand: Scaling Byzantine Agreements for Cryptocurrencies,” in _26th Symposium on Operating Systems Principles_ , ser. SOSP ’17. ACM, 2017, 10.1145/3132747.3132757.
  * [20] Ethereum, “Proof-of-stake (PoS),” 2022. [Online]. Available: https://ethereum.org/en/developers/docs/consensus-mechanisms/pos/
  * [21] A. Hayward, “Solana Blames ‘Denial of Service Attack’ for Last Week’s Downtime,” 2021. [Online]. Available: https://decrypt.co/81375/solana-blames-denial-of-service-attack-for-last-weeks-downtime
  * [22] A. M. Antonopoulos, R. Pickhardt, and O. Osuntokun, _Mastering the Lightning Network_. O’Reilly Media, 2021.
  * [23] B. Pillai, K. Biswas, and V. Muthukkumarasamy, “Cross-chain interoperability among blockchain-based systems using transactions,” _The Knowledge Engineering Review_ , vol. 35, 2020, 10.1017/S0269888920000314.
  * [24] N. Shadab, F. Houshmand, and M. Lesani, “Cross-chain Transactions,” in _2020 IEEE International Conference on Blockchain and Cryptocurrency (ICBC)_. IEEE, 2020, 10.1109/ICBC48266.2020.9169477.
  * [25] M. Herlihy, “Atomic Cross-Chain Swaps,” in _2018 ACM Symposium on Principles of Distributed Computing_. Egham United Kingdom: ACM, 2018, pp. 245–254, 10.1145/3212734.3212736.
  * [26] V. Zakhary, D. Agrawal, and A. El Abbadi, “Atomic commitment across blockchains,” _Proceedings of the VLDB Endowment_ , vol. 13, no. 9, pp. 1319–1331, 2020, 10.14778/3397230.3397231.
  * [27] M. Bartoletti, S. Lande, L. Pompianu, and A. Bracciali, “A general framework for blockchain analytics,” in _1st Workshop on Scalable and Resilient Infrastructures for Distributed Ledgers_ , ser. SERIAL ’17. New York, NY, USA: ACM, 2017, pp. 1–6, 10.1145/3152824.3152831.
  * [28] G. Camozzi, F. Härer, and H.-G. Fill, “Multidimensional Analysis of Blockchain Data Using an ETL-based Approach,” in _Wirtschaftsinformatik 2022 Proceedings_ , 2022.
  * [29] I. Liiv, “Exploration with Structured Query Language,” in _Data Science Techniques for Cryptocurrency Blockchains_ , ser. Behaviormetrics: Quantitative Approaches to Human Behavior. Springer, 2021. [Online]. Available: http://doi.org/10.1007/978-981-16-2418-6_2
  * [30] R. Belchior, A. Vasconcelos, S. Guerreiro, and M. Correia, “A Survey on Blockchain Interoperability: Past, Present, and Future Trends,” _arXiv:2005.14282 [cs]_ , 2021, 10.48550/arXiv.2005.14282.
  * [31] W3C, “Blindfold Grammars,” 2001. [Online]. Available: https://www.w3.org/2001/06/blindfold/grammar


Authors’ Instructions

# Context-Aware Learning using Transferable Features for Classification of
Breast Cancer Histology Images

Ruqayya Awan Joint co-authors Department of Computer Science, University of
Warwick, Coventry, UK  Navid Alemi KoohbananiContext-Aware Learning using
Transferable Features for Classification of Breast Cancer Histology Images
Department of Computer Science, University of Warwick, Coventry, UK  The Alan
Turing Institute, London, UK  Muhammad Shaban  Department of Computer Science,
University of Warwick, Coventry, UK  Anna Lisowska  Department of Computer
Science, University of Warwick, Coventry, UK  Nasir Rajpoot  Department of
Computer Science, University of Warwick, Coventry, UK  The Alan Turing
Institute, London, UK  Department of Pathology, University Hospitals Coventry
& Warwickshire, UK

###### Abstract

Convolutional neural networks (CNNs) have been recently used for a variety of
histology image analysis. However, availability of a large dataset is a major
prerequisite for training a CNN which limits its use by the computational
pathology community. In previous studies, CNNs have demonstrated their
potential in terms of feature generalizability and transferability accompanied
with better performance. Considering these traits of CNN, we propose a simple
yet effective method which leverages the strengths of CNN combined with the
advantages of including contextual information, particularly designed for a
small dataset. Our method consists of two main steps: first it uses the
activation features of CNN trained for a patch-based classification and then
it trains a separate classifier using features of overlapping patches to
perform image-based classification using the contextual information. The
proposed framework outperformed the state-of-the-art method for breast cancer
classification.

###### Keywords:

Digital pathology, Convolutional neural network, Context-aware learning,
Transferable features, Breast cancer

##  1 Introduction

Breast cancer is the most common type of cancer diagnosed and is the second
most common type of cancer with high mortality rate after lung cancer in women
[1]. Due to the increased incidence of breast cancer and subjectivity in
diagnosis, there is an increasing demand for automated systems. To this end,
deep neural networks (DNNs) have been widely used to produce the state-of-the-
art results for a variety of histology image analysis tasks such as nuclei
detection and classification [2], tissue classification [3, 4] and
segmentation [5, 6].

The CAMELYON16 challenge [6] is the best demonstration of using deep learning
for automatic tissue analysis, outperforming the pathologists in terms of
detection of tumors within the whole slide images (WSIs). The objective of
this challenge was to automatically detect the metastasis in haematoxylin and
eosin (H&E) stained WSIs of lymph node sections. Cruz-Roa _et al._ [3]
presented a deep learning architecture for automated basal carcinoma
detection. This method first learns image representation via autoencoder and
then a CNN is applied on this representation to capture both translation
invariant features and a compact image representation. Spanhol _et al._ [7]
applied a simple CNN for classifying the BreaKHis database [8] consisting of
microscopic images of benign and malignant breast tumor biopsies. Small
patches were extracted at different magnification levels to train the network
and during inference, final output was produced by combining the predictions
of the small patches.

The generalizability property of DNN makes their features transferable to
other applications which encouraged the researchers to employ transfer
learning for histology images as in [5, 9, 10]. These features have also been
used to train separate classifiers for predictions [11, 12, 13, 14], which are
particularly useful when there is not enough dataset for training the CNN from
scratch. In some recent studies [15, 16], context-aware based learning
architecture has been introduced, in which first CNN is trained using high
pixel resolution patches to extract features at a cellular level that are then
fed to a second CNN, stacked on top of the first for expanding the context
from a single patch to a large tissue region. The experimental results of
these studies suggest that the contextual information plays a crucial role in
identifying abnormalities in heterogeneous tissue structures.

Our contribution in this work is twofold. First, we propose to use CNN
features as a generic descriptor for a small dataset, provided as a part of a
challenge dataset. We extract transferable features from a number of networks,
each trained on a different dataset for the purpose of classification by a
separate classifier trained on these features. As our second contribution, we
combine these features to learn context of a large patch to improve our
classification performance. To this end, we use transferable features for a
block of consecutive patches to train a SVM model to classify the H&E stained
breast images into normal, benign, carcinoma _insitu_ (CIS) and breast
invasive carcinoma (BIC).

##  2 Dataset and Experimental Setup

We used the dataset provided as a part of the ICIAR 2018 challenge for the
classification of breast cancer histology images. This dataset comprises of
400 high resolution images of size 2048$\times$1536 pixels at 20$\times$
magnification, stained with H&E stain. The pixel resolution for these images
is 0.42 $\mu$m. Each image belongs to one of the four classes: normal, benign,
_insitu_ carcinoma or invasive carcinoma. The ground truth was provided by the
two pathologists. To study the feature transferability of CNN, we experimented
with other part of the challenge dataset provided for segmentation task. Ten
WSIs with coarse annotations were provided for this task. We extracted patches
from these WSIs after manually refining the original annotations.

The challenge dataset for a classification task consists of training images
used in [14] along with 151 additional images. To evaluate the effectiveness
of our proposed approach, we splitted the challenge dataset for two settings.
In the first setting, we use the same images for training and testing which
were used in [14] for a fair comparison. We included the additional images in
our validation set while training the network. The test dataset contains two
set of images, with equal number of images in each class. The testing data is
not provided with the challenge data but is made publicly available by the
authors in two sets. The first test set contains 20 images while the second
set contains 16 images and is referred as ’test extended’ dataset in this
paper. In the second setting which is used for submission to the challenge, we
combined the whole challenge dataset from task-1 and the test dataset and
randomly split them into 75% training and 25% validation set.

Regarding the implementation, we used residual neural network with 50 layers
for patch-based classification in Tensorflow. For context-aware image-based
classification, support vector machine (SVM) classifier with radial basis
function (RBF) was used and implemented in MATLAB. Further details on both
these steps are given in the Methods section.

##  3 Methods

In this paper, we introduce an effective model for the purpose of image-based
classification using more context information, particularly for a small
dataset. To this end, we design our model in two main steps: patch-based
classification and context-aware image-based classification. The overall
system architecture is shown in Figure 1.

Figure 1: Flow Diagram of our classification framework. Twelve non-overlapping
patches are extracted from the input image. A 8192-dimensional feature vector
is then obtained for each patch using a trained ResNet. The class label for
the overlapping blocks (2$\times$2) of features is obtained from the SVM model
after reducing the dimensionality. The final image-based prediction is made
using the majority voting approach.

###  3.1 Preprocessing

Stain inconsistency of digitized WSIs is a significant issue affecting the
performance of machine learning (ML) systems. The dataset provided for this
challenge contains images with large stain variation. To this end, we
performed stain normalization using the Reinhard method [17], available in our
group’s Stain Normalization Toolbox [18]. This method transforms the color
distribution of an image to the color distribution of a target image by
matching the mean and standard deviation of the source image to that of target
image. This transformation is carried out for each channel separately, in the
Lab colorspace.

Figure 2: Output of stain normalization: A, B and C show the target image, the
original image and the stain normalized version of B respectively.

###  3.2 Patch-based classification

ResNet [19] introduced in 2015 by Microsoft has been shown to outperform
several architectures including VGG [20], GoogleNet [21], PReLU-net [22] and
BN-inception [23]. This network also outperformed best performing networks
with a significant margin for the classification of histopathology colorectal
images [24]. The state-of-the-art results of ResNet on different datasets
motivated us to use it for our patch-based classification. For our
experiments, we used ResNet with 50 layers. For network training, overlapping
patches of size 512$\times$512 pixels were extracted from the images. The
network was trained for 16 epochs with batch size of 12 and the best trained
network was selected for further processing. The training was done using
stochastic gradient descent with momentum set to 0.95. The learning rate was
initially set to 0.001 and was decremented after each update. Due to the very
small dataset and also to make our network robust to feature transformation,
we performed data augmentation involving random rotation (90 to 360 degrees
with step of 90 degrees) and flipping during the training stage.

###  3.3 Context-aware image-wise classification

The above patch-based classification network learns a limited contextual
representation for each class by using small patches of size 512$\times$512
pixels. To train a classifier with larger context, we divided each image into
twelve non-overlapping patches and for each patch, we then extracted 8192
dimensional feature vector from the last layer of our patch-based network. We
then trained an SVM classifier with the flattened features of 2$\times$2
overlapping blocks of patches which is equivalent to training the classifier
with the features of patch 1024$\times$1024 pixels in size. Principal
component analysis (PCA) was performed to reduce the dimensionality. The image
level label was then decided by majority voting on the labels of overlapping
blocks. This approach has been shown to improve the results in previous
studies by training a CNN using the features of bigger blocks of patches. Due
to the limited availability of dataset for training, we chose to train an SVM
classifier rather than a CNN. To increase the number of samples for SVM
training, we augmented the training samples using rotation and flipping.

##  4 Experimental Results

For the evaluation of our proposed method, we experimented with different
configurations to show the significance of contextual information, effect of
feature transferability using networks trained on different datasets and also
to compare our method with the results of [14].

Firstly, we experimented with contextual information captured from the varying
size of block of patches. We trained SVM with the context of 1$\times$1 block
(512$\times$512 pixels), 2$\times$2 block (1024$\times$1024 pixels) and
3$\times$3 block (1536$\times$1536 pixels) of patches. As shown in Figure 3
(a), we obtained better accuracy with 2$\times$2 block as compared to the
1$\times$1 block but we observed a decline in accuracy for 3$\times$3 block of
context. It is due to the fact that the increase in context using the large
block of patches reduces the amount of data for training SVM. Otherwise,
incorporating a larger context could have improved our results if we had
enough dataset. For our further experiments, we used 2$\times$2 block of
context for classification.

To study the feature transferability, we used activation features from three
networks, each trained on a different dataset: training images used in [14],
challenge dataset (WSIs) for segmentation task and the Camelyon dataset [6].
To enrich the SVM training, we added half of the additional challenge dataset
to our training set. Our results demonstrate that the features learned by the
first network tend to provide the most appropriate representation for training
the SVM. The network trained on the WSIs has been shown to be the second best
feature descriptor as the dataset used to train this network is similar to the
evaluation data. While our third network, since it is trained on a completely
different dataset did not perform well as compared to the other networks.

For comparative analysis of our proposed method, we compared our results with
the results of previously published work of the organizers of BACH challenge
[14]. For a fair comparison, we used the same dataset as in [14] for training
and testing. Along with 4-class classification, we also present comparison
using 2-class classification, for which we grouped normal and benign images in
one class while CIS and BIC were grouped in the other class. The 2-class and
4-class comparative results are shown in Figure 3 (c) and (d) respectively.
Our method achieved higher accuracy compared to [14] which demonstrates the
capability of the contextual information for discriminating different classes.

Figure 3: Summary of our experimental results. (a) Accuracy obtained using the
context of various size of blocks where Context(1$\times$1),
Context(2$\times$2) and Context(3$\times$3) represent contextual block of size
512$\times$512, 1024$\times$1024 and 1536$\times$1537 pixels. (b) Analysis of
transferable features using three networks, each trained with a different
dataset where BACH, WSI and Camelyon16 represent challenge dataset for
classification, challenge dataset for segmentation and Camelyon16 challenge
dataset respectively. (c) and (d) show comparative analysis of our approach
with the previous study [14] using both 2-class and 4-class classification
respectively.

##  5 Conclusion

In this paper, we proposed a context-aware network for automated
classification of breast cancer histology images. The proposed method
leverages the power of CNNs to encode the representation of a patch into high
dimensional space and uses traditional machine method (SVM) to aggregate the
contextual information from the high dimensional features while having a
limited dataset. Our proposed approach outperformed the existing methods
proposed for the same task. The proposed method is not limited to breast
cancer classification task. It could be applied to other problems where both
high resolution and contextual information are required to make an optimal
prediction.

## References

  * [1] R. L. Siegel, K. D. Miller, and A. Jemal, “Cancer statistics, 2016,” CA: a cancer journal for clinicians, vol. 66, no. 1, pp. 7–30, 2016.
  * [2] K. Sirinukunwattana, S. E. A. Raza, Y.-W. Tsang, D. R. Snead, I. A. Cree, and N. M. Rajpoot, “Locality sensitive deep learning for detection and classification of nuclei in routine colon cancer histology images,” IEEE transactions on medical imaging, vol. 35, no. 5, pp. 1196–1206, 2016.
  * [3] A. Cruz-Roa, A. Basavanhally, F. González, H. Gilmore, M. Feldman, S. Ganesan, N. Shih, J. Tomaszewski, and A. Madabhushi, “Automatic detection of invasive ductal carcinoma in whole slide images with convolutional neural networks,” in SPIE medical imaging, vol. 9041, pp. 904103–904103, International Society for Optics and Photonics, 2014.
  * [4] D. Wang, A. Khosla, R. Gargeya, H. Irshad, and A. H. Beck, “Deep learning for identifying metastatic breast cancer,” arXiv preprint arXiv:1606.05718, 2016.
  * [5] H. Chen, X. Qi, L. Yu, and P.-A. Heng, “Dcan: Deep contour-aware networks for accurate gland segmentation,” in Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 2487–2496, 2016.
  * [6] B. E. Bejnordi, M. Veta, P. J. van Diest, B. van Ginneken, N. Karssemeijer, G. Litjens, J. A. van der Laak, M. Hermsen, Q. F. Manson, M. Balkenhol, et al., “Diagnostic assessment of deep learning algorithms for detection of lymph node metastases in women with breast cancer,” Jama, vol. 318, no. 22, pp. 2199–2210, 2017.
  * [7] F. A. Spanhol, L. S. Oliveira, C. Petitjean, and L. Heutte, “Breast cancer histopathological image classification using convolutional neural networks,” in Neural Networks (IJCNN), 2016 International Joint Conference on, pp. 2560–2567, IEEE, 2016.
  * [8] F. A. Spanhol, L. S. Oliveira, C. Petitjean, and L. Heutte, “A dataset for breast cancer histopathological image classification,” IEEE Transactions on Biomedical Engineering, vol. 63, no. 7, pp. 1455–1462, 2016\.
  * [9] N. Bayramoglu and J. Heikkilä, “Transfer learning for cell nuclei classification in histopathology images,” in Computer Vision–ECCV 2016 Workshops, pp. 532–539, Springer, 2016.
  * [10] Z. Han, B. Wei, Y. Zheng, Y. Yin, K. Li, and S. Li, “Breast cancer multi-classification from histopathological images with structured deep learning model,” Scientific reports, vol. 7, no. 1, p. 4172, 2017.
  * [11] Y. Xu, Z. Jia, L.-B. Wang, Y. Ai, F. Zhang, M. Lai, I. Eric, and C. Chang, “Large scale tissue histopathology image classification, segmentation, and visualization via deep convolutional activation features,” BMC bioinformatics, vol. 18, no. 1, p. 281, 2017.
  * [12] M. Valkonen, K. Kartasalo, K. Liimatainen, M. Nykter, L. Latonen, and P. Ruusuvuori, “Dual structured convolutional neural network with feature augmentation for quantitative characterization of tissue histology,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 27–35, 2017.
  * [13] Y. Xu, Z. Jia, Y. Ai, F. Zhang, M. Lai, I. Eric, and C. Chang, “Deep convolutional activation features for large scale brain tumor histopathology image classification and segmentation,” in Acoustics, Speech and Signal Processing (ICASSP), 2015 IEEE International Conference on, pp. 947–951, IEEE, 2015.
  * [14] T. Araújo, G. Aresta, E. Castro, J. Rouco, P. Aguiar, C. Eloy, A. Polónia, and A. Campilho, “Classification of breast cancer histology images using convolutional neural networks,” PloS one, vol. 12, no. 6, p. e0177544, 2017.
  * [15] A. Agarwalla, M. Shaban, and N. M. Rajpoot, “Representation-aggregation networks for segmentation of multi-gigapixel histology images,” arXiv preprint arXiv:1707.08814, 2017.
  * [16] B. E. Bejnordi, G. Zuidhof, M. Balkenhol, M. Hermsen, P. Bult, B. van Ginneken, N. Karssemeijer, G. Litjens, and J. van der Laak, “Context-aware stacked convolutional neural networks for classification of breast carcinomas in whole-slide histopathology images,” arXiv preprint arXiv:1705.03678, 2017\.
  * [17] E. Reinhard, M. Adhikhmin, B. Gooch, and P. Shirley, “Color transfer between images,” IEEE Computer graphics and applications, vol. 21, no. 5, pp. 34–41, 2001.
  * [18] A. M. Khan, N. Rajpoot, D. Treanor, and D. Magee, “A nonlinear mapping approach to stain normalization in digital histopathology images using image-specific color deconvolution,” IEEE Transactions on Biomedical Engineering, vol. 61, no. 6, pp. 1729–1738, 2014.
  * [19] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
  * [20] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” arXiv preprint arXiv:1409.1556, 2014.
  * [21] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, “Going deeper with convolutions,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1–9, 2015.
  * [22] K. He, X. Zhang, S. Ren, and J. Sun, “Delving deep into rectifiers: Surpassing human-level performance on imagenet classification,” in Proceedings of the IEEE international conference on computer vision, pp. 1026–1034, 2015.
  * [23] S. Ioffe and C. Szegedy, “Batch normalization: Accelerating deep network training by reducing internal covariate shift,” in International Conference on Machine Learning, pp. 448–456, 2015.
  * [24] B. Korbar, A. M. Olofson, A. P. Miraflor, K. M. Nicka, M. A. Suriawinata, L. Torresani, A. A. Suriawinata, and S. Hassanpour, “Deep-learning for classification of colorectal polyps on whole-slide images,” arXiv preprint arXiv:1703.01550, 2017.


# Comparison of Current Approaches to Lemmatization: A Case Study in Estonian

Aleksei Dorkin
Institute of Computer Science
University of Tartu
<EMAIL_ADDRESS>
Kairit Sirts
Institute of Computer Science
University of Tartu
<EMAIL_ADDRESS>

###### Abstract

This study evaluates three different lemmatization approaches to
Estonian—Generative character-level models, Pattern-based word-level
classification models, and rule-based morphological analysis. According to our
experiments, a significantly smaller Generative model consistently outperforms
the Pattern-based classification model based on EstBERT. Additionally, we
observe a relatively small overlap in errors made by all three models,
indicating that an ensemble of different approaches could lead to
improvements.

##  1 Introduction

Recently, two different approaches have been adopted for model-based
lemmatization. The Generative approach is based on encoder-decoder models and
they generate the lemma character by character conditioned on the word form
with its relevant context Qi et al. (2020); Bergmanis and Goldwater (2018).
The Pattern-based approach treats lemmatization as a classification task
Straka (2018), where each class is a transformation rule. When the correct
rule is applied to a word-form, it unambiguously transforms the word-form to
its lemma. .

Our aim in this paper is to compare the performance of these two lemmatization
approaches in Estonian. As a third approach, we also adopt the Estonian rule-
based lemmatizer Vabamorf Kaalep and Vaino (2001). As all three approaches
rely on different formalisms to lemmatization, we are also interested in the
complementarity of these methods. The Generative approach is the most
flexible, it has the largest search space and therefore it can occasionally
result in hallucinating non-existing morphological transformations. On the
other hand, the search space of the Pattern-based approach is much smaller as
the model only has to correctly choose a single transformation class. However,
if the required transformation is not present in the set of classes then the
model is blocked from making the correct prediction. Similarly, the rule-based
system can be highly precise but if it encounters a word that is absent from
its dictionary the system can be clueless even if this word is morphologically
highly regular.

One problem with the recently proposed pattern-based approach implemented in
the UDPipe2 is that the transformation rules mix the casing and morphological
transformations. This means that for many morphological transformations there
will be two rules in the ruleset—one for the lower-cased version of the word
and another for the same word with the capital initial letter that needs to be
lowered for the lemma—which increases the size of the ruleset considerably and
thus artificially complicates the prediction task. Thus, in many cases a more
optimal approach would be to treat casing separately from the lemmatization.
Additionally, in the UD Estonian treebanks, lemmas include annotations of
derivational and compounding processes marked by special symbols. However,
these annotations are inconsistent in the data which confuses the models and
also complicates the transformation rules. Thus, for our evaluation to be
unaffected by these factors, we also train our models on the lowercased data
with the special symbols removed.

(a) Generative approach.

(b) Pattern-based approach.

Figure 1: Schematic representations of the generative and pattern-based
approaches.

Lemmatization models are commonly token-based, meaning that if the same word-
form (with its relevant context) appears several times in the dataset, these
repeating instances are kept in the data and thus the training and evaluation
sets reflect the natural distribution of words. In contrast, for the
morphological reinflection task, the custom has been to train type-based
models, in which each lemma and morphological feature combination is presented
to the model only once. We were interested in how well the type-based approach
can work for lemmatization and thus we also experimented with type-based
models where appropriate.

In sum, our contributions in this paper are first comparing three different
lemmatization approaches on two Estonian datasets with different domains with
the goal of assessing the complementarity of these systems. Secondly, we
investigate the effect of casing and special symbols as well as type- vs
token-based training and evaluation for each comparison system.

##  2 Lemmatization approaches

This section gives a brief overview of the current approaches to
lemmatization.

###  2.1 Generative approach

Generative lemmatization involves using a neural network to convert a word
form, represented as a sequence of characters, into its lemma, also
represented as a sequence of characters.

The model is trained to predict the lemma in an auto-regressive manner,
meaning that it makes predictions one character at a time based on the
previously predicted characters. Commonly, generative lemmatization makes use
of part of speech and morphological information as context Qi et al. (2020).
However, it is not necessarily limited to that. For example, Bergmanis and
Goldwater (2018) propose using surrounding words, subword units, or characters
as context for a given word form.

###  2.2 Pattern-based approach

In the Pattern-based lemmatization, the model assigns a specific
transformation class to each word form, and then uses a predetermined rule to
transform the word form to the lemma.

The approach is not bound to any specific method of classification, or for
that matter, representation of input features. For instance, in the UDPipe2
Straka (2018), the patterns are sequences of string edit operations, while the
Spacy’s lemmatizer uses an edit tree structure as a pattern Müller et al.
(2015).

###  2.3 Rule- and lexicon-based approaches

Rule-based approaches to lemmatization use various rule formalisms such as
rule cascades or finite state transducers to transform the word form into
lemma. For instance, the rule-based machine translation library Apertium also
includes rule-based morphological analyzers for many languages Khanna et al.
(2021). For the Estonian language, there is a morphological analyzer called
Vabamorf Kaalep and Vaino (2001).

In the dictionary-based approach, the lemma of a word is determined by looking
it up in a special dictionary. The dictionary may include word forms and their
POS tags with morphological features, which can be used to identify the
correct lemma. Such morphologial dictionaries include for instance Unimorph
McCarthy et al. (2020) and UD Lexicons Sagot (2018).

What these approaches have in common is that, intrinsically, they are not able
to fully consider the context in which a given word form appears, which
prevents them from disambiguating multiple candidates. So, for that purpose
they have to rely on separate tools, such as Hidden Markov Models. They are
also language-specific. The advantage, however, is that they are not dependent
on the amount of training data, and can be quite precise.

##  3 Data

We use the Estonian Dependency Treebank (EDT) and the Estonian Web Treebank
(EWT) from the Universal Dependencies collection version 2.10. The EDT
comprises several genres such as newspaper texts, fiction, scientific
articles, while the EWT is composed of texts from internet blogs and forums.
The statistics of both datasets are given in Table 1.

| train | dev | test
---|---|---|---
EDT # of sentences | 24633 | 3125 | 3214
EDT # of tokens | 344953 | 44686 | 48532
EWT # of sentences | 4579 | 833 | 913
EWT # of tokens | 55143 | 10012 | 13176
Table 1: Number of sentences and tokens per split in Estonian Dependency
Treebank and Estonian Web Treebank as of version 2.10.

##  4 Implementation

For the Generative approach, we adopted the neural transducer by Wu et al.
(2020), previously used for morphological reinflection. Neural transducer is a
character-level transformer, which takes individual characters of a word form
and morphological tags as input, and outputs the resulting lemma character-by-
character.

For the Pattern-based model we adopted an approach similar to UDpipe2 Straka
(2018). We used a transformer-based token classification model by fine-tuning
EstBERT Tanvir et al. (2020) to predict the correct transformation class (form
$\rightarrow$ lemma) for every token in a sentence. Our model uses HuggingFace
Wolf et al. (2020) TokenClassification implementation. Moreover, we reuse the
code to generate transformation classes from
UDpipe2.111https://github.com/ufal/udpipe/blob/udpipe-2/udpipe2_dataset.py

For the rule-based approach, we adopted the Estonian rule-based morphological
analyzer Vabamorf Kaalep and Vaino (2001). We used Vabamorf via EstNLTK, which
is a library that provides an API to various Estonian language technology
tools Orasmaa et al. (2016). We utilized Vabamorf’s HMM-based disambiguation
capabilities to output a single lemma for each token.

##  5 Results

Tables 2 and 3 show the results on the EDT and EWT validation sets
respectively. Overall, the Generative model (in the token-based training
setting, see below) outperforms both the Pattern-based model and the rule-
based Vabamorf on both datasets.

The first column (Original) in Table 2 shows results on the EDT data in its
original case sensitive form and including special symbols marking derivation
and compounding. The second column (No Sym) shows the results of models
trained on lowercased data with special symbols removed. All approaches show a
noticeable improvement in accuracy in the simplified environment. Although the
improvement with the Pattern-based model is the smallest, it has the largest
implications—ignoring casing and removing special symbols halves the number of
transformation classes.

| Original | No Sym | Type Eval
---|---|---|---
Gen Token | 95.49 | 97.59 | 97.61
Gen Type | 91.55 | 95.64 | 95.10
Pattern-based | 95.04 | 96.34 | –
Vabamorf | 87.78 | 91.66 | –
Vabamorf Oracle | 99.31 | 99.47 | –
Table 2: Lemmatization accuracy on the EDT validation set. Original: unaltered EDT, No Sym: lowercased EDT with special symbols removed, Type Eval: evaluation on distinct word types with No Sym setting.  Trained on | EWT | EDT
---|---|---
Gen Token | 95.88 | 96.28
Gen Type | 94.63 | 95.97
Pattern-based | 95.02 | 87.97
Vabamorf | 91.75 | 91.74
Vabamorf Oracle | 96.98 | 96.98
Table 3: Lemmatization accuracy on the EWT validation set. The first column
contains results for models trained on EWT, the results for models trained on
EDT are shown in the second column.

The top part of the Tables 2 and 3 compare the results of the Generative model
trained on word tokens and word types. Additionally, the last column of the
Table 2 also shows the evaluation on unique types of both the token-based and
type-based models trained in the No Sym setting. The Generative model trained
on word tokens always performs better than the model trained on unique word
types even when evaluated on word types. We conclude that there does not seem
to be any disadvantages to token-based training.

In Table 3, EWT validation set is evaluated in two settings. The first column
shows the results of the in-domain models trained on the EWT train set, the
results in the second column are obtained with the out-of-domain models
trained on the EDT train set. We observe that the Generative models perform
well in the cross-domain environment, and outperform the model trained on the
EWT train set. Meanwhile, the Pattern-based model trained on the EDT shows a
significant drop in performance when evaluated on EWT. Vabamorf also
demonstrates a degraded performance on EWT.

The last row in both Tables 2 and 3 show the performance of the Vabamorf in
the oracle mode, in which case the prediction is considered correct if the
true lemma appears in the list of generated candidates. We observe a
significant improvement in the accuracy of Vabamorf in the oracle mode. This
means that a large chunk of errors made by the rule-based approach is the
result of poor disambiguation, rather than incorrect morphological analysis.

In addition to comparing the performance of different approaches, we are
interested in whether there is any complementarity in the errors made by
models based on different approaches. Figure 2 presents a Venn diagram of the
token-level errors made by each system. We note that the area of the
intersection of all three models is relatively small, meaning that the number
of words where all models make an error is quite small, suggesting that
different approaches can complement each other in an ensemble setting.

##  6 Discussion

Because the UDPipe2’s pattern-based approach was highly successful in the
Sigmorphon 2019 shared task Straka et al. (2019), we expected it to perform
well also in our case, especially because instead of the frozen BERT weights
used in the UDPipe2, we fine-tuned the full model. However, the best shared
task lemmatization scores for the Estonian language were obtained with the
generative contextual lemmatizer by Bergmanis and Goldwater (2018), which
perhaps explains the success of the Generative model also in our experiments.
When analyzing the errors made by each three approaches, we can see that the
set of errors where all models overlap is relatively small (302 out of 5194,
5.8%), which suggests that different approaches can potentially compensate for
each other and thus an ensemble of different methods can be useful.

The rule-based Vabamorf made the largest number of errors. However, when we
evaluated it in the oracle mode on EDT, it covered the vast majority of
correct answers. This implies that Vabamorf could gain a lot from a better
disambiguator than the current HMM-based one. This was not the case for EWT
which, being a web treebank, contains more word forms (such as neologisms,
more recent loanwords, and so on) missing from the Vabamorf’s lexicon. Thus,
while Vabamorf can be a good solution for formal and grammatically correct
Estonian, it is less suitable for more noisy web texts.

Figure 2: Venn diagram of the token-level lemmatization errors made by each
model on the EDT validation set.

The approach to creating transformation rules suggested by the developers of
UDpipe may output equivalent rules, i.e., when applying these rules to a
surface form, the result is identical. We noticed that the Pattern-based model
is able to identify such cases. This means that an incorrectly predicted label
can result in a correct lemma. For example, two rules ↓0;d¦---+m+a and
0;d¦-+m→- transform the third person plural present tense form into the
corresponding -ma infinitive (vabandavad $\rightarrow$ vabandama “to
apologize”). The difference between these rules is that the former rule
removes three last letters and adds ma-suffix, while the latter removes the
last letter, and then replaces the existing letter preceding the existing a
with m. We suggest that such a peculiarity may be used to probe language
models for morphological knowledge.

The five most common rules are shown in Table 4. The most common rule is the
“do-nothing” rule, which accounts for more than half of the occurrences in the
EDT train set. The next three most common rules with smaller but still
considerable frequency involve removing suffixes of varying length. The last
rule fitting into our top-5 list is specific to verbs, replacing the last
character with the lemma suffix for verbs. The total set contains a very long
tail of transformation rules that appear only a few times or just once, such
as rules corresponding to the transformation of infrequently used suppletive
forms.

% | Rule | Description
---|---|---
54.1 | ↓0;d¦ | Do nothing
8.3 | ↓0;d¦- | Remove the last letter
5.2 | ↓0;d¦-- | Remove two last letters
3.4 | ↓0;d¦--- | Remove three last letters
3.3 | ↓0;d¦-+m+a | Replace the last letter with ma
Table 4: Top 5 most common transformation rules present in the train split of
the EDT dataset.

##  7 Conclusion

We compared three lemmatization approaches on two Estonian datasets from
different domains and found that on both datasets the Generative encoder-
decoder approach trained from scratch outperforms both the rule-based Vabamorf
as well as the Pattern-based approach fine-tuned from a large pre-trained
language model. We observed complementary error patterns for each three
approaches, which suggests that ensembling techniques can take advantage of
the complementary strengths of each individual approach.

## Acknowledgments

This research was supported by the Estonian Research Council Grant PSG721.

## References

  * Bergmanis and Goldwater (2018) Toms Bergmanis and Sharon Goldwater. 2018.  Context sensitive neural lemmatization with Lematus.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1391–1400, New Orleans, Louisiana. Association for Computational Linguistics.
  * Kaalep and Vaino (2001) Heiki-Jaan Kaalep and Tarmo Vaino. 2001.  Complete morphological analysis in the linguist’s toolbox.  _Congressus Nonus Internationalis Fenno-Ugristarum Pars V_ , pages 9–16.
  * Khanna et al. (2021) Tanmai Khanna, Jonathan N Washington, Francis M Tyers, Sevilay Bayatlı, Daniel G Swanson, Tommi A Pirinen, Irene Tang, and Hèctor Alòs i Font. 2021.  Recent advances in apertium, a free/open-source rule-based machine translation platform for low-resource languages.  _Machine Translation_ , 35(4):475–502.
  * McCarthy et al. (2020) Arya D. McCarthy, Christo Kirov, Matteo Grella, Amrit Nidhi, Patrick Xia, Kyle Gorman, Ekaterina Vylomova, Sabrina J. Mielke, Garrett Nicolai, Miikka Silfverberg, Timofey Arkhangelskiy, Nataly Krizhanovsky, Andrew Krizhanovsky, Elena Klyachko, Alexey Sorokin, John Mansfield, Valts Ernštreits, Yuval Pinter, Cassandra L. Jacobs, Ryan Cotterell, Mans Hulden, and David Yarowsky. 2020.  UniMorph 3.0: Universal Morphology.  In _Proceedings of the Twelfth Language Resources and Evaluation Conference_ , pages 3922–3931, Marseille, France. European Language Resources Association.
  * Müller et al. (2015) Thomas Müller, Ryan Cotterell, Alexander Fraser, and Hinrich Schütze. 2015.  Joint lemmatization and morphological tagging with lemming.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 2268–2274, Lisbon, Portugal. Association for Computational Linguistics.
  * Orasmaa et al. (2016) Siim Orasmaa, Timo Petmanson, Alexander Tkachenko, Sven Laur, and Heiki-Jaan Kaalep. 2016.  Estnltk - nlp toolkit for estonian.  In _Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC 2016)_ , Paris, France. European Language Resources Association (ELRA).
  * Qi et al. (2020) Peng Qi, Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D. Manning. 2020.  Stanza: A Python natural language processing toolkit for many human languages.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_.
  * Sagot (2018) Benoît Sagot. 2018.  A multilingual collection of CoNLL-U-compatible morphological lexicons.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018)_ , Miyazaki, Japan. European Language Resources Association (ELRA).
  * Straka (2018) Milan Straka. 2018.  UDPipe 2.0 prototype at CoNLL 2018 UD shared task.  In _Proceedings of the CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies_ , pages 197–207, Brussels, Belgium. Association for Computational Linguistics.
  * Straka et al. (2019) Milan Straka, Jana Straková, and Jan Hajic. 2019.  Udpipe at sigmorphon 2019: Contextualized embeddings, regularization with morphological categories, corpora merging.  _SIGMORPHON 2019_ , page 95.
  * Tanvir et al. (2020) Hasan Tanvir, Claudia Kittask, and Kairit Sirts. 2020.  Estbert: A pretrained language-specific BERT for estonian.  _CoRR_ , abs/2011.04784.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Wu et al. (2020) Shijie Wu, Ryan Cotterell, and Mans Hulden. 2020.  Applying the transformer to character-level transduction.  _CoRR_ , abs/2005.10213.