OpenRaiser/Intern-Atlas huggingface dataset:
Data-Driven MPC for Quadrotors
Venue: arXiv cs.RO 2021
Year: 2021

Aerodynamic forces render accurate high-speed trajectory tracking with quadrotors extremely challenging. These complex aerodynamic effects become a significant disturbance at high speeds, introducing large positional tracking errors, and are extremely difficult to model. To fly at high speeds, feedback control must be able to account for these aerodynamic effects in real-time. This necessitates a modelling procedure that is both accurate and efficient to evaluate. Therefore, we present an approach to model aerodynamic effects using Gaussian Processes, which we incorporate into a Model Predictive Controller to achieve efficient and precise real-time feedback control, leading to up to 70% reduction in trajectory tracking error at high speeds. We verify our method by extensive comparison to a state-of-the-art linear drag model in synthetic and real-world experiments at speeds of up to 14m/s and accelerations beyond 4g.
Defense Against Reward Poisoning Attacks in Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

We study defense strategies against reward poisoning attacks in reinforcement learning. As a threat model, we consider attacks that minimally alter rewards to make the attacker's target policy uniquely optimal under the poisoned rewards, with the optimality gap specified by an attack parameter. Our goal is to design agents that are robust against such attacks in terms of the worst-case utility w.r.t. the true, unpoisoned, rewards while computing their policies under the poisoned rewards. We propose an optimization framework for deriving optimal defense policies, both when the attack parameter is known and unknown. Moreover, we show that defense policies that are solutions to the proposed optimization problems have provable performance guarantees. In particular, we provide the following bounds with respect to the true, unpoisoned, rewards: a) lower bounds on the expected return of the defense policies, and b) upper bounds on how suboptimal these defense policies are compared to the attacker's target policy. We conclude the paper by illustrating the intuitions behind our formal results, and showing that the derived bounds are non-trivial.
Multi-level Weighted Additive Spanners
Venue: arXiv cs.DM 2021
Year: 2021

Given a graph $G = (V,E)$, a subgraph $H$ is an \emph{additive $+β$ spanner} if $\dist_H(u,v) \le \dist_G(u,v) + β$ for all $u, v \in V$. A \emph{pairwise spanner} is a spanner for which the above inequality only must hold for specific pairs $P \subseteq V \times V$ given on input, and when the pairs have the structure $P = S \times S$ for some subset $S \subseteq V$, it is specifically called a \emph{subsetwise spanner}. Spanners in unweighted graphs have been studied extensively in the literature, but have only recently been generalized to weighted graphs. In this paper, we consider a multi-level version of the subsetwise spanner in weighted graphs, where the vertices in $S$ possess varying level, priority, or quality of service (QoS) requirements, and the goal is to compute a nested sequence of spanners with the minimum number of total edges. We first generalize the $+2$ subsetwise spanner of [Pettie 2008, Cygan et al., 2013] to the weighted setting. We experimentally measure the performance of this and several other algorithms for weighted additive spanners, both in terms of runtime and sparsity of output spanner, when applied at each level of the multi-level problem. Spanner sparsity is compared to the sparsest possible spanner satisfying the given error budget, obtained using an integer programming formulation of the problem. We run our experiments with respect to input graphs generated by several different random graph generators: Erdős--Rényi, Watts--Strogatz, Barabási--Albert, and random geometric models. By analyzing our experimental results we developed a new technique of changing an initialization parameter value that provides better performance in practice.
An electric vehicle charging station access equilibrium model with M/D/C queueing
Venue: arXiv cs.CY 2021
Year: 2021

Despite the dependency of electric vehicle (EV) fleets on charging station availability, charging infrastructure remains limited in many cities. Three contributions are made. First, we propose an EV-to-charging station user equilibrium (UE) assignment model with a M/D/C queue approximation as a nondifferentiable nonlinear program. Second, to address the non-differentiability of the queue delay function, we propose an original solution algorithm based on the derivative-free Method of Successive Averages. Computational tests with a toy network show that the model converges to a UE. A working code in Python is provided free on Github with detailed test cases. Third, the model is applied to the large-scale case study of New York City Department of Citywide Administrative Services (NYC DCAS) fleet and EV charging station configuration as of July 8, 2020, which includes unique, real data for 563 Level 2 chargers and 4 Direct Current Fast Chargers (DCFCs) and 1484 EVs distributed over 512 Traffic Analysis Zones. The arrival rates of the assignment model are calibrated in the base scenario to fit an observed average utilization ratio of 7.6% in NYC. The model is then applied to compare charging station investment policies of DCFCs to Level 2 charging stations based on two alternative criteria. Results suggest a policy based on selecting locations with high utilization ratio instead of with high queue delay.
Approximation Algorithms for Generalized Multidimensional Knapsack
Venue: arXiv cs.DS 2021
Year: 2021

We study a generalization of the knapsack problem with geometric and vector constraints. The input is a set of rectangular items, each with an associated profit and $d$ nonnegative weights ($d$-dimensional vector), and a square knapsack. The goal is to find a non-overlapping axis-parallel packing of a subset of items into the given knapsack such that the vector constraints are not violated, i.e., the sum of weights of all the packed items in any of the $d$ dimensions does not exceed one. We consider two variants of the problem: $(i)$ the items are not allowed to be rotated, $(ii)$ items can be rotated by 90 degrees. We give a $(2+ε)$-approximation algorithm for this problem (both versions). In the process, we also study a variant of the maximum generalized assignment problem (Max-GAP), called Vector-Max-GAP, and design a PTAS for it.
Searching for Designs in-between
Venue: arXiv cs.NE 2021
Year: 2021

The use of evolutionary methods in design and art is increasing in diversity and popularity. Approaches to using these methods for creative production typically focus either on optimisation or exploration. In this paper we introduce an evolutionary system for design that combines these two approaches, enabling users to explore landscapes of design alternatives using design-oriented measures of fitness, along with their own aesthetic preferences. We test our methods using a biologically-inspired generative system capable of producing 3D objects that can be exported directly as 3D printing toolpath instructions. For the search stage of our system we combine the use of the CMA-ES algorithm for optimisation and linear interpolation between generated objects for feature exploration. We investigate the system`s capabilities by evolving highly fit artefacts and then combining them with aesthetically interesting ones.
ABOShips -- An Inshore and Offshore Maritime Vessel Detection Dataset with Precise Annotations
Venue: arXiv cs.CV 2021
Year: 2021

Availability of domain-specific datasets is an essential problem in object detection. Maritime vessel detection of inshore and offshore datasets is no exception, there is a limited number of studies addressing this need. For that reason, we collected a dataset of images of maritime vessels taking into account different factors: background variation, atmospheric conditions, illumination, visible proportion, occlusion and scale variation. Vessel instances (including 9 types of vessels), seamarks and miscellaneous floaters were precisely annotated: we employed a first round of labelling and subsequently, we used the CSRT [1] tracker to trace inconsistencies and relabel inadequate label instances. Moreover, we evaluated the the out-of-the-box performance of four prevalent object detection algorithms (Faster R-CNN [2], R-FCN [3], SSD [4] and EfficientDet [5]). The algorithms were previously trained on the Microsoft COCO dataset. We compare their accuracy based on feature extractor and object size. Our experiments show that Faster R-CNN with Inception-Resnet v2 outperforms the other algorithms, except in the large object category where EfficientDet surpasses the latter.
Talking After Lights Out: An Ad Hoc Network for Electric Grid Recovery
Venue: arXiv cs.NI 2021
Year: 2021

When the electric grid in a region suffers a major outage, e.g., after a catastrophic cyber attack, a "black start" may be required, where the grid is slowly restarted, carefully and incrementally adding generating capacity and demand. To ensure safe and effective black start, the grid control center has to be able to communicate with field personnel and with supervisory control and data acquisition (SCADA) systems. Voice and text communication are particularly critical. As part of the Defense Advanced Research Projects Agency (DARPA) Rapid Attack Detection, Isolation, and Characterization Systems (RADICS) program, we designed, tested and evaluated a self-configuring mesh network architecture and prototype called the Phoenix Secure Emergency Network (PhoenixSEN). PhoenixSEN is designed as a drop-in replacement for primary communication networks, combines existing and new technologies, can work with a variety of link-layer protocols, emphasizes manageability and auto-configuration, and provides a core set of services and applications for coordination of people and devices including voice, text, and SCADA communication. The PhoenixSEN prototype was evaluated in the field through a series of DARPA-led exercises. The same system is also likely to support coordination of recovery efforts after large-scale natural disasters.
OpinionRank: Extracting Ground Truth Labels from Unreliable Expert Opinions with Graph-Based Spectral Ranking
Venue: arXiv cs.LG 2021
Year: 2021

As larger and more comprehensive datasets become standard in contemporary machine learning, it becomes increasingly more difficult to obtain reliable, trustworthy label information with which to train sophisticated models. To address this problem, crowdsourcing has emerged as a popular, inexpensive, and efficient data mining solution for performing distributed label collection. However, crowdsourced annotations are inherently untrustworthy, as the labels are provided by anonymous volunteers who may have varying, unreliable expertise. Worse yet, some participants on commonly used platforms such as Amazon Mechanical Turk may be adversarial, and provide intentionally incorrect label information without the end user's knowledge. We discuss three conventional models of the label generation process, describing their parameterizations and the model-based approaches used to solve them. We then propose OpinionRank, a model-free, interpretable, graph-based spectral algorithm for integrating crowdsourced annotations into reliable labels for performing supervised or semi-supervised learning. Our experiments show that OpinionRank performs favorably when compared against more highly parameterized algorithms. We also show that OpinionRank is scalable to very large datasets and numbers of label sources, and requires considerably fewer computational resources than previous approaches.
Toward Improving Coherence and Diversity of Slogan Generation
Venue: arXiv cs.CL 2021
Year: 2021

Previous work in slogan generation focused on utilising slogan skeletons mined from existing slogans. While some generated slogans can be catchy, they are often not coherent with the company's focus or style across their marketing communications because the skeletons are mined from other companies' slogans. We propose a sequence-to-sequence (seq2seq) transformer model to generate slogans from a brief company description. A naive seq2seq model fine-tuned for slogan generation is prone to introducing false information. We use company name delexicalisation and entity masking to alleviate this problem and improve the generated slogans' quality and truthfulness. Furthermore, we apply conditional training based on the first words' POS tag to generate syntactically diverse slogans. Our best model achieved a ROUGE-1/-2/-L F1 score of 35.58/18.47/33.32. Besides, automatic and human evaluations indicate that our method generates significantly more factual, diverse and catchy slogans than strong LSTM and transformer seq2seq baselines.
Adversarially robust deepfake media detection using fused convolutional neural network predictions
Venue: arXiv cs.CV 2021
Year: 2021

Deepfakes are synthetically generated images, videos or audios, which fraudsters use to manipulate legitimate information. Current deepfake detection systems struggle against unseen data. To address this, we employ three different deep Convolutional Neural Network (CNN) models, (1) VGG16, (2) InceptionV3, and (3) XceptionNet to classify fake and real images extracted from videos. We also constructed a fusion of the deep CNN models to improve the robustness and generalisation capability. The proposed technique outperforms state-of-the-art models with 96.5% accuracy, when tested on publicly available DeepFake Detection Challenge (DFDC) test data, comprising of 400 videos. The fusion model achieves 99% accuracy on lower quality DeepFake-TIMIT dataset videos and 91.88% on higher quality DeepFake-TIMIT videos. In addition to this, we prove that prediction fusion is more robust against adversarial attacks. If one model is compromised by an adversarial attack, the prediction fusion does not let it affect the overall classification.
Demarcating Endogenous and Exogenous Opinion Dynamics: An Experimental Design Approach
Venue: arXiv cs.SI 2021
Year: 2021

The networked opinion diffusion in online social networks (OSN) is often governed by the two genres of opinions - endogenous opinions that are driven by the influence of social contacts among users, and exogenous opinions which are formed by external effects like news, feeds etc. Accurate demarcation of endogenous and exogenous messages offers an important cue to opinion modeling, thereby enhancing its predictive performance. In this paper, we design a suite of unsupervised classification methods based on experimental design approaches, in which, we aim to select the subsets of events which minimize different measures of mean estimation error. In more detail, we first show that these subset selection tasks are NP-Hard. Then we show that the associated objective functions are weakly submodular, which allows us to cast efficient approximation algorithms with guarantees. Finally, we validate the efficacy of our proposal on various real-world datasets crawled from Twitter as well as diverse synthetic datasets. Our experiments range from validating prediction performance on unsanitized and sanitized events to checking the effect of selecting optimal subsets of various sizes. Through various experiments, we have found that our method offers a significant improvement in accuracy in terms of opinion forecasting, against several competitors.
Tackling Virtual and Real Concept Drifts: An Adaptive Gaussian Mixture Model
Venue: arXiv cs.LG 2021
Year: 2021

Real-world applications have been dealing with large amounts of data that arrive over time and generally present changes in their underlying joint probability distribution, i.e., concept drift. Concept drift can be subdivided into two types: virtual drift, which affects the unconditional probability distribution p(x), and real drift, which affects the conditional probability distribution p(y|x). Existing works focuses on real drift. However, strategies to cope with real drift may not be the best suited for dealing with virtual drift, since the real class boundaries remain unchanged. We provide the first in depth analysis of the differences between the impact of virtual and real drifts on classifiers' suitability. We propose an approach to handle both drifts called On-line Gaussian Mixture Model With Noise Filter For Handling Virtual and Real Concept Drifts (OGMMF-VRD). Experiments with 7 synthetic and 3 real-world datasets show that OGMMF-VRD obtained the best results in terms of average accuracy, G-mean and runtime compared to existing approaches. Moreover, its accuracy over time suffered less performance degradation in the presence of drifts.
A Survey on Synchronous Augmented, Virtual and Mixed Reality Remote Collaboration Systems
Venue: arXiv cs.HC 2021
Year: 2021

Remote collaboration systems have become increasingly important in today's society, especially during times where physical distancing is advised. Industry, research and individuals face the challenging task of collaborating and networking over long distances. While video and teleconferencing are already widespread, collaboration systems in augmented, virtual, and mixed reality are still a niche technology. We provide an overview of recent developments of synchronous remote collaboration systems and create a taxonomy by dividing them into three main components that form such systems: Environment, Avatars, and Interaction. A thorough overview of existing systems is given, categorising their main contributions in order to help researchers working in different fields by providing concise information about specific topics such as avatars, virtual environment, visualisation styles and interaction. The focus of this work is clearly on synchronised collaboration from a distance. A total of 82 unique systems for remote collaboration are discussed, including more than 100 publications and 25 commercial systems.
Large-Scale Training System for 100-Million Classification at Alibaba
Venue: arXiv cs.LG 2021
Year: 2021

In the last decades, extreme classification has become an essential topic for deep learning. It has achieved great success in many areas, especially in computer vision and natural language processing (NLP). However, it is very challenging to train a deep model with millions of classes due to the memory and computation explosion in the last output layer. In this paper, we propose a large-scale training system to address these challenges. First, we build a hybrid parallel training framework to make the training process feasible. Second, we propose a novel softmax variation named KNN softmax, which reduces both the GPU memory consumption and computation costs and improves the throughput of training. Then, to eliminate the communication overhead, we propose a new overlapping pipeline and a gradient sparsification method. Furthermore, we design a fast continuous convergence strategy to reduce total training iterations by adaptively adjusting learning rate and updating model parameters. With the help of all the proposed methods, we gain 3.9$\times$ throughput of our training system and reduce almost 60\% of training iterations. The experimental results show that using an in-house 256 GPUs cluster, we could train a classifier of 100 million classes on Alibaba Retail Product Dataset in about five days while achieving a comparable accuracy with the naive softmax training process.
Search Planning of a UAV/UGV Team with Localization Uncertainty in a Subterranean Environment
Venue: arXiv cs.RO 2021
Year: 2021

We present a waypoint planning algorithm for an unmanned aerial vehicle (UAV) that is teamed with an unmanned ground vehicle (UGV) for the task of search and rescue in a subterranean environment. The UAV and UGV are teamed such that the localization of the UAV is conducted on the UGV via the multi-sensor fusion of a fish-eye camera, 3D LIDAR, ranging radio, and a laser altimeter. Likewise, the trajectory planning of the UAV is conducted on the UGV, which is assumed to have a 3D map of the environment (e.g., from Simultaneous Localization and Mapping). The goal of the planning algorithm is to satisfy the mission's exploration criteria while reducing the localization error of the UAV by evaluating the belief space for potential exploration routes. The presented algorithm is evaluated in a relevant simulation environment where the planning algorithm is shown to be effective at reducing the localization errors of the UAV.
Deep Photo Scan: Semi-Supervised Learning for dealing with the real-world degradation in Smartphone Photo Scanning
Venue: arXiv cs.CV 2021
Year: 2021

Physical photographs now can be conveniently scanned by smartphones and stored forever as a digital version, yet the scanned photos are not restored well. One solution is to train a supervised deep neural network on many digital photos and the corresponding scanned photos. However, it requires a high labor cost, leading to limited training data. Previous works create training pairs by simulating degradation using image processing techniques. Their synthetic images are formed with perfectly scanned photos in latent space. Even so, the real-world degradation in smartphone photo scanning remains unsolved since it is more complicated due to lens defocus, lighting conditions, losing details via printing. Besides, locally structural misalignment still occurs in data due to distorted shapes captured in a 3-D world, reducing restoration performance and the reliability of the quantitative evaluation. To solve these problems, we propose a semi-supervised Deep Photo Scan (DPScan). First, we present a way of producing real-world degradation and provide the DIV2K-SCAN dataset for smartphone-scanned photo restoration. Also, Local Alignment is proposed to reduce the minor misalignment remaining in data. Second, we simulate many different variants of the real-world degradation using low-level image transformation to gain a generalization in smartphone-scanned image properties, then train a degradation network to generalize all styles of degradation and provide pseudo-scanned photos for unscanned images as if they were scanned by a smartphone. Finally, we propose a Semi-Supervised Learning that allows our restoration network to be trained on both scanned and unscanned images, diversifying training image content. As a result, the proposed DPScan quantitatively and qualitatively outperforms its baseline architecture, state-of-the-art academic research, and industrial products in smartphone photo scanning.
Sample Efficient Learning of Image-Based Diagnostic Classifiers Using Probabilistic Labels
Venue: arXiv cs.CV 2021
Year: 2021

Deep learning approaches often require huge datasets to achieve good generalization. This complicates its use in tasks like image-based medical diagnosis, where the small training datasets are usually insufficient to learn appropriate data representations. For such sensitive tasks it is also important to provide the confidence in the predictions. Here, we propose a way to learn and use probabilistic labels to train accurate and calibrated deep networks from relatively small datasets. We observe gains of up to 22% in the accuracy of models trained with these labels, as compared with traditional approaches, in three classification tasks: diagnosis of hip dysplasia, fatty liver, and glaucoma. The outputs of models trained with probabilistic labels are calibrated, allowing the interpretation of its predictions as proper probabilities. We anticipate this approach will apply to other tasks where few training instances are available and expert knowledge can be encoded as probabilities.