OpenRaiser/Intern-Atlas huggingface dataset:
Native Chemical Automata and the Thermodynamic Interpretation of Their Experimental Accept/Reject Responses
Venue: arXiv cs.ET 2019
Year: 2019

The theory of computation is based on abstract computing automata which can be classified into a three-class hierarchy: Finite Automata (FA), Push-down Automata (PDA) and the Turing Machines (TM). Each class corresponds to grammar/language classes. The function of the automata consists on recognizing words in a language generated by some grammar and expressed with letters from an alphabet. Such automata are, in principle, abstract entities and with suitable combinations of them we can represent any computation, no matter how complex. Their physical implementations are possible in any information carrying and recognition contexts and media, such as electrons in semiconductors, certain biomolecules in biology or even non-biological molecules. Here we describe and build non-biochemistry (inorganic chemistry) examples of a FA, PDA and TM computations carried out by specific laboratory realizations of the automata. For each of the three realizations we find a thermodynamic metric, based on enthalpy for the FA and PDA, and on the Gibbs free energy for the TM, to both assess the results of computation and as a first step towards quantifying the energetic cost of such computations.
A Low-Complexity Cache-Aided Multi-antenna Content Delivery Scheme
Venue: arXiv cs.IT 2019
Year: 2019

We study downlink beamforming in a single-cell network with a multi-antenna base station (BS) serving cache-enabled users. For a given common rate of the files in the system, we first formulate the minimum transmit power with beamforming at the BS as a non-convex optimization problem. This corresponds to a multiple multicast problem, to which a stationary solution can be efficiently obtained through successive convex approximation (SCA). It is observed that the complexity of the problem grows exponentially with the number of subfiles delivered to each user in each time slot, which itself grows exponentially with the number of users in the system. Therefore, we introduce a low-complexity alternative through time-sharing that limits the number of subfiles that can be received by a user in each time slot. It is shown through numerical simulations that, the reduced-complexity beamforming scheme has minimal performance gap compared to transmitting all the subfiles jointly, and outperforms the state-of-the-art low-complexity scheme at all SNR and rate values with sufficient spatial degrees of freedom, and in the high SNR/high rate regime when the number of spatial degrees of freedom is limited.
Machine Learning Meets Quantitative Planning: Enabling Self-Adaptation in Autonomous Robots
Venue: arXiv cs.AI 2019
Year: 2019

Modern cyber-physical systems (e.g., robotics systems) are typically composed of physical and software components, the characteristics of which are likely to change over time. Assumptions about parts of the system made at design time may not hold at run time, especially when a system is deployed for long periods (e.g., over decades). Self-adaptation is designed to find reconfigurations of systems to handle such run-time inconsistencies. Planners can be used to find and enact optimal reconfigurations in such an evolving context. However, for systems that are highly configurable, such planning becomes intractable due to the size of the adaptation space. To overcome this challenge, in this paper we explore an approach that (a) uses machine learning to find Pareto-optimal configurations without needing to explore every configuration and (b) restricts the search space to such configurations to make planning tractable. We explore this in the context of robot missions that need to consider task timeliness and energy consumption. An independent evaluation shows that our approach results in high-quality adaptation plans in uncertain and adversarial environments.
Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems
Venue: arXiv cs.DS 2019
Year: 2019

We present prior robust algorithms for a large class of resource allocation problems where requests arrive one-by-one (online), drawn independently from an unknown distribution at every step. We design a single algorithm that, for every possible underlying distribution, obtains a $1-ε$ fraction of the profit obtained by an algorithm that knows the entire request sequence ahead of time. The factor $ε$ approaches $0$ when no single request consumes/contributes a significant fraction of the global consumption/contribution by all requests together. We show that the tradeoff we obtain here that determines how fast $ε$ approaches $0$, is near optimal: we give a nearly matching lower bound showing that the tradeoff cannot be improved much beyond what we obtain. Going beyond the model of a static underlying distribution, we introduce the adversarial stochastic input model, where an adversary, possibly in an adaptive manner, controls the distributions from which the requests are drawn at each step. Placing no restriction on the adversary, we design an algorithm that obtains a $1-ε$ fraction of the optimal profit obtainable w.r.t. the worst distribution in the adversarial sequence. In the offline setting we give a fast algorithm to solve very large LPs with both packing and covering constraints. We give algorithms to approximately solve (within a factor of $1+ε$) the mixed packing-covering problem with $O(\frac{γm \log (n/δ)}{ε^2})$ oracle calls where the constraint matrix of this LP has dimension $n\times m$, the success probability of the algorithm is $1-δ$, and $γ$ quantifies how significant a single request is when compared to the sum total of all requests. We discuss implications of our results to several special cases including online combinatorial auctions, network routing and the adwords problem.
Rethinking System Health Management
Venue: arXiv cs.AI 2019
Year: 2019

Health management of complex dynamic systems has traditionally evolved separately from automated control, planning, and scheduling (generally referred to in the paper as decision making). A goal of Integrated System Health Management has been to enable coordination between system health management and decision making, although successful practical implementations have remained limited. This paper proposes that, rather than being treated as connected, yet distinct entities, system health management and decision making should be unified in their formulations. Enabled by advances in modeling and computing, we argue that the unified approach will increase a system's operational effectiveness and may also lead to a lower overall system complexity. We overview the prevalent system health management methodology and illustrate its limitations through numerical examples. We then describe the proposed unification approach and show how it accommodates the typical system health management concepts.
One-Pass Sparsified Gaussian Mixtures
Venue: arXiv cs.LG 2019
Year: 2019

We present a one-pass sparsified Gaussian mixture model (SGMM). Given $N$ data points in $P$ dimensions, $X$, the model fits $K$ Gaussian distributions to $X$ and (softly) classifies each point to these clusters. After paying an up-front cost of $\mathcal{O}(NP\log P)$ to precondition the data, we subsample $Q$ entries of each data point and discard the full $P$-dimensional data. SGMM operates in $\mathcal{O}(KNQ)$ time per iteration for diagonal or spherical covariances, independent of $P$, while estimating the model parameters in the full $P$-dimensional space, making it one-pass and hence suitable for streaming data. We derive the maximum likelihood estimators for the parameters in the sparsified regime, demonstrate clustering on synthetic and real data, and show that SGMM is faster than GMM while preserving accuracy.
Clustering-Correcting Codes
Venue: arXiv cs.IT 2019
Year: 2019

A new family of codes, called clustering-correcting codes, is presented in this paper. This family of codes is motivated by the special structure of data that is stored in DNA-based storage systems. The data stored in these systems has the form of unordered sequences, also called strands, and every strand is synthesized thousands to millions of times, where some of these copies are read back during sequencing. Due to the unordered structure of the strands, an important task in the decoding process is to place them in their correct order. This is usually accomplished by allocating a part of the strand for an index. However, in the presence of errors in the index field, important information on the order of the strands may be lost. Clustering-correcting codes ensure that if the distance between the index fields of two strands is small, then there will be a large distance between their data fields. It is shown how this property enables to place the strands together in their correct clusters even in the presence of errors. We present lower and upper bounds on the size of clustering-correcting codes and an explicit construction of these codes which uses only a single bit of redundancy.
Fisher-Bures Adversary Graph Convolutional Networks
Venue: arXiv cs.LG 2019
Year: 2019

In a graph convolutional network, we assume that the graph $G$ is generated wrt some observation noise. During learning, we make small random perturbations $ΔG$ of the graph and try to improve generalization. Based on quantum information geometry, $ΔG$ can be characterized by the eigendecomposition of the graph Laplacian matrix. We try to minimize the loss wrt the perturbed $G+Δ{G}$ while making $Δ{G}$ to be effective in terms of the Fisher information of the neural network. Our proposed model can consistently improve graph convolutional networks on semi-supervised node classification tasks with reasonable computational overhead. We present three different geometries on the manifold of graphs: the intrinsic geometry measures the information theoretic dynamics of a graph; the extrinsic geometry characterizes how such dynamics can affect externally a graph neural network; the embedding geometry is for measuring node embeddings. These new analytical tools are useful in developing a good understanding of graph neural networks and fostering new techniques.
Object-oriented requirements: reusable, understandable, verifiable
Venue: arXiv cs.SE 2019
Year: 2019

Insufficient requirements reusability, understandability and verifiability jeopardize software projects. Empirical studies show little success in improving these qualities separately. Applying object-oriented thinking to requirements leads to their unified treatment. An online library of reusable requirement templates implements recurring requirement structures, offering a starting point for practicing the unified approach.
Investigation on Combining 3D Convolution of Image Data and Optical Flow to Generate Temporal Action Proposals
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, several variants of two-stream architectures for temporal action proposal generation in long, untrimmed videos are presented. Inspired by the recent advances in the field of human action recognition utilizing 3D convolutions in combination with two-stream networks and based on the Single-Stream Temporal Action Proposals (SST) architecture, four different two-stream architectures utilizing sequences of images on one stream and sequences of images of optical flow on the other stream are subsequently investigated. The four architectures fuse the two separate streams at different depths in the model; for each of them, a broad range of parameters is investigated systematically as well as an optimal parametrization is empirically determined. The experiments on the THUMOS'14 dataset show that all four two-stream architectures are able to outperform the original single-stream SST and achieve state of the art results. Additional experiments revealed that the improvements are not restricted to a single method of calculating optical flow by exchanging the formerly used method of Brox with FlowNet2 and still achieving improvements.
Graph Data on the Web: extend the pivot, don't reinvent the wheel
Venue: arXiv cs.DB 2019
Year: 2019

This article is a collective position paper from the Wimmics research team, expressing our vision of how Web graph data technologies should evolve in the future in order to ensure a high-level of interoperability between the many types of applications that produce and consume graph data. Wimmics stands for Web-Instrumented Man-Machine Interactions, Communities, and Semantics. We are a joint research team between INRIA Sophia Antipolis-M{é}diterran{é}e and I3S (CNRS and Universit{é} C{ô}te d'Azur). Our challenge is to bridge formal semantics and social semantics on the web. Our research areas are graph-oriented knowledge representation, reasoning and operationalization to model and support actors, actions and interactions in web-based epistemic communities. The application of our research is supporting and fostering interactions in online communities and management of their resources. In this position paper, we emphasize the need to extend the semantic Web standard stack to address and fulfill new graph data needs, as well as the importance of remaining compatible with existing recommendations, in particular the RDF stack, to avoid the painful duplication of models, languages, frameworks, etc. The following sections group motivations for different directions of work and collect reasons for the creation of a working group on RDF 2.0 and other recommendations of the RDF family.
InceptionGCN: Receptive Field Aware Graph Convolutional Network for Disease Prediction
Venue: arXiv cs.LG 2019
Year: 2019

Geometric deep learning provides a principled and versatile manner for the integration of imaging and non-imaging modalities in the medical domain. Graph Convolutional Networks (GCNs) in particular have been explored on a wide variety of problems such as disease prediction, segmentation, and matrix completion by leveraging large, multimodal datasets. In this paper, we introduce a new spectral domain architecture for deep learning on graphs for disease prediction. The novelty lies in defining geometric 'inception modules' which are capable of capturing intra- and inter-graph structural heterogeneity during convolutions. We design filters with different kernel sizes to build our architecture. We show our disease prediction results on two publicly available datasets. Further, we provide insights on the behaviour of regular GCNs and our proposed model under varying input scenarios on simulated data.
From Hotelling to Load Balancing: Approximation and the Principle of Minimum Differentiation
Venue: arXiv cs.GT 2019
Year: 2019

Competing firms tend to select similar locations for their stores. This phenomenon, called the principle of minimum differentiation, was captured by Hotelling with a landmark model of spatial competition but is still the object of an ongoing scientific debate. Although consistently observed in practice, many more realistic variants of Hotelling's model fail to support minimum differentiation or do not have pure equilibria at all. In particular, it was recently proven for a generalized model which incorporates negative network externalities and which contains Hotelling's model and classical selfish load balancing as special cases, that the unique equilibria do not adhere to minimum differentiation. Furthermore, it was shown that for a significant parameter range pure equilibria do not exist. We derive a sharp contrast to these previous results by investigating Hotelling's model with negative network externalities from an entirely new angle: approximate pure subgame perfect equilibria. This approach allows us to prove analytically and via agent-based simulations that approximate equilibria having good approximation guarantees and that adhere to minimum differentiation exist for the full parameter range of the model. Moreover, we show that the obtained approximate equilibria have high social welfare.
Grid-Constrained Distributed Optimization for Frequency Control with Low-Voltage Flexibility
Venue: arXiv cs.SY 2019
Year: 2019

Providing frequency control services with flexible assets connected to the low-voltage distribution grid, amongst which residential battery storage or electrical hot water boilers, can lead to congestion problems and voltage issues in the distribution grid. In order to mitigate these problems, a new regulation has been put in place in Belgium, imposing a specific constraint: in any circle with a radius of 100m, there can be at maximum 10 connection points providing frequency control at any time. This paper presents an impact analysis and a coordination strategy of a Flexibility Service Provider (FSP) that operates a pool of assets and is exposed to this new regulatory constraint. Results show that at 5% participation, only 90% of total control capacity can be used, with a large difference between neighbourhoods with different population densities. A distributed optimization framework to coordinate the assets arises naturally, in which the assets are able to keep their local cost functions private and only have to communicate with neighbouring assets that are geographically close, and with the FSP. Analysis of the proposed distributed optimization algorithm shows a clear trade-off between optimality gap, owing to the mixed-integer nature of the problem, and iterations to convergence.
Reachability and Coverage Planning for Connected Agents: Extended Version
Venue: arXiv cs.AI 2019
Year: 2019

Motivated by the increasing appeal of robots in information-gathering missions, we study multi-agent path planning problems in which the agents must remain interconnected. We model an area by a topological graph specifying the movement and the connectivity constraints of the agents. We study the theoretical complexity of the reachability and the coverage problems of a fleet of connected agents on various classes of topological graphs. We establish the complexity of these problems on known classes, and introduce a new class called sight-moveable graphs which admit efficient algorithms.
Adaptive Fault Detection exploiting Redundancy with Uncertainties in Space and Time
Venue: arXiv cs.SY 2019
Year: 2019

The Internet of Things (IoT) connects millions of devices of different cyber-physical systems (CPSs) providing the CPSs additional (implicit) redundancy during runtime. However, the increasing level of dynamicity, heterogeneity, and complexity adds to the system's vulnerability, and challenges its ability to react to faults. Self-healing is an increasingly popular approach for ensuring resilience, that is, a proper monitoring and recovery, in CPSs. This work encodes and searches an adaptive knowledge base in Prolog/ProbLog that models relations among system variables given that certain implicit redundancy exists in the system. We exploit the redundancy represented in our knowledge base to generate adaptive runtime monitors which compares related signals by considering uncertainties in space and time. This enables the comparison of uncertain, asynchronous, multi-rate and delayed measurements. The monitor is used to trigger the recovery process of a self-healing mechanism. We demonstrate our approach by deploying it in a real-world CPS prototype of a rover whose sensors are susceptible to failure.
Labeler-hot Detection of EEG Epileptic Transients
Venue: arXiv cs.LG 2019
Year: 2019

Preventing early progression of epilepsy and so the severity of seizures requires an effective diagnosis. Epileptic transients indicate the ability to develop seizures but humans overlook such brief events in an electroencephalogram (EEG) what compromises patient treatment. Traditionally, training of the EEG event detection algorithms has relied on ground truth labels, obtained from the consensus of the majority of labelers. In this work, we go beyond labeler consensus on EEG data. Our event descriptor integrates EEG signal features with one-hot encoded labeler category that is a key to improved generalization performance. Notably, boosted decision trees take advantage of singly-labeled but more varied training sets. Our quantitative experiments show the proposed labeler-hot epileptic event detector consistently outperforms a consensus-trained detector and maintains confidence bounds of the detection. The results on our infant EEG recordings suggest datasets can gain higher event variety faster and thus better performance by shifting available human effort from consensus-oriented to separate labeling when labels include both, the event and the labeler category.
Robot kinematic structure classification from time series of visual data
Venue: arXiv cs.RO 2019
Year: 2019

In this paper we present a novel algorithm to solve the robot kinematic structure identification problem. Given a time series of data, typically obtained processing a set of visual observations, the proposed approach identifies the ordered sequence of links associated to the kinematic chain, the joint type interconnecting each couple of consecutive links, and the input signal influencing the relative motion. Compared to the state of the art, the proposed algorithm has reduced computational costs, and is able to identify also the joints' type sequence.
Publicness, Privacy and Confidentiality in the Single-Serving Quantum Broadcast Channel
Venue: arXiv cs.IT 2019
Year: 2019

The 2-receiver broadcast channel is studied: a network with three parties where the transmitter and one of the receivers are the primarily involved parties and the other receiver considered as third party. The messages that are determined to be communicated are classified into public, private and confidential based on the information they convey. The public message contains information intended for both parties and is required to be decoded correctly by both of them, the private message is intended for the primary party only, however, there is no secrecy requirement imposed upon it meaning that it can possibly be exposed to the third party and finally the confidential message containing information intended exclusively for the primary party such that this information must be kept completely secret from the other receiver. A trade-off arises between the rates of the three messages, when one of the rates is high, the other rates may need to be reduced to guarantee the reliable transmission of all three messages. The encoder performs the necessary equivocation by virtue of dummy random numbers whose rate is assumed to be limited and should be considered in the trade-off as well. We study this trade-off in the one-shot regime of a quantum broadcast channel by providing achievability and (weak) converse regions. In the achievability, we prove and use a conditional version of the convex-split lemma as well as position-based decoding. By studying the asymptotic behaviour of our bounds, we will recover several well-known asymptotic results in the literature.