OpenRaiser/Intern-Atlas huggingface dataset:
A Tipping Point for the Planarity of Small and Medium Sized Graphs
Venue: arXiv cs.DM 2020
Year: 2020

This paper presents an empirical study of the relationship between the density of small-medium sized random graphs and their planarity. It is well known that, when the number of vertices tends to infinite, there is a sharp transition between planarity and non-planarity for edge density d=0.5. However, this asymptotic property does not clarify what happens for graphs of reduced size. We show that an unexpectedly sharp transition is also exhibited by small and medium sized graphs. Also, we show that the same "tipping point" behavior can be observed for some restrictions or relaxations of planarity (we considered outerplanarity and near-planarity, respectively).
Automatic sleep stage classification with deep residual networks in a mixed-cohort setting
Venue: arXiv cs.CV 2020
Year: 2020

Study Objectives: Sleep stage scoring is performed manually by sleep experts and is prone to subjective interpretation of scoring rules with low intra- and interscorer reliability. Many automatic systems rely on few small-scale databases for developing models, and generalizability to new datasets is thus unknown. We investigated a novel deep neural network to assess the generalizability of several large-scale cohorts. Methods: A deep neural network model was developed using 15684 polysomnography studies from five different cohorts. We applied four different scenarios: 1) impact of varying time-scales in the model; 2) performance of a single cohort on other cohorts of smaller, greater or equal size relative to the performance of other cohorts on a single cohort; 3) varying the fraction of mixed-cohort training data compared to using single-origin data; and 4) comparing models trained on combinations of data from 2, 3, and 4 cohorts. Results: Overall classification accuracy improved with increasing fractions of training data (0.25$\%$: 0.782 $\pm$ 0.097, 95$\%$ CI [0.777-0.787]; 100$\%$: 0.869 $\pm$ 0.064, 95$\%$ CI [0.864-0.872]), and with increasing number of data sources (2: 0.788 $\pm$ 0.102, 95$\%$ CI [0.787-0.790]; 3: 0.808 $\pm$ 0.092, 95$\%$ CI [0.807-0.810]; 4: 0.821 $\pm$ 0.085, 95$\%$ CI [0.819-0.823]). Different cohorts show varying levels of generalization to other cohorts. Conclusions: Automatic sleep stage scoring systems based on deep learning algorithms should consider as much data as possible from as many sources available to ensure proper generalization. Public datasets for benchmarking should be made available for future research.
Action-Based Representation Learning for Autonomous Driving
Venue: arXiv cs.CV 2020
Year: 2020

Human drivers produce a vast amount of data which could, in principle, be used to improve autonomous driving systems. Unfortunately, seemingly straightforward approaches for creating end-to-end driving models that map sensor data directly into driving actions are problematic in terms of interpretability, and typically have significant difficulty dealing with spurious correlations. Alternatively, we propose to use this kind of action-based driving data for learning representations. Our experiments show that an affordance-based driving model pre-trained with this approach can leverage a relatively small amount of weakly annotated imagery and outperform pure end-to-end driving models, while being more interpretable. Further, we demonstrate how this strategy outperforms previous methods based on learning inverse dynamics models as well as other methods based on heavy human supervision (ImageNet).
Adversarial Imitation Learning via Random Search
Venue: arXiv cs.LG 2020
Year: 2020

Developing agents that can perform challenging complex tasks is the goal of reinforcement learning. The model-free reinforcement learning has been considered as a feasible solution. However, the state of the art research has been to develop increasingly complicated techniques. This increasing complexity makes the reconstruction difficult. Furthermore, the problem of reward dependency is still exists. As a result, research on imitation learning, which learns policy from a demonstration of experts, has begun to attract attention. Imitation learning directly learns policy based on data on the behavior of the experts without the explicit reward signal provided by the environment. However, imitation learning tries to optimize policies based on deep reinforcement learning such as trust region policy optimization. As a result, deep reinforcement learning based imitation learning also poses a crisis of reproducibility. The issue of complex model-free model has received considerable critical attention. A derivative-free optimization based reinforcement learning and the simplification on policies obtain competitive performance on the dynamic complex tasks. The simplified policies and derivative free methods make algorithm be simple. The reconfiguration of research demo becomes easy. In this paper, we propose an imitation learning method that takes advantage of the derivative-free optimization with simple linear policies. The proposed method performs simple random search in the parameter space of policies and shows computational efficiency. Experiments in this paper show that the proposed model, without a direct reward signal from the environment, obtains competitive performance on the MuJoCo locomotion tasks.
Counterfactual-based minority oversampling for imbalanced classification
Venue: arXiv cs.LG 2020
Year: 2020

A key challenge of oversampling in imbalanced classification is that the generation of new minority samples often neglects the usage of majority classes, resulting in most new minority sampling spreading the whole minority space. In view of this, we present a new oversampling framework based on the counterfactual theory. Our framework introduces a counterfactual objective by leveraging the rich inherent information of majority classes and explicitly perturbing majority samples to generate new samples in the territory of minority space. It can be analytically shown that the new minority samples satisfy the minimum inversion, and therefore most of them locate near the decision boundary. Empirical evaluations on benchmark datasets suggest that our approach significantly outperforms the state-of-the-art methods.
Beyond Individual and Group Fairness
Venue: arXiv cs.LG 2020
Year: 2020

We present a new data-driven model of fairness that, unlike existing static definitions of individual or group fairness is guided by the unfairness complaints received by the system. Our model supports multiple fairness criteria and takes into account their potential incompatibilities. We consider both a stochastic and an adversarial setting of our model. In the stochastic setting, we show that our framework can be naturally cast as a Markov Decision Process with stochastic losses, for which we give efficient vanishing regret algorithmic solutions. In the adversarial setting, we design efficient algorithms with competitive ratio guarantees. We also report the results of experiments with our algorithms and the stochastic framework on artificial datasets, to demonstrate their effectiveness empirically.
MAGE: Mutual Attestation for a Group of Enclaves without Trusted Third Parties
Venue: arXiv cs.CR 2020
Year: 2020

Intel Software Guard Extensions (SGX) local and remote attestation mechanisms enable an enclave to attest its identity (i.e., the enclave measurement, which is the cryptographic hash of its initial code and data) to an enclave. To verify that the attested identity is trusted, one enclave usually includes the measurement of the enclave it trusts into its initial data in advance assuming no trusted third parties are available during runtime to provide this piece of information. However, when mutual trust between these two enclaves is required, it is infeasible to simultaneously include into their own initial data the other's measurements respectively as any change to the initial data will change their measurements, making the previously included measurements invalid. In this paper, we propose MAGE, a framework enabling a group of enclaves to mutually attest each other without trusted third parties. Particularly, we introduce a technique to instrument these enclaves so that each of them could derive the others' measurements using information solely from its own initial data. We also provide a prototype implementation based on Intel SGX SDK, to facilitate enclave developers to adopt this technique.
Authorized and Unauthorized Practices of Law: The Role of Autonomous Levels of AI Legal Reasoning
Venue: arXiv cs.CY 2020
Year: 2020

Advances in Artificial Intelligence (AI) and Machine Learning (ML) that are being applied to legal efforts have raised controversial questions about the existent restrictions imposed on the practice-of-law. Generally, the legal field has sought to define Authorized Practices of Law (APL) versus Unauthorized Practices of Law (UPL), though the boundaries are at times amorphous and some contend capricious and self-serving, rather than being devised holistically for the benefit of society all told. A missing ingredient in these arguments is the realization that impending legal profession disruptions due to AI can be more robustly discerned by examining the matter through the lens of a framework utilizing the autonomous levels of AI Legal Reasoning (AILR). This paper explores a newly derived instrumental grid depicting the key characteristics underlying APL and UPL as they apply to the AILR autonomous levels and offers key insights for the furtherance of these crucial practice-of-law debates.
BLONDiE: Blockchain Ontology with Dynamic Extensibility
Venue: arXiv cs.CR 2020
Year: 2020

There are thousands of projects worldwide based primarily on blockchain technology. These have a large number of users and hundreds of use cases. One of the most popular is the use of cryptocurrencies and their benefits against money without intrinsic value (fiat money) and centralized financial solutions. However, although thousands of new transactions are carried out daily in different platforms, uniform and standardized information does not exist to be able to manage the large amount of data that is generated and exchanged between users through transactions and the generation of new blocks. This research reports the development of BLONDiE, an ontology that allows the semantic representation of knowledge to describe the native structure and related information of the three most relevant blockchain projects to date: Bitcoin, Ethereum and in the recent 1.0 version extends its definitions to include Hyperledger, specifically the Hyperledger Fabric infrastructure. Its use allows having common data formats of different platforms for further processing, such as the execution of semantic queries.
Evaluation of the cumulated impacts on the marine resource of a socio-ecological coral system: approach by agent-based modeling
Venue: arXiv cs.MA 2020
Year: 2020

In the context of climate change and significant changes in human activities around the world, coral reefs are subject to many disruptions. We develop here a tool to help decision-making in Moorea (French Polynesia), based on multi-agent modeling. We model the trophic interactions with a Lotka-Volterra model, and also the interactions between fishermen, trophic groups and tourist operators. The results are generated through global, temporal (time series), and spatial (GIS maps) outputs. The model produced here can be transposed to other ecological and economic situations, and other geographical areas, by modifying the parameters and changing the input map data.
A framework for modelling Molecular Interaction Maps
Venue: arXiv cs.LO 2020
Year: 2020

Metabolic networks, formed by a series of metabolic pathways, are made of intracellular and extracellular reactions that determine the biochemical properties of a cell, and by a set of interactions that guide and regulate the activity of these reactions. Most of these pathways are formed by an intricate and complex network of chain reactions, and can be represented in a human readable form using graphs which describe the cell cycle checkpoint pathways. This paper proposes a method to represent Molecular Interaction Maps (graphical representations of complex metabolic networks) in Linear Temporal Logic. The logical representation of such networks allows one to reason about them, in order to check, for instance, whether a graph satisfies a given property $ϕ$, as well as to find out which initial conditons would guarantee $ϕ$, or else how can the the graph be updated in order to satisfy $ϕ$. Both the translation and resolution methods have been implemented in a tool capable of addressing such questions thanks to a reduction to propositional logic which allows exploiting classical SAT solvers.
Robust and Efficient Swarm Communication Topologies for Hostile Environments
Venue: arXiv cs.NE 2020
Year: 2020

Swarm Intelligence-based optimization techniques combine systematic exploration of the search space with information available from neighbors and rely strongly on communication among agents. These algorithms are typically employed to solve problems where the function landscape is not adequately known and there are multiple local optima that could result in premature convergence for other algorithms. Applications of such algorithms can be found in communication systems involving design of networks for efficient information dissemination to a target group, targeted drug-delivery where drug molecules search for the affected site before diffusing, and high-value target localization with a network of drones. In several of such applications, the agents face a hostile environment that can result in loss of agents during the search. Such a loss changes the communication topology of the agents and hence the information available to agents, ultimately influencing the performance of the algorithm. In this paper, we present a study of the impact of loss of agents on the performance of such algorithms as a function of the initial network configuration. We use particle swarm optimization to optimize an objective function with multiple sub-optimal regions in a hostile environment and study its performance for a range of network topologies with loss of agents. The results reveal interesting trade-offs between efficiency, robustness, and performance for different topologies that are subsequently leveraged to discover general properties of networks that maximize performance. Moreover, networks with small-world properties are seen to maximize performance under hostile conditions.
Lyra 2: Designing Interactive Visualizations by Demonstration
Venue: arXiv cs.HC 2020
Year: 2020

Recent graphical interfaces offer direct manipulation mechanisms for authoring visualizations, but are largely restricted to static output. To author interactive visualizations, users must instead turn to textual specification; but, such approaches impose a higher technical burden than their graphical counterparts. To bridge this gap, we introduce interaction design by demonstration: a novel method for authoring interaction techniques via direct manipulation. Users perform an interaction (e.g., button clicks, drags, or key presses) directly on the visualization they are editing. The system interprets this performance using a set of heuristics, and produces suggestions of possible interaction designs. Heuristics account for properties of the interaction (e.g., target and event type) as well as the visualization (e.g., mark and scale types, and multiple views). Interaction design suggestions are displayed as thumbnails; users can preview and test these suggestions, iteratively refine them through additional demonstrations, and finally apply and customize them via property inspectors. To evaluate our approach, we instantiate it in Lyra, an existing visualization design environment. We demonstrate its expressive extent with a gallery of diverse examples, and evaluate its usability through a first-use study and via an analysis of its cognitive dimensions. We find that, in Lyra, interaction design by demonstration enables users to rapidly express a wide range of interactive visualizations.
A Principled Approach to Design Using High Fidelity Fluid-Structure Interaction Simulations
Venue: arXiv cs.CE 2020
Year: 2020

A high fidelity fluid-structure interaction simulation may require many days to run, on hundreds of cores. This poses a serious burden, both in terms of time and economic considerations, when repetitions of such simulations may be required (e.g. for the purpose of design optimization). In this paper we present strategies based on (constrained) Bayesian optimization (BO) to alleviate this burden. BO is a numerical optimization technique based on Gaussian processes (GP) that is able to efficiently (with minimal calls to the expensive FSI models) converge towards some globally optimal design, as gauged using a black box objective function. In this study we present a principled design evolution that moves from FSI model verification, through a series of Bridge Simulations (bringing the verification case incrementally closer to the application), in order that we may identify material properties for an underwater, unmanned, autonomous vehicle (UUAV) sail plane. We are able to achieve fast convergence towards an optimal design, using a small number of FSI simulations (a dozen at most), even when selecting over several design parameters, and while respecting optimization constraints.
Toward Quantifying Ambiguities in Artistic Images
Venue: arXiv cs.CV 2020
Year: 2020

It has long been hypothesized that perceptual ambiguities play an important role in aesthetic experience: a work with some ambiguity engages a viewer more than one that does not. However, current frameworks for testing this theory are limited by the availability of stimuli and data collection methods. This paper presents an approach to measuring the perceptual ambiguity of a collection of images. Crowdworkers are asked to describe image content, after different viewing durations. Experiments are performed using images created with Generative Adversarial Networks, using the Artbreeder website. We show that text processing of viewer responses can provide a fine-grained way to measure and describe image ambiguities.
Detecting and Classifying Malevolent Dialogue Responses: Taxonomy, Data and Methodology
Venue: arXiv cs.CL 2020
Year: 2020

Conversational interfaces are increasingly popular as a way of connecting people to information. Corpus-based conversational interfaces are able to generate more diverse and natural responses than template-based or retrieval-based agents. With their increased generative capacity of corpusbased conversational agents comes the need to classify and filter out malevolent responses that are inappropriate in terms of content and dialogue acts. Previous studies on the topic of recognizing and classifying inappropriate content are mostly focused on a certain category of malevolence or on single sentences instead of an entire dialogue. In this paper, we define the task of Malevolent Dialogue Response Detection and Classification (MDRDC). We make three contributions to advance research on this task. First, we present a Hierarchical Malevolent Dialogue Taxonomy (HMDT). Second, we create a labelled multi-turn dialogue dataset and formulate the MDRDC task as a hierarchical classification task over this taxonomy. Third, we apply stateof-the-art text classification methods to the MDRDC task and report on extensive experiments aimed at assessing the performance of these approaches.
One Exploit to Rule them All? On the Security of Drop-in Replacement and Counterfeit Microcontrollers
Venue: arXiv cs.CR 2020
Year: 2020

With the increasing complexity of embedded systems, the firmware has become a valuable asset. At the same time, pressure for cost reductions in hardware is imminent. These two aspects are united at the heart of the system, i.e., the microcontroller. It runs and protects its firmware, but simultaneously has to prevail against cheaper alternatives. For the very popular STM32F1 microcontroller series, this has caused the emergence of many competitors in the last few years who offer drop-in replacements or even sell counterfeit devices at a fraction of the original price. Thus, the question emerges whether the replacements are silicon-level clones and, if not, whether they provide better, equal, or less security. In this paper, we analyze a total of six devices by four manufacturers, including the original device, in depth. Via a low-level analysis, we identify all of them as being individually developed devices. We further put the focus on debug and hardware security, discovering several novel vulnerabilities in all devices, causing the exposure of the entire firmware. All of the presented vulnerabilities, including invasive ones, are on a Do it Yourself (DiY) level without the demand for a sophisticated lab -- thereby underlining the urgency for hardware fixes. To facilitate further research, reproduction, and testing of other devices, we provide a comprehensive description of all vulnerabilities in this paper and code for proofs-of-concepts online.
On the treatment of boundary conditions for bond-based peridynamic models
Venue: arXiv cs.CE 2020
Year: 2020

In this paper, we propose two approaches to apply boundary conditions for bond-based peridynamic models. There has been in recent years a renewed interest in the class of so-called non-local models, which include peridynamic models, for the simulation of structural mechanics problems as an alternative approach to classical local continuum models. However, a major issue, which is often disregarded when dealing with this class of models, is concerned with the manner by which boundary conditions should be prescribed. Our point of view here is that classical boundary conditions, since applied on surfaces of solid bodies, are naturally associated with local models. The paper describes two methods to incorporate classical Dirichlet and Neumann boundary conditions into bond-based peridynamics. The first method consists in artificially extending the domain with a thin boundary layer over which the displacement field is required to behave as an odd function with respect to the boundary points. The second method resorts to the idea that peridynamic models and local models should be compatible in the limit that the so-called horizon vanishes. The approach consists then in decreasing the horizon from a constant value in the interior of the domain to zero at the boundary so that one can directly apply the classical boundary conditions. We present the continuous and discrete formulations of the two methods and assess their performance on several numerical experiments dealing with the simulation of a one-dimensional bar.
Online Adaptive Learning for Runtime Resource Management of Heterogeneous SoCs
Venue: arXiv cs.DC 2020
Year: 2020

Dynamic resource management has become one of the major areas of research in modern computer and communication system design due to lower power consumption and higher performance demands. The number of integrated cores, level of heterogeneity and amount of control knobs increase steadily. As a result, the system complexity is increasing faster than our ability to optimize and dynamically manage the resources. Moreover, offline approaches are sub-optimal due to workload variations and large volume of new applications unknown at design time. This paper first reviews recent online learning techniques for predicting system performance, power, and temperature. Then, we describe the use of predictive models for online control using two modern approaches: imitation learning (IL) and an explicit nonlinear model predictive control (NMPC). Evaluations on a commercial mobile platform with 16 benchmarks show that the IL approach successfully adapts the control policy to unknown applications. The explicit NMPC provides 25% energy savings compared to a state-of-the-art algorithm for multi-variable power management of modern GPU sub-systems.