# FLASH-RL: Federated Learning Addressing System and Static Heterogeneity
using Reinforcement Learning

Sofiane Bouaziz1, Hadjer Benmeziane2, Youcef Imine2, Leila Hamdad1, Smail
Niar2, Hamza Ouarnoughi2  1 École nationale Supérieure d’Informatique,
Algiers, Algeria  2Univ. Polytechnique Hauts-de-France, CNRS, UMR 8201 -
LAMIH, F-59313 Valenciennes, France

###### Abstract

Federated Learning (FL) has emerged as a promising Machine Learning paradigm,
enabling multiple users to collaboratively train a shared model while
preserving their local data. To minimize computing and communication costs
associated with parameter transfer, it is common practice in FL to select a
subset of clients in each training round. This selection must consider both
system and static heterogeneity. Therefore, we propose FLASH-RL, a framework
that utilizes Double Deep Q-Learning (DDQL) to address both system and static
heterogeneity in FL. FLASH-RL introduces a new reputation-based utility
function to evaluate client contributions based on their current and past
performances. Additionally, an adapted DDQL algorithm is proposed to expedite
the learning process. Experimental results on MNIST and CIFAR-10 datasets have
shown FLASH-RL’s effectiveness in achieving a balanced trade-off between model
performance and end-to-end latency against existing solutions. Indeed, FLASH-
RL reduces latency by up to 24.83% compared to FedAVG and 24.67% compared to
FAVOR. It also reduces the training rounds by up to 60.44% compared to FedAVG
and +76% compared to FAVOR. In fall detection using the MobiAct dataset,
FLASH-RL outperforms FedAVG by up to 2.82% in model’s performance and reduces
latency by up to 34.75%. Additionally, FLASH-RL achieves the target
performance faster, with up to a 45.32% reduction in training rounds compared
to FedAVG.

###### Index Terms:

Federated Learning, Reinforcement Learning, System heterogeneity, Static
heterogeneity, Client selection.

##  I Introduction

Federated learning (FL) is a promising approach to machine learning (ML) that
allows privacy-preserving model training in heterogeneous and distributed
networks. The motivation behind FL is to make more data available to improve
day-to-day lives. It enables edge devices to collaborate in order to train a
shared ML model while maintaining control of data on the edge level. In the
context of smart homes, FL offers significant advantages where the smart homes
are equipped with various sensors that generate a wealth of data about
occupants’ activities and living environment. By applying FL in smart homes
[1], it becomes possible to develop personalized and context-aware services
while respecting privacy.

In FL, each participant (client’s device) independently performs model
training on its local data and communicates the updated model parameters to a
central server for aggregation. Existing works [2, 3, 4] mainly focus on
optimizing this aggregation to improve the performance of the global model. In
real-world scenarios such as smart homes, the number of clients is large,
making it necessary to select the appropriate subset of clients participating
in each training round. The client selection process plays a crucial role in
FL, as it impacts the convergence time, communication overhead, and overall
performance of the trained model. The shared model is then deployed at the end
of the training iterations to allow better performance on each client’s
device.

A key challenge in FL is the presence of system and static heterogeneity
across the participating clients. System heterogeneity refers to variations in
the computational capabilities and resources of the clients, such as
processing power, memory, and network connectivity. For instance, devices with
limited processing power or unstable network connections may experience delays
in completing their local training, leading to overall slower convergence of
the global model. Static heterogeneity pertains to the diversity in the number
of samples and the data characteristics across clients, including
demographics, classes or labels of interest, data distributions, and sensor
types. This diversity can have a significant impact on the performance and
generalization of the trained model.

Several works [5] have focused on performing client selection to mitigate the
effects of system and static heterogeneity. They focus on selecting the best
subset of clients that can represent the diversity of the entire client
population while also considering their computational capabilities. However,
these works typically address either system or static heterogeneity
separately, lacking simultaneous handling of both aspects.

This paper introduces a novel and efficient FL client selection strategy using
reinforcement learning (RL). Our approach addresses the challenges of system
and static heterogeneity by considering the computational capabilities of
clients, such as processing power and network connectivity, along with their
data characteristics.

The contributions presented in this paper are as follows:

  * •

We define a reputation-based utility function that assesses the performance of
each client’s local model during training and the latency incurred in training
its model with its own data. This function serves as the basis for the reward
function, which is optimized using our RL agent. Incorporating the reputation
improves the quality and reliability of the selected clients, striking a
favorable balance between maximizing the global model performance and
minimizing the overall training latency.

  * •

We design double deep Q-learning (DDQL) and multi-action selection-based RL
algorithms to perform the client’s selection during the FL process.

  * •

We apply our approach in a real-world use-case which is fall detection in
smart homes.

The rest of the paper is organized as follows. Section II provides an overview
of the FL process and discusses related works. Section III-A explains how
latency is computed in FL training rounds. In Section III-B, we define the
reputation-based utility function for scoring the client’s local performance.
We then give an overview of the client’s selection process and describe our RL
agent in Section III-C Finally, Section IV outlines the experimental
methodology and presents the results.

##  II Background & Related Works

This section provides a background on FL and the heterogeneity problem. A
literature on RL-based approaches and the fall detection use-case review is
presented as well.

###  II-A Federated Learning Problem Formulation

In FL [6], we assume the existence of $N$ clients
$\left\\{P_{i}\right\\}_{i=1}^{N}$ with their own datasets
$\left\\{D_{i}\right\\}_{i=1}^{N}$. The aim of FL is to train a global model
without having to expose local client data. Thus, for each client $k$, a local
ML model is trained to minimize its objective function, denoted $F_{k}$, and
is defined in 1.

$F_{k}(w)=\frac{1}{n_{K}}\sum_{i\in D_{k}}l\left(x_{i},y_{i};w_{k}\right)$ (1)

where $n_{k}=|D_{k}|$ represents the number of training data provided by
client $k$, and $l\left(x_{i},y_{i};w_{k}\right)$ corresponds to the loss
function of the prediction on the data sample $(x_{i},y_{i})$ using the local
model parameters of client $k$, denoted $w_{k}$. The FL optimization problem
is described as follows in Equation 2.

$\min_{w\in R^{d}}\phi(w)=\sum_{k=1}^{N}p_{k}F_{k}(w)$ (2)

where $p_{k}>0$ and $\sum_{i=1}^{N}p_{k}=1$.

At each communication round, the server sends its model parameters to the
clients, who in turn train their local models. The clients then send their
local parameters back to the server for aggregation. Nevertheless, if the
server selects all the clients at the same time, it overloads the network and
incurs excessive computation and communication costs. Thus, only a subset of
the clients are selected to participate in the training.

###  II-B Static and System Heterogeneity

The client selection needs to account for FL heterogeneity problems [7]:

  * •

Static heterogeneity: Client data is often distributed non-identically and
non-independently (non-IID), resulting in heterogeneous data distribution and
unbalanced learning between clients. For example, countries in the southern
hemisphere may have higher rates of skin cancer patients than their
counterparts in the northern hemisphere, leading to variations in disease
distribution between them.

  * •

System heterogeneity: The storage, computing, and communication capacities of
each client may differ due to the variability of hardware, and network
connectivity. This leads to variability in the transfer time of client
parameters. To tackle this issue, latency has garnered significant attention
within the FL domain, resulting in several works targeting its minimization
[8, 9].

Even though existing FL algorithms [6, 10] achieve good performances, they
remain unstable in highly heterogeneous environments.

In [11], they proposed Astraeaa, a self-balancing FL framework to mitigate
imbalances in data samples. However, it only addresses one type of static
heterogeneity and does not account for system heterogeneity. In contrast,[12]
introduced FedNorm as a framework that handles both static and system
heterogeneity in FL. Although, their approach remains static and lacks the
incorporation of intelligent algorithms.

###  II-C Reinforcement Learning-based Solutions

The use of RL for client selection in FL has shown great potential in recent
works [13, 14, 15, 16]. The latter proposes an optimization framework that
enables adaptive client selection by considering various factors, such as data
distribution and hardware resources. This enables the client selection
strategy to adapt to changes in federated environment, improving the
performance and efficiency of the global model.

Table LABEL:tab:FLalgocomparative presents a comparative study of RL-based
client selection approaches organized by the used RL algorithm, their ability
to incorporate static and system heterogeneity, and the number of RL agents
involved.

TABLE I: Comparison of state-of-the-art RL client selection. Approach | Algorithm | Static | System | Number
---|---|---|---|---
|  | heterogeneity | heterogeneity | of agents
[13] | DDQL | ✓ | x | $1$
[14] | DDQL | x | ✓ | $1$
[15] | DDQL | x | ✓ | $1$
[16] | MARL | ✓ | ✓ | $N$

In [13], the authors introduce FAVOR, an experience-based control framework
that leverages the DDQL algorithm for client selection considering static
heterogeneity. However, the training of the DDQL model relies on a single
client, which may impede rapid convergence of the agent. Similarly, [14] and
[15] use DDQL in client selection, with a focus on addressing system
heterogeneity. Notably, the distinctive aspect of [14] lies in its
consideration of a variable number of clients. In [16], a multi-agent RL
(MARL) system was introduced to address both system and static heterogeneity
in client selection. This approach employed a one-to-one correspondence
between the number of agents in the system and the number of clients. However,
using multiple agents results in additional resource demands, making it a
resource-intensive solution.

###  II-D Fall Detection Use-case

Fall detection is a classification method used to distinguish between regular
human activities and instances of falling. Temporal data captured by wearable
sensors, including accelerometer, gyroscope, and magnetometer, are used to
detect falls using either threshold-based or ML-based methods. The wearable
sensors are commonly deployed in smart home environments. However, accessing
the data generated by them can pose confidentiality challenges.

In centralized solutions, [17] proposes to use Long Short-Term Memory neural
network to develop an algorithm for distinguishing Activities of Daily Living
(ADL). In [18], the authors proposed the application of ensemble methods to
classify temporal data from accelerometers as ADL or fall.

FL-based solutions feature the work of [19] that presents FedHome, a cloud-
based FL framework designed for personalized in-home health monitoring. Their
approach primarily focuses on model size reduction and enhancing performances
across clients. Our work focuses on optimizing the client selection process
using an RL-based methodology.

##  III Proposed Approach

In this section, we describe the objective functions employed to account for
system and static heterogeneity. Subsequently, we propose a DDQL-based
solution that incorporates them into the reward function to determine the best
clients to select during each training round.

###  III-A Handling System Heterogeneity: Latency

It is crucial to account for the varying computational capabilities and
connectivity conditions among the clients. In this work, we consider latency
as the objective function to handle system heterogeneity. Minimizing latency
involves optimizing the time it takes for data to be transmitted, processed,
and returned to the clients during the FL process.

We define the latency of a selected client $k$ during training round $t$ as
the sum of its local computing time, denoted as $T_{t}^{\text{local}_{k}}$ and
its transmission time, denoted $T_{t}^{\text{transmission}_{k}}$, formulated
in Equation 3.

$l_{t}^{k}=T_{t}^{\text{local}_{k}}+T_{t}^{\text{transmission}_{k}}$ (3)

####  III-A1 Local computing time

It corresponds to the computation time required for a local iteration of the
gradient descent method. To estimate this time, we rely on the available
computing resources of each client $k$, specifically its CPU frequency
$f_{t,k}$ during training round $t$, the number of cores in its processor
$c_{k}$ and the number of CPU cycles required to train one bit of data
$g_{k}$. The formula for calculating the local training time of a client $k$
at training round $t$ is described in Equation 4.

$T_{t}^{\text{local}_{k}}=\frac{|D_{t,k}|g_{k}}{c_{k}f_{t,k}}$ (4)

where $|D_{t,k}|$ represents the size of the local data in bits held by the
client $k$ at training round $t$.

####  III-A2 Transmission time

It represents the duration needed to transfer the local model parameters from
the client to the server. To compute this time, we use the bandwidth of client
$k$ at training round $t$, denoted $b_{t,k}$. The formula for calculating the
transmission time of client $k$ at training round $t$ is defined in Equation
5.

$T_{t}^{\text{transmission}_{k}}=\frac{\sigma(m_{k})}{b_{t,k}}$ (5)

where $\sigma(m_{k})$ represents the size of the local model $m$ maintained by
the client $k$.

###  III-B Handling Static Heterogeneity: Reputation and Utility

To mitigate the effects of static heterogeneity in FL, it is crucial to
establish a scoring mechanism to evaluate the contributions of participating
clients during each training round.

####  III-B1 Reputation-based function

More recently, researchers have extensively explored the adoption of
reputation in client selection systems within the realm of FL [20].

We formulate a reputation-based function as in Equation 6. In which,
$A_{t}^{k}$ represents the accuracy of user $k$’s local model at training
round $t$, while $A_{t-1}$ denotes the accuracy of the global model at the
previous training round. This equation, denoted as $\Psi$, is formulated as a
recursive function that considers the client’s historical contributions.

Our function addresses the limitation of RFFL [20] by including the client’s
past performance in reputation calculation, avoiding potential issues. This
approach considers past contributions for a fairer and more comprehensive
evaluation of client performance, overcoming the problem of oscillations in
the model’s performance.

$\Psi_{t}^{k}=\lambda\left(A_{t}^{k}-A_{t-1}\right)+(1-\lambda){\Psi}{}_{t-1}^{k}$
(6)

The equation consists of two terms. The first term prioritizes clients whose
local models achieve higher accuracy than the previous global model. The
second term considers a client’s past contributions, reflecting its historical
performance compared to the old global model. The hyperparameter $\lambda$
adjusts the balance between current and past contributions.

However, it is important to acknowledge that a significant drawback of this
approach is the extensive runtime required for calculating the accuracy of
each selected client during every training round according to the validation
set. To address this challenge, we introduce a function called the utility
function, which allows us to overcome this computational burden.

####  III-B2 Utility function

The utility function denoted $\zeta$, serves as a measure of the relevance of
a client’s local update to the global model. Similar to the reputation-based
function, the utility function has also been employed for the selection of the
most pertinent clients to participate in the training round [21]. Our utility
function is based on normalized model divergence [5] which quantifies the
average difference between the model weights of client $k$ and the global
model during training round $t$, and is defined in Equation 7.

$d(w_{t}^{k},w_{t})=\frac{1}{|w_{t}|}\sum_{j=1}^{|w_{t}|}\left|\frac{w_{t}^{k,j}-w_{t}^{j}}{w_{t}^{j}}\right|$
(7)

where $w_{t}$ represents the weights of a model during training round $t$, and
$w_{t}^{k,j}$ and $w_{t}^{j}$ is the $j$-th model weight of client $k$ and the
global model at training round $t$, respectively.

This equation assumes that if the normalized model divergence is small, the
local update from a client is considered insignificant, resulting in a small
value. However, this assumption does not always hold true. In cases where the
performance of our global model has improved, it implies that clients who have
contributed the most to this convergence, i.e., having a minimum distance from
the global weight, are actually more significant and should be assigned a
higher utility value. This intuition stems from the aggregation process, where
the local model parameters of selected clients are combined through a weighted
sum. Clients with the smallest distance between their local and global model
weights following the aggregation process are the ones who have made the most
significant contributions during that specific training round. These clients
have exerted the greatest influence on the performance of the global model. In
this manner, we define our utility function in Equation 8. $P$ represents the
performance measure used in our study, such as accuracy and F1 score.

$\zeta_{t}^{k}=\begin{cases}e^{-|d(w_{t}^{k},w_{t})|},&\text{if
}P_{t}>P_{t-1}\\\ 1-e^{-|d(w_{t}^{k},w_{t})|},&\text{if }P_{t}\leq
P_{t-1}\end{cases}$ (8)

Our utility function is defined in two cases. The first case corresponds to an
improvement in the global model performance, in which we aim to give a high
score to clients whose distances between the parameters of their local model
and those of the global model are minimal. To achieve this, we use the
function $f(x)=e^{-|x|}$, where $x=d(w_{t}^{k},w_{t})$. This function assigns
a score close to $1$ for values of $x$ that are near $0$, indicating a high
utility. Figure 1 illustrates the shape of this function.

The second case represents a deterioration in the global model performance, in
which we intend to assign a low score to clients whose distances between the
parameters of their local model and those of the global model are minimal. To
accomplish this, we utilize the function $g(x)=1-e^{-|x|}$, where
$x=d(w_{t}^{k},w_{t})$. This function assigns a score close to $0$ for values
of $x$ that are in proximity to $0$. Figure 1 visually depicts the shape of
this function.

Figure 1: Plot of the two mathematical functions used in our proposed utility
function.

####  III-B3 Reputation-based utility function

To capitalize on the advantages offered by both the reputation and the utility
functions, we present a hybridization approach, which is our complete client
scoring function. We define this function in Equation 9.

$\Psi_{t}^{k}=\lambda\zeta_{t}^{k}+(1-\lambda){\Psi}{}_{t-1}^{k}$ (9)

To account for both static and system heterogeneity, we propose a
reformulation of the reputation-based utility function described in 10.

$\Psi_{t}^{k}=\lambda(\alpha_{1}\zeta_{t}^{k}-\alpha_{2}l_{t}^{k})+(1-\lambda){\Psi}{}_{t-1}^{k}$
(10)

where $l_{t}^{k}$ represents the latency of client $k$ at training round $t$.
The inclusion of a negative sign in front of latency in this function serves
to guide our RL agent to the minimization of latency. $\alpha_{1}$ and
$\alpha_{2}$ respectively denote the importance assigned to performance
maximization and latency minimization.To ensure a mathematically meaningful
relationship, we apply Min-Max normalization to the latency value, which
allows us to scale it within a range of $[0,1]$.

###  III-C DDQL based client selection

Figure 2: Overview of FLASH-RL methodology. 1- The server sends its current
state to the RL agent, 2- The agent sends an action vector to the environment,
3- Client selection based on the action vector, 4- Client local training, 5-
Local parameters aggregation, 6- Storage of the current transisition, 7-
Random sampling from the replay memory to train our DDRL model, 8- The agent
respectively sends the current state and the next state to the main and target
networks, 9-The agent calculates the loss using the Q values received from the
two networks and the reward, 10-The agent updates the main network parameters
using the calculated loss value, 11-If $P$ steps have been completed, the
agent transfers the local parameters of the main network to the target
network.

The overall FLASH-RL process is described in detail in Figure 2. Details of
each step are described below.

####  III-C1 Markov decision process formulation

To apply RL to a particular process, it’s crucial to formalize it as a Markov
decision process. Our formulation includes the key elements: state space,
action space, and reward function.

  1. 1.

State: We introduce a vector representation of the state at each training
round $t$, described in Equation 11.

$s_{t}=\left(s_{t}^{1},s_{t}^{2},\ldots,s_{t}^{N}\right)$ (11)

where $s_{k}$ represents the state of client $k$ at training round $t$ and is
defined in Equation 12.

$s_{t}^{k}=\left(w_{t}^{k},n_{t}^{k},c_{k},f_{t,k},b_{t,k}\right)$ (12)

where $w_{t}^{k},n_{t}^{k},c_{k},f_{t,k},b_{t,k}$ represent respectively the
model weights of client $k$, the amount of data held by client $k$, the number
of cores of client $k$’s processor, the CPU frequency and the bandwidth at
training round $t$. However, using each client’s weight vector directly to
train our RL agent’s model would be impractical due to its large size.
Therefore, we apply the PCA technique to reduce the dimensionality of the
weight vector [13].

  2. 2.

Action: The action is represented by a vector of $N$ booleans, where each
component corresponds to the selection status of a specific client. If the
$k$-th component equals $1$, client $k$ has been selected. This representation
is detailed in Equation 13.

$a_{t}=\\{i\\}\times N,\text{ where }i\in\\{0,1\\}$ (13)

However, if we have to select a subset of size $U$ at each training round,
adopting the above representation would result in a number of combinations of
size $C_{N}^{U}$. Such a large action space would raise computational problems
and could adversely affect the performance of our RL agent. To solve this
problem, we use multi-action RL explained in Section III-C2.

  3. 3.

Reward: The reward is represented by a vector of length $U$, representing the
number of clients selected in each training round.

$r_{t}=\left(r_{t}^{1},r_{t}^{2},\ldots,r_{t}^{U}\right)$ (14)

Every element within this vector, $r_{t}^{k}$, corresponds to the reward
assigned to client $k$ during training round $t$. Thus, $r_{t}^{k}$ equals
$\Psi_{t}^{k}$.

####  III-C2 Double Deep Q-learning Adaptation

To solve the computational and memory problems associated with using all
possible subsets of clients as actions, we propose a modification to the RL
algorithm. Our adapted RL approach enables the selection and learning of
several actions simultaneously, a concept known as multi-action selection in
RL. Instead of considering all possible subsets, we generate a space of $N$
actions representing all clients. Subsequently, we introduce $Q(s_{t},a_{k})$,
which represents the selection value of client $k$ in state $s_{t}$. To select
the $U$ best clients, we consider the $U$ actions with the highest Q value.
Initially, we encourage exploration using $\epsilon$-greedy and gradually
shift to exploitation by reducing the $\epsilon$ value over training rounds.

In this work, we used the DDQL algorithm [22]. Our DDQL agent consists of two
neural networks: the main and target network. The main network is used for
training, while the target network evaluates the actions of the next state and
is updated periodically every $P$ step. Additionally, our DDQL agent
incorporates a replay memory mechanism to break the correlation between
consecutive experiences $(s_{i},a_{i},s_{i+1},r_{i+1},d_{i})$ and
$(s_{i+1},a_{i+1},s_{i+2},r_{i+2},d_{i+1})$, where $d_{i}$ represents a
Boolean value to indicate whether or not the final state has been reached.

The RL learning problem can be framed as minimizing the Mean Squared Error
loss (MSE) between the target and the approximated values, which is expressed
as in Equation 15.

$L_{t}^{k}\left(\boldsymbol{\theta}_{t}\right)=\left(Y_{t}^{k}-Q\left(\boldsymbol{s}_{t},a_{k};\boldsymbol{\theta}_{t}\right)\right)^{2}$
(15)

where $Y_{t}^{k}$ t is the target value at round $t$ for action $a_{k}$ and is
defined in Equation 16.

$Y_{t}^{k}=r_{t}^{k}+\gamma
Q\left(\boldsymbol{s}_{t},\operatorname{argmax}Q\left(\boldsymbol{s}_{t},a_{i};\boldsymbol{\theta}_{t}\right);\boldsymbol{\theta}^{\prime}{}_{t}\right)$
(16)

where $r_{t}^{k}$ is the reward associated with the selection of client $k$,
$\theta$ and ${\theta}^{\prime}$ denotes respectively the parameters of the
main and target network, and $\gamma$, represents the discount rate, with
$0\leq\gamma\leq 1$, indicating the value assigned to future rewards.

This loss is computed for each selected client during training round $t$.
Rather than formulating the problem as the traditional RL problem of finding
the optimal action for a given state, our focus is on identifying the top $U$
actions that correspond to the most suitable clients.

##  IV Evaluation Methodology and Results

In this section, we present the evaluation of our proposed approach using
three benchmark datasets: MNIST, CIFAR-10 [23], and MobiACT [24] for Fall
Detection. We compare our approach with existing methods, namely FedAVG [6],
and FAVOR [13] to assess its effectiveness and performance.

###  IV-A Experimental Methodology

##### Dataset Description

In these experiments, we consider three datasets:

  * •

MNIST: a collection of handwritten digits used for image classification tasks.
It includes 60,000 training images and 10,000 test imagess. We train a CNN
model with two 5x5 convolution layers. The first layer has 20 output channels,
and the second layer has 50. Both layers are followed by 2x2 max pooling.

  * •

CIFAR-10: consists of 60,000 colored images divided into 10 classes, with
6,000 images per class. We train a CNN model with two 5x5 convolution layers.
The first and second layer has 6 and 16 channels respectively. Both layers are
followed by 2x2 max pooling.

  * •

MobiAct: designed for activity recognition and fall detection. It includes
smartphone data collected during various activities, including different types
of falls. The dataset comprises 4 types of falls and 12 activities of daily
life (ADL). It involves data from 67 volunteers with over 3,200 tests
conducted. The dataset captures heterogeneity in terms of gender, age, height,
weight, and physical status, contributing to overall heterogeneity bias. For
this dataset, we train a two-layer Gated Recurrent Unit model, with each layer
consisting of 256 hidden units.

##### Non-iid data division

To address the issue of heterogeneity in FL, we focused on non-iid data, which
is known to be one of its primary sources. We carefully partitioned our
datasets to create subsets that exhibit non-iid distribution.

To divide MNIST and CIFAR-10 datasets, we used the FedLab framework [25],
which offers various types of data partitioning strategies. For MNIST, we
employed the noniid-label partitioning, assigning each client data from only
two labels with a variable number of data items. Additionally, we used the
Hetero Dirichlet partition with $\alpha$ values of $0.5$ and $0.8$. For
CIFAR-10, we adopted the shards partitioning, which assigns each client data
associated with only two labels, with an equal number of data samples per
client. Similarly, we employed the Hetero Dirichlet partition with $\alpha$
values of $0.5$ and $0.8$.

Regarding the MobiAct dataset, it poses some challenges in terms of non-iid
data divisions due to its nature as time series data. We propose three
divisions that will serve as test benchmarks for our solution. In all of these
divisions, we have extracted 17 volunteers to form our test set, while the
remaining volunteers will be divided among the clients.

  * •

Volunteer-based division: Each volunteer in the MobiAct dataset is treated as
an individual client residing in their respective smart home, resulting in
inherent non-iid division due to their unique behaviors and characteristics.

  * •

Label skew 8: Each volunteer is treated as a separate client residing in their
own smart home. They are assigned 8 activities that differ from those assigned
to other clients. This introduces another form of non-iid data distribution
known as label skew.

  * •

Label skew 4: Similar to label skew 8, but each client is assigned exactly 4
activities instead of 8.

##### Heterogeneous Hardware settings

To create a heterogeneous FL environment in terms of system capacity, we
introduced variations in the edge equipment and transfer protocols, which are
described in table LABEL:tab:edgeeqipement and LABEL:tab:transferspec. These
values are set to simulate various edge platforms inspired by: Intel Core i3,
i5, i7, first-generation TPU, raspberry PI3, Jetson Nano, Jetson TX2, Jetson
Xavier NX, and FPGA Xilinx ZCU102. This allowed us to mimic the diversity of
resources and communication capabilities present in real-world scenarios.

TABLE II: Edge equipment simulated specifications. Name | CPU Frequency (MHZ) | Number of Cores
---|---|---
Hardware Spec. 1 | 921 | 128
Hardware Spec. 2 | 1300 | 256
Hardware Spec. 3 | 800 | 384
Hardware Spec. 4 | 1100 | 384
Hardware Spec. 5 | 1377 | 384
Hardware Spec. 6 | 350 | 4
Hardware Spec. 7 | 1500 | 4
Hardware Spec. 8 | 700 | 1
Hardware Spec. 9 | 3950 | 2
Hardware Spec. 10 | 4300 | 4
Hardware Spec. 11 | 4400 | 4
Hardware Spec. 12 | 4400 | 8
TABLE III: Transfer protocols specifications. Name | Bandwidth (Mb/s)
---|---
Wi-Fi 1 | 6
Wi-Fi 3 | 33
Wi-Fi 4 | 336
Fast Ethernet | 100

The frequency and bandwidth values specified in the tables represent the
average between the maximum and minimum values. To simulate a realistic
scenario, with diverse workloads, we modeled each value as a normal
distribution with a variable standard deviation. In each training round, a
random value is sampled from the respective normal distribution.

##### Hypeparameter calibration

An overview of the hyperparameter values used in our study for the three
datasets (Table LABEL:tab:hyperparametere).

TABLE IV: Hypeparameter tuning. Hyperparameter | MobiACT | CIFAR10 | MNST
---|---|---|---
N (number of clients) | 50 | 100 | 100
U (size of selected clients) | 5 | 10 | 10
E (number of local epochs) | 5 | 5 | 5
B (size of batch size) | 50 | 10 | 50
Learning rate | 0.001 | 0.01 | 0.01
Momentum | 0.99 | 0.9 | 0.9
RL batch size | 50 | 50 | 50
$P$ | 10 | 10 | 10
RL learning rate | 0.01 | 0.01 | 0.01
$\gamma$ | 0.9 | 0.9 | 0.9
$\epsilon_{init}$ | 0.9 | 0.9 | 0.9
$\epsilon_{end}$ | 0.2 | 0.2 | 0.35
$\Psi_{init}$ | $1/50$ | $1/100$ | $1/100$
$\lambda$ | 0.6 | 0.6 | 0.6

###  IV-B Overall Results

Table LABEL:tab:overallresults showcases multiple tests conducted on the non-
iid divisions of CIFAR-10 and MNIST datasets. The evaluation metrics employed
include accuracy(%) and latency(s).

TABLE V: Overall results on several dataset divisions compared to FedAvg [6] and FAVOR [13]. Dataset | Division | #Training rounds | FeAvg [6] | FAVOR [13] | FLASH-RL
---|---|---|---|---|---
|  |  | Accuracy | Latency | Accuracy | Latency | Accuracy | Latency
| Hetero Dirchlet 0.8 | 300 | 52.24 | 383.43 | 51.83 | 388.36 | 54.50 | 380.45
CIFAR-10 | Hetero Dirchlet 0.5 | 300 | 50.99 | 383.92 | 52.90 | 382.85 | 52.25 | 288.59
| Shards | 300 | 47.84 | 378.61 | 50.34 | 380.59 | 51.20 | 337.86
| Hetero Dirchlet 0.8 | 100 | 99.04 | 676.89 | 99.09 | 682.22 | 99.06 | 601.07
MNIST | Hetero Dirchlet 0.5 | 100 | 98.99 | 674.13 | 99.04 | 672.77 | 98.90 | 621.06
| Non-iid label | 150 | 98.89 | 1002.57 | 99.02 | 1015.77 | 98.74 | 979.79

In the CIFAR-10 dataset, specifically in the Hetero Dirichlet 0.8 division,
our approach achieved the highest accuracy compared to FedAVG and FAVOR, with
an improvement of 2.26% and 2.67% respectively. Despite achieving this
accuracy improvement, FLASH-RL also managed to reduce latency by 0.78%
compared to FedAVG and 2.03% compared to FAVOR. For the Hetero Dirichlet 0.5
division, FLASH-RL showed a 1.26% improvement in accuracy compared to FedAVG.
Although it did not surpass FAVOR in terms of accuracy, FLASH-RL significantly
reduced latency by 24.83% and 24.67% compared to FedAVG and FAVOR
respectively. In the Shards division of the CIFAR-10 dataset, FLASH-RL showed
a 3.36% improvement in accuracy compared to FedAVG and a 0.86% improvement
compared to FAVOR. Additionally, we observed a reduction in latency by 10.76%
and 11.23% compared to FedAVG and FAVOR respectively. For MNIST, FAVOR
achieved the best accuracy results with a slight difference compared FLASH-RL.
However, our approach reduces the latency. For example, in the Hetero
Dirichlet 0.8 division, we achieved a latency reduction of 11.20% compared to
FedAVG and 12.41% compared to FAVOR.

This results highlights the effectiveness of our method in striking a
desirable balance between maximizing accuracy and minimizing latency. However,
an important consideration in FL is the convergence speed of the algorithm,
which is typically measured by the number of training rounds required to
achieve specific target performance. To assess the convergence speed of our
algorithm, we set target accuracies of 52% for CIFAR-10 Hetero Dirichlet
partition 0.8, 50.5% for CIFAR-10 Hetero Dirichlet partition 0.5, and 47% for
CIFAR-10 shards partition, and we showcase the results in Figure 3.

Figure 3: Comparison of training rounds and end-to-end latencies on CIFAR-10.

In the Hetero Dirichlet 0.8 division, FLASH-RL achieved a significant
reduction of 60.44% in the number of training rounds compared to FedAVG, and a
remarkable reduction of +76% compared to FAVOR. In the Hetero Dirichlet 0.5
division, we reduced training rounds by 28.97% compared to FedAVG. We don’t
surpass FAVOR in this division, but we have considerably reduced the end-to-
end latency, as shown in the second graph. In the shards division, FLASH-RL
achieved a reduction of 49.28% in training rounds compared to FedAVG and
26.70% compared to FAVOR.

###  IV-C Case study

We now present the results obtained on the divisions of the MobiAct dataset.
These results provide insights into the performance and efficacy of FLASH-RL
in addressing fall detection within a smart home environment. The evaluation
metrics employed include F1-score(%) and latency(s). Since FAVOR is not
specifically designed for fall detection in FL and there is no existing work
on applying client selection in this context, we use FedAVG as a baseline for
comparison.

To evaluate the convergence speed and the effectiveness of our algorithm in
selecting clients based on reputation, we visualize the F1-score and latency
across training rounds (see Figure 4).

Figure 4: General evolution of FL processes on MobiAct.

The figure illustrates the convergence behavior of our algorithm in terms of
F1-score and latency. It is evident that FLASH-RL has faster convergence
towards the F1-score targets compared to the FedAVG algorithm. For instance,
when setting the F1-score target to 95% for the label skew 8 division, FedAVG
requires 417 training rounds to reach it, while FLASH-RL achieves the same
target in only 228 training rounds, resulting in a significant reduction of
45.32% in training rounds. When setting the F1 score target at 83% for the
label skew division 4, the FedAVG algorithm requires 400 training rounds to
reach it. In contrast, FLASH-RL achieves the same target in only 86 training
rounds, resulting in a substantial reduction of 78.5% in the number of
required training rounds. Additionally, it is noteworthy that the end-to-end
latency by the FedAVG algorithm exhibits a linear trend, whereas FLASH-RL
converges towards a constant latency. This observation indicates that our
algorithm effectively identifies the best clients, striking a balance between
maximizing F1-score and minimizing latency.

##  V Conclusion

In this study, we have proposed FLASH-RL, a novel FL framework that leverages
DDQL to effectively address the challenges of system and static heterogeneity
in FL. Our approach addresses the problem of selecting the most suitable
clients for each training round, considering their performance, latency, and
past contributions. By integrating a novel reputation-based utility function
into DDQL’s reward mechanism, we have evaluated and ranked clients based on
their contributions to the FL process. Furthermore, we have proposed
enhancements to the DDQL algorithm, enabling it to make multiple action
choices simultaneously, thereby accelerating the convergence of the agent
model. FLASH-RL outperforms state-of-the-art strategies on MNIST, CIFAR-10,
and MobiAct divisions, enabling faster convergence. For instance, in CIFAR-10,
FLASH-RL reduces latency by up to 24.82% and 24.67% compared to FedAVG and
FAVOR. It also reduces training rounds by up to 60.44% compared to FedAVG and
+76% compared to FAVOR.

## References

  * [1] D. C. Nguyen, Q.-V. Pham, P. N. Pathirana, M. Ding, A. Seneviratne, Z. Lin, O. Dobre, and W.-J. Hwang, “Federated learning for smart healthcare: A survey,” _ACM Comput. Surv._ , vol. 55, no. 3, feb 2022. [Online]. Available: https://doi.org/10.1145/3501296
  * [2] S. EK, F. PORTET, P. LALANDA, and G. VEGA, “A federated learning aggregation algorithm for pervasive computing: Evaluation and comparison,” in _2021 IEEE International Conference on Pervasive Computing and Communications (PerCom)_ , 2021, pp. 1–10.
  * [3] S. Kwatra and V. Torra, “A k-anonymised federated learning framework with decision trees,” in _Data Privacy Management, Cryptocurrencies and Blockchain Technology - ESORICS International Workshops, DPM and CBT_ , ser. Lecture Notes in Computer Science, J. García-Alfaro, J. L. Muñoz-Tapia, G. Navarro-Arribas, and M. Soriano, Eds., vol. 13140, 2021, pp. 106–120.
  * [4] Y. Qin and M. Kondo, “Mlmg: Multi-local and multi-global model aggregation for federated learning,” in _2021 IEEE International Conference on Pervasive Computing and Communications Workshops and other Affiliated Events (PerCom Workshops)_ , 2021, pp. 565–571.
  * [5] L. Fu, H. Zhang, G. Gao, H. Wang, M. Zhang, and X. Liu, “Client selection in federated learning: Principles, challenges, and opportunities,” _arXiv preprint arXiv:2211.01549_ , 2022.
  * [6] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas, “Communication-Efficient Learning of Deep Networks from Decentralized Data,” in _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_. PMLR, Apr. 2017, pp. 1273–1282, iSSN: 2640-3498.
  * [7] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated Learning: Challenges, Methods, and Future Directions,” _IEEE Signal Processing Magazine_ , vol. 37, no. 3, pp. 50–60, May 2020.
  * [8] C. Liu, T. J. Chua, and J. Zhao, “Time minimization in hierarchical federated learning,” in _2022 IEEE/ACM 7th Symposium on Edge Computing (SEC)_ , 2022, pp. 96–106.
  * [9] R. Li, H. Xu, G. Zhang, Y. Chen, and X. Chen, “Latency optimization for Federated Learning over Wireless Power Transfer,” _Physical Communication_ , vol. 53, p. 101765, 2022.
  * [10] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, “Federated Optimization in Heterogeneous Networks,” _Proceedings of Machine Learning and Systems_ , vol. 2, pp. 429–450, Mar. 2020.
  * [11] M. Duan, D. Liu, X. Chen, Y. Tan, J. Ren, L. Qiao, and L. Liang, “Astraea: Self-balancing federated learning for improving classification accuracy of mobile deep learning applications,” in _37th IEEE International Conference on Computer Design, ICCD_. IEEE, 2019, pp. 246–254.
  * [12] Z. Lian, W. Liu, J. Cao, Z. Zhu, and X. Zhou, “Fednorm: An efficient federated learning framework with dual heterogeneity coexistence on edge intelligence systems,” in _IEEE 40th International Conference on Computer Design (ICCD)_ , 2022, pp. 619–626.
  * [13] H. Wang, Z. Kaplan, D. Niu, and B. Li, “Optimizing Federated Learning on Non-IID Data with Reinforcement Learning,” in _IEEE Conference on Computer Communications_ , Jul. 2020, pp. 1698–1707, iSSN: 2641-9874.
  * [14] H. Zhang, Z. Xie, R. Zarei, T. Wu, and K. Chen, “Adaptive client selection in resource-constrained federated learning systems: A deep reinforcement learning approach,” __, vol. 9, pp. 98 423–98 432, 2021.
  * [15] G. Rjoub, O. A. Wahab, J. Bentahar, R. Cohen, and A. S. Bataineh, “Trust-Augmented Deep Reinforcement Learning for Federated Learning Client Selection,” _Information Systems Frontiers: A Journal of Research and Innovation_ , pp. 1–18, Jul. 2022.
  * [16] S. Q. Zhang, J. Lin, and Q. Zhang, “A Multi-Agent Reinforcement Learning Approach for Efficient Client Selection in Federated Learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 36, Jun. 2022, pp. 9091–9099.
  * [17] I. W. W. Wisesa and G. Mahardika, “Fall detection algorithm based on accelerometer and gyroscope sensor data using recurrent neural networks,” _IOP Publishing_ , vol. 258, no. 1, p. 012035, apr 2019.
  * [18] D. C. Yacchirema, J. S. de Puga, C. E. Palau, and M. Esteve, “Fall detection system for elderly people using iot and ensemble machine learning algorithm,” _Pers. Ubiquitous Comput._ , vol. 23, no. 5-6, pp. 801–817, 2019.
  * [19] Q. Wu, X. Chen, Z. Zhou, and J. Zhang, “Fedhome: Cloud-edge based personalized federated learning for in-home health monitoring,” _IEEE Transactions on Mobile Computing_ , vol. 21, no. 8, pp. 2818–2832, 2022.
  * [20] Y. Wang and B. Kantarci, “A novel reputation-aware client selection scheme for federated learning within mobile environments,” in _IEEE 25th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD)_. IEEE, 2020, pp. 1–6.
  * [21] C. Li, X. Zeng, M. Zhang, and Z. Cao, “Pyramidfl: a fine-grained client selection framework for efficient federated learning,” in _MobiCom ’22: The 28th Annual International Conference on Mobile Computing and Networking,_. ACM, 2022, pp. 158–171.
  * [22] S. Latif, H. Cuayáhuitl, F. Pervez, F. Shamshad, H. S. Ali, and E. Cambria, “A survey on deep reinforcement learning for audio-based applications,” _Artificial Intelligence Review_ , Jul. 2022.
  * [23] A. Krizhevsky, “Learning multiple layers of features from tiny images,” __, 2009.
  * [24] G. Vavoulas, C. Chatzaki, T. Malliotakis, M. Pediaditis, and M. Tsiknakis, “The mobiact dataset: Recognition of activities of daily living using smartphones,” in _ICT4AgeingWell_ , 2016.
  * [25] D. Zeng, S. Liang, X. Hu, H. Wang, and Z. Xu, “Fedlab: A flexible federated learning framework,” _Journal of Machine Learning Research_ , vol. 24, no. 100, pp. 1–7, 2023.


[table]font=small

# The Semantic Similarity Ensemble111This article extends work presented at
the 6th International Workshop on Semantics and Conceptual Issues in
Geographical Information Systems (SeCoGIS 2012) [7]

Andrea Ballatore  School of Computer Science and Informatics, University
College Dublin, Ireland  Michela Bertolotto  School of Computer Science and
Informatics, University College Dublin, Ireland  David C. Wilson  Department
of Software and Information Systems, University of North Carolina, USA

###### Abstract

Computational measures of semantic similarity between geographic terms provide
valuable support across geographic information retrieval, data mining, and
information integration. To date, a wide variety of approaches to geo-semantic
similarity have been devised. A judgement of similarity is not intrinsically
right or wrong, but obtains a certain degree of cognitive plausibility,
depending on how closely it mimics human behaviour. Thus selecting the most
appropriate measure for a specific task is a significant challenge. To address
this issue, we make an analogy between computational similarity measures and
soliciting domain expert opinions, which incorporate a subjective set of
beliefs, perceptions, hypotheses, and epistemic biases. Following this
analogy, we define the _semantic similarity ensemble (SSE)_ as a composition
of different similarity measures, acting as a panel of experts having to reach
a decision on the semantic similarity of a set of geographic terms. The
approach is evaluated in comparison to human judgements, and results indicate
that an SSE performs better than the average of its parts. Although the best
member tends to outperform the ensemble, all ensembles outperform the average
performance of each ensemble’s member. Hence, in contexts where the best
measure is unknown, the ensemble provides a more cognitively plausible
approach.

###### keywords:

Semantic similarity ensemble; SSE; Lexical similarity; Semantic similarity;
Ensemble modelling; Geo-semantics; Expert disagreement; WordNet

##  1 Introduction

The importance of semantic similarity in geographical information science
(GIScience) is widely acknowledged [21]. As diverse information communities
generate increasingly large and complex geo-datasets, semantics play an
essential role to constrain the meaning of the terms being defined. The
automatic assessment of the semantic similarity of terms, such as _river_ and
_stream_ , enables practical applications in data mining, geographic
information retrieval, and information integration. Research in natural
language processing and computational linguistics has produced a wide variety
of approaches, classifiable as knowledge-based (structural similarity is
computed in expert-authored ontologies), corpus-based (similarity is extracted
from statistical patterns in large text corpora), or hybrid (combining
knowledge and corpus-based approaches) [29, 32]. Several similarity techniques
have been tailored specifically to geographic information [35]. In general, a
judgement on semantic similarity is not simply right or wrong, but rather
shows a certain degree of cognitive plausibility, i.e. a correlation with
human behaviour. Hence, selecting the most appropriate measure for a specific
task is non-trivial, and represents in itself a challenge.

From this perspective, a semantic similarity measure bears resemblance with a
human expert being summoned to give her opinion on a complex semantic problem.
In domains such as medicine and economic policy, critical choices have be made
in uncertain, complex scenarios. However, disagreement among experts occurs
very often, and equally credible and trustworthy experts can hold divergent
opinions about a given problem [25]. To overcome decisional deadlocks, an
effective solution consists of combining diverse opinions into a
representative average. Instead of identifying a supposedly ‘best’ expert in a
domain, an opinion is gathered from a panel of experts, extracting a
representative average from their diverging opinions [10]. Similarly, complex
computational problems in machine learning are often tackled with _ensemble
methods_ , which achieve higher accuracy by combining of heterogeneous models,
regressors, or classifiers [34]. This idea was first explored in our previous
work under the analogy of the _similarity jury_ [7].

Rather than developing a new measure for geo-semantic similarity, we explore
the idea of combining existing measures into a _semantic similarity ensemble
(SSE)_. In order to gain insight about the merits and limitations of the SSE,
we conducted a large empirical evaluation, selecting ten WordNet-based
similarity measures as a case study. The ten measures were combined into all
of the possible 1,012 ensembles, exploring the entire combinatorial space. To
measure the cognitive plausibility of each measure and ensemble, a set of 50
geographic term pairs including 97 unique terms, selected from OpenStreetMap
and ranked by 203 human subjects, was adopted as ground truth. The results of
this evaluation confirms that, in absence of knowledge about the performance
of the similarity measures, the ensemble approach tends to provide more
cognitively plausible results than any individual measure.

The remainder of this paper is organised as follows. Section 2 reviews
relevant related work in the areas of geo-semantic similarity and ensemble
methods. Section 3 describes the WordNet-based similarity measures selected as
a case study. The SSE is defined in Section 4, while Section 5 presents and
discusses the empirical evaluation. Finally, Section 6 draws conclusions about
the SSE, and indicates directions for future work.

##  2 Related work

The ability to assess similarity between stimuli is considered a central
characteristic of human psychology. Hence, it should not come as a surprise
that semantic similarity is widely studied in psychology, cognitive science,
and natural language processing. Over the past ten years, a scientific
literature on the semantic similarity has emerged in the context of GIScience
[17, 6, 3]. Schwering [35] surveyed and classified semantic similarity
techniques for geographic terms, including network-based, set-theoretical, and
geometric approaches. Notably, Rodríguez and Egenhofer [33] have developed the
Matching-Distance Similarity Measure (MDSM) by extending Tversky’s set-
theoretical similarity for geographic terms. In the area of the Semantic Web,
SIM-DL is a semantic similarity measure for spatial terms expressed in
description logic (DL) [16]. As these measures are tailored to specific
formalisms and data, we selected WordNet-based measures as a more generic case
study (see Section 3).

A key element in this article is the combination of different semantic
similarity measures, relying on the analogy between computable measures and
domain experts. The idea of combining divergent opinions is not new. Indeed,
expert disagreement is not an exceptional state of affairs, but rather the
norm in human activities characterised by uncertainty, complexity, and trade-
offs between multiple criteria [25]. As Mumpower and Stewart [26] put it, the
“character and fallibilities of the human judgement process itself lead to
persistent disagreements even among competent, honest, and disinterested
experts” (p. 191). From a psychological perspective, in cases of high
uncertainty and risk (e.g. choosing medical treatments and long term
investments), decision makers consult multiple experts, and try to obtain a
representative average of divergent expert judgements [10]. In the context of
risk analysis, mathematical and behavioural models have been devised to elicit
judgements from experts, suggesting that simple mathematical methods such as
the average perform quite well [11]. The underlying intuition has been
controversially labelled as ‘wisdom of crowds,’ and can account for the
success of some crowdsourcing applications [37].

In complex domains such as econometrics, genetics, and meteorology, _ensemble
methods_ aggregate different models of the same phenomenon, trying to overcome
the limitations of each model. In the context of machine learning, a wide
variety of ensemble methods have been devised and evaluated [34]. Such methods
aim at generating a single classifier from a set of classifiers applied to the
same problem, maximising its overall accuracy and robustness [27]. Similarly,
clustering ensembles obtain a single partitioning of a set of objects by
aggregating several partitionings returned by different clustering techniques
[36]. In computational biology, ensemble approaches are currently being used
to compute the similarity of proteins [19].

Forecasting complex phenomena can also benefit from ensemble methods.
Armstrong [2] pointed out that “combining forecasts is especially useful when
you are uncertain about the situation, uncertain about which method is most
accurate, and when you want to avoid large errors” (p. 417). Notably, a study
of the Blue Chip Economic Indicators survey indicates that forecasts issued by
a panel of seventy economists tended to outperform all the seventy individual
forecasts [9]. To date, we are not aware of studies that explores
systematically the possibility of combining semantic similarity measures
through an ensemble method. The next section describes in detail the
similarity measures that we selected as a case study.

##  3 WordNet similarity measures

In this study, we selected WordNet-based semantic similarity measures as a
case study for our ensemble technique, the semantic similarity ensemble (SSE).
In the context of natural language processing, WordNet [13] is a well-known
knowledge base for the computation of semantic similarity. Numerous knowledge-
based approaches exploit its deep taxonomic structure for nouns and verbs [22,
32, 23, 38, 8]. From a geo-semantic viewpoint, WordNet terms have been mapped
to OpenStreetMap [5]. Table 1 summarises the salient characteristics of ten
popular WordNet-based measures. In order to compute the similarity scores,
each measure adopts a different strategy. Seven measures relies on the
_shortest path_ between terms in the noun/verb taxonomy, assuming that the
number of edges is inversely proportional to the similarity of terms. This
approach is limited by the variability in the path lengths in the different
semantic areas of WordNet, determined by arbitrary choices and biases of the
knowledge base’s owners. Paths in dense, well-developed parts of the taxonomy
tend to be longer than those in shallow, sparse areas, making the direct
comparison of term pairs from different areas problematic. Missing edges
between terms make the score drop to $0$.

To overcome these limitations, three measures include the _information
content_ of the two terms and that of the _least-common subsumer_ , i.e. the
more specific term that is an ancestor to both target terms [e.g. 32]. Hence,
at the same path length, terms with a very specific subsumer (‘building’) are
considered to be more similar than terms with a generic subsumer (‘thing’).
Although this approach mitigates the issues of the shortest paths, a new issue
lies in the extraction of the information content from a text corpus. Text
corpora tend to be biased towards specific semantic fields, underestimating
the specificity of terms contained in those fields, resulting in skewed
similarity scores. An alternative approach that do not rely on taxonomy paths
consists of comparing the term _glosses_ , i.e. the lexical definition of
terms. Definitions can be compared in terms of word overlap (terms that are
defined with the same words tend to be similar), or with co-occurrence
patterns in a text corpus (terms that are defined with co-occurring words tend
to be similar) [28]. The results of this approach are sensitive to noise in
the definitions (e.g. very frequent or rare words that skew the scores), and
to the arbitrary nature of definitions, which can under- or over-specified.

Empirical research suggests that the performance of these measures largely
depends on the specific ground-truth dataset utilised in the evaluation [24].
Therefore, these measures constitute a striking example of alternative models
of the same phenomenon, none of which can be considered to be
uncontroversially better than the others. Each measure is sensitive to
specific biases in the knowledge base, and tends to reflect these biases in
the similarity scores. For this reason, we consider these measures to be a
suitable case study for the ensemble approach, formally defined in the next
section.

Name |  Reference |  Description | SPath | Gloss | InfoC
---|---|---|---|---|---
path |  Rada _et al._ [30] |  Edge count in the semantic network | $\surd$ |  |
lch |  Leacock and Chodorow [22] |  Edge count scaled by depth | $\surd$ |  |
res |  Resnik [32] |  Information content of $lcs$ | $\surd$ |  | $\surd$
jcn |  Jiang and Conrath [18] |  Information content of $lcs$ and terms | $\surd$ |  | $\surd$
lin |  Lin [23] |  Ratio of information content of $lcs$ and terms | $\surd$ |  | $\surd$
wup |  Wu and Palmer [38] |  Edge count between $lcs$ and terms | $\surd$ |  |
hso |  Hirst and St-Onge [15] |  Paths in lexical chains | $\surd$ |  |
lesk |  Banerjee and Pedersen [8] |  Extended gloss overlap |  | $\surd$ |
vector |  Patwardhan and Pedersen [28] |  Second order co-occurrence vectors |  | $\surd$ |
vectorp |  Patwardhan and Pedersen [28] |  Pairwise second order co-occurrence vectors |  | $\surd$ |
Table 1: WordNet-based similarity measures. _SPath_ : shortest path; _Gloss_ :
lexical definitions (glosses); _InfoC_ : information content; _lcs_ : least
common subsumer.

##  4 The semantic similarity ensemble (SSE)

A computable measure of semantic similarity can be seen as a human domain
expert summoned to rank pairs of terms, according to her subjective set of
beliefs, perceptions, hypotheses, and epistemic biases. When the performance
of an expert can be compared against a gold standard, it is a reasonable
policy to trust the expert showing the best performance. Unfortunately, such
gold standards are difficult to construct and validate, and the choice of most
appropriate expert remains highly problematic in many contexts. To overcome
this issue, we propose the _semantic similarity ensemble (SSE)_ , a technique
to combine different semantic similarity measures on the same set of terms.
This ensemble of measures can be intuitively seen as a jury or a panel of
human experts deliberating on a complex case [7]. Formally, the similarity
function $sim$ quantifies the semantic similarity of a pair of geographic
terms $t_{\\_}a$ and $t_{\\_}b$ ($sim(t_{\\_}a,t_{\\_}b)\in[0,1]$). Set $P$
contains all term pairs whose similarity needs to be assessed, while set $M$
contains a set of selected semantic similarity measures from which the
ensembles will be formed:

$\displaystyle P=\\{\langle t_{\\_}{a1}t_{\\_}{b1}\rangle,\langle
t_{\\_}{a2}t_{\\_}{b2}\rangle~{}\ldots~{}\langle
t_{\\_}{an}t_{\\_}{bn}\rangle\\}$ (1) $\displaystyle
M=\\{sim_{\\_}{1},sim_{\\_}{2}~{}\ldots~{}sim_{\\_}{m}\\}$

A measure $sim$ from $M$ applied to $P$ maps the set of pairs to a set of
scores $S_{\\_}{sc}$, which can then be converted into rankings $S_{\\_}{rk}$,
from the most similar (e.g. _stream_ and _river_) to the least similar (e.g.
_stream_ and _restaurant_):

$\displaystyle sim(P)\rightarrow S_{\\_}{sc}=\\{s_{\\_}1,s_{\\_}2\ldots
s_{\\_}n\\}~{}~{}~{}~{}s\in\mathbb{R}_{\\_}{\geq 0}$ (2) $\displaystyle
rank(S_{\\_}{sc})\rightarrow S_{\\_}{rk}=\\{r_{\\_}1,r_{\\_}2\ldots
r_{\\_}n\\}$

For example, a measure $sim\in M$ applied to a set of three pairs $P$ might
return $S_{\\_}{sc}=\\{.45,.13,.91\\}$, corresponding to rankings
$S_{\\_}{rk}=\\{2,3,1\\}$. The rankings $S_{\\_}{rk}(P)$ can be used to assess
the cognitive plausibility of $sim$ against a human-generated rankings $H(P)$.
The cognitive plausibility of $sim$ can be estimated with the Spearman’s
correlation $\rho\in[-1,1]$ between $S_{\\_}{rk}(P)$ and $H_{\\_}{rk}(P)$. If
$\rho$ is close to 1 or -1, $sim$ is highly plausible, while if $\rho$ is
close to 0, $sim$ shows no correlation with human behaviour.

In this context, a _semantic similarity ensemble (SSE)_ is defined as a set
$E$ of unique semantic similarity measures:

$\displaystyle
E=\\{sim_{\\_}{1},sim_{\\_}{2}~{}\ldots~{}sim_{\\_}{k}\\},~{}~{}\forall
j\in\\{1,2\ldots k\\}:sim_{\\_}j\in M$ (3) $\displaystyle\forall
i\in\\{1,2\ldots|M|-1\\}:~{}sim_{\\_}i\neq
sim_{\\_}{i+1},~{}~{}~{}~{}~{}~{}~{}k\leq m,|E|\leq|M|$

For example, considering the ten measures in Table 1, ensemble $E_{\\_}a$ has
two members $\\{jcn,lesk\\}$, while ensemble $E_{\\_}b$ has three members
$\\{jcn,res,wup\\}$.

Several techniques have been discussed to aggregate rankings, using either
unsupervised or supervised methods. Clemen and Winkler [11] stated that simple
mathematical methods, such as the average, tend to perform quite well to
combine expert judgements in risk assessment. Hence, we define two aggregation
approaches $A$ to compute the rankings of ensemble $E$:

  1. 1.

Mean of the similarity scores:
$A_{\\_}{s}=rank(mean(S_{\\_}{sc1},S_{\\_}{sc2}\ldots S_{\\_}{scn}))$

  2. 2.

Mean of the similarity rankings:
$A_{\\_}{r}=rank(mean(S_{\\_}{rk1},S_{\\_}{rk2}\ldots S_{\\_}{rkn}))$

The first approach, $A_{\\_}{s}$, combines directly the similarity scores,
while the second approach flattens the scores into equidistant rankings.
Rankings contain less information than scores: for example, scores
$\\{.01,.02,.98,.99\\}$ and $\\{.51,.52,.53,.54\\}$ have very different
distributions, but result in the same rankings $\\{1,2,3,4\\}$. For this
reason, in some cases, $A_{\\_}s\neq A_{\\_}r$. If two measures on five term
pairs generate the scores $S_{\\_}{sc1}=\\{.9,.9,.38,.44,.31\\}$ and
$S_{\\_}{sc2}=\\{.28,.47,.14,.61,.36\\}$, the resulting $A_{\\_}s$ is
$\\{4,5,1,3,2\\}$, whilst $A_{\\_}r$ is $\\{3,5,1,4,2\\}$.

A given similarity measure has a cognitive plausibility, i.e. the ability to
approximate human judgement. A traditional approach to quantify the cognitive
plausibility of a measure consists of comparing rankings against a human-
generated ground truth [14]. The ranked similarity scores are compared with
the rankings or ratings returned by human subjects on the same set of term
pairs. Following this approach, we define $\rho_{\\_}{sim}$ as the correlation
of an individual measure $sim$ (i.e. an ensemble of size one) with human-
generated rankings $H_{\\_}{rk}$, while $\rho_{\\_}{E}$ the correlation of the
judgement obtained from an ensemble $E$. When knowledge of $\rho_{\\_}{sim}$
is available for the current task, the optimal $sim\in M$ can be simply the
$sim$ having highest $\rho_{\\_}{sim}$. However, in real settings this
knowledge is often absent, or incomplete, or unreliable. The same semantic
similarity measure can obtain considerably different degrees of cognitive
plausibility based on the specific dataset in consideration. In such contexts
of limited information, the SSE offers a viable alternative to an arbitrary
selection of a $sim$ from $M$. The empirical evidence discussed in the next
section supports this claim.

##  5 Evaluation

This section discusses an empirical evaluation conducted on the SSE in real
settings. The purpose of this evaluation is to assess the performance of the
SSE in detail, highlighting strengths and weaknesses. Ten semantic similarity
measures are tested on a set of pairs of geographic terms utilised in
OpenStreetMap. A preliminary evaluation of an analogous technique on a small
scale was conducted in [7]. Ensembles of cardinalities 2,3, and 4 were
generated from eight similarity measures, for a total of 154 ensembles. The
evaluation described below is conducted on a larger scale, adopting a larger
set of geographic terms, ranked by 203 human subjects as ground truth. To
obtain a complete picture of ensemble’s performance, the entire combinatorial
space is considered, for a total of 1,012 unique ensembles. The remainder of
this section outlines the evaluation criteria by which the performance of the
SSE is assessed (Section 5.1), the human-generated ground truth (Section 5.2),
the experiment set-up (Section 5.3), and the empirical results obtained,
including a comparison with the preliminary evaluation (Section 5.4).

###  5.1 Evaluation criteria

The performance of an ensemble $E$ is measured on its cognitive plausibility
$\rho_{\\_}{E}$, with respect to the plausibility of its individual members
$\rho_{\\_}{sim}$. Intuitively, an ensemble succeeds when it provides rankings
that are more cognitively plausible than those of its members. Four criteria
are formally defined in this evaluation:

  * $-$

Total success. The plausibility of the ensemble is strictly greater than all
of its members: $\forall sim\in E:\rho_{\\_}{E}>\rho_{\\_}{sim}$

  * $-$

Partial success. The plausibility of the ensemble is strictly greater than a
member: $\exists sim\in E:\rho_{\\_}{E}>\rho_{\\_}{sim}$

  * $-$

Success over mean. The plausibility of the ensemble is strictly greater than
the mean plausibility of its members:
$\rho_{\\_}{E}>mean(\rho_{\\_}{sim_{\\_}1},\rho_{\\_}{sim_{\\_}2}\ldots\rho_{\\_}{sim_{\\_}n})$

  * $-$

Success over median. The plausibility of the ensemble is strictly greater than
the median plausibility of its members:
$\rho_{\\_}{E}>median(\rho_{\\_}{sim_{\\_}1},\rho_{\\_}{sim_{\\_}2}\ldots\rho_{\\_}{sim_{\\_}n})$

###  5.2 Ground truth

In order to assess the cognitive plausibility of the similarity measures and
the ensembles, a human-generated ground truth has to be selected. In the
preliminary evaluation described, a human-generated set of similarity rankings
was extracted from an existing dataset [7]. That dataset contains similarity
rankings of 50 term pairs, over on 29 geographic terms, originally collected
by Rodríguez and Egenhofer [33], and is available
online.222http://github.com/ucd-spatial/Datasets In order to provide a
thorough assessment of the SSE in the present article, a new and larger human-
generated dataset was adopted as ground truth.

As part of a wider study on geo-semantic similarity, we selected 50 pairs of
geographic terms commonly used in OpenStreetMap, including 97 man-made and
natural features. The terms were subsequently mapped to the corresponding
terms in WordNet, as exemplified in Table 2. A Web-based survey was
subsequently prepared on the set of 50 term pairs, asking human subjects to
rate the pairs’ similarity on a five-point Likert scale, from _very
dissimilar_ to _very similar_. In order to be understandable by any native
speaker of English, regardless of knowledge of the geographic domain, the
survey only included common and non-technical terms, aiming to collect a
generic set of geo-semantic judgements. The survey was disseminated online
through mailing lists, and obtained valid responses from 203 human subjects.
The subjects’ ratings for each pair were normalised on a $[0,1]$ interval and
averaged, obtaining human-generated similarity scores $H_{\\_}{sc}$, then
ranked as $H_{\\_}{rk}$. Table 3 outlines a sample of term pairs, with the
similarity score and ranking assigned by the 203 human subjects. This dataset
was utilised as ground truth in the experiment outlined in the next section.

Term |  OpenStreetMap tag |  WordNet synset
---|---|---
bay | natural=bay | bay#n#1
canal | waterway=canal | canal#n#3
city | place=city | city#n#1
post box | amenity=post_box | postbox#n#1
floodplain | natural=floodplain | floodplain#n#1
historic castle | historic=castle | castle#n#2
motel | tourism=motel | motel#n#1
supermarket | shop=supermarket | supermarket#n#1
… | … | …
Table 2: Sample of the 97 terms extracted from OpenStreetMap and mapped to WordNet. Term A | Term B | $~{}~{}H_{\\_}{sc}~{}~{}$ | $~{}~{}H_{\\_}{rk}~{}~{}$
---|---|---|---
motel | hotel | .90 | 1
public transport station | railway platform | .81 | 2
stadium | athletics track | .76 | 3
theatre | cinema | .87 | 4
art shop | art gallery | .75 | 5
… | … | … | …
water ski facility | office furniture shop | .05 | 46
greengrocer | aqueduct | .03 | 47
interior decoration shop | tomb | .05 | 48
political boundary | women’s clothes shop | .02 | 49
nursing home | continent | .02 | 50
Table 3: Human-generated similarity scores ($H_{\\_}{sc}$) and rankings
($H_{\\_}{rk}$) on 50 term pairs

###  5.3 Experiment setup

To explore the performance of an SSE versus individual measures, we selected a
set of ten WordNet-based similarity measures as a case study. Table 4
summarises the resources involved in this experiment. The ten similarity
measures were not applied directly to the term pairs, but they were applied to
the their lexical definitions, using a paraphrase-detection technique
[4].333The _WordNet::Similarity_ tool [29] was used to compute the similarity
scores.

10 similarity measures $sim\in M$: |  | $\\{jcn,lch,hso,lesk,lin,path,~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
---|---|---
|  |  $~{}~{}res,vector,vectorp,wup\\}$ (see Table 1)
9 ensemble cardinalities $|E|$: |  | $\\{2,3,4,5,6,7,8,9,10\\}$
Number of unique ensembles $E$: |  | {$45,120,$ $210,$ $252,$ $210,$ $120,45,9,1$}; Total: 1,012
2 types of ensembles $E$: |  |  ensemble of scores $E_{\\_}s$ and ensemble of rankings $E_{\\_}r$
Ground truth: |  | 50 term pairs ranked by
|  | 203 human subjects by semantic similarity
4 evaluation criteria: |  | (a) total success; (b) partial success;
|  | (c) success over mean; (d) success over median
Table 4: Experiment setup

In order to explore the space of all the possible ensembles, we considered the
entire range of ensemble sizes $|E|\in\\{2,3\ldots 10\\}$ for $M$. The entire
power set of $M$ was computed. Increasing the ensemble cardinality from 2 to
10, respectively $45,120,$ $210,$ $252,$ $210,$ $120,45,9,1$ ensembles were
generated, for a total 1,012 ensembles. The experiment was carried out through
the following steps:

  1. 1.

Compute $S_{\\_}{sc}$ and $S_{\\_}{rk}$ for each of the ten measures on the 50
term pairs from OpenStreetMap.

  2. 2.

Generate 1,012 ensembles, combining the measures on either similarity scores
($E_{\\_}s$) or rankings ($E_{\\_}r$).

  3. 3.

For each of the ten measures, compute the cognitive plausibility
$\rho_{\\_}{sim}$ against human-generated rankings $H_{\\_}{rk}$.

  4. 4.

For each of the 1,012 ensembles, compute the cognitive plausibility
$\rho_{\\_}E$ against $H_{\\_}{rk}$.

  5. 5.

Compute the four evaluation criteria (total success, partial success, success
over mean, success over median) for each measure and ensemble.

| $|E|$ | vector | lch | path | hso | wup | vecp | res | lesk | jcn | lin | mean
---|---|---|---|---|---|---|---|---|---|---|---|---
$\rho_{\\_}{sim}$ | $-$ | .737 | .727 | .727 | .708 | .663 | .641 | .635 | .628 | .588 | .562 | .662
Total | 2 | 33.3 | 22.2 | 22.2 | 11.1 | 22.2 | 33.3 | 22.2 | 55.6 | 11.1 | 11.1 | 24.4
success | 3 | 27.8 | 22.2 | 27.8 | 27.8 | 36.1 | 19.4 | 36.1 | 41.7 | 11.1 | 8.3 | 25.8
(%) | 4 | 11.9 | 17.9 | 16.7 | 17.9 | 22.6 | 10.7 | 23.8 | 20.2 | 6.0 | 4.8 | 15.2
| 5 | 8.7 | 11.1 | 13.5 | 11.9 | 12.7 | 7.1 | 16.7 | 12.7 | 2.4 | 2.4 | 9.9
| 6 | 8.7 | 8.7 | 7.9 | 9.5 | 6.3 | 4.0 | 9.5 | 6.3 | 0.0 | 0.8 | 6.2
| 7 | 3.6 | 4.8 | 4.8 | 4.8 | 3.6 | 3.6 | 4.8 | 3.6 | 0.0 | 0.0 | 3.3
| 8 | 2.8 | 2.8 | 2.8 | 2.8 | 2.8 | 0.0 | 2.8 | 2.8 | 0.0 | 2.8 | 2.2
| 9 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
| 10 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0 | 0.0
Mean | All | 10.8 | 10.0 | 10.6 | 9.5 | 11.8 | 8.7 | 12.9 | 15.9 | 3.4 | 3.4 | 9.7
Partial | 2 | 33.3 | 22.2 | 22.2 | 33.3 | 66.7 | 77.8 | 77.8 | 100.0 | 88.9 | 100.0 | 62.2
success | 3 | 27.8 | 25.0 | 30.6 | 58.3 | 86.1 | 94.4 | 97.2 | 97.2 | 100.0 | 100.0 | 71.7
(%) | 4 | 11.9 | 26.2 | 23.8 | 50.0 | 95.2 | 97.6 | 98.8 | 100.0 | 100.0 | 100.0 | 70.3
| 5 | 8.7 | 19.8 | 22.2 | 58.7 | 95.2 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 70.5
| 6 | 8.7 | 18.3 | 17.5 | 56.3 | 98.4 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 69.9
| 7 | 3.6 | 19.0 | 19.0 | 67.9 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 71.0
| 8 | 2.8 | 11.1 | 11.1 | 63.9 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 68.9
| 9 | 0.0 | 22.2 | 22.2 | 55.6 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 70.0
| 10 | 0.0 | 0.0 | 0.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 70.0
Mean | All | 10.8 | 18.2 | 18.7 | 60.4 | 93.5 | 96.6 | 97.1 | 99.7 | 98.8 | 100.0 | 69.4
Succ. mean | All | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0
Succ. med. | All | 96.6 | 95.6 | 96.2 | 97.9 | 99.7 | 98.9 | 99.9 | 99.7 | 97.8 | 97.1 | 98.0
Table 5: Overall results of the experiment, including cognitive plausibility
$\rho_{\\_}{sim}$, and the four evaluation criteria. _Succ. mean_ : success
over mean; _Succ. med._ : success over median. Figure 1: The four evaluation
criteria w.r.t. ensemble cardinality

###  5.4 Experiment results

The experiment was carried out on two types of ensemble, once with $A_{\\_}s$
(mean of scores), and once with $A_{\\_}r$ (mean of rankings). These two
approaches obtained very close results, with a slightly better performance for
$A_{\\_}r$, with each evaluation criterion always within a $5\%$ distance from
$A_{\\_}s$. To avoid repetition, only cases with $A_{\\_}r$ are included in
the discussion. All the cognitive plausibility correlations obtained
statistically significant results at $p<.01$. The experiment results are
summarised in Table 5, showing the cognitive plausibility of each measure, and
the four evaluation criteria across all the ensemble cardinalities. For
example, the ensembles of cardinality $2$ containing measure $wup$ obtains
partial success in $86.1\%$ of the cases. The cognitive plausibility of the
ten measures are in range $\rho\in[.562,.737]$, where $vector$ is the best
measure, and $lin$ the worst. Whilst total and partial success change
considerably and are fully reported, the success over mean and median obtain
homogenous results and only the means are included in the table. The general
trends followed by the evaluation criteria are depicted in Figure 1.

Figure 2: Ensemble total and partial success w.r.t. similarity measures $sim$

#### Total success.

The total success for the 1,012 ensembles falls in interval $[0,55.6]$
percent, with a mean of $9.7\%$. On average, small cardinalities (2 and 3)
obtain the best total success rate ($\approx 25\%$). As the cardinality
increases, the total success decreases rapidly, dropping below $10\%$ with
cardinality greater than 4. This makes sense intuitively, as the larger the
ensemble, the less likely the ensemble can outperform every single member. The
total success varies across the different measures too, falling in interval
$[3.4,15.9]$. No statistically significant correlation exists between a
measure’s cognitive plausibility and its rate of total success. In other
words, ensembles containing the best measures do not necessarily have better
or worse total success rate. Although ensembles do not tend to outperform all
of their members, the plausibility of an ensemble is never lower than that of
all of its members, $~{}\exists sim\in E:\rho_{\\_}{E}>\rho_{\\_}{sim}$.

#### Partial success.

Partial success rate is considerably greater than that of total success. Over
the entire space of ensembles, the partial success rate varies widely between
$0\%$ and $100\%$, with an global average of $\approx 70\%$. The ensembles’
cardinality has no clear impact on the mean partial success rate, which
remains in the interval $[62.2,71.7]$ both with small and large ensembles.
Unlike total success, partial success rate is affected by each measure’s
cognitive plausibility $\rho_{\\_}{sim}$. The top measures in $M$ ($vector$,
$lch$, and $path$) obtain low partial success ($<20\%$), whereas ensembles
consistently outperform the bottom measures ($100\%$).

The average partial success rates bear strong inverse correlation with the
measures’ plausibility, i.e. $\rho=-.87~{}(p<.05)$. Ensembles tend to
outperform the worst measures, and tend to be outperformed by the top
measures. The total and partial success of each measure is displayed in Figure
2. We note that the three top measures do not benefit from being aggregated
within the ensemble, whereas all the others do. While in this experiment a
ground truth is given, in many real-world settings the best measures are
unknown, and therefore the SSE constitutes a viable alternative to the
arbitrary selection of a measure. In particular, ensembles of cardinality 3
obtain optimal results over other cardinalities.

#### Success over mean and median.

Unlike total and partial success, the success of ensembles over the mean and
median of their members’ plausibilities is consistent. All 1,012 ensembles
obtain higher plausibility than the mean of their members’ plausibilities
($100\%$). Similarly, $98\%$ of the ensembles are more plausible than the
median of their members’ plausibilities. Hence, an ensemble is more than the
mean (or the median) of its parts. In order to quantify more precisely the
advantage of the ensembles over the mean of their members’ plausibilities, we
computed the difference between the ensemble’s plausibility $\rho_{\\_}{E}$
and the mean (or median) of all the $\rho_{\\_}{sim}$, where $sim\in E$. On
average, the ensembles’ plausibility is $.042$ higher than the mean of their
members ($+4.2\%$), and $.046$ over the median ($+4.6\%$). Figure 3 depicts
the advantage of the ensemble in terms of cognitive plausibility over mean and
median, with respect with the cardinality of the ensemble. The advantage is
directly proportional to the ensemble’s size, i.e. the larger the ensemble,
the larger the improvement over mean and median.

Figure 3: Improvement in cognitive plausibility of the ensembles over the mean
and median of their members’ plausibility

In other words, by combining the rankings, the ensemble reduces the weight of
individual bias, converging towards a shared judgement. Such shared judgement
is not necessarily the best fit in absolute terms, but tends to be more
reliable than most individual judgements.

#### Comparison with preliminary experiment.

To further assess the SSE, the empirical evidence described above can be
compared with the preliminary evaluation we conducted in [7], discussing their
commonalities and differences. That evaluation included only eight of the ten
WordNet-based similarity measures, on ensembles of cardinality 2, 3, and 4,
called _similarity juries_. These measures and ensembles were compared against
an existing similarity dataset, originally collected by Rodríguez and
Egenhofer [33]. The salient characteristics of the two evaluations are
summarised in Table 6. The comparison of the two evaluations reveals that the
same general trends are observable across the board. The total success of the
current evaluation appears to be lower than in the preliminary evaluation, and
this is because the current evaluation includes larger ensembles, which tend
to have lower total success than the small ensembles of cardinality smaller
than 5. On average, the partial success rates are very similar in both
evaluations ($\approx 70\%$). The success over mean is very high in both
evaluations, consistently falling between from $93\%$ to $100\%$.

Although the mean plausibility of the measures is consistent across the two
evaluations, the relative performances of the individual measures vary widely.
Notably, the measure $jcn$ is the most plausible measure in the preliminary
evaluation, while being the second-last in the current evaluation. Similarly,
$vector$ is the top measure in the current evaluation, and ranks among the
worst in the preliminary evaluation. By contrast, $lch$, $wup$, and $lesk$
maintain almost the same relative position in terms of cognitive plausibility.
The two sets of plausibilities do not show any statistically significant
correlation (Spearman’s $\rho\approx.1$). Although the measures fall within a
similar range in both evaluations, it is difficult to identify measures that
are always optimal or inadequate. These results confirm the difficulty of
identifying optimal semantic similarity measures, suggesting that the SSE
offers a way to proceed in a context of limited and uncertain information.

Input and output |  Preliminary | Current
---|---|---
parameters | evaluation |  evaluation
Ground truth: geographic terms |  29 | 97
Ground truth: term pairs |  50 |  50
Ground truth: human subjects |  72 |  203
Similarity measures | 8 | 10
Similarity ensembles | 154 | 1,012
Cardinalities | $\\{2,3,4\\}$ | $\\{2,3\ldots 10\\}$
Measures’ plausibility (mean $\rho$) | $.62$ | $.66$
Measures’ plausibility (range $\rho$) | $[.45,.72]$ | $[.56,.74]$
Total success (range $\%$) | $[28.6,46.1]$ | $[0,55.6]$
Total success (mean $\%$) | $34.8$ | $9.7$
Partial success (range $\%$) | $[55,87.2]$ | $[0,100]$
Partial success (mean $\%$) | $73.3$ | $69.4$
Success over mean (mean $\%$) | $93.2$ | $100$
Table 6: Comparison between the preliminary evaluation in [7] and the
evaluation in this article.

##  6 Conclusions

In this paper we have outlined, formalised, and evaluated the _semantic
similarity ensemble (SSE)_ , a combination technique for semantic similarity
measures. In the SSE, a computational measure of semantic similarity is seen
as a human expert giving a judgement on the similarity of two given pairs.
Like human experts, similarity measures often disagree, and it is often
difficult to identify unequivocally the best measure for a given context. The
ensemble approach is inspired by findings in risk management, machine
learning, biology, and econometrics, which indicate that analyses that
aggregate expert opinions from different experts tend to outperform analyses
from single experts [11, 2, 34]. Based on empirical results collected on
WordNet-based similarity measures in the context of geographic terms, the
following conclusions can be drawn:

  * $-$

An ensemble $E$, whose members are semantic similarity measures, is generally
less cognitively plausible than the best of its members, i.e.
$max(\rho_{\\_}{sim})>\rho_{\\_}E$. In $\approx 9\%$ of cases, the ensemble
obtains total success, i.e. it outperforms the most plausible measure. The
larger the ensemble, the less frequently the ensemble outperforms its best
member.

  * $-$

On average, similarity ensembles $E$ tend to be more cognitively plausible
than any of its individual measures $sim$ in isolation (mean of partial
success ratio $\approx 70\%$). In our evaluation, ensembles with 3 members are
the most successful.

  * $-$

The SSE confirms what Cooke and Goossens [12] pointed out in the context of
risk assessment: “a group of experts tends to perform better than the average
solitary expert, but the best individual in the group often outperforms the
group as a whole” (p. 644).

  * $-$

In the vast majority of cases ($\geq 98\%$), the cognitive plausibility of an
SSE is higher than the mean and median of its members’ plausibilities. An
ensemble is more plausible than the mean (or median) of its parts. These
results are overall consistent with a preliminary evaluation [7].

  * $-$

Individual similarity measures obtain widely different cognitive plausibility
on different ground truths and contexts. In a context of limited information
in which the optimal measure is unknown, we believe that the SSE should be
favoured over any individual similarity measure.

Several issues should be considered for future work. This study focused
exclusively on ten WordNet-based similarity measures and, to gather more
empirical evidence, the ensemble approach should be extended to different
similarity measures. Moreover, to aggregate the similarity scores, we have
adopted two simple ensemble methods (the mean of scores and the mean of
rankings). More sophisticated ensemble techniques based on machine learning
could be explored to increase the ensemble’s performance [31]. Furthermore,
the empirical evidence presented in this paper was limited to the geographic
context. General-purpose semantic similarity datasets, such as that devised by
Agirre _et al._ [1], could be used to further evaluate the ensemble across
various semantic domains.

The evaluation utilised in this study is based on ranking comparison, which
allows to quantify the cognitive plausibility of semantic similarity measure
directly. Although this approach is the most popular in the literature, it has
several drawbacks, as extensively discussed by Ferrara and Tasso [14].
Alternatively, task-based evaluations could be used to assess the cognitive
plausibility of measures indirectly by observing their ability to support a
specific task. Suitable tasks in geographic information retrieval and natural
language processing, such as geographic query expansion, could be devised and
deployed to evaluate the SSE further. In this study, similarity is modelled as
a continuous score, but it can also be represented as a set of discrete
classes. More importantly, the evaluation discussed in this article focuses on
_acontextual_ judgements of similarity of geographic terms. Context, however,
has been identified as a crucial component of similarity [20], and the SSE
should extended to capture specific facets of the observed terms. The
effectiveness of the ensemble should be assessed when observing either the
affordances, the size or the physical structure of geospatial entities.

The importance of semantic similarity measures in information retrieval,
natural language processing, and data mining can hardly be underestimated [17,
21]. In this article, we have shown that a scientific contribution can be
given not only by devising new similarity measures, but also by studying the
combination of existing measures. The SSE provides a general approach to
obtain more cognitively plausible results in settings where the ground truth
is unstable and shifting.

#### Acknowledgements.

The research presented in this paper was funded by a Strategic Research
Cluster grant (07/SRC/I1168) by Science Foundation Ireland under the National
Development Plan. The authors gratefully acknowledge this support.

## References

  * [1] Agirre, E., Alfonseca, E., Hall, K., Kravalova, J., Paşca, M., and Soroa, A. A study on similarity and relatedness using distributional and WordNet-based approaches.  In Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics (2009), ACL, pp. 19–27.  doi:10.3115/1620754.1620758.
  * [2] Armstrong, J. Combining forecasts.  In Principles of Forecasting: A Handbook for Researchers and Practitioners, M. Norwell, Ed. Kluwer Academic Publishing, New York, 2001, pp. 417–439.
  * [3] Ballatore, A., Bertolotto, M., and Wilson, D. Geographic Knowledge Extraction and Semantic Similarity in OpenStreetMap.  Knowledge and Information Systems (2012).  in press.
  * [4] Ballatore, A., Bertolotto, M., and Wilson, D. Computing the Semantic Similarity of Geographic Terms Using Volunteered Lexical Definitions.  International Journal of Geographical Information Science (2013).  in press.
  * [5] Ballatore, A., Bertolotto, M., and Wilson, D. Grounding Linked Open Data in WordNet: The Case of the OSM Semantic Network.  In Proceedings of the Web and Wireless Geographical Information Systems International Symposium (W2GIS 2013), S. Liang, X. Wang, and C. Claramunt, Eds., vol. 7820 of LNCS. Springer, 2013, pp. 1–15.  doi:10.1007/978-3-642-37087-81.
  * [6] Ballatore, A., Wilson, D., and Bertolotto, M. A Holistic Semantic Similarity Measure for Viewports in Interactive Maps.  In Proceedings of the Web and Wireless Geographical Information Systems International Symposium (W2GIS 2012), S. Di Martino, A. Peron, and T. Tezuka, Eds., vol. 7236 of LNCS. Springer, 2012, pp. 151–166.  doi:10.1007/978-3-642-29247-712.
  * [7] Ballatore, A., Wilson, D., and Bertolotto, M. The Similarity Jury: Combining expert judgements on geographic concepts.  In Advances in Conceptual Modeling. ER 2012 Workshops (SeCoGIS), S. Castano, P. Vassiliadis, L. Lakshmanan, and M. Lee, Eds., vol. 7518 of LNCS. Springer, 2012, pp. 231–240.  doi:10.1007/978-3-642-33999-829.
  * [8] Banerjee, S., and Pedersen, T. An adapted Lesk algorithm for word sense disambiguation using WordNet.  In Computational Linguistics and Intelligent Text Processing (2002), vol. 2276 of LNCS, Springer, pp. 117–171.  doi:10.1007/3-540-45715-111.
  * [9] Bauer, A., Eisenbeis, R., Waggoner, D., and Zha, T. Forecast evaluation with cross-sectional data: The Blue Chip Surveys.  Economic Review-Federal Reserve Bank of Atlanta 88, 2 (2003), 17–32.
  * [10] Budescu, D., and Rantilla, A. Confidence in aggregation of expert opinions.  Acta Psychologica 104, 3 (2000), 371–398.  doi:10.1016/S0001-6918(00)00037-8.
  * [11] Clemen, R., and Winkler, R. Combining probability distributions from experts in risk analysis.  Risk Analysis 19, 2 (1999), 187–203.  doi:10.1111/j.1539-6924.1999.tb00399.x.
  * [12] Cooke, R., and Goossens, L. Expert judgement elicitation for risk assessments of critical infrastructures.  Journal of Risk Research 7, 6 (2004), 643–656.  doi:10.1080/1366987042000192237.
  * [13] Fellbaum, C. WordNet.  In Theory and Applications of Ontology: Computer Applications, R. Poli, M. Healy, and A. Kameas, Eds. Springer, 2010, pp. 231–243.  doi:10.1007/978-90-481-8847-510.
  * [14] Ferrara, F., and Tasso, C. Evaluating the Results of Methods for Computing Semantic Relatedness.  In Computational Linguistics and Intelligent Text Processing, A. Gelbukh, Ed., vol. 7816 of LNCS. Springer, 2013, pp. 447–458.  doi:10.1007/978-3-642-37247-636.
  * [15] Hirst, G., and St-Onge, D. Lexical chains as representations of context for the detection and correction of malapropisms.  In WordNet: An electronic lexical database, C. Fellbaum, Ed. MIT Press, Cambridge, MA, 1998, pp. 305–332.
  * [16] Janowicz, K., Keßler, C., Schwarz, M., Wilkes, M., Panov, I., Espeter, M., and Bäumer, B. Algorithm, implementation and application of the SIM-DL similarity server.  In GeoSpatial Semantics: Second International Conference, GeoS 2007 (2007), F. Fonseca, M. A. Rodriguez, and S. Levashkin, Eds., vol. 4853 of LNCS, Springer, pp. 128–145.  doi:10.1007/978-3-540-76876-09.
  * [17] Janowicz, K., Raubal, M., and Kuhn, W. The semantics of similarity in geographic information retrieval.  Journal of Spatial Information Science 2, 1 (2011), 29–57.  doi:10.5311/JOSIS.2011.2.3.
  * [18] Jiang, J., and Conrath, D. Semantic Similarity Based on Corpus Statistics and Lexical Taxonomy.  In Proceedings of International Conference on Research in Computational Linguistics, ROCLING X (1997), vol. 1, ACL, pp. 19–33.
  * [19] Keiser, M. J., Roth, B. L., Armbruster, B. N., Ernsberger, P., Irwin, J. J., and Shoichet, B. K. Relating protein pharmacology by ligand chemistry.  Nature biotechnology 25, 2 (2007), 197–206.  doi:10.1038/nbt1284.
  * [20] Keßler, C. Similarity measurement in context.  In Proceedings of the 6th International and Interdisciplinary Conference on Modeling and Using Context (2007), M. Beigl, H. Christiansen, T. Roth-Berghofer, A. Kofod-Petersen, K. R. Coventry, and H. R. Schmidtke, Eds., vol. 4635 of LNCS, Springer, pp. 277–290.  doi:10.1007/3-540-57868-450.
  * [21] Kuhn, W. Cognitive and linguistic ideas and geographic information semantics.  In Cognitive and Linguistic Aspects of Geographic Space, LNGC. Springer, 2013, pp. 159–174.  doi:10.1007/978-3-642-34359-99.
  * [22] Leacock, C., and Chodorow, M. Combining local context and WordNet similarity for word sense identification.  In WordNet: An electronic lexical database, C. Fellbaum, Ed. MIT Press, Cambridge, MA, 1998, pp. 265–283.
  * [23] Lin, D. An information-theoretic definition of similarity.  In Proceedings of the 15th International Conference on Machine Learning (1998), vol. 1, Morgan Kaufmann, pp. 296–304.
  * [24] Mihalcea, R., Corley, C., and Strapparava, C. Corpus-based and knowledge-based measures of text semantic similarity.  In Proceedings of the Twenty-First National Conference on Artificial Intelligence (2006), vol. 21, AAAI, pp. 775–780.
  * [25] Morgan, M., and Henrion, M. Uncertainty: A Guide to Dealing with Uncertainty in Quantitative Risk and Policy Analysis.  Cambridge University Press, New York, 1992.
  * [26] Mumpower, J., and Stewart, T. Expert judgement and expert disagreement.  Thinking & Reasoning 2, 2-3 (1996), 191–212.  doi:10.1080/135467896394500.
  * [27] Opitz, D., and Maclin, R. Popular Ensemble Methods: An Empirical Study.  Journal of Artificial Intelligence Research 11 (1999), 169–198.  doi:10.1613/jair.614.
  * [28] Patwardhan, S., and Pedersen, T. Using WordNet-based context vectors to estimate the semantic relatedness of concepts.  In Proceedings of the EACL 2006 Workshop Making Sense of Sense – Bringing Computational Linguistics and Psycholinguistics Together (2006), vol. 1501, ACL, pp. 1–8.  doi:10.1.1.116.9473.
  * [29] Pedersen, T., Patwardhan, S., and Michelizzi, J. WordNet::Similarity: measuring the relatedness of concepts.  In Proceedings of Human Language Technologies: The 2004 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Companion Volume: Demonstration Session (2004), ACL, pp. 38–41.
  * [30] Rada, R., Mili, H., Bicknell, E., and Blettner, M. Development and application of a metric on semantic nets.  IEEE Transactions on Systems, Man and Cybernetics 19, 1 (1989), 17–30.  doi:10.1109/21.24528.
  * [31] Renda, M., and Straccia, U. Web metasearch: rank vs. score based rank aggregation methods.  In Proceedings of the 2003 ACM Symposium on Applied Computing, SAC ’03 (2003), ACM, pp. 841–846.
  * [32] Resnik, P. Using Information Content to Evaluate Semantic Similarity in a Taxonomy.  In Proceedings of the 14th International Joint Conference on Artificial Intelligence, IJCAI’95 (1995), vol. 1, Morgan Kaufmann, pp. 448–453.  doi:10.1.1.55.5277.
  * [33] Rodríguez, M., and Egenhofer, M. Comparing Geospatial Entity Classes: An Asymmetric and Context-Dependent Similarity Measure.  International Journal of Geographical Information Science 18, 3 (2004), 229–256.  doi:10.1.1.10.2767.
  * [34] Rokach, L. Ensemble-based classifiers.  Artificial Intelligence Review 33, 1-2 (2010), 1–39.  doi:10.1007/s10462-009-9124-7.
  * [35] Schwering, A. Approaches to Semantic Similarity Measurement for Geo-Spatial Data: A Survey.  Transactions in GIS 12, 1 (2008), 5–29.  doi:10.1111/j.1467-9671.2008.01084.x.
  * [36] Strehl, A., and Ghosh, J. Cluster Ensembles: A Knowledge Reuse Framework for Combining Multiple Partitions.  The Journal of Machine Learning Research 3 (2003), 583–617.  doi:10.1.1.12.309.
  * [37] Surowiecki, J. The Wisdom of Crowds: Why the Many Are Smarter Than the Few and How Collective Wisdom Shapes Business, Economies, Societies and Nations.  Abacus, London, 2005.
  * [38] Wu, Z., and Palmer, M. Verbs semantics and lexical selection.  In Proceedings of the 32nd Annual Meeting of the Association for Computational Linguistics, ACL-94 (1994), ACL, pp. 133–138.  doi:10.1.1.26.3208.