Alessandro Varsi

Dr. Alessandro Varsi

Electrical Engineering and Electronics, University of Liverpool, Liverpool, UK
orcid

Research Focus & Metrics

Academic Career Length

10Years (2017-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
4 August 2020 in IEEE Signal Processing Letters
Verified
Journal Article
Closed access
AVAlessandro Varsi
Alessandro Varsi
JTJack Taylor
Jack Taylor
LKLykourgos Kekempanos
Lykourgos Kekempanos
EKEdward Pyzer Knapp
Edward Pyzer Knapp
SMSimon Maskell
Simon Maskell
Particle Filters (PFs) are Sequential Monte Carlo methods which are widely used to solve filtering problems of dynamic models under Non-Linear Non-Gaussian noise. Modern PF applications have demanding accuracy and run-time constraints that can be addressed through parallel computing. However, an efficient parallelization of PFs can only be achieved by effectively parallelizing the bottleneck: resampling and its constituent redistribution step. A pre-existing implementation of redistribute on Shared Memory Architectures (SMAs) achieves O((N/T) x log(N)) time complexity over T parallel cores. This redistribute implementation is, however, highly computationally intensive and cannot be effectively parallelized due to the inherently limited number of cores of SMAs. In this paper, we propose a novel parallel redistribute on OpenMP 4.5 which takes O((N/T) + logN) steps and fully exploits the computational power of SMAs. The proposed approach is up to six times faster than the O((N/T) x log(N)) one and its implementation on GPU provides a further three-time speed-up vs its equivalent on a 32-core CPU. We also show on an exemplary PF that our redistribution is no longer the bottleneck.

26 November 2021 in Algorithms
Verified
Journal Article
Open access
PDF file
AVAlessandro Varsi
Alessandro Varsi
SMSimon Maskell
Simon Maskell
PSPaul Spirakis
Paul Spirakis
Resampling is a well-known statistical algorithm that is commonly applied in the context of Particle Filters (PFs) in order to perform state estimation for non-linear non-Gaussian dynamic models. As the models become more complex and accurate, the run-time of PF applications becomes increasingly slow. Parallel computing can help to address this. However, resampling (and, hence, PFs as well) necessarily involves a bottleneck, the redistribution step, which is notoriously challenging to parallelize if using textbook parallel computing techniques. A state-of-the-art redistribution takes O((log2N)2) computations on Distributed Memory (DM) architectures, which most supercomputers adopt, whereas redistribution can be performed in O(log2N) on Shared Memory (SM) architectures, such as GPU or mainstream CPUs. In this paper, we propose a novel parallel redistribution for DM that achieves an O(log2N) time complexity. We also present empirical results that indicate that our novel approach outperforms the O((log2N)2) approach.

8 March 2024 in IEEE Transactions on Aerospace and Electronic Systems
Verified
Journal Article
Closed access
AVAlessandro Varsi
Alessandro Varsi
LDLee Devlin
Lee Devlin
PHPaul Horridge
Paul Horridge
SMSimon Maskell
Simon Maskell
Particle Filters (PFs) are commonly used Sequential Monte Carlo (SMC) algorithms to process a never-ending stream of measurements relating to a nonlinear non-Gaussian state space model. Fixed-Lag SMC (FL-SMC) is an extension to the PF that allows for re-processing of historic data. FL-SMC is widely flexible, such that it can solve problems that are challenging for standard PFs. However, FL-SMC also inherits the challenges (in terms of maximizing accuracy and efficiency) that can limit PFs' efficacy when using a poor choice of the proposal distribution: this can be especially evident in strongly nonlinear scenarios. One alternative is to employ Sequential Markov Chain Monte Carlo (S-MCMC) methods, for which the literature offers a wider selection of efficient proposal distributions. However, S-MCMC does not inherently have the broad applicability of FL-SMC. In this paper, we present the Fixed-Lag No-U-Turn Sampler, an SMC framework that combines FL-SMC and No-U-Turn Sampler (NUTS), a gradient-based MCMC method. We show that, when compared with several variants of PFs, including one that employs Particle Flow, several variants of FL-SMC, and S-MCMC, our proposed approach provides significant accuracy and efficiency improvements, at the price of a moderate run-time overhead.

2 January 2025 in Algorithms
Verified
Journal Article
Open access
PDF file
EDEfthyvoulos Drousiotis
Efthyvoulos Drousiotis
AVAlessandro Varsi
Alessandro Varsi
APAlexander Mark Phillips
Alexander Mark Phillips
SMSimon Maskell
Simon Maskell
PSPaul Spirakis
Paul Spirakis
Bayesian approaches to decision trees (DTs) using Markov Chain Monte Carlo (MCMC) samplers have recently demonstrated state-of-the-art accuracy performance when it comes to training DTs to solve classification problems. Despite the competitive classification accuracy, MCMC requires a potentially long runtime to converge. A widely used approach to reducing an algorithm’s runtime is to employ modern multi-core computer architectures, either with shared memory (SM) or distributed memory (DM), and use parallel computing to accelerate the algorithm. However, the inherent sequential nature of MCMC makes it unsuitable for parallel implementation unless the accuracy is sacrificed. This issue is particularly evident in DM architectures, which normally provide access to larger numbers of cores than SM. Sequential Monte Carlo (SMC) samplers are a parallel alternative to MCMC, which do not trade off accuracy for parallelism. However, the performance of SMC samplers in the context of DTs is underexplored, and the parallelization is complicated by the challenges in parallelizing its bottleneck, namely redistribution, especially on variable-size data types such as DTs. In this work, we study the problem of parallelizing SMC in the context of DTs both on SM and DM. On both memory architectures, we show that the proposed parallelization strategies achieve asymptotically optimal O(log2N) time complexity. Numerical results are presented for a 32-core SM machine and a 256-core DM cluster. For both computer architectures, the experimental results show that our approach has comparable or better accuracy than MCMC but runs up to 51 times faster on SM and 640 times faster on DM. In this paper, we share the GitHub link to the source code.

1 January 2017
Verified
Conference Paper
Closed access
AVAlessandro Varsi
Alessandro Varsi
LKL. Kekempanos
L. Kekempanos
JTJeyan Thiyagalingam
Jeyan Thiyagalingam
SMS. Maskell
S. Maskell
Particle Filters are parallelisable. However, the resampling step, which is necessary to handle the degeneracy problem, is non-trivial to parallelise. A textbook implementation of this step achieves O (N) time complexity with a very low constant but deriving an efficient parallel implementation of the same is non-trivial. Several alternative solutions have been proposed. A state-of-the-art parallelisable algorithm has O (log2N)2 time complexity and has been implemented in the Big data MapReduce context. However, portability of this algorithm is difficult to achieve, especially on distributed memory systems. In paper, we reformulate this algorithm for the distributed memory setup and demonstrate that the same algorithm can be almost twice as fast as the exiting state-of-theart algorithm for up to 128 cores. Furthermore, we also show that our algorithm is 20 times faster than the serial version of the algorithm.

9 July 2024 in Research Square
Verified
Preprint
Open access
PDF file
EDEfthyvoulos Drousiotis
Efthyvoulos Drousiotis
DJDan Joyce
Dan Joyce
AVAlessandro Varsi
Alessandro Varsi
PSPaul Spirakis
Paul Spirakis
SMSimon Maskell
Simon Maskell
The deployment of machine learning for high-stakes decision support may demand algorithms that are intrinsically interpretable so that a model can be interrogated by a user to understand how the model arrived at an output given an input. Decision trees exemplify intrinsically interpretable machine learning but to achieve acceptable performance they rely on ensemble methods which sacrifice their interpretability because there is no single, or ‘canonical’ tree for the user to inspect. Sequential Monte Carlo Decision Trees are a novel method for training populations of decision trees that do not rely on ensembles or subspace sampling and achieve comparable performance to other tree-based methods. With SMC-DTs, each of the population of trees are trained on the entire feature space and each is a candidate for an intrinsically interpretable canonical decision tree. In this paper, we propose a tree-similarity algorithm to assist a user in choosing a final, canonical high-performing tree that is consistent (in structure) with other high-performing candidate trees. This enables the user to reduce the pool of candidates to a small number that can be inspected to select a final tree for deployment. We show that SMC-DTs are competitive with well-established methods Random Forest, Extreme Gradient Boosting Trees and Classification and Regression Trees on four benchmark health-related data sets. We then demonstrate the combination of SMC-DTs with the tree similarity method to derive and present an interpretable decision tree to identify university students likely to experience suicidal ideation using summary and administrative data university welfare services would be able to access for their students (i.e. without detailed clinical information). We conclude that combining SMC-DTs with tree-similarity offers a plausible way of delivering intrinsic interpretability for use in mixed-data type tabular data sets.