OpenRaiser/Intern-Atlas huggingface dataset:
Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models
Venue: arXiv cs.DS 2020
Year: 2020

We provide prophet inequality algorithms for online weighted matching in general (non-bipartite) graphs, under two well-studied arrival models, namely edge arrival and vertex arrival. The weight of each edge is drawn independently from an a-priori known probability distribution. Under edge arrival, the weight of each edge is revealed upon arrival, and the algorithm decides whether to include it in the matching or not. Under vertex arrival, the weights of all edges from the newly arriving vertex to all previously arrived vertices are revealed, and the algorithm decides which of these edges, if any, to include in the matching. To study these settings, we introduce a novel unified framework of batched prophet inequalities that captures online settings where elements arrive in batches; in particular it captures matching under the two aforementioned arrival models. Our algorithms rely on the construction of suitable online contention resolution scheme (OCRS). We first extend the framework of OCRS to batched-OCRS, we then establish a reduction from batched prophet inequality to batched OCRS, and finally we construct batched OCRSs with selectable ratios of 0.337 and 0.5 for edge and vertex arrival models, respectively. Both results improve the state of the art for the corresponding settings. For the vertex arrival, our result is tight. Interestingly, a pricing-based prophet inequality with comparable competitive ratios is unknown.
Model Predictive Congestion Control for TCP Endpoints
Venue: arXiv cs.NI 2020
Year: 2020

A common problem in science networks and private wide area networks (WANs) is that of achieving predictable data transfers of multiple concurrent flows by maintaining specific pacing rates for each. We address this problem by developing a control algorithm based on concepts from model predictive control (MPC) to produce flows with smooth pacing rates and round trip times (RTTs). In the proposed approach, we model the bottleneck link as a queue and derive a model relating the pacing rate and the RTT. A MPC based control algorithm based on this model is shown to avoid the extreme window (which translates to rate) reduction that exists in current control algorithms when facing network congestion. We have implemented our algorithm as a Linux kernel module. Through simulation and experimental analysis, we show that our algorithm achieves the goals of a low standard deviation of RTT and pacing rate, even when the bottleneck link is fully utilized. In the case of multiple flows, we can assign different rates to each flow and as long as the sum of rates is less than bottleneck rate, they can maintain their assigned pacing rate with low standard deviation. This is achieved even when the flows have different RTTs.
Sequence Preserving Network Traffic Generation
Venue: arXiv cs.NI 2020
Year: 2020

We present the Network Traffic Generator (NTG), a framework for perturbing recorded network traffic with the purpose of generating diverse but realistic background traffic for network simulation and what-if analysis in enterprise environments. The framework preserves many characteristics of the original traffic recorded in an enterprise, as well as sequences of network activities. Using the proposed framework, the original traffic flows are profiled using 200 cross-protocol features. The traffic is aggregated into flows of packets between IP pairs and clustered into groups of similar network activities. Sequences of network activities are then extracted. We examined two methods for extracting sequences of activities: a Markov model and a neural language model. Finally, new traffic is generated using the extracted model. We developed a prototype of the framework and conducted extensive experiments based on two real network traffic collections. Hypothesis testing was used to examine the difference between the distribution of original and generated features, showing that 30-100\% of the extracted features were preserved. Small differences between n-gram perplexities in sequences of network activities in the original and generated traffic, indicate that sequences of network activities were well preserved.
Fill in the BLANC: Human-free quality estimation of document summaries
Venue: arXiv cs.CL 2020
Year: 2020

We present BLANC, a new approach to the automatic estimation of document summary quality. Our goal is to measure the functional performance of a summary with an objective, reproducible, and fully automated method. Our approach achieves this by measuring the performance boost gained by a pre-trained language model with access to a document summary while carrying out its language understanding task on the document's text. We present evidence that BLANC scores have as good correlation with human evaluations as do the ROUGE family of summary quality measurements. And unlike ROUGE, the BLANC method does not require human-written reference summaries, allowing for fully human-free summary quality estimation.
Optimizing Traffic Lights with Multi-agent Deep Reinforcement Learning and V2X communication
Venue: arXiv cs.AI 2020
Year: 2020

We consider a system to optimize duration of traffic signals using multi-agent deep reinforcement learning and Vehicle-to-Everything (V2X) communication. This system aims at analyzing independent and shared rewards for multi-agents to control duration of traffic lights. A learning agent traffic light gets information along its lanes within a circular V2X coverage. The duration cycles of traffic light are modeled as Markov decision Processes. We investigate four variations of reward functions. The first two are unshared-rewards: based on waiting number, and waiting time of vehicles between two cycles of traffic light. The third and fourth functions are: shared-rewards based on waiting cars, and waiting time for all agents. Each agent has a memory for optimization through target network and prioritized experience replay. We evaluate multi-agents through the Simulation of Urban MObility (SUMO) simulator. The results prove effectiveness of the proposed system to optimize traffic signals and reduce average waiting cars to 41.5 % as compared to the traditional periodic traffic control system.
How Good Is a Strategy in a Game With Nature?
Venue: arXiv cs.FL 2020
Year: 2020

We consider games with two antagonistic players --- Éloïse (modelling a program) and Abélard (modelling a byzantine environment) --- and a third, unpredictable and uncontrollable player, that we call Nature. Motivated by the fact that the usual probabilistic semantics very quickly leads to undecidability when considering either infinite game graphs or imperfect-information, we propose two alternative semantics that leads to decidability where the probabilistic one fails: one based on counting and one based on topology.
De-randomized PAC-Bayes Margin Bounds: Applications to Non-convex and Non-smooth Predictors
Venue: arXiv cs.LG 2020
Year: 2020

In spite of several notable efforts, explaining the generalization of deterministic non-smooth deep nets, e.g., ReLU-nets, has remained challenging. Existing approaches for deterministic non-smooth deep nets typically need to bound the Lipschitz constant of such deep nets but such bounds are quite large, may even increase with the training set size yielding vacuous generalization bounds. In this paper, we present a new family of de-randomized PAC-Bayes margin bounds for deterministic non-convex and non-smooth predictors, e.g., ReLU-nets. Unlike PAC-Bayes, which applies to Bayesian predictors, the de-randomized bounds apply to deterministic predictors like ReLU-nets. A specific instantiation of the bound depends on a trade-off between the (weighted) distance of the trained weights from the initialization and the effective curvature (`flatness') of the trained predictor. To get to these bounds, we first develop a de-randomization argument for non-convex but smooth predictors, e.g., linear deep networks (LDNs), which connects the performance of the deterministic predictor with a Bayesian predictor. We then consider non-smooth predictors which for any given input realized as a smooth predictor, e.g., ReLU-nets become some LDNs for any given input, but the realized smooth predictors can be different for different inputs. For such non-smooth predictors, we introduce a new PAC-Bayes analysis which takes advantage of the smoothness of the realized predictors, e.g., LDN, for a given input, and avoids dependency on the Lipschitz constant of the non-smooth predictor. After careful de-randomization, we get a bound for the deterministic non-smooth predictor. We also establish non-uniform sample complexity results based on such bounds. Finally, we present extensive empirical results of our bounds over changing training set size and randomness in labels.
Ensuring Privacy in Location-Based Services: A Model-based Approach
Venue: arXiv cs.CR 2020
Year: 2020

In recent years, the widespread of mobile devices equipped with GPS and communication chips has led to the growing use of location-based services (LBS) in which a user receives a service based on his current location. The disclosure of user's location, however, can raise serious concerns about user privacy in general, and location privacy in particular which led to the development of various location privacy-preserving mechanisms aiming to enhance the location privacy while using LBS applications. In this paper, we propose to model the user mobility pattern and utility of the LBS as a Markov decision process (MDP), and inspired by probabilistic current state opacity notation, we introduce a new location privacy metric, namely $ε-$privacy, that quantifies the adversary belief over the user's current location. We exploit this dynamic model to design a LPPM that while it ensures the utility of service is being fully utilized, independent of the adversary prior knowledge about the user, it can guarantee a user-specified privacy level can be achieved for an infinite time horizon. The overall privacy-preserving framework, including the construction of the user mobility model as a MDP, and design of the proposed LPPM, are demonstrated and validated with real-world experimental data.
Real-time Kinematic Ground Truth for the Oxford RobotCar Dataset
Venue: arXiv cs.RO 2020
Year: 2020

We describe the release of reference data towards a challenging long-term localisation and mapping benchmark based on the large-scale Oxford RobotCar Dataset. The release includes 72 traversals of a route through Oxford, UK, gathered in all illumination, weather and traffic conditions, and is representative of the conditions an autonomous vehicle would be expected to operate reliably in. Using post-processed raw GPS, IMU, and static GNSS base station recordings, we have produced a globally-consistent centimetre-accurate ground truth for the entire year-long duration of the dataset. Coupled with a planned online benchmarking service, we hope to enable quantitative evaluation and comparison of different localisation and mapping approaches focusing on long-term autonomy for road vehicles in urban environments challenged by changing weather.
Relaxing Relationship Queries on Graph Data
Venue: arXiv cs.IR 2020
Year: 2020

In many domains we have witnessed the need to search a large entity-relation graph for direct and indirect relationships between a set of entities specified in a query. A search result, called a semantic association (SA), is typically a compact (e.g., diameter-constrained) connected subgraph containing all the query entities. For this problem of SA search, efficient algorithms exist but will return empty results if some query entities are distant in the graph. To reduce the occurrence of failing query and provide alternative results, we study the problem of query relaxation in the context of SA search. Simply relaxing the compactness constraint will sacrifice the compactness of an SA, and more importantly, may lead to performance issues and be impracticable. Instead, we focus on removing the smallest number of entities from the original failing query, to form a maximum successful sub-query which minimizes the loss of result quality caused by relaxation. We prove that verifying the success of a sub-query turns into finding an entity (called a certificate) that satisfies a distance-based condition about the query entities. To efficiently find a certificate of the success of a maximum sub-query, we propose a best-first search algorithm that leverages distance-based estimation to effectively prune the search space. We further improve its performance by adding two fine-grained heuristics: one based on degree and the other based on distance. Extensive experiments over popular RDF datasets demonstrate the efficiency of our algorithm, which is more scalable than baselines.
iLQGames.jl: Rapidly Designing and Solving Differential Games in Julia
Venue: arXiv cs.MA 2020
Year: 2020

In many problems that involve multiple decision making agents, optimal choices for each agent depend on the choices of others. Differential game theory provides a principled formalism for expressing these coupled interactions and recent work offers efficient approximations to solve these problems to non-cooperative equilibria. iLQGames.jl is a framework for designing and solving differential games, built around the iterative linear-quadratic method. It is written in the Julia programming language to allow flexible prototyping and integration with other research software, while leveraging the high-performance nature of the language to allow real-time execution. The open-source software package can be found at https://github.com/lassepe/iLQGames.jl.
Automatic Estimation of Sphere Centers from Images of Calibrated Cameras
Venue: arXiv cs.CV 2020
Year: 2020

Calibration of devices with different modalities is a key problem in robotic vision. Regular spatial objects, such as planes, are frequently used for this task. This paper deals with the automatic detection of ellipses in camera images, as well as to estimate the 3D position of the spheres corresponding to the detected 2D ellipses. We propose two novel methods to (i) detect an ellipse in camera images and (ii) estimate the spatial location of the corresponding sphere if its size is known. The algorithms are tested both quantitatively and qualitatively. They are applied for calibrating the sensor system of autonomous cars equipped with digital cameras, depth sensors and LiDAR devices.
The Archimedean trap: Why traditional reinforcement learning will probably not yield AGI
Venue: arXiv cs.LG 2020
Year: 2020

After generalizing the Archimedean property of real numbers in such a way as to make it adaptable to non-numeric structures, we demonstrate that the real numbers cannot be used to accurately measure non-Archimedean structures. We argue that, since an agent with Artificial General Intelligence (AGI) should have no problem engaging in tasks that inherently involve non-Archimedean rewards, and since traditional reinforcement learning rewards are real numbers, therefore traditional reinforcement learning probably will not lead to AGI. We indicate two possible ways traditional reinforcement learning could be altered to remove this roadblock.
Linear-frictional contact model for 3D discrete element simulations of granular systems
Venue: arXiv cs.CE 2020
Year: 2020

The linear-frictional contact model is the most commonly used contact mechanism for discrete element (DEM) simulations of granular materials. Linear springs with a frictional slider are used for modeling interactions in directions normal and tangential to the contact surface. Although the model is simple in two dimensions, its implementation in 3D faces certain subtle challenges, and the particle interactions that occur within a single time-step require careful modeling with a robust algorithm. The paper details a 3D algorithm that accounts for the changing direction of the tangential force within a time-step, the transition from elastic to slip behavior within a time-step, possible contact sliding during only part of a time-step, and twirling and rotation of the tangential force during a time-step. Without three of these adjustments, errors are introduced in the incremental stiffness of an assembly. Without the fourth adjustment, the resulting stress tensor is not only incorrect, it is no longer a tensor. The algorithm also computes the work increments during a time-step, both elastic and dissipative.
Fractional-Order Models for the Static and Dynamic Analysis of Nonlocal Plates
Venue: arXiv cs.CE 2020
Year: 2020

This study presents the analytical formulation and the finite element solution of fractional order nonlocal plates under both Mindlin and Kirchoff formulations. By employing consistent definitions for fractional-order kinematic relations, the governing equations and the associated boundary conditions are derived based on variational principles. Remarkably, the fractional-order nonlocal model gives rise to a self-adjoint and positive-definite system that accepts a unique solution. Further, owing to the difficulty in obtaining analytical solutions to this fractional-order differ-integral problem, a 2D finite element model for the fractional-order governing equations is presented. Following a thorough validation with benchmark problems, the 2D fractional finite element model is used to study the static as well as the free dynamic response of fractional-order plates subject to various loading and boundary conditions. It is established that the fractional-order nonlocality leads to a reduction in the stiffness of the plate structure thereby increasing the displacements and reducing the natural frequency of vibration of the plates. Further, it is seen that the effect of nonlocality is stronger on the higher modes of vibration when compared to the fundamental mode. These effects of the fractional-order nonlocality are noted irrespective of the nature of the boundary conditions. More specifically, the fractional-order model of nonlocal plates is free from boundary effects that lead to paradoxical predictions such as hardening and absence of nonlocal effects in classical integral approaches to nonlocal elasticity. This consistency in the predictions is a result of the well-posed nature of the fractional-order governing equations that accept a unique solution.
TensorShield: Tensor-based Defense Against Adversarial Attacks on Images
Venue: arXiv cs.LG 2020
Year: 2020

Recent studies have demonstrated that machine learning approaches like deep neural networks (DNNs) are easily fooled by adversarial attacks. Subtle and imperceptible perturbations of the data are able to change the result of deep neural networks. Leveraging vulnerable machine learning methods raises many concerns especially in domains where security is an important factor. Therefore, it is crucial to design defense mechanisms against adversarial attacks. For the task of image classification, unnoticeable perturbations mostly occur in the high-frequency spectrum of the image. In this paper, we utilize tensor decomposition techniques as a preprocessing step to find a low-rank approximation of images which can significantly discard high-frequency perturbations. Recently a defense framework called Shield could "vaccinate" Convolutional Neural Networks (CNN) against adversarial examples by performing random-quality JPEG compressions on local patches of images on the ImageNet dataset. Our tensor-based defense mechanism outperforms the SLQ method from Shield by 14% against FastGradient Descent (FGSM) adversarial attacks, while maintaining comparable speed.
Using Machine Learning to predict extreme events in the Hénon map
Venue: arXiv cs.LG 2020
Year: 2020

Machine Learning (ML) inspired algorithms provide a flexible set of tools for analyzing and forecasting chaotic dynamical systems. We here analyze the performance of one algorithm for the prediction of extreme events in the two-dimensional Hénon map at the classical parameters. The task is to determine whether a trajectory will exceed a threshold after a set number of time steps into the future. This task has a geometric interpretation within the dynamics of the Hénon map, which we use to gauge the performance of the neural networks that are used in this work. We analyze the dependence of the success rate of the ML models on the prediction time $T$ , the number of training samples $N_T$ and the size of the network $N_p$. We observe that in order to maintain a certain accuracy, $N_T \propto exp(2 h T)$ and $N_p \propto exp(hT)$, where $h$ is the topological entropy. Similar relations between the intrinsic chaotic properties of the dynamics and ML parameters might be observable in other systems as well.
SupRB: A Supervised Rule-based Learning System for Continuous Problems
Venue: arXiv cs.LG 2020
Year: 2020

We propose the SupRB learning system, a new Pittsburgh-style learning classifier system (LCS) for supervised learning on multi-dimensional continuous decision problems. SupRB learns an approximation of a quality function from examples (consisting of situations, choices and associated qualities) and is then able to make an optimal choice as well as predict the quality of a choice in a given situation. One area of application for SupRB is parametrization of industrial machinery. In this field, acceptance of the recommendations of machine learning systems is highly reliant on operators' trust. While an essential and much-researched ingredient for that trust is prediction quality, it seems that this alone is not enough. At least as important is a human-understandable explanation of the reasoning behind a recommendation. While many state-of-the-art methods such as artificial neural networks fall short of this, LCSs such as SupRB provide human-readable rules that can be understood very easily. The prevalent LCSs are not directly applicable to this problem as they lack support for continuous choices. This paper lays the foundations for SupRB and shows its general applicability on a simplified model of an additive manufacturing problem.
Adaptive Propagation Graph Convolutional Network
Venue: arXiv cs.LG 2020
Year: 2020

Graph convolutional networks (GCNs) are a family of neural network models that perform inference on graph data by interleaving vertex-wise operations and message-passing exchanges across nodes. Concerning the latter, two key questions arise: (i) how to design a differentiable exchange protocol (e.g., a 1-hop Laplacian smoothing in the original GCN), and (ii) how to characterize the trade-off in complexity with respect to the local updates. In this paper, we show that state-of-the-art results can be achieved by adapting the number of communication steps independently at every node. In particular, we endow each node with a halting unit (inspired by Graves' adaptive computation time) that after every exchange decides whether to continue communicating or not. We show that the proposed adaptive propagation GCN (AP-GCN) achieves superior or similar results to the best proposed models so far on a number of benchmarks, while requiring a small overhead in terms of additional parameters. We also investigate a regularization term to enforce an explicit trade-off between communication and accuracy. The code for the AP-GCN experiments is released as an open-source library.