OpenRaiser/Intern-Atlas huggingface dataset:
Testing Scenario Library Generation for Connected and Automated Vehicles, Part I: Methodology
Venue: arXiv cs.SY 2020
Year: 2020

Testing and evaluation is a critical step in the development and deployment of connected and automated vehicles (CAVs), and yet there is no systematic framework to generate testing scenario library. This study aims to provide a general framework for the testing scenario library generation (TSLG) problem with different operational design domains (ODDs), CAV models, and performance metrics. Given an ODD, the testing scenario library is defined as a critical set of scenarios that can be used for CAV test. Each testing scenario is evaluated by a newly proposed measure, scenario criticality, which can be computed as a combination of maneuver challenge and exposure frequency. To search for critical scenarios, an auxiliary objective function is designed, and a multi-start optimization method along with seed-filling is applied. The proposed framework is theoretically proved to obtain accurate evaluation results with much fewer number of tests, if compared with the on-road test method. In part II of the study, three case studies are investigated to demonstrate the proposed methodologies. Reinforcement learning based technique is applied to enhance the searching method under high-dimensional scenarios.
Typical Sequences Revisited --- Computing Width Parameters of Graphs
Venue: arXiv cs.DS 2020
Year: 2020

In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized algorithms for treewidth and pathwidth. The lemma addresses a runtime bottleneck in those algorithms but so far it does not lead to asymptotically faster algorithms. However, we apply the lemma to show that the cutwidth and the modified cutwidth of series parallel digraphs can be computed in $\mathcal{O}(n^2)$ time.
Genuinely Distributed Byzantine Machine Learning
Venue: arXiv cs.DC 2020
Year: 2020

Machine Learning (ML) solutions are nowadays distributed, according to the so-called server/worker architecture. One server holds the model parameters while several workers train the model. Clearly, such architecture is prone to various types of component failures, which can be all encompassed within the spectrum of a Byzantine behavior. Several approaches have been proposed recently to tolerate Byzantine workers. Yet all require trusting a central parameter server. We initiate in this paper the study of the ``general'' Byzantine-resilient distributed machine learning problem where no individual component is trusted. We show that this problem can be solved in an asynchronous system, despite the presence of $\frac{1}{3}$ Byzantine parameter servers and $\frac{1}{3}$ Byzantine workers (which is optimal). We present a new algorithm, ByzSGD, which solves the general Byzantine-resilient distributed machine learning problem by relying on three major schemes. The first, Scatter/Gather, is a communication scheme whose goal is to bound the maximum drift among models on correct servers. The second, Distributed Median Contraction (DMC), leverages the geometric properties of the median in high dimensional spaces to bring parameters within the correct servers back close to each other, ensuring learning convergence. The third, Minimum-Diameter Averaging (MDA), is a statistically-robust gradient aggregation rule whose goal is to tolerate Byzantine workers. MDA requires loose bound on the variance of non-Byzantine gradient estimates, compared to existing alternatives (e.g., Krum). Interestingly, ByzSGD ensures Byzantine resilience without adding communication rounds (on a normal path), compared to vanilla non-Byzantine alternatives. ByzSGD requires, however, a larger number of messages which, we show, can be reduced if we assume synchrony.
DEMC: A Deep Dual-Encoder Network for Denoising Monte Carlo Rendering
Venue: arXiv cs.MM 2020
Year: 2020

In this paper, we present DEMC, a deep Dual-Encoder network to remove Monte Carlo noise efficiently while preserving details. Denoising Monte Carlo rendering is different from natural image denoising since inexpensive by-products (feature buffers) can be extracted in the rendering stage. Most of them are noise-free and can provide sufficient details for image reconstruction. However, these feature buffers also contain redundant information, which makes Monte Carlo denoising different from natural image denoising. Hence, the main challenge of this topic is how to extract useful information and reconstruct clean images. To address this problem, we propose a novel network structure, Dual-Encoder network with a feature fusion sub-network, to fuse feature buffers firstly, then encode the fused feature buffers and a noisy image simultaneously, and finally reconstruct a clean image by a decoder network. Compared with the state-of-the-art methods, our model is more robust on a wide range of scenes and is able to generate satisfactory results in a significantly faster way.
A true concurrent model of smart contracts executions
Venue: arXiv cs.PL 2020
Year: 2020

The development of blockchain technologies has enabled the trustless execution of so-called smart contracts, i.e. programs that regulate the exchange of assets (e.g., cryptocurrency) between users. In a decentralized blockchain, the state of smart contracts is collaboratively maintained by a peer-to-peer network of mutually untrusted nodes, which collect from users a set of transactions (representing the required actions on contracts), and execute them in some order. Once this sequence of transactions is appended to the blockchain, the other nodes validate it, re-executing the transactions in the same order. The serial execution of transactions does not take advantage of the multi-core architecture of modern processors, so contributing to limit the throughput. In this paper we propose a true concurrent model of smart contract execution. Based on this, we show how static analysis of smart contracts can be exploited to parallelize the execution of transactions.
Long Short-Term Memory with Gate and State Level Fusion for Light Field-Based Face Recognition
Venue: arXiv cs.CV 2020
Year: 2020

Long Short-Term Memory (LSTM) is a prominent recurrent neural network for extracting dependencies from sequential data such as time-series and multi-view data, having achieved impressive results for different visual recognition tasks. A conventional LSTM network can learn a model to posteriorly extract information from one input sequence. However, if two or more dependent sequences of data are simultaneously acquired, the conventional LSTM networks may only process those sequences consecutively, not taking benefit of the information carried out by their mutual dependencies. In this context, this paper proposes two novel LSTM cell architectures that are able to jointly learn from multiple sequences simultaneously acquired, targeting to create richer and more effective models for recognition tasks. The efficacy of the novel LSTM cell architectures is assessed by integrating them into deep learning-based methods for face recognition with multi-view, light field images. The new cell architectures jointly learn the scene horizontal and vertical parallaxes available in a light field image, to capture richer spatio-angular information from both directions. A comprehensive evaluation, with the IST-EURECOM LFFD dataset using three challenging evaluation protocols, shows the advantage of using the novel LSTM cell architectures for face recognition over the state-of-the-art light field-based methods. These results highlight the added value of the novel cell architectures when learning from correlated input sequences.
Hadamard Matrix Guided Online Hashing
Venue: arXiv cs.IR 2020
Year: 2020

Online image hashing has attracted increasing research attention recently, which receives large-scale data in a streaming manner to update the hash functions on-the-fly. Its key challenge lies in the difficulty of balancing the learning timeliness and model accuracy. To this end, most works follow a supervised setting, i.e., using class labels to boost the hashing performance, which defects in two aspects: First, strong constraints, e.g., orthogonal or similarity preserving, are used, which however are typically relaxed and lead to large accuracy drop. Second, large amounts of training batches are required to learn the up-to-date hash functions, which largely increase the learning complexity. To handle the above challenges, a novel supervised online hashing scheme termed Hadamard Matrix Guided Online Hashing (HMOH) is proposed in this paper. Our key innovation lies in introducing Hadamard matrix, which is an orthogonal binary matrix built via Sylvester method. In particular, to release the need of strong constraints, we regard each column of Hadamard matrix as the target code for each class label, which by nature satisfies several desired properties of hashing codes. To accelerate the online training, LSH is first adopted to align the lengths of target code and to-be-learned binary code. We then treat the learning of hash functions as a set of binary classification problems to fit the assigned target code. Finally, extensive experiments demonstrate the superior accuracy and efficiency of the proposed method over various state-of-the-art methods. Codes are available at https://github.com/lmbxmu/mycode.
Evidence Propagation and Consensus Formation in Noisy Environments
Venue: arXiv cs.MA 2020
Year: 2020

We study the effectiveness of consensus formation in multi-agent systems where there is both belief updating based on direct evidence and also belief combination between agents. In particular, we consider the scenario in which a population of agents collaborate on the best-of-n problem where the aim is to reach a consensus about which is the best (alternatively, true) state from amongst a set of states, each with a different quality value (or level of evidence). Agents' beliefs are represented within Dempster-Shafer theory by mass functions and we investigate the macro-level properties of four well-known belief combination operators for this multi-agent consensus formation problem: Dempster's rule, Yager's rule, Dubois & Prade's operator and the averaging operator. The convergence properties of the operators are considered and simulation experiments are conducted for different evidence rates and noise levels. Results show that a combination of updating on direct evidence and belief combination between agents results in better consensus to the best state than does evidence updating alone. We also find that in this framework the operators are robust to noise. Broadly, Yager's rule is shown to be the better operator under various parameter values, i.e. convergence to the best state, robustness to noise, and scalability.
Physically-interpretable classification of biological network dynamics for complex collective motions
Venue: arXiv cs.MA 2020
Year: 2020

Understanding biological network dynamics is a fundamental issue in various scientific and engineering fields. Network theory is capable of revealing the relationship between elements and their propagation; however, for complex collective motions, the network properties often transiently and complexly change. A fundamental question addressed here pertains to the classification of collective motion network based on physically-interpretable dynamical properties. Here we apply a data-driven spectral analysis called graph dynamic mode decomposition, which obtains the dynamical properties for collective motion classification. Using a ballgame as an example, we classified the strategic collective motions in different global behaviours and discovered that, in addition to the physical properties, the contextual node information was critical for classification. Furthermore, we discovered the label-specific stronger spectra in the relationship among the nearest agents, providing physical and semantic interpretations. Our approach contributes to the understanding of principles of biological complex network dynamics from the perspective of nonlinear dynamical systems.
Augmenting Cloud Connectivity with Opportunistic Networks for Rural Remote Patient Monitoring
Venue: arXiv cs.NI 2020
Year: 2020

Current remote patient monitoring (RPM) systems are fully reliant on the Internet. However, complete reliance on Internet connectivity is impractical in rural and remote environments where modern infrastructure is often lacking, power outages are frequent, and/or network connectivity is sparse (e.g. rural communities, mountainous regions of Appalachia, American Indian reservations, developing countries, and natural disaster situations). This paper proposes augmenting intermittent Internet with opportunistic communication to leverage the social behaviors of patients, caregivers, and community members to facilitate out-of-range monitoring of patients via Bluetooth 5 during intermittent network connectivity in rural communities. The architecture is evaluated for Owingsville, KY using U.S. Census Bureau, the National Cancer Institute's, and IPUMS-ATUS sample data, and is compared against a delay tolerant RPM case that is completely disconnected from the Internet. The findings show that with only 0.30 rural adult population participation, the architecture can deliver 0.95 of non-emergency medical information with an average delivery latency of approximately 13 hours.
Embeddings of Persistence Diagrams into Hilbert Spaces
Venue: arXiv cs.LG 2020
Year: 2020

Since persistence diagrams do not admit an inner product structure, a map into a Hilbert space is needed in order to use kernel methods. It is natural to ask if such maps necessarily distort the metric on persistence diagrams. We show that persistence diagrams with the bottleneck distance do not even admit a coarse embedding into a Hilbert space. As part of our proof, we show that any separable, bounded metric space isometrically embeds into the space of persistence diagrams with the bottleneck distance. As corollaries, we obtain the generalized roundness, negative type, and asymptotic dimension of this space.
Abelian periods of factors of Sturmian words
Venue: arXiv cs.FL 2020
Year: 2020

We study the abelian period sets of Sturmian words, which are codings of irrational rotations on a one-dimensional torus. The main result states that the minimum abelian period of a factor of a Sturmian word of angle $α$ with continued fraction expansion $[0; a_1, a_2, \ldots]$ is either $tq_k$ with $1 \leq t \leq a_{k+1}$ (a multiple of a denominator $q_k$ of a convergent of $α$) or $q_{k,\ell}$ (a denominator $q_{k,\ell}$ of a semiconvergent of $α$). This result generalizes a result of Fici et. al stating that the abelian period set of the Fibonacci word is the set of Fibonacci numbers. A characterization of the Fibonacci word in terms of its abelian period set is obtained as a corollary.
The Mobility Network of Scientists: Analyzing Temporal Correlations in Scientific Careers
Venue: arXiv cs.SI 2020
Year: 2020

The mobility of scientists between different universities and countries is important to foster knowledge exchange. At the same time, the potential mobility is restricted by geographic and institutional constraints, which leads to temporal correlations in the career trajectories of scientists. To quantify this effect, we extract 3.5 million career trajectories of scientists from two large scale bibliographic data sets and analyze them applying a novel method of higher-order networks. We study the effect of temporal correlations at three different levels of aggregation, universities, cities and countries. We find strong evidence for such correlations for the top 100 universities, i.e. scientists move likely between specific institutions. These correlations also exist at the level of countries, but cannot be found for cities. Our results allow to draw conclusions about the institutional path dependence of scientific careers and the efficiency of mobility programs.
Ethically Aligned Design: An empirical evaluation of the RESOLVEDD-strategy in Software and Systems development context
Venue: arXiv cs.CY 2020
Year: 2020

Use of artificial intelligence (AI) in human contexts calls for ethical considerations for the design and development of AI-based systems. However, little knowledge currently exists on how to provide useful and tangible tools that could help software developers and designers implement ethical considerations into practice. In this paper, we empirically evaluate a method that enables ethically aligned design in a decision-making process. Though this method, titled the RESOLVEDD-strategy, originates from the field of business ethics, it is being applied in other fields as well. We tested the RESOLVEDD-strategy in a multiple case study of five student projects where the use of ethical tools was given as one of the design requirements. A key finding from the study indicates that simply the presence of an ethical tool has an effect on ethical consideration, creating more responsibility even in instances where the use of the tool is not intrinsically motivated.
Efficient Scheduling for the Massive Random Access Gaussian Channel
Venue: arXiv cs.IT 2020
Year: 2020

This paper investigates the massive random access Gaussian channel with a focus on small payloads. For this problem, grant-based schemes have been regarded as inefficient due to the necessity of large feedbacks and the use of inefficient scheduling request methods. This papers attempts to answer whether grant-based schemes can be competitive against state-ot-art grantless schemes and worthy of further investigation. In order to compare these schemes fairly, a novel model is proposed, and, under this model, a novel grant-based scheme is proposed. The scheme uses Ordentlich and Polyanskiy's grantless method to transmit small coordination indices in order to perform the scheduling request, which allows both the request from the users to be efficient and the feedback to be small. We also present improvements to the Ordentlich and Polyanskiy's scheme, allowing it to transmit information through the choice of sub-block, as well as to handle collisions of the same message, significantly improving the method for very small messages. Simulation results show that, if a small feedback is allowed, the proposed scheme performs closely to the state-of-art while using simpler coding schemes, suggesting that novel grant-based schemes should not be dismissed as a potential solution to the massive random access problem.
MoGlow: Probabilistic and controllable motion synthesis using normalising flows
Venue: arXiv cs.LG 2020
Year: 2020

Data-driven modelling and synthesis of motion is an active research area with applications that include animation, games, and social robotics. This paper introduces a new class of probabilistic, generative, and controllable motion-data models based on normalising flows. Models of this kind can describe highly complex distributions, yet can be trained efficiently using exact maximum likelihood, unlike GANs or VAEs. Our proposed model is autoregressive and uses LSTMs to enable arbitrarily long time-dependencies. Importantly, is is also causal, meaning that each pose in the output sequence is generated without access to poses or control inputs from future time steps; this absence of algorithmic latency is important for interactive applications with real-time motion control. The approach can in principle be applied to any type of motion since it does not make restrictive, task-specific assumptions regarding the motion or the character morphology. We evaluate the models on motion-capture datasets of human and quadruped locomotion. Objective and subjective results show that randomly-sampled motion from the proposed method outperforms task-agnostic baselines and attains a motion quality close to recorded motion capture.
Efficient Attack Correlation and Identification of Attack Scenarios based on Network-Motifs
Venue: arXiv cs.CR 2020
Year: 2020

An Intrusion Detection System (IDS) to secure computer networks reports indicators for an attack as alerts. However, every attack can result in a multitude of IDS alerts that need to be correlated to see the full picture of the attack. In this paper, we present a correlation approach that transforms clusters of alerts into a graph structure on which we compute signatures of network motifs to characterize these clusters. A motif representation of attack characteristics is magnitudes smaller than the original alert data, but still allows to efficiently compare and correlate attacks with each other and with reference signatures. This allows not only to identify known attack scenarios, e.g., DDoS, scan, and worm attacks, but also to derive new reference signatures for unknown scenarios. Our results indicate a reliable identification of scenarios, even when attacks differ in size and at least slightly in their characteristics. Applied on real-world alert data, our approach can classify and assign attack scenarios of up to 96% of all attacks and can represent their characteristics using 1% of the size of the full alert data.
Stability of Linear Structural Equation Models of Causal Inference
Venue: arXiv cs.LG 2020
Year: 2020

We consider the numerical stability of the parameter recovery problem in Linear Structural Equation Model ($\LSEM$) of causal inference. A long line of work starting from Wright (1920) has focused on understanding which sub-classes of $\LSEM$ allow for efficient parameter recovery. Despite decades of study, this question is not yet fully resolved. The goal of this paper is complementary to this line of work; we want to understand the stability of the recovery problem in the cases when efficient recovery is possible. Numerical stability of Pearl's notion of causality was first studied in Schulman and Srivastava (2016) using the concept of condition number where they provide ill-conditioned examples. In this work, we provide a condition number analysis for the $\LSEM$. First we prove that under a sufficient condition, for a certain sub-class of $\LSEM$ that are \emph{bow-free} (Brito and Pearl (2002)), the parameter recovery is stable. We further prove that \emph{randomly} chosen input parameters for this family satisfy the condition with a substantial probability. Hence for this family, on a large subset of parameter space, recovery is numerically stable. Next we construct an example of $\LSEM$ on four vertices with \emph{unbounded} condition number. We then corroborate our theoretical findings via simulations as well as real-world experiments for a sociology application. Finally, we provide a general heuristic for estimating the condition number of any $\LSEM$ instance.
MSRBot: Using Bots to Answer Questions from Software Repositories
Venue: arXiv cs.SE 2020
Year: 2020

Software repositories contain a plethora of useful information that can be used to enhance software projects. Prior work has leveraged repository data to improve many aspects of the software development process, such as, help extract requirement decisions, identify potentially defective code and improve maintenance and evolution. However, in many cases, practitioners are not able to fully benefit from software repositories due to the fact that they need special expertise and dedicated effort to mine their repositories. Therefore, in this paper, we use bots to automate and ease the process of extracting useful information from software repositories. Particularly, we lay out an approach of how bots, layered on top of software repositories, can be used to answer some of the most common software development/maintenance questions facing developers. We perform a preliminary study with 12 participants to validate the effectiveness of the bot. Our findings indicate that using bots achieves very promising results in terms of answer accuracy, speed and usefulness. Our work has the potential to transform the MSR field by significantly lowering the barrier to entry, making the extraction of useful information from software repositories as easy as chatting with a bot.