OpenRaiser/Intern-Atlas huggingface dataset:
Smoke Testing for Machine Learning: Simple Tests to Discover Severe Defects
Venue: arXiv cs.SE 2021
Year: 2021

Machine learning is nowadays a standard technique for data analysis within software applications. Software engineers need quality assurance techniques that are suitable for these new kinds of systems. Within this article, we discuss the question whether standard software testing techniques that have been part of textbooks since decades are also useful for the testing of machine learning software. Concretely, we try to determine generic and simple smoke tests that can be used to assert that basic functions can be executed without crashing. We found that we can derive such tests using techniques similar to equivalence classes and boundary value analysis. Moreover, we found that these concepts can also be applied to hyperparameters, to further improve the quality of the smoke tests. Even though our approach is almost trivial, we were able to find bugs in all three machine learning libraries that we tested and severe bugs in two of the three libraries. This demonstrates that common software testing techniques are still valid in the age of machine learning and that considerations how they can be adapted to this new context can help to find and prevent severe bugs, even in mature machine learning libraries.
Private Weighted Random Walk Stochastic Gradient Descent
Venue: arXiv cs.IT 2021
Year: 2021

We consider a decentralized learning setting in which data is distributed over nodes in a graph. The goal is to learn a global model on the distributed data without involving any central entity that needs to be trusted. While gossip-based stochastic gradient descent (SGD) can be used to achieve this learning objective, it incurs high communication and computation costs, since it has to wait for all the local models at all the nodes to converge. To speed up the convergence, we propose instead to study random walk based SGD in which a global model is updated based on a random walk on the graph. We propose two algorithms based on two types of random walks that achieve, in a decentralized way, uniform sampling and importance sampling of the data. We provide a non-asymptotic analysis on the rate of convergence, taking into account the constants related to the data and the graph. Our numerical results show that the weighted random walk based algorithm has a better performance for high-variance data. Moreover, we propose a privacy-preserving random walk algorithm that achieves local differential privacy based on a Gamma noise mechanism that we propose. We also give numerical results on the convergence of this algorithm and show that it outperforms additive Laplace-based privacy mechanisms.
IoT-based Contact Tracing Systems for Infectious Diseases: Architecture and Analysis
Venue: arXiv cs.CY 2021
Year: 2021

The recent COVID-19 pandemic has become a major threat to human health and well-being. Non-pharmaceutical interventions such as contact tracing solutions are important to contain the spreads of COVID-19-like infectious diseases. However, current contact tracing solutions are fragmented with limited use of sensing technologies and centered on monitoring the interactions between individuals without an analytical framework for evaluating effectiveness. Therefore, we need to first explore generic architecture for contact tracing in the context of today's Internet of Things (IoT) technologies based on a broad range of applicable sensors. A new architecture for IoT based solutions to contact tracing is proposed and its overall effectiveness for disease containment is analyzed based on the traditional epidemiological models with the simulation results. The proposed work aims to provide a framework for assisting future designs and evaluation of IoT-based contact tracing solutions and to enable data-driven collective efforts on combating current and future infectious diseases.
Smoothed analysis of the condition number under low-rank perturbations
Venue: arXiv cs.DS 2021
Year: 2021

Let $M$ be an arbitrary $n$ by $n$ matrix of rank $n-k$. We study the condition number of $M$ plus a \emph{low-rank} perturbation $UV^T$ where $U, V$ are $n$ by $k$ random Gaussian matrices. Under some necessary assumptions, it is shown that $M+UV^T$ is unlikely to have a large condition number. The main advantages of this kind of perturbation over the well-studied dense Gaussian perturbation, where every entry is independently perturbed, is the $O(nk)$ cost to store $U,V$ and the $O(nk)$ increase in time complexity for performing the matrix-vector multiplication $(M+UV^T)x$. This improves the $Ω(n^2)$ space and time complexity increase required by a dense perturbation, which is especially burdensome if $M$ is originally sparse. Our results also extend to the case where $U$ and $V$ have rank larger than $k$ and to symmetric and complex settings. We also give an application to linear systems solving and perform some numerical experiments. Lastly, barriers in applying low-rank noise to other problems studied in the smoothed analysis framework are discussed.
Variational Deep Learning for the Identification and Reconstruction of Chaotic and Stochastic Dynamical Systems from Noisy and Partial Observations
Venue: arXiv cs.LG 2021
Year: 2021

The data-driven recovery of the unknown governing equations of dynamical systems has recently received an increasing interest. However, the identification of governing equations remains challenging when dealing with noisy and partial observations. Here, we address this challenge and investigate variational deep learning schemes. Within the proposed framework, we jointly learn an inference model to reconstruct the true states of the system and the governing laws of these states from series of noisy and partial data. In doing so, this framework bridges classical data assimilation and state-of-the-art machine learning techniques. We also demonstrate that it generalises state-of-the-art methods. Importantly, both the inference model and the governing model embed stochastic components to account for stochastic variabilities, model errors, and reconstruction uncertainties. Various experiments on chaotic and stochastic dynamical systems support the relevance of our scheme w.r.t. state-of-the-art approaches.
Distributed Synchronous Visualization Design: Challenges and Strategies
Venue: arXiv cs.HC 2021
Year: 2021

We reflect on our experiences as designers of COVID-19 data visualizations working in a distributed synchronous design space during the pandemic. This is especially relevant as the pandemic posed new challenges to distributed collaboration amidst civic lockdown measures and an increased dependency on spatially distributed teamwork across almost all sectors. Working from home being 'the new normal', we explored potential solutions for collaborating and prototyping remotely from our own homes using the existing tools at our disposal. Since members of our cross-disciplinary team had different technical skills, we used a range of synchronous remote design tools and methods. We aimed to preserve the richness of co-located collaboration such as face-to-face physical presence, body gestures, facial expressions, and the making and sharing of physical artifacts. While meeting over Zoom, we sketched on paper and used digital collaboration tools, such as Miro and Google Docs. Using an auto-ethnographic approach, we articulate our challenges and strategies throughout the process, providing useful insights about synchronous distributed collaboration.
On prefix palindromic length of automatic words
Venue: arXiv cs.FL 2021
Year: 2021

The prefix palindromic length $\mathrm{PPL}_{\mathbf{u}}(n)$ of an infinite word $\mathbf{u}$ is the minimal number of concatenated palindromes needed to express the prefix of length $n$ of $\mathbf{u}$. Since 2013, it is still unknown if $\mathrm{PPL}_{\mathbf{u}}(n)$ is unbounded for every aperiodic infinite word $\mathbf{u}$, even though this has been proven for almost all aperiodic words. At the same time, the only well-known nontrivial infinite word for which the function $\mathrm{PPL}_{\mathbf{u}}(n)$ has been precisely computed is the Thue-Morse word $\mathbf{t}$. This word is $2$-automatic and, predictably, its function $\mathrm{PPL}_{\mathbf{t}}(n)$ is $2$-regular, but is this the case for all automatic words? In this paper, we prove that this function is $k$-regular for every $k$-automatic word containing only a finite number of palindromes. For two such words, namely the paperfolding word and the Rudin-Shapiro word, we derive a formula for this function. Our computational experiments suggest that generally this is not true: for the period-doubling word, the prefix palindromic length does not look $2$-regular, and for the Fibonacci word, it does not look Fibonacci-regular. If proven, these results would give rare (if not first) examples of a natural function of an automatic word which is not regular.
Stabilizing Invertible Neural Networks Using Mixture Models
Venue: arXiv cs.LG 2021
Year: 2021

In this paper, we analyze the properties of invertible neural networks, which provide a way of solving inverse problems. Our main focus lies on investigating and controlling the Lipschitz constants of the corresponding inverse networks. Without such an control, numerical simulations are prone to errors and not much is gained against traditional approaches. Fortunately, our analysis indicates that changing the latent distribution from a standard normal one to a Gaussian mixture model resolves the issue of exploding Lipschitz constants. Indeed, numerical simulations confirm that this modification leads to significantly improved sampling quality in multimodal applications.
sunny-as2: Enhancing SUNNY for Algorithm Selection
Venue: arXiv cs.AI 2021
Year: 2021

SUNNY is an Algorithm Selection (AS) technique originally tailored for Constraint Programming (CP). SUNNY enables to schedule, from a portfolio of solvers, a subset of solvers to be run on a given CP problem. This approach has proved to be effective for CP problems, and its parallel version won many gold medals in the Open category of the MiniZinc Challenge -- the yearly international competition for CP solvers. In 2015, the ASlib benchmarks were released for comparing AS systems coming from disparate fields (e.g., ASP, QBF, and SAT) and SUNNY was extended to deal with generic AS problems. This led to the development of sunny-as2, an algorithm selector based on SUNNY for ASlib scenarios. A preliminary version of sunny-as2 was submitted to the Open Algorithm Selection Challenge (OASC) in 2017, where it turned out to be the best approach for the runtime minimization of decision problems. In this work, we present the technical advancements of sunny-as2, including: (i) wrapper-based feature selection; (ii) a training approach combining feature selection and neighbourhood size configuration; (iii) the application of nested cross-validation. We show how sunny-as2 performance varies depending on the considered AS scenarios, and we discuss its strengths and weaknesses. Finally, we also show how sunny-as2 improves on its preliminary version submitted to OASC.
A Neural Network Perturbation Theory Based on the Born Series
Venue: arXiv cs.LG 2021
Year: 2021

Deep Learning using the eponymous deep neural networks (DNNs) has become an attractive approach towards various data-based problems of theoretical physics in the past decade. There has been a clear trend to deeper architectures containing increasingly more powerful and involved layers. Contrarily, Taylor coefficients of DNNs still appear mainly in the light of interpretability studies, where they are computed at most to first order. However, especially in theoretical physics numerous problems benefit from accessing higher orders, as well. This gap motivates a general formulation of neural network (NN) Taylor expansions. Restricting our analysis to multilayer perceptrons (MLPs) and introducing quantities we refer to as propagators and vertices, both depending on the MLP's weights and biases, we establish a graph-theoretical approach. Similarly to Feynman rules in quantum field theories, we can systematically assign diagrams containing propagators and vertices to the corresponding partial derivative. Examining this approach for S-wave scattering lengths of shallow potentials, we observe NNs to adapt their derivatives mainly to the leading order of the target function's Taylor expansion. To circumvent this problem, we propose an iterative NN perturbation theory. During each iteration we eliminate the leading order, such that the next-to-leading order can be faithfully learned during the subsequent iteration. After performing two iterations, we find that the first- and second-order Born terms are correctly adapted during the respective iterations. Finally, we combine both results to find a proxy that acts as a machine-learned second-order Born approximation.
FedCM: A Real-time Contribution Measurement Method for Participants in Federated Learning
Venue: arXiv cs.LG 2021
Year: 2021

Federated Learning (FL) creates an ecosystem for multiple agents to collaborate on building models with data privacy consideration. The method for contribution measurement of each agent in the FL system is critical for fair credits allocation but few are proposed. In this paper, we develop a real-time contribution measurement method FedCM that is simple but powerful. The method defines the impact of each agent, comprehensively considers the current round and the previous round to obtain the contribution rate of each agent with attention aggregation. Moreover, FedCM updates contribution every round, which enable it to perform in real-time. Real-time is not considered by the existing approaches, but it is critical for FL systems to allocate computing power, communication resources, etc. Compared to the state-of-the-art method, the experimental results show that FedCM is more sensitive to data quantity and data quality under the premise of real-time. Furthermore, we developed federated learning open-source software based on FedCM. The software has been applied to identify COVID-19 based on medical images.
NC-MOPSO: Network centrality guided multi-objective particle swarm optimization for transport optimization on networks
Venue: arXiv cs.NI 2021
Year: 2021

Transport processes are universal in real-world complex networks, such as communication and transportation networks. As the increase of the traffic in these complex networks, problems like traffic congestion and transport delay are becoming more and more serious, which call for a systematic optimization of these networks. In this paper, we formulate a multi-objective optimization problem (MOP) to deal with the enhancement of network capacity and efficiency simultaneously, by appropriately adjusting the weights of edges in networks. To solve this problem, we provide a multi-objective evolutionary algorithm (MOEA) based on particle swarm optimization (PSO), namely network centrality guided multi-objective PSO (NC-MOPSO). Specifically, in the framework of PSO, we propose a hybrid population initialization mechanism and a local search strategy by employing the network centrality theory to enhance the quality of initial solutions and strengthen the exploration of the search space, respectively. Simulation experiments performed on network models and real networks show that our algorithm has better performance than four state-of-the-art alternatives on several most-used metrics.
Space efficient merging of de Bruijn graphs and Wheeler graphs
Venue: arXiv cs.DS 2021
Year: 2021

The merging of succinct data structures is a well established technique for the space efficient construction of large succinct indexes. In the first part of the paper we propose a new algorithm for merging succinct representations of de Bruijn graphs. Our algorithm has the same asymptotic cost of the state of the art algorithm for the same problem but it uses less than half of its working space. A novel important feature of our algorithm, not found in any of the existing tools, is that it can compute the Variable Order succinct representation of the union graph within the same asymptotic time/space bounds. In the second part of the paper we consider the more general problem of merging succinct representations of Wheeler graphs, a recently introduced graph family which includes as special cases de Bruijn graphs and many other known succinct indexes based on the BWT or one of its variants. We show that Wheeler graphs merging is in general a much more difficult problem, and we provide a space efficient algorithm for the slightly simplified problem of determining whether the union graph has an ordering that satisfies the Wheeler conditions.
Traction Adaptive Motion Planning at the Limits of Handling
Venue: arXiv cs.RO 2021
Year: 2021

In this paper, we address the problem of motion planning and control at the limits of handling, under locally varying traction conditions. We propose a novel solution method where traction variations over the prediction horizon are represented by time-varying tire force constraints, derived from a predictive friction estimate. A constrained finite time optimal control problem is solved in a receding horizon fashion, imposing these time-varying constraints. Furthermore, our method features an integrated sampling augmentation procedure that addresses the problems of infeasibility and sensitivity to local minima that arise at abrupt constraint alterations, e.g., due to sudden friction changes. We validate the proposed algorithm on a Volvo FH16 heavy-duty vehicle, in a range of critical scenarios. Experimental results indicate that traction adaptive motion planning and control improves the vehicle's capacity to avoid accidents, both when adapting to low local traction, by ensuring dynamic feasibility of the planned motion, and when adapting to high local traction, by realizing high traction utilization.
On Decoding of Reed-Muller Codes Using a Local Graph Search
Venue: arXiv cs.IT 2021
Year: 2021

We present a novel iterative decoding algorithm for Reed-Muller (RM) codes, which takes advantage of a graph representation of the code. Vertices of the considered graph correspond to codewords, with two vertices being connected by an edge if and only if the Hamming distance between the corresponding codewords equals the minimum distance of the code. The algorithm uses a greedy local search to find a node optimizing a metric, e.g. the correlation between the received vector and the corresponding codeword. In addition, the cyclic redundancy check can be used to terminate the search as soon as a valid codeword is found, leading to an improvement in the average computational complexity of the algorithm. Simulation results for both binary symmetric channel and additive white Gaussian noise channel show that the presented decoder approaches the performance of maximum likelihood decoding for RM codes of length less than 1024 and for the second-order RM codes of length less than 4096. Moreover, it is demonstrated that the considered decoding approach outperforms state-of-the-art decoding algorithms of RM codes with similar computational complexity for a wide range of block lengths and rates.
Optimal Inspection and Maintenance Planning for Deteriorating Structural Components through Dynamic Bayesian Networks and Markov Decision Processes
Venue: arXiv cs.AI 2021
Year: 2021

Civil and maritime engineering systems, among others, from bridges to offshore platforms and wind turbines, must be efficiently managed as they are exposed to deterioration mechanisms throughout their operational life, such as fatigue or corrosion. Identifying optimal inspection and maintenance policies demands the solution of a complex sequential decision-making problem under uncertainty, with the main objective of efficiently controlling the risk associated with structural failures. Addressing this complexity, risk-based inspection planning methodologies, supported often by dynamic Bayesian networks, evaluate a set of pre-defined heuristic decision rules to reasonably simplify the decision problem. However, the resulting policies may be compromised by the limited space considered in the definition of the decision rules. Avoiding this limitation, Partially Observable Markov Decision Processes (POMDPs) provide a principled mathematical methodology for stochastic optimal control under uncertain action outcomes and observations, in which the optimal actions are prescribed as a function of the entire, dynamically updated, state probability distribution. In this paper, we combine dynamic Bayesian networks with POMDPs in a joint framework for optimal inspection and maintenance planning, and we provide the formulation for developing both infinite and finite horizon POMDPs in a structural reliability context. The proposed methodology is implemented and tested for the case of a structural component subject to fatigue deterioration, demonstrating the capability of state-of-the-art point-based POMDP solvers for solving the underlying planning optimization problem. Within the numerical experiments, POMDP and heuristic-based policies are thoroughly compared, and results showcase that POMDPs achieve substantially lower costs as compared to their counterparts, even for traditional problem settings.
SkyTrakx: A Toolkit for Simulation and Verification of Unmanned Air-Traffic Management Systems (Extended Version)
Venue: arXiv cs.MA 2021
Year: 2021

The key concept for safe and efficient traffic management for Unmanned Aircraft Systems (UAS) is the notion of operation volume (OV). An OV is a 4-dimensional block of airspace and time, which can express an aircraft's intent, and can be used for planning, de-confliction, and traffic management. While there are several high-level simulators for UAS Traffic Management (UTM), we are lacking a framework for creating, manipulating, and reasoning about OVs for heterogeneous air vehicles. In this paper, we address this and present SkyTrakx -- a software toolkit for simulation and verification of UTM scenarios based on OVs. First, we illustrate a use case of SkyTrakx by presenting a specific air traffic coordination protocol. This protocol communicates OVs between participating aircraft and an airspace manager for traffic routing. We show how existing formal verification tools, Dafny and Dione, can assist in automatically checking key properties of the protocol. Second, we show how the OVs can be computed for heterogeneous air vehicles like quadcopters and fixed-wing aircraft using another verification technique, namely reachability analysis. Finally, we show that SkyTrakx can be used to simulate complex scenarios involving heterogeneous vehicles, for testing and performance evaluation in terms of workload and response delays analysis. Our experiments delineate the trade-off between performance and workload across different strategies for generating OVs.