OpenRaiser/Intern-Atlas huggingface dataset:
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths
Venue: arXiv cs.DS 2021
Year: 2021

APSP with small integer weights in undirected graphs [Seidel'95, Galil and Margalit'97] has an $\tilde{O}(n^ω)$ time algorithm, where $ω<2.373$ is the matrix multiplication exponent. APSP in directed graphs with small weights however, has a much slower running time that would be $Ω(n^{2.5})$ even if $ω=2$ [Zwick'02]. To understand this $n^{2.5}$ bottleneck, we build a web of reductions around directed unweighted APSP. We show that it is fine-grained equivalent to computing a rectangular Min-Plus product for matrices with integer entries; the dimensions and entry size of the matrices depend on the value of $ω$. As a consequence, we establish an equivalence between APSP in directed unweighted graphs, APSP in directed graphs with small $(\tilde{O}(1))$ integer weights, All-Pairs Longest Paths in DAGs with small weights, approximate APSP with additive error $c$ in directed graphs with small weights, for $c\le \tilde{O}(1)$ and several other graph problems. We also provide fine-grained reductions from directed unweighted APSP to All-Pairs Shortest Lightest Paths (APSLP) in undirected graphs with $\{0,1\}$ weights and $\#_{\text{mod}\ c}$APSP in directed unweighted graphs (computing counts mod $c$). We complement our hardness results with new algorithms. We improve the known algorithms for APSLP in directed graphs with small integer weights and for approximate APSP with sublinear additive error in directed unweighted graphs. Our algorithm for approximate APSP with sublinear additive error is optimal, when viewed as a reduction to Min-Plus product. We also give new algorithms for variants of #APSP in unweighted graphs, as well as a near-optimal $\tilde{O}(n^3)$-time algorithm for the original #APSP problem in unweighted graphs. Our techniques also lead to a simpler alternative for the original APSP problem in undirected graphs with small integer weights.
Selecting Treatment Effects Models for Domain Adaptation Using Causal Knowledge
Venue: arXiv cs.LG 2021
Year: 2021

Selecting causal inference models for estimating individualized treatment effects (ITE) from observational data presents a unique challenge since the counterfactual outcomes are never observed. The problem is challenged further in the unsupervised domain adaptation (UDA) setting where we only have access to labeled samples in the source domain, but desire selecting a model that achieves good performance on a target domain for which only unlabeled samples are available. Existing techniques for UDA model selection are designed for the predictive setting. These methods examine discriminative density ratios between the input covariates in the source and target domain and do not factor in the model's predictions in the target domain. Because of this, two models with identical performance on the source domain would receive the same risk score by existing methods, but in reality, have significantly different performance in the test domain. We leverage the invariance of causal structures across domains to propose a novel model selection metric specifically designed for ITE methods under the UDA setting. In particular, we propose selecting models whose predictions of interventions' effects satisfy known causal structures in the target domain. Experimentally, our method selects ITE models that are more robust to covariate shifts on several healthcare datasets, including estimating the effect of ventilation in COVID-19 patients from different geographic locations.
Straggler-Resilient Distributed Machine Learning with Dynamic Backup Workers
Venue: arXiv cs.LG 2021
Year: 2021

With the increasing demand for large-scale training of machine learning models, consensus-based distributed optimization methods have recently been advocated as alternatives to the popular parameter server framework. In this paradigm, each worker maintains a local estimate of the optimal parameter vector, and iteratively updates it by waiting and averaging all estimates obtained from its neighbors, and then corrects it on the basis of its local dataset. However, the synchronization phase can be time consuming due to the need to wait for \textit{stragglers}, i.e., slower workers. An efficient way to mitigate this effect is to let each worker wait only for updates from the fastest neighbors before updating its local parameter. The remaining neighbors are called \textit{backup workers.} To minimize the globally training time over the network, we propose a fully distributed algorithm to dynamically determine the number of backup workers for each worker. We show that our algorithm achieves a linear speedup for convergence (i.e., convergence performance increases linearly with respect to the number of workers). We conduct extensive experiments on MNIST and CIFAR-10 to verify our theoretical results.
Improving Fault Localization by Integrating Value and Predicate Based Causal Inference Techniques
Venue: arXiv cs.SE 2021
Year: 2021

Statistical fault localization (SFL) techniques use execution profiles and success/failure information from software executions, in conjunction with statistical inference, to automatically score program elements based on how likely they are to be faulty. SFL techniques typically employ one type of profile data: either coverage data, predicate outcomes, or variable values. Most SFL techniques actually measure correlation, not causation, between profile values and success/failure, and so they are subject to confounding bias that distorts the scores they produce. This paper presents a new SFL technique, named \emph{UniVal}, that uses causal inference techniques and machine learning to integrate information about both predicate outcomes and variable values to more accurately estimate the true failure-causing effect of program statements. \emph{UniVal} was empirically compared to several coverage-based, predicate-based, and value-based SFL techniques on 800 program versions with real faults.
Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients
Venue: arXiv cs.LG 2021
Year: 2021

Federated learning (FL) is a new machine learning framework which trains a joint model across a large amount of decentralized computing devices. Existing methods, e.g., Federated Averaging (FedAvg), are able to provide an optimization guarantee by synchronously training the joint model, but usually suffer from stragglers, i.e., IoT devices with low computing power or communication bandwidth, especially on heterogeneous optimization problems. To mitigate the influence of stragglers, this paper presents a novel FL algorithm, namely Hybrid Federated Learning (HFL), to achieve a learning balance in efficiency and effectiveness. It consists of two major components: synchronous kernel and asynchronous updater. Unlike traditional synchronous FL methods, our HFL introduces the asynchronous updater which actively pulls unsynchronized and delayed local weights from stragglers. An adaptive approximation method, Adaptive Delayed-SGD (AD-SGD), is proposed to merge the delayed local updates into the joint model. The theoretical analysis of HFL shows that the convergence rate of the proposed algorithm is $\mathcal{O}(\frac{1}{t+τ})$ for both convex and non-convex optimization problems.
SCOUT: Socially-COnsistent and UndersTandable Graph Attention Network for Trajectory Prediction of Vehicles and VRUs
Venue: arXiv cs.LG 2021
Year: 2021

Autonomous vehicles navigate in dynamically changing environments under a wide variety of conditions, being continuously influenced by surrounding objects. Modelling interactions among agents is essential for accurately forecasting other agents' behaviour and achieving safe and comfortable motion planning. In this work, we propose SCOUT, a novel Attention-based Graph Neural Network that uses a flexible and generic representation of the scene as a graph for modelling interactions, and predicts socially-consistent trajectories of vehicles and Vulnerable Road Users (VRUs) under mixed traffic conditions. We explore three different attention mechanisms and test our scheme with both bird-eye-view and on-vehicle urban data, achieving superior performance than existing state-of-the-art approaches on InD and ApolloScape Trajectory benchmarks. Additionally, we evaluate our model's flexibility and transferability by testing it under completely new scenarios on RounD dataset. The importance and influence of each interaction in the final prediction is explored by means of Integrated Gradients technique and the visualization of the attention learned.
Complete Power Reallocation for MU-MIMO under Per-Antenna Power Constraint
Venue: arXiv cs.IT 2021
Year: 2021

This paper proposes a beamforming method under a per-antenna power constraint (PAPC). Although many beamformer designs with the PAPC need to solve complex optimization problems, the proposed complete power reallocation (CPR) method can generate beamformers with excellent performance only with linear operations. CPR is designed to have a simple structure, making it highly flexible and practical. In this paper, three CPR variations considering algorithm convergence speed, sum-rate maximization, and robustness to channel uncertainty are developed. Simulation results verify that CPR and its variations satisfy their design criteria, and, hence, CPR can be readily utilized for various purposes.
SceneRec: Scene-Based Graph Neural Networks for Recommender Systems
Venue: arXiv cs.IR 2021
Year: 2021

Collaborative filtering has been largely used to advance modern recommender systems to predict user preference. A key component in collaborative filtering is representation learning, which aims to project users and items into a low dimensional space to capture collaborative signals. However, the scene information, which has effectively guided many recommendation tasks, is rarely considered in existing collaborative filtering methods. To bridge this gap, we focus on scene-based collaborative recommendation and propose a novel representation model SceneRec. SceneRec formally defines a scene as a set of pre-defined item categories that occur simultaneously in real-life situations and creatively designs an item-category-scene hierarchical structure to build a scene-based graph. In the scene-based graph, we adopt graph neural networks to learn scene-specific representation on each item node, which is further aggregated with latent representation learned from collaborative interactions to make recommendations. We perform extensive experiments on real-world E-commerce datasets and the results demonstrate the effectiveness of the proposed method.
On Signings and the Well-Founded Semantics
Venue: arXiv cs.LO 2021
Year: 2021

In this note, we use Kunen's notion of a signing to establish two theorems about the well-founded semantics of logic programs, in the case where we are interested in only (say) the positive literals of a predicate $p$ that are consequences of the program. The first theorem identifies a class of programs for which the well-founded and Fitting semantics coincide for the positive part of $p$. The second theorem shows that if a program has a signing then computing the positive part of $p$ under the well-founded semantics requires the computation of only one part of each predicate. This theorem suggests an analysis for query-answering under the well-founded semantics. In the process of proving these results, we use an alternative formulation of the well-founded semantics of logic programs, which might be of independent interest. Under consideration in Theory and Practice of Logic Programming (TPLP)
Depthwise Separable Convolutions Allow for Fast and Memory-Efficient Spectral Normalization
Venue: arXiv cs.LG 2021
Year: 2021

An increasing number of models require the control of the spectral norm of convolutional layers of a neural network. While there is an abundance of methods for estimating and enforcing upper bounds on those during training, they are typically costly in either memory or time. In this work, we introduce a very simple method for spectral normalization of depthwise separable convolutions, which introduces negligible computational and memory overhead. We demonstrate the effectiveness of our method on image classification tasks using standard architectures like MobileNetV2.
Interpretable Predictive Maintenance for Hard Drives
Venue: arXiv cs.LG 2021
Year: 2021

Existing machine learning approaches for data-driven predictive maintenance are usually black boxes that claim high predictive power yet cannot be understood by humans. This limits the ability of humans to use these models to derive insights and understanding of the underlying failure mechanisms, and also limits the degree of confidence that can be placed in such a system to perform well on future data. We consider the task of predicting hard drive failure in a data center using recent algorithms for interpretable machine learning. We demonstrate that these methods provide meaningful insights about short- and long-term drive health, while also maintaining high predictive performance. We also show that these analyses still deliver useful insights even when limited historical data is available, enabling their use in situations where data collection has only recently begun.
Mutually exciting point process graphs for modelling dynamic networks
Venue: arXiv cs.SI 2021
Year: 2021

A new class of models for dynamic networks is proposed, called mutually exciting point process graphs (MEG). MEG is a scalable network-wide statistical model for point processes with dyadic marks, which can be used for anomaly detection when assessing the significance of future events, including previously unobserved connections between nodes. The model combines mutually exciting point processes to estimate dependencies between events and latent space models to infer relationships between the nodes. The intensity functions for each network edge are characterised exclusively by node-specific parameters, which allows information to be shared across the network. This construction enables estimation of intensities even for unobserved edges, which is particularly important in real world applications, such as computer networks arising in cyber-security. A recursive form of the log-likelihood function for MEG is obtained, which is used to derive fast inferential procedures via modern gradient ascent algorithms. An alternative EM algorithm is also derived. The model and algorithms are tested on simulated graphs and real world datasets, demonstrating excellent performance.
Analysis of Interpolation based Image In-painting Approaches
Venue: arXiv cs.CV 2021
Year: 2021

Interpolation and internal painting are one of the basic approaches in image internal painting, which is used to eliminate undesirable parts that occur in digital images or to enhance faulty parts. This study was designed to compare the interpolation algorithms used in image in-painting in the literature. Errors and noise generated on the colour and grayscale formats of some of the commonly used standard images in the literature were corrected by using Cubic, Kriging, Radial based function and High dimensional model representation approaches and the results were compared using standard image comparison criteria, namely, PSNR (peak signal-to-noise ratio), SSIM (Structural SIMilarity), Mean Square Error (MSE). According to the results obtained from the study, the absolute superiority of the methods against each other was not observed. However, Kriging and RBF interpolation give better results both for numerical data and visual evaluation for image in-painting problems with large area losses.
Fuzzing Symbolic Expressions
Venue: arXiv cs.SE 2021
Year: 2021

Recent years have witnessed a wide array of results in software testing, exploring different approaches and methodologies ranging from fuzzers to symbolic engines, with a full spectrum of instances in between such as concolic execution and hybrid fuzzing. A key ingredient of many of these tools is Satisfiability Modulo Theories (SMT) solvers, which are used to reason over symbolic expressions collected during the analysis. In this paper, we investigate whether techniques borrowed from the fuzzing domain can be applied to check whether symbolic formulas are satisfiable in the context of concolic and hybrid fuzzing engines, providing a viable alternative to classic SMT solving techniques. We devise a new approximate solver, FUZZY-SAT, and show that it is both competitive with and complementary to state-of-the-art solvers such as Z3 with respect to handling queries generated by hybrid fuzzers.
On the Application of BAC-NOMA to 6G umMTC
Venue: arXiv cs.IT 2021
Year: 2021

This letter studies the application of backscatter communications (BackCom) assisted non-orthogonal multiple access (BAC-NOMA) to the envisioned sixth-generation (6G) ultra-massive machine type communications (umMTC). In particular, the proposed BAC-NOMA transmission scheme can realize simultaneous energy and spectrum cooperation between uplink and downlink users, which is important to support massive connectivity and stringent energy constraints in umMTC. Furthermore, a resource allocation problem for maximizing the uplink throughput and suppressing the interference between downlink and uplink transmission is formulated as an optimization problem and the corresponding optimal resource allocation policy is obtained. Computer simulations are provided to demonstrate the superior performance of BAC-NOMA.
A Computability Perspective on (Verified) Machine Learning
Venue: arXiv cs.LG 2021
Year: 2021

There is a strong consensus that combining the versatility of machine learning with the assurances given by formal verification is highly desirable. It is much less clear what verified machine learning should mean exactly. We consider this question from the (unexpected?) perspective of computable analysis. This allows us to define the computational tasks underlying verified ML in a model-agnostic way, and show that they are in principle computable.
A taxonomy for quality in simulation-based development and testing of automated driving systems
Venue: arXiv cs.SE 2021
Year: 2021

Ensuring the quality of automated driving systems is a major challenge the automotive industry is facing. In this context, quality defines the degree to which an object meets expectations and requirements. Especially, automated vehicles at SAE level 4 and 5 will be expected to operate safely in various contexts and complex situations without misconduct. Thus, a systematic approach is needed to show their safe operation. A way to address this challenge is simulation-based testing as pure physical testing is not feasible. During simulation-based testing, the data used to evaluate the actual quality of an automated driving system are generated using a simulation. However, to rely on these simulation data, the overall simulation, which also includes its simulation models, must provide a certain quality level. This quality level depends on the intended purpose for which the generated simulation data should be used. Therefore, three categories of quality can be considered: quality of the automated driving system and simulation quality, consisting of simulation model quality and scenario quality. Hence, quality must be determined and evaluated in various process steps in developing and testing automated driving systems, the overall simulation, and the simulation models used for the simulation. In this paper, we propose a taxonomy to serve a better understanding of the concept of quality in the development and testing process to have a clear separation and insight where further testing is needed -- both in terms of automated driving systems and simulation, including their simulation models and scenarios used for testing.
Leveraging Artificial Intelligence to Analyze the COVID-19 Distribution Pattern based on Socio-economic Determinants
Venue: arXiv cs.SI 2021
Year: 2021

The spatialization of socioeconomic data can be used and integrated with other sources of information to reveal valuable insights. Such data can be utilized to infer different variations, such as the dynamics of city dwellers and their spatial and temporal variability. This work focuses on such applications to explore the underlying association between socioeconomic characteristics of different geographical regions in Dublin, Ireland, and the number of confirmed COVID cases in each area. Our aim is to implement a machine learning approach to identify demographic characteristics and spatial patterns. Spatial analysis was used to describe the pattern of interest in Electoral Divisions (ED), which are the legally defined administrative areas in the Republic of Ireland for which population statistics are published from the census data. We used the most informative variables of the census data to model the number of infected people in different regions at ED level. Seven clusters detected by implementing an unsupervised neural network method. The distribution of people who have contracted the virus was studied.
Leveraging Artificial Intelligence to Analyze Citizens' Opinions on Urban Green Space
Venue: arXiv cs.SI 2021
Year: 2021

Continued population growth and urbanization is shifting research to consider the quality of urban green space over the quantity of these parks, woods, and wetlands. The quality of urban green space has been hitherto measured by expert assessments, including in-situ observations, surveys, and remote sensing analyses. Location data platforms, such as TripAdvisor, can provide people's opinion on many destinations and experiences, including UGS. This paper leverages Artificial Intelligence techniques for opinion mining and text classification using such platform's reviews as a novel approach to urban green space quality assessments. Natural Language Processing is used to analyze contextual information given supervised scores of words by implementing computational analysis. Such an application can support local authorities and stakeholders in their understanding of and justification for future investments in urban green space.
Qualifying Software Engineers Undergraduates in DevOps -- Challenges of Introducing Technical and Non-technical Concepts in a Project-oriented Course
Venue: arXiv cs.SE 2021
Year: 2021

The constant changes in the software industry, practices, and methodologies impose challenges to teaching and learning current software engineering concepts and skills. DevOps is particularly challenging because it covers technical concepts, such as pipeline automation, and non-technical ones, such as team roles and project management. The present study investigates a course setup to introduce these concepts to software engineering undergraduates. We designed the course by employing coding to associate DevOps concepts to Agile, Lean, and Open source practices and tools. We present the main aspects of this project-oriented DevOps course, with 240 students enrolled in it since its first offering in 2016. We conducted an empirical study, with both a quantitative and qualitative analysis, to evaluate this project-oriented course setup. We collected the data from the projects repository and students perceptions from a questionnaire. We mined 148 repositories (corresponding to 72 projects) and obtained 86 valid responses to the questionnaire. We also mapped the concepts which are more challenging to students learn from experience. The results evidence that first-hand experience facilitates the comprehension of DevOps concepts and enriches classes discussions. We present a set of lessons learned, which may help professors better design and conduct project-oriented courses to cover DevOps concepts.