# Efficient Dense Frontier Detection for 2D Graph SLAM Based on Occupancy Grid
Submaps

Juraj Oršulić1, Damjan Miklić2 and Zdenko Kovačić1  1University of Zagreb
Faculty of Electrical Engineering and Computing, Laboratory for Robotics and
Intelligent Control Systems
2 RoMb Technologies d.o.o., Zagreb
Email<EMAIL_ADDRESS>Faculty of Electrical Engineering and Computing,
University of Zagreb
Laboratory for Robotics and Intelligent Control Systems
Email<EMAIL_ADDRESS>
###### Abstract

In autonomous robot exploration, the frontier is the border in the world map
between the explored space and unexplored space. The frontier plays an
important role when deciding where in the environment the robots should go
explore next. We examine a modular control system pipeline for autonomous
exploration where a 2D graph SLAM algorithm based on occupancy grid submaps
performs map building and localization. We provide an overview of the state of
the art in frontier detection and the relevant SLAM concepts and propose a
specialized frontier detection method which is efficiently constrained to
active submaps, yet robust to SLAM loop closures.

Juraj Oršulić

Sensor data acquisition (lidar, IMU, odometry) SLAM Frontier detection
Exploration task generation and scheduling Path planning and following
Environment Figure 1: Block diagram providing a high-level overview of the
proposed control system for performing autonomous exploration. The robot may
be equipped with a laser rangefinder, an inertial measurement unit, and wheel
encoders for odometry. A Simultaneous Localization and Mapping module uses the
sensed environment data to build an environment map and to estimate the pose
therein, while a frontier detection module keeps track of the exploration
frontier. An exploration task generation and scheduling module assigns
exploration tasks to be performed according to an exploration strategy and
forwards it to a path planning and following module, which uses the map and
localization from SLAM to steer the robot towards the goal defined by the
assigned task. Notably, the frontier detector is tightly coupled with the SLAM
module, enabling an efficient implementation of frontier detection.

##  I Introduction

A fully autonomous mobile robot, able to explore, navigate and perform actions
in an unknown environment is the ultimate objective of today’s mobile robotics
research. To this end, we consider a single autonomous robot or an autonomous
team of robots tasked with exploring the unknown environment. The autonomous
exploration problem comprises collecting the data sensed from the environment,
using the collected data to build a structured model of the environment, self-
localizing in the environment model, high-level planning and scheduling of
robot tasks (mission generation and assignment), and path planning and
following. All of these need to be performed in real time.

In a common approach known as frontier exploration, the robot maintains
information about the border which divides the explored and unexplored space
in the environment – the _frontier_. Elements of the frontier represent places
in the environment which the robot may approach and thereby increase the
knowledge about the structure of the environment. With the information about
the exploration frontier available, mission planning can be described in its
simplest version as _(boldly) go where no one has gone before_.

Many components of the autonomous exploration problem mentioned above are
complex enough to be associated with their own field of robotics research,
resulting in sophisticated methods and software modules being available for
solving them. Namely, building the model of the environment (a map) and self-
localization therein may be performed by a module implementing a Simultaneous
Localization and Mapping (SLAM) algorithm. For this reason, we consider a
control system implementing a modular exploration pipeline as depicted in
Figure 1. Map building and localization are performed by a SLAM module. The
SLAM results – a map and a robot pose – are processed in a frontier detection
module. The detected frontier is then used by a high-level exploration task
generation and scheduling module, which creates and selects exploration tasks
to be executed according to an exploration strategy, and further requests the
path planning and following modules to execute the exploration tasks.

The main contribution of this paper is a piece of the exploration pipeline – a
new, efficient frontier detection approach, specialized for use with a 2D
graph SLAM algorithm based on occupancy grid submaps [1]. The proposed
approach is robust to loop closures and exploits the submap structure of the
SLAM algorithm in order to quickly perform frontier updates. By providing high
frequency incremental frontier updates which enable more responsive planning
of exploration objectives, it facilitates a real-time use case on large and
complex maps, e.g. the Deutsches museum dataset [1]. All the while the
proposed frontier detection algorithm delivers a result at least as good as a
naive frontier edge-detection algorithm, i.e. performing edge detection on a
completely assembled global map each time after SLAM updates the map by
inserting scans or optimizing the pose graph to perform loop closures.

##  II Related Work

###  II-A Frontier Exploration as a Prevalent Exploration Method

Frontier exploration in the context of autonomous robotics was first
introduced by Yamauchi in 1997 [2], paving the way for many others ([3, 4,
5]). Commonly, elements of the detected frontier are used as navigation goals
during planning of exploration tasks. Building on this, there are more complex
exploration strategies which attempt to coordinate entire robot teams ([6,
7]), or use frontiers as sinks in a potential field ([8]). Frontier detection
is therefore a key elementary operation in frontier exploration, and it is
important that it be performed as quickly as possible so that exploration can
be more efficient [9].

###  II-B State of the Frontier Detection Art

A naive algorithm for frontier detection is to perform edge detection on the
complete global map after each map update. However, this approach is not
feasible for larger maps and real-time robot operation with such maps, as it
presents a significant computational burden.

####  II-B1 Keidar and Kaminka’s seminal work on efficient frontier detection

Keidar and Kaminka [10] proposed in 2014 several approaches which attempt to
perform frontier detection in an efficient manner. The first, _Wavefront
Frontier Detector_ (WFD), consists of running two consecutive breadth-first
searches (BFS). The first BFS starts at the robot position and continues
throughout the free space, until eventually a frontier point is found which
belongs to a component of connected frontier points. From there, the rest of
the connected component is found by a second BFS along the connected frontier
points. While WFD avoids searching the unoccupied space, it still searches all
observed free space in each iteration, which may degenerate into a full map
search as exploration progresses.

The second approach to frontier detection proposed by Keidar and Kaminka, the
_Fast Frontier Detector_ (FFD), does not use the map built by SLAM, but rather
constructs the contour of each laser scan using Bresenham’s line algorithm,
and uses the constructed contour to detect the frontier and store it in a
specialized data structure. Quin and Alempijević [9] note that FFD has to be
executed after each scan, which results in many wasteful calculations if
frontier updates are required only occasionally, and that Bresenham’s line
algorithm can cut across unobserved space and miss some frontier cells. The
proposed approach does not require execution after each processed scan,
supporting a use case where frontier updates are required only occasionally.

FFD is also notable for introducing the concept of _active area_ – a bounding
box positioned in the map around the robot position, circumscribing the last
scan the map was updated with. The frontier update step is sped up by
restricting it to the active area. Keidar and Kaminka also applied this
concept to the WFD detector, yielding the _incremental WFD_ (WFD-INC)
algorithm, which requires non-trivial auxiliary data structures for frontier
point maintenance. The proposed algorithm uses a similar concept of _active
submaps_.

####  II-B2 Impact of loop closure in SLAM on frontier detection

Loop closure is an event when the SLAM algorithm recognizes that the robot has
revisited the same place, and then makes a correction using this information
which reduces the error caused by drift in localization along the whole loop.
The frontier detector has to be able to efficiently cope with the map changes
induced by loop closure corrections. These map changes may not be confined to
the active area - in fact, loop closure may result in widespread changes all
over the map. While an efficient frontier detection algorithm should avoid
reassembling and iterating throughout the entire global map in every
iteration, constraining the algorithm to only the active area makes it
difficult to be robust to loop closures. WFD-INC addresses loop closure events
by evicting the detected frontier and performing frontier detection from
scratch using the new loop-corrected map.

To efficiently address loop closures, the frontier detection algorithm needs
to get intimate to a certain degree with the implementation of the SLAM
algorithm. For example, Keidar and Kaminka additionally proposed an
implementation of WFD-INC for GMapping (a particle filter-based SLAM [11])
called _incremental parallel_ WFD (WFD-IP). WFD-IP performs in parallel
separate WFD-INC frontier detection for each particle (each particle having
its own map), and outputs the appropriate frontier of the current best
particle. Like WFD-INC, the proposed method uses the internals of the SLAM
algorithm in order to perform frontier detection faster while also being
robust to loop closure.

Quin and Alempijević [9] introduce two frontier detection methods: _naive
active area_ (NaiveAA), which is the naive approach confined to the active
area, and a version of WFD called _Expanding WFD_ (EWFD) which steers the WFD
breadth-first search into newly discovered free areas. EWFD assumes that the
entropy for each cell can only decrease over time. This is not true in the
general case for the complete global map when considering effects of loop
closure – observed areas can get moved around in the global map during loop
closure and leave unexplored space in their wake. However, the entropy
decrease assumption _is_ almost surely true for single submaps in submap-based
SLAM, and we exploit this fact in the proposed approach.

####  II-B3 Other approaches

Senarathne and Wang [12] use an oriented bounding-box based inexact approach.

Umari [13] uses rapidly-exploring random trees (RRT) to perform sparse
frontier detection by building a tree inside the free space in the SLAM-built
map. When the algorithm crosses the frontier while trying to expand the random
tree, a single frontier point is detected. However, using the implementation
of the algorithm provided in [13] does require reassembling the global map in
each iteration. Also, this algorithm is not robust to loop closure, since the
built RRT tree does not follow the results of pose graph optimization.

Experiments were performed with a modified version of the RRT frontier
detection algorithm in which the tree nodes were bent according to the
displacement of the closest submap in the optimized pose graph in an attempt
to make the algorithm robust to loop closure. However, narrow corridors in the
map have proven problematic as the map size increases, because the probability
of extending the tree into a narrow corridor dramatically decreases as the map
canvas size increases. An inspiration for the proposed method was attempting
to perform dense local frontier detection (opposed to sparse, as with RRT),
while trying to follow the global ”dance” of the pose graph as it is
optimized.

##  III Prerequisites

###  III-A Simultaneous Localization and Mapping

The term SLAM was coined by Leonard and Durrant-Whyte in 1991 [14]. As shown
in the block diagram of the exploration pipeline in Figure 1, a SLAM algorithm
uses sensor data to build a map and perform localization, which is further
used in frontier detection, exploration task planning and execution. There is
a wealthy trove of SLAM methods developed to this day, which can be roughly
grouped into methods based on filtering and methods based on graph
optimization.

We will focus on graph SLAM, which represents poses and detected features as
nodes in a graph, while the correspondences which impose constraints on the
poses of the respective nodes are represented as edges. Various optimization
methods may be used to minimize the residual error of all constraints, e.g.
the Ceres solver [15].

Submaps are small local maps which are merged into a global map. One of
earlier approaches to SLAM using submaps is [16], with further examples being
[17] and a graph SLAM approach using histograms of submap features [18].

$\cup$ $=$

Figure 2: Depiction of merging two adjacent submaps and their local frontiers
into a global composite map. Colour legend: unobserved grid cells are grey,
free cells are white, occupied cells are black, while frontier points are red.
Each submap has a _local frontier_ which is based solely on the occupancy grid
of that submap. The points in the local frontier set are candidates for
becoming part of the _global frontier_. The submaps are then projected into
the global map coordinate system according to the current optimized solution
of graph SLAM. Any local frontier point which after projection ends up in an
observed (free or occupied) area of any other submap (i.e. fails the stabbing
query test against that submap) is discarded from the global frontier set.

###  III-B Cartographer

The proposed frontier detection method was designed for use with Cartographer,
an open-source multi-robot multi-trajectory 2D and 3D graph SLAM based on
occupancy grid submaps, developed by Google (Hess, Kohler, Rapp in 2016 [1]).
Cartographer’s approach of optimizing the poses of all scans and submaps
follows Sparse Pose Adjustment [19] and uses the Ceres solver [15] for
optimizing the pose graph using the Levenberg–Marquardt algorithm (LMA).

Cartographer submaps are spatially and temporally compact occupancy grid maps
made from a short, continuous series of rangefinder sensor measurements (laser
scans) taken during traversal of a short section of the robot trajectory. It
is desired that the size of the submaps be small enough such that the
localization drift is not perceptible when looking at one submap at a time.
Building the submaps and the trajectory (without loop closures) is handled by
Cartographer’s _local trajectory builder_ component, which maintains a pair of
active submaps that the laser scans are inserted into according to a local
pose obtained by performing scan matching against the older (larger) submap
from the active pair.

When a predetermined number of scans is inserted into a submap, it is marked
as finished, and a new submap is created to take its place in the active
submap pair. Importantly, once a submap is finished, its occupancy grid is
immutable from that point onward.

Cell occupancy probabilities are clamped to the interval $[0.1,0.9]$ and are
stored linearly mapped onto the space of unsigned 16-bit integers. Scan
insertion into submaps is performed as Bayesian updates of the cell occupancy
probabilities (see (3) in [1]). The cells corresponding to laser hit points
are updated with ”occupied” observations, while the intermediate points
(obtained by casting rays from the laser rangefinder origin to hit points) are
updated with ”free” observations. It is also important to note that on a level
of a single submap, the cell entropy (i.e. the uncertainty of the occupancy
probability) can be assumed to be monotonically decreasing. If there are
moving objects in the environment (e.g. a door which was previously closed is
now open), it is theoretically possible that an observed cell may afterwards
land in the narrow occupancy probability interval near 0.5 where it would be
again considered unobserved. However, the probability of this is negligible,
and it is considered that _the cells of an active submap cannot become
unobserved once they are observed_.

When loop closures are detected by the _constraint builder_ component of
Cartographer, pose constraints between the corresponding trajectory nodes and
submaps are added as edges into the pose graph. Afterwards, optimization is
periodically invoked in order to find a new solution – a set of global submap
and trajectory node poses – which minimizes the residual costs of the
constraints. As discussed, for frontier detection, this implies that when pose
graph optimization is performed, the submaps can and do get displaced and
rotated (i.e. undergo rigid transformations), although their occupancy grids
are immutable after they are marked as finished. The proposed frontier
detection approach attempts to take advantage of these properties of
Cartographer.

##  IV Frontier detection

###  IV-A Definitions

Rigid transformation $\mathbf{T}^{b}_{a}\in\mathbf{SE}(3)$ is the pose of the
coordinate system $b$ relative to the coordinate system $a$. The
$\mathbf{SE}(3)$ group operation of pose composition is written as
multiplication, e.g. $\mathbf{T}^{b}_{a}$ $\mathbf{T}^{c}_{b}$. The transform
inverse $(\mathbf{T}^{b}_{a})^{-1}$ is equal to $\mathbf{T}^{a}_{b}$. The
projection of a point with coordinates expressed in $b$,
$\mathbf{p}^{b}=\begin{bmatrix}x\;y\;z\end{bmatrix}^{T}\in\mathbb{R}^{3}$, to
the corresponding point $\mathbf{p}^{a}$ in coordinate system $a$ is denoted
as $\mathbf{p}^{a}=\mathbf{T}^{b}_{a}\;\mathbf{p}^{b}$.

The global map coordinate system is denoted with $g$. The solution of pose
graph optimization are poses of graph members expressed with respect to $g$.

Submap is an occupancy grid of resolution (i.e. cell size) $r$, which is
typically 0.05 cm. The occupancy probabilities of grid cells are initially
unobserved i.e. unknown (exactly 0.5). Submaps are constructed by insertion of
$n_{scans}$ sequential laser scans, where parameters $r$ and $n_{scans}$ are
predetermined fixed parameters. A submap is marked as finished when
$n_{scans}$ scans have been inserted into the submap.

The set of active submaps contains the submaps which are not yet finished.

The local submap coordinate system has the origin fixed, for example, to the
robot pose in the first scan inserted into the submap. The cells of a submap
occupancy grid are indexed in a 2D matrix using a 2-integer tuple:
$\mathbf{S}^{si}_{k,l}$ is the occupancy probability value of the cell $(k,l)$
in the submap $si$. As the submap grows in size, the 2-integer tuples
corresponding to the same cell in the submap may change (which is an
implementation-specific detail), but the position of the cell in the local
submap coordinate system must remain the same.

Global submap pose $\mathbf{T}_{g}^{si}$ is the global pose of the origin of
the local coordinate system of a submap $si$. Since submaps are members of the
pose graph, submap poses are part of the optimized pose graph solution.

Occupancy classification – in the frontier detection algorithm, the cell
occupancy probability values are not used directly. The probability values are
first classified according to the following thresholding rule:

$\text{class}(p=\mathbf{S}^{si}_{k,l})\colonequals\begin{cases}\text{free}&p<0.5\\\
\text{occupied}&p>0.5\\\ \text{unobserved}&p=0.5\end{cases}$ (1)

Observed cells are occupancy grid cells that are not unobserved.

Local frontier point is the center of an unobserved occupancy grid cell which
is adjacent to a free cell in the same submap.

Local frontier of a submap is the set of its local frontier points. See the
red points in the first two pictures in Figure 2 for an example.

Stabbing query refers to looking up the corresponding cell in a given submap
for a given global point and the global submap pose. More precisely, for a
submap $si$ and a global point $\mathbf{p}^{g}\in\mathbb{R}^{3}$ expressed in
$g$, to find the occupancy grid cell $(k,l)$ in $si$ whose center coordinates
in the local coordinate system of the submap $si$ are closest to
$(\mathbf{T}_{g}^{si})^{-1}\mathbf{p}^{g}$. Further, performing a stabbing
query test means checking if the corresponding cell $\mathbf{S}^{si}_{k,l}$ is
an unobserved cell, in which case the test passes.

Global frontier point is the center of an unobserved global occupancy grid map
cell adjacent to a free global map cell. A valid global frontier point must
pass the stabbing query test against all other submaps.

Global frontier is the set of all valid global frontier points at a given
time. See the third picture in Figure 2.

Perimeter of the global or local frontier is the number of frontier points in
the respective set.

It may be noted that the frontier points could alternatively have been defined
as centers of _free_ cells adjacent to _unobserved_ cells. We have chosen to
define frontier points as centers of _unobserved_ cells as above in order to
simplify the stabbing query test.

###  IV-B The frontier detection algorithm

There are two kinds of events which occur during SLAM execution which are of
interest for frontier detection: a submap update event, where a scan is
inserted into the active submaps; and a pose graph optimization event which
also occurs periodically, but less often. Algorithm 1 describes handling of
submap update events, while Algorithm 2 describes handling of pose graph
optimization events.

Input: active_submaps, global_submap_poses

Persistent variables:

local_frontiers, global_frontiers,

global_submap_bounding_boxes

Local variable initializations:

current_bounding_boxes $\Leftarrow$ empty

submaps_with_frontier_updates $\Leftarrow$ active_submaps

1 foreach submap $si\in$ active_submaps do

2 local_frontiers[$si$].Clear();

3 global_frontiers[$si$].Clear();

7654 current_bounding_boxes[$si$] $\Leftarrow$
CalculateGlobalBoundingBox($si$,
global_submap_poses[$si$]);intersecting_submaps $\Leftarrow$
global_submap_bounding_boxes.Intersect(
current_bounding_boxes[$si$]);Threshold and classify cells in $si$ according
to (1); foreach cell $(k,l)\in$ submap $si$ do

8 if cell $(k,l)$ is unobserved $\wedge$ cell $(k,l)$ is adjacent to a free
cell in $si$ then

11109 local_frontiers[$si$].Add($(k,l)$); projected_to_global $\Leftarrow$
ProjectToGlobal( global_submap_poses[$si$], cell $(k,l)$);if
StabbingQueryTest( projected_to_global, intersecting_submaps $\cup$
active_submaps $\setminus$ $si$) then

12 global_frontiers[$si$].Add( projected_to_global);

else

13 local_frontiers[$si$] .AddFailingSubmapHintForCell($(k,l)$);

14foreach submap $sj\in$ intersecting_submaps do

15 foreach global_frontier_point $\in$ global_frontiers[$sj$] do

16 if not StabbingQueryTest( global_frontier_point, $si$) then

1817 global_frontiers[$sj$].Remove(
global_frontier_point);submaps_with_frontier_updates.Add($sj$);

19foreach submap $si\in$ active_submaps do

20 if submap $si$ has just been finished then

21 global_submap_bounding_boxes.Insert( current_bounding_boxes[$si$]);

22foreach submap $si\in$ submaps_with_frontier_updates do

23 PublishFrontierUpdates($si$, global_frontiers[$si$]);

Algorithm 1 Handling of updates to active submaps

Input: updated global_submap_poses, finished_submaps, active_submaps

Persistent variables:

local_frontiers, global_frontiers,

global_submap_bounding_boxes

1 global_submap_bounding_boxes.Clear();

2 foreach submap $si\in$ finished_submaps do

3 global_submap_bounding_boxes.Insert( CalculateGlobalBoundingBox($si$,
global_submap_poses[$si$]));

54global_frontiers.Clear(); foreach submap $si\in$ finished_submaps $\cup$
active_submaps do

76 intersecting_submaps $\Leftarrow$ global_submap_bounding_boxes.Intersect(
global_submap_bounding_boxes[$si$]) $\cup$ active_submaps $\setminus$
$si$;foreach cell $(k,l)\in$ local_frontiers[$si$] do

98 projected_to_global $\Leftarrow$ ProjectToGlobal(
global_submap_poses[$si$], cell $(k,l)$);// First try testing against the

10 // failing submap hint if present.

11 if StabbingQueryTest( projected_to_global, intersecting_submaps $\cup$
active_submaps $\setminus$ $si$) then

12 global_frontiers[$si$].Add( projected_to_global);

else

13 local_frontiers[$si$] .AddFailingSubmapHintForCell($(k,l)$);

14PublishFrontierUpdates($si$, global_frontiers[$si$]);

Algorithm 2 Handling of pose graph optimization events

####  IV-B1 Handling of submap updates

For each laser scan processed in SLAM, both submaps in the active pair are
updated, making submap updates the most frequently occurring type of event. A
submap update can only affect the frontier in the area covered by the active
submaps, therefore the frontier detection algorithm can be constrained to this
area in order to maximize efficiency.

The first step in handling a submap update of an active submap is performing
dense local frontier detection on the new version of the submap occupancy grid
(Algorithm 1, algorithms 1–1). In other words, on the local submap level, we
have opted to perform a naive edge detection approach.

The reason for using a naive approach for local frontier detection is twofold.
First, since the submaps are bounded in size (controlled by the fixed
parameter $n_{scans}$), and the number of active submaps is constant, the time
complexity of local frontier detection is not affected by the size of the
global map or the size of the dataset. Second, probability thresholding,
classification (Algorithm 1) and edge detection (Algorithm 1) can be
vectorized, allowing for high performance on modern CPUs. Our implementation
relies on Eigen [20] for vectorization, where we used matrix block algebra and
Hadamard products to implement thresholding, classification and Boolean logic
for edge detection.

Computing and storing the set of local frontier points for an active submap
produces a set of _candidates_ for the global frontier. Every local frontier
point is projected into the global map frame $g$ according to the current
global pose of the corresponding submap (Algorithm 1) and the stabbing query
test is performed against the intersecting submaps (Algorithm 1). In case the
test passes against all submaps, the projected frontier point is indeed a
global frontier point and is added to the global frontier set (Algorithm 1).
If the test fails, the submap against which the test failed is recorded as a
hint (Algorithm 1) so that future re-testing can be performed faster –
performing a test against the failing submap hint in most cases immediately
produces a negative result.

In the next step of handling submap updates, we exploit several properties of
graph SLAM based on occupancy grid submaps:

  1. 1.

The occupancy grids of finished submaps are immutable. Therefore, it is not
necessary to re-detect _local_ frontiers for already finished submaps.

  2. 2.

The algorithm for handling submap updates may assume that no graph
optimization has occurred since the last submap update event, so all existing
_global_ frontiers of finished submaps are valid (except for the situation
described below).

  3. 3.

The cell occupancy probabilities of active submaps have decreasing entropy,
which means that only previously unobserved cells can become observed, and not
vice-versa. This implies that updates to active submaps can invalidate the
global frontiers of intersecting submaps.

In algorithms 1–1, it is tested if the new versions of active submaps cover
existing valid global frontiers of the intersecting finished submaps. This is
done by performing stabbing query tests of the global frontier points against
the active submaps. If the stabbing query test fails, the newly covered global
frontier points are removed from the set of global frontier points (Algorithm
1), thus preserving the invariant that all global frontier points at a time
are valid. The global frontiers of finished submaps whose global frontier
points got removed are also marked as updated (Algorithm 1) for incremental
publishing of frontier updates (Algorithm 1).

Bounding boxes of finished submaps are stored inside a tree data structure
which enables fast queries of submaps which intersect with a given bounding
box (e.g. looking up finished submaps intersecting with an active submap,
Algorithm 1). When a submap is marked as finished, its bounding box is
inserted into the tree structure (Algorithm 1). Our implementation uses the
Boost implementation of R-trees [21] for storing global axis-aligned bounding
boxes of finished submaps.

It can also be noted that not all submap update events have to be handled in
order to guarantee a correct result – any non-final submap update can be
skipped. A robotic exploration system which does not require real-time
frontier updates after every scan, but rather occasionally, can invoke the
algorithm for handling submap updates only when a submap is finished. This can
significantly reduce the computational effort of keeping the frontier up to
date, up to a factor of $n_{scans}$.

####  IV-B2 Handling of graph optimization events

When graph SLAM performs optimization, a new solution is produced for poses of
all graph members. For frontier detection, this means that the submap poses
have changed. This invalidates the global bounding boxes of submaps and the
entire global frontier, all of which has to be recomputed in Algorithm 2.
However, advantage is taken of the fact that the local frontiers have already
been computed for all submaps, so all that needs to be done is to re-project
the local frontier points to the global coordinate system $g$ and re-test
them.

The global bounding boxes are recomputed in algorithms 2–2, while the rest of
Algorithm 2 recomputes the global frontier similarly to Algorithm 1: each
local frontier point is re-projected according to the corresponding new global
submap pose (Algorithm 2) and the stabbing query test against the intersecting
submaps is performed (Algorithm 2). If the stabbing query test is passed, the
re-projected and re-tested frontier point is inserted into the new global
frontier set (Algorithm 2).

Note that during re-testing, it is advisable to first try testing against the
failing submap hint, if it exists (comment in algorithms 2–2). This speeds up
rejection of points which fail the test by first testing against the same
submap which caused the same local frontier point to fail the test earlier.
Even though recomputing the entire global frontier in Algorithm 2 is certainly
not a computationally lightweight operation, it is still more efficient than
any other non-submap aware approach which would require iterating through the
entire reassembled global map, and thus have a time complexity proportional to
the _area_ of the global map. Recomputing the global frontier in Algorithm 2
has the time complexity proportional to the _perimeter_ of local frontiers.

To summarize, Algorithm 1 assumed that all global frontier points before a
submap update event were valid and up-to-date. Graph optimization violates
this assumption by displacing the submaps according to submap poses of the new
pose graph solution. Algorithm 2 restores this invariant by recomputing the
global frontier.

##  V Algorithm analysis

###  V-A Soundness and completeness

Let us first note that the process of merging submaps into a global map
according to a pose graph solution cannot result in an unobserved cell in the
global map if any of the corresponding submap cells are observed. In other
words, if a global map cell is unobserved, the corresponding cells in all
submaps are also unobserved. Also, let $LF$ and $GF$ denote the sets of local
and valid global frontier points of all submaps.

For discussing completeness, we will consider a valid global frontier point in
$GF$, i.e. the center of an _unobserved_ global map cell adjacent to a free
global map cell. Due to the map merging process, all submap cells
corresponding to the global frontier cell have to be unobserved as well. Next,
the adjacent free global map cell is also free in at least one submap, whose
merging caused the free global map cell to be marked as such. In that submap,
the unobserved cell next to the free cell is a local frontier and is in $LF$.
Therefore, each valid global frontier point corresponds to a local frontier
point in at least one submap (i.e. $GF\subseteq LF$ projected to $g$), and an
algorithm which computes the set of global frontier points $GF$ by taking the
set of all local frontier points $LF$ as input is thus complete, providing it
does not incorrectly discard any valid global frontier points in the process.
The rule for discarding local frontier points when they fail the stabbing
query test can only result in _observed_ cells being correctly discarded from
the global frontier, and therefore the property of completeness is preserved.
Also, the naive edge detection algorithm used for computing the local
frontiers is trivially valid.

For soundness, we will consider a global frontier point returned by the
proposed algorithm, and suppose that it is not valid. This could be either
because the returned global frontier point is not an unobserved cell in the
global map, or because the returned global frontier point is not adjacent to a
free cell in the global map. The first case is not possible because the
frontier point would have failed the stabbing query test against the submap
that contains an observed cell which resulted in marking the corresponding
global cell as observed. The second case is theoretically possible – for
example, if there were a plurality of submaps with corresponding occupied
cells rather than free, so the merging process results in adjacent global map
cells being marked as occupied instead of free. However, this case is of no
practical significance, because the chance that this will happen without the
unobserved frontier cell also getting covered up by observed cells (which in
turn will make it fail the stabbing query test) is negligible. To exclude this
case, the stabbing query test could be modified to also look at the adjacent
cells in submaps, instead of just checking if the single cell corresponding to
the frontier is unobserved. This would not increase the theoretical time
complexity, but would make the implementation unnecessarily more elaborate and
slow.

###  V-B Computational complexity

####  V-B1 Handling of submap updates

In Algorithm 1, Algorithm 1, the complexity of querying the R-tree for submaps
intersecting with the updated submap $si$ is $O(\log|S|+|S_{\cap si}|)$, where
$S$ is the set of all submaps, and $S_{\cap si}$ is the set of submaps
intersecting with the submap $si$. This also includes the complexity of
inserting a finished submap bounding box into the R-tree.

In algorithms 1–1, naive local frontier detection runs in $O(A(si))$, where
$A(si)$ is the area of submap $si$, i.e. the number of cells in the submap.

The number of local frontier points in $si$, i.e. the perimeter of its local
frontier $LF_{si}$ will be denoted as $P(LF_{si})$, while the global frontier
of the submap $si$ and its perimeter will be denoted as $GF_{si}$ and
$P(GF_{si})$, respectively.

For each detected local frontier point in the updated submap, the complexity
of performing the stabbing query test against the intersecting submaps
(Algorithm 1) is $O(|S_{\cap si}|)$, yielding the complexity of this step
$O(P(LF_{si})\cdot|S_{\cap si}|)$.

Invalidating global frontiers of the intersecting submaps (algorithms 1–1)
runs linearly with respect to their perimeter, i.e. in time
$O(P(\bigcup_{sj\in S_{\cap si}}GF_{sj}))$.

The total time complexity of handling an update of submap $si$ thus equals
(simplified assuming $P(LF_{si})\geq 1$):

$O(\log|S|+A(si)+P(LF_{si})\cdot|S_{\cap si}|+P(\bigcup_{sj\in S_{\cap
si}}GF_{sj}))$ (2)

####  V-B2 Handling of pose graph optimization events

The first step in Algorithm 2 is to rebuilt the R-tree (algorithms 2–2), which
runs in $O(|S|\log|S|)$. This complexity also covers looking up the
intersecting submaps for each submap (Algorithm 2).

Next, every local frontier point is projected to the global coordinate frame
$g$ and the stabbing query test is performed against the intersecting submaps
(algorithms 2–2). A pessimistic bound would entail testing every local
frontier point against all other submaps, i.e. a time complexity of
$O(|S|\cdot P(LF))$. The pessimism of this bound can be reduced by assuming
that the points which fail the stabbing query test will do so on the first
test, performed against the failing submap hint. If their perimeter, equal to
$P(LF)-P(GF)$, is denoted as $P(FF)$, this assumption yields the time
complexity of $O(|S|\cdot P(GF)+P(FF))$.

The total time complexity of handling a pose graph optimization event thus
depends on the number of submaps and the local and global frontier perimeters:

$O(|S|\cdot(\log|S|+P(GF))+P(FF))$ (3)

We have managed to avoid having the two-dimensional map area in the time
complexity of the global operation of handling pose graph optimization by
taking advantage of submaps and their immutability.

##  VI Experimental results

Our implementation of frontier detection, available online on
Github111https://github.com/larics/cartographer_frontier_detection, has been
tested on an Intel i7 6800K CPU running Ubuntu 18.04. A demo video of
processing Google’s Deutsches museum dataset [1] is
available222https://goo.gl/62zEUy. We are using the Google Cartographer
_offline node_ , which processes a ROS bag dataset as fast as the CPU can
handle (around 4-5x realtime), making it ideal for benchmarking the impact of
performing frontier detection on SLAM performance.

In order to minimize the impact on SLAM performance, the frontier detection
algorithm is running in a separate thread. The algorithm tries to process all
submap updates, while it can adaptively skip non-final submap updates in case
the processing speed of frontier detection falls behind SLAM. For this reason,
the wall clock frequency of incremental frontier updates has been measured.
The results are given in Table I.

TABLE I: Experimental setup and results Dataset:
cartographer_paper_deutsches_museum.bag, duration: 1912s
---
Testing setup details
Intel i7 6800K @ 3600 MHz, Ubuntu 18.04, ROS Melodic
POSE_GRAPH.constraint_builder.sampling_ratio = 0.1
MAP_BUILDER.num_background_threads = 10
Cartographer offline node, exit before final optimization
No RViz visualization
Wall clock SLAM processing time (not including final optimization)
with frontier detection: 434s (4.4x realtime on average)
without frontier detection: 360s (5.3x realtime on average)
Frequency of frontier updates
Average: 78 Hz (13 ms) Std. deviation: 22 ms
SLAM events
Total submap update events: 37816
Skipped submap update events: 3900/37816
Pose graph optimization events: 355

###  VI-A Additional notes on implementation of the frontier detection
algorithm

An optimization that has been included in our implementation is performing
additional stabbing query tests against a fixed number of _temporally close_
i.e. sequential submaps using _unoptimized_ submap poses into the local
frontier edge detection condition in Algorithm 1, Algorithm 1 (for example,
against 4 previous submaps). This would have the result of permanently ”baking
in” a negative test result against these submaps, since these points would
permanently be erased from the local frontiers. A benefit of discarding points
early from local frontiers is speeding up recomputation of the global frontier
in Algorithm 2, since there will now be fewer candidates in the local frontier
which have to be re-projected and re-tested. Also, it is expected that the
localization drift between sequential submaps is small, and that pose graph
optimization will not produce a significant relative displacement between
sequential submaps. Using the unoptimized poses may actually be preferential
for processing sequential submaps, because it could prevent detecting a false
frontier resulting from slight misalignment of sequential submaps introduced
by pose graph optimization when closing loops.

We have employed a few cosmetic improvements which result in (subjectively)
aesthetically better frontiers. The first improvement is treating cells with a
very uncertain ”free” probability (i.e.
$\mathbf{S}^{si}_{k,l}\in[0.5-\varepsilon,0.5]$, where
$\varepsilon\colonequals 0.04$ is an arbitrarily chosen small value) as
”unobserved” cells. This prevents detecting a false frontier around single
false long-distance laser readings, which cause insertion of a false ray of
”free” cells into the submap. This also has the beneficial effect of driving
the robot exploration system to get a ”better look” at areas with uncertain
free cells, since they are considered unexplored. The second change we have
made is simple smoothing of local frontiers by adjusting the definition of a
local frontier to be _the center of an unobserved cell with $\geq$ 2 free
adjacent cells and $\geq$ 2 unobserved adjacent cells_, where _adjacent_ cells
are cells in the Moore 8-neighbourhood.

##  VII Conclusion and future work

We have described, implemented and tested an efficient frontier detection
algorithm that is specialized for 2D graph SLAM based on occupancy grid
submaps. Our algorithm is efficiently constrained to the area of active
submaps, yet robust to loop closure by recomputing the global frontier after
pose graph optimization. Importantly, the time complexity of recomputing the
global frontier is a function of the frontier perimeter, and not of map area.

_Future work:_ Some cited state of the art (e.g. [10]) performs grouping of
continuous frontier points into segments, which is useful for selecting
navigation objectives of exploration tasks. Another kind of post-processing of
the detected frontier which might be of interest is reachability analysis:
detecting frontier points unreachable by the robot which do not make sense as
navigation objectives, such as frontier points behind glass, closed doors or
behind walls (e.g. from false laser readings, or slight misadjustment of walls
in different submaps). Nonetheless, a performant algorithm for frontier
detection is the basis for any such further improvements.

## References

  * [1] W. Hess, D. Kohler, H. Rapp, and D. Andor, “Real-time loop closure in 2d lidar slam,” in _Robotics and Automation (ICRA), 2016 IEEE International Conference on_. IEEE, 2016, pp. 1271–1278.
  * [2] B. Yamauchi, “A frontier-based approach for autonomous exploration,” in _Computational Intelligence in Robotics and Automation, 1997. CIRA’97., Proceedings., 1997 IEEE International Symposium on_. IEEE, 1997, pp. 146–151.
  * [3] W. Burgard, M. Moors, D. Fox, R. Simmons, and S. Thrun, “Collaborative multi-robot exploration,” in _Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065)_. IEEE. [Online]. Available: https://doi.org/10.1109/robot.2000.844100
  * [4] L. Freda and G. Oriolo, “Frontier-based probabilistic strategies for sensor-based exploration,” in _Proceedings of the 2005 IEEE International Conference on Robotics and Automation_. IEEE. [Online]. Available: https://doi.org/10.1109/robot.2005.1570713
  * [5] J. Wettach and K. Berns, “Dynamic frontier based exploration with a mobile indoor robot,” in _ISR 2010 (41st International Symposium on Robotics) and ROBOTIK 2010 (6th German Conference on Robotics)_ , June 2010, pp. 1–8.
  * [6] W. Burgard, M. Moors, C. Stachniss, and F. Schneider, “Coordinated multi-robot exploration,” _IEEE Transactions on Robotics_ , vol. 21, no. 3, pp. 376–386, jun 2005. [Online]. Available: https://doi.org/10.1109/tro.2004.839232
  * [7] J. Faigl and M. Kulich, “On determination of goal candidates in frontier-based multi-robot exploration,” in _2013 European Conference on Mobile Robots_. IEEE, sep 2013. [Online]. Available: https://doi.org/10.1109/ecmr.2013.6698844
  * [8] R. Shade and P. Newman, “Choosing where to go: Complete 3d exploration with stereo,” in _2011 IEEE International Conference on Robotics and Automation_. IEEE, may 2011. [Online]. Available: https://doi.org/10.1109/icra.2011.5980121
  * [9] P. Quin, A. Alempijevic, G. Paul, and D. Liu, “Expanding wavefront frontier detection: An approach for efficiently detecting frontier cells,” in _Australasian Conference on Robotics and Automation_. Australasian Robotics and Automation Association, 2014\.
  * [10] M. Keidar and G. A. Kaminka, “Efficient frontier detection for robot exploration,” _The International Journal of Robotics Research_ , vol. 33, no. 2, pp. 215–236, oct 2013. [Online]. Available: https://doi.org/10.1177/0278364913494911
  * [11] G. Grisetti, C. Stachniss, and W. Burgard, “Improved techniques for grid mapping with rao-blackwellized particle filters,” _IEEE transactions on Robotics_ , vol. 23, no. 1, pp. 34–46, 2007.
  * [12] P. Senarathne, D. Wang, Z. Wang, and Q. Chen, “Efficient frontier detection and management for robot exploration,” in _Cyber Technology in Automation, Control and Intelligent Systems (CYBER), 2013 IEEE 3rd Annual International Conference on_. IEEE, 2013, pp. 114–119.
  * [13] H. Umari and S. Mukhopadhyay, “Autonomous robotic exploration based on multiple rapidly-exploring randomized trees,” in _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, sep 2017. [Online]. Available: https://doi.org/10.1109/iros.2017.8202319
  * [14] J. J. Leonard and H. F. Durrant-Whyte, “Simultaneous map building and localization for an autonomous mobile robot,” in _Intelligent Robots and Systems’ 91.’Intelligence for Mechanical Systems, Proceedings IROS’91. IEEE/RSJ International Workshop on_. Ieee, 1991, pp. 1442–1447.
  * [15] S. Agarwal, K. Mierle, and Others, “Ceres solver,” http://ceres-solver.org.
  * [16] S. Williams, G. Dissanayake, and H. Durrant-Whyte, “An efficient approach to the simultaneous localisation and mapping problem,” in _Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No.02CH37292)_. IEEE. [Online]. Available: https://doi.org/10.1109/robot.2002.1013394
  * [17] J. Strom and E. Olson, “Occupancy grid rasterization in large environments for teams of robots,” in _Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference on_. IEEE, 2011, pp. 4271–4276.
  * [18] M. Bosse and R. Zlot, “Map matching and data association for large-scale two-dimensional laser scan-based slam,” _The International Journal of Robotics Research_ , vol. 27, no. 6, pp. 667–691, 2008.
  * [19] K. Konolige, G. Grisetti, R. Kümmerle, W. Burgard, B. Limketkai, and R. Vincent, “Efficient sparse pose adjustment for 2d mapping,” in _Intelligent Robots and Systems (IROS), 2010 IEEE/RSJ International Conference on_. IEEE, 2010, pp. 22–29.
  * [20] G. Guennebaud, B. Jacob _et al._ , “Eigen v3,” http://eigen.tuxfamily.org, 2010.
  * [21] “Boost R-tree spatial index,” https://www.boost.org/doc/libs/1_68_0/libs/geometry/doc/html/geometry/spatial_indexes/introduction.html.


# Subword-Level Language Identification for Intra-Word Code-Switching

Manuel Mager[1], Özlem Çetinoğlu[1] and Katharina Kann[2]
[1]Institute for Natural Language Processing,
University of Stuttgart, Germany
[2]Center for Data Science, New York University, USA
{manuel.mager<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Language identification for code-switching (CS), the phenomenon of alternating
between two or more languages in conversations, has traditionally been
approached under the assumption of a single language per token. However, if at
least one language is morphologically rich, a large number of words can be
composed of morphemes from more than one language (intra-word CS). In this
paper, we extend the language identification task to the subword level, such
that it includes splitting mixed words while tagging each part with a language
ID. We further propose a model for this task, which is based on a segmental
recurrent neural network. In experiments on a new Spanish–Wixarika dataset and
on an adapted German–Turkish dataset, our proposed model performs slightly
better than or roughly on par with our best baseline, respectively.
Considering only mixed words, however, it strongly outperforms all baselines.

author=Ozlem,color=blue!40,size=,fancyline,caption=,]Manuel, there are a few
comments within the text. Could you also make sure you cover the comments I
gave on the printed version and the ones from our last meeting?
author=Katharina,color=green!40,size=,fancyline,caption=,]

  * •

LID means language identification by our definition. Manuel, you now also use
it as language ID, which is confusing. Undo these abbreviations, please!

author=Manuel,color=orange!40,size=,fancyline,caption=,]done

##  1 Introduction

In settings where multilingual speakers share more than one language, mixing
two or more languages within a single piece of text, for example a tweet, is
getting increasingly common Grosjean (2010). This constitutes a challenge for
natural language processing (NLP) systems, since they are commonly designed to
handle one language at a time.

Code-switching (CS) can be found in multiple non-exclusive variants. For
instance, sentences in different languages can be mixed within one text, or
words from different languages can be combined into sentences. CS can also
occur on the subword level, when speakers combine morphemes from different
languages (_intra-word CS_). This last phenomenon can mostly be found if at
least one of the languages is morphologically rich. An example for intra-word
CS between the Romance language Spanish and the Yuto-Aztecan language
Wixarika111Wixarika, also known as Huichol, is a polysynthetic Mexican
indigenous language. is shown in Figure 1.
author=Katharina,color=green!40,size=,fancyline,caption=,]Why is this saying
tire instead of tired?
author=Manuel,color=orange!40,size=,fancyline,caption=,]Because tired is the
inflected form, and this only happens after adding the x+
morpheme.author=Katharina,color=green!40,size=,fancyline,caption=,]I think we
could argue if this is a derived or inflected form. I would go with derived,
since tired is a lemma for sure. Would you mind changing it?

CS language identification (LID) , i.e., predicting the language of each token
in a text, has attracted a lot of attention in recent years (cf. Solorio et
al. (2014); Molina et al. (2016)). However, intra-word mixing is mostly not
handled explicitly: words with morphemes from more than one language are
simply tagged with a mixed label.

| (a) | ne’iwa | pecansadox
---|---|---|---
|  | WIX | MIXED
|  | my.brother | you-are.tired.PPFV

| (b) | ne’iwa | pe | cansado | x
---|---|---|---|---|---
|  | WIX | WIX | ES | WIX
|  | my.brother | you-are | tired | PPFV
|  | ‘My brother, you are tired.’ |

Figure 1: Intra-word CS between Spanish and Wixarika, (a) standard LID for CS,
(b) our task. PPFV stands for past perfective.

While this works reasonably well for previously studied language pairs,
overlooking intra-word CS leads to a major loss of information for highly
polsynthetic author=Katharina,color=green!40,size=,fancyline,caption=,]Check
this; but I think we want to say polysynthetic, not agglutinative.
author=Manuel,color=orange!40,size=,fancyline,caption=,]I added polysynthetic
because Turkish is agglutinative, so non of both typologies covers our
languagesauthor=Katharina,color=green!40,size=,fancyline,caption=,]This seems
wrong! Let’s
discuss.author=Manuel,color=orange!40,size=,fancyline,caption=,]ok. languages.
A mixed word is unknown for NLP systems, yet a single word contains much more
information, cf. Figure 1 (b). Furthermore, we find intra-word CS to be much
more frequent for Spanish–Wixarika than for previously studied language pairs,
such that it is crucial to handle it.

Motivated by these considerations, we extend the LID task to the subword level
(from (a) to (b) in Figure 1). We introduce a new CS dataset for
Spanish–Wixarika (ES–WIX) and modify an existing German–Turkish (DE–TR) CS
corpus Çetinoğlu (2016) for our purposes. We then introduce a segmental
recurrent neural network (SegRNN) model for the task, which we compare against
several strong baselines. Our experiments show clear advantages of SegRNNs
over all baselines for intra-word CS.

##  2 Related Work

The task of LID for CS has been frequently studied in the last years Al-
Badrashiny and Diab (2016); Rijhwani et al. (2017); Zhang et al. (2018),
including two shared tasks on the topic Solorio et al. (2014); Molina et al.
(2016). The best systems Samih et al. (2016); Shirvani et al. (2016) achieved
over $90\%$ accuracy for all language pairs. However, intra-word CS was not
handled explicitly, and often systems even failed to correctly assign the
mixed label. For Nepali–English, Barman et al. (2014) correctly identified
some of the mixed words with a combination of linear kernel support vector
machines and a $k$-nearest neighbour approach. The most similar work to ours
is Nguyen and Cornips (2016), which focused on detecting intra-word CS for
Dutch–Limburgish Nguyen et al. (2015). The authors utilized Morfessor Creutz
and Lagus (2002) to segment all words into morphemes and Wikipedia to assign
LID probabilities to each morpheme. However, their task definition and
evaluation are on the word level. Furthermore, as this method relies on large
monolingual resources, it is not applicable to low-resource languages like
Wixarika, which does not even have its own Wikipedia edition.

Subword-level LID consists of both segmentation and tagging of words. An
earlier approach to handle a similar scenario was the connectionist temporal
classification (CTC) model developed by Graves et al. (2006). The disadvantage
of this model was the lack of prediction of the segmentation boundaries that
are necessary for our task. Kong et al. (2016) later proposed the SegRNN model
that segments and labels jointly, with successful applications on automatic
glossing of polysynthetic languages Micher (2017, 2018). Segmentation of words
into morphemes alone has a long history in NLP Harris (1951), including semi-
or unsupervised methods Goldsmith (2001); Creutz and Lagus (2002); Hammarström
and Borin (2011); Grönroos et al. (2014), as well as supervised ones Zhang and
Clark (2008); Ruokolainen et al. (2013); Cotterell et al. (2015); Kann et al.
(2018).

##  3 Task and Data Description

###  3.1 Task Description

Formally, the task of subword-level LID consists of producing two sequences,
given an input sequence of tokens $X=\langle
x_{1},\dots,x_{i},\dots,x_{|X|}\rangle$. The first sequence contains all words
and splits $X^{s}=\langle x^{s}_{1},\dots,x^{s}_{i},\dots,x^{s}_{|X|}\rangle$,
where each $x^{s}_{i}$ is an $m$-tuple of variable length $0<m\leq|x_{i}|$,
where $|x_{i}|$ is the number of characters in $x_{i}$. The second sequence is
such that $T^{s}=\langle t^{s}_{1},\dots,t^{s}_{i},\dots,t^{s}_{|X|}\rangle$,
where $|T^{s}|=|X^{s}|=|X|$ and each $t^{s}_{i}\in T^{s}$ is an $n$-tuple of
tags from a given set of LID tags. An input–output example for a DE–TR mixed
phrase is shown in Figure 2.

Input |  $\langle$ ‘Yerim’, | ‘seni’, | ‘,’, | ‘danke’, | ‘Schatzym’$\rangle$
---|---|---|---|---|---
Output |  $\langle$ (Yerim), | (seni), | (,), | (danke), | (Schatzy, m)$\rangle$
|  $\langle$ (TR), | (TR), | (OTHER), | (DE), | (DE, TR)$\rangle$
Figure 2: Subword-level LID in German–Turkish.

###  3.2 Datasets

#### German–Turkish

The German–Turkish Twitter Corpus (Çetinoğlu and Çöltekin, 2016) consists of
1029 tweets with 17K tokens. They are manually normalized, tokenized, and
annotated with language IDs. The language ID tag set consists of TR (Turkish),
DE (German), LANG3 (other language), MIXED (intra-word CS), AMBIG (ambiguous
language ID in context), and OTHER (punctuation, numbers, emoticns, symbols,
etc.). Named entities are tagged with a combination of NE and their language
ID: NE.TR, NE.DE, NE.LANG3. In the original corpus, some Turkish and mixed
words undergo a morphosyntactic split,222E.g., separating copular suffixes
from roots they are attached to, cf. Çetinoğlu and Çöltekin (2016) for
details. with splitting points not usually corresponding to language
boundaries. For the purpose of subword-level LID, these morphosyntactic splits
are merged back into single words. We then manually segment MIXED words at
language boundaries, and replace their labels with more fine-grained language
ID tags. The total percentage of mixed words is $2.75\%$. However, the
percentage of sentences with mixed words is 15.66%. The complete dataset
statistics can be found in Table 1.
author=Ozlem,color=blue!40,size=,fancyline,caption=,]typoauthor=Manuel,color=orange!40,size=,fancyline,caption=,]corrected
author=Ozlem,color=blue!40,size=,fancyline,caption=,]Correct the Table 1
caption, adapt it to the Table 2 caption. Corrections: LIDs -¿ language IDs,
The All -¿ All author=Manuel,color=orange!40,size=,fancyline,caption=,]Done.

Tokens | All | % | Unique | Unique %
---|---|---|---|---
DE | 3992 | 20.37 | 1360 | 20.43
TR | 9913 | 50.59 | 4071 | 61.16
LANG3 | 112 | 0.57 | 83 | 1.25
AMBIG | 32 | 0.16 | 23 | 0.18
OTHER | 4345 | 22.17 | 294 | 4.42
NE.TR | 417 | 2.13 | 275 | 4.13
NE.DE | 389 | 1.99 | 244 | 3.67
NE.AMBIG | 16 | 0.08 | 12 | 1.25
NE.LANG3 | 112 | 0.57 | 95 | 1.43
MIXED | 231 | 1.18 | 183 | 2.75
DE TR | 231 | 100.0 | 183 | 100.0
Table 1: The frequency breakdown of tokens by language IDs in the German-
Turkish dataset. All: the total number of tokens per tag, %: the percentage of
them with respect to the total number of tokens; Unique: the number of unique
word types, and Unique %: the percentage of them with respect the total number
of unique word types.

#### Spanish–Wixarika

Our second dataset consists of 985 sentences and 8K tokens in Spanish and
Wixarika. Wixarika is spoken by approximately $50,000$ people in the Mexican
states of Durango, Jalisco, Nayarit and Zacatecas Leza and López (2006) and is
polysynthetic, with most morphemes ocurring in verbs. The data is collected
from public postings and comments from Facebook accounts. To ensure the public
characteristic of these posts, we manually collect data that is accessible
publicly without being logged in to Facebook, to comply with the terms of use
and privacy of the users. These posts and comments are taken from 34 users: 14
women, 10 men, and the rest does not publically reveal their gender. None of
them have publically mentioned their age. To get a dataset that focuses on the
LID task, we only consider threads where the CS phenomenon appears. We replace
usernames with @username in order to preserve privacy. Afterwards, we tokenize
the text, segment mixed words, and add language IDs to words and segments.

Tokens | All | % | Unique | Unique %
---|---|---|---|---
ES | 4218 | 50.73 | 1527 | 45.76
WIX | 2019 | 24.28 | 1191 | 35.69
EN | 24 | 0.29 | 21 | 0.63
AMBIG | 28 | 0.34 | 25 | 0.75
OTHER | 1664 | 20.01 | 288 | 8.63
NE.ES | 96 | 01.15 | 85 | 2.55
NE.WIX | 77 | 0.93 | 49 | 1.47
NE.EN | 11 | 0.13 | 9 | 0.27
MIXED | 177 | 02.13 | 142 | 4.26
ES WIX | 35 | 19.77 | 31 | 21.83
WIX ES | 122 | 68.93 | 93 | 65.49
WIX ES WIX | 17 | 9.60 | 31 | 10.56
WIX EN | 1 | 0.07 | 1 | 0.07
EN ES | 1 | 0.07 | 1 | 0.07
Table 2: Number of tokens classified by language tags seen in the Spanish-
Wixarika dataset. We show the total number of Tokens per tag, their proportion
(%) with the total tokens, the Unique word types, and the proportion (U. %) of
them with the total number of unique word types.

The tag set is parallel to that of German–Turkish: ES (Spanish), WIX
(Wixarika), EN (English), AMBIG (ambiguous) OTHER (punctuation, numbers,
emoticons, etc), NE.ES, NE.WIX and NE.EN (named entities). Mixed words are
segmented and each segment is labeled with its corresponding language (ES,
WIX, EN). Table 2 shows a detailed description of the dataset. The percentage
of mixed words is higher than in the DE–TR dataset: $3.13\%$ of the tokens and
$4.26\%$ of the types. The most common combination is Spanish roots with
Wixarika affixes. Furthermore, 16.55% of the sentences contain mixed
words.author=Ozlem,color=blue!40,size=,fancyline,caption=,]the URL is empty at
the moment! author=Manuel,color=orange!40,size=,fancyline,caption=,]Thank you!
:)

We split the DE–TR corpus and the ES–WIX corpus into training and test sets of
sizes 800:229 and 770:216, respectively. Error analysis and hyperparameter
tuning are done on the training set via 5-fold cross-validation. We present
results on the test sets. Both datasets are available at https://www.ims.uni-
stuttgart.de/institut/mitarbeiter/ozlem/NAACL2019.html

| DE–TR | ES–WIX
---|---|---
| Segmentation | Tagging | Char | Segmentation | Tagging | Char
| P | R | F1 | P | R | F1 | Acc. | P | R | F1 | P | R | F1 | Acc.
SegRNN | 60.4 | 46.8 | 53.0 | 78.8 | 60.2 | 74.0 | 72.9 | 75.6 | 62.7 | 68.5 | 85.3 | 70.5 | 77.2 | 84.6
BiLSTM+Seq2Seq | 46.1 | 33.4 | 38.7 | 84.3 | 66.8 | 74.5 | 67.7 | 66.6 | 52.2 | 58.5 | 82.4 | 66.2 | 73.4 | 78.4
BiLSTM+CRF | 49.4 | 34.5 | 40.6 | 84.3 | 66.8 | 74.5 | 68.0 | 61.1 | 48.4 | 54.0 | 82.4 | 66.3 | 73.4 | 76.7
CRFTag+Seq2Seq | 12.7 | 6.8 | 8.9 | 27.8 | 15.2 | 19.7 | 37.2 | 47.2 | 31.9 | 38.1 | 63.5 | 43.0 | 51.3 | 69.6
CRFTag+CRF | 11.0 | 5.9 | 7.7 | 27.8 | 15.2 | 19.7 | 36.8 | 47.6 | 32.4 | 38.6 | 63.5 | 43.0 | 51.3 | 69.4
CharBiLSTM | 19.1 | 26.6 | 22.2 | 32.9 | 45.7 | 38.2 | 61.1 | 49.7 | 52.2 | 50.8 | 63.1 | 68.1 | 66.5 | 75.7
Table 3: Segmentation and LID test results for mixed words only.

author=Ozlem,color=blue!40,size=,fancyline,caption=,]we sometimes say LID,
sometimes tagging. should make them consistent in the text and in the tables
author=Manuel,color=orange!40,size=,fancyline,caption=,]Should I replace it
with ‘LID tagging’? Or only ‘LID’?
author=Ozlem,color=blue!40,size=,fancyline,caption=,]In our paper LID stands
for Language Identification. So Language Identification Tagging doesn’t make
sense. If ’LID’ is used as Language ID we should explicitly write it, e.g.
Table 1 caption (there could be some others, I didn’t check)
author=Manuel,color=orange!40,size=,fancyline,caption=,]Oh! I see. I will read
it and try to find such cases.

##  4 Experiments

Our main system is a neural architecture that jointly solves the segmentation
and language identification tasks. We compare it to multiple pipeline systems
and another joint system.

###  4.1 SegRNN

We suggest a SegRNN Kong et al. (2016) would be the best fit for our task
because it models a joint probability distribution over possible segmentations
of the input and labels for each segment.

The model is trained to optimize the following objective, which corresponds to
the joint log-likelihood of the segment lengths $e$ and the language tags $t$:

$\displaystyle{\cal L(\theta)}\\!=$
$\displaystyle\\!\\!\\!\sum_{(x,t,e)\in{\cal D}}-\log p(t,e|x)$ (1)

${\cal D}$ denotes the training data, $\theta$ is the set of model parameters,
$x$ the input, $t$ the tag sequence and $e$ the sequence of segment lengths.

Our inputs are single words.333We also experimented with entire phrases as
inputs, and the achieved scores were slightly worse than for word-based
inputs. As hyperparameters we use: 1 RNN layer, a 64-dimensional input layer,
32 dimensions for tags, 16 for segments, and 4 for lengths. For training, we
use Adam Kingma and Ba (2014).

###  4.2 Baselines

#### BiLSTM+Seq2Seq/BiLSTM+CRF

Our first baselines are pipelines. First, the input text is tagged with
language IDs. Language IDs of a mixed word are directly predicted as a
combination of all language ID tags of the word (i.e., WIX_ES). Second, a
subword-level model segments words with composed language ID tags. For word-
level tagging, we use a hierarchical bidirectional LSTM (BiLSTM) that
incorporates both token- and character-level information Plank et al. (2016),
similar to the winning system Samih et al. (2016) of the Second Code-Switching
Shared Task Molina et al. (2016). 444For all BiLSTM models input dimension is
100 with a hidden layer size of 100. For training we use a stochastic gradient
descent Bottou (2010), 30 epochs, with a learning rate of 0.1. A 0.25 dropout
factor is applied.
author=Manuel,color=orange!40,size=,fancyline,caption=,]Added hyperparameters
to this baseline as requested by the reviewers. Not sure if we should keep it.
For the subword level, we use two supervised segmentation methods: a CRF
segmenter proposed by Ruokolainen et al. (2013), that models segmentation as a
labeling problem and a sequence-to-sequence (Seq2Seq) model trained with an
auxiliary task as proposed by Kann et al. (2018).

#### CRFTag+Seq2Seq/CRFTag+CRF

Since our datasets might be small for training neural networks, we substitute
the BiLSTM with a CRF tagger (Müller et al., 2013, CRFTag) in the first step.
For segmentation, we use the same two approaches as for the previous
baselines.

#### CharBiLSTM

We further employ a BiLSTM to tag each character with a language ID. For
training, each character inherits the language ID of the word or segment it
belongs to. At prediction time, if the characters of a word have different
language IDs, the word is split.

###  4.3 Metrics

We use two metrics for evaluation. First, we follow Kong et al. (2016) and
calculate precision (P), recall (R), and F1, using segments as units (an
unsegmented word corresponds to one segment). We also report a tagging
accuracy (Char Acc.) by assigning a language ID to each character and
calculating the ratio of correct language tags over all characters.

| DE–TR | ES–WIX
---|---|---
| Seg. | Tag. | Char | Seg. | Tag. | Char
| F1 | F1 | Acc. | F1 | F1 | Acc.
SegRNN | 98.7 | 94.0 | 93.6 | 97.8 | 92.5 | 92.4
BiLSTM+Seq2Seq | 98.6 | 95.1 | 94.3 | 98.1 | 90.9 | 90.7
BiLSTM+CRF | 98.7 | 94.9 | 94.4 | 97.9 | 87.8 | 90.6
CRFTag+Seq2Seq | 98.4 | 93.7 | 93.1 | 97.7 | 90.4 | 90.1
CRFTag+CRF | 98.4 | 93.7 | 93.1 | 97.6 | 90.3 | 90.1
CharBiLSTM | 87.7 | 88.0 | 92.5 | 89.7 | 87.9 | 91.3
Table 4: Test set results for entire datasets.

###  4.4 Results and Discussion

Table 4 shows all test results for the entire datasets. We find the following:
(i) For ES–WIX, SegRNN performs slightly better for tagging than the best
baseline, both in terms of F1 and character accuracy. For DE–TR, SegRNN and
BiLSTM+CRF are the best segmentation models, but the BiLSTM models slightly
outperform SegRNN for tagging. (ii) The CRF pipelines perform slightly worse
than the best word-level BiLSTM models for both datasets and all evaluations.

Figure 3: Confusion matrices of the two best models on both datasets. The $x$
axis represents tags seen in the gold standard, and the $y$ axis shows the
corresponding predicted tags. Values are rounded up, therefore not all columns
add up to 1.

Table 3 shows the results of tagging and segmentation only for the mixed words
in our datasets. Here, we can see that: (i) Our SegRNN model achieves the best
performance for segmentation. Differences to the other approaches are $\geq
10\%$, showing clearly why these models are good for the task when the number
of words belonging to two languages is high. (ii) The pipeline BiLSTM models
work best for tagging of the DE–TR data with a slight margin, but underperform
on the ES–WIX dataset as compared to the SegRNN models. (iii) Both CRFTag
models achieve very low results for both segmentation and tagging. (iv)
CharBiLSTM performs better than the CRFTag models on both tasks, but is worse
than all other approaches in our experiments.

More generally, we further observe that recall on mixed words for the DE–TR
pair is low for all systems, as compared to ES–WIX. This effect is especially
strong for the CRFTag and CharBiLSTM models, which seem to be unable to
correctly identify mixed words. While this tendency can also be seen for the
ES–WIX pair, it is less extreme. We suggest that the better segmentation and
tagging of mixed words for ES–WIX might mostly be due to the higher percentage
of available examples of mixed words in the training set for ES–WIX.

Overall, we conclude that SegRNN models seem to work better on language pairs
that have more intra-word CS, while pipeline approaches might be as good for
language pairs where the number of mixed words is lower.

author=Ozlem,color=blue!40,size=,fancyline,caption=,]fig3 caption: Values are
rounded up, therefore not all columns add up to 1. I don’t repeat my other
comments about the matrices.

#### Error analysis.

Figure 3 author=Katharina,color=green!40,size=,fancyline,caption=,]The caption
is grammatically
incorrect.author=Manuel,color=orange!40,size=,fancyline,caption=,]changed sums
to sum. Is there other grammar error? shows confusion matrices for SegRNN and
BiLSTM+Seg2Seg. Both models achieve good results assigning monolingual tags
(ES, WIX, DE, TR) and punctuation symbols (OTHERS). The hardest labels to
classify are named entities (NE, NE.TR, NE.TR, NE.WIX, NE.ES), as well as
third language and ambiguous tags (LANG3, EN, AMBIG). Performance on
multilingual tags (DE TR, WIX ES, ES WIX, WIX ES WIX) is mixed. For DE TR,
BiLSTM+Seq2Seq gets slightly better classifications, but for the ES–WIX tags
SegRNN achieves better results.
author=Katharina,color=green!40,size=,fancyline,caption=,]Write tags in the
same way always! author=Manuel,color=orange!40,size=,fancyline,caption=,]ups!
author=Katharina,color=green!40,size=,fancyline,caption=,]Still wrong.

Regarding author=Ozlem,color=blue!40,size=,fancyline,caption=,]in regards to
-¿ regardingauthor=Manuel,color=orange!40,size=,fancyline,caption=,]Done
oversegmentation problems, BiLSTM+Seq2Seq (0.8% for DE–TR and 2.0% for ES–WIX)
slightly underperforms
author=Ozlem,color=blue!40,size=,fancyline,caption=,]under performs -¿
underperformsauthor=Manuel,color=orange!40,size=,fancyline,caption=,]done
SegRNN (0.7% for DE–TR and 1.13% for ES–WIX). The BiLSTM+Seq2Seq (2.4%) makes
fewer undersegmentation errors for DE–TR than SegRNN (2.7%). However, for
ES–WIX, SegRNN performs better with 3.81% undersegmentation errors compared to
4.2% of BiLSTM+Seq2Seq.

##  5 Conclusion

In this paper, we extended the LID task to the subword level, which is
particularly important for code-switched text in morphologically rich
languages. We further proposed a SegRNN model for the task and compared it to
several strong baselines. Investigating the behaviour of all systems, we found
that pipelines including a BiLSTM tagger work well for tagging DE–TR, where
the number of mixed tokens is not that high, but that our proposed SegRNN
approach performs better than all other systems for ES–WIX. Also, SegRNNs have
clear advantages over all baselines if we consider mixed words only. Our
subword-level LID datasets for ES–WIX and DE–TR are publicly available.
author=Katharina,color=green!40,size=,fancyline,caption=,]IMPORTANT: change
that sentence!!
author=Manuel,color=orange!40,size=,fancyline,caption=,]Deleted. We already
have a footnote with a link to the datasets.
author=Katharina,color=green!40,size=,fancyline,caption=,]Please repeat the
mention of the dataset in the conclusion.

## Acknowledgments

We would like to thank Mohamed Balabel, Sam Bowman, Agnieszka Falenska, Ilya
Kulikov and Phu Mon Htut for their valuable feedback. We also want to thank
Jeffrey Micher for his help with the setup of the SegRNN code. This project
has benefited from financial support to Manuel Mager and Özlem Çetinoğlu by
DFG via project CE 326/1-1 “Computational Structural Analysis of German-
Turkish Code-Switching”, to Manuel Mager by DAAD Doctoral Research Grant, and
to Katharina Kann by Samsung Research.

author=Ozlem,color=blue!40,size=,fancyline,caption=,]:) Initials are
unnecessary when there are still 5-6 empty lines. When used, my initials
should have diacritics.

## References

  * Al-Badrashiny and Diab (2016) Mohamed Al-Badrashiny and Mona Diab. 2016.  Lili: A simple language independent approach for language identification.  In _COLING_.
  * Barman et al. (2014) Utsab Barman, Amitava Das, Joachim Wagner, and Jennifer Foster. 2014.  Code mixing: A challenge for language identification in the language of social media.  _EMNLP_.
  * Bottou (2010) Léon Bottou. 2010.  Large-scale machine learning with stochastic gradient descent.  In _COMPSTAT_. Springer.
  * Çetinoğlu (2016) Özlem Çetinoğlu. 2016.  A Turkish-German code-switching corpus.  In _LREC_.
  * Çetinoğlu and Çöltekin (2016) Özlem Çetinoğlu and Çağrı Çöltekin. 2016.  Part of speech annotation of a Turkish-German code-switching corpus.  In _LAW-X_ , Berlin, Germany.
  * Cotterell et al. (2015) Ryan Cotterell, Thomas Müller, Alexander Fraser, and Hinrich Schütze. 2015\.  Labeled morphological segmentation with semi-markov models.  In _CoNLL_.
  * Creutz and Lagus (2002) Mathias Creutz and Krista Lagus. 2002.  Unsupervised discovery of morphemes.  In _SIGMORPHON_.
  * Goldsmith (2001) John Goldsmith. 2001.  Unsupervised learning of the morphology of a natural language.  _Computational Linguistics_ , 27(2):153–198.
  * Graves et al. (2006) Alex Graves, Santiago Fernández, Faustino Gomez, and Jürgen Schmidhuber. 2006.  Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks.  In _ICML_. ACM.
  * Grönroos et al. (2014) Stig-Arne Grönroos, Sami Virpioja, Peter Smit, and Mikko Kurimo. 2014.  Morfessor flatcat: An HMM-based method for unsupervised and semi-supervised learning of morphology.  In _COLING_.
  * Grosjean (2010) F. Grosjean. 2010.  _Bilingual: Life and Reality_.  Harvard University Press.
  * Hammarström and Borin (2011) Harald Hammarström and Lars Borin. 2011.  Unsupervised learning of morphology.  _Computational Linguistics_ , 37(2).
  * Harris (1951) Zellig S Harris. 1951.  Methods in structural linguistics.
  * Kann et al. (2018) Katharina Kann, Manuel Mager, Ivan Meza, and Hinrich Schütze. 2018.  Fortification of neural morphological segmentation models for polysynthetic minimal-resource languages.  In _NAACL-HLT_.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _ICLR_.
  * Kong et al. (2016) Lingpeng Kong, Chris Dyer, and Noah A Smith. 2016.  Segmental recurrent neural networks.  _Interspeech_.
  * Leza and López (2006) José Luis Iturrioz Leza and Paula Gómez López. 2006.  _Gramática wixarika_ , volume 1.  Lincom Europa.
  * Micher (2017) Jeffrey Micher. 2017.  Improving coverage of an inuktitut morphological analyzer using a segmental recurrent neural network.  In _ComputEL_.
  * Micher (2018) Jeffrey Micher. 2018.  Using the Nunavut Hansard data for experiments in morphological analysis and machine translation.  In _PYLO_.
  * Molina et al. (2016) Giovanni Molina, Fahad AlGhamdi, Mahmoud Ghoneim, Abdelati Hawwari, Nicolas Rey-Villamizar, Mona Diab, and Thamar Solorio. 2016.  Overview for the second shared task on language identification in code-switched data.  In _CS Workshop_.
  * Müller et al. (2013) Thomas Müller, Helmut Schmid, and Hinrich Schütze. 2013.  Efficient higher-order CRFs for morphological tagging.  In _EMNLP_.
  * Nguyen and Cornips (2016) Dong Nguyen and Leonie Cornips. 2016.  Automatic detection of intra-word code-switching.  In _SIGMORPHON_.
  * Nguyen et al. (2015) Dong Nguyen, Dolf Trieschnigg, and Leonie Cornips. 2015.  Audience and the use of minority languages on twitter.  In _ICWSM_.
  * Plank et al. (2016) Barbara Plank, Anders Søgaard, and Yoav Goldberg. 2016.  Multilingual part-of-speech tagging with bidirectional long short-term memory models and auxiliary loss.  In _ACL_.
  * Rijhwani et al. (2017) Shruti Rijhwani, Royal Sequiera, Monojit Choudhury, Kalika Bali, and Chandra Shekhar Maddila. 2017.  Estimating code-switching on twitter with a novel generalized word-level language detection technique.  In _ACL_.
  * Ruokolainen et al. (2013) Teemu Ruokolainen, Oskar Kohonen, Sami Virpioja, and Mikko Kurimo. 2013.  Supervised morphological segmentation in a low-resource learning setting using conditional random fields.  In _CoNLL_.
  * Samih et al. (2016) Younes Samih, Suraj Maharjan, Mohammed Attia, Laura Kallmeyer, and Thamar Solorio. 2016.  Multilingual code-switching identification via LSTM recurrent neural networks.  In _CS Workshop_.
  * Shirvani et al. (2016) Rouzbeh Shirvani, Mario Piergallini, Gauri Shankar Gautam, and Mohamed Chouikha. 2016.  The howard university system submission for the shared task in language identification in Spanish-English codeswitching.  In _CS Workshop_.
  * Solorio et al. (2014) Thamar Solorio, Elizabeth Blair, Suraj Maharjan, Steven Bethard, Mona Diab, Mahmoud Gohneim, Abdelati Hawwari, Fahad AlGhamdi, Julia Hirschberg, Alison Chang, et al. 2014.  Overview for the first shared task on language identification in code-switched data.  _CS Workshop_.
  * Zhang et al. (2018) Yuan Zhang, Jason Riesa, Daniel Gillick, Anton Bakalov, Jason Baldridge, and David Weiss. 2018.  A fast, compact, accurate model for language identification of codemixed text.  In _EMNLP_.
  * Zhang and Clark (2008) Yue Zhang and Stephen Clark. 2008.  Joint word segmentation and POS tagging using a single perceptron.  _ACL-HLT_.