OpenRaiser/Intern-Atlas huggingface dataset:
On Performance Estimation in Automatic Algorithm Configuration
Venue: arXiv cs.LG 2019
Year: 2019

Over the last decade, research on automated parameter tuning, often referred to as automatic algorithm configuration (AAC), has made significant progress. Although the usefulness of such tools has been widely recognized in real world applications, the theoretical foundations of AAC are still very weak. This paper addresses this gap by studying the performance estimation problem in AAC. More specifically, this paper first proves the universal best performance estimator in a practical setting, and then establishes theoretical bounds on the estimation error, i.e., the difference between the training performance and the true performance for a parameter configuration, considering finite and infinite configuration spaces respectively. These findings were verified in extensive experiments conducted on four algorithm configuration scenarios involving different problem domains. Moreover, insights for enhancing existing AAC methods are also identified.
Computation Offloading in the Untrusted MEC-aided Mobile Blockchain IoT System
Venue: arXiv cs.IT 2019
Year: 2019

Deploying mobile edge computing (MEC) server in the mobile blockchain-enabled Internet of things (IoT) system is a promising approach to improve the system performance, however, it imposes a significant challenge on the trust of MEC server. To address this problem, we first propose an untrusted MEC proof of work scheme in mobile blockchain network where plenty of nonce hash computing demands can be offloaded to MEC server. Then, we design a nonce ordering algorithm for this scheme to provide fairer computing resource allocation for all mobile IoT devices/users. Specifically, we formulate the user's nonce selection strategy as a non-cooperative game, where the utilities of individual user are maximized in the untrusted MEC-aided mobile blockchain network. We also prove the existence of Nash equilibrium and analyze that the cooperation behavior is unsuitable for the blockchain-enabled IoT devices by using the repeated game. Finally, we design the blockchain's difficulty adjustment mechanism to ensure stable block times during a long period of time.
Bidding in Smart Grid PDAs: Theory, Analysis and Strategy (Extended Version)
Venue: arXiv cs.GT 2019
Year: 2019

Periodic Double Auctions (PDAs) are commonly used in the real world for trading, e.g. in stock markets to determine stock opening prices, and energy markets to trade energy in order to balance net demand in smart grids, involving trillions of dollars in the process. A bidder, participating in such PDAs, has to plan for bids in the current auction as well as for the future auctions, which highlights the necessity of good bidding strategies. In this paper, we perform an equilibrium analysis of single unit single-shot double auctions with a certain clearing price and payment rule, which we refer to as ACPR, and find it intractable to analyze as number of participating agents increase. We further derive the best response for a bidder with complete information in a single-shot double auction with ACPR. Leveraging the theory developed for single-shot double auction and taking the PowerTAC wholesale market PDA as our testbed, we proceed by modeling the PDA of PowerTAC as an MDP. We propose a novel bidding strategy, namely MDPLCPBS. We empirically show that MDPLCPBS follows the equilibrium strategy for double auctions that we previously analyze. In addition, we benchmark our strategy against the baseline and the state-of-the-art bidding strategies for the PowerTAC wholesale market PDAs, and show that MDPLCPBS outperforms most of them consistently.
Beyond Natural Proofs: Hardness Magnification and Locality
Venue: arXiv cs.CC 2019
Year: 2019

Hardness magnification reduces major complexity separations (such as $\mathsf{\mathsf{EXP}} \nsubseteq \mathsf{NC}^1$) to proving lower bounds for some natural problem $Q$ against weak circuit models. Several recent works [OS18, MMW19, CT19, OPS19, CMMW19, Oli19, CJW19a] have established results of this form. In the most intriguing cases, the required lower bound is known for problems that appear to be significantly easier than $Q$, while $Q$ itself is susceptible to lower bounds but these are not yet sufficient for magnification. In this work, we provide more examples of this phenomenon, and investigate the prospects of proving new lower bounds using this approach. In particular, we consider the following essential questions associated with the hardness magnification program: Does hardness magnification avoid the natural proofs barrier of Razborov and Rudich [RR97]? Can we adapt known lower bound techniques to establish the desired lower bound for $Q$?
Energy Usage Reports: Environmental awareness as part of algorithmic accountability
Venue: arXiv cs.LG 2019
Year: 2019

The carbon footprint of algorithms must be measured and transparently reported so computer scientists can take an honest and active role in environmental sustainability. In this paper, we take analyses usually applied at the industrial level and make them accessible for individual computer science researchers with an easy-to-use Python package. Localizing to the energy mixture of the electrical power grid, we make the conversion from energy usage to CO2 emissions, in addition to contextualizing these results with more human-understandable benchmarks such as automobile miles driven. We also include comparisons with energy mixtures employed in electrical grids around the world. We propose including these automatically-generated Energy Usage Reports as part of standard algorithmic accountability practices, and demonstrate the use of these reports as part of model-choice in a machine learning context.
Volenti non fit injuria: Ransomware and its Victims
Venue: arXiv cs.CR 2019
Year: 2019

With the recent growth in the number of malicious activities on the internet, cybersecurity research has seen a boost in the past few years. However, as certain variants of malware can provide highly lucrative opportunities for bad actors, significant resources are dedicated to innovations and improvements by vast criminal organisations. Among these forms of malware, ransomware has experienced a significant recent rise as it offers the perpetrators great financial incentive. Ransomware variants operate by removing system access from the user by either locking the system or encrypting some or all of the data, and subsequently demanding payment or ransom in exchange for returning system access or providing a decryption key to the victim. Due to the ubiquity of sensitive data in many aspects of modern life, many victims of such attacks, be they an individual home user or operators of a business, are forced to pay the ransom to regain access to their data, which in many cases does not happen as renormalisation of system operations is never guaranteed. As the problem of ransomware does not seem to be subsiding, it is very important to investigate the underlying forces driving and facilitating such attacks in order to create preventative measures. As such, in this paper, we discuss and provide further insight into variants of ransomware and their victims in order to understand how and why they have been targeted and what can be done to prevent or mitigate the effects of such attacks.
On the path partition number of 6-regular graphs
Venue: arXiv cs.DM 2019
Year: 2019

A path partition (also referred to as a linear forest) of a graph $G$ is a set of vertex-disjoint paths which together contain all the vertices of $G$. An isolated vertex is considered to be a path in this case. The path partition conjecture states that every $n$-vertices $d$-regular graph has a path partition with at most $\frac{n}{d+1}$ paths. The conjecture has been proved for all $d<6$. We prove the conjecture for $d=6$.
Towards a computer-interpretable actionable formal model to encode data governance rules
Venue: arXiv cs.AI 2019
Year: 2019

With the needs of science and business, data sharing and re-use has become an intensive activity for various areas. In many cases, governance imposes rules concerning data use, but there is no existing computational technique to help data-users comply with such rules. We argue that intelligent systems can be used to improve the situation, by recording provenance records during processing, encoding the rules and performing reasoning. We present our initial work, designing formal models for data rules and flow rules and the reasoning system, as the first step towards helping data providers and data users sustain productive relationships.
Sibling Neural Estimators: Improving Iterative Image Decoding with Gradient Communication
Venue: arXiv cs.CV 2019
Year: 2019

For lossy image compression, we develop a neural-based system which learns a nonlinear estimator for decoding from quantized representations. The system links two recurrent networks that \help" each other reconstruct same target image patches using complementary portions of spatial context that communicate via gradient signals. This dual agent system builds upon prior work that proposed the iterative refinement algorithm for recurrent neural network (RNN)based decoding which improved image reconstruction compared to standard decoding techniques. Our approach, which works with any encoder, neural or non-neural, This system progressively reduces image patch reconstruction error over a fixed number of steps. Experiment with variants of RNN memory cells, with and without future information, find that our model consistently creates lower distortion images of higher perceptual quality compared to other approaches. Specifically, on the Kodak Lossless True Color Image Suite, we observe as much as a 1:64 decibel (dB) gain over JPEG, a 1:46 dB gain over JPEG 2000, a 1:34 dB gain over the GOOG neural baseline, 0:36 over E2E (a modern competitive neural compression model), and 0:37 over a single iterative neural decoder.
Action Recognition Using Volumetric Motion Representations
Venue: arXiv cs.CV 2019
Year: 2019

Traditional action recognition models are constructed around the paradigm of 2D perspective imagery. Though sophisticated time-series models have pushed the field forward, much of the information is still not exploited by confining the domain to 2D. In this work, we introduce a novel representation of motion as a voxelized 3D vector field and demonstrate how it can be used to improve performance of action recognition networks. This volumetric representation is a natural fit for 3D CNNs, and allows out-of-plane data augmentation techniques during training of these networks. Both the construction of this representation from RGB-D video and inference can be run in real time. We demonstrate superior results using this representation with our network design on the open-source NTU RGB+D dataset where it outperforms state-of-the-art on both of the defined evaluation metrics. Furthermore, we experimentally show how the out-of-plane augmentation techniques create viewpoint invariance and allow the model trained using this representation to generalize to unseen camera angles. Code is available here: https://github.com/mpeven/ntu_rgb.
Topological properties of secure wireless sensor networks under the q-composite key predistribution scheme with unreliable links
Venue: arXiv cs.NI 2019
Year: 2019

Security is an important issue in wireless sensor networks (WSNs), which are often deployed in hostile environments. The q-composite key predistribution scheme has been recognized as a suitable approach to secure WSNs. Although the q-composite scheme has received much attention in the literature, there is still a lack of rigorous analysis for secure WSNs operating under the q-composite scheme in consideration of the unreliability of links. One main difficulty lies in analyzing the network topology, whose links are not independent. Wireless links can be unreliable in practice due to the presence of physical barriers between sensors or because of harsh environmental conditions severely impairing communications. In this paper, we resolve the difficult challenge and investigate topological properties related to node degree in WSNs operating under the q-composite scheme with unreliable communication links modeled as independent ON/OFF channels. Specifically, we derive the asymptotically exact probability for the property of minimum degree being at least k, present the asymptotic probability distribution for the minimum degree, and demonstrate that the number of nodes with a fixed degree is in distribution asymptotically equivalent to a Poisson random variable. We further use the theoretical results to provide useful design guidelines for secure WSNs. Experimental results also confirm the validity of our analytical findings.
Representation Learning with Multisets
Venue: arXiv cs.LG 2019
Year: 2019

We study the problem of learning permutation invariant representations that can capture "flexible" notions of containment. We formalize this problem via a measure theoretic definition of multisets, and obtain a theoretically-motivated learning model. We propose training this model on a novel task: predicting the size of the symmetric difference (or intersection) between pairs of multisets. We demonstrate that our model not only performs very well on predicting containment relations (and more effectively predicts the sizes of symmetric differences and intersections than DeepSets-based approaches with unconstrained object representations), but that it also learns meaningful representations.
A Benchmark Suite for Evaluating Caches' Vulnerability to Timing Attacks
Venue: arXiv cs.CR 2019
Year: 2019

Timing-based side or covert channels in processor caches continue to present a threat to computer systems, and they are the key to many of the recent Spectre and Meltdown attacks. Based on improvements to an existing three-step model for cache timing-based attacks, this work presents 88 Strong types of theoretical timing-based vulnerabilities in processor caches. To understand and evaluate all possible types of vulnerabilities in processor caches, this work further presents and implements a new benchmark suite which can be used to test to which types of cache timing-based attacks a given processor or cache design is vulnerable. In total, there are 1094 automatically-generated test programs which cover the 88 theoretical vulnerabilities. The benchmark suite generates the Cache Timing Vulnerability Score which can be used to evaluate how vulnerable a specific cache implementation is to different attacks. A smaller Cache Timing Vulnerability Score means the design is more secure, and the scores among different machines can be easily compared. Evaluation is conducted on commodity Intel and AMD processors and shows the differences in processor implementations can result in different types of attacks that they are vulnerable to. Beyond testing commodity processors, the benchmarks and the Cache Timing Vulnerability Score can be used to help designers of new secure processor caches evaluate their design's susceptibility to cache timing-based attacks.
Deep Anomaly Detection with Deviation Networks
Venue: arXiv cs.LG 2019
Year: 2019

Although deep learning has been applied to successfully address many data mining problems, relatively limited work has been done on deep learning for anomaly detection. Existing deep anomaly detection methods, which focus on learning new feature representations to enable downstream anomaly detection methods, perform indirect optimization of anomaly scores, leading to data-inefficient learning and suboptimal anomaly scoring. Also, they are typically designed as unsupervised learning due to the lack of large-scale labeled anomaly data. As a result, they are difficult to leverage prior knowledge (e.g., a few labeled anomalies) when such information is available as in many real-world anomaly detection applications. This paper introduces a novel anomaly detection framework and its instantiation to address these problems. Instead of representation learning, our method fulfills an end-to-end learning of anomaly scores by a neural deviation learning, in which we leverage a few (e.g., multiple to dozens) labeled anomalies and a prior probability to enforce statistically significant deviations of the anomaly scores of anomalies from that of normal data objects in the upper tail. Extensive results show that our method can be trained substantially more data-efficiently and achieves significantly better anomaly scoring than state-of-the-art competing methods.
Unified Multifaceted Feature Learning for Person Re-Identification
Venue: arXiv cs.CV 2019
Year: 2019

Person re-identification (ReID) aims at re-identifying persons from different viewpoints across multiple cameras, of which it is of great importance to learn multifaceted features expressed in different parts of a person, e.g., clothes, bags, and other accessories in the main body, appearance in the head, and shoes in the foot. To learn such features, existing methods are focused on the striping-based approach that builds multi-branch neural networks to learn local features in each part of the identities, with one-branch network dedicated to one part. This results in complex models with a large number of parameters. To address this issue, this paper proposes to learn the multifaceted features in a simple unified single-branch neural network. The Unified Multifaceted Feature Learning (UMFL) framework is introduced to fulfill this goal, which consists of two key collaborative modules: compound batch image erasing (including batch constant erasing and random erasing) and hierarchical structured loss. The loss structures the augmented images resulted by the two types of image erasing in a two-level hierarchy and enforces multifaceted attention to different parts. As we show in the extensive experimental results on four benchmark person ReID datasets, despite the use of significantly simplified network structure, our method performs substantially better than state-of-the-art competing methods. Our method can also effectively generalize to vehicle ReID, achieving similar improvement on two vehicle ReID datasets.
Bayesian Curiosity for Efficient Exploration in Reinforcement Learning
Venue: arXiv cs.LG 2019
Year: 2019

Balancing exploration and exploitation is a fundamental part of reinforcement learning, yet most state-of-the-art algorithms use a naive exploration protocol like $ε$-greedy. This contributes to the problem of high sample complexity, as the algorithm wastes effort by repeatedly visiting parts of the state space that have already been explored. We introduce a novel method based on Bayesian linear regression and latent space embedding to generate an intrinsic reward signal that encourages the learning agent to seek out unexplored parts of the state space. This method is computationally efficient, simple to implement, and can extend any state-of-the-art reinforcement learning algorithm. We evaluate the method on a range of algorithms and challenging control tasks, on both simulated and physical robots, demonstrating how the proposed method can significantly improve sample complexity.
Controlling Neural Machine Translation Formality with Synthetic Supervision
Venue: arXiv cs.CL 2019
Year: 2019

This work aims to produce translations that convey source language content at a formality level that is appropriate for a particular audience. Framing this problem as a neural sequence-to-sequence task ideally requires training triplets consisting of a bilingual sentence pair labeled with target language formality. However, in practice, available training examples are limited to English sentence pairs of different styles, and bilingual parallel sentences of unknown formality. We introduce a novel training scheme for multi-task models that automatically generates synthetic training triplets by inferring the missing element on the fly, thus enabling end-to-end training. Comprehensive automatic and human assessments show that our best model outperforms existing models by producing translations that better match desired formality levels while preserving the source meaning.
Graph-Driven Generative Models for Heterogeneous Multi-Task Learning
Venue: arXiv cs.LG 2019
Year: 2019

We propose a novel graph-driven generative model, that unifies multiple heterogeneous learning tasks into the same framework. The proposed model is based on the fact that heterogeneous learning tasks, which correspond to different generative processes, often rely on data with a shared graph structure. Accordingly, our model combines a graph convolutional network (GCN) with multiple variational autoencoders, thus embedding the nodes of the graph i.e., samples for the tasks) in a uniform manner while specializing their organization and usage to different tasks. With a focus on healthcare applications (tasks), including clinical topic modeling, procedure recommendation and admission-type prediction, we demonstrate that our method successfully leverages information across different tasks, boosting performance in all tasks and outperforming existing state-of-the-art approaches.
DermGAN: Synthetic Generation of Clinical Skin Images with Pathology
Venue: arXiv cs.CV 2019
Year: 2019

Despite the recent success in applying supervised deep learning to medical imaging tasks, the problem of obtaining large and diverse expert-annotated datasets required for the development of high performant models remains particularly challenging. In this work, we explore the possibility of using Generative Adverserial Networks (GAN) to synthesize clinical images with skin condition. We propose DermGAN, an adaptation of the popular Pix2Pix architecture, to create synthetic images for a pre-specified skin condition while being able to vary its size, location and the underlying skin color. We demonstrate that the generated images are of high fidelity using objective GAN evaluation metrics. In a Human Turing test, we note that the synthetic images are not only visually similar to real images, but also embody the respective skin condition in dermatologists' eyes. Finally, when using the synthetic images as a data augmentation technique for training a skin condition classifier, we observe that the model performs comparably to the baseline model overall while improving on rare but malignant conditions.
Towards Ghost-free Shadow Removal via Dual Hierarchical Aggregation Network and Shadow Matting GAN
Venue: arXiv cs.CV 2019
Year: 2019

Shadow removal is an essential task for scene understanding. Many studies consider only matching the image contents, which often causes two types of ghosts: color in-consistencies in shadow regions or artifacts on shadow boundaries. In this paper, we tackle these issues in two ways. First, to carefully learn the border artifacts-free image, we propose a novel network structure named the dual hierarchically aggregation network~(DHAN). It contains a series of growth dilated convolutions as the backbone without any down-samplings, and we hierarchically aggregate multi-context features for attention and prediction, respectively. Second, we argue that training on a limited dataset restricts the textural understanding of the network, which leads to the shadow region color in-consistencies. Currently, the largest dataset contains 2k+ shadow/shadow-free image pairs. However, it has only 0.1k+ unique scenes since many samples share exactly the same background with different shadow positions. Thus, we design a shadow matting generative adversarial network~(SMGAN) to synthesize realistic shadow mattings from a given shadow mask and shadow-free image. With the help of novel masks or scenes, we enhance the current datasets using synthesized shadow images. Experiments show that our DHAN can erase the shadows and produce high-quality ghost-free images. After training on the synthesized and real datasets, our network outperforms other state-of-the-art methods by a large margin. The code is available: http://github.com/vinthony/ghost-free-shadow-removal/