# Deep SIMBAD:
Active Landmark-based Self-localization Using Ranking -based Scene Descriptor

Tanaka Kanji Our work has been supported in part by JSPS KAKENHI Grant-in-Aid
for Scientific Research (C) 17K00361 and 20K12008.The authors are with
Graduate School of Engineering, University of Fukui, Japan.
<EMAIL_ADDRESS>
###### Abstract

Landmark-based robot self-localization has recently garnered interest as a
highly-compressive domain-invariant approach for performing visual place
recognition (VPR) across domains (e.g., time of day, weather, and season).
However, landmark-based self-localization can be an ill-posed problem for a
passive observer (e.g., manual robot control), as many viewpoints may not
provide an effective landmark view. In this study, we consider an active self-
localization task by an active observer and present a novel reinforcement
learning (RL)-based next-best-view (NBV) planner. Our contributions are as
follows. (1) SIMBAD-based VPR: We formulate the problem of landmark-based
compact scene description as SIMBAD (similarity-based pattern recognition) and
further present its deep learning extension. (2) VPR-to-NBV knowledge
transfer: We address the challenge of RL under uncertainty (i.e., active self-
localization) by transferring the state recognition ability of VPR to the NBV.
(3) NNQL-based NBV: We regard the available VPR as the experience database by
adapting nearest-neighbor approximation of Q-learning (NNQL). The result shows
an extremely compact data structure that compresses both the VPR and NBV into
a single incremental inverted index. Experiments using the public NCLT dataset
validated the effectiveness of the proposed approach.

##  I Introduction

Landmark-based robot self-localization has recently garnered interest as a
highly-compressive domain-invariant approach for performing visual place
recognition (VPR) across domains (e.g., time of day, weather, season). In
long-term cross-domain navigation [1, 2, 3], a robot vision must be able to
recognize its location (i.e., self-localization) and the main objects [4]
(i.e., landmarks) in the scene. This landmark-based self-localization problem
presents two unique challenges. (1) Landmark selection: In the offline
training stage, the robot must learn the main landmarks that represent the
robot workspace in either a self-supervised or unsupervised manner [5]. (2)
Next best view (NBV): In the online self-localization stage, the robot must
determine the NBVs to re-identify as many spatially sparse landmarks as
possible [6]. This study focuses on the NBV problem.

In landmark-based self-localization, the only available feature (Fig. 1) in
each map/live scene $x$ is landmark $p_{i}(i\in[1,r])$ observed at signal
strength $d(x,p_{i})$ (i.e., landmark ID + intensity). This is in contrast to
many existing self-localization frameworks that assume the availability of
vectorial features for each map image. To address this issue, we formulate the
landmark-based self-localization as similarity-based pattern recognition
(SIMBAD) [7] and present its deep-learning extension. In pattern recognition,
SIMBAD is a highly-compressive method to describe an object as its
dissimilarities from $r$ prototypes (e.g., $r=500$), which is particularly
effective when traditional vectorial descriptions of objects are difficult to
obtain or inefficient for learning. We adopt SIMBAD because of the following
two reasons: (1) First, the landmark selection problem is analogous to and can
be informed by the well-investigated problem of prototype selection or
optimization [8]. (2) Second, many recent deep learning techniques can
effectively measure the (dis)similarity between an object and prototypes [9],
instead of directly describing an object. However, the deep learning extension
of SIMBAD has not yet been sufficiently investigated, and hence is the main
focus of our current study.

Figure 1: Motivation. Unlike existing approaches that maintain the model of an
entire environment (left panel), we aim to maintain only a small fraction
(i.e., landmark regions) of the robot workspace (right panel). Hence, the per-
domain cost for retraining (change detection, map updating) is inherently low.
However, self-localization with such spatially sparse landmarks can be an ill-
posed problem for a passive observer, as many viewpoints may not provide an
effective landmark view. Therefore, we considered an active observer and
presented an active landmark-based self-localization framework.

Most existing self-localization techniques reported hitherto assume a passive
observer (e.g., manual robot control) and do not consider the issue of
viewpoint planning or observer control. However, landmark-based self-
localization can be an ill-posed problem for a passive observer, as many
viewpoints may not provide an effective landmark view. Therefore, we aim to
develop an active observer that can adapt its viewpoints, thereby avoiding
non-salient scenes that provide no effective landmark view, or moving
efficiently toward locations that are the most informative, to reduce
sensing/computation costs. This is associated closely with the NBV problem
investigated in machine vision studies [10]. However, in our cross-domain
scenario, the NBV planner is trained and tested in different domains. The cost
for retraining such an NBV planner that does not consider domain shifts is
high in cross-domain scenarios, and we intend to address this issue in the
current study.

In this study, we investigated an active landmark-based self-localization
framework from a novel perspective of SIMBAD. Our primary contributions are
threefold: (1) SIMBAD-based VPR: First, we present a landmark-based compact
scene descriptor by introducing a deep-learning extension of SIMBAD. Our
strategy is to describe each map/live scene $x$ with dissimilarities
$\\{d(x,p_{i})\\}$ from the prototypes (i.e., landmarks)
$\\{p_{i}\\}_{i=1}^{r}$ and further compress it into a length $h$ $(\ll r)$
list of ranked IDs (e.g., $r=500$, $h=4$) of top-$h$ most similar landmarks
$\\{(v_{1},\cdots,v_{h})|d(x,p_{v_{1}})<\cdots<d(x,p_{v_{h}})\\},$ which can
then be efficiently indexed using an inverted index. (2) VPR-to-NBV knowledge
transfer: Second, we address the challenge of RL under uncertainty (i.e.,
active self-localization) by transferring the state recognition ability of VPR
to the NBV. Our scheme is based on a recently developed method of reciprocal
rank feature (RRF) [11], inspired by our previous works [11, 12, 13], which is
effective for transfer learning [14] and information retrieval [15]. (3) NNQL-
based NBV: Third, we regard the available VPR as the experience database by
adapting nearest-neighbor approximation of Q-learning (NNQL) [16]. The result
is an extremely compact data structure that compresses the VPR and NBV into a
single incremental inverted index. Experiments using the public NCLT dataset
validated the effectiveness of the proposed approach.

Figure 2:  Active self-localization system. Online processing comprised three
main stages: scene description, passive self-localization, and NBV planning.
Offline processing comprised landmark selection, mapping, and NN Q-learning.
Details of the scene description module are provided in Fig. 3. Details of the
NN lookup module are provided in Fig. 4.

##  II Approach

The active self-localization system aims to estimate the robot location on a
prelearned route (Fig. 2). It iterates for each viewpoint, three main steps:
scene description, (passive) self-localization, and NBV planning. The scene
description describes an input map/live image $x$ as its dissimilarities
$D(x,\cdot)$ from the predefined landmarks. The (passive) self-localization
incorporates each perceptual/action measurement into the belief of the robot
viewpoint. The NBV planning takes the scene descriptor $x$ of a live image and
determines the NBV action. In addition, three additional modules exist, i.e.,
landmark selection, mapping, and nearest-neighbor Q-learning, which operates
offline to learn the prior knowledge (“landmarks,” “map,” and “Q-function”)
required for the abovementioned three main modules. These individual modules
are described in detail in the following subsections.

###  II-A Landmark Model

The proposed landmark model can be explained as follows. Let
$R=\\{p_{1},p_{2},\cdots,p_{r}\\}$ be a set of $r$ predefined prototypes
(i.e., landmarks). For a dissimilarity measure $d$, which measures the
dissimilarity between a prototype $p$ and an input object $x$, one may
consider a new description based on the proximities to the set $R$, as
$D(x,R)=$$[d(x,p_{1})$, $d(x,p_{2})$, $\cdots$, $d(x,p_{r})]$. Here, $D(x,R)$
is a data-dependent mapping $D(\cdot,R)$: $X$ $\rightarrow$ $\mathbb{R}^{r}$
from a representation $X$ to the dissimilarity space, defined by set $R$. This
is a vector space, in which each dimension corresponds to a dissimilarity
$D(\cdot,p_{i})$ to the prototype from $R$. A vector $D(\cdot,p_{i})$ of
dissimilarities to the prototype $p_{i}$ can be interpreted as a feature. It
is noteworthy that even when no landmark is present in the input image, the
proposed model still can describe the image as dissimilarities to the
landmarks.

Figure 3: Scene description module. First, the input query/landmark images are
translated into vectorial features. Subsequently, the query feature is
described by its dissimilarities from the landmark features. Next, the
dissimilarity values are ranked to obtain a ranked list of top-$h$ most
similar landmarks. Finally, the proposed landmark ranking-based scene
descriptor is obtained.

The advantage of this representation is its applicability to any method in
dissimilarity spaces, including recent deep learning techniques. For example,
$d$ can be (1) a pairwise comparison network (e.g., deep Siamese [17]) that
predicts the dissimilarity $d(x,p)$ between $p$ and $x$, (2) a deep anomaly
detection network (e.g., deep autoencoder [18]) that predicts the deviation
$d(x|p)$ of $x$ from learned prototypes $p$, (3) an object proposal network
(e.g., feature pyramid network [19]) that predicts object bounding-boxes and
class label $d(p|x)$ (e.g., [20]), (4) an L2 distance $|f(x)-f(p)|$ of deep
feature $f(\cdot)$ [21] between $p$ and $x$, as well as (5) any methods for
dissimilarities $d(p,x)$ including those for non-visual modalities (e.g.,
natural language). In the current study, the experimental system was based on
(4) using NetVLAD [22] as the feature extraction network $f(\cdot)$. We
believe that this enables effective exploitation of the discriminative power
of a deep neural network within SIMBAD.

###  II-B Landmark Selection

The landmark selection is performed prior to the training/testing phase, in an
independent “landmark domain”. Landmarks should be selected such that they are
dissimilar to each other. This is because, if the dissimilarity
$d(p_{i},p_{j})$ is small for a prototype pair, $d(x,p_{i})\simeq d(x,p_{j})$
for other objects $x$, then either $p_{i}$ or $p_{j}$ is a redundant
prototype. Intuitively, an ideal clustering algorithm may identify good
landmarks as cluster representatives. However, this clustering is NP-hard
[23]. In practice, heuristics such as k-means algorithms are often used as
alternatives. Moreover, the utility issue (e.g., [24]) complicates the
problem, i.e., landmark visibility and other observation conditions (e.g.,
occlusions and field-of-views) must be considered to identify useful
landmarks. For such landmark selection, only a heuristic approximate solution
exists, i.e., no analytical solution exists [5].

In our study, we do not focus on the landmark selection method; instead, we
propose a simple and effective method. Our solution comprises three
procedures: (1) First, high-dimensional vectorial features $X=\\{x\\}$ (i.e.,
NetVLAD) are extracted from individual candidate images. (2) Subsequently,
each candidate image $x\in X$ is scored by the dissimilarity
$\min_{x^{\prime}\in X\setminus\\{x\\}}|x-x^{\prime}|$ from its nearest
neighbor over the other features. (3) Finally, all the candidate images are
sorted in the descending order of the scores, and the top-$r$ images are
selected as the prototype landmarks. This approach offers two advantages.
First, the selected landmarks are expected to be dissimilar to each other. In
addition, the dissimilarity features $D(\cdot,R)$ are expected to become
accurate when the robot approaches a viewpoint with landmark view.

###  II-C Self-localization

The (offline) mapping is performed prior to the self-localization tasks, in an
independent “training domain”. It extracts a 4,096 dim NetVLAD image feature
from each map image $x$ and then translates it to an $r$-dim dissimilarity
descriptor $D(x,\cdot)$. Subsequently, it sorts the $r$ elements of the
descriptor in the ascending order and returns an ordered list of top-$h$
ranked landmark IDs, which is our proposed $h$-dim scene descriptor (Fig. 3).
With an inverted index, the map image’s ID is indexed by using its landmark ID
and the rank value, as primary and secondary keys (Fig. 4).

The (online) self-localization is performed in a new “test domain”. It
translates an input query image to a ranking-based descriptor. Subsequently,
the inverted index is looked up using each landmark ID in the ordered list as
a query. Hence, a short list of map images with a common landmark ID is
obtained. Next, the relevance of a map image is evaluated as the inner product
$\langle v_{RRF}^{r}(q),v_{RRF}^{h}(m)\rangle$ of RRF between the query image
$q$ and each map image $m$ in the short list. An RRF $v_{RRF}^{h}$ is an
$r$-dim $h$-hot vector whose $i$-th element is the reciprocal $1/v[i]$ of the
rank value $v[i]$ of the $i$-th landmark if $v[i]\leq h$, or 0 otherwise. For
more details regarding the RRF, please refer to [11].

During the active multi-view self-localization, the results of (passive) self-
localization at each viewpoint are incrementally integrated by a particle
filter (PF). PF is a computationally efficient implementation of a Bayes
filter, and can address multimodal belief distributions [25]. In the PF-based
inference system, the robot’s 1D location on the route prelearned in the
training domain is regarded as the state. The PF system is initialized at the
starting viewpoint of the robot. In the prediction stage, the particles are
propagated through a dynamic model using the latest action of the robot. In
the update stage, the likelihood models for the landmark observation are
approximated by the RRF, and the weight of each $k$-th particle is updated as
$w_{k}$$\leftarrow$$w_{k}$+$v_{RRF}[u_{k}]$, where $v_{RRF}[u_{k}]$ is the RRF
element that corresponds to the hypothesized viewpoint $u_{k}$. Other details
are the same as that of the PF-based self-localization framework [25].

Figure 4: Nearest neighbor scheme. (1) Offline mapping stage: First, a map
image is translated to a landmark ranking-based scene descriptor.
Subsequently, the image ID is inserted into the inverted index entries that
have common landmark IDs. (2) Online self-localization stage: First, a live
image is translated into a landmark ranking-based scene descriptor. Next, a
shortlist is obtained from the inverted index entries that have common
landmark IDs, and then refined. Finally, the viewpoints or Q-values associated
with the nearest neighbor states are obtained from the experience database,
and then returned.

###  II-D NBV Planning

The NBV planning task is formulated as an RL problem, in which a learning
agent interacts with a stochastic environment. The interaction is modeled as a
discrete-time discounted Markov decision process (MDP). A discounted MDP is a
quintuple $(S,A,P,R,\gamma)$, where $S$ and $A$ are the set of states and
actions, $P$ the state transition distribution, $R$ the reward function, and
$\gamma\in(0,1)$ a discount factor ($\gamma=0.9$). We denote by $P(\cdot|s,a)$
and $R(s,a)$ the probability distribution over the next state and the
immediate reward of performing action $a$ at state $s$, respectively.

A Markov policy is the distribution over the control actions for the state, in
our case represented by the scene descriptor of a live image (i.e., $s=x$).
The action-value function of a policy $\pi$, denoted by $Q:$ $S\times A$
$\rightarrow$ $\mathbb{R}$, is defined as the expected sum of discounted
rewards that are encountered when policy $\pi$ is executed. For an MDP, the
goal is to identify a policy that yields the best possible values,
$Q^{*}(s,a)$ = $\sup_{\pi}$ $Q^{\pi}(s,a)$, $\forall(s,a)\in S\times A$.

The implementation of the “Q-function” $Q(\cdot,\cdot)$ as a computationally
tractable function is a key issue. A naive implementation of the function
$Q(\cdot,\cdot)$ is to employ a two-dimensional table, which is indexed by a
state-action pair $(s,a)$ and whose element is a Q-value [26]. However, this
simple implementation presents several limitations. In particular, it requires
a significant amount of memory space, proportional to the number and
dimensionality of the state vectors, which are intractable in many
applications including ours. An alternative approach is to use a deep neural
network based approximation of the Q-table (e.g., DQN [27]), as in [28].
However, the DQN must be retrained for every new domain with a significant
amount of space/time overhead. Herein, we present a new highly efficient NNQL-
based approximation that reuses the existing inverted index (II-C) to
approximate $Q(\cdot,\cdot)$ with a small additional space cost.

Our approach is inspired by the recently developed nearest-neighbor
approximation of the Q-function (Fig. 4) [16]. Specifically, the inverted
index which was originally developed for VPR (II-C) is regarded as a
compressed representation of visual experiences in the training domain. Recall
that the inverted index aims to index map image ID using the landmark ID.
Next, we now introduce a supplementary two-dimensional table called
“experience database” that aims to index action-specific Q-values $Q(s,\cdot)$
by map image ID. Subsequently, we approximate the Q-function by the NNQL [16].
The key difference between NNQL and the standard Q-learning is that the
Q-value of an input state-action pair $(s,a)$ in the former is approximated by
a set of Q-values that are associated with its $k$ nearest neighbors ($k=4$).
Next, we used the supplementary table to store the action-specific Q values
$Q(s,\cdot)$. Hence, the Q-function is approximated by
$|N(s|a)|^{-1}\sum_{(s^{\prime},a)\in N(s|a)}Q(s^{\prime},a)$, where $N(s|a)$
is the nearest neighbor of $(s,a)$ conditioned on a specified action $a$. In
fact, such an action-specific NNQL can be regarded as an instance of RL. For
more details regarding NNQL, please refer to [16].

Figure 5: Experimental environments. The trajectories of the four datasets,
“2012/1/22”, “2012/3/31”, “2012/8/4”, and “2012/11/17”, used in our
experiments are visualized in green, purple, blue, and light-blue curves,
respectively.

##  III Experiements

We evaluated the effectiveness of the proposed algorithm via self-localization
tasks in a cross-season scenario.

We used the publicly available NCLT dataset [29]. The data we used included
view image sequences along vehicle trajectories acquired using the front-
facing camera of the Ladybug3, as well as ground-truth GPS viewpoint
information. Both indoor and outdoor change objects such as cars, pedestrians,
construction machines, posters, and furniture were present during seamless
indoor and outdoor navigation by the Segway robot.

In the experiments, we used four different datasets, i.e., “2012/1/22 (WI)”,
“2012/3/31 (SP)”, “2012/8/4 (SU)”, and “2012/11/17 (AU)”, which contained
26,208, 26,364, 24,138, and 26,923 images (Fig. 5). They were used to create
eight different landmark-training-test domain triplets (Fig. 2): WI-SP-SU, WI-
SP-AU, SP-SU-AU, SP-SU-WI, SU-AU-WI, SU-AU-SP, AU-WI-SP, and AU-WI-SU. The
number of landmarks was set to 500 for every triplet, which is consistent with
the settings in our previous studies using the same dataset (e.g., [30]).

For NNQL training, the learning rate was set $\alpha=0.1$. Q-value for a
state-action pair was initialized to 0.0001, and a positive reward of 100 was
assigned when the belief value of the ground-truth viewpoint was top-10%
ranked. The number of training episodes was 10,000. The action candidates are
a set of forward movements $A=\\{1,2,\cdots,10\\}$ [m] along the route defined
in the NCLT dataset. One episode consists of an action sequence of length 10,
and its starting location is randomly sampled from the route.

(a)

(b)

Figure 6: ANR performance of VPR.

Figure 7: Performance results for active self-localization.

The VPR performance at each viewpoint in the context above was measured based
on the averaged normalized rank (ANR). In the ANR, a subjective VPR is modeled
as a ranking function that takes an input query image and assigns a rank value
to each map image. Subsequently, the rank values for the ground-truth map
images are computed, normalized by the number of map images, and averaged over
all test queries, thereby yielding the ANR. A VPR system with high ANR
performance can be regarded as having nearly perfect performance and high
retrieval robustness [31], which is typically required in loop closing
applications [32].

Four different scene descriptors based on NetVLAD were developed as the
baseline/ablation methods: “brute-force”, “SIMBAD”, “bag-of-(most-
similar-)landmarks”, and “RRF”. In “brute-force”, the map model is a nearest-
neighbor search based on the L2 dissimilarity measure with NetVLAD of the
query image, assuming that every map image is described by the NetVLAD
feature. In the other three methods, the map model describes each map image by
the dissimilarities with the $h$ most similar landmarks. More specifically,
“bag-of-landmarks” assumes $h$-hot binary (0/1) similarity value, “SIMBAD”
uses the $h$-hot L2 dissimilarity value, and “RRF” uses the $h$-hot RRF
similarity value.

It is noteworthy that the three methods “SIMBAD”, “bag-of-landmarks”, and
“RRF” require significantly lower time cost owing to the availability of
efficient inverted index.

In terms of space cost, “bag-of-landmarks” is the most efficient, “RRF” and
“SIMBAD” are slightly more expensive because they need to memorize the rank
value for each map image, and “brute-force” is intractably expensive as it
requires to memorize the high-dimensional map features.

Figure 6 shows ANR of single-view VPR tasks.

As can be seen from Fig. 6 (a), the “brute-force” method shows very good
recognition performance, but at the cost of high time/space cost for per-
domain retraining. As we found in [11], NetVLAD’s utility as a dissimilarity-
based feature vector is low. In this experiment, the method “SIMBAD” was about
the same as “bag-of-landmarks” and had slightly lower performance. Compared
with these two methods, the proposed method “RRF” had much higher performance.
To summarize, the proposed method “RRF” achieves a good trade-off between
time/space efficiency and recognition performance. In subsequent experiments,
we will use this “RRF” as the default method for the passive self-localization
module.

As can be seen from Fig. 6 (b), in the case where the rank list length (i.e.,
descriptor size) is very small (e.g., $h=4$), the proposed method has a small
performance drop, while the other two methods have as bad VPR performance as
the chance method (i.e., ANR=50%).

Figure 7 demonstrates the performance of active self-localization. Note that
each episode has a different number of valid observations, and long episodes
do not always provide high performance. We plot the ANR performance for all
test images (frames) on the graph in Fig. 7, regardless of how many episodes
were observed. In the figure, “proposed” is the performance of NBV using NNQL
trained using the RRF feature as a state vector. “baseline” is different from
“proposed” only in that the action is randomly determined. “$a$[m]”
($a\in[1,10]$) is a naive strategy that repeats the same forward movement
$a[m]$ at every viewpoint, independent of the RRFs. They often performed worse
than the “proposed”, and to make the matters worse, which action is best is
domain-dependent and cannot be known in advance. The characteristics that the
higher the VPR performance, the better the active self-localization
performance, is consistent with our recent studies dealing with other VPR
methods (e..g, pole-landmark-based VPR [28], e.g., convolutional neural
network -based VPR [33], and e.g., map-matching-based VPR [34]). It is
noteworthy that the proposed method outperformed all the methods considered
here, although the landmark-based VPR and NNQL-based NBV were compressed into
a single incremental inverted index.

Finally, we also investigated the space/time performance. The inverted index
consumes 15$h$-bit per map image. The main processes, extracting NetVLAD
features, VPR, and NBV consumes 8.6 ms (GPU), 495.4 ms (CPU), and 7$\times
10^{-3}$ ms (CPU) per viewpoint (CPU: intel core i3-1115G4 3.00GHz). The most
time consuming part is the scene description processing in VPR, which consumes
410 ms. The NBV is significantly fast, compared with the recent deep learning
variants, thus the additional cost for the extension from the passive to
active self-localization was little.

##  IV Conclusions and Future Directions

Herein, a new framework for active landmark-based self-localization for highly
compressive applications (e.g., 40-bit image descriptor) was proposed. Unlike
previous approaches of active self-localization, we assumed the main landmark
objects as the only available model of the robot’s workspace (“map”), and
proposed to describe each map/live scene as dissimilarities to these
landmarks. Subsequently, a novel reciprocal rank feature-based VPR-to-NBV
knowledge transfer was introduced to address the challenge of RL under
uncertainty. Furthermore, an extremely compact data structure that compresses
the VPR and NBV into a single incremental inverted index was presented. The
proposed framework was experimentally verified using the public NCLT dataset.

Future work must investigate how to accelerate the (dis)similarity evaluator
$d(\cdot,\cdot)$ while retaining the ability to discriminate between different
levels of (dis)similarities. In the training phase, the evaluator is repeated
for every viewpoint of every episode. Since the number of repetitions is very
large (e.g., 10,000$\times$10$\times$500=5$\times$$10^{7}$), efficiency of
calculation is the key to suppress per-domain retraining cost. Another
direction for future research is compression of the proposed scene/state
descriptor, towards extremely-compressive applications (e.g., [35]). Although
the proposed ranking-based descriptor is the first compact (e.g., 40-bit)
descriptor for the VPR-to-NBV applications, it is still uncompressed, i.e., it
may be further compressed. Finally, our on-going research topic is to
incorporate various (dis)similarity evaluators into the proposed deep SIMBAD
framework, including non-visual -based (dis)similarity evaluators (II-A).

## References

  * [1] M. J. Milford and G. F. Wyeth, “Seqslam: Visual route-based navigation for sunny summer days and stormy winter nights,” in _2012 IEEE International Conference on Robotics and Automation_ , 2012, pp. 1643–1649.
  * [2] W. Churchill and P. Newman, “Experience-based navigation for long-term localisation,” _The International Journal of Robotics Research_ , vol. 32, no. 14, pp. 1645–1661, 2013.
  * [3] R. Arroyo, P. F. Alcantarilla, L. M. Bergasa, and E. Romera, “Fusion and binarization of cnn features for robust topological localization across seasons,” in _2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2016, pp. 4656–4663.
  * [4] A. Torralba, K. P. Murphy, W. T. Freeman, and M. A. Rubin, “Context-based vision system for place and object recognition,” in _Computer Vision, IEEE International Conference on_ , vol. 2. IEEE Computer Society, 2003, pp. 273–273.
  * [5] M. Bürki, C. Cadena, I. Gilitschenski, R. Siegwart, and J. Nieto, “Appearance-based landmark selection for visual localization,” _Journal of Field Robotics_ , pp. 4137–4143, 2016.
  * [6] S. K. Gottipati, K. Seo, D. Bhatt, V. Mai, K. Murthy, and L. Paull, “Deep active localization,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 4, pp. 4394–4401, 2019.
  * [7] A. Feragen, M. Pelillo, and M. Loog, _Similarity-Based Pattern Recognition: Third International Workshop, SIMBAD 2015, Copenhagen, Denmark, October 12-14, 2015. Proceedings_. Springer, 2015, vol. 9370.
  * [8] K. S. Gurumoorthy, P. Jawanpuria, and B. Mishra, “Spot: A framework for selection of prototypes using optimal transport,” _arXiv preprint arXiv:2103.10159_ , 2021.
  * [9] B. Li, W. Wu, Q. Wang, F. Zhang, J. Xing, and J. Yan, “Siamrpn++: Evolution of siamese visual tracking with very deep networks,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 4282–4291.
  * [10] M. Mendoza, J. I. Vasquez-Gomez, H. Taud, L. E. Sucar, and C. Reta, “Supervised learning of the next-best-view for 3d object reconstruction,” _Pattern Recognition Letters_ , vol. 133, pp. 224–231, 2020.
  * [11] K. Takeda and K. Tanaka, “Dark reciprocal-rank: Teacher-to-student knowledge transfer from self-localization model to graph-convolutional neural network,” in _2021 International Conference on Robotics and Automation (ICRA)_ , 2021, pp. 4348–4355.
  * [12] K. Tanaka, “Detection-by-localization: Maintenance-free change object detector,” in _2019 International Conference on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 4348–4355.
  * [13] ——, “Unsupervised part-based scene modeling for visual robot localization,” in _2015 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2015, pp. 6359–6365.
  * [14] G. Hinton, O. Vinyals, and J. Dean, “Distilling the knowledge in a neural network,” _arXiv preprint arXiv:1503.02531_ , 2015.
  * [15] P. K. Atrey, M. A. Hossain, A. El Saddik, and M. S. Kankanhalli, “Multimodal fusion for multimedia analysis: a survey,” _Multimedia systems_ , vol. 16, no. 6, pp. 345–379, 2010.
  * [16] D. Shah and Q. Xie, “Q-learning with nearest neighbors,” _arXiv preprint arXiv:1802.03900_ , 2018.
  * [17] Y. Zhan, K. Fu, M. Yan, X. Sun, H. Wang, and X. Qiu, “Change detection based on deep siamese convolutional network for optical aerial images,” _IEEE Geoscience and Remote Sensing Letters_ , vol. 14, no. 10, pp. 1845–1849, 2017\.
  * [18] J. An and S. Cho, “Variational autoencoder based anomaly detection using reconstruction probability,” _Special Lecture on IE_ , vol. 2, no. 1, pp. 1–18, 2015.
  * [19] S.-W. Kim, H.-K. Kook, J.-Y. Sun, M.-C. Kang, and S.-J. Ko, “Parallel feature pyramid network for object detection,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2018, pp. 234–250.
  * [20] S. Hanada and K. Tanaka, “Partslam: Unsupervised part-based scene modeling for fast succinct map matching,” in _2013 IEEE/RSJ International Conference on Intelligent Robots and Systems_. IEEE, 2013, pp. 1582–1588.
  * [21] A. Babenko, A. Slesarev, A. Chigorin, and V. Lempitsky, “Neural codes for image retrieval,” in _European conference on computer vision_. Springer, 2014, pp. 584–599.
  * [22] R. Arandjelovic, P. Gronat, A. Torii, T. Pajdla, and J. Sivic, “Netvlad: Cnn architecture for weakly supervised place recognition,” pp. 5297–5307, 2016.
  * [23] K. Tanaka, “Self-supervised map-segmentation by mining minimal-map-segments,” in _2020 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2020, pp. 637–644.
  * [24] K. Tanaka, H. Zha, and T. Hasegawa, “Viewpoint planning in map updating task for improving utility of a map,” in _Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003)(Cat. No. 03CH37453)_ , vol. 1. IEEE, 2003, pp. 729–734.
  * [25] F. Dellaert, D. Fox, W. Burgard, and S. Thrun, “Monte carlo localization for mobile robots,” in _1999 International Conference on Robotics and Automation (ICRA)_ , vol. 2, 1999, pp. 1322–1328.
  * [26] R. S. Sutton, A. G. Barto, _et al._ , _Introduction to reinforcement learning_. MIT press Cambridge, 1998, vol. 135.
  * [27] J. Fan, Z. Wang, Y. Xie, and Z. Yang, “A theoretical analysis of deep q-learning,” in _Learning for Dynamics and Control_. PMLR, 2020, pp. 486–489.
  * [28] K. Tanaka, “Active cross-domain self-localization using pole-like landmarks,” in _2021 IEEE International Conference on Mechatronics and Automation (ICMA)_ , 2021, pp. 1188–1194.
  * [29] N. Carlevaris-Bianco, A. K. Ushani, and R. M. Eustice, “University of michigan north campus long-term vision and lidar dataset,” _The International Journal of Robotics Research_ , vol. 35, no. 9, pp. 1023–1035, 2016.
  * [30] T. Hiroki and K. Tanaka, “Long-term knowledge distillation of visual place classifiers,” in _2019 22st International Conference on Intelligent Transportation Systems (ITSC)_ , 2019.
  * [31] P. Hiremath and J. Pujari, “Content based image retrieval using color, texture and shape features,” in _15th International Conference on Advanced Computing and Communications (ADCOM 2007)_. IEEE, 2007, pp. 780–784.
  * [32] J. P. Company-Corcoles, E. Garcia-Fidalgo, and A. Ortiz, “Lipo-lcd: Combining lines and points for appearance-based loop closure detection.” in _BMVC_ , 2020.
  * [33] K. Kurauchi and K. Tanaka, “Deep next-best-view planner for cross-season visual route classification,” in _2020 25th International Conference on Pattern Recognition (ICPR)_ , 2021, pp. 497–502.
  * [34] K. Tanaka, “Active map-matching: Teacher-to-student knowledge transfer from visual-place-recognition model to next-best-view planner for active cross-domain self-localization,” in _2021 IEEE International Conference on Computational Intelligence and Virtual Environments for Measurement Systems and Applications (CIVEMSA)_ , 2021, pp. 1–6.
  * [35] F. Yan, O. Vysotska, and C. Stachniss, “Global localization on openstreetmap using 4-bit semantic descriptors,” in _2019 European Conference on Mobile Robots (ECMR)_. IEEE, 2019, pp. 1–7.


††footnotetext: Copyright © 2020 for this paper by its authors. Use permitted
under Creative Commons License Attribution 4.0 International (CC BY 4.0). CLEF
2020, 22-25 September 2020, Thessaloniki, Greece.11institutetext: Fraunhofer
Institute for Secure Information Technology SIT
Rheinstrasse 75, 64295 Darmstadt, Germany
{Inna.Vogel<EMAIL_ADDRESS>
# Fake News Spreader Detection on Twitter
using Character $N$-Grams

Notebook for PAN at CLEF 2024

Inna Vogel  Meghana Meghana

###### Abstract

The authors of fake news often use facts from verified news sources and mix
them with misinformation to create confusion and provoke unrest among the
readers. The spread of fake news can thereby have serious implications on our
society. They can sway political elections, push down the stock price or crush
reputations of corporations or public figures. Several websites have taken on
the mission of checking rumors and allegations, but are often not fast enough
to check the content of all the news being disseminated. Especially social
media websites have offered an easy platform for the fast propagation of
information. Towards limiting fake news from being propagated among social
media users, the task of this year’s PAN 2020 challenge lays the focus on the
fake news spreaders. The aim of the task is to determine whether it is
possible to discriminate authors that have shared fake news in the past from
those that have never done it. In this notebook, we describe our profiling
system for the fake news detection task on Twitter. For this, we conduct
different feature extraction techniques and learning experiments from a
multilingual perspective, namely English and Spanish. Our final submitted
systems use character $n$-grams as features in combination with a linear SVM
for English and Logistic Regression for the Spanish language. Our submitted
models achieve an overall accuracy of 73% and 79% on the English and Spanish
official test set, respectively. Our experiments show that it is difficult to
differentiate solidly fake news spreaders on Twitter from users who share
credible information leaving room for further investigations. Our model ranked
3rd out of 72 competitors.

Keywords: Author Profiling, Fake News Spreader, Fake News Detection, Deception
Detection, Social Media, Twitter

##  1 Dataset and Corpus Analysis

To train our system, we used the PAN 2020 author profiling
corpus111https://zenodo.org/record/3692319#.XrlnomgzZaQ proposed by Rangel et
al. [10]. The corpus consists of 300 English (EN) and Spanish (ES) Twitter
user accounts each. The tweets of every Twitter user are stored in an XML file
containing 100 tweets per author. Every tweet is stored in a <document> XML
tag. The tweets were manually collected and fact-checked. The dataset is
balanced which means the data refers to an equal distribution of class
instances. Half of the documents per language folder are authors that have
been identified sharing fake news. The other half are texts from credible
users. Table 1 shows excerpts from the data. Every author received an
alphanumeric author-ID which is stored in a separate text file together with
the corresponding class affiliation. For training and testing, we split the
data in the ratio 70/30. The gold-standard can only be accessed through the
TIRA [7] evaluation platform provided by the PAN organizers. The results are
hidden for the participants.

Table 1: English (EN) and Spanish (ES) excerpts from the PAN 2020 Twitter “Fake News Spreader” data. EN and ES True News Tweets | EN and ES Fake News Tweets
---|---
“RT #USER#: Best dunk of the contest no doubt about it. Aaron Gordon robbed again #URL#” |  “Jay-Z Must Give Beyonce $5 Million Per Child They Have Together Due to Crazy Prenup…#URL#”
“RT #USER#: Sure would be an interesting day to read a book that examines Trump’s obsession with the king-like powers of his offic…” |  “RT #USER# #USER# When Obama was tapping my phones in October, just prior to Election!”
“A Data-Driven Approach Aims to Help Cities Recover After Earthquakes #URL#” |  “Why Trump lies, and why you should care - The Boston Globe #URL#”
“Javier Cámara ya es el líder más valorado de los españoles por delante de Pedro Sánchez, según una encuesta #URL# #URL#” |  “Dictadura pura y dura toma tasas y todos felicices #URL#”
“Me gusta la foto. Una foto con variedad, diversidad. Me da la impresion que con más sonrisas que otras. #URL#” |  “GANAR DINERO AHORA ES FACIL – Google te paga 15 dólares por contestar encuestas #URL# #URL#”
“Navidad en RD: son 3 días gozando, luego 362 llorando y deseando mal a los demás. Dejen su hipocresía !!” |  “Ortega Smith: ‘VOX expulsará de España a todos los inmigrantes ilegales’ #URL#”

As can be seen in Table 1, the Twitter specific tokens hashtags, URLs and user
mentions were replaced by the providers with the following placeholders:
_#HASHTAG#_ , _#URL#_ and _#USER#_. Prior to the feature engineering, we
analyzed the distribution of different tokens. Additionally, we determined the
sentiment of each tweet (positive, negative, or neutral) using _TextBlob_
222https://textblob.readthedocs.io/en/dev. For recognizing the named entities
(NER), we used the Python library _spaCy_. Table 2 shows some key insights for
both languages.

Table 2: Feature distribution of the fake news (Fake) and true news (True) spreaders | English | Spanish
---|---|---
Features |  True |  Fake |  True |  Fake
Unique Tokens |  24,050 |  23,809 |  32,802 |  27,932
Emojis Total |  1,614 |  522 |  3,867 |  1,629
Emojis Unique |  325 |  145 |  603 |  301
Neutral Tweets |  6,857 |  7,061 |  14,228 |  14,261
Positive Tweets |  6,173 |  5,464 |  571 |  488
Negative Tweets |  1,970 |  2,475 |  201 |  251
Uppercased Tokens Total |  38,519 |  32,467 |  36,388 |  30,177
Uppercased Phrases Total |  861 |  1,019 |  406 |  953
#URL# Token |  16,565 |  17,018 |  10,887 |  13,900
#HASHTAG# Token |  6,739 |  4,715 |  5,905 |  1,580
#USER# Token |  5,628 |  2,279 |  10,668 |  5,949
Retweets (RT) |  2,383 |  1,158 |  4,289 |  1,977
NER ORG |  8,340 |  7,299 |  2,617 |  2,595
NER PERSON |  7,742 |  9,801 |  4,845 |  5,573
NER LOC |  188 |  222 |  5,337 |  5,214

The observations of the corpus content were the following:

  * •

Fake news spreaders:

    * –

mention other Twitter users less often (_#USER#_ 333e.g. “@Username”).

    * –

utilize fewer hashtags (#HASHTAG#).

    * –

re-post fewer tweets (RT).

    * –

share slightly more URLs (#URL#).

  * •

Spanish speaking authors use more emojis than English speaking Twitter users.

  * •

Half of the English tweets are based on factual information and most of the
Spanish tweets (90%) are free of emotions.

  * •

Fake news tend to be more often negative.

  * •

Tweets of true news spreaders tend to be more often positive.

  * •

By counting the named entities no significant difference between the classes
could be established.

  * •

Fake news spreaders tend to tweet slightly more often about other people.

  * •

Uppercased tokens are shared equally by true news and fake news spreaders.

  * •

Spanish fake news spreaders make more often use of capitalized phrases.

##  2 Preprocessing and Feature Extraction

The preprocessing pipeline was performed for both languages (EN and ES)
basically. The steps for cleaning and structuring the data were performed as
follows:

  1. 1.

First, we extracted the text from the original XML document of each user and
concatenated all 100 tweets to a single text.

  2. 2.

White space between tokens were normalized to a single space.

  3. 3.

URLs, hashtags and user mentions were left untouched as they are already
replaced by placeholders by default.

  4. 4.

Numbers and emojis were replaced by the placeholders #NUMBER# and #EMOJI#.

  5. 5.

Irrelevant signs, e.g. “+,*,/,” were deleted.

  6. 6.

Sequences of repeated characters with a length greater than three were
normalized to a maximum of two letters (e.g. “LOOOOOOOOL” to “LOOL”).

  7. 7.

Words with less than three characters were ignored.

  8. 8.

Stopwords were deleted by using the NLTK (Natural Language Toolkit)
library444https://www.nltk.org/ for each language separately.

  9. 9.

From the NLTK library we additionally used the TwitterTokenizer to tokenize
the words. The tokenizer is suitable for Twitter and other casual speech that
is often used in social networks. Additionally, TwitterTokenizer contains
different regularization and normalization features. We made use of the
lowercaser.

After the Twitter texts were preprocessed, we tested different vectorization
techniques with manual hyperparameter tuning, and by employing scikit-learn’s
grid search function. The hyperparameters were tuned separately for English
and Spanish, but the features we used were mainly language-independent which
means that the same set of features can be used in multi-language domains. The
selected features were presented in Section 1 (e.g. counts of tokens or named
entities). The only language dependant feature we experimented with was the
sentiment polarity calculated separately for every tweet (whether it is
positive, negative, or neutral). Besides the handcrafted features, we also
experimented with automatically learned features i.e. term frequency
distribution (tf) and character and word $n$-grams. Additionally, we made use
of _Feature Union_ 555https://scikit-
learn.org/stable/modules/generated/sklearn.pipeline.FeatureUnion.html to
experiment with feature concatenation. To convert the tokens to a numerical
matrix in order to build a vector for each language, we made use of:

  * (1)

Scikit-learn’s term frequency-inverse document frequency (TF-IDF)

  * (2)

_GloVe_ 666https://nlp.stanford.edu/projects/glove (Global Vectors for Word
Representation) word vectors pre-trained on Twitter data as well as custom
trained _word2vec_ 777https://radimrehurek.com/gensim/models/word2vec.html
word embeddings

  * (3)

Scikit-learn’s Count Vectorizer

All tested features and their representations are summarized in Table 3.

Table 3: Features, vectorization techniques and model hyperparameters used for training purposes Features |  Vectorizer |  Hyperparameters / ranges
---|---|---
Tokens |  Word Embeddings |  n-gram_range: $[1;3]$,$[2;7]$,$[3;7]$
Token $n$-grams |  TF-IDF |  min_df: 1,2,3
Character $n$-grams |  Count Vectorizer |  max_features: $[1,000;50,000]$

##  3 Methodology

We defined the author profiling task as a binary problem predicting whether a
tweet was composed by a fake news spreader or a reliable Twitter user. For
each language (EN and ES) a separate classification model was trained. As
mentioned before, for training and testing, we split the data in the ratio
70/30. We tested different features, vectorization techniques and
dimensionality sizes in combination with a Support Vector Machine (SVM) and
Logistic Regression of which we report the best performed ones. For the final
SVM, we used a linear kernel with default hyperparameter
values888https://scikit-learn.org/stable/modules/generated/sklearn.svm.
LinearSVC.html. Logistic Regression was also trained by utilizing default
hyperparameters999https://scikit-
learn.org/stable/modules/generated/sklearn.linear_model.
LogisticRegression.html.

The performance of the fake news spreader author profiling task was ranked by
accuracy. Table 4 shows the scores for our final system performed on the
official PAN 2020 test set on the TIRA platform [7]. Accuracy scores were
calculated individually for each language by discriminating between the two
classes. Each model was trained on 70% of the training data. Hyperparameters
were tuned on the remaining 30% split. As the data set is hidden, the four
confusion matrix values (TP, TN, FP and FN) and other metrics like Precision
and Recall cannot be provided. Therefore, we display these classification
results and accuracy scores which we achieved on the 30% test dataset (see
Table 5). The highest accuracy in English was obtained using SVM with TF-IDF
weighted character $n$-grams with range $[1;3]$ and top 3,000 features. In
Spanish, the best results were achieved using Logistic Regression employing a
feature union of TF-IDF weighted character $n$-grams with range $[1;3]$ and
top 5,000 features and a vector consisting of character $n$-gram counts with
range $[3;7]$ and top 50,000 features. The submitted models achieve an overall
accuracy of 73% and 79% on the English and Spanish corpus, respectively.

Table 4: Accuracy (Acc.) scores of the final submitted systems on the official PAN 2020 test dataset on Tira Model | Features | Language | Acc.
---|---|---|---
SVM | TF-IDF char $n$-grams [1;3] 3,000 features | EN | 0.73
Logistic Regression |  | Feature union TF-IDF char $n$-grams [1;3]
---
5,000 features and
char $n$-gram counts [3;7] 50,000 features
ES | 0.79
Table 5: Evaluation results on the test split of the submitted systems for
every language (EN and ES) with the metrics Precision (P), Recall (R),
Accuracy (Acc.) and $F_{1}$-Score

|  |  | Confusion Matrix |  |  |  |
---|---|---|---|---|---|---|---
Model | Features | Language | TP | TN | FP | FN | P | R | $F_{1}$ | Acc.
SVM | TF-IDF char $n$-grams [1;3] 3,000 features | EN | 35 | 35 | 10 | 10 | 0.78 | 0.78 | 0.78 | 0.78
Logistic Regression |  | Feature union TF-IDF char $n$-grams [1;3]
---
5,000 features and
char $n$-gram counts [3;7] 50,000 features
ES | 42 | 36 | 9 | 3 | 0.92 | 0.80 | 0.86 | 0.87

## References

  * [1] Álvarez-Carmona, M.A., López-Monroy, A.P., Montes-y Gómez, M., Villaseñor-Pineda, L., Meza, I.: Evaluating topic-based representations for author profiling in social media. In: Montes y Gómez, M., Escalante, H.J., Segura, A., Murillo, J.d.D. (eds.) Advances in Artificial Intelligence \- IBERAMIA 2016. pp. 151–162. Springer International Publishing, Cham (2016)
  * [2] Argamon, S., Dhawle, S., Koppel, M., Pennebaker, J.W.: Lexical predictors of personality type. In: Proceedings of the Joint Annual Meeting of the Interface and the Classification Society of North America (01 2005)
  * [3] Giachanou, A., Rosso, P., Crestani, F.: Leveraging emotional signals for credibility detection. In: Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 877–880 (2019)
  * [4] Koppel, M., Schler, J.: Authorship verification as a one-class classification problem. In: Brodley, C.E. (ed.) Machine Learning, Proceedings of the Twenty-first International Conference (ICML 2004), Banff, Alberta, Canada, July 4–8, 2004. ACM International Conference Proceeding Series, vol. 69. ACM (2004), http://doi.acm.org/10.1145/1015330.1015448
  * [5] Liu, Y., Wu, Y.B.: Early detection of fake news on social media through propagation path classification with recurrent and convolutional networks. In: McIlraith, S.A., Weinberger, K.Q. (eds.) Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018. pp. 354–361. AAAI Press (2018), https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16826
  * [6] Pérez-Rosas, V., Kleinberg, B., Lefevre, A., Mihalcea, R.: Automatic detection of fake news. In: Proceedings of the 27th International Conference on Computational Linguistics. pp. 3391–3401. Association for Computational Linguistics (2018), http://aclweb.org/anthology/C18-1287
  * [7] Potthast, M., Gollub, T., Wiegmann, M., Stein, B.: TIRA Integrated Research Architecture. In: Ferro, N., Peters, C. (eds.) Information Retrieval Evaluation in a Changing World - Lessons Learned from 20 Years of CLEF. Springer (2019)
  * [8] Potthast, M., Kiesel, J., Reinartz, K., Bevendorff, J., Stein, B.: A stylometric inquiry into hyperpartisan and fake news. In: The 56th Annual Meeting of the Association for Computational Linguistics (Long Papers). Association for Computational Linguistics (2018), http://arxiv.org/abs/1702.05638
  * [9] Rangel, F., Giachanou, A., Ghanem, B., Rosso, P.: Overview of the 8th Author Profiling Task at PAN 2020: Profiling Fake News Spreaders on Twitter. In: Cappellato, L., Eickhoff, C., Ferro, N., Névéol, A. (eds.) CLEF 2020 Labs and Workshops, Notebook Papers. CEUR Workshop Proceedings (Sep 2020), CEUR-WS.org
  * [10] Rangel, F., Rosso, P., Ghanem, B., Giachanou, A.: Profiling fake news spreaders on twitter. In: PAN at CLEF 2020 Fake News Spreader Twitter Dataset. Zenodo (Feb 2020), https://doi.org/10.5281/zenodo.3692319
  * [11] Rangel, F., Rosso, P., Koppel, M., Stamatatos, E., Inches, G.: Overview of the author profiling task at pan 2013. In: CLEF Conference on Multilingual and Multimodal Information Access Evaluation. pp. 352–365. CELCT (2013)
  * [12] Russell, C.A., Miller, B.H.: Profile of a terrorist. Studies in conflict & terrorism 1(1), 17–34 (1977), https://doi.org/10.1080/10576107708435394
  * [13] Thorne, J., Vlachos, A., Christodoulopoulos, C., Mittal, A.: Fever: a large-scale dataset for fact extraction and verification. In: Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers). pp. 809–819. Association for Computational Linguistics (2018), http://aclweb.org/anthology/N18-1074
  * [14] Wang, W.Y.: Liar, liar pants on fire: A new benchmark dataset for fake news detection. In: Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers). pp. 422–426. Association for Computational Linguistics (2017)
  * [15] Zhou, X., Zafarani, R.: Network-based fake news detection: A pattern-driven approach. SIGKDD Explor. Newsl. 21(2), 48–60 (Nov 2019), https://doi.org/10.1145/3373464.3373473


XX XX XX X/X

Department: Applications Editor: Mike Potel<EMAIL_ADDRESS>
# Cartographic Design of Cultural Maps

Edyta Paulina Bogucka  Technical University of Munich  Marios Constantinides
Nokia Bell Labs, Cambridge (UK)  Luca Maria Aiello  Nokia Bell Labs, Cambridge
(UK)  Daniele Quercia  Nokia Bell Labs, Cambridge (UK)  Wonyoung So
Massachusetts Institute of Technology  Melanie Bancilhon  Washington
University in Saint Louis

(2020)

###### Abstract

Throughout history, maps have been used as a tool to explore cities. They
visualize a city’s urban fabric through its streets, buildings, and points of
interest. Besides purely navigation purposes, street names also reflect a
city’s culture through its commemorative practices. Therefore, cultural maps
that unveil socio-cultural characteristics encoded in street names could
potentially raise citizens’ historical awareness. But designing effective
cultural maps is challenging, not only due to data scarcity but also due to
the lack of effective approaches to engage citizens with data exploration. To
address these challenges, we collected a dataset of 5,000 streets across the
cities of Paris, Vienna, London, and New York, and built their cultural maps
grounded on cartographic storytelling techniques. Through data exploration
scenarios, we demonstrated how cultural maps engage users and allow them to
discover distinct patterns in the ways these cities are gender-biased,
celebrate various professions, and embrace foreign cultures.

††journal: IEEE Computer Graphics and Applications

H.2.8.c Data and knowledge visualization; O.6.1 Methods of data collection;
I.2.1.a Cartography

Introduction

The European Council defines intercultural cities as urban units with diverse
population from different nationalities, origins, languages, or religions and
beliefs [1]. It crafted strategic actions for reviewing current urban policies
of cultural inclusion. This agenda prompts cities to collect data and informal
stories on communities, develop participatory methods of citizens’ engagement,
and lead public awareness campaigns [1].

Various data collection and visualization techniques can be employed to
explore cultural diversity [2]. Among them _maps_ are widely used to make
spatial patterns of cultural production visible. The earliest examples of
cultural maps are archival administrative map series, which document
historical place naming processes [3]. Due to the developments in web mapping,
maps have become social justice tools promoting indigenous territories
(https://native-land.ca), exposing cultural diversity indices [4], or giving
voice to marginalized groups. For example, the Southern Poverty Law Center
mapped the public oppression symbols of the Civil War still present in
American street names (https://www.splcenter.org/data-projects/whose-
heritage), while the feminist association l’Escouade developed an alternative
map of Geneva to celebrate female influence through a symbolic renaming of 100
streets (https://100elles.ch). To assess cultural diversity, cities need to
first develop mechanisms to quantify their culture; a challenging task due to
official administrative data scarcity. Therefore, researchers often resort to
unconventional datasets to develop proxies that capture complex socio-cultural
characteristics. These include geo-referenced pictures [5], points of
interests [6], social media photos [2], and street names [7], to name a few.

Associating a city’s street naming system with socio-cultural dimensions
emerged in the 18th century, when street naming practices switched from
highlighting cities’ geographic features to establishing commemorative spaces
[7]. Street names were used to develop urban indicators of male predominance,
women’s societal role, religious connections [7], and biodiversity [8]. What
remains less explored, however, are comparative studies of cities. Examples in
this direction are the discovery of commemorative practices of new settlements
in Israel [9], socialistic Poland and Czechia [3]. But case-based research
lacks automated workflows and is mostly done manually by mapping communities
or by participants of thematic workshops. For example, the Open Street Maps
(OSM) mapping community Geochicas made it possible to investigate the gender
distribution of street honorees of eleven Spanish speaking cities including
Barcelona, Havana, and Mexico City
(https://geochicasosm.github.io/lascallesdelasmujeres). Overall, previous
street names studies have been limited in scale (covering one city or group of
cities in the same country), have been restricted to a single cultural
dimension, or have lacked appealing visual interfaces to raise awareness about
the commemorative practices.

While maps have been widely used as tools for cities’ exploration, they have
not yet been adopted as visual analytical tools to reason about cities’
culture and create awareness of “who” stands behind a certain street [3]. To
increase citizens’ engagement and awareness, one needs to ensure users’
emotional responses [10]. One way to achieve that, cartographers say, is
through visual storytelling [11], which aims at evoking surprise [12] and
inducing reflection [13]. Alternatives include interactive functionalities
that incorporate the audience’s voice or show the humans behind the data [14].
Current street names maps use simple thematic mapping techniques to color-code
streets based on the honoree’s mother language (http://str.sg/sgstreets),
gender (http://genderatlas.at), (https://equalstreetnames.brussels), or
occupation (https://www.zeit.de/feature/streetdirectory-streetnames-origin-
germany-infographic-english). Therefore, the main challenge of cultural
mapping that remains is how to develop a visual language that represents
intangible values encoded in the data such as a city’s global focus or gender
bias. To help meet this challenge, our work makes two main contributions:

  * •

a workflow for street names collection in the cities of Paris, Vienna, New
York, and London (§DATASET).

  * •

interactive cultural maps, grounded on cartographic techniques, which promote
historic awareness while doing so in a playful way (§Interaction capabilities
of cultural maps involve selections _(a,b,c,d)_ , map controls _(e)_ , button
for serendipitous discoveries _(f)_ , and user engagement buttons _(g,h)_.).

## DATASET

From open data sources, we collected and curated a dataset of 4,932 streets in
four cities, namely Paris, Vienna, New York, and London, which we describe
next. For each street, we gathered eight types of information (Table 1).

#### Paris

Using the SPARQL endpoint query service of Wikidata
(https://query.wikidata.org), we retrieved a total of 3,413 streets located in
Paris. Each returned street object, including the field _named after_ , which
corresponds to an eponym (e.g., event or person). We used it to filter streets
that are named after a person by only taking the eponym instances of the
_person class_. This yielded a dataset of 1,808 streets. We then crawled these
persons’ Wikipedia page and obtained each street’s: borough, honoree’s name,
gender, occupation, date of birth, date of death, and country of origin. After
further data cleaning, the final Paris dataset contains information for 1,428
honorific streets, and covers the historical period between 1202 and 2011.

#### Vienna

The ‘Vienna History Wiki’ platform (https://www.geschichtewiki.wien.gv.at)
aggregates historical knowledge about the city in a structured way (similar to
Wikipedia). We crawled the webpages containing the history of a given street,
and retrieved an initial dataset of 2,481 streets, along with the eight type
of information for each street. All German information was translated to
English using a Python _language translate_ package. After data cleaning, the
final Vienna dataset contains 1,662 streets, and covers the historical period
between 1778 and 2018.

#### London

As no curated London dataset was publicly available, we resorted to Wikipedia
entries that referred to London streets. We narrowed down the search space
using mentions that typically characterize pages about streets such as ‘named
after’, ‘honor’, and ‘celebrate’. This resulted into a dataset of 2500
streets, which were annotated along the eight types of information. Each
street was annotated by at least 2 people through a crowdsourcing task using
the Amazon Mechanical Turk platform, and we manually resolved conflicts. After
data cleaning, the resulting London dataset contains 770 streets, and covers
the historical period between 1030 and 2013.

#### New York

We obtained a curated dataset of 1,459 honoric streets from the urban planner
Gilbert Tauber (http://nycstreets.info). The dataset is aligned with the eight
types of information for each street. After data cleaning, the New York
dataset contains 1,072 streets, and covers the historical period between 1998
and 2013.

Table 1: Dataset structure. Each row corresponds to a street for which name, location, and honoree information have been collected. Field |  Description
---|---
streetname |  Name of the honorific street
district |  District that the street belongs to
denomination |  (Re)naming date of the street
honoree |  Person that the street was named after
gender |  Gender of the person
occupation |  Occupation of the person
country |  Country of origin of the person
dob |  Date of birth of the person
dod |  Date of death of the person

#### Dataset preparation

To ensure consistency across the four datasets, we utilized a unified coding
scheme for occupations. Based on the International Standard Classification of
Occupations, we mapped each occupation to any of the following 17 occupational
groups: legislators, writers, creative and performing artists, science and
engineering professionals, health associate professionals, sportsmen, social
workers, teaching professionals, businessmen, craft and related trades
workers, legal and social professionals, religion representatives, military
personnel, royals, politicians, and 9-11 Responders and Victims. Additionally,
we matched each street with its corresponding OSM shape file. To build the
cultural maps, we stored the underlying geodata in the PostgreSQL database,
and designed the interface with Mapbox GL JS library
(https://docs.mapbox.com/mapbox-gl-js/api).

Figure 1: Narrative design of cultural maps. (a) Setting a visual tone with
the animation of flying points. (b) A promise of an unusual neighbourhood walk
serves as a hook to capture audience attention. (c) The problem of street
names data as cultural indicators. (d) Cultural maps make street naming
patterns visible. (e) Final denouement with data, credit sections, and reading
materials. User advances the plot through entry points marked with the click
icon. Video available: http://social-dynamics.net/streetonomics/teaser.mp4

## CULTURAL STREET MAPS

Next we introduce the storytelling techniques used to develop cultural street
maps, explain their user interface, and provide map exploration possibilities
through a narrative walk-through.

Figure 2: Four functional regions of the user interface: group selections
(S1-S4), map controls (M1-M2), serendipitous discoveries (R), and user
engagement functionalities (E1-E2).

(a) S1: selecting a city of interest

(b) S2: changing the map’s theme

(c) S3: visualizing streets (re)named in a given period

(d) S4: visualizing streets categories by honorees

(e) M1, M2: exploring the map in-depth

(f) R: focusing on a random street

(g) E1: downloading a picture of the map

(h) E2: sharing insights on social media

Figure 3: Interaction capabilities of cultural maps involve selections
_(a,b,c,d)_ , map controls _(e)_ , button for serendipitous discoveries _(f)_
, and user engagement buttons _(g,h)_.

### Cartographic techniques for visual storytelling

Cultural street maps are developed using a map-based visual storytelling
conceptual framework [11], and are publicly accessible (http://social-
dynamics.net/streetonomics). They are organized into a _spatial narrative_
(plotline) and utilize _tropes_ to introduce the story.

The visualization consists of five sections, ordered in a three-arc narrative
sequence from set-up through conflict to resolution (Figure 1), to show street
names patterns in each city and between cities. The first section in the _set
up_ contains a pre-loader with a micro animation to indicate the visual tone
of the application and create suspense (Figure 1a). The second section
captures audience’s attention by a _hook_ ; a promise of an unusual
neighborhood walk (Figure 1b). The third section introduces _conflict_ and
presents the _problem context_ of street names as cultural indicators (Figure
1c). The fourth one presents cultural maps as the _resolution_ (Figure 1d).
The visualization makes the _problem context_ visible and encourages users to
explore a city. The last section includes a _denouement_ with original data,
attributions, and additional materials (Figure 1e).

To engage users in the exploration of cultural maps, we used six visual
storytelling tropes:

  1. 1.

_Pointillism_ is a _metaphorical_ impressionistic technique which applies
paint through colorful spots [15]. When such image is viewed from a distance,
dots are blended by the viewer’s eye into a comprehensible spatial pattern.
Similarly, overlapping points of single, seemingly unconnected streets form
commemorative landscapes (Figure 1d) and keep the _mood_ of suspense.

  2. 2.

_Zoomy-telling_ is our name for a visual narration technique that adjusts
visualization content depending on the selected zoom level. Cultural maps
offer different representations of data on the view levels of the city,
district and street. While looking at a city as whole, a user sees colorful,
painting-like thematic data clusters (Figure 1d, Figure 3c). When zoomed to
district level, streets turn into half-transparent lines (Figure 3d) and then
become fully opaque at street level (Figure 3e).

Figure 4: Scenarios of map-based explorations: Urban growth of Paris during
the Hausmann’s enlargement phase between 1853 (a) and 1870 (b). Cluster of
streets named after females near Seestadt Aspen (c) reflects recent Viennese
naming policies (d). Celebrating the popularity of Royals and politicians
(marked in red tones) in London (e) vs. paying tribute to artists and writers
(marked in yellow tones) in Vienna (f). Vienna is open to a variety of
nationalities (g), while Paris (h), London (i) and New York (j) are less so.

  3. 3.

_Attention_ is influenced by the use of visual hierarchy and highly contrasted
figure-ground background map. The level of detail is minimal, with district
names being the only labels available for the city’s orientation. Each
thematic layer (occupation, gender, nation of origin, historical period) is
represented using bright, vibrant colors. In doing so, similar occupations are
depicted with similar color hues (e.g., streets named after creatives are
displayed in tones of orange, while greens indicate professionals from social
and science domains). Contrary to the conventional and stereotypical pink and
blue color scheme for gender, we resorted to purples and greens as advocated
by the data visualization community [16]. Colors of the categorical labels of
origin were chosen based on the countries’ flags respectively. Finally, the
historical period layer utilizes a multi-hue sequential color scheme to map
the oldest streets in yellow and the newest ones in blue tones.

  4. 4.

In spatial narratives, both places and people can be treated as _story
characters_ [11], and that allows users to see that each street represents a
unique historical persona. Therefore, each time a user selects a street, a
styled map pop-up is displayed. The design of the pop-up takes the form of a
badge, and contains an image of the honoree, his or her date of birth, name,
and profession.

  5. 5.

The users can use the visualization to express their own _voice_ about street
names practices by downloading the maps, commenting and sharing them in social
media.

### User Interface and Interactions

Adhering to responsive design principles, the user interface is organized in
four functional regions (Figure 2): selections (S), map controls (M),
serendipitous discoveries (R), and user engagement functionalities (E). These
serve the following purposes:

  * •

Four selectors (S1-4) promote the exploration of individual streets, their
different occupational categories and other themes, and their denomination
years.

  * •

Two types of map controls (M1-2) support transitions between different levels
of detail.

  * •

One random street button (R) provides an opportunity for serendipitous
discoveries.

  * •

Two engagement buttons (E1-2) allow for map download and social media sharing.

Cultural maps facilitate an in-depth and visual exploratory analysis. In
particular, a user can:

S1

Select a city of interest (Figure 3a).

S2

Select a specific attribute (theme) of the data to be mapped such as ‘gender’
or ‘occupation’ (Figure 3b).

S3

Select a given period of time and display subset of streets that were
re(named) during that period (Figure 3c).

S4

Select theme tags to filter and visualize only a subset of streets that were
named (or renamed) after a specific group of people. For example, a user can
select tags for writers under the theme of ‘occupation’ (Figure 3d).

M1

Click on a street segment to enable a pop-up window containing information
about the street honoree (including a Wikipedia’s link) (Figure 3e).

M2

Explore the map by zooming in/out, rotating it, searching for a specific
address, and resetting the current view.

R

Serendipitous exploration by pressing the “Random street” button: the map
zooms to a randomly selected street and displays a popup window (Figure 3f).

E1

Download the currently displayed cultural map as a picture (Figure 3g).

E2

Share a cultural map on social media (Figure 3h).

### A narrative walk-through

By combining nine types of interactions users are encouraged to develop their
own data-driven questions. Next we describe the possible scenarios for a
single theme and city exploration as well as comparative analysis of cities:

  * •

_Exploration of a city’s spatial development_. Denomination dates of streets
might suggest urban growth. To visualize it, a user can select the city of
interest (S1) and map the theme of ‘historical period’ (S2). By dragging the
time slider (S3), a mesmerizing animation is revealed. This illustrates the
street network growth over the decades and centuries. As an example, consider
the effects of Haussmann’s enlargement plan for Paris between 1853 and 1870
(Figure 4a-b). Using the same time filter, a user can switch (S1) to London
and see that the British capital reached a similar city area well before the
18th century. By further switching cities and comparing the dominant street
colors helps users to place naming processes on the timeline. This is achieved
using one color, starting from the oldest ‘yellow’ London, to the ‘red’ Paris,
to the ‘purple’ Vienna to the newest ‘blue’ New York.

  * •

_Exploration of historical gender biases and modern responses to mitigate it_.
This exploration is available by selecting ‘gender’ as the map’s theme (S2),
selecting the city of interest (S1), and then the streets (re)named within a
specific time period and gender (S3, S4). For example, using the map
exploration tools (M1, M2), one could find that street naming policies in
Vienna led to the emergence of clusters of streets named after female figures
in the last decade (Figure 4c-d).  Similar newly-formed clusters are present
in south Paris (13th arrondissement) and New York (Brooklyn).

  * •

_Exploration of the rise and fall of occupations throughout history_ User
selects the city of interest (S1) and ‘occupation’ as the map’s theme (S2). By
toggling tags with specific professions (S4) one could see that numerous
London streets celebrate the members of the British royal family and
politicians, but only a few celebrate artists and writers (Figure 4e). In the
next step, one could download the resulting map (E1), change the city to
Vienna (S1), and observe that those two cities have opposite commemorative
practices (Figure 4f).  Additionally, one can observe that New York celebrates
social activists and no military professionals, while Paris commemorates
generals and soldiers from French Revolution, Napoleonic wars and both World
Wars.

  * •

_Exploration of cities’ global openness_ starts with selecting ‘nation of
origin’ as the map’s theme (S2). It continues by choosing multiple cities of
interest (S1), downloading their thematic maps (E1), and comparing the
patterns. Figure 4 shows the country of origin of the foreign street name
honorees in Vienna, Paris, London and New York. These maps confirm that, while
the commemorative landscape of Vienna reflects many nationalities from the
times of Austro-Hungarian Empire (Figure 4g), other cities are less open to
celebrating foreigners (Figure 4h-j). One could set the downloaded maps (E1)
side-by-side and share these insights on social media (E2).

## CONCLUSION

Cultural street maps visualize a city’s history encoded in its streets names
through cartographic lenses. Unlike previous interactive street names maps,
our approach offers a cartographic perspective in a three-arc narrative
structure to promote commemorative practices. Using map-based tropes such as
pointillism, zoomy-telling, attention, mood, and voice, it enables reflection
of historical processes and keeps users engaged in exploration. In the
intercultural cities context [1], our tool can encourage the general public to
explore hidden city patterns and promote historic awareness. Additionally, it
can assist policy-makers to reflect on a city’s past and steer its future
development. For example, participants of a mapping workshop in Brussels
proposed a list of future street honorees to better reflect the city’s
cultural diversity. Our tool shows that it is possible to advance such
initiatives in a productive yet playful way.

## References

  * [1] What is an intercultural city? (2020) [online] Available at: https://www.coe.int/en/web/interculturalcities [Accessed 10 Jul. 2020] (online)
  * [2] Manovich, L. The Science of Culture? Social Computing, Digital Humanities and Cultural Analytics. Journal of Cultural Analytics. 10.22148/16.004 (2016)
  * [3] David, J. Street names - between ideology and cultural heritage. Acta Onomastica. 54, 53–60 (2013)
  * [4] Cultural Mapping as Cultural Inquiry. (Routledge, 2015)
  * [5] Hristova, D., Aiello, L. & Quercia, D. The New Urban Success: How Culture Pays. Frontiers In Physics. 6 pp. 27 (201) (2018)
  * [6] Cranshaw, J., Schwartz, R., Hong, J.I., Sadeh, N.M. The Livehoods Project: Utilizing Social Media to Understand the Dynamics of a City. Information Systems: Behavioral and Social Methods eJournal. (2012)
  * [7] Oto-Peralías, D. What do street names tell us? The ’city-text’ as socio-cultural data. Journal of Economic Geography. 18, 187–211 (2018)
  * [8] Shackleton C. M. Urban street names: An opportunity to examine biocultural relationships? PloS one. 13(7), e0200891 (2018)
  * [9] Pinchevski, A., Torgovnik, E. Signifying passages: the signs of change in Israeli street names. Media, Culture and Society. 24(3), 365–-388 (2002)
  * [10] Kennedy, H., Hill, R. L. The Feeling of Numbers: Emotions in Everyday Engagements with Data and Their Visualisation. Sociology. 52(4), 830–848, (2018)
  * [11] Roth, E. R. (online preprint) Cartographic Design as Visual Storytelling: Synthesis and Review of Map-Based Narratives, Genres, and Tropes. The Cartographic Journal. Available at: https://doi.org/10.1080/00087041.2019.1633103
  * [12] Kostelnick, C. The Re-Emergence of Emotional Appeals in Interactive Data Visualization. Technical Communication. 63, 116–135 (2016)
  * [13] Vande Moere, A., Tomitsch, M., Wimmer, C., Boesch, C. & Grechenig T. Evaluating the Effect of Style in Information Visualization. IEEE Transactions on Visualization and Computer Graphics. 63, 2739–2748 (2012)
  * [14] Bach B., Stefaner M., Boy J., Drucker S., Bartram L., Wood J., Ciuccarelli P., Engelhardt Y., Köppen U., Tversky B. Narrative Design Patterns for Data-Driven Storytelling. Data-Driven Storytelling. A K Peters/CRC Press (2018)
  * [15] Mamassian, P. Ambiguities and conventions in the perception of visual art. Vision Research. 48, 2143–2153 (2008)
  * [16] D’Ignazio, C., Klein, L. F. Data Feminism. (The MIT Press, 2020)

Edyta Paulina Bogucka is a Doctoral Candidate in Cartography at the Technical
University of Munich, Germany. Her current research interests involve visual
storytelling, spatial digital humanities, and urban cartography. Contact her
at<EMAIL_ADDRESS>
Marios Constantinides is a Research Scientist in the Social Dynamics team at
Nokia Bell Labs Cambridge (UK). He is interested in human-computer
interaction, ubiquitous and affective computing. Contact him at
<EMAIL_ADDRESS>
Luca Maria Aiello is a Senior Research Scientist in the Social Dynamics team
at Nokia Bell Labs Cambridge (UK). He conducts interdisciplinary research in
network science, computational social science, and urban informatics. Contact
him at<EMAIL_ADDRESS>
Daniele Quercia is the Department Head at Nokia Bell Labs in Cambridge (UK)
and Professor of Urban Informatics at Kings College London. His research
focuses in the areas of data mining, computational social science, and urban
informatics. Contact him at<EMAIL_ADDRESS>
Wonyoung So is a Doctoral Candidate at the Massachusetts Institute of
Technology (MIT). His is interested in the bottom-up data movement, and in how
the open-source and DIY movement will affect the urban space. Contact him at
<EMAIL_ADDRESS>
Melanie Bancilhon is a Doctoral Candidate in Washington University St. Louis.
She is interested in in human-computer interaction, urban informatics and
computational social science. Contact her at<EMAIL_ADDRESS>