Search NASA⌕ Search

Engineering topics

Kay, Bill

Publications and source records attributed to Kay, Bill.

At least 19 records

Community detection in hypergraphs via mutual information maximization

Abstract The hypergraph community detection problem seeks to identify groups of related vertices in hypergraph data. We propose an information-theoretic hypergraph community detection algorithm which compresses the observed data in terms of community labels and community-edge intersections. This algorithm can also be viewed as maximum-likelihood inference in a degree-corrected microcanonical stochastic blockmodel. We perform the compression/inference step via simulated annealing. Unlike several recent algorithms based on canonical models, our microcanonical algorithm does not require inference of statistical parameters such as vertex degrees or pairwise group connection rates. Through synthetic experiments, we find that our algorithm succeeds down to recently-conjectured thresholds for sparse random hypergraphs. We also find competitive performance in cluster recovery tasks on several hypergraph data sets.

97 MATHEMATICS AND COMPUTING↗

A comprehensive guide to CAN IDS data and introduction of the ROAD dataset

Although ubiquitous in modern vehicles, Controller Area Networks (CANs) lack basic security properties and are easily exploitable. A rapidly growing field of CAN security research has emerged that seeks to detect intrusions or anomalies on CANs. Producing vehicular CAN data with a variety of intrusions is a difficult task for most researchers as it requires expensive assets and deep expertise. To illuminate this task, we introduce the first comprehensive guide to the existing open CAN intrusion detection system (IDS) datasets. We categorize attacks on CANs including fabrication (adding frames, e.g., flooding or targeting and ID), suspension (removing an ID’s frames), and masquerade attacks (spoofed frames sent in lieu of suspended ones). We provide a quality analysis of each dataset; an enumeration of each datasets’ attacks, benefits, and drawbacks; categorization as real vs. simulated CAN data and real vs. simulated attacks; whether the data is raw CAN data or signal-translated; number of vehicles/CANs; quantity in terms of time; and finally a suggested use case of each dataset. State-of-the-art public CAN IDS datasets are limited to real fabrication (simple message injection) attacks and simulated attacks often in synthetic data, lacking fidelity. In general, the physical effects of attacks on the vehicle are not verified in the available datasets. Only one dataset provides signal-translated data but is missing a corresponding “raw” binary version. This issue pigeon-holes CAN IDS research into testing on limited and often inappropriate data (usually with attacks that are too easily detectable to truly test the method). The scarcity of appropriate data has stymied comparability and reproducibility of results for researchers. As our primary contribution, we present the Real ORNL Automotive Dynamometer (ROAD) CAN IDS dataset, consisting of over 3.5 hours of one vehicle’s CAN data. ROAD contains ambient data recorded during a diverse set of activities, and attacks of increasing stealth with multiple variants and instances of real (i.e. non-simulated) fuzzing, fabrication, unique advanced attacks, and simulated masquerade attacks. To facilitate a benchmark for CAN IDS methods that require signal-translated inputs, we also provide the signal time series format for many of the CAN captures. Our contributions aim to facilitate appropriate benchmarking and needed comparability in the CAN IDS research field.

97 MATHEMATICS AND COMPUTING↗

Seven open problems in applied combinatorics

We present and discuss seven different open problems in applied combinatorics. Additionally, the application areas relevant to this compilation include quantum computing, algorithmic differentiation, topological data analysis, iterative methods, hypergraph cut algorithms, and power systems.

97 MATHEMATICS AND COMPUTING↗

Similarity Downselection: Finding the n Most Dissimilar Molecular Conformers for Reference-Free Metabolomics

Computational methods for creating in silico libraries of molecular descriptors (e.g., collision cross sections) are becoming increasingly prevalent due to the limited number of authentic reference materials available for traditional library building. These so-called “reference-free metabolomics” methods require sampling sets of molecular conformers in order to produce high accuracy property predictions. Due to the computational cost of the subsequent calculations for each conformer, there is a need to sample the most relevant subset and avoid repeating calculations on conformers that are nearly identical. The goal of this study is to introduce a heuristic method of finding the most dissimilar conformers from a larger population in order to help speed up reference-free calculation methods and maintain a high property prediction accuracy. Finding the set of the n items most dissimilar from each other out of a larger population becomes increasingly difficult and computationally expensive as either n or the population size grows large. Because there exists a pairwise relationship between each item and all other items in the population, finding the set of the n most dissimilar items is different than simply sorting an array of numbers. For instance, if you have a set of the most dissimilar n = 4 items, one or more of the items from n = 4 might not be in the set n = 5. An exact solution would have to search all possible combinations of size n in the population exhaustively. We present an open-source software called similarity downselection (SDS), written in Python and freely available on GitHub. SDS implements a heuristic algorithm for quickly finding the approximate set(s) of the n most dissimilar items. We benchmark SDS against a Monte Carlo method, which attempts to find the exact solution through repeated random sampling. We show that for SDS to find the set of n most dissimilar conformers, our method is not only orders of magnitude faster, but it is also more accurate than running Monte Carlo for 1,000,000 iterations, each searching for set sizes n = 3–7 out of a population of 50,000. We also benchmark SDS against the exact solution for example small populations, showing that SDS produces a solution close to the exact solution in these instances. Using theoretical approaches, we also demonstrate the constraints of the greedy algorithm and its efficacy as a ratio to the exact solution.

97 MATHEMATICS AND COMPUTING↗

A review of non-cognitive applications for neuromorphic computing

Abstract Though neuromorphic computers have typically targeted applications in machine learning and neuroscience (‘cognitive’ applications), they have many computational characteristics that are attractive for a wide variety of computational problems. In this work, we review the current state-of-the-art for non-cognitive applications on neuromorphic computers, including simple computational kernels for composition, graph algorithms, constrained optimization, and signal processing. We discuss the advantages of using neuromorphic computers for these different applications, as well as the challenges that still remain. The ultimate goal of this work is to bring awareness to this class of problems for neuromorphic systems to the broader community, particularly to encourage further work in this area and to make sure that these applications are considered in the design of future neuromorphic systems.

97 MATHEMATICS AND COMPUTING↗

Avoiding excess computation in asynchronous evolutionary algorithms

Abstract Asynchronous evolutionary algorithms are becoming increasingly popular as a means of making full use of many processors while solving computationally expensive search and optimization problems. These algorithms excel at keeping large clusters fully utilized, but may sometimes inefficiently sample an excess of fast‐evaluating solutions at the expense of higher‐quality, slow‐evaluating ones. We have previously introduced a steady‐state parent selection strategy, SWEET (“Selection whilE EvaluaTing”), that sometimes selects individuals that are still being evaluated and allows them to reproduce early. We perform a takeover‐time analysis that confirms that this strategy gives slow‐evaluating individuals that have higher fitnesses an increased ability to multiply in the population. We also find that SWEET appears effective at improving optimization performance on problems in which solution quality is positively correlated with evaluation time. We evaluate our approach on six simulated real‐valued optimization problems and three real‐world applications: an autonomous vehicle controller problem that involves tuning a spiking neural network and two adversarial EA problems. We further evaluate SWEET versus a basic asynchronous process in a simulated setting. We present evidence that SWEET outperforms basic asynchronous processes in a use‐case in which performance is positively correlated with evaluation time, and performs comparably (and often better) than basic asynchronous processes in several use‐cases where performance is negatively correlated with evaluation time. That said, in the cases where performance and evaluation time are negatively correlated the variance of outcomes for SWEET is notably high.

97 MATHEMATICS AND COMPUTING↗

Neuromorphic Computing is Turing-Complete

Neuromorphic computing is a non-von Neumann computing paradigm that performs computation by emulating the human brain. Neuromorphic systems are extremely energy-efficient and known to consume thousands of times less power than CPUs and GPUs. They have the potential to drive critical use cases such as autonomous vehicles, edge computing and internet of things in the future. For this reason, they are sought to be an indispensable part of the future computing landscape. Neuromorphic systems are mainly used for spike-based machine learning applications, although there are some non-machine learning applications in graph theory, differential equations, and spike-based simulations. These applications suggest that neuromorphic computing might be capable of general-purpose computing. However, general-purpose computability of neuromorphic computing has not been established yet. In this work, we prove that neuromorphic computing is Turing-complete and therefore capable of general-purpose computing. Specifically, we present a model of neuromorphic computing, with just two neuron parameters (threshold and leak), and two synaptic parameters (weight and delay). We devise neuromorphic circuits for computing all the μ-recursive functions (i.e., constant, successor and projection functions) and all the μ-recursive operators (i.e., composition, primitive recursion and minimization operators). Given that the μ-recursive functions and operators are precisely the ones that can be computed using a Turing machine, this work establishes the Turing-completeness of neuromorphic computing.

Date, Prasanna↗

Threshold progressions in covering and packing contexts

Here, using standard methods (due to Janson, Stein–Chen, and Talagrand) from probabilistic combinatorics, we explore the following general theme: As one progresses from each member of a family of objects $\mathcal{A}$ being “covered” by at most one object in a random collection $\mathcal{C}$, to being covered at most λ times, to being covered at least once, to being covered at least λ times, a hierarchy of thresholds emerge. We will use examples from extremal set theory, combinatorics, and additive number theory to see how these results vary according to the context, and level of dependence introduced.

97 MATHEMATICS AND COMPUTING↗

Models and Methods for Sparse (Hyper)Network Science in Business, Industry, and Government

The authors are hosting an AMS sponsored Mathematics Research Community (MRC) focusing on two themes that have garnered intense attention in network models of complex relational data: (1) how to faithfully model multi-way relations in hypergraphs, rather than only pairwise interactions in graphs; and (2) challenges posed by modelling networks with extreme sparsity. Here we introduce and explore these two themes and their challenges. In this work, we hope to generate interest from researchers in pure and applied mathematics and computer science.

97 MATHEMATICS AND COMPUTING↗

Opportunities for neuromorphic computing algorithms and applications

Neuromorphic computing technologies will be important for the future of computing, but much of the work in neuromorphic computing has focused on hardware development. In this study, we review recent results in neuromorphic computing algorithms and applications. We highlight characteristics of neuromorphic computing technologies that make them attractive for the future of computing and we discuss opportunities for future development of algorithms and applications on these systems.

97 MATHEMATICS AND COMPUTING↗

Efficient Contingency Analysis in Power Systems via Network Trigger Nodes

Modeling failure dynamics within a power system is a complex and challenging process due to multiple inter-dependencies and convoluted inter-domain relationships. Subject matter experts (SMEs) are interested in understanding these failure dynamics for reducing the impact from future disasters (i.e., losses or failures of power system components, such as transmission lines). Contingency analysis (CA) tools enable such ’what-if’ scenario analyses to evaluate the impacts on the power system. Analyzing all possible contingencies among N system components can be computationally expensive. An important step for performing CA is identifying a set of k ‘trigger’ components, which when failed initially can significantly impact the overall system by causing multiple failures. Currently SMEs focus on identifying these trigger components by running expensive simulations on all possible subsets, which quickly becomes infeasible. Hence finding a relevant set of trigger components (contingencies) rapidly to enable efficient and useful CA is crucial.In a collaboration between computer scientists and power system experts, we propose an efficient method for performing CA by exploiting network inter-dependencies in power system components. First, we construct a network with multiple electric grid infrastructure components and dependencies as connections among them. We reformulate the problem of finding a set of trigger components as a problem of identifying critical nodes in the network, which can cascade power failures through connected nodes and cause significant damage to the network. To guide the practical CA tools, we develop a network-based model with a probabilistic edge-weights setup using intricate domain rules. Then we conduct an empirical study on real power system data in the US for both regional and national levels. Firstly, we use power system datasets for the US to create a national-scale domain-driven model. Secondly, we demonstrate that network-based model outperforms the outputs from a real CA tool and show on average 25 × improved selection of contingencies, thereby showcasing practical benefits to the power experts.

Tabassum, Anika↗

Identification of Critical Infrastructure via PageRank

Assessing critical infrastructure vulnerabilities is paramount to arranging efficient plans for their protection. Critical infrastructures are cyber-physical systems that can be represented as a network consisting of nodes and edges and highly interdependent in nature. Given the interdependent nature of critical infrastuctures, failure in one node may cause failure in many others resulting in a cascade of failures. In this paper, we propose a node criticality metric that uses Google’s PageRank algorithm to identify nodes that are likely to fail (are vulnerable), nodes whose failure may cascade to many other sites in the network (are important), and nodes that are both vulnerable and important (are critical). We then present a series of experiments to understand how protecting certain critical nodes can help mitigate massive cascading failures. Simulating failures in a real-world network with and without critical node protections demonstrates the importance of identifying critical nodes in an infrastructure network.

Kay, Bill↗

Avoiding Excess Computation in Asynchronous Evolutionary Algorithms

Asynchronous evolutionary algorithms are becoming increasingly popular as a means of making full use of many processors while solving computationally expensive search and optimization problems. These algorithms excel at keeping large clusters fully utilized, but may sometimes inefficiently sample an excess of fast-evaluating solutions at the expense of higher-quality, slow-evaluating ones. We introduce a steady-state parent selection strategy, SWEET (“Selection whilE EvaluaTing”), that sometimes selects individuals that are still being evaluated and allows them to reproduce early. This gives slow-evaluating individuals that have higher fitnesses an increased ability to multiply in the population. We find that SWEET appears effective in simulated take-over time analysis, but that its benefit is confined mostly to early in the run, and our preliminary study on an autonomous vehicle controller problem that involves tuning a spiking neural network proves inconclusive.

Scott, Eric↗

Computational Complexity of Neuromorphic Algorithms

Neuromorphic computing has several characteristics that make it an extremely compelling computing paradigm for post Moore computation. Some of these characteristics include intrinsic parallelism, inherent scalability, collocated processing and memory, and event-driven computation. While these characteristics impart energy efficiency to neuromorphic systems, they do come with their own set of challenges. One of the biggest challenges in neuromorphic computing is to establish the theoretical underpinnings of the computational complexity of neuromorphic algorithms. In this paper, we take the first steps towards defining the space and time complexity of neuromorphic algorithms. Specifically, we describe a model of neuromorphic computation and state the assumptions that govern the computational complexity of neuromorphic algorithms. Next, we present a theoretical framework to define the computational complexity of a neuromorphic algorithm. We explicitly define what space and time complexities mean in the context of neuromorphic algorithms based on our model of neuromorphic computation. Finally, we leverage our approach and define the computational complexities of six neuromorphic algorithms: constant function, successor function, predecessor function, projection function, neuromorphic sorting algorithm and neighborhood subgraph extraction algorithm.

Date, Prasanna↗

Neuromorphic Graph Algorithms: Cycle Detection, Odd Cycle Detection, and Max Flow

Neuromorphic computing is poised to become a promising computing paradigm in the post Moore’s law era due to its extremely low power usage and inherent parallelism. Spiking neural networks are the traditional use case for neuromorphic systems, and have proven to be highly effective at machine learning tasks such as control problems. More recently, neuromorphic systems have been applied outside of the arena of machine learning, primarily in the field of graph algorithms. Neuromorphic systems have been shown to perform graph algorithms faster and with lower power consumption than their traditional (GPU/CPU) counterparts, and are hence an attractive option for a co-processing unit in future high performance computing systems, where graph algorithms play a critical role. In this paper, we present a neuromorphic implementation of cycle detection, odd cycle detection, and the Ford-Fulkerson max-flow algorithm. We further evaluate the performance of these implementations using the NEST neuromorphic simulator by using spike counts and simulation time as proxies for energy consumption and run time. In addition to gains inherent in neuromorphic systems, we show that within the neuromorphic implementations early stopping criteria can be implemented to further improve performance.

Kay, Bill↗

Improved Bounds for Burning Fence Graphs

Graph burning studies how fast a contagion, modeled as a set of fires, spreads in a graph. The burning process takes place in synchronous, discrete rounds. In each round, a fire breaks out at a vertex, and the fire spreads to all vertices that are adjacent to a burning vertex. Additionally, the burning number of a graph G is the minimum number of rounds necessary for each vertex of G to burn. We consider the burning number of the \(m \times n\) Cartesian grid graphs, written \(G_{m,n}\) . For \(m = \omega (\sqrt{n})\) , the asymptotic value of the burning number of \(G_{m,n}\) was determined, but only the growth rate of the burning number was investigated in the case \(m = O(\sqrt{n})\) , which we refer to as fence graphs. We provide new explicit bounds on the burning number of fence graphs \(G_{c\sqrt{n},n}\) , where \(c > 0\) .

79 ASTRONOMY AND ASTROPHYSICS↗

Accurate and Accelerated Neuromorphic Network Design Leveraging A Bayesian Hyperparameter Pareto Optimization Approach

Neuromorphic systems allow for extremely efficient hardware implementations for neural networks (NNs). In recent years, several algorithms have been presented to train spiking NNs (SNNs) for neuromorphic hardware. However, SNNs often provide lower accuracy than their artificial NNs (ANNs) counterparts or require computationally expensive and slow training/inference methods. To close this gap, designers typically rely on reconfiguring SNNs through adjustments in the neuron/synapse model or training algorithm itself. Nevertheless, these steps incur significant design time, while still lacking the desired improvement in terms of training/inference times (latency). Designing SNNs that can mimic the accuracy of ANNs with reasonable training times is an exigent challenge in neuromorphic computing. In this work, we present an alternative approach that looks at such designs as an optimization problem rather than algorithm or architecture redesign. We develop a versatile multiobjective hyperparameter optimization (HPO) for automatically tuning HPs of two state-of-the-art SNN training algorithms, SLAYER and HYBRID. We emphasize that, to the best of our knowledge, this is the first work trying to improve SNNs’ computational efficiency, accuracy, and training time using an efficient HPO. We demonstrate significant performance improvements for SNNs on several datasets without the need to redesign or invent new training algorithms/architectures. Our approach results in more accurate networks with lower latency and, in turn, higher energy efficiency than previous implementations. In particular, we demonstrate improvement in accuracy and more than 5× reduction in the training/inference time for the SLAYER algorithm on the DVS Gesture dataset. In the case of HYBRID, we demonstrate 30% reduction in timesteps while surpassing the accuracy of the state-of-the-art networks on CIFAR10. Further, our analysis suggests that even a seemingly minor change in HPs could change the accuracy by 5 - 6×.

Parsa, Maryam↗

Sparse Binary Matrix-Vector Multiplication on Neuromorphic Computers

Neuromorphic computers offer the opportunity for low-power, efficient computation. Though they have been primarily applied to neural network tasks, there is also the opportunity to leverage the inherent characteristics of neuromorphic computers (low power, massive parallelism, collocated processing and memory) to perform non-neural network tasks. Here, we demonstrate how an approach for performing sparse binary matrix-vector multiplication on neuromorphic computers. We describe the approach, which relies on the connection between binary matrix-vector multiplication and breadth first search, and we introduce the algorithm for performing this calculation in a neuromorphic way. We validate the approach in simulation. Finally, we provide a discussion of the runtime of this algorithm and discuss where neuromorphic computers in the future may have a computational advantage when performing this computation.

Schuman, Catherine↗