OpenRaiser/Intern-Atlas huggingface dataset:
Decentralized Coded Caching Without File Splitting
Venue: arXiv cs.IT 2019
Year: 2019

Coded caching is an effective technique to reduce the redundant traffic in wireless networks. The existing coded caching schemes require the splitting of files into a possibly large number of subfiles, i.e., they perform coded subfile caching. Keeping the files intact during the caching process would actually be appealing, broadly speaking because of its simpler implementation. However, little is known about the effectiveness of this coded file caching in reducing the data delivery rate. In this paper, we propose such a file caching scheme which uses a decentralized algorithm for content placement and either an online clique cover or matching algorithm for the delivery of missing data. We derive approximations for the expected delivery rate of both schemes using the differential equations method, and show them to be tight through concentration analysis and computer simulations. Our numerical results demonstrate that the proposed coded file caching is significantly more effective than uncoded caching in reducing the delivery rate. We furthermore show the additional improvement in the performance of the proposed scheme when its application is extended to subfile caching with a small number of subfiles.
Improving Robustness of ML Classifiers against Realizable Evasion Attacks Using Conserved Features
Venue: arXiv cs.CR 2019
Year: 2019

Machine learning (ML) techniques are increasingly common in security applications, such as malware and intrusion detection. However, ML models are often susceptible to evasion attacks, in which an adversary makes changes to the input (such as malware) in order to avoid being detected. A conventional approach to evaluate ML robustness to such attacks, as well as to design robust ML, is by considering simplified feature-space models of attacks, where the attacker changes ML features directly to effect evasion, while minimizing or constraining the magnitude of this change. We investigate the effectiveness of this approach to designing robust ML in the face of attacks that can be realized in actual malware (realizable attacks). We demonstrate that in the context of structure-based PDF malware detection, such techniques appear to have limited effectiveness, but they are effective with content-based detectors. In either case, we show that augmenting the feature space models with conserved features (those that cannot be unilaterally modified without compromising malicious functionality) significantly improves performance. Finally, we show that feature space models enable generalized robustness when faced with a variety of realizable attacks, as compared to classifiers which are tuned to be robust to a specific realizable attack.
Algorithmic Networks: central time to trigger expected emergent open-endedness
Venue: arXiv cs.IT 2019
Year: 2019

This article investigates emergence and complexity in complex systems that can share information on a network. To this end, we use a theoretical approach from information theory, computability theory, and complex networks. One key studied question is how much emergent complexity (or information) arises when a population of computable systems is networked compared with when this population is isolated. First, we define a general model for networked theoretical machines, which we call algorithmic networks. Then, we narrow our scope to investigate algorithmic networks that optimize the average fitnesses of nodes in a scenario in which each node imitates the fittest neighbor and the randomly generated population is networked by a time-varying graph. We show that there are graph-topological conditions that cause these algorithmic networks to have the property of expected emergent open-endedness for large enough populations. In other words, the expected emergent algorithmic complexity of a node tends to infinity as the population size tends to infinity. Given a dynamic network, we show that these conditions imply the existence of a central time to trigger expected emergent open-endedness. Moreover, we show that networks with small diameter compared to the network size meet these conditions. We also discuss future research based on how our results are related to some problems in network science, information theory, computability theory, distributed computing, game theory, evolutionary biology, and synergy in complex systems.
Boosting with Lexicographic Programming: Addressing Class Imbalance without Cost Tuning
Venue: arXiv cs.CV 2019
Year: 2019

A large amount of research effort has been dedicated to adapting boosting for imbalanced classification. However, boosting methods are yet to be satisfactorily immune to class imbalance, especially for multi-class problems. This is because most of the existing solutions for handling class imbalance rely on expensive cost set tuning for determining the proper level of compensation. We show that the assignment of weights to the component classifiers of a boosted ensemble can be thought of as a game of Tug of War between the classes in the margin space. We then demonstrate how this insight can be used to attain a good compromise between the rare and abundant classes without having to resort to cost set tuning, which has long been the norm for imbalanced classification. The solution is based on a lexicographic linear programming framework which requires two stages. Initially, class-specific component weight combinations are found so as to minimize a hinge loss individually for each of the classes. Subsequently, the final component weights are assigned so that the maximum deviation from the class-specific minimum loss values (obtained in the previous stage) is minimized. Hence, the proposal is not only restricted to two-class situations, but is also readily applicable to multi-class problems. Additionally,we also derive the dual formulation corresponding to the proposed framework. Experiments conducted on artificial and real-world imbalanced datasets as well as on challenging applications such as hyperspectral image classification and ImageNet classification establish the efficacy of the proposal.
EuroSAT: A Novel Dataset and Deep Learning Benchmark for Land Use and Land Cover Classification
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we address the challenge of land use and land cover classification using Sentinel-2 satellite images. The Sentinel-2 satellite images are openly and freely accessible provided in the Earth observation program Copernicus. We present a novel dataset based on Sentinel-2 satellite images covering 13 spectral bands and consisting out of 10 classes with in total 27,000 labeled and geo-referenced images. We provide benchmarks for this novel dataset with its spectral bands using state-of-the-art deep Convolutional Neural Network (CNNs). With the proposed novel dataset, we achieved an overall classification accuracy of 98.57%. The resulting classification system opens a gate towards a number of Earth observation applications. We demonstrate how this classification system can be used for detecting land use and land cover changes and how it can assist in improving geographical maps. The geo-referenced dataset EuroSAT is made publicly available at https://github.com/phelber/eurosat.
A Simple Balanced Search Tree with No Balance Criterion
Venue: arXiv cs.DS 2019
Year: 2019

We present a method that maintains a balanced binary search tree without using any tree balance criterion at all, with the ultimate aim of maximum simplicity. In fact, our method is highly intuitive, and we only need to add minimal extra code and a simple partial-rebuilding algorithm to a naive binary search tree. Our method will be suitable as a highly simple and short solution when amortized logarithmic costs are enough.
Persistent homology for low-complexity models
Venue: arXiv cs.CG 2019
Year: 2019

We show that recent results on randomized dimension reduction schemes that exploit structural properties of data can be applied in the context of persistent homology. In the spirit of compressed sensing, the dimension reduction is determined by the Gaussian width of a structure associated to the data set, rather than its size, and such a reduction can be computed efficiently. We further relate the Gaussian width to the doubling dimension of a finite metric space, which appears in the study of the complexity of other methods for approximating persistent homology. We can therefore literally replace the ambient dimension by an intrinsic notion of dimension related to the structure of the data.
Fault-tolerant additive weighted geometric spanners
Venue: arXiv cs.CG 2019
Year: 2019

Let S be a set of n points and let w be a function that assigns non-negative weights to points in S. The additive weighted distance d_w(p, q) between two points p,q belonging to S is defined as w(p) + d(p, q) + w(q) if p \ne q and it is zero if p = q. Here, d(p, q) denotes the (geodesic) Euclidean distance between p and q. A graph G(S, E) is called a t-spanner for the additive weighted set S of points if for any two points p and q in S the distance between p and q in graph G is at most t.d_w(p, q) for a real number t > 1. Here, d_w(p,q) is the additive weighted distance between p and q. For some integer k \geq 1, a t-spanner G for the set S is a (k, t)-vertex fault-tolerant additive weighted spanner, denoted with (k, t)-VFTAWS, if for any set S' \subset S with cardinality at most k, the graph G \ S' is a t-spanner for the points in S \ S'. For any given real number ε> 0, we obtain the following results: - When the points in S belong to Euclidean space R^d, an algorithm to compute a (k,(2 + ε))-VFTAWS with O(kn) edges for the metric space (S, d_w). Here, for any two points p, q \in S, d(p, q) is the Euclidean distance between p and q in R^d. - When the points in S belong to a simple polygon P, for the metric space (S, d_w), one algorithm to compute a geodesic (k, (2 + ε))-VFTAWS with O(\frac{k n}{ε^{2}}\lg{n}) edges and another algorithm to compute a geodesic (k, (\sqrt{10} + ε))-VFTAWS with O(kn(\lg{n})^2) edges. Here, for any two points p, q \in S, d(p, q) is the geodesic Euclidean distance along the shortest path between p and q in P. - When the points in $S$ lie on a terrain T, an algorithm to compute a geodesic (k, (2 + ε))-VFTAWS with O(\frac{k n}{ε^{2}}\lg{n}) edges.
Democratic Fair Allocation of Indivisible Goods
Venue: arXiv cs.GT 2019
Year: 2019

We study the problem of fairly allocating indivisible goods to groups of agents. Agents in the same group share the same set of goods even though they may have different preferences. Previous work has focused on unanimous fairness, in which all agents in each group must agree that their group's share is fair. Under this strict requirement, fair allocations exist only for small groups. We introduce the concept of democratic fairness, which aims to satisfy a certain fraction of the agents in each group. This concept is better suited to large groups such as cities or countries. We present protocols for democratic fair allocation among two or more arbitrarily large groups of agents with monotonic, additive, or binary valuations. For two groups with arbitrary monotonic valuations, we give an efficient protocol that guarantees envy-freeness up to one good for at least $1/2$ of the agents in each group, and prove that the $1/2$ fraction is optimal. We also present other protocols that make weaker fairness guarantees to more agents in each group, or to more groups. Our protocols combine techniques from different fields, including combinatorial game theory, cake cutting, and voting.
Slick: Secure Middleboxes using Shielded Execution
Venue: arXiv cs.CR 2019
Year: 2019

Cloud computing offers the economies of scale for computational resources with the ease of management, elasticity, and fault tolerance. To take advantage of these benefits, many enterprises are contemplating to outsource the middlebox processing services in the cloud. However, middleboxes that process confidential and private data cannot be securely deployed in the untrusted environment of the cloud. To securely outsource middleboxes to the cloud, the state-of-the-art systems advocate network processing over the encrypted traffic. Unfortunately, these systems support only restrictive middlebox functionalities, and incur prohibitively high overheads due to the complex computations involved over the encrypted traffic. This motivated the design of Slick --- a secure middlebox framework for deploying high-performance Network Functions (NFs) on untrusted commodity servers. Slick exposes a generic interface based on Click to design and implement a wide-range of NFs using its out-of-the box elements and C++ extensions. Slick leverages SCONE (a shielded execution framework based on Intel SGX) and DPDK to securely process confidential data at line rate. More specifically, Slick provides hardware-assisted memory protection, and configuration and attestation service for seamless and verifiable deployment of middleboxes. We have also added several new features for commonly required functionalities: new specialized Click elements for secure packet processing, secure shared memory packet transfer for NFs chaining, secure state persistence, an efficient on-NIC timer for SGX enclaves, and memory safety against DPDK-specific Iago attacks. Furthermore, we have implemented several SGX-specific optimizations in Slick. Our evaluation shows that Slick achieves near-native throughput and latency.
On the interaction between Autonomous Mobility-on-Demand systems and the power network: models and coordination algorithms
Venue: arXiv cs.SY 2019
Year: 2019

We study the interaction between a fleet of electric, self-driving vehicles servicing on-demand transportation requests (referred to as Autonomous Mobility-on-Demand, or AMoD, system) and the electric power network. We propose a model that captures the coupling between the two systems stemming from the vehicles' charging requirements and captures time-varying customer demand and power generation costs, road congestion, battery depreciation, and power transmission and distribution constraints. We then leverage the model to jointly optimize the operation of both systems. We devise an algorithmic procedure to losslessly reduce the problem size by bundling customer requests, allowing it to be efficiently solved by off-the-shelf linear programming solvers. Next, we show that the socially optimal solution to the joint problem can be enforced as a general equilibrium, and we provide a dual decomposition algorithm that allows self-interested agents to compute the market clearing prices without sharing private information. We assess the performance of the mode by studying a hypothetical AMoD system in Dallas-Fort Worth and its impact on the Texas power network. Lack of coordination between the AMoD system and the power network can cause a 4.4% increase in the price of electricity in Dallas-Fort Worth; conversely, coordination between the AMoD system and the power network could reduce electricity expenditure compared to the case where no cars are present (despite the increased demand for electricity) and yield savings of up $147M/year. Finally, we provide a receding-horizon implementation and assess its performance with agent-based simulations. Collectively, the results of this paper provide a first-of-a-kind characterization of the interaction between electric-powered AMoD systems and the power network, and shed additional light on the economic and societal value of AMoD.
Minimizing the Age of Information through Queues
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we investigate scheduling policies that minimize the age of information in single-hop queueing systems. We propose a Last-Generated, First-Serve (LGFS) scheduling policy, in which the packet with the earliest generation time is processed with the highest priority. If the service times are i.i.d. exponentially distributed, the preemptive LGFS policy is proven to be age-optimal in a stochastic ordering sense. If the service times are i.i.d. and satisfy a New-Better-than-Used (NBU) distributional property, the non-preemptive LGFS policy is shown to be within a constant gap from the optimum age performance. These age-optimality results are quite general: (i) They hold for arbitrary packet generation times and arrival times (including out-of-order packet arrivals), (ii) They hold for multi-server packet scheduling with the possibility of replicating a packet over multiple servers, (iii) They hold for minimizing not only the time-average age and mean peak age, but also for minimizing the age stochastic process and any non-decreasing functional of the age stochastic process. If the packet generation time is equal to packet arrival time, the LGFS policies reduce to the Last-Come, First-Serve (LCFS) policies. Hence, the age optimality results of LCFS-type policies are also established.
Dynamic Markers: UAV landing proof of concept
Venue: arXiv cs.RO 2019
Year: 2019

In this paper, we introduce a dynamic fiducial marker which can change its appearance according to the spatiotemporal requirements of the visual perception task of a mobile robot using a camera as the sensor. We present a control scheme to dynamically change the appearance of the marker in order to increase the range of detection and to assure a better accuracy on the close range. The marker control takes into account the camera to marker distance (which influences the scale of the marker in image coordinates) to select which fiducial markers to display. Hence, we realize a tight coupling between the visual pose control of the mobile robot and the appearance of the dynamic fiducial marker. Additionally, we discuss the practical implications of time delays due to processing time and communication delays between the robot and the marker. Finally, we propose a real-time dynamic marker visual servoing control scheme for quadcopter landing and evaluate the performance on a real-world example.
MultiNet: Multi-Modal Multi-Task Learning for Autonomous Driving
Venue: arXiv cs.LG 2019
Year: 2019

Autonomous driving requires operation in different behavioral modes ranging from lane following and intersection crossing to turning and stopping. However, most existing deep learning approaches to autonomous driving do not consider the behavioral mode in the training strategy. This paper describes a technique for learning multiple distinct behavioral modes in a single deep neural network through the use of multi-modal multi-task learning. We study the effectiveness of this approach, denoted MultiNet, using self-driving model cars for driving in unstructured environments such as sidewalks and unpaved roads. Using labeled data from over one hundred hours of driving our fleet of 1/10th scale model cars, we trained different neural networks to predict the steering angle and driving speed of the vehicle in different behavioral modes. We show that in each case, MultiNet networks outperform networks trained on individual modes while using a fraction of the total number of parameters.
Predicting Video Saliency with Object-to-Motion CNN and Two-layer Convolutional LSTM
Venue: arXiv cs.CV 2019
Year: 2019

Over the past few years, deep neural networks (DNNs) have exhibited great success in predicting the saliency of images. However, there are few works that apply DNNs to predict the saliency of generic videos. In this paper, we propose a novel DNN-based video saliency prediction method. Specifically, we establish a large-scale eye-tracking database of videos (LEDOV), which provides sufficient data to train the DNN models for predicting video saliency. Through the statistical analysis of our LEDOV database, we find that human attention is normally attracted by objects, particularly moving objects or the moving parts of objects. Accordingly, we propose an object-to-motion convolutional neural network (OM-CNN) to learn spatio-temporal features for predicting the intra-frame saliency via exploring the information of both objectness and object motion. We further find from our database that there exists a temporal correlation of human attention with a smooth saliency transition across video frames. Therefore, we develop a two-layer convolutional long short-term memory (2C-LSTM) network in our DNN-based method, using the extracted features of OM-CNN as the input. Consequently, the inter-frame saliency maps of videos can be generated, which consider the transition of attention across video frames. Finally, the experimental results show that our method advances the state-of-the-art in video saliency prediction.
Deep Reinforcement Learning for Event-Driven Multi-Agent Decision Processes
Venue: arXiv cs.AI 2019
Year: 2019

The incorporation of macro-actions (temporally extended actions) into multi-agent decision problems has the potential to address the curse of dimensionality associated with such decision problems. Since macro-actions last for stochastic durations, multiple agents executing decentralized policies in cooperative environments must act asynchronously. We present an algorithm that modifies generalized advantage estimation for temporally extended actions, allowing a state-of-the-art policy optimization algorithm to optimize policies in Dec-POMDPs in which agents act asynchronously. We show that our algorithm is capable of learning optimal policies in two cooperative domains, one involving real-time bus holding control and one involving wildfire fighting with unmanned aircraft. Our algorithm works by framing problems as "event-driven decision processes," which are scenarios in which the sequence and timing of actions and events are random and governed by an underlying stochastic process. In addition to optimizing policies with continuous state and action spaces, our algorithm also facilitates the use of event-driven simulators, which do not require time to be discretized into time-steps. We demonstrate the benefit of using event-driven simulation in the context of multiple agents taking asynchronous actions. We show that fixed time-step simulation risks obfuscating the sequence in which closely separated events occur, adversely affecting the policies learned. In addition, we show that arbitrarily shrinking the time-step scales poorly with the number of agents.
A Multimodal, Full-Surround Vehicular Testbed for Naturalistic Studies and Benchmarking: Design, Calibration and Deployment
Venue: arXiv cs.CV 2019
Year: 2019

Recent progress in autonomous and semi-autonomous driving has been made possible in part through an assortment of sensors that provide the intelligent agent with an enhanced perception of its surroundings. It has been clear for quite some while now that for intelligent vehicles to function effectively in all situations and conditions, a fusion of different sensor technologies is essential. Consequently, the availability of synchronized multi-sensory data streams are necessary to promote the development of fusion based algorithms for low, mid and high level semantic tasks. In this paper, we provide a comprehensive description of LISA-A: our heavily sensorized, full-surround testbed capable of providing high quality data from a slew of synchronized and calibrated sensors such as cameras, LIDARs, radars, and the IMU/GPS. The vehicle has recorded over 100 hours of real world data for a very diverse set of weather, traffic and daylight conditions. All captured data is accurately calibrated and synchronized using timestamps, and stored safely in high performance servers mounted inside the vehicle itself. Details on the testbed instrumentation, sensor layout, sensor outputs, calibration and synchronization are described in this paper.