API

    Application Programming Interface
CSS

    Cascading Style Sheets
DOM

    Document Object Model
DSL

    Domain Specific Language
ELK

    Eclipse Layout Kernel
ELK Layered

     ELK Layered
EMF

    Eclipse Modeling Framework
GWT

    Google Web Toolkit
HCI

    Human Computer Interaction
HTML

    Hypertext Markup Language
IDE

    Integrated Development Environment
iur

    initialize-update-read
J2EE

    Java 2 Platform, Enterprise Edition
JDK

    Java Development Kit
JDT

    Eclipse Java development tools
JSON

    JavaScript Object Notation
JSON-RPC

     JSON Remote Procedure Call
JVM

    Java Virtual Machine
KEITH

     KIEL Environment Integrated in Theia
KiCo

     KIELER Compiler
KIEL

    Kiel Integrated Environment for Layout
KIELER

    Kiel Integrated Environment for Layout Eclipse Rich Client
KIML

    Kieler Infrastructure for Meta Layout
KLighD

     KIELER Lightweight Diagrams
KLoDD

     KIELER Layout of Dataflow Diagrams
KLay

     KIELER Layout
LSP

    Language Server Protocol
MDE

    Model-Driven Engineering
OS

    Operating System
OSGi

    Open Service Gateway Initiative
PDE

    Plug-in Development Environment
RCA

    Rich Client Application
SCCharts

    Sequential Constructive Statecharts
SCL

    Sequentially Constructive Language
SVG

    Scalable Vector Graphic
SWT

    Standard Widget Toolkit
TCP

    Transmission Control Protocol
UI

    user interface
URI

    Uniform Resource Identifier
URL

    Uniform Resource Locator
UX

    user experience
VSCode

    Visual Studio Code
XML

    Extensible Markup Language
YANG

    Yet Another Next Generation
RiCharts

    for Rich Charts
11institutetext:  Kiel University 11email: {sdo<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>22institutetext: Typefox GmbH
22email<EMAIL_ADDRESS>
# The Eclipse Layout Kernel

Sören Domrös 11 0000-0002-8011-8484 Reinhard von Hanxleden 11
0000-0001-5691-1215 Miro Spönemann 22 Ulf Rüegg 11 Christoph Daniel Schulze 11

###### Abstract

The Eclipse Layout Kernel (ELK) is a collection of graph drawing algorithms
that supports compound graph layout and ports as explicit anchor points of
edges. It is available as open-source library under an EPL license. Since its
beginning, ELK has served both as a research vehicle for graph drawing
algorithms, and as a practical tool for solving real-world problems. ELK and
its transpiled JavaScript cousin elkjs are now included in numerous academic
and commercial projects.

Most of the algorithms realized in ELK are described in a series of
publications. In this paper, the technical description concentrates on the key
features of the flag-ship algorithm ELK Layered, the algorithm architecture,
and usage. However, the main purpose of this paper is to give the broader view
that is typically left unpublished. Specifically, we review its history, give
a brief overview of technical papers, discuss lessons learned over the past
fifteen years, and present example usages. Finally, we reflect on potential
threats to open-source graph drawing libraries.

###### Keywords:

Automatic Layout Layered Layout Layout Library

##  1 Introduction

Freely available, high-quality graph drawing libraries are useful both for
stress-testing their underlying algorithms, and for harnessing the power of
automatic graph drawing in practical applications. In 2004, Jünger and Mutzel
published a volume of papers on various graph drawing libraries [29]. This
paper presents the ELK, which has been developed since 2008 and is still
actively maintained, with a growing user base.

The original driver of the ELK is modeling pragmatics [26], which, in a
nutshell, aims to increase the productivity of designers working with
graphical modeling languages. This is still the main focus of ELK, and
explains why modeling languages such as SCCharts [24], Ptolemy [37], or, more
recently, Lingua Franca [32], feature prominently in publications on ELK. In
fact, when getting started on modeling pragmatics with the Kiel Integrated
Environment for Layout (KIEL) tool [36] for model-driven engineering of
statecharts [27], the developers started with the off-the-shelf layout library
Graphviz [21]. It was only when they noticed that existing libraries did not
fully address their needs that they started developing and publishing their
own algorithms. We believe this practical motivation, and continuously tight
interaction between researchers and practitioners of model-driven engineering,
has contributed to the quality and usability of ELK.

Fig. 1 displays ELK’s development timeline with selected student
theses111https://www.rtsys.informatik.uni-
kiel.de/en/teaching/theses/completed-theses. The diploma thesis of Spönemann
led to the first publication of the  Layout of Dataflow Diagrams (KLoDD)
algorithm to visualize data-flow [60]. That thesis subsequently led to the
development of the ELK predecessor  Layout (KLay), which already included a
predecessor of ELKs flagship algorithm, which was at that time called KLay
Layered [53]. Each transformation step from KLoDD to ELK as well as each ELK
release marks not only new algorithms and features but also big refactoring
efforts, which enabled the longevity of ELK.

2020202120222023[6][5][7][8][35]0.7.00.8.0BT CarstensenMT KasperowskiBT
Riepe2016201720182019[38][40][55][50][48]0.1.00.2.0elkjs0.3.00.4.00.5.00.6.0[41][28][47][39][44][51][43]MT
ScheltenMT SprungMT CyrukMT JahnBT LucasBT WeberBT BorgfeldBT SchönbernerBT
Petzold2012201320142015[30][54][58][23][61][57][42]KLay LayeredELK CreationMT
CartensDT FuhrmannDT ToepfferBT ScheltenBT
Lasch2008200920102011[59][60]KLoDDDT SpönemannBT RießBT DöhringDT SchulzeDT
Wersig Figure 1: The ELK development timeline. Selected diploma theses (DT),
bachelor theses (BT), and master theses (MT) are marked in green, software
releases are marked with a gray triangle, and relevant publications are cited.

Years of work and several publications formed ELK as it is presented today: An
open-source layout library for layered layouts, rectangle packing, tree
drawing, force and stress layouts, radial layouts, and packing of disconnected
components, which transpiles into the popular (see Fig. 2) npm-package
elkjs222https://github.com/kieler/elkjs, and includes bridges to Graphviz [21]
and libavoid [65].

Figure 2: Weekly downloads of elkjs (green) compared to other popular layout
libraries tagged with layout, graph, or dataflow on npm
(https://npmtrends.com/cytoscape-vs-dagre-vs-elkjs-vs-gojs-vs-webcola,
retrieved: 05/06/2023).

In the following, we will continue with related work. Sec. 2 presents the
users of ELK and elkjs. ELK’s layout algorithms are presented in Sec. 3 with
special focus on ELK Layered. We contribute an in depth discussion of ELK’s
architecture, the algorithm architecture of the ELK Layered algorithm, and
lessons learned from developing and maintaining a large open-source layout
algorithm library in an academic context in Sec. 4. Sec. 5 presents real world
examples layouted with ELK. Sec. 6 concludes the paper and presents future
work on ELK.

#### Related Work

There exist several layout libraries, graphical editors, or algorithms that
utilize automatic layout, as presented by Jünger and Mutzel [29].

Dunnart [10] is a constraint based diagram editor, which utilizes constraints
to create desirable layouts using libavoid [65], OGDF [2], or cola [9].

Cytoscape[15] is a layout library originally used for bio-informatics, which
provides several algorithms for various use cases including
webcola333https://ialab.it.monash.edu/webcola/, dagre, and elkjs. Similar to
ELK, this allows using the same interface for various use cases.

The yWorks GmbH and their commercial yFiles tool [64] provide layout
algorithms and visualizations. However, it is not open-source and the free yEd
tool does not expose an API only for layout.

Zink et al. [66] support layered layouts with port constraint groups. Instead
of just fixed positions or orderings, they allow grouping ports, which again
may contain additional port groups that can have distinct layout constraints.
In terms of ports constraints this Sugiyama algorithm is superior. However, it
is especially developed for layout of hardware components and lacks ELK’s
configurability.

##  2 ELK Availability, Usage and Algorithms

ELK mainly serves as a sandbox for developing new algorithms or layout
strategies, which are often used in the context of Model-Driven Engineering
(MDE) to create data-flow or control-flow diagrams [26]. Most publications are
based on the layered approach [60, 18, 25, 30, 23, 53, 58, 61, 42, 28, 43, 39,
44, 40, 5, 8]. The only other algorithm with a peer reviewed paper is ELK
Rectangle Packing [6, 7], which is used for the layout of SCCharts [24], as
seen in Fig. 7.

####  2.0.1 Availability

ELK is available on GitHub444https://github.com/eclipse/elk and is released
via maven central under EPL-2.0, which is a weak copyleft license (except ELK
libavoid, which is available under LGPL, a strong copyleft license). The
JavaScript library elkjs is also available on GitHub and published via
npm555https://www.npmjs.com/package/elkjs. Further information regarding ELK
can be found on its Eclipse Project
website666https://projects.eclipse.org/projects/modeling.elk, the Eclipse ELK
website777https://www.eclipse.org/elk/, and the elklive
website888https://rtsys.informatik.uni-kiel.de/elklive/index.html, which hosts
a simple ELK graph editor that allows users to switch between different ELK
versions, can convert between different ELK graph formats, and houses examples
graphs.

####  2.0.2 Usage

Since ELK is open-source and added to several other libraries and tools, we
can only partly trace its usage on the basis of questions, pull-request, and
issues. Notable visualization libraries that use ELK or elkjs are KLighD [46],
Eclipse Sprotty999https://sprotty.org,
Terrastruct101010https://terrastruct.com/, Cytoscape,
Mermaid111111https://mermaid.js.org/, and
reaflow121212https://github.com/reaviz/reaflow. The integration of elkjs into
other tools might be the reason for its increasing weekly downloads since the
Cytoscape and elkjs downloads seem to correlate (see Fig. 2). These libraries
make ELK available in tools such as Eclipse
4diac131313https://www.eclipse.org/4diac/, Eclipse
Sirius141414https://www.eclipse.org/sirius/, Eclipse
Papyrus151515https://www.eclipse.org/papyrus/,
plantUML161616https://plantuml.com/, the
GLSP171717https://www.eclipse.org/glsp/, bigER [22], ExplorViz [13], the Kiel
Integrated Environment for Layout Eclipse Rich Client (KIELER) [24], Lingua
Franca [32], Capella Diagrams by Digitale Schiene
Deutschland181818https://github.com/DSD-DBS/capellambse-context-diagrams,
Ptolemy II [37], ETAS EHandbook [16], and probably many more. Since ELK is
published as an Eclipse project, industrial users such as ETAS, which use ELK
nearly since it creation, can safely rely on ELK without fearing issues
regarding intellectual property, since every ELK committer has to sign the
Eclipse Contributor Agreement191919https://www.eclipse.org/legal/ECA.php. This
enables ELK users that reach from model-driven engineers to doctors that look
at medication plans layouted with ELK to use the library.

####  2.0.3 Algorithms

All these tools mainly use layered layouts (ELK Layered). However, ELK also
supports rectangle packing (ELK Box, ELK Rectangle Packing), tree drawing (ELK
Mr. Tree), force and stress layout (ELK Force, ELK Stress), disconnected
component packing (ELK DisCo), radial layout (ELK Radial), and topology aware
compaction and overlap removal (ELK SpOre Compaction/Overlap Removal).
Moreover, it integrates the Graphviz layout algorithms Circo, Dot, FDP, Neato,
and Twopi and a bridge to libavoid [65], which does standalone edge routing.
Previous versions of ELK also included a bridge to OGDF [2].

Each layout algorithm might be fairly complex. E. g. ELK Layered supports in
its current state 140 layout options to further configure the Sugiyama
algorithm to add spacing and configurations for edges, nodes, comments [49],
labels [52], disconnected components [48], and ports [53]. Moreover, these
layout options can configure and enable different layout strategies such as
model order [8], node [35] and port constraints [53], node size constraints,
compaction [42], edge wrapping [40], edge and node label placement [51], self-
loop arrangement, top-down layout, and layout direction.

Additionally to the works mentioned in Fig. 1, ELK implements the following
strategies based on works of several researchers: stress-majorization layout
based on Gansner et al. [19], Fruchtermann and Reingold force layout [17],
Eades force layout [11], and tree node placement based on Walker [63].
Furthermore, the following algorithms are adopted for ELK Layered: a greedy
cycle breaking algorithm inspired by Eades et al. and di Battista et al. [12,
4], a depth-first cycle breaker by Gansner et al. [20], a node promotion
algorithm used as layer assignment post-processing, a minimal width layerer, a
stretch width layerer, and a longest path layerer by Nikolov et al. [34, 33],
Coffman-Graham layer assignment [3], network-simplex layer assignment and node
placement by Gansner et al. [20], Forster constraint resolving during
barycenter crossing minimization [14], Sugiyama style crossing
minimization[62], Brandes and Köpf node placement [1], linear segment node
placement based on Sander [45], hyper-edge cycle detection based work of Eades
et al. [12], orthogonal edge routing based on Sander and Di Battista et al.
[45, 4], spline edge routing based on the approach of Sederberg [56], and a
scan-line algorithm based on Lengauer[31].

##  3 ELK Features

In the following, we present how ELK Layered deals with compound graphs and
model order as an example for two ELK features.

####  3.0.1 Compound Graphs and Hierarchical Ports

Compound graphs or hierarchical graphs are laid out bottom-up by default. The
inner graph of a compound node determines the position of hierarchical ports,
which cannot be changed by the parent. In 3(a) the order of the inner graph
inside ChronoLogic, specifically the order of the outputs of the inner
reaction (gray arrow without a number), determines the order of the
hierarchical ports d, s, and m on the ChronoLogic node. At the same time, the
order of the reactions 1 - 3 (numbered gray arrows) inside PrintOutput
determines the order of the hierarchical input ports m, s, and d of
PrintOutput. If these ordering decisions are made independently, edge
crossings, as the one in 3(a), cannot be prevented. ELK Layered can solve this
problem by considering the hierarchical edges and their destination in the
child nodes if desired. This increases the complexity of the layout step and
is invasive in the algorithm structure. Therefore, many strategies such as
different layout directions in different hierarchies and all strategies that
influence ordering do not work together with this option.

(a)

(b)

Figure 3: An abbreviated Chrono Lingua Franca [32] program by Schulz-
Rosengarten and von Hanxleden layouted bottom-up with ELK. In (a) the
hierarchical edges may create preventable edge crossings, which can be
prevented by considering the edges across hierarchy levels, as seen in (b).

####  3.0.2 Model Order

Model order represents the order of the input model, which can often be used
for layout decisions, since “the input data can be expected to determine the
choice …” (see Jünger and Mutzel [29], p. 31). Domrös et al. describe how ELK
Layered utilizes model order as a tie-breaker or a constraint not only during
cycle breaking but also during layer assignment and crossing minimization to
capture the user intention. This approach tends to create better layouts that
can be influenced more directly by users and translates secondary notation
from a (textual) input model into the layout. Furthermore, it solves common
problems created by the bottom-up layout approach for compound graphs, as seen
in Fig. 3. If one assumes that the user will always order ports, outputs, and
inputs such that m, s, and d are consistently ordered, model order prevents
the problem in 3(a) form occurring. Model order crossing minimization will
create the crossing-free drawing depicted in 3(b) without using a complex
hierarchy-aware layout algorithm.

##  4 Implementation

ELK consists of 146000 lines of handwritten Java code (nearly 60000 lines
alone for ELK Layered), 3500 lines of algorithm metadata, which generate the
layout options and algorithm documentations, and five Xtext Domain Specific
Languages. The Google Web Toolkit transpiles ELK-native algorithms into the
JavaScript package elkjs to make ELK usable in web-applications. However,
elkjs is not as performant for larger graphs as the original
ELK202020https://github.com/kieler/elk-speed.

Figure 4: The five phases (dark gray) of ELK Layered with intermediate
processor slots (light gray) before, between, and after each phase with an
enclosing import and export step (gray) [53].

###  4.1 Algorithm Architecture

ELK provides a phase and processor infrastructure with import and export
steps, as seen in Fig. 4. The structuring of ELK Layered into five instead of
the traditional three phases makes it easier to interchange different layout
strategies. The import step transforms a general ELK graph into a layered
graph and transforms the layout problem into a left-to-right layout. The
exporter reverses these changes after the layout. This allows algorithm-
specific data-structures and abstracts from problems such as layout direction
or implicit ports. Additionally, pre- and post-processing may be done in the
six intermediate processing slots.

Before, between, and after each of the phases, each of the 57 intermediate
processors (see Fig. 5) can be executed with the limitation that they need to
have a static execution order [53]. The use of intermediate processors might
slightly increase the running time of the algorithm. However, these processors
make the algorithm much more maintainable by avoiding duplicate code and
allowing to adopt algorithms for different sub-problems. This is done
programmatically to keep the phase-processor dependencies maintainable. E. g.,
the GREEDY cycle breaking strategy can define that it needs the
REVERSED_EDGE_RESTORER processor, which re-reverses the reversed edges, to be
executed after phase five.

Figure 5: All ELK Layered processors, ordered by their execution order, and
layout strategies, layouted with ELK Layered and styled with KLighD [46].

Since ELK has its roots in the Eclipse Rich Client Application (RCA) KIELER,
it additionally contributes debugging and logging views for Eclipse Integrated
Development Environment (IDE). Furthermore, an Eclipse project wizard allows
easy creation of algorithms, which is mainly used for teaching purposes.

###  4.2 Lessons Learned

In the following, we describe what users want from a layout library based on
feature requests and questions from the ELK community. We reflect on the
maintenance and documentation practices of ELK, and present features that
should be removed or reworked to foster ELK’s future success.

####  4.2.1 Listening to Users

We interpret the success of ELK (and other layout libraries) to indicate that
the idea of automatic layout is slowly but surely gaining ground in the
practical usage of graphical languages. However, to be truly successful, one
still has to listen to the users. Specifically, in our experience, users
generally seem to be quite pleased with the layout results, at least as far as
the aesthetic criteria are concerned that drawing algorithms are typically
evaluated with, such as reducing edge crossings. However, users may get
frustrated if they appear to have “little control” over actual results. When
somebody’s mental map of a graph is inflicted because drawings change
drastically after minimal changes of the graph, or, even worse, without any
changes of the graph, this also causes irritations. For quite some time, we
experimented with different approaches to give the users more control and
stability. For example, we provide annotations to the graph that specify the
nodes that should be placed in the same layer [35]. However, these did not
really seem to catch on, probably for lack of awareness of these options.

We, therefore, lately focused on a different approach to give modelers
control, and to enhance layout stability as well, which is the _model order_
approach mentioned earlier. Basically, we consider it—in most cases—a mistake
to consider a graph as a _set_ of nodes and _set_ of edges, as done in most of
the literature. In our experience, it is much more practical to treat nodes
and edges as ordered lists, with the order stemming e. g. from a textual input
file. The model order should only be violated if the graph can clearly be
improved by it. Whenever there are equally good alternative drawings
available, one should use model order as a “tie-breaker”, i. e., choose the
drawing that is closer to the model order [8].

For the same reasoning, while we originally used randomness rather liberally
in our algorithms, in the hope to increase the chances of optimizing drawings
according to some aesthetic criteria, we by now try to avoid randomness unless
there are very strong reasons to include it.

####  4.2.2 Maintaining and Documenting the Project

Since its beginnings, ELK typically had (only) one to three active developers.
Furthermore, ELK is research driven, and whatever software engineering and
maintenance it receives is mostly provided by motivated graduate students “on
the side.” Software engineering tasks such as adding documentation, fixing
bugs, testing, updating versions, interacting with users, and managing builds
and releases cannot be the main focus of researchers, which mainly focus on
new features and strategies for ELK for their dissertation. At the same time,
in computer science it is not common to fund software engineers that operate
and maintain open-source libraries such as ELK by the research institution
itself. On the long run this is a severe impediment for research that builds
on powerful, reliable open-source platforms. The situation is different in
other fields. E. g., in experimental physics it is understood that a research
institution not only needs scientists that actually conduct and publish
research, but that there are also highly skilled lab engineers required that
tend to the infrastructure. Given these circumstances, we originally would not
have expected ELK’s longevity and popularity. E. g., elkjs has received over
1200 “stars” on GitHub by now.

This maintenance effort also enables research. Even though the first
contributors to ELK have graduated long ago, ELK still provides a stable
research infrastructure for complex layout algorithms. E. g., the recently
added model order strategies require a highly modular layout algorithm with
exchangeable layout strategies for the Sugiyama algorithm and a flexible
system for pre- and post-processing, which is provided by the phase and
processor infrastructure of ELK presented in Fig. 4.

As part of the maintenance effort, early ELK developers lived and enforced
good coding conventions consisting of regular code reviews and refactoring as
part of the release cycle. These made sure that the algorithm structure did
not degrade over time. Most of the releases in Fig. 1 were accompanied by a
refactoring process, especially for the initial release of KLay Layered, ELK,
and elkjs. E. g., as part of the creation of ELK the graph format was
customized for layout and anything regarding visualization was removed.
Moreover, the transpilation to elkjs required elimination of “hacks” such as
Java reflection.

The move to the Eclipse Foundation was a time-consuming effort but finally
helped to support the maintenance, documentation, and legal efforts. As a
result, ELK has a stable release and build management system, which does not
depend on sometimes unreliable university server infrastructure. Release
reviews guarantee a certain code, documentation, and process quality, and the
Eclipse Contributor Agreement prevents legal issues.

Additionally, documentation is partly enforced by convention and syntax. The
metadata language that describes algorithms configurations enforces
documentation, which is hosted on the Eclipse project web-page together with
additional documentation in form of guides, examples, and blog posts. However,
as in many academic projects, the end user documentation lacks behind.
Interactive support channels proved necessary. As a result, ELK utilizes the
online ELK editor elklive (see Sec. 2.0.1) and the ELK Gitter
chat212121https://gitter.im/eclipse/elk, next to the GitHub issues to
communicate with its user base.

Not only the end users but also developers need documentation. For the layered
algorithm, processors are carefully ordered in each slot based on dependencies
between, which corresponds to the processor ordering in Fig. 5. Each processor
documentation lists its designated slots, pre- and post-conditions, and in-
slot dependencies to other processors in form of Javadoc. However, the
documentation of dependencies is not always done carefully since dependencies
between processors and between different layout options get exponentially more
complex with the number of features. Moreover, new features might require
constraints that were previously deemed irrelevant. E. g., the model order
strategies might reorder nodes and edges and assume that other processors will
not introduce additional nodes and will respect this ordering. This was
originally not considered since a graph was previously assumed to consist of
_unordered_ sets of nodes and edges.

####  4.2.3 Removing Outdated Features

The metadata-compiler, which compiles the algorithm metadata into Java and
generates algorithm and layout option documentation, on the one hand makes it
easier for ELK developers to add new layout options. On the other hand it
requires an installed metadata-compiler in the development environment, which
is, hence, limited to the Eclipse IDE. In its current state, this limits
collaboration in the open-source project. We experience that highly motivated
users want to collaborate but fail to install the necessary tooling. At the
same time, the metadata-compiler generates most of the algorithm
documentation. Reworking this would require an effort but would greatly help
ELK gain additional contributors.

Debugging tools, which proved to be essential for algorithm development, only
exist for the Eclipse IDE. As part of future work the Eclipse-specific
functions as well as part of the service architecture should move in a
separate repository, leaving only the algorithms and their infrastructure in
the ELK core project.

Refactoring should not only be used to improve code quality and to identify
bottlenecks but also to remove features. Some features, such as the diploma
thesis of Fuhrmann (see Fig. 1) about compound graph layout, were too complex
to be maintained or do not fit into the algorithm phase structure. Such
features may threaten the whole layout library since they increase the
maintenance effort and facilitate the usage of “hacks” to build desired
functionality. Hence, regular refactoring needs to identify such features and
deprecate them to decrease unnecessary maintenance efforts.

##  5 Examples

In the following, we showcase how ELK is used to layout SCCharts [24], a
synchronous language that models control-flow, and Lingua Franca [32], a
polyglot coordination language that models data-flow. All the following models
are styled with KLighD [46], since ELK does not support colors, fonts, and
non-rectangular forms but only computes coordinates and sizes for rectangles
and routes lines.

The Lingua Franca model in Fig. 6 showcases hierarchical edges using ELK
Layered. The reactors WaitingRoom and Customer both have internal behavior,
which is also layouted using ELK Layered. Here, model order orders the
internal behavior of WaitingRoom and Customer as their numbering suggests. The
inner graph, the ports, and the port labels determine the size of a compound
node. ELK Layered is here configured to place the port labels consistently
above the corresponding port. The placement of the vertical edge segments
between WaitingRoom and Customer minimizes the used horizontal space. The
port-label spacing and port-port spacing makes sure that the labels does not
overlap with the arrow shaped ports and that no ports overlap.

Figure 6: The sleeping barber Lingua Franca model taken from
https://github.com/lf-lang/examples-lingua-franca.

The SCChart in Fig. 7 showcases how different layout algorithms can be used in
the same model. Here, rectangle packings and layered layouts alternate.
Moreover, directions of layered layouts also alternate, creating drawings with
a better aspect ratio. The graph inside ProcessInputs is layouted top-to-
bottom, and the graph inside Running and GenClkState is layouted left-to-
right. Model order is used as a tie-breaker, which makes sure that the
outgoing and incoming edges of the initial Pause state are correctly ordered.
Model order also highlights the control-flow loops, since the textual state
ordering inside an SCChart usually determines the choice for a backward edge.
Edge-label-management positions edge labels such that they have semantic line
breaks. Moreover, edge labels are positioned on an edge such that labels can
be clearly matched with the transitions they refer to. The “on-edge”
positioning tends to reduce the drawing height. Padding makes sure that the
inner layered graph will not overlap with the triangle in the upper left
corner or the label next to it. In a corresponding IDE, the layout direction,
label shortening strategies, and other layout options can be directly
configured, e. g., to get a drawing to fit a certain aspect ratio or to create
a desired layout.

The layout algorithm and all mentioned strategies are suitable in interactive
scenarios and the layout time is for all shown models in millisecond range.

Figure 7: The motor SCChart.

##  6 Conclusion and Outlook

ELK and the algorithms behind it are used as the basis of several academic and
commercial projects, while only being developed by a handful of people over
the course of nearly fifteen years. Through its migration into the Eclipse
Foundation and focusing not only on individual research but also on software
engineering, it will hopefully live on for some time.

Graduate students not only spent a considerable amount of time engineering ELK
but also implemented good coding and documentation practices to maintain a
high code quality. Time spent interacting with the community through multiple
interactive collaboration channels allows identifying highly requested
features and developing practically relevant algorithms. These new use cases
spawn new research topics, which again attracts future developers for ELK in
form of graduate students. However, ELK could greatly benefit from a non-
scientific software engineer.

Future work on ELK will include refactoring as well as general maintenance
issues to make ELK more robust for future development. ELK will add support
for top-down layout as an alternative to the presented bottom-up layout
strategy for compound graphs, which can be used to add map-navigation-like
tooling for complex graphs. Moreover, ELK Layered will get support for
selective in-layer edges, which are usually forbidden in layered layouts. We
also plan to add more model order configurations as well as model order
support using different model order groups used to discern the ordering of
different kind of graph elements.

##  7 Acknowledgments

We thank all the developers that put their heart and soul into ELK, which are
partly mentioned in Fig. 1. We are indebted to the numerous users of ELK
providing valuable feedback. In particular, Edward Lee and his group have been
enthusiastic and supportive for many years now, which helped to considerably
broaden the scope and utility of ELK.

## References

  * [1] Brandes, U., Köpf, B.: Fast and simple horizontal coordinate assignment. In: Proc. of the 9th Int. Symp. on Graph Drawing (GD ’01). LNCS, vol. 2265, pp. 33–36. Springer (2002). https://doi.org/10.1007/3-540-45848-4
  * [2] Chimani, M., Gutwenger, C., Jünger, M., Klein, K., Mutzel, P., Schulz, M.: The Open Graph Drawing Framework. Poster at the 15th Int. Symp. on Graph Drawing (GD07) (2007)
  * [3] Coffman., E.G., Graham, R.L.: Optimal scheduling for two-processor systems. Acta Informatica 1(3), 200–213 (1972). https://doi.org/10.1007/BF00288685
  * [4] Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall (1999)
  * [5] Domrös, S., von Hanxleden, R.: Preserving order during crossing minimization in Sugiyama layouts. In: Proc. of the 17th Int. Joint Conf. on Comp. Vision, Imaging and Comp. Graphics Theory and Apps. (VISIGRAPP 2022). pp. 156–163. INSTICC, SciTePress (2022). https://doi.org/10.5220/0010833800003124
  * [6] Domrös, S., Lucas, D., von Hanxleden, R., Jansen, K.: On order-preserving, gap-avoiding rectangle packing. In: Proc. of the 16th Int. Joint Conf. on Comp. Vision, Imaging and Comp. Graphics Theory and Apps. (VISIGRAPP 2021). pp. 38–49. INSTICC, SciTePress (2021). https://doi.org/10.5220/0010186400380049
  * [7] Domrös, S., Lucas, D., von Hanxleden, R., Jansen, K.: Revisiting order-preserving, gap-avoiding rectangle packing. In: Comp. Vision, Imaging and Comp. Graphics Theory and Apps. pp. 183–205. Springer International Publishing, Cham (2023)
  * [8] Domrös., S., Riepe., M., von Hanxleden., R.: Model order in sugiyama layouts. In: Proc. of the 18th Int. Joint Conf. on Comp. Vision, Imaging and Comp. Graphics Theory and Apps. (VISIGRAPP 2023). pp. 77–88. INSTICC, SciTePress (2023). https://doi.org/10.5220/0011656700003417
  * [9] Dwyer, T., Koren, Y.: Dig-CoLa: directed graph layout through constrained energy minimization. In: Proc. of the IEEE Symp. on Inf. Vis. (INFOVIS’05). pp. 65–72 (Oct 2005). https://doi.org/10.1109/INFVIS.2005.1532130
  * [10] Dwyer, T., Marriott, K., Wybrow, M.: Dunnart: A constraint-based network diagram authoring tool. In: Rev. Papers of the 16th Int. Symp. on Graph Drawing (GD ’08). LNCS, vol. 5417, pp. 420–431. Springer (2009). https://doi.org/10.1007/978-3-642-00219-9
  * [11] Eades, P.: A heuristic for graph drawing. Congressus Numerantium 42, 149–160 (1984)
  * [12] Eades, P., Lin, X., Smyth, W.F.: A fast and effective heuristic for the feedback arc set problem. Information Processing Letters 47(6), 319–323 (1993). https://doi.org/10.1016/0020-0190(93)90079-O
  * [13] Fittkau, F., Krause, A., Hasselbring, W.: Software landscape and application visualization for aystem comprehension with explorviz. Information and Software Technology 87, 259–277 (2017)
  * [14] Forster, M.: A fast and simple heuristic for constrained two-level crossing reduction. In: Proc. of the 12th Int. Symp. on Graph Drawing (GD ’04), LNCS, vol. 3383, pp. 206–216. Springer (2005)
  * [15] Franz, M., Lopes, C.T., Huck, G., Dong, Y., Sumer, O., Bader, G.D.: Cytoscape.js: A graph theory library for visualisation and analysis. Bioinformatics 32(2), 309–311 (2016)
  * [16] Frey, P., von Hanxleden, R., Krüger, C., Rüegg, U., Schneider, C., Spönemann, M.: Efficient exploration of complex data flow models. In: Proc. of Modellierung 2014. pp. 321–336 (2014)
  * [17] Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Software—Practice & Experience 21(11), 1129–1164 (1991). https://doi.org/10.1002/spe.4380211102
  * [18] Fuhrmann, H., von Hanxleden, R.: Taming graphical modeling. In: Proc. of the ACM/IEEE 13th Int. Conf. on Model Driven Eng. Lang. and Sys. (MoDELS ’10). LNCS, vol. 6394, pp. 196–210. Springer (Oct 2010). https://doi.org/10.1007/978-3-642-16145-2
  * [19] Gansner, E.R., Koren, Y., North, S.C.: Graph drawing by stress majorization. In: Graph Drawing. LNCS, vol. 3383. Springer Berlin Heidelberg (2005). https://doi.org/10.1007/978-3-540-31843-9_25
  * [20] Gansner, E.R., Koutsofios, E., North, S.C., Vo, K.P.: A technique for drawing directed graphs. Software Engineering 19(3), 214–230 (1993)
  * [21] Gansner, E.R., North, S.C.: An open graph visualization system and its applications to software engineering. Software—Practice and Experience 30(11), 1203–1234 (2000)
  * [22] Glaser, P.L., Bork, D.: The biger tool-hybrid textual and graphical modeling of entity relationships in vs code. In: IEEE 25th Int. Ent. Distrib. Object Comp. Workshop (EDOCW). pp. 337–340. IEEE (2021)
  * [23] Gutwenger, C., von Hanxleden, R., Mutzel, P., Rüegg, U., Spönemann, M.: Examining the compactness of automatic layout algorithms for practical diagrams. In: Proc. of the Workshop on Graph Vis. in Prac. (GraphViP ’14). pp. 42–52 (2014)
  * [24] von Hanxleden, R., Duderstadt, B., Motika, C., Smyth, S., Mendler, M., Aguado, J., Mercer, S., O’Brien, O.: SCCharts: Sequentially Constructive Statecharts for safety-critical applications. In: Proc. of Conf. on Prog. Lang. Design and Impl. (PLDI ’14). pp. 372–383. ACM, Edinburgh, UK (2014). https://doi.org/10.1145/2594291.2594310
  * [25] von Hanxleden, R., Fuhrmann, H., Spönemann, M.: KIELER—The KIEL Integrated Environment for Layout Eclipse Rich Client. In: Proc. of the Design, Autom. and Test in Europe University Booth (DATE ’11). Grenoble, France (2011)
  * [26] von Hanxleden, R., Lee, E.A., Fuhrmann, H., Schulz-Rosengarten, A., Domrös, S., Lohstroh, M., Bateni, S., Menard, C.: Pragmatics twelve years later: a report on Lingua Franca. In: 11th Int. Symp. on Lev. Apps. of Formal Methods, Verif. and Valid. (ISoLA). LNCS, vol. 13702, pp. 60–89. Springer, Rhodes, Greece (Oct 2022). https://doi.org/10.1007/978-3-031-19756-7_5
  * [27] Harel, D.: Statecharts: A visual formalism for complex systems. Science of Computer Programming 8(3), 231–274 (Jun 1987)
  * [28] Jabrayilov, A., Mallach, S., Mutzel, P., Rüegg, U., von Hanxleden, R.: Compact layered drawings of general directed graphs. In: Proc. of the 24th Int. Symp. on Graph Drawing and Net. Viz. (GD ’16). pp. 209–221 (2016). https://doi.org/10.1007/978-3-319-50106-2
  * [29] Jünger, M., Mutzel, P. (eds.): Graph Drawing Software. Springer (2004)
  * [30] Klauske, L.K., Schulze, C.D., Spönemann, M., von Hanxleden, R.: Improved layout for data flow diagrams with port constraints. In: Proc. of the 7th Int. Conf. on the Theory and Apps. of Diagrams (DIAGRAMS ’12). LNAI, vol. 7352, pp. 65–79. Springer (2012). https://doi.org/10.1007/978-3-642-31223-6
  * [31] Lengauer, T.: Combinatorial Algorithms for Integrated Circuit Layout. John Wiley & Sons, Inc., New York, NY, USA (1990)
  * [32] Lohstroh, M., Menard, C., Bateni, S., Lee, E.A.: Toward a Lingua Franca for Deterministic Concurrent Systems. ACM Trans. on Emb. Comp. Sys. (TECS) 20(4), Article 36 (May 2021). https://doi.org/10.1145/3448128
  * [33] Nikolov, N.S., Tarassov, A.: Graph layering by promotion of nodes. Disc. Appl. Maths. 154(5), 848–860 (2006). https://doi.org/10.1016/j.dam.2005.05.023
  * [34] Nikolov, N.S., Tarassov, A., Branke, J.: In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes. Journal of Experimental Algorithmics 10 (2005). https://doi.org/10.1145/1064546.1180618
  * [35] Petzold, J., Domrös, S., Schönberner, C., von Hanxleden, R.: An Interactive Graph Layout Constraint Framework. In: Proc. of the 18th Int. Joint Conf. on Comp. Vision, Imaging and Comp. Graphics Theory and Apps. (VISIGRAPP 2023). pp. 240–247. INSTICC, SciTePress (2023). https://doi.org/10.5220/0011803000003417, with accompanying poster
  * [36] Prochnow, S., Traulsen, C.: KIEL—textual and graphical representations of statecharts. Pres. at the 12th Synchr. Workshop (SYNCHRON ’05), Malta (Nov 2005)
  * [37] Ptolemaeus, C. (ed.): System Design, Modeling, and Simulation using Ptolemy II. Ptolemy.org (2014), http://ptolemy.org/books/Systems
  * [38] Rüegg, U.: Sugiyama layouts for prescribed drawing areas. No. 2018/1 in Kiel Computer Science Series (2018), Dissertation, Kiel University
  * [39] Rüegg, U., Ehlers, T., Spönemann, M., von Hanxleden, R.: A generalization of the directed graph layering problem. In: Proc. of the 24th Int. Symp. on Graph Drawing and Net. Vis. (GD ’16). pp. 196–208 (2016). https://doi.org/10.1007/978-3-319-50106-2_16
  * [40] Rüegg, U., von Hanxleden, R.: Wrapping layered graphs. In: Proc. of the 10th Int. Conf. on the Theory and Apps. of Diagrams (DIAGRAMS ’18). pp. 743–747. Springer (2018)
  * [41] Rüegg, U., Lakkundi, R., Prasad, A., Kodaganur, A., Schulze, C.D., von Hanxleden, R.: Incremental diagram layout for automated model migration. In: Proc. of the ACM/IEEE 19th Int. Conf. on Model Driven Eng. Lang. and Sys. (MoDELS ’16). pp. 185–195 (2016). https://doi.org/10.1145/2976767.2976805
  * [42] Rüegg, U., Schulze, C.D., Carstens, J.J., von Hanxleden, R.: Size- and port-aware horizontal node coordinate assignment. In: Proc. of the 23rd Int. Symp. on Graph Drawing and Net. Vis. (GD ’15). pp. 139–150 (2015). https://doi.org/10.1007/978-3-319-27261-0_12
  * [43] Rüegg, U., Schulze, C.D., Grevismühl, D., von Hanxleden, R.: Using one-dimensional compaction for smaller graph drawings. In: Proc. of the 9th Int. Conf. on the Theory and Apps. of Diagrams (DIAGRAMS ’16). LNCS, vol. 9781, pp. 212–218. Springer (2016). https://doi.org/10.1007/978-3-319-42333-3_16
  * [44] Rüegg, U., Schulze, C.D., Sprung, C., Wechselberg, N., von Hanxleden, R.: Edge bundling for dataflow diagrams. Poster at the 24th Int. Symp. on Graph Drawing and Net. Vis. (GD ’16) (2016)
  * [45] Sander, G.: A fast heuristic for hierarchical Manhattan layout. In: Proc. of the Symp. on Graph Drawing (GD ’95). LNCS, vol. 1027, pp. 447–458. Springer (1996). https://doi.org/10.1007/BFb0021828
  * [46] Schneider, C., Spönemann, M., von Hanxleden, R.: Just model! – Putting automatic synthesis of node-link-diagrams into practice. In: Proc. of the IEEE Symp. on Vis. Lang. and Human-Centric Comp. (VL/HCC ’13). pp. 75–82. IEEE, San Jose, CA, USA (Sep 2013). https://doi.org/10.1109/VLHCC.2013.6645246
  * [47] Schulze, C.D.: Two opportunities and challenges of automatic layout in visual languages. In: Proc. of the ACM Stdnt. Res. Compet. at MODELS’16 co-located with the 19th Int. Conf. on Model Driven Eng. Lang. and Sys. (MODELS’16) (2016)
  * [48] Schulze, C.D.: Text in Diagrams: Challenges to and Opportunities of Automatic Layout. No. 2019/4 in Kiel Computer Science Series (2019). https://doi.org/10.21941/kcss/2019/4, Dissertation, Kiel University
  * [49] Schulze, C.D., von Hanxleden, R.: Automatic layout in the face of unattached comments. In: Proc. of the IEEE Symp. on Vis. Lang. and Human-Centric Comp. (VL/HCC ’14). pp. 41–44. Melbourne, Australia (Jul 2014). https://doi.org/10.1109/VLHCC.2014.6883019
  * [50] Schulze, C.D., Hoops, G., von Hanxleden, R.: Automatic layout and label management for UML sequence diagrams. In: Proc. of the IEEE Symp. on Vis. Lang. and Human-Centric Comp. (VL/HCC ’18) (2018)
  * [51] Schulze, C.D., Lasch, Y., von Hanxleden, R.: Label management: Keeping complex diagrams usable. In: Proc. of the IEEE Symp. on Vis. Lang. and Human-Centric Comp. (VL/HCC ’16). pp. 3–11 (Sep 2016). https://doi.org/10.1109/VLHCC.2016.7739657
  * [52] Schulze, C.D., Plöger, C., von Hanxleden, R.: On comments in visual languages. In: Proc. of the 9th Int. Conf. on the Theory and Apps. of Diagrams (DIAGRAMS ’16). pp. 219–225. LNCS (2016). https://doi.org/10.1007/978-3-319-42333-3_17
  * [53] Schulze, C.D., Spönemann, M., von Hanxleden, R.: Drawing layered graphs with port constraints. JVLC, Special Issue on Diagram Aesthetics and Layout 25(2), 89–106 (2014). https://doi.org/10.1016/j.jvlc.2013.11.005
  * [54] Schulze, C.D., Spönemann, M., Schneider, C., von Hanxleden, R.: Two applications for transient views in software development environments (showpiece). In: Proc. of the IEEE Symp. on Vis. Lang. and Human-Centric Comp. (VL/HCC ’14). Melbourne, Australia (Jul 2014)
  * [55] Schulze, C.D., Wechselberg, N., von Hanxleden, R.: Edge label placement in layered graph drawing. In: Proc. of the 10th Int. Conf. on the Theory and Apps. of Diagrams (DIAGRAMS ’18). pp. 71–78. LNCS, Springer (2018). https://doi.org/10.1007/978-3-319-91376-6_10
  * [56] Sederberg, T.W.: An introduction to b-spline curves. Brigham Young University (2005)
  * [57] Spönemann, M.: Graph layout support for model-driven engineering. No. 2015/2 in Kiel Computer Science Series (2015), Dissertation, Kiel University
  * [58] Spönemann, M., Duderstadt, B., von Hanxleden, R.: Evolutionary meta layout of graphs. In: Proc. of the 8th Int. Conf. on the Theory and Apps. of Diagrams (DIAGRAMS ’14). LNAI, vol. 8578, pp. 16–30. Springer (2014)
  * [59] Spönemann, M., Fuhrmann, H., von Hanxleden, R.: Automatic layout of data flow diagrams in KIELER and Ptolemy II. Tec. Rep.0̃914, Kiel University (2009)
  * [60] Spönemann, M., Fuhrmann, H., von Hanxleden, R., Mutzel, P.: Port constraints in hierarchical layout of data flow diagrams. In: Proc. of the 17th Int. Symp. on Graph Drawing (GD ’09). LNCS, vol. 5849, pp. 135–146. Springer (2010). https://doi.org/10.1007/978-3-642-11805-0
  * [61] Spönemann, M., Schulze, C.D., Rüegg, U., von Hanxleden, R.: Counting crossings for layered hypergraphs. In: Proc. of the 8th Int. Conf. on the Theory and Apps. of Diagrams (DIAGRAMS ’14). LNAI, vol. 8578, pp. 9–15. Springer (2014). https://doi.org/10.1007/978-3-662-44043-8_2
  * [62] Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. on Sys., Man and Cybernetics 11(2), 109–125 (Feb 1981). https://doi.org/10.1109/TSMC.1981.4308636
  * [63] Walker, II, J.Q.: A node-positioning algorithm for general trees. Software – Practice and Experience 20(7), 685–705 (1990)
  * [64] Wiese, R., Eiglsperger, M., Kaufmann, M.: yFiles: Visualization and automatic layout of graphs. In: Proc. of the 9th Int. Symp. on Graph Drawing (GD ’01). LNCS, vol. 2265, pp. 588–590. Springer (2001)
  * [65] Wybrow, M., Marriott, K., Stuckey, P.J.: Orthogonal connector routing. In: Proc. of the 17th Int. Symp. on Graph Drawing (GD ’09). LNCS, vol. 5849, pp. 219–231. Springer (2010). https://doi.org/10.1007/978-3-642-11805-0
  * [66] Zink, J., Walter, J., Baumeister, J., Wolff, A.: Layered drawing of undirected graphs with generalized port constraints. Computational Geometry 105-106, 101886 (2022). https://doi.org/10.1016/j.comgeo.2022.101886

  *[ELK]: Eclipse Layout Kernel
  *[JSON]: JavaScript Object Notation
  *[KIEL]: Kiel Integrated Environment for Layout
  *[KIELER]: Kiel Integrated Environment for Layout Eclipse Rich Client
  *[]:
  *[KLoDD]:  Layout of Dataflow Diagrams
  *[KLay]:  Layout
  *[ELKs]: Eclipse Layout Kernel
  *[MDE]: Model-Driven Engineering
  *[RCA]: Rich Client Application
  *[IDE]: Integrated Development Environment


# A PSO Approach for Optimum Design of Multivariable PID Controller for
nonlinear systems

Taeib Adel  Research Unit on Control,
Monitoring and Safety of Systems (C3S)
High School ESSTT
Email<EMAIL_ADDRESS>Ltaeif Ali  Research Unit on Control,
Monitoring and Safety of Systems (C3S)
High School ESSTT
Email<EMAIL_ADDRESS>Chaari Abdelkader  Research Unit on Control,
Monitoring and Safety of Systems (C3S)
High School ESSTT
Email<EMAIL_ADDRESS>
###### Abstract

The aim of this research is to design a PID Controller using particle swarm
optimization (PSO) algorithm for multiple-input multiple output (MIMO) Takagi-
Sugeno fuzzy model. The conventional gain tuning of PID controller (such as
Ziegler-Nichols (ZN) method) usually produces a big overshoot, and therefore
modern heuristics approach such as PSO are employed to enhance the capability
of traditional techniques. However, due to the computational efficiency, only
PSO will be used in this paper. The results show the advantage of the PID
tuning using PSO-based optimization approach.

##  I Introduction

PID control, which is usually known as a classical output feedback control for
SISO systems, has been widely used in the industrial world [1] and [2]. The
tuning methods of PID control are adjusting the proportional, the integral and
the derivative gains to make an output of a controlled system track a target
value properly. several researchers focus on multiple-input multiple output
MIMO control systems. Because many industrial processes are MIMO systems which
need MIMO control techniques to improve performance, though they are naturally
more difficult than SISO systems. As we know, MIMO PID controller design has
developed over a number of years. Luyben (1986) proposed a simple tuning
method for decentralized PID controllers in MIMO system from single-loop relay
tests [3]. Yusof and Omatu (1993) presented a multivariable self-tuning PID
controller based on estimation strategies [4]. Wang et al. (1997) proposed a
tuning method for fully cross-coupled multivariable PID controller from
decentralized relay feedback test to find the critical oscillation frequency
of the system by first designing the diagonal elements of multivariable PID
controller independent of off-diagonal ones [5]. Recently, the computational
intelligence has proposed particle swarm optimization (PSO) [6,7] as opened
paths to a new generation of advanced process control. The PSO algorithm,
proposed by Kennedy and Eberhart [6] in 1995, was an evolution computation
technology based on population intelligent methods. In comparison with genetic
algorithm, PSO is simple,easy to realize and has very deep intelligent
background. It is not only suitable for scientific research, but also suitable
for engineering applications in particular. Thus, PSO received widely
attentions from evolution computation field and other fields. Now the PSO has
become a hotspot of research. Various objective functions based on error
performance criterion are used to evaluate the performance of PSO algorithms.

In this paper, a scheduling PID tuning parameters using particle swarm
optimization strategy for MIMO nonlinear systems . This paper has been
organized as follows: In section 2, a brief review of the TS fuzzy model
formulation is given. Estimation method of recursive weighted least-squares
(RWLS)in section 3. In section 4, PID control systems of multivariable
processes. Finally, some conclusions are made in section 5.

##  II Takagi-Sugeno fuzzy model of a MIMO process

Generally, modeling process consists to obtain a parametric model with the
same dynamic behavior of the real process. In this section, we are interested
to the problem of the MIMO process identification[8]. We consider a MIMO
system with $n_{i}$ inputs and $n_{0}$ outputs. The MISO models are a input-
output NARX (Non linear Auto Regressive with eXogenous input) defined by:

$y_{l}(k+1)=f_{l}(x_{l}(k))\,\,\,\,\,\,\,\,\,\,l=1,2,...,n_{0}$ (1)

With the regression vector represented by:

$\begin{array}[]{c}x_{l}(k)=[\\{y_{1}(k)\\}_{0}^{n_{yl1}},\\{y_{2}(k)\\}_{0}^{n_{yl2}},...,\\{y_{n0}(k)\\}_{0}^{ln_{yln_{0}}},\\\
\,\,\,\,\,\,\,\,\,\,\,\,\,\\{u_{1}(k)\\}_{n_{dl1}}^{n_{ul1}},\\{u_{2}(k)\\}_{n_{dl2}}^{n_{ul2}},...,\\{u_{n_{i}}(k)\\}_{n_{dln_{i}}}^{n_{ud1n_{i}}}]\end{array}$
(2)

$n_{y}$ and $n_{u}$ define the number of delayed outputs and inputs
respectively. $n_{d}$ is the number of pure delays. $n_{y}$ is a $n_{0}*n_{0}$
matrix and $n_{u}$, $nd$ are $n_{0}*n_{i}$ matrices. $f_{l}$ are unknown non
linear functions. MISO models are estimated independly [9], so, to simplify
the notation, the output index $l$ is omitted and we will be interested only
in the multi-input, mono-output case. The Takagi-Sugeno MISO rules are
estimated from the system input- output data[15]. The base rule contains $r$
rules of the following form:

$\begin{array}[]{l}\textbf{R}_{i}:Ify_{1}(k)\,\,\,is\,\,\,\textbf{A}_{i1}\,\,\,and\,\,\,if\,\,\,u_{nu}(k-n+1)\,\,\,is\,\,\,\textbf{A}_{{}_{ino}}\\\
\textbf{then}\,\,\,y_{i}(k+1)=\sum\limits_{j=1}^{n}a_{ir}y_{i}(k-j+1)+\sum\limits_{j=1}^{n}b_{ij}u_{i}(k-j+1)\\\
+\sum\limits_{l=1}^{nu}\sum\limits_{j=1}^{n}b_{ilj}u_{l}(k+j-1)+c_{i}\,\,\,\,\,$i=1,2..,r$\end{array}$
(3)

##  III Estimation method of recursive weighted least-squares (RWLS)

For nonlinear systems the online adaptation is necessary to obtain a model
able to continue the system in its evolution. The system described by relation
(4) can also be rewritten as:

$y_{i}(k)=\theta^{t}_{i}\varphi_{i}(k-1)$ (4)

with $\theta$ being a system parameter vector and $\varphi$ a regression
vector. It should be noted that the system (5) is in general nonlinear but it
is linear with respect to its unknown parameter vectors. Based on
parameterizations (4), the identification algorithm giving estimates
$\widehat{\theta}(k)$ of $\theta(k)$ can be obtained using the RWLS.
We define:

$\begin{array}[]{c}\varphi_{i}({k-1})=[\mu_{i}\,y_{i}(k-1)...\,\mu_{ij}y_{i}(k-n)\\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\mu_{i}u_{i}(k-1)...\,\mu_{i}u_{i}(k-n)\,\,\,\mu_{i}]\end{array}$
(5) $\theta_{i}=\left[{a_{i1}...a_{in}\,b_{i1}...b_{in}c_{i}}\right]$ (6)
$\varphi_{i}\left({k-1}\right)=\left[{\varphi^{t}_{i1}\left({k-1}\right)\,\varphi^{t}_{i2}\left({k-1}\right)...\varphi_{ir}^{t}\left({k-1}\right)}\right]^{t}$
(7)
$\theta_{i}(k)=\theta_{i}(k-1)+L_{i}(k)[y_{i}(k)-\varphi^{t}(k)\theta_{i}^{t}(k-1)]$
(8)
$L_{i}(k)=\frac{P(k-1)*\varphi^{t}(k)}{1/\mu_{ik}+\varphi(k)P(k-1)\varphi^{t}}$
(9) $P(k)=P_{i}({k-1}-L_{i}(k)\varphi(k)P_{i}(k-1)$ (10)

for $k=1,...,N,P(k-1)$ is a covariance matrix and L(k) referred to the
estimator gain vector. A common choice of initial value is to take
$\theta_{i}(0)=0$ and $P_{i}(0)=\alpha I$ where $\alpha$ is a large number.

##  IV PID control systems of multivariable processes

Consider a multivariable PID control structure as shown in Fig. 1, where:
Desired output vector : $\textbf{Y}_{d}=[y_{d1},y_{d2},...,y_{dn}]^{T}$.
Actual output vector: $\textbf{Y}=[y_{1},y_{2},...,y_{n}]^{T}$.
Error vector :
$\textbf{E}=\textbf{Y}_{d}-\textbf{Y}=[y_{d1}-y_{1},y_{dn}-y_{2},...,y_{dn}-y_{n}]=[e_{1},e_{2},...,e_{n}]^{T}$.
Control input vector : $\textbf{U}=[u_{1},u_{2},...,u_{n}]^{T}$.
$n*n$ multivariable processes:

$\textbf{H}(z)=\left|\begin{array}[]{ccc}h_{11}(z)&...&h_{1n}(z)\\\
...&...&...\\\ h_{n1}(z)&...&h_{nn}(z)\end{array}\right|$ (11)

$n*n$multivariable PID controller:

$\textbf{C}(z)=\left|\begin{array}[]{ccc}c_{11}(z)&...&c_{1n}(z)\\\
...&...&...\\\ c_{n1}(z)&...&c_{nn}(z)\end{array}\right|$ (12)

The form of $kij(z)$, for $i,j\in\underline{n}$ and
$\underline{n}=\\{1,2,...,n\\}$, is given by:

$\textbf{C}(z)=kp_{ij}(1+\frac{z}{Ti_{ij}(z-1)}+\frac{(z-1)}{Td_{ij}z})$ (13)

where $kp$ is the proportional gain, Ti is the integral time constant, and
$Td$ is the derivative time constant. It can be also rewritten (9) as:

$\textbf{C}(z)=kp_{ij}+\frac{ki_{ij}z}{(z-1)}+\frac{kd_{ij}(z-1)}{z})$ (14)

where $ki=kp/Ti$ is the integral gain and $kd=kp*Td$ is the derivative gain.
For convenience, let $K=[kp_{ij};ki_{ij}$ ; $kd_{ij}]^{T}$ represent the gains
vector of $i^{th}$ row and $j^{th}$ column[12]. In the design of a PID
controller, the performance criterion or objective function is first defined
based on our desired specifications and constraints under input testing
signal. Typical output specifications in the time domain are peak
overshooting, rise time, settling time, and steady-state error, to name a few.

Figure 1: A multivariable PID control system.

Three kinds of performance criteria usually considered in the control design
are integral of the Absolute Error (IAE), integral of Square Error (ISE) and
integral of Time weighted Square Error (ITSE) which are given as:

$\textbf{IAE}=|{e_{1}(k)+e_{2}(k)}+...+e_{n}(k)|$ (15)
$\textbf{ISE}=\sum{e_{1}(k)}^{2}+\sum{e_{2}(k)}^{2}+...+\sum{e_{n}(k)}^{2}$
(16) $\textbf{ITSE}=\sum k*{e_{1}(k)}^{2}+\sum k*{e_{2}(k)}^{2}+...+\sum
k*{e_{n}(k)}^{2}$ (17)

Therefore, for the PSO-based PID tuning, these performance indexes (Eqs.
(17)-(19)) will be used as the objective function. In other word, the
objective in the PSO-based optimization is to seek a set of PID parameters
such that the feedback control system has minimum performance index.

###  IV-A Tuning of PID uzing Z-N method

The first method of Z-N tuning is based on the open-loop step response of the
system. The open-loop system s Shaped response is characterized by the
parameters, namely the process time constant $T$ and $L$. These parameters are
used to determine the controller s tuning parameters (see TABLE.1).

TABLE I: Ziegler-Nichols open-loop tuning parameter Controller | kp | Ti=kp/ki | Td=kd/kp
---|---|---|---
P | T/L | - | 0
PI | 0.9(T/L) | L/0.3 | 0
PID | 1.2(T/L) | 2L | 0.5L

The second method of Z-N tuning is closed-loop tuning method that requires the
determination of the ultimate gain and ultimate period. The method can be
interpreted as a technique of positioning one point on the Nyquist curve [13].
This can be achieved by adjusting the controller gain (Ku) till the system
undergoes sustained oscillations (at the ultimate gain or critical gain),
whilst maintaining the integral time constant ( Ti ) at infinity and the
derivative time constant (Td) at zero (see TABLE.2).

TABLE II: Ziegler-Nichols closed-loop tuning parameter Controller | kp | Ti=kp/ki | Td=kd/kp
---|---|---|---
P | 0.5ku | - | 0
PI | 0.45ki | 1.5kp/Pu | 0
PID | 0.6ku | 2kp/Pu | kpPu/8

###  IV-B Implementation of PSO-Based PID Tuning

####  IV-B1 Particle swarm optimization (PSO)

Particle swarm optimization was introduced by Kennedy and Eberhart by
simulating social behavior of birds flocks in (199[10]. The PSO algorithm has
been successfully applied to solve various optimization problems [14]. The PSO
works by having a group of m particles. Each particle can be considered as a
candidate solution to an optimization problem and it can be represented by a
point or a position vector $\textbf{X}_{ij}=[X_{i1},...,X_{id}]$ in a d
dimensional search space which keeps on moving toward new points in the search
space with the addition of a velocity vector
$\textbf{V}_{ij}=[V_{i1},...,V_{id}]$ to further facilitate the search
procedure. The initial positions and velocities of particles are random from a
normal population in the interval [0, 1]. All particles move in the search
space to optimize an objective function f. Each member of the group gets a
score after evaluation on objective function f. The score is regarded as a
fitness value. The member with the highest score is called global best. Each
particle memorizes its previous best positions. During the search process all
particles move toward the areas of potential solutions by utilizing the
cognitive and social learning components. The process is repeated until any
prescribed stopping criterion is reached. After any iteration, all particles
update their positions and velocities to achieve better fitness values
according to the following:

$\displaystyle\textbf{V}_{pd}^{t+1}$ $\displaystyle=$
$\displaystyle\omega\textbf{V}_{pd}^{t}+c_{1}r_{1}(\textbf{pbest}^{t}-\textbf{X}_{pd}^{t})$
$\displaystyle+$ $\displaystyle
c_{2}r_{2}(\textbf{gbest}^{t}-\textbf{X}_{id}^{k}),$
$\displaystyle\textbf{X}_{pd}^{t+1}$ $\displaystyle=$
$\displaystyle\textbf{X}_{pd}^{t}+\textbf{V}_{pd}^{t+1},$ (19)

where:
$t$ is the current iteration number, $\textbf{pbest}_{i}$ is ${pbest}$ of
particle $i$, $\textbf{gbest}_{g}$ is ${gbest}$ of the group, $r_{1},r_{2}$
are two random numbers in the interval [0, 1], $c_{1},c_{2}$ are positive
constants and $w$ is the inertia weight,is a parameter used to control the
impact of the previous velocities on the current velocity. It influences the
tradeoff between the global and local exploitation abilities of the particles.
Weight is updated as:

$\omega=\omega_{\max}-\left({\frac{{\omega\max-\omega_{\min}}}{{iter_{\max}}}}\right)iter$
(20)

where $\omega_{\min}$, $\omega_{\max}$, $iter$, and $iter_{\max}$ are minimum,
maximum values of $\omega$ , the current iteration number and pre-specified
maximum number of iteration cycles, respectively.

####  IV-B2 Proposed PSO-PID Controller

This paper presents a PSO-PID controller for searching the optimal controllers
parameters of MIMO nonlinear system ,$kp_{i}$ , $ki_{i}$ and , $kd_{i}$ with
the PSO algorithm. Each individual $K_{i}$ contains 3*m members $kp_{i}$ ,
$ki_{i}$ and , $kd_{i}$. Its dimension is n*3*m. The searching procedures of
the proposed PSO-PID controller were shown as below [12]. Optimal design for
both conventional PID controllers can be fulfilled using PSO technique. Based
on the PSO technique, the PID controller can be tuned to some parameters
values that minimize those fitness functions given in (15), (16) and(17). The
algorithmic steps for the PSO is as follows:

  * •

Step 1: Select the number of particles, generations, tuning accelerating
coefficients $c_{1}$ and $c_{2}$ and random numbers $r_{1}$, and $r_{2}$ to
start the optimal solution searching.

  * •

Step 2: Initialize the particle position and velocity.

  * •

Step 3: Select the particle s individual best value for each generation.

  * •

Step 4: Select the particle s global best value, particle near the target
among all the particles, is obtained by comparing all the individual best
values.

  * •

Step 5: Update particle individual best pbest , global best gbest , in the
velocity equation (18) and obtain the new velocity.

  * •

Step 6: Update the new velocity value in Eq. (19) and obtain the position of
the particle.

  * •

Step 7: Find the optimal solution with a minimum (IAE, ISE, ITSE) from the
updated new velocity and position values.

##  V SIMULATION RESULTS

This section presents a simulation example to shown an application of the
proposed control algorithm and its satisfactory performance. The MIMO
nonlinear system is characterized by the equation(16), [16][17].

$\left\\{\begin{array}[]{ll}y1(k)=\frac{a_{1}y_{1}(k-1)y_{2}(k-1)}{1+a_{2}y_{1}^{2}(k-1)+a_{3}y_{2}^{2}(k-1)}+\\\
\,\,\,\,\,\,\,a_{4}u_{1}(k-2)+a_{5}u_{1}(k-1)+a_{6}u_{2}(k-1)\\\
y_{2}(k)=\frac{b_{1}y_{2}(k-1)sin(y_{2}(k-2))}{1+b_{2}y_{2}^{2}(k-1)+b_{3}y_{1}^{2}(k-1)}+\\\
\,\,\,\,\,\,\,b_{4}u_{2}(k-2)+b_{5}u_{2}(k-1)+b_{6}u_{1}(k-1)\end{array}\right.$
(21)

The system parameters are:
$a_{1}=0.7,a_{2}=1,a_{3}=1,a_{4}=0.3,a_{5}=1,a_{6}=0.2,b_{1}=0.5,b_{2}=1,b_{3}=1,b_{4}=0.5,b_{5}=1andb_{6}=0.2$
which is used as a test for control techniques introduced in this paper, to
demonstrate the effectiveness of the proposed algorithms. Here $y_{1}$ and
$y_{2}$ are the outputs, $u_{1}$ and $u_{2}$ are the inputs which is uniformly
bounded in the region $[-2,2]$.
We choose $[y_{1}(k-1),y_{1}(k-2),u_{1}(k-1),u_{1}(k-2),u_{2}(k-1)]$ and
$[y_{2}(k-1),y_{2}(k-2),u_{2}(k-1),u_{2}(k-2),,u_{2}(k-1)]$ as inputs
variables, and the number of fuzzy rules is four. The setup applied in this
work was the following: the population size was 20, the stopping criterion was
30 generations, $\omega_{min}=0.5$, $\omega_{max}=0.9$, and $c_{1}=c_{2}=2$.

Figure 2: System response (y1) Figure 3: System response (y2) TABLE III: Optimized PID parameters (y1) Tuning Method | kp | ki | kd
---|---|---|---
Z-N-PID | 32.3431 | 3.2943 | 4.4829
PSO-PID1 (ISE) | $26.7236$ | 46.2192 | 30.136
PSO-PID1 (IAE) | $8.7263$ | 46.2192 | 33.1360
PSO-PID1 (ITSE) | $5.3487$ | 15.7988 | 45.4369
TABLE IV: Optimized PID parameters (y2) Tuning Method | kp | ki | kd
---|---|---|---
Z-N PID | 38.0743 | 4.6739 | 5.6734
PSO-PID1 (ISE) | $35.7236$ | 16.2192 | 9.136
PSO-PID2 (IAE) | $39.5246$ | 17.2514 | 9.7983
PSO-PID3 (ITSE) | $45.3487$ | 15.7988 | 41.4369
TABLE V: Step response performance for PID controllers (y1) Tuning Method |  Overshoot(%) | Rise Time | Setting Time
---|---|---|---
Z-N PID | 55.3483 | 0.1264 | 1.6733
SPSO-PID1 (ISE) | $41.6977$ | 0.0474 | 0.6182
PSO-PID2 (IAE) | $40.5825$ | 0.0453 | 0.4791
PSO-PID3 (ITSE)t | $46.1849$ | 0.0374 | 0.4246
TABLE VI: Step response performance for PID controllers (y2) Tuning Method | Overshoot(%) | Rise Time | Setting Time
---|---|---|---
Z-N PID | 64.8174 | 0.1352 | 3.2941
PSO-PID1 (ISE) | $40.8062$ | 0.0929 | 0.7970
PSO-PID2 (IAE) | $42.3434$ | 0.0884 | 0.7775
PSO-PID3 (ITSE) | $48.5050$ | 0.0389 | 0.5265

In the conventionally Z-N tuned PID controller, the systems response produces
high overshoot, but a better performance obtained with the implementation of
PSO-based PID controller tuning. In the PSO-based PID controllers (PSO-PID),
different performance index gives different results. These are shown in TABLE.
III and TABLE. IV. Comparative results for the PID controllers are given below
in TABLE. V and TABLE. VI where the step response performance is evaluated
based on the overshoot, settling time and Rise time. The corresponding plot
for the step responses are shown in Fig. 2 and Fig.3.

##  VI CONCLUSIONS

This paper presents a design method for determining the PID controller
parameters using the PSO method for MIMO nonlinear systems. The proposed
method integrates the PSO algorithm with performance criterions into a PSO-PID
controller. The comparison between PSO-based PID (PSO-PID) performance and the
ZN-PID is presented. The results show the advantage of the PID tuning using
PSO-based optimization approach.

## References

  * [1] Astrom. K. J and H gglund. T, PID Controllers: Theory, Design, and Tuning, ISBN-10: 1556175167, ISBN-13. 978-1556175169, Edition. 2 Sub, January 1, 1995.
  * [2] N. Suda, PID Control, Asakura Publishing company, Ltd., ISBN 978-4-254-20966-2, Tokyo, 1992.
  * [3] Luyben. W. L. , A simple method for tuning SISO controllers in a multivariable system, Industrial Engineering Chemistry Product Research and Development, vol. 25, pp. 654 660, 1986.
  * [4] Yusof, R., Omatu, S. , A multivariable self-tuning PID controller, Internal Journal of Control, vol. 57(6), pp. 1387 1403, 1993.
  * [5] Wang. Q. G, Zou. B, Lee. T. H, Qiang. B, Auto-tuning of multivariable PID controllers from decentralized relay feedback, Automatica, vol. 33(3), pp. 319 330, 1997.
  * [6] Kennedy. J, and Eberhart. C, Particle Swarm Optimization, Proceedings of the IEEE International Conference on Neural Networks, Australia, pp. 1942-1948, 1995.
  * [7] Oliveira. P. M, Cunha. J. B, and Coelho. J. o,Design of PID controllers using the Particle Swarm Algorithm, Twenty-First IASTED International Conference: Modeling, Identification, and Control, Innsbruck, Austria, 2002.
  * [8] Lagrat. I, Ouakka. H and Boumhidi. L. I, Fuzzy clustring for identification of Takagi-Sugeno fuzzy models of a class of nonlinear multivariable systems, Facult Des Sciences, B. P, Atlas, 30000 Fez- MOROCCO, 1996.
  * [9] Takagi. T, Sugeno. M, Fuzzy Identification of Systems and its Application to Modeling and Control, IEEE Transactions on Systems, Man and Cybernetics, vol. 15(1), pp. 116-132, 1985.
  * [10] Qin. S. J and Badgwell. T. A, A survey of industrial model predictive control technology, Control Engineering Practice, vol. 11, pp. 733-764, 2003.
  * [11] Chang. W. D, A multi-crossover genetic approach to multivariable PID controllers tuning, Department of Computer and Communication, Shu-Te University, Kaohsiung 824, Taiwan, Expert Systems with Applications, vol. 33 pp. 620-626, 2007.
  * [12] Morkos. S, Kamal. H, Optimal Tuning of PID Controller using Adaptive Hybrid Particle Swarm Optimization Algorithm, Int. J. of Computers, Communications and Control, ISSN pp. 1841-9836, 2012.
  * [13] Astrom. K. J. and Hagglund. t, PID Controllers: Theory, Design and Tuning, ISA, Research Triangle, Par, NC, 1995.
  * [14] Soltani, M., Chaari, A. and Benhmida, F. , A novel fuzzy c regression model algorithm using new measure of error and based on particle swarm optimization, International Journal of Applied Mathematics and Computer Science, Vol. 22, No. 3, pp. 617-628, 2012.
  * [15] I. Lagrat. I, Ouakka. H and Boumhidi. I, Fuzzy adaptive control of a class of MISO nonlinear systems, Control and Cybernetics, vol. 37, No. 1, 2008.
  * [16] Song. F and Li. P, MIMO Decoupling Control Based on Support Vector Machines $\alpha^{th}$-order Inversion. Proceedings of the 6th World Congress on Intelligent Control and Automation, Dalian-China, pp. 1002-1006, 2006.
  * [17] Petlenkov. E, NN-ANARX Structure Based Dynamic Output Feedback Linearization for Contro of Nonlinear MIMO Systems, Proceedings of the 15th Mediterranean Conference on Control and Automation, Athens-Greece, pp. 1-6, 2007.


11institutetext: National Research University Higher School of Economics
11email: {dgpopov, avpugachev, posvyatokum<EMAIL_ADDRESS>11email:
<EMAIL_ADDRESS>
# Evaluation of Sentence Embedding Models for Natural Language Understanding
Problems in Russian

Dmitry Popov  Alexander Pugachev  Polina Svyatokum  Elizaveta Svitanko
Ekaterina Artemova

###### Abstract

We investigate the performance of sentence embeddings models on several tasks
for the Russian language. In our comparison, we include such tasks as multiple
choice question answering, next sentence prediction, and paraphrase
identification. We employ FastText embeddings as a baseline and compare it to
ELMo and BERT embeddings. We conduct two series of experiments, using both
unsupervised (i.e., based on similarity measure only) and supervised
approaches for the tasks. Finally, we present datasets for multiple choice
question answering and next sentence prediction in Russian.

###### Keywords:

multiple choice question answering next sentence prediction paraphrase
identification sentence embedding

##  1 Introduction

With word embeddings have been in the focus of researchers for several
decades, sentence embeddings recently started to gain more and more attention.
A word (sentence) embedding is a projection in a vector space of relatively
small dimensionality, that can capture word (sentence) meaning by making the
embeddings of two words (sentences) that are similar to get closer in this
vector space. With no doubts, the usage of the properly trained word
embeddings boosted the quality of the majority of natural language processing
(NLP), information extraction (IE), neural machine translation (NMT) tasks.
However, it seems that word embedding models are facing their limits when it
comes to polysemy and ambiguity. A natural solution to these problems lies in
sentence embedding models too, as they allow to capture the context–dependent
meaning of any part of the sentence.

For the last two years, the amount of projects and papers on sentence
embeddings has increased dramatically. Several research groups show that a
complex pre–trained language model may serve both as an input to another
architecture and as a standalone sentence embedding model. The most famous
models of this type, ELMo, and BERT, named after characters of Sesame Street
show, can be treated as ‘‘black boxes’’, that read a sentence in and output a
vector representation of the sentence. The efficiency of these models for the
English language is well studied already not only in several natural language
understanding (NLU) tasks but also for language modeling and machine
translation. However little has been done to explore the quality of sentence
embeddings models for other languages, including Russian, probably due to the
absence of NLU datasets. The contribution of this paper is two–fold. First, we
create two novel NLU datasets for the Russian language: a) multiple choice
question answering dataset, which consists of open domain questions on various
topics; b) next sentence prediction dataset, that can be treated as a kind of
multiple choice question answering. Given a sentence, one needs to choose
between four possible next sentences. Correct answers are present in both
datasets by design, which makes supervised training possible. Second, we
evaluate the quality of several sentence embedding models for three NLU tasks:
multiple choice question answering, next sentence prediction and paraphrase
identification.

The results confirm, that in the tasks under consideration, sentence–level
representations perform better than the word–level ones as in many other
tasks.

The remainder is structured as follows. Section 2 presents an overview of
related works; Section 3 introduces the datasets, Section 4 describes the
methods we used to tackle the tasks. The results of the experiments are
presented in Section 5. Section 6 concludes.

##  2 Related work

A word embedding is a dense vector representation of a word that allows
modeling some sort of semantic (or functional) word similarity. Two words are
considered similar if a similarity measure, such as cosine function, for
example, between corresponding vectors is high enough. As this definition is
rather vague, there are two main approaches to evaluating the quality of a
word embedding model. Intrinsic evaluation is based on conducting on standard
word pairs and analogies datasets, such as
Word–353111http://www.cs.technion.ac.il/~gabr/resources/data/wordsim353/ or
Simlex–999222https://fh295.github.io/simlex.html. External evaluation requires
an external machine learning tasks, such as sentiment classification or news
clustering, which can be evaluated by a quality measure, such as accuracy or
Rank index. All factors of machine learning algorithms are held equals so that
these quality measures are affected by the word embeddings model only.

The methodology of creation and evaluation of sentence embeddings is less
developed, when compared to the zoo of word embedding models. The evaluation
of sentence embeddings models is usually conducted of natural language
understanding tasks, such as semantic textual similarity, natural language
inference, question answering, etc. Further, we overview the basic and more
advanced models of sentence embeddings.

###  2.1 Unsupervised sentence embeddings

The simplest way of obtaining the sentence embedding is by taking the average
of the word embeddings in the sentence. The averaging can treat words equally,
rely on $tf-idf$ weights [1], take the power mean of concatenated word
embeddings [17] and employ other weighting and averaging techniques.

Another approach of unsupervised training of sentence embeddings is Doc2Vec
[12], which succeeds after Word2Vec and FastText. Word2Vec [13] by Mikolov et
al. is a predictive embedding model and has two main neural network
architectures: continuous Bag–of–Words (CBoW) and continuous skip–gram [14].
Given a central word and its context (i.e., $k$ words to the left and $k$
words to the right), CBoW tries to predict the context words based on the
central one, while skip–gram on tries to predict the context words based on
the central one.

Joulin et al. [9] suggest an approach called FastText, which is built on
Word2Vec by learning embeddings for each subword (i.e., character $n$–gram,
where $n$ can vary between some bounds and is a hyperparameter to the model).
To achieve the desired word embeddings, the subword embeddings are averaged
into one vector at each training step. While this adds a lot of additional
computation to training, nevertheless it enables word embeddings to encode
sub–word information, which appears to be crucial for morphologically rich
languages, the Russian language being one of them.

The goal of the aforementioned Doc2Vec approach, introduced by Mikolov et al.
[12], is to create an embedding of a document, regardless of its length.

All the studies as mentioned earlier work properly on the English language and
some of them release pre–trained Russian embeddings, too. Russian–specific
RusVectores [11] pre–trained model, which was trained on Russian National
Corpora, Russian Wikipedia and other Web corpora possesses several pre–trained
word embeddings models and allows to conduct a meaningful comparison between
the models and their hyperparameters.

The Skip–Thought model follows the skip–gram approach: given a central
sentence, the context (i.e., the previous and the next) sentences are
predicted. The architecture of Skip–Thought consists of a single encoder,
which encodes the central sentence and two decoders, that decode the context
sentences. All three parts are based on recurrent neural networks. Thus their
training is rather difficult and time–consuming.

###  2.2 Supervised sentence embeddings

In recent years, several sources say the unsupervised efforts to obtain
embeddings for larger chunks of text, such as sentences, are not as successful
as the supervised methods. Conneau et al. [5] introduced the universal
sentence representation method, which works better than, for instance,
Skip–Thought [10] on a wide range of transfer tasks. It’s model architecture
with BiLSTM network and max–pooling is the best current universal sentence
encoding method. The paper on Universal Sentence Encoder [3] discovers that
transfer learning using sentence embeddings, which tends to outperform the
word level transfer. As an advantage, it needs a small amount of data to be
trained in a supervised fashion.

###  2.3 Language models

One of the recently introduced and efficient methods are embeddings from
Language Models (ELMo) [16] that models both complex characteristics of word
use, and how it is different across various linguistic contexts and can also
be applied to the whole sentence instead of the words. Bidirectional Encoder
Representations from Transformers (BERT) [6] has recently presented
state–of–the–art results in a wide variety of NLP tasks including Natural
Language Inference, Question Answering, and others. The application of an
attention model called Transformer allows a language model to have a better
understanding of the language context. In comparison to the single–direction
language models, this one uses another technique namely Masked LM (MLM) for a
bidirectional training.

###  2.4 Evaluation of sentence embedding models

While different embedding methods are previously discussed, the most suitable
evaluation metric is also a challenge. Quality metrics are largely overviewed
in RepEval333https://aclweb.org/anthology/events/repeval-2017/ proceedings. In
[2] both widely–used and experimental methods are described. SentEval is used
to measure the quality of sentence representations for the tasks of natural
language inference or sentence similarity [4]. The General Language
Understanding Evaluation (GLUE) benchmark444https://gluebenchmark.com is one
of the popular benchmarks for evaluation of natural understanding systems. The
top solutions, according to the GLUE leadership, exploit some sort of sentence
embedding frameworks. GLUE allows testing any model in nine sentence or
sentence–pair tasks, such as natural language inference (NLI), semantic
textual similarity (paraphrase identification, STS) or question answering
(QA).

##  3 Datasets

###  3.1 Multiple Choice Question Answering (MCQA)

The portal geetest.ru provides tests on many subjects such as history,
biology, economics, math, etc., with most of the tasks being simple
wh–questions. These tests were downloaded to create a multiple choice question
answering dataset.

Every test is a set of questions in a specific area of a certain subject. For
the final dataset we handpicked tests from the following subjects: Medicine,
Biology, History, Geography, Economics, Pedagogy, Informatics, Social Studies.

The selection was based on two criteria. Firstly, questions should be
answerable without knowing the topic of the test. For example, some questions
in test could not be answered correctly without presenting a context of a
specific legal system. Secondly, questions should test factual knowledge and
not skills. For example, almost any math test will require to perform
computations, and such type of task is not suitable for this dataset.

What is more, we have collected questions on history and geography from
ege.sdamgia.ru. The selection of questions was similar to described above. As
a result, the total number of questions is around 11k with three subjects
being larger than other. These subjects are: medicine, (4k of questions),
history (3k of questions), biology (2k of questions). The resulting dataset is
somewhat similar to Trivia QA dataset, however the domains are different [8].

###  3.2 Multiple choice next sentence prediction (NSP)

We have collected a new dataset with 54k multiple choice questions where the
objective is to predict the correct continuation for a given context sentence
from four possible answer choices. The dataset was produced using the corpora
of news articles of ‘‘Lenta.ru’’555https://github.com/yutkin/Lenta.Ru-News-
Dataset. To sample correct and incorrect answer choices we chose a trigram and
a context sentence which ends on this trigram. The correct answer choice was
the continuation of the context sentence, and the incorrect choices were the
sentences following the trigram in other sentences in the corpora. Labels of
correct answers were sampled uniformly. So, the random or constant predictions
results in an accuracy score of 0.25.

###  3.3 Paraphrase identification (PI)

For a paraphrase detection task, we used Russian language paraphrase dataset
collected from news titles 666http://paraphraser.ru. The dataset contains 7k
pairs of titles which are the same, close and different by meaning. Constant
prediction on this dataset gives us an accuracy score of 0.64. In a sense,
Microsoft Research Paraphrase Corpora[7] is similar to this dataset. Both of
them were collected from news titles.

Question
Какие из указанных симптомов характерны для фарингита?
---
Answer choices
1\. резкая боль в горле
2\. першение и дискомфорт в горле
3\. затруднение проглатывания слюны
4\. субфебрильная температура

Table 1: Examples from MCQA dataset. The correct answer is bolded.

Context
Мартин Скорсезе намеревается приступить к съемкам экранизации романа
«Молчание» японского писателя Сюсаку Эндо в 2014 году,
---
Answer choices
1\. был оснащен одиннадцатиметровым стеклянным полом шириной два метра,
сообщается в полученном «Домом» пресс-релизе компании «Сен-Гобен».
2\. когда он провозил мак для одной из продуктовых баз
3\. сообщает Deadline. Финансированием проекта займутся компании Emmett/Furla
Films и Corsan Films
4\. а производить трубы там начали уже спустя два года. В числе поставщиков
«Газпрома» ЗТЗ появился в 2017 году

Table 2: An example from NSP dataset. The correct answer is bolded.

text 1 |  text 2 | label
---|---|---
Мэрилин Мэнсон передумал выступать в России. |  Мэрилин Мэнсон отменил тур по России. | 1
Бывший чемпион мира по боксу умер в 48 лет. |  Как судей судили за их решения. | 0

Table 3: Examples from the PI dataset.

###  3.4 Dataset statistics

Frequency distribution of top 25 most frequent tokens, the number of unique
tokens and the total number of tokens in the datasets can be found in Figure
1. Sentence length distribution, average and median sentence length can be
found in Figure 2.

Figure 1: Frequency distribution of top 25 tokens for MCQA, NSP, PI datasets.

Figure 2: Sentence length distribution for MCQA, NSP, PI datasets.

##  4 Methods

There are two types of problems we were considered for the comparison of
sentence embeddings:

  * •

Multiple choice questions. Datasets for this type are MCQA and NSP ones. The
objective of the problem is to predict the correct answer for a given
question/context and four answer choices.

  * •

Paraphrase identification. The goal for such a problem is to predict if two
given sentences are a paraphrase or not.

To compare different methods of obtaining sentence embeddings, we have
explored supervised and unsupervised scenarios of using such embeddings.

###  4.1 Unsupervised approach

In unsupervised methods, we are interested in a similarity between sentence
embeddings in terms of cosine similarity.

Multiple choice questions. For such type of problem for a given set
$\\{q,a_{1},$ $a_{2},a_{3},a_{4}\\}$, where $q$ is an embedding of either a
question or a context sentence and $a_{i}$ is an embedding of $i$–$th$ answer
choice, the predicted answer choice is the choice which embedding is the most
similar to $q$.

Paraphrase identification. Let for a given pair of sentences $t_{1}$ and
$t_{2}$ are sentence embeddings of this pair respectively. First of all, we
split the dataset into training and test sets, after that searching for a
threshold $t$ on a training set such that pairs with $sim(t_{1},t_{2})>t$ will
be labeled as a paraphrase. Finally, we will evaluate results on a test set.

###  4.2 Supervised approach

Text vector representations are often inputs to machine learning models. In
this approach, we are aiming to figure out which methods of obtaining vector
representations are better as inputs into linear models such as the logistic
regression and which methods are better as inputs to a gradient boosting
models such as the CatBoost [15].

Multiple choice questions. Since we cannot just run a multiclass
classification as the correct answers numbers are not related to questions we
will make a binary classification model which predicts a probability for a
given question–answer (context–answer) pair to be correct, i.e. the answer is
the correct answer choice for the question/context. Then for a given
question/context and four answers, the predicted answer is the answer such
that the model gives the highest probability.

Paraphrase identification. For this problem, we just build a binary classifier
on a concatenation of sentence embeddings.

##  5 Experiments and results

###  5.1 FastText

Table 4: FastText embeddings results. Method | MCQA | NSP | PI
---|---|---|---
Accuracy |  F1 |  Accuracy | F1 |  Accuracy | F1
Unsupervised | 0.305 | 0.304 | 0.337 | 0.337 | 0.719 | 0.806
Logistic regression | 0.287 | 0.287 | 0.248 | 0.248 | 0.704 | 0.612
CatBoost | 0.318 | 0.317 | 0.496 | 0.496 | 0.762 | 0.715

As it can be seen from Table 4, FastText model accomplishes differently
depending on tasks and methods. The best quality on each task was reached by
CatBoost method according to Accuracy metrics. According to the F1 score,
CatBoost also outperforms other methods in all of the tasks except Paraphrase
identification where the best score with a large margin was achieved by the
unsupervised method. There can also be seen a big quality difference between
CatBoost and other methods in next sentence prediction task. Logistic
regression shows the worst results in each task. The overall performance of
methods based on FastText model is far from perfect. The results achieved
using FastText can be considered as a baseline for our investigation.

###  5.2 ELMo

We have used three ELMo models
777http://docs.deeppavlov.ai/en/master/intro/pretrained_vectors.html
pre–trained on Russian Wikipedia, ‘‘Lenta.Ru’’ news articles and Russian
tweets corpora, respectively. So, one of the main results obtained from our
experiments is how different domains of pre–trained models affects final
results.

Table 5: ELMo unsupervised experiments results. Method | Domain | MCQA | NSP | PI
---|---|---|---|---
Accuracy |  F1 |  Accuracy | F1 |  Accuracy | F1
Unsupervised | Wikipedia | 0.300 | 0.300 | 0.645 | 0.645 | 0.807 | 0.867
News | 0.293 | 0.293 | 0.691 | 0.691 | 0.807 | 0.866
Twitter | 0.291 | 0.291 | 0.559 | 0.559 | 0.803 | 0.863
Logistic regression | Wikipedia | 0.301 | 0.300 | 0.249 | 0.249 | 0.684 | 0.652
News | 0.318 | 0.318 | 0.249 | 0.248 | 0.702 | 0.668
Twitter | 0.317 | 0.316 | 0.251 | 0.250 | 0.705 | 0.674
CatBoost | Wikipedia | 0.314 | 0.314 | 0.647 | 0.647 | 0.773 | 0.729
News | 0.310 | 0.310 | 0.669 | 0.669 | 0.797 | 0.758
Twitter | 0.314 | 0.314 | 0.631 | 0.631 | 0.779 | 0.741

The results achieved by three methods based on three different pre–trained
ELMo models are presented in Table 5. The performance of these methods is
quite sensitive to the source of training data for ELMo model. For example,
regarding the MCQA task, models trained on the News and Twitter corpora
perform better than the model trained on Wikipedia, especially when logistic
regression is used. In the unsupervised setting, the quality of next sentence
prediction task highly depends on the source of training data ELMo model, too.
However, in most cases there is no significant difference in results between
three ELMo models.

One can notice that logistic regression in both cases (FastText model and all
three ELMo models) shows the worst results in the majority of the tasks.
Regarding the next sentence prediction task, the performance of logistic
regression has not gone far away from random choice. However, it shows better
results than other models in the MCQA task. The unsupervised method achieved
the best results for the paraphrase identification task. We can claim that the
use of ELMo model contributed to better results in next sentence and
paraphrase identification tasks, as there was observed significant improvement
in accuracy and F1 scores. Speaking of MCQA task, the results are comparable
with the previously obtained.

###  5.3 BERT

Table 6: BERT embeddings results on MCQA dataset.

Method | Best score | Average score | Worst score
---|---|---|---
Accuracy |  F1 |  Layer |  Accuracy | F1 |  Accuracy | F1
Unsupervised | 0.303 | 0.302 |  Concatenation of layers from 1 to 6 | 0.292 | 0.292 | 0.274 | 0.274
Logistic regression | 0.336 | 0.335 |  Layer number 1 | 0.324 | 0.323 | 0.310 | 0.310
CatBoost | 0.346 | 0.346 |  Max pooling of layers from 4 to 6 | 0.326 | 0.326 | 0.312 | 0.311

Table 7: BERT embeddings results on NSP dataset.

Method | Best score | Average score | Worst score
---|---|---|---
Accuracy |  F1 |  Layer |  Accuracy | F1 |  Accuracy | F1
Unsupervised | 0.508 | 0.508 |  Layer number 12 | 0.457 | 0.457 | 0.429 | 0.429
Logistic regression | 0.255 | 0.255 |  Max pooling of layers from 7 to 9 | 0.249 | 0.248 | 0.244 | 0.244
CatBoost | 0.514 | 0.514 |  Average pooling of layers from 7 to 12 | 0.479 | 0.479 | 0.414 | 0.414

Table 8: BERT embeddings results on PI dataset.

Method | Best score | Average score | Worst score
---|---|---|---
Accuracy |  F1 |  Layer |  Accuracy | F1 |  Accuracy | F1
Unsupervised | 0.801 | 0.857 |  Average pooling of layers from 1 to 3 | 0.787 | 0.851 | 0.775 | 0.843
Logistic regression | 0.715 | 0.676 |  Average pooling of layers from 7 to 12 | 0.693 | 0.651 | 0.670 | 0.615
CatBoost | 0.778 | 0.732 |  Layer number 3 | 0.763 | 0.713 | 0.749 | 0.694

Table 9: BERT embeddings results on MCQA dataset (1st and 12th layer).

Method | 1st layer | 12th layer | Average pooling
---|---|---|---
Accuracy | F1 | Accuracy | F1 | Accuracy | F1
Unsupervised | 0.298 | 0.298 | 0.296 | 0.296 | 0.296 | 0.296
Logistic regression | 0.336 | 0.335 | 0.321 | 0.321 | 0.326 | 0.326
CatBoost | 0.318 | 0.318 | 0.318 | 0.318 | 0.329 | 0.330

Table 10: BERT embeddings results on NSP dataset (1st and 12th layer).

Method | 1st layer | 12th layer | Average pooling
---|---|---|---
Accuracy | F1 | Accuracy | F1 | Accuracy | F1
Unsupervised | 0.429 | 0.429 | 0.508 | 0.508 | 0.484 | 0.484
Logistic regression | 0.244 | 0.244 | 0.248 | 0.248 | 0.247 | 0.246
CatBoost | 0.414 | 0.414 | 0.497 | 0.497 | 0.514 | 0.514

Table 11: BERT embeddings results on PI dataset (1st and 12th layer).

Method | 1st layer | 12th layer | Average pooling
---|---|---|---
Accuracy | F1 | Accuracy | F1 | Accuracy | F1
Unsupervised | 0.795 | 0.853 | 0.781 | 0.850 | 0.789 | 0.853
Logistic regression | 0.670 | 0.615 | 0.704 | 0.664 | 0.703 | 0.662
CatBoost | 0.762 | 0.708 | 0.758 | 0.706 | 0.764 | 0.718

Table 12: Final results.

Model | MCQA | NSP | PI
---|---|---|---
Accuracy |  F1 |  Accuracy | F1 |  Accuracy | F1
FastText | 0.318 | 0.317 | 0.496 | 0.496 | 0.762 | 0.806
ELMo | 0.318 | 0.318 | 0.691 | 0.691 | 0.807 | 0.867
BERT | 0.346 | 0.346 | 0.514 | 0.514 | 0.801 | 0.857

The results of different methods based on BERT embeddings are shown in Tables
8 – 12. All the results were obtained using BERT–Base Multilingual Cased
model888https://github.com/google-research/bert/blob/master/multilingual.md.
There were considered different BERT model layers and combinations of layers.
For each method and task, there is presented the best result achieved with
layer indication. From Table 8 we can see that using BERT embeddings we can
significantly improve results in MCQA task. The CatBoost method based on BERT
model noticeably outperforms FastText and ELMo models within this task.
According to Table 8, we can claim that BERT model could not get better
results compared to ELMo. Even the performance of logistic regression remained
the same. However, as we can notice from Table 8, the performance of BERT
model regarding paraphrase identification task is comparable to the ELMo
results. In both cases, the best score was achieved by the unsupervised method
and the worst by logistic regression. We suppose that in many cases BERT could
not outperform ELMo model because it was not trained for these tasks and the
best way for BERT is to fine–tune it by ourselves.

##  6 Conclusion

We tested three sentence embedding models: (a) FastText averaged over words in
the sentence, b) three pre–trained on various sources ELMo models, c) BERT
model in three NLU tasks for the Russian language. These tasks are a) multiple
choice question answering, b) next sentence prediction, c) paraphrase
identification. For the first two tasks, we presented our own new datasets.
These datasets are designed as multiple choice questions: given a question / a
sentence one need to choose a correct option from four possible answers /
continuations.

Our experiments show that the MCQA dataset is much more complicated than the
other two datasets. The quality of the results for this task is not as high as
for two others. All models perform somewhat similar in next sentence
prediction and paraphrase identification tasks. The paraphrase identification
dataset is highly unbalanced, and the positive examples are in the minority,
which may affect the quality if the results.

Overall, we can claim that we started to evaluate the popular sentence
embeddings frameworks in GLUE–like fashion for the Russian language. So far we
can state that (1) the word–level embeddings are outperformed by the
sentence–level embeddings, (2) the pre–trained models available online with no
doubts can attempt some of the NLU tasks with little or almost no fine tuning.
The directions of the future work may include probing of embedding models for
Russian rich morphology and free word order. The code of all experiments is
available on GitHub999https://github.com/foksly/aist-sentence-embeddings.

## Acknowledgements

This project was supported by the framework of the HSE University Basic
Research Program and Russian Academic Excellence Project ‘‘5–100’’.

## References

  * [1] Arroyo-Fernández, I., Méndez-Cruz, C.F., Sierra, G., Torres-Moreno, J.M., Sidorov, G.: Unsupervised sentence representations as word information series: Revisiting tf–idf. Computer Speech & Language 56, 107–129 (2019)
  * [2] Bakarov, A.: A survey of word embeddings evaluation methods (2018)
  * [3] Cer, D., Yang, Y., Kong, S.y., Hua, N., Limtiaco, N., John, R.S., Constant, N., Guajardo-Cespedes, M., Yuan, S., Tar, C., et al.: Universal sentence encoder. arXiv preprint arXiv:1803.11175 (2018)
  * [4] Conneau, A., Kiela, D.: Senteval: An evaluation toolkit for universal sentence representations (2018)
  * [5] Conneau, A., Kiela, D., Schwenk, H., Barrault, L., Bordes, A.: Supervised learning of universal sentence representations from natural language inference data. In: Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing. pp. 670–680. Association for Computational Linguistics, Copenhagen, Denmark (September 2017), https://www.aclweb.org/anthology/D17-1070
  * [6] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidirectional transformers for language understanding (2018)
  * [7] Dolan, W., Quirk, C., Brockett, C.: Unsupervised Construction of Large Paraphrase Corpora: Exploiting Massively Parallel News Sources. https://www.microsoft.com/en-us/download/details.aspx?id=52398
  * [8] Joshi, M., Choi, E., Weld, D.S., Zettlemoyer, L.: Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension. arXiv preprint arXiv:1705.03551 (2018)
  * [9] Joulin, A., Grave, E., Bojanowski, P., Mikolov, T.: Bag of tricks for efficient text classification. CoRR abs/1607.01759 (2016), http://arxiv.org/abs/1607.01759
  * [10] Kiros, R., Zhu, Y., Salakhutdinov, R., Zemel, R.S., Torralba, A., Urtasun, R., Fidler, S.: Skip-thought vectors (2015)
  * [11] Kutuzov, A., Kuzmenko, E.: Webvectors: a toolkit for building web interfaces for vector semantic models. In: International Conference on Analysis of Images, Social Networks and Texts. pp. 155–161. Springer (2016)
  * [12] Le, Q.V., Mikolov, T.: Distributed representations of sentences and documents (2014)
  * [13] Mikolov, T., Chen, K., Corrado, G., Dean, J.: Efficient estimation of word representations in vector space. CoRR abs/1301.3781 (2013), http://arxiv.org/abs/1301.3781
  * [14] Mikolov, T., Sutskever, I., Chen, K., Corrado, G., Dean, J.: Distributed representations of words and phrases and their compositionality. CoRR abs/1310.4546 (2013), http://arxiv.org/abs/1310.4546
  * [15] Ostroumova, L., Gusev, G., Vorobev, A., Dorogush, A.V., Gulin, A.: Catboost: unbiased boosting with categorical features. arXiv preprint arXiv:1706.09516 (2018)
  * [16] Peters, M., Neumann, M., Iyyer, M., Gardner, M., Clark, C., Lee, K., Zettlemoyer, L.: Deep contextualized word representations. Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (2018). https://doi.org/10.18653/v1/n18-1202, http://dx.doi.org/10.18653/v1/N18-1202
  * [17] Rücklé, A., Eger, S., Peyrard, M., Gurevych, I.: Concatenated power mean word embeddings as universal cross-lingual sentence representations. arXiv preprint arXiv:1803.01400 (2018)