OpenRaiser/Intern-Atlas huggingface dataset:
Online Multivariate Anomaly Detection and Localization for High-dimensional Settings
Venue: arXiv cs.LG 2020
Year: 2020

This paper considers the real-time detection of anomalies in high-dimensional systems. The goal is to detect anomalies quickly and accurately so that the appropriate countermeasures could be taken in time, before the system possibly gets harmed. We propose a sequential and multivariate anomaly detection method that scales well to high-dimensional datasets. The proposed method follows a nonparametric, i.e., data-driven, and semi-supervised approach, i.e., trains only on nominal data. Thus, it is applicable to a wide range of applications and data types. Thanks to its multivariate nature, it can quickly and accurately detect challenging anomalies, such as changes in the correlation structure and stealth low-rate cyberattacks. Its asymptotic optimality and computational complexity are comprehensively analyzed. In conjunction with the detection method, an effective technique for localizing the anomalous data dimensions is also proposed. We further extend the proposed detection and localization methods to a supervised setup where an additional anomaly dataset is available, and combine the proposed semi-supervised and supervised algorithms to obtain an online learning algorithm under the semi-supervised framework. The practical use of proposed algorithms are demonstrated in DDoS attack mitigation, and their performances are evaluated using a real IoT-botnet dataset and simulations.
Optimal Pricing for Job Offloading in the MEC System with Two Priority Classes
Venue: arXiv cs.IT 2020
Year: 2020

Multi-Access edge computing (MEC) is an emerging paradigm where users offload computationally intensive jobs to the Access Point (AP). Given that the AP's resources are shared by selfish users, pricing is a useful tool for incentivising users to internalize the negative externality of delay they cause to other users. Nevertheless, different users have different negative valuations towards delay as some are more delay sensitive. To serve heterogeneous users, we propose a priority pricing scheme where users can get served first for a higher price. Our goal is to find the prices such that in decision making, users will choose the class and the offloading frequency that jointly maximize social welfare. With the assumption that the AP knows users' profit functions, we derive in semi-closed form the optimal prices. However in practice, the reporting of users's profit information incurs a large signalling overhead. Besides, in reality users might falsely report their private profit information. To overcome this, we further propose a learning-based pricing mechanism where no knowledge of individual user profit functions is required. At equilibrium, the optimal prices and average edge delays are learnt, and users have chosen the correct priority class and offload at the socially optimal frequency.
Neural Graph Collaborative Filtering
Venue: arXiv cs.IR 2020
Year: 2020

Learning vector representations (aka. embeddings) of users and items lies at the core of modern recommender systems. Ranging from early matrix factorization to recently emerged deep learning based methods, existing efforts typically obtain a user's (or an item's) embedding by mapping from pre-existing features that describe the user (or the item), such as ID and attributes. We argue that an inherent drawback of such methods is that, the collaborative signal, which is latent in user-item interactions, is not encoded in the embedding process. As such, the resultant embeddings may not be sufficient to capture the collaborative filtering effect. In this work, we propose to integrate the user-item interactions -- more specifically the bipartite graph structure -- into the embedding process. We develop a new recommendation framework Neural Graph Collaborative Filtering (NGCF), which exploits the user-item graph structure by propagating embeddings on it. This leads to the expressive modeling of high-order connectivity in user-item graph, effectively injecting the collaborative signal into the embedding process in an explicit manner. We conduct extensive experiments on three public benchmarks, demonstrating significant improvements over several state-of-the-art models like HOP-Rec and Collaborative Memory Network. Further analysis verifies the importance of embedding propagation for learning better user and item representations, justifying the rationality and effectiveness of NGCF. Codes are available at https://github.com/xiangwang1223/neural_graph_collaborative_filtering.
Locally Differentially Private Frequency Estimation with Consistency
Venue: arXiv cs.CR 2020
Year: 2020

Local Differential Privacy (LDP) protects user privacy from the data collector. LDP protocols have been increasingly deployed in the industry. A basic building block is frequency oracle (FO) protocols, which estimate frequencies of values. While several FO protocols have been proposed, the design goal does not lead to optimal results for answering many queries. In this paper, we show that adding post-processing steps to FO protocols by exploiting the knowledge that all individual frequencies should be non-negative and they sum up to one can lead to significantly better accuracy for a wide range of tasks, including frequencies of individual values, frequencies of the most frequent values, and frequencies of subsets of values. We consider 10 different methods that exploit this knowledge differently. We establish theoretical relationships between some of them and conducted extensive experimental evaluations to understand which methods should be used for different query tasks.
Compression with Flows via Local Bits-Back Coding
Venue: arXiv cs.LG 2020
Year: 2020

Likelihood-based generative models are the backbones of lossless compression due to the guaranteed existence of codes with lengths close to negative log likelihood. However, there is no guaranteed existence of computationally efficient codes that achieve these lengths, and coding algorithms must be hand-tailored to specific types of generative models to ensure computational efficiency. Such coding algorithms are known for autoregressive models and variational autoencoders, but not for general types of flow models. To fill in this gap, we introduce local bits-back coding, a new compression technique for flow models. We present efficient algorithms that instantiate our technique for many popular types of flows, and we demonstrate that our algorithms closely achieve theoretical codelengths for state-of-the-art flow models on high-dimensional data.
Silent MST approximation for tiny memory
Venue: arXiv cs.DC 2020
Year: 2020

In this paper we show that approximation can help reduce the space used for self-stabilization. In the classic \emph{state model}, where the nodes of a network communicate by reading the states of their neighbors, an important measure of efficiency is the space: the number of bits used at each node to encode the state. In this model, a classic requirement is that the algorithm has to be \emph{silent}, that is, after stabilization the states should not change anymore. We design a silent self-stabilizing algorithm for the problem of minimum spanning tree, that has a trade-off between the quality of the solution and the space needed to compute it.
A Standalone FPGA-based Miner for Lyra2REv2 Cryptocurrencies
Venue: arXiv cs.CR 2020
Year: 2020

Lyra2REv2 is a hashing algorithm that consists of a chain of individual hashing algorithms, and it is used as a proof-of-work function in several cryptocurrencies. The most crucial and exotic hashing algorithm in the Lyra2REv2 chain is a specific instance of the general Lyra2 algorithm. This work presents the first hardware implementation of the specific instance of Lyra2 that is used in Lyra2REv2. Several properties of the aforementioned algorithm are exploited in order to optimize the design. In addition, an FPGA-based hardware implementation of a standalone miner for Lyra2REv2 on a Xilinx Multi-Processor System on Chip is presented. The proposed Lyra2REv2 miner is shown to be significantly more energy efficient than both a GPU and a commercially available FPGA-based miner. Finally, we also explain how the simplified Lyra2 and Lyra2REv2 architectures can be modified with minimal effort to also support the recent Lyra2REv3 chained hashing algorithm.
IPAW 2020 Preprint: Efficient Computation of Provenance for Query Result Exploration
Venue: arXiv cs.DB 2020
Year: 2020

Users typically interact with a database by asking queries and examining the results. We refer to the user examining the query results and asking follow-up questions as query result exploration. Our work builds on two decades of provenance research useful for query result exploration. Three approaches for computing provenance have been described in the literature: lazy, eager, and hybrid. We investigate lazy and eager approaches that utilize constraints that we have identified in the context of query result exploration, as well as novel hybrid approaches. For the TPC-H benchmark, these constraints are applicable to 19 out of the 22 queries, and result in a better performance for all queries that have a join. Furthermore, the performance benefits from our approaches are significant, sometimes several orders of magnitude.
IN2LAAMA: INertial Lidar Localisation Autocalibration And MApping
Venue: arXiv cs.RO 2020
Year: 2020

In this paper, we present INertial Lidar Localisation Autocalibration And MApping (IN2LAAMA): an offline probabilistic framework for localisation, mapping, and extrinsic calibration based on a 3D-lidar and a 6-DoF-IMU. Most of today's lidars collect geometric information about the surrounding environment by sweeping lasers across their field of view. Consequently, 3D-points in one lidar scan are acquired at different timestamps. If the sensor trajectory is not accurately known, the scans are affected by the phenomenon known as motion distortion. The proposed method leverages preintegration with a continuous representation of the inertial measurements to characterise the system's motion at any point in time. It enables precise correction of the motion distortion without relying on any explicit motion model. The system's pose, velocity, biases, and time-shift are estimated via a full batch optimisation that includes automatically generated loop-closure constraints. The autocalibration and the registration of lidar data rely on planar and edge features matched across pairs of scans. The performance of the framework is validated through simulated and real-data experiments.
Workflow Design Analysis for High Resolution Satellite Image Analysis
Venue: arXiv cs.DC 2020
Year: 2020

Ecological sciences are using imagery from a variety of sources to monitor and survey populations and ecosystems. Very High Resolution (VHR) satellite imagery provide an effective dataset for large scale surveys. Convolutional Neural Networks have successfully been employed to analyze such imagery and detect large animals. As the datasets increase in volume, O(TB), and number of images, O(1k), utilizing High Performance Computing (HPC) resources becomes necessary. In this paper, we investigate a task-parallel data-driven workflows design to support imagery analysis pipelines with heterogeneous tasks on HPC. We analyze the capabilities of each design when processing a dataset of 3,000 VHR satellite images for a total of 4~TB. We experimentally model the execution time of the tasks of the image processing pipeline. We perform experiments to characterize the resource utilization, total time to completion, and overheads of each design. Based on the model, overhead and utilization analysis, we show which design approach to is best suited in scientific pipelines with similar characteristics.
Efficient Batch Black-box Optimization with Deterministic Regret Bounds
Venue: arXiv cs.LG 2020
Year: 2020

In this work, we investigate black-box optimization from the perspective of frequentist kernel methods. We propose a novel batch optimization algorithm, which jointly maximizes the acquisition function and select points from a whole batch in a holistic way. Theoretically, we derive regret bounds for both the noise-free and perturbation settings irrespective of the choice of kernel. Moreover, we analyze the property of the adversarial regret that is required by a robust initialization for Bayesian Optimization (BO). We prove that the adversarial regret bounds decrease with the decrease of covering radius, which provides a criterion for generating a point set to minimize the bound. We then propose fast searching algorithms to generate a point set with a small covering radius for the robust initialization. Experimental results on both synthetic benchmark problems and real-world problems show the effectiveness of the proposed algorithms.
Signature codes for weighted binary adder channel and multimedia fingerprinting
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we study the signature codes for weighted binary adder channel (WbAC) and collusion-resistant multimedia fingerprinting. Let $A(n,t)$ denote the maximum cardinality of a $t$-signature code of length $n$, and $A(n,w,t)$ denote the maximum cardinality of a $t$-signature code of length $n$ and constant weight $w$. First, we derive asymptotic and general upper bounds of $A(n,t)$ by relating signature codes to $B_t$ codes and bipartite graphs with large girth respectively, and also show the upper bounds are tight for certain cases. Second, we determine the exact values of $A(n,2,2)$ and $A(n,3,2)$ for infinitely many $n$ by connecting signature codes with $C_4$-free graphs and union-free families, respectively. Third, we provide two explicit constructions for $t$-signature codes which have efficient decoding algorithms and applications to two-level signature codes. Furthermore, we show from the geometric viewpoint that there does not exist any binary code with complete traceability for noisy WbAC and multimedia fingerprinting. A new type of signature codes with a weaker requirement than complete traceability is introduced for the noisy scenario.
Fully Hyperbolic Convolutional Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

Convolutional Neural Networks (CNN) have recently seen tremendous success in various computer vision tasks. However, their application to problems with high dimensional input and output, such as high-resolution image and video segmentation or 3D medical imaging, has been limited by various factors. Primarily, in the training stage, it is necessary to store network activations for back propagation. In these settings, the memory requirements associated with storing activations can exceed what is feasible with current hardware, especially for problems in 3D. Motivated by the propagation of signals over physical networks, that are governed by the hyperbolic Telegraph equation, in this work we introduce a fully conservative hyperbolic network for problems with high dimensional input and output. We introduce a coarsening operation that allows completely reversible CNNs by using a learnable Discrete Wavelet Transform and its inverse to both coarsen and interpolate the network state and change the number of channels. We show that fully reversible networks are able to achieve results comparable to the state of the art in 4D time-lapse hyper spectral image segmentation and full 3D video segmentation, with a much lower memory footprint that is a constant independent of the network depth. We also extend the use of such networks to Variational Auto Encoders with high resolution input and output.
An Exploratory Study on Machine Learning Model Stores
Venue: arXiv cs.SE 2020
Year: 2020

Recent advances in Artificial Intelligence, especially in Machine Learning (ML), have brought applications previously considered as science fiction (e.g., virtual personal assistants and autonomous cars) into the reach of millions of everyday users. Since modern ML technologies like deep learning require considerable technical expertise and resource to build custom models, reusing existing models trained by experts has become essential. This is why in the past year model stores have been introduced, which, similar to mobile app stores, offer organizations and developers access to pre-trained models and/or their code to train, evaluate, and predict samples. This paper conducts an exploratory study on three popular model stores (AWS marketplace, Wolfram neural net repository, and ModelDepot) that compares the information elements (features and policies) provided by model stores to those used by the two popular mobile app stores (Google Play and Apple's App Store). We have found that the model information elements vary among the different model stores, with 65% elements shared by all three studied stores. Model stores share five information elements with mobile app stores, while eight elements are unique to model stores and four elements unique to app stores. Only few models were available on multiple model stores. Our findings allow to better understand the differences between ML models and "regular" source code components or applications, and provide inspiration to identify software engineering practices (e.g., in requirements and delivery) specific to ML applications.
Safe Reinforcement Learning with Nonlinear Dynamics via Model Predictive Shielding
Venue: arXiv cs.LG 2020
Year: 2020

Reinforcement learning is a promising approach to synthesizing policies for challenging robotics tasks. A key problem is how to ensure safety of the learned policy---e.g., that a walking robot does not fall over or that an autonomous car does not run into an obstacle. We focus on the setting where the dynamics are known, and the goal is to ensure that a policy trained in simulation satisfies a given safety constraint. We propose an approach, called model predictive shielding (MPS), that switches on-the-fly between a learned policy and a backup policy to ensure safety. We prove that our approach guarantees safety, and empirically evaluate it on the cart-pole.
Let's Agree to Agree: Neural Networks Share Classification Order on Real Datasets
Venue: arXiv cs.LG 2020
Year: 2020

We report a series of robust empirical observations, demonstrating that deep Neural Networks learn the examples in both the training and test sets in a similar order. This phenomenon is observed in all the commonly used benchmarks we evaluated, including many image classification benchmarks, and one text classification benchmark. While this phenomenon is strongest for models of the same architecture, it also crosses architectural boundaries -- models of different architectures start by learning the same examples, after which the more powerful model may continue to learn additional examples. We further show that this pattern of results reflects the interplay between the way neural networks learn benchmark datasets. Thus, when fixing the architecture, we show synthetic datasets where this pattern ceases to exist. When fixing the dataset, we show that other learning paradigms may learn the data in a different order. We hypothesize that our results reflect how neural networks discover structure in natural datasets.
Applying Abstract Argumentation Theory to Cooperative Game Theory
Venue: arXiv cs.GT 2020
Year: 2020

We apply ideas from abstract argumentation theory to study cooperative game theory. Building on Dung's results in his seminal paper, we further the correspondence between Dung's four argumentation semantics and solution concepts in cooperative game theory by showing that complete extensions (the grounded extension) correspond to Roth's subsolutions (respectively, the supercore). We then investigate the relationship between well-founded argumentation frameworks and convex games, where in each case the semantics (respectively, solution concepts) coincide; we prove that three-player convex games do not in general have well-founded argumentation frameworks.
Multi-User Detection Based on Expectation Propagation for the Non-Coherent SIMO Multiple Access Channel
Venue: arXiv cs.IT 2020
Year: 2020

We consider the non-coherent single-input multiple-output (SIMO) multiple access channel with general signaling under spatially correlated Rayleigh block fading. We propose a novel soft-output multi-user detector that computes an approximate marginal posterior of each transmitted signal using only the knowledge about the channel distribution. Our detector is based on expectation propagation (EP) approximate inference and has polynomial complexity in the number of users, the number of receive antennas, and channel coherence time. We also propose two simplifications of this detector with reduced complexity. With Grassmannian signaling, the proposed detectors outperform a state-of-the-art non-coherent detector with projection-based interference mitigation. With pilot-assisted signaling, the EP detector outperforms, in terms of symbol error rate, some conventional coherent pilot-based detectors, including a sphere decoder and a joint channel estimation-data detection scheme. Our EP-based detectors produce accurate approximates of the true posterior leading to high achievable sum-rates. The gains of these detectors are further observed in terms of the bit error rate when using their soft outputs for a turbo channel decoder.
Underactuation Design for Tendon-driven Hands via Optimization of Mechanically Realizable Manifolds in Posture and Torque Spaces
Venue: arXiv cs.RO 2020
Year: 2020

Grasp synergies represent a useful idea to reduce grasping complexity without compromising versatility. Synergies describe coordination patterns between joints, either in terms of position (joint angles) or effort (joint torques). In both of these cases, a grasp synergy can be represented as a low-dimensional manifold lying in the high-dimensional joint posture or torque space. In this paper, we use the term \textit{Mechanically Realizable Manifolds} to refer to the subset of such manifolds (in either posture or torque space) that can be achieved via mechanical coupling of the joints in underactuated hands. We present a method to optimize the design parameters of an underactuated hand in order to shape the Mechanically Realizable Manifolds to fit a pre-defined set of desired grasps. Our method guarantees that the resulting synergies can be physically implemented in an underactuated hand, and will enable the resulting hand to both reach the desired grasp postures and achieve quasistatic equilibrium while loading the grasps. We demonstrate this method on three concrete design examples motivated by a real use case, and evaluate and compare their performance in practice.