-
Characterizing the Interpretability of Attention Maps in Digital Pathology
Authors:
Tomé Albuquerque,
Anil Yüce,
Markus D. Herrmann,
Alvaro Gomariz
Abstract:
Interpreting machine learning model decisions is crucial for high-risk applications like healthcare. In digital pathology, large whole slide images (WSIs) are decomposed into smaller tiles and tile-derived features are processed by attention-based multiple instance learning (ABMIL) models to predict WSI-level labels. These networks generate tile-specific attention weights, which can be visualized…
▽ More
Interpreting machine learning model decisions is crucial for high-risk applications like healthcare. In digital pathology, large whole slide images (WSIs) are decomposed into smaller tiles and tile-derived features are processed by attention-based multiple instance learning (ABMIL) models to predict WSI-level labels. These networks generate tile-specific attention weights, which can be visualized as attention maps for interpretability. However, a standardized evaluation framework for these maps is lacking, questioning their reliability and ability to detect spurious correlations that can mislead models. We herein propose a framework to assess the ability of attention networks to attend to relevant features in digital pathology by creating artificial model confounders and using dedicated interpretability metrics. Models are trained and evaluated on data with tile modifications correlated with WSI labels, enabling the analysis of model sensitivity to artificial confounders and the accuracy of attention maps in highlighting them. Confounders are introduced either through synthetic tile modifications or through tile ablations based on their specific image-based features, with the latter being used to assess more clinically relevant scenarios. We also analyze the impact of varying confounder quantities at both the tile and WSI levels. Our results show that ABMIL models perform as desired within our framework. While attention maps generally highlight relevant regions, their robustness is affected by the type and number of confounders. Our versatile framework has the potential to be used in the evaluation of various methods and the exploration of image-based features driving model predictions, which could aid in biomarker discovery.
△ Less
Submitted 2 July, 2024;
originally announced July 2024.
-
Position: Why We Must Rethink Empirical Research in Machine Learning
Authors:
Moritz Herrmann,
F. Julian D. Lange,
Katharina Eggensperger,
Giuseppe Casalicchio,
Marcel Wever,
Matthias Feurer,
David Rügamer,
Eyke Hüllermeier,
Anne-Laure Boulesteix,
Bernd Bischl
Abstract:
We warn against a common but incomplete understanding of empirical research in machine learning that leads to non-replicable results, makes findings unreliable, and threatens to undermine progress in the field. To overcome this alarming situation, we call for more awareness of the plurality of ways of gaining knowledge experimentally but also of some epistemic limitations. In particular, we argue…
▽ More
We warn against a common but incomplete understanding of empirical research in machine learning that leads to non-replicable results, makes findings unreliable, and threatens to undermine progress in the field. To overcome this alarming situation, we call for more awareness of the plurality of ways of gaining knowledge experimentally but also of some epistemic limitations. In particular, we argue most current empirical machine learning research is fashioned as confirmatory research while it should rather be considered exploratory.
△ Less
Submitted 25 May, 2024; v1 submitted 3 May, 2024;
originally announced May 2024.
-
Human Factors in Model-Driven Engineering: Future Research Goals and Initiatives for MDE
Authors:
Grischa Liebel,
Jil Klünder,
Regina Hebig,
Christopher Lazik,
Inês Nunes,
Isabella Graßl,
Jan-Philipp Steghöfer,
Joeri Exelmans,
Julian Oertel,
Kai Marquardt,
Katharina Juhnke,
Kurt Schneider,
Lucas Gren,
Lucia Happe,
Marc Herrmann,
Marvin Wyrich,
Matthias Tichy,
Miguel Goulão,
Rebekka Wohlrab,
Reyhaneh Kalantari,
Robert Heinrich,
Sandra Greiner,
Satrio Adi Rukmono,
Shalini Chakraborty,
Silvia Abrahão
, et al. (1 additional authors not shown)
Abstract:
Purpose: Software modelling and Model-Driven Engineering (MDE) is traditionally studied from a technical perspective. However, one of the core motivations behind the use of software models is inherently human-centred. Models aim to enable practitioners to communicate about software designs, make software understandable, or make software easier to write through domain-specific modelling languages.…
▽ More
Purpose: Software modelling and Model-Driven Engineering (MDE) is traditionally studied from a technical perspective. However, one of the core motivations behind the use of software models is inherently human-centred. Models aim to enable practitioners to communicate about software designs, make software understandable, or make software easier to write through domain-specific modelling languages. Several recent studies challenge the idea that these aims can always be reached and indicate that human factors play a role in the success of MDE. However, there is an under-representation of research focusing on human factors in modelling. Methods: During a GI-Dagstuhl seminar, topics related to human factors in modelling were discussed by 26 expert participants from research and industry. Results: In breakout groups, five topics were covered in depth, namely modelling human aspects, factors of modeller experience, diversity and inclusion in MDE, collaboration and MDE, and teaching human-aware MDE. Conclusion: We summarise our insights gained during the discussions on the five topics. We formulate research goals, questions, and propositions that support directing future initiatives towards an MDE community that is aware of and supportive of human factors and values.
△ Less
Submitted 29 April, 2024;
originally announced April 2024.
-
DCSI -- An improved measure of cluster separability based on separation and connectedness
Authors:
Jana Gauss,
Fabian Scheipl,
Moritz Herrmann
Abstract:
Whether class labels in a given data set correspond to meaningful clusters is crucial for the evaluation of clustering algorithms using real-world data sets. This property can be quantified by separability measures. The central aspects of separability for density-based clustering are between-class separation and within-class connectedness, and neither classification-based complexity measures nor c…
▽ More
Whether class labels in a given data set correspond to meaningful clusters is crucial for the evaluation of clustering algorithms using real-world data sets. This property can be quantified by separability measures. The central aspects of separability for density-based clustering are between-class separation and within-class connectedness, and neither classification-based complexity measures nor cluster validity indices (CVIs) adequately incorporate them. A newly developed measure (density cluster separability index, DCSI) aims to quantify these two characteristics and can also be used as a CVI. Extensive experiments on synthetic data indicate that DCSI correlates strongly with the performance of DBSCAN measured via the adjusted Rand index (ARI) but lacks robustness when it comes to multi-class data sets with overlapping classes that are ill-suited for density-based hard clustering. Detailed evaluation on frequently used real-world data sets shows that DCSI can correctly identify touching or overlapping classes that do not correspond to meaningful density-based clusters.
△ Less
Submitted 1 July, 2024; v1 submitted 19 October, 2023;
originally announced October 2023.
-
Towards a Neuronally Consistent Ontology for Robotic Agents
Authors:
Florian Ahrens,
Mihai Pomarlan,
Daniel Beßler,
Thorsten Fehr,
Michael Beetz,
Manfred Herrmann
Abstract:
The Collaborative Research Center for Everyday Activity Science & Engineering (CRC EASE) aims to enable robots to perform environmental interaction tasks with close to human capacity. It therefore employs a shared ontology to model the activity of both kinds of agents, empowering robots to learn from human experiences. To properly describe these human experiences, the ontology will strongly benefi…
▽ More
The Collaborative Research Center for Everyday Activity Science & Engineering (CRC EASE) aims to enable robots to perform environmental interaction tasks with close to human capacity. It therefore employs a shared ontology to model the activity of both kinds of agents, empowering robots to learn from human experiences. To properly describe these human experiences, the ontology will strongly benefit from incorporating characteristics of neuronal information processing which are not accessible from a behavioral perspective alone. We, therefore, propose the analysis of human neuroimaging data for evaluation and validation of concepts and events defined in the ontology model underlying most of the CRC projects. In an exploratory analysis, we employed an Independent Component Analysis (ICA) on functional Magnetic Resonance Imaging (fMRI) data from participants who were presented with the same complex video stimuli of activities as robotic and human agents in different environments and contexts. We then correlated the activity patterns of brain networks represented by derived components with timings of annotated event categories as defined by the ontology model. The present results demonstrate a subset of common networks with stable correlations and specificity towards particular event classes and groups, associated with environmental and contextual factors. These neuronal characteristics will open up avenues for adapting the ontology model to be more consistent with human information processing.
△ Less
Submitted 26 September, 2023;
originally announced September 2023.
-
An Approach to Multiple Comparison Benchmark Evaluations that is Stable Under Manipulation of the Comparate Set
Authors:
Ali Ismail-Fawaz,
Angus Dempster,
Chang Wei Tan,
Matthieu Herrmann,
Lynn Miller,
Daniel F. Schmidt,
Stefano Berretti,
Jonathan Weber,
Maxime Devanne,
Germain Forestier,
Geoffrey I. Webb
Abstract:
The measurement of progress using benchmarks evaluations is ubiquitous in computer science and machine learning. However, common approaches to analyzing and presenting the results of benchmark comparisons of multiple algorithms over multiple datasets, such as the critical difference diagram introduced by Demšar (2006), have important shortcomings and, we show, are open to both inadvertent and inte…
▽ More
The measurement of progress using benchmarks evaluations is ubiquitous in computer science and machine learning. However, common approaches to analyzing and presenting the results of benchmark comparisons of multiple algorithms over multiple datasets, such as the critical difference diagram introduced by Demšar (2006), have important shortcomings and, we show, are open to both inadvertent and intentional manipulation. To address these issues, we propose a new approach to presenting the results of benchmark comparisons, the Multiple Comparison Matrix (MCM), that prioritizes pairwise comparisons and precludes the means of manipulating experimental results in existing approaches. MCM can be used to show the results of an all-pairs comparison, or to show the results of a comparison between one or more selected algorithms and the state of the art. MCM is implemented in Python and is publicly available.
△ Less
Submitted 19 May, 2023;
originally announced May 2023.
-
Proximity Forest 2.0: A new effective and scalable similarity-based classifier for time series
Authors:
Matthieu Herrmann,
Chang Wei Tan,
Mahsa Salehi,
Geoffrey I. Webb
Abstract:
Time series classification (TSC) is a challenging task due to the diversity of types of feature that may be relevant for different classification tasks, including trends, variance, frequency, magnitude, and various patterns. To address this challenge, several alternative classes of approach have been developed, including similarity-based, features and intervals, shapelets, dictionary, kernel, neur…
▽ More
Time series classification (TSC) is a challenging task due to the diversity of types of feature that may be relevant for different classification tasks, including trends, variance, frequency, magnitude, and various patterns. To address this challenge, several alternative classes of approach have been developed, including similarity-based, features and intervals, shapelets, dictionary, kernel, neural network, and hybrid approaches. While kernel, neural network, and hybrid approaches perform well overall, some specialized approaches are better suited for specific tasks. In this paper, we propose a new similarity-based classifier, Proximity Forest version 2.0 (PF 2.0), which outperforms previous state-of-the-art similarity-based classifiers across the UCR benchmark and outperforms state-of-the-art kernel, neural network, and hybrid methods on specific datasets in the benchmark that are best addressed by similarity-base methods. PF 2.0 incorporates three recent advances in time series similarity measures -- (1) computationally efficient early abandoning and pruning to speedup elastic similarity computations; (2) a new elastic similarity measure, Amerced Dynamic Time Warping (ADTW); and (3) cost function tuning. It rationalizes the set of similarity measures employed, reducing the eight base measures of the original PF to three and using the first derivative transform with all similarity measures, rather than a limited subset. We have implemented both PF 1.0 and PF 2.0 in a single C++ framework, making the PF framework more efficient.
△ Less
Submitted 13 April, 2023; v1 submitted 12 April, 2023;
originally announced April 2023.
-
The NCI Imaging Data Commons as a platform for reproducible research in computational pathology
Authors:
Daniela P. Schacherer,
Markus D. Herrmann,
David A. Clunie,
Henning Höfener,
William Clifford,
William J. R. Longabaugh,
Steve Pieper,
Ron Kikinis,
Andrey Fedorov,
André Homeyer
Abstract:
Background and Objectives: Reproducibility is a major challenge in developing machine learning (ML)-based solutions in computational pathology (CompPath). The NCI Imaging Data Commons (IDC) provides >120 cancer image collections according to the FAIR principles and is designed to be used with cloud ML services. Here, we explore its potential to facilitate reproducibility in CompPath research.
Me…
▽ More
Background and Objectives: Reproducibility is a major challenge in developing machine learning (ML)-based solutions in computational pathology (CompPath). The NCI Imaging Data Commons (IDC) provides >120 cancer image collections according to the FAIR principles and is designed to be used with cloud ML services. Here, we explore its potential to facilitate reproducibility in CompPath research.
Methods: Using the IDC, we implemented two experiments in which a representative ML-based method for classifying lung tumor tissue was trained and/or evaluated on different datasets. To assess reproducibility, the experiments were run multiple times with separate but identically configured instances of common ML services.
Results: The AUC values of different runs of the same experiment were generally consistent. However, we observed small variations in AUC values of up to 0.045, indicating a practical limit to reproducibility.
Conclusions: We conclude that the IDC facilitates approaching the reproducibility limit of CompPath research (i) by enabling researchers to reuse exactly the same datasets and (ii) by integrating with cloud ML services so that experiments can be run in identically configured computing environments.
△ Less
Submitted 7 November, 2023; v1 submitted 16 March, 2023;
originally announced March 2023.
-
Parameterizing the cost function of Dynamic Time Warping with application to time series classification
Authors:
Matthieu Herrmann,
Chang Wei Tan,
Geoffrey I. Webb
Abstract:
Dynamic Time Warping (DTW) is a popular time series distance measure that aligns the points in two series with one another. These alignments support warping of the time dimension to allow for processes that unfold at differing rates. The distance is the minimum sum of costs of the resulting alignments over any allowable warping of the time dimension. The cost of an alignment of two points is a fun…
▽ More
Dynamic Time Warping (DTW) is a popular time series distance measure that aligns the points in two series with one another. These alignments support warping of the time dimension to allow for processes that unfold at differing rates. The distance is the minimum sum of costs of the resulting alignments over any allowable warping of the time dimension. The cost of an alignment of two points is a function of the difference in the values of those points. The original cost function was the absolute value of this difference. Other cost functions have been proposed. A popular alternative is the square of the difference. However, to our knowledge, this is the first investigation of both the relative impacts of using different cost functions and the potential to tune cost functions to different tasks. We do so in this paper by using a tunable cost function λγ with parameter γ. We show that higher values of γ place greater weight on larger pairwise differences, while lower values place greater weight on smaller pairwise differences. We demonstrate that training γ significantly improves the accuracy of both the DTW nearest neighbor and Proximity Forest classifiers.
△ Less
Submitted 28 March, 2023; v1 submitted 24 January, 2023;
originally announced January 2023.
-
Extrinsic Camera Calibration with Semantic Segmentation
Authors:
Alexander Tsaregorodtsev,
Johannes Müller,
Jan Strohbeck,
Martin Herrmann,
Michael Buchholz,
Vasileios Belagiannis
Abstract:
Monocular camera sensors are vital to intelligent vehicle operation and automated driving assistance and are also heavily employed in traffic control infrastructure. Calibrating the monocular camera, though, is time-consuming and often requires significant manual intervention. In this work, we present an extrinsic camera calibration approach that automatizes the parameter estimation by utilizing s…
▽ More
Monocular camera sensors are vital to intelligent vehicle operation and automated driving assistance and are also heavily employed in traffic control infrastructure. Calibrating the monocular camera, though, is time-consuming and often requires significant manual intervention. In this work, we present an extrinsic camera calibration approach that automatizes the parameter estimation by utilizing semantic segmentation information from images and point clouds. Our approach relies on a coarse initial measurement of the camera pose and builds on lidar sensors mounted on a vehicle with high-precision localization to capture a point cloud of the camera environment. Afterward, a mapping between the camera and world coordinate spaces is obtained by performing a lidar-to-camera registration of the semantically segmented sensor data. We evaluate our method on simulated and real-world data to demonstrate low error measurements in the calibration results. Our approach is suitable for infrastructure sensors as well as vehicle sensors, while it does not require motion of the camera platform.
△ Less
Submitted 8 August, 2022;
originally announced August 2022.
-
On the Subjectivity of Emotions in Software Projects: How Reliable are Pre-Labeled Data Sets for Sentiment Analysis?
Authors:
Marc Herrmann,
Martin Obaidi,
Larissa Chazette,
Jil Klünder
Abstract:
Social aspects of software projects become increasingly important for research and practice. Different approaches analyze the sentiment of a development team, ranging from simply asking the team to so-called sentiment analysis on text-based communication. These sentiment analysis tools are trained using pre-labeled data sets from different sources, including GitHub and Stack Overflow. In this pape…
▽ More
Social aspects of software projects become increasingly important for research and practice. Different approaches analyze the sentiment of a development team, ranging from simply asking the team to so-called sentiment analysis on text-based communication. These sentiment analysis tools are trained using pre-labeled data sets from different sources, including GitHub and Stack Overflow. In this paper, we investigate if the labels of the statements in the data sets coincide with the perception of potential members of a software project team. Based on an international survey, we compare the median perception of 94 participants with the pre-labeled data sets as well as every single participant's agreement with the predefined labels. Our results point to three remarkable findings: (1) Although the median values coincide with the predefined labels of the data sets in 62.5% of the cases, we observe a huge difference between the single participant's ratings and the labels; (2) there is not a single participant who totally agrees with the predefined labels; and (3) the data set whose labels are based on guidelines performs better than the ad hoc labeled data set.
△ Less
Submitted 16 July, 2022;
originally announced July 2022.
-
Enhancing cluster analysis via topological manifold learning
Authors:
Moritz Herrmann,
Daniyal Kazempour,
Fabian Scheipl,
Peer Kröger
Abstract:
We discuss topological aspects of cluster analysis and show that inferring the topological structure of a dataset before clustering it can considerably enhance cluster detection: theoretical arguments and empirical evidence show that clustering embedding vectors, representing the structure of a data manifold instead of the observed feature vectors themselves, is highly beneficial. To demonstrate,…
▽ More
We discuss topological aspects of cluster analysis and show that inferring the topological structure of a dataset before clustering it can considerably enhance cluster detection: theoretical arguments and empirical evidence show that clustering embedding vectors, representing the structure of a data manifold instead of the observed feature vectors themselves, is highly beneficial. To demonstrate, we combine manifold learning method UMAP for inferring the topological structure with density-based clustering method DBSCAN. Synthetic and real data results show that this both simplifies and improves clustering in a diverse set of low- and high-dimensional problems including clusters of varying density and/or entangled shapes. Our approach simplifies clustering because topological pre-processing consistently reduces parameter sensitivity of DBSCAN. Clustering the resulting embeddings with DBSCAN can then even outperform complex methods such as SPECTACL and ClusterGAN. Finally, our investigation suggests that the crucial issue in clustering does not appear to be the nominal dimension of the data or how many irrelevant features it contains, but rather how \textit{separable} the clusters are in the ambient observation space they are embedded in, which is usually the (high-dimensional) Euclidean space defined by the features of the data. Our approach is successful because we perform the cluster analysis after projecting the data into a more suitable space that is optimized for separability, in some sense.
△ Less
Submitted 1 July, 2022;
originally announced July 2022.
-
A geometric framework for outlier detection in high-dimensional data
Authors:
Moritz Herrmann,
Florian Pfisterer,
Fabian Scheipl
Abstract:
Outlier or anomaly detection is an important task in data analysis. We discuss the problem from a geometrical perspective and provide a framework that exploits the metric structure of a data set. Our approach rests on the manifold assumption, i.e., that the observed, nominally high-dimensional data lie on a much lower dimensional manifold and that this intrinsic structure can be inferred with mani…
▽ More
Outlier or anomaly detection is an important task in data analysis. We discuss the problem from a geometrical perspective and provide a framework that exploits the metric structure of a data set. Our approach rests on the manifold assumption, i.e., that the observed, nominally high-dimensional data lie on a much lower dimensional manifold and that this intrinsic structure can be inferred with manifold learning methods. We show that exploiting this structure significantly improves the detection of outlying observations in high-dimensional data. We also suggest a novel, mathematically precise, and widely applicable distinction between distributional and structural outliers based on the geometry and topology of the data manifold that clarifies conceptual ambiguities prevalent throughout the literature. Our experiments focus on functional data as one class of structured high-dimensional data, but the framework we propose is completely general and we include image and graph data applications. Our results show that the outlier structure of high-dimensional and non-tabular data can be detected and visualized using manifold learning methods and quantified using standard outlier scoring methods applied to the manifold embedding vectors.
△ Less
Submitted 29 July, 2022; v1 submitted 1 July, 2022;
originally announced July 2022.
-
SEnti-Analyzer: Joint Sentiment Analysis For Text-Based and Verbal Communication in Software Projects
Authors:
Marc Herrmann,
Martin Obaidi,
Jil Klünder
Abstract:
Social aspects in software development teams are of particular importance for a successful project closure. To analyze sentiments in software projects, there are several tools and approaches available. These tools analyze text-based communication based on the used words to predict whether they appear to be positive, negative, or neutral for the receiver of the message. In the research project ComC…
▽ More
Social aspects in software development teams are of particular importance for a successful project closure. To analyze sentiments in software projects, there are several tools and approaches available. These tools analyze text-based communication based on the used words to predict whether they appear to be positive, negative, or neutral for the receiver of the message. In the research project ComContA, we investigate so-called sentiment analysis striving to analyze the content of text-based communication in development teams with regard to the statement's polarity. That is, we analyze whether the communication appears to be adequate (i.e., positive or neutral) or negative. In a workshop paper, we presented a tool called SEnti-Analyzer that allows to apply sentiment analysis to verbal communication in meetings of software projects. In this technical report, we present the extended functionalities of the SEnti-Analyzer by also allowing the analysis of text-based communication, we improve the prediction of the tool by including established sentiment analysis tools, and we evaluate the tool with respect to its accuracy. We evaluate the tool by comparing the prediction of the SEnti-Analyzer to pre-labeled established data sets used for sentiment analysis in software engineering and to perceptions of computer scientists. Our results indicate that in almost all cases at least two of the three votes coincide, but in only about half of the cases all three votes coincide. Our results raise the question of the "ultimate truth" of sentiment analysis outcomes: What do we want to predict with sentiment analysis tools? The pre-defined labels of established data sets? The perception of computer scientists? Or the perception of single computer scientists which appears to be the most meaningful objective?
△ Less
Submitted 22 June, 2022;
originally announced June 2022.
-
Self-Assessment for Single-Object Tracking in Clutter Using Subjective Logic
Authors:
Thomas Griebel,
Johannes Müller,
Paul Geisler,
Charlotte Hermann,
Martin Herrmann,
Michael Buchholz,
Klaus Dietmayer
Abstract:
Reliable tracking algorithms are essential for automated driving. However, the existing consistency measures are not sufficient to meet the increasing safety demands in the automotive sector. Therefore, this work presents a novel method for self-assessment of single-object tracking in clutter based on Kalman filtering and subjective logic. A key feature of the approach is that it additionally prov…
▽ More
Reliable tracking algorithms are essential for automated driving. However, the existing consistency measures are not sufficient to meet the increasing safety demands in the automotive sector. Therefore, this work presents a novel method for self-assessment of single-object tracking in clutter based on Kalman filtering and subjective logic. A key feature of the approach is that it additionally provides a measure of the collected statistical evidence in its online reliability scores. In this way, various aspects of reliability, such as the correctness of the assumed measurement noise, detection probability, and clutter rate, can be monitored in addition to the overall assessment based on the available evidence. Here, we present a mathematical derivation of the reference distribution used in our self-assessment module for our studied problem. Moreover, we introduce a formula that describes how a threshold should be chosen for the degree of conflict, the subjective logic comparison measure used for the reliability decision making. Our approach is evaluated in a challenging simulation scenario designed to model adverse weather conditions. The simulations show that our method can significantly improve the reliability checking of single-object tracking in clutter in several aspects.
△ Less
Submitted 15 June, 2022;
originally announced June 2022.
-
Amercing: An Intuitive, Elegant and Effective Constraint for Dynamic Time Warping
Authors:
Matthieu Herrmann,
Geoffrey I. Webb
Abstract:
Dynamic Time Warping (DTW), and its constrained (CDTW) and weighted (WDTW) variants, are time series distances with a wide range of applications. They minimize the cost of non-linear alignments between series. CDTW and WDTW have been introduced because DTW is too permissive in its alignments. However, CDTW uses a crude step function, allowing unconstrained flexibility within the window, and none b…
▽ More
Dynamic Time Warping (DTW), and its constrained (CDTW) and weighted (WDTW) variants, are time series distances with a wide range of applications. They minimize the cost of non-linear alignments between series. CDTW and WDTW have been introduced because DTW is too permissive in its alignments. However, CDTW uses a crude step function, allowing unconstrained flexibility within the window, and none beyond it. WDTW's multiplicative weight is relative to the distances between aligned points along a warped path, rather than being a direct function of the amount of warping that is introduced. In this paper, we introduce Amerced Dynamic Time Warping (ADTW), a new, intuitive, DTW variant that penalizes the act of warping by a fixed additive cost. Like CDTW and WDTW, ADTW constrains the amount of warping. However, it avoids both abrupt discontinuities in the amount of warping allowed and the limitations of a multiplicative penalty. We formally introduce ADTW, prove some of its properties, and discuss its parameterization. We show on a simple example how it can be parameterized to achieve an intuitive outcome, and demonstrate its usefulness on a standard time series classification benchmark. We provide a demonstration application in C++.
△ Less
Submitted 26 November, 2021;
originally announced November 2021.
-
Motion Planning for Connected Automated Vehicles at Occluded Intersections With Infrastructure Sensors
Authors:
Johannes Müller,
Jan Strohbeck,
Martin Herrmann,
Michael Buchholz
Abstract:
Motion planning at urban intersections that accounts for the situation context, handles occlusions, and deals with measurement and prediction uncertainty is a major challenge on the way to urban automated driving. In this work, we address this challenge with a sampling-based optimization approach. For this, we formulate an optimal control problem that optimizes for low risk and high passenger comf…
▽ More
Motion planning at urban intersections that accounts for the situation context, handles occlusions, and deals with measurement and prediction uncertainty is a major challenge on the way to urban automated driving. In this work, we address this challenge with a sampling-based optimization approach. For this, we formulate an optimal control problem that optimizes for low risk and high passenger comfort. The risk is calculated on the basis of the perception information and the respective uncertainty using a risk model. The risk model combines set-based methods and probabilistic approaches. Thus, the approach provides safety guarantees in a probabilistic sense, while for a vanishing risk, the formal safety guarantees of the set-based methods are inherited. By exploring all available behavior options, our approach solves decision making and longitudinal trajectory planning in one step. The available behavior options are provided by a formal representation of the situation context, which is also used to reduce calculation efforts. Occlusions are resolved using the external perception of infrastructure-mounted sensors. Yet, instead of merging external and ego perception with track-to-track fusion, the information is used in parallel. The motion planning scheme is validated through real-world experiments.
△ Less
Submitted 21 October, 2021;
originally announced October 2021.
-
A geometric perspective on functional outlier detection
Authors:
Moritz Herrmann,
Fabian Scheipl
Abstract:
We consider functional outlier detection from a geometric perspective, specifically: for functional data sets drawn from a functional manifold which is defined by the data's modes of variation in amplitude and phase. Based on this manifold, we develop a conceptualization of functional outlier detection that is more widely applicable and realistic than previously proposed. Our theoretical and exper…
▽ More
We consider functional outlier detection from a geometric perspective, specifically: for functional data sets drawn from a functional manifold which is defined by the data's modes of variation in amplitude and phase. Based on this manifold, we develop a conceptualization of functional outlier detection that is more widely applicable and realistic than previously proposed. Our theoretical and experimental analyses demonstrate several important advantages of this perspective: It considerably improves theoretical understanding and allows to describe and analyse complex functional outlier scenarios consistently and in full generality, by differentiating between structurally anomalous outlier data that are off-manifold and distributionally outlying data that are on-manifold but at its margins. This improves practical feasibility of functional outlier detection: We show that simple manifold learning methods can be used to reliably infer and visualize the geometric structure of functional data sets. We also show that standard outlier detection methods requiring tabular data inputs can be applied to functional data very successfully by simply using their vector-valued representations learned from manifold learning methods as input features. Our experiments on synthetic and real data sets demonstrate that this approach leads to outlier detection performances at least on par with existing functional data-specific methods in a large variety of settings, without the highly specialized, complex methodology and narrow domain of application these methods often entail.
△ Less
Submitted 14 September, 2021;
originally announced September 2021.
-
From Textual to Verbal Communication: Towards Applying Sentiment Analysis to a Software Project Meeting
Authors:
Marc Herrmann,
Jil Klünder
Abstract:
Sentiment analysis gets increasing attention in software engineering with new tools emerging from new insights provided by researchers. Existing use cases and tools are meant to be used for textual communication such as comments on collaborative version control systems. While this can already provide useful feedback for development teams, a lot of communication takes place in meetings and is not s…
▽ More
Sentiment analysis gets increasing attention in software engineering with new tools emerging from new insights provided by researchers. Existing use cases and tools are meant to be used for textual communication such as comments on collaborative version control systems. While this can already provide useful feedback for development teams, a lot of communication takes place in meetings and is not suited for present tool designs and concepts.
In this paper, we present a concept that is capable of processing live meeting audio and classifying transcribed statements into sentiment polarity classes. We combine the latest advances in open source speech recognition with previous research in sentiment analysis. We tested our approach on a student software project meeting to gain proof of concept, showing moderate agreement between the classifications of our tool and a human observer on the meeting audio. Despite the preliminary character of our study, we see promising results motivating future research in sentiment analysis on meetings. For example, the polarity classification can be extended to detect destructive behaviour that can endanger project success.
△ Less
Submitted 4 August, 2021;
originally announced August 2021.
-
Highdicom: A Python library for standardized encoding of image annotations and machine learning model outputs in pathology and radiology
Authors:
Christopher P. Bridge,
Chris Gorman,
Steven Pieper,
Sean W. Doyle,
Jochen K. Lennerz,
Jayashree Kalpathy-Cramer,
David A. Clunie,
Andriy Y. Fedorov,
Markus D. Herrmann
Abstract:
Machine learning is revolutionizing image-based diagnostics in pathology and radiology. ML models have shown promising results in research settings, but their lack of interoperability has been a major barrier for clinical integration and evaluation. The DICOM a standard specifies Information Object Definitions and Services for the representation and communication of digital images and related info…
▽ More
Machine learning is revolutionizing image-based diagnostics in pathology and radiology. ML models have shown promising results in research settings, but their lack of interoperability has been a major barrier for clinical integration and evaluation. The DICOM a standard specifies Information Object Definitions and Services for the representation and communication of digital images and related information, including image-derived annotations and analysis results. However, the complexity of the standard represents an obstacle for its adoption in the ML community and creates a need for software libraries and tools that simplify working with data sets in DICOM format. Here we present the highdicom library, which provides a high-level application programming interface for the Python programming language that abstracts low-level details of the standard and enables encoding and decoding of image-derived information in DICOM format in a few lines of Python code. The highdicom library ties into the extensive Python ecosystem for image processing and machine learning. Simultaneously, by simplifying creation and parsing of DICOM-compliant files, highdicom achieves interoperability with the medical imaging systems that hold the data used to train and run ML models, and ultimately communicate and store model outputs for clinical use. We demonstrate through experiments with slide microscopy and computed tomography imaging, that, by bridging these two ecosystems, highdicom enables developers to train and evaluate state-of-the-art ML models in pathology and radiology while remaining compliant with the DICOM standard and interoperable with clinical systems at all stages. To promote standardization of ML research and streamline the ML model development and deployment process, we made the library available free and open-source.
△ Less
Submitted 8 May, 2022; v1 submitted 14 June, 2021;
originally announced June 2021.
-
Early Abandoning and Pruning for Elastic Distances including Dynamic Time Warping
Authors:
Matthieu Herrmann,
Geoffrey I. Webb
Abstract:
Nearest neighbor search under elastic distances is a key tool for time series analysis, supporting many applications. However, straightforward implementations of distances require $O(n^2)$ space and time complexities, preventing these applications from scaling to long series. Much work has been devoted to speeding up the NN search process, mostly with the development of lower bounds, allowing to a…
▽ More
Nearest neighbor search under elastic distances is a key tool for time series analysis, supporting many applications. However, straightforward implementations of distances require $O(n^2)$ space and time complexities, preventing these applications from scaling to long series. Much work has been devoted to speeding up the NN search process, mostly with the development of lower bounds, allowing to avoid costly distance computations when a given threshold is exceeded. This threshold, provided by the similarity search process, also allows to early abandon the computation of a distance itself. Another approach, is to prune parts of the computation. All these techniques are othogonal to each other. In this work, we develop a new generic strategy, "EAPruned", that tightly integrates pruning with early abandoning. We apply it to six elastic distance measures: DTW, CDTW, WDTW, ERP, MSM and TWE, showing substantial speedup in NN search applications. Pruning alone also shows substantial speedup for some distances, benefiting applications beyond the scope of NN search (e.g. requiring all pairwise distances), and hence where early abandoning is not applicable. We~release our implementation as part of a new C++ library for time series classification, along with easy to use Python/Numpy bindings.
△ Less
Submitted 2 June, 2021; v1 submitted 9 February, 2021;
originally announced February 2021.
-
Linking Labs: Interconnecting Experimental Environments
Authors:
Tanja Schultz,
Felix Putze,
Thorsten Fehr,
Moritz Meier,
Celeste Mason,
Florian Ahrens,
Manfred Herrmann
Abstract:
We introduce the concept of LabLinking: a technology-based interconnection of experimental laboratories across institutions, disciplines, cultures, languages, and time zones - in other words experiments without borders. In particular, we introduce LabLinking levels (LLL), which define the degree of tightness of empirical interconnection between labs. We describe the technological infrastructure in…
▽ More
We introduce the concept of LabLinking: a technology-based interconnection of experimental laboratories across institutions, disciplines, cultures, languages, and time zones - in other words experiments without borders. In particular, we introduce LabLinking levels (LLL), which define the degree of tightness of empirical interconnection between labs. We describe the technological infrastructure in terms of hard- and software required for the respective LLLs and present examples of linked laboratories along with insights about the challenges and benefits. In sum, we argue that linked labs provide a unique platform for a continuous exchange between scientists and experimenters, thereby enabling a time synchronous execution of experiments performed with and by decentralized user and researchers, improving outreach and ease of subject recruitment, allowing to establish new experimental designs and to incorporate a panoply of complementary biosensors, devices, hard- and software solutions.
△ Less
Submitted 6 February, 2021;
originally announced February 2021.
-
Unsupervised Functional Data Analysis via Nonlinear Dimension Reduction
Authors:
Moritz Herrmann,
Fabian Scheipl
Abstract:
In recent years, manifold methods have moved into focus as tools for dimension reduction. Assuming that the high-dimensional data actually lie on or close to a low-dimensional nonlinear manifold, these methods have shown convincing results in several settings. This manifold assumption is often reasonable for functional data, i.e., data representing continuously observed functions, as well. However…
▽ More
In recent years, manifold methods have moved into focus as tools for dimension reduction. Assuming that the high-dimensional data actually lie on or close to a low-dimensional nonlinear manifold, these methods have shown convincing results in several settings. This manifold assumption is often reasonable for functional data, i.e., data representing continuously observed functions, as well. However, the performance of manifold methods recently proposed for tabular or image data has not been systematically assessed in the case of functional data yet. Moreover, it is unclear how to evaluate the quality of learned embeddings that do not yield invertible mappings, since the reconstruction error cannot be used as a performance measure for such representations. In this work, we describe and investigate the specific challenges for nonlinear dimension reduction posed by the functional data setting. The contributions of the paper are three-fold: First of all, we define a theoretical framework which allows to systematically assess specific challenges that arise in the functional data context, transfer several nonlinear dimension reduction methods for tabular and image data to functional data, and show that manifold methods can be used successfully in this setting. Secondly, we subject performance assessment and tuning strategies to a thorough and systematic evaluation based on several different functional data settings and point out some previously undescribed weaknesses and pitfalls which can jeopardize reliable judgment of embedding quality. Thirdly, we propose a nuanced approach to make trustworthy decisions for or against competing nonconforming embeddings more objectively.
△ Less
Submitted 22 December, 2020;
originally announced December 2020.
-
LMB Filter Based Tracking Allowing for Multiple Hypotheses in Object Reference Point Association*
Authors:
Martin Herrmann,
Aldi Piroli,
Jan Strohbeck,
Johannes Müller,
Michael Buchholz
Abstract:
Autonomous vehicles need precise knowledge on dynamic objects in their surroundings. Especially in urban areas with many objects and possible occlusions, an infrastructure system based on a multi-sensor setup can provide the required environment model for the vehicles. Previously, we have published a concept of object reference points (e.g. the corners of an object), which allows for generic senso…
▽ More
Autonomous vehicles need precise knowledge on dynamic objects in their surroundings. Especially in urban areas with many objects and possible occlusions, an infrastructure system based on a multi-sensor setup can provide the required environment model for the vehicles. Previously, we have published a concept of object reference points (e.g. the corners of an object), which allows for generic sensor "plug and play" interfaces and relatively cheap sensors. This paper describes a novel method to additionally incorporate multiple hypotheses for fusing the measurements of the object reference points using an extension to the previously presented Labeled Multi-Bernoulli (LMB) filter. In contrast to the previous work, this approach improves the tracking quality in the cases where the correct association of the measurement and the object reference point is unknown. Furthermore, this paper identifies options based on physical models to sort out inconsistent and unfeasible associations at an early stage in order to keep the method computationally tractable for real-time applications. The method is evaluated on simulations as well as on real scenarios. In comparison to comparable methods, the proposed approach shows a considerable performance increase, especially the number of non-continuous tracks is decreased significantly.
△ Less
Submitted 11 November, 2020;
originally announced November 2020.
-
Early Abandoning PrunedDTW and its application to similarity search
Authors:
Matthieu Herrmann,
Geoffrey I. Webb
Abstract:
The Dynamic Time Warping ("DTW") distance is widely used in time series analysis, be it for classification, clustering or similarity search. However, its quadratic time complexity prevents it from scaling. Strategies, based on early abandoning DTW or skipping its computation altogether thanks to lower bounds, have been developed for certain use cases such as nearest neighbour search. But vectoriza…
▽ More
The Dynamic Time Warping ("DTW") distance is widely used in time series analysis, be it for classification, clustering or similarity search. However, its quadratic time complexity prevents it from scaling. Strategies, based on early abandoning DTW or skipping its computation altogether thanks to lower bounds, have been developed for certain use cases such as nearest neighbour search. But vectorization and approximation aside, no advance was made on DTW itself until recently with the introduction of PrunedDTW. This algorithm, able to prune unpromising alignments, was later fitted with early abandoning. We present a new version of PrunedDTW, "EAPrunedDTW", designed with early abandon in mind from the start, and able to early abandon faster than before. We show that EAPrunedDTW significantly improves the computation time of similarity search in the UCR Suite, and renders lower bounds dispensable.
△ Less
Submitted 11 October, 2020;
originally announced October 2020.
-
Evolutionary Selective Imitation: Interpretable Agents by Imitation Learning Without a Demonstrator
Authors:
Roy Eliya,
J. Michael Herrmann
Abstract:
We propose a new method for training an agent via an evolutionary strategy (ES), in which we iteratively improve a set of samples to imitate: Starting with a random set, in every iteration we replace a subset of the samples with samples from the best trajectories discovered so far. The evaluation procedure for this set is to train, via supervised learning, a randomly initialised neural network (NN…
▽ More
We propose a new method for training an agent via an evolutionary strategy (ES), in which we iteratively improve a set of samples to imitate: Starting with a random set, in every iteration we replace a subset of the samples with samples from the best trajectories discovered so far. The evaluation procedure for this set is to train, via supervised learning, a randomly initialised neural network (NN) to imitate the set and then execute the acquired policy against the environment. Our method is thus an ES based on a fitness function that expresses the effectiveness of imitating an evolving data subset. This is in contrast to other ES techniques that iterate over the weights of the policy directly. By observing the samples that the agent selects for learning, it is possible to interpret and evaluate the evolving strategy of the agent more explicitly than in NN learning. In our experiments, we trained an agent to solve the OpenAI Gym environment Bipedalwalker-v3 by imitating an evolutionarily selected set of only 25 samples with a NN with only a few thousand parameters. We further test our method on the Procgen game Plunder and show here as well that the proposed method is an interpretable, small, robust and effective alternative to other ES or policy gradient methods.
△ Less
Submitted 17 September, 2020;
originally announced September 2020.
-
Large-scale benchmark study of survival prediction methods using multi-omics data
Authors:
Moritz Herrmann,
Philipp Probst,
Roman Hornung,
Vindi Jurinovic,
Anne-Laure Boulesteix
Abstract:
Multi-omics data, that is, datasets containing different types of high-dimensional molecular variables (often in addition to classical clinical variables), are increasingly generated for the investigation of various diseases. Nevertheless, questions remain regarding the usefulness of multi-omics data for the prediction of disease outcomes such as survival time. It is also unclear which methods are…
▽ More
Multi-omics data, that is, datasets containing different types of high-dimensional molecular variables (often in addition to classical clinical variables), are increasingly generated for the investigation of various diseases. Nevertheless, questions remain regarding the usefulness of multi-omics data for the prediction of disease outcomes such as survival time. It is also unclear which methods are most appropriate to derive such prediction models. We aim to give some answers to these questions by means of a large-scale benchmark study using real data. Different prediction methods from machine learning and statistics were applied on 18 multi-omics cancer datasets from the database "The Cancer Genome Atlas", containing from 35 to 1,000 observations and from 60,000 to 100,000 variables. The considered outcome was the (censored) survival time. Twelve methods based on boosting, penalized regression and random forest were compared, comprising both methods that do and that do not take the group structure of the omics variables into account. The Kaplan-Meier estimate and a Cox model using only clinical variables were used as reference methods. The methods were compared using several repetitions of 5-fold cross-validation. Uno's C-index and the integrated Brier-score served as performance metrics. The results show that, although multi-omics data can improve the prediction performance, this is not generally the case. Only the method block forest slightly outperformed the Cox model on average over all datasets. Taking into account the multi-omics structure improves the predictive performance and protects variables in low-dimensional groups - especially clinical variables - from not being included in the model. All analyses are reproducible using freely available R code.
△ Less
Submitted 7 March, 2020;
originally announced March 2020.
-
BARD: A structured technique for group elicitation of Bayesian networks to support analytic reasoning
Authors:
Ann E. Nicholson,
Kevin B. Korb,
Erik P. Nyberg,
Michael Wybrow,
Ingrid Zukerman,
Steven Mascaro,
Shreshth Thakur,
Abraham Oshni Alvandi,
Jeff Riley,
Ross Pearson,
Shane Morris,
Matthieu Herrmann,
A. K. M. Azad,
Fergus Bolger,
Ulrike Hahn,
David Lagnado
Abstract:
In many complex, real-world situations, problem solving and decision making require effective reasoning about causation and uncertainty. However, human reasoning in these cases is prone to confusion and error. Bayesian networks (BNs) are an artificial intelligence technology that models uncertain situations, supporting probabilistic and causal reasoning and decision making. However, to date, BN me…
▽ More
In many complex, real-world situations, problem solving and decision making require effective reasoning about causation and uncertainty. However, human reasoning in these cases is prone to confusion and error. Bayesian networks (BNs) are an artificial intelligence technology that models uncertain situations, supporting probabilistic and causal reasoning and decision making. However, to date, BN methodologies and software require significant upfront training, do not provide much guidance on the model building process, and do not support collaboratively building BNs. BARD (Bayesian ARgumentation via Delphi) is both a methodology and an expert system that utilises (1) BNs as the underlying structured representations for better argument analysis, (2) a multi-user web-based software platform and Delphi-style social processes to assist with collaboration, and (3) short, high-quality e-courses on demand, a highly structured process to guide BN construction, and a variety of helpful tools to assist in building and reasoning with BNs, including an automated explanation tool to assist effective report writing. The result is an end-to-end online platform, with associated online training, for groups without prior BN expertise to understand and analyse a problem, build a model of its underlying probabilistic causal structure, validate and reason with the causal model, and use it to produce a written analytic report. Initial experimental results demonstrate that BARD aids in problem solving, reasoning and collaboration.
△ Less
Submitted 2 March, 2020;
originally announced March 2020.
-
LACI: Low-effort Automatic Calibration of Infrastructure Sensors
Authors:
Johannes Müller,
Martin Herrmann,
Jan Strohbeck,
Vasileios Belagiannis,
Michael Buchholz
Abstract:
Sensor calibration usually is a time consuming yet important task. While classical approaches are sensor-specific and often need calibration targets as well as a widely overlapping field of view (FOV), within this work, a cooperative intelligent vehicle is used as callibration target. The vehicleis detected in the sensor frame and then matched with the information received from the cooperative awa…
▽ More
Sensor calibration usually is a time consuming yet important task. While classical approaches are sensor-specific and often need calibration targets as well as a widely overlapping field of view (FOV), within this work, a cooperative intelligent vehicle is used as callibration target. The vehicleis detected in the sensor frame and then matched with the information received from the cooperative awareness messagessend by the coperative intelligent vehicle. The presented algorithm is fully automated as well as sensor-independent, relying only on a very common set of assumptions. Due to the direct registration on the world frame, no overlapping FOV is necessary. The algorithm is evaluated through experiment for four laserscanners as well as one pair of stereo cameras showing a repetition error within the measurement uncertainty of the sensors. A plausibility check rules out systematic errors that might not have been covered by evaluating the repetition error.
△ Less
Submitted 5 November, 2019;
originally announced November 2019.
-
Lagged correlation-based deep learning for directional trend change prediction in financial time series
Authors:
Ben Moews,
J. Michael Herrmann,
Gbenga Ibikunle
Abstract:
Trend change prediction in complex systems with a large number of noisy time series is a problem with many applications for real-world phenomena, with stock markets as a notoriously difficult to predict example of such systems. We approach predictions of directional trend changes via complex lagged correlations between them, excluding any information about the target series from the respective inp…
▽ More
Trend change prediction in complex systems with a large number of noisy time series is a problem with many applications for real-world phenomena, with stock markets as a notoriously difficult to predict example of such systems. We approach predictions of directional trend changes via complex lagged correlations between them, excluding any information about the target series from the respective inputs to achieve predictions purely based on such correlations with other series. We propose the use of deep neural networks that employ step-wise linear regressions with exponential smoothing in the preparatory feature engineering for this task, with regression slopes as trend strength indicators for a given time interval. We apply this method to historical stock market data from 2011 to 2016 as a use case example of lagged correlations between large numbers of time series that are heavily influenced by externally arising new information as a random factor. The results demonstrate the viability of the proposed approach, with state-of-the-art accuracies and accounting for the statistical significance of the results for additional validation, as well as important implications for modern financial economics.
△ Less
Submitted 29 November, 2018; v1 submitted 27 November, 2018;
originally announced November 2018.
-
The Voynich Manuscript is Written in Natural Language: The Pahlavi Hypothesis
Authors:
J. Michael Herrmann
Abstract:
The late medieval Voynich Manuscript (VM) has resisted decryption and was considered a meaningless hoax or an unsolvable cipher. Here, we provide evidence that the VM is written in natural language by establishing a relation of the Voynich alphabet and the Iranian Pahlavi script. Many of the Voynich characters are upside-down versions of their Pahlavi counterparts, which may be an effect of differ…
▽ More
The late medieval Voynich Manuscript (VM) has resisted decryption and was considered a meaningless hoax or an unsolvable cipher. Here, we provide evidence that the VM is written in natural language by establishing a relation of the Voynich alphabet and the Iranian Pahlavi script. Many of the Voynich characters are upside-down versions of their Pahlavi counterparts, which may be an effect of different writing directions. Other Voynich letters can be explained as ligatures or departures from Pahlavi with the intent to cope with known problems due to the stupendous ambiguity of Pahlavi text. While a translation of the VM text is not attempted here, we can confirm the Voynich-Pahlavi relation at the character level by the transcription of many words from the VM illustrations and from parts of the main text. Many of the transcribed words can be identified as terms from Zoroastrian cosmology which is in line with the use of Pahlavi script in Zoroastrian communities from medieval times.
△ Less
Submitted 6 October, 2017; v1 submitted 5 September, 2017;
originally announced September 2017.
-
On the dependent conjunction and implication
Authors:
Matthieu Herrmann,
Alain Prouté
Abstract:
We give a theoretical model of conjunctions $E\wedge F$ and implications $E\implies F$ where $F$ is meaningful only when $E$ is true, a situation which is very often encountered in everyday mathematics, and which was already formalized by several type theorists. We present a version of these concepts which should be more attractive for mathematicians and in particular for non logicians, by using a…
▽ More
We give a theoretical model of conjunctions $E\wedge F$ and implications $E\implies F$ where $F$ is meaningful only when $E$ is true, a situation which is very often encountered in everyday mathematics, and which was already formalized by several type theorists. We present a version of these concepts which should be more attractive for mathematicians and in particular for non logicians, by using an extension of Lawvere's definition of the quantifiers. We explain the link of this phenomenon with the principle of description, why this dependency is obtained through the use of a "hidden" variable, and more generally the link of these concepts with the vernacular language of mathematics, which is actually our main motivation. Despite its links with topos theory, this article is readable by non specialists.
△ Less
Submitted 9 May, 2018; v1 submitted 20 June, 2016;
originally announced June 2016.
-
Critical Parameters in Particle Swarm Optimisation
Authors:
J. Michael Herrmann,
Adam Erskine,
Thomas Joyce
Abstract:
Particle swarm optimisation is a metaheuristic algorithm which finds reasonable solutions in a wide range of applied problems if suitable parameters are used. We study the properties of the algorithm in the framework of random dynamical systems which, due to the quasi-linear swarm dynamics, yields analytical results for the stability properties of the particles. Such considerations predict a relat…
▽ More
Particle swarm optimisation is a metaheuristic algorithm which finds reasonable solutions in a wide range of applied problems if suitable parameters are used. We study the properties of the algorithm in the framework of random dynamical systems which, due to the quasi-linear swarm dynamics, yields analytical results for the stability properties of the particles. Such considerations predict a relationship between the parameters of the algorithm that marks the edge between convergent and divergent behaviours. Comparison with simulations indicates that the algorithm performs best near this margin of instability.
△ Less
Submitted 19 November, 2015;
originally announced November 2015.
-
CriPS: Critical Dynamics in Particle Swarm Optimization
Authors:
Adam Erskine,
J Michael Herrmann
Abstract:
Particle Swarm Optimisation (PSO) makes use of a dynamical system for solving a search task. Instead of adding search biases in order to improve performance in certain problems, we aim to remove algorithm-induced scales by controlling the swarm with a mechanism that is scale-free except possibly for a suppression of scales beyond the system size. In this way a very promising performance is achieve…
▽ More
Particle Swarm Optimisation (PSO) makes use of a dynamical system for solving a search task. Instead of adding search biases in order to improve performance in certain problems, we aim to remove algorithm-induced scales by controlling the swarm with a mechanism that is scale-free except possibly for a suppression of scales beyond the system size. In this way a very promising performance is achieved due to the balance of large-scale exploration and local search. The resulting algorithm shows evidence for self-organised criticality, brought about via the intrinsic dynamics of the swarm as it interacts with the objective function, rather than being explicitly specified. The Critical Particle Swarm (CriPS) can be easily combined with many existing extensions such as chaotic exploration, additional force terms or non-trivial topologies.
△ Less
Submitted 27 February, 2014;
originally announced February 2014.